Reverse style resolution to avoid N^2 walk when building the render tree

Source/core/dom/Element.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Peter Kelly (pmk@post.com)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  *           (C) 2007 David Smith (catfish.man@gmail.com)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012, 2013 Apple Inc. All rights reserved.
  *           (C) 2007 Eric Seidel (eric@webkit.org)
  *
  * This library is free software; you can redistribute it and/or
@@ skipping 1496 matching lines @@
         document().styleResolver()->invalidateMatchedPropertiesCache();
         return Force;
     }
 
     if (styleChangeType() >= SubtreeStyleChange)
         return Force;
 
     return max(localChange, change);
 }
 
+static const int maxWhitespaceChildrenToDefer = 10;
+typedef Vector<Text*, maxWhitespaceChildrenToDefer> DeferredWhitespaceChildren;
+
+static inline void recalcWhitespaceChildrenStyle(DeferredWhitespaceChildren& whitespaceChildren, StyleRecalcChange change)
+{
+    for (int i = whitespaceChildren.size() - 1; i >= 0; --i)
+        whitespaceChildren[i]->recalcTextStyle(change);
+}
+
 void Element::recalcChildStyle(StyleRecalcChange change)
 {
     ASSERT(document().inStyleRecalc());
 
     StyleResolverParentPusher parentPusher(this);
 
     for (ShadowRoot* root = youngestShadowRoot(); root; root = root->olderShadowRoot()) {
         if (shouldRecalcStyle(change, root)) {
             parentPusher.push();
             root->recalcStyle(change);
         }
     }
 
     if (shouldRecalcStyle(change, this))
         updatePseudoElement(BEFORE, change);
 
     // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar.
     // For now we will just worry about the common case, since it's a lot trickier to get the second case right
     // without doing way too much re-resolution.
     bool hasDirectAdjacentRules = childrenAffectedByDirectAdjacentRules();
     bool hasIndirectAdjacentRules = childrenAffectedByForwardPositionalRules();
     bool forceCheckOfNextElementSibling = false;
     bool forceCheckOfAnyElementSibling = false;
-    bool forceReattachOfAnyWhitespaceSibling = false;
-    for (Node* child = firstChild(); child; child = child->nextSibling()) {
+    if (hasDirectAdjacentRules || hasIndirectAdjacentRules) {
+        for (Node* child = firstChild(); child; child = child->nextSibling()) {
+            if (!child->isElementNode())
+                continue;
+            Element* element = toElement(child);
+            bool childRulesChanged = element->needsStyleRecalc() && element->styleChangeType() >= SubtreeStyleChange;
+            if (forceCheckOfNextElementSibling || forceCheckOfAnyElementSibling)
+                element->setNeedsStyleRecalc();
+            forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
+            forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
+        }
+    }
+    // This loop is deliberately backwards because we use insertBefore in the rendering tree, and want to avoid
+    // a potentially n^2 loop to find the insertion point while resolving style. Having us start from the last
+    // child and work our way back means in the common case, we'll find the insertion point in O(1) time.
+    // Reversing this loop can lead to non-deterministic results in our code to optimize out empty whitespace
+    // RenderTexts. We try to put off recalcing their style until the end to avoid this issue.
+    // See crbug.com/288225
+    DeferredWhitespaceChildren whitespaceChildren;
+    for (Node* child = lastChild(); child; child = child->previousSibling()) {
         bool didReattach = false;
 
-        if (child->renderer())
-            forceReattachOfAnyWhitespaceSibling = false;
-
         if (child->isTextNode()) {
-            if (forceReattachOfAnyWhitespaceSibling && toText(child)->containsOnlyWhitespace())
-                child->reattach();
-            else
+            Text* textChild = toText(child);
+            if (textChild->containsOnlyWhitespace()) {

[esprehn, 2013/09/30 22:55:34]

This also makes us do the string scan for whitespace on every text node. The
boolean meant we didn't do that except when something reattached. We should be
really careful, this makes us probe the string contents of every string as the
recalcStyle loop walks down the tree.

Watch the perf bots for that.

+                if (whitespaceChildren.size() == maxWhitespaceChildrenToDefer) {
+                    recalcWhitespaceChildrenStyle(whitespaceChildren, change);
+                    whitespaceChildren.clear();
+                }
+                whitespaceChildren.append(textChild);
+            } else {
                 didReattach = toText(child)->recalcTextStyle(change);
+            }
         } else if (child->isElementNode()) {
             Element* element = toElement(child);
-
-            bool childRulesChanged = element->needsStyleRecalc() && element->styleChangeType() >= SubtreeStyleChange;
-
-            if (forceCheckOfNextElementSibling || forceCheckOfAnyElementSibling)
-                element->setNeedsStyleRecalc();
-
-            forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
-            forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
-
             if (shouldRecalcStyle(change, element)) {
                 parentPusher.push();
                 didReattach = element->recalcStyle(change);
             } else if (document().styleResolver()->supportsStyleSharing(element)) {
                 document().styleResolver()->addToStyleSharingList(element);
             }
         }
 
-        forceReattachOfAnyWhitespaceSibling = didReattach || forceReattachOfAnyWhitespaceSibling;
+        if (didReattach)
+            child->reattachWhitespaceSiblings();
     }
 
+    recalcWhitespaceChildrenStyle(whitespaceChildren, change);
+
     if (shouldRecalcStyle(change, this)) {
         updatePseudoElement(AFTER, change);
         updatePseudoElement(BACKDROP, change);
     }
 }
 
 ElementShadow* Element::shadow() const
 {
     return hasRareData() ? elementRareData()->shadow() : 0;
 }
@@ skipping 149 matching lines @@
 
         // We also have to handle node removal.  The parser callback case is similar to node removal as well in that we need to change the last child
         // to match now.
         if ((childCountDelta < 0 || finishedParsingCallback) && newLastChild == lastElementBeforeInsertion && newLastChild && (!newLastChildStyle || !newLastChildStyle->lastChildState()))
             newLastChild->setNeedsStyleRecalc();
     }
 
     // The + selector.  We need to invalidate the first element following the insertion point.  It is the only possible element
     // that could be affected by this DOM change.
     if (e->childrenAffectedByDirectAdjacentRules() && afterChange) {
-        if (Node* firstElementAfterInsertion = afterChange->nextElementSibling())
+        if (Node* firstElementAfterInsertion = afterChange->isElementNode() ? afterChange : afterChange->nextElementSibling())
             firstElementAfterInsertion->setNeedsStyleRecalc();
     }
 }
 
 void Element::childrenChanged(bool changedByParser, Node* beforeChange, Node* afterChange, int childCountDelta)
 {
     ContainerNode::childrenChanged(changedByParser, beforeChange, afterChange, childCountDelta);
     if (changedByParser)
         checkForEmptyStyleChange(this, renderStyle());
     else
@@ skipping 1888 matching lines @@
     return 0;
 }
 
 Attribute* UniqueElementData::attributeItem(unsigned index)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(index < length());
     return &m_attributeVector.at(index);
 }
 
 } // namespace WebCore