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..b438adbf0ace5b9e4589cbf912aeb9249557cea0 100644
--- a/Source/core/dom/shadow/ShadowRoot.cpp
+++ b/Source/core/dom/shadow/ShadowRoot.cpp
@@ -34,6 +34,7 @@
 #include "core/dom/ElementTraversal.h"
 #include "core/dom/StyleEngine.h"
 #include "core/dom/Text.h"
+#include "core/dom/WhitespaceChildList.h"
 #include "core/dom/shadow/ElementShadow.h"
 #include "core/dom/shadow/InsertionPoint.h"
 #include "core/dom/shadow/ShadowRootRareData.h"
@@ -182,25 +183,21 @@ void ShadowRoot::recalcStyle(StyleRecalcChange change)
         change = Force;
 
     // FIXME: This doesn't handle :hover + div properly like Element::recalcStyle does.
-    bool forceReattachOfAnyWhitespaceSibling = false;
-    for (Node* child = firstChild(); child; child = child->nextSibling()) {
-        bool didReattach = false;
-
-        if (child->renderer())
-            forceReattachOfAnyWhitespaceSibling = false;
-
+    WhitespaceChildList whitespaceChildList(change);
+    for (Node* child = lastChild(); child; child = child->previousSibling()) {
         if (child->isTextNode()) {
-            if (forceReattachOfAnyWhitespaceSibling && toText(child)->containsOnlyWhitespace())
-                child->reattach();
+            Text* textChild = toText(child);
+            if (textChild->containsOnlyWhitespace())
+                whitespaceChildList.append(textChild);
             else
-                didReattach = toText(child)->recalcTextStyle(change);
+                textChild->recalcTextStyle(change);
         } else if (child->isElementNode() && shouldRecalcStyle(change, child)) {
-            didReattach = toElement(child)->recalcStyle(change);
+            toElement(child)->recalcStyle(change);
         }
-
-        forceReattachOfAnyWhitespaceSibling = didReattach || forceReattachOfAnyWhitespaceSibling;
     }
 
+    whitespaceChildList.recalcStyle();
+
     styleResolver->popParentShadowRoot(*this);
     clearNeedsStyleRecalc();
     clearChildNeedsStyleRecalc();