v8/test/mjsunit/array-sort-inline.js

// Copyright 2025 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Flags: --allow-natives-syntax --maglev

// Tests for the compiler-inlined insertion sort of Array.prototype.sort.
// Both Maglev and Turbofan inline a small insertion sort for PACKED arrays
// with a provided comparefn and length <= 8.  Larger arrays fall through
// to the generic PowerSort builtin.  These tests are tier-neutral; the test
// runner variants exercise both compiler tiers.

// ---------------------------------------------------------------------------
// Helpers
// ---------------------------------------------------------------------------

function opt(fn) {
  %PrepareFunctionForOptimization(fn);
  fn();
  %OptimizeFunctionOnNextCall(fn);
  fn();
}
%NeverOptimizeFunction(opt);

function optWith(fn, ...args) {
  %PrepareFunctionForOptimization(fn);
  fn(...args);
  %OptimizeFunctionOnNextCall(fn);
  return fn(...args);
}
%NeverOptimizeFunction(optWith);

// =========================================================================
// 1. PACKED_SMI_ELEMENTS — basic sorting
// =========================================================================

(function TestSmiAscending() {
  const cmp = (a, b) => a - b;
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
})();

(function TestSmiDescending() {
  const cmp = (a, b) => b - a;
  function f() { return [1, 2, 3, 4, 5].sort(cmp); }
  opt(f);
  assertEquals([5, 4, 3, 2, 1], f());
})();

(function TestSmiAlreadySorted() {
  const cmp = (a, b) => a - b;
  function f() { return [1, 2, 3, 4, 5, 6, 7, 8].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8], f());
})();

(function TestSmiReversed8() {
  const cmp = (a, b) => a - b;
  function f() { return [8, 7, 6, 5, 4, 3, 2, 1].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8], f());
})();

(function TestSmiAllEqual() {
  const cmp = (a, b) => a - b;
  function f() { return [7, 7, 7, 7, 7].sort(cmp); }
  opt(f);
  assertEquals([7, 7, 7, 7, 7], f());
})();

(function TestSmiDuplicates() {
  const cmp = (a, b) => a - b;
  function f() { return [3, 1, 4, 1, 5, 9, 2, 6].sort(cmp); }
  opt(f);
  assertEquals([1, 1, 2, 3, 4, 5, 6, 9], f());
})();

(function TestSmiNegative() {
  const cmp = (a, b) => a - b;
  function f() { return [-3, 0, 5, -1, 2].sort(cmp); }
  opt(f);
  assertEquals([-3, -1, 0, 2, 5], f());
})();

// =========================================================================
// 2. PACKED_DOUBLE_ELEMENTS
// =========================================================================

(function TestDoubleSort() {
  const cmp = (a, b) => a - b;
  function f() { return [5.5, 3.3, 1.1, 2.2].sort(cmp); }
  opt(f);
  assertEquals([1.1, 2.2, 3.3, 5.5], f());
})();

// =========================================================================
// 3. Boundary lengths
// =========================================================================

(function TestEmpty() {
  const cmp = (a, b) => a - b;
  function f() { return [].sort(cmp); }
  opt(f);
  assertEquals([], f());
})();

(function TestSingleElement() {
  const cmp = (a, b) => a - b;
  function f() { return [42].sort(cmp); }
  opt(f);
  assertEquals([42], f());
})();

(function TestTwoElements() {
  const cmp = (a, b) => a - b;
  function f() { return [2, 1].sort(cmp); }
  opt(f);
  assertEquals([1, 2], f());
})();

(function TestTwoElementsAlreadySorted() {
  const cmp = (a, b) => a - b;
  function f() { return [1, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2], f());
})();

(function TestThreeElementPermutations() {
  const cmp = (a, b) => a - b;
  function f1() { return [1, 2, 3].sort(cmp); }
  function f2() { return [1, 3, 2].sort(cmp); }
  function f3() { return [2, 1, 3].sort(cmp); }
  function f4() { return [2, 3, 1].sort(cmp); }
  function f5() { return [3, 1, 2].sort(cmp); }
  function f6() { return [3, 2, 1].sort(cmp); }
  for (const f of [f1, f2, f3, f4, f5, f6]) {
    opt(f);
    assertEquals([1, 2, 3], f());
  }
})();

// =========================================================================
// 4. Fast/slow path boundary (kMaxInlineSortSize = 8)
// =========================================================================

(function TestExactly8() {
  const cmp = (a, b) => a - b;
  function f() { return [8, 4, 6, 2, 7, 1, 5, 3].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8], f());
})();

(function TestSlowPath9() {
  const cmp = (a, b) => a - b;
  function f() { return [9, 8, 7, 6, 5, 4, 3, 2, 1].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8, 9], f());
})();

(function TestSlowPathLarge() {
  const cmp = (a, b) => a - b;
  function f() {
    const a = Array.from({length: 50}, (_, i) => 50 - i);
    a.sort(cmp);
    return a;
  }
  opt(f);
  assertEquals(Array.from({length: 50}, (_, i) => i + 1), f());
})();

// Mixed: optimized function sees both fast and slow path arrays at runtime.
(function TestMixedLengths() {
  const cmp = (a, b) => a - b;
  function f(arr) { return arr.sort(cmp); }
  optWith(f, [3, 1, 2]);
  assertEquals([1, 2, 3], f([3, 1, 2]));
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8, 9],
               f([9, 8, 7, 6, 5, 4, 3, 2, 1]));
  assertEquals([1, 2, 3], f([3, 1, 2]));
})();

// =========================================================================
// 5. PACKED_ELEMENTS (tagged objects)
// =========================================================================

(function TestObjectsByProperty() {
  const cmp = (a, b) => a.v - b.v;
  function f() {
    return [{v: 3}, {v: 1}, {v: 2}].sort(cmp);
  }
  opt(f);
  assertEquals([1, 2, 3], f().map(x => x.v));
})();

(function TestStringsCustomComparator() {
  const cmp = (a, b) => a.length - b.length;
  function f() {
    return ["ccc", "a", "bb", "dddd", "ee"].sort(cmp);
  }
  opt(f);
  assertEquals(["a", "bb", "ee", "ccc", "dddd"], f());
})();

(function TestStringsLexicographic() {
  function cmp(a, b) { return a < b ? -1 : a > b ? 1 : 0; }
  %PrepareFunctionForOptimization(cmp);
  function f() {
    return ['cherry', 'apple', 'banana'].sort(cmp);
  }
  opt(f);
  assertEquals(['apple', 'banana', 'cherry'], f());
})();

// =========================================================================
// 6. sort() returns the same array object
// =========================================================================

(function TestReturnsSameArray() {
  const cmp = (a, b) => a - b;
  let arr;
  function f() {
    arr = [3, 1, 2];
    return arr.sort(cmp);
  }
  opt(f);
  assertTrue(f() === arr);
})();

(function TestSlowPathReturnsSameArray() {
  const cmp = (a, b) => a - b;
  let arr;
  function f() {
    arr = [9, 8, 7, 6, 5, 4, 3, 2, 1];
    return arr.sort(cmp);
  }
  opt(f);
  assertTrue(f() === arr);
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8, 9], arr);
})();

// =========================================================================
// 7. Comparefn edge cases
// =========================================================================

// comparefn always returns 0: stable sort preserves original order.
(function TestComparefnAlwaysZero() {
  const cmp = (a, b) => 0;
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([5, 3, 1, 4, 2], f());
})();

// comparefn returns fractional values.
(function TestComparefnFractional() {
  const cmp = (a, b) => (a - b) / 100.0;
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
})();

// comparefn returns very large / very small values.
(function TestComparefnLargeValues() {
  const cmp = (a, b) => (a < b) ? -1e15 : (a > b) ? 1e15 : 0;
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
})();

// comparefn that calls a helper function (tests inlining / call handling).
(function TestComparefnWithCalls() {
  function getRank(x) { return x; }
  %NeverOptimizeFunction(getRank);
  function cmp(a, b) { return getRank(a) - getRank(b); }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3], f());
})();

// comparefn with localeCompare (method call inside comparefn).
(function TestComparefnLocaleCompare() {
  function cmp(a, b) { return a.localeCompare(b); }
  %PrepareFunctionForOptimization(cmp);
  function f() { return ['cherry', 'apple', 'banana'].sort(cmp); }
  opt(f);
  assertEquals(['apple', 'banana', 'cherry'], f());
})();

