htmlite 0.19.0 - Docs.rs

use crate::parser::{Namespace, VOID_ELEMENT_NAMES};
use crate::selector::CompiledSelector;
use std::ops::Deref;
use std::{
    cell::RefCell,
    collections::BTreeMap,
    fmt::Display,
    rc::{Rc, Weak},
};

// TODO: Document invariants in the tree operations using debug_asserts
// Ideas: When last child is None, first_child is also None. Vice-versa
// In insert_before, it's essential that we are not trying to insert a node as its sibling.
// This would runtime panic because we'd be taking a uniq ref and a shared ref at the same time to set the parent.
//
// TODO: Update examples. NodeArena is no more.

/// 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,
}

/// A handle to a node in a DOM-like tree.
///
/// # Ownership model
///
/// A `Node` holds strong references (i.e. [`Rc`]) to its children.
/// Parent links on the other hand are weak (i.e. [`Weak`]).
/// This avoids reference cycles, but also means a node does not keep its ancestors alive.
/// If ancestor traversal (for example [`Node::parent`] or [`Node::ancestors`]) matters, keep a strong
/// handle to a root or ancestor node for at least that long.
///
/// ```
/// use htmlite::{html, select, tag};
///
/// let leaf = tag("span", [], []);
/// let root = html!(
///     (div
///         (section
///             (> &leaf)
///         )
///     )
/// );
///
/// assert_eq!(select("*", leaf.ancestors()).count(), 2);
///
/// drop(root);
/// assert_eq!(leaf.ancestors().count(), 0);
/// ```
///
/// # Cloning
///
/// `Node` is cheap to clone; it only increments a reference count.
/// It maintains the Node's identity: a given node compares equal to nodes cloned from it.
/// Use [`deep_copy`] if you need to actually duplicate the tree rooted at a node.
#[derive(Clone)]
pub struct Node(Rc<RefCell<NodeInner>>);

struct NodeInner {
    next_sibling: Option<Rc<RefCell<NodeInner>>>,
    first_child: Option<Rc<RefCell<NodeInner>>>,
    parent: Option<Weak<RefCell<NodeInner>>>,
    previous_sibling: Option<Weak<RefCell<NodeInner>>>,
    last_child: Option<Weak<RefCell<NodeInner>>>,
    kind: NodeKind,
    data: Rc<str>,
    attributes: BTreeMap<Rc<str>, Rc<str>>,
    flags: NodeFlags,
    namespace: Namespace,
}

