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