I’ve got an announcement to make. As of Jan 4th, I’m starting at Amazon as the tech lead of their new Rust team. Working at Mozilla has been a great experience, but I’m pretty excited about this change. It’s a chance to help shape what I hope to be an exciting new phase for Rust, where we grow from a project with a single primary sponsor (Mozilla) to an industry standard, supported by a wide array of companies. It’s also a chance to work with some pretty awesome people – both familiar faces from the Rust community¹ and some new folks. Finally, I’m hoping it will be an opportunity for me to refocus my attention to some long-standing projects that I really want to see through.

I wanted to write a post that looks back over 2020 from a personal perspective. My goal here is to look at the various initiatives that I’ve been involved in and try to get a sense for how they went, what worked and what didn’t, and also what that means for next year. This post is a backdrop for a #niko2021 post that I plan to post sometime before 2021 actually starts, talking about what I expect to be doing in 2021.

(removed)

The point of the async interview series, in the end, was to help figure out what we should be doing next when it comes to Async I/O. I thought it would be good then to step back and, rather than interviewing someone else, give my opinion on some of the immediate next steps, and a bit about the medium to longer term. I’m also going to talk a bit about what I see as some of the practical challenges.

I’ve noticed that the ideas that I post on my blog are getting much more “well rounded”. That is a problem. It means I’m waiting too long to write about things. So I want to post about something that’s a bit more half-baked – it’s an idea that I’ve been kicking around to create a kind of informal “analysis API” for rustc.

The problem statement

I am interested in finding better ways to support advanced analyses that “layer on” to rustc. I am thinking of projects like Prusti or Facebook’s MIRAI, or even the venerable Clippy. All of these projects are attempts to layer on additional analyses atop Rust’s existing type system that prove useful properties about your code. Prusti, for example, lets you add pre- and post-conditions to your functions, and it will prove that they hold.

Hello everyone! I’m happy to be posting a transcript of my async interview with withoutboats. This particularly interview took place way back on January 14th, but the intervening months have been a bit crazy and I didn’t get around to writing it up till now.

Video

You can watch the video on YouTube. I’ve also embedded a copy here for your convenience:

Next steps for async

Before I go into boats’ interview, I want to talk a bit about the state of async-await in Rust and what I see as the obvious next steps. I may still do a few more async interviews after this – there are tons of interesting folks I never got to speak to! – but I think it’s also past time to try and come to a consensus of the “async roadmap” for the rest of the year (and maybe some of 2021, too). The good news is that I feel like the async interviews highlighted a number of relatively clear next steps. Sometime after this post, I hope to post a blog post laying out a “rough draft” of what such a roadmap might look like.

Hello! For the latest async interview, I spoke with Eliza Weisman (hawkw, mycoliza on twitter). Eliza first came to my attention as the author of the tracing crate, which is a nifty crate for doing application level tracing. However, she is also a core maintainer of tokio, and she works at Buoyant on the linkerd system. linkerd is one of a small set of large applications that were build using 0.1 futures – i.e., before async-await. This range of experience gives Eliza an interesting “overview” perspective on async-await and Rust more generally.

Hello! For the latest async interview, I spoke with Steven Fackler (sfackler). sfackler has been involved in Rust for a long time and is a member of the Rust libs team. He is also the author of a lot of crates, most notably tokio-postgres.

I particularly wanted to talk to sfackler about the AsyncRead and AsyncWrite traits. These traits are on everybody’s list of “important things to stabilize”, particularly if we want to create more interop between different executors and runtimes. On the other hand, in [tokio-rs/tokio#1744], the tokio project is considering adopting its own variant traits that diverge significantly from those in the futures crate, precisely because they have concerns over the design of the traits as is. This seems like an important area to dig into!

Hello! For the latest async interview, I spoke with Florian Gilcher (skade). Florian is involved in the async-std project, but he’s also one of the founders of Ferrous Systems, a Rust consulting firm that also does a lot of trainings. In that capacity, he’s been teaching people to use async Rust now since Rust’s 1.0 release.

Video

You can watch the video on YouTube. I’ve also embedded a copy here for your convenience:

One note: something about our setup meant that I was hearing a lot of echo. I think you can sometimes hear it in the recording, but not nearly as bad as it was live. So if I seem a bit spacey, or take very long pauses, you might know the reason why!

In my #rust2020 blog post, I mentioned rather off-handedly that I think the time has come for us to talk about forming a Rust foundation. I wanted to come back to this topic and talk in more detail about what I think a Rust foundation might look like. And, since I don’t claim to have the final answer to that question by any means, I’d also like to talk about how I think we should have this conversation going forward.

Hello! For the latest async interview, I spoke with Carl Lerche (carllerche). Among many other crates¹, Carl is perhaps best known as one of the key authors behind tokio and mio. These two crates are quite widely used through the async ecosystem. Carl and I spoke on December 3rd.

Video

You can watch the video on YouTube. I’ve also embedded a copy here for your convenience:

Background: the mio crate

One of the first things we talked about was a kind of overview of the layers of the “tokio-based async stack”.

This blog post is continuing my conversation with cramertj. This will be the last post.

In the first post, I covered what we said about Fuchsia, interoperability, and the organization of the futures crate.

In the second post, I covered cramertj’s take on the Stream, AsyncRead, and AsyncWrite traits. We also discused the idea of attached streams and the imporance of GATs for modeling those.

In this post, we’ll talk about async closures.

You can watch the video on YouTube.

This blog post is continuing my conversation with cramertj.

In the first post, I covered what we said about Fuchsia, interoperability, and the organization of the futures crate. This post covers cramertj’s take on the Stream trait as well as the AsyncRead and AsyncWrite traits.

You can watch the video on YouTube.

The need for “streaming” streams and iterators

Next, cramertj and I turned to discussing some of the specific traits from the futures crate. One of the traits that we covered was Stream. The Stream trait is basically the asynchronous version of the Iterator trait. In (slightly) simplified form, it is as follows:

For the second async interview, I spoke with Taylor Cramer – or cramertj, as I’ll refer to him. cramertj is a member of the compiler and lang teams and was – until recently – working on Fuchsia at Google. He’s been a key player in Rust’s Async I/O design and in the discussions around it. He was also responsible for a lot of the implementation work to make async fn a reality.

I want to write about an idea that Josh Triplett and I have been iterating on to revamp the lang team RFC process. I have written a draft of an RFC already, but this blog post aims to introduce the idea and some of the motivations. The key idea of the RFC is formalize the steps leading up to an RFC, as well as to capture the lang team operations around project groups. The hope is that, if this process works well, it can apply to teams beyond the lang team as well.

Technically speaking, it’s past the deadline for #rust2020 posts, but I’m running late this year, and I’m going to post something anyway. In this post, I am focusing on what I see as the “largest scale” issues, and not on technical initiatives. If I have time, I will try to post a follow-up talking about some of the key technical initiatives that I think we should focus on as well.

Hello from Iceland! (I’m on vacation.) I’ve just uploaded [the first of the Async Interviews][video] to YouTube. It is a conversation with Alex Crichton (alexcrichton) and Nick Fitzgerald (fitzgen) about how WebAssembly and Rust’s Async I/O system interact. When you watch it, you will probably notice two things:

• First, I spent a lot of time looking off to the side! This is because I had the joint Dropbox paper document open on my side monitor and I forgot how strange that would look. I’ll have to remember that for the future. =)
• Second, we recorded this on October 3rd¹, which was before async-await had landed on stable. So at various points we talk about async-await being on beta or not yet being stable. Don’t be confused. =)

Video

You can view the [video][video] on YouTube, but it is also embedded here if that’s easier for you.

Hello all! I’m going to be trying something new, which I call the “Async Interviews”. These interviews are going to be a series of recorded video calls with various “luminaries” from Rust’s Async I/O effort. In each one, I’m going to be asking roughly the same question: Now that the async-await MVP is stable, what should we be doing next? After each call, I’ll post the recording from the interview, along with a blog post that leaves a brief summary.

After reading boat’s excellent post on asynchronous destructors, I thought it might be a good idea to write some about async fn in traits. Support for async fn in traits is probably the single most common feature request that I hear about. It’s also one of the more complex topics. So I thought it’d be nice to do a blog post kind of giving the “lay of the land” on that feature – what makes it complicated? What questions remain open?

I would like to describe an idea that’s been kicking around in my head. I’m calling this idea “shepherds 3.0” – the 3.0 is to distinguish it from the other places we’ve used the term in the past. This proposal actually supplants both of the previous uses of the term, replacing them with what I believe to be a preferred alternative (more on that later).

Caveat

This is an idea that has been kicking around in my head for a while. It is not a polished plan and certainly not an accepted one. I’ve not talked it over with the rest of the lang team, for example. However, I wanted to put it out there for discussion, and I do think we should be taking some step in this direction soon-ish.

I have been thinking about how language feature development works in Rust¹. I wanted to write a post about what I see as one of the key problems: too much concurrency in our design process, without any kind of “back-pressure” to help keep the number of “open efforts” under control. This setup does enable us to get a lot of things done sometimes, but I believe it also leads to a number of problems.

I wanted to give an update on the status of the “async-await foundations” working group. This post aims to cover three things:

• the “async await MVP” that we are currently targeting;
• how that fits into the bigger picture;
• and how you can help, if you’re so inclined;

Current target: async-await MVP

We are currently working on stabilizing what we call the async-await MVP – as in, “minimal viable product”. As the name suggests, the work we’re doing now is basically the minimum that is needed to “unlock” async-await. After this work is done, it will be easier to build async I/O based applications in Rust, though a number of rough edges remain.

On internals, I just announced the formation of the language-design team meta working group. The role of the meta working group is to figure out how other language-design team working groups should work. The plan is to begin by enumerating some of our goals – the problems we aim to solve, the good things we aim to keep – and then move on to draw up more details plans. I expect this discussion will intersect the RFC process quite heavily (at least when it comes to language design changes). Should be interesting! It’s all happening in the open, and a major goal of mine is for this to be easy to follow along with from the outside – so if talking about talking is your thing, you should check it out.

In my previous post, I talked about the idea of mapping the solution space:

When we talk about the RFC process, we always emphasize that the point of RFC discussion is not to select the best answer; rather, the point is to map the solution space. That is, to explore what the possible tradeoffs are and to really look for alternatives. This mapping process also means exploring the ups and downs of the current solutions on the table.

In the talk I gave at Rust LATAM, I said that the Rust project has always emphasized finding the best solution, rather than winning the argument. I think this is one of our deepest values. It’s also one of the hardest for us to uphold.

Let’s face it – when you’re having a conversation, it’s easy to get attached to specific proposals. It’s easy to have those proposals change from “Option A” vs “Option B” to “my option” and “their option”. Once this happens, it can be very hard to let them “win” – even if you know that both options are quite reasonable.

Lately, the compiler team has been changing up the way that we work. Our goal is to make it easier for people to track what we are doing and – hopefully – get involved. This is an ongoing effort, but one thing that has become clear immediately is this: the compiler team needs more than coders.

Traditionally, when we’ve thought about how to “get involved” in the compiler team, we’ve thought about it in terms of writing PRs. But more and more I’m thinking about all the other jobs that go into maintaining the compiler. “What kinds of jobs are these?”, you’re asking. I think there are quite a few, but let me give a few examples:

I wanted to post a quick update on the status of the async-await effort. The short version is that we’re in the home stretch for some kind of stabilization, but there remain some significant questions to overcome.

Announcing the implementation working group

As part of this push, I’m happy to announce we’ve formed a async-await implementation working group. This working group is part of the whole async-await effort, but focused on the implementation, and is part of the compiler team. If you’d like to help get async-await over the finish line, we’ve got a list of issues where we’d definitely like help (read on).

Now that the Rust 2018 edition has shipped, the language design team has been thinking a lot about what to do in 2019 and over the next few years. I think we’ve got a lot of exciting stuff on the horizon, and I wanted to write about it.

Theme for this edition

In 2015, our overall theme was stability. For the 2018 Edition, we adopted productivity. For Rust 2021¹, we are thinking of maturity as the theme. Our goal is finish up a number of in-flight features – such as specialization, generic associated types, and const generics – that have emerged as key enablers for future work. In tandem, we aim to start improving our reference material, both through continuing the great work that’s been done on the Rust reference but also through more specialized efforts like the Grammar and Unsafe Code Guidelines working groups.

So for the last couple of months or so, I’ve been hacking in my spare time on this library named salsa, along with a number of awesome other folks. Salsa basically extracts the incremental recompilation techniques that we built for rustc into a general-purpose framework that can be used by other programs. Salsa is developing quickly: with the publishing of v0.10.0, we saw a big step up in the overall ergonomics, and I think the current interface is starting to feel very nice.

In my previous post about Polonius and subregion obligations, I mentioned that there needs to be a follow-up to deal with higher-ranked subregions. This post digs a bit more into what the problem is in the first place and sketches out the general solution I have in mind, but doesn’t give any concrete algorithms for it.

The subset relation in Polonius is not enough

In my original post on Polonius, I assumed that when we computed a subtype relation T1 <: T2 between two types, the result was either a hard error or a set of subset relations between various regions. So, for example, if we had a subtype relation between two references:

Now that NLL has been shipped, I’ve been doing some work revisiting the Polonius project. Polonius is the project that implements the “alias-based formulation” described in my older blogpost. Polonius has come a long way since that post; it’s now quite fast and also experimentally integrated into rustc, where it passes the full test suite.

However, polonius as described is not complete. It describes the core “borrow check” analysis, but there are a number of other checks that the current implementation checks which polonius ignores:

To me, 2018 felt like a big turning point for Rust, and it wasn’t just the edition. Suddenly, it has become “normal” for me to meet people using Rust at their jobs. Rust conferences are growing and starting to have large number of sponsors. Heck, I even met some professional Rust developers amongst the parents at a kid’s birthday party recently. Something has shifted, and I like it.

At the same time, I’ve also noticed a lot of exhaustion. I know I feel it – and a lot of people I talk to seem to feel the same way. It’s great that so much is going on in the Rust world, but we need to get better at scaling our processes up and processing it effectively.

This week I’ve been attending SPLASH 2018. It’s already been quite an interesting week, and it’s only just begun. I thought I’d write up a quick report on some of the things that have been particularly interesting to me, and some of the ideas that they’ve sparked off.

Teaching programming (and Rust!)

I really enjoyed this talk by Felienne Hermans entitled “Explicit Direct Instruction in Programming Education”. The basic gist of the talk was that, when we teach programming, we often phrase it in terms of “exploration” and “self-expression”, but that this winds up leaving a lot of folks in the cold and may be at least partly responsible for the lack of diversity in computer science today. She argued that this is like telling kids that they should just be able to play a guitar and create awesome songs without first practicing their chords¹ – it kind of sets them up to fail.

In my previous post on the status of NLL, I promised to talk about “What is next?” for ownership and borrowing in Rust. I want to lay out the various limitations of Rust’s ownership and borrowing system that I see, as well as – where applicable – current workarounds. I’m curious to get feedback on which problems affect folks the most.

The first limitation I wanted to focus on is interprocedural conflicts. In fact, I’ve covered a special case of this before – where a closure conflicts with its creator function – in my post on Precise Closure Capture Clauses. But the problem is more general.

Now that the final Rust 2018 Release Candidate has shipped, I thought it would be a good idea to do another update on the state of the MIR-based borrow check (aka NLL). The last update was in June, when we were still hard at work on getting things to work.

Rust 2018 will use NLL now

Let’s get the highlights out of the way. Most importantly, Rust 2018 crates will use NLL by default. Once the Rust 2018 release candidate becomes stable, we plan to switch Rust 2015 crates to use NLL as well, but we’re holding off until we have some more experience with people using it in the wild.

Just a quick note that the October 2018 office hour slots are now posted. If you’re having a problem with Rust, or have something you’d like to talk out, please sign up!

This is a report on the second “office hours”, in which we discussed how to setup a series of services or actors that communicate with one another. This is a classic kind of problem in Rust: how to deal with cyclic data. Usually, the answer is that the cycle is not necessary (as in this case).

The setup

To start, let’s imagine that we were working in a GC’d language, like JavaScript. We want to have various “services”, each represented by an object. These services may need to communicate with one another, so we also create a directory, which stores pointers to all the services. As each service is created, they add themselves to the directory; when it’s all setup, each service can access all other services. The setup might look something like this:

This is a report on the first “office hours”, in which we discussed debugging Rust programs with gdb. I’m very grateful to Ramana Venkata for suggesting the topic, and to Tom Tromey, who joined in. (Tom has been doing a lot of the work of integrating rustc into gdb and lldb lately.)

This blog post is just going to be a quick summary of the basic workflow of using Rust with gdb on the command line. I’m assuming you are using Linux here, since I think otherwise you would prefer a different debugger. There are probably also nifty graphical tools you can use and maybe even IDE integrations, I’m not sure.

Hello, all! Beginning this Friday (in two days)¹, I’m going to start an experiment that I call Rust office hours. The idea is simple: I’ve set aside a few slots per week to help people work through problems they are having learning or using Rust. My goal here is both to be of service but also to gain more insight into the kinds of things people have trouble with. No problem is too big or too small!²

This post examines a particular, seemingly simple problem: given ownership of a Rc<Vec<u32>>, can we write a function that returns an impl Iterator<Item = u32>? It turns out that this is a bit harder than it might at first appear – and, as we’ll see, for good reason. I’ll dig into what’s going on, how you can fix it, and how we might extend the language in the future to try and get past this challenge.

One of the long-standing issues that we’ve been wrestling with in Rust is how to integrate the concept of an “uninhabited type” – that is, a type which has no values at all. Uninhabited types are useful to represent the “result” of some computation you know will never execute – for example, if you have to define an error type for some computation, but this particular computation can never fail, you might use an uninhabited type.

I consider Rust’s RFC process one of our great accomplishments, but it’s no secret that it has a few flaws. At its best, the RFC offers an opportunity for collaborative design that is really exciting to be a part of. At its worst, it can devolve into bickering without any real motion towards consensus. If you’ve not done so already, I strongly recommend reading aturon’s excellent blog posts on this topic.

The RFC process has also evolved somewhat organically over time. What began as “just open a pull request on GitHub” has moved into a process with a number of formal and informal stages (described below). I think it’s a good time for us to take a step back and see if we can refine those stages into something that works better for everyone.

I’ve been getting a lot of questions about the status of “Non-lexical lifetimes” (NLL) – or, as I prefer to call it these days, the MIR-based borrow checker – so I wanted to post a status update.

The single most important fact is that the MIR-based borrow check is feature complete and available on nightly. What this means is that the behavior of #![feature(nll)] is roughly what we intend to ship for “version 1”, except that (a) the performance needs work and (b) we are still improving the diagnostics. (More on those points later.)

Ever since the Rust All Hands, I’ve been experimenting with an alternative formulation of the Rust borrow checker. The goal is to find a formulation that overcomes some shortcomings of the current proposal while hopefully also being faster to compute. I have implemented a prototype for this analysis. It passes the full NLL test suite and also handles a few cases – such as #47680 – that the current NLL analysis cannot handle. However, the performance has a long way to go (it is currently slower than existing analysis). That said, I haven’t even begun to optimize yet, and I know I am doing some naive and inefficient things that can definitely be done better; so I am still optimistic we’ll be able to make big strides there.

This is the second in a series of posts about Rust compiler errors. Each one will talk about a particular error that I got recently and try to explain (a) why I am getting it and (b) how I fixed it. The purpose of this series of posts is partly to explain Rust, but partly just to gain data for myself. I may also write posts about errors I’m not getting – basically places where I anticipated an error, and used a pattern to avoid it. I hope that after writing enough of these posts, I or others will be able to synthesize some of these facts to make intermediate Rust material, or perhaps to improve the language itself.

I’ve decided to do a little series of posts about Rust compiler errors. Each one will talk about a particular error that I got recently and try to explain (a) why I am getting it and (b) how I fixed it. The purpose of this series of posts is partly to explain Rust, but partly just to gain data for myself. I may also write posts about errors I’m not getting – basically places where I anticipated an error, and used a pattern to avoid it. I hope that after writing enough of these posts, I or others will be able to synthesize some of these facts to make intermediate Rust material, or perhaps to improve the language itself.

So aturon wrote this beautiful post about what a good week it has been. In there, they wrote:

Breakthrough #2: @nikomatsakis had a eureka moment and figured out a path to make specialization sound, while still supporting its most important use cases (blog post forthcoming!). Again, this suddenly puts specialization on the map for Rust Epoch 2018.

Sheesh I wish they hadn’t written that! Now the pressure is on. Well, here goes nothing =).

I’ve been thinking a lot about persistent collections lately and in particular how they relate to Rust, and I wanted to write up some of my observations.¹

What is a persistent collection?

Traditionally, persistent collections are seen as this “wildly different” way to setup your collection. Instead of having methods like push, which grow a vector in place:

vec.push(element); // add element to `vec`

you have a method like add, which leaves the original vector alone but returns a new vector that has been modified:

In my last Chalk post, I talked about an experimental, SLG-based solver that I wrote for Chalk. That particular design was based very closely on the excellent paper “Efficient top-down computation of queries under the well-founded semantics”, by W. Chen, T. Swift, and D. Warren. It followed a traditional Prolog execution model: this has a lot of strengths, but it probably wasn’t really suitable for use in rustc. The single biggest reason for this was that it didn’t really know when to stop: given a query like exists<T> { T: Sized }, it would happily try to enumerate all sized types in the system. It was also pretty non-obvious to me how to extend that system with things like co-inductive predicates (needed for auto traits) and a few other peculiarities of Rust.

As part of #Rust2018, I thought I would try to writeup my own (current) perspective. I’ll try to keep things brief.

First and foremost, I think that this year we have to finish what we started and get the “Rust 2018” release out the door. We did good work in 2017: now we have to make sure the world knows it and can use it. This primarily means we have to do stabilization work, both for the recent features added in 2017 as well as some, ahem, longer-running topics, like SIMD. It also means keeping up our focus on tooling, like IDE support, rustfmt, and debugger integration.

So, as you likely know, we tried something new at the end of 2017. For roughly the final quarter of the year, we essentially stopped doing design work, and instead decided to focus on implementation – what we called the “impl period”. We had two goals for the impl period: (a) get a lot of high-value implementation work done and (b) to do that by expanding the size of our community, and making it easy for new people to get involved. To that end, we spun up about 40 working groups, which is really a tremendous figure when you think about it, each of which was devoted to a particular task.

