// Copyright 2014 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "cc/trees/property_tree.h"

#include <stddef.h>

#include <algorithm>
#include <cmath>
#include <memory>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "base/check_op.h"
#include "base/debug/crash_logging.h"
#include "base/feature_list.h"
#include "base/memory/ptr_util.h"
#include "base/numerics/checked_math.h"
#include "base/numerics/safe_conversions.h"
#include "base/trace_event/traced_value.h"
#include "cc/base/features.h"
#include "cc/base/math_util.h"
#include "cc/trees/clip_node.h"
#include "cc/trees/compositor_commit_data.h"
#include "cc/trees/effect_node.h"
#include "cc/trees/layer_tree_impl.h"
#include "cc/trees/scroll_elasticity_utils.h"
#include "cc/trees/scroll_node.h"
#include "cc/trees/transform_node.h"
#include "cc/trees/viewport_property_ids.h"
#include "components/viz/common/frame_sinks/copy_output_request.h"
#include "ui/gfx/geometry/outsets_f.h"
#include "ui/gfx/geometry/point_conversions.h"
#include "ui/gfx/geometry/transform_util.h"
#include "ui/gfx/geometry/vector2d.h"
#include "ui/gfx/geometry/vector2d_conversions.h"
#include "ui/gfx/geometry/vector2d_f.h"

namespace cc {

AnchorPositionScrollData::AnchorPositionScrollData() = default;
AnchorPositionScrollData::~AnchorPositionScrollData() = default;
AnchorPositionScrollData::AnchorPositionScrollData(
    const AnchorPositionScrollData&) = default;

bool AnchorPositionScrollData::operator==(
    const AnchorPositionScrollData& other) const = default;

bool StickyPositionNodeData::operator==(
    const StickyPositionNodeData& other) const = default;

template <typename T>
PropertyTree<T>::PropertyTree(PropertyTrees* property_trees)
    : needs_update_(false), property_trees_(property_trees) {
  nodes_.push_back(T());
  MutableBack()->id = kRootPropertyNodeId;
  MutableBack()->parent_id = kInvalidPropertyNodeId;
}

// Equivalent to
// PropertyTree<T>::~PropertyTree() = default;
// but due to a gcc bug the generated destructor will have wrong symbol
// visibility in component build.
template <typename T>
PropertyTree<T>::~PropertyTree() = default;

template <typename T>
PropertyTree<T>& PropertyTree<T>::operator=(const PropertyTree<T>&) = default;

#define DCHECK_NODE_EXISTENCE(check_node_existence, state, property,           \
                              needs_rebuild)                                   \
  DCHECK(!check_node_existence || ((!state.currently_running[property] &&      \
                                    !state.potentially_animating[property]) || \
                                   needs_rebuild))

TransformTree::TransformTree(PropertyTrees* property_trees)
    : PropertyTree<TransformNode>(property_trees),
      page_scale_factor_(1.f),
      device_scale_factor_(1.f),
      device_transform_scale_factor_(1.f),
      external_page_scale_factor_(1.f) {
  cached_data_.push_back(TransformCachedNodeData());
}

TransformTree::~TransformTree() = default;
TransformTree& TransformTree::operator=(const TransformTree&) = default;

template <typename T>
int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
  DCHECK_GT(nodes_.size(), 0u);
  nodes_.push_back(tree_node);
  T& node = nodes_.back();
  node.parent_id = parent_id;
  node.id = static_cast<int>(nodes_.size()) - 1;
  return node.id;
}

template <typename T>
void PropertyTree<T>::RemoveNodes(size_t n) {
  CHECK_LE(n, nodes_.size());
  nodes_.resize(nodes_.size() - n);

  const int upper_bound = base::checked_cast<int>(nodes_.size());
  base::EraseIf(element_id_to_node_index_, [upper_bound](const auto& entry) {
    return entry.second >= upper_bound;
  });
}

template <typename T>
void PropertyTree<T>::clear() {
  needs_update_ = false;
  nodes_.clear();
  nodes_.push_back(T());
  MutableBack()->id = kRootPropertyNodeId;
  MutableBack()->parent_id = kInvalidPropertyNodeId;
  element_id_to_node_index_.clear();

#if DCHECK_IS_ON()
  PropertyTree<T> tree(nullptr);
  DCHECK(tree == *this);
#endif
}

#if DCHECK_IS_ON()
template <typename T>
bool PropertyTree<T>::operator==(const PropertyTree<T>& other) const {
  return nodes() == other.nodes() && needs_update() == other.needs_update() &&
         element_id_to_node_index() == other.element_id_to_node_index();
}

template <typename T>
std::string PropertyTree<T>::ToString() const {
  base::trace_event::TracedValueJSON value;
  AsValueInto(&value);
  return value.ToFormattedJSON();
}
#endif

template <typename T>
void PropertyTree<T>::AsValueInto(base::trace_event::TracedValue* value) const {
  value->BeginArray("nodes");
  for (const auto& node : nodes_) {
    value->BeginDictionary();
    node.AsValueInto(value);
    value->EndDictionary();
  }
  value->EndArray();
  value->SetBooleanWithCopiedName("needs_update", needs_update_);
}

template class PropertyTree<TransformNode>;
template class PropertyTree<ClipNode>;
template class PropertyTree<EffectNode>;
template class PropertyTree<ScrollNode>;

int TransformTree::Insert(const TransformNode& tree_node, int parent_id) {
  int node_id = PropertyTree<TransformNode>::Insert(tree_node, parent_id);
  DCHECK_EQ(node_id, static_cast<int>(cached_data_.size()));

  cached_data_.push_back(TransformCachedNodeData());
  return node_id;
}

void TransformTree::RemoveNodes(size_t n) {
  PropertyTree<TransformNode>::RemoveNodes(n);
  cached_data_.resize(cached_data_.size() - n);
}

void TransformTree::clear() {
  PropertyTree<TransformNode>::clear();

  page_scale_factor_ = 1.f;
  device_scale_factor_ = 1.f;
  device_transform_scale_factor_ = 1.f;
  external_page_scale_factor_ = 1.f;
  nodes_affected_by_outer_viewport_bounds_delta_.clear();
  nodes_affected_by_safe_area_inset_bottom_.clear();
  cached_data_.clear();
  cached_data_.push_back(TransformCachedNodeData());
  sticky_position_data_.clear();
  anchor_position_scroll_data_.clear();
  drawn_elastic_overscroll_.clear();

#if DCHECK_IS_ON()
  DCHECK(TransformTree() == *this);
#endif
}

void TransformTree::set_needs_update(bool needs_update) {
  if (needs_update && !PropertyTree<TransformNode>::needs_update())
    property_trees()->UpdateTransformTreeUpdateNumber();
  PropertyTree<TransformNode>::set_needs_update(needs_update);
}

bool TransformTree::OnTransformAnimated(ElementId element_id,
                                        const gfx::Transform& transform) {
  TransformNode* node = MutableFindNodeFromElementId(element_id);
  // TODO(crbug.com/40828469): Remove this when we no longer animate
  // non-existent nodes.
  if (!node) {
    return false;
  }
  if (node->local == transform)
    return false;
  node->local = transform;
  node->needs_local_transform_update = true;
  node->SetTransformChanged(DamageReason::kUntracked);
  property_trees()->set_changed(true);
  set_needs_update(true);
  return true;
}

void TransformTree::ResetChangeTracking() {
  for (int id = kContentsRootPropertyNodeId; id < static_cast<int>(size());
       ++id) {
    TransformNode& node = MutableNode(id);
    node.ClearTransformChanged();
  }
}

void TransformTree::UpdateAllTransforms(
    const ViewportPropertyIds& viewport_property_ids) {
  if (!needs_update()) {
#if DCHECK_IS_ON()
    // If the transform tree does not need an update, no TransformNode should
    // need a local transform update.
    for (int i = kContentsRootPropertyNodeId; i < static_cast<int>(size());
         ++i) {
      DCHECK(!Node(i).needs_local_transform_update);
    }
#endif
    return;
  }

  UpdateTransformsData update_data;
  do {
    size_t last_num_stale_forward_dependencies =
        update_data.stale_forward_dependencies.size();
    for (int i = kContentsRootPropertyNodeId; i < static_cast<int>(size());
         ++i) {
      UpdateTransforms(i, &viewport_property_ids, &update_data);
    }
    CHECK(last_num_stale_forward_dependencies == 0 ||
          update_data.stale_forward_dependencies.size() <
              last_num_stale_forward_dependencies);
  } while (!update_data.stale_forward_dependencies.empty());

  set_needs_update(false);
}

void TransformTree::CopyFromPreservingNodes(const TransformTree& other) {
  PropertyTree<TransformNode>::set_needs_update(other.needs_update());
  element_id_to_node_index_ = other.element_id_to_node_index_;

  page_scale_factor_ = other.page_scale_factor_;
  device_scale_factor_ = other.device_scale_factor_;
  device_transform_scale_factor_ = other.device_transform_scale_factor_;
  external_page_scale_factor_ = other.external_page_scale_factor_;
  nodes_affected_by_outer_viewport_bounds_delta_ =
      other.nodes_affected_by_outer_viewport_bounds_delta_;
  nodes_affected_by_safe_area_inset_bottom_ =
      other.nodes_affected_by_safe_area_inset_bottom_;
  sticky_position_data_ = other.sticky_position_data_;
  anchor_position_scroll_data_ = other.anchor_position_scroll_data_;
  drawn_elastic_overscroll_ = other.drawn_elastic_overscroll_;
}

TransformTree::UpdateTransformsData::UpdateTransformsData() = default;
TransformTree::UpdateTransformsData::~UpdateTransformsData() = default;

void TransformTree::UpdateTransforms(
    int id,
    const ViewportPropertyIds* viewport_property_ids,
    UpdateTransformsData* update_data) {
  TransformNode& node = MutableNode(id);
  TransformNode& parent_node = MutableParent(node);
  gfx::Transform old_to_parent = node.to_parent;
  gfx::Vector2dF old_snap_amount = node.snap_amount;
  // TODO(flackr): Only dirty when scroll offset changes.
  if (node.sticky_position_constraint_id >= 0 ||
      node.anchor_position_scroll_data_id >= 0 ||
      node.needs_local_transform_update || node.should_undo_overscroll) {
    UpdateLocalTransform(&node, viewport_property_ids, update_data);
  } else {
    UndoSnapping(&node);
  }
  UpdateScreenSpaceTransform(&node, parent_node);
  UpdateAnimationProperties(&node, parent_node);
  UpdateSnapping(&node);
  UpdateTransformChanged(&node, parent_node);
  UpdateNodeAndAncestorsAreAnimatedOrInvertible(&node, parent_node);
  UpdateNodeOrAncestorsWillChangeTransform(&node, parent_node);

  // If `node` has been depended by a previous node and neither its `to_parent`
  // nor its `snap_amount` is changed, the depending node actually got correct
  // data, so remove `id` from `stale_forward_dependencies`. Note that we
  // should check all changes that may affect the depending transform node.
  // For now forward dependency only happens in AnchorPositionOffset().
  if (update_data && node.to_parent == old_to_parent &&
      node.snap_amount == old_snap_amount) {
    update_data->stale_forward_dependencies.erase(id);
  }

  DCHECK(!node.needs_local_transform_update);
}

bool TransformTree::IsDescendant(int desc_id, int source_id) const {
  while (desc_id != source_id) {
    if (desc_id == kInvalidPropertyNodeId)
      return false;
    desc_id = Node(desc_id).parent_id;
  }
  return true;
}

void TransformTree::CombineTransformsBetween(int source_id,
                                             int dest_id,
                                             gfx::Transform* transform) const {
  DCHECK(source_id > dest_id);
  const TransformNode& current = Node(source_id);
  const TransformNode& dest = Node(dest_id);
  // Combine transforms to and from the screen when possible. Since flattening
  // is a non-linear operation, we cannot use this approach when there is
  // non-trivial flattening between the source and destination nodes. For
  // example, consider the tree R->A->B->C, where B flattens its inherited
  // transform, and A has a non-flat transform. Suppose C is the source and A is
  // the destination. The expected result is C * B. But C's to_screen
  // transform is C * B * flattened(A * R), and A's from_screen transform is
  // R^{-1} * A^{-1}. If at least one of A and R isn't flat, the inverse of
  // flattened(A * R) won't be R^{-1} * A{-1}, so multiplying C's to_screen and
  // A's from_screen will not produce the correct result.
  if (dest.ancestors_are_invertible && dest.node_and_ancestors_are_flat) {
    transform->PostConcat(ToScreen(current.id));
    transform->PostConcat(FromScreen(dest.id));
    return;
  }

  // Flattening is defined in a way that requires it to be applied while
  // traversing downward in the tree. We first identify nodes that are on the
  // path from the source to the destination (this is traversing upward), and
  // then we visit these nodes in reverse order, flattening as needed. We
  // early-out if we get to a node whose target node is the destination, since
  // we can then re-use the target space transform stored at that node. However,
  // we cannot re-use a stored target space transform if the destination has a
  // zero surface contents scale, since stored target space transforms have
  // surface contents scale baked in, but we need to compute an unscaled
  // transform.
  std::vector<int> source_to_destination;
  source_to_destination.push_back(current.id);
  const TransformNode* current_node =
      HasParent(current) ? &parent(current) : nullptr;
  for (; current_node && current_node->id > dest_id;
       current_node = HasParent(*current_node) ? &parent(*current_node)
                                               : nullptr) {
    source_to_destination.push_back(current_node->id);
  }

  gfx::Transform combined_transform;
  if (current_node->id < dest_id) {
    // We have reached the lowest common ancestor of the source and destination
    // nodes. This case can occur when we are transforming between a node
    // corresponding to a fixed-position layer (or its descendant) and the node
    // corresponding to the layer's render target. For example, consider the
    // layer tree R->T->S->F where F is fixed-position, S owns a render surface,
    // and T has a significant transform. This will yield the following
    // transform tree:
    //    R
    //    |
    //    T
    //   /|
    //  S F
    // In this example, T will have id 2, S will have id 3, and F will have id
    // 4. When walking up the ancestor chain from F, the first node with a
    // smaller id than S will be T, the lowest common ancestor of these nodes.
    // We compute the transform from T to S here, and then from F to T in the
    // loop below.
    DCHECK(IsDescendant(dest_id, current_node->id));
    CombineInversesBetween(current_node->id, dest_id, &combined_transform);
  }

  size_t source_to_destination_size = source_to_destination.size();
  for (size_t i = 0; i < source_to_destination_size; ++i) {
    size_t index = source_to_destination_size - 1 - i;
    const TransformNode& node = Node(source_to_destination[index]);
    if (node.flattens_inherited_transform) {
      combined_transform.Flatten();
    }
    combined_transform.PreConcat(node.to_parent);
  }

  transform->PostConcat(combined_transform);
}

