/* 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, 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, } 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 { Empty, Occupied(T), } #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] struct Store { elements: Vec>, free_indices: Vec, } impl Store { 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 ops::Index for Store { 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 ops::IndexMut for Store { 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, /// 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, 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, } 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, 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, descriptor: SpatialNodeDescriptor, }, Update { index: usize, parent: Option, 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, } 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, /// 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, root_reference_frame_index: SpatialNodeIndex, /// Stack of current state for each parent node while traversing and updating tree update_state_stack: Vec, } #[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, /// 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 { Local, ScaleOffset(ScaleOffset), Transform(Transform3D), } impl CoordinateSpaceMapping { pub fn into_transform(self) -> Transform3D { 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 { 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> { 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( &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( &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(&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(&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> { 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>, ) { 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 { 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 { 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 { 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 { 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 { 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 { 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, ) -> 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( &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::::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(&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( 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, node_type: &SpatialNodeType, ) -> Option { // 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); } #[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); }