# A String.prototype.diff() implementation (text diff)

I just had the idea to develop an algorithm to calculate and highlight the difference between two strings. I know that there are already some libraries to do the job but I just tried to make my own. I really don't know whether this one is similar to the existing ones but it seems to work fine. As of now it's still in it's early stage which means depending on the situation it sometimes produce some multiple consecutive deletion and insertion spans which probably require a second pass to consolidate them under two single delete and insert spans.

How it works:

It takes two strings like

"the quick brown fox jumps over the lazy dog"

and

"the quick brown coyote jumps over the lazy dog"

It will create match a string up until it meets the first mismatching character in-between the two. The index of this character is designated by base index (bi). So in this case matchStr is "the quick brown " then it will generate two new strings as longer ("coyote jumps over the lazy dog") and shorter ("fox jumps over the lazy dog"). Now the Array.prototype.rotate() generic method, which i had implemented a while back for another project walks in. Array.prototype.rotate() can rotate the array in both directions but in this particular case we will only rotate it in one direction. shorter stays static and longer gets rotated to find the longest overlapping sub-string.

XX: "fox jumps over the lazy dog"
00: "coyote jumps over the lazy dog"
01: "oyote jumps over the lazy dogc"
02: "yote jumps over the lazy dogco"
03: "ote jumps over the lazy dogcoy"
04: "te jumps over the lazy dogcoyo"
05: "e jumps over the lazy dogcoyot"
06: " jumps over the lazy dogcoyote"
07: "jumps over the lazy dogcoyote "
08: "umps over the lazy dogcoyote j"
09: "mps over the lazy dogcoyote ju"
10: "ps over the lazy dogcoyote jum"
11: "s over the lazy dogcoyote jump"
12: " over the lazy dogcoyote jumps"
13: "over the lazy dogcoyote jumps "
14: "ver the lazy dogcoyote jumps o"
15: "er the lazy dogcoyote jumps ov"
16: "r the lazy dogcoyote jumps ove"
17: " the lazy dogcoyote jumps over"
18: "the lazy dogcoyote jumps over "
19: "he lazy dogcoyote jumps over t"
20: "e lazy dogcoyote jumps over th"
21: " lazy dogcoyote jumps over the"
22: "lazy dogcoyote jumps over the "
23: "azy dogcoyote jumps over the l"
24: "zy dogcoyote jumps over the la"
25: "y dogcoyote jumps over the laz"
26: " dogcoyote jumps over the lazy"
27: "ogcoyote jumps over the lazy d"
28: "gcoyote jumps over the lazy do"
00: "coyote jumps over the lazy dog"


So we will collect all matched sub-strings for each single character rotated version of longer for it's length many times (one complete turn). Once we have length many matched sub-strings, among which we will chose the longest one. So as you will notice at rotate count (rc) #03 both strings produce the longest matched sub-string. Which is " jumps over the lazy dog" So now we know that in the shorter string (which doesn't rotate) the mismatching characters (mismatching sub-string) are the ones at indices 0, 1 and 2. So the start of match is index 3 (cd.fis). While for the longer it (cd.fil) can be calculated as start of match of shorter (cd.fis) + rotate count (rc). However there may be cases in which the longer sentence has a shorter mismatching sub-string and in that case (think about it) cd.fil would be cd.fis + len - rc where len is the length of longer.

So now that we have the matching sub string at the head, the two mismatching strings and the remaining matching string (up until the next mismatch) it's just concatenating the string into one with necessary HTML mark up. Then we recursively feed the function up until we reach to the end of one of the strings.

I totally don't know if this algorithm is a reasonable approach for this job. I tried some edge cases where it seems to work fine but I might be wrong and it might turn out to be inefficient. What would be your ideas to speed it up?

Array.prototype.rotate = function(n) {
var len = this.length;
return !(n % len) ? this
: n > 0 ? this.map((e,i,a) => a[(i + n) % len])
: this.map((e,i,a) => a[(len - (len - i - n) % len) % len]);
};

