Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Slice operations do not handle correctly slices of structs #2083

Closed
sirasistant opened this issue Jul 28, 2023 · 0 comments · Fixed by #2150
Closed

Slice operations do not handle correctly slices of structs #2083

sirasistant opened this issue Jul 28, 2023 · 0 comments · Fixed by #2150
Assignees
Labels
bug Something isn't working ssa

Comments

@sirasistant
Copy link
Contributor

sirasistant commented Jul 28, 2023

Aim

Slices of structs should generate consistent SSA

Expected Behavior

Consider the following code:

struct NestedSliceStruct {
    id: Field,
    arr: [Field]
}

unconstrained fn create_struct(id: Field, value: Field) -> NestedSliceStruct {
    let mut arr = [id];
    arr = arr.push_back(value);
    NestedSliceStruct { id, arr }
}

unconstrained fn main(a: Field, b: Field) {
    let mut slice = [create_struct(a, b), create_struct(b, a)];

    let item_that_will_be_removed = slice[1];
    assert(item_that_will_be_removed.id == b);

    let remove_result = slice.remove(1);
    let removed_item = remove_result.1;
...
}

It should generate SSA like the following:

brillig fn main f0 {
  b0(v0: Field, v1: Field):
    v3, v4 = call f1(v0, v1)
    v6, v7 = call f1(v1, v0)
    v9 = allocate
    store [v3, v4, v6, v7] at v9
    v10 = load v9
    v13 = array_get v10, index Field 2
    v15 = array_get v10, index Field 3
    v16 = eq v13, v1
    constrain v16
    v18 = load v9
    v19, v20, v21 = call slice_remove(v18, Field 2)
...
}

Bug

The ssa generated looks like this:

brillig fn main f0 {
  b0(v0: Field, v1: Field):
    v3, v4 = call f1(v0, v1)
    v6, v7 = call f1(v1, v0)
    v9 = allocate
    store [v3, v4, v6, v7] at v9
    v10 = load v9
    v13 = array_get v10, index Field 2
    v15 = array_get v10, index Field 3
    v16 = eq v13, v1
    constrain v16
    v18 = load v9
    v19, v20, v21 = call slice_remove(v18, Field 1) // here: The index should have been multipled by the number of elements in the struct  
    // Like it has been for array_get operations
    v22 = eq v20, v1
    constrain v22
    v24 = array_get v21, index Field 0
    v25 = eq v24, Field 0
    constrain v25
    return 
}


Also, the simplification in SSA does not handle correctly struct slices:
https://github.com/noir-lang/noir/blob/master/crates/noirc_evaluator/src/ssa_refactor/ir/instruction.rs#L438
As you can see there, it's assuming there is only going to be one parameter to push to a slice. But when pushing to struct slices, the SSA does have one parameter per field of the struct:

brillig fn push_back_to_slice f2 {
  b0(v0: [Field, [Field]], v1: Field, v2: [Field]):
    v4 = call slice_push_back(v0, v1, v2)
    return v4
}

To Reproduce

Installation Method

None

Nargo Version

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

@sirasistant sirasistant added the bug Something isn't working label Jul 28, 2023
@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Jul 28, 2023
@jfecher jfecher added P-MEDIUM and removed P-MEDIUM labels Jul 31, 2023
@jfecher jfecher self-assigned this Jul 31, 2023
@github-project-automation github-project-automation bot moved this from 📋 Backlog to ✅ Done in Noir Aug 3, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working ssa
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

2 participants