Stream: wg-traits

Topic: design meeting 2019.10.28


nikomatsakis (Oct 28 2019 at 18:04, on Zulip):

Hi @WG-traits :wave:

Alexander Regueiro (Oct 28 2019 at 18:05, on Zulip):

Hi

nikomatsakis (Oct 28 2019 at 18:05, on Zulip):

so .. what to discuss today :)

nikomatsakis (Oct 28 2019 at 18:06, on Zulip):

Some thoughts:

nikomatsakis (Oct 28 2019 at 18:06, on Zulip):

we've been talking a lot about chalk, we could discuss a bit something in/around rustc?

nikomatsakis (Oct 28 2019 at 18:07, on Zulip):

I haven't quite gotten the stride here of preparing on Friday with some idea of what to dive into :)

nikomatsakis (Oct 28 2019 at 18:08, on Zulip):

my hope was that we can use this meeting (in general) to talk out tricky design questions

nikomatsakis (Oct 28 2019 at 18:08, on Zulip):

and not just kind of "lecture" on stuff that's semi already known -- but I guess that'll come in time

nikomatsakis (Oct 28 2019 at 18:09, on Zulip):

in any case, around rustc, the things that I have on my mind

nikomatsakis (Oct 28 2019 at 18:10, on Zulip):
Alexander Regueiro (Oct 28 2019 at 18:11, on Zulip):

it's okay, I can give updates.

nikomatsakis (Oct 28 2019 at 18:11, on Zulip):

ok, why don't we discuss upcast a bit?

Alexander Regueiro (Oct 28 2019 at 18:11, on Zulip):

mind doing it sooner rather than later, as I have to leave soon? sorry. if not I can just leave my notes here though...

nikomatsakis (Oct 28 2019 at 18:11, on Zulip):

now is good :)

nikomatsakis (Oct 28 2019 at 18:13, on Zulip):

As context, @Alexander Regueiro has been working on a PR to enable us to "upcast" from &dyn Foo to &dyn Bar is Foo: Bar

Alexander Regueiro (Oct 28 2019 at 18:14, on Zulip):

cheers

Alexander Regueiro (Oct 28 2019 at 18:14, on Zulip):

yep

nikomatsakis (Oct 28 2019 at 18:14, on Zulip):

The general strategy is that we make the vtable for a trait Foo also embed the vtables for all of its supertraits

Alexander Regueiro (Oct 28 2019 at 18:14, on Zulip):

I was just rebasing all my work today BTW

Alexander Regueiro (Oct 28 2019 at 18:14, on Zulip):

yep, so right now the vtable is single (non-auto) trait, and looks like:
D S A M_1 M_2 ...

nikomatsakis (Oct 28 2019 at 18:14, on Zulip):

We encountered some challenges in/around the codegen and decided we might as well try to land the "frontend" changes first

Alexander Regueiro (Oct 28 2019 at 18:15, on Zulip):

where D S A are drop, size, align info

Alexander Regueiro (Oct 28 2019 at 18:15, on Zulip):

and M_i are the method pointers

nikomatsakis (Oct 28 2019 at 18:15, on Zulip):

yep, so right now the vtable is single (non-auto) trait, and looks like:
D S A M_1 M_2 ...

i.e., before your PR

Alexander Regueiro (Oct 28 2019 at 18:15, on Zulip):

yep

Alexander Regueiro (Oct 28 2019 at 18:16, on Zulip):

now (post-PR) it's D S A M_1 M_2 ... D S A N_1 N_2 ... D S A O_1 O_2 ...
where N_i and O_i are pointers to the methods for supertraits

Alexander Regueiro (Oct 28 2019 at 18:16, on Zulip):

so the idea is we can just offset into the base vtable when upcasting

Alexander Regueiro (Oct 28 2019 at 18:16, on Zulip):

but yeah, we had troubles with codegen like Niko said

Alexander Regueiro (Oct 28 2019 at 18:16, on Zulip):

all the other parts (mainly trait & MIR-related) are done.