For the last month or so, I’ve gotten kind of obsessed with exploring a new evaluation model for Chalk. Specifically, I’ve been looking at adapting the SLG algorithm, which is used in the XSB Prolog engine. I recently opened a PR that adds this SLG-based solver as an alternative, and this blog post is an effort to describe how that PR works, and explore some of the advantages and disadvantages I see in this approach relative to the current solver that I described in my previous post.

In my last post about chalk queries, I discussed how the query model in chalk. Since that writing, there have been some updates, and I thought it’d be nice to do a new post covering the current model. This post will also cover the tabling technique that scalexm implemented for handling cyclic relations and show how that enables us to implement implied bounds and other long-desired features in an elegant way. (Nice work, scalexm!)

I’ve been hard at work the last month or so on trying to complete the non-lexical lifetimes RFC. I’m pretty excited about how it’s shaping up. I wanted to write a kind of “meta” blog post talking about the current state of the proposal – almost there! – and how you could get involved with helping to push it over the finish line.

TL;DR

What can I say, I’m loquacious! In case you don’t want to read the full post, here are the highlights:

For my next post discussing chalk, I want to take kind of a different turn. I want to talk about the general struct of chalk queries and how chalk handles them right now. (If you’ve never heard of chalk, it’s sort of “reference implementation” for Rust’s trait system, as well as an attempt to describe Rust’s trait system in terms of its logical underpinnings; see this post for an introduction to the big idea.)

I recently participated in the GNOME / Rust “dev sprint” in Mexico City. (A thousand thanks to Federico and Joaquin for organizing!) While there I spent some time working on the gnome-class plugin. The goal of gnome-class was to make it easy to write GObject implementations in Rust which would fully interoperate with C code.

Roughly speaking, my goal was that you should be able to write code that looked and felt like Vala code, but where the method bodies (and types, and so forth) are in Rust. The plugin is in no way done, but I think it’s already letting you do some pretty nice stuff. For example, this little snippet defines a Counter class offering two methods (add() and get()):

In my previous post, I talked over the basics of how unification works and showed how that “mathematical version” winds up being expressed in chalk. I want to go a bit further now and extend that base system to cover associated types. These turn out to be a pretty non-trival extension.

What is an associated type?

If you’re not a Rust programmer, you may not be familiar with the term “associated type” (although many langages have equivalents). The basic idea is that traits can have type members associated with them. I find the most intuitive example to be the Iterator trait, which has an associated type Item. This type corresponds to kind of elements that are produced by the iterator:

So in my first post on chalk, I mentioned that unification and normalization of associated types were interesting topics. I’m going to write a two-part blog post series covering that. This first part begins with an overview of how ordinary type unification works during compilation. The next post will add in associated types and we can see what kinds of mischief they bring with them.

What is unification?

Let’s start with a brief overview of what unification is. When you are doing type-checking or trait-checking, it often happens that you wind up with types that you don’t know yet. For example, the user might write None – you know that this has type Option<T>, but you don’t know what that type T is. To handle this, the compiler will create a type variable. This basically represents an unknown, to-be-determined type. To denote this, I’ll write Option<?T>, where the leading question mark indicates a variable.

In my previous post, I outlined a plan for non-lexical lifetimes. I wanted to write a follow-up post today that discusses different ways that we can extend the system to support nested mutable calls. The ideas here are based on some the ideas that emerged in a recent discussion on internals, although what I describe here is a somewhat simplified variant. If you want more background, it’s worth reading at least the top post in the thread, where I laid out a lot of the history here. I’ll try to summarize the key bits as I go.

At the recent compiler design sprint, we spent some time discussing non-lexical lifetimes, the plan to make Rust’s lifetime system significantly more advanced. I want to write-up those plans here, and give some examples of the kinds of programs that would now type-check, along with some that still will not (for better or worse).

If you were at the sprint, then the system I am going to describe in this blog post will actually sound quite a bit different than what we were talking about. However, I believe it is equivalent to that system. I am choosing to describe it differently because this version, I believe, would be significantly more efficient to implement (if implemented naively). I also find it rather easier to understand.

This last week we had the rustc compiler team design sprint. This was our second rustc compiler team sprint; the first one (last year) we simply worked on pushing various projects over the finish line (for example, in an epic effort, arielb1 completed dynamic drop during that sprint).

This sprint was different: we had the goal of talking over many of the big design challenges that we’d like to tackle in the upcoming year and making sure that the compiler team was roughly on board with the best way to implement them.

In a previous post, I talked about a proposed approach to drafting the unsafe code guidelines. Specifically, I want to the approach of having an executable specification of Rust with additional checks that will signal when undefined behavior has occurred. In this post, I want to try to dive into that idea a bit more and give some more specifics of the approach I have in mind. I’m going to focus on this post on the matter of the proper use of shared references &T – I’ll completely ignore &mut T for now, since those are much more complicated (because they require a notion of uniqueness).

Over the last year or two (man, it’s scary how time flies), I’ve been doing quite a lot of thinking about Rust’s trait system. I’ve been looking for a way to correct a number of flaws and shortcomings in the current implementation, not the least of which is that it’s performance is not that great. But also, I’ve been wanting to get a relatively clear, normative definition of how the trait system works, so that we can better judge possible extensions. After a number of false starts, I think I’m finally getting somewhere, so I wanted to start writing about it.

While I was at POPL the last few days, I was reminded of an idea regarding how to bring more struture to the unsafe code guidelines process that I’ve been kicking around lately, but which I have yet to write about publicly. The idea is fresh on my mind because while at POPL I realized that there is an interesting opportunity to leverage the “blame” calculation techniques from gradual typing research. But before I get to blame, let me back up and give some context.

This post is the (long awaited, or at least long promised) third post in my series on Rayon’s parallel iterators. The previous two posts were some time ago, but I’ve been feeling inspired to push more on Rayon lately, and I remembered that I had never finished this blog post series.

Here is a list of the other posts in the series. If you haven’t read them, or don’t remember them, you will want to do so before reading this one:

This post is a continuation of my posts discussing the topic of associated type constructors (ATC) and higher-kinded types (HKT):

1. The first post focused on introducing the basic idea of ATC, as well as introducing some background material.
2. The second post showed how we can use ATC to model HKT, via the “family” pattern.
3. The third post did some exploration into what it would mean to support HKT directly in the language, instead of modeling them via the family pattern.
4. This post considers what it might mean if we had both ATC and HKT in the language: in particular, whether those two concepts can be unified, and at what cost.

Unifying HKT and ATC

So far we have seen “associated-type constructors” and “higher-kinded types” as two distinct concepts. The question is, would it make sense to try and unify these two, and what would that even mean?

This post is a continuation of my posts discussing the topic of associated type constructors (ATC) and higher-kinded types (HKT):

1. The first post focused on introducing the basic idea of ATC, as well as introducing some background material.
2. The second post showed how we can use ATC to model HKT, via the “family” pattern.
3. This post dives into what it would mean to support HKT directly in the language, instead of modeling them via the family pattern.

The story thus far (a quick recap)

In the previous posts, we had introduced a basic Collection trait that used ATC to support an iterate() method:

Hello. This post is a continuation of my posts discussing the topic of associated type constructors (ATC) and higher-kinded types (HKT):

1. The first post focused on introducing the basic idea of ATC, as well as introducing some background material.
2. This post talks about some apparent limitations of associated type constructors, and shows how we can overcome them by making use of a design pattern that I call “family traits”. Along the way, we introduce the term higher-kinded type for the first time, and show (informally) that family traits are equally general.

The limits of associated type constructors

OK, so in the last post we saw how we can use ATC to define a Collection trait, and how to implement that trait for our sample collection List<T>. In particular, ATC let us express the return type of the iterator() method as Self::Iter<'iter>, so that we can incorporate the lifetime 'iter of each particular iterator.

So for the end of last week, I was at Rust Belt Rust. This was awesome. And not only because the speakers and attendees at Rust Belt Rust were awesome, though they were. But also because it gave aturon, withoutboats, and I a chance to talk over a lot of stuff in person. We covered a lot of territory and so I wanted to do a series of blog posts trying to write down some of the things we were thinking so as to get other people’s input.

In my previous post, I talked about how we can separate out specialization into two distinct concepts: reuse and override. Doing so makes because the conditions that make reuse possible are more stringent than those that make override possible. In this post, I want to extend this idea to talk about a new rule for specialization that allow overriding in more cases. These rules are a big enabler for specialization, allowing it to accommodate many use cases that we couldn’t handle before. In particular, they enable us to add blanket impls like impl<T: Copy> Clone for T in a backwards compatible fashion, though only under certain conditions.

I spent a really interesting day last week at Northeastern University. First, I saw a fun talk by Philip Haller covering LaCasa, which is a set of extensions to Scala that enable it to track ownership. Many of the techniques reminded me very much of Rust (e.g., the use of “spores”, which are closures that can limit the types of things they close over); if I have time, I’ll try to write up a more detailed comparison in some later post.

For the past year or so, I and a few others have been iterating on some tutorial slides for learning Rust. I’ve given this tutorial here at the local Boston Rust Meetup a few times, and we used the same basic approach at RustConf; I’ve been pretty happy with the results. But until now it’s been limited to “in person” events.

That’s why I’m so happy to announce a new site, Into Rust. Into Rust contains screencasts of many of these slides, and in particular the ones I consider most important: those that cover Ownership and Borrowing, which I think is the best place to start teaching Rust. I’ve divided up the material into roughly 30min screencasts so that they should be relatively easy to consume in one sitting – each also has some associated exercises to help make your knowledge more concrete.

In my previous post, I started discussing the idea of intersection impls, which are a possible extension to specialization. I am specifically looking at the idea of making it possible to add blanket impls to (e.g.) implement Clone for any Copy type. We saw that intersection impls, while useful, do not enable us to do this in a backwards compatible way.

Today I want to dive a bit deeper into specialization. We’ll see that specialization actually couples together two things: refinement of behavior and reuse of code. This is no accident, and its normally a natural thing to do, but I’ll show that, in order to enable the kinds of blanket impls I want, it’s important to be able to tease those apart somewhat.

As some of you are probably aware, on the nightly Rust builds, we currently offer a feature called specialization, which was defined in RFC 1210. The idea of specialization is to improve Rust’s existing coherence rules to allow for overlap between impls, so long as one of the overlapping impls can be considered more specific. Specialization is hotly desired because it can enable powerful optimizations, but also because it is an important component for modeling object-oriented designs.

I’ve been thinking about the unsafe code guidelines a lot in the back of my mind. In particular, I’ve been trying to think through what it means to “trust types” – if you recall from the Tootsie Pop Model (TPM) blog post, one of the key examples that I was wrestling with was the RefCell-Ref example. I want to revisit a variation on that example now, but from a different angle. (This by the way is one of those “Niko thinks out loud” blog posts, not one of those “Niko writes up a proposal” blog posts.)

A little while back, I wrote up a tentative proposal I called the “Tootsie Pop” model for unsafe code. It’s safe to say that this model was not universally popular. =) There was quite a long and fruitful discussion on discuss. I wanted to write a quick post summarizing my main take-away from that discussion and to talk a bit about the plans to push the unsafe discussion forward.

The importance of the unchecked-get use case

For me, the most important lesson was the importance of the “unchecked get” use case. Here the idea is that you have some (safe) code which is indexing into a vector:

In my previous post, I spent some time talking about the idea of unsafe abstractions. At the end of the post, I mentioned that Rust does not really have any kind of official guidelines for what kind of code is legal in an unsafe block and what is not.What this means in practice is that people wind up writing what “seems reasonable” and checking it against what the compiler does today. This is of course a risky proposition since it means that if we start doing more optimization in the compiler, we may well wind up breaking unsafe code (the code would still compile; it would just not execute like it used to).

