Non-Lexical Lifetimes in Rust

http://smallcultfollowing.com/babysteps/blog/2016/04/27/non-lexical-lifetimes-introduction/

by kibwen • 10 years ago

135 58 10 years ago

kibwen7• 10 years ago

Short background: in today's Rust, the lifetime of a reference is bound to a lexical scope. Sometimes this forces one to create temporary variables solely to change the lexical scope of a reference, which is an annoyance. Take the following example:

    let mut nums = Vec::new();
    nums.push(nums.len());

The above code would compile if we had non-lexical lifetimes, but today it doesn't. This is because method calls are effectively desugared to something like this:

    let mut nums = Vec::new();
    Vec::push(&mut nums, nums.len());

The arguments are evaluated left-to-right, and the mutable borrow prevents the immutable borrow later. Once non-lexical lifetimes arrives this will be possible thanks to control-flow analysis, but today we have to make a temporary:

    let mut nums = Vec::new();
    let length = nums.len();
    nums.push(length);

It doesn't involve any new user-facing features to the language and is fully backward-compatible, so it's basically just a straight quality-of-life improvement for Rust programmers.

untothebreach• 10 years ago

My understanding was that implementing this is dependent on MIR fully landing, is that correct?

steveklabnik5• 10 years ago

In an extremely strict sense, no, but in reality yes. MIR makes it so much easier to implement a feature like this that we will wait for it before adding this.

eridius4• 10 years ago

I'm not quite sure how non-lexical lifetimes is supposed to fix this issue. Control-flow analysis doesn't change the fact that the arguments are evaluated in left-to-right order, and it doesn't change the fact that the &mut reference is created prior to the method arguments being evaluated and lives until the method itself is invoked. Control flow analysis will simply confirm the fact that the &mut borrow exists while the arguments are evaluated.

What might fix this is a special-case rule where an implicit¹ & or &mut reference as a method receiver is temporarily ignored while the arguments are being evaluated (with the borrow checker double-checking after the arguments are evaluated that the & or &mut reference is still legal, i.e. that the referenced value wasn't moved and, in the case of a &mut reference, that no other borrow exists as a result of evaluating the arguments). This rule, being a special case, doesn't require non-lexical lifetimes.

¹I say implicit because it would be potentially confusing for an explicit reference to be ignored while the arguments are evaluated.

webkike• 10 years ago

My guess is that if a mutable reference dominates the lifetimes of all its borrows, then an exception to the rule can be made.

kibwen7• 10 years ago

You're correct in that I was painting with too broad a stroke by attributing all of NLL to control-flow analysis, I was just trying to be brief. :) Having knowledge of control flow is just one of the approaches that will be used to achieve non-lexical lifetimes, though it is particularly applicable when also talking about MIR given that MIR is structured as a control-flow graph.

cwzwarich3• 10 years ago

The assumed fix here is to distinguish between a mutable borrow and the reservation of a location to later do a mutable borrow. Locations based on local variables and their fields can be reserved, although a move out of the variable would invalidate a reservation. Other locations (e.g. the result of a function call) can't be reserved and would give an error.

k__2• 10 years ago

it's basically just a straight quality-of-life improvement for Rust programmers

Nice to read. Are there any other such improvements planned?

Doing mostly scripting languages, Rust feels often a bit clunky with solutions like you mentioned or its unwrapping etc.

steveklabnik5• 10 years ago

One thing that would be helpful for those looking to write scripts is to use crates which provide a higher level API. So for example, the text-io crate wraps up the lower-level standard library interface to make it easier to use, though it gives you much less control over errors.

Due to Rust's low-level nature, we've focused on the low-level stuff first: the higher-level APIs can then be built on top. I think this kind of thing would be more helpful to you than actual language improvements in many cases.

kibwen7• 10 years ago

If you're aware of Rust's `try!()` macro for error handling, its functionality is being elevated into the language via the new `?` operator, which, in addition to being less verbose, will make for better error messages and also allow us to potentially extend the error propagation to types other than `Result` (such as `Option`). This feature is currently in nightly waiting to be stabilized, and the compiler codebase itself has been converted to use it: https://github.com/rust-lang/rust/pull/32390

There's also a huge overhaul to compiler error message formatting that should make error messages friendlier and more informative, and should hopefully be landing in nightly sometime today: https://github.com/rust-lang/rust/pull/32756 .

Also, part of the same work that is enabling non-lexical lifetimes (MIR, discussed here last week: https://news.ycombinator.com/item?id=11581681 ) is also going to enable incremental recompilation of Rust code, which should have a dramatic effect on turnaround time when developing code, as you'll spend enormously less time waiting for things to compile.

megrimlock• 10 years ago

That Niko's text-arrow lifetime annotations are so helpful here suggests a rust IDE could offer similar highlighting or annotations to explain borrow checker errors.

One of the ergonomic hurdles to rust adoption by experienced C++ users is that the language looks similar enough that such people may think they fully understand the semantics even before they've fully internalized all the details. It's a tricky zone when something feels familiar enough that you don't realize the remaining mistakes in your conceptualization.

Manishearth2• 10 years ago

The borrow checker already outputs these arrows.

This output is improving, too https://github.com/rust-lang/rust/pull/32756 -- feedback appreciated!

kibwen7• 10 years ago

At this very moment there is a PR from Niko that is about to land that will overhaul borrow checker error message reporting (and error formatting in general): https://github.com/rust-lang/rust/pull/32756 .

mtanski• 10 years ago

Can't happen fast enough. For the last two years in a row I try Rust every 6 months to see if it's at a place that I would consider using it. I hit the 3 problems described here every time I try it. You can work around all of them by restructuring your code it's just so tedious. I rather be doing something else versus working around this.

The community hasn't really been helpful, the answer is always restructure how write things. I'm writing a column store query engine (with table blocks accessing them by columns) that leads to a lot of borrowing so the advice is not all that helpful. I want to like Rust, but I can't.

TillE• 10 years ago

I've also found that basic problems like how to implement typical data structures (without unsafe code) are controversial, difficult, or actually impossible. That's really not good.

Still optimistic about Rust. But it has some fundamental issues to solve before it's generally usable.

Gankro4• 10 years ago

You can express data structures safely perfectly fine in Rust as long as you do all the things that make them safe in every other language -- aggressively garbage collect, indirect, and runtime validate.

I'm not aware of any language that lets you implement an interesting high performance data structure totally safely. Heck, Rust is impressive because you can encode singly-linked-stack and binary-tree-without-parent-pointers efficiently and safely without garbage collection! You can even build iterators that are statically verified to iterate over every element at most once, and statically guaranteed to not be invalidated.

Type systems that are powerful enough to ensure the safety of even moderately complex designs (doubly linked list, tree with parent pointers, singly linked stack, hashmap) appear to be unwieldy and relegated to academia.

pcwalton• 10 years ago

Let's not exaggerate the problem. First of all, non-lexical lifetimes have nothing to do with doubly linked lists (what you're referring to). Second, the language is clearly generally usable, as evidenced by the hundreds of thousands of lines of code written in it, most of which was written by people who have never touched the compiler. The reason is simple: most people get by just fine with the rich set of generic collections available in the standard library and on crates.io. For cases in which those aren't sufficient, you write unsafe code or use Rc.

Nobody claims Golang is "generally unusable" because you can't implement your own generic data structures. That it's harder than in unsafe C or C++ to implement doubly linked lists in Rust is just a less severe version of the same kind of thing.

rectang• 10 years ago

I'm just learning Rust and this is the primary question I have: If I can't use the data structures I'm accustomed to (because of mutability issues), what are the alternatives?

Where are the articles describing those alternatives? I've seen a lot of interesting discourse about the low-level stuff (e.g. error handling), but not higher-level "start here" approaches.

rkangel2• 10 years ago

Implementing data structures is considered an 'advanced' topic in Rust. That's ok for two reasons:

1) The data structures you'll need for most scenarios are in the standard library. The data structures you'll need for pretty much every scenario anyone has ever encountered in Rust are on crates.io. It should be relatively rare that you need to write one.

2) Writing data structures IS an advanced topic. The fact that you have trouble with the borrow checker trying to implement them highlights that understanding data ownership can get very complicated. Plus there's usually lots of corner cases to get tripped up in (I can't tell you how many times I've had to debug issues causes with crap implementations of circular buffers in C).

And when you do need to write a data structure - unsafe is there to allow you to do it. And given Rusts type system, you can write that data structure once, make REALLY sure you got the unsafe bits right and then hide it behind a beautiful abstraction and never think of it again.

steveklabnik5• 10 years ago

I always wonder about patterns like this, and how they arise. For the kind of Rust code I personally write, I can count on one hand the number of times I needed to deal with a non-lexical lifetime. But it's clearly a pain point for a lot of people, so I wonder where the difference is.

