Cycle detected when processing existential type

[Nemo157]

playground

#![feature(existential_type)]

use std::rc::Rc;

existential type Foo: Fn() -> usize;

fn foo() -> Foo {
    let rc = Rc::new(5);
    move || { *rc.as_ref() }
}

fn assert_send<T: Send>(_: &T) {
}

fn main() {
    let f = foo();
    assert_send(&f);
    println!("{}", f());
}

error[E0391]: cycle detected when processing `Foo`
 --> src/main.rs:5:1
  |
5 | existential type Foo: Fn() -> usize;
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: ...which requires processing `main`...
 --> src/main.rs:15:1
  |
15| fn main() {
  | ^^^^^^^^^
note: ...which requires evaluating trait selection obligation `Foo: std::marker::Send`...
  = note: ...which again requires processing `Foo`, completing the cycle

Commenting out the assert_send(&f); line compiles and runs fine (playground), moving Foo and foo into a sub-module correctly identifies that Foo: !Send (playground).

[Arnavion]

I almost filed a duplicate for this. Can someone please tag this A: impl trait ?

Separately, is it intentional that existential types don't auto-implement auto traits like impl Trait does?

[Nemo157]

It appears that existential types do leak auto traits: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=de5ba08a8f48bd7859c252c9ba81c849

[oli-obk]

It appears that existential types do leak auto traits

That is intended by the RFC. At least it was for impl Trait. And we really want to keep the two in sync.

[oli-obk]

moving Foo and foo into a sub-module correctly identifies that Foo: !Send

That is actually the intended behavior (at least by me). I specifically implemented existential types in a way that mean every use inside the current module or a submodule will be checked for being a defining use.

We should definitely improve the error message though. It should point to the assert_send call and mention that moving Foo and the functions that actually are defining uses to a submodule will probably fix the error.

[Arnavion]

I guess I understand the rules (current and submodules are defining uses + auto-trait impls are only inferred outside the defining scope), but the overall experience is this:

1. If the existential type explicitly impls Send (existential type Foo: Debug + Send;), then both submodules and other modules will see that the type impls Send.

2. If the existential type doesn't explicitly impl Send (existential type Foo: Debug;), and the defining use does not explicitly require Send, then other modules will see that the existential type actually does impl Send. (Nemo157's second comment)

3. ... but if a submodule does require Send, the compiler will raise an error. (OP)

I feel this will be a big source of confusion because of how contradictory it seems. "Testing that the type impls Send makes it not impl Send. Leaving it untested makes it impl Send." I hope the error message can elaborate that submodules count as defining uses, maybe list all the uses or something.

The code that I had a problem was a unit test, something like this:

pub existential type Foo: Debug;

pub fn foo() -> Foo {
    5
}

#[cfg(test)]
mod tests {
    #[test]
    fn test_foo() {
        assert_send(foo());
    }
}

cargo build was fine but cargo test failed. assert_send-style tests are useful for API-compatibility checks (example), so if these were unit tests they would end up breaking the very thing they were trying to test.

The "move to a submodule" strategy will mean either the unit test has to move to the parent module, or I would have to make a temporary inner module for foo() and Foo and re-export them.

It'll also look weird if foo() was an inherent method of a struct, and there were many such methods. I might have to split each such method into its own impl block and put each block in a separate submodule, depending on what unit tests I happened to write.

For my own case I solved it by doing option 1, ie I added an explicit + Send bound to the existential type definition, which is ugly considering it would've been Send anyway, but seems preferable to artificially introducing an inner module.

[oli-obk]

The problem is that I don't see any way we can detect ahead of time that test_foo is not a defining use without failing to see foo to be a defining use.

The RFC on existential types also talks about let x: Foo = ...; being a defining use, so we can't just rule out functions that don't have a Foo in their return type. If assert_send were fn assert_send(x: Foo), test_foo would be a defining use if it called assert_send(42) directly.

So we do need to process test_foo.

I just had an idea while writing this text. Maybe we can defer the checking of such "magic" bounds (Send + Sync an existential types) to after the query finishes. I'll have a look.

[oli-obk]

