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
//! Helper module to build up a selector safely and efficiently.
6
//!
7
//! Our selector representation is designed to optimize matching, and has
8
//! several requirements:
9
//! * All simple selectors and combinators are stored inline in the same buffer
10
//! as Component instances.
11
//! * We store the top-level compound selectors from right to left, i.e. in
12
//! matching order.
13
//! * We store the simple selectors for each combinator from left to right, so
14
//! that we match the cheaper simple selectors first.
15
//!
16
//! Meeting all these constraints without extra memmove traffic during parsing
17
//! is non-trivial. This module encapsulates those details and presents an
18
//! easy-to-use API for the parser.
19
20
use crate::parser::{Combinator, Component, SelectorImpl};
21
use crate::sink::Push;
22
use servo_arc::{Arc, HeaderWithLength, ThinArc};
23
use smallvec::{self, SmallVec};
24
use std::cmp;
25
use std::iter;
26
use std::ptr;
27
use std::slice;
28
29
/// Top-level SelectorBuilder struct. This should be stack-allocated by the
30
/// consumer and never moved (because it contains a lot of inline data that
31
/// would be slow to memmov).
32
///
33
/// After instantation, callers may call the push_simple_selector() and
34
/// push_combinator() methods to append selector data as it is encountered
35
/// (from left to right). Once the process is complete, callers should invoke
36
/// build(), which transforms the contents of the SelectorBuilder into a heap-
37
/// allocated Selector and leaves the builder in a drained state.
38
#[derive(Debug)]
39
pub struct SelectorBuilder<Impl: SelectorImpl> {
40
/// The entire sequence of simple selectors, from left to right, without combinators.
41
///
42
/// We make this large because the result of parsing a selector is fed into a new
43
/// Arc-ed allocation, so any spilled vec would be a wasted allocation. Also,
44
/// Components are large enough that we don't have much cache locality benefit
45
/// from reserving stack space for fewer of them.
46
simple_selectors: SmallVec<[Component<Impl>; 32]>,
47
/// The combinators, and the length of the compound selector to their left.
48
combinators: SmallVec<[(Combinator, usize); 16]>,
49
/// The length of the current compount selector.
50
current_len: usize,
51
}
52
53
impl<Impl: SelectorImpl> Default for SelectorBuilder<Impl> {
54
#[inline(always)]
55
fn default() -> Self {
56
SelectorBuilder {
57
simple_selectors: SmallVec::new(),
58
combinators: SmallVec::new(),
59
current_len: 0,
60
}
61
}
62
}
63
64
impl<Impl: SelectorImpl> Push<Component<Impl>> for SelectorBuilder<Impl> {
65
fn push(&mut self, value: Component<Impl>) {
66
self.push_simple_selector(value);
67
}
68
}
69
70
impl<Impl: SelectorImpl> SelectorBuilder<Impl> {
71
/// Pushes a simple selector onto the current compound selector.
72
#[inline(always)]
73
pub fn push_simple_selector(&mut self, ss: Component<Impl>) {
74
assert!(!ss.is_combinator());
75
self.simple_selectors.push(ss);
76
self.current_len += 1;
77
}
78
79
/// Completes the current compound selector and starts a new one, delimited
80
/// by the given combinator.
81
#[inline(always)]
82
pub fn push_combinator(&mut self, c: Combinator) {
83
self.combinators.push((c, self.current_len));
84
self.current_len = 0;
85
}
86
87
/// Returns true if combinators have ever been pushed to this builder.
88
#[inline(always)]
89
pub fn has_combinators(&self) -> bool {
90
!self.combinators.is_empty()
91
}
92
93
/// Consumes the builder, producing a Selector.
94
#[inline(always)]
95
pub fn build(
96
&mut self,
97
parsed_pseudo: bool,
98
parsed_slotted: bool,
99
parsed_part: bool,
100
) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
101
// Compute the specificity and flags.
102
let specificity = specificity(self.simple_selectors.iter());
103
let mut flags = SelectorFlags::empty();
104
if parsed_pseudo {
105
flags |= SelectorFlags::HAS_PSEUDO;
106
}
107
if parsed_slotted {
108
flags |= SelectorFlags::HAS_SLOTTED;
109
}
110
if parsed_part {
111
flags |= SelectorFlags::HAS_PART;
112
}
113
self.build_with_specificity_and_flags(SpecificityAndFlags {
114
specificity,
115
flags,
116
})
117
}
118
119
/// Builds with an explicit SpecificityAndFlags. This is separated from build() so
120
/// that unit tests can pass an explicit specificity.
121
#[inline(always)]
122
pub fn build_with_specificity_and_flags(
123
&mut self,
124
spec: SpecificityAndFlags,
125
) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
126
// First, compute the total number of Components we'll need to allocate
127
// space for.
128
let full_len = self.simple_selectors.len() + self.combinators.len();
129
130
// Create the header.
131
let header = HeaderWithLength::new(spec, full_len);
132
133
// Create the Arc using an iterator that drains our buffers.
134
135
// Use a raw pointer to be able to call set_len despite "borrowing" the slice.
136
// This is similar to SmallVec::drain, but we use a slice here because
137
// we’re gonna traverse it non-linearly.
138
let raw_simple_selectors: *const [Component<Impl>] = &*self.simple_selectors;
139
unsafe {
140
// Panic-safety: if SelectorBuilderIter is not iterated to the end,
141
// some simple selectors will safely leak.
142
self.simple_selectors.set_len(0)
143
}
144
let (rest, current) = split_from_end(unsafe { &*raw_simple_selectors }, self.current_len);
145
let iter = SelectorBuilderIter {
146
current_simple_selectors: current.iter(),
147
rest_of_simple_selectors: rest,
148
combinators: self.combinators.drain().rev(),
149
};
150
151
Arc::into_thin(Arc::from_header_and_iter(header, iter))
152
}
153
}
154
155
struct SelectorBuilderIter<'a, Impl: SelectorImpl> {
156
current_simple_selectors: slice::Iter<'a, Component<Impl>>,
157
rest_of_simple_selectors: &'a [Component<Impl>],
158
combinators: iter::Rev<smallvec::Drain<'a, (Combinator, usize)>>,
159
}
160
161
impl<'a, Impl: SelectorImpl> ExactSizeIterator for SelectorBuilderIter<'a, Impl> {
162
fn len(&self) -> usize {
163
self.current_simple_selectors.len() +
164
self.rest_of_simple_selectors.len() +
165
self.combinators.len()
166
}
167
}
168
169
impl<'a, Impl: SelectorImpl> Iterator for SelectorBuilderIter<'a, Impl> {
170
type Item = Component<Impl>;
171
#[inline(always)]
172
fn next(&mut self) -> Option<Self::Item> {
173
if let Some(simple_selector_ref) = self.current_simple_selectors.next() {
174
// Move a simple selector out of this slice iterator.
175
// This is safe because we’ve called SmallVec::set_len(0) above,
176
// so SmallVec::drop won’t drop this simple selector.
177
unsafe { Some(ptr::read(simple_selector_ref)) }
178
} else {
179
self.combinators.next().map(|(combinator, len)| {
180
let (rest, current) = split_from_end(self.rest_of_simple_selectors, len);
181
self.rest_of_simple_selectors = rest;
182
self.current_simple_selectors = current.iter();
183
Component::Combinator(combinator)
184
})
185
}
186
}
187
188
fn size_hint(&self) -> (usize, Option<usize>) {
189
(self.len(), Some(self.len()))
190
}
191
}
192
193
fn split_from_end<T>(s: &[T], at: usize) -> (&[T], &[T]) {
194
s.split_at(s.len() - at)
195
}
196
197
bitflags! {
198
/// Flags that indicate at which point of parsing a selector are we.
199
#[derive(Default, ToShmem)]
200
pub (crate) struct SelectorFlags : u8 {
201
const HAS_PSEUDO = 1 << 0;
202
const HAS_SLOTTED = 1 << 1;
203
const HAS_PART = 1 << 2;
204
}
205
}
206
207
#[derive(Clone, Copy, Debug, Eq, PartialEq, ToShmem)]
208
pub struct SpecificityAndFlags {
209
/// There are two free bits here, since we use ten bits for each specificity
210
/// kind (id, class, element).
211
pub (crate) specificity: u32,
212
/// There's padding after this field due to the size of the flags.
213
pub (crate) flags: SelectorFlags,
214
}
215
216
impl SpecificityAndFlags {
217
#[inline]
218
pub fn specificity(&self) -> u32 {
219
self.specificity
220
}
221
222
#[inline]
223
pub fn has_pseudo_element(&self) -> bool {
224
self.flags.intersects(SelectorFlags::HAS_PSEUDO)
225
}
226
227
#[inline]
228
pub fn is_slotted(&self) -> bool {
229
self.flags.intersects(SelectorFlags::HAS_SLOTTED)
230
}
231
232
#[inline]
233
pub fn is_part(&self) -> bool {
234
self.flags.intersects(SelectorFlags::HAS_PART)
235
}
236
}
237
238
const MAX_10BIT: u32 = (1u32 << 10) - 1;
239
240
#[derive(Add, AddAssign, Clone, Copy, Default, Eq, Ord, PartialEq, PartialOrd)]
241
struct Specificity {
242
id_selectors: u32,
243
class_like_selectors: u32,
244
element_selectors: u32,
245
}
246
247
impl From<u32> for Specificity {
248
#[inline]
249
fn from(value: u32) -> Specificity {
250
assert!(value <= MAX_10BIT << 20 | MAX_10BIT << 10 | MAX_10BIT);
251
Specificity {
252
id_selectors: value >> 20,
253
class_like_selectors: (value >> 10) & MAX_10BIT,
254
element_selectors: value & MAX_10BIT,
255
}
256
}
257
}
258
259
impl From<Specificity> for u32 {
260
#[inline]
261
fn from(specificity: Specificity) -> u32 {
262
cmp::min(specificity.id_selectors, MAX_10BIT) << 20 |
263
cmp::min(specificity.class_like_selectors, MAX_10BIT) << 10 |
264
cmp::min(specificity.element_selectors, MAX_10BIT)
265
}
266
}
267
268
fn specificity<Impl>(iter: slice::Iter<Component<Impl>>) -> u32
269
where
270
Impl: SelectorImpl,
271
{
272
complex_selector_specificity(iter).into()
273
}
274
275
fn complex_selector_specificity<Impl>(iter: slice::Iter<Component<Impl>>) -> Specificity
276
where
277
Impl: SelectorImpl,
278
{
279
fn simple_selector_specificity<Impl>(
280
simple_selector: &Component<Impl>,
281
specificity: &mut Specificity,
282
) where
283
Impl: SelectorImpl,
284
{
285
match *simple_selector {
286
Component::Combinator(..) => {
287
unreachable!("Found combinator in simple selectors vector?");
288
},
289
Component::Part(..) | Component::PseudoElement(..) | Component::LocalName(..) => {
290
specificity.element_selectors += 1
291
},
292
Component::Slotted(ref selector) => {
293
specificity.element_selectors += 1;
294
// Note that due to the way ::slotted works we only compete with
295
// other ::slotted rules, so the above rule doesn't really
296
// matter, but we do it still for consistency with other
297
// pseudo-elements.
298
//
300
*specificity += Specificity::from(selector.specificity());
301
},
302
Component::Host(ref selector) => {
303
specificity.class_like_selectors += 1;
304
if let Some(ref selector) = *selector {
306
*specificity += Specificity::from(selector.specificity());
307
}
308
},
309
Component::ID(..) => {
310
specificity.id_selectors += 1;
311
},
312
Component::Class(..) |
313
Component::AttributeInNoNamespace { .. } |
314
Component::AttributeInNoNamespaceExists { .. } |
315
Component::AttributeOther(..) |
316
Component::FirstChild |
317
Component::LastChild |
318
Component::OnlyChild |
319
Component::Root |
320
Component::Empty |
321
Component::Scope |
322
Component::NthChild(..) |
323
Component::NthLastChild(..) |
324
Component::NthOfType(..) |
325
Component::NthLastOfType(..) |
326
Component::FirstOfType |
327
Component::LastOfType |
328
Component::OnlyOfType |
329
Component::NonTSPseudoClass(..) => {
330
specificity.class_like_selectors += 1;
331
},
332
Component::ExplicitUniversalType |
333
Component::ExplicitAnyNamespace |
334
Component::ExplicitNoNamespace |
335
Component::DefaultNamespace(..) |
336
Component::Namespace(..) => {
337
// Does not affect specificity
338
},
339
Component::Negation(ref negated) => {
340
for ss in negated.iter() {
341
simple_selector_specificity(&ss, specificity);
342
}
343
},
344
}
345
}
346
347
let mut specificity = Default::default();
348
for simple_selector in iter {
349
simple_selector_specificity(&simple_selector, &mut specificity);
350
}
351
specificity
352
}