[BUG]: Compiler Crash with Self Referential Variant

[lsh]

Bug description

from utils.variant import Variant
from collections.vector import DynamicVector


@value
struct Value(CollectionElement):
    alias Variant = Variant[Float64, DynamicVector[Value]]
    var _variant: Self.Variant

    @always_inline
    fn __moveinit__(inout self, owned rhs: Self):
        self._variant = rhs._variant

    @always_inline
    fn __copyinit__(inout self, rhs: Self):
        self._variant = rhs._variant


fn main():
    pass

outputs:

[68451:5573323:20240229,122117.821876:WARNING crash_report_exception_handler.cc:257] UniversalExceptionRaise: (os/kern) failure (5)
fish: Job 1, 'mojo main.mojo' terminated by signal SIGILL (Illegal instruction)

Note that doing the following does not fix the issue:

from utils.variant import Variant
from collections.vector import DynamicVector


alias T = Variant[Float64, Delegate]


@value
struct Delegate(CollectionElement):
    var _data: DynamicVector[Value]


@value
struct Value(CollectionElement):
    var _variant: T

    @always_inline
    fn __moveinit__(inout self, owned existing: Self):
        self._variant = existing._variant

    @always_inline
    fn __copyinit__(inout self, existing: Self):
        self._variant = existing._variant


fn main():
    pass

It outputs:

recursive reference to declaration

And moving the alias beneath Delegate outputs this error instead:

'Variant' parameter #0 has 'CollectionElement' type, but value has type 'Delegate'

System information

- What OS did you do install Mojo on ? macOS
- Provide version information for Mojo by pasting the output of `mojo -v`:  mojo 24.1.0 (55ec12d6)
- Provide Modular CLI version by pasting the output of `modular -v`: modular 0.4.1 (2d8afe15)

[lsh]

More minimal version:

from utils.variant import Variant
from memory.unsafe import Pointer


@value
struct Value(CollectionElement):
    alias Variant = Variant[Float64, Pointer[Self]]
    var _variant: Self.Variant


fn main():
    pass

outputs

[69714:5614294:20240406,122210.916482:WARNING crash_report_exception_handler.cc:257] UniversalExceptionRaise: (os/kern) failure (5)
fish: Job 1, 'mojo main.mojo' terminated by signal SIGBUS (Misaligned address error)

with

- modular 0.6.0 (04c05243)
- mojo 2024.4.117 (8f6529b0)

[lattner]

I spent some time looking into this and it completely twists my brain. The problem is that we're infinitely recursing in the internal LowerLITTypes pass when lowering types and attributes involving Value. The issue is that we're recursively lowering attributes like vtable entries and other stuff that isn't part of hte struct layout itself, because it is recursively reachable through the type references in the !kgen.variant type attribute list, and we never go through a !kgen.pointer which would break the cycle.

I'm not sure the right way to solve this. Perhaps handle vtable entries specially - they are fundamentally pointer like. There is something pointer like that I'm not understanding here. @weiweichen can you investigate this?

[weiweichen]

I spent some time looking into this and it completely twists my brain. The problem is that we're infinitely recursing in the internal LowerLITTypes pass when lowering types and attributes involving Value. The issue is that we're recursively lowering attributes like vtable entries and other stuff that isn't part of hte struct layout itself, because it is recursively reachable through the type references in the !kgen.variant type attribute list, and we never go through a !kgen.pointer which would break the cycle.

I'm not sure the right way to solve this. Perhaps handle vtable entries specially - they are fundamentally pointer like. There is something pointer like that I'm not understanding here. @weiweichen can you investigate this?

Sure, I'll take a look. Also @willghatch, might also need some idea from you about vtables.