@sanity/diff-match-patch - npm Package Compare versions

Comparing version 3.0.1 to 3.1.1

dist/index.d.ts

@@ -8,8 +8,29 @@ /**
  * @param base - The base string to use for counting bytes
+ * @param options - Options for the adjustment of indices
  * @returns A new array of patches with adjusted indicies
  * @beta
  */
-export declare function adjustIndiciesToUcs2(patches: Patch[], base: string): Patch[]
+export declare function adjustIndiciesToUcs2(
+  patches: Patch[],
+  base: string,
+  options?: AdjustmentOptions
+): Patch[]
 
 /**
+ * Options for the index adjustment operations.
+ *
+ * @public
+ */
+export declare interface AdjustmentOptions {
+  /**
+   * When converting indices between UTF-8 and UCS-2, certain scenarios can occur
+   * where we go beyond the target offset. This can happen in particular with
+   * surrogate pairs/high codepoints, when the base string we are applying the
+   * patch to does not fully match the one that was used to generate the patch.
+   * Defaults to `false`.
+   */
+  allowExceedingIndices?: boolean
+}
+
+/**
  * Merge a set of patches onto the text. Returns patched text, as well as a
@@ -20,2 +41,3 @@ * list of true/false values indicating which patches were applied.
  * @param text - Old text.
+ * @param opts - Optional settings for the patch application.
  * @returns Two element Array, containing the new text and an array of boolean values.
@@ -46,2 +68,10 @@ * @public
   deleteThreshold: number
+  /**
+   * When converting indices between UTF-8 and UCS-2, certain scenarios can occur
+   * where we go beyond the target offset. This can happen in particular with
+   * surrogate pairs/high codepoints, when the base string we are applying the
+   * patch to does not fully match the one that was used to generate the patch.
+   * Defaults to `false`.
+   */
+  allowExceedingIndices: boolean
 }
@@ -48,0 +78,0 @@

dist/index.js

@@ -50,16 +50,16 @@ function isHighSurrogate(char) {
   }
-  let pointermin = 0;
-  let pointermax = Math.min(text1.length, text2.length);
-  let pointermid = pointermax;
-  let pointerstart = 0;
-  while (pointermin < pointermid) {
-    if (text1.substring(pointerstart, pointermid) == text2.substring(pointerstart, pointermid)) {
-      pointermin = pointermid;
-      pointerstart = pointermin;
+  let pointerMin = 0;
+  let pointerMax = Math.min(text1.length, text2.length);
+  let pointerMid = pointerMax;
+  let pointerStart = 0;
+  while (pointerMin < pointerMid) {
+    if (text1.substring(pointerStart, pointerMid) === text2.substring(pointerStart, pointerMid)) {
+      pointerMin = pointerMid;
+      pointerStart = pointerMin;
     } else {
-      pointermax = pointermid;
+      pointerMax = pointerMid;
     }
-    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
+    pointerMid = Math.floor((pointerMax - pointerMin) / 2 + pointerMin);
   }
-  return pointermid;
+  return pointerMid;
 }
@@ -70,23 +70,23 @@ function getCommonSuffix(text1, text2) {
   }
-  let pointermin = 0;
-  let pointermax = Math.min(text1.length, text2.length);
-  let pointermid = pointermax;
-  let pointerend = 0;
-  while (pointermin < pointermid) {
-    if (text1.substring(text1.length - pointermid, text1.length - pointerend) === text2.substring(text2.length - pointermid, text2.length - pointerend)) {
-      pointermin = pointermid;
-      pointerend = pointermin;
+  let pointerMin = 0;
+  let pointerMax = Math.min(text1.length, text2.length);
+  let pointerMid = pointerMax;
+  let pointerEnd = 0;
+  while (pointerMin < pointerMid) {
+    if (text1.substring(text1.length - pointerMid, text1.length - pointerEnd) === text2.substring(text2.length - pointerMid, text2.length - pointerEnd)) {
+      pointerMin = pointerMid;
+      pointerEnd = pointerMin;
     } else {
-      pointermax = pointermid;
+      pointerMax = pointerMid;
     }
-    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
+    pointerMid = Math.floor((pointerMax - pointerMin) / 2 + pointerMin);
   }
-  return pointermid;
+  return pointerMid;
 }
 function cleanupSemantic(rawDiffs) {
   let diffs = rawDiffs.map(diff => cloneDiff(diff));
-  let changes = false;
+  let hasChanges = false;
   const equalities = [];
   let equalitiesLength = 0;
-  let lastequality = null;
+  let lastEquality = null;
   let pointer = 0;
@@ -104,3 +104,3 @@ let lengthInsertions1 = 0;
       lengthDeletions2 = 0;
-      lastequality = diffs[pointer][1];
+      lastEquality = diffs[pointer][1];
     } else {
@@ -112,4 +112,4 @@ if (diffs[pointer][0] === DIFF_INSERT) {
       }
-      if (lastequality && lastequality.length <= Math.max(lengthInsertions1, lengthDeletions1) && lastequality.length <= Math.max(lengthInsertions2, lengthDeletions2)) {
-        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastequality]);
+      if (lastEquality && lastEquality.length <= Math.max(lengthInsertions1, lengthDeletions1) && lastEquality.length <= Math.max(lengthInsertions2, lengthDeletions2)) {
+        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastEquality]);
         diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;
@@ -123,4 +123,4 @@ equalitiesLength--;
         lengthDeletions2 = 0;
-        lastequality = null;
-        changes = true;
+        lastEquality = null;
+        hasChanges = true;
       }
