gliese1337 / fast-myers-diff

MIT License
53 stars 8 forks source link

`lcs` and `diff` sometimes pass index -1 to the `eq` function #21

Open TomBinford opened 3 months ago

TomBinford commented 3 months ago

I believe this is a bug because I expect the numbers passed to eq to be integers from 0 up to the length of the input (xs.length for i and ys.length for j). In my testing it seems that this happens when exactly one of the parameters to lcs or diff has length 0. For example:

const a = [["a"]];
const b = [];

console.log("LCS:", Array.from(
  lcs(a, b, (i, j) => {
    console.log("Comparing elements at " + i + " and " + j);
    return a[i][0] === b[j][0];
  })
));

will print out "Comparing elements at 0 and -1" and then throw an error because b[-1][0] attempts to index into undefined. Same issue happens if the values are switched to a = [] and b = [["b"]].

Regarding the fix, I hope we can root-cause the error before tacking on the quick fix of early-returning on if (a.length === 0 || b.length === 0). It may indicate an error in implementing the Myers algorithm.