From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- .../rust-analyzer/crates/text-edit/Cargo.toml | 14 ++ .../rust-analyzer/crates/text-edit/src/lib.rs | 264 +++++++++++++++++++++ 2 files changed, 278 insertions(+) create mode 100644 src/tools/rust-analyzer/crates/text-edit/Cargo.toml create mode 100644 src/tools/rust-analyzer/crates/text-edit/src/lib.rs (limited to 'src/tools/rust-analyzer/crates/text-edit') diff --git a/src/tools/rust-analyzer/crates/text-edit/Cargo.toml b/src/tools/rust-analyzer/crates/text-edit/Cargo.toml new file mode 100644 index 000000000..cf14bbd3c --- /dev/null +++ b/src/tools/rust-analyzer/crates/text-edit/Cargo.toml @@ -0,0 +1,14 @@ +[package] +name = "text-edit" +version = "0.0.0" +description = "TBD" +license = "MIT OR Apache-2.0" +edition = "2021" +rust-version = "1.57" + +[lib] +doctest = false + +[dependencies] +itertools = "0.10.3" +text-size = "1.1.0" diff --git a/src/tools/rust-analyzer/crates/text-edit/src/lib.rs b/src/tools/rust-analyzer/crates/text-edit/src/lib.rs new file mode 100644 index 000000000..9bb4271b6 --- /dev/null +++ b/src/tools/rust-analyzer/crates/text-edit/src/lib.rs @@ -0,0 +1,264 @@ +//! Representation of a `TextEdit`. +//! +//! `rust-analyzer` never mutates text itself and only sends diffs to clients, +//! so `TextEdit` is the ultimate representation of the work done by +//! rust-analyzer. + +#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)] + +use itertools::Itertools; +use std::cmp::max; +pub use text_size::{TextRange, TextSize}; + +/// `InsertDelete` -- a single "atomic" change to text +/// +/// Must not overlap with other `InDel`s +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Indel { + pub insert: String, + /// Refers to offsets in the original text + pub delete: TextRange, +} + +#[derive(Default, Debug, Clone)] +pub struct TextEdit { + /// Invariant: disjoint and sorted by `delete`. + indels: Vec, +} + +#[derive(Debug, Default, Clone)] +pub struct TextEditBuilder { + indels: Vec, +} + +impl Indel { + pub fn insert(offset: TextSize, text: String) -> Indel { + Indel::replace(TextRange::empty(offset), text) + } + pub fn delete(range: TextRange) -> Indel { + Indel::replace(range, String::new()) + } + pub fn replace(range: TextRange, replace_with: String) -> Indel { + Indel { delete: range, insert: replace_with } + } + + pub fn apply(&self, text: &mut String) { + let start: usize = self.delete.start().into(); + let end: usize = self.delete.end().into(); + text.replace_range(start..end, &self.insert); + } +} + +impl TextEdit { + pub fn builder() -> TextEditBuilder { + TextEditBuilder::default() + } + + pub fn insert(offset: TextSize, text: String) -> TextEdit { + let mut builder = TextEdit::builder(); + builder.insert(offset, text); + builder.finish() + } + + pub fn delete(range: TextRange) -> TextEdit { + let mut builder = TextEdit::builder(); + builder.delete(range); + builder.finish() + } + + pub fn replace(range: TextRange, replace_with: String) -> TextEdit { + let mut builder = TextEdit::builder(); + builder.replace(range, replace_with); + builder.finish() + } + + pub fn len(&self) -> usize { + self.indels.len() + } + + pub fn is_empty(&self) -> bool { + self.indels.is_empty() + } + + pub fn iter(&self) -> std::slice::Iter<'_, Indel> { + self.into_iter() + } + + pub fn apply(&self, text: &mut String) { + match self.len() { + 0 => return, + 1 => { + self.indels[0].apply(text); + return; + } + _ => (), + } + + let text_size = TextSize::of(&*text); + let mut total_len = text_size; + let mut max_total_len = text_size; + for indel in &self.indels { + total_len += TextSize::of(&indel.insert); + total_len -= indel.delete.len(); + max_total_len = max(max_total_len, total_len); + } + + if let Some(additional) = max_total_len.checked_sub(text_size) { + text.reserve(additional.into()); + } + + for indel in self.indels.iter().rev() { + indel.apply(text); + } + + assert_eq!(TextSize::of(&*text), total_len); + } + + pub fn union(&mut self, other: TextEdit) -> Result<(), TextEdit> { + let iter_merge = + self.iter().merge_by(other.iter(), |l, r| l.delete.start() <= r.delete.start()); + if !check_disjoint(&mut iter_merge.clone()) { + return Err(other); + } + + // Only dedup deletions and replacements, keep all insertions + self.indels = iter_merge.dedup_by(|a, b| a == b && !a.delete.is_empty()).cloned().collect(); + Ok(()) + } + + pub fn apply_to_offset(&self, offset: TextSize) -> Option { + let mut res = offset; + for indel in &self.indels { + if indel.delete.start() >= offset { + break; + } + if offset < indel.delete.end() { + return None; + } + res += TextSize::of(&indel.insert); + res -= indel.delete.len(); + } + Some(res) + } +} + +impl IntoIterator for TextEdit { + type Item = Indel; + type IntoIter = std::vec::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.indels.into_iter() + } +} + +impl<'a> IntoIterator for &'a TextEdit { + type Item = &'a Indel; + type IntoIter = std::slice::Iter<'a, Indel>; + + fn into_iter(self) -> Self::IntoIter { + self.indels.iter() + } +} + +impl TextEditBuilder { + pub fn is_empty(&self) -> bool { + self.indels.is_empty() + } + pub fn replace(&mut self, range: TextRange, replace_with: String) { + self.indel(Indel::replace(range, replace_with)); + } + pub fn delete(&mut self, range: TextRange) { + self.indel(Indel::delete(range)); + } + pub fn insert(&mut self, offset: TextSize, text: String) { + self.indel(Indel::insert(offset, text)); + } + pub fn finish(self) -> TextEdit { + let mut indels = self.indels; + assert_disjoint_or_equal(&mut indels); + TextEdit { indels } + } + pub fn invalidates_offset(&self, offset: TextSize) -> bool { + self.indels.iter().any(|indel| indel.delete.contains_inclusive(offset)) + } + fn indel(&mut self, indel: Indel) { + self.indels.push(indel); + if self.indels.len() <= 16 { + assert_disjoint_or_equal(&mut self.indels); + } + } +} + +fn assert_disjoint_or_equal(indels: &mut [Indel]) { + assert!(check_disjoint_and_sort(indels)); +} + +fn check_disjoint_and_sort(indels: &mut [Indel]) -> bool { + indels.sort_by_key(|indel| (indel.delete.start(), indel.delete.end())); + check_disjoint(&mut indels.iter()) +} + +fn check_disjoint<'a, I>(indels: &mut I) -> bool +where + I: std::iter::Iterator + Clone, +{ + indels.clone().zip(indels.skip(1)).all(|(l, r)| l.delete.end() <= r.delete.start() || l == r) +} + +#[cfg(test)] +mod tests { + use super::{TextEdit, TextEditBuilder, TextRange}; + + fn range(start: u32, end: u32) -> TextRange { + TextRange::new(start.into(), end.into()) + } + + #[test] + fn test_apply() { + let mut text = "_11h1_2222_xx3333_4444_6666".to_string(); + let mut builder = TextEditBuilder::default(); + builder.replace(range(3, 4), "1".to_string()); + builder.delete(range(11, 13)); + builder.insert(22.into(), "_5555".to_string()); + + let text_edit = builder.finish(); + text_edit.apply(&mut text); + + assert_eq!(text, "_1111_2222_3333_4444_5555_6666") + } + + #[test] + fn test_union() { + let mut edit1 = TextEdit::delete(range(7, 11)); + let mut builder = TextEditBuilder::default(); + builder.delete(range(1, 5)); + builder.delete(range(13, 17)); + + let edit2 = builder.finish(); + assert!(edit1.union(edit2).is_ok()); + assert_eq!(edit1.indels.len(), 3); + } + + #[test] + fn test_union_with_duplicates() { + let mut builder1 = TextEditBuilder::default(); + builder1.delete(range(7, 11)); + builder1.delete(range(13, 17)); + + let mut builder2 = TextEditBuilder::default(); + builder2.delete(range(1, 5)); + builder2.delete(range(13, 17)); + + let mut edit1 = builder1.finish(); + let edit2 = builder2.finish(); + assert!(edit1.union(edit2).is_ok()); + assert_eq!(edit1.indels.len(), 3); + } + + #[test] + fn test_union_panics() { + let mut edit1 = TextEdit::delete(range(7, 11)); + let edit2 = TextEdit::delete(range(9, 13)); + assert!(edit1.union(edit2).is_err()); + } +} -- cgit v1.2.3