Avoid N^2 walk placing renderers 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 147 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()) {
+    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();
     }
 
     styleResolver->popParentShadowRoot(this);
     clearNeedsStyleRecalc();
     clearChildNeedsStyleRecalc();
 }
 
 bool ShadowRoot::isActive() const
 {
     for (ShadowRoot* shadowRoot = youngerShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot())
@@ skipping 111 matching lines @@
 {
     MemoryClassInfo info(memoryObjectInfo, this, WebCoreMemoryTypes::DOM);
     DocumentFragment::reportMemoryUsage(memoryObjectInfo);
     TreeScope::reportMemoryUsage(memoryObjectInfo);
     info.addMember(m_prev, "prev");
     info.addMember(m_next, "next");
     info.addMember(m_scopeDistribution, "scopeDistribution");
 }
 
 }