Changeset 184615 in webkit

Timestamp:

May 19, 2015 10:28:02 PM (9 years ago)

Author:

Antti Koivisto

Message:

Crash under WebCore::invalidateStyleRecursively
​https://bugs.webkit.org/show_bug.cgi?id=145186
rdar://problem/19736838

Reviewed by Andreas Kling

We have seen crashes where we run out of stack under invalidateStyleRecursively in StyleInvalidationAnalysis
on some devices.

Switch to iterative algorithm.

• css/StyleInvalidationAnalysis.cpp:

(WebCore::StyleInvalidationAnalysis::StyleInvalidationAnalysis):
(WebCore::invalidateIfNeeded):
(WebCore::invalidateStyleForTree):
(WebCore::StyleInvalidationAnalysis::invalidateStyle):
(WebCore::invalidateStyleRecursively): Deleted.

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• css/StyleInvalidationAnalysis.cpp (modified) (3 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2015-05-19  Antti Koivisto  <antti@apple.com>
+
+        Crash under WebCore::invalidateStyleRecursively
+        https://bugs.webkit.org/show_bug.cgi?id=145186
+        rdar://problem/19736838
+
+        Reviewed by Andreas Kling
+
+        We have seen crashes where we run out of stack under invalidateStyleRecursively in StyleInvalidationAnalysis
+        on some devices.
+
+        Switch to iterative algorithm.
+
+        * css/StyleInvalidationAnalysis.cpp:
+        (WebCore::StyleInvalidationAnalysis::StyleInvalidationAnalysis):
+        (WebCore::invalidateIfNeeded):
+        (WebCore::invalidateStyleForTree):
+        (WebCore::StyleInvalidationAnalysis::invalidateStyle):
+        (WebCore::invalidateStyleRecursively): Deleted.
+
 2015-05-19  Yusuke Suzuki  <utatane.tea@gmail.com>
 

trunk/Source/WebCore/css/StyleInvalidationAnalysis.cpp

@@ -89 +89 @@
 }
 
-static void invalidateStyleRecursively(Element& element, SelectorFilter& filter, const DocumentRuleSets& ruleSets)
+enum class CheckDescendants { Yes, No };
+static CheckDescendants invalidateIfNeeded(Element& element, SelectorFilter& filter, const DocumentRuleSets& ruleSets)
 {
-    if (element.styleChangeType() > InlineStyleChange)
-        return;
-    if (element.styleChangeType() == NoStyleChange) {
+    switch (element.styleChangeType()) {
+    case NoStyleChange: {
         ElementRuleCollector ruleCollector(element, nullptr, ruleSets, filter);
         ruleCollector.setMode(SelectorChecker::Mode::CollectingRulesIgnoringVirtualPseudoElements);
@@ -100 +100 @@
         if (ruleCollector.hasMatchedRules())
             element.setNeedsStyleRecalc(InlineStyleChange);
+        return CheckDescendants::Yes;
+    }
+    case InlineStyleChange:
+        return CheckDescendants::Yes;
+    case FullStyleChange:
+    case SyntheticStyleChange:
+    case ReconstructRenderTree:
+        return CheckDescendants::No;
+    }
+    ASSERT_NOT_REACHED();
+    return CheckDescendants::Yes;
+}
+
+static void invalidateStyleForTree(Element& root, SelectorFilter& filter, const DocumentRuleSets& ruleSets)
+{
+    if (invalidateIfNeeded(root, filter, ruleSets) == 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);
+                filter.pushParent(parent);
+            } else {
+                while (parentStack.last() != parent) {
+                    parentStack.removeLast();
+                    filter.popParent();
+                }
+            }
+        }
+        previousElement = &descendant;
+
+        if (invalidateIfNeeded(descendant, filter, ruleSets) == CheckDescendants::Yes)
+            it.traverseNext();
+        else
+            it.traverseNextSkippingChildren();
     }
 
-    auto children = childrenOfType<Element>(element);
-    if (!children.first())
-        return;
-    filter.pushParent(&element);
-    for (auto& child : children)
-        invalidateStyleRecursively(child, filter, ruleSets);
-    filter.popParent();
+    while (!parentStack.isEmpty()) {
+        parentStack.removeLast();
+        filter.popParent();
+    }
 }
 
@@ -123 +161 @@
     SelectorFilter filter;
     filter.setupParentStack(documentElement);
-    invalidateStyleRecursively(*documentElement, filter, m_ruleSets);
+    invalidateStyleForTree(*documentElement, filter, m_ruleSets);
 }