// =========================================================================
// 8. Stability: insertion sort preserves relative order of equal keys.
// =========================================================================

(function TestStability() {
  const cmp = (a, b) => a.group - b.group;
  function f() {
    return [
      {group: 2, id: "a"},
      {group: 1, id: "b"},
      {group: 2, id: "c"},
      {group: 1, id: "d"},
      {group: 3, id: "e"},
    ].sort(cmp);
  }
  opt(f);
  const r = f();
  assertEquals([1, 1, 2, 2, 3], r.map(x => x.group));
  assertEquals(["b", "d", "a", "c", "e"], r.map(x => x.id));
})();

// =========================================================================
// 9. Snapshot semantics: comparefn side effects on the receiver should not
//    affect the sort result (temp array isolates the sort).
//    These tests may deopt; we only assert correctness, not tier.
// =========================================================================

(function TestComparefnModifiesElements() {
  const cmp = (a, b) => a - b;
  function f(arr) { return arr.sort(cmp); }
  optWith(f, [3, 1, 2]);
  // Now call with a mutating comparefn: copy-back overwrites mutations.
  let arr = [3, 1, 2];
  arr.sort((a, b) => { arr[0] = 99; return a - b; });
  assertEquals([1, 2, 3], arr);
})();

// =========================================================================
// 10. Length-change guard: comparefn that changes array length should
//     deopt and produce a valid result without crashing.
// =========================================================================

(function TestComparefnShrinksArray() {
  const cmp = (a, b) => a - b;
  function f(arr, c) { return arr.sort(c); }
  optWith(f, [3, 1, 2], cmp);
  let arr = [5, 3, 1, 4, 2];
  f(arr, (a, b) => { if (arr.length > 2) arr.length = 2; return a - b; });
  assertTrue(arr.length <= 5);
})();

(function TestComparefnGrowsArray() {
  const cmp = (a, b) => a - b;
  function f(arr, c) { return arr.sort(c); }
  optWith(f, [3, 1, 2], cmp);
  let arr = [5, 3, 1];
  let grew = false;
  f(arr, (a, b) => { if (!grew) { arr.push(99); grew = true; } return a - b; });
  // Must not crash.
})();

// =========================================================================
// 11. Comparefn `this` is undefined (called with ConvertReceiverMode::kAny).
// =========================================================================

(function TestComparefnThisIsUndefined() {
  "use strict";
  let observed_this;
  const cmp = function(a, b) { observed_this = this; return a - b; };
  function f() {
    observed_this = "sentinel";
    return [2, 1].sort(cmp);
  }
  opt(f);
  f();
  assertEquals(undefined, observed_this);
})();

// =========================================================================
// 12. Comparefn arguments are from the array.
// =========================================================================

(function TestComparefnArguments() {
  let recorded = [];
  const cmp = (a, b) => { recorded.push([a, b]); return a - b; };
  function f() {
    recorded = [];
    return [3, 1, 2].sort(cmp);
  }
  opt(f);
  f();
  for (const [a, b] of recorded) {
    assertTrue([1, 2, 3].includes(a), "a=" + a + " not in array");
    assertTrue([1, 2, 3].includes(b), "b=" + b + " not in array");
  }
})();

// =========================================================================
// 13. Repeated sorting of the same array.
// =========================================================================

(function TestRepeatedSort() {
  const cmp = (a, b) => a - b;
  let arr = [5, 3, 1, 4, 2];
  function f() { return arr.sort(cmp); }
  opt(f);
  for (let i = 0; i < 10; i++) {
    f();
    assertEquals([1, 2, 3, 4, 5], arr);
  }
})();

// =========================================================================
// 14. Comparefn that allocates (may trigger GC, moving elements pointers).
// =========================================================================

(function TestComparefnTriggersGC() {
  let garbage = [];
  const cmp = (a, b) => {
    garbage.push({x: a, y: b, z: new Array(100)});
    return a - b;
  };
  function f() {
    garbage = [];
    return [8, 4, 6, 2, 7, 1, 5, 3].sort(cmp);
  }
  opt(f);
  assertEquals([1, 2, 3, 4, 5, 6, 7, 8], f());
})();

