tor-browser

spatial_tree.rs (80601B)

---

/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

use api::{ExternalScrollId, PropertyBinding, ReferenceFrameKind, TransformStyle, PropertyBindingId};
use api::{APZScrollGeneration, HasScrollLinkedEffect, PipelineId, SampledScrollOffset, SpatialTreeItemKey};
use api::units::*;
use euclid::Transform3D;
use crate::gpu_types::TransformPalette;
use crate::internal_types::{FastHashMap, FastHashSet, FrameMemory, PipelineInstanceId};
use crate::print_tree::{PrintableTree, PrintTree, PrintTreePrinter};
use crate::scene::SceneProperties;
use crate::spatial_node::{ReferenceFrameInfo, SpatialNode, SpatialNodeDescriptor, SpatialNodeType, StickyFrameInfo};
use crate::spatial_node::{SpatialNodeUid, ScrollFrameKind, SceneSpatialNode, SpatialNodeInfo, SpatialNodeUidKind};
use std::{ops, u32};
use crate::util::{FastTransform, LayoutToWorldFastTransform, MatrixHelpers, ScaleOffset, scale_factors};
use smallvec::SmallVec;
use std::collections::hash_map::Entry;
use crate::util::TransformedRectKind;
use peek_poke::PeekPoke;


/// An id that identifies coordinate systems in the SpatialTree. Each
/// coordinate system has an id and those ids will be shared when the coordinates
/// system are the same or are in the same axis-aligned space. This allows
/// for optimizing mask generation.
#[derive(Debug, Copy, Clone, PartialEq, PartialOrd)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct CoordinateSystemId(pub u32);

/// A node in the hierarchy of coordinate system
/// transforms.
#[derive(Debug)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct CoordinateSystem {
   pub transform: LayoutTransform,
   pub world_transform: LayoutToWorldTransform,
   pub should_flatten: bool,
   pub parent: Option<CoordinateSystemId>,
}

impl CoordinateSystem {
   fn root() -> Self {
       CoordinateSystem {
           transform: LayoutTransform::identity(),
           world_transform: LayoutToWorldTransform::identity(),
           should_flatten: false,
           parent: None,
       }
   }
}

#[derive(Debug, Copy, Clone, Eq, Hash, MallocSizeOf, PartialEq, PeekPoke, Default)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct SpatialNodeIndex(pub u32);

impl SpatialNodeIndex {
   pub const INVALID: SpatialNodeIndex = SpatialNodeIndex(u32::MAX);

   /// May be set on a cluster / picture during scene building if the spatial
   /// node is not known at this time. It must be set to a valid value before
   /// scene building is complete (by `finalize_picture`). In future, we could
   /// make this type-safe with a wrapper type to ensure we know when a spatial
   /// node index may have an unknown value.
   pub const UNKNOWN: SpatialNodeIndex = SpatialNodeIndex(u32::MAX - 1);
}

// In some cases, the conversion from CSS pixels to device pixels can result in small
// rounding errors when calculating the scrollable distance of a scroll frame. Apply
// a small epsilon so that we don't detect these frames as "real" scroll frames.
const MIN_SCROLLABLE_AMOUNT: f32 = 0.01;

// The minimum size for a scroll frame for it to be considered for a scroll root.
const MIN_SCROLL_ROOT_SIZE: f32 = 128.0;

impl SpatialNodeIndex {
   pub fn new(index: usize) -> Self {
       debug_assert!(index < ::std::u32::MAX as usize);
       SpatialNodeIndex(index as u32)
   }
}

impl CoordinateSystemId {
   pub fn root() -> Self {
       CoordinateSystemId(0)
   }
}

#[derive(Debug, Copy, Clone, PartialEq)]
pub enum VisibleFace {
   Front,
   Back,
}

impl Default for VisibleFace {
   fn default() -> Self {
       VisibleFace::Front
   }
}

impl ops::Not for VisibleFace {
   type Output = Self;
   fn not(self) -> Self {
       match self {
           VisibleFace::Front => VisibleFace::Back,
           VisibleFace::Back => VisibleFace::Front,
       }
   }
}

/// Allows functions and methods to retrieve common information about
/// a spatial node, whether during scene or frame building
pub trait SpatialNodeContainer {
   /// Get the common information for a given spatial node
   fn get_node_info(&self, index: SpatialNodeIndex) -> SpatialNodeInfo;

   fn get_snapping_info(
       &self,
       parent_index: Option<SpatialNodeIndex>
   ) -> Option<ScaleOffset> {
       match parent_index {
           Some(parent_index) => {
               let node_info = self.get_node_info(parent_index);
               node_info.snapping_transform
           }
           None => {
               Some(ScaleOffset::identity())
           }
       }
   }
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
enum StoreElement<T> {
   Empty,
   Occupied(T),
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct Store<T> {
   elements: Vec<StoreElement<T>>,
   free_indices: Vec<usize>,
}

impl<T> Store<T> {
   fn new() -> Self {
       Store {
           elements: Vec::new(),
           free_indices: Vec::new(),
       }
   }

   fn insert(&mut self, element: T) -> usize {
       match self.free_indices.pop() {
           Some(index) => {
               match &mut self.elements[index] {
                   e @ StoreElement::Empty => *e = StoreElement::Occupied(element),
                   StoreElement::Occupied(..) => panic!("bug: slot already occupied"),
               };
               index
           }
           None => {
               let index = self.elements.len();
               self.elements.push(StoreElement::Occupied(element));
               index
           }
       }
   }

   fn set(&mut self, index: usize, element: T) {
       match &mut self.elements[index] {
           StoreElement::Empty => panic!("bug: set on empty element!"),
           StoreElement::Occupied(ref mut entry) => *entry = element,
       }
   }

   fn free(&mut self, index: usize) -> T {
       self.free_indices.push(index);

       let value = std::mem::replace(&mut self.elements[index], StoreElement::Empty);

       match value {
           StoreElement::Occupied(value) => value,
           StoreElement::Empty => panic!("bug: freeing an empty slot"),
       }
   }
}

impl<T> ops::Index<usize> for Store<T> {
   type Output = T;
   fn index(&self, index: usize) -> &Self::Output {
       match self.elements[index] {
           StoreElement::Occupied(ref e) => e,
           StoreElement::Empty => panic!("bug: indexing an empty element!"),
       }
   }
}

impl<T> ops::IndexMut<usize> for Store<T> {
   fn index_mut(&mut self, index: usize) -> &mut T {
       match self.elements[index] {
           StoreElement::Occupied(ref mut e) => e,
           StoreElement::Empty => panic!("bug: indexing an empty element!"),
       }
   }
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct SpatialNodeEntry {
   index: usize,
   last_used: u64,
}

/// The representation of the spatial tree during scene building, which is
/// mostly write-only, with a small number of queries for snapping,
/// picture cache building
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct SceneSpatialTree {
   /// Nodes which determine the positions (offsets and transforms) for primitives
   /// and clips.
   spatial_nodes: Store<SceneSpatialNode>,

   /// A set of the uids we've encountered for spatial nodes, used to assert that
   /// we're not seeing duplicates. Likely to be removed once we rely on this feature.
   spatial_node_map: FastHashMap<SpatialNodeUid, SpatialNodeEntry>,

   root_reference_frame_index: SpatialNodeIndex,

   frame_counter: u64,
   updates: SpatialTreeUpdates,

   /// A debug check that the caller never adds a spatial node with duplicate
   /// uid, since that can cause badness if it occurs (e.g. a malformed spatial
   /// tree and infinite loops in is_ancestor etc)
   spatial_nodes_set: FastHashSet<SpatialNodeUid>,
}

impl SpatialNodeContainer for SceneSpatialTree {
   fn get_node_info(&self, index: SpatialNodeIndex) -> SpatialNodeInfo {
       let node = &self.spatial_nodes[index.0 as usize];

       SpatialNodeInfo {
           parent: node.parent,
           node_type: &node.descriptor.node_type,
           snapping_transform: node.snapping_transform,
       }
   }
}

impl SceneSpatialTree {
   pub fn new() -> Self {
       let mut tree = SceneSpatialTree {
           spatial_nodes: Store::new(),
           spatial_node_map: FastHashMap::default(),
           root_reference_frame_index: SpatialNodeIndex(0),
           frame_counter: 0,
           updates: SpatialTreeUpdates::new(),
           spatial_nodes_set: FastHashSet::default(),
       };

       let node = SceneSpatialNode::new_reference_frame(
           None,
           TransformStyle::Flat,
           PropertyBinding::Value(LayoutTransform::identity()),
           ReferenceFrameKind::Transform {
               should_snap: true,
               is_2d_scale_translation: true,
               paired_with_perspective: false,
           },
           LayoutVector2D::zero(),
           PipelineId::dummy(),
           true,
           true,
       );

       tree.add_spatial_node(node, SpatialNodeUid::root());

       tree
   }

