veridian_kernel/browser/
dom.rs

1//! DOM Tree
2//!
3//! Arena-based Document Object Model using `Vec<Node>` with `NodeId(usize)`
4//! indices. Supports element creation, tree manipulation, traversal, and
5//! querying by ID or tag name. No raw pointers.
6
7#![allow(dead_code)]
8
9use alloc::{
10    collections::BTreeMap,
11    string::{String, ToString},
12    vec::Vec,
13};
14
15/// Index into the node arena
16#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
17pub struct NodeId(pub usize);
18
19/// Type of DOM node
20#[derive(Debug, Clone, Default, PartialEq, Eq)]
21pub enum NodeType {
22    #[default]
23    Document,
24    Element,
25    Text,
26    Comment,
27    DocumentType,
28}
29
30/// Data specific to Element nodes
31#[derive(Debug, Clone, Default)]
32pub struct ElementData {
33    pub tag_name: String,
34    pub attributes: BTreeMap<String, String>,
35    pub namespace: Option<String>,
36}
37
38impl ElementData {
39    pub fn new(tag_name: &str) -> Self {
40        Self {
41            tag_name: tag_name.to_string(),
42            attributes: BTreeMap::new(),
43            namespace: None,
44        }
45    }
46
47    pub fn get_attr(&self, name: &str) -> Option<&str> {
48        self.attributes.get(name).map(|s| s.as_str())
49    }
50
51    pub fn set_attr(&mut self, name: &str, value: &str) {
52        self.attributes.insert(name.to_string(), value.to_string());
53    }
54
55    pub fn has_class(&self, class_name: &str) -> bool {
56        self.attributes
57            .get("class")
58            .map(|c| c.split_whitespace().any(|w| w == class_name))
59            .unwrap_or(false)
60    }
61}
62
63/// A single node in the DOM tree
64#[derive(Debug, Clone, Default)]
65pub struct Node {
66    pub node_type: NodeType,
67    pub parent: Option<NodeId>,
68    pub children: Vec<NodeId>,
69    pub element_data: Option<ElementData>,
70    pub text_content: Option<String>,
71}
72
73/// Arena allocator for DOM nodes
74#[derive(Debug, Default)]
75pub struct NodeArena {
76    nodes: Vec<Node>,
77}
78
79impl NodeArena {
80    pub fn new() -> Self {
81        Self { nodes: Vec::new() }
82    }
83
84    /// Allocate a new node and return its ID
85    pub fn alloc(&mut self, node: Node) -> NodeId {
86        let id = NodeId(self.nodes.len());
87        self.nodes.push(node);
88        id
89    }
90
91    /// Get a reference to a node by ID
92    pub fn get(&self, id: NodeId) -> Option<&Node> {
93        self.nodes.get(id.0)
94    }
95
96    /// Get a mutable reference to a node by ID
97    pub fn get_mut(&mut self, id: NodeId) -> Option<&mut Node> {
98        self.nodes.get_mut(id.0)
99    }
100
101    /// Number of nodes in the arena
102    pub fn len(&self) -> usize {
103        self.nodes.len()
104    }
105
106    /// Check if arena is empty
107    pub fn is_empty(&self) -> bool {
108        self.nodes.is_empty()
109    }
110}
111
112/// The DOM Document
113#[derive(Debug)]
114pub struct Document {
115    pub arena: NodeArena,
116    pub root: NodeId,
117}
118
119impl Default for Document {
120    fn default() -> Self {
121        Self::new()
122    }
123}
124
125impl Document {
126    /// Create a new empty document
127    pub fn new() -> Self {
128        let mut arena = NodeArena::new();
129        let root = arena.alloc(Node {
130            node_type: NodeType::Document,
131            parent: None,
132            children: Vec::new(),
133            element_data: None,
134            text_content: None,
135        });
136        Self { arena, root }
137    }
138
139    /// Create an element node
140    pub fn create_element(&mut self, tag_name: &str) -> NodeId {
141        self.arena.alloc(Node {
142            node_type: NodeType::Element,
143            parent: None,
144            children: Vec::new(),
145            element_data: Some(ElementData::new(tag_name)),
146            text_content: None,
147        })
148    }
149
150    /// Create an element node with attributes
151    pub fn create_element_with_attrs(
152        &mut self,
153        tag_name: &str,
154        attrs: BTreeMap<String, String>,
155    ) -> NodeId {
156        let mut ed = ElementData::new(tag_name);
157        ed.attributes = attrs;
158        self.arena.alloc(Node {
159            node_type: NodeType::Element,
160            parent: None,
161            children: Vec::new(),
162            element_data: Some(ed),
163            text_content: None,
164        })
165    }
166
167    /// Create a text node
168    pub fn create_text(&mut self, text: &str) -> NodeId {
169        self.arena.alloc(Node {
170            node_type: NodeType::Text,
171            parent: None,
172            children: Vec::new(),
173            element_data: None,
174            text_content: Some(text.to_string()),
175        })
176    }
177
178    /// Create a comment node
179    pub fn create_comment(&mut self, text: &str) -> NodeId {
180        self.arena.alloc(Node {
181            node_type: NodeType::Comment,
182            parent: None,
183            children: Vec::new(),
184            element_data: None,
185            text_content: Some(text.to_string()),
186        })
187    }
188
189    /// Create a document type node
190    pub fn create_doctype(&mut self, name: &str) -> NodeId {
191        self.arena.alloc(Node {
192            node_type: NodeType::DocumentType,
193            parent: None,
194            children: Vec::new(),
195            element_data: Some(ElementData::new(name)),
196            text_content: None,
197        })
198    }
199
200    /// Append a child node to a parent
201    pub fn append_child(&mut self, parent_id: NodeId, child_id: NodeId) {
202        // Set parent on child
203        if let Some(child) = self.arena.get_mut(child_id) {
204            child.parent = Some(parent_id);
205        }
206        // Add child to parent's children
207        if let Some(parent) = self.arena.get_mut(parent_id) {
208            parent.children.push(child_id);
209        }
210    }
211
212    /// Remove a child from its parent
213    pub fn remove_child(&mut self, parent_id: NodeId, child_id: NodeId) {
214        if let Some(parent) = self.arena.get_mut(parent_id) {
215            parent.children.retain(|&id| id != child_id);
216        }
217        if let Some(child) = self.arena.get_mut(child_id) {
218            child.parent = None;
219        }
220    }
221
222    /// Insert a child before a reference node
223    pub fn insert_before(&mut self, parent_id: NodeId, new_child_id: NodeId, ref_child_id: NodeId) {
224        // Set parent
225        if let Some(child) = self.arena.get_mut(new_child_id) {
226            child.parent = Some(parent_id);
227        }
228        // Insert before reference
229        if let Some(parent) = self.arena.get_mut(parent_id) {
230            if let Some(pos) = parent.children.iter().position(|&id| id == ref_child_id) {
231                parent.children.insert(pos, new_child_id);
232            } else {
233                parent.children.push(new_child_id);
234            }
235        }
236    }
237
238    /// Find an element by its "id" attribute
239    pub fn get_element_by_id(&self, id: &str) -> Option<NodeId> {
240        let mut result = None;
241        self.walk(self.root, &mut |node_id| {
242            if let Some(node) = self.arena.get(node_id) {
243                if let Some(ref ed) = node.element_data {
244                    if ed.get_attr("id") == Some(id) {
245                        result = Some(node_id);
246                    }
247                }
248            }
249        });
250        result
251    }
252
253    /// Find all elements with a given tag name
254    pub fn get_elements_by_tag_name(&self, tag: &str) -> Vec<NodeId> {
255        let mut results = Vec::new();
256        self.walk(self.root, &mut |node_id| {
257            if let Some(node) = self.arena.get(node_id) {
258                if let Some(ref ed) = node.element_data {
259                    if ed.tag_name == tag {
260                        results.push(node_id);
261                    }
262                }
263            }
264        });
265        results
266    }
267
268    /// Walk the tree depth-first, calling the callback on each node
269    pub fn walk<F: FnMut(NodeId)>(&self, start: NodeId, callback: &mut F) {
270        callback(start);
271        if let Some(node) = self.arena.get(start) {
272            let children = node.children.clone();
273            for child_id in children {
274                self.walk(child_id, callback);
275            }
276        }
277    }
278
279    /// Get all descendant NodeIds (depth-first)
280    pub fn descendants(&self, start: NodeId) -> Vec<NodeId> {
281        let mut result = Vec::new();
282        self.walk(start, &mut |id| {
283            if id != start {
284                result.push(id);
285            }
286        });
287        result
288    }
289
290    /// Get all ancestor NodeIds (from parent up to root)
291    pub fn ancestors(&self, start: NodeId) -> Vec<NodeId> {
292        let mut result = Vec::new();
293        let mut current = start;
294        while let Some(node) = self.arena.get(current) {
295            if let Some(parent_id) = node.parent {
296                result.push(parent_id);
297                current = parent_id;
298            } else {
299                break;
300            }
301        }
302        result
303    }
304
305    /// Get the inner text of a node (concatenation of all text descendants)
306    pub fn inner_text(&self, node_id: NodeId) -> String {
307        let mut text = String::new();
308        self.walk(node_id, &mut |id| {
309            if let Some(node) = self.arena.get(id) {
310                if node.node_type == NodeType::Text {
311                    if let Some(ref t) = node.text_content {
312                        text.push_str(t);
313                    }
314                }
315            }
316        });
317        text
318    }
319
320    /// Generate outer HTML for debugging
321    pub fn outer_html(&self, node_id: NodeId) -> String {
322        let node = match self.arena.get(node_id) {
323            Some(n) => n,
324            None => return String::new(),
325        };
326
327        match node.node_type {
328            NodeType::Document => {
329                let mut s = String::new();
330                let children = node.children.clone();
331                for child in children {
332                    s.push_str(&self.outer_html(child));
333                }
334                s
335            }
336            NodeType::Element => {
337                let ed = node.element_data.as_ref().unwrap();
338                let mut s = String::from("<");
339                s.push_str(&ed.tag_name);
340                for (k, v) in &ed.attributes {
341                    s.push(' ');
342                    s.push_str(k);
343                    s.push_str("=\"");
344                    s.push_str(v);
345                    s.push('"');
346                }
347                s.push('>');
348                let children = node.children.clone();
349                for child in children {
350                    s.push_str(&self.outer_html(child));
351                }
352                s.push_str("</");
353                s.push_str(&ed.tag_name);
354                s.push('>');
355                s
356            }
357            NodeType::Text => node.text_content.clone().unwrap_or_default(),
358            NodeType::Comment => {
359                let mut s = String::from("<!--");
360                if let Some(ref t) = node.text_content {
361                    s.push_str(t);
362                }
363                s.push_str("-->");
364                s
365            }
366            NodeType::DocumentType => {
367                let name = node
368                    .element_data
369                    .as_ref()
370                    .map(|e| e.tag_name.as_str())
371                    .unwrap_or("html");
372                let mut s = String::from("<!DOCTYPE ");
373                s.push_str(name);
374                s.push('>');
375                s
376            }
377        }
378    }
379
380    /// Get the tag name of an element node
381    pub fn tag_name(&self, node_id: NodeId) -> Option<&str> {
382        self.arena
383            .get(node_id)
384            .and_then(|n| n.element_data.as_ref())
385            .map(|ed| ed.tag_name.as_str())
386    }
387
388    /// Get an attribute value from an element node
389    pub fn get_attribute(&self, node_id: NodeId, attr: &str) -> Option<String> {
390        self.arena
391            .get(node_id)
392            .and_then(|n| n.element_data.as_ref())
393            .and_then(|ed| ed.attributes.get(attr))
394            .cloned()
395    }
396
397    /// Count total nodes in the arena
398    pub fn node_count(&self) -> usize {
399        self.arena.len()
400    }
401}
402
403#[cfg(test)]
404mod tests {
405    #[allow(unused_imports)]
406    use alloc::vec;
407
408    use super::*;
409
410    #[test]
411    fn test_new_document() {
412        let doc = Document::new();
413        assert_eq!(doc.root, NodeId(0));
414        assert_eq!(doc.arena.len(), 1);
415    }
416
417    #[test]
418    fn test_create_element() {
419        let mut doc = Document::new();
420        let div = doc.create_element("div");
421        assert_eq!(div, NodeId(1));
422        assert_eq!(doc.tag_name(div), Some("div"));
423    }
424
425    #[test]
426    fn test_create_text() {
427        let mut doc = Document::new();
428        let text = doc.create_text("hello");
429        let node = doc.arena.get(text).unwrap();
430        assert_eq!(node.node_type, NodeType::Text);
431        assert_eq!(node.text_content.as_deref(), Some("hello"));
432    }
433
434    #[test]
435    fn test_create_comment() {
436        let mut doc = Document::new();
437        let c = doc.create_comment("a comment");
438        let node = doc.arena.get(c).unwrap();
439        assert_eq!(node.node_type, NodeType::Comment);
440        assert_eq!(node.text_content.as_deref(), Some("a comment"));
441    }
442
443    #[test]
444    fn test_append_child() {
445        let mut doc = Document::new();
446        let div = doc.create_element("div");
447        doc.append_child(doc.root, div);
448        let root = doc.arena.get(doc.root).unwrap();
449        assert_eq!(root.children, vec![div]);
450        let div_node = doc.arena.get(div).unwrap();
451        assert_eq!(div_node.parent, Some(doc.root));
452    }
453
454    #[test]
455    fn test_remove_child() {
456        let mut doc = Document::new();
457        let div = doc.create_element("div");
458        doc.append_child(doc.root, div);
459        doc.remove_child(doc.root, div);
460        let root = doc.arena.get(doc.root).unwrap();
461        assert!(root.children.is_empty());
462    }
463
464    #[test]
465    fn test_insert_before() {
466        let mut doc = Document::new();
467        let a = doc.create_element("a");
468        let b = doc.create_element("b");
469        let c = doc.create_element("c");
470        doc.append_child(doc.root, a);
471        doc.append_child(doc.root, c);
472        doc.insert_before(doc.root, b, c);
473        let root = doc.arena.get(doc.root).unwrap();
474        assert_eq!(root.children, vec![a, b, c]);
475    }
476
477    #[test]
478    fn test_get_element_by_id() {
479        let mut doc = Document::new();
480        let mut attrs = BTreeMap::new();
481        attrs.insert("id".to_string(), "main".to_string());
482        let div = doc.create_element_with_attrs("div", attrs);
483        doc.append_child(doc.root, div);
484        assert_eq!(doc.get_element_by_id("main"), Some(div));
485        assert_eq!(doc.get_element_by_id("none"), None);
486    }
487
488    #[test]
489    fn test_get_elements_by_tag_name() {
490        let mut doc = Document::new();
491        let p1 = doc.create_element("p");
492        let p2 = doc.create_element("p");
493        let div = doc.create_element("div");
494        doc.append_child(doc.root, p1);
495        doc.append_child(doc.root, div);
496        doc.append_child(div, p2);
497        let ps = doc.get_elements_by_tag_name("p");
498        assert_eq!(ps.len(), 2);
499    }
500
501    #[test]
502    fn test_inner_text() {
503        let mut doc = Document::new();
504        let p = doc.create_element("p");
505        let t = doc.create_text("hello world");
506        doc.append_child(doc.root, p);
507        doc.append_child(p, t);
508        assert_eq!(doc.inner_text(p), "hello world");
509    }
510
511    #[test]
512    fn test_inner_text_nested() {
513        let mut doc = Document::new();
514        let div = doc.create_element("div");
515        let span = doc.create_element("span");
516        let t1 = doc.create_text("hello ");
517        let t2 = doc.create_text("world");
518        doc.append_child(doc.root, div);
519        doc.append_child(div, t1);
520        doc.append_child(div, span);
521        doc.append_child(span, t2);
522        assert_eq!(doc.inner_text(div), "hello world");
523    }
524
525    #[test]
526    fn test_outer_html_element() {
527        let mut doc = Document::new();
528        let p = doc.create_element("p");
529        let t = doc.create_text("hi");
530        doc.append_child(p, t);
531        assert_eq!(doc.outer_html(p), "<p>hi</p>");
532    }
533
534    #[test]
535    fn test_outer_html_with_attrs() {
536        let mut doc = Document::new();
537        let mut attrs = BTreeMap::new();
538        attrs.insert("class".to_string(), "big".to_string());
539        let div = doc.create_element_with_attrs("div", attrs);
540        assert_eq!(doc.outer_html(div), "<div class=\"big\"></div>");
541    }
542
543    #[test]
544    fn test_descendants() {
545        let mut doc = Document::new();
546        let a = doc.create_element("a");
547        let b = doc.create_element("b");
548        let c = doc.create_element("c");
549        doc.append_child(doc.root, a);
550        doc.append_child(a, b);
551        doc.append_child(a, c);
552        let desc = doc.descendants(a);
553        assert_eq!(desc, vec![b, c]);
554    }
555
556    #[test]
557    fn test_ancestors() {
558        let mut doc = Document::new();
559        let a = doc.create_element("a");
560        let b = doc.create_element("b");
561        doc.append_child(doc.root, a);
562        doc.append_child(a, b);
563        let anc = doc.ancestors(b);
564        assert_eq!(anc, vec![a, doc.root]);
565    }
566
567    #[test]
568    fn test_walk() {
569        let mut doc = Document::new();
570        let a = doc.create_element("a");
571        let b = doc.create_element("b");
572        doc.append_child(doc.root, a);
573        doc.append_child(a, b);
574        let mut visited = Vec::new();
575        doc.walk(doc.root, &mut |id| visited.push(id));
576        assert_eq!(visited, vec![doc.root, a, b]);
577    }
578
579    #[test]
580    fn test_node_count() {
581        let mut doc = Document::new();
582        assert_eq!(doc.node_count(), 1);
583        let _a = doc.create_element("a");
584        assert_eq!(doc.node_count(), 2);
585    }
586
587    #[test]
588    fn test_doctype_node() {
589        let mut doc = Document::new();
590        let dt = doc.create_doctype("html");
591        let node = doc.arena.get(dt).unwrap();
592        assert_eq!(node.node_type, NodeType::DocumentType);
593    }
594
595    #[test]
596    fn test_element_data_has_class() {
597        let mut ed = ElementData::new("div");
598        ed.set_attr("class", "foo bar baz");
599        assert!(ed.has_class("foo"));
600        assert!(ed.has_class("bar"));
601        assert!(!ed.has_class("qux"));
602    }
603
604    #[test]
605    fn test_element_data_get_attr() {
606        let mut ed = ElementData::new("a");
607        ed.set_attr("href", "/home");
608        assert_eq!(ed.get_attr("href"), Some("/home"));
609        assert_eq!(ed.get_attr("none"), None);
610    }
611
612    #[test]
613    fn test_get_attribute() {
614        let mut doc = Document::new();
615        let mut attrs = BTreeMap::new();
616        attrs.insert("src".to_string(), "img.png".to_string());
617        let img = doc.create_element_with_attrs("img", attrs);
618        assert_eq!(doc.get_attribute(img, "src"), Some("img.png".to_string()));
619    }
620
621    #[test]
622    fn test_empty_arena() {
623        let arena = NodeArena::new();
624        assert!(arena.is_empty());
625        assert_eq!(arena.len(), 0);
626    }
627
628    #[test]
629    fn test_multiple_children() {
630        let mut doc = Document::new();
631        let a = doc.create_element("a");
632        let b = doc.create_element("b");
633        let c = doc.create_element("c");
634        let d = doc.create_element("d");
635        doc.append_child(doc.root, a);
636        doc.append_child(doc.root, b);
637        doc.append_child(doc.root, c);
638        doc.append_child(doc.root, d);
639        let root = doc.arena.get(doc.root).unwrap();
640        assert_eq!(root.children.len(), 4);
641    }
642
643    #[test]
644    fn test_outer_html_comment() {
645        let mut doc = Document::new();
646        let c = doc.create_comment("test");
647        assert_eq!(doc.outer_html(c), "<!--test-->");
648    }
649
650    #[test]
651    fn test_outer_html_doctype() {
652        let mut doc = Document::new();
653        let dt = doc.create_doctype("html");
654        assert_eq!(doc.outer_html(dt), "<!DOCTYPE html>");
655    }
656
657    #[test]
658    fn test_default_document() {
659        let doc = Document::default();
660        assert_eq!(doc.node_count(), 1);
661    }
662
663    #[test]
664    fn test_deep_nesting() {
665        let mut doc = Document::new();
666        let mut parent = doc.root;
667        for i in 0..10 {
668            let child = doc.create_element("div");
669            doc.append_child(parent, child);
670            // Create a text child for inner_text testing
671            if i == 9 {
672                let t = doc.create_text("deep");
673                doc.append_child(child, t);
674            }
675            parent = child;
676        }
677        assert_eq!(doc.inner_text(doc.root), "deep");
678    }
679}
veridian_kernel/browser/dom.rs

veridian_kernel/browser/
dom.rs
