Avoid N^2 walk placing renderers 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 1329 matching lines @@
                 // is needed, but for now just assume a layout will be required.  The diff code
                 // in RenderObject::setStyle would need to be factored out so that it could be reused.
                 renderer()->setNeedsLayoutAndPrefWidthsRecalc();
             }
             return true;
         }
     }
     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());
 
     if (hasCustomStyleCallbacks())
         willRecalcStyle(change);
 
     // Ref currentStyle in case it would otherwise be deleted when setting the new style in the renderer.
     RefPtr<RenderStyle> currentStyle(renderStyle());
     bool hasParentStyle = parentNodeForRenderingAndStyle() ? static_cast<bool>(parentNodeForRenderingAndStyle()->renderStyle()) : false;
     bool hasDirectAdjacentRules = childrenAffectedByDirectAdjacentRules();
     bool hasIndirectAdjacentRules = childrenAffectedByForwardPositionalRules();
 
     if ((change > NoChange || needsStyleRecalc())) {
         if (hasRareData())
             elementRareData()->resetComputedStyle();
     }
     if (hasParentStyle && (change >= Inherit || needsStyleRecalc())) {
         StyleChange localChange = Detach;
         RefPtr<RenderStyle> newStyle;
         if (currentStyle) {
             // 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());
         }
         if (localChange == Detach) {
             // FIXME: The style gets computed twice by calling attach. We could do better if we passed the style along.
             reattach();
             // attach recalculates the style for all children. No need to do it twice.
             clearNeedsStyleRecalc();
             clearChildNeedsStyleRecalc();
 
             if (hasCustomStyleCallbacks())
@@ skipping 35 matching lines @@
     }
 
     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 forceCheckOfNextElementSibling = false;
     bool forceCheckOfAnyElementSibling = false;
+    int indexForChild = 0;
     for (Node *n = firstChild(); n; n = n->nextSibling()) {
+        ++indexForChild;
         if (n->isTextNode()) {
             toText(n)->recalcTextStyle(change);
             continue;
         } 
         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);
-        }
         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()) {
+        if (n->isTextNode() || !n->isElementNode())

[esprehn, 2013/06/05 00:12:26]

You don't need to check for isTextNode, it's already covered by the
isElementNode check.

+            continue;
+        Element* element = toElement(n);
+        if (shouldRecalcStyle(change, element)) {
+            parentPusher.push();
+            element->recalcStyle(change, indexForChild);
+        }
+        --indexForChild;
+    }
 
     if (shouldRecalcStyle(change, this))
         updatePseudoElement(AFTER, change);
 
     clearNeedsStyleRecalc();
     clearChildNeedsStyleRecalc();
     
     if (hasCustomStyleCallbacks())
         didRecalcStyle(change);
     InspectorInstrumentation::didRecalculateStyleForElement(this);
@@ skipping 1630 matching lines @@
     return 0;
 }
 
 Attribute* UniqueElementData::attributeItem(unsigned index)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(index < length());
     return &m_attributeVector.at(index);
 }
 
 } // namespace WebCore