Rust Programming Language RustConf 2022, 5 Sep 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: RustConf 2022 - Bootstrapping: The once and future compiler by Joshua Nelson

Description

"Bootstrapping" is the process of building a compiler written in its target language. Bootstrapping has been used since the development of ALGOL and LISP in the 1960s. In this talk, you'll learn the history of the bootstrapping the Rust compiler, how bootstrap works today, and some big ideas for bootstrap in the future. You'll also have a chance to get involved in working on bootstrap.

A

I think you know all right, so my talk is called bootstrapping and that's probably already raised a bunch of questions like what is bootstrapping and what does it have to do with compilers, and so I'm going to talk about what it is first before we dive too deep into it. uh So the rest compiler is written in rust, which leads to some strange and and interesting challenges, and because it's in rust, that means you have to compile it with an existing rest compiler.

A

So you need to compile it with itself like. How does this work? How? How do we compile the compiler with itself? Well, the way you do it is: you can use an older version of the compiler, so the some definitions, real quick, um the rest compiler is self-hosted, which means it's written in rest, the same language that it compiles and bootstrapping is the process of building it.

A

Okay right! So there's three parts of this talk, and the first part is how we want things to work, how how they should work, how we hope they work right. So when I say an older version, the rust compiler always uses the immediate previous version. So, for example, nightly is built with beta beta is booked by stable and stable is built by the previous stable, and it goes back in the chain one at a time, and you might ask why are we going one at a time like?

A

Wouldn't it be simpler, if we just like had one version of the rust compiler that we always used? Pin that in place and there we go, we never need to update it. Well, the problem with that is that we use unstable features in the compiler, but let's go ahead: let's, let's try it out and see what happens: we're going to build the current beta compiler 1.63 with the previous stable compiler. This is like only two versions back like how bad could it be right. It can't be that bad well oops.

A

So so, if you look at the error here, um it's telling us there's something called a language item that we need to know and it's called from eat and we don't know what from meat is- and this is like something in 1.62, not in 1.61 so like, even in that short amount of time, we're already running into errors um and because we depend on those unstable features in the compiler.

A

We can't use that older version, but like what does this mean right like what are language items like all this stuff? um So some some more definitions standard is the standard library. If you look at this error here, it's not actually pointing to the compiler. It's pointing to the standard library and what's going on here is the standard library depends on implementation, details of the compiler and one of those is language items.

A

So let's take an example here. This is the addition trait it's defined in core. It's how you do operator overloading and rust and for the most part, it's a normal trait. You have an output type that tells you the type of result. It has a function you implement. That tells the compiler how to calculate the result, and you can do it for any of your user defined types just like any other shape, but what makes it special is the little attribute at the top language equals add, and what that does.

A

Is it's a little bit of compiler internal magic? That says this trait corresponds to the addition operator, and we need this to make operator overloading work, so you can use a plus instead of a function, but it also means that we're, depending on implement implementation details of the compiler that can change in any release. We don't stabilize stuff like this, because you're not meant to use it unstable.

A

We want to be able to make breaking changes in case we find a better way or faster way or whatever to implement this, and there's lots of things like this. It's not just operator overloading the library depends on rust stock internals. So we can document primitives and keywords. We have intrinsics.

A

If you look at the error earlier, we have some intrinsic functions that were added in 1.62.

A

And other all sorts of other things, and because the standard library is so tied in with the compiler itself, you can almost think of it as part of the compiler. If we define this edition trait in any other way, if we remove the output type or if we change the function signature, we won't be able to compile it. We won't be able to implement operator overloading um it's important, that it looks exactly the way that it does, and now you might ask like what happens if we do change these implementation details right.

A

We we said earlier. The reason they're unstable is because we might want to change them, and so, if we do change them, won't it break the standard library right because it's depending on unstable features and the reason this is okay- is because we only ever build the standard library with one version of the compiler. It only has to support 1.62, not any later version, and so it knows how the compiler is implemented, and it can. It can write code in exactly the way that it knows the compiler will accept right.

