aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Cargo.lock8
-rw-r--r--crates/ra_ide_db/Cargo.toml3
-rw-r--r--crates/ra_ide_db/src/line_index.rs8
-rw-r--r--crates/stdx/src/lib.rs30
-rw-r--r--xtask/tests/tidy.rs1
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 = [
1077 "ra_text_edit", 1077 "ra_text_edit",
1078 "rayon", 1078 "rayon",
1079 "rustc-hash", 1079 "rustc-hash",
1080 "superslice", 1080 "stdx",
1081 "test_utils", 1081 "test_utils",
1082] 1082]
1083 1083
@@ -1584,12 +1584,6 @@ name = "stdx"
1584version = "0.1.0" 1584version = "0.1.0"
1585 1585
1586[[package]] 1586[[package]]
1587name = "superslice"
1588version = "1.0.0"
1589source = "registry+https://github.com/rust-lang/crates.io-index"
1590checksum = "ab16ced94dbd8a46c82fd81e3ed9a8727dac2977ea869d217bcc4ea1f122e81f"
1591
1592[[package]]
1593name = "syn" 1587name = "syn"
1594version = "1.0.35" 1588version = "1.0.35"
1595source = "registry+https://github.com/rust-lang/crates.io-index" 1589source = "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"
16rayon = "1.3.0" 16rayon = "1.3.0"
17fst = { version = "0.4", default-features = false } 17fst = { version = "0.4", default-features = false }
18rustc-hash = "1.1.0" 18rustc-hash = "1.1.0"
19superslice = "1.0.0"
20once_cell = "1.3.1" 19once_cell = "1.3.1"
21either = "1.5.3" 20either = "1.5.3"
22 21
22stdx = { path = "../stdx" }
23
23ra_syntax = { path = "../ra_syntax" } 24ra_syntax = { path = "../ra_syntax" }
24ra_text_edit = { path = "../ra_text_edit" } 25ra_text_edit = { path = "../ra_text_edit" }
25ra_db = { path = "../ra_db" } 26ra_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;
4 4
5use ra_syntax::{TextRange, TextSize}; 5use ra_syntax::{TextRange, TextSize};
6use rustc_hash::FxHashMap; 6use rustc_hash::FxHashMap;
7use superslice::Ext; 7use stdx::partition_point;
8 8
9#[derive(Clone, Debug, PartialEq, Eq)] 9#[derive(Clone, Debug, PartialEq, Eq)]
10pub struct LineIndex { 10pub struct LineIndex {
@@ -89,7 +89,7 @@ impl LineIndex {
89 } 89 }
90 90
91 pub fn line_col(&self, offset: TextSize) -> LineCol { 91 pub fn line_col(&self, offset: TextSize) -> LineCol {
92 let line = self.newlines.upper_bound(&offset) - 1; 92 let line = partition_point(&self.newlines, |&it| it <= offset) - 1;
93 let line_start_offset = self.newlines[line]; 93 let line_start_offset = self.newlines[line];
94 let col = offset - line_start_offset; 94 let col = offset - line_start_offset;
95 95
@@ -103,8 +103,8 @@ impl LineIndex {
103 } 103 }
104 104
105 pub fn lines(&self, range: TextRange) -> impl Iterator<Item = TextRange> + '_ { 105 pub fn lines(&self, range: TextRange) -> impl Iterator<Item = TextRange> + '_ {
106 let lo = self.newlines.lower_bound(&range.start()); 106 let lo = partition_point(&self.newlines, |&it| it < range.start());
107 let hi = self.newlines.upper_bound(&range.end()); 107 let hi = partition_point(&self.newlines, |&it| it <= range.end());
108 let all = iter::once(range.start()) 108 let all = iter::once(range.start())
109 .chain(self.newlines[lo..hi].iter().copied()) 109 .chain(self.newlines[lo..hi].iter().copied())
110 .chain(iter::once(range.end())); 110 .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> {
158 } 158 }
159} 159}
160 160
161// https://github.com/rust-lang/rust/issues/73831
162pub fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize
163where
164 P: FnMut(&T) -> bool,
165{
166 let mut left = 0;
167 let mut right = slice.len();
168
169 while left != right {
170 let mid = left + (right - left) / 2;
171 // SAFETY:
172 // When left < right, left <= mid < right.
173 // Therefore left always increases and right always decreases,
174 // and either of them is selected.
175 // In both cases left <= right is satisfied.
176 // Therefore if left < right in a step,
177 // left <= right is satisfied in the next step.
178 // Therefore as long as left != right, 0 <= left < right <= len is satisfied
179 // and if this case 0 <= mid < len is satisfied too.
180 let value = unsafe { slice.get_unchecked(mid) };
181 if pred(value) {
182 left = mid + 1;
183 } else {
184 right = mid;
185 }
186 }
187
188 left
189}
190
161#[cfg(test)] 191#[cfg(test)]
162mod tests { 192mod tests {
163 use super::*; 193 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() {
53fn check_licenses() { 53fn check_licenses() {
54 let expected = " 54 let expected = "
550BSD OR MIT OR Apache-2.0 550BSD OR MIT OR Apache-2.0
56Apache-2.0
57Apache-2.0 OR BSL-1.0 56Apache-2.0 OR BSL-1.0
58Apache-2.0 OR MIT 57Apache-2.0 OR MIT
59Apache-2.0 WITH LLVM-exception OR Apache-2.0 OR MIT 58Apache-2.0 WITH LLVM-exception OR Apache-2.0 OR MIT