Rust Programming Language RLS 2.0 Working Group, 26 Feb 2019

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: rust analyzer syntax trees

Description

@matklad walks us through how syntax trees are implemented in rust-analyzer.

Recorded 2019.02.26.

A

Okay, let's probably get started if anyone joins later there is a video recording.

A

Okay, so I'd like to talk about the current implementation of c63 North analyzer I, think that, like a lot of details should be changed to make it like more efficient, etc. But the general idea seems great to me why not because it's like a great idea but because other projects like crossly all suites, are trying to use it. So it seems like a reasonable, reasonable theory that it should work for us as well, but, like macros, can throw a wrench into the details.

A

I am actually an issue on rust and wiser repository about like finalizing the design of industries. So if you have any thoughts after the meeting, you probably should base the comments on this issue.

A

862 currently position basically have a list of requirements and I'd like to briefly went through them to understand why I've been doing things the way we do them, so the through primary becomes trains on the syntax tree. The idea is, is that the syntax tree must be faulted.

A

Elegy impotent must maintain all whitespace and comments, parentheses, cetera et cetera, et le, like it should maintain them in a like, more or less explicit form, so that you can actually have a wide space now, and you can like take a look at the knot to the left and not to the right, like you could just store a source text alongside the tree and saying if this is a full fidelity implementation. But if you have, it won't be too useful. For these basically important requirement is that the parse in itself must be our tolerance.

A

What I mean is that, if you throw any valid, would have a text at the parser, it must produce some kind of a source tree which should be full fidelity and represent this like completely bare which detects Texas, 100% et le person, should also figure out fragments of red source code in these garbage texts and like produce best-effort synthetic story, even if it doesn't match the gram of rust.

A

Exactly what I mean is that like, for example, in Ross drama, each truck must have a name, but we must allow for syntax tree to have a struct which has no name. It has just extract keyboard or maybe like a list of fields. Okay, other requirements, like probably less important, but also quite important,.

A

The interesting bit here is probably represent in a hygienic macro expansion because we certainly can imagine a situation and, for example, like we used once in 63 for macro expansion and various index 3 for actual any fishes, but I fear at like it could roar, but it would mean duplicated efforts, etc. So if we could use a single syntax tree to do like low level, compiler, rework like micro expansion and a resolution and like just ID full fidelity work that would be great and here another interesting bits that I need probably needs.

A

It's like not one half percent crucial, but pretty important is like ability to use parent pointers and absolute offsets with the tree. So because in a compiler you technically take a root node of some function or something else and like walk it in top-down manner, and only expecting children, in indeed at least start with an offset in a file, and you locate a node at this offset and traverse the tree upwards to find like a function with this offset so like parent pointers are pretty important.

B

And can I push back on that just a little, but I mean at least in the RLS, for example like what you really want is the ability to find it. The nodes that intersect a lion column right the end of the day, a cursor position, or something like that, and the parent pointers are certainly one way to do. It.

B

I mean I, think we may want them anyway, but, like you, also traverse the tree from the top and find the match rate, and you may wind up doing that in order, because you have to search you have to index it by offset anyway, when you get a request in from the ID you get like. This is the line in column right, not here's a note.

A

Yeah that could work as well, basically like, if you have information about offsets that basically isomorphic to have my parents, a child relationship because, like something is parent of something, if the text offset is within the extent of the parent node so but like kind of partial processing, it still useful to just take a look at the parts tracked and like to figure out what kind of node is it like, for example, okay, so you have an offset and, like you figured out that you are at the identifier and then you need to somehow I classify these identifiers.

A

It is like part of the pattern, or is this expression, or maybe like a Strathfield and looking at the parent in this sense is useful, not crucial. So it's like it must have category. Not him like absolutely, must have a useful property yeah.

B

I guess I would just I feel like it is useful, but not for the reason that you say isn't you want to kind of say like in order to yeah yeah.

A

B