   pub fn is_root_coord_system(&self, index: SpatialNodeIndex) -> bool {
       self.spatial_nodes[index.0 as usize].is_root_coord_system
   }

   /// Complete building this scene, return the updates to apply to the frame spatial tree
   pub fn end_frame_and_get_pending_updates(&mut self) -> SpatialTreeUpdates {
       self.updates.root_reference_frame_index = self.root_reference_frame_index;
       self.spatial_nodes_set.clear();

       let now = self.frame_counter;
       let spatial_nodes = &mut self.spatial_nodes;
       let updates = &mut self.updates;

       self.spatial_node_map.get_mut(&SpatialNodeUid::root()).unwrap().last_used = now;

       self.spatial_node_map.retain(|_, entry| {
           if entry.last_used + 10 < now {
               spatial_nodes.free(entry.index);
               updates.updates.push(SpatialTreeUpdate::Remove {
                   index: entry.index,
               });
               return false;
           }

           true
       });

       let updates = std::mem::replace(&mut self.updates, SpatialTreeUpdates::new());

       self.frame_counter += 1;

       updates
   }

   /// Check if a given spatial node is an ancestor of another spatial node.
   pub fn is_ancestor(
       &self,
       maybe_parent: SpatialNodeIndex,
       maybe_child: SpatialNodeIndex,
   ) -> bool {
       // Early out if same node
       if maybe_parent == maybe_child {
           return false;
       }

       let mut current_node = maybe_child;

       while current_node != self.root_reference_frame_index {
           let node = self.get_node_info(current_node);
           current_node = node.parent.expect("bug: no parent");

           if current_node == maybe_parent {
               return true;
           }
       }

       false
   }

   /// Find the spatial node that is the scroll root for a given spatial node.
   /// A scroll root is the first spatial node when found travelling up the
   /// spatial node tree that is an explicit scroll frame.
   pub fn find_scroll_root(
       &self,
       spatial_node_index: SpatialNodeIndex,
       allow_sticky_frames: bool,
   ) -> SpatialNodeIndex {
       let mut real_scroll_root = self.root_reference_frame_index;
       let mut outermost_scroll_root = self.root_reference_frame_index;
       let mut current_scroll_root_is_sticky = false;
       let mut node_index = spatial_node_index;

       while node_index != self.root_reference_frame_index {
           let node = self.get_node_info(node_index);
           match node.node_type {
               SpatialNodeType::ReferenceFrame(ref info) => {
                   match info.kind {
                       ReferenceFrameKind::Transform { is_2d_scale_translation: true, .. } => {
                           // We can handle scroll nodes that pass through a 2d scale/translation node
                       }
                       ReferenceFrameKind::Transform { is_2d_scale_translation: false, .. } |
                       ReferenceFrameKind::Perspective { .. } => {
                           // When a reference frame is encountered, forget any scroll roots
                           // we have encountered, as they may end up with a non-axis-aligned transform.
                           real_scroll_root = self.root_reference_frame_index;
                           outermost_scroll_root = self.root_reference_frame_index;
                           current_scroll_root_is_sticky = false;
                       }
                   }
               }
               SpatialNodeType::StickyFrame(..) => {
                   // Though not a scroll frame, we optionally treat sticky frames as scroll roots
                   // to ensure they are given a separate picture cache slice.
                   if allow_sticky_frames {
                       outermost_scroll_root = node_index;
                       real_scroll_root = node_index;
                       // Set this true so that we don't select an ancestor scroll frame as the scroll root
                       // on a subsequent iteration.
                       current_scroll_root_is_sticky = true;
                   }
               }
               SpatialNodeType::ScrollFrame(ref info) => {
                   match info.frame_kind {
                       ScrollFrameKind::PipelineRoot { is_root_pipeline } => {
                           // Once we encounter a pipeline root, there is no need to look further
                           if is_root_pipeline {
                               break;
                           }
                       }
                       ScrollFrameKind::Explicit => {
                           // Store the closest scroll root we find to the root, for use
                           // later on, even if it's not actually scrollable.
                           outermost_scroll_root = node_index;

                           // If the previously identified scroll root is sticky then we don't
                           // want to choose an ancestor scroll root, as we want the sticky item
                           // to have its own picture cache slice.
                           if !current_scroll_root_is_sticky {
                               // If the scroll root has no scrollable area, we don't want to
                               // consider it. This helps pages that have a nested scroll root
                               // within a redundant scroll root to avoid selecting the wrong
                               // reference spatial node for a picture cache.
                               if info.scrollable_size.width > MIN_SCROLLABLE_AMOUNT ||
                                  info.scrollable_size.height > MIN_SCROLLABLE_AMOUNT {
                                   // Since we are skipping redundant scroll roots, we may end up
                                   // selecting inner scroll roots that are very small. There is
                                   // no performance benefit to creating a slice for these roots,
                                   // as they are cheap to rasterize. The size comparison is in
                                   // local-space, but makes for a reasonable estimate. The value
                                   // is arbitrary, but is generally small enough to ignore things
                                   // like scroll roots around text input elements.
                                   if info.viewport_rect.width() > MIN_SCROLL_ROOT_SIZE &&
                                      info.viewport_rect.height() > MIN_SCROLL_ROOT_SIZE {
                                       // If we've found a root that is scrollable, and a reasonable
                                       // size, select that as the current root for this node
                                       real_scroll_root = node_index;
                                   }
                               }
                           }
                       }
                   }
               }
           }
           node_index = node.parent.expect("unable to find parent node");
       }

       // If we didn't find any real (scrollable) frames, then return the outermost
       // redundant scroll frame. This is important so that we can correctly find
       // the clips defined on the content which should be handled when drawing the
       // picture cache tiles (by definition these clips are ancestors of the
       // scroll root selected for the picture cache).
       if real_scroll_root == self.root_reference_frame_index {
           outermost_scroll_root
       } else {
           real_scroll_root
       }
   }

   /// The root reference frame, which is the true root of the SpatialTree.
   pub fn root_reference_frame_index(&self) -> SpatialNodeIndex {
       self.root_reference_frame_index
   }

   fn add_spatial_node(
       &mut self,
       mut node: SceneSpatialNode,
       uid: SpatialNodeUid,
   ) -> SpatialNodeIndex {
       let parent_info = self.get_snapping_info(node.parent);

       node.snapping_transform = calculate_snapping_transform(
           parent_info,
           &node.descriptor.node_type,
       );

       // Ensure a node with the same uid hasn't been added during this scene build
       assert!(self.spatial_nodes_set.insert(uid), "duplicate key {:?}", uid);

       let index = match self.spatial_node_map.entry(uid) {
           Entry::Occupied(mut e) => {
               let e = e.get_mut();
               e.last_used = self.frame_counter;

               let existing_node = &self.spatial_nodes[e.index];

               if *existing_node != node {
                   self.updates.updates.push(SpatialTreeUpdate::Update {
                       index: e.index,
                       parent: node.parent,
                       descriptor: node.descriptor.clone(),
                   });
                   self.spatial_nodes.set(e.index, node);
               }

               e.index
           }
           Entry::Vacant(e) => {
               let descriptor = node.descriptor.clone();
               let parent = node.parent;

               let index = self.spatial_nodes.insert(node);

               e.insert(SpatialNodeEntry {
                   index,
                   last_used: self.frame_counter,
               });

               self.updates.updates.push(SpatialTreeUpdate::Insert {
                   index,
                   descriptor,
                   parent,
               });

               index
           }
       };

       SpatialNodeIndex(index as u32)
   }

