Avoid N^2 walk placing renderers when building the render tree

Source/core/dom/ContainerNodeAlgorithms.h

 /*
  * Copyright (C) 2007 Apple Inc. All rights reserved.
  *           (C) 2008 Nikolas Zimmermann <zimmermann@kde.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 200 matching lines @@
 }
 
 inline void ChildNodeInsertionNotifier::notify(Node* node)
 {
     ASSERT(!NoEventDispatchAssertion::isEventDispatchForbidden());
 
     InspectorInstrumentation::didInsertDOMNode(node->document(), node);
 
     RefPtr<Document> protectDocument(node->document());
     RefPtr<Node> protectNode(node);
+    InsertionCallbackDeferer insertionCallbackDeferer;
 
     if (m_insertionPoint->inDocument())
         notifyNodeInsertedIntoDocument(node);
     else if (node->isContainerNode())
         notifyNodeInsertedIntoTree(toContainerNode(node));
 
-    for (size_t i = 0; i < m_postInsertionNotificationTargets.size(); ++i)
-        m_postInsertionNotificationTargets[i]->didNotifySubtreeInsertions(m_insertionPoint);
+    for (size_t i = m_postInsertionNotificationTargets.size(); i; --i)
+        m_postInsertionNotificationTargets[i - 1]->didNotifySubtreeInsertions(m_insertionPoint);

[esprehn, 2013/07/11 01:24:32]

This looks strange, insertedInto happens during appendChild(), it shouldn't have
anything to do with recalcStyle.

[leviw_travelin_and_unemployed, 2013/07/11 01:35:11]

Looking into it, but I've verified we fail 3 tests without this.

fast/forms/radio/radio-group.html
fast/frames/unload-reparent-sibling-frame.html
fast/parser/inline-script-order.html

 }
 
 
 inline void ChildNodeRemovalNotifier::notifyNodeRemovedFromDocument(Node* node)
 {
     ASSERT(m_insertionPoint->inDocument());
     node->removedFrom(m_insertionPoint);
 
     if (node->isContainerNode())
         notifyDescendantRemovedFromDocument(toContainerNode(node));
@@ skipping 90 matching lines @@
         for (Node* child = m_root->firstChild(); child; child = child->nextSibling())
             collectFrameOwners(child);
     }
 
     disconnectCollectedFrameOwners();
 }
 
 } // namespace WebCore
 
 #endif // ContainerNodeAlgorithms_h