Still have to search from the top to find where the cursor is, but one it is just useful to be able to go to parents, because then you have to pass up the whole yeah.

A

Yeah, that's true. Okay, so.

A

Yeah one more kind of model property is ability to do incremental, parse and, like incremental parsing, what incremental person actually person algorithm, which you can like rerun partial results, but another part is like the actual syntax tree structure which you can modify in place instead of like constructing from the other pieces, its I actually don't think that this is like it really really crucially important thing, because Arsen on the way you want usually to intrumental your bars on a single file and bars in a single file.

A

Is it fast enough, like it's like tens of milliseconds? It's like not an extremely big delay, but, of course it's like would be more memory efficient and faster to just actually update the tree instead of reversing everything from scratch. Okay, so that's a kind of like basic requirements. Let's take a look. How seems extreme breathalyzer work to like keep these requirements?

A

The rough plan is, first of all, to work through the EPI like behind level, public API ups index 3 and then to go through the implementation of the data structure which powers this index degree, which is basically the same data structure which is used in Rhossili or in Swift's new lips impacts and then to go through this incremental and error, tolerant, parson bit, and maybe take a look at how we actually use industries inside of rust, analyze.

A

Okay. So, let's start with a public API. So here we have an example through in which the some rust source code- and we parse this stream into a syntax tree and kind of like one, of course, Department.

A

That I like to achieve is that person should be independent from the semantic knowledge to compile, and but we should be able to parse some stream in isolation without creating like some kind of the compiler sessions cetera, we certainly will need to add some kind of, like addition, 2018 or something like that to account for addition, but I hope that, like the addition is the single flag from the global state, we need two R's files.

A

So what we get is actually source file struct, which represents the ice-t node for the coal fire and due to the weight ownerships. Is we get actually a smart pointer to the source file? So 3 Ark is like just it's like a usual art, but it points will be whole tweet, so it like you, can imagine some kind of an application in raspberries and important.

A

The main object is always held behind an art, pointer, and so the code base polish interacts with either art of this thing, all with the reference to this theme- and it never seems like they shall bear thing. This is what happens with industry. You either see a reference to a node or.

A

Twee arc of node and you never see burn on the self. So all these ice-t nodes at, like usual, a pilot example in file. We can iterate items where item can be like extract the functions, etc. So here's the list of items you can see inside the file and we can extract the particular items they like this was function definition and get the reference to it. Although we started with an old version of the file over tear also always yields a yields, references.

A

We, however, can create an old version from references, so this is like shared from with these problems. It was plus you get a reference and you can get an old version of this reference, which is the cheap reparation which does not clog that also fix tree, but just bumps the arc counter for the to itself. So you know, we've got this function, node, we can inspect its name its body and we can get the expression from the bodies. Etcetera.

A

One thing to note here is that all these functions return options. So, although, like the name of the function is mandatory, it was drama. Here we get an option because syntax tree is able to represent partial notes and.

A

Yes, so here I have that I function, without a name and in the syntax tree for a dysfunctional series, append F, not all the way, the name and that's.

B

A

B

Wait two things actually a couple things, but let's start with the most recent: what.

A

B

This, like wizardry, that you're showing is here's some integration, where you can see the parse tree or something yeah.

A

Yeah, this is basically the parse tree or the file I'm, currently editing under stage of life and kind of cool and nice. That is cool.

B

For the tree arc struct is this basically like an unsafely implemented thing that keeps the arc to the root and then has like a pointer to something that's owned transitively by the root set? The idea? Yes,.

A

We will go for the implementation, like you know this, a while yeah but like here. The idea is it's a bit of unsafe code, which I am not entirely sure is correct, but I hope is correct or could be made. Correct sounds good, okay, yeah, okay, so we have, we can inspect beads or tweeze, and this iced tea name is also like. Not an insurance to english represent the name of action, but an actual iced tea. No with parent pointers. Offset register so like this shows how we can use like strut like ice team.

A