The unsafe keyword is a crucial part of Rust’s design. For those not familiar with it, the unsafe keyword is basically a way to bypass Rust’s type checker; it essentially allows you to write something more like C code, but using Rust syntax.

The existence of the unsafe keyword sometimes comes as a surprise at first. After all, isn’t the point of Rust that Rust programs should not crash? Why would we make it so easy then to bypass Rust’s type system? It can seem like a kind of flaw in the design.

This is the third post in my series on non-lexical lifetimes. Here I want to dive into Problem Case #3 from the introduction. This is an interesting case because exploring it is what led me to move away from the continuous lifetimes proposed as part of RFC 396.

Problem case #3 revisited

As a reminder, problem case #3 was the following fragment:

fn get_default<'m,K,V:Default>(map: &'m mut HashMap<K,V>,
                               key: K)
                               -> &'m mut V {
    match map.get_mut(&key) { // -------------+ 'm
        Some(value) => value,              // |
        None => {                          // |
            map.insert(key, V::default()); // |
            //  ^~~~~~ ERROR               // |
            map.get_mut(&key).unwrap()     // |
        }                                  // |
    }                                      // |
}                                          // v

What makes this example interesting is that it crosses functions. In particular, when we call get_mut the first time, if we get back a Some value, we plan to return the point, and hence the value must last until the end of the lifetime 'm (that is, until some point in the caller). However, if we get back a None value, we wish to release the loan immediately, because there is no reference to return.

In my previous post I outlined several cases that we would like to improve with Rust’s current borrow checker. This post discusses one possible scheme for solving those. The heart of the post is two key ideas:

1. Define a lifetime as a set of points in the control-flow graph, where a point here refers to some particular statement in the control-flow graph (i.e., not a basic block, but some statement within a basic block).
2. Use liveness as the basis for deciding where a variable’s type must be valid.

The rest of this post expounds on these two ideas and shows how they affect the various examples from the previous post.

Over the last few weeks, I’ve been devoting my free time to fleshing out the theory behind non-lexical lifetimes (NLL). I think I’ve arrived at a pretty good point and I plan to write various posts talking about it. Before getting into the details, though, I wanted to start out with a post that lays out roughly how today’s lexical lifetimes work and gives several examples of problem cases that we would like to solve.

For the last couple of weeks, my mornings have been occupied with a pretty serious revamping of LALRPOP’s error message output. I will probably wind up doing a series of blog posts about the internal details of how it works, but I wanted to write a little post to advertise this work.

Typically when you use an LR(1) parser generator, error messages tend to be written in terms of the LR(1) state generation algorithm. They use phrases like “shift/reduce conflict” and talk about LR(1) items. Ultimately, you have to do some clever thinking to relate the error to your grammar, and then a bit more clever thinking to figure out how you should adjust your grammar to make the problem go away. While working on adapting the Rust grammar to LALRPOP, I found I was wasting a lot of time trying to decrypt the error messages, and I wanted to do something about it. This work is the result.

This post is the second post in my series on Rayon’s parallel iterators. The goal of this series is to explain how parallel iterators are implemented internally, so I’m going to be going over a lot of details and giving a lot of little code examples in Rust. If all you want to do is use parallel iterators, you don’t really have to understand any of this stuff.

I’ve had a lot of fun designing this system, and I learned a few lessons about how best to use Rust (some of which I cover in the conclusions). I hope you enjoy reading about it!

Since giving a talk about Rayon at the Bay Area Rust meetup, I’ve been working off and on on the support for parallel iterators. The basic idea of a parallel iterator is that I should be able to take an existing iterator chain, which operates sequentially, and easily convert it to work in parallel. As a simple example, consider this bit of code that computes the dot-product of two vectors:

vec1.iter()
    .zip(vec2.iter())
    .map(|(i, j)| i * j)
    .sum()

Using parallel iterators, all I have to do to make this run in parallel is change the iter calls into par_iter:

Over the last week or so, I’ve been working on an update to Rayon, my experimental library for data parallelism in Rust. I’m pretty happy with the way it’s been going, so I wanted to write a blog post to explain what I’ve got so far.

Rayon’s goal is to make it easy to add parallelism to your sequential code – so basically to take existing for loops or iterators and make them run in parallel. For example, if you have an existing iterator chain like this:

So, aturon wrote this interesting post on an alternative “virtual structs” approach, and, more-or-less since he wrote it, I’ve been wanting to write up my thoughts. I finally got them down.

Before I go any further, a note on terminology. I will refer to Aaron’s proposal as the Thin Traits proposal, and my own previous proposal as the Extended Enums proposal. Very good.

(OK, I lied, one more note: starting with this post, I’ve decided to disable comments on this blog. There are just too many forums to keep up with! So if you want to discuss this post, I’d recommend doing so on this Rust internals thread.)

Around four years ago, when I had first decided to start at Mozilla research, I had planned to write an LR(1) parser generator. It seemed like a good way to get to know Rust. However, I found that newborns actually occupy somewhat more time than anticipated (read: I was lucky to squeeze in a shower), and hence that never came to pass.

Well, I’m happy to say that, four years later, I’ve finally rectified that. For a few months now I’ve been working on a side project while I have my morning coffee: LALRPOP (pronounced like some sort of strangely accented version of “lollypop”). LALRPOP is an LR(1) parser generator that emits Rust code. It is designed for ease of use, so it includes a number of features that many parser generators are missing:

So, in previous posts, I discussed the pros and cons of two different approaches to modeling variants: Rust-style enums and C++-style classes. In those posts, I explained why I see Rust enums and OO-style class hierarchies as more alike than different (I personally credit Scala for opening my eyes to this, though I’m sure it’s been understood by others for much longer). The key points were as follows:

• Both Rust-style enums and C++-style classes can be used to model the idea of a value that be one of many variants, but there are differences in how they work at runtime. These differences mean that Rust-style enums are more convenient for some tasks, and C++-style classes for others. In particular:
  • A Rust-style enum is sized as large as the largest variant. This is great because you can lay them out flat in another data structure without requiring any allocation. You can also easily change from one variant to another. One downside of Rust enums is that you cannot “refine” them to narrow the set of variants that a particular value can have.
  • A C++-style class is sized to be exactly as big as one variant. This is great because it can be much more memory efficient. However, if you don’t know what variant you have, you must manipulate the value by pointer, so it tends to require more allocation. It is also impossible to change from one variant to another. Class hierarchies also give you a simple, easily understood kind of refinement, and the ability to have common fields that are shared between variants.
• C++-style classes offer constructors, which allows for more abstraction and code reuse when initially creating an instance, but raise thorny questions about the type of a value under construction; Rust structs and enums are always built in a single-shot today, which is simpler and safer but doesn’t compose as well.

What I want to talk about in this post is a proposal (or proto-proposal) for bridging those two worlds in Rust. I’m going to focus on data layout in this post. I’ll defer virtual methods for another post (or perhaps an RFC). Spoiler alert: they can be viewed as a special case of specialization.

This is the second post summarizing my current thoughts about ideas related to “virtual structs”. In the last post, I described how, when coding C++, I find myself missing Rust’s enum type. In this post, I want to turn it around. I’m going to describe why the class model can be great, and something that’s actually kind of missing from Rust. In the next post, I’ll talk about how I think we can get the best of both worlds for Rust. As in the first post, I’m focusing here primarily on the data layout side of the equation; I’ll discuss virtual dispatch afterwards.

One priority for Rust after 1.0 is going to be incorporating some kind of support for “efficient inheritance” or “virtual structs”. In order to motivate and explain this design, I am writing a series of blog posts examining how Rust’s current abstractions compare with those found in other languages.

The way I see it, the topic of “virtual structs” has always had two somewhat orthogonal components to it. The first component is a question of how we can generalize and extend Rust enums to cover more scenarios. The second component is integrating virtual dispatch into this picture.

So there has been a lot of really interesting discussion in response to my blog post. I wanted to highlight some of the comments I’ve seen, because I think they raise good points that I failed to address in the blog post itself. My comments here are lightly edited versions of what I wrote elsewhere.

Isn’t the problem with objects and leak-safe types more general?

Reem writes:

I posit that this is in fact a problem with trait objects, not a problem with Leak; the exact same flaw pointed about in the blog post already applies to the existing OIBITs, Send, Sync, and Reflect. The decision of which OIBITs to include on any trait object is already a difficult one, and is a large reason why std strives to avoid trait objects as part of public types.

What’s a 1.0 release without a little drama? Recently, we discovered that there was an oversight in one of the standard library APIs that we had intended to stabilize. In particular, we recently added an API for scoped threads – that is, child threads which have access to the stack frame of their parent thread.

The flaw came about because, when designing the scoped threads API, we failed to consider the impact of resource leaks. Rust’s ownership model makes it somewhat hard to leak data, but not impossible. In particular, using reference-counted data, you can construct a cycle in the heap, in which case the components of that cycle may never be freed.

After reading nrc’s blog post about graphs, I felt inspired to write up an alternative way to code graphs in Rust, based on vectors and indicates. This encoding has certain advantages over using Rc and RefCell; in particular, I think it’s a closer fit to Rust’s ownership model. (Of course, it has disadvantages too.)

I’m going to describe a simplified version of the strategy that rustc uses internally. The actual code in Rustc is written in a somewhat dated “Rust dialect”. I’ve also put the sources to this blog post in their own GitHub repository. At some point, presumably when I come up with a snazzy name, I’ll probably put an extended version of this library up on crates.io. Anyway, the code I cover in this blog post is pared down to the bare essentials, and so it doesn’t support (e.g.) enumerating incoming edges to a node, or attach arbitrary data to nodes/edges, etc. It would be easy to extend it to support that sort of thing, however.

We’ve recently been doing a lot of work on Rust’s orphan rules, which are an important part of our system for guaranteeing trait coherence. The idea of trait coherence is that, given a trait and some set of types for its type parameters, there should be exactly one impl that applies. So if we think of the trait Show, we want to guarantee that if we have a trait reference like MyType : Show, we can uniquely identify a particular impl. (The alternative to coherence is to have some way for users to identify which impls are in scope at any time. It has its own complications; if you’re curious for more background on why we use coherence, you might find this rust-dev thread from a while back to be interesting reading.)

The so-called “unboxed closure” implementation in Rust has reached the point where it is time to start using it in the standard library. As a starting point, I have a pull request that removes proc from the language. I started on this because I thought it’d be easier than replacing closures, but it turns out that there are a few subtle points to this transition.

I am writing this blog post to explain what changes are in store and give guidance on how people can port existing code to stop using proc. This post is basically targeted Rust devs who want to adapt existing code, though it also covers the closure design in general.

There has been a lot of discussion lately about Rust’s allocator story, and in particular our relationship to jemalloc. I’ve been trying to catch up, and I wanted to try and summarize my understanding and explain for others what is going on. I am trying to be as factually precise in this post as possible. If you see a factual error, please do not hesitate to let me know.

The core tradeoff

The story begins, like all interesting design questions, with a trade-off. The problem with trade-offs is that neither side is 100% right. In this case, the trade-off has to do with two partial truths:

