diff options
Diffstat (limited to 'components/layout')
| -rw-r--r-- | components/layout/block.rs | 1 | ||||
| -rw-r--r-- | components/layout/construct.rs | 13 | ||||
| -rw-r--r-- | components/layout/css/matching.rs | 104 | ||||
| -rw-r--r-- | components/layout/layout_task.rs | 18 | ||||
| -rw-r--r-- | components/layout/parallel.rs | 133 | ||||
| -rw-r--r-- | components/layout/wrapper.rs | 6 |
6 files changed, 238 insertions, 37 deletions
diff --git a/components/layout/block.rs b/components/layout/block.rs index 4a5395b7582..26564e9f84a 100644 --- a/components/layout/block.rs +++ b/components/layout/block.rs @@ -2449,4 +2449,3 @@ fn propagate_column_inline_sizes_to_child(kid: &mut Flow, kid_base.position.start.i = *inline_start_margin_edge; kid_base.position.size.inline = inline_size; } - diff --git a/components/layout/construct.rs b/components/layout/construct.rs index a1631a5858d..05231a091e4 100644 --- a/components/layout/construct.rs +++ b/components/layout/construct.rs @@ -186,15 +186,15 @@ enum WhitespaceStrippingMode { } /// An object that knows how to create flows. -pub struct FlowConstructor<'a, 'b> { +pub struct FlowConstructor<'a> { /// The layout context. - pub layout_context: &'b LayoutContext<'b>, + pub layout_context: &'a LayoutContext<'a>, } -impl<'a, 'b> FlowConstructor<'a, 'b> { +impl<'a> FlowConstructor<'a> { /// Creates a new flow constructor. - pub fn new<'b>(layout_context: &'b LayoutContext) - -> FlowConstructor<'a, 'b> { + pub fn new<'a>(layout_context: &'a LayoutContext<'a>) + -> FlowConstructor<'a> { FlowConstructor { layout_context: layout_context, } @@ -826,7 +826,7 @@ impl<'a, 'b> FlowConstructor<'a, 'b> { } } -impl<'a, 'b> PostorderNodeMutTraversal for FlowConstructor<'a, 'b> { +impl<'a> PostorderNodeMutTraversal for FlowConstructor<'a> { // Construct Flow based on 'display', 'position', and 'float' values. // // CSS 2.1 Section 9.7 @@ -1109,4 +1109,3 @@ impl FlowConstructionUtils for FlowRef { } } } - diff --git a/components/layout/css/matching.rs b/components/layout/css/matching.rs index c1d766c32ca..7abc683f4ad 100644 --- a/components/layout/css/matching.rs +++ b/components/layout/css/matching.rs @@ -12,6 +12,7 @@ use util::{LayoutDataAccess, LayoutDataWrapper}; use wrapper::{LayoutElement, LayoutNode, PostorderNodeMutTraversal, ThreadSafeLayoutNode}; use servo_util::atom::Atom; +use servo_util::bloom::BloomFilter; use servo_util::cache::{Cache, LRUCache, SimpleHashCache}; use servo_util::namespace::Null; use servo_util::smallvec::{SmallVec, SmallVec16}; @@ -19,7 +20,9 @@ use servo_util::str::DOMString; use std::mem; use std::hash::{Hash, sip}; use std::slice::Items; -use style::{After, Before, ComputedValues, DeclarationBlock, Stylist, TElement, TNode, cascade}; +use style; +use style::{After, Before, ComputedValues, DeclarationBlock, Stylist, TElement, TNode}; +use style::cascade; use sync::Arc; pub struct ApplicableDeclarations { @@ -211,16 +214,14 @@ impl StyleSharingCandidate { } }; - let mut style = Some(style); - let mut parent_style = Some(parent_style); let element = node.as_element(); if element.style_attribute().is_some() { return None } Some(StyleSharingCandidate { - style: style.take_unwrap(), - parent_style: parent_style.take_unwrap(), + style: style, + parent_style: parent_style, local_name: element.get_local_name().clone(), class: element.get_attr(&Null, "class") .map(|string| string.to_string()), @@ -278,16 +279,31 @@ pub enum StyleSharingResult<'ln> { } pub trait MatchMethods { + /// Inserts and removes the matching `Descendant` selectors from a bloom + /// filter. This is used to speed up CSS selector matching to remove + /// unnecessary tree climbs for `Descendant` queries. + /// + /// A bloom filter of the local names, namespaces, IDs, and classes is kept. + /// Therefore, each node must have its matching selectors inserted _after_ + /// its own selector matching and _before_ its children start. + fn insert_into_bloom_filter(&self, bf: &mut BloomFilter); + + /// After all the children are done css selector matching, this must be + /// called to reset the bloom filter after an `insert`. + fn remove_from_bloom_filter(&self, bf: &mut BloomFilter); + /// Performs aux initialization, selector matching, cascading, and flow construction /// sequentially. fn recalc_style_for_subtree(&self, stylist: &Stylist, layout_context: &LayoutContext, + parent_bf: &mut Option<BloomFilter>, applicable_declarations: &mut ApplicableDeclarations, parent: Option<LayoutNode>); fn match_node(&self, stylist: &Stylist, + parent_bf: &Option<BloomFilter>, applicable_declarations: &mut ApplicableDeclarations, shareable: &mut bool); @@ -403,20 +419,24 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> { impl<'ln> MatchMethods for LayoutNode<'ln> { fn match_node(&self, stylist: &Stylist, + parent_bf: &Option<BloomFilter>, applicable_declarations: &mut ApplicableDeclarations, shareable: &mut bool) { let style_attribute = self.as_element().style_attribute().as_ref(); applicable_declarations.normal_shareable = stylist.push_applicable_declarations(self, + parent_bf, style_attribute, None, &mut applicable_declarations.normal); stylist.push_applicable_declarations(self, + parent_bf, None, Some(Before), &mut applicable_declarations.before); stylist.push_applicable_declarations(self, + parent_bf, None, Some(After), &mut applicable_declarations.after); @@ -455,9 +475,63 @@ impl<'ln> MatchMethods for LayoutNode<'ln> { CannotShare(true) } + // The below two functions are copy+paste because I can't figure out how to + // write a function which takes a generic function. I don't think it can + // be done. + // + // Ideally, I'd want something like: + // + // > fn with_really_simple_selectors(&self, f: <H: Hash>|&H|); + + + // In terms of `SimpleSelector`s, these two functions will insert and remove: + // - `LocalNameSelector` + // - `NamepaceSelector` + // - `IDSelector` + // - `ClassSelector` + + fn insert_into_bloom_filter(&self, bf: &mut BloomFilter) { + // Only elements are interesting. + if !self.is_element() { return; } + let element = self.as_element(); + + bf.insert(element.get_local_name()); + bf.insert(element.get_namespace()); + element.get_id().map(|id| bf.insert(&id)); + + // TODO: case-sensitivity depends on the document type and quirks mode + element + .get_attr(&Null, "class") + .map(|attr| { + for c in attr.split(style::SELECTOR_WHITESPACE) { + bf.insert(&c); + } + }); + } + + fn remove_from_bloom_filter(&self, bf: &mut BloomFilter) { + // Only elements are interesting. + if !self.is_element() { return; } + let element = self.as_element(); + + bf.remove(element.get_local_name()); + bf.remove(element.get_namespace()); + element.get_id().map(|id| bf.remove(&id)); + + // TODO: case-sensitivity depends on the document type and quirks mode + element + .get_attr(&Null, "class") + .map(|attr| { + for c in attr.split(style::SELECTOR_WHITESPACE) { + bf.remove(&c); + } + }); + } + fn recalc_style_for_subtree(&self, stylist: &Stylist, layout_context: &LayoutContext, + parent_bf: &mut Option<BloomFilter>, applicable_declarations: &mut ApplicableDeclarations, parent: Option<LayoutNode>) { self.initialize_layout_data(layout_context.shared.layout_chan.clone()); @@ -471,7 +545,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> { match sharing_result { CannotShare(mut shareable) => { if self.is_element() { - self.match_node(stylist, applicable_declarations, &mut shareable) + self.match_node(stylist, &*parent_bf, applicable_declarations, &mut shareable); } unsafe { @@ -490,11 +564,22 @@ impl<'ln> MatchMethods for LayoutNode<'ln> { StyleWasShared(index) => layout_context.style_sharing_candidate_cache().touch(index), } + match *parent_bf { + None => {}, + Some(ref mut pbf) => self.insert_into_bloom_filter(pbf), + } + for kid in self.children() { kid.recalc_style_for_subtree(stylist, - layout_context, - applicable_declarations, - Some(self.clone())) + layout_context, + parent_bf, + applicable_declarations, + Some(self.clone())); + } + + match *parent_bf { + None => {}, + Some(ref mut pbf) => self.remove_from_bloom_filter(pbf), } // Construct flows. @@ -555,4 +640,3 @@ impl<'ln> MatchMethods for LayoutNode<'ln> { } } } - diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs index 62c6781557c..36db0d8c44e 100644 --- a/components/layout/layout_task.rs +++ b/components/layout/layout_task.rs @@ -45,6 +45,7 @@ use servo_msg::constellation_msg::{ConstellationChan, PipelineId, Failure, Failu use servo_net::image_cache_task::{ImageCacheTask, ImageResponseMsg}; use gfx::font_cache_task::{FontCacheTask}; use servo_net::local_image_cache::{ImageResponder, LocalImageCache}; +use servo_util::bloom::BloomFilter; use servo_util::geometry::Au; use servo_util::geometry; use servo_util::logical_geometry::LogicalPoint; @@ -57,6 +58,7 @@ use servo_util::workqueue::WorkQueue; use std::comm::{channel, Sender, Receiver, Select}; use std::mem; use std::ptr; +use style; use style::{AuthorOrigin, Stylesheet, Stylist}; use style::iter_font_face_rules; use sync::{Arc, Mutex, MutexGuard}; @@ -409,7 +411,12 @@ impl LayoutTask { } // Create a layout context for use in building display lists, hit testing, &c. - fn build_shared_layout_context(&self, rw_data: &LayoutTaskData, reflow_root: &LayoutNode, url: &Url) -> SharedLayoutContext { + fn build_shared_layout_context( + &self, + rw_data: &LayoutTaskData, + reflow_root: &LayoutNode, + url: &Url) + -> SharedLayoutContext { SharedLayoutContext { image_cache: rw_data.local_image_cache.clone(), screen_size: rw_data.screen_size.clone(), @@ -718,7 +725,11 @@ impl LayoutTask { rw_data.screen_size = current_screen_size; // Create a layout context for use throughout the following passes. - let mut shared_layout_ctx = self.build_shared_layout_context(rw_data.deref(), node, &data.url); + let mut shared_layout_ctx = + self.build_shared_layout_context( + rw_data.deref(), + node, + &data.url); let mut layout_root = profile(time::LayoutStyleRecalcCategory, self.time_profiler_chan.clone(), @@ -729,8 +740,11 @@ impl LayoutTask { None => { let layout_ctx = LayoutContext::new(&shared_layout_ctx); let mut applicable_declarations = ApplicableDeclarations::new(); + let mut parent_bf = Some(BloomFilter::new( + style::RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE)); node.recalc_style_for_subtree(&*rw_data.stylist, &layout_ctx, + &mut parent_bf, &mut applicable_declarations, None) } diff --git a/components/layout/parallel.rs b/components/layout/parallel.rs index a2786e8ba91..fbf85053a4f 100644 --- a/components/layout/parallel.rs +++ b/components/layout/parallel.rs @@ -20,12 +20,14 @@ use wrapper::{layout_node_to_unsafe_layout_node, layout_node_from_unsafe_layout_ use wrapper::{ThreadSafeLayoutNode, UnsafeLayoutNode}; use gfx::display_list::OpaqueNode; +use servo_util::bloom::BloomFilter; use servo_util::time::{TimeProfilerChan, profile}; use servo_util::time; use servo_util::workqueue::{WorkQueue, WorkUnit, WorkerProxy}; use std::mem; use std::ptr; use std::sync::atomics::{AtomicInt, Relaxed, SeqCst}; +use style; use style::TNode; #[allow(dead_code)] @@ -213,7 +215,91 @@ impl<'a> ParallelPreorderFlowTraversal for AssignISizesTraversal<'a> { impl<'a> ParallelPostorderFlowTraversal for AssignBSizesAndStoreOverflowTraversal<'a> {} -fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode, +/// A pair of the bloom filter used for css selector matching, and the node to +/// which it applies. This is used to efficiently do `Descendant` selector +/// matches. Thanks to the bloom filter, we can avoid walking up the tree +/// looking for ancestors that aren't there in the majority of cases. +/// +/// As we walk down the DOM tree a task-local bloom filter is built of all the +/// CSS `SimpleSelector`s which are part of a `Descendant` compound selector +/// (i.e. paired with a `Descendant` combinator, in the `next` field of a +/// `CompoundSelector`. +/// +/// Before a `Descendant` selector match is tried, it's compared against the +/// bloom filter. If the bloom filter can exclude it, the selector is quickly +/// rejected. +/// +/// When done styling a node, all selectors previously inserted into the filter +/// are removed. +/// +/// Since a work-stealing queue is used for styling, sometimes, the bloom filter +/// will no longer be the for the parent of the node we're currently on. When +/// this happens, the task local bloom filter will be thrown away and rebuilt. +local_data_key!(style_bloom: (BloomFilter, UnsafeLayoutNode)) + +/// Returns the task local bloom filter. +/// +/// If one does not exist, a new one will be made for you. If it is out of date, +/// it will be thrown out and a new one will be made for you. +fn take_task_local_bloom_filter( + parent_node: Option<LayoutNode>, + layout_context: &LayoutContext) + -> BloomFilter { + + let new_bloom = + |p: Option<LayoutNode>| -> BloomFilter { + let mut bf = BloomFilter::new(style::RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE); + p.map(|p| insert_ancestors_into_bloom_filter(&mut bf, p, layout_context)); + bf + }; + + match (parent_node, style_bloom.replace(None)) { + // Root node. Needs new bloom filter. + (None, _ ) => new_bloom(None), + // No bloom filter for this thread yet. + (Some(p), None) => new_bloom(Some(p)), + // Found cached bloom filter. + (Some(p), Some((bf, old_node))) => { + // Hey, the cached parent is our parent! We can reuse the bloom filter. + if old_node == layout_node_to_unsafe_layout_node(&p) { + bf + // Oh no. the cached parent is stale. I guess we need a new one... + } else { + new_bloom(Some(p)) + } + }, + } +} + +fn put_task_local_bloom_filter(bf: BloomFilter, unsafe_node: &UnsafeLayoutNode) { + match style_bloom.replace(Some((bf, *unsafe_node))) { + None => {}, + Some(_) => fail!("Putting into a never-taken task-local bloom filter"), + } +} + +/// "Ancestors" in this context is inclusive of ourselves. +fn insert_ancestors_into_bloom_filter( + bf: &mut BloomFilter, mut n: LayoutNode, layout_context: &LayoutContext) { + loop { + n.insert_into_bloom_filter(bf); + n = match parent_node(&n, layout_context) { + None => return, + Some(p) => p, + }; + } +} + +fn parent_node<'ln>(node: &LayoutNode<'ln>, layout_context: &LayoutContext) -> Option<LayoutNode<'ln>> { + let opaque_node: OpaqueNode = OpaqueNodeMethods::from_layout_node(node); + if opaque_node == layout_context.shared.reflow_root { + None + } else { + node.parent_node() + } +} + +fn recalc_style_for_node(mut unsafe_layout_node: UnsafeLayoutNode, proxy: &mut WorkerProxy<*const SharedLayoutContext,UnsafeLayoutNode>) { let shared_layout_context = unsafe { &**proxy.user_data() }; let layout_context = LayoutContext::new(shared_layout_context); @@ -230,12 +316,10 @@ fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode, node.initialize_layout_data(layout_context.shared.layout_chan.clone()); // Get the parent node. - let opaque_node: OpaqueNode = OpaqueNodeMethods::from_layout_node(&node); - let parent_opt = if opaque_node == layout_context.shared.reflow_root { - None - } else { - node.parent_node() - }; + let parent_opt = parent_node(&node, &layout_context); + + // Get the style bloom filter. + let bf = take_task_local_bloom_filter(parent_opt, &layout_context); // First, check to see whether we can share a style with someone. let style_sharing_candidate_cache = layout_context.style_sharing_candidate_cache(); @@ -244,6 +328,9 @@ fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode, parent_opt.clone()) }; + // Just needs to be wrapped in an option for `match_node`. + let some_bf = Some(bf); + // Otherwise, match and cascade selectors. match sharing_result { CannotShare(mut shareable) => { @@ -252,7 +339,7 @@ fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode, if node.is_element() { // Perform the CSS selector matching. let stylist = unsafe { &*layout_context.shared.stylist }; - node.match_node(stylist, &mut applicable_declarations, &mut shareable); + node.match_node(stylist, &some_bf, &mut applicable_declarations, &mut shareable); } // Perform the CSS cascade. @@ -285,6 +372,13 @@ fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode, } } + // It can be `None` now. + let mut bf = some_bf; + + // Before running the children, we need to insert our nodes into the bloom + // filter. + bf.as_mut().map(|bf| node.insert_into_bloom_filter(bf)); + // It's *very* important that this block is in a separate scope to the block above, // to avoid a data race that can occur (github issue #2308). The block above issues // a borrow on the node layout data. That borrow must be dropped before the child @@ -299,19 +393,21 @@ fn recalc_style_for_node(unsafe_layout_node: UnsafeLayoutNode, data: layout_node_to_unsafe_layout_node(&kid), }); } - return + } else { + // If we got here, we're a leaf. Start construction of flows for this node. + construct_flows(&mut unsafe_layout_node, &mut bf, &layout_context); } - // If we got here, we're a leaf. Start construction of flows for this node. - construct_flows(unsafe_layout_node, &layout_context) + bf.map(|bf| put_task_local_bloom_filter(bf, &unsafe_layout_node)); } -fn construct_flows(mut unsafe_layout_node: UnsafeLayoutNode, - layout_context: &LayoutContext) { +fn construct_flows<'a>(unsafe_layout_node: &mut UnsafeLayoutNode, + parent_bf: &mut Option<BloomFilter>, + layout_context: &'a LayoutContext<'a>) { loop { // Get a real layout node. let node: LayoutNode = unsafe { - layout_node_from_unsafe_layout_node(&unsafe_layout_node) + layout_node_from_unsafe_layout_node(&*unsafe_layout_node) }; // Construct flows for this node. @@ -340,7 +436,10 @@ fn construct_flows(mut unsafe_layout_node: UnsafeLayoutNode, // If this is the reflow root, we're done. let opaque_node: OpaqueNode = OpaqueNodeMethods::from_layout_node(&node); if layout_context.shared.reflow_root == opaque_node { - break + *parent_bf = None; + break; + } else { + parent_bf.as_mut().map(|parent_bf| node.remove_from_bloom_filter(parent_bf)); } // Otherwise, enqueue the parent. @@ -352,6 +451,8 @@ fn construct_flows(mut unsafe_layout_node: UnsafeLayoutNode, unsafe { match *parent.borrow_layout_data_unchecked() { Some(ref parent_layout_data) => { + *unsafe_layout_node = layout_node_to_unsafe_layout_node(&parent); + let parent_layout_data: &mut LayoutDataWrapper = mem::transmute(parent_layout_data); if parent_layout_data.data .parallel @@ -359,7 +460,6 @@ fn construct_flows(mut unsafe_layout_node: UnsafeLayoutNode, .fetch_sub(1, SeqCst) == 1 { // We were the last child of our parent. Construct flows for our // parent. - unsafe_layout_node = layout_node_to_unsafe_layout_node(&parent) } else { // Get out of here and find another node to work on. break @@ -558,4 +658,3 @@ pub fn build_display_list_for_subtree(root: &mut FlowRef, queue.data = ptr::null() } - diff --git a/components/layout/wrapper.rs b/components/layout/wrapper.rs index 8f948a9a128..bdabc3b5840 100644 --- a/components/layout/wrapper.rs +++ b/components/layout/wrapper.rs @@ -231,6 +231,12 @@ impl<'ln> TNode<LayoutElement<'ln>> for LayoutNode<'ln> { } } + fn tnode_first_child(&self) -> Option<LayoutNode<'ln>> { + unsafe { + self.node.first_child_ref().map(|node| self.new_with_this_lifetime(&node)) + } + } + fn prev_sibling(&self) -> Option<LayoutNode<'ln>> { unsafe { self.node.prev_sibling_ref().map(|node| self.new_with_this_lifetime(&node)) |