1 //! Representation of a `TextEdit`.
2 //!
3 //! `rust-analyzer` never mutates text itself and only sends diffs to clients,
4 //! so `TextEdit` is the ultimate representation of the work done by
5 //! rust-analyzer.
6
7 #![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
8
9 use itertools::Itertools;
10 use std::cmp::max;
11 pub use text_size::{TextRange, TextSize};
12
13 /// `InsertDelete` -- a single "atomic" change to text
14 ///
15 /// Must not overlap with other `InDel`s
16 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
17 pub struct Indel {
18 pub insert: String,
19 /// Refers to offsets in the original text
20 pub delete: TextRange,
21 }
22
23 #[derive(Default, Debug, Clone)]
24 pub struct TextEdit {
25 /// Invariant: disjoint and sorted by `delete`.
26 indels: Vec<Indel>,
27 }
28
29 #[derive(Debug, Default, Clone)]
30 pub struct TextEditBuilder {
31 indels: Vec<Indel>,
32 }
33
34 impl Indel {
insert(offset: TextSize, text: String) -> Indel35 pub fn insert(offset: TextSize, text: String) -> Indel {
36 Indel::replace(TextRange::empty(offset), text)
37 }
delete(range: TextRange) -> Indel38 pub fn delete(range: TextRange) -> Indel {
39 Indel::replace(range, String::new())
40 }
replace(range: TextRange, replace_with: String) -> Indel41 pub fn replace(range: TextRange, replace_with: String) -> Indel {
42 Indel { delete: range, insert: replace_with }
43 }
44
apply(&self, text: &mut String)45 pub fn apply(&self, text: &mut String) {
46 let start: usize = self.delete.start().into();
47 let end: usize = self.delete.end().into();
48 text.replace_range(start..end, &self.insert);
49 }
50 }
51
52 impl TextEdit {
builder() -> TextEditBuilder53 pub fn builder() -> TextEditBuilder {
54 TextEditBuilder::default()
55 }
56
insert(offset: TextSize, text: String) -> TextEdit57 pub fn insert(offset: TextSize, text: String) -> TextEdit {
58 let mut builder = TextEdit::builder();
59 builder.insert(offset, text);
60 builder.finish()
61 }
62
delete(range: TextRange) -> TextEdit63 pub fn delete(range: TextRange) -> TextEdit {
64 let mut builder = TextEdit::builder();
65 builder.delete(range);
66 builder.finish()
67 }
68
replace(range: TextRange, replace_with: String) -> TextEdit69 pub fn replace(range: TextRange, replace_with: String) -> TextEdit {
70 let mut builder = TextEdit::builder();
71 builder.replace(range, replace_with);
72 builder.finish()
73 }
74
len(&self) -> usize75 pub fn len(&self) -> usize {
76 self.indels.len()
77 }
78
is_empty(&self) -> bool79 pub fn is_empty(&self) -> bool {
80 self.indels.is_empty()
81 }
82
iter(&self) -> std::slice::Iter<'_, Indel>83 pub fn iter(&self) -> std::slice::Iter<'_, Indel> {
84 self.into_iter()
85 }
86
apply(&self, text: &mut String)87 pub fn apply(&self, text: &mut String) {
88 match self.len() {
89 0 => return,
90 1 => {
91 self.indels[0].apply(text);
92 return;
93 }
94 _ => (),
95 }
96
97 let text_size = TextSize::of(&*text);
98 let mut total_len = text_size;
99 let mut max_total_len = text_size;
100 for indel in &self.indels {
101 total_len += TextSize::of(&indel.insert);
102 total_len -= indel.delete.len();
103 max_total_len = max(max_total_len, total_len);
104 }
105
106 if let Some(additional) = max_total_len.checked_sub(text_size) {
107 text.reserve(additional.into());
108 }
109
110 for indel in self.indels.iter().rev() {
111 indel.apply(text);
112 }
113
114 assert_eq!(TextSize::of(&*text), total_len);
115 }
116
union(&mut self, other: TextEdit) -> Result<(), TextEdit>117 pub fn union(&mut self, other: TextEdit) -> Result<(), TextEdit> {
118 let iter_merge =
119 self.iter().merge_by(other.iter(), |l, r| l.delete.start() <= r.delete.start());
120 if !check_disjoint(&mut iter_merge.clone()) {
121 return Err(other);
122 }
123
124 // Only dedup deletions and replacements, keep all insertions
125 self.indels = iter_merge.dedup_by(|a, b| a == b && !a.delete.is_empty()).cloned().collect();
126 Ok(())
127 }
128
apply_to_offset(&self, offset: TextSize) -> Option<TextSize>129 pub fn apply_to_offset(&self, offset: TextSize) -> Option<TextSize> {
130 let mut res = offset;
131 for indel in &self.indels {
132 if indel.delete.start() >= offset {
133 break;
134 }
135 if offset < indel.delete.end() {
136 return None;
137 }
138 res += TextSize::of(&indel.insert);
139 res -= indel.delete.len();
140 }
141 Some(res)
142 }
143 }
144
145 impl IntoIterator for TextEdit {
146 type Item = Indel;
147 type IntoIter = std::vec::IntoIter<Indel>;
148
into_iter(self) -> Self::IntoIter149 fn into_iter(self) -> Self::IntoIter {
150 self.indels.into_iter()
151 }
152 }
153
154 impl<'a> IntoIterator for &'a TextEdit {
155 type Item = &'a Indel;
156 type IntoIter = std::slice::Iter<'a, Indel>;
157
into_iter(self) -> Self::IntoIter158 fn into_iter(self) -> Self::IntoIter {
159 self.indels.iter()
160 }
161 }
162
163 impl TextEditBuilder {
is_empty(&self) -> bool164 pub fn is_empty(&self) -> bool {
165 self.indels.is_empty()
166 }
replace(&mut self, range: TextRange, replace_with: String)167 pub fn replace(&mut self, range: TextRange, replace_with: String) {
168 self.indel(Indel::replace(range, replace_with));
169 }
delete(&mut self, range: TextRange)170 pub fn delete(&mut self, range: TextRange) {
171 self.indel(Indel::delete(range));
172 }
insert(&mut self, offset: TextSize, text: String)173 pub fn insert(&mut self, offset: TextSize, text: String) {
174 self.indel(Indel::insert(offset, text));
175 }
finish(self) -> TextEdit176 pub fn finish(self) -> TextEdit {
177 let mut indels = self.indels;
178 assert_disjoint_or_equal(&mut indels);
179 indels = coalesce_indels(indels);
180 TextEdit { indels }
181 }
invalidates_offset(&self, offset: TextSize) -> bool182 pub fn invalidates_offset(&self, offset: TextSize) -> bool {
183 self.indels.iter().any(|indel| indel.delete.contains_inclusive(offset))
184 }
indel(&mut self, indel: Indel)185 fn indel(&mut self, indel: Indel) {
186 self.indels.push(indel);
187 if self.indels.len() <= 16 {
188 assert_disjoint_or_equal(&mut self.indels);
189 }
190 }
191 }
192
assert_disjoint_or_equal(indels: &mut [Indel])193 fn assert_disjoint_or_equal(indels: &mut [Indel]) {
194 assert!(check_disjoint_and_sort(indels));
195 }
196
check_disjoint_and_sort(indels: &mut [Indel]) -> bool197 fn check_disjoint_and_sort(indels: &mut [Indel]) -> bool {
198 indels.sort_by_key(|indel| (indel.delete.start(), indel.delete.end()));
199 check_disjoint(&mut indels.iter())
200 }
201
check_disjoint<'a, I>(indels: &mut I) -> bool where I: std::iter::Iterator<Item = &'a Indel> + Clone,202 fn check_disjoint<'a, I>(indels: &mut I) -> bool
203 where
204 I: std::iter::Iterator<Item = &'a Indel> + Clone,
205 {
206 indels.clone().zip(indels.skip(1)).all(|(l, r)| l.delete.end() <= r.delete.start() || l == r)
207 }
208
coalesce_indels(indels: Vec<Indel>) -> Vec<Indel>209 fn coalesce_indels(indels: Vec<Indel>) -> Vec<Indel> {
210 indels
211 .into_iter()
212 .coalesce(|mut a, b| {
213 if a.delete.end() == b.delete.start() {
214 a.insert.push_str(&b.insert);
215 a.delete = TextRange::new(a.delete.start(), b.delete.end());
216 Ok(a)
217 } else {
218 Err((a, b))
219 }
220 })
221 .collect_vec()
222 }
223
224 #[cfg(test)]
225 mod tests {
226 use super::{TextEdit, TextEditBuilder, TextRange};
227
range(start: u32, end: u32) -> TextRange228 fn range(start: u32, end: u32) -> TextRange {
229 TextRange::new(start.into(), end.into())
230 }
231
232 #[test]
test_apply()233 fn test_apply() {
234 let mut text = "_11h1_2222_xx3333_4444_6666".to_string();
235 let mut builder = TextEditBuilder::default();
236 builder.replace(range(3, 4), "1".to_string());
237 builder.delete(range(11, 13));
238 builder.insert(22.into(), "_5555".to_string());
239
240 let text_edit = builder.finish();
241 text_edit.apply(&mut text);
242
243 assert_eq!(text, "_1111_2222_3333_4444_5555_6666")
244 }
245
246 #[test]
test_union()247 fn test_union() {
248 let mut edit1 = TextEdit::delete(range(7, 11));
249 let mut builder = TextEditBuilder::default();
250 builder.delete(range(1, 5));
251 builder.delete(range(13, 17));
252
253 let edit2 = builder.finish();
254 assert!(edit1.union(edit2).is_ok());
255 assert_eq!(edit1.indels.len(), 3);
256 }
257
258 #[test]
test_union_with_duplicates()259 fn test_union_with_duplicates() {
260 let mut builder1 = TextEditBuilder::default();
261 builder1.delete(range(7, 11));
262 builder1.delete(range(13, 17));
263
264 let mut builder2 = TextEditBuilder::default();
265 builder2.delete(range(1, 5));
266 builder2.delete(range(13, 17));
267
268 let mut edit1 = builder1.finish();
269 let edit2 = builder2.finish();
270 assert!(edit1.union(edit2).is_ok());
271 assert_eq!(edit1.indels.len(), 3);
272 }
273
274 #[test]
test_union_panics()275 fn test_union_panics() {
276 let mut edit1 = TextEdit::delete(range(7, 11));
277 let edit2 = TextEdit::delete(range(9, 13));
278 assert!(edit1.union(edit2).is_err());
279 }
280
281 #[test]
test_coalesce_disjoint()282 fn test_coalesce_disjoint() {
283 let mut builder = TextEditBuilder::default();
284 builder.replace(range(1, 3), "aa".into());
285 builder.replace(range(5, 7), "bb".into());
286 let edit = builder.finish();
287
288 assert_eq!(edit.indels.len(), 2);
289 }
290
291 #[test]
test_coalesce_adjacent()292 fn test_coalesce_adjacent() {
293 let mut builder = TextEditBuilder::default();
294 builder.replace(range(1, 3), "aa".into());
295 builder.replace(range(3, 5), "bb".into());
296
297 let edit = builder.finish();
298 assert_eq!(edit.indels.len(), 1);
299 assert_eq!(edit.indels[0].insert, "aabb");
300 assert_eq!(edit.indels[0].delete, range(1, 5));
301 }
302
303 #[test]
test_coalesce_adjacent_series()304 fn test_coalesce_adjacent_series() {
305 let mut builder = TextEditBuilder::default();
306 builder.replace(range(1, 3), "au".into());
307 builder.replace(range(3, 5), "www".into());
308 builder.replace(range(5, 8), "".into());
309 builder.replace(range(8, 9), "ub".into());
310
311 let edit = builder.finish();
312 assert_eq!(edit.indels.len(), 1);
313 assert_eq!(edit.indels[0].insert, "auwwwub");
314 assert_eq!(edit.indels[0].delete, range(1, 9));
315 }
316 }
317