htmlite 0.12.0 - Docs.rs

use crate::parser::{Namespace, VOID_ELEMENT_NAMES};
use crate::selector::CompiledSelector;
use std::borrow::Cow;
use std::cell::Cell;
use std::fmt::{self, Debug, Display};
use std::num::NonZeroUsize;
use std::ops::Index;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct NodeId(NonZeroUsize);

/// Types of nodes that might exist in an HTML document.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NodeKind {
    /// A synthetic node that exists purely to contain the other nodes.
    Fragment,
    /// Text within an HTML element.
    Text,
    /// An HTML comment  (e.g. `<!-- blah -->`)
    Comment,
    /// A doctype element (e.g. `<!DOCTYPE html>`)
    Doctype,
    /// An HTML tag
    Element,
}

pub(crate) struct NodeData {
    pub(crate) parent: Cell<Option<NodeId>>,
    pub(crate) previous_sibling: Cell<Option<NodeId>>,
    pub(crate) next_sibling: Cell<Option<NodeId>>,
    pub(crate) first_child: Cell<Option<NodeId>>,
    pub(crate) last_child: Cell<Option<NodeId>>,
    pub(crate) kind: NodeKind,
    pub(crate) data: Cow<'static, str>,
    pub(crate) attrs: Vec<(String, String)>,
    pub(crate) special: bool,
    pub(crate) namespace: Namespace,
}

/// Storage for parsed HTML nodes.
///
/// You'll generally pass an instance of this struct around to functions that create new nodes.
/// The created nodes will have a liftime tied to the arena that was used to create them.
///
/// Dropping the arena cleans up the memory used for storing HTML nodes all at once.
///
/// # Constructing HTML
///
/// This struct is also the starting point for programmatically constructing HTML ([impl block](crate::NodeArena#impl-NodeArena-1)).
///
/// The methods all have the same structure; they accept two arguments: attributes and child elements.
/// For attributes, you can pass in anything that can be converted into an iterator of two item tuples.
/// For children, you can pass in anything that can be converted into an iterator of [`Nodes`](crate::Node).
///
/// Note: `Option<T>` implements `IntoIterator`, so you can also use `None` to mean "no children" or "no attributes"
///
/// ```
/// use htmlite::{NodeArena};
///
/// let h = NodeArena::new();
///
/// // These are the same
/// let empty_div = h.div([], []);
/// let empty_div = h.div(None, None);
///
/// let div_with_one_span = h.div(None, h.span(None, None));
/// let div_with_many_spans = h.div(None, [h.span(None, None), h.span(None, None)]);
///
/// let div_with_attributes = h.div([("class", "container"), ("id", "nav")], None);
/// ```
pub struct NodeArena {
    pub(crate) nodes: Box<boxcar::Vec<NodeData>>,
}

/// Represents a [node](https://developer.mozilla.org/en-US/docs/Web/API/Node) in an HTML document.
///
/// # Nodes are detached before `append`/`prepend`/`insert_*`:
///
/// Appending a node `B` to node `A` automatically [detaches](Node::detach) node `B`.
/// Without this, your DOM tree could easily turn into a DOM graph.   
///
/// ```
/// let h = htmlite::NodeArena::new();
///
/// let src = h.div([], h.a([], []));
/// let dst = h.section([], []);
///
/// // Try to copy the anchor element into the section element.
/// dst.append(src.descendants().select("a"));
///
/// // *poof*
/// assert_eq!(src.html(), "<div></div>");
/// assert_eq!(dst.html(), "<section><a></a></section>");
/// ```
///
/// When you need to "copy-paste" a node, use [`Node::deep_copy`]
///
/// ```
/// let h = htmlite::NodeArena::new();
///
/// let src = h.div([], h.a([], []));
/// let dst = h.section([], []);
///
/// let a = src.first_child().unwrap();
/// dst.append(a.deep_copy());
///
/// assert_eq!(src.html(), "<div><a></a></div>");
/// assert_eq!(dst.html(), "<section><a></a></section>");
#[derive(Clone, Copy)]
pub struct Node<'a> {
    pub(crate) id: NodeId,
    pub(crate) arena: &'a NodeArena,
}

pub struct NodeIter<'a> {
    curr: Option<Node<'a>>,
    next: fn(Node<'a>) -> Option<Node<'a>>,
}

pub struct Descendants<'a> {
    stack: Vec<Node<'a>>,
}

/// An iterator of nodes that match a particular criteria.
///
/// Returned from methods like [`Node::ancestors`] or [`Node::children`] return this struct.
///
/// Of particular interest is this structs [`select`](crate::Selection::select) method, which filters iterated nodes using a CSS selector.
pub struct Selection<I> {
    iter: I,
    selector: Option<CompiledSelector>,
}

impl<'a> Node<'a> {
    /// Returns the node's name.
    ///
    /// For [`NodeKind::Element`] this returns the tag name.
    /// For [`NodeKind::Doctype`] this returns the doctype name.
    /// For all other node kinds, this returns an empty string.
    pub fn name(&self) -> &str {
        let node = &self.arena.nodes[self.id];
        match node.kind {
            NodeKind::Element | NodeKind::Doctype => &node.data,
            _ => "",
        }
    }

    /// Returns the node's type.
    pub fn kind(&self) -> NodeKind {
        let node = &self.arena.nodes[self.id];
        node.kind
    }

    /// Returns an iterator of this node's attributes.
    pub fn attrs(&self) -> impl Iterator<Item = (&str, &str)> {
        let node = &self.arena.nodes[self.id];
        node.attrs.iter().map(|(k, v)| (k.as_str(), v.as_str()))
    }

    /// Returns the value of the attribute with the given name.
    ///
    /// The name comparison is done in a case insensitive manner.
    ///
    /// If there is no such attribute, or if self is not a [`NodeKind::Element`], returns None.
    pub fn attr(&self, name: &str) -> Option<&str> {
        let node = &self.arena.nodes[self.id];
        node.attrs
            .iter()
            .find(|(n, _)| name.eq_ignore_ascii_case(n))
            .map(|(_, v)| v.as_str())
    }

