feat: Make arrays and slices polymorphic over each other

[jfecher]

Description

Problem*

Resolves #1963
Resolves #1931
Resolves #1842
Resolves #1354

Summary*

Instead of representing Type::Array(size, elem) as a separate type from Type::Slice(elem) and allowing them to intermingle via subtyping, this PR removes the subtyping relationship and the Type::Slice variant entirely. Now, array literals have a polymorphic "MaybeConstant" size that can later be resolved to either a Constant size (array) or a NotConstant size (slice). This also means we no longer need type annotations to create slice literals.

BREAKING CHANGES:
- Arrays and slices are no longer subtypes of each other. So if you have an array and you need to pass it to a function that only accepts a slice, you now need to add an explicit .as_slice().

• I've added an array to slice coercion so there should no longer be any breaking changes.

Documentation

• This PR requires documentation updates when merged.

  • I will submit a noir-lang/docs PR.
  • I will request for and support Dev Rel's help in documenting this PR.
    • An array literal [a, b, c, ..] can now resolve to either an array or a slice depending on how it is used.
    • This is just like how an integer literal can resolve to any integer type depending on how it is used.
    • Just like integer literals, if you want to convert between arrays and slices you now need an explicit conversion function.
    • Users wishing to write a function that is polymorphic over arrays and slices can still use the fn foo<T, N>(array_or_slice: [T; N]) syntax since slices are considered to be arrays internally of a non-constant size (implementation detail).

Additional Context

I'm putting this PR out a bit early for visibility and because I need the CI to help find which tests need a .as_slice() to be added.

PR Checklist*

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

[jfecher]

I think I'll try to add rust's implicit coercion of array to slice. This should no longer be a breaking change afterward.

Edit: Added

[jfecher]

This PR is currently held up by an error in brillig_slices:

the application panicked (crashed).
Message:  internal error: entered unreachable code: ICE: Expected array, got HeapVector(HeapVector { pointer: RegisterIndex(6), size: RegisterIndex(7) })
Location: crates/noirc_evaluator/src/brillig/brillig_gen/brillig_fn.rs:114

This is a bug. We may have already fixed this in newer versions of Nargo so try searching for similar issues at https://github.com/noir-lang/noir/issues/.
If there isn't an open issue for this bug, consider opening one at https://github.com/noir-lang/noir/issues/new?labels=bug&template=bug_report.yml

  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ BACKTRACE ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
                                ⋮ 13 frames hidden ⋮                              
  14: noirc_evaluator::brillig::brillig_gen::brillig_fn::FunctionContext::extract_heap_array::h612d83e614e579d9
      at /.../noir/crates/noirc_evaluator/src/brillig/brillig_gen/brillig_fn.rs:114
  15: noirc_evaluator::brillig::brillig_gen::brillig_block::BrilligBlock::convert_ssa_value::h03347b8489e010ae
      at /.../noir/crates/noirc_evaluator/src/brillig/brillig_gen/brillig_block.rs:803
  16: noirc_evaluator::brillig::brillig_gen::brillig_block::BrilligBlock::convert_ssa_instruction::h435b587b3c58d1e0
      at /.../noir/crates/noirc_evaluator/src/brillig/brillig_gen/brillig_block.rs:236
  17: noirc_evaluator::brillig::brillig_gen::brillig_block::BrilligBlock::convert_block::h3079b65c1c7e2aaa
      at /.../noir/crates/noirc_evaluator/src/brillig/brillig_gen/brillig_block.rs:61
  18: noirc_evaluator::brillig::brillig_gen::brillig_block::BrilligBlock::compile::h4903fe94bd90897c
      at /.../noir/crates/noirc_evaluator/src/brillig/brillig_gen/brillig_block.rs:47
  19: noirc_evaluator::brillig::brillig_gen::convert_ssa_function::h6239c1d6fcb032a1
      at /.../noir/crates/noirc_evaluator/src/brillig/brillig_gen.rs:28
  20: noirc_evaluator::brillig::Brillig::compile::h3cd51d3807fe3513
      at /.../noir/crates/noirc_evaluator/src/brillig/mod.rs:28
  21: noirc_evaluator::brillig::<impl noirc_evaluator::ssa_refactor::ssa_gen::program::Ssa>::to_brillig::h58acb38d118edfdd
      at /.../noir/crates/noirc_evaluator/src/brillig/mod.rs:99
  22: noirc_evaluator::ssa_refactor::optimize_into_acir::h96fd7ea2cbc06f17
      at /.../noir/crates/noirc_evaluator/src/ssa_refactor.rs:48
  23: noirc_evaluator::ssa_refactor::create_circuit::h3221b5c03c1245cd
      at /.../noir/crates/noirc_evaluator/src/ssa_refactor.rs:81
  24: noirc_driver::compile_no_check::ha192bac6b09f9ae5
      at /.../noir/crates/noirc_driver/src/lib.rs:306
  25: noirc_driver::compile_main::h159318b5103cbeb1
      at /.../noir/crates/noirc_driver/src/lib.rs:195
  26: nargo_cli::cli::compile_cmd::compile_circuit::h750de128d64d5da7
      at /.../noir/crates/nargo_cli/src/cli/compile_cmd.rs:128
  27: nargo_cli::cli::prove_cmd::prove_with_path::hc2b46b42c1fbf6f9
      at /.../noir/crates/nargo_cli/src/cli/prove_cmd.rs:112
  28: nargo_cli::cli::prove_cmd::run::h9a42555316685c8e
      at /.../noir/crates/nargo_cli/src/cli/prove_cmd.rs:68
  29: nargo_cli::cli::start_cli::hafb3033a71756cdf
      at /.../noir/crates/nargo_cli/src/cli/mod.rs:80
  30: nargo::main::hb051dd85bb9ddb14
      at /.../noir/crates/nargo_cli/src/main.rs:14
  31: core::ops::function::FnOnce::call_once::he90185e242af6ac8
      at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ops/function.rs:251
                                ⋮ 13 frames hidden ⋮                              
exit 101

Any insight into this @sirasistant?

[sirasistant]

Yes, fixed in #2080. The problem was that it was previously assumed that a Value::Array was always had Type::Array, which is no longer the case. Also improved a bit the brillig_slices test now that references have coherent typing!

[sirasistant]

Thanks a lot for this! 🚀

[jfecher]

@sirasistant I've pushed an array -> slice coercion so that this is no longer a breaking change. I think this recovers the lost ergonomics as well. It works by implicitly adding a .as_slice() call when needed, so the backend does not have to worry about values changing types.