burntsushi• 10 years ago

I run into it infrequently (in particular, kibwen's example), but it's like a mosquito bite. "Oh, yeah, that sucks. Ah well, it's not going to stop me from doing what I was going to do anyway." It's definitely a little weird to hear it's preventing someone from using the language, so I too would like to hear more.

Manishearth2• 10 years ago

It's probably because you're used to Rust and know how to write Rust in a way that just avoids all compiler errors. People new to the language try to write Rust code as if it were C++ or something (or, in general, are not yet used to the Rust way of doing things). I have had this issue with every language I've learned so far, most recently Go (which I tried writing as if it were Rust).

So often newcomers end up designing code in a way that at a higher level isn't too flexible when it comes to borrow check, leading to these issues.

bsder3• 10 years ago

Fixing a compiler error by adding a lexical scope level has never occurred in any other language I can think of.

This was shocking to me when I bumped into it.

The problem is that you don't have the tools to even ask the right question to debug Rust code when you start. You have to ask questions on the IRC channel or you will get nowhere for quite a while.

A lot of people who program quite successfully in C or C++ do not really understand the idea of scope (which is what lets so many bugs creep in). Rust smacks you with "lifetime" in the face and makes you deal with it at compile time.

For those of us who are in environments where we have to struggle to debug C, the issues Rust is flagging are simply syntax errors. For other folks, they generally have to upgrade their mental models.

"Oh, that would have escaped the function after having gotten freed. Oops." is easy to understand when you have had to debug that dozens of times in C (generally because you accidentally added a code branch that didn't handle something). That error is not so apparent when you are used to simply returning an object in a garbage-collected language and letting the VM handle the issue.

blaisio2• 10 years ago

I'm surprised you keep encountering these problems. I've written a few significant (>1000 LOC) Rust programs and never encountered them.

bsder3• 10 years ago

The community hasn't really been helpful, the answer is always restructure how write things.

Um, what alternative should there be other than "the compiler should magically figure it out"? Every language has specific idioms that are the way you fix "Issue X"--the Gang of Four book, for example, is effectively an inventory of idioms to deal with C++ weaknesses.

You may be correct in your assessment that Rust is "too mentally expensive" for your task. That's fine. Rust has a very specific target, and that target is systems programs like kernels or Firefox--large programs that have long lifetimes and complicated memory management.

So, for example, if your program restarts processes often, then memory issues pretty much go away, and Rust really doesn't buy you much. If you can tolerate garbage collection, then there are probably much more expressive languages for the task.

I like Rust, but I'm really only going to consider Rust when I'm thinking "C or C++". If I'm thinking Python, Ruby, Go, Swift, etc., Rust probably isn't on the plate for now.

gsg• 10 years ago

This reminds me of an irritating problem in CPS based compilers where you can have a transformation that is obvious and legal except that after the transformation one of the relevant variables would not be in scope. The solution(s) are to decline to do that transformation, fart around with sinking and hoisting in order to get the scope right, or ditch scope and move to a graph model in which dependence is represented with explicit edges rather than being approximated by the lexical structure of the program.

I'm guessing that the lexical borrow problems that Rust are facing are an instance of the same problem. It will be interesting to read the follow up post and see what relation, if any, the suggested solution has to the graph approaches that I am familiar with.

cwzwarich3• 10 years ago

The solution is basically the same as the CPS case: switch to dominator-based scoping rather lexical scoping. I wrote an RFC on what would need to be done to the region system for nonlexical borrows a while back: https://github.com/rust-lang/rfcs/pull/396.

jeffdavis2• 10 years ago

"The lifetime of a value"

Surely he means variable, not value, right?

glass-animal• 10 years ago

I want to like Rust, and in the abstract I do, but every time I dive in the concepts have too much complexity for me to get going, and this post reinforces that.

It's not that I couldn't eventually grok Rust, it's that I don't have time to given that it's not part of my day job. I really hope that Rust leads to some of the same features being expressed in a more intuitive way by a subsequent language.

jeffdavis2• 10 years ago

I wonder how much of this is required to use rust effectively. A lot of languages have fairly tricky semantics and type systems, and most developers don't fully understand them. C++ is obviously a big language, but even C has things like volatile pointers and pointer aliasing and numerical type promotion.

And if you don't understand non-lexical lifetimes, I think that's OK. You can just be more explicit about the lifetimes and it will still work. And reading someone else's code should still make sense.

Non-Lexical Lifetimes in Rust

Related Stories