Stream: wg-async-foundations

Topic: type parameter out of range #55872


nikomatsakis (Jun 13 2019 at 17:07, on Zulip):

hi @davidtwco

davidtwco (Jun 13 2019 at 17:07, on Zulip):

:wave:

nikomatsakis (Jun 13 2019 at 17:07, on Zulip):

let's try zulip

nikomatsakis (Jun 13 2019 at 17:08, on Zulip):

better logs..plus I have a lot of calls today and that always wears me out

nikomatsakis (Jun 13 2019 at 17:08, on Zulip):

right...so...

nikomatsakis (Jun 13 2019 at 17:08, on Zulip):

it occurs to me I'm not 100% sure how much you understand about the type parameters etc

nikomatsakis (Jun 13 2019 at 17:08, on Zulip):

i.e., you're familiar with the general system of "substs" in the compiler?

davidtwco (Jun 13 2019 at 17:09, on Zulip):

I think so yeah.

nikomatsakis (Jun 13 2019 at 17:09, on Zulip):

ok. So the general idea (just to review real briefly) is that when you have a type parameter type like X, it includes an index into the parameters in scope

nikomatsakis (Jun 13 2019 at 17:10, on Zulip):

When we do a substitution, if you have e.g., struct Foo<T> { t: T } and you access the field t, it's type is a Param(0) (say) -- and then we have the substs array (maybe [u32])

nikomatsakis (Jun 13 2019 at 17:10, on Zulip):

and we index into that array with the 0 offset to convert T to u32 (presuming Foo<u32>)

nikomatsakis (Jun 13 2019 at 17:10, on Zulip):

(all familiar?)

nikomatsakis (Jun 13 2019 at 17:10, on Zulip):

so the reason I'm worried is that an out of range error here usually means we failed to substitute somewhere

nikomatsakis (Jun 13 2019 at 17:10, on Zulip):

and hence a TyParam with an index meant for one set of generics

nikomatsakis (Jun 13 2019 at 17:11, on Zulip):

leaks into a scope with a different set

nikomatsakis (Jun 13 2019 at 17:11, on Zulip):

(though it could have other causes)

nikomatsakis (Jun 13 2019 at 17:11, on Zulip):

leaks into a scope with a different set

but if such a leak happens...badness

nikomatsakis (Jun 13 2019 at 17:12, on Zulip):

anyway I guess the first step is to get a backtrace for the ICE

davidtwco (Jun 13 2019 at 17:12, on Zulip):

https://gist.github.com/davidtwco/4f0bf9ff3aad9df25c272909492e6982

nikomatsakis (Jun 13 2019 at 17:12, on Zulip):

although the minimized form that was given doesn't build for me

nikomatsakis (Jun 13 2019 at 17:13, on Zulip):

hmm this error is very confusing

nikomatsakis (Jun 13 2019 at 17:13, on Zulip):

oh I forgot the edition

davidtwco (Jun 13 2019 at 17:13, on Zulip):

Though, my build for this is maybe a week old at this point, so the actual output may have changed.

nikomatsakis (Jun 13 2019 at 17:13, on Zulip):

right so I'm skimming past tall the type folder stuff

nikomatsakis (Jun 13 2019 at 17:14, on Zulip):

and I guess the real "source" of the error is here

rustc_typeck::collect::find_existential_constraints::ConstraintLocator::check
davidtwco (Jun 13 2019 at 17:14, on Zulip):

I landed on typeck/collect.rs:1549 as being the place to start.

nikomatsakis (Jun 13 2019 at 17:14, on Zulip):

seems right

nikomatsakis (Jun 13 2019 at 17:14, on Zulip):

so what happens here --

nikomatsakis (Jun 13 2019 at 17:14, on Zulip):

this is the code for an existential type (opaque type)

nikomatsakis (Jun 13 2019 at 17:15, on Zulip):

the idea is that we have some hidden type whose value has been inferred

