DiagnosticCollection.set([Uri, [Diagnostic[]][]) is not reliable

[DustinCampbell]

The documentation for DiagnosticCollection.set([Uri, Diagnostic[]][]) states the following:

Diagnostics of multiple tuples of the same uri will be merged, e.g [[file1, [d1]], [file1, [d2]]] is equivalent to [[file1, [d1, d2]]]. If a diagnostics item is undefined as in [file1, undefined] all previous but not subsequent diagnostics are removed.

However, this doesn't work in practice because the entries end up being sorted by uri, but the sort is not stable. Here's the code that does the sort. This can result in entries being reordered so that this...

[file1, undefined]
[file1, [diagnostic1, diagnostic2]]

...becomes this...

[file1, [diagnostic1, diagnostic2]]
[file1, undefined]

That results in diagnostics being cleared when they aren't supposed to be.

[DustinCampbell]

In the C# extension, I tried sorting entries using the same code as VS Code and could clearly see the impact of not having a stable sort.

Here are the entries before sorting:

Here they are after sorting:

Note that several elements are reversed. These elements have the same uri.

[jrieken]

Awesome find and analysis. @DustinCampbell should have commit rights

[jrieken]

So, that's what you get when you rely on un-specified behaviour... It seems that v8 is especially mean because it uses stable-sorting for small arrays and unstable-sorting for larger arrays.

From here

Small arrays are sorted using a simpler algorithm which happens to be stable.
You need a larger array to trigger the quicksort algorithm which is non-stable.

[DustinCampbell]

Nice fix!

[chrmarti]

Verified by code review and running the test with the fix reverted.