Skip to main content

fatou_parser/parser/
reparse.rs

1//! Incremental reparse: turn a text edit plus the previous parse into a new
2//! tree without re-lexing and re-parsing the whole file.
3//!
4//! The cheapest strategy runs first, with a full
5//! [`parse`](crate::parser::parse) as the always-correct fallback. Two tiers are
6//! available:
7//! the token tier ([`reparse_token`]) relexes an edit confined to a single
8//! `Ident`, comment, or whitespace leaf in isolation and splices it into the
9//! previous green tree ([`try_splice_plain_token`]), or — for a `StringContent`
10//! leaf, whose lexing depends on the enclosing delimiter's mode — relexes the
11//! whole enclosing string literal in isolation and requires it to reproduce its
12//! own token run ([`try_splice_string_content`]); the top-level statement tier
13//! ([`reparse_toplevel`]) reparses the run of `ROOT` children touching the edit
14//! with the public [`parse`](crate::parser::parse) and splices the resulting
15//! children and diagnostics in place, provided the boundary guards prove the
16//! region decoupled from its neighbors.
17//!
18//! Two entry points sit above those tiers. [`reparse_edits`] takes the precise
19//! chain the language server staged from a `didChange` batch and replays it one
20//! edit at a time; [`reparse`] takes a single edit, which is what the host's
21//! `fatou::incremental` recovers with [`diff_edit`] from a pair of whole texts
22//! when no chain is available. The chain is tried first: a collapsed diff of
23//! scattered edits spans everything between them, and the region that produces
24//! is wide enough that [`region_is_too_wide`] declines it outright, where
25//! replaying the chain splices each edit on its own. The Tenet-4 oracle
26//! ([`assert_matches_full_parse`] plus `tests/incremental_reparse.rs`) checks
27//! every splice against a full parse.
28//!
29//! **Correctness invariant (Tenet 4):** a successful reparse must yield a
30//! green tree *and* diagnostics byte-identical to a full parse of the edited
31//! text. A reparse is an output-pure performance hint: the salsa layer only
32//! ever sees text changes, and a miss is a full parse, never an error.
33//!
34//! # Why the `STRING_CONTENT` splice is sound
35//!
36//! [`try_splice_string_content`] relexes the whole enclosing string literal
37//! rather than the edited leaf, and the argument that this preserves the tree
38//! is the subtlest one in the module, so it is recorded here in full.
39//!
40//! Nothing outside the lexer reads `StringContent` *text*: the parser only
41//! pushes the token, docstring eligibility tests the first token's kind, and the
42//! flag passes are kind-based — so preserving the node's token-kind sequence
43//! preserves both the tree and the diagnostics. (Nor does triple-quoted
44//! dedenting intrude: that lives in the test-only JuliaSyntax projector, which
45//! rebuilds the string at projection time.) Given that:
46//!
47//! * The bytes before the node are unchanged and the lexer is a deterministic
48//!   left-to-right machine, so its mode stack at the node start is identical.
49//!   That subsumes the backward join probe.
50//! * The relex proves the kinds are unchanged and that only the edited leaf's
51//!   end, and the ends after it, moved by the delta. The bytes after the leaf
52//!   *within* the node are therefore byte-identical — including the close
53//!   delimiter and any suffix — so the mode stack is back to its starting depth
54//!   at the node end and the rest of the file lexes identically, merely shifted.
55//!   That subsumes the forward join probe, which could not have expressed a
56//!   delimiter-plus-suffix tail with its one probe character anyway.
57//!
58//! The second bullet needs the literal to be *terminated*, which gets its own
59//! check rather than leaning on an `UnterminatedLiteral` diagnostic's anchor.
60//!
61//! The faithfulness relex (the unedited node text must reproduce the node's own
62//! tokens) is what makes that bullet an induction rather than an assumption: an
63//! isolated [`lex`] starts from an empty mode stack and no token history, while
64//! in context the node may sit under a `Str`/`Interp` frame and
65//! `prev_ends_value` consults the preceding token. Proving faithfulness for the
66//! old text, plus an identical kind sequence, carries it to the new text.
67
68use rowan::{GreenNode, GreenToken, TextRange, TextSize, TokenAtOffset};
69
70use crate::parser::ParseDiagnostic;
71use crate::parser::diagnostics::DIAGNOSTIC_STREAMS;
72use crate::parser::lexer::lex;
73use crate::parser::tree_builder::syntax_kind_for;
74use crate::syntax::{SyntaxKind, SyntaxNode, SyntaxToken};
75
76/// The edit currency, defined in the sibling `edit` module and re-exported
77/// here so `parser::Edit` stays the path the parser layer uses.
78pub use super::edit::{Edit, apply_edits, diff_edit, try_apply_edits};
79
80/// Structural fingerprint of a tree: one line per descendant element with
81/// `kind@range` plus the token text (empty for nodes). Two trees with equal
82/// fingerprints are byte-identical. Oracle/debug support: the Tenet-4 assert
83/// in [`reparse`] and the `tests/incremental_reparse.rs` harness share this
84/// definition so they can never diverge.
85pub fn fingerprint(node: &SyntaxNode) -> String {
86    use std::fmt::Write;
87
88    let mut out = String::new();
89    for el in node.descendants_with_tokens() {
90        let text = el
91            .as_token()
92            .map(|t| t.text().to_string())
93            .unwrap_or_default();
94        let _ = writeln!(out, "{:?}@{:?} {:?}", el.kind(), el.text_range(), text);
95    }
96    out
97}
98
99/// Which strategy produced a [`Reparsed`]. Surfaced for tests and benchmarks.
100/// Ordered cheapest-first, so a chain of reparses can report the most
101/// expensive tier it had to reach with [`Ord::max`].
102#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
103pub enum ReparseTier {
104    /// A single leaf token was relexed in isolation and spliced in place.
105    Token,
106    /// A run of top-level statements was reparsed and spliced under `ROOT`.
107    TopLevel,
108}
109
110/// The result of a successful incremental reparse: the new whole-file green
111/// tree and its parse diagnostics (absolute offsets in the new text).
112#[derive(Debug, Clone)]
113pub struct Reparsed {
114    pub green: GreenNode,
115    pub diagnostics: Vec<ParseDiagnostic>,
116    pub tier: ReparseTier,
117}
118
119/// Attempt an incremental reparse of the previous parse (`prev_green`, parsed
120/// from `prev_text` with `prev_diags`) under `edit`, which transforms
121/// `prev_text` into `new_text`. Returns `None` when no incremental strategy
122/// applies — the caller must then do a full parse.
123///
124/// In debug builds every successful reparse is checked against a full parse
125/// of `new_text` (Tenet 4): tree fingerprint and diagnostics vector must be
126/// identical.
127///
128/// `edit` is not trusted, for the same reason [`reparse_edits`]'s chain is
129/// not: one that does not fit `prev_text` — a stale range, a buffer that moved
130/// underneath it — is rejected here rather than applied at offsets that would
131/// panic on a slice.
132pub fn reparse(
133    prev_text: &str,
134    prev_green: &GreenNode,
135    prev_diags: &[ParseDiagnostic],
136    edit: &Edit,
137    new_text: &str,
138) -> Option<Reparsed> {
139    if !fits(prev_text, edit) {
140        return None;
141    }
142    let result = reparse_impl(prev_text, prev_green, prev_diags, edit, new_text)?;
143    assert_matches_full_parse(&result, new_text);
144    Some(result)
145}
146
147/// Attempt an incremental reparse across a *chain* of edits, each expressed
148/// against the text its predecessors produced — the shape an LSP `didChange`
149/// batch arrives in (see `fatou::text::apply_content_changes` host-side).
150///
151/// This is for the case [`diff_edit`] cannot express: when the edits are
152/// scattered, collapsing them into one spanning edit covers everything between
153/// the first and the last change and blows both tiers' guards, while replaying
154/// them one at a time keeps each splice small. Try this *before* the collapsed
155/// edit: a wide span is the one shape the collapsed edit can never answer, so
156/// offering it first is the difference between a hit and a
157/// `region_is_too_wide` bail (`benches/reparse.rs`).
158///
159/// Fewer than two edits returns `None` immediately: a single edit's span
160/// always contains [`diff_edit`]'s for the same transform, so there is nothing
161/// to gain over the caller's next step.
162///
163/// `edits` is not trusted: a slice that is not the exact transform from
164/// `prev_text` to `new_text` (a stale chain, a buffer that moved underneath
165/// it) is rejected rather than applied at meaningless offsets. Each step is
166/// proven to `fits` the text its predecessors produced *before* that text is
167/// sliced, and the composed result is proven to be `new_text` before anything
168/// is returned — so a stale chain costs at most the splices it got through,
169/// bounded by the caller's chain budget (`incremental::MAX_CHAIN_EDITS`).
170///
171/// Validating step by step rather than pre-folding the whole chain with
172/// [`try_apply_edits`] keeps the replay to one application: the fold would have
173/// to redo every `replace_range` the loop below already does, which costs the
174/// same order as the splice it is guarding (`benches/reparse.rs`,
175/// `precise_chain`).
176pub fn reparse_edits(
177    prev_text: &str,
178    prev_green: &GreenNode,
179    prev_diags: &[ParseDiagnostic],
180    edits: &[Edit],
181    new_text: &str,
182) -> Option<Reparsed> {
183    if edits.len() < 2 {
184        return None;
185    }
186
187    let mut text = prev_text.to_string();
188    let mut green = prev_green.clone();
189    let mut diagnostics = prev_diags.to_vec();
190    let mut tier = ReparseTier::Token;
191
192    for edit in edits {
193        if !fits(&text, edit) {
194            return None;
195        }
196        let next = edit.apply(&text);
197        let step = reparse_impl(&text, &green, &diagnostics, edit, &next)?;
198        tier = tier.max(step.tier);
199        text = next;
200        green = step.green;
201        diagnostics = step.diagnostics;
202    }
203
204    // The chain applied cleanly, but that alone does not make it the transform
205    // the caller is asking about: a stale chain can fit and still land
206    // somewhere else entirely. This check is what the Tenet-4 assert below
207    // relies on to be comparing the same two texts.
208    if text != new_text {
209        return None;
210    }
211
212    let result = Reparsed {
213        green,
214        diagnostics,
215        tier,
216    };
217    assert_matches_full_parse(&result, new_text);
218    Some(result)
219}
220
221/// Tenet 4: a successful reparse yields a green tree *and* diagnostics
222/// byte-identical to a full parse of the edited text.
223///
224/// Debug builds only — this runs a whole `parse` plus two whole-tree
225/// [`fingerprint`] builds, so it is far too expensive to leave on. A chain
226/// asserts once on its composed result rather than once per step, which would
227/// otherwise make a debug-build language server unusable on a large file.
228#[cfg(debug_assertions)]
229fn assert_matches_full_parse(result: &Reparsed, new_text: &str) {
230    let full = crate::parser::parse(new_text);
231    debug_assert_eq!(
232        fingerprint(&SyntaxNode::new_root(result.green.clone())),
233        fingerprint(&full.cst),
234        "Tenet 4: reparse ({:?}) tree differs from full parse",
235        result.tier,
236    );
237    debug_assert_eq!(
238        result.diagnostics, full.diagnostics,
239        "Tenet 4: reparse ({:?}) diagnostics differ from full parse",
240        result.tier,
241    );
242}
243
244#[cfg(not(debug_assertions))]
245fn assert_matches_full_parse(_result: &Reparsed, _new_text: &str) {}
246
247/// Whether `edit`'s range is a well-formed byte range of `text`. Both tiers
248/// slice `prev_text` at the edit's offsets, so an edit that does not fit is a
249/// panic rather than a miss.
250fn fits(text: &str, edit: &Edit) -> bool {
251    edit.range.start <= edit.range.end
252        && edit.range.end <= text.len()
253        && text.is_char_boundary(edit.range.start)
254        && text.is_char_boundary(edit.range.end)
255}
256
257/// Tier dispatch: cheapest first.
258fn reparse_impl(
259    prev_text: &str,
260    prev_green: &GreenNode,
261    prev_diags: &[ParseDiagnostic],
262    edit: &Edit,
263    new_text: &str,
264) -> Option<Reparsed> {
265    reparse_token(prev_text, prev_green, prev_diags, edit)
266        .or_else(|| reparse_toplevel(prev_text, prev_green, prev_diags, edit, new_text))
267}
268
269/// Leaf kinds proved by the isolated single-token relex plus the two join
270/// probes ([`try_splice_plain_token`]). Their text never spans a newline and
271/// their lexing is local enough for those probes to prove a splice sound.
272/// Deliberately absent: `NEWLINE` (statement structure), `CHAR` and the
273/// numeric kinds (quote-context and juxtaposition traps outweigh the win), and
274/// the string prefix/suffix kinds (glued to their delimiters).
275/// `STRING_CONTENT` is handled too, but by a different proof — its lexing
276/// depends on the enclosing delimiter's mode, so it takes the whole-literal
277/// relex in [`try_splice_string_content`] instead.
278const TOKEN_REPARSE_KINDS: &[SyntaxKind] = &[
279    SyntaxKind::IDENT,
280    SyntaxKind::COMMENT,
281    SyntaxKind::BLOCK_COMMENT,
282    SyntaxKind::WHITESPACE,
283];
284
285/// Literal node kinds a `STRING_CONTENT` leaf may sit directly under. Error
286/// recovery can leave one under an `ERROR` node instead, which
287/// [`try_splice_string_content`] rejects: the proof needs the delimiters.
288const STRING_LITERAL_KINDS: &[SyntaxKind] = &[
289    SyntaxKind::STRING_LITERAL,
290    SyntaxKind::CMD_LITERAL,
291    // `var"…"`, a non-standard *identifier*. Nothing keys on its content text
292    // either, so a content edit is as safe here as in a plain string.
293    SyntaxKind::NONSTANDARD_IDENTIFIER,
294];
295
296/// Identifier texts the parser treats structurally even though they lex as
297/// plain `Ident`, so a same-kind relex proves nothing about the tree shape.
298/// True keywords (`where`, `mutable`, …) need no entry: they lex as their own
299/// kinds, and the same-kind guard rejects them.
300///
301/// This list is the one guard here with no compile-time link to what it
302/// describes, and the Tenet-4 oracle only catches an omission if a seeded edit
303/// happens to spell the missing word — so
304/// [`every_contextual_ident_is_listed`](tests::every_contextual_ident_is_listed)
305/// scans the grammar for `Ident`-text comparisons and fails if one names a word
306/// that is not here.
307const CONTEXTUAL_IDENTS: &[&str] = &[
308    "as",        // import alias (structural.rs)
309    "abstract",  // `abstract type` (expr.rs)
310    "primitive", // `primitive type` (expr.rs)
311    "type",      // the `type` in `abstract`/`primitive` type decls (expr.rs)
312    "typegroup", // `typegroup` declaration (expr.rs)
313    "public",    // top-level `public` statement (expr.rs)
314    "var",       // `var"..."` quoting prefix (expr.rs)
315    "in",        // iteration spec / infix operator (expr.rs)
316    "∈",         // Unicode `in` (expr.rs)
317    "isa",       // infix operator (expr.rs)
318    "doc",       // `doc"..."` / `@doc` marker (expr.rs)
319    "outer",     // `for outer i in xs` iteration spec (expr.rs)
320];
321
322/// The token tier: when the edit is confined to a single eligible leaf, relex
323/// that leaf in isolation and splice it via [`SyntaxToken::replace_with`].
324///
325/// A pure insertion at a token boundary is ambiguous (it could extend either
326/// neighbor), so both candidates are tried, left first; whichever passes the
327/// guards yields the same new file text, and the guards plus the Tenet-4
328/// oracle arbitrate tree equality. Any guard failure returns `None`, which
329/// the caller answers with a full parse, so every bail here is safe.
330fn reparse_token(
331    prev_text: &str,
332    prev_green: &GreenNode,
333    prev_diags: &[ParseDiagnostic],
334    edit: &Edit,
335) -> Option<Reparsed> {
336    let root = SyntaxNode::new_root(prev_green.clone());
337    let (s, e) = (edit.range.start, edit.range.end);
338    let mut candidates: Vec<SyntaxToken> = Vec::with_capacity(2);
339    if s == e {
340        match root.token_at_offset(TextSize::new(s as u32)) {
341            TokenAtOffset::None => return None,
342            TokenAtOffset::Single(t) => candidates.push(t),
343            TokenAtOffset::Between(l, r) => candidates.extend([l, r]),
344        }
345    } else {
346        // A range spanning a token boundary covers a node, not a token, and
347        // bails here.
348        let range = TextRange::new(TextSize::new(s as u32), TextSize::new(e as u32));
349        candidates.push(root.covering_element(range).into_token()?);
350    }
351
352    candidates
353        .into_iter()
354        .find_map(|token| try_splice_token(prev_text, prev_diags, edit, &token))
355}
356
357/// Dispatch one candidate leaf to the proof its kind takes.
358fn try_splice_token(
359    prev_text: &str,
360    prev_diags: &[ParseDiagnostic],
361    edit: &Edit,
362    token: &SyntaxToken,
363) -> Option<Reparsed> {
364    match token.kind() {
365        SyntaxKind::STRING_CONTENT => try_splice_string_content(prev_text, prev_diags, edit, token),
366        kind if TOKEN_REPARSE_KINDS.contains(&kind) => {
367            try_splice_plain_token(prev_text, prev_diags, edit, token)
368        }
369        _ => None,
370    }
371}
372
373/// Run the stage-2 guards against one candidate leaf and splice on success.
374fn try_splice_plain_token(
375    prev_text: &str,
376    prev_diags: &[ParseDiagnostic],
377    edit: &Edit,
378    token: &SyntaxToken,
379) -> Option<Reparsed> {
380    // Newline ban: these kinds either cannot contain a newline or (block
381    // comments) rarely see one edited, and a newline moves statement
382    // boundaries, so bail early. The single-token relex guard below would
383    // catch most of these anyway; this is the cheap early-out. It does not
384    // apply to `STRING_CONTENT`, whose run legitimately spans newlines and
385    // whose proof does not depend on line structure.
386    if edit.insert.contains(['\n', '\r']) || prev_text[edit.range.clone()].contains(['\n', '\r']) {
387        return None;
388    }
389
390    let tr = token.text_range();
391    let (t0, t1) = (usize::from(tr.start()), usize::from(tr.end()));
392
393    // The leaf's new text, with the edit applied at its relative offset. A
394    // whole-leaf deletion leaves it empty, which the relex guard rejects.
395    let mut new_leaf = token.text().to_string();
396    new_leaf.replace_range((edit.range.start - t0)..(edit.range.end - t0), &edit.insert);
397
398    // Isolated relex: still exactly one token, same kind, spanning all of it.
399    // This alone rejects kind flips (ident ⇒ keyword, whitespace ⇒ newline)
400    // and splits (`=#` typed into a block comment).
401    let relexed = lex(&new_leaf);
402    let [only] = relexed.as_slice() else {
403        return None;
404    };
405    if only.start != 0 || only.end != new_leaf.len() || syntax_kind_for(only.kind) != token.kind() {
406        return None;
407    }
408
409    // Contextual identifiers parse structurally, so text changes into or out
410    // of one can reshape the tree under an unchanged token kind.
411    if token.kind() == SyntaxKind::IDENT
412        && (CONTEXTUAL_IDENTS.contains(&token.text())
413            || CONTEXTUAL_IDENTS.contains(&new_leaf.as_str()))
414    {
415        return None;
416    }
417
418    // Forward join: the next source character must not extend the token
419    // (`r` + `"…"` fusing into a prefixed string, an unterminated block
420    // comment swallowing its neighbor). At EOF probe with `\n`, which no
421    // eligible kind can absorb, so a leaf left unterminated at EOF (`#=` typed
422    // into the last block comment) still fails here.
423    let next_char = prev_text[t1..].chars().next().unwrap_or('\n');
424    let mut probe = new_leaf.clone();
425    probe.push(next_char);
426    let first = lex(&probe).into_iter().next()?;
427    if first.end != new_leaf.len() || syntax_kind_for(first.kind) != token.kind() {
428        return None;
429    }
430
431    // Backward join: the previous leaf plus the new text must relex to the
432    // same two tokens. Catches juxtaposition fusing (`2` + `e10` ⇒ one
433    // `Float`), and conservatively bails whenever the previous leaf's
434    // isolated lex diverges from its in-context one (e.g. a closing string
435    // delimiter reopening as a string).
436    if let Some(prev) = token.prev_token() {
437        let mut probe = prev.text().to_string();
438        let boundary = probe.len();
439        probe.push_str(&new_leaf);
440        let relexed = lex(&probe);
441        let [a, b] = relexed.as_slice() else {
442            return None;
443        };
444        if a.end != boundary
445            || syntax_kind_for(a.kind) != prev.kind()
446            || b.end != probe.len()
447            || syntax_kind_for(b.kind) != token.kind()
448        {
449            return None;
450        }
451    }
452
453    // Keep diagnostic remapping trivial: bail when any diagnostic touches the
454    // leaf, boundaries included. A clean same-kind relex introduces none of
455    // its own, so the rest keep their meaning and only need shifting.
456    if prev_diags.iter().any(|d| d.start <= t1 && d.end >= t0) {
457        return None;
458    }
459    let delta = edit.delta();
460    let shift = |pos: usize| (pos as isize + delta) as usize;
461    let diagnostics = prev_diags
462        .iter()
463        .map(|d| {
464            let mut d = d.clone();
465            if d.start >= t1 {
466                d.start = shift(d.start);
467                d.end = shift(d.end);
468            }
469            d
470        })
471        .collect();
472
473    let green = token.replace_with(GreenToken::new(token.kind().into(), &new_leaf));
474    Some(Reparsed {
475        green,
476        diagnostics,
477        tier: ReparseTier::Token,
478    })
479}
480
481/// `text` — the slice of the previous buffer starting at absolute offset
482/// `base` — with `edit` applied at its relative offset.
483fn edited_slice(text: &str, base: usize, edit: &Edit) -> String {
484    let mut out = text.to_string();
485    out.replace_range(
486        (edit.range.start - base)..(edit.range.end - base),
487        &edit.insert,
488    );
489    out
490}
491
492/// Every token under `node` as `(kind, end)`, with `end` relative to the node
493/// start. Tokens tile the node's text contiguously from `0` and the tree
494/// synthesizes none of its own (`tree_builder`), so this *is* the lexer's
495/// token run for that span and the ends alone pin every range.
496fn literal_token_ends(node: &SyntaxNode) -> Vec<(SyntaxKind, usize)> {
497    let base = usize::from(node.text_range().start());
498    node.descendants_with_tokens()
499        .filter_map(|el| el.into_token())
500        .map(|t| (t.kind(), usize::from(t.text_range().end()) - base))
501        .collect()
502}
503
504/// Whether an isolated [`lex`] of `text` reproduces `expected`: the same kinds
505/// in the same order, with the same ends, covering all of `text`. `grown`
506/// names the index whose end — and every end after it — is expected to have
507/// moved by that delta.
508fn relex_matches(
509    text: &str,
510    expected: &[(SyntaxKind, usize)],
511    grown: Option<(usize, isize)>,
512) -> bool {
513    let tokens = lex(text);
514    if tokens.len() != expected.len() {
515        return false;
516    }
517    for (i, (got, &(kind, end))) in tokens.iter().zip(expected).enumerate() {
518        let shift = match grown {
519            Some((from, delta)) if i >= from => delta,
520            _ => 0,
521        };
522        // A shift that runs an end past zero cannot describe any token, so it
523        // simply fails to match rather than wrapping into a huge `usize`.
524        let Ok(want) = usize::try_from(end as isize + shift) else {
525            return false;
526        };
527        if syntax_kind_for(got.kind) != kind || got.end != want {
528            return false;
529        }
530    }
531    tokens.last().is_some_and(|t| t.end == text.len())
532}
533
534/// The token tier's `STRING_CONTENT` path: relex the *whole enclosing string
535/// literal* in isolation and require it to reproduce its own token run with
536/// only the edited content leaf resized.
537///
538/// A content leaf cannot take [`try_splice_plain_token`]'s proof, because both
539/// of its probes assume a leaf that lexes the same standing alone: `abc` in
540/// isolation is an `Ident`, never `StringContent`, and a leaf following an
541/// interpolation (`"a$x b"`) has an `Ident` before it, which blows the
542/// two-token backward probe. Taking the delimiters along instead puts the
543/// isolated lexer into the right mode for free, so triple/raw/prefixed need no
544/// hand-written character table.
545///
546/// The soundness argument — why relexing the literal preserves the tree and the
547/// diagnostics — is in the module docs under *Why the `STRING_CONTENT` splice is
548/// sound*.
549///
550/// Newlines are allowed here, unlike in [`try_splice_plain_token`]: a content
551/// run spans them freely (a triple-quoted body, and a single-quoted one too —
552/// no newline stops the run, which is why an unterminated literal reaches EOF),
553/// and a newline *inside* one emits no `NEWLINE` token, so no statement
554/// boundary moves. Diagnostics are byte offsets and do not care about lines.
555/// That is what puts Enter in a docstring on this tier.
556fn try_splice_string_content(
557    prev_text: &str,
558    prev_diags: &[ParseDiagnostic],
559    edit: &Edit,
560    token: &SyntaxToken,
561) -> Option<Reparsed> {
562    let node = token.parent()?;
563    if !STRING_LITERAL_KINDS.contains(&node.kind()) {
564        return None;
565    }
566    let nr = node.text_range();
567    let (n0, n1) = (usize::from(nr.start()), usize::from(nr.end()));
568
569    // Bail when any diagnostic touches the literal, boundaries included. The
570    // relex proves the token sequence unchanged, so the four string-related
571    // kinds would in fact survive a shift — but "no diagnostic may touch the
572    // literal we splice" is an invariant that keeps holding as diagnostics are
573    // added, and what it gives up (`x = "abc`, `"a"b`, `var"x"y`) is the error
574    // path, not the keystroke path.
575    //
576    // This runs *first*, before either relex: an unterminated literal runs to
577    // EOF, so its node is the rest of the file, and every keystroke inside one
578    // would otherwise pay two whole-file lexes to learn what a diagnostic
579    // already says (`benches/reparse.rs`, `rejected_attempt`).
580    if prev_diags.iter().any(|d| d.start <= n1 && d.end >= n0) {
581        return None;
582    }
583
584    let expected = literal_token_ends(&node);
585    let tr = token.text_range();
586    let (t0, t1) = (usize::from(tr.start()), usize::from(tr.end()));
587    // Ends are unique (tokens tile with positive width), so this identifies the
588    // leaf by index — which the edited relex then pins as the one that resized.
589    let leaf = expected
590        .iter()
591        .position(|&(kind, end)| kind == SyntaxKind::STRING_CONTENT && end == t1 - n0)?;
592
593    // Terminated: a matching close delimiter must follow the leaf. A prefixed
594    // literal's suffix is lexed as part of the same node, so nothing but the
595    // close can end the run.
596    let close = if node.kind() == SyntaxKind::CMD_LITERAL {
597        SyntaxKind::CMD_DELIM_CLOSE
598    } else {
599        SyntaxKind::STRING_DELIM_CLOSE
600    };
601    if !expected[leaf + 1..].iter().any(|&(kind, _)| kind == close) {
602        return None;
603    }
604
605    let old_node_text = &prev_text[n0..n1];
606    if !relex_matches(old_node_text, &expected, None) {
607        return None;
608    }
609    let delta = edit.delta();
610    let edited = edited_slice(old_node_text, n0, edit);
611    if !relex_matches(&edited, &expected, Some((leaf, delta))) {
612        return None;
613    }
614
615    let new_leaf = &edited[(t0 - n0)..((t1 - n0) as isize + delta) as usize];
616
617    // Every surviving diagnostic lies wholly outside the literal, so the ones
618    // past it shift and the rest keep their positions.
619    let shift = |pos: usize| (pos as isize + delta) as usize;
620    let diagnostics = prev_diags
621        .iter()
622        .map(|d| {
623            let mut d = d.clone();
624            if d.start >= n1 {
625                d.start = shift(d.start);
626                d.end = shift(d.end);
627            }
628            d
629        })
630        .collect();
631
632    let green = token.replace_with(GreenToken::new(SyntaxKind::STRING_CONTENT.into(), new_leaf));
633    Some(Reparsed {
634        green,
635        diagnostics,
636        tier: ReparseTier::Token,
637    })
638}
639
640/// Whether a token kind is trivia. Mirrors `TokKind::is_trivia` on the CST
641/// side.
642fn is_trivia_kind(kind: SyntaxKind) -> bool {
643    matches!(
644        kind,
645        SyntaxKind::WHITESPACE
646            | SyntaxKind::NEWLINE
647            | SyntaxKind::COMMENT
648            | SyntaxKind::BLOCK_COMMENT
649    )
650}
651
652/// Whether a `ROOT` child carries statement-level content: a positive-width
653/// node, or a loose non-trivia token (the unparseable-token recovery emits
654/// bare tokens at the root, without an `ERROR` wrapper). Zero-width nodes and
655/// trivia are gap material.
656fn is_significant_child(el: &crate::syntax::SyntaxElement) -> bool {
657    match el {
658        rowan::NodeOrToken::Node(n) => !n.text_range().is_empty(),
659        rowan::NodeOrToken::Token(t) => !is_trivia_kind(t.kind()),
660    }
661}
662
663/// Below this the tier always tries, whatever fraction of the file the region
664/// is: on a small file every parse in play is small, and the fraction test
665/// alone would refuse the common case of a file with one or two statements.
666const REGION_ALWAYS_TRY_BYTES: usize = 4 * 1024;
667
668/// A region wider than `1 / REGION_MAX_FILE_DIVISOR` of the file is wide enough
669/// that answering it costs more than the full parse it is trying to avoid. A
670/// divisor rather than a fraction, so `4` here means a quarter.
671const REGION_MAX_FILE_DIVISOR: usize = 4;
672
673/// Whether a region is too wide to be worth attempting, per the two consts
674/// above. The tier answers a region with a fragment parse of it *plus* up to
675/// three neighbor-sized boundary parses, so a miss costs more than the full
676/// parse it was avoiding; bailing on the region's byte span — cheap evidence,
677/// known before any parse — caps the loss (`benches/reparse.rs`,
678/// `scattered_via_diff_edit`).
679///
680/// A performance guard only: like every other bail here it returns the caller to
681/// a full parse, so it cannot affect what a reparse yields.
682fn region_is_too_wide(region_len: usize, text_len: usize) -> bool {
683    region_len > REGION_ALWAYS_TRY_BYTES && region_len > text_len / REGION_MAX_FILE_DIVISOR
684}
685
686/// The reparse region at the top-level tier: a contiguous run of `ROOT`
687/// children (statement nodes and loose trivia tokens both), identified by
688/// child index and old-text byte range. The boundary child kinds
689/// disambiguate zero-width diagnostics anchored exactly on a boundary.
690struct Region {
691    first: usize,
692    last: usize,
693    start: usize,
694    end: usize,
695    first_is_node: bool,
696    last_is_node: bool,
697}
698
699/// Select the contiguous run of `ROOT` children whose closed range touches
700/// the edit. Closed-interval touch makes boundary insertions extend into the
701/// neighbor they abut (blank-line typing selects the surrounding newline
702/// tokens; deleting a newline pulls in both neighbor statements). A
703/// zero-width child abutting the region start is absorbed: stray-closer
704/// recovery pairs a zero-width `ERROR` with its byte-bearing run at the same
705/// offset, and the fragment reparse regenerates both, so leaving it outside
706/// would duplicate it. `None` when the run covers every child (the fragment
707/// reparse would be the full parse) or `ROOT` is empty.
708fn select_region(root: &SyntaxNode, edit: &Edit) -> Option<Region> {
709    let (s, e) = (edit.range.start, edit.range.end);
710    let children: Vec<_> = root.children_with_tokens().collect();
711    let touches = |el: &crate::syntax::SyntaxElement| {
712        let r = el.text_range();
713        usize::from(r.start()) <= e && usize::from(r.end()) >= s
714    };
715    let mut first = children.iter().position(touches)?;
716    let last = children.len() - 1 - children.iter().rev().position(touches)?;
717
718    let start = usize::from(children[first].text_range().start());
719    while first > 0
720        && children[first - 1].text_range() == TextRange::empty(TextSize::new(start as u32))
721    {
722        first -= 1;
723    }
724
725    if first == 0 && last == children.len() - 1 {
726        return None;
727    }
728    Some(Region {
729        first,
730        last,
731        start,
732        end: usize::from(children[last].text_range().end()),
733        first_is_node: children[first].as_node().is_some(),
734        last_is_node: children[last].as_node().is_some(),
735    })
736}
737
738/// The nearest positive-width `ROOT` child nodes outside the region. Trivia
739/// tokens are gap material, and a zero-width `ERROR` node contributes no text
740/// (taking one as the forward neighbor would make the boundary guard
741/// vacuous), so both are skipped.
742fn sibling_nodes(root: &SyntaxNode, region: &Region) -> (Option<SyntaxNode>, Option<SyntaxNode>) {
743    let positive_node =
744        |el: crate::syntax::SyntaxElement| el.into_node().filter(|n| !n.text_range().is_empty());
745    let prev = root
746        .children_with_tokens()
747        .take(region.first)
748        .filter_map(positive_node)
749        .last();
750    let next = root
751        .children_with_tokens()
752        .skip(region.last + 1)
753        .find_map(positive_node);
754    (prev, next)
755}
756
757/// Whether no `ROOT` child (node or loose token) of `cst` straddles `seam`.
758/// Children tile the text, so no-straddle is equivalent to a boundary
759/// existing exactly at the seam: the two sides parse independently. A
760/// straddling node is a cross-boundary statement (trailing-operator
761/// continuation, a docstring fold, an unterminated block absorbing its
762/// neighbor); a straddling token is a lexical fusion (`#=` swallowing
763/// trailing trivia, an unterminated string).
764fn no_straddle(cst: &SyntaxNode, seam: usize) -> bool {
765    let seam = TextSize::new(seam as u32);
766    cst.children_with_tokens().all(|el| {
767        let r = el.text_range();
768        !(r.start() < seam && seam < r.end())
769    })
770}
771
772/// Splice the fragment's diagnostics into the previous ones, stream by
773/// stream ([`DiagnosticKind::stream`](crate::parser::diagnostics::DiagnosticKind::stream)):
774/// keep those before the region, drop those the fragment reparse
775/// regenerates, and shift those after by the edit delta. Emission order
776/// within a stream is positional across statements (the drive loop is
777/// per-line sequential, the flag passes walk in document order), so
778/// `before ++ fragment ++ after` per stream, concatenated in stream order,
779/// reproduces a full parse's vector.
780///
781/// A zero-width diagnostic exactly on a region boundary is ambiguous by
782/// position alone and is disambiguated by the boundary child's kind: a
783/// statement node owns a start-anchored marker at `start` (`const x` at the
784/// region's front) and an end-anchored one at `end`, while a trivia boundary
785/// child owns nothing, so the marker belongs to the statement just outside.
786/// This is sound only because the decoupling guards already rejected
787/// zero-gap node adjacency at the boundaries. A diagnostic genuinely
788/// straddling a boundary aborts the splice (`None`); regions are whole
789/// children and diagnostics never outgrow their statement, so this arm
790/// should be unreachable and is purely defensive.
791///
792/// A stream index outside [`DIAGNOSTIC_STREAMS`] aborts the splice too, rather
793/// than indexing out of bounds. [`DiagnosticKind::stream`] is an exhaustive
794/// match today, so this cannot fire — but a bail returns the caller to a full
795/// parse, whereas a panic here takes down an analysis query, and this module
796/// buys its whole safety argument from every failure being a bail.
797fn splice_diagnostics(
798    prev_diags: &[ParseDiagnostic],
799    frag_diags: &[ParseDiagnostic],
800    region: &Region,
801    delta: isize,
802) -> Option<Vec<ParseDiagnostic>> {
803    enum Class {
804        Before,
805        Drop,
806        After,
807    }
808    let classify = |d: &ParseDiagnostic| -> Option<Class> {
809        let (rs, re) = (region.start, region.end);
810        if d.start == d.end && d.start == rs {
811            return Some(if region.first_is_node {
812                Class::Drop
813            } else {
814                Class::Before
815            });
816        }
817        if d.start == d.end && d.start == re {
818            return Some(if region.last_is_node {
819                Class::Drop
820            } else {
821                Class::After
822            });
823        }
824        if d.end <= rs {
825            return Some(Class::Before);
826        }
827        if d.start >= re {
828            return Some(Class::After);
829        }
830        if d.start >= rs && d.end <= re {
831            return Some(Class::Drop);
832        }
833        None
834    };
835
836    let mut before: [Vec<ParseDiagnostic>; DIAGNOSTIC_STREAMS] = Default::default();
837    let mut after: [Vec<ParseDiagnostic>; DIAGNOSTIC_STREAMS] = Default::default();
838    for d in prev_diags {
839        let class = classify(d)?;
840        let stream = d.kind.stream();
841        if stream >= DIAGNOSTIC_STREAMS {
842            debug_assert!(false, "diagnostic stream {stream} is out of range");
843            return None;
844        }
845        match class {
846            Class::Before => before[stream].push(d.clone()),
847            Class::Drop => {}
848            Class::After => {
849                let mut d = d.clone();
850                d.start = (d.start as isize + delta) as usize;
851                d.end = (d.end as isize + delta) as usize;
852                after[stream].push(d);
853            }
854        }
855    }
856
857    let mut out = Vec::with_capacity(prev_diags.len() + frag_diags.len());
858    for stream in 0..DIAGNOSTIC_STREAMS {
859        out.append(&mut before[stream]);
860        out.extend(
861            frag_diags
862                .iter()
863                .filter(|d| d.kind.stream() == stream)
864                .map(|d| {
865                    let mut d = d.clone();
866                    d.start += region.start;
867                    d.end += region.start;
868                    d
869                }),
870        );
871        out.append(&mut after[stream]);
872    }
873    Some(out)
874}
875
876/// The top-level statement tier: reparse the run of `ROOT` children touching
877/// the edit with the public [`parse`](crate::parser::parse) (which reruns
878/// `fold_docstrings` and the flag passes on the fragment) and splice the
879/// resulting children and diagnostics in place.
880///
881/// The guards, in order: decoupling scans require a newline between each
882/// untouched sibling statement and the fragment's non-trivia content, because
883/// the drive loop's per-line junk recovery couples same-line siblings; the
884/// boundary parses then prove the seam survives — the neighbor plus the
885/// actual gap bytes plus the fragment must parse with a boundary exactly at
886/// the old one, which rejects trailing-operator continuation, docstring
887/// folds, forward absorption by an unterminated block, and lexical fusion.
888/// Diagnostics splice last (see [`splice_diagnostics`]).
889fn reparse_toplevel(
890    prev_text: &str,
891    prev_green: &GreenNode,
892    prev_diags: &[ParseDiagnostic],
893    edit: &Edit,
894    new_text: &str,
895) -> Option<Reparsed> {
896    let root = SyntaxNode::new_root(prev_green.clone());
897    let region = select_region(&root, edit)?;
898    if region_is_too_wide(region.end - region.start, prev_text.len()) {
899        return None;
900    }
901    let delta = edit.delta();
902    let frag_end = (region.end as isize + delta) as usize;
903    let fragment = &new_text[region.start..frag_end];
904
905    let frag = crate::parser::parse(fragment);
906    let (prev_node, next_node) = sibling_nodes(&root, &region);
907
908    let positive_nodes = |node: &SyntaxNode| {
909        node.children_with_tokens()
910            .filter_map(|el| el.into_node())
911            .filter(|n| !n.text_range().is_empty())
912    };
913
914    // Backward decoupling: a newline must separate the last significant
915    // content before the region (a statement node or a loose junk token, not
916    // just `prev_node`) from the fragment's first significant content (or
917    // all of a trivia-only fragment). The drive loop's per-line junk
918    // recovery couples same-line siblings, and the newline often lives in
919    // the unchanged gap outside the region, so scan `new_text`.
920    let prev_significant_end = root
921        .children_with_tokens()
922        .take(region.first)
923        .filter(is_significant_child)
924        .last()
925        .map(|el| usize::from(el.text_range().end()));
926    if let Some(from) = prev_significant_end {
927        let anchor = frag
928            .cst
929            .children_with_tokens()
930            .find(is_significant_child)
931            .map(|el| usize::from(el.text_range().start()))
932            .unwrap_or(fragment.len());
933        if !new_text[from..region.start + anchor].contains('\n') {
934            return None;
935        }
936    }
937
938    // Forward decoupling, in both texts: the next statement is kept, not
939    // reparsed, so its line must have been decoupled from the old region
940    // content too (deleting `x` from `x y` puts the kept junk `y` at line
941    // start, where a full parse reads it as a plain statement). The new-text
942    // scan anchors at the fragment's last statement *node* end, not its last
943    // token: an unterminated bracket consumes the separating newline into
944    // the statement, and a consumed newline decouples nothing.
945    if let Some(next) = &next_node {
946        let anchor = frag
947            .cst
948            .children_with_tokens()
949            .filter(is_significant_child)
950            .last()
951            .map(|el| usize::from(el.text_range().end()))
952            .unwrap_or(0);
953        let to = (usize::from(next.text_range().start()) as isize + delta) as usize;
954        if !new_text[region.start + anchor..to].contains('\n') {
955            return None;
956        }
957
958        let old_anchor = root
959            .children_with_tokens()
960            .skip(region.first)
961            .take(region.last + 1 - region.first)
962            .filter(is_significant_child)
963            .last()
964            .map(|el| usize::from(el.text_range().end()))
965            .or(prev_significant_end)
966            .unwrap_or(0);
967        if !prev_text[old_anchor..usize::from(next.text_range().start())].contains('\n') {
968            return None;
969        }
970    }
971
972    // Cross-region coupling: when the fragment carries no significant content,
973    // the two neighbors sit next to each other across it and can couple in a
974    // way neither boundary parse can see, because each concatenation contains
975    // only one of them. Deleting the `]` from `"doc" ]\nf() = 1` is the shape:
976    // the stray closer was all that kept the string from being the statement
977    // below it, and once it goes `fold_docstrings` folds the pair into a `DOC`
978    // spanning both seams. Parse the neighbors together, through the real gap
979    // bytes, and require both seams to survive. Only reachable when the region
980    // is reduced to trivia, so the extra parse is rare and neighbor-sized.
981    if !frag
982        .cst
983        .children_with_tokens()
984        .any(|el| is_significant_child(&el))
985        && let (Some(prev), Some(next)) = (&prev_node, &next_node)
986    {
987        let back_gap = &prev_text[usize::from(prev.text_range().end())..region.start];
988        let fwd_gap = &prev_text[region.end..usize::from(next.text_range().start())];
989        let guard = format!(
990            "{}{}{}{}{}",
991            prev.text(),
992            back_gap,
993            fragment,
994            fwd_gap,
995            next.text()
996        );
997        let back_seam = usize::from(prev.text_range().len()) + back_gap.len();
998        let fwd_seam = back_seam + fragment.len();
999        let parsed = crate::parser::parse(&guard);
1000        if !no_straddle(&parsed.cst, back_seam) || !no_straddle(&parsed.cst, fwd_seam) {
1001            return None;
1002        }
1003    }
1004
1005    // A zero-width diagnostic exactly on a guard seam is disambiguated by
1006    // the fragment's own boundary child, mirroring `splice_diagnostics`: a
1007    // statement node owns a start-anchored marker at its start and an
1008    // end-anchored one at its end; a trivia boundary child owns nothing.
1009    let frag_starts_with_node = frag
1010        .cst
1011        .children_with_tokens()
1012        .next()
1013        .is_some_and(|el| el.as_node().is_some());
1014    let frag_ends_with_node = frag
1015        .cst
1016        .children_with_tokens()
1017        .last()
1018        .is_some_and(|el| el.as_node().is_some());
1019
1020    // Backward boundary parse: previous statement + gap trivia + fragment
1021    // must keep a boundary exactly at the old one, and the fragment must
1022    // parse in context with exactly the diagnostics it produced in
1023    // isolation.
1024    if let Some(prev) = &prev_node {
1025        let back_gap = &prev_text[usize::from(prev.text_range().end())..region.start];
1026        let guard = format!("{}{}{}", prev.text(), back_gap, fragment);
1027        let seam = guard.len() - fragment.len();
1028        let parsed = crate::parser::parse(&guard);
1029        if !no_straddle(&parsed.cst, seam) {
1030            return None;
1031        }
1032        let guard_frag: Vec<ParseDiagnostic> = parsed
1033            .diagnostics
1034            .iter()
1035            .filter(|d| {
1036                d.start > seam
1037                    || (d.start == seam && d.end > seam)
1038                    || (d.start == seam && d.end == seam && frag_starts_with_node)
1039            })
1040            .map(|d| {
1041                let mut d = d.clone();
1042                d.start -= seam;
1043                d.end -= seam;
1044                d
1045            })
1046            .collect();
1047        if guard_frag != frag.diagnostics {
1048            return None;
1049        }
1050    }
1051
1052    // Forward boundary parse: fragment + gap trivia + next statement (or the
1053    // trailing trivia to EOF when no statement follows). Three checks
1054    // against one parse of the concatenation: no element straddles the seam;
1055    // the fragment reparses exactly as it did in isolation (an EOF-adjacent
1056    // junk run wraps differently once text follows it); and the kept next
1057    // statement reappears untouched — same start, kind, and length — since a
1058    // fragment ending in an unterminated bracket can consume the separating
1059    // newline and demote the next line to flat junk without anything
1060    // straddling the seam.
1061    let tail = match &next_node {
1062        Some(next) => {
1063            let gap = &prev_text[region.end..usize::from(next.text_range().start())];
1064            format!("{}{}", gap, next.text())
1065        }
1066        None => prev_text[region.end..].to_string(),
1067    };
1068    if !tail.is_empty() {
1069        let guard = format!("{fragment}{tail}");
1070        let seam = fragment.len();
1071        let parsed = crate::parser::parse(&guard);
1072        if !no_straddle(&parsed.cst, seam) {
1073            return None;
1074        }
1075        let signature = |el: crate::syntax::SyntaxElement| {
1076            (
1077                usize::from(el.text_range().start()),
1078                el.as_node().is_some(),
1079                el.kind(),
1080                usize::from(el.text_range().len()),
1081            )
1082        };
1083        let frag_sig: Vec<_> = frag.cst.children_with_tokens().map(signature).collect();
1084        let pre_seam: Vec<_> = parsed
1085            .cst
1086            .children_with_tokens()
1087            .filter(|el| {
1088                let r = el.text_range();
1089                // A zero-width child exactly at the seam pairs with a junk
1090                // run on the far side; it belongs to the tail.
1091                usize::from(r.end()) <= seam && !(r.is_empty() && usize::from(r.start()) == seam)
1092            })
1093            .map(signature)
1094            .collect();
1095        if pre_seam != frag_sig {
1096            return None;
1097        }
1098        // The fragment's in-context diagnostics must also match: a trailing
1099        // token at the fragment's EOF can emit differently once text follows
1100        // it (`:` with a newline after it flags `QuoteColonWhitespace`; at
1101        // EOF it does not).
1102        let guard_frag: Vec<ParseDiagnostic> = parsed
1103            .diagnostics
1104            .iter()
1105            .filter(|d| {
1106                d.end < seam
1107                    || (d.end == seam && d.start < seam)
1108                    || (d.start == seam && d.end == seam && frag_ends_with_node)
1109            })
1110            .cloned()
1111            .collect();
1112        if guard_frag != frag.diagnostics {
1113            return None;
1114        }
1115        if let Some(next) = &next_node {
1116            let gap_len = usize::from(next.text_range().start()) - region.end;
1117            let reparsed_next =
1118                positive_nodes(&parsed.cst).find(|n| usize::from(n.text_range().start()) >= seam);
1119            let intact = reparsed_next.is_some_and(|n| {
1120                usize::from(n.text_range().start()) == seam + gap_len
1121                    && n.kind() == next.kind()
1122                    && n.text_range().len() == next.text_range().len()
1123            });
1124            if !intact {
1125                return None;
1126            }
1127        }
1128    }
1129
1130    let diagnostics = splice_diagnostics(prev_diags, &frag.diagnostics, &region, delta)?;
1131
1132    let frag_green = frag.cst.green();
1133    let green = prev_green.splice_children(
1134        region.first..=region.last,
1135        frag_green.children().map(|c| c.to_owned()),
1136    );
1137    Some(Reparsed {
1138        green,
1139        diagnostics,
1140        tier: ReparseTier::TopLevel,
1141    })
1142}
1143
1144#[cfg(test)]
1145mod tests {
1146    use super::*;
1147
1148    fn edit(range: std::ops::Range<usize>, insert: &str) -> Edit {
1149        Edit {
1150            range,
1151            insert: insert.to_string(),
1152        }
1153    }
1154
1155    /// The grammar decides some tree shapes by an identifier's *text*, and the
1156    /// token tier's same-kind relex cannot see such a change — so every such
1157    /// word has to be in [`CONTEXTUAL_IDENTS`]. Nothing in the type system says
1158    /// so, and the oracle only surfaces an omission by luck, so scan the
1159    /// grammar for the two spellings those comparisons take and check the words
1160    /// they name.
1161    ///
1162    /// The known words are asserted to have been *found*, not just listed: if a
1163    /// comparison is ever rewritten into a shape this scan does not recognize,
1164    /// the test fails loudly rather than quietly covering nothing.
1165    #[test]
1166    fn every_contextual_ident_is_listed() {
1167        // `t.kind == TokKind::Ident && t.text == "word"` and any form that
1168        // passes `t.text` along to a comparison, `matches!(t.text, "word" |
1169        // "other")` above all. Both are keyed on `t.text`, which is what makes
1170        // them text-structural.
1171        fn words_after(haystack: &str, marker: &str) -> Vec<String> {
1172            let mut out = Vec::new();
1173            for tail in haystack.split(marker).skip(1) {
1174                // Take the literals in the comparison that follows, stopping at
1175                // the first token that ends it.
1176                let stop = tail.find([';', '{', '}']).unwrap_or(tail.len());
1177                let mut rest = &tail[..stop];
1178                while let Some(open) = rest.find('"') {
1179                    let Some(close) = rest[open + 1..].find('"') else {
1180                        break;
1181                    };
1182                    out.push(rest[open + 1..open + 1 + close].to_string());
1183                    rest = &rest[open + 1 + close + 1..];
1184                }
1185            }
1186            out
1187        }
1188
1189        // The grammar files, read from source: this is a lint over the code,
1190        // not over anything the crate exposes at runtime.
1191        let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("src/parser");
1192        let mut found: Vec<String> = Vec::new();
1193        for name in ["expr.rs", "structural.rs", "core.rs", "recovery.rs"] {
1194            let src = std::fs::read_to_string(dir.join(name))
1195                .unwrap_or_else(|e| panic!("read {name}: {e}"));
1196            found.extend(words_after(&src, "t.text =="));
1197            found.extend(words_after(&src, "t.text,"));
1198            found.extend(words_after(&src, "next.text =="));
1199        }
1200        assert!(
1201            !found.is_empty(),
1202            "the scan matched nothing — the grammar's `Ident`-text comparisons \
1203             have been rewritten, and this guard is no longer guarding anything"
1204        );
1205
1206        for word in &found {
1207            assert!(
1208                CONTEXTUAL_IDENTS.contains(&word.as_str()),
1209                "the grammar branches on the identifier text {word:?}, so an \
1210                 edit into or out of it can reshape the tree under an unchanged \
1211                 token kind. Add it to CONTEXTUAL_IDENTS.",
1212            );
1213        }
1214
1215        // Every word the scan is known to reach today. A rewrite that hides one
1216        // from the scan trips this rather than silently narrowing the guard.
1217        for expected in ["as", "abstract", "primitive", "type", "typegroup", "public"] {
1218            assert!(
1219                found.iter().any(|w| w == expected),
1220                "the scan no longer finds the {expected:?} comparison",
1221            );
1222        }
1223    }
1224
1225    #[test]
1226    fn fingerprint_is_stable_and_discriminating() {
1227        let a1 = fingerprint(&crate::parser::parse("x = 1\n").cst);
1228        let a2 = fingerprint(&crate::parser::parse("x = 1\n").cst);
1229        let b = fingerprint(&crate::parser::parse("x = 2\n").cst);
1230        assert_eq!(a1, a2);
1231        assert_ne!(a1, b);
1232    }
1233
1234    /// A numeric literal is deliberately outside `TOKEN_REPARSE_KINDS`, and a
1235    /// lone `x = 1` statement is the whole `ROOT`, so the top-level tier finds
1236    /// no decoupled region either.
1237    #[test]
1238    fn a_number_edit_in_a_lone_statement_falls_back() {
1239        let parsed = crate::parser::parse("x = 1\n");
1240        let green = parsed.cst.green().to_owned();
1241        let e = diff_edit("x = 1\n", "x = 2\n");
1242        assert!(reparse("x = 1\n", &green, &parsed.diagnostics, &e, "x = 2\n").is_none());
1243    }
1244
1245    /// The point of the `STRING_CONTENT` path: a docstring body edit stays at
1246    /// the token tier. `fold_docstrings` folds a docstring with the definition
1247    /// it documents into one `ROOT` child, so the statement tier would answer
1248    /// this by reparsing the docstring *and* the whole function under it.
1249    #[test]
1250    fn a_docstring_body_edit_stays_at_the_token_tier() {
1251        let old = "\"\"\"\ndoc\n\"\"\"\nfunction f(x)\n    x + 1\nend\n";
1252        let parsed = crate::parser::parse(old);
1253        let green = parsed.cst.green().to_owned();
1254        let e = edit(5..5, "s");
1255        let new = e.apply(old);
1256
1257        let out = reparse(old, &green, &parsed.diagnostics, &e, &new)
1258            .expect("a docstring body edit is spliceable");
1259        assert_eq!(out.tier, ReparseTier::Token);
1260    }
1261
1262    /// An unterminated literal runs to EOF, so its node is the rest of the
1263    /// file. The diagnostic bail must reject a content edit inside one — and
1264    /// must do so before either relex, which is why it is hoisted to the top
1265    /// of `try_splice_string_content`.
1266    #[test]
1267    fn a_content_edit_in_an_unterminated_literal_falls_back() {
1268        let old = "x = 1\ny = \"abc\nz = 2\n";
1269        let parsed = crate::parser::parse(old);
1270        let green = parsed.cst.green().to_owned();
1271        // Offset 12 is inside the content run, which here swallows the rest of
1272        // the file; `UnterminatedLiteral` is anchored at the literal's start.
1273        let token = SyntaxNode::new_root(green.clone())
1274            .token_at_offset(TextSize::new(12))
1275            .right_biased()
1276            .expect("a leaf at offset 12");
1277        assert_eq!(token.kind(), SyntaxKind::STRING_CONTENT);
1278
1279        let e = edit(12..13, "X");
1280        let new = e.apply(old);
1281        assert!(try_splice_string_content(old, &parsed.diagnostics, &e, &token).is_none());
1282        // The statement tier may still answer it (the in-crate Tenet-4 assert
1283        // validates that splice); what matters is that the token tier declined.
1284        let tier = reparse(old, &green, &parsed.diagnostics, &e, &new).map(|r| r.tier);
1285        assert_ne!(tier, Some(ReparseTier::Token));
1286    }
1287
1288    /// An edit that does not fit `prev_text` is rejected rather than applied at
1289    /// offsets that would panic on a slice. `reparse_edits` proves its chain
1290    /// with `try_apply_edits`; the single-edit entry point has to check too.
1291    #[test]
1292    fn reparse_rejects_an_edit_that_does_not_fit() {
1293        let old = "α = 1\n";
1294        let parsed = crate::parser::parse(old);
1295        let green = parsed.cst.green().to_owned();
1296        // `new_text` is deliberately not the edit's result: a misfitting edit
1297        // has none, which is the whole point.
1298        let run = |e: Edit| reparse(old, &green, &parsed.diagnostics, &e, old);
1299
1300        // Past the end of the text.
1301        assert!(run(edit(99..99, "x")).is_none());
1302        // Off a char boundary (α is two bytes).
1303        assert!(run(edit(1..1, "x")).is_none());
1304        // Inverted range (built by hand: a literal `4..2` is a clippy error).
1305        let inverted = Edit {
1306            range: std::ops::Range { start: 4, end: 2 },
1307            insert: "x".to_string(),
1308        };
1309        assert!(run(inverted).is_none());
1310    }
1311
1312    /// A region wide enough that answering it costs more than the full parse it
1313    /// avoids is declined on the cheap evidence, before any fragment parse. The
1314    /// shape is a collapsed `diff_edit` of scattered edits, which spans
1315    /// everything between the first and the last.
1316    #[test]
1317    fn a_region_covering_most_of_a_large_file_is_declined() {
1318        let mut old = String::new();
1319        for i in 0..2000 {
1320            old.push_str(&format!("var_{i} = {i}\n"));
1321        }
1322        let parsed = crate::parser::parse(&old);
1323        let green = parsed.cst.green().to_owned();
1324
1325        // A narrow edit near the end still splices: the guard keys on the
1326        // region, not on the file size.
1327        let narrow = edit(old.len()..old.len(), "tail = 1\n");
1328        assert!(
1329            reparse(
1330                &old,
1331                &green,
1332                &parsed.diagnostics,
1333                &narrow,
1334                &narrow.apply(&old)
1335            )
1336            .is_some()
1337        );
1338
1339        // The same net change seen as one collapsed edit spanning most of the
1340        // file: `select_region` returns nearly every child, and the tier bails.
1341        // Both sites are inside an identifier, and the second is expressed
1342        // against the text the first produced (one byte longer), so the chain
1343        // below stays at the token tier. The last line is `var_1999 = 1999\n`,
1344        // 16 bytes, whose name runs from its start.
1345        let scattered = vec![edit(4..4, "X"), edit(old.len() - 11..old.len() - 11, "X")];
1346        let new = apply_edits(&old, &scattered);
1347        let collapsed = diff_edit(&old, &new);
1348        assert!(collapsed.range.len() > old.len() / 2, "{collapsed:?}");
1349        assert!(reparse(&old, &green, &parsed.diagnostics, &collapsed, &new).is_none());
1350
1351        // Replaying the chain still answers it at the token tier — the guard
1352        // costs the precise-edit path nothing.
1353        let out = reparse_edits(&old, &green, &parsed.diagnostics, &scattered, &new)
1354            .expect("the precise chain is unaffected");
1355        assert_eq!(out.tier, ReparseTier::Token);
1356    }
1357
1358    /// The width guard is a fraction *and* a floor: a small file's region is
1359    /// always worth trying, however much of the file it covers.
1360    #[test]
1361    fn the_region_width_guard_leaves_small_files_alone() {
1362        assert!(!region_is_too_wide(4 * 1024, 4 * 1024));
1363        assert!(!region_is_too_wide(64 * 1024, 1024 * 1024));
1364        assert!(region_is_too_wide(64 * 1024, 128 * 1024));
1365    }
1366
1367    /// The shape `reparse_edits` exists for: two identifier edits far apart,
1368    /// which `diff_edit` would collapse into one span covering both statements.
1369    #[test]
1370    fn reparse_edits_chains_scattered_edits() {
1371        let old = "alpha = 1\nfiller = 2\nomega = 3\n";
1372        let parsed = crate::parser::parse(old);
1373        let green = parsed.cst.green().to_owned();
1374        // `alpha` -> `alphaX`, then `omega` -> `omegaX` at its post-first-edit
1375        // offset (one byte further along).
1376        let edits = vec![edit(5..5, "X"), edit(27..27, "X")];
1377        let new = apply_edits(old, &edits);
1378        assert_eq!(new, "alphaX = 1\nfiller = 2\nomegaX = 3\n");
1379
1380        // The collapsed diff spans from `alpha` all the way to `omega`, so the
1381        // cheap token tier cannot touch it and the whole run of statements has
1382        // to be reparsed. Replaying the chain keeps both splices at the token
1383        // tier. On three statements that is a wash; on a real file the
1384        // difference is two orders of magnitude (`benches/reparse.rs`), which
1385        // is why the chain is tried first.
1386        let collapsed = diff_edit(old, &new);
1387        assert!(collapsed.range.len() > 20, "{collapsed:?} should be coarse");
1388        let via_diff = reparse(old, &green, &parsed.diagnostics, &collapsed, &new)
1389            .expect("the whole-file region is still spliceable at this size");
1390        assert_eq!(via_diff.tier, ReparseTier::TopLevel);
1391
1392        let out = reparse_edits(old, &green, &parsed.diagnostics, &edits, &new)
1393            .expect("two identifier edits should chain");
1394        assert_eq!(out.tier, ReparseTier::Token);
1395        assert_eq!(
1396            fingerprint(&SyntaxNode::new_root(out.green)),
1397            fingerprint(&crate::parser::parse(&new).cst),
1398        );
1399    }
1400
1401    /// The chain reports the most expensive tier it had to reach.
1402    #[test]
1403    fn reparse_edits_reports_the_max_tier() {
1404        let old = "alpha = 1\nfiller = 2\nomega = 3\n";
1405        let parsed = crate::parser::parse(old);
1406        let green = parsed.cst.green().to_owned();
1407        // An ident edit (token tier) plus a whole added statement (top level),
1408        // appended at the post-first-edit end of the buffer.
1409        let edits = vec![edit(5..5, "X"), edit(32..32, "beta = 4\n")];
1410        let new = apply_edits(old, &edits);
1411
1412        let out = reparse_edits(old, &green, &parsed.diagnostics, &edits, &new)
1413            .expect("ident edit plus a new statement should chain");
1414        assert_eq!(out.tier, ReparseTier::TopLevel);
1415    }
1416
1417    /// Fewer than two edits is always `diff_edit`'s job: its span for the same
1418    /// transform is contained in the single edit's, and the caller tried it.
1419    #[test]
1420    fn reparse_edits_declines_short_chains() {
1421        let old = "alpha = 1\nomega = 3\n";
1422        let parsed = crate::parser::parse(old);
1423        let green = parsed.cst.green().to_owned();
1424
1425        assert!(reparse_edits(old, &green, &parsed.diagnostics, &[], old).is_none());
1426        let one = vec![edit(5..5, "X")];
1427        let new = apply_edits(old, &one);
1428        assert!(reparse_edits(old, &green, &parsed.diagnostics, &one, &new).is_none());
1429    }
1430
1431    /// A chain that is not the exact transform between the two texts is
1432    /// rejected before any offset is trusted — both when it simply does not
1433    /// reproduce the target, and when it does not fit the source at all.
1434    #[test]
1435    fn reparse_edits_rejects_a_stale_chain() {
1436        let old = "alpha = 1\nfiller = 2\nomega = 3\n";
1437        let parsed = crate::parser::parse(old);
1438        let green = parsed.cst.green().to_owned();
1439
1440        // Applies cleanly, but the buffer moved on underneath it.
1441        let edits = vec![edit(5..5, "X"), edit(26..26, "X")];
1442        let elsewhere = "alphaX = 1\nfiller = 2\nomegaX = 3\nextra = 4\n";
1443        assert!(reparse_edits(old, &green, &parsed.diagnostics, &edits, elsewhere).is_none());
1444
1445        // Does not even fit the source text.
1446        let past_end = vec![edit(500..500, "X"), edit(501..501, "X")];
1447        assert!(reparse_edits(old, &green, &parsed.diagnostics, &past_end, old).is_none());
1448    }
1449
1450    /// One unhandleable step aborts the whole chain — the caller full-parses.
1451    #[test]
1452    fn reparse_edits_aborts_on_an_unhandleable_step() {
1453        let old = "alpha = 1\nfiller = 2\nomega = 3\n";
1454        let parsed = crate::parser::parse(old);
1455        let green = parsed.cst.green().to_owned();
1456        // The second edit opens an unterminated string, which no tier splices.
1457        let edits = vec![edit(5..5, "X"), edit(26..26, "\"")];
1458        let new = apply_edits(old, &edits);
1459        assert!(reparse_edits(old, &green, &parsed.diagnostics, &edits, &new).is_none());
1460    }
1461}