1
/*
2
 *  This file is part of CoCalc: However, the license is Apache V2, exactly as
3
 *  for the original upstream code.   We have barely changed it.  -- William Stein
4
 */
5

6
/**
7
 * Diff Match and Patch
8
 * Copyright 2018 The diff-match-patch Authors.
9
 * https://github.com/google/diff-match-patch
10
 *
11
 * Licensed under the Apache License, Version 2.0 (the "License");
12
 * you may not use this file except in compliance with the License.
13
 * You may obtain a copy of the License at
14
 *
15
 *   http://www.apache.org/licenses/LICENSE-2.0
16
 *
17
 * Unless required by applicable law or agreed to in writing, software
18
 * distributed under the License is distributed on an "AS IS" BASIS,
19
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20
 * See the License for the specific language governing permissions and
21
 * limitations under the License.
22
 */
23

24
/**
25
 * @fileoverview Computes the difference between two texts to create a patch.
26
 * Applies the patch onto another text, allowing for errors.
27
 * @author [email protected] (Neil Fraser)
28
 */
29

30
/**
31
 * Class containing the diff, match and patch methods.
32
 * @constructor
33
 */
34

35
export const diff_match_patch = function () {
36
  // Defaults.
37
  // Redefine these in your program to override the defaults.
38

39
  // Number of seconds to map a diff before giving up (0 for infinity).
40
  this.Diff_Timeout = 1.0;
41
  // Cost of an empty edit operation in terms of edit characters.
42
  this.Diff_EditCost = 4;
43
  // At what point is no match declared (0.0 = perfection, 1.0 = very loose).
44
  this.Match_Threshold = 0.5;
45
  // How far to search for a match (0 = exact location, 1000+ = broad match).
46
  // A match this many characters away from the expected location will add
47
  // 1.0 to the score (0.0 is a perfect match).
48
  this.Match_Distance = 1000;
49
  // When deleting a large block of text (over ~64 characters), how close do
50
  // the contents have to be to match the expected contents. (0.0 = perfection,
51
  // 1.0 = very loose).  Note that Match_Threshold controls how closely the
52
  // end points of a delete need to match.
53
  this.Patch_DeleteThreshold = 0.5;
54
  // Chunk size for context length.
55
  this.Patch_Margin = 4;
56

57
  // The number of bits in an int.
58
  this.Match_MaxBits = 32;
59
};
60

61
//  DIFF FUNCTIONS
62

63
/**
64
 * The data structure representing a diff is an array of tuples:
65
 * [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']]
66
 * which means: delete 'Hello', add 'Goodbye' and keep ' world.'
67
 */
68
export const DIFF_DELETE = -1;
69
export const DIFF_INSERT = 1;
70
export const DIFF_EQUAL = 0;
71

72
/**
73
 * Class representing one diff tuple.
74
 * Attempts to look like a two-element array (which is what this used to be).
75
 * @param {number} op Operation, one of: DIFF_DELETE, DIFF_INSERT, DIFF_EQUAL.
76
 * @param {string} text Text to be deleted, inserted, or retained.
77
 * @constructor
78
 */
79
diff_match_patch.Diff = function (op, text) {
80
  this[0] = op;
81
  this[1] = text;
82
};
83

84
diff_match_patch.Diff.prototype.length = 2;
85

86
/**
87
 * Emulate the output of a two-element array.
88
 * @return {string} Diff operation as a string.
89
 */
90
diff_match_patch.Diff.prototype.toString = function () {
91
  return this[0] + "," + this[1];
92
};
93

94
/**
95
 * Find the differences between two texts.  Simplifies the problem by stripping
96
 * any common prefix or suffix off the texts before diffing.
97
 * @param {string} text1 Old string to be diffed.
98
 * @param {string} text2 New string to be diffed.
99
 * @param {boolean=} opt_checklines Optional speedup flag. If present and false,
100
 *     then don't run a line-level diff first to identify the changed areas.
101
 *     Defaults to true, which does a faster, slightly less optimal diff.
102
 * @param {number=} opt_deadline Optional time when the diff should be complete
103
 *     by.  Used internally for recursive calls.  Users should set DiffTimeout
104
 *     instead.
105
 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.
106
 */
107
diff_match_patch.prototype.diff_main = function (
108
  text1,
109
  text2,
110
  opt_checklines,
111
  opt_deadline,
112
) {
113
  // Set a deadline by which time the diff must be complete.
114
  if (typeof opt_deadline == "undefined") {
115
    if (this.Diff_Timeout <= 0) {
116
      opt_deadline = Number.MAX_VALUE;
117
    } else {
118
      opt_deadline = new Date().getTime() + this.Diff_Timeout * 1000;
119
    }
120
  }
121
  var deadline = opt_deadline;
122

123
  // Check for null inputs.
124
  if (text1 == null || text2 == null) {
125
    throw new Error("Null input. (diff_main)");
126
  }
127

128
  // Check for equality (speedup).
129
  if (text1 == text2) {
130
    if (text1) {
131
      return [new diff_match_patch.Diff(DIFF_EQUAL, text1)];
132
    }
133
    return [];
134
  }
135

136
  if (typeof opt_checklines == "undefined") {
137
    opt_checklines = true;
138
  }
139
  var checklines = opt_checklines;
140

141
  // Trim off common prefix (speedup).
142
  var commonlength = this.diff_commonPrefix(text1, text2);
143
  var commonprefix = text1.substring(0, commonlength);
144
  text1 = text1.substring(commonlength);
145
  text2 = text2.substring(commonlength);
146

147
  // Trim off common suffix (speedup).
148
  commonlength = this.diff_commonSuffix(text1, text2);
149
  var commonsuffix = text1.substring(text1.length - commonlength);
150
  text1 = text1.substring(0, text1.length - commonlength);
151
  text2 = text2.substring(0, text2.length - commonlength);
152

153
  // Compute the diff on the middle block.
154
  var diffs = this.diff_compute_(text1, text2, checklines, deadline);
155

156
  // Restore the prefix and suffix.
157
  if (commonprefix) {
158
    diffs.unshift(new diff_match_patch.Diff(DIFF_EQUAL, commonprefix));
159
  }
160
  if (commonsuffix) {
161
    diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, commonsuffix));
162
  }
163
  this.diff_cleanupMerge(diffs);
164
  return diffs;
165
};
166

167
/**
168
 * Find the differences between two texts.  Assumes that the texts do not
169
 * have any common prefix or suffix.
170
 * @param {string} text1 Old string to be diffed.
171
 * @param {string} text2 New string to be diffed.
172
 * @param {boolean} checklines Speedup flag.  If false, then don't run a
173
 *     line-level diff first to identify the changed areas.
174
 *     If true, then run a faster, slightly less optimal diff.
175
 * @param {number} deadline Time when the diff should be complete by.
176
 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.
177
 * @private
178
 */
179
diff_match_patch.prototype.diff_compute_ = function (
180
  text1,
181
  text2,
182
  checklines,
183
  deadline,
184
) {
185
  var diffs;
186

187
  if (!text1) {
188
    // Just add some text (speedup).
189
    return [new diff_match_patch.Diff(DIFF_INSERT, text2)];
190
  }
191

192
  if (!text2) {
193
    // Just delete some text (speedup).
194
    return [new diff_match_patch.Diff(DIFF_DELETE, text1)];
195
  }
196

197
  var longtext = text1.length > text2.length ? text1 : text2;
198
  var shorttext = text1.length > text2.length ? text2 : text1;
199
  var i = longtext.indexOf(shorttext);
200
  if (i != -1) {
201
    // Shorter text is inside the longer text (speedup).
202
    diffs = [
203
      new diff_match_patch.Diff(DIFF_INSERT, longtext.substring(0, i)),
204
      new diff_match_patch.Diff(DIFF_EQUAL, shorttext),
205
      new diff_match_patch.Diff(
206
        DIFF_INSERT,
207
        longtext.substring(i + shorttext.length),
208
      ),
209
    ];
210
    // Swap insertions for deletions if diff is reversed.
211
    if (text1.length > text2.length) {
212
      diffs[0][0] = diffs[2][0] = DIFF_DELETE;
213
    }
214
    return diffs;
215
  }
216

217
  if (shorttext.length == 1) {
218
    // Single character string.
219
    // After the previous speedup, the character can't be an equality.
220
    return [
221
      new diff_match_patch.Diff(DIFF_DELETE, text1),
222
      new diff_match_patch.Diff(DIFF_INSERT, text2),
223
    ];
224
  }
225

226
  // Check to see if the problem can be split in two.
227
  var hm = this.diff_halfMatch_(text1, text2);
228
  if (hm) {
229
    // A half-match was found, sort out the return data.
230
    var text1_a = hm[0];
231
    var text1_b = hm[1];
232
    var text2_a = hm[2];
233
    var text2_b = hm[3];
234
    var mid_common = hm[4];
235
    // Send both pairs off for separate processing.
236
    var diffs_a = this.diff_main(text1_a, text2_a, checklines, deadline);
237
    var diffs_b = this.diff_main(text1_b, text2_b, checklines, deadline);
238
    // Merge the results.
239
    return diffs_a.concat(
240
      [new diff_match_patch.Diff(DIFF_EQUAL, mid_common)],
241
      diffs_b,
242
    );
243
  }
244

245
  if (checklines && text1.length > 100 && text2.length > 100) {
246
    return this.diff_lineMode_(text1, text2, deadline);
247
  }
248

249
  return this.diff_bisect_(text1, text2, deadline);
250
};
251

252
/**
253
 * Do a quick line-level diff on both strings, then rediff the parts for
254
 * greater accuracy.
255
 * This speedup can produce non-minimal diffs.
256
 * @param {string} text1 Old string to be diffed.
257
 * @param {string} text2 New string to be diffed.
258
 * @param {number} deadline Time when the diff should be complete by.
259
 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.
260
 * @private
261
 */
262
diff_match_patch.prototype.diff_lineMode_ = function (text1, text2, deadline) {
263
  // Scan the text on a line-by-line basis first.
264
  var a = this.diff_linesToChars_(text1, text2);
265
  text1 = a.chars1;
266
  text2 = a.chars2;
267
  var linearray = a.lineArray;
268

269
  var diffs = this.diff_main(text1, text2, false, deadline);
270

271
  // Convert the diff back to original text.
272
  this.diff_charsToLines_(diffs, linearray);
273
  // Eliminate freak matches (e.g. blank lines)
274
  this.diff_cleanupSemantic(diffs);
275

276
  // Rediff any replacement blocks, this time character-by-character.
277
  // Add a dummy entry at the end.
278
  diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, ""));
279
  var pointer = 0;
280
  var count_delete = 0;
281
  var count_insert = 0;
282
  var text_delete = "";
283
  var text_insert = "";
284
  while (pointer < diffs.length) {
285
    switch (diffs[pointer][0]) {
286
      case DIFF_INSERT:
287
        count_insert++;
288
        text_insert += diffs[pointer][1];
289
        break;
290
      case DIFF_DELETE:
291
        count_delete++;
292
        text_delete += diffs[pointer][1];
293
        break;
294
      case DIFF_EQUAL:
295
        // Upon reaching an equality, check for prior redundancies.
296
        if (count_delete >= 1 && count_insert >= 1) {
297
          // Delete the offending records and add the merged ones.
298
          diffs.splice(
299
            pointer - count_delete - count_insert,
300
            count_delete + count_insert,
301
          );
302
          pointer = pointer - count_delete - count_insert;
303
          var subDiff = this.diff_main(
304
            text_delete,
305
            text_insert,
306
            false,
307
            deadline,
308
          );
309
          for (var j = subDiff.length - 1; j >= 0; j--) {
310
            diffs.splice(pointer, 0, subDiff[j]);
311
          }
312
          pointer = pointer + subDiff.length;
313
        }
314
        count_insert = 0;
315
        count_delete = 0;
316
        text_delete = "";
317
        text_insert = "";
318
        break;
319
    }
320
    pointer++;
321
  }
322
  diffs.pop(); // Remove the dummy entry at the end.
323

324
  return diffs;
325
};
326

327
/**
328
 * Find the 'middle snake' of a diff, split the problem in two
329
 * and return the recursively constructed diff.
330
 * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.
331
 * @param {string} text1 Old string to be diffed.
332
 * @param {string} text2 New string to be diffed.
333
 * @param {number} deadline Time at which to bail if not yet complete.
334
 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.
335
 * @private
336
 */
337
diff_match_patch.prototype.diff_bisect_ = function (text1, text2, deadline) {
338
  // Cache the text lengths to prevent multiple calls.
339
  var text1_length = text1.length;
340
  var text2_length = text2.length;
341
  var max_d = Math.ceil((text1_length + text2_length) / 2);
342
  var v_offset = max_d;
343
  var v_length = 2 * max_d;
344
  var v1 = new Array(v_length);
345
  var v2 = new Array(v_length);
346
  // Setting all elements to -1 is faster in Chrome & Firefox than mixing
347
  // integers and undefined.
348
  for (var x = 0; x < v_length; x++) {
349
    v1[x] = -1;
350
    v2[x] = -1;
351
  }
352
  v1[v_offset + 1] = 0;
353
  v2[v_offset + 1] = 0;
354
  var delta = text1_length - text2_length;
355
  // If the total number of characters is odd, then the front path will collide
356
  // with the reverse path.
357
  var front = delta % 2 != 0;
358
  // Offsets for start and end of k loop.
359
  // Prevents mapping of space beyond the grid.
360
  var k1start = 0;
361
  var k1end = 0;
362
  var k2start = 0;
363
  var k2end = 0;
364
  for (var d = 0; d < max_d; d++) {
365
    // Bail out if deadline is reached.
366
    if (new Date().getTime() > deadline) {
367
      break;
368
    }
369

370
    // Walk the front path one step.
371
    for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
372
      var k1_offset = v_offset + k1;
373
      var x1;
374
      if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
375
        x1 = v1[k1_offset + 1];
376
      } else {
377
        x1 = v1[k1_offset - 1] + 1;
378
      }
379
      var y1 = x1 - k1;
380
      while (
381
        x1 < text1_length &&
382
        y1 < text2_length &&
383
        text1.charAt(x1) == text2.charAt(y1)
384
      ) {
385
        x1++;
386
        y1++;
387
      }
388
      v1[k1_offset] = x1;
389
      if (x1 > text1_length) {
390
        // Ran off the right of the graph.
391
        k1end += 2;
392
      } else if (y1 > text2_length) {
393
        // Ran off the bottom of the graph.
394
        k1start += 2;
395
      } else if (front) {
396
        var k2_offset = v_offset + delta - k1;
397
        if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
398
          // Mirror x2 onto top-left coordinate system.
399
          var x2 = text1_length - v2[k2_offset];
400
          if (x1 >= x2) {
401
            // Overlap detected.
402
            return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);
403
          }
404
        }
405
      }
406
    }
407

408
    // Walk the reverse path one step.
409
    for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
410
      var k2_offset = v_offset + k2;
411
      var x2;
412
      if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
413
        x2 = v2[k2_offset + 1];
414
      } else {
415
        x2 = v2[k2_offset - 1] + 1;
416
      }
417
      var y2 = x2 - k2;
418
      while (
419
        x2 < text1_length &&
420
        y2 < text2_length &&
421
        text1.charAt(text1_length - x2 - 1) ==
422
          text2.charAt(text2_length - y2 - 1)
423
      ) {
424
        x2++;
425
        y2++;
426
      }
427
      v2[k2_offset] = x2;
428
      if (x2 > text1_length) {
429
        // Ran off the left of the graph.
430
        k2end += 2;
431
      } else if (y2 > text2_length) {
432
        // Ran off the top of the graph.
433
        k2start += 2;
434
      } else if (!front) {
435
        var k1_offset = v_offset + delta - k2;
436
        if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
437
          var x1 = v1[k1_offset];
438
          var y1 = v_offset + x1 - k1_offset;
439
          // Mirror x2 onto top-left coordinate system.
440
          x2 = text1_length - x2;
441
          if (x1 >= x2) {
442
            // Overlap detected.
443
            return this.diff_bisectSplit_(text1, text2, x1, y1, deadline);
444
          }
445
        }
446
      }
447
    }
448
  }
449
  // Diff took too long and hit the deadline or
450
  // number of diffs equals number of characters, no commonality at all.
451
  return [
452
    new diff_match_patch.Diff(DIFF_DELETE, text1),
453
    new diff_match_patch.Diff(DIFF_INSERT, text2),
454
  ];
455
};
456

457
/**
458
 * Given the location of the 'middle snake', split the diff in two parts
459
 * and recurse.
460
 * @param {string} text1 Old string to be diffed.
461
 * @param {string} text2 New string to be diffed.
462
 * @param {number} x Index of split point in text1.
463
 * @param {number} y Index of split point in text2.
464
 * @param {number} deadline Time at which to bail if not yet complete.
465
 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.
466
 * @private
467
 */
468
diff_match_patch.prototype.diff_bisectSplit_ = function (
469
  text1,
470
  text2,
471
  x,
472
  y,
473
  deadline,
474
) {
475
  var text1a = text1.substring(0, x);
476
  var text2a = text2.substring(0, y);
477
  var text1b = text1.substring(x);
478
  var text2b = text2.substring(y);
479

480
  // Compute both diffs serially.
481
  var diffs = this.diff_main(text1a, text2a, false, deadline);
482
  var diffsb = this.diff_main(text1b, text2b, false, deadline);
483

484
  return diffs.concat(diffsb);
485
};
486

487
/**
488
 * Split two texts into an array of strings.  Reduce the texts to a string of
489
 * hashes where each Unicode character represents one line.
490
 * @param {string} text1 First string.
491
 * @param {string} text2 Second string.
492
 * @return {{chars1: string, chars2: string, lineArray: !Array.<string>}}
493
 *     An object containing the encoded text1, the encoded text2 and
494
 *     the array of unique strings.
495
 *     The zeroth element of the array of unique strings is intentionally blank.
496
 * @private
497
 */
498
diff_match_patch.prototype.diff_linesToChars_ = function (text1, text2) {
499
  var lineArray = []; // e.g. lineArray[4] == 'Hello\n'
500
  var lineHash = {}; // e.g. lineHash['Hello\n'] == 4
501

502
  // '\x00' is a valid character, but various debuggers don't like it.
503
  // So we'll insert a junk entry to avoid generating a null character.
504
  lineArray[0] = "";
505

506
  /**
507
   * Split a text into an array of strings.  Reduce the texts to a string of
508
   * hashes where each Unicode character represents one line.
509
   * Modifies linearray and linehash through being a closure.
510
   * @param {string} text String to encode.
511
   * @return {string} Encoded string.
512
   * @private
513
   */
514
  function diff_linesToCharsMunge_(text) {
515
    var chars = "";
516
    // Walk the text, pulling out a substring for each line.
517
    // text.split('\n') would would temporarily double our memory footprint.
518
    // Modifying text would create many large strings to garbage collect.
519
    var lineStart = 0;
520
    var lineEnd = -1;
521
    // Keeping our own length variable is faster than looking it up.
522
    var lineArrayLength = lineArray.length;
523
    while (lineEnd < text.length - 1) {
524
      lineEnd = text.indexOf("\n", lineStart);
525
      if (lineEnd == -1) {
526
        lineEnd = text.length - 1;
527
      }
528
      var line = text.substring(lineStart, lineEnd + 1);
529

530
      if (
531
        lineHash.hasOwnProperty
532
          ? lineHash.hasOwnProperty(line)
533
          : lineHash[line] !== undefined
534
      ) {
535
        chars += String.fromCharCode(lineHash[line]);
536
      } else {
537
        if (lineArrayLength == maxLines) {
538
          // Bail out at 65535 because
539
          // String.fromCharCode(65536) == String.fromCharCode(0)
540
          line = text.substring(lineStart);
541
          lineEnd = text.length;
542
        }
543
        chars += String.fromCharCode(lineArrayLength);
544
        lineHash[line] = lineArrayLength;
545
        lineArray[lineArrayLength++] = line;
546
      }
547
      lineStart = lineEnd + 1;
548
    }
549
    return chars;
550
  }
551
  // Allocate 2/3rds of the space for text1, the rest for text2.
552
  var maxLines = 40000;
553
  var chars1 = diff_linesToCharsMunge_(text1);
554
  maxLines = 65535;
555
  var chars2 = diff_linesToCharsMunge_(text2);
556
  return { chars1: chars1, chars2: chars2, lineArray: lineArray };
557
};
558

559
/**
560
 * Rehydrate the text in a diff from a string of line hashes to real lines of
561
 * text.
562
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
563
 * @param {!Array.<string>} lineArray Array of unique strings.
564
 * @private
565
 */
566
diff_match_patch.prototype.diff_charsToLines_ = function (diffs, lineArray) {
567
  for (var i = 0; i < diffs.length; i++) {
568
    var chars = diffs[i][1];
569
    var text = [];
570
    for (var j = 0; j < chars.length; j++) {
571
      text[j] = lineArray[chars.charCodeAt(j)];
572
    }
573
    diffs[i][1] = text.join("");
574
  }
575
};
576

577
/**
578
 * Determine the common prefix of two strings.
579
 * @param {string} text1 First string.
580
 * @param {string} text2 Second string.
581
 * @return {number} The number of characters common to the start of each
582
 *     string.
583
 */
584
diff_match_patch.prototype.diff_commonPrefix = function (text1, text2) {
585
  // Quick check for common null cases.
586
  if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) {
587
    return 0;
588
  }
589
  // Binary search.
590
  // Performance analysis: https://neil.fraser.name/news/2007/10/09/
591
  var pointermin = 0;
592
  var pointermax = Math.min(text1.length, text2.length);
593
  var pointermid = pointermax;
594
  var pointerstart = 0;
595
  while (pointermin < pointermid) {
596
    if (
597
      text1.substring(pointerstart, pointermid) ==
598
      text2.substring(pointerstart, pointermid)
599
    ) {
600
      pointermin = pointermid;
601
      pointerstart = pointermin;
602
    } else {
603
      pointermax = pointermid;
604
    }
605
    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
606
  }
607
  return pointermid;
608
};
609

610
/**
611
 * Determine the common suffix of two strings.
612
 * @param {string} text1 First string.
613
 * @param {string} text2 Second string.
614
 * @return {number} The number of characters common to the end of each string.
615
 */
616
diff_match_patch.prototype.diff_commonSuffix = function (text1, text2) {
617
  // Quick check for common null cases.
618
  if (
619
    !text1 ||
620
    !text2 ||
621
    text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)
622
  ) {
623
    return 0;
624
  }
625
  // Binary search.
626
  // Performance analysis: https://neil.fraser.name/news/2007/10/09/
627
  var pointermin = 0;
628
  var pointermax = Math.min(text1.length, text2.length);
629
  var pointermid = pointermax;
630
  var pointerend = 0;
631
  while (pointermin < pointermid) {
632
    if (
633
      text1.substring(text1.length - pointermid, text1.length - pointerend) ==
634
      text2.substring(text2.length - pointermid, text2.length - pointerend)
635
    ) {
636
      pointermin = pointermid;
637
      pointerend = pointermin;
638
    } else {
639
      pointermax = pointermid;
640
    }
641
    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
642
  }
643
  return pointermid;
644
};
645

646
/**
647
 * Determine if the suffix of one string is the prefix of another.
648
 * @param {string} text1 First string.
649
 * @param {string} text2 Second string.
650
 * @return {number} The number of characters common to the end of the first
651
 *     string and the start of the second string.
652
 * @private
653
 */
654
diff_match_patch.prototype.diff_commonOverlap_ = function (text1, text2) {
655
  // Cache the text lengths to prevent multiple calls.
656
  var text1_length = text1.length;
657
  var text2_length = text2.length;
658
  // Eliminate the null case.
659
  if (text1_length == 0 || text2_length == 0) {
660
    return 0;
661
  }
662
  // Truncate the longer string.
663
  if (text1_length > text2_length) {
664
    text1 = text1.substring(text1_length - text2_length);
665
  } else if (text1_length < text2_length) {
666
    text2 = text2.substring(0, text1_length);
667
  }
668
  var text_length = Math.min(text1_length, text2_length);
669
  // Quick check for the worst case.
670
  if (text1 == text2) {
671
    return text_length;
672
  }
673

674
  // Start by looking for a single character match
675
  // and increase length until no match is found.
676
  // Performance analysis: https://neil.fraser.name/news/2010/11/04/
677
  var best = 0;
678
  var length = 1;
679
  while (true) {
680
    var pattern = text1.substring(text_length - length);
681
    var found = text2.indexOf(pattern);
682
    if (found == -1) {
683
      return best;
684
    }
685
    length += found;
686
    if (
687
      found == 0 ||
688
      text1.substring(text_length - length) == text2.substring(0, length)
689
    ) {
690
      best = length;
691
      length++;
692
    }
693
  }
694
};
695

696
/**
697
 * Do the two texts share a substring which is at least half the length of the
698
 * longer text?
699
 * This speedup can produce non-minimal diffs.
700
 * @param {string} text1 First string.
701
 * @param {string} text2 Second string.
702
 * @return {Array.<string>} Five element Array, containing the prefix of
703
 *     text1, the suffix of text1, the prefix of text2, the suffix of
704
 *     text2 and the common middle.  Or null if there was no match.
705
 * @private
706
 */
707
diff_match_patch.prototype.diff_halfMatch_ = function (text1, text2) {
708
  if (this.Diff_Timeout <= 0) {
709
    // Don't risk returning a non-optimal diff if we have unlimited time.
710
    return null;
711
  }
712
  var longtext = text1.length > text2.length ? text1 : text2;
713
  var shorttext = text1.length > text2.length ? text2 : text1;
714
  if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {
715
    return null; // Pointless.
716
  }
717
  var dmp = this; // 'this' becomes 'window' in a closure.
718

719
  /**
720
   * Does a substring of shorttext exist within longtext such that the substring
721
   * is at least half the length of longtext?
722
   * Closure, but does not reference any external variables.
723
   * @param {string} longtext Longer string.
724
   * @param {string} shorttext Shorter string.
725
   * @param {number} i Start index of quarter length substring within longtext.
726
   * @return {Array.<string>} Five element Array, containing the prefix of
727
   *     longtext, the suffix of longtext, the prefix of shorttext, the suffix
728
   *     of shorttext and the common middle.  Or null if there was no match.
729
   * @private
730
   */
731
  function diff_halfMatchI_(longtext, shorttext, i) {
732
    // Start with a 1/4 length substring at position i as a seed.
733
    var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));
734
    var j = -1;
735
    var best_common = "";
736
    var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;
737
    while ((j = shorttext.indexOf(seed, j + 1)) != -1) {
738
      var prefixLength = dmp.diff_commonPrefix(
739
        longtext.substring(i),
740
        shorttext.substring(j),
741
      );
742
      var suffixLength = dmp.diff_commonSuffix(
743
        longtext.substring(0, i),
744
        shorttext.substring(0, j),
745
      );
746
      if (best_common.length < suffixLength + prefixLength) {
747
        best_common =
748
          shorttext.substring(j - suffixLength, j) +
749
          shorttext.substring(j, j + prefixLength);
750
        best_longtext_a = longtext.substring(0, i - suffixLength);
751
        best_longtext_b = longtext.substring(i + prefixLength);
752
        best_shorttext_a = shorttext.substring(0, j - suffixLength);
753
        best_shorttext_b = shorttext.substring(j + prefixLength);
754
      }
755
    }
756
    if (best_common.length * 2 >= longtext.length) {
757
      return [
758
        best_longtext_a,
759
        best_longtext_b,
760
        best_shorttext_a,
761
        best_shorttext_b,
762
        best_common,
763
      ];
764
    } else {
765
      return null;
766
    }
767
  }
768

769
  // First check if the second quarter is the seed for a half-match.
770
  var hm1 = diff_halfMatchI_(
771
    longtext,
772
    shorttext,
773
    Math.ceil(longtext.length / 4),
774
  );
775
  // Check again based on the third quarter.
776
  var hm2 = diff_halfMatchI_(
777
    longtext,
778
    shorttext,
779
    Math.ceil(longtext.length / 2),
780
  );
781
  var hm;
782
  if (!hm1 && !hm2) {
783
    return null;
784
  } else if (!hm2) {
785
    hm = hm1;
786
  } else if (!hm1) {
787
    hm = hm2;
788
  } else {
789
    // Both matched.  Select the longest.
790
    hm = hm1[4].length > hm2[4].length ? hm1 : hm2;
791
  }
792

793
  // A half-match was found, sort out the return data.
794
  var text1_a, text1_b, text2_a, text2_b;
795
  if (text1.length > text2.length) {
796
    text1_a = hm[0];
797
    text1_b = hm[1];
798
    text2_a = hm[2];
799
    text2_b = hm[3];
800
  } else {
801
    text2_a = hm[0];
802
    text2_b = hm[1];
803
    text1_a = hm[2];
804
    text1_b = hm[3];
805
  }
806
  var mid_common = hm[4];
807
  return [text1_a, text1_b, text2_a, text2_b, mid_common];
808
};
809

810
/**
811
 * Reduce the number of edits by eliminating semantically trivial equalities.
812
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
813
 */
814
diff_match_patch.prototype.diff_cleanupSemantic = function (diffs) {
815
  var changes = false;
816
  var equalities = []; // Stack of indices where equalities are found.
817
  var equalitiesLength = 0; // Keeping our own length var is faster in JS.
818
  /** @type {?string} */
819
  var lastEquality = null;
820
  // Always equal to diffs[equalities[equalitiesLength - 1]][1]
821
  var pointer = 0; // Index of current position.
822
  // Number of characters that changed prior to the equality.
823
  var length_insertions1 = 0;
824
  var length_deletions1 = 0;
825
  // Number of characters that changed after the equality.
826
  var length_insertions2 = 0;
827
  var length_deletions2 = 0;
828
  while (pointer < diffs.length) {
829
    if (diffs[pointer][0] == DIFF_EQUAL) {
830
      // Equality found.
831
      equalities[equalitiesLength++] = pointer;
832
      length_insertions1 = length_insertions2;
833
      length_deletions1 = length_deletions2;
834
      length_insertions2 = 0;
835
      length_deletions2 = 0;
836
      lastEquality = diffs[pointer][1];
837
    } else {
838
      // An insertion or deletion.
839
      if (diffs[pointer][0] == DIFF_INSERT) {
840
        length_insertions2 += diffs[pointer][1].length;
841
      } else {
842
        length_deletions2 += diffs[pointer][1].length;
843
      }
844
      // Eliminate an equality that is smaller or equal to the edits on both
845
      // sides of it.
846
      if (
847
        lastEquality &&
848
        lastEquality.length <=
849
          Math.max(length_insertions1, length_deletions1) &&
850
        lastEquality.length <= Math.max(length_insertions2, length_deletions2)
851
      ) {
852
        // Duplicate record.
853
        diffs.splice(
854
          equalities[equalitiesLength - 1],
855
          0,
856
          new diff_match_patch.Diff(DIFF_DELETE, lastEquality),
857
        );
858
        // Change second copy to insert.
859
        diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;
860
        // Throw away the equality we just deleted.
861
        equalitiesLength--;
862
        // Throw away the previous equality (it needs to be reevaluated).
863
        equalitiesLength--;
864
        pointer = equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1;
865
        length_insertions1 = 0; // Reset the counters.
866
        length_deletions1 = 0;
867
        length_insertions2 = 0;
868
        length_deletions2 = 0;
869
        lastEquality = null;
870
        changes = true;
871
      }
872
    }
873
    pointer++;
874
  }
875

876
  // Normalize the diff.
877
  if (changes) {
878
    this.diff_cleanupMerge(diffs);
879
  }
880
  this.diff_cleanupSemanticLossless(diffs);
881

882
  // Find any overlaps between deletions and insertions.
883
  // e.g: <del>abcxxx</del><ins>xxxdef</ins>
884
  //   -> <del>abc</del>xxx<ins>def</ins>
885
  // e.g: <del>xxxabc</del><ins>defxxx</ins>
886
  //   -> <ins>def</ins>xxx<del>abc</del>
887
  // Only extract an overlap if it is as big as the edit ahead or behind it.
888
  pointer = 1;
889
  while (pointer < diffs.length) {
890
    if (
891
      diffs[pointer - 1][0] == DIFF_DELETE &&
892
      diffs[pointer][0] == DIFF_INSERT
893
    ) {
894
      var deletion = diffs[pointer - 1][1];
895
      var insertion = diffs[pointer][1];
896
      var overlap_length1 = this.diff_commonOverlap_(deletion, insertion);
897
      var overlap_length2 = this.diff_commonOverlap_(insertion, deletion);
898
      if (overlap_length1 >= overlap_length2) {
899
        if (
900
          overlap_length1 >= deletion.length / 2 ||
901
          overlap_length1 >= insertion.length / 2
902
        ) {
903
          // Overlap found.  Insert an equality and trim the surrounding edits.
904
          diffs.splice(
905
            pointer,
906
            0,
907
            new diff_match_patch.Diff(
908
              DIFF_EQUAL,
909
              insertion.substring(0, overlap_length1),
910
            ),
911
          );
912
          diffs[pointer - 1][1] = deletion.substring(
913
            0,
914
            deletion.length - overlap_length1,
915
          );
916
          diffs[pointer + 1][1] = insertion.substring(overlap_length1);
917
          pointer++;
918
        }
919
      } else {
920
        if (
921
          overlap_length2 >= deletion.length / 2 ||
922
          overlap_length2 >= insertion.length / 2
923
        ) {
924
          // Reverse overlap found.
925
          // Insert an equality and swap and trim the surrounding edits.
926
          diffs.splice(
927
            pointer,
928
            0,
929
            new diff_match_patch.Diff(
930
              DIFF_EQUAL,
931
              deletion.substring(0, overlap_length2),
932
            ),
933
          );
934
          diffs[pointer - 1][0] = DIFF_INSERT;
935
          diffs[pointer - 1][1] = insertion.substring(
936
            0,
937
            insertion.length - overlap_length2,
938
          );
939
          diffs[pointer + 1][0] = DIFF_DELETE;
940
          diffs[pointer + 1][1] = deletion.substring(overlap_length2);
941
          pointer++;
942
        }
943
      }
944
      pointer++;
945
    }
946
    pointer++;
947
  }
948
};
949

950
/**
951
 * Look for single edits surrounded on both sides by equalities
952
 * which can be shifted sideways to align the edit to a word boundary.
953
 * e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.
954
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
955
 */
956
diff_match_patch.prototype.diff_cleanupSemanticLossless = function (diffs) {
957
  /**
958
   * Given two strings, compute a score representing whether the internal
959
   * boundary falls on logical boundaries.
960
   * Scores range from 6 (best) to 0 (worst).
961
   * Closure, but does not reference any external variables.
962
   * @param {string} one First string.
963
   * @param {string} two Second string.
964
   * @return {number} The score.
965
   * @private
966
   */
967
  function diff_cleanupSemanticScore_(one, two) {
968
    if (!one || !two) {
969
      // Edges are the best.
970
      return 6;
971
    }
972

973
    // Each port of this function behaves slightly differently due to
974
    // subtle differences in each language's definition of things like
975
    // 'whitespace'.  Since this function's purpose is largely cosmetic,
976
    // the choice has been made to use each language's native features
977
    // rather than force total conformity.
978
    var char1 = one.charAt(one.length - 1);
979
    var char2 = two.charAt(0);
980
    var nonAlphaNumeric1 = char1.match(diff_match_patch.nonAlphaNumericRegex_);
981
    var nonAlphaNumeric2 = char2.match(diff_match_patch.nonAlphaNumericRegex_);
982
    var whitespace1 =
983
      nonAlphaNumeric1 && char1.match(diff_match_patch.whitespaceRegex_);
984
    var whitespace2 =
985
      nonAlphaNumeric2 && char2.match(diff_match_patch.whitespaceRegex_);
986
    var lineBreak1 =
987
      whitespace1 && char1.match(diff_match_patch.linebreakRegex_);
988
    var lineBreak2 =
989
      whitespace2 && char2.match(diff_match_patch.linebreakRegex_);
990
    var blankLine1 =
991
      lineBreak1 && one.match(diff_match_patch.blanklineEndRegex_);
992
    var blankLine2 =
993
      lineBreak2 && two.match(diff_match_patch.blanklineStartRegex_);
994

995
    if (blankLine1 || blankLine2) {
996
      // Five points for blank lines.
997
      return 5;
998
    } else if (lineBreak1 || lineBreak2) {
999
      // Four points for line breaks.
1000
      return 4;
1001
    } else if (nonAlphaNumeric1 && !whitespace1 && whitespace2) {
1002
      // Three points for end of sentences.
1003
      return 3;
1004
    } else if (whitespace1 || whitespace2) {
1005
      // Two points for whitespace.
1006
      return 2;
1007
    } else if (nonAlphaNumeric1 || nonAlphaNumeric2) {
1008
      // One point for non-alphanumeric.
1009
      return 1;
1010
    }
1011
    return 0;
1012
  }
1013

1014
  var pointer = 1;
1015
  // Intentionally ignore the first and last element (don't need checking).
1016
  while (pointer < diffs.length - 1) {
1017
    if (
1018
      diffs[pointer - 1][0] == DIFF_EQUAL &&
1019
      diffs[pointer + 1][0] == DIFF_EQUAL
1020
    ) {
1021
      // This is a single edit surrounded by equalities.
1022
      var equality1 = diffs[pointer - 1][1];
1023
      var edit = diffs[pointer][1];
1024
      var equality2 = diffs[pointer + 1][1];
1025

1026
      // First, shift the edit as far left as possible.
1027
      var commonOffset = this.diff_commonSuffix(equality1, edit);
1028
      if (commonOffset) {
1029
        var commonString = edit.substring(edit.length - commonOffset);
1030
        equality1 = equality1.substring(0, equality1.length - commonOffset);
1031
        edit = commonString + edit.substring(0, edit.length - commonOffset);
1032
        equality2 = commonString + equality2;
1033
      }
1034

1035
      // Second, step character by character right, looking for the best fit.
1036
      var bestEquality1 = equality1;
1037
      var bestEdit = edit;
1038
      var bestEquality2 = equality2;
1039
      var bestScore =
1040
        diff_cleanupSemanticScore_(equality1, edit) +
1041
        diff_cleanupSemanticScore_(edit, equality2);
1042
      while (edit.charAt(0) === equality2.charAt(0)) {
1043
        equality1 += edit.charAt(0);
1044
        edit = edit.substring(1) + equality2.charAt(0);
1045
        equality2 = equality2.substring(1);
1046
        var score =
1047
          diff_cleanupSemanticScore_(equality1, edit) +
1048
          diff_cleanupSemanticScore_(edit, equality2);
1049
        // The >= encourages trailing rather than leading whitespace on edits.
1050
        if (score >= bestScore) {
1051
          bestScore = score;
1052
          bestEquality1 = equality1;
1053
          bestEdit = edit;
1054
          bestEquality2 = equality2;
1055
        }
1056
      }
1057

1058
      if (diffs[pointer - 1][1] != bestEquality1) {
1059
        // We have an improvement, save it back to the diff.
1060
        if (bestEquality1) {
1061
          diffs[pointer - 1][1] = bestEquality1;
1062
        } else {
1063
          diffs.splice(pointer - 1, 1);
1064
          pointer--;
1065
        }
1066
        diffs[pointer][1] = bestEdit;
1067
        if (bestEquality2) {
1068
          diffs[pointer + 1][1] = bestEquality2;
1069
        } else {
1070
          diffs.splice(pointer + 1, 1);
1071
          pointer--;
1072
        }
1073
      }
1074
    }
1075
    pointer++;
1076
  }
1077
};
1078

1079
// Define some regex patterns for matching boundaries.
1080
diff_match_patch.nonAlphaNumericRegex_ = /[^a-zA-Z0-9]/;
1081
diff_match_patch.whitespaceRegex_ = /\s/;
1082
diff_match_patch.linebreakRegex_ = /[\r\n]/;
1083
diff_match_patch.blanklineEndRegex_ = /\n\r?\n$/;
1084
diff_match_patch.blanklineStartRegex_ = /^\r?\n\r?\n/;
1085

1086
/**
1087
 * Reduce the number of edits by eliminating operationally trivial equalities.
1088
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1089
 */
1090
diff_match_patch.prototype.diff_cleanupEfficiency = function (diffs) {
1091
  var changes = false;
1092
  var equalities = []; // Stack of indices where equalities are found.
1093
  var equalitiesLength = 0; // Keeping our own length var is faster in JS.
1094
  /** @type {?string} */
1095
  var lastEquality = null;
1096
  // Always equal to diffs[equalities[equalitiesLength - 1]][1]
1097
  var pointer = 0; // Index of current position.
1098
  // Is there an insertion operation before the last equality.
1099
  var pre_ins = false;
1100
  // Is there a deletion operation before the last equality.
1101
  var pre_del = false;
1102
  // Is there an insertion operation after the last equality.
1103
  var post_ins = false;
1104
  // Is there a deletion operation after the last equality.
1105
  var post_del = false;
1106
  while (pointer < diffs.length) {
1107
    if (diffs[pointer][0] == DIFF_EQUAL) {
1108
      // Equality found.
1109
      if (
1110
        diffs[pointer][1].length < this.Diff_EditCost &&
1111
        (post_ins || post_del)
1112
      ) {
1113
        // Candidate found.
1114
        equalities[equalitiesLength++] = pointer;
1115
        pre_ins = post_ins;
1116
        pre_del = post_del;
1117
        lastEquality = diffs[pointer][1];
1118
      } else {
1119
        // Not a candidate, and can never become one.
1120
        equalitiesLength = 0;
1121
        lastEquality = null;
1122
      }
1123
      post_ins = post_del = false;
1124
    } else {
1125
      // An insertion or deletion.
1126
      if (diffs[pointer][0] == DIFF_DELETE) {
1127
        post_del = true;
1128
      } else {
1129
        post_ins = true;
1130
      }
1131
      /*
1132
       * Five types to be split:
1133
       * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
1134
       * <ins>A</ins>X<ins>C</ins><del>D</del>
1135
       * <ins>A</ins><del>B</del>X<ins>C</ins>
1136
       * <ins>A</del>X<ins>C</ins><del>D</del>
1137
       * <ins>A</ins><del>B</del>X<del>C</del>
1138
       */
1139
      if (
1140
        lastEquality &&
1141
        ((pre_ins && pre_del && post_ins && post_del) ||
1142
          (lastEquality.length < this.Diff_EditCost / 2 &&
1143
            pre_ins + pre_del + post_ins + post_del == 3))
1144
      ) {
1145
        // Duplicate record.
1146
        diffs.splice(
1147
          equalities[equalitiesLength - 1],
1148
          0,
1149
          new diff_match_patch.Diff(DIFF_DELETE, lastEquality),
1150
        );
1151
        // Change second copy to insert.
1152
        diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;
1153
        equalitiesLength--; // Throw away the equality we just deleted;
1154
        lastEquality = null;
1155
        if (pre_ins && pre_del) {
1156
          // No changes made which could affect previous entry, keep going.
1157
          post_ins = post_del = true;
1158
          equalitiesLength = 0;
1159
        } else {
1160
          equalitiesLength--; // Throw away the previous equality.
1161
          pointer =
1162
            equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1;
1163
          post_ins = post_del = false;
1164
        }
1165
        changes = true;
1166
      }
1167
    }
1168
    pointer++;
1169
  }
1170

1171
  if (changes) {
1172
    this.diff_cleanupMerge(diffs);
1173
  }
1174
};
1175

1176
/**
1177
 * Reorder and merge like edit sections.  Merge equalities.
1178
 * Any edit section can move as long as it doesn't cross an equality.
1179
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1180
 */
1181
diff_match_patch.prototype.diff_cleanupMerge = function (diffs) {
1182
  // Add a dummy entry at the end.
1183
  diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, ""));
1184
  var pointer = 0;
1185
  var count_delete = 0;
1186
  var count_insert = 0;
1187
  var text_delete = "";
1188
  var text_insert = "";
1189
  var commonlength;
1190
  while (pointer < diffs.length) {
1191
    switch (diffs[pointer][0]) {
1192
      case DIFF_INSERT:
1193
        count_insert++;
1194
        text_insert += diffs[pointer][1];
1195
        pointer++;
1196
        break;
1197
      case DIFF_DELETE:
1198
        count_delete++;
1199
        text_delete += diffs[pointer][1];
1200
        pointer++;
1201
        break;
1202
      case DIFF_EQUAL:
1203
        // Upon reaching an equality, check for prior redundancies.
1204
        if (count_delete + count_insert > 1) {
1205
          if (count_delete !== 0 && count_insert !== 0) {
1206
            // Factor out any common prefixies.
1207
            commonlength = this.diff_commonPrefix(text_insert, text_delete);
1208
            if (commonlength !== 0) {
1209
              if (
1210
                pointer - count_delete - count_insert > 0 &&
1211
                diffs[pointer - count_delete - count_insert - 1][0] ==
1212
                  DIFF_EQUAL
1213
              ) {
1214
                diffs[pointer - count_delete - count_insert - 1][1] +=
1215
                  text_insert.substring(0, commonlength);
1216
              } else {
1217
                diffs.splice(
1218
                  0,
1219
                  0,
1220
                  new diff_match_patch.Diff(
1221
                    DIFF_EQUAL,
1222
                    text_insert.substring(0, commonlength),
1223
                  ),
1224
                );
1225
                pointer++;
1226
              }
1227
              text_insert = text_insert.substring(commonlength);
1228
              text_delete = text_delete.substring(commonlength);
1229
            }
1230
            // Factor out any common suffixies.
1231
            commonlength = this.diff_commonSuffix(text_insert, text_delete);
1232
            if (commonlength !== 0) {
1233
              diffs[pointer][1] =
1234
                text_insert.substring(text_insert.length - commonlength) +
1235
                diffs[pointer][1];
1236
              text_insert = text_insert.substring(
1237
                0,
1238
                text_insert.length - commonlength,
1239
              );
1240
              text_delete = text_delete.substring(
1241
                0,
1242
                text_delete.length - commonlength,
1243
              );
1244
            }
1245
          }
1246
          // Delete the offending records and add the merged ones.
1247
          pointer -= count_delete + count_insert;
1248
          diffs.splice(pointer, count_delete + count_insert);
1249
          if (text_delete.length) {
1250
            diffs.splice(
1251
              pointer,
1252
              0,
1253
              new diff_match_patch.Diff(DIFF_DELETE, text_delete),
1254
            );
1255
            pointer++;
1256
          }
1257
          if (text_insert.length) {
1258
            diffs.splice(
1259
              pointer,
1260
              0,
1261
              new diff_match_patch.Diff(DIFF_INSERT, text_insert),
1262
            );
1263
            pointer++;
1264
          }
1265
          pointer++;
1266
        } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) {
1267
          // Merge this equality with the previous one.
1268
          diffs[pointer - 1][1] += diffs[pointer][1];
1269
          diffs.splice(pointer, 1);
1270
        } else {
1271
          pointer++;
1272
        }
1273
        count_insert = 0;
1274
        count_delete = 0;
1275
        text_delete = "";
1276
        text_insert = "";
1277
        break;
1278
    }
1279
  }
1280
  if (diffs[diffs.length - 1][1] === "") {
1281
    diffs.pop(); // Remove the dummy entry at the end.
1282
  }
1283

1284
  // Second pass: look for single edits surrounded on both sides by equalities
1285
  // which can be shifted sideways to eliminate an equality.
1286
  // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
1287
  var changes = false;
1288
  pointer = 1;
1289
  // Intentionally ignore the first and last element (don't need checking).
1290
  while (pointer < diffs.length - 1) {
1291
    if (
1292
      diffs[pointer - 1][0] == DIFF_EQUAL &&
1293
      diffs[pointer + 1][0] == DIFF_EQUAL
1294
    ) {
1295
      // This is a single edit surrounded by equalities.
1296
      if (
1297
        diffs[pointer][1].substring(
1298
          diffs[pointer][1].length - diffs[pointer - 1][1].length,
1299
        ) == diffs[pointer - 1][1]
1300
      ) {
1301
        // Shift the edit over the previous equality.
1302
        diffs[pointer][1] =
1303
          diffs[pointer - 1][1] +
1304
          diffs[pointer][1].substring(
1305
            0,
1306
            diffs[pointer][1].length - diffs[pointer - 1][1].length,
1307
          );
1308
        diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];
1309
        diffs.splice(pointer - 1, 1);
1310
        changes = true;
1311
      } else if (
1312
        diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==
1313
        diffs[pointer + 1][1]
1314
      ) {
1315
        // Shift the edit over the next equality.
1316
        diffs[pointer - 1][1] += diffs[pointer + 1][1];
1317
        diffs[pointer][1] =
1318
          diffs[pointer][1].substring(diffs[pointer + 1][1].length) +
1319
          diffs[pointer + 1][1];
1320
        diffs.splice(pointer + 1, 1);
1321
        changes = true;
1322
      }
1323
    }
1324
    pointer++;
1325
  }
1326
  // If shifts were made, the diff needs reordering and another shift sweep.
1327
  if (changes) {
1328
    this.diff_cleanupMerge(diffs);
1329
  }
1330
};
1331

1332
/**
1333
 * loc is a location in text1, compute and return the equivalent location in
1334
 * text2.
1335
 * e.g. 'The cat' vs 'The big cat', 1->1, 5->8
1336
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1337
 * @param {number} loc Location within text1.
1338
 * @return {number} Location within text2.
1339
 */
1340
diff_match_patch.prototype.diff_xIndex = function (diffs, loc) {
1341
  var chars1 = 0;
1342
  var chars2 = 0;
1343
  var last_chars1 = 0;
1344
  var last_chars2 = 0;
1345
  var x;
1346
  for (x = 0; x < diffs.length; x++) {
1347
    if (diffs[x][0] !== DIFF_INSERT) {
1348
      // Equality or deletion.
1349
      chars1 += diffs[x][1].length;
1350
    }
1351
    if (diffs[x][0] !== DIFF_DELETE) {
1352
      // Equality or insertion.
1353
      chars2 += diffs[x][1].length;
1354
    }
1355
    if (chars1 > loc) {
1356
      // Overshot the location.
1357
      break;
1358
    }
1359
    last_chars1 = chars1;
1360
    last_chars2 = chars2;
1361
  }
1362
  // Was the location was deleted?
1363
  if (diffs.length != x && diffs[x][0] === DIFF_DELETE) {
1364
    return last_chars2;
1365
  }
1366
  // Add the remaining character length.
1367
  return last_chars2 + (loc - last_chars1);
1368
};
1369

1370
/**
1371
 * Convert a diff array into a pretty HTML report.
1372
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1373
 * @return {string} HTML representation.
1374
 */
1375
diff_match_patch.prototype.diff_prettyHtml = function (diffs) {
1376
  var html = [];
1377
  var pattern_amp = /&/g;
1378
  var pattern_lt = /</g;
1379
  var pattern_gt = />/g;
1380
  var pattern_para = /\n/g;
1381
  for (var x = 0; x < diffs.length; x++) {
1382
    var op = diffs[x][0]; // Operation (insert, delete, equal)
1383
    var data = diffs[x][1]; // Text of change.
1384
    var text = data
1385
      .replace(pattern_amp, "&amp;")
1386
      .replace(pattern_lt, "&lt;")
1387
      .replace(pattern_gt, "&gt;")
1388
      .replace(pattern_para, "&para;<br>");
1389
    switch (op) {
1390
      case DIFF_INSERT:
1391
        html[x] = '<ins style="background:#e6ffe6;">' + text + "</ins>";
1392
        break;
1393
      case DIFF_DELETE:
1394
        html[x] = '<del style="background:#ffe6e6;">' + text + "</del>";
1395
        break;
1396
      case DIFF_EQUAL:
1397
        html[x] = "<span>" + text + "</span>";
1398
        break;
1399
    }
1400
  }
1401
  return html.join("");
1402
};
1403

1404
/**
1405
 * Compute and return the source text (all equalities and deletions).
1406
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1407
 * @return {string} Source text.
1408
 */
1409
diff_match_patch.prototype.diff_text1 = function (diffs) {
1410
  var text = [];
1411
  for (var x = 0; x < diffs.length; x++) {
1412
    if (diffs[x][0] !== DIFF_INSERT) {
1413
      text[x] = diffs[x][1];
1414
    }
1415
  }
1416
  return text.join("");
1417
};
1418

1419
/**
1420
 * Compute and return the destination text (all equalities and insertions).
1421
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1422
 * @return {string} Destination text.
1423
 */
1424
diff_match_patch.prototype.diff_text2 = function (diffs) {
1425
  var text = [];
1426
  for (var x = 0; x < diffs.length; x++) {
1427
    if (diffs[x][0] !== DIFF_DELETE) {
1428
      text[x] = diffs[x][1];
1429
    }
1430
  }
1431
  return text.join("");
1432
};
1433

1434
/**
1435
 * Compute the Levenshtein distance; the number of inserted, deleted or
1436
 * substituted characters.
1437
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1438
 * @return {number} Number of changes.
1439
 */
1440
diff_match_patch.prototype.diff_levenshtein = function (diffs) {
1441
  var levenshtein = 0;
1442
  var insertions = 0;
1443
  var deletions = 0;
1444
  for (var x = 0; x < diffs.length; x++) {
1445
    var op = diffs[x][0];
1446
    var data = diffs[x][1];
1447
    switch (op) {
1448
      case DIFF_INSERT:
1449
        insertions += data.length;
1450
        break;
1451
      case DIFF_DELETE:
1452
        deletions += data.length;
1453
        break;
1454
      case DIFF_EQUAL:
1455
        // A deletion and an insertion is one substitution.
1456
        levenshtein += Math.max(insertions, deletions);
1457
        insertions = 0;
1458
        deletions = 0;
1459
        break;
1460
    }
1461
  }
1462
  levenshtein += Math.max(insertions, deletions);
1463
  return levenshtein;
1464
};
1465

1466
/**
1467
 * Crush the diff into an encoded string which describes the operations
1468
 * required to transform text1 into text2.
1469
 * E.g. =3\t-2\t+ing  -> Keep 3 chars, delete 2 chars, insert 'ing'.
1470
 * Operations are tab-separated.  Inserted text is escaped using %xx notation.
1471
 * @param {!Array.<!diff_match_patch.Diff>} diffs Array of diff tuples.
1472
 * @return {string} Delta text.
1473
 */
1474
diff_match_patch.prototype.diff_toDelta = function (diffs) {
1475
  var text = [];
1476
  for (var x = 0; x < diffs.length; x++) {
1477
    switch (diffs[x][0]) {
1478
      case DIFF_INSERT:
1479
        text[x] = "+" + encodeURI(diffs[x][1]);
1480
        break;
1481
      case DIFF_DELETE:
1482
        text[x] = "-" + diffs[x][1].length;
1483
        break;
1484
      case DIFF_EQUAL:
1485
        text[x] = "=" + diffs[x][1].length;
1486
        break;
1487
    }
1488
  }
1489
  return text.join("\t").replace(/%20/g, " ");
1490
};
1491

1492
/**
1493
 * Given the original text1, and an encoded string which describes the
1494
 * operations required to transform text1 into text2, compute the full diff.
1495
 * @param {string} text1 Source string for the diff.
1496
 * @param {string} delta Delta text.
1497
 * @return {!Array.<!diff_match_patch.Diff>} Array of diff tuples.
1498
 * @throws {!Error} If invalid input.
1499
 */
1500
diff_match_patch.prototype.diff_fromDelta = function (text1, delta) {
1501
  var diffs = [];
1502
  var diffsLength = 0; // Keeping our own length var is faster in JS.
1503
  var pointer = 0; // Cursor in text1
1504
  var tokens = delta.split(/\t/g);
1505
  for (var x = 0; x < tokens.length; x++) {
1506
    // Each token begins with a one character parameter which specifies the
1507
    // operation of this token (delete, insert, equality).
1508
    var param = tokens[x].substring(1);
1509
    switch (tokens[x].charAt(0)) {
1510
      case "+":
1511
        try {
1512
          diffs[diffsLength++] = new diff_match_patch.Diff(
1513
            DIFF_INSERT,
1514
            decodeURI(param),
1515
          );
1516
        } catch (ex) {
1517
          // Malformed URI sequence.
1518
          throw new Error("Illegal escape in diff_fromDelta: " + param);
1519
        }
1520
        break;
1521
      case "-":
1522
      // Fall through.
1523
      case "=":
1524
        var n = parseInt(param, 10);
1525
        if (isNaN(n) || n < 0) {
1526
          throw new Error("Invalid number in diff_fromDelta: " + param);
1527
        }
1528
        var text = text1.substring(pointer, (pointer += n));
1529
        if (tokens[x].charAt(0) == "=") {
1530
          diffs[diffsLength++] = new diff_match_patch.Diff(DIFF_EQUAL, text);
1531
        } else {
1532
          diffs[diffsLength++] = new diff_match_patch.Diff(DIFF_DELETE, text);
1533
        }
1534
        break;
1535
      default:
1536
        // Blank tokens are ok (from a trailing \t).
1537
        // Anything else is an error.
1538
        if (tokens[x]) {
1539
          throw new Error(
1540
            "Invalid diff operation in diff_fromDelta: " + tokens[x],
1541
          );
1542
        }
1543
    }
1544
  }
1545
  if (pointer != text1.length) {
1546
    throw new Error(
1547
      "Delta length (" +
1548
        pointer +
1549
        ") does not equal source text length (" +
1550
        text1.length +
1551
        ").",
1552
    );
1553
  }
1554
  return diffs;
1555
};
1556

1557
//  MATCH FUNCTIONS
1558

1559
/**
1560
 * Locate the best instance of 'pattern' in 'text' near 'loc'.
1561
 * @param {string} text The text to search.
1562
 * @param {string} pattern The pattern to search for.
1563
 * @param {number} loc The location to search around.
1564
 * @return {number} Best match index or -1.
1565
 */
1566
diff_match_patch.prototype.match_main = function (text, pattern, loc) {
1567
  // Check for null inputs.
1568
  if (text == null || pattern == null || loc == null) {
1569
    throw new Error("Null input. (match_main)");
1570
  }
1571

1572
  loc = Math.max(0, Math.min(loc, text.length));
1573
  if (text == pattern) {
1574
    // Shortcut (potentially not guaranteed by the algorithm)
1575
    return 0;
1576
  } else if (!text.length) {
1577
    // Nothing to match.
1578
    return -1;
1579
  } else if (text.substring(loc, loc + pattern.length) == pattern) {
1580
    // Perfect match at the perfect spot!  (Includes case of null pattern)
1581
    return loc;
1582
  } else {
1583
    // Do a fuzzy compare.
1584
    return this.match_bitap_(text, pattern, loc);
1585
  }
1586
};
1587

1588
/**
1589
 * Locate the best instance of 'pattern' in 'text' near 'loc' using the
1590
 * Bitap algorithm.
1591
 * @param {string} text The text to search.
1592
 * @param {string} pattern The pattern to search for.
1593
 * @param {number} loc The location to search around.
1594
 * @return {number} Best match index or -1.
1595
 * @private
1596
 */
1597
diff_match_patch.prototype.match_bitap_ = function (text, pattern, loc) {
1598
  if (pattern.length > this.Match_MaxBits) {
1599
    throw new Error("Pattern too long for this browser.");
1600
  }
1601

1602
  // Initialise the alphabet.
1603
  var s = this.match_alphabet_(pattern);
1604

1605
  var dmp = this; // 'this' becomes 'window' in a closure.
1606

1607
  /**
1608
   * Compute and return the score for a match with e errors and x location.
1609
   * Accesses loc and pattern through being a closure.
1610
   * @param {number} e Number of errors in match.
1611
   * @param {number} x Location of match.
1612
   * @return {number} Overall score for match (0.0 = good, 1.0 = bad).
1613
   * @private
1614
   */
1615
  function match_bitapScore_(e, x) {
1616
    var accuracy = e / pattern.length;
1617
    var proximity = Math.abs(loc - x);
1618
    if (!dmp.Match_Distance) {
1619
      // Dodge divide by zero error.
1620
      return proximity ? 1.0 : accuracy;
1621
    }
1622
    return accuracy + proximity / dmp.Match_Distance;
1623
  }
1624

1625
  // Highest score beyond which we give up.
1626
  var score_threshold = this.Match_Threshold;
1627
  // Is there a nearby exact match? (speedup)
1628
  var best_loc = text.indexOf(pattern, loc);
1629
  if (best_loc != -1) {
1630
    score_threshold = Math.min(match_bitapScore_(0, best_loc), score_threshold);
1631
    // What about in the other direction? (speedup)
1632
    best_loc = text.lastIndexOf(pattern, loc + pattern.length);
1633
    if (best_loc != -1) {
1634
      score_threshold = Math.min(
1635
        match_bitapScore_(0, best_loc),
1636
        score_threshold,
1637
      );
1638
    }
1639
  }
1640

1641
  // Initialise the bit arrays.
1642
  var matchmask = 1 << (pattern.length - 1);
1643
  best_loc = -1;
1644

1645
  var bin_min, bin_mid;
1646
  var bin_max = pattern.length + text.length;
1647
  var last_rd;
1648
  for (var d = 0; d < pattern.length; d++) {
1649
    // Scan for the best match; each iteration allows for one more error.
1650
    // Run a binary search to determine how far from 'loc' we can stray at this
1651
    // error level.
1652
    bin_min = 0;
1653
    bin_mid = bin_max;
1654
    while (bin_min < bin_mid) {
1655
      if (match_bitapScore_(d, loc + bin_mid) <= score_threshold) {
1656
        bin_min = bin_mid;
1657
      } else {
1658
        bin_max = bin_mid;
1659
      }
1660
      bin_mid = Math.floor((bin_max - bin_min) / 2 + bin_min);
1661
    }
1662
    // Use the result from this iteration as the maximum for the next.
1663
    bin_max = bin_mid;
1664
    var start = Math.max(1, loc - bin_mid + 1);
1665
    var finish = Math.min(loc + bin_mid, text.length) + pattern.length;
1666

1667
    var rd = Array(finish + 2);
1668
    rd[finish + 1] = (1 << d) - 1;
1669
    for (var j = finish; j >= start; j--) {
1670
      // The alphabet (s) is a sparse hash, so the following line generates
1671
      // warnings.
1672
      var charMatch = s[text.charAt(j - 1)];
1673
      if (d === 0) {
1674
        // First pass: exact match.
1675
        rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;
1676
      } else {
1677
        // Subsequent passes: fuzzy match.
1678
        rd[j] =
1679
          (((rd[j + 1] << 1) | 1) & charMatch) |
1680
          (((last_rd[j + 1] | last_rd[j]) << 1) | 1) |
1681
          last_rd[j + 1];
1682
      }
1683
      if (rd[j] & matchmask) {
1684
        var score = match_bitapScore_(d, j - 1);
1685
        // This match will almost certainly be better than any existing match.
1686
        // But check anyway.
1687
        if (score <= score_threshold) {
1688
          // Told you so.
1689
          score_threshold = score;
1690
          best_loc = j - 1;
1691
          if (best_loc > loc) {
1692
            // When passing loc, don't exceed our current distance from loc.
1693
            start = Math.max(1, 2 * loc - best_loc);
1694
          } else {
1695
            // Already passed loc, downhill from here on in.
1696
            break;
1697
          }
1698
        }
1699
      }
1700
    }
1701
    // No hope for a (better) match at greater error levels.
1702
    if (match_bitapScore_(d + 1, loc) > score_threshold) {
1703
      break;
1704
    }
1705
    last_rd = rd;
1706
  }
1707
  return best_loc;
1708
};
1709

1710
/**
1711
 * Initialise the alphabet for the Bitap algorithm.
1712
 * @param {string} pattern The text to encode.
1713
 * @return {!Object} Hash of character locations.
1714
 * @private
1715
 */
1716
diff_match_patch.prototype.match_alphabet_ = function (pattern) {
1717
  var s = {};
1718
  for (var i = 0; i < pattern.length; i++) {
1719
    s[pattern.charAt(i)] = 0;
1720
  }
1721
  for (var i = 0; i < pattern.length; i++) {
1722
    s[pattern.charAt(i)] |= 1 << (pattern.length - i - 1);
1723
  }
1724
  return s;
1725
};
1726

1727
//  PATCH FUNCTIONS
1728

1729
/**
1730
 * Increase the context until it is unique,
1731
 * but don't let the pattern expand beyond Match_MaxBits.
1732
 * @param {!diff_match_patch.patch_obj} patch The patch to grow.
1733
 * @param {string} text Source text.
1734
 * @private
1735
 */
1736
diff_match_patch.prototype.patch_addContext_ = function (patch, text) {
1737
  if (text.length == 0) {
1738
    return;
1739
  }
1740
  if (patch.start2 === null) {
1741
    throw Error("patch not initialized");
1742
  }
1743
  var pattern = text.substring(patch.start2, patch.start2 + patch.length1);
1744
  var padding = 0;
1745

1746
  // Look for the first and last matches of pattern in text.  If two different
1747
  // matches are found, increase the pattern length.
1748
  while (
1749
    text.indexOf(pattern) != text.lastIndexOf(pattern) &&
1750
    pattern.length < this.Match_MaxBits - this.Patch_Margin - this.Patch_Margin
1751
  ) {
1752
    padding += this.Patch_Margin;
1753
    pattern = text.substring(
1754
      patch.start2 - padding,
1755
      patch.start2 + patch.length1 + padding,
1756
    );
1757
  }
1758
  // Add one chunk for good luck.
1759
  padding += this.Patch_Margin;
1760

1761
  // Add the prefix.
1762
  var prefix = text.substring(patch.start2 - padding, patch.start2);
1763
  if (prefix) {
1764
    patch.diffs.unshift(new diff_match_patch.Diff(DIFF_EQUAL, prefix));
1765
  }
1766
  // Add the suffix.
1767
  var suffix = text.substring(
1768
    patch.start2 + patch.length1,
1769
    patch.start2 + patch.length1 + padding,
1770
  );
1771
  if (suffix) {
1772
    patch.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, suffix));
1773
  }
1774

1775
  // Roll back the start points.
1776
  patch.start1 -= prefix.length;
1777
  patch.start2 -= prefix.length;
1778
  // Extend the lengths.
1779
  patch.length1 += prefix.length + suffix.length;
1780
  patch.length2 += prefix.length + suffix.length;
1781
};
1782

1783
/**
1784
 * Compute a list of patches to turn text1 into text2.
1785
 * Use diffs if provided, otherwise compute it ourselves.
1786
 * There are four ways to call this function, depending on what data is
1787
 * available to the caller:
1788
 * Method 1:
1789
 * a = text1, b = text2
1790
 * Method 2:
1791
 * a = diffs
1792
 * Method 3 (optimal):
1793
 * a = text1, b = diffs
1794
 * Method 4 (deprecated, use method 3):
1795
 * a = text1, b = text2, c = diffs
1796
 *
1797
 * @param {string|!Array.<!diff_match_patch.Diff>} a text1 (methods 1,3,4) or
1798
 * Array of diff tuples for text1 to text2 (method 2).
1799
 * @param {string|!Array.<!diff_match_patch.Diff>} opt_b text2 (methods 1,4) or
1800
 * Array of diff tuples for text1 to text2 (method 3) or undefined (method 2).
1801
 * @param {string|!Array.<!diff_match_patch.Diff>} opt_c Array of diff tuples
1802
 * for text1 to text2 (method 4) or undefined (methods 1,2,3).
1803
 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.
1804
 */
1805
diff_match_patch.prototype.patch_make = function (a, opt_b, opt_c) {
1806
  var text1, diffs;
1807
  if (
1808
    typeof a == "string" &&
1809
    typeof opt_b == "string" &&
1810
    typeof opt_c == "undefined"
1811
  ) {
1812
    // Method 1: text1, text2
1813
    // Compute diffs from text1 and text2.
1814
    text1 = /** @type {string} */ (a);
1815
    diffs = this.diff_main(text1, /** @type {string} */ (opt_b), true);
1816
    if (diffs.length > 2) {
1817
      this.diff_cleanupSemantic(diffs);
1818
      this.diff_cleanupEfficiency(diffs);
1819
    }
1820
  } else if (
1821
    a &&
1822
    typeof a == "object" &&
1823
    typeof opt_b == "undefined" &&
1824
    typeof opt_c == "undefined"
1825
  ) {
1826
    // Method 2: diffs
1827
    // Compute text1 from diffs.
1828
    diffs = /** @type {!Array.<!diff_match_patch.Diff>} */ (a);
1829
    text1 = this.diff_text1(diffs);
1830
  } else if (
1831
    typeof a == "string" &&
1832
    opt_b &&
1833
    typeof opt_b == "object" &&
1834
    typeof opt_c == "undefined"
1835
  ) {
1836
    // Method 3: text1, diffs
1837
    text1 = /** @type {string} */ (a);
1838
    diffs = /** @type {!Array.<!diff_match_patch.Diff>} */ (opt_b);
1839
  } else if (
1840
    typeof a == "string" &&
1841
    typeof opt_b == "string" &&
1842
    opt_c &&
1843
    typeof opt_c == "object"
1844
  ) {
1845
    // Method 4: text1, text2, diffs
1846
    // text2 is not used.
1847
    text1 = /** @type {string} */ (a);
1848
    diffs = /** @type {!Array.<!diff_match_patch.Diff>} */ (opt_c);
1849
  } else {
1850
    throw new Error("Unknown call format to patch_make.");
1851
  }
1852

1853
  if (diffs.length === 0) {
1854
    return []; // Get rid of the null case.
1855
  }
1856
  var patches = [];
1857
  var patch = new diff_match_patch.patch_obj();
1858
  var patchDiffLength = 0; // Keeping our own length var is faster in JS.
1859
  var char_count1 = 0; // Number of characters into the text1 string.
1860
  var char_count2 = 0; // Number of characters into the text2 string.
1861
  // Start with text1 (prepatch_text) and apply the diffs until we arrive at
1862
  // text2 (postpatch_text).  We recreate the patches one by one to determine
1863
  // context info.
1864
  var prepatch_text = text1;
1865
  var postpatch_text = text1;
1866
  for (var x = 0; x < diffs.length; x++) {
1867
    var diff_type = diffs[x][0];
1868
    var diff_text = diffs[x][1];
1869

1870
    if (!patchDiffLength && diff_type !== DIFF_EQUAL) {
1871
      // A new patch starts here.
1872
      patch.start1 = char_count1;
1873
      patch.start2 = char_count2;
1874
    }
1875

1876
    switch (diff_type) {
1877
      case DIFF_INSERT:
1878
        patch.diffs[patchDiffLength++] = diffs[x];
1879
        patch.length2 += diff_text.length;
1880
        postpatch_text =
1881
          postpatch_text.substring(0, char_count2) +
1882
          diff_text +
1883
          postpatch_text.substring(char_count2);
1884
        break;
1885
      case DIFF_DELETE:
1886
        patch.length1 += diff_text.length;
1887
        patch.diffs[patchDiffLength++] = diffs[x];
1888
        postpatch_text =
1889
          postpatch_text.substring(0, char_count2) +
1890
          postpatch_text.substring(char_count2 + diff_text.length);
1891
        break;
1892
      case DIFF_EQUAL:
1893
        if (
1894
          diff_text.length <= 2 * this.Patch_Margin &&
1895
          patchDiffLength &&
1896
          diffs.length != x + 1
1897
        ) {
1898
          // Small equality inside a patch.
1899
          patch.diffs[patchDiffLength++] = diffs[x];
1900
          patch.length1 += diff_text.length;
1901
          patch.length2 += diff_text.length;
1902
        } else if (diff_text.length >= 2 * this.Patch_Margin) {
1903
          // Time for a new patch.
1904
          if (patchDiffLength) {
1905
            this.patch_addContext_(patch, prepatch_text);
1906
            patches.push(patch);
1907
            patch = new diff_match_patch.patch_obj();
1908
            patchDiffLength = 0;
1909
            // Unlike Unidiff, our patch lists have a rolling context.
1910
            // https://github.com/google/diff-match-patch/wiki/Unidiff
1911
            // Update prepatch text & pos to reflect the application of the
1912
            // just completed patch.
1913
            prepatch_text = postpatch_text;
1914
            char_count1 = char_count2;
1915
          }
1916
        }
1917
        break;
1918
    }
1919

1920
    // Update the current character count.
1921
    if (diff_type !== DIFF_INSERT) {
1922
      char_count1 += diff_text.length;
1923
    }
1924
    if (diff_type !== DIFF_DELETE) {
1925
      char_count2 += diff_text.length;
1926
    }
1927
  }
1928
  // Pick up the leftover patch if not empty.
1929
  if (patchDiffLength) {
1930
    this.patch_addContext_(patch, prepatch_text);
1931
    patches.push(patch);
1932
  }
1933

1934
  return patches;
1935
};
1936

1937
/**
1938
 * Given an array of patches, return another array that is identical.
1939
 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.
1940
 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.
1941
 */
1942
diff_match_patch.prototype.patch_deepCopy = function (patches) {
1943
  // Making deep copies is hard in JavaScript.
1944
  var patchesCopy = [];
1945
  for (var x = 0; x < patches.length; x++) {
1946
    var patch = patches[x];
1947
    var patchCopy = new diff_match_patch.patch_obj();
1948
    patchCopy.diffs = [];
1949
    for (var y = 0; y < patch.diffs.length; y++) {
1950
      patchCopy.diffs[y] = new diff_match_patch.Diff(
1951
        patch.diffs[y][0],
1952
        patch.diffs[y][1],
1953
      );
1954
    }
1955
    patchCopy.start1 = patch.start1;
1956
    patchCopy.start2 = patch.start2;
1957
    patchCopy.length1 = patch.length1;
1958
    patchCopy.length2 = patch.length2;
1959
    patchesCopy[x] = patchCopy;
1960
  }
1961
  return patchesCopy;
1962
};
1963

1964
/**
1965
 * Merge a set of patches onto the text.  Return a patched text, as well
1966
 * as a list of true/false values indicating which patches were applied.
1967
 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.
1968
 * @param {string} text Old text.
1969
 * @return {!Array.<string|!Array.<boolean>>} Two element Array, containing the
1970
 *      new text and an array of boolean values.
1971
 */
1972
diff_match_patch.prototype.patch_apply = function (patches, text) {
1973
  if (patches.length == 0) {
1974
    return [text, []];
1975
  }
1976

1977
  // Deep copy the patches so that no changes are made to originals.
1978
  patches = this.patch_deepCopy(patches);
1979

1980
  var nullPadding = this.patch_addPadding(patches);
1981
  text = nullPadding + text + nullPadding;
1982

1983
  this.patch_splitMax(patches);
1984
  // delta keeps track of the offset between the expected and actual location
1985
  // of the previous patch.  If there are patches expected at positions 10 and
1986
  // 20, but the first patch was found at 12, delta is 2 and the second patch
1987
  // has an effective expected position of 22.
1988
  var delta = 0;
1989
  var results = [];
1990
  for (var x = 0; x < patches.length; x++) {
1991
    var expected_loc = patches[x].start2 + delta;
1992
    var text1 = this.diff_text1(patches[x].diffs);
1993
    var start_loc;
1994
    var end_loc = -1;
1995
    if (text1.length > this.Match_MaxBits) {
1996
      // patch_splitMax will only provide an oversized pattern in the case of
1997
      // a monster delete.
1998
      start_loc = this.match_main(
1999
        text,
2000
        text1.substring(0, this.Match_MaxBits),
2001
        expected_loc,
2002
      );
2003
      if (start_loc != -1) {
2004
        end_loc = this.match_main(
2005
          text,
2006
          text1.substring(text1.length - this.Match_MaxBits),
2007
          expected_loc + text1.length - this.Match_MaxBits,
2008
        );
2009
        if (end_loc == -1 || start_loc >= end_loc) {
2010
          // Can't find valid trailing context.  Drop this patch.
2011
          start_loc = -1;
2012
        }
2013
      }
2014
    } else {
2015
      start_loc = this.match_main(text, text1, expected_loc);
2016
    }
2017
    if (start_loc == -1) {
2018
      // No match found.  :(
2019
      results[x] = false;
2020
      // Subtract the delta for this failed patch from subsequent patches.
2021
      delta -= patches[x].length2 - patches[x].length1;
2022
    } else {
2023
      // Found a match.  :)
2024
      results[x] = true;
2025
      delta = start_loc - expected_loc;
2026
      var text2;
2027
      if (end_loc == -1) {
2028
        text2 = text.substring(start_loc, start_loc + text1.length);
2029
      } else {
2030
        text2 = text.substring(start_loc, end_loc + this.Match_MaxBits);
2031
      }
2032
      if (text1 == text2) {
2033
        // Perfect match, just shove the replacement text in.
2034
        text =
2035
          text.substring(0, start_loc) +
2036
          this.diff_text2(patches[x].diffs) +
2037
          text.substring(start_loc + text1.length);
2038
      } else {
2039
        // Imperfect match.  Run a diff to get a framework of equivalent
2040
        // indices.
2041
        var diffs = this.diff_main(text1, text2, false);
2042
        if (
2043
          text1.length > this.Match_MaxBits &&
2044
          this.diff_levenshtein(diffs) / text1.length >
2045
            this.Patch_DeleteThreshold
2046
        ) {
2047
          // The end points match, but the content is unacceptably bad.
2048
          results[x] = false;
2049
        } else {
2050
          this.diff_cleanupSemanticLossless(diffs);
2051
          var index1 = 0;
2052
          var index2;
2053
          for (var y = 0; y < patches[x].diffs.length; y++) {
2054
            var mod = patches[x].diffs[y];
2055
            if (mod[0] !== DIFF_EQUAL) {
2056
              index2 = this.diff_xIndex(diffs, index1);
2057
            }
2058
            if (mod[0] === DIFF_INSERT) {
2059
              // Insertion
2060
              text =
2061
                text.substring(0, start_loc + index2) +
2062
                mod[1] +
2063
                text.substring(start_loc + index2);
2064
            } else if (mod[0] === DIFF_DELETE) {
2065
              // Deletion
2066
              text =
2067
                text.substring(0, start_loc + index2) +
2068
                text.substring(
2069
                  start_loc + this.diff_xIndex(diffs, index1 + mod[1].length),
2070
                );
2071
            }
2072
            if (mod[0] !== DIFF_DELETE) {
2073
              index1 += mod[1].length;
2074
            }
2075
          }
2076
        }
2077
      }
2078
    }
2079
  }
2080
  // Strip the padding off.
2081
  text = text.substring(nullPadding.length, text.length - nullPadding.length);
2082
  return [text, results];
2083
};
2084

2085
/**
2086
 * Add some padding on text start and end so that edges can match something.
2087
 * Intended to be called only from within patch_apply.
2088
 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.
2089
 * @return {string} The padding string added to each side.
2090
 */
2091
diff_match_patch.prototype.patch_addPadding = function (patches) {
2092
  var paddingLength = this.Patch_Margin;
2093
  var nullPadding = "";
2094
  for (var x = 1; x <= paddingLength; x++) {
2095
    nullPadding += String.fromCharCode(x);
2096
  }
2097

2098
  // Bump all the patches forward.
2099
  for (var x = 0; x < patches.length; x++) {
2100
    patches[x].start1 += paddingLength;
2101
    patches[x].start2 += paddingLength;
2102
  }
2103

2104
  // Add some padding on start of first diff.
2105
  var patch = patches[0];
2106
  var diffs = patch.diffs;
2107
  if (diffs.length == 0 || diffs[0][0] != DIFF_EQUAL) {
2108
    // Add nullPadding equality.
2109
    diffs.unshift(new diff_match_patch.Diff(DIFF_EQUAL, nullPadding));
2110
    patch.start1 -= paddingLength; // Should be 0.
2111
    patch.start2 -= paddingLength; // Should be 0.
2112
    patch.length1 += paddingLength;
2113
    patch.length2 += paddingLength;
2114
  } else if (paddingLength > diffs[0][1].length) {
2115
    // Grow first equality.
2116
    var extraLength = paddingLength - diffs[0][1].length;
2117
    diffs[0][1] = nullPadding.substring(diffs[0][1].length) + diffs[0][1];
2118
    patch.start1 -= extraLength;
2119
    patch.start2 -= extraLength;
2120
    patch.length1 += extraLength;
2121
    patch.length2 += extraLength;
2122
  }
2123

2124
  // Add some padding on end of last diff.
2125
  patch = patches[patches.length - 1];
2126
  diffs = patch.diffs;
2127
  if (diffs.length == 0 || diffs[diffs.length - 1][0] != DIFF_EQUAL) {
2128
    // Add nullPadding equality.
2129
    diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, nullPadding));
2130
    patch.length1 += paddingLength;
2131
    patch.length2 += paddingLength;
2132
  } else if (paddingLength > diffs[diffs.length - 1][1].length) {
2133
    // Grow last equality.
2134
    var extraLength = paddingLength - diffs[diffs.length - 1][1].length;
2135
    diffs[diffs.length - 1][1] += nullPadding.substring(0, extraLength);
2136
    patch.length1 += extraLength;
2137
    patch.length2 += extraLength;
2138
  }
2139

2140
  return nullPadding;
2141
};
2142

2143
/**
2144
 * Look through the patches and break up any which are longer than the maximum
2145
 * limit of the match algorithm.
2146
 * Intended to be called only from within patch_apply.
2147
 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.
2148
 */
2149
diff_match_patch.prototype.patch_splitMax = function (patches) {
2150
  var patch_size = this.Match_MaxBits;
2151
  for (var x = 0; x < patches.length; x++) {
2152
    if (patches[x].length1 <= patch_size) {
2153
      continue;
2154
    }
2155
    var bigpatch = patches[x];
2156
    // Remove the big old patch.
2157
    patches.splice(x--, 1);
2158
    var start1 = bigpatch.start1;
2159
    var start2 = bigpatch.start2;
2160
    var precontext = "";
2161
    while (bigpatch.diffs.length !== 0) {
2162
      // Create one of several smaller patches.
2163
      var patch = new diff_match_patch.patch_obj();
2164
      var empty = true;
2165
      patch.start1 = start1 - precontext.length;
2166
      patch.start2 = start2 - precontext.length;
2167
      if (precontext !== "") {
2168
        patch.length1 = patch.length2 = precontext.length;
2169
        patch.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, precontext));
2170
      }
2171
      while (
2172
        bigpatch.diffs.length !== 0 &&
2173
        patch.length1 < patch_size - this.Patch_Margin
2174
      ) {
2175
        var diff_type = bigpatch.diffs[0][0];
2176
        var diff_text = bigpatch.diffs[0][1];
2177
        if (diff_type === DIFF_INSERT) {
2178
          // Insertions are harmless.
2179
          patch.length2 += diff_text.length;
2180
          start2 += diff_text.length;
2181
          patch.diffs.push(bigpatch.diffs.shift());
2182
          empty = false;
2183
        } else if (
2184
          diff_type === DIFF_DELETE &&
2185
          patch.diffs.length == 1 &&
2186
          patch.diffs[0][0] == DIFF_EQUAL &&
2187
          diff_text.length > 2 * patch_size
2188
        ) {
2189
          // This is a large deletion.  Let it pass in one chunk.
2190
          patch.length1 += diff_text.length;
2191
          start1 += diff_text.length;
2192
          empty = false;
2193
          patch.diffs.push(new diff_match_patch.Diff(diff_type, diff_text));
2194
          bigpatch.diffs.shift();
2195
        } else {
2196
          // Deletion or equality.  Only take as much as we can stomach.
2197
          diff_text = diff_text.substring(
2198
            0,
2199
            patch_size - patch.length1 - this.Patch_Margin,
2200
          );
2201
          patch.length1 += diff_text.length;
2202
          start1 += diff_text.length;
2203
          if (diff_type === DIFF_EQUAL) {
2204
            patch.length2 += diff_text.length;
2205
            start2 += diff_text.length;
2206
          } else {
2207
            empty = false;
2208
          }
2209
          patch.diffs.push(new diff_match_patch.Diff(diff_type, diff_text));
2210
          if (diff_text == bigpatch.diffs[0][1]) {
2211
            bigpatch.diffs.shift();
2212
          } else {
2213
            bigpatch.diffs[0][1] = bigpatch.diffs[0][1].substring(
2214
              diff_text.length,
2215
            );
2216
          }
2217
        }
2218
      }
2219
      // Compute the head context for the next patch.
2220
      precontext = this.diff_text2(patch.diffs);
2221
      precontext = precontext.substring(precontext.length - this.Patch_Margin);
2222
      // Append the end context for this patch.
2223
      var postcontext = this.diff_text1(bigpatch.diffs).substring(
2224
        0,
2225
        this.Patch_Margin,
2226
      );
2227
      if (postcontext !== "") {
2228
        patch.length1 += postcontext.length;
2229
        patch.length2 += postcontext.length;
2230
        if (
2231
          patch.diffs.length !== 0 &&
2232
          patch.diffs[patch.diffs.length - 1][0] === DIFF_EQUAL
2233
        ) {
2234
          patch.diffs[patch.diffs.length - 1][1] += postcontext;
2235
        } else {
2236
          patch.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, postcontext));
2237
        }
2238
      }
2239
      if (!empty) {
2240
        patches.splice(++x, 0, patch);
2241
      }
2242
    }
2243
  }
2244
};
2245

2246
/**
2247
 * Take a list of patches and return a textual representation.
2248
 * @param {!Array.<!diff_match_patch.patch_obj>} patches Array of Patch objects.
2249
 * @return {string} Text representation of patches.
2250
 */
2251
diff_match_patch.prototype.patch_toText = function (patches) {
2252
  var text = [];
2253
  for (var x = 0; x < patches.length; x++) {
2254
    text[x] = patches[x];
2255
  }
2256
  return text.join("");
2257
};
2258

2259
/**
2260
 * Parse a textual representation of patches and return a list of Patch objects.
2261
 * @param {string} textline Text representation of patches.
2262
 * @return {!Array.<!diff_match_patch.patch_obj>} Array of Patch objects.
2263
 * @throws {!Error} If invalid input.
2264
 */
2265
diff_match_patch.prototype.patch_fromText = function (textline) {
2266
  var patches = [];
2267
  if (!textline) {
2268
    return patches;
2269
  }
2270
  var text = textline.split("\n");
2271
  var textPointer = 0;
2272
  var patchHeader = /^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/;
2273
  while (textPointer < text.length) {
2274
    var m = text[textPointer].match(patchHeader);
2275
    if (!m) {
2276
      throw new Error("Invalid patch string: " + text[textPointer]);
2277
    }
2278
    var patch = new diff_match_patch.patch_obj();
2279
    patches.push(patch);
2280
    patch.start1 = parseInt(m[1], 10);
2281
    if (m[2] === "") {
2282
      patch.start1--;
2283
      patch.length1 = 1;
2284
    } else if (m[2] == "0") {
2285
      patch.length1 = 0;
2286
    } else {
2287
      patch.start1--;
2288
      patch.length1 = parseInt(m[2], 10);
2289
    }
2290

2291
    patch.start2 = parseInt(m[3], 10);
2292
    if (m[4] === "") {
2293
      patch.start2--;
2294
      patch.length2 = 1;
2295
    } else if (m[4] == "0") {
2296
      patch.length2 = 0;
2297
    } else {
2298
      patch.start2--;
2299
      patch.length2 = parseInt(m[4], 10);
2300
    }
2301
    textPointer++;
2302

2303
    while (textPointer < text.length) {
2304
      var sign = text[textPointer].charAt(0);
2305
      try {
2306
        var line = decodeURI(text[textPointer].substring(1));
2307
      } catch (ex) {
2308
        // Malformed URI sequence.
2309
        throw new Error("Illegal escape in patch_fromText: " + line);
2310
      }
2311
      if (sign == "-") {
2312
        // Deletion.
2313
        patch.diffs.push(new diff_match_patch.Diff(DIFF_DELETE, line));
2314
      } else if (sign == "+") {
2315
        // Insertion.
2316
        patch.diffs.push(new diff_match_patch.Diff(DIFF_INSERT, line));
2317
      } else if (sign == " ") {
2318
        // Minor equality.
2319
        patch.diffs.push(new diff_match_patch.Diff(DIFF_EQUAL, line));
2320
      } else if (sign == "@") {
2321
        // Start of next patch.
2322
        break;
2323
      } else if (sign === "") {
2324
        // Blank line?  Whatever.
2325
      } else {
2326
        // WTF?
2327
        throw new Error('Invalid patch mode "' + sign + '" in: ' + line);
2328
      }
2329
      textPointer++;
2330
    }
2331
  }
2332
  return patches;
2333
};
2334

2335
/**
2336
 * Class representing one patch operation.
2337
 * @constructor
2338
 */
2339
diff_match_patch.patch_obj = function () {
2340
  /** @type {!Array.<!diff_match_patch.Diff>} */
2341
  this.diffs = [];
2342
  /** @type {?number} */
2343
  this.start1 = null;
2344
  /** @type {?number} */
2345
  this.start2 = null;
2346
  /** @type {number} */
2347
  this.length1 = 0;
2348
  /** @type {number} */
2349
  this.length2 = 0;
2350
};
2351

2352
/**
2353
 * Emulate GNU diff's format.
2354
 * Header: @@ -382,8 +481,9 @@
2355
 * Indices are printed as 1-based, not 0-based.
2356
 * @return {string} The GNU diff string.
2357
 */
2358
diff_match_patch.patch_obj.prototype.toString = function () {
2359
  var coords1, coords2;
2360
  if (this.length1 === 0) {
2361
    coords1 = this.start1 + ",0";
2362
  } else if (this.length1 == 1) {
2363
    coords1 = this.start1 + 1;
2364
  } else {
2365
    coords1 = this.start1 + 1 + "," + this.length1;
2366
  }
2367
  if (this.length2 === 0) {
2368
    coords2 = this.start2 + ",0";
2369
  } else if (this.length2 == 1) {
2370
    coords2 = this.start2 + 1;
2371
  } else {
2372
    coords2 = this.start2 + 1 + "," + this.length2;
2373
  }
2374
  var text = ["@@ -" + coords1 + " +" + coords2 + " @@\n"];
2375
  var op;
2376
  // Escape the body of the patch with %xx notation.
2377
  for (var x = 0; x < this.diffs.length; x++) {
2378
    switch (this.diffs[x][0]) {
2379
      case DIFF_INSERT:
2380
        op = "+";
2381
        break;
2382
      case DIFF_DELETE:
2383
        op = "-";
2384
        break;
2385
      case DIFF_EQUAL:
2386
        op = " ";
2387
        break;
2388
    }
2389
    text[x + 1] = op + encodeURI(this.diffs[x][1]) + "\n";
2390
  }
2391
  return text.join("").replace(/%20/g, " ");
2392
};
2393

2394