{"_id":"@jest/diff-sequences","_rev":"4509379","name":"@jest/diff-sequences","description":"Compare items in two sequences to find a longest common subsequence","dist-tags":{"latest":"30.3.0","next":"30.0.0-beta.8"},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"time":{"modified":"2026-04-09T10:13:09.000Z","created":"2025-05-27T01:23:14.346Z","30.3.0":"2026-03-10T01:59:37.637Z","30.0.1":"2025-06-18T22:31:17.025Z","30.0.0":"2025-06-10T02:15:39.865Z","30.0.0-beta.8":"2025-06-04T07:53:01.641Z","30.0.0-beta.7":"2025-06-04T03:35:34.544Z","30.0.0-beta.6":"2025-06-03T23:50:37.166Z","30.0.0-beta.3":"2025-05-27T01:27:35.402Z","30.0.0-beta.2":"2025-05-27T01:23:14.346Z"},"users":{},"repository":{"type":"git","url":"https://github.com/jestjs/jest.git","directory":"packages/diff-sequences"},"versions":{"30.3.0":{"name":"@jest/diff-sequences","version":"30.3.0","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || ^22.0.0 || >=24.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.1.1","benchmark":"^2.1.4","diff":"^8.0.3"},"publishConfig":{"access":"public"},"gitHead":"efb59c2e81083f8dc941f20d6d20a3af2dc8d068","_nodeVersion":"24.14.0","_npmVersion":"lerna/4.3.0/node@v24.14.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.3.0","dist":{"shasum":"25b0818d3d83f00b9c7b04e069b8810f9014b143","size":11439,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.3.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.3.0.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.3.0_1773107977482_0.5244905296602691"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2026-03-10T01:59:37.637Z","publish_time":1773107977637,"_source_registry_name":"default","_cnpm_publish_time":1773107977637},"30.0.1":{"name":"@jest/diff-sequences","version":"30.0.1","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || ^22.0.0 || >=24.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.1.1","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"5ce865b4060189fe74cd486544816c079194a0f7","_nodeVersion":"24.2.0","_npmVersion":"lerna/4.3.0/node@v24.2.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.1","dist":{"shasum":"0ededeae4d071f5c8ffe3678d15f3a1be09156be","size":11401,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.1.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.1.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com","actor":{"name":"cpojer","email":"christoph.pojer@gmail.com","type":"user"}},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.1_1750285876850_0.7390238164916036"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-06-18T22:31:17.025Z","publish_time":1750285877025,"_source_registry_name":"default","_cnpm_publish_time":1750285877025},"30.0.0":{"name":"@jest/diff-sequences","version":"30.0.0","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || ^22.0.0 || >=24.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.1.1","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"a383155cd5af4539b3c447cfa7184462ee32f418","_nodeVersion":"24.1.0","_npmVersion":"lerna/4.3.0/node@v24.1.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.0","dist":{"shasum":"402d27d14e9d5161dedfca98bf181018a8931eb1","size":11401,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.0.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.0_1749521739663_0.2263188657876063"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-06-10T02:15:39.865Z","publish_time":1749521739865,"_source_registry_name":"default","_cnpm_publish_time":1749521739865},"30.0.0-beta.8":{"name":"@jest/diff-sequences","version":"30.0.0-beta.8","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || ^22.0.0 || >=24.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.1.1","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"ac334c0cdf04ead9999f0964567d81672d116d42","_nodeVersion":"24.1.0","_npmVersion":"lerna/4.3.0/node@v24.1.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.0-beta.8","dist":{"shasum":"d960e46228f008c15f10bd98161c81f5d6ffc39a","size":11400,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.0-beta.8.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.0-beta.8.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.0-beta.8_1749023581466_0.5935016076470272"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-06-04T07:53:01.641Z","publish_time":1749023581641,"_source_registry_name":"default","_cnpm_publish_time":1749023581641},"30.0.0-beta.7":{"name":"@jest/diff-sequences","version":"30.0.0-beta.7","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || ^22.0.0 || >=24.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.1.1","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"48de6a91368727d853d491df16e7d00c1f323676","_nodeVersion":"24.1.0","_npmVersion":"lerna/4.3.0/node@v24.1.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.0-beta.7","dist":{"shasum":"d41c9bf06f4ecb2e57d1a655c30843c7e5fa0a7d","size":11404,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.0-beta.7.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.0-beta.7.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.0-beta.7_1749008134322_0.45309901799383745"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-06-04T03:35:34.544Z","publish_time":1749008134544,"_source_registry_name":"default","_cnpm_publish_time":1749008134544},"30.0.0-beta.6":{"name":"@jest/diff-sequences","version":"30.0.0-beta.6","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || ^22.0.0 || >=24.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.0.0","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"4f964497dc21c06ce4d54f1349e299a9f6773d52","_nodeVersion":"24.1.0","_npmVersion":"lerna/3.12.3/node@v24.1.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.0-beta.6","dist":{"shasum":"250c1b1ad097b36c22c65288e650f77b1972ca82","size":11403,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.0-beta.6.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.0-beta.6.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.0-beta.6_1748994636982_0.5570974136486866"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-06-03T23:50:37.166Z","publish_time":1748994637166,"_source_registry_name":"default","_cnpm_publish_time":1748994637166},"30.0.0-beta.3":{"name":"@jest/diff-sequences","version":"30.0.0-beta.3","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || >=22.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.0.0","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"a123a3b667a178fb988662aaa1bc6308af759017","_nodeVersion":"23.11.0","_npmVersion":"lerna/3.12.3/node@v23.11.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.0-beta.3","dist":{"shasum":"1e695c3a71438d4a4bf94dac32a37148eada73aa","size":11403,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.0-beta.3.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.0-beta.3.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.0-beta.3_1748309255220_0.7379922374947048"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-05-27T01:27:35.402Z","publish_time":1748309255402,"_source_registry_name":"default","_cnpm_publish_time":1748309255402},"30.0.0-beta.2":{"name":"@jest/diff-sequences","version":"30.0.0-beta.2","repository":{"type":"git","url":"https://github.com/jestjs/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":"^18.14.0 || ^20.0.0 || >=22.0.0"},"main":"./build/index.js","types":"./build/index.d.ts","exports":{".":{"types":"./build/index.d.ts","require":"./build/index.js","import":"./build/index.mjs","default":"./build/index.js"},"./package.json":"./package.json"},"devDependencies":{"@fast-check/jest":"^2.0.0","benchmark":"^2.1.4","diff":"^7.0.0"},"publishConfig":{"access":"public"},"gitHead":"53a5635ac9a43099033f6103e179b13a5465e017","_nodeVersion":"23.11.0","_npmVersion":"lerna/3.12.3/node@v23.11.0+arm64 (darwin)","_id":"@jest/diff-sequences@30.0.0-beta.2","dist":{"shasum":"a94526a5de0c5885ba2c0fbf04b796eda1558204","size":11403,"noattachment":false,"key":"/@jest/diff-sequences/-/@jest/diff-sequences-30.0.0-beta.2.tgz","tarball":"http://registry.cnpm.dingdandao.com/@jest/diff-sequences/download/@jest/diff-sequences-30.0.0-beta.2.tgz"},"_npmUser":{"name":"cpojer","email":"christoph.pojer@gmail.com"},"directories":{},"maintainers":[{"name":"aaronabramov","email":""},{"name":"cpojer","email":"christoph.pojer@gmail.com"},{"name":"openjs-operations","email":""},{"name":"rickhanlonii","email":"rickhanlonii@gmail.com"},{"name":"simenb","email":"sbekkhus91@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/diff-sequences_30.0.0-beta.2_1748308994153_0.33958524731410766"},"_hasShrinkwrap":false,"_cnpmcore_publish_time":"2025-05-27T01:23:14.346Z","publish_time":1748308994346,"_source_registry_name":"default","_cnpm_publish_time":1748308994346}},"readme":"# diff-sequences\n\nCompare items in two sequences to find a **longest common subsequence**.\n\nThe items not in common are the items to delete or insert in a **shortest edit script**.\n\nTo maximize flexibility and minimize memory, you write **callback** functions as configuration:\n\n**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.\n\n- Because your function encapsulates **comparison**, this package can compare items according to `===` operator, `Object.is` method, or other criterion.\n- Because your function encapsulates **sequences**, this package can find differences in arrays, strings, or other data.\n\n**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.\n\nIf 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.\n\n[_An O(ND) Difference Algorithm and Its Variations_](http://xmailserver.org/diff2.pdf) by Eugene W. Myers is fast when sequences have **few** differences.\n\nThis package implements the **linear space** variation with optimizations so it is fast even when sequences have **many** differences.\n\n## Usage\n\nTo add this package as a dependency of a project, do either of the following:\n\n- `npm install diff-sequences`\n- `yarn add diff-sequences`\n\nTo use `diff` as the name of the default export from this package, do either of the following:\n\n- `var diff = require('@jest/diff-sequences').default; // CommonJS modules`\n- `import diff from '@jest/diff-sequences'; // ECMAScript modules`\n\nCall `diff` with the **lengths** of sequences and your **callback** functions:\n\n```js\nconst a = ['a', 'b', 'c', 'a', 'b', 'b', 'a'];\nconst b = ['c', 'b', 'a', 'b', 'a', 'c'];\n\nfunction isCommon(aIndex, bIndex) {\n  return a[aIndex] === b[bIndex];\n}\nfunction foundSubsequence(nCommon, aCommon, bCommon) {\n  // see examples\n}\n\ndiff(a.length, b.length, isCommon, foundSubsequence);\n```\n\n## Example of longest common subsequence\n\nSome sequences (for example, `a` and `b` in the example of usage) have more than one longest common subsequence.\n\nThis package finds the following common items:\n\n| comparisons of common items      | values     |            output arguments |\n| :------------------------------- | :--------- | --------------------------: |\n| `a[2] === b[0]`                  | `'c'`      | `foundSubsequence(1, 2, 0)` |\n| `a[4] === b[1]`                  | `'b'`      | `foundSubsequence(1, 4, 1)` |\n| `a[5] === b[3] && a[6] === b[4]` | `'b', 'a'` | `foundSubsequence(2, 5, 3)` |\n\nThe “edit graph” analogy in the Myers paper shows the following common items:\n\n| comparisons of common items      | values     |\n| :------------------------------- | :--------- |\n| `a[2] === b[0]`                  | `'c'`      |\n| `a[3] === b[2] && a[4] === b[3]` | `'a', 'b'` |\n| `a[6] === b[4]`                  | `'a'`      |\n\nVarious 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.\n\n## Example of callback functions to count common items\n\n```js\n// Return length of longest common subsequence according to === operator.\nfunction countCommonItems(a, b) {\n  let n = 0;\n  function isCommon(aIndex, bIndex) {\n    return a[aIndex] === b[bIndex];\n  }\n  function foundSubsequence(nCommon) {\n    n += nCommon;\n  }\n\n  diff(a.length, b.length, isCommon, foundSubsequence);\n\n  return n;\n}\n\nconst commonLength = countCommonItems(\n  ['a', 'b', 'c', 'a', 'b', 'b', 'a'],\n  ['c', 'b', 'a', 'b', 'a', 'c'],\n);\n```\n\n| category of items  |                expression | value |\n| :----------------- | ------------------------: | ----: |\n| in common          |            `commonLength` |   `4` |\n| to delete from `a` | `a.length - commonLength` |   `3` |\n| to insert from `b` | `b.length - commonLength` |   `2` |\n\nIf the length difference `b.length - a.length` is:\n\n- negative: its absolute value is the minimum number of items to **delete** from `a`\n- positive: it is the minimum number of items to **insert** from `b`\n- zero: there is an **equal** number of items to delete from `a` and insert from `b`\n- non-zero: there is an equal number of **additional** items to delete from `a` and insert from `b`\n\nIn this example, `6 - 7` is:\n\n- negative: `1` is the minimum number of items to **delete** from `a`\n- non-zero: `2` is the number of **additional** items to delete from `a` and insert from `b`\n\n## Example of callback functions to find common items\n\n```js\n// Return array of items in longest common subsequence according to Object.is method.\nconst findCommonItems = (a, b) => {\n  const array = [];\n  diff(\n    a.length,\n    b.length,\n    (aIndex, bIndex) => Object.is(a[aIndex], b[bIndex]),\n    (nCommon, aCommon) => {\n      for (; nCommon !== 0; nCommon -= 1, aCommon += 1) {\n        array.push(a[aCommon]);\n      }\n    },\n  );\n  return array;\n};\n\nconst commonItems = findCommonItems(\n  ['a', 'b', 'c', 'a', 'b', 'b', 'a'],\n  ['c', 'b', 'a', 'b', 'a', 'c'],\n);\n```\n\n| `i` | `commonItems[i]` | `aIndex` |\n| --: | :--------------- | -------: |\n| `0` | `'c'`            |      `2` |\n| `1` | `'b'`            |      `4` |\n| `2` | `'b'`            |      `5` |\n| `3` | `'a'`            |      `6` |\n\n## Example of callback functions to diff index intervals\n\nInstead of slicing array-like objects, you can adjust indexes in your callback functions.\n\n```js\n// Diff index intervals that are half open [start, end) like array slice method.\nconst diffIndexIntervals = (a, aStart, aEnd, b, bStart, bEnd) => {\n  // Validate: 0 <= aStart and aStart <= aEnd and aEnd <= a.length\n  // Validate: 0 <= bStart and bStart <= bEnd and bEnd <= b.length\n\n  diff(\n    aEnd - aStart,\n    bEnd - bStart,\n    (aIndex, bIndex) => Object.is(a[aStart + aIndex], b[bStart + bIndex]),\n    (nCommon, aCommon, bCommon) => {\n      // aStart + aCommon, bStart + bCommon\n    },\n  );\n\n  // After the last common subsequence, do any remaining work.\n};\n```\n\n## Example of callback functions to emulate diff command\n\nLinux or Unix has a `diff` command to compare files line by line. Its output is a **shortest edit script**:\n\n- **c**hange adjacent lines from the first file to lines from the second file\n- **d**elete lines from the first file\n- **a**ppend or insert lines from the second file\n\n```js\n// Given zero-based half-open range [start, end) of array indexes,\n// return one-based closed range [start + 1, end] as string.\nconst getRange = (start, end) =>\n  start + 1 === end ? `${start + 1}` : `${start + 1},${end}`;\n\n// Given index intervals of lines to delete or insert, or both, or neither,\n// push formatted diff lines onto array.\nconst pushDelIns = (aLines, aIndex, aEnd, bLines, bIndex, bEnd, array) => {\n  const deleteLines = aIndex !== aEnd;\n  const insertLines = bIndex !== bEnd;\n  const changeLines = deleteLines && insertLines;\n  if (changeLines) {\n    array.push(`${getRange(aIndex, aEnd)}c${getRange(bIndex, bEnd)}`);\n  } else if (deleteLines) {\n    array.push(`${getRange(aIndex, aEnd)}d${String(bIndex)}`);\n  } else if (insertLines) {\n    array.push(`${String(aIndex)}a${getRange(bIndex, bEnd)}`);\n  } else {\n    return;\n  }\n\n  for (; aIndex !== aEnd; aIndex += 1) {\n    array.push(`< ${aLines[aIndex]}`); // delete is less than\n  }\n\n  if (changeLines) {\n    array.push('---');\n  }\n\n  for (; bIndex !== bEnd; bIndex += 1) {\n    array.push(`> ${bLines[bIndex]}`); // insert is greater than\n  }\n};\n\n// Given content of two files, return emulated output of diff utility.\nconst findShortestEditScript = (a, b) => {\n  const aLines = a.split('\\n');\n  const bLines = b.split('\\n');\n  const aLength = aLines.length;\n  const bLength = bLines.length;\n\n  const isCommon = (aIndex, bIndex) => aLines[aIndex] === bLines[bIndex];\n\n  let aIndex = 0;\n  let bIndex = 0;\n  const array = [];\n  const foundSubsequence = (nCommon, aCommon, bCommon) => {\n    pushDelIns(aLines, aIndex, aCommon, bLines, bIndex, bCommon, array);\n    aIndex = aCommon + nCommon; // number of lines compared in a\n    bIndex = bCommon + nCommon; // number of lines compared in b\n  };\n\n  diff(aLength, bLength, isCommon, foundSubsequence);\n\n  // After the last common subsequence, push remaining change lines.\n  pushDelIns(aLines, aIndex, aLength, bLines, bIndex, bLength, array);\n\n  return array.length === 0 ? '' : `${array.join('\\n')}\\n`;\n};\n```\n\n## Example of callback functions to format diff lines\n\nHere is simplified code to format **changed and unchanged lines** in expected and received values after a test fails in Jest:\n\n```js\n// Format diff with minus or plus for change lines and space for common lines.\nconst formatDiffLines = (a, b) => {\n  // Jest depends on pretty-format package to serialize objects as strings.\n  // Unindented for comparison to avoid distracting differences:\n  const aLinesUn = format(a, {indent: 0 /*, other options*/}).split('\\n');\n  const bLinesUn = format(b, {indent: 0 /*, other options*/}).split('\\n');\n  // Indented to display changed and unchanged lines:\n  const aLinesIn = format(a, {indent: 2 /*, other options*/}).split('\\n');\n  const bLinesIn = format(b, {indent: 2 /*, other options*/}).split('\\n');\n\n  const aLength = aLinesIn.length; // Validate: aLinesUn.length === aLength\n  const bLength = bLinesIn.length; // Validate: bLinesUn.length === bLength\n\n  const isCommon = (aIndex, bIndex) => aLinesUn[aIndex] === bLinesUn[bIndex];\n\n  // Only because the GitHub Flavored Markdown doc collapses adjacent spaces,\n  // this example code and the following table represent spaces as middle dots.\n  let aIndex = 0;\n  let bIndex = 0;\n  const array = [];\n  const foundSubsequence = (nCommon, aCommon, bCommon) => {\n    for (; aIndex !== aCommon; aIndex += 1) {\n      array.push(`-·${aLinesIn[aIndex]}`); // delete is minus\n    }\n    for (; bIndex !== bCommon; bIndex += 1) {\n      array.push(`+·${bLinesIn[bIndex]}`); // insert is plus\n    }\n    for (; nCommon !== 0; nCommon -= 1, aIndex += 1, bIndex += 1) {\n      // For common lines, received indentation seems more intuitive.\n      array.push(`··${bLinesIn[bIndex]}`); // common is space\n    }\n  };\n\n  diff(aLength, bLength, isCommon, foundSubsequence);\n\n  // After the last common subsequence, push remaining change lines.\n  for (; aIndex !== aLength; aIndex += 1) {\n    array.push(`-·${aLinesIn[aIndex]}`);\n  }\n  for (; bIndex !== bLength; bIndex += 1) {\n    array.push(`+·${bLinesIn[bIndex]}`);\n  }\n\n  return array;\n};\n\nconst expected = {\n  searching: '',\n  sorting: {\n    ascending: true,\n    fieldKey: 'what',\n  },\n};\nconst received = {\n  searching: '',\n  sorting: [\n    {\n      descending: false,\n      fieldKey: 'what',\n    },\n  ],\n};\n\nconst diffLines = formatDiffLines(expected, received);\n```\n\nIf 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.\n\n|  `i` | `diffLines[i]`                     | `aIndex` | `bIndex` |\n| ---: | :--------------------------------- | -------: | -------: |\n|  `0` | `'··Object {'`                     |      `0` |      `0` |\n|  `1` | `'····\"searching\": \"\",'`           |      `1` |      `1` |\n|  `2` | `'-···\"sorting\": Object {'`        |      `2` |          |\n|  `3` | `'-·····\"ascending\": true,'`       |      `3` |          |\n|  `4` | `'+·····\"sorting\": Array ['`       |          |      `2` |\n|  `5` | `'+·······Object {'`               |          |      `3` |\n|  `6` | `'+·········\"descending\": false,'` |          |      `4` |\n|  `7` | `'··········\"fieldKey\": \"what\",'`  |      `4` |      `5` |\n|  `8` | `'········},'`                     |      `5` |      `6` |\n|  `9` | `'+·····],'`                       |          |      `7` |\n| `10` | `'··}'`                            |      `6` |      `8` |\n\n## Example of callback functions to find diff items\n\nHere is simplified code to find changed and unchanged substrings **within adjacent changed lines** in expected and received values after a test fails in Jest:\n\n```js\n// Return diff items for strings (compatible with diff-match-patch package).\nconst findDiffItems = (a, b) => {\n  const isCommon = (aIndex, bIndex) => a[aIndex] === b[bIndex];\n\n  let aIndex = 0;\n  let bIndex = 0;\n  const array = [];\n  const foundSubsequence = (nCommon, aCommon, bCommon) => {\n    if (aIndex !== aCommon) {\n      array.push([-1, a.slice(aIndex, aCommon)]); // delete is -1\n    }\n    if (bIndex !== bCommon) {\n      array.push([1, b.slice(bIndex, bCommon)]); // insert is 1\n    }\n\n    aIndex = aCommon + nCommon; // number of characters compared in a\n    bIndex = bCommon + nCommon; // number of characters compared in b\n    array.push([0, a.slice(aCommon, aIndex)]); // common is 0\n  };\n\n  diff(a.length, b.length, isCommon, foundSubsequence);\n\n  // After the last common subsequence, push remaining change items.\n  if (aIndex !== a.length) {\n    array.push([-1, a.slice(aIndex)]);\n  }\n  if (bIndex !== b.length) {\n    array.push([1, b.slice(bIndex)]);\n  }\n\n  return array;\n};\n\nconst expectedDeleted = ['\"sorting\": Object {', '\"ascending\": true,'].join(\n  '\\n',\n);\nconst receivedInserted = [\n  '\"sorting\": Array [',\n  'Object {',\n  '\"descending\": false,',\n].join('\\n');\n\nconst diffItems = findDiffItems(expectedDeleted, receivedInserted);\n```\n\n| `i` | `diffItems[i][0]` | `diffItems[i][1]` |\n| --: | ----------------: | :---------------- |\n| `0` |               `0` | `'\"sorting\": '`   |\n| `1` |               `1` | `'Array [\\n'`     |\n| `2` |               `0` | `'Object {\\n\"'`   |\n| `3` |              `-1` | `'a'`             |\n| `4` |               `1` | `'de'`            |\n| `5` |               `0` | `'scending\": '`   |\n| `6` |              `-1` | `'tru'`           |\n| `7` |               `1` | `'fals'`          |\n| `8` |               `0` | `'e,'`            |\n\nThe 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`.\n\n| category of diff item | `[0]` |      `[1]` lengths | subtotal |\n| :-------------------- | ----: | -----------------: | -------: |\n| in common             |   `0` | `11 + 10 + 11 + 2` |      `0` |\n| to delete from `a`    |  `–1` |            `1 + 3` |     `-4` |\n| to insert from `b`    |   `1` |        `8 + 2 + 4` |     `14` |\n\nInstead 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:\n\n| `i` | `diffItems[i][0]` | `diffItems[i][1]` |\n| --: | ----------------: | :---------------- |\n| `6` |              `-1` | `'true'`          |\n| `7` |               `1` | `'false'`         |\n| `8` |               `0` | `','`             |\n\nFor 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.\n","_attachments":{},"license":"MIT"}