Inferred array lengths on function returns do not work when defined in the wrong order

[jfecher]

Description

Aim

Trying to use inferred array lengths on a function's return type:

fn main() {
    let a = foo([1, 2]);
    constrain a[1] == 2;
}

fn foo(b: [Field]) -> [Field] {
    b
}

Expected behavior

The program to work without issue.

Bug

The compiler is unable to infer the correct array size for a leading to an internal compiler panic during monomorphisation. This is because to see that the length of the returned array should be equal to the input array, it would need to infer foo before main, but it instead starts inferring the type of main first.

Possible fixes

1. Remove this syntax, forcing users to be more explicit. More burdensome but closer to rust:

fn main() {
    let a = foo([1, 2]);
    constrain a[1] == 2;
}

fn foo<N>(b: [Field; N]) -> [Field; N] {
    b
}

2. Change the typechecking pass so that it no longer assumes the types of called functions are correct. Its ordering will have to be changed to always typecheck a called function before its caller.

[guipublic]

Since we have already a PR to handle slices, the best would be to not try to infer slice length in the frontend and uses PR #314 which uses proper function ordering for getting the length.

[jfecher]

After the last internal discussion, it seems we were leaning more towards option 1, requiring users to be explicit instead. It seems option 1 requires changing some name resolution items so that the N generic can be in scope in an expression position of the array types. So perhaps option 2 may actually be less code changes required overall.

[guipublic]

I forgot about the slice PR, until we reviewed the PRs recently, this is why I did not mention it when we discussed this issue.
I don't think the generics and the slices are incompatible, we could have generics <N> [Field;N] that will be resolved by the type system, and we could also support slices [Field], like in rust in fact, using the implementation in the PR I mentioned. This would be the easiest way to do it.

[jfecher]

My main concern is that they interlap, there is no real reason to support both.

[guipublic]

does not rust have both?

[jfecher]

It does, but that is because slices are semantically different from arrays in rust in terms of runtime semantics. Namely in whether they're passed by value copying the whole array or passed by reference and carrying the length of the array as a separate field. This is not true for noir so we should not support both.

[jfecher]

Closing this. The old sugared generics syntax has finally been removed and the syntax now stands for slices which cause the example to work as-is.