Compiler panic when you make a recursive call which does not terminate

[pventuzelo]

Aim

We (https://github.com/FuzzingLabs) found that the compiler panics when you make a recursive call without condition, even if a return call makes you go out of the loop.a

Expected Behavior

No panic should occur.

Bug

When a function makes a recursive call after a return statement, the compiler considers the recursive call, which can lead to a panic crash as it treats it as an infinite loop. As you can see in the code example, the rec1 function has a return statement before the recursive call, preventing any potential looping. However, the compiler still perceives it as an infinite recursive function.

rec2 is another function that might exhibit the same behavior, but in this case, the compiler doesn’t panic. This seems to be because the compiler never enters the else block. The same phenomenon occurs with rec3.

The issue occurs with the latest compiler version on the master branch. The error message is as follows:

The application panicked (crashed).
Message:  Attempted to recur more than 1000 times during function inlining.
Location: compiler/noirc_evaluator/src/ssa/opt/inlining.rs:167

To Reproduce

/* Function with a recursive call which should end by returning 1, but the compiler treats it as an infinite loop. */
fn rec1() -> u8 {
    if true {
        1
    }
    rec1()
}

/* Function with a recursive call under a condition, so the compiler handles it correctly even though the result should be the same as rec1. */
fn rec2() -> u8 {
    if true {
        1
    } else {
        rec2()
    }
}

/* Another function with the same behavior that doesn't cause the compiler to panic. */
fn rec3() -> u8 {
    if false {
        rec3()
    }
    1
}

fn main() {
    rec1();
    rec2();
    rec3();
}

Project Impact

None

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

None

Nargo Version

No response

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[TomAFrench]

/* Function with a recursive call which should end by returning 1, but the compiler treats it as an infinite loop. */
fn rec1() -> u8 {
    if true {
        1
    }
    rec1()
}

This function isn't doing what the comment is suggesting. The if statement doesn't cause the function rec1 to return so the compiler is correct to treat this as an infinite loop.

We should have a nicer error for this than a panic however.

[AFredefon]

/* Function with a recursive call which should end by returning 1, but the compiler treats it as an infinite loop. */
fn rec1() -> u8 {
    if true {
        1
    }
    rec1()
}

This function isn't doing what the comment is suggesting. The if statement doesn't cause the function rec1 to return so the compiler is correct to treat this as an infinite loop.

We should have a nicer error for this than a panic however.

I had omitted the fact that functions only return the last instruction. I assumed it worked like in Rust, where an instruction not followed by a semicolon is treated as a return. Sorry for the misunderstanding.

[jfecher]

I had omitted the fact that functions only return the last instruction. I assumed it worked like in Rust, where an instruction not followed by a semicolon is treated as a return. Sorry for the misunderstanding.

It does work the same as in Rust. In Rust and Noir an instruction not followed by a semicolon is not a return from the function, it just yields the value of that expression. The same code in Rust does however issue an error that the result of an if with no else is expected to be a unit value though and suggests maybe a return should be added. We have a similar warning (without the helpful extra bit about adding return) in some cases, but not in an if with no else. Adding rust's error/warning would be helpful here.

[jfecher]

Since this error applies to any recursive function and doesn't require a return call, I'm going to treat this issue as the general issue for improving the "Attempted to recur more than 1000 times during function inlining" error and am closing #4843.

Minimal repro for this issue is

fn main() {
    main();
}