crates/text_edit/src/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
   7 pub use text_size::{TextRange, TextSize};
   8
   9 /// `InsertDelete` -- a single "atomic" change to text
  10 ///
  11 /// Must not overlap with other `InDel`s
  12 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  13 pub struct Indel {
  14     pub insert: String,
  15     /// Refers to offsets in the original text
  16     pub delete: TextRange,
  17 }
  18
  19 #[derive(Default, Debug, Clone)]
  20 pub struct TextEdit {
  21     /// Invariant: disjoint and sorted by `delete`.
  22     indels: Vec<Indel>,
  23 }
  24
  25 #[derive(Debug, Default, Clone)]
  26 pub struct TextEditBuilder {
  27     indels: Vec<Indel>,
  28 }
  29
  30 impl Indel {
  31     pub fn insert(offset: TextSize, text: String) -> Indel {
  32         Indel::replace(TextRange::empty(offset), text)
  33     }
  34     pub fn delete(range: TextRange) -> Indel {
  35         Indel::replace(range, String::new())
  36     }
  37     pub fn replace(range: TextRange, replace_with: String) -> Indel {
  38         Indel { delete: range, insert: replace_with }
  39     }
  40
  41     pub fn apply(&self, text: &mut String) {
  42         let start: usize = self.delete.start().into();
  43         let end: usize = self.delete.end().into();
  44         text.replace_range(start..end, &self.insert);
  45     }
  46 }
  47
  48 impl TextEdit {
  49     pub fn builder() -> TextEditBuilder {
  50         TextEditBuilder::default()
  51     }
  52
  53     pub fn insert(offset: TextSize, text: String) -> TextEdit {
  54         let mut builder = TextEdit::builder();
  55         builder.insert(offset, text);
  56         builder.finish()
  57     }
  58
  59     pub fn delete(range: TextRange) -> TextEdit {
  60         let mut builder = TextEdit::builder();
  61         builder.delete(range);
  62         builder.finish()
  63     }
  64
  65     pub fn replace(range: TextRange, replace_with: String) -> TextEdit {
  66         let mut builder = TextEdit::builder();
  67         builder.replace(range, replace_with);
  68         builder.finish()
  69     }
  70
  71     pub fn len(&self) -> usize {
  72         self.indels.len()
  73     }
  74
  75     pub fn is_empty(&self) -> bool {
  76         self.indels.is_empty()
  77     }
  78
  79     pub fn iter(&self) -> std::slice::Iter<'_, Indel> {
  80         self.into_iter()
  81     }
  82
  83     pub fn apply(&self, text: &mut String) {
  84         match self.len() {
  85             0 => return,
  86             1 => {
  87                 self.indels[0].apply(text);
  88                 return;
  89             }
  90             _ => (),
  91         }
  92
  93         let mut total_len = TextSize::of(&*text);
  94         for indel in &self.indels {
  95             total_len += TextSize::of(&indel.insert);
  96             total_len -= indel.delete.end() - indel.delete.start();
  97         }
  98         let mut buf = String::with_capacity(total_len.into());
  99         let mut prev = 0;
 100         for indel in &self.indels {
 101             let start: usize = indel.delete.start().into();
 102             let end: usize = indel.delete.end().into();
 103             if start > prev {
 104                 buf.push_str(&text[prev..start]);
 105             }
 106             buf.push_str(&indel.insert);
 107             prev = end;
 108         }
 109         buf.push_str(&text[prev..text.len()]);
 110         assert_eq!(TextSize::of(&buf), total_len);
 111
 112         // FIXME: figure out a way to mutate the text in-place or reuse the
 113         // memory in some other way
 114         *text = buf;
 115     }
 116
 117     pub fn union(&mut self, other: TextEdit) -> Result<(), TextEdit> {
 118         // FIXME: can be done without allocating intermediate vector
 119         let mut all = self.iter().chain(other.iter()).collect::<Vec<_>>();
 120         if !check_disjoint_and_sort(&mut all) {
 121             return Err(other);
 122         }
 123
 124         self.indels.extend(other.indels);
 125         check_disjoint_and_sort(&mut self.indels);
 126         // Only dedup deletions and replacements, keep all insertions
 127         self.indels.dedup_by(|a, b| a == b && !a.delete.is_empty());
 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
 147 impl IntoIterator for TextEdit {
 148     type Item = Indel;
 149     type IntoIter = std::vec::IntoIter<Indel>;
 150
 151     fn into_iter(self) -> Self::IntoIter {
 152         self.indels.into_iter()
 153     }
 154 }
 155
 156 impl<'a> IntoIterator for &'a TextEdit {
 157     type Item = &'a Indel;
 158     type IntoIter = std::slice::Iter<'a, Indel>;
 159
 160     fn into_iter(self) -> Self::IntoIter {
 161         self.indels.iter()
 162     }
 163 }
 164
 165 impl TextEditBuilder {
 166     pub fn is_empty(&self) -> bool {
 167         self.indels.is_empty()
 168     }
 169     pub fn replace(&mut self, range: TextRange, replace_with: String) {
 170         self.indel(Indel::replace(range, replace_with));
 171     }
 172     pub fn delete(&mut self, range: TextRange) {
 173         self.indel(Indel::delete(range));
 174     }
 175     pub fn insert(&mut self, offset: TextSize, text: String) {
 176         self.indel(Indel::insert(offset, text));
 177     }
 178     pub fn finish(self) -> TextEdit {
 179         let mut indels = self.indels;
 180         assert_disjoint_or_equal(&mut indels);
 181         TextEdit { indels }
 182     }
 183     pub fn invalidates_offset(&self, offset: TextSize) -> bool {
 184         self.indels.iter().any(|indel| indel.delete.contains_inclusive(offset))
 185     }
 186     fn indel(&mut self, indel: Indel) {
 187         self.indels.push(indel);
 188         if self.indels.len() <= 16 {
 189             assert_disjoint_or_equal(&mut self.indels);
 190         }
 191     }
 192 }
 193
 194 fn assert_disjoint_or_equal(indels: &mut [Indel]) {
 195     assert!(check_disjoint_and_sort(indels));
 196 }
 197 // FIXME: Remove the impl Bound here, it shouldn't be needed
 198 fn check_disjoint_and_sort(indels: &mut [impl std::borrow::Borrow<Indel>]) -> bool {
 199     indels.sort_by_key(|indel| (indel.borrow().delete.start(), indel.borrow().delete.end()));
 200     indels.iter().zip(indels.iter().skip(1)).all(|(l, r)| {
 201         let l = l.borrow();
 202         let r = r.borrow();
 203         l.delete.end() <= r.delete.start() || l == r
 204     })
 205 }
 206
 207 #[test]
 208 fn test_apply() {
 209     let mut text = "_11h1_2222_xx3333_4444_6666".to_string();
 210     let mut builder = TextEditBuilder::default();
 211     builder.replace(TextRange::new(3.into(), 4.into()), "1".to_string());
 212     builder.delete(TextRange::new(11.into(), 13.into()));
 213     builder.insert(22.into(), "_5555".to_string());
 214
 215     let text_edit = builder.finish();
 216     text_edit.apply(&mut text);
 217
 218     assert_eq!(text, "_1111_2222_3333_4444_5555_6666")
 219 }