@@ -130,3 +130,3 @@ }
   }
-  if (changes) {
+  if (hasChanges) {
     diffs = cleanupMerge(diffs);
@@ -317,3 +317,3 @@ }
   }
-  let changes = false;
+  let hasChanges = false;
   pointer = 1;
@@ -326,3 +326,3 @@ while (pointer < diffs.length - 1) {
         diffs.splice(pointer - 1, 1);
-        changes = true;
+        hasChanges = true;
       } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) === diffs[pointer + 1][1]) {
@@ -332,3 +332,3 @@ diffs[pointer - 1][1] += diffs[pointer + 1][1];
         diffs.splice(pointer + 1, 1);
-        changes = true;
+        hasChanges = true;
       }
@@ -338,3 +338,3 @@ }
   }
-  if (changes) {
+  if (hasChanges) {
     diffs = cleanupMerge(diffs);
@@ -353,6 +353,6 @@ }
   let diffs = rawDiffs.map(diff => cloneDiff(diff));
-  let changes = false;
+  let hasChanges = false;
   const equalities = [];
   let equalitiesLength = 0;
-  let lastequality = null;
+  let lastEquality = null;
   let pointer = 0;
@@ -369,6 +369,6 @@ let preIns = false;
         preDel = postDel;
-        lastequality = diffs[pointer][1];
+        lastEquality = diffs[pointer][1];
       } else {
         equalitiesLength = 0;
-        lastequality = null;
+        lastEquality = null;
       }
@@ -383,7 +383,7 @@ postIns = false;
       }
-      if (lastequality && (preIns && preDel && postIns && postDel || lastequality.length < editCost / 2 && trueCount(preIns, preDel, postIns, postDel) === 3)) {
-        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastequality]);
+      if (lastEquality && (preIns && preDel && postIns && postDel || lastEquality.length < editCost / 2 && trueCount(preIns, preDel, postIns, postDel) === 3)) {
+        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastEquality]);
         diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT;
         equalitiesLength--;
-        lastequality = null;
+        lastEquality = null;
         if (preIns && preDel) {
@@ -399,3 +399,3 @@ postIns = true;
         }
-        changes = true;
+        hasChanges = true;
       }
@@ -405,3 +405,3 @@ }
   }
-  if (changes) {
+  if (hasChanges) {
     diffs = cleanupMerge(diffs);
@@ -511,26 +511,2 @@ }
 }
-function halfMatchI(longtext, shorttext, i) {
-  const seed = longtext.substring(i, i + Math.floor(longtext.length / 4));
-  let j = -1;
-  let bestCommon = "";
-  let bestLongtextA;
-  let bestLongtextB;
-  let bestShorttextA;
-  let bestShorttextB;
-  while ((j = shorttext.indexOf(seed, j + 1)) !== -1) {
-    const prefixLength = getCommonPrefix(longtext.substring(i), shorttext.substring(j));
-    const suffixLength = getCommonSuffix(longtext.substring(0, i), shorttext.substring(0, j));
-    if (bestCommon.length < suffixLength + prefixLength) {
-      bestCommon = shorttext.substring(j - suffixLength, j) + shorttext.substring(j, j + prefixLength);
-      bestLongtextA = longtext.substring(0, i - suffixLength);
-      bestLongtextB = longtext.substring(i + prefixLength);
-      bestShorttextA = shorttext.substring(0, j - suffixLength);
-      bestShorttextB = shorttext.substring(j + prefixLength);
-    }
-  }
-  if (bestCommon.length * 2 >= longtext.length) {
-    return [bestLongtextA || "", bestLongtextB || "", bestShorttextA || "", bestShorttextB || "", bestCommon || ""];
-  }
-  return null;
-}
 function findHalfMatch(text1, text2) {
@@ -541,19 +517,22 @@ let timeout = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 1;
   }
