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 l

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;

• 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
.deleted {background-color : LightPink;
text-decoration : line-through}
.inserted {background-color : PaleGreen}




JS Bin


The quick brown fox jumps over the lazy dog
The quick brown coyote jumps over the lazy dog
Click to get diff





`

StackExchange Code Review Q#133586, answer score: 4