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

Source/core/dom/ContainerNode.h

Index: Source/core/dom/ContainerNode.h
diff --git a/Source/core/dom/ContainerNode.h b/Source/core/dom/ContainerNode.h
index 28dea402f4a5ff20e07055e35e504bf60f6a3726..93a8f3e42646c728f453b2d2e8fbdbfc70891dae 100644
--- a/Source/core/dom/ContainerNode.h
+++ b/Source/core/dom/ContainerNode.h
@@ -36,6 +36,7 @@ class FloatPoint;
 class HTMLCollection;
 
 typedef void (*NodeCallback)(Node*);
+typedef void (*ElementCallback)(Element*);
 
 namespace Private {
     template<class GenericNode, class GenericNodeContainer>
@@ -80,6 +81,7 @@ private:
 
 class ContainerNode : public Node {
     friend class PostAttachCallbackDisabler;
+    friend class InsertionCallbackDeferer;
 public:
     virtual ~ContainerNode();
 
@@ -133,9 +135,11 @@ public:
 
     virtual void reportMemoryUsage(MemoryObjectInfo*) const OVERRIDE;
 
+    static void queueInsertionCallback(ElementCallback, Element*);
 protected:
     ContainerNode(TreeScope*, ConstructionType = CreateContainer);
 
+    static bool insertionCallbacksAreSuspended();
     static void queuePostAttachCallback(NodeCallback, Node*);
     static bool postAttachCallbacksAreSuspended();
 
@@ -161,6 +165,11 @@ private:
     void suspendPostAttachCallbacks();
     void resumePostAttachCallbacks();
 
+    static void dispatchInsertionCallbacks();
+
+    static void suspendInsertionCallbacks();
+    static void resumeInsertionCallbacks();
+
     bool getUpperLeftCorner(FloatPoint&) const;
     bool getLowerRightCorner(FloatPoint&) const;
 
@@ -270,7 +279,7 @@ class ChildNodesLazySnapshot {
     WTF_MAKE_FAST_ALLOCATED;
 public:
     explicit ChildNodesLazySnapshot(Node* parentNode)
-        : m_currentNode(parentNode->firstChild())
+        : m_currentNode(parentNode->lastChild())
         , m_currentIndex(0)
     {
         m_nextSnapshot = latestSnapshot;
@@ -282,13 +291,13 @@ public:
         latestSnapshot = m_nextSnapshot;
     }
 
-    // Returns 0 if there is no next Node.
-    PassRefPtr<Node> nextNode()
+    // Returns 0 if there is no previous Node.
+    PassRefPtr<Node> previousNode()
     {
         if (LIKELY(!hasSnapshot())) {
             RefPtr<Node> node = m_currentNode;
             if (node)
-                m_currentNode = node->nextSibling();
+                m_currentNode = node->previousSibling();
             return node.release();
         }
         Vector<RefPtr<Node> >& nodeVector = *m_childNodes;
@@ -305,7 +314,7 @@ public:
         Node* node = m_currentNode.get();
         while (node) {
             m_childNodes->append(node);
-            node = node->nextSibling();
+            node = node->previousSibling();
         }
     }
 
@@ -330,6 +339,22 @@ private:
     ChildNodesLazySnapshot* m_nextSnapshot;
 };
 
+// Used to ensure Radio Buttons resolve their checked state in document
+// order when a subtree of them is inserted. This is necessary because
+// we resolve style in reverse document order.
+class InsertionCallbackDeferer {
+public:
+    InsertionCallbackDeferer()
+    {
+        ContainerNode::suspendInsertionCallbacks();
+    }
+
+    ~InsertionCallbackDeferer()
+    {
+        ContainerNode::resumeInsertionCallbacks();
+    }
+};
+
 class PostAttachCallbackDisabler {
 public:
     PostAttachCallbackDisabler(ContainerNode* node)