// #target: macos-x64
module test_generic<Type, Func>;

fn void sort(Type list, isz, isz, Func cmp)
{}

module sort_test;
import std::sort;
import test_generic;

macro quicksort(list, cmp = null)
{
    var $Type = $typeof(list);
    var $CmpType = $typeof(cmp);
    usz len = lengthof(list);
    test_generic::sort{$Type, $CmpType}(list, 0, (isz)len - 1, cmp);
}

fn void quicksort_with_value() @nostrip
{
    int[][] tcases = {
        {},
        {10, 3},
        {3, 2, 1},
        {1, 2, 3},
        {2, 1, 3},
    };

    foreach (tc : tcases)
    {
        quicksort(tc, &cmp_int_value);
    }
}

fn void quicksort_with_value2() @nostrip
{
    int[][] tcases = {
        {},
        {10, 3},
        {3, 2, 1},
        {1, 2, 3},
        {2, 1, 3},
    };

    foreach (tc : tcases)
    {
        quicksort(tc, &cmp_int_value2);
    }
}

fn int cmp_int_value(int x, int y) {
    return x - y;
}

fn int cmp_int_value2(int x, int y) {
    return x - y;
}

/* #expect: sort_test.ll

define void @sort_test.quicksort_with_value() #0 {
entry:
  %tcases = alloca %"int[][]", align 8
  %literal = alloca [5 x %"int[]"], align 16
  %literal1 = alloca [2 x i32], align 4
  %literal3 = alloca [3 x i32], align 4
  %literal5 = alloca [3 x i32], align 4
  %literal7 = alloca [3 x i32], align 4
  %.anon = alloca i64, align 8
  %tc = alloca %"int[]", align 8
  %list = alloca %"int[]", align 8
  %len = alloca i64, align 8
  store %"int[]" zeroinitializer, ptr %literal, align 16
  %ptradd = getelementptr inbounds i8, ptr %literal, i64 16
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal1, ptr align 4 @.__const, i32 8, i1 false)
  %0 = insertvalue %"int[]" undef, ptr %literal1, 0
  %1 = insertvalue %"int[]" %0, i64 2, 1
  store %"int[]" %1, ptr %ptradd, align 16
  %ptradd2 = getelementptr inbounds i8, ptr %literal, i64 32
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal3, ptr align 4 @.__const.1, i32 12, i1 false)
  %2 = insertvalue %"int[]" undef, ptr %literal3, 0
  %3 = insertvalue %"int[]" %2, i64 3, 1
  store %"int[]" %3, ptr %ptradd2, align 16
  %ptradd4 = getelementptr inbounds i8, ptr %literal, i64 48
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal5, ptr align 4 @.__const.2, i32 12, i1 false)
  %4 = insertvalue %"int[]" undef, ptr %literal5, 0
  %5 = insertvalue %"int[]" %4, i64 3, 1
  store %"int[]" %5, ptr %ptradd4, align 16
  %ptradd6 = getelementptr inbounds i8, ptr %literal, i64 64
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal7, ptr align 4 @.__const.3, i32 12, i1 false)
  %6 = insertvalue %"int[]" undef, ptr %literal7, 0
  %7 = insertvalue %"int[]" %6, i64 3, 1
  store %"int[]" %7, ptr %ptradd6, align 16
  %8 = insertvalue %"int[][]" undef, ptr %literal, 0
  %9 = insertvalue %"int[][]" %8, i64 5, 1
  store %"int[][]" %9, ptr %tcases, align 8
  %ptradd8 = getelementptr inbounds i8, ptr %tcases, i64 8
  %10 = load i64, ptr %ptradd8, align 8
  store i64 0, ptr %.anon, align 8
  br label %loop.cond

loop.cond:                                        ; preds = %loop.body, %entry
  %11 = load i64, ptr %.anon, align 8
  %lt = icmp ult i64 %11, %10
  br i1 %lt, label %loop.body, label %loop.exit

loop.body:                                        ; preds = %loop.cond
  %12 = load ptr, ptr %tcases, align 8
  %13 = load i64, ptr %.anon, align 8
  %ptroffset = getelementptr inbounds [16 x i8], ptr %12, i64 %13
  call void @llvm.memcpy.p0.p0.i32(ptr align 8 %tc, ptr align 8 %ptroffset, i32 16, i1 false)
  call void @llvm.memcpy.p0.p0.i32(ptr align 8 %list, ptr align 8 %tc, i32 16, i1 false)
  %ptradd9 = getelementptr inbounds i8, ptr %list, i64 8
  %14 = load i64, ptr %ptradd9, align 8
  store i64 %14, ptr %len, align 8
  %15 = load i64, ptr %len, align 8
  %sub = sub i64 %15, 1
  %lo = load ptr, ptr %list, align 8
  %ptradd10 = getelementptr inbounds i8, ptr %list, i64 8
  %hi = load i64, ptr %ptradd10, align 8
  call void @"test_generic.sort$sa$int$fn$int$int$$int$$"(ptr %lo, i64 %hi, i64 0, i64 %sub, ptr @sort_test.cmp_int_value)
  %16 = load i64, ptr %.anon, align 8
  %addnuw = add nuw i64 %16, 1
  store i64 %addnuw, ptr %.anon, align 8
  br label %loop.cond

loop.exit:                                        ; preds = %loop.cond
  ret void
}

define void @sort_test.quicksort_with_value2() #0 {
entry:
  %tcases = alloca %"int[][]", align 8
  %literal = alloca [5 x %"int[]"], align 16
  %literal1 = alloca [2 x i32], align 4
  %literal3 = alloca [3 x i32], align 4
  %literal5 = alloca [3 x i32], align 4
  %literal7 = alloca [3 x i32], align 4
  %.anon = alloca i64, align 8
  %tc = alloca %"int[]", align 8
  %list = alloca %"int[]", align 8
  %len = alloca i64, align 8
  store %"int[]" zeroinitializer, ptr %literal, align 16
  %ptradd = getelementptr inbounds i8, ptr %literal, i64 16
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal1, ptr align 4 @.__const.4, i32 8, i1 false)
  %0 = insertvalue %"int[]" undef, ptr %literal1, 0
  %1 = insertvalue %"int[]" %0, i64 2, 1
  store %"int[]" %1, ptr %ptradd, align 16
  %ptradd2 = getelementptr inbounds i8, ptr %literal, i64 32
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal3, ptr align 4 @.__const.5, i32 12, i1 false)
  %2 = insertvalue %"int[]" undef, ptr %literal3, 0
  %3 = insertvalue %"int[]" %2, i64 3, 1
  store %"int[]" %3, ptr %ptradd2, align 16
  %ptradd4 = getelementptr inbounds i8, ptr %literal, i64 48
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal5, ptr align 4 @.__const.6, i32 12, i1 false)
  %4 = insertvalue %"int[]" undef, ptr %literal5, 0
  %5 = insertvalue %"int[]" %4, i64 3, 1
  store %"int[]" %5, ptr %ptradd4, align 16
  %ptradd6 = getelementptr inbounds i8, ptr %literal, i64 64
  call void @llvm.memcpy.p0.p0.i32(ptr align 4 %literal7, ptr align 4 @.__const.7, i32 12, i1 false)
  %6 = insertvalue %"int[]" undef, ptr %literal7, 0
  %7 = insertvalue %"int[]" %6, i64 3, 1
  store %"int[]" %7, ptr %ptradd6, align 16
  %8 = insertvalue %"int[][]" undef, ptr %literal, 0
  %9 = insertvalue %"int[][]" %8, i64 5, 1
  store %"int[][]" %9, ptr %tcases, align 8
  %ptradd8 = getelementptr inbounds i8, ptr %tcases, i64 8
  %10 = load i64, ptr %ptradd8, align 8
  store i64 0, ptr %.anon, align 8
  br label %loop.cond

loop.cond:                                        ; preds = %loop.body, %entry
  %11 = load i64, ptr %.anon, align 8
  %lt = icmp ult i64 %11, %10
  br i1 %lt, label %loop.body, label %loop.exit

loop.body:                                        ; preds = %loop.cond
  %12 = load ptr, ptr %tcases, align 8
  %13 = load i64, ptr %.anon, align 8
  %ptroffset = getelementptr inbounds [16 x i8], ptr %12, i64 %13
  call void @llvm.memcpy.p0.p0.i32(ptr align 8 %tc, ptr align 8 %ptroffset, i32 16, i1 false)
  call void @llvm.memcpy.p0.p0.i32(ptr align 8 %list, ptr align 8 %tc, i32 16, i1 false)
  %ptradd9 = getelementptr inbounds i8, ptr %list, i64 8
  %14 = load i64, ptr %ptradd9, align 8
  store i64 %14, ptr %len, align 8
  %15 = load i64, ptr %len, align 8
  %sub = sub i64 %15, 1
  %lo = load ptr, ptr %list, align 8
  %ptradd10 = getelementptr inbounds i8, ptr %list, i64 8
  %hi = load i64, ptr %ptradd10, align 8
  call void @"test_generic.sort$sa$int$fn$int$int$$int$$"(ptr %lo, i64 %hi, i64 0, i64 %sub, ptr @sort_test.cmp_int_value2)
  %16 = load i64, ptr %.anon, align 8
  %addnuw = add nuw i64 %16, 1
  store i64 %addnuw, ptr %.anon, align 8
  br label %loop.cond

loop.exit:                                        ; preds = %loop.cond
  ret void
}

declare extern_weak void @"test_generic.sort$sa$int$fn$int$int$$int$$"(ptr, i64, i64, i64, ptr) #0