servo/components/style/dom_apis.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 //! Generic implementations of some DOM APIs so they can be shared between Servo
   6 //! and Gecko.
   7
   8 use crate::context::QuirksMode;
   9 use crate::dom::{TDocument, TElement, TNode, TShadowRoot};
  10 use crate::invalidation::element::invalidation_map::Dependency;
  11 use crate::invalidation::element::invalidator::{
  12     DescendantInvalidationLists, Invalidation, SiblingTraversalMap,
  13 };
  14 use crate::invalidation::element::invalidator::{InvalidationProcessor, InvalidationVector};
  15 use crate::selector_parser::SelectorImpl;
  16 use crate::values::AtomIdent;
  17 use selectors::attr::CaseSensitivity;
  18 use selectors::matching::{
  19     self, MatchingForInvalidation, MatchingContext, MatchingMode, NeedsSelectorFlags,
  20     SelectorCaches,
  21 };
  22 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
  23 use selectors::parser::{Combinator, Component, LocalName};
  24 use selectors::{Element, SelectorList};
  25 use smallvec::SmallVec;
  26
  27 /// <https://dom.spec.whatwg.org/#dom-element-matches>
  28 pub fn element_matches<E>(
  29     element: &E,
  30     selector_list: &SelectorList<E::Impl>,
  31     quirks_mode: QuirksMode,
  32 ) -> bool
  33 where
  34     E: Element,
  35 {
  36     let mut selector_caches = SelectorCaches::default();
  37
  38     let mut context = MatchingContext::new(
  39         MatchingMode::Normal,
  40         None,
  41         &mut selector_caches,
  42         quirks_mode,
  43         NeedsSelectorFlags::No,
  44         MatchingForInvalidation::No,
  45     );
  46     context.scope_element = Some(element.opaque());
  47     context.current_host = element.containing_shadow_host().map(|e| e.opaque());
  48     matching::matches_selector_list(selector_list, element, &mut context)
  49 }
  50
  51 /// <https://dom.spec.whatwg.org/#dom-element-closest>
  52 pub fn element_closest<E>(
  53     element: E,
  54     selector_list: &SelectorList<E::Impl>,
  55     quirks_mode: QuirksMode,
  56 ) -> Option<E>
  57 where
  58     E: Element,
  59 {
  60     let mut selector_caches = SelectorCaches::default();
  61
  62     let mut context = MatchingContext::new(
  63         MatchingMode::Normal,
  64         None,
  65         &mut selector_caches,
  66         quirks_mode,
  67         NeedsSelectorFlags::No,
  68         MatchingForInvalidation::No,
  69     );
  70     context.scope_element = Some(element.opaque());
  71     context.current_host = element.containing_shadow_host().map(|e| e.opaque());
  72
  73     let mut current = Some(element);
  74     while let Some(element) = current.take() {
  75         if matching::matches_selector_list(selector_list, &element, &mut context) {
  76             return Some(element);
  77         }
  78         current = element.parent_element();
  79     }
  80
  81     return None;
  82 }
  83
  84 /// A selector query abstraction, in order to be generic over QuerySelector and
  85 /// QuerySelectorAll.
  86 pub trait SelectorQuery<E: TElement> {
  87     /// The output of the query.
  88     type Output;
  89
  90     /// Whether the query should stop after the first element has been matched.
  91     fn should_stop_after_first_match() -> bool;
  92
  93     /// Append an element matching after the first query.
  94     fn append_element(output: &mut Self::Output, element: E);
  95
  96     /// Returns true if the output is empty.
  97     fn is_empty(output: &Self::Output) -> bool;
  98 }
  99
 100 /// The result of a querySelectorAll call.
 101 pub type QuerySelectorAllResult<E> = SmallVec<[E; 128]>;
 102
 103 /// A query for all the elements in a subtree.
 104 pub struct QueryAll;
 105
 106 impl<E: TElement> SelectorQuery<E> for QueryAll {
 107     type Output = QuerySelectorAllResult<E>;
 108
 109     fn should_stop_after_first_match() -> bool {
 110         false
 111     }
 112
 113     fn append_element(output: &mut Self::Output, element: E) {
 114         output.push(element);
 115     }
 116
 117     fn is_empty(output: &Self::Output) -> bool {
 118         output.is_empty()
 119     }
 120 }
 121
 122 /// A query for the first in-tree match of all the elements in a subtree.
 123 pub struct QueryFirst;
 124
 125 impl<E: TElement> SelectorQuery<E> for QueryFirst {
 126     type Output = Option<E>;
 127
 128     fn should_stop_after_first_match() -> bool {
 129         true
 130     }
 131
 132     fn append_element(output: &mut Self::Output, element: E) {
 133         if output.is_none() {
 134             *output = Some(element)
 135         }
 136     }
 137
 138     fn is_empty(output: &Self::Output) -> bool {
 139         output.is_none()
 140     }
 141 }
 142
 143 struct QuerySelectorProcessor<'a, 'b, E, Q>
 144 where
 145     E: TElement + 'a,
 146     Q: SelectorQuery<E>,
 147     Q::Output: 'a,
 148 {
 149     results: &'a mut Q::Output,
 150     matching_context: MatchingContext<'b, E::Impl>,
 151     traversal_map: SiblingTraversalMap<E>,
 152     dependencies: &'a [Dependency],
 153 }
 154
 155 impl<'a, 'b, E, Q> InvalidationProcessor<'a, 'b, E> for QuerySelectorProcessor<'a, 'b, E, Q>
 156 where
 157     E: TElement + 'a,
 158     Q: SelectorQuery<E>,
 159     Q::Output: 'a,
 160 {
 161     fn light_tree_only(&self) -> bool {
 162         true
 163     }
 164
 165     fn check_outer_dependency(&mut self, _: &Dependency, _: E) -> bool {
 166         debug_assert!(
 167             false,
 168             "How? We should only have parent-less dependencies here!"
 169         );
 170         true
 171     }
 172
 173     fn collect_invalidations(
 174         &mut self,
 175         element: E,
 176         self_invalidations: &mut InvalidationVector<'a>,
 177         descendant_invalidations: &mut DescendantInvalidationLists<'a>,
 178         _sibling_invalidations: &mut InvalidationVector<'a>,
 179     ) -> bool {
 180         // TODO(emilio): If the element is not a root element, and
 181         // selector_list has any descendant combinator, we need to do extra work
 182         // in order to handle properly things like:
 183         //
 184         //   <div id="a">
 185         //     <div id="b">
 186         //       <div id="c"></div>
 187         //     </div>
 188         //   </div>
 189         //
 190         // b.querySelector('#a div'); // Should return "c".
 191         //
 192         // For now, assert it's a root element.
 193         debug_assert!(element.parent_element().is_none());
 194
 195         let target_vector = if self.matching_context.scope_element.is_some() {
 196             &mut descendant_invalidations.dom_descendants
 197         } else {
 198             self_invalidations
 199         };
 200
 201         for dependency in self.dependencies.iter() {
 202             target_vector.push(Invalidation::new(
 203                 dependency,
 204                 self.matching_context.current_host.clone(),
 205             ))
 206         }
 207
 208         false
 209     }
 210
 211     fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl> {
 212         &mut self.matching_context
 213     }
 214
 215     fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
 216         &self.traversal_map
 217     }
 218
 219     fn should_process_descendants(&mut self, _: E) -> bool {
 220         if Q::should_stop_after_first_match() {
 221             return Q::is_empty(&self.results);
 222         }
 223
 224         true
 225     }
 226
 227     fn invalidated_self(&mut self, e: E) {
 228         Q::append_element(self.results, e);
 229     }
 230
 231     fn invalidated_sibling(&mut self, e: E, _of: E) {
 232         Q::append_element(self.results, e);
 233     }
 234
 235     fn recursion_limit_exceeded(&mut self, _e: E) {}
 236     fn invalidated_descendants(&mut self, _e: E, _child: E) {}
 237 }
 238
 239 fn collect_all_elements<E, Q, F>(root: E::ConcreteNode, results: &mut Q::Output, mut filter: F)
 240 where
 241     E: TElement,
 242     Q: SelectorQuery<E>,
 243     F: FnMut(E) -> bool,
 244 {
 245     for node in root.dom_descendants() {
 246         let element = match node.as_element() {
 247             Some(e) => e,
 248             None => continue,
 249         };
 250
 251         if !filter(element) {
 252             continue;
 253         }
 254
 255         Q::append_element(results, element);
 256         if Q::should_stop_after_first_match() {
 257             return;
 258         }
 259     }
 260 }
 261
 262 /// Returns whether a given element connected to `root` is descendant of `root`.
 263 ///
 264 /// NOTE(emilio): if root == element, this returns false.
 265 fn connected_element_is_descendant_of<E>(element: E, root: E::ConcreteNode) -> bool
 266 where
 267     E: TElement,
 268 {
 269     // Optimize for when the root is a document or a shadow root and the element
 270     // is connected to that root.
 271     if root.as_document().is_some() {
 272         debug_assert!(element.as_node().is_in_document(), "Not connected?");
 273         debug_assert_eq!(
 274             root,
 275             root.owner_doc().as_node(),
 276             "Where did this element come from?",
 277         );
 278         return true;
 279     }
 280
 281     if root.as_shadow_root().is_some() {
 282         debug_assert_eq!(
 283             element.containing_shadow().unwrap().as_node(),
 284             root,
 285             "Not connected?"
 286         );
 287         return true;
 288     }
 289
 290     let mut current = element.as_node().parent_node();
 291     while let Some(n) = current.take() {
 292         if n == root {
 293             return true;
 294         }
 295
 296         current = n.parent_node();
 297     }
 298     false
 299 }
 300
 301 /// Fast path for iterating over every element with a given id in the document
 302 /// or shadow root that `root` is connected to.
 303 fn fast_connected_elements_with_id<'a, N>(
 304     root: N,
 305     id: &AtomIdent,
 306     case_sensitivity: CaseSensitivity,
 307 ) -> Result<&'a [N::ConcreteElement], ()>
 308 where
 309     N: TNode + 'a,
 310 {
 311     if case_sensitivity != CaseSensitivity::CaseSensitive {
 312         return Err(());
 313     }
 314
 315     if root.is_in_document() {
 316         return root.owner_doc().elements_with_id(id);
 317     }
 318
 319     if let Some(shadow) = root.as_shadow_root() {
 320         return shadow.elements_with_id(id);
 321     }
 322
 323     if let Some(shadow) = root.as_element().and_then(|e| e.containing_shadow()) {
 324         return shadow.elements_with_id(id);
 325     }
 326
 327     Err(())
 328 }
 329
 330 /// Collects elements with a given id under `root`, that pass `filter`.
 331 fn collect_elements_with_id<E, Q, F>(
 332     root: E::ConcreteNode,
 333     id: &AtomIdent,
 334     results: &mut Q::Output,
 335     class_and_id_case_sensitivity: CaseSensitivity,
 336     mut filter: F,
 337 ) where
 338     E: TElement,
 339     Q: SelectorQuery<E>,
 340     F: FnMut(E) -> bool,
 341 {
 342     let elements = match fast_connected_elements_with_id(root, id, class_and_id_case_sensitivity) {
 343         Ok(elements) => elements,
 344         Err(()) => {
 345             collect_all_elements::<E, Q, _>(root, results, |e| {
 346                 e.has_id(id, class_and_id_case_sensitivity) && filter(e)
 347             });
 348
 349             return;
 350         },
 351     };
 352
 353     for element in elements {
 354         // If the element is not an actual descendant of the root, even though
 355         // it's connected, we don't really care about it.
 356         if !connected_element_is_descendant_of(*element, root) {
 357             continue;
 358         }
 359
 360         if !filter(*element) {
 361             continue;
 362         }
 363
 364         Q::append_element(results, *element);
 365         if Q::should_stop_after_first_match() {
 366             break;
 367         }
 368     }
 369 }
 370
 371 fn has_attr<E>(element: E, local_name: &AtomIdent) -> bool
 372 where
 373     E: TElement,
 374 {
 375     let mut found = false;
 376     element.each_attr_name(|name| found |= name == local_name);
 377     found
 378 }
 379
 380 #[inline(always)]
 381 fn local_name_matches<E>(element: E, local_name: &LocalName<E::Impl>) -> bool
 382 where
 383     E: TElement,
 384 {
 385     let LocalName {
 386         ref name,
 387         ref lower_name,
 388     } = *local_name;
 389
 390     let chosen_name = if name == lower_name || element.is_html_element_in_html_document() {
 391         lower_name
 392     } else {
 393         name
 394     };
 395
 396     element.local_name() == &**chosen_name
 397 }
 398
 399 fn get_attr_name(component: &Component<SelectorImpl>) -> Option<&AtomIdent> {
 400     let (name, name_lower) = match component {
 401         Component::AttributeInNoNamespace { ref local_name, .. } => return Some(local_name),
 402         Component::AttributeInNoNamespaceExists {
 403             ref local_name,
 404             ref local_name_lower,
 405             ..
 406         } => (local_name, local_name_lower),
 407         Component::AttributeOther(ref attr) => (&attr.local_name, &attr.local_name_lower),
 408         _ => return None,
 409     };
 410     if name != name_lower {
 411         return None; // TODO: Maybe optimize this?
 412     }
 413     Some(name)
 414 }
 415
 416 fn get_id(component: &Component<SelectorImpl>) -> Option<&AtomIdent> {
 417     use selectors::attr::AttrSelectorOperator;
 418     Some(match component {
 419         Component::ID(ref id) => id,
 420         Component::AttributeInNoNamespace {
 421             ref operator,
 422             ref local_name,
 423             ref value,
 424             ..
 425         } => {
 426             if *local_name != local_name!("id") {
 427                 return None;
 428             }
 429             if *operator != AttrSelectorOperator::Equal {
 430                 return None;
 431             }
 432             AtomIdent::cast(&value.0)
 433         },
 434         _ => return None,
 435     })
 436 }
 437
 438 /// Fast paths for querySelector with a single simple selector.
 439 fn query_selector_single_query<E, Q>(
 440     root: E::ConcreteNode,
 441     component: &Component<E::Impl>,
 442     results: &mut Q::Output,
 443     class_and_id_case_sensitivity: CaseSensitivity,
 444 ) -> Result<(), ()>
 445 where
 446     E: TElement,
 447     Q: SelectorQuery<E>,
 448 {
 449     match *component {
 450         Component::ExplicitUniversalType => {
 451             collect_all_elements::<E, Q, _>(root, results, |_| true)
 452         },
 453         Component::Class(ref class) => collect_all_elements::<E, Q, _>(root, results, |element| {
 454             element.has_class(class, class_and_id_case_sensitivity)
 455         }),
 456         Component::LocalName(ref local_name) => {
 457             collect_all_elements::<E, Q, _>(root, results, |element| {
 458                 local_name_matches(element, local_name)
 459             })
 460         },
 461         Component::AttributeInNoNamespaceExists {
 462             ref local_name,
 463             ref local_name_lower,
 464         } => {
 465             collect_all_elements::<E, Q, _>(root, results, |element| {
 466                 element.has_attr_in_no_namespace(matching::select_name(&element, local_name, local_name_lower))
 467             })
 468         },
 469         Component::AttributeInNoNamespace {
 470             ref local_name,
 471             ref value,
 472             operator,
 473             case_sensitivity,
 474         } => {
 475             let empty_namespace = selectors::parser::namespace_empty_string::<E::Impl>();
 476             let namespace_constraint = NamespaceConstraint::Specific(&empty_namespace);
 477             collect_all_elements::<E, Q, _>(root, results, |element| {
 478                 element.attr_matches(
 479                     &namespace_constraint,
 480                     local_name,
 481                     &AttrSelectorOperation::WithValue {
 482                         operator,
 483                         case_sensitivity: matching::to_unconditional_case_sensitivity(case_sensitivity, &element),
 484                         value,
 485                     },
 486                 )
 487             })
 488         },
 489         ref other => {
 490             let id = match get_id(other) {
 491                 Some(id) => id,
 492                 // TODO(emilio): More fast paths?
 493                 None => return Err(()),
 494             };
 495             collect_elements_with_id::<E, Q, _>(
 496                 root,
 497                 id,
 498                 results,
 499                 class_and_id_case_sensitivity,
 500                 |_| true,
 501             );
 502         },
 503     }
 504
 505     Ok(())
 506 }
 507
 508 enum SimpleFilter<'a> {
 509     Class(&'a AtomIdent),
 510     Attr(&'a AtomIdent),
 511     LocalName(&'a LocalName<SelectorImpl>),
 512 }
 513
 514 /// Fast paths for a given selector query.
 515 ///
 516 /// When there's only one component, we go directly to
 517 /// `query_selector_single_query`, otherwise, we try to optimize by looking just
 518 /// at the subtrees rooted at ids in the selector, and otherwise we try to look
 519 /// up by class name or local name in the rightmost compound.
 520 ///
 521 /// FIXME(emilio, nbp): This may very well be a good candidate for code to be
 522 /// replaced by HolyJit :)
 523 fn query_selector_fast<E, Q>(
 524     root: E::ConcreteNode,
 525     selector_list: &SelectorList<E::Impl>,
 526     results: &mut Q::Output,
 527     matching_context: &mut MatchingContext<E::Impl>,
 528 ) -> Result<(), ()>
 529 where
 530     E: TElement,
 531     Q: SelectorQuery<E>,
 532 {
 533     // We need to return elements in document order, and reordering them
 534     // afterwards is kinda silly.
 535     if selector_list.0.len() > 1 {
 536         return Err(());
 537     }
 538
 539     let selector = &selector_list.0[0];
 540     let class_and_id_case_sensitivity = matching_context.classes_and_ids_case_sensitivity();
 541     // Let's just care about the easy cases for now.
 542     if selector.len() == 1 {
 543         if query_selector_single_query::<E, Q>(
 544             root,
 545             selector.iter().next().unwrap(),
 546             results,
 547             class_and_id_case_sensitivity,
 548         )
 549         .is_ok()
 550         {
 551             return Ok(());
 552         }
 553     }
 554
 555     let mut iter = selector.iter();
 556     let mut combinator: Option<Combinator> = None;
 557
 558     // We want to optimize some cases where there's no id involved whatsoever,
 559     // like `.foo .bar`, but we don't want to make `#foo .bar` slower because of
 560     // that.
 561     let mut simple_filter = None;
 562
 563     'selector_loop: loop {
 564         debug_assert!(combinator.map_or(true, |c| !c.is_sibling()));
 565
 566         'component_loop: for component in &mut iter {
 567             match *component {
 568                 Component::Class(ref class) => {
 569                     if combinator.is_none() {
 570                         simple_filter = Some(SimpleFilter::Class(class));
 571                     }
 572                 },
 573                 Component::LocalName(ref local_name) => {
 574                     if combinator.is_none() {
 575                         // Prefer to look at class rather than local-name if
 576                         // both are present.
 577                         if let Some(SimpleFilter::Class(..)) = simple_filter {
 578                             continue;
 579                         }
 580                         simple_filter = Some(SimpleFilter::LocalName(local_name));
 581                     }
 582                 },
 583                 ref other => {
 584                     if let Some(id) = get_id(other) {
 585                         if combinator.is_none() {
 586                             // In the rightmost compound, just find descendants of root that match
 587                             // the selector list with that id.
 588                             collect_elements_with_id::<E, Q, _>(
 589                                 root,
 590                                 id,
 591                                 results,
 592                                 class_and_id_case_sensitivity,
 593                                 |e| {
 594                                     matching::matches_selector_list(
 595                                         selector_list,
 596                                         &e,
 597                                         matching_context,
 598                                     )
 599                                 },
 600                             );
 601                             return Ok(());
 602                         }
 603
 604                         let elements = fast_connected_elements_with_id(
 605                             root,
 606                             id,
 607                             class_and_id_case_sensitivity,
 608                         )?;
 609                         if elements.is_empty() {
 610                             return Ok(());
 611                         }
 612
 613                         // Results need to be in document order. Let's not bother
 614                         // reordering or deduplicating nodes, which we would need to
 615                         // do if one element with the given id were a descendant of
 616                         // another element with that given id.
 617                         if !Q::should_stop_after_first_match() && elements.len() > 1 {
 618                             continue;
 619                         }
 620
 621                         for element in elements {
 622                             // If the element is not a descendant of the root, then
 623                             // it may have descendants that match our selector that
 624                             // _are_ descendants of the root, and other descendants
 625                             // that match our selector that are _not_.
 626                             //
 627                             // So we can't just walk over the element's descendants
 628                             // and match the selector against all of them, nor can
 629                             // we skip looking at this element's descendants.
 630                             //
 631                             // Give up on trying to optimize based on this id and
 632                             // keep walking our selector.
 633                             if !connected_element_is_descendant_of(*element, root) {
 634                                 continue 'component_loop;
 635                             }
 636
 637                             query_selector_slow::<E, Q>(
 638                                 element.as_node(),
 639                                 selector_list,
 640                                 results,
 641                                 matching_context,
 642                             );
 643
 644                             if Q::should_stop_after_first_match() && !Q::is_empty(&results) {
 645                                 break;
 646                             }
 647                         }
 648
 649                         return Ok(());
 650                     }
 651                     if combinator.is_none() && simple_filter.is_none() {
 652                         if let Some(attr_name) = get_attr_name(other) {
 653                             simple_filter = Some(SimpleFilter::Attr(attr_name));
 654                         }
 655                     }
 656                 },
 657             }
 658         }
 659
 660         loop {
 661             let next_combinator = match iter.next_sequence() {
 662                 None => break 'selector_loop,
 663                 Some(c) => c,
 664             };
 665
 666             // We don't want to scan stuff affected by sibling combinators,
 667             // given we scan the subtree of elements with a given id (and we
 668             // don't want to care about scanning the siblings' subtrees).
 669             if next_combinator.is_sibling() {
 670                 // Advance to the next combinator.
 671                 for _ in &mut iter {}
 672                 continue;
 673             }
 674
 675             combinator = Some(next_combinator);
 676             break;
 677         }
 678     }
 679
 680     // We got here without finding any ID or such that we could handle. Try to
 681     // use one of the simple filters.
 682     let simple_filter = match simple_filter {
 683         Some(f) => f,
 684         None => return Err(()),
 685     };
 686
 687     match simple_filter {
 688         SimpleFilter::Class(ref class) => {
 689             collect_all_elements::<E, Q, _>(root, results, |element| {
 690                 element.has_class(class, class_and_id_case_sensitivity) &&
 691                     matching::matches_selector_list(selector_list, &element, matching_context)
 692             });
 693         },
 694         SimpleFilter::LocalName(ref local_name) => {
 695             collect_all_elements::<E, Q, _>(root, results, |element| {
 696                 local_name_matches(element, local_name) &&
 697                     matching::matches_selector_list(selector_list, &element, matching_context)
 698             });
 699         },
 700         SimpleFilter::Attr(ref local_name) => {
 701             collect_all_elements::<E, Q, _>(root, results, |element| {
 702                 has_attr(element, local_name) &&
 703                     matching::matches_selector_list(selector_list, &element, matching_context)
 704             });
 705         },
 706     }
 707
 708     Ok(())
 709 }
 710
 711 // Slow path for a given selector query.
 712 fn query_selector_slow<E, Q>(
 713     root: E::ConcreteNode,
 714     selector_list: &SelectorList<E::Impl>,
 715     results: &mut Q::Output,
 716     matching_context: &mut MatchingContext<E::Impl>,
 717 ) where
 718     E: TElement,
 719     Q: SelectorQuery<E>,
 720 {
 721     collect_all_elements::<E, Q, _>(root, results, |element| {
 722         matching::matches_selector_list(selector_list, &element, matching_context)
 723     });
 724 }
 725
 726 /// Whether the invalidation machinery should be used for this query.
 727 #[derive(PartialEq)]
 728 pub enum MayUseInvalidation {
 729     /// We may use it if we deem it useful.
 730     Yes,
 731     /// Don't use it.
 732     No,
 733 }
 734
 735 /// <https://dom.spec.whatwg.org/#dom-parentnode-queryselector>
 736 pub fn query_selector<E, Q>(
 737     root: E::ConcreteNode,
 738     selector_list: &SelectorList<E::Impl>,
 739     results: &mut Q::Output,
 740     may_use_invalidation: MayUseInvalidation,
 741 ) where
 742     E: TElement,
 743     Q: SelectorQuery<E>,
 744 {
 745     use crate::invalidation::element::invalidator::TreeStyleInvalidator;
 746
 747     let mut selector_caches = SelectorCaches::default();
 748     let quirks_mode = root.owner_doc().quirks_mode();
 749
 750     let mut matching_context = MatchingContext::new(
 751         MatchingMode::Normal,
 752         None,
 753         &mut selector_caches,
 754         quirks_mode,
 755         NeedsSelectorFlags::No,
 756         MatchingForInvalidation::No,
 757     );
 758     let root_element = root.as_element();
 759     matching_context.scope_element = root_element.map(|e| e.opaque());
 760     matching_context.current_host = match root_element {
 761         Some(root) => root.containing_shadow_host().map(|host| host.opaque()),
 762         None => root.as_shadow_root().map(|root| root.host().opaque()),
 763     };
 764
 765     let fast_result =
 766         query_selector_fast::<E, Q>(root, selector_list, results, &mut matching_context);
 767
 768     if fast_result.is_ok() {
 769         return;
 770     }
 771
 772     // Slow path: Use the invalidation machinery if we're a root, and tree
 773     // traversal otherwise.
 774     //
 775     // See the comment in collect_invalidations to see why only if we're a root.
 776     //
 777     // The invalidation mechanism is only useful in presence of combinators.
 778     //
 779     // We could do that check properly here, though checking the length of the
 780     // selectors is a good heuristic.
 781     //
 782     // A selector with a combinator needs to have a length of at least 3: A
 783     // simple selector, a combinator, and another simple selector.
 784     let invalidation_may_be_useful = may_use_invalidation == MayUseInvalidation::Yes &&
 785         selector_list.0.iter().any(|s| s.len() > 2);
 786
 787     if root_element.is_some() || !invalidation_may_be_useful {
 788         query_selector_slow::<E, Q>(root, selector_list, results, &mut matching_context);
 789     } else {
 790         let dependencies = selector_list
 791             .0
 792             .iter()
 793             .map(|selector| Dependency::for_full_selector_invalidation(selector.clone()))
 794             .collect::<SmallVec<[_; 5]>>();
 795         let mut processor = QuerySelectorProcessor::<E, Q> {
 796             results,
 797             matching_context,
 798             traversal_map: SiblingTraversalMap::default(),
 799             dependencies: &dependencies,
 800         };
 801
 802         for node in root.dom_children() {
 803             if let Some(e) = node.as_element() {
 804                 TreeStyleInvalidator::new(e, /* stack_limit_checker = */ None, &mut processor)
 805                     .invalidate();
 806             }
 807         }
 808     }
 809 }