diff-sequences 29.6.3: diff two sequences and report common subsequences

Clean-room public code sample — generation instructions

Write a brand-new, minimal, self-contained code sample in this clean-room directory.
Do not copy, paraphrase, or reference any existing project source. Work only from this spec.

A csx.json manifest scaffold already exists. Do not recreate it from memory. Preserve its case.goal, packages and symbols; fill its empty case.contract with exact assertions and correct its environment, commands and verifierAdapter for the files you generate.

Goal: diff two sequences and report common subsequences
Kind: HOW

Use EXACTLY these public packages and versions:
  - pkg:npm/diff-sequences@29.6.3
Demonstrate these symbols/APIs:
  - default

Rules:
  - One focused purpose; the smallest project that proves the goal.
  - Include a contract test (test/contract.*) that runs OFFLINE and exits 0 exactly when the goal behavior works.
  - Pin every dependency with a lockfile so resolution is reproducible.
  - No secrets, credentials, or tokens. No real URLs (only example.com or localhost). No absolute paths.
  - No personal names, emails, company names, or project identifiers of any kind.
  - No binaries and no generated output (node_modules, dist, target, venv, .git, .env).
  - Keep it under 200 files and 256KB packed.

{"case":{"caseId":"case:sha256:8c7555bbf073a4eda003b7f7429c2abd3f1308b121c83722e2b01fbbfc1c4354","contract":["assert diffSequences finds common subsequences between two sequences","assert diffSequences handles identical sequences reporting single full subsequence","assert diffSequences handles completely disjoint sequences reporting no subsequences","assert diffSequences handles empty sequences gracefully without errors","assert diffSequences supports custom equality comparator function","assert diffSequences throws TypeError when lengths are not numbers or callbacks are not functions","assert diffSequences throws RangeError for negative lengths or non-safe integers","assert diffSequences interop export is a callable function"],"goal":"diff two sequences and report common subsequences","kind":"HOW","packages":["pkg:npm/diff-sequences@29.6.3"],"schemaVersion":1,"symbols":["default"]},"contractCommand":["node","test/contract.mjs"],"environment":{"arch":"x64","distro":"ubuntu","ecosystem":"npm","executionContext":"node","language":"javascript","libc":"glibc","libcVersion":"2.39","moduleSystem":"cjs","os":"linux","osVersionBucket":"24","packageManager":"npm","packageManagerVersion":"10.9.8","runtime":"node","runtimeVersion":"22.23.2","schemaVersion":1},"license":"MIT-0","packages":["pkg:npm/diff-sequences@29.6.3"],"schemaVersion":1,"subject":"pkg:npm/diff-sequences@29.6.3","symbols":["default"],"verifierAdapter":"node-typescript@1"}

const diffSequencesRaw = require('diff-sequences');

const diffSequences = typeof diffSequencesRaw === 'function'
  ? diffSequencesRaw
  : (diffSequencesRaw && diffSequencesRaw.default) || diffSequencesRaw;

/**
 * Finds all common subsequences between sequence a and sequence b.
 *
 * @param {Array|string} a - First sequence
 * @param {Array|string} b - Second sequence
 * @param {Function} [isCommon] - Custom item equality comparator (aIndex, bIndex) => boolean
 * @returns {Array<{nCommon: number, aCommon: number, bCommon: number}>} Array of found common subsequences
 */
function findCommonSubsequences(a, b, isCommon) {
  const comparator = isCommon || ((aIndex, bIndex) => a[aIndex] === b[bIndex]);
  const subsequences = [];

  diffSequences(a.length, b.length, comparator, (nCommon, aCommon, bCommon) => {
    subsequences.push({ nCommon, aCommon, bCommon });
  });

  return subsequences;
}

/**
 * Computes longest common subsequence items between sequence a and sequence b.
 *
 * @param {Array|string} a - First sequence
 * @param {Array|string} b - Second sequence
 * @param {Function} [isCommon] - Custom item equality comparator
 * @returns {Array} Items present in the longest common subsequence
 */
function computeLCS(a, b, isCommon) {
  const subs = findCommonSubsequences(a, b, isCommon);
  const lcs = [];

  for (const { nCommon, aCommon } of subs) {
    for (let i = 0; i < nCommon; i++) {
      lcs.push(a[aCommon + i]);
    }
  }

  return lcs;
}

/**
 * Computes line/item diff operations between sequence a and sequence b.
 *
 * @param {Array} a - Original items
 * @param {Array} b - Modified items
 * @param {Function} [isCommon] - Custom equality comparator
 * @returns {Array<{type: 'common'|'delete'|'insert', items: Array}>} Edit script
 */
