Working around "overflow adding drop-check rules"

[Yorwba]

It's easy to create pathological types like the one below

struct Rec<T> {
    item: T,
    rec: Option<Box<Rec<Rec<T>>>>,
}

fn main() {
    let e: Option<Rec<usize>> = None;
}

that fails to compile (Playground) with the error message below

error[E0320]: overflow while adding drop-check rules for std::option::Option<Rec<usize>>
 --> src/main.rs:7:9
  |
7 |     let e: Option<Rec<usize>> = None;
  |         ^
  |
  = note: overflowed on Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<Rec<usize>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

However, there's a workaround: replacing Box<T> with Box<dyn The<Type=T>> where The is a trait defined as follows:

trait The {
    type Type;
    fn self_ref(&self) -> &Self::Type;
    fn self_mut(&mut self) -> &mut Self::Type;
    fn self_own(self) -> Self::Type;
}

impl<T> The for T {
    type Type = Self;
    fn self_ref(&self) -> &Self {
        self
    }
    fn self_mut(&mut self) -> &mut Self {
        self
    }
    fn self_own(self) -> Self {
        self
    }
}

struct Rec<T> {
    item: T,
    rec: Option<Box<dyn The<Type=Rec<Rec<T>>>>>,
}

fn main() {
    let e: Option<Rec<usize>> = None;
}

and then the program compiles without errors. (Playground)

As far as I can tell, Box<T> and Box<dyn The<Type=T>> are functionally equivalent, except that the second one requires an additional method call to get at the T. In particular, I don't think they should behave differently with respect to lifetimes and dropping.

So here are my questions:

1. Is there any situation where Box<dyn The<Type=T>> cannot be used as a replacement for Box<T>?
2. Why does drop-checking not overflow with the trait?
3. Is this sound? If not, too bad, if yes, could the drop-checking rule be rewritten to treat the two situations the same?

[sfackler]

The fact that the overflow happens at the drop-checker is kind of irrelevant. The core problem is that your original definition requires the creation of an infinite set of types. The type Rec<()> contains the type Rec<Rec<()>>, which contains the type Rec<Rec<Rec<()>>>, which contains the type Rec<Rec<Rec<Rec<()>>>>, etc. The compiler is not willing to examine an infinite number of types regardless of which bit of analysis runs first.

[alice]

The difference is that the drop code for Rec<T> must contain a hard-coded pointer to the drop function for Rec<Rec<T>>, which must then recursively contain a hard-coded pointer, and so on. On the other hand, a trait object includes the drop code as part of the vtable, which is stored by the box, so the drop code for Rec<T> is easy, just call the function pointer from the vtable.

As for when the drop-code behind that vtable is generated, well it's generated at the point where you convert a Box<Rec<Rec<T>>> into a Box<dyn The<Type = Rec<Rec<T>>>>. If you never construct such a box, that drop code is never generated.

Note that this means that you can never write a program that builds an infinitely deep Rec<T>. You must have a piece of code for creating the box for each level.

[Yorwba]

Thank you for the replies. The drop function being hard-coded vs. included in the vtable of the trait object is exactly the explanation I needed.

As for generating an arbitrarily deep Rec<T>, I did try just now and ran into the type length limit, so it does seem to be impossible. Fortunately, in my actual use case the number of recursion levels is finite and known at compile time; I just didn't want to manually duplicate the shared structure for each level.