1use api::{BorderRadius, ClipMode, HitTestFlags, HitTestResultItem, HitTestResult, ItemTag, PrimitiveFlags};
6use api::{ApiHitTester, PipelineId};
7use api::units::*;
8use crate::clip::{rounded_rectangle_contains_point, ClipNodeId, ClipTreeBuilder};
9use crate::clip::{polygon_contains_point, ClipItemKey, ClipItemKeyKind};
10use crate::prim_store::PolygonKey;
11use crate::scene_builder_thread::Interners;
12use crate::spatial_tree::{SpatialNodeIndex, SpatialTree, get_external_scroll_offset};
13use crate::internal_types::{FastHashMap, LayoutPrimitiveInfo};
14use std::sync::{Arc, Mutex};
15use crate::util::LayoutToWorldFastTransform;
16
17pub struct SharedHitTester {
18 hit_tester: Mutex<Arc<HitTester>>,
23}
24
25impl SharedHitTester {
26 pub fn new() -> Self {
27 SharedHitTester {
28 hit_tester: Mutex::new(Arc::new(HitTester::empty())),
29 }
30 }
31
32 pub fn get_ref(&self) -> Arc<HitTester> {
33 let guard = self.hit_tester.lock().unwrap();
34 Arc::clone(&*guard)
35 }
36
37 pub(crate) fn update(&self, new_hit_tester: Arc<HitTester>) {
38 let mut guard = self.hit_tester.lock().unwrap();
39 *guard = new_hit_tester;
40 }
41}
42
43impl ApiHitTester for SharedHitTester {
44 fn hit_test(
45 &self,
46 pipeline_id: Option<PipelineId>,
47 point: WorldPoint,
48 flags: HitTestFlags,
49 ) -> HitTestResult {
50 self.get_ref().hit_test(HitTest::new(pipeline_id, point, flags))
51 }
52}
53
54#[derive(MallocSizeOf)]
58struct HitTestSpatialNode {
59 pipeline_id: PipelineId,
61
62 world_content_transform: LayoutToWorldFastTransform,
64
65 world_viewport_transform: LayoutToWorldFastTransform,
67
68 external_scroll_offset: LayoutVector2D,
70}
71
72#[derive(MallocSizeOf)]
73struct HitTestClipNode {
74 region: HitTestRegion,
77 spatial_node_index: SpatialNodeIndex,
79 parent: ClipNodeId,
81}
82
83impl HitTestClipNode {
84 fn new(
85 item: &ClipItemKey,
86 interners: &Interners,
87 parent: ClipNodeId,
88 ) -> Self {
89 let region = match item.kind {
90 ClipItemKeyKind::Rectangle(rect, mode) => {
91 HitTestRegion::Rectangle(rect.into(), mode)
92 }
93 ClipItemKeyKind::RoundedRectangle(rect, radius, mode) => {
94 HitTestRegion::RoundedRectangle(rect.into(), radius.into(), mode)
95 }
96 ClipItemKeyKind::ImageMask(rect, _, polygon_handle) => {
97 if let Some(handle) = polygon_handle {
98 let polygon = &interners.polygon[handle];
100 HitTestRegion::Polygon(rect.into(), *polygon)
101 } else {
102 HitTestRegion::Rectangle(rect.into(), ClipMode::Clip)
103 }
104 }
105 ClipItemKeyKind::BoxShadow(..) => HitTestRegion::Invalid,
106 };
107
108 HitTestClipNode {
109 region,
110 spatial_node_index: item.spatial_node_index,
111 parent,
112 }
113 }
114}
115
116#[derive(Clone, MallocSizeOf)]
117struct HitTestingItem {
118 rect: LayoutRect,
119 tag: ItemTag,
120 animation_id: u64,
121 is_backface_visible: bool,
122 spatial_node_index: SpatialNodeIndex,
123 clip_node_id: ClipNodeId,
124}
125
126impl HitTestingItem {
127 fn new(
128 tag: ItemTag,
129 animation_id: u64,
130 info: &LayoutPrimitiveInfo,
131 spatial_node_index: SpatialNodeIndex,
132 clip_node_id: ClipNodeId,
133 ) -> HitTestingItem {
134 HitTestingItem {
135 rect: info.rect,
136 tag,
137 animation_id,
138 is_backface_visible: info.flags.contains(PrimitiveFlags::IS_BACKFACE_VISIBLE),
139 spatial_node_index,
140 clip_node_id,
141 }
142 }
143}
144
145pub struct HitTestingSceneStats {
148 pub clip_nodes_count: usize,
149 pub items_count: usize,
150}
151
152impl HitTestingSceneStats {
153 pub fn empty() -> Self {
154 HitTestingSceneStats {
155 clip_nodes_count: 0,
156 items_count: 0,
157 }
158 }
159}
160
161#[derive(MallocSizeOf)]
168pub struct HitTestingScene {
169 clip_nodes: FastHashMap<ClipNodeId, HitTestClipNode>,
170
171 items: Vec<HitTestingItem>,
173}
174
175impl HitTestingScene {
176 pub fn new(stats: &HitTestingSceneStats) -> Self {
179 HitTestingScene {
180 clip_nodes: FastHashMap::default(),
181 items: Vec::with_capacity(stats.items_count),
182 }
183 }
184
185 pub fn reset(&mut self) {
186 self.clip_nodes.clear();
187 self.items.clear();
188 }
189
190 pub fn get_stats(&self) -> HitTestingSceneStats {
192 HitTestingSceneStats {
193 clip_nodes_count: 0,
194 items_count: self.items.len(),
195 }
196 }
197
198 fn add_clip_node(
199 &mut self,
200 clip_node_id: ClipNodeId,
201 clip_tree_builder: &ClipTreeBuilder,
202 interners: &Interners,
203 ) {
204 if clip_node_id == ClipNodeId::NONE {
205 return;
206 }
207
208 if !self.clip_nodes.contains_key(&clip_node_id) {
209 let src_clip_node = clip_tree_builder.get_node(clip_node_id);
210 let clip_item = &interners.clip[src_clip_node.handle];
211
212 let clip_node = HitTestClipNode::new(
213 &clip_item.key,
214 interners,
215 src_clip_node.parent,
216 );
217
218 self.clip_nodes.insert(clip_node_id, clip_node);
219
220 self.add_clip_node(
221 src_clip_node.parent,
222 clip_tree_builder,
223 interners,
224 );
225 }
226 }
227
228 pub fn add_item(
230 &mut self,
231 tag: ItemTag,
232 anim_id: u64,
233 info: &LayoutPrimitiveInfo,
234 spatial_node_index: SpatialNodeIndex,
235 clip_node_id: ClipNodeId,
236 clip_tree_builder: &ClipTreeBuilder,
237 interners: &Interners,
238 ) {
239 self.add_clip_node(
240 clip_node_id,
241 clip_tree_builder,
242 interners,
243 );
244
245 let item = HitTestingItem::new(
246 tag,
247 anim_id,
248 info,
249 spatial_node_index,
250 clip_node_id,
251 );
252
253 self.items.push(item);
254 }
255}
256
257#[derive(MallocSizeOf)]
258enum HitTestRegion {
259 Invalid,
260 Rectangle(LayoutRect, ClipMode),
261 RoundedRectangle(LayoutRect, BorderRadius, ClipMode),
262 Polygon(LayoutRect, PolygonKey),
263}
264
265impl HitTestRegion {
266 fn contains(&self, point: &LayoutPoint) -> bool {
267 match *self {
268 HitTestRegion::Rectangle(ref rectangle, ClipMode::Clip) =>
269 rectangle.contains(*point),
270 HitTestRegion::Rectangle(ref rectangle, ClipMode::ClipOut) =>
271 !rectangle.contains(*point),
272 HitTestRegion::RoundedRectangle(rect, radii, ClipMode::Clip) =>
273 rounded_rectangle_contains_point(point, &rect, &radii),
274 HitTestRegion::RoundedRectangle(rect, radii, ClipMode::ClipOut) =>
275 !rounded_rectangle_contains_point(point, &rect, &radii),
276 HitTestRegion::Polygon(rect, polygon) =>
277 polygon_contains_point(point, &rect, &polygon),
278 HitTestRegion::Invalid => true,
279 }
280 }
281}
282
283#[derive(MallocSizeOf)]
284pub struct HitTester {
285 #[ignore_malloc_size_of = "Arc"]
286 scene: Arc<HitTestingScene>,
287 spatial_nodes: FastHashMap<SpatialNodeIndex, HitTestSpatialNode>,
288 pipeline_root_nodes: FastHashMap<PipelineId, SpatialNodeIndex>,
289}
290
291impl HitTester {
292 pub fn empty() -> Self {
293 HitTester {
294 scene: Arc::new(HitTestingScene::new(&HitTestingSceneStats::empty())),
295 spatial_nodes: FastHashMap::default(),
296 pipeline_root_nodes: FastHashMap::default(),
297 }
298 }
299
300 pub fn new(
301 scene: Arc<HitTestingScene>,
302 spatial_tree: &SpatialTree,
303 ) -> HitTester {
304 let mut hit_tester = HitTester {
305 scene,
306 spatial_nodes: FastHashMap::default(),
307 pipeline_root_nodes: FastHashMap::default(),
308 };
309 hit_tester.read_spatial_tree(spatial_tree);
310 hit_tester
311 }
312
313 fn read_spatial_tree(
314 &mut self,
315 spatial_tree: &SpatialTree,
316 ) {
317 self.spatial_nodes.clear();
318 self.spatial_nodes.reserve(spatial_tree.spatial_node_count());
319
320 self.pipeline_root_nodes.clear();
321
322 spatial_tree.visit_nodes(|index, node| {
323 self.pipeline_root_nodes.entry(node.pipeline_id).or_insert(index);
326
327 self.spatial_nodes.insert(index, HitTestSpatialNode {
332 pipeline_id: node.pipeline_id,
333 world_content_transform: spatial_tree
334 .get_world_transform(index)
335 .into_fast_transform(),
336 world_viewport_transform: spatial_tree
337 .get_world_viewport_transform(index)
338 .into_fast_transform(),
339 external_scroll_offset: get_external_scroll_offset(spatial_tree, index),
340 });
341 });
342 }
343
344 pub fn hit_test(&self, test: HitTest) -> HitTestResult {
345 let point = test.get_absolute_point(self);
346
347 let mut result = HitTestResult::default();
348
349 let mut current_spatial_node_index = SpatialNodeIndex::INVALID;
350 let mut point_in_layer = None;
351 let mut current_root_spatial_node_index = SpatialNodeIndex::INVALID;
352 let mut point_in_viewport = None;
353
354 for item in self.scene.items.iter().rev() {
356 let scroll_node = &self.spatial_nodes[&item.spatial_node_index];
357 let pipeline_id = scroll_node.pipeline_id;
358
359 if item.spatial_node_index != current_spatial_node_index {
362 point_in_layer = scroll_node
363 .world_content_transform
364 .inverse()
365 .and_then(|inverted| inverted.project_point2d(point));
366 current_spatial_node_index = item.spatial_node_index;
367 }
368
369 let point_in_layer = match point_in_layer {
371 Some(p) => p,
372 None => continue,
373 };
374
375 if !item.rect.contains(point_in_layer) {
378 continue;
379 }
380
381 let mut current_clip_node_id = item.clip_node_id;
383 let mut is_valid = true;
384
385 while current_clip_node_id != ClipNodeId::NONE {
386 let clip_node = &self.scene.clip_nodes[¤t_clip_node_id];
387
388 let transform = self
389 .spatial_nodes[&clip_node.spatial_node_index]
390 .world_content_transform;
391 if let Some(transformed_point) = transform
392 .inverse()
393 .and_then(|inverted| inverted.project_point2d(point))
394 {
395 if !clip_node.region.contains(&transformed_point) {
396 is_valid = false;
397 break;
398 }
399 }
400
401 current_clip_node_id = clip_node.parent;
402 }
403
404 if !is_valid {
405 continue;
406 }
407
408 if !item.is_backface_visible && scroll_node.world_content_transform.is_backface_visible() {
410 continue;
411 }
412
413 let root_spatial_node_index = self.pipeline_root_nodes[&pipeline_id];
418 if root_spatial_node_index != current_root_spatial_node_index {
419 let root_node = &self.spatial_nodes[&root_spatial_node_index];
420 point_in_viewport = root_node
421 .world_viewport_transform
422 .inverse()
423 .and_then(|inverted| inverted.transform_point2d(test.point))
424 .map(|pt| pt - scroll_node.external_scroll_offset);
425
426 current_root_spatial_node_index = root_spatial_node_index;
427 }
428
429 if let Some(point_in_viewport) = point_in_viewport {
430 result.items.push(HitTestResultItem {
431 pipeline: pipeline_id,
432 tag: item.tag,
433 animation_id: item.animation_id,
434 point_in_viewport,
435 point_relative_to_item: point_in_layer - item.rect.min.to_vector(),
436 });
437 }
438
439 if !test.flags.contains(HitTestFlags::FIND_ALL) {
440 return result;
441 }
442 }
443
444 result.items.dedup();
445 result
446 }
447
448 fn get_pipeline_root(&self, pipeline_id: PipelineId) -> Option<&HitTestSpatialNode> {
449 let root_node = &self.pipeline_root_nodes.get(&pipeline_id)?;
450 self.spatial_nodes.get(root_node)
451 }
452
453}
454
455#[derive(MallocSizeOf)]
456pub struct HitTest {
457 pipeline_id: Option<PipelineId>,
458 point: WorldPoint,
459 #[ignore_malloc_size_of = "bitflags"]
460 flags: HitTestFlags,
461}
462
463impl HitTest {
464 pub fn new(
465 pipeline_id: Option<PipelineId>,
466 point: WorldPoint,
467 flags: HitTestFlags,
468 ) -> HitTest {
469 HitTest {
470 pipeline_id,
471 point,
472 flags
473 }
474 }
475
476 fn get_absolute_point(&self, hit_tester: &HitTester) -> WorldPoint {
477 if !self.flags.contains(HitTestFlags::POINT_RELATIVE_TO_PIPELINE_VIEWPORT) {
478 return self.point;
479 }
480
481 let point = LayoutPoint::new(self.point.x, self.point.y);
482 self.pipeline_id
483 .and_then(|id|
484 hit_tester
485 .get_pipeline_root(id)?
486 .world_viewport_transform
487 .transform_point2d(point)
488 )
489 .unwrap_or_else(|| {
490 WorldPoint::new(self.point.x, self.point.y)
491 })
492 }
493
494}