nikomatsakis (Oct 28 2019 at 18:17, on Zulip):

so --

Alexander Regueiro (Oct 28 2019 at 18:17, on Zulip):

@nikomatsakis eddyb hasn't replied to our msgs here still, but he did actually made some changes to the relevant codegen sections of code, which I want to test to see if they helped things... who knows. he also left a new FIXME note.

nikomatsakis (Oct 28 2019 at 18:17, on Zulip):

(he pushed to your branch?)

Alexander Regueiro (Oct 28 2019 at 18:17, on Zulip):

if not, we'll probably want to merge it minus the codegen stuff, obviously under a feature gate, and probably with a warning

Alexander Regueiro (Oct 28 2019 at 18:17, on Zulip):

no, just a PR that got merged. I noticed it during my rebase today though

nikomatsakis (Oct 28 2019 at 18:18, on Zulip):

OK.

Alexander Regueiro (Oct 28 2019 at 18:19, on Zulip):

testing right now in fact :-)

nikomatsakis (Oct 28 2019 at 18:20, on Zulip):

We could talk a bit about what changes you wound up doing to enable this --

Alexander Regueiro (Oct 28 2019 at 18:21, on Zulip):

sure

nikomatsakis (Oct 28 2019 at 18:21, on Zulip):

the key thing being that when we coerce a value to a dyn type (e.g., &dyn Foo), we generate a CoerceUnsized obligation that must be proven

nikomatsakis (Oct 28 2019 at 18:21, on Zulip):

(this was already true)

Alexander Regueiro (Oct 28 2019 at 18:22, on Zulip):

yes

nikomatsakis (Oct 28 2019 at 18:23, on Zulip):

so sooner or later we wind up in confirm_builtin_unsizing_candidate

nikomatsakis (Oct 28 2019 at 18:23, on Zulip):

and in the cast of upcasting we go in this arm in particular

nikomatsakis (Oct 28 2019 at 18:24, on Zulip):

so we've basically generalized that to handle not just the case of lifetime bounds but also changing the principle traits

nikomatsakis (Oct 28 2019 at 18:24, on Zulip):

I guess, apart from that, the only other thing that really has to be changed is codegen?

nikomatsakis (Oct 28 2019 at 18:25, on Zulip):

(and there has to be some logic for computing the offsets into the vtable)

Alexander Regueiro (Oct 28 2019 at 18:25, on Zulip):

yep I think so

Alexander Regueiro (Oct 28 2019 at 18:25, on Zulip):

which I've already done

Alexander Regueiro (Oct 28 2019 at 18:25, on Zulip):

and I think is correct.. it's not too complex

nikomatsakis (Oct 28 2019 at 18:26, on Zulip):

ok, seems good, let me know when the PR is rebased and I will re-review I guess :)

nikomatsakis (Oct 28 2019 at 18:26, on Zulip):

Not that surprisingly, doesn't seem like there's a lot of unknowns to dig into here, maybe turn to another topic? not sure if anybody else has questions.

nikomatsakis (Oct 28 2019 at 18:28, on Zulip):

I'm trying to find my doc on lazy const normalization

nikomatsakis (Oct 28 2019 at 18:29, on Zulip):

I guess this was it: https://hackmd.io/S8cE-e-ORtCqjJzyOU5cLQ

nikomatsakis (Oct 28 2019 at 18:29, on Zulip):

maybe I'll talk a bit about that

Laurențiu Nicola (Oct 28 2019 at 18:29, on Zulip):

