Stack overflow when bounding FnOnce with Send + 'static

@nikomatsakis

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

@alexcrichton

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

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

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.

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.

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() { }

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.

When generating WF criteria, do not visit the same type more than

Rollup merge of rust-lang#23013 - nikomatsakis:syncbox, r=pnkfelix

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

@nikomatsakis

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)

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

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

@nikomatsakis

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.

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

Merge pull request rust-lang#23003 from A4-Tacks/coerce-func-param-comp

Navigation Menu

Repository navigation

Stack overflow when bounding FnOnce with Send + 'static #23003

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Stack overflow when bounding FnOnce with Send + 'static #23003

Description

Activity

carllerche commented on Mar 3, 2015

nikomatsakis commented on Mar 3, 2015

nikomatsakis commented on Mar 3, 2015

nikomatsakis commented on Mar 3, 2015

nikomatsakis commented on Mar 3, 2015

nikomatsakis commented on Mar 4, 2015

arielb1 commented on Mar 5, 2015

frewsxcv commented on Apr 25, 2015

frewsxcv commented on Apr 25, 2015

apasel422 commented on Oct 24, 2015

steveklabnik commented on Oct 24, 2015

apasel422 commented on Oct 25, 2015

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions