layout: Split stacking context and display list construction (#37047)

Previously, after a layout was finished (or skipped in the case of
repaint-only layout), both the stacking context tree and display list
were built. In the case of repaint-only layout, we should be able to
skip the reconstruction of the stacking context tree and only do display
list building.

This change does that, also generally cleaning and up and clarifying the
data structure used during this phase of layout. This opens up the
possibility of a new kind of incremental layout that does both repaint
and a rebuild of the stacking context tree.

On the blaster.html test case[^1], this reduces tightly-measured layout
time from ~45-50 milliseconds to ~25-30 milliseconds on my M3.

[^1]: https://gist.github.com/mrobinson/44ec87d028c0198917a7715a06dd98a0

Testing: There are currently no performance tests for layout. :( This
should
not modify the results of WPT tests.

Signed-off-by: Martin Robinson <mrobinson@igalia.com>
Co-authored-by: Oriol Brufau <obrufau@igalia.com>

3 files changed, 140 insertions, 59 deletions

diff --git a/components/shared/compositing/display_list.rs b/components/shared/compositing/display_list.rs
index 6aa822cb145..4fb0d5e94db 100644
--- a/components/shared/compositing/display_list.rs
+++ b/components/shared/compositing/display_list.rs
@@ -6,11 +6,17 @@
 
 use base::id::ScrollTreeNodeId;
 use embedder_traits::Cursor;
+use euclid::SideOffsets2D;
 use malloc_size_of_derive::MallocSizeOf;
 use serde::{Deserialize, Serialize};
 use style::values::specified::Overflow;
-use webrender_api::units::{LayoutSize, LayoutVector2D};
-use webrender_api::{Epoch, ExternalScrollId, PipelineId, ScrollLocation, SpatialId};
+use webrender_api::units::{
+    LayoutPixel, LayoutPoint, LayoutRect, LayoutSize, LayoutTransform, LayoutVector2D,
+};
+use webrender_api::{
+    Epoch, ExternalScrollId, PipelineId, ReferenceFrameKind, ScrollLocation, SpatialId,
+    StickyOffsetBounds, TransformStyle,
+};
 
 /// The scroll sensitivity of a scroll node in a particular axis ie whether it can be scrolled due to
 /// input events and script events or only script events.
@@ -56,6 +62,29 @@ pub struct HitTestInfo {
     pub scroll_tree_node: ScrollTreeNodeId,
 }
 
+#[derive(Debug, Deserialize, Serialize)]
+pub enum SpatialTreeNodeInfo {
+    ReferenceFrame(ReferenceFrameNodeInfo),
+    Scroll(ScrollableNodeInfo),
+    Sticky(StickyNodeInfo),
+}
+
+#[derive(Debug, Deserialize, Serialize)]
+pub struct StickyNodeInfo {
+    pub frame_rect: LayoutRect,
+    pub margins: SideOffsets2D<Option<f32>, LayoutPixel>,
+    pub vertical_offset_bounds: StickyOffsetBounds,
+    pub horizontal_offset_bounds: StickyOffsetBounds,
+}
+
+#[derive(Debug, Deserialize, Serialize)]
+pub struct ReferenceFrameNodeInfo {
+    pub origin: LayoutPoint,
+    pub transform_style: TransformStyle,
+    pub transform: LayoutTransform,
+    pub kind: ReferenceFrameKind,
+}
+
 /// Data stored for nodes in the [ScrollTree] that actually scroll,
 /// as opposed to reference frames and sticky nodes which do not.
 #[derive(Debug, Deserialize, Serialize)]
@@ -64,8 +93,11 @@ pub struct ScrollableNodeInfo {
     /// it between successive re-layouts.
     pub external_id: ExternalScrollId,
 
-    /// Amount that this `ScrollableNode` can scroll in both directions.
-    pub scrollable_size: LayoutSize,
+    /// The content rectangle for this scroll node;
+    pub content_rect: LayoutRect,
+
+    /// The clip rectange for this scroll node.
+    pub clip_rect: LayoutRect,
 
     /// Whether this `ScrollableNode` is sensitive to input events.
     pub scroll_sensitivity: AxesScrollSensitivity,
@@ -74,6 +106,12 @@ pub struct ScrollableNodeInfo {
     pub offset: LayoutVector2D,
 }
 
+impl ScrollableNodeInfo {
+    fn scrollable_size(&self) -> LayoutSize {
+        self.content_rect.size() - self.clip_rect.size()
+    }
+}
+
 #[derive(Debug, Deserialize, Serialize)]
 /// A node in a tree of scroll nodes. This may either be a scrollable
 /// node which responds to scroll events or a non-scrollable one.
@@ -82,35 +120,51 @@ pub struct ScrollTreeNode {
     /// None then this is the root node.
     pub parent: Option<ScrollTreeNodeId>,
 
-    /// Scrolling data which will not be None if this is a scrolling node.
-    pub scroll_info: Option<ScrollableNodeInfo>,
+    /// The WebRender id, which is filled in when this tree is serialiezd
+    /// into a WebRender display list.
+    pub webrender_id: Option<SpatialId>,
+
+    /// Specific information about this node, depending on whether it is a scroll node
+    /// or a reference frame.
+    pub info: SpatialTreeNodeInfo,
 }
 
 impl ScrollTreeNode {
+    /// Get the WebRender [`SpatialId`] for the given [`ScrollNodeId`]. This will
+    /// panic if [`ScrollTree::build_display_list`] has not been called yet.
+    pub fn webrender_id(&self) -> SpatialId {
+        self.webrender_id
+            .expect("Should have called ScrollTree::build_display_list before querying SpatialId")
+    }
+
     /// Get the external id of this node.
     pub fn external_id(&self) -> Option<ExternalScrollId> {
-        self.scroll_info.as_ref().map(|info| info.external_id)
+        match self.info {
+            SpatialTreeNodeInfo::Scroll(ref info) => Some(info.external_id),
+            _ => None,
+        }
     }
 
     /// Get the offset id of this node if it applies.
     pub fn offset(&self) -> Option<LayoutVector2D> {
-        self.scroll_info.as_ref().map(|info| info.offset)
+        match self.info {
+            SpatialTreeNodeInfo::Scroll(ref info) => Some(info.offset),
+            _ => None,
+        }
     }
 
     /// Set the offset for this node, returns false if this was a
     /// non-scrolling node for which you cannot set the offset.
     pub fn set_offset(&mut self, new_offset: LayoutVector2D) -> bool {
-        match self.scroll_info {
-            Some(ref mut info) => {
-                let scrollable_width = info.scrollable_size.width;
-                let scrollable_height = info.scrollable_size.height;
-
-                if scrollable_width > 0. {
-                    info.offset.x = (new_offset.x).min(0.0).max(-scrollable_width);
+        match self.info {
+            SpatialTreeNodeInfo::Scroll(ref mut info) => {
+                let scrollable_size = info.scrollable_size();
+                if scrollable_size.width > 0. {
+                    info.offset.x = (new_offset.x).min(0.0).max(-scrollable_size.width);
                 }
 
-                if scrollable_height > 0. {
-                    info.offset.y = (new_offset.y).min(0.0).max(-scrollable_height);
+                if scrollable_size.height > 0. {
+                    info.offset.y = (new_offset.y).min(0.0).max(-scrollable_size.height);
                 }
                 true
             },
@@ -125,9 +179,9 @@ impl ScrollTreeNode {
         &mut self,
         scroll_location: ScrollLocation,
     ) -> Option<(ExternalScrollId, LayoutVector2D)> {
-        let info = match self.scroll_info {
-            Some(ref mut data) => data,
-            None => return None,
+        let info = match self.info {
+            SpatialTreeNodeInfo::Scroll(ref mut info) => info,
+            _ => return None,
         };
 
         if info.scroll_sensitivity.x != ScrollSensitivity::ScriptAndInputEvents &&
@@ -148,7 +202,7 @@ impl ScrollTreeNode {
                 return Some((info.external_id, info.offset));
             },
             ScrollLocation::End => {
-                let end_pos = -info.scrollable_size.height;
+                let end_pos = -info.scrollable_size().height;
                 if info.offset.y.round() <= end_pos {
                     // Nothing to do on this layer.
                     return None;
@@ -159,20 +213,23 @@ impl ScrollTreeNode {
             },
         };
 
-        let scrollable_width = info.scrollable_size.width;
-        let scrollable_height = info.scrollable_size.height;
+        let scrollable_size = info.scrollable_size();
         let original_layer_scroll_offset = info.offset;
 
-        if scrollable_width > 0. &&
+        if scrollable_size.width > 0. &&
             info.scroll_sensitivity.x == ScrollSensitivity::ScriptAndInputEvents
         {
-            info.offset.x = (info.offset.x + delta.x).min(0.0).max(-scrollable_width);
+            info.offset.x = (info.offset.x + delta.x)
+                .min(0.0)
+                .max(-scrollable_size.width);
         }
 
-        if scrollable_height > 0. &&
+        if scrollable_size.height > 0. &&
             info.scroll_sensitivity.y == ScrollSensitivity::ScriptAndInputEvents
         {
-            info.offset.y = (info.offset.y + delta.y).min(0.0).max(-scrollable_height);
+            info.offset.y = (info.offset.y + delta.y)
+                .min(0.0)
+                .max(-scrollable_size.height);
         }
 
         if info.offset != original_layer_scroll_offset {
@@ -199,16 +256,23 @@ impl ScrollTree {
     pub fn add_scroll_tree_node(
         &mut self,
         parent: Option<&ScrollTreeNodeId>,
-        spatial_id: SpatialId,
-        scroll_info: Option<ScrollableNodeInfo>,
+        info: SpatialTreeNodeInfo,
     ) -> ScrollTreeNodeId {
         self.nodes.push(ScrollTreeNode {
             parent: parent.cloned(),
-            scroll_info,
+            webrender_id: None,
+            info,
         });
         ScrollTreeNodeId {
             index: self.nodes.len() - 1,
-            spatial_id,
+        }
+    }
+
+    /// Once WebRender display list construction is complete for this [`ScrollTree`], update
+    /// the mapping of nodes to WebRender [`SpatialId`]s.
+    pub fn update_mapping(&mut self, mapping: Vec<SpatialId>) {
+        for (spatial_id, node) in mapping.into_iter().zip(self.nodes.iter_mut()) {
+            node.webrender_id = Some(spatial_id);
         }
     }
 
@@ -218,10 +282,16 @@ impl ScrollTree {
     }
 
     /// Get an immutable reference to the node with the given index.
-    pub fn get_node(&mut self, id: &ScrollTreeNodeId) -> &ScrollTreeNode {
+    pub fn get_node(&self, id: &ScrollTreeNodeId) -> &ScrollTreeNode {
         &self.nodes[id.index]
     }
 
+    /// Get the WebRender [`SpatialId`] for the given [`ScrollNodeId`]. This will
+    /// panic if [`ScrollTree::build_display_list`] has not been called yet.
+    pub fn webrender_id(&self, id: &ScrollTreeNodeId) -> SpatialId {
+        self.get_node(id).webrender_id()
+    }
+
     /// Scroll the given scroll node on this scroll tree. If the node cannot be scrolled,
     /// because it isn't a scrollable node or it's already scrolled to the maximum scroll
     /// extent, try to scroll an ancestor of this node. Returns the node scrolled and the
@@ -251,8 +321,10 @@ impl ScrollTree {
         offset: LayoutVector2D,
     ) -> bool {
         for node in self.nodes.iter_mut() {
-            match node.scroll_info {
-                Some(ref mut scroll_info) if scroll_info.external_id == external_scroll_id => {
+            match node.info {
+                SpatialTreeNodeInfo::Scroll(ref mut scroll_info)
+                    if scroll_info.external_id == external_scroll_id =>
+                {
                     scroll_info.offset = offset;
                     return true;
                 },
@@ -320,15 +392,19 @@ impl CompositorDisplayListInfo {
         let mut scroll_tree = ScrollTree::default();
         let root_reference_frame_id = scroll_tree.add_scroll_tree_node(
             None,
-            SpatialId::root_reference_frame(pipeline_id),
-            None,
+            SpatialTreeNodeInfo::ReferenceFrame(ReferenceFrameNodeInfo {
+                origin: Default::default(),
+                transform_style: TransformStyle::Flat,
+                transform: LayoutTransform::identity(),
+                kind: ReferenceFrameKind::default(),
+            }),
         );
         let root_scroll_node_id = scroll_tree.add_scroll_tree_node(
             Some(&root_reference_frame_id),
-            SpatialId::root_scroll_node(pipeline_id),
-            Some(ScrollableNodeInfo {
+            SpatialTreeNodeInfo::Scroll(ScrollableNodeInfo {
                 external_id: ExternalScrollId(0, pipeline_id),
-                scrollable_size: content_size - viewport_size,
+                content_rect: LayoutRect::from_origin_and_size(LayoutPoint::zero(), content_size),
+                clip_rect: LayoutRect::from_origin_and_size(LayoutPoint::zero(), viewport_size),
                 scroll_sensitivity: viewport_scroll_sensitivity,
                 offset: LayoutVector2D::zero(),
             }),
diff --git a/components/shared/compositing/lib.rs b/components/shared/compositing/lib.rs
index a6701ca2b52..061dfe023df 100644
--- a/components/shared/compositing/lib.rs
+++ b/components/shared/compositing/lib.rs
@@ -236,7 +236,7 @@ impl CrossProcessCompositorApi {
     pub fn send_display_list(
         &self,
         webview_id: WebViewId,
-        display_list_info: CompositorDisplayListInfo,
+        display_list_info: &CompositorDisplayListInfo,
         list: BuiltDisplayList,
     ) {
         let (display_list_data, display_list_descriptor) = list.into_data();
diff --git a/components/shared/compositing/tests/compositor.rs b/components/shared/compositing/tests/compositor.rs
index 4d2ecfd99c9..e04f1770964 100644
--- a/components/shared/compositing/tests/compositor.rs
+++ b/components/shared/compositing/tests/compositor.rs
@@ -4,11 +4,12 @@
 
 use base::id::ScrollTreeNodeId;
 use compositing_traits::display_list::{
-    AxesScrollSensitivity, ScrollSensitivity, ScrollTree, ScrollableNodeInfo,
+    AxesScrollSensitivity, ScrollSensitivity, ScrollTree, ScrollableNodeInfo, SpatialTreeNodeInfo,
+    StickyNodeInfo,
 };
-use euclid::Size2D;
+use euclid::{SideOffsets2D, Size2D};
 use webrender_api::units::LayoutVector2D;
-use webrender_api::{ExternalScrollId, PipelineId, ScrollLocation, SpatialId};
+use webrender_api::{ExternalScrollId, PipelineId, ScrollLocation, StickyOffsetBounds};
 
 fn add_mock_scroll_node(tree: &mut ScrollTree) -> ScrollTreeNodeId {
     let pipeline_id = PipelineId(0, 0);
@@ -16,7 +17,6 @@ fn add_mock_scroll_node(tree: &mut ScrollTree) -> ScrollTreeNodeId {
     let parent = if num_nodes > 0 {
         Some(ScrollTreeNodeId {
             index: num_nodes - 1,
-            spatial_id: SpatialId::new(num_nodes - 1, pipeline_id),
         })
     } else {
         None
@@ -24,10 +24,10 @@ fn add_mock_scroll_node(tree: &mut ScrollTree) -> ScrollTreeNodeId {
 
     tree.add_scroll_tree_node(
         parent.as_ref(),
-        SpatialId::new(num_nodes, pipeline_id),
-        Some(ScrollableNodeInfo {
+        SpatialTreeNodeInfo::Scroll(ScrollableNodeInfo {
             external_id: ExternalScrollId(num_nodes as u64, pipeline_id),
-            scrollable_size: Size2D::new(100.0, 100.0),
+            content_rect: Size2D::new(200.0, 200.0).into(),
+            clip_rect: Size2D::new(100.0, 100.0).into(),
             scroll_sensitivity: AxesScrollSensitivity {
                 x: ScrollSensitivity::ScriptAndInputEvents,
                 y: ScrollSensitivity::ScriptAndInputEvents,
@@ -78,8 +78,15 @@ fn test_scroll_tree_simple_scroll_chaining() {
 
     let pipeline_id = PipelineId(0, 0);
     let parent_id = add_mock_scroll_node(&mut scroll_tree);
-    let unscrollable_child_id =
-        scroll_tree.add_scroll_tree_node(Some(&parent_id), SpatialId::new(1, pipeline_id), None);
+    let unscrollable_child_id = scroll_tree.add_scroll_tree_node(
+        Some(&parent_id),
+        SpatialTreeNodeInfo::Sticky(StickyNodeInfo {
+            frame_rect: Size2D::new(100.0, 100.0).into(),
+            margins: SideOffsets2D::default(),
+            vertical_offset_bounds: StickyOffsetBounds::new(0.0, 0.0),
+            horizontal_offset_bounds: StickyOffsetBounds::new(0.0, 0.0),
+        }),
+    );
 
     let (scrolled_id, offset) = scroll_tree
         .scroll_node_or_ancestor(
@@ -157,16 +164,14 @@ fn test_scroll_tree_chain_through_overflow_hidden() {
     let pipeline_id = PipelineId(0, 0);
     let parent_id = add_mock_scroll_node(&mut scroll_tree);
     let overflow_hidden_id = add_mock_scroll_node(&mut scroll_tree);
-    scroll_tree
-        .get_node_mut(&overflow_hidden_id)
-        .scroll_info
-        .as_mut()
-        .map(|info| {
-            info.scroll_sensitivity = AxesScrollSensitivity {
-                x: ScrollSensitivity::Script,
-                y: ScrollSensitivity::Script,
-            };
-        });
+    let node = scroll_tree.get_node_mut(&overflow_hidden_id);
+
+    if let SpatialTreeNodeInfo::Scroll(ref mut scroll_node_info) = node.info {
+        scroll_node_info.scroll_sensitivity = AxesScrollSensitivity {
+            x: ScrollSensitivity::Script,
+            y: ScrollSensitivity::Script,
+        };
+    }
 
     let (scrolled_id, offset) = scroll_tree
         .scroll_node_or_ancestor(