   pub fn add_reference_frame(
       &mut self,
       parent_index: SpatialNodeIndex,
       transform_style: TransformStyle,
       source_transform: PropertyBinding<LayoutTransform>,
       kind: ReferenceFrameKind,
       origin_in_parent_reference_frame: LayoutVector2D,
       pipeline_id: PipelineId,
       uid: SpatialNodeUid,
   ) -> SpatialNodeIndex {
       // Determine if this reference frame creates a new static coordinate system
       let new_static_coord_system = match kind {
           ReferenceFrameKind::Transform { is_2d_scale_translation: true, .. } => {
               // Client has guaranteed this transform will only be axis-aligned
               false
           }
           ReferenceFrameKind::Transform { is_2d_scale_translation: false, .. } | ReferenceFrameKind::Perspective { .. } => {
               // Even if client hasn't promised it's an axis-aligned transform, we can still
               // check this so long as the transform isn't animated (and thus could change to
               // anything by APZ during frame building)
               match source_transform {
                   PropertyBinding::Value(m) => {
                       !m.is_2d_scale_translation()
                   }
                   PropertyBinding::Binding(..) => {
                       // Animated, so assume it may introduce a complex transform
                       true
                   }
               }
           }
       };

       let is_root_coord_system = !new_static_coord_system &&
           self.spatial_nodes[parent_index.0 as usize].is_root_coord_system;
       let is_pipeline_root = match uid.kind {
           SpatialNodeUidKind::InternalReferenceFrame { .. } => true,
           _ => false,
       };

       let node = SceneSpatialNode::new_reference_frame(
           Some(parent_index),
           transform_style,
           source_transform,
           kind,
           origin_in_parent_reference_frame,
           pipeline_id,
           is_root_coord_system,
           is_pipeline_root,
       );
       self.add_spatial_node(node, uid)
   }

   pub fn add_scroll_frame(
       &mut self,
       parent_index: SpatialNodeIndex,
       external_id: ExternalScrollId,
       pipeline_id: PipelineId,
       frame_rect: &LayoutRect,
       content_size: &LayoutSize,
       frame_kind: ScrollFrameKind,
       external_scroll_offset: LayoutVector2D,
       scroll_offset_generation: APZScrollGeneration,
       has_scroll_linked_effect: HasScrollLinkedEffect,
       uid: SpatialNodeUid,
   ) -> SpatialNodeIndex {
       // Scroll frames are only 2d translations - they can't introduce a new static coord system
       let is_root_coord_system = self.spatial_nodes[parent_index.0 as usize].is_root_coord_system;

       let node = SceneSpatialNode::new_scroll_frame(
           pipeline_id,
           parent_index,
           external_id,
           frame_rect,
           content_size,
           frame_kind,
           external_scroll_offset,
           scroll_offset_generation,
           has_scroll_linked_effect,
           is_root_coord_system,
       );
       self.add_spatial_node(node, uid)
   }

   pub fn add_sticky_frame(
       &mut self,
       parent_index: SpatialNodeIndex,
       sticky_frame_info: StickyFrameInfo,
       pipeline_id: PipelineId,
       key: SpatialTreeItemKey,
       instance_id: PipelineInstanceId,
   ) -> SpatialNodeIndex {
       // Sticky frames are only 2d translations - they can't introduce a new static coord system
       let is_root_coord_system = self.spatial_nodes[parent_index.0 as usize].is_root_coord_system;
       let uid = SpatialNodeUid::external(key, pipeline_id, instance_id);

       let node = SceneSpatialNode::new_sticky_frame(
           parent_index,
           sticky_frame_info,
           pipeline_id,
           is_root_coord_system,
       );
       self.add_spatial_node(node, uid)
   }
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub enum SpatialTreeUpdate {
   Insert {
       index: usize,
       parent: Option<SpatialNodeIndex>,
       descriptor: SpatialNodeDescriptor,
   },
   Update {
       index: usize,
       parent: Option<SpatialNodeIndex>,
       descriptor: SpatialNodeDescriptor,
   },
   Remove {
       index: usize,
   },
}

/// The delta updates to apply after building a new scene to the retained frame building
/// tree.
// TODO(gw): During the initial scaffolding work, this is the exact same as previous
//           behavior - that is, a complete list of new spatial nodes. In future, this
//           will instead be a list of deltas to apply to the frame spatial tree.
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct SpatialTreeUpdates {
   root_reference_frame_index: SpatialNodeIndex,
   updates: Vec<SpatialTreeUpdate>,
}

impl SpatialTreeUpdates {
   fn new() -> Self {
       SpatialTreeUpdates {
           root_reference_frame_index: SpatialNodeIndex::INVALID,
           updates: Vec::new(),
       }
   }
}

/// Represents the spatial tree during frame building, which is mostly
/// read-only, apart from the tree update at the start of the frame
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct SpatialTree {
   /// Nodes which determine the positions (offsets and transforms) for primitives
   /// and clips.
   spatial_nodes: Vec<SpatialNode>,

   /// A list of transforms that establish new coordinate systems.
   /// Spatial nodes only establish a new coordinate system when
   /// they have a transform that is not a simple 2d translation.
   coord_systems: Vec<CoordinateSystem>,

   root_reference_frame_index: SpatialNodeIndex,

   /// Stack of current state for each parent node while traversing and updating tree
   update_state_stack: Vec<TransformUpdateState>,

   next_internal_uid: u64,
}

#[derive(Clone)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct TransformUpdateState {
   pub parent_reference_frame_transform: LayoutToWorldFastTransform,
   pub parent_accumulated_scroll_offset: LayoutVector2D,
   pub nearest_scrolling_ancestor_offset: LayoutVector2D,
   pub nearest_scrolling_ancestor_viewport: LayoutRect,

   /// An id for keeping track of the axis-aligned space of this node. This is used in
   /// order to to track what kinds of clip optimizations can be done for a particular
   /// display list item, since optimizations can usually only be done among
   /// coordinate systems which are relatively axis aligned.
   pub current_coordinate_system_id: CoordinateSystemId,

   /// Scale and offset from the coordinate system that started this compatible coordinate system.
   pub coordinate_system_relative_scale_offset: ScaleOffset,

   /// True if this node is transformed by an invertible transform.  If not, display items
   /// transformed by this node will not be displayed and display items not transformed by this
   /// node will not be clipped by clips that are transformed by this node.
   pub invertible: bool,

   /// True if this node is a part of Preserve3D hierarchy.
   pub preserves_3d: bool,

   /// True if the any parent nodes are currently zooming
   pub is_ancestor_or_self_zooming: bool,

   /// Set to true if this state represents a scroll node with external id
   pub external_id: Option<ExternalScrollId>,

   /// The node scroll offset if this state is a scroll/sticky node. Zero if a reference frame.
   pub scroll_offset: LayoutVector2D,
}

/// Transformation between two nodes in the spatial tree that can sometimes be
/// encoded more efficiently than with a full matrix.
#[derive(Debug, Clone)]
pub enum CoordinateSpaceMapping<Src, Dst> {
   Local,
   ScaleOffset(ScaleOffset),
   Transform(Transform3D<f32, Src, Dst>),
}

impl<Src, Dst> CoordinateSpaceMapping<Src, Dst> {
   pub fn into_transform(self) -> Transform3D<f32, Src, Dst> {
       match self {
           CoordinateSpaceMapping::Local => Transform3D::identity(),
           CoordinateSpaceMapping::ScaleOffset(scale_offset) => scale_offset.to_transform(),
           CoordinateSpaceMapping::Transform(transform) => transform,
       }
   }

   pub fn into_fast_transform(self) -> FastTransform<Src, Dst> {
       match self {
           CoordinateSpaceMapping::Local => FastTransform::identity(),
           CoordinateSpaceMapping::ScaleOffset(scale_offset) => FastTransform::with_scale_offset(scale_offset),
           CoordinateSpaceMapping::Transform(transform) => FastTransform::with_transform(transform),
       }
   }

   pub fn is_perspective(&self) -> bool {
       match *self {
           CoordinateSpaceMapping::Local |
           CoordinateSpaceMapping::ScaleOffset(_) => false,
           CoordinateSpaceMapping::Transform(ref transform) => transform.has_perspective_component(),
       }
   }

   pub fn is_2d_axis_aligned(&self) -> bool {
       match *self {
           CoordinateSpaceMapping::Local |
           CoordinateSpaceMapping::ScaleOffset(_) => true,
           CoordinateSpaceMapping::Transform(ref transform) => transform.preserves_2d_axis_alignment(),
       }
   }

   pub fn is_2d_scale_translation(&self) -> bool {
       match *self {
           CoordinateSpaceMapping::Local |
           CoordinateSpaceMapping::ScaleOffset(_) => true,
           CoordinateSpaceMapping::Transform(ref transform) => transform.is_2d_scale_translation(),
       }
   }

   pub fn scale_factors(&self) -> (f32, f32) {
       match *self {
           CoordinateSpaceMapping::Local => (1.0, 1.0),
           CoordinateSpaceMapping::ScaleOffset(ref scale_offset) => (scale_offset.scale.x.abs(), scale_offset.scale.y.abs()),
           CoordinateSpaceMapping::Transform(ref transform) => scale_factors(transform),
       }
   }

   pub fn inverse(&self) -> Option<CoordinateSpaceMapping<Dst, Src>> {
       match *self {
           CoordinateSpaceMapping::Local => Some(CoordinateSpaceMapping::Local),
           CoordinateSpaceMapping::ScaleOffset(ref scale_offset) => {
               Some(CoordinateSpaceMapping::ScaleOffset(scale_offset.inverse()))
           }
           CoordinateSpaceMapping::Transform(ref transform) => {
               transform.inverse().map(CoordinateSpaceMapping::Transform)
           }
       }
   }

   pub fn as_2d_scale_offset(&self) -> Option<ScaleOffset> {
       Some(match *self {
           CoordinateSpaceMapping::Local => ScaleOffset::identity(),
           CoordinateSpaceMapping::ScaleOffset(transfrom) => transfrom,
           CoordinateSpaceMapping::Transform(ref transform) => {
               if !transform.is_2d_scale_translation() {
                   return None
               }
               ScaleOffset::new(transform.m11, transform.m22, transform.m41, transform.m42)
           }
       })
   }
}

enum TransformScroll {
   Scrolled,
   Unscrolled,
}

impl SpatialNodeContainer for SpatialTree {
   fn get_node_info(&self, index: SpatialNodeIndex) -> SpatialNodeInfo {
       let node = self.get_spatial_node(index);

       SpatialNodeInfo {
           parent: node.parent,
           node_type: &node.node_type,
           snapping_transform: node.snapping_transform,
       }
   }
}

impl SpatialTree {
   pub fn new() -> Self {
       SpatialTree {
           spatial_nodes: Vec::new(),
           coord_systems: Vec::new(),
           root_reference_frame_index: SpatialNodeIndex::INVALID,
           update_state_stack: Vec::new(),
           next_internal_uid: 1,
       }
   }

   fn visit_node_impl_mut<F>(
       &mut self,
       index: SpatialNodeIndex,
       f: &mut F,
   ) where F: FnMut(SpatialNodeIndex, &mut SpatialNode) {
       let mut child_indices: SmallVec<[SpatialNodeIndex; 8]> = SmallVec::new();

       let node = self.get_spatial_node_mut(index);
       f(index, node);
       child_indices.extend_from_slice(&node.children);

       for child_index in child_indices {
           self.visit_node_impl_mut(child_index, f);
       }
   }

   fn visit_node_impl<F>(
       &self,
       index: SpatialNodeIndex,
       f: &mut F,
   ) where F: FnMut(SpatialNodeIndex, &SpatialNode) {
       let node = self.get_spatial_node(index);

       f(index, node);

       for child_index in &node.children {
           self.visit_node_impl(*child_index, f);
       }
   }

   /// Visit all nodes from the root of the tree, invoking a closure on each one
   pub fn visit_nodes<F>(&self, mut f: F) where F: FnMut(SpatialNodeIndex, &SpatialNode) {
       if self.root_reference_frame_index == SpatialNodeIndex::INVALID {
           return;
       }

       self.visit_node_impl(self.root_reference_frame_index, &mut f);
   }

   /// Visit all nodes from the root of the tree, invoking a closure on each one
   pub fn visit_nodes_mut<F>(&mut self, mut f: F) where F: FnMut(SpatialNodeIndex, &mut SpatialNode) {
       if self.root_reference_frame_index == SpatialNodeIndex::INVALID {
           return;
       }

       self.visit_node_impl_mut(self.root_reference_frame_index, &mut f);
   }

   /// Apply updates from a new scene to the frame spatial tree
   pub fn apply_updates(
       &mut self,
       updates: SpatialTreeUpdates,
   ) {
       self.root_reference_frame_index = updates.root_reference_frame_index;

       for update in updates.updates {
           match update {
               SpatialTreeUpdate::Insert { index, parent, descriptor } => {
                   if let Some(parent) = parent {
                       self.get_spatial_node_mut(parent).add_child(SpatialNodeIndex(index as u32));
                   }

                   let uid = self.next_internal_uid;
                   self.next_internal_uid += 1;

                   let node = SpatialNode {
                       viewport_transform: ScaleOffset::identity(),
                       content_transform: ScaleOffset::identity(),
                       snapping_transform: None,
                       coordinate_system_id: CoordinateSystemId(0),
                       transform_kind: TransformedRectKind::AxisAligned,
                       parent,
                       children: Vec::new(),
                       pipeline_id: descriptor.pipeline_id,
                       node_type: descriptor.node_type,
                       invertible: true,
                       is_async_zooming: false,
                       is_ancestor_or_self_zooming: false,
                       uid,
                   };

                   assert!(index <= self.spatial_nodes.len());
                   if index < self.spatial_nodes.len() {
                       self.spatial_nodes[index] = node;
                   } else {
                       self.spatial_nodes.push(node);
                   }
               }
               SpatialTreeUpdate::Update { index, descriptor, parent } => {
                   let current_parent = self.spatial_nodes[index].parent;

                   if current_parent != parent {
                       if let Some(current_parent) = current_parent {
                           let i = self.spatial_nodes[current_parent.0 as usize]
                               .children
                               .iter()
                               .position(|e| e.0 as usize == index)
                               .expect("bug: not found!");
                           self.spatial_nodes[current_parent.0 as usize].children.remove(i);
                       }

                       let new_parent = parent.expect("todo: is this valid?");
                       self.spatial_nodes[new_parent.0 as usize].add_child(SpatialNodeIndex(index as u32));
                   }

                   let uid = self.next_internal_uid;
                   self.next_internal_uid += 1;

                   let node = &mut self.spatial_nodes[index];

                   node.node_type = descriptor.node_type;
                   node.pipeline_id = descriptor.pipeline_id;
                   node.parent = parent;
                   node.uid = uid;
               }
               SpatialTreeUpdate::Remove { index, .. } => {
                   let node = &mut self.spatial_nodes[index];

                   // Set the pipeline id to be invalid, so that even though this array
                   // entry still exists we can easily see it's invalid when debugging.
                   node.pipeline_id = PipelineId::dummy();

                   if let Some(parent) = node.parent {
                       let i = self.spatial_nodes[parent.0 as usize]
                           .children
                           .iter()
                           .position(|e| e.0 as usize == index)
                           .expect("bug: not found!");
                       self.spatial_nodes[parent.0 as usize].children.remove(i);
                   }
               }
           }
       }

       self.visit_nodes_mut(|_, node| {
           match node.node_type {
               SpatialNodeType::ScrollFrame(ref mut info) => {
                   info.offsets = vec![SampledScrollOffset{
                       offset: -info.external_scroll_offset,
                       generation: info.offset_generation,
                   }];
               }
               SpatialNodeType::StickyFrame(ref mut info) => {
                   info.current_offset = LayoutVector2D::zero();
               }
               SpatialNodeType::ReferenceFrame(..) => {}
           }
       });
   }

