Add support for list expressions

[cburgdorf]

What is wrong?

We do currently not support list expressions such as [1, 2, 3]. While we do have support for it in the parser and partly in the analyzer this comes up repeatedly in crashes found by the fuzzer.

See related issues:

• internal error: entered unreachable code at analyzer/src/traversal/expressions.rs:297:32 #370
• Empty list reaches unreachable!() #256

How can it be fixed

I'm wondering if we should handle this in the lowering pass. Let's assume we have the following code:

x: u8[3] = [10, 20, 30]

The lowering pass could rewrite that to:

x: u8[3]
x[0] = 10
x[1] = 20
x[2] = 30

@g-r-a-n-t Do you think it would be reasonable to handle list expressions in the lowering pass so that we could eliminate them completely from the mapping?

[g-r-a-n-t]

I think we should handle them in lowering pass, but there is a bit more to it. @satyamakgec and I discussed this here before the lowering pass existed. The same fundamental issues exist.

We could map

x: u8[3] = [10, 20, 30]

to

x: u8[3]
x[0] = 10
x[1] = 20
x[2] = 30

but that would only work for assignment statements. We want this to work on the expression level, so we need to map [10, 20, 30] to another expression.

i.e.

x: u8[3] = build_array_u8_3(10, 20, 30)

def build_array_u8_3(value0: u8, value1: u8, value2: u8) -> u8[3]:
  x: u8[3]
  x[0] = 10
  x[1] = 20
  x[2] = 30
  return x

My concern with this approach in the linked thread was that we would run into StackTooDeep errors for arrays longer than 16, but this might not actually be an issue (something to look into). If length is an issue, I think we should just cap the length of list expressions at 16 and call it a day.

This approach isn't too far off from what Rust does with vec!, they just have the work split up between macro expansion and lowering of closures - we would be doing it all in the lowering pass.

[satyamakgec]

If I am not mistaken, We don't need to do anything much on the compiler side as we are already supporting the lowering pass then parser can generate the AST not as the list but as the assignment and rest will be handle automatically with the existing code. Although I am not sure how does the python type list is gonna work (1 .. 100) or using range() function I am not sure whether we are going to support it or not.

[cburgdorf]

If length is an issue, I think we should just cap the length of list expressions at 16 and call it a day.

That sounds reasonable. We could always tweak it in the future. 👍

[sbillig]

Closed by #388