path: root/chromium/third_party/blink/renderer/core/paint/pre_paint_tree_walk.cc

// 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 "third_party/blink/renderer/core/paint/pre_paint_tree_walk.h"

#include "base/auto_reset.h"
#include "third_party/blink/renderer/core/dom/document_lifecycle.h"
#include "third_party/blink/renderer/core/frame/event_handler_registry.h"
#include "third_party/blink/renderer/core/frame/local_dom_window.h"
#include "third_party/blink/renderer/core/frame/local_frame.h"
#include "third_party/blink/renderer/core/frame/local_frame_view.h"
#include "third_party/blink/renderer/core/frame/settings.h"
#include "third_party/blink/renderer/core/frame/visual_viewport.h"
#include "third_party/blink/renderer/core/layout/layout_embedded_content.h"
#include "third_party/blink/renderer/core/layout/layout_multi_column_spanner_placeholder.h"
#include "third_party/blink/renderer/core/layout/layout_shift_tracker.h"
#include "third_party/blink/renderer/core/layout/layout_view.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_fragment_item.h"
#include "third_party/blink/renderer/core/layout/ng/ng_block_break_token.h"
#include "third_party/blink/renderer/core/layout/ng/ng_fragment_child_iterator.h"
#include "third_party/blink/renderer/core/layout/ng/ng_fragmentation_utils.h"
#include "third_party/blink/renderer/core/layout/ng/ng_physical_box_fragment.h"
#include "third_party/blink/renderer/core/page/chrome_client.h"
#include "third_party/blink/renderer/core/page/page.h"
#include "third_party/blink/renderer/core/paint/compositing/composited_layer_mapping.h"
#include "third_party/blink/renderer/core/paint/compositing/compositing_layer_property_updater.h"
#include "third_party/blink/renderer/core/paint/ng/ng_paint_fragment.h"
#include "third_party/blink/renderer/core/paint/paint_layer.h"
#include "third_party/blink/renderer/core/paint/paint_property_tree_printer.h"
#include "third_party/blink/renderer/platform/graphics/paint/geometry_mapper.h"
#include "third_party/blink/renderer/platform/runtime_enabled_features.h"