bool TransformTree::CombineInversesBetween(int source_id,
                                           int dest_id,
                                           gfx::Transform* transform) const {
  DCHECK(source_id < dest_id);
  const TransformNode& current = Node(dest_id);
  const TransformNode& dest = Node(source_id);
  // Just as in CombineTransformsBetween, we can use screen space transforms in
  // this computation only when there isn't any non-trivial flattening
  // involved.
  if (current.ancestors_are_invertible && current.node_and_ancestors_are_flat) {
    transform->PreConcat(FromScreen(current.id));
    transform->PreConcat(ToScreen(dest.id));
    return true;
  }

  // Inverting a flattening is not equivalent to flattening an inverse. This
  // means we cannot, for example, use the inverse of each node's to_parent
  // transform, flattening where needed. Instead, we must compute the transform
  // from the destination to the source, with flattening, and then invert the
  // result.
  gfx::Transform dest_to_source;
  CombineTransformsBetween(dest_id, source_id, &dest_to_source);
  gfx::Transform source_to_dest;
  bool all_are_invertible = dest_to_source.GetInverse(&source_to_dest);
  transform->PreConcat(source_to_dest);
  return all_are_invertible;
}

bool TransformTree::SetDrawnElasticOverscroll(
    ElementId id,
    const gfx::Vector2dF& elastic_overscroll) {
  if (elastic_overscroll.IsZero()) {
    return drawn_elastic_overscroll_.erase(id) != 0;
  }
  gfx::Vector2dF& current_overscroll = drawn_elastic_overscroll_[id];
  bool changed = current_overscroll != elastic_overscroll;
  current_overscroll = elastic_overscroll;
  return changed;
}

gfx::Vector2dF TransformTree::GetDrawnElasticOverscroll(ElementId id) const {
  auto it = drawn_elastic_overscroll_.find(id);
  if (it == drawn_elastic_overscroll_.end()) {
    return gfx::Vector2dF();
  }
  return it->second;
}

std::pair<ElementId, gfx::Vector2dF>
TransformTree::FindDrawnElasticOverscrollFromTransformId(
    int transform_id,
    const ViewportPropertyIds* viewport_property_ids) const {
  // TODO(crbug.com/465422599): Optimize this to use the `ElementId` directly
  // from the `TransformNode` to do a direct lookup instead of doing a search.
  // This will require updating the scroll translation transform node to use the
  // same compositor element id as the scroll node.
  const auto& scroll_tree = property_trees()->scroll_tree();
  if (viewport_property_ids &&
      transform_id == viewport_property_ids->overscroll_elasticity_transform) {
    if (viewport_property_ids->inner_scroll != kInvalidPropertyNodeId) {
      const ScrollNode& scroll_node =
          scroll_tree.Node(viewport_property_ids->inner_scroll);
      if (auto it = drawn_elastic_overscroll_.find(scroll_node.element_id);
          it != drawn_elastic_overscroll_.end()) {
        return {it->first, it->second};
      }
    }
  } else {
    // Iterate over the small set of elastic overscroll elements instead of all
    // scroll nodes.
    for (const auto& [element_id, stretch_amount] : drawn_elastic_overscroll_) {
      if (const ScrollNode* scroll_node =
              scroll_tree.FindNodeFromElementId(element_id)) {
        if (scroll_node->transform_id == transform_id) {
          return {element_id, stretch_amount};
        }
      }
    }
  }

  return {ElementId{}, gfx::Vector2dF{}};
}

// This function should match the offset we set for sticky position layer in
// blink::LayoutBoxModelObject::StickyPositionOffset.
gfx::Vector2dF TransformTree::StickyPositionOffset(const TransformNode& node) {
  StickyPositionNodeData* sticky_data = MutableStickyPositionData(node.id);
  if (!sticky_data) {
    return gfx::Vector2dF();
  }
  const StickyPositionConstraint& constraint = sticky_data->constraints;

  const ScrollNode* scroll_node_x = nullptr;
  if (sticky_data->x_scroll_ancestor != kInvalidPropertyNodeId) {
    scroll_node_x =
        &property_trees()->scroll_tree().Node(sticky_data->x_scroll_ancestor);
  }
  const ScrollNode* scroll_node_y = nullptr;
  if (sticky_data->y_scroll_ancestor != kInvalidPropertyNodeId) {
    scroll_node_y =
        &property_trees()->scroll_tree().Node(sticky_data->y_scroll_ancestor);
  }

  const TransformNode* transform_node_x = nullptr;
  if (scroll_node_x && scroll_node_x->transform_id != kInvalidPropertyNodeId) {
    transform_node_x = &Node(scroll_node_x->transform_id);
  }
  const TransformNode* transform_node_y = nullptr;
  if (scroll_node_y && scroll_node_y->transform_id != kInvalidPropertyNodeId) {
    transform_node_y = &Node(scroll_node_y->transform_id);
  }
  DCHECK(transform_node_x || transform_node_y);

  // We need the scroll offset from the transform tree, not the scroll tree.
  // Tracking the scroll tree here would make sticky elements run "ahead" of a
  // main-repainted scroll.
  gfx::PointF scroll_position;
  gfx::Vector2dF snap_offset;
  if (transform_node_x) {
    scroll_position.set_x(transform_node_x->scroll_offset().x());
    snap_offset.set_x(transform_node_x->snap_amount.x());
  }
  if (transform_node_y) {
    scroll_position.set_y(transform_node_y->scroll_offset().y());
    snap_offset.set_y(transform_node_y->snap_amount.y());
  }
  scroll_position -= snap_offset;

  // The clip region may need to be offset by the outer viewport bounds, e.g. if
  // the top bar hides/shows. Position sticky should never attach to the inner
  // viewport since it shouldn't be affected by pinch-zoom.
  gfx::Vector2dF constraint_box_expansion;
  if (scroll_node_x) {
    DCHECK(!scroll_node_x->scrolls_inner_viewport);
    if (scroll_node_x->scrolls_outer_viewport) {
      constraint_box_expansion.set_x(
          property_trees()->outer_viewport_container_bounds_delta().x());
    }
  }
  if (scroll_node_y) {
    DCHECK(!scroll_node_y->scrolls_inner_viewport);
    if (scroll_node_y->scrolls_outer_viewport) {
      constraint_box_expansion.set_y(
          property_trees()->outer_viewport_container_bounds_delta().y());
    }
  }

  // Used to find shifting ancestors that affect this sticky element itself
  // (sticky box) and its "cage" (containing block).
  auto get_ancestor =
      [&](int transform_node_id) -> const StickyPositionNodeData* {
    if (transform_node_id == kInvalidPropertyNodeId) {
      return nullptr;
    }
    // TODO(crbug.com/40053373): Investigate why there would be an invalid index
    // passed in. Early return for now.
    if (transform_node_id >=
        static_cast<int>(property_trees()->transform_tree().size())) {
      return nullptr;
    }
    const StickyPositionNodeData* ancestor_data =
        GetStickyPositionData(transform_node_id);
    DCHECK(ancestor_data);
    return ancestor_data;
  };

  // Ancestor sticky elements between the element itself, and its containing
  // block can apply additional dynamic offsets.
  gfx::Vector2dF ancestor_sticky_box_offset;
  if (const StickyPositionNodeData* ancestor_sticky_data =
          get_ancestor(sticky_data->nearest_node_shifting_sticky_box)) {
    // Only shifting sticky ancestors that share the same scroll ancestor for a
    // given axis need to be applied.
    if (ancestor_sticky_data->x_scroll_ancestor ==
        sticky_data->x_scroll_ancestor) {
      ancestor_sticky_box_offset.set_x(
          ancestor_sticky_data->total_sticky_box_sticky_offset.x());
    }
    if (ancestor_sticky_data->y_scroll_ancestor ==
        sticky_data->y_scroll_ancestor) {
      ancestor_sticky_box_offset.set_y(
          ancestor_sticky_data->total_sticky_box_sticky_offset.y());
    }
  }

  // Ancestor sticky elements between the element's containing block, and
  // containing scroll container can apply additional dynamic offsets.
  gfx::Vector2dF ancestor_containing_block_offset;
  if (const StickyPositionNodeData* ancestor_sticky_data =
          get_ancestor(sticky_data->nearest_node_shifting_containing_block)) {
    // Only shifting sticky ancestors that share the same scroll ancestor for a
    // given axis need to be applied.
    if (ancestor_sticky_data->x_scroll_ancestor ==
        sticky_data->x_scroll_ancestor) {
      ancestor_containing_block_offset.set_x(
          ancestor_sticky_data->total_containing_block_sticky_offset.x());
    }
    if (ancestor_sticky_data->y_scroll_ancestor ==
        sticky_data->y_scroll_ancestor) {
      ancestor_containing_block_offset.set_y(
          ancestor_sticky_data->total_containing_block_sticky_offset.y());
    }
  }

  gfx::Vector2dF sticky_offset = constraint.StickyPositionOffset(
      scroll_position, constraint_box_expansion, ancestor_sticky_box_offset,
      ancestor_containing_block_offset);

  sticky_data->total_sticky_box_sticky_offset =
      ancestor_sticky_box_offset + sticky_offset;
  sticky_data->total_containing_block_sticky_offset =
      ancestor_sticky_box_offset + ancestor_containing_block_offset +
      sticky_offset;

  return gfx::ToRoundedVector2d(sticky_offset + constraint.pixel_snap_offset);
}

AnchorPositionScrollData& TransformTree::EnsureAnchorPositionScrollData(
    int node_id) {
  TransformNode& node = MutableNode(node_id);
  if (node.anchor_position_scroll_data_id == -1 ||
      static_cast<size_t>(node.anchor_position_scroll_data_id) >=
          anchor_position_scroll_data_.size()) {
    node.anchor_position_scroll_data_id = anchor_position_scroll_data_.size();
    anchor_position_scroll_data_.emplace_back();
  }
  return anchor_position_scroll_data_[node.anchor_position_scroll_data_id];
}

const AnchorPositionScrollData* TransformTree::GetAnchorPositionScrollData(
    int node_id) const {
  const TransformNode& node = Node(node_id);
  if (node.anchor_position_scroll_data_id == -1 ||
      static_cast<size_t>(node.anchor_position_scroll_data_id) >=
          anchor_position_scroll_data_.size()) {
    return nullptr;
  }
  return &anchor_position_scroll_data_[node.anchor_position_scroll_data_id];
}

gfx::Vector2dF TransformTree::AnchorPositionOffset(
    const TransformNode& node,
    int max_updated_node_id,
    UpdateTransformsData* update_data,
    base::flat_set<int>& visited) {
  if (visited.contains(node.id)) {
    return gfx::Vector2dF();
  }
  visited.insert(node.id);

  const AnchorPositionScrollData* data = GetAnchorPositionScrollData(node.id);
  if (!data) {
    return gfx::Vector2dF();
  }

  // `update_data` can be null if UpdateTransforms() is called from
  // PropertyTreeBuilder (for layer tree mode for ui), but we should not have
  // anchor position in chrome ui.
  CHECK(update_data);

  auto get_transformed_offset = [&](gfx::Vector2dF offset,
                                    int container_transform_id) {
    if (offset.IsZero()) {
      return offset;
    }
    gfx::Transform mapper = ToScreen(container_transform_id);
    mapper.PostConcat(FromScreen(node.parent_id));
    gfx::PointF transformed_offset =
        mapper.MapPoint(gfx::PointF(offset.x(), offset.y()));
    return transformed_offset - mapper.MapPoint(gfx::PointF());
  };

  gfx::Vector2dF accumulated_offset(0, 0);
  for (ElementId container_id : data->adjustment_container_ids) {
    int container_transform_id = kInvalidNodeId;
    if (const ScrollNode* scroll_node =
            property_trees()->scroll_tree().FindNodeFromElementId(
                container_id)) {
      container_transform_id = scroll_node->transform_id;
      const TransformNode& transform_node = Node(container_transform_id);
      // We don't ever expect that an anchor node or any of its scrolling
      // containers should have an invalid transform_id.
      DCHECK(container_transform_id != kInvalidPropertyNodeId);
      accumulated_offset += get_transformed_offset(
          transform_node.scroll_offset().OffsetFromOrigin(),
          transform_node.parent_id);
      // TODO(crbug.com/325613705): Should we consider snap_amount here?
    } else if (TransformNode* container_transform =
                   property_trees()
                       ->transform_tree_mutable()
                       .MutableFindNodeFromElementId(container_id)) {
      container_transform_id = container_transform->id;
      gfx::Vector2dF adjustment = StickyPositionOffset(*container_transform);
      // Adjust for chained anchor positioned offset.
      adjustment += AnchorPositionOffset(
          *container_transform, max_updated_node_id, update_data, visited);

      accumulated_offset -=
          get_transformed_offset(adjustment, container_transform_id);
    }
    if (container_transform_id > max_updated_node_id) {
      // The adjustment depends on a later transform node that may contain
      // stale data. See UpdateAllTransforms() and UpdateTransforms() for how
      // stale forward dependencies are handled.
      update_data->stale_forward_dependencies.insert(container_transform_id);
    }
  }
  gfx::Vector2dF result = data->accumulated_scroll_origin - accumulated_offset;
  if (!data->needs_scroll_adjustment_in_x) {
    result.set_x(0);
  }
  if (!data->needs_scroll_adjustment_in_y) {
    result.set_y(0);
  }
  return result;
}

void TransformTree::UndoOverscroll(
    const TransformNode& node,
    gfx::Vector2dF& position_adjustment,
    const ViewportPropertyIds* viewport_property_ids) {
  DCHECK(node.should_undo_overscroll);

  const int transform_id =
      viewport_property_ids
          ? viewport_property_ids->overscroll_elasticity_transform
          : kInvalidPropertyNodeId;
  if (transform_id == kInvalidPropertyNodeId)
    return;

  const int clip_id = viewport_property_ids ? viewport_property_ids->outer_clip
                                            : kInvalidPropertyNodeId;
  if (clip_id == kInvalidPropertyNodeId)
    return;

  const gfx::Vector2dF overscroll_offset =
      FindDrawnElasticOverscrollFromTransformId(transform_id,
                                                viewport_property_ids)
          .second;
  if (overscroll_offset.IsZero())
    return;

  position_adjustment +=
      MathUtil::ScaleVectorByInverse(overscroll_offset, page_scale_factor());

  ClipTree& clip_tree = property_trees()->clip_tree_mutable();
  ClipNode& clip_node = clip_tree.MutableNode(clip_id);

  // Inflate the clip rect based on the overscroll direction.
  gfx::OutsetsF outsets;
  position_adjustment.x() < 0 ? outsets.set_left(-position_adjustment.x())
                              : outsets.set_right(position_adjustment.x());
  position_adjustment.y() < 0 ? outsets.set_top(-position_adjustment.y())
                              : outsets.set_bottom(position_adjustment.y());
  clip_node.clip.Outset(outsets);
  clip_tree.set_needs_update(true);
}