A

So, let's take another look at the error: we've talked about language items, we've talked about intriguing functions, we've seen this is in the standard library, and I want to point out something strange here: we're building the standard library before we build the compiler now this is different from any other program that you would write in rust in a normal program.

A

You have a hello world and you use functions from the standard library just like you would anywhere else and the standard library is kind of automatically present for you when, when we ship it to you through rest, stop with ryu distro or wherever.

A

Why is the compiler different and the reason is when we build the compiler, we are not using the beta compiler, we are using the nightly standard library and the reason we do. That is because it lets us dog food new nightly features, even as they're added, without waiting for beta release, and so the way this works is we have the beta compiler, which builds the standard library, and then the new standard library is used with the beta compiler to build standard and again this is unlike any other program in that we're building the standard library.

A

Before we build the nightly compiler.

A

Right so I've talked so far about how the standard library depends on implementation. Details about how we dog food those unstable features, so we can use them in the compiler and there's another way we dog food features and that's by using language features in the compiler. We do this on nightly, even before the beta release. As soon as someone adds a new feature to the compiler, we can immediately start using it.

A

How is that possible right? How do you use these language features when you're compiling with a beta compiler and the answer? Is you don't use the beta compiler? We use something called staging, which is we use two different compilers to build rsc.

A

So the way this works is first, we build the standard library with the beta compiler. Like I talked about earlier, then we use the beta compiler and the newly compiled nightly standard library to build the nightly compiler. So we can start using library features.

A

Then we rebuild the standard library with the nightly compiler. And now, if you look at this, you might think that's kind of weird. Why are we rebuilding the standard library when we've already built it.

A

There's a great reason for that and the reason is magic, abi reasons, I'm not going to go into abis and and why this is important in this talk, but I'm happy to answer on discord or after the talk right. So then we rebuild the sender library. We use that newly compiled standard library to build the compiler again using the nightly compiler, and what that lets us do is use language features in the nightly compiler.

A

So let's take a concrete example say we stabilize a feature. This is derived default enum which lets you derive default on an enum. It was stabilized in 1.62.

A

So when we're building 1.62 uh well, the numbers are wrong, but when we're building the nightly compiler with the beta compiler, we need to enable the feature when we use it, because the beta compiler still thinks it's unstable. It hasn't been stabilized on beta, it's only been stabilized on nightly, but when we rebuild the nightlight compiler with itself, the knightly compiler does think that it's stable, and so we can disable the feature. So we don't get a warning about an unused nightly feature.

A

That's what this attribute does. It says enable the feature exactly when we're using the beta compiler and not nightly.

A

All right, I've talked so far about how this works in theory, how we want it to work, how it should work now we're going to talk about what happens when it doesn't work.

A

What happens when someone introduces a bug to the compiler most of the time it'll be caught by our test suite. We have a lot of tests, they run in every merge. They run on every platform. We catch a lot of bugs this way, but not everything's covered by tests. Sometimes things slip through, usually things just break your program. It fails to compile you get an error.

A

You report the error, we fix it, but sometimes you get a worse kind of error and that's when the program still compiles, but it does the wrong thing at runtime and that's called miscompilation.

A

So, let's, let's step through how that happens, when we miscompile the compiler itself, first, the pr gets merged. We we build a compiler source with the bug, so now any code that it compiles will have this bug.

A

Then it builds the standard library rebuilds itself with that standard library and note here that the standard library now could have bugs introduced into it that aren't present in the source, because the compiler is buggy. It did something wrong and now the standard library no longer matches your source code and even more than that, the compiler was rebuilt with itself with a version of it that was buggy, and so now we can have new bugs that are even unrelated to the original bugs.

A

Like there's no limit on how buggy it can be right other than the test suite. So that's not great.

A

In practice, this really happens. We have a lot of tests. We have a lot of great reviewers who catch bugs in prs and we have something called a release, train nightly and beta and stable, and that gives people a lot of time to report bugs and let us fix them before they impact users unstable, there's, a great talk by pietro albini in 2019 called shipping a compiler every six weeks. I highly recommend looking that up. If you're interested in how the release process works.

