cadmus_core/document/html/
dom.rs

1use fxhash::{FxHashMap, FxHashSet};
2use std::num::NonZeroUsize;
3
4pub type Attributes = FxHashMap<String, String>;
5pub const WRAPPER_TAG_NAME: &str = "anonymous";
6
7#[derive(Debug, Clone)]
8pub enum NodeData {
9    Root,
10    Wrapper(usize),
11    Element(ElementData),
12    Text(TextData),
13    Whitespace(TextData),
14}
15
16#[derive(Debug, Clone)]
17pub struct ElementData {
18    pub offset: usize,
19    pub name: String,
20    pub qualified_name: Option<String>,
21    pub attributes: Attributes,
22}
23
24impl ElementData {
25    fn is_block(&self) -> bool {
26        matches!(
27            self.name.as_str(),
28            "address"
29                | "article"
30                | "aside"
31                | "blockquote"
32                | "body"
33                | "head"
34                | "details"
35                | "dialog"
36                | "dd"
37                | "div"
38                | "dl"
39                | "dt"
40                | "fieldset"
41                | "figcaption"
42                | "figure"
43                | "footer"
44                | "form"
45                | "h1"
46                | "h2"
47                | "h3"
48                | "h4"
49                | "h5"
50                | "h6"
51                | "header"
52                | "hgroup"
53                | "hr"
54                | "html"
55                | "li"
56                | "main"
57                | "nav"
58                | "ol"
59                | "p"
60                | "pre"
61                | "section"
62                | "table"
63                | "thead"
64                | "colgroup"
65                | "tbody"
66                | "tfoot"
67                | "tr"
68                | "caption"
69                | "td"
70                | "th"
71                | "ul"
72        )
73    }
74}
75
76impl NodeData {
77    fn text(&self) -> Option<&str> {
78        match *self {
79            NodeData::Text(TextData { ref text, .. })
80            | NodeData::Whitespace(TextData { ref text, .. }) => Some(text),
81            _ => None,
82        }
83    }
84
85    fn offset(&self) -> usize {
86        match *self {
87            NodeData::Text(TextData { offset, .. })
88            | NodeData::Whitespace(TextData { offset, .. })
89            | NodeData::Element(ElementData { offset, .. }) => offset,
90            NodeData::Wrapper(offset) => offset,
91            NodeData::Root => 0,
92        }
93    }
94}
95
96#[derive(Debug, Clone)]
97pub struct TextData {
98    pub offset: usize,
99    pub text: String,
100}
101
102pub fn element(name: &str, offset: usize, attributes: Attributes) -> NodeData {
103    let colon = name.find(':');
104    NodeData::Element(ElementData {
105        offset,
106        name: name[colon.map(|index| index + 1).unwrap_or(0)..].to_string(),
107        qualified_name: colon.map(|_| name.to_string()),
108        attributes,
109    })
110}
111
112pub fn text(text: &str, offset: usize) -> NodeData {
113    NodeData::Text(TextData {
114        offset,
115        text: text.to_string(),
116    })
117}
118
119pub fn whitespace(text: &str, offset: usize) -> NodeData {
120    NodeData::Whitespace(TextData {
121        offset,
122        text: text.to_string(),
123    })
124}
125
126#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
127pub struct NodeId(NonZeroUsize);
128
129impl NodeId {
130    pub fn from_index(n: usize) -> Self {
131        NodeId(unsafe { NonZeroUsize::new_unchecked(n + 1) })
132    }
133
134    pub fn to_index(self) -> usize {
135        self.0.get() - 1
136    }
137}
138
139#[derive(Debug, Clone)]
140pub struct XmlTree {
141    nodes: Vec<Node>,
142}
143
144#[derive(Debug, Clone)]
145pub struct Node {
146    data: NodeData,
147    parent: Option<NodeId>,
148    previous_sibling: Option<NodeId>,
149    next_sibling: Option<NodeId>,
150    first_child: Option<NodeId>,
151    last_child: Option<NodeId>,
152}
153
154impl Default for Node {
155    fn default() -> Self {
156        Node {
157            data: NodeData::Root,
158            parent: None,
159            previous_sibling: None,
160            next_sibling: None,
161            first_child: None,
162            last_child: None,
163        }
164    }
165}
166
167#[derive(Debug, Copy, Clone)]
168pub struct NodeRef<'a> {
169    pub id: NodeId,
170    pub node: &'a Node,
171    pub tree: &'a XmlTree,
172}
173
174#[derive(Debug)]
175pub struct NodeMut<'a> {
176    pub id: NodeId,
177    pub tree: &'a mut XmlTree,
178}
179
180impl XmlTree {
181    pub fn new() -> Self {
182        XmlTree {
183            nodes: vec![Node::default()],
184        }
185    }
186
187    fn node(&self, id: NodeId) -> &Node {
188        unsafe { self.nodes.get_unchecked(id.to_index()) }
189    }
190
191    fn node_mut(&mut self, id: NodeId) -> &mut Node {
192        unsafe { self.nodes.get_unchecked_mut(id.to_index()) }
193    }
194
195    pub fn get(&self, id: NodeId) -> NodeRef<'_> {
196        NodeRef {
197            id,
198            node: self.node(id),
199            tree: self,
200        }
201    }
202
203    pub fn get_mut(&mut self, id: NodeId) -> NodeMut<'_> {
204        NodeMut { id, tree: self }
205    }
206
207    pub fn root(&self) -> NodeRef<'_> {
208        self.get(NodeId::from_index(0))
209    }
210
211    pub fn root_mut(&mut self) -> NodeMut<'_> {
212        self.get_mut(NodeId::from_index(0))
213    }
214
215    pub fn push_node(&mut self, data: NodeData) -> NodeId {
216        let id = NodeId::from_index(self.nodes.len());
217        let node = Node {
218            data,
219            parent: None,
220            previous_sibling: None,
221            next_sibling: None,
222            first_child: None,
223            last_child: None,
224        };
225        self.nodes.push(node);
226        id
227    }
228
229    pub fn attach_child(&mut self, parent_id: NodeId, child_id: NodeId) {
230        let last_child = self.node(parent_id).last_child;
231
232        let child = self.node_mut(child_id);
233        child.parent = Some(parent_id);
234        child.previous_sibling = last_child;
235        child.next_sibling = None;
236
237        if let Some(last) = last_child {
238            self.node_mut(last).next_sibling = Some(child_id);
239        }
240
241        self.node_mut(parent_id).last_child = Some(child_id);
242
243        if self.node(parent_id).first_child.is_none() {
244            self.node_mut(parent_id).first_child = Some(child_id);
245        }
246    }
247
248    pub fn insert_before(&mut self, sibling_id: NodeId, new_id: NodeId) {
249        let parent_id = self.node(sibling_id).parent;
250        let prev_sibling = self.node(sibling_id).previous_sibling;
251
252        self.node_mut(new_id).parent = parent_id;
253        self.node_mut(new_id).previous_sibling = prev_sibling;
254        self.node_mut(new_id).next_sibling = Some(sibling_id);
255
256        self.node_mut(sibling_id).previous_sibling = Some(new_id);
257
258        if let Some(prev) = prev_sibling {
259            self.node_mut(prev).next_sibling = Some(new_id);
260        } else if let Some(parent) = parent_id {
261            self.node_mut(parent).first_child = Some(new_id);
262        }
263    }
264
265    pub fn detach(&mut self, id: NodeId) {
266        let node = self.node(id);
267        let parent_id = node.parent;
268        let prev_sibling = node.previous_sibling;
269        let next_sibling = node.next_sibling;
270
271        if let Some(prev) = prev_sibling {
272            self.node_mut(prev).next_sibling = next_sibling;
273        } else if let Some(parent) = parent_id {
274            self.node_mut(parent).first_child = next_sibling;
275        }
276
277        if let Some(next) = next_sibling {
278            self.node_mut(next).previous_sibling = prev_sibling;
279        } else if let Some(parent) = parent_id {
280            self.node_mut(parent).last_child = prev_sibling;
281        }
282
283        self.node_mut(id).parent = None;
284        self.node_mut(id).previous_sibling = None;
285        self.node_mut(id).next_sibling = None;
286    }
287
288    pub fn append_text_to(&mut self, id: NodeId, extra: &str) {
289        match &mut self.node_mut(id).data {
290            NodeData::Text(TextData { text, .. }) | NodeData::Whitespace(TextData { text, .. }) => {
291                text.push_str(extra);
292            }
293            _ => {}
294        }
295    }
296
297    pub fn add_attr_if_missing(&mut self, id: NodeId, name: &str, value: &str) {
298        if let NodeData::Element(ElementData {
299            ref mut attributes, ..
300        }) = self.node_mut(id).data
301        {
302            if !attributes.contains_key(name) {
303                attributes.insert(name.to_string(), value.to_string());
304            }
305        }
306    }
307
308    pub fn wrap_lost_inlines(&mut self) {
309        let mut ids = Vec::new();
310        let mut known_ids = FxHashSet::default();
311
312        for n in self.root().descendants().filter(|n| n.is_inline()) {
313            if known_ids.contains(&n.id) {
314                continue;
315            }
316
317            let mut first_id = None;
318            let mut last_id = None;
319
320            for s in n.previous_siblings() {
321                if s.is_block() {
322                    first_id = Some(s.next_sibling().unwrap().id);
323                    break;
324                } else {
325                    known_ids.insert(s.id);
326                }
327            }
328
329            for s in n.next_siblings() {
330                if s.is_block() {
331                    last_id = Some(s.previous_sibling().unwrap().id);
332                    break;
333                } else {
334                    known_ids.insert(s.id);
335                }
336            }
337
338            if first_id.is_some() || last_id.is_some() {
339                let parent = n.parent().unwrap();
340                ids.push([
341                    parent.id,
342                    first_id.unwrap_or_else(|| parent.node.first_child.unwrap()),
343                    last_id.unwrap_or_else(|| parent.node.last_child.unwrap()),
344                ]);
345            }
346        }
347
348        for [parent_id, first_id, last_id] in ids {
349            let offset = self.node(first_id).data.offset();
350            let mut node = self.get_mut(parent_id);
351            node.wrap_range(first_id, last_id, NodeData::Wrapper(offset));
352        }
353    }
354}
355
356impl<'a> NodeRef<'a> {
357    pub fn parent(&self) -> Option<Self> {
358        self.node.parent.map(|id| self.tree.get(id))
359    }
360
361    pub fn parent_element(&self) -> Option<Self> {
362        self.ancestors().find(|n| n.is_element() && !n.is_wrapper())
363    }
364
365    pub fn previous_sibling(&self) -> Option<Self> {
366        self.node.previous_sibling.map(|id| self.tree.get(id))
367    }
368
369    pub fn previous_sibling_element(&self) -> Option<NodeRef<'a>> {
370        self.previous_sibling_elements().next()
371    }
372
373    pub fn next_sibling_element(&self) -> Option<NodeRef<'a>> {
374        self.next_sibling_elements().next()
375    }
376
377    pub fn next_sibling(&self) -> Option<Self> {
378        self.node.next_sibling.map(|id| self.tree.get(id))
379    }
380
381    pub fn first_child(&self) -> Option<Self> {
382        self.node.first_child.map(|id| self.tree.get(id))
383    }
384
385    pub fn last_child(&self) -> Option<Self> {
386        self.node.last_child.map(|id| self.tree.get(id))
387    }
388
389    pub fn ancestors(&self) -> Ancestors<'a> {
390        Ancestors {
391            next: self.parent(),
392        }
393    }
394
395    pub fn ancestor_elements(&self) -> impl Iterator<Item = NodeRef<'a>> {
396        self.ancestors()
397            .filter(|n| n.is_element() && !n.is_wrapper())
398    }
399
400    pub fn previous_siblings(&self) -> PreviousSiblings<'a> {
401        PreviousSiblings {
402            next: self.previous_sibling(),
403        }
404    }
405
406    pub fn next_siblings(&self) -> NextSiblings<'a> {
407        NextSiblings {
408            next: self.next_sibling(),
409        }
410    }
411
412    pub fn previous_sibling_elements(&self) -> impl Iterator<Item = NodeRef<'a>> {
413        self.previous_siblings().filter(|n| n.is_element())
414    }
415
416    pub fn next_sibling_elements(&self) -> impl Iterator<Item = NodeRef<'a>> {
417        self.next_siblings().filter(|n| n.is_element())
418    }
419
420    pub fn children(&self) -> Children<'a> {
421        Children {
422            next: self.first_child(),
423        }
424    }
425
426    pub fn descendants(&self) -> Descendants<'a> {
427        Descendants {
428            root_id: self.id,
429            next: self.first_child(),
430        }
431    }
432
433    pub fn has_children(&self) -> bool {
434        self.node.first_child.is_some()
435    }
436
437    pub fn is_element(&self) -> bool {
438        matches!(
439            self.node.data,
440            NodeData::Element { .. } | NodeData::Wrapper(..) | NodeData::Root
441        )
442    }
443
444    pub fn is_inline(&self) -> bool {
445        match &self.node.data {
446            NodeData::Element(e) => !e.is_block(),
447            NodeData::Text(..) => true,
448            _ => false,
449        }
450    }
451
452    pub fn is_block(&self) -> bool {
453        match &self.node.data {
454            NodeData::Element(e) => e.is_block(),
455            NodeData::Wrapper(..) | NodeData::Root => true,
456            _ => false,
457        }
458    }
459
460    pub fn is_wrapper(&self) -> bool {
461        matches!(self.node.data, NodeData::Wrapper(..))
462    }
463
464    pub fn data(&self) -> &'a NodeData {
465        &self.node.data
466    }
467
468    pub fn offset(&self) -> usize {
469        self.node.data.offset()
470    }
471
472    pub fn text(&self) -> String {
473        self.node.data.text().map(String::from).unwrap_or_else(|| {
474            self.descendants()
475                .filter_map(|n| n.node.data.text())
476                .fold(String::new(), |mut a, b| {
477                    a.push_str(b);
478                    a
479                })
480        })
481    }
482
483    pub fn tag_name(&self) -> Option<&'a str> {
484        match self.node.data {
485            NodeData::Element(ElementData { ref name, .. }) => Some(name),
486            NodeData::Wrapper(..) => Some(WRAPPER_TAG_NAME),
487            _ => None,
488        }
489    }
490
491    pub fn tag_qualified_name(&self) -> Option<&'a str> {
492        match self.node.data {
493            NodeData::Element(ElementData {
494                ref qualified_name, ..
495            }) => qualified_name.as_deref(),
496            _ => None,
497        }
498    }
499
500    pub fn attributes(&self) -> Option<&'a Attributes> {
501        match self.node.data {
502            NodeData::Element(ElementData { ref attributes, .. }) => Some(attributes),
503            _ => None,
504        }
505    }
506
507    pub fn attribute(&self, name: &str) -> Option<&'a str> {
508        self.attributes()
509            .and_then(|a| a.get(name).map(String::as_str))
510    }
511
512    pub fn classes(&self) -> impl Iterator<Item = &'a str> {
513        self.attribute("class").unwrap_or("").split_whitespace()
514    }
515
516    pub fn id(&self) -> Option<&str> {
517        self.attribute("id")
518    }
519
520    pub fn find(&self, tag_name: &str) -> Option<Self> {
521        self.descendants().find(|n| n.tag_name() == Some(tag_name))
522    }
523
524    pub fn find_by_id(&self, id: &str) -> Option<Self> {
525        self.descendants().find(|n| n.id() == Some(id))
526    }
527}
528
529impl<'a> NodeMut<'a> {
530    fn node(&mut self) -> &mut Node {
531        self.tree.node_mut(self.id)
532    }
533
534    pub fn append(&mut self, data: NodeData) -> NodeId {
535        let id = NodeId::from_index(self.tree.nodes.len());
536
537        let node = Node {
538            data,
539            parent: Some(self.id),
540            previous_sibling: self.node().last_child,
541            next_sibling: None,
542            first_child: None,
543            last_child: None,
544        };
545
546        self.tree.nodes.push(node);
547
548        if let Some(last_child) = self.node().last_child {
549            self.tree.node_mut(last_child).next_sibling = Some(id);
550        }
551
552        self.node().last_child = Some(id);
553
554        if self.node().first_child.is_none() {
555            self.node().first_child = Some(id);
556        }
557
558        id
559    }
560
561    pub fn wrap_range(&mut self, first_id: NodeId, last_id: NodeId, data: NodeData) {
562        let before = self.tree.node(first_id).previous_sibling;
563        let after = self.tree.node(last_id).next_sibling;
564        let id = NodeId::from_index(self.tree.nodes.len());
565
566        let node = Node {
567            data,
568            parent: Some(self.id),
569            previous_sibling: before,
570            next_sibling: after,
571            first_child: Some(first_id),
572            last_child: Some(last_id),
573        };
574
575        self.tree.nodes.push(node);
576
577        if let Some(before_id) = before {
578            self.tree.node_mut(before_id).next_sibling = Some(id);
579        }
580
581        if let Some(after_id) = after {
582            self.tree.node_mut(after_id).previous_sibling = Some(id);
583        }
584
585        if let Some(first_child_id) = self.node().first_child {
586            if first_child_id == first_id {
587                self.node().first_child = Some(id);
588            }
589        }
590
591        if let Some(last_child_id) = self.node().last_child {
592            if last_child_id == last_id {
593                self.node().last_child = Some(id);
594            }
595        }
596
597        self.tree.node_mut(first_id).previous_sibling = None;
598        self.tree.node_mut(last_id).next_sibling = None;
599        self.tree.node_mut(first_id).parent = Some(id);
600
601        let mut node_id = first_id;
602        while let Some(next_id) = self.tree.node(node_id).next_sibling {
603            self.tree.node_mut(next_id).parent = Some(id);
604            node_id = next_id;
605        }
606    }
607}
608
609pub struct Ancestors<'a> {
610    next: Option<NodeRef<'a>>,
611}
612
613pub struct NextSiblings<'a> {
614    next: Option<NodeRef<'a>>,
615}
616
617pub struct PreviousSiblings<'a> {
618    next: Option<NodeRef<'a>>,
619}
620
621pub struct Children<'a> {
622    next: Option<NodeRef<'a>>,
623}
624
625pub struct Descendants<'a> {
626    root_id: NodeId,
627    next: Option<NodeRef<'a>>,
628}
629
630impl<'a> Iterator for Ancestors<'a> {
631    type Item = NodeRef<'a>;
632
633    fn next(&mut self) -> Option<Self::Item> {
634        let node = self.next.take();
635        self.next = node.as_ref().and_then(|node| node.parent());
636        node
637    }
638}
639
640impl<'a> Iterator for PreviousSiblings<'a> {
641    type Item = NodeRef<'a>;
642
643    fn next(&mut self) -> Option<Self::Item> {
644        let node = self.next.take();
645        self.next = node.as_ref().and_then(|node| node.previous_sibling());
646        node
647    }
648}
649
650impl<'a> Iterator for NextSiblings<'a> {
651    type Item = NodeRef<'a>;
652
653    fn next(&mut self) -> Option<Self::Item> {
654        let node = self.next.take();
655        self.next = node.as_ref().and_then(|node| node.next_sibling());
656        node
657    }
658}
659
660impl<'a> Iterator for Children<'a> {
661    type Item = NodeRef<'a>;
662
663    fn next(&mut self) -> Option<Self::Item> {
664        let node = self.next.take();
665        self.next = node.as_ref().and_then(|node| node.next_sibling());
666        node
667    }
668}
669
670impl<'a> Iterator for Descendants<'a> {
671    type Item = NodeRef<'a>;
672
673    fn next(&mut self) -> Option<Self::Item> {
674        let node = self.next.take();
675        if let Some(node) = node {
676            self.next = node
677                .first_child()
678                .or_else(|| node.next_sibling())
679                .or_else(|| {
680                    node.ancestors()
681                        .take_while(|n| n.id != self.root_id)
682                        .find(|n| n.node.next_sibling.is_some())
683                        .and_then(|n| n.next_sibling())
684                });
685        }
686        node
687    }
688}
cadmus_core/document/html/dom.rs

cadmus_core/document/html/
dom.rs
