5 files changed, 37 insertions, 13 deletions

diff --git a/Cargo.lock b/Cargo.lock
index af7062815..029698808 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1077,7 +1077,7 @@ dependencies = [
  "ra_text_edit",
  "rayon",
  "rustc-hash",
- "superslice",
+ "stdx",
  "test_utils",
 ]
 
@@ -1584,12 +1584,6 @@ name = "stdx"
 version = "0.1.0"
 
 [[package]]
-name = "superslice"
-version = "1.0.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ab16ced94dbd8a46c82fd81e3ed9a8727dac2977ea869d217bcc4ea1f122e81f"
-
-[[package]]
 name = "syn"
 version = "1.0.35"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/crates/ra_ide_db/Cargo.toml b/crates/ra_ide_db/Cargo.toml
index bcddad60c..2716a38cc 100644
--- a/crates/ra_ide_db/Cargo.toml
+++ b/crates/ra_ide_db/Cargo.toml
@@ -16,10 +16,11 @@ log = "0.4.8"
 rayon = "1.3.0"
 fst = { version = "0.4", default-features = false }
 rustc-hash = "1.1.0"
-superslice = "1.0.0"
 once_cell = "1.3.1"
 either = "1.5.3"
 
+stdx = { path = "../stdx" }
+
 ra_syntax = { path = "../ra_syntax" }
 ra_text_edit = { path = "../ra_text_edit" }
 ra_db = { path = "../ra_db" }
diff --git a/crates/ra_ide_db/src/line_index.rs b/crates/ra_ide_db/src/line_index.rs
index c7c744fce..2ab662098 100644
--- a/crates/ra_ide_db/src/line_index.rs
+++ b/crates/ra_ide_db/src/line_index.rs
@@ -4,7 +4,7 @@ use std::iter;
 
 use ra_syntax::{TextRange, TextSize};
 use rustc_hash::FxHashMap;
-use superslice::Ext;
+use stdx::partition_point;
 
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub struct LineIndex {
@@ -89,7 +89,7 @@ impl LineIndex {
     }
 
     pub fn line_col(&self, offset: TextSize) -> LineCol {
-        let line = self.newlines.upper_bound(&offset) - 1;
+        let line = partition_point(&self.newlines, |&it| it <= offset) - 1;
         let line_start_offset = self.newlines[line];
         let col = offset - line_start_offset;
 
@@ -103,8 +103,8 @@ impl LineIndex {
     }
 
     pub fn lines(&self, range: TextRange) -> impl Iterator<Item = TextRange> + '_ {
-        let lo = self.newlines.lower_bound(&range.start());
-        let hi = self.newlines.upper_bound(&range.end());
+        let lo = partition_point(&self.newlines, |&it| it < range.start());
+        let hi = partition_point(&self.newlines, |&it| it <= range.end());
         let all = iter::once(range.start())
             .chain(self.newlines[lo..hi].iter().copied())
             .chain(iter::once(range.end()));
diff --git a/crates/stdx/src/lib.rs b/crates/stdx/src/lib.rs
index 988853ed2..ea0e6b949 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -158,6 +158,36 @@ impl<'a> Iterator for LinesWithEnds<'a> {
     }
 }
 
+// https://github.com/rust-lang/rust/issues/73831
+pub fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize
+where
+    P: FnMut(&T) -> bool,
+{
+    let mut left = 0;
+    let mut right = slice.len();
+
+    while left != right {
+        let mid = left + (right - left) / 2;
+        // SAFETY:
+        // When left < right, left <= mid < right.
+        // Therefore left always increases and right always decreases,
+        // and either of them is selected.
+        // In both cases left <= right is satisfied.
+        // Therefore if left < right in a step,
+        // left <= right is satisfied in the next step.
+        // Therefore as long as left != right, 0 <= left < right <= len is satisfied
+        // and if this case 0 <= mid < len is satisfied too.
+        let value = unsafe { slice.get_unchecked(mid) };
+        if pred(value) {
+            left = mid + 1;
+        } else {
+            right = mid;
+        }
+    }
+
+    left
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
diff --git a/xtask/tests/tidy.rs b/xtask/tests/tidy.rs
index ca14e8ac1..adadffc53 100644
--- a/xtask/tests/tidy.rs
+++ b/xtask/tests/tidy.rs
@@ -53,7 +53,6 @@ fn rust_files_are_tidy() {
 fn check_licenses() {
     let expected = "
 0BSD OR MIT OR Apache-2.0
-Apache-2.0
 Apache-2.0 OR BSL-1.0
 Apache-2.0 OR MIT
 Apache-2.0 WITH LLVM-exception OR Apache-2.0 OR MIT