I’ve been working on a branch that implements both multidispatch (selecting the impl for a trait based on more than one input type) and conditional dispatch (selecting the impl for a trait based on where clauses). I wound up taking a direction that is slightly different from what is described in the trait reform RFC, and I wanted to take a chance to explain what I did and why. The main difference is that in the branch we move away from the crate concatenability property in exchange for better inference and less complexity.

A few weeks back pcwalton introduced a PR that aimed to move the attribute and macro syntax to use a leading @ sigil. This means that one would write macros like:

@format("SomeString: {}", 22)

or

@vec[1, 2, 3]

One would write attributes in the same way:

@deriving(Eq)
struct SomeStruct {
}

@inline
fn foo() { ... }

This proposal was controversial. This debate has been sitting for a week or so. I spent some time last week reading every single comment and I wanted to lay out my current thoughts.

While on vacation, I’ve been working on an alternate type inference scheme for rustc. (Actually, I got it 99% working on the plane, and have been slowly poking at it ever since.) This scheme simplifies the code of the type inferencer dramatically and (I think) helps to meet our intutions (as I will explain). It is however somewhat less flexible than the existing inference scheme, though all of rustc and all the libraries compile without any changes. The scheme will (I believe) make it much simpler to implement to proper one-way matching for traits (explained later).

I am on vacation for a few weeks. I wanted to take some time to jot down an idea that’s been bouncing around in my head. I plan to submit an RFC at some point on this topic, but not yet, so I thought I’d start out by writing a blog post. Also, my poor blog has been neglected for some time. Consider this a draft RFC. Some important details about references are omitted and will come in a follow-up blog post.

This post withdrawn: it was posted by accident and was incomplete.

+---+       +------+       +-----+
               ^
+---+          |
| & | ---------+
+---+

As you can see from the diagram, the &mut reference is a unique reference to the integer. That is, it can’t be copied, and it’s the only direct pointer to that integer. However, there are multiple paths to the &mut itself. That’s not the fault of the &mut, it’s just that uniqueness is a global property. In other words, if I have a variable p of type &&mut int, then **p is not a unique path, even though it traverses through a unique reference at some point.

Over time, I’ve become convinced that it would be better to drop the distinction between mutable and immutable local variables in Rust. Many people are highly skeptical, to say the least. I wanted to lay out my argument in public. I’ll give various motivations: a philosophical one, an eductional one, and a practical one, and also address the main defense of the current system. (Note: I considered submitting this as a Rust RFC, but decided that the tone was better suited to a blog post, and I don’t have the time to rewrite it now.)

In today’s Rust, there are a number of builtin traits (sometimes called “kinds”): Send, Freeze, Share, and Pod (in the future, perhaps Sized). These are expressed as traits, but they are quite unlike other traits in certain ways. One way is that they do not have any methods; instead, implementing a trait like Freeze indicates that the type has certain properties (defined below). The biggest difference, though, is that these traits are not implemented manually by users. Instead, the compiler decides automatically whether or not a type implements them based on the contents of the type.

Today, if you do a mutable borrow of a local variable, you lose the ability to write to that variable except through the new reference you just created:

let mut x = 3;
let p = &mut x;
x += 1;  // Error
*p += 1; // OK

However, you retain the ability to read the original variable:

let mut x = 3;
let p = &mut x;
print(x);  // OK
print(*p); // OK

I would like to change the borrow checker rules so that both writes and reads through the original path x are illegal while x is mutably borrowed. This change is not motivated by soundness, as I believe the current rules are sound. Rather, the motivation is that this change gives strong guarantees to the holder of an &mut pointer: at present, they can assume that an &mut referent will not be changed by anyone else. With this change, they can also assume that an &mut referent will not be read by anyone else. This enable more flexible borrowing rules and a more flexible kind of data parallelism API than what is possible today. It may also help to create more flexible rules around moves of borrowed data. As a side benefit, I personally think it also makes the borrow checker rules more consistent (mutable borrows mean original value is not usable during the mutable borrow, end of story). Let me lead with the motivation.

I have been working on making the borrow checker treat closures in a sound way. I hope to land this patch very soon. I want to describe the impact of these changes and summarize what we might do in the future.

The high-level idea

The basic idea is that the borrow checker will treat a closure as if it were constructing a record with one borrowed pointer for each variable mentioned in the closure.

I’ve been working on Issue #3511, which is an effort to rationalize the lifetimes of temporary values in Rust. This issue has been a thorn in the side of Rust users for a while, because the current lifetimes are rather haphazard and frequently too short. Some time ago, I did some thinking on this issue and then let it lie while other things took priority.

Part of the reason that this issue has lasted so long is that the current trans cleanup scheme is very inflexible. I have a branch now that rewrites the cleanup system so that it can handle any rules we would like. The problem I am encountering now, of course, is that it’s unclear what the rules should be. I want to lay out the options I see.

I believe I have come to the point where I am ready to make a final proposal for DST. Ironically, this proposal is quite similar to where I started, but somewhat more expansive. It seems to be one of those unusual cases where supporting more features actually makes things easier. Thanks to Eridius on IRC for pointing this out to me. I intend for this post to stand alone, so I’m going to start from the beginning in the description.

Over the Thanksgiving break I’ve been devoting a lot of time to thinking about DST and Rust’s approach to vector and object types. As before, this is very much still churning in my mind so I’m just going to toss out some semi-structured thoughts.

Brief recap

Treating vectors like any other container. Some time back, I wrote up a post about how we could treat vectors like any other container, which would (to some extent) avoid the need for DST.

In the previous post I elaborated a bit on DSTs and how they could be created and used. I want to look a bit now at an alternate way to support the combination of vector types and smart pointers (e.g., RC<[uint]>). This approach avoids the use of DSTs. We’ll see that it also addresses some of the rough patches of DST, but doesn’t work quite as well for object types.

After posting part 2 of my DST series, I realized that I had focusing too much on the pure “type system” aspect and ignoring some of the more…mundane semantics, and in particular the impact of monomorphization. I realize now that – without some further changes – we would not be able to compile and execute the second proposal (which I will dub statically sized typed (SST) from here on out). Let me first explain the problem and then show how my first thoughts on how it might be addressed.

In the past, I’ve been quite the champion of dynamically sized types (DST). Specifically what this means is that things like [T] and Trait would be “types” in the Rust type system. Lately I’ve been investing a lot of effort thinking through the ramifications of offering better support for smart pointers, and in particular how this interacts with dynamically sized types, and I am no longer persuaded that DST offer the best way forward. I’m a bit unsure, though, and the topic is complicated, so I wanted to stop and write up a short series of posts laying out my thought process thus far. This post will describe what it would mean to offer DST in more detail. I don’t plan to give a lot of Rust background, since there’s enough to talk about.

Alex Chrichton recently sent a message to the rust-dev mailing list discussing the fate of parameter coercion in Rust. I’ve been thinking about this for a while and feeling conflicted. As is my wont, I decided to try and write up a blog post explaining precisely what’s under debate and exporing the tradeoffs.

Historical background

In the interest of clarity, I wanted to briefly explain some terminology and precisely what the rules are. I refer to “autoref” as the addition of an implicit &: so converting from T to &T, in terms of the type. “Autoderef” is the addition of an implicit *: converting from &T, ~T, etc to T. Finally, “autoborrow” is the addition of both a & and a *, which effectively converts from ~T, &T etc to &T. “Autoslice” is the conversion from ~[..] and &[...] to &[...] – if we had a DST-based system, autoslice and autoborrow would be the same thing, but in today’s world they are not, and in fact there is no explicit syntax for slicing.

Some astute comments on a recent thread to rust-dev got me thinking about our approach to vectors. Until now, we have focused on having built-in support for vectors via the vector type (~[T]) and slice types (&[T]). However, another possible approach would be to move vector support out of the language (almost) entirely and into standard libraries. I wanted to write out a post exploring this idea; I find it brings some simplifications and reduces the need for DST. Seems like an idea worth considering. Consider this a thought experiment, not exactly a proposal.

I got a lot of feedback on my post about intermingled parameter lists – most of it negative – and I’ve been thinking about the issue over the weekend. Truth is, I wasn’t terribly fond of the proposal myself – making the position in the list significant feels wrong – but I felt it was the least bad of the various options. However, I’ve had a change of heart, and thus have a new “least bad” proposal.

I’ve been hard at work finishing up work on Rust’s “new” syntax for lifetimes – I put “new” in quotes because the syntax has been in use for some time, but in rustc itself the change was only half-baked. In effect, the new syntax was a kind of “bridge” to code that was designed for the older type system. This resulted in some artificial limitations: for example, types could only have a single lifetime parameter, and it had to be named 'self. Under my pull request, these limitations are lifted. However, in the process of implementing things, I realized one minor problem with the new syntax that must be rectified. In this post I describe the problem and my proposed solution.

There is a known bug with the borrowck rules that causes it to be overly permissive. The fix is relatively simple but it unfortunately affects some of our Iterator implementations, specifically those iterators that iterate over &mut values. The short version is that while it is possible to expose a safe interface for iterating over &mut values, it is not possible to implement such iterators without an unsafe block.

After giving this quite a bit of thought, I have come to the conclusion that we have three options:

The following is a draft proposal to support a form of single inheritance, similar to that found in object-oriented languages. The goal is to enable servo to efficiently support structures like the DOM. The proposal is not completely rounded out, but I wanted to put it up in its current form so as to gather any comments.

In a nutshell, the proposal is to:

1. Enable structs to extend other structs, meaning that the substruct inherits all fields of the superstruct, and also enabling a subtyping relationship between borrowed pointers.

As some of you may recall, the fate of function types in Rust has been somewhat uncertain. It all began when I realized that we could not soundly permit closures to recurse, which implies that closures must be tracked in a linear fashion. This caused interactions with the prior plans we had for dynamically sized types, and led to several alternative proposals. The most radical involved keeping only one closure type for borrowed closures and then using macros and object types to represent all other use cases.

Today I had the honor of giving a presentation on Rust at the Northeastern University PL Seminar. It was a lot of fun, and I also had a lot of good conversations afterwards with some of the professors and PhD students there. For those who are interested, I am uploading the slides from my talk. The talk takes the same approach that I would like to use for the next Rust paper. It was kind of a dry run to see if that approach would be understandable and would flow logically; overall, I thought it worked reasonably well.

Rust currently has very strong support for concurrency in the form of actors which exchange messages and do not share memory. However, there are many tasks for which actors are not a good fit. The unbounded lifetime of actors means that they cannot safely access stack-allocated memory from another task, even if it is immutable. Actors cannot share memory except through the relatively clumsy (and somewhat expensive) mechanism of Arc structures (which stands for “atomic reference count”), meaning that if there are large data structures they can be a pain to access. Arc is also inapplicable to data structures that transition between mutable and immutable and back again.

As I alluded in the previous post, I have noticed an interesting connection between memory management and data-race freedom. I want to take a moment to elaborate on this, becaause the connection was not obvious to me at first, but it ultimately drives a lot of the Rust design decisions.

First, I believe that if you want to guarantee data-race freedom, and you want to support the cheap transfer of mutable state between tasks, then you must have a garbage-collector-free subset of your language. To see what I mean by “cheap transfer of mutable state”, consider something like double-buffering: you have one drawing and one display task exchanging buffers (so there are only two buffers in total). While the drawing task is preparing the next frame, the display task is busy displaying the current one. At the end, they exchange buffers. In order to prevent data races in a scenario like this, it is vital that we be able to guarantee that when the buffers are exchanged, neither task has any remaining references. Otherwise, the display task would be able to read or write from the buffer that the drawing task is currently writing on.