@eddyb back when you created impl Trait, you added a test (08bf9f6#diff-d02a448934e98c0862197c125d781a21) which needed "deferred obligations" (due to the old typeck not having query powers) that allowed functions to know about Send and Sync of functions that came after them. That system was removed in favour of queries having a clear order. I don't want to reintroduce such a thing (since it seems strictly at odds with the query idea).

Then again, the way existential types work, they violate how queries run by going through every function in their parent module and checking them for some information that only can be inferred by their body.

This is not much of a problem for impl Trait, because there's a clear order. Existential types on the other hand basically go backwards in the query graph.

[Arnavion]

The problem is that I don't see any way we can detect ahead of time that test_foo is not a defining use without failing to see foo to be a defining use.

Just to be clear, I think the current implementation is fine. But submodules or tests can end up being unexpected defining uses (submodules, tests), so I'd like the error to be clear what they are. Eg:

error[E01234]: Multiple contradictory defining uses of `Foo` were found:

1. src/lib.rs:x:y | existential type Foo: Debug;

    defines `Foo` as `std::fmt::Debug`

2. src/lib.rs:x:y | assert_send(foo());

    defines `Foo` as `Send` because of the definition of `assert_send`

All uses of `Foo` in the module where it's defined and its submodules must agree on the bounds.

It can then suggest moving to a submodule as you said, or explicitly adding + Send to the definition.

---

I suppose it's too late to require an "explicit" defining use like fn foo() -> defines Foo { 5 } to resolve the ordering problem?

[oli-obk]

2. src/lib.rs:x:y | assert_send(foo());

    defines `Foo` as `Send` because of the definition of `assert_send`

That's not actually the issue. The issue is that we are looking at main to find any defining uses (and we aren't finding any), but in order to look for defining uses, main needs to get typechecked. The act of type-checking needs to check whether Foo: Send, and to check that we need to know the concrete type of Foo, which we are in the process of computing in an earlier query.

[oli-obk]

Oops, wrong button.

I suppose it's too late to require an "explicit" defining use like fn foo() -> defines Foo { 5 } to resolve the ordering problem?

We can go back, that's no problem, everything is still behind a feature gate, but the RFCs explicitly state that we want let bindings to be defining uses. Thus we need to either work with it or reevaluate that feature. My personal opinion is to go with it and figure out better diagnostics and/or allow more code by some more fine-grained type checking.

[Arnavion]

The let-binding equivalent would be let x: defines Foo = 5;, but anyway I agree with you.

[oli-obk]

Oh, heh, I misunderstood what you wrote. You acutally want a defines keyword? That's an interesting proposition. I'll see how far we can get with improved diagnostics, but keep explicit defining uses in mind.

[Aaron1011]

I think the simplest approach would be to require explicitly adding the auto-trait as a bound to the impl trait definition.

That is, instead of writing type Foo = impl Fn() -> usize, you would write type Foo = impl Fn() -> usize + Send. Note this will already resolve the cycle error on the latest compiler.

It's important to note that the auto traits 'leaked' by an impl trait (both RPIT and type-alias) implicitly create a Semver guarantee. That is, downstream crates can write code that relies on a particular impl trait also implementing an auto trait (e.g. Send), which will break if the underlying type stops implementing that auto trait.

Adding the auto trait as a bound in the definition just makes this more explicit. It doesn't actually promise anything more (even though it may look like it at first), and avoids the need for any complicated handling of auto-trait predicates.

It would probably be a good idea to detect these kinds of cycle errors, and emit a suggestion to add the auto-trait as a bound.

EDIT: This won't work when the underlying type is generic and doesn't implement the auto trait unconditionally.

[jackh726]

Modern repro:

#![feature(type_alias_impl_trait)]

use std::rc::Rc;

type Foo = impl Fn() -> usize;

fn foo() -> Foo {
    let rc = Rc::new(5);
    move || *rc.as_ref()
}

fn assert_send<T: Send>(_: &T) {}

fn main() {
    let f = foo();
    assert_send(&f);
    println!("{}", f());
}

playground

[nikomatsakis]

playground using min_type_alias_impl_trait

[nikomatsakis]

I think this is "behaving as expected". It's certainly not a blocker for stabilization. It would be nice if this worked, but it's ultimately expected based on the current implementation.

[oli-obk]

We should make the cycle diagnostic point at the assert_send call. Other than that, this issue works as intended for now