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

paint_api/
display_list.rs