function computeDiff(a, b, isCommon) {
  const subs = findCommonSubsequences(a, b, isCommon);
  const edits = [];
  let aIndex = 0;
  let bIndex = 0;

  for (const { nCommon, aCommon, bCommon } of subs) {
    if (aIndex < aCommon) {
      edits.push({
        type: 'delete',
        items: a.slice(aIndex, aCommon),
      });
    }
    if (bIndex < bCommon) {
      edits.push({
        type: 'insert',
        items: b.slice(bIndex, bCommon),
      });
    }
    edits.push({
      type: 'common',
      items: a.slice(aCommon, aCommon + nCommon),
    });
    aIndex = aCommon + nCommon;
    bIndex = bCommon + nCommon;
  }

  if (aIndex < a.length) {
    edits.push({
      type: 'delete',
      items: a.slice(aIndex),
    });
  }
  if (bIndex < b.length) {
    edits.push({
      type: 'insert',
      items: b.slice(bIndex),
    });
  }

  return edits;
}

module.exports = {
  diffSequences,
  findCommonSubsequences,
  computeLCS,
  computeDiff,
};

{
  "name": "sample-diff-sequences",
  "version": "1.0.0",
  "lockfileVersion": 3,
  "requires": true,
  "packages": {
    "": {
      "name": "sample-diff-sequences",
      "version": "1.0.0",
      "license": "MIT-0",
      "dependencies": {
        "diff-sequences": "29.6.3"
      }
    },
    "node_modules/diff-sequences": {
      "version": "29.6.3",
      "resolved": "https://registry.npmjs.org/diff-sequences/-/diff-sequences-29.6.3.tgz",
      "integrity": "sha512-EjePK1srD3P08o2j4f0ExnylqRs5B9tJjcp9t1krH2qRi8CCdsYfwe9JgSLurFBWwq4uOlipzfk5fHNvwFKr8Q==",
      "license": "MIT",
      "engines": {
        "node": "^14.15.0 || ^16.10.0 || >=18.0.0"
      }
    }
  }
}

{
  "name": "sample-diff-sequences",
  "version": "1.0.0",
  "description": "Minimal clean-room sample diffing sequences and finding common subsequences with diff-sequences",
  "main": "index.js",
  "license": "MIT-0",
  "dependencies": {
    "diff-sequences": "29.6.3"
  }
}

{
  "schemaVersion": 1,
  "goal": "diff two sequences and report common subsequences",
  "kind": "HOW",
  "packages": [
    "pkg:npm/diff-sequences@29.6.3"
  ],
  "symbols": [
    "default"
  ]
}

import assert from 'node:assert';
import diffPkg from 'diff-sequences';
import {
  diffSequences as helperDiff,
  findCommonSubsequences,
  computeLCS,
  computeDiff,
} from '../index.js';

const diffSequences = typeof diffPkg === 'function' ? diffPkg : diffPkg.default;

// 1. diffSequences finds common subsequences between two sequences
{
  const seqA = ['alpha', 'beta', 'gamma', 'delta'];
  const seqB = ['alpha', 'gamma', 'delta', 'epsilon'];

  const matches = [];
  diffSequences(
    seqA.length,
    seqB.length,
    (aIndex, bIndex) => seqA[aIndex] === seqB[bIndex],
    (nCommon, aCommon, bCommon) => {
      matches.push({ nCommon, aCommon, bCommon });
    }
  );

  assert.deepStrictEqual(
    matches,
    [
      { nCommon: 1, aCommon: 0, bCommon: 0 },
      { nCommon: 2, aCommon: 2, bCommon: 1 },
    ],
    'Must find exact common subsequence intervals'
  );

  const helperMatches = findCommonSubsequences(seqA, seqB);
  assert.deepStrictEqual(
    helperMatches,
    matches,
    'Helper findCommonSubsequences must match direct diffSequences'
  );

  const lcs = computeLCS(seqA, seqB);
  assert.deepStrictEqual(
    lcs,
    ['alpha', 'gamma', 'delta'],
    'computeLCS must reconstruct longest common subsequence elements'
  );

  const diff = computeDiff(seqA, seqB);
  assert.deepStrictEqual(
    diff,
    [
      { type: 'common', items: ['alpha'] },
      { type: 'delete', items: ['beta'] },
      { type: 'common', items: ['gamma', 'delta'] },
      { type: 'insert', items: ['epsilon'] },
    ],
    'computeDiff must return correct edit sequence'
  );
}

// 2. diffSequences handles identical sequences reporting single full subsequence
{
  const seq = [10, 20, 30, 40];
  const matches = [];

  diffSequences(
    seq.length,
    seq.length,
    (aIdx, bIdx) => seq[aIdx] === seq[bIdx],
    (nCommon, aCommon, bCommon) => {
      matches.push({ nCommon, aCommon, bCommon });
    }
  );

  assert.deepStrictEqual(
    matches,
    [{ nCommon: 4, aCommon: 0, bCommon: 0 }],
    'Identical sequences must produce a single common subsequence spanning full length'
  );

  assert.deepStrictEqual(computeLCS(seq, seq), seq);
}

