/* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ //! Defines data structures which are consumed by the Compositor. use std::collections::HashMap; use base::id::ScrollTreeNodeId; use base::print_tree::PrintTree; use bitflags::bitflags; 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::{ LayoutPixel, LayoutPoint, LayoutRect, LayoutSize, LayoutTransform, LayoutVector2D, }; use webrender_api::{ Epoch, ExternalScrollId, PipelineId, ReferenceFrameKind, ScrollLocation, SpatialId, StickyOffsetBounds, TransformStyle, }; /// A scroll type, describing whether what kind of action originated this scroll request. /// This is a bitflag as it is also used to track what kinds of [`ScrollType`]s scroll /// nodes are sensitive to. #[derive(Clone, Copy, Debug, Deserialize, MallocSizeOf, PartialEq, Serialize)] pub struct ScrollType(u8); bitflags! { impl ScrollType: u8 { /// This node can be scrolled by input events or an input event originated this /// scroll. const InputEvents = 1 << 0; /// This node can be scrolled by script events or script originated this scroll. const Script = 1 << 1; } } /// Convert [Overflow] to [ScrollSensitivity]. impl From for ScrollType { fn from(overflow: Overflow) -> Self { match overflow { Overflow::Hidden => ScrollType::Script, Overflow::Scroll | Overflow::Auto => ScrollType::Script | ScrollType::InputEvents, Overflow::Visible | Overflow::Clip => ScrollType::empty(), } } } /// The [ScrollSensitivity] of particular node in the vertical and horizontal axes. #[derive(Clone, Copy, Debug, Deserialize, MallocSizeOf, PartialEq, Serialize)] pub struct AxesScrollSensitivity { pub x: ScrollType, pub y: ScrollType, } /// Information that Servo keeps alongside WebRender display items /// in order to add more context to hit test results. #[derive(Debug, Deserialize, PartialEq, Serialize)] pub struct HitTestInfo { /// The id of the node of this hit test item. pub node: u64, /// The cursor of this node's hit test item. pub cursor: Option, /// The id of the [ScrollTree] associated with this hit test item. 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, 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)] pub struct ScrollableNodeInfo { /// The external scroll id of this node, used to track /// it between successive re-layouts. pub external_id: ExternalScrollId, /// 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, /// The current offset of this scroll node. pub offset: LayoutVector2D, } impl ScrollableNodeInfo { fn scroll_to_offset( &mut self, new_offset: LayoutVector2D, context: ScrollType, ) -> Option { if !self.scroll_sensitivity.x.contains(context) && !self.scroll_sensitivity.y.contains(context) { return None; } let scrollable_size = self.scrollable_size(); let original_layer_scroll_offset = self.offset; if scrollable_size.width > 0. && self.scroll_sensitivity.x.contains(context) { self.offset.x = new_offset.x.min(0.0).max(-scrollable_size.width); } if scrollable_size.height > 0. && self.scroll_sensitivity.y.contains(context) { self.offset.y = new_offset.y.min(0.0).max(-scrollable_size.height); } if self.offset != original_layer_scroll_offset { Some(self.offset) } else { None } } fn scroll_to_webrender_location( &mut self, scroll_location: ScrollLocation, context: ScrollType, ) -> Option { if !self.scroll_sensitivity.x.contains(context) && !self.scroll_sensitivity.y.contains(context) { return None; } let delta = match scroll_location { ScrollLocation::Delta(delta) => delta, ScrollLocation::Start => { if self.offset.y.round() >= 0.0 { // Nothing to do on this layer. return None; } self.offset.y = 0.0; return Some(self.offset); }, ScrollLocation::End => { let end_pos = -self.scrollable_size().height; if self.offset.y.round() <= end_pos { // Nothing to do on this layer. return None; } self.offset.y = end_pos; return Some(self.offset); }, }; self.scroll_to_offset(self.offset + delta, context) } } 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. pub struct ScrollTreeNode { /// The index of the parent of this node in the tree. If this is /// None then this is the root node. pub parent: Option, /// The WebRender id, which is filled in when this tree is serialiezd /// into a WebRender display list. pub webrender_id: Option, /// 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 { 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 { 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.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_size.height > 0. { info.offset.y = (new_offset.y).min(0.0).max(-scrollable_size.height); } true }, _ => false, } } /// Scroll this node given a WebRender ScrollLocation. Returns a tuple that can /// be used to scroll an individual WebRender scroll frame if the operation /// actually changed an offset. pub fn scroll( &mut self, scroll_location: ScrollLocation, context: ScrollType, ) -> Option<(ExternalScrollId, LayoutVector2D)> { let SpatialTreeNodeInfo::Scroll(ref mut info) = self.info else { return None; }; info.scroll_to_webrender_location(scroll_location, context) .map(|location| (info.external_id, location)) } pub fn debug_print(&self, print_tree: &mut PrintTree, node_index: usize) { match &self.info { SpatialTreeNodeInfo::ReferenceFrame(info) => { print_tree.new_level(format!( "Reference Frame({node_index}): webrender_id={:?}\ \norigin: {:?}\ \ntransform_style: {:?}\ \ntransform: {:?}\ \nkind: {:?}", self.webrender_id, info.origin, info.transform_style, info.transform, info.kind, )); }, SpatialTreeNodeInfo::Scroll(info) => { print_tree.new_level(format!( "Scroll Frame({node_index}): webrender_id={:?}\ \nexternal_id: {:?}\ \ncontent_rect: {:?}\ \nclip_rect: {:?}\ \nscroll_sensitivity: {:?}\ \noffset: {:?}", self.webrender_id, info.external_id, info.content_rect, info.clip_rect, info.scroll_sensitivity, info.offset, )); }, SpatialTreeNodeInfo::Sticky(info) => { print_tree.new_level(format!( "Sticky Frame({node_index}): webrender_id={:?}\ \nframe_rect: {:?}\ \nmargins: {:?}\ \nhorizontal_offset_bounds: {:?}\ \nvertical_offset_bounds: {:?}", self.webrender_id, info.frame_rect, info.margins, info.horizontal_offset_bounds, info.vertical_offset_bounds, )); }, }; } } /// A tree of spatial nodes, which mirrors the spatial nodes in the WebRender /// display list, except these are used to scrolling in the compositor so that /// new offsets can be sent to WebRender. #[derive(Debug, Default, Deserialize, Serialize)] pub struct ScrollTree { /// A list of compositor-side scroll nodes that describe the tree /// of WebRender spatial nodes, used by the compositor to scroll the /// contents of the display list. pub nodes: Vec, } impl ScrollTree { /// Add a scroll node to this ScrollTree returning the id of the new node. pub fn add_scroll_tree_node( &mut self, parent: Option<&ScrollTreeNodeId>, info: SpatialTreeNodeInfo, ) -> ScrollTreeNodeId { self.nodes.push(ScrollTreeNode { parent: parent.cloned(), webrender_id: None, info, }); ScrollTreeNodeId { index: self.nodes.len() - 1, } } /// 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) { for (spatial_id, node) in mapping.into_iter().zip(self.nodes.iter_mut()) { node.webrender_id = Some(spatial_id); } } /// Get a mutable reference to the node with the given index. pub fn get_node_mut(&mut self, id: &ScrollTreeNodeId) -> &mut ScrollTreeNode { &mut self.nodes[id.index] } /// Get an immutable reference to the node with the given index. 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 /// new offset if a scroll was performed, otherwise returns None. pub fn scroll_node_or_ancestor( &mut self, scroll_node_id: &ScrollTreeNodeId, scroll_location: ScrollLocation, context: ScrollType, ) -> Option<(ExternalScrollId, LayoutVector2D)> { let parent = { let node = &mut self.get_node_mut(scroll_node_id); let result = node.scroll(scroll_location, context); if result.is_some() { return result; } node.parent }; parent.and_then(|parent| self.scroll_node_or_ancestor(&parent, scroll_location, context)) } /// Given an [`ExternalScrollId`] and an offset, update the scroll offset of the scroll node /// with the given id. pub fn set_scroll_offset_for_node_with_external_scroll_id( &mut self, external_scroll_id: ExternalScrollId, offset: LayoutVector2D, context: ScrollType, ) -> Option { self.nodes.iter_mut().find_map(|node| match node.info { SpatialTreeNodeInfo::Scroll(ref mut scroll_info) if scroll_info.external_id == external_scroll_id => { scroll_info.scroll_to_offset(offset, context) }, _ => None, }) } /// Given a set of all scroll offsets coming from the Servo renderer, update all of the offsets /// for nodes that actually exist in this tree. pub fn set_all_scroll_offsets(&mut self, offsets: &HashMap) { for node in self.nodes.iter_mut() { if let SpatialTreeNodeInfo::Scroll(ref mut scroll_info) = node.info { if let Some(offset) = offsets.get(&scroll_info.external_id) { scroll_info.offset = *offset; } } } } /// Collect all of the scroll offsets of the scrolling nodes of this tree into a /// [`HashMap`] which can be applied to another tree. pub fn scroll_offsets(&self) -> HashMap { HashMap::from_iter(self.nodes.iter().filter_map(|node| match node.info { SpatialTreeNodeInfo::Scroll(ref scroll_info) => { Some((scroll_info.external_id, scroll_info.offset)) }, _ => None, })) } /// Get the scroll offset for the given [`ExternalScrollId`] or `None` if that node cannot /// be found in the tree. pub fn scroll_offset(&self, id: ExternalScrollId) -> Option { self.nodes.iter().find_map(|node| match node.info { SpatialTreeNodeInfo::Scroll(ref info) if info.external_id == id => Some(info.offset), _ => None, }) } } /// In order to pretty print the [ScrollTree] structure, we are converting /// the node list inside the tree to be a adjacency list. The adjacency list /// then is used for the [ScrollTree::debug_print_traversal] of the tree. /// /// This preprocessing helps decouples print logic a lot from its construction. type AdjacencyListForPrint = Vec>; /// Implementation of [ScrollTree] that is related to debugging. // FIXME: probably we could have a universal trait for this. Especially for // structures that utilizes PrintTree. impl ScrollTree { fn nodes_in_adjacency_list(&self) -> AdjacencyListForPrint { let mut adjacency_list: AdjacencyListForPrint = vec![Default::default(); self.nodes.len()]; for (node_index, node) in self.nodes.iter().enumerate() { let current_id = ScrollTreeNodeId { index: node_index }; if let Some(parent_id) = node.parent { adjacency_list[parent_id.index].push(current_id); } } adjacency_list } fn debug_print_traversal( &self, print_tree: &mut PrintTree, current_id: &ScrollTreeNodeId, adjacency_list: &[Vec], ) { for node_id in &adjacency_list[current_id.index] { self.nodes[node_id.index].debug_print(print_tree, node_id.index); self.debug_print_traversal(print_tree, node_id, adjacency_list); } print_tree.end_level(); } /// Print the [ScrollTree]. Particularly, we are printing the node in /// preorder traversal. The order of the nodes will depends of the /// index of a node in the [ScrollTree] which corresponds to the /// declarations of the nodes. // TODO(stevennovaryo): add information about which fragment that // defines this node. pub fn debug_print(&self) { let mut print_tree = PrintTree::new("Scroll Tree".to_owned()); let adj_list = self.nodes_in_adjacency_list(); let root_id = ScrollTreeNodeId { index: 0 }; self.nodes[root_id.index].debug_print(&mut print_tree, root_id.index); self.debug_print_traversal(&mut print_tree, &root_id, &adj_list); print_tree.end_level(); } } /// A data structure which stores compositor-side information about /// display lists sent to the compositor. #[derive(Debug, Deserialize, Serialize)] pub struct CompositorDisplayListInfo { /// The WebRender [PipelineId] of this display list. pub pipeline_id: PipelineId, /// The size of the viewport that this display list renders into. pub viewport_size: LayoutSize, /// The size of this display list's content. pub content_size: LayoutSize, /// The epoch of the display list. pub epoch: Epoch, /// An array of `HitTestInfo` which is used to store information /// to assist the compositor to take various actions (set the cursor, /// scroll without layout) using a WebRender hit test result. pub hit_test_info: Vec, /// A ScrollTree used by the compositor to scroll the contents of the /// display list. pub scroll_tree: ScrollTree, /// The `ScrollTreeNodeId` of the root reference frame of this info's scroll /// tree. pub root_reference_frame_id: ScrollTreeNodeId, /// The `ScrollTreeNodeId` of the topmost scrolling frame of this info's scroll /// tree. pub root_scroll_node_id: ScrollTreeNodeId, /// Contentful paint i.e. whether the display list contains items of type /// text, image, non-white canvas or SVG). Used by metrics. /// See . pub is_contentful: bool, /// Whether the first layout or a subsequent (incremental) layout triggered this /// display list creation. pub first_reflow: bool, } impl CompositorDisplayListInfo { /// Create a new CompositorDisplayListInfo with the root reference frame /// and scroll frame already added to the scroll tree. pub fn new( viewport_size: LayoutSize, content_size: LayoutSize, pipeline_id: PipelineId, epoch: Epoch, viewport_scroll_sensitivity: AxesScrollSensitivity, first_reflow: bool, ) -> Self { let mut scroll_tree = ScrollTree::default(); let root_reference_frame_id = scroll_tree.add_scroll_tree_node( 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), SpatialTreeNodeInfo::Scroll(ScrollableNodeInfo { external_id: ExternalScrollId(0, pipeline_id), 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(), }), ); CompositorDisplayListInfo { pipeline_id, viewport_size, content_size, epoch, hit_test_info: Default::default(), scroll_tree, root_reference_frame_id, root_scroll_node_id, is_contentful: false, first_reflow, } } /// Add or re-use a duplicate HitTestInfo entry in this `CompositorHitTestInfo` /// and return the index. pub fn add_hit_test_info( &mut self, node: u64, cursor: Option, scroll_tree_node: ScrollTreeNodeId, ) -> usize { let hit_test_info = HitTestInfo { node, cursor, scroll_tree_node, }; if let Some(last) = self.hit_test_info.last() { if hit_test_info == *last { return self.hit_test_info.len() - 1; } } self.hit_test_info.push(hit_test_info); self.hit_test_info.len() - 1 } }