diff options
| -rw-r--r-- | components/script/layout_wrapper.rs | 9 | ||||
| -rw-r--r-- | components/style/cache.rs | 32 | ||||
| -rw-r--r-- | components/style/context.rs | 82 | ||||
| -rw-r--r-- | components/style/dom.rs | 6 | ||||
| -rw-r--r-- | components/style/gecko/wrapper.rs | 9 | ||||
| -rw-r--r-- | components/style/matching.rs | 48 |
6 files changed, 129 insertions, 57 deletions
diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs index 4b118bdf7f1..e4df1b77ec3 100644 --- a/components/script/layout_wrapper.rs +++ b/components/script/layout_wrapper.rs @@ -55,6 +55,7 @@ use servo_atoms::Atom; use servo_url::ServoUrl; use std::fmt; use std::fmt::Debug; +use std::hash::{Hash, Hasher}; use std::marker::PhantomData; use std::mem::transmute; use std::sync::Arc; @@ -475,6 +476,14 @@ impl<'le> PartialEq for ServoLayoutElement<'le> { } } +impl<'le> Hash for ServoLayoutElement<'le> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.element.hash(state); + } +} + +impl<'le> Eq for ServoLayoutElement<'le> {} + impl<'le> ServoLayoutElement<'le> { fn from_layout_js(el: LayoutJS<Element>) -> ServoLayoutElement<'le> { ServoLayoutElement { diff --git a/components/style/cache.rs b/components/style/cache.rs index 2b12c8acf8f..fcdd7c79b8f 100644 --- a/components/style/cache.rs +++ b/components/style/cache.rs @@ -6,27 +6,28 @@ #![deny(missing_docs)] -use std::{iter, slice}; +use std::collections::VecDeque; +use std::collections::vec_deque; /// A LRU cache used to store a set of at most `n` elements at the same time. /// -/// Currently used for the style sharing candidate cache. +/// The most-recently-used entry is at index zero. pub struct LRUCache<K> { - entries: Vec<K>, + entries: VecDeque<K>, cache_size: usize, } /// A iterator over the items of the LRU cache. -pub type LRUCacheIterator<'a, K> = iter::Rev<slice::Iter<'a, K>>; +pub type LRUCacheIterator<'a, K> = vec_deque::Iter<'a, K>; /// A iterator over the mutable items of the LRU cache. -pub type LRUCacheMutIterator<'a, K> = iter::Rev<slice::IterMut<'a, K>>; +pub type LRUCacheMutIterator<'a, K> = vec_deque::IterMut<'a, K>; impl<K: PartialEq> LRUCache<K> { /// Create a new LRU cache with `size` elements at most. pub fn new(size: usize) -> Self { LRUCache { - entries: vec![], + entries: VecDeque::with_capacity(size), cache_size: size, } } @@ -37,32 +38,33 @@ impl<K: PartialEq> LRUCache<K> { } #[inline] - /// Touch a given position, and put it in the last item on the list. + /// Touch a given entry, putting it first in the list. pub fn touch(&mut self, pos: usize) { let last_index = self.entries.len() - 1; if pos != last_index { - let entry = self.entries.remove(pos); - self.entries.push(entry); + let entry = self.entries.remove(pos).unwrap(); + self.entries.push_front(entry); } } /// Iterate over the contents of this cache, from more to less recently /// used. - pub fn iter(&self) -> LRUCacheIterator<K> { - self.entries.iter().rev() + pub fn iter(&self) -> vec_deque::Iter<K> { + self.entries.iter() } /// Iterate mutably over the contents of this cache. - pub fn iter_mut(&mut self) -> LRUCacheMutIterator<K> { - self.entries.iter_mut().rev() + pub fn iter_mut(&mut self) -> vec_deque::IterMut<K> { + self.entries.iter_mut() } /// Insert a given key in the cache. pub fn insert(&mut self, key: K) { if self.entries.len() == self.cache_size { - self.entries.remove(0); + self.entries.pop_back(); } - self.entries.push(key); + self.entries.push_front(key); + debug_assert!(self.entries.len() <= self.cache_size); } /// Evict all elements from the cache. diff --git a/components/style/context.rs b/components/style/context.rs index f33e22a11f3..f89674e8d04 100644 --- a/components/style/context.rs +++ b/components/style/context.rs @@ -9,10 +9,12 @@ use animation::{Animation, PropertyAnimation}; use app_units::Au; use bit_vec::BitVec; use bloom::StyleBloom; +use cache::LRUCache; use data::ElementData; use dom::{OpaqueNode, TNode, TElement, SendElement}; use error_reporting::ParseErrorReporter; use euclid::Size2D; +use fnv::FnvHashMap; use font_metrics::FontMetricsProvider; #[cfg(feature = "gecko")] use gecko_bindings::structs; use matching::StyleSharingCandidateCache; @@ -281,10 +283,8 @@ bitflags! { /// is used by the style system to queue up work which is not safe to do during /// the parallel traversal. pub enum SequentialTask<E: TElement> { - /// Sets selector flags. This is used when we need to set flags on an - /// element that we don't have exclusive access to (i.e. the parent). - SetSelectorFlags(SendElement<E>, ElementSelectorFlags), - + /// Entry to avoid an unused type parameter error on servo. + Unused(SendElement<E>), #[cfg(feature = "gecko")] /// Marks that we need to update CSS animations, update effect properties of /// any type of animations after the normal traversal. @@ -297,9 +297,7 @@ impl<E: TElement> SequentialTask<E> { use self::SequentialTask::*; debug_assert!(thread_state::get() == thread_state::LAYOUT); match self { - SetSelectorFlags(el, flags) => { - unsafe { el.set_selector_flags(flags) }; - } + Unused(_) => unreachable!(), #[cfg(feature = "gecko")] UpdateAnimations(el, pseudo, tasks) => { unsafe { el.update_animations(pseudo.as_ref(), tasks) }; @@ -307,12 +305,6 @@ impl<E: TElement> SequentialTask<E> { } } - /// Creates a task to set the selector flags on an element. - pub fn set_selector_flags(el: E, flags: ElementSelectorFlags) -> Self { - use self::SequentialTask::*; - SetSelectorFlags(unsafe { SendElement::new(el) }, flags) - } - #[cfg(feature = "gecko")] /// Creates a task to update various animation state on a given (pseudo-)element. pub fn update_animations(el: E, pseudo: Option<PseudoElement>, @@ -322,6 +314,59 @@ impl<E: TElement> SequentialTask<E> { } } +/// Map from Elements to ElementSelectorFlags. Used to defer applying selector +/// flags until after the traversal. +pub struct SelectorFlagsMap<E: TElement> { + /// The hashmap storing the flags to apply. + map: FnvHashMap<SendElement<E>, ElementSelectorFlags>, + /// An LRU cache to avoid hashmap lookups, which can be slow if the map + /// gets big. + cache: LRUCache<(SendElement<E>, ElementSelectorFlags)>, +} + +#[cfg(debug_assertions)] +impl<E: TElement> Drop for SelectorFlagsMap<E> { + fn drop(&mut self) { + debug_assert!(self.map.is_empty()); + } +} + +impl<E: TElement> SelectorFlagsMap<E> { + /// Creates a new empty SelectorFlagsMap. + pub fn new() -> Self { + SelectorFlagsMap { + map: FnvHashMap::default(), + cache: LRUCache::new(4), + } + } + + /// Inserts some flags into the map for a given element. + pub fn insert_flags(&mut self, element: E, flags: ElementSelectorFlags) { + let el = unsafe { SendElement::new(element) }; + // Check the cache. If the flags have already been noted, we're done. + if self.cache.iter().find(|x| x.0 == el) + .map_or(ElementSelectorFlags::empty(), |x| x.1) + .contains(flags) { + return; + } + + let f = self.map.entry(el).or_insert(ElementSelectorFlags::empty()); + *f |= flags; + + // Insert into the cache. We don't worry about duplicate entries, + // which lets us avoid reshuffling. + self.cache.insert((unsafe { SendElement::new(element) }, *f)) + } + + /// Applies the flags. Must be called on the main thread. + pub fn apply_flags(&mut self) { + debug_assert!(thread_state::get() == thread_state::LAYOUT); + for (el, flags) in self.map.drain() { + unsafe { el.set_selector_flags(flags); } + } + } +} + /// A thread-local style context. /// /// This context contains data that needs to be used during restyling, but is @@ -339,6 +384,11 @@ pub struct ThreadLocalStyleContext<E: TElement> { /// the rest of the styling is complete. This is useful for infrequently-needed /// non-threadsafe operations. pub tasks: Vec<SequentialTask<E>>, + /// ElementSelectorFlags that need to be applied after the traversal is + /// complete. This map is used in cases where the matching algorithm needs + /// to set flags on elements it doesn't have exclusive access to (i.e. other + /// than the current element). + pub selector_flags: SelectorFlagsMap<E>, /// Statistics about the traversal. pub statistics: TraversalStatistics, /// Information related to the current element, non-None during processing. @@ -356,6 +406,7 @@ impl<E: TElement> ThreadLocalStyleContext<E> { bloom_filter: StyleBloom::new(), new_animations_sender: shared.local_context_creation_data.lock().unwrap().new_animations_sender.clone(), tasks: Vec::new(), + selector_flags: SelectorFlagsMap::new(), statistics: TraversalStatistics::default(), current_element_info: None, font_metrics_provider: E::FontMetricsProvider::create_from(shared), @@ -393,9 +444,12 @@ impl<E: TElement> ThreadLocalStyleContext<E> { impl<E: TElement> Drop for ThreadLocalStyleContext<E> { fn drop(&mut self) { debug_assert!(self.current_element_info.is_none()); + debug_assert!(thread_state::get() == thread_state::LAYOUT); + + // Apply any slow selector flags that need to be set on parents. + self.selector_flags.apply_flags(); // Execute any enqueued sequential tasks. - debug_assert!(thread_state::get() == thread_state::LAYOUT); for task in self.tasks.drain(..) { task.execute(); } diff --git a/components/style/dom.rs b/components/style/dom.rs index f64c594bd4e..ea2383f409e 100644 --- a/components/style/dom.rs +++ b/components/style/dom.rs @@ -20,6 +20,7 @@ use shared_lock::Locked; use sink::Push; use std::fmt; use std::fmt::Debug; +use std::hash::Hash; use std::ops::Deref; use std::sync::Arc; use stylist::ApplicableDeclarationBlock; @@ -275,7 +276,8 @@ pub struct AnimationRules(pub Option<Arc<Locked<PropertyDeclarationBlock>>>, pub Option<Arc<Locked<PropertyDeclarationBlock>>>); /// The element trait, the main abstraction the style crate acts over. -pub trait TElement : PartialEq + Debug + Sized + Copy + Clone + ElementExt + PresentationalHintsSynthetizer { +pub trait TElement : Eq + PartialEq + Debug + Hash + Sized + Copy + Clone + + ElementExt + PresentationalHintsSynthetizer { /// The concrete node type. type ConcreteNode: TNode<ConcreteElement = Self>; @@ -518,7 +520,7 @@ impl<N: TNode> Deref for SendNode<N> { /// Same reason as for the existence of SendNode, SendElement does the proper /// things for a given `TElement`. -#[derive(Debug, PartialEq)] +#[derive(Debug, Eq, Hash, PartialEq)] pub struct SendElement<E: TElement>(E); unsafe impl<E: TElement> Send for SendElement<E> {} impl<E: TElement> SendElement<E> { diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs index 0531384ae32..610686ab6de 100644 --- a/components/style/gecko/wrapper.rs +++ b/components/style/gecko/wrapper.rs @@ -67,6 +67,7 @@ use shared_lock::Locked; use sink::Push; use std::cell::RefCell; use std::fmt; +use std::hash::{Hash, Hasher}; use std::ptr; use std::sync::Arc; use string_cache::{Atom, Namespace, WeakAtom, WeakNamespace}; @@ -705,6 +706,14 @@ impl<'le> PartialEq for GeckoElement<'le> { } } +impl<'le> Eq for GeckoElement<'le> {} + +impl<'le> Hash for GeckoElement<'le> { + fn hash<H: Hasher>(&self, state: &mut H) { + (self.0 as *const _).hash(state); + } +} + impl<'le> PresentationalHintsSynthetizer for GeckoElement<'le> { fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V) where V: Push<ApplicableDeclarationBlock>, diff --git a/components/style/matching.rs b/components/style/matching.rs index 58a5c11c742..595f7a10eb9 100644 --- a/components/style/matching.rs +++ b/components/style/matching.rs @@ -13,7 +13,7 @@ use atomic_refcell::AtomicRefMut; use bit_vec::BitVec; use cache::{LRUCache, LRUCacheMutIterator}; use cascade_info::CascadeInfo; -use context::{CurrentElementInfo, SequentialTask, SharedStyleContext, StyleContext}; +use context::{CurrentElementInfo, SelectorFlagsMap, SharedStyleContext, StyleContext}; use data::{ComputedStyle, ElementData, ElementStyles, RestyleData}; use dom::{AnimationRules, SendElement, TElement, TNode}; use font_metrics::FontMetricsProvider; @@ -108,7 +108,7 @@ fn element_matches_candidate<E: TElement>(element: &E, shared: &SharedStyleContext, bloom: &BloomFilter, info: &mut CurrentElementInfo, - tasks: &mut Vec<SequentialTask<E>>) + selector_flags_map: &mut SelectorFlagsMap<E>) -> Result<ComputedStyle, CacheMiss> { macro_rules! miss { ($miss: ident) => { @@ -157,7 +157,7 @@ fn element_matches_candidate<E: TElement>(element: &E, } if !revalidate(element, candidate, candidate_element, - shared, bloom, info, tasks) { + shared, bloom, info, selector_flags_map) { miss!(Revalidation) } @@ -205,7 +205,7 @@ fn revalidate<E: TElement>(element: &E, shared: &SharedStyleContext, bloom: &BloomFilter, info: &mut CurrentElementInfo, - tasks: &mut Vec<SequentialTask<E>>) + selector_flags_map: &mut SelectorFlagsMap<E>) -> bool { // NB: We could avoid matching ancestor selectors entirely (rather than // just depending on the bloom filter), at the expense of some complexity. @@ -235,7 +235,7 @@ fn revalidate<E: TElement>(element: &E, // child span is subsequently removed from the DOM, missing selector // flags would cause us to miss the restyle on the second span. let mut set_selector_flags = |el: &E, flags: ElementSelectorFlags| { - element.apply_selector_flags(tasks, el, flags); + element.apply_selector_flags(selector_flags_map, el, flags); }; info.revalidation_match_results = Some(stylist.match_revalidation_selectors(element, bloom, @@ -560,9 +560,9 @@ trait PrivateMatchMethods: TElement { tasks.insert(EFFECT_PROPERTIES); } if !tasks.is_empty() { - let task = SequentialTask::update_animations(self.as_node().as_element().unwrap(), - pseudo.cloned(), - tasks); + let task = ::context::SequentialTask::update_animations(*self, + pseudo.cloned(), + tasks); context.thread_local.tasks.push(task); } } @@ -698,11 +698,11 @@ trait PrivateMatchMethods: TElement { shared: &SharedStyleContext, bloom: &BloomFilter, info: &mut CurrentElementInfo, - tasks: &mut Vec<SequentialTask<Self>>) + selector_flags_map: &mut SelectorFlagsMap<Self>) -> Result<ComputedStyle, CacheMiss> { let candidate_element = *candidate.element; element_matches_candidate(self, candidate, &candidate_element, - shared, bloom, info, tasks) + shared, bloom, info, selector_flags_map) } } @@ -802,9 +802,9 @@ pub trait MatchMethods : TElement { let mut rule_nodes_changed = false; let bloom = context.thread_local.bloom_filter.filter(); - let tasks = &mut context.thread_local.tasks; + let map = &mut context.thread_local.selector_flags; let mut set_selector_flags = |element: &Self, flags: ElementSelectorFlags| { - self.apply_selector_flags(tasks, element, flags); + self.apply_selector_flags(map, element, flags); }; // Compute the primary rule node. @@ -844,9 +844,9 @@ pub trait MatchMethods : TElement { Vec::<ApplicableDeclarationBlock>::with_capacity(16); let mut rule_nodes_changed = false; - let tasks = &mut context.thread_local.tasks; + let map = &mut context.thread_local.selector_flags; let mut set_selector_flags = |element: &Self, flags: ElementSelectorFlags| { - self.apply_selector_flags(tasks, element, flags); + self.apply_selector_flags(map, element, flags); }; // Borrow the stuff we need here so the borrow checker doesn't get mad @@ -923,10 +923,10 @@ pub trait MatchMethods : TElement { /// /// Anyway, let's do the obvious thing for now. fn apply_selector_flags(&self, - tasks: &mut Vec<SequentialTask<Self>>, + map: &mut SelectorFlagsMap<Self>, element: &Self, flags: ElementSelectorFlags) { - // Apply the selector flags. + // Handle flags that apply to the element. let self_flags = flags.for_self(); if !self_flags.is_empty() { if element == self { @@ -942,21 +942,17 @@ pub trait MatchMethods : TElement { // Instead, we can read them, and post them if necessary as a // sequential task in order for them to be processed later. if !element.has_selector_flags(self_flags) { - let task = - SequentialTask::set_selector_flags(element.clone(), - self_flags); - tasks.push(task); + map.insert_flags(*element, self_flags); } } } + + // Handle flags that apply to the parent. let parent_flags = flags.for_parent(); if !parent_flags.is_empty() { if let Some(p) = element.parent_element() { - // Avoid the overhead of the SequentialTask if the flags are - // already set. if !p.has_selector_flags(parent_flags) { - let task = SequentialTask::set_selector_flags(p, parent_flags); - tasks.push(task); + map.insert_flags(p, parent_flags); } } } @@ -1055,7 +1051,7 @@ pub trait MatchMethods : TElement { let current_element_info = &mut context.thread_local.current_element_info.as_mut().unwrap(); let bloom = context.thread_local.bloom_filter.filter(); - let tasks = &mut context.thread_local.tasks; + let selector_flags_map = &mut context.thread_local.selector_flags; let mut should_clear_cache = false; for (i, candidate) in cache.iter_mut().enumerate() { let sharing_result = @@ -1063,7 +1059,7 @@ pub trait MatchMethods : TElement { &context.shared, bloom, current_element_info, - tasks); + selector_flags_map); match sharing_result { Ok(shared_style) => { // Yay, cache hit. Share the style. |