Not addressed by zkemail/zk-regex#75 (comment) btw

Hey, this isn't an issue with the library but with noir's comptime interpreter. I've then moved this issue across to the main noir repository.

This can be replicated with the programs

    global ELEMENT_COUNT: u32 = 100;
    comptime fn main() {
        let values: [u32; ELEMENT_COUNT] = [0; ELEMENT_COUNT];
        let _ = quicksort(values);
    }
    
    comptime fn partition<let N: u32>(
        arr: &mut [u32; N],
        low: u32,
        high: u32,
    ) -> u32 {
        let pivot = high;
        let mut i = low;
        for j in low..high {
            if arr[j] < arr[pivot] {
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
    
                i += 1;
            }
        }
    
        let temp = arr[i];
        arr[i] = arr[pivot];
        arr[pivot] = temp;
        i
    }
    
    comptime fn quicksort_recursive<let N: u32>(
        arr: &mut [u32; N],
        low: u32,
        high: u32,
    ) {
        if low < high {
            let pivot_index = partition(arr, low, high);
            if pivot_index > 0 {
                quicksort_recursive(arr, low, pivot_index - 1);
            }
            quicksort_recursive(arr, pivot_index + 1, high);
        }
    }
    
    comptime fn quicksort<let N: u32>(
        _arr: [u32; N],
    ) -> [u32; N] {
        let mut arr: [u32; N] = _arr;
        if N > 1 {
            quicksort_recursive(&mut arr, 0, N - 1);
        }
        arr
    }    

or more minimally

    global RECURSION_LIMIT: u32 = 33;

    comptime fn main() {
        recurse(RECURSION_LIMIT);
    }
    
    comptime fn recurse(n: u32) {
        if n > 0 {
            recurse(n-1);
        }
    }

@jfecher can you assign someone to look into this?

Reworking the interpreter in general to not stack overflow for a large* amount of recursive calls will be difficult I think. In general it requires queuing calls using a trampoline or similar. Since the interpreter would also need to preserve control-flow in the middle of a function it'd mean making it async. Since the interpreter also uses the elaborator... the entire noir frontend would need to be async.

For now we can maybe rework quicksort to use loops instead of recursion.

* "large" is obviously imprecise and I'd hope that ~46 recursive calls or however many were used wouldn't be considered such but the point stands that unless we're being very inefficient with stack memory in ways that are easily fixable, saving some memory here and there probably won't get us to 1000+ recursive calls.

Would switching from a tree-walk interpreter to a VM-interpreter help here? For example here's part of the stack trace that repeats when it fails right now:

1497: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate_if
1498: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate_no_dereference
1499: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate
1500: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate_statement
1501: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate_block
1502: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate_no_dereference
1503: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate
1504: noirc_frontend::hir::comptime::interpreter::Interpreter::call_function_inner
1505: noirc_frontend::hir::comptime::interpreter::Interpreter::call_function
1506: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate_no_dereference
1507: noirc_frontend::hir::comptime::interpreter::Interpreter::evaluate

So a lot of function calls for interpreting something. I think with a VM-interpreter that would just be looping through bytecode, maybe pushing to a stack but here it's only one variable that's in the stack (and the "stack" could leave in the heap).

I tried using #[inline] in a few of the above functions and it helped a bit but it still crashes for relatively low numbers.

I don't know if a full-blown VM would be needed to solve this, maybe just transforming a function body or list of statements into bytecode so it can be looped instead of using function calls.

@asterite Rust doesn't have a way to ensure tail calls (see here), so I think that the idea of setting up a "trampoline" would end up being similar here.