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

Source/core/css/SiblingTraversalStrategies.h

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
@@ skipping 60 matching lines @@
     for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
         if (sibling->hasTagName(type))
             return false;
     }
     return true;
 }
 
 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;
 
     return count;
 }
 
 inline int DOMSiblingTraversalStrategy::countElementsOfTypeBefore(Element* element, const QualifiedName& type) const
 {
     int count = 0;
     for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
         if (sibling->hasTagName(type))
             ++count;
     }
 
     return count;
 }
 
 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;
 }
 
 inline int DOMSiblingTraversalStrategy::countElementsOfTypeAfter(Element* element, const QualifiedName& type) const
 {
     int count = 0;
     for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
         if (sibling->hasTagName(type))
             ++count;
@@ skipping 144 matching lines @@
         if (siblings[i] && siblings[i]->isElementNode() && siblings[i]->hasTagName(type))
             return ++count;
     }
 
     return count;
 }
 
 }
 
 #endif