WebKit
diff --git a/‎JSTests/stress/array-sort-inline-boolean-comparator.js‎
Lines changed: 148 additions & 0 deletions b/‎JSTests/stress/array-sort-inline-boolean-comparator.js‎
Lines changed: 148 additions & 0 deletions
diff --git a/‎JSTests/stress/array-sort-inline-closure-comparator.js‎
Lines changed: 38 additions & 0 deletions b/‎JSTests/stress/array-sort-inline-closure-comparator.js‎
Lines changed: 38 additions & 0 deletions
diff --git a/‎JSTests/stress/array-sort-inline-comparator-speculation-exit.js‎
Lines changed: 89 additions & 0 deletions b/‎JSTests/stress/array-sort-inline-comparator-speculation-exit.js‎
Lines changed: 89 additions & 0 deletions
diff --git a/‎JSTests/stress/array-sort-inline-constant-comparator.js‎
Lines changed: 26 additions & 0 deletions b/‎JSTests/stress/array-sort-inline-constant-comparator.js‎
Lines changed: 26 additions & 0 deletions
diff --git a/‎JSTests/stress/array-sort-inline-contiguous.js‎
Lines changed: 43 additions & 0 deletions b/‎JSTests/stress/array-sort-inline-contiguous.js‎
Lines changed: 43 additions & 0 deletions
@@ -0,0 +1,148 @@
+// The DFG ArraySortIntrinsic's inline insertion sort must interpret the comparator
+// result the same way runtime/StableSort.h's coerceComparatorResultToBoolean does:
+//
+//   - Int32: shift iff `< 0`.
+//   - Boolean: shift iff `!result` (true->no shift, false->shift) -- webkit.org/b/47825.
+//   - Other: shift iff `toNumber(result) < 0` (NaN coerces to 0 in V8 but in JSC's
+//     path `NaN < 0` is false, matching StableSort.h's `toNumber() < 0` for NaN).
+//
+// Before the fix the intrinsic did only `cmp < 0`, which gave false for boolean
+// `false` (since 0 < 0 is false), so a `() => false` comparator was a no-op and
+// the legacy `(a, b) => a > b` pattern never sorted. The fix routes `cmp === false`
+// through an extra branch that also goes to the shift target.
+
+function check(got, expected) {
+    if (got.length !== expected.length)
+        throw new Error("length mismatch: " + JSON.stringify(got) + " vs " + JSON.stringify(expected));
+    for (let i = 0; i < expected.length; ++i) {
+        if (!Object.is(got[i], expected[i]))
+            throw new Error("index " + i + " mismatch: " + JSON.stringify(got) + " vs " + JSON.stringify(expected));
+    }
+}
+
+function sortIt(a, c) { return a.sort(c); }
+
+// Warm up with a well-typed Int32 comparator so DFG inlines the intrinsic on the
+// hot doSort path.
+for (let i = 0; i < testLoopCount; ++i)
+    sortIt([5, 3, 1, 4, 2], (a, b) => a - b);
+
+// Expected results are computed via the generic baseline sort on a fresh array
+// (no DFG intrinsic cached state). Matches runtime/StableSort.h exactly.
+function expected(input, cmp) { return [...input].sort(cmp); }
+
+// --- Case A: Int32 comparator (primary fast path). ----------------------------
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    check(sortIt(input.slice(), (a, b) => a - b), [1, 2, 3, 4, 5]);
+    check(sortIt(input.slice(), (a, b) => b - a), [5, 4, 3, 2, 1]);
+}
+
+// Int32 boundary: zero / MIN_VALUE / MAX_VALUE / negative / positive.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    const cmp = (a, b) => {
+        const d = a - b;
+        if (d === 0) return 0;
+        return d < 0 ? -2147483648 : 2147483647;  // extreme Int32s
+    };
+    check(sortIt(input.slice(), cmp), expected(input, cmp));
+}
+
+// --- Case B: Boolean comparator (legacy b/47825 path). -----------------------
+// Constant-false: every comparison is "shift", insertion sort pushes each pivot
+// to the front.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    check(sortIt(input.slice(), () => false), expected(input, () => false));
+}
+
+// Constant-true: every comparison is "no shift", array stays as-is.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    check(sortIt(input.slice(), () => true), expected(input, () => true));
+}
+
+// The real-world legacy pattern: comparator returns a boolean. Both these must
+// end up ascending / descending respectively, matching baseline.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    check(sortIt(input.slice(), (a, b) => a > b), [1, 2, 3, 4, 5]);
+    check(sortIt(input.slice(), (a, b) => a < b), [5, 4, 3, 2, 1]);
+}
+
+// Mixed boolean / int return in a single comparator -- exercises both the
+// CompareLess branch (shift when < 0) and the CompareStrictEq branch (shift when
+// boolean false) in the same sort.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [7, 2, 5, 3, 8, 1, 6, 4, 0, 9];
+    const cmp = (a, b) => {
+        if ((a ^ b) & 1) return a > b;  // boolean
+        return a - b;                   // int32
+    };
+    check(sortIt(input.slice(), cmp), expected(input, cmp));
+}
+
+// --- Case C: Double comparator. --------------------------------------------
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    const cmp = (a, b) => (a - b) + 0.5 - 0.5;  // Double result.
+    check(sortIt(input.slice(), cmp), expected(input, cmp));
+}
+
+// Double edge cases: -0, +0, NaN, Infinity.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    const table = new Map([
+        ['lt', -Infinity],
+        ['gt', Infinity],
+        ['eq', 0],
+        ['negZero', -0],  // -0 < 0 is false per IEEE 754
+        ['nan', NaN],     // NaN < 0 is false
+    ]);
+    for (const [, v] of table) {
+        const cmp = (a, b) => a === b ? 0 : (a < b ? v : -v);
+        check(sortIt(input.slice(), cmp), expected(input, cmp));
+    }
+}
+
+// --- Case D: String comparator. Falls back to toNumber() < 0 path. -----------
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    const cmp = (a, b) => a === b ? "0" : (a < b ? "-1" : "1");
+    check(sortIt(input.slice(), cmp), expected(input, cmp));
+}
+
+// String coerces to NaN → NaN < 0 → false → no shift.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    check(sortIt(input.slice(), () => "abc"), expected(input, () => "abc"));
+}
+
+// --- Case E: null / undefined. ------------------------------------------------
+// toNumber(null) = 0 → 0 < 0 = false → no shift.
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    check(sortIt(input.slice(), () => null), expected(input, () => null));
+    check(sortIt(input.slice(), () => undefined), expected(input, () => undefined));
+}
+
+// --- Case F: Object with valueOf. toPrimitive then toNumber. ------------------
+for (let i = 0; i < testLoopCount; ++i) {
+    const input = [5, 3, 1, 4, 2];
+    const neg = { valueOf() { return -1; } };
+    const pos = { valueOf() { return 1; } };
+    const zero = { valueOf() { return 0; } };
+    // Return objects -- each sort iteration triggers valueOf.
+    check(sortIt(input.slice(), (a, b) => a < b ? neg : a > b ? pos : zero), [1, 2, 3, 4, 5]);
+    check(sortIt(input.slice(), () => neg), expected(input, () => neg));
+}
+
+// --- Case G: BigInt comparator. toNumber throws TypeError. -------------------
+// Both baseline and intrinsic must throw.
+for (let i = 0; i < testLoopCount; ++i) {
+    let threw = false;
+    try { sortIt([5, 3, 1], () => -1n); }
+    catch (e) { threw = e instanceof TypeError; }
+    if (!threw) throw new Error("BigInt comparator must throw TypeError");
+}
@@ -0,0 +1,38 @@
+// Verifies the DFG ArraySortIntrinsic's comparator body-inlining path for a
+// NewArrowFunction / NewFunction closure comparator allocated fresh on every
+// sort call. This is the `.sort((a,b) => a - b)` idiom that every real-world
+// sort caller uses; it's the path the parser-level inliner must detect via
+// Node::isFunctionAllocation().
+
+function test(arr) {
+    arr.sort((a, b) => a - b);
+}
+
+const original = [5, 3, 8, 1, 9, 4, 7, 2, 6, 0, 11, 14, 13, 10, 12, 15];
+const expected = original.slice().sort((a, b) => a - b);
+
+for (let i = 0; i < testLoopCount; i++) {
+    const copy = original.slice();
+    test(copy);
+    for (let j = 0; j < expected.length; j++) {
+        if (copy[j] !== expected[j])
+            throw new Error("iter " + i + " index " + j
+                + ": got " + copy[j] + " expected " + expected[j]);
+    }
+}
+
+// Descending comparator -- separate closure shape, also re-allocated per call.
+function descendingTest(arr) {
+    arr.sort((a, b) => b - a);
+}
+
+const expectedDesc = original.slice().sort((a, b) => b - a);
+for (let i = 0; i < testLoopCount; i++) {
+    const copy = original.slice();
+    descendingTest(copy);
+    for (let j = 0; j < expectedDesc.length; j++) {
+        if (copy[j] !== expectedDesc[j])
+            throw new Error("desc iter " + i + " index " + j
+                + ": got " + copy[j] + " expected " + expectedDesc[j]);
+    }
+}
@@ -0,0 +1,89 @@
+// Verifies that a naturally-occurring OSR exit inside the DFG-inlined comparator
+// (via Int32 speculation failure on ValueSub) recovers correctly and the sort
+// call completes with the right result. The existing
+// array-sort-inline-osr-exit-in-comparator.js uses `$vm.OSRExit()` to force an
+// exit synthetically; this test exercises the same code path that a real-world
+// caller would hit: warm up with Int32 inputs so DFG speculates Int32, then
+// feed doubles and watch the speculation fail mid-sort.
+//
+// The exit lands inside the comparator's inlined body. Per
+// InlineCallFrame::Kind::ArraySortComparatorCall, the comparator's baseline
+// resumes, completes, and returns via arraySortComparatorReturnTrampoline --
+// which discards the return value and re-dispatches the caller's op_call.
+// Baseline then calls sort generically with the correctly-preserved arguments.
+// The observable result must still be a correctly sorted array.
+
+function cmp(a, b) { return a - b; }
+
+function sortIt(a, c) { return a.sort(c); }
+
+function assertSorted(a, reference, label) {
+    if (a.length !== reference.length)
+        throw new Error(label + ": length " + a.length + " vs " + reference.length);
+    for (let i = 0; i < reference.length; ++i) {
+        if (a[i] !== reference[i])
+            throw new Error(label + ": @" + i + " got " + a[i] + " want " + reference[i]);
+    }
+}
+
+// --- Phase 1: warm up with Int32 arrays so DFG inlines sort + inlines the
+// comparator. DFG/FTL will profile `cmp`'s ValueSub as Int32Use.
+const int32Seed = [5, 3, 1, 4, 2, 8, 7, 6, 0, 9, 11, 14, 13, 10, 12, 15];
+const int32Expected = int32Seed.slice().sort(cmp);
+for (let w = 0; w < testLoopCount; ++w)
+    assertSorted(sortIt(int32Seed.slice(), cmp), int32Expected, "warmup int32 " + w);
+
+// --- Phase 2: now feed doubles. The comparator's Int32-speculated ValueSub
+// sees double operands and OSR-exits inside the comparator body. Baseline
+// finishes the comparator and jumps through the trampoline back to op_call,
+// which re-runs sort generically. Each iteration must still produce a
+// correctly sorted array.
+const doubleSeed = [5.5, 3.25, 1.75, 4.5, 2.125, 8.8, 7.1, 6.6, 0.5, 9.9, 11.1, 14.4, 13.3, 10.0, 12.2, 15.5];
+const doubleExpected = doubleSeed.slice().sort(cmp);
+for (let w = 0; w < testLoopCount; ++w)
+    assertSorted(sortIt(doubleSeed.slice(), cmp), doubleExpected, "double " + w);
+
+// --- Phase 3: alternate back to Int32. The call site has tiered back up by
+// now; must still sort correctly.
+for (let w = 0; w < testLoopCount; ++w)
+    assertSorted(sortIt(int32Seed.slice(), cmp), int32Expected, "back-to-int " + w);
+
+// --- Phase 4: mix Int32 and Double in the same array. Each iteration may
+// exit mid-sort as the comparator hits a double.
+const mixedSeed = [5, 3.25, 1, 4.5, 2, 8, 7.1, 0, 6.6, 9];
+const mixedExpected = mixedSeed.slice().sort(cmp);
+for (let w = 0; w < testLoopCount; ++w)
+    assertSorted(sortIt(mixedSeed.slice(), cmp), mixedExpected, "mixed " + w);
+
+// --- Phase 5: arrays of varying size around the 16-element boundary, each
+// with doubles, so the exit fires on both the insertion-sort fast path and
+// (for len > 16) the generic slow path. The array length 1 case is boring
+// (no comparator call) so start at 2.
+for (let len = 2; len <= 20; ++len) {
+    const seed = [];
+    for (let i = 0; i < len; ++i) seed.push((len - i) + 0.5);
+    const expected = seed.slice().sort(cmp);
+    for (let w = 0; w < 100; ++w)
+        assertSorted(sortIt(seed.slice(), cmp), expected, "len " + len + " w " + w);
+}
+
+// --- Phase 6: comparator that throws inside the inlined body. If OSR exit
+// handling is wrong, the exception might propagate from the wrong frame or
+// the sort call may appear to return a value (and spread would then crash,
+// which is the WebGPU bug we started from). Here we just assert the thrown
+// error is observed intact at the caller.
+let shouldThrow = false;
+function throwingCmp(a, b) {
+    if (shouldThrow)
+        throw new Error("boom");
+    return a - b;
+}
+// Warm up so the comparator is inlined.
+for (let w = 0; w < testLoopCount; ++w) sortIt([3, 1, 2], throwingCmp);
+
+shouldThrow = true;
+let threw = false;
+try { sortIt([5, 3, 1, 4, 2], throwingCmp); }
+catch (e) { threw = e.message === "boom"; }
+if (!threw)
+    throw new Error("throwing comparator did not propagate through the sort");
@@ -0,0 +1,26 @@
+// Verifies the DFG ArraySortIntrinsic's comparator body-inlining path when
+// the comparator is a constant JSFunction (named global / hoisted) rather
+// than a closure. The parser detects this via Node::hasConstant() +
+// dynamicCastConstant<JSFunction*>() and routes through handleCall with
+// CallLinkStatus(CallVariant(function)).
+
+function cmp(a, b) {
+    return a - b;
+}
+
+function test(arr) {
+    arr.sort(cmp);
+}
+
+const original = [5, 3, 8, 1, 9, 4, 7, 2, 6, 0, 11, 14, 13, 10, 12, 15];
+const expected = original.slice().sort(cmp);
+
+for (let i = 0; i < testLoopCount; i++) {
+    const copy = original.slice();
+    test(copy);
+    for (let j = 0; j < expected.length; j++) {
+        if (copy[j] !== expected[j])
+            throw new Error("iter " + i + " index " + j
+                + ": got " + copy[j] + " expected " + expected[j]);
+    }
+}
@@ -0,0 +1,43 @@
+// Verifies the DFG ArraySortIntrinsic's fast path handles ArrayWithContiguous arrays -- arrays
+// whose elements include non-Int32 values (doubles, strings, objects).
+
+function sortIt(a, cmp) { return a.sort(cmp); }
+
+// Contiguous (mixed-type) arrays: objects.
+{
+    const input = [{v:5},{v:3},{v:1},{v:4},{v:2}];
+    const expected = [1,2,3,4,5];
+    for (let w = 0; w < testLoopCount; w++) {
+        const a = input.slice();
+        const r = sortIt(a, (x, y) => x.v - y.v);
+        for (let i = 0; i < 5; i++)
+            if (r[i].v !== expected[i])
+                throw new Error("iter " + w + " index " + i + ": got " + r[i].v + " expected " + expected[i]);
+    }
+}
+
+// Contiguous (strings).
+{
+    const input = ["dd", "bb", "aa", "cc"];
+    const expected = ["aa", "bb", "cc", "dd"];
+    for (let w = 0; w < testLoopCount; w++) {
+        const a = input.slice();
+        const r = sortIt(a, (x, y) => x < y ? -1 : x > y ? 1 : 0);
+        for (let i = 0; i < 4; i++)
+            if (r[i] !== expected[i])
+                throw new Error("iter " + w + " index " + i + ": got " + r[i] + " expected " + expected[i]);
+    }
+}
+
+// Contiguous (doubles stored via contiguous indexing since allocated from literal with ints then a double).
+{
+    const input = [3.5, 1.2, 2.8, 0.4];
+    const expected = [0.4, 1.2, 2.8, 3.5];
+    for (let w = 0; w < testLoopCount; w++) {
+        const a = input.slice();
+        const r = sortIt(a, (x, y) => x - y);
+        for (let i = 0; i < 4; i++)
+            if (r[i] !== expected[i])
+                throw new Error("iter " + w + " index " + i + ": got " + r[i] + " expected " + expected[i]);
+    }
+}