diff options
author | Bernardo <[email protected]> | 2018-12-21 17:38:28 +0000 |
---|---|---|
committer | Bernardo <[email protected]> | 2018-12-25 18:59:02 +0000 |
commit | a005d2a614031a18c9a5bf6557789a41f1b25c31 (patch) | |
tree | 517d8b6885ab5a4eacb1d3bc77266aeea14a9a85 /crates/ra_editor | |
parent | 7299df8409097de67647b371b81da7bcf49112e6 (diff) |
final iteration, faster a bit simpler
the main thing is we iterate over inserted newlines at once for each edit
Diffstat (limited to 'crates/ra_editor')
-rw-r--r-- | crates/ra_editor/src/line_index_utils.rs | 380 |
1 files changed, 209 insertions, 171 deletions
diff --git a/crates/ra_editor/src/line_index_utils.rs b/crates/ra_editor/src/line_index_utils.rs index 6bd6a397e..5ce2446c1 100644 --- a/crates/ra_editor/src/line_index_utils.rs +++ b/crates/ra_editor/src/line_index_utils.rs | |||
@@ -1,4 +1,4 @@ | |||
1 | use ra_text_edit::{AtomTextEdit}; | 1 | use ra_text_edit::AtomTextEdit; |
2 | use ra_syntax::{TextUnit, TextRange}; | 2 | use ra_syntax::{TextUnit, TextRange}; |
3 | use crate::{LineIndex, LineCol}; | 3 | use crate::{LineIndex, LineCol}; |
4 | use superslice::Ext; | 4 | use superslice::Ext; |
@@ -24,41 +24,6 @@ impl<'a> Iterator for OffsetNewlineIter<'a> { | |||
24 | } | 24 | } |
25 | } | 25 | } |
26 | 26 | ||
27 | #[derive(Debug, Clone, Copy, PartialEq)] | ||
28 | enum TranslatedPos { | ||
29 | Before, | ||
30 | After, | ||
31 | } | ||
32 | |||
33 | /// None means it was deleted | ||
34 | type TranslatedOffset = Option<(TranslatedPos, TextUnit)>; | ||
35 | |||
36 | fn translate_offset(offset: TextUnit, edit: &TranslatedAtomEdit) -> TranslatedOffset { | ||
37 | if offset <= edit.delete.start() { | ||
38 | Some((TranslatedPos::Before, offset)) | ||
39 | } else if offset <= edit.delete.end() { | ||
40 | None | ||
41 | } else { | ||
42 | let diff = edit.insert.len() as i64 - edit.delete.len().to_usize() as i64; | ||
43 | let after = TextUnit::from((offset.to_usize() as i64 + diff) as u32); | ||
44 | Some((TranslatedPos::After, after)) | ||
45 | } | ||
46 | } | ||
47 | |||
48 | trait TranslatedNewlineIterator { | ||
49 | fn translate(&self, offset: TextUnit) -> TextUnit; | ||
50 | fn translate_range(&self, range: TextRange) -> TextRange { | ||
51 | TextRange::from_to(self.translate(range.start()), self.translate(range.end())) | ||
52 | } | ||
53 | fn next_translated(&mut self) -> Option<TextUnit>; | ||
54 | fn boxed<'a>(self) -> Box<TranslatedNewlineIterator + 'a> | ||
55 | where | ||
56 | Self: 'a + Sized, | ||
57 | { | ||
58 | Box::new(self) | ||
59 | } | ||
60 | } | ||
61 | |||
62 | #[derive(Debug)] | 27 | #[derive(Debug)] |
63 | struct AltEdit<'a> { | 28 | struct AltEdit<'a> { |
64 | insert_newlines: OffsetNewlineIter<'a>, | 29 | insert_newlines: OffsetNewlineIter<'a>, |
@@ -156,7 +121,7 @@ fn next_newline(candidate: Option<TextUnit>, edits: &mut [AltEdit]) -> NextNewli | |||
156 | return NextNewline::Replace(candidate); | 121 | return NextNewline::Replace(candidate); |
157 | } | 122 | } |
158 | 123 | ||
159 | fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { | 124 | pub fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { |
160 | let mut edits = to_alt_edits(offset, edits); | 125 | let mut edits = to_alt_edits(offset, edits); |
161 | let mut orig_newlines = line_index.newlines().iter().map(|x| *x).peekable(); | 126 | let mut orig_newlines = line_index.newlines().iter().map(|x| *x).peekable(); |
162 | 127 | ||
@@ -189,142 +154,184 @@ fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdi | |||
189 | count | 154 | count |
190 | } | 155 | } |
191 | 156 | ||
192 | struct TranslatedAtomEdit<'a> { | 157 | #[derive(Debug)] |
158 | enum NextNewlines<'a> { | ||
159 | Use, | ||
160 | ReplaceMany(OffsetNewlineIter<'a>), | ||
161 | AddMany(OffsetNewlineIter<'a>), | ||
162 | } | ||
163 | |||
164 | #[derive(Debug)] | ||
165 | struct TranslatedEdit<'a> { | ||
193 | delete: TextRange, | 166 | delete: TextRange, |
194 | insert: &'a str, | 167 | insert: &'a str, |
168 | diff: i64, | ||
195 | } | 169 | } |
196 | 170 | ||
197 | struct TranslatedNewlines<'a, T: TranslatedNewlineIterator> { | 171 | struct Edits<'a, 'b> { |
198 | inner: T, | 172 | edits: &'b [&'a AtomTextEdit], |
199 | next_inner: Option<TranslatedOffset>, | 173 | current: Option<TranslatedEdit<'a>>, |
200 | edit: TranslatedAtomEdit<'a>, | 174 | acc_diff: i64, |
201 | insert: OffsetNewlineIter<'a>, | ||
202 | } | 175 | } |
203 | 176 | ||
204 | impl<'a, T: TranslatedNewlineIterator> TranslatedNewlines<'a, T> { | 177 | impl<'a, 'b> Edits<'a, 'b> { |
205 | fn from(inner: T, edit: &'a AtomTextEdit) -> Self { | 178 | fn new(sorted_edits: &'b [&'a AtomTextEdit]) -> Edits<'a, 'b> { |
206 | let delete = inner.translate_range(edit.delete); | 179 | let mut x = Edits { |
207 | let mut res = TranslatedNewlines { | 180 | edits: sorted_edits, |
208 | inner, | 181 | current: None, |
209 | next_inner: None, | 182 | acc_diff: 0, |
210 | edit: TranslatedAtomEdit { | ||
211 | delete, | ||
212 | insert: &edit.insert, | ||
213 | }, | ||
214 | insert: OffsetNewlineIter { | ||
215 | offset: delete.start(), | ||
216 | text: &edit.insert, | ||
217 | }, | ||
218 | }; | 183 | }; |
219 | // prepare next_inner | 184 | x.advance_edit(); |
220 | res.advance_inner(); | 185 | x |
221 | res | ||
222 | } | 186 | } |
223 | 187 | fn advance_edit(&mut self) { | |
224 | fn advance_inner(&mut self) { | 188 | self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff); |
225 | self.next_inner = self | 189 | match self.edits.split_first() { |
226 | .inner | 190 | Some((next, rest)) => { |
227 | .next_translated() | 191 | let delete = translate_range_by(next.delete, self.acc_diff); |
228 | .map(|x| translate_offset(x, &self.edit)); | 192 | let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64; |
193 | self.current = Some(TranslatedEdit { | ||
194 | delete, | ||
195 | insert: &next.insert, | ||
196 | diff, | ||
197 | }); | ||
198 | self.edits = rest; | ||
199 | } | ||
200 | None => { | ||
201 | self.current = None; | ||
202 | } | ||
203 | } | ||
229 | } | 204 | } |
230 | } | ||
231 | 205 | ||
232 | impl<'a, T: TranslatedNewlineIterator> TranslatedNewlineIterator for TranslatedNewlines<'a, T> { | 206 | fn next_inserted_newlines(&mut self) -> Option<OffsetNewlineIter<'a>> { |
233 | fn translate(&self, offset: TextUnit) -> TextUnit { | 207 | let cur = self.current.as_ref()?; |
234 | let offset = self.inner.translate(offset); | 208 | let res = Some(OffsetNewlineIter { |
235 | let (_, offset) = | 209 | offset: cur.delete.start(), |
236 | translate_offset(offset, &self.edit).expect("translate_unit returned None"); | 210 | text: &cur.insert, |
237 | offset | 211 | }); |
212 | self.advance_edit(); | ||
213 | res | ||
238 | } | 214 | } |
239 | 215 | ||
240 | fn next_translated(&mut self) -> Option<TextUnit> { | 216 | fn next_newlines(&mut self, candidate: TextUnit) -> NextNewlines { |
241 | match self.next_inner { | 217 | let res = match &mut self.current { |
242 | None => self.insert.next(), | 218 | Some(edit) => { |
243 | Some(next) => match next { | 219 | if candidate <= edit.delete.start() { |
244 | None => self.insert.next().or_else(|| { | 220 | NextNewlines::Use |
245 | self.advance_inner(); | 221 | } else if candidate <= edit.delete.end() { |
246 | self.next_translated() | 222 | let iter = OffsetNewlineIter { |
247 | }), | 223 | offset: edit.delete.start(), |
248 | Some((TranslatedPos::Before, next)) => { | 224 | text: &edit.insert, |
249 | self.advance_inner(); | 225 | }; |
250 | Some(next) | 226 | // empty slice |
227 | edit.insert = &edit.insert[edit.insert.len()..]; | ||
228 | NextNewlines::ReplaceMany(iter) | ||
229 | } else { | ||
230 | let iter = OffsetNewlineIter { | ||
231 | offset: edit.delete.start(), | ||
232 | text: &edit.insert, | ||
233 | }; | ||
234 | // empty slice | ||
235 | edit.insert = &edit.insert[edit.insert.len()..]; | ||
236 | self.advance_edit(); | ||
237 | NextNewlines::AddMany(iter) | ||
251 | } | 238 | } |
252 | Some((TranslatedPos::After, next)) => self.insert.next().or_else(|| { | 239 | } |
253 | self.advance_inner(); | 240 | None => NextNewlines::Use, |
254 | Some(next) | 241 | }; |
255 | }), | 242 | res |
256 | }, | ||
257 | } | ||
258 | } | ||
259 | } | ||
260 | |||
261 | impl<'a> Iterator for Box<dyn TranslatedNewlineIterator + 'a> { | ||
262 | type Item = TextUnit; | ||
263 | fn next(&mut self) -> Option<TextUnit> { | ||
264 | self.next_translated() | ||
265 | } | 243 | } |
266 | } | 244 | } |
267 | 245 | ||
268 | impl<T: TranslatedNewlineIterator + ?Sized> TranslatedNewlineIterator for Box<T> { | 246 | pub fn count_newlines_alt(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { |
269 | fn translate(&self, offset: TextUnit) -> TextUnit { | 247 | let mut sorted_edits: Vec<&AtomTextEdit> = Vec::with_capacity(edits.len()); |
270 | self.as_ref().translate(offset) | 248 | for edit in edits { |
271 | } | 249 | let insert_index = |
272 | fn next_translated(&mut self) -> Option<TextUnit> { | 250 | sorted_edits.upper_bound_by_key(&edit.delete.start(), |x| x.delete.start()); |
273 | self.as_mut().next_translated() | 251 | sorted_edits.insert(insert_index, &edit); |
274 | } | 252 | } |
275 | } | ||
276 | |||
277 | struct IteratorWrapper<T: Iterator<Item = TextUnit>>(T); | ||
278 | 253 | ||
279 | impl<T: Iterator<Item = TextUnit>> TranslatedNewlineIterator for IteratorWrapper<T> { | 254 | let mut state = Edits::new(&sorted_edits); |
280 | fn translate(&self, offset: TextUnit) -> TextUnit { | 255 | |
281 | offset | 256 | let mut lines: u32 = 0; |
282 | } | 257 | |
283 | fn next_translated(&mut self) -> Option<TextUnit> { | 258 | for &orig_newline in line_index.newlines() { |
284 | self.0.next() | 259 | loop { |
260 | let translated_newline = translate_by(orig_newline, state.acc_diff); | ||
261 | match state.next_newlines(translated_newline) { | ||
262 | NextNewlines::Use => { | ||
263 | if offset < translated_newline { | ||
264 | return lines; | ||
265 | } else { | ||
266 | lines += 1; | ||
267 | } | ||
268 | break; | ||
269 | } | ||
270 | NextNewlines::ReplaceMany(ns) => { | ||
271 | for n in ns { | ||
272 | if offset < n { | ||
273 | return lines; | ||
274 | } else { | ||
275 | lines += 1; | ||
276 | } | ||
277 | } | ||
278 | break; | ||
279 | } | ||
280 | NextNewlines::AddMany(ns) => { | ||
281 | for n in ns { | ||
282 | if offset < n { | ||
283 | return lines; | ||
284 | } else { | ||
285 | lines += 1; | ||
286 | } | ||
287 | } | ||
288 | } | ||
289 | } | ||
290 | } | ||
285 | } | 291 | } |
286 | } | ||
287 | 292 | ||
288 | impl<T: Iterator<Item = TextUnit>> Iterator for IteratorWrapper<T> { | 293 | loop { |
289 | type Item = TextUnit; | 294 | match state.next_inserted_newlines() { |
290 | fn next(&mut self) -> Option<TextUnit> { | 295 | None => break, |
291 | self.0.next() | 296 | Some(ns) => { |
297 | for n in ns { | ||
298 | if offset < n { | ||
299 | return lines; | ||
300 | } else { | ||
301 | lines += 1; | ||
302 | } | ||
303 | } | ||
304 | } | ||
305 | } | ||
292 | } | 306 | } |
293 | } | ||
294 | 307 | ||
295 | fn translate_newlines<'a>( | 308 | lines |
296 | mut newlines: Box<TranslatedNewlineIterator + 'a>, | ||
297 | edits: &'a [AtomTextEdit], | ||
298 | ) -> Box<TranslatedNewlineIterator + 'a> { | ||
299 | for edit in edits { | ||
300 | newlines = TranslatedNewlines::from(newlines, edit).boxed(); | ||
301 | } | ||
302 | newlines | ||
303 | } | 309 | } |
304 | 310 | ||
305 | pub fn translate_offset_with_edit( | 311 | // for bench |
306 | pre_edit_index: &LineIndex, | 312 | pub fn translate_after_edit( |
313 | pre_edit_text: &str, | ||
307 | offset: TextUnit, | 314 | offset: TextUnit, |
308 | edits: &[AtomTextEdit], | 315 | edits: Vec<AtomTextEdit>, |
309 | ) -> LineCol { | 316 | ) -> LineCol { |
310 | let mut newlines: Box<TranslatedNewlineIterator> = Box::new(IteratorWrapper( | 317 | let text = edit_text(pre_edit_text, edits); |
311 | pre_edit_index.newlines().iter().map(|x| *x), | 318 | let line_index = LineIndex::new(&text); |
312 | )); | 319 | line_index.line_col(offset) |
320 | } | ||
313 | 321 | ||
314 | newlines = translate_newlines(newlines, edits); | 322 | fn edit_text(pre_edit_text: &str, mut edits: Vec<AtomTextEdit>) -> String { |
323 | // apply edits ordered from last to first | ||
324 | // since they should not overlap we can just use start() | ||
325 | edits.sort_by_key(|x| -(x.delete.start().to_usize() as isize)); | ||
315 | 326 | ||
316 | let mut line = 0; | 327 | let mut text = pre_edit_text.to_owned(); |
317 | for n in newlines { | ||
318 | if n > offset { | ||
319 | break; | ||
320 | } | ||
321 | line += 1; | ||
322 | } | ||
323 | 328 | ||
324 | LineCol { | 329 | for edit in &edits { |
325 | line: line, | 330 | let range = edit.delete.start().to_usize()..edit.delete.end().to_usize(); |
326 | col_utf16: 0, // TODO not implemented yet | 331 | text.replace_range(range, &edit.insert); |
327 | } | 332 | } |
333 | |||
334 | text | ||
328 | } | 335 | } |
329 | 336 | ||
330 | #[cfg(test)] | 337 | #[cfg(test)] |
@@ -354,46 +361,77 @@ mod test { | |||
354 | .boxed() | 361 | .boxed() |
355 | } | 362 | } |
356 | 363 | ||
357 | fn edit_text(pre_edit_text: &str, mut edits: Vec<AtomTextEdit>) -> String { | ||
358 | // apply edits ordered from last to first | ||
359 | // since they should not overlap we can just use start() | ||
360 | edits.sort_by_key(|x| -(x.delete.start().to_usize() as isize)); | ||
361 | |||
362 | let mut text = pre_edit_text.to_owned(); | ||
363 | |||
364 | for edit in &edits { | ||
365 | let range = edit.delete.start().to_usize()..edit.delete.end().to_usize(); | ||
366 | text.replace_range(range, &edit.insert); | ||
367 | } | ||
368 | |||
369 | text | ||
370 | } | ||
371 | |||
372 | fn translate_after_edit( | ||
373 | pre_edit_text: &str, | ||
374 | offset: TextUnit, | ||
375 | edits: Vec<AtomTextEdit>, | ||
376 | ) -> LineCol { | ||
377 | let text = edit_text(pre_edit_text, edits); | ||
378 | let line_index = LineIndex::new(&text); | ||
379 | line_index.line_col(offset) | ||
380 | } | ||
381 | |||
382 | proptest! { | 364 | proptest! { |
383 | #[test] | 365 | #[test] |
384 | fn test_translate_offset_with_edit(x in arb_text_with_offset_and_edits()) { | 366 | fn test_translate_offset_with_edit(x in arb_text_with_offset_and_edits()) { |
385 | let line_index = LineIndex::new(&x.text); | 367 | let line_index = LineIndex::new(&x.text); |
386 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); | 368 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); |
387 | let actual = translate_offset_with_edit(&line_index, x.offset, &x.edits); | 369 | let actual_lines = count_newlines(x.offset, &line_index, &x.edits); |
388 | assert_eq!(actual.line, expected.line); | 370 | assert_eq!(actual_lines, expected.line); |
389 | } | 371 | } |
390 | 372 | ||
391 | #[test] | 373 | #[test] |
392 | fn test_translate_offset_with_edit_alt(x in arb_text_with_offset_and_edits()) { | 374 | fn test_translate_offset_with_edit_alt(x in arb_text_with_offset_and_edits()) { |
393 | let line_index = LineIndex::new(&x.text); | 375 | let line_index = LineIndex::new(&x.text); |
394 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); | 376 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); |
395 | let actual_lines = count_newlines(x.offset, &line_index, &x.edits); | 377 | let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); |
396 | assert_eq!(actual_lines, expected.line); | 378 | assert_eq!(actual_lines, expected.line); |
397 | } | 379 | } |
398 | } | 380 | } |
381 | |||
382 | #[test] | ||
383 | fn test_translate_offset_with_edit_alt_1() { | ||
384 | let x = ArbTextWithOffsetAndEdits { | ||
385 | text: String::from("aA\n"), | ||
386 | offset: 2.into(), | ||
387 | edits: vec![AtomTextEdit::delete(TextRange::from_to(1.into(), 2.into()))], | ||
388 | }; | ||
389 | let line_index = LineIndex::new(&x.text); | ||
390 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); | ||
391 | let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); | ||
392 | assert_eq!(actual_lines, expected.line); | ||
393 | } | ||
394 | |||
395 | #[test] | ||
396 | fn test_translate_offset_with_edit_alt_2() { | ||
397 | let x = ArbTextWithOffsetAndEdits { | ||
398 | text: String::from("\nqꀸ#"), | ||
399 | offset: 5.into(), | ||
400 | edits: vec![AtomTextEdit::insert(1.into(), "\n".into())], | ||
401 | }; | ||
402 | let line_index = LineIndex::new(&x.text); | ||
403 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); | ||
404 | let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); | ||
405 | assert_eq!(actual_lines, expected.line); | ||
406 | } | ||
407 | |||
408 | #[test] | ||
409 | fn test_translate_offset_with_edit_alt_3() { | ||
410 | let x = ArbTextWithOffsetAndEdits { | ||
411 | text: String::from("\n\n\n"), | ||
412 | offset: 0.into(), | ||
413 | edits: vec![AtomTextEdit::delete(TextRange::from_to(0.into(), 2.into()))], | ||
414 | }; | ||
415 | let line_index = LineIndex::new(&x.text); | ||
416 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); | ||
417 | let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); | ||
418 | assert_eq!(actual_lines, expected.line); | ||
419 | } | ||
420 | |||
421 | #[test] | ||
422 | fn test_translate_offset_with_edit_alt_4() { | ||
423 | let x = ArbTextWithOffsetAndEdits { | ||
424 | text: String::from("☻54翑\"A"), | ||
425 | offset: 5.into(), | ||
426 | edits: vec![ | ||
427 | AtomTextEdit::delete(TextRange::from_to(0.into(), 8.into())), | ||
428 | AtomTextEdit::insert(9.into(), String::from("\n")), | ||
429 | ], | ||
430 | }; | ||
431 | let line_index = LineIndex::new(&x.text); | ||
432 | let expected = translate_after_edit(&x.text, x.offset, x.edits.clone()); | ||
433 | let actual_lines = count_newlines_alt(x.offset, &line_index, &x.edits); | ||
434 | assert_eq!(actual_lines, expected.line); | ||
435 | } | ||
436 | |||
399 | } | 437 | } |