1use crate::tags::Tag;
9
10pub type NodeId = u32;
12
13pub(crate) const NONE: NodeId = NodeId::MAX;
15
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub enum Ns {
18 Html,
19 Svg,
20 MathMl,
21 Xml,
24}
25
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29pub enum AttrNs {
30 None,
31 XLink,
32 Xml,
33 Xmlns,
34 Host(u32),
37}
38
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub enum Quirks {
41 No,
42 Limited,
43 Quirks,
44}
45
46const IN_SOURCE: u32 = 1 << 31;
49
50const IN_EXTRA: u32 = 1 << 30;
53
54pub const MAX_INPUT: usize = 1 << 29;
58
59#[derive(Debug, Clone, Copy)]
60pub(crate) struct Span {
61 pub start: u32,
62 pub end: u32,
63}
64
65#[derive(Debug, Clone, Copy)]
66pub(crate) enum Name {
67 Tag,
69 Svg(u8),
72 Span(Span),
74}
75
76#[derive(Debug, Clone, Copy)]
77pub(crate) struct Attr {
78 pub ns: AttrNs,
79 pub name: Span,
80 pub value: Span,
81}
82
83#[derive(Debug, Clone, Copy)]
84pub(crate) struct Element {
85 pub ns: Ns,
86 pub tag: Tag,
87 pub name: Name,
88 pub attrs: Span,
89 pub contents: NodeId,
91 pub html_integration: bool,
94}
95
96#[derive(Debug, Clone, Copy, PartialEq, Eq)]
99pub enum ShadowRootMode {
100 Open,
101 Closed,
102}
103
104#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
107pub enum SlotAssignment {
108 #[default]
109 Named,
110 Manual,
111}
112
113#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116pub struct ShadowRoot {
117 pub mode: ShadowRootMode,
118 pub delegates_focus: bool,
119 pub clonable: bool,
120 pub serializable: bool,
121 pub slot_assignment: SlotAssignment,
122 pub declarative: bool,
124}
125
126impl ShadowRoot {
127 pub fn open() -> ShadowRoot {
129 ShadowRoot {
130 mode: ShadowRootMode::Open,
131 delegates_focus: false,
132 clonable: false,
133 serializable: false,
134 slot_assignment: SlotAssignment::Named,
135 declarative: false,
136 }
137 }
138
139 pub fn closed() -> ShadowRoot {
141 ShadowRoot {
142 mode: ShadowRootMode::Closed,
143 ..ShadowRoot::open()
144 }
145 }
146}
147
148#[derive(Debug, Clone, Copy)]
149pub(crate) enum Data {
150 Document,
151 Fragment,
152 ShadowRoot {
155 host: NodeId,
156 init: ShadowRoot,
157 },
158 Doctype {
159 name: Span,
160 public_id: Span,
161 system_id: Span,
162 },
163 Element(Element),
164 Text(Span),
165 Comment(Span),
166 ProcessingInstruction {
167 target: Span,
168 data: Span,
169 },
170 Cdata(Span),
172}
173
174#[derive(Debug, Clone, Copy)]
175pub(crate) struct Node {
176 pub parent: NodeId,
177 pub first_child: NodeId,
178 pub last_child: NodeId,
179 pub prev: NodeId,
180 pub next: NodeId,
181 pub data: Data,
182}
183
184pub struct Document {
186 pub(crate) nodes: Vec<Node>,
187 pub(crate) src: String,
190 pub(crate) buf: String,
191 pub(crate) extras: Vec<String>,
196 pub(crate) attrs: Vec<Attr>,
197 pub(crate) quirks: Quirks,
198 pub(crate) scripting: bool,
201 pub(crate) positions: Option<Box<Positions>>,
205 pub(crate) hosts: Option<std::collections::HashMap<NodeId, NodeId>>,
209 pub(crate) shadow_roots: std::collections::HashMap<NodeId, NodeId>,
212 pub(crate) manual_slots: std::collections::HashMap<NodeId, Vec<NodeId>>,
215 pub(crate) errors: Vec<crate::SyntaxError>,
217 pub(crate) dead: Vec<u64>,
220}
221
222const UNKNOWN: [u32; 2] = [u32::MAX; 2];
224
225#[derive(Debug, Default)]
230pub(crate) struct Positions {
231 pub nodes: Vec<[u32; 2]>,
233 pub ends: Vec<[u32; 2]>,
235 pub attrs: Vec<[u32; 2]>,
237 pub crlf: Vec<u32>,
239 pub skipped: u32,
241}
242
243impl Positions {
244 pub(crate) fn set(list: &mut Vec<[u32; 2]>, i: usize, at: [u32; 2]) {
245 if list.len() <= i {
246 list.resize(i + 1, UNKNOWN);
247 }
248 list[i] = at;
249 }
250
251 fn get(list: &[[u32; 2]], i: usize) -> Option<[u32; 2]> {
252 list.get(i).copied().filter(|&a| a != UNKNOWN)
253 }
254
255 pub(crate) fn original(&self, at: u32) -> usize {
257 let dropped = self.crlf.partition_point(|&lf| lf < at);
258 self.skipped as usize + at as usize + dropped
259 }
260
261 fn range(&self, at: [u32; 2]) -> std::ops::Range<usize> {
262 self.original(at[0])..self.original(at[1])
263 }
264}
265
266#[derive(Debug, PartialEq, Eq)]
268pub enum Kind<'a> {
269 Document,
270 Fragment,
271 ShadowRoot(ShadowRoot),
273 Doctype {
274 name: &'a str,
275 public_id: &'a str,
276 system_id: &'a str,
277 },
278 Element {
279 ns: Ns,
280 name: &'a str,
281 },
282 Text(&'a str),
283 Comment(&'a str),
284 ProcessingInstruction {
285 target: &'a str,
286 data: &'a str,
287 },
288 Cdata(&'a str),
289}
290
291impl Document {
292 pub(crate) fn new(root: Data, capacity: usize) -> Document {
293 let mut nodes = Vec::with_capacity(capacity / 10 + 16);
297 nodes.push(Node {
298 parent: NONE,
299 first_child: NONE,
300 last_child: NONE,
301 prev: NONE,
302 next: NONE,
303 data: root,
304 });
305 Document {
306 nodes,
307 src: String::new(),
308 buf: String::with_capacity(capacity / 8),
309 extras: Vec::new(),
310 attrs: Vec::with_capacity(capacity / 32 + 16),
311 quirks: Quirks::No,
312 scripting: false,
313 positions: None,
314 hosts: None,
315 shadow_roots: std::collections::HashMap::new(),
316 manual_slots: std::collections::HashMap::new(),
317 errors: Vec::new(),
318 dead: Vec::new(),
319 }
320 }
321
322 pub fn empty() -> Document {
325 Document::new(Data::Document, 0)
326 }
327
328 pub fn root(&self) -> NodeId {
329 0
330 }
331
332 pub fn quirks(&self) -> Quirks {
333 self.quirks
334 }
335
336 pub fn len(&self) -> usize {
337 self.nodes.len()
338 }
339
340 pub fn is_empty(&self) -> bool {
341 self.nodes.len() <= 1
342 }
343
344 pub(crate) fn str(&self, s: Span) -> &str {
345 if s.start & IN_SOURCE != 0 {
346 &self.src[(s.start & !IN_SOURCE) as usize..(s.end & !IN_SOURCE) as usize]
347 } else if s.start & IN_EXTRA != 0 {
348 &self.extras[(s.start & !IN_EXTRA) as usize]
349 } else {
350 &self.buf[s.start as usize..s.end as usize]
351 }
352 }
353
354 pub(crate) fn push_stable(&mut self, s: &str) -> Span {
357 let at = self.extras.len() as u32 | IN_EXTRA;
358 self.extras.push(s.to_owned());
359 Span { start: at, end: at }
360 }
361
362 pub(crate) fn source_offset(&self, s: &str) -> Option<usize> {
364 let base = self.src.as_ptr() as usize;
365 let at = s.as_ptr() as usize;
366 (at >= base && at + s.len() <= base + self.src.len()).then(|| at - base)
367 }
368
369 pub(crate) fn intern(&mut self, s: &str) -> Span {
372 match self.source_offset(s) {
373 Some(at) => Span {
374 start: at as u32 | IN_SOURCE,
375 end: (at + s.len()) as u32 | IN_SOURCE,
376 },
377 None => self.push_str(s),
378 }
379 }
380
381 pub(crate) fn push_str(&mut self, s: &str) -> Span {
382 let start = self.buf.len() as u32;
383 self.buf.push_str(s);
384 debug_assert!(self.buf.len() < IN_EXTRA as usize, "buffer over 2^30 bytes");
386 Span {
387 start,
388 end: self.buf.len() as u32,
389 }
390 }
391
392 pub(crate) fn add(&mut self, data: Data) -> NodeId {
393 let id = self.nodes.len() as NodeId;
394 self.nodes.push(Node {
395 parent: NONE,
396 first_child: NONE,
397 last_child: NONE,
398 prev: NONE,
399 next: NONE,
400 data,
401 });
402 id
403 }
404
405 pub fn span(&self, id: NodeId) -> Option<std::ops::Range<usize>> {
418 if self.is_removed(id) {
419 return None;
420 }
421 let p = self.positions.as_deref()?;
422 Positions::get(&p.nodes, id as usize).map(|at| p.range(at))
423 }
424
425 pub fn end_span(&self, id: NodeId) -> Option<std::ops::Range<usize>> {
428 if self.is_removed(id) {
429 return None;
430 }
431 let p = self.positions.as_deref()?;
432 Positions::get(&p.ends, id as usize).map(|at| p.range(at))
433 }
434
435 pub fn attr_span(&self, id: NodeId, i: usize) -> Option<std::ops::Range<usize>> {
441 if self.is_removed(id) {
442 return None;
443 }
444 let p = self.positions.as_deref()?;
445 let e = self.element(id)?;
446 let at = e.attrs.start as usize + i;
447 if at >= e.attrs.end as usize {
448 return None;
449 }
450 Positions::get(&p.attrs, at).map(|at| p.range(at))
451 }
452
453 pub fn line_col(&self, offset: usize) -> (usize, usize) {
459 let (skipped, crlf) = self
462 .positions
463 .as_deref()
464 .map_or((0, &[][..]), |p| (p.skipped as usize, &p.crlf[..]));
465 let o = offset.saturating_sub(skipped);
466 let (mut lo, mut hi) = (0, crlf.len());
469 while lo < hi {
470 let mid = (lo + hi) / 2;
471 if crlf[mid] as usize + mid + 1 < o {
472 lo = mid + 1;
473 } else {
474 hi = mid;
475 }
476 }
477 let at = (o - lo.min(o)).min(self.src.len());
478 let bytes = &self.src.as_bytes()[..at];
479 let line = 1 + memchr::memchr_iter(b'\n', bytes).count();
480 let start = memchr::memrchr(b'\n', bytes).map_or(0, |i| i + 1);
481 let column = 1 + bytes[start..]
483 .iter()
484 .filter(|&&b| (b as i8) >= -0x40)
485 .count();
486 (line, column)
487 }
488
489 pub fn errors(&self) -> &[crate::SyntaxError] {
493 &self.errors
494 }
495
496 pub(crate) fn element(&self, id: NodeId) -> Option<&Element> {
497 match &self.nodes[id as usize].data {
498 Data::Element(e) => Some(e),
499 _ => None,
500 }
501 }
502
503 pub(crate) fn element_name(&self, e: &Element) -> &str {
504 match e.name {
505 Name::Tag => e.tag.name(),
506 Name::Svg(i) => crate::tree::SVG_TAG_NAMES[i as usize].1,
507 Name::Span(s) => self.str(s),
508 }
509 }
510
511 pub(crate) fn insert(&mut self, parent: NodeId, child: NodeId, before: NodeId) {
514 debug_assert!(
515 matches!(
516 self.nodes[parent as usize].data,
517 Data::Element(_) | Data::Document | Data::Fragment | Data::ShadowRoot { .. }
518 ),
519 "node {parent} can't have children"
520 );
521 debug_assert!(
522 !matches!(
523 self.nodes[child as usize].data,
524 Data::Document | Data::Fragment | Data::ShadowRoot { .. }
525 ),
526 "node {child} is a document, fragment or shadow root, never a child"
527 );
528 debug_assert!(
529 self.nodes[child as usize].parent == NONE
530 && self.nodes[child as usize].prev == NONE
531 && self.nodes[child as usize].next == NONE,
532 "node {child} is inserted while still linked"
533 );
534 debug_assert!(parent != child, "node {child} inserted into itself");
535 debug_assert!(
536 before == NONE || self.nodes[before as usize].parent == parent,
537 "node {before} isn't a child of {parent}"
538 );
539 let prev = if before == NONE {
540 self.nodes[parent as usize].last_child
541 } else {
542 self.nodes[before as usize].prev
543 };
544 {
545 let c = &mut self.nodes[child as usize];
546 c.parent = parent;
547 c.prev = prev;
548 c.next = before;
549 }
550 if prev == NONE {
551 self.nodes[parent as usize].first_child = child;
552 } else {
553 self.nodes[prev as usize].next = child;
554 }
555 if before == NONE {
556 self.nodes[parent as usize].last_child = child;
557 } else {
558 self.nodes[before as usize].prev = child;
559 }
560 debug_assert!(self.links_agree(child), "links around node {child}");
561 }
562
563 pub fn detach(&mut self, child: NodeId) {
567 let Node {
568 parent, prev, next, ..
569 } = self.nodes[child as usize];
570 if parent == NONE {
571 debug_assert!(
572 prev == NONE && next == NONE,
573 "node {child} has siblings, no parent"
574 );
575 return;
576 }
577 debug_assert!(self.links_agree(child), "links around node {child}");
578 if prev == NONE {
579 self.nodes[parent as usize].first_child = next;
580 } else {
581 self.nodes[prev as usize].next = next;
582 }
583 if next == NONE {
584 self.nodes[parent as usize].last_child = prev;
585 } else {
586 self.nodes[next as usize].prev = prev;
587 }
588 let c = &mut self.nodes[child as usize];
589 c.parent = NONE;
590 c.prev = NONE;
591 c.next = NONE;
592 debug_assert!(
593 (prev == NONE || self.links_agree(prev)) && (next == NONE || self.links_agree(next)),
594 "links where node {child} was"
595 );
596 }
597
598 pub(crate) fn links_agree(&self, id: NodeId) -> bool {
604 let n = &self.nodes[id as usize];
605 if n.parent == NONE {
606 return n.prev == NONE && n.next == NONE;
607 }
608 let p = &self.nodes[n.parent as usize];
609 let prev_ok = if n.prev == NONE {
610 p.first_child == id
611 } else {
612 let s = &self.nodes[n.prev as usize];
613 s.next == id && s.parent == n.parent && p.first_child != id
614 };
615 let next_ok = if n.next == NONE {
616 p.last_child == id
617 } else {
618 let s = &self.nodes[n.next as usize];
619 s.prev == id && s.parent == n.parent && p.last_child != id
620 };
621 prev_ok && next_ok
622 }
623
624 pub(crate) fn append_text(&mut self, id: NodeId, text: &str) {
628 let Data::Text(span) = self.nodes[id as usize].data else {
629 unreachable!("not a text node")
630 };
631 let in_source = span.start & IN_SOURCE != 0;
632 let in_buf = span.start & (IN_SOURCE | IN_EXTRA) == 0;
633 let span =
634 if in_source && self.source_offset(text) == Some((span.end & !IN_SOURCE) as usize) {
635 debug_assert!((span.end & !IN_SOURCE) as usize + text.len() <= self.src.len());
637 Span {
638 start: span.start,
639 end: span.end + text.len() as u32,
640 }
641 } else if in_buf && span.end as usize == self.buf.len() {
642 self.buf.push_str(text);
643 Span {
644 start: span.start,
645 end: self.buf.len() as u32,
646 }
647 } else if span.start & IN_EXTRA != 0 {
648 self.extras[(span.start & !IN_EXTRA) as usize].push_str(text);
650 span
651 } else {
652 let mut own = self.str(span).to_owned();
656 own.push_str(text);
657 let at = self.extras.len() as u32 | IN_EXTRA;
658 self.extras.push(own);
659 Span { start: at, end: at }
660 };
661 self.nodes[id as usize].data = Data::Text(span);
662 }
663
664 #[cfg(debug_assertions)]
676 pub fn check_tree(&self) {
677 let len = self.nodes.len();
678 let span_ok = |s: Span| {
679 if s.start & IN_SOURCE != 0 {
680 let (a, b) = (s.start & !IN_SOURCE, s.end & !IN_SOURCE);
681 s.end & IN_SOURCE != 0
682 && a <= b
683 && self.src.is_char_boundary(a as usize)
684 && self.src.is_char_boundary(b as usize)
685 } else if s.start & IN_EXTRA != 0 {
686 s.start == s.end && ((s.start & !IN_EXTRA) as usize) < self.extras.len()
687 } else {
688 s.start <= s.end
689 && self.buf.is_char_boundary(s.start as usize)
690 && self.buf.is_char_boundary(s.end as usize)
691 }
692 };
693 let mut contents_of = vec![NONE; len];
694 for (id, n) in self.nodes.iter().enumerate() {
695 let id = id as NodeId;
696 for link in [n.parent, n.first_child, n.last_child, n.prev, n.next] {
697 assert!(
698 link == NONE || (link as usize) < len,
699 "node {id} links past the end"
700 );
701 }
702 assert!(self.links_agree(id), "links around node {id}");
703 assert!(
704 !self.is_removed(id) || n.parent == NONE || self.is_removed(n.parent),
705 "removed node {id} is under {}, which isn't",
706 n.parent
707 );
708 assert_eq!(
709 n.first_child == NONE,
710 n.last_child == NONE,
711 "node {id} has a first child or a last, not both"
712 );
713 if n.first_child != NONE {
714 let first = &self.nodes[n.first_child as usize];
715 let last = &self.nodes[n.last_child as usize];
716 assert!(
717 first.parent == id && first.prev == NONE,
718 "node {id}'s first child"
719 );
720 assert!(
721 last.parent == id && last.next == NONE,
722 "node {id}'s last child"
723 );
724 assert!(
725 matches!(
726 n.data,
727 Data::Element(_)
728 | Data::Document
729 | Data::Fragment
730 | Data::ShadowRoot { .. }
731 ),
732 "node {id} can't have children"
733 );
734 }
735 match n.data {
736 Data::Document | Data::Fragment => {
737 assert!(
738 n.parent == NONE,
739 "node {id}, a document or fragment, has a parent"
740 )
741 }
742 Data::ShadowRoot { host, .. } => {
743 assert!(n.parent == NONE, "shadow root {id} has a parent");
744 assert!(
745 self.element(host).is_some(),
746 "shadow root {id}'s host isn't an element"
747 );
748 assert_eq!(
749 self.shadow_roots.get(&host),
750 Some(&id),
751 "shadow root {id} isn't its host's"
752 );
753 }
754 Data::Element(e) => {
755 let name_ok = match e.name {
756 Name::Tag => true,
757 Name::Svg(i) => (i as usize) < crate::tree::SVG_TAG_NAMES.len(),
758 Name::Span(s) => span_ok(s),
759 };
760 assert!(name_ok, "node {id}'s name");
761 assert!(
762 e.attrs.start <= e.attrs.end && e.attrs.end as usize <= self.attrs.len(),
763 "node {id}'s attributes"
764 );
765 if e.contents != NONE {
766 let c = e.contents as usize;
767 assert!(
768 e.ns == Ns::Html && e.tag == Tag::Template,
769 "node {id} has contents but isn't a template"
770 );
771 assert!(
772 c < len && matches!(self.nodes[c].data, Data::Fragment),
773 "node {id}'s contents aren't a fragment"
774 );
775 assert!(contents_of[c] == NONE, "two templates have contents {c}");
776 contents_of[c] = id;
777 }
778 }
779 Data::Doctype {
780 name,
781 public_id,
782 system_id,
783 } => assert!(
784 span_ok(name) && span_ok(public_id) && span_ok(system_id),
785 "node {id}'s strings"
786 ),
787 Data::Text(s) | Data::Comment(s) | Data::Cdata(s) => {
788 assert!(span_ok(s), "node {id}'s text")
789 }
790 Data::ProcessingInstruction { target, data } => {
791 assert!(span_ok(target) && span_ok(data), "node {id}'s strings")
792 }
793 }
794 }
795 for (i, a) in self.attrs.iter().enumerate() {
796 assert!(
797 span_ok(a.name) && span_ok(a.value),
798 "attribute {i}'s strings"
799 );
800 }
801 for (&host, &root) in &self.shadow_roots {
802 assert!(
803 matches!(self.nodes.get(root as usize).map(|n| n.data), Some(Data::ShadowRoot { host: h, .. }) if h == host),
804 "host {host}'s shadow root {root} doesn't name it"
805 );
806 }
807 for (&slot, nodes) in &self.manual_slots {
808 assert!(
809 self.element(slot).is_some(),
810 "manual slot {slot} isn't an element"
811 );
812 assert!(
813 nodes.iter().all(|&n| (n as usize) < len),
814 "manual slot {slot}'s nodes"
815 );
816 }
817 if let Some(hosts) = &self.hosts {
818 for (&contents, &host) in hosts {
819 assert_eq!(
820 contents_of.get(contents as usize),
821 Some(&host),
822 "the hosts map at {contents}"
823 );
824 }
825 let templates = contents_of.iter().filter(|&&h| h != NONE).count();
826 assert_eq!(hosts.len(), templates, "the hosts map misses a template");
827 }
828 let mut seen = vec![false; len];
832 let mut stack = vec![self.root()];
833 while let Some(id) = stack.pop() {
834 assert!(!seen[id as usize], "node {id} reached twice");
835 seen[id as usize] = true;
836 let n = &self.nodes[id as usize];
837 let mut child = n.first_child;
838 while child != NONE {
839 assert!(!seen[child as usize], "a loop among node {id}'s children");
840 assert_eq!(
841 self.nodes[child as usize].parent, id,
842 "node {child}'s parent"
843 );
844 stack.push(child);
845 child = self.nodes[child as usize].next;
846 if stack.len() > len {
847 panic!("a loop among node {id}'s children");
848 }
849 }
850 if let Data::Element(e) = n.data
851 && e.contents != NONE
852 {
853 stack.push(e.contents);
854 }
855 if let Some(&root) = self.shadow_roots.get(&id) {
856 stack.push(root);
857 }
858 }
859 if let Some(p) = self.positions.as_deref() {
860 let src = self.src.len() as u32;
861 let in_src = |at: &[u32; 2]| *at == UNKNOWN || (at[0] <= at[1] && at[1] <= src);
862 assert!(
863 p.nodes.len() <= len && p.ends.len() <= len,
864 "positions past the nodes"
865 );
866 assert!(
867 p.attrs.len() <= self.attrs.len(),
868 "positions past the attributes"
869 );
870 for (i, at) in p.nodes.iter().chain(&p.ends).chain(&p.attrs).enumerate() {
871 assert!(
872 in_src(at),
873 "position {i}, {at:?}, outside {src} bytes of source"
874 );
875 }
876 assert!(p.crlf.windows(2).all(|w| w[0] < w[1]), "CRLFs out of order");
877 assert!(
878 p.crlf.last().is_none_or(|&lf| lf < src),
879 "a CRLF past the source"
880 );
881 let original = p.original(src);
882 for e in &self.errors {
883 assert!(
884 e.offset <= original,
885 "{e:?} past the input's {original} bytes"
886 );
887 }
888 }
889 }
890
891 pub fn parent(&self, id: NodeId) -> Option<NodeId> {
892 if self.is_removed(id) {
893 return None;
894 }
895 Some(self.nodes[id as usize].parent).filter(|&p| p != NONE)
896 }
897
898 pub fn first_child(&self, id: NodeId) -> Option<NodeId> {
899 if self.is_removed(id) {
900 return None;
901 }
902 Some(self.nodes[id as usize].first_child).filter(|&c| c != NONE)
903 }
904
905 pub fn prev_sibling(&self, id: NodeId) -> Option<NodeId> {
906 if self.is_removed(id) {
907 return None;
908 }
909 Some(self.nodes[id as usize].prev).filter(|&c| c != NONE)
910 }
911
912 pub fn last_child(&self, id: NodeId) -> Option<NodeId> {
913 if self.is_removed(id) {
914 return None;
915 }
916 Some(self.nodes[id as usize].last_child).filter(|&c| c != NONE)
917 }
918
919 pub fn next_sibling(&self, id: NodeId) -> Option<NodeId> {
920 if self.is_removed(id) {
921 return None;
922 }
923 Some(self.nodes[id as usize].next).filter(|&c| c != NONE)
924 }
925
926 pub fn children(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_ {
927 std::iter::successors(self.first_child(id), move |&c| self.next_sibling(c))
928 }
929
930 pub fn template_contents(&self, id: NodeId) -> Option<NodeId> {
932 if self.is_removed(id) {
933 return None;
934 }
935 self.element(id).map(|e| e.contents).filter(|&c| c != NONE)
936 }
937
938 pub fn is_removed(&self, id: NodeId) -> bool {
944 self.dead
945 .get(id as usize / 64)
946 .is_some_and(|w| w >> (id % 64) & 1 == 1)
947 }
948
949 pub(crate) fn mark_removed(&mut self, id: NodeId) {
950 let word = id as usize / 64;
951 if self.dead.len() <= word {
952 self.dead.resize(word + 1, 0);
953 }
954 self.dead[word] |= 1 << (id % 64);
955 }
956
957 pub fn kind(&self, id: NodeId) -> Kind<'_> {
961 let kind = self.kind_of(id);
962 if !self.is_removed(id) {
963 return kind;
964 }
965 match kind {
966 Kind::Text(_) => Kind::Text(""),
967 Kind::Comment(_) => Kind::Comment(""),
968 Kind::Cdata(_) => Kind::Cdata(""),
969 Kind::ProcessingInstruction { target, .. } => {
970 Kind::ProcessingInstruction { target, data: "" }
971 }
972 other => other,
973 }
974 }
975
976 fn kind_of(&self, id: NodeId) -> Kind<'_> {
977 match &self.nodes[id as usize].data {
978 Data::Document => Kind::Document,
979 Data::Fragment => Kind::Fragment,
980 Data::ShadowRoot { init, .. } => Kind::ShadowRoot(*init),
981 Data::Doctype {
982 name,
983 public_id,
984 system_id,
985 } => Kind::Doctype {
986 name: self.str(*name),
987 public_id: self.str(*public_id),
988 system_id: self.str(*system_id),
989 },
990 Data::Element(e) => Kind::Element {
991 ns: e.ns,
992 name: self.element_name(e),
993 },
994 Data::Text(s) => Kind::Text(self.str(*s)),
995 Data::Comment(s) => Kind::Comment(self.str(*s)),
996 Data::Cdata(s) => Kind::Cdata(self.str(*s)),
997 Data::ProcessingInstruction { target, data } => Kind::ProcessingInstruction {
998 target: self.str(*target),
999 data: self.str(*data),
1000 },
1001 }
1002 }
1003
1004 pub fn attrs(&self, id: NodeId) -> impl Iterator<Item = (AttrNs, &str, &str)> + '_ {
1007 let attrs = if self.is_removed(id) {
1008 &[][..]
1009 } else {
1010 self.attrs_of(id)
1011 };
1012 attrs.iter().map(|a| {
1013 let name = self.str(a.name);
1014 let name = match a.ns {
1015 AttrNs::XLink | AttrNs::Xml | AttrNs::Xmlns => {
1016 name.split_once(':').map_or(name, |(_, local)| local)
1017 }
1018 _ => name,
1019 };
1020 (a.ns, name, self.str(a.value))
1021 })
1022 }
1023
1024 pub fn attrs_written(&self, id: NodeId) -> impl Iterator<Item = (AttrNs, &str, &str)> + '_ {
1027 let ns = self.element(id).map_or(Ns::Html, |e| e.ns);
1028 let attrs = if self.is_removed(id) {
1029 &[][..]
1030 } else {
1031 self.attrs_of(id)
1032 };
1033 attrs
1034 .iter()
1035 .map(move |a| (a.ns, self.written_name(ns, a), self.str(a.value)))
1036 }
1037
1038 pub(crate) fn attrs_of(&self, id: NodeId) -> &[Attr] {
1039 let range = self
1040 .element(id)
1041 .map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
1042 &self.attrs[range]
1043 }
1044
1045 pub(crate) fn written_name(&self, ns: Ns, a: &Attr) -> &str {
1048 let name = self.str(a.name);
1049 match (ns, a.ns) {
1050 (Ns::Svg, AttrNs::None) => crate::tree::svg_attr_name(name).unwrap_or(name),
1051 (Ns::MathMl, AttrNs::None) if name == "definitionurl" => "definitionURL",
1052 _ => name,
1053 }
1054 }
1055
1056 pub fn lower_name(&self, id: NodeId) -> Option<&str> {
1062 if self.is_removed(id) {
1063 return None;
1064 }
1065 let e = self.element(id)?;
1066 Some(match e.name {
1067 Name::Tag => e.tag.name(),
1068 Name::Svg(i) => crate::tree::SVG_TAG_NAMES[i as usize].0,
1069 Name::Span(s) => self.str(s),
1070 })
1071 }
1072
1073 pub fn known_tag(&self, id: NodeId) -> Option<u8> {
1078 if self.is_removed(id) {
1079 return None;
1080 }
1081 self.element(id)
1082 .filter(|e| e.tag != Tag::Other && e.ns != Ns::Xml)
1083 .map(|e| e.tag as u8)
1084 }
1085}
1086
1087#[cfg(test)]
1088mod tests {
1089 use crate::{AttrNs, parse};
1090
1091 #[test]
1095 fn foreign_attributes_have_a_lowercase_name_and_a_written_one() {
1096 let doc = parse(
1097 "<svg viewBox=0 xmlns:xlink=x><use xlink:href=#i></use></svg>\
1098 <math definitionURL=d></math>",
1099 false,
1100 );
1101 let svg = (0..doc.len() as u32)
1102 .find(|&n| doc.lower_name(n) == Some("svg"))
1103 .unwrap();
1104 let use_ = doc.first_child(svg).unwrap();
1105 let math = doc.next_sibling(svg).unwrap();
1106 let names = |n, written: bool| -> Vec<String> {
1107 if written {
1108 doc.attrs_written(n)
1109 .map(|(_, a, _)| a.to_string())
1110 .collect()
1111 } else {
1112 doc.attrs(n).map(|(_, a, _)| a.to_string()).collect()
1113 }
1114 };
1115 assert_eq!(names(svg, false), ["viewbox", "xlink"]);
1116 assert_eq!(names(svg, true), ["viewBox", "xmlns:xlink"]);
1117 assert_eq!(names(use_, false), ["href"]);
1118 assert_eq!(doc.attrs(use_).next().unwrap().0, AttrNs::XLink);
1119 assert_eq!(names(use_, true), ["xlink:href"]);
1120 assert_eq!(names(math, false), ["definitionurl"]);
1121 assert_eq!(names(math, true), ["definitionURL"]);
1122 assert!(doc.outer_html(svg).starts_with(r#"<svg viewBox="0""#));
1123 assert!(doc.outer_html(math).contains("definitionURL"));
1124 }
1125
1126 #[test]
1127 fn an_edit_finds_a_foreign_attribute_by_its_written_name() {
1128 let mut doc = parse("<svg viewBox=0></svg>", false);
1129 let svg = (0..doc.len() as u32)
1130 .find(|&n| doc.lower_name(n) == Some("svg"))
1131 .unwrap();
1132 doc.set_attr(svg, "viewBox", "1");
1133 assert_eq!(doc.outer_html(svg), r#"<svg viewBox="1"></svg>"#);
1134 assert!(doc.remove_attr(svg, "viewBox"));
1135 assert_eq!(doc.outer_html(svg), "<svg></svg>");
1136 }
1137}