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

ra_ap_text_edit/
lib.rs
