5 files changed, 126 insertions, 201 deletions

diff --git a/crates/ra_editor/Cargo.toml b/crates/ra_editor/Cargo.toml
index 1ad99af28..039688d7d 100644
--- a/crates/ra_editor/Cargo.toml
+++ b/crates/ra_editor/Cargo.toml
@@ -18,3 +18,11 @@ proptest = "0.8.7"
 
 [dev-dependencies]
 test_utils = { path = "../test_utils" }
+criterion = "0.2"
+rand = "*"
+rand_xorshift = "*"
+lazy_static = "*"
+
+[[bench]]
+name = "translate_offset_with_edit_benchmark"
+harness = false
\ No newline at end of file
diff --git a/crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs b/crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs
new file mode 100644
index 000000000..b345a91ae
--- /dev/null
+++ b/crates/ra_editor/benches/translate_offset_with_edit_benchmark.rs
@@ -0,0 +1,88 @@
+use criterion::{criterion_group, criterion_main};
+use criterion::Criterion;
+use criterion::Fun;
+use ra_text_edit::AtomTextEdit;
+use ra_text_edit::test_utils::{arb_edits_custom, arb_offset};
+use ra_editor::line_index_utils;
+use ra_editor::LineIndex;
+use ra_syntax::TextUnit;
+use proptest::test_runner;
+use proptest::string::string_regex;
+use proptest::strategy::{Strategy, ValueTree};
+use rand_xorshift::XorShiftRng;
+use rand::SeedableRng;
+use lazy_static::lazy_static;
+
+#[derive(Debug)]
+struct Data {
+    text: String,
+    line_index: LineIndex,
+    edits: Vec<AtomTextEdit>,
+    offset: TextUnit,
+}
+
+fn setup_data() -> Data {
+    let mut runner = test_runner::TestRunner::default();
+    {
+        struct TestRng {
+            rng: XorShiftRng,
+        }
+        // HACK to be able to manually seed the TestRunner
+        let rng: &mut TestRng = unsafe { std::mem::transmute(runner.rng()) };
+        rng.rng = XorShiftRng::seed_from_u64(0);
+    }
+
+    let text = {
+        let arb = string_regex("([a-zA-Z_0-9]{10,50}.{1,5}\n){100,500}").unwrap();
+        let tree = arb.new_tree(&mut runner).unwrap();
+        tree.current()
+    };
+
+    let edits = {
+        let arb = arb_edits_custom(&text, 99, 100);
+        let tree = arb.new_tree(&mut runner).unwrap();
+        tree.current()
+    };
+
+    let offset = {
+        let arb = arb_offset(&text);
+        let tree = arb.new_tree(&mut runner).unwrap();
+        tree.current()
+    };
+
+    let line_index = LineIndex::new(&text);
+
+    Data {
+        text,
+        line_index,
+        edits,
+        offset,
+    }
+}
+
+lazy_static! {
+    static ref DATA: Data = setup_data();
+}
+
+fn compare_translates(c: &mut Criterion) {
+    let f1 = Fun::new("translate_after_edit", |b, _| {
+        b.iter(|| {
+            let d = &*DATA;
+            line_index_utils::translate_after_edit(&d.text, d.offset, d.edits.clone());
+        })
+    });
+
+    let f2 = Fun::new("count_newlines", |b, _| {
+        b.iter(|| {
+            let d = &*DATA;
+            line_index_utils::count_newlines(d.offset, &d.line_index, &d.edits);
+        })
+    });
+
+    let functions = vec![f1, f2];
+
+    c.bench_functions("translate", functions, ());
+}
+
+criterion_group!(benches, compare_translates);
+criterion_main!(benches);
diff --git a/crates/ra_editor/src/lib.rs b/crates/ra_editor/src/lib.rs
index 619497f0b..7145c6cfb 100644
--- a/crates/ra_editor/src/lib.rs
+++ b/crates/ra_editor/src/lib.rs
@@ -2,7 +2,8 @@ mod code_actions;
 mod extend_selection;
 mod folding_ranges;
 mod line_index;
-mod line_index_utils;
+// public for benchmarkig
+pub mod line_index_utils;
 mod symbols;
 #[cfg(test)]
 mod test_utils;
@@ -13,7 +14,6 @@ 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_utils.rs b/crates/ra_editor/src/line_index_utils.rs
index 5ce2446c1..e62c5089d 100644
--- a/crates/ra_editor/src/line_index_utils.rs
+++ b/crates/ra_editor/src/line_index_utils.rs
@@ -25,136 +25,6 @@ impl<'a> Iterator for OffsetNewlineIter<'a> {
 }
 
 #[derive(Debug)]
