assert: make assertion_error user mysers diff algorithm

Fixes: https://github.com/nodejs/node/issues/51733

Co-Authored-By: Pietro Marchini pietro.marchini94@gmail.com

Why

As discussed in the linked issue, the diff algorithm used to display errors during assertions was a "quick, best-effort implementation." After researching, I found that there aren't many diff algorithms faster than Myers' algorithm, which I’ve implemented in this PR.

How

Following this article on Myers' diff algorithm: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/, I implemented the algorithm. Myers' algorithm is relatively simple, based on a matrix of size N * M, where N is the length of the first string and M is the length of the second string. Although it’s primarily used for string comparison, I’ve adapted it here to handle the results of the assert function.

Differences with the old implementation

In addition to changing the diff algorithm, I also updated the way diffs are displayed:

1. The previous implementation only grouped lines that were unchanged and in close proximity. In the new implementation, I improved how inserted and deleted lines are displayed. only identical inserted or deleted lines will be grouped example:

const assert = require('assert');

const actual = Array(20).fill(1);
const expected = Array(20).fill(2);

assert.deepStrictEqual(actual, expected);

Old implementation:

New implementation:

2. Myers' algorithm excels at finding the minimal changes required to transform one string into another, making it ideal for diffing. example:

const assert = require('assert');

const actual = [
  { a: 1 }, 2, 3, 4, { c: [1, 2, 3] },
];
const expected = [
  { a: 1 }, 2, 3, 4, { c: [3, 4, 5] },
];

assert.deepStrictEqual(actual, expected);

Old implementation:

New implementation:

In this example, the new implementation detects that the element "3" in the array is the same, while the old one treated the entire array as different.

Other example:

const assert = require('assert');

const actual = {
  a: {
    b: {
      c: 1
    }
  }
};
const expected = {
  a: {
    b: {
      c: 1
    },
    d: {
      c: 1
    }
  }
};

assert.strictEqual(actual, expected);

Old implementation:

New implementation:

Another example:

const assert = require('assert');

const actual = {a: ['AAAA', '12345', '6789', 'BC!!!GHI']};
const expected = {a: ['12345', '6789', 'AAAA', 'BC!!!GHI']};

assert.deepStrictEqual(actual, expected);

Old implementation:

New implementation:

3. The ^ indicator is now only displayed for string diffs when there is sufficient space in the terminal and it highlights all differences in the strings.
   example:

const assert = require('assert');

const actual = '123456789ABCDEFGHI';
const expected = '1!3!5!7!9!BC!!!GHI';

assert.strictEqual(actual, expected);

Old implementation:

New implementation:

4. The new implementation is faster than the old one.
5. Standardized spacings, indendations and new lines in the diff output.

Small quirk

Since Myers' algorithm is designed for string comparison, it is not perfect for object comparison out of the box. However, @pmarchini ’s idea addressed this limitation.
In an example like this:

const assert = require('assert');

const actual = {a: [1, 2, 3], b: 2};
const expected = {b: [3, 4, 5], c: 2};

assert.deepStrictEqual(actual, expected);

In this case, the algorithm might incorrectly think the number "3" just moved, when in fact the entire object changed.

Broken implementation:

The solution was simple: in utils/inspect.js, I prepended a special placeholder to each value when handling nested arrays. This placeholder helps the algorithm correctly track parent elements without being visible to the user. The placeholders are removed before displaying the diff, so it appears correctly.

Working implementation: