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

Source/core/css/SiblingTraversalStrategies.h

Index: Source/core/css/SiblingTraversalStrategies.h
diff --git a/Source/core/css/SiblingTraversalStrategies.h b/Source/core/css/SiblingTraversalStrategies.h
index 660a6c5edd3201bb12fbc303dbca15da6c5113de..f4e185b2ef32dfb577c58338a8eac59959ec16a4 100644
--- a/Source/core/css/SiblingTraversalStrategies.h
+++ b/Source/core/css/SiblingTraversalStrategies.h
@@ -79,14 +79,11 @@ inline bool DOMSiblingTraversalStrategy::isLastOfType(Element* element, const Qu
 inline int DOMSiblingTraversalStrategy::countElementsBefore(Element* element) const
 {
     int count = 0;
-    for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
-        unsigned index = sibling->childIndex();
-        if (index) {
-            count += index;
-            break;
-        }
-        count++;
-    }
+    // We can't use the same early return as is present in countElementsAfter due
+    // to the order we resolve style; if a new element is inserted into the middle,
+    // we'd end up using a stale cached childIndex.
+    for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling())
+        ++count;

[esprehn, 2013/06/05 00:12:26]

Lets watch the perf bots for this one.

 
     return count;
 }
@@ -105,8 +102,16 @@ inline int DOMSiblingTraversalStrategy::countElementsOfTypeBefore(Element* eleme
 inline int DOMSiblingTraversalStrategy::countElementsAfter(Element* element) const
 {
     int count = 0;
-    for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling())
+    // We can use an early return here because we resolve style from lastChild to
+    // firstChild, so we're guaranteed to not have stale cached childIndices.
+    for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
+        unsigned index = sibling->childIndex();
+        if (index) {
+            count += index;
+            break;
+        }
         ++count;
+    }
 
     return count;
 }