Rust Programming Language FOSDEM Rust Devroom 2018, 6 Feb 2018

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Nikita Baksalyar - Demystifying Rust Parsing

Description

Language parsing and automatic binding generation

Usually, the topic of parsing the Rust source code is associated with the Rust compiler itself, which for many is an uncharted territory. However, parsing by itself can (and should) be used out of the context of the Rust compiler: given the wealth of information that we can extract out of the code, we can do a lot of thing with it.

In this talk, we'll discuss several interesting applications for the Rust parser and the abstract syntax trees it produces, with practical examples of Mozilla bindgen (automatic generation of Rust library bindings based on C source code) and a Java binding generator written by the author for a large-scale open source library.

Some prior basic knowledge of compilers and parsing is expected.

The intended audience is Rust developers who want to learn more about the internal implementation of the Rust compiler and to practically apply this knowledge in their projects.

Nikita is a Mozilla Tech Speaker and a Rust engineer at MaidSafe, developing an open source peer-to-peer network technology and contributing to other open-source projects, including the Rust compiler. He's enthusiastic about the Rust programming language, also interested in low-level development, P2P networks, and alternative operating systems (like e.g. BSD/Illumos).

Rust devroom @ FOSDEM 2018
https://fosdem.org/2018/schedule/event/rust_demystifying_parsing/