namespace blink {

namespace {

// Locate or/and set up the current FragmentData object. This may involve
// creating it, or resetting an existing one. If |allow_reset| is set, we're
// allowed to clear old FragmentData objects.
NGPrePaintInfo SetupFragmentData(const NGFragmentChildIterator& iterator,
                                 bool allow_reset) {
  // TODO(crbug.com/1043787): What's here is mostly gross, and we need to come
  // up with something better. The way FragmentData works (and is stored)
  // vs. the way NGPhysicalFragment works is less than ideal.
  //
  // There's essentially a 1:1 correspondence between a block-level
  // NGPhysicalBoxFragment and FragmentData, but there's no direct link between
  // them, so we have to do some work. In the future we might want to make
  // FragmentData part of NGPhysicalBoxFragment objects, to simplify this, and
  // to get rid of O(n^2) performance complexity (where n is the number of
  // fragments generated by a node). Note that this performance complexity also
  // exists in the legacy engine.
  //
  // For inline-level nodes, it gets a bit more complicated. There's one
  // FragmentData object per fragmentainer said node occurs in. The offset and
  // invalidation rectangle in each FragmentData will be a union of all the
  // fragments generated by the node (one per line box, typically) in that
  // fragmentainer. This also matches how we do it in legacy layout. It's
  // considered too expensive to have one FragmentData object per line for each
  // text node or non-atomic inline.
  DCHECK(iterator->GetLayoutObject());
  const LayoutObject& object = *iterator->GetLayoutObject();
  FragmentData* fragment_data = &object.GetMutableForPainting().FirstFragment();
  const auto* incoming_break_token = iterator->BlockBreakToken();
  const NGPhysicalBoxFragment* box_fragment = iterator->BoxFragment();

  // The need for paint properties is the same across all fragments, so if the
  // first FragmentData needs it, so do all the others.
  bool needs_paint_properties = fragment_data->PaintProperties();

  if (const NGFragmentItem* fragment_item = iterator->FragmentItem()) {
    // We're in an inline formatting context. The consumed block-size stored in
    // the incoming break token will be stored in FragmentData objects to
    // identify each portion for a given fragmentainer.
    LayoutUnit consumed_block_size;
    if (incoming_break_token)
      consumed_block_size = incoming_break_token->ConsumedBlockSize();
    if (fragment_item->IsFirstForNode()) {
      // This is the first fragment generated for the node (i.e. we're on the
      // first line and first fragmentainer (column) that this node occurs
      // in). Now is our chance to reset everything (the number or size of
      // fragments may have changed since last time). All the other fragments
      // will be visited in due course.
      if (allow_reset && !object.IsBox()) {
        // For text and non-atomic inlines, we now remove additional
        // FragmentData objects, and reset the visual rect. The visual rect will
        // be set and expanded, as we visit each individual fragment.
        fragment_data->ClearNextFragment();
        fragment_data->SetVisualRect(IntRect());
      }
      fragment_data->SetLogicalTopInFlowThread(consumed_block_size);
    } else {
      // This is not the first fragment. Now see if we can find a FragmentData
      // with the right consumed block-size (or flow thread logical top). If
      // not, we'll have to create one now.
      while (consumed_block_size > fragment_data->LogicalTopInFlowThread()) {
        FragmentData* next_fragment_data = fragment_data->NextFragment();
        if (!next_fragment_data) {
          fragment_data = &fragment_data->EnsureNextFragment();
          fragment_data->SetLogicalTopInFlowThread(consumed_block_size);
          break;
        }
        fragment_data = next_fragment_data;
      }
      DCHECK_EQ(fragment_data->LogicalTopInFlowThread(), consumed_block_size);
    }
  } else {
    // The fragment is block-level.
    if (IsResumingLayout(incoming_break_token)) {
      // This isn't the first fragment for the node. We now need to walk past
      // all prededing fragments to figure out which FragmentData to return (or
      // create, if it doesn't already exist).
      const LayoutBox& layout_box = ToLayoutBox(object);
      for (wtf_size_t idx = 0;; idx++) {
        DCHECK_LT(idx, layout_box.PhysicalFragmentCount());
        if (layout_box.GetPhysicalFragment(idx) == box_fragment)
          break;
        FragmentData* next = fragment_data->NextFragment();
        if (!next) {
          DCHECK_EQ(layout_box.GetPhysicalFragment(idx + 1), box_fragment);
          fragment_data = &fragment_data->EnsureNextFragment();
          break;
        }
        fragment_data = next;
      }
      fragment_data->SetLogicalTopInFlowThread(
          incoming_break_token->ConsumedBlockSize());
    }
    if (!box_fragment->BreakToken()) {
      // We have reached the end. There may be more data entries that were
      // needed in the previous layout, but not any more. Clear them.
      fragment_data->ClearNextFragment();
    }
  }

  if (needs_paint_properties)
    fragment_data->EnsurePaintProperties();

  return NGPrePaintInfo(iterator, *fragment_data);
}

}  // anonymous namespace

void PrePaintTreeWalk::WalkTree(LocalFrameView& root_frame_view) {
  if (root_frame_view.ShouldThrottleRendering()) {
    // Skip the throttled frame. Will update it when it becomes unthrottled.
    return;
  }

  DCHECK(root_frame_view.GetFrame().GetDocument()->Lifecycle().GetState() ==
         DocumentLifecycle::kInPrePaint);

  // Reserve 50 elements for a really deep DOM. If the nesting is deeper than
  // this, then the vector will reallocate, but it shouldn't be a big deal. This
  // is also temporary within this function.
  DCHECK_EQ(context_storage_.size(), 0u);
  context_storage_.ReserveCapacity(50);
  context_storage_.emplace_back();

  // GeometryMapper depends on paint properties.
  bool needs_tree_builder_context_update =
      NeedsTreeBuilderContextUpdate(root_frame_view, context_storage_.back());
  if (needs_tree_builder_context_update)
    GeometryMapper::ClearCache();

  if (root_frame_view.GetFrame().IsMainFrame()) {
    auto property_changed = VisualViewportPaintPropertyTreeBuilder::Update(
        root_frame_view.GetPage()->GetVisualViewport(),
        *context_storage_.back().tree_builder_context);

    if (property_changed >
        PaintPropertyChangeType::kChangedOnlyCompositedValues) {
      root_frame_view.SetPaintArtifactCompositorNeedsUpdate();
    }
  }

  Walk(root_frame_view);
  paint_invalidator_.ProcessPendingDelayedPaintInvalidations();
  context_storage_.pop_back();

#if DCHECK_IS_ON()
  if (needs_tree_builder_context_update) {
    if (VLOG_IS_ON(2) && root_frame_view.GetLayoutView()) {
      LOG(ERROR) << "PrePaintTreeWalk::Walk(root_frame_view="
                 << &root_frame_view << ")\nPaintLayer tree:";
      showLayerTree(root_frame_view.GetLayoutView()->Layer());
    }
    if (VLOG_IS_ON(1))
      showAllPropertyTrees(root_frame_view);
  }
#endif

  // If the frame is invalidated, we need to inform the frame's chrome client
  // so that the client will initiate repaint of the contents.
  if (needs_invalidate_chrome_client_) {
    if (auto* client = root_frame_view.GetChromeClient())
      client->InvalidateRect(IntRect(IntPoint(), root_frame_view.Size()));
  }
}

void PrePaintTreeWalk::Walk(LocalFrameView& frame_view) {
  if (frame_view.ShouldThrottleRendering()) {
    // Skip the throttled frame. Will update it when it becomes unthrottled.
    return;
  }

  // We need to be careful not to have a reference to the parent context, since
  // this reference will be to the context_storage_ memory which may be
  // reallocated during this function call.
  wtf_size_t parent_context_index = context_storage_.size() - 1;
  auto parent_context = [this,
                         parent_context_index]() -> PrePaintTreeWalkContext& {
    return context_storage_[parent_context_index];
  };

  bool needs_tree_builder_context_update =
      NeedsTreeBuilderContextUpdate(frame_view, parent_context());

  // Note that because we're emplacing an object constructed from
  // parent_context() (which is a reference to the vector itself), it's
  // important to first ensure that there's sufficient capacity in the vector.
  // Otherwise, it may reallocate causing parent_context() to point to invalid
  // memory.
  ResizeContextStorageIfNeeded();
  context_storage_.emplace_back(parent_context(),
                                PaintInvalidatorContext::ParentContextAccessor(
                                    this, parent_context_index),
                                needs_tree_builder_context_update);
  auto context = [this]() -> PrePaintTreeWalkContext& {
    return context_storage_.back();
  };

  // ancestor_overflow_paint_layer does not cross frame boundaries.
  context().ancestor_overflow_paint_layer = nullptr;
  if (context().tree_builder_context) {
    PaintPropertyTreeBuilder::SetupContextForFrame(
        frame_view, *context().tree_builder_context);
    context().tree_builder_context->supports_composited_raster_invalidation =
        frame_view.GetFrame().GetSettings()->GetAcceleratedCompositingEnabled();
  }

  if (LayoutView* view = frame_view.GetLayoutView()) {
#if DCHECK_IS_ON()
    if (VLOG_IS_ON(3) && needs_tree_builder_context_update) {
      LOG(ERROR) << "PrePaintTreeWalk::Walk(frame_view=" << &frame_view
                 << ")\nLayout tree:";
      showLayoutTree(view);
    }
#endif

    Walk(*view, /* iterator */ nullptr);
#if DCHECK_IS_ON()
    view->AssertSubtreeClearedPaintInvalidationFlags();
#endif
  }

  frame_view.GetLayoutShiftTracker().NotifyPrePaintFinished();
  context_storage_.pop_back();
}

bool PrePaintTreeWalk::NeedsEffectiveAllowedTouchActionUpdate(
    const LayoutObject& object,
    PrePaintTreeWalk::PrePaintTreeWalkContext& context) const {
  return context.effective_allowed_touch_action_changed ||
         object.EffectiveAllowedTouchActionChanged() ||
         object.DescendantEffectiveAllowedTouchActionChanged();
}

namespace {
bool HasBlockingTouchEventHandler(const LocalFrame& frame,
                                  EventTarget& target) {
  if (!target.HasEventListeners())
    return false;
  const auto& registry = frame.GetEventHandlerRegistry();
  const auto* blocking = registry.EventHandlerTargets(
      EventHandlerRegistry::kTouchStartOrMoveEventBlocking);
  const auto* blocking_low_latency = registry.EventHandlerTargets(
      EventHandlerRegistry::kTouchStartOrMoveEventBlockingLowLatency);
  return blocking->Contains(&target) || blocking_low_latency->Contains(&target);
}

bool HasBlockingTouchEventHandler(const LayoutObject& object) {
  if (IsA<LayoutView>(object)) {
    auto* frame = object.GetFrame();
    if (HasBlockingTouchEventHandler(*frame, *frame->DomWindow()))
      return true;
  }

  auto* node = object.GetNode();
  auto* layout_block_flow = DynamicTo<LayoutBlockFlow>(object);
  if (!node && layout_block_flow &&
      layout_block_flow->IsAnonymousBlockContinuation()) {
    // An anonymous continuation does not have handlers so we need to check the
    // DOM ancestor for handlers using |NodeForHitTest|.
    node = object.NodeForHitTest();
  }
  if (!node)
    return false;
  return HasBlockingTouchEventHandler(*object.GetFrame(), *node);
}
}  // namespace

void PrePaintTreeWalk::UpdateEffectiveAllowedTouchAction(
    const LayoutObject& object,
    PrePaintTreeWalk::PrePaintTreeWalkContext& context) {
  if (object.EffectiveAllowedTouchActionChanged())
    context.effective_allowed_touch_action_changed = true;

  if (context.effective_allowed_touch_action_changed) {
    object.GetMutableForPainting().UpdateInsideBlockingTouchEventHandler(
        context.inside_blocking_touch_event_handler ||
        HasBlockingTouchEventHandler(object));
  }

  if (object.InsideBlockingTouchEventHandler())
    context.inside_blocking_touch_event_handler = true;
}

void PrePaintTreeWalk::InvalidatePaintForHitTesting(
    const LayoutObject& object,
    PrePaintTreeWalk::PrePaintTreeWalkContext& context) {
  if (context.paint_invalidator_context.subtree_flags &
      PaintInvalidatorContext::kSubtreeNoInvalidation)
    return;

  if (!context.effective_allowed_touch_action_changed)
    return;

  context.paint_invalidator_context.painting_layer->SetNeedsRepaint();
  ObjectPaintInvalidator(object).InvalidateDisplayItemClient(
      object, PaintInvalidationReason::kHitTest);
}

void PrePaintTreeWalk::UpdateAuxiliaryObjectProperties(
    const LayoutObject& object,
    PrePaintTreeWalk::PrePaintTreeWalkContext& context) {
  if (!RuntimeEnabledFeatures::CompositeAfterPaintEnabled())
    return;

  if (!object.HasLayer())
    return;

  PaintLayer* paint_layer = ToLayoutBoxModelObject(object).Layer();
  paint_layer->UpdateAncestorOverflowLayer(
      context.ancestor_overflow_paint_layer);

  if (object.StyleRef().HasStickyConstrainedPosition()) {
    paint_layer->GetLayoutObject().UpdateStickyPositionConstraints();

    // Sticky position constraints and ancestor overflow scroller affect the
    // sticky layer position, so we need to update it again here.
    // TODO(flackr): This should be refactored in the future to be clearer (i.e.
    // update layer position and ancestor inputs updates in the same walk).
    paint_layer->UpdateLayerPosition();
  }
  if (paint_layer->IsRootLayer() || object.HasOverflowClip())
    context.ancestor_overflow_paint_layer = paint_layer;
}

bool PrePaintTreeWalk::NeedsTreeBuilderContextUpdate(
    const LocalFrameView& frame_view,
    const PrePaintTreeWalkContext& context) {
  if (frame_view.GetFrame().IsMainFrame() &&
      frame_view.GetPage()->GetVisualViewport().NeedsPaintPropertyUpdate()) {
    return true;
  }

  return frame_view.GetLayoutView() &&
         (ObjectRequiresTreeBuilderContext(*frame_view.GetLayoutView()) ||
          ContextRequiresTreeBuilderContext(context,
                                            *frame_view.GetLayoutView()));
}

bool PrePaintTreeWalk::ObjectRequiresPrePaint(const LayoutObject& object) {
  return object.ShouldCheckForPaintInvalidation() ||
         object.EffectiveAllowedTouchActionChanged() ||
         object.DescendantEffectiveAllowedTouchActionChanged();
}

bool PrePaintTreeWalk::ContextRequiresPrePaint(
    const PrePaintTreeWalkContext& context) {
  return context.paint_invalidator_context.NeedsSubtreeWalk() ||
         context.effective_allowed_touch_action_changed || context.clip_changed;
}

bool PrePaintTreeWalk::ObjectRequiresTreeBuilderContext(
    const LayoutObject& object) {
  return object.NeedsPaintPropertyUpdate() ||
         (!object.PrePaintBlockedByDisplayLock(
              DisplayLockLifecycleTarget::kChildren) &&
          (object.DescendantNeedsPaintPropertyUpdate() ||
           object.DescendantNeedsPaintOffsetAndVisualRectUpdate()));
}

bool PrePaintTreeWalk::ContextRequiresTreeBuilderContext(
    const PrePaintTreeWalkContext& context,
    const LayoutObject& object) {
  return (context.tree_builder_context &&
          context.tree_builder_context->force_subtree_update_reasons) ||
         context.paint_invalidator_context.NeedsVisualRectUpdate(object);
}

void PrePaintTreeWalk::CheckTreeBuilderContextState(
    const LayoutObject& object,
    const PrePaintTreeWalkContext& parent_context) {
  if (parent_context.tree_builder_context ||
      (!ObjectRequiresTreeBuilderContext(object) &&
       !ContextRequiresTreeBuilderContext(parent_context, object))) {
    return;
  }

  CHECK(!object.NeedsPaintPropertyUpdate());
  CHECK(!object.DescendantNeedsPaintPropertyUpdate());
  CHECK(!object.DescendantNeedsPaintOffsetAndVisualRectUpdate());
  if (parent_context.paint_invalidator_context.NeedsVisualRectUpdate(object)) {
    // Note that if paint_invalidator_context's NeedsVisualRectUpdate(object) is
    // true, we definitely want to CHECK. However, we would also like to know
    // the value of object.NeedsPaintOffsetAndVisualRectUpdate(), hence one of
    // the two CHECKs below will definitely trigger, and depending on which one
    // does we will know the value.
    CHECK(object.NeedsPaintOffsetAndVisualRectUpdate());
    CHECK(!object.NeedsPaintOffsetAndVisualRectUpdate());
  }
  CHECK(false) << "Unknown reason.";
}

void PrePaintTreeWalk::WalkInternal(const LayoutObject& object,
                                    const NGFragmentChildIterator* iterator,
                                    PrePaintTreeWalkContext& context) {
  PaintInvalidatorContext& paint_invalidator_context =
      context.paint_invalidator_context;

  base::Optional<NGPrePaintInfo> pre_paint_info_storage;
  NGPrePaintInfo* pre_paint_info = nullptr;
  if (iterator) {
    bool allow_reset = context.tree_builder_context.has_value()
#if DCHECK_IS_ON()
                       && context.tree_builder_context->is_actually_needed
#endif
        ;
    pre_paint_info_storage.emplace(SetupFragmentData(*iterator, allow_reset));
    pre_paint_info = &pre_paint_info_storage.value();
  }

  // This must happen before updatePropertiesForSelf, because the latter reads
  // some of the state computed here.
  UpdateAuxiliaryObjectProperties(object, context);

  base::Optional<PaintPropertyTreeBuilder> property_tree_builder;
  PaintPropertyChangeType property_changed =
      PaintPropertyChangeType::kUnchanged;
  if (context.tree_builder_context) {
    property_tree_builder.emplace(object, pre_paint_info,
                                  *context.tree_builder_context);

    property_changed =
        std::max(property_changed, property_tree_builder->UpdateForSelf());

    if ((property_changed > PaintPropertyChangeType::kUnchanged) &&
        !context.tree_builder_context
             ->supports_composited_raster_invalidation) {
      paint_invalidator_context.subtree_flags |=
          PaintInvalidatorContext::kSubtreeFullInvalidation;
    }
  }

  // This must happen before paint invalidation because background painting
  // depends on the effective allowed touch action.
  UpdateEffectiveAllowedTouchAction(object, context);

  if (paint_invalidator_.InvalidatePaint(
          object, pre_paint_info,
          base::OptionalOrNullptr(context.tree_builder_context),
          paint_invalidator_context))
    needs_invalidate_chrome_client_ = true;

  InvalidatePaintForHitTesting(object, context);

  if (context.tree_builder_context) {
    property_changed =
        std::max(property_changed, property_tree_builder->UpdateForChildren());

    // Save clip_changed flag in |context| so that all descendants will see it
    // even if we don't create tree_builder_context.
    if (context.tree_builder_context->clip_changed)
      context.clip_changed = true;

    if (property_changed != PaintPropertyChangeType::kUnchanged) {
      if (property_changed >
          PaintPropertyChangeType::kChangedOnlyCompositedValues) {
        object.GetFrameView()->SetPaintArtifactCompositorNeedsUpdate();
      }

      if (!RuntimeEnabledFeatures::CompositeAfterPaintEnabled()) {
        if (property_changed >
            PaintPropertyChangeType::kChangedOnlyCompositedValues) {
          const auto* paint_invalidation_layer =
              paint_invalidator_context.paint_invalidation_container->Layer();
          if (!paint_invalidation_layer->SelfNeedsRepaint()) {
            auto* mapping =
                paint_invalidation_layer->GetCompositedLayerMapping();
            if (!mapping)
              mapping = paint_invalidation_layer->GroupedMapping();
            if (mapping)
              mapping->SetNeedsCheckRasterInvalidation();
          }
        }
      } else if (!context.tree_builder_context
                      ->supports_composited_raster_invalidation) {
        paint_invalidator_context.subtree_flags |=
            PaintInvalidatorContext::kSubtreeFullInvalidation;
      }
    }
  }

  // When this or ancestor clip changed, the layer needs repaint because it
  // may paint more or less results according to the changed clip.
  if (context.clip_changed && object.HasLayer())
    ToLayoutBoxModelObject(object).Layer()->SetNeedsRepaint();

  // TODO(crbug.com/1058792): Allow multiple fragments for composited elements
  // (passing |iterator| here is probably part of the solution).
  CompositingLayerPropertyUpdater::Update(object);
}

LocalFrameView* FindWebViewPluginContentFrameView(
    const LayoutEmbeddedContent& embedded_content) {
  for (Frame* frame = embedded_content.GetFrame()->Tree().FirstChild(); frame;
       frame = frame->Tree().NextSibling()) {
    if (frame->IsLocalFrame() &&
        To<LocalFrame>(frame)->OwnerLayoutObject() == &embedded_content)
      return To<LocalFrame>(frame)->View();
  }
  return nullptr;
}

void PrePaintTreeWalk::WalkNGChildren(const LayoutObject* parent,
                                      NGFragmentChildIterator* iterator) {
  for (; !iterator->IsAtEnd(); iterator->Advance()) {
    const LayoutObject* object = (*iterator)->GetLayoutObject();
    if (const auto* fragment_item = (*iterator)->FragmentItem()) {
      // Line boxes are not interesting. They have no paint effects. Descend
      // directly into children.
      if (fragment_item->Type() == NGFragmentItem::kLine) {
        WalkChildren(/* parent */ nullptr, iterator);
        continue;
      }
    } else if (!object) {
      // A column doesn't paint anything itself. Just include its offset and
      // descend into children.
      DCHECK((*iterator)->BoxFragment()->IsColumnBox());
      PhysicalOffset offset = (*iterator)->Link().offset;
      PaintPropertyTreeBuilderFragmentContext::ContainingBlockContext*
          fragment_context = nullptr;
      if (context_storage_.back().tree_builder_context) {
        PaintPropertyTreeBuilderContext& tree_builder_context =
            context_storage_.back().tree_builder_context.value();
        fragment_context = &tree_builder_context.fragments[0].current;
        fragment_context->paint_offset += offset;
      }
      WalkChildren(/* parent */ nullptr, iterator);
      if (fragment_context)
        fragment_context->paint_offset -= offset;
      continue;
    }
    Walk(*object, iterator);
  }

  const LayoutBlockFlow* parent_block = DynamicTo<LayoutBlockFlow>(parent);
  if (!parent_block || !parent_block->MultiColumnFlowThread())
    return;
  // Multicol containers only contain special legacy children invisible to
  // LayoutNG, so we need to clean them manually.
  for (const LayoutObject* child = parent->SlowFirstChild(); child;
       child = child->NextSibling()) {
    DCHECK(child->IsLayoutFlowThread() || child->IsLayoutMultiColumnSet() ||
           child->IsLayoutMultiColumnSpannerPlaceholder());
    child->GetMutableForPainting().ClearPaintFlags();
  }
}

void PrePaintTreeWalk::WalkLegacyChildren(const LayoutObject& object) {
  if (const LayoutBox* layout_box = ToLayoutBoxOrNull(&object)) {
    if (layout_box->CanTraversePhysicalFragments()) {
      // Enter NG child fragment traversal. We'll stay in this mode for all
      // descendants that support fragment traversal. We'll re-enter
      // LayoutObject traversal for descendants that don't support it. This only
      // works correctly if we're not block-fragmented, though, so DCHECK for
      // that.
      DCHECK_EQ(layout_box->PhysicalFragmentCount(), 1u);
      const NGPhysicalBoxFragment& fragment =
          To<NGPhysicalBoxFragment>(*layout_box->GetPhysicalFragment(0));
      DCHECK(!fragment.BreakToken());
      NGFragmentChildIterator child_iterator(fragment);
      WalkNGChildren(&object, &child_iterator);
      return;
    }
  }

  for (const LayoutObject* child = object.SlowFirstChild(); child;
       child = child->NextSibling()) {
    if (child->IsLayoutMultiColumnSpannerPlaceholder()) {
      child->GetMutableForPainting().ClearPaintFlags();
      continue;
    }
    // Skip out-of-flow positioned children lest they be walked twice. If |this|
    // is an NG object, but it still walks its children the legacy way (this may
    // happen to table-cells; see LayoutObject::CanTraversePhysicalFragments()),
    // we're either going to handle it in the code below after the loop - if
    // |this| is actually the containing block. Otherwise it will be handled by
    // some ancestor - either in the same code below (if it's a legacy-walking
    // object) or via regular child fragment traversal. If we walk it here as
    // well, we'd end up walking it twice. This is both bad for performance, and
    // also correctness, as fragment items are sensitive to how they're walked
    // (see SetupFragmentData()).
    if (UNLIKELY(RuntimeEnabledFeatures::LayoutNGFragmentTraversalEnabled() &&
                 child->IsOutOfFlowPositioned() && object.IsLayoutNGObject()))
      continue;
    Walk(*child, /* iterator */ nullptr);
  }

  if (!RuntimeEnabledFeatures::LayoutNGFragmentTraversalEnabled())
    return;

  const LayoutBlock* block = DynamicTo<LayoutBlock>(&object);
  if (!block)
    return;
  const auto* positioned_objects = block->PositionedObjects();
  if (!positioned_objects)
    return;

  // If we have performed NG fragment traversal in any part of the subtree, we
  // may have missed certain out-of-flow positioned objects. LayoutNG fragments
  // are always children of their containing block, while the structure of the
  // LayoutObject tree corresponds more closely to that of the DOM tree.
  //
  // Example: if we assume that flexbox isn't natively supported in LayoutNG:
  //
  // <div id="flex" style="display:flex; position:relative;">
  //   <div id="flexitem">
  //     <div id="abs" style="position:absolute;"></div>
  //     <div id="regular"></div>
  //
  // If we let |object| be #flex, it will be handled by legacy LayoutObject
  // traversal, while #flexitem, on the other hand, can traverse its NG child
  // fragments. However, #regular will be the only child fragment of #flexitem,
  // since the containing block for #abs is #flex. So we'd miss it, unless we
  // walk it now.
  for (const LayoutBox* box : *positioned_objects) {
    // It's important that objects that have already been walked be left alone.
    // Otherwise, we might calculate the wrong offsets (and overwrite the
    // correct ones) in case of out-of-flow positioned objects whose containing
    // block is a relatively positioned non-atomic inline (such objects will
    // already have been properly walked, since we don't switch engines within
    // an inline formatting context). Put differently, the code here will only
    // do the right thing if |object| is truly the containing block of the
    // positioned objects in its list (which isn't the case if the containing
    // block is a non-atomic inline).
    if (!ObjectRequiresPrePaint(*box) &&
        !ObjectRequiresTreeBuilderContext(*box))
      continue;
    DCHECK_EQ(box->Container(), &object);
    Walk(*box, /* iterator */ nullptr);
  }
}

void PrePaintTreeWalk::WalkChildren(const LayoutObject* object,
                                    const NGFragmentChildIterator* iterator) {
  DCHECK(iterator || object);

  if (!iterator) {
    // We're not doing LayoutNG fragment traversal of this object.
    WalkLegacyChildren(*object);
    return;
  }

  // If we are performing LayoutNG fragment traversal, but this object doesn't
  // support that, we need to switch back to legacy LayoutObject traversal for
  // its children. We're then also assuming that we're either not
  // block-fragmenting, or that this is monolithic content. We may re-enter
  // LayoutNG fragment traversal if we get to a descendant that supports that.
  if (object && !object->CanTraversePhysicalFragments()) {
    DCHECK(
        !object->FlowThreadContainingBlock() ||
        (object->IsBox() && ToLayoutBox(object)->GetPaginationBreakability() ==
                                LayoutBox::kForbidBreaks));
    WalkLegacyChildren(*object);
    return;
  }

  // Traverse child NG fragments.
  NGFragmentChildIterator child_iterator(iterator->Descend());
  WalkNGChildren(object, &child_iterator);
}

void PrePaintTreeWalk::Walk(const LayoutObject& object,
                            const NGFragmentChildIterator* iterator) {
  const NGPhysicalBoxFragment* physical_fragment = nullptr;
  bool is_last_fragment = true;
  if (iterator) {
    physical_fragment = (*iterator)->BoxFragment();
    if (const auto* fragment_item = (*iterator)->FragmentItem())
      is_last_fragment = fragment_item->IsLastForNode();
    else if (physical_fragment)
      is_last_fragment = !physical_fragment->BreakToken();
  }

  // We need to be careful not to have a reference to the parent context, since
  // this reference will be to the context_storage_ memory which may be
  // reallocated during this function call.
  wtf_size_t parent_context_index = context_storage_.size() - 1;
  auto parent_context = [this,
                         parent_context_index]() -> PrePaintTreeWalkContext& {
    return context_storage_[parent_context_index];
  };

  bool needs_tree_builder_context_update =
      ContextRequiresTreeBuilderContext(parent_context(), object) ||
      ObjectRequiresTreeBuilderContext(object);

  // The following is for debugging crbug.com/974639.
  CheckTreeBuilderContextState(object, parent_context());

  // Early out from the tree walk if possible.
  if (!needs_tree_builder_context_update && !ObjectRequiresPrePaint(object) &&
      !ContextRequiresPrePaint(parent_context())) {
    return;
  }

  // Note that because we're emplacing an object constructed from
  // parent_context() (which is a reference to the vector itself), it's
  // important to first ensure that there's sufficient capacity in the vector.
  // Otherwise, it may reallocate causing parent_context() to point to invalid
  // memory.
  ResizeContextStorageIfNeeded();
  context_storage_.emplace_back(parent_context(),
                                PaintInvalidatorContext::ParentContextAccessor(
                                    this, parent_context_index),
                                needs_tree_builder_context_update);
  auto context = [this]() -> PrePaintTreeWalkContext& {
    return context_storage_.back();
  };

  // Ignore clip changes from ancestor across transform boundaries.
  if (object.StyleRef().HasTransform()) {
    context().clip_changed = false;
    if (context().tree_builder_context)
      context().tree_builder_context->clip_changed = false;
  }

  WalkInternal(object, iterator, context());

  if (is_last_fragment)
    object.NotifyDisplayLockDidPrePaint(DisplayLockLifecycleTarget::kSelf);

  bool child_walk_blocked = object.PrePaintBlockedByDisplayLock(
      DisplayLockLifecycleTarget::kChildren);
  // If we need a subtree walk due to context flags, we need to store that
  // information on the display lock, since subsequent walks might not set the
  // same bits on the context.
  if (child_walk_blocked &&
      (ContextRequiresTreeBuilderContext(context(), object) ||
       ContextRequiresPrePaint(context()))) {
    // Note that effective allowed touch action changed is special in that
    // it requires us to specifically recalculate this value on each subtree
    // element. Other flags simply need a subtree walk. Some consideration
    // needs to be given to |clip_changed| which ensures that we repaint every
    // layer, but for the purposes of PrePaint, this flag is just forcing a
    // subtree walk.
    object.GetDisplayLockContext()->SetNeedsPrePaintSubtreeWalk(
        context().effective_allowed_touch_action_changed);
  }

  if (!child_walk_blocked) {
    WalkChildren(&object, iterator);

    if (object.IsLayoutEmbeddedContent()) {
      const LayoutEmbeddedContent& layout_embedded_content =
          ToLayoutEmbeddedContent(object);
      if (auto* embedded_view =
              layout_embedded_content.GetEmbeddedContentView()) {
        if (context().tree_builder_context) {
          auto& offset =
              context().tree_builder_context->fragments[0].current.paint_offset;
          offset += layout_embedded_content.ReplacedContentRect().offset;
          offset -= PhysicalOffset(embedded_view->FrameRect().Location());
          offset = PhysicalOffset(RoundedIntPoint(offset));
        }
        if (embedded_view->IsLocalFrameView()) {
          Walk(*To<LocalFrameView>(embedded_view));
        } else if (embedded_view->IsPluginView()) {
          // If it is a webview plugin, walk into the content frame view.
          if (auto* plugin_content_frame_view =
                  FindWebViewPluginContentFrameView(layout_embedded_content))
            Walk(*plugin_content_frame_view);
        } else {
          // We need to do nothing for RemoteFrameView. See crbug.com/579281.
        }
      }
    }

    object.NotifyDisplayLockDidPrePaint(DisplayLockLifecycleTarget::kChildren);
  }
  if (is_last_fragment)
    object.GetMutableForPainting().ClearPaintFlags();
  context_storage_.pop_back();
}

void PrePaintTreeWalk::ResizeContextStorageIfNeeded() {
  if (UNLIKELY(context_storage_.size() == context_storage_.capacity())) {
    DCHECK_GT(context_storage_.size(), 0u);
    context_storage_.ReserveCapacity(context_storage_.size() * 2);
  }
}

}  // namespace blink