String.prototype.diff = function(s){

var getBaseIndex = function(s,l){ // returns the index of first mismatching character
var i = 0;
while(s[i] === l[i] && i < s.length) ++i;
return i;
},

findFirstChange = function(s,l){ // returns the first matching substring after base index
var fi = len,
substr = "",
match = false,
i = 0;
while (!match && i < s.length) {
s[i] !== l[i] ? ++i : match = !match;
}
match && (fi = i); // match starts from this index
while (match && i < s.length) {
s[i] === l[i] ? substr += s[i++] : match = !match;
}
return {bix: bi,    // base index : index of first mismaching character
fis: fi,    // index of next re match in shorter string
fil: fi,    // index of next re match in longer string (will be adjusted later)
fss: substr // next matching substring after first mismatch
};
},

isThisLonger = true; // true if the string designated by "this" is longer
bi = getBaseIndex(this,s),
matchStr = s.slice(0,bi), // the matching portion at the beginning
long = this.length >= s.length ? (isThisLonger = true, [...this].slice(bi)) // converted to array as the
: (isThisLonger = false, [...s].slice(bi)),  // long string gets rotated
short = isThisLonger ? s.slice(bi) : this.slice(bi),
len = long.length,
substrings = [],
cd = {}, // change data !! important
change = [], // holds deleted and inserted substrings at indices 0 and 1
nextThis = "", // remaining part of old string to feed recursive call
nextS = "", // remaining part of new string to feed recursive call
result = ""; // the glorious result

for (var rc = 0; rc < len; rc++){ // rc -> rotate count
cd = findFirstChange(short,long.rotate(rc)); // collect change indices
cd.fil = rc < len - cd.fis ? cd.fil + rc : cd.fis + len - rc;   // adjusted for index of next re match in longer string
substrings.push(cd);
}
cd = !!substrings.length && substrings.sort((a,b) => b.fss.length - a.fss.length || a.fis - b.fis || b.fil - a.fil )[0];
long = long.join("");
if (cd) {
change   = isThisLonger ? [long.slice(0,cd.fil), short.slice(0,cd.fis)]
: [short.slice(0,cd.fis), long.slice(0,cd.fil)];
nextThis = isThisLonger ? long.slice(cd.fil) : short.slice(cd.fis);
nextS    = isThisLonger ? short.slice(cd.fis) : long.slice(cd.fil);
change[0] = change[0] && ('<span class = "deleted">' + change[0] + '</span>');
change[1] = change[1] && ('<span class = "inserted">' + change[1] + '</span>');
result = matchStr + change[0] + change[1];
} else result = this;
result += (nextThis !== "" || nextS !== "") ? nextThis.diff(nextS) : "";
return result;
};

textOld.oninput = function(e){textNew.innerText = this.value};
textNew.onfocus = function(e){this.select()};
myButton.onclick = function(e){textdiff.innerHTML = textOld.value.diff(textNew.value)}
.deleted  {background-color : LightPink;
text-decoration  : line-through}
.inserted {background-color : PaleGreen}
<div>
<textarea id="textOld" placeholder="Please type something here" rows = "4" cols = "25"></textarea>
<textarea id="textNew" placeholder="Please edit the previous text here" rows = "4" cols = "25"></textarea>
<button id = myButton style = "display:block"> Click to get diff</button>
<p id="textdiff"></p>
</div>

• Just tried to diff 'the quick brown fox' vs 'he quick brown fox j' and the algorithm seems to fail: see image – Rostislav Jul 1 '16 at 10:33
• Thank you for testing. I guess it does the job. But as i have mentioned in my explanations, "It sometimes produce some multiple consecutive deletion and insertion spans which probably require a second pass to consolidate them under two single delete and insert spans." So yes there is that. – Redu Jul 1 '16 at 10:38
• Well i have to say even though the previous result was technically right it confused me. So i did some rectifications in the code to get better results without doing a second pass. As it seems it's not "totally" perfect but that's the reason i am here for. I hope i am on a track... – Redu Jul 1 '16 at 18:34
• @syb0rg Yes ok and i have inserted a comment for the only guy who had answered, about the change that i am making. I read the link about iterative reviews too .. So do you suggest me to open up a new topic per each rectification in the code? Come on..! – Redu Jul 1 '16 at 18:48
• As the answer you got was more a comment "It's not working as nicely as it should", I converted the answer to a comment and re-applied your edits. I hope you get some nice real reviews. – Simon Forsberg Jul 1 '16 at 18:55

