Add a first pass of a class descendant invalidator, and a containing RuleSetAnalyzer

Source/core/css/analyzer/RuleSetAnalyzer.cpp

Index: Source/core/css/analyzer/RuleSetAnalyzer.cpp
diff --git a/Source/core/css/analyzer/RuleSetAnalyzer.cpp b/Source/core/css/analyzer/RuleSetAnalyzer.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..3b70d134e81fe8cf63c546db6b71ff7da6f67520
--- /dev/null
+++ b/Source/core/css/analyzer/RuleSetAnalyzer.cpp
@@ -0,0 +1,331 @@
+/*
+ * Copyright (C) 2014 Google Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "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 THE COPYRIGHT
+ * OWNER 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 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "core/css/analyzer/RuleSetAnalyzer.h"
+
+#include "core/css/CSSSelector.h"
+#include "core/css/CSSSelectorList.h"
+#include "core/css/RuleFeature.h"
+#include "core/css/RuleSet.h"
+#include "core/css/analyzer/DescendantInvalidationSet.h"
+#include "core/dom/Document.h"
+#include "core/dom/Element.h"
+#include "core/dom/Node.h"
+#include "core/dom/shadow/ElementShadow.h"
+#include "core/dom/shadow/ShadowRoot.h"
+#include "wtf/Forward.h"
+#include "wtf/HashSet.h"
+#include "wtf/text/AtomicString.h"
+#include "wtf/text/StringHash.h"
+
+
+namespace WebCore {
+
+static bool isSkippableComponentForInvalidation(const CSSSelector* selector)
+{
+    if (selector->matchesPseudoElement() || selector->pseudoType() == CSSSelector::PseudoHost)
+        return false;
+    return true;
+}
+
+// This method is somewhat conservative in what it acceptss.
+static bool supportsClassDescendantInvalidation(const CSSSelector* selector)
+{
+    bool foundDescendantRelation = false;
+    bool foundAncestorIdent = false;
+    bool foundIdent = false;
+    for (const CSSSelector* component = selector; component; component = component->tagHistory()) {
+
+        // FIXME: We should allow pseudo elements, but we need to change how they hook
+        // into recalcStyle by moving them to recalcOwnStyle instead of recalcChildStyle.
+
+        // FIXME: next up is adding ids and tags.
+        if (component->m_match == CSSSelector::Class) {
+            if (!foundDescendantRelation)
+                foundIdent = true;
+            else
+                foundAncestorIdent = true;
+        } else if (!isSkippableComponentForInvalidation(component)) {
+            return false;
+        }
+        // FIXME: We can probably support ChildTree and DescendantTree.
+        switch (component->relation()) {
+        case CSSSelector::Descendant:
+        case CSSSelector::Child:
+            foundDescendantRelation = true;
+            // Fall through!
+        case CSSSelector::SubSelector:
+            continue;
+        default:
+            return false;
+        }
+    }
+    return foundDescendantRelation && foundAncestorIdent && foundIdent;
+}
+
+void extractClassIdOrTag(const CSSSelector& selector, HashSet<AtomicString>& classes, AtomicString& id, AtomicString& tagName)
+{
+    if (selector.m_match == CSSSelector::Tag)
+        tagName = selector.tagQName().localName();
+    else if (selector.m_match == CSSSelector::Id)
+        id = selector.value();
+    else if (selector.m_match == CSSSelector::Class)
+        classes.add(selector.value());
+}
+
+RuleSetAnalyzer::RuleSetAnalyzer()
+{
+}
+
+bool RuleSetAnalyzer::updateClassInvalidationSets(const CSSSelector* selector)
+{
+    if (!selector)
+        return false;
+    bool supported = supportsClassDescendantInvalidation(selector);
+    // if (supported)
+    //     printf("desc. analysis supported for selector: %d %s\n", supported, selector->selectorText().ascii().data());
+    if (!supported)
+        return false;
+
+    HashSet<AtomicString> classes;
+    AtomicString id;
+    AtomicString tagName;
+
+    const CSSSelector* lastSelector = selector;
+    for (; lastSelector->relation() == CSSSelector::SubSelector; lastSelector = lastSelector->tagHistory()) {
+        extractClassIdOrTag(*selector, classes, id, tagName);
+    }
+    extractClassIdOrTag(*lastSelector, classes, id, tagName);
+
+    for ( ; selector; selector = selector->tagHistory()) {
+        if (selector->m_match == CSSSelector::Class) {
+            DescendantInvalidationSet* invalidationSet = ensureClassInvalidationSet(selector->value());
+            if (!id.isEmpty())
+                invalidationSet->addId(id);
+            if (!tagName.isEmpty())
+                invalidationSet->addTagName(tagName);
+            for (HashSet<AtomicString>::const_iterator it = classes.begin(); it != classes.end(); ++it) {
+                invalidationSet->addClass(*it);
+            }
+        }
+    }
+    return true;
+}
+
+PassRefPtr<RuleSetAnalyzer> RuleSetAnalyzer::create()
+{
+    return adoptRef(new RuleSetAnalyzer);
+}
+static bool debug = false;
+
+
+void RuleSetAnalyzer::collectFeaturesFromRuleData(RuleFeatureSet& features, const RuleData& ruleData)
+{
+    bool foundSiblingSelector = false;
+    unsigned maxDirectAdjacentSelectors = 0;
+    bool selectorUsesClassInvalidationSet= updateClassInvalidationSets(ruleData.selector());
+
+    HashSet<AtomicString> addedClasses;
+    for (const CSSSelector* selector = ruleData.selector(); selector; selector = selector->tagHistory()) {
+        features.collectFeaturesFromSelector(selector, &addedClasses);
+
+        if (const CSSSelectorList* selectorList = selector->selectorList()) {
+            for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
+                // FIXME: Shouldn't this be checking subSelector->isSiblingSelector()?
+                if (!foundSiblingSelector && selector->isSiblingSelector())
+                    foundSiblingSelector = true;
+                if (subSelector->isDirectAdjacentSelector())
+                    maxDirectAdjacentSelectors++;
+                features.collectFeaturesFromSelector(subSelector, &addedClasses);
+            }
+        } else {
+            if (!foundSiblingSelector && selector->isSiblingSelector())
+                foundSiblingSelector = true;
+            if (selector->isDirectAdjacentSelector())
+                maxDirectAdjacentSelectors++;
+        }
+    }
+    if (!selectorUsesClassInvalidationSet) {
+        for (HashSet<AtomicString>::const_iterator it = addedClasses.begin(); it != addedClasses.end(); ++it) {
+            if (debug) {
+                printf("recalc whole subtree for class=%s selector=%s\n", it->ascii().data(), ruleData.selector()->selectorText().ascii().data());
+            }
+            DescendantInvalidationSet* invalidationSet = ensureClassInvalidationSet(*it);
+            invalidationSet->setWholeSubtreeInvalid();
+        }
+    }
+    // } else {
+    //     printf("desc analysis supported: %s\n", ruleData.selector()->selectorText().ascii().data());
+    // }
+    features.setMaxDirectAdjacentSelectors(maxDirectAdjacentSelectors);
+    if (foundSiblingSelector)
+        features.siblingRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
+    if (ruleData.containsUncommonAttributeSelector())
+        features.uncommonAttributeRules.append(RuleFeature(ruleData.rule(), ruleData.selectorIndex(), ruleData.hasDocumentSecurityOrigin()));
+}
+
+DescendantInvalidationSet* RuleSetAnalyzer::ensureClassInvalidationSet(const AtomicString& className)
+{
+    InvalidationSetMap::AddResult addResult = classInvalidationSets.add(className, 0);
+    if (addResult.isNewEntry)
+        addResult.iterator->value = DescendantInvalidationSet::create();
+    return addResult.iterator->value.get();
+}
+
+void RuleSetAnalyzer::combine(const RuleSetAnalyzer& other)
+{
+    for (InvalidationSetMap::const_iterator it = other.classInvalidationSets.begin(); it != other.classInvalidationSets.end(); ++it) {
+        ensureClassInvalidationSet(it->key)->combine(*it->value);
+    }
+}
+
+RuleSetAnalyzer::InvalidationVec* RuleSetAnalyzer::ensurePendingInvalidationVector(Element* element)
+{
+    PendingInvalidationMap::AddResult addResult = m_pendingInvalidationMap.add(element, 0);
+    if (addResult.isNewEntry)
+        addResult.iterator->value = new InvalidationVec;
+    return addResult.iterator->value;
+}
+
+
+bool RuleSetAnalyzer::scheduleClassInvalidationForElement(const AtomicString& className, Element* element)
+{
+    if (DescendantInvalidationSet* invalidationSet = classInvalidationSets.get(className)) {
+        ensurePendingInvalidationVector(element)->append(invalidationSet);
+        element->setNeedsInvalidation();
+        if (debug)
+            printf("element invalidation recorded for class=%s outerHTML=%s\n", className.ascii().data(), element->outerHTML().ascii().data());
+        return true;
+    }
+    return false;
+}
+
+bool RuleSetAnalyzer::needsInvalidation(const Element* element) const
+{
+    return m_pendingInvalidationMap.get(const_cast<Element*>(element));
+}
+
+void RuleSetAnalyzer::recalcInvalidation(Document* document)
+{
+    if (debug)
+        printf("RuleSetAnalyzer::recalcInvalidation\n");
+    Vector<AtomicString> invalidationClasses;
+    for (Node* child = document->firstChild(); child; child = child->nextSibling()) {
+        if (child->isElementNode() && child->childNeedsInvalidation()) {
+            Element* childElement = toElement(child);
+            recalcInvalidationInternal(childElement, invalidationClasses, false);
+        }
+    }
+    document->clearChildNeedsInvalidation();
+    m_pendingInvalidationMap.clear();
+}
+
+bool RuleSetAnalyzer::recalcInvalidationInternalForShadowRoot(ShadowRoot* root, Vector<AtomicString>& invalidationClasses, bool foundInvalidationSet)
+{
+    bool someElementNeedsStyleRecalc = false;
+    for (Node* child = root->firstChild(); child; child = child->nextSibling()) {
+        if (child->isElementNode()) {
+            Element* childElement = toElement(child);
+            someElementNeedsStyleRecalc = someElementNeedsStyleRecalc || recalcInvalidationInternal(childElement, invalidationClasses, foundInvalidationSet);
+        }
+    }
+    return someElementNeedsStyleRecalc;
+}
+
+bool RuleSetAnalyzer::recalcInvalidationInternal(Element* element, Vector<AtomicString>& invalidationClasses, bool foundInvalidationSet)
+{
+    int oldSize = invalidationClasses.size();
+    if (InvalidationVec* invalidationVec = m_pendingInvalidationMap.get(element)) {
+        foundInvalidationSet = true;
+        if (debug)
+            printf("found an invalidation vec for element with outerHTML=%s\n", element->outerHTML().ascii().data());
+        bool recalcWholeSubtree = false;
+        for (InvalidationVec::const_iterator it = invalidationVec->begin(); it != invalidationVec->end(); ++it) {
+            if ((*it)->wholeSubtreeInvalid()) {
+                recalcWholeSubtree = true;
+                break;
+            } else {
+                (*it)->appendClasses(invalidationClasses);
+            }
+        }
+        if (recalcWholeSubtree) {
+            if (debug)
+                printf("setNeedsStyleRecalc(SubtreeStyleChange): element outerHTML=%s\n", element->outerHTML().ascii().data());
+            element->setNeedsStyleRecalc(SubtreeStyleChange);
+
+            // share code!!
+            invalidationClasses.remove(oldSize, invalidationClasses.size() - oldSize);
+            element->clearChildNeedsInvalidation();
+            return true;
+        }
+    }
+
+    bool thisElementNeedsStyleRecalc = false;
+
+    if (element->hasClass()) {
+        const SpaceSplitString& classNames = element->classNames();
+        if (debug)
+            printf("element class: %s\n", element->getClassAttribute().ascii().data());
+        for (Vector<AtomicString>::const_iterator it = invalidationClasses.begin(); it != invalidationClasses.end(); ++it) {
+            if (debug)
+                printf("checking class for invalidation: %s\n", it->ascii().data());
+            if (classNames.contains(*it)) {
+                thisElementNeedsStyleRecalc = true;
+                break;
+            }
+        }
+    }
+    if (foundInvalidationSet || element->childNeedsInvalidation()) {
+        for (Node* child = element->firstChild(); child; child = child->nextSibling()) {
+            if (child->isElementNode()) {
+                Element* childElement = toElement(child);
+                bool childAddedNeedsRecalc = 
+                    recalcInvalidationInternal(childElement, invalidationClasses, foundInvalidationSet);
+                thisElementNeedsStyleRecalc = thisElementNeedsStyleRecalc || (childAddedNeedsRecalc && foundInvalidationSet);
+            }
+        }
+        for (ShadowRoot* root = element->youngestShadowRoot(); root; root = root->olderShadowRoot()) {
+            thisElementNeedsStyleRecalc = thisElementNeedsStyleRecalc || recalcInvalidationInternalForShadowRoot(root, invalidationClasses, foundInvalidationSet);
+        }
+    }
+
+    if (thisElementNeedsStyleRecalc) {
+        if (debug)
+            printf("setNeedsStyleRecalc(LocalStyleChange): element outerHTML=%s\n", element->outerHTML().ascii().data());
+        element->setNeedsStyleRecalc(LocalStyleChange);
+    }
+
+    invalidationClasses.remove(oldSize, invalidationClasses.size() - oldSize);
+    element->clearChildNeedsInvalidation();
+    return thisElementNeedsStyleRecalc;
+}
+
+} // namespace WebCore