src/vendor/selectors/matching.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 http://mozilla.org/MPL/2.0/. */
   4
   5 use attr::{ParsedAttrSelectorOperation, AttrSelectorOperation, NamespaceConstraint};
   6 use bloom::BloomFilter;
   7 use parser::{Combinator, ComplexSelector, Component, LocalName};
   8 use parser::{Selector, SelectorInner, SelectorIter};
   9 use std::borrow::Borrow;
  10 use tree::Element;
  11
  12 // The bloom filter for descendant CSS selectors will have a <1% false
  13 // positive rate until it has this many selectors in it, then it will
  14 // rapidly increase.
  15 pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
  16
  17 bitflags! {
  18     /// Set of flags that determine the different kind of elements affected by
  19     /// the selector matching process.
  20     ///
  21     /// This is used to implement efficient sharing.
  22     #[derive(Default)]
  23     pub flags StyleRelations: usize {
  24         /// Whether this element is affected by an ID selector.
  25         const AFFECTED_BY_ID_SELECTOR = 1 << 0,
  26         /// Whether this element has a style attribute. Computed
  27         /// externally.
  28         const AFFECTED_BY_STYLE_ATTRIBUTE = 1 << 1,
  29         /// Whether this element is affected by presentational hints. This is
  30         /// computed externally (that is, in Servo).
  31         const AFFECTED_BY_PRESENTATIONAL_HINTS = 1 << 2,
  32         /// Whether this element has pseudo-element styles. Computed externally.
  33         const AFFECTED_BY_PSEUDO_ELEMENTS = 1 << 3,
  34     }
  35 }
  36
  37 bitflags! {
  38     /// Set of flags that are set on either the element or its parent (depending
  39     /// on the flag) if the element could potentially match a selector.
  40     pub flags ElementSelectorFlags: usize {
  41         /// When a child is added or removed from the parent, all the children
  42         /// must be restyled, because they may match :nth-last-child,
  43         /// :last-of-type, :nth-last-of-type, or :only-of-type.
  44         const HAS_SLOW_SELECTOR = 1 << 0,
  45
  46         /// When a child is added or removed from the parent, any later
  47         /// children must be restyled, because they may match :nth-child,
  48         /// :first-of-type, or :nth-of-type.
  49         const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1,
  50
  51         /// When a child is added or removed from the parent, the first and
  52         /// last children must be restyled, because they may match :first-child,
  53         /// :last-child, or :only-child.
  54         const HAS_EDGE_CHILD_SELECTOR = 1 << 2,
  55
  56         /// The element has an empty selector, so when a child is appended we
  57         /// might need to restyle the parent completely.
  58         const HAS_EMPTY_SELECTOR = 1 << 3,
  59     }
  60 }
  61
  62 impl ElementSelectorFlags {
  63     /// Returns the subset of flags that apply to the element.
  64     pub fn for_self(self) -> ElementSelectorFlags {
  65         self & (HAS_EMPTY_SELECTOR)
  66     }
  67
  68     /// Returns the subset of flags that apply to the parent.
  69     pub fn for_parent(self) -> ElementSelectorFlags {
  70         self & (HAS_SLOW_SELECTOR | HAS_SLOW_SELECTOR_LATER_SIBLINGS | HAS_EDGE_CHILD_SELECTOR)
  71     }
  72 }
  73
  74 /// What kind of selector matching mode we should use.
  75 ///
  76 /// There are two modes of selector matching. The difference is only noticeable
  77 /// in presence of pseudo-elements.
  78 #[derive(Debug, PartialEq)]
  79 pub enum MatchingMode {
  80     /// Don't ignore any pseudo-element selectors.
  81     Normal,
  82
  83     /// Ignores any stateless pseudo-element selectors in the rightmost sequence
  84     /// of simple selectors.
  85     ///
  86     /// This is useful, for example, to match against ::before when you aren't a
  87     /// pseudo-element yourself.
  88     ///
  89     /// For example, in presence of `::before:hover`, it would never match, but
  90     /// `::before` would be ignored as in "matching".
  91     ///
  92     /// It's required for all the selectors you match using this mode to have a
  93     /// pseudo-element.
  94     ForStatelessPseudoElement,
  95 }
  96
  97
  98 /// Data associated with the matching process for a element.  This context is
  99 /// used across many selectors for an element, so it's not appropriate for
 100 /// transient data that applies to only a single selector.
 101 pub struct MatchingContext<'a> {
 102     /// Output that records certains relations between elements noticed during
 103     /// matching (and also extended after matching).
 104     pub relations: StyleRelations,
 105     /// The matching mode we should use when matching selectors.
 106     pub matching_mode: MatchingMode,
 107     /// The bloom filter used to fast-reject selectors.
 108     pub bloom_filter: Option<&'a BloomFilter>,
 109 }
 110
 111 impl<'a> MatchingContext<'a> {
 112     /// Constructs a new `MatchingContext`.
 113     pub fn new(matching_mode: MatchingMode,
 114                bloom_filter: Option<&'a BloomFilter>)
 115                -> Self
 116     {
 117         Self {
 118             relations: StyleRelations::empty(),
 119             matching_mode: matching_mode,
 120             bloom_filter: bloom_filter,
 121         }
 122     }
 123 }
 124
 125 pub fn matches_selector_list<E>(selector_list: &[Selector<E::Impl>],
 126                                 element: &E,
 127                                 context: &mut MatchingContext)
 128                                 -> bool
 129     where E: Element
 130 {
 131     selector_list.iter().any(|selector| {
 132         matches_selector(&selector.inner,
 133                          element,
 134                          context,
 135                          &mut |_, _| {})
 136     })
 137 }
 138
 139 fn may_match<E>(sel: &SelectorInner<E::Impl>,
 140                 bf: &BloomFilter)
 141                 -> bool
 142     where E: Element,
 143 {
 144     // Check against the list of precomputed hashes.
 145     for hash in sel.ancestor_hashes.iter() {
 146         // If we hit the 0 sentinel hash, that means the rest are zero as well.
 147         if *hash == 0 {
 148             break;
 149         }
 150
 151         if !bf.might_contain_hash(*hash) {
 152             return false;
 153         }
 154     }
 155
 156     true
 157 }
 158
 159 /// A result of selector matching, includes 3 failure types,
 160 ///
 161 ///   NotMatchedAndRestartFromClosestLaterSibling
 162 ///   NotMatchedAndRestartFromClosestDescendant
 163 ///   NotMatchedGlobally
 164 ///
 165 /// When NotMatchedGlobally appears, stop selector matching completely since
 166 /// the succeeding selectors never matches.
 167 /// It is raised when
 168 ///   Child combinator cannot find the candidate element.
 169 ///   Descendant combinator cannot find the candidate element.
 170 ///
 171 /// When NotMatchedAndRestartFromClosestDescendant appears, the selector
 172 /// matching does backtracking and restarts from the closest Descendant
 173 /// combinator.
 174 /// It is raised when
 175 ///   NextSibling combinator cannot find the candidate element.
 176 ///   LaterSibling combinator cannot find the candidate element.
 177 ///   Child combinator doesn't match on the found element.
 178 ///
 179 /// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
 180 /// matching does backtracking and restarts from the closest LaterSibling
 181 /// combinator.
 182 /// It is raised when
 183 ///   NextSibling combinator doesn't match on the found element.
 184 ///
 185 /// For example, when the selector "d1 d2 a" is provided and we cannot *find*
 186 /// an appropriate ancestor element for "d1", this selector matching raises
 187 /// NotMatchedGlobally since even if "d2" is moved to more upper element, the
 188 /// candidates for "d1" becomes less than before and d1 .
 189 ///
 190 /// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
 191 /// provided and we cannot *find* an appropriate brother element for b1,
 192 /// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
 193 /// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
 194 ///
 195 /// The additional example is child and sibling. When the selector
 196 /// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
 197 /// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
 198 /// However since the selector "c1" raises
 199 /// NotMatchedAndRestartFromClosestDescendant. So the selector
 200 /// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
 201 #[derive(PartialEq, Eq, Copy, Clone)]
 202 enum SelectorMatchingResult {
 203     Matched,
 204     NotMatchedAndRestartFromClosestLaterSibling,
 205     NotMatchedAndRestartFromClosestDescendant,
 206     NotMatchedGlobally,
 207 }
 208
 209 /// Matches an inner selector.
 210 pub fn matches_selector<E, F>(selector: &SelectorInner<E::Impl>,
 211                               element: &E,
 212                               context: &mut MatchingContext,
 213                               flags_setter: &mut F)
 214                               -> bool
 215     where E: Element,
 216           F: FnMut(&E, ElementSelectorFlags),
 217 {
 218     // Use the bloom filter to fast-reject.
 219     if let Some(filter) = context.bloom_filter {
 220         if !may_match::<E>(&selector, filter) {
 221             return false;
 222         }
 223     }
 224
 225     matches_complex_selector(&selector.complex, element, context, flags_setter)
 226 }
 227
 228 /// Matches a complex selector.
 229 ///
 230 /// Use `matches_selector` if you need to skip pseudos.
 231 pub fn matches_complex_selector<E, F>(complex_selector: &ComplexSelector<E::Impl>,
 232                                       element: &E,
 233                                       context: &mut MatchingContext,
 234                                       flags_setter: &mut F)
 235                                       -> bool
 236     where E: Element,
 237           F: FnMut(&E, ElementSelectorFlags),
 238 {
 239     let mut iter = complex_selector.iter();
 240
 241     if cfg!(debug_assertions) {
 242         if context.matching_mode == MatchingMode::ForStatelessPseudoElement {
 243             assert!(complex_selector.iter().any(|c| {
 244                 matches!(*c, Component::PseudoElement(..))
 245             }));
 246         }
 247     }
 248
 249     if context.matching_mode == MatchingMode::ForStatelessPseudoElement {
 250         match *iter.next().unwrap() {
 251             // Stateful pseudo, just don't match.
 252             Component::NonTSPseudoClass(..) => return false,
 253             Component::PseudoElement(..) => {
 254                 // Pseudo, just eat the whole sequence.
 255                 let next = iter.next();
 256                 debug_assert!(next.is_none(),
 257                               "Someone messed up pseudo-element parsing?");
 258
 259                 if iter.next_sequence().is_none() {
 260                     return true;
 261                 }
 262             }
 263             _ => panic!("Used MatchingMode::ForStatelessPseudoElement in a non-pseudo selector"),
 264         }
 265     }
 266
 267     match matches_complex_selector_internal(iter,
 268                                             element,
 269                                             context,
 270                                             flags_setter) {
 271         SelectorMatchingResult::Matched => true,
 272         _ => false
 273     }
 274 }
 275
 276 fn matches_complex_selector_internal<E, F>(mut selector_iter: SelectorIter<E::Impl>,
 277                                            element: &E,
 278                                            context: &mut MatchingContext,
 279                                            flags_setter: &mut F)
 280                                            -> SelectorMatchingResult
 281      where E: Element,
 282            F: FnMut(&E, ElementSelectorFlags),
 283 {
 284     let matches_all_simple_selectors = selector_iter.all(|simple| {
 285         matches_simple_selector(simple, element, context, flags_setter)
 286     });
 287
 288     let combinator = selector_iter.next_sequence();
 289     let siblings = combinator.map_or(false, |c| c.is_sibling());
 290     if siblings {
 291         flags_setter(element, HAS_SLOW_SELECTOR_LATER_SIBLINGS);
 292     }
 293
 294     if !matches_all_simple_selectors {
 295         return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
 296     }
 297
 298     match combinator {
 299         None => SelectorMatchingResult::Matched,
 300         Some(c) => {
 301             let (mut next_element, candidate_not_found) = match c {
 302                 Combinator::NextSibling | Combinator::LaterSibling => {
 303                     (element.prev_sibling_element(),
 304                      SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant)
 305                 }
 306                 Combinator::Child | Combinator::Descendant => {
 307                     (element.parent_element(),
 308                      SelectorMatchingResult::NotMatchedGlobally)
 309                 }
 310                 Combinator::PseudoElement => {
 311                     (element.pseudo_element_originating_element(),
 312                      SelectorMatchingResult::NotMatchedGlobally)
 313                 }
 314             };
 315
 316             loop {
 317                 let element = match next_element {
 318                     None => return candidate_not_found,
 319                     Some(next_element) => next_element,
 320                 };
 321                 let result = matches_complex_selector_internal(selector_iter.clone(),
 322                                                                &element,
 323                                                                context,
 324                                                                flags_setter);
 325                 match (result, c) {
 326                     // Return the status immediately.
 327                     (SelectorMatchingResult::Matched, _) => return result,
 328                     (SelectorMatchingResult::NotMatchedGlobally, _) => return result,
 329
 330                     // Upgrade the failure status to
 331                     // NotMatchedAndRestartFromClosestDescendant.
 332                     (_, Combinator::PseudoElement) |
 333                     (_, Combinator::Child) => return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
 334
 335                     // Return the status directly.
 336                     (_, Combinator::NextSibling) => return result,
 337
 338                     // If the failure status is NotMatchedAndRestartFromClosestDescendant
 339                     // and combinator is Combinator::LaterSibling, give up this Combinator::LaterSibling matching
 340                     // and restart from the closest descendant combinator.
 341                     (SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant, Combinator::LaterSibling)
 342                         => return result,
 343
 344                     // The Combinator::Descendant combinator and the status is
 345                     // NotMatchedAndRestartFromClosestLaterSibling or
 346                     // NotMatchedAndRestartFromClosestDescendant,
 347                     // or the Combinator::LaterSibling combinator and the status is
 348                     // NotMatchedAndRestartFromClosestDescendant
 349                     // can continue to matching on the next candidate element.
 350                     _ => {},
 351                 }
 352                 next_element = if siblings {
 353                     element.prev_sibling_element()
 354                 } else {
 355                     element.parent_element()
 356                 };
 357             }
 358         }
 359     }
 360 }
 361
 362 /// Determines whether the given element matches the given single selector.
 363 #[inline]
 364 fn matches_simple_selector<E, F>(
 365         selector: &Component<E::Impl>,
 366         element: &E,
 367         context: &mut MatchingContext,
 368         flags_setter: &mut F)
 369         -> bool
 370     where E: Element,
 371           F: FnMut(&E, ElementSelectorFlags),
 372 {
 373     macro_rules! relation_if {
 374         ($ex:expr, $flag:ident) => {
 375             if $ex {
 376                 context.relations |= $flag;
 377                 true
 378             } else {
 379                 false
 380             }
 381         }
 382     }
 383
 384     match *selector {
 385         Component::Combinator(_) => unreachable!(),
 386         Component::PseudoElement(ref pseudo) => {
 387             element.match_pseudo_element(pseudo, context)
 388         }
 389         Component::LocalName(LocalName { ref name, ref lower_name }) => {
 390             let is_html = element.is_html_element_in_html_document();
 391             element.get_local_name() == select_name(is_html, name, lower_name).borrow()
 392         }
 393         Component::ExplicitUniversalType |
 394         Component::ExplicitAnyNamespace => {
 395             true
 396         }
 397         Component::Namespace(_, ref url) |
 398         Component::DefaultNamespace(ref url) => {
 399             element.get_namespace() == url.borrow()
 400         }
 401         Component::ExplicitNoNamespace => {
 402             let ns = ::parser::namespace_empty_string::<E::Impl>();
 403             element.get_namespace() == ns.borrow()
 404         }
 405         // TODO: case-sensitivity depends on the document type and quirks mode
 406         Component::ID(ref id) => {
 407             relation_if!(element.get_id().map_or(false, |attr| attr == *id),
 408                          AFFECTED_BY_ID_SELECTOR)
 409         }
 410         Component::Class(ref class) => {
 411             element.has_class(class)
 412         }
 413         Component::AttributeInNoNamespaceExists { ref local_name, ref local_name_lower } => {
 414             let is_html = element.is_html_element_in_html_document();
 415             element.attr_matches(
 416                 &NamespaceConstraint::Specific(&::parser::namespace_empty_string::<E::Impl>()),
 417                 select_name(is_html, local_name, local_name_lower),
 418                 &AttrSelectorOperation::Exists
 419             )
 420         }
 421         Component::AttributeInNoNamespace {
 422             ref local_name,
 423             ref local_name_lower,
 424             ref value,
 425             operator,
 426             case_sensitivity,
 427             never_matches,
 428         } => {
 429             if never_matches {
 430                 return false
 431             }
 432             let is_html = element.is_html_element_in_html_document();
 433             element.attr_matches(
 434                 &NamespaceConstraint::Specific(&::parser::namespace_empty_string::<E::Impl>()),
 435                 select_name(is_html, local_name, local_name_lower),
 436                 &AttrSelectorOperation::WithValue {
 437                     operator: operator,
 438                     case_sensitivity: case_sensitivity.to_unconditional(is_html),
 439                     expected_value: value,
 440                 }
 441             )
 442         }
 443         Component::AttributeOther(ref attr_sel) => {
 444             if attr_sel.never_matches {
 445                 return false
 446             }
 447             let is_html = element.is_html_element_in_html_document();
 448             element.attr_matches(
 449                 &attr_sel.namespace(),
 450                 select_name(is_html, &attr_sel.local_name, &attr_sel.local_name_lower),
 451                 &match attr_sel.operation {
 452                     ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
 453                     ParsedAttrSelectorOperation::WithValue {
 454                         operator,
 455                         case_sensitivity,
 456                         ref expected_value,
 457                     } => {
 458                         AttrSelectorOperation::WithValue {
 459                             operator: operator,
 460                             case_sensitivity: case_sensitivity.to_unconditional(is_html),
 461                             expected_value: expected_value,
 462                         }
 463                     }
 464                 }
 465             )
 466         }
 467         Component::NonTSPseudoClass(ref pc) => {
 468             element.match_non_ts_pseudo_class(pc, context, flags_setter)
 469         }
 470         Component::FirstChild => {
 471             matches_first_child(element, flags_setter)
 472         }
 473         Component::LastChild => {
 474             matches_last_child(element, flags_setter)
 475         }
 476         Component::OnlyChild => {
 477             matches_first_child(element, flags_setter) &&
 478             matches_last_child(element, flags_setter)
 479         }
 480         Component::Root => {
 481             // We never share styles with an element with no parent, so no point
 482             // in creating a new StyleRelation.
 483             element.is_root()
 484         }
 485         Component::Empty => {
 486             flags_setter(element, HAS_EMPTY_SELECTOR);
 487             element.is_empty()
 488         }
 489         Component::NthChild(a, b) => {
 490             matches_generic_nth_child(element, a, b, false, false, flags_setter)
 491         }
 492         Component::NthLastChild(a, b) => {
 493             matches_generic_nth_child(element, a, b, false, true, flags_setter)
 494         }
 495         Component::NthOfType(a, b) => {
 496             matches_generic_nth_child(element, a, b, true, false, flags_setter)
 497         }
 498         Component::NthLastOfType(a, b) => {
 499             matches_generic_nth_child(element, a, b, true, true, flags_setter)
 500         }
 501         Component::FirstOfType => {
 502             matches_generic_nth_child(element, 0, 1, true, false, flags_setter)
 503         }
 504         Component::LastOfType => {
 505             matches_generic_nth_child(element, 0, 1, true, true, flags_setter)
 506         }
 507         Component::OnlyOfType => {
 508             matches_generic_nth_child(element, 0, 1, true, false, flags_setter) &&
 509             matches_generic_nth_child(element, 0, 1, true, true, flags_setter)
 510         }
 511         Component::Negation(ref negated) => {
 512             !negated.iter().all(|ss| matches_simple_selector(ss, element, context, flags_setter))
 513         }
 514     }
 515 }
 516
 517 fn select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T) -> &'a T {
 518     if is_html {
 519         local_name_lower
 520     } else {
 521         local_name
 522     }
 523 }
 524
 525 #[inline]
 526 fn matches_generic_nth_child<E, F>(element: &E,
 527                                    a: i32,
 528                                    b: i32,
 529                                    is_of_type: bool,
 530                                    is_from_end: bool,
 531                                    flags_setter: &mut F)
 532                                    -> bool
 533     where E: Element,
 534           F: FnMut(&E, ElementSelectorFlags),
 535 {
 536     flags_setter(element, if is_from_end {
 537         HAS_SLOW_SELECTOR
 538     } else {
 539         HAS_SLOW_SELECTOR_LATER_SIBLINGS
 540     });
 541
 542     let mut index: i32 = 1;
 543     let mut next_sibling = if is_from_end {
 544         element.next_sibling_element()
 545     } else {
 546         element.prev_sibling_element()
 547     };
 548
 549     loop {
 550         let sibling = match next_sibling {
 551             None => break,
 552             Some(next_sibling) => next_sibling
 553         };
 554
 555         if is_of_type {
 556             if element.get_local_name() == sibling.get_local_name() &&
 557                 element.get_namespace() == sibling.get_namespace() {
 558                 index += 1;
 559             }
 560         } else {
 561           index += 1;
 562         }
 563         next_sibling = if is_from_end {
 564             sibling.next_sibling_element()
 565         } else {
 566             sibling.prev_sibling_element()
 567         };
 568     }
 569
 570     // Is there a non-negative integer n such that An+B=index?
 571     match index.checked_sub(b) {
 572         None => false,
 573         Some(an) => match an.checked_div(a) {
 574             Some(n) => n >= 0 && a * n == an,
 575             None /* a == 0 */ => an == 0,
 576         },
 577     }
 578 }
 579
 580 #[inline]
 581 fn matches_first_child<E, F>(element: &E, flags_setter: &mut F) -> bool
 582     where E: Element,
 583           F: FnMut(&E, ElementSelectorFlags),
 584 {
 585     flags_setter(element, HAS_EDGE_CHILD_SELECTOR);
 586     element.prev_sibling_element().is_none()
 587 }
 588
 589 #[inline]
 590 fn matches_last_child<E, F>(element: &E, flags_setter: &mut F) -> bool
 591     where E: Element,
 592           F: FnMut(&E, ElementSelectorFlags),
 593 {
 594     flags_setter(element, HAS_EDGE_CHILD_SELECTOR);
 595     element.next_sibling_element().is_none()
 596 }