aboutsummaryrefslogtreecommitdiff
path: root/node_modules/diff-sequences
diff options
context:
space:
mode:
Diffstat (limited to 'node_modules/diff-sequences')
-rw-r--r--node_modules/diff-sequences/LICENSE21
-rw-r--r--node_modules/diff-sequences/README.md404
-rw-r--r--node_modules/diff-sequences/build/index.d.ts18
-rw-r--r--node_modules/diff-sequences/build/index.js816
-rw-r--r--node_modules/diff-sequences/package.json42
-rw-r--r--node_modules/diff-sequences/perf/example.md48
-rw-r--r--node_modules/diff-sequences/perf/index.js170
7 files changed, 1519 insertions, 0 deletions
diff --git a/node_modules/diff-sequences/LICENSE b/node_modules/diff-sequences/LICENSE
new file mode 100644
index 0000000..b96dcb0
--- /dev/null
+++ b/node_modules/diff-sequences/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) Facebook, Inc. and its affiliates.
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/node_modules/diff-sequences/README.md b/node_modules/diff-sequences/README.md
new file mode 100644
index 0000000..42066c7
--- /dev/null
+++ b/node_modules/diff-sequences/README.md
@@ -0,0 +1,404 @@
+# diff-sequences
+
+Compare items in two sequences to find a **longest common subsequence**.
+
+The items not in common are the items to delete or insert in a **shortest edit script**.
+
+To maximize flexibility and minimize memory, you write **callback** functions as configuration:
+
+**Input** function `isCommon(aIndex, bIndex)` compares items at indexes in the sequences and returns a truthy/falsey value. This package might call your function more than once for some pairs of indexes.
+
+- Because your function encapsulates **comparison**, this package can compare items according to `===` operator, `Object.is` method, or other criterion.
+- Because your function encapsulates **sequences**, this package can find differences in arrays, strings, or other data.
+
+**Output** function `foundSubsequence(nCommon, aCommon, bCommon)` receives the number of adjacent items and starting indexes of each common subsequence. If sequences do not have common items, then this package does not call your function.
+
+If N is the sum of lengths of sequences and L is length of a longest common subsequence, then D = N – 2L is the number of **differences** in the corresponding shortest edit script.
+
+[_An O(ND) Difference Algorithm and Its Variations_](http://xmailserver.org/diff2.pdf) by Eugene W. Myers is fast when sequences have **few** differences.
+
+This package implements the **linear space** variation with optimizations so it is fast even when sequences have **many** differences.
+
+## Usage
+
+To add this package as a dependency of a project, do either of the following:
+
+- `npm install diff-sequences`
+- `yarn add diff-sequences`
+
+To use `diff` as the name of the default export from this package, do either of the following:
+
+- `var diff = require('diff-sequences').default; // CommonJS modules`
+- `import diff from 'diff-sequences'; // ECMAScript modules`
+
+Call `diff` with the **lengths** of sequences and your **callback** functions:
+
+```js
+const a = ['a', 'b', 'c', 'a', 'b', 'b', 'a'];
+const b = ['c', 'b', 'a', 'b', 'a', 'c'];
+
+function isCommon(aIndex, bIndex) {
+ return a[aIndex] === b[bIndex];
+}
+function foundSubsequence(nCommon, aCommon, bCommon) {
+ // see examples
+}
+
+diff(a.length, b.length, isCommon, foundSubsequence);
+```
+
+## Example of longest common subsequence
+
+Some sequences (for example, `a` and `b` in the example of usage) have more than one longest common subsequence.
+
+This package finds the following common items:
+
+| comparisons of common items | values | output arguments |
+| :------------------------------- | :--------- | --------------------------: |
+| `a[2] === b[0]` | `'c'` | `foundSubsequence(1, 2, 0)` |
+| `a[4] === b[1]` | `'b'` | `foundSubsequence(1, 4, 1)` |
+| `a[5] === b[3] && a[6] === b[4]` | `'b', 'a'` | `foundSubsequence(2, 5, 3)` |
+
+The “edit graph” analogy in the Myers paper shows the following common items:
+
+| comparisons of common items | values |
+| :------------------------------- | :--------- |
+| `a[2] === b[0]` | `'c'` |
+| `a[3] === b[2] && a[4] === b[3]` | `'a', 'b'` |
+| `a[6] === b[4]` | `'a'` |
+
+Various packages which implement the Myers algorithm will **always agree** on the **length** of a longest common subsequence, but might **sometimes disagree** on which **items** are in it.
+
+## Example of callback functions to count common items
+
+```js
+// Return length of longest common subsequence according to === operator.
+function countCommonItems(a, b) {
+ let n = 0;
+ function isCommon(aIndex, bIndex) {
+ return a[aIndex] === b[bIndex];
+ }
+ function foundSubsequence(nCommon) {
+ n += nCommon;
+ }
+
+ diff(a.length, b.length, isCommon, foundSubsequence);
+
+ return n;
+}
+
+const commonLength = countCommonItems(
+ ['a', 'b', 'c', 'a', 'b', 'b', 'a'],
+ ['c', 'b', 'a', 'b', 'a', 'c'],
+);
+```
+
+| category of items | expression | value |
+| :----------------- | ------------------------: | ----: |
+| in common | `commonLength` | `4` |
+| to delete from `a` | `a.length - commonLength` | `3` |
+| to insert from `b` | `b.length - commonLength` | `2` |
+
+If the length difference `b.length - a.length` is:
+
+- negative: its absolute value is the minimum number of items to **delete** from `a`
+- positive: it is the minimum number of items to **insert** from `b`
+- zero: there is an **equal** number of items to delete from `a` and insert from `b`
+- non-zero: there is an equal number of **additional** items to delete from `a` and insert from `b`
+
+In this example, `6 - 7` is:
+
+- negative: `1` is the minimum number of items to **delete** from `a`
+- non-zero: `2` is the number of **additional** items to delete from `a` and insert from `b`
+
+## Example of callback functions to find common items
+
+```js
+// Return array of items in longest common subsequence according to Object.is method.
+const findCommonItems = (a, b) => {
+ const array = [];
+ diff(
+ a.length,
+ b.length,
+ (aIndex, bIndex) => Object.is(a[aIndex], b[bIndex]),
+ (nCommon, aCommon) => {
+ for (; nCommon !== 0; nCommon -= 1, aCommon += 1) {
+ array.push(a[aCommon]);
+ }
+ },
+ );
+ return array;
+};
+
+const commonItems = findCommonItems(
+ ['a', 'b', 'c', 'a', 'b', 'b', 'a'],
+ ['c', 'b', 'a', 'b', 'a', 'c'],
+);
+```
+
+| `i` | `commonItems[i]` | `aIndex` |
+| --: | :--------------- | -------: |
+| `0` | `'c'` | `2` |
+| `1` | `'b'` | `4` |
+| `2` | `'b'` | `5` |
+| `3` | `'a'` | `6` |
+
+## Example of callback functions to diff index intervals
+
+Instead of slicing array-like objects, you can adjust indexes in your callback functions.
+
+```js
+// Diff index intervals that are half open [start, end) like array slice method.
+const diffIndexIntervals = (a, aStart, aEnd, b, bStart, bEnd) => {
+ // Validate: 0 <= aStart and aStart <= aEnd and aEnd <= a.length
+ // Validate: 0 <= bStart and bStart <= bEnd and bEnd <= b.length
+
+ diff(
+ aEnd - aStart,
+ bEnd - bStart,
+ (aIndex, bIndex) => Object.is(a[aStart + aIndex], b[bStart + bIndex]),
+ (nCommon, aCommon, bCommon) => {
+ // aStart + aCommon, bStart + bCommon
+ },
+ );
+
+ // After the last common subsequence, do any remaining work.
+};
+```
+
+## Example of callback functions to emulate diff command
+
+Linux or Unix has a `diff` command to compare files line by line. Its output is a **shortest edit script**:
+
+- **c**hange adjacent lines from the first file to lines from the second file
+- **d**elete lines from the first file
+- **a**ppend or insert lines from the second file
+
+```js
+// Given zero-based half-open range [start, end) of array indexes,
+// return one-based closed range [start + 1, end] as string.
+const getRange = (start, end) =>
+ start + 1 === end ? `${start + 1}` : `${start + 1},${end}`;
+
+// Given index intervals of lines to delete or insert, or both, or neither,
+// push formatted diff lines onto array.
+const pushDelIns = (aLines, aIndex, aEnd, bLines, bIndex, bEnd, array) => {
+ const deleteLines = aIndex !== aEnd;
+ const insertLines = bIndex !== bEnd;
+ const changeLines = deleteLines && insertLines;
+ if (changeLines) {
+ array.push(getRange(aIndex, aEnd) + 'c' + getRange(bIndex, bEnd));
+ } else if (deleteLines) {
+ array.push(getRange(aIndex, aEnd) + 'd' + String(bIndex));
+ } else if (insertLines) {
+ array.push(String(aIndex) + 'a' + getRange(bIndex, bEnd));
+ } else {
+ return;
+ }
+
+ for (; aIndex !== aEnd; aIndex += 1) {
+ array.push('< ' + aLines[aIndex]); // delete is less than
+ }
+
+ if (changeLines) {
+ array.push('---');
+ }
+
+ for (; bIndex !== bEnd; bIndex += 1) {
+ array.push('> ' + bLines[bIndex]); // insert is greater than
+ }
+};
+
+// Given content of two files, return emulated output of diff utility.
+const findShortestEditScript = (a, b) => {
+ const aLines = a.split('\n');
+ const bLines = b.split('\n');
+ const aLength = aLines.length;
+ const bLength = bLines.length;
+
+ const isCommon = (aIndex, bIndex) => aLines[aIndex] === bLines[bIndex];
+
+ let aIndex = 0;
+ let bIndex = 0;
+ const array = [];
+ const foundSubsequence = (nCommon, aCommon, bCommon) => {
+ pushDelIns(aLines, aIndex, aCommon, bLines, bIndex, bCommon, array);
+ aIndex = aCommon + nCommon; // number of lines compared in a
+ bIndex = bCommon + nCommon; // number of lines compared in b
+ };
+
+ diff(aLength, bLength, isCommon, foundSubsequence);
+
+ // After the last common subsequence, push remaining change lines.
+ pushDelIns(aLines, aIndex, aLength, bLines, bIndex, bLength, array);
+
+ return array.length === 0 ? '' : array.join('\n') + '\n';
+};
+```
+
+## Example of callback functions to format diff lines
+
+Here is simplified code to format **changed and unchanged lines** in expected and received values after a test fails in Jest:
+
+```js
+// Format diff with minus or plus for change lines and space for common lines.
+const formatDiffLines = (a, b) => {
+ // Jest depends on pretty-format package to serialize objects as strings.
+ // Unindented for comparison to avoid distracting differences:
+ const aLinesUn = format(a, {indent: 0 /*, other options*/}).split('\n');
+ const bLinesUn = format(b, {indent: 0 /*, other options*/}).split('\n');
+ // Indented to display changed and unchanged lines:
+ const aLinesIn = format(a, {indent: 2 /*, other options*/}).split('\n');
+ const bLinesIn = format(b, {indent: 2 /*, other options*/}).split('\n');
+
+ const aLength = aLinesIn.length; // Validate: aLinesUn.length === aLength
+ const bLength = bLinesIn.length; // Validate: bLinesUn.length === bLength
+
+ const isCommon = (aIndex, bIndex) => aLinesUn[aIndex] === bLinesUn[bIndex];
+
+ // Only because the GitHub Flavored Markdown doc collapses adjacent spaces,
+ // this example code and the following table represent spaces as middle dots.
+ let aIndex = 0;
+ let bIndex = 0;
+ const array = [];
+ const foundSubsequence = (nCommon, aCommon, bCommon) => {
+ for (; aIndex !== aCommon; aIndex += 1) {
+ array.push('-·' + aLinesIn[aIndex]); // delete is minus
+ }
+ for (; bIndex !== bCommon; bIndex += 1) {
+ array.push('+·' + bLinesIn[bIndex]); // insert is plus
+ }
+ for (; nCommon !== 0; nCommon -= 1, aIndex += 1, bIndex += 1) {
+ // For common lines, received indentation seems more intuitive.
+ array.push('··' + bLinesIn[bIndex]); // common is space
+ }
+ };
+
+ diff(aLength, bLength, isCommon, foundSubsequence);
+
+ // After the last common subsequence, push remaining change lines.
+ for (; aIndex !== aLength; aIndex += 1) {
+ array.push('-·' + aLinesIn[aIndex]);
+ }
+ for (; bIndex !== bLength; bIndex += 1) {
+ array.push('+·' + bLinesIn[bIndex]);
+ }
+
+ return array;
+};
+
+const expected = {
+ searching: '',
+ sorting: {
+ ascending: true,
+ fieldKey: 'what',
+ },
+};
+const received = {
+ searching: '',
+ sorting: [
+ {
+ descending: false,
+ fieldKey: 'what',
+ },
+ ],
+};
+
+const diffLines = formatDiffLines(expected, received);
+```
+
+If N is the sum of lengths of sequences and L is length of a longest common subsequence, then N – L is length of an array of diff lines. In this example, N is 7 + 9, L is 5, and N – L is 11.
+
+| `i` | `diffLines[i]` | `aIndex` | `bIndex` |
+| ---: | :--------------------------------- | -------: | -------: |
+| `0` | `'··Object {'` | `0` | `0` |
+| `1` | `'····"searching": "",'` | `1` | `1` |
+| `2` | `'-···"sorting": Object {'` | `2` | |
+| `3` | `'-·····"ascending": true,'` | `3` | |
+| `4` | `'+·····"sorting": Array ['` | | `2` |
+| `5` | `'+·······Object {'` | | `3` |
+| `6` | `'+·········"descending": false,'` | | `4` |
+| `7` | `'··········"fieldKey": "what",'` | `4` | `5` |
+| `8` | `'········},'` | `5` | `6` |
+| `9` | `'+·····],'` | | `7` |
+| `10` | `'··}'` | `6` | `8` |
+
+## Example of callback functions to find diff items
+
+Here is simplified code to find changed and unchanged substrings **within adjacent changed lines** in expected and received values after a test fails in Jest:
+
+```js
+// Return diff items for strings (compatible with diff-match-patch package).
+const findDiffItems = (a, b) => {
+ const isCommon = (aIndex, bIndex) => a[aIndex] === b[bIndex];
+
+ let aIndex = 0;
+ let bIndex = 0;
+ const array = [];
+ const foundSubsequence = (nCommon, aCommon, bCommon) => {
+ if (aIndex !== aCommon) {
+ array.push([-1, a.slice(aIndex, aCommon)]); // delete is -1
+ }
+ if (bIndex !== bCommon) {
+ array.push([1, b.slice(bIndex, bCommon)]); // insert is 1
+ }
+
+ aIndex = aCommon + nCommon; // number of characters compared in a
+ bIndex = bCommon + nCommon; // number of characters compared in b
+ array.push([0, a.slice(aCommon, aIndex)]); // common is 0
+ };
+
+ diff(a.length, b.length, isCommon, foundSubsequence);
+
+ // After the last common subsequence, push remaining change items.
+ if (aIndex !== a.length) {
+ array.push([-1, a.slice(aIndex)]);
+ }
+ if (bIndex !== b.length) {
+ array.push([1, b.slice(bIndex)]);
+ }
+
+ return array;
+};
+
+const expectedDeleted = ['"sorting": Object {', '"ascending": true,'].join(
+ '\n',
+);
+const receivedInserted = [
+ '"sorting": Array [',
+ 'Object {',
+ '"descending": false,',
+].join('\n');
+
+const diffItems = findDiffItems(expectedDeleted, receivedInserted);
+```
+
+| `i` | `diffItems[i][0]` | `diffItems[i][1]` |
+| --: | ----------------: | :---------------- |
+| `0` | `0` | `'"sorting": '` |
+| `1` | `1` | `'Array [\n'` |
+| `2` | `0` | `'Object {\n"'` |
+| `3` | `-1` | `'a'` |
+| `4` | `1` | `'de'` |
+| `5` | `0` | `'scending": '` |
+| `6` | `-1` | `'tru'` |
+| `7` | `1` | `'fals'` |
+| `8` | `0` | `'e,'` |
+
+The length difference `b.length - a.length` is equal to the sum of `diffItems[i][0]` values times `diffItems[i][1]` lengths. In this example, the difference `48 - 38` is equal to the sum `10`.
+
+| category of diff item | `[0]` | `[1]` lengths | subtotal |
+| :-------------------- | ----: | -----------------: | -------: |
+| in common | `0` | `11 + 10 + 11 + 2` | `0` |
+| to delete from `a` | `–1` | `1 + 3` | `-4` |
+| to insert from `b` | `1` | `8 + 2 + 4` | `14` |
+
+Instead of formatting the changed substrings with escape codes for colors in the `foundSubsequence` function to save memory, this example spends memory to **gain flexibility** before formatting, so a separate heuristic algorithm might modify the generic array of diff items to show changes more clearly:
+
+| `i` | `diffItems[i][0]` | `diffItems[i][1]` |
+| --: | ----------------: | :---------------- |
+| `6` | `-1` | `'true'` |
+| `7` | `1` | `'false'` |
+| `8` | `0` | `','` |
+
+For expected and received strings of serialized data, the result of finding changed **lines**, and then finding changed **substrings** within adjacent changed lines (as in the preceding two examples) sometimes displays the changes in a more intuitive way than the result of finding changed substrings, and then splitting them into changed and unchanged lines.
diff --git a/node_modules/diff-sequences/build/index.d.ts b/node_modules/diff-sequences/build/index.d.ts
new file mode 100644
index 0000000..29d1946
--- /dev/null
+++ b/node_modules/diff-sequences/build/index.d.ts
@@ -0,0 +1,18 @@
+/**
+ * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
+ *
+ * This source code is licensed under the MIT license found in the
+ * LICENSE file in the root directory of this source tree.
+ *
+ */
+declare type IsCommon = (aIndex: number, // caller can assume: 0 <= aIndex && aIndex < aLength
+bIndex: number) => boolean;
+declare type FoundSubsequence = (nCommon: number, // caller can assume: 0 < nCommon
+aCommon: number, // caller can assume: 0 <= aCommon && aCommon < aLength
+bCommon: number) => void;
+export declare type Callbacks = {
+ foundSubsequence: FoundSubsequence;
+ isCommon: IsCommon;
+};
+export default function diffSequence(aLength: number, bLength: number, isCommon: IsCommon, foundSubsequence: FoundSubsequence): void;
+export {};
diff --git a/node_modules/diff-sequences/build/index.js b/node_modules/diff-sequences/build/index.js
new file mode 100644
index 0000000..7ac6339
--- /dev/null
+++ b/node_modules/diff-sequences/build/index.js
@@ -0,0 +1,816 @@
+'use strict';
+
+Object.defineProperty(exports, '__esModule', {
+ value: true
+});
+exports.default = diffSequence;
+
+/**
+ * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
+ *
+ * This source code is licensed under the MIT license found in the
+ * LICENSE file in the root directory of this source tree.
+ *
+ */
+// This diff-sequences package implements the linear space variation in
+// An O(ND) Difference Algorithm and Its Variations by Eugene W. Myers
+// Relationship in notation between Myers paper and this package:
+// A is a
+// N is aLength, aEnd - aStart, and so on
+// x is aIndex, aFirst, aLast, and so on
+// B is b
+// M is bLength, bEnd - bStart, and so on
+// y is bIndex, bFirst, bLast, and so on
+// Δ = N - M is negative of baDeltaLength = bLength - aLength
+// D is d
+// k is kF
+// k + Δ is kF = kR - baDeltaLength
+// V is aIndexesF or aIndexesR (see comment below about Indexes type)
+// index intervals [1, N] and [1, M] are [0, aLength) and [0, bLength)
+// starting point in forward direction (0, 0) is (-1, -1)
+// starting point in reverse direction (N + 1, M + 1) is (aLength, bLength)
+// The “edit graph” for sequences a and b corresponds to items:
+// in a on the horizontal axis
+// in b on the vertical axis
+//
+// Given a-coordinate of a point in a diagonal, you can compute b-coordinate.
+//
+// Forward diagonals kF:
+// zero diagonal intersects top left corner
+// positive diagonals intersect top edge
+// negative diagonals insersect left edge
+//
+// Reverse diagonals kR:
+// zero diagonal intersects bottom right corner
+// positive diagonals intersect right edge
+// negative diagonals intersect bottom edge
+// The graph contains a directed acyclic graph of edges:
+// horizontal: delete an item from a
+// vertical: insert an item from b
+// diagonal: common item in a and b
+//
+// The algorithm solves dual problems in the graph analogy:
+// Find longest common subsequence: path with maximum number of diagonal edges
+// Find shortest edit script: path with minimum number of non-diagonal edges
+// Input callback function compares items at indexes in the sequences.
+// Output callback function receives the number of adjacent items
+// and starting indexes of each common subsequence.
+// Either original functions or wrapped to swap indexes if graph is transposed.
+// Indexes in sequence a of last point of forward or reverse paths in graph.
+// Myers algorithm indexes by diagonal k which for negative is bad deopt in V8.
+// This package indexes by iF and iR which are greater than or equal to zero.
+// and also updates the index arrays in place to cut memory in half.
+// kF = 2 * iF - d
+// kR = d - 2 * iR
+// Division of index intervals in sequences a and b at the middle change.
+// Invariant: intervals do not have common items at the start or end.
+const pkg = 'diff-sequences'; // for error messages
+
+const NOT_YET_SET = 0; // small int instead of undefined to avoid deopt in V8
+// Return the number of common items that follow in forward direction.
+// The length of what Myers paper calls a “snake” in a forward path.
+
+const countCommonItemsF = (aIndex, aEnd, bIndex, bEnd, isCommon) => {
+ let nCommon = 0;
+
+ while (aIndex < aEnd && bIndex < bEnd && isCommon(aIndex, bIndex)) {
+ aIndex += 1;
+ bIndex += 1;
+ nCommon += 1;
+ }
+
+ return nCommon;
+}; // Return the number of common items that precede in reverse direction.
+// The length of what Myers paper calls a “snake” in a reverse path.
+
+const countCommonItemsR = (aStart, aIndex, bStart, bIndex, isCommon) => {
+ let nCommon = 0;
+
+ while (aStart <= aIndex && bStart <= bIndex && isCommon(aIndex, bIndex)) {
+ aIndex -= 1;
+ bIndex -= 1;
+ nCommon += 1;
+ }
+
+ return nCommon;
+}; // A simple function to extend forward paths from (d - 1) to d changes
+// when forward and reverse paths cannot yet overlap.
+
+const extendPathsF = (
+ d,
+ aEnd,
+ bEnd,
+ bF,
+ isCommon,
+ aIndexesF,
+ iMaxF // return the value because optimization might decrease it
+) => {
+ // Unroll the first iteration.
+ let iF = 0;
+ let kF = -d; // kF = 2 * iF - d
+
+ let aFirst = aIndexesF[iF]; // in first iteration always insert
+
+ let aIndexPrev1 = aFirst; // prev value of [iF - 1] in next iteration
+
+ aIndexesF[iF] += countCommonItemsF(
+ aFirst + 1,
+ aEnd,
+ bF + aFirst - kF + 1,
+ bEnd,
+ isCommon
+ ); // Optimization: skip diagonals in which paths cannot ever overlap.
+
+ const nF = d < iMaxF ? d : iMaxF; // The diagonals kF are odd when d is odd and even when d is even.
+
+ for (iF += 1, kF += 2; iF <= nF; iF += 1, kF += 2) {
+ // To get first point of path segment, move one change in forward direction
+ // from last point of previous path segment in an adjacent diagonal.
+ // In last possible iteration when iF === d and kF === d always delete.
+ if (iF !== d && aIndexPrev1 < aIndexesF[iF]) {
+ aFirst = aIndexesF[iF]; // vertical to insert from b
+ } else {
+ aFirst = aIndexPrev1 + 1; // horizontal to delete from a
+
+ if (aEnd <= aFirst) {
+ // Optimization: delete moved past right of graph.
+ return iF - 1;
+ }
+ } // To get last point of path segment, move along diagonal of common items.
+
+ aIndexPrev1 = aIndexesF[iF];
+ aIndexesF[iF] =
+ aFirst +
+ countCommonItemsF(aFirst + 1, aEnd, bF + aFirst - kF + 1, bEnd, isCommon);
+ }
+
+ return iMaxF;
+}; // A simple function to extend reverse paths from (d - 1) to d changes
+// when reverse and forward paths cannot yet overlap.
+
+const extendPathsR = (
+ d,
+ aStart,
+ bStart,
+ bR,
+ isCommon,
+ aIndexesR,
+ iMaxR // return the value because optimization might decrease it
+) => {
+ // Unroll the first iteration.
+ let iR = 0;
+ let kR = d; // kR = d - 2 * iR
+
+ let aFirst = aIndexesR[iR]; // in first iteration always insert
+
+ let aIndexPrev1 = aFirst; // prev value of [iR - 1] in next iteration
+
+ aIndexesR[iR] -= countCommonItemsR(
+ aStart,
+ aFirst - 1,
+ bStart,
+ bR + aFirst - kR - 1,
+ isCommon
+ ); // Optimization: skip diagonals in which paths cannot ever overlap.
+
+ const nR = d < iMaxR ? d : iMaxR; // The diagonals kR are odd when d is odd and even when d is even.
+
+ for (iR += 1, kR -= 2; iR <= nR; iR += 1, kR -= 2) {
+ // To get first point of path segment, move one change in reverse direction
+ // from last point of previous path segment in an adjacent diagonal.
+ // In last possible iteration when iR === d and kR === -d always delete.
+ if (iR !== d && aIndexesR[iR] < aIndexPrev1) {
+ aFirst = aIndexesR[iR]; // vertical to insert from b
+ } else {
+ aFirst = aIndexPrev1 - 1; // horizontal to delete from a
+
+ if (aFirst < aStart) {
+ // Optimization: delete moved past left of graph.
+ return iR - 1;
+ }
+ } // To get last point of path segment, move along diagonal of common items.
+
+ aIndexPrev1 = aIndexesR[iR];
+ aIndexesR[iR] =
+ aFirst -
+ countCommonItemsR(
+ aStart,
+ aFirst - 1,
+ bStart,
+ bR + aFirst - kR - 1,
+ isCommon
+ );
+ }
+
+ return iMaxR;
+}; // A complete function to extend forward paths from (d - 1) to d changes.
+// Return true if a path overlaps reverse path of (d - 1) changes in its diagonal.
+
+const extendOverlappablePathsF = (
+ d,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ isCommon,
+ aIndexesF,
+ iMaxF,
+ aIndexesR,
+ iMaxR,
+ division // update prop values if return true
+) => {
+ const bF = bStart - aStart; // bIndex = bF + aIndex - kF
+
+ const aLength = aEnd - aStart;
+ const bLength = bEnd - bStart;
+ const baDeltaLength = bLength - aLength; // kF = kR - baDeltaLength
+ // Range of diagonals in which forward and reverse paths might overlap.
+
+ const kMinOverlapF = -baDeltaLength - (d - 1); // -(d - 1) <= kR
+
+ const kMaxOverlapF = -baDeltaLength + (d - 1); // kR <= (d - 1)
+
+ let aIndexPrev1 = NOT_YET_SET; // prev value of [iF - 1] in next iteration
+ // Optimization: skip diagonals in which paths cannot ever overlap.
+
+ const nF = d < iMaxF ? d : iMaxF; // The diagonals kF = 2 * iF - d are odd when d is odd and even when d is even.
+
+ for (let iF = 0, kF = -d; iF <= nF; iF += 1, kF += 2) {
+ // To get first point of path segment, move one change in forward direction
+ // from last point of previous path segment in an adjacent diagonal.
+ // In first iteration when iF === 0 and kF === -d always insert.
+ // In last possible iteration when iF === d and kF === d always delete.
+ const insert = iF === 0 || (iF !== d && aIndexPrev1 < aIndexesF[iF]);
+ const aLastPrev = insert ? aIndexesF[iF] : aIndexPrev1;
+ const aFirst = insert
+ ? aLastPrev // vertical to insert from b
+ : aLastPrev + 1; // horizontal to delete from a
+ // To get last point of path segment, move along diagonal of common items.
+
+ const bFirst = bF + aFirst - kF;
+ const nCommonF = countCommonItemsF(
+ aFirst + 1,
+ aEnd,
+ bFirst + 1,
+ bEnd,
+ isCommon
+ );
+ const aLast = aFirst + nCommonF;
+ aIndexPrev1 = aIndexesF[iF];
+ aIndexesF[iF] = aLast;
+
+ if (kMinOverlapF <= kF && kF <= kMaxOverlapF) {
+ // Solve for iR of reverse path with (d - 1) changes in diagonal kF:
+ // kR = kF + baDeltaLength
+ // kR = (d - 1) - 2 * iR
+ const iR = (d - 1 - (kF + baDeltaLength)) / 2; // If this forward path overlaps the reverse path in this diagonal,
+ // then this is the middle change of the index intervals.
+
+ if (iR <= iMaxR && aIndexesR[iR] - 1 <= aLast) {
+ // Unlike the Myers algorithm which finds only the middle “snake”
+ // this package can find two common subsequences per division.
+ // Last point of previous path segment is on an adjacent diagonal.
+ const bLastPrev = bF + aLastPrev - (insert ? kF + 1 : kF - 1); // Because of invariant that intervals preceding the middle change
+ // cannot have common items at the end,
+ // move in reverse direction along a diagonal of common items.
+
+ const nCommonR = countCommonItemsR(
+ aStart,
+ aLastPrev,
+ bStart,
+ bLastPrev,
+ isCommon
+ );
+ const aIndexPrevFirst = aLastPrev - nCommonR;
+ const bIndexPrevFirst = bLastPrev - nCommonR;
+ const aEndPreceding = aIndexPrevFirst + 1;
+ const bEndPreceding = bIndexPrevFirst + 1;
+ division.nChangePreceding = d - 1;
+
+ if (d - 1 === aEndPreceding + bEndPreceding - aStart - bStart) {
+ // Optimization: number of preceding changes in forward direction
+ // is equal to number of items in preceding interval,
+ // therefore it cannot contain any common items.
+ division.aEndPreceding = aStart;
+ division.bEndPreceding = bStart;
+ } else {
+ division.aEndPreceding = aEndPreceding;
+ division.bEndPreceding = bEndPreceding;
+ }
+
+ division.nCommonPreceding = nCommonR;
+
+ if (nCommonR !== 0) {
+ division.aCommonPreceding = aEndPreceding;
+ division.bCommonPreceding = bEndPreceding;
+ }
+
+ division.nCommonFollowing = nCommonF;
+
+ if (nCommonF !== 0) {
+ division.aCommonFollowing = aFirst + 1;
+ division.bCommonFollowing = bFirst + 1;
+ }
+
+ const aStartFollowing = aLast + 1;
+ const bStartFollowing = bFirst + nCommonF + 1;
+ division.nChangeFollowing = d - 1;
+
+ if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
+ // Optimization: number of changes in reverse direction
+ // is equal to number of items in following interval,
+ // therefore it cannot contain any common items.
+ division.aStartFollowing = aEnd;
+ division.bStartFollowing = bEnd;
+ } else {
+ division.aStartFollowing = aStartFollowing;
+ division.bStartFollowing = bStartFollowing;
+ }
+
+ return true;
+ }
+ }
+ }
+
+ return false;
+}; // A complete function to extend reverse paths from (d - 1) to d changes.
+// Return true if a path overlaps forward path of d changes in its diagonal.
+
+const extendOverlappablePathsR = (
+ d,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ isCommon,
+ aIndexesF,
+ iMaxF,
+ aIndexesR,
+ iMaxR,
+ division // update prop values if return true
+) => {
+ const bR = bEnd - aEnd; // bIndex = bR + aIndex - kR
+
+ const aLength = aEnd - aStart;
+ const bLength = bEnd - bStart;
+ const baDeltaLength = bLength - aLength; // kR = kF + baDeltaLength
+ // Range of diagonals in which forward and reverse paths might overlap.
+
+ const kMinOverlapR = baDeltaLength - d; // -d <= kF
+
+ const kMaxOverlapR = baDeltaLength + d; // kF <= d
+
+ let aIndexPrev1 = NOT_YET_SET; // prev value of [iR - 1] in next iteration
+ // Optimization: skip diagonals in which paths cannot ever overlap.
+
+ const nR = d < iMaxR ? d : iMaxR; // The diagonals kR = d - 2 * iR are odd when d is odd and even when d is even.
+
+ for (let iR = 0, kR = d; iR <= nR; iR += 1, kR -= 2) {
+ // To get first point of path segment, move one change in reverse direction
+ // from last point of previous path segment in an adjacent diagonal.
+ // In first iteration when iR === 0 and kR === d always insert.
+ // In last possible iteration when iR === d and kR === -d always delete.
+ const insert = iR === 0 || (iR !== d && aIndexesR[iR] < aIndexPrev1);
+ const aLastPrev = insert ? aIndexesR[iR] : aIndexPrev1;
+ const aFirst = insert
+ ? aLastPrev // vertical to insert from b
+ : aLastPrev - 1; // horizontal to delete from a
+ // To get last point of path segment, move along diagonal of common items.
+
+ const bFirst = bR + aFirst - kR;
+ const nCommonR = countCommonItemsR(
+ aStart,
+ aFirst - 1,
+ bStart,
+ bFirst - 1,
+ isCommon
+ );
+ const aLast = aFirst - nCommonR;
+ aIndexPrev1 = aIndexesR[iR];
+ aIndexesR[iR] = aLast;
+
+ if (kMinOverlapR <= kR && kR <= kMaxOverlapR) {
+ // Solve for iF of forward path with d changes in diagonal kR:
+ // kF = kR - baDeltaLength
+ // kF = 2 * iF - d
+ const iF = (d + (kR - baDeltaLength)) / 2; // If this reverse path overlaps the forward path in this diagonal,
+ // then this is a middle change of the index intervals.
+
+ if (iF <= iMaxF && aLast - 1 <= aIndexesF[iF]) {
+ const bLast = bFirst - nCommonR;
+ division.nChangePreceding = d;
+
+ if (d === aLast + bLast - aStart - bStart) {
+ // Optimization: number of changes in reverse direction
+ // is equal to number of items in preceding interval,
+ // therefore it cannot contain any common items.
+ division.aEndPreceding = aStart;
+ division.bEndPreceding = bStart;
+ } else {
+ division.aEndPreceding = aLast;
+ division.bEndPreceding = bLast;
+ }
+
+ division.nCommonPreceding = nCommonR;
+
+ if (nCommonR !== 0) {
+ // The last point of reverse path segment is start of common subsequence.
+ division.aCommonPreceding = aLast;
+ division.bCommonPreceding = bLast;
+ }
+
+ division.nChangeFollowing = d - 1;
+
+ if (d === 1) {
+ // There is no previous path segment.
+ division.nCommonFollowing = 0;
+ division.aStartFollowing = aEnd;
+ division.bStartFollowing = bEnd;
+ } else {
+ // Unlike the Myers algorithm which finds only the middle “snake”
+ // this package can find two common subsequences per division.
+ // Last point of previous path segment is on an adjacent diagonal.
+ const bLastPrev = bR + aLastPrev - (insert ? kR - 1 : kR + 1); // Because of invariant that intervals following the middle change
+ // cannot have common items at the start,
+ // move in forward direction along a diagonal of common items.
+
+ const nCommonF = countCommonItemsF(
+ aLastPrev,
+ aEnd,
+ bLastPrev,
+ bEnd,
+ isCommon
+ );
+ division.nCommonFollowing = nCommonF;
+
+ if (nCommonF !== 0) {
+ // The last point of reverse path segment is start of common subsequence.
+ division.aCommonFollowing = aLastPrev;
+ division.bCommonFollowing = bLastPrev;
+ }
+
+ const aStartFollowing = aLastPrev + nCommonF; // aFirstPrev
+
+ const bStartFollowing = bLastPrev + nCommonF; // bFirstPrev
+
+ if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
+ // Optimization: number of changes in forward direction
+ // is equal to number of items in following interval,
+ // therefore it cannot contain any common items.
+ division.aStartFollowing = aEnd;
+ division.bStartFollowing = bEnd;
+ } else {
+ division.aStartFollowing = aStartFollowing;
+ division.bStartFollowing = bStartFollowing;
+ }
+ }
+
+ return true;
+ }
+ }
+ }
+
+ return false;
+}; // Given index intervals and input function to compare items at indexes,
+// divide at the middle change.
+//
+// DO NOT CALL if start === end, because interval cannot contain common items
+// and because this function will throw the “no overlap” error.
+
+const divide = (
+ nChange,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ isCommon,
+ aIndexesF,
+ aIndexesR,
+ division // output
+) => {
+ const bF = bStart - aStart; // bIndex = bF + aIndex - kF
+
+ const bR = bEnd - aEnd; // bIndex = bR + aIndex - kR
+
+ const aLength = aEnd - aStart;
+ const bLength = bEnd - bStart; // Because graph has square or portrait orientation,
+ // length difference is minimum number of items to insert from b.
+ // Corresponding forward and reverse diagonals in graph
+ // depend on length difference of the sequences:
+ // kF = kR - baDeltaLength
+ // kR = kF + baDeltaLength
+
+ const baDeltaLength = bLength - aLength; // Optimization: max diagonal in graph intersects corner of shorter side.
+
+ let iMaxF = aLength;
+ let iMaxR = aLength; // Initialize no changes yet in forward or reverse direction:
+
+ aIndexesF[0] = aStart - 1; // at open start of interval, outside closed start
+
+ aIndexesR[0] = aEnd; // at open end of interval
+
+ if (baDeltaLength % 2 === 0) {
+ // The number of changes in paths is 2 * d if length difference is even.
+ const dMin = (nChange || baDeltaLength) / 2;
+ const dMax = (aLength + bLength) / 2;
+
+ for (let d = 1; d <= dMax; d += 1) {
+ iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
+
+ if (d < dMin) {
+ iMaxR = extendPathsR(d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR);
+ } else if (
+ // If a reverse path overlaps a forward path in the same diagonal,
+ // return a division of the index intervals at the middle change.
+ extendOverlappablePathsR(
+ d,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ isCommon,
+ aIndexesF,
+ iMaxF,
+ aIndexesR,
+ iMaxR,
+ division
+ )
+ ) {
+ return;
+ }
+ }
+ } else {
+ // The number of changes in paths is 2 * d - 1 if length difference is odd.
+ const dMin = ((nChange || baDeltaLength) + 1) / 2;
+ const dMax = (aLength + bLength + 1) / 2; // Unroll first half iteration so loop extends the relevant pairs of paths.
+ // Because of invariant that intervals have no common items at start or end,
+ // and limitation not to call divide with empty intervals,
+ // therefore it cannot be called if a forward path with one change
+ // would overlap a reverse path with no changes, even if dMin === 1.
+
+ let d = 1;
+ iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
+
+ for (d += 1; d <= dMax; d += 1) {
+ iMaxR = extendPathsR(
+ d - 1,
+ aStart,
+ bStart,
+ bR,
+ isCommon,
+ aIndexesR,
+ iMaxR
+ );
+
+ if (d < dMin) {
+ iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
+ } else if (
+ // If a forward path overlaps a reverse path in the same diagonal,
+ // return a division of the index intervals at the middle change.
+ extendOverlappablePathsF(
+ d,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ isCommon,
+ aIndexesF,
+ iMaxF,
+ aIndexesR,
+ iMaxR,
+ division
+ )
+ ) {
+ return;
+ }
+ }
+ }
+ /* istanbul ignore next */
+
+ throw new Error(
+ `${pkg}: no overlap aStart=${aStart} aEnd=${aEnd} bStart=${bStart} bEnd=${bEnd}`
+ );
+}; // Given index intervals and input function to compare items at indexes,
+// return by output function the number of adjacent items and starting indexes
+// of each common subsequence. Divide and conquer with only linear space.
+//
+// The index intervals are half open [start, end) like array slice method.
+// DO NOT CALL if start === end, because interval cannot contain common items
+// and because divide function will throw the “no overlap” error.
+
+const findSubsequences = (
+ nChange,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ transposed,
+ callbacks,
+ aIndexesF,
+ aIndexesR,
+ division // temporary memory, not input nor output
+) => {
+ if (bEnd - bStart < aEnd - aStart) {
+ // Transpose graph so it has portrait instead of landscape orientation.
+ // Always compare shorter to longer sequence for consistency and optimization.
+ transposed = !transposed;
+
+ if (transposed && callbacks.length === 1) {
+ // Lazily wrap callback functions to swap args if graph is transposed.
+ const {foundSubsequence, isCommon} = callbacks[0];
+ callbacks[1] = {
+ foundSubsequence: (nCommon, bCommon, aCommon) => {
+ foundSubsequence(nCommon, aCommon, bCommon);
+ },
+ isCommon: (bIndex, aIndex) => isCommon(aIndex, bIndex)
+ };
+ }
+
+ const tStart = aStart;
+ const tEnd = aEnd;
+ aStart = bStart;
+ aEnd = bEnd;
+ bStart = tStart;
+ bEnd = tEnd;
+ }
+
+ const {foundSubsequence, isCommon} = callbacks[transposed ? 1 : 0]; // Divide the index intervals at the middle change.
+
+ divide(
+ nChange,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ isCommon,
+ aIndexesF,
+ aIndexesR,
+ division
+ );
+ const {
+ nChangePreceding,
+ aEndPreceding,
+ bEndPreceding,
+ nCommonPreceding,
+ aCommonPreceding,
+ bCommonPreceding,
+ nCommonFollowing,
+ aCommonFollowing,
+ bCommonFollowing,
+ nChangeFollowing,
+ aStartFollowing,
+ bStartFollowing
+ } = division; // Unless either index interval is empty, they might contain common items.
+
+ if (aStart < aEndPreceding && bStart < bEndPreceding) {
+ // Recursely find and return common subsequences preceding the division.
+ findSubsequences(
+ nChangePreceding,
+ aStart,
+ aEndPreceding,
+ bStart,
+ bEndPreceding,
+ transposed,
+ callbacks,
+ aIndexesF,
+ aIndexesR,
+ division
+ );
+ } // Return common subsequences that are adjacent to the middle change.
+
+ if (nCommonPreceding !== 0) {
+ foundSubsequence(nCommonPreceding, aCommonPreceding, bCommonPreceding);
+ }
+
+ if (nCommonFollowing !== 0) {
+ foundSubsequence(nCommonFollowing, aCommonFollowing, bCommonFollowing);
+ } // Unless either index interval is empty, they might contain common items.
+
+ if (aStartFollowing < aEnd && bStartFollowing < bEnd) {
+ // Recursely find and return common subsequences following the division.
+ findSubsequences(
+ nChangeFollowing,
+ aStartFollowing,
+ aEnd,
+ bStartFollowing,
+ bEnd,
+ transposed,
+ callbacks,
+ aIndexesF,
+ aIndexesR,
+ division
+ );
+ }
+};
+
+const validateLength = (name, arg) => {
+ if (typeof arg !== 'number') {
+ throw new TypeError(`${pkg}: ${name} typeof ${typeof arg} is not a number`);
+ }
+
+ if (!Number.isSafeInteger(arg)) {
+ throw new RangeError(`${pkg}: ${name} value ${arg} is not a safe integer`);
+ }
+
+ if (arg < 0) {
+ throw new RangeError(`${pkg}: ${name} value ${arg} is a negative integer`);
+ }
+};
+
+const validateCallback = (name, arg) => {
+ const type = typeof arg;
+
+ if (type !== 'function') {
+ throw new TypeError(`${pkg}: ${name} typeof ${type} is not a function`);
+ }
+}; // Compare items in two sequences to find a longest common subsequence.
+// Given lengths of sequences and input function to compare items at indexes,
+// return by output function the number of adjacent items and starting indexes
+// of each common subsequence.
+
+function diffSequence(aLength, bLength, isCommon, foundSubsequence) {
+ validateLength('aLength', aLength);
+ validateLength('bLength', bLength);
+ validateCallback('isCommon', isCommon);
+ validateCallback('foundSubsequence', foundSubsequence); // Count common items from the start in the forward direction.
+
+ const nCommonF = countCommonItemsF(0, aLength, 0, bLength, isCommon);
+
+ if (nCommonF !== 0) {
+ foundSubsequence(nCommonF, 0, 0);
+ } // Unless both sequences consist of common items only,
+ // find common items in the half-trimmed index intervals.
+
+ if (aLength !== nCommonF || bLength !== nCommonF) {
+ // Invariant: intervals do not have common items at the start.
+ // The start of an index interval is closed like array slice method.
+ const aStart = nCommonF;
+ const bStart = nCommonF; // Count common items from the end in the reverse direction.
+
+ const nCommonR = countCommonItemsR(
+ aStart,
+ aLength - 1,
+ bStart,
+ bLength - 1,
+ isCommon
+ ); // Invariant: intervals do not have common items at the end.
+ // The end of an index interval is open like array slice method.
+
+ const aEnd = aLength - nCommonR;
+ const bEnd = bLength - nCommonR; // Unless one sequence consists of common items only,
+ // therefore the other trimmed index interval consists of changes only,
+ // find common items in the trimmed index intervals.
+
+ const nCommonFR = nCommonF + nCommonR;
+
+ if (aLength !== nCommonFR && bLength !== nCommonFR) {
+ const nChange = 0; // number of change items is not yet known
+
+ const transposed = false; // call the original unwrapped functions
+
+ const callbacks = [
+ {
+ foundSubsequence,
+ isCommon
+ }
+ ]; // Indexes in sequence a of last points in furthest reaching paths
+ // from outside the start at top left in the forward direction:
+
+ const aIndexesF = [NOT_YET_SET]; // from the end at bottom right in the reverse direction:
+
+ const aIndexesR = [NOT_YET_SET]; // Initialize one object as output of all calls to divide function.
+
+ const division = {
+ aCommonFollowing: NOT_YET_SET,
+ aCommonPreceding: NOT_YET_SET,
+ aEndPreceding: NOT_YET_SET,
+ aStartFollowing: NOT_YET_SET,
+ bCommonFollowing: NOT_YET_SET,
+ bCommonPreceding: NOT_YET_SET,
+ bEndPreceding: NOT_YET_SET,
+ bStartFollowing: NOT_YET_SET,
+ nChangeFollowing: NOT_YET_SET,
+ nChangePreceding: NOT_YET_SET,
+ nCommonFollowing: NOT_YET_SET,
+ nCommonPreceding: NOT_YET_SET
+ }; // Find and return common subsequences in the trimmed index intervals.
+
+ findSubsequences(
+ nChange,
+ aStart,
+ aEnd,
+ bStart,
+ bEnd,
+ transposed,
+ callbacks,
+ aIndexesF,
+ aIndexesR,
+ division
+ );
+ }
+
+ if (nCommonR !== 0) {
+ foundSubsequence(nCommonR, aEnd, bEnd);
+ }
+ }
+}
diff --git a/node_modules/diff-sequences/package.json b/node_modules/diff-sequences/package.json
new file mode 100644
index 0000000..dc05cd2
--- /dev/null
+++ b/node_modules/diff-sequences/package.json
@@ -0,0 +1,42 @@
+{
+ "name": "diff-sequences",
+ "version": "27.5.1",
+ "repository": {
+ "type": "git",
+ "url": "https://github.com/facebook/jest.git",
+ "directory": "packages/diff-sequences"
+ },
+ "license": "MIT",
+ "description": "Compare items in two sequences to find a longest common subsequence",
+ "keywords": [
+ "fast",
+ "linear",
+ "space",
+ "callback",
+ "diff"
+ ],
+ "engines": {
+ "node": "^10.13.0 || ^12.13.0 || ^14.15.0 || >=15.0.0"
+ },
+ "main": "./build/index.js",
+ "types": "./build/index.d.ts",
+ "exports": {
+ ".": {
+ "types": "./build/index.d.ts",
+ "default": "./build/index.js"
+ },
+ "./package.json": "./package.json"
+ },
+ "scripts": {
+ "perf": "node --expose-gc perf/index.js"
+ },
+ "devDependencies": {
+ "benchmark": "^2.1.4",
+ "diff": "^5.0.0",
+ "fast-check": "^2.0.0"
+ },
+ "publishConfig": {
+ "access": "public"
+ },
+ "gitHead": "67c1aa20c5fec31366d733e901fee2b981cb1850"
+}
diff --git a/node_modules/diff-sequences/perf/example.md b/node_modules/diff-sequences/perf/example.md
new file mode 100644
index 0000000..663f25d
--- /dev/null
+++ b/node_modules/diff-sequences/perf/example.md
@@ -0,0 +1,48 @@
+## Benchmark time for `diff-sequences` versus `diff`
+
+A ratio less than 1.0 means `diff-sequences` is faster.
+
+### n = 20
+
+| name | % | ratio | improved | rme | baseline | rme |
+| :----- | ---: | :----- | :-------- | ----: | :-------- | ----: |
+| delete | 20% | 0.1824 | 3.0639e-6 | 1.11% | 1.6795e-5 | 0.78% |
+| insert | 20% | 0.1367 | 2.5786e-6 | 0.75% | 1.8866e-5 | 0.85% |
+| delete | 40% | 0.1015 | 3.0534e-6 | 1.00% | 3.0090e-5 | 0.70% |
+| insert | 40% | 0.0791 | 2.6722e-6 | 0.61% | 3.3791e-5 | 0.56% |
+| delete | 80% | 0.0410 | 2.8870e-6 | 0.93% | 7.0411e-5 | 0.72% |
+| insert | 80% | 0.0371 | 2.5786e-6 | 0.83% | 6.9431e-5 | 0.62% |
+| change | 10% | 0.1504 | 2.8703e-6 | 0.71% | 1.9087e-5 | 0.83% |
+| change | 20% | 0.1706 | 3.2637e-6 | 0.78% | 1.9127e-5 | 0.62% |
+| change | 50% | 0.0944 | 1.2012e-5 | 0.55% | 1.2724e-4 | 0.76% |
+| change | 100% | 0.0522 | 1.5422e-5 | 0.61% | 2.9566e-4 | 0.66% |
+
+### n = 200
+
+| name | % | ratio | improved | rme | baseline | rme |
+| :----- | ---: | :----- | :-------- | ----: | :-------- | ----: |
+| delete | 20% | 0.1524 | 7.2866e-5 | 0.75% | 4.7797e-4 | 0.80% |
+| insert | 20% | 0.1226 | 6.1561e-5 | 0.58% | 5.0198e-4 | 0.66% |
+| delete | 40% | 0.1118 | 1.5674e-4 | 0.67% | 1.4020e-3 | 0.58% |
+| insert | 40% | 0.0894 | 1.2906e-4 | 0.64% | 1.4435e-3 | 0.53% |
+| delete | 80% | 0.0796 | 3.0119e-4 | 0.58% | 3.7852e-3 | 0.52% |
+| insert | 80% | 0.0734 | 2.4713e-4 | 0.67% | 3.3653e-3 | 0.54% |
+| change | 10% | 0.1572 | 7.2965e-5 | 0.48% | 4.6426e-4 | 0.73% |
+| change | 20% | 0.1446 | 7.0056e-5 | 0.69% | 4.8456e-4 | 0.53% |
+| change | 50% | 0.0764 | 6.5638e-4 | 0.67% | 8.5946e-3 | 0.70% |
+| change | 100% | 0.0525 | 1.1160e-3 | 0.51% | 2.1249e-2 | 0.63% |
+
+### n = 2000
+
+| name | % | ratio | improved | rme | baseline | rme |
+| :----- | ---: | :----- | :-------- | ----: | :-------- | ----: |
+| delete | 20% | 0.0669 | 3.4073e-3 | 0.54% | 5.0922e-2 | 0.54% |
+| insert | 20% | 0.0588 | 2.8273e-3 | 0.51% | 4.8111e-2 | 0.46% |
+| delete | 40% | 0.0517 | 1.1048e-2 | 0.52% | 2.1367e-1 | 0.47% |
+| insert | 40% | 0.0460 | 9.1469e-3 | 0.37% | 1.9878e-1 | 0.26% |
+| delete | 80% | 0.0563 | 2.7426e-2 | 0.56% | 4.8674e-1 | 0.36% |
+| insert | 80% | 0.0506 | 2.2208e-2 | 0.35% | 4.3888e-1 | 0.47% |
+| change | 10% | 0.0716 | 3.1267e-3 | 1.21% | 4.3652e-2 | 0.56% |
+| change | 20% | 0.0621 | 3.0197e-3 | 0.72% | 4.8652e-2 | 0.45% |
+| change | 50% | 0.0083 | 5.4250e-2 | 0.62% | 6.5595e+0 | 3.60% |
+| change | 100% | 0.0493 | 1.0534e-1 | 0.71% | 2.1362e+0 | 0.21% |
diff --git a/node_modules/diff-sequences/perf/index.js b/node_modules/diff-sequences/perf/index.js
new file mode 100644
index 0000000..5673f9d
--- /dev/null
+++ b/node_modules/diff-sequences/perf/index.js
@@ -0,0 +1,170 @@
+/**
+ * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
+ *
+ * This source code is licensed under the MIT license found in the
+ * LICENSE file in the root directory of this source tree.
+ */
+
+// Make sure to run node with --expose-gc option!
+
+// The times are reliable if about 1% relative mean error if you run it:
+
+// * immediately after restart
+// * with 100% battery charge
+// * not connected to network
+
+/* eslint import/no-extraneous-dependencies: "off" */
+
+const Benchmark = require('benchmark');
+const diffBaseline = require('diff').diffLines;
+const diffImproved = require('../build/index.js').default;
+
+const testBaseline = (a, b) => {
+ const benchmark = new Benchmark({
+ fn() {
+ diffBaseline(a, b);
+ },
+ name: 'baseline',
+ onCycle() {
+ global.gc(); // after run cycle
+ },
+ onStart() {
+ global.gc(); // when benchmark starts
+ },
+ });
+
+ benchmark.run({async: false});
+
+ return benchmark.stats;
+};
+
+const testImproved = function (a, b) {
+ const benchmark = new Benchmark({
+ fn() {
+ // Split string arguments to make fair comparison with baseline.
+ const aItems = a.split('\n');
+ const bItems = b.split('\n');
+
+ const isCommon = (aIndex, bIndex) => aItems[aIndex] === bItems[bIndex];
+
+ // This callback obviously does less than baseline `diff` package,
+ // but avoiding double work and memory churn is the goal.
+ // For example, `jest-diff` has had to split strings that `diff` joins.
+ const foundSubsequence = () => {};
+
+ diffImproved(aItems.length, bItems.length, isCommon, foundSubsequence);
+ },
+ name: 'improved',
+ onCycle() {
+ global.gc(); // after run cycle
+ },
+ onStart() {
+ global.gc(); // when benchmark starts
+ },
+ });
+
+ benchmark.run({async: false});
+
+ return benchmark.stats;
+};
+
+const writeHeading2 = () => {
+ console.log('## Benchmark time for `diff-sequences` versus `diff`\n');
+ console.log('A ratio less than 1.0 means `diff-sequences` is faster.');
+};
+
+const writeHeading3 = n => {
+ console.log(`\n### n = ${n}\n`);
+ console.log('| name | % | ratio | improved | rme | baseline | rme |');
+ console.log('| :--- | ---: | :--- | :--- | ---: | :--- | ---: |');
+};
+
+const writeRow = (name, percent, statsImproved, statsBaseline) => {
+ const {mean: meanImproved, rme: rmeImproved} = statsImproved;
+ const {mean: meanBaseline, rme: rmeBaseline} = statsBaseline;
+ const ratio = meanImproved / meanBaseline;
+
+ console.log(
+ `| ${name} | ${percent}% | ${ratio.toFixed(
+ 4,
+ )} | ${meanImproved.toExponential(4)} | ${rmeImproved.toFixed(
+ 2,
+ )}% | ${meanBaseline.toExponential(4)} | ${rmeBaseline.toFixed(2)}% |`,
+ );
+};
+
+const testDeleteInsert = (tenths, more, less) => {
+ // For improved `diff-sequences` package, delete is often slower than insert.
+ const statsDeleteImproved = testImproved(more, less);
+ const statsDeleteBaseline = testBaseline(more, less);
+ writeRow('delete', tenths * 10, statsDeleteImproved, statsDeleteBaseline);
+
+ // For baseline `diff` package, many insertions is serious perf problem.
+ // However, the benchmark package cannot accurately measure for large n.
+ const statsInsertBaseline = testBaseline(less, more);
+ const statsInsertImproved = testImproved(less, more);
+ writeRow('insert', tenths * 10, statsInsertImproved, statsInsertBaseline);
+};
+
+const testChange = (tenths, expected, received) => {
+ const statsImproved = testImproved(expected, received);
+ const statsBaseline = testBaseline(expected, received);
+ writeRow('change', tenths * 10, statsImproved, statsBaseline);
+};
+
+const getItems = (n, callback) => {
+ const items = [];
+
+ for (let i = 0; i !== n; i += 1) {
+ const item = callback(i);
+ if (typeof item === 'string') {
+ items.push(item);
+ }
+ }
+
+ return items.join('\n');
+};
+
+// Simulate change of property name which is usually not same line.
+// Expected: 0 1 2 3 4 5 6 7 8 9 and so on
+// Received: 1 2 3 4 x0 5 6 7 8 9 and so on
+const change2 = i => {
+ const j = i % 10;
+ return j === 4 ? `x${i - 4}` : j < 4 ? `${i + 1}` : `${i}`;
+};
+
+const testLength = n => {
+ const all = getItems(n, i => `${i}`);
+
+ writeHeading3(n);
+
+ [2, 4, 8].forEach(tenth => {
+ testDeleteInsert(
+ tenth,
+ all,
+ getItems(n, i => i % 10 >= tenth && `${i}`),
+ );
+ });
+ testChange(
+ 1,
+ all,
+ getItems(n, i => (i % 10 === 0 ? `x${i}` : `${i}`)),
+ );
+ testChange(2, all, getItems(n, change2));
+ testChange(
+ 5,
+ all,
+ getItems(n, i => (i % 2 === 0 ? `x${i}` : `${i}`)),
+ );
+ testChange(
+ 10,
+ all,
+ getItems(n, i => `x${i}`),
+ ); // simulate TDD
+};
+
+writeHeading2();
+
+testLength(20);
+testLength(200);
+testLength(2000);
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 14:26:06 +0000