layout/display_list/
hit_test.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
5use std::sync::Arc;
6
7use app_units::Au;
8use embedder_traits::Cursor;
9use euclid::{Box2D, Vector2D};
10use kurbo::{Ellipse, Shape};
11use layout_api::ElementsFromPointResult;
12use rustc_hash::FxHashMap;
13use servo_base::id::ScrollTreeNodeId;
14use servo_geometry::FastLayoutTransform;
15use style::computed_values::backface_visibility::T as BackfaceVisibility;
16use style::computed_values::pointer_events::T as PointerEvents;
17use style::computed_values::visibility::T as Visibility;
18use style::properties::ComputedValues;
19use style::values::computed::ui::CursorKind;
20use webrender_api::BorderRadius;
21use webrender_api::units::{LayoutPoint, LayoutRect, LayoutSize, RectExt};
22
23use crate::display_list::clip::{Clip, ClipId};
24use crate::display_list::paint_traversal::{PaintTraversal, PaintTraversalHandler};
25use crate::display_list::{StackingContext, StackingContextTree, ToWebRender, TraversalState};
26use crate::fragment_tree::{BoxFragmentWithStyle, Fragment, FragmentFlags, TextFragment};
27use crate::geom::PhysicalRect;
28
29pub(crate) struct HitTest<'a> {
30    /// The point to test for this hit test, relative to the page.
31    point_to_test: LayoutPoint,
32    /// A cached version of [`Self::point_to_test`] projected to a spatial node, to avoid
33    /// doing a lot of matrix math over and over.
34    projected_point_to_test: Option<(ScrollTreeNodeId, LayoutPoint, FastLayoutTransform)>,
35    /// The stacking context tree against which to perform the hit test.
36    stacking_context_tree: &'a StackingContextTree,
37    /// The resulting [`HitTestResultItems`] for this hit test.
38    results: Vec<ElementsFromPointResult>,
39    /// A cache of hit test results for shared clip nodes.
40    clip_hit_test_results: FxHashMap<ClipId, bool>,
41}
42
43impl<'a> HitTest<'a> {
44    pub(crate) fn run(
45        stacking_context_tree: &'a StackingContextTree,
46        point_to_test: LayoutPoint,
47    ) -> Vec<ElementsFromPointResult> {
48        let mut hit_test = Self {
49            point_to_test,
50            projected_point_to_test: None,
51            stacking_context_tree,
52            results: Vec::new(),
53            clip_hit_test_results: FxHashMap::default(),
54        };
55
56        PaintTraversal::traverse(&stacking_context_tree.root_stacking_context, &mut hit_test);
57
58        // PaintTraversal::traverse walks forward through all fragments via the stacking
59        // context tree, so results will be in back-to-front order. We want results to be
60        // front-to-back order, so reverse them.
61        //
62        // TODO: Eventually PaintTraversal should support walking backward through
63        // fragments.
64        hit_test.results.reverse();
65
66        hit_test.results
67    }
68
69    /// Perform a hit test against a the clip node for the given [`ClipId`], returning
70    /// true if it is not clipped out or false if is clipped out.
71    fn hit_test_clip_id(&mut self, clip_id: ClipId) -> bool {
72        if clip_id == ClipId::INVALID {
73            return true;
74        }
75
76        if let Some(result) = self.clip_hit_test_results.get(&clip_id) {
77            return *result;
78        }
79
80        let clip = self.stacking_context_tree.clip_store.get(clip_id);
81        let result = self
82            .location_in_spatial_node(clip.parent_scroll_node_id)
83            .is_some_and(|(point, _)| {
84                clip.contains(point) && self.hit_test_clip_id(clip.parent_clip_id)
85            });
86        self.clip_hit_test_results.insert(clip_id, result);
87        result
88    }
89
90    /// Get the hit test location in the coordinate system of the given spatial node,
91    /// returning `None` if the transformation is uninvertible or the point cannot be
92    /// projected into the spatial node.
93    fn location_in_spatial_node(
94        &mut self,
95        scroll_tree_node_id: ScrollTreeNodeId,
96    ) -> Option<(LayoutPoint, FastLayoutTransform)> {
97        match self.projected_point_to_test {
98            Some((cached_scroll_tree_node_id, projected_point, transform))
99                if cached_scroll_tree_node_id == scroll_tree_node_id =>
100            {
101                return Some((projected_point, transform));
102            },
103            _ => {},
104        }
105
106        let transform = self
107            .stacking_context_tree
108            .paint_info
109            .scroll_tree
110            .cumulative_root_to_node_transform(scroll_tree_node_id)?;
111
112        let projected_point = transform.project_point2d(self.point_to_test)?;
113
114        self.projected_point_to_test = Some((scroll_tree_node_id, projected_point, transform));
115        Some((projected_point, transform))
116    }
117}
118
119impl PaintTraversalHandler for HitTest<'_> {
120    type StackingContextState = ();
121
122    fn visit_stacking_context(&mut self, _: &StackingContext) -> Self::StackingContextState {}
123    fn leave_stacking_context(&mut self, _: &TraversalState, _: Self::StackingContextState) {}
124    fn visit_box(&mut self, state: &TraversalState, fragment: &BoxFragmentWithStyle<'_>) {
125        Fragment::Box(fragment.box_fragment.clone()).hit_test(state, self);
126    }
127    fn visit_text(
128        &mut self,
129        state: &TraversalState,
130        _: PhysicalRect<Au>,
131        fragment: &Arc<TextFragment>,
132    ) {
133        Fragment::Text(fragment.clone()).hit_test(state, self);
134    }
135}
136
137impl Clip {
138    fn contains(&self, point: LayoutPoint) -> bool {
139        rounded_rect_contains_point(self.rect, &self.radii, point)
140    }
141}
142
143impl Fragment {
144    pub(crate) fn hit_test(&self, state: &TraversalState, hit_test: &mut HitTest) -> bool {
145        let Some(tag) = self.tag() else {
146            return false;
147        };
148        if !hit_test.hit_test_clip_id(state.clip_id) {
149            return false;
150        }
151
152        let mut hit_test_fragment_inner =
153            |style: &ComputedValues,
154             fragment_rect: PhysicalRect<Au>,
155             border_radius: BorderRadius,
156             fragment_flags: FragmentFlags,
157             auto_cursor: Cursor| {
158                let is_root_element = fragment_flags.contains(FragmentFlags::IS_ROOT_ELEMENT);
159
160                if !is_root_element {
161                    if style.get_inherited_ui().pointer_events == PointerEvents::None {
162                        return false;
163                    }
164                    if style.get_inherited_box().visibility != Visibility::Visible {
165                        return false;
166                    }
167                }
168
169                let (point_in_spatial_node, transform) =
170                    match hit_test.location_in_spatial_node(state.spatial_id) {
171                        Some(point) => point,
172                        None => return false,
173                    };
174
175                if !is_root_element &&
176                    style.get_box().backface_visibility == BackfaceVisibility::Hidden &&
177                    transform.is_backface_visible()
178                {
179                    return false;
180                }
181
182                let fragment_rect = fragment_rect.translate(state.origin.to_vector());
183                if is_root_element {
184                    let viewport_size = hit_test
185                        .stacking_context_tree
186                        .paint_info
187                        .viewport_details
188                        .size;
189                    let viewport_rect = LayoutRect::from_origin_and_size(
190                        Default::default(),
191                        viewport_size.cast_unit(),
192                    );
193                    if !viewport_rect.contains(hit_test.point_to_test) {
194                        return false;
195                    }
196                } else if !rounded_rect_contains_point(
197                    fragment_rect.to_webrender(),
198                    &border_radius,
199                    point_in_spatial_node,
200                ) {
201                    return false;
202                }
203
204                let point_in_target = point_in_spatial_node.cast_unit() -
205                    Vector2D::new(
206                        fragment_rect.origin.x.to_f32_px(),
207                        fragment_rect.origin.y.to_f32_px(),
208                    );
209
210                hit_test.results.push(ElementsFromPointResult {
211                    node: tag.node,
212                    point_in_target,
213                    cursor: cursor(style.get_inherited_ui().cursor.keyword, auto_cursor),
214                });
215
216                // Since there is no reverse PaintTraversal, hit testing always searches
217                // the entire fragment tree (in stacking context order), which is why this
218                // is always returning `false` (keep looking). Once PaintTraversal can
219                // walk backward through fragments, this can return `true` if FindAll
220                // isn't specified.
221                false
222            };
223
224        match self {
225            Fragment::LayoutRoot(layout_root_fragment) => {
226                layout_root_fragment.inner().hit_test(state, hit_test)
227            },
228            Fragment::Box(box_fragment) | Fragment::Float(box_fragment) => hit_test_fragment_inner(
229                &box_fragment.style(),
230                box_fragment.border_rect(),
231                box_fragment.border_radius(),
232                box_fragment.base.flags,
233                Cursor::Default,
234            ),
235            Fragment::Text(text) => hit_test_fragment_inner(
236                &text.base.style(),
237                text.base.rect(),
238                BorderRadius::zero(),
239                FragmentFlags::empty(),
240                Cursor::Text,
241            ),
242            _ => false,
243        }
244    }
245}
246
247fn rounded_rect_contains_point(
248    rect: LayoutRect,
249    border_radius: &BorderRadius,
250    point: LayoutPoint,
251) -> bool {
252    if !rect.contains(point) {
253        return false;
254    }
255
256    if border_radius.is_zero() {
257        return true;
258    }
259
260    let check_corner = |corner: LayoutPoint, radius: &LayoutSize, is_right, is_bottom| {
261        let mut origin = corner;
262        if is_right {
263            origin.x -= radius.width;
264        }
265        if is_bottom {
266            origin.y -= radius.height;
267        }
268        if !Box2D::from_origin_and_size(origin, *radius).contains(point) {
269            return true;
270        }
271        let center = (
272            if is_right {
273                corner.x - radius.width
274            } else {
275                corner.x + radius.width
276            },
277            if is_bottom {
278                corner.y - radius.height
279            } else {
280                corner.y + radius.height
281            },
282        );
283        let radius = (radius.width as f64, radius.height as f64);
284        Ellipse::new(center, radius, 0.0).contains((point.x, point.y).into())
285    };
286
287    check_corner(rect.top_left(), &border_radius.top_left, false, false) &&
288        check_corner(rect.top_right(), &border_radius.top_right, true, false) &&
289        check_corner(rect.bottom_right(), &border_radius.bottom_right, true, true) &&
290        check_corner(rect.bottom_left(), &border_radius.bottom_left, false, true)
291}
292
293fn cursor(kind: CursorKind, auto_cursor: Cursor) -> Cursor {
294    match kind {
295        CursorKind::Auto => auto_cursor,
296        CursorKind::None => Cursor::None,
297        CursorKind::Default => Cursor::Default,
298        CursorKind::Pointer => Cursor::Pointer,
299        CursorKind::ContextMenu => Cursor::ContextMenu,
300        CursorKind::Help => Cursor::Help,
301        CursorKind::Progress => Cursor::Progress,
302        CursorKind::Wait => Cursor::Wait,
303        CursorKind::Cell => Cursor::Cell,
304        CursorKind::Crosshair => Cursor::Crosshair,
305        CursorKind::Text => Cursor::Text,
306        CursorKind::VerticalText => Cursor::VerticalText,
307        CursorKind::Alias => Cursor::Alias,
308        CursorKind::Copy => Cursor::Copy,
309        CursorKind::Move => Cursor::Move,
310        CursorKind::NoDrop => Cursor::NoDrop,
311        CursorKind::NotAllowed => Cursor::NotAllowed,
312        CursorKind::Grab => Cursor::Grab,
313        CursorKind::Grabbing => Cursor::Grabbing,
314        CursorKind::EResize => Cursor::EResize,
315        CursorKind::NResize => Cursor::NResize,
316        CursorKind::NeResize => Cursor::NeResize,
317        CursorKind::NwResize => Cursor::NwResize,
318        CursorKind::SResize => Cursor::SResize,
319        CursorKind::SeResize => Cursor::SeResize,
320        CursorKind::SwResize => Cursor::SwResize,
321        CursorKind::WResize => Cursor::WResize,
322        CursorKind::EwResize => Cursor::EwResize,
323        CursorKind::NsResize => Cursor::NsResize,
324        CursorKind::NeswResize => Cursor::NeswResize,
325        CursorKind::NwseResize => Cursor::NwseResize,
326        CursorKind::ColResize => Cursor::ColResize,
327        CursorKind::RowResize => Cursor::RowResize,
328        CursorKind::AllScroll => Cursor::AllScroll,
329        CursorKind::ZoomIn => Cursor::ZoomIn,
330        CursorKind::ZoomOut => Cursor::ZoomOut,
331    }
332}
layout/display_list/hit_test.rs

layout/display_list/
hit_test.rs