namespace {
[[maybe_unused]] void ApplyElasticOverscrollStretch(
    const ScrollTree& scroll_tree,
    float page_scale_factor,
    const std::pair<ElementId, gfx::Vector2dF>& elastic_overscroll,
    gfx::Transform* transform) {
  const ScrollNode* scroll_node =
      scroll_tree.FindNodeFromElementId(elastic_overscroll.first);

  // Early out if node is invalid, bounds are empty, or there is no overscroll.
  if (!scroll_node || scroll_tree.container_bounds(scroll_node->id).IsEmpty() ||
      elastic_overscroll.second.IsZero()) {
    return;
  }

  // The inner viewport container size takes into account the size change as a
  // result of the top controls, see ScrollTree::container_bounds.
  const gfx::Size scroller_size = scroll_tree.container_bounds(scroll_node->id);

  // On Android, elastic overscroll is implemented by stretching the content
  // from the overscrolled edge by applying a stretch transform.
  const gfx::Vector2dF scale_factor(
      1.f + std::abs(elastic_overscroll.second.x()) / scroller_size.width(),
      1.f + std::abs(elastic_overscroll.second.y()) / scroller_size.height());

  // If overscrolling to the right, stretch from right.
  gfx::PointF pivot;
  if (elastic_overscroll.second.x() > 0.f) {
    pivot.set_x(scroller_size.width());
  }

  // If overscrolling off the bottom, stretch from bottom.
  if (elastic_overscroll.second.y() > 0.f) {
    pivot.set_y(scroller_size.height());
  }

  // Convert pivot to content space if this is the inner viewport.
  if (scroll_node->scrolls_inner_viewport) {
    pivot = MathUtil::ScalePointByInverse(pivot, page_scale_factor);
  }

  // Apply transform: Translate(Pivot) -> Scale -> Translate(-Pivot).
  transform->Translate(pivot.OffsetFromOrigin());
  transform->Scale(scale_factor.x(), scale_factor.y());
  transform->Translate(-pivot.OffsetFromOrigin());
}
[[maybe_unused]] void ApplyElasticOverscrollTranslate(
    const ScrollTree&,
    float,
    const std::pair<ElementId, gfx::Vector2dF>& elastic_overscroll,
    gfx::Transform* transform) {
  transform->Translate(-elastic_overscroll.second.x(),
                       -elastic_overscroll.second.y());
}
}  // namespace

void TransformTree::UpdateLocalTransform(
    TransformNode* node,
    const ViewportPropertyIds* viewport_property_ids,
    UpdateTransformsData* update_data) {
  gfx::Transform transform;
  transform.Translate3d(node->post_translation.x() + node->origin.x(),
                        node->post_translation.y() + node->origin.y(),
                        node->origin.z());

  float y_adjustment = 0.f;
  if (node->moved_by_outer_viewport_bounds_delta_y) {
    y_adjustment +=
        property_trees()->outer_viewport_container_bounds_delta().y();
  }
  if (node->moved_by_safe_area_bottom) {
    y_adjustment +=
        property_trees()->transform_delta_by_safe_area_inset_bottom();
  }
  gfx::Vector2dF position_adjustment(0.f, y_adjustment);

  // Android does a stretch effect instead of translation - since we cannot do
  // a simple translation to undo the root elastic overscroll effect -
  // on Android we simply skip this.
#if !BUILDFLAG(IS_ANDROID)
  if (node->should_undo_overscroll) {
    UndoOverscroll(*node, position_adjustment, viewport_property_ids);
  }
#endif
  transform.Translate(position_adjustment);

  const std::pair<ElementId, gfx::Vector2dF> elastic_overscroll =
      FindDrawnElasticOverscrollFromTransformId(node->id,
                                                viewport_property_ids);

  if (!elastic_overscroll.second.IsZero()) {
    const auto& scroll_tree = property_trees()->scroll_tree();
#if BUILDFLAG(IS_ANDROID)

    ApplyElasticOverscrollStretch(scroll_tree, page_scale_factor(),
                                  elastic_overscroll, &transform);
#else
    ApplyElasticOverscrollTranslate(scroll_tree, page_scale_factor(),
                                    elastic_overscroll, &transform);
#endif
  }

  // Apply scroll translate after elastic stretch so that the origin for
  // stretching from the bottom / right is correct.
  transform.Translate(-node->scroll_offset().OffsetFromOrigin());

  transform.Translate(StickyPositionOffset(*node));
  if (node->anchor_position_scroll_data_id >= 0) {
    base::flat_set<int> visited;
    transform.Translate(
        AnchorPositionOffset(*node, node->id - 1, update_data, visited));
    // Make sure the damage rect is tracked.
    node->SetTransformChanged(DamageReason::kUntracked);
  }
  transform.PreConcat(node->local);
  transform.Translate3d(gfx::Point3F() - node->origin);

  node->set_to_parent(transform);
  node->needs_local_transform_update = false;
}

void TransformTree::UpdateScreenSpaceTransform(
    TransformNode* node,
    const TransformNode& parent_node) {
  gfx::Transform to_screen_space_transform = ToScreen(parent_node.id);
  if (node->flattens_inherited_transform) {
    to_screen_space_transform.Flatten();
  }
  to_screen_space_transform.PreConcat(node->to_parent);
  node->ancestors_are_invertible = parent_node.ancestors_are_invertible;
  node->node_and_ancestors_are_flat =
      parent_node.node_and_ancestors_are_flat && node->to_parent.IsFlat();
  SetToScreen(node->id, to_screen_space_transform);

  gfx::Transform from_screen;
  if (!ToScreen(node->id).GetInverse(&from_screen)) {
    node->ancestors_are_invertible = false;
  }
  SetFromScreen(node->id, from_screen);
}

void TransformTree::UpdateAnimationProperties(
    TransformNode* node,
    const TransformNode& parent_node) {
  bool ancestor_is_animating = false;
  ancestor_is_animating = parent_node.to_screen_is_potentially_animated;
  node->to_screen_is_potentially_animated =
      node->has_potential_animation || ancestor_is_animating;
}

void TransformTree::UndoSnapping(TransformNode* node) {
  // to_parent transform has snapping from previous frame baked in.
  // We need to undo it and use the un-snapped transform to compute current
  // target and screen space transforms.
  node->to_parent.Translate(-node->snap_amount.x(), -node->snap_amount.y());
  node->snap_amount = gfx::Vector2dF();
}

void TransformTree::UpdateSnapping(TransformNode* node) {
  if (!node->should_be_snapped || node->to_screen_is_potentially_animated ||
      !ToScreen(node->id).IsScaleOrTranslation() ||
      !node->ancestors_are_invertible) {
    return;
  }

  // Snapping must be done in target space (the pixels we care about) and then
  // the render pass should also be snapped if necessary. But, we do it in
  // screen space because it is easier and works most of the time if there is
  // no intermediate render pass with a snap-destrying transform. If ST is the
  // screen space transform and ST' is ST with its translation components
  // rounded, then what we're after is the scroll delta X, where ST * X = ST'.
  // I.e., we want a transform that will realize our snap. It follows that
  // X = ST^-1 * ST'. We cache ST and ST^-1 to make this more efficient.
  DCHECK_LT(node->id, static_cast<int>(cached_data_.size()));
  gfx::Transform& to_screen = cached_data_[node->id].to_screen;
  to_screen.Round2dTranslationComponents();
  gfx::Transform& from_screen = cached_data_[node->id].from_screen;
  gfx::Transform delta = from_screen;
  delta *= to_screen;

  constexpr float kTolerance = 1e-4f;
  DCHECK(delta.IsApproximatelyIdentityOrTranslation(kTolerance))
      << delta.ToString();

  gfx::Vector2dF translation = delta.To2dTranslation();
  node->snap_amount = translation;
  if (translation.IsZero())
    return;

  from_screen.PostTranslate(-translation);
  node->to_parent.Translate(translation);
  // Avoid accumulation of errors in to_parent.
  if (node->to_parent.IsApproximatelyIdentityOrIntegerTranslation(kTolerance))
    node->to_parent.RoundToIdentityOrIntegerTranslation();
}

void TransformTree::UpdateTransformChanged(TransformNode* node,
                                           const TransformNode& parent_node) {
  if (parent_node.transform_changed()) {
    node->CopyTransformChangedFrom(parent_node);
  }
}

void TransformTree::UpdateNodeAndAncestorsAreAnimatedOrInvertible(
    TransformNode* node,
    const TransformNode& parent_node) {
  if (!parent_node.node_and_ancestors_are_animated_or_invertible) {
    node->node_and_ancestors_are_animated_or_invertible = false;
    return;
  }
  bool is_invertible = node->is_invertible;
  // Even when the current node's transform and the parent's screen space
  // transform are invertible, the current node's screen space transform can
  // become uninvertible due to floating-point arithmetic.
  if (!node->ancestors_are_invertible && parent_node.ancestors_are_invertible) {
    is_invertible = false;
  }
  node->node_and_ancestors_are_animated_or_invertible =
      node->has_potential_animation || is_invertible;
}

void TransformTree::UpdateNodeOrAncestorsWillChangeTransform(
    TransformNode* node,
    const TransformNode& parent_node) {
  node->node_or_ancestors_will_change_transform = node->will_change_transform;
  node->node_or_ancestors_will_change_transform |=
      parent_node.node_or_ancestors_will_change_transform;
}

void TransformTree::SetRootScaleAndTransform(
    float device_scale_factor,
    const gfx::Transform& device_transform) {
  device_scale_factor_ = device_scale_factor;
  gfx::Vector2dF device_transform_scale_components =
      gfx::ComputeTransform2dScaleComponents(device_transform, 1.f);

  // Not handling the rare case of different x and y device scale.
  device_transform_scale_factor_ =
      std::max(device_transform_scale_components.x(),
               device_transform_scale_components.y());

  // Let DT be the device transform and DSF be the matrix scaled by (device
  // scale factor * page scale factor for root). Let Screen Space Scale(SSS) =
  // scale component of DT*DSF. The screen space transform of the root
  // transform node is set to SSS and the post local transform of the contents
  // root node is set to SSS^-1*DT*DSF.
  gfx::Transform transform = device_transform;
  transform.Scale(device_scale_factor, device_scale_factor);
  gfx::Vector2dF screen_space_scale =
      gfx::ComputeTransform2dScaleComponents(transform, device_scale_factor);
  DCHECK_NE(screen_space_scale.x(), 0.f);
  DCHECK_NE(screen_space_scale.y(), 0.f);

  gfx::Transform root_to_screen;
  root_to_screen.Scale(screen_space_scale.x(), screen_space_scale.y());
  gfx::Transform root_from_screen = root_to_screen.GetCheckedInverse();
  if (root_to_screen != ToScreen(kRootPropertyNodeId)) {
    SetToScreen(kRootPropertyNodeId, root_to_screen);
    SetFromScreen(kRootPropertyNodeId, root_from_screen);
    set_needs_update(true);
  }

  transform.PostConcat(root_from_screen);
  TransformNode& contents_root_node = MutableNode(kContentsRootPropertyNodeId);
  if (contents_root_node.local != transform) {
    contents_root_node.local = transform;
    contents_root_node.needs_local_transform_update = true;
    set_needs_update(true);
  }
}

void TransformTree::UpdateOuterViewportContainerBoundsDelta() {
  if (nodes_affected_by_outer_viewport_bounds_delta_.empty())
    return;

  set_needs_update(true);
  for (int i : nodes_affected_by_outer_viewport_bounds_delta_)
    MutableNode(i).needs_local_transform_update = true;
}

void TransformTree::AddNodeAffectedByOuterViewportBoundsDelta(int node_id) {
  nodes_affected_by_outer_viewport_bounds_delta_.push_back(node_id);
}

bool TransformTree::HasNodesAffectedByOuterViewportBoundsDelta() const {
  return !nodes_affected_by_outer_viewport_bounds_delta_.empty();
}

void TransformTree::NeedTransformUpdateForSafeAreaInsetBottom() {
  if (nodes_affected_by_safe_area_inset_bottom_.empty()) {
    return;
  }

  set_needs_update(true);
  for (int i : nodes_affected_by_safe_area_inset_bottom_) {
    MutableNode(i).needs_local_transform_update = true;
  }
}

void TransformTree::AddNodeAffectedBySafeAreaInsetBottom(int node_id) {
  nodes_affected_by_safe_area_inset_bottom_.push_back(node_id);
}

bool TransformTree::HasNodesAffectedBySafeAreaBottom() const {
  return !nodes_affected_by_safe_area_inset_bottom_.empty();
}

const gfx::Transform& TransformTree::FromScreen(int node_id) const {
  DCHECK(static_cast<int>(cached_data_.size()) > node_id &&
         node_id != kInvalidPropertyNodeId);
  return cached_data_[node_id].from_screen;
}

void TransformTree::SetFromScreen(int node_id,
                                  const gfx::Transform& transform) {
  DCHECK(static_cast<int>(cached_data_.size()) > node_id &&
         node_id != kInvalidPropertyNodeId);
  cached_data_[node_id].from_screen = transform;
}

const gfx::Transform& TransformTree::ToScreen(int node_id) const {
  DCHECK(static_cast<int>(cached_data_.size()) > node_id &&
         node_id != kInvalidPropertyNodeId);
  return cached_data_[node_id].to_screen;
}

void TransformTree::SetToScreen(int node_id, const gfx::Transform& transform) {
  DCHECK(static_cast<int>(cached_data_.size()) > node_id &&
         node_id != kInvalidPropertyNodeId);
  cached_data_[node_id].to_screen = transform;
  cached_data_[node_id].is_showing_backface = transform.IsBackFaceVisible();
}

#if DCHECK_IS_ON()
bool TransformTree::operator==(const TransformTree& other) const {
  return PropertyTree::operator==(other) &&
         page_scale_factor_ == other.page_scale_factor() &&
         device_scale_factor_ == other.device_scale_factor() &&
         device_transform_scale_factor_ ==
             other.device_transform_scale_factor() &&
         external_page_scale_factor_ == other.external_page_scale_factor() &&
         nodes_affected_by_outer_viewport_bounds_delta_ ==
             other.nodes_affected_by_outer_viewport_bounds_delta() &&
         cached_data_ == other.cached_data() &&
         drawn_elastic_overscroll_ == other.drawn_elastic_overscroll();
}
#endif

StickyPositionNodeData* TransformTree::MutableStickyPositionData(int node_id) {
  const TransformNode& node = Node(node_id);
  if (node.sticky_position_constraint_id == -1 ||
      static_cast<size_t>(node.sticky_position_constraint_id) >=
          sticky_position_data_.size()) {
    return nullptr;
  }
  return &sticky_position_data_[node.sticky_position_constraint_id];
}

StickyPositionNodeData& TransformTree::EnsureStickyPositionData(int node_id) {
  TransformNode& node = MutableNode(node_id);
  if (node.sticky_position_constraint_id == -1 ||
      static_cast<size_t>(node.sticky_position_constraint_id) >=
          sticky_position_data_.size()) {
    node.sticky_position_constraint_id = sticky_position_data_.size();
    sticky_position_data_.emplace_back();
  }
  return sticky_position_data_[node.sticky_position_constraint_id];
}

EffectTree::EffectTree(PropertyTrees* property_trees)
    : PropertyTree<EffectNode>(property_trees) {
  render_surfaces_.push_back(nullptr);
}

EffectTree::~EffectTree() = default;

int EffectTree::Insert(const EffectNode& tree_node, int parent_id) {
  int node_id = PropertyTree<EffectNode>::Insert(tree_node, parent_id);
  DCHECK_EQ(node_id, static_cast<int>(render_surfaces_.size()));

  render_surfaces_.push_back(nullptr);
  return node_id;
}

void EffectTree::RemoveNodes(size_t n) {
  PropertyTree<EffectNode>::RemoveNodes(n);
  render_surfaces_.resize(render_surfaces_.size() - n);
}

void EffectTree::clear() {
  PropertyTree<EffectNode>::clear();
  render_surfaces_.clear();
  render_surfaces_.push_back(nullptr);

#if DCHECK_IS_ON()
  EffectTree tree;
  DCHECK(tree == *this);
#endif
}