impl Node {
    /// 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) -> Rc<str> {
        match self.0.borrow().kind {
            NodeKind::Element | NodeKind::Doctype => self.0.borrow().data.clone(),
            _ => Rc::<str>::from(""),
        }
    }

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

    /// 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 panics if `self` is not an [element](NodeKind::Element).
    pub fn set_attribute(&self, name: &str, value: &str) {
        if self.kind() != NodeKind::Element {
            panic!("only elements may update their attributes")
        }

        let lowered = Rc::from(name.to_ascii_lowercase());
        self.0
            .borrow_mut()
            .attributes
            .insert(lowered, Rc::from(value));
    }

    /// 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 get_attribute(&self, name: &str) -> Option<Rc<str>> {
        let lowered = name.to_ascii_lowercase();
        self.0.borrow().attributes.get(lowered.as_str()).cloned()
    }

    /// Returns the attribute list for this node as sequence of (name, value) pairs.
    pub fn get_attributes(&self) -> Vec<(Rc<str>, Rc<str>)> {
        self.0
            .borrow()
            .attributes
            .iter()
            .map(|(k, v)| (k.clone(), v.clone()))
            .collect()
    }

    /// Returns a reference to the parent node if any.
    pub fn parent(&self) -> Option<Node> {
        self.0
            .borrow()
            .parent
            .as_ref()
            .and_then(|w| w.upgrade())
            .map(Node)
    }

    /// Returns a reference to this node's next sibling node.
    pub fn next(&self) -> Option<Node> {
        self.0
            .borrow()
            .next_sibling
            .as_ref()
            .map(|rc| Node(rc.clone()))
    }

    /// Returns a reference to this node's previous sibling node.
    pub fn previous(&self) -> Option<Node> {
        self.0
            .borrow()
            .previous_sibling
            .as_ref()
            .and_then(|w| w.upgrade())
            .map(Node)
    }

    /// Returns a reference to the first child of this node.
    pub fn first_child(&self) -> Option<Node> {
        self.0
            .borrow()
            .first_child
            .as_ref()
            .map(|rc| Node(rc.clone()))
    }

    /// Returns a reference to the last child of this node.
    pub fn last_child(&self) -> Option<Node> {
        self.0
            .borrow()
            .last_child
            .as_ref()
            .and_then(|w| w.upgrade())
            .map(Node)
    }

    /// 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) -> NodeIterator {
        NodeIterator {
            current: self.first_child(),
            step: Node::next,
        }
    }

    /// Returns an iterator of references to child nodes in reverse order.
    pub fn reverse_children(&self) -> NodeIterator {
        NodeIterator {
            current: self.last_child(),
            step: Node::previous,
        }
    }

    /// Returns an iterator of references to the nodes after this node.
    pub fn following(&self) -> NodeIterator {
        NodeIterator {
            current: self.next(),
            step: Node::next,
        }
    }

    /// Returns an iterator of references to the nodes before this node.
    pub fn preceding(&self) -> NodeIterator {
        NodeIterator {
            current: self.previous(),
            step: Node::previous,
        }
    }

    /// Returns an iterator of references to ancestor nodes.
    ///
    /// If the markup came from a string, the top-level elements will be wrapped in a [`NodeKind::Fragment`] node.
    pub fn ancestors(&self) -> NodeIterator {
        NodeIterator {
            current: self.parent(),
            step: Node::parent,
        }
    }

    /// Returns an iterator of references to descendant nodes.
    ///
    /// This is a pre-order, depth-first traversal; parent nodes appear before their children.
    pub fn descendants(&self) -> Descendants {
        Descendants {
            stack: self.first_child().into_iter().collect(),
        }
    }

    /// Returns an iterator that performs a depth-first walk of the subtree rooted at this node.
    /// It yields each node twice, once as [`Frame::Open`] before visiting its children,
    /// and a second time as [`Frame::Close`] after visiting its children.
    pub fn walk(&self) -> Walk {
        Walk {
            stack: vec![Frame::Open(self.clone())],
        }
    }

    /// 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.
    ///
    /// It also panics if insertion would create a cycle (for example, trying to append `self` or one of `self`'s ancestors into `self`).
    pub fn append(&self, children: impl IntoIterator<Item = Node>) {
        assert!(
            matches!(self.kind(), NodeKind::Element | NodeKind::Fragment),
            "can only append to fragment and element nodes"
        );

        let children = collect_and_validate_for_insertion(self, children);
        for child in children {
            self.append_impl(child);
        }
    }

    /// 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.
    ///
    /// It also panics if insertion would create a cycle.
    pub fn prepend(&self, children: impl IntoIterator<Item = Node>) {
        assert!(
            matches!(self.kind(), NodeKind::Element | NodeKind::Fragment),
            "can only prepend to fragment and element nodes"
        );

        // Implement prepend in terms of insert_before if there is a first child.
        // Otherwise, the node is empty, and prepending is the same as appending.
        if let Some(anchor) = self.first_child() {
            anchor.insert_before(children)
        } else {
            self.append(children);
        }
    }

    /// Inserts `siblings` before this node.
    ///
    /// # Panics
    ///
    /// This method panics if `self` is a [Fragment](NodeKind::Fragment).
    ///
    /// It also panics if insertion would create a cycle (for example, trying to insert `self` or one of `self`'s ancestors before `self`).
    pub fn insert_before(&self, siblings: impl IntoIterator<Item = Node>) {
        assert!(
            self.kind() != NodeKind::Fragment,
            "cannot insert before fragment node",
        );

        let siblings = collect_and_validate_for_insertion(self, siblings);
        for sibling in siblings {
            self.insert_before_impl(sibling);
        }
    }

    /// Inserts `siblings` after this node.
    ///
    /// # Panics
    ///
    /// This method panics if `self` is a [Fragment](NodeKind::Fragment).
    ///
    /// It also panics if insertion would create a cycle (for example, trying to insert `self` or one of `self`'s ancestors after `self`).
    pub fn insert_after(&self, siblings: impl IntoIterator<Item = Node>) {
        assert!(
            self.kind() != NodeKind::Fragment,
            "cannot insert after fragment node",
        );

        let siblings = collect_and_validate_for_insertion(self, siblings);

        let mut anchor = self.clone();
        for sibling in siblings {
            anchor.insert_after_impl(sibling.clone());
            anchor = sibling;
        }
    }

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

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

    /// 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.0.borrow().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.0.borrow().data);
                    }
                }
                out
            }
            NodeKind::Doctype => String::new(),
        }
    }

    /// Orphans this node by detaching it from its parent and siblings.
    ///
    /// Children are not affected.
    pub fn detach(&self) {
        let parent = self.0.borrow_mut().parent.take().and_then(|w| w.upgrade());
        let previous_sibling = self.0.borrow_mut().previous_sibling.take();
        let next_sibling = self.0.borrow_mut().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.borrow_mut().previous_sibling = previous_sibling.clone();
        } else if let Some(parent) = &parent {
            parent.borrow_mut().last_child = previous_sibling.clone();
        }

        if let Some(prev) = previous_sibling.and_then(|w| w.upgrade()) {
            prev.borrow_mut().next_sibling = next_sibling.clone();
        } else if let Some(parent) = &parent {
            parent.borrow_mut().first_child = next_sibling.clone();
        }
    }

    pub(crate) fn namespace(&self) -> Namespace {
        self.0.borrow().namespace
    }

    fn append_impl(&self, child: Node) {
        child.detach();
        child.0.borrow_mut().parent = Some(Rc::downgrade(&self.0));

        // 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.
        // Note that Option::replace() will unconditionally set `child` as self's last child.

        let last_child = self
            .0
            .borrow_mut()
            .last_child
            .replace(Rc::downgrade(&child.0))
            .and_then(|w| w.upgrade());

        if let Some(last_child) = last_child {
            child.0.borrow_mut().previous_sibling = Some(Rc::downgrade(&last_child));
            last_child.borrow_mut().next_sibling = Some(child.0);
        } else {
            self.0.borrow_mut().first_child = Some(child.0);
        }
    }

    fn insert_before_impl(&self, new_sibling: Node) {
        new_sibling.detach();
        new_sibling.0.borrow_mut().parent = self.0.borrow().parent.clone();
        new_sibling.0.borrow_mut().next_sibling = Some(self.0.clone());

        let previous_sibling = self
            .0
            .borrow_mut()
            .previous_sibling
            .replace(Rc::downgrade(&new_sibling.0))
            .and_then(|w| w.upgrade());

        if let Some(prev) = previous_sibling {
            new_sibling.0.borrow_mut().previous_sibling = Some(Rc::downgrade(&prev));
            prev.borrow_mut().next_sibling = Some(new_sibling.0);
        } else if let Some(parent) = self.0.borrow().parent.as_ref().and_then(|w| w.upgrade()) {
            parent.borrow_mut().first_child = Some(new_sibling.0)
        }
    }

    fn insert_after_impl(&self, new_sibling: Node) {
        new_sibling.detach();
        new_sibling.0.borrow_mut().parent = self.0.borrow().parent.clone();
        new_sibling.0.borrow_mut().previous_sibling = Some(Rc::downgrade(&self.0));

        let next_sibling = self
            .0
            .borrow_mut()
            .next_sibling
            .replace(new_sibling.0.clone());

        if let Some(next) = next_sibling {
            next.borrow_mut().previous_sibling = Some(Rc::downgrade(&new_sibling.0));
            new_sibling.0.borrow_mut().next_sibling = Some(next);
        } else if let Some(parent) = self.0.borrow().parent.as_ref().and_then(|w| w.upgrade()) {
            parent.borrow_mut().last_child = Some(Rc::downgrade(&new_sibling.0))
        }
    }
}

