htmlite 0.16.0 - Docs.rs

use crate::parser::{Namespace, VOID_ELEMENT_NAMES};
use crate::selector::CompiledSelector;
use std::cell::Cell;
use std::fmt::{self, Debug, Display};
use std::iter::Copied;

/// 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 type NodeRef<'a> = &'a Node<'a>;

/// 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.   
///
/// ```
/// use htmlite::{NodeArena, html};
/// let h = NodeArena::new();
///
/// let src = html!(h, (div (a)));
/// let dst = html!(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></section><a></a>");
/// ```
///
/// When you need to "copy-paste" a node, use [`NodeArena::deep_copy`]
///
/// ```
/// use htmlite::{NodeArena, html};
///
/// let h = NodeArena::new();
///
/// let src = html!(h, (div(a)));
/// let dst = html!(h, (section));
///
/// dst.append(h.deep_copy(src.descendants().select("a").next().unwrap()));
///
/// assert_eq!(src.html(), "<div><a></a></div>");
/// assert_eq!(dst.html(), "<section></section><a></a>");
#[derive(Clone)]
pub struct Node<'a> {
    pub(crate) parent: Cell<Option<NodeRef<'a>>>,
    pub(crate) previous_sibling: Cell<Option<NodeRef<'a>>>,
    pub(crate) next_sibling: Cell<Option<NodeRef<'a>>>,
    pub(crate) first_child: Cell<Option<NodeRef<'a>>>,
    pub(crate) last_child: Cell<Option<NodeRef<'a>>>,
    pub(crate) kind: NodeKind,
    pub(crate) data: &'a str,
    pub(crate) attributes: Cell<&'a [(&'a str, &'a str)]>,
    pub(crate) special: bool,
    pub(crate) namespace: Namespace,
    pub(crate) arena: &'a NodeArena,
}

/// 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.
pub struct NodeArena {
    pub(crate) nodes: bumpalo::Bump,
}

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

