markup5ever_rcdom/

lib.rs

// Copyright 2014-2017 The html5ever Project Developers. See the
// COPYRIGHT file at the top-level directory of this distribution.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! This crate is not supported, nor published by the html5ever project.
//!
//! This crate is built for the express purpose of writing automated tests for the html5ever and xml5ever crates. It is not intended to be a production-quality DOM implementation, and has not been fuzzed or tested against arbitrary, malicious, or nontrivial inputs. No maintenance or support for any such issues will be provided. If you use this DOM implementation in a production, user-facing system, you do so at your own risk.
//!
//! A simple reference-counted DOM.
//!
//! This is sufficient as a static parse tree, but don't build a
//! web browser using it. :)
//!
//! A DOM is a [tree structure] with ordered children that can be represented in an XML-like
//! format. For example, the following graph
//!
//! ```text
//! div
//!  +- "text node"
//!  +- span
//! ```
//! in HTML would be serialized as
//!
//! ```html
//! <div>text node<span></span></div>
//! ```
//!
//! See the [document object model article on wikipedia][dom wiki] for more information.
//!
//! This implementation stores the information associated with each node once, and then hands out
//! refs to children. The nodes themselves are reference-counted to avoid copying - you can create
//! a new ref and then a node will outlive the document. Nodes own their children, but only have
//! weak references to their parents.
//!
//! [tree structure]: https://en.wikipedia.org/wiki/Tree_(data_structure)
//! [dom wiki]: https://en.wikipedia.org/wiki/Document_Object_Model

extern crate markup5ever;
extern crate tendril;

use std::borrow::Cow;
use std::cell::{Cell, RefCell};
use std::collections::{HashSet, VecDeque};
use std::default::Default;
use std::fmt;
use std::io;
use std::mem;
use std::rc::{Rc, Weak};

use tendril::StrTendril;

use markup5ever::interface::tree_builder;
use markup5ever::interface::tree_builder::{ElementFlags, NodeOrText, QuirksMode, TreeSink};
use markup5ever::serialize::TraversalScope;
use markup5ever::serialize::TraversalScope::{ChildrenOnly, IncludeNode};
use markup5ever::serialize::{Serialize, Serializer};
use markup5ever::Attribute;
use markup5ever::ExpandedName;
use markup5ever::QualName;
use markup5ever::interface::ElemName;
use markup5ever::local_name;

/// The different kinds of nodes in the DOM.
#[derive(Debug, Clone)]
pub enum NodeData {
    /// The `Document` itself - the root node of a HTML document.
    Document,

    /// A `DOCTYPE` with name, public id, and system id. See
    /// [document type declaration on wikipedia][dtd wiki].
    ///
    /// [dtd wiki]: https://en.wikipedia.org/wiki/Document_type_declaration
    Doctype {
        name: StrTendril,
        public_id: StrTendril,
        system_id: StrTendril,
    },

    /// A text node.
    Text { contents: RefCell<StrTendril> },

    /// A comment.
    Comment { contents: StrTendril },

    /// An element with attributes.
    Element {
        name: QualName,
        attrs: RefCell<Vec<Attribute>>,

        /// For HTML \<template\> elements, the [template contents].
        ///
        /// [template contents]: https://html.spec.whatwg.org/multipage/#template-contents
        template_contents: RefCell<Option<Handle>>,

        /// Whether the node is a [HTML integration point].
        ///
        /// [HTML integration point]: https://html.spec.whatwg.org/multipage/#html-integration-point
        mathml_annotation_xml_integration_point: bool,
    },

    /// A Processing instruction.
    ProcessingInstruction {
        target: StrTendril,
        contents: StrTendril,
    },
}

/// A DOM node.
pub struct Node {
    /// Parent node.
    pub parent: Cell<Option<WeakHandle>>,
    /// Child nodes of this node.
    pub children: RefCell<Vec<Handle>>,
    /// Represents this node's data.
    pub data: NodeData,
}

// SAFETY: `Node` contains `Cell` and `RefCell`, which are `!Sync` in the
// general case. We manually assert `Send + Sync` here so that
// `Arc<Node>: Send` (which requires `Node: Send + Sync`), enabling
// futures that hold the parsed DOM to cross thread boundaries on a
// multi-threaded async runtime.
//
// Soundness invariant: a `Node` (and any `Handle = Arc<Node>` /
// `WeakHandle = Weak<Node>` referencing it) is owned by exactly one
// task at a time. The DOM is built by the parser, traversed/cleaned/
// serialized by callers, and dropped — all on a single logical task.
// Tokio's work-stealing scheduler may move the future between worker
// threads, but only one thread polls it at any instant, so no two
// threads ever access the same `Node` simultaneously.
//
// Cloning a `Handle` and using one clone on another thread *while the
// original is still in use on the source thread* is undefined behavior.
// Don't do that.
//
// `StrTendril` (= `Tendril<UTF8, Atomic>` via spider-tendril) is already
// `Send + Sync`, so the tendrils stored inside `NodeData` impose no
// additional constraint.
unsafe impl Send for Node {}
unsafe impl Sync for Node {}

impl Node {
    /// Create a new node from its contents
    pub fn new(data: NodeData) -> Rc<Self> {
        Rc::new(Node {
            data,
            parent: Cell::new(None),
            children: RefCell::new(Vec::new()),
        })
    }

    /// <https://html.spec.whatwg.org/#option-element-nearest-ancestor-select>
    fn get_option_element_nearest_ancestor_select(&self) -> Option<Rc<Self>> {
        // Step 1. Let ancestorOptgroup be null.
        // NOTE: The algorithm doesn't actually need the value, so a boolean is enough.
        let mut did_see_ancestor_optgroup = false;

        // Step 2. For each ancestor of option's ancestors, in reverse tree order:
        let mut current = self.parent().and_then(|parent| parent.upgrade())?;
        loop {
            if let NodeData::Element { name, .. } = &current.data {
                // Step 2.1 If ancestor is a datalist, hr, or option element, then return null.
                if matches!(
                    name.local_name(),
                    &local_name!("datalist") | &local_name!("hr") | &local_name!("option")
                ) {
                    return None;
                }

                // Step 2.2 If ancestor is an optgroup element:
                if name.local_name() == &local_name!("optgroup") {
                    // Step 2.2.1 If ancestorOptgroup is not null, then return null.
                    if did_see_ancestor_optgroup {
                        return None;
                    }

                    // Step 2.2.2 Set ancestorOptgroup to ancestor.
                    did_see_ancestor_optgroup = true;
                }

                // Step 2.3 If ancestor is a select, then return ancestor.
                if name.local_name() == &local_name!("select") {
                    return Some(current);
                }
            };

            // Move on to the next ancestor
            let Some(next_ancestor) = current.parent().and_then(|parent| parent.upgrade()) else {
                break;
            };
            current = next_ancestor;
        }

        // Step 3. Return null.
        None
    }

    fn parent(&self) -> Option<Weak<Self>> {
        let parent = self.parent.take();
        self.parent.set(parent.clone());
        parent
    }

    /// <https://html.spec.whatwg.org/#select-enabled-selectedcontent>
    fn get_a_selects_enabled_selectedcontent(&self) -> Option<Rc<Self>> {
        // Step 1. If select has the multiple attribute, then return null.
        let NodeData::Element { name, attrs, .. } = &self.data else {
            panic!("Trying to get selectedcontent of non-element");
        };
        debug_assert_eq!(name.local_name(), &local_name!("select"));
        if attrs
            .borrow()
            .iter()
            .any(|attribute| attribute.name.local == local_name!("multiple"))
        {
            return None;
        }

        // Step 2. Let selectedcontent be the first selectedcontent element descendant of select in tree order
        // if any such element exists; otherwise return null.
        // FIXME: This does not visit the nodes in tree order
        let mut remaining = VecDeque::default();
        remaining.extend(self.children.borrow().iter().cloned());
        let mut selectedcontent = None;
        while let Some(node) = remaining.pop_front() {
            remaining.extend(node.children.borrow().iter().cloned());

            let NodeData::Element { name, .. } = &self.data else {
                continue;
            };
            if name.local_name() == &local_name!("selectedcontent") {
                selectedcontent = Some(node);
                break;
            }
        }
        let selectedcontent = selectedcontent?;

        // Step 3. If selectedcontent's disabled is true, then return null.
        // FIXME: This step is unimplemented for now to reduce complexity.

        // Step 4. Return selectedcontent.
        Some(selectedcontent)
    }

