bug: [loop] Says moved when it shouldn't

[gaetbout]

Bug Report

Cairo version:

Tested at alpha.7

Current behavior:
When doing

    fn contains<impl TPartialEq: PartialEq<T>>(ref self: Array<T>, item: T) -> bool {
        let mut index = 0_usize;
        loop {
            check_gas();

            if index >= self.len() {
                break false;
            } else if *self[index] == item {
                break true;
            } else {
                index = index + 1_usize;
            };
        }
    } 

It doesn't work because self is moved and doesn't allow such behaviour.

Looks like loop doesn't understand it only needs to get @self instead of self.

[Amxx]

I am getting a similar issue with the following code

        fn balance_of_batch(mut accounts: Array<ContractAddress>, mut ids: Array<u256>) -> Array<u256> {
            let mut balances: Array<u256> = ArrayTrait::new();
            loop {
                let account = accounts.pop_front();
                let id = ids.pop_front();
                if (account.is_some() & id.is_some()) {
                    balances.append(ERC1155::balance_of(
                        account.unwrap(),
                        id.unwrap()
                    ));
                } else if (account.is_none() & id.is_none()) {
                    break balances;
                } else {
                    panic_with_felt252('ERC1155 invalid array length');
                };
            }
        }

is causing

error: Variable was previously moved. Trait has no implementation in context: core::traits::Copy::<core::array::Array::<core::integer::u256>>
 --> contract:49:27
                    break balances;
                          ^******^

[spapinistarkware]

The issue is that the logic for checking which variables member paths (i.e. a.b.c), does not include snapshot tracking.

Guidance:
At usage.rs, MemberPath represents a path of member accesses of a variable (e.g. a.b.c).
At usage.rs, handle_expr() computes the "captured" member paths of a loop body.
In that function there is also pruning of member parents. If a.b is already used, we pruned child usages like a.b.c, they are redundant.

At ref.rs, there is a logic to correctly treat member paths as variables inside code. For example, when assigning (a.b=5) or passing them as ref parameters (foo(ref a.b)).
The SemanticLoweringMapping keeps track of a mapping from a member path to VariableId. - the low-level variable that holds the value of the member.
SemanticLoweringMapping is able to assign and get member values on demand.by using struct construction and destruction.
Example: to access a.b.c, first a is deconstructed (let A{ b, b1, b2 } = a). Then b is deconstructed.

This is done with the break_into_value() and assemble_value() value function. The first deconstructs as needed, the other constructs as needed.
scattered holds all the trees, each entry is one tree of Values.

Goals:

1. Correctly compute the "captured" memebr paths with respect to snapshots. If the loop only needs a snapshot, it will take only the snapshot.
2. When accessing member path snapshot in code, not just loop (e.g. @a.b.c), don't consume a by destructing it. Instead, take the snapshot of a, then deconstruct it.
   Note: snapshots member paths cannot be assigned to.

Tasks:

1. Add an is_snapshot flag on MemberPath.
2. Correct capture computation at usage.rs
3. At handle_expr(), update this snpashot flag on Snapshot and Desnap.
4. At the pruning logic: if the child (a.b.c) is not a snapshot but parent (@a.b) is a snapshot => Prune a.b.c but change a.b to a non-snapshot. This is the easiest thing we can do. While not optimal, it's good enough.
5. Correct SemanticLoweringMapping at refs.rs. Possible suggestion: Add a variant Value::Snapshot(Box), which means we only have a snapshot to this value. Value::Var and Value::Scattered automatically discard the snapshot value, since we should take a snapshot to the existing value - this doesn't add an unecessary consuming destructure.

This issue is probably large and non-trivial

[Robertorosmaninho]

Looking forward to this feature!