From 4f7a3fba59269a2b37b78655a10778ba5af796bd Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Thu, 23 Jul 2020 12:59:18 +0200 Subject: Replace superslice with API on path to stabilization --- crates/ra_ide_db/Cargo.toml | 3 ++- crates/ra_ide_db/src/line_index.rs | 8 ++++---- crates/stdx/src/lib.rs | 30 ++++++++++++++++++++++++++++++ 3 files changed, 36 insertions(+), 5 deletions(-) (limited to 'crates') 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 + '_ { - 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(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::*; -- cgit v1.2.3