Merge #325

325: implement translate_offset_with_edit r=matklad a=vemoo

- Implement `translate_offset_with_edit` to resolve #105 
- Add proptest impls for text, offsets and edits and use them in tests for `translate_offset_with_edit` and `LineIndex`
- Added benchmark for `translate_offset_with_edit`

Co-authored-by: Bernardo <[email protected]>

9 files changed, 650 insertions, 150 deletions

diff --git a/crates/ra_editor/Cargo.toml b/crates/ra_editor/Cargo.toml
index c29be1350..f39fe4af6 100644
--- a/crates/ra_editor/Cargo.toml
+++ b/crates/ra_editor/Cargo.toml
@@ -16,3 +16,4 @@ ra_text_edit = { path = "../ra_text_edit" }
 
 [dev-dependencies]
 test_utils = { path = "../test_utils" }
+proptest = "0.8.7"
diff --git a/crates/ra_editor/src/lib.rs b/crates/ra_editor/src/lib.rs
index a8c68e79e..d9b89155b 100644
--- a/crates/ra_editor/src/lib.rs
+++ b/crates/ra_editor/src/lib.rs
@@ -2,6 +2,7 @@ mod code_actions;
 mod extend_selection;
 mod folding_ranges;
 mod line_index;
+mod line_index_utils;
 mod symbols;
 #[cfg(test)]
 mod test_utils;
@@ -12,6 +13,7 @@ pub use self::{
     extend_selection::extend_selection,
     folding_ranges::{folding_ranges, Fold, FoldKind},
     line_index::{LineCol, LineIndex},
+    line_index_utils::translate_offset_with_edit,
     symbols::{file_structure, file_symbols, FileSymbol, StructureNode},
     typing::{join_lines, on_enter, on_eq_typed},
 };
diff --git a/crates/ra_editor/src/line_index.rs b/crates/ra_editor/src/line_index.rs
index aab7e4081..898fee7e0 100644
--- a/crates/ra_editor/src/line_index.rs
+++ b/crates/ra_editor/src/line_index.rs
@@ -4,8 +4,8 @@ use superslice::Ext;
 
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub struct LineIndex {
-    newlines: Vec<TextUnit>,
-    utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
+    pub(crate) newlines: Vec<TextUnit>,
+    pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
 }
 
 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
@@ -15,9 +15,9 @@ pub struct LineCol {
 }
 
 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