-  const longtext = text1.length > text2.length ? text1 : text2;
-  const shorttext = text1.length > text2.length ? text2 : text1;
-  if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {
+  const longText = text1.length > text2.length ? text1 : text2;
+  const shortText = text1.length > text2.length ? text2 : text1;
+  if (longText.length < 4 || shortText.length * 2 < longText.length) {
     return null;
   }
-  const hm1 = halfMatchI(longtext, shorttext, Math.ceil(longtext.length / 4));
-  const hm2 = halfMatchI(longtext, shorttext, Math.ceil(longtext.length / 2));
-  let hm;
-  if (hm1 && hm2) {
-    hm = hm1[4].length > hm2[4].length ? hm1 : hm2;
-  } else if (!hm1 && !hm2) {
+  const halfMatch1 = halfMatchI(longText, shortText, Math.ceil(longText.length / 4));
+  const halfMatch2 = halfMatchI(longText, shortText, Math.ceil(longText.length / 2));
+  let halfMatch;
+  if (halfMatch1 && halfMatch2) {
+    halfMatch = halfMatch1[4].length > halfMatch2[4].length ? halfMatch1 : halfMatch2;
+  } else if (!halfMatch1 && !halfMatch2) {
     return null;
-  } else if (!hm2) {
-    hm = hm1;
-  } else if (!hm1) {
-    hm = hm2;
+  } else if (!halfMatch2) {
+    halfMatch = halfMatch1;
+  } else if (!halfMatch1) {
+    halfMatch = halfMatch2;
   }
+  if (!halfMatch) {
+    throw new Error("Unable to find a half match.");
+  }
   let text1A;
@@ -563,18 +542,39 @@ let text1B;
   let text2B;
-  if (hm) {
-    if (text1.length > text2.length) {
-      text1A = hm[0];
-      text1B = hm[1];
-      text2A = hm[2];
-      text2B = hm[3];
-    } else {
-      text2A = hm[0];
-      text2B = hm[1];
-      text1A = hm[2];
-      text1B = hm[3];
+  if (text1.length > text2.length) {
+    text1A = halfMatch[0];
+    text1B = halfMatch[1];
+    text2A = halfMatch[2];
+    text2B = halfMatch[3];
+  } else {
+    text2A = halfMatch[0];
+    text2B = halfMatch[1];
+    text1A = halfMatch[2];
+    text1B = halfMatch[3];
+  }
+  const midCommon = halfMatch[4];
+  return [text1A, text1B, text2A, text2B, midCommon];
+}
+function halfMatchI(longText, shortText, i) {
+  const seed = longText.slice(i, i + Math.floor(longText.length / 4));
+  let j = -1;
+  let bestCommon = "";
+  let bestLongTextA;
+  let bestLongTextB;
+  let bestShortTextA;
+  let bestShortTextB;
+  while ((j = shortText.indexOf(seed, j + 1)) !== -1) {
+    const prefixLength = getCommonPrefix(longText.slice(i), shortText.slice(j));
+    const suffixLength = getCommonSuffix(longText.slice(0, i), shortText.slice(0, j));
+    if (bestCommon.length < suffixLength + prefixLength) {
+      bestCommon = shortText.slice(j - suffixLength, j) + shortText.slice(j, j + prefixLength);
+      bestLongTextA = longText.slice(0, i - suffixLength);
+      bestLongTextB = longText.slice(i + prefixLength);
+      bestShortTextA = shortText.slice(0, j - suffixLength);
+      bestShortTextB = shortText.slice(j + prefixLength);
     }
-    const midCommon = hm[4];
-    return [text1A, text1B, text2A, text2B, midCommon];
   }
-  throw new Error("nope");
+  if (bestCommon.length * 2 >= longText.length) {
+    return [bestLongTextA || "", bestLongTextB || "", bestShortTextA || "", bestShortTextB || "", bestCommon || ""];
+  }
+  return null;
 }
@@ -605,3 +605,3 @@ function charsToLines(diffs, lineArray) {
       }
-      let line = text.substring(lineStart, lineEnd + 1);
+      let line = text.slice(lineStart, lineEnd + 1);
       if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) : lineHash[line] !== void 0) {
@@ -611,3 +611,3 @@ chars += String.fromCharCode(lineHash[line]);
         if (lineArrayLength === maxLines) {
-          line = text.substring(lineStart);
+          line = text.slice(lineStart);
           lineEnd = text.length;
@@ -1014,2 +1014,3 @@ }
 function adjustIndiciesToUcs2(patches, base) {
+  let options = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : {};
   let byteOffset = 0;
@@ -1030,3 +1031,3 @@ let idx = 0;
     }
-    if (byteOffset !== target) {
+    if (!options.allowExceedingIndices && byteOffset !== target) {
       throw new Error("Failed to determine byte offset");
@@ -1403,3 +1404,5 @@ }
   }
-  const parsed = adjustIndiciesToUcs2(patches, text);
+  const parsed = adjustIndiciesToUcs2(patches, text, {
+    allowExceedingIndices: opts.allowExceedingIndices
+  });
   const margin = opts.margin || DEFAULT_MARGIN;
@@ -1576,3 +1579,3 @@ const deleteThreshold = opts.deleteThreshold || 0.4;
       try {
-        line = decodeURI(currentLine.substring(1));
+        line = decodeURI(currentLine.slice(1));
       } catch (ex) {
@@ -1579,0 +1582,0 @@ throw new Error("Illegal escape in parse: ".concat(currentLine));

package.json

 {
   "name": "@sanity/diff-match-patch",
-  "version": "3.0.1",
+  "version": "3.1.1",
   "description": "Robust diff, match and patch algorithms to perform operations required for synchronizing plain text",
@@ -5,0 +5,0 @@ "sideEffects": false,

src/diff/charsToLines.ts

@@ -13,3 +13,3 @@ import type {Diff} from './diff.js'
     const chars = diffs[x][1]
-    const text = []
+    const text: string[] = []
     for (let y = 0; y < chars.length; y++) {
@@ -16,0 +16,0 @@ text[y] = lineArray[chars.charCodeAt(y)]

src/diff/cleanup.ts

@@ -17,7 +17,7 @@ import {cloneDiff} from './clone.js'
 
-  let changes = false
-  const equalities = [] // Stack of indices where equalities are found.
+  let hasChanges = false
+  const equalities: number[] = [] // Stack of indices where equalities are found.
   let equalitiesLength = 0 // Keeping our own length var is faster in JS.
   /** @type {?string} */
-  let lastequality = null
+  let lastEquality = null
   // Always equal to diffs[equalities[equalitiesLength - 1]][1]
@@ -39,3 +39,3 @@ let pointer = 0 // Index of current position.
       lengthDeletions2 = 0
-      lastequality = diffs[pointer][1]
+      lastEquality = diffs[pointer][1]
     } else {
@@ -51,8 +51,8 @@ // An insertion or deletion.
       if (
-        lastequality &&
-        lastequality.length <= Math.max(lengthInsertions1, lengthDeletions1) &&
-        lastequality.length <= Math.max(lengthInsertions2, lengthDeletions2)
+        lastEquality &&
+        lastEquality.length <= Math.max(lengthInsertions1, lengthDeletions1) &&
+        lastEquality.length <= Math.max(lengthInsertions2, lengthDeletions2)
       ) {
         // Duplicate record.
-        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastequality])
+        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastEquality])
         // Change second copy to insert.
@@ -69,4 +69,4 @@ diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT
         lengthDeletions2 = 0
-        lastequality = null
-        changes = true
+        lastEquality = null
+        hasChanges = true
       }
@@ -78,3 +78,3 @@ }
   // Normalize the diff.
-  if (changes) {
+  if (hasChanges) {
     diffs = cleanupMerge(diffs)
@@ -352,3 +352,3 @@ }
   // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
-  let changes = false
+  let hasChanges = false
   pointer = 1
@@ -369,3 +369,3 @@ // Intentionally ignore the first and last element (don't need checking).
         diffs.splice(pointer - 1, 1)
-        changes = true
+        hasChanges = true
       } else if (
@@ -379,3 +379,3 @@ diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) === diffs[pointer + 1][1]
         diffs.splice(pointer + 1, 1)
-        changes = true
+        hasChanges = true
       }
@@ -386,3 +386,3 @@ }
   // If shifts were made, the diff needs reordering and another shift sweep.
-  if (changes) {
+  if (hasChanges) {
     diffs = cleanupMerge(diffs)
@@ -408,7 +408,6 @@ }
   let diffs = rawDiffs.map((diff) => cloneDiff(diff))
-  let changes = false
-  const equalities = [] // Stack of indices where equalities are found.
+  let hasChanges = false
+  const equalities: number[] = [] // Stack of indices where equalities are found.
   let equalitiesLength = 0 // Keeping our own length var is faster in JS.
-  /** @type {?string} */
-  let lastequality = null
+  let lastEquality: string | null = null
   // Always equal to diffs[equalities[equalitiesLength - 1]][1]
@@ -432,7 +431,7 @@ let pointer = 0 // Index of current position.
         preDel = postDel
-        lastequality = diffs[pointer][1]
+        lastEquality = diffs[pointer][1]
       } else {
         // Not a candidate, and can never become one.
         equalitiesLength = 0
-        lastequality = null
+        lastEquality = null
       }
@@ -457,14 +456,14 @@ postIns = false
       if (
-        lastequality &&
+        lastEquality &&
         ((preIns && preDel && postIns && postDel) ||
-          (lastequality.length < editCost / 2 && trueCount(preIns, preDel, postIns, postDel) === 3))
+          (lastEquality.length < editCost / 2 && trueCount(preIns, preDel, postIns, postDel) === 3))
       ) {
         // Duplicate record.
-        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastequality])
+        diffs.splice(equalities[equalitiesLength - 1], 0, [DIFF_DELETE, lastEquality])
         // Change second copy to insert.
         diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT
         equalitiesLength-- // Throw away the equality we just deleted;
-        lastequality = null
+        lastEquality = null
         if (preIns && preDel) {
-          // No changes made which could affect previous entry, keep going.
+          // No hasChanges made which could affect previous entry, keep going.
           postIns = true
@@ -479,3 +478,3 @@ postDel = true
         }
-        changes = true
+        hasChanges = true
       }
@@ -486,3 +485,3 @@ }
 
-  if (changes) {
+  if (hasChanges) {
     diffs = cleanupMerge(diffs)
@@ -489,0 +488,0 @@ }

src/diff/commonPrefix.ts

@@ -17,16 +17,16 @@ /**
   // Performance analysis: http://neil.fraser.name/news/2007/10/09/
-  let pointermin = 0
-  let pointermax = Math.min(text1.length, text2.length)
-  let pointermid = pointermax
-  let pointerstart = 0
-  while (pointermin < pointermid) {
-    if (text1.substring(pointerstart, pointermid) == text2.substring(pointerstart, pointermid)) {
-      pointermin = pointermid
-      pointerstart = pointermin
+  let pointerMin = 0
+  let pointerMax = Math.min(text1.length, text2.length)
+  let pointerMid = pointerMax
+  let pointerStart = 0
+  while (pointerMin < pointerMid) {
+    if (text1.substring(pointerStart, pointerMid) === text2.substring(pointerStart, pointerMid)) {
+      pointerMin = pointerMid
+      pointerStart = pointerMin
     } else {
-      pointermax = pointermid
+      pointerMax = pointerMid
     }
-    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin)
+    pointerMid = Math.floor((pointerMax - pointerMin) / 2 + pointerMin)
   }
-  return pointermid
+  return pointerMid
 }

src/diff/commonSuffix.ts

@@ -17,20 +17,20 @@ /**
   // Performance analysis: http://neil.fraser.name/news/2007/10/09/
-  let pointermin = 0
-  let pointermax = Math.min(text1.length, text2.length)
-  let pointermid = pointermax
-  let pointerend = 0
-  while (pointermin < pointermid) {
+  let pointerMin = 0
+  let pointerMax = Math.min(text1.length, text2.length)
+  let pointerMid = pointerMax
+  let pointerEnd = 0
+  while (pointerMin < pointerMid) {
     if (
-      text1.substring(text1.length - pointermid, text1.length - pointerend) ===
-      text2.substring(text2.length - pointermid, text2.length - pointerend)
+      text1.substring(text1.length - pointerMid, text1.length - pointerEnd) ===
+      text2.substring(text2.length - pointerMid, text2.length - pointerEnd)
     ) {
-      pointermin = pointermid
-      pointerend = pointermin
+      pointerMin = pointerMid
+      pointerEnd = pointerMin
     } else {
-      pointermax = pointermid
+      pointerMax = pointerMid
     }
-    pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin)
+    pointerMid = Math.floor((pointerMax - pointerMin) / 2 + pointerMin)
   }
 
-  return pointermid
+  return pointerMid
 }

src/diff/diffText.ts

@@ -11,3 +11,3 @@ import {DIFF_DELETE, DIFF_INSERT, type Diff} from './diff.js'
 export function diffText1(diffs: Diff[]): string {
-  const text = []
+  const text: string[] = []
   for (let x = 0; x < diffs.length; x++) {
@@ -29,3 +29,3 @@ if (diffs[x][0] !== DIFF_INSERT) {
 export function diffText2(diffs: Diff[]): string {
-  const text = []
+  const text: string[] = []
   for (let x = 0; x < diffs.length; x++) {
@@ -32,0 +32,0 @@ if (diffs[x][0] !== DIFF_DELETE) {

src/diff/halfMatch.ts

@@ -7,50 +7,3 @@ import {getCommonPrefix} from './commonPrefix.js'
 /**
- * Do the two texts share a substring which is at least half the length of the
- * longer text?
- * This speedup can produce non-minimal diffs.
- *
- * @param text1 - First string.
- * @param text2 - Second string.
- * @returns Five element Array, containing the prefix of
- *     text1, the suffix of text1, the prefix of text2, the suffix of
- *     text2 and the common middle.  Or null if there was no match.
- * @internal
- */
-function halfMatchI(longtext: string, shorttext: string, i: number): null | HalfMatch {
-  // Start with a 1/4 length substring at position i as a seed.
-  const seed = longtext.substring(i, i + Math.floor(longtext.length / 4))
-  let j = -1
-  let bestCommon = ''
-  let bestLongtextA
-  let bestLongtextB
-  let bestShorttextA
-  let bestShorttextB
-
-  while ((j = shorttext.indexOf(seed, j + 1)) !== -1) {
-    const prefixLength = getCommonPrefix(longtext.substring(i), shorttext.substring(j))
-    const suffixLength = getCommonSuffix(longtext.substring(0, i), shorttext.substring(0, j))
-    if (bestCommon.length < suffixLength + prefixLength) {
-      bestCommon =
-        shorttext.substring(j - suffixLength, j) + shorttext.substring(j, j + prefixLength)
-      bestLongtextA = longtext.substring(0, i - suffixLength)
-      bestLongtextB = longtext.substring(i + prefixLength)
-      bestShorttextA = shorttext.substring(0, j - suffixLength)
-      bestShorttextB = shorttext.substring(j + prefixLength)
-    }
-  }
-  if (bestCommon.length * 2 >= longtext.length) {
-    return [
-      bestLongtextA || '',
-      bestLongtextB || '',
-      bestShorttextA || '',
-      bestShorttextB || '',
-      bestCommon || '',
-    ]
-  }
-
-  return null
-}
-
-/**
- * Does a substring of shorttext exist within longtext such that the substring
+ * Does a slice of shorttext exist within longtext such that the slice
  * is at least half the length of longtext?
@@ -60,3 +13,3 @@ *
  * @param shorttext - Shorter string.
- * @param i - Start index of quarter length substring within longtext.
+ * @param i - Start index of quarter length slice within longtext.
  * @returns Five element Array, containing the prefix of
@@ -73,5 +26,5 @@ *     longtext, the suffix of longtext, the prefix of shorttext, the suffix
 
-  const longtext = text1.length > text2.length ? text1 : text2
-  const shorttext = text1.length > text2.length ? text2 : text1
-  if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {
+  const longText = text1.length > text2.length ? text1 : text2
+  const shortText = text1.length > text2.length ? text2 : text1
+  if (longText.length < 4 || shortText.length * 2 < longText.length) {
     return null // Pointless.
@@ -81,18 +34,22 @@ }
   // First check if the second quarter is the seed for a half-match.
-  const hm1 = halfMatchI(longtext, shorttext, Math.ceil(longtext.length / 4))
+  const halfMatch1 = halfMatchI(longText, shortText, Math.ceil(longText.length / 4))
   // Check again based on the third quarter.
-  const hm2 = halfMatchI(longtext, shorttext, Math.ceil(longtext.length / 2))
+  const halfMatch2 = halfMatchI(longText, shortText, Math.ceil(longText.length / 2))
 
-  let hm
-  if (hm1 && hm2) {
+  let halfMatch
+  if (halfMatch1 && halfMatch2) {
     // Both matched.  Select the longest.
-    hm = hm1[4].length > hm2[4].length ? hm1 : hm2
-  } else if (!hm1 && !hm2) {
+    halfMatch = halfMatch1[4].length > halfMatch2[4].length ? halfMatch1 : halfMatch2
+  } else if (!halfMatch1 && !halfMatch2) {
     return null
-  } else if (!hm2) {
-    hm = hm1
-  } else if (!hm1) {
-    hm = hm2
+  } else if (!halfMatch2) {
+    halfMatch = halfMatch1
+  } else if (!halfMatch1) {
+    halfMatch = halfMatch2
   }
 
+  if (!halfMatch) {
+    throw new Error('Unable to find a half match.')
+  }
+
   // A half-match was found, sort out the return data.
@@ -103,18 +60,62 @@ let text1A: string
   let text2B: string
-  if (hm) {
-    if (text1.length > text2.length) {
-      text1A = hm[0]
-      text1B = hm[1]
-      text2A = hm[2]
-      text2B = hm[3]
-    } else {
-      text2A = hm[0]
-      text2B = hm[1]
-      text1A = hm[2]
-      text1B = hm[3]
+
+  if (text1.length > text2.length) {
+    text1A = halfMatch[0]
+    text1B = halfMatch[1]
+    text2A = halfMatch[2]
+    text2B = halfMatch[3]
+  } else {
+    text2A = halfMatch[0]
+    text2B = halfMatch[1]
+    text1A = halfMatch[2]
+    text1B = halfMatch[3]
+  }
+  const midCommon = halfMatch[4]
+  return [text1A, text1B, text2A, text2B, midCommon]
+}
+
+/**
+ * Do the two texts share a slice which is at least half the length of the
+ * longer text?
+ * This speedup can produce non-minimal diffs.
+ *
+ * @param longText - First string.
+ * @param shortText - Second string.
+ * @returns Five element array, containing the prefix of longText,
+ *     the suffix of longText, the prefix of shortText, the suffix of
+ *     shortText and the common middle.  Or null if there was no match.
+ * @internal
+ */
+function halfMatchI(longText: string, shortText: string, i: number): null | HalfMatch {
+  // Start with a 1/4 length slice at position i as a seed.
+  const seed = longText.slice(i, i + Math.floor(longText.length / 4))
+  let j = -1
+  let bestCommon = ''
+  let bestLongTextA
+  let bestLongTextB
+  let bestShortTextA
+  let bestShortTextB
+
+  while ((j = shortText.indexOf(seed, j + 1)) !== -1) {
+    const prefixLength = getCommonPrefix(longText.slice(i), shortText.slice(j))
+    const suffixLength = getCommonSuffix(longText.slice(0, i), shortText.slice(0, j))
+    if (bestCommon.length < suffixLength + prefixLength) {
+      bestCommon = shortText.slice(j - suffixLength, j) + shortText.slice(j, j + prefixLength)
+      bestLongTextA = longText.slice(0, i - suffixLength)
+      bestLongTextB = longText.slice(i + prefixLength)
+      bestShortTextA = shortText.slice(0, j - suffixLength)
+      bestShortTextB = shortText.slice(j + prefixLength)
     }
-    const midCommon = hm[4]
-    return [text1A, text1B, text2A, text2B, midCommon]
   }
-  throw new Error('nope')
+  if (bestCommon.length * 2 >= longText.length) {
+    return [
+      bestLongTextA || '',
+      bestLongTextB || '',
+      bestShortTextA || '',
+      bestShortTextB || '',
+      bestCommon || '',
+    ]
+  }
+
+  return null
 }

src/diff/linesToChars.ts

@@ -20,3 +20,3 @@ /**
 } {
-  const lineArray = [] // e.g. lineArray[4] === 'Hello\n'
+  const lineArray: string[] = [] // e.g. lineArray[4] === 'Hello\n'
   const lineHash: {[key: string]: number} = {} // e.g. lineHash['Hello\n'] === 4
@@ -51,3 +51,3 @@
       }
-      let line = text.substring(lineStart, lineEnd + 1)
+      let line = text.slice(lineStart, lineEnd + 1)
 
@@ -60,3 +60,3 @@ if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) : lineHash[line] !== undefined) {
           // String.fromCharCode(65536) == String.fromCharCode(0)
-          line = text.substring(lineStart)
+          line = text.slice(lineStart)
           lineEnd = text.length
@@ -63,0 +63,0 @@ }

src/diff/toDelta.ts

@@ -14,3 +14,3 @@ import {DIFF_DELETE, DIFF_EQUAL, DIFF_INSERT, type Diff} from './diff.js'
 export function toDelta(diffs: Diff[]): string {
-  const text = []
+  const text: string[] = []
   for (let x = 0; x < diffs.length; x++) {
@@ -17,0 +17,0 @@ const [diffType, diff] = diffs[x]

src/index.ts

@@ -24,2 +24,2 @@ // Diff
 // UCS-2 utils (beta)
-export {adjustIndiciesToUcs2} from './utils/utf8Indices.js'
+export {adjustIndiciesToUcs2, type AdjustmentOptions} from './utils/utf8Indices.js'

src/patch/apply.ts

@@ -32,2 +32,11 @@ /* eslint-disable max-depth */
   deleteThreshold: number
+
+  /**
+   * When converting indices between UTF-8 and UCS-2, certain scenarios can occur
+   * where we go beyond the target offset. This can happen in particular with
+   * surrogate pairs/high codepoints, when the base string we are applying the
+   * patch to does not fully match the one that was used to generate the patch.
+   * Defaults to `false`.
+   */
+  allowExceedingIndices: boolean
 }
@@ -50,2 +59,3 @@
  * @param text - Old text.
+ * @param opts - Optional settings for the patch application.
  * @returns Two element Array, containing the new text and an array of boolean values.
@@ -69,3 +79,5 @@ * @public
   // Note: adjustment also deep-copies patches so that no changes are made to the originals.
-  const parsed = adjustIndiciesToUcs2(patches, text)
+  const parsed = adjustIndiciesToUcs2(patches, text, {
+    allowExceedingIndices: opts.allowExceedingIndices,
+  })
 
@@ -84,3 +96,3 @@ const margin = opts.margin || DEFAULT_MARGIN
   let delta = 0
-  const results = []
+  const results: boolean[] = []
   for (let x = 0; x < parsed.length; x++) {
@@ -87,0 +99,0 @@ const expectedLoc = parsed[x].start2 + delta

src/patch/make.ts

@@ -96,3 +96,3 @@ import {cleanupSemantic, cleanupEfficiency} from '../diff/cleanup.js'
   }
-  const patches = []
+  const patches: Patch[] = []
 
@@ -99,0 +99,0 @@ let patch = createPatchObject(0, 0)

src/patch/parse.ts

@@ -83,3 +83,3 @@ import {DIFF_DELETE, DIFF_EQUAL, DIFF_INSERT} from '../diff/diff.js'
       try {
-        line = decodeURI(currentLine.substring(1))
+        line = decodeURI(currentLine.slice(1))
       } catch (ex) {
@@ -86,0 +86,0 @@ // Malformed URI sequence.

src/utils/utf8Indices.ts

@@ -25,2 +25,18 @@ import {cloneDiff} from '../diff/clone.js'
 /**
+ * Options for the index adjustment operations.
+ *
+ * @public
+ */
+export interface AdjustmentOptions {
+  /**
+   * When converting indices between UTF-8 and UCS-2, certain scenarios can occur
+   * where we go beyond the target offset. This can happen in particular with
+   * surrogate pairs/high codepoints, when the base string we are applying the
+   * patch to does not fully match the one that was used to generate the patch.
+   * Defaults to `false`.
+   */
+  allowExceedingIndices?: boolean
+}
+
+/**
  * Takes a `patches` array as produced by diff-match-patch and adjusts the
@@ -32,6 +48,11 @@ * `start1` and `start2` properties so that they refer to UCS-2 index instead
  * @param base - The base string to use for counting bytes
+ * @param options - Options for the adjustment of indices
  * @returns A new array of patches with adjusted indicies
  * @beta
  */
-export function adjustIndiciesToUcs2(patches: Patch[], base: string): Patch[] {
+export function adjustIndiciesToUcs2(
+  patches: Patch[],
+  base: string,
+  options: AdjustmentOptions = {}
+): Patch[] {
   let byteOffset = 0
@@ -59,3 +80,3 @@ let idx = 0 // index into the input.
 
-    if (byteOffset !== target) {
+    if (!options.allowExceedingIndices && byteOffset !== target) {
       throw new Error('Failed to determine byte offset')
@@ -62,0 +83,0 @@ }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

532727

increased by1.24%

Lines of code

6101

increased by1.06%

No dependency changes