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

Source/core/dom/shadow/ShadowRoot.cpp

 /*
  * Copyright (C) 2011 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Neither the name of Google Inc. nor the names of its
@@ skipping 16 matching lines @@
 #include "config.h"
 #include "core/dom/shadow/ShadowRoot.h"
 
 #include "bindings/v8/ExceptionMessages.h"
 #include "bindings/v8/ExceptionState.h"
 #include "core/css/StyleSheetList.h"
 #include "core/css/resolver/StyleResolver.h"
 #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"
 #include "core/editing/markup.h"
 #include "core/platform/HistogramSupport.h"
 
 namespace WebCore {
 
 struct SameSizeAsShadowRoot : public DocumentFragment, public TreeScope, public DoublyLinkedListNode<ShadowRoot> {
     void* pointers[3];
@@ skipping 128 matching lines @@
         return;
     }
 
     // When we're set to lazyAttach we'll have a SubtreeStyleChange and we'll need
     // to promote the change to a Force for all our descendants so they get a
     // recalc and will attach.
     if (styleChangeType() >= SubtreeStyleChange)
         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;
+    WhitespaceChildList whitespaceChildList(change);
+    for (Node* child = lastChild(); child; child = child->previousSibling()) {
+        if (child->isTextNode()) {
+            Text* textChild = toText(child);
+            if (textChild->containsOnlyWhitespace())
+                whitespaceChildList.append(textChild);
+            else
+                textChild->recalcTextStyle(change);
+        } else if (child->isElementNode() && shouldRecalcStyle(change, child)) {
+            toElement(child)->recalcStyle(change);
+        }
+    }
 
-        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)) {
-            didReattach = toElement(child)->recalcStyle(change);
-        }
-
-        forceReattachOfAnyWhitespaceSibling = didReattach || forceReattachOfAnyWhitespaceSibling;
-    }
+    whitespaceChildList.recalcStyle();
 
     styleResolver->popParentShadowRoot(*this);
     clearNeedsStyleRecalc();
     clearChildNeedsStyleRecalc();
 }
 
 bool ShadowRoot::isActive() const
 {
     for (ShadowRoot* shadowRoot = youngerShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot())
         if (!shadowRoot->containsShadowElements())
@@ skipping 204 matching lines @@
 
 StyleSheetList* ShadowRoot::styleSheets()
 {
     if (!ensureShadowRootRareData()->styleSheets())
         m_shadowRootRareData->setStyleSheets(StyleSheetList::create(this));
 
     return m_shadowRootRareData->styleSheets();
 }
 
 }