nikomatsakis (Jun 13 2019 at 17:15, on Zulip):

that is the concrete_type variable

nikomatsakis (Jun 13 2019 at 17:15, on Zulip):

and we are inferring its result

nikomatsakis (Jun 13 2019 at 17:15, on Zulip):

looking more closely at this, I am guessing this is a bug in the handling of existential type as an associated type definition in an impl

nikomatsakis (Jun 13 2019 at 17:15, on Zulip):

and probably not that specific to impl trait

nikomatsakis (Jun 13 2019 at 17:15, on Zulip):

but I guess let's wait a bit before we know if that's true

davidtwco (Jun 13 2019 at 17:15, on Zulip):

I believe the concrete_type was impl std::future::Future when I was looking at the logs (but rebuilding so can't check exactly).

davidtwco (Jun 13 2019 at 17:16, on Zulip):

And the substs just [S].

nikomatsakis (Jun 13 2019 at 17:16, on Zulip):

ok, that's interesting

nikomatsakis (Jun 13 2019 at 17:16, on Zulip):

this version of the example also ICEs in a very similar way

nikomatsakis (Jun 13 2019 at 17:16, on Zulip):
pub trait Bar
{
    type E: Copy;

    fn foo<T>() -> Self::E;
}

impl <S> Bar for S
{
    existential type E: Copy;

    fn foo<T>() -> Self::E
    {
        || ()
    }
}

fn main() {}
nikomatsakis (Jun 13 2019 at 17:16, on Zulip):

it does not use any async :)

nikomatsakis (Jun 13 2019 at 17:17, on Zulip):

I get:

error: internal compiler error: src/librustc/ty/subst.rs:570: type parameter `T/#1` (T/1) out of range when substituting (root type=Some([closure@/home/nmatsakis/tmp/issue-55872.rs:15:9: 15:14])) substs=[S]
nikomatsakis (Jun 13 2019 at 17:18, on Zulip):

but let's dig a bit more

nikomatsakis (Jun 13 2019 at 17:18, on Zulip):

let's use this version

nikomatsakis (Jun 13 2019 at 17:18, on Zulip):

less variables

nikomatsakis (Jun 13 2019 at 17:19, on Zulip):
 concrete_type: [closure@/home/nmatsakis/tmp/issue-55872.rs:15:9: 15:14], substs: [S]
nikomatsakis (Jun 13 2019 at 17:19, on Zulip):

(from debug logs)

nikomatsakis (Jun 13 2019 at 17:19, on Zulip):

rerunnign with -Zverbose

nikomatsakis (Jun 13 2019 at 17:19, on Zulip):

since closure types aren't that useful otherwise

nikomatsakis (Jun 13 2019 at 17:19, on Zulip):

gives

{ concrete_type:
    [closure@/home/nmatsakis/tmp/issue-55872.rs:15:9: 15:14
        closure_kind_ty=i8
        closure_sig_ty=extern "rust-call" fn(())
    ],
substs: [S] }
nikomatsakis (Jun 13 2019 at 17:20, on Zulip):

ok so

nikomatsakis (Jun 13 2019 at 17:20, on Zulip):

I think I see what's going on here

nikomatsakis (Jun 13 2019 at 17:21, on Zulip):

though it's not very evident from the debug output:)

nikomatsakis (Jun 13 2019 at 17:21, on Zulip):

first thing: closure types are implicitly parameterized by all of the generic types that are in scope

nikomatsakis (Jun 13 2019 at 17:21, on Zulip):

(same with async blocks)

nikomatsakis (Jun 13 2019 at 17:21, on Zulip):

this is because they may (e.g.) do things like T::foo()

nikomatsakis (Jun 13 2019 at 17:22, on Zulip):

though it's not very evident from the debug output:)

this btw sucks and I wish we had time to make it better :)

nikomatsakis (Jun 13 2019 at 17:22, on Zulip):

the full set of closure substitutions therefore will be something like this:

