Recursive traits should be allowed when boxing

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");
}

1. cc @nikomatsakis

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

   Aaron Turon at 2014-10-09 18:06:04

2. 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
   
   

   Steve Klabnik at 2016-02-02 22:10:14

3. 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
   
   

   Steve Klabnik at 2018-09-24 17:34:50

4. 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 at 2022-01-26 20:38:52

5. 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 https://github.com/rust-lang/rust/issues/88904? Will https://github.com/rust-lang/rust/issues/107374 -Ztrait-solver=next help? Does this require coinduction?

   MRE:

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

   dimpolo at 2023-09-18 18:22:18