-struct Utf16Char {
-    start: TextUnit,
-    end: TextUnit,
+pub(crate) struct Utf16Char {
+    pub(crate) start: TextUnit,
+    pub(crate) end: TextUnit,
 }
 
 impl Utf16Char {
@@ -62,6 +62,12 @@ impl LineIndex {
 
             curr_col += char_len;
         }
+
+        // Save any utf-16 characters seen in the last line
+        if utf16_chars.len() > 0 {
+            utf16_lines.insert(line, utf16_chars);
+        }
+
         LineIndex {
             newlines,
             utf16_lines,
@@ -122,111 +128,179 @@ impl LineIndex {
     }
 }
 
-#[test]
-fn test_line_index() {
-    let text = "hello\nworld";
-    let index = LineIndex::new(text);
-    assert_eq!(
-        index.line_col(0.into()),
-        LineCol {
-            line: 0,
-            col_utf16: 0
-        }
-    );
-    assert_eq!(
-        index.line_col(1.into()),
-        LineCol {
-            line: 0,
-            col_utf16: 1
-        }
-    );
-    assert_eq!(
-        index.line_col(5.into()),
-        LineCol {
-            line: 0,
-            col_utf16: 5
-        }
-    );
-    assert_eq!(
-        index.line_col(6.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 0
-        }
-    );
-    assert_eq!(
-        index.line_col(7.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 1
-        }
-    );
-    assert_eq!(
-        index.line_col(8.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 2
-        }
-    );
-    assert_eq!(
-        index.line_col(10.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 4
-        }
-    );
-    assert_eq!(
-        index.line_col(11.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 5
+#[cfg(test)]
+/// Simple reference implementation to use in proptests
+pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
+    let mut res = LineCol {
+        line: 0,
+        col_utf16: 0,
+    };
+    for (i, c) in text.char_indices() {
+        if i + c.len_utf8() > offset.to_usize() {
+            // if it's an invalid offset, inside a multibyte char
+            // return as if it was at the start of the char
+            break;
         }
-    );
-    assert_eq!(
-        index.line_col(12.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 6
+        if c == '\n' {
+            res.line += 1;
+            res.col_utf16 = 0;
+        } else {
+            res.col_utf16 += 1;
         }
-    );
+    }
+    res
+}
 
-    let text = "\nhello\nworld";
-    let index = LineIndex::new(text);
-    assert_eq!(
-        index.line_col(0.into()),
-        LineCol {
+#[cfg(test)]
+mod test_line_index {
+    use super::*;
+    use proptest::{prelude::*, proptest, proptest_helper};
+    use ra_text_edit::test_utils::{arb_text, arb_offset};
+
+    #[test]
+    fn test_line_index() {
+        let text = "hello\nworld";
+        let index = LineIndex::new(text);
+        assert_eq!(
+            index.line_col(0.into()),
+            LineCol {
+                line: 0,
+                col_utf16: 0
+            }
+        );
+        assert_eq!(
+            index.line_col(1.into()),
+            LineCol {
+                line: 0,
+                col_utf16: 1
+            }
+        );
+        assert_eq!(
+            index.line_col(5.into()),
+            LineCol {
+                line: 0,
+                col_utf16: 5
+            }
+        );
+        assert_eq!(
+            index.line_col(6.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 0
+            }
+        );
+        assert_eq!(
+            index.line_col(7.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 1
+            }
+        );
+        assert_eq!(
+            index.line_col(8.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 2
+            }
+        );
+        assert_eq!(
+            index.line_col(10.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 4
+            }
+        );
+        assert_eq!(
+            index.line_col(11.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 5
+            }
+        );
+        assert_eq!(
+            index.line_col(12.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 6
+            }
+        );
+
+        let text = "\nhello\nworld";
+        let index = LineIndex::new(text);
+        assert_eq!(
+            index.line_col(0.into()),
+            LineCol {
+                line: 0,
+                col_utf16: 0
+            }
+        );
+        assert_eq!(
+            index.line_col(1.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 0
+            }
+        );
+        assert_eq!(
+            index.line_col(2.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 1
+            }
+        );
+        assert_eq!(
+            index.line_col(6.into()),
+            LineCol {
+                line: 1,
+                col_utf16: 5
+            }
+        );
+        assert_eq!(
+            index.line_col(7.into()),
+            LineCol {
+                line: 2,
+                col_utf16: 0
+            }
+        );
+    }
+
+    fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> {
+        arb_text()
+            .prop_flat_map(|text| (arb_offset(&text), Just(text)))
+            .boxed()
+    }
+
+    fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
+        let mut res = LineCol {
             line: 0,
-            col_utf16: 0
-        }
-    );
-    assert_eq!(
-        index.line_col(1.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 0
-        }
-    );
-    assert_eq!(
-        index.line_col(2.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 1
-        }
-    );
-    assert_eq!(
-        index.line_col(6.into()),
-        LineCol {
-            line: 1,
-            col_utf16: 5
+            col_utf16: 0,
+        };
+        for (i, c) in text.char_indices() {
+            if i + c.len_utf8() > offset.to_usize() {
+                // if it's an invalid offset, inside a multibyte char
+                // return as if it was at the start of the char
+                break;
+            }
+            if c == '\n' {
+                res.line += 1;
+                res.col_utf16 = 0;
+            } else {
+                res.col_utf16 += 1;
+            }
         }
-    );
-    assert_eq!(
-        index.line_col(7.into()),
-        LineCol {
-            line: 2,
-            col_utf16: 0
+        res
+    }
+
+    proptest! {
+        #[test]
+        fn test_line_index_proptest((offset, text) in arb_text_with_offset()) {
+            let expected = to_line_col(&text, offset);
+            let line_index = LineIndex::new(&text);
+            let actual = line_index.line_col(offset);
+
+            assert_eq!(actual, expected);
         }
-    );
+    }
 }
 
 #[cfg(test)]
@@ -321,4 +395,5 @@ const C: char = \"メ メ\";
 
         assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
     }
+
 }
diff --git a/crates/ra_editor/src/line_index_utils.rs b/crates/ra_editor/src/line_index_utils.rs
new file mode 100644
index 000000000..ec3269bbb
--- /dev/null
+++ b/crates/ra_editor/src/line_index_utils.rs
@@ -0,0 +1,363 @@
+use ra_text_edit::{AtomTextEdit, TextEdit};
+use ra_syntax::{TextUnit, TextRange};
+use crate::{LineIndex, LineCol, line_index::Utf16Char};
+
+#[derive(Debug, Clone)]
+enum Step {
+    Newline(TextUnit),
+    Utf16Char(TextRange),
+}
+
+#[derive(Debug)]
+struct LineIndexStepIter<'a> {
+    line_index: &'a LineIndex,
+    next_newline_idx: usize,
+    utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>,
+}
+
+impl<'a> LineIndexStepIter<'a> {
+    fn from(line_index: &LineIndex) -> LineIndexStepIter {
+        let mut x = LineIndexStepIter {
+            line_index,
+            next_newline_idx: 0,
+            utf16_chars: None,
+        };
+        // skip first newline since it's not real
+        x.next();
+        x
+    }
+}
+
+impl<'a> Iterator for LineIndexStepIter<'a> {
+    type Item = Step;
+    fn next(&mut self) -> Option<Step> {
+        self.utf16_chars
+            .as_mut()
+            .and_then(|(newline, x)| {
+                let x = x.next()?;
+                Some(Step::Utf16Char(TextRange::from_to(
+                    *newline + x.start,
+                    *newline + x.end,
+                )))
+            })
+            .or_else(|| {
+                let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?;
+                self.utf16_chars = self
+                    .line_index
+                    .utf16_lines
+                    .get(&(self.next_newline_idx as u32))
+                    .map(|x| (next_newline, x.iter()));
+                self.next_newline_idx += 1;
+                Some(Step::Newline(next_newline))
+            })
+    }
+}
+
+#[derive(Debug)]
+struct OffsetStepIter<'a> {
+    text: &'a str,
+    offset: TextUnit,
+}
+
+impl<'a> Iterator for OffsetStepIter<'a> {
+    type Item = Step;
+    fn next(&mut self) -> Option<Step> {
+        let (next, next_offset) = self
+            .text
+            .char_indices()
+            .filter_map(|(i, c)| {
+                if c == '\n' {
+                    let next_offset = self.offset + TextUnit::from_usize(i + 1);
+                    let next = Step::Newline(next_offset);
+                    Some((next, next_offset))
+                } else {
+                    let char_len = TextUnit::of_char(c);
+                    if char_len.to_usize() > 1 {
+                        let start = self.offset + TextUnit::from_usize(i);
+                        let end = start + char_len;
+                        let next = Step::Utf16Char(TextRange::from_to(start, end));
+                        let next_offset = end;
+                        Some((next, next_offset))
+                    } else {
+                        None
+                    }
+                }
+            })
+            .next()?;
+        let next_idx = (next_offset - self.offset).to_usize();
+        self.text = &self.text[next_idx..];
+        self.offset = next_offset;
+        Some(next)
+    }
+}
+
+#[derive(Debug)]
+enum NextSteps<'a> {
+    Use,
+    ReplaceMany(OffsetStepIter<'a>),
+    AddMany(OffsetStepIter<'a>),
+}
+
+#[derive(Debug)]
+struct TranslatedEdit<'a> {
+    delete: TextRange,
+    insert: &'a str,
+    diff: i64,
+}
+
+struct Edits<'a> {
+    edits: &'a [AtomTextEdit],
+    current: Option<TranslatedEdit<'a>>,
+    acc_diff: i64,
+}
+
+impl<'a> Edits<'a> {
+    fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> {
+        let mut x = Edits {
+            edits: text_edit.as_atoms(),
+            current: None,
+            acc_diff: 0,
+        };
+        x.advance_edit();
+        x
+    }
+    fn advance_edit(&mut self) {
+        self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff);
+        match self.edits.split_first() {
+            Some((next, rest)) => {
+                let delete = self.translate_range(next.delete);
+                let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64;
+                self.current = Some(TranslatedEdit {
+                    delete,
+                    insert: &next.insert,
+                    diff,
+                });
+                self.edits = rest;
+            }
+            None => {
+                self.current = None;
+            }
+        }
+    }
+
+    fn next_inserted_steps(&mut self) -> Option<OffsetStepIter<'a>> {
+        let cur = self.current.as_ref()?;
+        let res = Some(OffsetStepIter {
+            offset: cur.delete.start(),
+            text: &cur.insert,
+        });
+        self.advance_edit();
+        res
+    }
+
+    fn next_steps(&mut self, step: &Step) -> NextSteps {
+        let step_pos = match step {
+            &Step::Newline(n) => n,
+            &Step::Utf16Char(r) => r.end(),
+        };
+        let res = match &mut self.current {
+            Some(edit) => {
+                if step_pos <= edit.delete.start() {
+                    NextSteps::Use
+                } else if step_pos <= edit.delete.end() {
+                    let iter = OffsetStepIter {
+                        offset: edit.delete.start(),
+                        text: &edit.insert,
+                    };
+                    // empty slice to avoid returning steps again
+                    edit.insert = &edit.insert[edit.insert.len()..];
+                    NextSteps::ReplaceMany(iter)
+                } else {
+                    let iter = OffsetStepIter {
+                        offset: edit.delete.start(),
+                        text: &edit.insert,
+                    };
+                    // empty slice to avoid returning steps again
+                    edit.insert = &edit.insert[edit.insert.len()..];
+                    self.advance_edit();
+                    NextSteps::AddMany(iter)
+                }
+            }
+            None => NextSteps::Use,
+        };
+        res
+    }
+
+    fn translate_range(&self, range: TextRange) -> TextRange {
+        if self.acc_diff == 0 {
+            range
+        } else {
+            let start = self.translate(range.start());
+            let end = self.translate(range.end());
+            TextRange::from_to(start, end)
+        }
+    }
+
+    fn translate(&self, x: TextUnit) -> TextUnit {
+        if self.acc_diff == 0 {
+            x
+        } else {
+            TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32)
+        }
+    }
+
+    fn translate_step(&self, x: &Step) -> Step {
+        if self.acc_diff == 0 {
+            x.clone()
+        } else {
+            match x {
+                &Step::Newline(n) => Step::Newline(self.translate(n)),
+                &Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)),
+            }
+        }
+    }
+}
+
+#[derive(Debug)]
+struct RunningLineCol {
+    line: u32,
+    last_newline: TextUnit,
+    col_adjust: TextUnit,
+}
+
+impl RunningLineCol {
+    fn new() -> RunningLineCol {
+        RunningLineCol {
+            line: 0,
+            last_newline: TextUnit::from(0),
+            col_adjust: TextUnit::from(0),
+        }
+    }
+
+    fn to_line_col(&self, offset: TextUnit) -> LineCol {
+        LineCol {
+            line: self.line,
+            col_utf16: ((offset - self.last_newline) - self.col_adjust).into(),
+        }
+    }
+
+    fn add_line(&mut self, newline: TextUnit) {
+        self.line += 1;
+        self.last_newline = newline;
+        self.col_adjust = TextUnit::from(0);
+    }
+
+    fn adjust_col(&mut self, range: &TextRange) {
+        self.col_adjust += range.len() - TextUnit::from(1);
+    }
+}
+
+pub fn translate_offset_with_edit(
+    line_index: &LineIndex,
+    offset: TextUnit,
+    text_edit: &TextEdit,
+) -> LineCol {
+    let mut state = Edits::from_text_edit(&text_edit);
+
+    let mut res = RunningLineCol::new();
+
+    macro_rules! test_step {
+        ($x:ident) => {
+            match &$x {
+                Step::Newline(n) => {
+                    if offset < *n {
+                        return res.to_line_col(offset);
+                    } else {
+                        res.add_line(*n);
+                    }
+                }
+                Step::Utf16Char(x) => {
+                    if offset < x.end() {
+                        // if the offset is inside a multibyte char it's invalid
+                        // clamp it to the start of the char
+                        let clamp = offset.min(x.start());
+                        return res.to_line_col(clamp);
+                    } else {
+                        res.adjust_col(x);
+                    }
+                }
+            }
+        };
+    }
+
+    for orig_step in LineIndexStepIter::from(line_index) {
+        loop {
+            let translated_step = state.translate_step(&orig_step);
+            match state.next_steps(&translated_step) {
+                NextSteps::Use => {
+                    test_step!(translated_step);
+                    break;
+                }
+                NextSteps::ReplaceMany(ns) => {
+                    for n in ns {
+                        test_step!(n);
+                    }
+                    break;
+                }
+                NextSteps::AddMany(ns) => {
+                    for n in ns {
+                        test_step!(n);
+                    }
+                }
+            }
+        }
+    }
+
+    loop {
+        match state.next_inserted_steps() {
+            None => break,
+            Some(ns) => {
+                for n in ns {
+                    test_step!(n);
+                }
+            }
+        }
+    }
+
+    res.to_line_col(offset)
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use proptest::{prelude::*, proptest, proptest_helper};
+    use crate::line_index;
+    use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit};
+    use ra_text_edit::TextEdit;
+
+    #[derive(Debug)]
+    struct ArbTextWithEditAndOffset {
+        text: String,
+        edit: TextEdit,
+        edited_text: String,
+        offset: TextUnit,
+    }
+
+    fn arb_text_with_edit_and_offset() -> BoxedStrategy<ArbTextWithEditAndOffset> {
+        arb_text_with_edit()
+            .prop_flat_map(|x| {
+                let edited_text = x.edit.apply(&x.text);
+                let arb_offset = arb_offset(&edited_text);
+                (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| {
+                    ArbTextWithEditAndOffset {
+                        text: x.text,
+                        edit: x.edit,
+                        edited_text,
+                        offset,
+                    }
+                })
+            })
+            .boxed()
+    }
+
+    proptest! {
+        #[test]
+        fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) {
+            let expected = line_index::to_line_col(&x.edited_text, x.offset);
+            let line_index = LineIndex::new(&x.text);
+            let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit);
+
+            assert_eq!(actual, expected);
+        }
+    }
+}
diff --git a/crates/ra_lsp_server/src/conv.rs b/crates/ra_lsp_server/src/conv.rs
index c0e4e3a36..d3670104e 100644
--- a/crates/ra_lsp_server/src/conv.rs
+++ b/crates/ra_lsp_server/src/conv.rs
@@ -3,7 +3,7 @@ use languageserver_types::{
     TextDocumentItem, TextDocumentPositionParams, Url, VersionedTextDocumentIdentifier, InsertTextFormat,
 };
 use ra_analysis::{FileId, FileSystemEdit, SourceChange, SourceFileEdit, FilePosition, CompletionItem, CompletionItemKind, InsertText};