/// Nodes are actually pointers.
/// Two nodes are considered equal if they point to the same structure on the heap.
impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}

impl Eq for Node {}

impl IntoIterator for Node {
    type Item = Node;

    type IntoIter = std::iter::Once<Self::Item>;

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

impl IntoIterator for &Node {
    type Item = Node;

    type IntoIter = std::iter::Once<Self::Item>;

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

impl std::fmt::Debug for Node {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Node")
            .field("kind", &self.0.borrow().kind)
            .field("data", &self.0.borrow().data)
            .field("attributes", &self.0.borrow().attributes)
            .field("flags", &self.0.borrow().flags)
            .field("parent", &self.parent().map(|n| n.0.as_ptr()))
            .field("previous", &self.previous().map(|n| n.0.as_ptr()))
            .field("next", &self.next().map(|n| n.0.as_ptr()))
            .field("first_child", &self.first_child().map(|n| n.0.as_ptr()))
            .field("last_child", &self.last_child().map(|n| n.0.as_ptr()))
            .finish()
    }
}
impl Display for Node {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for frame in self.walk() {
            match frame {
                Frame::Open(node) => match node.kind() {
                    NodeKind::Comment => {
                        write!(f, "<!--{}-->", node.0.borrow().data)?;
                    }
                    NodeKind::Doctype => {
                        write!(f, "<!DOCTYPE {}>", node.0.borrow().data)?;
                    }
                    NodeKind::Fragment => {}
                    NodeKind::Text => {
                        if node.0.borrow().flags.has(NodeFlags::VERBATIM_TEXT) {
                            write!(f, "{}", node.0.borrow().data)?;
                            continue;
                        }

                        if !node.0.borrow().data.contains(['&', '\u{a0}', '<', '>']) {
                            write!(f, "{}", node.0.borrow().data)?;
                            continue;
                        }

                        for c in node.0.borrow().data.chars() {
                            match c {
                                '&' => write!(f, "&amp;")?,
                                '\u{a0}' => write!(f, "&nbsp;")?,
                                '<' => write!(f, "&lt;")?,
                                '>' => write!(f, "&gt;")?,
                                c => write!(f, "{c}")?,
                            }
                        }
                    }
                    NodeKind::Element => {
                        write!(f, "<{}", node.0.borrow().data)?;
                        if !node.0.borrow().attributes.is_empty() {
                            for (name, value) in &node.0.borrow().attributes {
                                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 node.0.borrow().namespace == Namespace::Html
                            && VOID_ELEMENT_NAMES.contains(&node.0.borrow().data.deref())
                        {
                            write!(f, ">")?;
                            continue;
                        }

                        if node.0.borrow().namespace == Namespace::Foreign
                            && node.0.borrow().flags.has(NodeFlags::SELF_CLOSING)
                        {
                            write!(f, "/>")?;
                            continue;
                        }

                        write!(f, ">")?;
                    }
                },
                Frame::Close(node) => {
                    if node.kind() == NodeKind::Element {
                        let n = node.0.borrow();

                        let is_void = n.namespace == Namespace::Html
                            && VOID_ELEMENT_NAMES.contains(&n.data.deref());

                        let is_self_closing = n.namespace == Namespace::Foreign
                            && n.flags.has(NodeFlags::SELF_CLOSING);

                        if !is_void && !is_self_closing {
                            write!(f, "</{}>", n.data)?;
                        }
                    }
                }
            };
        }

        Ok(())
    }
}

/// Returns a new text node with the given contents.
///
/// Serializing the node to HTML will escape its contents.   
pub fn text(text: impl Display) -> Node {
    create_node(NodeKind::Text, Rc::from(text.to_string()))
}

/// 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(text: impl Display) -> Node {
    let n = create_node(NodeKind::Text, Rc::from(text.to_string()));
    n.0.borrow_mut().flags.set(NodeFlags::VERBATIM_TEXT);
    n
}

/// Returns a new comment node with the given contents.
pub fn comment(content: &str) -> Node {
    create_node(NodeKind::Comment, Rc::from(content))
}

/// Returns a new [doctype](crate::NodeKind::Doctype) "html" node.
pub fn doctype() -> Node {
    new_doctype("html")
}

/// Returns a new [fragment](crate::NodeKind::Fragment) with the given nodes.
pub fn fragment(children: impl IntoIterator<Item = Node>) -> Node {
    let n = create_node(NodeKind::Fragment, Rc::from(""));
    n.append(children);
    n
}

/// Returns a new [element](crate::NodeKind::Element) node with the given name and attributes.
pub fn tag(
    name: &str,
    attrs: impl IntoIterator<Item = (String, String)>,
    children: impl IntoIterator<Item = Node>,
) -> Node {
    new_element(
        name,
        Namespace::Html,
        NodeFlags::new(NodeFlags::NONE),
        attrs,
        children,
    )
}

/// Marks `root` and all descendant element nodes as belonging to a foreign namespace.
///
/// This is useful when constructing XML-like trees programmatically, so HTML void-element
/// serialization rules do not interfere.
pub fn mark_foreign_subtree(root: &Node) {
    for node in root.into_iter().chain(root.descendants()) {
        if node.kind() == NodeKind::Element {
            node.0.borrow_mut().namespace = Namespace::Foreign;
        }
    }
}

/// Creates a deep-copy of `node` by recursively building a tree out of deep copies of its children.
pub fn deep_copy(node: &Node) -> Node {
    match &node.kind() {
        NodeKind::Fragment => {
            let new_chunk = fragment([]);
            for child in node.children() {
                new_chunk.append(deep_copy(&child));
            }
            new_chunk
        }
        NodeKind::Comment => comment(&node.0.borrow().data),
        NodeKind::Doctype => new_doctype(&node.0.borrow().data),
        NodeKind::Text if node.0.borrow().flags.has(NodeFlags::VERBATIM_TEXT) => {
            raw_text(&node.0.borrow().data)
        }
        NodeKind::Text => text(&node.0.borrow().data),
        NodeKind::Element => {
            let new_element = new_element(
                &node.name(),
                node.namespace(),
                node.0.borrow().flags,
                node.get_attributes()
                    .iter()
                    .map(|(k, v)| (k.to_string(), v.to_string())),
                [],
            );
            for child in node.children() {
                new_element.append(deep_copy(&child))
            }
            new_element
        }
    }
}

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

impl NodeFlags {
    pub(crate) const NONE: u8 = 0;
    pub(crate) const VERBATIM_TEXT: u8 = 1 << 0;
    pub(crate) const SELF_CLOSING: u8 = 2;