re trait upcasts, will diamond inheritance be handled (just wondering, since it wasn't mentioned, just ignore me otherwise)?

nikomatsakis (Oct 28 2019 at 18:30, on Zulip):

good question, I think it works, but we should make sure to test it -- I presume this will mean that the vtable includes two copies of "shared" ancestor methods though

Alexander Regueiro (Oct 28 2019 at 18:30, on Zulip):

yeah sounds fair

Alexander Regueiro (Oct 28 2019 at 18:30, on Zulip):

thanks for addressing that at least

Alexander Regueiro (Oct 28 2019 at 18:30, on Zulip):

oh yes...

Alexander Regueiro (Oct 28 2019 at 18:30, on Zulip):

fair point that

Laurențiu Nicola (Oct 28 2019 at 18:31, on Zulip):

do we want to have two copies?

Alexander Regueiro (Oct 28 2019 at 18:31, on Zulip):

I believe it works too, as a consequence of how the supertraits query works, but we'll need a test!

nikomatsakis (Oct 28 2019 at 18:31, on Zulip):

do we want to have two copies?

seems ok, it's just a table of pointers

Laurențiu Nicola (Oct 28 2019 at 18:31, on Zulip):

I guess so, it's not as bad as in C++ :)

nikomatsakis (Oct 28 2019 at 18:31, on Zulip):

there are alternative vtable layouts we could explore

nikomatsakis (Oct 28 2019 at 18:32, on Zulip):

yeah, note that the real conundrum from diamond inheritance is typically what happens to the state

nikomatsakis (Oct 28 2019 at 18:32, on Zulip):

and also separate compilation of method bodies

nikomatsakis (Oct 28 2019 at 18:32, on Zulip):

i.e., you want to be able to compile access to a field like this->f, but that requires knowing the offset of f -- the same is true for method calls (in the vtable), but those are read-only, so we can duplicate

nikomatsakis (Oct 28 2019 at 18:34, on Zulip):

the bigger question for me (which is orthogonal from upcasting, really) will be how we want to support things like &dyn (Foo + Bar)

nikomatsakis (Oct 28 2019 at 18:35, on Zulip):

I'm trying to find my doc on lazy const normalization

ok, circling back to this

nikomatsakis (Oct 28 2019 at 18:35, on Zulip):

it's kind of interesting, because in a way the work we've been doing on chalk is actually moving away from this lazy norm strategy

Alexander Regueiro (Oct 28 2019 at 18:36, on Zulip):

oh, I was under the impression you've been actively working on lazy norm, Niko?

nikomatsakis (Oct 28 2019 at 18:36, on Zulip):

the idea in general here is that you a constant can be an expression that needs to be evaluated

nikomatsakis (Oct 28 2019 at 18:36, on Zulip):

e.g., maybe you have [u32; {1 + 2}] and [u32; 3], and you want to know if those are the same types

nikomatsakis (Oct 28 2019 at 18:38, on Zulip):

(sorry, got distracted look for another write-up, but I can't find it)

nikomatsakis (Oct 28 2019 at 18:38, on Zulip):

this is kind of a pain around where clauses

nikomatsakis (Oct 28 2019 at 18:38, on Zulip):

well anyway let's leave aside the root causes, the idea is that we want to do something where we wait to evaluate {1+2} until we are forced to do so (beacuse e.g. we are equating it with 3)

nikomatsakis (Oct 28 2019 at 18:39, on Zulip):

this is quite related to the problem of normalizing associated types like <Vec<u32> as IntoIterator>::Item (which normalizes to u32)

nikomatsakis (Oct 28 2019 at 18:39, on Zulip):

both of them are kind of "evaluating"

nikomatsakis (Oct 28 2019 at 18:39, on Zulip):

but even though they are conceptually identical, we don't necessarily have to handle them in 100% the same way, though I think we would eventually like to

nikomatsakis (Oct 28 2019 at 18:39, on Zulip):

oh, I was under the impression you've been actively working on lazy norm, Niko?

I have been, under various guises

nikomatsakis (Oct 28 2019 at 18:39, on Zulip):

the thing is that I've been modifying chalk so that unification logic doesn't have to handle normalization

nikomatsakis (Oct 28 2019 at 18:40, on Zulip):

and instead we handle it earlier on, by translating associated types into something different

nikomatsakis (Oct 28 2019 at 18:40, on Zulip):

but in rustc we have no such translation step to fall back on

nikomatsakis (Oct 28 2019 at 18:40, on Zulip):

so the idea would be roughly that when we are equating types, if we come across two constants, we'll generate an obligation as a result that "equates" them

nikomatsakis (Oct 28 2019 at 18:41, on Zulip):

(we have the machinery to do this, in general, which we plumbed at various points for various reasons, mostly lazy norm of assoc types)

nikomatsakis (Oct 28 2019 at 18:41, on Zulip):

so if you were relating

[u32; {1+2}] = [u32; 3]
nikomatsakis (Oct 28 2019 at 18:41, on Zulip):

we would wind up with a result that is like

nikomatsakis (Oct 28 2019 at 18:42, on Zulip):

here {1+2} is presumably, in the compiler, an "unevaluated" constant,

nikomatsakis (Oct 28 2019 at 18:42, on Zulip):

which is stored as the pair of a DefId (to identify the MIR for 1+2 in this case) plus some substitutions

nikomatsakis (Oct 28 2019 at 18:42, on Zulip):

anyway, the ConstEquate obligation will get added to the fulfillment context as normal and evaluated when we are able to do so

nikomatsakis (Oct 28 2019 at 18:42, on Zulip):

there are a few complications though

nikomatsakis (Oct 28 2019 at 18:43, on Zulip):

one has to do with higher-ranked regions, and the "leak check" code we currently use to handle them

nikomatsakis (Oct 28 2019 at 18:44, on Zulip):

the other has to do with type inference variables

nikomatsakis (Oct 28 2019 at 18:44, on Zulip):

(make sense so far?)

tmandry (Oct 28 2019 at 18:45, on Zulip):

I don't know if it would be helpful for this discussion, but I'm trying to remember why lazy norm was so important for const eval in the first place :)

nikomatsakis (Oct 28 2019 at 18:45, on Zulip):

heh, that was the thing I skipped over

nikomatsakis (Oct 28 2019 at 18:45, on Zulip):

let me see if I can reconstruct the example

nikomatsakis (Oct 28 2019 at 18:45, on Zulip):

I'm annoyed I didn't put notes on it in the doc

nikomatsakis (Oct 28 2019 at 18:45, on Zulip):

because it took me some time to get it back in cache

tmandry (Oct 28 2019 at 18:46, on Zulip):

it's ok if you need to skip for now

nikomatsakis (Oct 28 2019 at 18:47, on Zulip):

ok I think I found it

nikomatsakis (Oct 28 2019 at 18:47, on Zulip):

from some notes of mine

it's basically this: to evaluate {foo}, you must type-check it; to type-check it, you need its environment; so if {foo} appears in a where-clause, and the other where-clauses are ins cope, etc etc?

nikomatsakis (Oct 28 2019 at 18:47, on Zulip):

let me expand on that ;)

