New tool: JavaScript Diff
JavaScript or CSS files grow to enormous proportions and become almost impossible to manage. At my customer, I had the need to spot the differences between the versions in development and production. I found the algorithm written in JavaScript at John Resig.
The CSS
The code uses the default markup for insertions and deletions. I added a background colour:
ins{background:#cfc}
del{background:#fcc}
#out{font-family:monospace;font-size:11px;border:solid 1px #ccc;padding:2px}
The HTML
Is very simple: two textareas, a button and a div for output:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head><meta http-equiv="content-type" content="text/html;charset=UTF-8" />
<title>JavaScript Diff</title>
<style type="text/css">
body{font-family:trebuchet ms,sans-serif}
textarea{width:40%;height:200px}
ins{background:#cfc}
del{background:#fcc}
#out{font-family:monospace;font-size:11px;border:solid 1px #ccc;padding:2px}
</style>
</head><body><div id="canvas">
<h1>JavaScript Diff</h1>
<textarea id="one"></textarea>
<textarea id="two"></textarea><br />
<button onclick="test()">Calculate Diff</button> (<ins>added</ins> - <del>deleted</del>).
<div id="out">This space makes the difference.</div>
</div>
<script type="text/javascript">//<![CDATA
// js goes here
//]]></script>
</body></html>
The JavaScript
I copied the necessary parts from John Resig and shortened them a little:
var $=function(a){return document.getElementById(a)}
function test(){
var o=diffString(escape($('one').value),escape($('two').value))
o=o.replace(/\r/gm,'<br />')
o=o.replace(/\t/gm,' ')
$('out').innerHTML=o
}
function escape(s){return s.replace(/&/g,'&').replace(/</g,'<').replace(/>/g,'>').replace(/"/g,'"')}
function diffString(o,n){
o=o.replace(/\s+$/,'');n=n.replace(/\s+$/,'')
var out=diff(o==''?[]:o.split(/\s+/),n==''?[]:n.split(/\s+/)),str='',i,x=null,pre
var oSpace=o.match(/\s+/g),nSpace=n.match(/\s+/g)
if(oSpace==x)oSpace=['\n'];else oSpace.push('\n')
if(nSpace==x)nSpace=['\n'];else nSpace.push('\n')
if(out.n.length==0){for(i=0;i<out.o.length;i++)str+='<del>'+escape(out.o[i])+oSpace[i]+'</del>'}
else{
if(out.n[0].text==x){for(n=0;n<out.o.length && out.o[n].text==x;n++)str+='<del>'+escape(out.o[n])+oSpace[n]+'</del>'}
for(i=0;i<out.n.length;i++){
if(out.n[i].text==x)str+='<ins>'+escape(out.n[i])+nSpace[i]+'</ins>'
else{
pre=''
for(n=out.n[i].row+1;n<out.o.length && out.o[n].text==x;n++){
pre+='<del>'+escape(out.o[n])+oSpace[n]+'</del>'
}
str+=" "+out.n[i].text+nSpace[i]+pre
}
}
}
return str
}
function diff(o,n){
var ns={},os={},i,x=null
for(i=0;i<n.length;i++){if(ns[n[i]]==x)ns[n[i]]={rows:[],o:x};ns[n[i]].rows.push(i)}
for(i=0;i<o.length;i++){if(os[o[i]]==x)os[o[i]]={rows:[],n:x};os[o[i]].rows.push(i)}
for(i in ns){
if(ns[i].rows.length==1 && typeof(os[i])!='undefined' && os[i].rows.length==1){
n[ns[i].rows[0]]={text:n[ns[i].rows[0]],row:os[i].rows[0]}
o[os[i].rows[0]]={text:o[os[i].rows[0]],row:ns[i].rows[0]}
}
}
for(i=0;i<n.length-1;i++){
if(n[i].text!=x && n[i+1].text==x && n[i].row+1<o.length && o[n[i].row+1].text==x &&
n[i+1]==o[n[i].row+1]){
n[i+1]={text:n[i+1],row:n[i].row+1}
o[n[i].row+1]={text:o[n[i].row+1],row:i+1}
}
}
for(i=n.length-1;i>0;i--){
if(n[i].text!=x && n[i-1].text==x && n[i].row>0 && o[n[i].row-1].text==x &&
n[i-1]==o[n[i].row-1]){
n[i-1]={text:n[i-1],row:n[i].row-1}
o[n[i].row-1]={text:o[n[i].row-1],row:i-1}
}
}
return {o:o,n:n}
}
The result
I've made a JS-Diff test page. I've already filled the textareas with some content. If you want to use it: take the source, but leave in the credits to
http://ejohn.org/projects/javascript-diff-algorithm/.
Comments
10/30/2007 08:48:42 PM, Ben Poole
This is the algorithm we use in DominoWiki. Resig's is by far the best I'd say. There are a few issues with it, but they are documented in the pages you link to.
To add a comment, log in or register as new user. It's free and safe.