    /// Serializes this node and its descendants as an HTML string
    pub fn html(&self) -> String {
        self.to_string()
    }

    /// Serializes this node's descendants as an HTML string
    ///
    /// # Examples
    ///
    /// ```
    /// let h = htmlite::NodeArena::new();
    /// let root = htmlite::parse(&h, "<div>text</div>").unwrap();
    /// let div = root.descendants().select("div").next().unwrap();
    /// assert_eq!(div.inner_html(), "text");
    /// ```
    pub fn inner_html(&self) -> String {
        let mut result = String::new();
        for child in self.children() {
            result += &child.html();
        }
        result
    }

    /// Returns the text contents of this node and its descendants.
    ///
    /// Returns an empty string for [`NodeKind::Doctype`] nodes.
    pub fn text_content(&self) -> String {
        match self.kind() {
            NodeKind::Text | NodeKind::Comment => {
                let node = &self.arena.nodes[self.id];
                node.data.to_string()
            }
            NodeKind::Element | NodeKind::Fragment => {
                let mut out = String::new();
                for n in self.descendants() {
                    if n.kind() == NodeKind::Text {
                        out.push_str(&self.arena.nodes[n.id].data);
                    }
                }
                out
            }
            NodeKind::Doctype => String::new(),
        }
    }

    /// Returns a reference to the parent node if any.
    ///
    /// ```
    /// let h = htmlite::NodeArena::new();
    /// let root = htmlite::parse(&h, "<div>text</div>").unwrap();
    /// let div = root.descendants().select("div").next().unwrap();
    /// let text = div.first_child().unwrap();
    /// assert_eq!(text.parent(), Some(div));
    /// ```
    ///
    /// [Fragment nodes](`NodeKind::Fragment`) have no parents.
    ///
    /// ```
    /// use htmlite::{NodeArena, Node};
    /// let h = NodeArena::new();
    /// let root = htmlite::parse(&h, "<div></div>").unwrap();
    /// assert_eq!(root.parent(), None);
    /// ```
    pub fn parent(&self) -> Option<Node<'a>> {
        let node = &self.arena.nodes[self.id];
        node.parent.get().map(|id| Node {
            id,
            arena: self.arena,
        })
    }

    /// Returns a reference to this node's next sibling node.
    pub fn next(&self) -> Option<Node<'a>> {
        let node = &self.arena.nodes[self.id];
        node.next_sibling.get().map(|id| Node {
            id,
            arena: self.arena,
        })
    }

    /// Returns a reference to this node's previous sibling node.
    pub fn previous(&self) -> Option<Node<'a>> {
        let node = &self.arena.nodes[self.id];
        node.previous_sibling.get().map(|id| Node {
            id,
            arena: self.arena,
        })
    }

    /// Returns a reference to the first child of this node.
    pub fn first_child(&self) -> Option<Node<'a>> {
        let node = &self.arena.nodes[self.id];
        node.first_child.get().map(|id| Node {
            id,
            arena: self.arena,
        })
    }

    /// Returns a reference to the last child of this node.
    pub fn last_child(&self) -> Option<Node<'a>> {
        let node = &self.arena.nodes[self.id];
        node.last_child.get().map(|id| Node {
            id,
            arena: self.arena,
        })
    }

    /// Inserts `children` after this node's last child.
    ///
    /// # Panics
    ///
    /// This method panics if `self` is a [Text](NodeKind::Text), [comment](NodeKind::Comment) or [Doctype](NodeKind::Doctype) node.
    pub fn append<I>(&self, children: I)
    where
        I: IntoIterator<Item = Node<'a>>,
    {
        if matches!(
            self.kind(),
            NodeKind::Text | NodeKind::Comment | NodeKind::Doctype
        ) {
            panic!("can only append to fragment and element nodes");
        }

        for child in children {
            for node in child.flatten() {
                self.append_impl(node);
            }
        }
    }

    /// Inserts `children` before this node's first child.
    ///
    /// # Panics
    ///
    /// This method panics if `self` is a [Text](NodeKind::Text), [comment](NodeKind::Comment) or [Doctype](NodeKind::Doctype) node.
    pub fn prepend<I>(&self, children: I)
    where
        I: IntoIterator<Item = Node<'a>>,
    {
        if matches!(
            self.kind(),
            NodeKind::Text | NodeKind::Comment | NodeKind::Doctype
        ) {
            panic!("can only prepend to fragment and element nodes");
        }

        // We need to prepend the list of nodes in reverse order.
        // But that would mean requiring that `children` is an ExactSizeIterator (so we can use rev())
        // We can avoid that requirement by keeping track of the child node that needs a sibling node;
        let mut anchor: Option<Node<'a>> = None;
        for child in children {
            for node in child.flatten() {
                if let Some(anchor) = anchor {
                    anchor.insert_after([node]);
                } else {
                    self.prepend_impl(node);
                }
                anchor = Some(node);
            }
        }
    }

    /// Inserts `siblings` before this node.
    pub fn insert_before<I>(&self, siblings: I)
    where
        I: IntoIterator<Item = Node<'a>>,
    {
        if self.kind() == NodeKind::Fragment {
            panic!("cannot insert before fragment node");
        }

        for sibling in siblings {
            for node in sibling.flatten() {
                self.insert_before_impl(node);
            }
        }
    }

    /// Inserts `siblings` after this node.
    pub fn insert_after<I>(&self, siblings: I)
    where
        I: IntoIterator<Item = Node<'a>>,
    {
        if self.kind() == NodeKind::Fragment {
            panic!("cannot insert after fragment node");
        }

        // See comment in Node::prepend
        let mut anchor: Option<Node> = None;
        for sibling in siblings {
            for node in sibling.flatten() {
                if let Some(anchor) = anchor {
                    anchor.insert_after([node]);
                } else {
                    self.insert_after_impl(node);
                };
                anchor = Some(node);
            }
        }
    }

    /// Detaches `self` from its tree and replaces it with `other`
    pub fn replace(&self, other: Node<'a>) {
        self.insert_after(other);
        self.detach();
    }

    /// Returns an iterator of references to ancestor nodes.
    ///
    /// If the markup came from a string, the top-level nodes will be wrapped in a [`NodeKind::Fragment`] node.
    /// This will be the last element yielded by the iterator.
    ///
    /// # Examples
    ///
    /// ```
    /// use htmlite::{NodeArena, Node};
    /// let arena = NodeArena::new();
    /// let root = htmlite::parse(&arena, "<body><section><div></div></section></body>").unwrap();
    /// let div = root.descendants().select("div").next().unwrap();
    ///
    /// let iter = div.ancestors().map(|n| n.name().to_string());
    /// assert_eq!(
    ///     iter.collect::<Vec<_>>(),
    ///     ["section", "body", ""]
    /// );
    /// ```
    pub fn ancestors(&self) -> Selection<NodeIter<'a>> {
        Selection {
            iter: NodeIter {
                curr: self.parent(),
                next: |n| n.parent(),
            },
            selector: None,
        }
    }

    /// Returns an iterator of references to descendant nodes.
    ///
    /// Parent nodes will appear before their children.
    ///
    /// # Examples
    ///
    /// ```
    /// use htmlite::{NodeArena, Node};
    /// let arena = NodeArena::new();
    /// let root = htmlite::parse(&arena, "<body><aside></aside><main><section></section></main></body>").unwrap();
    /// let body = root.descendants().select("body").next().unwrap();
    ///
    /// let iter = body.descendants().map(|n| n.name().to_string());
    /// assert_eq!(
    ///     iter.collect::<Vec<_>>(),
    ///     ["aside", "main", "section"]
    /// );
    /// ```
    pub fn descendants(&self) -> Selection<Descendants<'a>> {
        Selection {
            iter: Descendants {
                stack: self.reverse_children().collect::<Vec<_>>(),
            },
            selector: None,
        }
    }

    /// Returns an iterator of references to children nodes.
    ///
    /// This only returns direct children. To traverse the tree rooted at `self`, use [`Node::descendants`].
    pub fn children(&self) -> Selection<NodeIter<'a>> {
        Selection {
            iter: NodeIter {
                curr: self.first_child(),
                next: |n| n.next(),
            },
            selector: None,
        }
    }

    /// Returns an iterator of references to children nodes in reverse order.
    pub fn reverse_children(&self) -> Selection<NodeIter<'a>> {
        Selection {
            iter: NodeIter {
                curr: self.last_child(),
                next: |n| n.previous(),
            },
            selector: None,
        }
    }

    /// Returns an iterator of references to the nodes before this node.
    pub fn preceding(&self) -> Selection<NodeIter<'a>> {
        Selection {
            iter: NodeIter {
                curr: self.previous(),
                next: |n| n.previous(),
            },
            selector: None,
        }
    }

    /// Returns an iterator of references to the nodes after this node.
    pub fn following(&self) -> Selection<NodeIter<'a>> {
        Selection {
            iter: NodeIter {
                curr: self.next(),
                next: |n| n.next(),
            },
            selector: None,
        }
    }

    /// Orphans this node by detaching it from its parent and siblings.
    ///
    /// Children are not affected.
    ///
    /// This has no effect on `Fragment` nodes.
    pub fn detach(&self) {
        let nodes = &self.arena.nodes;

        let parent = nodes[self.id].parent.take();
        let previous_sibling = nodes[self.id].previous_sibling.take();
        let next_sibling = nodes[self.id].next_sibling.take();

        // If the node we just detached had a right sibling, we need to maintain the link between
        // both sides of the node we just detached.
        // If it does not have a right sibling, this indicates it is the last child of its parent (if it has one),
        // so we'll need to adjust the parent pointers.
        // We mirror this same logic for the left side.

        if let Some(next) = next_sibling {
            nodes[next].previous_sibling.set(previous_sibling);
        } else if let Some(parent) = parent {
            nodes[parent].last_child.set(previous_sibling);
        }

        if let Some(prev) = previous_sibling {
            nodes[prev].next_sibling.set(next_sibling);
        } else if let Some(parent) = parent {
            nodes[parent].first_child.set(next_sibling);
        }
    }

    /// Creates a deep-copy this node by recursively building a tree out of new copies of its children.
    pub fn deep_copy(&self) -> Node<'a> {
        let n = &self.arena.nodes[self.id];
        match &self.kind() {
            NodeKind::Fragment => {
                let new_chunk = self.arena.fragment([]);
                for child in self.children() {
                    new_chunk.append(child.deep_copy());
                }
                new_chunk
            }
            NodeKind::Comment => self.arena.new_comment(n.data.to_string()),
            NodeKind::Doctype => self.arena.new_doctype(n.data.to_string()),
            NodeKind::Text => self.arena.new_text(n.data.to_string(), n.special),
            NodeKind::Element => {
                let new_element = self.arena.alloc(NodeData {
                    data: n.data.clone(),
                    attrs: n.attrs.clone(),
                    namespace: n.namespace,
                    kind: n.kind,
                    special: n.special,
                    ..Default::default()
                });
                for child in self.children() {
                    new_element.append(child.deep_copy())
                }
                new_element
            }
        }
    }

    fn append_impl(&self, child: Node) {
        child.detach();
        let nodes = &self.arena.nodes;

        nodes[child.id].parent.set(Some(self.id));

        // Set the new child as the parent's last child.
        // If the parent already had a last child, we'll adjust its pointers to account for the new sibling ahead of it.
        // If it did not, this implies we are inserting the first child, so set the new node to be the parent's first child as well.
        if let Some(last_child) = nodes[self.id].last_child.replace(Some(child.id)) {
            nodes[child.id].previous_sibling.set(Some(last_child));
            nodes[last_child].next_sibling.set(Some(child.id));
        } else {
            nodes[self.id].first_child.set(Some(child.id));
        }
    }

    fn prepend_impl(&self, child: Node) {
        child.detach();
        let nodes = &self.arena.nodes;

        nodes[child.id].parent.set(Some(self.id));

        if let Some(first_child) = nodes[self.id].first_child.replace(Some(child.id)) {
            nodes[child.id].next_sibling.set(Some(first_child));
            nodes[first_child].previous_sibling.set(Some(child.id));
        } else {
            nodes[self.id].last_child.set(Some(child.id));
        }
    }

    fn insert_before_impl(&self, new_sibling: Node) {
        new_sibling.detach();
        let nodes = &self.arena.nodes;

        nodes[new_sibling.id]
            .parent
            .set(nodes[self.id].parent.get());
        nodes[new_sibling.id].next_sibling.set(Some(self.id));

        if let Some(previous_sibling) = nodes[self.id]
            .previous_sibling
            .replace(Some(new_sibling.id))
        {
            nodes[previous_sibling]
                .next_sibling
                .set(Some(new_sibling.id));
            nodes[new_sibling.id]
                .previous_sibling
                .set(Some(previous_sibling));
        } else if let Some(parent) = nodes[self.id].parent.get() {
            nodes[parent].first_child.set(Some(new_sibling.id));
        }
    }

    fn insert_after_impl(&self, new_sibling: Node) {
        new_sibling.detach();
        let nodes = &self.arena.nodes;

        nodes[new_sibling.id]
            .parent
            .set(nodes[self.id].parent.get());
        nodes[new_sibling.id].previous_sibling.set(Some(self.id));

        if let Some(next_sibling) = nodes[self.id].next_sibling.replace(Some(new_sibling.id)) {
            nodes[next_sibling]
                .previous_sibling
                .set(Some(new_sibling.id));
            nodes[new_sibling.id].next_sibling.set(Some(next_sibling));
        } else if let Some(parent) = nodes[self.id].parent.get() {
            nodes[parent].last_child.set(Some(new_sibling.id))
        }
    }

    fn flatten(&self) -> NodeIter<'a> {
        match self.kind() {
            NodeKind::Fragment => NodeIter {
                curr: self.first_child(),
                next: |n| n.next(),
            },
            _ => NodeIter {
                curr: Some(*self),
                next: |_| None,
            },
        }
    }
}

