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:

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.

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.

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:

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 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.