Avoid N^2 walk placing renderers 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 4d3bae11dc22da0efb848f2c39ba49160f8fa334..3f83261a75a8091a5af90a44478a08b15917864f 100644
--- a/Source/core/dom/Element.cpp
+++ b/Source/core/dom/Element.cpp
@@ -1429,22 +1429,22 @@ bool Element::pseudoStyleCacheIsInvalid(const RenderStyle* currentStyle, RenderS
     return false;
 }
 
-PassRefPtr<RenderStyle> Element::styleForRenderer()
+PassRefPtr<RenderStyle> Element::styleForRenderer(int childIndex)
 {
     if (hasCustomStyleCallbacks()) {
         if (RefPtr<RenderStyle> style = customStyleForRenderer())
             return style.release();
     }
 
-    return originalStyleForRenderer();
+    return originalStyleForRenderer(childIndex);
 }
 
-PassRefPtr<RenderStyle> Element::originalStyleForRenderer()
+PassRefPtr<RenderStyle> Element::originalStyleForRenderer(int childIndex)
 {
-    return document()->styleResolver()->styleForElement(this);
+    return document()->styleResolver()->styleForElement(this, childIndex);
 }
 
-void Element::recalcStyle(StyleChange change)
+void Element::recalcStyle(StyleChange change, int childIndex)
 {
     ASSERT(document()->inStyleRecalc());
 
@@ -1468,7 +1468,7 @@ void Element::recalcStyle(StyleChange change)
             // FIXME: This still recalcs style twice when changing display types, but saves
             // us from recalcing twice when going from none -> anything else which is more
             // common, especially during lazy attach.
-            newStyle = styleForRenderer();
+            newStyle = styleForRenderer(childIndex);
             localChange = Node::diff(currentStyle.get(), newStyle.get(), document());
         } else if (attached() && isActiveInsertionPoint(this)) {
             // Active InsertionPoints will never have renderers so there's no reason to
@@ -1532,7 +1532,24 @@ void Element::recalcStyle(StyleChange change)
     // without doing way too much re-resolution.
     bool forceCheckOfNextElementSibling = false;
     bool forceCheckOfAnyElementSibling = false;
-    for (Node *n = firstChild(); n; n = n->nextSibling()) {
+    int indexForChild = 0;
+    if (hasDirectAdjacentRules || hasIndirectAdjacentRules) {
+        for (Node *n = firstChild(); n; n = n->nextSibling()) {
+            ++indexForChild;
+            if (!n->isElementNode())
+                continue;
+            Element* element = toElement(n);
+            bool childRulesChanged = element->needsStyleRecalc() && element->styleChangeType() == FullStyleChange;
+            if ((forceCheckOfNextElementSibling || forceCheckOfAnyElementSibling))
+                element->setNeedsStyleRecalc();
+            forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
+            forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
+        }
+    }
+    // FIXME: Reversing the loop we call recalcStyle avoids an N^2 walk through the DOM to find the next renderer
+    // to insert before. The logic in NodeRenderingContext should be improved to make this unnecessary.
+    for (Node *n = lastChild(); n; n = n->previousSibling()) {
+        --indexForChild;
         if (n->isTextNode()) {
             toText(n)->recalcTextStyle(change);
             continue;
@@ -1540,15 +1557,10 @@ void Element::recalcStyle(StyleChange change)
         if (!n->isElementNode())
             continue;
         Element* element = toElement(n);
-        bool childRulesChanged = element->needsStyleRecalc() && element->styleChangeType() == FullStyleChange;
-        if ((forceCheckOfNextElementSibling || forceCheckOfAnyElementSibling))
-            element->setNeedsStyleRecalc();
         if (shouldRecalcStyle(change, element)) {
             parentPusher.push();
-            element->recalcStyle(change);
+            element->recalcStyle(change, max(indexForChild + 1, 0));
         }
-        forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
-        forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
     }
 
     if (shouldRecalcStyle(change, this))