Skip to main content

parsec/
dom.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! The parsed document: every node in one `Vec`, linked by index, and every
5//! string in one buffer, so building it allocates a handful of times rather
6//! than once per node, and dropping it frees a handful of blocks.
7
8use crate::tags::Tag;
9
10/// A node's index in its document; the document itself is node 0.
11pub type NodeId = u32;
12
13/// No node, in the links.
14pub(crate) const NONE: NodeId = NodeId::MAX;
15
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub enum Ns {
18    Html,
19    Svg,
20    MathMl,
21    /// An element of an XML document: its name is the qualified name as
22    /// written, and its namespace is the host's to keep.
23    Xml,
24}
25
26/// A namespaced attribute's namespace, from the spec's "adjust foreign
27/// attributes" table; `None` for every ordinary attribute.
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29pub enum AttrNs {
30    None,
31    XLink,
32    Xml,
33    Xmlns,
34    /// An XML attribute in a namespace the host numbered; its name is the
35    /// qualified name as written.
36    Host(u32),
37}
38
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub enum Quirks {
41    No,
42    Limited,
43    Quirks,
44}
45
46/// A span's high bit says it's in the document's copy of its source, not
47/// in the buffer of strings the parser had to make.
48const IN_SOURCE: u32 = 1 << 31;
49
50/// A span with this bit (and not IN_SOURCE) is a string an edit added:
51/// `start` is its index in `extras`.
52const IN_EXTRA: u32 = 1 << 30;
53
54/// The most input a document can hold. Spans keep offsets in 30 bits, and
55/// the parse buffer, which only holds copies of what the input says, stays
56/// well under that.
57pub 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    /// The tag's own lowercase name.
68    Tag,
69    /// An SVG name the parser fixed the case of, such as `clipPath`: its
70    /// index in the table of them.
71    Svg(u8),
72    /// Any other name, in the document's buffer.
73    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    /// A template's contents, a fragment node of its own.
90    pub contents: NodeId,
91    /// A MathML annotation-xml whose encoding makes it an HTML integration
92    /// point.
93    pub html_integration: bool,
94}
95
96/// Whether a shadow root's host lets scripts reach it, from
97/// `shadowrootmode` or `attachShadow`'s `mode`.
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
99pub enum ShadowRootMode {
100    Open,
101    Closed,
102}
103
104/// How a shadow root's slots get their nodes: by the `slot` attribute of
105/// the host's children, or only as [`Document::assign`] says.
106#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
107pub enum SlotAssignment {
108    #[default]
109    Named,
110    Manual,
111}
112
113/// A shadow root's settings, as `attachShadow` takes them and a
114/// declarative `<template shadowrootmode>` sets them.
115#[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    /// Made by the parser from a `<template shadowrootmode>`.
123    pub declarative: bool,
124}
125
126impl ShadowRoot {
127    /// An open root, with every flag off and named slot assignment.
128    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    /// A closed root, otherwise as [`ShadowRoot::open`].
140    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    /// A shadow root: like a fragment, nobody's child, with a link back to
153    /// its host, which [`Document::shadow_root`] gives from the host.
154    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    /// An XML CDATA section.
171    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
184/// A parsed HTML document, or a fragment.
185pub struct Document {
186    pub(crate) nodes: Vec<Node>,
187    /// The input, after preprocessing. Text and attribute values that
188    /// didn't need changing point into it rather than being copied.
189    pub(crate) src: String,
190    pub(crate) buf: String,
191    /// Strings with an allocation each: what edits add, and text the
192    /// parser had to keep growing away from the end of `buf`. Only the
193    /// parse grows one, so once it's done none moves, and an edit never
194    /// moves a string already handed out, as growing `buf` would.
195    pub(crate) extras: Vec<String>,
196    pub(crate) attrs: Vec<Attr>,
197    pub(crate) quirks: Quirks,
198    /// Whether it was parsed with scripting on, which decides how a
199    /// noscript element's text serializes.
200    pub(crate) scripting: bool,
201    /// Where each node and attribute was written, when the parse was
202    /// asked to keep that, and how to map offsets back to the input, for
203    /// spans or errors.
204    pub(crate) positions: Option<Box<Positions>>,
205    /// Each template's contents, mapped to the template: no link leads
206    /// back from the contents, and an edit's cycle check has to climb out
207    /// of them. Edits build it the first time they need it.
208    pub(crate) hosts: Option<std::collections::HashMap<NodeId, NodeId>>,
209    /// Each shadow host's shadow root. Empty, and so free, for a page
210    /// without any.
211    pub(crate) shadow_roots: std::collections::HashMap<NodeId, NodeId>,
212    /// Each slot's manually assigned nodes, for a shadow root with
213    /// [`SlotAssignment::Manual`].
214    pub(crate) manual_slots: std::collections::HashMap<NodeId, Vec<NodeId>>,
215    /// The parse errors, when the parse was asked to collect them.
216    pub(crate) errors: Vec<crate::SyntaxError>,
217    /// A bit per node taken out with [`Document::remove`]. A slot is never
218    /// reused, so a removed id stays removed. Empty until a remove.
219    pub(crate) dead: Vec<u64>,
220}
221
222/// A node or attribute with no recorded position.
223const UNKNOWN: [u32; 2] = [u32::MAX; 2];
224
225/// Where nodes and attributes were written, as `[start, end)` offsets
226/// into the preprocessed source; the original input differs only by the
227/// CRs that preprocessing dropped and a dropped byte order mark, so these
228/// two are kept to map back.
229#[derive(Debug, Default)]
230pub(crate) struct Positions {
231    /// By node id: an element's start tag, or the whole of anything else.
232    pub nodes: Vec<[u32; 2]>,
233    /// By node id: an element's end tag.
234    pub ends: Vec<[u32; 2]>,
235    /// By index into [`Document::attrs`].
236    pub attrs: Vec<[u32; 2]>,
237    /// Where the preprocessed source has an LF that was a CRLF, ascending.
238    pub crlf: Vec<u32>,
239    /// Bytes before the source in the original: a byte order mark.
240    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    /// An offset in the preprocessed source, as one in the original.
256    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/// What a node is, as [`Document::kind`] reports it.
267#[derive(Debug, PartialEq, Eq)]
268pub enum Kind<'a> {
269    Document,
270    Fragment,
271    /// A shadow root: [`Document::shadow_host`] is its host.
272    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        // Enough for a dense page, a table cell every dozen bytes: growing
294        // a big page's nodes copies them, briefly holding both. Space never
295        // used is never touched, so it costs no memory.
296        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    /// An empty document to build into, as XML is: no source, no nodes
323    /// but the document itself.
324    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    /// A span for a string an edit adds. Unlike the parser's strings, it
355    /// never moves, so a `&str` read before the edit stays good.
356    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    /// Where `s` is in the source, if it's a slice of it.
363    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    /// A span for `s`: into the source when it's a slice of it, which
370    /// costs nothing, else a copy in the buffer.
371    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        // Past this, an offset would read as one of the flags.
385        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    /// Where a node was written, as a byte range of the input the parse
406    /// was given: an element's start tag from `<` to `>`, or the whole of
407    /// a text node, comment, doctype or processing instruction. A text
408    /// node made of several runs (text, then a character reference, then
409    /// text again, or text foster-parented out of a table) spans the first
410    /// run's start to the last one's end.
411    ///
412    /// `None` for a node the parser made up rather than read (an implied
413    /// `<html>`, `<head>`, `<body>` or `<tbody>`, a formatting element it
414    /// reopened, a copy the adoption agency made), for one an edit made,
415    /// and for every node unless the document was parsed with
416    /// [`Options::spans`](crate::Options::spans) on.
417    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    /// Where an element's end tag was written, when it had one: the end
426    /// tag whose handling closed it, `</p>` for a `<p>`, or a `</body>`.
427    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    /// Where an element's `i`th attribute, as [`Document::attrs`] lists
436    /// them, was written: from its name's first byte to the end of its
437    /// value, past a closing quote, or to the end of its name when it has
438    /// no value. An attribute an edit set has none; a reopened formatting
439    /// element's are where the original's were written.
440    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    /// The line and column of a byte offset into the input the parse was
454    /// given, as an editor shows them: both start at 1, a line ends at an
455    /// LF, a CRLF or a lone CR, and the column counts characters (Unicode
456    /// scalar values), not bytes. Worked out from the source each time,
457    /// so it costs a pass over the text before `offset`.
458    pub fn line_col(&self, offset: usize) -> (usize, usize) {
459        // Back into the preprocessed source, where every line ends at an
460        // LF: past the skipped bytes and the CRs that were dropped.
461        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        // The CRLFs wholly before `o`: the `i`th one's CR is at `lf + i`
467        // in the original, where `lf` is its LF's place in the source.
468        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        // Every byte but a UTF-8 continuation byte starts a character.
482        let column = 1 + bytes[start..]
483            .iter()
484            .filter(|&&b| (b as i8) >= -0x40)
485            .count();
486        (line, column)
487    }
488
489    /// The parse errors in the input, in source order: empty unless the
490    /// document was parsed with [`Options::errors`](crate::Options::errors)
491    /// on.
492    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    /// Inserts `child`, which has no parent, into `parent` before `before`,
512    /// or last when `before` is [`NONE`].
513    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    /// Takes `child` out of the tree, still usable: insert it again to move
564    /// it, subtree and all. To be done with a node for good, use
565    /// [`Document::remove`], after which its id reads as nothing.
566    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    /// Whether `id`'s links and its neighbours' agree: its siblings point
599    /// back at it, and its parent's first and last child are it exactly
600    /// when it has no sibling on that side. Constant time, for the debug
601    /// assertions on every insert and removal; [`Document::check_tree`]
602    /// checks every node.
603    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    /// Appends text to a text node, copying its old text to the end of the
625    /// buffer first if something else has been written after it.
626    /// Only the parser calls this: it may move the buffer.
627    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                // The next slice of the source: the span just grows.
636                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                // Already a string of its own: grows in place.
649                self.extras[(span.start & !IN_EXTRA) as usize].push_str(text);
650                span
651            } else {
652                // Something was written after it: move it to a string of its
653                // own, once, rather than copying it to the end of the buffer on
654                // every append (repeated <body x> made that quadratic).
655                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    /// Checks every invariant of the tree, panicking at the first that
665    /// doesn't hold: every node's links agree with its parent's and its
666    /// siblings', only elements, documents and fragments have children,
667    /// each node is reached from the root at most once (template contents
668    /// included), each template's contents are a fragment of its own
669    /// that's nobody's child, the map of hosts agrees with the templates,
670    /// and every string and recorded position is inside its buffer.
671    ///
672    /// Linear in the document's size, so it's for tests and fuzzing, not
673    /// for every edit; the parser and the edits assert the parts of this
674    /// they touch as they go. Only in builds with debug assertions.
675    #[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        // Down from the root, each node once: no cycle, no node in two
829        // places. Siblings are walked by their links, so a loop among
830        // them shows as a node seen twice.
831        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    /// A template element's contents.
931    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    /// Whether `id` was taken out with [`Document::remove`], or was inside
939    /// a node that was. A removed node reads as nothing: the readers that
940    /// return an `Option` give `None`, it has no children, attributes or
941    /// text, it serializes to `""`, it matches no selector, and inserting
942    /// it, or anything into it, is an error.
943    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    /// What `id` is. A removed node keeps its kind and an element its
958    /// name, but its text, a comment's, and a processing instruction's
959    /// data read as empty, as it has no children or attributes.
960    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    /// An element's attributes, in source order, as (namespace, local name,
1005    /// value).
1006    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    /// An element's attributes with their names as written: `xlink:href`
1025    /// rather than `href`, and an XML attribute's prefix kept.
1026    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    /// An attribute's name as the spec writes it on an element in `ns`:
1046    /// SVG's `viewBox` and MathML's `definitionURL` get their case back.
1047    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    /// An element's name lowercased, without allocating: SVG's
1057    /// `foreignObject` gives `foreignobject`, whether it was parsed or made
1058    /// with [`Document::create_element`]. An XML element's name as written,
1059    /// and so is a foreign element made under a name in another case
1060    /// (`LINEARGRADIENT`), which the DOM treats as a different element.
1061    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    /// The parser's number for an element's tag, from its lowercase name:
1074    /// what [`crate::tag_number`] gives for that name. HTML, SVG and MathML
1075    /// elements alike get one, so an SVG `<title>` shares HTML `title`'s;
1076    /// an XML element never does.
1077    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    /// Names as tokenized, lowercase and without a prefix, from attrs();
1092    /// as the spec writes them, case fixed and prefix kept, from
1093    /// attrs_written() and the serializer.
1094    #[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}