   pub fn get_last_sampled_scroll_offsets(
       &self,
   ) -> FastHashMap<ExternalScrollId, Vec<SampledScrollOffset>> {
       let mut result = FastHashMap::default();
       self.visit_nodes(|_, node| {
           if let SpatialNodeType::ScrollFrame(ref scrolling) = node.node_type {
               result.insert(scrolling.external_id, scrolling.offsets.clone());
           }
       });
       result
   }

   pub fn apply_last_sampled_scroll_offsets(
       &mut self,
       last_sampled_offsets: FastHashMap<ExternalScrollId, Vec<SampledScrollOffset>>,
   ) {
       self.visit_nodes_mut(|_, node| {
           if let SpatialNodeType::ScrollFrame(ref mut scrolling) = node.node_type {
               if let Some(offsets) = last_sampled_offsets.get(&scrolling.external_id) {
                   scrolling.offsets = offsets.clone();
               }
           }
       });
   }

   pub fn get_spatial_node(&self, index: SpatialNodeIndex) -> &SpatialNode {
       &self.spatial_nodes[index.0 as usize]
   }

   pub fn get_spatial_node_mut(&mut self, index: SpatialNodeIndex) -> &mut SpatialNode {
       &mut self.spatial_nodes[index.0 as usize]
   }

   /// Get total number of spatial nodes
   pub fn spatial_node_count(&self) -> usize {
       self.spatial_nodes.len()
   }

   pub fn find_spatial_node_by_anim_id(
       &self,
       id: PropertyBindingId,
   ) -> Option<SpatialNodeIndex> {
       let mut node_index = None;

       self.visit_nodes(|index, node| {
           if node.is_transform_bound_to_property(id) {
               debug_assert!(node_index.is_none());        // Multiple nodes with same anim id
               node_index = Some(index);
           }
       });

       node_index
   }

   /// Calculate the relative transform from `child_index` to `parent_index`.
   /// This method will panic if the nodes are not connected!
   pub fn get_relative_transform(
       &self,
       child_index: SpatialNodeIndex,
       parent_index: SpatialNodeIndex,
   ) -> CoordinateSpaceMapping<LayoutPixel, LayoutPixel> {
       self.get_relative_transform_with_face(child_index, parent_index, None)
   }

   /// Calculate the relative transform from `child_index` to `parent_index`.
   /// This method will panic if the nodes are not connected!
   /// Also, switch the visible face to `Back` if at any stage where the
   /// combined transform is flattened, we see the back face.
   pub fn get_relative_transform_with_face(
       &self,
       child_index: SpatialNodeIndex,
       parent_index: SpatialNodeIndex,
       mut visible_face: Option<&mut VisibleFace>,
   ) -> CoordinateSpaceMapping<LayoutPixel, LayoutPixel> {
       if child_index == parent_index {
           return CoordinateSpaceMapping::Local;
       }

       let child = self.get_spatial_node(child_index);
       let parent = self.get_spatial_node(parent_index);

       // TODO(gw): We expect this never to fail, but it's possible that it might due to
       //           either (a) a bug in WR / Gecko, or (b) some obscure real-world content
       //           that we're unaware of. If we ever hit this, please open a bug with any
       //           repro steps!
       assert!(
           child.coordinate_system_id.0 >= parent.coordinate_system_id.0,
           "bug: this is an unexpected case - please open a bug and talk to #gfx team!",
       );

       if child.coordinate_system_id == parent.coordinate_system_id {
           let scale_offset = child.content_transform.then(&parent.content_transform.inverse());
           return CoordinateSpaceMapping::ScaleOffset(scale_offset);
       }

       let mut coordinate_system_id = child.coordinate_system_id;
       let mut transform = child.content_transform.to_transform();

       // we need to update the associated parameters of a transform in two cases:
       // 1) when the flattening happens, so that we don't lose that original 3D aspects
       // 2) when we reach the end of iteration, so that our result is up to date

       while coordinate_system_id != parent.coordinate_system_id {
           let coord_system = &self.coord_systems[coordinate_system_id.0 as usize];

           if coord_system.should_flatten {
               if let Some(ref mut face) = visible_face {
                   if transform.is_backface_visible() {
                       **face = VisibleFace::Back;
                   }
               }
               transform.flatten_z_output();
           }

           coordinate_system_id = coord_system.parent.expect("invalid parent!");
           transform = transform.then(&coord_system.transform);
       }

       transform = transform.then(
           &parent.content_transform
               .inverse()
               .to_transform(),
       );
       if let Some(face) = visible_face {
           if transform.is_backface_visible() {
               *face = VisibleFace::Back;
           }
       }

       CoordinateSpaceMapping::Transform(transform)
   }

   /// Returns true if both supplied spatial nodes are in the same coordinate system
   /// (implies the relative transform produce axis-aligned rects).
   pub fn is_matching_coord_system(
       &self,
       index0: SpatialNodeIndex,
       index1: SpatialNodeIndex,
   ) -> bool {
       let node0 = self.get_spatial_node(index0);
       let node1 = self.get_spatial_node(index1);

       node0.coordinate_system_id == node1.coordinate_system_id
   }

   fn get_world_transform_impl(
       &self,
       index: SpatialNodeIndex,
       scroll: TransformScroll,
   ) -> CoordinateSpaceMapping<LayoutPixel, WorldPixel> {
       let child = self.get_spatial_node(index);

       if child.coordinate_system_id.0 == 0 {
           if index == self.root_reference_frame_index {
               CoordinateSpaceMapping::Local
           } else {
             match scroll {
               TransformScroll::Scrolled => CoordinateSpaceMapping::ScaleOffset(child.content_transform),
               TransformScroll::Unscrolled => CoordinateSpaceMapping::ScaleOffset(child.viewport_transform),
             }
           }
       } else {
           let system = &self.coord_systems[child.coordinate_system_id.0 as usize];
           let scale_offset = match scroll {
               TransformScroll::Scrolled => &child.content_transform,
               TransformScroll::Unscrolled => &child.viewport_transform,
           };
           let transform = scale_offset
               .to_transform()
               .then(&system.world_transform);

           CoordinateSpaceMapping::Transform(transform)
       }
   }

   /// Calculate the relative transform from `index` to the root.
   pub fn get_world_transform(
       &self,
       index: SpatialNodeIndex,
   ) -> CoordinateSpaceMapping<LayoutPixel, WorldPixel> {
       self.get_world_transform_impl(index, TransformScroll::Scrolled)
   }

   /// Calculate the relative transform from `index` to the root.
   /// Unlike `get_world_transform`, this variant doesn't account for the local scroll offset.
   pub fn get_world_viewport_transform(
       &self,
       index: SpatialNodeIndex,
   ) -> CoordinateSpaceMapping<LayoutPixel, WorldPixel> {
       self.get_world_transform_impl(index, TransformScroll::Unscrolled)
   }

   /// The root reference frame, which is the true root of the SpatialTree.
   pub fn root_reference_frame_index(&self) -> SpatialNodeIndex {
       self.root_reference_frame_index
   }

   pub fn set_scroll_offsets(
       &mut self,
       id: ExternalScrollId,
       offsets: Vec<SampledScrollOffset>,
   ) -> bool {
       let mut did_change = false;

       self.visit_nodes_mut(|_, node| {
           if node.matches_external_id(id) {
               did_change |= node.set_scroll_offsets(offsets.clone());
           }
       });

       did_change
   }

