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 1412 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());
         } else if (attached() && isActiveInsertionPoint(this)) {
             // Active InsertionPoints will never have renderers so there's no reason to
             // reattach them repeatedly once they're already attached.
             localChange = change;
         }
         if (localChange == Detach) {
             AttachContext reattachContext;
             reattachContext.resolvedStyle = newStyle.get();
             reattach(reattachContext);
@@ skipping 43 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;
-    for (Node *n = firstChild(); n; n = n->nextSibling()) {
+    int indexForChild = 0;

[esprehn, 2013/07/11 01:24:32]

childIndex

[leviw_travelin_and_unemployed, 2013/07/11 01:35:11]

childIndex is an input parameter.

+    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))

[esprehn, 2013/07/11 01:24:32]

Remove extra parens?

[leviw_travelin_and_unemployed, 2013/07/11 01:35:11]

Good call.

+                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()) {

[esprehn, 2013/07/11 01:24:32]

Can we rename n to child? I did this in my patch.

+        --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);
+            element->recalcStyle(change, max(indexForChild + 1, 0));

[esprehn, 2013/07/11 01:24:32]

Above just do

childIndex = max(childIndex - 1, 0);

?

[leviw_travelin_and_unemployed, 2013/07/11 01:35:11]

We need to decrement throughout the entire loop, not just here.

         }
-        forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
-        forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
     }
 
     if (shouldRecalcStyle(change, this))
         updatePseudoElement(AFTER, change);
 
     clearNeedsStyleRecalc();
     clearChildNeedsStyleRecalc();
 
     if (hasCustomStyleCallbacks())
         didRecalcStyle(change);
@@ skipping 2033 matching lines @@
     return 0;
 }
 
 Attribute* UniqueElementData::attributeItem(unsigned index)
 {
     ASSERT_WITH_SECURITY_IMPLICATION(index < length());
     return &m_attributeVector.at(index);
 }
 
 } // namespace WebCore