// =========================================================================
// 15. Comparefn result type: int32 / Smi / float64 paths.
// =========================================================================

// comparefn returns a raw int32 via a bitwise op.  Bitwise operations in
// Maglev always produce an untagged int32 node, so TryGetInt32 on the
// inlined return value succeeds directly (path 1, no Smi-untag needed).
(function TestComparefnReturnsInt32() {
  // (a - b) | 0 forces the result to be an untagged int32 in the graph.
  const cmp = (a, b) => (a - b) | 0;
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
})();

// comparefn returns -1/0/1 Smi literals.  Type feedback marks the return
// as NodeType::kSmi, exercising the UnsafeSmiUntag fast path.
(function TestComparefnReturnsSmi() {
  function cmp(a, b) { return a < b ? -1 : a > b ? 1 : 0; }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
})();

// Same on a double array: elements are float64 but the comparefn result
// is still a Smi, so the Smi path is taken for the comparison.
(function TestComparefnReturnsSmiDoubleArray() {
  function cmp(a, b) { return a < b ? -1 : a > b ? 1 : 0; }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [5.5, 3.3, 1.1, 4.4, 2.2].sort(cmp); }
  opt(f);
  assertEquals([1.1, 2.2, 3.3, 4.4, 5.5], f());
})();

// comparefn returns NaN.  NaN is not representable as int32/Smi, so the
// float64 fallback is taken.  NaN < 0.0 is false, so NaN is treated as
// >= 0 (equal), and the stable sort preserves the original order.
(function TestComparefnReturnsNaN() {
  const cmp = () => NaN;
  function f() { return [5, 3, 1, 4, 2].sort(cmp); }
  opt(f);
  assertEquals([5, 3, 1, 4, 2], f());
})();

// comparefn returns float (fractional), exercising the float64 fallback
// on a double array.
(function TestComparefnReturnsFloatDoubleArray() {
  const cmp = (a, b) => (a - b) / 100.0;
  function f() { return [5.5, 3.3, 1.1, 4.4, 2.2].sort(cmp); }
  opt(f);
  assertEquals([1.1, 2.2, 3.3, 4.4, 5.5], f());
})();

// =========================================================================
// 16. Deopt mid-sort restarts correctly.
// =========================================================================

(function TestDeoptRestartsSort() {
  let triggerDeopt = false;
  function cmpDeopt(a, b) {
    if (triggerDeopt) %DeoptimizeFunction(sortDeopt);
    return a - b;
  }
  %PrepareFunctionForOptimization(cmpDeopt);
  function sortDeopt() { return [4, 2, 3, 1].sort(cmpDeopt); }
  opt(sortDeopt);
  assertEquals([1, 2, 3, 4], sortDeopt());

  // Trigger deopt: result must still be correct.
  triggerDeopt = true;
  assertEquals([1, 2, 3, 4], sortDeopt());
})();

// =========================================================================
// 17. Comparefn edge cases: undefined and non-callable.
// =========================================================================

// sort(undefined) is equivalent to sort() per spec (ECMA-262 §23.1.3.30
// step 1: "If comparefn is not undefined, ...").  Must NOT throw TypeError.
(function TestSortUndefinedComparefn() {
  function f() { return [10, 9, 2, 1].sort(undefined); }
  opt(f);
  // Default string comparison: "1" < "10" < "2" < "9".
  assertEquals([1, 10, 2, 9], f());
})();

// sort(nonCallable) must throw TypeError per spec, even from optimized code.
(function TestSortNonCallableComparefn() {
  let cmp = (a, b) => a - b;
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  cmp = 42;
  assertThrows(f, TypeError);
})();

// =========================================================================
// 18. Comparefn that throws.
// =========================================================================

// comparefn throws on first call from optimized code.
(function TestComparefnThrowsImmediately() {
  let shouldThrow = false;
  function cmp(a, b) {
    if (shouldThrow) throw new Error("boom");
    return a - b;
  }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3], f());
  shouldThrow = true;
  assertThrows(f, Error);
})();

