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

Source/core/dom/Element.cpp

Index: Source/core/dom/Element.cpp
diff --git a/Source/core/dom/Element.cpp b/Source/core/dom/Element.cpp
index 56e69b05bac772a198385b665d19f8c410ddd634..707678c968dee84f0010477443b4f981db45dc10 100644
--- a/Source/core/dom/Element.cpp
+++ b/Source/core/dom/Element.cpp
@@ -1514,6 +1514,15 @@ StyleRecalcChange Element::recalcOwnStyle(StyleRecalcChange change)
     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());
@@ -1537,29 +1546,41 @@ void Element::recalcChildStyle(StyleRecalcChange change)
     bool hasIndirectAdjacentRules = childrenAffectedByForwardPositionalRules();
     bool forceCheckOfNextElementSibling = false;
     bool forceCheckOfAnyElementSibling = false;
-    bool forceReattachOfAnyWhitespaceSibling = false;
-    for (Node* child = firstChild(); child; child = child->nextSibling()) {
-        bool didReattach = false;
-
-        if (child->renderer())
-            forceReattachOfAnyWhitespaceSibling = false;
-
-        if (child->isTextNode()) {
-            if (forceReattachOfAnyWhitespaceSibling && toText(child)->containsOnlyWhitespace())
-                child->reattach();
-            else
-                didReattach = toText(child)->recalcTextStyle(change);
-        } else if (child->isElementNode()) {
+    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->isTextNode()) {
+            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);
             if (shouldRecalcStyle(change, element)) {
                 parentPusher.push();
                 didReattach = element->recalcStyle(change);
@@ -1568,9 +1589,12 @@ void Element::recalcChildStyle(StyleRecalcChange change)
             }
         }
 
-        forceReattachOfAnyWhitespaceSibling = didReattach || forceReattachOfAnyWhitespaceSibling;
+        if (didReattach)
+            child->reattachWhitespaceSiblings();
     }
 
+    recalcWhitespaceChildrenStyle(whitespaceChildren, change);
+
     if (shouldRecalcStyle(change, this)) {
         updatePseudoElement(AFTER, change);
         updatePseudoElement(BACKDROP, change);
@@ -1740,7 +1764,7 @@ static void checkForSiblingStyleChanges(Element* e, RenderStyle* style, bool fin
     // 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();
     }
 }