Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1998 insertions, 0 deletions

diff --git a/gfx/wr/webrender/src/spatial_tree.rs b/gfx/wr/webrender/src/spatial_tree.rs
new file mode 100644
index 0000000000..bdb62c81a0
--- /dev/null
+++ b/gfx/wr/webrender/src/spatial_tree.rs
@@ -0,0 +1,1998 @@
+/* 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, PipelineInstanceId};
+use crate::print_tree::{PrintableTree, PrintTree, PrintTreePrinter};
+use crate::scene::SceneProperties;
+use crate::spatial_node::{ReferenceFrameInfo, SpatialNode, SpatialNodeType, StickyFrameInfo, SpatialNodeDescriptor};
+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)]
+#[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;
+}
+
+#[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,
+    ) -> SpatialNodeIndex {
+        let mut real_scroll_root = self.root_reference_frame_index;
+        let mut outermost_scroll_root = self.root_reference_frame_index;
+        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;
+                        }
+                    }
+                }
+                SpatialNodeType::StickyFrame(..) => {}
+                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 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_snapping_transform = match node.parent {
+            Some(parent_index) => {
+                self.get_node_info(parent_index).snapping_transform
+            }
+            None => {
+                Some(ScaleOffset::identity())
+            }
+        };
+
+        node.snapping_transform = calculate_snapping_transform(
+            parent_snapping_transform,
+            &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>,
+}
+
+#[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 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)
+            }
+        }
+    }
+}
+
+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(),
+        }
+    }
+
+    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 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,
+                    };
+
+                    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 node = &mut self.spatial_nodes[index];
+
+                    node.node_type = descriptor.node_type;
+                    node.pipeline_id = descriptor.pipeline_id;
+                    node.parent = parent;
+                }
+                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 = parent.content_transform
+                .inverse()
+                .accumulate(&child.content_transform);
+            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 {
+                CoordinateSpaceMapping::ScaleOffset(child.content_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_snapping_transform = match self.get_spatial_node(node_index).parent {
+            Some(parent_index) => {
+                self.get_node_info(parent_index).snapping_transform
+            }
+            None => {
+                Some(ScaleOffset::identity())
+            }
+        };
+
+        let node = &mut self.spatial_nodes[node_index.0 as usize];
+
+        node.snapping_transform = calculate_snapping_transform(
+            parent_snapping_transform,
+            &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) -> TransformPalette {
+        profile_scope!("build_transform_palette");
+        TransformPalette::new(self.spatial_nodes.len())
+    }
+
+    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(&self) {
+        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);
+            }
+            // If running in Gecko, set RUST_LOG=webrender::spatial_tree=debug
+            // to get this logging to be emitted to stderr/logcat.
+            debug!("{}", std::str::from_utf8(&buf).unwrap_or("(Tree printer emitted non-utf8)"));
+        }
+    }
+}
+
+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(..) => {
+                // Doesn't provide any external scroll offset
+            }
+            SpatialNodeType::ReferenceFrame(..) => {
+                // External scroll offsets are not propagated across
+                // reference frames.
+                break;
+            }
+        }
+
+        current_node = node_info.parent;
+    }
+
+    offset
+}
+
+fn calculate_snapping_transform(
+    parent_snapping_transform: 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_snapping_transform {
+        Some(parent_snapping_transform) => parent_snapping_transform,
+        None => return None,
+    };
+
+    let scale_offset = match node_type {
+        SpatialNodeType::ReferenceFrame(ref info) => {
+            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) => {
+                            let origin_offset = info.origin_in_parent_reference_frame;
+                            ScaleOffset::from_offset(origin_offset.to_untyped())
+                                .accumulate(&scale_offset)
+                        }
+                        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(..) => {
+                    let origin_offset = info.origin_in_parent_reference_frame;
+                    ScaleOffset::from_offset(origin_offset.to_untyped())
+                }
+            }
+        }
+        _ => ScaleOffset::identity(),
+    };
+
+    Some(parent_scale_offset.accumulate(&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), 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), 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), 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), 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), 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), sub_scroll);
+}