impl<'a> IntoIterator for Node<'a> {
    type Item = Node<'a>;

    type IntoIter = std::iter::Once<Node<'a>>;

    fn into_iter(self) -> Self::IntoIter {
        std::iter::once(self)
    }
}

impl PartialEq for Node<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl Eq for Node<'_> {}

impl Debug for Node<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Node").field("id", &self.id).finish()
    }
}

impl Display for Node<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let n = &self.arena.nodes[self.id];
        match &n.kind {
            NodeKind::Comment => write!(f, "<!--{}-->", n.data),
            NodeKind::Doctype => write!(f, "<!DOCTYPE {}>", n.data),
            NodeKind::Text => {
                if n.special {
                    write!(f, "{}", n.data)?;
                    return Ok(());
                }

                if !n.data.contains(['"', '\'', '<', '>', '&']) {
                    write!(f, "{}", n.data)?;
                    return Ok(());
                }

                for c in n.data.chars() {
                    match c {
                        '&' => write!(f, "&amp;")?,
                        '\u{a0}' => write!(f, "&nbsp;")?,
                        '<' => write!(f, "&lt;")?,
                        '>' => write!(f, "&gt;")?,
                        c => write!(f, "{c}")?,
                    }
                }
                Ok(())
            }
            NodeKind::Fragment => {
                for child in self.children() {
                    write!(f, "{child}")?;
                }
                Ok(())
            }
            NodeKind::Element => {
                write!(f, "<{}", n.data)?;
                if !n.attrs.is_empty() {
                    for (name, value) in n.attrs.iter() {
                        write!(f, " {name}=\"")?;
                        for char in value.chars() {
                            // See: https://html.spec.whatwg.org/multipage/parsing.html#escapingString
                            match char {
                                '&' => write!(f, "&amp;")?,
                                '\u{a0}' => write!(f, "&nbsp;")?,
                                '<' => write!(f, "&lt;")?,
                                '>' => write!(f, "&gt;")?,
                                '"' => write!(f, "&quot;")?,
                                c => write!(f, "{c}")?,
                            }
                        }
                        write!(f, "\"")?;
                    }
                }

                if n.namespace == Namespace::Html && VOID_ELEMENT_NAMES.contains(&&*n.data) {
                    return write!(f, ">");
                }

                if n.namespace == Namespace::Foreign && n.first_child.get().is_none() {
                    return write!(f, "/>");
                }

                write!(f, ">")?;

                for n in self.children() {
                    write!(f, "{n}")?;
                }

                write!(f, "</{}>", n.data)
            }
        }
    }
}

impl Default for NodeArena {
    fn default() -> Self {
        Self::new()
    }
}

impl NodeArena {
    /// Returns an empty storage location for parsed nodes.
    pub fn new() -> NodeArena {
        let nodes = boxcar::Vec::new();

        // Push a dumy node so that all valid node ids are greater than 0.
        // This lets us use NonZeroUsize as the underlying type for NodeId, which cuts the space required to store Option<NodeId> in half.
        nodes.push(NodeData {
            kind: NodeKind::Fragment,
            ..NodeData::default()
        });
        NodeArena {
            nodes: Box::new(nodes),
        }
    }

    /// Allocates a [fragment](crate::NodeKind::Fragment) with the given nodes.
    pub fn fragment<'a, I>(&'a self, children: I) -> Node<'a>
    where
        I: IntoIterator<Item = Node<'a>>,
    {
        let node = self.new_fragment();
        node.append(children);
        node
    }

    /// Allocates a text node with the given contents and returns it.
    ///
    /// Serializing the node to HTML will escape its contents.   
    pub fn text(&self, text: impl Into<Cow<'static, str>>) -> Node<'_> {
        self.new_text(text, false)
    }

    /// Allocates a text node with the given contents and returns it.
    ///
    /// Serializing the node to HTML will _not_ escape its contents.
    /// They will be output verbatim.
    pub fn raw_text(&self, text: impl Into<Cow<'static, str>>) -> Node<'_> {
        self.new_text(text, true)
    }

    pub(crate) fn new_fragment(&self) -> Node<'_> {
        self.alloc(NodeData {
            kind: NodeKind::Fragment,
            ..NodeData::default()
        })
    }

    pub(crate) fn new_element<'attr, A>(
        &self,
        tag: impl Into<Cow<'static, str>>,
        attributes: A,
        namespace: Namespace,
    ) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        self.alloc(NodeData {
            data: tag.into(),
            namespace,
            attrs: attributes
                .into_iter()
                .map(|(n, v)| (String::from(n), String::from(v)))
                .collect(),
            ..NodeData::default()
        })
    }

    pub(crate) fn new_comment(&self, comment: impl Into<Cow<'static, str>>) -> Node<'_> {
        self.alloc(NodeData {
            kind: NodeKind::Comment,
            data: comment.into(),
            ..NodeData::default()
        })
    }

    pub(crate) fn new_text(
        &self,
        text: impl Into<Cow<'static, str>>,
        serialize_verbatim: bool,
    ) -> Node<'_> {
        self.alloc(NodeData {
            kind: NodeKind::Text,
            data: text.into(),
            special: serialize_verbatim,
            ..NodeData::default()
        })
    }

    pub(crate) fn new_doctype(&self, name: impl Into<Cow<'static, str>>) -> Node<'_> {
        self.alloc(NodeData {
            kind: NodeKind::Doctype,
            data: name.into(),
            ..NodeData::default()
        })
    }

    fn alloc(&self, node: NodeData) -> Node<'_> {
        let new_idx = self.nodes.push(node);

        Node {
            // The nodes array will always have at least one element, meaning our undex will always be > 0
            id: NodeId(NonZeroUsize::new(new_idx).unwrap()),
            arena: self,
        }
    }
}

