3 files changed, 544 insertions, 104 deletions

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);
+        }
+    }
+}