// comparefn throws after a few successful comparisons.
(function TestComparefnThrowsLater() {
  let count = 0;
  let limit = Infinity;
  function cmp(a, b) {
    if (++count > limit) throw new RangeError("too many");
    return a - b;
  }
  %PrepareFunctionForOptimization(cmp);
  function f() {
    count = 0;
    return [5, 3, 1, 4, 2].sort(cmp);
  }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
  limit = 2;
  assertThrows(f, RangeError);
})();

// Non-inlined comparefn that throws (not folded to unconditional deopt).
(function TestComparefnThrowsNotInlined() {
  let shouldThrow = false;
  function cmp(a, b) {
    if (shouldThrow) throw new Error("boom");
    return a - b;
  }
  %PrepareFunctionForOptimization(cmp);
  %NeverOptimizeFunction(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3], f());
  shouldThrow = true;
  assertThrows(f, Error);
})();

// Non-inlined comparefn that throws after a few comparisons.
(function TestComparefnThrowsLaterNotInlined() {
  let count = 0;
  let limit = Infinity;
  function cmp(a, b) {
    if (++count > limit) throw new RangeError("too many");
    return a - b;
  }
  %PrepareFunctionForOptimization(cmp);
  %NeverOptimizeFunction(cmp);
  function f() {
    count = 0;
    return [5, 3, 1, 4, 2].sort(cmp);
  }
  opt(f);
  assertEquals([1, 2, 3, 4, 5], f());
  limit = 2;
  assertThrows(f, RangeError);
})();

// Throw from comparefn caught inside the sorting function — verify the
// exception is wired to the correct catch handler.  We also throw during
// feedback collection so that Maglev doesn't eliminate the catch handler.
(function TestComparefnThrowsWithCatchHandler() {
  let shouldThrow = false;
  function cmp(a, b) {
    if (shouldThrow) throw new Error("caught");
    return a - b;
  }
  %PrepareFunctionForOptimization(cmp);
  function f() {
    try {
      return [5, 3, 1, 4, 2].sort(cmp);
    } catch (e) {
      return e.message;
    }
  }
  // Collect feedback with a throw so the catch handler gets feedback.
  shouldThrow = true;
  %PrepareFunctionForOptimization(f);
  assertEquals("caught", f());
  shouldThrow = false;
  %PrepareFunctionForOptimization(f);
  f();
  %OptimizeFunctionOnNextCall(f);
  assertEquals([1, 2, 3, 4, 5], f());
  shouldThrow = true;
  assertEquals("caught", f());
})();

// =========================================================================
// 19. Comparefn returns non-number.
// =========================================================================

// comparefn returns a string — ToNumber conversion applies.
(function TestComparefnReturnsString() {
  function cmp(a, b) { return String(a - b); }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3], f());
})();

// comparefn returns undefined — treated as NaN, which is >= 0 (no swap).
(function TestComparefnReturnsUndefined() {
  function cmp(a, b) { return undefined; }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  // undefined -> NaN -> NaN < 0 is false -> stable (no swaps).
  assertEquals([3, 1, 2], f());
})();

// comparefn returns a boolean — true coerces to 1 (> 0), false to 0 (>= 0).
(function TestComparefnReturnsBoolean() {
  function cmp(a, b) { return a > b; }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  // true -> 1 -> swap; false -> 0 -> no swap.  Insertion sort on [3,1,2]:
  //   i=1: cmp(1,3) -> false(0) -> no swap -> [3,1,2]
  //   i=2: cmp(2,1) -> true(1) -> no swap; cmp(2,3) -> false(0) -> no swap
  //   Result depends on insertion sort specifics, just check no crash.
  assertEquals(3, f().length);
})();

// comparefn returns an object with valueOf — ToNumber applies.
(function TestComparefnReturnsObject() {
  function cmp(a, b) { return { valueOf() { return a - b; } }; }
  %PrepareFunctionForOptimization(cmp);
  function f() { return [3, 1, 2].sort(cmp); }
  opt(f);
  assertEquals([1, 2, 3], f());
})();

// =========================================================================
// 19. Non-inlined comparator (builtin / constructor / bound function)
// =========================================================================

// These exercise the path where the comparefn is callable but is NOT a
// user-defined JSFunction the inliner picks up — so the JSCall to comparefn
// stays generic.  All previous tests use `cmp = (a, b) => ...` which gets
// inlined; this section covers the alternative path that originally tripped
// crbug/502439789.

