compositing_traits/
display_list.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 https://mozilla.org/MPL/2.0/. */
4
5//! Defines data structures which are consumed by the Compositor.
6
7use std::cell::Cell;
8use std::collections::HashMap;
9
10use base::Epoch;
11use base::id::ScrollTreeNodeId;
12use base::print_tree::PrintTree;
13use bitflags::bitflags;
14use embedder_traits::ViewportDetails;
15use euclid::SideOffsets2D;
16use malloc_size_of_derive::MallocSizeOf;
17use rustc_hash::FxHashMap;
18use serde::{Deserialize, Serialize};
19use servo_geometry::FastLayoutTransform;
20use style::values::specified::Overflow;
21use webrender_api::units::{LayoutPixel, LayoutPoint, LayoutRect, LayoutSize, LayoutVector2D};
22use webrender_api::{
23    ExternalScrollId, PipelineId, ReferenceFrameKind, ScrollLocation, SpatialId,
24    StickyOffsetBounds, TransformStyle,
25};
26
27/// A scroll type, describing whether what kind of action originated this scroll request.
28/// This is a bitflag as it is also used to track what kinds of [`ScrollType`]s scroll
29/// nodes are sensitive to.
30#[derive(Clone, Copy, Debug, Deserialize, MallocSizeOf, PartialEq, Serialize)]
31pub struct ScrollType(u8);
32
33bitflags! {
34    impl ScrollType: u8 {
35        /// This node can be scrolled by input events or an input event originated this
36        /// scroll.
37        const InputEvents = 1 << 0;
38        /// This node can be scrolled by script events or script originated this scroll.
39        const Script = 1 << 1;
40    }
41}
42
43/// Convert [Overflow] to [ScrollSensitivity].
44impl From<Overflow> for ScrollType {
45    fn from(overflow: Overflow) -> Self {
46        match overflow {
47            Overflow::Hidden => ScrollType::Script,
48            Overflow::Scroll | Overflow::Auto => ScrollType::Script | ScrollType::InputEvents,
49            Overflow::Visible | Overflow::Clip => ScrollType::empty(),
50        }
51    }
52}
53
54/// The [ScrollSensitivity] of particular node in the vertical and horizontal axes.
55#[derive(Clone, Copy, Debug, Deserialize, MallocSizeOf, PartialEq, Serialize)]
56pub struct AxesScrollSensitivity {
57    pub x: ScrollType,
58    pub y: ScrollType,
59}
60
61#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
62pub enum SpatialTreeNodeInfo {
63    ReferenceFrame(ReferenceFrameNodeInfo),
64    Scroll(ScrollableNodeInfo),
65    Sticky(StickyNodeInfo),
66}
67
68#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
69pub struct StickyNodeInfo {
70    pub frame_rect: LayoutRect,
71    pub margins: SideOffsets2D<Option<f32>, LayoutPixel>,
72    pub vertical_offset_bounds: StickyOffsetBounds,
73    pub horizontal_offset_bounds: StickyOffsetBounds,
74}
75
76impl StickyNodeInfo {
77    /// Calculate the sticky offset for this [`StickyNodeInfo`] given information about
78    /// sticky positioning from its ancestors.
79    ///
80    /// This is originally taken from WebRender `SpatialTree` implementation.
81    fn calculate_sticky_offset(
82        &self,
83        viewport_scroll_offset: &LayoutVector2D,
84        viewport_rect: &LayoutRect,
85    ) -> LayoutVector2D {
86        if self.margins.top.is_none() &&
87            self.margins.bottom.is_none() &&
88            self.margins.left.is_none() &&
89            self.margins.right.is_none()
90        {
91            return LayoutVector2D::zero();
92        }
93
94        // The viewport and margins of the item establishes the maximum amount that it can
95        // be offset in order to keep it on screen. Since we care about the relationship
96        // between the scrolled content and unscrolled viewport we adjust the viewport's
97        // position by the scroll offset in order to work with their relative positions on the
98        // page.
99        let mut sticky_rect = self.frame_rect.translate(*viewport_scroll_offset);
100
101        let mut sticky_offset = LayoutVector2D::zero();
102        if let Some(margin) = self.margins.top {
103            let top_viewport_edge = viewport_rect.min.y + margin;
104            if sticky_rect.min.y < top_viewport_edge {
105                // If the sticky rect is positioned above the top edge of the viewport (plus margin)
106                // we move it down so that it is fully inside the viewport.
107                sticky_offset.y = top_viewport_edge - sticky_rect.min.y;
108            }
109        }
110
111        // If we don't have a sticky-top offset (sticky_offset.y == 0) then we check for
112        // handling the bottom margin case. Note that the "don't have a sticky-top offset"
113        // case includes the case where we *had* a sticky-top offset but we reduced it to
114        // zero in the above block.
115        if sticky_offset.y <= 0.0 {
116            if let Some(margin) = self.margins.bottom {
117                // If sticky_offset.y is nonzero that means we must have set it
118                // in the sticky-top handling code above, so this item must have
119                // both top and bottom sticky margins. We adjust the item's rect
120                // by the top-sticky offset, and then combine any offset from
121                // the bottom-sticky calculation into sticky_offset below.
122                sticky_rect.min.y += sticky_offset.y;
123                sticky_rect.max.y += sticky_offset.y;
124
125                // Same as the above case, but inverted for bottom-sticky items. Here
126                // we adjust items upwards, resulting in a negative sticky_offset.y,
127                // or reduce the already-present upward adjustment, resulting in a positive
128                // sticky_offset.y.
129                let bottom_viewport_edge = viewport_rect.max.y - margin;
130                if sticky_rect.max.y > bottom_viewport_edge {
131                    sticky_offset.y += bottom_viewport_edge - sticky_rect.max.y;
132                }
133            }
134        }
135
136        // Same as above, but for the x-axis.
137        if let Some(margin) = self.margins.left {
138            let left_viewport_edge = viewport_rect.min.x + margin;
139            if sticky_rect.min.x < left_viewport_edge {
140                sticky_offset.x = left_viewport_edge - sticky_rect.min.x;
141            }
142        }
143
144        if sticky_offset.x <= 0.0 {
145            if let Some(margin) = self.margins.right {
146                sticky_rect.min.x += sticky_offset.x;
147                sticky_rect.max.x += sticky_offset.x;
148                let right_viewport_edge = viewport_rect.max.x - margin;
149                if sticky_rect.max.x > right_viewport_edge {
150                    sticky_offset.x += right_viewport_edge - sticky_rect.max.x;
151                }
152            }
153        }
154
155        // The total "sticky offset" and the extra amount we computed as a result of
156        // scrolling, stored in sticky_offset needs to be clamped to the provided bounds.
157        let clamp =
158            |value: f32, bounds: &StickyOffsetBounds| (value).max(bounds.min).min(bounds.max);
159        sticky_offset.y = clamp(sticky_offset.y, &self.vertical_offset_bounds);
160        sticky_offset.x = clamp(sticky_offset.x, &self.horizontal_offset_bounds);
161
162        sticky_offset
163    }
164}
165
166#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
167pub struct ReferenceFrameNodeInfo {
168    pub origin: LayoutPoint,
169    /// Origin of this frame relative to the document for bounding box queries.
170    pub frame_origin_for_query: LayoutPoint,
171    pub transform_style: TransformStyle,
172    pub transform: FastLayoutTransform,
173    pub kind: ReferenceFrameKind,
174}
175
176/// Data stored for nodes in the [ScrollTree] that actually scroll,
177/// as opposed to reference frames and sticky nodes which do not.
178#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
179pub struct ScrollableNodeInfo {
180    /// The external scroll id of this node, used to track
181    /// it between successive re-layouts.
182    pub external_id: ExternalScrollId,
183
184    /// The content rectangle for this scroll node;
185    pub content_rect: LayoutRect,
186
187    /// The clip rectange for this scroll node.
188    pub clip_rect: LayoutRect,
189
190    /// Whether this `ScrollableNode` is sensitive to input events.
191    pub scroll_sensitivity: AxesScrollSensitivity,
192
193    /// The current offset of this scroll node.
194    pub offset: LayoutVector2D,
195
196    /// Whether or not the scroll offset of this node has changed and it needs it's
197    /// cached transformations invalidated.
198    pub offset_changed: Cell<bool>,
199}
200
201impl ScrollableNodeInfo {
202    fn scroll_to_offset(
203        &mut self,
204        new_offset: LayoutVector2D,
205        context: ScrollType,
206    ) -> Option<LayoutVector2D> {
207        if !self.scroll_sensitivity.x.contains(context) &&
208            !self.scroll_sensitivity.y.contains(context)
209        {
210            return None;
211        }
212
213        let scrollable_size = self.scrollable_size();
214        let original_layer_scroll_offset = self.offset;
215
216        if scrollable_size.width > 0. && self.scroll_sensitivity.x.contains(context) {
217            self.offset.x = new_offset.x.clamp(0.0, scrollable_size.width);
218        }
219
220        if scrollable_size.height > 0. && self.scroll_sensitivity.y.contains(context) {
221            self.offset.y = new_offset.y.clamp(0.0, scrollable_size.height);
222        }
223
224        if self.offset != original_layer_scroll_offset {
225            self.offset_changed.set(true);
226            Some(self.offset)
227        } else {
228            None
229        }
230    }
231
232    fn scroll_to_webrender_location(
233        &mut self,
234        scroll_location: ScrollLocation,
235        context: ScrollType,
236    ) -> Option<LayoutVector2D> {
237        if !self.scroll_sensitivity.x.contains(context) &&
238            !self.scroll_sensitivity.y.contains(context)
239        {
240            return None;
241        }
242
243        let delta = match scroll_location {
244            ScrollLocation::Delta(delta) => delta,
245            ScrollLocation::Start => {
246                if self.offset.y.round() <= 0.0 {
247                    // Nothing to do on this layer.
248                    return None;
249                }
250
251                self.offset.y = 0.0;
252                self.offset_changed.set(true);
253                return Some(self.offset);
254            },
255            ScrollLocation::End => {
256                let end_pos = self.scrollable_size().height;
257                if self.offset.y.round() >= end_pos {
258                    // Nothing to do on this layer.
259                    return None;
260                }
261
262                self.offset.y = end_pos;
263                self.offset_changed.set(true);
264                return Some(self.offset);
265            },
266        };
267
268        self.scroll_to_offset(self.offset + delta, context)
269    }
270}
271
272impl ScrollableNodeInfo {
273    fn scrollable_size(&self) -> LayoutSize {
274        self.content_rect.size() - self.clip_rect.size()
275    }
276}
277
278/// A cached of transforms of a particular [`ScrollTree`] node in both directions:
279/// mapping from node-relative points to root-relative points and vice-versa.
280///
281/// Potential ideas for improvement:
282///  - Test optimizing simple translations to avoid having to do full matrix
283///    multiplication when transforms are not involved.
284#[derive(Clone, Copy, Debug, Default, Deserialize, MallocSizeOf, Serialize)]
285pub struct ScrollTreeNodeTransformationCache {
286    node_to_root_transform: FastLayoutTransform,
287    root_to_node_transform: Option<FastLayoutTransform>,
288    nearest_scrolling_ancestor_offset: LayoutVector2D,
289    nearest_scrolling_ancestor_viewport: LayoutRect,
290    cumulative_sticky_offsets: LayoutVector2D,
291}
292
293#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
294/// A node in a tree of scroll nodes. This may either be a scrollable
295/// node which responds to scroll events or a non-scrollable one.
296pub struct ScrollTreeNode {
297    /// The index of the parent of this node in the tree. If this is
298    /// None then this is the root node.
299    pub parent: Option<ScrollTreeNodeId>,
300
301    /// The children of this [`ScrollTreeNode`].
302    pub children: Vec<ScrollTreeNodeId>,
303
304    /// The WebRender id, which is filled in when this tree is serialiezd
305    /// into a WebRender display list.
306    pub webrender_id: Option<SpatialId>,
307
308    /// Specific information about this node, depending on whether it is a scroll node
309    /// or a reference frame.
310    pub info: SpatialTreeNodeInfo,
311
312    /// Cached transformation information that's used to do things like hit testing
313    /// and viewport bounding box calculation.
314    transformation_cache: Cell<Option<ScrollTreeNodeTransformationCache>>,
315}
316
317impl ScrollTreeNode {
318    /// Get the WebRender [`SpatialId`] for the given [`ScrollNodeId`]. This will
319    /// panic if [`ScrollTree::build_display_list`] has not been called yet.
320    pub fn webrender_id(&self) -> SpatialId {
321        self.webrender_id
322            .expect("Should have called ScrollTree::build_display_list before querying SpatialId")
323    }
324
325    /// Get the external id of this node.
326    pub fn external_id(&self) -> Option<ExternalScrollId> {
327        match self.info {
328            SpatialTreeNodeInfo::Scroll(ref info) => Some(info.external_id),
329            _ => None,
330        }
331    }
332
333    /// Get the offset id of this node if it applies.
334    pub fn offset(&self) -> Option<LayoutVector2D> {
335        match self.info {
336            SpatialTreeNodeInfo::Scroll(ref info) => Some(info.offset),
337            _ => None,
338        }
339    }
340
341    /// Scroll this node given a WebRender ScrollLocation. Returns a tuple that can
342    /// be used to scroll an individual WebRender scroll frame if the operation
343    /// actually changed an offset.
344    fn scroll(
345        &mut self,
346        scroll_location: ScrollLocation,
347        context: ScrollType,
348    ) -> Option<(ExternalScrollId, LayoutVector2D)> {
349        let SpatialTreeNodeInfo::Scroll(ref mut info) = self.info else {
350            return None;
351        };
352
353        info.scroll_to_webrender_location(scroll_location, context)
354            .map(|location| (info.external_id, location))
355    }
356
357    pub fn debug_print(&self, print_tree: &mut PrintTree, node_index: usize) {
358        match &self.info {
359            SpatialTreeNodeInfo::ReferenceFrame(info) => {
360                print_tree.new_level(format!(
361                    "Reference Frame({node_index}): webrender_id={:?}\
362                        \norigin: {:?}\
363                        \ntransform_style: {:?}\
364                        \ntransform: {:?}\
365                        \nkind: {:?}",
366                    self.webrender_id, info.origin, info.transform_style, info.transform, info.kind,
367                ));
368            },
369            SpatialTreeNodeInfo::Scroll(info) => {
370                print_tree.new_level(format!(
371                    "Scroll Frame({node_index}): webrender_id={:?}\
372                        \nexternal_id: {:?}\
373                        \ncontent_rect: {:?}\
374                        \nclip_rect: {:?}\
375                        \nscroll_sensitivity: {:?}\
376                        \noffset: {:?}",
377                    self.webrender_id,
378                    info.external_id,
379                    info.content_rect,
380                    info.clip_rect,
381                    info.scroll_sensitivity,
382                    info.offset,
383                ));
384            },
385            SpatialTreeNodeInfo::Sticky(info) => {
386                print_tree.new_level(format!(
387                    "Sticky Frame({node_index}): webrender_id={:?}\
388                        \nframe_rect: {:?}\
389                        \nmargins: {:?}\
390                        \nhorizontal_offset_bounds: {:?}\
391                        \nvertical_offset_bounds: {:?}",
392                    self.webrender_id,
393                    info.frame_rect,
394                    info.margins,
395                    info.horizontal_offset_bounds,
396                    info.vertical_offset_bounds,
397                ));
398            },
399        };
400    }
401
402    fn invalidate_cached_transforms(&self, scroll_tree: &ScrollTree, ancestors_invalid: bool) {
403        let node_invalid = match &self.info {
404            SpatialTreeNodeInfo::Scroll(info) => info.offset_changed.take(),
405            _ => false,
406        };
407
408        let invalid = node_invalid || ancestors_invalid;
409        if invalid {
410            self.transformation_cache.set(None);
411        }
412
413        for child_id in &self.children {
414            scroll_tree
415                .get_node(*child_id)
416                .invalidate_cached_transforms(scroll_tree, invalid);
417        }
418    }
419}
420
421/// A tree of spatial nodes, which mirrors the spatial nodes in the WebRender
422/// display list, except these are used to scrolling in the compositor so that
423/// new offsets can be sent to WebRender.
424#[derive(Debug, Default, Deserialize, MallocSizeOf, Serialize)]
425pub struct ScrollTree {
426    /// A list of compositor-side scroll nodes that describe the tree
427    /// of WebRender spatial nodes, used by the compositor to scroll the
428    /// contents of the display list.
429    pub nodes: Vec<ScrollTreeNode>,
430}
431
432impl ScrollTree {
433    /// Add a scroll node to this ScrollTree returning the id of the new node.
434    pub fn add_scroll_tree_node(
435        &mut self,
436        parent: Option<ScrollTreeNodeId>,
437        info: SpatialTreeNodeInfo,
438    ) -> ScrollTreeNodeId {
439        self.nodes.push(ScrollTreeNode {
440            parent,
441            children: Vec::new(),
442            webrender_id: None,
443            info,
444            transformation_cache: Cell::default(),
445        });
446
447        let new_node_id = ScrollTreeNodeId {
448            index: self.nodes.len() - 1,
449        };
450
451        if let Some(parent_id) = parent {
452            self.get_node_mut(parent_id).children.push(new_node_id);
453        }
454
455        new_node_id
456    }
457
458    /// Once WebRender display list construction is complete for this [`ScrollTree`], update
459    /// the mapping of nodes to WebRender [`SpatialId`]s.
460    pub fn update_mapping(&mut self, mapping: Vec<SpatialId>) {
461        for (spatial_id, node) in mapping.into_iter().zip(self.nodes.iter_mut()) {
462            node.webrender_id = Some(spatial_id);
463        }
464    }
465
466    /// Get a mutable reference to the node with the given index.
467    pub fn get_node_mut(&mut self, id: ScrollTreeNodeId) -> &mut ScrollTreeNode {
468        &mut self.nodes[id.index]
469    }
470
471    /// Get an immutable reference to the node with the given index.
472    pub fn get_node(&self, id: ScrollTreeNodeId) -> &ScrollTreeNode {
473        &self.nodes[id.index]
474    }
475
476    /// Get the WebRender [`SpatialId`] for the given [`ScrollNodeId`]. This will
477    /// panic if [`ScrollTree::build_display_list`] has not been called yet.
478    pub fn webrender_id(&self, id: ScrollTreeNodeId) -> SpatialId {
479        self.get_node(id).webrender_id()
480    }
481
482    pub fn scroll_node_or_ancestor_inner(
483        &mut self,
484        scroll_node_id: ScrollTreeNodeId,
485        scroll_location: ScrollLocation,
486        context: ScrollType,
487    ) -> Option<(ExternalScrollId, LayoutVector2D)> {
488        let parent = {
489            let node = &mut self.get_node_mut(scroll_node_id);
490            let result = node.scroll(scroll_location, context);
491            if result.is_some() {
492                return result;
493            }
494            node.parent
495        };
496
497        parent
498            .and_then(|parent| self.scroll_node_or_ancestor_inner(parent, scroll_location, context))
499    }
500
501    fn node_with_external_scroll_node_id(
502        &self,
503        external_id: ExternalScrollId,
504    ) -> Option<ScrollTreeNodeId> {
505        self.nodes
506            .iter()
507            .enumerate()
508            .find_map(|(index, node)| match &node.info {
509                SpatialTreeNodeInfo::Scroll(info) if info.external_id == external_id => {
510                    Some(ScrollTreeNodeId { index })
511                },
512                _ => None,
513            })
514    }
515
516    /// Scroll the scroll node with the given [`ExternalScrollId`] on this scroll tree. If
517    /// the node cannot be scrolled, because it's already scrolled to the maximum scroll
518    /// extent, try to scroll an ancestor of this node. Returns the node scrolled and the
519    /// new offset if a scroll was performed, otherwise returns None.
520    pub fn scroll_node_or_ancestor(
521        &mut self,
522        external_id: ExternalScrollId,
523        scroll_location: ScrollLocation,
524        context: ScrollType,
525    ) -> Option<(ExternalScrollId, LayoutVector2D)> {
526        let scroll_node_id = self.node_with_external_scroll_node_id(external_id)?;
527        let result = self.scroll_node_or_ancestor_inner(scroll_node_id, scroll_location, context);
528        if result.is_some() {
529            self.invalidate_cached_transforms();
530        }
531        result
532    }
533
534    /// Given an [`ExternalScrollId`] and an offset, update the scroll offset of the scroll node
535    /// with the given id.
536    pub fn set_scroll_offset_for_node_with_external_scroll_id(
537        &mut self,
538        external_scroll_id: ExternalScrollId,
539        offset: LayoutVector2D,
540        context: ScrollType,
541    ) -> Option<LayoutVector2D> {
542        let result = self.nodes.iter_mut().find_map(|node| match node.info {
543            SpatialTreeNodeInfo::Scroll(ref mut scroll_info)
544                if scroll_info.external_id == external_scroll_id =>
545            {
546                scroll_info.scroll_to_offset(offset, context)
547            },
548            _ => None,
549        });
550
551        if result.is_some() {
552            self.invalidate_cached_transforms();
553        }
554
555        result
556    }
557
558    /// Given a set of all scroll offsets coming from the Servo renderer, update all of the offsets
559    /// for nodes that actually exist in this tree.
560    pub fn set_all_scroll_offsets(
561        &mut self,
562        offsets: &FxHashMap<ExternalScrollId, LayoutVector2D>,
563    ) {
564        for node in self.nodes.iter_mut() {
565            if let SpatialTreeNodeInfo::Scroll(ref mut scroll_info) = node.info {
566                if let Some(offset) = offsets.get(&scroll_info.external_id) {
567                    scroll_info.scroll_to_offset(*offset, ScrollType::Script);
568                }
569            }
570        }
571
572        self.invalidate_cached_transforms();
573    }
574
575    /// Set the offsets of all scrolling nodes in this tree to 0.
576    pub fn reset_all_scroll_offsets(&mut self) {
577        for node in self.nodes.iter_mut() {
578            if let SpatialTreeNodeInfo::Scroll(ref mut scroll_info) = node.info {
579                scroll_info.scroll_to_offset(LayoutVector2D::zero(), ScrollType::Script);
580            }
581        }
582
583        self.invalidate_cached_transforms();
584    }
585
586    /// Collect all of the scroll offsets of the scrolling nodes of this tree into a
587    /// [`HashMap`] which can be applied to another tree.
588    pub fn scroll_offsets(&self) -> FxHashMap<ExternalScrollId, LayoutVector2D> {
589        HashMap::from_iter(self.nodes.iter().filter_map(|node| match node.info {
590            SpatialTreeNodeInfo::Scroll(ref scroll_info) => {
591                Some((scroll_info.external_id, scroll_info.offset))
592            },
593            _ => None,
594        }))
595    }
596
597    /// Get the scroll offset for the given [`ExternalScrollId`] or `None` if that node cannot
598    /// be found in the tree.
599    pub fn scroll_offset(&self, id: ExternalScrollId) -> Option<LayoutVector2D> {
600        self.nodes.iter().find_map(|node| match node.info {
601            SpatialTreeNodeInfo::Scroll(ref info) if info.external_id == id => Some(info.offset),
602            _ => None,
603        })
604    }
605
606    /// Find a transformation that can convert a point in the node coordinate system to a
607    /// point in the root coordinate system.
608    pub fn cumulative_node_to_root_transform(
609        &self,
610        node_id: ScrollTreeNodeId,
611    ) -> FastLayoutTransform {
612        self.cumulative_node_transform(node_id)
613            .node_to_root_transform
614    }
615
616    /// Find a transformation that can convert a point in the root coordinate system to a
617    /// point in the coordinate system of the given node. This may be `None` if the cumulative
618    /// transform is uninvertible.
619    pub fn cumulative_root_to_node_transform(
620        &self,
621        node_id: ScrollTreeNodeId,
622    ) -> Option<FastLayoutTransform> {
623        self.cumulative_node_transform(node_id)
624            .root_to_node_transform
625    }
626
627    /// Find the cumulative offsets of sticky positioned boxes from the given node up to
628    /// the root.
629    pub fn cumulative_sticky_offsets(&self, node_id: ScrollTreeNodeId) -> LayoutVector2D {
630        self.cumulative_node_transform(node_id)
631            .cumulative_sticky_offsets
632    }
633
634    fn cumulative_node_transform(
635        &self,
636        node_id: ScrollTreeNodeId,
637    ) -> ScrollTreeNodeTransformationCache {
638        let node = self.get_node(node_id);
639        if let Some(cached_transforms) = node.transformation_cache.get() {
640            return cached_transforms;
641        }
642
643        let transforms = self.cumulative_node_transform_inner(node);
644        node.transformation_cache.set(Some(transforms));
645        transforms
646    }
647
648    /// Traverse a scroll node to its root to calculate the transform.
649    fn cumulative_node_transform_inner(
650        &self,
651        node: &ScrollTreeNode,
652    ) -> ScrollTreeNodeTransformationCache {
653        let parent_transforms = node
654            .parent
655            .map(|parent_id| self.cumulative_node_transform(parent_id))
656            .unwrap_or_default();
657
658        let node_to_root_transform = |node_to_parent_transform: FastLayoutTransform| {
659            node_to_parent_transform.then(&parent_transforms.node_to_root_transform)
660        };
661        let root_to_node_transform = |parent_to_node_transform: FastLayoutTransform| {
662            parent_transforms
663                .root_to_node_transform
664                .map_or(parent_to_node_transform, |parent_transform| {
665                    parent_transform.then(&parent_to_node_transform)
666                })
667        };
668
669        match &node.info {
670            SpatialTreeNodeInfo::ReferenceFrame(info) => {
671                // To apply a transformation we need to make sure the rectangle's
672                // coordinate space is the same as reference frame's coordinate space.
673                let offset = info.frame_origin_for_query.to_vector();
674                let node_to_parent_transform =
675                    info.transform.pre_translate(-offset).then_translate(offset);
676                let parent_to_node_transform = info.transform.inverse().map(|inverse_transform| {
677                    FastLayoutTransform::Offset(-info.origin.to_vector()).then(&inverse_transform)
678                });
679                ScrollTreeNodeTransformationCache {
680                    node_to_root_transform: node_to_root_transform(node_to_parent_transform),
681                    root_to_node_transform: parent_to_node_transform.map(root_to_node_transform),
682                    nearest_scrolling_ancestor_viewport: parent_transforms
683                        .nearest_scrolling_ancestor_viewport
684                        .translate(-info.origin.to_vector()),
685                    nearest_scrolling_ancestor_offset: parent_transforms
686                        .nearest_scrolling_ancestor_offset,
687                    cumulative_sticky_offsets: parent_transforms.cumulative_sticky_offsets,
688                }
689            },
690            SpatialTreeNodeInfo::Scroll(info) => {
691                let node_to_parent_transform = FastLayoutTransform::Offset(-info.offset);
692                let parent_to_node_transform = node_to_parent_transform.inverse();
693                ScrollTreeNodeTransformationCache {
694                    node_to_root_transform: node_to_root_transform(node_to_parent_transform),
695                    root_to_node_transform: parent_to_node_transform.map(root_to_node_transform),
696                    nearest_scrolling_ancestor_viewport: info.clip_rect,
697                    nearest_scrolling_ancestor_offset: -info.offset,
698                    cumulative_sticky_offsets: parent_transforms.cumulative_sticky_offsets,
699                }
700            },
701
702            SpatialTreeNodeInfo::Sticky(info) => {
703                let offset = info.calculate_sticky_offset(
704                    &parent_transforms.nearest_scrolling_ancestor_offset,
705                    &parent_transforms.nearest_scrolling_ancestor_viewport,
706                );
707                let node_to_parent_transform = FastLayoutTransform::Offset(offset);
708                let parent_to_node_transform = node_to_parent_transform.inverse();
709                ScrollTreeNodeTransformationCache {
710                    node_to_root_transform: node_to_root_transform(node_to_parent_transform),
711                    root_to_node_transform: parent_to_node_transform.map(root_to_node_transform),
712                    nearest_scrolling_ancestor_viewport: parent_transforms
713                        .nearest_scrolling_ancestor_viewport,
714                    nearest_scrolling_ancestor_offset: parent_transforms
715                        .nearest_scrolling_ancestor_offset +
716                        offset,
717                    cumulative_sticky_offsets: parent_transforms.cumulative_sticky_offsets + offset,
718                }
719            },
720        }
721    }
722
723    fn invalidate_cached_transforms(&self) {
724        let Some(root_node) = self.nodes.first() else {
725            return;
726        };
727        root_node.invalidate_cached_transforms(self, false /* ancestors_invalid */);
728    }
729
730    fn external_scroll_id_for_scroll_tree_node(
731        &self,
732        id: ScrollTreeNodeId,
733    ) -> Option<ExternalScrollId> {
734        let mut maybe_node = Some(self.get_node(id));
735
736        while let Some(node) = maybe_node {
737            if let Some(external_scroll_id) = node.external_id() {
738                return Some(external_scroll_id);
739            }
740            maybe_node = node.parent.map(|id| self.get_node(id));
741        }
742
743        None
744    }
745}
746
747/// In order to pretty print the [ScrollTree] structure, we are converting
748/// the node list inside the tree to be a adjacency list. The adjacency list
749/// then is used for the [ScrollTree::debug_print_traversal] of the tree.
750///
751/// This preprocessing helps decouples print logic a lot from its construction.
752type AdjacencyListForPrint = Vec<Vec<ScrollTreeNodeId>>;
753
754/// Implementation of [ScrollTree] that is related to debugging.
755// FIXME: probably we could have a universal trait for this. Especially for
756//        structures that utilizes PrintTree.
757impl ScrollTree {
758    fn nodes_in_adjacency_list(&self) -> AdjacencyListForPrint {
759        let mut adjacency_list: AdjacencyListForPrint = vec![Default::default(); self.nodes.len()];
760
761        for (node_index, node) in self.nodes.iter().enumerate() {
762            let current_id = ScrollTreeNodeId { index: node_index };
763            if let Some(parent_id) = node.parent {
764                adjacency_list[parent_id.index].push(current_id);
765            }
766        }
767
768        adjacency_list
769    }
770
771    fn debug_print_traversal(
772        &self,
773        print_tree: &mut PrintTree,
774        current_id: ScrollTreeNodeId,
775        adjacency_list: &[Vec<ScrollTreeNodeId>],
776    ) {
777        for node_id in &adjacency_list[current_id.index] {
778            self.nodes[node_id.index].debug_print(print_tree, node_id.index);
779            self.debug_print_traversal(print_tree, *node_id, adjacency_list);
780        }
781        print_tree.end_level();
782    }
783
784    /// Print the [ScrollTree]. Particularly, we are printing the node in
785    /// preorder traversal. The order of the nodes will depends of the
786    /// index of a node in the [ScrollTree] which corresponds to the
787    /// declarations of the nodes.
788    // TODO(stevennovaryo): add information about which fragment that
789    //                      defines this node.
790    pub fn debug_print(&self) {
791        let mut print_tree = PrintTree::new("Scroll Tree".to_owned());
792
793        let adj_list = self.nodes_in_adjacency_list();
794        let root_id = ScrollTreeNodeId { index: 0 };
795
796        self.nodes[root_id.index].debug_print(&mut print_tree, root_id.index);
797        self.debug_print_traversal(&mut print_tree, root_id, &adj_list);
798        print_tree.end_level();
799    }
800}
801
802/// A data structure which stores compositor-side information about
803/// display lists sent to the compositor.
804#[derive(Debug, Deserialize, MallocSizeOf, Serialize)]
805pub struct CompositorDisplayListInfo {
806    /// The WebRender [PipelineId] of this display list.
807    pub pipeline_id: PipelineId,
808
809    /// The [`ViewportDetails`] that describe the viewport in the script/layout thread at
810    /// the time this display list was created.
811    pub viewport_details: ViewportDetails,
812
813    /// The size of this display list's content.
814    pub content_size: LayoutSize,
815
816    /// The epoch of the display list.
817    pub epoch: Epoch,
818
819    /// A ScrollTree used by the compositor to scroll the contents of the
820    /// display list.
821    pub scroll_tree: ScrollTree,
822
823    /// The `ScrollTreeNodeId` of the root reference frame of this info's scroll
824    /// tree.
825    pub root_reference_frame_id: ScrollTreeNodeId,
826
827    /// The `ScrollTreeNodeId` of the topmost scrolling frame of this info's scroll
828    /// tree.
829    pub root_scroll_node_id: ScrollTreeNodeId,
830
831    /// Contentful paint i.e. whether the display list contains items of type
832    /// text, image, non-white canvas or SVG). Used by metrics.
833    /// See <https://w3c.github.io/paint-timing/#first-contentful-paint>.
834    pub is_contentful: bool,
835
836    /// Whether the first layout or a subsequent (incremental) layout triggered this
837    /// display list creation.
838    pub first_reflow: bool,
839}
840
841impl CompositorDisplayListInfo {
842    /// Create a new CompositorDisplayListInfo with the root reference frame
843    /// and scroll frame already added to the scroll tree.
844    pub fn new(
845        viewport_details: ViewportDetails,
846        content_size: LayoutSize,
847        pipeline_id: PipelineId,
848        epoch: Epoch,
849        viewport_scroll_sensitivity: AxesScrollSensitivity,
850        first_reflow: bool,
851    ) -> Self {
852        let mut scroll_tree = ScrollTree::default();
853        let root_reference_frame_id = scroll_tree.add_scroll_tree_node(
854            None,
855            SpatialTreeNodeInfo::ReferenceFrame(ReferenceFrameNodeInfo {
856                origin: Default::default(),
857                frame_origin_for_query: Default::default(),
858                transform_style: TransformStyle::Flat,
859                transform: FastLayoutTransform::identity(),
860                kind: ReferenceFrameKind::default(),
861            }),
862        );
863        let root_scroll_node_id = scroll_tree.add_scroll_tree_node(
864            Some(root_reference_frame_id),
865            SpatialTreeNodeInfo::Scroll(ScrollableNodeInfo {
866                external_id: ExternalScrollId(0, pipeline_id),
867                content_rect: LayoutRect::from_origin_and_size(LayoutPoint::zero(), content_size),
868                clip_rect: LayoutRect::from_origin_and_size(
869                    LayoutPoint::zero(),
870                    viewport_details.layout_size(),
871                ),
872                scroll_sensitivity: viewport_scroll_sensitivity,
873                offset: LayoutVector2D::zero(),
874                offset_changed: Cell::new(false),
875            }),
876        );
877
878        CompositorDisplayListInfo {
879            pipeline_id,
880            viewport_details,
881            content_size,
882            epoch,
883            scroll_tree,
884            root_reference_frame_id,
885            root_scroll_node_id,
886            is_contentful: false,
887            first_reflow,
888        }
889    }
890
891    pub fn external_scroll_id_for_scroll_tree_node(
892        &self,
893        id: ScrollTreeNodeId,
894    ) -> ExternalScrollId {
895        self.scroll_tree
896            .external_scroll_id_for_scroll_tree_node(id)
897            .unwrap_or(ExternalScrollId(0, self.pipeline_id))
898    }
899}