Great question,

I do not like your rotate function;

• While the nested ternary seems brilliant, it reveals a violation of DRY ( you could do this with one map because every negative n has a positive equivalent
• An Array function should either change the current array or make a new array, your function could do either depending on whether a shift is necessary or not
• Rotation really is achieved by taking a part of the string and putting it on the other end, since JavaScripts provides splice and shift I would go with something like this
• Minor, but your indentation is off in this function and elsewhere, it disturbs the reading flow

I do like that you modify the prototype of Array. Most reviewers would complain but I have found 3rd party libraries to have sufficient guards nowadays that is no longer a problem.

Inside diff:

• I see no good reason to declare getBaseIndex with var, even worse is that you declared it as an anonymous function. Naming your variables with s and l is not great, but getBaseIndex does not convey at all what the function actually does
• match && (fi = i); // match starts from this index shows you know JavaScript, but really an if statement is what you should use here
• Same here: s[i] !== l[i] ? ++i : match = !match;
• From a naming perspective, spend the effort to have well written variables. bix, fis, fss, etc. etc. are too hard to parse for the reader
• The commenting however, is great. Otherwise I would probably have given up on this review
• isThisLonger = true; <- that semicolon just made all declarations under it globals (use http://jshint.com/)
• I like the idea of matching largest matches first, not sure about rotating. If I was asked to fix a bug in this code, I would steal that smart key idea and rewrite the whole thing.

I wrote an alternative, it works slightly different. (I like that your code recognizes the word fox, whereas my code goes too far in finding commonalities) I think for an extra bonus, the code should go for both the largest match and the largest mismatch, whatever is largest should go forward. My code has some idiosyncracies, feel free to adopt or ignore (like using ~ with indexOf or not always using curly braces with if statements.)

//The idea is that we try to match the original string,
//and then we keep on trying to match smaller and smaller strings
//If we try to match 'Attempt', we will match 'Attempt', 'Attemp' ,
//'ttempt', 'Attem', 'ttemp' etc. till 't'
String.prototype.largestMatch = function largestMatch( otherString ){

if( otherString.length < this.length )
return otherString.largestMatch( this );

var matchingLength = otherString.length,
possibleMatch, index;

while( matchingLength ){
index = 0;
while( index + matchingLength <= otherString.length ){
possibleMatch = otherString.substr( index, matchingLength );
if( ~this.indexOf( possibleMatch ) )
return otherString.substr( index, matchingLength );
index++;
}
matchingLength--;
}
return '';
};

String.prototype.diff = function( newValue ){

var largestMatch = this.largestMatch( newValue ),
preNew, postNew, preOld, postOld;

if(!largestMatch){
return '<span class = "deleted">' + this + '</span><span class = "inserted">' + newValue + '</span>';
} else {
preNew = newValue.substr(0, newValue.indexOf( largestMatch ) );
preOld = this.substr(0, this.indexOf( largestMatch ) );
postNew = newValue.substr( preNew.length + largestMatch.length );
postOld = this.substr( preOld.length + largestMatch.length );
console.log( { old: this.toString(), new : newValue , preOld: preOld, match: largestMatch, postOld: postOld,
preNew: preNew, match2: largestMatch, postNew: postNew} );
return preOld.diff( preNew ) + largestMatch + postOld.diff( postNew );
}
};

textOld.oninput = function(e){textNew.innerText = this.value;};
textNew.onfocus = function(e){this.select();};
myButton.onclick = function(e){textdiff.innerHTML = textOld.value.diff(textNew.value);};
.deleted  {background-color : LightPink;
text-decoration  : line-through}
.inserted {background-color : PaleGreen}
<!DOCTYPE html>
<html>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Bin</title>
<body>

<div>
<textarea id="textOld" placeholder="Please type something here" rows = "4" cols = "25">The quick brown fox jumps over the lazy dog</textarea>
<textarea id="textNew" placeholder="Please edit the previous text here" rows = "4" cols = "25">The quick brown coyote jumps over the lazy dog</textarea>
<button id = myButton style = "display:block"> Click to get diff</button>
<p id="textdiff"></p>
</div>

</body>
</html>

• isThisLonger = true; <- owww terrible... 10x for pointing out. Waiting for the alternative :) – Redu Jul 1 '16 at 20:51
• Counter proposal done. – konijn Jul 1 '16 at 21:47
• I would like to thank you for your very valuable comments. Thanks to your critics, regarding the Array.prototype.rotate() i have given some further thought and managed to reduce it to a much logical form (i had asked for it but couldn't get the reply that i wanted codereview.stackexchange.com/q/132397/105433) As per the String.prototype.diff() I believe your algorithm is superior and a proof of an expert approach. Again thanks to you i have managed to modify mine to produce much better results. – Redu Jul 3 '16 at 14:08
• Yet... yours is solid on the results where mine, while producing correct results sometimes it gets beyond itself :). I have also given performance tests and your's turn out to be returning the result in average 40% faster (160ms vs 280ms) in small paragraphs however when i switch to something really big it looks like mine is doing better (115000ms vs 44000ms) Yours : replit.com/C8Wm Mine: replit.com/C612/21. I have also checked both on bare Chrome V52 console and the results seem to be consistent. I will insert the modified one here later today. – Redu Jul 3 '16 at 14:08
• Feel free to mark my answer as accepted ;) – konijn Jul 6 '16 at 19:11

Well.. I have just finalized the code. I both had to modify the code according to the comments of @konijn and also tuned it to perform much faster. As of now there is no performance issues at all. A huge paragraph can be diffed in just a few milliseconds. I even added a precision factor to the code. The precision factor is a number used to stop the rotation of the longer string. It designates the minimum length of the substring that we are searching for. It's a value between 2 and 5. For the default text in below code 4 turns out to be ideal. I guess 4 should be ideal in general too.

The major modifications are;

1. Correcting the Array.prototype.rotate() according rightful comments of @konijn.
2. I totally changed the sub-string logic. Once i find the substrings to replace i do text diff on them recursively up until i can do no more.
3. No more collecting all sub-strings per longer string 1 char rotation. Only the first one is needed. Then rotate it one by one all the way it's length long and for each tick find the first matching sub-string. Just pick the longest one and set up your change data accordingly.
4. No more rotating the string by one character advances all along it's length many times. Once i get a sub-string no smaller than the precision factor we stop rotation. This is the key to the performance.

The tunings are;

1. All JS functors like .map, .reduce (which initially had replaced .sort) are replaced by their equivalents implemented by for loops.
2. All arrow functions are replaced by their conventional function equivalents.

Throughout my tests the algorithm produced solid results. No more getting beyond itself like in the previous versions. So this is as best as it gets from me.

One thing i liked is that, the array rotating thingy has turned out to be super efficient for this job. I will greatly appreciate all ideas to forward this job further.

OK the default text that i have chosen in the code sample below is quite a long one to demonstrate the capacity well enough. Please try it by modifying it or with different texts to check and measure the results.

Array.prototype.rotate = function(n){
var len = this.length,
res = new Array(this.length);
if (n % len === 0) return this.slice();
else for (var i = 0; i < len; i++) res[i] = this[(i + (len + n % len)) % len];
return res;
};