nikomatsakis (Jun 13 2019 at 17:22, on Zulip):
[
    S, // from the impl
    T,  // from the function
    ... // some other stuff specific to closures, e.g., the type of the upvars (none in this case)
]
nikomatsakis (Jun 13 2019 at 17:23, on Zulip):

now the problem here is that, if you look at the example, the set of generics in scope at the existential type is just S

nikomatsakis (Jun 13 2019 at 17:23, on Zulip):
impl <S> Bar for S
{
    existential type E: Copy;
nikomatsakis (Jun 13 2019 at 17:24, on Zulip):

this is my preferred minimization

nikomatsakis (Jun 13 2019 at 17:24, on Zulip):

let's switch to this

nikomatsakis (Jun 13 2019 at 17:24, on Zulip):
pub trait Bar
{
    type E: Copy;

    fn foo<T>() -> Self::E;
}

impl <S: Default> Bar for S
{
    existential type E: Copy;

    fn foo<T: Default>() -> Self::E
    {
        (S::default(), T::default())
    }
}

fn main() {}
nikomatsakis (Jun 13 2019 at 17:24, on Zulip):

here you can see that the return type from foo is (S, T)

nikomatsakis (Jun 13 2019 at 17:24, on Zulip):

but you see that there is no way that E could be equal to (S, T), as T is not in scope there

nikomatsakis (Jun 13 2019 at 17:25, on Zulip):

there is some logic that's supposed to detect this

nikomatsakis (Jun 13 2019 at 17:25, on Zulip):

at least we spend a lot of effort to do it for lifetimes

nikomatsakis (Jun 13 2019 at 17:26, on Zulip):

perhaps we are not doing it for types, or not doing it very well

nikomatsakis (Jun 13 2019 at 17:26, on Zulip):

let's look where this .concrete_existential_types field is populated

nikomatsakis (Jun 13 2019 at 17:27, on Zulip):

i.e., we have this:

          let ty = self
                .tcx
                .typeck_tables_of(def_id)
                .concrete_existential_types
                .get(&self.def_id);
nikomatsakis (Jun 13 2019 at 17:27, on Zulip):

(earlier in that function)

nikomatsakis (Jun 13 2019 at 17:27, on Zulip):

for me, it's collect.rs:1551

nikomatsakis (Jun 13 2019 at 17:28, on Zulip):

I believe that this is populated in the src/librustc_typeck/check/writeback.rs -- are you familiar with "writeback"?

davidtwco (Jun 13 2019 at 17:28, on Zulip):

I've been in that file but I have yet to work out why it's called writeback, line 603 in that seems to populate concrete_existential_types.

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

it's called writeback because

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

when we type check a function

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

we first create a "local" set of information for it

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

this local set includes inference variables and a bunch of intermediate stuff

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

once all inference is done, we create the final version of the information without any inference variables

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

then we write that to the global tables

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

I guess "writeback" is a bit strange, since it was never there before

nikomatsakis (Jun 13 2019 at 17:29, on Zulip):

I can't remember if we used to do it some other way

nikomatsakis (Jun 13 2019 at 17:30, on Zulip):

I guess "commit" might be a better name or something

nikomatsakis (Jun 13 2019 at 17:30, on Zulip):

anyway

nikomatsakis (Jun 13 2019 at 17:30, on Zulip):

right so this function:

nikomatsakis (Jun 13 2019 at 17:30, on Zulip):
           let definition_ty = if generics.parent.is_some() {
                // `impl Trait`
                self.fcx.infer_opaque_definition_from_instantiation(
                    def_id,
                    opaque_defn,
                    instantiated_ty,
                )
nikomatsakis (Jun 13 2019 at 17:30, on Zulip):

that infer_opaqe_definition_from_instantiation has the job

nikomatsakis (Jun 13 2019 at 17:30, on Zulip):

well, wait up,

nikomatsakis (Jun 13 2019 at 17:30, on Zulip):

in general what we want to do here

nikomatsakis (Jun 13 2019 at 17:31, on Zulip):

is to map from the "Local view" of the type

nikomatsakis (Jun 13 2019 at 17:31, on Zulip):

(the opaque type)

nikomatsakis (Jun 13 2019 at 17:31, on Zulip):

to the "definition" version

nikomatsakis (Jun 13 2019 at 17:31, on Zulip):

i.e., if you imagine

nikomatsakis (Jun 13 2019 at 17:31, on Zulip):
existential type Foo<T>: Sized;

fn foo<A>(a: A) -> Foo<A> { vec![a] }
nikomatsakis (Jun 13 2019 at 17:31, on Zulip):

then the "hidden type" is Vec<A>, from the point of view of foo

nikomatsakis (Jun 13 2019 at 17:32, on Zulip):

but we want to express it in terms of the bounds of the existential type, so we want Vec<T>

nikomatsakis (Jun 13 2019 at 17:32, on Zulip):

because this is the type that, when you substitute T for A (because we have Foo<A>), gives you Vec<A>

nikomatsakis (Jun 13 2019 at 17:32, on Zulip):

in general, there may not be a unique reverse mapping

nikomatsakis (Jun 13 2019 at 17:33, on Zulip):

e.g., if you had fn foo() -> Foo<u32> { 22_u32 }

nikomatsakis (Jun 13 2019 at 17:33, on Zulip):

then Foo<T> could be either T or u32

nikomatsakis (Jun 13 2019 at 17:33, on Zulip):

so we prohibit that :)

nikomatsakis (Jun 13 2019 at 17:33, on Zulip):

specifically, we require that the substitutions for Foo have to be fresh type parameters

nikomatsakis (Jun 13 2019 at 17:33, on Zulip):

that are not in scope for Foo itself

nikomatsakis (Jun 13 2019 at 17:34, on Zulip):

(this is called "pattern unification" instead of the more general "unification")

nikomatsakis (Jun 13 2019 at 17:34, on Zulip):

i.e., imposing this restriction

nikomatsakis (Jun 13 2019 at 17:34, on Zulip):

(it comes from lambda prolog, as it happens)

nikomatsakis (Jun 13 2019 at 17:34, on Zulip):

anyway, getting a bit afield here...

nikomatsakis (Jun 13 2019 at 17:34, on Zulip):

but the point is we have to do this reverse mapping

nikomatsakis (Jun 13 2019 at 17:35, on Zulip):

I'm not entirely sure which path we are going to go down in this file

nikomatsakis (Jun 13 2019 at 17:35, on Zulip):

i.e., we have

