adiff
diff and patch arrays.
npm install adiff
Want to see pretty graphs? Log in now!
43 | downloads in the last week |
78 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.2.12 last updated 4 months ago |
Repository | git://github.com/dominictarr/adiff.git (git) |
Homepage | https://github.com/dominictarr/adiff |
Bugs | https://github.com/dominictarr/adiff/issues |
Dependencies | None |
Dependents | bed, hdiff, quickansi, r-edit, xdiff |
Starred by | dodo |
adiff - Array diff tools is javacript
adiff is a minimal implementation of diff tools, diff, patch, diff3 in javascript.
I initially started writing this to understand how git works. then i got totally carried away. adiff is a central component in snob a self hosting port of git to javascript.
how git works.
if you want to know what is the difference between two files, you must first know what is the same.
this is called the Longest Common Subsequence problem. if you have two sequences x = "ABDCEF" and
y = "ABCXYZF"then
LCS(x,y)` is clearly "ABCF".
lcs
function lcs (a,b)
if head(a) == head(b)
then lcs(a,b) = head(a) + lcs(tail(a), tail(b))
else lcs(a, b) = max(lcs(tail(a),b), lcs(a, tail(b)))
(where max returns the longer list, head return the first element, and tail returns the rest of the sequence minus the head)
this is very simple, but with exponential time complexity. however, it can easily be made sufficantly performant by cacheing the return value of each call to lcs().
see js implementation, index.js#L64-94
chunking
now, we can see when the strings differ, by comparing them to the lcs. the next step is dividing them into 'stable' chunks where they match the lcs, and unstable chunks where they differ.
basically, to go from chunk("ABDCEF", "ABCXYZF")
to
["AB", ["D", ""], "C", ["E", "XYZ"], "F"]
note that stable and unstable chunks always alternate.
basically, you iterate over the sequences and while the heads match the head of the lcs, shift that value to a stable chunk. then, while the heads do not match the next head of the lcs, collect add those items into an unstable chunk.
diff
once you have the chunks getting a list of changes that you can apply is easy...
making a diff from a to b we want to know what changes to make to a to get b.
the way I have node this Array#splice
so, for ["AB", ["D", ""], "C", ["E", "XYZ"], "F"]
we want:
var changes = [
[4, 1, 'X', 'Y', 'Z'], //delete 1 item ("E") at index 4, then insert "X", "Y", "Z"
[2, 1] //delete 1 item at index 2 ("D")
]
note, you can apply changes to the end of the array without altering the indexes in the start of the array.
this makes the function to apply the patch very simple
patch
function patch (orig, changes) {
var ary = orig.split('') //assuming that orig is just a string
changes.forEach(function (ch) {
[].splice.apply(ary, ch)
})
return ary.join('')
}
diff3
if we want a distributed version management system, the we need to be able to make changes in parallel.
this is only a slightly more complicated problem. given a string "ABDCEF"
, If I changed it to "ABCXYZF"
and meanwhile you changed it to "AXBCEFG". we must compare each of our changes to the original string, the Concestor
merging rules
TODO: worked example with chunks, resolve.
license
MIT / Apache2