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