// Array constructor as comparator on PACKED_ELEMENTS.  Returns an array,
// which ToNumber coerces to NaN, so the sort order is unspecified — we just
// require that the call doesn't crash and the result has the right length.
(function TestPackedElementsBuiltinCmp() {
  function f() { return ['c', 'a', 'b'].sort(Array); }
  opt(f);
  assertEquals(3, f().length);
})();

// Same, with PACKED_SMI_ELEMENTS — verifies the SMI path doesn't crash even
// though it doesn't take the same TF reduction the bug originally hit.
(function TestPackedSmiBuiltinCmp() {
  function f() { return [3, 1, 2].sort(Array); }
  opt(f);
  assertEquals(3, f().length);
})();

// Math.max as comparator: returns a real number, so sort ordering is the
// max(a, b) of the two args (always >= 0), which causes a stable-ish order.
// Main goal: exercise SpeculativeToNumber on a Number return value with a
// non-inlined cmp.
(function TestMathMaxCmp() {
  function f() { return ['c', 'a', 'b'].sort(Math.max); }
  opt(f);
  assertEquals(3, f().length);
})();

// Length 0: copy loops have zero trip count.
(function TestEmptyArrayBuiltinCmp() {
  function f() { return [].sort(Array); }
  opt(f);
  assertEquals([], f());
})();

// Length exactly kMaxInlineSortLength (16): boundary of the fast path.
(function TestMaxInlineLengthBuiltinCmp() {
  const a = ['p', 'o', 'n', 'm', 'l', 'k', 'j', 'i',
             'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'];
  function f() { return a.slice().sort(Array); }
  opt(f);
  assertEquals(16, f().length);
})();

// Comparator that throws on first invocation: exercises the deferred
// throw / Unreachable continuation path that originally hit the DCHECK
// (the failing block in the regression-test trace was on this path).
(function TestThrowingCmp() {
  function badCmp() { throw new Error('boom'); }
  function f() {
    try {
      ['c', 'a', 'b'].sort(badCmp);
      return 'no-throw';
    } catch (e) {
      return e.message;
    }
  }
  opt(f);
  assertEquals('boom', f());
})();

// Comparator that mutates the receiver (length change): verifies the
// post-loop MaybeInsertMapChecks + CheckIf(length unchanged) deopt
// continuations.  The sort operates on a temp copy, so the mutation does
// NOT affect the sort order itself, but the post-sort length check should
// trip on the changed length.
(function TestReceiverMutatingCmp() {
  let arr;
  function mutate(a, b) { arr.length = 1; return 0; }
  function f() {
    arr = ['c', 'a', 'b'];
    arr.sort(mutate);
    return arr.length;
  }
  // Don't assert an exact length — the result depends on whether the
  // length-changed deopt fires before or after the mutating cmp call.
  // We just want to exercise the path without crashing.
  opt(f);
  f();
})();


// =========================================================================
// 20. Spec compliance: deopts during cmp must preserve permutation invariant
// =========================================================================
//
// ECMA-262 23.1.3.30: Array.prototype.sort takes a snapshot of the
// receiver's elements into _items_, sorts _items_ via comparefn, then
// writes _items_ back to the receiver.  Mutations of the receiver
// performed by comparefn are overwritten by the writeback, so the final
// array is always a permutation of the original elements.
//
// The inlined sort copies elements into a temp array before any cmp call.
// If a deopt fires during cmp, the deopt continuation must hand that
// snapshot to the generic sort -- re-reading the (possibly mutated)
// receiver would let cmp's side effects leak into the final result.

// Each test drives optimization with PrepareForOptimization+OptimizeOnNextCall
// on both `f` and `cmp` (so that cmp is inlined into f and the sort reduction
// fires), then triggers a deopt during cmp via the polymorphic-load technique
// or %DeoptimizeFunction.  All tests assert the ECMA-262 23.1.3.30 invariant:
// the final array is a permutation of the original elements.