So Ben Blum has doing some investigation into the full implications of the Sized bound that I proposed as part of the dynamically sized types post. It’s clear that, if we change nothing else, the impact of Sized will be somewhat greater than I thought. He estimates somewhere around 40% of the files in libstd need at least one Sized bound; the actual number may wind up being somewhat higher.

It is not entirely clear to me if this is a problem. I imagine that the number of Sized bounds will be highest in container and other library code. But it is worse than I hoped. So I wanted to briefly explore some of the alternatives, assuming that the Sized annotation burden is too high.

I have been thinking about my previous proposal for fn types. I wanted to offer some refinements and further thoughts.

On Thunks

I proposed a trait Task for encapsulating a function and the parameters it needs to run. I don’t like this name because this concept could be used in other places beyond just tasks. I was thinking that the proper name is probably Thunk. I quote Wikipedia for the definition of Thunk: “In computer science, a thunk (also suspension, suspended computation or delayed computation) is a parameterless closure created to prevent the evaluation of an expression until forced at a later time.” (There are, admittedly, other contrary uses for the term)

I’ve been thinking more about my proposal to split the current fn type into fn and proc. I have come to the conclusion that we just don’t need proc at all. I think we can get by with two types:

1. fn(S) -> T: closures that always reference an enclosing scope
2. extern "ABI" fn(S) -> t: raw function pointer, no environment

Code that uses @fn or ~fn today could be rewritten to either use a boxed trait or to use a pair of a user-data struct and an extern fn.

So, I didn’t actually mean to post that previous post, I had intended to think more on the idea. But oh well, cat’s out of the bag. In any case, I’ve been thinking about the “closures” vs “procedures” idea that I jotted down there and decided to try and elaborate on it a bit more, since I find it has a lot of appeal. In particular I think that the current collection of closure types is addressing too many distinct use cases and the result is confusing.

I’ve been thinking about what I wrote in my last post regarding closures and I am beginning to change my opinion about the correct solution. fn~ just seems so unfortunate. So, besides writing fn~, what are the other options? I just thought I’d write down a few of the other ideas I’ve come up with for later reference. Not saying any of the ideas in this post are good yet.

I realized today that there is an unfortunate interaction between the proposal for dynamically sized types and closure types. In particular, in the case of the recurring closure, I described the soundness issues that arise in our language when closures are able to recurse.

My solution for this was to make the type system treat a &fn() value the same way it treats &mut T pointers: they would be non-copyable, and when you invoke them, that would be effectively like a “mutable borrow”, meaning that for the duration of the call the original value would become inaccessible. So in short the type system would guarantee that when you call a closure, that same closure is not accessible from any other path in the system, just as we now guarantee that when you mutate a value, that same value is not accessible from any other path in the system.

Recently, separate discussions with pnkfelix and graydon have prompted me to think a bit about “dynamically sized types” once again. Those who know Rust well know all about the sometimes annoying discrepancy between a type like ~T (owned pointer to T) and ~[S] (owned vector of S instances)—in particular, despite the visual similarity, there is no type [S], so ~[S] is not an instance of ~T for any T. This design was the outcome of a lot of back-and-forth and I think it has generally served us well, but I’ve always had this nagging feeling that we can do better. Recently it occurred to me how we could, though it’s not without its price.

Yesterday I realized that you can violate Rust’s memory safety guarantees by using “stack closures”, meaning closures that are allocated on the stack which have can refer to and manipulate the local variables of the enclosing stack frame. Such closures are ubiquitous in Rust, since every for loop makes use of them (and virtually every higher-order function). Luckily, this hole can be fixed with (I think) very little pain—in fact, I think fixing it can also help us make other analyses a little less strict.

While working on issue #5656 I encountered an interesting problem that I had not anticipated. The result is a neat little extension to the region type system that increases its expressive power. The change is completely internal to the type rules and involves no user-visible syntax or anything like that, though there are some (basically nonsensical) programs that will no longer compile. Anyway I found it interesting and thought I would share.

I want to finish my discussion of associated items by taking a look at how they are handled in Haskell, and what that might mean in Rust.

These proposals have the same descriptive power as what I described before, but they are backwards compatible. This is nice.

Object-oriented style name resolution

In the object-oriented, C++-like version of associated items that I introduced before, the names of associated items and methods were resolved relative to a type. To see what I mean by this, consider a (slightly expanded) variant the graph example I introduced before:

I’ve been doing a lot of thinking about Rust’s trait system lately. The current system is a bit uneven: it offers a lot of power, but the implementation is inconsistent and incomplete, and in some cases we haven’t thought hard enough about precisely what should be allowed and what should not. I’m going to write a series of posts looking at various aspects of the trait system and trying to suss out what we should be doing in each case. In particular I want to be sure that our trait design is forwards compatible: that is, I expect that we will defer final decisions about various aspects of the trait system until after 1.0, but we should look now and try to anticipate any future difficulties we may encounter.

One of the things that I’ve been working on for some time now is the proper integration of C functions. As with virtually every other facet of the design of Rust, we’ve been slowly moving from a model where Rust tried to hide low-level details for you to one where Rust offers tight control over what’s going on, with the type system intervening only as needed to prevent segfaults or other strange behavior. This blog post details what I consider to be the best proposal so far; some of the finer points are a bit vague, however.

Rust features destructors and, as of this moment, they are simply not sound with respect to many other features of the language, such as borrowed and managed pointers. The problem is that destructors are granted unlimited access to arbitrary data, but the type system and runtime do not take that into account. I propose to fix this by limiting destructors to owned types, meaning types that don’t contain borrowed or managed pointers.

In Rust today, there is a special for syntax designed to support interruptible loops. Since we introduced it, this has proven to be a remarkable success. However, I think we can improve it very slightly.

Current for protocol

The current “for protocol” is best explained by giving an example of how to implement it for slices:

fn each<E>(v: &[E], f: &fn(&E) -> bool) {
    let mut i = 0;
    let n = v.len();
    while i < n {
        if !f(&v[i]) {
            return;
        }
        i += 1
    }
}

As you can see, the idea is that the last parameter to the each() method is a function of type &fn(&E) -> bool, which means that it is given a pointer to an element in the collection and it returns true or false. The return value indicates whether we should continue iterating.

In a previous post I outlined some of the options for updating our lifetime syntax. I want to revist those examples after having given the matter more thought, and also after some discussions in the comments and on IRC.

My newest proposal is that we use <> to designate lifetime parameters on types and we lean on semantic analysis (the resolve pass, more precisely) to handle the ambiguity between a lifetime name and a type name. Before I always wanted to have the distinction between lifetimes and types be made in the parser itself, but I think this is untenable. This proposal has the advantage that the most common cases are still written as they are today.

I’ve been thinking for a while that our lifetime notation has too many defaults which can be more confusing than helpful. A recent spate of e-mails on rust-dev brought this back to my mind. I’ve been wanting to take a look at these defaults for a while, so I thought I’d write up a quick exploration of the “syntactic space”. A warning: this is not really an exciting post to read. I hope to have a few of those coming up very soon. This one is mostly just a list of syntactic options I wanted to document for future reference and to serve as a starting point for discussion.

I’ve been thinking of a radical change we could make to the treatment of mutability and borrowed pointers in Rust. The goal is to eliminate all of the error messages about “aliasable, mutable data” that the borrow checker currently issues. The idea is somewhat inspired by writing a recent paper on Rust’s current system—writing a paper on something never fails to get me thinking about how to improve it, though it sometimes fails to stimulate ideas which are actually good—and also somewhat inspired by recent conversations on IRC and in person.

I am considering whether we should add a way to borrow something but retain uniqueness. This would address a shortcoming of the borrowing system that has been bothering me for some time, and it would enable a few patterns that are difficult or awkward today.

The Problem

I described the problem in this paper review I wrote, but I will repeat it here, because it’s relevant, and perhaps people don’t read and remember every single word that I write. In our system, a ~T type is always owned. So if you write:

My big goal for 0.5 is to straighten out our function types (yet again). I’ve been tossing the design for these over in my head since the summer and I wanted to lay out my plan. This is a variation of something that Ben Blum and I sketched out on a whiteboard.

Closure type

The closure type will be described something like so. Beware, it’s got a lot of options. It turns out that there is a very large variety of things one might want to use closures for, and supporting them requires a fair number of knobs. I believe that in practice there will be a smallish set of standard forms (I’ll describe those later). In any case, this is the closure type in its full generality, with annotations:

In this post I propose an extension of Rust’s purity rules. The short version is that pure functions would be allowed to mutate data owned by their &mut parameters. This extends the current Rust purity rules which allow pure functions to invoke impure closures so long as they are an argument to the function. The principle is the same: pure functions are functions whose side-effects can be completely determined by examining their parameters (for the more formally minded among you, this is effectively an effect-parametric system with very lightweight notation). The rest of the post is an elaboration and justification of this idea.

So, the condition that was supposed to ensure termination in my previous post is most certainly wrong. The idea was to prevent tautological impls like the following:

impl<A: Foo> A: Foo { ... }

Such impls, given a naive algorithm, would loop infinitely trying to decide if a type T implemented Foo. You can imagine: it would ask, “does T implement Foo? Well, if I map A to T then this impl applies, but only if T implements Foo. Hmm. That puts me back where I started from. Oh well, better try it again!” Obviously a less naive algorithm could keep a stack and then fail to execute, but it was precisely the logic of this stack that I was trying to capture in that restriction.

I was thinking more about type classes as I walked down the street. In my prior post I wrote that the rules I proposed resulted in a system where traits loosely fit the following Haskell template:

 class C self a ... z | self -> a ... z where ...

However, I gave two caveats. The first was that due to subtyping we cannot say that one type precisely determines another, but only that it puts a bound. The second was that, in any given impl, the value of a ... z may be a type parameter which does not appear in the self type. I think I understated the importance of this second caveat. For example, consider the example I gave for simulating overloading:

Currently, the Rust compiler accepts all manner of trait, impl, and bound declarations. In fact, it accepts plenty of declarations that later phases of the compiler are not sophisticated enough to handle. In other words, the syntax is writing checks the semantics can’t cash. (An aside: I just love saying that phrase for some perverse reason. I really wish however that checks, like rotary dial telephones, were something that younger people vaguely understood but which no longer had relevance in the modern era. The Swiss Einzahlungschein truly opened my eyes! Anyhow.)

I have been trying to come up with a reasonable set of rules for deciding when a pattern binding ought to be a move and when it ought to be a copy and utterly failing. Simultaneously, pcwalton, brson, and I kind of simultaneously arrived at an alternate design that tries to simplify the copy/move distinction. I think that it also solves the question of when to copy/move pattern bindings in a nice way. Therefore, I wanted to write up this proposal.

We need to clarify our story on rvalue lifetimes. This is related to issue #3387 and also various recent and not-so-recent discussions on IRC.

The basic question is how long an rvalue lives when the program creates pointers into it. To understand the rough issues, first consider this program:

let x = foo();
match x {
    Some(ref y) => {...}
    None => {...}
}

Here, the result of foo() is stored into a local variable. The match clause then creates a pointer to the interior of this local variable (i.e., into the stack) called y. But what if we eliminated the variable x:

One of the things that is sometimes frustrating in Rust is the inability to define a type that indicates some subset of enum variants. For example, it is very common to have a pattern like this:

match an_expr {
    expr_call(*) => process_call(an_expr)
    ...
}