    /// <https://html.spec.whatwg.org/#clone-an-option-into-a-selectedcontent>
    fn clone_an_option_into_selectedcontent(&self, selectedcontent: Rc<Self>) {
        // Step 1. Let documentFragment be a new DocumentFragment whose node document is option's node document.
        // NOTE: We just remember the children of said fragment, thats good enough.
        let mut document_fragment = Vec::new();

        // Step 2. For each child of option's children:
        for child in self.children.borrow().iter() {
            // Step 2.1 Let childClone be the result of running clone given child with subtree set to true.
            let child_clone = child.clone_with_subtree();

            // Step 2.2 Append childClone to documentFragment.
            document_fragment.push(child_clone);
        }

        // Step 3. Replace all with documentFragment within selectedcontent.
        *selectedcontent.children.borrow_mut() = document_fragment;
    }

    /// Clones the node and all of its descendants, returning a handle to the new subtree.
    ///
    /// This function will run into infinite recursion when the DOM tree contains cycles and it makes
    /// no attempts to guard against that.
    fn clone_with_subtree(&self) -> Rc<Self> {
        let children = self
            .children
            .borrow()
            .iter()
            .map(|child| child.clone_with_subtree())
            .collect();
        Rc::new(Self {
            parent: Cell::new(self.parent()),
            data: self.data.clone(),
            children: RefCell::new(children),
        })
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        let mut nodes = mem::take(&mut *self.children.borrow_mut());
        while let Some(node) = nodes.pop() {
            let children = mem::take(&mut *node.children.borrow_mut());
            nodes.extend(children.into_iter());
            if let NodeData::Element {
                ref template_contents,
                ..
            } = node.data
            {
                if let Some(template_contents) = template_contents.borrow_mut().take() {
                    nodes.push(template_contents);
                }
            }
        }
    }
}

impl fmt::Debug for Node {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        fmt.debug_struct("Node")
            .field("data", &self.data)
            .field("children", &self.children)
            .finish()
    }
}

/// Reference to a DOM node.
pub type Handle = Rc<Node>;

/// Weak reference to a DOM node, used for parent pointers.
pub type WeakHandle = Weak<Node>;

/// Append a parentless node to another nodes' children
fn append(new_parent: &Handle, child: Handle) {
    let previous_parent = child.parent.replace(Some(Rc::downgrade(new_parent)));
    // Invariant: child cannot have existing parent
    assert!(previous_parent.is_none());
    new_parent.children.borrow_mut().push(child);
}

/// If the node has a parent, get it and this node's position in its children
fn get_parent_and_index(target: &Handle) -> Option<(Handle, usize)> {
    if let Some(weak) = target.parent.take() {
        let parent = weak.upgrade().expect("dangling weak pointer");
        target.parent.set(Some(weak));
        let i = match parent
            .children
            .borrow()
            .iter()
            .enumerate()
            .find(|&(_, child)| Rc::ptr_eq(child, target))
        {
            Some((i, _)) => i,
            None => panic!("have parent but couldn't find in parent's children!"),
        };
        Some((parent, i))
    } else {
        None
    }
}

fn append_to_existing_text(prev: &Handle, text: &str) -> bool {
    match prev.data {
        NodeData::Text { ref contents } => {
            contents.borrow_mut().push_slice(text);
            true
        },
        _ => false,
    }
}

fn remove_from_parent(target: &Handle) {
    if let Some((parent, i)) = get_parent_and_index(target) {
        parent.children.borrow_mut().remove(i);
        target.parent.set(None);
    }
}

/// The DOM itself; the result of parsing.
pub struct RcDom {
    /// The `Document` itself.
    pub document: Handle,

    /// Errors that occurred during parsing.
    pub errors: RefCell<Vec<Cow<'static, str>>>,

    /// The document's quirks mode.
    pub quirks_mode: Cell<QuirksMode>,
}

impl TreeSink for RcDom {
    type Output = Self;
    fn finish(self) -> Self {
        self
    }

    type Handle = Handle;

    type ElemName<'a>
        = ExpandedName<'a>
    where
        Self: 'a;

    fn parse_error(&self, msg: Cow<'static, str>) {
        self.errors.borrow_mut().push(msg);
    }