macro_rules! tag_name_functions {
    ($($name:ident),*) => {
        $(
            pub fn $name<'a, 'attr, A, C>(&'a self, attributes: A, children: C) -> $crate::Node<'a>
            where C: IntoIterator<Item = Node<'a>>,
            A: IntoIterator<Item = (&'attr str, &'attr str)>,
            {
                let el = self.new_element(stringify!($name), attributes, Namespace::Html);
                el.append(children);
                el
            }
        )*
    };
}

/// Methods for creating various HTML elements.
impl NodeArena {
    pub fn doctype<'a>(&'a self) -> Node<'a> {
        self.new_doctype("html")
    }

    pub fn title<'attr, A>(&self, attributes: A, title: impl Into<Cow<'static, str>>) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        let text = self.raw_text(title);
        let el = self.new_element("title", attributes, Namespace::Html);
        el.append([text]);
        el
    }

    pub fn textarea<'attr, A>(&self, attributes: A, text: impl Into<Cow<'static, str>>) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        let text = self.raw_text(text);
        let el = self.new_element("textarea", attributes, Namespace::Html);
        el.append([text]);
        el
    }

    pub fn style<'attr, A>(&self, attributes: A, css: impl Into<Cow<'static, str>>) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        let text = self.raw_text(css);
        let el = self.new_element("style", attributes, Namespace::Html);
        el.append([text]);
        el
    }

    pub fn iframe<'attr, A>(&self, attributes: A, content: impl Into<Cow<'static, str>>) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        let text = self.raw_text(content);
        let el = self.new_element("iframe", attributes, Namespace::Html);
        el.append([text]);
        el
    }

    pub fn script<'attr, A>(&self, attributes: A, script: impl Into<Cow<'static, str>>) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        let text = self.raw_text(script);
        let el = self.new_element("script", attributes, Namespace::Html);
        el.append([text]);
        el
    }

    pub fn noscript<'attr, A>(
        &self,
        attributes: A,
        content: impl Into<Cow<'static, str>>,
    ) -> Node<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
    {
        let text = self.raw_text(content);
        let el = self.new_element("noscript", attributes, Namespace::Html);
        el.append([text]);
        el
    }

    tag_name_functions! {
        a,
        abbr,
        address,
        area,
        article,
        aside,
        audio,
        b,
        base,
        bdi,
        bdo,
        blockquote,
        body,
        br,
        button,
        canvas,
        caption,
        cite,
        code,
        col,
        colgroup,
        data,
        datalist,
        dd,
        del,
        details,
        dfn,
        dialog,
        div,
        dl,
        dt,
        em,
        embed,
        fieldset,
        figcaption,
        figure,
        footer,
        form,
        h1,
        h2,
        h3,
        h4,
        h5,
        h6,
        head,
        header,
        hgroup,
        hr,
        html,
        i,
        // iframe,
        img,
        input,
        ins,
        kbd,
        label,
        legend,
        li,
        link,
        main,
        map,
        mark,
        menu,
        meta,
        meter,
        nav,
        // noscript,
        object,
        ol,
        optgroup,
        option,
        output,
        p,
        picture,
        pre,
        progress,
        q,
        rp,
        rt,
        ruby,
        s,
        samp,
        // script,
        search,
        section,
        select,
        selectedcontent,
        slot,
        small,
        source,
        span,
        strong,
        // style,
        sub,
        summary,
        sup,
        table,
        tbody,
        td,
        template,
        // textarea,
        tfoot,
        th,
        thead,
        time,
        // title,
        tr,
        track,
        u,
        ul,
        var,
        video,
        wbr
    }
}
impl Default for NodeData {
    fn default() -> Self {
        Self {
            parent: Cell::new(None),
            previous_sibling: Cell::new(None),
            next_sibling: Cell::new(None),
            first_child: Cell::new(None),
            last_child: Cell::new(None),
            kind: NodeKind::Element,
            data: Cow::from(""),
            attrs: Vec::new(),
            special: false,
            namespace: Namespace::Html,
        }
    }
}