fn process_call(a_call_expr: @ast::expr) { ... }

But as you can see, the type of a_call_expr does not reflect the fact that this expression is a call. This is frustrating.

I have been working on a change to the definition of mutability in Rust. This is a much smaller change than my previous thought experiments, which were aimed at achieving better parameterization (those are still percolating; I think the best approach is a modified version of the latest proposal where not all types have mutability but type parameters do…but that’s a problem for another day with many complications). The goal of these changes is to enable operations like “freeze” and “thaw”.

Here is my latest stab at a tutorial on borrowed pointers. I know, I know, enough with the borrowed pointer tutorials already! Hopefully this will be my last post in this vein for a while. I am much happier with this version. It is still too long to serve as a chapter in the general Rust tutorial, but I think it’s more approachable than the previous attempt, which was more of a reference document. As always, feedback welcome! I have tried to incorporate what people wrote in the comments into this version.

One thing I didn’t make clear regarding my last post: I am not especially satisfied with the way the “tutorial” was turning out. I use scare quotes here because I think it resembles a reference manual more than a tutorial. Nonetheless I think there are some sections that are quite good; and a document like it probably ought to exist. So I figured I’d post it anyhow and I can mine it for material later. I intend to start afresh however with something that dives at the core ideas, which I think are relatively simple.

Here is a (much) more complete draft of the tutorial on borrowed pointers. It is becoming more in-depth than I intended. I hope to later extract a much shorter subset. But I thought I’d post what I’ve got so far.

Borrowed pointers

Borrowed pointers are one of the more flexible and powerful tools available in Rust. A borrowed pointer can be used to point anywhere: into the shared and exchange heaps, into the stack, and even into the interior of another data structure. With regard to flexibility, it is comparable to a C pointer or C++ reference. However, unlike C and C++, the Rust compiler includes special checks that ensure that borrowed pointers are being used safely. Another advantage of borrowed pointers is that they are invisible to the garbage collector, so working with borrowed pointers helps keep things efficient.

I had a very interesting discussion with Sriram and Terrence (of Kilim and ANTLR fame, respectively—two smart dudes) yesterday. One of the things we talked about was adapting shared-memory data structures like concurrent hash maps into an actor setting.

One thing we’ve found when working on Servo is that the temptation to cheat is enormous. Most of the papers you read about things like parallel layout just assume a shared memory setting and blithely make use of data strutures like concurrent hash maps. There is nothing wrong with such data structures, but if we can avoid shared, mutable memory it will go a long way towards avoiding bugs I think—as well as keeping things secure. Even if the bug is mostly correct, data races and similar subtle errors can open holes for exploitation.

I am trying to mop up some of the remaining work for regions now. One of the big remaining areas is dealing with function and iface types. This proposal is certainly influenced by my previous proposals. However, we have backed away from the idea of dynamically-sized types for vectors and so I will do the same here.

The design

My current design includes the following kinds of function types (written as I expect them to commonly be written; some details are omitted):

This is a draft of (the first section of) a new Rust tutorial on borrowed pointers (the official name for “regions”). Comments welcome.

UPDATE: I added a section “Why borrowed?”

Borrowed pointers

Borrowed pointers are one of the more flexible and powerful tools available in Rust. A borrowed pointer can be used to point anywhere: into the shared and exchange heaps, into the stack, and even into the interior of another data structure. With regard to flexibility, it is comparable to a C pointer or C++ reference. However, unlike C and C++, the Rust compiler includes special checks that ensure that borrowed pointers are being used safely. We have done our best to ensure that these checks mostly occur behind the scenes; but to get the most out of the system, you will have to understand a bit about how the compiler reasons about your program.

This is a proposal to unify the mechanics of alt and destructuring assignment. It was born out of discussion between erickt, pcwalton, and I amidst various bugs in the bug tracker but I wanted to float it around to a larger audience. I’d like to discuss this on Tuesday, because one of the logical next steps for the regions work is to begin deciding precisely what to do about the types of identifiers in alts.

OK, I’ve been thinking more about the mutability issue and I think I have found a formulation that I am happy with. The basic idea is that we refactor types like so:

T = M T
  | X
  | @T
  | ~T
  | [T]
  | {(f:T)*}
  | int
  | uint
  | ...
M = mut | const | imm

This no doubt looks similar to some of my other permutations. The key difference is that before I separated qualified and unqualified types. This was intended to aid with inference, but in fact it was getting me into trouble. I realize now there is a different way to solve the inference problem. But first let me back and explain what inference problem I am concerned about.

I have been thinking a bit more about the approach to mutability I recently discussed. It seemed a bit too good to be true (too clean) and I think I’ve realized a problem.

The problem derives from my definition of types:

T = Q U
Q = mut | const | imm
U = [T]
  | @T
  | &T
  | { (f : T)* }
  | X
  | int
  | uint
  | ...

The interesting case is that of a type variable, denoted as X. I grouped type variables under the heading of “unqualified types”. But this is of course incorrect, they are not unqualified types. They can map to a qualified type (in fact, that’s the whole point of this exercise). So really the hierarchy ought to be:

Currently, Rust has an effect system but refuses to admit it. In an effort to broaden the set of things that can be safely done in the face of extant aliases into the heap, I have been experimenting with a lightweight extension to Rust’s system. So far I think it is promising but also no magic bullet.

Background

For those who aren’t familiar with the term, an “effect system” is basically just a fancy name for tagging functions with some extra information beyond the types of their arguments and their return type.

I am dissatisfied with how mutability is treated in the Rust type system. The current system is that a type is not prefixed mutable; rather, lvalues are. That is, a type T is defined like so:

T = [M T]
  | @ M T
  | & M T
  | { (M f : T)* }
  | int
  | uint
  | ...
M = mut | const | (imm)

Note that there is no type mut int (a mutable integer). This is logical enough; such a type has little inherent meaning: an integer is a value, it is not mutable or immutable.

I wanted to bring together the various ideas around vectors and function types into one post. The goals of these changes are

1. to achieve orthogonality of the pointer types, so that leading &, @, and ~ sigils are the only way to indicate the kind of pointer that is in use;
2. to help pare down on the proliferation of subtle variantions on types, such as the 5 different function types currently available.

The proposal

The Rust type system would be described by the following grammar. In this grammar, I have included all optional portions except for region bounds. I indicated those types which could have a lifetime bound associated with them by writing (/&r) in the description (a lifetime bound indicates the lifetime of any pointers embedded within the type itself; this is not related to the changes I am discussing here so I won’t go into detail):

Yesterday I wrote about my scheme for paring down our set of function types to one type, fn:kind(S) -> T. When I finished writing the post, I was feeling somewhat uncertain about the merits of the idea, but I’m feeling somewhat better about it today. I really like the idea that top-level items have the type fn:kind(S) -> T and that you therefore give them an explicit sigil to use them in an expression; this allows us to remove the “bare function” type altogether without any complex hacks in the inference scheme.

As you loyal readers know, I am on a quest to make the Rust type system more orthogonal with respect to the kind of pointer in use, by which I mean that I want to have the three pointer sigils (@, &, and ~) indicate where memory is located and the other types indicate what value is to be found at that memory. Right now there are a few cases where we conflate the two things into one type. The first, vectors and slices, I discused in a recent post. This post discusses the second case: function and interface types.

I implemented a simple, non-flow-sensitive version of the reference checker which I described in my previous post. Of course it does not accept the Rust codebase; however, the lack of flow-sensitivity is not the problem, but rather our extensive use of unique vectors. I thought I’d write a post first showing the problem that you run into and then the various options for solving it.

Errors

The single most common error involves vec:len(). There are many variations, but mostly it boils down to code code like this, taken from the io package:

I’ve been working for the last few days on the proper safety conditions for borrowing. I am coming into a situation where I am not sure what would be the best approach. The question boils down to how coarse-grained and approximate our algorithm ought to be: in particular, ought it to be flow sensitive? But let me back up a bit, first, and provide a bit of background.

Background

Rust bucks the “new language” trend by not having a purely garbage-collected model. We feature things like interior and unique types which can be eagerly overwritten. This means that we have to be very careful when we create temporary references to those kinds of values that these references remain valid.

I’m still thinking about vector and string types in Rust and I think I’ve decided what I feel is the best approach. I thought I’d summarize it here and make the case for it. If you don’t know what I’m talking about, see this post for more background. I’ll forward this to the mailing list as well; I’m sorry if it seems like I’m harping on this issue. I just think vectors and strings are kind of central data structures so we want them to be as nice as possible, both in terms of what you can do with them and in terms of the notations we use to work with them.

I want to do an introduction to the regions system I’ve been working on. This is work-in-progress, so some of the details are likely to change. Also, I’m going to try some new terminology on for size: although it has a long history in the literature, I think the term “region” is not particularly accurate, so I am going to use the term “lifetime” or “pointer lifetime” and see how it fits.

After my recent dalliance in Matters of a Truly Trivial Nature, I’d like to return to Matters Most Deep and Profound. I’m running up against an interesting question with regions that has to do with the nature of function types like fn(&int): up until now, I’ve assumed that this refers to a function that takes an integer pointer in some region that is specified by the caller. That is, it is a kind of shorthand for a type that might be written like fn<r>(&r.int), where the <r> indicates that the function type is parameterized by the region r.

We’ve been discussing a lot about how to manage vectors and strings in Rust. Graydon sent out an excellent proposal which allows for a great number of use cases to be elegant handled. However, I find the syntax somewhat misleading. I’ve proposed one alternative on the mailing list, but I now find I don’t like it, so I thought I’d brainstorm a bit and try to find something better.

There are really three use cases:

One of the questions in our object system is what precisely how “declared” we want things to be when it comes to interfaces and implementations. In a discussion on IRC, graydon suggested it’d be nice to have terms like “duck-typing” defined more precisely in a Rust syntax, and he is correct. So here is my effort.

The current setup

Currently, implementations must declare precisely what types they implement. For example, it looks like this:

On the rust-dev mailing list, someone pointed out another “BitC retrospective” post by Jonathon Shapiro concerning typeclasses. The Rust object system provides interesting solutions to some of the problems he raises. We also manage to combine traditional class-oriented OOP with Haskell’s type classes in a way that feels seamless to me. I thought I would describe the object system as I see it in a post. However, it turns out that this will take me far too long to fit into a single blog post, so I’m going to do a series. This first one just describes the basics.

First off, I want to welcome Brian Anderson to the Rust blog-o-sphere (which so far consists primarily of myself). His first post does a great job of explaining how to use the new for syntax that was recently added to Rust: this syntax allows for break, ret, and cont from within user-defined loops, which is very nice.

Reading some of the Hacker News comments (this one in particular), I wanted to clarify one thing. There is some concern that this new syntax changes the semantics of ret when, in fact, it aims to do precisely the opposite.

pcwalton and I (but mostly pcwalton) have been hard at work implementing regions in Rust. We are hoping to use regions to avoid a lot of memory allocation overhead in the compiler—the idea is to use memory pools (a.k.a. arenas) so that we can cheaply allocate the data needed to process a given function and then release it all in one shot. It is well known that arenas are great fit for the memory allocation patterns of a compiler, which tend to produce a lot of data that lives for the duration of a pass but is not needed afterwards.

Cross-crate inlining has come a long way and is now basically functional (I have yet to write a comprehensive test suite, so I’m sure it will fail when exercising various corners of the language).

