webrender/
spatial_tree.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5use api::{ExternalScrollId, PropertyBinding, ReferenceFrameKind, TransformStyle, PropertyBindingId};
6use api::{APZScrollGeneration, HasScrollLinkedEffect, PipelineId, SampledScrollOffset, SpatialTreeItemKey};
7use api::units::*;
8use euclid::Transform3D;
9use crate::gpu_types::TransformPalette;
10use crate::internal_types::{FastHashMap, FastHashSet, FrameMemory, PipelineInstanceId};
11use crate::print_tree::{PrintableTree, PrintTree, PrintTreePrinter};
12use crate::scene::SceneProperties;
13use crate::spatial_node::{ReferenceFrameInfo, SpatialNode, SpatialNodeType, StickyFrameInfo, SpatialNodeDescriptor};
14use crate::spatial_node::{SpatialNodeUid, ScrollFrameKind, SceneSpatialNode, SpatialNodeInfo, SpatialNodeUidKind};
15use std::{ops, u32};
16use crate::util::{FastTransform, LayoutToWorldFastTransform, MatrixHelpers, ScaleOffset, scale_factors};
17use smallvec::SmallVec;
18use std::collections::hash_map::Entry;
19use crate::util::TransformedRectKind;
20use peek_poke::PeekPoke;
21
22
23/// An id that identifies coordinate systems in the SpatialTree. Each
24/// coordinate system has an id and those ids will be shared when the coordinates
25/// system are the same or are in the same axis-aligned space. This allows
26/// for optimizing mask generation.
27#[derive(Debug, Copy, Clone, PartialEq, PartialOrd)]
28#[cfg_attr(feature = "capture", derive(Serialize))]
29#[cfg_attr(feature = "replay", derive(Deserialize))]
30pub struct CoordinateSystemId(pub u32);
31
32/// A node in the hierarchy of coordinate system
33/// transforms.
34#[derive(Debug)]
35#[cfg_attr(feature = "capture", derive(Serialize))]
36#[cfg_attr(feature = "replay", derive(Deserialize))]
37pub struct CoordinateSystem {
38    pub transform: LayoutTransform,
39    pub world_transform: LayoutToWorldTransform,
40    pub should_flatten: bool,
41    pub parent: Option<CoordinateSystemId>,
42}
43
44impl CoordinateSystem {
45    fn root() -> Self {
46        CoordinateSystem {
47            transform: LayoutTransform::identity(),
48            world_transform: LayoutToWorldTransform::identity(),
49            should_flatten: false,
50            parent: None,
51        }
52    }
53}
54
55#[derive(Debug, Copy, Clone, Eq, Hash, MallocSizeOf, PartialEq, PeekPoke, Default)]
56#[cfg_attr(feature = "capture", derive(Serialize))]
57#[cfg_attr(feature = "replay", derive(Deserialize))]
58pub struct SpatialNodeIndex(pub u32);
59
60impl SpatialNodeIndex {
61    pub const INVALID: SpatialNodeIndex = SpatialNodeIndex(u32::MAX);
62
63    /// May be set on a cluster / picture during scene building if the spatial
64    /// node is not known at this time. It must be set to a valid value before
65    /// scene building is complete (by `finalize_picture`). In future, we could
66    /// make this type-safe with a wrapper type to ensure we know when a spatial
67    /// node index may have an unknown value.
68    pub const UNKNOWN: SpatialNodeIndex = SpatialNodeIndex(u32::MAX - 1);
69}
70
71// In some cases, the conversion from CSS pixels to device pixels can result in small
72// rounding errors when calculating the scrollable distance of a scroll frame. Apply
73// a small epsilon so that we don't detect these frames as "real" scroll frames.
74const MIN_SCROLLABLE_AMOUNT: f32 = 0.01;
75
76// The minimum size for a scroll frame for it to be considered for a scroll root.
77const MIN_SCROLL_ROOT_SIZE: f32 = 128.0;
78
79impl SpatialNodeIndex {
80    pub fn new(index: usize) -> Self {
81        debug_assert!(index < ::std::u32::MAX as usize);
82        SpatialNodeIndex(index as u32)
83    }
84}
85
86impl CoordinateSystemId {
87    pub fn root() -> Self {
88        CoordinateSystemId(0)
89    }
90}
91
92#[derive(Debug, Copy, Clone, PartialEq)]
93pub enum VisibleFace {
94    Front,
95    Back,
96}
97
98impl Default for VisibleFace {
99    fn default() -> Self {
100        VisibleFace::Front
101    }
102}
103
104impl ops::Not for VisibleFace {
105    type Output = Self;
106    fn not(self) -> Self {
107        match self {
108            VisibleFace::Front => VisibleFace::Back,
109            VisibleFace::Back => VisibleFace::Front,
110        }
111    }
112}
113
114/// Allows functions and methods to retrieve common information about
115/// a spatial node, whether during scene or frame building
116pub trait SpatialNodeContainer {
117    /// Get the common information for a given spatial node
118    fn get_node_info(&self, index: SpatialNodeIndex) -> SpatialNodeInfo;
119}
120
121#[cfg_attr(feature = "capture", derive(Serialize))]
122#[cfg_attr(feature = "replay", derive(Deserialize))]
123enum StoreElement<T> {
124    Empty,
125    Occupied(T),
126}
127
128#[cfg_attr(feature = "capture", derive(Serialize))]
129#[cfg_attr(feature = "replay", derive(Deserialize))]
130struct Store<T> {
131    elements: Vec<StoreElement<T>>,
132    free_indices: Vec<usize>,
133}
134
135impl<T> Store<T> {
136    fn new() -> Self {
137        Store {
138            elements: Vec::new(),
139            free_indices: Vec::new(),
140        }
141    }
142
143    fn insert(&mut self, element: T) -> usize {
144        match self.free_indices.pop() {
145            Some(index) => {
146                match &mut self.elements[index] {
147                    e @ StoreElement::Empty => *e = StoreElement::Occupied(element),
148                    StoreElement::Occupied(..) => panic!("bug: slot already occupied"),
149                };
150                index
151            }
152            None => {
153                let index = self.elements.len();
154                self.elements.push(StoreElement::Occupied(element));
155                index
156            }
157        }
158    }
159
160    fn set(&mut self, index: usize, element: T) {
161        match &mut self.elements[index] {
162            StoreElement::Empty => panic!("bug: set on empty element!"),
163            StoreElement::Occupied(ref mut entry) => *entry = element,
164        }
165    }
166
167    fn free(&mut self, index: usize) -> T {
168        self.free_indices.push(index);
169
170        let value = std::mem::replace(&mut self.elements[index], StoreElement::Empty);
171
172        match value {
173            StoreElement::Occupied(value) => value,
174            StoreElement::Empty => panic!("bug: freeing an empty slot"),
175        }
176    }
177}
178
179impl<T> ops::Index<usize> for Store<T> {
180    type Output = T;
181    fn index(&self, index: usize) -> &Self::Output {
182        match self.elements[index] {
183            StoreElement::Occupied(ref e) => e,
184            StoreElement::Empty => panic!("bug: indexing an empty element!"),
185        }
186    }
187}
188
189impl<T> ops::IndexMut<usize> for Store<T> {
190    fn index_mut(&mut self, index: usize) -> &mut T {
191        match self.elements[index] {
192            StoreElement::Occupied(ref mut e) => e,
193            StoreElement::Empty => panic!("bug: indexing an empty element!"),
194        }
195    }
196}
197
198#[cfg_attr(feature = "capture", derive(Serialize))]
199#[cfg_attr(feature = "replay", derive(Deserialize))]
200struct SpatialNodeEntry {
201    index: usize,
202    last_used: u64,
203}
204
205/// The representation of the spatial tree during scene building, which is
206/// mostly write-only, with a small number of queries for snapping,
207/// picture cache building
208#[cfg_attr(feature = "capture", derive(Serialize))]
209#[cfg_attr(feature = "replay", derive(Deserialize))]
210pub struct SceneSpatialTree {
211    /// Nodes which determine the positions (offsets and transforms) for primitives
212    /// and clips.
213    spatial_nodes: Store<SceneSpatialNode>,
214
215    /// A set of the uids we've encountered for spatial nodes, used to assert that
216    /// we're not seeing duplicates. Likely to be removed once we rely on this feature.
217    spatial_node_map: FastHashMap<SpatialNodeUid, SpatialNodeEntry>,
218
219    root_reference_frame_index: SpatialNodeIndex,
220
221    frame_counter: u64,
222    updates: SpatialTreeUpdates,
223
224    /// A debug check that the caller never adds a spatial node with duplicate
225    /// uid, since that can cause badness if it occurs (e.g. a malformed spatial
226    /// tree and infinite loops in is_ancestor etc)
227    spatial_nodes_set: FastHashSet<SpatialNodeUid>,
228}
229
230impl SpatialNodeContainer for SceneSpatialTree {
231    fn get_node_info(&self, index: SpatialNodeIndex) -> SpatialNodeInfo {
232        let node = &self.spatial_nodes[index.0 as usize];
233
234        SpatialNodeInfo {
235            parent: node.parent,
236            node_type: &node.descriptor.node_type,
237            snapping_transform: node.snapping_transform,
238        }
239    }
240}
241
242impl SceneSpatialTree {
243    pub fn new() -> Self {
244        let mut tree = SceneSpatialTree {
245            spatial_nodes: Store::new(),
246            spatial_node_map: FastHashMap::default(),
247            root_reference_frame_index: SpatialNodeIndex(0),
248            frame_counter: 0,
249            updates: SpatialTreeUpdates::new(),
250            spatial_nodes_set: FastHashSet::default(),
251        };
252
253        let node = SceneSpatialNode::new_reference_frame(
254            None,
255            TransformStyle::Flat,
256            PropertyBinding::Value(LayoutTransform::identity()),
257            ReferenceFrameKind::Transform {
258                should_snap: true,
259                is_2d_scale_translation: true,
260                paired_with_perspective: false,
261            },
262            LayoutVector2D::zero(),
263            PipelineId::dummy(),
264            true,
265            true,
266        );
267
268        tree.add_spatial_node(node, SpatialNodeUid::root());
269
270        tree
271    }
272
273    pub fn is_root_coord_system(&self, index: SpatialNodeIndex) -> bool {
274        self.spatial_nodes[index.0 as usize].is_root_coord_system
275    }
276
277    /// Complete building this scene, return the updates to apply to the frame spatial tree
278    pub fn end_frame_and_get_pending_updates(&mut self) -> SpatialTreeUpdates {
279        self.updates.root_reference_frame_index = self.root_reference_frame_index;
280        self.spatial_nodes_set.clear();
281
282        let now = self.frame_counter;
283        let spatial_nodes = &mut self.spatial_nodes;
284        let updates = &mut self.updates;
285
286        self.spatial_node_map.get_mut(&SpatialNodeUid::root()).unwrap().last_used = now;
287
288        self.spatial_node_map.retain(|_, entry| {
289            if entry.last_used + 10 < now {
290                spatial_nodes.free(entry.index);
291                updates.updates.push(SpatialTreeUpdate::Remove {
292                    index: entry.index,
293                });
294                return false;
295            }
296
297            true
298        });
299
300        let updates = std::mem::replace(&mut self.updates, SpatialTreeUpdates::new());
301
302        self.frame_counter += 1;
303
304        updates
305    }
306
307    /// Check if a given spatial node is an ancestor of another spatial node.
308    pub fn is_ancestor(
309        &self,
310        maybe_parent: SpatialNodeIndex,
311        maybe_child: SpatialNodeIndex,
312    ) -> bool {
313        // Early out if same node
314        if maybe_parent == maybe_child {
315            return false;
316        }
317
318        let mut current_node = maybe_child;
319
320        while current_node != self.root_reference_frame_index {
321            let node = self.get_node_info(current_node);
322            current_node = node.parent.expect("bug: no parent");
323
324            if current_node == maybe_parent {
325                return true;
326            }
327        }
328
329        false
330    }
331
332    /// Find the spatial node that is the scroll root for a given spatial node.
333    /// A scroll root is the first spatial node when found travelling up the
334    /// spatial node tree that is an explicit scroll frame.
335    pub fn find_scroll_root(
336        &self,
337        spatial_node_index: SpatialNodeIndex,
338        allow_sticky_frames: bool,
339    ) -> SpatialNodeIndex {
340        let mut real_scroll_root = self.root_reference_frame_index;
341        let mut outermost_scroll_root = self.root_reference_frame_index;
342        let mut current_scroll_root_is_sticky = false;
343        let mut node_index = spatial_node_index;
344
345        while node_index != self.root_reference_frame_index {
346            let node = self.get_node_info(node_index);
347            match node.node_type {
348                SpatialNodeType::ReferenceFrame(ref info) => {
349                    match info.kind {
350                        ReferenceFrameKind::Transform { is_2d_scale_translation: true, .. } => {
351                            // We can handle scroll nodes that pass through a 2d scale/translation node
352                        }
353                        ReferenceFrameKind::Transform { is_2d_scale_translation: false, .. } |
354                        ReferenceFrameKind::Perspective { .. } => {
355                            // When a reference frame is encountered, forget any scroll roots
356                            // we have encountered, as they may end up with a non-axis-aligned transform.
357                            real_scroll_root = self.root_reference_frame_index;
358                            outermost_scroll_root = self.root_reference_frame_index;
359                            current_scroll_root_is_sticky = false;
360                        }
361                    }
362                }
363                SpatialNodeType::StickyFrame(..) => {
364                    // Though not a scroll frame, we optionally treat sticky frames as scroll roots
365                    // to ensure they are given a separate picture cache slice.
366                    if allow_sticky_frames {
367                        outermost_scroll_root = node_index;
368                        real_scroll_root = node_index;
369                        // Set this true so that we don't select an ancestor scroll frame as the scroll root
370                        // on a subsequent iteration.
371                        current_scroll_root_is_sticky = true;
372                    }
373                }
374                SpatialNodeType::ScrollFrame(ref info) => {
375                    match info.frame_kind {
376                        ScrollFrameKind::PipelineRoot { is_root_pipeline } => {
377                            // Once we encounter a pipeline root, there is no need to look further
378                            if is_root_pipeline {
379                                break;
380                            }
381                        }
382                        ScrollFrameKind::Explicit => {
383                            // Store the closest scroll root we find to the root, for use
384                            // later on, even if it's not actually scrollable.
385                            outermost_scroll_root = node_index;
386
387                            // If the previously identified scroll root is sticky then we don't
388                            // want to choose an ancestor scroll root, as we want the sticky item
389                            // to have its own picture cache slice.
390                            if !current_scroll_root_is_sticky {
391                                // If the scroll root has no scrollable area, we don't want to
392                                // consider it. This helps pages that have a nested scroll root
393                                // within a redundant scroll root to avoid selecting the wrong
394                                // reference spatial node for a picture cache.
395                                if info.scrollable_size.width > MIN_SCROLLABLE_AMOUNT ||
396                                   info.scrollable_size.height > MIN_SCROLLABLE_AMOUNT {
397                                    // Since we are skipping redundant scroll roots, we may end up
398                                    // selecting inner scroll roots that are very small. There is
399                                    // no performance benefit to creating a slice for these roots,
400                                    // as they are cheap to rasterize. The size comparison is in
401                                    // local-space, but makes for a reasonable estimate. The value
402                                    // is arbitrary, but is generally small enough to ignore things
403                                    // like scroll roots around text input elements.
404                                    if info.viewport_rect.width() > MIN_SCROLL_ROOT_SIZE &&
405                                       info.viewport_rect.height() > MIN_SCROLL_ROOT_SIZE {
406                                        // If we've found a root that is scrollable, and a reasonable
407                                        // size, select that as the current root for this node
408                                        real_scroll_root = node_index;
409                                    }
410                                }
411                            }
412                        }
413                    }
414                }
415            }
416            node_index = node.parent.expect("unable to find parent node");
417        }
418
419        // If we didn't find any real (scrollable) frames, then return the outermost
420        // redundant scroll frame. This is important so that we can correctly find
421        // the clips defined on the content which should be handled when drawing the
422        // picture cache tiles (by definition these clips are ancestors of the
423        // scroll root selected for the picture cache).
424        if real_scroll_root == self.root_reference_frame_index {
425            outermost_scroll_root
426        } else {
427            real_scroll_root
428        }
429    }
430
431    /// The root reference frame, which is the true root of the SpatialTree.
432    pub fn root_reference_frame_index(&self) -> SpatialNodeIndex {
433        self.root_reference_frame_index
434    }
435
436    fn add_spatial_node(
437        &mut self,
438        mut node: SceneSpatialNode,
439        uid: SpatialNodeUid,
440    ) -> SpatialNodeIndex {
441        let parent_snapping_transform = match node.parent {
442            Some(parent_index) => {
443                self.get_node_info(parent_index).snapping_transform
444            }
445            None => {
446                Some(ScaleOffset::identity())
447            }
448        };
449
450        node.snapping_transform = calculate_snapping_transform(
451            parent_snapping_transform,
452            &node.descriptor.node_type,
453        );
454
455        // Ensure a node with the same uid hasn't been added during this scene build
456        assert!(self.spatial_nodes_set.insert(uid), "duplicate key {:?}", uid);
457
458        let index = match self.spatial_node_map.entry(uid) {
459            Entry::Occupied(mut e) => {
460                let e = e.get_mut();
461                e.last_used = self.frame_counter;
462
463                let existing_node = &self.spatial_nodes[e.index];
464
465                if *existing_node != node {
466                    self.updates.updates.push(SpatialTreeUpdate::Update {
467                        index: e.index,
468                        parent: node.parent,
469                        descriptor: node.descriptor.clone(),
470                    });
471                    self.spatial_nodes.set(e.index, node);
472                }
473
474                e.index
475            }
476            Entry::Vacant(e) => {
477                let descriptor = node.descriptor.clone();
478                let parent = node.parent;
479
480                let index = self.spatial_nodes.insert(node);
481
482                e.insert(SpatialNodeEntry {
483                    index,
484                    last_used: self.frame_counter,
485                });
486
487                self.updates.updates.push(SpatialTreeUpdate::Insert {
488                    index,
489                    descriptor,
490                    parent,
491                });
492
493                index
494            }
495        };
496
497        SpatialNodeIndex(index as u32)
498    }
499
500    pub fn add_reference_frame(
501        &mut self,
502        parent_index: SpatialNodeIndex,
503        transform_style: TransformStyle,
504        source_transform: PropertyBinding<LayoutTransform>,
505        kind: ReferenceFrameKind,
506        origin_in_parent_reference_frame: LayoutVector2D,
507        pipeline_id: PipelineId,
508        uid: SpatialNodeUid,
509    ) -> SpatialNodeIndex {
510        // Determine if this reference frame creates a new static coordinate system
511        let new_static_coord_system = match kind {
512            ReferenceFrameKind::Transform { is_2d_scale_translation: true, .. } => {
513                // Client has guaranteed this transform will only be axis-aligned
514                false
515            }
516            ReferenceFrameKind::Transform { is_2d_scale_translation: false, .. } | ReferenceFrameKind::Perspective { .. } => {
517                // Even if client hasn't promised it's an axis-aligned transform, we can still
518                // check this so long as the transform isn't animated (and thus could change to
519                // anything by APZ during frame building)
520                match source_transform {
521                    PropertyBinding::Value(m) => {
522                        !m.is_2d_scale_translation()
523                    }
524                    PropertyBinding::Binding(..) => {
525                        // Animated, so assume it may introduce a complex transform
526                        true
527                    }
528                }
529            }
530        };
531
532        let is_root_coord_system = !new_static_coord_system &&
533            self.spatial_nodes[parent_index.0 as usize].is_root_coord_system;
534        let is_pipeline_root = match uid.kind {
535            SpatialNodeUidKind::InternalReferenceFrame { .. } => true,
536            _ => false,
537        };
538
539        let node = SceneSpatialNode::new_reference_frame(
540            Some(parent_index),
541            transform_style,
542            source_transform,
543            kind,
544            origin_in_parent_reference_frame,
545            pipeline_id,
546            is_root_coord_system,
547            is_pipeline_root,
548        );
549        self.add_spatial_node(node, uid)
550    }
551
552    pub fn add_scroll_frame(
553        &mut self,
554        parent_index: SpatialNodeIndex,
555        external_id: ExternalScrollId,
556        pipeline_id: PipelineId,
557        frame_rect: &LayoutRect,
558        content_size: &LayoutSize,
559        frame_kind: ScrollFrameKind,
560        external_scroll_offset: LayoutVector2D,
561        scroll_offset_generation: APZScrollGeneration,
562        has_scroll_linked_effect: HasScrollLinkedEffect,
563        uid: SpatialNodeUid,
564    ) -> SpatialNodeIndex {
565        // Scroll frames are only 2d translations - they can't introduce a new static coord system
566        let is_root_coord_system = self.spatial_nodes[parent_index.0 as usize].is_root_coord_system;
567
568        let node = SceneSpatialNode::new_scroll_frame(
569            pipeline_id,
570            parent_index,
571            external_id,
572            frame_rect,
573            content_size,
574            frame_kind,
575            external_scroll_offset,
576            scroll_offset_generation,
577            has_scroll_linked_effect,
578            is_root_coord_system,
579        );
580        self.add_spatial_node(node, uid)
581    }
582
583    pub fn add_sticky_frame(
584        &mut self,
585        parent_index: SpatialNodeIndex,
586        sticky_frame_info: StickyFrameInfo,
587        pipeline_id: PipelineId,
588        key: SpatialTreeItemKey,
589        instance_id: PipelineInstanceId,
590    ) -> SpatialNodeIndex {
591        // Sticky frames are only 2d translations - they can't introduce a new static coord system
592        let is_root_coord_system = self.spatial_nodes[parent_index.0 as usize].is_root_coord_system;
593        let uid = SpatialNodeUid::external(key, pipeline_id, instance_id);
594
595        let node = SceneSpatialNode::new_sticky_frame(
596            parent_index,
597            sticky_frame_info,
598            pipeline_id,
599            is_root_coord_system,
600        );
601        self.add_spatial_node(node, uid)
602    }
603}
604
605#[cfg_attr(feature = "capture", derive(Serialize))]
606#[cfg_attr(feature = "replay", derive(Deserialize))]
607pub enum SpatialTreeUpdate {
608    Insert {
609        index: usize,
610        parent: Option<SpatialNodeIndex>,
611        descriptor: SpatialNodeDescriptor,
612    },
613    Update {
614        index: usize,
615        parent: Option<SpatialNodeIndex>,
616        descriptor: SpatialNodeDescriptor,
617    },
618    Remove {
619        index: usize,
620    },
621}
622
623/// The delta updates to apply after building a new scene to the retained frame building
624/// tree.
625// TODO(gw): During the initial scaffolding work, this is the exact same as previous
626//           behavior - that is, a complete list of new spatial nodes. In future, this
627//           will instead be a list of deltas to apply to the frame spatial tree.
628#[cfg_attr(feature = "capture", derive(Serialize))]
629#[cfg_attr(feature = "replay", derive(Deserialize))]
630pub struct SpatialTreeUpdates {
631    root_reference_frame_index: SpatialNodeIndex,
632    updates: Vec<SpatialTreeUpdate>,
633}
634
635impl SpatialTreeUpdates {
636    fn new() -> Self {
637        SpatialTreeUpdates {
638            root_reference_frame_index: SpatialNodeIndex::INVALID,
639            updates: Vec::new(),
640        }
641    }
642}
643
644/// Represents the spatial tree during frame building, which is mostly
645/// read-only, apart from the tree update at the start of the frame
646#[cfg_attr(feature = "capture", derive(Serialize))]
647#[cfg_attr(feature = "replay", derive(Deserialize))]
648pub struct SpatialTree {
649    /// Nodes which determine the positions (offsets and transforms) for primitives
650    /// and clips.
651    spatial_nodes: Vec<SpatialNode>,
652
653    /// A list of transforms that establish new coordinate systems.
654    /// Spatial nodes only establish a new coordinate system when
655    /// they have a transform that is not a simple 2d translation.
656    coord_systems: Vec<CoordinateSystem>,
657
658    root_reference_frame_index: SpatialNodeIndex,
659
660    /// Stack of current state for each parent node while traversing and updating tree
661    update_state_stack: Vec<TransformUpdateState>,
662}
663
664#[derive(Clone)]
665#[cfg_attr(feature = "capture", derive(Serialize))]
666#[cfg_attr(feature = "replay", derive(Deserialize))]
667pub struct TransformUpdateState {
668    pub parent_reference_frame_transform: LayoutToWorldFastTransform,
669    pub parent_accumulated_scroll_offset: LayoutVector2D,
670    pub nearest_scrolling_ancestor_offset: LayoutVector2D,
671    pub nearest_scrolling_ancestor_viewport: LayoutRect,
672
673    /// An id for keeping track of the axis-aligned space of this node. This is used in
674    /// order to to track what kinds of clip optimizations can be done for a particular
675    /// display list item, since optimizations can usually only be done among
676    /// coordinate systems which are relatively axis aligned.
677    pub current_coordinate_system_id: CoordinateSystemId,
678
679    /// Scale and offset from the coordinate system that started this compatible coordinate system.
680    pub coordinate_system_relative_scale_offset: ScaleOffset,
681
682    /// True if this node is transformed by an invertible transform.  If not, display items
683    /// transformed by this node will not be displayed and display items not transformed by this
684    /// node will not be clipped by clips that are transformed by this node.
685    pub invertible: bool,
686
687    /// True if this node is a part of Preserve3D hierarchy.
688    pub preserves_3d: bool,
689
690    /// True if the any parent nodes are currently zooming
691    pub is_ancestor_or_self_zooming: bool,
692
693    /// Set to true if this state represents a scroll node with external id
694    pub external_id: Option<ExternalScrollId>,
695
696    /// The node scroll offset if this state is a scroll/sticky node. Zero if a reference frame.
697    pub scroll_offset: LayoutVector2D,
698}
699
700/// Transformation between two nodes in the spatial tree that can sometimes be
701/// encoded more efficiently than with a full matrix.
702#[derive(Debug, Clone)]
703pub enum CoordinateSpaceMapping<Src, Dst> {
704    Local,
705    ScaleOffset(ScaleOffset),
706    Transform(Transform3D<f32, Src, Dst>),
707}
708
709impl<Src, Dst> CoordinateSpaceMapping<Src, Dst> {
710    pub fn into_transform(self) -> Transform3D<f32, Src, Dst> {
711        match self {
712            CoordinateSpaceMapping::Local => Transform3D::identity(),
713            CoordinateSpaceMapping::ScaleOffset(scale_offset) => scale_offset.to_transform(),
714            CoordinateSpaceMapping::Transform(transform) => transform,
715        }
716    }
717
718    pub fn into_fast_transform(self) -> FastTransform<Src, Dst> {
719        match self {
720            CoordinateSpaceMapping::Local => FastTransform::identity(),
721            CoordinateSpaceMapping::ScaleOffset(scale_offset) => FastTransform::with_scale_offset(scale_offset),
722            CoordinateSpaceMapping::Transform(transform) => FastTransform::with_transform(transform),
723        }
724    }
725
726    pub fn is_perspective(&self) -> bool {
727        match *self {
728            CoordinateSpaceMapping::Local |
729            CoordinateSpaceMapping::ScaleOffset(_) => false,
730            CoordinateSpaceMapping::Transform(ref transform) => transform.has_perspective_component(),
731        }
732    }
733
734    pub fn is_2d_axis_aligned(&self) -> bool {
735        match *self {
736            CoordinateSpaceMapping::Local |
737            CoordinateSpaceMapping::ScaleOffset(_) => true,
738            CoordinateSpaceMapping::Transform(ref transform) => transform.preserves_2d_axis_alignment(),
739        }
740    }
741
742    pub fn is_2d_scale_translation(&self) -> bool {
743        match *self {
744            CoordinateSpaceMapping::Local |
745            CoordinateSpaceMapping::ScaleOffset(_) => true,
746            CoordinateSpaceMapping::Transform(ref transform) => transform.is_2d_scale_translation(),
747        }
748    }
749
750    pub fn scale_factors(&self) -> (f32, f32) {
751        match *self {
752            CoordinateSpaceMapping::Local => (1.0, 1.0),
753            CoordinateSpaceMapping::ScaleOffset(ref scale_offset) => (scale_offset.scale.x.abs(), scale_offset.scale.y.abs()),
754            CoordinateSpaceMapping::Transform(ref transform) => scale_factors(transform),
755        }
756    }
757
758    pub fn inverse(&self) -> Option<CoordinateSpaceMapping<Dst, Src>> {
759        match *self {
760            CoordinateSpaceMapping::Local => Some(CoordinateSpaceMapping::Local),
761            CoordinateSpaceMapping::ScaleOffset(ref scale_offset) => {
762                Some(CoordinateSpaceMapping::ScaleOffset(scale_offset.inverse()))
763            }
764            CoordinateSpaceMapping::Transform(ref transform) => {
765                transform.inverse().map(CoordinateSpaceMapping::Transform)
766            }
767        }
768    }
769
770    pub fn as_2d_scale_offset(&self) -> Option<ScaleOffset> {
771        Some(match *self {
772            CoordinateSpaceMapping::Local => ScaleOffset::identity(),
773            CoordinateSpaceMapping::ScaleOffset(transfrom) => transfrom,
774            CoordinateSpaceMapping::Transform(ref transform) => {
775                if !transform.is_2d_scale_translation() {
776                    return None
777                }
778                ScaleOffset::new(transform.m11, transform.m22, transform.m41, transform.m42)
779            }
780        })
781    }
782}
783
784enum TransformScroll {
785    Scrolled,
786    Unscrolled,
787}
788
789impl SpatialNodeContainer for SpatialTree {
790    fn get_node_info(&self, index: SpatialNodeIndex) -> SpatialNodeInfo {
791        let node = self.get_spatial_node(index);
792
793        SpatialNodeInfo {
794            parent: node.parent,
795            node_type: &node.node_type,
796            snapping_transform: node.snapping_transform,
797        }
798    }
799}
800
801impl SpatialTree {
802    pub fn new() -> Self {
803        SpatialTree {
804            spatial_nodes: Vec::new(),
805            coord_systems: Vec::new(),
806            root_reference_frame_index: SpatialNodeIndex::INVALID,
807            update_state_stack: Vec::new(),
808        }
809    }
810
811    fn visit_node_impl_mut<F>(
812        &mut self,
813        index: SpatialNodeIndex,
814        f: &mut F,
815    ) where F: FnMut(SpatialNodeIndex, &mut SpatialNode) {
816        let mut child_indices: SmallVec<[SpatialNodeIndex; 8]> = SmallVec::new();
817
818        let node = self.get_spatial_node_mut(index);
819        f(index, node);
820        child_indices.extend_from_slice(&node.children);
821
822        for child_index in child_indices {
823            self.visit_node_impl_mut(child_index, f);
824        }
825    }
826
827    fn visit_node_impl<F>(
828        &self,
829        index: SpatialNodeIndex,
830        f: &mut F,
831    ) where F: FnMut(SpatialNodeIndex, &SpatialNode) {
832        let node = self.get_spatial_node(index);
833
834        f(index, node);
835
836        for child_index in &node.children {
837            self.visit_node_impl(*child_index, f);
838        }
839    }
840
841    /// Visit all nodes from the root of the tree, invoking a closure on each one
842    pub fn visit_nodes<F>(&self, mut f: F) where F: FnMut(SpatialNodeIndex, &SpatialNode) {
843        if self.root_reference_frame_index == SpatialNodeIndex::INVALID {
844            return;
845        }
846
847        self.visit_node_impl(self.root_reference_frame_index, &mut f);
848    }
849
850    /// Visit all nodes from the root of the tree, invoking a closure on each one
851    pub fn visit_nodes_mut<F>(&mut self, mut f: F) where F: FnMut(SpatialNodeIndex, &mut SpatialNode) {
852        if self.root_reference_frame_index == SpatialNodeIndex::INVALID {
853            return;
854        }
855
856        self.visit_node_impl_mut(self.root_reference_frame_index, &mut f);
857    }
858
859    /// Apply updates from a new scene to the frame spatial tree
860    pub fn apply_updates(
861        &mut self,
862        updates: SpatialTreeUpdates,
863    ) {
864        self.root_reference_frame_index = updates.root_reference_frame_index;
865
866        for update in updates.updates {
867            match update {
868                SpatialTreeUpdate::Insert { index, parent, descriptor } => {
869                    if let Some(parent) = parent {
870                        self.get_spatial_node_mut(parent).add_child(SpatialNodeIndex(index as u32));
871                    }
872
873                    let node = SpatialNode {
874                        viewport_transform: ScaleOffset::identity(),
875                        content_transform: ScaleOffset::identity(),
876                        snapping_transform: None,
877                        coordinate_system_id: CoordinateSystemId(0),
878                        transform_kind: TransformedRectKind::AxisAligned,
879                        parent,
880                        children: Vec::new(),
881                        pipeline_id: descriptor.pipeline_id,
882                        node_type: descriptor.node_type,
883                        invertible: true,
884                        is_async_zooming: false,
885                        is_ancestor_or_self_zooming: false,
886                    };
887
888                    assert!(index <= self.spatial_nodes.len());
889                    if index < self.spatial_nodes.len() {
890                        self.spatial_nodes[index] = node;
891                    } else {
892                        self.spatial_nodes.push(node);
893                    }
894                }
895                SpatialTreeUpdate::Update { index, descriptor, parent } => {
896                    let current_parent = self.spatial_nodes[index].parent;
897
898                    if current_parent != parent {
899                        if let Some(current_parent) = current_parent {
900                            let i = self.spatial_nodes[current_parent.0 as usize]
901                                .children
902                                .iter()
903                                .position(|e| e.0 as usize == index)
904                                .expect("bug: not found!");
905                            self.spatial_nodes[current_parent.0 as usize].children.remove(i);
906                        }
907
908                        let new_parent = parent.expect("todo: is this valid?");
909                        self.spatial_nodes[new_parent.0 as usize].add_child(SpatialNodeIndex(index as u32));
910                    }
911
912                    let node = &mut self.spatial_nodes[index];
913
914                    node.node_type = descriptor.node_type;
915                    node.pipeline_id = descriptor.pipeline_id;
916                    node.parent = parent;
917                }
918                SpatialTreeUpdate::Remove { index, .. } => {
919                    let node = &mut self.spatial_nodes[index];
920
921                    // Set the pipeline id to be invalid, so that even though this array
922                    // entry still exists we can easily see it's invalid when debugging.
923                    node.pipeline_id = PipelineId::dummy();
924
925                    if let Some(parent) = node.parent {
926                        let i = self.spatial_nodes[parent.0 as usize]
927                            .children
928                            .iter()
929                            .position(|e| e.0 as usize == index)
930                            .expect("bug: not found!");
931                        self.spatial_nodes[parent.0 as usize].children.remove(i);
932                    }
933                }
934            }
935        }
936
937        self.visit_nodes_mut(|_, node| {
938            match node.node_type {
939                SpatialNodeType::ScrollFrame(ref mut info) => {
940                    info.offsets = vec![SampledScrollOffset{
941                        offset: -info.external_scroll_offset,
942                        generation: info.offset_generation,
943                    }];
944                }
945                SpatialNodeType::StickyFrame(ref mut info) => {
946                    info.current_offset = LayoutVector2D::zero();
947                }
948                SpatialNodeType::ReferenceFrame(..) => {}
949            }
950        });
951    }
952
953    pub fn get_last_sampled_scroll_offsets(
954        &self,
955    ) -> FastHashMap<ExternalScrollId, Vec<SampledScrollOffset>> {
956        let mut result = FastHashMap::default();
957        self.visit_nodes(|_, node| {
958            if let SpatialNodeType::ScrollFrame(ref scrolling) = node.node_type {
959                result.insert(scrolling.external_id, scrolling.offsets.clone());
960            }
961        });
962        result
963    }
964
965    pub fn apply_last_sampled_scroll_offsets(
966        &mut self,
967        last_sampled_offsets: FastHashMap<ExternalScrollId, Vec<SampledScrollOffset>>,
968    ) {
969        self.visit_nodes_mut(|_, node| {
970            if let SpatialNodeType::ScrollFrame(ref mut scrolling) = node.node_type {
971                if let Some(offsets) = last_sampled_offsets.get(&scrolling.external_id) {
972                    scrolling.offsets = offsets.clone();
973                }
974            }
975        });
976    }
977
978    pub fn get_spatial_node(&self, index: SpatialNodeIndex) -> &SpatialNode {
979        &self.spatial_nodes[index.0 as usize]
980    }
981
982    pub fn get_spatial_node_mut(&mut self, index: SpatialNodeIndex) -> &mut SpatialNode {
983        &mut self.spatial_nodes[index.0 as usize]
984    }
985
986    /// Get total number of spatial nodes
987    pub fn spatial_node_count(&self) -> usize {
988        self.spatial_nodes.len()
989    }
990
991    pub fn find_spatial_node_by_anim_id(
992        &self,
993        id: PropertyBindingId,
994    ) -> Option<SpatialNodeIndex> {
995        let mut node_index = None;
996
997        self.visit_nodes(|index, node| {
998            if node.is_transform_bound_to_property(id) {
999                debug_assert!(node_index.is_none());        // Multiple nodes with same anim id
1000                node_index = Some(index);
1001            }
1002        });
1003
1004        node_index
1005    }
1006
1007    /// Calculate the relative transform from `child_index` to `parent_index`.
1008    /// This method will panic if the nodes are not connected!
1009    pub fn get_relative_transform(
1010        &self,
1011        child_index: SpatialNodeIndex,
1012        parent_index: SpatialNodeIndex,
1013    ) -> CoordinateSpaceMapping<LayoutPixel, LayoutPixel> {
1014        self.get_relative_transform_with_face(child_index, parent_index, None)
1015    }
1016
1017    /// Calculate the relative transform from `child_index` to `parent_index`.
1018    /// This method will panic if the nodes are not connected!
1019    /// Also, switch the visible face to `Back` if at any stage where the
1020    /// combined transform is flattened, we see the back face.
1021    pub fn get_relative_transform_with_face(
1022        &self,
1023        child_index: SpatialNodeIndex,
1024        parent_index: SpatialNodeIndex,
1025        mut visible_face: Option<&mut VisibleFace>,
1026    ) -> CoordinateSpaceMapping<LayoutPixel, LayoutPixel> {
1027        if child_index == parent_index {
1028            return CoordinateSpaceMapping::Local;
1029        }
1030
1031        let child = self.get_spatial_node(child_index);
1032        let parent = self.get_spatial_node(parent_index);
1033
1034        // TODO(gw): We expect this never to fail, but it's possible that it might due to
1035        //           either (a) a bug in WR / Gecko, or (b) some obscure real-world content
1036        //           that we're unaware of. If we ever hit this, please open a bug with any
1037        //           repro steps!
1038        assert!(
1039            child.coordinate_system_id.0 >= parent.coordinate_system_id.0,
1040            "bug: this is an unexpected case - please open a bug and talk to #gfx team!",
1041        );
1042
1043        if child.coordinate_system_id == parent.coordinate_system_id {
1044            let scale_offset = child.content_transform.then(&parent.content_transform.inverse());
1045            return CoordinateSpaceMapping::ScaleOffset(scale_offset);
1046        }
1047
1048        let mut coordinate_system_id = child.coordinate_system_id;
1049        let mut transform = child.content_transform.to_transform();
1050
1051        // we need to update the associated parameters of a transform in two cases:
1052        // 1) when the flattening happens, so that we don't lose that original 3D aspects
1053        // 2) when we reach the end of iteration, so that our result is up to date
1054
1055        while coordinate_system_id != parent.coordinate_system_id {
1056            let coord_system = &self.coord_systems[coordinate_system_id.0 as usize];
1057
1058            if coord_system.should_flatten {
1059                if let Some(ref mut face) = visible_face {
1060                    if transform.is_backface_visible() {
1061                        **face = VisibleFace::Back;
1062                    }
1063                }
1064                transform.flatten_z_output();
1065            }
1066
1067            coordinate_system_id = coord_system.parent.expect("invalid parent!");
1068            transform = transform.then(&coord_system.transform);
1069        }
1070
1071        transform = transform.then(
1072            &parent.content_transform
1073                .inverse()
1074                .to_transform(),
1075        );
1076        if let Some(face) = visible_face {
1077            if transform.is_backface_visible() {
1078                *face = VisibleFace::Back;
1079            }
1080        }
1081
1082        CoordinateSpaceMapping::Transform(transform)
1083    }
1084
1085    /// Returns true if both supplied spatial nodes are in the same coordinate system
1086    /// (implies the relative transform produce axis-aligned rects).
1087    pub fn is_matching_coord_system(
1088        &self,
1089        index0: SpatialNodeIndex,
1090        index1: SpatialNodeIndex,
1091    ) -> bool {
1092        let node0 = self.get_spatial_node(index0);
1093        let node1 = self.get_spatial_node(index1);
1094
1095        node0.coordinate_system_id == node1.coordinate_system_id
1096    }
1097
1098    fn get_world_transform_impl(
1099        &self,
1100        index: SpatialNodeIndex,
1101        scroll: TransformScroll,
1102    ) -> CoordinateSpaceMapping<LayoutPixel, WorldPixel> {
1103        let child = self.get_spatial_node(index);
1104
1105        if child.coordinate_system_id.0 == 0 {
1106            if index == self.root_reference_frame_index {
1107                CoordinateSpaceMapping::Local
1108            } else {
1109              match scroll {
1110                TransformScroll::Scrolled => CoordinateSpaceMapping::ScaleOffset(child.content_transform),
1111                TransformScroll::Unscrolled => CoordinateSpaceMapping::ScaleOffset(child.viewport_transform),
1112              }
1113            }
1114        } else {
1115            let system = &self.coord_systems[child.coordinate_system_id.0 as usize];
1116            let scale_offset = match scroll {
1117                TransformScroll::Scrolled => &child.content_transform,
1118                TransformScroll::Unscrolled => &child.viewport_transform,
1119            };
1120            let transform = scale_offset
1121                .to_transform()
1122                .then(&system.world_transform);
1123
1124            CoordinateSpaceMapping::Transform(transform)
1125        }
1126    }
1127
1128    /// Calculate the relative transform from `index` to the root.
1129    pub fn get_world_transform(
1130        &self,
1131        index: SpatialNodeIndex,
1132    ) -> CoordinateSpaceMapping<LayoutPixel, WorldPixel> {
1133        self.get_world_transform_impl(index, TransformScroll::Scrolled)
1134    }
1135
1136    /// Calculate the relative transform from `index` to the root.
1137    /// Unlike `get_world_transform`, this variant doesn't account for the local scroll offset.
1138    pub fn get_world_viewport_transform(
1139        &self,
1140        index: SpatialNodeIndex,
1141    ) -> CoordinateSpaceMapping<LayoutPixel, WorldPixel> {
1142        self.get_world_transform_impl(index, TransformScroll::Unscrolled)
1143    }
1144
1145    /// The root reference frame, which is the true root of the SpatialTree.
1146    pub fn root_reference_frame_index(&self) -> SpatialNodeIndex {
1147        self.root_reference_frame_index
1148    }
1149
1150    pub fn set_scroll_offsets(
1151        &mut self,
1152        id: ExternalScrollId,
1153        offsets: Vec<SampledScrollOffset>,
1154    ) -> bool {
1155        let mut did_change = false;
1156
1157        self.visit_nodes_mut(|_, node| {
1158            if node.matches_external_id(id) {
1159                did_change |= node.set_scroll_offsets(offsets.clone());
1160            }
1161        });
1162
1163        did_change
1164    }
1165
1166    pub fn update_tree(
1167        &mut self,
1168        scene_properties: &SceneProperties,
1169    ) {
1170        if self.root_reference_frame_index == SpatialNodeIndex::INVALID {
1171            return;
1172        }
1173
1174        profile_scope!("update_tree");
1175        self.coord_systems.clear();
1176        self.coord_systems.push(CoordinateSystem::root());
1177
1178        let root_node_index = self.root_reference_frame_index();
1179        assert!(self.update_state_stack.is_empty());
1180
1181        let state = TransformUpdateState {
1182            parent_reference_frame_transform: LayoutVector2D::zero().into(),
1183            parent_accumulated_scroll_offset: LayoutVector2D::zero(),
1184            nearest_scrolling_ancestor_offset: LayoutVector2D::zero(),
1185            nearest_scrolling_ancestor_viewport: LayoutRect::zero(),
1186            current_coordinate_system_id: CoordinateSystemId::root(),
1187            coordinate_system_relative_scale_offset: ScaleOffset::identity(),
1188            invertible: true,
1189            preserves_3d: false,
1190            is_ancestor_or_self_zooming: false,
1191            external_id: None,
1192            scroll_offset: LayoutVector2D::zero(),
1193        };
1194        self.update_state_stack.push(state);
1195
1196        self.update_node(
1197            root_node_index,
1198            scene_properties,
1199        );
1200
1201        self.update_state_stack.pop().unwrap();
1202    }
1203
1204    fn update_node(
1205        &mut self,
1206        node_index: SpatialNodeIndex,
1207        scene_properties: &SceneProperties,
1208    ) {
1209        let parent_snapping_transform = match self.get_spatial_node(node_index).parent {
1210            Some(parent_index) => {
1211                self.get_node_info(parent_index).snapping_transform
1212            }
1213            None => {
1214                Some(ScaleOffset::identity())
1215            }
1216        };
1217
1218        let node = &mut self.spatial_nodes[node_index.0 as usize];
1219
1220        node.snapping_transform = calculate_snapping_transform(
1221            parent_snapping_transform,
1222            &node.node_type,
1223        );
1224
1225        node.update(
1226            &self.update_state_stack,
1227            &mut self.coord_systems,
1228            scene_properties,
1229        );
1230
1231        if !node.children.is_empty() {
1232            let mut child_state = self.update_state_stack.last().unwrap().clone();
1233            node.prepare_state_for_children(&mut child_state);
1234            self.update_state_stack.push(child_state);
1235
1236            let mut child_indices: SmallVec<[SpatialNodeIndex; 8]> = SmallVec::new();
1237            child_indices.extend_from_slice(&node.children);
1238
1239            for child_index in child_indices {
1240                self.update_node(
1241                    child_index,
1242                    scene_properties,
1243                );
1244            }
1245
1246            self.update_state_stack.pop().unwrap();
1247        }
1248    }
1249
1250    pub fn build_transform_palette(&self, memory: &FrameMemory) -> TransformPalette {
1251        profile_scope!("build_transform_palette");
1252        TransformPalette::new(self.spatial_nodes.len(), memory)
1253    }
1254
1255    fn print_node<T: PrintTreePrinter>(
1256        &self,
1257        index: SpatialNodeIndex,
1258        pt: &mut T,
1259    ) {
1260        let node = self.get_spatial_node(index);
1261        match node.node_type {
1262            SpatialNodeType::StickyFrame(ref sticky_frame_info) => {
1263                pt.new_level(format!("StickyFrame"));
1264                pt.add_item(format!("sticky info: {:?}", sticky_frame_info));
1265            }
1266            SpatialNodeType::ScrollFrame(ref scrolling_info) => {
1267                pt.new_level(format!("ScrollFrame"));
1268                pt.add_item(format!("viewport: {:?}", scrolling_info.viewport_rect));
1269                pt.add_item(format!("scrollable_size: {:?}", scrolling_info.scrollable_size));
1270                pt.add_item(format!("scroll offset: {:?}", scrolling_info.offset()));
1271                pt.add_item(format!("external_scroll_offset: {:?}", scrolling_info.external_scroll_offset));
1272                pt.add_item(format!("offset generation: {:?}", scrolling_info.offset_generation));
1273                if scrolling_info.has_scroll_linked_effect == HasScrollLinkedEffect::Yes {
1274                    pt.add_item("has scroll-linked effect".to_string());
1275                }
1276                pt.add_item(format!("kind: {:?}", scrolling_info.frame_kind));
1277            }
1278            SpatialNodeType::ReferenceFrame(ref info) => {
1279                pt.new_level(format!("ReferenceFrame"));
1280                pt.add_item(format!("kind: {:?}", info.kind));
1281                pt.add_item(format!("transform_style: {:?}", info.transform_style));
1282                pt.add_item(format!("source_transform: {:?}", info.source_transform));
1283                pt.add_item(format!("origin_in_parent_reference_frame: {:?}", info.origin_in_parent_reference_frame));
1284            }
1285        }
1286
1287        pt.add_item(format!("index: {:?}", index));
1288        pt.add_item(format!("content_transform: {:?}", node.content_transform));
1289        pt.add_item(format!("viewport_transform: {:?}", node.viewport_transform));
1290        pt.add_item(format!("snapping_transform: {:?}", node.snapping_transform));
1291        pt.add_item(format!("coordinate_system_id: {:?}", node.coordinate_system_id));
1292
1293        for child_index in &node.children {
1294            self.print_node(*child_index, pt);
1295        }
1296
1297        pt.end_level();
1298    }
1299
1300    /// Get the visible face of the transfrom from the specified node to its parent.
1301    pub fn get_local_visible_face(&self, node_index: SpatialNodeIndex) -> VisibleFace {
1302        let node = self.get_spatial_node(node_index);
1303        let mut face = VisibleFace::Front;
1304        if let Some(mut parent_index) = node.parent {
1305            // Check if the parent is perspective. In CSS, a stacking context may
1306            // have both perspective and a regular transformation. Gecko translates the
1307            // perspective into a different `nsDisplayPerspective` and `nsDisplayTransform` items.
1308            // On WebRender side, we end up with 2 different reference frames:
1309            // one has kind of "transform", and it's parented to another of "perspective":
1310            // https://searchfox.org/mozilla-central/rev/72c7cef167829b6f1e24cae216fa261934c455fc/layout/generic/nsIFrame.cpp#3716
1311            if let SpatialNodeType::ReferenceFrame(ReferenceFrameInfo { kind: ReferenceFrameKind::Transform {
1312                paired_with_perspective: true,
1313                ..
1314            }, .. }) = node.node_type {
1315                let parent = self.get_spatial_node(parent_index);
1316                match parent.node_type {
1317                    SpatialNodeType::ReferenceFrame(ReferenceFrameInfo {
1318                        kind: ReferenceFrameKind::Perspective { .. },
1319                        ..
1320                    }) => {
1321                        parent_index = parent.parent.unwrap();
1322                    }
1323                    _ => {
1324                        log::error!("Unexpected parent {:?} is not perspective", parent_index);
1325                    }
1326                }
1327            }
1328
1329            self.get_relative_transform_with_face(node_index, parent_index, Some(&mut face));
1330        }
1331        face
1332    }
1333
1334    #[allow(dead_code)]
1335    pub fn print(&self) {
1336        if self.root_reference_frame_index != SpatialNodeIndex::INVALID {
1337            let mut buf = Vec::<u8>::new();
1338            {
1339                let mut pt = PrintTree::new_with_sink("spatial tree", &mut buf);
1340                self.print_with(&mut pt);
1341            }
1342            // If running in Gecko, set RUST_LOG=webrender::spatial_tree=debug
1343            // to get this logging to be emitted to stderr/logcat.
1344            debug!("{}", std::str::from_utf8(&buf).unwrap_or("(Tree printer emitted non-utf8)"));
1345        }
1346    }
1347}
1348
1349impl PrintableTree for SpatialTree {
1350    fn print_with<T: PrintTreePrinter>(&self, pt: &mut T) {
1351        if self.root_reference_frame_index != SpatialNodeIndex::INVALID {
1352            self.print_node(self.root_reference_frame_index(), pt);
1353        }
1354    }
1355}
1356
1357/// Calculate the accumulated external scroll offset for a given spatial node.
1358pub fn get_external_scroll_offset<S: SpatialNodeContainer>(
1359    spatial_tree: &S,
1360    node_index: SpatialNodeIndex,
1361) -> LayoutVector2D {
1362    let mut offset = LayoutVector2D::zero();
1363    let mut current_node = Some(node_index);
1364
1365    while let Some(node_index) = current_node {
1366        let node_info = spatial_tree.get_node_info(node_index);
1367
1368        match node_info.node_type {
1369            SpatialNodeType::ScrollFrame(ref scrolling) => {
1370                offset += scrolling.external_scroll_offset;
1371            }
1372            SpatialNodeType::StickyFrame(..) => {
1373                // Doesn't provide any external scroll offset
1374            }
1375            SpatialNodeType::ReferenceFrame(..) => {
1376                // External scroll offsets are not propagated across
1377                // reference frames.
1378                break;
1379            }
1380        }
1381
1382        current_node = node_info.parent;
1383    }
1384
1385    offset
1386}
1387
1388fn calculate_snapping_transform(
1389    parent_snapping_transform: Option<ScaleOffset>,
1390    node_type: &SpatialNodeType,
1391) -> Option<ScaleOffset> {
1392    // We need to incorporate the parent scale/offset with the child.
1393    // If the parent does not have a scale/offset, then we know we are
1394    // not 2d axis aligned and thus do not need to snap its children
1395    // either.
1396    let parent_scale_offset = match parent_snapping_transform {
1397        Some(parent_snapping_transform) => parent_snapping_transform,
1398        None => return None,
1399    };
1400
1401    let scale_offset = match node_type {
1402        SpatialNodeType::ReferenceFrame(ref info) => {
1403            match info.source_transform {
1404                PropertyBinding::Value(ref value) => {
1405                    // We can only get a ScaleOffset if the transform is 2d axis
1406                    // aligned.
1407                    match ScaleOffset::from_transform(value) {
1408                        Some(scale_offset) => {
1409                            let origin_offset = info.origin_in_parent_reference_frame;
1410                            scale_offset.then(&ScaleOffset::from_offset(origin_offset.to_untyped()))
1411                        }
1412                        None => return None,
1413                    }
1414                }
1415
1416                // Assume animations start at the identity transform for snapping purposes.
1417                // We still want to incorporate the reference frame offset however.
1418                // TODO(aosmond): Is there a better known starting point?
1419                PropertyBinding::Binding(..) => {
1420                    let origin_offset = info.origin_in_parent_reference_frame;
1421                    ScaleOffset::from_offset(origin_offset.to_untyped())
1422                }
1423            }
1424        }
1425        _ => ScaleOffset::identity(),
1426    };
1427
1428    Some(scale_offset.then(&parent_scale_offset))
1429}
1430
1431#[cfg(test)]
1432fn add_reference_frame(
1433    cst: &mut SceneSpatialTree,
1434    parent: SpatialNodeIndex,
1435    transform: LayoutTransform,
1436    origin_in_parent_reference_frame: LayoutVector2D,
1437    key: SpatialTreeItemKey,
1438) -> SpatialNodeIndex {
1439    let pid = PipelineInstanceId::new(0);
1440
1441    cst.add_reference_frame(
1442        parent,
1443        TransformStyle::Preserve3D,
1444        PropertyBinding::Value(transform),
1445        ReferenceFrameKind::Transform {
1446            is_2d_scale_translation: false,
1447            should_snap: false,
1448            paired_with_perspective: false,
1449        },
1450        origin_in_parent_reference_frame,
1451        PipelineId::dummy(),
1452        SpatialNodeUid::external(key, PipelineId::dummy(), pid),
1453    )
1454}
1455
1456#[cfg(test)]
1457fn test_pt(
1458    px: f32,
1459    py: f32,
1460    cst: &SpatialTree,
1461    child: SpatialNodeIndex,
1462    parent: SpatialNodeIndex,
1463    expected_x: f32,
1464    expected_y: f32,
1465) {
1466    use euclid::approxeq::ApproxEq;
1467    const EPSILON: f32 = 0.0001;
1468
1469    let p = LayoutPoint::new(px, py);
1470    let m = cst.get_relative_transform(child, parent).into_transform();
1471    let pt = m.transform_point2d(p).unwrap();
1472    assert!(pt.x.approx_eq_eps(&expected_x, &EPSILON) &&
1473            pt.y.approx_eq_eps(&expected_y, &EPSILON),
1474            "p: {:?} -> {:?}\nm={:?}",
1475            p, pt, m,
1476            );
1477}
1478
1479#[test]
1480fn test_cst_simple_translation() {
1481    // Basic translations only
1482
1483    let mut cst = SceneSpatialTree::new();
1484    let root_reference_frame_index = cst.root_reference_frame_index();
1485
1486    let root = add_reference_frame(
1487        &mut cst,
1488        root_reference_frame_index,
1489        LayoutTransform::identity(),
1490        LayoutVector2D::zero(),
1491        SpatialTreeItemKey::new(0, 0),
1492    );
1493
1494    let child1 = add_reference_frame(
1495        &mut cst,
1496        root,
1497        LayoutTransform::translation(100.0, 0.0, 0.0),
1498        LayoutVector2D::zero(),
1499        SpatialTreeItemKey::new(0, 1),
1500    );
1501
1502    let child2 = add_reference_frame(
1503        &mut cst,
1504        child1,
1505        LayoutTransform::translation(0.0, 50.0, 0.0),
1506        LayoutVector2D::zero(),
1507        SpatialTreeItemKey::new(0, 2),
1508    );
1509
1510    let child3 = add_reference_frame(
1511        &mut cst,
1512        child2,
1513        LayoutTransform::translation(200.0, 200.0, 0.0),
1514        LayoutVector2D::zero(),
1515        SpatialTreeItemKey::new(0, 3),
1516    );
1517
1518    let mut st = SpatialTree::new();
1519    st.apply_updates(cst.end_frame_and_get_pending_updates());
1520    st.update_tree(&SceneProperties::new());
1521
1522    test_pt(100.0, 100.0, &st, child1, root, 200.0, 100.0);
1523    test_pt(100.0, 100.0, &st, child2, root, 200.0, 150.0);
1524    test_pt(100.0, 100.0, &st, child2, child1, 100.0, 150.0);
1525    test_pt(100.0, 100.0, &st, child3, root, 400.0, 350.0);
1526}
1527
1528#[test]
1529fn test_cst_simple_scale() {
1530    // Basic scale only
1531
1532    let mut cst = SceneSpatialTree::new();
1533    let root_reference_frame_index = cst.root_reference_frame_index();
1534
1535    let root = add_reference_frame(
1536        &mut cst,
1537        root_reference_frame_index,
1538        LayoutTransform::identity(),
1539        LayoutVector2D::zero(),
1540        SpatialTreeItemKey::new(0, 0),
1541    );
1542
1543    let child1 = add_reference_frame(
1544        &mut cst,
1545        root,
1546        LayoutTransform::scale(4.0, 1.0, 1.0),
1547        LayoutVector2D::zero(),
1548        SpatialTreeItemKey::new(0, 1),
1549    );
1550
1551    let child2 = add_reference_frame(
1552        &mut cst,
1553        child1,
1554        LayoutTransform::scale(1.0, 2.0, 1.0),
1555        LayoutVector2D::zero(),
1556        SpatialTreeItemKey::new(0, 2),
1557    );
1558
1559    let child3 = add_reference_frame(
1560        &mut cst,
1561        child2,
1562        LayoutTransform::scale(2.0, 2.0, 1.0),
1563        LayoutVector2D::zero(),
1564        SpatialTreeItemKey::new(0, 3),
1565    );
1566
1567    let mut st = SpatialTree::new();
1568    st.apply_updates(cst.end_frame_and_get_pending_updates());
1569    st.update_tree(&SceneProperties::new());
1570
1571    test_pt(100.0, 100.0, &st, child1, root, 400.0, 100.0);
1572    test_pt(100.0, 100.0, &st, child2, root, 400.0, 200.0);
1573    test_pt(100.0, 100.0, &st, child3, root, 800.0, 400.0);
1574    test_pt(100.0, 100.0, &st, child2, child1, 100.0, 200.0);
1575    test_pt(100.0, 100.0, &st, child3, child1, 200.0, 400.0);
1576}
1577
1578#[test]
1579fn test_cst_scale_translation() {
1580    // Scale + translation
1581
1582    let mut cst = SceneSpatialTree::new();
1583    let root_reference_frame_index = cst.root_reference_frame_index();
1584
1585    let root = add_reference_frame(
1586        &mut cst,
1587        root_reference_frame_index,
1588        LayoutTransform::identity(),
1589        LayoutVector2D::zero(),
1590        SpatialTreeItemKey::new(0, 0),
1591    );
1592
1593    let child1 = add_reference_frame(
1594        &mut cst,
1595        root,
1596        LayoutTransform::translation(100.0, 50.0, 0.0),
1597        LayoutVector2D::zero(),
1598        SpatialTreeItemKey::new(0, 1),
1599    );
1600
1601    let child2 = add_reference_frame(
1602        &mut cst,
1603        child1,
1604        LayoutTransform::scale(2.0, 4.0, 1.0),
1605        LayoutVector2D::zero(),
1606        SpatialTreeItemKey::new(0, 2),
1607    );
1608
1609    let child3 = add_reference_frame(
1610        &mut cst,
1611        child2,
1612        LayoutTransform::translation(200.0, -100.0, 0.0),
1613        LayoutVector2D::zero(),
1614        SpatialTreeItemKey::new(0, 3),
1615    );
1616
1617    let child4 = add_reference_frame(
1618        &mut cst,
1619        child3,
1620        LayoutTransform::scale(3.0, 2.0, 1.0),
1621        LayoutVector2D::zero(),
1622        SpatialTreeItemKey::new(0, 4),
1623    );
1624
1625    let mut st = SpatialTree::new();
1626    st.apply_updates(cst.end_frame_and_get_pending_updates());
1627    st.update_tree(&SceneProperties::new());
1628
1629    test_pt(100.0, 100.0, &st, child1, root, 200.0, 150.0);
1630    test_pt(100.0, 100.0, &st, child2, root, 300.0, 450.0);
1631    test_pt(100.0, 100.0, &st, child4, root, 1100.0, 450.0);
1632
1633    test_pt(0.0, 0.0, &st, child4, child1, 400.0, -400.0);
1634    test_pt(100.0, 100.0, &st, child4, child1, 1000.0, 400.0);
1635    test_pt(100.0, 100.0, &st, child2, child1, 200.0, 400.0);
1636
1637    test_pt(100.0, 100.0, &st, child3, child1, 600.0, 0.0);
1638}
1639
1640#[test]
1641fn test_cst_translation_rotate() {
1642    // Rotation + translation
1643    use euclid::Angle;
1644
1645    let mut cst = SceneSpatialTree::new();
1646    let root_reference_frame_index = cst.root_reference_frame_index();
1647
1648    let root = add_reference_frame(
1649        &mut cst,
1650        root_reference_frame_index,
1651        LayoutTransform::identity(),
1652        LayoutVector2D::zero(),
1653        SpatialTreeItemKey::new(0, 0),
1654    );
1655
1656    let child1 = add_reference_frame(
1657        &mut cst,
1658        root,
1659        LayoutTransform::rotation(0.0, 0.0, 1.0, Angle::degrees(-90.0)),
1660        LayoutVector2D::zero(),
1661        SpatialTreeItemKey::new(0, 1),
1662    );
1663
1664    let mut st = SpatialTree::new();
1665    st.apply_updates(cst.end_frame_and_get_pending_updates());
1666    st.update_tree(&SceneProperties::new());
1667
1668    test_pt(100.0, 0.0, &st, child1, root, 0.0, -100.0);
1669}
1670
1671#[test]
1672fn test_is_ancestor1() {
1673    let mut st = SceneSpatialTree::new();
1674    let root_reference_frame_index = st.root_reference_frame_index();
1675
1676    let root = add_reference_frame(
1677        &mut st,
1678        root_reference_frame_index,
1679        LayoutTransform::identity(),
1680        LayoutVector2D::zero(),
1681        SpatialTreeItemKey::new(0, 0),
1682    );
1683
1684    let child1_0 = add_reference_frame(
1685        &mut st,
1686        root,
1687        LayoutTransform::identity(),
1688        LayoutVector2D::zero(),
1689        SpatialTreeItemKey::new(0, 1),
1690    );
1691
1692    let child1_1 = add_reference_frame(
1693        &mut st,
1694        child1_0,
1695        LayoutTransform::identity(),
1696        LayoutVector2D::zero(),
1697        SpatialTreeItemKey::new(0, 2),
1698    );
1699
1700    let child2 = add_reference_frame(
1701        &mut st,
1702        root,
1703        LayoutTransform::identity(),
1704        LayoutVector2D::zero(),
1705        SpatialTreeItemKey::new(0, 3),
1706    );
1707
1708    assert!(!st.is_ancestor(root, root));
1709    assert!(!st.is_ancestor(child1_0, child1_0));
1710    assert!(!st.is_ancestor(child1_1, child1_1));
1711    assert!(!st.is_ancestor(child2, child2));
1712
1713    assert!(st.is_ancestor(root, child1_0));
1714    assert!(st.is_ancestor(root, child1_1));
1715    assert!(st.is_ancestor(child1_0, child1_1));
1716
1717    assert!(!st.is_ancestor(child1_0, root));
1718    assert!(!st.is_ancestor(child1_1, root));
1719    assert!(!st.is_ancestor(child1_1, child1_0));
1720
1721    assert!(st.is_ancestor(root, child2));
1722    assert!(!st.is_ancestor(child2, root));
1723
1724    assert!(!st.is_ancestor(child1_0, child2));
1725    assert!(!st.is_ancestor(child1_1, child2));
1726    assert!(!st.is_ancestor(child2, child1_0));
1727    assert!(!st.is_ancestor(child2, child1_1));
1728}
1729
1730/// Tests that we select the correct scroll root in the simple case.
1731#[test]
1732fn test_find_scroll_root_simple() {
1733    let mut st = SceneSpatialTree::new();
1734    let pid = PipelineInstanceId::new(0);
1735
1736    let root = st.add_reference_frame(
1737        st.root_reference_frame_index(),
1738        TransformStyle::Flat,
1739        PropertyBinding::Value(LayoutTransform::identity()),
1740        ReferenceFrameKind::Transform {
1741            is_2d_scale_translation: true,
1742            should_snap: true,
1743            paired_with_perspective: false,
1744        },
1745        LayoutVector2D::new(0.0, 0.0),
1746        PipelineId::dummy(),
1747        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
1748    );
1749
1750    let scroll = st.add_scroll_frame(
1751        root,
1752        ExternalScrollId(1, PipelineId::dummy()),
1753        PipelineId::dummy(),
1754        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1755        &LayoutSize::new(800.0, 400.0),
1756        ScrollFrameKind::Explicit,
1757        LayoutVector2D::new(0.0, 0.0),
1758        APZScrollGeneration::default(),
1759        HasScrollLinkedEffect::No,
1760        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
1761    );
1762
1763    assert_eq!(st.find_scroll_root(scroll, true), scroll);
1764}
1765
1766/// Tests that we select the root scroll frame rather than the subframe if both are scrollable.
1767#[test]
1768fn test_find_scroll_root_sub_scroll_frame() {
1769    let mut st = SceneSpatialTree::new();
1770    let pid = PipelineInstanceId::new(0);
1771
1772    let root = st.add_reference_frame(
1773        st.root_reference_frame_index(),
1774        TransformStyle::Flat,
1775        PropertyBinding::Value(LayoutTransform::identity()),
1776        ReferenceFrameKind::Transform {
1777            is_2d_scale_translation: true,
1778            should_snap: true,
1779            paired_with_perspective: false,
1780        },
1781        LayoutVector2D::new(0.0, 0.0),
1782        PipelineId::dummy(),
1783        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
1784    );
1785
1786    let root_scroll = st.add_scroll_frame(
1787        root,
1788        ExternalScrollId(1, PipelineId::dummy()),
1789        PipelineId::dummy(),
1790        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1791        &LayoutSize::new(800.0, 400.0),
1792        ScrollFrameKind::Explicit,
1793        LayoutVector2D::new(0.0, 0.0),
1794        APZScrollGeneration::default(),
1795        HasScrollLinkedEffect::No,
1796        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
1797    );
1798
1799    let sub_scroll = st.add_scroll_frame(
1800        root_scroll,
1801        ExternalScrollId(1, PipelineId::dummy()),
1802        PipelineId::dummy(),
1803        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1804        &LayoutSize::new(800.0, 400.0),
1805        ScrollFrameKind::Explicit,
1806        LayoutVector2D::new(0.0, 0.0),
1807        APZScrollGeneration::default(),
1808        HasScrollLinkedEffect::No,
1809        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
1810    );
1811
1812    assert_eq!(st.find_scroll_root(sub_scroll, true), root_scroll);
1813}
1814
1815/// Tests that we select the sub scroll frame when the root scroll frame is not scrollable.
1816#[test]
1817fn test_find_scroll_root_not_scrollable() {
1818    let mut st = SceneSpatialTree::new();
1819    let pid = PipelineInstanceId::new(0);
1820
1821    let root = st.add_reference_frame(
1822        st.root_reference_frame_index(),
1823        TransformStyle::Flat,
1824        PropertyBinding::Value(LayoutTransform::identity()),
1825        ReferenceFrameKind::Transform {
1826            is_2d_scale_translation: true,
1827            should_snap: true,
1828            paired_with_perspective: false,
1829        },
1830        LayoutVector2D::new(0.0, 0.0),
1831        PipelineId::dummy(),
1832        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
1833    );
1834
1835    let root_scroll = st.add_scroll_frame(
1836        root,
1837        ExternalScrollId(1, PipelineId::dummy()),
1838        PipelineId::dummy(),
1839        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1840        &LayoutSize::new(400.0, 400.0),
1841        ScrollFrameKind::Explicit,
1842        LayoutVector2D::new(0.0, 0.0),
1843        APZScrollGeneration::default(),
1844        HasScrollLinkedEffect::No,
1845        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
1846    );
1847
1848    let sub_scroll = st.add_scroll_frame(
1849        root_scroll,
1850        ExternalScrollId(1, PipelineId::dummy()),
1851        PipelineId::dummy(),
1852        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1853        &LayoutSize::new(800.0, 400.0),
1854        ScrollFrameKind::Explicit,
1855        LayoutVector2D::new(0.0, 0.0),
1856        APZScrollGeneration::default(),
1857        HasScrollLinkedEffect::No,
1858        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
1859    );
1860
1861    assert_eq!(st.find_scroll_root(sub_scroll, true), sub_scroll);
1862}
1863
1864/// Tests that we select the sub scroll frame when the root scroll frame is too small.
1865#[test]
1866fn test_find_scroll_root_too_small() {
1867    let mut st = SceneSpatialTree::new();
1868    let pid = PipelineInstanceId::new(0);
1869
1870    let root = st.add_reference_frame(
1871        st.root_reference_frame_index(),
1872        TransformStyle::Flat,
1873        PropertyBinding::Value(LayoutTransform::identity()),
1874        ReferenceFrameKind::Transform {
1875            is_2d_scale_translation: true,
1876            should_snap: true,
1877            paired_with_perspective: false,
1878        },
1879        LayoutVector2D::new(0.0, 0.0),
1880        PipelineId::dummy(),
1881        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
1882    );
1883
1884    let root_scroll = st.add_scroll_frame(
1885        root,
1886        ExternalScrollId(1, PipelineId::dummy()),
1887        PipelineId::dummy(),
1888        &LayoutRect::from_size(LayoutSize::new(MIN_SCROLL_ROOT_SIZE, MIN_SCROLL_ROOT_SIZE)),
1889        &LayoutSize::new(1000.0, 1000.0),
1890        ScrollFrameKind::Explicit,
1891        LayoutVector2D::new(0.0, 0.0),
1892        APZScrollGeneration::default(),
1893        HasScrollLinkedEffect::No,
1894        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
1895    );
1896
1897    let sub_scroll = st.add_scroll_frame(
1898        root_scroll,
1899        ExternalScrollId(1, PipelineId::dummy()),
1900        PipelineId::dummy(),
1901        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1902        &LayoutSize::new(800.0, 400.0),
1903        ScrollFrameKind::Explicit,
1904        LayoutVector2D::new(0.0, 0.0),
1905        APZScrollGeneration::default(),
1906        HasScrollLinkedEffect::No,
1907        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
1908    );
1909
1910    assert_eq!(st.find_scroll_root(sub_scroll, true), sub_scroll);
1911}
1912
1913/// Tests that we select the root scroll node, even if it is not scrollable,
1914/// when encountering a non-axis-aligned transform.
1915#[test]
1916fn test_find_scroll_root_perspective() {
1917    let mut st = SceneSpatialTree::new();
1918    let pid = PipelineInstanceId::new(0);
1919
1920    let root = st.add_reference_frame(
1921        st.root_reference_frame_index(),
1922        TransformStyle::Flat,
1923        PropertyBinding::Value(LayoutTransform::identity()),
1924        ReferenceFrameKind::Transform {
1925            is_2d_scale_translation: true,
1926            should_snap: true,
1927            paired_with_perspective: false,
1928        },
1929        LayoutVector2D::new(0.0, 0.0),
1930        PipelineId::dummy(),
1931        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
1932    );
1933
1934    let root_scroll = st.add_scroll_frame(
1935        root,
1936        ExternalScrollId(1, PipelineId::dummy()),
1937        PipelineId::dummy(),
1938        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1939        &LayoutSize::new(400.0, 400.0),
1940        ScrollFrameKind::Explicit,
1941        LayoutVector2D::new(0.0, 0.0),
1942        APZScrollGeneration::default(),
1943        HasScrollLinkedEffect::No,
1944        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
1945    );
1946
1947    let perspective = st.add_reference_frame(
1948        root_scroll,
1949        TransformStyle::Flat,
1950        PropertyBinding::Value(LayoutTransform::identity()),
1951        ReferenceFrameKind::Perspective {
1952            scrolling_relative_to: None,
1953        },
1954        LayoutVector2D::new(0.0, 0.0),
1955        PipelineId::dummy(),
1956        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
1957    );
1958
1959    let sub_scroll = st.add_scroll_frame(
1960        perspective,
1961        ExternalScrollId(1, PipelineId::dummy()),
1962        PipelineId::dummy(),
1963        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
1964        &LayoutSize::new(800.0, 400.0),
1965        ScrollFrameKind::Explicit,
1966        LayoutVector2D::new(0.0, 0.0),
1967        APZScrollGeneration::default(),
1968        HasScrollLinkedEffect::No,
1969        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 3), PipelineId::dummy(), pid),
1970    );
1971
1972    assert_eq!(st.find_scroll_root(sub_scroll, true), root_scroll);
1973}
1974
1975/// Tests that encountering a 2D scale or translation transform does not prevent
1976/// us from selecting the sub scroll frame if the root scroll frame is unscrollable.
1977#[test]
1978fn test_find_scroll_root_2d_scale() {
1979    let mut st = SceneSpatialTree::new();
1980    let pid = PipelineInstanceId::new(0);
1981
1982    let root = st.add_reference_frame(
1983        st.root_reference_frame_index(),
1984        TransformStyle::Flat,
1985        PropertyBinding::Value(LayoutTransform::identity()),
1986        ReferenceFrameKind::Transform {
1987            is_2d_scale_translation: true,
1988            should_snap: true,
1989            paired_with_perspective: false,
1990        },
1991        LayoutVector2D::new(0.0, 0.0),
1992        PipelineId::dummy(),
1993        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
1994    );
1995
1996    let root_scroll = st.add_scroll_frame(
1997        root,
1998        ExternalScrollId(1, PipelineId::dummy()),
1999        PipelineId::dummy(),
2000        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
2001        &LayoutSize::new(400.0, 400.0),
2002        ScrollFrameKind::Explicit,
2003        LayoutVector2D::new(0.0, 0.0),
2004        APZScrollGeneration::default(),
2005        HasScrollLinkedEffect::No,
2006        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
2007    );
2008
2009    let scale = st.add_reference_frame(
2010        root_scroll,
2011        TransformStyle::Flat,
2012        PropertyBinding::Value(LayoutTransform::identity()),
2013        ReferenceFrameKind::Transform {
2014            is_2d_scale_translation: true,
2015            should_snap: false,
2016            paired_with_perspective: false,
2017        },
2018        LayoutVector2D::new(0.0, 0.0),
2019        PipelineId::dummy(),
2020        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 2), PipelineId::dummy(), pid),
2021    );
2022
2023    let sub_scroll = st.add_scroll_frame(
2024        scale,
2025        ExternalScrollId(1, PipelineId::dummy()),
2026        PipelineId::dummy(),
2027        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
2028        &LayoutSize::new(800.0, 400.0),
2029        ScrollFrameKind::Explicit,
2030        LayoutVector2D::new(0.0, 0.0),
2031        APZScrollGeneration::default(),
2032        HasScrollLinkedEffect::No,
2033        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 3), PipelineId::dummy(), pid),
2034    );
2035
2036    assert_eq!(st.find_scroll_root(sub_scroll, true), sub_scroll);
2037}
2038
2039/// Tests that a sticky spatial node is chosen as the scroll root rather than
2040/// its parent scroll frame
2041#[test]
2042fn test_find_scroll_root_sticky() {
2043    let mut st = SceneSpatialTree::new();
2044    let pid = PipelineInstanceId::new(0);
2045
2046    let root = st.add_reference_frame(
2047        st.root_reference_frame_index(),
2048        TransformStyle::Flat,
2049        PropertyBinding::Value(LayoutTransform::identity()),
2050        ReferenceFrameKind::Transform {
2051            is_2d_scale_translation: true,
2052            should_snap: true,
2053            paired_with_perspective: false,
2054        },
2055        LayoutVector2D::new(0.0, 0.0),
2056        PipelineId::dummy(),
2057        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 0), PipelineId::dummy(), pid),
2058    );
2059
2060    let scroll = st.add_scroll_frame(
2061        root,
2062        ExternalScrollId(1, PipelineId::dummy()),
2063        PipelineId::dummy(),
2064        &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
2065        &LayoutSize::new(400.0, 800.0),
2066        ScrollFrameKind::Explicit,
2067        LayoutVector2D::new(0.0, 0.0),
2068        APZScrollGeneration::default(),
2069        HasScrollLinkedEffect::No,
2070        SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid),
2071    );
2072
2073    let sticky = st.add_sticky_frame(
2074        scroll,
2075        StickyFrameInfo {
2076            frame_rect: LayoutRect::from_size(LayoutSize::new(400.0, 100.0)),
2077            margins: euclid::SideOffsets2D::new(Some(0.0), None, None, None),
2078            vertical_offset_bounds: api::StickyOffsetBounds::new(0.0, 0.0),
2079            horizontal_offset_bounds: api::StickyOffsetBounds::new(0.0, 0.0),
2080            previously_applied_offset: LayoutVector2D::zero(),
2081            current_offset: LayoutVector2D::zero(),
2082            transform: None
2083        },
2084        PipelineId::dummy(),
2085        SpatialTreeItemKey::new(0, 2),
2086        pid,
2087    );
2088
2089    assert_eq!(st.find_scroll_root(sticky, true), sticky);
2090    assert_eq!(st.find_scroll_root(sticky, false), scroll);
2091}
2092
2093#[test]
2094fn test_world_transforms() {
2095  // Create a spatial tree with a scroll frame node with scroll offset (0, 200).
2096  let mut cst = SceneSpatialTree::new();
2097  let pid = PipelineInstanceId::new(0);
2098  let scroll = cst.add_scroll_frame(
2099      cst.root_reference_frame_index(),
2100      ExternalScrollId(1, PipelineId::dummy()),
2101      PipelineId::dummy(),
2102      &LayoutRect::from_size(LayoutSize::new(400.0, 400.0)),
2103      &LayoutSize::new(400.0, 800.0),
2104      ScrollFrameKind::Explicit, 
2105      LayoutVector2D::new(0.0, 200.0),
2106      APZScrollGeneration::default(),
2107      HasScrollLinkedEffect::No,
2108      SpatialNodeUid::external(SpatialTreeItemKey::new(0, 1), PipelineId::dummy(), pid));
2109
2110  let mut st = SpatialTree::new();
2111  st.apply_updates(cst.end_frame_and_get_pending_updates());
2112  st.update_tree(&SceneProperties::new());
2113
2114  // The node's world transform should reflect the scroll offset,
2115  // e.g. here it should be (0, -200) to reflect that the content has been
2116  // scrolled up by 200px.
2117  assert_eq!(
2118      st.get_world_transform(scroll).into_transform(),
2119      LayoutToWorldTransform::translation(0.0, -200.0, 0.0));
2120
2121  // The node's world viewport transform only reflects enclosing scrolling
2122  // or transforms. Here we don't have any, so it should be the identity.
2123  assert_eq!(
2124      st.get_world_viewport_transform(scroll).into_transform(),
2125      LayoutToWorldTransform::identity());
2126}
2127
2128/// Tests that a spatial node that is async zooming and all of its descendants
2129/// are correctly marked as having themselves an ancestor that is zooming.
2130#[test]
2131fn test_is_ancestor_or_self_zooming() {
2132    let mut cst = SceneSpatialTree::new();
2133    let root_reference_frame_index = cst.root_reference_frame_index();
2134
2135    let root = add_reference_frame(
2136        &mut cst,
2137        root_reference_frame_index,
2138        LayoutTransform::identity(),
2139        LayoutVector2D::zero(),
2140        SpatialTreeItemKey::new(0, 0),
2141    );
2142    let child1 = add_reference_frame(
2143        &mut cst,
2144        root,
2145        LayoutTransform::identity(),
2146        LayoutVector2D::zero(),
2147        SpatialTreeItemKey::new(0, 1),
2148    );
2149    let child2 = add_reference_frame(
2150        &mut cst,
2151        child1,
2152        LayoutTransform::identity(),
2153        LayoutVector2D::zero(),
2154        SpatialTreeItemKey::new(0, 2),
2155    );
2156
2157    let mut st = SpatialTree::new();
2158    st.apply_updates(cst.end_frame_and_get_pending_updates());
2159
2160    // Mark the root node as async zooming
2161    st.get_spatial_node_mut(root).is_async_zooming = true;
2162    st.update_tree(&SceneProperties::new());
2163
2164    // Ensure that the root node and all descendants are marked as having
2165    // themselves or an ancestor zooming
2166    assert!(st.get_spatial_node(root).is_ancestor_or_self_zooming);
2167    assert!(st.get_spatial_node(child1).is_ancestor_or_self_zooming);
2168    assert!(st.get_spatial_node(child2).is_ancestor_or_self_zooming);
2169}