diff options
author | Aleksey Kladov <[email protected]> | 2019-01-08 19:17:36 +0000 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2019-01-08 19:17:36 +0000 |
commit | 1967884d6836219ee78a754ca5c66ac781351559 (patch) | |
tree | 7594f37cd0a5200eb097b9d472c61f0223d01d05 /crates/ra_ide_api_light/src/line_index_utils.rs | |
parent | 4f4f7933b1b7ff34f8633b1686b18b2d1b994c47 (diff) |
rename ra_editor -> ra_ide_api_light
Diffstat (limited to 'crates/ra_ide_api_light/src/line_index_utils.rs')
-rw-r--r-- | crates/ra_ide_api_light/src/line_index_utils.rs | 363 |
1 files changed, 363 insertions, 0 deletions
diff --git a/crates/ra_ide_api_light/src/line_index_utils.rs b/crates/ra_ide_api_light/src/line_index_utils.rs new file mode 100644 index 000000000..ec3269bbb --- /dev/null +++ b/crates/ra_ide_api_light/src/line_index_utils.rs | |||
@@ -0,0 +1,363 @@ | |||
1 | use ra_text_edit::{AtomTextEdit, TextEdit}; | ||
2 | use ra_syntax::{TextUnit, TextRange}; | ||
3 | use crate::{LineIndex, LineCol, line_index::Utf16Char}; | ||
4 | |||
5 | #[derive(Debug, Clone)] | ||
6 | enum Step { | ||
7 | Newline(TextUnit), | ||
8 | Utf16Char(TextRange), | ||
9 | } | ||
10 | |||
11 | #[derive(Debug)] | ||
12 | struct LineIndexStepIter<'a> { | ||
13 | line_index: &'a LineIndex, | ||
14 | next_newline_idx: usize, | ||
15 | utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>, | ||
16 | } | ||
17 | |||
18 | impl<'a> LineIndexStepIter<'a> { | ||
19 | fn from(line_index: &LineIndex) -> LineIndexStepIter { | ||
20 | let mut x = LineIndexStepIter { | ||
21 | line_index, | ||
22 | next_newline_idx: 0, | ||
23 | utf16_chars: None, | ||
24 | }; | ||
25 | // skip first newline since it's not real | ||
26 | x.next(); | ||
27 | x | ||
28 | } | ||
29 | } | ||
30 | |||
31 | impl<'a> Iterator for LineIndexStepIter<'a> { | ||
32 | type Item = Step; | ||
33 | fn next(&mut self) -> Option<Step> { | ||
34 | self.utf16_chars | ||
35 | .as_mut() | ||
36 | .and_then(|(newline, x)| { | ||
37 | let x = x.next()?; | ||
38 | Some(Step::Utf16Char(TextRange::from_to( | ||
39 | *newline + x.start, | ||
40 | *newline + x.end, | ||
41 | ))) | ||
42 | }) | ||
43 | .or_else(|| { | ||
44 | let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?; | ||
45 | self.utf16_chars = self | ||
46 | .line_index | ||
47 | .utf16_lines | ||
48 | .get(&(self.next_newline_idx as u32)) | ||
49 | .map(|x| (next_newline, x.iter())); | ||
50 | self.next_newline_idx += 1; | ||
51 | Some(Step::Newline(next_newline)) | ||
52 | }) | ||
53 | } | ||
54 | } | ||
55 | |||
56 | #[derive(Debug)] | ||
57 | struct OffsetStepIter<'a> { | ||
58 | text: &'a str, | ||
59 | offset: TextUnit, | ||
60 | } | ||
61 | |||
62 | impl<'a> Iterator for OffsetStepIter<'a> { | ||
63 | type Item = Step; | ||
64 | fn next(&mut self) -> Option<Step> { | ||
65 | let (next, next_offset) = self | ||
66 | .text | ||
67 | .char_indices() | ||
68 | .filter_map(|(i, c)| { | ||
69 | if c == '\n' { | ||
70 | let next_offset = self.offset + TextUnit::from_usize(i + 1); | ||
71 | let next = Step::Newline(next_offset); | ||
72 | Some((next, next_offset)) | ||
73 | } else { | ||
74 | let char_len = TextUnit::of_char(c); | ||
75 | if char_len.to_usize() > 1 { | ||
76 | let start = self.offset + TextUnit::from_usize(i); | ||
77 | let end = start + char_len; | ||
78 | let next = Step::Utf16Char(TextRange::from_to(start, end)); | ||
79 | let next_offset = end; | ||
80 | Some((next, next_offset)) | ||
81 | } else { | ||
82 | None | ||
83 | } | ||
84 | } | ||
85 | }) | ||
86 | .next()?; | ||
87 | let next_idx = (next_offset - self.offset).to_usize(); | ||
88 | self.text = &self.text[next_idx..]; | ||
89 | self.offset = next_offset; | ||
90 | Some(next) | ||
91 | } | ||
92 | } | ||
93 | |||
94 | #[derive(Debug)] | ||
95 | enum NextSteps<'a> { | ||
96 | Use, | ||
97 | ReplaceMany(OffsetStepIter<'a>), | ||
98 | AddMany(OffsetStepIter<'a>), | ||
99 | } | ||
100 | |||
101 | #[derive(Debug)] | ||
102 | struct TranslatedEdit<'a> { | ||
103 | delete: TextRange, | ||
104 | insert: &'a str, | ||
105 | diff: i64, | ||
106 | } | ||
107 | |||
108 | struct Edits<'a> { | ||
109 | edits: &'a [AtomTextEdit], | ||
110 | current: Option<TranslatedEdit<'a>>, | ||
111 | acc_diff: i64, | ||
112 | } | ||
113 | |||
114 | impl<'a> Edits<'a> { | ||
115 | fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> { | ||
116 | let mut x = Edits { | ||
117 | edits: text_edit.as_atoms(), | ||
118 | current: None, | ||
119 | acc_diff: 0, | ||
120 | }; | ||
121 | x.advance_edit(); | ||
122 | x | ||
123 | } | ||
124 | fn advance_edit(&mut self) { | ||
125 | self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff); | ||
126 | match self.edits.split_first() { | ||
127 | Some((next, rest)) => { | ||
128 | let delete = self.translate_range(next.delete); | ||
129 | let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64; | ||
130 | self.current = Some(TranslatedEdit { | ||
131 | delete, | ||
132 | insert: &next.insert, | ||
133 | diff, | ||
134 | }); | ||
135 | self.edits = rest; | ||
136 | } | ||
137 | None => { | ||
138 | self.current = None; | ||
139 | } | ||
140 | } | ||
141 | } | ||
142 | |||
143 | fn next_inserted_steps(&mut self) -> Option<OffsetStepIter<'a>> { | ||
144 | let cur = self.current.as_ref()?; | ||
145 | let res = Some(OffsetStepIter { | ||
146 | offset: cur.delete.start(), | ||
147 | text: &cur.insert, | ||
148 | }); | ||
149 | self.advance_edit(); | ||
150 | res | ||
151 | } | ||
152 | |||
153 | fn next_steps(&mut self, step: &Step) -> NextSteps { | ||
154 | let step_pos = match step { | ||
155 | &Step::Newline(n) => n, | ||
156 | &Step::Utf16Char(r) => r.end(), | ||
157 | }; | ||
158 | let res = match &mut self.current { | ||
159 | Some(edit) => { | ||
160 | if step_pos <= edit.delete.start() { | ||
161 | NextSteps::Use | ||
162 | } else if step_pos <= edit.delete.end() { | ||
163 | let iter = OffsetStepIter { | ||
164 | offset: edit.delete.start(), | ||
165 | text: &edit.insert, | ||
166 | }; | ||
167 | // empty slice to avoid returning steps again | ||
168 | edit.insert = &edit.insert[edit.insert.len()..]; | ||
169 | NextSteps::ReplaceMany(iter) | ||
170 | } else { | ||
171 | let iter = OffsetStepIter { | ||
172 | offset: edit.delete.start(), | ||
173 | text: &edit.insert, | ||
174 | }; | ||
175 | // empty slice to avoid returning steps again | ||
176 | edit.insert = &edit.insert[edit.insert.len()..]; | ||
177 | self.advance_edit(); | ||
178 | NextSteps::AddMany(iter) | ||
179 | } | ||
180 | } | ||
181 | None => NextSteps::Use, | ||
182 | }; | ||
183 | res | ||
184 | } | ||
185 | |||
186 | fn translate_range(&self, range: TextRange) -> TextRange { | ||
187 | if self.acc_diff == 0 { | ||
188 | range | ||
189 | } else { | ||
190 | let start = self.translate(range.start()); | ||
191 | let end = self.translate(range.end()); | ||
192 | TextRange::from_to(start, end) | ||
193 | } | ||
194 | } | ||
195 | |||
196 | fn translate(&self, x: TextUnit) -> TextUnit { | ||
197 | if self.acc_diff == 0 { | ||
198 | x | ||
199 | } else { | ||
200 | TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32) | ||
201 | } | ||
202 | } | ||
203 | |||
204 | fn translate_step(&self, x: &Step) -> Step { | ||
205 | if self.acc_diff == 0 { | ||
206 | x.clone() | ||
207 | } else { | ||
208 | match x { | ||
209 | &Step::Newline(n) => Step::Newline(self.translate(n)), | ||
210 | &Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)), | ||
211 | } | ||
212 | } | ||
213 | } | ||
214 | } | ||
215 | |||
216 | #[derive(Debug)] | ||
217 | struct RunningLineCol { | ||
218 | line: u32, | ||
219 | last_newline: TextUnit, | ||
220 | col_adjust: TextUnit, | ||
221 | } | ||
222 | |||
223 | impl RunningLineCol { | ||
224 | fn new() -> RunningLineCol { | ||
225 | RunningLineCol { | ||
226 | line: 0, | ||
227 | last_newline: TextUnit::from(0), | ||
228 | col_adjust: TextUnit::from(0), | ||
229 | } | ||
230 | } | ||
231 | |||
232 | fn to_line_col(&self, offset: TextUnit) -> LineCol { | ||
233 | LineCol { | ||
234 | line: self.line, | ||
235 | col_utf16: ((offset - self.last_newline) - self.col_adjust).into(), | ||
236 | } | ||
237 | } | ||
238 | |||
239 | fn add_line(&mut self, newline: TextUnit) { | ||
240 | self.line += 1; | ||
241 | self.last_newline = newline; | ||
242 | self.col_adjust = TextUnit::from(0); | ||
243 | } | ||
244 | |||
245 | fn adjust_col(&mut self, range: &TextRange) { | ||
246 | self.col_adjust += range.len() - TextUnit::from(1); | ||
247 | } | ||
248 | } | ||
249 | |||
250 | pub fn translate_offset_with_edit( | ||
251 | line_index: &LineIndex, | ||
252 | offset: TextUnit, | ||
253 | text_edit: &TextEdit, | ||
254 | ) -> LineCol { | ||
255 | let mut state = Edits::from_text_edit(&text_edit); | ||
256 | |||
257 | let mut res = RunningLineCol::new(); | ||
258 | |||
259 | macro_rules! test_step { | ||
260 | ($x:ident) => { | ||
261 | match &$x { | ||
262 | Step::Newline(n) => { | ||
263 | if offset < *n { | ||
264 | return res.to_line_col(offset); | ||
265 | } else { | ||
266 | res.add_line(*n); | ||
267 | } | ||
268 | } | ||
269 | Step::Utf16Char(x) => { | ||
270 | if offset < x.end() { | ||
271 | // if the offset is inside a multibyte char it's invalid | ||
272 | // clamp it to the start of the char | ||
273 | let clamp = offset.min(x.start()); | ||
274 | return res.to_line_col(clamp); | ||
275 | } else { | ||
276 | res.adjust_col(x); | ||
277 | } | ||
278 | } | ||
279 | } | ||
280 | }; | ||
281 | } | ||
282 | |||
283 | for orig_step in LineIndexStepIter::from(line_index) { | ||
284 | loop { | ||
285 | let translated_step = state.translate_step(&orig_step); | ||
286 | match state.next_steps(&translated_step) { | ||
287 | NextSteps::Use => { | ||
288 | test_step!(translated_step); | ||
289 | break; | ||
290 | } | ||
291 | NextSteps::ReplaceMany(ns) => { | ||
292 | for n in ns { | ||
293 | test_step!(n); | ||
294 | } | ||
295 | break; | ||
296 | } | ||
297 | NextSteps::AddMany(ns) => { | ||
298 | for n in ns { | ||
299 | test_step!(n); | ||
300 | } | ||
301 | } | ||
302 | } | ||
303 | } | ||
304 | } | ||
305 | |||
306 | loop { | ||
307 | match state.next_inserted_steps() { | ||
308 | None => break, | ||
309 | Some(ns) => { | ||
310 | for n in ns { | ||
311 | test_step!(n); | ||
312 | } | ||
313 | } | ||
314 | } | ||
315 | } | ||
316 | |||
317 | res.to_line_col(offset) | ||
318 | } | ||
319 | |||
320 | #[cfg(test)] | ||
321 | mod test { | ||
322 | use super::*; | ||
323 | use proptest::{prelude::*, proptest, proptest_helper}; | ||
324 | use crate::line_index; | ||
325 | use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit}; | ||
326 | use ra_text_edit::TextEdit; | ||
327 | |||
328 | #[derive(Debug)] | ||
329 | struct ArbTextWithEditAndOffset { | ||
330 | text: String, | ||
331 | edit: TextEdit, | ||
332 | edited_text: String, | ||
333 | offset: TextUnit, | ||
334 | } | ||
335 | |||
336 | fn arb_text_with_edit_and_offset() -> BoxedStrategy<ArbTextWithEditAndOffset> { | ||
337 | arb_text_with_edit() | ||
338 | .prop_flat_map(|x| { | ||
339 | let edited_text = x.edit.apply(&x.text); | ||
340 | let arb_offset = arb_offset(&edited_text); | ||
341 | (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| { | ||
342 | ArbTextWithEditAndOffset { | ||
343 | text: x.text, | ||
344 | edit: x.edit, | ||
345 | edited_text, | ||
346 | offset, | ||
347 | } | ||
348 | }) | ||
349 | }) | ||
350 | .boxed() | ||
351 | } | ||
352 | |||
353 | proptest! { | ||
354 | #[test] | ||
355 | fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) { | ||
356 | let expected = line_index::to_line_col(&x.edited_text, x.offset); | ||
357 | let line_index = LineIndex::new(&x.text); | ||
358 | let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit); | ||
359 | |||
360 | assert_eq!(actual, expected); | ||
361 | } | ||
362 | } | ||
363 | } | ||