Struct style::bloom::StyleBloom

pub struct StyleBloom<E: TElement> {
    filter: AtomicRefMut<'static, BloomFilter>,
    elements: SmallVec<[PushedElement<E>; 16]>,
    pushed_hashes: SmallVec<[u32; 64]>,
}

A struct that allows us to fast-reject deep descendant selectors avoiding selector-matching.

This is implemented using a counting bloom filter, and it’s a standard optimization. See Gecko’s AncestorFilter, and Blink’s and WebKit’s SelectorFilter.

The constraints for Servo’s style system are a bit different compared to traditional style systems given Servo does a parallel breadth-first traversal instead of a sequential depth-first traversal.

This implies that we need to track a bit more state than other browsers to ensure we’re doing the correct thing during the traversal, and being able to apply this optimization effectively.

Concretely, we have a bloom filter instance per worker thread, and we track the current DOM depth in order to find a common ancestor when it doesn’t match the previous element we’ve styled.

This is usually a pretty fast operation (we use to be one level deeper than the previous one), but in the case of work-stealing, we may needed to push and pop multiple elements.

See the insert_parents_recovering, where most of the magic happens.

Regarding thread-safety, this struct is safe because:

• We clear this after a restyle.
• The DOM shape and attributes (and every other thing we access here) are immutable during a restyle.

Fields

filter: AtomicRefMut<'static, BloomFilter>

A handle to the bloom filter from the thread upon which this StyleBloom was created. We use AtomicRefCell so that this is all |Send|, which allows StyleBloom to live in ThreadLocalStyleContext, which is dropped from the parent thread.

elements: SmallVec<[PushedElement<E>; 16]>

The stack of elements that this bloom filter contains, along with the number of hashes pushed for each element.

pushed_hashes: SmallVec<[u32; 64]>

Stack of hashes that have been pushed onto this filter.

Implementations

impl<E: TElement> StyleBloom<E>

pub fn new() -> Self

Create an empty StyleBloom. Because StyleBloom acquires the thread- local filter buffer, creating multiple live StyleBloom instances at the same time on the same thread will panic.

pub fn filter(&self) -> &BloomFilter

Return the bloom filter used properly by the selectors crate.

pub fn push(&mut self, element: E)

Push an element to the bloom filter, knowing that it’s a child of the last element parent.

fn push_internal(&mut self, element: E)

Same as push, but without asserting, in order to use it from rebuild.

fn pop(&mut self) -> Option<E>

Pop the last element in the bloom filter and return it.

pub fn matching_depth(&self) -> usize

Returns the DOM depth of elements that can be correctly matched against the bloom filter (that is, the number of elements in our list).

pub fn clear(&mut self)

Clears the bloom filter.

pub fn rebuild(&mut self, element: E)

Rebuilds the bloom filter up to the parent of the given element.

pub fn assert_complete(&self, element: E)

In debug builds, asserts that all the parents of element are in the bloom filter.

Goes away in release builds.

pub fn current_parent(&self) -> Option<E>

Get the element that represents the chain of things inserted into the filter right now. That chain is the given element (if any) and its ancestors.

pub fn insert_parents_recovering(&mut self, element: E, element_depth: usize)

Insert the parents of an element in the bloom filter, trying to recover the filter if the last element inserted doesn’t match.

Gets the element depth in the dom, to make it efficient, or if not provided always rebuilds the filter from scratch.

Returns the new bloom filter depth, that the traversal code is responsible to keep around if it wants to get an effective filter.

Trait Implementations

impl<E: TElement> Drop for StyleBloom<E>

fn drop(&mut self)

Executes the destructor for this type.