aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_ide_api
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_ide_api')
-rw-r--r--crates/ra_ide_api/Cargo.toml2
-rw-r--r--crates/ra_ide_api/src/lib.rs5
-rw-r--r--crates/ra_ide_api/src/line_index.rs280
-rw-r--r--crates/ra_ide_api/src/line_index_utils.rs330
4 files changed, 616 insertions, 1 deletions
diff --git a/crates/ra_ide_api/Cargo.toml b/crates/ra_ide_api/Cargo.toml
index 40b7a8d0a..ac8c8057b 100644
--- a/crates/ra_ide_api/Cargo.toml
+++ b/crates/ra_ide_api/Cargo.toml
@@ -14,6 +14,7 @@ fst = "0.3.1"
14rustc-hash = "1.0" 14rustc-hash = "1.0"
15parking_lot = "0.7.0" 15parking_lot = "0.7.0"
16unicase = "2.2.0" 16unicase = "2.2.0"
17superslice = "1.0.0"
17 18
18jemallocator = { version = "0.1.9", optional = true } 19jemallocator = { version = "0.1.9", optional = true }
19jemalloc-ctl = { version = "0.2.0", optional = true } 20jemalloc-ctl = { version = "0.2.0", optional = true }
@@ -28,6 +29,7 @@ ra_assists = { path = "../ra_assists" }
28 29
29[dev-dependencies] 30[dev-dependencies]
30insta = "0.7.0" 31insta = "0.7.0"
32proptest = "0.9.0"
31 33
32[features] 34[features]
33jemalloc = [ "jemallocator", "jemalloc-ctl" ] 35jemalloc = [ "jemallocator", "jemalloc-ctl" ]
diff --git a/crates/ra_ide_api/src/lib.rs b/crates/ra_ide_api/src/lib.rs
index 81ca57035..35f38fbb7 100644
--- a/crates/ra_ide_api/src/lib.rs
+++ b/crates/ra_ide_api/src/lib.rs
@@ -33,6 +33,8 @@ mod impls;
33mod assists; 33mod assists;
34mod diagnostics; 34mod diagnostics;
35mod syntax_tree; 35mod syntax_tree;
36mod line_index;
37mod line_index_utils;
36 38
37#[cfg(test)] 39#[cfg(test)]
38mod marks; 40mod marks;
@@ -60,10 +62,11 @@ pub use crate::{
60 references::ReferenceSearchResult, 62 references::ReferenceSearchResult,
61 assists::{Assist, AssistId}, 63 assists::{Assist, AssistId},
62 hover::{HoverResult}, 64 hover::{HoverResult},
65 line_index::{LineIndex, LineCol},
66 line_index_utils::translate_offset_with_edit,
63}; 67};
64pub use ra_ide_api_light::{ 68pub use ra_ide_api_light::{
65 Fold, FoldKind, HighlightedRange, Severity, StructureNode, LocalEdit, 69 Fold, FoldKind, HighlightedRange, Severity, StructureNode, LocalEdit,
66 LineIndex, LineCol, translate_offset_with_edit,
67}; 70};
68pub use ra_db::{ 71pub use ra_db::{
69 Canceled, CrateGraph, CrateId, FileId, FilePosition, FileRange, SourceRootId, 72 Canceled, CrateGraph, CrateId, FileId, FilePosition, FileRange, SourceRootId,
diff --git a/crates/ra_ide_api/src/line_index.rs b/crates/ra_ide_api/src/line_index.rs
new file mode 100644
index 000000000..bf004c33a
--- /dev/null
+++ b/crates/ra_ide_api/src/line_index.rs
@@ -0,0 +1,280 @@
1use crate::TextUnit;
2use rustc_hash::FxHashMap;
3use superslice::Ext;
4
5#[derive(Clone, Debug, PartialEq, Eq)]
6pub struct LineIndex {
7 pub(crate) newlines: Vec<TextUnit>,
8 pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
9}
10
11#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
12pub struct LineCol {
13 pub line: u32,
14 pub col_utf16: u32,
15}
16
17#[derive(Clone, Debug, Hash, PartialEq, Eq)]
18pub(crate) struct Utf16Char {
19 pub(crate) start: TextUnit,
20 pub(crate) end: TextUnit,
21}
22
23impl Utf16Char {
24 fn len(&self) -> TextUnit {
25 self.end - self.start
26 }
27}
28
29impl LineIndex {
30 pub fn new(text: &str) -> LineIndex {
31 let mut utf16_lines = FxHashMap::default();
32 let mut utf16_chars = Vec::new();
33
34 let mut newlines = vec![0.into()];
35 let mut curr_row = 0.into();
36 let mut curr_col = 0.into();
37 let mut line = 0;
38 for c in text.chars() {
39 curr_row += TextUnit::of_char(c);
40 if c == '\n' {
41 newlines.push(curr_row);
42
43 // Save any utf-16 characters seen in the previous line
44 if utf16_chars.len() > 0 {
45 utf16_lines.insert(line, utf16_chars);
46 utf16_chars = Vec::new();
47 }
48
49 // Prepare for processing the next line
50 curr_col = 0.into();
51 line += 1;
52 continue;
53 }
54
55 let char_len = TextUnit::of_char(c);
56 if char_len.to_usize() > 1 {
57 utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len });
58 }
59
60 curr_col += char_len;
61 }
62
63 // Save any utf-16 characters seen in the last line
64 if utf16_chars.len() > 0 {
65 utf16_lines.insert(line, utf16_chars);
66 }
67
68 LineIndex { newlines, utf16_lines }
69 }
70
71 pub fn line_col(&self, offset: TextUnit) -> LineCol {
72 let line = self.newlines.upper_bound(&offset) - 1;
73 let line_start_offset = self.newlines[line];
74 let col = offset - line_start_offset;
75
76 LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 }
77 }
78
79 pub fn offset(&self, line_col: LineCol) -> TextUnit {
80 //TODO: return Result
81 let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16);
82 self.newlines[line_col.line as usize] + col
83 }
84
85 fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize {
86 if let Some(utf16_chars) = self.utf16_lines.get(&line) {
87 let mut correction = TextUnit::from_usize(0);
88 for c in utf16_chars {
89 if col >= c.end {
90 correction += c.len() - TextUnit::from_usize(1);
91 } else {
92 // From here on, all utf16 characters come *after* the character we are mapping,
93 // so we don't need to take them into account
94 break;
95 }
96 }
97
98 col -= correction;
99 }
100
101 col.to_usize()
102 }
103
104 fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit {
105 let mut col: TextUnit = col.into();
106 if let Some(utf16_chars) = self.utf16_lines.get(&line) {
107 for c in utf16_chars {
108 if col >= c.start {
109 col += c.len() - TextUnit::from_usize(1);
110 } else {
111 // From here on, all utf16 characters come *after* the character we are mapping,
112 // so we don't need to take them into account
113 break;
114 }
115 }
116 }
117
118 col
119 }
120}
121
122#[cfg(test)]
123/// Simple reference implementation to use in proptests
124pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
125 let mut res = LineCol { line: 0, col_utf16: 0 };
126 for (i, c) in text.char_indices() {
127 if i + c.len_utf8() > offset.to_usize() {
128 // if it's an invalid offset, inside a multibyte char
129 // return as if it was at the start of the char
130 break;
131 }
132 if c == '\n' {
133 res.line += 1;
134 res.col_utf16 = 0;
135 } else {
136 res.col_utf16 += 1;
137 }
138 }
139 res
140}
141
142#[cfg(test)]
143mod test_line_index {
144 use super::*;
145 use proptest::{prelude::*, proptest};
146 use ra_text_edit::test_utils::{arb_text, arb_offset};
147
148 #[test]
149 fn test_line_index() {
150 let text = "hello\nworld";
151 let index = LineIndex::new(text);
152 assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
153 assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 });
154 assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 });
155 assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 });
156 assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 });
157 assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 });
158 assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 });
159 assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 });
160 assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 });
161
162 let text = "\nhello\nworld";
163 let index = LineIndex::new(text);
164 assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
165 assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 });
166 assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 });
167 assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 });
168 assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 });
169 }
170
171 fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> {
172 arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed()
173 }
174
175 fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
176 let mut res = LineCol { line: 0, col_utf16: 0 };
177 for (i, c) in text.char_indices() {
178 if i + c.len_utf8() > offset.to_usize() {
179 // if it's an invalid offset, inside a multibyte char
180 // return as if it was at the start of the char
181 break;
182 }
183 if c == '\n' {
184 res.line += 1;
185 res.col_utf16 = 0;
186 } else {
187 res.col_utf16 += 1;
188 }
189 }
190 res
191 }
192
193 proptest! {
194 #[test]
195 fn test_line_index_proptest((offset, text) in arb_text_with_offset()) {
196 let expected = to_line_col(&text, offset);
197 let line_index = LineIndex::new(&text);
198 let actual = line_index.line_col(offset);
199
200 assert_eq!(actual, expected);
201 }
202 }
203}
204
205#[cfg(test)]
206mod test_utf8_utf16_conv {
207 use super::*;
208
209 #[test]
210 fn test_char_len() {
211 assert_eq!('メ'.len_utf8(), 3);
212 assert_eq!('メ'.len_utf16(), 1);
213 }
214
215 #[test]
216 fn test_empty_index() {
217 let col_index = LineIndex::new(
218 "
219const C: char = 'x';
220",
221 );
222 assert_eq!(col_index.utf16_lines.len(), 0);
223 }
224
225 #[test]
226 fn test_single_char() {
227 let col_index = LineIndex::new(
228 "
229const C: char = 'メ';
230",
231 );
232
233 assert_eq!(col_index.utf16_lines.len(), 1);
234 assert_eq!(col_index.utf16_lines[&1].len(), 1);
235 assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
236
237 // UTF-8 to UTF-16, no changes
238 assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
239
240 // UTF-8 to UTF-16
241 assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20);
242
243 // UTF-16 to UTF-8, no changes
244 assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15));
245
246 // UTF-16 to UTF-8
247 assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21));
248 }
249
250 #[test]
251 fn test_string() {
252 let col_index = LineIndex::new(
253 "
254const C: char = \"メ メ\";
255",
256 );
257
258 assert_eq!(col_index.utf16_lines.len(), 1);
259 assert_eq!(col_index.utf16_lines[&1].len(), 2);
260 assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
261 assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() });
262
263 // UTF-8 to UTF-16
264 assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
265
266 assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19);
267 assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21);
268
269 assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15);
270
271 // UTF-16 to UTF-8
272 assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15));
273
274 assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20));
275 assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23));
276
277 assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
278 }
279
280}
diff --git a/crates/ra_ide_api/src/line_index_utils.rs b/crates/ra_ide_api/src/line_index_utils.rs
new file mode 100644
index 000000000..799a920ad
--- /dev/null
+++ b/crates/ra_ide_api/src/line_index_utils.rs
@@ -0,0 +1,330 @@
1use ra_text_edit::{AtomTextEdit, TextEdit};
2use ra_syntax::{TextUnit, TextRange};
3use crate::{LineIndex, LineCol, line_index::Utf16Char};
4
5#[derive(Debug, Clone)]
6enum Step {
7 Newline(TextUnit),
8 Utf16Char(TextRange),
9}
10
11#[derive(Debug)]
12struct LineIndexStepIter<'a> {
13 line_index: &'a LineIndex,
14 next_newline_idx: usize,
15 utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>,
16}
17
18impl<'a> LineIndexStepIter<'a> {
19 fn from(line_index: &LineIndex) -> LineIndexStepIter {
20 let mut x = LineIndexStepIter { line_index, next_newline_idx: 0, utf16_chars: None };
21 // skip first newline since it's not real
22 x.next();
23 x
24 }
25}
26
27impl<'a> Iterator for LineIndexStepIter<'a> {
28 type Item = Step;
29 fn next(&mut self) -> Option<Step> {
30 self.utf16_chars
31 .as_mut()
32 .and_then(|(newline, x)| {
33 let x = x.next()?;
34 Some(Step::Utf16Char(TextRange::from_to(*newline + x.start, *newline + x.end)))
35 })
36 .or_else(|| {
37 let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?;
38 self.utf16_chars = self
39 .line_index
40 .utf16_lines
41 .get(&(self.next_newline_idx as u32))
42 .map(|x| (next_newline, x.iter()));
43 self.next_newline_idx += 1;
44 Some(Step::Newline(next_newline))
45 })
46 }
47}
48
49#[derive(Debug)]
50struct OffsetStepIter<'a> {
51 text: &'a str,
52 offset: TextUnit,
53}
54
55impl<'a> Iterator for OffsetStepIter<'a> {
56 type Item = Step;
57 fn next(&mut self) -> Option<Step> {
58 let (next, next_offset) = self
59 .text
60 .char_indices()
61 .filter_map(|(i, c)| {
62 if c == '\n' {
63 let next_offset = self.offset + TextUnit::from_usize(i + 1);
64 let next = Step::Newline(next_offset);
65 Some((next, next_offset))
66 } else {
67 let char_len = TextUnit::of_char(c);
68 if char_len.to_usize() > 1 {
69 let start = self.offset + TextUnit::from_usize(i);
70 let end = start + char_len;
71 let next = Step::Utf16Char(TextRange::from_to(start, end));
72 let next_offset = end;
73 Some((next, next_offset))
74 } else {
75 None
76 }
77 }
78 })
79 .next()?;
80 let next_idx = (next_offset - self.offset).to_usize();
81 self.text = &self.text[next_idx..];
82 self.offset = next_offset;
83 Some(next)
84 }
85}
86
87#[derive(Debug)]
88enum NextSteps<'a> {
89 Use,
90 ReplaceMany(OffsetStepIter<'a>),
91 AddMany(OffsetStepIter<'a>),
92}
93
94#[derive(Debug)]
95struct TranslatedEdit<'a> {
96 delete: TextRange,
97 insert: &'a str,
98 diff: i64,
99}
100
101struct Edits<'a> {
102 edits: &'a [AtomTextEdit],
103 current: Option<TranslatedEdit<'a>>,
104 acc_diff: i64,
105}
106
107impl<'a> Edits<'a> {
108 fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> {
109 let mut x = Edits { edits: text_edit.as_atoms(), current: None, acc_diff: 0 };
110 x.advance_edit();
111 x
112 }
113 fn advance_edit(&mut self) {
114 self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff);
115 match self.edits.split_first() {
116 Some((next, rest)) => {
117 let delete = self.translate_range(next.delete);
118 let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64;
119 self.current = Some(TranslatedEdit { delete, insert: &next.insert, diff });
120 self.edits = rest;
121 }
122 None => {
123 self.current = None;
124 }
125 }
126 }
127
128 fn next_inserted_steps(&mut self) -> Option<OffsetStepIter<'a>> {
129 let cur = self.current.as_ref()?;
130 let res = Some(OffsetStepIter { offset: cur.delete.start(), text: &cur.insert });
131 self.advance_edit();
132 res
133 }
134
135 fn next_steps(&mut self, step: &Step) -> NextSteps {
136 let step_pos = match step {
137 &Step::Newline(n) => n,
138 &Step::Utf16Char(r) => r.end(),
139 };
140 let res = match &mut self.current {
141 Some(edit) => {
142 if step_pos <= edit.delete.start() {
143 NextSteps::Use
144 } else if step_pos <= edit.delete.end() {
145 let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert };
146 // empty slice to avoid returning steps again
147 edit.insert = &edit.insert[edit.insert.len()..];
148 NextSteps::ReplaceMany(iter)
149 } else {
150 let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert };
151 // empty slice to avoid returning steps again
152 edit.insert = &edit.insert[edit.insert.len()..];
153 self.advance_edit();
154 NextSteps::AddMany(iter)
155 }
156 }
157 None => NextSteps::Use,
158 };
159 res
160 }
161
162 fn translate_range(&self, range: TextRange) -> TextRange {
163 if self.acc_diff == 0 {
164 range
165 } else {
166 let start = self.translate(range.start());
167 let end = self.translate(range.end());
168 TextRange::from_to(start, end)
169 }
170 }
171
172 fn translate(&self, x: TextUnit) -> TextUnit {
173 if self.acc_diff == 0 {
174 x
175 } else {
176 TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32)
177 }
178 }
179
180 fn translate_step(&self, x: &Step) -> Step {
181 if self.acc_diff == 0 {
182 x.clone()
183 } else {
184 match x {
185 &Step::Newline(n) => Step::Newline(self.translate(n)),
186 &Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)),
187 }
188 }
189 }
190}
191
192#[derive(Debug)]
193struct RunningLineCol {
194 line: u32,
195 last_newline: TextUnit,
196 col_adjust: TextUnit,
197}
198
199impl RunningLineCol {
200 fn new() -> RunningLineCol {
201 RunningLineCol { line: 0, last_newline: TextUnit::from(0), col_adjust: TextUnit::from(0) }
202 }
203
204 fn to_line_col(&self, offset: TextUnit) -> LineCol {
205 LineCol {
206 line: self.line,
207 col_utf16: ((offset - self.last_newline) - self.col_adjust).into(),
208 }
209 }
210
211 fn add_line(&mut self, newline: TextUnit) {
212 self.line += 1;
213 self.last_newline = newline;
214 self.col_adjust = TextUnit::from(0);
215 }
216
217 fn adjust_col(&mut self, range: &TextRange) {
218 self.col_adjust += range.len() - TextUnit::from(1);
219 }
220}
221
222pub fn translate_offset_with_edit(
223 line_index: &LineIndex,
224 offset: TextUnit,
225 text_edit: &TextEdit,
226) -> LineCol {
227 let mut state = Edits::from_text_edit(&text_edit);
228
229 let mut res = RunningLineCol::new();
230
231 macro_rules! test_step {
232 ($x:ident) => {
233 match &$x {
234 Step::Newline(n) => {
235 if offset < *n {
236 return res.to_line_col(offset);
237 } else {
238 res.add_line(*n);
239 }
240 }
241 Step::Utf16Char(x) => {
242 if offset < x.end() {
243 // if the offset is inside a multibyte char it's invalid
244 // clamp it to the start of the char
245 let clamp = offset.min(x.start());
246 return res.to_line_col(clamp);
247 } else {
248 res.adjust_col(x);
249 }
250 }
251 }
252 };
253 }
254
255 for orig_step in LineIndexStepIter::from(line_index) {
256 loop {
257 let translated_step = state.translate_step(&orig_step);
258 match state.next_steps(&translated_step) {
259 NextSteps::Use => {
260 test_step!(translated_step);
261 break;
262 }
263 NextSteps::ReplaceMany(ns) => {
264 for n in ns {
265 test_step!(n);
266 }
267 break;
268 }
269 NextSteps::AddMany(ns) => {
270 for n in ns {
271 test_step!(n);
272 }
273 }
274 }
275 }
276 }
277
278 loop {
279 match state.next_inserted_steps() {
280 None => break,
281 Some(ns) => {
282 for n in ns {
283 test_step!(n);
284 }
285 }
286 }
287 }
288
289 res.to_line_col(offset)
290}
291
292#[cfg(test)]
293mod test {
294 use super::*;
295 use proptest::{prelude::*, proptest};
296 use crate::line_index;
297 use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit};
298 use ra_text_edit::TextEdit;
299
300 #[derive(Debug)]
301 struct ArbTextWithEditAndOffset {
302 text: String,
303 edit: TextEdit,
304 edited_text: String,
305 offset: TextUnit,
306 }
307
308 fn arb_text_with_edit_and_offset() -> BoxedStrategy<ArbTextWithEditAndOffset> {
309 arb_text_with_edit()
310 .prop_flat_map(|x| {
311 let edited_text = x.edit.apply(&x.text);
312 let arb_offset = arb_offset(&edited_text);
313 (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| {
314 ArbTextWithEditAndOffset { text: x.text, edit: x.edit, edited_text, offset }
315 })
316 })
317 .boxed()
318 }
319
320 proptest! {
321 #[test]
322 fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) {
323 let expected = line_index::to_line_col(&x.edited_text, x.offset);
324 let line_index = LineIndex::new(&x.text);
325 let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit);
326
327 assert_eq!(actual, expected);
328 }
329 }
330}