Multiple slice mergers requires equal size slices

[vezenovm]

Aim

I have this program where the first if case is hit and the second else-case is hit:

fn merge_slices_mutate_two_ifs(x: Field, y: Field) -> [Field] {
    let mut slice = [0; 2];
    if x != y {
        slice = slice.push_back(y);
        slice = slice.push_back(x);
    } else {
        slice = slice.push_back(x);
    }
    if x == 20 {
        slice = slice.push_back(20);
    } else {
        slice = slice.push_back(15);
    }
    slice = slice.push_back(30);
    
    slice
}

I should be able to write it like this:

fn merge_slices_mutate_two_ifs(x: Field, y: Field) -> [Field] {
    let mut slice = [0; 2];
    if x != y {
        slice = slice.push_back(y);
        slice = slice.push_back(x);
    } else {
        slice = slice.push_back(x);
    }
    if x == 20 {
        slice = slice.push_back(20);
    } 
    slice = slice.push_back(15);
    slice = slice.push_back(30);
    
    slice
}

Expected Behavior

We should have a resulting slice in both cases like this: 0x00, 0x00, 0x0a, 0x05, 0x0f, 0x1e.

Bug

However, when checking the values like such:

    let slice = merge_slices_mutate_two_ifs(x, y);
    assert(slice.len() == 6);
    assert(slice[3] == 5);
    assert(slice[4] == 15);
    assert(slice[5] == 30);

The second snippet has the wrong values assigned to the slice. Specifically, printing all fix values we get 0x00, 0x00, 0x0a, 0x05, 0x00, 0x0f, and thus the assertion will fail.

To Reproduce

1. Copy the above snippets into the Noir program
2. Run the program and see it fail
3. If desired you can print each slice value instead of asserting:

    dep::std::println(slice[0]);
    dep::std::println(slice[1]);    
    dep::std::println(slice[2]);
    dep::std::println(slice[3]);
    dep::std::println(slice[4]);
    dep::std::println(slice[5]);

Installation Method

Compiled from source

Nargo Version

nargo 0.11.0 (git version hash: 2728851, is dirty: true)

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[vezenovm]

This looks to be not that the else case is needed but that rather that multiple slice mergers break for slices of different sizes.

For example taking a simpler snippet of above:

fn merge_slices_mutate_two_ifs(x: Field, y: Field) -> [Field] {
    let mut slice = [0; 2];
    if x != y {
        slice = slice.push_back(y);
        slice = slice.push_back(x);
    } else {
        slice = slice.push_back(x);
    }
    if x == 20 {
        slice = slice.push_back(20);
    } 
    slice = slice.push_back(30);
    slice
} 

When we merge the first if statement we have a then length of 4 and an else length of 3, so we put placeholder data in the else case. Not accessing the placeholder data is handled by maintaining the actual slice length as part of a slice's structure (slices are a tuple of (length, contents), where contents.len() represents the slice capacity). The second if case x == 20 is false so we continue onwards. However, the then length and the else length are going to be 5 and 4 respectively because we have placeholder data in the else case. So slice = slice.push_back(30) gets pushed onto [0, 0, y, x, 0] , thus leading to gaps in the array where there is placeholder data from multiple mergers.

[vezenovm]

So in order to be able to handle multiple slice mergers of varying size we need check the tracked user facing slice length against the actual slice capacity when simplifying or codegen'ing slice intrinsics. These checks and their result need to be codegen'd

In order to implement this fix we will need to do what is stated below:

1. When we have a push_back (or other slice intrinsic), we need to check whether the length == capacity. If they are not equal we need to actually perform an array_set rather than making a new array. Simply adding an element to a slice which is the result of a slice merger would potentially result in the element being included after placeholder data in the slice's SSA value. When the slice is later accessed the placeholder data will potentially be accessed where the element that was pushed back is expected.
2. In order to conditionally array_set or make a new slice value we will need to expose the merging of values (the merge_values method in flattening) to the entire SSA crate rather than it being part of the flattening pass' context.
3. Doing the above means that all slices whose length is not constant will now be dynamic. This includes nested slices which means we need to implement non-const indices on nested slices.

I have a proof of concept that fixes the snippets posted in this issue, but I have only tested and implemented push_back so far. In order to implement push_back for the PoC, step 2 had to be implemented so that is complete already. The main challenge looks like it will be getting slice insert and slice remove correct as they do not simply add on or remove elements from the end of slice, but rather anywhere in the slice. I think these should be tackled next to determine the feasibility of this solution.

It may be also worth it to discuss whether it is worth it to return to mutable arrays in SSA if this solution is deemed too complex (or flat out unsound).