I might be wildly misreading the code, but it seems like [1,2,3,a,b,c] diffed with [a,b,c,1,2,3] is going to appear as six lines of replacement.
The table will be {a :(1,1), b :(1,1), ...} because each line appears in both files exactly once.
do {
c = a;
d = b;
// first pass a=0, b=0
// the lines aren't equal, they're "1" and "a" so we pass this case.
if (one[a] === two[b]) {
equality();
} else {
//one[0] is "1", matching 1:(1,1)
//two[0] is "a", matching a:(1,1)
if (table[one[a]].two < 1 && table[two[b]].one < 1) {
//can't get here
replaceUniques();
} else if (table[one[a]].two < 1 && one[a + 1] !== two[b + 2]) {
// 1:(1,1) cdr not less than 1, so this is out
deletion();
} else if (table[two[b]].one < 1 && one[a + 2] !== two[b + 1]) {
// a:(1,1) car not less than 1, so this is out
insertion();
} else if (table[one[a]].one - table[one[a]].two === 1 && one[a + 1] !== two[b + 2]) {
// 0 === one[a+1] !== two[b+2]
// === "2" !== "c"
// === true
deletionStatic();
} else if (table[two[b]].two - table[two[b]].one === 1 && one[a + 2] !== two[b + 1]) {
// 0 === one[a+2] !== two[b+1]
// === "3" !== "b"
// === true
insertionStatic();
} else {
// so we're stuck replacing.
replacement();
}
}
a += 1;
b += 1;
} while (a < lena && b < lenb);
it's very pretty, it just seems like it's not not doing enough lookahead to find those long distance relationships.
(although i didn't run it, i could have screwed up my interpretation)
in my limited experience, diff is very hard.
edit
fixed a couple typos in the comments.
yeah, three deletes and three inserts showing at least 3 lines of equality is preferable. ideally it'd show a single edit, move of 3 lines, but that's really hard to do.
I tested this using the online version at http://prettydiff.com/ , and you're right; if you feed it those two six-line files, it produces a six-line replacement without finding any common lines. Good catch, and good test case.
I had trouble reproducing 9 differences. I tried these samples in a couple different ways (on the same line or broken onto different lines) in different browsers and always came up with 6 differences instead of 9 differences.
The weird thing is, that website highlights 6 changes for that example (first and last three lines) but says at the top: Number of differences: 9 differences from 9 lines of code.
And the little folding button does indeed fold all nine lines.
When I instead try [a,b,c,1,2,3,x,y,z] against [a,b,c,1,2,3,a,b,c] it only shows "Number of differences: 3 differences from 3 lines of code." and folds the first 6 and the last 3 lines.
I still cannot reproduce the problem of 9 differences. I have tried in Edge, Chrome, and Firefox on Windows 10. I will try on OSX in just a second.
The reason why it changes output after using square braces is because the tool is language aware. Before it could not guess at a programming language and so the input is text parsed into lines. After the language detection guesses this is JSON format and formally parses the input, beautifies it, and then compares the beautified output.
I already realize that if I am going to the trouble of parsing languages that it would be far more efficient to simply compare the parsed token lists instead of beautified text, but I haven't gotten there yet.
Depends on what you want to achieve? When diffing source code, comparing lines, without caring too much about the broader context, may be a good-enough proxy of what you ideally want to compare, which is the program’s logic. But for the latter, you would first have to execute both programs, and diff their parse trees.
Likewise – and perhaps most notoriously – simple line-based diffing does not suffice for diffing prose (natural language text), where knowledge of the broader context, markup (semantics in punctuation and document structure), and paragraph order are crucially important.
programs are self-contained entities, whereas prose often drags in multitudes of real-world context involving assumptions, motives, and other considerations.
a diff might inform you of an edit in chapter 2 where you changed a man's status from "divorced" to "widowed" (to make him appear more sympathetic), but it won't also remind you that you need to rewrite that section in chapter 25 where the man gets a phone-call from his former wife.
this type of thing happens a lot, in ways that are much more subtle than that silly example. and it's usually because the arc of the story is greater than (and different from) a simple sum of its pieces.
> I might be wildly misreading the code, but it seems like [1,2,3,a,b,c] diffed with [a,b,c,1,2,3] is going to appear as six lines of replacement.
A bit of a pickle.
The challenge I experienced with this is that either there are 6 changes (line for line comparison) or there are 3 lines the same and three lines moved, but three lines moved means a deletion of 3 lines from the first sample and 3 lines of insertion later in the second sample, which is still 6 differences. The output reads very differently, but the number of differences is identical, which is no change in precision.
Unless my understanding of things is wrong, I'm pretty sure that unless the strong exponential time hypothesis (essentially, n variable CNF-SAT takes O(2^n) time in the worst case) is false, no diff algorithm can run in subquadratic time. If you could, then you would be able to solve longest common subsequence in subquadatic time, and that in turn implies SETH being false by https://arxiv.org/abs/1501.07053 .
I'm pretty sure exact diff in subquadratic time is therefore impossible. It's still a nice heuristic though.
Minor remark: If the edit distance between two n-length strings is (relatively) small, it is possible to find it in subquadratic time. More precisely, if the edit distance is at most d, you can solve the problem in O(nd) time. The upper bound d does not have to be known in advance. The conditional lower bound you mentioned holds only for large values of edit distance.
This "problem" may be more of a conceptual one rather than a technical one; for example, a file with "years = [1989,1870,2016]" diffed with "years = [1920,1889,1670]" according to you should appear as the move of 6 lines, it is technically true but doesn't help the user one bit, which is usually the purpose of a diff.
The table will be {a :(1,1), b :(1,1), ...} because each line appears in both files exactly once.
it's very pretty, it just seems like it's not not doing enough lookahead to find those long distance relationships.(although i didn't run it, i could have screwed up my interpretation)
in my limited experience, diff is very hard.
edit
fixed a couple typos in the comments.
yeah, three deletes and three inserts showing at least 3 lines of equality is preferable. ideally it'd show a single edit, move of 3 lines, but that's really hard to do.