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

Source/core/dom/ContainerNode.h

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2009, 2010, 2011 Apple Inc. All rights reserved.
  *
  * 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.
@@ skipping 18 matching lines @@
 
 #include <wtf/OwnPtr.h>
 #include <wtf/Vector.h>
 
 namespace WebCore {
 
 class FloatPoint;
 class HTMLCollection;
 
 typedef void (*NodeCallback)(Node*);
+typedef void (*ElementCallback)(Element*);
 
 namespace Private {
     template<class GenericNode, class GenericNodeContainer>
     void addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer*);
 };
 
 class NoEventDispatchAssertion {
 public:
     NoEventDispatchAssertion()
     {
@@ skipping 24 matching lines @@
 #endif
 
 private:
 #ifndef NDEBUG
     static unsigned s_count;
 #endif
 };
 
 class ContainerNode : public Node {
     friend class PostAttachCallbackDisabler;
+    friend class InsertionCallbackDeferer;
 public:
     virtual ~ContainerNode();
 
     Node* firstChild() const { return m_firstChild; }
     Node* lastChild() const { return m_lastChild; }
     bool hasChildNodes() const { return m_firstChild; }
 
     // ParentNode interface API
     PassRefPtr<HTMLCollection> children();
     Element* firstElementChild() const;
@@ skipping 33 matching lines @@
     // Notifies the node that it's list of children have changed (either by adding or removing child nodes), or a child
     // node that is of the type CDATA_SECTION_NODE, TEXT_NODE or COMMENT_NODE has changed its value.
     virtual void childrenChanged(bool createdByParser = false, Node* beforeChange = 0, Node* afterChange = 0, int childCountDelta = 0);
 
     void disconnectDescendantFrames();
 
     virtual bool childShouldCreateRenderer(const NodeRenderingContext&) const { return true; }
 
     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();
 
     template<class GenericNode, class GenericNodeContainer>
     friend void appendChildToContainer(GenericNode* child, GenericNodeContainer*);
 
     template<class GenericNode, class GenericNodeContainer>
     friend void Private::addChildNodesToDeletionQueue(GenericNode*& head, GenericNode*& tail, GenericNodeContainer*);
 
     void removeDetachedChildren();
     void setFirstChild(Node* child) { m_firstChild = child; }
     void setLastChild(Node* child) { m_lastChild = child; }
 
 private:
     void removeBetween(Node* previousChild, Node* nextChild, Node* oldChild);
     void insertBeforeCommon(Node* nextChild, Node* oldChild);
 
     void attachChildren(const AttachContext& = AttachContext());
     void detachChildren(const AttachContext& = AttachContext());
 
     static void dispatchPostAttachCallbacks();
 
     void suspendPostAttachCallbacks();
     void resumePostAttachCallbacks();
 
+    static void dispatchInsertionCallbacks();
+
+    static void suspendInsertionCallbacks();
+    static void resumeInsertionCallbacks();
+
     bool getUpperLeftCorner(FloatPoint&) const;
     bool getLowerRightCorner(FloatPoint&) const;
 
     Node* m_firstChild;
     Node* m_lastChild;
 };
 
 #ifndef NDEBUG
 bool childAttachedAllowedWhenAttachingChildren(ContainerNode*);
 #endif
@@ skipping 89 matching lines @@
     ASSERT(!nodes.size());
     for (Node* child = node->firstChild(); child; child = child->nextSibling())
         nodes.append(child);
 }
 
 class ChildNodesLazySnapshot {
     WTF_MAKE_NONCOPYABLE(ChildNodesLazySnapshot);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     explicit ChildNodesLazySnapshot(Node* parentNode)
-        : m_currentNode(parentNode->firstChild())
+        : m_currentNode(parentNode->lastChild())
         , m_currentIndex(0)
     {
         m_nextSnapshot = latestSnapshot;
         latestSnapshot = this;
     }
 
     ~ChildNodesLazySnapshot()
     {
         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;
         if (m_currentIndex >= nodeVector.size())
             return 0;
         return nodeVector[m_currentIndex++];
     }
 
     void takeSnapshot()
     {
         if (hasSnapshot())
             return;
         m_childNodes = adoptPtr(new Vector<RefPtr<Node> >());
         Node* node = m_currentNode.get();
         while (node) {
             m_childNodes->append(node);
-            node = node->nextSibling();
+            node = node->previousSibling();
         }
     }
 
     ChildNodesLazySnapshot* nextSnapshot() { return m_nextSnapshot; }
     bool hasSnapshot() { return !!m_childNodes.get(); }
 
     static void takeChildNodesLazySnapshot()
     {
         ChildNodesLazySnapshot* snapshot = latestSnapshot;
         while (snapshot && !snapshot->hasSnapshot()) {
             snapshot->takeSnapshot();
             snapshot = snapshot->nextSnapshot();
         }
     }
 
 private:
     static ChildNodesLazySnapshot* latestSnapshot;
 
     RefPtr<Node> m_currentNode;
     unsigned m_currentIndex;
     OwnPtr<Vector<RefPtr<Node> > > m_childNodes; // Lazily instantiated.
     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)
         : m_node(node)
     {
         ASSERT(m_node);
         m_node->suspendPostAttachCallbacks();
     }
 
     ~PostAttachCallbackDisabler()
     {
         m_node->resumePostAttachCallbacks();
     }
 
 private:
     ContainerNode* m_node;
 };
 
 } // namespace WebCore
 
 #endif // ContainerNode_h