bug: Found an unexpected cycle during cost computation.

[enitrat]

Bug Report

Cairo version:
2.2.0

Current behavior:
After implementing self-referring structs using a Nullable in Kakarot, we encounter the following error message. Note that since our main struct contains dicts, we need to derive Destruct to allow it to go out of scope.

The Destruct impl is:

impl NullableExecutionContextDestruct of Destruct<Nullable<ExecutionContext>> {
    fn destruct(self: Nullable<ExecutionContext>) nopanic {
        match match_nullable(self) {
            FromNullableResult::Null => {},
            FromNullableResult::NotNull(value) => value.unbox().destruct(),
        }
    }
}

I guess the problem comes from there?

Here's the error message. It only appears when running tests, not when compiling the crate.

     Running cairo-test evm
testing evm ...
thread 'main' panicked at 'Found an unexpected cycle during cost computation.', /Users/runner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/cairo-lang-sierra-gas-2.2.0/src/compute_costs.rs:348:29
stack backtrace:
   0: _rust_begin_unwind
   1: core::panicking::panic_fmt
   2: cairo_lang_sierra_gas::compute_costs::CostContext<CostType>::prepare_wallet_at
   3: cairo_lang_sierra_gas::compute_costs::compute_costs
   4: cairo_lang_sierra_to_casm::metadata::calc_metadata
   5: cairo_lang_test_runner::TestRunner::run
   6: scarb_cairo_test::main
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
error: process did not exit successfully: exit status: 101

The bug manifests when running scarb test in this branch: https://github.com/kkrt-labs/kakarot-ssj/tree/feat/nested-contexts
Expected behavior:

Steps to reproduce:

Related code:

Reproducible examples:

1. Using Nullable

use nullable::{match_nullable, FromNullableResult};

#[derive(Destruct)]
struct A {
    a: Nullable<A>,
}

impl NullableADestruct of Destruct<Nullable<A>> {
    fn destruct(self: Nullable<A>) nopanic {
        match match_nullable(self) {
            FromNullableResult::Null => {},
            FromNullableResult::NotNull(value) => value.unbox().destruct(),
        }
    }
}

#[test]
fn test_cycle() {
    let a = A { a: Default::default() };
}

2. Using Box<Option>

use nullable::{match_nullable, FromNullableResult};

#[derive(Destruct)]
struct A {
    a: Box<Option<A>>,
}

impl BoxADestruct of Destruct<Box<Option<A>>> {
    fn destruct(self: Box<Option<A>>) nopanic {
        match self.unbox() {
            Option::Some(value) => value.destruct(),
            Option::None => {},
        }
    }
}

#[test]
fn test_cycle() {
    let a = A { a: BoxTrait::new(Option::None) };
}

Other information:

[orizi]

This requires cost tokens to be pre-charged, as the destruct in this case is recursive.
This isn't going to be a simple solve, so I cannot begin to tell you when this will be fixed.
Is there a way to avoid the dict within the structure here?

[enitrat]

Unfortunately not, it's impossible to avoid having the Dict inside this struct. Kakarot's EVM relies on dicts for the implementation of the Memory, the Stack, and a few other elements. All of them are grouped relative to their ExecutionContext.

This is a big blocker for us as we're not able to spawn subcontexts (we can't implement the behavior of a call to other contracts)

[orizi]

i don't really like my solution, but i believe it would work:
Instead of holding a dictionary in the recursive struct, hold an id to an external dictionary there.
Then use that external id for access to an outside dict.

[enitrat]

hold an id to an external dictionary there.

What do you mean by id?
Let's say I want to get rid of all n dict-based substructs in my struct - I would hold an n IDs to what exactly?

[orizi]

struct Context {
... // The context non-dict info.
parent: Nullable,
id: u64, // The sequence number of the generated context.
}

memory_dict: Felt252Dict,

used by Hash(id, mem_addr) as key.

[enitrat]

If we don't have the choice then we will proceed this way but it involves refactoring the entire architecture, which we would like to avoid.

[orizi]

I don't see any other choice for the time being unfortunately.

Do note that a wrapper object holding both the dictionary and the current context is possible for abstracting most of this away.
(so in any case you would have accessed the original context you'd still access a rather similar object).