Specific Array.from(...).sort(...) leads to infinite loop

[StasZelenskiy]

Hello!
Starting from 3.0.0-beta-2002 expression like "Array.from(Root.Inner.Items).sort((a, b) => a.Value === '0001' ? -1 : 1)" causes application hang with high CPU consumption. Looks like infinite loop. See test case below:

[Test]
public void ArrayFromSortTest()
{
    IEnumerable<T> CastBy<T>(IEnumerable sequence, T example) where T : class
    {
        foreach (var o in sequence)
            yield return o as T;
    }

    var item1 = new { Id = "Id1", Value = "0020" };
    var item2 = new { Id = "Id2", Value = "0001" };

    var engine = new Engine();
    engine.SetValue("Root", new { Inner = new { Items = new[] { item1, item2 } } });

    var result = engine.Execute("Array.from(Root.Inner.Items).sort((a, b) => a.Value === '0001' ? -1 : 1)").GetCompletionValue().ToObject();

    var enumerableResult = CastBy(result as IEnumerable, item1).ToList();
    Assert.That(enumerableResult, Has.Exactly(2).Items);
    Assert.That(enumerableResult[0].Id, Is.EqualTo(item2.Id));
    Assert.That(enumerableResult[1].Id, Is.EqualTo(item1.Id));
}

This test case hangs at engine.Execute(...) starting 3.0.0-beta-2002, though it works fine in 3.0.0-beta-1914.

[lahma]

I think this is related to the stable sort change. This only happens on full framework as .NET Core / NET 5> detects the case and stops trying (or something similar).

[StasZelenskiy]

We are using .NET Framework 4.7.2

[lahma]

Your function also gets called with both "Id1" + "Id1" and then "Id1" + "Id2", so seems that the sort algorithm gets into infinite loop. Would it be possible for you to compare always a vs b instead of checking directly a? , for strings this would be (c#) a.CompareTo(b).

[StasZelenskiy]

Sure we can rewrite the expression, but I checked it with the latest DevTools in Chrome and it works fine, so IMO sorting algorithm implementation is broken.

[lahma]

Fair enough, let's keep this issue open and see if we can find a solution.

[AudriusButkevicius]

I've observed this too, my modification to Jint was to cache comparison results in c#, also saves a few round trips to js code.

Effectively as you compare a to b, you cache the result of a, b comparison, and also store negated result for b, a, forcing the comparisons to remain stable.

[lahma]

Checked the .NET source code and Array.Sort seems to check this comparer validity on older runtimes when using DepthLimitedQuickSort. Will throw an error if sorter doesn't yield stable results.

[AudriusButkevicius]

On .net 6 I had exceptions thrown by Array.sort due to unstable sorts, i.e:

(a, b) => {
  if (a.primary) { return 1; }
  If (b.primary) { return -1; }
  return a.score - b.score;
}

As result of a vs b is not the inverse of b vs a if both a and b are primary.

Yet the same sort runs fine in v8/spidermonkey.

[DecusMarkus]

Having this issue on .NET Framework 4.8 and latest version of Jint 3.1.3

Code sample:

sort(function(a, b) { return a.Name == "test" ? -1 : 1; });