style/invalidation/element/
relative_selector.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//! Invalidation of element styles relative selectors.
6
7use crate::data::ElementData;
8use crate::dom::{TElement, TNode};
9#[cfg(feature = "gecko")]
10use crate::gecko_bindings::structs::ServoElementSnapshotTable;
11use crate::invalidation::element::element_wrapper::ElementWrapper;
12use crate::invalidation::element::invalidation_map::{
13    AdditionalRelativeSelectorInvalidationMap, Dependency, DependencyInvalidationKind,
14    InvalidationMap, NormalDependencyInvalidationKind, RelativeDependencyInvalidationKind,
15    TSStateForInvalidation,
16};
17use crate::invalidation::element::invalidator::{
18    DescendantInvalidationLists, Invalidation, InvalidationProcessor, InvalidationResult,
19    InvalidationVector, SiblingTraversalMap, TreeStyleInvalidator,
20};
21use crate::invalidation::element::restyle_hints::RestyleHint;
22use crate::invalidation::element::state_and_attributes::{
23    check_dependency, dependency_may_be_relevant, invalidated_descendants, invalidated_self,
24    invalidated_sibling, push_invalidation, should_process_descendants,
25};
26#[cfg(feature = "servo")]
27use crate::selector_parser::SnapshotMap as ServoElementSnapshotTable;
28use crate::stylist::{CascadeData, Stylist};
29use dom::ElementState;
30use rustc_hash::FxHashMap;
31use selectors::matching::{
32    matches_selector, ElementSelectorFlags, IncludeStartingStyle, MatchingContext,
33    MatchingForInvalidation, MatchingMode, NeedsSelectorFlags, QuirksMode, SelectorCaches,
34    VisitedHandlingMode,
35};
36use selectors::parser::SelectorKey;
37use selectors::OpaqueElement;
38use smallvec::SmallVec;
39use std::ops::DerefMut;
40
41/// Kind of DOM mutation this relative selector invalidation is being carried out in.
42#[derive(Clone, Copy)]
43pub enum DomMutationOperation {
44    /// Insertion operation, can cause side effect, but presumed already happened.
45    Insert,
46    /// Append operation, cannot cause side effect.
47    Append,
48    /// Removal operation, can cause side effect, but presumed already happened. Sibling relationships are destroyed.
49    Remove,
50    /// Invalidating for side effect of a DOM operation, for the previous sibling.
51    SideEffectPrevSibling,
52    /// Invalidating for side effect of a DOM operation, for the next sibling.
53    SideEffectNextSibling,
54}
55
56impl DomMutationOperation {
57    fn accept<E: TElement>(&self, d: &Dependency, e: E) -> bool {
58        match self {
59            Self::Insert | Self::Append | Self::Remove => {
60                !e.relative_selector_search_direction().is_empty()
61            },
62            // `:has(+ .a + .b)` with `.anchor + .a + .remove + .b` - `.a` would be present
63            // in the search path.
64            Self::SideEffectPrevSibling => {
65                !e.relative_selector_search_direction().is_empty()
66                    && d.right_combinator_is_next_sibling()
67            },
68            // If an element is being removed and would cause next-sibling match to happen,
69            // e.g. `:has(+ .a)` with `.anchor + .remove + .a`, `.a` isn't yet searched
70            // for relative selector matching.
71            Self::SideEffectNextSibling => d.dependency_is_relative_with_single_next_sibling(),
72        }
73    }
74
75    fn is_side_effect(&self) -> bool {
76        match self {
77            Self::Insert | Self::Append | Self::Remove => false,
78            Self::SideEffectPrevSibling | Self::SideEffectNextSibling => true,
79        }
80    }
81}
82
83/// Context required to try and optimize away relative dependencies.
84struct OptimizationContext<'a, E: TElement> {
85    sibling_traversal_map: &'a SiblingTraversalMap<E>,
86    quirks_mode: QuirksMode,
87    operation: DomMutationOperation,
88}
89
90impl<'a, E: TElement> OptimizationContext<'a, E> {
91    fn can_be_ignored(
92        &self,
93        is_subtree: bool,
94        element: E,
95        host: Option<OpaqueElement>,
96        dependency: &Dependency,
97        leftmost_collapse_offset: usize,
98    ) -> bool {
99        if is_subtree {
100            // Subtree elements don't have unaffected sibling to look at.
101            return false;
102        }
103        debug_assert!(
104            matches!(
105                dependency.invalidation_kind(),
106                DependencyInvalidationKind::Relative(..)
107            ),
108            "Non-relative selector being evaluated for optimization"
109        );
110        // This optimization predecates on the fact that there may be a sibling that can readily
111        // "take over" this element.
112        let sibling = match self.sibling_traversal_map.prev_sibling_for(&element) {
113            None => {
114                if matches!(self.operation, DomMutationOperation::Append) {
115                    return false;
116                }
117                match self.sibling_traversal_map.next_sibling_for(&element) {
118                    Some(s) => s,
119                    None => return false,
120                }
121            },
122            Some(s) => s,
123        };
124        {
125            // Run through the affected compund.
126            let mut iter = dependency.selector.iter_from(dependency.selector_offset);
127            while let Some(c) = iter.next() {
128                if c.has_indexed_selector_in_subject() {
129                    // We do not calculate indices during invalidation as they're wasteful - as a side effect,
130                    // such selectors always return true, breaking this optimization. Note that we only check
131                    // this compound only because the check to skip compares against this element's sibling.
132                    // i.e. Given `:has(:nth-child(2) .foo)`, we'd try to find `.foo`'s sibling, which
133                    // shares `:nth-child` up the selector.
134                    return false;
135                }
136            }
137        }
138        let dependency_is_rightmost = dependency.selector_offset == 0;
139        if !dependency_is_rightmost {
140            let combinator = dependency
141                .selector
142                .combinator_at_match_order(dependency.selector_offset - 1);
143            if combinator.is_ancestor() {
144                // We can safely ignore these, since we're about to traverse the
145                // rest of the affected tree anyway to find the rightmost invalidated element.
146                return true;
147            }
148            if combinator.is_sibling() && matches!(self.operation, DomMutationOperation::Append) {
149                // If we're at the top of the DOM tree being mutated, we can ignore it if the
150                // operation is append - we know we'll cover all the later siblings and their descendants.
151                return true;
152            }
153        }
154
155        // We have a situation like `:has(.item .item + .item + .item)`, where the first element in the sibling
156        // chain position (i.e. The element matched by the second `.item` from the left) mutates. By the time we
157        // get here, we've collapsed the 4 dependencies for each of `.item` position into one at the rightmost
158        // position. Before we look for a standin, we need to find which `.item` this element matches - Doing
159        // that would generate more work than it saves.
160        if dependency_is_rightmost
161            && leftmost_collapse_offset != dependency.selector_offset
162            && self
163                .sibling_traversal_map
164                .next_sibling_for(&element)
165                .is_some()
166        {
167            return false;
168        }
169
170        let mut caches = SelectorCaches::default();
171        let mut matching_context = MatchingContext::new(
172            MatchingMode::Normal,
173            None,
174            &mut caches,
175            self.quirks_mode,
176            NeedsSelectorFlags::No,
177            MatchingForInvalidation::Yes,
178        );
179        matching_context.current_host = host;
180        let sibling_matches = matches_selector(
181            &dependency.selector,
182            dependency.selector_offset,
183            None,
184            &sibling,
185            &mut matching_context,
186        );
187        if sibling_matches {
188            // Remember that at this point, we know that the combinator to the right of this
189            // compound is a sibling combinator. Effectively, we've found a standin for the
190            // element we're mutating.
191            // e.g. Given `:has(... .a ~ .b ...)`, we're the mutating element matching `... .a`,
192            // if we find a sibling that matches the `... .a`, it can stand in for us.
193            debug_assert!(
194                dependency.next.is_some(),
195                "No relative selector outer dependency?"
196            );
197            return dependency.next.as_ref().map_or(false, |deps| {
198                // ... However, if the standin sibling can be the anchor, we can't skip it, since
199                // that sibling should be invlidated to become the anchor.
200                let next = &deps.as_ref().slice()[0];
201                !matches_selector(
202                    &next.selector,
203                    next.selector_offset,
204                    None,
205                    &sibling,
206                    &mut matching_context,
207                )
208            });
209        }
210        // Ok, there's no standin element - but would this element have matched the upstream
211        // selector anyway? If we don't, either the match exists somewhere far from us
212        // (In which case our mutation doesn't really matter), or it doesn't exist at all,
213        // so we can just skip the invalidation.
214        let (combinator, prev_offset) = {
215            let mut iter = dependency.selector.iter_from(dependency.selector_offset);
216            let mut o = dependency.selector_offset;
217            while iter.next().is_some() {
218                o += 1;
219            }
220            let combinator = iter.next_sequence();
221            o += 1;
222            debug_assert!(
223                combinator.is_some(),
224                "Should at least see a relative combinator"
225            );
226            (combinator.unwrap(), o)
227        };
228        if combinator.is_sibling() && prev_offset >= dependency.selector.len() - 1 {
229            // Hit the relative combinator - we don't have enough information to
230            // see if there's going to be a downstream match.
231            return false;
232        }
233        !matches_selector(
234            &dependency.selector,
235            dependency.selector_offset,
236            None,
237            &element,
238            &mut matching_context,
239        )
240    }
241}
242
243/// Overall invalidator for handling relative selector invalidations.
244pub struct RelativeSelectorInvalidator<'a, 'b, E>
245where
246    E: TElement + 'a,
247{
248    /// Element triggering the invalidation.
249    pub element: E,
250    /// Quirks mode of the current invalidation.
251    pub quirks_mode: QuirksMode,
252    /// Snapshot containing changes to invalidate against.
253    /// Can be None if it's a DOM mutation.
254    pub snapshot_table: Option<&'b ServoElementSnapshotTable>,
255    /// Callback to trigger when the subject element is invalidated.
256    pub invalidated: fn(E, &InvalidationResult),
257    /// The traversal map that should be used to process invalidations.
258    pub sibling_traversal_map: SiblingTraversalMap<E>,
259    /// Marker for 'a lifetime.
260    pub _marker: ::std::marker::PhantomData<&'a ()>,
261}
262
263struct RelativeSelectorInvalidation<'a> {
264    host: Option<OpaqueElement>,
265    kind: RelativeDependencyInvalidationKind,
266    dependency: &'a Dependency,
267}
268
269type ElementDependencies<'a> = SmallVec<[(Option<OpaqueElement>, &'a Dependency); 1]>;
270type Dependencies<'a, E> = SmallVec<[(E, ElementDependencies<'a>); 1]>;
271type AlreadyInvalidated<'a, E> = SmallVec<[AlreadyInvalidatedEntry<'a, E>; 2]>;
272
273struct AlreadyInvalidatedEntry<'a, E>
274where
275    E: TElement + 'a,
276{
277    /// Element where the invalidation will begin.
278    element: E,
279    /// The current shadow host.
280    host: Option<OpaqueElement>,
281    /// Dependency chain for this invalidation.
282    dependency: &'a Dependency,
283    /// The offset, of the leftmost dependencies that this
284    /// invalidation collapsed. See the `update()` function
285    /// for more information.
286    leftmost_collapse_offset: usize,
287}
288
289impl<'a, E> AlreadyInvalidatedEntry<'a, E>
290where
291    E: TElement + 'a,
292{
293    fn new(element: E, host: Option<OpaqueElement>, dependency: &'a Dependency) -> Self {
294        Self {
295            element,
296            host,
297            dependency,
298            leftmost_collapse_offset: dependency.selector_offset,
299        }
300    }
301
302    /// Update this invalidation with a new invalidation that may collapse with it.
303    fn update(&mut self, element: E, host: Option<OpaqueElement>, dependency: &'a Dependency) {
304        // This dependency should invalidate the same way - Collapse the invalidation
305        // to a more general case so we don't do duplicate work.
306        // e.g. For `:has(.item .item + .item + .item)`, since the anchor would be located
307        // in the ancestor chain for any invalidation triggered by any `.item` compound,
308        // 4 entries can collapse into one - but keep track of the leftmost offset.
309        if self.dependency.selector_offset > dependency.selector_offset {
310            *self = Self {
311                element,
312                host,
313                dependency,
314                leftmost_collapse_offset: self.leftmost_collapse_offset,
315            };
316        } else if self.leftmost_collapse_offset < dependency.selector_offset {
317            self.leftmost_collapse_offset = dependency.selector_offset;
318        }
319    }
320}
321
322/// Interface for collecting relative selector dependencies.
323pub struct RelativeSelectorDependencyCollector<'a, E>
324where
325    E: TElement,
326{
327    /// Dependencies that need to run through the normal invalidation that may generate
328    /// a relative selector invalidation.
329    dependencies: FxHashMap<E, ElementDependencies<'a>>,
330    /// Dependencies that created an invalidation right away.
331    invalidations: AlreadyInvalidated<'a, E>,
332    /// The top element in the subtree being invalidated.
333    top: E,
334    /// Optional context that will be used to try and skip invalidations
335    /// by running selector matches.
336    optimization_context: Option<OptimizationContext<'a, E>>,
337}
338
339type Invalidations<'a> = SmallVec<[RelativeSelectorInvalidation<'a>; 1]>;
340type InnerInvalidations<'a, E> = SmallVec<[(E, RelativeSelectorInvalidation<'a>); 1]>;
341
342struct ToInvalidate<'a, E: TElement + 'a> {
343    /// Dependencies to run through normal invalidator.
344    dependencies: Dependencies<'a, E>,
345    /// Dependencies already invalidated.
346    invalidations: Invalidations<'a>,
347}
348
349impl<'a, E: TElement + 'a> Default for ToInvalidate<'a, E> {
350    fn default() -> Self {
351        Self {
352            dependencies: Dependencies::default(),
353            invalidations: Invalidations::default(),
354        }
355    }
356}
357
358fn invalidation_can_collapse(
359    a: &Dependency,
360    b: &Dependency,
361    allow_indexed_selectors: bool,
362) -> bool {
363    // We want to detect identical dependencies that occur at different
364    // compounds but has the identical compound in the same selector,
365    // e.g. :has(.item .item).
366
367    // If they trigger different invalidations, they shouldn't be collapsed.
368    if a.relative_invalidation_kind() != b.relative_invalidation_kind() {
369        return false;
370    }
371
372    // Not in the same selector, trivially skipped.
373    if SelectorKey::new(&a.selector) != SelectorKey::new(&b.selector) {
374        return false;
375    }
376
377    // Check that this is in the same nesting.
378    // TODO(dshin): @scope probably brings more subtleties...
379    let mut a_next = a.next.as_ref();
380    let mut b_next = b.next.as_ref();
381    while let (Some(a_deps), Some(b_deps)) = (a_next, b_next) {
382        // This is a bit subtle - but we don't need to do the checks we do at higher levels.
383        // Cases like `:is(.item .foo) :is(.item .foo)` where `.item` invalidates would
384        // point to different dependencies, pointing to the same outer selector, but
385        // differing in selector offset.
386        let a_n = &a_deps.as_ref().slice()[0];
387        let b_n = &b_deps.as_ref().slice()[0];
388        if SelectorKey::new(&a_n.selector) != SelectorKey::new(&b_n.selector) {
389            return false;
390        }
391        a_next = a_n.next.as_ref();
392        b_next = b_n.next.as_ref();
393    }
394    if a_next.is_some() || b_next.is_some() {
395        return false;
396    }
397
398    // Ok, now, do the compounds actually match?
399    // This can get expensive quickly, but we're assuming that:
400    //
401    //   * In most cases, authors don't generally duplicate compounds in a selector, so
402    //     this fails quickly
403    //   * In cases where compounds are duplicated, reducing the number of invalidations
404    //     has a payoff that offsets the comparison cost
405    //
406    // Note, `.a.b` != `.b.a` - doesn't affect correctness, though.
407    // TODO(dshin): Caching this may be worth it as well?
408    let mut a_iter = a.selector.iter_from(a.selector_offset);
409    let mut b_iter = b.selector.iter_from(b.selector_offset);
410    loop {
411        let a_component = a_iter.next();
412        let b_component = b_iter.next();
413
414        if a_component != b_component {
415            return false;
416        }
417        let Some(component) = a_component else {
418            return true;
419        };
420        if !allow_indexed_selectors && component.has_indexed_selector_in_subject() {
421            // The element's positioning matters, so can't collapse.
422            return false;
423        }
424    }
425}
426
427impl<'a, E> RelativeSelectorDependencyCollector<'a, E>
428where
429    E: TElement,
430{
431    fn new(top: E, optimization_context: Option<OptimizationContext<'a, E>>) -> Self {
432        Self {
433            dependencies: FxHashMap::default(),
434            invalidations: AlreadyInvalidated::default(),
435            top,
436            optimization_context,
437        }
438    }
439
440    fn insert_invalidation(
441        &mut self,
442        element: E,
443        dependency: &'a Dependency,
444        host: Option<OpaqueElement>,
445    ) {
446        let in_subtree = element != self.top;
447        if let Some(entry) = self.invalidations.iter_mut().find(|entry| {
448            // If we're in the subtree of DOM manipulation - worrying the about positioning of this element
449            // is irrelevant, because the DOM structure is either completely new or about to go away.
450            let both_in_subtree = in_subtree && entry.element != self.top;
451            // If we're considering the same element for invalidation, their evaluation of the indexed selector
452            // is identical by definition.
453            let same_element = element == entry.element;
454            invalidation_can_collapse(
455                dependency,
456                entry.dependency,
457                both_in_subtree || same_element,
458            )
459        }) {
460            entry.update(element, host, dependency)
461        } else {
462            self.invalidations
463                .push(AlreadyInvalidatedEntry::new(element, host, dependency));
464        }
465    }
466
467    /// Add this dependency, if it is unique (i.e. Different outer dependency or same outer dependency
468    /// but requires a different invalidation traversal).
469    pub fn add_dependency(
470        &mut self,
471        dependency: &'a Dependency,
472        element: E,
473        host: Option<OpaqueElement>,
474    ) {
475        match dependency.invalidation_kind() {
476            DependencyInvalidationKind::FullSelector => unreachable!(),
477            DependencyInvalidationKind::Normal(..) | DependencyInvalidationKind::Scope(..) => {
478                self.dependencies
479                    .entry(element)
480                    .and_modify(|v| v.push((host, dependency)))
481                    .or_default()
482                    .push((host, dependency));
483            },
484            DependencyInvalidationKind::Relative(kind) => {
485                debug_assert!(
486                    dependency.next.is_some(),
487                    "Orphaned inner relative selector?"
488                );
489                if element != self.top
490                    && matches!(
491                        kind,
492                        RelativeDependencyInvalidationKind::Parent
493                            | RelativeDependencyInvalidationKind::PrevSibling
494                            | RelativeDependencyInvalidationKind::EarlierSibling
495                    )
496                {
497                    return;
498                }
499                self.insert_invalidation(element, dependency, host);
500            },
501        };
502    }
503
504    /// Get the dependencies in a list format.
505    fn get(self) -> ToInvalidate<'a, E> {
506        let mut result = ToInvalidate::default();
507        for invalidation in self.invalidations {
508            match invalidation.dependency.invalidation_kind() {
509                DependencyInvalidationKind::FullSelector => unreachable!(),
510                DependencyInvalidationKind::Normal(_) | DependencyInvalidationKind::Scope(_) => {
511                    unreachable!("Inner selector in invalidation?")
512                },
513                DependencyInvalidationKind::Relative(kind) => {
514                    if let Some(context) = self.optimization_context.as_ref() {
515                        if context.can_be_ignored(
516                            invalidation.element != self.top,
517                            invalidation.element,
518                            invalidation.host,
519                            invalidation.dependency,
520                            invalidation.leftmost_collapse_offset,
521                        ) {
522                            continue;
523                        }
524                    }
525                    let dependency = &invalidation.dependency.next.as_ref().unwrap().slice()[0];
526                    result.invalidations.push(RelativeSelectorInvalidation {
527                        kind,
528                        host: invalidation.host,
529                        dependency,
530                    });
531                    // We move the invalidation up to the top of the subtree to avoid unnecessary traveral, but
532                    // this means that we need to take ancestor-earlier sibling invalidations into account, as
533                    // they'd look into earlier siblings of the top of the subtree as well.
534                    if invalidation.element != self.top
535                        && matches!(
536                            kind,
537                            RelativeDependencyInvalidationKind::AncestorEarlierSibling
538                                | RelativeDependencyInvalidationKind::AncestorPrevSibling
539                        )
540                    {
541                        result.invalidations.push(RelativeSelectorInvalidation {
542                            kind: if matches!(
543                                kind,
544                                RelativeDependencyInvalidationKind::AncestorPrevSibling
545                            ) {
546                                RelativeDependencyInvalidationKind::PrevSibling
547                            } else {
548                                RelativeDependencyInvalidationKind::EarlierSibling
549                            },
550                            host: invalidation.host,
551                            dependency,
552                        });
553                    }
554                },
555            };
556        }
557        for (key, element_dependencies) in self.dependencies {
558            // At least for now, we don't try to optimize away dependencies emitted from nested selectors.
559            result.dependencies.push((key, element_dependencies));
560        }
561        result
562    }
563
564    fn collect_all_dependencies_for_element(
565        &mut self,
566        element: E,
567        scope: Option<OpaqueElement>,
568        quirks_mode: QuirksMode,
569        map: &'a InvalidationMap,
570        additional_relative_selector_invalidation_map: &'a AdditionalRelativeSelectorInvalidationMap,
571        operation: DomMutationOperation,
572    ) {
573        element
574            .id()
575            .map(|v| match map.id_to_selector.get(v, quirks_mode) {
576                Some(v) => {
577                    for dependency in v {
578                        if !operation.accept(dependency, element) {
579                            continue;
580                        }
581                        self.add_dependency(dependency, element, scope);
582                    }
583                },
584                None => (),
585            });
586        element.each_class(|v| match map.class_to_selector.get(v, quirks_mode) {
587            Some(v) => {
588                for dependency in v {
589                    if !operation.accept(dependency, element) {
590                        continue;
591                    }
592                    self.add_dependency(dependency, element, scope);
593                }
594            },
595            None => (),
596        });
597        element.each_custom_state(|v| match map.custom_state_affecting_selectors.get(v) {
598            Some(v) => {
599                for dependency in v {
600                    if !operation.accept(dependency, element) {
601                        continue;
602                    }
603                    self.add_dependency(dependency, element, scope);
604                }
605            },
606            None => (),
607        });
608        element.each_attr_name(|v| match map.other_attribute_affecting_selectors.get(v) {
609            Some(v) => {
610                for dependency in v {
611                    if !operation.accept(dependency, element) {
612                        continue;
613                    }
614                    self.add_dependency(dependency, element, scope);
615                }
616            },
617            None => (),
618        });
619        let state = element.state();
620        map.state_affecting_selectors.lookup_with_additional(
621            element,
622            quirks_mode,
623            None,
624            &[],
625            ElementState::empty(),
626            |dependency| {
627                if !dependency.state.intersects(state) {
628                    return true;
629                }
630                if !operation.accept(&dependency.dep, element) {
631                    return true;
632                }
633                self.add_dependency(&dependency.dep, element, scope);
634                true
635            },
636        );
637
638        additional_relative_selector_invalidation_map
639            .ts_state_to_selector
640            .lookup_with_additional(
641                element,
642                quirks_mode,
643                None,
644                &[],
645                ElementState::empty(),
646                |dependency| {
647                    if !operation.accept(&dependency.dep, element) {
648                        return true;
649                    }
650                    // This section contain potential optimization for not running full invalidation -
651                    // consult documentation in `TSStateForInvalidation`.
652                    if dependency.state.may_be_optimized() {
653                        if operation.is_side_effect() {
654                            // Side effect operations act on element not being mutated, so they can't
655                            // change the match outcome of these optimizable pseudoclasses.
656                            return true;
657                        }
658                        debug_assert!(
659                            self.optimization_context.is_some(),
660                            "Optimization context not available for DOM mutation?"
661                        );
662                        if dependency.state.contains(TSStateForInvalidation::EMPTY)
663                            && element.first_element_child().is_some()
664                        {
665                            return true;
666                        }
667
668                        let sibling_traversal_map = self
669                            .optimization_context
670                            .as_ref()
671                            .unwrap()
672                            .sibling_traversal_map;
673                        if dependency
674                            .state
675                            .contains(TSStateForInvalidation::NTH_EDGE_FIRST)
676                            && sibling_traversal_map.prev_sibling_for(&element).is_some()
677                        {
678                            return true;
679                        }
680
681                        if dependency
682                            .state
683                            .contains(TSStateForInvalidation::NTH_EDGE_LAST)
684                            && sibling_traversal_map.next_sibling_for(&element).is_some()
685                        {
686                            return true;
687                        }
688                    }
689                    self.add_dependency(&dependency.dep, element, scope);
690                    true
691                },
692            );
693
694        if let Some(v) = additional_relative_selector_invalidation_map
695            .type_to_selector
696            .get(element.local_name())
697        {
698            for dependency in v {
699                if !operation.accept(dependency, element) {
700                    continue;
701                }
702                self.add_dependency(dependency, element, scope);
703            }
704        }
705
706        for dependency in &additional_relative_selector_invalidation_map.any_to_selector {
707            if !operation.accept(dependency, element) {
708                continue;
709            }
710            self.add_dependency(dependency, element, scope);
711        }
712    }
713
714    fn is_empty(&self) -> bool {
715        self.invalidations.is_empty() && self.dependencies.is_empty()
716    }
717}
718
719impl<'a, 'b, E> RelativeSelectorInvalidator<'a, 'b, E>
720where
721    E: TElement + 'a,
722{
723    /// Gather relative selector dependencies for the given element, and invalidate as necessary.
724    #[inline(never)]
725    pub fn invalidate_relative_selectors_for_this<F>(
726        self,
727        stylist: &'a Stylist,
728        mut gather_dependencies: F,
729    ) where
730        F: FnMut(
731            &E,
732            Option<OpaqueElement>,
733            &'a CascadeData,
734            QuirksMode,
735            &mut RelativeSelectorDependencyCollector<'a, E>,
736        ),
737    {
738        let mut collector = RelativeSelectorDependencyCollector::new(self.element, None);
739        stylist.for_each_cascade_data_with_scope(self.element, |data, scope| {
740            let map = data.relative_invalidation_map_attributes();
741            if !map.used {
742                return;
743            }
744            gather_dependencies(
745                &self.element,
746                scope.map(|e| e.opaque()),
747                data,
748                self.quirks_mode,
749                &mut collector,
750            );
751        });
752        if collector.is_empty() {
753            return;
754        }
755        self.invalidate_from_dependencies(collector.get());
756    }
757
758    /// Gather relative selector dependencies for the given element (And its subtree) that mutated, and invalidate as necessary.
759    #[inline(never)]
760    pub fn invalidate_relative_selectors_for_dom_mutation(
761        self,
762        subtree: bool,
763        stylist: &'a Stylist,
764        inherited_search_path: ElementSelectorFlags,
765        operation: DomMutationOperation,
766    ) {
767        let mut collector = RelativeSelectorDependencyCollector::new(
768            self.element,
769            if operation.is_side_effect() {
770                None
771            } else {
772                Some(OptimizationContext {
773                    sibling_traversal_map: &self.sibling_traversal_map,
774                    quirks_mode: self.quirks_mode,
775                    operation,
776                })
777            },
778        );
779        let mut traverse_subtree = false;
780        self.element.apply_selector_flags(inherited_search_path);
781        stylist.for_each_cascade_data_with_scope(self.element, |data, scope| {
782            let map_attributes = data.relative_invalidation_map_attributes();
783            if !map_attributes.used {
784                return;
785            }
786            let map = data.relative_selector_invalidation_map();
787            traverse_subtree |= map_attributes.needs_ancestors_traversal;
788            collector.collect_all_dependencies_for_element(
789                self.element,
790                scope.map(|e| e.opaque()),
791                self.quirks_mode,
792                map,
793                map_attributes,
794                operation,
795            );
796        });
797
798        if subtree && traverse_subtree {
799            for node in self.element.as_node().dom_descendants() {
800                let descendant = match node.as_element() {
801                    Some(e) => e,
802                    None => continue,
803                };
804                descendant.apply_selector_flags(inherited_search_path);
805                stylist.for_each_cascade_data_with_scope(descendant, |data, scope| {
806                    let map_attributes = data.relative_invalidation_map_attributes();
807                    if !map_attributes.used {
808                        return;
809                    }
810                    let map = data.relative_selector_invalidation_map();
811                    collector.collect_all_dependencies_for_element(
812                        descendant,
813                        scope.map(|e| e.opaque()),
814                        self.quirks_mode,
815                        map,
816                        map_attributes,
817                        operation,
818                    );
819                });
820            }
821        }
822        if collector.is_empty() {
823            return;
824        }
825        self.invalidate_from_dependencies(collector.get());
826    }
827
828    /// Carry out complete invalidation triggered by a relative selector invalidation.
829    fn invalidate_from_dependencies(&self, to_invalidate: ToInvalidate<'a, E>) {
830        for (element, dependencies) in to_invalidate.dependencies {
831            let mut selector_caches = SelectorCaches::default();
832            let mut processor = RelativeSelectorInnerInvalidationProcessor::new(
833                self.quirks_mode,
834                self.snapshot_table,
835                &dependencies,
836                &mut selector_caches,
837                &self.sibling_traversal_map,
838            );
839            TreeStyleInvalidator::new(element, None, &mut processor).invalidate();
840            for (element, invalidation) in processor.take_invalidations() {
841                self.invalidate_upwards(element, &invalidation);
842            }
843        }
844        for invalidation in to_invalidate.invalidations {
845            self.invalidate_upwards(self.element, &invalidation);
846        }
847    }
848
849    fn invalidate_upwards(&self, element: E, invalidation: &RelativeSelectorInvalidation<'a>) {
850        // This contains the main reason for why relative selector invalidation is handled
851        // separately - It travels ancestor and/or earlier sibling direction.
852        match invalidation.kind {
853            RelativeDependencyInvalidationKind::Parent => {
854                element.parent_element().map(|e| {
855                    if !Self::in_search_direction(
856                        &e,
857                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
858                    ) {
859                        return;
860                    }
861                    self.handle_anchor(e, invalidation.dependency, invalidation.host);
862                });
863            },
864            RelativeDependencyInvalidationKind::Ancestors => {
865                let mut parent = element.parent_element();
866                while let Some(par) = parent {
867                    if !Self::in_search_direction(
868                        &par,
869                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
870                    ) {
871                        return;
872                    }
873                    self.handle_anchor(par, invalidation.dependency, invalidation.host);
874                    parent = par.parent_element();
875                }
876            },
877            RelativeDependencyInvalidationKind::PrevSibling => {
878                self.sibling_traversal_map
879                    .prev_sibling_for(&element)
880                    .map(|e| {
881                        if !Self::in_search_direction(
882                            &e,
883                            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
884                        ) {
885                            return;
886                        }
887                        self.handle_anchor(e, invalidation.dependency, invalidation.host);
888                    });
889            },
890            RelativeDependencyInvalidationKind::AncestorPrevSibling => {
891                let mut parent = element.parent_element();
892                while let Some(par) = parent {
893                    if !Self::in_search_direction(
894                        &par,
895                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
896                    ) {
897                        return;
898                    }
899                    par.prev_sibling_element().map(|e| {
900                        if !Self::in_search_direction(
901                            &e,
902                            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
903                        ) {
904                            return;
905                        }
906                        self.handle_anchor(e, invalidation.dependency, invalidation.host);
907                    });
908                    parent = par.parent_element();
909                }
910            },
911            RelativeDependencyInvalidationKind::EarlierSibling => {
912                let mut sibling = self.sibling_traversal_map.prev_sibling_for(&element);
913                while let Some(sib) = sibling {
914                    if !Self::in_search_direction(
915                        &sib,
916                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
917                    ) {
918                        return;
919                    }
920                    self.handle_anchor(sib, invalidation.dependency, invalidation.host);
921                    sibling = sib.prev_sibling_element();
922                }
923            },
924            RelativeDependencyInvalidationKind::AncestorEarlierSibling => {
925                let mut parent = element.parent_element();
926                while let Some(par) = parent {
927                    if !Self::in_search_direction(
928                        &par,
929                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
930                    ) {
931                        return;
932                    }
933                    let mut sibling = par.prev_sibling_element();
934                    while let Some(sib) = sibling {
935                        if !Self::in_search_direction(
936                            &sib,
937                            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
938                        ) {
939                            return;
940                        }
941                        self.handle_anchor(sib, invalidation.dependency, invalidation.host);
942                        sibling = sib.prev_sibling_element();
943                    }
944                    parent = par.parent_element();
945                }
946            },
947        }
948    }
949
950    /// Is this element in the direction of the given relative selector search path?
951    fn in_search_direction(element: &E, desired: ElementSelectorFlags) -> bool {
952        element
953            .relative_selector_search_direction()
954            .intersects(desired)
955    }
956
957    /// Handle a potential relative selector anchor.
958    fn handle_anchor(
959        &self,
960        element: E,
961        outer_dependency: &Dependency,
962        host: Option<OpaqueElement>,
963    ) {
964        let is_rightmost = Self::is_subject(outer_dependency);
965        if (is_rightmost
966            && !element.has_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR))
967            || (!is_rightmost
968                && !element.has_selector_flags(
969                    ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT,
970                ))
971        {
972            // If it was never a relative selector anchor, don't bother.
973            return;
974        }
975        let mut selector_caches = SelectorCaches::default();
976        let matching_context = MatchingContext::<'_, E::Impl>::new_for_visited(
977            MatchingMode::Normal,
978            None,
979            &mut selector_caches,
980            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
981            IncludeStartingStyle::No,
982            self.quirks_mode,
983            NeedsSelectorFlags::No,
984            MatchingForInvalidation::Yes,
985        );
986        let mut data = match element.mutate_data() {
987            Some(data) => data,
988            None => return,
989        };
990        let mut processor = RelativeSelectorOuterInvalidationProcessor {
991            element,
992            host,
993            data: data.deref_mut(),
994            dependency: &*outer_dependency,
995            matching_context,
996            traversal_map: &self.sibling_traversal_map,
997        };
998        let result = TreeStyleInvalidator::new(element, None, &mut processor).invalidate();
999        (self.invalidated)(element, &result);
1000    }
1001
1002    /// Does this relative selector dependency have its relative selector in the subject position?
1003    fn is_subject(outer_dependency: &Dependency) -> bool {
1004        debug_assert!(
1005            matches!(
1006                outer_dependency.invalidation_kind(),
1007                DependencyInvalidationKind::Normal(_) | DependencyInvalidationKind::Scope(_)
1008            ),
1009            "Outer selector of relative selector is relative?"
1010        );
1011
1012        if let Some(x) = outer_dependency.next.as_ref() {
1013            if !Self::is_subject(&x.as_ref().slice()[0]) {
1014                // Not subject in outer selector.
1015                return false;
1016            }
1017        }
1018        outer_dependency
1019            .selector
1020            .is_rightmost(outer_dependency.selector_offset)
1021    }
1022}
1023
1024/// Blindly invalidate everything outside of a relative selector.
1025/// Consider `:is(.a :has(.b) .c ~ .d) ~ .e .f`, where .b gets deleted.
1026/// Since the tree mutated, we cannot rely on snapshots.
1027pub struct RelativeSelectorOuterInvalidationProcessor<'a, 'b, E: TElement> {
1028    /// Element being invalidated.
1029    pub element: E,
1030    /// The current shadow host, if any.
1031    pub host: Option<OpaqueElement>,
1032    /// Data for the element being invalidated.
1033    pub data: &'a mut ElementData,
1034    /// Dependency to be processed.
1035    pub dependency: &'b Dependency,
1036    /// Matching context to use for invalidation.
1037    pub matching_context: MatchingContext<'a, E::Impl>,
1038    /// Traversal map for this invalidation.
1039    pub traversal_map: &'a SiblingTraversalMap<E>,
1040}
1041
1042impl<'a, 'b: 'a, E: 'a> InvalidationProcessor<'b, 'a, E>
1043    for RelativeSelectorOuterInvalidationProcessor<'a, 'b, E>
1044where
1045    E: TElement,
1046{
1047    fn invalidates_on_pseudo_element(&self) -> bool {
1048        true
1049    }
1050
1051    fn check_outer_dependency(
1052        &mut self,
1053        _dependency: &Dependency,
1054        _element: E,
1055        _: Option<OpaqueElement>,
1056    ) -> bool {
1057        // At this point, we know a relative selector invalidated, and are ignoring them.
1058        true
1059    }
1060
1061    fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> {
1062        &mut self.matching_context
1063    }
1064
1065    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
1066        self.traversal_map
1067    }
1068
1069    fn collect_invalidations(
1070        &mut self,
1071        element: E,
1072        _self_invalidations: &mut InvalidationVector<'b>,
1073        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
1074        sibling_invalidations: &mut InvalidationVector<'b>,
1075    ) -> bool {
1076        debug_assert_eq!(element, self.element);
1077        debug_assert!(
1078            self.matching_context.matching_for_invalidation(),
1079            "Not matching for invalidation?"
1080        );
1081
1082        // Ok, this element can potentially an anchor to the given dependency.
1083        // Before we do the potentially-costly ancestor/earlier sibling traversal,
1084        // See if it can actuall be an anchor by trying to match the "rest" of the selector
1085        // outside and to the left of `:has` in question.
1086        // e.g. Element under consideration can only be the anchor to `:has` in
1087        // `.foo .bar ~ .baz:has()`, iff it matches `.foo .bar ~ .baz`.
1088        let invalidated_self = {
1089            let mut d = self.dependency;
1090            loop {
1091                debug_assert!(
1092                    matches!(
1093                        d.invalidation_kind(),
1094                        DependencyInvalidationKind::Normal(_)
1095                            | DependencyInvalidationKind::Scope(_)
1096                    ),
1097                    "Unexpected dependency kind"
1098                );
1099                if !dependency_may_be_relevant(d, &element, false) {
1100                    break false;
1101                }
1102                if !matches_selector(
1103                    &d.selector,
1104                    d.selector_offset,
1105                    None,
1106                    &element,
1107                    self.matching_context(),
1108                ) {
1109                    break false;
1110                }
1111                let invalidation_kind = d.invalidation_kind();
1112                if matches!(
1113                    invalidation_kind,
1114                    DependencyInvalidationKind::Normal(NormalDependencyInvalidationKind::Element)
1115                        | DependencyInvalidationKind::Scope(_)
1116                ) {
1117                    if let Some(ref deps) = d.next {
1118                        d = &deps.as_ref().slice()[0];
1119                        continue;
1120                    }
1121                    break true;
1122                }
1123                debug_assert_ne!(d.selector_offset, 0);
1124                debug_assert_ne!(d.selector_offset, d.selector.len());
1125                let invalidation = Invalidation::new(&d, self.host, None);
1126                break push_invalidation(
1127                    invalidation,
1128                    d.invalidation_kind(),
1129                    descendant_invalidations,
1130                    sibling_invalidations,
1131                );
1132            }
1133        };
1134
1135        if invalidated_self {
1136            self.data.hint.insert(RestyleHint::RESTYLE_SELF);
1137        }
1138        invalidated_self
1139    }
1140
1141    fn should_process_descendants(&mut self, element: E) -> bool {
1142        if element == self.element {
1143            return should_process_descendants(&self.data);
1144        }
1145
1146        match element.borrow_data() {
1147            Some(d) => should_process_descendants(&d),
1148            None => return false,
1149        }
1150    }
1151
1152    fn recursion_limit_exceeded(&mut self, _element: E) {
1153        unreachable!("Unexpected recursion limit");
1154    }
1155
1156    fn invalidated_descendants(&mut self, element: E, child: E) {
1157        invalidated_descendants(element, child)
1158    }
1159
1160    fn invalidated_self(&mut self, element: E) {
1161        debug_assert_ne!(element, self.element);
1162        invalidated_self(element);
1163    }
1164
1165    fn invalidated_sibling(&mut self, element: E, of: E) {
1166        debug_assert_ne!(element, self.element);
1167        invalidated_sibling(element, of);
1168    }
1169}
1170
1171/// Invalidation for the selector(s) inside a relative selector.
1172pub struct RelativeSelectorInnerInvalidationProcessor<'a, 'b, 'c, E>
1173where
1174    E: TElement + 'a,
1175{
1176    /// Matching context to be used.
1177    matching_context: MatchingContext<'b, E::Impl>,
1178    /// Table of snapshots.
1179    snapshot_table: Option<&'c ServoElementSnapshotTable>,
1180    /// Incoming dependencies to be processed.
1181    dependencies: &'c ElementDependencies<'a>,
1182    /// Generated invalidations.
1183    invalidations: InnerInvalidations<'a, E>,
1184    /// Traversal map for this invalidation.
1185    traversal_map: &'b SiblingTraversalMap<E>,
1186}
1187
1188impl<'a, 'b, 'c, E> RelativeSelectorInnerInvalidationProcessor<'a, 'b, 'c, E>
1189where
1190    E: TElement + 'a,
1191{
1192    fn new(
1193        quirks_mode: QuirksMode,
1194        snapshot_table: Option<&'c ServoElementSnapshotTable>,
1195        dependencies: &'c ElementDependencies<'a>,
1196        selector_caches: &'b mut SelectorCaches,
1197        traversal_map: &'b SiblingTraversalMap<E>,
1198    ) -> Self {
1199        let matching_context = MatchingContext::new_for_visited(
1200            MatchingMode::Normal,
1201            None,
1202            selector_caches,
1203            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
1204            IncludeStartingStyle::No,
1205            quirks_mode,
1206            NeedsSelectorFlags::No,
1207            MatchingForInvalidation::Yes,
1208        );
1209        Self {
1210            matching_context,
1211            snapshot_table,
1212            dependencies,
1213            invalidations: InnerInvalidations::default(),
1214            traversal_map,
1215        }
1216    }
1217
1218    fn note_dependency(
1219        &mut self,
1220        element: E,
1221        host: Option<OpaqueElement>,
1222        dependency: &'a Dependency,
1223        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
1224        sibling_invalidations: &mut InvalidationVector<'a>,
1225    ) {
1226        match dependency.invalidation_kind() {
1227            DependencyInvalidationKind::FullSelector => unreachable!(),
1228            DependencyInvalidationKind::Normal(_) | DependencyInvalidationKind::Scope(_) => (),
1229            DependencyInvalidationKind::Relative(kind) => {
1230                self.found_relative_selector_invalidation(element, kind, dependency);
1231                return;
1232            },
1233        }
1234        if matches!(
1235            dependency.normal_invalidation_kind(),
1236            NormalDependencyInvalidationKind::Element
1237        ) {
1238            // Ok, keep heading outwards.
1239            debug_assert!(
1240                dependency.next.is_some(),
1241                "Orphaned inner selector dependency?"
1242            );
1243            if let Some(next) = dependency.next.as_ref() {
1244                self.note_dependency(
1245                    element,
1246                    host,
1247                    &next.as_ref().slice()[0],
1248                    descendant_invalidations,
1249                    sibling_invalidations,
1250                );
1251            }
1252            return;
1253        }
1254        let invalidation = Invalidation::new(&dependency, None, None);
1255        match dependency.normal_invalidation_kind() {
1256            NormalDependencyInvalidationKind::Descendants => {
1257                // Descendant invalidations are simplified due to pseudo-elements not being available within the relative selector.
1258                descendant_invalidations.dom_descendants.push(invalidation)
1259            },
1260            NormalDependencyInvalidationKind::Siblings => sibling_invalidations.push(invalidation),
1261            // Note(dshin, bug 1940212): Nesting can enabling stuffing pseudo-elements into :has, like `::marker { :has(&) }`.
1262            // Ideally, we can just not insert the dependency into the invalidation map, but the necessary selector information
1263            // for this (i.e. `HAS_PSEUDO`) is filtered out in `replace_parent_selector` through
1264            // `SelectorFlags::forbidden_for_nesting`, so just ignoring such dependencies here is the best we can do.
1265            _ => (),
1266        }
1267    }
1268
1269    /// Take the generated invalidations.
1270    fn take_invalidations(self) -> InnerInvalidations<'a, E> {
1271        self.invalidations
1272    }
1273}
1274
1275impl<'a, 'b, 'c, E> InvalidationProcessor<'a, 'b, E>
1276    for RelativeSelectorInnerInvalidationProcessor<'a, 'b, 'c, E>
1277where
1278    E: TElement + 'a,
1279{
1280    fn check_outer_dependency(
1281        &mut self,
1282        dependency: &Dependency,
1283        element: E,
1284        _: Option<OpaqueElement>,
1285    ) -> bool {
1286        if let Some(snapshot_table) = self.snapshot_table {
1287            let wrapper = ElementWrapper::new(element, snapshot_table);
1288            return check_dependency(
1289                dependency,
1290                &element,
1291                &wrapper,
1292                &mut self.matching_context,
1293                None,
1294            );
1295        }
1296        // Just invalidate if we don't have a snapshot.
1297        true
1298    }
1299
1300    fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl> {
1301        return &mut self.matching_context;
1302    }
1303
1304    fn collect_invalidations(
1305        &mut self,
1306        element: E,
1307        _self_invalidations: &mut InvalidationVector<'a>,
1308        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
1309        sibling_invalidations: &mut InvalidationVector<'a>,
1310    ) -> bool {
1311        for (scope, dependency) in self.dependencies {
1312            self.note_dependency(
1313                element,
1314                *scope,
1315                dependency,
1316                descendant_invalidations,
1317                sibling_invalidations,
1318            )
1319        }
1320        false
1321    }
1322
1323    fn should_process_descendants(&mut self, _element: E) -> bool {
1324        true
1325    }
1326
1327    fn recursion_limit_exceeded(&mut self, _element: E) {
1328        unreachable!("Unexpected recursion limit");
1329    }
1330
1331    // Don't do anything for normal invalidations.
1332    fn invalidated_self(&mut self, _element: E) {}
1333    fn invalidated_sibling(&mut self, _sibling: E, _of: E) {}
1334    fn invalidated_descendants(&mut self, _element: E, _child: E) {}
1335
1336    fn found_relative_selector_invalidation(
1337        &mut self,
1338        element: E,
1339        kind: RelativeDependencyInvalidationKind,
1340        dep: &'a Dependency,
1341    ) {
1342        debug_assert!(dep.next.is_some(), "Orphaned inners selector?");
1343        if element.relative_selector_search_direction().is_empty() {
1344            return;
1345        }
1346        self.invalidations.push((
1347            element,
1348            RelativeSelectorInvalidation {
1349                host: self.matching_context.current_host,
1350                kind,
1351                dependency: &dep.next.as_ref().unwrap().as_ref().slice()[0],
1352            },
1353        ));
1354    }
1355
1356    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
1357        &self.traversal_map
1358    }
1359}
style/invalidation/element/relative_selector.rs

style/invalidation/element/
relative_selector.rs
