aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Cargo.lock8
-rw-r--r--components/layout/block.rs1
-rw-r--r--components/layout/construct.rs13
-rw-r--r--components/layout/css/matching.rs104
-rw-r--r--components/layout/layout_task.rs18
-rw-r--r--components/layout/parallel.rs133
-rw-r--r--components/layout/wrapper.rs6
-rw-r--r--components/script/dom/element.rs2
-rw-r--r--components/script/dom/node.rs10
-rw-r--r--components/style/lib.rs4
-rw-r--r--components/style/node.rs3
-rw-r--r--components/style/selector_matching.rs122
-rw-r--r--components/style/selectors.rs10
-rw-r--r--components/util/bloom.rs398
-rw-r--r--components/util/fnv.rs45
-rw-r--r--components/util/lib.rs4
-rw-r--r--components/util/namespace.rs2
-rw-r--r--components/util/time.rs2
-rw-r--r--components/util/workqueue.rs1
-rw-r--r--ports/cef/Cargo.lock9
20 files changed, 817 insertions, 78 deletions
diff --git a/Cargo.lock b/Cargo.lock
index b79a663c2f8..57f5b658e50 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -409,17 +409,17 @@ source = "git+https://github.com/servo/rust-stb-image#f5022de4ad6bb474a03493d1f2
[[package]]
name = "string_cache"
version = "0.0.0"
-source = "git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a"
+source = "git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289"
dependencies = [
"phf 0.0.0 (git+https://github.com/sfackler/rust-phf#fa5d803428dd760287330571c919c7c5e11b2e1b)",
"phf_mac 0.0.0 (git+https://github.com/sfackler/rust-phf#fa5d803428dd760287330571c919c7c5e11b2e1b)",
- "string_cache_macros 0.0.0 (git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a)",
+ "string_cache_macros 0.0.0 (git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289)",
]
[[package]]
name = "string_cache_macros"
version = "0.0.0"
-source = "git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a"
+source = "git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289"
[[package]]
name = "style"
@@ -451,7 +451,7 @@ version = "0.0.1"
dependencies = [
"azure 0.1.0 (git+https://github.com/servo/rust-azure#9c5567b79d8b87e8ef3b48c5842f453978035d21)",
"geom 0.1.0 (git+https://github.com/servo/rust-geom#2982b770db6e5e3270305e0fd6b8068f6f80a489)",
- "string_cache 0.0.0 (git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a)",
+ "string_cache 0.0.0 (git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289)",
"task_info 0.0.1",
]
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))
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 2150e67f0eb..b0aad2f9bbf 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -801,7 +801,7 @@ impl<'a> ElementMethods for JSRef<'a, Element> {
Err(()) => Err(Syntax),
Ok(ref selectors) => {
let root: &JSRef<Node> = NodeCast::from_ref(self);
- Ok(matches(selectors, root))
+ Ok(matches(selectors, root, &mut None))
}
}
}
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index f419798a110..ee173eee1f2 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -610,7 +610,7 @@ impl<'m, 'n> NodeHelpers<'m, 'n> for JSRef<'n, Node> {
Ok(ref selectors) => {
let root = self.ancestors().last().unwrap_or(self.clone());
for node in root.traverse_preorder() {
- if node.is_element() && matches(selectors, &node) {
+ if node.is_element() && matches(selectors, &node, &mut None) {
let elem: &JSRef<Element> = ElementCast::to_ref(&node).unwrap();
return Ok(Some(Temporary::from_rooted(elem)));
}
@@ -631,7 +631,9 @@ impl<'m, 'n> NodeHelpers<'m, 'n> for JSRef<'n, Node> {
// Step 3.
Ok(ref selectors) => {
nodes = root.traverse_preorder().filter(
- |node| node.is_element() && matches(selectors, node)).collect()
+ // TODO(cgaebel): Is it worth it to build a bloom filter here
+ // (instead of passing `None`)? Probably.
+ |node| node.is_element() && matches(selectors, node, &mut None)).collect()
}
}
let window = window_from_node(self).root();
@@ -1988,6 +1990,10 @@ impl<'a> style::TNode<JSRef<'a, Element>> for JSRef<'a, Node> {
(self as &NodeHelpers).parent_node().map(|node| *node.root())
}
+ fn tnode_first_child(&self) -> Option<JSRef<'a, Node>> {
+ (self as &NodeHelpers).first_child().map(|node| *node.root())
+ }
+
fn prev_sibling(&self) -> Option<JSRef<'a, Node>> {
(self as &NodeHelpers).prev_sibling().map(|node| *node.root())
}
diff --git a/components/style/lib.rs b/components/style/lib.rs
index 869905d4a3f..107889cb57a 100644
--- a/components/style/lib.rs
+++ b/components/style/lib.rs
@@ -31,7 +31,8 @@ extern crate servo_util = "util";
// Public API
pub use stylesheets::{Stylesheet, iter_font_face_rules};
pub use selector_matching::{Stylist, StylesheetOrigin, UserAgentOrigin, AuthorOrigin, UserOrigin};
-pub use selector_matching::{DeclarationBlock, matches};
+pub use selector_matching::{DeclarationBlock, matches,matches_simple_selector};
+pub use selector_matching::{RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE,SELECTOR_WHITESPACE};
pub use properties::{cascade, cascade_anonymous};
pub use properties::{PropertyDeclaration, ComputedValues, computed_values, style_structs};
pub use properties::{PropertyDeclarationBlock, parse_style_attribute}; // Style attributes
@@ -40,6 +41,7 @@ pub use properties::longhands;
pub use node::{TElement, TNode};
pub use selectors::{PseudoElement, Before, After, SelectorList, parse_selector_list_from_str};
pub use selectors::{AttrSelector, NamespaceConstraint, SpecificNamespace, AnyNamespace};
+pub use selectors::{SimpleSelector,LocalNameSelector};
pub use cssparser::{Color, RGBA};
mod stylesheets;
diff --git a/components/style/node.rs b/components/style/node.rs
index cdd7cabf8e7..bd71aa6fd79 100644
--- a/components/style/node.rs
+++ b/components/style/node.rs
@@ -12,6 +12,8 @@ use servo_util::namespace::Namespace;
pub trait TNode<E:TElement> : Clone {
fn parent_node(&self) -> Option<Self>;
+ /// Name is prefixed to avoid a conflict with TLayoutNode.
+ fn tnode_first_child(&self) -> Option<Self>;
fn prev_sibling(&self) -> Option<Self>;
fn next_sibling(&self) -> Option<Self>;
fn is_document(&self) -> bool;
@@ -32,4 +34,3 @@ pub trait TElement {
fn get_enabled_state(&self) -> bool;
fn has_class(&self, name: &str) -> bool;
}
-
diff --git a/components/style/selector_matching.rs b/components/style/selector_matching.rs
index 766e2b8bce1..a0ddf7dd31d 100644
--- a/components/style/selector_matching.rs
+++ b/components/style/selector_matching.rs
@@ -10,6 +10,7 @@ use sync::Arc;
use url::Url;
use servo_util::atom::Atom;
+use servo_util::bloom::BloomFilter;
use servo_util::namespace;
use servo_util::smallvec::VecLike;
use servo_util::sort;
@@ -27,7 +28,7 @@ pub enum StylesheetOrigin {
}
/// The definition of whitespace per CSS Selectors Level 3 § 4.
-static SELECTOR_WHITESPACE: &'static [char] = &[' ', '\t', '\n', '\r', '\x0C'];
+pub static SELECTOR_WHITESPACE: &'static [char] = &[' ', '\t', '\n', '\r', '\x0C'];
/// Map node attributes to Rules whose last simple selector starts with them.
///
@@ -83,6 +84,7 @@ impl SelectorMap {
V:VecLike<DeclarationBlock>>(
&self,
node: &N,
+ parent_bf: &Option<BloomFilter>,
matching_rules_list: &mut V,
shareable: &mut bool) {
if self.empty {
@@ -95,6 +97,7 @@ impl SelectorMap {
match element.get_id() {
Some(id) => {
SelectorMap::get_matching_rules_from_hash(node,
+ parent_bf,
&self.id_hash,
&id,
matching_rules_list,
@@ -108,10 +111,11 @@ impl SelectorMap {
// FIXME: Store classes pre-split as atoms to make the loop below faster.
for class in class_attr.split(SELECTOR_WHITESPACE) {
SelectorMap::get_matching_rules_from_hash(node,
- &self.class_hash,
- &Atom::from_slice(class),
- matching_rules_list,
- shareable);
+ parent_bf,
+ &self.class_hash,
+ &Atom::from_slice(class),
+ matching_rules_list,
+ shareable);
}
}
None => {}
@@ -123,12 +127,14 @@ impl SelectorMap {
&self.local_name_hash
};
SelectorMap::get_matching_rules_from_hash(node,
+ parent_bf,
local_name_hash,
element.get_local_name(),
matching_rules_list,
shareable);
SelectorMap::get_matching_rules(node,
+ parent_bf,
self.universal_rules.as_slice(),
matching_rules_list,
shareable);
@@ -145,13 +151,14 @@ impl SelectorMap {
N:TNode<E>,
V:VecLike<DeclarationBlock>>(
node: &N,
+ parent_bf: &Option<BloomFilter>,
hash: &HashMap<Atom, Vec<Rule>>,
key: &Atom,
matching_rules: &mut V,
shareable: &mut bool) {
match hash.find(key) {
Some(rules) => {
- SelectorMap::get_matching_rules(node, rules.as_slice(), matching_rules, shareable)
+ SelectorMap::get_matching_rules(node, parent_bf, rules.as_slice(), matching_rules, shareable)
}
None => {}
}
@@ -162,11 +169,12 @@ impl SelectorMap {
N:TNode<E>,
V:VecLike<DeclarationBlock>>(
node: &N,
+ parent_bf: &Option<BloomFilter>,
rules: &[Rule],
matching_rules: &mut V,
shareable: &mut bool) {
for rule in rules.iter() {
- if matches_compound_selector(&*rule.selector, node, shareable) {
+ if matches_compound_selector(&*rule.selector, node, parent_bf, shareable) {
matching_rules.vec_push(rule.declarations.clone());
}
}
@@ -247,6 +255,11 @@ impl SelectorMap {
}
}
+// The bloom filter for descendant CSS selectors will have a <1% false
+// positive rate until it has this many selectors in it, then it will
+// rapidly increase.
+pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: uint = 4096;
+
pub struct Stylist {
element_map: PerPseudoElementSelectorMap,
before_map: PerPseudoElementSelectorMap,
@@ -336,6 +349,7 @@ impl Stylist {
V:VecLike<DeclarationBlock>>(
&self,
element: &N,
+ parent_bf: &Option<BloomFilter>,
style_attribute: Option<&PropertyDeclarationBlock>,
pseudo_element: Option<PseudoElement>,
applicable_declarations: &mut V)
@@ -354,10 +368,11 @@ impl Stylist {
// Step 1: Normal rules.
map.user_agent.normal.get_all_matching_rules(element,
+ parent_bf,
applicable_declarations,
&mut shareable);
- map.user.normal.get_all_matching_rules(element, applicable_declarations, &mut shareable);
- map.author.normal.get_all_matching_rules(element, applicable_declarations, &mut shareable);
+ map.user.normal.get_all_matching_rules(element, parent_bf, applicable_declarations, &mut shareable);
+ map.author.normal.get_all_matching_rules(element, parent_bf, applicable_declarations, &mut shareable);
// Step 2: Normal style attributes.
style_attribute.map(|sa| {
@@ -367,6 +382,7 @@ impl Stylist {
// Step 3: Author-supplied `!important` rules.
map.author.important.get_all_matching_rules(element,
+ parent_bf,
applicable_declarations,
&mut shareable);
@@ -378,9 +394,11 @@ impl Stylist {
// Step 5: User and UA `!important` rules.
map.user.important.get_all_matching_rules(element,
+ parent_bf,
applicable_declarations,
&mut shareable);
map.user_agent.important.get_all_matching_rules(element,
+ parent_bf,
applicable_declarations,
&mut shareable);
@@ -449,13 +467,12 @@ impl DeclarationBlock {
}
}
-pub fn matches<E:TElement, N:TNode<E>>(selector_list: &SelectorList, element: &N) -> bool {
+pub fn matches<E:TElement, N:TNode<E>>(selector_list: &SelectorList, element: &N, parent_bf: &Option<BloomFilter>) -> bool {
get_selector_list_selectors(selector_list).iter().any(|selector|
selector.pseudo_element.is_none() &&
- matches_compound_selector(&*selector.compound_selectors, element, &mut false))
+ matches_compound_selector(&*selector.compound_selectors, element, parent_bf, &mut false))
}
-
/// Determines whether the given element matches the given single or compound selector.
///
/// NB: If you add support for any new kinds of selectors to this routine, be sure to set
@@ -466,9 +483,10 @@ fn matches_compound_selector<E:TElement,
N:TNode<E>>(
selector: &CompoundSelector,
element: &N,
+ parent_bf: &Option<BloomFilter>,
shareable: &mut bool)
-> bool {
- match matches_compound_selector_internal(selector, element, shareable) {
+ match matches_compound_selector_internal(selector, element, parent_bf, shareable) {
Matched => true,
_ => false
}
@@ -523,17 +541,82 @@ enum SelectorMatchingResult {
NotMatchedGlobally,
}
+/// Quickly figures out whether or not the compound selector is worth doing more
+/// work on. If the simple selectors don't match, or there's a child selector
+/// that does not appear in the bloom parent bloom filter, we can exit early.
+fn can_fast_reject<E: TElement, N: TNode<E>>(
+ mut selector: &CompoundSelector,
+ element: &N,
+ parent_bf: &Option<BloomFilter>,
+ shareable: &mut bool) -> Option<SelectorMatchingResult> {
+ if !selector.simple_selectors.iter().all(|simple_selector| {
+ matches_simple_selector(simple_selector, element, shareable) }) {
+ return Some(NotMatchedAndRestartFromClosestLaterSibling);
+ }
+
+ let bf: &BloomFilter =
+ match *parent_bf {
+ None => return None,
+ Some(ref bf) => bf,
+ };
+
+ // See if the bloom filter can exclude any of the descendant selectors, and
+ // reject if we can.
+ loop {
+ match selector.next {
+ None => break,
+ Some((ref cs, Descendant)) => selector = &**cs,
+ Some((ref cs, _)) => {
+ selector = &**cs;
+ continue;
+ }
+ };
+
+ for ss in selector.simple_selectors.iter() {
+ match *ss {
+ LocalNameSelector(LocalNameSelector { ref name, ref lower_name }) => {
+ if bf.definitely_excludes(name)
+ && bf.definitely_excludes(lower_name) {
+ return Some(NotMatchedGlobally);
+ }
+ },
+ NamespaceSelector(ref namespace) => {
+ if bf.definitely_excludes(namespace) {
+ return Some(NotMatchedGlobally);
+ }
+ },
+ IDSelector(ref id) => {
+ if bf.definitely_excludes(id) {
+ return Some(NotMatchedGlobally);
+ }
+ },
+ ClassSelector(ref class) => {
+ if bf.definitely_excludes(&class.as_slice()) {
+ return Some(NotMatchedGlobally);
+ }
+ },
+ _ => {},
+ }
+ }
+
+ }
+
+ // Can't fast reject.
+ return None;
+}
+
fn matches_compound_selector_internal<E:TElement,
N:TNode<E>>(
selector: &CompoundSelector,
element: &N,
+ parent_bf: &Option<BloomFilter>,
shareable: &mut bool)
-> SelectorMatchingResult {
- if !selector.simple_selectors.iter().all(|simple_selector| {
- matches_simple_selector(simple_selector, element, shareable)
- }) {
- return NotMatchedAndRestartFromClosestLaterSibling
- }
+ match can_fast_reject(selector, element, parent_bf, shareable) {
+ None => {},
+ Some(result) => return result,
+ };
+
match selector.next {
None => Matched,
Some((ref next_selector, combinator)) => {
@@ -557,6 +640,7 @@ fn matches_compound_selector_internal<E:TElement,
if node.is_element() {
let result = matches_compound_selector_internal(&**next_selector,
&node,
+ parent_bf,
shareable);
match (result, combinator) {
// Return the status immediately.
@@ -596,7 +680,7 @@ fn matches_compound_selector_internal<E:TElement,
/// will almost certainly break as nodes will start mistakenly sharing styles. (See the code in
/// `main/css/matching.rs`.)
#[inline]
-fn matches_simple_selector<E:TElement,
+pub fn matches_simple_selector<E:TElement,
N:TNode<E>>(
selector: &SimpleSelector,
element: &N,
diff --git a/components/style/selectors.rs b/components/style/selectors.rs
index 44b098fa329..c398c09877e 100644
--- a/components/style/selectors.rs
+++ b/components/style/selectors.rs
@@ -31,7 +31,7 @@ pub struct Selector {
pub specificity: u32,
}
-#[deriving(PartialEq, Clone)]
+#[deriving(Eq, PartialEq, Clone, Hash)]
pub enum PseudoElement {
Before,
After,
@@ -54,7 +54,7 @@ pub enum Combinator {
LaterSibling, // ~
}
-#[deriving(PartialEq, Clone)]
+#[deriving(Eq, PartialEq, Clone, Hash)]
pub enum SimpleSelector {
IDSelector(Atom),
ClassSelector(Atom),
@@ -92,20 +92,20 @@ pub enum SimpleSelector {
// ...
}
-#[deriving(PartialEq, Clone)]
+#[deriving(Eq, PartialEq, Clone, Hash)]
pub struct LocalNameSelector {
pub name: Atom,
pub lower_name: Atom,
}
-#[deriving(PartialEq, Clone)]
+#[deriving(Eq, PartialEq, Clone, Hash)]
pub struct AttrSelector {
pub name: String,
pub lower_name: String,
pub namespace: NamespaceConstraint,
}
-#[deriving(PartialEq, Clone)]
+#[deriving(Eq, PartialEq, Clone, Hash)]
pub enum NamespaceConstraint {
AnyNamespace,
SpecificNamespace(Namespace),
diff --git a/components/util/bloom.rs b/components/util/bloom.rs
new file mode 100644
index 00000000000..0019092663f
--- /dev/null
+++ b/components/util/bloom.rs
@@ -0,0 +1,398 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Simple counting bloom filters.
+
+extern crate rand;
+
+use fnv::{FnvState, hash};
+use rand::Rng;
+use std::hash::Hash;
+use std::iter;
+use std::num;
+use std::uint;
+
+// Just a quick and dirty xxhash embedding.
+
+/// A counting bloom filter.
+///
+/// A bloom filter is a probabilistic data structure which allows you to add and
+/// remove elements from a set, query the set for whether it may contain an
+/// element or definitely exclude it, and uses much less ram than an equivalent
+/// hashtable.
+#[deriving(Clone)]
+pub struct BloomFilter {
+ buf: Vec<uint>,
+ number_of_insertions: uint,
+}
+
+// Here's where some of the magic numbers came from:
+//
+// m = number of elements in the filter
+// n = size of the filter
+// k = number of hash functions
+//
+// p = Pr[false positive] = 0.01 false positive rate
+//
+// if we have an estimation of the number of elements in the bloom filter, we
+// know m.
+//
+// p = (1 - exp(-kn/m))^k
+// k = (m/n)ln2
+// lnp = -(m/n)(ln2)^2
+// m = -nlnp/(ln2)^2
+// => n = -m(ln2)^2/lnp
+// ~= 10*m
+//
+// k = (m/n)ln2 = 10ln2 ~= 7
+
+static NUMBER_OF_HASHES: uint = 7;
+
+static BITS_PER_BUCKET: uint = 4;
+static BUCKETS_PER_WORD: uint = uint::BITS / BITS_PER_BUCKET;
+
+/// Returns a tuple of (array index, lsr shift amount) to get to the bits you
+/// need. Don't forget to mask with 0xF!
+fn bucket_index_to_array_index(bucket_index: uint) -> (uint, uint) {
+ let arr_index = bucket_index / BUCKETS_PER_WORD;
+ let shift_amount = (bucket_index % BUCKETS_PER_WORD) * BITS_PER_BUCKET;
+ (arr_index, shift_amount)
+}
+
+// Key Stretching
+// ==============
+//
+// Siphash is expensive. Instead of running it `NUMBER_OF_HASHES`, which would
+// be a pretty big hit on performance, we just use it to see a non-cryptographic
+// random number generator. This stretches the hash to get us our
+// `NUMBER_OF_HASHES` array indicies.
+//
+// A hash is a `u64` and comes from SipHash.
+// A shash is a `uint` stretched hash which comes from the XorShiftRng.
+
+fn to_rng(hash: u64) -> rand::XorShiftRng {
+ let bottom = (hash & 0xFFFFFFFF) as u32;
+ let top = ((hash >> 32) & 0xFFFFFFFF) as u32;
+ rand::SeedableRng::from_seed([ 0x97830e05, 0x113ba7bb, bottom, top ])
+}
+
+fn stretch<'a>(r: &'a mut rand::XorShiftRng)
+ -> iter::Take<rand::Generator<'a, uint, rand::XorShiftRng>> {
+ r.gen_iter().take(NUMBER_OF_HASHES)
+}
+
+impl BloomFilter {
+ /// This bloom filter is tuned to have ~1% false positive rate. In exchange
+ /// for this guarantee, you need to have a reasonable upper bound on the
+ /// number of elements that will ever be inserted into it. If you guess too
+ /// low, your false positive rate will suffer. If you guess too high, you'll
+ /// use more memory than is really necessary.
+ pub fn new(expected_number_of_insertions: uint) -> BloomFilter {
+ let size_in_buckets = 10 * expected_number_of_insertions;
+
+ let size_in_words = size_in_buckets / BUCKETS_PER_WORD;
+
+ let nonzero_size = if size_in_words == 0 { 1 } else { size_in_words };
+
+ let num_words =
+ num::checked_next_power_of_two(nonzero_size)
+ .unwrap();
+
+ BloomFilter {
+ buf: Vec::from_elem(num_words, 0),
+ number_of_insertions: 0,
+ }
+ }
+
+ /// Since the array length must be a power of two, this will return a
+ /// bitmask that can be `&`ed with a number to bring it into the range of
+ /// the array.
+ fn mask(&self) -> uint {
+ (self.buf.len()*BUCKETS_PER_WORD) - 1 // guaranteed to be a power of two
+ }
+
+ /// Converts a stretched hash into a bucket index.
+ fn shash_to_bucket_index(&self, shash: uint) -> uint {
+ shash & self.mask()
+ }
+
+ /// Converts a stretched hash into an array and bit index. See the comment
+ /// on `bucket_index_to_array_index` for details about the return value.
+ fn shash_to_array_index(&self, shash: uint) -> (uint, uint) {
+ bucket_index_to_array_index(self.shash_to_bucket_index(shash))
+ }
+
+ /// Gets the value at a given bucket.
+ fn bucket_get(&self, a_idx: uint, shift_amount: uint) -> uint {
+ let array_val = self.buf[a_idx];
+ (array_val >> shift_amount) & 0xF
+ }
+
+ /// Sets the value at a given bucket. This will not bounds check, but that's
+ /// ok because you've called `bucket_get` first, anyhow.
+ fn bucket_set(&mut self, a_idx: uint, shift_amount: uint, new_val: uint) {
+ // We can avoid bounds checking here since in order to do a bucket_set
+ // we have to had done a `bucket_get` at the same index for it to make
+ // sense.
+ let old_val = self.buf.as_mut_slice().get_mut(a_idx).unwrap();
+ let mask = (1 << BITS_PER_BUCKET) - 1; // selects the right-most bucket
+ let select_in_bucket = mask << shift_amount; // selects the correct bucket
+ let select_out_of_bucket = !select_in_bucket; // selects everything except the correct bucket
+ let new_array_val = (new_val << shift_amount) // move the new_val into the right spot
+ | (*old_val & select_out_of_bucket); // mask out the old value, and or it with the new one
+ *old_val = new_array_val;
+ }
+
+ /// Insert a stretched hash into the bloom filter, remembering to saturate
+ /// the counter instead of overflowing.
+ fn insert_shash(&mut self, shash: uint) {
+ let (a_idx, shift_amount) = self.shash_to_array_index(shash);
+ let b_val = self.bucket_get(a_idx, shift_amount);
+
+
+ // saturate the count.
+ if b_val == 0xF {
+ return;
+ }
+
+ let new_val = b_val + 1;
+
+ self.bucket_set(a_idx, shift_amount, new_val);
+ }
+
+ /// Insert a hashed value into the bloom filter.
+ fn insert_hashed(&mut self, hash: u64) {
+ self.number_of_insertions += 1;
+ for h in stretch(&mut to_rng(hash)) {
+ self.insert_shash(h);
+ }
+ }
+
+ /// Inserts a value into the bloom filter. Note that the bloom filter isn't
+ /// parameterized over the values it holds. That's because it can hold
+ /// values of different types, as long as it can get a hash out of them.
+ pub fn insert<H: Hash<FnvState>>(&mut self, h: &H) {
+ self.insert_hashed(hash(h))
+ }
+
+ /// Removes a stretched hash from the bloom filter, taking care not to
+ /// decrememnt saturated counters.
+ ///
+ /// It is an error to remove never-inserted elements.
+ fn remove_shash(&mut self, shash: uint) {
+ let (a_idx, shift_amount) = self.shash_to_array_index(shash);
+ let b_val = self.bucket_get(a_idx, shift_amount);
+ assert!(b_val != 0, "Removing an element that was never inserted.");
+
+ // can't do anything if the counter saturated.
+ if b_val == 0xF { return; }
+
+ self.bucket_set(a_idx, shift_amount, b_val - 1);
+ }
+
+ /// Removes a hashed value from the bloom filter.
+ fn remove_hashed(&mut self, hash: u64) {
+ self.number_of_insertions -= 1;
+ for h in stretch(&mut to_rng(hash)) {
+ self.remove_shash(h);
+ }
+ }
+
+ /// Removes a value from the bloom filter.
+ ///
+ /// Be careful of adding and removing lots of elements, especially for
+ /// long-lived bloom filters. The counters in each bucket will saturate if
+ /// 16 or more elements hash to it, and then stick there. This will hurt
+ /// your false positive rate. To fix this, you might consider refreshing the
+ /// bloom filter by `clear`ing it, and then reinserting elements at regular,
+ /// long intervals.
+ ///
+ /// It is an error to remove never-inserted elements.
+ pub fn remove<H: Hash<FnvState>>(&mut self, h: &H) {
+ self.remove_hashed(hash(h))
+ }
+
+ /// Returns `true` if the bloom filter cannot possibly contain the given
+ /// stretched hash.
+ fn definitely_excludes_shash(&self, shash: uint) -> bool {
+ let (a_idx, shift_amount) = self.shash_to_array_index(shash);
+ self.bucket_get(a_idx, shift_amount) == 0
+ }
+
+ /// A hash is definitely excluded iff none of the stretched hashes are in
+ /// the bloom filter.
+ fn definitely_excludes_hashed(&self, hash: u64) -> bool {
+ let mut ret = false;
+
+ // Doing `.any` is slower than this branch-free version.
+ for shash in stretch(&mut to_rng(hash)) {
+ ret |= self.definitely_excludes_shash(shash);
+ }
+
+ ret
+ }
+
+ /// A bloom filter can tell you whether or not a value has definitely never
+ /// been inserted. Note that bloom filters can give false positives.
+ pub fn definitely_excludes<H: Hash<FnvState>>(&self, h: &H) -> bool {
+ self.definitely_excludes_hashed(hash(h))
+ }
+
+ /// A bloom filter can tell you if an element /may/ be in it. It cannot be
+ /// certain. But, assuming correct usage, this query will have a low false
+ /// positive rate.
+ pub fn may_include<H: Hash<FnvState>>(&self, h: &H) -> bool {
+ !self.definitely_excludes(h)
+ }
+
+ /// Returns the number of elements ever inserted into the bloom filter - the
+ /// number of elements removed.
+ pub fn number_of_insertions(&self) -> uint {
+ self.number_of_insertions
+ }
+
+ /// Returns the number of bytes of memory the bloom filter uses.
+ pub fn size(&self) -> uint {
+ self.buf.len() * uint::BYTES
+ }
+
+ /// Removes all elements from the bloom filter. This is both more efficient
+ /// and has better false-positive properties than repeatedly calling `remove`
+ /// on every element.
+ pub fn clear(&mut self) {
+ self.number_of_insertions = 0;
+ for x in self.buf.as_mut_slice().mut_iter() {
+ *x = 0u;
+ }
+ }
+}
+
+#[test]
+fn create_and_insert_some_stuff() {
+ use std::iter::range;
+
+ let mut bf = BloomFilter::new(1000);
+
+ for i in range(0u, 1000) {
+ bf.insert(&i);
+ }
+
+ assert_eq!(bf.number_of_insertions(), 1000);
+
+ for i in range(0u, 1000) {
+ assert!(bf.may_include(&i));
+ }
+
+ let false_positives =
+ range(1001u, 2000).filter(|i| bf.may_include(&i)).count();
+
+ assert!(false_positives < 10) // 1%.
+
+ for i in range(0u, 100) {
+ bf.remove(&i);
+ }
+
+ assert_eq!(bf.number_of_insertions(), 900);
+
+ for i in range(100u, 1000) {
+ assert!(bf.may_include(&i));
+ }
+
+ let false_positives = range(0u, 100).filter(|i| bf.may_include(&i)).count();
+
+ assert!(false_positives < 2); // 2%.
+
+ bf.clear();
+
+ assert_eq!(bf.number_of_insertions(), 0);
+
+ for i in range(0u, 2000) {
+ assert!(bf.definitely_excludes(&i));
+ }
+}
+
+#[cfg(test)]
+mod bench {
+ extern crate test;
+
+ use std::hash::hash;
+ use std::iter;
+ use super::BloomFilter;
+
+ #[bench]
+ fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
+ b.iter(|| {
+ let mut bf = BloomFilter::new(1000);
+ for i in iter::range(0u, 1000) {
+ bf.insert(&i);
+ }
+ for i in iter::range(0u, 100) {
+ bf.remove(&i);
+ }
+ for i in iter::range(100u, 200) {
+ test::black_box(bf.may_include(&i));
+ }
+ });
+ }
+
+ #[bench]
+ fn may_include(b: &mut test::Bencher) {
+ let mut bf = BloomFilter::new(1000);
+
+ for i in iter::range(0u, 1000) {
+ bf.insert(&i);
+ }
+
+ let mut i = 0u;
+
+ b.bench_n(1000, |b| {
+ b.iter(|| {
+ test::black_box(bf.may_include(&i));
+ i += 1;
+ });
+ });
+ }
+
+ #[bench]
+ fn insert(b: &mut test::Bencher) {
+ let mut bf = BloomFilter::new(1000);
+
+ b.bench_n(1000, |b| {
+ let mut i = 0u;
+
+ b.iter(|| {
+ test::black_box(bf.insert(&i));
+ i += 1;
+ });
+ });
+ }
+
+ #[bench]
+ fn remove(b: &mut test::Bencher) {
+ let mut bf = BloomFilter::new(1000);
+ for i in range(0u, 1000) {
+ bf.insert(&i);
+ }
+
+ b.bench_n(1000, |b| {
+ let mut i = 0u;
+
+ b.iter(|| {
+ bf.remove(&i);
+ i += 1;
+ });
+ });
+
+ test::black_box(bf.may_include(&0u));
+ }
+
+ #[bench]
+ fn hash_a_uint(b: &mut test::Bencher) {
+ let mut i = 0u;
+ b.iter(|| {
+ test::black_box(hash(&i));
+ i += 1;
+ })
+ }
+}
diff --git a/components/util/fnv.rs b/components/util/fnv.rs
new file mode 100644
index 00000000000..a14f3ea2bec
--- /dev/null
+++ b/components/util/fnv.rs
@@ -0,0 +1,45 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! This file stolen wholesale from rustc/src/librustc/util/nodemap.rs
+
+pub use std::hash::{Hash, Hasher, Writer};
+
+/// A speedy hash algorithm for node ids and def ids. The hashmap in
+/// libcollections by default uses SipHash which isn't quite as speedy as we
+/// want. In the compiler we're not really worried about DOS attempts, so we
+/// just default to a non-cryptographic hash.
+///
+/// This uses FNV hashing, as described here:
+/// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+#[deriving(Clone)]
+pub struct FnvHasher;
+
+pub struct FnvState(u64);
+
+impl Hasher<FnvState> for FnvHasher {
+ fn hash<T: Hash<FnvState>>(&self, t: &T) -> u64 {
+ let mut state = FnvState(0xcbf29ce484222325);
+ t.hash(&mut state);
+ let FnvState(ret) = state;
+ return ret;
+ }
+}
+
+impl Writer for FnvState {
+ fn write(&mut self, bytes: &[u8]) {
+ let FnvState(mut hash) = *self;
+ for byte in bytes.iter() {
+ hash = hash ^ (*byte as u64);
+ hash = hash * 0x100000001b3;
+ }
+ *self = FnvState(hash);
+ }
+}
+
+#[inline(always)]
+pub fn hash<T: Hash<FnvState>>(t: &T) -> u64 {
+ let s = FnvHasher;
+ s.hash(t)
+}
diff --git a/components/util/lib.rs b/components/util/lib.rs
index 0d59b21124d..0c186fdb690 100644
--- a/components/util/lib.rs
+++ b/components/util/lib.rs
@@ -2,7 +2,7 @@
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-#![feature(macro_rules,unsafe_destructor)]
+#![feature(default_type_params,macro_rules,unsafe_destructor)]
#![deny(unused_imports, unused_variable)]
@@ -29,8 +29,10 @@ extern crate std_time = "time";
extern crate string_cache;
pub mod atom;
+pub mod bloom;
pub mod cache;
pub mod debug_utils;
+pub mod fnv;
pub mod geometry;
pub mod logical_geometry;
pub mod memory;
diff --git a/components/util/namespace.rs b/components/util/namespace.rs
index 1f32ae83017..8824accae00 100644
--- a/components/util/namespace.rs
+++ b/components/util/namespace.rs
@@ -2,7 +2,7 @@
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-#[deriving(PartialEq, Clone, Encodable)]
+#[deriving(Eq, PartialEq, Clone, Encodable, Hash)]
pub enum Namespace {
Null,
HTML,
diff --git a/components/util/time.rs b/components/util/time.rs
index 4f282aa2648..bb483ca2a99 100644
--- a/components/util/time.rs
+++ b/components/util/time.rs
@@ -38,6 +38,7 @@ pub enum TimeProfilerCategory {
CompositingCategory,
LayoutQueryCategory,
LayoutPerformCategory,
+ LayoutMaxSelectorMatchesCategory,
LayoutStyleRecalcCategory,
LayoutSelectorMatchCategory,
LayoutTreeBuilderCategory,
@@ -66,6 +67,7 @@ impl TimeProfilerCategory {
buckets.insert(CompositingCategory, vec!());
buckets.insert(LayoutQueryCategory, vec!());
buckets.insert(LayoutPerformCategory, vec!());
+ buckets.insert(LayoutMaxSelectorMatchesCategory, vec!());
buckets.insert(LayoutStyleRecalcCategory, vec!());
buckets.insert(LayoutSelectorMatchCategory, vec!());
buckets.insert(LayoutTreeBuilderCategory, vec!());
diff --git a/components/util/workqueue.rs b/components/util/workqueue.rs
index 5b27b4a5dab..f7823448243 100644
--- a/components/util/workqueue.rs
+++ b/components/util/workqueue.rs
@@ -288,4 +288,3 @@ impl<QueueData: Send, WorkData: Send> WorkQueue<QueueData, WorkData> {
}
}
}
-
diff --git a/ports/cef/Cargo.lock b/ports/cef/Cargo.lock
index dad6d3e58d2..89de2206488 100644
--- a/ports/cef/Cargo.lock
+++ b/ports/cef/Cargo.lock
@@ -445,17 +445,17 @@ source = "git+https://github.com/servo/rust-stb-image#f5022de4ad6bb474a03493d1f2
[[package]]
name = "string_cache"
version = "0.0.0"
-source = "git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a"
+source = "git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289"
dependencies = [
"phf 0.0.0 (git+https://github.com/sfackler/rust-phf#fa5d803428dd760287330571c919c7c5e11b2e1b)",
"phf_mac 0.0.0 (git+https://github.com/sfackler/rust-phf#fa5d803428dd760287330571c919c7c5e11b2e1b)",
- "string_cache_macros 0.0.0 (git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a)",
+ "string_cache_macros 0.0.0 (git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289)",
]
[[package]]
name = "string_cache_macros"
version = "0.0.0"
-source = "git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a"
+source = "git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289"
[[package]]
name = "style"
@@ -487,7 +487,7 @@ version = "0.0.1"
dependencies = [
"azure 0.1.0 (git+https://github.com/servo/rust-azure#9c5567b79d8b87e8ef3b48c5842f453978035d21)",
"geom 0.1.0 (git+https://github.com/servo/rust-geom#2982b770db6e5e3270305e0fd6b8068f6f80a489)",
- "string_cache 0.0.0 (git+https://github.com/servo/string-cache#6d5a6669d05fcc20fe0436a7f9a63310e2bc522a)",
+ "string_cache 0.0.0 (git+https://github.com/servo/string-cache#3e5a5178088729772d95fe8f1450511497e08289)",
"task_info 0.0.1",
]
@@ -495,4 +495,3 @@ dependencies = [
name = "xlib"
version = "0.1.0"
source = "git+https://github.com/servo/rust-xlib#79904fb42ff8a0e888f70fae336fbf6c11f1e6c8"
-
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-20 04:17:51 +0000