Crate patience_diff

This crate is for computing patience diffs, which require more effort to compute than normal diffs but are usually more human-readable.

A diff describes the difference between two lists a and b; namely, the diff between a and b describes how to go from a to b by inserting, deleting, or keeping elements.

Why use a patience diff?

Patience diffs are often more readable than ordinary, longest common subsequence-based diffs. For example, if you go from:

int func_1() {
    return 1;
}

int func_2() {
    return 2;
}

To:

int func_1() {
    return 1;
}

int func_new() {
    return 0;
}

int func_2() {
    return 2;
}

The LCS diff between these two sequences of lines is:

  int func_1() {
      return 1;
+ }
+
+ int func_new() {
+     return 0;
  }

  int func_2() {
      return 2;
  }

Their patience diff, on the other hand, is:

  int func_1() {
      return 1;
  }

+ int func_new() {
+     return 0;
+ }
+
  int func_2() {
      return 2;
  }

How a patience diff is computed

An “ordinary” diff is based on a longest common subsequence between a and b. A patience diff is very similar, but first finds the longest common subsequence between the unique elements of a and b to find “unambiguous” matches. Then, a patience diff is recursively computed for ranges between matched elements.

You can read Bram Cohen, “discoverer” of patience diff, describe patience diff in his own words here.

Enums

DiffComponent

Functions

patience_diff

Computes the patience diff betwen a and b. The DiffComponents hold references to the elements in a and b they correspond to.