Stream: t-compiler/help

Topic: variance and assoc types #71550


nikomatsakis (Apr 30 2020 at 16:46, on Zulip):

So @Santiago Pastorino ...

Santiago Pastorino (Apr 30 2020 at 16:47, on Zulip):

:wave:

nikomatsakis (Apr 30 2020 at 16:47, on Zulip):

I guess the first thing is to track out exactly why this is happening

nikomatsakis (Apr 30 2020 at 16:47, on Zulip):

The PR that was cited is somewhat surprising

nikomatsakis (Apr 30 2020 at 16:47, on Zulip):

but before we do even that

nikomatsakis (Apr 30 2020 at 16:47, on Zulip):

let me check-- do you understand the bug?

Santiago Pastorino (Apr 30 2020 at 16:47, on Zulip):

nikomatsakis said:

The PR that was cited is somewhat surprising

why do you say it's surprising?

nikomatsakis (Apr 30 2020 at 16:48, on Zulip):

because the intent of the PR was to fix a bug like this

nikomatsakis (Apr 30 2020 at 16:48, on Zulip):

do you know what we mean by "invariant"?

Santiago Pastorino (Apr 30 2020 at 16:49, on Zulip):

https://doc.rust-lang.org/nomicon/subtyping.html#variance

Santiago Pastorino (Apr 30 2020 at 16:49, on Zulip):

:)

Santiago Pastorino (Apr 30 2020 at 16:49, on Zulip):

nikomatsakis said:

because the intent of the PR was to fix a bug like this

ahh I see

Santiago Pastorino (Apr 30 2020 at 16:50, on Zulip):

trait objects shouldn't be covariant to its associated types I guess?

nikomatsakis (Apr 30 2020 at 16:50, on Zulip):

yeah

nikomatsakis (Apr 30 2020 at 16:50, on Zulip):

so in general associated types have to be "invariant" with respect to the input types on the trait

nikomatsakis (Apr 30 2020 at 16:50, on Zulip):

in other words

Santiago Pastorino (Apr 30 2020 at 16:50, on Zulip):

I'd need to read a bit more and think about it properly

nikomatsakis (Apr 30 2020 at 16:50, on Zulip):

normally we say that &'static u32 <: &'a u32 for any 'a

nikomatsakis (Apr 30 2020 at 16:51, on Zulip):

this is because &'b T <: &'a T if 'b: 'a

nikomatsakis (Apr 30 2020 at 16:51, on Zulip):

and 'static: 'a for all 'a

nikomatsakis (Apr 30 2020 at 16:51, on Zulip):

this in turn means that Vec<&'static u32> <: Vec<&'a u32>,

nikomatsakis (Apr 30 2020 at 16:51, on Zulip):

because Vec<T> is covariant with respect to T

Santiago Pastorino (Apr 30 2020 at 16:51, on Zulip):

:+1:

nikomatsakis (Apr 30 2020 at 16:52, on Zulip):

but if you have <Vec<&'static u32> as Iterator>::Item and <Vec<&'a u32> as Iterator>::Item...

nikomatsakis (Apr 30 2020 at 16:52, on Zulip):

there is no subtyping relationship

nikomatsakis (Apr 30 2020 at 16:52, on Zulip):

(even though, in that particular example, it would work out ok)

nikomatsakis (Apr 30 2020 at 16:52, on Zulip):

the reason is basically because we have no idea what Item will expand to be

nikomatsakis (Apr 30 2020 at 16:52, on Zulip):

and just because the inputs to the trait are subtypes, doesn't mean the "output" will be

nikomatsakis (Apr 30 2020 at 16:53, on Zulip):

so...similarly...

Santiago Pastorino (Apr 30 2020 at 16:53, on Zulip):

as I've said, I didn't spend time on this issue, but just by looking at it wonder if this can be reduced more?

nikomatsakis (Apr 30 2020 at 16:53, on Zulip):

a good question

nikomatsakis (Apr 30 2020 at 16:53, on Zulip):

surely yes

nikomatsakis (Apr 30 2020 at 16:53, on Zulip):

one sec

Santiago Pastorino (Apr 30 2020 at 16:54, on Zulip):

I can investigate that but yeah if there's something obvious to you would be good to know

nikomatsakis (Apr 30 2020 at 16:55, on Zulip):
trait Foo {
    type Bar;
}

fn gimme<'a>(
  x: &'a u32,
  y: &dyn Foo<Bar = &'a u32>
) { }

fn gimme2<'a>(
  x: &'a u32,
  y: &dyn Foo<Bar = &'static u32>,
) {
    gimme(x, y);
}

fn main() { }
nikomatsakis (Apr 30 2020 at 16:55, on Zulip):

so that program compiles

nikomatsakis (Apr 30 2020 at 16:55, on Zulip):

playground

nikomatsakis (Apr 30 2020 at 16:55, on Zulip):

but I don't think it should

Santiago Pastorino (Apr 30 2020 at 16:55, on Zulip):

I was going to say ... PhantomData doesn't seem to be needed

nikomatsakis (Apr 30 2020 at 16:56, on Zulip):

actually we can make it smaller still

