Merge #5503

5503: Replace superslice with API on path to stabilization r=matklad a=matklad



bors r+
🤖

Co-authored-by: Aleksey Kladov <[email protected]>

3 files changed, 36 insertions, 5 deletions

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::*;