// Polymorphic load: monomorphic on Smi map at warmup; flipping `mode` makes
// the IC miss, which is enough to deopt the surrounding optimized code.
const ic_obj_smi = { x: 1 };
const ic_obj_dbl = { x: 1.5 };
let deopt_mode = 0;
function readICX() {
  return (deopt_mode === 0 ? ic_obj_smi : ic_obj_dbl).x;
}

// Returns true iff `arr` is a permutation of `original` (multiset equal).
function isPermutation(arr, original) {
  if (arr.length !== original.length) return false;
  const a = arr.slice(), b = original.slice();
  a.sort((x, y) => (x < y ? -1 : x > y ? 1 : 0));
  b.sort((x, y) => (x < y ? -1 : x > y ? 1 : 0));
  for (let i = 0; i < a.length; ++i) if (a[i] !== b[i]) return false;
  return true;
}
%NeverOptimizeFunction(isPermutation);

// cmp mutates arr[0] on every call.  After flipping deopt_mode, the IC miss
// inside cmp's call to readICX deopts the outer optimized f mid-sort.  The
// final array must remain a permutation of the original; the mutation value
// must not appear in the result.
(function TestDeoptCmpKeepsPermutation() {
  let arr;
  function cmp(a, b) { arr[0] = 99; return a - b + readICX() - readICX(); }
  function f() {
    arr = [3, 1, 2];
    arr.sort(cmp);
    return arr;
  }
  %PrepareFunctionForOptimization(cmp);
  %PrepareFunctionForOptimization(f);
  deopt_mode = 0;
  f(); f();
  %OptimizeFunctionOnNextCall(f);
  %OptimizeFunctionOnNextCall(cmp);
  deopt_mode = 1;
  f();
  assertTrue(isPermutation(arr, [3, 1, 2]),
              "got " + JSON.stringify(arr));
  assertEquals(-1, arr.indexOf(99),
                "value 99 must not leak; got " + JSON.stringify(arr));
})();

// Worst-case reverse-sorted input forces every shift in the inner loop, so
// many cmp calls happen with temp_array mid-shift (pivot in register only).
// The deopt continuation must recover from any of these states.  The
// counter delays the polymorphic-load deopt to cmp call #N >= 3, so the
// deopt fires inside outer iter i=2's inner loop AFTER a shift has run
// (the "pivot-loss" state in the absence of the pivot-restore fix).
let pivot_loss_counter = 0;
(function TestDeoptCmpKeepsPermutationLong() {
  let arr;
  function cmp(a, b) {
    pivot_loss_counter++;
    arr[0] = 999;
    let k = 0;
    // Trigger the polymorphic-load deopt only on cmp call #3 onward.  For
    // input [5,4,3,2,1] the call schedule is:
    //   #1: iter i=1, j=0  (pre-shift)
    //   #2: iter i=2, j=1  (pre-shift in this outer iter)
    //   #3: iter i=2, j=0  (POST-shift -- pivot only in register pre-fix)
    if (pivot_loss_counter >= 3) k = readICX();
    return a - b + k - k;
  }
  function f() {
    pivot_loss_counter = 0;
    arr = [5, 4, 3, 2, 1];
    arr.sort(cmp);
    return arr;
  }
  %PrepareFunctionForOptimization(cmp);
  %PrepareFunctionForOptimization(f);
  deopt_mode = 0;
  f(); f();
  %OptimizeFunctionOnNextCall(f);
  %OptimizeFunctionOnNextCall(cmp);
  deopt_mode = 1;
  f();
  assertTrue(isPermutation(arr, [5, 4, 3, 2, 1]),
              "got " + JSON.stringify(arr));
  assertEquals(-1, arr.indexOf(999),
                "value 999 must not leak; got " + JSON.stringify(arr));
})();

// String value introduced by cmp must not appear in the result -- a leak
// is detectable by type alone (the original array contains only numbers).
(function TestDeoptCmpLeakedStringDoesNotAppear() {
  let arr;
  function cmp(a, b) {
    arr[1] = "INVADER";
    return a - b + readICX() - readICX();
  }
  function f() {
    arr = [3, 1, 2];
    arr.sort(cmp);
    return arr;
  }
  %PrepareFunctionForOptimization(cmp);
  %PrepareFunctionForOptimization(f);
  deopt_mode = 0;
  f(); f();
  %OptimizeFunctionOnNextCall(f);
  %OptimizeFunctionOnNextCall(cmp);
  deopt_mode = 1;
  f();
  for (let i = 0; i < arr.length; ++i) {
    assertEquals("number", typeof arr[i],
                  "non-number at " + i + ": " + JSON.stringify(arr));
  }
})();

