Rust Programming Language RLS 2.0 Working Group, 27 Mar 2019

Previous Meeting

Next Meeting

⏯

youtube image

►

From YouTube: RLS 2.0, Salsa, and Name Resolution

Description

A pragmatic discussion about how to proceed integrating name resolution with Salsa and RLS 2.0.

A

Now I can hear you.

A

Are you based in building somewhere or Garrity's.

B

So, which we start Alex I was reading your description and.

B

A

B

One thing I could explain: I could explain a little bit how like chalky and all cycles, which I think.

B

Or we could just talk about it, I think maybe the best place to start is actually mapping. Would you, rather than being totally abstract talking about the actual problem like how you got to that.

B

A

I think maybe it's even make sense to take a step back and speak a little bit about like name resolution in general, and why do we want to hear? Do this whole, so yeah? Let me just describe what you're trying to achieve.

A

We would like to have name resolution to be incremental and it's probably make sense to ask: why do we want it to be incremental, because example, in something like intellij name resolution is not much mental but is not incremental, because it is on-demand and really is basically the in Java every file has especially derivative and you import stuff using fully qualified name. So he can basically maintain a mapping from fully qualified named a class object in its internal presentation, and this mapping is like it's very easy to update after file changes.

A

So in IntelliJ you basically resolve names in this part. Every time you need to import something, and if you resolve names locally inside the file, you can just basically use of all of them, because it's usually not that question fork anyway, but you can also imagine that lay solutions which resolve name only in single function or something like that. Basically, you can be really lazy in rust. We, it seems to be that we can't really be lazy with name resolution inside the thing it is scientists, single crate.

A

We must name resolve the crate as a whole and when I say name is all basically neighbors of all the imports like not in solution in science item, but it's just like top-level stuff, because macros and imports need these exploitation algorithm and it's completely unclear how to make that on the mat, because this seems like it could take a fair amount of time. We need to make it faster and we need to somehow link realized.

A

One way you can commit lies. It is to memorize macro implications themselves. Basically, if you expand this macro using this input, token stream- you just analyzed it and when you expand this macro in some other context, you just take results from cache. This seems like an easy part and also requires part, because macros positional markers can be it's very complicated.

A

That's leaves us we've resolved in imports. Using this exploit iteration, loop and I think we should incremental eyes the is as well, because it's actually the code which works industrialized now is pretty fast. It's like tens of milliseconds, but it's like not super complete, not super complete and even tens of milliseconds is like something you could spend computing typing trains or stuff, like that. I think for completion of the budget is about like 100 milliseconds, but but even 100 milliseconds is already a noticeable perceptible delay, so the ETL does.

A

It will be like something like 16 milliseconds in your frame. So like tens of milliseconds is something we wishes were filed to, say. The strategy which I think could work for making this incremental is to detect what and there when there are now changes on the top level. For example, when you are typing inside a function you easily don't want to in a default name resolution, because all the modules are the same. All the imports are the same.

A

You maybe need some imports inside the function, but it's not over, so you can just resolve them legally yeah. So here's the basic idea Ian. So we start the query in such a way that it looks only at top-level items and it's not completely ignores bodies, and that means that type in anybody is okay and name is evolution is reused, and this actually is implemented and works quite well. So when you type something set, the body a resolution is instant. When you add a new import, you still got completions for import.

A

These completions are still basically instantaneous, but they rerun the in solution from scry for the whole crate and the problem where these approach falls down is macros, because so specific instance, where we conclude name resolution, but where I think we could avoid confusion in solution is when you have some item which is decorated by a macro, so something like lazy, static and inside this item there is items body and you type something inside the body of the item entirely.

A

You should maybe expand this single macro understand with the set of top-level items is the same and the computer name resolution. But currently, when we compute a set of top-level items itself, we include microbes with their bodies in this set. So if you change microbe body, you change the sort of top-level items and you have to rerun the whole name resolution, even if the result of macro expansion to basically be the same from the point of view of name solution.

A

