aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
authorBernardo <[email protected]>2018-12-21 17:38:28 +0000
committerBernardo <[email protected]>2018-12-25 18:59:02 +0000
commita005d2a614031a18c9a5bf6557789a41f1b25c31 (patch)
tree517d8b6885ab5a4eacb1d3bc77266aeea14a9a85 /crates
parent7299df8409097de67647b371b81da7bcf49112e6 (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')
-rw-r--r--crates/ra_editor/src/line_index_utils.rs380
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 @@
1use ra_text_edit::{AtomTextEdit}; 1use ra_text_edit::AtomTextEdit;
2use ra_syntax::{TextUnit, TextRange}; 2use ra_syntax::{TextUnit, TextRange};
3use crate::{LineIndex, LineCol}; 3use crate::{LineIndex, LineCol};
4use superslice::Ext; 4use superslice::Ext;
@@ -24,41 +24,6 @@ impl<'a> Iterator for OffsetNewlineIter<'a> {
24 } 24 }
25} 25}
26 26
27#[derive(Debug, Clone, Copy, PartialEq)]
28enum TranslatedPos {
29 Before,
30 After,
31}
32
33/// None means it was deleted
34type TranslatedOffset = Option<(TranslatedPos, TextUnit)>;
35
36fn 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
48trait 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)]
63struct AltEdit<'a> { 28struct 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
159fn count_newlines(offset: TextUnit, line_index: &LineIndex, edits: &[AtomTextEdit]) -> u32 { 124pub 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
192struct TranslatedAtomEdit<'a> { 157#[derive(Debug)]
158enum NextNewlines<'a> {
159 Use,
160 ReplaceMany(OffsetNewlineIter<'a>),
161 AddMany(OffsetNewlineIter<'a>),
162}
163
164#[derive(Debug)]
165struct TranslatedEdit<'a> {
193 delete: TextRange, 166 delete: TextRange,
194 insert: &'a str, 167 insert: &'a str,
168 diff: i64,
195} 169}
196 170
197struct TranslatedNewlines<'a, T: TranslatedNewlineIterator> { 171struct 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
204impl<'a, T: TranslatedNewlineIterator> TranslatedNewlines<'a, T> { 177impl<'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
232impl<'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
261impl<'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
268impl<T: TranslatedNewlineIterator + ?Sized> TranslatedNewlineIterator for Box<T> { 246pub 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
277struct IteratorWrapper<T: Iterator<Item = TextUnit>>(T);
278 253
279impl<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
288impl<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
295fn 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
305pub fn translate_offset_with_edit( 311// for bench
306 pre_edit_index: &LineIndex, 312pub 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); 322fn 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}