fix: Require for all foldable functions to use distinct return

[vezenovm]

…tnesses

Description

Problem*

Found the issue while working on #4608.

Summary*

For this program:

fn main(x: u32, y: pub u32) {
    let new_field = new_field_in_array([x, y, 3]);
    assert(new_field[0] == 25);
}

#[fold]
fn new_field_in_array(mut input: [u32; 3]) -> [u32 ; 3] {
    input[0] = input[0] + 20;
    input
}

We get the following ACIR:

Old ACIR:

func 0
current witness index : 5
private parameters indices : [0]
public parameters indices : [1]
return value indices : []
BLACKBOX::RANGE [(_0, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_1, num_bits: 32)] [ ]
EXPR [ (-1, _2) 3 ]
CALL func 1: PREDICATE = %EXPR [ 1 ]%
inputs: [Witness(0), Witness(1), Witness(2)], outputs: [Witness(3), Witness(4), Witness(5)]
EXPR [ (1, _3) -25 ]

func 1
current witness index : 3
private parameters indices : [0, 1, 2]
public parameters indices : []
return value indices : [1, 2, 3]
BLACKBOX::RANGE [(_0, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_1, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_2, num_bits: 32)] [ ]
EXPR [ (1, _0) (-1, _3) 20 ]
BLACKBOX::RANGE [(_3, num_bits: 32)] [ ]

One can see how simply the next witness (_3 in this case) is being assigned to 20 directly and returned rather than returning it correctly according to the type. The constraint in the main function above will fail as the returned array will be [5, 10, 20] when we want [20, 5, 10]. This re-ordering can be mitigated by requiring all returns from foldable functions to be distinct for which we get the following ACIR:

New ACIR:
The main func is the same.

func 0 (same as above)

func 1
current witness index : 6
private parameters indices : [0, 1, 2]
public parameters indices : []
return value indices : [4, 5, 6]
BLACKBOX::RANGE [(_0, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_1, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_2, num_bits: 32)] [ ]
EXPR [ (1, _0) (-1, _3) 20 ]
BLACKBOX::RANGE [(_3, num_bits: 32)] [ ]
EXPR [ (1, _3) (-1, _4) 0 ]
EXPR [ (1, _1) (-1, _5) 0 ]
EXPR [ (1, _2) (-1, _6) 0 ]

I think just defaulting all return values from foldable functions to be distinct is going to be the least confusing for users (and we have discussed making it the default on main as well). If we want to add the ability for a user to not use distinct on foldable function return values that can come in a follow up.

Additional Context

Documentation*

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[TomAFrench]

Let's merge in #4951 first as it'll simplify this PR a little bit.

[jfecher]

@vezenovm do we need this at all after #4951 is merged?

[vezenovm]

@vezenovm do we need this at all after #4951 is merged?

That PR looks to only touch the main_acir so these changes still do what is contained in the PR with making all the ACIRs distinct and the additional test.

[TomAFrench]

We still need this as we need to apply the distinct return witnesses to all circuits, not just the main one.

[vezenovm]

This should be ready again now that #4951 is merged