Skip to main content

oneyaml_syntax/tree/
mod.rs

1//! The lossless syntax tree.
2//!
3//! [`SyntaxTree`] turns the lossless event stream into a tree that keeps
4//! every byte of the input: parse → [`SyntaxTree::emit`] of an untouched
5//! tree reproduces the input byte for byte. It is what `Document`, the edit
6//! layer, comment attachment, and tooling build on.
7//!
8//! # Shape
9//!
10//! Elements are **nodes** (documents, collections, scalars, aliases, error
11//! regions) and **tokens** (every byte: scalar text, indicators, brackets,
12//! properties, white space, comments, …); see [`SyntaxKind`]. The tree
13//! mirrors the event stream: a node per `…Start`/`…End` pair,
14//! scalar, alias, and `Error` event, a token per event that covers bytes.
15//! Two placements differ from the stream, both so that a node owns what
16//! belongs to it:
17//!
18//! * a node's **properties** (`&a`, `!t`) and a block scalar's **header**,
19//!   with the trivia between them, are children of that node (the stream
20//!   emits them before the node's event, C3/C5);
21//! * a document's **directives** are children of that document.
22//!
23//! Collections are flat: a mapping's children are its keys and values
24//! (nodes) interleaved with `?`/`:`/`,` indicators and trivia, in source
25//! order. Because the stream places every zero-width start and end "hugging
26//! the content" (C4), no node begins or ends with white space, a line
27//! break, or a comment: trivia always lies *between* nodes, at the
28//! outermost level it can, which is what the comment attachment rules
29//! decide over.
30//!
31//! **Errors (C6).** Every `Error` event becomes an
32//! [`SyntaxKind::Error`] node holding the offending bytes; the lines skipped
33//! while resynchronising follow it as [`SyntaxKind::Skipped`] tokens; the
34//! repairs the parser synthesised (empty scalars, zero-width ends) are
35//! ordinary nodes. Diagnostics are kept ([`SyntaxTree::diagnostics`],
36//! [`Node::diagnostic`]).
37//!
38//! # Representation
39//!
40//! Our own arena, not `rowan`: the elements are stored **flat, in preorder**
41//! (which is also source order), as parallel arrays of 9 bytes per element:
42//!
43//! * `kind`: one byte;
44//! * `parent`: the parent's index (`u32`);
45//! * `word` (`u32`): for a **token**, its start offset; for a **node**, the
46//!   index one past its last descendant, so a subtree is the contiguous
47//!   index range `index..word`.
48//!
49//! Nothing else is stored per element. Because tokens tile the source in
50//! preorder (event contract C1), a token ends where the next token starts,
51//! and a node spans from its first token to the end of its last one; a
52//! zero-width node sits where the next element starts. First child, next
53//! sibling, subtree skipping, and emitting are O(1) per step; spans are
54//! O(1) except across a run of nodes that open at the same byte (bounded by
55//! the grammar, in practice at most 4). Offsets beyond 4 GiB are carried by
56//! a sparse list of the indices where a token's start crosses a multiple
57//! of 2³² (empty for smaller inputs), so no input is out of range; the index
58//! space holds up to about 4 billion elements, after which the rest of the
59//! input becomes one [`SyntaxKind::Skipped`] token under an error node (the
60//! tree still round-trips).
61//!
62//! What the tokens cannot say is kept sparsely: a block scalar's header
63//! (chomping, detected indentation) and a tag's `%TAG` prefix, both exactly
64//! as the event carried them; and the diagnostics. Scalar values, anchors,
65//! and tags are read with the **same** readers the event stream uses,
66//! e.g. [`Node::value`].
67//!
68//! # Handles
69//!
70//! [`Node`] is a borrowed view, cheap to copy. [`NodeId`] is a stable,
71//! owned handle: element index, generation, and the issuing tree's stamp.
72//! [`SyntaxTree::get`] returns [`StaleNode`] for a handle issued by another
73//! tree (every tree, including a clone, has its own stamp) or whose
74//! generation no longer matches its slot. A freshly built tree has every
75//! slot at generation 0 and stores no generations at all. Edits never
76//! reuse a slot: a removed or replaced element's handle stays stale, an
77//! inserted element gets a new slot, and every other handle keeps
78//! resolving to its element.
79//!
80//! **Forks**: [`SyntaxTree::fork`] copies a tree
81//! *with* its handle identity. The fork gets a stamp of its own and
82//! records its parent's stamp with the parent's next free slot; a slot
83//! below that limit is named by the parent's stamp (or, below an earlier
84//! limit, by an earlier ancestor's) in both trees, so a handle issued
85//! before the fork resolves in both, to the same element, until a copy
86//! removes it. Slots at or past the limit are allocated by each copy on
87//! its own and named by that copy's stamp, so a handle issued after the
88//! fork is stale in the other copy (never a wrong element). No per-copy
89//! translation map exists: a chain of forks keeps one `(stamp, limit)`
90//! pair per fork made after insertions whose range still holds a live
91//! slot (dead ranges are dropped at the next fork), and
92//! resolving is O(log) in their number.
93//!
94//! # Editing
95//!
96//! [`SyntaxTree::replace`], [`SyntaxTree::remove`],
97//! [`SyntaxTree::insert_before`], [`SyntaxTree::insert_after`],
98//! [`SyntaxTree::append_child`] (and their range forms) splice detached
99//! [`Fragment`]s in and out;
100//! [`SyntaxTree::replace_token`] rewrites one token;
101//! [`SyntaxTree::replace_to_line_end`] and [`SyntaxTree::insert_line_after`]
102//! edit through a line's end, placing its line break where the parser does
103//! (a block scalar's text ends with its line break, other content's break
104//! is a token at the outermost level that continues).
105//! Fragments come from
106//! text through the one parser ([`Fragment::parse_with`], or
107//! [`SyntaxTree::parse_with`] then [`SyntaxTree::extract`]). An
108//! edit never changes the parsed arrays: the first one adds a sparse
109//! overlay, and each costs O(depth + log R + window) for R runs (a few per
110//! edit), never O(document) below document level; reads stay local (see
111//! `edit.rs`). An edited tree emits exactly the string splice of its edits.
112//! Every edit returns `Result` and a refused edit changes nothing.
113//!
114//! **Reads of an edited tree**. A [`Node`] of an edited
115//! tree carries the run it lies in, so sequential reads (iterating
116//! children, descendants, a walk, kinds, token texts, [`SyntaxTree::emit`])
117//! cost amortised O(1) per element, as in a parsed tree: a step inside a
118//! run is the parsed arrays' arithmetic, and moving to the next run is one
119//! treap step. Only a step that leaves a run reads the overlay's maps
120//! (O(log R)), so a full read takes O(R) such lookups, whatever the size
121//! of the document, and emit takes none (O(1) per run, and R is at most the
122//! number of elements: O(n)). Random access (a span, a rank, a handle)
123//! stays O(log R).
124//!
125//! # Well-formed edits
126//!
127//! An edited tree always agrees with its own text: the edit layer accepts
128//! only **well-formed** edits and refuses the others with
129//! [`TreeEditError::NotWellFormed`] (or [`TreeEditError::Limit`]). An
130//! edit is well-formed when its **validation window**, read again through
131//! the one parser under the tree's own [`SyntaxTree::settings`] **in the
132//! window's real context**, reads as exactly the window's elements after
133//! the edit: the same kinds, nesting, token texts, block scalar headers,
134//! resolved tags, error nodes, and diagnostics (spans moved by the
135//! window's offset). So the edited tree's error set equals its re-parse's;
136//! an edit may sit next to an error region, but never changes how it
137//! reads, and never removes or replaces an [`SyntaxKind::Error`] node
138//! below document level (refused as `ReadOnly`). An accepted
139//! edit inside a document thus keeps [`SyntaxTree::error_count`]. The
140//! window is found from the edit's parent, going up past
141//! scalars, aliases, error nodes, flow pairs, and documents to the nearest
142//! **container**; a flow collection inside an implicit key (block or
143//! flow) is replaced by the outermost such key, read in its mapping.
144//!
145//! **Recovered input** (the edited tree agrees with its
146//! re-parse whole, diagnostics' labels and fixes included, with or
147//! without errors; known exception: under `lenient_inline_colons`, a
148//! document holding a failed directive block whose content ends in a
149//! `Y0028` warning, see `compare_trees`). An error region reads as its document before it left
150//! the parser (C6), what follows it may end it (a flow collection or quote
151//! cut off by a marker), and its diagnostics have labels and fixes away
152//! from their element (an unclosed `[`; a byte order mark that ended a
153//! document is reported over the line it starts). A stream child is
154//! **recovered** when it is an error node, or a document with an error in
155//! its content (directive errors do not count). An edit that could change
156//! how one reads, or move one of its labels, is refused with
157//! [`TreeEditError::ReadOnly`] `{ kind: Error }`; accepted are:
158//!
159//! * in a recovered document, an edit whose block or flow window ends
160//!   before every error of the document and every label and fix of them
161//!   (at the element it peeks, or at its own end when it reads to its
162//!   collection's end), and, for a flow window, outside any flow
163//!   collection used as an implicit key the edit could change: none of the
164//!   flow collections it lies in sits in a key's place (decided within
165//!   `TRIVIA_WALK` trivia siblings, else taken as one), nor is followed by
166//!   `:` on its line unless it spans lines both before and after the edit
167//!   (an invalid key either way): the document is text without errors up
168//!   to there, the window decides it as in a tree without errors, and the
169//!   parser goes on from there as before the edit;
170//! * next to a recovered stream child (trivia passed over), an edit it
171//!   cannot read: one after it when it ends with `...` (or inside the next
172//!   document, past its `---` at the start of a line), one before it when
173//!   it starts with `---` at the start of a line or a line right after a
174//!   document ended by `...` (before that marker); in each case when no
175//!   label or fix of its errors (nor of the errors of the child before a
176//!   clean neighbour: a mark's line) reaches the edit; and
177//!   past clean documents only when a `---` or `...` right after a
178//!   line break lies between (an unclosed quote reads on to such a line,
179//!   past a byte order mark that ended its document for the stream, and
180//!   past a marker after a mark), found within `TRIVIA_WALK` stream
181//!   children walked back from the edit: recovered children met before
182//!   any document are read whole by the edit's stream window and the walk
183//!   goes on past them; the first one met past a document refuses;
184//! * at stream level, a recovered stream child read whole by the window
185//!   (inserted, or put back): its errors are compared, the window starts
186//!   where reading starts afresh and ends where it does (a peeked
187//!   document starting afresh, or the end of the text), and its labels
188//!   lie inside the window.
189//!
190//! Directive errors are told from content errors only for a document
191//! recorded with one (`facts.rs`), within `TRIVIA_WALK` of its first
192//! children (past them it is taken as recovered), and only when its last
193//! error has a directive code and it is not mixed (see below;
194//! a failed directive block before the `---`, `Y0001`, may hold an
195//! unclosed quote that reads on into the content); whether a neighbour's
196//! errors reach an edit, and whether a window in a recovered document
197//! ends before its errors, is decided from content errors only
198//! (a directive error, `Y1004`, `Y0033` or `%YAML 2.x`, is zero-width
199//! before its document's `---` and only directive errors precede it, so
200//! the scans stop at the first). A document where an other error precedes
201//! a directive error (a failed directive block kept with later
202//! directives, recorded by `facts.rs`) is taken to reach every edit next
203//! to it, and its own edits are refused (O(1), where scanning
204//! its errors cost O(its directive errors)). The trivia shortcut and
205//! the unvalidated comment replacement below are not taken there. In a
206//! tree without errors none of these checks run (each edit records, in
207//! O(removed), whether the removed text holds a line break, which only
208//! they read).
209//!
210//! **Context.** Before the window's text the check writes what puts the
211//! parser in the state the window's first element is read in: the
212//! document's `%TAG` directives; for a flow collection, a synthetic block
213//! entry at the column of the nearest enclosing block collection (flow
214//! lines are indented past it, §7) and the collection's bracket; for a
215//! block collection read from its start, a synthetic entry of its parent
216//! collection (`_:`, `-`, `?`) at the parent's column, or the document's
217//! `---` when it shares that line, and the collection's first line at its
218//! column. `max_depth` is lowered by the window's depth below the tree's
219//! root, so depth counts from the root.
220//!
221//! **Extent** (the changed text plus the lines that can interact
222//! with it, never a neighbour's whole subtree):
223//!
224//! * **block mapping or sequence**: from the start of the entry the edit
225//!   is in (a key, `?`, or `-` first on its line at the entry column, or
226//!   the first child) or, for an edit after the last value of an entry,
227//!   from the last entry of the deepest block collection that value ends
228//!   with; to the first **synchronising element** after the edit: the
229//!   next entry start, or a value right after a `:` that lies after the
230//!   edit (a block collection only on a later line); never an error node,
231//!   a zero-width element, or the entry that sets the column. Of that
232//!   element, where it starts and its first token are compared (its first
233//!   line is read). Without one, the window reaches the collection's end
234//!   and takes the trivia after it up to a comment at the collection's
235//!   column or less (nothing inside can read past that), or through an
236//!   error region that follows; those tokens are compared one by one, and
237//!   outside error regions no node but the stream may end with them (C4);
238//!   an empty node among them is passed over unless it carries
239//!   diagnostics, which are then compared (a `Y0028` of a
240//!   lenient value attached to the empty value of an enclosing `? `
241//!   entry, in any tree);
242//! * **flow mapping or sequence**: from the entry the edit starts in (cut
243//!   at `,`) to the next `,` after the edit, which is compared by where it
244//!   starts, or to the closing bracket;
245//! * **stream** (edits at document or stream level): from the documents
246//!   the edit touches (or from the document before, unless the first
247//!   starts a line right after a document without diagnostics and starts
248//!   with `---` or follows `...`) to the next document, peeked when its
249//!   first line is untouched and it does not start with an error, else
250//!   read whole; trivia after the last document read is taken as for
251//!   block collections (a comment ends what a plain scalar could read).
252//!   What reads the text after a document or collection is its last
253//!   token with bytes, or an empty block scalar's text (a
254//!   zero-width last token, the empty value of a `? |` entry, hid a block
255//!   scalar whose header detects its indentation from the blank lines
256//!   after it); found down the last children, a zero-width sibling (with
257//!   its subtree) passed over in one step, at most `TRIVIA_WALK` of them
258//!   in a row at one level, else the edit is refused (O(depth),
259//!   so nested empty keys at a document's end do not refuse it).
260//!   Trivia inserted right after a document that ends with a block
261//!   collection, in a tree without errors, is read with that collection's
262//!   tail instead: the window of an edit at its end, when that window
263//!   covers the inserted text (what follows such a document is
264//!   trivia and documents starting with `---`, which read the same).
265//!
266//! **Warnings that leave.** A warning attached to the element right after
267//! the removed elements, all of whose labels lie in the removed text (a
268//! `Y0028` of a lenient `k: a: b` value, on the line break after it),
269//! leaves with that text when the edit is refused with it: the edit is
270//! then checked without it.
271//!
272//! **Shortcut.** An edit that only adds or removes white space, comments,
273//! and line breaks inside an existing run of them is well-formed exactly
274//! when the lines it touches lex, on their own, into those tokens, the
275//! content before the run cannot read them (it is closed: a comment lies
276//! between, or it is not a block scalar, and not a plain scalar when a
277//! comment is removed), and the line of the content after it is
278//! untouched: O(line), so trivia edits at document and stream level stay
279//! local. Replacing a comment by a comment is always well-formed and is
280//! not re-read in a tree without errors.
281//!
282//! **Limits.** `max_document_size` and, when documents are
283//! inserted, `max_documents` are checked on the whole text before the
284//! edit is applied (the tree keeps its document count, so this costs
285//! O(removed), not O(documents)); `max_depth` (flow pairs count, as in
286//! the parser) and `max_scalar_len` through the window.
287//! A limit the re-read reports is [`TreeEditError::Limit`] with its code.
288//!
289//! **Cost.** O(depth + window); a window is local below document level,
290//! and at document level O(the documents touched). Passing over a long run
291//! of trivia after a cut costs O(run) steps without copying text (none
292//! after a collection when the tree has no errors, hence no error region
293//! that could follow the run). Diagnostics elsewhere in the document are
294//! not visited: only those next to the edit and the document's errors,
295//! which end its content, are checked for labels the edit would move. The
296//! consequence, checked by the edit-script fuzz over arbitrary scripts and
297//! by an edit sweep over the yaml-test-suite and the fuzz corpora,
298//! recovered input included (`tests/reparse_sweep.rs`): after
299//! every accepted edit, the whole text re-parses with exactly the edited
300//! tree's diagnostics and structure ([`compare_trees`]). One exception,
301//! by design (`max_diagnostics`): past the cap, the edited
302//! tree may keep a diagnostic as a skeleton (code, severity, primary span,
303//! label reach and a keyed fingerprint of its texts, labels and fixes)
304//! where the re-parse has its texts; the two are equal on those fields,
305//! which is what [`compare_trees`] compares for a skeleton.
306//!
307//! # Recursion
308//!
309//! Nothing here recurses: the builder keeps an explicit stack of open nodes,
310//! traversals are index loops, and `Drop`, `Clone`, `Debug`, `PartialEq`,
311//! and `Hash` work on the flat arrays.
312
313mod arena;
314mod attach;
315mod build;
316mod check;
317mod cost;
318
319/// Work counters for tests (behind the unstable `__internal-checks`
320/// feature, outside the stability promise): the number of overlay
321/// lookups, treap edges and compaction visits the tree has taken on this
322/// thread since the last call. Tests use it to state that an edit costs
323/// the same on a small and on a huge document, without measuring time.
324#[cfg(feature = "__internal-checks")]
325#[doc(hidden)]
326pub fn take_work() -> u64 {
327    cost::take_total()
328}
329mod edit;
330mod facts;
331mod fragment;
332mod kind;
333mod line;
334mod node;
335mod runs;
336mod seq;
337mod slab;
338mod stored;
339mod validate;
340
341use std::borrow::Cow;
342use std::collections::BTreeMap;
343use std::sync::atomic::{AtomicU64, Ordering};
344
345use oneyaml_core::{Diagnostic, Settings, Span};
346
347use crate::event::{BlockHeader, Event, Sourced};
348
349pub use attach::{AttachRule, Attachment, CommentOwner};
350pub use check::{TreeMismatch, check_tree, compare_trees};
351pub use edit::{GroupMark, Inserted, Replaced, TreeEditError};
352pub use fragment::Fragment;
353pub use kind::SyntaxKind;
354pub use node::{Ancestors, Children, Descendants, Node, Walk, WalkEvent};
355
356use build::{Builder, Origin};
357use stored::Stored;
358
359/// `u32` index meaning "none" (the root's parent).
360const NONE: u32 = u32::MAX;
361
362/// 2³²: token starts are stored modulo this (see *Representation*).
363const WRAP: u64 = 0x1_0000_0000;
364
365/// What a node's event carried that its tokens cannot say (absolute
366/// positions, exactly as the event had them).
367#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
368struct Extra {
369    /// Start of the `%TAG` prefix the node's tag was resolved with.
370    tag_prefix: Option<usize>,
371    /// A block scalar's header.
372    block: Option<BlockHeader>,
373}
374
375/// The stamp of the next tree built or cloned (see *Handles*).
376///
377/// 64 bits, so stamps never wrap in practice: a wrapped counter would give
378/// a later tree an earlier tree's stamp, and that tree's stale handles
379/// could then resolve into the wrong tree.
380static NEXT_STAMP: AtomicU64 = AtomicU64::new(1);
381
382/// A fresh stamp. Fails closed: once the counter is exhausted (after 2⁶⁴ − 1
383/// trees), every new tree gets [`EXHAUSTED`], which resolves no handle.
384///
385/// The compare-exchange loop is what `AtomicU64::fetch_update` does; it is
386/// written out because that method is deprecated on nightly (renamed
387/// `try_update`, which is newer than the 1.85 MSRV) and docs.rs builds
388/// with nightly.
389fn new_stamp() -> u64 {
390    let mut current = NEXT_STAMP.load(Ordering::Relaxed);
391    loop {
392        let Some(next) = current.checked_add(1) else {
393            return EXHAUSTED;
394        };
395        match NEXT_STAMP.compare_exchange_weak(current, next, Ordering::Relaxed, Ordering::Relaxed)
396        {
397            Ok(previous) => return previous,
398            Err(actual) => current = actual,
399        }
400    }
401}
402
403/// The stamp of trees built after the stamp counter ran out.
404const EXHAUSTED: u64 = 0;
405
406/// A lossless syntax tree over an owned copy of its source (see the module
407/// docs).
408///
409/// Build one with [`SyntaxTree::parse`], [`SyntaxTree::parse_with`], or
410/// from an event stream with [`SyntaxTree::from_events`]. Building never
411/// fails and never panics; problems in the input are
412/// [`SyntaxKind::Error`] nodes and [`SyntaxTree::diagnostics`].
413///
414/// ```
415/// use oneyaml_syntax::tree::{SyntaxKind, SyntaxTree};
416///
417/// let tree = SyntaxTree::parse("a: [1, 2] # c\n");
418/// assert_eq!(tree.emit(), "a: [1, 2] # c\n");
419/// let doc = tree.root().first_child().unwrap();
420/// assert_eq!(doc.kind(), SyntaxKind::Document);
421/// let map = doc.first_child().unwrap();
422/// assert_eq!(map.kind(), SyntaxKind::BlockMapping);
423/// assert_eq!(map.text(), "a: [1, 2]");
424/// ```
425///
426/// Equality and hashing compare the source and the structure, not the
427/// stamp that ties [`NodeId`]s to one tree instance.
428pub struct SyntaxTree {
429    source: String,
430    kinds: Vec<SyntaxKind>,
431    parents: Vec<u32>,
432    words: Vec<u32>,
433    /// Indices at which token starts cross a multiple of 2³², one entry
434    /// per crossing; empty below 4 GiB.
435    wraps: Vec<u32>,
436    /// Sorted by node index.
437    extras: Vec<(u32, Extra)>,
438    /// Sorted by element index: an error's is its `Error` node, a
439    /// warning's is the element that followed it.
440    diagnostics: Vec<(u32, Stored)>,
441    /// `Document` children of the stream, kept up to date by edits (so
442    /// `max_documents` is checked against it in O(1)).
443    documents: usize,
444    /// Diagnostics of the parse kept as skeletons (past
445    /// `Limits::max_diagnostics`); edits never change it.
446    suppressed: usize,
447    /// Error-severity diagnostics in the tree, kept up to date by edits
448    /// (a tree without errors has no error region, which lets a
449    /// window skip looking for one past a run of trivia).
450    errors: usize,
451    /// Slots whose generation is not 0; empty for a freshly built tree.
452    ///
453    /// The edit layer never bumps a generation,
454    /// because it never reuses a slot (a removed element's slot is simply
455    /// not live, and resolves to [`StaleNode`]); the map stays empty and
456    /// allocates nothing. It is the one place a [`NodeId`]'s `generation`
457    /// is checked against, kept for a later compaction that reuses slots
458    /// (which would retire them here instead of leaving them dead).
459    generations: BTreeMap<u32, u32>,
460    stamp: u64,
461    /// Handle identity across [`SyntaxTree::fork`]:
462    /// `(stamp, limit)` of each ancestor this tree was forked
463    /// from, oldest first, limits strictly increasing. Slots below the
464    /// first limit are named by the first ancestor's stamp, slots from one
465    /// limit to the next by the next ancestor's, and the rest by `stamp`.
466    /// Empty (no allocation) for a tree that was never forked.
467    ///
468    /// Compacted at every fork: a pair whose range
469    /// holds no live slot any more is dropped (its range joins the next
470    /// owner's; its slots are dead for good, so no handle of either owner
471    /// resolves there). So a tree keeps at most one pair per range of
472    /// slots it still holds, bounded by its live content, never by the
473    /// number of forks in its history.
474    ancestry: Vec<(u64, u32)>,
475    /// The first slot an overlay created from now on may issue: a
476    /// rolled-back edit group that created the overlay drops it,
477    /// and the slots the group issued must never be issued again. 0 until
478    /// such a rollback.
479    slot_floor: u32,
480    /// Long stream-level trivia runs and documents with directive errors
481    /// of the parsed arrays (`facts.rs`; empty, no allocation, for most
482    /// trees).
483    facts: facts::StreamFacts,
484    /// The comment-run index of the parsed arrays (`runs.rs`;
485    /// empty, no allocation, without a long run of comment lines).
486    run_facts: runs::RunFacts,
487    /// The settings the tree was parsed with; edits re-read text under
488    /// them (never the defaults).
489    settings: Settings,
490    /// The edit overlay (`edit.rs`); `None` until the first edit, so the
491    /// read path of a parsed tree is unchanged.
492    edits: Option<Box<edit::Edits>>,
493    /// The accepted edits of the open edit groups
494    /// ([`SyntaxTree::begin_group`]), to be undone together; empty (no
495    /// allocation) outside a group.
496    group: edit::Group,
497}
498
499/// A stable handle to an element of one [`SyntaxTree`].
500///
501/// Resolve it with [`SyntaxTree::get`]; a handle that no longer names a
502/// live element of that tree yields [`StaleNode`], never a wrong element.
503#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
504pub struct NodeId {
505    tree: u64,
506    index: u32,
507    generation: u32,
508}
509
510/// A [`NodeId`] that names no live element of the tree it was used with:
511/// issued by another tree, or its element was replaced or removed.
512#[non_exhaustive]
513#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
514pub struct StaleNode {
515    /// The handle that failed to resolve.
516    pub id: NodeId,
517}
518
519impl core::fmt::Display for StaleNode {
520    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
521        f.write_str("stale node handle: the element no longer exists in this tree")
522    }
523}
524
525impl std::error::Error for StaleNode {}
526
527impl SyntaxTree {
528    /// Parses `source` under the default [`Settings`] and builds its tree.
529    ///
530    /// Pass a `String` to hand over its buffer; a `&str` is copied.
531    #[must_use]
532    pub fn parse(source: impl Into<String>) -> Self {
533        Self::parse_with(source, &Settings::new())
534    }
535
536    /// Parses `source` under `settings` and builds its tree from the pull
537    /// parser's events as they come, without collecting them.
538    #[must_use]
539    pub fn parse_with(source: impl Into<String>, settings: &Settings) -> Self {
540        let source = source.into();
541        let parts = {
542            let mut builder = Builder::new(source.len(), Origin::Parser)
543                .max_diagnostics(settings.get_limits().get_max_diagnostics());
544            for event in crate::parser::events_with(&source, settings) {
545                builder.push(event.into_event());
546            }
547            builder.finish()
548        };
549        Self::from_parts(source, parts, settings.clone())
550    }
551
552    /// Builds the tree of an event stream, e.g. `list.sourced()` of an
553    /// [`EventList`](crate::event::EventList) or
554    /// [`events_with`](crate::parser::events_with), copying its source.
555    ///
556    /// A stream from the parser always satisfies the event contract, and
557    /// its tree always round-trips. A stream that was filtered or reordered
558    /// still builds without panicking; the tree then records a `Y9001`
559    /// ([`INVALID_EVENT_STREAM`](oneyaml_core::code::INVALID_EVENT_STREAM))
560    /// diagnostic, covers any bytes the stream skipped with
561    /// [`SyntaxKind::Skipped`] tokens, and its spans follow the tokens it
562    /// was given.
563    #[must_use]
564    pub fn from_events<'a, E, I>(events: I) -> Self
565    where
566        E: core::borrow::Borrow<Event<'a>>,
567        I: IntoIterator<Item = Sourced<'a, E>>,
568    {
569        let mut events = events.into_iter().peekable();
570        let source = events.peek().map_or("", Sourced::source);
571        let mut builder = Builder::new(source.len(), Origin::Caller);
572        for event in events {
573            builder.push(event.event().clone());
574        }
575        let parts = builder.finish();
576        Self::from_parts(source.to_owned(), parts, Settings::new())
577    }
578
579    fn from_parts(source: String, parts: build::Parts, settings: Settings) -> Self {
580        let errors = parts
581            .diagnostics
582            .iter()
583            .filter(|(_, d)| d.is_error())
584            .count();
585        let mut tree = Self {
586            source,
587            kinds: parts.kinds,
588            parents: parts.parents,
589            words: parts.words,
590            wraps: parts.wraps,
591            extras: parts.extras,
592            diagnostics: parts.diagnostics,
593            documents: parts.documents,
594            suppressed: parts.suppressed,
595            errors,
596            generations: BTreeMap::new(),
597            stamp: new_stamp(),
598            ancestry: Vec::new(),
599            slot_floor: 0,
600            facts: facts::StreamFacts::default(),
601            run_facts: runs::RunFacts::default(),
602            settings,
603            edits: None,
604            group: edit::Group::default(),
605        };
606        let flat = tree.base_flat();
607        let mut child = flat.first_child(0);
608        let children = core::iter::from_fn(move || {
609            let c = child?;
610            child = flat.next_sibling(c);
611            Some(c)
612        });
613        tree.facts = facts::StreamFacts::of(flat, children, tree.errors > 0);
614        tree.run_facts = runs::RunFacts::of(tree.base_flat());
615        tree
616    }
617
618    /// The settings the tree was parsed with ([`Settings::new`] for a tree
619    /// built with [`SyntaxTree::from_events`]). Edits re-read text under
620    /// them.
621    #[must_use]
622    pub fn settings(&self) -> &Settings {
623        &self.settings
624    }
625
626    /// The source text the tree was built from (unchanged by edits: see
627    /// [`SyntaxTree::emit`] for the current text).
628    #[must_use]
629    pub fn source(&self) -> &str {
630        &self.source
631    }
632
633    /// The [`SyntaxKind::Stream`] node spanning the whole input.
634    #[must_use]
635    pub fn root(&self) -> Node<'_> {
636        // (O(1), without a hint; the iterators find theirs once.)
637        Node::new(self, 0)
638    }
639
640    /// Number of elements (nodes and tokens).
641    #[must_use]
642    pub fn len(&self) -> usize {
643        if self.edits.is_some() {
644            return usize::try_from(self.nav_total().0).unwrap_or(usize::MAX);
645        }
646        self.kinds.len()
647    }
648
649    /// `true` when the tree has no elements, which never happens for a
650    /// built tree (the root always exists).
651    #[must_use]
652    pub fn is_empty(&self) -> bool {
653        // The same count as [`SyntaxTree::len`].
654        self.len() == 0
655    }
656
657    /// The element `id` names, or [`StaleNode`].
658    ///
659    /// # Errors
660    ///
661    /// [`StaleNode`] when `id` was issued by another tree or its element no
662    /// longer exists.
663    pub fn get(&self, id: NodeId) -> Result<Node<'_>, StaleNode> {
664        // A handle names a slot of the tree, or of the
665        // ancestor it was forked from before the fork; O(log A) for A
666        // ancestors, O(1) for a tree never forked.
667        let named = id.tree == self.owner(id.index)
668            && id.tree != EXHAUSTED
669            && self.stamp != EXHAUSTED
670            && self.generation(id.index) == id.generation;
671        // The run lookup that finds the slot live gives its
672        // hint (one O(log R) lookup, as before).
673        let hint = if !named {
674            None
675        } else if self.edits.is_some() {
676            self.run_item(id.index).map(|(item, _, _)| item)
677        } else {
678            self.is_live(id.index).then_some(NONE)
679        };
680        match hint {
681            Some(h) => Ok(Node::hinted(self, id.index, h)),
682            None => Err(StaleNode { id }),
683        }
684    }
685
686    /// The live element named by `slot` ([`Node::slot`]), or `None` once
687    /// it was removed or replaced (or for a slot this tree never issued).
688    /// The same element as [`SyntaxTree::get`] resolves the handle of an
689    /// element of this tree to. O(1); O(log R) in an edited tree.
690    #[must_use]
691    pub fn node_at_slot(&self, slot: u32) -> Option<Node<'_>> {
692        if slot == NONE {
693            return None;
694        }
695        if self.edits.is_some() {
696            // The lookup that finds the slot live gives its hint.
697            return self
698                .run_item(slot)
699                .map(|(item, _, _)| Node::hinted(self, slot, item));
700        }
701        self.is_live(slot).then(|| Node::new(self, slot))
702    }
703
704    /// Every diagnostic, errors and warnings, in element order (see
705    /// [`SyntaxTree::diagnostics_by_element`]). Borrowed from a parsed
706    /// tree; an edited tree's are built with their spans moved to the
707    /// edited text (O(d + D log R) for the D runs holding diagnostics, no
708    /// cache). Complete: past `max_diagnostics` they are skeletons
709    /// ([`SyntaxTree::is_skeleton`]).
710    pub fn diagnostics(&self) -> impl ExactSizeIterator<Item = Cow<'_, Diagnostic>> + '_ {
711        self.diagnostics_by_element().map(|(_, d)| d)
712    }
713
714    /// How many of the parse's diagnostics are kept as skeletons:
715    /// a tree keeps the first `Limits::max_diagnostics + 1`
716    /// diagnostics of its parse in stream order with their texts, and the
717    /// first error wherever it is; every other one as a fixed-size
718    /// **skeleton** (32 bytes, no heap). So the tree's record of what the
719    /// parse found (every error, its position, its error node) is complete
720    /// whatever the limit; only texts are not stored. Edits never change
721    /// the count.
722    #[must_use]
723    pub const fn suppressed_diagnostics(&self) -> usize {
724        self.suppressed
725    }
726
727    /// Whether `d` is a skeleton (see
728    /// [`SyntaxTree::suppressed_diagnostics`]). Readers see a skeleton as
729    /// a diagnostic with its code, severity, and primary span, and empty
730    /// texts (no diagnostic with texts has an empty message), and nothing
731    /// else: how the tree compares skeletons with re-read diagnostics is
732    /// internal and never exposed.
733    #[must_use]
734    pub fn is_skeleton(d: &Diagnostic) -> bool {
735        d.message.is_empty()
736    }
737
738    /// The element a diagnostic is attached to.
739    fn diag_node(&self, i: u32) -> Option<Node<'_>> {
740        let live = if self.edits.is_some() {
741            i != NONE
742        } else {
743            (i as usize) < self.kinds.len()
744        };
745        live.then(|| Node::new(self, i))
746    }
747
748    /// Every diagnostic with the element it is attached to, in element
749    /// order: an error's [`SyntaxKind::Error`] node, a warning's element
750    /// that followed it in the event stream, or `None` for a warning after
751    /// the last element. Consumers that read the tree as an event stream
752    /// use this to see warnings where the stream reported them.
753    ///
754    /// Borrowed from a parsed tree. An edited tree's are built on each call
755    /// from the arenas' own lists, spans moved to the edited text: O(d + D
756    /// (log d + log R)) for d diagnostics, R runs, and the D runs holding
757    /// any (the others are skipped by the treap's sums), and
758    /// nothing is cached.
759    pub fn diagnostics_by_element(
760        &self,
761    ) -> impl ExactSizeIterator<Item = (Option<Node<'_>>, Cow<'_, Diagnostic>)> + '_ {
762        let source = match self.edits.as_deref() {
763            Some(e) => DiagSource::Built(self.edited_diagnostics(e, None).into_iter()),
764            None => DiagSource::Parsed(self.diagnostics.iter()),
765        };
766        DiagIter {
767            tree: self,
768            source,
769            fill: &[],
770        }
771    }
772
773    /// The diagnostics attached to elements of `node`'s subtree (see
774    /// [`SyntaxTree::diagnostics_by_element`]), in element order. Found by
775    /// binary search: O(log d + k) for k results, so reading one
776    /// document of a stream does not scan the others' diagnostics; in an
777    /// edited tree O(D' (log d + log R) + k) for the D' runs of the subtree
778    /// holding diagnostics (never the subtree's other runs), with
779    /// nothing rebuilt for the rest of the tree.
780    pub fn diagnostics_within<'s>(
781        &'s self,
782        node: Node<'s>,
783    ) -> impl ExactSizeIterator<Item = (Option<Node<'s>>, Cow<'s, Diagnostic>)> + 's {
784        self.diagnostics_within_iter(node)
785    }
786
787    fn diagnostics_within_iter<'s>(&'s self, node: Node<'s>) -> DiagIter<'s> {
788        let source = match self.edits.as_deref() {
789            Some(e) => DiagSource::Built(self.edited_diagnostics(e, Some(node.slot())).into_iter()),
790            None => {
791                let first = node.preorder_index();
792                let past = self.end_of(first);
793                let lo = self
794                    .diagnostics
795                    .partition_point(|(n, _)| (*n as usize) < first);
796                let hi = self
797                    .diagnostics
798                    .partition_point(|(n, _)| (*n as usize) < past)
799                    .max(lo);
800                DiagSource::Parsed(self.diagnostics.get(lo..hi).unwrap_or_default().iter())
801            }
802        };
803        DiagIter {
804            tree: self,
805            source,
806            fill: &[],
807        }
808    }
809
810    /// [`SyntaxTree::diagnostics_within`], with each skeleton
811    /// ([`SyntaxTree::is_skeleton`]) that a diagnostic of `fill` records
812    /// read as that diagnostic, texts included: `fill`
813    /// holds diagnostics with texts found by reading the same text again
814    /// (with spans in this tree's text), **sorted by start**. A skeleton
815    /// records a diagnostic when they have the same code, severity,
816    /// primary span, label reach, and keyed fingerprint of everything the
817    /// skeleton does not keep (as the tree compares them when it re-reads
818    /// an edit's text), so a skeleton is never given another
819    /// diagnostic's texts; one that none records stays a skeleton. Cost:
820    /// as [`SyntaxTree::diagnostics_within`], plus O(log f) per skeleton.
821    pub fn diagnostics_within_filled<'s>(
822        &'s self,
823        node: Node<'s>,
824        fill: &'s [Diagnostic],
825    ) -> impl ExactSizeIterator<Item = (Option<Node<'s>>, Cow<'s, Diagnostic>)> + 's {
826        DiagIter {
827            fill,
828            ..self.diagnostics_within_iter(node)
829        }
830    }
831
832    /// `true` when the tree has at least one error. O(1): the count is
833    /// kept by every edit.
834    #[must_use]
835    pub fn has_errors(&self) -> bool {
836        self.errors > 0
837    }
838
839    /// A copy that shares this tree's **handle identity**:
840    /// every [`NodeId`] issued before the fork, by this tree
841    /// or the copy, resolves in both to the same element for as long as
842    /// that copy keeps it, and [`Node::id`] of such an element is the same
843    /// value in both. Elements inserted after the fork get handles of
844    /// their own tree, stale in the other; an element removed from one
845    /// copy is stale there only. Forks of forks work the same way.
846    ///
847    /// [`Clone`] gives an independent tree instead (no handle of the
848    /// original resolves in it).
849    ///
850    /// Cost: O(n + L) for the parsed text and arrays (n) and the live
851    /// edits (L: the inserted arenas some run still covers, the runs, the
852    /// link overrides of live slots; never the edit history,
853    /// since text removed by accepted edits is dropped with its arena),
854    /// plus one `(stamp, slot)` pair of metadata per ancestor range that
855    /// still holds a live slot (no per-copy translation map, pairs of
856    /// ranges without live slots are dropped); resolving a handle is
857    /// O(log A) for A such pairs.
858    #[must_use]
859    pub fn fork(&self) -> Self {
860        let mut copy = self.clone();
861        // Only the ranges that still hold a live
862        // slot keep their pair (O(A log R)).
863        let mut lo = 0u32;
864        for &(stamp, limit) in &self.ancestry {
865            if self.holds_live(lo, limit) {
866                copy.ancestry.push((stamp, limit));
867            }
868            lo = limit;
869        }
870        let limit = self.next_slot();
871        // An ancestor that issued no slot since the previous fork owns an
872        // empty range: it is not recorded (chains of forks grow only
873        // with the edits between them); nor one whose slots are all dead.
874        if self.holds_live(lo, limit) {
875            copy.ancestry.push((self.stamp, limit));
876        }
877        copy
878    }
879
880    /// The text of the tree: its tokens' bytes in order. For a tree that
881    /// was not edited this is exactly the input; for an edited tree,
882    /// exactly the input with each edit's bytes spliced in. O(n): an edited
883    /// tree's text is copied run by run, O(1) per run beyond its bytes, with
884    /// no map lookup (a run holds at least one element).
885    #[must_use]
886    pub fn emit(&self) -> String {
887        if let Some(e) = self.edits.as_deref() {
888            return self.edited_emit(e);
889        }
890        let mut out = String::with_capacity(self.source.len());
891        // A flat loop over the arena; no recursion.
892        for node in self.root().descendants() {
893            if node.is_token() {
894                out.push_str(&node.text());
895            }
896        }
897        out
898    }
899
900    // ------------------------------------------------------------ storage
901
902    fn generation(&self, index: u32) -> u32 {
903        self.generations.get(&index).copied().unwrap_or(0)
904    }
905
906    #[inline]
907    fn kind_at(&self, i: usize) -> Option<SyntaxKind> {
908        self.kinds.get(i).copied()
909    }
910
911    /// The parent index of `i`, if any.
912    #[inline]
913    fn parent_of(&self, i: usize) -> Option<usize> {
914        match self.parents.get(i) {
915            Some(&p) if p != NONE => Some(p as usize),
916            _ => None,
917        }
918    }
919
920    /// One past the last index of `i`'s subtree.
921    #[inline]
922    fn end_of(&self, i: usize) -> usize {
923        match self.kind_at(i) {
924            Some(k) if !k.is_token() => self.words.get(i).map_or(i, |w| *w as usize),
925            _ => i.saturating_add(1),
926        }
927    }
928
929    /// The start offset of token `i`.
930    fn token_start(&self, i: usize) -> usize {
931        let low = u64::from(self.words.get(i).copied().unwrap_or(0));
932        if self.wraps.is_empty() {
933            return usize::try_from(low).unwrap_or(usize::MAX);
934        }
935        let crossings = self.wraps.partition_point(|w| *w as usize <= i);
936        let high = u64::try_from(crossings)
937            .ok()
938            .and_then(|c| c.checked_mul(WRAP));
939        high.and_then(|h| h.checked_add(low))
940            .and_then(|at| usize::try_from(at).ok())
941            .unwrap_or(usize::MAX)
942    }
943
944    /// Where element `i` starts: its own start for a token, the start of
945    /// the next token in preorder for a node (tiling, C1), or the end of
946    /// the input.
947    fn start_of(&self, mut i: usize) -> usize {
948        loop {
949            match self.kind_at(i) {
950                None => return self.source.len(),
951                Some(k) if k.is_token() => return self.token_start(i),
952                Some(_) => i = i.saturating_add(1),
953            }
954        }
955    }
956
957    /// The span of element `i`.
958    fn span_of(&self, i: usize) -> Span {
959        let start = self.start_of(i);
960        let end = self.start_of(self.end_of(i)).max(start);
961        Span::new(start, end)
962    }
963
964    fn extra(&self, i: usize) -> Option<&Extra> {
965        let at = self
966            .extras
967            .binary_search_by_key(&i, |(n, _)| *n as usize)
968            .ok()?;
969        self.extras.get(at).map(|(_, e)| e)
970    }
971
972    fn diagnostic_at(&self, i: usize) -> Option<Cow<'_, Diagnostic>> {
973        if self.edits.is_some() {
974            let slot = u32::try_from(i).ok()?;
975            return pick_error(self.diagnostics_of(slot).into_iter());
976        }
977        let first = self.diagnostics.partition_point(|(n, _)| (*n as usize) < i);
978        // A warning just before an error is attached to the same element
979        // (the one that followed it): the error node's own diagnostic is
980        // the error.
981        let at_i = self
982            .diagnostics
983            .get(first..)
984            .unwrap_or_default()
985            .iter()
986            .take_while(|(n, _)| *n as usize == i)
987            .map(|(_, d)| d.view());
988        pick_error(at_i)
989    }
990
991    fn id_of(&self, index: u32) -> NodeId {
992        NodeId {
993            tree: self.owner(index),
994            index,
995            generation: self.generation(index),
996        }
997    }
998
999    /// The stamp that names `index` in this tree (see `ancestry`).
1000    fn owner(&self, index: u32) -> u64 {
1001        let k = self.ancestry.partition_point(|(_, l)| *l <= index);
1002        self.ancestry.get(k).map_or(self.stamp, |(s, _)| *s)
1003    }
1004
1005    /// Some slot in `lo..hi` is live. O(log R).
1006    fn holds_live(&self, lo: u32, hi: u32) -> bool {
1007        if lo >= hi {
1008            return false;
1009        }
1010        let Some(e) = self.edits.as_deref() else {
1011            return (lo as usize) < self.kinds.len();
1012        };
1013        // Runs never overlap in slot space: the last run starting below
1014        // `hi` is the only one that can reach into the range from below.
1015        e.live_in(lo, hi)
1016    }
1017
1018    /// The first slot the next insertion takes.
1019    fn next_slot(&self) -> u32 {
1020        match self.edits.as_deref() {
1021            Some(e) => e.next_slot(),
1022            None => u32::try_from(self.kinds.len())
1023                .unwrap_or(NONE)
1024                .max(self.slot_floor),
1025        }
1026    }
1027}
1028
1029/// Where [`DiagIter`] reads from.
1030enum DiagSource<'t> {
1031    /// A parsed tree's list, borrowed.
1032    Parsed(core::slice::Iter<'t, (u32, Stored)>),
1033    /// An edited tree's, built for this call.
1034    Built(std::vec::IntoIter<(u32, Stored)>),
1035}
1036
1037/// Diagnostics with the elements they are attached to.
1038struct DiagIter<'t> {
1039    tree: &'t SyntaxTree,
1040    source: DiagSource<'t>,
1041    /// Diagnostics with texts, sorted by start, to read for the
1042    /// skeletons they record (see [`SyntaxTree::diagnostics_within_filled`]).
1043    fill: &'t [Diagnostic],
1044}
1045
1046impl<'t> DiagIter<'t> {
1047    /// `d` as readers see it, or, for a skeleton, the diagnostic of `fill`
1048    /// it records (O(log f + those starting where it starts)).
1049    fn seen(&self, d: &Stored) -> Cow<'t, Diagnostic> {
1050        if !self.fill.is_empty() && !matches!(d, Stored::Full(_)) {
1051            let at = d.span().start;
1052            let lo = self.fill.partition_point(|c| c.primary.span.start < at);
1053            let found = self
1054                .fill
1055                .get(lo..)
1056                .unwrap_or_default()
1057                .iter()
1058                .take_while(|c| c.primary.span.start == at)
1059                .find(|c| stored::records(d, c));
1060            if let Some(c) = found {
1061                return Cow::Borrowed(c);
1062            }
1063        }
1064        Cow::Owned(d.view().into_owned())
1065    }
1066}
1067
1068impl<'t> Iterator for DiagIter<'t> {
1069    type Item = (Option<Node<'t>>, Cow<'t, Diagnostic>);
1070
1071    fn next(&mut self) -> Option<Self::Item> {
1072        match &mut self.source {
1073            DiagSource::Parsed(it) => {
1074                let (i, d) = it.next()?;
1075                // (without `fill`, exactly the reads of the plain path,
1076                // at their cost.)
1077                let seen = if self.fill.is_empty() || matches!(d, Stored::Full(_)) {
1078                    d.view()
1079                } else {
1080                    self.seen(d)
1081                };
1082                Some((self.tree.diag_node(*i), seen))
1083            }
1084            DiagSource::Built(it) => {
1085                let (i, d) = it.next()?;
1086                let seen = if self.fill.is_empty() || matches!(d, Stored::Full(_)) {
1087                    Cow::Owned(d.view().into_owned())
1088                } else {
1089                    self.seen(&d)
1090                };
1091                Some((self.tree.diag_node(i), seen))
1092            }
1093        }
1094    }
1095
1096    fn size_hint(&self) -> (usize, Option<usize>) {
1097        match &self.source {
1098            DiagSource::Parsed(it) => it.size_hint(),
1099            DiagSource::Built(it) => it.size_hint(),
1100        }
1101    }
1102}
1103
1104impl ExactSizeIterator for DiagIter<'_> {}
1105
1106/// The error among one element's diagnostics, else the first warning.
1107fn pick_error<'a>(at_i: impl Iterator<Item = Cow<'a, Diagnostic>>) -> Option<Cow<'a, Diagnostic>> {
1108    let mut fallback = None;
1109    for d in at_i {
1110        if d.severity == oneyaml_core::Severity::Error {
1111            return Some(d);
1112        }
1113        fallback = fallback.or(Some(d));
1114    }
1115    fallback
1116}
1117
1118impl Clone for SyntaxTree {
1119    /// An independent copy with its own stamp: handles of the original do
1120    /// not resolve in the copy (they may diverge once edited). See
1121    /// [`SyntaxTree::fork`] for a copy that keeps them.
1122    fn clone(&self) -> Self {
1123        let mut copy = Self {
1124            source: self.source.clone(),
1125            kinds: self.kinds.clone(),
1126            parents: self.parents.clone(),
1127            words: self.words.clone(),
1128            wraps: self.wraps.clone(),
1129            extras: self.extras.clone(),
1130            diagnostics: self.diagnostics.clone(),
1131            documents: self.documents,
1132            suppressed: self.suppressed,
1133            errors: self.errors,
1134            generations: self.generations.clone(),
1135            stamp: new_stamp(),
1136            ancestry: Vec::new(),
1137            facts: self.facts.clone(),
1138            run_facts: self.run_facts.clone(),
1139            settings: self.settings.clone(),
1140            slot_floor: self.slot_floor,
1141            edits: self.edits.clone(),
1142            // An open group belongs to the tree it was opened on: the copy
1143            // starts with none (its accepted edits are simply kept).
1144            group: edit::Group::default(),
1145        };
1146        // The copy keeps the group's edits as accepted
1147        // ones, so it merges and releases what the group held back.
1148        self.settle_group_copy(&mut copy);
1149        copy
1150    }
1151}
1152
1153impl PartialEq for SyntaxTree {
1154    /// Structural equality ([`compare_trees`]): the same elements in the
1155    /// same shape, token texts, block headers, resolved tags, and
1156    /// diagnostics. Not the stamp, the generations, or how edits laid the
1157    /// tree out, so an edited tree equals the tree parsed from its
1158    /// [`SyntaxTree::emit`] exactly when they agree structurally.
1159    fn eq(&self, other: &Self) -> bool {
1160        // Fast path: identical parsed arrays.
1161        let raw = self.edits.is_none()
1162            && other.edits.is_none()
1163            && self.source == other.source
1164            && self.kinds == other.kinds
1165            && self.parents == other.parents
1166            && self.words == other.words
1167            && self.wraps == other.wraps
1168            && self.extras == other.extras
1169            && self.diagnostics == other.diagnostics;
1170        raw || compare_trees(self, other).is_ok()
1171    }
1172}
1173
1174impl Eq for SyntaxTree {}
1175
1176impl core::hash::Hash for SyntaxTree {
1177    /// Hashes what [`PartialEq`] compares (a flat walk).
1178    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
1179        check::for_each_item(self, |item| item.hash(state));
1180    }
1181}
1182
1183impl core::fmt::Debug for SyntaxTree {
1184    /// One line per element in preorder, `depth kind@start..end`, with the
1185    /// text of short tokens. Iterative, and O(n) output whatever the depth
1186    /// (depth is printed as a number, not as indentation).
1187    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1188        writeln!(f, "SyntaxTree ({} elements)", self.len())?;
1189        let mut depth = 0usize;
1190        for event in self.root().walk() {
1191            match event {
1192                WalkEvent::Enter(node) => {
1193                    let span = node.span();
1194                    write!(f, "{depth} {:?}@{}..{}", node.kind(), span.start, span.end)?;
1195                    if node.is_token() && span.len() <= 40 {
1196                        write!(f, " {:?}", node.text())?;
1197                    }
1198                    f.write_str("\n")?;
1199                    depth = depth.saturating_add(1);
1200                }
1201                WalkEvent::Leave(_) => depth = depth.saturating_sub(1),
1202            }
1203        }
1204        for d in self.diagnostics() {
1205            writeln!(f, "{d}")?;
1206        }
1207        Ok(())
1208    }
1209}
1210
1211#[cfg(test)]
1212mod tests;
1213
1214#[cfg(test)]
1215mod read_tests;