Implement a non-recursive PrePaint treewalk

third_party/WebKit/Source/core/paint/PrePaintTreeWalk.cpp

Index: third_party/WebKit/Source/core/paint/PrePaintTreeWalk.cpp
diff --git a/third_party/WebKit/Source/core/paint/PrePaintTreeWalk.cpp b/third_party/WebKit/Source/core/paint/PrePaintTreeWalk.cpp
index 7adecea88839413b0e1330aa2849047a6175db28..5265863cd33056e9ad38747b541769346b5d8c16 100644
--- a/third_party/WebKit/Source/core/paint/PrePaintTreeWalk.cpp
+++ b/third_party/WebKit/Source/core/paint/PrePaintTreeWalk.cpp
@@ -79,6 +79,40 @@ void PrePaintTreeWalk::walk(FrameView& frameView,
   frameView.clearNeedsPaintPropertyUpdate();
 }
 
+// |PrePaintTreeWalkContext| is large and can cause stack overflows when used
+// in a recursive treewalk (see: https://crbug.com/698653). This function
+// implements an iterative pre-order tree walk of the layout tree where the
+// stack is maintained using heap allocations in a Vector.
+void PrePaintTreeWalk::walk(const LayoutView& view,
+                            const PrePaintTreeWalkContext& parentContext) {
+  Vector<PrePaintTreeWalkContext> stack;

[pdr., 2017/03/08 01:04:59]

This has a bug: when the vector resizes, parent pointers in
PrePaintTreeWalkContext.paintInvalidatorContext are no longer valid. This should
use a linked list instead.

+  stack.push_back(parentContext);
+
+  const LayoutObject* object = &view;
+  while (object) {
+    if (!shouldEndWalkBefore(*object, stack.back())) {
+      stack.push_back(stack.back());
+      walkObject(*object, stack.back());
+      if (const auto* child = object->slowFirstChild()) {
+        object = child;
+        continue;
+      }
+      stack.pop_back();
+    }
+
+    while (object && !object->nextSibling()) {
+      object->getMutableForPainting().clearPaintFlags();
+      stack.pop_back();
+      object = object->parent();
+    }
+
+    if (object) {
+      object->getMutableForPainting().clearPaintFlags();
+      object = object->nextSibling();
+    }
+  }
+}
+
 static void updateAuxiliaryObjectProperties(const LayoutObject& object,
                                             PrePaintTreeWalkContext& context) {
   if (!RuntimeEnabledFeatures::slimmingPaintV2Enabled())
@@ -232,11 +266,11 @@ bool PrePaintTreeWalk::shouldEndWalkBefore(
            .shouldCheckForPaintInvalidationRegardlessOfPaintInvalidationState());
 }
 
-void PrePaintTreeWalk::walk(const LayoutObject& object,
-                            const PrePaintTreeWalkContext& parentContext) {
-  PrePaintTreeWalkContext context(parentContext);
+void PrePaintTreeWalk::walkObject(const LayoutObject& object,
+                                  PrePaintTreeWalkContext& context) {
+  DCHECK(!shouldEndWalkBefore(object, context));
 
-  if (shouldEndWalkBefore(object, parentContext))
+  if (object.isLayoutMultiColumnSpannerPlaceholder())
     return;
 
   // This must happen before updatePropertiesForSelf, because the latter reads
@@ -252,30 +286,20 @@ void PrePaintTreeWalk::walk(const LayoutObject& object,
 
   invalidatePaintLayerOptimizationsIfNeeded(object, context);
 
-  for (const LayoutObject* child = object.slowFirstChild(); child;
-       child = child->nextSibling()) {
-    if (child->isLayoutMultiColumnSpannerPlaceholder()) {
-      child->getMutableForPainting().clearPaintFlags();
-      continue;
-    }
-    walk(*child, context);
-  }
-
   if (object.isLayoutPart()) {
     const LayoutPart& layoutPart = toLayoutPart(object);
     FrameViewBase* frameViewBase = layoutPart.widget();
     if (frameViewBase && frameViewBase->isFrameView()) {
-      context.treeBuilderContext.current.paintOffset +=
+      PrePaintTreeWalkContext frameViewContext(context);
+      frameViewContext.treeBuilderContext.current.paintOffset +=
           layoutPart.replacedContentRect().location() -
           frameViewBase->frameRect().location();
-      context.treeBuilderContext.current.paintOffset =
-          roundedIntPoint(context.treeBuilderContext.current.paintOffset);
-      walk(*toFrameView(frameViewBase), context);
+      frameViewContext.treeBuilderContext.current.paintOffset = roundedIntPoint(
+          frameViewContext.treeBuilderContext.current.paintOffset);
+      walk(*toFrameView(frameViewBase), frameViewContext);
     }
     // TODO(pdr): Investigate RemoteFrameView (crbug.com/579281).
   }
-
-  object.getMutableForPainting().clearPaintFlags();
 }
 
 }  // namespace blink