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

Source/core/css/SelectorChecker.cpp

 /*
  * 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, 2012, 2013 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 476 matching lines @@
                 }
                 if (!parentElement->isFinishedParsingChildren())
                     return false;
                 return siblingTraversalStrategy.isFirstOfType(element, element->tagQName()) && siblingTraversalStrategy.isLastOfType(element, element->tagQName());
             }
             break;
         case CSSSelector::PseudoNthChild:
             if (!selector->parseNth())
                 break;
             if (Element* parentElement = element->parentElement()) {
-                int count = 1 + siblingTraversalStrategy.countElementsBefore(element);
+                // FIXME: We should always have the index passed in to avoid needing countElementsBefore.
+                int count = context.childIndex ? context.childIndex : 1 + siblingTraversalStrategy.countElementsBefore(element);

[ojan, 2013/05/31 18:05:07]

Not sure where, but that childIndices start at 1 probably deserves a comment
somewhere. :(

                 if (m_mode == ResolvingStyle) {
                     RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
                     element->setChildIndex(count);
                     if (childStyle)
                         childStyle->setUnique();
                     parentElement->setChildrenAffectedByForwardPositionalRules();
                 }
 
                 if (selector->matchNth(count))
                     return true;
@@ skipping 12 matching lines @@
             }
             break;
         case CSSSelector::PseudoNthLastChild:
             if (!selector->parseNth())
                 break;
             if (Element* parentElement = element->parentElement()) {
                 if (m_mode == ResolvingStyle)
                     parentElement->setChildrenAffectedByBackwardPositionalRules();
                 if (!parentElement->isFinishedParsingChildren())
                     return false;
-                int count = 1 + siblingTraversalStrategy.countElementsAfter(element);
+                // FIXME: We should always have the index passed in to avoid needing countElementsAfter.
+                int count = context.childIndex ? context.childIndex : 1 + siblingTraversalStrategy.countElementsAfter(element);
                 if (selector->matchNth(count))
                     return true;
             }
             break;
         case CSSSelector::PseudoNthLastOfType:
             if (!selector->parseNth())
                 break;
             if (Element* parentElement = element->parentElement()) {
                 if (m_mode == ResolvingStyle)
                     parentElement->setChildrenAffectedByBackwardPositionalRules();
@@ skipping 366 matching lines @@
     return element->focused() && isFrameFocused(element);
 }
 
 template
 SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext&, PseudoId&, const DOMSiblingTraversalStrategy&) const;
 
 template
 SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext&, PseudoId&, const ShadowDOMSiblingTraversalStrategy&) const;
 
 }