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.

[arielb1]

A mutated version (without Sized) causes a rustc stack overflow/illegal instruction:

use std::marker;

trait Async {
    type Cancel;
}

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

struct Complete<B: ?Sized> {
    core: marker::PhantomData<B>,
}

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

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

fn main() { }

The overflow is weird, because you can have impl<T> Foo for S<T> { type Ty = S<Option<T>>; }

[frewsxcv]

This is still an issue using Rust 1.0 beta 2

Full error message (compiling @nikomatsakis's latest code block): https://gist.githubusercontent.com/frewsxcv/c74c589b42675c5e5df7/raw/f0d4224d119fcf51db9d48c83fa266c0e955f4bd/gistfile1.txt

~/Downloads $ rustc --version
rustc 1.0.0-beta.2 (e9080ec39 2015-04-16) (built 2015-04-16)

[frewsxcv]

The I-ICE label can probably be removed, unless there is still an ICE issue here

[apasel422]

It appears that all example code in this issue now compiles on nightly.

[steveklabnik]

Okay! As such, let's add e-needstest, and let's get a test for @nikomatsakis 's last code block as a representatitve of this issue. I'd be happy to help anyone who wants to tackle this.

[apasel422]

This actually has a test already in src/test/run-pass/traits-issue-23003.rs and can be closed.