nikomatsakis (Oct 28 2019 at 18:47, on Zulip):

so the question is, how do we evaluate {1+2}?

nikomatsakis (Oct 28 2019 at 18:47, on Zulip):

To do that, we need the MIR. To create the MIR, we need to type-check it.

nikomatsakis (Oct 28 2019 at 18:47, on Zulip):

Now imagine that we have

nikomatsakis (Oct 28 2019 at 18:48, on Zulip):
fn foo<T>()
where
    T: SomeTrait<{1 + 2}>
nikomatsakis (Oct 28 2019 at 18:48, on Zulip):

this is assuming trait SomeTrait<const C>, i.e., a const-generic future

nikomatsakis (Oct 28 2019 at 18:48, on Zulip):

ok so we have to type-check {1+2} -- but that is a mini-function body, and part of type-checking requires figuring out which where clauses are in scope

nikomatsakis (Oct 28 2019 at 18:48, on Zulip):

this is not relevant for an expression like {1+2}

nikomatsakis (Oct 28 2019 at 18:48, on Zulip):

but you could have

Alexander Regueiro (Oct 28 2019 at 18:49, on Zulip):

@nikomatsakis ah, interesting. this will solve the apparent need for lazy normalisation in type alias bounds though?

nikomatsakis (Oct 28 2019 at 18:49, on Zulip):
fn foo<T>
where
    T: Sized,
    G: SomeTrait<T::SIZE>
