Module Melange_compiler_libs.Diffing_with_keys

When diffing lists where each element has a distinct key, we can refine the diffing patch by introducing two composite edit moves: swaps and moves.

Swaps exchange the position of two elements. Swap cost is set to 2 * change - epsilon. Moves change the position of one element. Move cost is set to delete + addition - epsilon.

When the cost delete + addition is greater than change and with those specific weights, the optimal patch with Swaps and Moves can be computed directly and cheaply from the original optimal patch.

type with_pos('a) = {
  1. pos: int,
  2. data: 'a,
};
let with_pos: list('a) => list(with_pos('a));
type mismatch('l, 'r, 'diff) =
  1. | Name of {
    1. pos: int,
    2. got: string,
    3. expected: string,
    4. types_match: bool,
    }
  2. | Type of {
    1. pos: int,
    2. got: 'l,
    3. expected: 'r,
    4. reason: 'diff,
    }
;
type change('l, 'r, 'diff) =
  1. | Change(mismatch('l, 'r, 'diff))
  2. | Swap of {
    1. pos: (int, int),
    2. first: string,
    3. last: string,
    }
  3. | Move of {
    1. name: string,
    2. got: int,
    3. expected: int,
    }
  4. | Insert of {
    1. pos: int,
    2. insert: 'r,
    }
  5. | Delete of {
    1. pos: int,
    2. delete: 'l,
    }
;

This specialized version of changes introduces two composite changes: Move and Swap

let prefix: Stdlib.Format.formatter => change('l, 'r, 'diff) => unit;
module Define: (D: Diffing.Defs with type eq := unit) => { ... };