Changeset 78322 in webkit

Timestamp:

Feb 11, 2011 12:57:40 AM (13 years ago)

Author:

Antti Koivisto

Message:

Enable ancestor identifier filtering for tree building
​https://bugs.webkit.org/show_bug.cgi?id=54241

Reviewed by Dave Hyatt.

Call CSSStyleSelector::push/popParent() during tree building too, fix up the parent
element stack as needed.

This roughly halves the remaining time in style matching over a typical page load.

• css/CSSStyleSelector.cpp:

(WebCore::CSSStyleSelector::pushParentStackFrame):
(WebCore::CSSStyleSelector::popParentStackFrame):
(WebCore::CSSStyleSelector::pushParent):
(WebCore::CSSStyleSelector::popParent):

• css/CSSStyleSelector.h:

(WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame):

• dom/Document.h:

(WebCore::Document::styleSelectorIfExists):

• dom/Element.cpp:

(WebCore::Element::beginParsingChildren):
(WebCore::Element::finishParsingChildren):

• dom/Element.h:

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• css/CSSStyleSelector.cpp (modified) (3 diffs)
• css/CSSStyleSelector.h (modified) (2 diffs)
• dom/Document.h (modified) (1 diff)
• dom/Element.cpp (modified) (2 diffs)
• dom/Element.h (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2011-02-10  Antti Koivisto  <antti@apple.com>
+
+        Reviewed by Dave Hyatt.
+
+        Enable ancestor identifier filtering for tree building
+        https://bugs.webkit.org/show_bug.cgi?id=54241
+        
+        Call CSSStyleSelector::push/popParent() during tree building too, fix up the parent
+        element stack as needed.
+        
+        This roughly halves the remaining time in style matching over a typical page load.
+
+        * css/CSSStyleSelector.cpp:
+        (WebCore::CSSStyleSelector::pushParentStackFrame):
+        (WebCore::CSSStyleSelector::popParentStackFrame):
+        (WebCore::CSSStyleSelector::pushParent):
+        (WebCore::CSSStyleSelector::popParent):
+        * css/CSSStyleSelector.h:
+        (WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame):
+        * dom/Document.h:
+        (WebCore::Document::styleSelectorIfExists):
+        * dom/Element.cpp:
+        (WebCore::Element::beginParsingChildren):
+        (WebCore::Element::finishParsingChildren):
+        * dom/Element.h:
+
 2011-02-10  Adam Barth  <abarth@webkit.org>
 

trunk/Source/WebCore/css/CSSStyleSelector.cpp

@@ -670 +670 @@
 }
 
-void CSSStyleSelector::pushParent(Element* parent)
-{
-    // If we are not invoked consistently for each parent, just pause maintaining the stack.
-    // There are all kinds of wacky special cases where the style recalc may temporarily branch to some random elements.
-    // FIXME: Perhaps we should fix up the stack instead? There is some danger of getting into O(n^2) situations doing that.
-    if (m_parentStack.isEmpty()) {
-        ASSERT(!m_ancestorIdentifierFilter);
-        // We must start from the root.
-        if (parent->parentElement())
-            return;
-        m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
-    } else {
-        ASSERT(m_ancestorIdentifierFilter);
-        if (m_parentStack.last().element != parent->parentElement())
-            return;
-    }
-
+void CSSStyleSelector::pushParentStackFrame(Element* parent)
+{
+    ASSERT(m_ancestorIdentifierFilter);
+    ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentElement());
+    ASSERT(!m_parentStack.isEmpty() || !parent->parentElement());
     m_parentStack.append(ParentStackFrame(parent));
     ParentStackFrame& parentFrame = m_parentStack.last();
@@ -697 +685 @@
 }
 
-void CSSStyleSelector::popParent(Element* parent)
-{
-    if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
-        return;
+void CSSStyleSelector::popParentStackFrame()
+{
+    ASSERT(!m_parentStack.isEmpty());
     ASSERT(m_ancestorIdentifierFilter);
-
     const ParentStackFrame& parentFrame = m_parentStack.last();
     size_t count = parentFrame.identifierHashes.size();
@@ -712 +698 @@
         m_ancestorIdentifierFilter.clear();
     }
+}
+
+void CSSStyleSelector::pushParent(Element* parent)
+{
+    if (m_parentStack.isEmpty()) {
+        ASSERT(!m_ancestorIdentifierFilter);
+        m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
+        // If the element is not the root itself, build the stack starting from the root.
+        if (parent->parentElement()) {
+            Vector<Element*, 30> ancestors;
+            for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentElement())
+                ancestors.append(ancestor);
+            int count = ancestors.size();
+            for (int n = count - 1; n >= 0; --n)
+                pushParentStackFrame(ancestors[n]);
+            return;
+        }
+    } else if (!parent->parentElement()) {
+        // We are not always invoked consistently. For example, script execution can cause us to enter
+        // style recalc in the middle of tree building. Reset the stack if we see a new root element.
+        ASSERT(m_ancestorIdentifierFilter);
+        m_ancestorIdentifierFilter->clear();
+        m_parentStack.resize(0);
+    } else {
+        ASSERT(m_ancestorIdentifierFilter);
+        // We may get invoked for some random elements in some wacky cases during style resolve.
+        // Pause maintaining the stack in this case.
+        if (m_parentStack.last().element != parent->parentElement())
+            return;
+    }
+    pushParentStackFrame(parent);
+}
+
+void CSSStyleSelector::popParent(Element* parent)
+{
+    if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
+        return;
+    popParentStackFrame();
 }
 

trunk/Source/WebCore/css/CSSStyleSelector.h

@@ -120 +120 @@
         Node* findSiblingForStyleSharing(Node*, unsigned& count) const;
         bool canShareStyleWithElement(Node*) const;
+        
+        void pushParentStackFrame(Element* parent);
+        void popParentStackFrame();
 
         RenderStyle* style() const { return m_style.get(); }
@@ -211 +214 @@
         
         struct ParentStackFrame {
+            ParentStackFrame() {}
             ParentStackFrame(Element* element) : element(element) {}
             Element* element;

trunk/Source/WebCore/dom/Document.h

@@ -432 +432 @@
     virtual bool isFrameSet() const { return false; }
     
+    CSSStyleSelector* styleSelectorIfExists() const { return m_styleSelector.get(); }
     CSSStyleSelector* styleSelector()
     { 

trunk/Source/WebCore/dom/Element.cpp

@@ -1261 +1261 @@
         checkForSiblingStyleChanges(this, renderStyle(), false, beforeChange, afterChange, childCountDelta);
 }
+    
+void Element::beginParsingChildren()
+{
+    clearIsParsingChildrenFinished();
+    CSSStyleSelector* styleSelector = document()->styleSelectorIfExists();
+    if (styleSelector && attached())
+        styleSelector->pushParent(this);
+}
 
 void Element::finishParsingChildren()
@@ -1267 +1275 @@
     setIsParsingChildrenFinished();
     checkForSiblingStyleChanges(this, renderStyle(), true, lastChild(), 0, 0);
+    if (CSSStyleSelector* styleSelector = document()->styleSelectorIfExists())
+        styleSelector->popParent(this);
 }
 

trunk/Source/WebCore/dom/Element.h

@@ -277 +277 @@
     bool isFinishedParsingChildren() const { return isParsingChildrenFinished(); }
     virtual void finishParsingChildren();
-    virtual void beginParsingChildren() { clearIsParsingChildrenFinished(); }
+    virtual void beginParsingChildren();
 
     // ElementTraversal API