Just for fun, I did some preliminary micro-benchmarks. The results are not that surprising: removing method call overhead makes programs run faster! But it’s still nice to see things go faster. We’ll look at the benchmarks, see the results, and then dive into the generated assembly. In all cases, I found LLVM doing optimizations that rather surprised me.

My current implementation of the auto-serialization code generator requires full type information. This is a drag. First, macros and syntax extension currently run before the type checker, so requiring full type information prevents the auto-serialization code from being implemented in the compiler, as it should be. At first I wanted to change how the compiler works to provide type information, but after numerous discussions with pcwalton and dherman, I’ve come to the conclusion that this is a bad idea: it requires exposing an API for the AST and for type information and introduces numerous other complications.

In the last few posts I’ve been discussing various options for regions. I’ve come to see region support as a kind of continuum, where the current system of reference modes lies at one end and a full-blown region system with explicit parameterized types and user-defined memory pools lies at the other. In between there are various options. To better explore these tradeoffs, I wrote up a document that outlines various possible schemes and also details use cases that are enabled by these schemes. I don’t claim this to be a comprehensive list of all possible schemes, just the ones I’ve thought about so far. In some cases, the descriptions are quite hand-wavy. I also think some of them don’t hang together so well.

Marijn pointed out to me that our current setup should avoid the worst of the versioning problems I was afraid of. In the snapshot, we package up a copy of the compiler along with its associated libraries, and use this compiler to produce the new compiler. The new compiler can then compilers its own target libraries, thus avoiding the need to interact with libraries produced by the snapshot.

Of course, I should have known this, since I have relied on this so that I can changed the metadata format without worrying about backwards compatibility. That’s what I get for writing blog posts late at night.

I’ve been busily implementing the Cross-Crate Inlining stuff, but one area I haven’t looked at much is versioning. In particular, if we are going to be serializing the AST, we need a plan for what to do when the AST changes. Actually, if inlining were only to be used for performance, we wouldn’t really need to have a plan: we could just not inline when the AST appeared to be stored in some form we don’t understand. However, if we fully monomorphize, we will not have that luxury: without type descriptors, the only way to compile cross-crate, generic calls will be by inlining.

One commonly requested feature for regions is the ability to return references to the inside of structures. I did not allow that in the proposal in my previous post because I did not want to have any region annotations beyond a simple &. I think, however, that if you want to allow returning references to the interior of a parameter, you need a way for the user to denote region names explicitly.

I was talking to brson today about the possibility of moving Rust to a regions system. He pointed out that the complexity costs may be high. I was trying to make a slimmer version where explicit region names were never required. This is what I came up with. The truth is, it’s not that different from the original: adding back region names wouldn’t change much. But I’m posting it anyway because it includes a description of how to handle regions in types and I think it’s the most complete and correct proposal at the moment.

Brian pointed out to me a nice solution to the Task API problem that I have overlooked, though it’s fairly obvious. Basically, I had rejected a “builder” style API for tasks because there is often a need for the child task to be able to send some data back to its parent after it has been spawned, and a builder API cannot easily accommodate this. Brian’s idea was to encapsulate these using futures. It’s still not perfect but it’s better I think and more composable than my first, limited proposal. It still requires that the actor pattern be a separate module.

One of the thorny API problems I’ve been thinking about lately is the task API for Rust. I originally had in mind this fancy and very flexible aproach based on bind. When I spelled it out I found it was very powerful and flexible but also completely unworkable in practice.

So here is a more limited proposal. There is a core task API that looks something like this:

enum task = uint; // wrap the task ID or whatever
type opts = { ... };

fn default_opts() -> opts;

fn spawn(opts: opts, body: fn~()) -> task;

The options struct will let you control simple things like stack size and so forth.

I’ve been working on implementing Cross-Crate Inlining. The major task here is to serialize the AST. This is conceptually trivial but in practice a major pain. It’s an interesting fact that the more tightly you type your data, the more of a pain it (generally) is to work with in a generic fashion. Of functional-ish languages that I’ve used, Scala actually makes things relatively easy by using a combination of reflection and dynamic typing (interfaces like Product come to mind).

One of the things I’d like to do for the iteration library is settle on a convention for breaking and continuing within loops. There is a bug on this issue (#1619) and it seems like the general approach is clear but some of the particulars are less so. So I thought I’d try to enumerate how code will look under the various alternatives and then maybe we can settle on one: they’re all fairly similar. Who knows, maybe just writing things out will settle my mind.

Cross-crate inlining (CCI) refers to the ability to inline a function across crate boundaries. In Rust, a “crate” is the unit of compilation, rather than an individual file as in C or C++. A crate basically corresponds to a single library or executable, but it may contain any number of modules and source files internally. CCI is important for performance due to the ubiquitous use of small methods like vec::iter() in our source code. Such methods have proven to be a very scalable way to define iteration abstracts, but performance is currently somewhat lacking.

It’s been a while since I wrote anything on the blog! A lot has been going on in the meantime, both in Rust, parallel JavaScript, and personally…I hate to write a big update post but I gotta’ catch up somehow!

Rust

First, we made our 0.1 release, which is great. We are now planning for 0.2. The goal is to make frequent, relatively regular releases. We’re still in such an early phase that it doesn’t seem to make sense to literally release every few months, but at the same time we don’t plan to wait long.

UPDATE: I found some more complications. Updates inline.

I have been working on and off on allowing block sugar to appear in Rust expressions and not only statements. For those who do not know what I am talking about, let me give a bit of context. At the moment, one can write the following in Rust:

vec::iter(v) { |e| 
   ...
}

which is sugar for the function call:

vec::iter(v, { |e| 
   ...
})

Objectively, there isn’t much difference between the two, but somehow pulling the {||} out of the parentheses feels much lighter to me.

The original Rust design included iterators very similar to Python’s generators. As I understand it, these were stripped out in favor of Ruby-esque blocks, partially because nobody could agree on the best way to implement iterators. I like blocks, but it seems like it’s more natural to compose iterators, so I wanted to think a bit about how one might use blocks to achieve similar things. I’m sure this is nothing new; there must be hundreds of libraries in Haskell that do the same things I’m talking about here.

So, I worry that my various posts about Rust give the impression that I’m dissatisfied with the language. It’s true that there are several things I’d like to change—and those are what I’ve focused on—but I want to clarify that I quite like Rust the way it is and I find the overall feel of the language to be very good. When it comes to the big decisions, I think Rust gets it right:

I landed a preliminary version of unique closures (which I am currently calling sendable fns) on the trunk last night. I wanted to briefly document what I did to alter the design of closures to get this working (of course there is a comment in the code too, but who reads that?).

Closures in Rust are represented as two words. The first is the function pointer and the second is a pointer to the closure, which is the captured environment that stores the data that was closed over. Because of how Rust is implemented, the closure must also store any type descriptors that were in scope at the point where the closure was created.

I keep thinking about parallel blocks although I know I probably shouldn’t; but so long as I write these notes while rustc builds, everybody wins, right?

Anyhow, pcwalton and dherman yesterday pointed out to me that const is not exactly one of the most beloved features of C++: “const-ification” is no fun, and if we’re not careful, Rust could walk right down that path. To some extent my reaction is, “Well, something’s gotta’ give.” You can’t have modular static race freedom without some way to know what function will write what. But nonetheless they are quite correct.

On a call with other Rust developers, I realized that I was thinking about unique closures all wrong. I had in mind a total ordering:

fn[send] <: fn <: block

but of course this is not necessary. What is desirable is a partial ordering:

fn[send] <: block
fn <: block

just as ~ and @ pointers can both be aliased using a reference. Ironically, this is precisely what I proposed in my list of possible solutions, but I did so using region terminology. Embarrassingly obvious, in retrospect, particularly as that was Graydon’s original design I believe. I think I got confused by the total ordering of kinds into thinking that this should translate to a total ordering of functions that close over data in those kinds. Anyhow, I will now work on implementing unique closures in this partially ordered way, and hopefully things will go more smoothly!

Update: See the recent post addressing the solution to this problem.

I have been trying to implement unique closures—or sendable functions, as I prefer to call them—but I realized that there is a fundamental problem that I hadn’t thought of before. The problem stems from two contradictory design goals:

• Sendable functions should be movable to another task without copying
• The various function types should have a subtyping relationship

The first requirement really demands that the sendable function’s environment be stored with a unique pointer. Otherwise multiple threads could share access to the same mutable state. Uncool.

I’ve been thinking a lot about “parallel blocks” recently and I am beginning to think they can be made to work very simply. The main thing that is needed is a type qualifier const that means “read-only”. This would be a type prefix with very low precedence, just like immutable and shared in D. The type const T would refer to an instance of T that cannot be modified. This is a deep property, so, given some record types defined like:

One of the last remaining tasks for Rust 0.1 is to find a way to address issues #1128 and #1038. The key problem is that, right now, we can only spawn a task with a bare function, which is to say a function that carries no closure or environment. Due to the way that Rust is implemented, this even excludes generic functions. I have been wanting to lift this restriction but have been stymied by trying to make it accessible.

Marijn asked me what it is that I dislike about parameter modes. I thought I might as well explain here.

For background, today in Rust a function can declare each parameter in one of several modes:

• By value (++): No pointer is used but the value is not owned by the callee. Therefore, the callee does not need to free it, for example, or decrement a ref count.
• By immutable reference (&&): a pointer to the variable in the caller’s stack frame is passed, but the callee cannot use it to make changes. Can be passed an lvalue or an rvalue.
• By mutable reference (&): a pointer to the variable in the caller’s stack frame is passed, and the callee can use it to reassign the variable. Can only be passed an lvalue.
• By copy (+): A fresh copy of the value is created and the callee must dispose of it.
• By move (-): The value is moved from the caller’s stack frame and the callee must dispose of it.

So what don’t I like about modes?

I recently implemented a new hashtable module for Rust. This was actually the first piece of code written in Rust which I started from scratch. I ran into some difficulties. Some of these are just things you have to get used to; some might be worth trying to correct. Just not entirely sure which problem falls into which category yet.

Cyclic types

Due to Rust’s structural types, types cannot reference themselves. In the hashtable module I was defining, I wanted a linked list of entries. In C I would write something like:

I have been thinking about unique closures, one of the last blocker items for the Rust 0.1 release. The original idea of a unique closure was that it should be a closure that can only access uniquely owned state, and which can therefore be sent to other tasks. However, I’ve come to have my doubts about this idea. In particular, a unique closure, like any closure, is a function, and can therefore be invoked many times: but this imposes some limits on what such a closure can safely do.

The primary means of parallel programming in Rust is tasks. Our task support is good: as good or better than any other language I’ve seen (good support for unique types and unique closures) but we have virtually no support for intra-task parallelism. The classic example is iterating over an array and processing each element in parallel. To be fair, this is a hard problem.

For my PhD, I worked on a language called Harmonic. Harmonic had a lot of ideas which I—naturally enough—really like, but most of them are probably not appropriate for Rust, as they leaned heavily on a complex, dependent type system. Some of them, however, might apply. In fact, thanks to unique pointers and interior types, it might be possible to make the Rust version even more expressive than the original.

I just posted a draft of a proposal for Rust that aims to eliminate implicit copies. At the moment, it is not the final version; there are some flaws I need to correct. For one thing, I need to address implicit capturing of variables by lambdas.

From the introduction:

This is a proposal for Rust whose purpose is to eliminate implicit copies of aggregate types, while preserving most other aspects of the language. Secondary goals include: