1
0

string_diff.js 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776
  1. /**
  2. * Author: @jhchen - https://github.com/jhchen
  3. * Modified by: @lucascalion - 23/07/2019
  4. * This library modifies the diff-patch-match library by Neil Fraser
  5. * by removing the patch and match functionality and certain advanced
  6. * options in the diff function. The original license is as follows:
  7. *
  8. * ===
  9. *
  10. * Diff Match and Patch
  11. *
  12. * Copyright 2006 Google Inc.
  13. * http://code.google.com/p/google-diff-match-patch/
  14. *
  15. * Licensed under the Apache License, Version 2.0 (the "License");
  16. * you may not use this file except in compliance with the License.
  17. * You may obtain a copy of the License at
  18. *
  19. * http://www.apache.org/licenses/LICENSE-2.0
  20. *
  21. * Unless required by applicable law or agreed to in writing, software
  22. * distributed under the License is distributed on an "AS IS" BASIS,
  23. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  24. * See the License for the specific language governing permissions and
  25. * limitations under the License.
  26. */
  27. /**
  28. * The data structure representing a diff is an array of tuples:
  29. * [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']]
  30. * which means: delete 'Hello', add 'Goodbye' and keep ' world.'
  31. */
  32. const DIFF_DELETE = -1;
  33. const DIFF_INSERT = 1;
  34. const DIFF_EQUAL = 0;
  35. /**
  36. * Find the differences between two texts. Simplifies the problem by stripping
  37. * any common prefix or suffix off the texts before diffing.
  38. * @param {string} text1 Old string to be diffed.
  39. * @param {string} text2 New string to be diffed.
  40. * @param {Int|Object} [cursor_pos] Edit position in text1 or object with more info
  41. * @return {Array} Array of diff tuples.
  42. */
  43. function diff_main(text1, text2, cursor_pos, _fix_unicode) {
  44. // Check for equality
  45. if (text1 === text2) {
  46. if (text1) {
  47. return [[DIFF_EQUAL, text1]];
  48. }
  49. return [];
  50. }
  51. if (cursor_pos != null) {
  52. const editdiff = find_cursor_edit_diff(text1, text2, cursor_pos);
  53. if (editdiff) {
  54. return editdiff;
  55. }
  56. }
  57. // Trim off common prefix (speedup).
  58. let commonlength = diff_commonPrefix(text1, text2);
  59. const commonprefix = text1.substring(0, commonlength);
  60. text1 = text1.substring(commonlength);
  61. text2 = text2.substring(commonlength);
  62. // Trim off common suffix (speedup).
  63. commonlength = diff_commonSuffix(text1, text2);
  64. const commonsuffix = text1.substring(text1.length - commonlength);
  65. text1 = text1.substring(0, text1.length - commonlength);
  66. text2 = text2.substring(0, text2.length - commonlength);
  67. // Compute the diff on the middle block.
  68. const diffs = diff_compute_(text1, text2);
  69. // Restore the prefix and suffix.
  70. if (commonprefix) {
  71. diffs.unshift([DIFF_EQUAL, commonprefix]);
  72. }
  73. if (commonsuffix) {
  74. diffs.push([DIFF_EQUAL, commonsuffix]);
  75. }
  76. diff_cleanupMerge(diffs, _fix_unicode);
  77. return diffs;
  78. }
  79. /**
  80. * Find the differences between two texts. Assumes that the texts do not
  81. * have any common prefix or suffix.
  82. * @param {string} text1 Old string to be diffed.
  83. * @param {string} text2 New string to be diffed.
  84. * @return {Array} Array of diff tuples.
  85. */
  86. function diff_compute_(text1, text2) {
  87. let diffs;
  88. if (!text1) {
  89. // Just add some text (speedup).
  90. return [[DIFF_INSERT, text2]];
  91. }
  92. if (!text2) {
  93. // Just delete some text (speedup).
  94. return [[DIFF_DELETE, text1]];
  95. }
  96. const longtext = text1.length > text2.length ? text1 : text2;
  97. const shorttext = text1.length > text2.length ? text2 : text1;
  98. const i = longtext.indexOf(shorttext);
  99. if (i !== -1) {
  100. // Shorter text is inside the longer text (speedup).
  101. diffs = [
  102. [DIFF_INSERT, longtext.substring(0, i)],
  103. [DIFF_EQUAL, shorttext],
  104. [DIFF_INSERT, longtext.substring(i + shorttext.length)]
  105. ];
  106. // Swap insertions for deletions if diff is reversed.
  107. if (text1.length > text2.length) {
  108. diffs[0][0] = diffs[2][0] = DIFF_DELETE;
  109. }
  110. return diffs;
  111. }
  112. if (shorttext.length === 1) {
  113. // Single character string.
  114. // After the previous speedup, the character can't be an equality.
  115. return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];
  116. }
  117. // Check to see if the problem can be split in two.
  118. var hm = diff_halfMatch_(text1, text2);
  119. if (hm) {
  120. // A half-match was found, sort out the return data.
  121. var text1_a = hm[0];
  122. var text1_b = hm[1];
  123. var text2_a = hm[2];
  124. var text2_b = hm[3];
  125. var mid_common = hm[4];
  126. // Send both pairs off for separate processing.
  127. var diffs_a = diff_main(text1_a, text2_a);
  128. var diffs_b = diff_main(text1_b, text2_b);
  129. // Merge the results.
  130. return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b);
  131. }
  132. return diff_bisect_(text1, text2);
  133. }
  134. /**
  135. * Find the 'middle snake' of a diff, split the problem in two
  136. * and return the recursively constructed diff.
  137. * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.
  138. * @param {string} text1 Old string to be diffed.
  139. * @param {string} text2 New string to be diffed.
  140. * @return {Array} Array of diff tuples.
  141. * @private
  142. */
  143. function diff_bisect_(text1, text2) {
  144. // Cache the text lengths to prevent multiple calls.
  145. const text1_length = text1.length;
  146. const text2_length = text2.length;
  147. const max_d = Math.ceil((text1_length + text2_length) / 2);
  148. const v_offset = max_d;
  149. const v_length = 2 * max_d;
  150. const v1 = new Array(v_length);
  151. const v2 = new Array(v_length);
  152. // Setting all elements to -1 is faster in Chrome & Firefox than mixing
  153. // integers and undefined.
  154. for (var x = 0; x < v_length; x++) {
  155. v1[x] = -1;
  156. v2[x] = -1;
  157. }
  158. v1[v_offset + 1] = 0;
  159. v2[v_offset + 1] = 0;
  160. const delta = text1_length - text2_length;
  161. // If the total number of characters is odd, then the front path will collide
  162. // with the reverse path.
  163. const front = (delta % 2 !== 0);
  164. // Offsets for start and end of k loop.
  165. // Prevents mapping of space beyond the grid.
  166. let k1start = 0;
  167. let k1end = 0;
  168. let k2start = 0;
  169. let k2end = 0;
  170. for (let d = 0; d < max_d; d++) {
  171. // Walk the front path one step.
  172. for (let k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
  173. const k1_offset = v_offset + k1;
  174. let x1;
  175. if (k1 === -d || (k1 !== d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
  176. x1 = v1[k1_offset + 1];
  177. } else {
  178. x1 = v1[k1_offset - 1] + 1;
  179. }
  180. let y1 = x1 - k1;
  181. while (
  182. x1 < text1_length && y1 < text2_length &&
  183. text1.charAt(x1) === text2.charAt(y1)
  184. ) {
  185. x1++;
  186. y1++;
  187. }
  188. v1[k1_offset] = x1;
  189. if (x1 > text1_length) {
  190. // Ran off the right of the graph.
  191. k1end += 2;
  192. } else if (y1 > text2_length) {
  193. // Ran off the bottom of the graph.
  194. k1start += 2;
  195. } else if (front) {
  196. const k2_offset = v_offset + delta - k1;
  197. if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] !== -1) {
  198. // Mirror x2 onto top-left coordinate system.
  199. const x2 = text1_length - v2[k2_offset];
  200. if (x1 >= x2) {
  201. // Overlap detfrontected.
  202. return diff_bisectSplit_(text1, text2, x1, y1);
  203. }
  204. }
  205. }
  206. }
  207. // Walk the reverse path one step.
  208. for (let k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
  209. const k2_offset = v_offset + k2;
  210. let x2;
  211. if (k2 === -d || (k2 !== d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
  212. x2 = v2[k2_offset + 1];
  213. } else {
  214. x2 = v2[k2_offset - 1] + 1;
  215. }
  216. let y2 = x2 - k2;
  217. while (
  218. x2 < text1_length && y2 < text2_length &&
  219. text1.charAt(text1_length - x2 - 1) === text2.charAt(text2_length - y2 - 1)
  220. ) {
  221. x2++;
  222. y2++;
  223. }
  224. v2[k2_offset] = x2;
  225. if (x2 > text1_length) {
  226. // Ran off the left of the graph.
  227. k2end += 2;
  228. } else if (y2 > text2_length) {
  229. // Ran off the top of the graph.
  230. k2start += 2;
  231. } else if (!front) {
  232. const k1_offset = v_offset + delta - k2;
  233. if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] !== -1) {
  234. const x1 = v1[k1_offset];
  235. const y1 = v_offset + x1 - k1_offset;
  236. // Mirror x2 onto top-left coordinate system.
  237. x2 = text1_length - x2;
  238. if (x1 >= x2) {
  239. // Overlap detected.
  240. return diff_bisectSplit_(text1, text2, x1, y1);
  241. }
  242. }
  243. }
  244. }
  245. }
  246. // Diff took too long and hit the deadline or
  247. // number of diffs equals number of characters, no commonality at all.
  248. return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];
  249. }
  250. /**
  251. * Given the location of the 'middle snake', split the diff in two parts
  252. * and recurse.
  253. * @param {string} text1 Old string to be diffed.
  254. * @param {string} text2 New string to be diffed.
  255. * @param {number} x Index of split point in text1.
  256. * @param {number} y Index of split point in text2.
  257. * @return {Array} Array of diff tuples.
  258. */
  259. function diff_bisectSplit_(text1, text2, x, y) {
  260. const text1a = text1.substring(0, x);
  261. const text2a = text2.substring(0, y);
  262. const text1b = text1.substring(x);
  263. const text2b = text2.substring(y);
  264. // Compute both diffs serially.
  265. const diffs = diff_main(text1a, text2a);
  266. const diffsb = diff_main(text1b, text2b);
  267. return diffs.concat(diffsb);
  268. }
  269. /**
  270. * Determine the common prefix of two strings.
  271. * @param {string} text1 First string.
  272. * @param {string} text2 Second string.
  273. * @return {number} The number of characters common to the start of each
  274. * string.
  275. */
  276. function diff_commonPrefix(text1, text2) {
  277. // Quick check for common null cases.
  278. if (!text1 || !text2 || text1.charAt(0) !== text2.charAt(0)) {
  279. return 0;
  280. }
  281. // Binary search.
  282. // Performance analysis: http://neil.fraser.name/news/2007/10/09/
  283. let pointermin = 0;
  284. let pointermax = Math.min(text1.length, text2.length);
  285. let pointermid = pointermax;
  286. let pointerstart = 0;
  287. while (pointermin < pointermid) {
  288. if (
  289. text1.substring(pointerstart, pointermid) ==
  290. text2.substring(pointerstart, pointermid)
  291. ) {
  292. pointermin = pointermid;
  293. pointerstart = pointermin;
  294. } else {
  295. pointermax = pointermid;
  296. }
  297. pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
  298. }
  299. if (is_surrogate_pair_start(text1.charCodeAt(pointermid - 1))) {
  300. pointermid--;
  301. }
  302. return pointermid;
  303. }
  304. /**
  305. * Determine the common suffix of two strings.
  306. * @param {string} text1 First string.
  307. * @param {string} text2 Second string.
  308. * @return {number} The number of characters common to the end of each string.
  309. */
  310. function diff_commonSuffix(text1, text2) {
  311. // Quick check for common null cases.
  312. if (!text1 || !text2 || text1.slice(-1) !== text2.slice(-1)) {
  313. return 0;
  314. }
  315. // Binary search.
  316. // Performance analysis: http://neil.fraser.name/news/2007/10/09/
  317. let pointermin = 0;
  318. let pointermax = Math.min(text1.length, text2.length);
  319. let pointermid = pointermax;
  320. let pointerend = 0;
  321. while (pointermin < pointermid) {
  322. if (
  323. text1.substring(text1.length - pointermid, text1.length - pointerend) ==
  324. text2.substring(text2.length - pointermid, text2.length - pointerend)
  325. ) {
  326. pointermin = pointermid;
  327. pointerend = pointermin;
  328. } else {
  329. pointermax = pointermid;
  330. }
  331. pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
  332. }
  333. if (is_surrogate_pair_end(text1.charCodeAt(text1.length - pointermid))) {
  334. pointermid--;
  335. }
  336. return pointermid;
  337. }
  338. /**
  339. * Do the two texts share a substring which is at least half the length of the
  340. * longer text?
  341. * This speedup can produce non-minimal diffs.
  342. * @param {string} text1 First string.
  343. * @param {string} text2 Second string.
  344. * @return {Array.<string>} Five element Array, containing the prefix of
  345. * text1, the suffix of text1, the prefix of text2, the suffix of
  346. * text2 and the common middle. Or null if there was no match.
  347. */
  348. function diff_halfMatch_(text1, text2) {
  349. const longtext = text1.length > text2.length ? text1 : text2;
  350. const shorttext = text1.length > text2.length ? text2 : text1;
  351. if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {
  352. return null; // Pointless.
  353. }
  354. /**
  355. * Does a substring of shorttext exist within longtext such that the substring
  356. * is at least half the length of longtext?
  357. * Closure, but does not reference any external variables.
  358. * @param {string} longtext Longer string.
  359. * @param {string} shorttext Shorter string.
  360. * @param {number} i Start index of quarter length substring within longtext.
  361. * @return {Array.<string>} Five element Array, containing the prefix of
  362. * longtext, the suffix of longtext, the prefix of shorttext, the suffix
  363. * of shorttext and the common middle. Or null if there was no match.
  364. * @private
  365. */
  366. function diff_halfMatchI_(longtext, shorttext, i) {
  367. // Start with a 1/4 length substring at position i as a seed.
  368. const seed = longtext.substring(i, i + Math.floor(longtext.length / 4));
  369. let j = -1;
  370. let best_common = '';
  371. let best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;
  372. while ((j = shorttext.indexOf(seed, j + 1)) !== -1) {
  373. const prefixLength = diff_commonPrefix(
  374. longtext.substring(i), shorttext.substring(j));
  375. const suffixLength = diff_commonSuffix(
  376. longtext.substring(0, i), shorttext.substring(0, j));
  377. if (best_common.length < suffixLength + prefixLength) {
  378. best_common = shorttext.substring(
  379. j - suffixLength, j) + shorttext.substring(j, j + prefixLength);
  380. best_longtext_a = longtext.substring(0, i - suffixLength);
  381. best_longtext_b = longtext.substring(i + prefixLength);
  382. best_shorttext_a = shorttext.substring(0, j - suffixLength);
  383. best_shorttext_b = shorttext.substring(j + prefixLength);
  384. }
  385. }
  386. if (best_common.length * 2 >= longtext.length) {
  387. return [
  388. best_longtext_a, best_longtext_b,
  389. best_shorttext_a, best_shorttext_b, best_common
  390. ];
  391. } else {
  392. return null;
  393. }
  394. }
  395. // First check if the second quarter is the seed for a half-match.
  396. const hm1 = diff_halfMatchI_(longtext, shorttext, Math.ceil(longtext.length / 4));
  397. // Check again based on the third quarter.
  398. const hm2 = diff_halfMatchI_(longtext, shorttext, Math.ceil(longtext.length / 2));
  399. let hm;
  400. if (!hm1 && !hm2) {
  401. return null;
  402. } else if (!hm2) {
  403. hm = hm1;
  404. } else if (!hm1) {
  405. hm = hm2;
  406. } else {
  407. // Both matched. Select the longest.
  408. hm = hm1[4].length > hm2[4].length ? hm1 : hm2;
  409. }
  410. // A half-match was found, sort out the return data.
  411. let text1_a, text1_b, text2_a, text2_b;
  412. if (text1.length > text2.length) {
  413. text1_a = hm[0];
  414. text1_b = hm[1];
  415. text2_a = hm[2];
  416. text2_b = hm[3];
  417. } else {
  418. text2_a = hm[0];
  419. text2_b = hm[1];
  420. text1_a = hm[2];
  421. text1_b = hm[3];
  422. }
  423. const mid_common = hm[4];
  424. return [text1_a, text1_b, text2_a, text2_b, mid_common];
  425. }
  426. /**
  427. * Reorder and merge like edit sections. Merge equalities.
  428. * Any edit section can move as long as it doesn't cross an equality.
  429. * @param {Array} diffs Array of diff tuples.
  430. * @param {boolean} fix_unicode Whether to normalize to a unicode-correct diff
  431. */
  432. function diff_cleanupMerge(diffs, fix_unicode) {
  433. diffs.push([DIFF_EQUAL, '']); // Add a dummy entry at the end.
  434. let pointer = 0;
  435. let count_delete = 0;
  436. let count_insert = 0;
  437. let text_delete = '';
  438. let text_insert = '';
  439. let commonlength;
  440. let previous_equality;
  441. while (pointer < diffs.length) {
  442. if (pointer < diffs.length - 1 && !diffs[pointer][1]) {
  443. diffs.splice(pointer, 1);
  444. continue;
  445. }
  446. switch (diffs[pointer][0]) {
  447. case DIFF_INSERT:
  448. count_insert++;
  449. text_insert += diffs[pointer][1];
  450. pointer++;
  451. break;
  452. case DIFF_DELETE:
  453. count_delete++;
  454. text_delete += diffs[pointer][1];
  455. pointer++;
  456. break;
  457. case DIFF_EQUAL:
  458. previous_equality = pointer - count_insert - count_delete - 1;
  459. if (fix_unicode) {
  460. // prevent splitting of unicode surrogate pairs. when fix_unicode is true,
  461. // we assume that the old and new text in the diff are complete and correct
  462. // unicode-encoded JS strings, but the tuple boundaries may fall between
  463. // surrogate pairs. we fix this by shaving off stray surrogates from the end
  464. // of the previous equality and the beginning of this equality. this may create
  465. // empty equalities or a common prefix or suffix. for example, if AB and AC are
  466. // emojis, `[[0, 'A'], [-1, 'BA'], [0, 'C']]` would turn into deleting 'ABAC' and
  467. // inserting 'AC', and then the common suffix 'AC' will be eliminated. in this
  468. // particular case, both equalities go away, we absorb any previous inequalities,
  469. // and we keep scanning for the next equality before rewriting the tuples.
  470. if (previous_equality >= 0 && ends_with_pair_start(diffs[previous_equality][1])) {
  471. const stray = diffs[previous_equality][1].slice(-1);
  472. diffs[previous_equality][1] = diffs[previous_equality][1].slice(0, -1);
  473. text_delete = stray + text_delete;
  474. text_insert = stray + text_insert;
  475. if (!diffs[previous_equality][1]) {
  476. // emptied out previous equality, so delete it and include previous delete/insert
  477. diffs.splice(previous_equality, 1);
  478. pointer--;
  479. var k = previous_equality - 1;
  480. if (diffs[k] && diffs[k][0] === DIFF_INSERT) {
  481. count_insert++;
  482. text_insert = diffs[k][1] + text_insert;
  483. k--;
  484. }
  485. if (diffs[k] && diffs[k][0] === DIFF_DELETE) {
  486. count_delete++;
  487. text_delete = diffs[k][1] + text_delete;
  488. k--;
  489. }
  490. previous_equality = k;
  491. }
  492. }
  493. if (starts_with_pair_end(diffs[pointer][1])) {
  494. const stray = diffs[pointer][1].charAt(0);
  495. diffs[pointer][1] = diffs[pointer][1].slice(1);
  496. text_delete += stray;
  497. text_insert += stray;
  498. }
  499. }
  500. if (pointer < diffs.length - 1 && !diffs[pointer][1]) {
  501. // for empty equality not at end, wait for next equality
  502. diffs.splice(pointer, 1);
  503. break;
  504. }
  505. if (text_delete.length > 0 || text_insert.length > 0) {
  506. // note that diff_commonPrefix and diff_commonSuffix are unicode-aware
  507. if (text_delete.length > 0 && text_insert.length > 0) {
  508. // Factor out any common prefixes.
  509. commonlength = diff_commonPrefix(text_insert, text_delete);
  510. if (commonlength !== 0) {
  511. if (previous_equality >= 0) {
  512. diffs[previous_equality][1] += text_insert.substring(0, commonlength);
  513. } else {
  514. diffs.splice(0, 0, [DIFF_EQUAL, text_insert.substring(0, commonlength)]);
  515. pointer++;
  516. }
  517. text_insert = text_insert.substring(commonlength);
  518. text_delete = text_delete.substring(commonlength);
  519. }
  520. // Factor out any common suffixes.
  521. commonlength = diff_commonSuffix(text_insert, text_delete);
  522. if (commonlength !== 0) {
  523. diffs[pointer][1] =
  524. text_insert.substring(text_insert.length - commonlength) + diffs[pointer][1];
  525. text_insert = text_insert.substring(0, text_insert.length - commonlength);
  526. text_delete = text_delete.substring(0, text_delete.length - commonlength);
  527. }
  528. }
  529. // Delete the offending records and add the merged ones.
  530. const n = count_insert + count_delete;
  531. if (text_delete.length === 0 && text_insert.length === 0) {
  532. diffs.splice(pointer - n, n);
  533. pointer = pointer - n;
  534. } else if (text_delete.length === 0) {
  535. diffs.splice(pointer - n, n, [DIFF_INSERT, text_insert]);
  536. pointer = pointer - n + 1;
  537. } else if (text_insert.length === 0) {
  538. diffs.splice(pointer - n, n, [DIFF_DELETE, text_delete]);
  539. pointer = pointer - n + 1;
  540. } else {
  541. diffs.splice(pointer - n, n, [DIFF_DELETE, text_delete], [DIFF_INSERT, text_insert]);
  542. pointer = pointer - n + 2;
  543. }
  544. }
  545. if (pointer !== 0 && diffs[pointer - 1][0] === DIFF_EQUAL) {
  546. // Merge this equality with the previous one.
  547. diffs[pointer - 1][1] += diffs[pointer][1];
  548. diffs.splice(pointer, 1);
  549. } else {
  550. pointer++;
  551. }
  552. count_insert = 0;
  553. count_delete = 0;
  554. text_delete = '';
  555. text_insert = '';
  556. break;
  557. }
  558. }
  559. if (diffs[diffs.length - 1][1] === '') {
  560. diffs.pop(); // Remove the dummy entry at the end.
  561. }
  562. // Second pass: look for single edits surrounded on both sides by equalities
  563. // which can be shifted sideways to eliminate an equality.
  564. // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
  565. let changes = false;
  566. pointer = 1;
  567. // Intentionally ignore the first and last element (don't need checking).
  568. while (pointer < diffs.length - 1) {
  569. if (diffs[pointer - 1][0] === DIFF_EQUAL &&
  570. diffs[pointer + 1][0] === DIFF_EQUAL) {
  571. // This is a single edit surrounded by equalities.
  572. if (diffs[pointer][1].substring(diffs[pointer][1].length -
  573. diffs[pointer - 1][1].length) === diffs[pointer - 1][1]) {
  574. // Shift the edit over the previous equality.
  575. diffs[pointer][1] = diffs[pointer - 1][1] +
  576. diffs[pointer][1].substring(0, diffs[pointer][1].length -
  577. diffs[pointer - 1][1].length);
  578. diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];
  579. diffs.splice(pointer - 1, 1);
  580. changes = true;
  581. } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==
  582. diffs[pointer + 1][1]) {
  583. // Shift the edit over the next equality.
  584. diffs[pointer - 1][1] += diffs[pointer + 1][1];
  585. diffs[pointer][1] =
  586. diffs[pointer][1].substring(diffs[pointer + 1][1].length) +
  587. diffs[pointer + 1][1];
  588. diffs.splice(pointer + 1, 1);
  589. changes = true;
  590. }
  591. }
  592. pointer++;
  593. }
  594. // If shifts were made, the diff needs reordering and another shift sweep.
  595. if (changes) {
  596. diff_cleanupMerge(diffs, fix_unicode);
  597. }
  598. }
  599. function is_surrogate_pair_start(charCode) {
  600. return charCode >= 0xD800 && charCode <= 0xDBFF;
  601. }
  602. function is_surrogate_pair_end(charCode) {
  603. return charCode >= 0xDC00 && charCode <= 0xDFFF;
  604. }
  605. function starts_with_pair_end(str) {
  606. return is_surrogate_pair_end(str.charCodeAt(0));
  607. }
  608. function ends_with_pair_start(str) {
  609. return is_surrogate_pair_start(str.charCodeAt(str.length - 1));
  610. }
  611. function remove_empty_tuples(tuples) {
  612. const ret = [];
  613. for (let i = 0; i < tuples.length; i++) {
  614. if (tuples[i][1].length > 0) {
  615. ret.push(tuples[i]);
  616. }
  617. }
  618. return ret;
  619. }
  620. function make_edit_splice(before, oldMiddle, newMiddle, after) {
  621. if (ends_with_pair_start(before) || starts_with_pair_end(after)) {
  622. return null;
  623. }
  624. return remove_empty_tuples([
  625. [DIFF_EQUAL, before],
  626. [DIFF_DELETE, oldMiddle],
  627. [DIFF_INSERT, newMiddle],
  628. [DIFF_EQUAL, after]
  629. ]);
  630. }
  631. function find_cursor_edit_diff(oldText, newText, cursor_pos) {
  632. // note: this runs after equality check has ruled out exact equality
  633. const oldRange = typeof cursor_pos === 'number' ?
  634. { index: cursor_pos, length: 0 } : cursor_pos.oldRange;
  635. const newRange = typeof cursor_pos === 'number' ?
  636. null : cursor_pos.newRange;
  637. // take into account the old and new selection to generate the best diff
  638. // possible for a text edit. for example, a text change from "xxx" to "xx"
  639. // could be a delete or forwards-delete of any one of the x's, or the
  640. // result of selecting two of the x's and typing "x".
  641. const oldLength = oldText.length;
  642. const newLength = newText.length;
  643. if (oldRange.length === 0 && (newRange === null || newRange.length === 0)) {
  644. // see if we have an insert or delete before or after cursor
  645. const oldCursor = oldRange.index;
  646. const oldBefore = oldText.slice(0, oldCursor);
  647. const oldAfter = oldText.slice(oldCursor);
  648. const maybeNewCursor = newRange ? newRange.index : null;
  649. editBefore: {
  650. // is this an insert or delete right before oldCursor?
  651. const newCursor = oldCursor + newLength - oldLength;
  652. if (maybeNewCursor !== null && maybeNewCursor !== newCursor) {
  653. break editBefore;
  654. }
  655. if (newCursor < 0 || newCursor > newLength) {
  656. break editBefore;
  657. }
  658. const newBefore = newText.slice(0, newCursor);
  659. const newAfter = newText.slice(newCursor);
  660. if (newAfter !== oldAfter) {
  661. break editBefore;
  662. }
  663. const prefixLength = Math.min(oldCursor, newCursor);
  664. const oldPrefix = oldBefore.slice(0, prefixLength);
  665. const newPrefix = newBefore.slice(0, prefixLength);
  666. if (oldPrefix !== newPrefix) {
  667. break editBefore;
  668. }
  669. const oldMiddle = oldBefore.slice(prefixLength);
  670. const newMiddle = newBefore.slice(prefixLength);
  671. return make_edit_splice(oldPrefix, oldMiddle, newMiddle, oldAfter);
  672. }
  673. editAfter: {
  674. // is this an insert or delete right after oldCursor?
  675. if (maybeNewCursor !== null && maybeNewCursor !== oldCursor) {
  676. break editAfter;
  677. }
  678. const cursor = oldCursor;
  679. const newBefore = newText.slice(0, cursor);
  680. const newAfter = newText.slice(cursor);
  681. if (newBefore !== oldBefore) {
  682. break editAfter;
  683. }
  684. const suffixLength = Math.min(oldLength - cursor, newLength - cursor);
  685. const oldSuffix = oldAfter.slice(oldAfter.length - suffixLength);
  686. const newSuffix = newAfter.slice(newAfter.length - suffixLength);
  687. if (oldSuffix !== newSuffix) {
  688. break editAfter;
  689. }
  690. const oldMiddle = oldAfter.slice(0, oldAfter.length - suffixLength);
  691. const newMiddle = newAfter.slice(0, newAfter.length - suffixLength);
  692. return make_edit_splice(oldBefore, oldMiddle, newMiddle, oldSuffix);
  693. }
  694. }
  695. if (oldRange.length > 0 && newRange && newRange.length === 0) {
  696. replaceRange: {
  697. // see if diff could be a splice of the old selection range
  698. const oldPrefix = oldText.slice(0, oldRange.index);
  699. const oldSuffix = oldText.slice(oldRange.index + oldRange.length);
  700. const prefixLength = oldPrefix.length;
  701. const suffixLength = oldSuffix.length;
  702. if (newLength < prefixLength + suffixLength) {
  703. break replaceRange;
  704. }
  705. const newPrefix = newText.slice(0, prefixLength);
  706. const newSuffix = newText.slice(newLength - suffixLength);
  707. if (oldPrefix !== newPrefix || oldSuffix !== newSuffix) {
  708. break replaceRange;
  709. }
  710. const oldMiddle = oldText.slice(prefixLength, oldLength - suffixLength);
  711. const newMiddle = newText.slice(prefixLength, newLength - suffixLength);
  712. return make_edit_splice(oldPrefix, oldMiddle, newMiddle, oldSuffix);
  713. }
  714. }
  715. return null;
  716. }
  717. function diff(text1, text2, cursor_pos) {
  718. // only pass fix_unicode=true at the top level, not when diff_main is
  719. // recursively invoked
  720. return diff_main(text1, text2, cursor_pos, true);
  721. }
  722. diff.INSERT = DIFF_INSERT;
  723. diff.DELETE = DIFF_DELETE;
  724. diff.EQUAL = DIFF_EQUAL;
  725. export default diff;