These talks have been recorded at FOSDEM (https://fosdem.org/)
This work is licensed under the Creative Commons Attribution 2.0 Belgium Licence.
To view a copy of this licence, visit http://creativecommons.org/licenses/by/2.0/be/deed.en

A

B

A

B

Hey thanks a lot and first let me introduce myself and before that. Let me say that it's always great to see so many people in this room, people who are interested in rust and the language itself has started about two years ago, less than a little bit more than two years ago, and there will were maybe a couple of hundreds of people who were interested in that language and now it's really great to see that is getting traction and see a lot of people in this room who are interested in this topic.

B

So introducing myself, my name is Nikita I work at made safe and might safe is a company that develops peer-to-peer network technology and I think we have one of the largest code bases that are written in rust. So today, I want to share or share my experience, developing one of the comprise one of the libraries that comprise our stack and they want to talk to you about parsing.

B

So Parsi is one of the crucial steps in the company in the topic of compilers and the compilers is a a complex topic by itself. So it's it will be. Almost impossible to cover all the things that go into compilers in 20 minutes, so this will be more like more of an observant talk, so I will cover the basics and my goal here.

B

My goal today is not to give you the entirety of information about compilers, but to inspire you and basically to pique your interest and actually compilers is a complex topic and a lot of people are scared, but it they opened the Dragon book. They see that it consists of more than thousand pages and they close the book and never read it again. But actually compilers are very interesting topic and if you take one part of it, they can be immensely useful and they're. Not that complex.

B

So, let's start from the basics, so how how parsing can be useful for you, so what is actually parsing? So if you don't know it is one of the steps in the compiler. You know which allows you to extract meta information about your code, so you can actually imagine the compiler as a kind of a pipeline that consists of several steps, and the first step in the compiler is the lexical parsing or the excuse me, the lexical analysis.

B

The lexical analysis is a simplest step that gets your code in its text representation and transforms it to a set of tokens. A token is a very simple thing and can be thought of as a word. It can be a keyword. It can be a string out of your code. It can be a number, it can be. Basically anything the return return is a curl is a token. A fan is a token, but have a just jokin x'. We can't do many useful things with them right.

B

We can do many useful things with just code as text. So what we do here is we put tokens in a token in token, trees and out of those token trees we create out of those token trees. We create a data structure, that's that is called abstract, syntax tree or SD for shirt.

B

Hd allows us to extract meta information out of our codes and use this information to do basically anything.

B

So how do we apply? Is these for our practical gold? You might think that HDS are usable only for the rats compiler itself or for now building some I, don't know some utilities or things that belong to the Ross compiler, but actually these have many everyday applications.

B

So you can extract metal information from your code and based on that information, you can generate code in other languages. This is very useful if you want to, for example, if you deal with F of Phi or a foreign function interface- and you want to create a library in rust that you want to be make usable from other languages, and it will be very tedious and complicated to write this code in other languages to work with your rough library. That's why we have a steez.

B

You can basically scan all of your libraries code and extract that information about the functions that you export from your library and generate code in other languages based on that extracted information, and you can also transform your code. It's perfect Chloe. Now, when you want to apply some kind of refactoring to your code and I believe the next talk will will be on this topic. So, for example, you have Clippy that shows you many compile errors in your rusts code and it's not.

B

It is very useful, but it will be very nice if it could do automatic transformation. How automatic refactoring of your code right so that what you can do with ASD with HD. You have full information about your code and you can also generate new code out of a steez. So basically, what you do here is you you're, taking the code of your library and you're generating new code based on based on that code and as an output?

B

You have a refactoring code and there is also the meta programming aspect, as basically you're related to macros and macros are very similar to how a Steve's or so mockers basically employed the HD framework that you have in your compiler, but the macros are accessible to only within the scope of the compiler and with a ste. You have the full information about your code. So basically that means that, with meta programming, you can generate any rust code based on the full information that you have extracted from the ast.

B

And of course you can use is to compile your code to a binary, but thankfully you rusts the Ross compiler. Does that part for us and of course you need to know that the use cases are not limited to those that were listed on the previous slide. There is a lot of. There is a lot more use cases and they are basically limited only by your imagination,.

B

But a person is these by themselves, are pretty abstract concept. How do we actually apply them to rust, because this is talked about the rust language right and, in fact, rust? Library's, multiple, rust libraries already apply that concept and we use these tools every day and rust. F&Amp;G is also another great example of code transformation, because what it does is basically takes the HD that it has extracted from the source code and outputs this iced tea with with a formatting that follows the presets preset rules about the.

B

How indentation should work, how to put it, how to put the brackets, where to put the brackets and so on and clip is a similar beast. So it extracts the meta information from a ste and based on that instructed extracted information. It checks whether your code has any bad patterns in it and suggests how to fix those bad patterns, and there is no magic in it.

B

You can basically write your own clip a based on the compiler technologies and, finally, if you use IDs or text editors with with the eraser plugin installed, you are also using SDS. Is these extract information from your code and you have killed completion, syntax, highlighting all the nice things that IDs provide you. So IDE is basically a compiler that compiler that extracts information from your code and makes it more usable and convenient for you to write your code in the users interface.

B

So how do we actually use these a steez? And of course you don't have to write your own library or you don't have to write your own code to extract this information or parser code into HTS. You have you, have it already in the Rath compiler and you can use the lip syntax. That is an integral part of the compiler to basically extract this information and use it in your code.

B

There is a caveat, though: that's lip, syntax library is available only in Nigel in the Nidal version of compiler and brass use it to parser code, and it provides a teaser basically in as an API. But if you can't use the nightly version of the compiler, the an alternative version will be syntax. That is a grade that has been ported from the lips index.

B

To a separate grade is basically a code that has been taken from the Russ compiler and put into a crate that can work on a stable branch of the Russ compiler, and it's it has the exact same API. So you can basically use it interchangeably in your library, if you want to, if you are not allowed to use an idle version of compiler, you can basically just link this this little library and it's a drop-in replacement, but there's another kavia in that this library has been deprecated and its usage mostly confined to legacy projects.

B

Well, you can still use it. It's still available on the grades, dot IO repository, but there is also an alternative and, if you're starting a new version of your basically, if you're starting from scratch and not from some kind of legacy code, you can use an alternative library, that's called as sin sy n and it is used by multiple projects too, and this syntax crate is used by rust affinity stable. So it's basically a matter of preference, although the authors of for this library that I would prefer you to not use it.

B

So how do you actually to put it in practical terms? How do you actually use that you basically import the syntax, which is a part of the russ compiler as a crate? You add this separate mmm kicker flag. That says that it's a lot to import private parts of the rust compiler and you basically import it and use it as a as a usual library.

B

So then, you provide a file name of a rust file that you want to parse and other, and as a result, you get a vector of items.

B

So items are actually e noms that represent all that you can use in your code, so it represents functions with their arguments. It represents statements. It represents all the expressions that you have in her code.

B

It's a nice thing about it is that it's an enum and, as you know, we have a very nice language construct in rust that works with enums there's called match and by using pattern matching it's very simple.

B

It's very easy to actually extract the information from those items you basically match on the type of your AC item, which could also call carry the all the relevant information with it in its anon variant and you use it. However, you like.

B

So that's how it could look yeah. It could be a function declaration which has its inputs, its arguments with together with its types, and it has also an output type.

B

So it goes on like that with other kinds of items with other kinds of STS. So it's not a rocket science, so you basically can continue in the same manner. And finally, you know there is a cogeneration aspect, so cogeneration has a lots and lots of useful and practical applications.

B

So if for, for example, when Mozilla started to develop servo, they stumbled upon an issue that there is many libraries that are not written in rust, yet so to use these libraries that are written in C and C++, they got together with a library, read sculptress banking. So what it does?

B

Basically, it uses si Lang to extract the meta information from C++ code, so basically can think about it, as as an analogy of that lip syntax from the Russ compiler, but it works for C++, so will extracts the meta information from the C++ code and Jerry's code in rust. So that that way you get a library that can talk to a single class library. But you don't need to write it by hand, which will be, of course, very tedious and error-prone.

B

So then there is a civilization aspect, so if you work with proto, buffs or ro or other frameworks that work with other languages, they basically follow the same pattern. They have a description of data structures that you might need to use in different languages and they basically use code generation to provide this feature and in rust you can do the same and I believe there is already a bunch of libraries that provide this thing for you. But if you want to make a similar thing, you can use code generation as well.

B

And finally, why why do we use HTS? Why do we use parsing, instead of instead of just going by macros well of first of all, macros don't have an access to you, the environment that you know run your program in so micros are kind of isolated by the compiler context, but they can't access the input out. They can't read a file from your file system.

B

They can't go to the network and so on and with and with parsing, by parsing your code, you can basically have and have a the all the power that rust, the rust compiler and the rust language, provide you, and, and not only the rust language and the the full power of your environment, and the second aspect of it is that macros 2.0 that should be available in the wrath compiler soon should cover at least a part of these use cases. So you might want to follow this closely.

B

And finally, how do you actually generate your code? huh You can use a tool that utilizes the Builder pattern. They basically call functions so to construct a function. You will call item of fun and provide the context of that function.

B

You provide the function name, you provide the function arguments and you provide the function body and, as a result, you will get the HT item that will contain on all the relevant information for your function and from that HT item you can convert it into into a string and get the rescue as a result, but it's not very convenient so whoever can use.

B

Instead, we can employ the concept that is called quasi, quasi quotation and it is widely known and widely used in the Lisp language and it's widely used by some functional languages like Haskell, for example, and the concept is quite simple: it's server resembling of macros, but actually, instead of you know, instead of outputting just string, it provides you with tokens and the HD items that you can use further.

B

So there is also a Russ library that that's called code that provides a bunch of handy markers that you can use to generate your code.

B

It looks like this, as you can see, it's almost the same as you would have written it if you have dealt with macros, so you can just create in your identifier and place it in your code instead of placeholder and as a result and as a result, if you convert it into a string, you will get a resulting function, a resulting source code and you can output it into a file or do whatever you'd, like with it and finally, a small case, a small case study about how can you use parsing in your project, so it made safe, we dealt with.

B

Our task will was to provide a library to be used in basically in multiple languages. We have a library that talks to a p2p network, a peer-to-peer network, and we want people to use it from basically any language that exists, and we provide this library as an fi interface. So it exports a foreign function interface and it's available as a C library as any other C library, but as we want it to be used by as we want it to be used by Java scripts or from Python and from Java and from other languages.

B

We and it's a very tedious process to just write that code by hand to write the language bindings code by hand. We came up with that solution of parsing, basically parsing our entire library and export on looking at the exported f5 functions and create generating Java and c-sharp and Python code. Based on that and besides that now Java wouldn't work simple with that code, so we also generate Jane I bindings in rust.

B

So we generate rust code that exports Jane I functions that Java understand and that the entire code of that libraries ik is generated by basically as a result of code generator and the parser.

B

So that's it, and if you have any questions, please ask.

B

A

Library and I want to replace.

A

B

The question is: can you use basically, can you transform a STIs in the compiled time? So when you're compiling your library, can you transform the ast to have some other representation and, of course it is possible when you do it's with macros, basically that what micros does they take the ast three and they produce another ast tree so mmm that is sold by macros and also there is a procedural macros thing and there is also macros 2.0.

B

So Russ provides multiple ways to transform your code to some other representation and you can choose whatever suits you better.

B

So the question is: can you basically do a mock testing and rust by replacing structures with some other version, with versions with instrumentation and test functions now and so on and yeah I believe it's possible if you use the compiler plugins and the procedural markers and if you use the derived key in keyword that what it basically does and that's also how serda how the serger library works. It derives your structs, so you just write, derive our allies and the rest.

B

The surgery library takes that instruction and generates the serialization and deserialization codes for your structure. So I believe that so I can work in a very similar way for the mock testing and the mock features of so for the mock version of your structs. Any other questions.

B

Yes, so the question is: is: is there a project in rust that that is a basically compiler generator that takes a description of a compiler and generates a compiler from from the BNF grammar or whatever it's called yeah there is?

B

There is a bunch of such projects, I believe for one is called Lal earth and it is based, obviously, on all our parsing, so yeah, there are there's a multiple projects and you can basically find them by googling Roz compiler generator, and there is a prominent once and activity that are being actively developed, so you can find many of them.

B

Okay, thanks all for your attention.