Skip to main content

oneyaml_syntax/tree/
edit.rs

1//! Structural edits of a [`SyntaxTree`].
2//!
3//! # Representation of an edited tree
4//!
5//! The parsed arrays are never modified. The first edit adds an [`Edits`]
6//! overlay (O(1)); from then on the tree is:
7//!
8//! * **arenas**: the base tree (arena 0) and one owned, immutable flat
9//!   arena per inserted [`Fragment`]. Every element has a **slot**: its
10//!   index in the base, or its arena's first slot plus its local index.
11//!   Slots are never reused, so a [`NodeId`] of a removed or replaced
12//!   element can never name another element. An inserted arena
13//!   that no run covers any more (all its text was removed again) is
14//!   dropped when that removal is accepted (memory stays bounded), so
15//!   the overlay holds the text in the tree, not the edit history;
16//! * **order**: the elements in preorder are a sequence of **runs**, each
17//!   a contiguous local range of one arena, kept in a treap with sums of
18//!   element counts and token bytes ([`Seq`]). A slot is live exactly when
19//!   a run covers it. Rank ([`Node::preorder_index`]) and byte offset
20//!   ([`Node::span`]) are a prefix sum: O(log R) for R runs, and R grows
21//!   by at most 3 per accepted edit, never with the document; a refused
22//!   edit merges back the runs it split, and an
23//!   accepted one merges the runs it leaves continuing each other (an
24//!   insertion and its removal leave no run behind). Each run
25//!   also counts its arena's diagnostics, summed in the treap, so a scan
26//!   for diagnostics jumps over the runs without any in O(log R); and
27//!   says whether it holds only stream-level trivia tokens, summed too,
28//!   so a walk over stream-level trivia jumps over any number of such runs
29//!   in O(log R);
30//!
31//!   **Sequential reads**: a run names its arena's index in a
32//!   slab (`slab.rs`, O(1), entries never move), and a [`Node`] carries
33//!   its run's treap item as a hint, which the iterators keep with the
34//!   run's bounds. Inside a run every step is the arena's arithmetic (see
35//!   *hinted reads* below: parents are the arena's and the run's preorder
36//!   is the arena's, so a link that stays inside a run is determined), and
37//!   the next run is the treap successor, so a full
38//!   read costs amortised O(1) per element and O(1) lookups per run;
39//!
40//!   **Edit cost is independent of edit history**:
41//!   no step of an edit or a read visits the runs
42//!   one by one outside the edit's own window, so the k-th edit costs
43//!   what the first costs, up to the O(log R) of the treap;
44//! * **links**: parent, first/last child, and next/previous sibling are
45//!   read from the element's own arena (the same O(1)/O(depth) arithmetic
46//!   as an unedited tree, one link at a time), except where an edit changed
47//!   them: a sparse map of overrides, at most 4 entries per edit, those
48//!   of removed slots dropped with them;
49//! * **dropped warnings**: warnings attached to a live element whose
50//!   labels were all in text an edit removed (a `Y0028` of a replaced
51//!   lenient value, on the line break after it): skipped by
52//!   every read, so the element and its handle stay.
53//!
54//! Nothing else is kept: no copies of text and no moved diagnostics
55//! (no per-node caches, no interior mutability). A
56//! node's text is read from the runs it spans (borrowed when one run holds
57//! it), and diagnostics are read from each arena's own list, their spans
58//! moved on the way out.
59//!
60//! # Cost of an edit
61//!
62//! An edit copies what it removes (O(removed)), links the fragment in
63//! (O(fragment roots)), splits at most two runs, updates at most four link
64//! overrides (O(depth)), and re-reads its validation window in context
65//! (see the module docs of [`super`], *Well-formed edits*): O(depth +
66//! log R + window), never O(document) below document level, and never a
67//! neighbouring entry's whole subtree. A refused edit
68//! is rolled back exactly (an undo record of the few changes made), so the
69//! tree, its text, and every handle are as they were.
70
71use super::stored::Stored;
72use std::borrow::Cow;
73use std::collections::{BTreeMap, BTreeSet};
74
75use oneyaml_core::{Code, Diagnostic, Settings, Span};
76
77use super::arena::{Arena, Flat};
78use super::facts::{LONG_RUN, StreamFacts};
79use super::fragment::Fragment;
80use super::runs::{Marks, Piece, RunFacts, marks};
81use super::seq::{Run, RunAt, Seq};
82use super::slab::Slab;
83use super::validate::Removed;
84use super::{Extra, NONE, NodeId, StaleNode, SyntaxKind, SyntaxTree, cost};
85
86/// Why an edit of a [`SyntaxTree`] was refused. The tree is unchanged
87/// when an edit fails.
88///
89/// A distinct name from `oneyaml`'s own `EditError`: the
90/// `oneyaml` crate maps this type and never re-exports it.
91#[non_exhaustive]
92#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
93pub enum TreeEditError {
94    /// A handle names no live element of this tree.
95    Stale(StaleNode),
96    /// Children were to be added under a token.
97    NotANode {
98        /// The token's kind.
99        kind: SyntaxKind,
100    },
101    /// A token operation was given a node.
102    NotAToken {
103        /// The node's kind.
104        kind: SyntaxKind,
105    },
106    /// The element has no parent (the stream root cannot be removed,
107    /// replaced, or given siblings).
108    NoParent,
109    /// The two ends of a range are not siblings, or the last comes before
110    /// the first.
111    NotSiblings,
112    /// A child position past the end.
113    Position {
114        /// The position asked for.
115        position: usize,
116        /// Number of children (or roots).
117        len: usize,
118    },
119    /// The element cannot be changed this way: the inside of a scalar,
120    /// alias, or error node; directives (they change the meaning of the
121    /// whole document); tag properties and block scalar headers (their
122    /// meaning is carried by the node: replace the node instead); tokens
123    /// whose text cannot be replaced in place. `kind: Error` also for an
124    /// edit that could change how recovered input reads (see
125    /// *Recovered input* in the [module docs](super)).
126    ReadOnly {
127        /// The kind refused.
128        kind: SyntaxKind,
129    },
130    /// A fragment element may not sit under that parent (a stream anywhere,
131    /// a document outside the stream, a YAML node directly in the stream).
132    Misplaced {
133        /// The fragment element's kind.
134        kind: SyntaxKind,
135        /// The parent's kind.
136        parent: SyntaxKind,
137    },
138    /// The fragment has tags resolved under other `%TAG` directives than
139    /// the document it would go into.
140    TagContext,
141    /// Replacement text does not read as exactly one token of the kind it
142    /// replaces.
143    InvalidToken {
144        /// The token kind expected.
145        kind: SyntaxKind,
146    },
147    /// Fragment text does not parse cleanly: the first error's code.
148    Syntax {
149        /// Code of the first error.
150        code: Code,
151    },
152    /// An empty fragment cannot be inserted.
153    EmptyFragment,
154    /// The edit is not well-formed: the text around it, read again through
155    /// the parser, would not give the tree the edit produces (it has
156    /// errors, or another structure). See the *Well-formed edits* section
157    /// of the [module docs](super) for the exact rule.
158    NotWellFormed,
159    /// The edit would exceed one of the tree's
160    /// [`Limits`](oneyaml_core::Limits) (limits apply to edits): the
161    /// code of the limit diagnostic the edited text would re-parse with
162    /// (`Y2000` `max_depth`, counted from the tree's root; `Y2001`
163    /// `max_scalar_len`; `Y2002` `max_document_size`; `Y2003`
164    /// `max_documents`).
165    Limit {
166        /// The limit diagnostic's code.
167        code: Code,
168    },
169    /// The slot space (2³² elements over the tree's lifetime) or a
170    /// fragment's 4 GiB is exhausted.
171    Capacity,
172    /// An internal invariant failed (a bug; `Y9000`).
173    Internal,
174}
175
176impl core::fmt::Display for TreeEditError {
177    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
178        match self {
179            Self::Stale(s) => write!(f, "{s}"),
180            Self::NotANode { kind } => write!(f, "a {kind:?} token has no children"),
181            Self::NotAToken { kind } => write!(f, "a {kind:?} node is not a token"),
182            Self::NoParent => f.write_str("the stream root cannot be removed or given siblings"),
183            Self::NotSiblings => f.write_str("the range ends are not siblings in order"),
184            Self::Position { position, len } => {
185                write!(f, "position {position} is past the end ({len})")
186            }
187            Self::ReadOnly { kind } => write!(f, "a {kind:?} cannot be edited this way"),
188            Self::Misplaced { kind, parent } => {
189                write!(f, "a {kind:?} cannot be a child of a {parent:?}")
190            }
191            Self::TagContext => f.write_str(
192                "the fragment's tags were resolved under other %TAG directives than the target \
193                 document's",
194            ),
195            Self::InvalidToken { kind } => {
196                write!(f, "the text does not read as exactly one {kind:?} token")
197            }
198            Self::Syntax { code } => write!(f, "the fragment text does not parse: {code}"),
199            Self::EmptyFragment => f.write_str("an empty fragment cannot be inserted"),
200            Self::NotWellFormed => f.write_str(
201                "the edit is not well-formed: its text would not read back as the edited tree",
202            ),
203            Self::Limit { code } => write!(f, "the edit would exceed a limit of the tree ({code})"),
204            Self::Capacity => f.write_str("the tree's element or byte capacity is exhausted"),
205            Self::Internal => f.write_str("internal error in the syntax tree (a bug)"),
206        }
207    }
208}
209
210impl std::error::Error for TreeEditError {}
211
212impl From<StaleNode> for TreeEditError {
213    fn from(s: StaleNode) -> Self {
214        Self::Stale(s)
215    }
216}
217
218/// The top-level elements an insertion added, first and last (the same
219/// for a one-root fragment).
220#[non_exhaustive]
221#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
222pub struct Inserted {
223    /// The first inserted top-level element.
224    pub first: NodeId,
225    /// The last inserted top-level element.
226    pub last: NodeId,
227}
228
229/// What a replacement removed and what it inserted.
230#[non_exhaustive]
231#[must_use = "the removed elements are only kept in `removed`"]
232#[derive(Clone, Debug, PartialEq, Eq, Hash)]
233pub struct Replaced {
234    /// The elements removed, as a detached fragment.
235    pub removed: Fragment,
236    /// The elements inserted in their place.
237    pub inserted: Inserted,
238}
239
240/// Overridden structural links of one slot (`NONE` = none).
241#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
242pub(super) struct Links {
243    first: u32,
244    last: u32,
245    next: u32,
246    prev: u32,
247}
248
249/// An inserted arena (its first slot is its key in [`Edits::arenas`]).
250#[derive(Clone, Debug)]
251pub(super) struct Grafted {
252    /// Slot of the parent of the arena's roots.
253    parent: u32,
254    arena: Arena,
255    /// Facts about its roots when they are stream children (`facts.rs`).
256    facts: StreamFacts,
257    /// Its comment-run index (`runs.rs`).
258    runs: RunFacts,
259}
260
261/// The edit overlay (see the module docs). Plain data: reads never
262/// change it.
263#[derive(Clone, Debug)]
264pub(super) struct Edits {
265    /// The inserted arenas that some run still covers, by first slot (a
266    /// run's `arena`). Memory retained after edits stays
267    /// within budget: an arena no run covers any more
268    /// is dropped once the edit that removed its last run is accepted, with
269    /// the link overrides of every slot that edit removed, so what the
270    /// overlay retains follows the text in the tree, not the edit history.
271    /// A slot of a dropped arena resolves to nothing (stale), never to a
272    /// stub; [`SyntaxTree::fork`] and `Clone` copy only these.
273    ///
274    /// The map names each arena's index in `grafts`, where it
275    /// is kept; a run carries that index too (`Run::graft`), so a read
276    /// reaches a run's arena in O(1), never through this map.
277    arenas: BTreeMap<u32, u32>,
278    /// The inserted arenas by index (`slab.rs`: O(1) access,
279    /// entries never move; the first few inside the overlay's
280    /// box, so a few arenas allocate nothing beyond their own data); free
281    /// entries are reused, and the slab is compacted when they outnumber
282    /// the live arenas and a quarter of the treap's items
283    /// (`Edits::drop_graft`), so it holds what the tree holds, not the
284    /// edit history.
285    grafts: Slab<Grafted>,
286    seq: Seq,
287    /// First slot of each run → its item in `seq`.
288    runs: BTreeMap<u32, u32>,
289    /// Link overrides of live slots (those of removed slots are dropped
290    /// when the removal is accepted).
291    links: BTreeMap<u32, Links>,
292    /// Warnings that left the tree with the text their labels are in
293    /// while the element they are attached to stayed (finding
294    /// 7: a `Y0028` of a replaced lenient value, attached to the line
295    /// break after it): `(slot, n)`, the `n`-th diagnostic attached to
296    /// live `slot`. Every diagnostic read skips them; empty (no
297    /// allocation) unless such an edit was made, and entries of removed
298    /// slots are dropped with them. Arenas stay immutable and every
299    /// handle keeps resolving (edits never invalidate
300    /// handles of untouched elements).
301    dropped: BTreeSet<(u32, u32)>,
302    next_slot: u32,
303}
304
305impl Edits {
306    /// The first slot the next insertion takes.
307    pub(super) const fn next_slot(&self) -> u32 {
308        self.next_slot
309    }
310
311    /// The first slot of item `item`'s run (a run's `arena` is its arena's
312    /// first slot, 0 for the base).
313    fn run_start(&self, item: u32) -> Option<u32> {
314        let run = self.seq.run(item)?;
315        run.arena.checked_add(run.a)
316    }
317
318    /// An **estimate** of the heap bytes the overlay holds, computed from
319    /// its containers' sizes and capacities. It is
320    /// complete: the treap, the run and link maps,
321    /// the dropped-warning set, and every inserted arena with the heap
322    /// inside its diagnostics (messages, labels, help, path, suggestions).
323    /// It is an estimate because B-tree nodes are counted at their
324    /// entries' size plus 16 bytes of overhead each, and a stream facts
325    /// table at its entries. An exact count needs a counting global
326    /// allocator; our crates forbid `unsafe`, but a dev-dependency may
327    /// provide one (as `allocation-counter` does for the `oracles`
328    /// crate's `ser_allocations` test); this crate does not use one.
329    #[cfg(test)]
330    pub(super) fn heap_bytes(&self) -> usize {
331        use core::mem::size_of;
332        let entry = |k: usize, v: usize| k.saturating_add(v).saturating_add(16);
333        let times = |n: usize, each: usize| n.saturating_mul(each);
334        let mut parts = vec![
335            self.seq.heap_bytes(),
336            times(self.runs.len(), entry(4, 4)),
337            times(self.links.len(), entry(4, size_of::<Links>())),
338            times(self.dropped.len(), entry(8, 0)),
339            times(self.arenas.len(), entry(4, 4)),
340            self.grafts.heap_bytes(),
341        ];
342        for g in self.grafts.iter() {
343            let a = &g.arena;
344            parts.extend([
345                a.source.capacity(),
346                a.kinds.capacity(),
347                times(a.parents.capacity(), 4),
348                times(a.words.capacity(), 4),
349                times(a.extras.capacity(), size_of::<(u32, Extra)>()),
350                times(a.diagnostics.capacity(), size_of::<(u32, Stored)>()),
351                g.facts.heap_bytes(),
352                g.runs.heap_bytes(),
353            ]);
354            parts.extend(
355                a.diagnostics
356                    .iter()
357                    .map(|(_, d)| d.heap_bytes(diagnostic_heap_bytes)),
358            );
359        }
360        parts.into_iter().fold(0, usize::saturating_add)
361    }
362
363    /// Some run covers a slot in `lo..hi` (runs never overlap in slot
364    /// space, so only the last run starting below `hi` can). O(log R).
365    pub(super) fn live_in(&self, lo: u32, hi: u32) -> bool {
366        let Some((&start, &item)) = self.runs.range(..hi).next_back() else {
367            return false;
368        };
369        let count = self.seq.run(item).map_or(0, |r| r.b.saturating_sub(r.a));
370        start.saturating_add(count) > lo
371    }
372
373    /// After an accepted edit, drops what only its
374    /// removed slots used: their link overrides, and each inserted arena
375    /// no run covers any more. O((k + 1) log L) per removed run, for the k
376    /// overrides it drops (each dropped once), plus O(log R) per arena.
377    fn release(&mut self, doomed: &[(u32, Run)]) {
378        for &(key, run) in doomed {
379            let end = key.saturating_add(run.b.saturating_sub(run.a));
380            let dead: Vec<u32> = self.links.range(key..end).map(|(s, _)| *s).collect();
381            for s in dead {
382                self.links.remove(&s);
383            }
384            if !self.dropped.is_empty() {
385                let gone: Vec<(u32, u32)> =
386                    self.dropped.range((key, 0)..(end, 0)).copied().collect();
387                for d in gone {
388                    self.dropped.remove(&d);
389                }
390            }
391            if run.arena == 0 {
392                continue;
393            }
394            let len = self.graft(run.arena).map_or(0, |g| g.arena.kinds.len());
395            let limit = u32::try_from(len)
396                .ok()
397                .and_then(|l| run.arena.checked_add(l))
398                .unwrap_or(NONE);
399            if self.runs.range(run.arena..limit).next().is_none() {
400                self.drop_graft(run.arena, true);
401            }
402        }
403    }
404
405    /// The inserted arena whose first slot is `first`. O(log A).
406    fn graft(&self, first: u32) -> Option<&Grafted> {
407        cost::count(cost::Step::Lookup);
408        let at = *self.arenas.get(&first)?;
409        self.graft_at(at)
410    }
411
412    /// The inserted arena at index `at` of the slab (`Run::graft`). O(1).
413    fn graft_at(&self, at: u32) -> Option<&Grafted> {
414        self.grafts.get(at)
415    }
416
417    /// Keeps `g` as the arena whose first slot is `first`; returns its
418    /// index (a free entry's, else a new one), or `None` (`g` dropped,
419    /// nothing else changed) when the index space is exhausted.
420    fn add_graft(&mut self, first: u32, g: Grafted) -> Option<u32> {
421        let at = self.grafts.insert(g)?;
422        self.arenas.insert(first, at);
423        Some(at)
424    }
425
426    /// Drops the arena whose first slot is `first`. With `compact` (an
427    /// accepted edit's release), a slab whose free entries outnumber
428    /// `max(16, live arenas, treap items / 4)` is compacted and every run
429    /// renumbered. Edit cost is independent of edit
430    /// history): a compaction visits the slab's entries (live + free) and
431    /// the treap's items, and since the last one at least as many entries
432    /// were freed as a quarter of what it visits, each by an accepted edit
433    /// (at most a few per edit), so it costs amortised O(1) per edit,
434    /// however many runs base removals left. The free entries it leaves are
435    /// bounded by the live arenas and runs, never by the history. An undo
436    /// never compacts, since the runs its record puts back carry the
437    /// indices they had.
438    fn drop_graft(&mut self, first: u32, compact: bool) {
439        let Some(at) = self.arenas.remove(&first) else {
440            return;
441        };
442        let _ = self.grafts.remove(at);
443        let free = self.grafts.free_len();
444        let bound = self.arenas.len().max(16).max(self.seq.items_len() / 4);
445        if compact && free > bound {
446            let (grafts, map) = std::mem::take(&mut self.grafts).compacted();
447            self.grafts = grafts;
448            for at in self.arenas.values_mut() {
449                if let Some(&n) = map.get(*at as usize) {
450                    *at = n;
451                }
452            }
453            self.seq.remap_grafts(&map);
454        }
455    }
456
457    /// Merges the run starting at `slot` into the run before it when the
458    /// two are one contiguous range of the same arena. O(log R).
459    fn merge_at(&mut self, slot: u32) {
460        let Some(&item) = self.runs.get(&slot) else {
461            return;
462        };
463        let (Some(right), Some(left_item)) = (self.seq.run(item), self.seq.prev(item)) else {
464            return;
465        };
466        let Some(left) = self.seq.run(left_item) else {
467            return;
468        };
469        if left.arena == right.arena && left.b == right.a {
470            // The halves' marks composed (exactly the marks of
471            // the merged range: summaries compose, `runs.rs`).
472            let marks = left.marks.then(right.marks);
473            let merged = Run {
474                b: right.b,
475                bytes: left.bytes.saturating_add(right.bytes),
476                diags: left.diags.saturating_add(right.diags),
477                trivia: left.trivia && right.trivia,
478                marks,
479                ..left
480            };
481            self.seq.set_run(left_item, merged);
482            self.seq.remove(item);
483            self.runs.remove(&slot);
484        }
485    }
486}
487
488/// A step of a walk over stream-level trivia (see
489/// [`SyntaxTree::jump_trivia`]).
490pub(super) enum Jump {
491    /// Go on one element at a time.
492    Step,
493    /// Every stream child up to this one (`None`: the end) is trivia.
494    Past(Option<u32>),
495}
496
497/// What a splice changed, to put it back if the edit is refused (never a
498/// panic: a refused edit changes nothing).
499#[derive(Default)]
500struct Undo {
501    /// The overlay was created by this edit: drop it.
502    created: bool,
503    /// The run before the removed runs, by its first slot (`None`: the
504    /// front). Runs are named by slot, never by treap item, so
505    /// the record stays exact across later edits that were undone (their
506    /// undo re-inserts runs as new items) inside an edit group.
507    after: Option<u32>,
508    /// The removed runs, in order, with their first slots.
509    doomed: Vec<(u32, Run)>,
510    /// The inserted fragment's first slot (its run's key).
511    grafted: Option<u32>,
512    arena_pushed: bool,
513    next_slot: u32,
514    /// Link overrides before the edit (`None`: there was none).
515    links: Vec<(u32, Option<Links>)>,
516    /// Slots at which this edit split a run in two (merged
517    /// back when the edit is refused, so R does not grow with refusals).
518    cuts: Vec<u32>,
519    /// The document and error counts before the edit.
520    documents: usize,
521    errors: usize,
522    /// Warnings this edit dropped.
523    dropped: Vec<(u32, u32)>,
524}
525
526/// The open edit groups of a tree: their accepted edits, each
527/// with the seams it left, oldest first.
528#[derive(Default)]
529pub(super) struct Group {
530    depth: usize,
531    log: Vec<(Undo, Vec<u32>)>,
532}
533
534/// The mark of an open edit group ([`SyntaxTree::begin_group`]): pass it
535/// to [`SyntaxTree::end_group`] or [`SyntaxTree::rollback_group`].
536#[must_use = "an edit group is closed with end_group or rollback_group"]
537#[derive(Clone, Copy, Debug, PartialEq, Eq)]
538pub struct GroupMark {
539    /// The stamp of the tree the group was opened on (a mark of
540    /// another tree is refused, whatever its depth).
541    tree: u64,
542    at: usize,
543    depth: usize,
544}
545
546/// Where a slot lives.
547#[derive(Clone, Copy)]
548pub(super) struct Loc<'a> {
549    pub(super) local: usize,
550    pub(super) flat: Flat<'a>,
551    /// Slot of local index 0.
552    first: u32,
553    /// Slot of the roots' parent (`NONE` for the base).
554    attach: u32,
555}
556
557impl Loc<'_> {
558    fn slot(&self, local: usize) -> Option<u32> {
559        u32::try_from(local)
560            .ok()
561            .and_then(|l| self.first.checked_add(l))
562    }
563}
564
565/// A diagnostic met by [`SyntaxTree::scan_diagnostics`]: its element's
566/// start in the current text, and the shift (`from` → `to`) that
567/// moves its spans there.
568pub(super) struct DiagAt<'a> {
569    /// The element's rank (preorder index) in the current tree.
570    pub(super) rank: u64,
571    pub(super) start: u64,
572    pub(super) diagnostic: &'a Stored,
573    pub(super) from: usize,
574    pub(super) to: usize,
575}
576
577/// What [`SyntaxTree::splice`] removed, and the first and last inserted
578/// top-level slots.
579pub(super) type Spliced = (Option<Fragment>, Option<(u32, u32)>);
580
581/// One splice of [`SyntaxTree::splice_pair`]: under `parent`, after
582/// `prev`, remove the siblings `removed` and insert `fragment`.
583pub(super) struct SpliceArgs {
584    pub(super) parent: u32,
585    pub(super) prev: Option<u32>,
586    pub(super) removed: Vec<u32>,
587    pub(super) fragment: Option<Fragment>,
588}
589
590/// What the well-formedness check of an applied splice needs.
591struct Check {
592    parent: u32,
593    prev: Option<u32>,
594    next: Option<u32>,
595    what: Removed,
596}
597
598/// An applied, not yet validated splice.
599struct Applied {
600    taken: Option<Fragment>,
601    span: Option<(u32, u32)>,
602    undo: Undo,
603    check: Check,
604}
605
606/// Where a splice goes, read before anything changes.
607#[derive(Clone, Copy)]
608struct Plan {
609    parent: u32,
610    prev: Option<u32>,
611    next: Option<u32>,
612    /// Insertion goes right before `cut` (`None`: at the very end).
613    cut: Option<u32>,
614    /// The first slot of the inserted arena.
615    new_first: Option<u32>,
616}
617
618/// Token kinds whose text [`SyntaxTree::replace_token`] replaces.
619const REPLACEABLE: &[SyntaxKind] = &[
620    SyntaxKind::PlainScalar,
621    SyntaxKind::SingleQuotedScalar,
622    SyntaxKind::DoubleQuotedScalar,
623    SyntaxKind::AliasName,
624    SyntaxKind::Anchor,
625    SyntaxKind::Comment,
626    SyntaxKind::Whitespace,
627    SyntaxKind::LineBreak,
628];
629
630const fn is_directive(k: SyntaxKind) -> bool {
631    matches!(
632        k,
633        SyntaxKind::YamlDirective | SyntaxKind::TagDirective | SyntaxKind::ReservedDirective
634    )
635}
636
637/// Tokens whose meaning is carried by their node's event data (the
638/// the extras), so they move only with their node.
639const fn is_node_property(k: SyntaxKind) -> bool {
640    matches!(k, SyntaxKind::Tag | SyntaxKind::BlockScalarHeader)
641}
642
643impl SyntaxTree {
644    // ============================================================ access
645
646    pub(super) fn base_flat(&self) -> Flat<'_> {
647        Flat {
648            source: &self.source,
649            tiled: self.source.len(),
650            kinds: &self.kinds,
651            parents: &self.parents,
652            words: &self.words,
653            wraps: &self.wraps,
654            extras: &self.extras,
655            diagnostics: &self.diagnostics,
656        }
657    }
658
659    /// The number of error-severity diagnostics in the tree, kept up to
660    /// date by every edit (O(1)). Accepted edits never change it
661    /// (they neither create nor remove an error region); a caller that
662    /// derives state from the errors can check that here.
663    #[must_use]
664    pub const fn error_count(&self) -> usize {
665        self.errors
666    }
667
668    /// `true` once an edit has been applied.
669    #[must_use]
670    pub fn is_edited(&self) -> bool {
671        self.edits.is_some()
672    }
673
674    /// Where `slot` lives (live or not). Inline, so a caller reading one
675    /// field of a base slot's place builds only that (out of
676    /// line, every call built the whole `Loc`).
677    #[inline]
678    pub(super) fn locate(&self, slot: u32) -> Option<Loc<'_>> {
679        if (slot as usize) < self.kinds.len() {
680            return Some(Loc {
681                local: slot as usize,
682                flat: self.base_flat(),
683                first: 0,
684                attach: NONE,
685            });
686        }
687        self.locate_grafted(slot)
688    }
689
690    /// [`SyntaxTree::locate`] for a slot past the base: through the arena
691    /// map. O(log A).
692    #[inline]
693    fn locate_grafted(&self, slot: u32) -> Option<Loc<'_>> {
694        let e = self.edits.as_deref()?;
695        // A slot of a dropped arena falls in no arena's range (or
696        // past the end of an earlier one): nothing, never a stub.
697        cost::count(cost::Step::Lookup);
698        let (&first, &at) = e.arenas.range(..=slot).next_back()?;
699        let ins = e.graft_at(at)?;
700        let local = slot.checked_sub(first)? as usize;
701        (local < ins.arena.kinds.len()).then(|| Loc {
702            local,
703            flat: ins.arena.flat(),
704            first,
705            attach: ins.parent,
706        })
707    }
708
709    /// The stream facts of `slot`'s arena, `slot`'s local index there, and
710    /// the slot of local index 0 (`facts.rs`). O(log arenas).
711    pub(super) fn facts_at(&self, slot: u32) -> Option<(&StreamFacts, usize, u32)> {
712        if (slot as usize) < self.kinds.len() {
713            return Some((&self.facts, slot as usize, 0));
714        }
715        let e = self.edits.as_deref()?;
716        cost::count(cost::Step::Lookup);
717        let (&first, &at) = e.arenas.range(..=slot).next_back()?;
718        let ins = e.graft_at(at)?;
719        let local = slot.checked_sub(first)? as usize;
720        (local < ins.arena.kinds.len()).then_some((&ins.facts, local, first))
721    }
722
723    /// For a live stream-level trivia token `p` inside a long run of its
724    /// arena (`facts.rs`): the first element of that run that is still
725    /// contiguous with `p` in the tree's order (the run's start, or the
726    /// start of the overlay run holding `p`); else `p`. Every element
727    /// from there to `p` is a stream-level trivia token, and they are
728    /// consecutive siblings (inside one overlay run the arena's order and
729    /// links hold). O(log R + log runs).
730    pub(super) fn trivia_run_start(&self, p: u32) -> u32 {
731        let Some((facts, local, first)) = self.facts_at(p) else {
732            return p;
733        };
734        let Some(a) = facts.run_start(local) else {
735            return p;
736        };
737        let lo = match self.run_item(p) {
738            Some((_, run, _)) => a.max(run.a as usize),
739            None if self.edits.is_none() => a,
740            None => return p,
741        };
742        u32::try_from(lo)
743            .ok()
744            .and_then(|l| first.checked_add(l))
745            .filter(|s| *s <= p)
746            .unwrap_or(p)
747    }
748
749    /// For a live stream-level trivia token `p` inside a long run of its
750    /// arena: the last element of that run still contiguous with `p` in
751    /// the tree's order (the run's end, or the end of the overlay run
752    /// holding `p`); else `p`. The mirror of
753    /// [`SyntaxTree::trivia_run_start`].
754    pub(super) fn trivia_run_end(&self, p: u32) -> u32 {
755        let Some((facts, local, first)) = self.facts_at(p) else {
756            return p;
757        };
758        let Some(b) = facts.run_end(local) else {
759            return p;
760        };
761        let hi = match self.run_item(p) {
762            Some((_, run, _)) => b.min((run.b as usize).saturating_sub(1)),
763            None if self.edits.is_none() => b,
764            None => return p,
765        };
766        u32::try_from(hi)
767            .ok()
768            .and_then(|h| first.checked_add(h))
769            .filter(|s| *s >= p)
770            .unwrap_or(p)
771    }
772
773    /// For stream-level trivia token `s` at the start (`forward`: the end)
774    /// of its overlay run, when the run before (after) it is all
775    /// stream-level trivia: the stream child past every such run in that
776    /// direction, found by the treap's sums in O(log R). The
777    /// runs skipped hold only stream-level trivia tokens, so they are
778    /// consecutive stream children, and the element next to them is the
779    /// last element of a stream child (backwards: climbed to it, O(depth))
780    /// or a stream child (forwards: the first element after a stream-level
781    /// token).
782    pub(super) fn jump_trivia(&self, s: u32, forward: bool) -> Result<Jump, TreeEditError> {
783        let Some(e) = self.edits.as_deref() else {
784            return Ok(Jump::Step);
785        };
786        let (item, run, start) = self.run_item(s).ok_or(TreeEditError::Internal)?;
787        let at_edge = if forward {
788            run.b
789                .checked_sub(run.a)
790                .and_then(|n| start.checked_add(n))
791                .and_then(|end| end.checked_sub(1))
792                == Some(s)
793        } else {
794            start == s
795        };
796        let neighbour = if forward {
797            e.seq.next(item)
798        } else {
799            e.seq.prev(item)
800        };
801        let trivia_next = neighbour
802            .and_then(|n| e.seq.run(n))
803            .is_some_and(|r| r.trivia);
804        if !at_edge || !trivia_next {
805            return Ok(Jump::Step);
806        }
807        let solid = if forward {
808            e.seq.next_solid(item)
809        } else {
810            e.seq.prev_solid(item)
811        };
812        let Some(j) = solid else {
813            return Ok(Jump::Past(None));
814        };
815        let r = e.seq.run(j).ok_or(TreeEditError::Internal)?;
816        if forward {
817            let first = r.arena.checked_add(r.a).ok_or(TreeEditError::Internal)?;
818            return Ok(Jump::Past(Some(first)));
819        }
820        let mut y =
821            r.b.checked_sub(1)
822                .and_then(|l| r.arena.checked_add(l))
823                .ok_or(TreeEditError::Internal)?;
824        // A loop up the parents. The stream root itself (a run that
825        // ends with it): the trivia are the stream's first children.
826        loop {
827            match self.nav_parent(y) {
828                Some(0) => return Ok(Jump::Past(Some(y))),
829                Some(p) => y = p,
830                None if y == 0 => return Ok(Jump::Past(None)),
831                None => return Err(TreeEditError::Internal),
832            }
833        }
834    }
835
836    /// Local elements `a..b` of arena `arena` are all stream-level trivia
837    /// tokens. O(`LONG_RUN` + log): a longer range is one only
838    /// inside a long run its arena's facts record.
839    fn stream_trivia(&self, arena: u32, a: u32, b: u32) -> bool {
840        let Some((flat, _, attach)) = self.arena_flat(arena) else {
841            return false;
842        };
843        let facts = if arena == 0 {
844            &self.facts
845        } else {
846            match self.edits.as_deref().and_then(|e| e.graft(arena)) {
847                Some(g) => &g.facts,
848                None => return false,
849            }
850        };
851        (arena == 0 || attach == 0) && all_stream_trivia(flat, facts, arena == 0, a, b)
852    }
853
854    /// The comment-run marks of local elements `a..b` of arena `arena`
855    /// (`runs.rs`).
856    fn run_marks(&self, arena: u32, a: u32, b: u32) -> Marks {
857        match self.arena_index(arena) {
858            Some((flat, rf)) => marks(flat, rf, self.stream_facts_of(arena), a, b),
859            // (Unreachable: a run's arena is live. Marks that claim content
860            // make every search look inside, never skip it.)
861            None => Marks::CONTENT,
862        }
863    }
864
865    /// Arena `arena`'s elements and comment-run index (`runs.rs`).
866    pub(super) fn arena_index(&self, arena: u32) -> Option<(Flat<'_>, &RunFacts)> {
867        if arena == 0 {
868            return Some((self.base_flat(), &self.run_facts));
869        }
870        let g = self.edits.as_deref()?.graft(arena)?;
871        Some((g.arena.flat(), &g.runs))
872    }
873
874    /// Arena `arena`'s stream facts, when its roots are stream-level (the
875    /// base, or a fragment inserted into the stream).
876    pub(super) fn stream_facts_of(&self, arena: u32) -> Option<&StreamFacts> {
877        if arena == 0 {
878            return Some(&self.facts);
879        }
880        let g = self.edits.as_deref()?.graft(arena)?;
881        (g.parent == 0).then_some(&g.facts)
882    }
883
884    /// The piece of the tree's order holding `slot`, and `slot`'s local
885    /// index there (`runs.rs`). O(log R).
886    pub(super) fn piece_at(&self, slot: u32) -> Option<(Piece, u32)> {
887        if self.edits.is_none() {
888            let len = u32::try_from(self.kinds.len()).ok()?;
889            let p = Piece {
890                arena: 0,
891                a: 0,
892                b: len,
893                item: None,
894            };
895            return (slot < len).then_some((p, slot));
896        }
897        let (item, run, start) = self.run_item(slot)?;
898        let local = run.a.checked_add(slot.checked_sub(start)?)?;
899        let p = Piece {
900            arena: run.arena,
901            a: run.a,
902            b: run.b,
903            item: Some(item),
904        };
905        Some((p, local))
906    }
907
908    /// The piece of overlay item `item`.
909    fn piece_of_item(&self, item: u32) -> Option<Piece> {
910        let run = self.edits.as_deref()?.seq.run(item)?;
911        Some(Piece {
912            arena: run.arena,
913            a: run.a,
914            b: run.b,
915            item: Some(item),
916        })
917    }
918
919    /// The first piece after item `item` that holds a content token or
920    /// may hold an own-line comment at a column below `v`. O(log R).
921    pub(super) fn piece_after(&self, item: u32, v: u32) -> Option<Piece> {
922        let next = self.edits.as_deref()?.seq.next_low(item, v)?;
923        self.piece_of_item(next)
924    }
925
926    /// The last piece before item `item` that holds a content token.
927    /// O(log R).
928    pub(super) fn piece_visible_before(&self, item: u32) -> Option<Piece> {
929        let prev = self.edits.as_deref()?.seq.prev_visible(item)?;
930        self.piece_of_item(prev)
931    }
932
933    /// The nearest piece after (`forward`) or before item `item` holding
934    /// an element that is not a trivia token. O(log R).
935    pub(super) fn piece_firm(&self, item: u32, forward: bool) -> Option<Piece> {
936        let at = self.edits.as_deref()?.seq.near_firm(item, forward)?;
937        self.piece_of_item(at)
938    }
939
940    /// The nearest piece after (`forward`) or before item `item` holding a
941    /// stream-level document. O(log R).
942    pub(super) fn piece_docs(&self, item: u32, forward: bool) -> Option<Piece> {
943        let e = self.edits.as_deref()?;
944        let at = if forward {
945            e.seq.next_docs(item)?
946        } else {
947            e.seq.prev_docs(item)?
948        };
949        self.piece_of_item(at)
950    }
951
952    fn arena_flat(&self, id: u32) -> Option<(Flat<'_>, u32, u32)> {
953        if id == 0 {
954            return Some((self.base_flat(), 0, NONE));
955        }
956        let e = self.edits.as_deref()?;
957        let ins = e.graft(id)?;
958        Some((ins.arena.flat(), id, ins.parent))
959    }
960
961    /// The arena of `run` (O(1)): its elements, its first slot,
962    /// and the slot of its roots' parent (`NONE` for the base).
963    pub(super) fn run_flat(&self, run: &Run) -> Option<(Flat<'_>, u32, u32)> {
964        self.graft_flat(run.arena, run.graft)
965    }
966
967    /// The arena whose first slot is `arena` and whose slab index is
968    /// `graft` (O(1)): its elements, first slot, and roots' parent slot.
969    #[inline(always)]
970    fn graft_flat(&self, arena: u32, graft: u32) -> Option<(Flat<'_>, u32, u32)> {
971        if arena == 0 {
972            return Some((self.base_flat(), 0, NONE));
973        }
974        let ins = self.edits.as_deref()?.graft_at(graft)?;
975        Some((ins.arena.flat(), arena, ins.parent))
976    }
977
978    /// The run covering `slot`: (item, run, slot of the run's first element).
979    pub(super) fn run_item(&self, slot: u32) -> Option<(u32, Run, u32)> {
980        let e = self.edits.as_deref()?;
981        cost::count(cost::Step::Lookup);
982        let (&start, &item) = e.runs.range(..=slot).next_back()?;
983        let run = e.seq.run(item)?;
984        let count = run.b.checked_sub(run.a)?;
985        (slot < start.checked_add(count)?).then_some((item, run, start))
986    }
987
988    /// `true` when `slot` names a live element.
989    pub(super) fn is_live(&self, slot: u32) -> bool {
990        if self.edits.is_none() {
991            return (slot as usize) < self.kinds.len();
992        }
993        self.run_item(slot).is_some()
994    }
995
996    pub(super) fn kind_of(&self, slot: u32) -> Option<SyntaxKind> {
997        let loc = self.locate(slot)?;
998        loc.flat.kind(loc.local)
999    }
1000
1001    // ======================================================== navigation
1002
1003    /// All four links of `slot` as its arena has them. O(depth): only for
1004    /// edits, never on a read path.
1005    fn default_links(loc: &Loc<'_>) -> Links {
1006        let f = &loc.flat;
1007        let l = loc.local;
1008        let s = |x: Option<usize>| x.and_then(|x| loc.slot(x)).unwrap_or(NONE);
1009        Links {
1010            first: s(f.first_child(l)),
1011            last: s(f.last_child(l)),
1012            next: s(f.next_sibling(l)),
1013            prev: s(f.prev_sibling(l)),
1014        }
1015    }
1016
1017    fn override_of(&self, slot: u32) -> Option<&Links> {
1018        let e = self.edits.as_deref()?;
1019        cost::count(cost::Step::Lookup);
1020        e.links.get(&slot)
1021    }
1022
1023    /// All four links of `slot` (for an edit to change one of them).
1024    fn links_of(&self, slot: u32) -> Links {
1025        if let Some(l) = self.override_of(slot) {
1026            return *l;
1027        }
1028        self.locate(slot).map_or(
1029            Links {
1030                first: NONE,
1031                last: NONE,
1032                next: NONE,
1033                prev: NONE,
1034            },
1035            |loc| Self::default_links(&loc),
1036        )
1037    }
1038
1039    fn some(x: u32) -> Option<u32> {
1040        (x != NONE).then_some(x)
1041    }
1042
1043    /// One link: the override if an edit set one, else what the arena
1044    /// says. Only the link asked for is computed, so the O(1) links
1045    /// stay O(1) (finding: computing all four made every step O(depth)).
1046    fn nav_link(
1047        &self,
1048        slot: u32,
1049        pick: fn(&Links) -> u32,
1050        local: impl FnOnce(&Flat<'_>, usize) -> Option<usize>,
1051    ) -> Option<u32> {
1052        if let Some(l) = self.override_of(slot) {
1053            return Self::some(pick(l));
1054        }
1055        let loc = self.locate(slot)?;
1056        local(&loc.flat, loc.local).and_then(|x| loc.slot(x))
1057    }
1058
1059    pub(super) fn nav_parent(&self, slot: u32) -> Option<u32> {
1060        if (slot as usize) < self.kinds.len() {
1061            // A base element's parent is its base parent.
1062            return self
1063                .parent_of(slot as usize)
1064                .and_then(|p| u32::try_from(p).ok());
1065        }
1066        let loc = self.locate(slot)?;
1067        match loc.flat.parent(loc.local) {
1068            Some(p) => loc.slot(p),
1069            None => Self::some(loc.attach),
1070        }
1071    }
1072
1073    /// O(1) (plus O(log) to find an override).
1074    pub(super) fn nav_first(&self, slot: u32) -> Option<u32> {
1075        self.nav_link(slot, |l| l.first, |f, i| f.first_child(i))
1076    }
1077
1078    /// O(depth), as in an unedited tree.
1079    pub(super) fn nav_last(&self, slot: u32) -> Option<u32> {
1080        self.nav_link(slot, |l| l.last, |f, i| f.last_child(i))
1081    }
1082
1083    /// O(1) (plus O(log) to find an override).
1084    pub(super) fn nav_next(&self, slot: u32) -> Option<u32> {
1085        self.nav_link(slot, |l| l.next, |f, i| f.next_sibling(i))
1086    }
1087
1088    /// O(depth), as in an unedited tree.
1089    pub(super) fn nav_prev(&self, slot: u32) -> Option<u32> {
1090        self.nav_link(slot, |l| l.prev, |f, i| f.prev_sibling(i))
1091    }
1092
1093    /// The next element in preorder. O(1), O(log R) across runs.
1094    pub(super) fn nav_succ(&self, slot: u32) -> Option<u32> {
1095        let Some(e) = self.edits.as_deref() else {
1096            let n = slot.checked_add(1)?;
1097            return ((n as usize) < self.kinds.len()).then_some(n);
1098        };
1099        let (item, run, start) = self.run_item(slot)?;
1100        let n = slot.checked_add(1)?;
1101        if n < start.checked_add(run.b.checked_sub(run.a)?)? {
1102            return Some(n);
1103        }
1104        let next = e.seq.next(item)?;
1105        let r = e.seq.run(next)?;
1106        let first = r.arena;
1107        first.checked_add(r.a)
1108    }
1109
1110    /// The previous element in preorder. O(1), O(log R) across runs.
1111    pub(super) fn nav_pred(&self, slot: u32) -> Option<u32> {
1112        let Some(e) = self.edits.as_deref() else {
1113            return slot.checked_sub(1);
1114        };
1115        let (item, _, start) = self.run_item(slot)?;
1116        if slot > start {
1117            return slot.checked_sub(1);
1118        }
1119        let prev = e.seq.prev(item)?;
1120        let r = e.seq.run(prev)?;
1121        let first = r.arena;
1122        first.checked_add(r.b.checked_sub(1)?)
1123    }
1124
1125    // ================================================ hinted reads
1126    //
1127    // A `Node` of an edited tree carries the treap item of
1128    // its run as a **hint**. A `Node` borrows its tree immutably, so the
1129    // overlay cannot change while the hint exists; it is checked anyway
1130    // (O(1)), and a hint that does not cover the slot is looked up again.
1131    // With the run at hand, a step that stays inside the run is the
1132    // arena's own O(1) arithmetic (`Flat`), with no map lookup. Why this
1133    // is exact is structural: parents are always the arena's
1134    // (`Links` has no parent field, and an edit never moves an element, it
1135    // copies it), and inside one run the tree's preorder is the arena's.
1136    // A first child is the element right after its parent in preorder when
1137    // that one is a child of it, a next sibling the element right after
1138    // its subtree when that one has the same parent, and so on: when those
1139    // elements lie in the run, the tree's link is determined by the
1140    // arena's order and parents, whatever overrides exist. (An override
1141    // may sit inside a run, e.g. after an insertion and its removal merged
1142    // the runs back; it then equals the arena's link, as every override
1143    // equals the tree's.) Only a step that leaves the run reads the link
1144    // overrides, and the next run is the treap successor (amortised O(1)
1145    // over a traversal). Sequential reads thus cost
1146    // amortised O(1) per element and O(1) lookups per run, independent of
1147    // the number of elements; the `cost` counters state it in the tests.
1148
1149    /// The run covering live `slot` and the slot of its first element:
1150    /// from `hint` in O(1) when it is that run's item, else looked up
1151    /// (O(log R)).
1152    #[inline(always)]
1153    pub(super) fn run_hinted(&self, slot: u32, hint: u32) -> Option<(RunAt, u32)> {
1154        if hint != NONE {
1155            if let Some(r) = self.edits.as_deref().and_then(|e| e.seq.at(hint)) {
1156                let start = r.arena.checked_add(r.a)?;
1157                let end = r.arena.checked_add(r.b)?;
1158                if start <= slot && slot < end {
1159                    return Some((r, start));
1160                }
1161            }
1162        }
1163        let (item, run, start) = self.run_item(slot)?;
1164        let r = RunAt {
1165            item,
1166            arena: run.arena,
1167            graft: run.graft,
1168            a: run.a,
1169            b: run.b,
1170        };
1171        Some((r, start))
1172    }
1173
1174    /// The slots `start..end` of the run of treap item `item`, or `(0,
1175    /// 0)` for none. O(1).
1176    #[inline]
1177    pub(super) fn run_slots(&self, item: u32) -> (u32, u32) {
1178        let bounds = self.edits.as_deref().and_then(|e| e.seq.bounds(item));
1179        let Some((arena, a, b)) = bounds else {
1180            return (0, 0);
1181        };
1182        match (arena.checked_add(a), arena.checked_add(b)) {
1183            (Some(s), Some(t)) => (s, t),
1184            _ => (0, 0),
1185        }
1186    }
1187
1188    /// The run after item `item`: its item and its slots `start..end`.
1189    /// Amortised O(1) over a traversal (a treap step).
1190    pub(super) fn run_after(&self, item: u32) -> Option<(u32, u32, u32)> {
1191        let next = self.edits.as_deref()?.seq.next(item)?;
1192        let (s, t) = self.run_slots(next);
1193        (t > s).then_some((next, s, t))
1194    }
1195
1196    /// For a base `slot` whose `hint` is its run's item: the run's base
1197    /// indices `a..b` (a base run's slots are its base indices).
1198    /// O(1), nothing copied.
1199    #[inline]
1200    fn base_run(&self, slot: u32, hint: u32) -> Option<(usize, usize)> {
1201        if hint == NONE || (slot as usize) >= self.kinds.len() {
1202            return None;
1203        }
1204        let (arena, a, b) = self.edits.as_deref()?.seq.bounds(hint)?;
1205        (arena == 0 && a <= slot && slot < b).then_some((a as usize, b as usize))
1206    }
1207
1208    /// The parent's slot (the base arrays for a base slot, the
1209    /// hint's arena for an inserted one; no run lookup with a hint).
1210    #[inline]
1211    pub(super) fn parent_slot(&self, slot: u32, hint: u32) -> Option<u32> {
1212        if (slot as usize) < self.kinds.len() {
1213            return self
1214                .parent_of(slot as usize)
1215                .and_then(|p| u32::try_from(p).ok());
1216        }
1217        self.nav_parent_hinted(slot, hint).map(|(p, _)| p)
1218    }
1219
1220    /// Lowers the arena slab's index space to the entries it has now plus
1221    /// `spare` (for tests: running out).
1222    #[cfg(test)]
1223    pub(super) fn limit_arenas(&mut self, spare: usize) {
1224        if let Some(e) = self.edits.as_deref_mut() {
1225            let n = e.grafts.len().saturating_add(spare);
1226            e.grafts.limit_entries(n);
1227        }
1228    }
1229
1230    /// Live inserted arenas, and free entries of the slab (for
1231    /// tests).
1232    #[cfg(test)]
1233    pub(super) fn arena_counts(&self) -> (usize, usize) {
1234        self.edits
1235            .as_deref()
1236            .map_or((0, 0), |e| (e.arenas.len(), e.grafts.free_len()))
1237    }
1238
1239    /// The element count of each run, in order, and the number of runs
1240    /// the run map names (for tests).
1241    #[cfg(test)]
1242    pub(super) fn run_lengths(&self) -> (Vec<u32>, usize) {
1243        let Some(e) = self.edits.as_deref() else {
1244            return (Vec::new(), 0);
1245        };
1246        let mut out = Vec::new();
1247        let mut at = e.seq.first();
1248        while let Some(x) = at {
1249            out.extend(e.seq.run(x).map(|r| r.b.saturating_sub(r.a)));
1250            at = e.seq.next(x);
1251        }
1252        (out, e.runs.len())
1253    }
1254
1255    /// The hint of live `slot`: its run's item (O(log R)); `NONE` for an
1256    /// unedited tree (no hint is needed there).
1257    pub(super) fn hint_of(&self, slot: u32) -> u32 {
1258        if self.edits.is_none() {
1259            return NONE;
1260        }
1261        self.run_item(slot).map_or(NONE, |(item, _, _)| item)
1262    }
1263
1264    /// Where `slot` lives in `run`'s arena. O(1).
1265    #[inline(always)]
1266    fn loc_in_run(&self, run: &RunAt, slot: u32) -> Option<Loc<'_>> {
1267        let (flat, first, attach) = self.graft_flat(run.arena, run.graft)?;
1268        Some(Loc {
1269            local: slot.checked_sub(first)? as usize,
1270            flat,
1271            first,
1272            attach,
1273        })
1274    }
1275
1276    /// [`SyntaxTree::locate`] through a hint: O(1) for a base slot (as
1277    /// always) and for an inserted slot whose hint holds it.
1278    #[inline(never)]
1279    pub(super) fn locate_hinted(&self, slot: u32, hint: u32) -> Option<Loc<'_>> {
1280        if (slot as usize) < self.kinds.len() || hint == NONE {
1281            return self.locate(slot);
1282        }
1283        match self.run_hinted(slot, hint) {
1284            Some((run, _)) => self.loc_in_run(&run, slot),
1285            None => self.locate(slot),
1286        }
1287    }
1288
1289    /// The kind of live `slot` through a hint (a base slot's from the
1290    /// base arrays, O(1)).
1291    pub(super) fn kind_hinted(&self, slot: u32, hint: u32) -> Option<SyntaxKind> {
1292        if let Some(k) = self.kind_at(slot as usize) {
1293            return Some(k);
1294        }
1295        // An inserted slot: its arena's kinds, straight from the slab.
1296        let e = self.edits.as_deref()?;
1297        if let Some(r) = e.seq.at(hint) {
1298            let start = r.arena.checked_add(r.a)?;
1299            let end = r.arena.checked_add(r.b)?;
1300            if start <= slot && slot < end {
1301                let g = e.graft_at(r.graft)?;
1302                return g
1303                    .arena
1304                    .kinds
1305                    .get(slot.checked_sub(r.arena)? as usize)
1306                    .copied();
1307            }
1308        }
1309        let loc = self.locate(slot)?;
1310        loc.flat.kind(loc.local)
1311    }
1312
1313    /// The run of live `slot` (from `hint`) with `slot`'s place in it.
1314    #[inline(always)]
1315    fn at_hinted(&self, slot: u32, hint: u32) -> Option<(u32, RunAt, Loc<'_>)> {
1316        let (run, _) = self.run_hinted(slot, hint)?;
1317        let loc = self.loc_in_run(&run, slot)?;
1318        Some((run.item, run, loc))
1319    }
1320
1321    /// The hint of `slot`, the first element of the run after item
1322    /// `item`, when that run starts with it (else `NONE`). O(1) amortised
1323    /// over a traversal (a treap step).
1324    fn hint_after(&self, item: u32, slot: u32) -> u32 {
1325        let Some(e) = self.edits.as_deref() else {
1326            return NONE;
1327        };
1328        e.seq
1329            .next(item)
1330            .filter(|n| e.run_start(*n) == Some(slot))
1331            .unwrap_or(NONE)
1332    }
1333
1334    /// The next element in preorder and its hint. O(1) inside a run; a
1335    /// treap step to the next run.
1336    pub(super) fn nav_succ_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1337        let Some(e) = self.edits.as_deref() else {
1338            return self.nav_succ(slot).map(|s| (s, NONE));
1339        };
1340        let (run, start) = self.run_hinted(slot, hint)?;
1341        let item = run.item;
1342        let n = slot.checked_add(1)?;
1343        if n < start.checked_add(run.b.checked_sub(run.a)?)? {
1344            return Some((n, item));
1345        }
1346        let next = e.seq.next(item)?;
1347        let r = e.seq.run(next)?;
1348        Some((r.arena.checked_add(r.a)?, next))
1349    }
1350
1351    /// The previous element in preorder and its hint.
1352    pub(super) fn nav_pred_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1353        let Some(e) = self.edits.as_deref() else {
1354            return self.nav_pred(slot).map(|s| (s, NONE));
1355        };
1356        let (run, start) = self.run_hinted(slot, hint)?;
1357        let item = run.item;
1358        if slot > start {
1359            return Some((slot.checked_sub(1)?, item));
1360        }
1361        let prev = e.seq.prev(item)?;
1362        let r = e.seq.run(prev)?;
1363        Some((r.arena.checked_add(r.b.checked_sub(1)?)?, prev))
1364    }
1365
1366    /// The parent and its hint (the same run when the parent lies in it).
1367    /// Without a hint, [`SyntaxTree::nav_parent`] (O(1) for a base slot).
1368    pub(super) fn nav_parent_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1369        if hint == NONE || self.edits.is_none() {
1370            return self.nav_parent(slot).map(|p| (p, NONE));
1371        }
1372        if let Some((a, _)) = self.base_run(slot, hint) {
1373            let p = self.parent_of(slot as usize)?;
1374            let h = if p >= a { hint } else { NONE };
1375            return Some((u32::try_from(p).ok()?, h));
1376        }
1377        let (item, run, loc) = self.at_hinted(slot, hint)?;
1378        match loc.flat.parent(loc.local) {
1379            // A live element's parent is live; inside the run when it lies
1380            // at or after the run's first element.
1381            Some(p) => Some((loc.slot(p)?, if p >= run.a as usize { item } else { NONE })),
1382            None => Self::some(loc.attach).map(|p| (p, NONE)),
1383        }
1384    }
1385
1386    /// The first child and its hint. O(1) unless `slot` ends its run.
1387    pub(super) fn nav_first_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1388        // Without a hint, exactly the unhinted step (no run lookup on
1389        // top of the override lookup).
1390        if self.edits.is_none() || hint == NONE {
1391            return self.nav_first(slot).map(|s| (s, NONE));
1392        }
1393        if let Some((_, b)) = self.base_run(slot, hint) {
1394            let i = slot as usize;
1395            let c = i.checked_add(1)?;
1396            if c < b {
1397                // (As below, by the base arrays.)
1398                return (c < self.end_of(i))
1399                    .then(|| u32::try_from(c).ok())
1400                    .flatten()
1401                    .map(|c| (c, hint));
1402            }
1403            // `slot` ends its run: the fallback below, without re-reading
1404            // the run.
1405            let c = self.nav_first(slot)?;
1406            return Some((c, self.hint_after(hint, c)));
1407        }
1408        let (item, run, loc) = self.at_hinted(slot, hint)?;
1409        let next = loc.local.checked_add(1)?;
1410        if next < run.b as usize {
1411            // The element after `slot` is the arena's next one: a child
1412            // exactly when the arena says so.
1413            return loc
1414                .flat
1415                .first_child(loc.local)
1416                .and_then(|c| loc.slot(c))
1417                .map(|c| (c, item));
1418        }
1419        let c = self.nav_first(slot)?;
1420        Some((c, self.hint_after(item, c)))
1421    }
1422
1423    /// The next sibling and its hint. O(1) unless `slot`'s subtree reaches
1424    /// the end of its run.
1425    pub(super) fn nav_next_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1426        // Without a hint, exactly the unhinted step (no run lookup on
1427        // top of the override lookup).
1428        if self.edits.is_none() || hint == NONE {
1429            return self.nav_next(slot).map(|s| (s, NONE));
1430        }
1431        if let Some((_, b)) = self.base_run(slot, hint) {
1432            let i = slot as usize;
1433            let after = self.end_of(i);
1434            if after < b {
1435                // (As below, by the base arrays.)
1436                let limit = self
1437                    .parent_of(i)
1438                    .map_or(self.kinds.len(), |p| self.end_of(p));
1439                return (after < limit && after > i)
1440                    .then(|| u32::try_from(after).ok())
1441                    .flatten()
1442                    .map(|s| (s, hint));
1443            }
1444            // The subtree reaches the run's end: the fallback below,
1445            // without re-reading the run.
1446            let s = self.nav_next(slot)?;
1447            let h = if after == b {
1448                self.hint_after(hint, s)
1449            } else {
1450                NONE
1451            };
1452            return Some((s, h));
1453        }
1454        let (item, run, loc) = self.at_hinted(slot, hint)?;
1455        let end = loc.flat.end(loc.local);
1456        if end < run.b as usize {
1457            // The subtree and the element after it lie in the run: the
1458            // arena's next sibling is the tree's.
1459            return loc
1460                .flat
1461                .next_sibling(loc.local)
1462                .and_then(|s| loc.slot(s))
1463                .map(|s| (s, item));
1464        }
1465        let s = self.nav_next(slot)?;
1466        // When the subtree ends the run, the next run may start with it.
1467        let h = if end == run.b as usize {
1468            self.hint_after(item, s)
1469        } else {
1470            NONE
1471        };
1472        Some((s, h))
1473    }
1474
1475    /// The previous sibling and its hint. O(depth), as unedited; no
1476    /// override lookup unless `slot` starts its run.
1477    pub(super) fn nav_prev_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1478        // Without a hint, exactly the unhinted step (no run lookup on
1479        // top of the override lookup).
1480        if self.edits.is_none() || hint == NONE {
1481            return self.nav_prev(slot).map(|s| (s, NONE));
1482        }
1483        let (item, run, loc) = self.at_hinted(slot, hint)?;
1484        if loc.local > run.a as usize {
1485            // The element before `slot` is the arena's previous one, the
1486            // last of the previous sibling's subtree (or the parent).
1487            return loc.flat.prev_sibling(loc.local).and_then(|s| {
1488                let h = if s >= run.a as usize { item } else { NONE };
1489                Some((loc.slot(s)?, h))
1490            });
1491        }
1492        self.nav_prev(slot).map(|s| (s, NONE))
1493    }
1494
1495    /// The last child and its hint. O(depth), as unedited; no override
1496    /// lookup unless `slot`'s subtree reaches the end of its run.
1497    pub(super) fn nav_last_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1498        // Without a hint, exactly the unhinted step (no run lookup on
1499        // top of the override lookup).
1500        if self.edits.is_none() || hint == NONE {
1501            return self.nav_last(slot).map(|s| (s, NONE));
1502        }
1503        let (item, run, loc) = self.at_hinted(slot, hint)?;
1504        if loc.flat.end(loc.local) < run.b as usize {
1505            return loc
1506                .flat
1507                .last_child(loc.local)
1508                .and_then(|c| loc.slot(c))
1509                .map(|c| (c, item));
1510        }
1511        self.nav_last(slot).map(|s| (s, NONE))
1512    }
1513
1514    /// (rank, byte offset) of live `slot` through a hint. O(log R) (the
1515    /// treap's prefix sums), without the run lookup.
1516    pub(super) fn nav_rank_hinted(&self, slot: u32, hint: u32) -> Option<(u64, u64)> {
1517        let Some(e) = self.edits.as_deref() else {
1518            return self.nav_rank(slot);
1519        };
1520        let (item, run, loc) = self.at_hinted(slot, hint)?;
1521        let (pc, pb) = e.seq.prefix(item);
1522        let within = u64::try_from(loc.local.checked_sub(run.a as usize)?).ok()?;
1523        let bytes = loc
1524            .flat
1525            .start(loc.local)
1526            .checked_sub(loc.flat.start(run.a as usize))?;
1527        Some((
1528            pc.checked_add(within)?,
1529            pb.checked_add(u64::try_from(bytes).ok()?)?,
1530        ))
1531    }
1532
1533    /// The span of live `slot` in the edited text, through a hint.
1534    pub(super) fn nav_span_hinted(&self, slot: u32, hint: u32) -> Span {
1535        let Some((_, start)) = self.nav_rank_hinted(slot, hint) else {
1536            return Span::empty(0);
1537        };
1538        let end = self
1539            .nav_after(slot)
1540            .and_then(|a| self.nav_rank(a))
1541            .map_or(self.nav_total().1, |(_, b)| b);
1542        let start = usize::try_from(start).unwrap_or(usize::MAX);
1543        let end = usize::try_from(end).unwrap_or(usize::MAX).max(start);
1544        Span::new(start, end)
1545    }
1546
1547    /// The text of live `slot` through a hint: a token's is borrowed from
1548    /// its arena in O(1).
1549    pub(super) fn edited_text_hinted(&self, slot: u32, hint: u32) -> Cow<'_, str> {
1550        let i = slot as usize;
1551        if self.kind_at(i).is_some_and(SyntaxKind::is_token) {
1552            // A base token's bytes are its bytes in the source.
1553            let s = self.span_of(i);
1554            return Cow::Borrowed(self.source.get(s.start..s.end).unwrap_or(""));
1555        }
1556        if let Some(loc) = self.locate_hinted(slot, hint) {
1557            if loc.flat.kind(loc.local).is_some_and(SyntaxKind::is_token) {
1558                return Cow::Borrowed(loc.flat.token_text(loc.local));
1559            }
1560        }
1561        self.edited_text(slot)
1562    }
1563
1564    /// The last element of `slot`'s subtree in preorder (itself when it
1565    /// has no children): the end of its chain of last children.
1566    /// O(log R) plus [`SyntaxTree::nav_after`]'s climb, where
1567    /// following [`SyntaxTree::nav_last`] level by level costs O(depth)
1568    /// per level, O(depth²) in all.
1569    pub(super) fn nav_last_leaf(&self, slot: u32) -> Option<u32> {
1570        if self.nav_first(slot).is_none() {
1571            return self.is_live(slot).then_some(slot);
1572        }
1573        match self.nav_after(slot) {
1574            Some(a) => self.nav_pred(a),
1575            None => match self.edits.as_deref() {
1576                None => u32::try_from(self.kinds.len().checked_sub(1)?).ok(),
1577                Some(e) => {
1578                    let r = e.seq.run(e.seq.last()?)?;
1579                    let first = r.arena;
1580                    first.checked_add(r.b.checked_sub(1)?)
1581                }
1582            },
1583        }
1584    }
1585
1586    /// The chain of last children from `slot` down: `slot`, its last
1587    /// child, that one's last child, … (O(depth + log R), see
1588    /// [`SyntaxTree::nav_last_leaf`]).
1589    pub(super) fn last_chain(&self, slot: u32) -> Vec<u32> {
1590        let mut chain = Vec::new();
1591        let Some(mut x) = self.nav_last_leaf(slot) else {
1592            chain.push(slot);
1593            return chain;
1594        };
1595        // A loop up the parents, then reversed.
1596        loop {
1597            chain.push(x);
1598            if x == slot {
1599                break;
1600            }
1601            match self.nav_parent(x) {
1602                Some(p) => x = p,
1603                None => {
1604                    // Not below `slot` (cannot happen for a live slot).
1605                    chain.clear();
1606                    chain.push(slot);
1607                    return chain;
1608                }
1609            }
1610        }
1611        chain.reverse();
1612        chain
1613    }
1614
1615    /// (rank, byte offset) of a live slot. O(log R).
1616    pub(super) fn nav_rank(&self, slot: u32) -> Option<(u64, u64)> {
1617        let Some(e) = self.edits.as_deref() else {
1618            let start = self.start_of(slot as usize);
1619            return Some((u64::from(slot), u64::try_from(start).ok()?));
1620        };
1621        let (item, run, start) = self.run_item(slot)?;
1622        let loc = self.locate(slot)?;
1623        let (pc, pb) = e.seq.prefix(item);
1624        let within = u64::from(slot.checked_sub(start)?);
1625        let a = run.a as usize;
1626        let bytes = loc.flat.start(loc.local).checked_sub(loc.flat.start(a))?;
1627        Some((
1628            pc.checked_add(within)?,
1629            pb.checked_add(u64::try_from(bytes).ok()?)?,
1630        ))
1631    }
1632
1633    /// Element count and token bytes of the whole tree.
1634    pub(super) fn nav_total(&self) -> (u64, u64) {
1635        match self.edits.as_deref() {
1636            Some(e) => e.seq.total(),
1637            None => (
1638                u64::try_from(self.kinds.len()).unwrap_or(u64::MAX),
1639                u64::try_from(self.source.len()).unwrap_or(u64::MAX),
1640            ),
1641        }
1642    }
1643
1644    /// The first element after `slot`'s subtree in preorder; `None` at the
1645    /// end. O(log R) when the subtree was not edited, else O(depth): one
1646    /// O(1) link per level climbed (a loop, no recursion).
1647    pub(super) fn nav_after(&self, slot: u32) -> Option<u32> {
1648        if self.edits.is_none() {
1649            let end = self.end_of(slot as usize);
1650            return u32::try_from(end)
1651                .ok()
1652                .filter(|e| (*e as usize) < self.kinds.len());
1653        }
1654        let loc = self.locate(slot)?;
1655        if let Some((_, run, _)) = self.run_item(slot) {
1656            let end = loc.flat.end(loc.local);
1657            if end > loc.local && end < run.b as usize {
1658                return loc.slot(end);
1659            }
1660        }
1661        let mut x = slot;
1662        loop {
1663            if let Some(n) = self.nav_next(x) {
1664                return Some(n);
1665            }
1666            x = self.nav_parent(x)?;
1667        }
1668    }
1669
1670    /// Elements in `slot`'s subtree, itself included.
1671    pub(super) fn nav_size(&self, slot: u32) -> u64 {
1672        let Some((r, _)) = self.nav_rank(slot) else {
1673            return 0;
1674        };
1675        let end = self
1676            .nav_after(slot)
1677            .and_then(|a| self.nav_rank(a))
1678            .map_or(self.nav_total().0, |(r, _)| r);
1679        end.saturating_sub(r)
1680    }
1681
1682    /// Byte range of a live slot in the edited text.
1683    pub(super) fn nav_bytes(&self, slot: u32) -> Option<(u64, u64)> {
1684        let (_, start) = self.nav_rank(slot)?;
1685        let end = self
1686            .nav_after(slot)
1687            .and_then(|a| self.nav_rank(a))
1688            .map_or(self.nav_total().1, |(_, b)| b);
1689        Some((start, end.max(start)))
1690    }
1691
1692    // ============================================================== text
1693
1694    /// The text of a live slot in an edited tree: borrowed from its arena
1695    /// when one run holds it (tokens always), else built from the runs it
1696    /// spans (O(node size)). Nothing is cached.
1697    pub(super) fn edited_text(&self, slot: u32) -> Cow<'_, str> {
1698        if let Some(loc) = self.locate(slot) {
1699            if loc.flat.kind(loc.local).is_some_and(SyntaxKind::is_token) {
1700                return Cow::Borrowed(loc.flat.token_text(loc.local));
1701            }
1702        }
1703        match self.nav_bytes(slot) {
1704            // The fallback is exact, so a read
1705            // does not assert; `text_ranges_are_covered_or_an_error` checks
1706            // that the runs cover every element.
1707            Some((a, b)) => self
1708                .try_text_range(a, b)
1709                .unwrap_or_else(|_| self.text_from_tokens(slot)),
1710            None => Cow::Borrowed(""),
1711        }
1712    }
1713
1714    /// Bytes `start..end` of the current text: borrowed when one run (or
1715    /// the unedited source) holds them, else joined from the runs.
1716    /// O(log R + bytes + runs crossed).
1717    ///
1718    /// # Errors
1719    ///
1720    /// [`TreeEditError::Internal`] when the runs do not cover the range
1721    /// (the runs tile the text by construction, so this
1722    /// is a bug, reported rather than truncated).
1723    pub(super) fn try_text_range(
1724        &self,
1725        start: u64,
1726        end: u64,
1727    ) -> Result<Cow<'_, str>, TreeEditError> {
1728        let Some(e) = self.edits.as_deref() else {
1729            let a = usize::try_from(start).map_err(|_| TreeEditError::Internal)?;
1730            let b = usize::try_from(end).map_err(|_| TreeEditError::Internal)?;
1731            if b <= a {
1732                return Ok(Cow::Borrowed(""));
1733            }
1734            return self
1735                .source
1736                .get(a..b)
1737                .map(Cow::Borrowed)
1738                .ok_or(TreeEditError::Internal);
1739        };
1740        if end <= start {
1741            return Ok(Cow::Borrowed(""));
1742        }
1743        let (mut item, mut off) = e.seq.find_byte(start).ok_or(TreeEditError::Internal)?;
1744        let mut left = end.saturating_sub(start);
1745        let mut out: Option<String> = None;
1746        loop {
1747            let piece = e.seq.run(item).and_then(|run| {
1748                let (flat, _, _) = self.run_flat(&run)?;
1749                let take = left.min(run.bytes.saturating_sub(off));
1750                let a = flat
1751                    .start(run.a as usize)
1752                    .checked_add(usize::try_from(off).ok()?)?;
1753                let b = a.checked_add(usize::try_from(take).ok()?)?;
1754                Some((flat.source.get(a..b)?, take))
1755            });
1756            // The runs tile the text (seq.rs): a missing piece is a bug.
1757            let (piece, take) = piece.ok_or(TreeEditError::Internal)?;
1758            left = left.saturating_sub(take);
1759            if left == 0 && out.is_none() {
1760                return Ok(Cow::Borrowed(piece));
1761            }
1762            out.get_or_insert_with(String::new).push_str(piece);
1763            if left == 0 {
1764                break;
1765            }
1766            item = e.seq.next(item).ok_or(TreeEditError::Internal)?;
1767            off = 0;
1768        }
1769        Ok(Cow::Owned(out.unwrap_or_default()))
1770    }
1771
1772    /// The text of live `slot` in an edited tree, joined from its tokens
1773    /// (each borrowed from its own arena): the read path's fallback when
1774    /// [`SyntaxTree::try_text_range`] reports a bug, so a read never
1775    /// returns truncated text. O(node size).
1776    fn text_from_tokens(&self, slot: u32) -> Cow<'_, str> {
1777        let mut out = String::new();
1778        let mut left = self.nav_size(slot);
1779        let mut at = Some(slot);
1780        while left > 0 {
1781            let Some(x) = at else { break };
1782            if let Some(loc) = self.locate(x) {
1783                if loc.flat.kind(loc.local).is_some_and(SyntaxKind::is_token) {
1784                    out.push_str(loc.flat.token_text(loc.local));
1785                }
1786            }
1787            left = left.saturating_sub(1);
1788            at = self.nav_succ(x);
1789        }
1790        Cow::Owned(out)
1791    }
1792
1793    /// Byte `offset` of the current text. O(log R).
1794    pub(super) fn byte_at(&self, offset: u64) -> Option<u8> {
1795        let Some(e) = self.edits.as_deref() else {
1796            return self
1797                .source
1798                .as_bytes()
1799                .get(usize::try_from(offset).ok()?)
1800                .copied();
1801        };
1802        let (item, off) = e.seq.find_byte(offset)?;
1803        let run = e.seq.run(item)?;
1804        let (flat, _, _) = self.run_flat(&run)?;
1805        let at = flat
1806            .start(run.a as usize)
1807            .checked_add(usize::try_from(off).ok()?)?;
1808        flat.source.as_bytes().get(at).copied()
1809    }
1810
1811    /// Bytes between the line break before byte `offset` of the current
1812    /// text (or its start) and `offset`: the column there, in the parser's
1813    /// own unit (it counts columns in bytes; a count of
1814    /// characters disagreed with it after non-ASCII text, and the context
1815    /// written for a re-read must put the parser where it was).
1816    /// O(column + runs crossed).
1817    ///
1818    /// Byte order marks at the start of the line are not counted: the
1819    /// parser starts a line after one (`scan_trivia`; a fuzz finding:
1820    /// counting them refused every block edit of a document behind a BOM).
1821    /// White space before a mark still counts, as the parser's indentation
1822    /// does (and the parser reports it as an error).
1823    pub(super) fn column_at(&self, offset: u64) -> Option<usize> {
1824        let mut col = self.line_bytes_before(offset)?;
1825        let mut at = offset.checked_sub(u64::try_from(col).ok()?)?;
1826        while col >= 3
1827            && self.byte_at(at) == Some(0xef)
1828            && self.byte_at(at.saturating_add(1)) == Some(0xbb)
1829            && self.byte_at(at.saturating_add(2)) == Some(0xbf)
1830        {
1831            col = col.saturating_sub(3);
1832            at = at.saturating_add(3);
1833        }
1834        Some(col)
1835    }
1836
1837    /// Bytes between the line break before byte `offset` (or the start of
1838    /// the text) and `offset`. O(column + runs crossed).
1839    fn line_bytes_before(&self, offset: u64) -> Option<usize> {
1840        let breaks = ['\n', '\r'];
1841        let Some(e) = self.edits.as_deref() else {
1842            let before = self.source.get(..usize::try_from(offset).ok()?)?;
1843            let line = before
1844                .rfind(breaks)
1845                .and_then(|i| before.get(i.checked_add(1)?..))
1846                .unwrap_or(before);
1847            return Some(line.len());
1848        };
1849        if offset == 0 {
1850            return Some(0);
1851        }
1852        let (mut item, mut last) = e.seq.find_byte(offset.checked_sub(1)?)?;
1853        let mut count = 0usize;
1854        loop {
1855            let run = e.seq.run(item)?;
1856            let (flat, _, _) = self.run_flat(&run)?;
1857            let a = flat.start(run.a as usize);
1858            let b = a.checked_add(usize::try_from(last.checked_add(1)?).ok()?)?;
1859            let piece = flat.source.get(a..b)?;
1860            if let Some(i) = piece.rfind(breaks) {
1861                let tail = piece.get(i.checked_add(1)?..)?;
1862                return Some(count.saturating_add(tail.len()));
1863            }
1864            count = count.saturating_add(piece.len());
1865            let mut p = e.seq.prev(item);
1866            loop {
1867                let Some(x) = p else { return Some(count) };
1868                let bytes = e.seq.run(x)?.bytes;
1869                if bytes > 0 {
1870                    item = x;
1871                    last = bytes.checked_sub(1)?;
1872                    break;
1873                }
1874                p = e.seq.prev(x);
1875            }
1876        }
1877    }
1878
1879    /// The text of the edited tree, run by run: O(1) per run beyond its
1880    /// bytes (the arena from the run's slab index, the next run
1881    /// by a treap step, amortised O(1); no map lookup), so O(n).
1882    pub(super) fn edited_emit(&self, e: &Edits) -> String {
1883        let (_, bytes) = e.seq.total();
1884        let mut out = String::with_capacity(usize::try_from(bytes).unwrap_or(0));
1885        let mut at = e.seq.first();
1886        while let Some(item) = at {
1887            if let Some(run) = e.seq.run(item) {
1888                if let Some((flat, _, _)) = self.run_flat(&run) {
1889                    let a = flat.start(run.a as usize);
1890                    let b = flat.start(run.b as usize).max(a);
1891                    out.push_str(flat.source.get(a..b).unwrap_or(""));
1892                }
1893            }
1894            at = e.seq.next(item);
1895        }
1896        out
1897    }
1898
1899    /// Moves a local span of `slot`'s arena to the edited text.
1900    pub(super) fn to_global(&self, slot: u32, span: Span) -> Span {
1901        let (Some(loc), Some((_, off))) = (self.locate(slot), self.nav_rank(slot)) else {
1902            return span;
1903        };
1904        let from = loc.flat.start(loc.local);
1905        super::arena::shift_span(span, from, usize::try_from(off).unwrap_or(usize::MAX))
1906    }
1907
1908    // ======================================================= diagnostics
1909
1910    /// The diagnostics attached to live `slot`, in order, spans in the
1911    /// current text. O(log d) (+ O(log R) edited).
1912    ///
1913    /// A diagnostic's spans move with the element it is attached to. The
1914    /// only diagnostics whose primary span lies before their element are
1915    /// `Y0028` (`lenient_inline_colons`) warnings, whose span is inside the
1916    /// plain scalar right before the element: no other element lies
1917    /// between, so the move is exact unless that scalar itself is replaced
1918    /// (the warning then leaves with it: see
1919    /// [`SyntaxTree::is_dropped`], or the check refuses the edit).
1920    pub(super) fn diagnostics_of(&self, slot: u32) -> Vec<Cow<'_, Diagnostic>> {
1921        if self.edits.is_none() {
1922            let i = slot as usize;
1923            let lo = self.diagnostics.partition_point(|(n, _)| (*n as usize) < i);
1924            return self
1925                .diagnostics
1926                .get(lo..)
1927                .unwrap_or_default()
1928                .iter()
1929                .take_while(|(n, _)| *n as usize == i)
1930                .map(|(_, d)| d.view())
1931                .collect();
1932        }
1933        let (Some(loc), Some((_, off))) = (self.locate(slot), self.nav_rank(slot)) else {
1934            return Vec::new();
1935        };
1936        let from = loc.flat.start(loc.local);
1937        let to = usize::try_from(off).unwrap_or(usize::MAX);
1938        loc.flat
1939            .diagnostics_at(loc.local)
1940            .iter()
1941            .enumerate()
1942            .filter(|(n, _)| !self.is_dropped(slot, *n))
1943            .map(|(_, (_, d))| {
1944                let mut d = d.clone();
1945                d.shift(from, to);
1946                Cow::Owned(d.view().into_owned())
1947            })
1948            .collect()
1949    }
1950
1951    /// Calls `f(diagnostic, from, to)` for each diagnostic attached to
1952    /// live `slot`, in order, where moving its spans by `to - from` puts
1953    /// them in the current text. No allocation, and
1954    /// nothing searched in an arena without diagnostics.
1955    pub(super) fn for_each_diagnostic(&self, slot: u32, mut f: impl FnMut(&Stored, usize, usize)) {
1956        let Some(loc) = self.locate(slot) else {
1957            return;
1958        };
1959        if loc.flat.diagnostics.is_empty() {
1960            return;
1961        }
1962        let list = loc.flat.diagnostics_at(loc.local);
1963        if list.is_empty() {
1964            return;
1965        }
1966        let (from, to) = if self.edits.is_none() {
1967            (0, 0)
1968        } else {
1969            let Some((_, off)) = self.nav_rank(slot) else {
1970                return;
1971            };
1972            (
1973                loc.flat.start(loc.local),
1974                usize::try_from(off).unwrap_or(usize::MAX),
1975            )
1976        };
1977        for (n, (_, d)) in list.iter().enumerate() {
1978            if !self.is_dropped(slot, n) {
1979                f(d, from, to);
1980            }
1981        }
1982    }
1983
1984    /// The `n`-th diagnostic attached to `slot` left the tree (see
1985    /// `Edits::dropped`). O(1) while none has, else
1986    /// O(log).
1987    pub(super) fn is_dropped(&self, slot: u32, n: usize) -> bool {
1988        self.edits.as_deref().is_some_and(|e| {
1989            !e.dropped.is_empty() && u32::try_from(n).is_ok_and(|n| e.dropped.contains(&(slot, n)))
1990        })
1991    }
1992
1993    /// `is_dropped` for entry `at` of `flat`'s diagnostic list, whose
1994    /// arena's first slot is `first`. O(1) while none was dropped.
1995    fn list_dropped(&self, flat: &Flat<'_>, first: u32, at: usize) -> bool {
1996        let Some(e) = self.edits.as_deref() else {
1997            return false;
1998        };
1999        if e.dropped.is_empty() {
2000            return false;
2001        }
2002        let Some(&(l, _)) = flat.diagnostics.get(at) else {
2003            return false;
2004        };
2005        let group = flat.diagnostics.partition_point(|(x, _)| *x < l);
2006        self.is_dropped(first.saturating_add(l), at.saturating_sub(group))
2007    }
2008
2009    /// Calls `f` for the diagnostics attached to elements from live
2010    /// `slot` on, in element order (`forward`), or from `slot` back
2011    /// (`slot` included), until `f` returns `false` or the element rank
2012    /// leaves the bound (`forward`: ranks below `bound`; backwards: ranks
2013    /// at or above `bound`). Nothing is built or cloned,
2014    /// and only the runs inside the bound are visited, O(log d + log R)
2015    /// each, so a caller that stops early pays for what it reads.
2016    pub(super) fn scan_diagnostics(
2017        &self,
2018        slot: u32,
2019        forward: bool,
2020        bound: u64,
2021        mut f: impl FnMut(DiagAt<'_>) -> bool,
2022    ) {
2023        let Some(e) = self.edits.as_deref() else {
2024            let i = slot as usize;
2025            let len = self.kinds.len();
2026            let list = &self.diagnostics;
2027            let mut visit = |(n, d): &(u32, Stored)| {
2028                let n = *n as usize;
2029                let rank = u64::try_from(n).unwrap_or(u64::MAX);
2030                let inside = n < len && if forward { rank < bound } else { rank >= bound };
2031                inside
2032                    && f(DiagAt {
2033                        rank,
2034                        start: u64::try_from(self.start_of(n)).unwrap_or(u64::MAX),
2035                        diagnostic: d,
2036                        from: 0,
2037                        to: 0,
2038                    })
2039            };
2040            if forward {
2041                let lo = list.partition_point(|(n, _)| (*n as usize) < i);
2042                for x in list.get(lo..).unwrap_or_default() {
2043                    if !visit(x) {
2044                        return;
2045                    }
2046                }
2047            } else {
2048                let hi = list.partition_point(|(n, _)| (*n as usize) <= i);
2049                for x in list.get(..hi).unwrap_or_default().iter().rev() {
2050                    if !visit(x) {
2051                        return;
2052                    }
2053                }
2054            }
2055            return;
2056        };
2057        let Some((mut item, first_run, start)) = self.run_item(slot) else {
2058            return;
2059        };
2060        let (mut count_at, mut bytes_at) = e.seq.prefix(item);
2061        // The local index to scan from in the current run.
2062        let mut local = first_run.a.saturating_add(slot.saturating_sub(start));
2063        loop {
2064            let Some(run) = e.seq.run(item) else { return };
2065            // The runs visited are all inside the bound's side.
2066            let run_count = u64::from(run.b.saturating_sub(run.a));
2067            let outside = if forward {
2068                count_at >= bound
2069            } else {
2070                count_at.saturating_add(run_count) <= bound
2071            };
2072            if outside {
2073                return;
2074            }
2075            let flat = self.run_flat(&run).filter(|_| run_count > 0);
2076            if let Some((flat, first, _)) = flat {
2077                let run_from = flat.start(run.a as usize);
2078                let list = flat.diagnostics;
2079                let (lo, hi) = if forward {
2080                    (
2081                        list.partition_point(|(l, _)| *l < local),
2082                        list.partition_point(|(l, _)| *l < run.b),
2083                    )
2084                } else {
2085                    (
2086                        list.partition_point(|(l, _)| *l < run.a),
2087                        list.partition_point(|(l, _)| *l <= local),
2088                    )
2089                };
2090                let window = list.get(lo..hi.max(lo)).unwrap_or_default();
2091                let mut visit = |(l, d): &(u32, Stored)| {
2092                    let rank = count_at.saturating_add(u64::from(l.saturating_sub(run.a)));
2093                    let inside = if forward { rank < bound } else { rank >= bound };
2094                    let from = flat.start(*l as usize);
2095                    let start = u64::try_from(from.saturating_sub(run_from))
2096                        .unwrap_or(u64::MAX)
2097                        .saturating_add(bytes_at);
2098                    inside
2099                        && f(DiagAt {
2100                            rank,
2101                            start,
2102                            diagnostic: d,
2103                            from,
2104                            to: usize::try_from(start).unwrap_or(usize::MAX),
2105                        })
2106                };
2107                // Warnings that left the tree are passed over.
2108                let gone = |k: usize| self.list_dropped(&flat, first, lo.saturating_add(k));
2109                if forward {
2110                    for (k, x) in window.iter().enumerate() {
2111                        if !gone(k) && !visit(x) {
2112                            return;
2113                        }
2114                    }
2115                } else {
2116                    for (k, x) in window.iter().enumerate().rev() {
2117                        if !gone(k) && !visit(x) {
2118                            return;
2119                        }
2120                    }
2121                }
2122            }
2123            // Jump straight to the next run holding a
2124            // diagnostic (subtree sums, O(log R)); walking run by run made
2125            // every edit O(R), so edit cost grew with the edit history.
2126            let jump = if forward {
2127                e.seq.next_with_diags(item)
2128            } else {
2129                e.seq.prev_with_diags(item)
2130            };
2131            let Some(n) = jump else { return };
2132            let Some(nr) = e.seq.run(n) else { return };
2133            item = n;
2134            (count_at, bytes_at) = e.seq.prefix(n);
2135            local = if forward {
2136                nr.a
2137            } else {
2138                // (An empty run's window is empty.)
2139                nr.b.saturating_sub(1).max(nr.a)
2140            };
2141        }
2142    }
2143
2144    /// An edited tree's diagnostics in element order, spans moved to the
2145    /// edited text, read from each arena's own sorted list (nothing
2146    /// is rebuilt per edit). `within`: only those attached inside that
2147    /// slot's subtree (O(D' (log d + log R) + k) for its D' runs holding
2148    /// diagnostics); `None`: all,
2149    /// with the base's after-the-last-element warnings (attached to
2150    /// `NONE`) at the end.
2151    pub(super) fn edited_diagnostics(&self, e: &Edits, within: Option<u32>) -> Vec<(u32, Stored)> {
2152        let mut out = Vec::new();
2153        let start = match within {
2154            Some(slot) => self
2155                .run_item(slot)
2156                .and_then(|(item, _, first)| Some((item, slot.checked_sub(first)?))),
2157            None => e.seq.first().map(|item| (item, 0)),
2158        };
2159        let size = match within {
2160            Some(slot) => self.nav_size(slot),
2161            None => e.seq.total().0,
2162        };
2163        if let Some((mut item, mut skip)) = start {
2164            let (run_rank, mut bytes_at) = e.seq.prefix(item);
2165            // The rank one past the last element read.
2166            let end = run_rank
2167                .saturating_add(u64::from(skip))
2168                .saturating_add(size);
2169            let mut rank_at = run_rank;
2170            while rank_at < end {
2171                let Some(run) = e.seq.run(item) else { break };
2172                let Some((flat, first, _)) = self.run_flat(&run) else {
2173                    break;
2174                };
2175                let a = run.a.saturating_add(skip);
2176                let n = u32::try_from(end.saturating_sub(rank_at))
2177                    .unwrap_or(u32::MAX)
2178                    .min(run.b.saturating_sub(run.a))
2179                    .saturating_sub(skip);
2180                let b = a.saturating_add(n);
2181                let run_from = flat.start(run.a as usize);
2182                let lo = flat.diagnostics.partition_point(|(l, _)| *l < a);
2183                let list = flat.diagnostics.get(lo..).unwrap_or_default();
2184                for (k, (l, d)) in list.iter().take_while(|(l, _)| *l < b).enumerate() {
2185                    // Warnings that left the tree are not listed.
2186                    if self.list_dropped(&flat, first, lo.saturating_add(k)) {
2187                        continue;
2188                    }
2189                    let from = flat.start(*l as usize);
2190                    let to = from
2191                        .checked_sub(run_from)
2192                        .and_then(|x| u64::try_from(x).ok())
2193                        .and_then(|x| x.checked_add(bytes_at))
2194                        .and_then(|x| usize::try_from(x).ok())
2195                        .unwrap_or(usize::MAX);
2196                    let mut d = d.clone();
2197                    d.shift(from, to);
2198                    out.push((first.saturating_add(*l), d));
2199                }
2200                skip = 0;
2201                // The runs without diagnostics are
2202                // skipped in O(log R), not visited one by one.
2203                match e.seq.next_with_diags(item) {
2204                    Some(x) => {
2205                        item = x;
2206                        (rank_at, bytes_at) = e.seq.prefix(x);
2207                    }
2208                    None => break,
2209                }
2210            }
2211        }
2212        if within.is_none() {
2213            // Warnings after the last element: their spans are at the end
2214            // of the base text, which is the end of the edited text.
2215            let base_len = self.kinds.len();
2216            let lo = self
2217                .diagnostics
2218                .partition_point(|(n, _)| (*n as usize) < base_len);
2219            let to = usize::try_from(e.seq.total().1).unwrap_or(usize::MAX);
2220            for (_, d) in self.diagnostics.get(lo..).unwrap_or_default() {
2221                let mut d = d.clone();
2222                d.shift(self.source.len(), to);
2223                out.push((NONE, d));
2224            }
2225        }
2226        out
2227    }
2228
2229    // ============================================================ copying
2230
2231    /// The document enclosing `slot` (or `slot` itself). O(depth).
2232    pub(super) fn document_of(&self, slot: u32) -> Option<u32> {
2233        let mut x = Some(slot);
2234        while let Some(s) = x {
2235            if self.kind_of(s) == Some(SyntaxKind::Document) {
2236                return Some(s);
2237            }
2238            x = self.nav_parent(s);
2239        }
2240        None
2241    }
2242
2243    /// The `%TAG` directives (text, one per line) of the document enclosing
2244    /// `slot` (or `slot` itself); empty outside any document. Cheap:
2245    /// directives are a document's first children, so only those and the
2246    /// trivia between them are read, never the document's content.
2247    pub(super) fn tag_context(&self, slot: u32) -> String {
2248        let mut out = String::new();
2249        let Some(doc) = self.document_of(slot) else {
2250            return out;
2251        };
2252        let mut c = self.nav_first(doc);
2253        while let Some(ch) = c {
2254            let Some(loc) = self.locate(ch) else { break };
2255            match loc.flat.kind(loc.local) {
2256                Some(SyntaxKind::TagDirective) => {
2257                    out.push_str(loc.flat.token_text(loc.local));
2258                    out.push('\n');
2259                }
2260                Some(k) if is_directive(k) || k.is_trivia() => {}
2261                _ => break,
2262            }
2263            c = self.nav_next(ch);
2264        }
2265        out
2266    }
2267
2268    /// A fragment of the subtrees of `roots` (live slots, in order): its
2269    /// `%TAG` context is that of `context`'s document, read only when a
2270    /// copied tag needs it.
2271    pub(super) fn fragment_of(
2272        &self,
2273        roots: &[u32],
2274        context: u32,
2275    ) -> Result<Fragment, TreeEditError> {
2276        let (arena, has_tags) = self.copy_forest(roots)?;
2277        let context = if has_tags {
2278            self.tag_context(context)
2279        } else {
2280            String::new()
2281        };
2282        Ok(Fragment {
2283            arena,
2284            context,
2285            has_tags,
2286        })
2287    }
2288
2289    /// Copies the subtrees of `roots` (live slots, in order) into a new
2290    /// arena; also says whether a tag lies outside every copied document.
2291    /// O(copied elements), with an explicit stack: no recursion.
2292    pub(super) fn copy_forest(&self, roots: &[u32]) -> Result<(Arena, bool), TreeEditError> {
2293        self.copy_forest_with(roots, true)
2294    }
2295
2296    /// [`SyntaxTree::copy_forest`]; `slices`: through
2297    /// [`SyntaxTree::copy_slice`] where it applies (`false`: the element
2298    /// walk only, which the tests compare it with).
2299    fn copy_forest_with(
2300        &self,
2301        roots: &[u32],
2302        slices: bool,
2303    ) -> Result<(Arena, bool), TreeEditError> {
2304        let cap = |n: usize| u32::try_from(n).ok().filter(|n| *n < NONE);
2305        let mut out = Arena::default();
2306        // (global slot, local index, is a document)
2307        let mut stack: Vec<(u32, u32, bool)> = Vec::new();
2308        // Open documents are counted, not searched for per tag.
2309        let mut open_docs = 0usize;
2310        let mut prefixes: Vec<(usize, String)> = Vec::new();
2311        let mut has_tags = false;
2312        for &root in roots {
2313            // A subtree that is one piece of one arena
2314            // (always in a parsed tree) is copied as slices.
2315            if slices && self.copy_slice(root, &mut out, &mut prefixes, &mut has_tags)? {
2316                continue;
2317            }
2318            let count = self.nav_size(root);
2319            let mut x = Some(root);
2320            let mut left = count;
2321            while left > 0 {
2322                left = left.saturating_sub(1);
2323                let slot = x.ok_or(TreeEditError::Internal)?;
2324                x = self.nav_succ(slot);
2325                let loc = self.locate(slot).ok_or(TreeEditError::Internal)?;
2326                let kind = loc.flat.kind(loc.local).ok_or(TreeEditError::Internal)?;
2327                let parent = if slot == root {
2328                    None
2329                } else {
2330                    self.nav_parent(slot)
2331                };
2332                while let Some(&(g, local, doc)) = stack.last() {
2333                    if Some(g) == parent {
2334                        break;
2335                    }
2336                    stack.pop();
2337                    if doc {
2338                        open_docs = open_docs.saturating_sub(1);
2339                    }
2340                    let end = cap(out.kinds.len()).ok_or(TreeEditError::Capacity)?;
2341                    *out.words
2342                        .get_mut(local as usize)
2343                        .ok_or(TreeEditError::Internal)? = end;
2344                }
2345                let index = cap(out.kinds.len()).ok_or(TreeEditError::Capacity)?;
2346                let at = out.source.len();
2347                out.kinds.push(kind);
2348                out.parents.push(stack.last().map_or(NONE, |(_, l, _)| *l));
2349                for (k, (_, d)) in loc.flat.diagnostics_at(loc.local).iter().enumerate() {
2350                    // A warning that left the tree is not copied.
2351                    if self.is_dropped(slot, k) {
2352                        continue;
2353                    }
2354                    let mut d = d.clone();
2355                    d.shift(loc.flat.start(loc.local), at);
2356                    out.diagnostics.push((index, d));
2357                }
2358                if kind.is_token() {
2359                    out.words.push(cap(at).ok_or(TreeEditError::Capacity)?);
2360                    let text = loc.flat.token_text(loc.local);
2361                    out.source.push_str(text);
2362                    if kind == SyntaxKind::Tag && open_docs == 0 {
2363                        has_tags = true;
2364                    }
2365                    if kind == SyntaxKind::BlockScalarHeader {
2366                        // The header span is the header token's (C5). The
2367                        // owner's extra is the last one pushed: only its
2368                        // property tokens came since (no search).
2369                        let owner = stack.last().map(|(_, l, _)| *l);
2370                        if let Some(e) = out.extras.last_mut().filter(|(i, _)| Some(*i) == owner) {
2371                            if let Some(h) = e.1.block.as_mut() {
2372                                h.span = Span::new(at, at.saturating_add(text.len()));
2373                            }
2374                        }
2375                    }
2376                } else {
2377                    let doc = kind == SyntaxKind::Document;
2378                    out.words.push(index);
2379                    stack.push((slot, index, doc));
2380                    if doc {
2381                        open_docs = open_docs.saturating_add(1);
2382                    }
2383                    if let Some(extra) = loc.flat.extra(loc.local) {
2384                        if let Some(p) = extra.tag_prefix {
2385                            let text = loc.flat.source.get(p..).unwrap_or("");
2386                            let end = text.find([' ', '\t', '\n', '\r']).unwrap_or(text.len());
2387                            prefixes
2388                                .push((out.extras.len(), text.get(..end).unwrap_or("").to_owned()));
2389                        }
2390                        out.extras.push((
2391                            index,
2392                            Extra {
2393                                tag_prefix: None,
2394                                block: extra.block,
2395                            },
2396                        ));
2397                    }
2398                }
2399            }
2400            while let Some((_, local, _)) = stack.pop() {
2401                let end = cap(out.kinds.len()).ok_or(TreeEditError::Capacity)?;
2402                *out.words
2403                    .get_mut(local as usize)
2404                    .ok_or(TreeEditError::Internal)? = end;
2405            }
2406            open_docs = 0;
2407        }
2408        out.tiled = out.source.len();
2409        for (e, text) in prefixes {
2410            let p = out.source.len();
2411            out.source.push_str(&text);
2412            out.source.push('\n');
2413            if let Some(x) = out.extras.get_mut(e) {
2414                x.1.tag_prefix = Some(p);
2415            }
2416        }
2417        cap(out.source.len()).ok_or(TreeEditError::Capacity)?;
2418        Ok((out, has_tags))
2419    }
2420
2421    /// [`SyntaxTree::copy_forest`] of one root whose subtree is local
2422    /// indices `l0..l1` of one arena, all in one overlay run (every subtree
2423    /// of a parsed tree): the arena's arrays are copied as slices, their
2424    /// links moved by a constant, with no navigation per element (the
2425    /// per-element walk was 54% of the cost of removing a large entry).
2426    /// Writes exactly what the element walk writes, or nothing and
2427    /// returns `false` (a subtree holding a document, or one an edit cut
2428    /// into pieces: the walk copies it). O(copied elements).
2429    fn copy_slice(
2430        &self,
2431        root: u32,
2432        out: &mut Arena,
2433        prefixes: &mut Vec<(usize, String)>,
2434        has_tags: &mut bool,
2435    ) -> Result<bool, TreeEditError> {
2436        let Some(loc) = self.locate(root) else {
2437            return Ok(false);
2438        };
2439        let flat = loc.flat;
2440        let l0 = loc.local;
2441        let Ok(count) = usize::try_from(self.nav_size(root)) else {
2442            return Ok(false);
2443        };
2444        let Some(l1) = l0.checked_add(count) else {
2445            return Ok(false);
2446        };
2447        if count == 0 || l1 > flat.len() || flat.end(l0) != l1 {
2448            return Ok(false);
2449        }
2450        // One run: its slots are consecutive, in its arena's order.
2451        if self.edits.is_some() {
2452            let Some((_, run, start)) = self.run_item(root) else {
2453                return Ok(false);
2454            };
2455            let end = run
2456                .b
2457                .checked_sub(run.a)
2458                .and_then(|n| start.checked_add(n))
2459                .and_then(|e| usize::try_from(e).ok());
2460            let last = usize::try_from(root)
2461                .ok()
2462                .and_then(|r| r.checked_add(count));
2463            if !matches!((last, end), (Some(l), Some(e)) if l <= e) {
2464                return Ok(false);
2465            }
2466        }
2467        let Some(kinds) = flat.kinds.get(l0..l1) else {
2468            return Ok(false);
2469        };
2470        // (A document's tags are resolved inside it: the walk counts them.)
2471        if kinds.contains(&SyntaxKind::Document) {
2472            return Ok(false);
2473        }
2474        let tags = kinds.contains(&SyntaxKind::Tag);
2475        let cap = |n: usize| u32::try_from(n).ok().filter(|n| *n < NONE);
2476        let base = out.kinds.len();
2477        let at_base = out.source.len();
2478        let src_a = flat.start(l0);
2479        let src_b = flat.start(l1);
2480        let Some(text) = flat.source.get(src_a..src_b) else {
2481            return Ok(false);
2482        };
2483        cap(base.saturating_add(count)).ok_or(TreeEditError::Capacity)?;
2484        cap(at_base.saturating_add(text.len())).ok_or(TreeEditError::Capacity)?;
2485        let marks = (
2486            out.parents.len(),
2487            out.words.len(),
2488            out.extras.len(),
2489            out.diagnostics.len(),
2490            prefixes.len(),
2491        );
2492        // An element's index and a byte offset in the copy (in range: both
2493        // capped above).
2494        let index = |i: usize| -> u32 {
2495            let x = base.saturating_add(i.saturating_sub(l0));
2496            u32::try_from(x).unwrap_or(NONE)
2497        };
2498        let offset = |at: usize| -> usize { at_base.saturating_add(at.saturating_sub(src_a)) };
2499        // Links and words; the tokens must start in order (C1), so that
2500        // their texts, one after another as the walk copies them, are
2501        // `text`.
2502        let mut tiled = src_a;
2503        let mut ok = true;
2504        let mut headers: Vec<(usize, usize, usize)> = Vec::new();
2505        out.parents.reserve(count);
2506        out.words.reserve(count);
2507        out.kinds.reserve(count);
2508        for (i, kind) in (l0..l1).zip(kinds.iter().copied()) {
2509            let parent = if i == l0 {
2510                NONE
2511            } else {
2512                match flat.parent(i) {
2513                    Some(p) if p >= l0 && p < i => index(p),
2514                    _ => {
2515                        ok = false;
2516                        break;
2517                    }
2518                }
2519            };
2520            out.parents.push(parent);
2521            if kind.is_token() {
2522                let start = flat.token_start(i).min(flat.tiled);
2523                if start < tiled || start > src_b {
2524                    ok = false;
2525                    break;
2526                }
2527                tiled = start;
2528                let at = offset(start);
2529                out.words.push(u32::try_from(at).unwrap_or(NONE));
2530                if kind == SyntaxKind::BlockScalarHeader && i != l0 {
2531                    headers.push((i, at, flat.token_span(i).len()));
2532                }
2533            } else {
2534                let end = flat.end(i);
2535                if end <= i || end > l1 {
2536                    ok = false;
2537                    break;
2538                }
2539                out.words.push(index(end));
2540            }
2541        }
2542        if ok {
2543            // Extras (nodes only), in order, as the walk pushes them.
2544            let lo = flat.extras.partition_point(|(n, _)| (*n as usize) < l0);
2545            let hi = flat.extras.partition_point(|(n, _)| (*n as usize) < l1);
2546            for (n, extra) in flat.extras.get(lo..hi).unwrap_or_default() {
2547                let n = *n as usize;
2548                if flat.kind(n).is_none_or(SyntaxKind::is_token) {
2549                    continue;
2550                }
2551                if let Some(p) = extra.tag_prefix {
2552                    let t = flat.source.get(p..).unwrap_or("");
2553                    let end = t.find([' ', '\t', '\n', '\r']).unwrap_or(t.len());
2554                    prefixes.push((out.extras.len(), t.get(..end).unwrap_or("").to_owned()));
2555                }
2556                out.extras.push((
2557                    index(n),
2558                    Extra {
2559                        tag_prefix: None,
2560                        block: extra.block,
2561                    },
2562                ));
2563            }
2564            // A block scalar header's span is its token's (C5), set where
2565            // the walk sets it: on the last extra pushed before the header
2566            // token, when that is its parent's.
2567            for (i, at, len) in headers {
2568                let (Some(p), here) = (flat.parent(i), index(i)) else {
2569                    continue;
2570                };
2571                let owner = index(p);
2572                let k = out.extras.partition_point(|(n, _)| *n < here);
2573                let Some(e) = k.checked_sub(1).and_then(|k| out.extras.get_mut(k)) else {
2574                    continue;
2575                };
2576                if e.0 == owner {
2577                    if let Some(h) = e.1.block.as_mut() {
2578                        h.span = Span::new(at, at.saturating_add(len));
2579                    }
2580                }
2581            }
2582            // Diagnostics, by element, in order (a dropped warning stays).
2583            let lo = flat
2584                .diagnostics
2585                .partition_point(|(n, _)| (*n as usize) < l0);
2586            let hi = flat
2587                .diagnostics
2588                .partition_point(|(n, _)| (*n as usize) < l1);
2589            let mut prev = usize::MAX;
2590            let mut k = 0usize;
2591            for (n, d) in flat.diagnostics.get(lo..hi).unwrap_or_default() {
2592                let n = *n as usize;
2593                k = if n == prev { k.saturating_add(1) } else { 0 };
2594                prev = n;
2595                let slot = u32::try_from(n.saturating_sub(l0))
2596                    .ok()
2597                    .and_then(|o| root.checked_add(o))
2598                    .ok_or(TreeEditError::Internal)?;
2599                if self.is_dropped(slot, k) {
2600                    continue;
2601                }
2602                let from = flat.start(n);
2603                let mut d = d.clone();
2604                d.shift(from, offset(from));
2605                out.diagnostics.push((index(n), d));
2606            }
2607        }
2608        if !ok {
2609            out.parents.truncate(marks.0);
2610            out.words.truncate(marks.1);
2611            out.extras.truncate(marks.2);
2612            out.diagnostics.truncate(marks.3);
2613            prefixes.truncate(marks.4);
2614            return Ok(false);
2615        }
2616        out.kinds.extend_from_slice(kinds);
2617        out.source.push_str(text);
2618        *has_tags |= tags;
2619        Ok(true)
2620    }
2621
2622    // ========================================================= validation
2623
2624    pub(super) fn live_slot(&self, id: NodeId) -> Result<u32, TreeEditError> {
2625        Ok(self.get(id)?.slot())
2626    }
2627
2628    /// Children may be added under / removed from `parent`.
2629    pub(super) fn check_parent(&self, parent: u32) -> Result<SyntaxKind, TreeEditError> {
2630        let kind = self.kind_of(parent).ok_or(TreeEditError::Internal)?;
2631        if kind.is_token() {
2632            return Err(TreeEditError::NotANode { kind });
2633        }
2634        if matches!(
2635            kind,
2636            SyntaxKind::Scalar | SyntaxKind::Alias | SyntaxKind::Error
2637        ) {
2638            return Err(TreeEditError::ReadOnly { kind });
2639        }
2640        Ok(kind)
2641    }
2642
2643    /// The siblings `first..=last`, with their parent.
2644    pub(super) fn sibling_range(
2645        &self,
2646        first: u32,
2647        last: u32,
2648    ) -> Result<(u32, Vec<u32>), TreeEditError> {
2649        let parent = self.nav_parent(first).ok_or(TreeEditError::NoParent)?;
2650        if self.nav_parent(last) != Some(parent) {
2651            return Err(TreeEditError::NotSiblings);
2652        }
2653        let mut roots = vec![first];
2654        let mut x = first;
2655        while x != last {
2656            x = self.nav_next(x).ok_or(TreeEditError::NotSiblings)?;
2657            roots.push(x);
2658        }
2659        Ok((parent, roots))
2660    }
2661
2662    /// The range may be removed.
2663    pub(super) fn check_removable(&self, roots: &[u32]) -> Result<(), TreeEditError> {
2664        for &r in roots {
2665            let kind = self.kind_of(r).ok_or(TreeEditError::Internal)?;
2666            if is_directive(kind) || is_node_property(kind) {
2667                return Err(TreeEditError::ReadOnly { kind });
2668            }
2669        }
2670        // An error region reads the same after
2671        // edits, so no edit removes (or replaces) an `Error` node inside a
2672        // document; a whole document goes with its errors (the edited
2673        // text then has neither, as its re-parse). Only a tree with errors
2674        // pays for the walk, O(removed) (what a removal copies anyway);
2675        // A flat walk.
2676        if self.error_count() > 0 {
2677            for &r in roots {
2678                if self.kind_of(r) == Some(SyntaxKind::Document) {
2679                    continue;
2680                }
2681                let error = super::Node::new(self, r)
2682                    .descendants()
2683                    .any(|n| n.kind() == SyntaxKind::Error);
2684                if error {
2685                    return Err(TreeEditError::ReadOnly {
2686                        kind: SyntaxKind::Error,
2687                    });
2688                }
2689            }
2690        }
2691        Ok(())
2692    }
2693
2694    /// `fragment` may go under `parent`.
2695    pub(super) fn check_insertable(
2696        &self,
2697        parent: u32,
2698        parent_kind: SyntaxKind,
2699        fragment: &Fragment,
2700    ) -> Result<(), TreeEditError> {
2701        if fragment.is_empty() {
2702            return Err(TreeEditError::EmptyFragment);
2703        }
2704        for kind in fragment.root_kinds() {
2705            if is_directive(kind) || is_node_property(kind) {
2706                return Err(TreeEditError::ReadOnly { kind });
2707            }
2708            let fits = match (parent_kind, kind) {
2709                (_, SyntaxKind::Stream) => false,
2710                (SyntaxKind::Stream, k) => k == SyntaxKind::Document || k.is_token(),
2711                (_, SyntaxKind::Document) => false,
2712                _ => true,
2713            };
2714            if !fits {
2715                return Err(TreeEditError::Misplaced {
2716                    kind,
2717                    parent: parent_kind,
2718                });
2719            }
2720        }
2721        if fragment.has_tags && fragment.context != self.tag_context(parent) {
2722            return Err(TreeEditError::TagContext);
2723        }
2724        Ok(())
2725    }
2726
2727    // ============================================================ editing
2728
2729    /// Creates the overlay on the first edit: one run over the base, O(1).
2730    fn ensure_edits(&mut self) -> Result<(), TreeEditError> {
2731        if self.edits.is_some() {
2732            return Ok(());
2733        }
2734        let len = u32::try_from(self.kinds.len()).map_err(|_| TreeEditError::Capacity)?;
2735        let bytes = u64::try_from(self.source.len()).map_err(|_| TreeEditError::Capacity)?;
2736        let diags = self.base_flat().diagnostics_in(0, len);
2737        let marks = marks(self.base_flat(), &self.run_facts, Some(&self.facts), 0, len);
2738        let seq = Seq::new(Run {
2739            arena: 0,
2740            graft: NONE,
2741            a: 0,
2742            b: len,
2743            bytes,
2744            diags,
2745            // The base holds the stream root.
2746            trivia: false,
2747            marks,
2748        });
2749        let mut runs = BTreeMap::new();
2750        runs.insert(0, seq.first().ok_or(TreeEditError::Internal)?);
2751        self.edits = Some(Box::new(Edits {
2752            arenas: BTreeMap::new(),
2753            grafts: Slab::default(),
2754            seq,
2755            runs,
2756            links: BTreeMap::new(),
2757            dropped: BTreeSet::new(),
2758            // Never below the slots a rolled-back group
2759            // issued before it dropped the overlay.
2760            next_slot: len.max(self.slot_floor),
2761        }));
2762        Ok(())
2763    }
2764
2765    /// Makes `slot` the first element of a run; returns that run's item.
2766    /// Changes how the order is cut, never the order itself.
2767    #[cfg(test)]
2768    fn cut_before(&mut self, slot: u32) -> Result<u32, TreeEditError> {
2769        self.cut_logged(slot, None)
2770    }
2771
2772    /// [`SyntaxTree::cut_before`], recording an actual split in `undo`.
2773    fn cut_logged(&mut self, slot: u32, undo: Option<&mut Undo>) -> Result<u32, TreeEditError> {
2774        let (item, run, start) = self.run_item(slot).ok_or(TreeEditError::Internal)?;
2775        let offset = slot.checked_sub(start).ok_or(TreeEditError::Internal)?;
2776        if offset == 0 {
2777            return Ok(item);
2778        }
2779        let (flat, _, _) = self.run_flat(&run).ok_or(TreeEditError::Internal)?;
2780        let mid = run.a.checked_add(offset).ok_or(TreeEditError::Internal)?;
2781        let left_bytes = flat
2782            .start(mid as usize)
2783            .checked_sub(flat.start(run.a as usize))
2784            .and_then(|b| u64::try_from(b).ok())
2785            .ok_or(TreeEditError::Internal)?;
2786        let left_diags = flat.diagnostics_in(run.a, mid);
2787        // Each half's own flag (O(LONG_RUN + log)).
2788        let (left_trivia, right_trivia) = if run.trivia {
2789            (true, true)
2790        } else {
2791            (
2792                self.stream_trivia(run.arena, run.a, mid),
2793                self.stream_trivia(run.arena, mid, run.b),
2794            )
2795        };
2796        // Each half's marks (O(log + LONG_RUN + a line)).
2797        let left_marks = self.run_marks(run.arena, run.a, mid);
2798        let right_marks = self.run_marks(run.arena, mid, run.b);
2799        let left = Run {
2800            b: mid,
2801            bytes: left_bytes,
2802            diags: left_diags,
2803            trivia: left_trivia,
2804            marks: left_marks,
2805            ..run
2806        };
2807        let right = Run {
2808            a: mid,
2809            bytes: run.bytes.saturating_sub(left_bytes),
2810            diags: run.diags.saturating_sub(left_diags),
2811            trivia: right_trivia,
2812            marks: right_marks,
2813            ..run
2814        };
2815        let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
2816        // Reserve first: a full item space leaves the run whole.
2817        if !e.seq.can_insert(1) {
2818            return Err(TreeEditError::Capacity);
2819        }
2820        let new = e
2821            .seq
2822            .insert_after(Some(item), right)
2823            .ok_or(TreeEditError::Capacity)?;
2824        e.seq.set_run(item, left);
2825        e.runs.insert(slot, new);
2826        if let Some(u) = undo {
2827            u.cuts.push(slot);
2828        }
2829        Ok(new)
2830    }
2831
2832    fn set_links(
2833        &mut self,
2834        slot: u32,
2835        undo: &mut Undo,
2836        f: impl FnOnce(&mut Links),
2837    ) -> Result<(), TreeEditError> {
2838        let mut l = self.links_of(slot);
2839        f(&mut l);
2840        let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
2841        let old = e.links.insert(slot, l);
2842        undo.links.push((slot, old));
2843        Ok(())
2844    }
2845
2846    /// The one structural edit: under `parent`, after sibling `prev`
2847    /// (`None`: at the front), remove the siblings `removed` (consecutive,
2848    /// starting right after `prev`) and insert `fragment`'s roots; then,
2849    /// when `validate`, check that the edit is well-formed. The caller has
2850    /// done the other checks. Refused or failed, the edit is undone
2851    /// exactly: the tree is unchanged on error.
2852    pub(super) fn splice(
2853        &mut self,
2854        parent: u32,
2855        prev: Option<u32>,
2856        removed: &[u32],
2857        fragment: Option<Fragment>,
2858        validate: bool,
2859    ) -> Result<Spliced, TreeEditError> {
2860        self.splice_dropping(parent, prev, removed, fragment, validate, &[])
2861    }
2862
2863    /// [`SyntaxTree::splice`] that also drops warnings `drops` (`(slot,
2864    /// n)`: the `n`-th diagnostic attached to live `slot`) before the
2865    /// check (undone with the rest when refused).
2866    fn splice_dropping(
2867        &mut self,
2868        parent: u32,
2869        prev: Option<u32>,
2870        removed: &[u32],
2871        fragment: Option<Fragment>,
2872        validate: bool,
2873        drops: &[(u32, u32)],
2874    ) -> Result<Spliced, TreeEditError> {
2875        let mut a = self.splice_apply(parent, prev, removed, fragment, validate)?;
2876        if let Some(e) = self.edits.as_deref_mut() {
2877            for &d in drops {
2878                if e.dropped.insert(d) {
2879                    a.undo.dropped.push(d);
2880                }
2881            }
2882        }
2883        if validate {
2884            let c = a.check;
2885            if let Err(err) = self.check_well_formed(c.parent, c.prev, c.next, a.span, c.what) {
2886                self.undo(a.undo)?;
2887                return Err(err);
2888            }
2889        }
2890        self.accept(a.undo);
2891        Ok((a.taken, a.span))
2892    }
2893
2894    /// After an accepted edit: its seams merged and what it removed
2895    /// released, or, inside an edit group, the edit kept to be undone.
2896    fn accept(&mut self, undo: Undo) {
2897        let seams = self.seams(&undo);
2898        self.accept_with(undo, seams);
2899    }
2900
2901    /// [`SyntaxTree::accept`] with the seams read already.
2902    fn accept_with(&mut self, undo: Undo, seams: Vec<u32>) {
2903        if self.group.depth > 0 {
2904            // Nothing is merged or released while a group
2905            // is open, so every logged undo record stays exact.
2906            self.group.log.push((undo, seams));
2907            return;
2908        }
2909        self.coalesce(&seams);
2910        self.release(&undo);
2911    }
2912
2913    /// Opens an **edit group** (a multi-step edit is all or
2914    /// nothing): the edits accepted until the matching
2915    /// [`SyntaxTree::end_group`] can be undone together by
2916    /// [`SyntaxTree::rollback_group`], exactly (the tree, its text, its
2917    /// diagnostics, and every handle are as they were at
2918    /// `begin_group`). Groups nest; each edit is still checked on its own.
2919    /// O(1).
2920    ///
2921    /// While a group is open, accepted edits keep their undo records and
2922    /// the runs they split (merged and released when the outermost group
2923    /// ends), so a group should be closed by one of the two calls: an
2924    /// unclosed group costs memory and run count, never correctness.
2925    pub fn begin_group(&mut self) -> GroupMark {
2926        self.group.depth = self.group.depth.saturating_add(1);
2927        GroupMark {
2928            tree: self.stamp,
2929            at: self.group.log.len(),
2930            depth: self.group.depth,
2931        }
2932    }
2933
2934    /// `mark` is the innermost open group's mark of this tree.
2935    fn check_mark(&self, mark: GroupMark) -> Result<(), TreeEditError> {
2936        if mark.tree != self.stamp
2937            || mark.depth != self.group.depth
2938            || mark.at > self.group.log.len()
2939        {
2940            return Err(TreeEditError::Internal);
2941        }
2942        Ok(())
2943    }
2944
2945    /// For a copy of this tree made while a group is open (`Clone`,
2946    /// [`SyntaxTree::fork`]): the copy has no group, so the group's edits
2947    /// are accepted edits there; they are merged and released in the copy
2948    /// as [`SyntaxTree::end_group`] would (a copy never
2949    /// keeps the runs or arenas the group held back).
2950    pub(super) fn settle_group_copy(&self, copy: &mut Self) {
2951        for (_, seams) in &self.group.log {
2952            copy.coalesce(seams);
2953        }
2954        for (undo, _) in &self.group.log {
2955            copy.release(undo);
2956        }
2957    }
2958
2959    /// Closes the group `mark` opened, keeping its edits (for the
2960    /// outermost group: merging and releasing as each edit alone would
2961    /// have; O(edits of the group · log R)).
2962    ///
2963    /// # Errors
2964    ///
2965    /// [`TreeEditError::Internal`] when `mark` is not the innermost open
2966    /// group's (the tree is unchanged).
2967    pub fn end_group(&mut self, mark: GroupMark) -> Result<(), TreeEditError> {
2968        self.check_mark(mark)?;
2969        self.group.depth = self.group.depth.saturating_sub(1);
2970        if self.group.depth == 0 {
2971            let log = std::mem::take(&mut self.group.log);
2972            for (_, seams) in &log {
2973                self.coalesce(seams);
2974            }
2975            for (undo, _) in &log {
2976                self.release(undo);
2977            }
2978        }
2979        Ok(())
2980    }
2981
2982    /// Closes the group `mark` opened, undoing every edit accepted in it,
2983    /// latest first: the tree is exactly as at [`SyntaxTree::begin_group`].
2984    /// O(edits of the group · (log R + their size)).
2985    ///
2986    /// # Errors
2987    ///
2988    /// [`TreeEditError::Internal`] when `mark` is not the innermost open
2989    /// group's (the tree is unchanged), or an undo record does not apply
2990    /// (an invariant of this crate).
2991    pub fn rollback_group(&mut self, mark: GroupMark) -> Result<(), TreeEditError> {
2992        self.check_mark(mark)?;
2993        // Slots are never reused: the slots the group
2994        // issued stay issued. Undoing its edits puts back everything else,
2995        // but the next slot stays past them, in the overlay or, when the
2996        // rollback drops the overlay the group created, in `slot_floor`.
2997        let high = self.next_slot();
2998        let undone = self.group.log.split_off(mark.at);
2999        self.group.depth = self.group.depth.saturating_sub(1);
3000        for (undo, _) in undone.into_iter().rev() {
3001            self.undo(undo)?;
3002        }
3003        match self.edits.as_deref_mut() {
3004            Some(e) => e.next_slot = e.next_slot.max(high),
3005            None => self.slot_floor = self.slot_floor.max(high),
3006        }
3007        if self.group.depth == 0 {
3008            // Only an outer group's edits can be left (none here, as the
3009            // outermost mark starts at 0); kept for symmetry.
3010            let log = std::mem::take(&mut self.group.log);
3011            for (_, seams) in &log {
3012                self.coalesce(seams);
3013            }
3014            for (undo, _) in &log {
3015                self.release(undo);
3016            }
3017        }
3018        Ok(())
3019    }
3020
3021    /// `true` while an edit group is open.
3022    #[must_use]
3023    pub fn in_group(&self) -> bool {
3024        self.group.depth > 0
3025    }
3026
3027    /// See [`Edits::release`] (after an accepted edit only: a
3028    /// refused one puts its removed runs back).
3029    fn release(&mut self, u: &Undo) {
3030        if let Some(e) = self.edits.as_deref_mut() {
3031            e.release(&u.doomed);
3032        }
3033    }
3034
3035    /// Up to two splices applied as one edit: each
3036    /// is applied, then each is checked for well-formedness on the tree
3037    /// both produced (a window of one may read the other's text); refused
3038    /// or failed, both are undone, the later first. The second is planned
3039    /// by `second` once the first is applied (its places may name what
3040    /// the first inserted). Returns what each removed and inserted.
3041    pub(super) fn splice_pair(
3042        &mut self,
3043        first: SpliceArgs,
3044        second: impl FnOnce(&Self, Option<(u32, u32)>) -> Result<Option<SpliceArgs>, TreeEditError>,
3045    ) -> Result<(Spliced, Option<Spliced>), TreeEditError> {
3046        let a = self.splice_apply(
3047            first.parent,
3048            first.prev,
3049            &first.removed,
3050            first.fragment,
3051            true,
3052        )?;
3053        let plan = match second(self, a.span) {
3054            Ok(p) => p,
3055            Err(err) => {
3056                self.undo(a.undo)?;
3057                return Err(err);
3058            }
3059        };
3060        let b = match plan {
3061            Some(s) => match self.splice_apply(s.parent, s.prev, &s.removed, s.fragment, true) {
3062                Ok(b) => Some(b),
3063                Err(err) => {
3064                    self.undo(a.undo)?;
3065                    return Err(err);
3066                }
3067            },
3068            None => None,
3069        };
3070        // When the second splice replaced the element right after
3071        // the first (`splice_leaving_warnings`), the first's `next` is its
3072        // copy now.
3073        let mut a = a;
3074        if let (Some(n), Some(b)) = (a.check.next, &b) {
3075            if !self.is_live(n) {
3076                a.check.next = b.span.map(|s| s.0).or(b.check.next);
3077            }
3078        }
3079        // The first splice's labels are checked in the
3080        // text before it, so the elements after the second splice are
3081        // moved back by that one's bytes too, the others (the first's own
3082        // elements) not. Every caller puts the second after the first.
3083        let mut what = a.check.what;
3084        let mut ordered = true;
3085        if let Some(b) = &b {
3086            let from = self.rank_after(&b.check, b.span);
3087            // In every caller the second splice sits right after the first
3088            // in preorder (it moves the line break that ends the first's
3089            // line, or re-copies the element after the first without a
3090            // warning that left with it): no element lies between them, so
3091            // only the first's own elements were moved by the whole text's
3092            // delta. Checked in release too,
3093            // as part of `ordered` (an `Err(Internal)`, never a wrong
3094            // label check).
3095            let adjacent = Some(self.rank_after(&a.check, a.span))
3096                == match b.span {
3097                    Some((f, _)) => self.nav_rank(f).map(|r| r.0),
3098                    None => Some(from),
3099                };
3100            let head = a.span.map(|s| s.0).or(a.check.next);
3101            let head_rank = head.and_then(|h| self.nav_rank(h)).map(|r| r.0);
3102            ordered = adjacent && head_rank.is_none_or(|h| h <= from);
3103            let more =
3104                i128::from(b.check.what.added).saturating_sub(i128::from(b.check.what.removed));
3105            what.later = Some((from, more));
3106        }
3107        debug_assert!(
3108            ordered,
3109            "splice_pair: the second splice precedes the first or is not next to it"
3110        );
3111        let mut checked = if ordered {
3112            let c = &a.check;
3113            self.check_well_formed(c.parent, c.prev, c.next, a.span, what)
3114        } else {
3115            Err(TreeEditError::Internal)
3116        };
3117        if let (Ok(()), Some(b)) = (&checked, &b) {
3118            let c = &b.check;
3119            checked = self.check_well_formed(c.parent, c.prev, c.next, b.span, c.what);
3120        }
3121        if let Err(err) = checked {
3122            if let Some(b) = b {
3123                self.undo(b.undo)?;
3124            }
3125            self.undo(a.undo)?;
3126            return Err(err);
3127        }
3128        // Both seams are read before any merge (item ids are only valid
3129        // until then).
3130        let seams_a = self.seams(&a.undo);
3131        let spliced_a = (a.taken, a.span);
3132        let Some(b) = b else {
3133            self.accept_with(a.undo, seams_a);
3134            return Ok((spliced_a, None));
3135        };
3136        let seams_b = self.seams(&b.undo);
3137        self.accept_with(a.undo, seams_a);
3138        self.accept_with(b.undo, seams_b);
3139        Ok((spliced_a, Some((b.taken, b.span))))
3140    }
3141
3142    /// The rank of the first element after an applied splice's change (the
3143    /// total element count at the end).
3144    fn rank_after(&self, check: &Check, span: Option<(u32, u32)>) -> u64 {
3145        let x = match (span, check.next, check.prev) {
3146            (Some((_, l)), _, _) => self.nav_after(l),
3147            (None, Some(n), _) => Some(n),
3148            (None, None, Some(p)) => self.nav_after(p),
3149            (None, None, None) => self.nav_after(check.parent),
3150        };
3151        x.and_then(|x| self.nav_rank(x))
3152            .map_or(self.nav_total().0, |r| r.0)
3153    }
3154
3155    /// The applying part of [`SyntaxTree::splice`]: the checks that come
3156    /// before any change (limits, capacity), then the change. The caller
3157    /// validates and undoes.
3158    fn splice_apply(
3159        &mut self,
3160        parent: u32,
3161        prev: Option<u32>,
3162        removed: &[u32],
3163        fragment: Option<Fragment>,
3164        validate: bool,
3165    ) -> Result<Applied, TreeEditError> {
3166        // ---- everything read before anything changes
3167        let next = match removed.last() {
3168            Some(&l) => self.nav_next(l),
3169            None => match prev {
3170                Some(p) => self.nav_next(p),
3171                None => self.nav_first(parent),
3172            },
3173        };
3174        // Insertion goes right before `cut` (`None`: at the very end).
3175        let cut = match removed.last() {
3176            Some(&l) => self.nav_after(l),
3177            None => match next {
3178                Some(n) => Some(n),
3179                None => self.nav_after(parent),
3180            },
3181        };
3182        let taken = if removed.is_empty() {
3183            None
3184        } else {
3185            Some(self.fragment_of(removed, parent)?)
3186        };
3187        // Limits apply to edits. The whole text's size, and the
3188        // number of documents when documents are inserted (the window
3189        // reads only its own documents). The documents
3190        // are counted (`SyntaxTree::documents`, kept by every edit) and the
3191        // removed ones once, so the check is O(removed), never
3192        // O(documents).
3193        let limits = self.settings.get_limits();
3194        let removed_bytes = taken.as_ref().map_or(0, |t| t.arena.tiled);
3195        let added_bytes = fragment.as_ref().map_or(0, |f| f.arena.tiled);
3196        let total = usize::try_from(self.nav_total().1).map_err(|_| TreeEditError::Capacity)?;
3197        let new_total = total
3198            .saturating_sub(removed_bytes)
3199            .saturating_add(added_bytes);
3200        if validate && new_total > limits.get_max_document_size() && new_total > total {
3201            return Err(TreeEditError::Limit {
3202                code: oneyaml_core::code::DOCUMENT_TOO_LARGE,
3203            });
3204        }
3205        let (docs_removed, docs_added) = if parent == 0 {
3206            (
3207                removed
3208                    .iter()
3209                    .filter(|&&r| self.kind_of(r) == Some(SyntaxKind::Document))
3210                    .count(),
3211                fragment.as_ref().map_or(0, |f| {
3212                    f.root_kinds()
3213                        .filter(|k| *k == SyntaxKind::Document)
3214                        .count()
3215                }),
3216            )
3217        } else {
3218            (0, 0)
3219        };
3220        let documents = self
3221            .documents
3222            .saturating_sub(docs_removed)
3223            .saturating_add(docs_added);
3224        // The error count moves with the diagnostics removed and inserted
3225        // (O(their diagnostics), already copied or owned).
3226        let error_count = |a: &Arena| a.diagnostics.iter().filter(|(_, d)| d.is_error()).count();
3227        let errors = self
3228            .errors
3229            .saturating_sub(taken.as_ref().map_or(0, |t| error_count(&t.arena)))
3230            .saturating_add(fragment.as_ref().map_or(0, |f| error_count(&f.arena)));
3231        if validate && docs_added > 0 && documents > limits.get_max_documents() {
3232            return Err(TreeEditError::Limit {
3233                code: oneyaml_core::code::TOO_MANY_DOCUMENTS,
3234            });
3235        }
3236        let what = Removed {
3237            // A diagnostic leaving with what is removed is decided by the
3238            // window (the shortcut only reads the lines around).
3239            trivia_only: taken
3240                .as_ref()
3241                .is_none_or(|t| t.arena.diagnostics.is_empty())
3242                && removed.iter().all(|&r| {
3243                    self.kind_of(r).is_some_and(|k| {
3244                        matches!(
3245                            k,
3246                            SyntaxKind::Whitespace | SyntaxKind::LineBreak | SyntaxKind::Comment
3247                        )
3248                    })
3249                }),
3250            comment: removed
3251                .iter()
3252                .any(|&r| self.kind_of(r) == Some(SyntaxKind::Comment)),
3253            // Whether the element after the edit started a line before it.
3254            next_line_start: match removed.last() {
3255                Some(&r) => self.kind_of(r) == Some(SyntaxKind::LineBreak),
3256                // The start of the text starts a line.
3257                None => match prev {
3258                    Some(p) => self.kind_of(p) == Some(SyntaxKind::LineBreak),
3259                    None => parent == 0,
3260                },
3261            },
3262            added: u64::try_from(added_bytes).map_err(|_| TreeEditError::Capacity)?,
3263            removed: u64::try_from(removed_bytes).map_err(|_| TreeEditError::Capacity)?,
3264            later: None,
3265            // Read before the change (see `Removed::old_column`).
3266            old_column: (validate
3267                && prev.is_none()
3268                && self.errors == 0
3269                && self.kind_of(parent) == Some(SyntaxKind::BlockMapping))
3270            .then(|| self.entry_column(parent))
3271            .flatten(),
3272            // (O(removed), as copying it.)
3273            line_break: taken
3274                .as_ref()
3275                .is_some_and(|t| t.text().contains(['\n', '\r'])),
3276        };
3277        let mut new_first = None;
3278        if let Some(f) = &fragment {
3279            // (past the slots of a rolled-back group, too.)
3280            let next_slot = self.next_slot() as usize;
3281            let end = next_slot
3282                .checked_add(f.len())
3283                .ok_or(TreeEditError::Capacity)?;
3284            if u32::try_from(end).map_or(true, |e| e == NONE) {
3285                return Err(TreeEditError::Capacity);
3286            }
3287            new_first = Some(u32::try_from(next_slot).map_err(|_| TreeEditError::Capacity)?);
3288        }
3289
3290        // ---- the change, recorded to be undone
3291        let created = self.edits.is_none();
3292        self.ensure_edits()?;
3293        let mut undo = Undo {
3294            created,
3295            next_slot: self.edits.as_deref().map_or(0, |e| e.next_slot),
3296            documents: self.documents,
3297            errors: self.errors,
3298            ..Undo::default()
3299        };
3300        let plan = Plan {
3301            parent,
3302            prev,
3303            next,
3304            cut,
3305            new_first,
3306        };
3307        match self.apply(plan, removed, fragment, &mut undo) {
3308            Ok(span) => {
3309                self.documents = documents;
3310                self.errors = errors;
3311                Ok(Applied {
3312                    taken,
3313                    span,
3314                    undo,
3315                    check: Check {
3316                        parent,
3317                        prev,
3318                        next,
3319                        what,
3320                    },
3321                })
3322            }
3323            Err(err) => {
3324                self.undo(undo)?;
3325                Err(err)
3326            }
3327        }
3328    }
3329
3330    /// The mutating part of [`SyntaxTree::splice`].
3331    fn apply(
3332        &mut self,
3333        plan: Plan,
3334        removed: &[u32],
3335        fragment: Option<Fragment>,
3336        undo: &mut Undo,
3337    ) -> Result<Option<(u32, u32)>, TreeEditError> {
3338        let Plan {
3339            parent,
3340            prev,
3341            next,
3342            cut,
3343            new_first,
3344        } = plan;
3345        if let Some(&first) = removed.first() {
3346            let from = self.cut_logged(first, Some(undo))?;
3347            let until = cut.map(|c| self.cut_logged(c, Some(undo))).transpose()?;
3348            let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
3349            undo.after = match e.seq.prev(from) {
3350                Some(item) => Some(e.run_start(item).ok_or(TreeEditError::Internal)?),
3351                None => None,
3352            };
3353            let mut doomed = Vec::new();
3354            let mut at = Some(from);
3355            while let Some(item) = at {
3356                if Some(item) == until {
3357                    break;
3358                }
3359                doomed.push(item);
3360                at = e.seq.next(item);
3361            }
3362            for item in doomed {
3363                let run = e.seq.run(item).ok_or(TreeEditError::Internal)?;
3364                let key = run
3365                    .arena
3366                    .checked_add(run.a)
3367                    .ok_or(TreeEditError::Internal)?;
3368                e.runs.remove(&key);
3369                e.seq.remove(item);
3370                undo.doomed.push((key, run));
3371            }
3372        }
3373        let mut span = None;
3374        if let (Some(fragment), Some(first)) = (fragment, new_first) {
3375            let before = match cut {
3376                Some(c) => Some(self.cut_logged(c, Some(undo))?),
3377                None => None,
3378            };
3379            let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
3380            let after = match before {
3381                Some(b) => e.seq.prev(b),
3382                None => e.seq.last(),
3383            };
3384            let len = u32::try_from(fragment.len()).map_err(|_| TreeEditError::Capacity)?;
3385            let bytes = u64::try_from(fragment.arena.tiled).map_err(|_| TreeEditError::Capacity)?;
3386            // An arena is named by its first slot (never 0: the
3387            // base holds at least the stream root).
3388            let id = first;
3389            let last_root = fragment.arena.flat().roots().last().unwrap_or(0);
3390            let last = first
3391                .checked_add(u32::try_from(last_root).map_err(|_| TreeEditError::Internal)?)
3392                .ok_or(TreeEditError::Internal)?;
3393            let next_slot = first.checked_add(len).ok_or(TreeEditError::Capacity)?;
3394            // Reserve before mutating: the run's item.
3395            if !e.seq.can_insert(1) {
3396                return Err(TreeEditError::Capacity);
3397            }
3398            // O(roots + diagnostics), which
3399            // building the fragment already cost.
3400            let facts = if parent == 0 {
3401                let flat = fragment.arena.flat();
3402                let errors = flat.diagnostics.iter().any(|(_, d)| d.is_error());
3403                StreamFacts::of(flat, flat.roots(), errors)
3404            } else {
3405                StreamFacts::default()
3406            };
3407            // Whether the whole fragment is stream-level trivia.
3408            let trivia =
3409                parent == 0 && all_stream_trivia(fragment.arena.flat(), &facts, false, 0, len);
3410            // Its comment-run index, O(its elements), which
3411            // building it already cost.
3412            let runs = RunFacts::of(fragment.arena.flat());
3413            let marks = marks(
3414                fragment.arena.flat(),
3415                &runs,
3416                (parent == 0).then_some(&facts),
3417                0,
3418                len,
3419            );
3420            let diags = fragment.arena.flat().diagnostics_in(0, len);
3421            // The arena is kept first, so the run names its index.
3422            let graft = e
3423                .add_graft(
3424                    first,
3425                    Grafted {
3426                        parent,
3427                        arena: fragment.arena,
3428                        facts,
3429                        runs,
3430                    },
3431                )
3432                .ok_or(TreeEditError::Capacity)?;
3433            let run = Run {
3434                arena: id,
3435                graft,
3436                a: 0,
3437                b: len,
3438                bytes,
3439                diags,
3440                trivia,
3441                marks,
3442            };
3443            let Some(item) = e.seq.insert_after(after, run) else {
3444                e.drop_graft(first, false);
3445                return Err(TreeEditError::Capacity);
3446            };
3447            undo.grafted = Some(first);
3448            undo.arena_pushed = true;
3449            e.runs.insert(first, item);
3450            e.next_slot = next_slot;
3451            span = Some((first, last));
3452        }
3453
3454        // ---- links (at most four overrides)
3455        let (head, tail) = match span {
3456            Some((f, l)) => (Some(f), Some(l)),
3457            None => (next, prev),
3458        };
3459        match prev {
3460            Some(p) => self.set_links(p, undo, |l| l.next = head.unwrap_or(NONE))?,
3461            None => self.set_links(parent, undo, |l| l.first = head.unwrap_or(NONE))?,
3462        }
3463        match next {
3464            Some(n) => self.set_links(n, undo, |l| l.prev = tail.unwrap_or(NONE))?,
3465            None => self.set_links(parent, undo, |l| l.last = tail.unwrap_or(NONE))?,
3466        }
3467        if let Some((f, l)) = span {
3468            self.set_links(f, undo, |x| x.prev = prev.unwrap_or(NONE))?;
3469            self.set_links(l, undo, |x| x.next = next.unwrap_or(NONE))?;
3470        }
3471        Ok(span)
3472    }
3473
3474    /// Puts back what [`SyntaxTree::apply`] changed. The order of runs and
3475    /// every link is restored (the treap's shape may differ, which no read
3476    /// can see).
3477    fn undo(&mut self, u: Undo) -> Result<(), TreeEditError> {
3478        self.documents = u.documents;
3479        self.errors = u.errors;
3480        if u.created {
3481            self.edits = None;
3482            return Ok(());
3483        }
3484        let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
3485        for d in &u.dropped {
3486            e.dropped.remove(d);
3487        }
3488        for (slot, old) in u.links.into_iter().rev() {
3489            match old {
3490                Some(l) => e.links.insert(slot, l),
3491                None => e.links.remove(&slot),
3492            };
3493        }
3494        if let Some(first) = u.grafted {
3495            let item = e.runs.remove(&first).ok_or(TreeEditError::Internal)?;
3496            e.seq.remove(item);
3497            if u.arena_pushed {
3498                e.drop_graft(first, false);
3499            }
3500        }
3501        e.next_slot = u.next_slot;
3502        let mut at = match u.after {
3503            Some(key) => Some(*e.runs.get(&key).ok_or(TreeEditError::Internal)?),
3504            None => None,
3505        };
3506        for (key, run) in u.doomed {
3507            // The removals freed these items: re-inserting cannot fail.
3508            let item = e.seq.insert_after(at, run).ok_or(TreeEditError::Internal)?;
3509            e.runs.insert(key, item);
3510            at = Some(item);
3511        }
3512        // The splits this edit made are merged back, latest
3513        // first, so a refused edit leaves the runs as they were.
3514        for slot in u.cuts.into_iter().rev() {
3515            e.merge_at(slot);
3516        }
3517        Ok(())
3518    }
3519
3520    /// The run starts where an accepted edit may have left two runs that
3521    /// continue each other: its cuts, and the place of its removal.
3522    /// Collected before any merge (item ids are only valid until then).
3523    fn seams(&self, u: &Undo) -> Vec<u32> {
3524        let mut out = u.cuts.clone();
3525        let Some(e) = self.edits.as_deref() else {
3526            return out;
3527        };
3528        if !u.doomed.is_empty() {
3529            let after = match u.after {
3530                Some(key) => e.runs.get(&key).and_then(|a| e.seq.next(*a)),
3531                None => e.seq.first(),
3532            };
3533            if let Some(key) = after.and_then(|item| e.run_start(item)) {
3534                out.push(key);
3535            }
3536        }
3537        out
3538    }
3539
3540    /// Edit cost is independent of edit history: after an accepted edit,
3541    /// merges the runs it left continuing each other (a cut next to a
3542    /// removal of inserted text, e.g. an insertion and its removal), so R
3543    /// grows only with the edits whose text is still in the tree. O(k log
3544    /// R) for k seams (at most 4 per splice).
3545    fn coalesce(&mut self, seams: &[u32]) {
3546        if let Some(e) = self.edits.as_deref_mut() {
3547            for &slot in seams {
3548                e.merge_at(slot);
3549            }
3550        }
3551    }
3552
3553    fn inserted(&self, span: Option<(u32, u32)>) -> Result<Inserted, TreeEditError> {
3554        let (f, l) = span.ok_or(TreeEditError::Internal)?;
3555        Ok(Inserted {
3556            first: self.id_of(f),
3557            last: self.id_of(l),
3558        })
3559    }
3560
3561    // ========================================================= public API
3562
3563    /// Copies the siblings `first..=last` and their subtrees into a
3564    /// detached [`Fragment`], leaving the tree as it is. O(copied).
3565    ///
3566    /// With [`SyntaxTree::parse_with`], this builds a fragment out of any
3567    /// text through the one parser: parse a snippet written for the
3568    /// target context, then extract the elements wanted.
3569    ///
3570    /// # Errors
3571    ///
3572    /// [`TreeEditError::Stale`], [`TreeEditError::NoParent`] (the stream
3573    /// root), [`TreeEditError::NotSiblings`].
3574    pub fn extract(&self, first: NodeId, last: NodeId) -> Result<Fragment, TreeEditError> {
3575        let (f, l) = (self.live_slot(first)?, self.live_slot(last)?);
3576        let (parent, roots) = self.sibling_range(f, l)?;
3577        self.fragment_of(&roots, parent)
3578    }
3579
3580    /// Removes element `id` with its subtree and returns it as a detached
3581    /// fragment (with its diagnostics). Handles into it become stale.
3582    ///
3583    /// # Errors
3584    ///
3585    /// See [`SyntaxTree::remove_range`].
3586    pub fn remove(&mut self, id: NodeId) -> Result<Fragment, TreeEditError> {
3587        self.remove_range(id, id)
3588    }
3589
3590    /// Removes the siblings `first..=last` with their subtrees.
3591    /// O(depth + log R + removed + window).
3592    ///
3593    /// # Errors
3594    ///
3595    /// [`TreeEditError::Stale`]; [`TreeEditError::NoParent`] for the stream
3596    /// root; [`TreeEditError::NotSiblings`]; [`TreeEditError::ReadOnly`]
3597    /// inside a scalar, alias, or error node, and for directives, tag
3598    /// properties, and block scalar headers; `ReadOnly { kind: Error }`
3599    /// for a range holding an [`SyntaxKind::Error`] node below document
3600    /// level (an error region is never removed or replaced by an
3601    /// edit; a whole document goes with its errors), and for an edit that
3602    /// could change how recovered input reads;
3603    /// [`TreeEditError::NotWellFormed`] when the text left would not read
3604    /// back as the tree left (e.g. removing the `:` of `a: 1`).
3605    pub fn remove_range(&mut self, first: NodeId, last: NodeId) -> Result<Fragment, TreeEditError> {
3606        let (f, l) = (self.live_slot(first)?, self.live_slot(last)?);
3607        let (parent, roots) = self.sibling_range(f, l)?;
3608        self.check_parent(parent)?;
3609        self.check_removable(&roots)?;
3610        let prev = self.nav_prev(f);
3611        // (a removal keeps its warnings, unlike a replacement:
3612        // the removed text could not be put back, since an insertion
3613        // cannot give the element after it the warning back.)
3614        let (taken, _) = self.splice(parent, prev, &roots, None, true)?;
3615        taken.ok_or(TreeEditError::Internal)
3616    }
3617
3618    /// Replaces element `id` (with its subtree) by `with`'s elements.
3619    ///
3620    /// # Errors
3621    ///
3622    /// See [`SyntaxTree::replace_range`].
3623    pub fn replace(&mut self, id: NodeId, with: Fragment) -> Result<Replaced, TreeEditError> {
3624        self.replace_range(id, id, with)
3625    }
3626
3627    /// Replaces the siblings `first..=last` by `with`'s elements. The
3628    /// fragment is dropped when the edit is refused (clone it first to keep
3629    /// it). O(depth + log R + removed + inserted roots + window).
3630    ///
3631    /// # Errors
3632    ///
3633    /// Those of [`SyntaxTree::remove_range`] and
3634    /// [`SyntaxTree::insert_before`].
3635    pub fn replace_range(
3636        &mut self,
3637        first: NodeId,
3638        last: NodeId,
3639        with: Fragment,
3640    ) -> Result<Replaced, TreeEditError> {
3641        let (f, l) = (self.live_slot(first)?, self.live_slot(last)?);
3642        let (parent, roots) = self.sibling_range(f, l)?;
3643        let pk = self.check_parent(parent)?;
3644        self.check_removable(&roots)?;
3645        self.check_insertable(parent, pk, &with)?;
3646        let prev = self.nav_prev(f);
3647        let (taken, span) = self.splice_leaving_warnings(parent, prev, roots, Some(with))?;
3648        Ok(Replaced {
3649            removed: taken.ok_or(TreeEditError::Internal)?,
3650            inserted: self.inserted(span)?,
3651        })
3652    }
3653
3654    /// Inserts `fragment`'s elements right before `sibling`.
3655    /// O(depth + log R + inserted roots + window). The fragment is dropped
3656    /// when the edit is refused.
3657    ///
3658    /// # Errors
3659    ///
3660    /// [`TreeEditError::Stale`]; [`TreeEditError::NoParent`];
3661    /// [`TreeEditError::EmptyFragment`]; [`TreeEditError::ReadOnly`]
3662    /// (inside a scalar, alias, or error node; directive, tag, or header
3663    /// elements); [`TreeEditError::Misplaced`];
3664    /// [`TreeEditError::TagContext`]; [`TreeEditError::NotWellFormed`]
3665    /// (e.g. `x` appended right after `a: 1`); [`TreeEditError::Capacity`].
3666    pub fn insert_before(
3667        &mut self,
3668        sibling: NodeId,
3669        fragment: Fragment,
3670    ) -> Result<Inserted, TreeEditError> {
3671        let s = self.live_slot(sibling)?;
3672        let parent = self.nav_parent(s).ok_or(TreeEditError::NoParent)?;
3673        let prev = self.nav_prev(s);
3674        self.insert_at(parent, prev, fragment)
3675    }
3676
3677    /// Inserts `fragment`'s elements right after `sibling`.
3678    ///
3679    /// # Errors
3680    ///
3681    /// As [`SyntaxTree::insert_before`].
3682    pub fn insert_after(
3683        &mut self,
3684        sibling: NodeId,
3685        fragment: Fragment,
3686    ) -> Result<Inserted, TreeEditError> {
3687        let s = self.live_slot(sibling)?;
3688        let parent = self.nav_parent(s).ok_or(TreeEditError::NoParent)?;
3689        self.insert_at(parent, Some(s), fragment)
3690    }
3691
3692    /// Inserts `fragment`'s elements as the last children of `parent`.
3693    ///
3694    /// # Errors
3695    ///
3696    /// As [`SyntaxTree::insert_before`], plus [`TreeEditError::NotANode`]
3697    /// when `parent` is a token.
3698    pub fn append_child(
3699        &mut self,
3700        parent: NodeId,
3701        fragment: Fragment,
3702    ) -> Result<Inserted, TreeEditError> {
3703        let p = self.live_slot(parent)?;
3704        self.check_parent(p)?;
3705        let prev = self.nav_last(p);
3706        self.insert_at(p, prev, fragment)
3707    }
3708
3709    /// Inserts `fragment`'s elements so that the first becomes child
3710    /// number `position` of `parent` (`0..=children`). O(position) to find
3711    /// the place, then as [`SyntaxTree::insert_before`].
3712    ///
3713    /// # Errors
3714    ///
3715    /// As [`SyntaxTree::append_child`], plus [`TreeEditError::Position`].
3716    #[doc(hidden)]
3717    pub fn insert_child(
3718        &mut self,
3719        parent: NodeId,
3720        position: usize,
3721        fragment: Fragment,
3722    ) -> Result<Inserted, TreeEditError> {
3723        let p = self.live_slot(parent)?;
3724        self.check_parent(p)?;
3725        let mut prev = None;
3726        let mut seen = 0usize;
3727        while seen < position {
3728            let next = match prev {
3729                None => self.nav_first(p),
3730                Some(x) => self.nav_next(x),
3731            };
3732            match next {
3733                Some(n) => prev = Some(n),
3734                None => {
3735                    return Err(TreeEditError::Position {
3736                        position,
3737                        len: seen,
3738                    });
3739                }
3740            }
3741            seen = seen.saturating_add(1);
3742        }
3743        self.insert_at(p, prev, fragment)
3744    }
3745
3746    fn insert_at(
3747        &mut self,
3748        parent: u32,
3749        prev: Option<u32>,
3750        fragment: Fragment,
3751    ) -> Result<Inserted, TreeEditError> {
3752        let pk = self.check_parent(parent)?;
3753        self.check_insertable(parent, pk, &fragment)?;
3754        let (_, span) = self.splice(parent, prev, &[], Some(fragment), true)?;
3755        self.inserted(span)
3756    }
3757
3758    /// Replaces the text of token `id`, returning the new token's handle
3759    /// (the old one becomes stale). The text must read, through the one
3760    /// parser under the tree's own [`SyntaxTree::settings`], as
3761    /// exactly one token of the same kind: in flow context for a scalar,
3762    /// alias, or anchor inside a flow collection. Replaceable: plain,
3763    /// quoted, alias, anchor, comment, white space, and line break tokens.
3764    /// The caller supplies text valid in its context (e.g. a multi-line
3765    /// scalar's indentation); the edit must be well-formed (a comment
3766    /// replaced by a comment always is).
3767    ///
3768    /// # Errors
3769    ///
3770    /// [`TreeEditError::Stale`]; [`TreeEditError::NotAToken`];
3771    /// [`TreeEditError::ReadOnly`] for other token kinds;
3772    /// [`TreeEditError::InvalidToken`] when the text does not read as one
3773    /// such token; [`TreeEditError::NotWellFormed`] when it does, but not
3774    /// where it would go (e.g. a multi-line key, or indentation that moves
3775    /// an entry).
3776    pub fn replace_token(&mut self, id: NodeId, text: &str) -> Result<NodeId, TreeEditError> {
3777        let x = self.live_slot(id)?;
3778        let kind = self.kind_of(x).ok_or(TreeEditError::Internal)?;
3779        if !kind.is_token() {
3780            return Err(TreeEditError::NotAToken { kind });
3781        }
3782        if !REPLACEABLE.contains(&kind) {
3783            return Err(TreeEditError::ReadOnly { kind });
3784        }
3785        let parent = self.nav_parent(x).ok_or(TreeEditError::Internal)?;
3786        let flow = {
3787            let mut at = Some(parent);
3788            let mut flow = false;
3789            while let Some(a) = at {
3790                match self.kind_of(a) {
3791                    Some(
3792                        SyntaxKind::FlowMapping | SyntaxKind::FlowSequence | SyntaxKind::FlowPair,
3793                    ) => {
3794                        flow = true;
3795                        break;
3796                    }
3797                    Some(SyntaxKind::Document | SyntaxKind::Stream) | None => break,
3798                    _ => at = self.nav_parent(a),
3799                }
3800            }
3801            flow
3802        };
3803        let fragment = token_fragment(kind, text, flow, &self.settings)?;
3804        // A comment's text ends its line and means nothing: another comment
3805        // in its place is always well-formed (not re-read). A diagnostic
3806        // attached to it would leave with it, so then it is re-read.
3807        // In a tree with errors it is checked too, as any
3808        // edit (a diagnostic after it may have a label before it, which
3809        // would move with its element: an unclosed `[`).
3810        let validate = kind != SyntaxKind::Comment
3811            || self.error_count() > 0
3812            || !self.diagnostics_of(x).is_empty();
3813        let prev = self.nav_prev(x);
3814        let (_, span) = if validate {
3815            self.splice_leaving_warnings(parent, prev, vec![x], Some(fragment))?
3816        } else {
3817            self.splice(parent, prev, &[x], Some(fragment), false)?
3818        };
3819        Ok(self.inserted(span)?.first)
3820    }
3821
3822    /// [`SyntaxTree::splice`] of a replacement of `roots`, validated.
3823    /// With `lenient_inline_colons`, a
3824    /// warning attached to the element right after `roots` whose labels
3825    /// all lie inside the removed bytes (a `Y0028` on the line break after
3826    /// a lenient `k: a: b` value) leaves with them when the edit is refused
3827    /// with it: the edit is then applied again with that warning dropped
3828    /// (`Edits::dropped`; the element and its handle stay), and the
3829    /// re-read decides. The one-splice edit, which keeps the warning, is
3830    /// tried first, so it stays when the new text reads with it again
3831    /// (e.g. a scalar replaced by a copy of itself); a refused edit
3832    /// changes nothing, so the retry starts from the same tree (the
3833    /// fragment is cloned for it only when such a warning exists).
3834    fn splice_leaving_warnings(
3835        &mut self,
3836        parent: u32,
3837        prev: Option<u32>,
3838        roots: Vec<u32>,
3839        fragment: Option<Fragment>,
3840    ) -> Result<Spliced, TreeEditError> {
3841        let Some((next, nths)) = self.orphaned_warnings(&roots)? else {
3842            return self.splice(parent, prev, &roots, fragment, true);
3843        };
3844        match self.splice(parent, prev, &roots, fragment.clone(), true) {
3845            Err(TreeEditError::NotWellFormed) => {}
3846            done => return done,
3847        }
3848        let drops: Vec<(u32, u32)> = nths.into_iter().map(|n| (next, n)).collect();
3849        self.splice_dropping(parent, prev, &roots, fragment, true, &drops)
3850    }
3851
3852    /// For the removal of `roots`: the element right after them, and the
3853    /// positions (in its list) of the warnings attached to it whose labels
3854    /// all lie inside the removed bytes (see
3855    /// [`SyntaxTree::splice_leaving_warnings`]); `None` when there is no
3856    /// such warning. O(its diagnostics).
3857    fn orphaned_warnings(&self, roots: &[u32]) -> Result<Option<(u32, Vec<u32>)>, TreeEditError> {
3858        let (Some(&f), Some(&l)) = (roots.first(), roots.last()) else {
3859            return Ok(None);
3860        };
3861        let Some(next) = self.nav_after(l) else {
3862            return Ok(None);
3863        };
3864        // The common case (no diagnostic there) costs a lookup.
3865        let Some(loc) = self.locate(next) else {
3866            return Ok(None);
3867        };
3868        if loc.flat.diagnostics.is_empty() {
3869            return Ok(None);
3870        }
3871        let list = loc.flat.diagnostics_at(loc.local);
3872        if list.is_empty() {
3873            return Ok(None);
3874        }
3875        let lo = self.nav_bytes(f).ok_or(TreeEditError::Internal)?.0;
3876        let hi = self.nav_bytes(l).ok_or(TreeEditError::Internal)?.1;
3877        let mut nths = Vec::new();
3878        let from = loc.flat.start(loc.local);
3879        let to = self.nav_bytes(next).ok_or(TreeEditError::Internal)?.0;
3880        let to = usize::try_from(to).map_err(|_| TreeEditError::Internal)?;
3881        for (k, (_, d)) in list.iter().enumerate() {
3882            if self.is_dropped(next, k) {
3883                continue;
3884            }
3885            // Every label and fix inside: the earliest start and the
3886            // latest end (what a skeleton keeps).
3887            let s = super::arena::shift_span(Span::new(d.first_start(), d.last_end()), from, to);
3888            let inside = lo <= s.start as u64 && s.end as u64 <= hi;
3889            if d.severity() == oneyaml_core::Severity::Warning && inside {
3890                nths.push(u32::try_from(k).map_err(|_| TreeEditError::Capacity)?);
3891            }
3892        }
3893        Ok((!nths.is_empty()).then_some((next, nths)))
3894    }
3895}
3896
3897/// The heap a diagnostic owns (its strings and vectors, by capacity), for
3898/// [`Edits::heap_bytes`].
3899#[cfg(test)]
3900fn diagnostic_heap_bytes(d: &Diagnostic) -> usize {
3901    use core::mem::size_of;
3902    use oneyaml_core::{Label, PathSegment, Replacement, Suggestion};
3903    let label = |l: &Label| l.message.capacity();
3904    let mut n = d.message.capacity();
3905    n = n.saturating_add(label(&d.primary));
3906    n = n.saturating_add(d.secondary.capacity().saturating_mul(size_of::<Label>()));
3907    n = d.secondary.iter().map(label).fold(n, usize::saturating_add);
3908    n = n.saturating_add(d.help.as_ref().map_or(0, String::capacity));
3909    if let Some(p) = &d.path {
3910        n = n.saturating_add(p.segments().len().saturating_mul(size_of::<PathSegment>()));
3911        for s in p.segments() {
3912            if let PathSegment::Key(k) = s {
3913                n = n.saturating_add(k.capacity());
3914            }
3915        }
3916    }
3917    n = n.saturating_add(
3918        d.suggestions
3919            .capacity()
3920            .saturating_mul(size_of::<Suggestion>()),
3921    );
3922    for s in &d.suggestions {
3923        n = n.saturating_add(s.message.capacity());
3924        n = n.saturating_add(s.edits.capacity().saturating_mul(size_of::<Replacement>()));
3925        n = s
3926            .edits
3927            .iter()
3928            .map(|e| e.text.capacity())
3929            .fold(n, usize::saturating_add);
3930    }
3931    n
3932}
3933
3934/// Local elements `a..b` of `flat` are all stream-level trivia tokens:
3935/// children of the stream (`base`: local parent 0), or roots of an arena
3936/// inserted into the stream. A range longer than [`LONG_RUN`] is one only
3937/// inside a long run `facts` records; a shorter one is read element by
3938/// element. O(`LONG_RUN` + log).
3939fn all_stream_trivia(flat: Flat<'_>, facts: &StreamFacts, base: bool, a: u32, b: u32) -> bool {
3940    let (a, b) = (a as usize, b as usize);
3941    if b <= a {
3942        return true;
3943    }
3944    if b.saturating_sub(a) > LONG_RUN {
3945        return facts.run_start(b.saturating_sub(1)).is_some_and(|s| s <= a);
3946    }
3947    (a..b).all(|i| {
3948        let level = if base {
3949            flat.parent(i) == Some(0)
3950        } else {
3951            flat.parent(i).is_none()
3952        };
3953        level && flat.kind(i).is_some_and(|k| k.is_trivia() && k.is_token())
3954    })
3955}
3956
3957/// Reads `text` as one token of `kind` through the parser, under
3958/// `settings`, and copies that token out.
3959pub(super) fn token_fragment(
3960    kind: SyntaxKind,
3961    text: &str,
3962    flow: bool,
3963    settings: &Settings,
3964) -> Result<Fragment, TreeEditError> {
3965    let bad = TreeEditError::InvalidToken { kind };
3966    let scalarish = matches!(
3967        kind,
3968        SyntaxKind::PlainScalar
3969            | SyntaxKind::SingleQuotedScalar
3970            | SyntaxKind::DoubleQuotedScalar
3971            | SyntaxKind::AliasName
3972            | SyntaxKind::Anchor
3973    );
3974    let empty_plain = kind == SyntaxKind::PlainScalar && text.is_empty();
3975    let src = if empty_plain {
3976        // An anchor on an empty node: its text token is the empty plain
3977        // scalar wanted.
3978        "&x".to_owned()
3979    } else if flow && scalarish {
3980        format!("[{text}]")
3981    } else {
3982        text.to_owned()
3983    };
3984    let tree = SyntaxTree::parse_with(src, settings);
3985    if tree.has_errors() {
3986        return Err(bad);
3987    }
3988    let wrapped = flow && scalarish && !empty_plain;
3989    let mut found = None;
3990    for n in tree.root().descendants().filter(|n| n.is_token()) {
3991        let k = n.kind();
3992        if wrapped
3993            && matches!(
3994                k,
3995                SyntaxKind::FlowSequenceOpen | SyntaxKind::FlowSequenceClose
3996            )
3997        {
3998            continue;
3999        }
4000        if empty_plain && k != SyntaxKind::PlainScalar {
4001            continue;
4002        }
4003        if n.text().is_empty() && !empty_plain {
4004            continue;
4005        }
4006        if found.is_some() {
4007            return Err(bad);
4008        }
4009        found = Some(n);
4010    }
4011    let token = found.ok_or(bad)?;
4012    if token.kind() != kind || token.text() != text {
4013        return Err(bad);
4014    }
4015    let (arena, _) = tree.copy_forest(&[token.slot()])?;
4016    Ok(Fragment {
4017        arena,
4018        context: String::new(),
4019        has_tags: false,
4020    })
4021}
4022
4023#[cfg(test)]
4024mod tests {
4025    #![allow(
4026        clippy::unwrap_used,
4027        clippy::expect_used,
4028        clippy::indexing_slicing,
4029        clippy::arithmetic_side_effects
4030    )]
4031
4032    use super::*;
4033    use crate::tree::Fragment;
4034    use crate::tree::fragment::tags_outside_documents;
4035
4036    /// Memory, deterministically: after k edits the overlay holds at most
4037    /// 1 + 3k runs and 4k link overrides, whatever the document's size;
4038    /// the first edit costs one run.
4039    #[test]
4040    fn overlay_size_depends_on_edits_not_on_the_document() {
4041        for entries in [10usize, 10_000] {
4042            let src: String = (0..entries).map(|i| format!("k{i}: [a, b]\n")).collect();
4043            let mut tree = SyntaxTree::parse(src);
4044            let targets: Vec<NodeId> = tree
4045                .root()
4046                .descendants()
4047                .filter(|n| n.kind() == SyntaxKind::FlowSequence)
4048                .map(|n| n.id())
4049                .step_by((entries / 10).max(1))
4050                .take(10)
4051                .collect();
4052            let mut k = 0usize;
4053            for id in targets {
4054                let first = tree.get(id).unwrap().children().nth(1).unwrap().id();
4055                let f = Fragment::parse("zz").unwrap();
4056                let _ = tree.replace(first, f).unwrap();
4057                k += 1;
4058                let e = tree.edits.as_deref().unwrap();
4059                assert!(e.runs.len() <= 1 + 3 * k, "{} runs after {k}", e.runs.len());
4060                assert!(e.links.len() <= 4 * k, "{} links after {k}", e.links.len());
4061            }
4062            // Cutting at an existing boundary adds no run.
4063            let slot = tree.root().first_child().unwrap().slot();
4064            let before = tree.edits.as_deref().unwrap().runs.len();
4065            let a = tree.cut_before(slot).unwrap();
4066            let b = tree.cut_before(slot).unwrap();
4067            assert_eq!(a, b);
4068            assert!(tree.edits.as_deref().unwrap().runs.len() <= before + 1);
4069            assert_eq!(tree.emit().matches("zz").count(), 10.min(entries));
4070        }
4071    }
4072
4073    /// `n` toggles of the first plain scalar of `tree` between `x` and `y`.
4074    fn toggle(tree: &mut SyntaxTree, n: usize) {
4075        let mut id = tree
4076            .root()
4077            .descendants()
4078            .find(|x| x.kind() == SyntaxKind::PlainScalar)
4079            .unwrap()
4080            .id();
4081        for i in 0..n {
4082            id = tree
4083                .replace_token(id, if i % 2 == 0 { "x" } else { "y" })
4084                .unwrap();
4085        }
4086    }
4087
4088    /// Memory retained after edits stays within the budget:
4089    /// 100k token toggles retain
4090    /// what 100 retain, on a 15-byte and on a 3 KB document (keeping
4091    /// every inserted arena and its link overrides would grow with the
4092    /// edits). Estimated from the overlay's containers (see
4093    /// [`Edits::heap_bytes`] on exact counting); the slots of
4094    /// dropped arenas resolve to nothing, and a fork copies what is live.
4095    /// (the estimate counts the dropped-warning set and the heap
4096    /// inside diagnostics too.)
4097    #[test]
4098    #[ignore = "slow: runs in CI"]
4099    fn toggles_retain_what_the_tree_holds_not_the_history() {
4100        let big: String = (0..300).map(|i| format!("key{i}: v\n")).collect();
4101        for src in ["a: [q, y]\nb: 1\n".to_owned(), format!("a: q\n{big}")] {
4102            let base = SyntaxTree::parse(src.as_str());
4103            let bytes = |t: &SyntaxTree| t.edits.as_deref().unwrap().heap_bytes();
4104            let mut few = base.clone();
4105            toggle(&mut few, 100);
4106            let mut many = base.clone();
4107            let first = many
4108                .root()
4109                .descendants()
4110                .find(|x| x.kind() == SyntaxKind::PlainScalar)
4111                .unwrap()
4112                .id();
4113            toggle(&mut many, 100_000);
4114            let (f, m) = (bytes(&few), bytes(&many));
4115            eprintln!("{} B: 100 toggles keep {f} B, 100k keep {m} B", src.len());
4116            assert!(
4117                m <= f + 256,
4118                "{} B: 100 toggles keep {f} B, 100k keep {m} B",
4119                src.len()
4120            );
4121            assert!(m < 2048, "{m} B retained");
4122            let e = many.edits.as_deref().unwrap();
4123            assert!(e.arenas.len() <= 1, "{} arenas", e.arenas.len());
4124            assert!(e.links.len() <= 4, "{} link overrides", e.links.len());
4125            // Slots of dropped arenas resolve to nothing (stale), never a
4126            // stub; the base slot the first toggle removed is stale too.
4127            assert!(many.get(first).is_err());
4128            let base_len = u32::try_from(many.kinds.len()).unwrap();
4129            let live: Vec<u32> = (base_len..e.next_slot())
4130                .filter(|s| many.kind_of(*s).is_some())
4131                .collect();
4132            assert_eq!(live.len(), 1, "{live:?}");
4133            assert!(many.is_live(live[0]));
4134            // The fork copies what is live.
4135            let fork = many.fork();
4136            assert!(bytes(&fork) <= m, "{} > {m}", bytes(&fork));
4137            assert_eq!(fork.emit(), many.emit());
4138            assert_eq!(many, SyntaxTree::parse(many.emit()));
4139        }
4140    }
4141
4142    /// Reads keep nothing. Reading the text,
4143    /// spans, and diagnostics of every element leaves the overlay exactly
4144    /// as the edits left it (before the fix, every ancestor's text was
4145    /// copied into a per-node cache on first read).
4146    #[test]
4147    fn reads_leave_the_overlay_untouched() {
4148        let src = "a:\n  b:\n    - [x, y]\n    - z # c\nq: [1\n";
4149        let mut tree = SyntaxTree::parse(src);
4150        let x = tree
4151            .root()
4152            .descendants()
4153            .find(|n| n.kind() == SyntaxKind::PlainScalar && n.text() == "x")
4154            .unwrap()
4155            .id();
4156        tree.replace_token(x, "xx").unwrap();
4157        let before = format!("{:?}", tree.edits);
4158        let mut total = 0usize;
4159        for n in tree.root().descendants() {
4160            total += n.text().len() + n.span().len();
4161            total += n.ancestors().map(|a| a.text().len()).sum::<usize>();
4162            total += tree.diagnostics_within(n).count();
4163            total += usize::from(n.diagnostic().is_some());
4164        }
4165        total += tree.diagnostics().count();
4166        assert!(total > 0);
4167        assert_eq!(format!("{:?}", tree.edits), before);
4168        // Split nodes' texts are built, tokens' are borrowed.
4169        let seq = tree
4170            .root()
4171            .descendants()
4172            .find(|n| n.kind() == SyntaxKind::FlowSequence)
4173            .unwrap();
4174        assert!(matches!(seq.text(), Cow::Owned(_)));
4175        assert_eq!(seq.text(), "[xx, y]");
4176        let tok = seq.children().nth(1).unwrap().first_child().unwrap();
4177        assert!(matches!(tok.text(), Cow::Borrowed("xx")));
4178    }
4179
4180    /// `copy_forest`'s open-document count says what the O(n)
4181    /// scan says, on every sibling range of every suite-like shape.
4182    #[test]
4183    fn copied_tag_flags_agree_with_a_scan() {
4184        for src in [
4185            "--- !t a\n--- [!t b]\n",
4186            "- !t [!u a, &x !v b]\n- c\n",
4187            "%TAG !e! tag:e,2000:\n--- !e!x\n- !e!y z\n",
4188            "!t\n",
4189        ] {
4190            let tree = SyntaxTree::parse(src);
4191            for n in tree.root().descendants() {
4192                let mut last = n;
4193                for _ in 0..3 {
4194                    let (arena, has_tags) = tree.copy_forest(&[last.slot()]).unwrap();
4195                    assert_eq!(has_tags, tags_outside_documents(&arena), "{src:?} {n:?}");
4196                    match last.next_sibling() {
4197                        Some(s) => last = s,
4198                        None => break,
4199                    }
4200                }
4201                let mut roots = vec![n.slot()];
4202                let mut at = n.next_sibling();
4203                while let Some(s) = at {
4204                    roots.push(s.slot());
4205                    at = s.next_sibling();
4206                }
4207                let (arena, has_tags) = tree.copy_forest(&roots).unwrap();
4208                assert_eq!(has_tags, tags_outside_documents(&arena), "{src:?} {n:?}");
4209            }
4210        }
4211    }
4212
4213    /// Every copy through slices equals the element walk's, for every
4214    /// element and sibling range of `tree`.
4215    /// Returns how many elements were copied as slices.
4216    fn assert_slices_copy_as_the_walk(tree: &SyntaxTree, what: &str) -> usize {
4217        let mut sliced = 0;
4218        for n in tree.root().descendants() {
4219            let mut out = Arena::default();
4220            if tree
4221                .copy_slice(n.slot(), &mut out, &mut Vec::new(), &mut false)
4222                .unwrap()
4223            {
4224                sliced += 1;
4225            }
4226            let mut roots = vec![n.slot()];
4227            let mut at = n.next_sibling();
4228            for _ in 0..3 {
4229                let one = [*roots.last().unwrap()];
4230                for r in [&one[..], &roots[..]] {
4231                    let fast = tree.copy_forest_with(r, true);
4232                    let walk = tree.copy_forest_with(r, false);
4233                    assert_eq!(fast, walk, "{what}: {n:?} {r:?}");
4234                }
4235                match at {
4236                    Some(s) => {
4237                        roots.push(s.slot());
4238                        at = s.next_sibling();
4239                    }
4240                    None => break,
4241                }
4242            }
4243        }
4244        sliced
4245    }
4246
4247    /// `copy_slice` writes exactly what the element walk
4248    /// writes (kinds, links, words, text, extras with their block headers
4249    /// and `%TAG` prefixes, diagnostics with dropped warnings left out, the
4250    /// tag flag), over the yaml-test-suite (strict and lenient) and shapes
4251    /// of its own, parsed and after edits that cut subtrees into pieces.
4252    #[test]
4253    fn slice_copies_equal_the_element_walk() {
4254        let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR"))
4255            .join("../test-suite/data/yaml-test-suite");
4256        let mut stack = vec![dir];
4257        let mut inputs = Vec::new();
4258        while let Some(d) = stack.pop() {
4259            for e in std::fs::read_dir(&d).unwrap() {
4260                let p = e.unwrap().path();
4261                if p.is_dir() {
4262                    stack.push(p);
4263                } else if p.file_name().is_some_and(|n| n == "in.yaml") {
4264                    inputs.push(std::fs::read_to_string(&p).unwrap());
4265                }
4266            }
4267        }
4268        assert!(inputs.len() > 300);
4269        inputs.extend(
4270            [
4271                "k: |+ # c\n  x\n\n ",
4272                "- &a !t |2-\n   x\n- >\n  y\n- [!u a, b]\n",
4273                "%TAG !e! tag:e,2000:\n--- !e!x\n- !e!y z\n- {a: !e!w |\n  q\n}\n",
4274                "k: a: b\nm: 1\nn: [x: y: z]\n",
4275                "a: [1, 2\nb: }\n- c\n",
4276            ]
4277            .iter()
4278            .map(|s| (*s).to_owned()),
4279        );
4280        // (Edits at its start leave most of it in pieces of one run.)
4281        inputs.push((0..200).map(|i| format!("k{i}: [a, {{b: c}}]\n")).collect());
4282        let lenient = Settings::new().lenient_inline_colons(true);
4283        let (mut parsed, mut cut) = (0, 0);
4284        for src in &inputs {
4285            for settings in [&Settings::new(), &lenient] {
4286                let mut tree = SyntaxTree::parse_with(src.as_str(), settings);
4287                parsed += assert_slices_copy_as_the_walk(&tree, src);
4288                // Edits: removals and insertions cut subtrees into runs.
4289                let scalars: Vec<NodeId> = tree
4290                    .root()
4291                    .descendants()
4292                    .filter(|n| n.kind() == SyntaxKind::Scalar)
4293                    .map(|n| n.id())
4294                    .collect();
4295                let mut edited = false;
4296                for (i, id) in scalars.iter().enumerate().take(6) {
4297                    let ok = match i % 3 {
4298                        0 => tree.remove(*id).is_ok(),
4299                        1 => {
4300                            let f = Fragment::parse("x").unwrap();
4301                            tree.insert_after(*id, f).is_ok()
4302                        }
4303                        _ => {
4304                            let f = Fragment::parse("yy").unwrap();
4305                            tree.replace(*id, f).is_ok()
4306                        }
4307                    };
4308                    edited |= ok;
4309                }
4310                if edited {
4311                    cut += assert_slices_copy_as_the_walk(&tree, src);
4312                }
4313            }
4314        }
4315        // (Both paths ran: slices for most subtrees, parsed or edited.)
4316        assert!(parsed > 20_000 && cut > 5_000, "{parsed} {cut}");
4317    }
4318
4319    /// Deterministically: copying a large subtree that an
4320    /// edit elsewhere left whole (one run) takes a constant number of
4321    /// overlay lookups, not one per element as the walk does; the copy is
4322    /// the walk's.
4323    #[test]
4324    fn copying_a_whole_subtree_looks_up_a_constant() {
4325        let mut lookups = Vec::new();
4326        for n in [100usize, 10_000] {
4327            let mut src = String::from("a: 1\nbig:\n");
4328            for i in 0..n {
4329                src.push_str(&format!("  k{i}: [v, {{w: {i}}}] # c\n"));
4330            }
4331            let mut tree = SyntaxTree::parse(src.as_str());
4332            let one = tree
4333                .root()
4334                .descendants()
4335                .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "1")
4336                .unwrap()
4337                .id();
4338            let _ = tree.replace(one, Fragment::parse("2").unwrap()).unwrap();
4339            assert!(tree.is_edited());
4340            let big = tree
4341                .root()
4342                .descendants()
4343                .filter(|x| x.kind() == SyntaxKind::BlockMapping)
4344                .nth(1)
4345                .unwrap()
4346                .slot();
4347            cost::take();
4348            let fast = tree.copy_forest(&[big]).unwrap();
4349            let (l, _) = cost::take();
4350            lookups.push(l);
4351            let walk = tree.copy_forest_with(&[big], false).unwrap();
4352            let (w, _) = cost::take();
4353            assert_eq!(fast, walk);
4354            assert!(w as usize > n, "{w}");
4355        }
4356        assert!(lookups.iter().all(|l| *l <= 8), "{lookups:?}");
4357    }
4358
4359    /// An item space that runs out part-way through an
4360    /// edit leaves the tree, its text, and its handles as they were.
4361    #[test]
4362    fn capacity_failures_leave_the_tree_unchanged() {
4363        let src = "k: [a, b, c]\nv: {x: 1}\n";
4364        let mut tree = SyntaxTree::parse(src);
4365        let b = tree
4366            .root()
4367            .descendants()
4368            .find(|n| n.kind() == SyntaxKind::Scalar && n.text() == "b")
4369            .unwrap()
4370            .id();
4371        // A first edit so the overlay exists, then a tight item space.
4372        let c = tree
4373            .root()
4374            .descendants()
4375            .find(|n| n.kind() == SyntaxKind::Scalar && n.text() == "c")
4376            .unwrap()
4377            .id();
4378        let _ = tree.replace(c, Fragment::parse("cc").unwrap()).unwrap();
4379        let text = tree.emit();
4380        let all: Vec<(NodeId, Span)> = tree
4381            .root()
4382            .descendants()
4383            .map(|n| (n.id(), n.span()))
4384            .collect();
4385        let links = tree.edits.as_deref().unwrap().links.clone();
4386        // Two cuts need two items (the removed run frees one for the
4387        // insertion): with none or one to spare the edit fails part-way.
4388        for spare in [0, 1] {
4389            let seq = &mut tree.edits.as_deref_mut().unwrap().seq;
4390            seq.limit_items(seq.items_len() + spare);
4391            let r = tree.replace(b, Fragment::parse("[q]").unwrap());
4392            assert_eq!(r.err(), Some(TreeEditError::Capacity), "spare {spare}");
4393            assert_eq!(tree.emit(), text);
4394            for (id, span) in &all {
4395                assert_eq!(tree.get(*id).unwrap().span(), *span);
4396            }
4397            assert_eq!(tree.edits.as_deref().unwrap().links, links);
4398            assert!(tree.edits.as_deref().unwrap().arenas.len() == 1);
4399        }
4400        let seq = &mut tree.edits.as_deref_mut().unwrap().seq;
4401        seq.limit_items(seq.items_len() + 2);
4402        let _ = tree.replace(b, Fragment::parse("[q]").unwrap()).unwrap();
4403        assert_eq!(tree.emit(), "k: [a, [q], cc]\nv: {x: 1}\n");
4404    }
4405
4406    /// (start, code) of the diagnostics `scan_diagnostics` visits from
4407    /// `slot` in one direction, up to `bound`.
4408    fn scanned(t: &SyntaxTree, slot: u32, forward: bool, bound: u64) -> Vec<(u64, String)> {
4409        let mut out = Vec::new();
4410        t.scan_diagnostics(slot, forward, bound, |x| {
4411            let mut d = x.diagnostic.clone();
4412            d.shift(x.from, x.to);
4413            out.push((x.start, format!("{} {:?}", d.code(), d.span())));
4414            true
4415        });
4416        out
4417    }
4418
4419    /// The diagnostic scan visits exactly the diagnostics the
4420    /// full list has on each side of every element, spans moved, edited
4421    /// or not; and a subtree's errors are found from its last diagnostic
4422    /// (errors end their document's content).
4423    #[test]
4424    fn diagnostic_scans_agree_with_the_full_list() {
4425        let lenient = Settings::new().lenient_inline_colons(true);
4426        let src = "%YAML 1.1\n--- \na: b: c\nd: [e, f]\ng: h: i\n--- \nx: y: z\nk: [1\n...\nq: r\n";
4427        let mut tree = SyntaxTree::parse_with(src, &lenient);
4428        let check = |t: &SyntaxTree| {
4429            let all: Vec<(u64, u64, String)> = t
4430                .diagnostics_by_element()
4431                .filter_map(|(n, d)| {
4432                    let n = n?;
4433                    Some((
4434                        n.preorder_index() as u64,
4435                        n.span().start as u64,
4436                        format!("{} {:?}", d.code, d.primary.span),
4437                    ))
4438                })
4439                .collect();
4440            let total = t.nav_total().0;
4441            for n in t.root().descendants() {
4442                let rank = n.preorder_index() as u64;
4443                let fwd: Vec<(u64, String)> = all
4444                    .iter()
4445                    .filter(|(r, _, _)| *r >= rank)
4446                    .map(|(_, s, d)| (*s, d.clone()))
4447                    .collect();
4448                assert_eq!(scanned(t, n.slot(), true, total), fwd, "{n:?}");
4449                let back: Vec<(u64, String)> = all
4450                    .iter()
4451                    .rev()
4452                    .filter(|(r, _, _)| *r <= rank)
4453                    .map(|(_, s, d)| (*s, d.clone()))
4454                    .collect();
4455                assert_eq!(scanned(t, n.slot(), false, 0), back, "{n:?}");
4456                // Bounded to the subtree.
4457                let end = rank + n.descendants().len() as u64;
4458                let inside: Vec<(u64, String)> = all
4459                    .iter()
4460                    .filter(|(r, _, _)| *r >= rank && *r < end)
4461                    .map(|(_, s, d)| (*s, d.clone()))
4462                    .collect();
4463                assert_eq!(scanned(t, n.slot(), true, end), inside, "{n:?}");
4464                let errors = t
4465                    .diagnostics_within(n)
4466                    .any(|(_, d)| d.severity == oneyaml_core::Severity::Error);
4467                assert_eq!(t.has_errors_within(n.slot()), errors, "{n:?}");
4468            }
4469        };
4470        check(&tree);
4471        let find = |t: &SyntaxTree, text: &str| {
4472            t.root()
4473                .descendants()
4474                .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == text)
4475                .unwrap()
4476                .id()
4477        };
4478        let e = find(&tree, "e");
4479        let _ = tree.replace_token(e, "ee").unwrap();
4480        check(&tree);
4481        let a = find(&tree, "a");
4482        let _ = tree.replace_token(a, "aaa").unwrap();
4483        check(&tree);
4484        let r = find(&tree, "r");
4485        let _ = tree.replace_token(r, "rr").unwrap();
4486        check(&tree);
4487        assert_eq!(tree, SyntaxTree::parse_with(tree.emit(), &lenient));
4488    }
4489
4490    /// The invariant `has_errors_within` and `labels_cross`
4491    /// rest on, over the whole yaml-test-suite (strict and lenient): in a
4492    /// document, no warning is attached after an error.
4493    #[test]
4494    fn errors_are_the_last_diagnostics_of_their_document() {
4495        let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR"))
4496            .join("../test-suite/data/yaml-test-suite");
4497        let mut stack = vec![dir];
4498        let mut inputs = Vec::new();
4499        while let Some(d) = stack.pop() {
4500            for e in std::fs::read_dir(&d).unwrap() {
4501                let p = e.unwrap().path();
4502                if p.is_dir() {
4503                    stack.push(p);
4504                } else if p.file_name().is_some_and(|n| n == "in.yaml") {
4505                    inputs.push(std::fs::read_to_string(&p).unwrap());
4506                }
4507            }
4508        }
4509        assert!(inputs.len() > 300);
4510        // Directive errors are followed by warnings
4511        // of later directives (and, lenient, of the content).
4512        inputs.extend(DIRECTIVE_ERRORS.iter().map(|s| (*s).to_owned()));
4513        let mut docs_with_errors = 0;
4514        let mut directive_errors = 0;
4515        for settings in [Settings::new(), Settings::new().lenient_inline_colons(true)] {
4516            for src in &inputs {
4517                let tree = SyntaxTree::parse_with(src.as_str(), &settings);
4518                for doc in tree.root().children() {
4519                    // Content errors end the content: after the `---`
4520                    // (or from the start without one), no warning follows
4521                    // an error.
4522                    let marker = doc
4523                        .children()
4524                        .find(|c| c.kind() == SyntaxKind::DocumentStartMarker)
4525                        .map_or(0, |m| m.preorder_index());
4526                    let all: Vec<_> = tree
4527                        .diagnostics_within(doc)
4528                        .map(|(n, d)| (n.map_or(usize::MAX, |n| n.preorder_index()), d))
4529                        .collect();
4530                    let content: Vec<_> = all
4531                        .iter()
4532                        .filter(|(at, _)| *at > marker)
4533                        .map(|(_, d)| d.severity)
4534                        .collect();
4535                    if let Some(i) = content
4536                        .iter()
4537                        .position(|s| *s == oneyaml_core::Severity::Error)
4538                    {
4539                        assert!(
4540                            content[i..]
4541                                .iter()
4542                                .all(|s| *s == oneyaml_core::Severity::Error),
4543                            "{src:?}: {content:?}"
4544                        );
4545                    }
4546                    // Errors before it are directive errors, and recorded.
4547                    let early = all
4548                        .iter()
4549                        .any(|(at, d)| *at < marker && d.severity == oneyaml_core::Severity::Error);
4550                    let recorded = doc.kind() == SyntaxKind::Document
4551                        && tree
4552                            .facts_at(doc.slot())
4553                            .is_some_and(|(f, l, _)| f.directive_error(l));
4554                    assert_eq!(early, recorded, "{src:?}");
4555                    directive_errors += usize::from(early);
4556                    let any = all
4557                        .iter()
4558                        .any(|(_, d)| d.severity == oneyaml_core::Severity::Error);
4559                    docs_with_errors += usize::from(any);
4560                    assert_eq!(tree.has_errors_within(doc.slot()), any, "{src:?}");
4561                }
4562                assert_eq!(tree.has_errors_within(0), tree.has_errors());
4563            }
4564        }
4565        assert!(docs_with_errors > 50, "{docs_with_errors}");
4566        assert!(
4567            directive_errors >= 2 * DIRECTIVE_ERRORS.len(),
4568            "{directive_errors}"
4569        );
4570    }
4571
4572    /// A line-end edit made of two splices checks the
4573    /// first one's labels with that splice's own shift (and the second's
4574    /// for the elements after the second). Swept over every range and
4575    /// line-end edit of inputs with `Y0028` warnings (labels before their
4576    /// element) next to block scalars and line breaks at other levels:
4577    /// accepted edits equal their re-parse, diagnostics and spans included
4578    /// (each on a fork of the tree, where its handles resolve).
4579    #[test]
4580    fn pair_edits_check_labels_in_each_splices_own_text() {
4581        let lenient = Settings::new().lenient_inline_colons(true);
4582        let inputs = [
4583            "a:\n  b: 1\nc: d: e\n",
4584            "a:\n  b: |\n    x\nc: d: e\nf: g\n",
4585            "- k: v\n- p: q: r\n",
4586            "a:\n  - x: y: z\n  - w\nb: c: d\n",
4587        ];
4588        let withs = ["|\n  new\n", "n: m: o\n", "9\n", ">-\n  f\n\n"];
4589        let (mut accepted, mut pairs) = (0usize, 0usize);
4590        for src in inputs {
4591            let tree = SyntaxTree::parse_with(src, &lenient);
4592            assert!(tree.diagnostics().len() > 0, "{src:?}");
4593            for n in tree.root().descendants() {
4594                for with in withs {
4595                    let Ok(f) = Fragment::parse_with(with, &lenient) else {
4596                        continue;
4597                    };
4598                    for insert in [false, true] {
4599                        let mut e = tree.fork();
4600                        let arenas =
4601                            |t: &SyntaxTree| t.edits.as_deref().map_or(0, |e| e.arenas.len());
4602                        let r = if insert {
4603                            e.insert_line_after(n.id(), f.clone()).map(|_| ())
4604                        } else {
4605                            e.replace_to_line_end(n.id(), n.id(), f.clone()).map(|_| ())
4606                        };
4607                        if r.is_ok() {
4608                            accepted += 1;
4609                            pairs += usize::from(arenas(&e) > 1);
4610                            let again = SyntaxTree::parse_with(e.emit(), &lenient);
4611                            assert_eq!(e, again, "{src:?} {n:?} {with:?} {insert}");
4612                        }
4613                    }
4614                }
4615            }
4616        }
4617        assert!(
4618            accepted > 20 && pairs > 5,
4619            "{accepted} accepted, {pairs} pairs"
4620        );
4621    }
4622
4623    /// Documents whose directives hold an error that
4624    /// later warnings follow.
4625    const DIRECTIVE_ERRORS: &[&str] = &[
4626        "%YAML 2.0\n%FOO bar\n---\na: 1\n",
4627        "%TAG !a! x\n%TAG !a! y\n%FOO\n--- a\n",
4628        "%YAML 1.1\n%YAML 1.2\n%FOO\n---\nk: a: b\n",
4629        "a: 1\n...\n%YAML 2.0\n%FOO\n--- [b]\n",
4630    ];
4631
4632    /// The backward pass of `labels_cross` may stop
4633    /// before a document's directive errors because they never cross: each
4634    /// is a zero-width error node whose labels are all at its own start.
4635    #[test]
4636    fn directive_errors_never_cross() {
4637        for settings in [Settings::new(), Settings::new().lenient_inline_colons(true)] {
4638            for src in DIRECTIVE_ERRORS {
4639                let tree = SyntaxTree::parse_with(*src, &settings);
4640                let mut seen = 0;
4641                for (n, d) in tree.diagnostics_by_element() {
4642                    let n = n.unwrap();
4643                    let in_directives = n.kind() == SyntaxKind::Error
4644                        && n.parent().is_some_and(|p| {
4645                            p.kind() == SyntaxKind::Document
4646                                && p.children().any(|c| {
4647                                    c.kind() == SyntaxKind::DocumentStartMarker
4648                                        && c.preorder_index() > n.preorder_index()
4649                                })
4650                        });
4651                    if !in_directives {
4652                        continue;
4653                    }
4654                    seen += 1;
4655                    let at = n.span().start;
4656                    assert!(n.span().is_empty(), "{src:?}");
4657                    assert_eq!(d.primary.span, Span::empty(at), "{src:?}");
4658                    assert!(d.secondary.iter().all(|l| l.span.start >= at));
4659                    assert!(
4660                        d.suggestions
4661                            .iter()
4662                            .all(|s| s.edits.iter().all(|e| e.span.start >= at))
4663                    );
4664                }
4665                assert!(seen >= 1, "{src:?}");
4666                // Edits after them are accepted exactly when the re-parse
4667                // agrees (the implication), errors included; each on a
4668                // fork, where the handle resolves.
4669                for n in tree.root().descendants() {
4670                    if n.kind() != SyntaxKind::PlainScalar {
4671                        continue;
4672                    }
4673                    let mut e = tree.fork();
4674                    if e.replace_token(n.id(), "zz").is_ok() {
4675                        assert_eq!(e, SyntaxTree::parse_with(e.emit(), &settings), "{src:?}");
4676                    }
4677                }
4678            }
4679        }
4680    }
4681
4682    /// What `errors_reach` and
4683    /// `before_errors` rely on when they stop scanning a document's errors
4684    /// (backwards) at the first one with a directive code
4685    /// (`validate::is_directive_error`): every such diagnostic in a
4686    /// document is a directive error (a zero-width error node before its
4687    /// `---`), and every error before it in the document is one too, unless
4688    /// the document is recorded as mixed (`facts.rs`), which the scans
4689    /// take, in O(1), as reaching every edit next to it. Over
4690    /// the yaml-test-suite, every fuzz corpus and the directive shapes,
4691    /// strict and lenient.
4692    #[test]
4693    fn directive_codes_mark_directive_errors_only() {
4694        let root = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("..");
4695        let mut stack = vec![
4696            root.join("test-suite/data/yaml-test-suite"),
4697            root.join("fuzz/corpus"),
4698            root.join("fuzz/regressions"),
4699        ];
4700        let mut inputs: Vec<String> = DIRECTIVE_ERRORS.iter().map(|s| (*s).to_owned()).collect();
4701        inputs.extend(
4702            [
4703                "%YAML 1.2\n%YAML 1.2\n---\na: x\nb: ]\n",
4704                "%TAG !t! a\n%TAG !t! b\n---\n- [x\n",
4705                "%YAML 2.0\n---\n'x\n\u{feff}y\n",
4706                "a: [x\n---\n%YAML 1.2\n%YAML 1.2\n",
4707                "%YAML 0.2\n----\nm\n...\n%YAML 1.2\n%YAML 1.2\n---\n",
4708            ]
4709            .map(str::to_owned),
4710        );
4711        while let Some(d) = stack.pop() {
4712            for e in std::fs::read_dir(&d).unwrap() {
4713                let p = e.unwrap().path();
4714                if p.is_dir() {
4715                    stack.push(p);
4716                } else if p.extension().is_none_or(|x| x != "md") {
4717                    let b = std::fs::read(&p).unwrap();
4718                    inputs.push(String::from_utf8_lossy(&b).into_owned());
4719                }
4720            }
4721        }
4722        assert!(inputs.len() > 3000, "{}", inputs.len());
4723        let mut seen = 0usize;
4724        let mut mixed_docs = 0usize;
4725        for settings in [Settings::new(), Settings::new().lenient_inline_colons(true)] {
4726            for src in &inputs {
4727                let tree = SyntaxTree::parse_with(src.as_str(), &settings);
4728                for doc in tree.root().children() {
4729                    if doc.kind() != SyntaxKind::Document {
4730                        continue;
4731                    }
4732                    let marker = doc
4733                        .children()
4734                        .find(|c| c.kind() == SyntaxKind::DocumentStartMarker)
4735                        .map(|m| m.preorder_index());
4736                    let all: Vec<_> = tree.diagnostics_within(doc).collect();
4737                    // Read backwards, as the scans do: once a directive
4738                    // code is met, only directive-coded errors (and
4739                    // warnings) come before it.
4740                    let mut past_directive = false;
4741                    let mut mixed = false;
4742                    for (n, d) in all.iter().rev() {
4743                        let directive = super::super::validate::is_directive_error(d.code);
4744                        if d.severity != oneyaml_core::Severity::Error {
4745                            continue;
4746                        }
4747                        if directive {
4748                            seen += 1;
4749                            let n = n.as_ref().unwrap();
4750                            assert_eq!(n.kind(), SyntaxKind::Error, "{src:?}");
4751                            assert!(n.span().is_empty(), "{src:?}");
4752                            assert!(
4753                                marker.is_some_and(|m| m > n.preorder_index()),
4754                                "{src:?}: a directive code after the document's `---`"
4755                            );
4756                            past_directive = true;
4757                        } else {
4758                            mixed |= past_directive;
4759                        }
4760                    }
4761                    // Such an error before a directive error (a failed
4762                    // directive block kept with the next directives) is
4763                    // recorded; the scans take it as reaching (O(1)).
4764                    let recorded = tree
4765                        .facts_at(doc.slot())
4766                        .is_some_and(|(f, l, _)| f.mixed_directive_error(l));
4767                    assert_eq!(mixed, recorded, "{src:?}");
4768                    mixed_docs += usize::from(mixed);
4769                }
4770            }
4771        }
4772        assert!(seen > 20, "{seen}");
4773        assert!(mixed_docs >= 2, "{mixed_docs}");
4774    }
4775
4776    /// A refused edit merges back the runs it split,
4777    /// so R grows only with accepted edits (at most 3 each), never with
4778    /// refusals.
4779    #[test]
4780    fn refused_edits_leave_the_runs_as_they_were() {
4781        let src = "a: 1\nb: [x, y, z]\nc: 3\nd: {k: v}\n";
4782        let mut tree = SyntaxTree::parse(src);
4783        let colon = |t: &SyntaxTree, n: usize| {
4784            t.root()
4785                .descendants()
4786                .filter(|x| x.kind() == SyntaxKind::MappingValue)
4787                .nth(n)
4788                .unwrap()
4789                .id()
4790        };
4791        // Refusals on an unedited tree leave no overlay.
4792        for n in 0..4 {
4793            assert_eq!(
4794                tree.remove(colon(&tree, n)),
4795                Err(TreeEditError::NotWellFormed)
4796            );
4797            assert!(!tree.is_edited());
4798        }
4799        let y = tree
4800            .root()
4801            .descendants()
4802            .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "y")
4803            .unwrap()
4804            .id();
4805        let _ = tree.replace_token(y, "yy").unwrap();
4806        let runs = tree.edits.as_deref().unwrap().runs.len();
4807        // The treap's storage reaches the peak of one attempt and reuses
4808        // freed items after that.
4809        let mut items = None;
4810        let text = tree.emit();
4811        for round in 0..20 {
4812            for n in 0..4 {
4813                let r = tree.remove(colon(&tree, n));
4814                assert_eq!(r, Err(TreeEditError::NotWellFormed), "{round} {n}");
4815            }
4816            let comma = tree
4817                .root()
4818                .descendants()
4819                .find(|x| x.kind() == SyntaxKind::FlowEntry)
4820                .unwrap()
4821                .id();
4822            assert_eq!(tree.remove(comma), Err(TreeEditError::NotWellFormed));
4823            let e = tree.edits.as_deref().unwrap();
4824            assert_eq!(e.runs.len(), runs, "runs grew after refusals");
4825            assert_eq!(*items.get_or_insert(e.seq.items_len()), e.seq.items_len());
4826        }
4827        assert_eq!(tree.emit(), text);
4828        assert_eq!(tree, SyntaxTree::parse(tree.emit()));
4829    }
4830
4831    /// The runs cover every live element's bytes;
4832    /// the read path's fallback (joining tokens) gives the same text, and
4833    /// a range past the end is an `Internal` error, never a truncation.
4834    #[test]
4835    fn text_ranges_are_covered_or_an_error() {
4836        let mut tree = SyntaxTree::parse("a:\n  b: [1, 2]\n  c: |\n    x\n# end\n");
4837        let one = tree
4838            .root()
4839            .descendants()
4840            .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "1")
4841            .unwrap()
4842            .id();
4843        let _ = tree.replace_token(one, "11").unwrap();
4844        let two = tree
4845            .root()
4846            .descendants()
4847            .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "2")
4848            .unwrap()
4849            .id();
4850        let _ = tree
4851            .replace(two, Fragment::parse("{z: 2}").unwrap())
4852            .unwrap();
4853        for n in tree.root().descendants() {
4854            let (a, b) = tree.nav_bytes(n.slot()).unwrap();
4855            let runs = tree.try_text_range(a, b).unwrap();
4856            assert_eq!(runs, tree.text_from_tokens(n.slot()), "{n:?}");
4857            assert_eq!(runs, n.text());
4858        }
4859        let total = tree.nav_total().1;
4860        assert_eq!(
4861            tree.try_text_range(total, total + 5),
4862            Err(TreeEditError::Internal)
4863        );
4864        assert_eq!(tree.try_text_range(0, total).unwrap(), tree.emit());
4865        assert_eq!(tree.byte_at(0), Some(b'a'));
4866        assert_eq!(tree.byte_at(total), None);
4867    }
4868
4869    /// Columns are counted in the parser's unit, bytes,
4870    /// edited or not (a count of characters put the re-read context in
4871    /// another place than the parser after non-ASCII text on a line).
4872    #[test]
4873    fn columns_are_bytes_as_the_parser_counts_them() {
4874        let src = "\u{e9}\u{1f600}: [a, b]\n";
4875        let mut tree = SyntaxTree::parse(src);
4876        let seq_at = src.find('[').unwrap() as u64;
4877        assert_eq!(tree.column_at(seq_at), Some(8));
4878        let a = tree
4879            .root()
4880            .descendants()
4881            .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "a")
4882            .unwrap()
4883            .id();
4884        let _ = tree.replace_token(a, "\u{2603}").unwrap();
4885        let b_at = tree.emit().find('b').unwrap() as u64;
4886        assert_eq!(tree.column_at(seq_at), Some(8));
4887        assert_eq!(tree.column_at(b_at), Some(14));
4888        assert_eq!(tree.column_at(0), Some(0));
4889    }
4890
4891    /// A fuzz finding: a byte order mark starts the line, as for the
4892    /// parser (`scan_trivia`), edited or not.
4893    #[test]
4894    fn columns_skip_a_byte_order_mark() {
4895        let src = "\u{feff}a: [b]\n--- \u{feff}\n";
4896        let mut tree = SyntaxTree::parse(src);
4897        assert_eq!(tree.column_at(3), Some(0));
4898        assert_eq!(tree.column_at(src.find('[').unwrap() as u64), Some(3));
4899        let b = tree
4900            .root()
4901            .descendants()
4902            .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "b")
4903            .unwrap()
4904            .id();
4905        let _ = tree.replace_token(b, "cc").unwrap();
4906        assert_eq!(tree.column_at(src.find('[').unwrap() as u64), Some(3));
4907        assert_eq!(tree.column_at(0), Some(0));
4908    }
4909
4910    /// The last leaf and the chain of last children agree
4911    /// with `nav_last` level by level, edited or not.
4912    #[test]
4913    fn last_chains_agree_with_last_children() {
4914        let mut tree = SyntaxTree::parse("a:\n  b:\n    - [x, {y: z}]\n    - q\nc: []\n");
4915        let check = |t: &SyntaxTree| {
4916            for n in t.root().descendants() {
4917                let mut want = vec![n.slot()];
4918                let mut at = n.slot();
4919                while let Some(l) = t.nav_last(at) {
4920                    want.push(l);
4921                    at = l;
4922                }
4923                assert_eq!(t.last_chain(n.slot()), want, "{n:?}");
4924                assert_eq!(t.nav_last_leaf(n.slot()), want.last().copied());
4925            }
4926        };
4927        check(&tree);
4928        let q = tree
4929            .root()
4930            .descendants()
4931            .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "q")
4932            .unwrap()
4933            .id();
4934        let _ = tree
4935            .replace(q, Fragment::parse("[r, [s]]").unwrap())
4936            .unwrap();
4937        check(&tree);
4938    }
4939
4940    /// `is_empty` agrees with `len`, edited or not.
4941    #[test]
4942    fn is_empty_agrees_with_len() {
4943        let mut tree = SyntaxTree::parse("[a]");
4944        assert!(!tree.is_empty());
4945        assert_eq!(tree.is_empty(), matches!(tree.len(), 0));
4946        let a = tree
4947            .root()
4948            .descendants()
4949            .find(|x| x.kind() == SyntaxKind::PlainScalar)
4950            .unwrap()
4951            .id();
4952        let _ = tree.replace_token(a, "b").unwrap();
4953        assert!(!tree.is_empty());
4954        assert_eq!(tree.is_empty(), matches!(tree.len(), 0));
4955    }
4956
4957    /// `unwrap_root` moves the element's warnings to
4958    /// its first child, and refuses an element without children that
4959    /// carries one (it would move to the next root or be dropped).
4960    #[test]
4961    fn unwrap_root_keeps_warnings() {
4962        let warning = Diagnostic::warning(
4963            oneyaml_core::code::YAML_VERSION_1_1,
4964            "w",
4965            oneyaml_core::Label::new(Span::new(0, 1), ""),
4966        );
4967        let mut f = Fragment::parse("[a, b]").unwrap();
4968        f.arena.diagnostics.push((0, Stored::full(warning.clone())));
4969        let g = f.unwrap_root(0).unwrap();
4970        assert_eq!(g.arena.diagnostics.len(), 1);
4971        let at = g.arena.diagnostics[0].0 as usize;
4972        assert_eq!(at, 0);
4973        assert_eq!(g.arena.flat().kind(at), Some(SyntaxKind::FlowSequenceOpen));
4974        // A hand-built childless root followed by another root.
4975        let mut f = Fragment::parse("x").unwrap();
4976        let arena = &mut f.arena;
4977        arena.kinds.insert(0, SyntaxKind::Alias);
4978        arena.parents.insert(0, NONE);
4979        arena.words.insert(0, 1);
4980        for p in arena.parents.iter_mut().skip(1) {
4981            if *p != NONE {
4982                *p += 1;
4983            }
4984        }
4985        for (i, w) in arena.words.iter_mut().enumerate().skip(1) {
4986            if !arena.kinds[i].is_token() {
4987                *w += 1;
4988            }
4989        }
4990        arena.diagnostics.push((0, Stored::full(warning)));
4991        assert_eq!(
4992            f.unwrap_root(0),
4993            Err(TreeEditError::ReadOnly {
4994                kind: SyntaxKind::Alias
4995            })
4996        );
4997    }
4998
4999    /// A document's leading comments are the
5000    /// stream's (C4), so `tag_context` stops at the document's first child
5001    /// when it has no directive: O(1), whatever the comments before it.
5002    #[test]
5003    fn tag_context_reads_only_directives() {
5004        let src = format!("{}a: !t x\n", "# c\n".repeat(1000));
5005        let tree = SyntaxTree::parse(src);
5006        let doc = tree
5007            .root()
5008            .children()
5009            .find(|x| x.kind() == SyntaxKind::Document)
5010            .unwrap();
5011        assert_eq!(doc.first_child().unwrap().kind(), SyntaxKind::BlockMapping);
5012        assert_eq!(tree.tag_context(doc.slot()), "");
5013        let tree = SyntaxTree::parse("# c\n%TAG !e! tag:e,2000:\n# d\n--- !e!x a\n");
5014        let doc = tree
5015            .root()
5016            .children()
5017            .find(|x| x.kind() == SyntaxKind::Document)
5018            .unwrap();
5019        assert_eq!(doc.first_child().unwrap().kind(), SyntaxKind::TagDirective);
5020        assert_eq!(tree.tag_context(doc.slot()), "%TAG !e! tag:e,2000:\n");
5021    }
5022
5023    /// A refused edit is undone exactly, including the removal of
5024    /// runs and the link overrides, and the tree then edits on normally.
5025    #[test]
5026    fn refused_edits_are_undone() {
5027        let src = "a: 1\nb: [x, y]\nc: 3\n";
5028        let mut tree = SyntaxTree::parse(src);
5029        let find = |t: &SyntaxTree, k: SyntaxKind, n: usize| {
5030            t.root()
5031                .descendants()
5032                .filter(|x| x.kind() == k)
5033                .nth(n)
5034                .unwrap()
5035                .id()
5036        };
5037        // Refused on an unedited tree: no overlay is left behind.
5038        let colon = find(&tree, SyntaxKind::MappingValue, 0);
5039        assert_eq!(tree.remove(colon), Err(TreeEditError::NotWellFormed));
5040        assert!(!tree.is_edited());
5041        let y = find(&tree, SyntaxKind::Scalar, 4);
5042        let _ = tree.replace(y, Fragment::parse("yy").unwrap()).unwrap();
5043        let text = tree.emit();
5044        let all: Vec<(NodeId, Span)> = tree
5045            .root()
5046            .descendants()
5047            .map(|n| (n.id(), n.span()))
5048            .collect();
5049        let links = tree.edits.as_deref().unwrap().links.clone();
5050        let arenas = tree.edits.as_deref().unwrap().arenas.len();
5051        // Removing the comma of `[x, yy]` gives `[x yy]`: one scalar.
5052        let comma = find(&tree, SyntaxKind::FlowEntry, 0);
5053        assert_eq!(tree.remove(comma), Err(TreeEditError::NotWellFormed));
5054        let map = find(&tree, SyntaxKind::BlockMapping, 0);
5055        assert_eq!(
5056            tree.append_child(map, Fragment::parse("x").unwrap()),
5057            Err(TreeEditError::NotWellFormed)
5058        );
5059        assert_eq!(tree.emit(), text);
5060        for (id, span) in &all {
5061            assert_eq!(tree.get(*id).unwrap().span(), *span);
5062        }
5063        let e = tree.edits.as_deref().unwrap();
5064        assert_eq!(e.links, links);
5065        assert_eq!(e.arenas.len(), arenas);
5066        // Still editable.
5067        let three = find(&tree, SyntaxKind::Scalar, 6);
5068        let _ = tree.replace(three, Fragment::parse("33").unwrap()).unwrap();
5069        assert_eq!(tree.emit(), "a: 1\nb: [x, yy]\nc: 33\n");
5070        assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5071    }
5072
5073    /// Every run's diagnostic count is its arena's count over its range,
5074    /// and the treap's sums add up (the scans skip runs by them).
5075    fn assert_diag_sums(tree: &SyntaxTree) {
5076        let e = tree.edits.as_deref().unwrap();
5077        let mut at = e.seq.first();
5078        let mut total = 0u64;
5079        while let Some(item) = at {
5080            let run = e.seq.run(item).unwrap();
5081            let (flat, _, _) = tree.arena_flat(run.arena).unwrap();
5082            assert_eq!(run.diags, flat.diagnostics_in(run.a, run.b), "{run:?}");
5083            total += run.diags;
5084            at = e.seq.next(item);
5085        }
5086        let listed = tree
5087            .diagnostics_by_element()
5088            .filter(|(n, _)| n.is_some())
5089            .count();
5090        // (warnings that left the tree stay counted in their
5091        // runs, and are skipped when read.)
5092        assert_eq!(total, (listed + e.dropped.len()) as u64);
5093    }
5094
5095    /// A dropped warning is recorded by its element's
5096    /// slot, undone with a refused edit, and released with its element.
5097    #[test]
5098    fn dropped_warnings_are_undone_and_released() {
5099        let settings = Settings::new().lenient_inline_colons(true);
5100        let mut tree = SyntaxTree::parse_with("k: a: b\nm: 1\n", &settings);
5101        let find = |t: &SyntaxTree, k: SyntaxKind, text: &str| {
5102            t.root()
5103                .descendants()
5104                .find(|x| x.kind() == k && x.text() == text)
5105                .unwrap()
5106                .id()
5107        };
5108        let v = find(&tree, SyntaxKind::PlainScalar, "a: b");
5109        let _ = tree.replace_token(v, "x").unwrap();
5110        let e = tree.edits.as_deref().unwrap();
5111        assert_eq!(e.dropped.len(), 1);
5112        assert_diag_sums(&tree);
5113        // A refused edit adds none.
5114        let colon = tree
5115            .root()
5116            .descendants()
5117            .find(|x| x.kind() == SyntaxKind::MappingValue)
5118            .unwrap()
5119            .id();
5120        assert_eq!(tree.remove(colon), Err(TreeEditError::NotWellFormed));
5121        assert_eq!(tree.edits.as_deref().unwrap().dropped.len(), 1);
5122        // Its element replaced: released.
5123        let brk = tree
5124            .root()
5125            .descendants()
5126            .find(|x| x.kind() == SyntaxKind::LineBreak)
5127            .unwrap()
5128            .id();
5129        let _ = tree.replace_token(brk, "\n").unwrap();
5130        assert!(tree.edits.as_deref().unwrap().dropped.is_empty());
5131        assert_diag_sums(&tree);
5132        assert_eq!(tree.diagnostics().count(), 0);
5133        assert_eq!(tree, SyntaxTree::parse_with(tree.emit(), &settings));
5134        // Refused as a whole: a value that reads as a lenient value with a
5135        // warning of its own elsewhere is refused twice, nothing dropped.
5136        let mut tree = SyntaxTree::parse_with("k: a: b\nm: 1\n", &settings);
5137        let node = tree
5138            .root()
5139            .descendants()
5140            .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "a: b")
5141            .unwrap()
5142            .id();
5143        let map = Fragment::parse("p: q").unwrap();
5144        assert_eq!(tree.replace(node, map), Err(TreeEditError::NotWellFormed));
5145        assert!(tree.edits.as_deref().is_none_or(|e| e.dropped.is_empty()));
5146        assert_eq!(tree.diagnostics().count(), 1);
5147    }
5148
5149    /// Every run's `trivia` flag says exactly whether all its elements
5150    /// are stream-level trivia tokens (the walks over
5151    /// stream-level trivia jump over the runs by it).
5152    fn assert_trivia_flags(tree: &SyntaxTree) {
5153        let Some(e) = tree.edits.as_deref() else {
5154            return;
5155        };
5156        let mut at = e.seq.first();
5157        while let Some(item) = at {
5158            let run = e.seq.run(item).unwrap();
5159            let all = (run.a..run.b).all(|l| {
5160                let slot = run.arena + l;
5161                tree.nav_parent(slot) == Some(0)
5162                    && tree.kind_of(slot).is_some_and(|k| k.is_trivia())
5163            });
5164            assert_eq!(run.trivia, all, "{run:?}");
5165            at = e.seq.next(item);
5166        }
5167    }
5168
5169    /// The facts of an inserted arena. A fragment of
5170    /// more than 64 stream-level trivia elements records its long run (so
5171    /// walks jump over it), whole or cut by later edits; an extracted
5172    /// document with a directive error (`%YAML 2.0`) inserted at stream
5173    /// level records it (so `has_errors_within` sees it without a scan).
5174    #[test]
5175    fn inserted_arenas_record_their_stream_facts() {
5176        let mut tree = SyntaxTree::parse("a: 1\n--- b\n");
5177        let doc_b = tree
5178            .root()
5179            .children()
5180            .filter(|x| x.kind() == SyntaxKind::Document)
5181            .nth(1);
5182        let doc_b = doc_b.unwrap().id();
5183        let comments = Fragment::parse(&"# c\n".repeat(40)).unwrap();
5184        assert_eq!(comments.len(), 80);
5185        let ins = tree.insert_before(doc_b, comments).unwrap();
5186        let first = tree.get(ins.first).unwrap().slot();
5187        let last = tree.get(ins.last).unwrap().slot();
5188        let (facts, local, _) = tree.facts_at(last).unwrap();
5189        assert_eq!(facts.run_start(local), Some(0));
5190        assert_eq!(facts.run_end(0), Some(79));
5191        assert_eq!(tree.trivia_run_start(last), first);
5192        assert_eq!(tree.trivia_run_end(first), last);
5193        assert_trivia_flags(&tree);
5194        // Cut in the middle: each piece is bounded by its overlay run.
5195        let mid = tree
5196            .root()
5197            .children()
5198            .filter(|x| x.kind() == SyntaxKind::Comment)
5199            .nth(20)
5200            .unwrap();
5201        let (mid_slot, mid_id) = (mid.slot(), mid.id());
5202        let new = tree.replace_token(mid_id, "# d").unwrap();
5203        let new_slot = tree.get(new).unwrap().slot();
5204        assert_eq!(tree.trivia_run_start(last), mid_slot + 1);
5205        assert_eq!(tree.trivia_run_end(first), mid_slot - 1);
5206        assert_eq!(tree.trivia_run_start(new_slot), new_slot);
5207        assert_trivia_flags(&tree);
5208        // `b` is edited with the whole run between it and `a: 1` jumped.
5209        let b = tree
5210            .root()
5211            .descendants()
5212            .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "b")
5213            .unwrap()
5214            .id();
5215        let _ = tree.replace_token(b, "bb").unwrap();
5216        assert_trivia_flags(&tree);
5217        assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5218        // A document with a directive error, extracted and inserted.
5219        let donor = SyntaxTree::parse("%YAML 2.0\n--- x\n");
5220        let bad = donor.root().first_child().unwrap();
5221        assert_eq!(bad.kind(), SyntaxKind::Document);
5222        let f = donor.extract(bad.id(), bad.id()).unwrap();
5223        // (After a document ended by `...`: a directive after an open one
5224        // would be its content.)
5225        let mut tree = SyntaxTree::parse("--- a\n...\n");
5226        let root = tree.root().id();
5227        let ins = tree.append_child(root, f).unwrap();
5228        let slot = tree.get(ins.first).unwrap().slot();
5229        let (facts, local, _) = tree.facts_at(slot).unwrap();
5230        assert!(facts.directive_error(local));
5231        assert!(tree.has_errors_within(slot));
5232        assert!(tree.has_errors());
5233        let first_doc = tree.root().first_child().unwrap().slot();
5234        assert!(!tree.has_errors_within(first_doc));
5235        assert_trivia_flags(&tree);
5236        assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5237    }
5238
5239    /// The runs' trivia flags stay exact
5240    /// through insertions, cuts, removals, merges, and refusals of
5241    /// stream-level trivia and documents; and the walks over them find
5242    /// what a step-by-step walk finds.
5243    #[test]
5244    fn trivia_flags_follow_every_edit() {
5245        let mut tree = SyntaxTree::parse(format!("a: 1\n{}--- b\n# t\n", "# c\n".repeat(70)));
5246        let mut rng = 0x5eed_u64;
5247        let mut next = |n: usize| {
5248            rng = rng.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
5249            (rng >> 33) as usize % n.max(1)
5250        };
5251        let pieces = ["# d\n", "\n", "--- z\n", "# e\n# f\n"];
5252        let mut accepted = 0usize;
5253        for round in 0..300 {
5254            let kids: Vec<NodeId> = tree.root().children().map(|x| x.id()).collect();
5255            let at = kids[next(kids.len())];
5256            match next(3) {
5257                0 => {
5258                    let f = Fragment::parse(pieces[next(pieces.len())]).unwrap();
5259                    accepted += usize::from(tree.insert_before(at, f).is_ok());
5260                }
5261                1 => accepted += usize::from(tree.remove(at).is_ok()),
5262                _ => {
5263                    let n = tree.get(at).unwrap();
5264                    if n.kind() == SyntaxKind::Comment {
5265                        let r = tree.replace_token(at, &format!("# r{round}"));
5266                        accepted += usize::from(r.is_ok());
5267                    }
5268                }
5269            }
5270            assert_trivia_flags(&tree);
5271            // Every stream child's content before and after, both ways.
5272            let kids: Vec<u32> = tree.root().children().map(|x| x.slot()).collect();
5273            for (i, &k) in kids.iter().enumerate() {
5274                let is_trivia = |s: &&u32| !tree.kind_of(**s).unwrap().is_trivia();
5275                let before = kids[..i].iter().rev().find(is_trivia).copied();
5276                let after = kids[i..].iter().find(is_trivia).copied();
5277                assert_eq!(tree.content_before(k).unwrap(), before, "round {round}");
5278                assert_eq!(tree.content_after(k).unwrap(), after, "round {round}");
5279            }
5280            assert_eq!(tree, SyntaxTree::parse(tree.emit()), "round {round}");
5281        }
5282        assert!(accepted > 150, "{accepted}");
5283        let runs = tree.edits.as_deref().unwrap().runs.len();
5284        assert!(runs > 20, "{runs} runs");
5285    }
5286
5287    /// An insertion and its removal
5288    /// leave no run behind (the base runs they cut are merged again), so R
5289    /// grows only with the edits whose text is still in the tree.
5290    #[test]
5291    fn insert_remove_pairs_leave_no_runs_behind() {
5292        let src: String = (0..200).map(|i| format!("- e{i}\n")).collect();
5293        let mut tree = SyntaxTree::parse(src.as_str());
5294        let t = SyntaxTree::parse("- x\n- z");
5295        let seq = t.root().first_child().unwrap().first_child().unwrap();
5296        let kids: Vec<_> = seq.children().collect();
5297        let entry = t.extract(kids[3].id(), kids[6].id()).unwrap();
5298        let values: Vec<NodeId> = tree
5299            .root()
5300            .descendants()
5301            .filter(|n| n.kind() == SyntaxKind::Scalar)
5302            .map(|n| n.id())
5303            .collect();
5304        let mut stale = Vec::new();
5305        for (k, id) in values.iter().enumerate().step_by(7) {
5306            let ins = tree.insert_after(*id, entry.clone()).unwrap();
5307            let _ = tree.remove_range(ins.first, ins.last).unwrap();
5308            stale.push(ins.first);
5309            let e = tree.edits.as_deref().unwrap();
5310            assert_eq!(e.runs.len(), 1, "runs left behind after pair {k}");
5311            assert_eq!(e.seq.total().0 as usize, tree.len());
5312        }
5313        assert_eq!(tree.emit().as_bytes(), src.as_bytes());
5314        for id in &values {
5315            assert!(tree.get(*id).is_ok());
5316        }
5317        for id in stale {
5318            assert!(tree.get(id).is_err());
5319        }
5320        // A replacement's text stays: its runs stay too, bounded as before.
5321        let _ = tree
5322            .replace(values[3], Fragment::parse("zz").unwrap())
5323            .unwrap();
5324        assert!(tree.edits.as_deref().unwrap().runs.len() <= 3);
5325        assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5326    }
5327
5328    /// A copy made while a group is open
5329    /// (`Clone` or `fork`) merges and releases what the group held back,
5330    /// exactly as ending the group does; the original's group is intact.
5331    #[test]
5332    fn copies_made_inside_a_group_settle_its_edits() {
5333        let src: String = (0..20).map(|i| format!("k{i}: v\n")).collect();
5334        let mut tree = SyntaxTree::parse(src.as_str());
5335        let mut ended = tree.clone();
5336        let edit = |t: &mut SyntaxTree| {
5337            toggle(t, 40);
5338            let s = t
5339                .root()
5340                .descendants()
5341                .filter(|x| x.kind() == SyntaxKind::Scalar)
5342                .nth(5)
5343                .unwrap()
5344                .id();
5345            let ins = t.insert_after(s, Fragment::parse("# c").unwrap());
5346            if let Ok(ins) = ins {
5347                let _ = t.remove(ins.first).unwrap();
5348            }
5349        };
5350        let mark = tree.begin_group();
5351        edit(&mut tree);
5352        let m = ended.begin_group();
5353        edit(&mut ended);
5354        ended.end_group(m).unwrap();
5355        let shape = |t: &SyntaxTree| {
5356            let e = t.edits.as_deref().unwrap();
5357            (e.runs.len(), e.arenas.len(), e.links.len(), t.emit())
5358        };
5359        let held = shape(&tree);
5360        assert!(held.1 > shape(&ended).1, "{held:?}");
5361        for copy in [tree.clone(), tree.fork()] {
5362            assert!(!copy.in_group());
5363            assert_eq!(shape(&copy), shape(&ended));
5364            assert_eq!(copy, SyntaxTree::parse(copy.emit()));
5365        }
5366        assert_eq!(shape(&tree), held);
5367        tree.rollback_group(mark).unwrap();
5368        assert_eq!(tree.emit(), src);
5369    }
5370
5371    /// The per-run diagnostic counts stay exact through cuts,
5372    /// insertions of fragments with diagnostics, removals, merges, and
5373    /// refused edits; the diagnostics read through them are the
5374    /// re-parse's.
5375    #[test]
5376    fn run_diagnostic_counts_follow_every_edit() {
5377        let settings = Settings::new().lenient_inline_colons(true);
5378        let src: String = (0..40)
5379            .map(|i| format!("k{i}: a: b\nv{i}: [x, y]\n"))
5380            .collect();
5381        let mut tree = SyntaxTree::parse_with(src.as_str(), &settings);
5382        assert!(tree.diagnostics().len() >= 40);
5383        // The warning of `w: e` is attached to the element after it, `r`:
5384        // inside the fragment.
5385        let donor = SyntaxTree::parse_with("a: 1\nq: w: e\nr: 1\n", &settings);
5386        let map = donor.root().first_child().unwrap().first_child().unwrap();
5387        let kids: Vec<_> = map.children().collect();
5388        let with_warning = donor
5389            .extract(kids[4].id(), kids.last().unwrap().id())
5390            .unwrap();
5391        assert_eq!(with_warning.text(), "\nq: w: e\nr: 1");
5392        let mut inserted = Vec::new();
5393        for round in 0..30usize {
5394            let seqs: Vec<NodeId> = tree
5395                .root()
5396                .descendants()
5397                .filter(|n| n.kind() == SyntaxKind::FlowSequence)
5398                .map(|n| n.id())
5399                .collect();
5400            let s = seqs[round * 7 % seqs.len()];
5401            let x = tree.get(s).unwrap().children().nth(1).unwrap();
5402            let tok = x.first_child().unwrap().id();
5403            let _ = tree.replace_token(tok, &format!("x{round}")).unwrap();
5404            assert_diag_sums(&tree);
5405            // An entry with its own warning, from another arena.
5406            inserted.push(tree.insert_after(s, with_warning.clone()).unwrap());
5407            assert_diag_sums(&tree);
5408            if round % 3 == 2 {
5409                let ins = inserted.remove(round % inserted.len());
5410                let _ = tree.remove_range(ins.first, ins.last).unwrap();
5411                assert_diag_sums(&tree);
5412            }
5413            // A refused edit changes no count.
5414            let colon = tree
5415                .root()
5416                .descendants()
5417                .find(|n| n.kind() == SyntaxKind::MappingValue)
5418                .unwrap()
5419                .id();
5420            assert_eq!(tree.remove(colon), Err(TreeEditError::NotWellFormed));
5421            assert_diag_sums(&tree);
5422            assert_eq!(tree, SyntaxTree::parse_with(tree.emit(), &settings));
5423        }
5424        assert_eq!(tree.emit().matches("q: w: e").count(), 20);
5425    }
5426}