1 files changed, 147 insertions, 74 deletions

diff --git a/Source/WebCore/css/StyleInvalidationAnalysis.cpp b/Source/WebCore/css/StyleInvalidationAnalysis.cpp
index 48383ed77..b89eac08c 100644
--- a/Source/WebCore/css/StyleInvalidationAnalysis.cpp
+++ b/Source/WebCore/css/StyleInvalidationAnalysis.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012 Apple Inc. All rights reserved.
+ * Copyright (C) 2012, 2014 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -10,10 +10,10 @@
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
- * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
@@ -29,106 +29,179 @@
 #include "CSSSelectorList.h"
 #include "Document.h"
 #include "ElementIterator.h"
+#include "ElementRuleCollector.h"
+#include "HTMLSlotElement.h"
+#include "SelectorFilter.h"
+#include "ShadowRoot.h"
 #include "StyleRuleImport.h"
 #include "StyleSheetContents.h"
-#include "StyledElement.h"
 
 namespace WebCore {
 
-StyleInvalidationAnalysis::StyleInvalidationAnalysis(const Vector<StyleSheetContents*>& sheets)
-    : m_dirtiesAllStyle(false)
+static bool shouldDirtyAllStyle(const Vector<RefPtr<StyleRuleBase>>& rules)
 {
-    for (unsigned i = 0; i < sheets.size() && !m_dirtiesAllStyle; ++i)
-        analyzeStyleSheet(sheets[i]);
+    for (auto& rule : rules) {
+        if (is<StyleRuleMedia>(*rule)) {
+            const auto* childRules = downcast<StyleRuleMedia>(*rule).childRulesWithoutDeferredParsing();
+            if (childRules && shouldDirtyAllStyle(*childRules))
+                return true;
+            continue;
+        }
+        // FIXME: At least font faces don't need full recalc in all cases.
+        if (!is<StyleRule>(*rule))
+            return true;
+    }
+    return false;
 }
 
-static bool determineSelectorScopes(const CSSSelectorList& selectorList, HashSet<AtomicStringImpl*>& idScopes, HashSet<AtomicStringImpl*>& classScopes)
+static bool shouldDirtyAllStyle(const StyleSheetContents& sheet)
 {
-    for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector)) {
-        const CSSSelector* scopeSelector = 0;
-        // This picks the widest scope, not the narrowest, to minimize the number of found scopes.
-        for (const CSSSelector* current = selector; current; current = current->tagHistory()) {
-            // Prefer ids over classes.
-            if (current->m_match == CSSSelector::Id)
-                scopeSelector = current;
-            else if (current->m_match == CSSSelector::Class && (!scopeSelector || scopeSelector->m_match != CSSSelector::Id))
-                scopeSelector = current;
-            CSSSelector::Relation relation = current->relation();
-            if (relation != CSSSelector::Descendant && relation != CSSSelector::Child && relation != CSSSelector::SubSelector)
-                break;
-        }
-        if (!scopeSelector)
-            return false;
-        ASSERT(scopeSelector->m_match == CSSSelector::Class || scopeSelector->m_match == CSSSelector::Id);
-        if (scopeSelector->m_match == CSSSelector::Id)
-            idScopes.add(scopeSelector->value().impl());
-        else
-            classScopes.add(scopeSelector->value().impl());
+    for (auto& import : sheet.importRules()) {
+        if (!import->styleSheet())
+            continue;
+        if (shouldDirtyAllStyle(*import->styleSheet()))
+            return true;
+    }
+    if (shouldDirtyAllStyle(sheet.childRules()))
+        return true;
+    return false;
+}
+
+static bool shouldDirtyAllStyle(const Vector<StyleSheetContents*>& sheets)
+{
+    for (auto& sheet : sheets) {
+        if (shouldDirtyAllStyle(*sheet))
+            return true;
     }
-    return true;
+    return false;
 }
 