A

Now there's another type of bug which is when we miss a bug. It makes it past tests it gets merged rightly, but when we try and build the next version of the compiler, when we promote nightly to beta, we can't compile the new nightly compiler.

A

um So we merge the pr. We publish the beta release, we start building nightly with beta, and at this point we hit an error and we're like why. Why are we hitting an error right like we? We know this just worked before and at this point we'll discover the miscompilation will be like okay, we did something wrong, we fixed the bug and then we will patch the beta compiler, which is called back porting and then we'll use that new, patched compiler, and then we can get it to work.

A

Okay, so I've talked about bugs um that occur pretty frequently in practice, bugs that cause compile errors bugs that cause miscompilations, and we know what those look like. We know how to fix them. We have experience dealing with them now I want to talk about a kind of bug- that's still theoretically possible, but a lot harder to detect or to fix, and to do that, I need to take a detour and talk about some compiler theory, but I promise it does have practical implications. Just stay with me for a bit.

A

You may recognize this guy. His name is ken thompson. He's done a lot of stuff he's written the unix operating system. He helped work on the c programming language in the 70s and he also wrote a little pamphlet called reflections on trusting trust.

A

Now, while ken thompson was working on c, he's, of course involved with the c compiler and while he's working on it, he gets this kind of intuition about language features. Work he's like when, when you add a new feature, it's like you're teaching, the compiler about the language.

A

So, let's take a concrete example: let's say that we add a new line character to the rest language. I have some pseudo code here of basically what that would look like you have a function. It takes its input, which is a string. You parse the string. You see like a backslash n you're like okay. This is a newline character, and so the very first time you add support for this feature.

A

The new line character is not in the rest language, because you haven't added that support yet, and so you can't write it in the output code. You have to write the the actual value instead, which is ox0a and ascii, but the next time when you recompile the compiler, now it because it's written in rust now it has the feature and you no longer need to write the value in the source code. You can just write. Backslash n, like any other program, would and that's great.

A

That means that you can add lots of features to the language and you can add syntax sugar and make it easier to use and that sort of thing, but it also means that your program source is like not exactly what's in the final binary right, you have the character, lateral, which is a symbolic representation of the value, but not the value itself.

A

What happens when, instead of a feature, it's a malicious compiler, and so what goes on here is you can have a compiler that takes your source, that you reviewed and you know, is correct and does what you want to and you take a compiler that does not generate a program that corresponds to that source.

A

Then you end up with a program that looks like it should be trustworthy, but is not in fact trustworthy and so there's a solution here and the solution is you just read the source of the compiler you're like okay? Well, I've I've looked at it, I've read through rusty or whatever it's good. I'm glad great problem solved. uh Well, we're not quite what happens if the program you're generating is itself a compiler.

A

What goes wrong here, is you take your trusted. Compiler restse, you compile it with an older version with some malicious compiler and you end up with a backdoor compiler. That looks like it's trustworthy, but doesn't do what it says.

A

Then you take your trusted program which you've, reviewed and you're pretty sure is correct, and you compile that with the backdoor compiler and you end up with a binary that looks like it should be trustworthy because reviewed it in the compiler that creates it, but still is not trustworthy like. How do you avoid this sort of issue.

A

The answer to that is you keep going up the chain you keep reading more and more compiler sources. You're like okay, I've reviewed them. Every single compiler ever used in the history of my program looks good, we're pretty sure it's trustworthy, and this is called a trust chain. All those compilers in the history of your program are a trust chain.

A

The problem for rust is our trust chain is pretty long.

A

And not only is it pretty long, but it kind of trails off in 2012. We kind of forget releases come before that you have to like go through the build system and like read the source of the make files by hand like it would be like a very involved process to try and go back that far.

A

So that's great, uh but there's a solution to this there's a guy named david, a wheeler in 20 2009. He came up with an idea called diverse, double compilation and the basic idea is you take a bunch of compilers and you compile them with each other you're like if we compile cling with gcc file out with gcc again compile clang again. If we end up with the same compilers we had originally, then we're pretty sure it's trustworthy. It's it's like very, very hard to sneak a bug through that way.

A

The problem for rest is, we don't have multiple compilers. We only have one compiler, the official compiler.

A

That's fine, everything's, fine, it's probably not a big deal.

A

I seem to have messed up my selects there. We go all right, everything's, fine!

A

Well, it's not quite true that we only have one compiler there's something called mresc, which is a c plus plus compiler, which compiles rust. It's written in c, plus, compiles rust and so from there we can use existing truss chain c, plus plus, is a lot easier to establish trust trains for uh because you only have to go back four or five compilers instead of a hundred or so, and people use this in practice.

A

Google and amazon and facebook and all the big companies have their own trust chains that already exist, and they can start at m rest c, go forward and establish a trust chain for the rest, compiler.

A

And because c plus plus has multiple compilers. They can also do a shorter thing, which is just verify them against each other. They don't they don't need the trust chain unless they want to right, but there's a problem still, uh which is that mrc is kind of a one-person project right now, and so it can't keep up with all the nightly features that the rust compiler is adding on every six weeks.

A

uh Now it does support pretty recent versions. It supports 1.54, but in practice that's still like 10 or so versions of the compiler. Now I don't know how many of you have tried to compile rest c from source, but it takes a while, uh if you, if you compile it 10 times, it's probably a full day of running your computer non-stop right there, but it does work. You can do it if you want to.

A

Now I'm going to talk about future ideas for the language and for bootstrapping the compiler.

A

So not only do we have around m rescue in the last month or so there's actually the gccrs front end, which was merged into gcc master.

A

Now gccrs right now is still pretty experimental passes about half of the tests in the rest c test suite, but in two or three years I think it's very possible that it could be another source for the trust chain and it would let us compile and establish that trust chain with a lot fewer steps you wouldn't have to compile or sc 10 different times, which is great, and it also lets us verify the compilers against each other and make sure they don't have bugs that sort of thing.

A

Okay, I'm going to switch tax for a bit, I'm going to switch away from trusting trust. I talked a bit earlier about how we use beta compiled nightly, but I didn't mention where beta comes from right, like most people who are working on the compiler itself, don't have beta installed right, they use nightly. Sometimes they use stable. um We actually have a lot of trouble getting people to use beta because most of them use stable and production or if they do want features they're using nightly it's hard to get people to use beta.

A

So how do we get it onto people's systems? So we can use it and the answer is we just download it? We have a little python script that reaches out to a website. It downloads the beta compiler. It builds our build system and then the build system uses the beta compiler to build the standard library, and that works great we've done this for ages.

A

uh The problem is that now we have a python script right. If you're working on the compiler, you probably don't want to have python installed, it's not part of your normal workflow. You have to figure out like python, one versus two versus three and you're like wait. What if python, doesn't have a version number and like it turns out that there is no version of python with a name that exists on every platform?

A

It's it's like a whole mess and I got really frustrated at this in, like january of this year, I'm like okay, I'm fixing this I'm getting rid of this problem, and so, instead of using python, I had the idea what if we just use the compiler people already have installed most people working on rust use rust regularly, which is why they contribute to the language. So we can just use the rust they already have installed.

A

Take that build the beta compiler build our build system and there we go, um and I've been working on that for about six months now and it's going pretty well. uh This is the tracking issue. As you can see, it has uh six of eleven tasks checked. This is this is making good progress here.

A

uh If anyone is interested in working on this by the way please do reach out to me, I would love to help people get involved in the project and help out with this problem.

A

All right, that's it! For me, a little about me. My name is joshua nelson. I work at a company called cloudflare that does computer networking uh and I've been involved for the project for three or four years now I started with docs.rs the documentation site. I worked on rustoc the documentation generator uh most recently I work on bootstrapping.

A

A