Santiago Pastorino (Apr 30 2020 at 16:57, on Zulip):

we can probably make it print a dangling reference as in the issue, right?

Santiago Pastorino (Apr 30 2020 at 16:57, on Zulip):

so we have a repro that make things explode badly :)

nikomatsakis (Apr 30 2020 at 16:57, on Zulip):
trait Foo {
    type Bar;
}

fn make() -> Box<dyn Foo<Bar = &'static u32>> {
    panic!()
}

fn take<'a>(
  _: &'a u32,
) {
    let _: Box<dyn Foo<Bar = &'a u32>> = make();
}

fn main() { }
nikomatsakis (Apr 30 2020 at 16:57, on Zulip):

nah

nikomatsakis (Apr 30 2020 at 16:58, on Zulip):

I mean a weaponized variant that explodes badly

nikomatsakis (Apr 30 2020 at 16:58, on Zulip):

is sort of by definition not minimal :)

nikomatsakis (Apr 30 2020 at 16:58, on Zulip):

for debugging we want the minimal thing

nikomatsakis (Apr 30 2020 at 16:58, on Zulip):

the key bug is that this subtyping relationship doesn't hold

Santiago Pastorino (Apr 30 2020 at 16:58, on Zulip):

ahh yeah, for debugging minimal but as a test to place it with the PR maybe it's good?

nikomatsakis (Apr 30 2020 at 16:59, on Zulip):

maybe -- we can worry about it then

Santiago Pastorino (Apr 30 2020 at 16:59, on Zulip):

in any case I'll try the repro of the issue at least locally :)

nikomatsakis (Apr 30 2020 at 16:59, on Zulip):

I'd sort of prefer to include the minimal one, and then maybe also a weaponized one

Santiago Pastorino (Apr 30 2020 at 16:59, on Zulip):

once fixed

nikomatsakis (Apr 30 2020 at 16:59, on Zulip):

anyway the thing is to figure out why there is no invariance here

Santiago Pastorino (Apr 30 2020 at 16:59, on Zulip):

ok I guess I can investigate for a bit and ask questions maybe?

nikomatsakis (Apr 30 2020 at 16:59, on Zulip):

so let me give you a few tips

Santiago Pastorino (Apr 30 2020 at 16:59, on Zulip):

do you have ... tips ... exactly :)

nikomatsakis (Apr 30 2020 at 17:00, on Zulip):

there are actually.. two bits of relevant code?

nikomatsakis (Apr 30 2020 at 17:00, on Zulip):

the first one would be https://github.com/rust-lang/rust/blob/master/src/librustc_middle/ty/relate.rs -- the "type relating" code

nikomatsakis (Apr 30 2020 at 17:00, on Zulip):

this is like a visitor that walks down two pairs of types

nikomatsakis (Apr 30 2020 at 17:00, on Zulip):

note that it has this callback relate_with_variance

nikomatsakis (Apr 30 2020 at 17:01, on Zulip):

so if we loop down here.. we see this code, which is where it handles two dyn types

nikomatsakis (Apr 30 2020 at 17:02, on Zulip):

you can see that it is specifying Contravariant here as it relates the "predicates" of the two dyn types (line)

nikomatsakis (Apr 30 2020 at 17:02, on Zulip):

I...have no real idea why it would choose that, actually

nikomatsakis (Apr 30 2020 at 17:02, on Zulip):

/me thinks

nikomatsakis (Apr 30 2020 at 17:02, on Zulip):

or sorry

nikomatsakis (Apr 30 2020 at 17:02, on Zulip):

that is just the region bound

nikomatsakis (Apr 30 2020 at 17:02, on Zulip):

i.e., a dyn type is really short for dyn Bound + 'a

nikomatsakis (Apr 30 2020 at 17:03, on Zulip):

and it is correct that the 'a region bound is contravariant

Santiago Pastorino (Apr 30 2020 at 17:03, on Zulip):

ahh right :+1:

nikomatsakis (Apr 30 2020 at 17:03, on Zulip):

more interesting is the recursive call relation.relate

nikomatsakis (Apr 30 2020 at 17:03, on Zulip):

which will I think bring you to the impl for ExistentialPredicate

nikomatsakis (Apr 30 2020 at 17:04, on Zulip):

which will bring you ultimately *here*

nikomatsakis (Apr 30 2020 at 17:04, on Zulip):

(at least for the case of Foo=Bar bounds)

nikomatsakis (Apr 30 2020 at 17:04, on Zulip):

I'm sort of debating where I think the bug is here

nikomatsakis (Apr 30 2020 at 17:05, on Zulip):

but somewhere along this chain, we should have a relate_with_invariance sort of call

nikomatsakis (Apr 30 2020 at 17:05, on Zulip):

nikomatsakis said:

more interesting is the recursive call relation.relate

quite possibly on this line, but maybe also other lines :)

nikomatsakis (Apr 30 2020 at 17:05, on Zulip):

to explain what I mean...

Santiago Pastorino (Apr 30 2020 at 17:05, on Zulip):

nikomatsakis said:

but somewhere along this chain, we should have a relate_with_invariance sort of call