float EffectTree::EffectiveOpacity(const EffectNode& node) const {
  return node.subtree_hidden ? 0.f : node.opacity;
}

void EffectTree::UpdateOpacities(EffectNode* node,
                                 const EffectNode* parent_node) {
  node->screen_space_opacity = EffectiveOpacity(*node);

  if (parent_node) {
    node->screen_space_opacity *= parent_node->screen_space_opacity;
  }
}

void EffectTree::UpdateSubtreeHidden(EffectNode* node,
                                     const EffectNode* parent_node) {
  if (parent_node) {
    node->subtree_hidden |= parent_node->subtree_hidden;
  }
}

void EffectTree::UpdateIsDrawn(EffectNode* node,
                               const EffectNode* parent_node) {
  // Nodes that have screen space opacity 0 are hidden. So they are not drawn.
  // Exceptions:
  // 1) Nodes that contribute to copy requests, whether hidden or not, must be
  //    drawn.
  // 2) Nodes that have a valid SubtreeCaptureId, must be drawn so that they can
  //    be captured by the FrameSinkVideoCapturer.
  // 3) Nodes that have a backdrop filter.
  // 4) Nodes with animating screen space opacity on main thread or pending tree
  //    are drawn if their parent is drawn irrespective of their opacity.
  if (node->has_copy_request || node->cache_render_surface ||
      node->subtree_capture_id.is_valid()) {
    node->is_drawn = true;
  } else if (EffectiveOpacity(*node) == 0.f &&
             (!node->has_potential_opacity_animation ||
              property_trees()->is_active()) &&
             node->backdrop_filters.IsEmpty()) {
    node->is_drawn = false;
  } else if (parent_node) {
    node->is_drawn = parent_node->is_drawn;
  } else {
    node->is_drawn = true;
  }
}

void EffectTree::UpdateEffectChanged(EffectNode* node,
                                     const EffectNode* parent_node) {
  if (parent_node && parent_node->effect_changed) {
    node->effect_changed = true;
  }
}

void EffectTree::UpdateHasFilters(EffectNode* node,
                                  const EffectNode* parent_node) {
  node->lcd_text_disallowed_by_filter =
      node->has_potential_filter_animation || !node->filters.AllowsLCDText();
  if (parent_node) {
    node->lcd_text_disallowed_by_filter |=
        parent_node->lcd_text_disallowed_by_filter;
  }
}

void EffectTree::UpdateHasFastRoundedCorner(EffectNode* node,
                                            const EffectNode* parent_node) {
  node->node_or_ancestor_has_fast_rounded_corner = node->is_fast_rounded_corner;
  if (parent_node) {
    node->node_or_ancestor_has_fast_rounded_corner |=
        parent_node->node_or_ancestor_has_fast_rounded_corner;
  }
}

void EffectTree::UpdateBackfaceVisibility(EffectNode* node,
                                          const EffectNode* parent_node) {
  if (parent_node && parent_node->hidden_by_backface_visibility) {
    node->hidden_by_backface_visibility = true;
    return;
  }
  if (node->double_sided) {
    node->hidden_by_backface_visibility = false;
    return;
  }
  node->hidden_by_backface_visibility = property_trees()
                                            ->transform_tree()
                                            .cached_data()[node->transform_id]
                                            .is_showing_backface;
}

void EffectTree::UpdateHasMaskingChild(EffectNode* node,
                                       EffectNode* parent_node) {
  // Reset to false when a node is first met. We'll set the bit later
  // when we actually encounter a masking child.
  node->has_masking_child = false;
  if (node->blend_mode == SkBlendMode::kDstIn && parent_node) {
    parent_node->has_masking_child = true;
  }
}

void EffectTree::UpdateOnlyDrawsVisibleContent(EffectNode* node,
                                               const EffectNode* parent_node) {
  node->only_draws_visible_content =
      !node->has_copy_request && !node->subtree_capture_id.is_valid() &&
      !node->view_transition_element_resource_id.IsValid();
  if (parent_node) {
    node->only_draws_visible_content &= parent_node->only_draws_visible_content;
  }
  if (!node->backdrop_filters.IsEmpty()) {
    node->only_draws_visible_content &=
        !node->backdrop_filters.HasFilterOfType(FilterOperation::ZOOM);
  }
}

void EffectTree::UpdateSurfaceContentsScale(EffectNode* effect_node) {
  if (!effect_node->HasRenderSurface()) {
    effect_node->surface_contents_scale = gfx::Vector2dF(1.0f, 1.0f);
    return;
  }

  const TransformTree& transform_tree = property_trees()->transform_tree();
  float layer_scale_factor = transform_tree.device_scale_factor() *
                             transform_tree.device_transform_scale_factor();
  const TransformNode& transform_node =
      transform_tree.Node(effect_node->transform_id);
  if (transform_node.in_subtree_of_page_scale_layer) {
    layer_scale_factor *= transform_tree.page_scale_factor();
  }

  const gfx::Vector2dF old_scale = effect_node->surface_contents_scale;
  effect_node->surface_contents_scale = gfx::ComputeTransform2dScaleComponents(
      transform_tree.ToScreen(transform_node.id), layer_scale_factor);

  // external_page_scale_factor is the embedder's magnification of this OOPIF
  // (like page_scale_factor for the main frame): it raises raster/backing
  // resolution, not on-screen geometry. surface_contents_scale is a backing
  // resolution too, so scaling it here only sharpens the effect surface's
  // backing without changing where or how large it draws. Do this for non-root
  // effect surfaces (mirroring PictureLayerImpl::UpdateIdealScales) so their
  // backing matches raster density; otherwise the crisp tiles are downsampled
  // into an un-magnified backing and upsampled when composited, blurring text.
  // The root surface is left un-magnified: it defines the OOPIF's submitted
  // frame size, which the embedder magnifies.
  if (effect_node->id != kContentsRootPropertyNodeId &&
      base::FeatureList::IsEnabled(
          features::kSizeOopifEffectSurfacesAtExternalScale)) {
    effect_node->surface_contents_scale.Scale(
        transform_tree.external_page_scale_factor());
  }

  // To avoid seams we apply only scale as draw transform instead of raster
  // content transform.
  if (effect_node->render_surface_reason ==
      RenderSurfaceReason::k2DScaleTransformWithCompositedDescendants) {
    // We raster at closest positive integer scale and then apply the rest as
    // the draw transform, e.g scale 3.5 will rastered at 4 and 0.875 (3.5/4)
    // will be applied as draw transform.
    effect_node->surface_contents_scale.set_x(
        std::ceil(std::abs(effect_node->surface_contents_scale.x())));
    effect_node->surface_contents_scale.set_y(
        std::ceil(std::abs(effect_node->surface_contents_scale.y())));
  }

  // If surface contents scale changes, draw transforms are no longer valid.
  // Invalidates the draw transform cache and updates the clip for the surface.
  if (old_scale != effect_node->surface_contents_scale) {
    property_trees()->clip_tree_mutable().set_needs_update(true);
    property_trees()->UpdateTransformTreeUpdateNumber();
  }
}

bool EffectTree::OnOpacityAnimated(ElementId id, float opacity) {
  EffectNode* node = MutableFindNodeFromElementId(id);
  // TODO(crbug.com/40828469): Remove this when we no longer animate
  // non-existent nodes.
  if (!node) {
    return false;
  }
  if (node->opacity == opacity)
    return false;
  node->opacity = opacity;
  node->effect_changed = true;
  property_trees()->set_changed(true);
  property_trees()->effect_tree_mutable().set_needs_update(true);
  return true;
}

bool EffectTree::OnFilterAnimated(ElementId id,
                                  const FilterOperations& filters) {
  EffectNode* node = MutableFindNodeFromElementId(id);
  // TODO(crbug.com/40828469): Remove this when we no longer animate
  // non-existent nodes.
  if (!node) {
    return false;
  }
  if (node->filters == filters)
    return false;
  node->filters = filters;
  node->effect_changed = true;
  property_trees()->set_changed(true);
  property_trees()->effect_tree_mutable().set_needs_update(true);
  return true;
}

bool EffectTree::OnBackdropFilterAnimated(
    ElementId id,
    const FilterOperations& backdrop_filters) {
  EffectNode* node = MutableFindNodeFromElementId(id);
  // TODO(crbug.com/40828469): Remove this when we no longer animate
  // non-existent nodes.
  if (!node) {
    return false;
  }
  if (node->backdrop_filters == backdrop_filters)
    return false;
  node->backdrop_filters = backdrop_filters;
  node->effect_changed = true;
  property_trees()->set_changed(true);
  property_trees()->effect_tree_mutable().set_needs_update(true);
  return true;
}

void EffectTree::UpdateEffects(int id) {
  EffectNode& node = MutableNode(id);
  EffectNode* parent_node = HasParent(node) ? &MutableParent(node) : nullptr;

  UpdateOpacities(&node, parent_node);
  UpdateSubtreeHidden(&node, parent_node);
  UpdateIsDrawn(&node, parent_node);
  UpdateEffectChanged(&node, parent_node);
  UpdateHasFilters(&node, parent_node);
  UpdateHasFastRoundedCorner(&node, parent_node);
  UpdateBackfaceVisibility(&node, parent_node);
  UpdateHasMaskingChild(&node, parent_node);
  UpdateOnlyDrawsVisibleContent(&node, parent_node);
  UpdateClosestAncestorSharedElement(&node, parent_node);
  UpdateSurfaceContentsScale(&node);
}

void EffectTree::UpdateClosestAncestorSharedElement(
    EffectNode* node,
    const EffectNode* parent_node) {
  if (node->view_transition_element_resource_id.IsValid()) {
    node->closest_ancestor_with_shared_element_id = node->id;
  } else if (parent_node) {
    node->closest_ancestor_with_shared_element_id =
        parent_node->closest_ancestor_with_shared_element_id;
  }
}

void EffectTree::AddCopyRequest(
    int node_id,
    std::unique_ptr<viz::CopyOutputRequest> request) {
  EffectNode& effect_node = MutableNode(node_id);
  effect_node.has_copy_request = true;
  copy_requests_.insert(std::make_pair(node_id, std::move(request)));
}

void EffectTree::PullCopyRequestsFrom(CopyRequestMap& new_copy_requests) {
  copy_requests_ = std::move(new_copy_requests);
}

void EffectTree::TakeCopyRequestsAndTransformToSurface(
    int node_id,
    std::vector<std::unique_ptr<viz::CopyOutputRequest>>* requests) {
  EffectNode& effect_node = MutableNode(node_id);
  DCHECK(effect_node.HasRenderSurface());
  DCHECK(effect_node.has_copy_request);

  // The area needs to be transformed from the space of content that draws to
  // the surface to the space of the surface itself.
  int destination_id = effect_node.transform_id;
  int source_id;
  if (effect_node.parent_id != kInvalidPropertyNodeId) {
    // For non-root surfaces, transform only by sub-layer scale.
    source_id = destination_id;
  } else {
    // The root surface doesn't have the notion of sub-layer scale, but instead
    // has a similar notion of transforming from the space of the root layer to
    // the space of the screen.
    DCHECK_EQ(kRootPropertyNodeId, destination_id);
    source_id = kContentsRootPropertyNodeId;
  }
  gfx::Transform transform;
  property_trees()->GetToTarget(source_id, node_id, &transform);

  // Move each CopyOutputRequest out of |copy_requests_| and into |requests|,
  // adjusting the source area and scale ratio of each. If the transform is
  // something other than a straightforward translate+scale, the copy requests
  // will be dropped.
  auto range = copy_requests_.equal_range(node_id);
  if (transform.IsPositiveScaleOrTranslation()) {
    // Transform a vector in content space to surface space to determine how the
    // scale ratio of each CopyOutputRequest should be adjusted. Since the scale
    // ratios are provided integer coordinates, the basis vector determines the
    // precision w.r.t. the fractional part of the Transform's scale factors.
    constexpr gfx::Vector2d kContentVector(1024, 1024);
    gfx::RectF surface_rect = transform.MapRect(
        gfx::RectF(0, 0, kContentVector.x(), kContentVector.y()));

    for (auto it = range.first; it != range.second; ++it) {
      viz::CopyOutputRequest* const request = it->second.get();
      if (request->has_area()) {
        // Avoid creating bigger copy area which may contain unnecessary
        // area if the error margin is tiny.
        constexpr float kEpsilon = 0.001f;
        request->set_area(MathUtil::MapEnclosingClippedRectIgnoringError(
            transform, request->area(), kEpsilon));
      }

      // Only adjust the scale ratio if the request specifies one, or if it
      // specifies a result selection. Otherwise, the requestor is expecting a
      // copy of the exact source pixels. If the adjustment to the scale ratio
      // would produce out-of-range values, drop the copy request.
      if (request->is_scaled() || request->has_result_selection()) {
        float scale_from_x_f = request->scale_from().x() * surface_rect.width();
        float scale_from_y_f =
            request->scale_from().y() * surface_rect.height();
        if (std::isnan(scale_from_x_f) ||
            !base::IsValueInRangeForNumericType<int>(scale_from_x_f) ||
            std::isnan(scale_from_y_f) ||
            !base::IsValueInRangeForNumericType<int>(scale_from_y_f)) {
          continue;
        }
        int scale_to_x = request->scale_to().x();
        int scale_to_y = request->scale_to().y();
        if (!base::CheckMul(scale_to_x, kContentVector.x())
                 .AssignIfValid(&scale_to_x) ||
            !base::CheckMul(scale_to_y, kContentVector.y())
                 .AssignIfValid(&scale_to_y)) {
          continue;
        }
        int scale_from_x = base::ClampRound(scale_from_x_f);
        int scale_from_y = base::ClampRound(scale_from_y_f);
        if (scale_from_x <= 0 || scale_from_y <= 0 || scale_to_x <= 0 ||
            scale_to_y <= 0) {
          // Transformed scaling ratio became illegal. Drop the request to
          // provide an empty response.
          continue;
        }
        request->SetScaleRatio(gfx::Vector2d(scale_from_x, scale_from_y),
                               gfx::Vector2d(scale_to_x, scale_to_y));
      }

      requests->push_back(std::move(it->second));
    }
  }
  copy_requests_.erase(range.first, range.second);
}

bool EffectTree::HasCopyRequests() const {
  return !copy_requests_.empty();
}

void EffectTree::ClearCopyRequests() {
  for (auto& node : nodes()) {
    node.subtree_has_copy_request = false;
    node.has_copy_request = false;
    node.closest_ancestor_with_copy_request_id = kInvalidPropertyNodeId;
  }

  // Any copy requests that are still left will be aborted (sending an empty
  // result) on destruction.
  copy_requests_.clear();
  set_needs_update(true);
}

void EffectTree::GetRenderSurfaceChangedFlags(
    std::vector<RenderSurfacePropertyChangedFlags>& flags) const {
  flags.resize(size());
  for (int id = kContentsRootPropertyNodeId; id < static_cast<int>(size());
       ++id) {
    if (render_surfaces_[id])
      flags[id] = render_surfaces_[id]->GetPropertyChangeFlags();
    else
      flags[id] = {false, false};
  }
}

void EffectTree::ApplyRenderSurfaceChangedFlags(
    const std::vector<RenderSurfacePropertyChangedFlags>& flags) {
  if (flags.empty()) {
    return;
  }
  DCHECK_EQ(flags.size(), size());
  for (int id = kContentsRootPropertyNodeId; id < static_cast<int>(size());
       ++id) {
    if (render_surfaces_[id])
      render_surfaces_[id]->ApplyPropertyChangeFlags(flags[id]);
  }
}

int EffectTree::LowestCommonAncestorWithRenderSurface(int id_1,
                                                      int id_2) const {
  DCHECK(GetRenderSurface(id_1));
  DCHECK(GetRenderSurface(id_2));
  while (id_1 != id_2) {
    if (id_1 < id_2)
      id_2 = Node(id_2).target_id;
    else
      id_1 = Node(id_1).target_id;
  }

  return id_1;
}

bool EffectTree::ContributesToDrawnSurface(int id) const {
  // All drawn nodes contribute to drawn surface.
  // Exception : Nodes that are hidden and are drawn only for the sake of
  // copy requests.
  const EffectNode& node = Node(id);
  return node.is_drawn && (!HasParent(node) || parent(node).is_drawn);
}

void EffectTree::ResetChangeTracking() {
  for (int id = kContentsRootPropertyNodeId; id < static_cast<int>(size());
       ++id) {
    MutableNode(id).effect_changed = false;
    // During a flush-only sync (TreesInViz), we skip expensive render surface
    // recomputations, so |render_surfaces_| might be smaller than |size()|.
    if (static_cast<size_t>(id) < render_surfaces_.size() &&
        render_surfaces_[id]) {
      render_surfaces_[id]->ResetPropertyChangedFlags();
    }
  }
}

void EffectTree::TakeRenderSurfaces(
    std::vector<std::unique_ptr<RenderSurfaceImpl>>* render_surfaces) {
  for (int id = kContentsRootPropertyNodeId; id < static_cast<int>(size());
       ++id) {
    if (render_surfaces_[id]) {
      render_surfaces->push_back(std::move(render_surfaces_[id]));
    }
  }
}

bool EffectTree::CreateOrReuseRenderSurfaces(
    std::vector<std::unique_ptr<RenderSurfaceImpl>>* old_render_surfaces,
    LayerTreeImpl* layer_tree_impl) {
  // Make a list of {stable id, node id} pairs for nodes that are supposed to
  // have surfaces.
  std::vector<std::pair<ElementId, int>> stable_id_node_id_list;
  for (int id = kContentsRootPropertyNodeId; id < static_cast<int>(size());
       ++id) {
    EffectNode& node = MutableNode(id);
    if (node.HasRenderSurface()) {
      stable_id_node_id_list.emplace_back(node.element_id, node.id);
    }
  }

  // Sort by stable id so that we can process the two lists cosequentially.
  std::sort(stable_id_node_id_list.begin(), stable_id_node_id_list.end());
  std::sort(old_render_surfaces->begin(), old_render_surfaces->end(),
            [](const std::unique_ptr<RenderSurfaceImpl>& a,
               const std::unique_ptr<RenderSurfaceImpl>& b) {
              return a->id() < b->id();
            });

  bool render_surfaces_changed = false;
  auto surfaces_list_it = old_render_surfaces->begin();
  auto id_list_it = stable_id_node_id_list.begin();
  while (surfaces_list_it != old_render_surfaces->end() &&
         id_list_it != stable_id_node_id_list.end()) {
    if ((*surfaces_list_it)->id() == id_list_it->first) {
      int new_node_id = id_list_it->second;
      render_surfaces_[new_node_id] = std::move(*surfaces_list_it);
      render_surfaces_[new_node_id]->set_effect_tree_index(new_node_id);
      surfaces_list_it++;
      id_list_it++;
      continue;
    }

    render_surfaces_changed = true;

    if (id_list_it->first < (*surfaces_list_it)->id()) {
      int new_node_id = id_list_it->second;
      render_surfaces_[new_node_id] = std::make_unique<RenderSurfaceImpl>(
          layer_tree_impl, id_list_it->first);
      render_surfaces_[new_node_id]->set_effect_tree_index(new_node_id);
      id_list_it++;
    } else {
      surfaces_list_it++;
    }
  }

  if (surfaces_list_it != old_render_surfaces->end() ||
      id_list_it != stable_id_node_id_list.end()) {
    render_surfaces_changed = true;
  }

  while (id_list_it != stable_id_node_id_list.end()) {
    int new_node_id = id_list_it->second;
    render_surfaces_[new_node_id] =
        std::make_unique<RenderSurfaceImpl>(layer_tree_impl, id_list_it->first);
    render_surfaces_[new_node_id]->set_effect_tree_index(new_node_id);
    id_list_it++;
  }

  return render_surfaces_changed;
}

bool EffectTree::ClippedHitTestRegionIsRectangle(int effect_id) const {
  for (int id = effect_id; id != kContentsRootPropertyNodeId;
       id = Node(id).target_id) {
    const EffectNode& effect_node = Node(id);
    gfx::Transform to_target;
    if (!property_trees()->GetToTarget(effect_node.transform_id,
                                       effect_node.target_id, &to_target) ||
        !to_target.Preserves2dAxisAlignment()) {
      return false;
    }
  }
  return true;
}

bool EffectTree::HitTestMayBeAffectedByMask(int effect_id) const {
  for (int id = effect_id; id != kContentsRootPropertyNodeId;
       id = Node(id).parent_id) {
    const EffectNode& effect_node = Node(id);
    if (!effect_node.mask_filter_info.IsEmpty() ||
        effect_node.has_masking_child) {
      return true;
    }
  }
  return false;
}

EffectTree::CopyRequestMap EffectTree::TakeCopyRequests() {
  // Property trees need to get rebuilt since effect nodes (and render surfaces)
  // that were created only for the copy requests we just pushed are no longer
  // needed.
  if (property_trees()->is_main_thread() && !copy_requests_.empty())
    property_trees()->set_needs_rebuild(true);
  return std::move(copy_requests_);
}

ClipTree::ClipTree(PropertyTrees* property_trees)
    : PropertyTree<ClipNode>(property_trees) {}

void ClipTree::SetViewportClip(gfx::RectF viewport_rect) {
  if (size() < 2)
    return;
  ClipNode& node = MutableNode(1);
  if (viewport_rect == node.clip) {
    return;
  }
  node.clip = viewport_rect;
  set_needs_update(true);
}

gfx::RectF ClipTree::ViewportClip() const {
  const size_t min_size = 1;
  DCHECK_GT(size(), min_size);
  return Node(kViewportPropertyNodeId).clip;
}

#if DCHECK_IS_ON()
bool ClipTree::operator==(const ClipTree& other) const {
  return PropertyTree::operator==(other);
}
#endif

EffectTree& EffectTree::operator=(const EffectTree& from) {
  PropertyTree::operator=(from);
  render_surfaces_.resize(size());
  // copy_requests_ are omitted here, since these need to be moved rather
  // than copied or assigned.

  return *this;
}

#if DCHECK_IS_ON()
bool EffectTree::operator==(const EffectTree& other) const {
  return PropertyTree::operator==(other);
}
#endif

ScrollTree::ScrollTree(PropertyTrees* property_trees)
    : PropertyTree<ScrollNode>(property_trees) {}

ScrollTree::~ScrollTree() = default;

ScrollTree& ScrollTree::operator=(const ScrollTree& from) {
  PropertyTree::operator=(from);
  scrolling_contents_cull_rects_ = from.scrolling_contents_cull_rects_;
  if (from.property_trees()->is_main_thread()) {
    scroll_offset_map_ = from.scroll_offset_map_;
  }
  currently_scrolling_node_id_ = kInvalidPropertyNodeId;

  // Remove obsolete overscroll amounts.
  // TODO(crbug.com/430266889): If we have an entry in the map whose node has
  // been removed, there must either be an active overscroll on this node
  // or an ongoing animation of overscroll on this node which should also be
  // cleaned up.
  base::EraseIf(elastic_overscroll_, [&](const auto& pair) {
    const ScrollNode* node = FindNodeFromElementId(pair.first);
    if (!node) {
      return true;
    }
    return !scroll_elasticity_utils::ShouldAllowOverscrollEffect(*node, *this,
                                                                 nullptr);
  });

  // Maps for ScrollOffsets/SyncedScrollOffsets are intentionally omitted here
  // since we can not directly copy them. Pushing of these updates from main
  // currently depends on Layer properties for scroll offset animation changes
  // (setting clobber_active_value for scroll offset animations interrupted on
  // the main thread) being pushed to impl first.
  // |callbacks_| is omitted because it's for the main thread only.
  return *this;
}

#if DCHECK_IS_ON()
bool ScrollTree::operator==(const ScrollTree& other) const {
  if (scroll_offset_map_ != other.scroll_offset_map_)
    return false;
  if (synced_scroll_offset_map_ != other.synced_scroll_offset_map_)
    return false;
  if (callbacks_.get() != other.callbacks_.get())
    return false;

  bool is_currently_scrolling_node_equal =
      currently_scrolling_node_id_ == other.currently_scrolling_node_id_;

  return PropertyTree::operator==(other) && is_currently_scrolling_node_equal;
}

void ScrollTree::CopyCompleteTreeState(const ScrollTree& other) {
  currently_scrolling_node_id_ = other.currently_scrolling_node_id_;
  scroll_offset_map_ = other.scroll_offset_map_;
  synced_scroll_offset_map_ = other.synced_scroll_offset_map_;
  callbacks_ = other.callbacks_;
}
#endif  // DCHECK_IS_ON()

bool ScrollTree::CanRealizeScrollsOnActiveTree(const ScrollNode& node) const {
  return node.transform_id != kInvalidPropertyNodeId && node.is_composited &&
         node.main_thread_repaint_reasons.empty();
}

bool ScrollTree::CanRealizeScrollsOnPendingTree(const ScrollNode& node) const {
  return node.transform_id != kInvalidPropertyNodeId && !node.is_composited &&
         node.main_thread_repaint_reasons.empty();
}

bool ScrollTree::ShouldRealizeScrollsOnMain(const ScrollNode& node) const {
  return node.transform_id != kInvalidPropertyNodeId &&
         !node.main_thread_repaint_reasons.empty();
}

void ScrollTree::clear() {
  PropertyTree<ScrollNode>::clear();

  if (property_trees()->is_main_thread()) {
    currently_scrolling_node_id_ = kInvalidPropertyNodeId;
    scroll_offset_map_.clear();
  }

  scrolling_contents_cull_rects_.clear();

#if DCHECK_IS_ON()
  ScrollTree tree;
  if (property_trees()->is_main_thread()) {
    tree.callbacks_ = callbacks_;
  } else {
    DCHECK(scroll_offset_map_.empty());
    tree.currently_scrolling_node_id_ = currently_scrolling_node_id_;
    tree.synced_scroll_offset_map_ = synced_scroll_offset_map_;
  }
  DCHECK(tree == *this);
#endif
}

gfx::PointF ScrollTree::MaxScrollOffset(int scroll_node_id) const {
  const ScrollNode& scroll_node = Node(scroll_node_id);
  gfx::SizeF scroll_bounds = this->scroll_bounds(scroll_node_id);

  if (scroll_bounds.IsEmpty()) {
    return gfx::PointF();
  }

  const TransformTree& transform_tree = property_trees()->transform_tree();
  float scale_factor = 1.f;
  if (scroll_node.max_scroll_offset_affected_by_page_scale) {
    scale_factor = transform_tree.page_scale_factor();
  }

  gfx::SizeF scaled_scroll_bounds = gfx::ScaleSize(scroll_bounds, scale_factor);
  scaled_scroll_bounds.SetSize(std::floor(scaled_scroll_bounds.width()),
                               std::floor(scaled_scroll_bounds.height()));

  gfx::Size clip_layer_bounds = container_bounds(scroll_node.id);

  gfx::PointF max_offset(
      scaled_scroll_bounds.width() - clip_layer_bounds.width(),
      scaled_scroll_bounds.height() - clip_layer_bounds.height());

  max_offset.Scale(1 / scale_factor);
  max_offset.SetToMax(gfx::PointF());
  return max_offset;
}

gfx::SizeF ScrollTree::scroll_bounds(int scroll_node_id) const {
  const ScrollNode& scroll_node = Node(scroll_node_id);
  gfx::SizeF bounds(scroll_node.bounds);
  if (scroll_node.scrolls_inner_viewport) {
    const auto& delta = property_trees()->inner_viewport_scroll_bounds_delta();
    bounds.Enlarge(delta.x(), delta.y());
  }
  return bounds;
}

void ScrollTree::OnScrollOffsetAnimated(ElementId id,
                                        int scroll_tree_index,
                                        const gfx::PointF& scroll_offset,
                                        LayerTreeImpl* layer_tree_impl) {
  // Only active tree needs to be updated, pending tree will find out about
  // these changes as a result of the shared SyncedProperty.
  if (!property_trees()->is_active())
    return;

  TRACE_EVENT2("cc", "ScrollTree::OnScrollOffsetAnimated", "x",
               scroll_offset.x(), "y", scroll_offset.y());
  ScrollNode& scroll_node = MutableNode(scroll_tree_index);
  if (SetScrollOffset(id,
                      ClampScrollOffsetToLimits(scroll_offset, scroll_node))) {
    layer_tree_impl->DidUpdateScrollOffset(
        id, /*pushed_from_main_or_pending_tree=*/false);
  }
  layer_tree_impl->DidAnimateScrollOffset();
}

gfx::Size ScrollTree::container_bounds(int scroll_node_id) const {
  const ScrollNode& scroll_node = Node(scroll_node_id);
  gfx::Size container_bounds = scroll_node.container_bounds;

  gfx::Vector2dF container_bounds_delta;
  if (scroll_node.scrolls_inner_viewport) {
    container_bounds_delta.Add(
        property_trees()->inner_viewport_container_bounds_delta());
  } else if (scroll_node.scrolls_outer_viewport) {
    container_bounds_delta.Add(
        property_trees()->outer_viewport_container_bounds_delta());
  }

  gfx::Vector2d delta = gfx::ToCeiledVector2d(container_bounds_delta);
  container_bounds.Enlarge(delta.x(), delta.y());

  return container_bounds;
}

ScrollNode* ScrollTree::CurrentlyScrollingNode() {
  if (currently_scrolling_node_id_ == kInvalidPropertyNodeId) {
    return nullptr;
  }
  return &MutableNode(currently_scrolling_node_id_);
}

const ScrollNode* ScrollTree::CurrentlyScrollingNode() const {
  if (currently_scrolling_node_id_ == kInvalidPropertyNodeId) {
    return nullptr;
  }
  return &Node(currently_scrolling_node_id_);
}

#if DCHECK_IS_ON()
int ScrollTree::CurrentlyScrollingNodeId() const {
  return currently_scrolling_node_id_;
}
#endif

void ScrollTree::set_currently_scrolling_node(int scroll_node_id) {
  currently_scrolling_node_id_ = scroll_node_id;
}

gfx::Transform ScrollTree::ScreenSpaceTransform(int scroll_node_id) const {
  return property_trees()->transform_tree().ToScreen(
      Node(scroll_node_id).transform_id);
}

SyncedScrollOffset* ScrollTree::GetSyncedScrollOffset(ElementId id) {
  DCHECK(!property_trees()->is_main_thread());
  auto it = synced_scroll_offset_map_.find(id);
  return it != synced_scroll_offset_map_.end() ? it->second.get() : nullptr;
}

