User:Quarl/diff.js

// ] - utility functions for doing diffs

// quarl 2006-01-29 initial version

// requires: util.js (trimspaces)

// <pre><nowiki>

// if more than this many words of changes, use overflow string
var diff_wikisummary_maxwords = 30;
var diff_wikisummary_overflow = "$1 words changed";

/*
 * diff() and diffString() are based on
 *  http://ejohn.org/projects/javascript-diff-algorithm/
 *   Copyright John Resig
 */

function diff_split(s) {
    //return trimspaces(s).split(/(?:\s|)+/);
    return trimspaces(s).split(/\s+/);
}

function diffString( o, n ) {
    var out = diff( diff_split(o), diff_split(n) );
    var str = "";

    for ( var i = 0; i < out.n.length - 1; i++ ) {
        if ( out.n.text == null ) {
            if ( out.n.indexOf('"') == -1 && out.n.indexOf('<') == -1 )
                str += "<ins style='background:#E6FFE6;'> " + out.n +"</ins>";
            else
                str += " " + out.n;
        } else {
            var pre = "";
            if ( out.n.text.indexOf('"') == -1 && out.n.text.indexOf('<') == -1 ) {

                var n = out.n.row + 1;
                while ( n < out.o.length && out.o.text == null ) {
                    if ( out.o.indexOf('"') == -1 && out.o.indexOf('<') == -1 && out.o.indexOf(':') == -1 && out.o.indexOf(';') == -1 )
                        pre += " <del style='background:#FFE6E6;'>" + out.o +" </del>";
                    n++;
                }
            }
            str += " " + out.n.text + pre;
        }
    }

    return str;
}

function diff( o, n ) {
    var ns = {};
    var os = {};

    for ( var i = 0; i < n.length; i++ ) {
        // note we have to check that it is in fact an object with "rows", in
        // case ns happens to match a javascript member function of class
        // Array, e.g. "some"!
        if ( ns ] == null || !ns].rows )
            ns ] = { rows: new Array(), o: null };
        ns ].rows.push( i );
    }

    for ( var i = 0; i < o.length; i++ ) {
        if ( os ] == null || !os].rows )
            os ] = { rows: new Array(), n: null };
        os ].rows.push( i );
    }

    for ( var i in ns ) {
        if ( ns.rows.length == 1 && typeof(os) != "undefined" && os.rows.length == 1 ) {
            n.rows ] = { text: n.rows ], row: os.rows };
            o.rows ] = { text: o.rows ], row: ns.rows };
        }
    }

    for ( var i = 0; i < n.length - 1; i++ ) {
        if ( n.text != null && n.text == null &&
             0 <= n.row+1 && n.row+1 < o.length &&
             o.row + 1 ].text == null &&
             n == o.row + 1 ] )
        {
            n = { text: n, row: n.row + 1 };
            o.row+1] = { text: o.row+1], row: i + 1 };
        }
    }

    for ( var i = n.length - 1; i > 0; i-- ) {
        if ( n.text != null && n.text == null &&
             0 <= n.row-1 && n.row-1 < o.length &&
             o.row - 1 ].text == null &&
             n == o.row - 1 ] )
        {
            n = { text: n, row: n.row - 1 };
            o.row-1] = { text: o.row-1], row: i - 1 };
        }
    }

    return { o: o, n: n };
}

function diffAggregate(words) {
    var phrases = new Array();
    var cur = null;
    var wordcount = 0;

    // start at virtual index -1 to check for removed words at beginning of
    // text
    for ( var i = -1; i < words.n.length; i++ ) {
        if ( i!=-1 && words.n.text == null ) {
            if (!cur) {
                cur = { o: "", n: "" };
                phrases.push(cur);
            }
            cur.n += " " + words.n;
            wordcount ++;
        } else {
            var pre = "";
            var j = i==-1 ? 0 : words.n.row + 1;
            while ( j < words.o.length && words.o.text == null ) {
                pre += " " + words.o;
                j++;
                wordcount ++;
            }
            if (pre) {
                if (!cur) {
                    cur = { o: "", n: "" };
                    phrases.push(cur);
                }
                cur.o += pre;
            }
            if (pre && words.n && words.n.text == null) {
                // If there's an addition following, treat this as part of the
                // same change.
            } else {
                cur = null;
            }
        }
    }

    for (var i in phrases) {
        phrases.n = trimspaces(phrases.n);
        phrases.o = trimspaces(phrases.o);
    }

    return { phrases: phrases, wordcount: wordcount };
}

function diffWikiQuote(s) {
    if (!s) return s;
    if (s.match(/^\{\{.*\}\}$/)) return s;
    s = s.replace(/\"/g, "'");
    return '"'+s+'"';
}


function reverse(s) {
    var ret = '';
    for (var i = s.length-1; i >= 0; --i) {
        ret += s;
    }
    return ret;
}

// trim the equal chars from the front and back of o,n at a word boundary
function diffStringTrim(o, n) {
    var r = diffStringTrim0(reverse(o), reverse(n));
    return diffStringTrim0(reverse(r.o), reverse(r.n));
}

function diffStringTrim0(o, n) {
    var i = 0;
    while (i < o.length && i < n.length && o == n) {
        ++i;
    }

    // find index of last non-word character
    var prefix = o.substr(0, i);

    // if prefix ends with word characters and suffix starts with non-word,
    // then erase entire prefix
    if (prefix.match(/\w$/) &&
        !o.substr(i, 1).match(/^\w/) && !n.substr(i, 1).match(/^\w/))
    {
        o = o.substr(i);
        n = n.substr(i);
    } else if (prefix.match(/.*\W/)) {
        i = RegExp.lastMatch.length;
        o = o.substr(i);
        n = n.substr(i);
    } else {
        // keep entire prefix
    }
    return { o: o, n: n };
}

function diffSummary(o, n) {
    if (o == n) return "";
    if (!o) return "new";
    if (!n) return "blank";
    var words = diff( diff_split(o), diff_split(n) );
    var r = diffAggregate(words);
    if (!r.wordcount) return "";
    if (r.wordcount > diff_wikisummary_maxwords) {
        return diff_wikisummary_overflow.replace('$1', r.wordcount);
    }

    var phrases = r.phrases;
    var str = ;
    for (var i in phrases) {
        var r = diffStringTrim(phrases.o, phrases.n);
        var o = diffWikiQuote(r.o), n = diffWikiQuote(r.n);
        if (o && n) {
            str.push(o + ' → ' + n);
        } else if (o) {
            str.push('-' + o);
        } else if (n) {
            str.push('+' + n);
        } else {
            alert("## internal error 15e1b13f-bae3-4399-86c5-721786822fa2");
        }
    }

    return str.join(", ");
}

// </nowiki></pre>