Array.sort arguments order changed in Node.js 11

[hudochenkov]

• Version: 11.1.0
• Platform: Darwin hubert.local 18.2.0 Darwin Kernel Version 18.2.0: Fri Oct 5 19:41:49 PDT 2018; root:xnu-4903.221.2~2/RELEASE_X86_64 x86_64 (macOS 10.14.1)
• Subsystem:

Hi!

I've noticed a change with Array.sort(). In Node.js 11 order of arguments passed to compare function is reversed. While in most cases it's not a problem, in some cases it causes problems.

In my project I have quite large compare function for .sort(): https://github.com/hudochenkov/postcss-sorting/blob/944da947a628192b54448368c197f586fbbe0c10/lib/sorting.js#L10-L62. It relies on arguments order. It works in Node.js 4—10. I don't expect anyone to figure out what my function does, and I can't simplify it for this issue report yet.

I created a gist, which shows how arguments get to compare function in Node.js 10 and Node.js 11.

$ npx -p node@10 npx https://gist.github.com/hudochenkov/29b739f8dbdb4aa00a46b953f62dd0a6

a: 1, b: 2
a: 2, b: 3
a: 3, b: 4
[ 1, 2, 3, 4 ]

$ npx -p node@11 npx https://gist.github.com/hudochenkov/29b739f8dbdb4aa00a46b953f62dd0a6

a: 2, b: 1
a: 3, b: 2
a: 4, b: 3
[ 1, 2, 3, 4 ]

Is it a regression or intentional change?

I tried to understand how V8 7.0 changed .sort(), but it's to complex for me :(

[richardlau]

It's intentional: #22754 (comment)

[refack]

Hello @hudochenkov, and thank you for the report.
As you mention, this is a change node get by way of a update V8. There was some discussion on the implication of the new algorithm #22754 (comment), but AFAIK this specific issue was reported for node

/CC @nodejs/v8 (esp. @targos @hashseed @mathiasbynens)

[refack]

P.S. @hudochenkov can you provide some data that using your code sorts differently?

[devsnek]

@hudochenkov stable sort means what if elements in the unsorted array were already in the correct order, they are guaranteed to be in the same order after sorting.

in any case, as long as you always return the correct number for two elements, no matter the order, the engine will properly handle it. if the engine switches the order of the arguments, it will also handle the switched return value.

[hudochenkov]

Thank you for quick replies!

I'll simplify my sorting function as much as possible and will provide examples of how it sorts differently. I'll do it tomorrow.

[refack]

I've forked your gist - https://gist.github.com/refack/8fc2bbdf084f9ad28f900ad5a4f80a14 to uncover the regression:

$ npx -p node@10 npx https://gist.github.com/refack/8fc2bbdf084f9ad28f900ad5a4f80a14

a: { p: 'mottob', id: 1 }, b: { p: 'bottom', id: 2 } - 0
a: { p: 'bottom', id: 2 }, b: { p: 'mottob', id: 3 } - -1
a: { p: 'mottob', id: 3 }, b: { p: 'bottom', id: 4 } - 0
[ { p: 'mottob', id: 1 },
  { p: 'bottom', id: 2 },
  { p: 'mottob', id: 3 },
  { p: 'bottom', id: 4 } ]


$ npx -p node@11 npx https://gist.github.com/refack/8fc2bbdf084f9ad28f900ad5a4f80a14

a: { p: 'bottom', id: 2 }, b: { p: 'mottob', id: 1 } - -1
a: { p: 'mottob', id: 3 }, b: { p: 'bottom', id: 2 } - 0
a: { p: 'mottob', id: 3 }, b: { p: 'mottob', id: 1 } - 0
a: { p: 'bottom', id: 4 }, b: { p: 'mottob', id: 1 } - -1
a: { p: 'bottom', id: 4 }, b: { p: 'bottom', id: 2 } - -1
[ { p: 'bottom', id: 4 },
  { p: 'bottom', id: 2 },
  { p: 'mottob', id: 1 },
  { p: 'mottob', id: 3 } ]

[refack]

simpler code:

const declarations = [
  {p: 'mottob', id: 1},
  {p: 'bottom', id: 2},
  {p: 'mottob', id: 3},
  {p: 'mottob', id: 4},
];

