Source code

Revision control

Other Tools

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 http://mozilla.org/MPL/2.0/. */
4
5
use api::{BorderRadius, ClipMode, HitTestFlags, HitTestItem, HitTestResult, ItemTag, PrimitiveFlags};
6
use api::{PipelineId, ApiHitTester};
7
use api::units::*;
8
use crate::clip::{ClipChainId, ClipDataStore, ClipNode, ClipItemKind, ClipStore};
9
use crate::clip::{rounded_rectangle_contains_point};
10
use crate::spatial_tree::{SpatialNodeIndex, SpatialTree};
11
use crate::internal_types::{FastHashMap, LayoutPrimitiveInfo};
12
use std::{ops, u32};
13
use std::sync::{Arc, Mutex};
14
use crate::util::LayoutToWorldFastTransform;
15
16
pub struct SharedHitTester {
17
// We don't really need a mutex here. We could do with some sort of
18
// atomic-atomic-ref-counted pointer (an Arc which would let the pointer
19
// be swapped atomically like an AtomicPtr).
20
// In practive this shouldn't cause performance issues, though.
21
hit_tester: Mutex<Arc<HitTester>>,
22
}
23
24
impl SharedHitTester {
25
pub fn new() -> Self {
26
SharedHitTester {
27
hit_tester: Mutex::new(Arc::new(HitTester::empty())),
28
}
29
}
30
31
pub fn get_ref(&self) -> Arc<HitTester> {
32
let guard = self.hit_tester.lock().unwrap();
33
Arc::clone(&*guard)
34
}
35
36
pub(crate) fn update(&self, new_hit_tester: Arc<HitTester>) {
37
let mut guard = self.hit_tester.lock().unwrap();
38
*guard = new_hit_tester;
39
}
40
}
41
42
impl ApiHitTester for SharedHitTester {
43
fn hit_test(&self,
44
pipeline_id: Option<PipelineId>,
45
point: WorldPoint,
46
flags: HitTestFlags
47
) -> HitTestResult {
48
self.get_ref().hit_test(HitTest::new(pipeline_id, point, flags))
49
}
50
}
51
52
/// A copy of important spatial node data to use during hit testing. This a copy of
53
/// data from the SpatialTree that will persist as a new frame is under construction,
54
/// allowing hit tests consistent with the currently rendered frame.
55
#[derive(MallocSizeOf)]
56
pub struct HitTestSpatialNode {
57
/// The pipeline id of this node.
58
pipeline_id: PipelineId,
59
60
/// World transform for content transformed by this node.
61
world_content_transform: LayoutToWorldFastTransform,
62
63
/// World viewport transform for content transformed by this node.
64
world_viewport_transform: LayoutToWorldFastTransform,
65
66
/// The accumulated external scroll offset for this spatial node.
67
external_scroll_offset: LayoutVector2D,
68
}
69
70
#[derive(MallocSizeOf)]
71
pub struct HitTestClipNode {
72
/// A particular point must be inside all of these regions to be considered clipped in
73
/// for the purposes of a hit test.
74
region: HitTestRegion,
75
}
76
77
impl HitTestClipNode {
78
fn new(node: &ClipNode) -> Self {
79
let region = match node.item.kind {
80
ClipItemKind::Rectangle { rect, mode } => {
81
HitTestRegion::Rectangle(rect, mode)
82
}
83
ClipItemKind::RoundedRectangle { rect, radius, mode } => {
84
HitTestRegion::RoundedRectangle(rect, radius, mode)
85
}
86
ClipItemKind::Image { rect, .. } => {
87
HitTestRegion::Rectangle(rect, ClipMode::Clip)
88
}
89
ClipItemKind::BoxShadow { .. } => HitTestRegion::Invalid,
90
};
91
92
HitTestClipNode {
93
region,
94
}
95
}
96
}
97
98
#[derive(Debug, Copy, Clone, MallocSizeOf, PartialEq, Eq, Hash)]
99
pub struct HitTestClipChainId(u32);
100
101
impl HitTestClipChainId {
102
pub const NONE: Self = HitTestClipChainId(u32::MAX);
103
}
104
105
/// A hit testing clip chain node is the same as a
106
/// normal clip chain node, except that the clip
107
/// node is embedded inside the clip chain, rather
108
/// than referenced. This means we don't need to
109
/// copy the complete interned clip data store for
110
/// hit testing.
111
#[derive(MallocSizeOf)]
112
pub struct HitTestClipChainNode {
113
pub region: HitTestClipNode,
114
pub spatial_node_index: SpatialNodeIndex,
115
pub parent_clip_chain_id: HitTestClipChainId,
116
}
117
118
#[derive(Copy, Clone, Debug, MallocSizeOf)]
119
pub struct HitTestingClipChainIndex(u32);
120
121
#[derive(Clone, MallocSizeOf)]
122
pub struct HitTestingItem {
123
rect: LayoutRect,
124
clip_rect: LayoutRect,
125
tag: ItemTag,
126
is_backface_visible: bool,
127
#[ignore_malloc_size_of = "simple"]
128
clip_chain_range: ops::Range<HitTestingClipChainIndex>,
129
spatial_node_index: SpatialNodeIndex,
130
}
131
132
impl HitTestingItem {
133
pub fn new(
134
tag: ItemTag,
135
info: &LayoutPrimitiveInfo,
136
spatial_node_index: SpatialNodeIndex,
137
clip_chain_range: ops::Range<HitTestingClipChainIndex>,
138
) -> HitTestingItem {
139
HitTestingItem {
140
rect: info.rect,
141
clip_rect: info.clip_rect,
142
tag,
143
is_backface_visible: info.flags.contains(PrimitiveFlags::IS_BACKFACE_VISIBLE),
144
spatial_node_index,
145
clip_chain_range,
146
}
147
}
148
}
149
150
/// Statistics about allocation sizes of current hit tester,
151
/// used to pre-allocate size of the next hit tester.
152
pub struct HitTestingSceneStats {
153
pub clip_chain_roots_count: usize,
154
pub items_count: usize,
155
}
156
157
impl HitTestingSceneStats {
158
pub fn empty() -> Self {
159
HitTestingSceneStats {
160
clip_chain_roots_count: 0,
161
items_count: 0,
162
}
163
}
164
}
165
166
/// Defines the immutable part of a hit tester for a given scene.
167
/// The hit tester is recreated each time a frame is built, since
168
/// it relies on the current values of the spatial tree.
169
/// However, the clip chain and item definitions don't change,
170
/// so they are created once per scene, and shared between
171
/// hit tester instances via Arc.
172
#[derive(MallocSizeOf)]
173
pub struct HitTestingScene {
174
/// The list of variable clip chain roots referenced by the items.
175
pub clip_chain_roots: Vec<HitTestClipChainId>,
176
177
/// List of hit testing primitives.
178
pub items: Vec<HitTestingItem>,
179
}
180
181
impl HitTestingScene {
182
/// Construct a new hit testing scene, pre-allocating to size
183
/// provided by previous scene stats.
184
pub fn new(stats: &HitTestingSceneStats) -> Self {
185
HitTestingScene {
186
clip_chain_roots: Vec::with_capacity(stats.clip_chain_roots_count),
187
items: Vec::with_capacity(stats.items_count),
188
}
189
}
190
191
/// Get stats about the current scene allocation sizes.
192
pub fn get_stats(&self) -> HitTestingSceneStats {
193
HitTestingSceneStats {
194
clip_chain_roots_count: self.clip_chain_roots.len(),
195
items_count: self.items.len(),
196
}
197
}
198
199
/// Add a hit testing primitive.
200
pub fn add_item(&mut self, item: HitTestingItem) {
201
self.items.push(item);
202
}
203
204
/// Add a clip chain to the clip chain roots list.
205
pub fn add_clip_chain(&mut self, clip_chain_id: ClipChainId) {
206
if clip_chain_id != ClipChainId::INVALID {
207
self.clip_chain_roots.push(HitTestClipChainId(clip_chain_id.0));
208
}
209
}
210
211
/// Get the slice of clip chain roots for a given hit test primitive.
212
fn get_clip_chains_for_item(&self, item: &HitTestingItem) -> &[HitTestClipChainId] {
213
&self.clip_chain_roots[item.clip_chain_range.start.0 as usize .. item.clip_chain_range.end.0 as usize]
214
}
215
216
/// Get the next index of the clip chain roots list.
217
pub fn next_clip_chain_index(&self) -> HitTestingClipChainIndex {
218
HitTestingClipChainIndex(self.clip_chain_roots.len() as u32)
219
}
220
}
221
222
#[derive(MallocSizeOf)]
223
enum HitTestRegion {
224
Invalid,
225
Rectangle(LayoutRect, ClipMode),
226
RoundedRectangle(LayoutRect, BorderRadius, ClipMode),
227
}
228
229
impl HitTestRegion {
230
pub fn contains(&self, point: &LayoutPoint) -> bool {
231
match *self {
232
HitTestRegion::Rectangle(ref rectangle, ClipMode::Clip) =>
233
rectangle.contains(*point),
234
HitTestRegion::Rectangle(ref rectangle, ClipMode::ClipOut) =>
235
!rectangle.contains(*point),
236
HitTestRegion::RoundedRectangle(rect, radii, ClipMode::Clip) =>
237
rounded_rectangle_contains_point(point, &rect, &radii),
238
HitTestRegion::RoundedRectangle(rect, radii, ClipMode::ClipOut) =>
239
!rounded_rectangle_contains_point(point, &rect, &radii),
240
HitTestRegion::Invalid => true,
241
}
242
}
243
}
244
245
#[derive(MallocSizeOf)]
246
pub struct HitTester {
247
#[ignore_malloc_size_of = "Arc"]
248
scene: Arc<HitTestingScene>,
249
spatial_nodes: Vec<HitTestSpatialNode>,
250
clip_chains: Vec<HitTestClipChainNode>,
251
pipeline_root_nodes: FastHashMap<PipelineId, SpatialNodeIndex>,
252
}
253
254
impl HitTester {
255
pub fn empty() -> Self {
256
HitTester {
257
scene: Arc::new(HitTestingScene::new(&HitTestingSceneStats::empty())),
258
spatial_nodes: Vec::new(),
259
clip_chains: Vec::new(),
260
pipeline_root_nodes: FastHashMap::default(),
261
}
262
}
263
264
pub fn new(
265
scene: Arc<HitTestingScene>,
266
spatial_tree: &SpatialTree,
267
clip_store: &ClipStore,
268
clip_data_store: &ClipDataStore,
269
) -> HitTester {
270
let mut hit_tester = HitTester {
271
scene,
272
spatial_nodes: Vec::new(),
273
clip_chains: Vec::new(),
274
pipeline_root_nodes: FastHashMap::default(),
275
};
276
hit_tester.read_spatial_tree(
277
spatial_tree,
278
clip_store,
279
clip_data_store,
280
);
281
hit_tester
282
}
283
284
fn read_spatial_tree(
285
&mut self,
286
spatial_tree: &SpatialTree,
287
clip_store: &ClipStore,
288
clip_data_store: &ClipDataStore,
289
) {
290
self.spatial_nodes.clear();
291
self.clip_chains.clear();
292
293
self.spatial_nodes.reserve(spatial_tree.spatial_nodes.len());
294
for (index, node) in spatial_tree.spatial_nodes.iter().enumerate() {
295
let index = SpatialNodeIndex::new(index);
296
297
// If we haven't already seen a node for this pipeline, record this one as the root
298
// node.
299
self.pipeline_root_nodes.entry(node.pipeline_id).or_insert(index);
300
301
//TODO: avoid inverting more than necessary:
302
// - if the coordinate system is non-invertible, no need to try any of these concrete transforms
303
// - if there are other places where inversion is needed, let's not repeat the step
304
305
self.spatial_nodes.push(HitTestSpatialNode {
306
pipeline_id: node.pipeline_id,
307
world_content_transform: spatial_tree
308
.get_world_transform(index)
309
.into_fast_transform(),
310
world_viewport_transform: spatial_tree
311
.get_world_viewport_transform(index)
312
.into_fast_transform(),
313
external_scroll_offset: spatial_tree.external_scroll_offset(index),
314
});
315
}
316
317
// For each clip chain node, extract the clip node from the clip
318
// data store, and store it inline with the clip chain node.
319
self.clip_chains.reserve(clip_store.clip_chain_nodes.len());
320
for node in &clip_store.clip_chain_nodes {
321
let clip_node = &clip_data_store[node.handle];
322
self.clip_chains.push(HitTestClipChainNode {
323
region: HitTestClipNode::new(clip_node),
324
spatial_node_index: clip_node.item.spatial_node_index,
325
parent_clip_chain_id: HitTestClipChainId(node.parent_clip_chain_id.0),
326
});
327
}
328
}
329
330
fn is_point_clipped_in_for_clip_chain(
331
&self,
332
point: WorldPoint,
333
clip_chain_id: HitTestClipChainId,
334
test: &mut HitTest
335
) -> bool {
336
if clip_chain_id == HitTestClipChainId::NONE {
337
return true;
338
}
339
340
if let Some(result) = test.get_from_clip_chain_cache(clip_chain_id) {
341
return result == ClippedIn::ClippedIn;
342
}
343
344
let descriptor = &self.clip_chains[clip_chain_id.0 as usize];
345
let parent_clipped_in = self.is_point_clipped_in_for_clip_chain(
346
point,
347
descriptor.parent_clip_chain_id,
348
test,
349
);
350
351
if !parent_clipped_in {
352
test.set_in_clip_chain_cache(clip_chain_id, ClippedIn::NotClippedIn);
353
return false;
354
}
355
356
if !self.is_point_clipped_in_for_clip_node(
357
point,
358
clip_chain_id,
359
descriptor.spatial_node_index,
360
test,
361
) {
362
test.set_in_clip_chain_cache(clip_chain_id, ClippedIn::NotClippedIn);
363
return false;
364
}
365
366
test.set_in_clip_chain_cache(clip_chain_id, ClippedIn::ClippedIn);
367
true
368
}
369
370
fn is_point_clipped_in_for_clip_node(
371
&self,
372
point: WorldPoint,
373
clip_chain_node_id: HitTestClipChainId,
374
spatial_node_index: SpatialNodeIndex,
375
test: &mut HitTest
376
) -> bool {
377
if let Some(clipped_in) = test.node_cache.get(&clip_chain_node_id) {
378
return *clipped_in == ClippedIn::ClippedIn;
379
}
380
381
let node = &self.clip_chains[clip_chain_node_id.0 as usize].region;
382
let transform = self
383
.spatial_nodes[spatial_node_index.0 as usize]
384
.world_content_transform;
385
let transformed_point = match transform
386
.inverse()
387
.and_then(|inverted| inverted.transform_point2d(point))
388
{
389
Some(point) => point,
390
None => {
391
test.node_cache.insert(clip_chain_node_id, ClippedIn::NotClippedIn);
392
return false;
393
}
394
};
395
396
if !node.region.contains(&transformed_point) {
397
test.node_cache.insert(clip_chain_node_id, ClippedIn::NotClippedIn);
398
return false;
399
}
400
401
test.node_cache.insert(clip_chain_node_id, ClippedIn::ClippedIn);
402
true
403
}
404
405
pub fn find_node_under_point(&self, mut test: HitTest) -> Option<SpatialNodeIndex> {
406
let point = test.get_absolute_point(self);
407
let mut current_spatial_node_index = SpatialNodeIndex::INVALID;
408
let mut point_in_layer = None;
409
410
// For each hit test primitive
411
for item in self.scene.items.iter().rev() {
412
let scroll_node = &self.spatial_nodes[item.spatial_node_index.0 as usize];
413
414
// Update the cached point in layer space, if the spatial node
415
// changed since last primitive.
416
if item.spatial_node_index != current_spatial_node_index {
417
point_in_layer = scroll_node
418
.world_content_transform
419
.inverse()
420
.and_then(|inverted| inverted.transform_point2d(point));
421
422
current_spatial_node_index = item.spatial_node_index;
423
}
424
425
// Only consider hit tests on transformable layers.
426
if let Some(point_in_layer) = point_in_layer {
427
// If the item's rect or clip rect don't contain this point,
428
// it's not a valid hit.
429
if !item.rect.contains(point_in_layer) {
430
continue;
431
}
432
if !item.clip_rect.contains(point_in_layer) {
433
continue;
434
}
435
436
// See if any of the clip chain roots for this primitive
437
// cull out the item.
438
let clip_chains = self.scene.get_clip_chains_for_item(item);
439
let mut is_valid = true;
440
for clip_chain_id in clip_chains {
441
if !self.is_point_clipped_in_for_clip_chain(point, *clip_chain_id, &mut test) {
442
is_valid = false;
443
break;
444
}
445
}
446
447
// Found a valid hit test result!
448
if is_valid {
449
return Some(item.spatial_node_index);
450
}
451
}
452
}
453
454
None
455
}
456
457
pub fn hit_test(&self, mut test: HitTest) -> HitTestResult {
458
let point = test.get_absolute_point(self);
459
460
let mut result = HitTestResult::default();
461
let mut current_spatial_node_index = SpatialNodeIndex::INVALID;
462
let mut point_in_layer = None;
463
let mut current_root_spatial_node_index = SpatialNodeIndex::INVALID;
464
let mut point_in_viewport = None;
465
466
// For each hit test primitive
467
for item in self.scene.items.iter().rev() {
468
let scroll_node = &self.spatial_nodes[item.spatial_node_index.0 as usize];
469
let pipeline_id = scroll_node.pipeline_id;
470
match (test.pipeline_id, pipeline_id) {
471
(Some(id), node_id) if node_id != id => continue,
472
_ => {},
473
}
474
475
// Update the cached point in layer space, if the spatial node
476
// changed since last primitive.
477
if item.spatial_node_index != current_spatial_node_index {
478
point_in_layer = scroll_node
479
.world_content_transform
480
.inverse()
481
.and_then(|inverted| inverted.transform_point2d(point));
482
current_spatial_node_index = item.spatial_node_index;
483
}
484
485
// Only consider hit tests on transformable layers.
486
if let Some(point_in_layer) = point_in_layer {
487
// If the item's rect or clip rect don't contain this point,
488
// it's not a valid hit.
489
if !item.rect.contains(point_in_layer) {
490
continue;
491
}
492
if !item.clip_rect.contains(point_in_layer) {
493
continue;
494
}
495
496
// See if any of the clip chain roots for this primitive
497
// cull out the item.
498
let clip_chains = self.scene.get_clip_chains_for_item(item);
499
let mut is_valid = true;
500
for clip_chain_id in clip_chains {
501
if !self.is_point_clipped_in_for_clip_chain(point, *clip_chain_id, &mut test) {
502
is_valid = false;
503
break;
504
}
505
}
506
if !is_valid {
507
continue;
508
}
509
510
// Don't hit items with backface-visibility:hidden if they are facing the back.
511
if !item.is_backface_visible && scroll_node.world_content_transform.is_backface_visible() {
512
continue;
513
}
514
515
// We need to calculate the position of the test point relative to the origin of
516
// the pipeline of the hit item. If we cannot get a transformed point, we are
517
// in a situation with an uninvertible transformation so we should just skip this
518
// result.
519
let root_spatial_node_index = self.pipeline_root_nodes[&pipeline_id];
520
if root_spatial_node_index != current_root_spatial_node_index {
521
let root_node = &self.spatial_nodes[root_spatial_node_index.0 as usize];
522
point_in_viewport = root_node
523
.world_viewport_transform
524
.inverse()
525
.and_then(|inverted| inverted.transform_point2d(point))
526
.map(|pt| pt - scroll_node.external_scroll_offset);
527
528
current_root_spatial_node_index = root_spatial_node_index;
529
}
530
531
if let Some(point_in_viewport) = point_in_viewport {
532
result.items.push(HitTestItem {
533
pipeline: pipeline_id,
534
tag: item.tag,
535
point_in_viewport,
536
point_relative_to_item: point_in_layer - item.rect.origin.to_vector(),
537
});
538
539
if !test.flags.contains(HitTestFlags::FIND_ALL) {
540
return result;
541
}
542
}
543
}
544
}
545
546
result.items.dedup();
547
result
548
}
549
550
pub fn get_pipeline_root(&self, pipeline_id: PipelineId) -> &HitTestSpatialNode {
551
&self.spatial_nodes[self.pipeline_root_nodes[&pipeline_id].0 as usize]
552
}
553
}
554
555
#[derive(Clone, Copy, MallocSizeOf, PartialEq)]
556
enum ClippedIn {
557
ClippedIn,
558
NotClippedIn,
559
}
560
561
#[derive(MallocSizeOf)]
562
pub struct HitTest {
563
pipeline_id: Option<PipelineId>,
564
point: WorldPoint,
565
flags: HitTestFlags,
566
node_cache: FastHashMap<HitTestClipChainId, ClippedIn>,
567
clip_chain_cache: Vec<Option<ClippedIn>>,
568
}
569
570
impl HitTest {
571
pub fn new(
572
pipeline_id: Option<PipelineId>,
573
point: WorldPoint,
574
flags: HitTestFlags,
575
) -> HitTest {
576
HitTest {
577
pipeline_id,
578
point,
579
flags,
580
node_cache: FastHashMap::default(),
581
clip_chain_cache: Vec::new(),
582
}
583
}
584
585
fn get_from_clip_chain_cache(&mut self, index: HitTestClipChainId) -> Option<ClippedIn> {
586
let index = index.0 as usize;
587
if index >= self.clip_chain_cache.len() {
588
None
589
} else {
590
self.clip_chain_cache[index]
591
}
592
}
593
594
fn set_in_clip_chain_cache(&mut self, index: HitTestClipChainId, value: ClippedIn) {
595
let index = index.0 as usize;
596
if index >= self.clip_chain_cache.len() {
597
self.clip_chain_cache.resize(index + 1, None);
598
}
599
self.clip_chain_cache[index] = Some(value);
600
}
601
602
fn get_absolute_point(&self, hit_tester: &HitTester) -> WorldPoint {
603
if !self.flags.contains(HitTestFlags::POINT_RELATIVE_TO_PIPELINE_VIEWPORT) {
604
return self.point;
605
}
606
607
let point = LayoutPoint::new(self.point.x, self.point.y);
608
self.pipeline_id
609
.and_then(|id|
610
hit_tester
611
.get_pipeline_root(id)
612
.world_viewport_transform
613
.transform_point2d(point)
614
)
615
.unwrap_or_else(|| {
616
WorldPoint::new(self.point.x, self.point.y)
617
})
618
}
619
}