Research
Security News
Malicious npm Package Typosquats react-login-page to Deploy Keylogger
Socket researchers unpack a typosquatting package with malicious code that logs keystrokes and exfiltrates sensitive data to a remote server.
diff-sequences
Advanced tools
Package description
The diff-sequences package is a utility for finding the longest common subsequence of items in two sequences (arrays). It is typically used for comparing sequences to determine the changes necessary to convert one sequence into another, which is useful in various applications such as diff tools, merging changes, and more.
Finding Longest Common Subsequence (LCS)
This feature allows you to find the longest common subsequence between two arrays. The provided code sample demonstrates how to use the package to compare two arrays and log the LCS.
const diff = require('diff-sequences');
const a = [1, 2, 3, 4, 5];
const b = [2, 3, 5];
const isCommon = (aIndex, bIndex) => a[aIndex] === b[bIndex];
let result = '';
const foundSubsequence = diff(a.length, b.length, isCommon, (nCommon, aCommon, bCommon) => {
for (let i = 0; i < nCommon; i++) {
result += a[aCommon + i];
}
});
console.log(result); // '235'
fast-diff is a JavaScript implementation of the O(ND) difference algorithm. It is used to quickly compute the difference between two strings and can return the result as an array of parts indicating if they are in the first string, second string, or both. It is similar to diff-sequences but is specifically optimized for string comparison rather than generic sequences.
jsdiff (also known as diff) is a library that provides several algorithms for string comparison, including character-by-character, word-by-word, and line-by-line diffs. It offers more features than diff-sequences, such as applying patches or computing diffs in different formats (e.g., JSON). It is more feature-rich but also larger and potentially slower for simple LCS computations.
google-diff-match-patch is a comprehensive library for performing operations required for synchronizing plain text. It includes algorithms for diff, match, and patch operations. It is more complex and feature-complete compared to diff-sequences, which is more focused on the specific task of finding the longest common subsequence.
Changelog
25.1.0
[babel-plugin-jest-hoist]
Show codeframe on static hoisting issues (#8865)[babel-plugin-jest-hoist]
Add BigInt
to ALLOWED_IDENTIFIERS
(#8382)[babel-preset-jest]
Add @babel/plugin-syntax-bigint
(#8382)[expect]
Add BigInt
support to toBeGreaterThan
, toBeGreaterThanOrEqual
, toBeLessThan
and toBeLessThanOrEqual
(#8382)[expect, jest-matcher-utils]
Display change counts in annotation lines (#9035)[expect, jest-snapshot]
Support custom inline snapshot matchers (#9278)[jest-config]
Throw the full error message and stack when a Jest preset is missing a dependency (#8924)[jest-config]
[BREAKING] Set default display name color based on runner (#8689)[jest-config]
Merge preset globals with project globals (#9027)[jest-config]
Support .cjs
config files (#9291)[jest-config]
[BREAKING] Support .mjs
config files (#9431)[jest-core]
Support reporters as default exports (#9161)[jest-core]
Support --findRelatedTests
paths case insensitivity on Windows (#8961)[jest-diff]
Add options for colors and symbols (#8841)[jest-diff]
[BREAKING] Export as ECMAScript module (#8873)[jest-diff]
Add includeChangeCounts
and rename Indicator
options (#8881)[jest-diff]
Add changeColor
and patchColor
options (#8911)[jest-diff]
Add trailingSpaceFormatter
option and replace cyan with commonColor
(#8927)[jest-diff]
Add firstOrLastEmptyLineReplacement
option and export 3 diffLines
functions (#8955)[jest-environment]
Add optional getVmContext
next to runScript
(#9252 & #9428)[jest-environment-jsdom]
Add fakeTimersLolex
(#8925)[jest-environment-node]
Add fakeTimersLolex
(#8925)[jest-environment-node]
Add queueMicrotask
(#9140)[jest-environment-node]
Implement getVmContext
(#9252 & #9428)[@jest/fake-timers]
Add Lolex as implementation of fake timers (#8897)[jest-get-type]
Add BigInt
support. (#8382)[jest-matcher-utils]
Add BigInt
support to ensureNumbers
ensureActualIsNumber
, ensureExpectedIsNumber
(#8382)[jest-matcher-utils]
Ignore highlighting matched asymmetricMatcher in diffs (#9257)[jest-reporters]
Export utils for path formatting (#9162)[jest-reporters]
Provides global coverage thresholds as watermarks for istanbul (#9416)[jest-runner]
Warn if a worker had to be force exited (#8206)[jest-runtime]
[BREAKING] Do not export ScriptTransformer
- it can be imported from @jest/transform
instead (#9256)[jest-runtime]
Use JestEnvironment.getVmContext
and vm.compileFunction
if available to avoid the module wrapper (#9252 & #9428)[jest-snapshot]
Display change counts in annotation lines (#8982)[jest-snapshot]
[BREAKING] Improve report when the matcher has properties (#9104)[jest-snapshot]
Improve colors when snapshots are updatable (#9132)[jest-snapshot]
Ignore indentation for most serialized objects (#9203)[jest-transform]
Create createTranspilingRequire
function for easy transpiling modules (#9194)[jest-transform]
[BREAKING] Return transformed code as a string, do not wrap in vm.Script
(#9253)[@jest/test-result]
Create method to create empty TestResult
(#8867)[jest-worker]
[BREAKING] Return a promise from end()
, resolving with the information whether workers exited gracefully (#8206)[jest-reporters]
Transform file paths into hyperlinks (#8980)[expect]
Display expectedDiff
more carefully in toBeCloseTo
(#8389)[expect]
Avoid incorrect difference for subset when toMatchObject
fails (#9005)[expect]
Consider all RegExp flags for equality (#9167)[expect]
[BREAKING] Consider primitives different from wrappers instantiated with new
(#9167)[expect]
Prevent maintaining RegExp state between multiple tests (#9289)[expect]
Fix subsetEquality false circular reference detection (#9322)[jest-config]
Use half of the available cores when watchAll
mode is enabled (#9117)[jest-config]
Fix Jest multi project runner still cannot handle exactly one project (#8894)[jest-console]
Add missing console.group
calls to NullConsole
(#9024)[jest-core]
Don't include unref'd timers in --detectOpenHandles results (#8941)[jest-core]
Limit number of workers when creating haste maps in projects (#9259)[jest-diff]
Do not inverse format if line consists of one change (#8903)[jest-diff]
Rename some new options and change their default values (#9077)[jest-environment-node]
Fix TextEncoder.encode
not referencing same global Uint8Array
constructor (#9261)[jest-fake-timers]
getTimerCount
will not include cancelled immediates (#8764)[jest-fake-timers]
Support util.promisify
on setTimeout
(#9180)[jest-jasmine2, jest-circus]
Improve error message format for Node's assert.fail (#9262)[jest-leak-detector]
[BREAKING] Use weak-napi
instead of weak
package (#8686)[jest-mock]
Fix for mockReturnValue overriding mockImplementationOnce (#8398)[jest-reporters]
Make node-notifier an optional dependency (#8918)[jest-reporters]
Make all arguments to methods on BaseReporter
optional (#9159)[jest-resolve]
: Set MODULE_NOT_FOUND as error code when module is not resolved from paths (#8487)[jest-resolve-dependencies]
Handle dynamic dependencies correctly even when using module maps (#9303)[jest-snapshot]
Remove only the added newlines in multiline snapshots (#8859)[jest-snapshot]
Distinguish empty string from external snapshot not written (#8880)[jest-snapshot]
[BREAKING] Distinguish empty string from internal snapshot not written (#8898)[jest-snapshot]
[BREAKING] Remove report
method and throw matcher errors (#9049)[jest-snapshot]
Omit irrelevant received
properties when property matchers fail (#9198)[jest-transform]
Properly cache transformed files across tests (#8890)[jest-transform]
Don't fail the test suite when a generated source map is invalid (#9058)[jest-types]
[BREAKING] Use less null | undefined
in config types (#9200)[jest-util]
Allow querying process.domain (#9136)[pretty-format]
Correctly detect memoized elements (#9196)[pretty-format]
Fix pretty-format to respect displayName on forwardRef (#9422)[*]
[BREAKING] Drop support for Node 6 (#8455)[*]
Add Node 12 to CI (#8411)[*]
[BREAKING] Upgrade to Micromatch v4 (#8852)[babel-plugin-jest-hoist]
[BREAKING] Use ESM exports (#8874)[docs]
Add alias and optional boolean value to coverage
CLI Reference (#8996)[docs]
Fix broken link pointing to legacy JS file in "Snapshot Testing".[docs]
Add setupFilesAfterEnv
and jest.setTimeout
example (#8971)[expect]
Test that toStrictEqual
is equivalent to Node's assert.deepStrictEqual
(#9167)[jest]
[BREAKING] Use ESM exports (#8874)[jest-cli]
[BREAKING] Use ESM exports (#8874)[jest-cli]
[BREAKING] Remove re-exports from @jest/core
(#8874)[jest-diff]
Remove the need to export splitLines0
function (#9151)[jest-environment-jsdom]
[BREAKING] Upgrade JSDOM from v11 to v15 (#8851)[jest-haste-map]
Upgrade to fsevents@2
(#9215)[jest-reporters]
[BREAKING] Upgrade Istanbul dependencies, which are used for code coverage (#9192)[jest-util]
[BREAKING] Remove deprecated exports (#8863)[jest-validate]
[BREAKING] Use ESM exports (#8874)[jest-types]
Mark InitialOptions
as Partial
(#8848)[jest-config]
Refactor normalize
to be more type safe (#8848)Readme
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.
===
operator, Object.is
method, or other criterion.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 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.
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:
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);
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.
// 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:
a
b
a
and insert from b
a
and insert from b
In this example, 6 - 7
is:
1
is the minimum number of items to delete from a
2
is the number of additional items to delete from a
and insert from b
// 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 |
Instead of slicing array-like objects, you can adjust indexes in your callback functions.
// 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.
};
Linux or Unix has a diff
command to compare files line by line. Its output is a shortest edit script:
// 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';
};
Here is simplified code to format changed and unchanged lines in expected and received values after a test fails in Jest:
// 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 |
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:
// 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.
FAQs
Unknown package
The npm package diff-sequences receives a total of 22,849,201 weekly downloads. As such, diff-sequences popularity was classified as popular.
We found that diff-sequences demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 5 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Research
Security News
Socket researchers unpack a typosquatting package with malicious code that logs keystrokes and exfiltrates sensitive data to a remote server.
Security News
The JavaScript community has launched the e18e initiative to improve ecosystem performance by cleaning up dependency trees, speeding up critical parts of the ecosystem, and documenting lighter alternatives to established tools.
Product
Socket now supports four distinct alert actions instead of the previous two, and alert triaging allows users to override the actions taken for all individual alerts.