path: root/src/edits.rs

use crate::edits::line_pair::LinePair;

/*
  Consider minus line m and paired plus line p, respectively.  The following cases exist:

  1. Whitespace deleted at line beginning.
     => The deleted section is highlighted in m; p is unstyled.

  2. Whitespace inserted at line beginning.
     => The inserted section is highlighted in p; m is unstyled.

  3. An internal section of the line containing a non-whitespace character has been deleted.
     => The deleted section is highlighted in m; p is unstyled.

  4. An internal section of the line containing a non-whitespace character has been changed.
     => The original section is highlighted in m; the replacement is highlighted in p.

  5. An internal section of the line containing a non-whitespace character has been inserted.
     => The inserted section is highlighted in p; m is unstyled.

  Note that whitespace can be neither deleted nor inserted at the end of the line: the line by
  definition has no trailing whitespace.
*/

type AnnotatedLine<'a, EditOperation> = Vec<(EditOperation, &'a str)>;

/// Infer the edit operations responsible for the differences between a collection of old and new
/// lines. Return the input minus and plus lines, in annotated form.
pub fn infer_edits<'a, EditOperation>(
    minus_lines: &'a Vec<String>,
    plus_lines: &'a Vec<String>,
    non_deletion: EditOperation,
    deletion: EditOperation,
    non_insertion: EditOperation,
    insertion: EditOperation,
    distance_threshold: f64,
) -> (
    Vec<AnnotatedLine<'a, EditOperation>>,
    Vec<AnnotatedLine<'a, EditOperation>>,
)
where
    EditOperation: Copy,
{
    let mut annotated_minus_lines = Vec::<AnnotatedLine<EditOperation>>::new();
    let mut annotated_plus_lines = Vec::<AnnotatedLine<EditOperation>>::new();

    let mut emitted = 0; // plus lines emitted so far

    'minus_lines_loop: for minus_line in minus_lines {
        let mut considered = 0; // plus lines considered so far as match for minus_line
        for plus_line in &plus_lines[emitted..] {
            let line_pair = LinePair::new(minus_line, plus_line);
            if line_pair.distance < distance_threshold {
                // minus_line and plus_line are inferred to be a homologous pair.

                // Emit as unpaired the plus lines already considered and rejected
                for plus_line in &plus_lines[emitted..(emitted + considered)] {
                    annotated_plus_lines.push(vec![(non_insertion, plus_line)]);
                }
                emitted += considered;

                // Emit the homologous pair.
                let (minus_edit, plus_edit) = (line_pair.minus_edit, line_pair.plus_edit);
                annotated_minus_lines.push(vec![
                    (non_deletion, &minus_line[0..minus_edit.start]),
                    (deletion, &minus_line[minus_edit.start..minus_edit.end]),
                    (non_deletion, &minus_line[minus_edit.end..]),
                ]);
                annotated_plus_lines.push(vec![
                    (non_insertion, &plus_line[0..plus_edit.start]),
                    (insertion, &plus_line[plus_edit.start..plus_edit.end]),
                    (non_insertion, &plus_line[plus_edit.end..]),
                ]);
                emitted += 1;

                // Move on to the next minus line.
                continue 'minus_lines_loop;
            } else {
                considered += 1;
            }
        }
        // No homolog was found for minus i; emit as unpaired.
        annotated_minus_lines.push(vec![(non_deletion, minus_line)]);
    }
    // Emit any remaining plus lines
    for plus_line in &plus_lines[emitted..] {
        annotated_plus_lines.push(vec![(non_insertion, plus_line)]);
    }

    (annotated_minus_lines, annotated_plus_lines)
}

mod line_pair {
    use std::cmp::{max, min};

    use itertools::{Itertools, PeekingNext};
    use unicode_segmentation::UnicodeSegmentation;

    /// A pair of right-trimmed strings.
    pub struct LinePair<'a> {
        pub minus_line: &'a str,
        pub plus_line: &'a str,
        pub minus_edit: Edit,
        pub plus_edit: Edit,
        pub distance: f64,
    }

    #[derive(Debug)]
    pub struct Edit {
        pub start: usize,
        pub end: usize,
        string_length: usize,
    }

    impl Edit {
        // TODO: exclude leading whitespace in this calculation
        fn distance(&self) -> f64 {
            (self.end - self.start) as f64 / self.string_length as f64
        }
    }

    impl<'a> LinePair<'a> {
        pub fn new(s0: &'a str, s1: &'a str) -> Self {
            let (g0, g1) = (s0.grapheme_indices(true), s1.grapheme_indices(true));
            let (prefix_length, leading_whitespace) = LinePair::prefix_data(g0, g1);
            let common_prefix_length = [
                leading_whitespace[0] + prefix_length,
                leading_whitespace[1] + prefix_length,
            ];
            // TODO: Don't compute grapheme segmentation twice?
            let (g0, g1) = (s0.grapheme_indices(true), s1.grapheme_indices(true));
            let (common_suffix_length, trailing_whitespace) = LinePair::suffix_data(g0, g1);
            let lengths = [
                s0.len() - trailing_whitespace[0],
                s1.len() - trailing_whitespace[1],
            ];

            // We require that (right-trimmed length) >= (common prefix length). Consider:
            // minus = "a    "
            // plus  = "a b  "
            // Here, the right-trimmed length of minus is 1, yet the common prefix length is 2. We
            // resolve this by taking the following maxima:
            let minus_length = max(lengths[0], common_prefix_length[0]);
            let plus_length = max(lengths[1], common_prefix_length[1]);

            // Work backwards from the end of the strings. The end of the change region is equal to
            // the start of their common suffix. To find the start of the change region, start with
            // the end of their common prefix, and then move leftwards until it is before the start
            // of the common suffix in both strings.