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

Source/core/css/resolver/StyleResolver.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 502 matching lines @@
     if (parent->inlineStyle())
         return 0;
     if (parent->isSVGElement() && toSVGElement(parent)->animatedSMILStyleProperties())
         return 0;
     if (parent->hasID() && m_features.idsInRules.contains(parent->idForStyleResolution().impl()))
         return 0;
 
     RenderStyle* parentStyle = parent->renderStyle();
     unsigned subcount = 0;
     Node* thisCousin = parent;
-    Node* currentNode = parent->previousSibling();
+    Node* currentNode = parent->nextSibling();
 
     // Reserve the tries for this level. This effectively makes sure that the algorithm
     // will never go deeper than cStyleSearchLevelThreshold levels into recursion.
     visitedNodeCount += cStyleSearchThreshold;
     while (thisCousin) {
         while (currentNode) {
             ++subcount;
             if (!currentNode->hasScopedHTMLStyleChild() && currentNode->renderStyle() == parentStyle && currentNode->lastChild()
                 && currentNode->isElementNode() && !parentElementPreventsSharing(toElement(currentNode))
                 && !toElement(currentNode)->shadow()
                 ) {
                 // Adjust for unused reserved tries.
                 visitedNodeCount -= cStyleSearchThreshold - subcount;
                 return currentNode->lastChild();
             }
             if (subcount >= cStyleSearchThreshold)
                 return 0;
-            currentNode = currentNode->previousSibling();
+            currentNode = currentNode->nextSibling();
         }
         currentNode = locateCousinList(thisCousin->parentElement(), visitedNodeCount);
         thisCousin = currentNode;
     }
 
     return 0;
 }
 
 bool StyleResolver::styleSharingCandidateMatchesRuleSet(RuleSet* ruleSet)
 {
@@ skipping 178 matching lines @@
     if (FullscreenController* fullscreen = FullscreenController::fromIfExists(state.document())) {
         if (element == fullscreen->webkitCurrentFullScreenElement() || state.element() == fullscreen->webkitCurrentFullScreenElement())
             return false;
     }
 
     return true;
 }
 
 inline Element* StyleResolver::findSiblingForStyleSharing(Node* node, unsigned& count) const
 {
-    for (; node; node = node->previousSibling()) {
+    for (; node; node = node->nextSibling()) {
         if (!node->isStyledElement())
             continue;
         if (canShareStyleWithElement(toElement(node)))
             break;
         if (count++ == cStyleSearchThreshold)
             return 0;
     }
     return toElement(node);
 }
 
@@ skipping 33 matching lines @@
     // When a dialog is first shown, its style is mutated to center it in the
     // viewport. So the styles can't be shared since the viewport position and
     // size may be different each time a dialog is opened.
     if (state.element()->hasTagName(dialogTag))
         return 0;
 
     // Cache whether state.element is affected by any known class selectors.
     // FIXME: This shouldn't be a member variable. The style sharing code could be factored out of StyleResolver.
     state.setElementAffectedByClassRules(state.element() && state.element()->hasClass() && classNamesAffectedByRules(state.element()->classNames()));
 
-    // Check previous siblings and their cousins.
+    // Check next siblings and their cousins.
     unsigned count = 0;
     unsigned visitedNodeCount = 0;
     Element* shareElement = 0;
-    Node* cousinList = state.styledElement()->previousSibling();
+    Node* cousinList = state.styledElement()->nextSibling();
     while (cousinList) {
         shareElement = findSiblingForStyleSharing(cousinList, count);
         if (shareElement)
             break;
         cousinList = locateCousinList(cousinList->parentElement(), visitedNodeCount);
     }
 
     // If we have exhausted all our budget or our cousins.
     if (!shareElement)
         return 0;
@@ skipping 181 matching lines @@
 }
 
 static inline bool isAtShadowBoundary(const Element* element)
 {
     if (!element)
         return false;
     ContainerNode* parentNode = element->parentNode();
     return parentNode && parentNode->isShadowRoot();
 }
 
-PassRefPtr<RenderStyle> StyleResolver::styleForElement(Element* element, RenderStyle* defaultParent,
-    StyleSharingBehavior sharingBehavior, RuleMatchingBehavior matchingBehavior, RenderRegion* regionForStyling)
+PassRefPtr<RenderStyle> StyleResolver::styleForElement(Element* element, RenderStyle* defaultParent, StyleSharingBehavior sharingBehavior,
+    RuleMatchingBehavior matchingBehavior, RenderRegion* regionForStyling, int childIndex)
 {
     // Once an element has a renderer, we don't try to destroy it, since otherwise the renderer
     // will vanish if a style recalc happens during loading.
     if (sharingBehavior == AllowStyleSharing && !element->document()->haveStylesheetsLoaded() && !element->renderer()) {
         if (!s_styleNotYetAvailable) {
             s_styleNotYetAvailable = RenderStyle::create().leakRef();
             s_styleNotYetAvailable->setDisplay(NONE);
             s_styleNotYetAvailable->font().update(m_fontSelector);
         }
         element->document()->setHasNodesWithPlaceholderStyle();
         return s_styleNotYetAvailable;
     }
 
     StyleResolverState& state = m_state;
-    state.initForStyleResolve(document(), element, defaultParent, regionForStyling);
+    state.initForStyleResolve(document(), element, childIndex, defaultParent, regionForStyling);
     if (sharingBehavior == AllowStyleSharing && !state.distributedToInsertionPoint()) {
         RenderStyle* sharedStyle = locateSharedStyle();
         if (sharedStyle) {
             state.clear();
             return sharedStyle;
         }
     }
 
     if (state.parentStyle()) {
         state.setStyle(RenderStyle::create());
@@ skipping 170 matching lines @@
 }
 
 PassRefPtr<RenderStyle> StyleResolver::pseudoStyleForElement(Element* e, const PseudoStyleRequest& pseudoStyleRequest, RenderStyle* parentStyle)
 {
     ASSERT(parentStyle);
     if (!e)
         return 0;
 
     StyleResolverState& state = m_state;
 
-    state.initForStyleResolve(document(), e, parentStyle);
+    state.initForStyleResolve(document(), e, 0, parentStyle);
 
     if (pseudoStyleRequest.allowsInheritance(state.parentStyle())) {
         state.setStyle(RenderStyle::create());
         state.style()->inheritFrom(state.parentStyle());
     } else {
         state.setStyle(defaultStyleForElement());
         state.setParentStyle(RenderStyle::clone(state.style()));
     }
 
     // Since we don't use pseudo-elements in any of our quirk/print user agent rules, don't waste time walking
@@ skipping 479 matching lines @@
 PassRefPtr<CSSRuleList> StyleResolver::styleRulesForElement(Element* e, unsigned rulesToInclude)
 {
     return pseudoStyleRulesForElement(e, NOPSEUDO, rulesToInclude);
 }
 
 PassRefPtr<CSSRuleList> StyleResolver::pseudoStyleRulesForElement(Element* e, PseudoId pseudoId, unsigned rulesToInclude)
 {
     if (!e || !e->document()->haveStylesheetsLoaded())
         return 0;
 
-    m_state.initForStyleResolve(document(), e, 0);
+    m_state.initForStyleResolve(document(), e);
 
     ElementRuleCollector collector(this, m_state);
     collector.setMode(SelectorChecker::CollectingRules);
     collector.setPseudoStyleRequest(PseudoStyleRequest(pseudoId));
 
     if (rulesToInclude & UAAndUserCSSRules) {
         // First we match rules from the user agent sheet.
         matchUARules(collector);
 
         // Now we check user sheet rules.
@@ skipping 326 matching lines @@
 
     if (cachedMatchedProperties || !cacheHash)
         return;
     if (!MatchedPropertiesCache::isCacheable(state.element(), state.style(), state.parentStyle()))
         return;
     m_matchedPropertiesCache.add(state.style(), state.parentStyle(), cacheHash, matchResult);
 }
 
 void StyleResolver::applyPropertyToStyle(CSSPropertyID id, CSSValue* value, RenderStyle* style)
 {
-    m_state.initForStyleResolve(document(), 0, style);
+    m_state.initForStyleResolve(document(), 0, 0, style);
     m_state.setStyle(style);
     applyPropertyToCurrentStyle(id, value);
 }
 
 void StyleResolver::applyPropertyToCurrentStyle(CSSPropertyID id, CSSValue* value)
 {
     if (value)
         applyProperty(id, value);
 }
 
@@ skipping 330 matching lines @@
 void CachedMatchedProperties::reportMemoryUsage(MemoryObjectInfo* memoryObjectInfo) const
 {
     MemoryClassInfo info(memoryObjectInfo, this, WebCoreMemoryTypes::CSS);
     info.addMember(matchedProperties, "matchedProperties");
     info.addMember(ranges, "ranges");
     info.addMember(renderStyle, "renderStyle");
     info.addMember(parentRenderStyle, "parentRenderStyle");
 }
 
 } // namespace WebCore