use std::num::NonZeroU32;
use crate::tokenizer::{Attribute as TokenAttribute, Position};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct NodeId(NonZeroU32);
impl NodeId {
fn from_index(index: usize) -> Self {
Self(
NonZeroU32::new(u32::try_from(index).expect("node arena index overflowed u32"))
.expect("node arena index must be nonzero"),
)
}
fn index(self) -> usize {
self.0.get() as usize
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Attribute {
pub name: String,
pub value: String,
pub namespace: Option<String>,
}
impl From<TokenAttribute> for Attribute {
fn from(attribute: TokenAttribute) -> Self {
Attribute {
name: attribute.name,
value: attribute.value,
namespace: None,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum NodeKind {
Document,
Element {
name: String,
namespace: Option<String>,
attributes: Vec<Attribute>,
},
Text { content: String },
Comment { content: String },
ProcessingInstruction { target: String, data: String },
Doctype {
name: Option<String>,
public_identifier: Option<String>,
system_identifier: Option<String>,
},
DocumentFragment,
}
#[derive(Debug, Clone)]
pub struct Node {
pub kind: NodeKind,
pub position: Option<Position>,
parent: Option<NodeId>,
first_child: Option<NodeId>,
last_child: Option<NodeId>,
next_sibling: Option<NodeId>,
prev_sibling: Option<NodeId>,
}
impl Node {
fn new(kind: NodeKind, position: Option<Position>) -> Self {
Node {
kind,
position,
parent: None,
first_child: None,
last_child: None,
next_sibling: None,
prev_sibling: None,
}
}
}
#[derive(Debug)]
pub struct Document {
nodes: Vec<Node>,
root: NodeId,
}
impl Document {
pub(crate) fn new() -> Self {
let placeholder = Node::new(NodeKind::Document, None);
let root_node = Node::new(NodeKind::Document, None);
Document {
nodes: vec![placeholder, root_node],
root: NodeId::from_index(1),
}
}
pub fn root(&self) -> NodeId {
self.root
}
pub fn node(&self, id: NodeId) -> &Node {
&self.nodes[id.index()]
}
pub(crate) fn node_mut(&mut self, id: NodeId) -> &mut Node {
&mut self.nodes[id.index()]
}
pub fn parent(&self, id: NodeId) -> Option<NodeId> {
self.node(id).parent
}
pub(crate) fn last_child(&self, id: NodeId) -> Option<NodeId> {
self.node(id).last_child
}
pub(crate) fn prev_sibling(&self, id: NodeId) -> Option<NodeId> {
self.node(id).prev_sibling
}
pub(crate) fn new_node(&mut self, kind: NodeKind, position: Option<Position>) -> NodeId {
self.nodes.push(Node::new(kind, position));
NodeId::from_index(self.nodes.len() - 1)
}
pub(crate) fn clone_subtree(&mut self, source: NodeId) -> NodeId {
let kind = self.node(source).kind.clone();
let clone = self.new_node(kind, None);
let children: Vec<_> = self.children(source).collect();
for child in children {
let child_clone = self.clone_subtree(child);
self.append_child(clone, child_clone);
}
clone
}
pub(crate) fn remove(&mut self, node: NodeId) {
let Some(parent) = self.node(node).parent else {
return;
};
let previous_sibling = self.node(node).prev_sibling;
let next_sibling = self.node(node).next_sibling;
match previous_sibling {
Some(previous_sibling) => {
self.nodes[previous_sibling.index()].next_sibling = next_sibling;
}
None => self.nodes[parent.index()].first_child = next_sibling,
}
match next_sibling {
Some(next_sibling) => {
self.nodes[next_sibling.index()].prev_sibling = previous_sibling;
}
None => self.nodes[parent.index()].last_child = previous_sibling,
}
let node = &mut self.nodes[node.index()];
node.parent = None;
node.prev_sibling = None;
node.next_sibling = None;
}
pub(crate) fn is_inclusive_ancestor(&self, ancestor: NodeId, node: NodeId) -> bool {
let mut current = Some(node);
while let Some(current_node) = current {
if current_node == ancestor {
return true;
}
current = self.node(current_node).parent;
}
false
}
pub(crate) fn insert_before(
&mut self,
parent: NodeId,
reference: Option<NodeId>,
new_node: NodeId,
) {
self.remove(new_node);
match reference {
None => {
let previous_last_child = self.node(parent).last_child;
self.nodes[new_node.index()].parent = Some(parent);
self.nodes[new_node.index()].prev_sibling = previous_last_child;
if let Some(previous_last_child) = previous_last_child {
self.nodes[previous_last_child.index()].next_sibling = Some(new_node);
} else {
self.nodes[parent.index()].first_child = Some(new_node);
}
self.nodes[parent.index()].last_child = Some(new_node);
}
Some(reference) => {
debug_assert_eq!(
self.node(reference).parent,
Some(parent),
"insert_before's reference node must already be a child of parent"
);
let previous_sibling = self.node(reference).prev_sibling;
self.nodes[new_node.index()].parent = Some(parent);
self.nodes[new_node.index()].next_sibling = Some(reference);
self.nodes[new_node.index()].prev_sibling = previous_sibling;
self.nodes[reference.index()].prev_sibling = Some(new_node);
if let Some(previous_sibling) = previous_sibling {
self.nodes[previous_sibling.index()].next_sibling = Some(new_node);
} else {
self.nodes[parent.index()].first_child = Some(new_node);
}
}
}
}
pub(crate) fn append_child(&mut self, parent: NodeId, child: NodeId) {
self.insert_before(parent, None, child);
}
pub fn children(&self, id: NodeId) -> Children<'_> {
Children {
document: self,
next: self.node(id).first_child,
}
}
}
impl Default for Document {
fn default() -> Self {
Self::new()
}
}
pub struct Children<'a> {
document: &'a Document,
next: Option<NodeId>,
}
impl Iterator for Children<'_> {
type Item = NodeId;
fn next(&mut self) -> Option<NodeId> {
let current = self.next?;
self.next = self.document.node(current).next_sibling;
Some(current)
}
}
#[cfg(test)]
mod tests {
use super::{Document, NodeKind, Position};
fn pos(line: u32, column: u32, byte_offset: usize) -> Position {
Position {
line,
column,
byte_offset,
}
}
#[test]
fn new_document_has_only_its_own_document_node() {
let document = Document::new();
assert_eq!(document.node(document.root()).kind, NodeKind::Document);
assert_eq!(document.children(document.root()).count(), 0);
assert_eq!(document.node(document.root()).position, None);
}
#[test]
fn append_child_attaches_a_detached_node_as_the_last_child() {
let mut document = Document::new();
let root = document.root();
let p = document.new_node(
NodeKind::Element {
name: "p".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
Some(pos(1, 1, 0)),
);
document.append_child(root, p);
let children: Vec<_> = document.children(root).collect();
assert_eq!(children, vec![p]);
assert_eq!(document.parent(p), Some(root));
}
#[test]
fn multiple_children_are_yielded_in_document_order() {
let mut document = Document::new();
let root = document.root();
let first = document.new_node(
NodeKind::Text {
content: "a".to_owned(),
},
None,
);
let second = document.new_node(
NodeKind::Text {
content: "b".to_owned(),
},
None,
);
let third = document.new_node(
NodeKind::Text {
content: "c".to_owned(),
},
None,
);
document.append_child(root, first);
document.append_child(root, second);
document.append_child(root, third);
let children: Vec<_> = document.children(root).collect();
assert_eq!(children, vec![first, second, third]);
}
#[test]
fn insert_before_a_reference_places_the_new_node_in_the_middle() {
let mut document = Document::new();
let root = document.root();
let first = document.new_node(
NodeKind::Text {
content: "a".to_owned(),
},
None,
);
let third = document.new_node(
NodeKind::Text {
content: "c".to_owned(),
},
None,
);
document.append_child(root, first);
document.append_child(root, third);
let second = document.new_node(
NodeKind::Text {
content: "b".to_owned(),
},
None,
);
document.insert_before(root, Some(third), second);
let children: Vec<_> = document.children(root).collect();
assert_eq!(children, vec![first, second, third]);
}
#[test]
fn insert_before_at_the_start_updates_first_child() {
let mut document = Document::new();
let root = document.root();
let second = document.new_node(
NodeKind::Text {
content: "b".to_owned(),
},
None,
);
document.append_child(root, second);
let first = document.new_node(
NodeKind::Text {
content: "a".to_owned(),
},
None,
);
document.insert_before(root, Some(second), first);
let children: Vec<_> = document.children(root).collect();
assert_eq!(children, vec![first, second]);
}
#[test]
fn nested_children_are_independent_of_their_parents_siblings() {
let mut document = Document::new();
let root = document.root();
let div = document.new_node(
NodeKind::Element {
name: "div".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
Some(pos(1, 1, 0)),
);
document.append_child(root, div);
let text = document.new_node(
NodeKind::Text {
content: "hi".to_owned(),
},
Some(pos(1, 6, 5)),
);
document.append_child(div, text);
assert_eq!(document.children(root).collect::<Vec<_>>(), vec![div]);
assert_eq!(document.children(div).collect::<Vec<_>>(), vec![text]);
assert_eq!(document.parent(text), Some(div));
}
#[test]
fn synthesized_nodes_carry_no_position_while_parsed_nodes_do() {
let mut document = Document::new();
let root = document.root();
let implied_html = document.new_node(
NodeKind::Element {
name: "html".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
None,
);
document.append_child(root, implied_html);
let parsed_p = document.new_node(
NodeKind::Element {
name: "p".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
Some(pos(1, 1, 0)),
);
document.append_child(implied_html, parsed_p);
assert_eq!(document.node(implied_html).position, None);
assert_eq!(document.node(parsed_p).position, Some(pos(1, 1, 0)));
}
#[test]
fn remove_detaches_a_node_and_relinks_its_siblings() {
let mut document = Document::new();
let root = document.root();
let first = document.new_node(
NodeKind::Text {
content: "a".to_owned(),
},
None,
);
let second = document.new_node(
NodeKind::Text {
content: "b".to_owned(),
},
None,
);
let third = document.new_node(
NodeKind::Text {
content: "c".to_owned(),
},
None,
);
document.append_child(root, first);
document.append_child(root, second);
document.append_child(root, third);
document.remove(second);
assert_eq!(
document.children(root).collect::<Vec<_>>(),
vec![first, third]
);
assert_eq!(document.parent(second), None);
}
#[test]
fn remove_on_a_node_with_no_parent_is_a_no_op() {
let mut document = Document::new();
let detached = document.new_node(
NodeKind::Text {
content: "a".to_owned(),
},
None,
);
document.remove(detached);
assert_eq!(document.parent(detached), None);
}
#[test]
fn insert_before_an_already_attached_node_moves_it() {
let mut document = Document::new();
let root = document.root();
let old_parent = document.new_node(
NodeKind::Element {
name: "div".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
None,
);
let new_parent = document.new_node(
NodeKind::Element {
name: "span".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
None,
);
document.append_child(root, old_parent);
document.append_child(root, new_parent);
let child = document.new_node(
NodeKind::Text {
content: "hi".to_owned(),
},
None,
);
document.append_child(old_parent, child);
document.append_child(new_parent, child);
assert_eq!(document.children(old_parent).count(), 0);
assert_eq!(
document.children(new_parent).collect::<Vec<_>>(),
vec![child]
);
assert_eq!(document.parent(child), Some(new_parent));
}
#[test]
fn is_inclusive_ancestor_covers_self_and_real_ancestors_but_not_others() {
let mut document = Document::new();
let root = document.root();
let div = document.new_node(
NodeKind::Element {
name: "div".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
None,
);
document.append_child(root, div);
let span = document.new_node(
NodeKind::Element {
name: "span".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
None,
);
document.append_child(div, span);
let unrelated = document.new_node(
NodeKind::Text {
content: "x".to_owned(),
},
None,
);
document.append_child(root, unrelated);
assert!(document.is_inclusive_ancestor(span, span));
assert!(document.is_inclusive_ancestor(div, span));
assert!(document.is_inclusive_ancestor(root, span));
assert!(!document.is_inclusive_ancestor(unrelated, span));
assert!(!document.is_inclusive_ancestor(span, div));
}
#[test]
fn clone_subtree_deep_copies_kind_and_structure_into_new_nodes() {
let mut document = Document::new();
let root = document.root();
let original = document.new_node(
NodeKind::Element {
name: "b".to_owned(),
namespace: Some("http://www.w3.org/1999/xhtml".to_owned()),
attributes: vec![],
},
Some(pos(1, 1, 0)),
);
document.append_child(root, original);
let text = document.new_node(
NodeKind::Text {
content: "hi".to_owned(),
},
Some(pos(1, 4, 3)),
);
document.append_child(original, text);
let clone = document.clone_subtree(original);
assert_ne!(clone, original);
assert_eq!(document.node(clone).kind, document.node(original).kind);
assert_eq!(document.parent(clone), None);
let clone_children: Vec<_> = document.children(clone).collect();
assert_eq!(clone_children.len(), 1);
assert_ne!(clone_children[0], text);
assert_eq!(
document.node(clone_children[0]).kind,
NodeKind::Text {
content: "hi".to_owned()
}
);
assert_eq!(document.node(clone).position, None);
assert_eq!(document.children(original).collect::<Vec<_>>(), vec![text]);
}
}