-void StyleInvalidationAnalysis::analyzeStyleSheet(StyleSheetContents* styleSheetContents)
+StyleInvalidationAnalysis::StyleInvalidationAnalysis(const Vector<StyleSheetContents*>& sheets, const MediaQueryEvaluator& mediaQueryEvaluator)
+    : m_ownedRuleSet(std::make_unique<RuleSet>())
+    , m_ruleSet(*m_ownedRuleSet)
+    , m_dirtiesAllStyle(shouldDirtyAllStyle(sheets))
 {
-    ASSERT(!styleSheetContents->isLoading());
+    if (m_dirtiesAllStyle)
+        return;
 
-    // See if all rules on the sheet are scoped to some specific ids or classes.
-    // Then test if we actually have any of those in the tree at the moment.
-    const Vector<RefPtr<StyleRuleImport>>& importRules = styleSheetContents->importRules();
-    for (unsigned i = 0; i < importRules.size(); ++i) {
-        if (!importRules[i]->styleSheet())
-            continue;
-        analyzeStyleSheet(importRules[i]->styleSheet());
-        if (m_dirtiesAllStyle)
-            return;
+    m_ownedRuleSet->disableAutoShrinkToFit();
+    for (auto& sheet : sheets)
+        m_ownedRuleSet->addRulesFromSheet(*sheet, mediaQueryEvaluator);
+
+    m_hasShadowPseudoElementRulesInAuthorSheet = m_ruleSet.hasShadowPseudoElementRules();
+}
+
+StyleInvalidationAnalysis::StyleInvalidationAnalysis(const RuleSet& ruleSet)
+    : m_ruleSet(ruleSet)
+    , m_hasShadowPseudoElementRulesInAuthorSheet(ruleSet.hasShadowPseudoElementRules())
+{
+}
+
+StyleInvalidationAnalysis::CheckDescendants StyleInvalidationAnalysis::invalidateIfNeeded(Element& element, const SelectorFilter* filter)
+{
+    if (m_hasShadowPseudoElementRulesInAuthorSheet) {
+        // FIXME: This could do actual rule matching too.
+        if (element.shadowRoot())
+            element.invalidateStyleForSubtree();
     }
-    const Vector<RefPtr<StyleRuleBase>>& rules = styleSheetContents->childRules();
-    for (unsigned i = 0; i < rules.size(); i++) {
-        StyleRuleBase* rule = rules[i].get();
-        if (!rule->isStyleRule()) {
-            // FIXME: Media rules and maybe some others could be allowed.
-            m_dirtiesAllStyle = true;
-            return;
-        }
-        StyleRule* styleRule = static_cast<StyleRule*>(rule);
-        if (!determineSelectorScopes(styleRule->selectorList(), m_idScopes, m_classScopes)) {
-            m_dirtiesAllStyle = true;
-            return;
+
+    bool shouldCheckForSlots = !m_ruleSet.slottedPseudoElementRules().isEmpty() && !m_didInvalidateHostChildren;
+    if (shouldCheckForSlots && is<HTMLSlotElement>(element)) {
+        auto* containingShadowRoot = element.containingShadowRoot();
+        if (containingShadowRoot && containingShadowRoot->host()) {
+            for (auto& possiblySlotted : childrenOfType<Element>(*containingShadowRoot->host()))
+                possiblySlotted.invalidateStyle();
         }
+        // No need to do this again.
+        m_didInvalidateHostChildren = true;
     }
+
+    switch (element.styleValidity()) {
+    case Style::Validity::Valid: {
+        ElementRuleCollector ruleCollector(element, m_ruleSet, filter);
+        ruleCollector.setMode(SelectorChecker::Mode::CollectingRulesIgnoringVirtualPseudoElements);
+        ruleCollector.matchAuthorRules(false);
+
+        if (ruleCollector.hasMatchedRules())
+            element.invalidateStyle();
+        return CheckDescendants::Yes;
+    }
+    case Style::Validity::ElementInvalid:
+        return CheckDescendants::Yes;
+    case Style::Validity::SubtreeInvalid:
+    case Style::Validity::SubtreeAndRenderersInvalid:
+        if (shouldCheckForSlots)
+            return CheckDescendants::Yes;
+        return CheckDescendants::No;
+    }
+    ASSERT_NOT_REACHED();
+    return CheckDescendants::Yes;
 }
 
-static bool elementMatchesSelectorScopes(const Element& element, const HashSet<AtomicStringImpl*>& idScopes, const HashSet<AtomicStringImpl*>& classScopes)
+void StyleInvalidationAnalysis::invalidateStyleForTree(Element& root, SelectorFilter* filter)
 {
-    if (!idScopes.isEmpty() && element.hasID() && idScopes.contains(element.idForStyleResolution().impl()))
-        return true;
-    if (classScopes.isEmpty() || !element.hasClass())
-        return false;
-    const SpaceSplitString& classNames = element.classNames();
-    for (unsigned i = 0; i < classNames.size(); ++i) {
-        if (classScopes.contains(classNames[i].impl()))
-            return true;
+    if (invalidateIfNeeded(root, filter) == CheckDescendants::No)
+        return;
+
+    Vector<Element*, 20> parentStack;
+    Element* previousElement = &root;
+    auto descendants = descendantsOfType<Element>(root);
+    for (auto it = descendants.begin(), end = descendants.end(); it != end;) {
+        auto& descendant = *it;
+        auto* parent = descendant.parentElement();
+        if (parentStack.isEmpty() || parentStack.last() != parent) {
+            if (parent == previousElement) {
+                parentStack.append(parent);
+                if (filter)
+                    filter->pushParent(parent);
+            } else {
+                while (parentStack.last() != parent) {
+                    parentStack.removeLast();
+                    if (filter)
+                        filter->popParent();
+                }
+            }
+        }
+        previousElement = &descendant;
+
+        if (invalidateIfNeeded(descendant, filter) == CheckDescendants::Yes)
+            it.traverseNext();
+        else
+            it.traverseNextSkippingChildren();
     }
-    return false;
 }
 
 void StyleInvalidationAnalysis::invalidateStyle(Document& document)
 {
     ASSERT(!m_dirtiesAllStyle);
-    if (m_idScopes.isEmpty() && m_classScopes.isEmpty())
+
+    Element* documentElement = document.documentElement();
+    if (!documentElement)
         return;
 
-    auto it = descendantsOfType<Element>(document).begin();
-    auto end = descendantsOfType<Element>(document).end();
-    while (it != end) {
-        if (elementMatchesSelectorScopes(*it, m_idScopes, m_classScopes)) {
-            it->setNeedsStyleRecalc();
-            // The whole subtree is now invalidated, we can skip to the next sibling.
-            it.traverseNextSkippingChildren();
-            continue;
-        }
-        ++it;
+    SelectorFilter filter;
+    invalidateStyleForTree(*documentElement, &filter);
+}
+
+void StyleInvalidationAnalysis::invalidateStyle(ShadowRoot& shadowRoot)
+{
+    ASSERT(!m_dirtiesAllStyle);
+
+    if (!m_ruleSet.hostPseudoClassRules().isEmpty() && shadowRoot.host())
+        shadowRoot.host()->invalidateStyle();
+
+    for (auto& child : childrenOfType<Element>(shadowRoot)) {
+        SelectorFilter filter;
+        invalidateStyleForTree(child, &filter);
     }
 }
 
+void StyleInvalidationAnalysis::invalidateStyle(Element& element)
+{
+    ASSERT(!m_dirtiesAllStyle);
+
+    // Don't use SelectorFilter as the rule sets here tend to be small and the filter would have setup cost deep in the tree.
+    invalidateStyleForTree(element, nullptr);
+}
+
 }