    fn get_document(&self) -> Handle {
        self.document.clone()
    }

    fn get_template_contents(&self, target: &Handle) -> Handle {
        if let NodeData::Element {
            ref template_contents,
            ..
        } = target.data
        {
            template_contents
                .borrow()
                .as_ref()
                .expect("not a template element!")
                .clone()
        } else {
            panic!("not a template element!")
        }
    }

    fn set_quirks_mode(&self, mode: QuirksMode) {
        self.quirks_mode.set(mode);
    }

    fn same_node(&self, x: &Handle, y: &Handle) -> bool {
        Rc::ptr_eq(x, y)
    }

    fn elem_name<'a>(&self, target: &'a Handle) -> ExpandedName<'a> {
        match target.data {
            NodeData::Element { ref name, .. } => name.expanded(),
            _ => panic!("not an element!"),
        }
    }

    fn create_element(&self, name: QualName, attrs: Vec<Attribute>, flags: ElementFlags) -> Handle {
        Node::new(NodeData::Element {
            name,
            attrs: RefCell::new(attrs),
            template_contents: RefCell::new(if flags.template {
                Some(Node::new(NodeData::Document))
            } else {
                None
            }),
            mathml_annotation_xml_integration_point: flags.mathml_annotation_xml_integration_point,
        })
    }

    fn create_comment(&self, text: StrTendril) -> Handle {
        Node::new(NodeData::Comment { contents: text })
    }

    fn create_pi(&self, target: StrTendril, data: StrTendril) -> Handle {
        Node::new(NodeData::ProcessingInstruction {
            target,
            contents: data,
        })
    }

    fn append(&self, parent: &Handle, child: NodeOrText<Handle>) {
        // Append to an existing Text node if we have one.
        if let NodeOrText::AppendText(text) = &child {
            if let Some(h) = parent.children.borrow().last() {
                if append_to_existing_text(h, text) {
                    return;
                }
            }
        }

        append(
            parent,
            match child {
                NodeOrText::AppendText(text) => Node::new(NodeData::Text {
                    contents: RefCell::new(text),
                }),
                NodeOrText::AppendNode(node) => node,
            },
        );
    }

    fn append_before_sibling(&self, sibling: &Handle, child: NodeOrText<Handle>) {
        let (parent, i) = get_parent_and_index(sibling)
            .expect("append_before_sibling called on node without parent");

        let child = match (child, i) {
            // No previous node.
            (NodeOrText::AppendText(text), 0) => Node::new(NodeData::Text {
                contents: RefCell::new(text),
            }),

            // Look for a text node before the insertion point.
            (NodeOrText::AppendText(text), i) => {
                let children = parent.children.borrow();
                let prev = &children[i - 1];
                if append_to_existing_text(prev, &text) {
                    return;
                }
                Node::new(NodeData::Text {
                    contents: RefCell::new(text),
                })
            },

            // The tree builder promises we won't have a text node after
            // the insertion point.

            // Any other kind of node.
            (NodeOrText::AppendNode(node), _) => node,
        };

        remove_from_parent(&child);

        child.parent.set(Some(Rc::downgrade(&parent)));
        parent.children.borrow_mut().insert(i, child);
    }

    fn append_based_on_parent_node(
        &self,
        element: &Self::Handle,
        prev_element: &Self::Handle,
        child: NodeOrText<Self::Handle>,
    ) {
        let parent = element.parent.take();
        let has_parent = parent.is_some();
        element.parent.set(parent);

        if has_parent {
            self.append_before_sibling(element, child);
        } else {
            self.append(prev_element, child);
        }
    }

    fn append_doctype_to_document(
        &self,
        name: StrTendril,
        public_id: StrTendril,
        system_id: StrTendril,
    ) {
        append(
            &self.document,
            Node::new(NodeData::Doctype {
                name,
                public_id,
                system_id,
            }),
        );
    }

    fn add_attrs_if_missing(&self, target: &Handle, attrs: Vec<Attribute>) {
        let mut existing = if let NodeData::Element { ref attrs, .. } = target.data {
            attrs.borrow_mut()
        } else {
            panic!("not an element")
        };

        let existing_names = existing
            .iter()
            .map(|e| e.name.clone())
            .collect::<HashSet<_>>();
        existing.extend(
            attrs
                .into_iter()
                .filter(|attr| !existing_names.contains(&attr.name)),
        );
    }

    fn remove_from_parent(&self, target: &Handle) {
        remove_from_parent(target);
    }

    fn reparent_children(&self, node: &Handle, new_parent: &Handle) {
        let mut children = node.children.borrow_mut();
        let mut new_children = new_parent.children.borrow_mut();
        for child in children.iter() {
            let previous_parent = child.parent.replace(Some(Rc::downgrade(new_parent)));
            assert!(Rc::ptr_eq(
                node,
                &previous_parent.unwrap().upgrade().expect("dangling weak")
            ))
        }
        new_children.extend(mem::take(&mut *children));
    }

    fn is_mathml_annotation_xml_integration_point(&self, target: &Handle) -> bool {
        if let NodeData::Element {
            mathml_annotation_xml_integration_point,
            ..
        } = target.data
        {
            mathml_annotation_xml_integration_point
        } else {
            panic!("not an element!")
        }
    }

    fn maybe_clone_an_option_into_selectedcontent(&self, option: &Self::Handle) {
        let NodeData::Element { name, attrs, .. } = &option.data else {
            panic!("\"maybe clone an option into selectedcontent\" called with non-element node");
        };
        debug_assert_eq!(name.local_name(), &local_name!("option"));

        // Step 1. Let select be option's option element nearest ancestor select.
        let select = option.get_option_element_nearest_ancestor_select();

        // Step 2. If all of the following conditions are true:
        // * select is not null;
        // * option's selectedness is true; and
        // * select's enabled selectedcontent is not null,
        // then run clone an option into a selectedcontent given option and select's enabled selectedcontent.
        if let Some(selectedcontent) =
            select.and_then(|select| select.get_a_selects_enabled_selectedcontent())
        {
            if attrs
                .borrow()
                .iter()
                .any(|attribute| attribute.name.local == local_name!("selected"))
            {
                option.clone_an_option_into_selectedcontent(selectedcontent);
            }
        }
    }
}

impl Default for RcDom {
    fn default() -> RcDom {
        RcDom {
            document: Node::new(NodeData::Document),
            errors: Default::default(),
            quirks_mode: Cell::new(tree_builder::NoQuirks),
        }
    }
}

enum SerializeOp {
    Open(Handle),
    Close(QualName),
}

pub struct SerializableHandle(Handle);

impl From<Handle> for SerializableHandle {
    fn from(h: Handle) -> SerializableHandle {
        SerializableHandle(h)
    }
}

impl Serialize for SerializableHandle {
    fn serialize<S>(&self, serializer: &mut S, traversal_scope: TraversalScope) -> io::Result<()>
    where
        S: Serializer,
    {
        let mut ops = VecDeque::new();
        match traversal_scope {
            IncludeNode => ops.push_back(SerializeOp::Open(self.0.clone())),
            ChildrenOnly(_) => ops.extend(
                self.0
                    .children
                    .borrow()
                    .iter()
                    .map(|h| SerializeOp::Open(h.clone())),
            ),
        }

        while let Some(op) = ops.pop_front() {
            match op {
                SerializeOp::Open(handle) => match handle.data {
                    NodeData::Element {
                        ref name,
                        ref attrs,
                        ..
                    } => {
                        serializer.start_elem(
                            name.clone(),
                            attrs.borrow().iter().map(|at| (&at.name, &at.value[..])),
                        )?;

                        ops.reserve(1 + handle.children.borrow().len());
                        ops.push_front(SerializeOp::Close(name.clone()));

                        for child in handle.children.borrow().iter().rev() {
                            ops.push_front(SerializeOp::Open(child.clone()));
                        }
                    },

                    NodeData::Doctype { ref name, .. } => serializer.write_doctype(name)?,

                    NodeData::Text { ref contents } => serializer.write_text(&contents.borrow())?,

                    NodeData::Comment { ref contents } => serializer.write_comment(contents)?,

                    NodeData::ProcessingInstruction {
                        ref target,
                        ref contents,
                    } => serializer.write_processing_instruction(target, contents)?,

                    NodeData::Document => panic!("Can't serialize Document node itself"),
                },

                SerializeOp::Close(name) => {
                    serializer.end_elem(name)?;
                },
            }
        }

        Ok(())
    }
}