This PR implements for loops down to Yul and also improvements on the current arrays implementation. Design was made after a conversation with @micahscopes about possible needs from Circom's Poseidon Hash if being implemented on Fe.

Happy to discuss the reasons behind the lowering strategies on our call.

While this compiles valid Yul feel free to replace with a better implementation. That being said, I'll keep focusing on the examples and Yul code expected to keep track of the actual implementation.

New Features added

1. Ranged for loops. Example here
   (note that literal ranges are not supported yet)

let start: u64 = 0
let end: u64 = 10
for i in start..end {
    sum = sum + i
}

2. For loop array iteration. Example here

let arr: [u64; 25] = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
    21, 22, 23, 24, 25
]
for elem in arr {
    sum = sum + elem
}

3. Unroll annotation for for loops. Example here

Notice the #unroll annotation

#[unroll]
for elem in [1, 2, 3, 4, 5] {
    sum = sum + elem
}

Will result on:

let v0 := 0
let v1 := 1
v0 := add(v0, v1)
let v2 := 2
v0 := add(v0, v2)
let v3 := 3
v0 := add(v0, v3)
let v4 := 4
v0 := add(v0, v4)
let v5 := 5
v0 := add(v0, v5)

4. Data region

4.a Immutable arrays. Example here

Now, big immutable arrays will be stored on data region, baked into the bytecode. For example:

let arr: [u8; 64] = [
    1, 2, 3, 4, 5, 6, 7, 8,
    9, 10, 11, 12, 13, 14, 15, 16,
    17, 18, 19, 20, 21, 22, 23, 24,
    25, 26, 27, 28, 29, 30, 31, 32,
    33, 34, 35, 36, 37, 38, 39, 40,
    41, 42, 43, 44, 45, 46, 47, 48,
    49, 50, 51, 52, 53, 54, 55, 56,
    57, 58, 59, 60, 61, 62, 63, 64
]

Will result on, notice the data region added by encoding the array into a hex string.

object "Module" {
  code {
    [...]
  }
  data "data_0" hex"0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f40"
}

4.b Big strings. Example here

Now strings bigger than 32 bytes like this one:

pub fn large_string() -> String<64> {
    "This is a long string that exceeds thirty-two bytes in length!!"
}

Will be lowered into data region instead of inline stack.

object "Module" {
  code {
    [...]
  }
  data "data_0" hex"546869732069732061206c6f6e6720737472696e6720746861742065786365656473207468697274792d74776f20627974657320696e206c656e6774682121"
}

Structural changes

Parser:

• Added .. and ..=
• Added the capacity to for loops to attach the #unroll annotation via the AttrListOwner param

HIR:

• Added the `Range(ExprId /start/, ExprId /end/, bool /lt or le/) expression
• Now the for loops handles the AttrListOwner for the #unroll annotation

MIR

• DataRegionDef added to the MIR body to accept data regions
• Added CopyDataRegion Synthetic type for arrays and large (>32 bytes) strings
• Added LoopInfo extra data to be able to detect the init and post block for loop code

Yul codegen

• While style and unrolled loops implementation
• Array and big strings data sections

TODOs

• Review codex comments
• Make more tests (e.g. data section const arrays vs memory based mut arrays iteration)
• Do more in depth change analysis in case this PR becomes an actual candidate to be merged