const SyncedScrollOffset* ScrollTree::GetSyncedScrollOffset(
    ElementId id) const {
  return const_cast<ScrollTree*>(this)->GetSyncedScrollOffset(id);
}

gfx::Vector2dF ScrollTree::ClampScrollToMaxScrollOffset(
    const ScrollNode& node,
    LayerTreeImpl* layer_tree_impl) {
  gfx::PointF old_offset = current_scroll_offset(node.element_id);
  gfx::PointF clamped_offset = ClampScrollOffsetToLimits(old_offset, node);
  gfx::Vector2dF delta = clamped_offset - old_offset;
  if (!delta.IsZero())
    ScrollBy(node, delta, layer_tree_impl);
  return delta;
}

const gfx::PointF ScrollTree::current_scroll_offset(ElementId id) const {
  if (property_trees()->is_main_thread()) {
    auto it = scroll_offset_map_.find(id);
    return it != scroll_offset_map_.end() ? it->second : gfx::PointF();
  }
  if (const auto* synced_scroll_offset = GetSyncedScrollOffset(id))
    return synced_scroll_offset->Current(property_trees()->is_active());
  return gfx::PointF();
}

gfx::PointF ScrollTree::GetScrollOffsetForScrollTimeline(
    const ScrollNode& scroll_node) const {
  gfx::PointF offset = current_scroll_offset(scroll_node.element_id);
  if (!property_trees()->is_main_thread()) {
    if (const SyncedScrollOffset* synced_offset =
            GetSyncedScrollOffset(scroll_node.element_id)) {
      // Ignore compositor scroll delta if the scroll can't be realized on the
      // corresponding tree because the delta has not been realized yet.
      if (property_trees()->is_active()) {
        if (!CanRealizeScrollsOnActiveTree(scroll_node)) {
          offset = synced_offset->ActiveBase();
        }
      } else if (!CanRealizeScrollsOnActiveTree(scroll_node) &&
                 !CanRealizeScrollsOnPendingTree(scroll_node)) {
        offset = synced_offset->PendingBase();
      }
    }
  }

  if (scroll_node.transform_id == kInvalidPropertyNodeId) {
    return offset;
  }

  const TransformNode& transform_node =
      property_trees()->transform_tree().Node(scroll_node.transform_id);

  // TODO(crbug.com/40894892): current_scroll_offset can disagree with
  // transform_node.scroll_offset if the delta on a main frame update is
  // simply rounding of the scroll position and not using fractional scroll
  // deltas (see needs_scroll_update in PushScrollUpdatesFromMainThread).

  if (transform_node.scrolls) {
    // If necessary perform a update for this node to ensure snap amount is
    // accurate. This method is used by scroll timeline, so it is possible for
    // it to get called before transform tree has gone through a full update
    // cycle so this node snap amount may be stale.
    if (transform_node.needs_local_transform_update) {
      property_trees()->transform_tree_mutable().UpdateTransforms(
          transform_node.id);
    }

    // The calculated pixel snap amount can be slightly larger than the actual
    // snapping needed, due to floating point precision errors. In general this
    // is fine, but we never want to report a negative scroll offset so avoid
    // that case here.
    // TODO(crbug.com/40688441): Remove the clamping when scroll timeline
    // effects always match the snapping.
    offset = ClampScrollOffsetToLimits(offset - transform_node.snap_amount,
                                       scroll_node);
  }

  return offset;
}

gfx::Vector2dF ScrollTree::PullDeltaForMainThread(
    SyncedScrollOffset* scroll_offset,
    bool use_fractional_deltas,
    bool next_bmf) {
  DCHECK(property_trees()->is_active());

  // Once this setting is enabled, all the complicated rounding logic below can
  // go away.
  if (use_fractional_deltas)
    return scroll_offset->PullDeltaForMainThread(next_bmf);

  // TODO(flackr): We should pass the fractional scroll deltas when Blink fully
  // supports fractional scrolls. crbug.com/414283.
  // TODO(flackr): We should ideally round the fractional scrolls in the same
  // direction as the scroll will be snapped but for common cases this is
  // equivalent to rounding to the nearest integer offset.
  gfx::PointF current_offset =
      scroll_offset->Current(/* is_active_tree */ true);
  gfx::PointF rounded_offset(gfx::ToRoundedPoint(current_offset));
  // The calculation of the difference from the rounded active base is to
  // represent the integer delta that the main thread should know about.
  gfx::PointF active_base = scroll_offset->ActiveBase();
  gfx::Vector2dF diff_active_base =
      active_base - gfx::PointF(gfx::ToRoundedPoint(active_base));
  scroll_offset->SetCurrent(rounded_offset + diff_active_base);
  gfx::Vector2dF delta = scroll_offset->PullDeltaForMainThread(next_bmf);
  scroll_offset->SetCurrent(current_offset);
  return delta;
}

void ScrollTree::CollectScrollDeltas(
    CompositorCommitData* commit_data,
    ElementId inner_viewport_scroll_element_id,
    bool use_fractional_deltas,
    const base::flat_map<ElementId, TargetSnapAreaElementIds>& snapped_elements,
    const MutatorHost* main_thread_mutator_host) {
  DCHECK(!property_trees()->is_main_thread());
  TRACE_EVENT0("cc", "ScrollTree::CollectScrollDeltas");
  for (auto map_entry : synced_scroll_offset_map_) {
    // The presence of a non-null mutator_host indicates that there is a
    // ready-to-commit main frame, hence we are pipelining this main frame.
    bool pipeline = main_thread_mutator_host;
    gfx::Vector2dF scroll_delta;
    // If the ready-to-commit main frame is going to clobber the scroll offset
    // in the active tree, then we shouldn't send a delta down to the main
    // thread.
    bool clobber =
        main_thread_mutator_host &&
        main_thread_mutator_host->ScrollOffsetAnimationWasInterrupted(
            map_entry.first);
    if (!clobber) {
      scroll_delta = PullDeltaForMainThread(map_entry.second.get(),
                                            use_fractional_deltas, pipeline);
    }

    ElementId id = map_entry.first;

    std::optional<TargetSnapAreaElementIds> snap_target_ids;
    if (snapped_elements.contains(id))
      snap_target_ids = snapped_elements.at(id);

    // Snap targets are set at the end of scroll offset animations (i.e when the
    // animation state is updated to FINISHED). The state can be updated after
    // the compositor's draw stage, which means the next attempt to push the
    // snap targets is during the next frame. This makes it possible for the
    // scroll delta to be zero.
    if (!scroll_delta.IsZero() || snap_target_ids) {
      TRACE_EVENT_INSTANT("cc", "CollectScrollDeltas", "x", scroll_delta.x(),
                          "y", scroll_delta.y());
      CompositorCommitData::ScrollUpdateInfo update(id, scroll_delta,
                                                    snap_target_ids);
      if (id == inner_viewport_scroll_element_id) {
        // Inner (visual) viewport is stored separately.
        commit_data->inner_viewport_scroll = std::move(update);
      } else {
        commit_data->scrolls.push_back(std::move(update));
      }
    }
  }
}

void ScrollTree::CollectScrollDeltasForTesting(bool use_fractional_deltas) {
  for (auto map_entry : synced_scroll_offset_map_) {
    PullDeltaForMainThread(map_entry.second.get(), use_fractional_deltas,
                           /* next_bmf */ false);
  }
}

void ScrollTree::PushScrollUpdatesFromMainThread(
    const PropertyTrees& main_property_trees,
    LayerTreeImpl* sync_tree,
    bool use_fractional_deltas) {
  DCHECK(!property_trees()->is_main_thread());
  const ScrollOffsetMap& main_scroll_offset_map =
      main_property_trees.scroll_tree().scroll_offset_map_;

  // We first want to clear SyncedProperty instances for layers which were
  // destroyed or became non-scrollable on the main thread.
  for (auto map_entry = synced_scroll_offset_map_.begin();
       map_entry != synced_scroll_offset_map_.end();) {
    ElementId id = map_entry->first;
    if (main_scroll_offset_map.find(id) == main_scroll_offset_map.end()) {
      // This SyncedScrollOffset might still be used to send a delta from the
      // active tree to the main thread, so we need to clear out the delta that
      // was sent to the main thread for this commit.
      map_entry->second->PushMainToPending(map_entry->second->Current(true));
      map_entry = synced_scroll_offset_map_.erase(map_entry);
    } else {
      map_entry++;
    }
  }

  for (auto map_entry : main_scroll_offset_map) {
    ElementId id = map_entry.first;
    // In non-test code, this should be the only code path that creates a new
    // SyncedScrollOffset.
    SyncedScrollOffset* synced_scroll_offset = GetSyncedScrollOffset(id);
    if (!synced_scroll_offset) {
      synced_scroll_offset = new SyncedScrollOffset();
      synced_scroll_offset_map_[id] = synced_scroll_offset;
    }

    // If the value on the main thread differs from the value on the pending
    // tree after state sync, we need to update the scroll state on the newly
    // committed PropertyTrees.
    bool needs_scroll_update =
        synced_scroll_offset->PushMainToPending(map_entry.second);
    // If `use_fractional_deltas` is false, then check against the rounded
    // pending offset instead of the offset directly. This matches
    // PullDeltaForMainThread where only an integer delta is extracted and
    // prevents unnecessary property change in this case.
    if (!use_fractional_deltas) {
      gfx::PointF pending_offset = synced_scroll_offset->Current(false);
      gfx::PointF rounded_offset(gfx::ToRoundedPoint(pending_offset));
      needs_scroll_update = map_entry.second != rounded_offset;
    }

    // If we are committing directly to the active tree, push pending to active
    // here. If the value differs between the pending and active trees, we need
    // to update the scroll state on the newly activated PropertyTrees.
    // In the case of pushing to the active tree, even if the pending and active
    // tree state match but the value on the active tree changed, we need to
    // update the scrollbar geometries.
    if (property_trees()->is_active())
      needs_scroll_update |= synced_scroll_offset->PushPendingToActive();

    if (needs_scroll_update) {
      sync_tree->DidUpdateScrollOffset(
          id, /*pushed_from_main_or_pending_tree=*/true);
    }
  }
}

void ScrollTree::PushScrollUpdatesFromPendingTree(
    PropertyTrees* pending_property_trees,
    LayerTreeImpl* active_tree) {
  DCHECK(property_trees()->is_active());
  DCHECK(!pending_property_trees->is_main_thread());
  DCHECK(!pending_property_trees->is_active());

  // When pushing to the active tree, we can simply copy over the map from the
  // pending tree. The pending and active tree hold a reference to the same
  // SyncedProperty instances.
  synced_scroll_offset_map_.clear();
  for (auto map_entry :
       pending_property_trees->scroll_tree().synced_scroll_offset_map_) {
    synced_scroll_offset_map_[map_entry.first] = map_entry.second;
    if (map_entry.second->PushPendingToActive()) {
      active_tree->DidUpdateScrollOffset(
          map_entry.first, /*pushed_from_main_or_pending_tree=*/true);
    }
  }
}

void ScrollTree::ApplySentScrollDeltasFromAbortedCommit(
    bool next_bmf,
    bool main_frame_applied_deltas) {
  DCHECK(property_trees()->is_active());
  for (auto& map_entry : synced_scroll_offset_map_)
    map_entry.second->AbortCommit(next_bmf, main_frame_applied_deltas);
}

void ScrollTree::SetBaseScrollOffset(ElementId id,
                                     const gfx::PointF& scroll_offset) {
  if (!std::isfinite(scroll_offset.x()) || !std::isfinite(scroll_offset.y())) {
    return;
  }
  if (property_trees()->is_main_thread()) {
    scroll_offset_map_[id] = scroll_offset;
    return;
  }

  DCHECK(GetSyncedScrollOffset(id));
  GetSyncedScrollOffset(id)->PushMainToPending(scroll_offset);
}

bool ScrollTree::SetScrollOffset(ElementId id,
                                 const gfx::PointF& scroll_offset) {
  if (!std::isfinite(scroll_offset.x()) || !std::isfinite(scroll_offset.y())) {
    return false;
  }
  // TODO(crbug.com/40132829): Remove TRACE_EVENT call when the bug is fixed
  TRACE_EVENT2("cc", "ScrollTree::SetScrollOffset", "x", scroll_offset.x(), "y",
               scroll_offset.y());
  if (property_trees()->is_main_thread()) {
    if (scroll_offset_map_[id] == scroll_offset)
      return false;
    scroll_offset_map_[id] = scroll_offset;
    return true;
  }

  if (property_trees()->is_active()) {
    if (auto* synced_scroll_offset = GetSyncedScrollOffset(id)) {
      return synced_scroll_offset->SetCurrent(scroll_offset);
    }
  }

  return false;
}

bool ScrollTree::SetElasticOverscroll(
    const ScrollNode& scroll_node,
    const gfx::Vector2dF& elastic_overscroll) {
  if (elastic_overscroll.IsZero()) {
    return elastic_overscroll_.erase(scroll_node.element_id) != 0;
  }
  gfx::Vector2dF& current_overscroll =
      elastic_overscroll_[scroll_node.element_id];
  bool changed = current_overscroll != elastic_overscroll;
  current_overscroll = elastic_overscroll;
  return changed;
}

gfx::Vector2dF ScrollTree::GetElasticOverscroll(
    const ScrollNode& scroll_node) const {
  return GetElasticOverscrollFromElementId(scroll_node.element_id);
}

gfx::Vector2dF ScrollTree::GetElasticOverscrollFromElementId(
    ElementId id) const {
  auto it = elastic_overscroll_.find(id);
  if (it == elastic_overscroll_.end()) {
    return gfx::Vector2dF();
  }
  return it->second;
}

std::pair<ElementId, gfx::Vector2dF>
ScrollTree::FindElasticOverscrollFromTransformId(
    int transform_id,
    const ViewportPropertyIds* viewport_property_ids) const {
  // TODO(crbug.com/465422599): Optimize this to use the `ElementId` directly
  // from the `TransformNode` to do a direct lookup instead of doing a search.
  // This will require updating the scroll translation transform node to use the
  // same compositor element id as the scroll node.
  const auto& scroll_tree = property_trees()->scroll_tree();
  if (viewport_property_ids &&
      transform_id == viewport_property_ids->overscroll_elasticity_transform) {
    if (viewport_property_ids->inner_scroll != kInvalidPropertyNodeId) {
      const ScrollNode& scroll_node =
          scroll_tree.Node(viewport_property_ids->inner_scroll);
      if (auto it = elastic_overscroll_.find(scroll_node.element_id);
          it != elastic_overscroll_.end()) {
        return {it->first, it->second};
      }
    }
  } else {
    // Iterate over the small set of elastic overscroll elements instead of all
    // scroll nodes.
    for (const auto& [element_id, stretch_amount] : elastic_overscroll_) {
      if (const ScrollNode* scroll_node =
              scroll_tree.FindNodeFromElementId(element_id)) {
        if (scroll_node->transform_id == transform_id) {
          return {element_id, stretch_amount};
        }
      }
    }
  }

  return {ElementId{}, gfx::Vector2dF{}};
}

void ScrollTree::SetScrollingContentsCullRect(ElementId id,
                                              const gfx::Rect& cull_rect) {
  scrolling_contents_cull_rects_[id] = cull_rect;
}