-struct AltEdit<'a> {
-    insert_newlines: OffsetNewlineIter<'a>,
-    delete: TextRange,
-    diff: i64,
-}
-
-fn translate_range_by(range: TextRange, diff: i64) -> TextRange {
-    if diff == 0 {
-        range
-    } else {
-        let start = translate_by(range.start(), diff);
-        let end = translate_by(range.end(), diff);
-        TextRange::from_to(start, end)
-    }
-}
-
-fn translate_by(x: TextUnit, diff: i64) -> TextUnit {
-    if diff == 0 {
-        x
-    } else {
-        TextUnit::from((x.to_usize() as i64 + diff) as u32)
-    }
-}
-
-fn to_alt_edits<'a>(offset: TextUnit, edits: &'a [AtomTextEdit]) -> Vec<AltEdit<'a>> {
-    let mut xs: Vec<AltEdit<'a>> = Vec::with_capacity(edits.len());
-    // collect and sort edits
-    for edit in edits {
-        // TODO discard after translating?
-        // if edit.delete.start() >= offset {
-        //     continue;
-        // }
-        let insert_index = xs.upper_bound_by_key(&edit.delete.start(), |x| x.delete.start());
-        let diff = edit.insert.len() as i64 - edit.delete.len().to_usize() as i64;
-        xs.insert(
-            insert_index,
-            AltEdit {
-                insert_newlines: OffsetNewlineIter {
-                    offset: edit.delete.start(),
-                    text: &edit.insert,
-                },
-                delete: edit.delete,
-                diff: diff,
-            },
-        );
-    }
-    // translate edits by previous edits
-    for i in 1..xs.len() {
-        let (x, prevs) = xs[0..=i].split_last_mut().unwrap();
-        for prev in prevs {
-            x.delete = translate_range_by(x.delete, prev.diff);
-            x.insert_newlines.offset = translate_by(x.insert_newlines.offset, prev.diff);
-        }
-    }
-    xs
-}
-
-#[derive(Debug)]
-enum NextNewline {
-    Use,
-    Discard,
-    Replace(TextUnit),
-    New(TextUnit),
-}
-
-fn next_newline(candidate: Option<TextUnit>, edits: &mut [AltEdit]) -> NextNewline {
-    let mut candidate = match candidate {
-        None => {
-            for edit in edits {
-                if let Some(inserted) = edit.insert_newlines.next() {
-                    return NextNewline::New(inserted);
-                }
-            }
-            return NextNewline::Use; // END
-        }
-        Some(x) => x,
-    };
-
-    for edit in edits {
-        if candidate <= edit.delete.start() {
-            return NextNewline::Replace(candidate);
-        } else if candidate <= edit.delete.end() {
-            return match edit.insert_newlines.next() {
-                Some(x) => NextNewline::Replace(x),
-                None => NextNewline::Discard,
-            };
-        } else {
-            if let Some(inserted) = edit.insert_newlines.next() {
-                return NextNewline::New(inserted);
-            }
-            candidate = translate_by(candidate, edit.diff);
-        }
-    }
-    return NextNewline::Replace(candidate);
-}
-
-pub fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 {
-    let mut edits = to_alt_edits(offset, edits);
-    let mut orig_newlines = line_index.newlines().iter().map(|x| *x).peekable();
-
-    let mut count = 0;
-
-    loop {
-        let res = next_newline(orig_newlines.peek().map(|x| *x), &mut edits);
-        let next = match res {
-            NextNewline::Use => orig_newlines.next(),
-            NextNewline::Discard => {
-                orig_newlines.next();
-                continue;
-            }
-            NextNewline::Replace(new) => {
-                orig_newlines.next();
-                Some(new)
-            }
-            NextNewline::New(new) => Some(new),
-        };
-        match next {
-            Some(n) if n <= offset => {
-                count += 1;
-            }
-            _ => {
-                break;
-            }
-        }
-    }
-
-    count
-}
-
-#[derive(Debug)]
 enum NextNewlines<'a> {
     Use,
     ReplaceMany(OffsetNewlineIter<'a>),
@@ -188,7 +58,7 @@ impl<'a, 'b> Edits<'a, 'b> {
         self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff);
         match self.edits.split_first() {
             Some((next, rest)) => {
-                let delete = translate_range_by(next.delete, self.acc_diff);
+                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,
@@ -241,9 +111,27 @@ impl<'a, 'b> Edits<'a, 'b> {
         };
         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)
+        }
+    }
 }
 