   pub fn update_tree(
       &mut self,
       scene_properties: &SceneProperties,
   ) {
       if self.root_reference_frame_index == SpatialNodeIndex::INVALID {
           return;
       }

       profile_scope!("update_tree");
       self.coord_systems.clear();
       self.coord_systems.push(CoordinateSystem::root());

       let root_node_index = self.root_reference_frame_index();
       assert!(self.update_state_stack.is_empty());

       let state = TransformUpdateState {
           parent_reference_frame_transform: LayoutVector2D::zero().into(),
           parent_accumulated_scroll_offset: LayoutVector2D::zero(),
           nearest_scrolling_ancestor_offset: LayoutVector2D::zero(),
           nearest_scrolling_ancestor_viewport: LayoutRect::zero(),
           current_coordinate_system_id: CoordinateSystemId::root(),
           coordinate_system_relative_scale_offset: ScaleOffset::identity(),
           invertible: true,
           preserves_3d: false,
           is_ancestor_or_self_zooming: false,
           external_id: None,
           scroll_offset: LayoutVector2D::zero(),
       };
       self.update_state_stack.push(state);

       self.update_node(
           root_node_index,
           scene_properties,
       );

       self.update_state_stack.pop().unwrap();
   }

   fn update_node(
       &mut self,
       node_index: SpatialNodeIndex,
       scene_properties: &SceneProperties,
   ) {
       let parent_index = self.get_spatial_node(node_index).parent;
       let parent_info = self.get_snapping_info(parent_index);

       let node = &mut self.spatial_nodes[node_index.0 as usize];

       node.snapping_transform = calculate_snapping_transform(
           parent_info,
           &node.node_type,
       );

       node.update(
           &self.update_state_stack,
           &mut self.coord_systems,
           scene_properties,
       );

       if !node.children.is_empty() {
           let mut child_state = self.update_state_stack.last().unwrap().clone();
           node.prepare_state_for_children(&mut child_state);
           self.update_state_stack.push(child_state);

           let mut child_indices: SmallVec<[SpatialNodeIndex; 8]> = SmallVec::new();
           child_indices.extend_from_slice(&node.children);

           for child_index in child_indices {
               self.update_node(
                   child_index,
                   scene_properties,
               );
           }

           self.update_state_stack.pop().unwrap();
       }
   }

   pub fn build_transform_palette(&self, memory: &FrameMemory) -> TransformPalette {
       profile_scope!("build_transform_palette");
       TransformPalette::new(self.spatial_nodes.len(), memory)
   }

   fn print_node<T: PrintTreePrinter>(
       &self,
       index: SpatialNodeIndex,
       pt: &mut T,
   ) {
       let node = self.get_spatial_node(index);
       match node.node_type {
           SpatialNodeType::StickyFrame(ref sticky_frame_info) => {
               pt.new_level(format!("StickyFrame"));
               pt.add_item(format!("sticky info: {:?}", sticky_frame_info));
           }
           SpatialNodeType::ScrollFrame(ref scrolling_info) => {
               pt.new_level(format!("ScrollFrame"));
               pt.add_item(format!("viewport: {:?}", scrolling_info.viewport_rect));
               pt.add_item(format!("scrollable_size: {:?}", scrolling_info.scrollable_size));
               pt.add_item(format!("scroll offset: {:?}", scrolling_info.offset()));
               pt.add_item(format!("external_scroll_offset: {:?}", scrolling_info.external_scroll_offset));
               pt.add_item(format!("offset generation: {:?}", scrolling_info.offset_generation));
               if scrolling_info.has_scroll_linked_effect == HasScrollLinkedEffect::Yes {
                   pt.add_item("has scroll-linked effect".to_string());
               }
               pt.add_item(format!("kind: {:?}", scrolling_info.frame_kind));
           }
           SpatialNodeType::ReferenceFrame(ref info) => {
               pt.new_level(format!("ReferenceFrame"));
               pt.add_item(format!("kind: {:?}", info.kind));
               pt.add_item(format!("transform_style: {:?}", info.transform_style));
               pt.add_item(format!("source_transform: {:?}", info.source_transform));
               pt.add_item(format!("origin_in_parent_reference_frame: {:?}", info.origin_in_parent_reference_frame));
           }
       }

       pt.add_item(format!("index: {:?}", index));
       pt.add_item(format!("content_transform: {:?}", node.content_transform));
       pt.add_item(format!("viewport_transform: {:?}", node.viewport_transform));
       pt.add_item(format!("snapping_transform: {:?}", node.snapping_transform));
       pt.add_item(format!("coordinate_system_id: {:?}", node.coordinate_system_id));

       for child_index in &node.children {
           self.print_node(*child_index, pt);
       }

       pt.end_level();
   }

   /// Get the visible face of the transfrom from the specified node to its parent.
   pub fn get_local_visible_face(&self, node_index: SpatialNodeIndex) -> VisibleFace {
       let node = self.get_spatial_node(node_index);
       let mut face = VisibleFace::Front;
       if let Some(mut parent_index) = node.parent {
           // Check if the parent is perspective. In CSS, a stacking context may
           // have both perspective and a regular transformation. Gecko translates the
           // perspective into a different `nsDisplayPerspective` and `nsDisplayTransform` items.
           // On WebRender side, we end up with 2 different reference frames:
           // one has kind of "transform", and it's parented to another of "perspective":
           // https://searchfox.org/mozilla-central/rev/72c7cef167829b6f1e24cae216fa261934c455fc/layout/generic/nsIFrame.cpp#3716
           if let SpatialNodeType::ReferenceFrame(ReferenceFrameInfo { kind: ReferenceFrameKind::Transform {
               paired_with_perspective: true,
               ..
           }, .. }) = node.node_type {
               let parent = self.get_spatial_node(parent_index);
               match parent.node_type {
                   SpatialNodeType::ReferenceFrame(ReferenceFrameInfo {
                       kind: ReferenceFrameKind::Perspective { .. },
                       ..
                   }) => {
                       parent_index = parent.parent.unwrap();
                   }
                   _ => {
                       log::error!("Unexpected parent {:?} is not perspective", parent_index);
                   }
               }
           }

           self.get_relative_transform_with_face(node_index, parent_index, Some(&mut face));
       }
       face
   }

   #[allow(dead_code)]
   pub fn print_to_string(&self) -> String {
       let mut result = String::new();

       if self.root_reference_frame_index != SpatialNodeIndex::INVALID {
           let mut buf = Vec::<u8>::new();
           {
               let mut pt = PrintTree::new_with_sink("spatial tree", &mut buf);
               self.print_with(&mut pt);
           }
           result = std::str::from_utf8(&buf).unwrap_or("(Tree printer emitted non-utf8)").to_string();
       }

       result
   }

