WIP: Move StyleEngine::m_activeTreeScopes to TreeScope::m_childTreeScopesWithActiveStyleSheets

Source/core/dom/TreeScope.cpp

Index: Source/core/dom/TreeScope.cpp
diff --git a/Source/core/dom/TreeScope.cpp b/Source/core/dom/TreeScope.cpp
index 801eafbc6ec8c056517e19f50aa3d1c0749c8d40..339484fbcb05bd9ca8067bfff5294ae7ad005612 100644
--- a/Source/core/dom/TreeScope.cpp
+++ b/Source/core/dom/TreeScope.cpp
@@ -64,6 +64,7 @@ TreeScope::TreeScope(ContainerNode& rootNode, Document& document)
     , m_guardRefCount(0)
 #endif
     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
+    , m_selfOrDescendantsHaveActiveStyleSheets(false)
 {
     ASSERT(rootNode != document);
 #if !ENABLE(OILPAN)
@@ -80,6 +81,7 @@ TreeScope::TreeScope(Document& document)
     , m_guardRefCount(0)
 #endif
     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
+    , m_selfOrDescendantsHaveActiveStyleSheets(false)
 {
     m_rootNode->setTreeScope(this);
 }
@@ -95,6 +97,9 @@ TreeScope::~TreeScope()
         m_selection = nullptr;
     }
 
+    if (m_selfOrDescendantsHaveActiveStyleSheets)
+        clearSelfOrDescendantsHaveActiveStyleSheets();
+
     if (m_parentTreeScope)
         m_parentTreeScope->guardDeref();
 #endif
@@ -137,6 +142,8 @@ void TreeScope::setParentTreeScope(TreeScope& newParentScope)
     // A document node cannot be re-parented.
     ASSERT(!rootNode().isDocumentNode());
 
+    if (m_selfOrDescendantsHaveActiveStyleSheets)
+        clearSelfOrDescendantsHaveActiveStyleSheets();
 #if !ENABLE(OILPAN)
     newParentScope.guardRef();
     if (m_parentTreeScope)
@@ -568,6 +575,188 @@ void TreeScope::setNeedsStyleRecalcForViewportUnits()
     }
 }
 
