xdiff_string_diff function from http://locutus.io/php/xdiff/xdiff_string_diff/

xdiff_string_diff.js

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
}

xdiff_string_diff.min.js

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};