diff.js

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

    bin_max = bin_mid; // Use the result from this iteration as the maximum for the next.
    var start = Math.max(0, loc - (bin_mid - loc) - 1);
    var finish = Math.min(text.length-1, pattern.length + bin_mid);

    if (text.charAt(finish) == pattern.charAt(pattern.length-1))
      rd[finish] = Math.pow(2, d+1)-1;
    else
      rd[finish] = Math.pow(2, d)-1;
    for (var j=finish-1; j>=start; j--) {
      // The alphabet (s) is a sparse hash, so the following lines generate warnings.
      if (d == 0) // First pass: exact match.
        rd[j] = ((rd[j+1] << 1) | 1) & s[text.charAt(j)];
      else // Subsequent passes: fuzzy match.
        rd[j] = ((rd[j+1] << 1) | 1) & s[text.charAt(j)] | ((last_rd[j+1] << 1) | 1) | ((last_rd[j] << 1) | 1) | last_rd[j+1];
      if (rd[j] & matchmask) {
        var score = match_bitap_score(d, j);
        // This match will almost certainly be better than any existing match.  But check anyway.
        if (score <= score_threshold) {
          // Told you so.
          score_threshold = score;
          best_loc = j;
          if (j > loc) {
            // When passing loc, don't exceed our current distance from loc.
            start = Math.max(0, loc - (j - loc));
          } else {
            // Already passed loc, downhill from here on in.
            break;
          }
        }
      }
    }
    if (match_bitap_score(d+1, loc) > score_threshold) // No hope for a (better) match at greater error levels.
      break;
    last_rd = rd;
  }
  return best_loc;
}


function match_alphabet(pattern) {
  // Initialise the alphabet for the Bitap algorithm.
  var s = Object();
  for (var i=0; i<pattern.length; i++)
    s[pattern.charAt(i)] = 0;
  for (var i=0; i<pattern.length; i++)
    s[pattern.charAt(i)] |= Math.pow(2, pattern.length-i-1);
  return s;
}


  //////////////////////////////////////////////////////////////////////
 //  Patch                                                           //
//////////////////////////////////////////////////////////////////////


function patch_obj() {
  // Constructor for a patch object.
  this.diffs = [];
  this.start1 = null;
  this.start2 = null;
  this.length1 = 0;
  this.length2 = 0;

  this.toString = function() {
    // Emmulate GNU diff's format.
    // Header: @@ -382,8 +481,9 @@
    // Indicies are printed as 1-based, not 0-based.
    var coords1, coords2;
    if (this.length1 == 0)
      coords1 = this.start1+",0";
    else if (this.length1 == 1)
      coords1 = this.start1+1;
    else
      coords1 = (this.start1+1)+","+this.length1;
    if (this.length2 == 0)
      coords2 = this.start2+",0";
    else if (this.length2 == 1)
      coords2 = this.start2+1;
    else
      coords2 = (this.start2+1)+","+this.length2;
    var txt = "@@ -"+coords1+" +"+coords2+" @@\n";
    // Escape the body of the patch with %xx notation.
    for (var x=0; x<this.diffs.length; x++)
      txt += ("- +".charAt(this.diffs[x][0]+1)) + encodeURI(this.diffs[x][1]) + "\n";
    return txt.replace(/%20/g, ' ');
  }

  this.text1 = function() {
    // Compute and return the source text (all equalities and deletions).
    var txt = '';
    for (var x=0; x<this.diffs.length; x++)
      if (this.diffs[x][0] == 0 || this.diffs[x][0] == -1)
        txt += this.diffs[x][1];
    return txt;
  }

  this.text2 = function() {
    // Compute and return the destination text (all equalities and insertions).
    var txt = '';
    for (var x=0; x<this.diffs.length; x++)
      if (this.diffs[x][0] == 0 || this.diffs[x][0] == 1)
        txt += this.diffs[x][1];
    return txt;
  }
}


function patch_addcontext(patch, text) {
  var pattern = text.substring(patch.start2, patch.start2+patch.length1);
  var padding = 0;
  // Increase the context until we're unique (but don't let the pattern expand beyond MATCH_MAXBITS).
  while (text.indexOf(pattern) != text.lastIndexOf(pattern) && pattern.length < MATCH_MAXBITS-PATCH_MARGIN-PATCH_MARGIN) {
    padding += PATCH_MARGIN;
    pattern = text.substring(patch.start2 - padding, patch.start2+patch.length1 + padding);
  }
  // Add one chunk for good luck.
  padding += PATCH_MARGIN;
  // Add the prefix.
  var prefix = text.substring(patch.start2 - padding, patch.start2);
  if (prefix != '')
    patch.diffs.unshift([0, prefix]);
  // Add the suffix
  var suffix = text.substring(patch.start2+patch.length1, patch.start2+patch.length1 + padding);
  if (suffix != '')
    patch.diffs.push([0, suffix]);

  // Roll back the start points.
  patch.start1 -= prefix.length;
  patch.start2 -= prefix.length;
  // Extend the lengths.
  patch.length1 += prefix.length + suffix.length;
  patch.length2 += prefix.length + suffix.length;
}


function patch_make(text1, text2, diff) {
  // Compute a list of patches to turn text1 into text2.
  // Use diff if provided, otherwise compute it ourselves.
  if (typeof diff == 'undefined') {
    diff = diff_main(text1, text2, true);
    if (diff.length > 2) {
      diff_cleanup_semantic(diff);
      diff_cleanup_efficiency(diff);
    }
  }
  if (diff.length == 0)
    return []; // Get rid of the null case.
  var patches = [];
  var patch = new patch_obj();
  var char_count1 = 0; // Number of characters into the text1 string.
  var char_count2 = 0; // Number of characters into the text2 string.
  var last_type = null;
  var prepatch_text = text1; // Recreate the patches to determine context info.
  var postpatch_text = text1;
  for (var x=0; x<diff.length; x++) {
    var diff_type = diff[x][0];
    var diff_text = diff[x][1];

    if (patch.diffs.length == 0 && diff_type != 0) {
      // A new patch starts here.
      patch.start1 = char_count1;
      patch.start2 = char_count2;
    }

    if (diff_type == 1) {
      // Insertion
      patch.diffs.push(diff[x]);
      patch.length2 += diff_text.length;
      postpatch_text = postpatch_text.substring(0, char_count2) + diff_text + postpatch_text.substring(char_count2);
    } else if (diff_type == -1) {
      // Deletion.
      patch.length1 += diff_text.length;
      patch.diffs.push(diff[x]);
      postpatch_text = postpatch_text.substring(0, char_count2) + postpatch_text.substring(char_count2 + diff_text.length);
    } else if (diff_type == 0 && diff_text.length <= 2*PATCH_MARGIN && patch.diffs.length != 0 && diff.length != x+1) {
      // Small equality inside a patch.
      patch.diffs.push(diff[x]);
      patch.length1 += diff_text.length;
      patch.length2 += diff_text.length;
    }

    last_type = diff_type;
    if (diff_type == 0 && diff_text.length >= 2*PATCH_MARGIN) {
      // Time for a new patch.
      if (patch.diffs.length != 0) {
        patch_addcontext(patch, prepatch_text);
        patches.push(patch);
        var patch = new patch_obj();
        last_type = null;
        prepatch_text = postpatch_text;
      }
    }

    // Update the current character count.
    if (diff_type != 1)
      char_count1 += diff_text.length;
    if (diff_type != -1)
      char_count2 += diff_text.length;
  }
  // Pick up the leftover patch if not empty.
  if (patch.diffs.length != 0) {
    patch_addcontext(patch, prepatch_text);
    patches.push(patch);
  }

  return patches;
}


function patch_apply(patches, text) {
  // Merge a set of patches onto the text.
  // Return a patched text, as well as a list of true/false values indicating which patches were applied.
  patch_splitmax(patches);
  var results = [];
  var delta = 0;
  var expected_loc, start_loc;
  var text1, text2;
  var diff, mod, index1, index2;
  for (var x=0; x<patches.length; x++) {
    expected_loc = patches[x].start2 + delta;
    text1 = patches[x].text1();
    start_loc = match_main(text, text1, expected_loc);
    if (start_loc == null) {
      // No match found.  :(
      results.push(false);
    } else {
      // Found a match.  :)
      results.push(true);
      delta = start_loc - expected_loc;
      text2 = text.substring(start_loc, start_loc + text1.length);
      if (text1 == text2) {
        // Perfect match, just shove the replacement text in.
        text = text.substring(0, start_loc) + patches[x].text2() + text.substring(start_loc + text1.length);
      } else {
        // Imperfect match.  Run a diff to get a framework of equivalent indicies.
        diff = diff_main(text1, text2, false);
        index1 = 0;
        for (var y=0; y<patches[x].diffs.length; y++) {
          mod = patches[x].diffs[y];
          if (mod[0] != 0)
            index2 = diff_xindex(diff, index1);
          if (mod[0] == 1) // Insertion
            text = text.substring(0, start_loc + index2) + mod[1] + text.substring(start_loc + index2);
          else if (mod[0] == -1) // Deletion
            text = text.substring(0, start_loc + index2) + text.substring(start_loc + diff_xindex(diff, index1 + mod[1].length));
          if (mod[0] != -1)
            index1 += mod[1].length;
        }
      }
    }
  }
  return [text, results];
}


function patch_splitmax(patches) {
  // Look through the patches and break up any which are longer than the maximum limit of the match algorithm.
  var bigpatch, patch, patch_size, start1, start2, diff_type, diff_text, precontext, postcontext, empty;
  for (var x=0; x<patches.length; x++) {
    if (patches[x].length1 > MATCH_MAXBITS) {
      bigpatch = patches[x];
      // Remove the big old patch.
      patches.splice(x, 1);
      patch_size = MATCH_MAXBITS;
      start1 = bigpatch.start1;
      start2 = bigpatch.start2;
      precontext = '';
      while (bigpatch.diffs.length != 0) {
        // Create one of several smaller patches.
        patch = new patch_obj();
        empty = true;
        patch.start1 = start1 - precontext.length;
        patch.start2 = start2 - precontext.length;
        if (precontext  != '') {
          patch.length1 = patch.length2 = precontext.length;
          patch.diffs.push([0, precontext]);
        }
        while (bigpatch.diffs.length != 0 && patch.length1 < patch_size - PATCH_MARGIN) {
          diff_type = bigpatch.diffs[0][0];
          diff_text = bigpatch.diffs[0][1];
          if (diff_type == 1) {
            // Insertions are harmless.
            patch.length2 += diff_text.length;
            start2 += diff_text.length;
            patch.diffs.push(bigpatch.diffs.shift());
            empty = false;
          } else {
            // Deletion or equality.  Only take as much as we can stomach.
            diff_text = diff_text.substring(0, patch_size - patch.length1 - PATCH_MARGIN);
            patch.length1 += diff_text.length;
            start1 += diff_text.length;
            if (diff_type == 0) {
              patch.length2 += diff_text.length;
              start2 += diff_text.length;
            } else {
              empty = false;
            }
            patch.diffs.push([diff_type, diff_text]);
            if (diff_text == bigpatch.diffs[0][1])
              bigpatch.diffs.shift();
            else
              bigpatch.diffs[0][1] = bigpatch.diffs[0][1].substring(diff_text.length);
          }
        }
        // Compute the head context for the next patch.
        precontext = patch.text2();
        precontext = precontext.substring(precontext.length - PATCH_MARGIN);
        // Append the end context for this patch.
        postcontext = bigpatch.text1().substring(0, PATCH_MARGIN);
        if (postcontext  != '') {
          patch.length1 += postcontext.length;
          patch.length2 += postcontext.length;
          if (patch.diffs.length > 0 && patch.diffs[patch.diffs.length-1][0] == 0)
            patch.diffs[patch.diffs.length-1][1] += postcontext;
          else
            patch.diffs.push([0, postcontext]);
        }
        if (!empty)
          patches.splice(x++, 0, patch);
      }
    }
  }
}


function patch_totext(patches) {
  // Take a list of patches and return a textual representation.
  var text = '';
  for (var x=0; x<patches.length; x++)
    text += patches[x];
  return text;
}


function patch_fromtext(text) {
  // Take a textual representation of patches and return a list of patch objects.
  var patches = [];
  text = text.split('\n');
  var patch, m, chars1, chars2, sign, line;
  while (text.length != 0) {
    m = text[0].match(/^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/);
    if (!m)
      return alert("Invalid patch string:\n"+text[0]);
    patch = new patch_obj();
    patches.push(patch);
    patch.start1 = parseInt(m[1]);
    if (m[2] == '') {
      patch.start1--;
      patch.length1 = 1;
    } else if (m[2] == '0') {
      patch.length1 = 0;
    } else {
      patch.start1--;
      patch.length1 = parseInt(m[2]);
    }

    patch.start2 = parseInt(m[3]);
    if (m[4] == '') {
      patch.start2--;
      patch.length2 = 1;
    } else if (m[4] == '0') {
      patch.length2 = 0;
    } else {
      patch.start2--;
      patch.length2 = parseInt(m[4]);
    }
    text.shift();

    while (text.length != 0) {
      sign = text[0].charAt(0);
      line = decodeURIComponent(text[0].substring(1));
      if (sign == '-') {
        // Deletion.
        patch.diffs.push([-1, line]);
      } else if (sign == '+') {
        // Insertion.
        patch.diffs.push([1, line]);
      } else if (sign == ' ') {
        // Minor equality.
        patch.diffs.push([0, line]);
      } else if (sign == '@') {
        // Start of next patch.
        break;
      } else if (sign == '') {
        // Blank line?  Whatever.
      } else {
        // WTF?
        return alert("Invalid patch mode: '"+sign+"'\n"+line);
      }
      text.shift();
    }
  }
  return patches;
}

// EOF