Implement a non-recursive PrePaint treewalk

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

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "core/paint/PrePaintTreeWalk.h"
 
 #include "core/dom/DocumentLifecycle.h"
 #include "core/frame/FrameView.h"
 #include "core/frame/LocalFrame.h"
 #include "core/layout/LayoutMultiColumnSpannerPlaceholder.h"
@@ skipping 61 matching lines @@
 
   if (LayoutView* view = frameView.layoutView()) {
     walk(*view, context);
 #if DCHECK_IS_ON()
     view->assertSubtreeClearedPaintInvalidationFlags();
 #endif
   }
   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())
     return;
 
   if (!object.hasLayer())
     return;
 
   PaintLayer* paintLayer = object.enclosingLayer();
   paintLayer->updateAncestorOverflowLayer(context.ancestorOverflowPaintLayer);
@@ skipping 133 matching lines @@
     const PrePaintTreeWalkContext& context) {
   return (
       !object.needsPaintPropertyUpdate() &&
       !object.descendantNeedsPaintPropertyUpdate() &&
       !context.treeBuilderContext.forceSubtreeUpdate &&
       !context.paintInvalidatorContext.forcedSubtreeInvalidationFlags &&
       !object
            .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
   // some of the state computed here.
   updateAuxiliaryObjectProperties(object, context);
 
   m_propertyTreeBuilder.updatePropertiesForSelf(object,
                                                 context.treeBuilderContext);
   m_paintInvalidator.invalidatePaintIfNeeded(object,
                                              context.paintInvalidatorContext);
   m_propertyTreeBuilder.updatePropertiesForChildren(object,
                                                     context.treeBuilderContext);
 
   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