fatou_parser/parser/
edit.rs1use std::ops::Range;
11
12#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct Edit {
16 pub range: Range<usize>,
17 pub insert: String,
18}
19
20impl Edit {
21 pub fn delta(&self) -> isize {
23 self.insert.len() as isize - (self.range.end - self.range.start) as isize
24 }
25
26 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
37pub 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
50pub 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
73pub 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 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 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 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 assert_eq!(try_apply_edits("x = 1\n", &[edit(9..9, "!")]), None);
191 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 assert_eq!(try_apply_edits("α", &[edit(1..1, "!")]), None);
199 let edits = vec![edit(0..6, ""), edit(3..3, "!")];
201 assert_eq!(try_apply_edits("x = 1\n", &edits), None);
202 }
203}