   #[allow(dead_code)]
   pub fn print(&self) {
       let result = self.print_to_string();
       // If running in Gecko, set RUST_LOG=webrender::spatial_tree=debug
       // to get this logging to be emitted to stderr/logcat.
       debug!("{}", result);
   }
}

impl PrintableTree for SpatialTree {
   fn print_with<T: PrintTreePrinter>(&self, pt: &mut T) {
       if self.root_reference_frame_index != SpatialNodeIndex::INVALID {
           self.print_node(self.root_reference_frame_index(), pt);
       }
   }
}

/// Calculate the accumulated external scroll offset for a given spatial node.
pub fn get_external_scroll_offset<S: SpatialNodeContainer>(
   spatial_tree: &S,
   node_index: SpatialNodeIndex,
) -> LayoutVector2D {
   let mut offset = LayoutVector2D::zero();
   let mut current_node = Some(node_index);

   while let Some(node_index) = current_node {
       let node_info = spatial_tree.get_node_info(node_index);

       match node_info.node_type {
           SpatialNodeType::ScrollFrame(ref scrolling) => {
               offset += scrolling.external_scroll_offset;
           }
           SpatialNodeType::StickyFrame(ref sticky) => {
               // Remove the sticky offset that was applied in the
               // content process, so that primitive interning
               // sees stable values, and doesn't invalidate unnecessarily.
               offset -= sticky.previously_applied_offset;
           }
           SpatialNodeType::ReferenceFrame(..) => {
               // External scroll offsets are not propagated across
               // reference frames.
               break;
           }
       }

       current_node = node_info.parent;
   }

   offset
}

fn calculate_snapping_transform(
   parent_scale_offset: Option<ScaleOffset>,
   node_type: &SpatialNodeType,
) -> Option<ScaleOffset> {
   // We need to incorporate the parent scale/offset with the child.
   // If the parent does not have a scale/offset, then we know we are
   // not 2d axis aligned and thus do not need to snap its children
   // either.
   let parent_scale_offset = match parent_scale_offset {
       Some(transform) => transform,
       None => return None,
   };

   let scale_offset = match node_type {
       SpatialNodeType::ReferenceFrame(ref info) => {
           let origin_offset = info.origin_in_parent_reference_frame;

           match info.source_transform {
               PropertyBinding::Value(ref value) => {
                   // We can only get a ScaleOffset if the transform is 2d axis
                   // aligned.
                   match ScaleOffset::from_transform(value) {
                       Some(scale_offset) => {
                           scale_offset.then(&ScaleOffset::from_offset(origin_offset.to_untyped()))
                       }
                       None => return None,
                   }
               }

               // Assume animations start at the identity transform for snapping purposes.
               // We still want to incorporate the reference frame offset however.
               // TODO(aosmond): Is there a better known starting point?
               PropertyBinding::Binding(..) => {
                   ScaleOffset::from_offset(origin_offset.to_untyped())
               }
           }
       }
       _ => ScaleOffset::identity(),
   };

   Some(scale_offset.then(&parent_scale_offset))
}

#[cfg(test)]
fn add_reference_frame(
   cst: &mut SceneSpatialTree,
   parent: SpatialNodeIndex,
   transform: LayoutTransform,
   origin_in_parent_reference_frame: LayoutVector2D,
   key: SpatialTreeItemKey,
) -> SpatialNodeIndex {
   let pid = PipelineInstanceId::new(0);

   cst.add_reference_frame(
       parent,
       TransformStyle::Preserve3D,
       PropertyBinding::Value(transform),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: false,
           should_snap: false,
           paired_with_perspective: false,
       },
       origin_in_parent_reference_frame,
       PipelineId::dummy(),
       SpatialNodeUid::external(key, PipelineId::dummy(), pid),
   )
}

#[cfg(test)]
fn test_pt(
   px: f32,
   py: f32,
   cst: &SpatialTree,
   child: SpatialNodeIndex,
   parent: SpatialNodeIndex,
   expected_x: f32,
   expected_y: f32,
) {
   use euclid::approxeq::ApproxEq;
   const EPSILON: f32 = 0.0001;

   let p = LayoutPoint::new(px, py);
   let m = cst.get_relative_transform(child, parent).into_transform();
   let pt = m.transform_point2d(p).unwrap();
   assert!(pt.x.approx_eq_eps(&expected_x, &EPSILON) &&
           pt.y.approx_eq_eps(&expected_y, &EPSILON),
           "p: {:?} -> {:?}\nm={:?}",
           p, pt, m,
           );
}

#[test]
fn test_cst_simple_translation() {
   // Basic translations only

   let mut cst = SceneSpatialTree::new();
   let root_reference_frame_index = cst.root_reference_frame_index();

   let root = add_reference_frame(
       &mut cst,
       root_reference_frame_index,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 0),
   );

   let child1 = add_reference_frame(
       &mut cst,
       root,
       LayoutTransform::translation(100.0, 0.0, 0.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 1),
   );

   let child2 = add_reference_frame(
       &mut cst,
       child1,
       LayoutTransform::translation(0.0, 50.0, 0.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 2),
   );

   let child3 = add_reference_frame(
       &mut cst,
       child2,
       LayoutTransform::translation(200.0, 200.0, 0.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 3),
   );

   let mut st = SpatialTree::new();
   st.apply_updates(cst.end_frame_and_get_pending_updates());
   st.update_tree(&SceneProperties::new());

   test_pt(100.0, 100.0, &st, child1, root, 200.0, 100.0);
   test_pt(100.0, 100.0, &st, child2, root, 200.0, 150.0);
   test_pt(100.0, 100.0, &st, child2, child1, 100.0, 150.0);
   test_pt(100.0, 100.0, &st, child3, root, 400.0, 350.0);
}

#[test]
fn test_cst_simple_scale() {
   // Basic scale only

   let mut cst = SceneSpatialTree::new();
   let root_reference_frame_index = cst.root_reference_frame_index();

   let root = add_reference_frame(
       &mut cst,
       root_reference_frame_index,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 0),
   );

   let child1 = add_reference_frame(
       &mut cst,
       root,
       LayoutTransform::scale(4.0, 1.0, 1.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 1),
   );

   let child2 = add_reference_frame(
       &mut cst,
       child1,
       LayoutTransform::scale(1.0, 2.0, 1.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 2),
   );

   let child3 = add_reference_frame(
       &mut cst,
       child2,
       LayoutTransform::scale(2.0, 2.0, 1.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 3),
   );

   let mut st = SpatialTree::new();
   st.apply_updates(cst.end_frame_and_get_pending_updates());
   st.update_tree(&SceneProperties::new());

   test_pt(100.0, 100.0, &st, child1, root, 400.0, 100.0);
   test_pt(100.0, 100.0, &st, child2, root, 400.0, 200.0);
   test_pt(100.0, 100.0, &st, child3, root, 800.0, 400.0);
   test_pt(100.0, 100.0, &st, child2, child1, 100.0, 200.0);
   test_pt(100.0, 100.0, &st, child3, child1, 200.0, 400.0);
}

#[test]
fn test_cst_scale_translation() {
   // Scale + translation

   let mut cst = SceneSpatialTree::new();
   let root_reference_frame_index = cst.root_reference_frame_index();

   let root = add_reference_frame(
       &mut cst,
       root_reference_frame_index,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 0),
   );

   let child1 = add_reference_frame(
       &mut cst,
       root,
       LayoutTransform::translation(100.0, 50.0, 0.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 1),
   );

   let child2 = add_reference_frame(
       &mut cst,
       child1,
       LayoutTransform::scale(2.0, 4.0, 1.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 2),
   );

   let child3 = add_reference_frame(
       &mut cst,
       child2,
       LayoutTransform::translation(200.0, -100.0, 0.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 3),
   );

   let child4 = add_reference_frame(
       &mut cst,
       child3,
       LayoutTransform::scale(3.0, 2.0, 1.0),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 4),
   );

   let mut st = SpatialTree::new();
   st.apply_updates(cst.end_frame_and_get_pending_updates());
   st.update_tree(&SceneProperties::new());

   test_pt(100.0, 100.0, &st, child1, root, 200.0, 150.0);
   test_pt(100.0, 100.0, &st, child2, root, 300.0, 450.0);
   test_pt(100.0, 100.0, &st, child4, root, 1100.0, 450.0);

   test_pt(0.0, 0.0, &st, child4, child1, 400.0, -400.0);
   test_pt(100.0, 100.0, &st, child4, child1, 1000.0, 400.0);
   test_pt(100.0, 100.0, &st, child2, child1, 200.0, 400.0);

   test_pt(100.0, 100.0, &st, child3, child1, 600.0, 0.0);
}

#[test]
fn test_cst_translation_rotate() {
   // Rotation + translation
   use euclid::Angle;

   let mut cst = SceneSpatialTree::new();
   let root_reference_frame_index = cst.root_reference_frame_index();

   let root = add_reference_frame(
       &mut cst,
       root_reference_frame_index,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 0),
   );

   let child1 = add_reference_frame(
       &mut cst,
       root,
       LayoutTransform::rotation(0.0, 0.0, 1.0, Angle::degrees(-90.0)),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 1),
   );

   let mut st = SpatialTree::new();
   st.apply_updates(cst.end_frame_and_get_pending_updates());
   st.update_tree(&SceneProperties::new());

   test_pt(100.0, 0.0, &st, child1, root, 0.0, -100.0);
}