-pub fn count_newlines_alt(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 {
+pub fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 {
     let mut sorted_edits: Vec<&AtomTextEdit> = Vec::with_capacity(edits.len());
     for edit in edits {
         let insert_index =
@@ -257,7 +145,7 @@ pub fn count_newlines_alt(offset: TextUnit, line_index: &LineIndex, edits: &[Ato
 
     for &orig_newline in line_index.newlines() {
         loop {
-            let translated_newline = translate_by(orig_newline, state.acc_diff);
+            let translated_newline = state.translate(orig_newline);
             match state.next_newlines(translated_newline) {
                 NextNewlines::Use => {
                     if offset < translated_newline {
@@ -369,69 +257,5 @@ mod test {
             let actual_lines = count_newlines(x.offset, &line_index, &x.edits);
             assert_eq!(actual_lines, expected.line);
         }
-
-        #[test]
-        fn test_translate_offset_with_edit_alt(x in arb_text_with_offset_and_edits()) {
-            let line_index = LineIndex::new(&x.text);
-            let expected = translate_after_edit(&x.text, x.offset, x.edits.clone());
-            let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits);
-            assert_eq!(actual_lines, expected.line);
-        }
-    }
-
-    #[test]
-    fn test_translate_offset_with_edit_alt_1() {
-        let x = ArbTextWithOffsetAndEdits {
-            text: String::from("aA\n"),
-            offset: 2.into(),
-            edits: vec![AtomTextEdit::delete(TextRange::from_to(1.into(), 2.into()))],
-        };
-        let line_index = LineIndex::new(&x.text);
-        let expected = translate_after_edit(&x.text, x.offset, x.edits.clone());
-        let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits);
-        assert_eq!(actual_lines, expected.line);
-    }
-
-    #[test]
-    fn test_translate_offset_with_edit_alt_2() {
-        let x = ArbTextWithOffsetAndEdits {
-            text: String::from("\nqꀸ#"),
-            offset: 5.into(),
-            edits: vec![AtomTextEdit::insert(1.into(), "\n".into())],
-        };
-        let line_index = LineIndex::new(&x.text);
-        let expected = translate_after_edit(&x.text, x.offset, x.edits.clone());
-        let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits);
-        assert_eq!(actual_lines, expected.line);
-    }
-
-    #[test]
-    fn test_translate_offset_with_edit_alt_3() {
-        let x = ArbTextWithOffsetAndEdits {
-            text: String::from("\n\n\n"),
-            offset: 0.into(),
-            edits: vec![AtomTextEdit::delete(TextRange::from_to(0.into(), 2.into()))],
-        };
-        let line_index = LineIndex::new(&x.text);
-        let expected = translate_after_edit(&x.text, x.offset, x.edits.clone());
-        let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits);
-        assert_eq!(actual_lines, expected.line);
     }
-
-    #[test]
-    fn test_translate_offset_with_edit_alt_4() {
-        let x = ArbTextWithOffsetAndEdits {
-            text: String::from("☻54翑\"A"),
-            offset: 5.into(),
-            edits: vec![
-                AtomTextEdit::delete(TextRange::from_to(0.into(), 8.into())),
-                AtomTextEdit::insert(9.into(), String::from("\n")),
-            ],
-        };
-        let line_index = LineIndex::new(&x.text);
-        let expected = translate_after_edit(&x.text, x.offset, x.edits.clone());
-        let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits);
-        assert_eq!(actual_lines, expected.line);
-    }
-
 }
diff --git a/crates/ra_text_edit/src/test_utils.rs b/crates/ra_text_edit/src/test_utils.rs
index 4a0ebc08e..f150288f6 100644
--- a/crates/ra_text_edit/src/test_utils.rs
+++ b/crates/ra_text_edit/src/test_utils.rs
@@ -24,6 +24,10 @@ pub fn arb_offset(text: &str) -> BoxedStrategy<TextUnit> {
 }
 
 pub fn arb_edits(text: &str) -> BoxedStrategy<Vec<AtomTextEdit>> {
+    arb_edits_custom(&text, 0, 7)
+}
+
+pub fn arb_edits_custom(text: &str, min: usize, max: usize) -> BoxedStrategy<Vec<AtomTextEdit>> {
     if text.is_empty() {
         // only valid edits
         return Just(vec![])
@@ -37,9 +41,10 @@ pub fn arb_edits(text: &str) -> BoxedStrategy<Vec<AtomTextEdit>> {
     }
 
     let offsets = text_offsets(text);
-    let max_cuts = offsets.len().min(7);
+    let max_cuts = max.min(offsets.len());
+    let min_cuts = min.min(offsets.len() - 1);
 
-    proptest::sample::subsequence(offsets, 0..max_cuts)
+    proptest::sample::subsequence(offsets, min_cuts..max_cuts)
         .prop_flat_map(|cuts| {
             let strategies: Vec<_> = cuts
                 .chunks(2)