Stack overflow when bounding FnOnce with Send + 'static

[carllerche]

I'm not exactly sure what is happening, but I thought I would file an issue. I am attempting to update syncbox (https://github.com/carllerche/syncbox). I have to add 'static bounds to types that were previously only bound by Send, however it seems to be causing stack overflow errors in rustc.

I could not make a simple repro, but here is the code in a single file:

https://gist.github.com/carllerche/7961c85b171c829cd625

cc @nikomatsakis

[carllerche]

mr. @alexcrichton has used creduce to reduce the case:

use std::marker::PhantomData;
use std::sync::atomic::AtomicUsize;
struct Receipt<A: Async> {
    core: (),
    count: u64,
    marker: PhantomData<A>,
}
struct Complete<T, E> {
    core: Option<Core<T, E>>,
}
impl <T: Send, E: Send> Async for Complete<T, E> {type
    Cancel
    =
    Receipt<Complete<T, E>>;
}

impl <T: Send, E: Send> Cancel<Complete<T, E>> for Receipt<Complete<T, E>> {
    fn cancel(self) -> Option<Complete<T, E>> { }
}

struct Core<T, E> {
    refs: AtomicUsize,
    state: AtomicState,
    consumer_wait: Option<Callback<T, E>>,
    producer_wait: Option<Callback<T, E>>,
    val: AsyncResult<T, E>, //
}
struct AtomicState;
type Callback<T, E> = Box<BoxedReceive<Core<T, E>>>;
trait Async {type Cancel: Cancel<Self>; }
trait Cancel<A> {
    fn cancel(self) -> Option<A>;
}
type AsyncResult<T, E> = Result<T, AsyncError<E>>;
enum AsyncError<E> { ExecutionError(E), }
trait BoxedReceive<T> {
    fn receive_boxed(Box<Self>, T);
}

[nikomatsakis]

This was caused by fixing #22246 (PR #22436 in particular). I have to think on what's the best fix here.

[nikomatsakis]

Just FYI, you can workaround the problem by removing the A:Async bound from Receipt. What happens is that, per #22246, for Result<A> to be legal in some context with lifetime 'x, it winds up requiring that A::Cancel :'x, which in turn isresult : 'x`. Probably the fix is just to check that we don't reach the same type again. This wasn't necessary before because types were always of finite size.

[nikomatsakis]

So adding a cache is probably the way to fix this crash. What worries me is that the set of types might be ever-expanding. We could add a recursion depth to counter that but it feels like it might rule out potentially legitimate types? I guess they can probably always be phrased differently. Let me try to work up a concrete example of what I mean.

[nikomatsakis]

Reduced more:

use std::marker::PhantomData;

trait Async {
    type Cancel;
}

struct Receipt<A:Async> {
    marker: PhantomData<A>,
}

struct Complete {
    core: Option<()>,
}

impl Async for Complete {
    type Cancel = Receipt<Complete>;
}

fn foo(r: Receipt<Complete>) { }

fn main() { }

[nikomatsakis]

This variant generates (at least in my version, which contains a fix for the above issue), an overflow error:

use std::marker::PhantomData;

trait Async {
    type Cancel;
}

struct Receipt<A:Async> {
    marker: PhantomData<A>,
}

struct Complete<B> {
    core: Option<B>,
}

impl<B> Async for Complete<B> {
    type Cancel = Receipt<Complete<Option<B>>>;
}

fn foo(r: Receipt<Complete<()>>) { }

fn main() { }

The reason is because Complete<()>::Cancel, normalized, is Receipt<Complete<Option<()>>>, which in turn expands out to Receipt<Complete<Option<Option<()>>>> and so forth.

I am not sure if this overflow error is entirely legitimate -- by which I mean, it falls out of the rules as we have them today, but it doesn't feel entirely necessary.