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

Source/core/css/resolver/StyleResolver.h

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 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.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 130 matching lines @@
     StyleResolver(Document*, bool matchAuthorAndUserStyles);
     ~StyleResolver();
 
     // Using these during tree walk will allow style selector to optimize child and descendant selector lookups.
     void pushParentElement(Element*);
     void popParentElement(Element*);
     void pushParentShadowRoot(const ShadowRoot*);
     void popParentShadowRoot(const ShadowRoot*);
 
     PassRefPtr<RenderStyle> styleForElement(Element*, RenderStyle* parentStyle = 0, StyleSharingBehavior = AllowStyleSharing,
-        RuleMatchingBehavior = MatchAllRules, RenderRegion* regionForStyling = 0);
+        RuleMatchingBehavior = MatchAllRules, RenderRegion* regionForStyling = 0, int childIndex = 0);
+
+    // childIndex's origin is 1, and avoids unnecessary tree walks to resolve nth/nth-last selectors.
+    PassRefPtr<RenderStyle> styleForElement(Element* element, int childIndex)
+    {
+        return styleForElement(element, 0, AllowStyleSharing, MatchAllRules, 0, childIndex);
+    }
 
     void keyframeStylesForAnimation(Element*, const RenderStyle*, KeyframeList&);
 
     PassRefPtr<RenderStyle> pseudoStyleForElement(Element*, const PseudoStyleRequest&, RenderStyle* parentStyle);
 
     PassRefPtr<RenderStyle> styleForPage(int pageIndex);
     PassRefPtr<RenderStyle> defaultStyleForElement();
     PassRefPtr<RenderStyle> styleForText(Text*);
 
     static PassRefPtr<RenderStyle> styleForDocument(Document*, CSSFontSelector* = 0);
@@ skipping 17 matching lines @@
     DocumentRuleSets& ruleSets() { return m_ruleSets; }
     const DocumentRuleSets& ruleSets() const { return m_ruleSets; }
     SelectorFilter& selectorFilter() { return m_selectorFilter; }
 
     ScopedStyleResolver* ensureScopedStyleResolver(const ContainerNode* scope)
     {
         return m_styleTree.ensureScopedStyleResolver(scope ? scope : document());
     }
 
 private:
-    void initElement(Element*);
+    void initElement(Element*, int childIndex = 0);

[eseidel, 2013/06/04 06:29:35]

This method is so horrible and must die.  StyleResolver should not have
per-element resolve state. :(

[eseidel, 2013/06/04 06:29:35]

Why 0?  isn't that the firstChild?

     RenderStyle* locateSharedStyle();
     bool styleSharingCandidateMatchesRuleSet(RuleSet*);
     Node* locateCousinList(Element* parent, unsigned& visitedNodeCount) const;
     StyledElement* findSiblingForStyleSharing(Node*, unsigned& count) const;
     bool canShareStyleWithElement(StyledElement*) const;
 
     PassRefPtr<RenderStyle> styleForKeyframe(const RenderStyle*, const StyleKeyframe*, KeyframeValue&);
 
 public:
     // These methods will give back the set of rules that matched for a given element (or a pseudo-element).
@@ skipping 275 matching lines @@
         PseudoId ignoreDynamicPseudo = NOPSEUDO;
         if (selectorChecker.match(selectorCheckingContext, ignoreDynamicPseudo, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches)
             return true;
     }
     return false;
 }
 
 } // namespace WebCore
 
 #endif // StyleResolver_h