Rust Programming Language Traits Working Group, 1 Jul 2019

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Chalk + Specialization

Description

Discussed the next steps around chalk + specialization.

A

B

Alright, then, making a recording for future reference so.

B

So when I was hoping we could do kind of forget, of course, so whoa no, you could. You um must be a new feature so.

B

I was hoping we could talk a little bit about the talks, very structure which meaning to think about anyway. I think that's pretty relevant so like we were gonna do or the overall plan around specialization or we go there make sure we're in agreement on this. The overall plan that we were working on was to.

B

Given kind of given the role that one involved a specializes, another input B, we can adjust the rules around projection so that B wins and in particular we have to adjust. We basically have to adjust the rules port in both a because will be, or rather the point is any default- that's a potentially specialized type. So those that's where we need to adjust the rules we probably may or may not real-life.

B

We might want to change the rules for all types to account for erroneous programs that people didn't use default but still has specialized, is going on, but we can braid out that there.

B

The question is I think it was sort of clear, well I. Think we covered last name like how very my notes it covered somewhere how to adjust these rules. Kind of that. True.

B

This to get I'll be sure dad make a new one. I think I made a new one. I.

A

Just pasted it oh yeah.

B

So something like this, which you would already started to do, oh so then the question is sort of. When do we generate these overrides impulse and also I? Think in general our query structures a little bit wrong.

B

B

When I would like is that you think, when.

B

What happens is we have the.

B

Okay, we get the you get a request for our callback with: let's open a good stock source of it,.

B

So we have this day, trust our database thing and at some point we get, or rather we have this chalk. Solver I guess is where this comes from.

B

We get a request, a kind of callback for what are the program clauses for a given goal. I have to find where that code is.

A

B

A

B

Still not used to the non-motorized thing um so and.

B

This is really a place where ideally I think I'd like to do some caching, but this interacts with the rest of our database.

B

So the tricky part is here this code. We have this function program clauses for gold.

B

B

That's gonna have to what we want to do is generate okay, let's just jump back one second, so the override. Let's come back to the original question: when do we generate these overrides clauses?

B

And the answer needs to be.

B

Basically, when one name Bowl specializes, another I think this this this. If I did it I recall this ID, this overrides were tied to a particular associated type yeah.

A

That was the idea of an associate alright.

B

So when one name ball when in Bobby specializes.

B

Then we would generate for each I and imp will be for eat and let kind of let IBA be the ID of the associated typing in belay. I think generate overrides right now.

A

What about for the trademark part of this as well, because we also have like 40, I, guess: I, you.

B

Know we are booty iterator, something.

A

Like that, right.

B

So if info B is for the two it reached, let's put it let's say like trait ref, a B, the tree graph from nimble a and let your f be either trade rep from.

A

B

And this is gonna get generated for trade, ref, beef and really you're gonna need some wherever the, where clauses are from previews. So.

A

It simple a this iterator, oh okay, you're using the same example.

B

Import I mean give us the example.

B

This would be so in our. In the case the example above I.

B

Believe we would generate overrides V 0 of spring.

B

In other words, we take it from input, B right and the reason is imple. B is overriding that item for those cases that it applies to yeah.

A

B

It's really, this is not relevant, so it seems like program clauses for goal when, when the goal is overrides of v-0.

B

The V for some V.

B

Needs to walk all impulse, I mean really means to walk all impulse that potentially override the in pool containing V.

B

And for each of their associated types generated clauses.

B

A

B

It gets it up, so the associated.

A

Type or any simple a would be at some point in the specialization tree and we would have to look at.

A

B

Impulse and then.

A

Generate override causes from that so.

B

That means that this function needs.

A

Access to its position right to the.

B

Tree yes, so right now, let's take a look back right now: there's there's the rust I our database, trait and then separately. There's.

B

In this coherence, module.

B

There's this thing called the coherence solver, which you can instantiate for a given trait, and you can ask it to create a specialization priorities which is pretty much the specialization forests. If I recall um and yeah I think this I.

B

Think what we want.

B

You think we want a.

B

Second yeah, so we could do this in a few ways, depending how much we want to hop like tie to the use of chalk. I.

B

Think probably we don't sorry in that chalk to the use of salsa I, don't think we poke well, we basically want to do is have some way for the program clauses code to invoke this relation priorities function, but I don't think we want to do it directly instead, I think we want to do it kind of through a trait and right now yeah right now. We couldn't call it directly anyway, because we don't have the solver choice that we need to basically says what solver to use, which is fine, I, think what we want.

B

So one way to go about this would be.

B

Is to extend the rust I our database straight. Let's do this.

B

Option a and the rust I are, there is true, we would add a specialization tree.

B

Something like this method and in the chalk, integration crate. This will be mapped to a salsa query. Probably that that invokes the code. Talk solve coherence, module, so what would happen? The flow would be like talk. Solve clauses invokes.

B

Box off invokes specialization tree method, which is implemented in our crate.

B

And then that in turn invokes.

B

Ox all of coherence, which will recursively use the clauses code and this little like indirection through the trade, gives the integration create a chance to pick the solver and detect cycles and fail in some way.

B

At the moment, panicking is probably good enough, which is what would happen by default.

B

That seems, okay, the other option would be the way salsa is set up. You can sort of have partial databases. We could have like a partial salsa database in chalks. All that says, I offer the following method: specialization entry and I extend the rest.

B

I our database or I require the rest our database tree, and then we can because use to salsa query groups, but I think I, don't see a lot of advantage to that and the disadvantage would be that if you wanted to integrate the talk selves into something, that's not using salsa, you sort of couldn't, whereas here in option a you really have more flexibility.

B

A

We rebuilding the specialization shape for every doing well,.

B

You'll note that it's tied to the tree all right, so it's not every imple, it's every trait using salsa would get cached anyway. So you would only do it once per trade. Currently we do it. I, don't know the answer.

A

I think they good for every trait for.

B

Every trait we do it yeah, so the difference would be here also that you would only do it if you needed it in this setup right. If you.

A

B

Default type somewhere and then you'll generate an override goal and when you go to solve the override school, you'll create the tree. But until then you wouldn't- and this tree, let's see I, don't really remember what shape it has.

B

B

Like what is a specialization priority, it's probably just a number yeah, okay um right, so we can then use this.

B

If you had once you get this tree in an info, you can basically iterate over all the impose with lower priority than you.

B

Right and generate an overrides for them. It's a little bit crude.

A

Yeah I think you'll have some false.

B

You'll kind of have some false false rules, so to speak like if you had something like this.

B

You have this setup.

B

Presumably I don't know exactly what priorities these would get, but it's plausible that this could get. You know priority zero, already zero, whatever I already won, and hence you would have overrides I.

B

Don't see that this is harmful, but that rule is correct, but you would also presumably get this rule, which is not useful kind of box et.

A

But wouldn't you start from v-0 right like you would get something like math lecture you get like overrides the zero.

A

With oh sorry, connecti, oh right, yeah, and so this would thank.

B

You you would get, you would get normalized back of tea. Yes,.

A

Yes, you get this and then because you have this b0 here, wouldn't you be able to use that to only get third people here? Why would you also generate going for v1 for.

B

This rule you're also going to make a roll like style right.

B

And then now the problem is when we go to solve, find all the things that implement overrides of v1.

B

We're going to find this in pull we're gonna see that it has higher priority than the input containing v1, so either will will generate.

B

If we don't do anything else, we would generate this clause. Oh I.

A

See it's because we're in lower priority yeah.

B

I mean you could do more work to figure out if this is like this is actually a parent or is it a non related brand sort of treaty of Impuls, um but that's kind of annoying there? You did all the work to build this tree in the first place, they would I think it would be better. We already did that work when we build these priorities, so what we would need to do is.

B

Basically, create a better or richer data structure, it's not just storing an integer but is storing actual parent-child relationships.

A

B

Said I, don't really think there's any harm in this setup, I mean it's not it's sort of a room for improvement situation because yeah we would make this rule and yeah it's it's sort of not correct, but it would never unify because back of team you know boxes do not equal so like, in other words, if the original code is correct- and indeed these are unrelated impulse, then this could never hold true because they were supposed to be disjoint.

B

So eventually we should always rule it out, but it's kind of wrong and it's wasteful.

B

A

So there's a couple things: I have to be good with you right so I have to add some things to the database trade. Yes,.

B

A

Need to integrate that stuff with salsa I think that's already done.

B

Yeah, so to extend the rest idea in our database trade with a optimization tree or something forest method yeah, we call it and.

A

B

B

Connect that right, let's see there, should be a salsa query or a probably, let's see.

B

B

