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.
55/// The parse buffer, which holds the strings the parser had to change,
56/// can outgrow the input (each NUL it replaces is three bytes of U+FFFD),
57/// so a string that would take it past 30 bits goes in a string of its
58/// own instead.
59pub 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    /// The tag's own lowercase name.
70    Tag,
71    /// An SVG name the parser fixed the case of, such as `clipPath`: its
72    /// index in the table of them.
73    Svg(u8),
74    /// Any other name, in the document's buffer.
75    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    /// A template's contents, a fragment node of its own.
92    pub contents: NodeId,
93    /// A MathML annotation-xml whose encoding makes it an HTML integration
94    /// point.
95    pub html_integration: bool,
96}
97
98/// Whether a shadow root's host lets scripts reach it, from
99/// `shadowrootmode` or `attachShadow`'s `mode`.
100#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101pub enum ShadowRootMode {
102    Open,
103    Closed,
104}
105
106/// How a shadow root's slots get their nodes: by the `slot` attribute of
107/// the host's children, or only as [`Document::assign`] says.
108#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
109pub enum SlotAssignment {
110    #[default]
111    Named,
112    Manual,
113}
114
115/// A shadow root's settings, as `attachShadow` takes them and a
116/// declarative `<template shadowrootmode>` sets them.
117#[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    /// Made by the parser from a `<template shadowrootmode>`.
125    pub declarative: bool,
126}
127
128impl ShadowRoot {
129    /// An open root, with every flag off and named slot assignment.
130    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    /// A closed root, otherwise as [`ShadowRoot::open`].
142    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    /// A shadow root: like a fragment, nobody's child, with a link back to
155    /// its host, which [`Document::shadow_root`] gives from the host.
156    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    /// An XML CDATA section.
173    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
186/// A parsed HTML document, or a fragment.
187pub struct Document {
188    pub(crate) nodes: Vec<Node>,
189    /// The input, after preprocessing. Text and attribute values that
190    /// didn't need changing point into it rather than being copied.
191    pub(crate) src: String,
192    pub(crate) buf: String,
193    /// Strings with an allocation each: what edits add, and text the
194    /// parser had to keep growing away from the end of `buf`. Only the
195    /// parse grows one, so once it's done none moves, and an edit never
196    /// moves a string already handed out, as growing `buf` would.
197    pub(crate) extras: Vec<String>,
198    pub(crate) attrs: Vec<Attr>,
199    pub(crate) quirks: Quirks,
200    /// Whether it was parsed with scripting on, which decides how a
201    /// noscript element's text serializes.
202    pub(crate) scripting: bool,
203    /// Where each node and attribute was written, when the parse was
204    /// asked to keep that, and how to map offsets back to the input, for
205    /// spans or errors.
206    pub(crate) positions: Option<Box<Positions>>,
207    /// Each template's contents, mapped to the template: no link leads
208    /// back from the contents, and an edit's cycle check has to climb out
209    /// of them. Edits build it the first time they need it.
210    pub(crate) hosts: Option<std::collections::HashMap<NodeId, NodeId>>,
211    /// Each shadow host's shadow root. Empty, and so free, for a page
212    /// without any.
213    pub(crate) shadow_roots: std::collections::HashMap<NodeId, NodeId>,
214    /// Each slot's manually assigned nodes, for a shadow root with
215    /// [`SlotAssignment::Manual`].
216    pub(crate) manual_slots: std::collections::HashMap<NodeId, Vec<NodeId>>,
217    /// The parse errors, when the parse was asked to collect them.
218    pub(crate) errors: Vec<crate::SyntaxError>,
219    /// A bit per node taken out with [`Document::remove`]. A slot is never
220    /// reused, so a removed id stays removed. Empty until a remove.
221    pub(crate) dead: Vec<u64>,
222    /// For [`Document::line_col`], made the first time it's asked.
223    lines: std::sync::OnceLock<Lines>,
224}
225
226/// Where each line of the source starts, and how many characters come
227/// before every [`Lines::BLOCK`] bytes, so a line and column take a search
228/// and a count of at most a block, not a pass over the source.
229struct 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        // For the end of a source that fills its last block.
247        chars.push(before);
248        Lines { starts, chars }
249    }
250
251    /// How many characters come before byte `at`.
252    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
258/// Characters in UTF-8 `bytes`: every byte but a continuation byte starts
259/// one.
260fn count_chars(bytes: &[u8]) -> usize {
261    bytes.iter().filter(|&&b| (b as i8) >= -0x40).count()
262}
263
264/// A node or attribute with no recorded position.
265const UNKNOWN: [u32; 2] = [u32::MAX; 2];
266
267/// Where nodes and attributes were written, as `[start, end)` offsets
268/// into the preprocessed source; the original input differs only by the
269/// CRs that preprocessing dropped and a dropped byte order mark, so these
270/// two are kept to map back.
271#[derive(Debug, Default)]
272pub(crate) struct Positions {
273    /// By node id: an element's start tag, or the whole of anything else.
274    pub nodes: Vec<[u32; 2]>,
275    /// By node id: an element's end tag.
276    pub ends: Vec<[u32; 2]>,
277    /// By index into [`Document::attrs`].
278    pub attrs: Vec<[u32; 2]>,
279    /// Where the preprocessed source has an LF that was a CRLF, ascending.
280    pub crlf: Vec<u32>,
281    /// Bytes before the source in the original: a byte order mark.
282    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    /// An offset in the preprocessed source, as one in the original.
298    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/// What a node is, as [`Document::kind`] reports it.
309#[derive(Debug, PartialEq, Eq)]
310pub enum Kind<'a> {
311    Document,
312    Fragment,
313    /// A shadow root: [`Document::shadow_host`] is its host.
314    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        // Enough for a dense page, a table cell every dozen bytes: growing
336        // a big page's nodes copies them, briefly holding both. Space never
337        // used is never touched, so it costs no memory.
338        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    /// An empty document to build into, as XML is: no source, no nodes
366    /// but the document itself.
367    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    /// A span for a string an edit adds. Unlike the parser's strings, it
398    /// never moves, so a `&str` read before the edit stays good.
399    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    /// Where `s` is in the source, if it's a slice of it.
406    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    /// A span for `s`: into the source when it's a slice of it, which
413    /// costs nothing, else a copy in the buffer.
414    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        // Past this, an offset would read as one of the flags.
426        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    /// Where a node was written, as a byte range of the input the parse
451    /// was given: an element's start tag from `<` to `>`, or the whole of
452    /// a text node, comment, doctype or processing instruction. A text
453    /// node made of several runs (text, then a character reference, then
454    /// text again, or text foster-parented out of a table) spans the first
455    /// run's start to the last one's end.
456    ///
457    /// `None` for a node the parser made up rather than read (an implied
458    /// `<html>`, `<head>`, `<body>` or `<tbody>`, a formatting element it
459    /// reopened, a copy the adoption agency made), for one an edit made,
460    /// and for every node unless the document was parsed with
461    /// [`Options::spans`](crate::Options::spans) on.
462    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    /// Where an element's end tag was written, when it had one: the end
471    /// tag whose handling closed it, `</p>` for a `<p>`, or a `</body>`.
472    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    /// Where an element's `i`th attribute, as [`Document::attrs`] lists
481    /// them, was written: from its name's first byte to the end of its
482    /// value, past a closing quote, or to the end of its name when it has
483    /// no value. An attribute an edit set has none; a reopened formatting
484    /// element's are where the original's were written.
485    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    /// The line and column of a byte offset into the input the parse was
499    /// given, as an editor shows them: both start at 1, a line ends at an
500    /// LF, a CRLF or a lone CR, and the column counts characters (Unicode
501    /// scalar values), not bytes. The first call indexes the source's
502    /// lines, a pass over it; each after costs a search and a count of a
503    /// few kilobytes, however long the line.
504    pub fn line_col(&self, offset: usize) -> (usize, usize) {
505        // Back into the preprocessed source, where every line ends at an
506        // LF: past the skipped bytes and the CRs that were dropped.
507        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        // The CRLFs wholly before `o`: the `i`th one's CR is at `lf + i`
513        // in the original, where `lf` is its LF's place in the source.
514        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    /// The parse errors in the input, in source order: empty unless the
533    /// document was parsed with [`Options::errors`](crate::Options::errors)
534    /// on.
535    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    /// Inserts `child`, which has no parent, into `parent` before `before`,
555    /// or last when `before` is [`NONE`].
556    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    /// Takes `child` out of the tree, still usable: insert it again to move
607    /// it, subtree and all. To be done with a node for good, use
608    /// [`Document::remove`], after which its id reads as nothing.
609    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    /// Whether `id`'s links and its neighbours' agree: its siblings point
642    /// back at it, and its parent's first and last child are it exactly
643    /// when it has no sibling on that side. Constant time, for the debug
644    /// assertions on every insert and removal; [`Document::check_tree`]
645    /// checks every node.
646    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    /// Appends text to a text node, copying its old text to the end of the
668    /// buffer first if something else has been written after it.
669    /// Only the parser calls this: it may move the buffer.
670    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                // The next slice of the source: the span just grows.
679                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                // Already a string of its own: grows in place.
695                self.extras[(span.start & !IN_EXTRA) as usize].push_str(text);
696                span
697            } else {
698                // Something was written after it: move it to a string of its
699                // own, once, rather than copying it to the end of the buffer on
700                // every append (repeated <body x> made that quadratic).
701                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    /// Checks every invariant of the tree, panicking at the first that
711    /// doesn't hold: every node's links agree with its parent's and its
712    /// siblings', only elements, documents and fragments have children,
713    /// each node is reached from the root at most once (template contents
714    /// included), each template's contents are a fragment of its own
715    /// that's nobody's child, the map of hosts agrees with the templates,
716    /// and every string and recorded position is inside its buffer.
717    ///
718    /// Linear in the document's size, so it's for tests and fuzzing, not
719    /// for every edit; the parser and the edits assert the parts of this
720    /// they touch as they go. Only in builds with debug assertions.
721    #[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        // Down from the root, each node once: no cycle, no node in two
875        // places. Siblings are walked by their links, so a loop among
876        // them shows as a node seen twice.
877        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    /// A template element's contents.
977    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    /// Whether `id` was taken out with [`Document::remove`], or was inside
985    /// a node that was. A removed node reads as nothing: the readers that
986    /// return an `Option` give `None`, it has no children, attributes or
987    /// text, it serializes to `""`, it matches no selector, and inserting
988    /// it, or anything into it, is an error.
989    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    /// What `id` is. A removed node keeps its kind and an element its
1004    /// name, but its text, a comment's, and a processing instruction's
1005    /// data read as empty, as it has no children or attributes.
1006    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    /// An element's attributes, in source order, as (namespace, local name,
1051    /// value).
1052    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    /// An element's attributes with their names as written: `xlink:href`
1071    /// rather than `href`, and an XML attribute's prefix kept.
1072    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    /// An attribute's name as the spec writes it on an element in `ns`:
1092    /// SVG's `viewBox` and MathML's `definitionURL` get their case back.
1093    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    /// An element's name lowercased, without allocating: SVG's
1103    /// `foreignObject` gives `foreignobject`, whether it was parsed or made
1104    /// with [`Document::create_element`]. An XML element's name as written,
1105    /// and so is a foreign element made under a name in another case
1106    /// (`LINEARGRADIENT`), which the DOM treats as a different element.
1107    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    /// The parser's number for an element's tag, from its lowercase name:
1120    /// what [`crate::tag_number`] gives for that name. HTML, SVG and MathML
1121    /// elements alike get one, so an SVG `<title>` shares HTML `title`'s;
1122    /// an XML element never does.
1123    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    /// Names as tokenized, lowercase and without a prefix, from attrs();
1139    /// as the spec writes them, case fixed and prefix kept, from
1140    /// attrs_written() and the serializer.
1141    #[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    /// line_col counted the source up to the offset on every call, so a
1174    /// line and column for each of a big page's nodes cost the square of
1175    /// its size.
1176    #[test]
1177    fn line_col_agrees_with_counting_and_costs_little_a_call() {
1178        // Every line end, multibyte characters, and lines across blocks.
1179        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        // As it was worked out before: a count over the source each time.
1192        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        // The same calls, near the end of a page eight times longer, take
1210        // about as long.
1211        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    /// The parse buffer can grow past the input (a NUL becomes three
1241    /// bytes of U+FFFD), and an offset past 2^30 read as a flag: a string
1242    /// written there came back as another one, or panicked.
1243    #[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        // A text node at the end of the buffer grows into a string of its
1253        // own rather than past the limit.
1254        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}