--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -30,27 +30,68 @@ pub struct TreeStyleInvalidator<'a, 'b:
{
element: E,
data: Option<&'a mut ElementData>,
shared_context: &'a SharedStyleContext<'b>,
}
type InvalidationVector = SmallVec<[Invalidation; 10]>;
+/// The kind of invalidation we're processing.
+///
+/// We can use this to avoid pushing invalidations of the same kind to our
+/// descendants or siblings.
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+enum InvalidationKind {
+ Descendant,
+ Sibling,
+}
+
/// An `Invalidation` is a complex selector that describes which elements,
/// relative to a current element we are processing, must be restyled.
///
/// When `offset` points to the right-most compound selector in `selector`,
/// then the Invalidation `represents` the fact that the current element
/// must be restyled if the compound selector matches. Otherwise, if
/// describes which descendants (or later siblings) must be restyled.
#[derive(Clone)]
struct Invalidation {
selector: Selector<SelectorImpl>,
offset: usize,
+ /// Whether the invalidation was already matched by any previous sibling or
+ /// ancestor.
+ ///
+ /// If this is the case, we can avoid pushing invalidations generated by
+ /// this one if the generated invalidation is effective for all the siblings
+ /// or descendants after us.
+ matched_by_any_previous: bool,
+}
+
+impl Invalidation {
+ /// Whether this invalidation is effective for the next sibling or
+ /// descendant after us.
+ fn effective_for_next(&self) -> bool {
+ // TODO(emilio): For pseudo-elements this should be mostly false, except
+ // for the weird pseudos in <input type="number">.
+ //
+ // We should be able to do better here!
+ match self.selector.combinator_at(self.offset) {
+ Combinator::NextSibling |
+ Combinator::Child => false,
+ _ => true,
+ }
+ }
+
+ fn kind(&self) -> InvalidationKind {
+ if self.selector.combinator_at(self.offset).is_ancestor() {
+ InvalidationKind::Descendant
+ } else {
+ InvalidationKind::Sibling
+ }
+ }
}
impl fmt::Debug for Invalidation {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
use cssparser::ToCss;
f.write_str("Invalidation(")?;
for component in self.selector.iter_raw_parse_order_from(self.offset - 1) {
@@ -62,19 +103,19 @@ impl fmt::Debug for Invalidation {
f.write_str(")")
}
}
/// The result of processing a single invalidation for a given element.
struct InvalidationResult {
/// Whether the element itself was invalidated.
invalidated_self: bool,
- /// Whether the invalidation we've processed is effective for the next
- /// sibling or descendant after us.
- effective_for_next: bool,
+ /// Whether the invalidation matched, either invalidating the element or
+ /// generating another invalidation.
+ matched: bool,
}
impl<'a, 'b: 'a, E> TreeStyleInvalidator<'a, 'b, E>
where E: TElement,
{
/// Trivially constructs a new `TreeStyleInvalidator`.
pub fn new(
element: E,
@@ -455,24 +496,26 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
let mut i = 0;
let mut new_sibling_invalidations = InvalidationVector::new();
let mut invalidated_self = false;
while i < sibling_invalidations.len() {
let result = self.process_invalidation(
&sibling_invalidations[i],
descendant_invalidations,
- &mut new_sibling_invalidations
+ &mut new_sibling_invalidations,
+ InvalidationKind::Sibling,
);
invalidated_self |= result.invalidated_self;
- if !result.effective_for_next {
+ sibling_invalidations[i].matched_by_any_previous |= result.matched;
+ if sibling_invalidations[i].effective_for_next() {
+ i += 1;
+ } else {
sibling_invalidations.remove(i);
- } else {
- i += 1;
}
}
sibling_invalidations.extend(new_sibling_invalidations.drain());
invalidated_self
}
/// Process a given invalidation list coming from our parent,
@@ -488,20 +531,23 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
) -> bool {
let mut invalidated = false;
for invalidation in invalidations {
let result = self.process_invalidation(
invalidation,
descendant_invalidations,
sibling_invalidations,
+ InvalidationKind::Descendant,
);
invalidated |= result.invalidated_self;
- if result.effective_for_next {
+ if invalidation.effective_for_next() {
+ let mut invalidation = invalidation.clone();
+ invalidation.matched_by_any_previous |= result.matched;
descendant_invalidations.push(invalidation.clone());
}
}
invalidated
}
/// Processes a given invalidation, potentially invalidating the style of
@@ -509,20 +555,21 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
///
/// Returns whether invalidated the style of the element, and whether the
/// invalidation should be effective to subsequent siblings or descendants
/// down in the tree.
fn process_invalidation(
&mut self,
invalidation: &Invalidation,
descendant_invalidations: &mut InvalidationVector,
- sibling_invalidations: &mut InvalidationVector
+ sibling_invalidations: &mut InvalidationVector,
+ invalidation_kind: InvalidationKind,
) -> InvalidationResult {
- debug!("TreeStyleInvalidator::process_invalidation({:?}, {:?})",
- self.element, invalidation);
+ debug!("TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})",
+ self.element, invalidation, invalidation_kind);
let mut context =
MatchingContext::new_for_visited(
MatchingMode::Normal,
None,
VisitedHandlingMode::AllLinksVisitedAndUnvisited,
self.shared_context.quirks_mode,
);
@@ -530,24 +577,27 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
let matching_result = matches_compound_selector(
&invalidation.selector,
invalidation.offset,
&mut context,
&self.element
);
let mut invalidated_self = false;
+ let mut matched = false;
match matching_result {
CompoundSelectorMatchingResult::Matched { next_combinator_offset: 0 } => {
debug!(" > Invalidation matched completely");
+ matched = true;
invalidated_self = true;
}
CompoundSelectorMatchingResult::Matched { next_combinator_offset } => {
let next_combinator =
invalidation.selector.combinator_at(next_combinator_offset);
+ matched = true;
if matches!(next_combinator, Combinator::PseudoElement) {
let pseudo_selector =
invalidation.selector
.iter_raw_parse_order_from(next_combinator_offset - 1)
.next()
.unwrap();
let pseudo = match *pseudo_selector {
@@ -573,50 +623,112 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
invalidated_self = true;
}
}
let next_invalidation = Invalidation {
selector: invalidation.selector.clone(),
offset: next_combinator_offset,
+ matched_by_any_previous: false,
};
debug!(" > Invalidation matched, next: {:?}, ({:?})",
next_invalidation, next_combinator);
- if next_combinator.is_ancestor() {
- descendant_invalidations.push(next_invalidation);
+
+ let next_invalidation_kind = next_invalidation.kind();
+
+ // We can skip pushing under some circumstances, and we should
+ // because otherwise the invalidation list could grow
+ // exponentially.
+ //
+ // * First of all, both invalidations need to be of the same
+ // kind. This is because of how we propagate them going to
+ // the right of the tree for sibling invalidations and going
+ // down the tree for children invalidations. A sibling
+ // invalidation that ends up generating a children
+ // invalidation ends up (correctly) in five different lists,
+ // not in the same list five different times.
+ //
+ // * Then, the invalidation needs to be matched by a previous
+ // ancestor/sibling, in order to know that this invalidation
+ // has been generated already.
+ //
+ // * Finally, the new invalidation needs to be
+ // `effective_for_next()`, in order for us to know that it is
+ // still in the list, since we remove the dependencies that
+ // aren't from the lists for our children / siblings.
+ //
+ // To go through an example, let's imagine we are processing a
+ // dom subtree like:
+ //
+ // <div><address><div><div/></div></address></div>
+ //
+ // And an invalidation list with a single invalidation like:
+ //
+ // [div div div]
+ //
+ // When we process the invalidation list for the outer div, we
+ // match it, and generate a `div div` invalidation, so for the
+ // <address> child we have:
+ //
+ // [div div div, div div]
+ //
+ // With the first of them marked as `matched`.
+ //
+ // When we process the <address> child, we don't match any of
+ // them, so both invalidations go untouched to our children.
+ //
+ // When we process the second <div>, we match _both_
+ // invalidations.
+ //
+ // However, when matching the first, we can tell it's been
+ // matched, and not push the corresponding `div div`
+ // invalidation, since we know it's necessarily already on the
+ // list.
+ //
+ // Thus, without skipping the push, we'll arrive to the
+ // innermost <div> with:
+ //
+ // [div div div, div div, div div, div]
+ //
+ // While skipping it, we won't arrive here with duplicating
+ // dependencies:
+ //
+ // [div div div, div div, div]
+ //
+ let can_skip_pushing =
+ next_invalidation_kind == invalidation_kind &&
+ invalidation.matched_by_any_previous &&
+ next_invalidation.effective_for_next();
+
+ if can_skip_pushing {
+ debug!(" > Can avoid push, since the invalidation had \
+ already been matched before");
} else {
- sibling_invalidations.push(next_invalidation);
+ match next_invalidation_kind {
+ InvalidationKind::Descendant => {
+ descendant_invalidations.push(next_invalidation);
+ }
+ InvalidationKind::Sibling => {
+ sibling_invalidations.push(next_invalidation);
+ }
+ }
}
}
CompoundSelectorMatchingResult::NotMatched => {}
}
if invalidated_self {
if let Some(ref mut data) = self.data {
data.restyle.hint.insert(RESTYLE_SELF);
}
}
- // TODO(emilio): For pseudo-elements this should be mostly false, except
- // for the weird pseudos in <input type="number">.
- //
- // We should be able to do better here!
- let effective_for_next =
- match invalidation.selector.combinator_at(invalidation.offset) {
- Combinator::NextSibling |
- Combinator::Child => false,
- _ => true,
- };
-
- InvalidationResult {
- invalidated_self: invalidated_self,
- effective_for_next: effective_for_next,
- }
+ InvalidationResult { invalidated_self, matched, }
}
}
struct InvalidationCollector<'a, 'b: 'a, E>
where E: TElement,
{
element: E,
wrapper: ElementWrapper<'b, E>,
@@ -825,22 +937,24 @@ impl<'a, 'b: 'a, E> InvalidationCollecto
}
if dependency.affects_descendants() {
debug_assert_ne!(dependency.selector_offset, 0);
debug_assert!(!dependency.affects_later_siblings());
self.descendant_invalidations.push(Invalidation {
selector: dependency.selector.clone(),
offset: dependency.selector_offset,
+ matched_by_any_previous: false,
});
} else if dependency.affects_later_siblings() {
debug_assert_ne!(dependency.selector_offset, 0);
self.sibling_invalidations.push(Invalidation {
selector: dependency.selector.clone(),
offset: dependency.selector_offset,
+ matched_by_any_previous: false,
});
}
}
/// Returns whether `dependency` may cause us to invalidate the style of
/// more elements than what we've already invalidated.
fn dependency_may_be_relevant(&self, dependency: &Dependency) -> bool {
if dependency.affects_descendants() || dependency.affects_later_siblings() {