Now knows we can also have like a nice API for an enum like ice-t note. So, for example, here we got an expression for the block, so this would be one plus one and we would like to know which kind of expression is this exactly so we call a head method and get back and and on with all there is kind of expressions we have this.

B

A

Like interesting feet, and because we do not so I see directly as to your panels, so you can't do nasty partial motion.

A

You can, for example, a directly writing much expression for an expression which is an addition where the left-hand side is a customer enter or select that you need to do this like one layer of motion at a time, but you still can help these Russian and exhausted, check and citrusy trap and what's cool about it is that it seems to me that when final presentation could actually be flexible, there is an all these like expert, current and up stored anywhere. It is like route ratings on the fly yeah.

A

So this is basically all the API of be like x layer over ice-t, where you can get no, which is a particular type, and if you some children or collection of children, or it can be one of the kindest research. There is also a so called untyped where for the ISDN, where there is only a single type, syntax node, which can hold any note.

A

So, by calling a simplex method, we get a reference to the next node and like what's also kind. Of course, representation is that this index node is basically exactly the same as the expression node we've got before so every type ice-t node is a transparent, wrapper around the on x index node and what it says. So it doesn't store any additional fields, it'll cetera. It only gives you study information about what kinds of fields are available for this index node.

A

So you actually can get a reference to a specs note from a reference to an expression due to the fact that this is marked as wrapper transparence.

A

Yes, oh this transparent, beat is important, and this unsafe Impala is also important to pass between the references.

A

We can also get in the opposite direction from the antique node2 typed note, the cast operator, but costs obviously returns an option because you don't know if it's not actually that's expression. A lot and yeah the app cast also returns the references, because this is not parenting.

A

The way the way cutting walk is that each team picks north towards so called syntax kind.

A

Yeah, so subscribe is giant annum, which holds all the various type of syntax note rust chest. It's both for tokens, like parentheses, curly, braces, etc, and for like bigger things like if expression and expression, cetera, et cetera and.

A

The cast a curator basically checks that the kind of Angela ends index node much they study kind of the highest expression and then just has to stop or if it doesn't match it returns. None.

A

Yep, so this Ross index contains a kind it contains. Text range and text range is actually an absolute range into the file, so it's both a start offset and the end of self, and this is the an interesting bit because the syntax does support incremental parsing and in Toronto a person and ability to store absolute offsets is like somewhat contradictory, because when you modify part of the tree, you have to fix all the above sets downstream, and it actually is possible to do that and with like vlog and complexity.

A

If you use the clever implementation from Roslin and lives index, we probably blow talk about a bit later, but the general idea is that you calculate these ranges lately. So if you haven't operated a particular range, you haven't to update it and if you have to update the range you, it means that you have colitis it, and that means that, like average time to update all the ranges, is actually constant because you've spent some a lot of credit to calculate in those ranges yeah. So it's not also like contains their full fidelity text.

A

Of the note, like exactly the sequence of bytes, that it's that is in the source file, it doesn't like contains literally a reference to a text, but each token each leaf porting contains like a bit of text to distort them. So you can get a text to the node by just walking all the talking stuff right.

A

It also contains this generic API for Jefferson tree you get, you can get to the parent to be first child, the next sibling, and that allows you to get from any point to the tree to any other point of the tree, and this is the kind of property that you can get from here to there, which places like requirements on how the API might look like, because it means that you need some kind of a shared ownership. You can't draw.

A

You can hold a reference to a node inside the file and drop all other nodes, because that would mean that part things would be invalidated in the current stop you also, you always maintain the whole file.

A

Okay. So obviously, using this like basic atomic methods, you can build some nice services. For example, you can take all the ancestors of this expression node and find a function definition among those ancestors, and here you can, for example, compare that yeah this function gets here is exactly the function we have started from over here.

A

We has also like siblings and a way to walk some tree.

A

It's interesting that yeah, due to due to the fact that we have parent quarters, we can actually implement what in a subtree using only constant amount of memory, so you don't have to write a recursive traversal, which maintains a stack. You can do this in a single stack frame.

A

There's like a nice pre-order API, which tells you hey. We entered this node and then we left this now then it can be used to implement, stop like printing a tree and yeah. Basically, these three presentation is implemented using this pre-order method and enter live events used to maintain indentation.

A

And here we actually see that we have this white space now explicitly in between.

A

Yeah, so usually, when you traverse between you, want like some kind of an iced tea visit ever expression or visit every item, or something like that in this two part just way you can do it is to using the cache method. So here I would like to collect all the expressions so I get the raw syntax of the file and get all the descendant modes of the file and kill and cast an order to expression. Take on the ghost results, the Poisson and you get Texas etcetera.

A

It's also possible to do a visitor style API, it's possible to implement visitor as selling some trait, which you have to implement, which has all methods deposited, but I kind of try to do this in a more cute way where you can write a time directed visitor. So you write like I'd like to use F and F and used by a lambda which accents and F, and you can do something about it. So this is again works because each F and F now's its index kind.

A

So because the visitor knows that it has to walk a friend f, it knows that it has to look at the node with this particular index kind and yeah. It works. So this.

B

So it's kind of like a builder pattern for visitors. Yes,.

A

Because you just think can supply it a lamp and it will figure out the types it's cute. It's.

B

A

It's cute, but like actually in practice it's not much better than just using casts because it's doesn't buy you a lot of type safety because you still get this like you get none in the fault case. So just I in practice like tactically use, custom, yeah.

B

But yes, it depends on many things here: yeah.

A

But you can totally make life more type, most strongly typed visitor, where you have to under write each expression or something like that. It's probably like actually not too important, because the bulk of analysis does not actually operate on this syntax tree indirectly. This is X 3 and this you're getting to more lower level visitation which we'll talk about shortly. Well, not show me one talk about it. Ok, so are there any questions about this high level API, because we are going to dive into implementation right now,.

A

Okay, so let's.

A

Let's dive into implementation well, first bit is what I've already shown you is that each index node is actually a wrapper around a rose index node, and this actually is all generated from.

A

This data file in your own format, so it's like just an interesting detail, run.

B

Being thrust object, notation.

A

Notation just examine on format, and it's actually kind of pretty big files like 5,000 lines of syntax nodes, I'm glad I have not right, it's the hands. Okay, so the implementation of the national data structure lives in the raw and crate and here's actual source code of their own crate.

A

The representation is to learn. It contains many purely functional, so-called green tree, which does not store offset or parent pointers, and it contains lazy layer of syntax, node or red nodes which contains parent pointers and absolute offsets, but is lightly populated. So, let's start with the green node, it's not too interesting. Basically, a green node is either a token which has text and syntax kind. This chicken kind is what was super sky and rust analyzed, because this liner is certain generic sperm tries on this parameter.

A

It also can be a branch and because this green node should be cheap navigable. We are using art here, so you can imagine like you, can substitute a single child in some node, and this will clone only some of nodes and nautical tree. So the branch contains the total length, which is a sum of length of children. It also contains a current and it contains an array of children. The Spectre presentation actually uses a cool trick with ll the trailing objects here in Swift. This basically is a single allocation.

A

It's dynamically size type where children asked or just after we know that cell. So there is no implementation and implementation of this trick yet, but it could be probably edit once we had user defined. Is this so just be usual? You've usable syntax, tree, nothing interesting here: do we have methods to replace no I, wonder well other methods for replacement, but the promotion somewhere.

B

Just to restate I think this is where you said: the green tree kind of is the underlying tree. It only has information and downward right like about its children, so that they can be relocated and if incremental reports, without yes,.

A

Be relocated, it can also be shared about line between different file level twist, so this is actually implemented, but you can imagine that if you have the same one plus one in two places in the index three, you can actually use the same green node for both instances of one plus one. In other words, green node nodes do not have identity.

B

A

The syntax nodes have identity, and here we are getting to this bit unsafe code, which allows you for three are thing. So that's not it tours a reference to a green node.

A

It also stores a reference to parents and stores a reference to the root of extreme, and the idea is that all simple are owned by the root of a dream. So when the room goes away, all steps nodes go away, and we must make sure that, as long as we have a reference list index node, the root itself is always alive.

A

The root itself is not aspects node, it's just some special data structure which contains which owns the nose itself and here I use the arena's, optimization Wednesday, not a really crucial bit of the implementation, and it also contains an arbitrary data structure which you can associate with into itself in rust. Analyzer I store syntax errors like the actual messages in these route data field, but I actually now think that probably this is a bad design and they should be inspected, or else would probably be stored completely separate from the tool itself.

A

Like parsing process should produced at Paris index three and a set of errors. That's probably not important, okay, so yeah. The interesting bit here is, of course, laziness, and this is the chief, the this amazing out data structure. So these lazy, node.

A

Is sort of an odd tear until you looked at it and when you looked into this place you know we actually allocate, and you see the X node set up its parent doing notice it's route cetera. This happens. We get child map. So if we want to get a child of index nodes, we look at this lazy node and if it's nice to know it already exists, we just return it.

A

Otherwise, we take the green child with the appropriate index and allocate a new child node and use index node child, and here we can actually see parent pointer, the start offset and all these other information which does not work with incremental repairs.

A

Okay, so it's lazy, node is based on swap cell, which kind of lazy cell, which has some unsafe, coordinate ability so that you can get either get value or initialize it with some much and the business is. How do you actually maintain this invariant that, as long as you have a sip X node, you have root of its we alive as well. There is where these three hours pipe comes in, so our three arc is a type which stores a reference to a single node inside the tree.

A

So this inner is a pointer to the node inside the street, not to the root, but it also makes sure that.

A

When you create a tree, art would actually bumps the arc pointer. Let me show this one yeah, so here, if we get have a reference to a node inside the tree, we can wrap this node into an ownership business. We are and to do that, we manually bound the pointer to the tree itself and then we create a trigger elantra. Conversely, in drop we decrement the counter, and this could potentially drop the whole tree.

A

Yeah so like the.

A

Initial reference count of one we get in the new route method, where we get a doing a green note, which is like fully immutable, blah blah blah note. We get these arbitrary, you specify data, it's very pointer and we get a syntax note for these route.

A

So we first create a route we put it into an arc pointer, so we get reference count one and we create three arc manually without bumping art the second time pointing to this red node instead, and we also use some it ability to yeah to actually set up a parent pointer because.

A

Why do we need point here yeah, because we need parent pointer to the root, because when we are allocating new child, we have to yeah whatever allocation children, or we have to ask the arena at the root to allocate the list of children so thing they're a bit of details here like why do we throw with text unit in swap Selma? It probably not important in general idea. Hope is clear at this point: yeah any.

B

A

B

Slight question in the arena: first of all, like in this implementation, I guess the so for allocating the memory for the trees from an arena or a partial like mix partly from the arena and partly from the heap like the arcs, are kind of on the heap. I guess so.

A

Green nodes are always allocated on the heap, and this next node are allocated on the arena because for green nodes, I want the ability to take a subtree and drop us to the tree. For this note, I have to maintain the whole tree anyway, because I want PowerPoint just to work, so make sense to locate them on the arena. When.

B

When there's an incremental update, do you also do you trash the entire syntax note later, because.

A

You know yeah for incremental updates the entire syntax, not layer is trashed, and this, like this separation, can actually be o4n like you can trust the whole syntax file, but because to create this cross lyrics file, you have to traverse it just that, like average, to constant update, nevertheless like, for example, if user type something- and you have inspected only the particular function to like do Sonic's, coloring and then user type, something else you don't have the false in text to layer in memory.

A

You have this next to layer only for this particular function, so it's cheap to donate I'm like I'm, not entirely sure about all this complexity is actually required, because this incremental parsing is not a measuring scale. Because, technically you read files once and they are never.

B

A

Only small amount of files are modified and for that files, like even from scratch from scratch, a parson is not too costly but wasn't too difficult to implement and well. Why not? And another thing is that I've talked about when I talk about Adams I was talking about. You can't do nested atom-smashing, but you can change the presentation of the tree and this is actually the place where we can take advantage of that.

A

We can imagine a second presentation of the implementation where you allocate above the green nodes and the next node in the single arena, and maybe not than my green notes and six notes, but some kind of a foot kind of like yellow node, which is like eagerly computed blah blah blah now and you can the iced tea layer does not the IP of ice layer does not expose these underlying details right.

B

You might do that for like create soil content or something that you know will not be edited later.

A

B

So well, I have a few questions, but I'm wondering um before I ask them, because I think they might be better to leave til the end. Are you planning to present also other things built on top of this I remember. We talked, for example, about like this higher level view on rust code yeah.

A

Oh, we are almost out of time well time.

B

A

Okay, let me just briefly talk about the parson and tri-level stuff and maybe leave the questions to the tiger.

B

And I think it's better I think I'd be happy to ask the questions you know and zuly also, if it comes to it, yeah.

A

So about parsley.

A

Like the cool thing about parsley is that actually it is independent from the index 3, so the syntax to itself lives in erasing back straight and parcel depends basically on nothing and it communicates with the rest of the analyzer, using basically these two traits for rare token source and twisting, and this kind of works nice with some type 3 presentation, because three Scene is sometimes it says what like I, have started this kind of syntax tree and not like a struct with this field or blah blah blah blah.

A

So it kind of works together nicely and parsing is not lis too interesting. Let me just we show how our calorie works.

A

Do we have? Oh it's nominal here so here we see a crowd, parson, struct definition, and first thing is that we have actually allowed struct to miss the name and strategy we use here. Is that if you are trying to parse the name- and we see a token from this set, we don't actually consume the next column. So if we deftly start something and event rule so we see here that the function syntax node is presented completely correctly because often struck.

A

We haven't consumed this append token, but if except translated like 92 winter, currently is 92 as an error node. So it is basically some heuristic to understand when we should see that token is mistyped or when the token is actually part of the next next time and another treat for our recovery is that when we are parsing list of things, we basically just ignore all the errors and just skip tokens until we actually see the close brace.

A

So it allows us to otherwise errors, and it does not matter what garbage I'll go into type here, the syntax tree, and then we left in light one.

B

Questionnaire about that yeah I've thought about that strategy. A lot it seems obvious, but if you're missing a closing brace, you could go very wrong right. Do you have some trick to like recover like if you encounter I, don't know what looks like a new item.

A

No, no, basically, you see yeah, but when I am I didn't before some bracelet, it's my light starts to morning when I erase it like everything Briggs but with proper methods. It shouldn't be too important practice because the analysis, time for a file should be like under a second under 13 300, milliseconds, Jelena I. Think like.

B

The the syntax highlighting actually provides a nice feedback for the user that, like PS I, didn't recognize this correctly yeah.

A

Like instantly for person ever since, like kind of a nice user experience right, so let's see how we actually use parse them to do some analysis.

A

Yeah, so the trick is that we not actually using these tweets for analysis would be bad because twist or absolute, offsets and absolute, I destroyed by every edit. So if you use this node as a saw ck, you have to compute everything, etc.

A

So when we want to do something in the tree, we go the lowering process, for example, to type check function. We lower a function syntax to this bad representation which contains expressions, but in this like yes, yes, I'll presentation, and here the expression is like actual an actual atom and it does not contain optional steps. Only each expression like if expression, has condition and has a vent branch, and they are not options. But we allow special mission expression to express expressions mission.

A

Some talk about my English yeah and.

A

A

Basically, a function which takes a syntax and I, see PowerPoint, etcetera, etcetera and converts it to these anon based representation and just recursively. What's the tree and allocates top on this idea, Rena, etc, etc. And what line is that? Because this representation does not contain offset super employers or stuff like that? It is not. It doesn't change when you type something before action, so it is not validated, and it probably also is more memory efficient because we don't store whitespace.

A

Yes, so we can take a syntax tree for a file, convert all functions to this presentation, and then we can throw away this in that stream and probably recreate the syntax to relate when they actually need them and to maintain the mapping between misrepresentation, syntax tree. We used so-called source map pattern where basically stole a hash map between these expressions and the syntax nodes in the original source tree.

A

Although we don't stole the literal CX node, because we want to be able to free the memory- and if you stop is next node, we store our pointer to the root of the trees with two basically and offset and a kind of a syntax. Now so we went actually but node. We can create it by parsing the source again and walking between finding the offset yeah. So that's, basically everything I wanted to cover.

B

So this last first of all today, we also have any other questions Frank, but ok, the last the last point of the design kind of gets out. What I wanted to ask about, which was none of the incremental story, and it feels to me like hmm it's kind of a minor point in some sense, but it feels like the the intermediate node, which has to be rebuilt, actually contains a lot more information than I suspect. You need a lot of the time in the form of absolute offsets and so forth.

B

You need you need some way to get an absolute offset, but it may not have to be like in the tree and I know their computer lays like. So maybe it doesn't matter because you throw away the whole syntax tree, but uh I don't know baby. This isn't a specific question and I should try to write down a proposal or something, but it feels to me like we could tune this essentially for first also like style, to get better incremental, be used across compilations.

B

But well let me come back. Let me forget that point for one second and dial back to the single biggest question I had, which was one which is related, which is that one part of your syntax tree had the premise that you can sort of get from any node in this index tree to any other node and that's not.

B

It seems to be obviously desirable, in fact, I think it has sense to nights and downsides, like you might want to, and specifically around incremental basically, and what we might want to do instead is to make it so that it's more like a tree of trees or a forest or something the idea being that when I get the tree say for a particular item like a function in our struct. Yes, I can navigate within that item freely.

B

But if I want to exit the item, I have to go back to to the API, to some extent I and the reason for that being that, then we can track more closely, which parts of the tree that you actually look at. So when we do an incremental update, we might see like indeed this imple, like you, never even looked at that impulse, little carrots that had changed her this function so on, and maybe that that kind of all comes out.

B

I guess through the expression I can later layers in this also mapping kind of achieved that same effect, but it might be something we want to think about pushing earlier. I think.

A

Yeah, probably my current thought is that these bodies mix patent representation gets you exactly bet, you can inspect the body, but you can't look outside of it and you have to have salsa database somewhere get the owner of this body and I think. The idea is that, like this syntax tree, contains a special presentation as possible to make the writing IDE work migratory patterns as convenient as possible, but that we are always eager to discard it.

A

In generally, we should like build a syntax tree for a single file and then this carbon and Gillis industry for the next file. This probably won't walk with matter expansion, but probably if I could to some extent but I, don't think that probably we can tweak this and move incremental beats closer to actual bars, yeah.

B

I guess it seems okay, it just seems like a little baked in inefficiency. That is not obviously necessary or more.

A

Even that much more.

B

Convenient like we might instead say that we, you know you have all that information that you have to sort of ask for it, so that we don't it's kind of in some sense, maybe moving some of that lazy, rebuilding out from the unsafe code and into salsa yeah.

A

I'd like to kind of show a bit of code where I think this, like ability to navigate to parse it. Some ships are easily especially important. So this is a deed of completion infrastructure and the task of the beach is figuring out. What we identifier at the position actually is about, and so here we basically get estimate like hey. We have an identified, but let's look at the parent, and if this is is, if this happens to be a named field, then we are inside of like struct.

A

It's wrong like this thing, which type inside expression. Otherwise, let's take a look at the ancestors and see here if we are at the top level in some sense or if we're inside a function best of stuff. So this like I, definitely feel that the day I was throwing in the Inca. Walkthrough is a useful model to the IDE, because it's simple you just get parents, children, cetera et cetera the implementation, totally change, and it wouldn't be too bad.

A

If all of these functions will have to get the data base argument or something but would make it less nice- and it actually would make these like less constrained, because if you have a reference to salsa database, you can get anywhere in the types in the matter of the setter etcetera. She s image 3 is pretty much isolated from salsa, so there's 0 semantic information missing between this kind of variable as well could be variable as well.

B

Yeah, that makes sense thanks, I, particularly.

B

Another question: what built atop this, like I, assume you don't have like some take on rust format or anything like that, because that would be incredible, but.

B

I'm, basically trying to figure out how much have it would be interesting to see sort of examples where it was. You know, each of the case of capabilities was used. What for.

A

Head I have a certain like where, for examples like, for example, one nice feature is that if I call giant Lions function in rust in Eliza, it like actually removes these trailing comma. For me because workshops, industries.

A

A

Yeah- and here we actually use this capability of getting to the previous sibling and checking that this is a comma and the next node is a closing brace. Let's just remove this coma yep I.

A

Want to build rust from the tree on top of these three, so it's like this is actually why I am interested in nailing down. This particular aspect of rust analyzing, some oddity here, because if we are final about the design of a syntax tree, we can actually start building in stuff on top of this, and we can start thinking about like how do we move recedes when you use these trees or something like that, it.

B

Sounds like somewhat.

A

Isolated from my heart, heart beats like name resolution on macro expansion like.

B

That, yes, foundational.

A

Of course, the biggest question here is: how do we do micro expansion using these trees? I have like some some draft. What here wish I can actually take a talking tree and produce a nice team note without actually going via text representation, because I have this like twisting token source version for parsing, but doesn't, for example, handle hygiene well like. In this token representation each target has an identity, but in this source tree because it only remembers tokens way.

A

Like the text of the token I can't say that this name instruct came from this talk and it somehow has to be implemented elsewhere.

B

hmm I, don't quite understand why you can't do that because.

B

You don't have a way that sort of splice the tokens to indicate that they came from another. They were spliced and from somewhere else.

A

What I'm trying to say is that syntax tree currently does not contain any semantic information and hygiene. Isn't some cells, not information? We can either build hygiene into the tree itself or we can maintain an side table and I'm currently leading towards maintaining a side table for that, but that needs to be implemented in.

B

General there's like it's not just about hygiene, I mean generally the spins in rusty at least have a sort of extry them right, like a stack structure so that we can say things like we. We use this internally to say things like we do sugar the for loop into a while loop. But when you see this while loop, like it's compiler generated from this original source, do you have any notion of the left handling that kind of information? Would that also be a side table? I? Guess yes,.

A

So it's actually on the tree. It's like called a token map and like it's not really works, just some dropped code, but the idea is that each token has an identity, basically integer and we can, for example, map each token in the token tree to the source span, where this token came from and kind of maintain that back but I don't have the general hand, notion and I probably would like to avoid spicy, because it seems to me that spans don't work quite well with incremental compilation.

A

Idly kind of I will try it through my Intel and we'll find great babies like expression. Id function, ie, something like that, but for macro expansion here we need some kind of a more general martin between tokens. Okay,.

B

This was super helpful. Thank you. Relax yeah.

A

Yeah I, probably like it probably shouldn't be on video, that this is really based on the implementation of the Swift and Swift. Has a really wait with me: explain in this red green stop! So if you don't understand anything I was talking about, it makes sense to read that first and then watch the video. Unfortunately, it will be made of video, so yeah.

B

Cool, oh sorry, cut.

A

B

Thanks everyone.