#[test]
fn test_is_ancestor1() {
   let mut st = SceneSpatialTree::new();
   let root_reference_frame_index = st.root_reference_frame_index();

   let root = add_reference_frame(
       &mut st,
       root_reference_frame_index,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 0),
   );

   let child1_0 = add_reference_frame(
       &mut st,
       root,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 1),
   );

   let child1_1 = add_reference_frame(
       &mut st,
       child1_0,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 2),
   );

   let child2 = add_reference_frame(
       &mut st,
       root,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 3),
   );

   assert!(!st.is_ancestor(root, root));
   assert!(!st.is_ancestor(child1_0, child1_0));
   assert!(!st.is_ancestor(child1_1, child1_1));
   assert!(!st.is_ancestor(child2, child2));

   assert!(st.is_ancestor(root, child1_0));
   assert!(st.is_ancestor(root, child1_1));
   assert!(st.is_ancestor(child1_0, child1_1));

   assert!(!st.is_ancestor(child1_0, root));
   assert!(!st.is_ancestor(child1_1, root));
   assert!(!st.is_ancestor(child1_1, child1_0));

   assert!(st.is_ancestor(root, child2));
   assert!(!st.is_ancestor(child2, root));

   assert!(!st.is_ancestor(child1_0, child2));
   assert!(!st.is_ancestor(child1_1, child2));
   assert!(!st.is_ancestor(child2, child1_0));
   assert!(!st.is_ancestor(child2, child1_1));
}

/// Tests that we select the correct scroll root in the simple case.
#[test]
fn test_find_scroll_root_simple() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   assert_eq!(st.find_scroll_root(scroll, true), scroll);
}

/// Tests that we select the root scroll frame rather than the subframe if both are scrollable.
#[test]
fn test_find_scroll_root_sub_scroll_frame() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let root_scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   let sub_scroll = st.add_scroll_frame(
       root_scroll,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
   );

   assert_eq!(st.find_scroll_root(sub_scroll, true), root_scroll);
}

/// Tests that we select the sub scroll frame when the root scroll frame is not scrollable.
#[test]
fn test_find_scroll_root_not_scrollable() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let root_scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(400.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   let sub_scroll = st.add_scroll_frame(
       root_scroll,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
   );

   assert_eq!(st.find_scroll_root(sub_scroll, true), sub_scroll);
}

/// Tests that we select the sub scroll frame when the root scroll frame is too small.
#[test]
fn test_find_scroll_root_too_small() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let root_scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(MIN_SCROLL_ROOT_SIZE, MIN_SCROLL_ROOT_SIZE)),
       &LayoutSize::new(1000.0, 1000.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   let sub_scroll = st.add_scroll_frame(
       root_scroll,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
   );

   assert_eq!(st.find_scroll_root(sub_scroll, true), sub_scroll);
}

/// Tests that we select the root scroll node, even if it is not scrollable,
/// when encountering a non-axis-aligned transform.
#[test]
fn test_find_scroll_root_perspective() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let root_scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(400.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   let perspective = st.add_reference_frame(
       root_scroll,
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Perspective {
           scrolling_relative_to: None,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
   );

   let sub_scroll = st.add_scroll_frame(
       perspective,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 3), PipelineId::dummy(), pid),
   );

   assert_eq!(st.find_scroll_root(sub_scroll, true), root_scroll);
}

/// Tests that encountering a 2D scale or translation transform does not prevent
/// us from selecting the sub scroll frame if the root scroll frame is unscrollable.
#[test]
fn test_find_scroll_root_2d_scale() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let root_scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(400.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   let scale = st.add_reference_frame(
       root_scroll,
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: false,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
   );

   let sub_scroll = st.add_scroll_frame(
       scale,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(800.0, 400.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 3), PipelineId::dummy(), pid),
   );

   assert_eq!(st.find_scroll_root(sub_scroll, true), sub_scroll);
}

/// Tests that a sticky spatial node is chosen as the scroll root rather than
/// its parent scroll frame
#[test]
fn test_find_scroll_root_sticky() {
   let mut st = SceneSpatialTree::new();
   let pid = PipelineInstanceId::new(0);

   let root = st.add_reference_frame(
       st.root_reference_frame_index(),
       TransformStyle::Flat,
       PropertyBinding::Value(LayoutTransform::identity()),
       ReferenceFrameKind::Transform {
           is_2d_scale_translation: true,
           should_snap: true,
           paired_with_perspective: false,
       },
       LayoutVector2D::new(0.0, 0.0),
       PipelineId::dummy(),
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
   );

   let scroll = st.add_scroll_frame(
       root,
       ExternalScrollId(1, PipelineId::dummy()),
       PipelineId::dummy(),
       &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
       &LayoutSize::new(400.0, 800.0),
       ScrollFrameKind::Explicit,
       LayoutVector2D::new(0.0, 0.0),
       APZScrollGeneration::default(),
       HasScrollLinkedEffect::No,
       SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
   );

   let sticky = st.add_sticky_frame(
       scroll,
       StickyFrameInfo {
           frame_rect: LayoutRect::from_size(LayoutSize::new(400.0, 100.0)),
           margins: euclid::SideOffsets2D::new(Some(0.0), None, None, None),
           vertical_offset_bounds: api::StickyOffsetBounds::new(0.0, 0.0),
           horizontal_offset_bounds: api::StickyOffsetBounds::new(0.0, 0.0),
           previously_applied_offset: LayoutVector2D::zero(),
           current_offset: LayoutVector2D::zero(),
           transform: None
       },
       PipelineId::dummy(),
       SpatialTreeItemKey::new(0, 2),
       pid,
   );

   assert_eq!(st.find_scroll_root(sticky, true), sticky);
   assert_eq!(st.find_scroll_root(sticky, false), scroll);
}

#[test]
fn test_world_transforms() {
 // Create a spatial tree with a scroll frame node with scroll offset (0, 200).
 let mut cst = SceneSpatialTree::new();
 let pid = PipelineInstanceId::new(0);
 let scroll = cst.add_scroll_frame(
     cst.root_reference_frame_index(),
     ExternalScrollId(1, PipelineId::dummy()),
     PipelineId::dummy(),
     &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
     &LayoutSize::new(400.0, 800.0),
     ScrollFrameKind::Explicit,
     LayoutVector2D::new(0.0, 200.0),
     APZScrollGeneration::default(),
     HasScrollLinkedEffect::No,
     SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid));

 let mut st = SpatialTree::new();
 st.apply_updates(cst.end_frame_and_get_pending_updates());
 st.update_tree(&SceneProperties::new());

 // The node's world transform should reflect the scroll offset,
 // e.g. here it should be (0, -200) to reflect that the content has been
 // scrolled up by 200px.
 assert_eq!(
     st.get_world_transform(scroll).into_transform(),
     LayoutToWorldTransform::translation(0.0, -200.0, 0.0));

 // The node's world viewport transform only reflects enclosing scrolling
 // or transforms. Here we don't have any, so it should be the identity.
 assert_eq!(
     st.get_world_viewport_transform(scroll).into_transform(),
     LayoutToWorldTransform::identity());
}

/// Tests that a spatial node that is async zooming and all of its descendants
/// are correctly marked as having themselves an ancestor that is zooming.
#[test]
fn test_is_ancestor_or_self_zooming() {
   let mut cst = SceneSpatialTree::new();
   let root_reference_frame_index = cst.root_reference_frame_index();

   let root = add_reference_frame(
       &mut cst,
       root_reference_frame_index,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 0),
   );
   let child1 = add_reference_frame(
       &mut cst,
       root,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 1),
   );
   let child2 = add_reference_frame(
       &mut cst,
       child1,
       LayoutTransform::identity(),
       LayoutVector2D::zero(),
       SpatialTreeItemKey::new(0, 2),
   );

   let mut st = SpatialTree::new();
   st.apply_updates(cst.end_frame_and_get_pending_updates());

   // Mark the root node as async zooming
   st.get_spatial_node_mut(root).is_async_zooming = true;
   st.update_tree(&SceneProperties::new());

   // Ensure that the root node and all descendants are marked as having
   // themselves or an ancestor zooming
   assert!(st.get_spatial_node(root).is_ancestor_or_self_zooming);
   assert!(st.get_spatial_node(child1).is_ancestor_or_self_zooming);
   assert!(st.get_spatial_node(child2).is_ancestor_or_self_zooming);
}