Make this monomorphization not overflow?


#1

I’ve got a program that involves infinite recursion. I happen to know that this recursion will always terminate in practice, but this recursion involves constructing nested types. As a result, I’m getting an overflow during monomorphization. A very boiled down example is:

trait Any {}
impl<T> Any for T {}

fn into_option<T>(t: T) -> Option<impl Any> {
    Some(into_option(t))
}

fn main() {
    let _ = into_option(0u8);
}

The problem is that there is no correct monomorphization of the type of into_option(0u8). It’s Option<Option<Option<...>>> ad infinitum.

I figured that what I really want to do is make it so that, if I already have an Option<T>, instead of wrapping it again, I can just return it directly. I figured I could do this using the new impl specialization feature:

#![feature(specialization)]

trait Any {}
impl<T> Any for T {}

fn into_option<T>(t: T) -> Option<impl Any> {
    // Types which can produce an Option<A>
    trait IntoAny<A: Any> {
        fn into_any(self) -> Option<A>;
    }
    // Any type can produce an Option<A> by wrapping itself in Some
    impl<A: Any> IntoAny<A> for A {
        default fn into_any(self) -> Option<A> {
            Some(self)
        }
    }
    // An Option<A> can produce an Option<A> just by returning itself
    impl<A: Any> IntoAny<A> for Option<A> {
        fn into_any(self) -> Option<A> {
            self
        }
    }
    into_option(t.into_any())
}

fn main() {
    let _ = into_option(0u8);
}

Unfortunately, this still doesn’t compile:

error[E0275]: overflow evaluating the requirement `impl Any: std::marker::Freeze`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because it appears within the type `impl Any`
  = note: required because it appears within the type `impl Any`
  ...

Is there any way to get this to compile, or am I just stuck?


#2

Code that can terminate might be better example. Without the Option is just as much infinite recursion. (Just makes compiler panic)

fn into_option<T>(t: T) -> impl Any {
    into_option(t)
}