String.prototype.diff = function(s,p){       // p -> precision factor

function getMatchingSubstring(s,l,m){      // returns the first matching substring in-between the two strings
var i = 0,
slen = s.length,
match = false,
o = {fis:slen, mtc:m, sbs:""};       // temporary object used to construct the cd (change data) object
while (i < slen ) {
l[i] === s[i] ? match ? o.sbs += s[i]  // o.sbs holds the matching substring itsef
: (match = true, o.fis = i, o.sbs = s[i])
: match && (i = slen);   // stop after the first found substring
++i;
}
return o;
}

function getChanges(t,s,m){
var isThisLonger = t.length >= s.length ? true : false,
[longer,shorter] = isThisLonger ? [t,s] : [s,t], // assignment of longer and shorter by es6 destructuring
bi = 0;  // base index designating the index of first mismacthing character in both strings

while (shorter[bi] === longer[bi] && bi < shorter.length) ++bi; // make bi the index of first mismatching character
longer = longer.split("").slice(bi);   // as the longer string will be rotated it is converted into array
shorter = shorter.slice(bi);           // shorter and longer now starts from the first mismatching character

var  len = longer.length,              // length of the longer string
cd = {fis: shorter.length,       // the index of matching string in the shorter string
fil: len,                  // the index of matching string in the longer string
sbs: "",                   // the matching substring itself
mtc: m + s.slice(0,bi)},   // if exists mtc holds the matching string at the front
sub = {sbs:""};                   // returned substring per 1 character rotation of the longer string

if (shorter !== "") {
for (var rc = 0; rc < len && sub.sbs.length < p; rc++){           // rc -> rotate count, p -> precision factor
sub = getMatchingSubstring(shorter, longer.rotate(rc), cd.mtc); // rotate longer string 1 char and get substring
sub.fil = rc < len - sub.fis ? sub.fis + rc                     // mismatch is longer than the mismatch in short
: sub.fis - len + rc;              // mismatch is shorter than the mismatch in short
sub.sbs.length > cd.sbs.length && (cd = sub);                   // only keep the one with the longest substring.
}
}
// insert the mismatching delete subsrt and insert substr to the cd object and attach the previous substring
[cd.del, cd.ins] = isThisLonger ? [longer.slice(0,cd.fil).join(""), shorter.slice(0,cd.fis)]
: [shorter.slice(0,cd.fis), longer.slice(0,cd.fil).join("")];
return cd.del.indexOf(" ") == -1 ||
cd.ins.indexOf(" ") == -1 ||
cd.del === ""             ||
cd.ins === ""             ||
cd.sbs === ""              ? cd : getChanges(cd.del, cd.ins, cd.mtc);
}

var changeData = getChanges(this,s,""),
nextS = s.slice(changeData.mtc.length + changeData.ins.length + changeData.sbs.length),    // remaining part of "s"
nextThis = this.slice(changeData.mtc.length + changeData.del.length + changeData.sbs.length), // remaining part of "this"
result = "";  // the glorious result
changeData.del.length > 0 && (changeData.del = '<span class = "deleted">'  + changeData.del + '</span>');
changeData.ins.length > 0 && (changeData.ins = '<span class = "inserted">' + changeData.ins + '</span>');
result = changeData.mtc + changeData.del + changeData.ins + changeData.sbs;
result += (nextThis !== "" || nextS !== "") ? nextThis.diff(nextS,p) : "";
return result;
};

textOld.oninput = function(e){textNew.innerText = this.value};
textNew.onfocus = function(e){this.select()};
myButton.onclick = function(e){
var sr = "",
so = textOld.value,
sn = textNew.value,
ts = 0,
te = 0;
ts = performance.now();
sr = so.diff(sn,+precision.value);
te = performance.now();
textdiff.innerHTML = sr;
perfdiff.textContent = "Diffing the above texts took " + (te-ts) + "msecs";
};
.deleted  {background-color : LightPink;
text-decoration  : line-through;
border           : 1px solid coral}
.inserted {background-color : PaleGreen;
border           : 1px solid forestGreen}
<div>

<br>
<div style="text-align: center">PRECISION</div>
<div style="display:table; margin: 0 auto" >
<div style="display: inline; line-height: 100%; vertical-align: 60%; text-align: center">LESS <<<</div>
<input type="range" id="precision" style="display:inline" min="2" max="5" step="1" list="ticks" value="2">
<div style="display: inline; line-height: 100%; vertical-align: 60%">>>> MORE</div>
<datalist id="ticks">
<option>2</option>
<option>3</option>
<option>4</option>
<option>5</option>
</datalist>
</div>
<button id=myButton style="display:block; margin: 0 auto"> Click to get diff</button>
<p id="perfdiff"></p>
<p id="textdiff"></p>
</div>

• Why is the precision the fasted at step 3, but slowest at 4? – mix3d Dec 4 '18 at 21:24
• @mix3d I guess when precision is low it wastes time to paint DOM with some redundant replacements wastefuly (i mean all those pinks and greens) and losing a few miliseconds on those... But obviously it's best at 3 as both as performance and the result you have figured. – Redu Dec 4 '18 at 21:46