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;
60
61#[derive(Debug, Clone, Copy)]
62pub(crate) struct Span {
63 pub start: u32,
64 pub end: u32,
65}
66
67#[derive(Debug, Clone, Copy)]
68pub(crate) enum Name {
69 Tag,
71 Svg(u8),
74 Span(Span),
76}
77
78#[derive(Debug, Clone, Copy)]
79pub(crate) struct Attr {
80 pub ns: AttrNs,
81 pub name: Span,
82 pub value: Span,
83}
84
85#[derive(Debug, Clone, Copy)]
86pub(crate) struct Element {
87 pub ns: Ns,
88 pub tag: Tag,
89 pub name: Name,
90 pub attrs: Span,
91 pub contents: NodeId,
93 pub html_integration: bool,
96}
97
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101pub enum ShadowRootMode {
102 Open,
103 Closed,
104}
105
106#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
109pub enum SlotAssignment {
110 #[default]
111 Named,
112 Manual,
113}
114
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
118pub struct ShadowRoot {
119 pub mode: ShadowRootMode,
120 pub delegates_focus: bool,
121 pub clonable: bool,
122 pub serializable: bool,
123 pub slot_assignment: SlotAssignment,
124 pub declarative: bool,
126}
127
128impl ShadowRoot {
129 pub fn open() -> ShadowRoot {
131 ShadowRoot {
132 mode: ShadowRootMode::Open,
133 delegates_focus: false,
134 clonable: false,
135 serializable: false,
136 slot_assignment: SlotAssignment::Named,
137 declarative: false,
138 }
139 }
140
141 pub fn closed() -> ShadowRoot {
143 ShadowRoot {
144 mode: ShadowRootMode::Closed,
145 ..ShadowRoot::open()
146 }
147 }
148}
149
150#[derive(Debug, Clone, Copy)]
151pub(crate) enum Data {
152 Document,
153 Fragment,
154 ShadowRoot {
157 host: NodeId,
158 init: ShadowRoot,
159 },
160 Doctype {
161 name: Span,
162 public_id: Span,
163 system_id: Span,
164 },
165 Element(Element),
166 Text(Span),
167 Comment(Span),
168 ProcessingInstruction {
169 target: Span,
170 data: Span,
171 },
172 Cdata(Span),
174}
175
176#[derive(Debug, Clone, Copy)]
177pub(crate) struct Node {
178 pub parent: NodeId,
179 pub first_child: NodeId,
180 pub last_child: NodeId,
181 pub prev: NodeId,
182 pub next: NodeId,
183 pub data: Data,
184}
185
186pub struct Document {
188 pub(crate) nodes: Vec<Node>,
189 pub(crate) src: String,
192 pub(crate) buf: String,
193 pub(crate) extras: Vec<String>,
198 pub(crate) attrs: Vec<Attr>,
199 pub(crate) quirks: Quirks,
200 pub(crate) scripting: bool,
203 pub(crate) positions: Option<Box<Positions>>,
207 pub(crate) hosts: Option<std::collections::HashMap<NodeId, NodeId>>,
211 pub(crate) shadow_roots: std::collections::HashMap<NodeId, NodeId>,
214 pub(crate) manual_slots: std::collections::HashMap<NodeId, Vec<NodeId>>,
217 pub(crate) errors: Vec<crate::SyntaxError>,
219 pub(crate) dead: Vec<u64>,
222 lines: std::sync::OnceLock<Lines>,
224}
225
226struct Lines {
230 starts: Vec<u32>,
231 chars: Vec<u32>,
232}
233
234impl Lines {
235 const BLOCK: usize = 4096;
236
237 fn new(src: &[u8]) -> Lines {
238 let mut starts = vec![0];
239 starts.extend(memchr::memchr_iter(b'\n', src).map(|i| i as u32 + 1));
240 let mut chars = Vec::with_capacity(src.len() / Lines::BLOCK + 1);
241 let mut before = 0;
242 for block in src.chunks(Lines::BLOCK) {
243 chars.push(before);
244 before += count_chars(block) as u32;
245 }
246 chars.push(before);
248 Lines { starts, chars }
249 }
250
251 fn chars_before(&self, src: &[u8], at: usize) -> usize {
253 let block = at / Lines::BLOCK;
254 self.chars[block] as usize + count_chars(&src[block * Lines::BLOCK..at])
255 }
256}
257
258fn count_chars(bytes: &[u8]) -> usize {
261 bytes.iter().filter(|&&b| (b as i8) >= -0x40).count()
262}
263
264const UNKNOWN: [u32; 2] = [u32::MAX; 2];
266
267#[derive(Debug, Default)]
272pub(crate) struct Positions {
273 pub nodes: Vec<[u32; 2]>,
275 pub ends: Vec<[u32; 2]>,
277 pub attrs: Vec<[u32; 2]>,
279 pub crlf: Vec<u32>,
281 pub skipped: u32,
283}
284
285impl Positions {
286 pub(crate) fn set(list: &mut Vec<[u32; 2]>, i: usize, at: [u32; 2]) {
287 if list.len() <= i {
288 list.resize(i + 1, UNKNOWN);
289 }
290 list[i] = at;
291 }
292
293 fn get(list: &[[u32; 2]], i: usize) -> Option<[u32; 2]> {
294 list.get(i).copied().filter(|&a| a != UNKNOWN)
295 }
296
297 pub(crate) fn original(&self, at: u32) -> usize {
299 let dropped = self.crlf.partition_point(|&lf| lf < at);
300 self.skipped as usize + at as usize + dropped
301 }
302
303 fn range(&self, at: [u32; 2]) -> std::ops::Range<usize> {
304 self.original(at[0])..self.original(at[1])
305 }
306}
307
308#[derive(Debug, PartialEq, Eq)]
310pub enum Kind<'a> {
311 Document,
312 Fragment,
313 ShadowRoot(ShadowRoot),
315 Doctype {
316 name: &'a str,
317 public_id: &'a str,
318 system_id: &'a str,
319 },
320 Element {
321 ns: Ns,
322 name: &'a str,
323 },
324 Text(&'a str),
325 Comment(&'a str),
326 ProcessingInstruction {
327 target: &'a str,
328 data: &'a str,
329 },
330 Cdata(&'a str),
331}
332
333impl Document {
334 pub(crate) fn new(root: Data, capacity: usize) -> Document {
335 let mut nodes = Vec::with_capacity(capacity / 10 + 16);
339 nodes.push(Node {
340 parent: NONE,
341 first_child: NONE,
342 last_child: NONE,
343 prev: NONE,
344 next: NONE,
345 data: root,
346 });
347 Document {
348 nodes,
349 src: String::new(),
350 buf: String::with_capacity(capacity / 8),
351 extras: Vec::new(),
352 attrs: Vec::with_capacity(capacity / 32 + 16),
353 quirks: Quirks::No,
354 scripting: false,
355 positions: None,
356 hosts: None,
357 shadow_roots: std::collections::HashMap::new(),
358 manual_slots: std::collections::HashMap::new(),
359 errors: Vec::new(),
360 dead: Vec::new(),
361 lines: std::sync::OnceLock::new(),
362 }
363 }
364
365 pub fn empty() -> Document {
368 Document::new(Data::Document, 0)
369 }
370
371 pub fn root(&self) -> NodeId {
372 0
373 }
374
375 pub fn quirks(&self) -> Quirks {
376 self.quirks
377 }
378
379 pub fn len(&self) -> usize {
380 self.nodes.len()
381 }
382
383 pub fn is_empty(&self) -> bool {
384 self.nodes.len() <= 1
385 }
386
387 pub(crate) fn str(&self, s: Span) -> &str {
388 if s.start & IN_SOURCE != 0 {
389 &self.src[(s.start & !IN_SOURCE) as usize..(s.end & !IN_SOURCE) as usize]
390 } else if s.start & IN_EXTRA != 0 {
391 &self.extras[(s.start & !IN_EXTRA) as usize]
392 } else {
393 &self.buf[s.start as usize..s.end as usize]
394 }
395 }
396
397 pub(crate) fn push_stable(&mut self, s: &str) -> Span {
400 let at = self.extras.len() as u32 | IN_EXTRA;
401 self.extras.push(s.to_owned());
402 Span { start: at, end: at }
403 }
404
405 pub(crate) fn source_offset(&self, s: &str) -> Option<usize> {
407 let base = self.src.as_ptr() as usize;
408 let at = s.as_ptr() as usize;
409 (at >= base && at + s.len() <= base + self.src.len()).then(|| at - base)
410 }
411
412 pub(crate) fn intern(&mut self, s: &str) -> Span {
415 match self.source_offset(s) {
416 Some(at) => Span {
417 start: at as u32 | IN_SOURCE,
418 end: (at + s.len()) as u32 | IN_SOURCE,
419 },
420 None => self.push_str(s),
421 }
422 }
423
424 pub(crate) fn push_str(&mut self, s: &str) -> Span {
425 if self.buf.len() + s.len() >= IN_EXTRA as usize {
427 return self.push_stable(s);
428 }
429 let start = self.buf.len() as u32;
430 self.buf.push_str(s);
431 Span {
432 start,
433 end: self.buf.len() as u32,
434 }
435 }
436
437 pub(crate) fn add(&mut self, data: Data) -> NodeId {
438 let id = self.nodes.len() as NodeId;
439 self.nodes.push(Node {
440 parent: NONE,
441 first_child: NONE,
442 last_child: NONE,
443 prev: NONE,
444 next: NONE,
445 data,
446 });
447 id
448 }
449
450 pub fn span(&self, id: NodeId) -> Option<std::ops::Range<usize>> {
463 if self.is_removed(id) {
464 return None;
465 }
466 let p = self.positions.as_deref()?;
467 Positions::get(&p.nodes, id as usize).map(|at| p.range(at))
468 }
469
470 pub fn end_span(&self, id: NodeId) -> Option<std::ops::Range<usize>> {
473 if self.is_removed(id) {
474 return None;
475 }
476 let p = self.positions.as_deref()?;
477 Positions::get(&p.ends, id as usize).map(|at| p.range(at))
478 }
479
480 pub fn attr_span(&self, id: NodeId, i: usize) -> Option<std::ops::Range<usize>> {
486 if self.is_removed(id) {
487 return None;
488 }
489 let p = self.positions.as_deref()?;
490 let e = self.element(id)?;
491 let at = e.attrs.start as usize + i;
492 if at >= e.attrs.end as usize {
493 return None;
494 }
495 Positions::get(&p.attrs, at).map(|at| p.range(at))
496 }
497
498 pub fn line_col(&self, offset: usize) -> (usize, usize) {
505 let (skipped, crlf) = self
508 .positions
509 .as_deref()
510 .map_or((0, &[][..]), |p| (p.skipped as usize, &p.crlf[..]));
511 let o = offset.saturating_sub(skipped);
512 let (mut lo, mut hi) = (0, crlf.len());
515 while lo < hi {
516 let mid = (lo + hi) / 2;
517 if crlf[mid] as usize + mid + 1 < o {
518 lo = mid + 1;
519 } else {
520 hi = mid;
521 }
522 }
523 let at = (o - lo.min(o)).min(self.src.len());
524 let src = self.src.as_bytes();
525 let lines = self.lines.get_or_init(|| Lines::new(src));
526 let line = lines.starts.partition_point(|&s| s as usize <= at);
527 let start = lines.starts[line - 1] as usize;
528 let column = 1 + lines.chars_before(src, at) - lines.chars_before(src, start);
529 (line, column)
530 }
531
532 pub fn errors(&self) -> &[crate::SyntaxError] {
536 &self.errors
537 }
538
539 pub(crate) fn element(&self, id: NodeId) -> Option<&Element> {
540 match &self.nodes[id as usize].data {
541 Data::Element(e) => Some(e),
542 _ => None,
543 }
544 }
545
546 pub(crate) fn element_name(&self, e: &Element) -> &str {
547 match e.name {
548 Name::Tag => e.tag.name(),
549 Name::Svg(i) => crate::tree::SVG_TAG_NAMES[i as usize].1,
550 Name::Span(s) => self.str(s),
551 }
552 }
553
554 pub(crate) fn insert(&mut self, parent: NodeId, child: NodeId, before: NodeId) {
557 debug_assert!(
558 matches!(
559 self.nodes[parent as usize].data,
560 Data::Element(_) | Data::Document | Data::Fragment | Data::ShadowRoot { .. }
561 ),
562 "node {parent} can't have children"
563 );
564 debug_assert!(
565 !matches!(
566 self.nodes[child as usize].data,
567 Data::Document | Data::Fragment | Data::ShadowRoot { .. }
568 ),
569 "node {child} is a document, fragment or shadow root, never a child"
570 );
571 debug_assert!(
572 self.nodes[child as usize].parent == NONE
573 && self.nodes[child as usize].prev == NONE
574 && self.nodes[child as usize].next == NONE,
575 "node {child} is inserted while still linked"
576 );
577 debug_assert!(parent != child, "node {child} inserted into itself");
578 debug_assert!(
579 before == NONE || self.nodes[before as usize].parent == parent,
580 "node {before} isn't a child of {parent}"
581 );
582 let prev = if before == NONE {
583 self.nodes[parent as usize].last_child
584 } else {
585 self.nodes[before as usize].prev
586 };
587 {
588 let c = &mut self.nodes[child as usize];
589 c.parent = parent;
590 c.prev = prev;
591 c.next = before;
592 }
593 if prev == NONE {
594 self.nodes[parent as usize].first_child = child;
595 } else {
596 self.nodes[prev as usize].next = child;
597 }
598 if before == NONE {
599 self.nodes[parent as usize].last_child = child;
600 } else {
601 self.nodes[before as usize].prev = child;
602 }
603 debug_assert!(self.links_agree(child), "links around node {child}");
604 }
605
606 pub fn detach(&mut self, child: NodeId) {
610 let Node {
611 parent, prev, next, ..
612 } = self.nodes[child as usize];
613 if parent == NONE {
614 debug_assert!(
615 prev == NONE && next == NONE,
616 "node {child} has siblings, no parent"
617 );
618 return;
619 }
620 debug_assert!(self.links_agree(child), "links around node {child}");
621 if prev == NONE {
622 self.nodes[parent as usize].first_child = next;
623 } else {
624 self.nodes[prev as usize].next = next;
625 }
626 if next == NONE {
627 self.nodes[parent as usize].last_child = prev;
628 } else {
629 self.nodes[next as usize].prev = prev;
630 }
631 let c = &mut self.nodes[child as usize];
632 c.parent = NONE;
633 c.prev = NONE;
634 c.next = NONE;
635 debug_assert!(
636 (prev == NONE || self.links_agree(prev)) && (next == NONE || self.links_agree(next)),
637 "links where node {child} was"
638 );
639 }
640
641 pub(crate) fn links_agree(&self, id: NodeId) -> bool {
647 let n = &self.nodes[id as usize];
648 if n.parent == NONE {
649 return n.prev == NONE && n.next == NONE;
650 }
651 let p = &self.nodes[n.parent as usize];
652 let prev_ok = if n.prev == NONE {
653 p.first_child == id
654 } else {
655 let s = &self.nodes[n.prev as usize];
656 s.next == id && s.parent == n.parent && p.first_child != id
657 };
658 let next_ok = if n.next == NONE {
659 p.last_child == id
660 } else {
661 let s = &self.nodes[n.next as usize];
662 s.prev == id && s.parent == n.parent && p.last_child != id
663 };
664 prev_ok && next_ok
665 }
666
667 pub(crate) fn append_text(&mut self, id: NodeId, text: &str) {
671 let Data::Text(span) = self.nodes[id as usize].data else {
672 unreachable!("not a text node")
673 };
674 let in_source = span.start & IN_SOURCE != 0;
675 let in_buf = span.start & (IN_SOURCE | IN_EXTRA) == 0;
676 let span =
677 if in_source && self.source_offset(text) == Some((span.end & !IN_SOURCE) as usize) {
678 debug_assert!((span.end & !IN_SOURCE) as usize + text.len() <= self.src.len());
680 Span {
681 start: span.start,
682 end: span.end + text.len() as u32,
683 }
684 } else if in_buf
685 && span.end as usize == self.buf.len()
686 && self.buf.len() + text.len() < IN_EXTRA as usize
687 {
688 self.buf.push_str(text);
689 Span {
690 start: span.start,
691 end: self.buf.len() as u32,
692 }
693 } else if span.start & IN_EXTRA != 0 {
694 self.extras[(span.start & !IN_EXTRA) as usize].push_str(text);
696 span
697 } else {
698 let mut own = self.str(span).to_owned();
702 own.push_str(text);
703 let at = self.extras.len() as u32 | IN_EXTRA;
704 self.extras.push(own);
705 Span { start: at, end: at }
706 };
707 self.nodes[id as usize].data = Data::Text(span);
708 }
709
710 #[cfg(debug_assertions)]
722 pub fn check_tree(&self) {
723 let len = self.nodes.len();
724 let span_ok = |s: Span| {
725 if s.start & IN_SOURCE != 0 {
726 let (a, b) = (s.start & !IN_SOURCE, s.end & !IN_SOURCE);
727 s.end & IN_SOURCE != 0
728 && a <= b
729 && self.src.is_char_boundary(a as usize)
730 && self.src.is_char_boundary(b as usize)
731 } else if s.start & IN_EXTRA != 0 {
732 s.start == s.end && ((s.start & !IN_EXTRA) as usize) < self.extras.len()
733 } else {
734 s.start <= s.end
735 && self.buf.is_char_boundary(s.start as usize)
736 && self.buf.is_char_boundary(s.end as usize)
737 }
738 };
739 let mut contents_of = vec![NONE; len];
740 for (id, n) in self.nodes.iter().enumerate() {
741 let id = id as NodeId;
742 for link in [n.parent, n.first_child, n.last_child, n.prev, n.next] {
743 assert!(
744 link == NONE || (link as usize) < len,
745 "node {id} links past the end"
746 );
747 }
748 assert!(self.links_agree(id), "links around node {id}");
749 assert!(
750 !self.is_removed(id) || n.parent == NONE || self.is_removed(n.parent),
751 "removed node {id} is under {}, which isn't",
752 n.parent
753 );
754 assert_eq!(
755 n.first_child == NONE,
756 n.last_child == NONE,
757 "node {id} has a first child or a last, not both"
758 );
759 if n.first_child != NONE {
760 let first = &self.nodes[n.first_child as usize];
761 let last = &self.nodes[n.last_child as usize];
762 assert!(
763 first.parent == id && first.prev == NONE,
764 "node {id}'s first child"
765 );
766 assert!(
767 last.parent == id && last.next == NONE,
768 "node {id}'s last child"
769 );
770 assert!(
771 matches!(
772 n.data,
773 Data::Element(_)
774 | Data::Document
775 | Data::Fragment
776 | Data::ShadowRoot { .. }
777 ),
778 "node {id} can't have children"
779 );
780 }
781 match n.data {
782 Data::Document | Data::Fragment => {
783 assert!(
784 n.parent == NONE,
785 "node {id}, a document or fragment, has a parent"
786 )
787 }
788 Data::ShadowRoot { host, .. } => {
789 assert!(n.parent == NONE, "shadow root {id} has a parent");
790 assert!(
791 self.element(host).is_some(),
792 "shadow root {id}'s host isn't an element"
793 );
794 assert_eq!(
795 self.shadow_roots.get(&host),
796 Some(&id),
797 "shadow root {id} isn't its host's"
798 );
799 }
800 Data::Element(e) => {
801 let name_ok = match e.name {
802 Name::Tag => true,
803 Name::Svg(i) => (i as usize) < crate::tree::SVG_TAG_NAMES.len(),
804 Name::Span(s) => span_ok(s),
805 };
806 assert!(name_ok, "node {id}'s name");
807 assert!(
808 e.attrs.start <= e.attrs.end && e.attrs.end as usize <= self.attrs.len(),
809 "node {id}'s attributes"
810 );
811 if e.contents != NONE {
812 let c = e.contents as usize;
813 assert!(
814 e.ns == Ns::Html && e.tag == Tag::Template,
815 "node {id} has contents but isn't a template"
816 );
817 assert!(
818 c < len && matches!(self.nodes[c].data, Data::Fragment),
819 "node {id}'s contents aren't a fragment"
820 );
821 assert!(contents_of[c] == NONE, "two templates have contents {c}");
822 contents_of[c] = id;
823 }
824 }
825 Data::Doctype {
826 name,
827 public_id,
828 system_id,
829 } => assert!(
830 span_ok(name) && span_ok(public_id) && span_ok(system_id),
831 "node {id}'s strings"
832 ),
833 Data::Text(s) | Data::Comment(s) | Data::Cdata(s) => {
834 assert!(span_ok(s), "node {id}'s text")
835 }
836 Data::ProcessingInstruction { target, data } => {
837 assert!(span_ok(target) && span_ok(data), "node {id}'s strings")
838 }
839 }
840 }
841 for (i, a) in self.attrs.iter().enumerate() {
842 assert!(
843 span_ok(a.name) && span_ok(a.value),
844 "attribute {i}'s strings"
845 );
846 }
847 for (&host, &root) in &self.shadow_roots {
848 assert!(
849 matches!(self.nodes.get(root as usize).map(|n| n.data), Some(Data::ShadowRoot { host: h, .. }) if h == host),
850 "host {host}'s shadow root {root} doesn't name it"
851 );
852 }
853 for (&slot, nodes) in &self.manual_slots {
854 assert!(
855 self.element(slot).is_some(),
856 "manual slot {slot} isn't an element"
857 );
858 assert!(
859 nodes.iter().all(|&n| (n as usize) < len),
860 "manual slot {slot}'s nodes"
861 );
862 }
863 if let Some(hosts) = &self.hosts {
864 for (&contents, &host) in hosts {
865 assert_eq!(
866 contents_of.get(contents as usize),
867 Some(&host),
868 "the hosts map at {contents}"
869 );
870 }
871 let templates = contents_of.iter().filter(|&&h| h != NONE).count();
872 assert_eq!(hosts.len(), templates, "the hosts map misses a template");
873 }
874 let mut seen = vec![false; len];
878 let mut stack = vec![self.root()];
879 while let Some(id) = stack.pop() {
880 assert!(!seen[id as usize], "node {id} reached twice");
881 seen[id as usize] = true;
882 let n = &self.nodes[id as usize];
883 let mut child = n.first_child;
884 while child != NONE {
885 assert!(!seen[child as usize], "a loop among node {id}'s children");
886 assert_eq!(
887 self.nodes[child as usize].parent, id,
888 "node {child}'s parent"
889 );
890 stack.push(child);
891 child = self.nodes[child as usize].next;
892 if stack.len() > len {
893 panic!("a loop among node {id}'s children");
894 }
895 }
896 if let Data::Element(e) = n.data
897 && e.contents != NONE
898 {
899 stack.push(e.contents);
900 }
901 if let Some(&root) = self.shadow_roots.get(&id) {
902 stack.push(root);
903 }
904 }
905 if let Some(p) = self.positions.as_deref() {
906 let src = self.src.len() as u32;
907 let in_src = |at: &[u32; 2]| *at == UNKNOWN || (at[0] <= at[1] && at[1] <= src);
908 assert!(
909 p.nodes.len() <= len && p.ends.len() <= len,
910 "positions past the nodes"
911 );
912 assert!(
913 p.attrs.len() <= self.attrs.len(),
914 "positions past the attributes"
915 );
916 for (i, at) in p.nodes.iter().chain(&p.ends).chain(&p.attrs).enumerate() {
917 assert!(
918 in_src(at),
919 "position {i}, {at:?}, outside {src} bytes of source"
920 );
921 }
922 assert!(p.crlf.windows(2).all(|w| w[0] < w[1]), "CRLFs out of order");
923 assert!(
924 p.crlf.last().is_none_or(|&lf| lf < src),
925 "a CRLF past the source"
926 );
927 let original = p.original(src);
928 for e in &self.errors {
929 assert!(
930 e.offset <= original,
931 "{e:?} past the input's {original} bytes"
932 );
933 }
934 }
935 }
936
937 pub fn parent(&self, id: NodeId) -> Option<NodeId> {
938 if self.is_removed(id) {
939 return None;
940 }
941 Some(self.nodes[id as usize].parent).filter(|&p| p != NONE)
942 }
943
944 pub fn first_child(&self, id: NodeId) -> Option<NodeId> {
945 if self.is_removed(id) {
946 return None;
947 }
948 Some(self.nodes[id as usize].first_child).filter(|&c| c != NONE)
949 }
950
951 pub fn prev_sibling(&self, id: NodeId) -> Option<NodeId> {
952 if self.is_removed(id) {
953 return None;
954 }
955 Some(self.nodes[id as usize].prev).filter(|&c| c != NONE)
956 }
957
958 pub fn last_child(&self, id: NodeId) -> Option<NodeId> {
959 if self.is_removed(id) {
960 return None;
961 }
962 Some(self.nodes[id as usize].last_child).filter(|&c| c != NONE)
963 }
964
965 pub fn next_sibling(&self, id: NodeId) -> Option<NodeId> {
966 if self.is_removed(id) {
967 return None;
968 }
969 Some(self.nodes[id as usize].next).filter(|&c| c != NONE)
970 }
971
972 pub fn children(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_ {
973 std::iter::successors(self.first_child(id), move |&c| self.next_sibling(c))
974 }
975
976 pub fn template_contents(&self, id: NodeId) -> Option<NodeId> {
978 if self.is_removed(id) {
979 return None;
980 }
981 self.element(id).map(|e| e.contents).filter(|&c| c != NONE)
982 }
983
984 pub fn is_removed(&self, id: NodeId) -> bool {
990 self.dead
991 .get(id as usize / 64)
992 .is_some_and(|w| w >> (id % 64) & 1 == 1)
993 }
994
995 pub(crate) fn mark_removed(&mut self, id: NodeId) {
996 let word = id as usize / 64;
997 if self.dead.len() <= word {
998 self.dead.resize(word + 1, 0);
999 }
1000 self.dead[word] |= 1 << (id % 64);
1001 }
1002
1003 pub fn kind(&self, id: NodeId) -> Kind<'_> {
1007 let kind = self.kind_of(id);
1008 if !self.is_removed(id) {
1009 return kind;
1010 }
1011 match kind {
1012 Kind::Text(_) => Kind::Text(""),
1013 Kind::Comment(_) => Kind::Comment(""),
1014 Kind::Cdata(_) => Kind::Cdata(""),
1015 Kind::ProcessingInstruction { target, .. } => {
1016 Kind::ProcessingInstruction { target, data: "" }
1017 }
1018 other => other,
1019 }
1020 }
1021
1022 fn kind_of(&self, id: NodeId) -> Kind<'_> {
1023 match &self.nodes[id as usize].data {
1024 Data::Document => Kind::Document,
1025 Data::Fragment => Kind::Fragment,
1026 Data::ShadowRoot { init, .. } => Kind::ShadowRoot(*init),
1027 Data::Doctype {
1028 name,
1029 public_id,
1030 system_id,
1031 } => Kind::Doctype {
1032 name: self.str(*name),
1033 public_id: self.str(*public_id),
1034 system_id: self.str(*system_id),
1035 },
1036 Data::Element(e) => Kind::Element {
1037 ns: e.ns,
1038 name: self.element_name(e),
1039 },
1040 Data::Text(s) => Kind::Text(self.str(*s)),
1041 Data::Comment(s) => Kind::Comment(self.str(*s)),
1042 Data::Cdata(s) => Kind::Cdata(self.str(*s)),
1043 Data::ProcessingInstruction { target, data } => Kind::ProcessingInstruction {
1044 target: self.str(*target),
1045 data: self.str(*data),
1046 },
1047 }
1048 }
1049
1050 pub fn attrs(&self, id: NodeId) -> impl Iterator<Item = (AttrNs, &str, &str)> + '_ {
1053 let attrs = if self.is_removed(id) {
1054 &[][..]
1055 } else {
1056 self.attrs_of(id)
1057 };
1058 attrs.iter().map(|a| {
1059 let name = self.str(a.name);
1060 let name = match a.ns {
1061 AttrNs::XLink | AttrNs::Xml | AttrNs::Xmlns => {
1062 name.split_once(':').map_or(name, |(_, local)| local)
1063 }
1064 _ => name,
1065 };
1066 (a.ns, name, self.str(a.value))
1067 })
1068 }
1069
1070 pub fn attrs_written(&self, id: NodeId) -> impl Iterator<Item = (AttrNs, &str, &str)> + '_ {
1073 let ns = self.element(id).map_or(Ns::Html, |e| e.ns);
1074 let attrs = if self.is_removed(id) {
1075 &[][..]
1076 } else {
1077 self.attrs_of(id)
1078 };
1079 attrs
1080 .iter()
1081 .map(move |a| (a.ns, self.written_name(ns, a), self.str(a.value)))
1082 }
1083
1084 pub(crate) fn attrs_of(&self, id: NodeId) -> &[Attr] {
1085 let range = self
1086 .element(id)
1087 .map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
1088 &self.attrs[range]
1089 }
1090
1091 pub(crate) fn written_name(&self, ns: Ns, a: &Attr) -> &str {
1094 let name = self.str(a.name);
1095 match (ns, a.ns) {
1096 (Ns::Svg, AttrNs::None) => crate::tree::svg_attr_name(name).unwrap_or(name),
1097 (Ns::MathMl, AttrNs::None) if name == "definitionurl" => "definitionURL",
1098 _ => name,
1099 }
1100 }
1101
1102 pub fn lower_name(&self, id: NodeId) -> Option<&str> {
1108 if self.is_removed(id) {
1109 return None;
1110 }
1111 let e = self.element(id)?;
1112 Some(match e.name {
1113 Name::Tag => e.tag.name(),
1114 Name::Svg(i) => crate::tree::SVG_TAG_NAMES[i as usize].0,
1115 Name::Span(s) => self.str(s),
1116 })
1117 }
1118
1119 pub fn known_tag(&self, id: NodeId) -> Option<u8> {
1124 if self.is_removed(id) {
1125 return None;
1126 }
1127 self.element(id)
1128 .filter(|e| e.tag != Tag::Other && e.ns != Ns::Xml)
1129 .map(|e| e.tag as u8)
1130 }
1131}
1132
1133#[cfg(test)]
1134mod tests {
1135 use super::{Data, Document, IN_EXTRA, Kind, count_chars};
1136 use crate::{AttrNs, parse};
1137
1138 #[test]
1142 fn foreign_attributes_have_a_lowercase_name_and_a_written_one() {
1143 let doc = parse(
1144 "<svg viewBox=0 xmlns:xlink=x><use xlink:href=#i></use></svg>\
1145 <math definitionURL=d></math>",
1146 false,
1147 );
1148 let svg = (0..doc.len() as u32)
1149 .find(|&n| doc.lower_name(n) == Some("svg"))
1150 .unwrap();
1151 let use_ = doc.first_child(svg).unwrap();
1152 let math = doc.next_sibling(svg).unwrap();
1153 let names = |n, written: bool| -> Vec<String> {
1154 if written {
1155 doc.attrs_written(n)
1156 .map(|(_, a, _)| a.to_string())
1157 .collect()
1158 } else {
1159 doc.attrs(n).map(|(_, a, _)| a.to_string()).collect()
1160 }
1161 };
1162 assert_eq!(names(svg, false), ["viewbox", "xlink"]);
1163 assert_eq!(names(svg, true), ["viewBox", "xmlns:xlink"]);
1164 assert_eq!(names(use_, false), ["href"]);
1165 assert_eq!(doc.attrs(use_).next().unwrap().0, AttrNs::XLink);
1166 assert_eq!(names(use_, true), ["xlink:href"]);
1167 assert_eq!(names(math, false), ["definitionurl"]);
1168 assert_eq!(names(math, true), ["definitionURL"]);
1169 assert!(doc.outer_html(svg).starts_with(r#"<svg viewBox="0""#));
1170 assert!(doc.outer_html(math).contains("definitionURL"));
1171 }
1172
1173 #[test]
1177 fn line_col_agrees_with_counting_and_costs_little_a_call() {
1178 let input = "\u{FEFF}<p>a\r\nb\rc\n\u{e9}\u{20ac}\u{1F600}</p>".repeat(300)
1180 + &"\u{e9}".repeat(5_000)
1181 + "\n"
1182 + &"x".repeat(4_096 * 2 - 1);
1183 let doc = crate::parse_with(
1184 &input,
1185 crate::Options {
1186 spans: true,
1187 ..crate::Options::default()
1188 },
1189 )
1190 .unwrap();
1191 let slow = |offset: usize| {
1193 let p = doc.positions.as_deref().unwrap();
1194 let o = offset.saturating_sub(p.skipped as usize);
1195 let lo = (0..p.crlf.len())
1196 .take_while(|&k| p.crlf[k] as usize + k + 1 < o)
1197 .count();
1198 let bytes = &doc.src.as_bytes()[..(o - lo.min(o)).min(doc.src.len())];
1199 let start = memchr::memrchr(b'\n', bytes).map_or(0, |i| i + 1);
1200 (
1201 1 + memchr::memchr_iter(b'\n', bytes).count(),
1202 1 + count_chars(&bytes[start..]),
1203 )
1204 };
1205 for at in 0..=input.len() + 2 {
1206 assert_eq!(doc.line_col(at), slow(at), "at {at}");
1207 }
1208
1209 let calls = |lines: usize| {
1212 let page = parse(&"x\n".repeat(lines), false);
1213 let start = std::time::Instant::now();
1214 for i in lines - 10_000..lines {
1215 assert_eq!(page.line_col(i * 2), (i + 1, 1));
1216 }
1217 start.elapsed()
1218 };
1219 let rounds: Vec<_> = (0..5).map(|_| (calls(250_000), calls(2_000_000))).collect();
1220 assert!(
1221 rounds
1222 .iter()
1223 .any(|&(a, b)| b < a * 3 + std::time::Duration::from_millis(20)),
1224 "{rounds:?}"
1225 );
1226 }
1227
1228 #[test]
1229 fn an_edit_finds_a_foreign_attribute_by_its_written_name() {
1230 let mut doc = parse("<svg viewBox=0></svg>", false);
1231 let svg = (0..doc.len() as u32)
1232 .find(|&n| doc.lower_name(n) == Some("svg"))
1233 .unwrap();
1234 doc.set_attr(svg, "viewBox", "1").unwrap();
1235 assert_eq!(doc.outer_html(svg), r#"<svg viewBox="1"></svg>"#);
1236 assert!(doc.remove_attr(svg, "viewBox"));
1237 assert_eq!(doc.outer_html(svg), "<svg></svg>");
1238 }
1239
1240 #[test]
1244 fn strings_past_two_to_the_thirty_bytes_of_buffer_read_back() {
1245 let mut doc = Document::empty();
1246 doc.buf = "x".repeat(IN_EXTRA as usize - 4);
1247 let near = doc.push_str("abcdefgh");
1248 let past = doc.push_str("ijkl");
1249 assert_eq!(doc.str(near), "abcdefgh");
1250 assert_eq!(doc.str(past), "ijkl");
1251 assert!(doc.buf.len() < IN_EXTRA as usize);
1252 doc.buf.truncate(IN_EXTRA as usize - 4);
1255 let at = doc.push_str("ab");
1256 let text = doc.add(Data::Text(at));
1257 doc.append_text(text, "cdef");
1258 assert!(matches!(doc.kind(text), Kind::Text("abcdef")));
1259 assert!(doc.buf.len() < IN_EXTRA as usize);
1260 }
1261}