Crash under WebCore::invalidateStyleRecursively
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 20 May 2015 05:28:02 +0000 (05:28 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 20 May 2015 05:28:02 +0000 (05:28 +0000)
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@184615 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/css/StyleInvalidationAnalysis.cpp

index 2a56522..0647939 100644 (file)
@@ -1,3 +1,23 @@
+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>
 
         Move AtomicStringImpl table related operations from AtomicString to AtomicStringImpl
index 6d51b0f..7a91c66 100644 (file)
@@ -88,26 +88,64 @@ StyleInvalidationAnalysis::StyleInvalidationAnalysis(const Vector<StyleSheetCont
         m_dirtiesAllStyle = true;
 }
 
-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);
         ruleCollector.matchAuthorRules(false);
 
         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;
+}
 
-    auto children = childrenOfType<Element>(element);
-    if (!children.first())
+static void invalidateStyleForTree(Element& root, SelectorFilter& filter, const DocumentRuleSets& ruleSets)
+{
+    if (invalidateIfNeeded(root, filter, ruleSets) == CheckDescendants::No)
         return;
-    filter.pushParent(&element);
-    for (auto& child : children)
-        invalidateStyleRecursively(child, filter, ruleSets);
-    filter.popParent();
+
+    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();
+    }
+
+    while (!parentStack.isEmpty()) {
+        parentStack.removeLast();
+        filter.popParent();
+    }
 }
 
 void StyleInvalidationAnalysis::invalidateStyle(Document& document)
@@ -122,7 +160,7 @@ void StyleInvalidationAnalysis::invalidateStyle(Document& document)
 
     SelectorFilter filter;
     filter.setupParentStack(documentElement);
-    invalidateStyleRecursively(*documentElement, filter, m_ruleSets);
+    invalidateStyleForTree(*documentElement, filter, m_ruleSets);
 }
 
 }