    pub(crate) fn new(flags: u8) -> NodeFlags {
        NodeFlags(flags)
    }

    fn set(&mut self, flag: u8) {
        self.0 |= flag;
    }

    fn has(&self, flag: u8) -> bool {
        self.0 & flag != 0
    }
}

pub struct NodeIterator {
    current: Option<Node>,
    step: fn(&Node) -> Option<Node>,
}

impl Iterator for NodeIterator {
    type Item = Node;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.current.take()?;
        // Note: the iterator steps before returning the current node.
        // This turns out to be crucial.
        // It means that consumers of the iterator can freely detach the returned node and iteration won't be affected.
        // This manifests when using flatten() during node insertion.
        self.current = (self.step)(&current);
        Some(current)
    }
}

// See [`Node::descendants`]
pub struct Descendants {
    stack: Vec<Node>,
}

impl Iterator for Descendants {
    type Item = Node;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.stack.pop()?;
        if let Some(next) = current.next() {
            self.stack.push(next);
        }
        if let Some(child) = current.first_child() {
            self.stack.push(child);
        }
        Some(current)
    }
}

// See [`Node::walk`]
#[derive(Debug, Clone)]
pub enum Frame {
    Open(Node),
    Close(Node),
}

// See [`Node::walk`]
pub struct Walk {
    stack: Vec<Frame>,
}

impl Iterator for Walk {
    type Item = Frame;
    fn next(&mut self) -> Option<Self::Item> {
        let current = self.stack.pop()?;
        if let Frame::Open(node) = &current {
            self.stack.push(Frame::Close(node.clone()));
            self.stack.extend(node.reverse_children().map(Frame::Open));
        }
        Some(current)
    }
}

/// An iterator of nodes matching a particular css selector.
///
/// See [`select`].
pub struct Selection<I> {
    iter: I,
    selector: CompiledSelector,
}

/// Returns a new iterator that only yields elements from `iter` matching the given CSS selector.
///
/// This method 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<I: IntoIterator<Item = Node>>(selector: &str, iter: I) -> Selection<I::IntoIter> {
    let compiled = match CompiledSelector::new(selector) {
        Ok(c) => c,
        Err(err) => panic!("failed to parse selector: {:?}", err),
    };

    Selection {
        selector: compiled,
        iter: iter.into_iter(),
    }
}

// See [`select`].
impl<I> Iterator for Selection<I>
where
    I: Iterator<Item = Node>,
{
    type Item = Node;

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

pub(crate) fn create_node(kind: NodeKind, data: Rc<str>) -> Node {
    let cell = RefCell::new(NodeInner {
        next_sibling: None,
        first_child: None,
        parent: None,
        previous_sibling: None,
        last_child: None,
        kind,
        data,
        namespace: Namespace::Html,
        attributes: BTreeMap::new(),
        flags: NodeFlags::new(NodeFlags::NONE),
    });
    Node(Rc::new(cell))
}

pub(crate) fn new_doctype(name: &str) -> Node {
    create_node(NodeKind::Doctype, Rc::from(name))
}

pub(crate) fn new_element(
    name: &str,
    namespace: Namespace,
    flags: NodeFlags,
    attrs: impl IntoIterator<Item = (String, String)>,
    children: impl IntoIterator<Item = Node>,
) -> Node {
    let n = create_node(NodeKind::Element, Rc::from(name));
    for (k, v) in attrs {
        n.0.borrow_mut().attributes.insert(Rc::from(k), Rc::from(v));
    }
    n.0.borrow_mut().namespace = namespace;
    n.0.borrow_mut().flags = flags;
    n.append(children);
    n
}

// When inserting fragments, we need to flatten them to lists of their child nodes.
// By doing this at insertion time, I guarantee that the constructed tree never has fragments within.
fn flatten(n: &Node) -> NodeIterator {
    match n.kind() {
        NodeKind::Fragment => NodeIterator {
            current: n.first_child(),
            step: Node::next,
        },
        _ => NodeIterator {
            current: Some(n.clone()),
            step: |_| None,
        },
    }
}

fn assert_no_cycle(destination: &Node, incoming: &Node) {
    let mut current = Some(destination.clone());
    while let Some(node) = current {
        if node == *incoming {
            panic!("insertion would create a cycle");
        }
        current = node.parent();
    }
}

// We need to ensure we are never inserting or appending a node to itself or any of its descendants.
// We do this separately to ensure the node tree is not modified if we end up panicking.
fn collect_and_validate_for_insertion(
    destination: &Node,
    nodes: impl IntoIterator<Item = Node>,
) -> Vec<Node> {
    let flattened: Vec<_> = nodes.into_iter().flat_map(|n| flatten(&n)).collect();
    for node in &flattened {
        assert_no_cycle(destination, node);
    }
    flattened
}

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

    #[test]
    fn huh() {
        let node = create_node(NodeKind::Element, Rc::from("hello"));
        node.0.borrow_mut().next_sibling = Some(node.0.clone());
        node.detach();
    }
}

#[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() {
        text("foo").append(text("bar"));
    }

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

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

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

    #[test]
    #[should_panic = "can only append to fragment and element nodes"]
    fn cannot_append_to_doctype() {
        doctype().append(text("foo"));
    }

    #[test]
    #[should_panic = "can only prepend to fragment and element nodes"]
    fn cannot_prepend_to_doctype() {
        doctype().prepend(text("foo"));
    }

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

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

    #[test]
    #[should_panic = "only elements may update their attributes"]
    fn cannot_update_attr_on_fragment_nodes() {
        html!().set_attribute("blah", "blah");
    }

    #[test]
    #[should_panic = "only elements may update their attributes"]
    fn cannot_update_attr_on_text_nodes() {
        let text = text("blah");
        text.set_attribute("blah", "blah");
    }

    #[test]
    #[should_panic = "insertion would create a cycle"]
    fn cannot_append_ancestor_into_descendant() {
        let root = tag("div", [], []);
        let child = tag("span", [], []);
        root.append(&child);
        child.append(root);
    }

    #[test]
    #[should_panic = "insertion would create a cycle"]
    fn cannot_insert_before_self() {
        let node = tag("div", [], []);
        node.insert_before(&node);
    }

    #[test]
    #[should_panic = "insertion would create a cycle"]
    fn cannot_insert_after_self() {
        let node = tag("div", [], []);
        node.insert_after(&node);
    }

    #[test]
    #[should_panic = "insertion would create a cycle"]
    fn cannot_insert_ancestor_as_sibling() {
        let root = tag("div", [], []);
        let mid = tag("section", [], []);
        let leaf = tag("span", [], []);
        root.append(&mid);
        mid.append(&leaf);

        leaf.insert_before(root);
    }

    #[test]
    fn setting_attributes() {
        // Updating an attribute
        let node = tag("div", [], []);
        assert_eq!(node.get_attribute("one"), None);
        node.set_attribute("one", "1");
        assert_eq!(node.get_attribute("one").as_deref(), Some("1"));
        node.set_attribute("one", "2");
        assert_eq!(node.get_attribute("one").as_deref(), Some("2"));

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

    #[test]
    fn appending_a_sequence_of_nodes_maintains_order() {
        let parent = tag("div", [], []);
        parent.append(html!((text "a") (text "b") (text "c")));
        parent.prepend(html!((text "d") (text "e") (text "f")));

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

    #[test]
    fn inserting_a_sequence_of_nodes_maintains_order() {
        let parent = tag("div", [], []);
        let anchor = tag("span", [], []);
        parent.append(anchor.clone());

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

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

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

    #[test]
    fn appending_flattens_fragments_of_arbitrary_depth() {
        let parent = tag("div", [], []);

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

        parent.append(frag1);
        parent.prepend(frag2);

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

    #[test]
    fn inserting_flattens_fragments_of_arbitrary_depth() {
        let parent = tag("section", [], []);
        let anchor = tag("div", [], []);
        parent.append(anchor.clone());

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

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

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

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

        b.detach();

        assert_eq!(a.next(), Some(c.clone()));
        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 root = tag("div", [], []);

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

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

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

        c.detach();

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

    #[test]
    fn detaching_a_parents_first_child() {
        let root = tag("div", [], []);

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

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

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

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

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

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

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

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

    #[test]
    fn deep_copying_nodes() {
        // Fragments
        let node = html!((div)(div));
        let cloned = 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!((section(div)(div))).first_child().unwrap();
        let cloned = 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 = text("foo");
        let cloned = deep_copy(&node);
        assert_eq!(node.html(), "foo");
        assert_eq!(cloned.html(), "foo");
        assert_ne!(node, cloned);
    }

    #[test]
    fn replacing_nodes() {
        let t = text("hello");
        let doc = html!((section (span (> &t))));
        assert_eq!(doc.html(), "<section><span>hello</span></section>");

        t.replace_with(text("bye"));

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

    #[test]
    fn text_content() {
        let root = parse("<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("<div></div>").unwrap();
        assert_eq!(root.text_content(), "");
    }
}

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

    #[test]
    fn descendants_visits_all_children_of_fragment() {
        let html = html!((a)(b)(c));

        assert_eq!(html.descendants().count(), 3)
    }

    #[test]
    fn descendants_visits_only_the_subtree_rooted_at_a_particular_element() {
        let html = html!(
            (text "abc")
            (div (div (div)))
            (text "xyz")
        );

        let div = select("div", html.children()).next().unwrap();
        for descendant in div.descendants() {
            assert_eq!(&*descendant.name(), "div");
        }
        assert_eq!(div.descendants().count(), 2);
    }

    #[test]
    fn walking_visits_only_the_subtree_rooted_at_a_particular_element() {
        let html = html!(
            (text "abc")
            (div (div (div)))
            (text "xyz")
        );

        let div = select("div", html.children()).next().unwrap();
        assert_eq!(div.html(), "<div><div><div></div></div></div>");
    }

    #[test]
    fn following() {
        let root = html!((a)(a)(a));

        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 root = html!((a)(a)(a));

        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 child = tag("div", [], []);
        let _root = html!(
            (div
                (div
                    (> &child)
                )
            )

        );

        let mut n = 0;
        // The select filters out the fragment at the very top of the tree.
        for c in select("*", child.ancestors()) {
            n += 1;
            assert_eq!(&*c.name(), "div")
        }

        assert_eq!(n, 2);
    }

    #[test]
    fn ancestors_are_empty_after_dropping_root() {
        let child = tag("div", [], []);
        let root = html!(
            (div
                (div
                    (> &child)
                )
            )
        );

        assert_eq!(select("*", child.ancestors()).count(), 2);
        drop(root);
        assert_eq!(child.ancestors().count(), 0);
    }
}

#[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 root = parse(html).unwrap();
        let matched_elements = select(selector, root.descendants())
            .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"],
        );

        // Regression: The ".CLASS" selector should be translated to a WSSeparated attribute check, not an equality check.
        check("<div class='foo bar'></div>", ".foo", ["div"]);
    }
}

#[cfg(test)]
mod serialization_tests {
    use crate::{html, mark_foreign_subtree, parse};

    #[test]
    fn self_closing_in_foreign_namespace() {
        let html = parse("<svg><link/></svg>").unwrap();
        assert_eq!(html.to_string(), "<svg><link/></svg>");

        let html = parse("<svg/>").unwrap();
        assert_eq!(html.to_string(), "<svg/>");
    }

    #[test]
    fn empty_element_in_foreign_namespace() {
        let html = parse("<svg><link></link></svg>").unwrap();
        assert_eq!(html.to_string(), "<svg><link></link></svg>");

        let html = parse("<svg></svg>").unwrap();
        assert_eq!(html.to_string(), "<svg></svg>");
    }

    #[test]
    fn marking_subtree_as_foreign_avoids_html_void_serialization() {
        let tree = html!((feed(link)));
        assert_eq!(tree.to_string(), "<feed><link></feed>");

        mark_foreign_subtree(&tree);
        assert_eq!(tree.to_string(), "<feed><link></link></feed>");
    }
    
    #[test]
    fn size() {
        dbg!(std::mem::size_of::<crate::node::NodeInner>());
    }
}