Skip to main content

fatou_parser/parser/
edit.rs

1//! Byte-range text edits.
2//!
3//! [`Edit`] is the parser's one edit currency: a byte range in some old text
4//! plus the string that replaces it. These operations are pure text
5//! manipulation with no parser content; `super::reparse` re-exports them so
6//! `parser::Edit` stays the path the parser layer uses. Conversion from LSP
7//! `didChange` content changes lives host-side (`fatou::text`), keeping this
8//! crate free of protocol dependencies.
9
10use std::ops::Range;
11
12/// A single contiguous text edit: replace `range` (a byte range in the *old*
13/// text) with `insert`.
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct Edit {
16    pub range: Range<usize>,
17    pub insert: String,
18}
19
20impl Edit {
21    /// The signed length change this edit applies to text after `range`.
22    pub fn delta(&self) -> isize {
23        self.insert.len() as isize - (self.range.end - self.range.start) as isize
24    }
25
26    /// Apply the edit to `old`, producing the new text.
27    pub fn apply(&self, old: &str) -> String {
28        let mut out =
29            String::with_capacity(old.len().saturating_sub(self.range.len()) + self.insert.len());
30        out.push_str(&old[..self.range.start]);
31        out.push_str(&self.insert);
32        out.push_str(&old[self.range.end..]);
33        out
34    }
35}
36
37/// Apply `edits` to `old` left-to-right, each expressed against the text its
38/// predecessors produced (the shape LSP `didChange` batches arrive in). Folds
39/// in place, so peak memory is one text rather than one per edit.
40///
41/// # Panics
42///
43/// If any edit's range is out of bounds or off a char boundary of the text its
44/// predecessors produced. Use [`try_apply_edits`] for a slice that may be
45/// stale.
46pub fn apply_edits(old: &str, edits: &[Edit]) -> String {
47    try_apply_edits(old, edits).expect("apply_edits: edit slice does not fit the text")
48}
49
50/// [`apply_edits`] for an edit slice of unproven provenance: [`None`] when any
51/// edit's range does not fit the text its predecessors produced.
52///
53/// This is the apply-and-verify guard the incremental reparse leans on.
54/// Reconstructing the current buffer from an old snapshot plus an edit slice
55/// proves the slice is the exact transform between them, so a stale or
56/// misaligned sequence rejects — either here, or by comparing the result
57/// against the buffer — in favor of the whole-text [`diff_edit`] fallback.
58pub fn try_apply_edits(old: &str, edits: &[Edit]) -> Option<String> {
59    let mut text = old.to_string();
60    for e in edits {
61        if e.range.start > e.range.end
62            || e.range.end > text.len()
63            || !text.is_char_boundary(e.range.start)
64            || !text.is_char_boundary(e.range.end)
65        {
66            return None;
67        }
68        text.replace_range(e.range.clone(), &e.insert);
69    }
70    Some(text)
71}
72
73/// Recover a single contiguous [`Edit`] from a pair of full texts by stripping
74/// the common prefix and suffix. Multiple disjoint edits collapse into one
75/// spanning edit — still a correct transform, just coarser. Boundaries are
76/// clamped to char boundaries of both texts.
77pub fn diff_edit(old: &str, new: &str) -> Edit {
78    let ob = old.as_bytes();
79    let nb = new.as_bytes();
80
81    let mut prefix = 0;
82    let max_prefix = ob.len().min(nb.len());
83    while prefix < max_prefix && ob[prefix] == nb[prefix] {
84        prefix += 1;
85    }
86    while prefix > 0 && !old.is_char_boundary(prefix) {
87        prefix -= 1;
88    }
89
90    let mut suffix = 0;
91    let max_suffix = (ob.len() - prefix).min(nb.len() - prefix);
92    while suffix < max_suffix && ob[ob.len() - 1 - suffix] == nb[nb.len() - 1 - suffix] {
93        suffix += 1;
94    }
95    while suffix > 0
96        && (!old.is_char_boundary(old.len() - suffix) || !new.is_char_boundary(new.len() - suffix))
97    {
98        suffix -= 1;
99    }
100
101    Edit {
102        range: prefix..(old.len() - suffix),
103        insert: new[prefix..(new.len() - suffix)].to_string(),
104    }
105}
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110
111    fn edit(range: std::ops::Range<usize>, insert: &str) -> Edit {
112        Edit {
113            range,
114            insert: insert.to_string(),
115        }
116    }
117
118    #[test]
119    fn diff_edit_recovers_a_noop() {
120        assert_eq!(diff_edit("x = 1\n", "x = 1\n"), edit(6..6, ""));
121    }
122
123    #[test]
124    fn diff_edit_recovers_an_insertion() {
125        let e = diff_edit("x = 1\n", "x = 12\n");
126        assert_eq!(e, edit(5..5, "2"));
127        assert_eq!(e.apply("x = 1\n"), "x = 12\n");
128        assert_eq!(e.delta(), 1);
129    }
130
131    #[test]
132    fn diff_edit_recovers_a_deletion() {
133        let e = diff_edit("x = 12\n", "x = 1\n");
134        assert_eq!(e, edit(5..6, ""));
135        assert_eq!(e.apply("x = 12\n"), "x = 1\n");
136        assert_eq!(e.delta(), -1);
137    }
138
139    #[test]
140    fn diff_edit_recovers_a_replacement() {
141        let e = diff_edit("f(a, b)\n", "f(a, c)\n");
142        assert_eq!(e, edit(5..6, "c"));
143        assert_eq!(e.apply("f(a, b)\n"), "f(a, c)\n");
144        assert_eq!(e.delta(), 0);
145    }
146
147    #[test]
148    fn diff_edit_collapses_disjoint_edits_into_one_span() {
149        // Two edits (a→z at 0, c→z at 4) collapse into one spanning edit.
150        let e = diff_edit("a b c\n", "z b z\n");
151        assert_eq!(e, edit(0..5, "z b z"));
152        assert_eq!(e.apply("a b c\n"), "z b z\n");
153    }
154
155    #[test]
156    fn diff_edit_handles_whole_replacement_and_empty_texts() {
157        assert_eq!(diff_edit("", "x = 1\n"), edit(0..0, "x = 1\n"));
158        assert_eq!(diff_edit("x = 1\n", ""), edit(0..6, ""));
159        assert_eq!(diff_edit("abc", "xyz"), edit(0..3, "xyz"));
160    }
161
162    #[test]
163    fn diff_edit_clamps_to_char_boundaries() {
164        // α (0xCE 0xB1) and β (0xCE 0xB2) share their lead byte; a naive byte
165        // prefix would split the code point.
166        let e = diff_edit("α = 1\n", "β = 1\n");
167        assert_eq!(e, edit(0..2, "β"));
168        assert_eq!(e.apply("α = 1\n"), "β = 1\n");
169
170        // Shared trail bytes: ά vs ᾶ end in different code points whose UTF-8
171        // shares a final byte pattern only mid-character.
172        let old = "x\u{3AC}";
173        let new = "x\u{1FB6}";
174        let e = diff_edit(old, new);
175        assert!(old.is_char_boundary(e.range.start));
176        assert!(old.is_char_boundary(e.range.end));
177        assert_eq!(e.apply(old), new);
178    }
179
180    #[test]
181    fn apply_edits_chains_left_to_right() {
182        let edits = vec![edit(0..1, "y"), edit(4..5, "2")];
183        assert_eq!(apply_edits("x = 1\n", &edits), "y = 2\n");
184        assert_eq!(apply_edits("x = 1\n", &[]), "x = 1\n");
185    }
186
187    #[test]
188    fn try_apply_edits_rejects_a_slice_that_does_not_fit() {
189        // Past the end of the text.
190        assert_eq!(try_apply_edits("x = 1\n", &[edit(9..9, "!")]), None);
191        // Inverted range (built by hand: a literal `4..2` is a clippy error).
192        let inverted = Edit {
193            range: std::ops::Range { start: 4, end: 2 },
194            insert: "!".to_string(),
195        };
196        assert_eq!(try_apply_edits("x = 1\n", &[inverted]), None);
197        // Off a char boundary (α is two bytes).
198        assert_eq!(try_apply_edits("α", &[edit(1..1, "!")]), None);
199        // Only the *second* edit misfits: a chain rejects as a whole.
200        let edits = vec![edit(0..6, ""), edit(3..3, "!")];
201        assert_eq!(try_apply_edits("x = 1\n", &edits), None);
202    }
203}