diff.js

Joomla!是一套获得过多个奖项的内容管理系统(Content Management System, CMS)。Joomla!采用PHP+MySQL数据库开发

}


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


function diff_halfmatch(text1, text2) {
  // Do the two texts share a substring which is at least half the length of the longer text?
  var longtext = text1.length > text2.length ? text1 : text2;
  var shorttext = text1.length > text2.length ? text2 : text1;
  if (longtext.length < 10 || shorttext.length < 1)
    return null; // Pointless.

  function diff_halfmatch_i(longtext, shorttext, i) {
    // Start with a 1/4 length substring at position i as a seed.
    var seed = longtext.substring(i, i+Math.floor(longtext.length/4));
    var j = -1;
    var best_common = '';
    var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;
    while ((j = shorttext.indexOf(seed, j+1)) != -1) {
      var my_prefix = diff_prefix(longtext.substring(i), shorttext.substring(j));
      var my_suffix = diff_suffix(longtext.substring(0, i), shorttext.substring(0, j));
      if (best_common.length < (my_suffix[2] + my_prefix[2]).length) {
        best_common = my_suffix[2] + my_prefix[2];
        best_longtext_a = my_suffix[0];
        best_longtext_b = my_prefix[0];
        best_shorttext_a = my_suffix[1];
        best_shorttext_b = my_prefix[1];
      }
    }
    if (best_common.length >= longtext.length/2)
      return [best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b, best_common];
    else
      return null;
  }

  // First check if the second quarter is the seed for a half-match.
  var hm1 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/4));
  // Check again based on the third quarter.
  var hm2 = diff_halfmatch_i(longtext, shorttext, Math.ceil(longtext.length/2));
  var hm;
  if (!hm1 && !hm2)
    return null;
  else if (!hm2)
    hm = hm1;
  else if (!hm1)
    hm = hm2;
  else // Both matched.  Select the longest.
    hm = hm1[4].length > hm2[4].length ? hm1 : hm2;

  // A half-match was found, sort out the return data.
  if (text1.length > text2.length) {
    var text1_a = hm[0];
    var text1_b = hm[1];
    var text2_a = hm[2];
    var text2_b = hm[3];
  } else {
    var text2_a = hm[0];
    var text2_b = hm[1];
    var text1_a = hm[2];
    var text1_b = hm[3];
  }
  var mid_common = hm[4];
  return [text1_a, text1_b, text2_a, text2_b, mid_common];
}


function diff_cleanup_semantic(diff) {
  // Reduce the number of edits by eliminating semantically trivial equalities.
  var changes = false;
  var equalities = []; // Stack of indices where equalities are found.
  var lastequality = null; // Always equal to equalities[equalities.length-1][1]
  var pointer = 0; // Index of current position.
  var length_changes1 = 0; // Number of characters that changed prior to the equality.
  var length_changes2 = 0; // Number of characters that changed after the equality.
  while (pointer < diff.length) {
    if (diff[pointer][0] == 0) { // equality found
      equalities.push(pointer);
      length_changes1 = length_changes2;
      length_changes2 = 0;
      lastequality = diff[pointer][1];
    } else { // an insertion or deletion
      length_changes2 += diff[pointer][1].length;
      if (lastequality != null && (lastequality.length <= length_changes1) && (lastequality.length <= length_changes2)) {
        //alert("Splitting: '"+lastequality+"'");
        diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record
        diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.
        equalities.pop();  // Throw away the equality we just deleted;
        equalities.pop();  // Throw away the previous equality;
        pointer = equalities.length ? equalities[equalities.length-1] : -1;
        length_changes1 = 0; // Reset the counters.
        length_changes2 = 0;
        lastequality = null;
        changes = true;
      }
    }
    pointer++;
  }

  if (changes)
    diff_cleanup_merge(diff);
}


function diff_cleanup_efficiency(diff) {
  // Reduce the number of edits by eliminating operationally trivial equalities.
  var changes = false;
  var equalities = []; // Stack of indices where equalities are found.
  var lastequality = ''; // Always equal to equalities[equalities.length-1][1]
  var pointer = 0; // Index of current position.
  var pre_ins = false; // Is there an insertion operation before the last equality.
  var pre_del = false; // Is there an deletion operation before the last equality.
  var post_ins = false; // Is there an insertion operation after the last equality.
  var post_del = false; // Is there an deletion operation after the last equality.
  while (pointer < diff.length) {
    if (diff[pointer][0] == 0) { // equality found
      if (diff[pointer][1].length < DIFF_EDIT_COST && (post_ins || post_del)) {
        // Candidate found.
        equalities.push(pointer);
        pre_ins = post_ins;
        pre_del = post_del;
        lastequality = diff[pointer][1];
      } else {
        // Not a candidate, and can never become one.
        equalities = [];
        lastequality = '';
      }
      post_ins = post_del = false;
    } else { // an insertion or deletion
      if (diff[pointer][0] == -1)
        post_del = true;
      else
        post_ins = true;
      // Five types to be split:
      // <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
      // <ins>A</ins>X<ins>C</ins><del>D</del>
      // <ins>A</ins><del>B</del>X<ins>C</ins>
      // <ins>A</del>X<ins>C</ins><del>D</del>
      // <ins>A</ins><del>B</del>X<del>C</del>
      if (lastequality && ((pre_ins && pre_del && post_ins && post_del) || ((lastequality.length < DIFF_EDIT_COST/2) && (pre_ins + pre_del + post_ins + post_del) == 3))) {
        //alert("Splitting: '"+lastequality+"'");
        diff.splice(equalities[equalities.length-1], 0, [-1, lastequality]); // Duplicate record
        diff[equalities[equalities.length-1]+1][0] = 1; // Change second copy to insert.
        equalities.pop();  // Throw away the equality we just deleted;
        lastequality = '';
        if (pre_ins && pre_del) {
          // No changes made which could affect previous entry, keep going.
          post_ins = post_del = true;
          equalities = [];
        } else {
          equalities.pop();  // Throw away the previous equality;
          pointer = equalities.length ? equalities[equalities.length-1] : -1;
          post_ins = post_del = false;
        }
        changes = true;
      }
    }
    pointer++;
  }

  if (changes)
    diff_cleanup_merge(diff);
}


function diff_cleanup_merge(diff) {
  // Reorder and merge like edit sections.  Merge equalities.
  // Any edit section can move as long as it doesn't cross an equality.
  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 = '';
  var record_insert, record_delete;
  var my_xfix;
  while(pointer < diff.length) {
    if (diff[pointer][0] == 1) {
      count_insert++;
      text_insert += diff[pointer][1];
      pointer++;
    } else if (diff[pointer][0] == -1) {
      count_delete++;
      text_delete += diff[pointer][1];
      pointer++;
    } else {  // Upon reaching an equality, check for prior redundancies.
      if (count_delete > 1 || count_insert > 1) {
        if (count_delete > 1 && count_insert > 1) {
          // Factor out any common prefixies.
          my_xfix = diff_prefix(text_insert, text_delete);
          if (my_xfix[2] != '') {
            if ((pointer - count_delete - count_insert) > 0 && diff[pointer - count_delete - count_insert - 1][0] == 0) {
              text_insert = my_xfix[0];
              text_delete = my_xfix[1];
              diff[pointer - count_delete - count_insert - 1][1] += my_xfix[2];
            }
          }
          // Factor out any common suffixies.
          my_xfix = diff_suffix(text_insert, text_delete);
          if (my_xfix[2] != '') {
            text_insert = my_xfix[0];
            text_delete = my_xfix[1];
            diff[pointer][1] = my_xfix[2] + diff[pointer][1];
          }
        }
        // Delete the offending records and add the merged ones.
        if (count_delete == 0)
          diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [1, text_insert]);
        else if (count_insert == 0)
          diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete]);
        else
          diff.splice(pointer - count_delete - count_insert, count_delete + count_insert, [-1, text_delete], [1, text_insert]);
        pointer = pointer - count_delete - count_insert + (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;
      } else if (pointer != 0 && diff[pointer-1][0] == 0) {
        // Merge this equality with the previous one.
        diff[pointer-1][1] += diff[pointer][1];
        diff.splice(pointer, 1);
      } else {
        pointer++;
      }
      count_insert = 0;
      count_delete = 0;
      text_delete = '';
      text_insert = '';
    }
  }
  if (diff[diff.length-1][1] == '')
    diff.pop();  // Remove the dummy entry at the end.
}


function diff_addindex(diff) {
  // Add an index to each tuple, represents where the tuple is located in text2.
  // e.g. [[-1, 'h', 0], [1, 'c', 0], [0, 'at', 1]]
  var i = 0;
  for (var x=0; x<diff.length; x++) {
    diff[x].push(i);
    if (diff[x][0] != -1)
      i += diff[x][1].length;
  }
}


function diff_xindex(diff, loc) {
  // loc is a location in text1, compute and return the equivalent location in text2.
  // e.g. "The cat" vs "The big cat", 1->1, 5->8
  var chars1 = 0;
  var chars2 = 0;
  var last_chars1 = 0;
  var last_chars2 = 0;
  for (var x=0; x<diff.length; x++) {
    if (diff[x][0] != 1) // Equality or deletion.
      chars1 += diff[x][1].length;
    if (diff[x][0] != -1) // Equality or insertion.
      chars2 += diff[x][1].length;
    if (chars1 > loc) // Overshot the location.
      break;
    last_chars1 = chars1;
    last_chars2 = chars2;
  }
  if (diff.length != x && diff[x][0] == -1) // The location was deleted.
    return last_chars2;
  // Add the remaining character length.
  return last_chars2 + (loc - last_chars1);
}


function diff_prettyhtml(diff) {
  // Convert a diff array into a pretty HTML report.
  diff_addindex(diff);
  var html = '';
  for (var x=0; x<diff.length; x++) {
    var m = diff[x][0]; // Mode (-1=delete, 0=copy, 1=add)
    var t = diff[x][1]; // Text of change.
    var i = diff[x][2]; // Index of change.
    t = t.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;");
    t = t.replace(/\n/g, "&para;<BR>");
    if (m == -1)
      html += "<DEL STYLE='background:#FFE6E6;' TITLE='i="+i+"'>"+t+"</DEL>";
    else if (m == 1)
      html += "<INS STYLE='background:#E6FFE6;' TITLE='i="+i+"'>"+t+"</INS>";
    else
      html += "<SPAN TITLE='i="+i+"'>"+t+"</SPAN>";
  }
  return html;
}


  //////////////////////////////////////////////////////////////////////
 //  Match                                                           //
//////////////////////////////////////////////////////////////////////


function match_getmaxbits() {
  // Compute the number of bits in an int.
  // The normal answer for JavaScript is 32.
  var maxbits = 0;
  var oldi = 1;
  var newi = 2;
  while (oldi != newi) {
    maxbits++;
    oldi = newi;
    newi = newi << 1;
  }
  return maxbits;
}
var MATCH_MAXBITS = match_getmaxbits();


function match_main(text, pattern, loc) {
  // Locate the best instance of 'pattern' in 'text' near 'loc'.
  loc = Math.max(0, Math.min(loc, text.length-pattern.length));
  if (text == pattern) {
    // Shortcut (potentially not guaranteed by the algorithm)
    return 0;
  } else if (text.length == 0) {
    // Nothing to match.
    return null;
  } else if (text.substring(loc, loc + pattern.length) == pattern) {
    // Perfect match at the perfect spot!  (Includes case of null pattern)
    return loc;
  } else {
    // Do a fuzzy compare.
    var match = match_bitap(text, pattern, loc);
    return match;
  }
}


function match_bitap(text, pattern, loc) {
  // Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm.
  if (pattern.length > MATCH_MAXBITS)
    return alert("Pattern too long for this browser.");

  // Initialise the alphabet.
  var s = match_alphabet(pattern);

  var score_text_length = text.length;
  // Coerce the text length between reasonable maximums and minimums.
  score_text_length = Math.max(score_text_length, MATCH_MINLENGTH);
  score_text_length = Math.min(score_text_length, MATCH_MAXLENGTH);

  function match_bitap_score (e, x) {
    // Compute and return the score for a match with e errors and x location.
    var d = Math.abs(loc-x);
    return (e / pattern.length / MATCH_BALANCE) + (d / score_text_length / (1.0 - MATCH_BALANCE));
  }

  // Highest score beyond which we give up.
  var score_threshold = MATCH_THRESHOLD;
  // Is there a nearby exact match? (speedup)
  var best_loc = text.indexOf(pattern, loc);
  if (best_loc != -1)
    score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);
  // What about in the other direction? (speedup)
  best_loc = text.lastIndexOf(pattern, loc+pattern.length);
  if (best_loc != -1)
    score_threshold = Math.min(match_bitap_score(0, best_loc), score_threshold);

  // Initialise the bit arrays.
  var r = Array();
  var d = -1;
  var matchmask = Math.pow(2, pattern.length-1);
  best_loc = null;

  var bin_min, bin_mid;
  var bin_max = Math.max(loc+loc, text.length);
  var last_rd;
  for (var d=0; d<pattern.length; d++) {
    // Scan for the best match; each iteration allows for one more error.
    var rd = Array(text.length);

    // Run a binary search to determine how far from 'loc' we can stray at this error level.
    bin_min = loc;
    bin_mid = bin_max;
    while(bin_min < bin_mid) {
      if (match_bitap_score(d, bin_mid) < score_threshold)
        bin_min = bin_mid;
      else
        bin_max = bin_mid;
      bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);
    }