Yes, I think this is the statement of the problem.

B

You really want to reuse the expanded form. We went out a way to be expanding necklace.

B

And don't think I didn't understand when you're you said that the macro and its body does include items. So if you change the macro body and in detective rear-ending, was that right? Yes, but if you're taking the body of some other function, I wouldn't tell me when you change the contents of the Mac.

A

B

Repeat this, please, it's only when you change the body of the macro. Yes,.

A

Yes, you change the body of the Metro, but like macros, like could be big, like you can imagine sampling procedural micro, which the currents a function, for example, so typing inside this function, is basically typing on the top level.

B

B

Why do we think that we could avoid I mean when you do change? The body of the map where we are gonna have to really expand to see what its result is? Yes, because it might have been different. Yes, is your idea that after you, we expand the macro? You can figure out that the solution didn't need to change personally name. Yes,.

A

Yes, so, like lazy stats, for example, is a very good example here, because if you change the definition how you initialize really static, you don't change the name of the stuff. So, from the point of view of any resolution, this is actually now of change. Nothing changes.

B

Okay, so in the dark, I'm gonna write this out over Society. So one scenario would you like? Do the leading static I? Don't care how the syntax is whatever it is. Heading left.

A

Cookie-Based example.

B

Okay, so you're saying right, so the change is to alter this line.

A

Basically uncomment it yeah.

B

And so that doesn't need to affect.

B

B

Okay and so the challenge you're finding, so what you would like to have understood is some way to say basically, some way to say we had like a top-level query that was like a resolution was also as a different, that's kind of a fully missiles or or something this kind of gives up a map.

B

Look like identifiers to ID here, something it's close enough to traverse and then it in the process of figuring these out. This is like a fixed point.

A

B

Trade in the process, it invokes like expand query.

B

Let's say this: has ID ID l0, it would sort of say, hey, expand this sorry, not expand memory.

B

Right and the date, the problem is this: would this in turn uses a m-- resolution results right, really, I suppose this is also parametrized by, like probably a module or something.

A

By crates, okay,.

B

So this uses those results. So now we have a site called great. Yes, this axe.

A

B

Uses those results or figuring out which not really I, suppose it's figuring out, which definition lazy static? Yes, birds, too. Yes,.

A

So it does not like actually takes an ID l know it takes an identifier, lazy, static.

B

Okay, if you figure out what lazy static refers to so there's a query: usin, it's like the code has implemented today. Probably does this internally. Yes,.

A

It is not a query because this runs inside this, like general six-point loop, so it just looks up in this map which we are currently building.

B

And so then it would invoke like let's say it: we figure out what first to use the map we are building. We get back the idea of a definition, that's easier, and so then there's a query. That's like expand macro invocation and 0 with the arguments from l0, I guess state.

B

A

B

B

And that query, though, doesn't recursively refer back to neighbors or does.

A

The expand, macron vacation query is all good. Now it doesn't into the first name resolution but like this actually is important. What are the arguments to this query so like if we actually pass token three as an argument, we need to have this token three in this neighbor solution results query, and that means that we depend on the actual ticket read about on the results of the expansion.

A

So we could pass an ID here like the ID of the macro and this actually, what makes it difficult, because you need results of name resolution to assign this ID so, for example, okay in the simple case, this list static is a macro in a file which is typed by the user. So any could be a position in this file and this would actually work for one level. So.

B

To be sure, when you say the ID, you referring the idea of the macro definition or invocation.

A

A

So I, like the idea of micro invocation, could be basically a position in the file, maybe like a relative position or some path length. So it can not be. You know the patient on changes, and this would work for one layer but say this list static generates another macro, generic, something which invokes another macro, and we need to expand that macro and we somehow need to identify that macro and kind of to understand the meaning of that ID.

A

You need to know the results of invocation or the previous macro and to know that you do need name solution, I think.

B

You would need what you would definitely need it seems like is. The IDE would have to sort of tell you how to recreate the input. I guess right so like so for one level. So so really, then I guess what the question is. It's like what does the ID nap? In other words,.

B

I'm thinking of the salsa Internet privacy, you know where the ID could be, as you say, like the base. Ids are sort of some path through the invoice to some bytes I guess you can just think of it as a file line for now.

B

It's like the base level and then the next level would be like a span into the result of a macro expansion, which means we would need few other IDs to identify it right, yeah, and that seems like it covers all the cases. No, so there is your write. That name resolution plays a role because figuring out the D. In that macro expansion got the definition, that's like name resolutions job, but given a definition ended in with.

A

B

Think you could, but I don't think this would solve here. So so I think you could say: okay, I think you could make an ID that maps to something like this over here and the idea would be. If you have to. Let's say that the lazy static is inside. If one macaroni generates the invocation of another mackworthy, then what would happen a crow, a spins to be banned. Something's been right. Why you would wind.

A

B

You would invoke like in macro inculcation a definition right and this. This use sight is just a base decision in a file, something that would give you some set of tokens which are part of the.

B

Then you would ask for okay now. I would ask for light.

B

Now I might say.

B

Later I, look at those tokens, I see be ban and I say I make an ID.

B

Which I'll call B? You say the corresponds to them there. Yes, yes, I.

A

See I, yes, I think. Actually this might solve a problem. The problem was that in my intimidation, I used.

A

Okay, so in my implementation, I used on the user side as an ID because, like in fear, we're given your side, you can get to the definition. If you involve name resolution because I could say you cite if, however, the we actually put definition of the macro into the same entity, this seems like it could just work, probably.

A

What does expand microwave invocation return because it is returned to for talking trees? Doesn't that invalidate the whole cry anyway? Every time we change something.

B

Right so I think that's I think you could do something, something like what I'm showing but I think it may not solve no problem like I just realized it.

A

Yes, I now understand that this is at least a partial solution. Due to the problem, that's Florian said because, like really, we need to put some kind of extract top-level items between expand marker in the occasion and the rest of the name resolution.

A

B

Yeah I mean the problem: is that explained macro Invitational right? It returns to full. It returns the full set of tokens. So in principle you could have a layer in between that sort of extracts out the stuff that name resolution cares about, which is like the definitions that results from a macro invocation for something right: yeah, yes, and if you did that, you might well find that the full name resolution becomes reusable, because you have like that name resolution which directly in focus like definitions from a crow invocation or something a.

B

Death a use sight which wouldn't I guess this would probably return back.

B

This would afterward, maybe definitions isn't quite the right term, but it has to include also the macros right. They need to be expanded further, but I think this idea be relatively stable, like it would return back.

B

Be you cite this? Yes.

B

Which, hopefully, didn't change I, guess like actually using spans, isn't probably great, but if you have it or stable for identifiers, um then, and then this would say okay, then we would invoke definitions from a clarification.

B

We would figure out. The name somehow do this, and that point would be that, while the results of expand macro implication are dirty the results with definitions from a clinician.

B

Yes, so you would reexpansion she wouldn't, or some of them I think you could do something like this feels like it can't work and in fact, like it feels sort of nice because having a label, you did. You want some sort of ID for the text in a macro, then, just on its own, you can sort of trace it back to recover. That text. I mean that's kind of what this ID gives us.

B

B

Think what this solution does not give us is the ability to have finer grained reuse within a crate. If we think we want that like right now, you are doing name resolution across the entire crate, and maybe we would like to be able to stay within this module. Nothing changed so I don't need to compute anything. You know that's a little bit complicated because of the interdependence between modules.

A

Yes, but my hope is like that probably is a point to the Damini of diminishing returns like if we can get reuse across not typing on the top level, and that's probably fine.

A

B

I think like at least at.

A

Least the mists, based based on what's performance, looks like right. Now that would be justice. We will have instantaneous completions right.

B

It seems like, if we're careful with our with our choice of intermedia inquiries right, then the only time you would have to rerun name resolution. So when you add a new item or when you change the name of an item or in some other way like this or at a new macro application at the top level in that is probably unusual, it's not Bachelor.

B

A

Right, so, in a sense correctly, what we're trying to do is if the outermost.

B

My configuration changes, then we hope that the innermost.

A

One docents doesn't change, becomes cached by the creationism and set rights.

B

It's more like the set of definitions created by the macro. They'll change, like the actual macro, expanded token tree probably will change. Well, that's the whole idea. It is changing. We know it's changing.

B

With the innermost ones,.

A

Are cached because they hopefully don't change.

B

A

The locations themselves like what this token tree expands to giving these micro definition is definitely cached, and this does not seem like a hard problem because well basically cache it and that's it, but I'm understanding that the specific names which are in the result, the name of the invocation, is the same.

A

So basically, the in the macros would just be reused if they resolve to the same macro. Yes,.

B

I think that's right and I think what this would do is like any macro whose definition changed with Apple to expand in physics unavoidable.

B

But as long as generate the same set of ID's, the neighbor solution results themselves to con. The key thing would be coming up with the name of like making sure the ideas are sufficiently stable, that it's true but I think the basic trick for that is to make the ideas a tree right, so that you're not using like the offset in bytes or tokens the flat list, because then inserting things in the middle.

B

The list costs problems, but you know have some tree structure to it, so that inserting the body of the lazy static doesn't affect the idea.

A

Well, actually, also, the second trick we should actually use for items now like the IDS are not trees. The IDS are positional to identify an item in the file. We enumerate all the top-level items and use the index of an item is as an ID. So it's like kind of not really a tree structure. It's a positional positional thing, but you carefully arranged so that positions don't change, often.

B

A

That sounds like it's changing when you form a sort of L, for example, because then the positions changed with structure doesn't ready.

B

Right right, the ID comes out the same, but the thing with the ID maps to changes um I think it.

A

Works to class.

B

Name record this.

B

Seems like a cover that would make me happy. I do think at some point. We can accommodate this recursive invocation style, but I would want to I don't mind putting off the day of reckoning a little longer if we can do so.

B

A

I think I feel satisfied well, at least at least I want to try it. I am Not sure that I don't actually hit a wall somewhere in this plan, but I don't see problems before implementing it actually, actually, if, if somebody else wants to dig into micro, Spanish name resolution because feel free to join like to work on something else like doing Diagnostics now, it's also very exciting I.

B

Would love to but I don't think that's a very realistic other suggestion. So I'm not gonna make it I know. I will say: I will.

B

See where it goes, I would be the best I could do sure it might be useful, like I think it might be worth trying to play with this. In a smaller example, I, don't know how much Oh I never actually worked. In my say, maybe it's small enough and you're familiar enough that you move pretty fast like for me. If I were gonna, try to fruit, this node I would make a little stain I.

A

B

A

So yes, one thing I want to talk through is that how does this work, with macro by example, defined like part of the crate so like what would be ad for macro by example? Is it the intern intern version of basically determines which defines the macro or something else.

A

Can't just be the idea, I thought.

B

It would just be the idea, I'm not sure, I, understand what it makes it harder.

B

A

Okay, yeah I think that they do it work. I was under the impression that, like you, really need to intern the macro bodies, but it doesn't look like this okay, so we probably can do this here without that internal branch of salsa.

B

Probably I yeah I think the original.

B

Are we ready to land gorgeous but a toilet, but maybe it would be nice if we keep that a little separated, I guess um I do think that will be a really powerful in a blender for this sort of thing, it's exactly the kind of case where it's useful.

B

Because you need some way, but I mean you could the interning branch. Ultimately, you could always like it's really just useful for constructing these sort of complex identifiers, but they could always be built out of our system. Yeah.

A

Like we do haven't turned in already, it's just like handwritten ends, no good see at home right.

B

So it doesn't really enable anything. You can't already do just makes a little nicer.

A

B

A

Is it like and I'm satisfied more than satisfied? Well.

B

Let's see what happens, he I mean, try it roblox again.