ide_db/
text_edit.rs

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

ide_db/
text_edit.rs
