1use ordered_float::OrderedFloat;
2use rope::{Point, Rope, TextSummary};
3use std::collections::{BTreeSet, HashMap};
4use std::{
5 cmp,
6 fmt::{self, Debug},
7 ops::Range,
8};
9
10#[derive(Default)]
11struct Matrix {
12 cells: Vec<f64>,
13 rows: usize,
14 cols: usize,
15}
16
17impl Matrix {
18 fn new() -> Self {
19 Self {
20 cells: Vec::new(),
21 rows: 0,
22 cols: 0,
23 }
24 }
25
26 fn resize(&mut self, rows: usize, cols: usize) {
27 self.cells.resize(rows * cols, 0.);
28 self.rows = rows;
29 self.cols = cols;
30 }
31
32 fn swap_columns(&mut self, col1: usize, col2: usize) {
33 if col1 == col2 {
34 return;
35 }
36
37 if col1 >= self.cols {
38 panic!("column out of bounds");
39 }
40
41 if col2 >= self.cols {
42 panic!("column out of bounds");
43 }
44
45 unsafe {
46 let ptr = self.cells.as_mut_ptr();
47 std::ptr::swap_nonoverlapping(
48 ptr.add(col1 * self.rows),
49 ptr.add(col2 * self.rows),
50 self.rows,
51 );
52 }
53 }
54
55 fn get(&self, row: usize, col: usize) -> f64 {
56 if row >= self.rows {
57 panic!("row out of bounds")
58 }
59
60 if col >= self.cols {
61 panic!("column out of bounds")
62 }
63 self.cells[col * self.rows + row]
64 }
65
66 fn set(&mut self, row: usize, col: usize, value: f64) {
67 if row >= self.rows {
68 panic!("row out of bounds")
69 }
70
71 if col >= self.cols {
72 panic!("column out of bounds")
73 }
74
75 self.cells[col * self.rows + row] = value;
76 }
77}
78
79impl Debug for Matrix {
80 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
81 writeln!(f)?;
82 for i in 0..self.rows {
83 for j in 0..self.cols {
84 write!(f, "{:5}", self.get(i, j))?;
85 }
86 writeln!(f)?;
87 }
88 Ok(())
89 }
90}
91
92#[derive(Debug, Clone)]
93pub enum CharOperation {
94 Insert { text: String },
95 Delete { bytes: usize },
96 Keep { bytes: usize },
97}
98
99#[derive(Default)]
100pub struct StreamingDiff {
101 old: Vec<char>,
102 new: Vec<char>,
103 scores: Matrix,
104 old_text_ix: usize,
105 new_text_ix: usize,
106 equal_runs: HashMap<(usize, usize), u32>,
107}
108
109impl StreamingDiff {
110 const INSERTION_SCORE: f64 = -1.;
111 const DELETION_SCORE: f64 = -20.;
112 const EQUALITY_BASE: f64 = 1.8;
113 const MAX_EQUALITY_EXPONENT: i32 = 16;
114
115 pub fn new(old: String) -> Self {
116 let old = old.chars().collect::<Vec<_>>();
117 let mut scores = Matrix::new();
118 scores.resize(old.len() + 1, 1);
119 for i in 0..=old.len() {
120 scores.set(i, 0, i as f64 * Self::DELETION_SCORE);
121 }
122 Self {
123 old,
124 new: Vec::new(),
125 scores,
126 old_text_ix: 0,
127 new_text_ix: 0,
128 equal_runs: Default::default(),
129 }
130 }
131
132 pub fn push_new(&mut self, text: &str) -> Vec<CharOperation> {
133 self.new.extend(text.chars());
134 self.scores.swap_columns(0, self.scores.cols - 1);
135 self.scores
136 .resize(self.old.len() + 1, self.new.len() - self.new_text_ix + 1);
137 self.equal_runs.retain(|(_i, j), _| *j == self.new_text_ix);
138
139 for j in self.new_text_ix + 1..=self.new.len() {
140 let relative_j = j - self.new_text_ix;
141
142 self.scores
143 .set(0, relative_j, j as f64 * Self::INSERTION_SCORE);
144 for i in 1..=self.old.len() {
145 let insertion_score = self.scores.get(i, relative_j - 1) + Self::INSERTION_SCORE;
146 let deletion_score = self.scores.get(i - 1, relative_j) + Self::DELETION_SCORE;
147 let equality_score = if self.old[i - 1] == self.new[j - 1] {
148 let mut equal_run = self.equal_runs.get(&(i - 1, j - 1)).copied().unwrap_or(0);
149 equal_run += 1;
150 self.equal_runs.insert((i, j), equal_run);
151
152 let exponent = cmp::min(equal_run as i32 / 4, Self::MAX_EQUALITY_EXPONENT);
153 self.scores.get(i - 1, relative_j - 1) + Self::EQUALITY_BASE.powi(exponent)
154 } else {
155 f64::NEG_INFINITY
156 };
157
158 let score = insertion_score.max(deletion_score).max(equality_score);
159 self.scores.set(i, relative_j, score);
160 }
161 }
162
163 let mut max_score = f64::NEG_INFINITY;
164 let mut next_old_text_ix = self.old_text_ix;
165 let next_new_text_ix = self.new.len();
166 for i in self.old_text_ix..=self.old.len() {
167 let score = self.scores.get(i, next_new_text_ix - self.new_text_ix);
168 if score > max_score {
169 max_score = score;
170 next_old_text_ix = i;
171 }
172 }
173
174 let hunks = self.backtrack(next_old_text_ix, next_new_text_ix);
175 self.old_text_ix = next_old_text_ix;
176 self.new_text_ix = next_new_text_ix;
177 hunks
178 }
179
180 fn backtrack(&self, old_text_ix: usize, new_text_ix: usize) -> Vec<CharOperation> {
181 let mut pending_insert: Option<Range<usize>> = None;
182 let mut hunks = Vec::new();
183 let mut i = old_text_ix;
184 let mut j = new_text_ix;
185 while (i, j) != (self.old_text_ix, self.new_text_ix) {
186 let insertion_score = if j > self.new_text_ix {
187 Some((i, j - 1))
188 } else {
189 None
190 };
191 let deletion_score = if i > self.old_text_ix {
192 Some((i - 1, j))
193 } else {
194 None
195 };
196 let equality_score = if i > self.old_text_ix && j > self.new_text_ix {
197 if self.old[i - 1] == self.new[j - 1] {
198 Some((i - 1, j - 1))
199 } else {
200 None
201 }
202 } else {
203 None
204 };
205
206 let (prev_i, prev_j) = [insertion_score, deletion_score, equality_score]
207 .iter()
208 .max_by_key(|cell| {
209 cell.map(|(i, j)| OrderedFloat(self.scores.get(i, j - self.new_text_ix)))
210 })
211 .unwrap()
212 .unwrap();
213
214 if prev_i == i && prev_j == j - 1 {
215 if let Some(pending_insert) = pending_insert.as_mut() {
216 pending_insert.start = prev_j;
217 } else {
218 pending_insert = Some(prev_j..j);
219 }
220 } else {
221 if let Some(range) = pending_insert.take() {
222 hunks.push(CharOperation::Insert {
223 text: self.new[range].iter().collect(),
224 });
225 }
226
227 let char_len = self.old[i - 1].len_utf8();
228 if prev_i == i - 1 && prev_j == j {
229 if let Some(CharOperation::Delete { bytes: len }) = hunks.last_mut() {
230 *len += char_len;
231 } else {
232 hunks.push(CharOperation::Delete { bytes: char_len })
233 }
234 } else if let Some(CharOperation::Keep { bytes: len }) = hunks.last_mut() {
235 *len += char_len;
236 } else {
237 hunks.push(CharOperation::Keep { bytes: char_len })
238 }
239 }
240
241 i = prev_i;
242 j = prev_j;
243 }
244
245 if let Some(range) = pending_insert.take() {
246 hunks.push(CharOperation::Insert {
247 text: self.new[range].iter().collect(),
248 });
249 }
250
251 hunks.reverse();
252 hunks
253 }
254
255 pub fn finish(self) -> Vec<CharOperation> {
256 self.backtrack(self.old.len(), self.new.len())
257 }
258}
259
260#[derive(Debug, Clone, PartialEq)]
261pub enum LineOperation {
262 Insert { lines: u32 },
263 Delete { lines: u32 },
264 Keep { lines: u32 },
265}
266
267#[derive(Debug, Default)]
268pub struct LineDiff {
269 inserted_newline_at_end: bool,
270 /// The extent of kept and deleted text.
271 old_end: Point,
272 /// The extent of kept and inserted text.
273 new_end: Point,
274 /// Deleted rows, expressed in terms of the old text.
275 deleted_rows: BTreeSet<u32>,
276 /// Inserted rows, expressed in terms of the new text.
277 inserted_rows: BTreeSet<u32>,
278 buffered_insert: String,
279 /// After deleting a newline, we buffer deletion until we keep or insert a character.
280 buffered_delete: usize,
281}
282
283impl LineDiff {
284 pub fn push_char_operations<'a>(
285 &mut self,
286 operations: impl IntoIterator<Item = &'a CharOperation>,
287 old_text: &Rope,
288 ) {
289 for operation in operations {
290 self.push_char_operation(operation, old_text);
291 }
292 }
293
294 pub fn push_char_operation(&mut self, operation: &CharOperation, old_text: &Rope) {
295 match operation {
296 CharOperation::Insert { text } => {
297 self.flush_delete(old_text);
298
299 if is_line_start(self.old_end) {
300 if let Some(newline_ix) = text.rfind('\n') {
301 let (prefix, suffix) = text.split_at(newline_ix + 1);
302 self.buffered_insert.push_str(prefix);
303 self.flush_insert(old_text);
304 self.buffered_insert.push_str(suffix);
305 } else {
306 self.buffered_insert.push_str(text);
307 }
308 } else {
309 self.buffered_insert.push_str(text);
310 if !text.ends_with('\n') {
311 self.flush_insert(old_text);
312 }
313 }
314 }
315 CharOperation::Delete { bytes } => {
316 self.buffered_delete += bytes;
317
318 let common_suffix_len = self.trim_buffered_end(old_text);
319 self.flush_insert(old_text);
320
321 if common_suffix_len > 0 || !is_line_end(self.old_end, old_text) {
322 self.flush_delete(old_text);
323 self.keep(common_suffix_len, old_text);
324 }
325 }
326 CharOperation::Keep { bytes } => {
327 self.flush_delete(old_text);
328 self.flush_insert(old_text);
329 self.keep(*bytes, old_text);
330 }
331 }
332 }
333
334 fn flush_insert(&mut self, old_text: &Rope) {
335 if self.buffered_insert.is_empty() {
336 return;
337 }
338
339 let new_start = self.new_end;
340 let lines = TextSummary::from(self.buffered_insert.as_str()).lines;
341 self.new_end += lines;
342
343 if is_line_start(self.old_end) {
344 if self.new_end.column == 0 {
345 self.inserted_rows.extend(new_start.row..self.new_end.row);
346 } else {
347 self.deleted_rows.insert(self.old_end.row);
348 self.inserted_rows.extend(new_start.row..=self.new_end.row);
349 }
350 } else if is_line_end(self.old_end, old_text) {
351 if self.buffered_insert.starts_with('\n') {
352 self.inserted_rows
353 .extend(new_start.row + 1..=self.new_end.row);
354 self.inserted_newline_at_end = true;
355 } else {
356 if !self.inserted_newline_at_end {
357 self.deleted_rows.insert(self.old_end.row);
358 }
359 self.inserted_rows.extend(new_start.row..=self.new_end.row);
360 }
361 } else {
362 self.deleted_rows.insert(self.old_end.row);
363 self.inserted_rows.extend(new_start.row..=self.new_end.row);
364 }
365
366 self.buffered_insert.clear();
367 }
368
369 fn flush_delete(&mut self, old_text: &Rope) {
370 if self.buffered_delete == 0 {
371 return;
372 }
373
374 let old_start = self.old_end;
375 self.old_end =
376 old_text.offset_to_point(old_text.point_to_offset(self.old_end) + self.buffered_delete);
377
378 if is_line_end(old_start, old_text) && is_line_end(self.old_end, old_text) {
379 self.deleted_rows
380 .extend(old_start.row + 1..=self.old_end.row);
381 } else if is_line_start(old_start)
382 && (is_line_start(self.old_end) && self.old_end < old_text.max_point())
383 && self.new_end.column == 0
384 {
385 self.deleted_rows.extend(old_start.row..self.old_end.row);
386 } else {
387 self.inserted_rows.insert(self.new_end.row);
388 self.deleted_rows.extend(old_start.row..=self.old_end.row);
389 }
390
391 self.inserted_newline_at_end = false;
392 self.buffered_delete = 0;
393 }
394
395 fn keep(&mut self, bytes: usize, old_text: &Rope) {
396 if bytes == 0 {
397 return;
398 }
399
400 let lines =
401 old_text.offset_to_point(old_text.point_to_offset(self.old_end) + bytes) - self.old_end;
402 self.old_end += lines;
403 self.new_end += lines;
404 self.inserted_newline_at_end = false;
405 }
406
407 fn trim_buffered_end(&mut self, old_text: &Rope) -> usize {
408 let old_start_offset = old_text.point_to_offset(self.old_end);
409 let old_end_offset = old_start_offset + self.buffered_delete;
410
411 let new_chars = self.buffered_insert.chars().rev();
412 let old_chars = old_text
413 .chunks_in_range(old_start_offset..old_end_offset)
414 .flat_map(|chunk| chunk.chars().rev());
415
416 let mut common_suffix_len = 0;
417 for (new_ch, old_ch) in new_chars.zip(old_chars) {
418 if new_ch == old_ch {
419 common_suffix_len += new_ch.len_utf8();
420 } else {
421 break;
422 }
423 }
424
425 self.buffered_delete -= common_suffix_len;
426 self.buffered_insert
427 .truncate(self.buffered_insert.len() - common_suffix_len);
428
429 common_suffix_len
430 }
431
432 pub fn finish(&mut self, old_text: &Rope) {
433 self.flush_insert(old_text);
434 self.flush_delete(old_text);
435
436 let old_start = self.old_end;
437 self.old_end = old_text.max_point();
438 self.new_end += self.old_end - old_start;
439 }
440
441 pub fn line_operations(&self) -> Vec<LineOperation> {
442 let mut ops = Vec::new();
443 let mut deleted_rows = self.deleted_rows.iter().copied().peekable();
444 let mut inserted_rows = self.inserted_rows.iter().copied().peekable();
445 let mut old_row = 0;
446 let mut new_row = 0;
447
448 while deleted_rows.peek().is_some() || inserted_rows.peek().is_some() {
449 // Check for a run of deleted lines at current old row.
450 if Some(old_row) == deleted_rows.peek().copied() {
451 if let Some(LineOperation::Delete { lines }) = ops.last_mut() {
452 *lines += 1;
453 } else {
454 ops.push(LineOperation::Delete { lines: 1 });
455 }
456 old_row += 1;
457 deleted_rows.next();
458 } else if Some(new_row) == inserted_rows.peek().copied() {
459 if let Some(LineOperation::Insert { lines }) = ops.last_mut() {
460 *lines += 1;
461 } else {
462 ops.push(LineOperation::Insert { lines: 1 });
463 }
464 new_row += 1;
465 inserted_rows.next();
466 } else {
467 // Keep lines until the next deletion, insertion, or the end of the old text.
468 let lines_to_next_deletion = inserted_rows
469 .peek()
470 .copied()
471 .unwrap_or(self.new_end.row + 1)
472 - new_row;
473 let lines_to_next_insertion =
474 deleted_rows.peek().copied().unwrap_or(self.old_end.row + 1) - old_row;
475 let kept_lines =
476 cmp::max(1, cmp::min(lines_to_next_insertion, lines_to_next_deletion));
477 if kept_lines > 0 {
478 ops.push(LineOperation::Keep { lines: kept_lines });
479 old_row += kept_lines;
480 new_row += kept_lines;
481 }
482 }
483 }
484
485 if old_row < self.old_end.row + 1 {
486 ops.push(LineOperation::Keep {
487 lines: self.old_end.row + 1 - old_row,
488 });
489 }
490
491 ops
492 }
493}
494
495fn is_line_start(point: Point) -> bool {
496 point.column == 0
497}
498
499fn is_line_end(point: Point, text: &Rope) -> bool {
500 text.line_len(point.row) == point.column
501}
502
503#[cfg(test)]
504mod tests {
505 use super::*;
506 use gpui::BackgroundExecutor;
507 use rand::prelude::*;
508 use std::env;
509
510 #[gpui::test]
511 fn test_delete_first_of_two_lines(cx: &mut gpui::TestAppContext) {
512 let old_text = "aaaa\nbbbb";
513 let char_ops = vec![
514 CharOperation::Delete { bytes: 5 },
515 CharOperation::Keep { bytes: 4 },
516 ];
517 let expected_line_ops = vec![
518 LineOperation::Delete { lines: 1 },
519 LineOperation::Keep { lines: 1 },
520 ];
521 let new_text = apply_char_operations(old_text, &char_ops);
522 assert_eq!(
523 new_text,
524 apply_line_operations(old_text, &new_text, &expected_line_ops)
525 );
526
527 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
528 assert_eq!(line_ops, expected_line_ops);
529 }
530
531 #[gpui::test]
532 fn test_delete_second_of_two_lines(cx: &mut gpui::TestAppContext) {
533 let old_text = "aaaa\nbbbb";
534 let char_ops = vec![
535 CharOperation::Keep { bytes: 5 },
536 CharOperation::Delete { bytes: 4 },
537 ];
538 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
539 assert_eq!(
540 line_ops,
541 vec![
542 LineOperation::Keep { lines: 1 },
543 LineOperation::Delete { lines: 1 },
544 LineOperation::Insert { lines: 1 }
545 ]
546 );
547 let new_text = apply_char_operations(old_text, &char_ops);
548 assert_eq!(
549 new_text,
550 apply_line_operations(old_text, &new_text, &line_ops)
551 );
552 }
553
554 #[gpui::test]
555 fn test_add_new_line(cx: &mut gpui::TestAppContext) {
556 let old_text = "aaaa\nbbbb";
557 let char_ops = vec![
558 CharOperation::Keep { bytes: 9 },
559 CharOperation::Insert {
560 text: "\ncccc".into(),
561 },
562 ];
563 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
564 assert_eq!(
565 line_ops,
566 vec![
567 LineOperation::Keep { lines: 2 },
568 LineOperation::Insert { lines: 1 }
569 ]
570 );
571 let new_text = apply_char_operations(old_text, &char_ops);
572 assert_eq!(
573 new_text,
574 apply_line_operations(old_text, &new_text, &line_ops)
575 );
576 }
577
578 #[gpui::test]
579 fn test_delete_line_in_middle(cx: &mut gpui::TestAppContext) {
580 let old_text = "aaaa\nbbbb\ncccc";
581 let char_ops = vec![
582 CharOperation::Keep { bytes: 5 },
583 CharOperation::Delete { bytes: 5 },
584 CharOperation::Keep { bytes: 4 },
585 ];
586 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
587 assert_eq!(
588 line_ops,
589 vec![
590 LineOperation::Keep { lines: 1 },
591 LineOperation::Delete { lines: 1 },
592 LineOperation::Keep { lines: 1 }
593 ]
594 );
595 let new_text = apply_char_operations(old_text, &char_ops);
596 assert_eq!(
597 new_text,
598 apply_line_operations(old_text, &new_text, &line_ops)
599 );
600 }
601
602 #[gpui::test]
603 fn test_replace_line(cx: &mut gpui::TestAppContext) {
604 let old_text = "aaaa\nbbbb\ncccc";
605 let char_ops = vec![
606 CharOperation::Keep { bytes: 5 },
607 CharOperation::Delete { bytes: 4 },
608 CharOperation::Insert {
609 text: "BBBB".into(),
610 },
611 CharOperation::Keep { bytes: 5 },
612 ];
613 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
614 assert_eq!(
615 line_ops,
616 vec![
617 LineOperation::Keep { lines: 1 },
618 LineOperation::Delete { lines: 1 },
619 LineOperation::Insert { lines: 1 },
620 LineOperation::Keep { lines: 1 }
621 ]
622 );
623 let new_text = apply_char_operations(old_text, &char_ops);
624 assert_eq!(
625 new_text,
626 apply_line_operations(old_text, &new_text, &line_ops)
627 );
628 }
629
630 #[gpui::test]
631 fn test_multiple_edits_on_different_lines(cx: &mut gpui::TestAppContext) {
632 let old_text = "aaaa\nbbbb\ncccc\ndddd";
633 let char_ops = vec![
634 CharOperation::Insert { text: "A".into() },
635 CharOperation::Keep { bytes: 9 },
636 CharOperation::Delete { bytes: 5 },
637 CharOperation::Keep { bytes: 4 },
638 CharOperation::Insert {
639 text: "\nEEEE".into(),
640 },
641 ];
642 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
643 assert_eq!(
644 line_ops,
645 vec![
646 LineOperation::Delete { lines: 1 },
647 LineOperation::Insert { lines: 1 },
648 LineOperation::Keep { lines: 1 },
649 LineOperation::Delete { lines: 2 },
650 LineOperation::Insert { lines: 2 },
651 ]
652 );
653 let new_text = apply_char_operations(old_text, &char_ops);
654 assert_eq!(
655 new_text,
656 apply_line_operations(old_text, &new_text, &line_ops)
657 );
658 }
659
660 #[gpui::test]
661 fn test_edit_at_end_of_line(cx: &mut gpui::TestAppContext) {
662 let old_text = "aaaa\nbbbb\ncccc";
663 let char_ops = vec![
664 CharOperation::Keep { bytes: 4 },
665 CharOperation::Insert { text: "A".into() },
666 CharOperation::Keep { bytes: 10 },
667 ];
668 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
669 assert_eq!(
670 line_ops,
671 vec![
672 LineOperation::Delete { lines: 1 },
673 LineOperation::Insert { lines: 1 },
674 LineOperation::Keep { lines: 2 }
675 ]
676 );
677 let new_text = apply_char_operations(old_text, &char_ops);
678 assert_eq!(
679 new_text,
680 apply_line_operations(old_text, &new_text, &line_ops)
681 );
682 }
683
684 #[gpui::test]
685 fn test_insert_newline_character(cx: &mut gpui::TestAppContext) {
686 let old_text = "aaaabbbb";
687 let char_ops = vec![
688 CharOperation::Keep { bytes: 4 },
689 CharOperation::Insert { text: "\n".into() },
690 CharOperation::Keep { bytes: 4 },
691 ];
692 let new_text = apply_char_operations(old_text, &char_ops);
693 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
694 assert_eq!(
695 line_ops,
696 vec![
697 LineOperation::Delete { lines: 1 },
698 LineOperation::Insert { lines: 2 }
699 ]
700 );
701 assert_eq!(
702 new_text,
703 apply_line_operations(old_text, &new_text, &line_ops)
704 );
705 }
706
707 #[gpui::test]
708 fn test_insert_newline_at_beginning(cx: &mut gpui::TestAppContext) {
709 let old_text = "aaaa\nbbbb";
710 let char_ops = vec![
711 CharOperation::Insert { text: "\n".into() },
712 CharOperation::Keep { bytes: 9 },
713 ];
714 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
715 assert_eq!(
716 line_ops,
717 vec![
718 LineOperation::Insert { lines: 1 },
719 LineOperation::Keep { lines: 2 }
720 ]
721 );
722 let new_text = apply_char_operations(old_text, &char_ops);
723 assert_eq!(
724 new_text,
725 apply_line_operations(old_text, &new_text, &line_ops)
726 );
727 }
728
729 #[gpui::test]
730 fn test_delete_newline(cx: &mut gpui::TestAppContext) {
731 let old_text = "aaaa\nbbbb";
732 let char_ops = vec![
733 CharOperation::Keep { bytes: 4 },
734 CharOperation::Delete { bytes: 1 },
735 CharOperation::Keep { bytes: 4 },
736 ];
737 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
738 assert_eq!(
739 line_ops,
740 vec![
741 LineOperation::Delete { lines: 2 },
742 LineOperation::Insert { lines: 1 }
743 ]
744 );
745
746 let new_text = apply_char_operations(old_text, &char_ops);
747 assert_eq!(
748 new_text,
749 apply_line_operations(old_text, &new_text, &line_ops)
750 );
751 }
752
753 #[gpui::test]
754 fn test_insert_multiple_newlines(cx: &mut gpui::TestAppContext) {
755 let old_text = "aaaa\nbbbb";
756 let char_ops = vec![
757 CharOperation::Keep { bytes: 5 },
758 CharOperation::Insert {
759 text: "\n\n".into(),
760 },
761 CharOperation::Keep { bytes: 4 },
762 ];
763 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
764 assert_eq!(
765 line_ops,
766 vec![
767 LineOperation::Keep { lines: 1 },
768 LineOperation::Insert { lines: 2 },
769 LineOperation::Keep { lines: 1 }
770 ]
771 );
772 let new_text = apply_char_operations(old_text, &char_ops);
773 assert_eq!(
774 new_text,
775 apply_line_operations(old_text, &new_text, &line_ops)
776 );
777 }
778
779 #[gpui::test]
780 fn test_delete_multiple_newlines(cx: &mut gpui::TestAppContext) {
781 let old_text = "aaaa\n\n\nbbbb";
782 let char_ops = vec![
783 CharOperation::Keep { bytes: 5 },
784 CharOperation::Delete { bytes: 2 },
785 CharOperation::Keep { bytes: 4 },
786 ];
787 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
788 assert_eq!(
789 line_ops,
790 vec![
791 LineOperation::Keep { lines: 1 },
792 LineOperation::Delete { lines: 2 },
793 LineOperation::Keep { lines: 1 }
794 ]
795 );
796 let new_text = apply_char_operations(old_text, &char_ops);
797 assert_eq!(
798 new_text,
799 apply_line_operations(old_text, &new_text, &line_ops)
800 );
801 }
802
803 #[gpui::test]
804 fn test_complex_scenario(cx: &mut gpui::TestAppContext) {
805 let old_text = "line1\nline2\nline3\nline4";
806 let char_ops = vec![
807 CharOperation::Keep { bytes: 6 },
808 CharOperation::Insert {
809 text: "inserted\n".into(),
810 },
811 CharOperation::Delete { bytes: 6 },
812 CharOperation::Keep { bytes: 5 },
813 CharOperation::Insert {
814 text: "\nnewline".into(),
815 },
816 CharOperation::Keep { bytes: 6 },
817 ];
818 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
819 assert_eq!(
820 line_ops,
821 vec![
822 LineOperation::Keep { lines: 1 },
823 LineOperation::Delete { lines: 1 },
824 LineOperation::Insert { lines: 1 },
825 LineOperation::Keep { lines: 1 },
826 LineOperation::Insert { lines: 1 },
827 LineOperation::Keep { lines: 1 }
828 ]
829 );
830 let new_text = apply_char_operations(old_text, &char_ops);
831 assert_eq!(new_text, "line1\ninserted\nline3\nnewline\nline4");
832 assert_eq!(
833 apply_line_operations(old_text, &new_text, &line_ops),
834 new_text,
835 );
836 }
837
838 #[gpui::test]
839 fn test_cleaning_up_common_suffix(cx: &mut gpui::TestAppContext) {
840 let old_text = concat!(
841 " for y in 0..size.y() {\n",
842 " let a = 10;\n",
843 " let b = 20;\n",
844 " }",
845 );
846 let char_ops = [
847 CharOperation::Keep { bytes: 8 },
848 CharOperation::Insert { text: "let".into() },
849 CharOperation::Insert {
850 text: " mut".into(),
851 },
852 CharOperation::Insert { text: " y".into() },
853 CharOperation::Insert { text: " =".into() },
854 CharOperation::Insert { text: " 0".into() },
855 CharOperation::Insert { text: ";".into() },
856 CharOperation::Insert { text: "\n".into() },
857 CharOperation::Insert {
858 text: " while".into(),
859 },
860 CharOperation::Insert { text: " y".into() },
861 CharOperation::Insert {
862 text: " < size".into(),
863 },
864 CharOperation::Insert { text: ".".into() },
865 CharOperation::Insert { text: "y".into() },
866 CharOperation::Insert { text: "()".into() },
867 CharOperation::Insert { text: " {".into() },
868 CharOperation::Insert { text: "\n".into() },
869 CharOperation::Delete { bytes: 23 },
870 CharOperation::Keep { bytes: 23 },
871 CharOperation::Keep { bytes: 1 },
872 CharOperation::Keep { bytes: 23 },
873 CharOperation::Keep { bytes: 1 },
874 CharOperation::Keep { bytes: 8 },
875 CharOperation::Insert {
876 text: " y".into(),
877 },
878 CharOperation::Insert { text: " +=".into() },
879 CharOperation::Insert { text: " 1".into() },
880 CharOperation::Insert { text: ";".into() },
881 CharOperation::Insert { text: "\n".into() },
882 CharOperation::Insert {
883 text: " ".into(),
884 },
885 CharOperation::Keep { bytes: 1 },
886 ];
887 let line_ops = char_ops_to_line_ops(old_text, &char_ops, cx.background_executor());
888 assert_eq!(
889 line_ops,
890 vec![
891 LineOperation::Delete { lines: 1 },
892 LineOperation::Insert { lines: 2 },
893 LineOperation::Keep { lines: 2 },
894 LineOperation::Delete { lines: 1 },
895 LineOperation::Insert { lines: 2 },
896 ]
897 );
898 let new_text = apply_char_operations(old_text, &char_ops);
899 assert_eq!(
900 new_text,
901 apply_line_operations(old_text, &new_text, &line_ops)
902 );
903 }
904
905 #[gpui::test]
906 fn test_random_diffs(cx: &mut gpui::TestAppContext) {
907 random_test(|mut rng| {
908 let old_text_len = env::var("OLD_TEXT_LEN")
909 .map(|i| i.parse().expect("invalid `OLD_TEXT_LEN` variable"))
910 .unwrap_or(10);
911
912 let old = random_text(&mut rng, old_text_len);
913 println!("old text: {:?}", old);
914
915 let new = randomly_edit(&old, &mut rng);
916 println!("new text: {:?}", new);
917
918 let char_operations = random_streaming_diff(&mut rng, &old, &new);
919 println!("char operations: {:?}", char_operations);
920
921 // Use apply_char_operations to verify the result
922 let patched = apply_char_operations(&old, &char_operations);
923 assert_eq!(patched, new);
924
925 // Test char_ops_to_line_ops
926 let line_ops = char_ops_to_line_ops(&old, &char_operations, cx.background_executor());
927 println!("line operations: {:?}", line_ops);
928 let patched = apply_line_operations(&old, &new, &line_ops);
929 assert_eq!(patched, new);
930 });
931 }
932
933 fn char_ops_to_line_ops(
934 old_text: &str,
935 char_ops: &[CharOperation],
936 executor: &BackgroundExecutor,
937 ) -> Vec<LineOperation> {
938 let old_rope = Rope::from_str(old_text, executor);
939 let mut diff = LineDiff::default();
940 for op in char_ops {
941 diff.push_char_operation(op, &old_rope);
942 }
943 diff.finish(&old_rope);
944 diff.line_operations()
945 }
946
947 fn random_streaming_diff(rng: &mut impl Rng, old: &str, new: &str) -> Vec<CharOperation> {
948 let mut diff = StreamingDiff::new(old.to_string());
949 let mut char_operations = Vec::new();
950 let mut new_len = 0;
951
952 while new_len < new.len() {
953 let mut chunk_len = rng.random_range(1..=new.len() - new_len);
954 while !new.is_char_boundary(new_len + chunk_len) {
955 chunk_len += 1;
956 }
957 let chunk = &new[new_len..new_len + chunk_len];
958 let new_hunks = diff.push_new(chunk);
959 char_operations.extend(new_hunks);
960 new_len += chunk_len;
961 }
962
963 char_operations.extend(diff.finish());
964 char_operations
965 }
966
967 fn random_test<F>(mut test_fn: F)
968 where
969 F: FnMut(StdRng),
970 {
971 let iterations = env::var("ITERATIONS")
972 .map(|i| i.parse().expect("invalid `ITERATIONS` variable"))
973 .unwrap_or(100);
974
975 let seed: u64 = env::var("SEED")
976 .map(|s| s.parse().expect("invalid `SEED` variable"))
977 .unwrap_or(0);
978
979 println!(
980 "Running test with {} iterations and seed {}",
981 iterations, seed
982 );
983
984 for i in 0..iterations {
985 println!("Iteration {}", i + 1);
986 let rng = StdRng::seed_from_u64(seed + i);
987 test_fn(rng);
988 }
989 }
990
991 fn apply_line_operations(old_text: &str, new_text: &str, line_ops: &[LineOperation]) -> String {
992 let mut result: Vec<&str> = Vec::new();
993
994 let old_lines: Vec<&str> = old_text.split('\n').collect();
995 let new_lines: Vec<&str> = new_text.split('\n').collect();
996 let mut old_start = 0_usize;
997 let mut new_start = 0_usize;
998
999 for op in line_ops {
1000 match op {
1001 LineOperation::Keep { lines } => {
1002 let old_end = old_start + *lines as usize;
1003 result.extend(&old_lines[old_start..old_end]);
1004 old_start = old_end;
1005 new_start += *lines as usize;
1006 }
1007 LineOperation::Delete { lines } => {
1008 old_start += *lines as usize;
1009 }
1010 LineOperation::Insert { lines } => {
1011 let new_end = new_start + *lines as usize;
1012 result.extend(&new_lines[new_start..new_end]);
1013 new_start = new_end;
1014 }
1015 }
1016 }
1017
1018 result.join("\n")
1019 }
1020
1021 #[test]
1022 fn test_apply_char_operations() {
1023 let old_text = "Hello, world!";
1024 let char_ops = vec![
1025 CharOperation::Keep { bytes: 7 },
1026 CharOperation::Delete { bytes: 5 },
1027 CharOperation::Insert {
1028 text: "Rust".to_string(),
1029 },
1030 CharOperation::Keep { bytes: 1 },
1031 ];
1032 let result = apply_char_operations(old_text, &char_ops);
1033 assert_eq!(result, "Hello, Rust!");
1034 }
1035
1036 fn random_text(rng: &mut impl Rng, length: usize) -> String {
1037 util::RandomCharIter::new(rng).take(length).collect()
1038 }
1039
1040 fn randomly_edit(text: &str, rng: &mut impl Rng) -> String {
1041 let mut result = String::from(text);
1042 let edit_count = rng.random_range(1..=5);
1043
1044 fn random_char_range(text: &str, rng: &mut impl Rng) -> (usize, usize) {
1045 let mut start = rng.random_range(0..=text.len());
1046 while !text.is_char_boundary(start) {
1047 start -= 1;
1048 }
1049 let mut end = rng.random_range(start..=text.len());
1050 while !text.is_char_boundary(end) {
1051 end += 1;
1052 }
1053 (start, end)
1054 }
1055
1056 for _ in 0..edit_count {
1057 match rng.random_range(0..3) {
1058 0 => {
1059 // Insert
1060 let (pos, _) = random_char_range(&result, rng);
1061 let insert_len = rng.random_range(1..=5);
1062 let insert_text: String = random_text(rng, insert_len);
1063 result.insert_str(pos, &insert_text);
1064 }
1065 1 => {
1066 // Delete
1067 if !result.is_empty() {
1068 let (start, end) = random_char_range(&result, rng);
1069 result.replace_range(start..end, "");
1070 }
1071 }
1072 2 => {
1073 // Replace
1074 if !result.is_empty() {
1075 let (start, end) = random_char_range(&result, rng);
1076 let replace_len = end - start;
1077 let replace_text: String = random_text(rng, replace_len);
1078 result.replace_range(start..end, &replace_text);
1079 }
1080 }
1081 _ => unreachable!(),
1082 }
1083 }
1084
1085 result
1086 }
1087
1088 fn apply_char_operations(old_text: &str, char_ops: &[CharOperation]) -> String {
1089 let mut result = String::new();
1090 let mut old_ix = 0;
1091
1092 for operation in char_ops {
1093 match operation {
1094 CharOperation::Keep { bytes } => {
1095 result.push_str(&old_text[old_ix..old_ix + bytes]);
1096 old_ix += bytes;
1097 }
1098 CharOperation::Delete { bytes } => {
1099 old_ix += bytes;
1100 }
1101 CharOperation::Insert { text } => {
1102 result.push_str(text);
1103 }
1104 }
1105 }
1106
1107 result
1108 }
1109}