you meant, instead of just a relate call?

nikomatsakis (Apr 30 2020 at 17:06, on Zulip):

yeah

nikomatsakis (Apr 30 2020 at 17:06, on Zulip):

the actual fn is relate_with_variance and supplying an argument of invariance

Santiago Pastorino (Apr 30 2020 at 17:06, on Zulip):

need to investigate the code but yeah :+1: maybe that's the problem or something like that ... unsure

nikomatsakis (Apr 30 2020 at 17:06, on Zulip):

so imagine a case like dyn Foo<A>

nikomatsakis (Apr 30 2020 at 17:06, on Zulip):

(no associated types)

nikomatsakis (Apr 30 2020 at 17:06, on Zulip):

the Foo<A> here is an ExistentialTraitRef

nikomatsakis (Apr 30 2020 at 17:06, on Zulip):

that is, this is how it is represented

nikomatsakis (Apr 30 2020 at 17:07, on Zulip):

the impl for that is here

nikomatsakis (Apr 30 2020 at 17:07, on Zulip):

and you can see that it invokes relate_substs with the second argument set to None

nikomatsakis (Apr 30 2020 at 17:07, on Zulip):

this will cause the substs to be related with invariance

nikomatsakis (Apr 30 2020 at 17:07, on Zulip):

the point being---

nikomatsakis (Apr 30 2020 at 17:08, on Zulip):

whenever an "existential trait reference" like Foo<A> is related to another like Foo<B>, we require that A = B

nikomatsakis (Apr 30 2020 at 17:08, on Zulip):

in other words, we want to inject invariance, but the question is where does it come from, in some sense

Santiago Pastorino (Apr 30 2020 at 17:08, on Zulip):

sorry, where does what comes from?

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

i.e., if we injected it when recursing in the dyn type, that would suggest that it's the keyword dyn that makes it invariant, but I think that's wrong. It's really most appropriate to inject it in the ExistentialProjection impl imo

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

Santiago Pastorino said:

sorry, where does what comes from?

the invariance

Santiago Pastorino (Apr 30 2020 at 17:09, on Zulip):

yeah :+1:

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

i.e., is there some context where you have an ExistentialProjection

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

where you would want to relate them with covariance

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

or whatever

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

as it happens, the "existential" types only appear in dyn right now

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

so it's sort of a moot point

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

but regardless I think the answer is no :)

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

trait matching and associated types are inherently invariant in rust right now

Santiago Pastorino (Apr 30 2020 at 17:09, on Zulip):

:+1:

nikomatsakis (Apr 30 2020 at 17:09, on Zulip):

so if we had some other kind of type that used the same concept, it should still be invariant

nikomatsakis (Apr 30 2020 at 17:10, on Zulip):

tl;dr I think these two calls should use "invariant" (here)

nikomatsakis (Apr 30 2020 at 17:10, on Zulip):

actually I think just doing that is probably the fix

Santiago Pastorino (Apr 30 2020 at 17:10, on Zulip):

so I can investigate where the invariance comes from and let you know before diving into a solution I guess

nikomatsakis (Apr 30 2020 at 17:10, on Zulip):

I said there were two bits of code but I think they both use this same core, "type-relating" visitor

Santiago Pastorino (Apr 30 2020 at 17:10, on Zulip):

nikomatsakis said:

actually I think just doing that is probably the fix

ahh well, :)

nikomatsakis (Apr 30 2020 at 17:11, on Zulip):

feel free to investigate, but I think that's the fix, the interesting question will be whether we start to encounter problems as a result of fixing the bug

Santiago Pastorino (Apr 30 2020 at 17:12, on Zulip):

hehe, yeah, you meant, more issues as part of fixing this problem?

Santiago Pastorino (Apr 30 2020 at 17:13, on Zulip):

nikomatsakis said:

feel free to investigate, but I think that's the fix, the interesting question will be whether we start to encounter problems as a result of fixing the bug

going to try to spend some time on this before throwing a fix because it will serve the purposes of understanding a bit the code there :)

nikomatsakis (Apr 30 2020 at 17:14, on Zulip):

Santiago Pastorino said:

hehe, yeah, you meant, more issues as part of fixing this problem?

I mean like

nikomatsakis (Apr 30 2020 at 17:15, on Zulip):

there's probably code relying on this

nikomatsakis (Apr 30 2020 at 17:15, on Zulip):

and we're going to break that code

nikomatsakis (Apr 30 2020 at 17:15, on Zulip):

and what's worse, the code is probably reasonable -- i.e., a more sophisticated type system that incorporated some notion of variance into trait matching could accept it

nikomatsakis (Apr 30 2020 at 17:15, on Zulip):

this is why I said this is P-criticial despite being old

nikomatsakis (Apr 30 2020 at 17:15, on Zulip):

because the sooner we fix, the less of code like that we have to deal with

Santiago Pastorino (Apr 30 2020 at 17:17, on Zulip):

ok, going to investigate a bit

Santiago Pastorino (Apr 30 2020 at 17:17, on Zulip):

but after brewing a good :coffee:, first things first :slight_smile:

Last update: Sep 28 2020 at 16:30UTC