Memory operations should sometimes accept an Integer

[notlesh]

Describe the bug

The pythonic implementation of some memory operations accepts either an integer or a relocatable in some isolated cases. These cases are used by cairo-lang and break the OS when not supported.

This issue replaces #1856 which assumed that the downstream problem was caused by the way cast(0, felt*) was used. However, the behavior described there is consistent with the way the pythonic implementation works (see code below), so I will close it as "works as intended."

There are two specific functions used in the OS that depend on support for integers, discussed below.

add_relocation_rule()

Source, called from here.

While the python code clearly declares dest_ptr: RelocatableValue, neither function does any checks against it (except assert src_ptr = dest_ptr; in the latter; note that this assert makes it impossible to work around the issue).

Consider the following code snippet which demonstrates that the relocation system works transparently when dest_ptr is a felt and not a felt*:

from starkware.cairo.common.segments import relocate_segment

func main() {
    alloc_locals;

    local temp_segment: felt*;
    local temp_segment_2: felt*;

    %{
        ids.temp_segment = segments.add_temp_segment()
        ids.temp_segment_2 = segments.add_temp_segment()

        # the following prints "-1:0"
        print("temp_segment before relocation:", ids.temp_segment)

        # the following prints "-2:0"
        print("temp_segment_2 before relocation:", ids.temp_segment_2)

    %}

    relocate_segment(src_ptr=temp_segment, dest_ptr=ptr_from_cast_0);
    relocate_segment(src_ptr=temp_segment_2, dest_ptr=ptr_from_cast_1);

    %{
        # the following prints "0"
        print("temp_segment after relocation:", ids.temp_segment)

        # the following prints "1"
        print("temp_segment_2 after relocation:", ids.temp_segment_2)
    %}

    ret;
}

get_range()

Source

Similarly, this function is happy to operate on addr of type felt so long as size == 0. Unlike the add_relocation_rule() issue, this one may be easy to workaround.

Consider the following code snippet which clearly shows that get_range can be called as described above:

func main() {
    alloc_locals;

    let ptr_from_cast_0: felt* = cast(0, felt*);
    let ptr_from_cast_1: felt* = cast(1, felt*);

    %{
        # note that ptr_from_cast_0 and ptr_from_cast_1 are both internally treated as felt
        # and not felt*:
        # the following prints "0"
        print("ptr_from_cast_0:", ids.ptr_from_cast_0)
        # the following prints "1"
        print("ptr_from_cast_1:", ids.ptr_from_cast_1)

        # get_range(0,0) works
        range = memory.get_range(ids.ptr_from_cast_0, 0)
        # the following prints "[]"
        print("get_range(0,0)", range)

        # get_range(1,0) works
        range = memory.get_range(ids.ptr_from_cast_1, 0)
        # the following prints "[]"
        print("get_range(1,0)", range)

        # get_range(0,1) fails
        # range = memory.get_range(ids.ptr_from_cast_0, 1)

        # get_range(1,1) fails
        # range = memory.get_range(ids.ptr_from_cast_1, 1)
    %}
}

To Reproduce
Compile (with cairo-compile) the above code snippets and run with cairo-run, e.g.:

cairo-compile test_cast.cairo --output test_cast_compiled.json
cairo-run --program=test_cast_compiled.json --print_output --print_info --relocate_prints

Expected behavior

Changing the underlying types used by cairo-vm to be MaybeRelocatable could fix this. It seems like a step backwards in sanity, but it does support the behavior that is required by the OS.

I'll propose a concrete suggestion (and I'm happy to implement it, although I'd love feedback as well):

• Modify the relocation_rules table here to be a HashMap<usize, MaybeRelocatable>
• Keep existing accessors for adding a relocation rule (that is, the functions which accept Relocatable)
• Add new functions which accept a MaybeRelocatable and give them an obnoxious name like fn add_relocation_rule_maybe_relocatable()

What version/commit are you on?

git commit 58363ad8065ed891e3b14a8191b707677c7c7cb5b9d10030822506786d8d8108 (roughly v1.0.1)

Additional context

These requirements come from the OS code in cairo-lang. They are very much corner cases as well (triggered in fewer than 1% of blocks on Sepolia testnet), which suggests that the behavior may not be intentional. It could be argued that these are bugs in the OS code... 🤷