-use ra_editor::{LineCol, LineIndex};
+use ra_editor::{LineCol, LineIndex, translate_offset_with_edit};
 use ra_text_edit::{AtomTextEdit, TextEdit};
 use ra_syntax::{SyntaxKind, TextRange, TextUnit};
 
@@ -238,13 +238,15 @@ impl TryConvWith for SourceChange {
             None => None,
             Some(pos) => {
                 let line_index = world.analysis().file_line_index(pos.file_id);
-                let edits = self
+                let edit = self
                     .source_file_edits
                     .iter()
                     .find(|it| it.file_id == pos.file_id)
-                    .map(|it| it.edit.as_atoms())
-                    .unwrap_or(&[]);
-                let line_col = translate_offset_with_edit(&*line_index, pos.offset, edits);
+                    .map(|it| &it.edit);
+                let line_col = match edit {
+                    Some(edit) => translate_offset_with_edit(&*line_index, pos.offset, edit),
+                    None => line_index.line_col(pos.offset),
+                };
                 let position =
                     Position::new(u64::from(line_col.line), u64::from(line_col.col_utf16));
                 Some(TextDocumentPositionParams {
@@ -264,41 +266,6 @@ impl TryConvWith for SourceChange {
     }
 }
 
-// HACK: we should translate offset to line/column using linde_index *with edits applied*.
-// A naive version of this function would be to apply `edits` to the original text,
-// construct a new line index and use that, but it would be slow.
-//
-// Writing fast & correct version is issue #105, let's use a quick hack in the meantime
-fn translate_offset_with_edit(
-    pre_edit_index: &LineIndex,
-    offset: TextUnit,
-    edits: &[AtomTextEdit],
-) -> LineCol {
-    let fallback = pre_edit_index.line_col(offset);
-    let edit = match edits.first() {
-        None => return fallback,
-        Some(edit) => edit,
-    };
-    let end_offset = edit.delete.start() + TextUnit::of_str(&edit.insert);
-    if !(edit.delete.start() <= offset && offset <= end_offset) {
-        return fallback;
-    }
-    let rel_offset = offset - edit.delete.start();
-    let in_edit_line_col = LineIndex::new(&edit.insert).line_col(rel_offset);
-    let edit_line_col = pre_edit_index.line_col(edit.delete.start());
-    if in_edit_line_col.line == 0 {
-        LineCol {
-            line: edit_line_col.line,
-            col_utf16: edit_line_col.col_utf16 + in_edit_line_col.col_utf16,
-        }
-    } else {
-        LineCol {
-            line: edit_line_col.line + in_edit_line_col.line,
-            col_utf16: in_edit_line_col.col_utf16,
-        }
-    }
-}
-
 impl TryConvWith for SourceFileEdit {
     type Ctx = ServerWorld;
     type Output = TextDocumentEdit;
diff --git a/crates/ra_text_edit/Cargo.toml b/crates/ra_text_edit/Cargo.toml
index 3c4157a4e..e0db49688 100644
--- a/crates/ra_text_edit/Cargo.toml
+++ b/crates/ra_text_edit/Cargo.toml
@@ -7,6 +7,7 @@ publish = false
 
 [dependencies]
 text_unit = "0.1.5"
+proptest = "0.8.7"
 
 [dev-dependencies]
 test_utils = { path = "../test_utils" }
diff --git a/crates/ra_text_edit/src/lib.rs b/crates/ra_text_edit/src/lib.rs
index 13e20f6fb..8acf10448 100644
--- a/crates/ra_text_edit/src/lib.rs
+++ b/crates/ra_text_edit/src/lib.rs
@@ -1,12 +1,15 @@
 mod text_edit;
 pub mod text_utils;
+pub mod test_utils;
 
 pub use crate::text_edit::{TextEdit, TextEditBuilder};
 
 use text_unit::{TextRange, TextUnit};
 
+/// Must not overlap with other `AtomTextEdit`s
 #[derive(Debug, Clone)]
 pub struct AtomTextEdit {
+    /// Refers to offsets in the original text
     pub delete: TextRange,
     pub insert: String,
 }
diff --git a/crates/ra_text_edit/src/test_utils.rs b/crates/ra_text_edit/src/test_utils.rs
new file mode 100644
index 000000000..745f21c93
--- /dev/null
+++ b/crates/ra_text_edit/src/test_utils.rs
@@ -0,0 +1,85 @@
+use proptest::prelude::*;
+use text_unit::{TextUnit, TextRange};
+use crate::{AtomTextEdit, TextEdit};
+
+pub fn arb_text() -> proptest::string::RegexGeneratorStrategy<String> {
+    // generate multiple newlines
+    proptest::string::string_regex("(.*\n?)*").unwrap()
+}
+
+fn text_offsets(text: &str) -> Vec<TextUnit> {
+    text.char_indices()
+        .map(|(i, _)| TextUnit::from_usize(i))
+        .collect()
+}
+
+pub fn arb_offset(text: &str) -> BoxedStrategy<TextUnit> {
+    let offsets = text_offsets(text);
+    // this is necessary to avoid "Uniform::new called with `low >= high`" panic
+    if offsets.is_empty() {
+        Just(TextUnit::from(0)).boxed()
+    } else {
+        prop::sample::select(offsets).boxed()
+    }
+}
+
+pub fn arb_text_edit(text: &str) -> BoxedStrategy<TextEdit> {
+    if text.is_empty() {
+        // only valid edits
+        return Just(vec![])
+            .boxed()
+            .prop_union(
+                arb_text()
+                    .prop_map(|text| vec![AtomTextEdit::insert(TextUnit::from(0), text)])
+                    .boxed(),
+            )
+            .prop_map(TextEdit::from_atoms)
+            .boxed();
+    }
+
+    let offsets = text_offsets(text);
+    let max_cuts = 7.min(offsets.len());
+
+    proptest::sample::subsequence(offsets, 0..max_cuts)
+        .prop_flat_map(|cuts| {
+            let strategies: Vec<_> = cuts
+                .chunks(2)
+                .map(|chunk| match chunk {
+                    &[from, to] => {
+                        let range = TextRange::from_to(from, to);
+                        Just(AtomTextEdit::delete(range))
+                            .boxed()
+                            .prop_union(
+                                arb_text()
+                                    .prop_map(move |text| AtomTextEdit::replace(range, text))
+                                    .boxed(),
+                            )
+                            .boxed()
+                    }
+                    &[x] => arb_text()
+                        .prop_map(move |text| AtomTextEdit::insert(x, text))
+                        .boxed(),
+                    _ => unreachable!(),
+                })
+                .collect();
+            strategies
+        })
+        .prop_map(TextEdit::from_atoms)
+        .boxed()
+}
+
+#[derive(Debug, Clone)]
+pub struct ArbTextWithEdit {
+    pub text: String,
+    pub edit: TextEdit,
+}
+
+pub fn arb_text_with_edit() -> BoxedStrategy<ArbTextWithEdit> {
+    let text = arb_text();
+    text.prop_flat_map(|s| {
+        let edit = arb_text_edit(&s);
+        (Just(s), edit)
+    })
+    .prop_map(|(text, edit)| ArbTextWithEdit { text, edit })
+    .boxed()
+}
diff --git a/crates/ra_text_edit/src/text_edit.rs b/crates/ra_text_edit/src/text_edit.rs
index 392968d63..0881f3e1c 100644
--- a/crates/ra_text_edit/src/text_edit.rs
+++ b/crates/ra_text_edit/src/text_edit.rs
@@ -26,12 +26,7 @@ impl TextEditBuilder {
         self.atoms.push(AtomTextEdit::insert(offset, text))
     }
     pub fn finish(self) -> TextEdit {
-        let mut atoms = self.atoms;
-        atoms.sort_by_key(|a| (a.delete.start(), a.delete.end()));
-        for (a1, a2) in atoms.iter().zip(atoms.iter().skip(1)) {
-            assert!(a1.delete.end() <= a2.delete.start())
-        }
-        TextEdit { atoms }
+        TextEdit::from_atoms(self.atoms)
     }
     pub fn invalidates_offset(&self, offset: TextUnit) -> bool {
         self.atoms
@@ -41,6 +36,14 @@ impl TextEditBuilder {
 }
 
 impl TextEdit {
+    pub(crate) fn from_atoms(mut atoms: Vec<AtomTextEdit>) -> TextEdit {
+        atoms.sort_by_key(|a| (a.delete.start(), a.delete.end()));
+        for (a1, a2) in atoms.iter().zip(atoms.iter().skip(1)) {
+            assert!(a1.delete.end() <= a2.delete.start())
+        }
+        TextEdit { atoms }
+    }
+
     pub fn as_atoms(&self) -> &[AtomTextEdit] {
         &self.atoms
     }