1use crate::parser::{
27 Combinator, Component, ParseRelative, RelativeSelector, Selector, SelectorImpl,
28};
29use crate::sink::Push;
30use bitflags::bitflags;
31use derive_more::{Add, AddAssign};
32use servo_arc::{Arc, ThinArc};
33use smallvec::SmallVec;
34use std::cmp;
35use std::slice;
36
37#[cfg(feature = "to_shmem")]
38use to_shmem_derive::ToShmem;
39
40#[derive(Debug)]
48pub struct SelectorBuilder<Impl: SelectorImpl> {
49 components: SmallVec<[Component<Impl>; 32]>,
54 last_compound_start: Option<usize>,
55}
56
57impl<Impl: SelectorImpl> Push<Component<Impl>> for SelectorBuilder<Impl> {
58 fn push(&mut self, value: Component<Impl>) {
59 self.push_simple_selector(value);
60 }
61}
62
63impl<Impl: SelectorImpl> SelectorBuilder<Impl> {
64 #[inline(always)]
66 pub fn push_simple_selector(&mut self, ss: Component<Impl>) {
67 debug_assert!(!ss.is_combinator());
68 self.components.push(ss);
69 }
70
71 #[inline(always)]
74 pub fn push_combinator(&mut self, c: Combinator) {
75 self.reverse_last_compound();
76 self.components.push(Component::Combinator(c));
77 self.last_compound_start = Some(self.components.len());
78 }
79
80 fn reverse_last_compound(&mut self) {
81 let start = self.last_compound_start.unwrap_or(0);
82 self.components[start..].reverse();
83 }
84
85 #[inline(always)]
87 pub fn has_combinators(&self) -> bool {
88 self.last_compound_start.is_some()
89 }
90
91 #[inline(always)]
93 pub fn build(
94 &mut self,
95 parse_relative: ParseRelative,
96 ) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
97 let sf = specificity_and_flags(
99 self.components.iter(),
100 false,
101 );
102 self.build_with_specificity_and_flags(sf, parse_relative)
103 }
104
105 #[inline(always)]
108 pub(crate) fn build_with_specificity_and_flags(
109 &mut self,
110 mut spec: SpecificityAndFlags,
111 parse_relative: ParseRelative,
112 ) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
113 let implicit_addition = match parse_relative {
114 ParseRelative::ForNesting if !spec.flags.intersects(SelectorFlags::HAS_PARENT) => {
115 Some((Component::ParentSelector, SelectorFlags::HAS_PARENT))
116 },
117 ParseRelative::ForScope
118 if !spec
119 .flags
120 .intersects(SelectorFlags::HAS_SCOPE | SelectorFlags::HAS_PARENT) =>
121 {
122 Some((Component::ImplicitScope, SelectorFlags::HAS_SCOPE))
123 },
124 _ => None,
125 };
126 let implicit_selector_and_combinator;
127 let implicit_selector = if let Some((component, flag)) = implicit_addition {
128 spec.flags.insert(flag);
129 implicit_selector_and_combinator =
130 [Component::Combinator(Combinator::Descendant), component];
131 &implicit_selector_and_combinator[..]
132 } else {
133 &[]
134 };
135
136 if self.last_compound_start.is_none() {
139 return Arc::from_header_and_iter(
140 spec,
141 ExactChain(self.components.drain(..), implicit_selector.iter().cloned()),
142 );
143 }
144
145 self.reverse_last_compound();
146 Arc::from_header_and_iter(
147 spec,
148 ExactChain(
149 self.components.drain(..).rev(),
150 implicit_selector.iter().cloned(),
151 ),
152 )
153 }
154}
155
156impl<Impl: SelectorImpl> Default for SelectorBuilder<Impl> {
157 #[inline(always)]
158 fn default() -> Self {
159 SelectorBuilder {
160 components: SmallVec::new(),
161 last_compound_start: None,
162 }
163 }
164}
165
166struct ExactChain<A, B>(A, B);
169
170impl<A, B, Item> ExactSizeIterator for ExactChain<A, B>
171where
172 A: ExactSizeIterator<Item = Item>,
173 B: ExactSizeIterator<Item = Item>,
174{
175 fn len(&self) -> usize {
176 self.0.len() + self.1.len()
177 }
178}
179
180impl<A, B, Item> Iterator for ExactChain<A, B>
181where
182 A: ExactSizeIterator<Item = Item>,
183 B: ExactSizeIterator<Item = Item>,
184{
185 type Item = Item;
186
187 #[inline(always)]
188 fn next(&mut self) -> Option<Self::Item> {
189 self.0.next().or_else(|| self.1.next())
190 }
191
192 fn size_hint(&self) -> (usize, Option<usize>) {
193 let len = self.len();
194 (len, Some(len))
195 }
196}
197
198#[derive(Clone, Copy, Default, Eq, PartialEq)]
200#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
201pub(crate) struct SelectorFlags(u8);
202
203bitflags! {
204 impl SelectorFlags: u8 {
205 const HAS_PSEUDO = 1 << 0;
206 const HAS_SLOTTED = 1 << 1;
207 const HAS_PART = 1 << 2;
208 const HAS_PARENT = 1 << 3;
209 const HAS_HOST = 1 << 4;
210 const HAS_SCOPE = 1 << 5;
211 }
212}
213
214impl core::fmt::Debug for SelectorFlags {
215 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
216 if self.is_empty() {
217 write!(f, "{:#x}", Self::empty().bits())
218 } else {
219 bitflags::parser::to_writer(self, f)
220 }
221 }
222}
223
224impl SelectorFlags {
225 pub(crate) fn forbidden_for_nesting() -> Self {
232 Self::HAS_PSEUDO | Self::HAS_SLOTTED | Self::HAS_PART
233 }
234}
235
236#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
237#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
238pub struct SpecificityAndFlags {
239 pub(crate) specificity: u32,
242 pub(crate) flags: SelectorFlags,
244}
245
246const MAX_10BIT: u32 = (1u32 << 10) - 1;
247
248#[derive(Add, AddAssign, Clone, Copy, Default, Eq, Ord, PartialEq, PartialOrd)]
249pub(crate) struct Specificity {
250 id_selectors: u32,
251 class_like_selectors: u32,
252 element_selectors: u32,
253}
254
255impl Specificity {
256 #[inline]
258 pub fn single_class_like() -> Self {
259 Specificity {
260 id_selectors: 0,
261 class_like_selectors: 1,
262 element_selectors: 0,
263 }
264 }
265}
266
267impl From<u32> for Specificity {
268 #[inline]
269 fn from(value: u32) -> Specificity {
270 assert!(value <= MAX_10BIT << 20 | MAX_10BIT << 10 | MAX_10BIT);
271 Specificity {
272 id_selectors: value >> 20,
273 class_like_selectors: (value >> 10) & MAX_10BIT,
274 element_selectors: value & MAX_10BIT,
275 }
276 }
277}
278
279impl From<Specificity> for u32 {
280 #[inline]
281 fn from(specificity: Specificity) -> u32 {
282 cmp::min(specificity.id_selectors, MAX_10BIT) << 20
283 | cmp::min(specificity.class_like_selectors, MAX_10BIT) << 10
284 | cmp::min(specificity.element_selectors, MAX_10BIT)
285 }
286}
287
288fn specificity_and_flags<Impl>(
289 iter: slice::Iter<Component<Impl>>,
290 for_nesting_parent: bool,
291) -> SpecificityAndFlags
292where
293 Impl: SelectorImpl,
294{
295 complex_selector_specificity_and_flags(iter, for_nesting_parent).into()
296}
297
298fn complex_selector_specificity_and_flags<Impl>(
299 iter: slice::Iter<Component<Impl>>,
300 for_nesting_parent: bool,
301) -> SpecificityAndFlags
302where
303 Impl: SelectorImpl,
304{
305 fn component_specificity<Impl>(
306 simple_selector: &Component<Impl>,
307 specificity: &mut Specificity,
308 flags: &mut SelectorFlags,
309 for_nesting_parent: bool,
310 ) where
311 Impl: SelectorImpl,
312 {
313 match *simple_selector {
314 Component::Combinator(..) => {},
315 Component::ParentSelector => flags.insert(SelectorFlags::HAS_PARENT),
316 Component::Part(..) => {
317 flags.insert(SelectorFlags::HAS_PART);
318 if !for_nesting_parent {
319 specificity.element_selectors += 1
320 }
321 },
322 Component::PseudoElement(ref pseudo) => {
323 use crate::parser::PseudoElement;
324 flags.insert(SelectorFlags::HAS_PSEUDO);
325 if !for_nesting_parent {
326 specificity.element_selectors += pseudo.specificity_count();
327 }
328 },
329 Component::LocalName(..) => specificity.element_selectors += 1,
330 Component::Slotted(ref selector) => {
331 flags.insert(SelectorFlags::HAS_SLOTTED);
332 if !for_nesting_parent {
333 specificity.element_selectors += 1;
334 *specificity += Specificity::from(selector.specificity());
341 }
342 flags.insert(selector.flags());
343 },
344 Component::Host(ref selector) => {
345 flags.insert(SelectorFlags::HAS_HOST);
346 specificity.class_like_selectors += 1;
347 if let Some(ref selector) = *selector {
348 *specificity += Specificity::from(selector.specificity());
350 flags.insert(selector.flags());
351 }
352 },
353 Component::ID(..) => {
354 specificity.id_selectors += 1;
355 },
356 Component::Class(..)
357 | Component::AttributeInNoNamespace { .. }
358 | Component::AttributeInNoNamespaceExists { .. }
359 | Component::AttributeOther(..)
360 | Component::Root
361 | Component::Empty
362 | Component::Nth(..)
363 | Component::NonTSPseudoClass(..) => {
364 specificity.class_like_selectors += 1;
365 },
366 Component::Scope | Component::ImplicitScope => {
367 flags.insert(SelectorFlags::HAS_SCOPE);
368 if matches!(*simple_selector, Component::Scope) {
369 specificity.class_like_selectors += 1;
370 }
371 },
372 Component::NthOf(ref nth_of_data) => {
373 specificity.class_like_selectors += 1;
380 let sf = selector_list_specificity_and_flags(
381 nth_of_data.selectors().iter(),
382 for_nesting_parent,
383 );
384 *specificity += Specificity::from(sf.specificity);
385 flags.insert(sf.flags);
386 },
387 Component::Where(ref list)
393 | Component::Negation(ref list)
394 | Component::Is(ref list) => {
395 let sf = selector_list_specificity_and_flags(
396 list.slice().iter(),
397 true,
398 );
399 if !matches!(*simple_selector, Component::Where(..)) {
400 *specificity += Specificity::from(sf.specificity);
401 }
402 flags.insert(sf.flags);
403 },
404 Component::Has(ref relative_selectors) => {
405 let sf = relative_selector_list_specificity_and_flags(
406 relative_selectors,
407 for_nesting_parent,
408 );
409 *specificity += Specificity::from(sf.specificity);
410 flags.insert(sf.flags);
411 },
412 Component::ExplicitUniversalType
413 | Component::ExplicitAnyNamespace
414 | Component::ExplicitNoNamespace
415 | Component::DefaultNamespace(..)
416 | Component::Namespace(..)
417 | Component::RelativeSelectorAnchor
418 | Component::Invalid(..) => {
419 },
421 }
422 }
423
424 let mut specificity = Default::default();
425 let mut flags = Default::default();
426 for simple_selector in iter {
427 component_specificity(
428 &simple_selector,
429 &mut specificity,
430 &mut flags,
431 for_nesting_parent,
432 );
433 }
434 SpecificityAndFlags {
435 specificity: specificity.into(),
436 flags,
437 }
438}
439
440pub(crate) fn selector_list_specificity_and_flags<'a, Impl: SelectorImpl>(
442 itr: impl Iterator<Item = &'a Selector<Impl>>,
443 for_nesting_parent: bool,
444) -> SpecificityAndFlags {
445 let mut specificity = 0;
446 let mut flags = SelectorFlags::empty();
447 for selector in itr {
448 let selector_flags = selector.flags();
449 let selector_specificity = if for_nesting_parent
450 && selector_flags.intersects(SelectorFlags::forbidden_for_nesting())
451 {
452 specificity_and_flags(selector.iter_raw_match_order(), for_nesting_parent).specificity
454 } else {
455 selector.specificity()
456 };
457 specificity = std::cmp::max(specificity, selector_specificity);
458 flags.insert(selector.flags());
459 }
460 SpecificityAndFlags { specificity, flags }
461}
462
463pub(crate) fn relative_selector_list_specificity_and_flags<Impl: SelectorImpl>(
464 list: &[RelativeSelector<Impl>],
465 for_nesting_parent: bool,
466) -> SpecificityAndFlags {
467 selector_list_specificity_and_flags(list.iter().map(|rel| &rel.selector), for_nesting_parent)
468}