void ScrollTree::ClearScrollingContentsCullRect(ElementId id) {
  scrolling_contents_cull_rects_.erase(id);
}

const gfx::Rect* ScrollTree::ScrollingContentsCullRect(ElementId id) const {
  auto it = scrolling_contents_cull_rects_.find(id);
  if (it == scrolling_contents_cull_rects_.end()) {
    return nullptr;
  }
  return &it->second;
}

SyncedScrollOffset* ScrollTree::GetOrCreateSyncedScrollOffsetForTesting(
    ElementId id) {
  auto it = synced_scroll_offset_map_.find(id);
  if (it == synced_scroll_offset_map_.end()) {
    it = synced_scroll_offset_map_.try_emplace(id, new SyncedScrollOffset())
             .first;
  }
  return it->second.get();
}

bool ScrollTree::UpdateScrollOffsetBaseForTesting(ElementId id,
                                                  const gfx::PointF& offset) {
  DCHECK(!property_trees()->is_main_thread());
  SyncedScrollOffset* synced_scroll_offset =
      GetOrCreateSyncedScrollOffsetForTesting(id);  // IN-TEST
  bool changed = synced_scroll_offset->PushMainToPending(offset);
  if (property_trees()->is_active())
    changed |= synced_scroll_offset->PushPendingToActive();
  return changed;
}

bool ScrollTree::SetScrollOffsetDeltaForTesting(ElementId id,
                                                const gfx::Vector2dF& delta) {
  auto* synced_scroll_offset =
      GetOrCreateSyncedScrollOffsetForTesting(id);  // IN-TEST
  return synced_scroll_offset->SetCurrent(synced_scroll_offset->ActiveBase() +
                                          delta);
}

const gfx::PointF ScrollTree::GetScrollOffsetBaseForTesting(
    ElementId id) const {
  DCHECK(!property_trees()->is_main_thread());
  if (GetSyncedScrollOffset(id)) {
    return property_trees()->is_active()
               ? GetSyncedScrollOffset(id)->ActiveBase()
               : GetSyncedScrollOffset(id)->PendingBase();
  }
  return gfx::PointF();
}

const gfx::Vector2dF ScrollTree::GetScrollOffsetDeltaForTesting(
    ElementId id) const {
  DCHECK(!property_trees()->is_main_thread());
  if (GetSyncedScrollOffset(id)) {
    return property_trees()->is_active()
               ? GetSyncedScrollOffset(id)->Delta()
               : GetSyncedScrollOffset(id)->PendingDelta();
  }
  return gfx::Vector2dF();
}

gfx::Vector2dF ScrollTree::ScrollBy(const ScrollNode& scroll_node,
                                    const gfx::Vector2dF& scroll,
                                    LayerTreeImpl* layer_tree_impl) {
  TRACE_EVENT_BEGIN("input", "ScrollTree::ScrollBy", "scroll", scroll,
                    "scroll_node_id", scroll_node.id);
  gfx::Vector2dF adjusted_scroll(scroll);
  if (!scroll_node.user_scrollable_horizontal)
    adjusted_scroll.set_x(0);
  if (!scroll_node.user_scrollable_vertical)
    adjusted_scroll.set_y(0);
  gfx::PointF old_offset = current_scroll_offset(scroll_node.element_id);
  gfx::PointF new_offset =
      ClampScrollOffsetToLimits(old_offset + adjusted_scroll, scroll_node);
  if (SetScrollOffset(scroll_node.element_id, new_offset)) {
    layer_tree_impl->DidUpdateScrollOffset(
        scroll_node.element_id,
        /*pushed_from_main_or_pending_tree=*/false);
  }

  TRACE_EVENT_END("input", /* ScrollTree::ScrollBy */
                  "old_offset", old_offset, "new_offset", new_offset);

  // Return the amount of scroll delta we could not consume for this node.
  return old_offset + scroll - new_offset;
}

gfx::PointF ScrollTree::ClampScrollOffsetToLimits(
    gfx::PointF offset,
    const ScrollNode& scroll_node) const {
  offset.SetToMin(MaxScrollOffset(scroll_node.id));
  offset.SetToMax(gfx::PointF());
  return offset;
}

void ScrollTree::SetScrollCallbacks(base::WeakPtr<ScrollCallbacks> callbacks) {
  DCHECK(property_trees()->is_main_thread());
  callbacks_ = std::move(callbacks);
}

void ScrollTree::NotifyDidCompositorScroll(
    ElementId scroll_element_id,
    const gfx::PointF& scroll_offset,
    ScrollSourceType type,
    const std::optional<TargetSnapAreaElementIds>& snap_target_ids) {
  DCHECK(property_trees()->is_main_thread());
  if (callbacks_) {
    callbacks_->DidCompositorScroll(scroll_element_id, scroll_offset, type,
                                    snap_target_ids);
  }
}

void ScrollTree::NotifyDidChangeScrollbarsHidden(ElementId scroll_element_id,
                                                 bool hidden) const {
  DCHECK(property_trees()->is_main_thread());
  if (callbacks_)
    callbacks_->DidChangeScrollbarsHidden(scroll_element_id, hidden);
}

PropertyTreesCachedData::PropertyTreesCachedData()
    : transform_tree_update_number(0) {
  animation_scales.clear();
}

PropertyTreesCachedData::~PropertyTreesCachedData() = default;

PropertyTrees::PropertyTrees()
    : transform_tree_(this),
      effect_tree_(this),
      clip_tree_(this),
      scroll_tree_(this) {}

PropertyTrees::~PropertyTrees() = default;

#if DCHECK_IS_ON()
bool PropertyTrees::operator==(const PropertyTrees& other) const {
  return transform_tree() == other.transform_tree() &&
         effect_tree() == other.effect_tree() &&
         clip_tree() == other.clip_tree() &&
         scroll_tree() == other.scroll_tree() &&
         needs_rebuild() == other.needs_rebuild() &&
         changed() == other.changed() &&
         full_tree_damaged() == other.full_tree_damaged() &&
         is_main_thread() == other.is_main_thread() &&
         is_active() == other.is_active() &&
         sequence_number() == other.sequence_number() &&
         inner_viewport_container_bounds_delta() ==
             other.inner_viewport_container_bounds_delta() &&
         outer_viewport_container_bounds_delta() ==
             other.outer_viewport_container_bounds_delta() &&
         changed_effect_nodes_ == other.changed_effect_nodes_ &&
         changed_transform_nodes_ == other.changed_transform_nodes_;
}
#endif

PropertyTrees& PropertyTrees::operator=(const PropertyTrees& from) {
  transform_tree_mutable() = from.transform_tree();
  effect_tree_mutable() = from.effect_tree();
  clip_tree_mutable() = from.clip_tree();
  scroll_tree_mutable() = from.scroll_tree();
  set_needs_rebuild(from.needs_rebuild());
  set_changed(from.changed());
  set_full_tree_damaged(from.full_tree_damaged());
  set_sequence_number(from.sequence_number());
  set_is_main_thread(from.is_main_thread());
  set_is_active(from.is_active());
  SetInnerViewportContainerBoundsDelta(
      from.inner_viewport_container_bounds_delta());
  SetOuterViewportContainerBoundsDelta(
      from.outer_viewport_container_bounds_delta());
  SetTransformDeltaBySafeAreaInsetBottom(
      from.transform_delta_by_safe_area_inset_bottom());
  changed_effect_nodes_ = from.changed_effect_nodes_;
  changed_transform_nodes_ = from.changed_transform_nodes_;
  surface_property_changed_flags_ = from.surface_property_changed_flags_;
  transform_tree_mutable().SetPropertyTrees(this);
  effect_tree_mutable().SetPropertyTrees(this);
  clip_tree_mutable().SetPropertyTrees(this);
  scroll_tree_mutable().SetPropertyTrees(this);
  ResetCachedData();
  return *this;
}

void PropertyTrees::clear() {
  transform_tree_mutable().clear();
  clip_tree_mutable().clear();
  effect_tree_mutable().clear();
  scroll_tree_mutable().clear();

  set_needs_rebuild(true);
  set_full_tree_damaged(false);
  set_changed(false);
  increment_sequence_number();

  changed_effect_nodes_.clear();
  changed_transform_nodes_.clear();
  surface_property_changed_flags_.clear();

#if DCHECK_IS_ON()
  PropertyTrees tree;
  tree.transform_tree_mutable() = transform_tree();
  tree.effect_tree_mutable() = effect_tree();
  tree.clip_tree_mutable() = clip_tree();
  tree.scroll_tree_mutable() = scroll_tree();
  tree.scroll_tree_mutable().CopyCompleteTreeState(scroll_tree());

  tree.set_sequence_number(sequence_number());
  tree.set_is_main_thread(is_main_thread());
  tree.set_is_active(is_active());
  DCHECK(tree == *this);
#endif
}

void PropertyTrees::SetInnerViewportContainerBoundsDelta(
    gfx::Vector2dF bounds_delta) {
  if (inner_viewport_container_bounds_delta() == bounds_delta)
    return;

  inner_viewport_container_bounds_delta_ = bounds_delta;
}

void PropertyTrees::SetOuterViewportContainerBoundsDelta(
    gfx::Vector2dF bounds_delta) {
  if (outer_viewport_container_bounds_delta() == bounds_delta)
    return;

  outer_viewport_container_bounds_delta_ = bounds_delta;
  transform_tree_mutable().UpdateOuterViewportContainerBoundsDelta();
}

void PropertyTrees::SetTransformDeltaBySafeAreaInsetBottom(float delta) {
  if (transform_delta_by_safe_area_inset_bottom() == delta) {
    return;
  }

  transform_delta_by_safe_area_inset_bottom_ = delta;
  transform_tree_mutable().NeedTransformUpdateForSafeAreaInsetBottom();
}

bool PropertyTrees::ElementIsAnimatingChanged(
    const PropertyToElementIdMap& element_id_map,
    const PropertyAnimationState& mask,
    const PropertyAnimationState& state,
    bool check_node_existence) {
  bool updated_transform = false;
  for (int property = TargetProperty::FIRST_TARGET_PROPERTY;
       property <= TargetProperty::LAST_TARGET_PROPERTY; ++property) {
    if (!mask.currently_running[property] &&
        !mask.potentially_animating[property])
      continue;

    // The mask represents which properties have had their state changed. This
    // can include properties for which there are no longer any animations, in
    // which case there will not be an entry in the map.
    //
    // It is unclear whether this is desirable; it may be that we are missing
    // updates to property nodes here because we no longer have the required
    // ElementId to look them up. See http://crbug.com/912574 for context around
    // why this code was rewritten.
    auto it = element_id_map.find(static_cast<TargetProperty::Type>(property));
    if (it == element_id_map.end())
      continue;

    const ElementId element_id = it->second;
    switch (property) {
      case TargetProperty::TRANSFORM:
      case TargetProperty::SCALE:
      case TargetProperty::ROTATE:
      case TargetProperty::TRANSLATE:
        if (TransformNode* transform_node =
                transform_tree_mutable().MutableFindNodeFromElementId(
                    element_id)) {
          if (mask.currently_running[property])
            transform_node->is_currently_animating =
                state.currently_running[property];
          if (mask.potentially_animating[property]) {
            transform_node->has_potential_animation =
                state.potentially_animating[property];
            transform_tree_mutable().set_needs_update(true);
            // We track transform updates specifically, whereas we
            // don't do so for opacity/filter, because whether a
            // transform is animating can change what layer(s) we
            // draw.
            updated_transform = true;
          }
        } else {
          DCHECK_NODE_EXISTENCE(check_node_existence, state, property,
                                needs_rebuild())
              << "Attempting to animate non existent transform node";
        }
        break;
      case TargetProperty::OPACITY:
        if (EffectNode* effect_node =
                effect_tree_mutable().MutableFindNodeFromElementId(
                    element_id)) {
          if (mask.potentially_animating[property]) {
            effect_node->has_potential_opacity_animation =
                state.potentially_animating[property];
            // We may need to propagate things like screen space opacity.
            effect_tree_mutable().set_needs_update(true);
          }
        } else {
          DCHECK_NODE_EXISTENCE(check_node_existence, state, property,
                                needs_rebuild())
              << "Attempting to animate opacity on non existent effect node";
        }
        break;
      case TargetProperty::FILTER:
        if (EffectNode* effect_node =
                effect_tree_mutable().MutableFindNodeFromElementId(
                    element_id)) {
          if (mask.potentially_animating[property])
            effect_node->has_potential_filter_animation =
                state.potentially_animating[property];
          // Filter animation changes only the node, and the subtree does not
          // care, thus there is no need to request property tree update.
        } else {
          DCHECK_NODE_EXISTENCE(check_node_existence, state, property,
                                needs_rebuild())
              << "Attempting to animate filter on non existent effect node";
        }
        break;
      case TargetProperty::BACKDROP_FILTER:
        if (EffectNode* effect_node =
                effect_tree_mutable().MutableFindNodeFromElementId(
                    element_id)) {
          if (mask.potentially_animating[property])
            effect_node->has_potential_backdrop_filter_animation =
                state.potentially_animating[property];
          // Backdrop-filter animation changes only the node, and the subtree
          // does not care, thus there is no need to request property tree
          // update.
        } else {
          DCHECK_NODE_EXISTENCE(check_node_existence, state, property,
                                needs_rebuild())
              << "Attempting to animate filter on non existent effect node";
        }
        break;
      default:
        break;
    }
  }
  return updated_transform;
}
#undef DCHECK_NODE_EXISTENCE

void PropertyTrees::MaximumAnimationScaleChanged(ElementId element_id,
                                                 float maximum_scale) {
  if (TransformNode* transform_node =
          transform_tree_mutable().MutableFindNodeFromElementId(element_id)) {
    transform_node->maximum_animation_scale = maximum_scale;
    UpdateTransformTreeUpdateNumber();
  }
}

void PropertyTrees::UpdateChangeTracking() {
  auto& mutable_effect_tree = effect_tree_mutable();
  for (int id = kContentsRootPropertyNodeId;
       id < static_cast<int>(mutable_effect_tree.size()); ++id) {
    EffectNode& node = mutable_effect_tree.MutableNode(id);
    EffectNode* parent_node = mutable_effect_tree.HasParent(node)
                                  ? &mutable_effect_tree.MutableParent(node)
                                  : nullptr;
    mutable_effect_tree.UpdateEffectChanged(&node, parent_node);
  }
  auto& mutable_transform_tree = transform_tree_mutable();
  for (int i = kContentsRootPropertyNodeId;
       i < static_cast<int>(mutable_transform_tree.size()); ++i) {
    TransformNode& node = mutable_transform_tree.MutableNode(i);
    TransformNode& parent_node = mutable_transform_tree.MutableParent(node);
    mutable_transform_tree.UpdateTransformChanged(&node, parent_node);
  }
}

void PropertyTrees::GetChangedNodes(std::vector<int>& effect_nodes,
                                    std::vector<int>& transform_nodes) const {
  for (int id = kContentsRootPropertyNodeId;
       id < static_cast<int>(effect_tree().size()); ++id) {
    if (effect_tree().Node(id).effect_changed) {
      effect_nodes.push_back(id);
    }
  }
  for (int id = kContentsRootPropertyNodeId;
       id < static_cast<int>(transform_tree().size()); ++id) {
    if (transform_tree().Node(id).transform_changed()) {
      transform_nodes.push_back(id);
    }
  }
}