 if generics.parent.is_some() {
     // impl Trait
} else {
}
nikomatsakis (Jun 13 2019 at 17:35, on Zulip):

the comments suggest the first path is specific to -> impl Trait

nikomatsakis (Jun 13 2019 at 17:35, on Zulip):

but I think that's not true

nikomatsakis (Jun 13 2019 at 17:35, on Zulip):

I imagine that is the path we are going to go down

nikomatsakis (Jun 13 2019 at 17:36, on Zulip):

do you know what generics.parent is?

nikomatsakis (Jun 13 2019 at 17:36, on Zulip):

(ok, I think I understand the bug fully now...)

davidtwco (Jun 13 2019 at 17:36, on Zulip):

Not really, if I had to guess, in our example generics would contain T and generics.parent is where S lives.

nikomatsakis (Jun 13 2019 at 17:36, on Zulip):

correct

nikomatsakis (Jun 13 2019 at 17:36, on Zulip):

well

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

sort of

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

this is indeed the role of parent

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

if you have nested scopes which inherit the generic parameters from an outer scope

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

then you get a "chain" of generics

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

so e.g. the generics for the method are [T]

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

but they have a parent of [S]

nikomatsakis (Jun 13 2019 at 17:37, on Zulip):

we don't often have such chains -- methods in impls are one of the few cases

nikomatsakis (Jun 13 2019 at 17:38, on Zulip):

in this particular case, though, the generics in question refers to the generics on the existential type

nikomatsakis (Jun 13 2019 at 17:38, on Zulip):

so it's going to be [] here, but the parent will be the impl

nikomatsakis (Jun 13 2019 at 17:38, on Zulip):

(it is [] because we have existential type Foo, no generics)

nikomatsakis (Jun 13 2019 at 17:38, on Zulip):

(if we had existential type Foo<A>, it would be [A] (but that'd be GATs))

nikomatsakis (Jun 13 2019 at 17:38, on Zulip):

anyway the reason that it is checking the parent field

nikomatsakis (Jun 13 2019 at 17:39, on Zulip):

this is because we "desugar" impl Trait like so:

nikomatsakis (Jun 13 2019 at 17:39, on Zulip):
fn foo<A>() -> impl Trait { }
nikomatsakis (Jun 13 2019 at 17:39, on Zulip):

becomes

nikomatsakis (Jun 13 2019 at 17:39, on Zulip):
fn foo<A>() -> Foo {
    existential type Foo;
}
nikomatsakis (Jun 13 2019 at 17:39, on Zulip):

well, something like that

nikomatsakis (Jun 13 2019 at 17:39, on Zulip):

you couldn't actually write it, because scoping doesn't work that way

nikomatsakis (Jun 13 2019 at 17:40, on Zulip):

but the point is, we make the parent be the function, and it inherits the generic parameters from the parent

nikomatsakis (Jun 13 2019 at 17:40, on Zulip):

(there is a legendary hack here concerning lifetimes, but I'm going to ignore that for now)

centril (Jun 13 2019 at 17:40, on Zulip):

we make the parent be the function, and it inherits the generic parameters from the parent

(https://www.microsoft.com/en-us/research/publication/lexically-scoped-type-variables/)

nikomatsakis (Jun 13 2019 at 17:40, on Zulip):

this has an interesting implication, in the case of impl Trait

nikomatsakis (Jun 13 2019 at 17:41, on Zulip):

in particular, the existential type Foo that we introduce only ever has lifetime parameters on it. And, the set of type parameters in scope at its definition (the function) are all parameters the function shares with the existential type

nikomatsakis (Jun 13 2019 at 17:41, on Zulip):

in other words, we can just ignore types completely for the purpose of the "reverse mapping" check

nikomatsakis (Jun 13 2019 at 17:42, on Zulip):

put another way, the -> impl Trait sugar always ensures all type parametesr that might appear in the hidden type are "in scope" (and have the same indices)

nikomatsakis (Jun 13 2019 at 17:42, on Zulip):

so you might get a clue where we are going wrong here now...

nikomatsakis (Jun 13 2019 at 17:43, on Zulip):

when this code was generalized to support existential type Foo; declarations,

nikomatsakis (Jun 13 2019 at 17:43, on Zulip):

we were distinguishing the impl trait case from the more general case

nikomatsakis (Jun 13 2019 at 17:43, on Zulip):

(I'm not entirely sure why)

nikomatsakis (Jun 13 2019 at 17:43, on Zulip):

initially, we didn't support those in impls

nikomatsakis (Jun 13 2019 at 17:43, on Zulip):

so we just checked in writeback.rs for whether there is a parent

nikomatsakis (Jun 13 2019 at 17:43, on Zulip):

if so, it is a nested "impl trait" item

nikomatsakis (Jun 13 2019 at 17:44, on Zulip):

and it invokes the infer_opaque_definition_from_instantiation helper function to check that the lifetimes involved have a reverse mapping

nikomatsakis (Jun 13 2019 at 17:44, on Zulip):

but this helper function ignores types

davidtwco (Jun 13 2019 at 17:44, on Zulip):

Does the same desugaring you described for impl Trait, where it is "defined" in the function apply when an existential type is an associated type like in our example then?

nikomatsakis (Jun 13 2019 at 17:44, on Zulip):

it is defined here

nikomatsakis (Jun 13 2019 at 17:45, on Zulip):

Does the same desugaring you described for impl Trait, where it is "defined" in the function apply when an existential type is an associated type like in our example then?

in some sense yes

nikomatsakis (Jun 13 2019 at 17:45, on Zulip):

because they share a prefix

nikomatsakis (Jun 13 2019 at 17:45, on Zulip):

of type parameters in common

nikomatsakis (Jun 13 2019 at 17:45, on Zulip):

and those type parameters don't need to be remapped, they're just in scope for both

nikomatsakis (Jun 13 2019 at 17:45, on Zulip):

but the difference is that, here, the method is introducing a new type parameter T that is not shraed

nikomatsakis (Jun 13 2019 at 17:46, on Zulip):

if you look at the else path, you can see we are checking that case

nikomatsakis (Jun 13 2019 at 17:47, on Zulip):

in contrast, the impl trait case goes down employs this ReverseMapper visitor

nikomatsakis (Jun 13 2019 at 17:47, on Zulip):

which just folds types

nikomatsakis (Jun 13 2019 at 17:47, on Zulip):

so I think the fix is to merge those two paths

nikomatsakis (Jun 13 2019 at 17:47, on Zulip):

(i'm not sure why they are separate at all)

nikomatsakis (Jun 13 2019 at 17:47, on Zulip):

maybe no good reason

nikomatsakis (Jun 13 2019 at 17:47, on Zulip):

@oli might remember, they were doing some of this work

nikomatsakis (Jun 13 2019 at 17:48, on Zulip):

I think the check we want is basically:

nikomatsakis (Jun 13 2019 at 17:49, on Zulip):

I'm wondering if we should use last few minutes to look at the other problem though :)

davidtwco (Jun 13 2019 at 17:49, on Zulip):

That's probably enough background on #55872 for me to attempt fixing it.

davidtwco (Jun 13 2019 at 17:49, on Zulip):

Thanks, this was very helpful.

nikomatsakis (Jun 13 2019 at 17:50, on Zulip):

I was thinking -- this would be good material to try and get into the rustc-guide

nikomatsakis (Jun 13 2019 at 17:50, on Zulip):

e.g., talking about how opaque types are implemented

nikomatsakis (Jun 13 2019 at 17:50, on Zulip):

maybe I'll cc @Santiago Pastorino -- do you have some kind of "queue" for things that might be good to add to the rustc-guide? If so, there is some coverage of the high-level view of opaque types in this thread that we might try to transcribe.

oli (Jun 14 2019 at 08:17, on Zulip):

so... When I implemented existential types I believed it would not work to merge the paths, but if we add the ty::Param and ConstVal::Param code to the visitor we should be able to do it

oli (Jun 14 2019 at 08:17, on Zulip):

it will end up doing some T by T replacements for impl Trait, but that should be fine.

mark-i-m (Jun 14 2019 at 15:37, on Zulip):

@nikomatsakis

maybe I'll cc @Santiago Pastorino -- do you have some kind of "queue" for things that might be good to add to the rustc-guide? If so, there is some coverage of the high-level view of opaque types in this thread that we might try to transcribe.

Currently it is just github issues, though we have been looking at other things. I opened https://github.com/rust-lang/rustc-guide/issues/339

Santiago Pastorino (Jun 14 2019 at 18:13, on Zulip):

maybe I'll cc Santiago Pastorino -- do you have some kind of "queue" for things that might be good to add to the rustc-guide? If so, there is some coverage of the high-level view of opaque types in this thread that we might try to transcribe.

:+1:, cool that @mark-i-m did open an issue :)

davidtwco (Jun 24 2019 at 08:19, on Zulip):

Sorry for the delay here, had a busy week, submitted #62090 for this, @nikomatsakis.

Last update: Nov 18 2019 at 00:40UTC