4 files changed, 184 insertions, 0 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 51cf1825d..3a3793581 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -74,6 +74,19 @@ dependencies = [
 ]
 
 [[package]]
+name = "bit-set"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "bit-vec 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "bit-vec"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "bitflags"
 version = "1.0.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -303,6 +316,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "fnv"
+version = "1.0.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "fst"
 version = "0.3.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -626,6 +644,28 @@ dependencies = [
 ]
 
 [[package]]
+name = "proptest"
+version = "0.8.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "bit-set 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "byteorder 1.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
+ "lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "quick-error 1.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "regex-syntax 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rusty-fork 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "tempfile 3.0.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "quick-error"
+version = "1.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "quote"
 version = "0.6.10"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -763,6 +803,7 @@ dependencies = [
 name = "ra_text_edit"
 version = "0.1.0"
 dependencies = [
+ "proptest 0.8.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "test_utils 0.1.0",
  "text_unit 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
@@ -984,6 +1025,17 @@ dependencies = [
 ]
 
 [[package]]
+name = "rusty-fork"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "fnv 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "quick-error 1.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "tempfile 3.0.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "wait-timeout 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "ryu"
 version = "0.2.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1413,6 +1465,14 @@ version = "1.0.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "wait-timeout"
+version = "0.1.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "walkdir"
 version = "2.2.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1459,6 +1519,8 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum backtrace 0.3.13 (registry+https://github.com/rust-lang/crates.io-index)" = "b5b493b66e03090ebc4343eb02f94ff944e0cbc9ac6571491d170ba026741eb5"
 "checksum backtrace-sys 0.1.26 (registry+https://github.com/rust-lang/crates.io-index)" = "3fcce89e5ad5c8949caa9434501f7b55415b3e7ad5270cb88c75a8d35e8f1279"
 "checksum base64 0.9.3 (registry+https://github.com/rust-lang/crates.io-index)" = "489d6c0ed21b11d038c31b6ceccca973e65d73ba3bd8ecb9a2babf5546164643"
+"checksum bit-set 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "6f1efcc46c18245a69c38fcc5cc650f16d3a59d034f3106e9ed63748f695730a"
+"checksum bit-vec 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "4440d5cb623bb7390ae27fec0bb6c61111969860f8e3ae198bfa0663645e67cf"
 "checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
 "checksum block-buffer 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a076c298b9ecdb530ed9d967e74a6027d6a7478924520acddcddc24c1c8ab3ab"
 "checksum byte-tools 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "560c32574a12a89ecd91f5e742165893f86e3ab98d21f8ea548658eb9eef5f40"
@@ -1487,6 +1549,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum failure_derive 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "64c2d913fe8ed3b6c6518eedf4538255b989945c14c2a7d5cbff62a5e2120596"
 "checksum fake-simd 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "e88a8acf291dafb59c2d96e8f59828f3838bb1a70398823ade51a84de6a6deed"
 "checksum flexi_logger 0.10.3 (registry+https://github.com/rust-lang/crates.io-index)" = "4dda06444ccc8b0a6da19d939989b4a4e83f328710ada449eedaed48c8b903cd"
+"checksum fnv 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "2fad85553e09a6f881f739c29f0b00b0f01357c743266d478b68951ce23285f3"
 "checksum fst 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "db72126ca7dff566cdbbdd54af44668c544897d9d3862b198141f176f1238bdf"
 "checksum fuchsia-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2e9763c69ebaae630ba35f74888db465e49e259ba1bc0eda7d06f4a067615d82"
 "checksum fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3dcaa9ae7725d12cdb85b3ad99a434db70b468c09ded17e012d86b5c1010f7a7"
@@ -1527,6 +1590,8 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum pest_generator 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3ebee4e9680be4fd162e6f3394ae4192a6b60b1e4d17d845e631f0c68d1a3386"
 "checksum pest_meta 2.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1f6d5f6f0e6082578c86af197d780dc38328e3f768cec06aac9bc46d714e8221"
 "checksum proc-macro2 0.4.24 (registry+https://github.com/rust-lang/crates.io-index)" = "77619697826f31a02ae974457af0b29b723e5619e113e9397b8b82c6bd253f09"
+"checksum proptest 0.8.7 (registry+https://github.com/rust-lang/crates.io-index)" = "926d0604475349f463fe44130aae73f2294b5309ab2ca0310b998bd334ef191f"
+"checksum quick-error 1.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9274b940887ce9addde99c4eee6b5c44cc494b182b97e73dc8ffdcb3397fd3f0"
 "checksum quote 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)" = "53fa22a1994bd0f9372d7a816207d8a2677ad0325b073f5c5332760f0fb62b5c"
 "checksum rand 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "8356f47b32624fef5b3301c1be97e5944ecdd595409cc5da11d05f211db6cfbd"
 "checksum rand 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)" = "e464cd887e869cddcae8792a4ee31d23c7edd516700695608f5b98c67ee0131c"
@@ -1551,6 +1616,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum rustc-demangle 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "01b90379b8664dd83460d59bdc5dd1fd3172b8913788db483ed1325171eab2f7"
 "checksum rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7540fc8b0c49f096ee9c961cda096467dce8084bec6bdca2fc83895fd9b28cb8"
 "checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a"
+"checksum rusty-fork 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "9591f190d2852720b679c21f66ad929f9f1d7bb09d1193c26167586029d8489c"
 "checksum ryu 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "eb9e9b8cde282a9fe6a42dd4681319bfb63f121b8a8ee9439c6f4107e58a46f7"
 "checksum safemem 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8dca453248a96cb0749e36ccdfe2b0b4e54a61bfef89fb97ec621eb8e0a93dd9"
 "checksum salsa 0.8.0 (git+https://github.com/matklad/salsa?branch=no-upgrade)" = "<none>"
@@ -1602,6 +1668,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum vec_map 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "05c78687fb1a80548ae3250346c3db86a80a7cdd77bda190189f2d0a0987c81a"
 "checksum version_check 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "914b1a6776c4c929a602fafd8bc742e06365d4bcbe48c30f9cca5824f70dc9dd"
 "checksum void 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "6a02e4885ed3bc0f2de90ea6dd45ebcbb66dacffe03547fadbb0eeae2770887d"
+"checksum wait-timeout 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "b9f3bf741a801531993db6478b95682117471f76916f5e690dd8d45395b09349"
 "checksum walkdir 2.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "9d9d7ed3431229a144296213105a390676cc49c9b6a72bd19f3176c98e129fa1"
 "checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0"
 "checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
diff --git a/crates/ra_text_edit/Cargo.toml b/crates/ra_text_edit/Cargo.toml
index 3c4157a4e..67dfd0924 100644
--- a/crates/ra_text_edit/Cargo.toml
+++ b/crates/ra_text_edit/Cargo.toml
@@ -10,3 +10,4 @@ text_unit = "0.1.5"
 
 [dev-dependencies]
 test_utils = { path = "../test_utils" }
+proptest = "0.8.7"
diff --git a/crates/ra_text_edit/src/lib.rs b/crates/ra_text_edit/src/lib.rs
index 13e20f6fb..0a407795e 100644
--- a/crates/ra_text_edit/src/lib.rs
+++ b/crates/ra_text_edit/src/lib.rs
@@ -1,5 +1,7 @@
 mod text_edit;
 pub mod text_utils;
+#[cfg(test)]
+pub mod test_utils;
 
 pub use crate::text_edit::{TextEdit, TextEditBuilder};
 
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..92b79ab59
--- /dev/null
+++ b/crates/ra_text_edit/src/test_utils.rs
@@ -0,0 +1,114 @@
+use proptest::{prelude::*, proptest, proptest_helper};
+use text_unit::{TextUnit, TextRange};
+use crate::AtomTextEdit;
+
+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_edits(text: &str) -> BoxedStrategy<Vec<AtomTextEdit>> {
+    let offsets = text_offsets(text);
+    let offsets_len = offsets.len();
+
+    if offsets_len == 0 {
+        return proptest::bool::ANY
+            .prop_flat_map(|b| {
+                // only valid edits
+                if b {
+                    arb_text()
+                        .prop_map(|text| vec![AtomTextEdit::insert(TextUnit::from(0), text)])
+                        .boxed()
+                } else {
+                    Just(vec![]).boxed()
+                }
+            })
+            .boxed();
+    }
+
+    proptest::sample::subsequence(offsets, 0..offsets_len)
+        .prop_flat_map(|xs| {
+            let strategies: Vec<_> = xs
+                .chunks(2)
+                .map(|chunk| match chunk {
+                    &[from, to] => {
+                        let range = TextRange::from_to(from, to);
+                        (proptest::bool::ANY)
+                            .prop_flat_map(move |b| {
+                                if b {
+                                    Just(AtomTextEdit::delete(range)).boxed()
+                                } else {
+                                    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
+        })
+        .boxed()
+}
+
+fn arb_text_with_edits() -> BoxedStrategy<(String, Vec<AtomTextEdit>)> {
+    let text = arb_text();
+    text.prop_flat_map(|s| {
+        let edits = arb_edits(&s);
+        (Just(s), edits)
+    })
+    .boxed()
+}
+
+fn intersect(r1: TextRange, r2: TextRange) -> Option<TextRange> {
+    let start = r1.start().max(r2.start());
+    let end = r1.end().min(r2.end());
+    if start <= end {
+        Some(TextRange::from_to(start, end))
+    } else {
+        None
+    }
+}
+
+proptest! {
+#[test]
+    fn atom_text_edits_are_valid((text, edits) in arb_text_with_edits()) {
+        proptest_atom_text_edits_are_valid(text, edits)
+    }
+}
+
+fn proptest_atom_text_edits_are_valid(text: String, edits: Vec<AtomTextEdit>) {
+    // slicing doesn't panic
+    for e in &edits {
+        let _ = &text[e.delete];
+    }
+    // ranges do not overlap
+    for (i1, e1) in edits.iter().skip(1).enumerate() {
+        for e2 in &edits[0..i1] {
+            if intersect(e1.delete, e2.delete).is_some() {
+                assert!(false, "Overlapping ranges {} {}", e1.delete, e2.delete);
+            }
+        }
+    }
+}