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