selectors/
builder.rs

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 as Component
10//!   instances.
11//! * We store the top-level compound selectors from right to left, i.e. in matching order.
12//! * We store the simple selectors for each combinator from left to right, so that we match the
13//!   cheaper simple selectors first.
14//!
15//! For example, the selector:
16//!
17//!   .bar:hover > .baz:nth-child(2) + .qux
18//!
19//! Gets stored as:
20//!
21//!   [.qux,  + , .baz, :nth-child(2),  > , .bar, :hover]
22//!
23//! Meeting all these constraints without extra memmove traffic during parsing is non-trivial. This
24//! module encapsulates those details and presents an easy-to-use API for the parser.
25
26use 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/// Top-level SelectorBuilder struct. This should be stack-allocated by the consumer and never
41/// moved (because it contains a lot of inline data that would be slow to memmove).
42///
43/// After instantiation, callers may call the push_simple_selector() and push_combinator() methods
44/// to append selector data as it is encountered (from left to right). Once the process is
45/// complete, callers should invoke build(), which transforms the contents of the SelectorBuilder
46/// into a heap- allocated Selector and leaves the builder in a drained state.
47#[derive(Debug)]
48pub struct SelectorBuilder<Impl: SelectorImpl> {
49    /// The entire sequence of components. We make this large because the result of parsing a
50    /// selector is fed into a new Arc-ed allocation, so any spilled vec would be a wasted
51    /// allocation. Also, Components are large enough that we don't have much cache locality
52    /// benefit from reserving stack space for fewer of them.
53    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    /// Pushes a simple selector onto the current compound selector.
65    #[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    /// Completes the current compound selector and starts a new one, delimited by the given
72    /// combinator.
73    #[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    /// Returns true if combinators have ever been pushed to this builder.
86    #[inline(always)]
87    pub fn has_combinators(&self) -> bool {
88        self.last_compound_start.is_some()
89    }
90
91    /// Consumes the builder, producing a Selector.
92    #[inline(always)]
93    pub fn build(
94        &mut self,
95        parse_relative: ParseRelative,
96    ) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
97        // Compute the specificity and flags.
98        let sf = specificity_and_flags(
99            self.components.iter(),
100            /* for_nesting_parent = */ false,
101        );
102        self.build_with_specificity_and_flags(sf, parse_relative)
103    }
104
105    /// Builds with an explicit SpecificityAndFlags. This is separated from build() so that unit
106    /// tests can pass an explicit specificity.
107    #[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        // As an optimization, for a selector without combinators, we can just keep the order
137        // as-is.
138        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
166// This is effectively a Chain<>, but Chain isn't an ExactSizeIterator, see
167// https://github.com/rust-lang/rust/issues/34433
168struct 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/// Flags that indicate at which point of parsing a selector are we.
199#[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    /// When you nest a pseudo-element with something like:
226    ///
227    ///   ::before { & { .. } }
228    ///
229    /// It is not supposed to work, because :is(::before) is invalid. We can't propagate the
230    /// pseudo-flags from inner to outer selectors, to avoid breaking our invariants.
231    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    /// There are two free bits here, since we use ten bits for each specificity
240    /// kind (id, class, element).
241    pub(crate) specificity: u32,
242    /// There's padding after this field due to the size of the flags.
243    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    // Return the specficity of a single class-like selector.
257    #[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                    // Note that due to the way ::slotted works we only compete with
335                    // other ::slotted rules, so the above rule doesn't really
336                    // matter, but we do it still for consistency with other
337                    // pseudo-elements.
338                    //
339                    // See: https://github.com/w3c/csswg-drafts/issues/1915
340                    *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                    // See: https://github.com/w3c/csswg-drafts/issues/1915
349                    *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                // https://drafts.csswg.org/selectors/#specificity-rules:
374                //
375                //     The specificity of the :nth-last-child() pseudo-class,
376                //     like the :nth-child() pseudo-class, combines the
377                //     specificity of a regular pseudo-class with that of its
378                //     selector argument S.
379                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            // https://drafts.csswg.org/selectors/#specificity-rules:
388            //
389            //     The specificity of an :is(), :not(), or :has() pseudo-class
390            //     is replaced by the specificity of the most specific complex
391            //     selector in its selector list argument.
392            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                    /* nested = */ 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                // Does not affect specificity
420            },
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
440/// Finds the maximum specificity of elements in the list and returns it.
441pub(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            // In this case we need to re-compute the specificity.
453            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}