void PropertyTrees::ApplyChangedNodes(
    const std::vector<int>& changed_effect_nodes,
    const std::vector<int>& changed_transform_nodes) {
  if (changed_effect_nodes.size() || changed_transform_nodes.size()) {
    for (int i : changed_effect_nodes) {
      effect_tree_mutable().MutableNode(i).effect_changed = true;
    }
    for (int i : changed_transform_nodes) {
      transform_tree_mutable().MutableNode(i).SetTransformChanged(
          DamageReason::kUntracked);
    }
    UpdateChangeTracking();
  }
}

void PropertyTrees::CollectChangeState() {
  GetChangedNodes(changed_effect_nodes_, changed_transform_nodes_);
  effect_tree().GetRenderSurfaceChangedFlags(surface_property_changed_flags_);
}

void PropertyTrees::TakeChangeStateFrom(PropertyTrees& source) {
  // Note that EffectTree::TakeCopyRequest() can flip the value of
  // needs_rebuild(), but the prior value is the one we need to propagate, so we
  // snapshot that first.
  auto copy_requests = source.effect_tree_mutable().TakeCopyRequests();
  effect_tree_mutable().PullCopyRequestsFrom(copy_requests);
  CollectChangeState();
}

void PropertyTrees::ApplyChangeStateFrom(PropertyTrees& source) {
  changed_ |= source.changed();
  needs_rebuild_ |= source.needs_rebuild();
  full_tree_damaged_ |= source.full_tree_damaged();
  // To preserve ordering, the copy requests in source should come before
  // any requests added since source was created.
  auto copy_requests = source.effect_tree_mutable().TakeCopyRequests();
  copy_requests.merge(effect_tree_mutable().TakeCopyRequests());
  effect_tree_mutable().PullCopyRequestsFrom(copy_requests);
  ApplyChangedNodes(source.changed_effect_nodes(),
                    source.changed_transform_nodes());
}

void PropertyTrees::ResetAllChangeTracking() {
  transform_tree_mutable().ResetChangeTracking();
  effect_tree_mutable().ResetChangeTracking();
  set_changed(false);
  set_full_tree_damaged(false);
  changed_effect_nodes_.clear();
  changed_transform_nodes_.clear();
  surface_property_changed_flags_.clear();
}

std::unique_ptr<base::trace_event::TracedValue> PropertyTrees::AsTracedValue()
    const {
  auto value = std::make_unique<base::trace_event::TracedValue>();
  AsValueInto(value.get());
  return value;
}

void PropertyTrees::AsValueInto(base::trace_event::TracedValue* value) const {
  value->SetInteger("sequence_number", sequence_number());

  value->BeginDictionary("transform_tree");
  transform_tree().AsValueInto(value);
  value->EndDictionary();

  value->BeginDictionary("effect_tree");
  effect_tree().AsValueInto(value);
  value->EndDictionary();

  value->BeginDictionary("clip_tree");
  clip_tree().AsValueInto(value);
  value->EndDictionary();

  value->BeginDictionary("scroll_tree");
  scroll_tree().AsValueInto(value);
  value->EndDictionary();
}

std::string PropertyTrees::ToString() const {
  base::trace_event::TracedValueJSON value;
  AsValueInto(&value);
  return value.ToFormattedJSON();
}

bool PropertyTrees::AnimationScaleCacheIsInvalid(int transform_id) const {
  DCHECK(!is_main_thread());
  // This doesn't check if |update_number| equals to
  // |transform_tree_update_number| because the the latter is changed by the
  // animation itself while we want to treat the scale as valid during the
  // animation. |update_number| is reset to kInvalidUpdateNumber when a new
  // property tree is pushed.
  CHECK(transform_id >= 0 &&
        transform_id < static_cast<int>(cached_data_.animation_scales.size()));
  return cached_data_.animation_scales[transform_id].update_number ==
         kInvalidUpdateNumber;
}

float PropertyTrees::MaximumAnimationToScreenScale(int transform_id) {
  return GetAnimationScaleData(transform_id).maximum_to_screen_scale;
}

bool PropertyTrees::AnimationAffectedByInvalidScale(int transform_id) {
  return GetAnimationScaleData(transform_id).affected_by_invalid_scale;
}

const AnimationScaleData& PropertyTrees::GetAnimationScaleData(
    int transform_id) {
  DCHECK(!is_main_thread());

  CHECK(transform_id >= 0 &&
        transform_id < static_cast<int>(cached_data_.animation_scales.size()));
  auto& animation_scale = cached_data_.animation_scales[transform_id];
  if (animation_scale.update_number ==
      cached_data_.transform_tree_update_number) {
    return animation_scale;
  }

  animation_scale.update_number = cached_data_.transform_tree_update_number;

  TransformNode& node = transform_tree_mutable().MutableNode(transform_id);
  TransformNode* parent_node =
      transform_tree_mutable().HasParent(node)
          ? &transform_tree_mutable().MutableParent(node)
          : nullptr;
  const auto* parent_animation_scale =
      parent_node ? &GetAnimationScaleData(parent_node->id) : nullptr;

  bool ancestor_affected_by_animation_scale =
      parent_node && parent_animation_scale->affected_by_animation_scale;
  bool node_affected_by_animation_scale =
      node.has_potential_animation && node.maximum_animation_scale != 1.0f;

  animation_scale.affected_by_animation_scale =
      node_affected_by_animation_scale || ancestor_affected_by_animation_scale;
  animation_scale.affected_by_invalid_scale =
      (parent_node && parent_animation_scale->affected_by_invalid_scale) ||
      // Computing maximum animated scale in the presence of perspective isn't
      // supported.
      node.to_parent.HasPerspective() ||
      (node.has_potential_animation &&
       node.maximum_animation_scale == kInvalidScale);

  // We don't attempt to accumulate animation scale from multiple nodes with
  // scale animations, because of the risk of significant overestimation. For
  // example, one node might be increasing scale from 1 to 10 at the same time
  // as another node is decreasing scale from 10 to 1. Naively combining these
  // scales would produce a scale of 100.
  bool failed_for_multiple_scale_animations =
      ancestor_affected_by_animation_scale && node_affected_by_animation_scale;

  float local_maximum_scale = 1.0f;
  if (animation_scale.affected_by_invalid_scale ||
      failed_for_multiple_scale_animations) {
    // Will use the parent's maximum_to_screen_scale.
  } else if (!node.to_screen_is_potentially_animated) {
    // No transform animations. Calculate the current to_screen scale.
    gfx::Vector2dF to_screen_scales = gfx::ComputeTransform2dScaleComponents(
        transform_tree().ToScreen(transform_id), kInvalidScale);
    animation_scale.maximum_to_screen_scale =
        std::max(to_screen_scales.x(), to_screen_scales.y());
    return animation_scale;
  } else if (!node.has_potential_animation) {
    gfx::Vector2dF local_scales =
        gfx::ComputeTransform2dScaleComponents(node.local, 1.0f);
    local_maximum_scale = std::max(local_scales.x(), local_scales.y());
  } else {
    DCHECK_NE(node.maximum_animation_scale, kInvalidScale);
    local_maximum_scale = node.maximum_animation_scale;
  }

  animation_scale.maximum_to_screen_scale = local_maximum_scale;
  if (parent_node) {
    animation_scale.maximum_to_screen_scale *=
        parent_animation_scale->maximum_to_screen_scale;
  }

  return animation_scale;
}

void PropertyTrees::SetMaximumAnimationToScreenScaleForTesting(
    int transform_id,
    float maximum_scale,
    bool affected_by_invalid_scale) {
  CHECK(transform_id >= 0 &&
        transform_id < static_cast<int>(cached_data_.animation_scales.size()));
  auto& animation_scale = cached_data_.animation_scales[transform_id];
  animation_scale.maximum_to_screen_scale = maximum_scale;
  animation_scale.affected_by_invalid_scale = affected_by_invalid_scale;
  animation_scale.update_number = cached_data_.transform_tree_update_number;
}

bool PropertyTrees::GetToTarget(int transform_id,
                                int effect_id,
                                gfx::Transform* to_target) const {
  if (effect_id == kContentsRootPropertyNodeId) {
    *to_target = transform_tree().ToScreen(transform_id);
    return true;
  }
  DrawTransforms& transforms = GetDrawTransforms(transform_id, effect_id);
  if (transforms.to_valid) {
    *to_target = transforms.to_target;
    return true;
  } else if (!transforms.might_be_invertible) {
    return false;
  } else {
    transforms.might_be_invertible =
        transforms.from_target.GetInverse(to_target);
    transforms.to_valid = transforms.might_be_invertible;
    transforms.to_target = *to_target;
    return transforms.to_valid;
  }
}

bool PropertyTrees::GetFromTarget(int transform_id,
                                  int effect_id,
                                  gfx::Transform* from_target) const {
  const TransformNode& node = transform_tree().Node(transform_id);
  if (node.ancestors_are_invertible &&
      effect_id == kContentsRootPropertyNodeId) {
    *from_target = transform_tree().FromScreen(transform_id);
    return true;
  }
  DrawTransforms& transforms = GetDrawTransforms(transform_id, effect_id);
  if (transforms.from_valid) {
    *from_target = transforms.from_target;
    return true;
  } else if (!transforms.might_be_invertible) {
    return false;
  } else {
    transforms.might_be_invertible =
        transforms.to_target.GetInverse(from_target);
    transforms.from_valid = transforms.might_be_invertible;
    transforms.from_target = *from_target;
    return transforms.from_valid;
  }
}

DrawTransformData& PropertyTrees::FetchDrawTransformsDataFromCache(
    int transform_id,
    int effect_id) const {
  CHECK(transform_id >= 0 &&
        transform_id < static_cast<int>(cached_data_.draw_transforms.size()));
  for (auto& transform_data : cached_data_.draw_transforms[transform_id]) {
    // We initialize draw_transforms with 1 element vectors when
    // ResetCachedData, so if we hit an invalid target id, it means it's the
    // first time we compute draw transforms after reset.
    if (transform_data.effect_id == effect_id ||
        transform_data.effect_id == kInvalidPropertyNodeId) {
      return transform_data;
    }
  }
  // Add an entry to the cache.
  cached_data_.draw_transforms[transform_id].push_back(DrawTransformData());
  DrawTransformData& data = cached_data_.draw_transforms[transform_id].back();
  data.update_number = kInvalidUpdateNumber;
  data.effect_id = effect_id;
  return data;
}

ClipRectData* PropertyTrees::FetchClipRectFromCache(int clip_id,
                                                    int target_id) {
  ClipNode& clip_node = clip_tree_mutable().MutableNode(clip_id);
  for (auto& data : clip_node.cached_clip_rects) {
    if (data.target_id == target_id || data.target_id == kInvalidPropertyNodeId)
      return &data;
  }
  clip_node.cached_clip_rects.emplace_back();
  clip_node.cached_clip_rects.back().target_id = kInvalidPropertyNodeId;
  return &clip_node.cached_clip_rects.back();
}

bool PropertyTrees::HasElement(ElementId element_id) const {
  if (!element_id)
    return false;
  return clip_tree().FindNodeFromElementId(element_id) ||
         effect_tree().FindNodeFromElementId(element_id) ||
         scroll_tree().FindNodeFromElementId(element_id) ||
         transform_tree().FindNodeFromElementId(element_id);
}

DrawTransforms& PropertyTrees::GetDrawTransforms(int transform_id,
                                                 int effect_id) const {
  const EffectNode& effect_node = effect_tree().Node(effect_id);
  int dest_id = effect_node.transform_id;

  DrawTransformData& data =
      FetchDrawTransformsDataFromCache(transform_id, effect_id);

  DCHECK(data.update_number != cached_data_.transform_tree_update_number ||
         data.effect_id != kInvalidPropertyNodeId);
  if (data.update_number == cached_data_.transform_tree_update_number) {
    return data.transforms;
  }

  // Cache miss.
  gfx::Transform target_space_transform;
  gfx::Transform from_target;
  bool already_computed_inverse = false;
  if (transform_id == dest_id) {
    target_space_transform.Scale(effect_node.surface_contents_scale.x(),
                                 effect_node.surface_contents_scale.y());
    data.transforms.to_valid = true;
    data.transforms.from_valid = false;
  } else if (transform_id > dest_id) {
    transform_tree().CombineTransformsBetween(transform_id, dest_id,
                                              &target_space_transform);
    target_space_transform.PostScale(effect_node.surface_contents_scale.x(),
                                     effect_node.surface_contents_scale.y());
    data.transforms.to_valid = true;
    data.transforms.from_valid = false;
    data.transforms.might_be_invertible = true;
  } else {
    gfx::Transform combined_transform;
    transform_tree().CombineTransformsBetween(dest_id, transform_id,
                                              &combined_transform);
    if (effect_node.surface_contents_scale.x() != 0.f &&
        effect_node.surface_contents_scale.y() != 0.f) {
      combined_transform.Scale(1.0f / effect_node.surface_contents_scale.x(),
                               1.0f / effect_node.surface_contents_scale.y());
    }
    bool invertible = combined_transform.GetInverse(&target_space_transform);
    data.transforms.might_be_invertible = invertible;
    data.transforms.to_valid = invertible;
    data.transforms.from_valid = true;
    from_target = combined_transform;
    already_computed_inverse = true;
  }

  if (!already_computed_inverse)
    data.transforms.to_valid = true;
  data.update_number = cached_data_.transform_tree_update_number;
  data.effect_id = effect_id;
  data.transforms.from_target = from_target;
  data.transforms.to_target = target_space_transform;
  return data.transforms;
}

void PropertyTrees::ResetCachedData() {
  cached_data_.transform_tree_update_number = 0;
  const auto transform_count = transform_tree().size();
  cached_data_.animation_scales.resize(transform_count);
  for (auto& animation_scale : cached_data_.animation_scales)
    animation_scale.update_number = kInvalidUpdateNumber;

  cached_data_.draw_transforms.resize(transform_count,
                                      std::vector<DrawTransformData>(1));
  for (auto& draw_transforms_for_id : cached_data_.draw_transforms) {
    draw_transforms_for_id.resize(1);
    draw_transforms_for_id[0].update_number = kInvalidUpdateNumber;
    draw_transforms_for_id[0].effect_id = kInvalidPropertyNodeId;
  }
}

void PropertyTrees::UpdateTransformTreeUpdateNumber() {
  cached_data_.transform_tree_update_number++;
}

gfx::Transform PropertyTrees::ToScreenSpaceTransformWithoutSurfaceContentsScale(
    int transform_id,
    int effect_id) const {
  if (transform_id == kRootPropertyNodeId) {
    return gfx::Transform();
  }
  gfx::Transform screen_space_transform =
      transform_tree().ToScreen(transform_id);
  const EffectNode& effect_node = effect_tree().Node(effect_id);

  if (effect_node.surface_contents_scale.x() != 0.0 &&
      effect_node.surface_contents_scale.y() != 0.0) {
    screen_space_transform.Scale(1.0 / effect_node.surface_contents_scale.x(),
                                 1.0 / effect_node.surface_contents_scale.y());
  }
  return screen_space_transform;
}

}  // namespace cc