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

Source/core/dom/shadow/ShadowRoot.cpp

Index: Source/core/dom/shadow/ShadowRoot.cpp
diff --git a/Source/core/dom/shadow/ShadowRoot.cpp b/Source/core/dom/shadow/ShadowRoot.cpp
index f59e922b8a4b367dc74da613a68f7321de2c1b71..67254d7e6ddcf370093c1654b25a81a97eae72dd 100644
--- a/Source/core/dom/shadow/ShadowRoot.cpp
+++ b/Source/core/dom/shadow/ShadowRoot.cpp
@@ -183,22 +183,16 @@ void ShadowRoot::recalcStyle(StyleRecalcChange change)
 
     // FIXME: This doesn't handle :hover + div properly like Element::recalcStyle does.
     bool forceReattachOfAnyWhitespaceSibling = false;
-    for (Node* child = firstChild(); child; child = child->nextSibling()) {
+    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
-                didReattach = toText(child)->recalcTextStyle(change);
-        } else if (child->isElementNode() && shouldRecalcStyle(change, child)) {
+        if (child->isTextNode())
+            didReattach = toText(child)->recalcTextStyle(change);
+        else if (child->isElementNode() && shouldRecalcStyle(change, child))
             didReattach = toElement(child)->recalcStyle(change);
-        }
 
-        forceReattachOfAnyWhitespaceSibling = didReattach || forceReattachOfAnyWhitespaceSibling;
+        if (didReattach)
+            child->reattachWhitespaceSiblings();

[esprehn, 2013/09/30 22:52:03]

You're missing the nasty whitespace stuff in here... I think you want to
encapsulate that inside something like a WhitespaceChildList that inside
append() understands when it hits the limit to call the recalc loop.

WhitespaceChildList whitespaceChildren;

whitespaceChildren.append(...);

to hide all the nastiness.

     }
 
     styleResolver->popParentShadowRoot(*this);