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 https://mozilla.org/MPL/2.0/. */
4
5
//! Generic implementations of some DOM APIs so they can be shared between Servo
6
//! and Gecko.
7
8
use crate::context::QuirksMode;
9
use crate::dom::{TDocument, TElement, TNode, TShadowRoot};
10
use crate::invalidation::element::invalidator::{DescendantInvalidationLists, Invalidation};
11
use crate::invalidation::element::invalidator::{InvalidationProcessor, InvalidationVector};
12
use crate::Atom;
13
use selectors::attr::CaseSensitivity;
14
use selectors::matching::{self, MatchingContext, MatchingMode};
15
use selectors::parser::{Combinator, Component, LocalName, SelectorImpl};
16
use selectors::{Element, NthIndexCache, SelectorList};
17
use smallvec::SmallVec;
18
use std::borrow::Borrow;
19
21
pub fn element_matches<E>(
22
element: &E,
23
selector_list: &SelectorList<E::Impl>,
24
quirks_mode: QuirksMode,
25
) -> bool
26
where
27
E: Element,
28
{
29
let mut context = MatchingContext::new(MatchingMode::Normal, None, None, quirks_mode);
30
context.scope_element = Some(element.opaque());
31
context.current_host = element.containing_shadow_host().map(|e| e.opaque());
32
matching::matches_selector_list(selector_list, element, &mut context)
33
}
34
36
pub fn element_closest<E>(
37
element: E,
38
selector_list: &SelectorList<E::Impl>,
39
quirks_mode: QuirksMode,
40
) -> Option<E>
41
where
42
E: Element,
43
{
44
let mut nth_index_cache = NthIndexCache::default();
45
46
let mut context = MatchingContext::new(
47
MatchingMode::Normal,
48
None,
49
Some(&mut nth_index_cache),
50
quirks_mode,
51
);
52
context.scope_element = Some(element.opaque());
53
context.current_host = element.containing_shadow_host().map(|e| e.opaque());
54
55
let mut current = Some(element);
56
while let Some(element) = current.take() {
57
if matching::matches_selector_list(selector_list, &element, &mut context) {
58
return Some(element);
59
}
60
current = element.parent_element();
61
}
62
63
return None;
64
}
65
66
/// A selector query abstraction, in order to be generic over QuerySelector and
67
/// QuerySelectorAll.
68
pub trait SelectorQuery<E: TElement> {
69
/// The output of the query.
70
type Output;
71
72
/// Whether the query should stop after the first element has been matched.
73
fn should_stop_after_first_match() -> bool;
74
75
/// Append an element matching after the first query.
76
fn append_element(output: &mut Self::Output, element: E);
77
78
/// Returns true if the output is empty.
79
fn is_empty(output: &Self::Output) -> bool;
80
}
81
82
/// The result of a querySelectorAll call.
83
pub type QuerySelectorAllResult<E> = SmallVec<[E; 128]>;
84
85
/// A query for all the elements in a subtree.
86
pub struct QueryAll;
87
88
impl<E: TElement> SelectorQuery<E> for QueryAll {
89
type Output = QuerySelectorAllResult<E>;
90
91
fn should_stop_after_first_match() -> bool {
92
false
93
}
94
95
fn append_element(output: &mut Self::Output, element: E) {
96
output.push(element);
97
}
98
99
fn is_empty(output: &Self::Output) -> bool {
100
output.is_empty()
101
}
102
}
103
104
/// A query for the first in-tree match of all the elements in a subtree.
105
pub struct QueryFirst;
106
107
impl<E: TElement> SelectorQuery<E> for QueryFirst {
108
type Output = Option<E>;
109
110
fn should_stop_after_first_match() -> bool {
111
true
112
}
113
114
fn append_element(output: &mut Self::Output, element: E) {
115
if output.is_none() {
116
*output = Some(element)
117
}
118
}
119
120
fn is_empty(output: &Self::Output) -> bool {
121
output.is_none()
122
}
123
}
124
125
struct QuerySelectorProcessor<'a, E, Q>
126
where
127
E: TElement + 'a,
128
Q: SelectorQuery<E>,
129
Q::Output: 'a,
130
{
131
results: &'a mut Q::Output,
132
matching_context: MatchingContext<'a, E::Impl>,
133
selector_list: &'a SelectorList<E::Impl>,
134
}
135
136
impl<'a, E, Q> InvalidationProcessor<'a, E> for QuerySelectorProcessor<'a, E, Q>
137
where
138
E: TElement + 'a,
139
Q: SelectorQuery<E>,
140
Q::Output: 'a,
141
{
142
fn light_tree_only(&self) -> bool {
143
true
144
}
145
146
fn collect_invalidations(
147
&mut self,
148
element: E,
149
self_invalidations: &mut InvalidationVector<'a>,
150
descendant_invalidations: &mut DescendantInvalidationLists<'a>,
151
_sibling_invalidations: &mut InvalidationVector<'a>,
152
) -> bool {
153
// TODO(emilio): If the element is not a root element, and
154
// selector_list has any descendant combinator, we need to do extra work
155
// in order to handle properly things like:
156
//
157
// <div id="a">
158
// <div id="b">
159
// <div id="c"></div>
160
// </div>
161
// </div>
162
//
163
// b.querySelector('#a div'); // Should return "c".
164
//
165
// For now, assert it's a root element.
166
debug_assert!(element.parent_element().is_none());
167
168
let target_vector = if self.matching_context.scope_element.is_some() {
169
&mut descendant_invalidations.dom_descendants
170
} else {
171
self_invalidations
172
};
173
174
for selector in self.selector_list.0.iter() {
175
target_vector.push(Invalidation::new(selector, 0))
176
}
177
178
false
179
}
180
181
fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> {
182
&mut self.matching_context
183
}
184
185
fn should_process_descendants(&mut self, _: E) -> bool {
186
if Q::should_stop_after_first_match() {
187
return Q::is_empty(&self.results);
188
}
189
190
true
191
}
192
193
fn invalidated_self(&mut self, e: E) {
194
Q::append_element(self.results, e);
195
}
196
197
fn recursion_limit_exceeded(&mut self, _e: E) {}
198
fn invalidated_descendants(&mut self, _e: E, _child: E) {}
199
}
200
201
fn collect_all_elements<E, Q, F>(root: E::ConcreteNode, results: &mut Q::Output, mut filter: F)
202
where
203
E: TElement,
204
Q: SelectorQuery<E>,
205
F: FnMut(E) -> bool,
206
{
207
for node in root.dom_descendants() {
208
let element = match node.as_element() {
209
Some(e) => e,
210
None => continue,
211
};
212
213
if !filter(element) {
214
continue;
215
}
216
217
Q::append_element(results, element);
218
if Q::should_stop_after_first_match() {
219
return;
220
}
221
}
222
}
223
224
/// Returns whether a given element connected to `root` is descendant of `root`.
225
///
226
/// NOTE(emilio): if root == element, this returns false.
227
fn connected_element_is_descendant_of<E>(element: E, root: E::ConcreteNode) -> bool
228
where
229
E: TElement,
230
{
231
// Optimize for when the root is a document or a shadow root and the element
232
// is connected to that root.
233
if root.as_document().is_some() {
234
debug_assert!(element.as_node().is_in_document(), "Not connected?");
235
debug_assert_eq!(
236
root,
237
root.owner_doc().as_node(),
238
"Where did this element come from?",
239
);
240
return true;
241
}
242
243
if root.as_shadow_root().is_some() {
244
debug_assert_eq!(
245
element.containing_shadow().unwrap().as_node(),
246
root,
247
"Not connected?"
248
);
249
return true;
250
}
251
252
let mut current = element.as_node().parent_node();
253
while let Some(n) = current.take() {
254
if n == root {
255
return true;
256
}
257
258
current = n.parent_node();
259
}
260
false
261
}
262
263
/// Fast path for iterating over every element with a given id in the document
264
/// or shadow root that `root` is connected to.
265
fn fast_connected_elements_with_id<'a, N>(
266
root: N,
267
id: &Atom,
268
quirks_mode: QuirksMode,
269
) -> Result<&'a [N::ConcreteElement], ()>
270
where
271
N: TNode + 'a,
272
{
273
let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
274
if case_sensitivity != CaseSensitivity::CaseSensitive {
275
return Err(());
276
}
277
278
if root.is_in_document() {
279
return root.owner_doc().elements_with_id(id);
280
}
281
282
if let Some(shadow) = root.as_shadow_root() {
283
return shadow.elements_with_id(id);
284
}
285
286
if let Some(shadow) = root.as_element().and_then(|e| e.containing_shadow()) {
287
return shadow.elements_with_id(id);
288
}
289
290
Err(())
291
}
292
293
/// Collects elements with a given id under `root`, that pass `filter`.
294
fn collect_elements_with_id<E, Q, F>(
295
root: E::ConcreteNode,
296
id: &Atom,
297
results: &mut Q::Output,
298
quirks_mode: QuirksMode,
299
mut filter: F,
300
) where
301
E: TElement,
302
Q: SelectorQuery<E>,
303
F: FnMut(E) -> bool,
304
{
305
let elements = match fast_connected_elements_with_id(root, id, quirks_mode) {
306
Ok(elements) => elements,
307
Err(()) => {
308
let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
309
310
collect_all_elements::<E, Q, _>(root, results, |e| {
311
e.has_id(id, case_sensitivity) && filter(e)
312
});
313
314
return;
315
},
316
};
317
318
for element in elements {
319
// If the element is not an actual descendant of the root, even though
320
// it's connected, we don't really care about it.
321
if !connected_element_is_descendant_of(*element, root) {
322
continue;
323
}
324
325
if !filter(*element) {
326
continue;
327
}
328
329
Q::append_element(results, *element);
330
if Q::should_stop_after_first_match() {
331
break;
332
}
333
}
334
}
335
336
#[inline(always)]
337
fn local_name_matches<E>(element: E, local_name: &LocalName<E::Impl>) -> bool
338
where
339
E: TElement,
340
{
341
let LocalName {
342
ref name,
343
ref lower_name,
344
} = *local_name;
345
if element.is_html_element_in_html_document() {
346
element.local_name() == lower_name.borrow()
347
} else {
348
element.local_name() == name.borrow()
349
}
350
}
351
352
/// Fast paths for querySelector with a single simple selector.
353
fn query_selector_single_query<E, Q>(
354
root: E::ConcreteNode,
355
component: &Component<E::Impl>,
356
results: &mut Q::Output,
357
quirks_mode: QuirksMode,
358
) -> Result<(), ()>
359
where
360
E: TElement,
361
Q: SelectorQuery<E>,
362
{
363
match *component {
364
Component::ExplicitUniversalType => {
365
collect_all_elements::<E, Q, _>(root, results, |_| true)
366
},
367
Component::ID(ref id) => {
368
collect_elements_with_id::<E, Q, _>(root, id, results, quirks_mode, |_| true);
369
},
370
Component::Class(ref class) => {
371
let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
372
collect_all_elements::<E, Q, _>(root, results, |element| {
373
element.has_class(class, case_sensitivity)
374
})
375
},
376
Component::LocalName(ref local_name) => {
377
collect_all_elements::<E, Q, _>(root, results, |element| {
378
local_name_matches(element, local_name)
379
})
380
},
381
// TODO(emilio): More fast paths?
382
_ => return Err(()),
383
}
384
385
Ok(())
386
}
387
388
enum SimpleFilter<'a, Impl: SelectorImpl> {
389
Class(&'a Atom),
390
LocalName(&'a LocalName<Impl>),
391
}
392
393
/// Fast paths for a given selector query.
394
///
395
/// When there's only one component, we go directly to
396
/// `query_selector_single_query`, otherwise, we try to optimize by looking just
397
/// at the subtrees rooted at ids in the selector, and otherwise we try to look
398
/// up by class name or local name in the rightmost compound.
399
///
400
/// FIXME(emilio, nbp): This may very well be a good candidate for code to be
401
/// replaced by HolyJit :)
402
fn query_selector_fast<E, Q>(
403
root: E::ConcreteNode,
404
selector_list: &SelectorList<E::Impl>,
405
results: &mut Q::Output,
406
matching_context: &mut MatchingContext<E::Impl>,
407
) -> Result<(), ()>
408
where
409
E: TElement,
410
Q: SelectorQuery<E>,
411
{
412
// We need to return elements in document order, and reordering them
413
// afterwards is kinda silly.
414
if selector_list.0.len() > 1 {
415
return Err(());
416
}
417
418
let selector = &selector_list.0[0];
419
let quirks_mode = matching_context.quirks_mode();
420
421
// Let's just care about the easy cases for now.
422
if selector.len() == 1 {
423
return query_selector_single_query::<E, Q>(
424
root,
425
selector.iter().next().unwrap(),
426
results,
427
quirks_mode,
428
);
429
}
430
431
let mut iter = selector.iter();
432
let mut combinator: Option<Combinator> = None;
433
434
// We want to optimize some cases where there's no id involved whatsoever,
435
// like `.foo .bar`, but we don't want to make `#foo .bar` slower because of
436
// that.
437
let mut simple_filter = None;
438
439
'selector_loop: loop {
440
debug_assert!(combinator.map_or(true, |c| !c.is_sibling()));
441
442
'component_loop: for component in &mut iter {
443
match *component {
444
Component::ID(ref id) => {
445
if combinator.is_none() {
446
// In the rightmost compound, just find descendants of
447
// root that match the selector list with that id.
448
collect_elements_with_id::<E, Q, _>(root, id, results, quirks_mode, |e| {
449
matching::matches_selector_list(selector_list, &e, matching_context)
450
});
451
452
return Ok(());
453
}
454
455
let elements = fast_connected_elements_with_id(root, id, quirks_mode)?;
456
if elements.is_empty() {
457
return Ok(());
458
}
459
460
// Results need to be in document order. Let's not bother
461
// reordering or deduplicating nodes, which we would need to
462
// do if one element with the given id were a descendant of
463
// another element with that given id.
464
if !Q::should_stop_after_first_match() && elements.len() > 1 {
465
continue;
466
}
467
468
for element in elements {
469
// If the element is not a descendant of the root, then
470
// it may have descendants that match our selector that
471
// _are_ descendants of the root, and other descendants
472
// that match our selector that are _not_.
473
//
474
// So we can't just walk over the element's descendants
475
// and match the selector against all of them, nor can
476
// we skip looking at this element's descendants.
477
//
478
// Give up on trying to optimize based on this id and
479
// keep walking our selector.
480
if !connected_element_is_descendant_of(*element, root) {
481
continue 'component_loop;
482
}
483
484
query_selector_slow::<E, Q>(
485
element.as_node(),
486
selector_list,
487
results,
488
matching_context,
489
);
490
491
if Q::should_stop_after_first_match() && !Q::is_empty(&results) {
492
break;
493
}
494
}
495
496
return Ok(());
497
},
498
Component::Class(ref class) => {
499
if combinator.is_none() {
500
simple_filter = Some(SimpleFilter::Class(class));
501
}
502
},
503
Component::LocalName(ref local_name) => {
504
if combinator.is_none() {
505
// Prefer to look at class rather than local-name if
506
// both are present.
507
if let Some(SimpleFilter::Class(..)) = simple_filter {
508
continue;
509
}
510
simple_filter = Some(SimpleFilter::LocalName(local_name));
511
}
512
},
513
_ => {},
514
}
515
}
516
517
loop {
518
let next_combinator = match iter.next_sequence() {
519
None => break 'selector_loop,
520
Some(c) => c,
521
};
522
523
// We don't want to scan stuff affected by sibling combinators,
524
// given we scan the subtree of elements with a given id (and we
525
// don't want to care about scanning the siblings' subtrees).
526
if next_combinator.is_sibling() {
527
// Advance to the next combinator.
528
for _ in &mut iter {}
529
continue;
530
}
531
532
combinator = Some(next_combinator);
533
break;
534
}
535
}
536
537
// We got here without finding any ID or such that we could handle. Try to
538
// use one of the simple filters.
539
let simple_filter = match simple_filter {
540
Some(f) => f,
541
None => return Err(()),
542
};
543
544
match simple_filter {
545
SimpleFilter::Class(ref class) => {
546
let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
547
collect_all_elements::<E, Q, _>(root, results, |element| {
548
element.has_class(class, case_sensitivity) &&
549
matching::matches_selector_list(selector_list, &element, matching_context)
550
});
551
},
552
SimpleFilter::LocalName(ref local_name) => {
553
collect_all_elements::<E, Q, _>(root, results, |element| {
554
local_name_matches(element, local_name) &&
555
matching::matches_selector_list(selector_list, &element, matching_context)
556
});
557
},
558
}
559
560
Ok(())
561
}
562
563
// Slow path for a given selector query.
564
fn query_selector_slow<E, Q>(
565
root: E::ConcreteNode,
566
selector_list: &SelectorList<E::Impl>,
567
results: &mut Q::Output,
568
matching_context: &mut MatchingContext<E::Impl>,
569
) where
570
E: TElement,
571
Q: SelectorQuery<E>,
572
{
573
collect_all_elements::<E, Q, _>(root, results, |element| {
574
matching::matches_selector_list(selector_list, &element, matching_context)
575
});
576
}
577
578
/// Whether the invalidation machinery should be used for this query.
579
#[derive(PartialEq)]
580
pub enum MayUseInvalidation {
581
/// We may use it if we deem it useful.
582
Yes,
583
/// Don't use it.
584
No,
585
}
586
588
pub fn query_selector<E, Q>(
589
root: E::ConcreteNode,
590
selector_list: &SelectorList<E::Impl>,
591
results: &mut Q::Output,
592
may_use_invalidation: MayUseInvalidation,
593
) where
594
E: TElement,
595
Q: SelectorQuery<E>,
596
{
597
use crate::invalidation::element::invalidator::TreeStyleInvalidator;
598
599
let quirks_mode = root.owner_doc().quirks_mode();
600
601
let mut nth_index_cache = NthIndexCache::default();
602
let mut matching_context = MatchingContext::new(
603
MatchingMode::Normal,
604
None,
605
Some(&mut nth_index_cache),
606
quirks_mode,
607
);
608
609
let root_element = root.as_element();
610
matching_context.scope_element = root_element.map(|e| e.opaque());
611
matching_context.current_host = match root_element {
612
Some(root) => root.containing_shadow_host().map(|host| host.opaque()),
613
None => root.as_shadow_root().map(|root| root.host().opaque()),
614
};
615
616
let fast_result =
617
query_selector_fast::<E, Q>(root, selector_list, results, &mut matching_context);
618
619
if fast_result.is_ok() {
620
return;
621
}
622
623
// Slow path: Use the invalidation machinery if we're a root, and tree
624
// traversal otherwise.
625
//
626
// See the comment in collect_invalidations to see why only if we're a root.
627
//
628
// The invalidation mechanism is only useful in presence of combinators.
629
//
630
// We could do that check properly here, though checking the length of the
631
// selectors is a good heuristic.
632
//
633
// A selector with a combinator needs to have a length of at least 3: A
634
// simple selector, a combinator, and another simple selector.
635
let invalidation_may_be_useful = may_use_invalidation == MayUseInvalidation::Yes &&
636
selector_list.0.iter().any(|s| s.len() > 2);
637
638
if root_element.is_some() || !invalidation_may_be_useful {
639
query_selector_slow::<E, Q>(root, selector_list, results, &mut matching_context);
640
} else {
641
let mut processor = QuerySelectorProcessor::<E, Q> {
642
results,
643
matching_context,
644
selector_list,
645
};
646
647
for node in root.dom_children() {
648
if let Some(e) = node.as_element() {
649
TreeStyleInvalidator::new(e, /* stack_limit_checker = */ None, &mut processor)
650
.invalidate();
651
}
652
}
653
}
654
}