Skip to content

Instantly share code, notes, and snippets.

@HatScripts
Created April 12, 2017 14:04
Show Gist options
  • Save HatScripts/e971eed73d9afae441f2dc24c533e84a to your computer and use it in GitHub Desktop.
Save HatScripts/e971eed73d9afae441f2dc24c533e84a to your computer and use it in GitHub Desktop.
xdiff_string_diff function from http://locutus.io/php/xdiff/xdiff_string_diff/
function xdiff_string_diff(oldData, newData, contextLines) {
// discuss at: http://locutus.io/php/xdiff_string_diff
// original by: Brett Zamir (http://brett-zamir.me)
// based on: Imgen Tata (http://www.myipdf.com/)
// bugfixed by: Imgen Tata (http://www.myipdf.com/)
// improved by: Brett Zamir (http://brett-zamir.me)
// note 1: The minimal argument is not currently supported
// example 1: xdiff_string_diff('', 'Hello world!')
// returns 1: '@@ -0,0 +1,1 @@\n+Hello world!'
// (This code was done by Imgen Tata; I have only reformatted for use in Locutus)
// See http://en.wikipedia.org/wiki/Diff#Unified_format
var i = 0
var j = 0
var k = 0
var oriHunkStart
var newHunkStart
var oriHunkEnd
var newHunkEnd
var oriHunkLineNo
var newHunkLineNo
var oriHunkSize
var newHunkSize
var MAX_CONTEXT_LINES = Number.POSITIVE_INFINITY // Potential configuration
var MIN_CONTEXT_LINES = 0
var DEFAULT_CONTEXT_LINES = 3
var HEADER_PREFIX = '@@ ' //
var HEADER_SUFFIX = ' @@'
var ORIGINAL_INDICATOR = '-'
var NEW_INDICATOR = '+'
var RANGE_SEPARATOR = ','
var CONTEXT_INDICATOR = ' '
var DELETION_INDICATOR = '-'
var ADDITION_INDICATOR = '+'
var oriLines
var newLines
var NEW_LINE = '\n'
var _trim = function (text) {
if (typeof text !== 'string') {
throw new Error('String parameter required')
}
return text.replace(/(^\s*)|(\s*$)/g, '')
}
var _verifyType = function (type) {
var args = arguments
var argsLen = arguments.length
var basicTypes = ['number', 'boolean', 'string', 'function', 'object', 'undefined']
var basicType
var i
var j
var typeOfType = typeof type
if (typeOfType !== 'string' && typeOfType !== 'function') {
throw new Error('Bad type parameter')
}
if (argsLen < 2) {
throw new Error('Too few arguments')
}
if (typeOfType === 'string') {
type = _trim(type)
if (type === '') {
throw new Error('Bad type parameter')
}
for (j = 0; j < basicTypes.length; j++) {
basicType = basicTypes[j]
if (basicType === type) {
for (i = 1; i < argsLen; i++) {
if (typeof args[i] !== type) {
throw new Error('Bad type')
}
}
return
}
}
throw new Error('Bad type parameter')
}
// Not basic type. we need to use instanceof operator
for (i = 1; i < argsLen; i++) {
if (!(args[i] instanceof type)) {
throw new Error('Bad type')
}
}
}
var _hasValue = function (array, value) {
var i
_verifyType(Array, array)
for (i = 0; i < array.length; i++) {
if (array[i] === value) {
return true
}
}
return false
}
var _areTypeOf = function (type) {
var args = arguments
var argsLen = arguments.length
var basicTypes = ['number', 'boolean', 'string', 'function', 'object', 'undefined']
var basicType
var i
var j
var typeOfType = typeof type
if (typeOfType !== 'string' && typeOfType !== 'function') {
throw new Error('Bad type parameter')
}
if (argsLen < 2) {
throw new Error('Too few arguments')
}
if (typeOfType === 'string') {
type = _trim(type)
if (type === '') {
return false
}
for (j = 0; j < basicTypes.length; j++) {
basicType = basicTypes[j]
if (basicType === type) {
for (i = 1; i < argsLen; i++) {
if (typeof args[i] !== type) {
return false
}
}
return true
}
}
throw new Error('Bad type parameter')
}
// Not basic type. we need to use instanceof operator
for (i = 1; i < argsLen; i++) {
if (!(args[i] instanceof type)) {
return false
}
}
return true
}
var _getInitializedArray = function (arraySize, initValue) {
var array = []
var i
_verifyType('number', arraySize)
for (i = 0; i < arraySize; i++) {
array.push(initValue)
}
return array
}
var _splitIntoLines = function (text) {
_verifyType('string', text)
if (text === '') {
return []
}
return text.split('\n')
}
var _isEmptyArray = function (obj) {
return _areTypeOf(Array, obj) && obj.length === 0
}
/**
* Finds longest common sequence between two sequences
* @see {@link http://wordaligned.org/articles/longest-common-subsequence}
*/
var _findLongestCommonSequence = function (seq1, seq2, seq1IsInLcs, seq2IsInLcs) {
if (!_areTypeOf(Array, seq1, seq2)) {
throw new Error('Array parameters are required')
}
// Deal with edge case
if (_isEmptyArray(seq1) || _isEmptyArray(seq2)) {
return []
}
// Function to calculate lcs lengths
var lcsLens = function (xs, ys) {
var i
var j
var prev
var curr = _getInitializedArray(ys.length + 1, 0)
for (i = 0; i < xs.length; i++) {
prev = curr.slice(0)
for (j = 0; j < ys.length; j++) {
if (xs[i] === ys[j]) {
curr[j + 1] = prev[j] + 1
} else {
curr[j + 1] = Math.max(curr[j], prev[j + 1])
}
}
}
return curr
}
// Function to find lcs and fill in the array to indicate the optimal longest common sequence
var _findLcs = function (xs, xidx, xIsIn, ys) {
var i
var xb
var xe
var llB
var llE
var pivot
var max
var yb
var ye
var nx = xs.length
var ny = ys.length
if (nx === 0) {
return []
}
if (nx === 1) {
if (_hasValue(ys, xs[0])) {
xIsIn[xidx] = true
return [xs[0]]
}
return []
}
i = Math.floor(nx / 2)
xb = xs.slice(0, i)
xe = xs.slice(i)
llB = lcsLens(xb, ys)
llE = lcsLens(xe.slice(0)
.reverse(), ys.slice(0)
.reverse())
pivot = 0
max = 0
for (j = 0; j <= ny; j++) {
if (llB[j] + llE[ny - j] > max) {
pivot = j
max = llB[j] + llE[ny - j]
}
}
yb = ys.slice(0, pivot)
ye = ys.slice(pivot)
return _findLcs(xb, xidx, xIsIn, yb).concat(_findLcs(xe, xidx + i, xIsIn, ye))
}
// Fill in seq1IsInLcs to find the optimal longest common subsequence of first sequence
_findLcs(seq1, 0, seq1IsInLcs, seq2)
// Fill in seq2IsInLcs to find the optimal longest common subsequence
// of second sequence and return the result
return _findLcs(seq2, 0, seq2IsInLcs, seq1)
}
// First, check the parameters
if (_areTypeOf('string', oldData, newData) === false) {
return false
}
if (oldData === newData) {
return ''
}
if (typeof contextLines !== 'number' ||
contextLines > MAX_CONTEXT_LINES ||
contextLines < MIN_CONTEXT_LINES) {
contextLines = DEFAULT_CONTEXT_LINES
}
oriLines = _splitIntoLines(oldData)
newLines = _splitIntoLines(newData)
var oriLen = oriLines.length
var newLen = newLines.length
var oriIsInLcs = _getInitializedArray(oriLen, false)
var newIsInLcs = _getInitializedArray(newLen, false)
var lcsLen = _findLongestCommonSequence(oriLines, newLines, oriIsInLcs, newIsInLcs).length
var unidiff = ''
if (lcsLen === 0) {
// No common sequence
unidiff = [
HEADER_PREFIX,
ORIGINAL_INDICATOR,
(oriLen > 0 ? '1' : '0'),
RANGE_SEPARATOR,
oriLen,
' ',
NEW_INDICATOR,
(newLen > 0 ? '1' : '0'),
RANGE_SEPARATOR,
newLen,
HEADER_SUFFIX
].join('')
for (i = 0; i < oriLen; i++) {
unidiff += NEW_LINE + DELETION_INDICATOR + oriLines[i]
}
for (j = 0; j < newLen; j++) {
unidiff += NEW_LINE + ADDITION_INDICATOR + newLines[j]
}
return unidiff
}
var leadingContext = []
var trailingContext = []
var actualLeadingContext = []
var actualTrailingContext = []
// Regularize leading context by the contextLines parameter
var regularizeLeadingContext = function (context) {
if (context.length === 0 || contextLines === 0) {
return []
}
var contextStartPos = Math.max(context.length - contextLines, 0)
return context.slice(contextStartPos)
}
// Regularize trailing context by the contextLines parameter
var regularizeTrailingContext = function (context) {
if (context.length === 0 || contextLines === 0) {
return []
}
return context.slice(0, Math.min(contextLines, context.length))
}
// Skip common lines in the beginning
while (i < oriLen && oriIsInLcs[i] === true && newIsInLcs[i] === true) {
leadingContext.push(oriLines[i])
i++
}
j = i
// The index in the longest common sequence
k = i
oriHunkStart = i
newHunkStart = j
oriHunkEnd = i
newHunkEnd = j
while (i < oriLen || j < newLen) {
while (i < oriLen && oriIsInLcs[i] === false) {
i++
}
oriHunkEnd = i
while (j < newLen && newIsInLcs[j] === false) {
j++
}
newHunkEnd = j
// Find the trailing context
trailingContext = []
while (i < oriLen && oriIsInLcs[i] === true && j < newLen && newIsInLcs[j] === true) {
trailingContext.push(oriLines[i])
k++
i++
j++
}
if (k >= lcsLen || // No more in longest common lines
trailingContext.length >= 2 * contextLines) {
// Context break found
if (trailingContext.length < 2 * contextLines) {
// It must be last block of common lines but not a context break
trailingContext = []
// Force break out
i = oriLen
j = newLen
// Update hunk ends to force output to the end
oriHunkEnd = oriLen
newHunkEnd = newLen
}
// Output the diff hunk
// Trim the leading and trailing context block
actualLeadingContext = regularizeLeadingContext(leadingContext)
actualTrailingContext = regularizeTrailingContext(trailingContext)
oriHunkStart -= actualLeadingContext.length
newHunkStart -= actualLeadingContext.length
oriHunkEnd += actualTrailingContext.length
newHunkEnd += actualTrailingContext.length
oriHunkLineNo = oriHunkStart + 1
newHunkLineNo = newHunkStart + 1
oriHunkSize = oriHunkEnd - oriHunkStart
newHunkSize = newHunkEnd - newHunkStart
// Build header
unidiff += [
HEADER_PREFIX,
ORIGINAL_INDICATOR,
oriHunkLineNo,
RANGE_SEPARATOR,
oriHunkSize,
' ',
NEW_INDICATOR,
newHunkLineNo,
RANGE_SEPARATOR,
newHunkSize,
HEADER_SUFFIX,
NEW_LINE
].join('')
// Build the diff hunk content
while (oriHunkStart < oriHunkEnd || newHunkStart < newHunkEnd) {
if (oriHunkStart < oriHunkEnd &&
oriIsInLcs[oriHunkStart] === true &&
newIsInLcs[newHunkStart] === true) {
// The context line
unidiff += CONTEXT_INDICATOR + oriLines[oriHunkStart] + NEW_LINE
oriHunkStart++
newHunkStart++
} else if (oriHunkStart < oriHunkEnd && oriIsInLcs[oriHunkStart] === false) {
// The deletion line
unidiff += DELETION_INDICATOR + oriLines[oriHunkStart] + NEW_LINE
oriHunkStart++
} else if (newHunkStart < newHunkEnd && newIsInLcs[newHunkStart] === false) {
// The additional line
unidiff += ADDITION_INDICATOR + newLines[newHunkStart] + NEW_LINE
newHunkStart++
}
}
// Update hunk position and leading context
oriHunkStart = i
newHunkStart = j
leadingContext = trailingContext
}
}
// Trim the trailing new line if it exists
if (unidiff.length > 0 && unidiff.charAt(unidiff.length) === NEW_LINE) {
unidiff = unidiff.slice(0, -1)
}
return unidiff
}
function xdiff_string_diff(t,G,x){var U=0;var T=0;var S=0;var Y;var I;var n;var F;var c;var u;var p;var f;var A=Number.POSITIVE_INFINITY;var e=0;var E=3;var v="@@ ";var H=" @@";var L="-";var B="+";var M=",";var W=" ";var h="-";var R="+";var y;var J;var N="\n";var a=function(i){if(typeof i!=="string"){throw new Error("String parameter required")}return i.replace(/(^\s*)|(\s*$)/g,"")};var D=function(af){var ac=arguments;var aa=arguments.length;var ae=["number","boolean","string","function","object","undefined"];var Z;var ad;var ab;var k=typeof af;if(k!=="string"&&k!=="function"){throw new Error("Bad type parameter")}if(aa<2){throw new Error("Too few arguments")}if(k==="string"){af=a(af);if(af===""){throw new Error("Bad type parameter")}for(ab=0;ab<ae.length;ab++){Z=ae[ab];if(Z===af){for(ad=1;ad<aa;ad++){if(typeof ac[ad]!==af){throw new Error("Bad type")}}return}}throw new Error("Bad type parameter")}for(ad=1;ad<aa;ad++){if(!(ac[ad] instanceof af)){throw new Error("Bad type")}}};var O=function(Z,k){var j;D(Array,Z);for(j=0;j<Z.length;j++){if(Z[j]===k){return true}}return false};var V=function(af){var ac=arguments;var aa=arguments.length;var ae=["number","boolean","string","function","object","undefined"];var Z;var ad;var ab;var k=typeof af;if(k!=="string"&&k!=="function"){throw new Error("Bad type parameter")}if(aa<2){throw new Error("Too few arguments")}if(k==="string"){af=a(af);if(af===""){return false}for(ab=0;ab<ae.length;ab++){Z=ae[ab];if(Z===af){for(ad=1;ad<aa;ad++){if(typeof ac[ad]!==af){return false}}return true}}throw new Error("Bad type parameter")}for(ad=1;ad<aa;ad++){if(!(ac[ad] instanceof af)){return false}}return true};var l=function(Z,k){var aa=[];var j;D("number",Z);for(j=0;j<Z;j++){aa.push(k)}return aa};var o=function(i){D("string",i);if(i===""){return[]}return i.split("\n")};var w=function(i){return V(Array,i)&&i.length===0};var z=function(ab,aa,k,j){if(!V(Array,ab,aa)){throw new Error("Array parameters are required")}if(w(ab)||w(aa)){return[]}var Z=function(ad,af){var ae;var ac;var ag;var ah=l(af.length+1,0);for(ae=0;ae<ad.length;ae++){ag=ah.slice(0);for(ac=0;ac<af.length;ac++){if(ad[ae]===af[ac]){ah[ac+1]=ag[ac]+1}else{ah[ac+1]=Math.max(ah[ac],ag[ac+1])}}}return ah};var i=function(ad,aj,ae,ap){var af;var aq;var an;var ac;var ao;var am;var al;var ak;var ai;var ah=ad.length;var ag=ap.length;if(ah===0){return[]}if(ah===1){if(O(ap,ad[0])){ae[aj]=true;return[ad[0]]}return[]}af=Math.floor(ah/2);aq=ad.slice(0,af);an=ad.slice(af);ac=Z(aq,ap);ao=Z(an.slice(0).reverse(),ap.slice(0).reverse());am=0;al=0;for(T=0;T<=ag;T++){if(ac[T]+ao[ag-T]>al){am=T;al=ac[T]+ao[ag-T]}}ak=ap.slice(0,am);ai=ap.slice(am);return i(aq,aj,ae,ak).concat(i(an,aj+af,ae,ai))};i(ab,0,k,aa);return i(aa,0,j,ab)};if(V("string",t,G)===false){return false}if(t===G){return""}if(typeof x!=="number"||x>A||x<e){x=E}y=o(t);J=o(G);var m=y.length;var b=J.length;var g=l(m,false);var C=l(b,false);var X=z(y,J,g,C).length;var Q="";if(X===0){Q=[v,L,(m>0?"1":"0"),M,m," ",B,(b>0?"1":"0"),M,b,H].join("");for(U=0;U<m;U++){Q+=N+h+y[U]}for(T=0;T<b;T++){Q+=N+R+J[T]}return Q}var d=[];var s=[];var r=[];var K=[];var P=function(j){if(j.length===0||x===0){return[]}var i=Math.max(j.length-x,0);return j.slice(i)};var q=function(i){if(i.length===0||x===0){return[]}return i.slice(0,Math.min(x,i.length))};while(U<m&&g[U]===true&&C[U]===true){d.push(y[U]);U++}T=U;S=U;Y=U;I=T;n=U;F=T;while(U<m||T<b){while(U<m&&g[U]===false){U++}n=U;while(T<b&&C[T]===false){T++}F=T;s=[];while(U<m&&g[U]===true&&T<b&&C[T]===true){s.push(y[U]);S++;U++;T++}if(S>=X||s.length>=2*x){if(s.length<2*x){s=[];U=m;T=b;n=m;F=b}r=P(d);K=q(s);Y-=r.length;I-=r.length;n+=K.length;F+=K.length;c=Y+1;u=I+1;p=n-Y;f=F-I;Q+=[v,L,c,M,p," ",B,u,M,f,H,N].join("");while(Y<n||I<F){if(Y<n&&g[Y]===true&&C[I]===true){Q+=W+y[Y]+N;Y++;I++}else{if(Y<n&&g[Y]===false){Q+=h+y[Y]+N;Y++}else{if(I<F&&C[I]===false){Q+=R+J[I]+N;I++}}}}Y=U;I=T;d=s}}if(Q.length>0&&Q.charAt(Q.length)===N){Q=Q.slice(0,-1)}return Q};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment