Rust Programming Language EuroRust 2022, 4 Nov 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Parsing Rust code considered harmful - Sasha Pourcelot - EuroRust 2022

Description

Sasha Pourcelot
CS Student, Software Engineer at Trustinsoft

Sasha discusses the different static analysis techniques that were used in the development of cargo-breaking.

We’ll start with basic Rust code parsers and show that, although being super simple, they require complex manipulations when it comes to import resolution and dependency handling.

Then we’ll use the Rust compiler as a library and dive deep in its internal API. While this approach allows us to capture all the subtilities of a Rust crate, we’ll show that it requires just too much maintenance and involves a huge complexity, potentially slowing down the development.

Once this is done, we’ll discuss how we can leverage rustdoc in order to extract the API of the crate and get a lot of super useful metadata in the process. This approach allowed us to do great process in the cargo-breaking development, as it allowed us to get all the data we needed while not being too complex to analyze.

At the end of the talk, we’ll allow ourselves to dream of the future. We could maybe add a plugin system to rust-analyzer and perform custom analysis in real time, so the diagnosis can be provided to the user after each key press.

A

A

So my talk is named like you can see it. Of course, parsing rest code considered a harmful. My goal is to show the different ways that allow a restoration to perform static analysis of rest code. I won't show go into the actual algorithms, because I'm bad at algorithms um I will show all the different tools available in the rust Community can be used and leveraged in order to make static analysis easy so um I'm, Sasha personal as it can be said, uh my pronouns are she and her?

A

um And basically you can ping me everywhere on the handle scripture I'm, a computer science student at Polytechnic Sofia, which is a French school and nothing much to say, I will graduate in September, which is so great I can't wait um when I'm not studying I'm working as a software engineer in a French company whose name is trestonsoft.

A

um Basically, my role is to build a posix compliant implementation of the file system, manipulation functions which we can use later for static analysis. Our goal is to be able to find every possible source of undefined behavior in a c program, and this is the most awesome jump ever anyway.

A

um So uh and I also have done a few contributions to the rest ecosystems, including so the compiler itself. I did various pull, requests and I also worked in the Tremor project in in the spring.

A

So, let's start with the basic static analysis. The whole point of static analysis is finding a property. It can be literally anything you, like literally anything, about a program, but without um actually running it, and this is where the magic happens. You are not allowed to run something. You can't just look at the code and reduce properties.

A

The most simple example, which we all know is type checking, which means that you are looking at the program and basically finding potential potential type errors before compiling the program so that they just can't happen at runtime.

A

um You also have that cut path, detection, which is a lint which is quite quite common in Rust. uh There are, there are also so basically every kind of lens, such as unused variant or attributes, and what I will talk about today, mostly breaking change, detection.

A

um So, basically, this world talk will be about how I developed the project cargo breaking from last summer up to this summer, um so cargo braking is a tool which aims to flag potential sources of breaking change in a restraint.

A

um The goal is to flag a breaking change before a release. Release happens so that we don't have to break code on the library user side.

A

The end goal was to embed it in CI, so that a ripple request that is opened by a roostation immediately gets checked against breaking changes which would be great and the role for every every the world Community could benefit it by getting more insurance. That updating a crate like running cargo update is just safe and cannot fail in any way.

A

So there are a lot of sources of breaking change. The easiest one which I showed here is to flag differences in the public API, for instance, here I added a specific mood parameter, um which basically makes previous calls to the function, Knight name just invalid, because you can't run a function which has two arguments. If you only give it one argument: So In, This, Very, concrete example, Knight name has a new parameter. It is a breaking change, so it must result in proper semantic versioning upgrade.

A

This is not always that easy.

A

Basically, there are so much ways in making um there are so much ways to make a breaking change, which is almost a noticeable, for instance, adding a second as rev implementation to a trade to a type can basically destroy everything, because the trade method resolution works well, when there's one candidate and it just it just fails when there are one more than one candidate.

A

Also, we have a way for now now to add custom variants to nms thanks to the non-exhaustive attributes. We also can add field pills to structs, which is very great, and this is something which we must take into account when dealing with breaking changes.

A

um It's also kind of easy to accidentally remove the sand and sink traits of a type by by adding feeding um like a member or something which is not itself sand or sink and which is even more weird changing the size of a type.

A

If you are doing some extra magic could trigger um breaking changes, especially if you are trying to run transmute on it, because changing the size make transmit just stop working and I spent a lot of time figuring out various ways to just by your various reasons, for a program for a library to break so I'm. Sorry, this is the crime we are all doing. Today.

A

We are not going going to deal with anything stubble stable. We will try to make to use stable tools, but it is mostly likely to stay unstable for a while. There are some discussions of from people who are very interested in making all the tools I'm talking about stable, but it's not something available for now, um the in the worst case, we can still use the rest table, strap environment variable which allows us to cheat and use nightly features when not actually running lightly. It is a crime, it is a crime.

A

We are all willing to commit today. So when dealing with breaking changes, we have to find informations about the crates. What are the functions? What are the I, the the trades? What are the types which are defined? All these things are called the items. This is the official name of anything you can find in a module.

A

So how do we get information about a crate? My first approach approach was to just use a very simple parser. So basically, it was about I, wanted to read a file and just give its content, so a string to a parser which gives me a very nice syntax tree about. What's in it, and perhaps we may figure out a way to actually perform analysis on it, so I needed a parser which was able to parse the whole rest syntax, and actually this is the moment. I discovered the scene.

A

Crate sin is a treasure on its own. I could learn like I could give three different talks about Sin. It has so much nice properties which are clearly undervalued, anyways. So thinking pars a string and gives you give you a syntax trick responding to it, and this is like perhaps the easiest way to get the syntax tree of a rust crate, because it's literally pulling a dependency which is already here, because scene is heavier everywhere and it just works, which is incredible.

A

But this approach is not perfect because you cannot handle macros. It would mean that you, you can't like fingering up figuring out a way to expand. Micros on our own is just too complex. We, this is just too much work, so a solution. A way to avoid this issue is instead to run cargo, expand, get this, get it out its output and just feed it into scenes so that we have a prop macro, expanded code.

A

This is supposed to be another crime, because um we have a very useful mechanism in Rust which prevents variables defined in micros to be referenced from the outside in this way or the other, which is called hygiene.

A

um So this is supposed to be a crime, but luckily, for us, hygiene doesn't apply at the item level. It only applies inside a function body, so we're all clear.

A

This solution is very stable, actually it's like if a new kind of syntax is ever added to rest, then I just have to bump a dependency literally just seen, update scene release a new version and it will work, especially. This is actually not even required, because sin has very nice fallback modes where you fit this. If it detects something it counts. Parse at the item level, then it will just stop and give the whole tokens that, as if it failed to parse actually and nothing can ever break break in this way.

A

The problem is that this cannot be that simple. For instance, we we are just dealing with tokens with it identifiers. While us it will be way more useful to have every import resolved, because this way we don't have to write a complex import resolver on our own. Similarly, there is no support for dependencies if I have an item in my API, for instance, in function, which returns something that comes from another crate, then from my perspective, just handling abstract, syntax, trees, I just don't know, I just don't know what it is.

A

I know it's a foreign type, something that doesn't come from my API, but I have no other information, and this is really really a pain point. When working that way, there are possible solutions. For instance, I could write my own password resolution. Algorithm I could download each dependency on my own and parse it directly from craze.io, but this is just way too complex, and this is a very bad idea, since this is not our job, our job is to take information and perform static.

A

Analysis figuring out dependencies and um Imports and path resolution is rest, C and cargo job, and we do not want to do the same. I try to do the same and it really hurts you do not want to do it, and this is why this wall talk is entitled. Parsing rust code is considered harmful. You don't want to just parse stress code. You want to do more than passing, so let's take our initial problem slide and add more requirements.

A

So we want to get information about the crates, but we do not want to rewrite a compiler and a dependency resolver. We want to be able to handle dependencies the easy way.

A

Let's try to to use the most simple approach, let's see as a library, so we want, we will try. The goal is to basically embed a custom version of resc in our executable and basically run as much of it of its code as possible, so that our um cargo braking contains only um basically what it should what's it should what it is supposed to contain so breaking change direction.

A

The idea like this fits in a wall slide. This is a world process of using rest c, as a library just add the nightly feature, and you suddenly have access to everything to the wall. Public API of the compiler, which is like easy, just just a custom feature to enable, and you suddenly have access to thousands of power of engineering I. Like this completely blew my mind.

A

This is something which is already used by other people, for instance um clippy. So the most common rest linter uses this technique um for the simple reason that, like Linton, lynching is actually static. Analysis performed in a specific way, so it makes sense to use similar method right handling dependencies is complex.

A

We need like when running the compiler. Even if it's in a library we need to tell it's a lot of information about where to find all the dependencies of the crates we are currently compiling.

A

My initial idea was to read the Manifest file and, like just do what cargo does so Computing a dependency graph, perform compilation of each crate separately and then then perform the final compiler. The final static analysis pass on the last crate, but this is once again too much work, and this is not the work we are supposed to do when doing static analysis. What we are supposed to do is to use cargo.

A

It turns out. Cargo has a super nice environment variable which is restive wrapper, which allows us to tell to Cargo that, instead of using resc to invoke any custom binary, so we could you could. We could tell it to invoke us instead, foreign. This works really well really. Well, because our only job is to know to guess if we are actually building a dependency or the final crate. If we are building a dependency, then we just pull back on the actual rest.

A

C perform the compilation and if we are compiling, if we are called for the very last invocation, the one where we are supposed to perform static analysis, then we can just perform static analysis, which is great.

A

It's also very easy to interact with Rusty when it's embedded as a library. Thus the trait whose name is callbacks- and this is the whole entry point of the compiler- it allows to alter to change the way to customize the way uh the library the compiler is called. Maybe you want to tweak the settings. For instance, you may want to change the name of the crate as it's seen by Rusty, because you want to perform internal crimes.

A

Let's say you, may you may also want to change the abstract industry that has been parsed I, don't know who wants it, but it's a it could be proved useful later and which is the most important part. It can also be used to perform Mir code analysis.

A

Basically, Mir is a way the crates code and its dependencies are represented in Rusty. At this step of the compilations, the compilation, everything has been resolved and we are almost guaranteed to have enough information so that we can perform all the static analysis we want rust. C is built using a very, not weird, not strange, but uncommon pattern when working um when writing rust code. Basically, it's a whole query engine. The thing is that compiling a rest program is kind of slow.

A

Everyone in the room agrees I'm pretty sure, so people wanted to make it complex. A simple way to make a complex program go faster, is to um to to ensure that no work is performed twice. This is the whole idea of this query engine.

A

Basically, when doing static analysis, this way you are interacting with a strict whose name is tyctxt, which represents a typed context, and this is the structure you are going to perform. Queries against this structure has a tremendous amount of method. It has about or 500 yeah, 500 methods and Counting, which is like incredible.

A

The problem with this approach, like we tried, really hard to flow that way, because it's the easiest way to get correct. It doesn't work it's just too much. You are constantly tied to Rusty. You can't even let data flow out of the Callback trades, which I shown which I showed earlier.

A

You also need to spend a lot of time, um understanding how the compiler is is written and how different prints interact with each other, which is like very complex. This is a learning curve which is even steeper than the learning curve of rest itself. In my opinion, about stability, this is not stable. This is the most unstable project. I've never worked with. Basically, the thing is that the rest, compiler developers don't want to spend time stabilizing or keeping like not breaking their own internal apis.

A

It makes sense they are focused on shipping and compiler, which is a very complex problem. They don't want to do any additional work and it makes sense, but the result of this is that your project is going to break every once in a while, because a developer somewhere decided to change the compiler internal.

A

So, let's update once again our slide.

A

We don't want to be this tight to the compiler. We want something clean. We want to get data from the compiler and not constantly querying query information about the compiler.

A

The most simple solution is to use res Dock and it kind of makes sense when looking at a like rust dock is already a tool. Will's goal is to extract the API of a crate, so it has almost all the code required to perform this extraction this extraction step.

A

The idea is that rosdoc has a custom flag whose name is output format, which allows us to tweak the way what what files it will generate. In The End by default. It generates a bunch of HTML pages, but we can tell it to just do a Json file, and this is great because a Json file is easy to understand and to reason with.

A

It has it outputs data in a specific format, using specific data structures defined in the compiler repository as restaurant restock Json types, and someone in the community is responsible for publishing, regularly the risk doc types traits which basically maps to these data types. It uses 30 internally, so you just have to give it all the the content of the Json file generated by restock, and it will do all its work on its own, which is perfect. We are freeing ourselves from the compiler right now.

A

There is just invocating rustdock reading the Json file, the serializing it and then only static analysis, which is awesome also eating. It integrates perfectly with with cargo, because you just can't run cargo rest, Dock and it cargo will figure out when to call Rusty went to call restock and you just have to read the final file, which is awesome.

A

This is not perfect, though it is limited to items. You cannot sparse the content of the body of a function body which means that your project. In order for this approach to work, your project must be focused only on the public API and not what inside functions, which may be a problem. Also, you only have informations about you about to create after macro are expanded, which may not be on the scope of your project. You may want to get actual pre-expension um to perform pre-expension analysis.

A

This method is more stable than Rusty, um but still not that stable, because the the type the data type outputed by Russ by rustdoc may change without notice, but luckily, for us, the the release process of restock types is almost automated, which means that fixing. It's is super easy, okay. So this, where all the approach approaches I had the opportunity to experiment with they have upsides and downsides.

A

For now, let's focus on something slightly different: let's see if we can embed all these like, let's see if we can imagine another approach which would fit instead of fitting in a CI script or something which we could run um basically when the program is being written so that we can link indirect it at each keystroke that something is happening.

A

Basically, in my opinion, the easiest way to do this would be to plug ourselves to rest analyzer, which is the most common language rest language, integration used When developing.

A

um We could, for instance, spin a separate process which would communicate with a rationalizer. It doesn't have to be fancy code, loading at runtime. We can just exchange a bunch of Json files. Just sorry Json messages and what's really interesting, is that westernizer and the other language Integrations are focused on performing as much computation as possible. This is the best way to give instant feedback when typing something you want. For instance, you type checking to work instantly instantly.

A

So all rest analyzer is crafted so that as little recomputations are are done.

A

um This means it has its own incremental and query based computation models, and basically, what it is doing is keeping track of the data required in order to compute another data and each time the source that I get changed changed. Then the every data which depends from it will get computed, which is awesome because all the static analysis we may perform wraps kind of well in this data flow and I need this in order to do that and very functional as in a per function.

A

So one way we could do that would be to be able to communicate with restaurant analyzer and telling it. What are the queries we want to perform and it will, for instance, build the same data dependency tree for our tool. This, and this way it would allow us to get to recompute to perform the static analysis only when required only on what we require and on and perform like. Do it almost instantly, which is what you want once again when you want to plug yourself in an ID okay. So that's the end of my talk.

A

Thank you. So much for listening.