pub struct Descendants<'a> {
    stack: Vec<NodeRef<'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 {
        match self.kind {
            NodeKind::Element | NodeKind::Doctype => self.data,
            _ => "",
        }
    }

    /// Returns the node's type.
    pub fn kind(&self) -> NodeKind {
        self.kind
    }

    /// Returns an iterator of this node's attributes.
    pub fn attrs(&self) -> Copied<std::slice::Iter<'_, (&str, &str)>> {
        self.attributes.get().iter().copied()
    }

    /// Sets the value of the given attribute name to the given value.
    ///
    /// If the element has no attribute by this name, a new one is added.
    /// Otherwise, the existing value is updated.
    ///
    /// # Panics
    ///
    /// This method patnics if the `self` is not an [element](NodeKind::Element).
    pub fn set_attr(&self, name: &str, value: &str) {
        if self.kind != NodeKind::Element {
            panic!("only element may update their attributes")
        }

        // Since Nodes are stored a bump allocator, we don't actually update the attribute list.
        // Instead, we create a new attribute list with the right length,
        // copy all the existing attributes over (while performing the update),
        // then replace the existing list.

        let current_attributes = self.attributes.get();

        let new_len = if self.attrs().any(|(k, _)| k == name) {
            current_attributes.len()
        } else {
            current_attributes.len() + 1
        };

        let new_attributes = self.arena.nodes.alloc_slice_fill_with(new_len, |idx| {
            let Some((old_name, old_value)) = current_attributes.get(idx) else {
                // We've gone through all existing attributes without finding one with the given name.
                // idx should be one past the last index of the current list of attributes at this point.
                debug_assert!(idx == current_attributes.len());
                debug_assert!(idx == new_len - 1);
                return self.arena.alloc_attribute((name, value));
            };
            if old_name.eq_ignore_ascii_case(name) {
                (*old_name, self.arena.nodes.alloc_str(value))
            } else {
                (*old_name, *old_value)
            }
        });

        self.attributes.set(new_attributes);
    }

    /// 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> {
        self.attrs()
            .find(|(n, _)| name.eq_ignore_ascii_case(n))
            .map(|(_, v)| v)
    }

    /// 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 => self.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(n.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<NodeRef<'a>> {
        self.parent.get()
    }

    /// Returns a reference to this node's next sibling node.
    pub fn next(&self) -> Option<NodeRef<'a>> {
        self.next_sibling.get()
    }

    /// Returns a reference to this node's previous sibling node.
    pub fn previous(&self) -> Option<NodeRef<'a>> {
        self.previous_sibling.get()
    }

    /// Returns a reference to the first child of this node.
    pub fn first_child(&self) -> Option<NodeRef<'a>> {
        self.first_child.get()
    }

    /// Returns a reference to the last child of this node.
    pub fn last_child(&self) -> Option<NodeRef<'a>> {
        self.last_child.get()
    }

    /// 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>(&'a self, children: I)
    where
        I: IntoIterator<Item = NodeRef<'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>(&'a self, children: I)
    where
        I: IntoIterator<Item = NodeRef<'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<NodeRef<'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>(&'a self, siblings: I)
    where
        I: IntoIterator<Item = NodeRef<'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>(&'a self, siblings: I)
    where
        I: IntoIterator<Item = NodeRef<'a>>,
    {
        if self.kind() == NodeKind::Fragment {
            panic!("cannot insert after fragment node");
        }

        // See comment in Node::prepend
        let mut anchor: Option<NodeRef<'a>> = 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_with(&'a self, other: NodeRef<'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 parent = self.parent.take();
        let previous_sibling = self.previous_sibling.take();
        let next_sibling = self.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 {
            next.previous_sibling.set(previous_sibling);
        } else if let Some(parent) = parent {
            parent.last_child.set(previous_sibling);
        }

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

    fn append_impl(&'a self, child: NodeRef<'a>) {
        child.detach();

        child.parent.set(Some(self));

        // 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) = self.last_child.replace(Some(child)) {
            child.previous_sibling.set(Some(last_child));
            last_child.next_sibling.set(Some(child));
        } else {
            self.first_child.set(Some(child));
        }
    }

    fn prepend_impl(&'a self, child: NodeRef<'a>) {
        child.detach();

        child.parent.set(Some(self));

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

    fn insert_before_impl(&'a self, new_sibling: NodeRef<'a>) {
        new_sibling.detach();
        new_sibling.parent.set(self.parent.get());
        new_sibling.next_sibling.set(Some(self));

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

    fn insert_after_impl(&'a self, new_sibling: NodeRef<'a>) {
        new_sibling.detach();

        new_sibling.parent.set(self.parent.get());
        new_sibling.previous_sibling.set(Some(self));

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

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

    pub(crate) fn empty(arena: &'a NodeArena, kind: NodeKind) -> Node<'a> {
        Node {
            arena,
            kind,
            data: "",
            attributes: Cell::new(&[]),
            namespace: Namespace::Html,
            special: false,
            parent: Cell::new(None),
            previous_sibling: Cell::new(None),
            next_sibling: Cell::new(None),
            first_child: Cell::new(None),
            last_child: Cell::new(None),
        }
    }
}

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

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

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

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

impl Eq for Node<'_> {}

impl<'a> Debug for Node<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Node")
            .field("kind", &self.kind)
            .field("data", &self.data)
            .field("attributes", &self.attributes)
            .field("special", &self.special)
            .field("parent", &self.parent.get().map(|p| p as *const Node<'a>))
            .field(
                "previous_sibling",
                &self.previous_sibling.get().map(|p| p as *const Node<'a>),
            )
            .field(
                "next_sibling",
                &self.next_sibling.get().map(|p| p as *const Node<'a>),
            )
            .field(
                "first_child",
                &self.first_child.get().map(|p| p as *const Node<'a>),
            )
            .field(
                "last_child",
                &self.last_child.get().map(|p| p as *const Node<'a>),
            )
            .finish()
    }
}

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

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

                for c in self.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, "<{}", self.data)?;
                if !self.attributes.get().is_empty() {
                    for (name, value) in self.attrs() {
                        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 self.namespace == Namespace::Html && VOID_ELEMENT_NAMES.contains(&self.data) {
                    return write!(f, ">");
                }

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

                write!(f, ">")?;

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

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

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

impl NodeArena {
    /// Returns an empty storage location for parsed nodes.
    pub fn new() -> NodeArena {
        NodeArena {
            nodes: bumpalo::Bump::new(),
        }
    }

    /// Returns a new [element](crate::NodeKind::Element) node with the given name and attributes.
    pub fn tag<'attr, A>(&self, tag: &str, attributes: A) -> NodeRef<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
        <A as IntoIterator>::IntoIter: ExactSizeIterator,
    {
        self.new_element(tag, attributes, Namespace::Html)
    }

    /// Returns a new [doctype](crate::NodeKind::Doctype) "html" node.
    pub fn doctype(&self) -> NodeRef<'_> {
        self.new_doctype("html")
    }

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

    /// Returns a new text node with the given contents.
    ///
    /// Serializing the node to HTML will escape its contents.   
    pub fn text(&self, text: &str) -> NodeRef<'_> {
        self.new_text(text, false)
    }

    /// Returns a new text node with the given contents.
    ///
    /// Serializing the node to HTML will _not_ escape its contents.
    /// It will be output verbatim.
    pub fn raw_text(&self, text: &str) -> NodeRef<'_> {
        self.new_text(text, true)
    }

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

    pub(crate) fn new_element<'attr, A>(
        &self,
        tag: &str,
        attributes: A,
        namespace: Namespace,
    ) -> NodeRef<'_>
    where
        A: IntoIterator<Item = (&'attr str, &'attr str)>,
        <A as IntoIterator>::IntoIter: ExactSizeIterator,
    {
        let tag = self.nodes.alloc_str(tag);
        let attributes = self.attributes(attributes);
        self.nodes.alloc(Node {
            data: tag,
            attributes: Cell::new(attributes),
            namespace,
            ..Node::empty(self, NodeKind::Element)
        })
    }

    pub(crate) fn new_comment(&self, comment: &str) -> NodeRef<'_> {
        self.nodes.alloc(Node {
            data: self.nodes.alloc_str(comment),
            ..Node::empty(self, NodeKind::Comment)
        })
    }

    pub(crate) fn new_text(&self, text: &str, serialize_verbatim: bool) -> NodeRef<'_> {
        self.nodes.alloc(Node {
            data: self.nodes.alloc_str(text),
            special: serialize_verbatim,
            ..Node::empty(self, NodeKind::Text)
        })
    }

    pub(crate) fn new_doctype(&self, name: &str) -> NodeRef<'_> {
        self.nodes.alloc(Node {
            data: self.nodes.alloc_str(name),
            ..Node::empty(self, NodeKind::Doctype)
        })
    }

    pub(crate) fn attributes<'attr, 'arena, I>(
        &'arena self,
        attrs: I,
    ) -> &'arena [(&'arena str, &'arena str)]
    where
        I: IntoIterator<Item = (&'attr str, &'attr str)>,
        <I as IntoIterator>::IntoIter: ExactSizeIterator,
    {
        let allocated_attrs = attrs
            .into_iter()
            .map(|(name, value)| self.alloc_attribute((name, value)));
        self.nodes.alloc_slice_fill_iter(allocated_attrs)
    }

    pub(crate) fn alloc_attribute<'attr, 'arena>(
        &'arena self,
        attr: (&'attr str, &'attr str),
    ) -> (&'arena str, &'arena str) {
        let name = self.nodes.alloc_str(attr.0);
        let value = self.nodes.alloc_str(attr.1);
        name.make_ascii_lowercase();
        (name as &str, value as &str)
    }
}

impl<'a> Iterator for Descendants<'a> {
    type Item = NodeRef<'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 = NodeRef<'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 = NodeRef<'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 = NodeRef<'a>>,
{
    type Item = NodeRef<'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 node_tests {
    use crate::{html, parse};

    use super::*;

    #[test]
    #[should_panic = "can only append to fragment and element nodes"]
    fn cannot_append_to_text() {
        let h = NodeArena::new();
        h.new_text("foo", false).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.new_text("foo", false).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.new_doctype("html").append(h.text("foo"));
    }

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

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

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

    #[test]
    #[should_panic = "only element may update their attributes"]
    fn cannot_update_attr_on_fragment_nodes() {
        let h = NodeArena::new();
        html!(h).set_attr("blah", "blah");
    }

    #[test]
    #[should_panic = "only element may update their attributes"]
    fn cannot_update_attr_on_text_nodes() {
        let h = NodeArena::new();
        let text = h.text("blah");
        text.set_attr("blah", "blah");
    }

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

        // Updating an attribute
        let node = h.tag("div", []);
        assert_eq!(node.attr("one"), None);
        node.set_attr("one", "1");
        assert_eq!(node.attr("one"), Some("1"));
        node.set_attr("one", "2");
        assert_eq!(node.attr("one"), Some("2"));

        // Adding the same attribute with a different case shouldn't create a new one.
        let node = h.tag("div", []);
        node.set_attr("ONE", "1");
        node.set_attr("one", "2");
        assert_eq!(node.attrs().count(), 1);
    }

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

        let parent = h.tag("div", []);
        parent.append(html!(h, (text "a") (text "b") (text "c")));
        parent.prepend(html!(h, (text "d") (text "e") (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.tag("div", []);
        let anchor = h.tag("span", []);
        parent.append(anchor);

        anchor.insert_after(html!(h, (text "a") (text "b") (text "c")));
        anchor.insert_before(html!(h, (text "d") (text "e") (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.tag("div", []);
        let root2 = h.tag("div", []);

        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.tag("div", []);

        let frag1 = h.fragment(h.fragment(h.fragment(html!(h, (text "text")))));
        let frag2 = h.fragment(h.fragment(h.fragment(html!(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 parent = h.tag("section", []);
        let anchor = h.tag("div", []);
        parent.append(anchor);

        let frag1 = h.fragment(h.fragment(html!(h, (text "text"))));
        let frag2 = h.fragment(h.fragment(html!(h, (text "foo"))));

        anchor.insert_after(frag1);
        anchor.insert_before(frag2);

        assert_eq!(parent.html(), "<section>foo<div></div>text</section>");
    }

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

        let parent = h.tag("div", []);
        let anchor = h.tag("div", []);
        anchor.insert_after(h.text("after"));

        parent.append(anchor);

        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.tag("div", []);

        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.tag("div", []);

        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.tag("div", []);

        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 = html!(h, (div(a)));
        let target = html!(h, (section));

        target.append(src.descendants().select("a"));

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

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

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

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

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

        // Elements
        let node = html!(h, (section(div)(div))).first_child().unwrap();
        let cloned = h.deep_copy(node);
        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 = h.deep_copy(node);
        assert_eq!(node.html(), "foo");
        assert_eq!(cloned.html(), "foo");
        assert_ne!(node, cloned);
    }

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

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

        text.replace_with(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 grandparent = h.tag("div", []);
        let parent = h.tag("div", []);
        let child = h.tag("div", []);
        grandparent.append(parent);
        parent.append(child);

        let mut n = 0;
        for c in child.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"]);

        // Regression: The hyphen-suffixed matcher was incorrectly assuming that the attribute would match only what was before the first hyphen
        check(
            "<a class='markdown-alert-warning'></a>",
            "[class|=markdown-alert]",
            ["a"],
        );
    }
}