if (process.argv[2] === 'anti' ) {
  declarations.sort((b, a) => {
    const ret = sortDeclarations(a, b);
    console.log(`a: %o, b: %o - %d`, a, b, ret);

    return -ret
  });
} else {
  declarations.sort((a, b) => {
    const ret = sortDeclarations(a, b);
    console.log(`a: %o, b: %o - %d`, a, b, ret);

    return ret
  });
}

console.log(declarations);

function sortDeclarations(a, b) {
  if (b.p === 'bottom') {
    return 1;
  }
  return a.id - b.id;
}

Get me:

D:\code\prws>d:\bin\dev\node\node10.9.0.exe t.js
a: { p: 'mottob', id: 1 }, b: { p: 'bottom', id: 2 } - 1
a: { p: 'mottob', id: 1 }, b: { p: 'mottob', id: 3 } - -2
a: { p: 'mottob', id: 3 }, b: { p: 'mottob', id: 4 } - -1
[ { p: 'bottom', id: 2 },
  { p: 'mottob', id: 1 },
  { p: 'mottob', id: 3 },
  { p: 'mottob', id: 4 } ]

D:\code\prws>d:\bin\dev\node\node11.0.0.exe t.js
a: { p: 'bottom', id: 2 }, b: { p: 'mottob', id: 1 } - 1
a: { p: 'mottob', id: 3 }, b: { p: 'bottom', id: 2 } - 1
a: { p: 'mottob', id: 4 }, b: { p: 'mottob', id: 3 } - 1
[ { p: 'mottob', id: 1 },
  { p: 'bottom', id: 2 },
  { p: 'mottob', id: 3 },
  { p: 'mottob', id: 4 } ]

D:\code\prws>d:\bin\dev\node\node11.0.0.exe t.js anti
a: { p: 'mottob', id: 1 }, b: { p: 'bottom', id: 2 } - 1
a: { p: 'bottom', id: 2 }, b: { p: 'mottob', id: 3 } - -1
a: { p: 'mottob', id: 1 }, b: { p: 'mottob', id: 3 } - -2
a: { p: 'mottob', id: 1 }, b: { p: 'mottob', id: 4 } - -3
a: { p: 'mottob', id: 3 }, b: { p: 'mottob', id: 4 } - -1
[ { p: 'bottom', id: 2 },
  { p: 'mottob', id: 1 },
  { p: 'mottob', id: 3 },
  { p: 'mottob', id: 4 } ]

[mathiasbynens]

• Array#sort is returning the correct result, just like before the change in V8. This report is not about a spec correctness issue.

• The order in which the elements are compared during sorting (and similarly, how many times the comparison function is called in total) is intentionally unspecified, and depends on the exact implementation. When the V8 implementation changed from QuickSort to TimSort, this order changed. But that’s the thing: this order wildly varies across implementations, and even within the same engine it can change at any point; developers shouldn’t rely on it. This is explicitly called out in https://v8.dev/blog/array-sort#accessors-prototype.

This is not a regression; it’s an implementation detail that shouldn’t be relied upon.

[mathiasbynens]

My above comment was in response to the gist in the OP, i.e. https://gist.github.com/hudochenkov/29b739f8dbdb4aa00a46b953f62dd0a6.

@refack, let me respond to your test case now. This program demonstrates something separate from the issue OP reported. The sort callback in this code example is what the spec calls an inconsistent comparison function. For example, assume the following values:

• a = { p: 'x', id: 3 }
• b = { p: 'bottom', id: 4 }

Now, given the way sortDeclarations is written, we can observe the following:

• if you compare a with b, sortDeclarations returns 1
• if you compare b with a, sortDeclarations returns 4 - 3 which is… also 1

The result of a sort with an inconsistent comparison function is implementation-defined, and cannot be relied upon. In other words, this too is WAI.

[hudochenkov]

Thank you for investigation, @refack! And thank you for clarification, @mathiasbynens!

this order wildly varies across implementations, and even within the same engine it can change at any point; developers shouldn’t rely on it.

I guess I was just lucky with my sorting function all these years :) I'm going to rewrite it to be independent of arguments order.