// cmp grows the receiver mid-sort.  Positions [0, originalLength) must be a
// permutation of the snapshot; the pushed element may remain at its new
// position depending on when the deopt fires.
(function TestDeoptCmpGrowsReceiver() {
  let arr;
  function cmp(a, b) {
    if (arr.length === 3) arr.push(100);
    return a - b + readICX() - readICX();
  }
  function f() {
    arr = [3, 1, 2];
    arr.sort(cmp);
    return arr;
  }
  %PrepareFunctionForOptimization(cmp);
  %PrepareFunctionForOptimization(f);
  deopt_mode = 0;
  f(); f();
  %OptimizeFunctionOnNextCall(f);
  %OptimizeFunctionOnNextCall(cmp);
  deopt_mode = 1;
  f();
  assertTrue(isPermutation(arr.slice(0, 3), [3, 1, 2]),
              "positions 0..2 must be a permutation; got " +
              JSON.stringify(arr));
})();

// cmp shrinks the receiver mid-sort.  The spec captures len at the start
// of sort and writes that many elements back, re-extending the array if it
// was truncated.
(function TestDeoptCmpShrinksReceiver() {
  let arr;
  function cmp(a, b) {
    if (arr.length === 4) arr.length = 1;
    return a - b + readICX() - readICX();
  }
  function f() {
    arr = [4, 3, 2, 1];
    arr.sort(cmp);
    return arr;
  }
  %PrepareFunctionForOptimization(cmp);
  %PrepareFunctionForOptimization(f);
  deopt_mode = 0;
  f(); f();
  %OptimizeFunctionOnNextCall(f);
  %OptimizeFunctionOnNextCall(cmp);
  deopt_mode = 1;
  f();
  assertTrue(isPermutation(arr.slice(0, 4), [4, 3, 2, 1]),
              "positions 0..3 must be a permutation; got " +
              JSON.stringify(arr));
})();

// PACKED_ELEMENTS containing Undefined: CompareArrayElements
// (ECMA-262 23.1.3.30) requires Undefined values to sort to the end
// without invoking the comparator.  The inlined insertion sort cannot
// honor this special-case, so the reduction bails out at copy-in time
// when an Undefined is detected.  The first call after tier-up deopts;
// subsequent re-tiers do not re-inline the sort.
(function TestUndefinedInPackedElementsBailsOut() {
  let saw_undef_in_cmp = false;
  function cmp(a, b) {
    if (a === undefined || b === undefined) saw_undef_in_cmp = true;
    return (a < b) ? -1 : (a > b) ? 1 : 0;
  }
  function f(arr) {
    arr.sort(cmp);
    return arr;
  }
  %PrepareFunctionForOptimization(cmp);
  %PrepareFunctionForOptimization(f);
  f(["c", "x", "a", "b"]);
  f(["c", "x", "a", "b"]);
  %OptimizeFunctionOnNextCall(f);
  %OptimizeFunctionOnNextCall(cmp);
  f(["c", "x", "a", "b"]);
  assertOptimized(f);

  saw_undef_in_cmp = false;
  const arr = ["c", undefined, "a", "b"];
  const result = f(arr);
  assertEquals(4, result.length);
  assertEquals("a", result[0]);
  assertEquals("b", result[1]);
  assertEquals("c", result[2]);
  assertEquals(undefined, result[3]);
  assertFalse(saw_undef_in_cmp,
              "cmp must not be invoked with undefined arg");
  assertUnoptimized(f);

  // After the deopt the call IC is kDisallowSpeculation, so subsequent
  // re-tiers must not re-inline the sort and must not re-deopt.
  for (let i = 0; i < 3; ++i) {
    %PrepareFunctionForOptimization(f);
    %OptimizeFunctionOnNextCall(f);
    f(["c", undefined, "a", "b"]);
    assertOptimized(f, "f should stay optimized after retier #" + i);
  }
})();