Revert r174436 (Reduce the cost of the n^2 loop in collectTreeBoundaryCrossingRules)

Source/core/css/TreeBoundaryCrossingRules.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 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 14 matching lines @@
  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  * Boston, MA 02110-1301, USA.
  */
 
 #include "config.h"
 #include "core/css/TreeBoundaryCrossingRules.h"
 
 #include "core/css/ElementRuleCollector.h"
 #include "core/css/RuleFeature.h"
 #include "core/dom/StyleEngine.h"
-#include "core/dom/shadow/InsertionPoint.h"
 #include "core/dom/shadow/ShadowRoot.h"
 
 namespace WebCore {
 
 static void addRules(RuleSet* ruleSet, const WillBeHeapVector<MinimalRuleData>& rules)
 {
     for (unsigned i = 0; i < rules.size(); ++i) {
         const MinimalRuleData& info = rules[i];
         ruleSet->addRule(info.m_rule, info.m_selectorIndex, info.m_flags);
     }
@@ skipping 21 matching lines @@
     if (m_treeBoundaryCrossingRuleSetMap.isEmpty())
         return;
 
     RuleRange ruleRange = collector.matchedResult().ranges.authorRuleRange();
 
     // When comparing rules declared in outer treescopes, outer's rules win.
     CascadeOrder outerCascadeOrder = size() + size();
     // When comparing rules declared in inner treescopes, inner's rules win.
     CascadeOrder innerCascadeOrder = size();
 
-    // FIXME: This is n^2 across the number of scoping nodes in the entire document! We need to walk the
-    // ancestors of |element| instead.
     for (DocumentOrderedList::iterator it = m_scopingNodes.begin(); it != m_scopingNodes.end(); ++it) {
         const ContainerNode* scopingNode = toContainerNode(*it);
         CSSStyleSheetRuleSubSet* ruleSubSet = m_treeBoundaryCrossingRuleSetMap.get(scopingNode);
         unsigned boundaryBehavior = SelectorChecker::ScopeContainsLastMatchedElement;
         bool isInnerTreeScope = element->treeScope().isInclusiveAncestorOf(scopingNode->treeScope());
 
         // If a given scoping node is a shadow root,
         // we should use ScopeIsShadowHost.
         if (scopingNode && scopingNode->isShadowRoot()) {
             boundaryBehavior |= SelectorChecker::ScopeIsShadowHost;
             scopingNode = toShadowRoot(scopingNode)->host();
         }
 
-        // FIXME: This is a terrible hack to avoid doing most of the work in this n^2 loop.
-        // Instead we should just fix the loop to collect the proper scopes up the tree instead
-        // of iterating all possible scopes.
-        const InsertionPoint* insertionPoint = resolveReprojection(element);
-        if ((insertionPoint && !scopingNode->containsIncludingShadowDOM(insertionPoint))
-            || (!insertionPoint && !scopingNode->containsIncludingShadowDOM(element))) {
-            ++innerCascadeOrder;
-            --outerCascadeOrder;
-            continue;
-        }
-
         CascadeOrder cascadeOrder = isInnerTreeScope ? innerCascadeOrder : outerCascadeOrder;
         for (CSSStyleSheetRuleSubSet::iterator it = ruleSubSet->begin(); it != ruleSubSet->end(); ++it) {
             CSSStyleSheet* parentStyleSheet = it->first;
             RuleSet* ruleSet = it->second.get();
             collector.collectMatchingRules(MatchRequest(ruleSet, includeEmptyRules, scopingNode, parentStyleSheet), ruleRange, static_cast<SelectorChecker::BehaviorAtBoundary>(boundaryBehavior), ignoreCascadeScope, cascadeOrder);
         }
-
         ++innerCascadeOrder;
         --outerCascadeOrder;
     }
 }
 
 void TreeBoundaryCrossingRules::reset(const ContainerNode* scopingNode)
 {
     m_treeBoundaryCrossingRuleSetMap.remove(scopingNode);
     m_scopingNodes.remove(scopingNode);
 }
 
 void TreeBoundaryCrossingRules::collectFeaturesFromRuleSubSet(CSSStyleSheetRuleSubSet* ruleSubSet, RuleFeatureSet& features)
 {
     for (CSSStyleSheetRuleSubSet::iterator it = ruleSubSet->begin(); it != ruleSubSet->end(); ++it)
         features.add(it->second->features());
 }
 
 void TreeBoundaryCrossingRules::collectFeaturesTo(RuleFeatureSet& features)
 {
     for (TreeBoundaryCrossingRuleSetMap::iterator::Values it = m_treeBoundaryCrossingRuleSetMap.values().begin(); it != m_treeBoundaryCrossingRuleSetMap.values().end(); ++it)
         collectFeaturesFromRuleSubSet(it->get(), features);
 }
 
 } // namespace WebCore