Defining scope of existential type defined by associated type

[alexreg]

So, during our discussion earlier today, @nikomatsakis brought up this interesting example of code that should really compile, we think:

existential type X: Sized;

trait Foo {
    type Bar: Iterator<Item = Self::_0>;
    type _0;
}

impl Foo for () {
    type Bar = std::vec::IntoIter<u32>;
    type _0 = X;    
}

Error:

error: could not find defining uses
 --> src/main.rs:3:1
  |
3 | existential type X: Sized;
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^

Playground

It seems that type _0 = X; isn't being considered as a "defining use", even though it clearly does constrain X. The question is, what sort of changes do we need for this to work? (I'm pretty sure it should work.) Do we need Chalk perhaps?

CC @nikomatsakis @cramertj @scalexm

[cramertj]

cc @oli-obk

[oli-obk]

I'm not surprised this doesn't work. "defining uses" are hardcoded to be function bodies (either by return value or by let binding) right now.

While type _0 = X; does constrain X to u32, there is no nice graph of constraints to follow to this conclusion. If it's something Chalk can do while still producing helpful diagnostics, I'd totally love it if we had such complex cases.

I'm not sure we want to support this though, as it is very hard to reason about, and it also seems slightly weird that we now know that X is i32 (via Bar::Item) outside of this module.

In any way, the implications are well beyond what was suggested in the RFC and I am very certain we'd need an RFC for anything in this direction.

[nikomatsakis]

I don't think a new RFC is warranted per se. I think that tweaking the idea of what a "defining use" is falls pretty squarely under the "experiment in master" heading.

(In fact, I'll have to re-read the RFCs, but I'm not sure they even include the concept of defining uses, do they?)

In any case, if we want to support impl Trait in positions like this one:

trait Foo {
    type Bar: Iterator<Item = impl Display>
}

which I think we do, as that is part of RFC 2289, right?

[alexreg]

I think what @nikomatsakis says intuitively makes sense. I'll try to do some experimentation there, but any advice on how to go about implementing it would be much appreciated.

[Centril]

(In fact, I'll have to re-read the RFCs, but I'm not sure they even include the concept of defining uses, do they?)

Not in so many words, but it quite explicitly talks about bodies:

Each existential type declaration must be constrained by at least one function body or const/static initializer. A body or initializer must either fully constrain or place no constraints upon a given existential type.

---

which I think we do, as that is part of RFC 2289, right?

Not with that syntax, no. It's also not super clear what that means; it could either be an existential type _0: Display; in the scope of the trait (or module), or merely a bound <Self::Bar as Iterator>::Item: Display.

As for needing an RFC; I think that depends on how far reaching implications the suggested change has re. complier, user, and type system complexity.

[oli-obk]

I think that tweaking the idea of what a "defining use" is falls pretty squarely under the "experiment in master" heading.

My worry is less about whether it's in the spirit of the RFC (it definitely is), but more about the kind of constraints used to figure out an existential type's concrete type.

Right now there's a obvious ordered dependency tree for computing the concrete type: when run the type_of query on an existential type, all TypeckTables in the same module or in a submodule are checked for concrete types.

If we added the system proposed above with a similar scheme, we'd need to start creating TypeckTables for associated types and figure out when we want an existential type use in an associated type to be defining or just using.

And while thinking about the latter I realized that I utterly misread the example... So consider my worries moot. It should be simple enough extend the search space for defining uses from bodies to also include associated type definitions in impl blocks.

[jackh726]

Modern repro:

#![feature(type_alias_impl_trait)]

type X = impl Sized;

trait Foo {
    type Bar: Iterator<Item = Self::_0>;
    type _0;
}

impl Foo for () {
    type Bar = std::vec::IntoIter<u32>;
    type _0 = X;    
}

fn main() {}

playground

[nikomatsakis]

min_type_alias_impl_trait

This actually feels like a blocker, I think this should count as a "defining use".

[oli-obk]

I need to run some traces, but I'm assuming we're actually figuring out the hidden type, but not storing it somewhere where we can find it again.

Should this block stabilization? It seems forward compatible to allow later

[nikomatsakis]

This appears to be a result of overlooking obligations, as @oli-obk suggested, here is an example that causes an ICE (but ought to error in type checking):

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=ff7b2e0a740ca9264da708753e2fe3d3

#![feature(type_alias_impl_trait)]

type X = impl Sized;

trait Foo {
    type Bar: Iterator<Item = X>;
}

impl Foo for () {
    type Bar = std::vec::IntoIter<u32>;
}

fn incoherent() {
    let f: X = 22_i32;
}

fn main() {}

[oli-obk]

The problem as debugged by @ouz-a is that the hidden type of X is only determined during well-formedness checking. This is because only in wf checking we check that an associated type in an impl satisfies the bounds on the trait definition. Regular type checking ignores the bounds.

I worry that there are more similar cases lurking in the compiler, so we're going to expose them as type mismatch errors for now and then look into whether they can be made to compile successfully with reasonable compiler changes.

[nikomatsakis]

@oli-obk and I discussed this today. My take is that it is fine if this code gives an error. We can always adapt it later -- but there is no backwards compatibility risk, the only code that would successfully compile is code that works independently of the value of X, or an impl that (independently) constraints X to be u32, such as this one (playground):

#![feature(type_alias_impl_trait)]

type X = impl Sized;

trait Foo {
    type Bar: Iterator<Item = X>;
    
    fn into_bar(self) -> Self::Bar;
}

impl Foo for () {
    type Bar = std::vec::IntoIter<X>;
    
    fn into_bar(self) -> Self::Bar {
        vec![22, 44].into_iter()
    }
}

fn incoherent() {
    let f: X = 22_i32;
}

fn main() {}