// 3. diffSequences handles completely disjoint sequences reporting no subsequences
{
  const seqA = [1, 2, 3];
  const seqB = [4, 5, 6];
  const matches = [];

  diffSequences(
    seqA.length,
    seqB.length,
    (aIdx, bIdx) => seqA[aIdx] === seqB[bIdx],
    (nCommon, aCommon, bCommon) => {
      matches.push({ nCommon, aCommon, bCommon });
    }
  );

  assert.strictEqual(matches.length, 0, 'Disjoint sequences must produce no common subsequences');
  assert.deepStrictEqual(computeLCS(seqA, seqB), []);
}

// 4. diffSequences handles empty sequences gracefully without errors
{
  const emptyMatches = [];
  diffSequences(
    0,
    0,
    () => true,
    (nCommon, aCommon, bCommon) => {
      emptyMatches.push({ nCommon, aCommon, bCommon });
    }
  );
  assert.strictEqual(emptyMatches.length, 0, 'Empty sequences must produce no common subsequences');

  const leftEmpty = [];
  diffSequences(
    0,
    3,
    () => false,
    (nCommon, aCommon, bCommon) => {
      leftEmpty.push({ nCommon, aCommon, bCommon });
    }
  );
  assert.strictEqual(leftEmpty.length, 0, 'Left empty sequence must produce no common subsequences');

  const rightEmpty = [];
  diffSequences(
    3,
    0,
    () => false,
    (nCommon, aCommon, bCommon) => {
      rightEmpty.push({ nCommon, aCommon, bCommon });
    }
  );
  assert.strictEqual(rightEmpty.length, 0, 'Right empty sequence must produce no common subsequences');
}

// 5. diffSequences supports custom equality comparator function
{
  const usersA = [
    { id: 1, name: 'Alice' },
    { id: 2, name: 'Bob' },
  ];
  const usersB = [
    { id: 1, name: 'Alice (Modified)' },
    { id: 3, name: 'Charlie' },
  ];

  const idMatches = findCommonSubsequences(
    usersA,
    usersB,
    (aIdx, bIdx) => usersA[aIdx].id === usersB[bIdx].id
  );

  assert.deepStrictEqual(
    idMatches,
    [{ nCommon: 1, aCommon: 0, bCommon: 0 }],
    'Custom comparator comparing only IDs must match id=1'
  );
}

// 6. diffSequences throws TypeError when lengths are not numbers or callbacks are not functions
{
  assert.throws(
    () => diffSequences('4', 4, () => true, () => {}),
    {
      name: 'TypeError',
      message: /aLength typeof string is not a number/,
    },
    'Must throw TypeError when aLength is not a number'
  );

  assert.throws(
    () => diffSequences(4, '4', () => true, () => {}),
    {
      name: 'TypeError',
      message: /bLength typeof string is not a number/,
    },
    'Must throw TypeError when bLength is not a number'
  );

  assert.throws(
    () => diffSequences(4, 4, null, () => {}),
    {
      name: 'TypeError',
      message: /isCommon typeof object is not a function/,
    },
    'Must throw TypeError when isCommon is not a function'
  );

  assert.throws(
    () => diffSequences(4, 4, () => true, 'callback'),
    {
      name: 'TypeError',
      message: /foundSubsequence typeof string is not a function/,
    },
    'Must throw TypeError when foundSubsequence is not a function'
  );
}

// 7. diffSequences throws RangeError for negative lengths or non-safe integers
{
  assert.throws(
    () => diffSequences(-1, 5, () => true, () => {}),
    {
      name: 'RangeError',
      message: /aLength value -1 is a negative integer/,
    },
    'Must throw RangeError for negative aLength'
  );

  assert.throws(
    () => diffSequences(5, -2, () => true, () => {}),
    {
      name: 'RangeError',
      message: /bLength value -2 is a negative integer/,
    },
    'Must throw RangeError for negative bLength'
  );

  assert.throws(
    () => diffSequences(1.5, 5, () => true, () => {}),
    {
      name: 'RangeError',
      message: /aLength value 1.5 is not a safe integer/,
    },
    'Must throw RangeError for floating point aLength'
  );
}

// 8. Module export verification
assert.strictEqual(typeof diffSequences, 'function', 'diffSequences must be a function');
assert.strictEqual(typeof helperDiff, 'function', 'helper diffSequences must be a function');

console.log('All diff-sequences contract assertions passed.');