Crate patience_diff

Source
Expand description

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§

Functions§

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