So they put it always in this file. Query look! hmm So we have this coherence, query.

B

What does that do? So? That's a little too broad there's this existing query because it it goes over all traits, yeah.

A

B

Kind of want to extract this into a query itself.

B

So maybe the first step is create base sort of coherence, trade, ID, query with this code: I don't know if we want to call it coherence or specialization forest or something else, but yeah.

A

I was gonna, say change. It.

B

And then extend this and then it can invoke the query. Both we just added and then we should be able to extend the croisé generation code accordingly or to use that method and create overrides.

B

That's probably the best way to go forward rather than X I was originally contemplating well, should we I mean actually hmm yeah okay, so this seems reasonable. The other option would be that for the purposes of testing you could hard code. The relationships between Impuls, somehow but I think that's actually probably just more work. Oh god dude. Could you tell me a bit about the.

A

Way, we store the specialization format. Yes,.

B

I mean like go on. Do a specific question: they're doing yeah.

A

B

Is it in tree? How is it a tree yeah.

A

So it looks like we're storing what was it just the Impala and a number right, yep.

B

A

What what makes that a tree.

B

Nothing, but we know that it's a tree because of the nature of the analysis, it's, but it's not that we're not storing enough information to recover the full tree. That's the problem! That's why you might make those extra clauses. Oh no, so you're not wrong about that. But let's see where's the.

A

Maybe I should ask: how do we yeah.

B

I was gonna, say why don't we just look at the code? It's not that complicated. So when you do construct the specialization priorities, it calls this build specialization. Forest yep.

A

B

Calls this method visit specializations of trait for each one. It gives you basically pairs mm-hmm.

A

B

Add edge method where's that.

B

B

Where did I put that here? Well, this is where the visit specializations is we'll, come back to that, but where's add edge to find.

B

Comes from somewhere, oh you know what this might be. Just the graph great or something oh I see. Let me see, let's try to remember oh forest, into graph digraph map- okay, great! Oh, it's coming from pet graph, yeah, okay, so yeah! So it just adds edges into a graph and then I, don't know what this diagraph map thing is and.

A

What is a directed.

B

Graph for sure.

B

Not sure why you.

A

Had to grab the carriages.

B

Okay, so it gets converted to a digraph map. Probably just means that there's a hashmap mapping from the node labels to the node IDs, with your integers, the.

A

So it looks like they're storing yeah. What's that looks like restoring unit in a ditch? Oh that's.

B

Just the yeah, so the extra data for each edge, you can have a weight on the edge bouncing bang, there's no weight. So then it returns a graph. This is just a graph at this point. This is actually what we really want. This is the real data. Okay,.

A

B

It looks like we then throw that data away by calling set priorities which essentially iterates over and says you know you start, you start at depth, zero, I, guess externals must mean something with no incoming edges. Okay, you started zero. Then you visit all of its children and since you know it's a forest of trees by construction and I. Don't have to worry about cycles.

B

So the question is how you get at byte construction that comes from this method, and what that method does is here.

B

So visit specializations of trait it goes over every pair of impulse. These are a and B or they call it left and right.

A

Yeah, when it does the check the specialization check, yeah are you surely this could before this response make sense? I think I understand the priority, so it's just the depth of the tree yeah. So it seems like what we.

B

Probably just want to do is just change that specialization priorities, data structure to be in action to like store the actual grass. Why.

A

Didn't we do I.

B

Don't think there's a real reason: I mean this. This code was written without yet having a consumer, so it seems like the kind of thing, maybe I, think those boats that wrote it. Maybe boats have something in mind, but we've changed directions and.

A

So one of the things you said earlier was that you'd want to iterate over all the impulse with lower priority. That's because things higher up in the tree are overwriting. My things lower down in the.

B

A

Okay and does every trait have one tree or gonna trade before us as well.

A

It's a forest, because this is a specialization forest right. No, it's.

B

Not really a tree I lost this tab. Somehow.

A

So, what's an example of a natural forest because I won't.

B

We just covered one here. This was a forest. This example we did okay, Beck of T and Bek of you. Thirty-Two have an edge between them, but box of T has no edge to either one so I see.

A

B

Like two there's two trees, one of which is a singleton tree.

A

Right I'm sure I'm gonna have lots of other questions, but this has been very helpful. Thank you great and just be all right. Cool have a good chili for this happy America day. You too happy whatever.

B

You say in Canada.

A