+TreeScopeStyleSheetCollection* TreeScope::styleSheetCollection()
+{
+    return document().styleEngine().styleSheetCollectionFor(*this);
+}
+
+bool TreeScope::OrderedTreeScopeSet::insert(TreeScope* treeScope)
+{
+    if (m_treeScopes.isEmpty()) {
+        m_treeScopes.append(treeScope);
+        m_hash.add(treeScope);
+        return true;
+    }
+    if (m_hash.contains(treeScope))
+        return false;
+
+    int end = m_treeScopes.size() - 1;
+    int start = 0;
+    int position = 0;
+    unsigned result = 0;
+
+    while (start <= end) {
+        position = (start + end) / 2;
+        result = m_treeScopes[position]->comparePosition(*treeScope);
+
+        if (result & Node::DOCUMENT_POSITION_PRECEDING) {
+            end = position - 1;
+        } else {
+            ASSERT(result & Node::DOCUMENT_POSITION_FOLLOWING);
+            start = position + 1;
+        }
+    }
+
+    if (result & Node::DOCUMENT_POSITION_FOLLOWING) {
+        ++position;
+        ASSERT(static_cast<size_t>(position) == m_treeScopes.size() || (m_treeScopes[position]->comparePosition(*treeScope) & Node::DOCUMENT_POSITION_PRECEDING));
+    }
+    m_treeScopes.insert(position, treeScope);
+    m_hash.add(treeScope);
+
+#if ENABLE(ASSERT)
+    // Check whether m_treeScopes is sorted in document order or not.
+    for (unsigned i = 0; i < m_treeScopes.size() - 1; ++i) {
+        unsigned result = m_treeScopes[i]->comparePosition(*m_treeScopes[i + 1]);
+        ASSERT(result & Node::DOCUMENT_POSITION_FOLLOWING);
+    }
+#endif
+    return true;
+}
+
+bool TreeScope::OrderedTreeScopeSet::remove(TreeScope* treeScope)
+{
+    if (!m_hash.contains(treeScope))
+        return false;
+    size_t position = m_treeScopes.find(treeScope);
+    m_treeScopes.remove(position);
+    m_hash.remove(treeScope);
+    return true;
+}
+
+DEFINE_TRACE(TreeScope::OrderedTreeScopeSet)
+{
+#if ENABLE(OILPAN)
+    visitor->trace(m_treeScopes);
+    visitor->trace(m_hash);
+#endif
+}
+
+TreeScope::TreeScopesWithActiveStyleSheetsTraversal::TreeScopesWithActiveStyleSheetsTraversal(TreeScope& treeScope)
+    : m_current(&treeScope), m_iterator(nullptr), m_end(nullptr)
+{
+    skipIfNoStyleSheetCollection();
+}
+
+TreeScope::TreeScopesWithActiveStyleSheetsTraversal::TreeScopesWithActiveStyleSheetsTraversal(OrderedTreeScopeSet& treeScopes)
+    : m_current(nullptr), m_iterator(treeScopes.begin()), m_end(treeScopes.end())
+{
+    if (m_iterator != m_end)
+        m_current = *m_iterator;
+    skipIfNoStyleSheetCollection();
+}
+
+void TreeScope::TreeScopesWithActiveStyleSheetsTraversal::skipIfNoStyleSheetCollection()
+{
+    while (m_current && !m_current->styleSheetCollection())
+        next();
+}
+
+void TreeScope::TreeScopesWithActiveStyleSheetsTraversal::nextWithStyleSheetCollection()
+{
+    do {
+        next();
+    } while (m_current && !m_current->styleSheetCollection());
+}
+
+void TreeScope::TreeScopesWithActiveStyleSheetsTraversal::next()
+{
+    if (!m_current)
+        return;
+
+    OrderedTreeScopeSet& children = m_current->m_childTreeScopesWithActiveStyleSheets;
+    if (!children.isEmpty()) {
+        if (m_iterator) {
+            ++m_iterator;
+            if (m_iterator != m_end)
+                m_stack.append(std::make_pair(m_iterator, m_end));
+        }
+        m_iterator = children.begin();
+        m_end = children.end();
+        ASSERT(m_iterator != m_end);
+        m_current = *m_iterator;
+        return;
+    }
+
+    if (!m_iterator) {
+        m_current = nullptr;
+        return;
+    }
+
+    ++m_iterator;
+    if (m_iterator != m_end) {
+        m_current = *m_iterator;
+        return;
+    }
+
+    if (m_stack.isEmpty()) {
+        m_current = nullptr;
+        return;
+    }
+
+    m_iterator = m_stack.last().first;
+    m_end = m_stack.last().second;
+    ASSERT(m_iterator != m_end);
+    m_stack.removeLast();
+    m_current = *m_iterator;
+}
+
+DEFINE_TRACE(TreeScope::TreeScopesWithActiveStyleSheetsTraversal)
+{
+#if ENABLE(OILPAN)
+    visitor->trace(m_current);
+    visitor->trace(m_iterator);
+    visitor->trace(m_end);
+    visitor->trace(m_stack);
+#endif
+}
+
+void TreeScope::setSelfOrDescendantsHaveActiveStyleSheets()
+{
+    ASSERT(this != m_document);
+    for (TreeScope* treeScope = this;;) {
+        TreeScope* parent = treeScope->parentTreeScope();
+        if (!parent)
+            break;
+        parent->m_childTreeScopesWithActiveStyleSheets.insert(treeScope);
+        treeScope->m_selfOrDescendantsHaveActiveStyleSheets= true;
+
+        // Make sure to include parents so that we can traverse to this from the root treeScope.
+        treeScope = parent;
+        if (treeScope->m_selfOrDescendantsHaveActiveStyleSheets)
+            break;
+    }
+}
+
+void TreeScope::clearSelfOrDescendantsHaveActiveStyleSheets()
+{
+    ASSERT(this != m_document);
+    ASSERT(parentTreeScope());
+    ASSERT(m_selfOrDescendantsHaveActiveStyleSheets);
+    for (TreeScope* treeScope = this;;) {
+        TreeScope* parent = treeScope->parentTreeScope();
+        if (!parent)
+            break;
+        parent->m_childTreeScopesWithActiveStyleSheets.remove(treeScope);
+        treeScope->m_selfOrDescendantsHaveActiveStyleSheets = false;
+
+        // Remove parents if they were included only to traverse to this.
+        treeScope = parent;
+        if (!treeScope->m_selfOrDescendantsHaveActiveStyleSheets || !treeScope->m_childTreeScopesWithActiveStyleSheets.isEmpty())
+            break;
+    }
+}
+
 DEFINE_TRACE(TreeScope)
 {
     visitor->trace(m_rootNode);
@@ -579,6 +768,7 @@ DEFINE_TRACE(TreeScope)
     visitor->trace(m_imageMapsByName);
     visitor->trace(m_labelsByForAttribute);
     visitor->trace(m_scopedStyleResolver);
+    visitor->trace(m_childTreeScopesWithActiveStyleSheets);
 }
 
 } // namespace blink