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 165 matching lines @@
     }
 
     // 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()) {
+    for (Node* child = lastChild(); child; child = child->previousSibling()) {
         bool didReattach = false;
 
-        if (child->renderer())
-            forceReattachOfAnyWhitespaceSibling = false;
+        if (child->isTextNode())
+            didReattach = toText(child)->recalcTextStyle(change);
+        else if (child->isElementNode() && shouldRecalcStyle(change, child))
+            didReattach = toElement(child)->recalcStyle(change);
 
-        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;
+        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);
     clearNeedsStyleRecalc();
     clearChildNeedsStyleRecalc();
 }
 
 bool ShadowRoot::isActive() const
 {
     for (ShadowRoot* shadowRoot = youngerShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot())
@@ skipping 205 matching lines @@
 
 StyleSheetList* ShadowRoot::styleSheets()
 {
     if (!ensureShadowRootRareData()->styleSheets())
         m_shadowRootRareData->setStyleSheets(StyleSheetList::create(this));
 
     return m_shadowRootRareData->styleSheets();
 }
 
 }