Recursive traits should be allowed when boxing

[carllerche]

The following should work:

trait Future<T> {
    fn take(self) -> T;
}

trait Stream<T>: Future<Option<(T, Box<Stream<T>>)>> {
}

pub fn main() {
    println!("zomg");
}

[aturon]

cc @nikomatsakis

Currently gets the error "error: illegal recursive type; insert an enum or struct in the cycle, if this is desired"

[steveklabnik]

Triage: current error:

hello.rs:5:40: 5:49 error: unsupported cyclic reference between types/traits detected [E0391]
hello.rs:5 trait Stream<T>: Future<Option<(T, Box<Stream<T>>)>> {
                                                  ^~~~~~~~~
hello.rs:5:40: 5:49 help: run `rustc --explain E0391` to see a detailed explanation
note: the cycle begins when computing the supertraits of `Stream`...
note: ...which then again requires computing the supertraits of `Stream`, completing the cycle.
hello.rs:5:40: 5:49 error: unsupported cyclic reference between types/traits detected [E0391]
hello.rs:5 trait Stream<T>: Future<Option<(T, Box<Stream<T>>)>> {
                                                  ^~~~~~~~~
hello.rs:5:40: 5:49 help: run `rustc --explain E0391` to see a detailed explanation
note: the cycle begins when computing the supertraits of `Stream`...
note: ...which then again requires computing the supertraits of `Stream`, completing the cycle.
error: aborting due to 2 previous errors

[steveklabnik]

New error:

error[E0391]: cycle detected when computing the supertraits of `Stream`
 --> src/main.rs:5:1
  |
5 | trait Stream<T>: Future<Option<(T, Box<Stream<T>>)>> {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: ...which again requires computing the supertraits of `Stream`, completing the cycle

[dimpolo]

I would also like to see this.
My use case is a custom Rc implementation with cycle detection, specifically designed for trait objects.
Code would look something like this:

use core::marker::PhantomData;

// API:

pub struct Rc<Dyn: ?Sized + Trace<Dyn>>{
    ptr_and_stuff: PhantomData<Dyn>,
}

pub trait Trace<Dyn: Trace<Dyn> + ?Sized> {
    /// Give the tracer access to other Rc<Dyn> that we own.
    /// Their `Dyn` must be the same as ours. 
    fn trace(&self, tracer: fn(&Rc<Dyn>));
}

// user code:

trait MyTrait: Trace<dyn MyTrait>{}

struct MyStruct{
    field: Rc<dyn MyTrait>,
}

impl Trace<dyn MyTrait> for MyStruct {
    fn trace(&self, tracer: fn(&Rc<dyn MyTrait>)){
        tracer(&self.field);
    }
}

The hacky workarounds found on stackoverflow sadly don't work.

[dimpolo]

Could someone comment if this has a chance to get accepted in the future?
Is the problem that dyn Trait doesn't always implement Trait #88904?
Will #107374 -Ztrait-solver=next help?
Does this require coinduction?

MRE:

trait Foo<T: ?Sized> {}
trait Bar: Foo<dyn Bar> {}