diff.js

AdamCMS是免费开源软件,使用简单功能实用,针对个人和中小型企业能够方便快速的架设自己网站,可自定义模块和文档,自制网站样式风格,使用UTF-8编码,方便发布各种语言的信息,欢迎大家使用

// Diff_Match_Patch v1.3
// Computes the difference between two texts to create a patch.
// Applies the patch onto another text, allowing for errors.
// Copyright (C) 2006 Neil Fraser
// http://neil.fraser.name/software/diff_match_patch/

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License (www.gnu.org) for more details.


// Constants.
// Redefine these in your program to override the defaults.

// Number of seconds to map a diff before giving up.  (0 for infinity)
var DIFF_TIMEOUT = 1.0;
// Cost of an empty edit operation in terms of edit characters.
var DIFF_EDIT_COST = 4;
// Tweak the relative importance (0.0 = accuracy, 1.0 = proximity)
var MATCH_BALANCE = 0.5;
// At what point is no match declared (0.0 = perfection, 1.0 = very loose)
var MATCH_THRESHOLD = 0.5;
// The min and max cutoffs used when computing text lengths.
var MATCH_MINLENGTH = 100;
var MATCH_MAXLENGTH = 1000;
// Chunk size for context length.
var PATCH_MARGIN = 4;


  //////////////////////////////////////////////////////////////////////
 //  Diff                                                            //
//////////////////////////////////////////////////////////////////////

// The data structure representing a diff is an array of tuples:
// [[-1, "Hello"], [1, "Goodbye"], [0, " world."]]
// which means: delete "Hello", add "Goodbye" and keep " world."


function diff_main(text1, text2, checklines) {
  // Find the differences between two texts.  Return an array of changes.
  // If checklines is present and false, then don't run a line-level diff first to identify the changed areas.
  // Check for equality (speedup)
  if (text1 == text2)
    return [[0, text1]];

  if (typeof checklines == 'undefined')
    checklines = true;

  var a;
  // Trim off common prefix (speedup)
  a = diff_prefix(text1, text2);
  text1 = a[0];
  text2 = a[1];
  var commonprefix = a[2];

  // Trim off common suffix (speedup)
  a = diff_suffix(text1, text2);
  text1 = a[0];
  text2 = a[1];
  var commonsuffix = a[2];

  var diff, i;
  var longtext = text1.length > text2.length ? text1 : text2;
  var shorttext = text1.length > text2.length ? text2 : text1;

  if (!text1) {  // Just add some text (speedup)
    diff = [[1, text2]];
  } else if (!text2) { // Just delete some text (speedup)
    diff = [[-1, text1]];
  } else if ((i = longtext.indexOf(shorttext)) != -1) {
    // Shorter text is inside the longer text (speedup)
    diff = [[1, longtext.substring(0, i)], [0, shorttext], [1, longtext.substring(i+shorttext.length)]];
    // Swap insertions for deletions if diff is reversed.
    if (text1.length > text2.length)
      diff[0][0] = diff[2][0] = -1;
  } else {
    longtext = shorttext = null; // Garbage collect
    // Check to see if the problem can be split in two.
    var hm = diff_halfmatch(text1, text2);
    if (hm) {
      // A half-match was found, sort out the return data.
      var text1_a = hm[0];
      var text1_b = hm[1];
      var text2_a = hm[2];
      var text2_b = hm[3];
      var mid_common = hm[4];
      // Send both pairs off for separate processing.
      var diff_a = diff_main(text1_a, text2_a, checklines);
      var diff_b = diff_main(text1_b, text2_b, checklines);
      // Merge the results.
      diff = diff_a.concat([[0, mid_common]], diff_b);
    } else {
      // Perform a real diff.
      if (checklines && text1.length + text2.length < 250)
        checklines = false; // Too trivial for the overhead.
      if (checklines) {
        // Scan the text on a line-by-line basis first.
        a = diff_lines2chars(text1, text2);
        text1 = a[0];
        text2 = a[1];
        var linearray = a[2];
      }
      diff = diff_map(text1, text2);
      if (!diff) // No acceptable result.
        diff = [[-1, text1], [1, text2]];
      if (checklines) {
        diff_chars2lines(diff, linearray); // Convert the diff back to original text.
        diff_cleanup_semantic(diff); // Eliminate freak matches (e.g. blank lines)

        // Rediff any replacement blocks, this time on character-by-character basis.
        diff.push([0, '']);  // Add a dummy entry at the end.
        var pointer = 0;
        var count_delete = 0;
        var count_insert = 0;
        var text_delete = '';
        var text_insert = '';
        while(pointer < diff.length) {
          if (diff[pointer][0] == 1) {
            count_insert++;
            text_insert += diff[pointer][1];
          } else if (diff[pointer][0] == -1) {
            count_delete++;
            text_delete += diff[pointer][1];
          } else {  // Upon reaching an equality, check for prior redundancies.
            if (count_delete >= 1 && count_insert >= 1) {
              // Delete the offending records and add the merged ones.
              a = diff_main(text_delete, text_insert, false);
              diff.splice(pointer - count_delete - count_insert, count_delete + count_insert);
              pointer = pointer - count_delete - count_insert;
              for (i=a.length-1; i>=0; i--)
                diff.splice(pointer, 0, a[i]);
              pointer = pointer + a.length;
            }
            count_insert = 0;
            count_delete = 0;
            text_delete = '';
            text_insert = '';
          }
          pointer++;
        }
        diff.pop();  // Remove the dummy entry at the end.

      }
    }
  }

  if (commonprefix)
    diff.unshift([0, commonprefix]);
  if (commonsuffix)
    diff.push([0, commonsuffix]);
  diff_cleanup_merge(diff);
  return diff;
}


function diff_lines2chars(text1, text2) {
  // Split text into an array of strings.
  // Reduce the texts to a string of hashes where each character represents one line.
  var linearray = new Array();  // linearray[4] == "Hello\n"
  var linehash = new Object();  // linehash["Hello\n"] == 4

  // "\x00" is a valid JavaScript character, but the Venkman debugger doesn't like it (bug 335098)
  // So we'll insert a junk entry to avoid generating a null character.
  linearray.push('');

  function diff_lines2chars_munge(text) {
    // My first ever closure!
    var i, line;
    var chars = '';
    while (text) {
      i = text.indexOf('\n');
      if (i == -1)
        i = text.length;
      line = text.substring(0, i+1);
      text = text.substring(i+1);
      if (linehash.hasOwnProperty ? linehash.hasOwnProperty(line) : (linehash[line] !== undefined)) {
        chars += String.fromCharCode(linehash[line]);
      } else {
        linearray.push(line);
        linehash[line] = linearray.length - 1;
        chars += String.fromCharCode(linearray.length - 1);
      }
    }
    return chars;
  }

  var chars1 = diff_lines2chars_munge(text1);
  var chars2 = diff_lines2chars_munge(text2);
  return [chars1, chars2, linearray];
}


function diff_chars2lines(diff, linearray) {
  // Rehydrate the text in a diff from a string of line hashes to real lines of text.
  var chars, text;
  for (var x=0; x<diff.length; x++) {
    chars = diff[x][1];
    text = '';
    for (var y=0; y<chars.length; y++)
      text += linearray[chars.charCodeAt(y)];
    diff[x][1] = text;
  }
}


function diff_map(text1, text2) {
  // Explore the intersection points between the two texts.
  var now = new Date();
  var ms_end = now.getTime() + DIFF_TIMEOUT * 1000; // Don't run for too long.
  var max = (text1.length + text2.length) / 2;
  var v_map1 = new Array();
  var v_map2 = new Array();
  var v1 = new Object();
  var v2 = new Object();
  v1[1] = 0;
  v2[1] = 0;
  var x, y;
  var footstep; // Used to track overlapping paths.
  var footsteps = new Object();
  var done = false;
  var hasOwnProperty = !!(footsteps.hasOwnProperty);
  // If the total number of characters is odd, then the front path will collide with the reverse path.
  var front = (text1.length + text2.length) % 2;
  for (var d=0; d<max; d++) {
    now = new Date();
    if (DIFF_TIMEOUT > 0 && now.getTime() > ms_end) // Timeout reached
      return null;

    // Walk the front path one step.
    v_map1[d] = new Object();
    for (var k=-d; k<=d; k+=2) {
      if (k == -d || k != d && v1[k-1] < v1[k+1])
        x = v1[k+1];
      else
        x = v1[k-1]+1;
      y = x - k;
      footstep = x+","+y;
      if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))
        done = true;
      if (!front)
        footsteps[footstep] = d;
      while (!done && x < text1.length && y < text2.length && text1.charAt(x) == text2.charAt(y)) {
        x++; y++;
        footstep = x+","+y;
        if (front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))
          done = true;
        if (!front)
          footsteps[footstep] = d;
      }
      v1[k] = x;
      v_map1[d][x+","+y] = true;
      if (done) {
        // Front path ran over reverse path.
        v_map2 = v_map2.slice(0, footsteps[footstep]+1);
        var a = diff_path1(v_map1, text1.substring(0, x), text2.substring(0, y));
        return a.concat(diff_path2(v_map2, text1.substring(x), text2.substring(y)));
      }
    }

    // Walk the reverse path one step.
    v_map2[d] = new Object();
    for (var k=-d; k<=d; k+=2) {
      if (k == -d || k != d && v2[k-1] < v2[k+1])
        x = v2[k+1];
      else
        x = v2[k-1]+1;
      y = x - k;
      footstep = (text1.length-x)+","+(text2.length-y);
      if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))
        done = true;
      if (front)
        footsteps[footstep] = d;
      while (!done && x < text1.length && y < text2.length && text1.charAt(text1.length-x-1) == text2.charAt(text2.length-y-1)) {
        x++; y++;
        footstep = (text1.length-x)+","+(text2.length-y);
        if (!front && (hasOwnProperty ? footsteps.hasOwnProperty(footstep) : (footsteps[footstep] !== undefined)))
          done = true;
        if (front)
          footsteps[footstep] = d;
      }
      v2[k] = x;
      v_map2[d][x+","+y] = true;
      if (done) {
        // Reverse path ran over front path.
        v_map1 = v_map1.slice(0, footsteps[footstep]+1);
        var a = diff_path1(v_map1, text1.substring(0, text1.length-x), text2.substring(0, text2.length-y));
        return a.concat(diff_path2(v_map2, text1.substring(text1.length-x), text2.substring(text2.length-y)));
      }
    }
  }
  // Number of diffs equals number of characters, no commonality at all.
  return null;
}


function diff_path1(v_map, text1, text2) {
  // Work from the middle back to the start to determine the path.
  var path = [];
  var x = text1.length;
  var y = text2.length;
  var last_op = null;
  for (var d=v_map.length-2; d>=0; d--) {
    while(1) {
      if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {
        x--;
        if (last_op === -1)
          path[0][1] = text1.charAt(x) + path[0][1];
        else
          path.unshift([-1, text1.charAt(x)]);
        last_op = -1;
        break;
      } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {
        y--;
        if (last_op === 1)
          path[0][1] = text2.charAt(y) + path[0][1];
        else
          path.unshift([1, text2.charAt(y)]);
        last_op = 1;
        break;
      } else {
        x--;
        y--;
        //if (text1.charAt(x) != text2.charAt(y))
        //  return alert("No diagonal.  Can't happen. (diff_path1)");
        if (last_op === 0)
          path[0][1] = text1.charAt(x) + path[0][1];
        else
          path.unshift([0, text1.charAt(x)]);
        last_op = 0;
      }
    }
  }
  return path;
}


function diff_path2(v_map, text1, text2) {
  // Work from the middle back to the end to determine the path.
  var path = [];
  var x = text1.length;
  var y = text2.length;
  var last_op = null;
  for (var d=v_map.length-2; d>=0; d--) {
    while(1) {
      if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty((x-1)+","+y) : (v_map[d][(x-1)+","+y] !== undefined)) {
        x--;
        if (last_op === -1)
          path[path.length-1][1] += text1.charAt(text1.length-x-1);
        else
          path.push([-1, text1.charAt(text1.length-x-1)]);
        last_op = -1;
        break;
      } else if (v_map[d].hasOwnProperty ? v_map[d].hasOwnProperty(x+","+(y-1)) : (v_map[d][x+","+(y-1)] !== undefined)) {
        y--;
        if (last_op === 1)
          path[path.length-1][1] += text2.charAt(text2.length-y-1);
        else
          path.push([1, text2.charAt(text2.length-y-1)]);
        last_op = 1;
        break;
      } else {
        x--;
        y--;
        //if (text1.charAt(text1.length-x-1) != text2.charAt(text2.length-y-1))
        //  return alert("No diagonal.  Can't happen. (diff_path2)");
        if (last_op === 0)
          path[path.length-1][1] += text1.charAt(text1.length-x-1);
        else
          path.push([0, text1.charAt(text1.length-x-1)]);
        last_op = 0;
      }
    }
  }
  return path;
}


function diff_prefix(text1, text2) {
  // Trim off common prefix
  var pointermin = 0;
  var pointermax = Math.min(text1.length, text2.length);
  var pointermid = pointermax;
  while(pointermin < pointermid) {
    if (text1.substring(0, pointermid) == text2.substring(0, pointermid))
      pointermin = pointermid;
    else
      pointermax = pointermid;
    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
  }
  var commonprefix = text1.substring(0, pointermid);
  text1 = text1.substring(pointermid);
  text2 = text2.substring(pointermid);
  return [text1, text2, commonprefix];