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;