impl Index<NodeId> for boxcar::Vec<NodeData> {
    type Output = NodeData;

    fn index(&self, index: NodeId) -> &Self::Output {
        &self[index.0.get()]
    }
}

impl<'a> Iterator for Descendants<'a> {
    type Item = Node<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.stack.pop()?;

        for child in next.reverse_children() {
            self.stack.push(child);
        }

        Some(next)
    }
}

impl<'a> Iterator for NodeIter<'a> {
    type Item = Node<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        let node = self.curr.take()?;
        self.curr = (self.next)(node);
        Some(node)
    }
}

impl<'a, I> Selection<I>
where
    I: Iterator<Item = Node<'a>>,
{
    /// Modifies the iterator such that it only yields elements matching the given CSS selector.
    ///
    /// This methods supports a small subset of the CSS selector syntax.
    /// It accepts what the spec calls a [complex selector][complex].
    /// However, pseudo-elements, pseudo-classes (e.g. `:first-child`, `:hover`) and namespaces are not supported.
    ///
    /// [Type], [universal], [class],  [ID] and [attribute] selectors are recognized.
    /// For attribute selectors though, the case-sensitivity flags are not supported.
    ///
    /// [complex]: https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_selectors/Selector_structure#complex_selector
    /// [Type]: https://developer.mozilla.org/en-US/docs/Web/CSS/Type_selectors
    /// [universal]: https://developer.mozilla.org/en-US/docs/Web/CSS/Universal_selectors
    /// [class]: https://developer.mozilla.org/en-US/docs/Web/CSS/Class_selectors
    /// [ID]: https://developer.mozilla.org/en-US/docs/Web/CSS/ID_selectors
    /// [attribute]: https://developer.mozilla.org/en-US/docs/Web/CSS/Attribute_selectors
    pub fn select(mut self, selector: &str) -> Selection<I> {
        let compiled = match CompiledSelector::new(selector) {
            Ok(c) => c,
            Err(err) => panic!("failed to parse selector: {:?}", err),
        };

        self.selector = Some(compiled);
        self
    }
}

impl<'a, I> Iterator for Selection<I>
where
    I: Iterator<Item = Node<'a>>,
{
    type Item = Node<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(selector) = &self.selector {
            loop {
                let next = self.iter.next()?;
                if selector.matches(next) {
                    return Some(next);
                }
            }
        } else {
            self.iter.next()
        }
    }
}

#[cfg(test)]
mod serialization_tests {
    use super::*;

    #[test]
    fn empty_attribute_and_child_iterators() {
        let h = NodeArena::new();

        assert_eq!(h.span(None, None).html(), "<span></span>");

        assert_eq!(h.span([], []).html(), "<span></span>");
    }

    #[test]
    fn serializing_text_in_different_contexts() {
        let h = NodeArena::new();
        // Text is automatically escaped by default
        assert_eq!(
            h.text("hello &\u{a0}<>").html(),
            "hello &amp;&nbsp;&lt;&gt;"
        );
        assert_eq!(
            h.div(None, h.text("hello &\u{a0}<>")).html(),
            "<div>hello &amp;&nbsp;&lt;&gt;</div>"
        );

        // Except for inside certain elements
        assert_eq!(
            h.script(None, "hello &\u{a0}<>").html(),
            "<script>hello &\u{a0}<></script>"
        );
        assert_eq!(
            h.style(None, "hello &\u{a0}<>").html(),
            "<style>hello &\u{a0}<></style>"
        );
        assert_eq!(
            h.iframe(None, "hello &\u{a0}<>").html(),
            "<iframe>hello &\u{a0}<></iframe>"
        );
        assert_eq!(
            h.textarea(None, "hello &\u{a0}<>").html(),
            "<textarea>hello &\u{a0}<></textarea>"
        );
        assert_eq!(
            h.noscript(None, "hello &\u{a0}<>").html(),
            "<noscript>hello &\u{a0}<></noscript>"
        );
    }

    #[test]
    fn serializing_attributes() {
        let h = NodeArena::new();
        assert_eq!(
            h.div([("class", "&\u{a0}<>\"⋈")], None).html(),
            r#"<div class="&amp;&nbsp;&lt;&gt;&quot;⋈"></div>"#
        )
    }

    #[test]
    fn children() {
        let h = NodeArena::new();

        assert_eq!(
            h.div(None, [h.button(None, None)]).html(),
            "<div><button></button></div>"
        );

        assert_eq!(
            h.div(None, h.button(None, None)).html(),
            "<div><button></button></div>"
        );

        assert_eq!(
            h.div(None, Some(h.button(None, None))).html(),
            "<div><button></button></div>"
        );
    }
}

#[cfg(test)]
mod node_tests {
    use crate::parse;

    use super::*;

    #[test]
    #[should_panic = "can only append to fragment and element nodes"]
    fn cannot_append_to_text() {
        let h = NodeArena::new();
        h.text("foo").append(h.text("bar"));
    }

    #[test]
    #[should_panic = "can only prepend to fragment and element nodes"]
    fn cannot_prepend_to_text() {
        let h = NodeArena::new();
        h.text("foo").prepend(h.text("bar"));
    }

    #[test]
    #[should_panic = "can only append to fragment and element nodes"]
    fn cannot_append_to_comment() {
        let h = NodeArena::new();
        let comment = h.new_comment("comment");
        comment.append(h.text("bar"));
    }

    #[test]
    #[should_panic = "can only prepend to fragment and element nodes"]
    fn cannot_prepend_to_comment() {
        let h = NodeArena::new();
        let comment = h.new_comment("comment");
        comment.prepend(h.text("bar"));
    }

    #[test]
    #[should_panic = "can only append to fragment and element nodes"]
    fn cannot_append_to_doctype() {
        let h = NodeArena::new();
        h.doctype().append(h.doctype());
    }

    #[test]
    #[should_panic = "can only prepend to fragment and element nodes"]
    fn cannot_prepend_to_doctype() {
        let h = NodeArena::new();
        h.doctype().prepend(h.doctype());
    }

    #[test]
    #[should_panic = "cannot insert before fragment node"]
    fn cannot_insert_before_fragment() {
        let h = NodeArena::new();
        h.fragment([]).insert_before(h.text("foo"));
    }

    #[test]
    #[should_panic = "cannot insert after fragment node"]
    fn cannot_insert_after_fragment() {
        let h = NodeArena::new();
        h.fragment([]).insert_after(h.text("foo"));
    }
    #[test]
    fn appending_a_sequence_of_nodes_maintains_order() {
        let h = NodeArena::new();

        let parent = h.div(None, None);

        parent.append([h.text("a"), h.text("b"), h.text("c")]);
        parent.prepend([h.text("d"), h.text("e"), h.text("f")]);

        assert_eq!(parent.html(), "<div>defabc</div>");
    }

    #[test]
    fn inserting_a_sequence_of_nodes_maintains_order() {
        let h = NodeArena::new();

        let parent = h.div(None, h.span(None, None));
        let anchor = parent.descendants().select("span").next().unwrap();

        anchor.insert_after([h.text("a"), h.text("b"), h.text("c")]);

        anchor.insert_before([h.text("d"), h.text("e"), h.text("f")]);

        assert_eq!(anchor.html(), "<span></span>");

        assert_eq!(parent.html(), "<div>def<span></span>abc</div>");
    }

    #[test]
    fn prepending_the_first_child_is_the_same_as_appending() {
        let h = NodeArena::new();

        let root1 = h.div(None, None);
        let root2 = h.div(None, None);

        root1.append(h.text("foo"));
        root2.prepend(h.text("foo"));

        assert_eq!(root1.html(), root2.html());
    }

    #[test]
    fn appending_flattens_fragments_of_arbitrary_depth() {
        let h = NodeArena::new();

        let parent = h.div(None, None);
        let frag1 = h.fragment(h.fragment(h.fragment(h.text("text"))));
        let frag2 = h.fragment(h.fragment(h.fragment(h.text("foo"))));
        parent.append(frag1);
        parent.prepend(frag2);
        assert_eq!(parent.html(), "<div>footext</div>");
    }

    #[test]
    fn inserting_flattens_fragments_of_arbitrary_depth() {
        let h = NodeArena::new();
        let root = h.section(None, h.div(None, None));
        let parent = root.descendants().select("div").next().unwrap();
        let frag1 = h.fragment(h.fragment(h.fragment(h.text("text"))));
        let frag2 = h.fragment(h.fragment(h.fragment(h.text("foo"))));
        parent.insert_after(frag1);
        parent.insert_before(frag2);
        assert_eq!(root.html(), "<section>foo<div></div>text</section>");
    }

    #[test]
    fn appending_a_node_with_siblings() {
        let h = NodeArena::new();
        let parent = h.div(None, None);
        let node = h.div(None, None);
        node.insert_after(h.text("after"));
        parent.append(node);
        assert_eq!(parent.html(), "<div><div></div></div>");
    }

    #[test]
    fn detaching_a_node_between_two_siblings_preserves_the_sibling_chain() {
        let h = NodeArena::new();

        let tree = h.div(None, None);

        let a = h.text("a");
        let b = h.text("b");
        let c = h.text("c");

        tree.append([a, b, c]);

        assert_eq!(b.parent(), Some(tree));
        assert_eq!(b.next(), Some(c));
        assert_eq!(b.previous(), Some(a));

        b.detach();

        assert_eq!(a.next(), Some(c));
        assert_eq!(c.previous(), Some(a));

        assert_eq!(b.parent(), None);
        assert_eq!(b.next(), None);
        assert_eq!(b.previous(), None);
    }

    #[test]
    fn detaching_a_parents_last_child() {
        let h = NodeArena::new();
        let root = h.div(None, None);

        let a = h.text("a");
        let b = h.text("b");
        let c = h.text("c");

        root.append([a, b, c]);

        assert_eq!(root.last_child(), Some(c));

        c.detach();

        assert_eq!(root.first_child(), Some(a));
        assert_eq!(root.last_child(), Some(b));
    }

    #[test]
    fn detaching_a_parents_first_child() {
        let h = NodeArena::new();
        let root = h.div(None, None);

        let a = h.text("a");
        let b = h.text("b");
        let c = h.text("c");

        root.append([a, b, c]);

        assert_eq!(root.first_child(), Some(a));

        a.detach();

        assert_eq!(root.first_child(), Some(b));
        assert_eq!(root.last_child(), Some(c));
    }

    #[test]
    fn nodes_are_detached_and_reparented_upon_insertion() {
        let h = NodeArena::new();
        let src = h.div(None, h.a(None, None));
        let target = h.section(None, None);
        target.append(src.children().select("a"));

        assert_eq!(src.html(), "<div></div>");
        assert_eq!(target.html(), "<section><a></a></section>");
    }

    #[test]
    fn deep_copying_nodes_prevents_mutation() {
        let h = NodeArena::new();
        let src = h.div(None, h.a(None, None));
        let target = h.section(None, None);
        target.append(src.deep_copy().children().select("a"));

        assert_eq!(src.html(), "<div><a></a></div>");
        assert_eq!(target.html(), "<section><a></a></section>");
    }

    #[test]
    fn deep_copying_nodes() {
        let h = NodeArena::new();

        // Fragments
        let node = h.fragment([h.div(None, None), h.div(None, None)]);
        let cloned = node.deep_copy();
        assert_eq!(node.html(), "<div></div><div></div>");
        assert_eq!(cloned.html(), "<div></div><div></div>");
        assert_ne!(node, cloned);

        // Elements
        let node = h.section(None, [h.div(None, None), h.div(None, None)]);
        let cloned = node.deep_copy();
        assert_eq!(node.html(), "<section><div></div><div></div></section>");
        assert_eq!(cloned.html(), "<section><div></div><div></div></section>");
        assert_ne!(node, cloned);

        // Text
        let node = h.text("foo");
        let cloned = node.deep_copy();
        assert_eq!(node.html(), "foo");
        assert_eq!(cloned.html(), "foo");
        assert_ne!(node, cloned);
    }

    #[test]
    fn replacing_nodes() {
        let h = NodeArena::new();

        let doc = h.section(None, [h.span(None, h.text("hello"))]);

        assert_eq!(doc.html(), "<section><span>hello</span></section>");

        let text = doc.first_child().and_then(|n| n.first_child()).unwrap();
        text.replace(h.text("bye"));

        assert_eq!(doc.html(), "<section><span>bye</span></section>");
    }

    #[test]
    fn text_content() {
        let h = NodeArena::new();

        let root = parse(
            &h,
            "<div>one <div>two <div>three</div> four</div> five</div>",
        )
        .unwrap();
        assert_eq!(root.text_content(), "one two three four five");

        let root = parse(&h, "<div></div>").unwrap();
        assert_eq!(root.text_content(), "");
    }
}

#[cfg(test)]
mod iter_tests {
    use super::*;
    use crate::parse;

    #[test]
    fn deeply_nested_html() {
        let arena = NodeArena::new();
        let root = parse(
            &arena,
            "<b><b><b><b><b><b><b><b><b><b>gold</b></b></b></b></b></b></b></b></b></b>",
        )
        .unwrap();

        // 10 <b>s + 1 text
        assert_eq!(root.descendants().count(), 11);
    }

    #[test]
    fn following() {
        let h = NodeArena::new();

        let root = parse(&h, "<a></a><a></a><a></a>").unwrap();

        let mut n = 0;
        for c in root.first_child().unwrap().following() {
            n += 1;
            assert_eq!(c.name(), "a");
        }

        assert_eq!(n, 2);
    }

    #[test]
    fn preceding() {
        let h = NodeArena::new();

        let root = parse(&h, "<a></a><a></a><a></a>").unwrap();

        let mut n = 0;
        for c in root.last_child().unwrap().preceding() {
            n += 1;
            assert_eq!(c.name(), "a");
        }

        assert_eq!(n, 2);
    }

    #[test]
    fn ancestors() {
        let h = NodeArena::new();
        let root = h.div(None, [h.div(None, [h.div([("class", "start")], None)])]);

        let mut n = 0;
        for c in root
            .descendants()
            .select(".start")
            .next()
            .unwrap()
            .ancestors()
        {
            n += 1;
            assert_eq!(c.name(), "div")
        }

        assert_eq!(n, 2);
    }
}

#[cfg(test)]
mod selector_tests {
    use super::*;
    use crate::parse;

    #[track_caller]
    fn check<const N: usize>(html: &str, selector: &str, expected: [&str; N]) {
        let arena = NodeArena::new();
        let root = parse(&arena, html).unwrap();
        let matched_elements = root
            .descendants()
            .select(selector)
            .map(|n| n.name().to_string())
            .collect::<Vec<_>>();

        assert_eq!(matched_elements, expected);
    }

    #[test]
    fn universal_selector() {
        check("<a><b><c></c></b></a>", "*", ["a", "b", "c"]);
        check(
            "text<a>in<b>between<c><!--comment--></c><!doctype name></b></a>",
            "*",
            ["a", "b", "c"],
        );
    }

    #[test]
    fn type_selector() {
        check("<a></a><b></b>", "a", ["a"]);
        check("<a></a><b></b>", "A", ["a"]);
    }

    #[test]
    fn descendant_selector() {
        check("<gc></gc><p><c><gc></gc></c></p>", "gc", ["gc", "gc"]);
        check("<gc></gc><p><c><gc></gc></c></p>", "p gc", ["gc"]);
    }

    #[test]
    fn child_selector() {
        check("<gc></gc><p><c><gc></gc></c></p>", "p > gc", []);
        check("<gc></gc><p><c><gc></gc></c></p>", "p > c", ["c"]);
    }

    #[test]
    fn adjacent_selector() {
        check("<a></a><b></b><a></a>", "a", ["a", "a"]);
        check("<a></a><b></b><a></a>", "b + a", ["a"]);
    }

    #[test]
    fn attribute_selectors() {
        check("<a foo></a><b><c foo></c></b>", "[foo]", ["a", "c"]);
        check("<a foo></a><b><c foo></c></b>", "[FOO]", ["a", "c"]);

        check("<a foo></a><b><c foo=bar></c></b>", "[foo=\"bar\"]", ["c"]);
        check(
            "<a foo='rect box'></a><b><c foo='rect'></c></b>",
            "[foo~=\"box\"]",
            ["a"],
        );
        check(
            "<a foo='rect-box'></a><b><c foo='box-rect'></c></b>",
            "[foo|=\"box\"]",
            ["c"],
        );
        check("<a id=one></a><b><c id=two></c></b>", "#two", ["c"]);
        check("<a class=one></a><b><c class=two></c></b>", ".two", ["c"]);
    }
}