Build dependency graph between variables in name resolution

[jfecher]

Aim

Trying to write a program

struct ShouldError {
    uses_nested_arrays: [Array; 2],
}

struct Array {
    array: [Field; 3],
}

Expected behavior

Noir should issue an error that nested arrays are currently unimplemented

Bug

The error is only issued sometimes when the program is compiled. This is because on some runs Array is resolved first and when ShouldError is subsequently resolved, it can see all the fields of Array and will error that nested arrays are used. On other runs however, ShouldError is resolved first and sees only an empty struct for Array and thus does not issue an error. In this case, the program continues until monomorphization where it fails with an unreachable assert.

To reproduce

Installation method

None

Nargo version

No response

@noir-lang/noir_wasm version

No response

@noir-lang/barretenberg version

No response

@noir-lang/aztec_backend version

No response

Additional context

No response

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[kevaundray]

@jfecher what is the status of this issue?

[kevaundray]

Lowest hanging fruit to attempt to fix would be replacing suspicious usages of hashmap with something like indexmap

[kevaundray]

@jfecher - "The above is not enough, we would need a dependency tree of structures, we could also use this in places where globals depend on other globals"

[kevaundray]

Spoke with Jake; he says, ideally name resolution is split into smaller components and we build this dependency tree at the last step to be used in later passes.

[jfecher]

Can we re-tag this E-HIGH? I think it'd require a large rewrite of name resolution to first create the graph then follow its nodes to resolve names in that order.

Edit: Retagged it as "Large" myself. Not sure what the precise difference is between Large and X-Large so I kept it on large.

[Savio-Sou]

precise difference is between Large and X-Large

Choice is all good as long as it feels right. The Size field is used just as a subjective reference for now.