author Emilio Cobos Álvarez <>
Wed, 10 Aug 2016 21:02:30 -0500
changeset 368499 48d70a3b372b6eefc472d3ac777bc9fd47b82343
parent 368408 4931c9df27ee3f3eb19d1a7a30a93c5c81e637b2
child 368541 53148dde6135ef48a1035b82c1b5dfbcbc77f79f
permissions -rw-r--r--
servo: Merge #12757 - stylo: Stop restyling display: none elements, remove the has_changed hack that made us use ReconstructFrame unconditionally (from emilio:stylo); r=bholley,pcwalton <!-- Please describe your changes on the following line: --> --- <!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: --> - [x] `./mach build -d` does not report any errors - [x] `./mach test-tidy` does not report any errors <!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. --> r? @bholley Source-Repo: Source-Revision: 1b2450339c40dbcb65e94a346ea434d45f0edf90

/* 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 */

//! Implements parallel traversal over the DOM tree.
//! This code is highly unsafe. Keep this file small and easy to audit.


use dom::{OpaqueNode, TNode, UnsafeNode};
use std::mem;
use std::sync::atomic::Ordering;
use traversal::{RestyleResult, DomTraversalContext};
use workqueue::{WorkQueue, WorkUnit, WorkerProxy};

fn static_assertion(node: UnsafeNode) {
    unsafe {
        let _: UnsafeNodeList = mem::transmute(node);

pub type UnsafeNodeList = (Box<Vec<UnsafeNode>>, OpaqueNode);

pub const CHUNK_SIZE: usize = 64;

pub struct WorkQueueData(usize, usize);

pub fn run_queue_with_custom_work_data_type<To, F, SharedContext: Sync>(
        queue: &mut WorkQueue<SharedContext, WorkQueueData>,
        callback: F,
        shared: &SharedContext)
        where To: 'static + Send, F: FnOnce(&mut WorkQueue<SharedContext, To>) {
    let queue: &mut WorkQueue<SharedContext, To> = unsafe {

pub fn traverse_dom<N, C>(root: N,
                          queue_data: &C::SharedContext,
                          queue: &mut WorkQueue<C::SharedContext, WorkQueueData>)
                          where N: TNode, C: DomTraversalContext<N> {
    run_queue_with_custom_work_data_type(queue, |queue| {
        queue.push(WorkUnit {
            fun: top_down_dom::<N, C>,
            data: (Box::new(vec![root.to_unsafe()]), root.opaque()),
    }, queue_data);

/// A parallel top-down DOM traversal.
fn top_down_dom<N, C>(unsafe_nodes: UnsafeNodeList,
                      proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>)
                      where N: TNode, C: DomTraversalContext<N> {
    let context = C::new(proxy.user_data(), unsafe_nodes.1);

    let mut discovered_child_nodes = vec![];
    for unsafe_node in *unsafe_nodes.0 {
        // Get a real layout node.
        let node = unsafe { N::from_unsafe(&unsafe_node) };

        if !context.should_process(node) {

        // Possibly enqueue the children.
        let mut children_to_process = 0isize;
        // Perform the appropriate traversal.
        if let RestyleResult::Continue = context.process_preorder(node) {
            for kid in node.children() {
                // Trigger the hook pre-adding the kid to the list. This can
                // (and in fact uses to) change the result of the should_process
                // operation.
                // As of right now, this hook takes care of propagating the
                // restyle flag down the tree. In the future, more accurate
                // behavior is probably going to be needed.
                context.pre_process_child_hook(node, kid);
                if context.should_process(kid) {
                    children_to_process += 1;

        // Reset the count of children if we need to do a bottom-up traversal
        // after the top up.
        if context.needs_postorder_traversal() {

            // If there were no more children, start walking back up.
            if children_to_process == 0 {
                bottom_up_dom::<N, C>(unsafe_nodes.1, unsafe_node, proxy)

    for chunk in discovered_child_nodes.chunks(CHUNK_SIZE) {
        proxy.push(WorkUnit {
            fun:  top_down_dom::<N, C>,
            data: (Box::new(chunk.iter().cloned().collect()), unsafe_nodes.1),

/// Process current node and potentially traverse its ancestors.
/// If we are the last child that finished processing, recursively process
/// our parent. Else, stop. Also, stop at the root.
/// Thus, if we start with all the leaves of a tree, we end up traversing
/// the whole tree bottom-up because each parent will be processed exactly
/// once (by the last child that finishes processing).
/// The only communication between siblings is that they both
/// fetch-and-subtract the parent's children count.
fn bottom_up_dom<N, C>(root: OpaqueNode,
                       unsafe_node: UnsafeNode,
                       proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>)
    where N: TNode,
          C: DomTraversalContext<N>
    let context = C::new(proxy.user_data(), root);

    // Get a real layout node.
    let mut node = unsafe { N::from_unsafe(&unsafe_node) };
    loop {
        // Perform the appropriate operation.

        let parent = match node.layout_parent_node(root) {
            None => break,
            Some(parent) => parent,

        let parent_data = unsafe {

        if parent_data
            .fetch_sub(1, Ordering::Relaxed) != 1 {
            // Get out of here and find another node to work on.

        // We were the last child of our parent. Construct flows for our parent.
        node = parent;