tenant.openagents/omega

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