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

ide_db/
text_edit.rs
