What is a good mental model of borrow checker?

You really do yourself a disservice by forcing lifetimes to map onto any single line of code. There are many trivial cases where this just isn't true, like conditional borrows within a loop. Syntactically, lifetimes are irrelevant. It's all about the liveness of data.

1 Like

Similarly, “two-phase borrows” fundamentally break the syntactic interpretation of borrow lifetimes; it requires reordering evaluation order where two-phase borrows are allowed, but isn't completely describable via the evaluation reordering, because the evaluation order isn't reordered, just the lifetime validity range activation deferred. In the currently proposed Stacked Borrows runtime borrowing/memory model for Rust, two-phase borrows are a special kind of borrow with distinct rules[1] from normal &mut to accommodate this.

“Two-phase” borrowing is what allows you to write things of form place.set(place.get()) (or, technically, even just place.field = place.get() for some fn Place::set(&mut self, _) and fn Place::get(&self, _). Semantically, the lhs place is evaluated first, and then the argument uses the place by-ref for place.get(). Without two-phase borrowing, this invalidates the by-mut evaluation of the lhs place, and the code shouldn't compile. What two-phase borrows allow is for the lhs place evaluation to happen and take a “not yet active mut-reference” to the lhs, then evaluate the arguments, giving them ref-access to the place, only “activating” the lhs mut-access after the arguments are evaluated, so the mut-access lifetime/region doesn't overlap the ref-access required to compute the arguments. The conditions required to make two-phase borrowing allowed are subtle[2]; this falls under a “if the compiler allows it, it's sound” pattern which you'll write without realizing it's a hard case.

The only mental model rules you need to understand what borrowing and lifetimes communicate are roughly the discussed:

  • “simple”
    • & are shared references; until the &s' last use, it is impossible to use the pointee region except by-ref (i.e. it cannot be used by-mut or by-move, but can by-ref or by-copy);
    • &mut are exclusive references; the pointee region which it borrows cannot be accessed by through a parent lifetime while the &mut exists, bit the &mut can temporarily loan access to derived references/lifetimes;
    • If it's safe code and the compiler accepts it, it's sound and you don't need to worry about it.
  • “intermediate”
    • & does not mean immutability of the pointee-reachable; indirection and UnsafeCell can introduce sound by-ref
    • Derived lifetimes from are allowed to borrow the entire parent region, thus static borrowing enforcing all derived lifetimes to expire before accessing a parent &mut, but that's a maximum;
    • When writing unsafe, you need to worry about variance w.r.t. lifetime-erased implementation (e.g. using raw pointers);
    • Just because safe code can do something doesn't imply unsafe APIs can do the same thing, because APIs require the introduction of full references that language features can elide;
    • Pinning and ?Unpin allow breaking the &mut-is-exclusive rule in ways nobody fully understands yet[3];
  • “advanced”
    • These advanced features do not need to be understood except to ask why these safe code snippets are allowed to compile and if/why unsafe function APIs cannot replicate the behavior exactly;
    • Examples include but are not limited to
      • Staggered field splitting, where built-in pure place evaluation (i.e. doesn't create fresh &mut reborrows to call DerefMut or IndexMut) is allowed to reborrow disjoint fields from separate place computations, instead of requiring both come from a pattern match destructure of the same place computation or unsafe place access not creating &mut;
      • Moving out of a pure built-in place evaluation with non-Copy type, creating a deinitialized and inaccessible place, along with moving back into that place reinitializing it and reenabling place access (also handling deferred variable initialization);
      • Two-phase borrows, as described above, enabling place.by_mut(place.by_ref()) for some place types;
    • The compiler getting smarter can allow more patterns in the future, such as NLL did previously and Polonius may in the future.

Everything “advanced” is recognizing the special cases where the “if the compiler allows safe code, it's sound” and whether it's doing magic place (re)evaluation not accessible to surface code. But there's no need to understand any of these features ahead of time, because these have no impact on what function API designs are sound. They do have an impact on what's possible with an API, thus idiomatic/ideal API design (e.g. preferring pub fields instead of trivial getter/setter pairs, to enable borrow splitting), but it's perfectly fine to defer understanding these patterns to when you find yourself asking “why does this compile”. You know already it's sound because it compiles, the advanced principle is being able to describe why it's a sound pattern, and why unsafe function APIs can't soundly replicate the pattern (if they can't).


  1. Actually, I'm not exactly certain how (or even if) the Stacked Borrows model handles two-phase borrows. Miri's implementation of Stacked Borrows has a workaround similar to the described, where it IIRC just doesn't activate the lhs borrow in the Stacked Borrows until the second active phase. This does illustrate that two-phase borrows aren't a completely separate concept; regular one-phase &mut can be semantically treated uniformly with two-phase by just immediately moving from the first “deferred” phase to the “active” phase. There's even been a minor proposal of the dynamic model being “three-phase,” even if it's not possible with safe references, where a with-mut-permission tag starts in a “preshared” phase, where it acts like a shared borrow tag, enters the “active” phase when it's mut-retagged, then if invalidated by ref-access, decays to a “postshared” tag that again acts like a shared tag, and still allows by-ref access to the place. That'd be roughly be

    let r: *mut T = addr_of_mut!(place);
    
    // UB: &mut *r; (formally, no UB yet; it's realized later)
    // `&mut *r` puts `r` in the active state as below
    preshared(&*r);
    
    &place;
    
    active(&mut *r);
    // r moves from preshared to active by mut-access
    // only made valid by two-phase borrows
    // IOW, UB with conservative semantics, including Miri
    // (Miri handles language two-phase, not for pointers)
    postshared(&*r);
    
    &place;
    
    // UB: &mut *r; (realized here)
    // r is put in postshared state by parent shared access
    // mut-access behind r is now UB
    // ref-access made valid by three-phase borrows
    // IOW, UB with conservative semantics, including Miri
    postshared(&*r);
    
    &mut place;
    
    // UB: &*r; (realized here)
    // r is invalidated by parent unique access
    // any access through r is UB
    
    ↩︎
  2. Minimally, the place computation must be transparently pure (e.g. cannot go through a library DerefMut, only naming a variable or built-in derefs (references, pointers, and Box) thereof) after autoref and autoderef, and the place's type must not (perhaps even transitive) contain any shared mutability which could violate the &mut exclusivity expectation that the pointee-reachable must not be modified. ↩︎

  3. The implications of pinning fall into the advanced-itermediate which may become suggested understanding before writing advanced unsafe relying on &mut-exclusivity. It's not worth going into here, as Unpin being safe to implement means the aliasing relaxation cannot be soundly utilized without creating a Pin, so it can be essentially ignored if you never use Pin, and the language has reserved the right to require the use of some new UnsafeMutCell to get &mut-aliasing permission, where PhantomPinned only impacts the safe Unpin trait — i.e. whether Pin<&mut YourType> is allowed to be address-sensitive and can't be relocated by safe code — but not anything further, like aliasing borrow validity when you Pin::get_unchecked_mut(self) -> &mut YourType. ↩︎

2 Likes

Thanks for pointing out borrow splitting

and also two-phase borrows. I really appreciate it!!

You say that

On the contrary I think you have to understand some of it to write good Rust code.

Assume that I haven't read your post and I have no idea about two-phase borrows. So, far my mental model of borrowcheker is that if you take a mutable references to some data it invalidates all the shared references before. So I would think that data.set(data.get()) cannot compile so I would first do let cloned = data.get().clone(); and then pass that cloned value to data.set(cloned). Because of my terrible mental model I did not write a good Rust code and introduced unnecessary clones.

And I think this is not just limited to unnecessary clones. It might affect all my data structure or API design. For example, I know that MVC systems requires that each of the components contain references to each other (or have callbacks that capture references to other units to notify changes) which would introduce reference cycles that Rust would not allow. So, when I design my program I would avoid MVC architecture.

Now that assume that I have a some API design pattern in mind which is clean and I am experienced using it in some other domain, but I mistakenly think that borrowchekcer would not allow it. Then probably I would design my system with unnecessary controtions to satisfy the borrowchecker even though borrowcheker would allow th original design.

So what is the alternative? Just write a piece of code that you would write in other languages without borrowchecker and see whether the borrowchecker is angry? I think this is not feasible. We are giving this advice to Rustaceans, whou would think about software from Rust perspective, using Rust idioms and patterns. The advice here says that be a Pythonista etc, and write your Rust code the way you would in python, then see borrowchecker's complains. Then you can contort your pythonic code to convince the borrowchecker. I think what you would get out of this process would be nothing but a monstrosity.

The issue I am mentioning is not soundness. But elegant, Rustic, code and it cannot be achieved without a sound mental model of the borrow checker.

Thank you for the breakdown of topics to simple, intermediate, advanced, let me try to paraphrase (the ones I manage to understand) for posterity.

Road map to understand borrows and lifetimes

  • beginner
    • shared and mutable references must live at most the lifetime of the referent, and refeneces lock the value they point to i.e once you have a shared reference your interaction with the value must be through it (or you can drop the reference and keep interacting with the value directly) and similarly with mutable references.
    • Reborrows if you have a shared reference you can get new shared references through it. and if you have a mutable references you can get shared or mutable references from it, but the same rules of locking and interaction apply. (i.e if you get a mut ref x from a mut ref y all your interactions with the data must be via x until you drop it)
  • intermediate
    • Interior mutability some types give you the ability to mutate the data even when you only have a shared reference to that type.
    • field/borrow splitting borrowchecker undertsands some compound types that you can have two mut references at the same time to disjoint parts of the compound type.
  • advanced
    • two phase borrows borrowchecker can sometimes reinterpret the order when a mut ref and a shared ref to same data came into being, so that patterns like data.set(data.get() can be allowed.

As you can see my list is smaller than yours because I could not understand some of the points that you made, but I would very much like to.

Hopefully you would agree that having such a roadmap is good for new Rustaceans. Not because it provides soundness for their code but it provides elegegance and Rustic quality to their code.
So, what other thing can I add to this roadmap?

1 Like

OK, I said I would, so here we go.

First, it's been referred to at least indirectly already, but if you haven't already go read Common Rust Lifetime Misconceptions.

Something like this is the general context of this section: a method that borrows mutably but returns a shared borrow (misconception #9).

// With non-elided lifetimes
fn insert_then_get<'a>(&'a mut self, data: T) -> &'a T { /* ... */ }

Sometimes people come around ask why it doesn't work like the article talks about -- letting the method body use a &mut self, but after returning, the object is only immutably (shared) borrowed. And I struggled with this too. The explanation of "well Mutex (a library type) relies on it so we can't change it now" seemed somewhat weak [1]. The more general argument of "&mut is really exclusive access and you can rely on that in your own methods" rang more true [2], but I still struggled to make it gel with my mental model.

So I could explain errors arising from this to others, but it was along the lines of "well, the return sort of carries around the exclusiveness after it gets returned..." [3]

Then eventually, and sadly I can't explain exactly why, I gelled this situation with misconception #8, even though I had understood #8 in isolation for some time: the return being shared or not doesn't matter because in order to call the method at all, the &'a mut must be created, and thus -- statically, unchangeably -- the object is exclusively borrowed for 'a. Within region 'a, you can only access the object with things derived from the &'a mut. That's what creating the &'a mut means. [4] The flavor of the return (shared or exclusive) just doesn't matter in this model.

The return isn't carrying around the exclusiveness; the creation of the reborrow to make the method call in the first place demands the exclusiveness. [5] They're still connected via the lifetime, but once I started thinking of it this way, it was much more clear and "but of course" and I stopped caring about the exact flavor of the return type.

Into the fractal breach...

That wasn't the end of the story though! The adjustment to my mental model really firmed up how I felt about that particular case, but eventually I realized a conflict with my mental model of another borrow functionality: the ability to reborrow an exclusive borrow as shared without killing other existent shared reborrows. Here's an example.

So then I had to spend some time thinking about how the two related, since this sort of re-asks the question: Why can't I call insert_then_get and then turn the borrow of the entire object into a shared borrow? And my eventual answer was, because I've given away the &mut and I can't reborrow it any more. insert_then_get would have to do the reborrow and give it back to me.

It's still an area where I'm fleshing out my ideal model, but as it turns out the different mechanics usually arise in isolation from each other, so truthfully I just use the side of my model that fits any given situation the best.

Because it's never the end of the story.


Related issues come up when people try to explicitly drop references or similar in order to shorten lifetimes. Dropping things actually can make a difference for objects with destructors (as drop scopes are still lexical), but for references, calling drop is just another use site. If the lifetime of a reference was already problematic, adding a use site isn't going to help; your problem is elsewhere.

A reference's lifetime isn't something it's carrying around you can dispose of; it's the output of a static analysis of use sites and liveness.


One last one, though it's arguably more about type than borrows. We like to elide lifetimes on reference types when possible, and refer to "the &str type", and so on. But there is no single type that covers all references &T. Instead, &T is a type constructor: it takes a lifetime, and then &'some_lifetime T is an actual type.

There is no higher-ranked for<'any> &'any T type.

This seems to come up a lot when dealing with generics, because a generic type parameter can only resolve to a concrete type -- and not to a type constructor. So for example here:

fn take_closure<F, I, O>(f: F) where F: Fn(&I) -> O, {
    let _ignored = f;
}
fn example(s: &String) -> &str {
    &**s
}
fn main() {
    take_closure(example);
}

Errors in a pretty poor way:

error[E0308]: mismatched types
 --> src/main.rs:8:5

8 |     take_closure(example);
  |     ^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
  |
  = note: expected trait `for<'a> <for<'a> fn(&'a String) -> &'a str {example} as FnOnce<(&'a String,)>>`
             found trait `for<'a> <for<'a> fn(&'a String) -> &'a str {example} as FnOnce<(&'a String,)>>`
note: the lifetime requirement is introduced here
 --> src/main.rs:1:51
  |
1 | fn take_closure<F, I, O>(f: F) where F: Fn(&I) -> O, {
  |                                                   ^

The nicest thing here (spoilers) is that it points to the O.

Trying to coerce to a function pointer improves it a bit:

-    take_closure(example);
+    take_closure(example as fn(_) -> _);
8 |     take_closure(example as fn(_) -> _);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
  |
  = note: expected trait `for<'a> Fn<(&'a String,)>`
             found trait `Fn<(&String,)>`
note: the lifetime requirement is introduced here
 --> src/main.rs:1:41
  |
1 | fn take_closure<F, I, O>(f: F) where F: Fn(&I) -> O, {
  |                                         ^^^^^^^^^^^

error: implementation of `FnOnce` is not general enough
 --> src/main.rs:8:5
  |
8 |     take_closure(example as fn(_) -> _);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
  |
  = note: `fn(&'2 String) -> &str` must implement `FnOnce<(&'1 String,)>`, for any lifetime `'1`...
  = note: ...but it actually implements `FnOnce<(&'2 String,)>`, for some specific lifetime `'2`

...well, maybe an improvement, it's at least talking about "for any lifetime" versus "some specific lifetime".

Anyway, given how I introduced this section, you may have already figured out the problem: A function that returns a borrow of it's inputs does not return a single type. It returns types that differ in lifetime, based on the input reference's lifetime. The type parameter O doesn't match -- since it represents a single type, the bound can only work for functions that return something unrelated to the input lifetime.

If you know the return is a reference specifically, you can rewrite the bound. Otherwise the workarounds tend to involve traits that allow you to not mention the result as a type parameter, e.g. by using GATs (generic associated types). The original name for GAT was ATC (associated type constructor).

I've mainly seen this for closures, but it happens in other ways when you try to abstract over "borrowing or owned" with generics.


  1. even though I accepted it as a practical barrier to change ↩︎

  2. and I have since made use of this guarantee in my own code for logical correctness! ↩︎

  3. which is still a valid interpretation in many ways! But I found it unsatisfying. Today I'd probably phrase it more like "the &mut gets transformed into the return value". ↩︎

  4. Moreover, you passed the &mut to the method, and &mut isn't copy, ergo you can only access the object with things derived from the return value during 'a. ↩︎

  5. And then you give away the root of that exclusiveness by making the method call. ↩︎

2 Likes

That’s not how two-phase borrows work. They really are nothing more than a neat way to make the syntax slightly neater. data.set(data.get()) will only work if the signature of get is fn(&self) -> SomeOwnedValue, it cannot return anything that’s re-borrowing the &self argument, or else data.set(data.get()) would fail. The alternative is to write let new_value = data.get(); data.set(new_value); which doesn’t do extra clones, and has the same performance.

Two-phase borrows really are a niche feature; many fairly advanced Rust-programmers will have little or no idea that it exists or what exactly it does, and thus:

  • when carefully programming to appease the borrow-checker, they would write such code with an extra let new_value = … step; which it honestly fine, nothing is lost here…
  • when – which is more commonly the case – not thinking about borrow checking much at all unless the compiler starts complaining, every so often “accidentally” write code such as data.set(data.get()), and not spend a single thought about why it compiled successfully. Still, everyone understands what this code means, what it’s supposed to do, everyone’s happy it just works, and that’s even the intention of this feature in the first place: Adding a convenience rule that makes the borrow checker slightly less annoying in a very specific kind of case. See below:

Motivation

The overriding goal here is that we want to accept nested method calls where the outer call is an &mut self method, like vec.push(vec.len()). This is a common limitation that beginners stumble over and find confusing and which experienced users have as a persistent annoyance. This makes it a natural target to eliminate as part of the 2017 Roadmap.

Some thoughts on why people might, if not thinking about the code in detail, assume data.set(data.get()) to compile?

The problem is: data.set(data.get()) desugars[1] to something like Foo::set(&mut data, data.get()), and then &mut data is executed before data.get(). On the other hand, this &mut data expression was completely implicit; in the form data.set(data.get()) there was no obviously visible expression to be evaluated in the first place, so the intuitive interpretation of this kind of code would be

  • evaluate data.get()
  • pass the result to the data.set call

instead of

  • evaluate &mut data
  • then evaluate data.get()
  • pass the results to the .set call

With an intuitive mental model of the borrow checker in mind, the first (and inaccurate) interpretation looks like data is first borrowed immutably for a short time in data.get(), then borrowed mutably for a short time in data.set; and the second (more accurate) interpretation looks like data is first borrowed mutably; while this borrow persists (since it’s later used in the .set call), it is also borrowed again immutably… boom… compilation error. Two-phase borrows are mainly not a concept to learn to get a better/deeper understanding of the borrow checker, but more a feature designed literally for the opposite effect: to allow people to care less about the specifics of borrow checking (in an admittedly very narrow set of cases).


In the above interpretation, the inaccuracy that lead to the belief that data.set(data.get()) would compile was – by the way – [2] not an inaccuracy in determining how borrow-checking works, but rather an inaccuracy in determining how method calls are desugared. This also demonstrates another aspect of understanding borrow-checking in Rust that I meant to mention but haven’t before:

The borrow checker operates on desugared Rust code, with all of those convenience features / syntactic sugars that we have expanded, and even that desugared version of Rust still has quite a few features… in order to fully understand borrow checking of Rust programs, you would also need to fully understand all the language features of Rust, all syntactic sugar and how it expands, all the fundamental language features and how they interact with the borrow checker, and presumably even with a detailed, not just rough and intuitive understanding.

Of course that’s a lot, but that’s because the goal of fully understanding the borrow checker is not the most useful goal (unless you want to write your own implementation of a Rust compiler, and one that does – unlike the ones that I’m aware of[3] – comes with a borrow checker).


Addressing your further points now…

Unless you’re saying that two-phase borrows (or one of the other features @CAD97 listed as “advanced”) would be relevant to API design, I’m not sure I get your point.

However, those “advanced” features are really quite irrelevant for API design:

  • Two-phase borrows are completely irrelevant, you can work around the lack of two-phase borrows trivially by evaluating the relevant method arguments before the method call expression, as explained above.
  • Moving out of certain places behind indirection is irrelevant for data-structure design or API design, because you can achieve effectively the same thing by using Option values, which can be moved using Option::take, so data structures aren’t affected, and partially-moved-out-of values cannot be represented in function signatures, so they don’t appear in APIs at all either (if you want something like them there, again, you’d need to use Option).
  • Lack of borrowing parts of a variable/value in multiple steps is something that, as far as I’m aware, should be generally fairly straightforward to work around, too, in all cases; of course splitting borrows in general is a must know, but not necessarily borrowing e.g. fields of a struct, possibly even behind built-in dereference or index operations. Access the whole thing once, split the borrows once in a match, and most situations are solved; in some niche cases, knowledge of how to split a (mutable borrow of a) slice into multiple parts could be required.

The alternative is what I explained in my first reply: Approach borrowing in Rust from two sides: Things that you know are forbidden/impossible, patterns of code that you know are possible, and a bit of unknown in the middle. If you only avoid the known-forbidden patterns, you won’t discard any “clean APIs” that would’ve been acceptable by the borrow checker but didn’t immediately fit with your known-possible code patterns. In most cases, avoiding known-forbidden patterns is enough – when you’re designing a clean/nice API, too – that you’ll be automatically (or perhaps “by change”, though the chance is high) end up with a design that you then also know how to actually implement using the code patterns you know are allowed, or at least assume should be fine. If it doesn’t work out fully, some experimentation, and compiler error messages often solve the rest. In the rare case where you think your API should be fine because it doesn’t violate any of the know-forbidden things in Rust, but also you cannot quite figure out how to pull it off, finally it’s time to learn more… or ask someone more experienced for help (which will also result in learning more). You’ll either learn new forbidden things, so the API wasn’t good after all, or you’ll learn new details of what you can pull off and convince the borrow checker is correct, or (probably) both; and if you asked someone for help, you might get additional feedback on the API design that wasn’t strictly about “what is or isn’t okay w.r.t. borrow-checking”.


I don’t believe Rust code should be written like python. Even though even good python code often has a structured ownership story; after all, even in GCd languages, people manage to avoid memory leaks, so you’ll have a rough understanding on what keeps what values alive so that everything can be cleaned up eventually. On the other hand, of course a rough understanding of the basic principles of ownership in Rust helps a lot, and some (well… maybe lots) of smaller or larger coding patterns need to be learned and adjusted eventually in order to write nice code and not end up with a monstrosity. But that’s the comparable to most other aspects of learning programming (or programming paradigms), too, I believe.


I like your paraphrasing (haven’t read it in detail yet), and will gladly look into giving more insight into the points you haven’t understood enough to paraphrase yet. I like your “roadmap” idea, but it does make sense in my opinion to really mark the “advanced” topics as “does not need to be understood unless you have fun acquiring niche knowledge or would like to be able to explain every last bit of compiler behavior in detail” (both of which I myself would consider myself to fall under). In my view, the listing you gave above as of now contains 5 large points about fundamental and important aspects/features of ownership+borrowing in Rust (references, reborrows, interior mutability, borrow splitting), and one little piece of niche knowledge with little practical value (two phase borrows). I mean, at least “two phase borrows” are explained quickly, so it’s not really much effort to learn about them anyways? I do have to admit (and IIRC that was my initial reaction, too) that the term “two phase borrows” sounds a lot more big and important of a language feature than what it’s really about :slight_smile:


  1. well, with two-phase borrows it no longer desugars to exactly that, but something slightly different, mostly equivalent, but supporting the &mut data expression to be executed in two steps; but that’s besides the point of this argument ↩︎

  2. at least in my opinion ↩︎

  3. please feel free to point out any alternative Rust implementations that do have a borrow checker ↩︎

3 Likes

That’s a lovely example to do another round of those diagrams I started in an earlier post above

#[derive(Debug)]
pub struct S {
    a: String,
    b: String,
}

impl S {
    pub fn foo(&mut self) {
        // (1)
        let a_ref = &mut self.a;
        // (2)
        let b_ref = &mut self.b;
        // (3)
        
        *a_ref += "a";
        *b_ref += "b";
        println!("{a_ref} {b_ref}");
        
        let a_ref_two = &self.a;
        // (4)
        *b_ref += "b";
        println!("{a_ref_two} {b_ref}");
        
        let s_ref = &*self;
        // (5)

        println!("{s_ref:?} {a_ref_two}");
    }
}

At (1)

// `self` is the variable of type `&mut S`, not the `S` itself
self

At (2)

// “*.a” stands for the place obtained by first dereferencing, then going to field `.a`
self <--mut @*.a-- a_ref

At (3)

// creating `b_ref` accesses only the “*.b” part of `self` which is disjoint from the
// part mutably borrowed by `a_ref`, which is why `a` can still exist
self <--mut @*.a-- a_ref
    ^
    |
    +---mut @*.b-- b_ref

At (4)

// creating `a_ref_two` accesses the “*.a” part, so `a_ref` must end/die
// and the newly created shared reference a_ref_two now borrows immutably
// from `self` at “*.a”, hence there’s no “mut” but “shared”
self             ( a_ref [now dead])
  ^ ^
  | |
  | +---mut @*.b-- b_ref
  |
  +--shared @*.a-- a_ref_two

At (5)

// creating `s_ref` accesses `self` at `*` (i.e. its dereferencing target)
// which overlaps with both “*.a” and “*.b”. It’s a shared borrow
// so any overlapping mutable borrow conflicts and must die. This
// kills `b_ref`, but NOT `a_ref_two` since the latter has non-`mut`
// access to `self`. Note that we did NOT care about the type of `b_ref`
// here but merely about whether the arrow in the re-borrow diagram
// has a “mut” or “shared”.
self             ( a_ref [now dead])
^ ^
| |
| |              ( b_ref [now dead])
| |
+ +--shared @*.a-- a_ref_two
|
+----shared @*---- s_ref

And an example with insert_then_get

struct S(/* … */);
struct T(/* … */);

impl S {
    fn insert_then_get<'a>(&'a mut self, data: T) -> &'a T { todo!() /* ... */ }

    pub fn foo(&mut self, data: T) {
        // (1)
        let immut = self/*(2)*/.insert_then_get(data);
        // (3)

        let other_immut = &*self;
        // (4)

        (immut, other_immut); // compilation error
    }
}

At (1)

// self: &mut S
self

At (2): We implicitly create a &mut *self re-borrow here which is passed to insert_then_get(data). [Just so no-one blames this re-borrow later: If we wouldn’t re-borrow, self would be moved, so that’s no good either, as we use it later.]

// I’m calling it `insert_then_get::self`, because it’s
// the value of the `self` variable inside the `insert_then_get` function
self <--mut@*-- insert_then_get::self

Now for (3), we need to evaluate the right model of reasoning about function calls. I would agree with @quinedot that for this purpose replacing values passed into the function makes a lot of sense. Note that we are replacing insert_then_get::self with the return value because the lifetimes in the signatures dictate that the returned &'a T’s lifetime is the same (and thus in particular outlived by) the &'a mut self’s lifetime. As mentioned before, more complicated function signatures might involve the need to replace multiple inputs with a single output, which inherits all the edges in the borrow graph so it’s a DAG then, no longer just a tree – or multiple return values[1] could replace a single input, possibly resuling in multiple parallel <-mut- edges that almost look as if they’re conflicting[2].

So at (3)

// the type of `immut` is `&T`, but types don’t matter, instead
// the existing `<-mut@*-` edge is simply kept in place
self <--mut@*-- immut

At (4)

self           ( immut [now dead])
    ^
    |
    +-shared@*-- other_immut

The immut got eliminated since the shared@* conflicts with the mut@*.

Compilation error happens upon accessing immut even though it’s dead.


For comparison, here’s the equivalent code but with an implementation

struct S(Option<T>);
struct T(u8);

impl S {
    fn insert_then_get<'a>(&'a mut self, data: T) -> &'a T {
        (*self).0 = Some(data);
        let &mut S(Some(ref data_ref)) = self else { unreachable!() };
        data_ref
    }

    pub fn foo(&mut self, data: T) {
        let immut = self.insert_then_get(data);

        let other_immut = &*self;

        (immut, other_immut); // compilation error
    }
}

and if we now inline the function call

struct S(Option<T>);
struct T(u8);

impl S {
    pub fn foo(&mut self, data: T) {
        let immut = {
            let self_ = &mut *self; // first function argument
            let data_ = data; // second function argument

            (*self_).0 = Some(data_);
            let &mut S(Some(ref data_ref)) = self_ else { unreachable!() };
            data_ref
        };

        let other_immut = &*self;

        (immut, other_immut); // compilation error
    }
}

it still fails (with almost the same error message)! This demonstrates that the problem was not even merely artificial constraints from the function signature (something that can happen, too, if lifetimes are too restrictive on the caller), but even borrow checking while seeing the body doesn’t help. Only if the re-borrow is eliminated will the code compile

struct S(Option<T>);
struct T(u8);

impl S {
    pub fn foo(&mut self, data: T) {
        let immut = {
            // let self_ = &mut *self; // re-borrow no more!
            let data_ = data; // second function argument

            (*self).0 = Some(data_);
            let &mut S(Some(ref data_ref)) = self else { unreachable!() };
            data_ref
        };

        let other_immut = &*self;

        (immut, other_immut); // works!!!
    }
}

This makes for two more nice cases.


struct S(Option<T>);
struct T(u8);

impl S {
    pub fn foo(&mut self, data: T) {
        let immut = {
            let self_ = &mut *self; // first function argument
            let data_ = data; // second function argument

            (*self_).0 = Some(data_);
            // (1)
            let &mut S(Some(ref data_ref)) = self_ else { unreachable!() };
            // (2)
            data_ref
        };
        // (3)

        let other_immut = &*self;
        // (4)

        (immut, other_immut); // compilation error
    }
}

Let’s skip the most boring steps.

At (1)

self <---mut @*--- self_

At (2): Note that the match accesses self_ by: dereferencing, then going into the only field of the S, then going into the Some variant, and inside of that into its only field. This field is then borrowed immutably by the ref data_ref pattern. Let’s make up some ad-hoc syntax for enum variant access, e.g. .:Some.

self <---mut @*--- self_ <---shared @*.0.:Some.0--- data_ref

Before reaching (3), the inner block ends. This is an interesting new thing: we are dropping self_. There must be some borrow checking rules to determine what happens there. E.g. if some references returned from that block borrowed from self_ directly, that would be bad. However, data_ref borrows only things that are behind at least one level of indirection and thus the borrow-checker allows such references to keep existing even though self_ is gone. Logically, we still have a situation as follows

// `self_` is dropped, but the reference it used to contain is not dead:
// its lifetime, inherited (as an upper bound) on `data_ref`
// is still very much alive

self <---mut @*--- (self_ [dropped]) <---shared @*.0.:Some.0--- data_ref

however, since self_ is out of scope, nobody cares anymore about the details of the ways in which self_ was borrowed. References that re-borrow from self_ can no longer be killed by new accesses to the self_ variable (as self_ can no longer be mentioned in any code since it’s out of scope), so the only way they can still be killed is by any access that would have killed self_.

For illustrative purposes let’s carry on with both interpretations though. Either we still have

At (3)

// `data_ref` was moved into `immut` by the way, which we’ll model by simply replacing
// the name in the diagram

self <---mut @*--- (self_ [dropped]) <---shared @*.0.:Some.0--- immut

Or we can reduce the “(self_ [dropped]) <---shared @*.0.:Some.0--- ” part and simplify to

self <---mut @*--- immut

At (4), the other_immut reference is created, and this operation needs (immutable) acces to *self, which overlaps with the existing <---mut @*--- edge. So in either interpretation, we get either

// `self_` was killed; killing a borrow also kills all its re-borrows recursively
self      (self_ [dropped, now also dead])     (immut [dead])
    ^
    |
    +--shared @*-- other_immut

or in the other interpretation

self              (immut [dead])
    ^
    |
    +--shared @*-- other_immut

Finally, the code that does work

struct S(Option<T>);
struct T(u8);

impl S {
    pub fn foo(&mut self, data: T) {
        let immut = {
            // let self_ = &mut *self; // re-borrow no more!
            let data_ = data; // second function argument

            (*self).0 = Some(data_);
            // (1)
            let &mut S(Some(ref data_ref)) = self else { unreachable!() };
            // (2)
            data_ref
        };
        // (3)

        let other_immut = &*self;
        // (4)

        (immut, other_immut); // works!!!
    }
}

At (1)

// so far, only one write access directly to `self` happened,
// no references were created
self

At (2)

self <---shared @*.0.:Some.0--- data_ref

At (3) (no data with lifetimes was dropped, so nothing to talk about w.r.t. dropping things)

// moved `data_ref` to `immut`
self <---shared @*.0.:Some.0--- immut

At this point, in the previous code, the shared access was not on self directly, but hidden deeper in the tree behind an outer <--mut …-- edge, which is the significant difference resulting in immut surviving the next step.

At (4), the creation of other_immut doesn’t conflict with immut since immut is only an immutable borrow.

self <---shared @*.0.:Some.0--- immut
    ^
    |
    +----shared @*------------- other_immut

  1. still ignoring that there is arguably an intermediate step of receiving a single tuple value and then taking it apart ↩︎

  2. but as you see above, the only time we actually check for conflicts is when creating new borrows, and kill existing borrows overlapping with that new borrow ↩︎

2 Likes

But it seems like this is a niche feature, and we can still say "the syntactic interpretation is valid in these common cases, and when its invalid, the visualization breaks down". Tooling which gives us such a syntactic visualization could simply warn the user about this advanced case, or hide if from the user by showing the 2-phase-borrowed reference as a syntactic lifetime which encloses the entire place.set(place.get()) subexpression (which would be a "lie" but is likely enough explanation for less experienced users who really need a visual model of lifetimes the most).

These are just the actual rules for references/lifetimes, which is one mental model (the most correct one, in a sense), but there may be others. This model makes no reference to source code locations or lexical structure (this is likely intentional!). I think it may be worthwhile to try to find a mental model which is "almost" as powerful, "almost" as correct, but much more amenable to visualization.

This is still a very useful breakdown of lifetime-related rules into categories of increasing complexity.

Yes. Perhaps our reasoning about incorrect code is more important. But I image the same reasoning should apply to to correct code.

Type inference produces extra information which may be useful to the user, even for correct programs. In VSCode these are "inlay type hints". Is it sensible to talk about "lifetime range hints"? Or in the case of a borrow checker error, is it sensible to talk about "two overlapping lifetime ranges which must not overlap"? In the same way that some type errors talk about "two expressions whose types differ which must be the same"?

Visualization of lifetimes within the source code itself is still impractical. To illustrate, it is fundamentally obvious that source code can be visualized in the same form as its abstract syntax tree. But critically, this tells us nothing about the runtime behavior of the code. Analyzing some property of the code such as time complexity is not really possible with just an AST.

For this set of problems, you need a different representation. Something like a finite state machine. The visualization of an FSM is vastly different to the visualization of an AST. And coincidentally, an FSM is a closer approximation to what is required for real-world analyses of lifetimes.

To put it another way, you will find cases where lifetimes are applicable syntactically (the pre-NLL borrow checker is an example of this class). But for anything even mildly more complex, this model breaks down and the visualization becomes too detached from the structure of the code. And I would wager the simple cases that can be visualized within the code are not even the challenging ones that would benefit most from visualization.

The point being made was that "the borrow checker said it's ok" ought to be good enough for most programs. No more reasoning is required if all you want to do is get work done. Trust has been placed in the borrow checker to accept only valid code. The exception stated earlier is that reasoning about why valid code is indeed valid is that it's still a useful question for educational purposes. With very high probability, it isn't a useful question for validating the validator.

These are good questions to ask, IMHO. I don't have a great answer, though, because lifetimes are something that you don't really control directly. At least not in the same sense that you control types directly. The reason is because everything has a lifetime, just as everything has a type. In fact, the lifetime can be considered "part of the type" in many respects [1].

But as far as providing lifetime hints in an IDE? There might not be a solid way to define the lifetime of everything apart from giving them unique names when they are not equivalent. Which are what lifetime annotations do.


  1. This probably most apparent with lifetime bounds like T: 'a or 'a: 'b. This is sorely oversimplified, and I'm not confident in my own understanding to comment on this topic further. ↩︎

1 Like

I'm wondering what visualisation of lifetimes in an IDE would look like.

I mean, in any piece of code we have multiple parameters, local variables, structure elements all mixed up with lifetimes that likely overlap more or less, here and there in some tangled way.

How would one colourize that, or highlight it in anyway that was not a total mess?

Probably any such visualization could not be passively available for all lifetimes, as they're not even properly nested like e.g. colored brackets are.

Instead, it would have to be a thing where you request to see a specific lifetime (e.g. via hover) and temporary annotation for just that one lifetime shows up, highlighting the region(s) where it is considered live and/or the contributing uses that keep it live (or kill it).

One property to note that makes it a possible visualization is that for the purpose of visualization, we're mostly only considered with a slightly simplified question: would inserting a use (e.g. of the hovered variable) at this point compile? This is a source-positional question, thus it has a source-meaningful interpretation.

Borrowck is IIRC exclusively done on MIR nowadays, which is after the source's structured control flow has been transformed into CFG form. As such, it might not be possible to fully losslessly translate back to regions of the source code, but "can I use the borrow at this position in source" is a meaningful query that's possible to visualize.

Just note, however, that this query is fundamentally not meaningfully true for all borrows simultaneously; adding a use of a borrow necessarily impacts the regions where other related lifetimes/borrows may validly have uses added.

3 Likes

@quinedot Thank you for pointing out the example

and your comparison of it with

When I first read your post I was also got the impression that the borrow checking is complicated in a fractal manner, hopelessly complex. But after I read @steffahn 's entry

in which they explain how you can understand those two examples not in a fractal manner but stemming from just two principles that we already demarcated namely, (1)you are allowed to reborrow and (2) reborrows form a stack. [maybe third, i.e. desugarings]

Maybe something that I should add to the roadmap which @steffahn has pointed out before and steps their construction of the diagram emphasized more clearly

is that one should keep desugarings in mind and not evaluate lifetime issues on the level of surface syntax.

That @steffahn 's explanation is so illuminating and the visual diagramatic presentation is so convincing is I think what explains the interest in this post that maybe we should have similar visual clues in IDE. The whole purpose of this post is to get a better idea of the reasoning steps that borrowchecker takes so that one can manually follow those steps while they are writing the code before they get into endless discussions with the borrowchecker. And the idea that instead of taking those steps mentally, automating it in the IDE and having visual clues is very appealing. But I think it is a different topic. For the purposes of this discussion it would be better if we just collect the main concepts and principles about how one should about the borrowchecker first, then we can discuss whether it is feasible to present guiding signs of these concepts in an IDE in an automated manner.

1 Like

This would seem to imply that lifetimes are a non-lexical property of a program, because lifetime analysis is done on the control flow graph, not the abstract syntax tree. But the CFG is derived from the AST, even the NLL RFC described a pretty straightforward derivation, and describes the method for reporting errors in terms of "points" within the CFG (which, naturally, must be mapped back to the AST to eventually report them). Every concrete of lifetime errors within a concrete program (written by a human or reported by the compiler) seems to appeal to reasoning of this form (as described in the NLL RFC):

  • The point where the borrow occurred (B).
  • The point where the resulting reference is used (U).
  • An intervening point that might have invalidated the reference (A).

It seems to me that this sort of structure can be extended beyond error cases, to cover the program in the same exact lifetime annotations (borrow occurs here, reference used there) for every reference. Would it be easy? Would the result make sense or be some sort of monstrosity of dozens of color coded annotations? I don't know - the borrow checker is pretty complex, so it may very well be the case.

Indeed. I don't feel the need to validate the validator, it is purely for educational purposes. I want the borrow checker to "show its work".

Yes, mere annotations are a start, but it seems to me that lifetimes have more structure than "each reference has a lifetime" (in particular, I think they span over source code locations).

Random aside: I know I've seen lifetimes in the "inlay type hints" sometimes. It doesn't always generate them, and I don't know the necessary conditions to generate them.

This would probably be ideal, we already do pretty much the same for compiler errors.

Does it make sense to display this information for all points in the program, for a single variable? In particular, highlight any regions where the hovered variable is useable in this way. This is what I think I mean by "lifetime range hints" (although references may become unusable, then become usable again later, so it really should be "lifetime union-of-ranges hints").

Yes, I feel like I may have derailed this somewhat, sorry for that. However my reasoning is that a "good" model is one which is easy to visualize. This is not even strictly related to IDE tooling - can I draw my reasoning in a particular model with pen and paper using pictograms, boxes, lines, etc., without appealing to complex algebraic rules? I think that if we had a model which was naturally amenable to visual reasoning in this way, IDE tooling would naturally fall out of it.

There's two difficult parts here:

  • The mapping for B to U is 1:many - a single borrow can be used many times, so your visualization has to have some way of showing all of the ranges B to Un for all n in an unambiguous fashion.
  • Given a pair B, U, there are multiple possible As. Again, this makes doing a good visualization hard, since while errors can just point to one A and say "this is a previous invalidation point", a good visualization has to tell me about all the As that cause me to have trouble.

It'll also be true that in the error case, many (perhaps all) of the As in your situation will also be Us from the context of other triples (B, U, A). Again, for error messages, this is not a problem (you only need think about the (B, U) pairs that result in an error, and for each of those, you need only pick one A), but for the visualization case, it's a challenge.

A lot of conversation has definitely happened here, and I will confess that I am guilty of not reading the whole thread. I like to make the following general talking points:

  • I don't think it is generally useful to think of local variables as having lifetimes. It is unfortunate that the term "lifetime" tends to make people think about the scope of a variable, but scopes really aren't the important thing here. Rather, what's important are borrows and mutable borrows, and the bit about scope can mostly be handwaved by saying that dropping or deinitializing (read: moving without Copy) effectively takes a mutable borrow.
  • Borrowing a value (e.g. &expr and &mut expr) creates what is known as a loan. The goal of the borrow checker is to prevent a &mut loan from coexisting with another loan of the same thing. It does this by identifying every loan that occurs in a function body and tracing the regions through which each one is active in the control flow graph.
  • These loans are represented in the type system using lifetime annotations.
  • Values in rust can carry loans, which we express in the type system by writing T: 'a. And here is where the word "lifetime" begins to make sense, because you can also think of this as notation as expressing a "lifetime constraint." Most values have a constraint of T: 'static, meaning they can live as long as you want. But sometimes you have T: 'a, meaning it can only live for as long as the loans in 'a do not conflict with anything.

Some more resources on this:

14 Likes

Can you explain a bit more the interaction between Pin/Unpin and &mut exclusivity. (not that I expect a complete picture after your comment that nobody understands it yet, but a brief introduction would be much appreciated)

What took my interest in your phrasing here is that you emphasize this is the case for built-in place evaluation which suggests that these are not available for user created structures. Is that correct?

I assume here you refer to what I call partial moving (is that close to its official name? ) i.e

struct A {
    a : String,
    b : String
}  

let x = A{a: "hello".to_string(),"world".to_string()};
let z = x.a \\ here I moved out of x, which means x is not in a valid state
let w = x.b \\ but I can still use x   

I always wanted to know the story that how it works and when is it allowed, I vaguely remember that if the struct implements drop it is disabled. I would like to here more about it and its interaction with borrows and lifetimes, can you explain your point more?

The short version of it is that async allows you to hold references to locals across .await points. But those references are derived from / aliasing the Pin<&mut F> used to drive the future, causing a problem if we naïvely treat that outer reference as exclusive.

The usage pattern works out in practice, but formally justifying why, as well as how to communicate this to optimizing backends, is not clear.

Yes; or to be more specific, user defined DerefMut and IndexMut implementations. The compiler tries very hard to make it that the validity of code depends only on the signature of functions, and not their implementation; this means that when functions aren't involved, the compiler has a more complete picture and can allow more things.

That's it, really: whenever a type is used, it must be complete. If a type implements drop, the drop counts as a use. Because any[1] operation could potentially panic, a type with a drop implementation can't even temporarily be incomplete.

This doesn't interact with borrowing at all; it's just the normal fact that mutating a place conflicts with any borrows previously derived from your access method.


  1. Being pedantic, built-in place evaluation and copies/moves can't panic. In theory, Rust could allow moving out of and back into a field of a drop-having type if you do absolutely nothing in-between. It doesn't currently, though; use mem::swap or mem::replace to do so instead, which use unsafe to implement essentially that. ↩︎

Simple comparison in code: [T] slices have built-in indexing, while Vec<T> uses the Index/IndexMut traits.

fn f(x: &mut [(u32, u32)]) {
    let r1 = &mut x[0].0;
    let r2 = &mut x[0].1;
    std::mem::swap(r1, r2);
}

compiles, whereas

fn f(x: &mut Vec<(u32, u32)>) {
    let r1 = &mut x[0].0;
    let r2 = &mut x[0].1;
    std::mem::swap(r1, r2); // compilation error
}

doesn’t.

But in this case,

fn f(x: &mut Vec<(u32, u32)>) {
    let r = &mut x[0];
    let r1 = &mut r.0;
    let r2 = &mut r.1;
    std::mem::swap(r1, r2);
}

can be used instead.


Similarly for Box<T> with built-in dereferencing, vs cell::RefMut<T> using the Deref/DerefMut traits.

fn f(x: &mut Box<(u8, u8)>) {
    let r1 = &mut x.0;
    let r2 = &mut x.1;
    std::mem::swap(r1, r2);
}

vs

fn f(x: &mut std::cell::RefMut<(u8, u8)>) {
    let r1 = &mut x.0;
    let r2 = &mut x.1;
    std::mem::swap(r1, r2); // compilation error
}

but the latter can be saved using

fn f(x: &mut std::cell::RefMut<(u8, u8)>) {
    let r = &mut **x;
    let r1 = &mut r.0;
    let r2 = &mut r.1;
    std::mem::swap(r1, r2);
}

or

fn f(x: &mut std::cell::RefMut<(u8, u8)>) {
    let (ref mut r1, ref mut r2) = **x;
    std::mem::swap(r1, r2);
}
1 Like

So, this is just an extension of your point that when thinking about lifetimes and borrows one should think about the desugared versions where method calls t.met() are resolved as {Type of t}::method(self) and operators t op y are resolved as <{Type of T} as {Trait related to the operator>}::Op(self, y) and the additional point that even though v[1] seems like a univocal expression, it desugars to two different things.i.e. if v is a vector it uses Index and IndexMut if v is a slice it does not go through those traits.

And surprisingly, the ones that do not use trait indirection are better integrated with borrowchecker so that borrowchecker can track disjointness of the references more easily.

I think it is surprising because the whole reason of implementing operators as traits is that it is supposed to allow you to integrate your own user defined types with the rest of the language so that they should be like primitive types, i.e. whether a type is built in or user defined should be an implementation detail not a API concern. :frowning:

(AFAIU) field expresions like a.f also have this integration and in that case it does not matter if it is a user defined struct, which is a relief. Are there other expressions that one should be aware of?