nikomatsakis (Oct 28 2019 at 18:49, on Zulip):

(where SIZE is an associated constant)

nikomatsakis (Oct 28 2019 at 18:49, on Zulip):

etc etc

nikomatsakis (Oct 28 2019 at 18:50, on Zulip):

so now the problem is:

nikomatsakis (Oct 28 2019 at 18:50, on Zulip):

we actually have a similar problem with associated types

nikomatsakis (Oct 28 2019 at 18:50, on Zulip):

but we kind of "cheat" by normalizing with the unevaluated versions in scope

nikomatsakis (Oct 28 2019 at 18:51, on Zulip):

that is,

fn foo<T: Iterator>
where
    X: Blah<T::Item>

we would normalize T::Item with X: Blah<T::Item> in scope

nikomatsakis (Oct 28 2019 at 18:51, on Zulip):

er, let me make that a better example

nikomatsakis (Oct 28 2019 at 18:51, on Zulip):
fn foo<T: Iterator<Item = u32>>
where
    X: Blah<T::Item>

here, when we normalize T::Item, we would have X: Blah<T::Item> in scope, not X: Blah<u32>

nikomatsakis (Oct 28 2019 at 18:52, on Zulip):

we could conceivably do something similar around constants

nikomatsakis (Oct 28 2019 at 18:52, on Zulip):

ah, interesting. this will solve the apparent need for lazy normalisation in type alias bounds though?

not 100% sure what you're referring to here, @Alexander Regueiro

Alexander Regueiro (Oct 28 2019 at 18:53, on Zulip):

the issue with type alias bounds not working required lazy norm, people deemed

nikomatsakis (Oct 28 2019 at 18:53, on Zulip):

do you mean stuff like type Foo<X: Iterator> = ...?

Alexander Regueiro (Oct 28 2019 at 18:53, on Zulip):

yes that

nikomatsakis (Oct 28 2019 at 18:54, on Zulip):

ok ok -- well, yes, to handle that the way I would like to probably would want something like lazy norm too -- at the moment I'm just focused on constants, though. But there's definitely a relationship -- the user types Foo<T>, and it gets normalized to the ...

nikomatsakis (Oct 28 2019 at 18:55, on Zulip):

(but one of the things I was planning is to prototype these pathways for constants only)

nikomatsakis (Oct 28 2019 at 18:55, on Zulip):

I don't know if it would be helpful for this discussion, but I'm trying to remember why lazy norm was so important for const eval in the first place :)

did that answer your question, @tmandry ?

nikomatsakis (Oct 28 2019 at 18:55, on Zulip):

we could conceivably do something similar around constants

what we would do here is presumably to type-check constants with an unnormalized set of where-clauses. This would probably get us .. somewhat far.

nikomatsakis (Oct 28 2019 at 18:56, on Zulip):

but it's not really the right answer longer term

nikomatsakis (Oct 28 2019 at 18:56, on Zulip):

(or at least type-check constants that appear in where-clauses)

nikomatsakis (Oct 28 2019 at 18:56, on Zulip):

but we kind of "cheat" by normalizing with the unevaluated versions in scope

I'm trying to find the code where this happens

nikomatsakis (Oct 28 2019 at 18:57, on Zulip):

it's normalize_param_env_or_error

nikomatsakis (Oct 28 2019 at 18:57, on Zulip):

you can see this comment here

nikomatsakis (Oct 28 2019 at 18:58, on Zulip):

anyway, I guess that at least laid the groundwork on normalization :)

nikomatsakis (Oct 28 2019 at 18:58, on Zulip):

let's plan a bit for next time :)

nikomatsakis (Oct 28 2019 at 18:59, on Zulip):

I'm thinking we'll continue, in a sense, from where this left off, and talk about the universes + regions PR and -- maybe if we have time -- I'll talk a bit about my thoughts on how to handle regions more generally

nikomatsakis (Oct 28 2019 at 18:59, on Zulip):

(seem good?)

Last update: Nov 12 2019 at 16:10UTC