diff options
| -rw-r--r-- | Cargo.lock | 8 | ||||
| -rw-r--r-- | crates/ra_ide_db/Cargo.toml | 3 | ||||
| -rw-r--r-- | crates/ra_ide_db/src/line_index.rs | 8 | ||||
| -rw-r--r-- | crates/stdx/src/lib.rs | 30 | ||||
| -rw-r--r-- | xtask/tests/tidy.rs | 1 |
5 files changed, 37 insertions, 13 deletions
diff --git a/Cargo.lock b/Cargo.lock index af706281533..0296988083f 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 bcddad60cfa..2716a38cc99 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 c7c744fce1e..2ab662098a6 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 988853ed2a4..ea0e6b94997 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 ca14e8ac135..adadffc53a9 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 |