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