Though this be madness, yet there is method in 't.

More context

1. Hamlet:

   For yourself, sir, shall grow old as I am – if, like a crab, you could go backward.

2. Polonius:

   Though this be madness, yet there is method in 't.

3. Polonius, eventually:

   

::polonius-the-crab

Tools to feature more lenient Polonius-based borrow-checker patterns in stable Rust.

Rationale: limitations of the NLL borrow checker

See the following issues:

• #54663 – Borrow checker extends borrow range in code with early return

• #70255 – Weird error for mutable references in a loop

• #92985 – Filter adapter for LendingIterator requires Polonius (this one marks bonus points for involving GATs and the pervasive LendingIterator example).

• etc.

All these examples boil down to the following canonical instance:

```rust ,compile_fail

![forbid(unsafe_code)]

use ::std::{ collections::HashMap, };

/// Typical example of lack-of-Polonius limitation: get_or_insert pattern. /// See https://nikomatsakis.github.io/rust-belt-rust-2019/#72 fn get_or_insert ( map: &' mut HashMap, ) -> &' String { if let Some(v) = map.get(&22) { return v; } map.insert(22, String::from("hi")); &map[&22] }

error message



```rust
# /*
 error[E0502]: cannot borrow `*map` as mutable because it is also borrowed as immutable
  --> src/lib.rs:53:5
   |
14 |     map: &mut HashMap<u32, String>,
   |          - let's call the lifetime of this reference `'1`
15 | ) -> &String {
16 |     if let Some(v) = map.get(&22) {
   |                      --- immutable borrow occurs here
17 |         return v;
   |                - returning this value requires that `*map` be borrowed for `'1`
18 |     }
19 |     map.insert(22, String::from("hi"));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
# */

Explanation

Click to hide

Now, this pattern is known to be sound / a false positive from the current borrow checker, NLL.

• The technical reason behind it is the named / in-function-signature lifetime involved in the borrow: contrary to a fully-in-body anonymous borrow, borrows that last for a "named" / outer-generic lifetime are deemed to last until the end of the function, across all possible codepaths (even those unreachable whence the borrow starts).

  • a way to notice this difference is to, when possible, rewrite the function as a macro. By virtue of being syntactically inlined, it will involve anonymous lifetimes and won't cause any trouble.

Workarounds

So "jUsT uSe UnSaFe" you may suggest. But this is tricky:

• does your use-case really fit this canonical example?

  • or a variant: will it still fit it as the code evolves / in face of code refactorings?

• even when we know "we can use unsafe", actually using it is subtle and error-prone. Since &mut borrows are often involved in this situation, one may accidentally end up transmuting a & reference to a &mut reference, which is always UB.

• both of these issues lead to a certain completely legitimate allergy to unsafe_code, and the very reassuring #![forbid(unsafe_code)]-at-the-root-of-the-crate pattern.

Non-unsafe albeit cumbersome workarounds for lack-of-Polonius issues

Click to show

• if possible, reach for a dedicated API. For instance, the get_or_insert() example can be featured using the .entry() API:

  ```rust

  ![forbid(unsafe_code)]

  use ::std::{ collections::HashMap, };

  fn get_or_insert ( map: &' mut HashMap, ) -> &' String { map.entry(22).or_insert_with(|| String::from("hi")) } ```

  Sadly, the reality is that you won't always have such convenient APIs at your disposal.

• otherwise, you can perform successive non-idiomatic lookups to avoid holding the borrow for too long:

  ```rust

  ![forbid(unsafe_code)]

  use ::std::{ collections::HashMap, };

  fn get_or_insert ( map: &' mut HashMap, ) -> &' String { // written like this to show the "transition path" from previous code let should_insert = if let Some(_discarded) = map.get(&22) { false } else { true } ; // but should_insert can obviously be shortened down to map.get(&22).is_none() // or, in this very instance, to map.contains_key(&22).not(). if should_insert { map.insert(22, String::from("hi")); } map.get(&22).unwrap() // or &map[&22] } ```

• finally, related to the "this only happens with concrete named lifetimes" issue, a clever non-unsafe albeit cumbersome way to circumvent the limitation is to use CPS / callbacks / a scoped API:

  ```rust

  ![forbid(unsafe_code)]

  use ::std::{ collections::HashMap, };

  fn with_get_or_insert ( map: &' mut HashMap, yield: impl FnOnce( / -> / &' String ) -> R ) -> R { if let Some(v) = map.get(&22) { yield(v) } else { map.insert(22, String::from("hi")); yield_(&map[&22]) } } ```

While you should try these workarounds first and see how they apply to your codebase, sometimes they're not applicable or way too cumbersome compared to "a tiny bit of unsafe".

In that case, as with all the cases of known-to-be-sound unsafe patterns, the ideal solution is to factor it out down to its own small and easy to review crate or module, and then use the non-unsafe fn API thereby exposed 👌.

Enters ::polonius-the-crab

Explanation of its implementation

Click to show

So, back to that "safety encapsulation" idea:

1. let's find a canonical instance of this borrow checker issue that is known to be sound and accepted under Polonius;

2. and tweak it so that it can then be re-used as a general-purpose tool for most of these issues.

And if we stare at the borrow checker issues above, we can see there are two defining ingredients:

• An explicit generic lifetime parameter (potentially elided);
• A branch, where one of the branches returns based on that borrow, whilst the other is no longer interested in it.

The issue is then that this second branch ought to get back access to the stuff borrowed in the first branch, but the current borrow checker denies it.

That's where we'll sprinkle some correctly-placed unsafe to make the "borrow checker look the other way" just for a moment, the right moment.

This thus gives us (in pseudo-code first):

``rust ,ignore fn polonius<'r, T> ( borrow: &'r mut T, branch: impl // generic type to apply to all possible scopes. for<'any> // <- higher-order lifetime ensures the&mut Tinfected with it… FnOnce(&'any mut T) // …can only escape the closure… // vvvv … through its return type and its return type only. -> Option< _<'any> > // <- TheSome/Nonediscriminant represents the branch info. // ^^^^^^^ // some return type allowed to depend on'any. // For instance, in the case ofget_or_insert, this could // have been&'any String(orOption<&'any String>). // Bear with me for the moment and tolerate this pseudo-code. , ) -> Result< // <- we "forward the branch", but with data attached to the fallback one (Err(…)). _<'r>, // <- "plot twist":'anyabove was'r! &'r mut T, // <- through Arcane Magic™ we get to transmute theNoneinto anErr(borrow)> { let tentative_borrow = &mut *borrow; // reborrow if let Some(dependent) = branch(tentative_borrow) { /* within this branch, the reborrow needs to last for'r` / return Ok(dependent); } / but within this branch, the reborrow needs to have ended: only Polonius supports that kind of logic */

// give the borrow back
Err(borrow) // <- without Polonius this is denied

}

This function, ignoring that generic unspecified `_<'…>` return type in
pseudo-code, does indeed represent a canonical example of the borrow checker
issue (without `-Zpolonius`, it will reject the `Err(borrow)` line saying that
`borrow` needs to be borrowed for `'r` so that `dependent` is, and that `'r`
spans until _any_ end of function (the borrow checker bug).

Whereas with `-Zpolonius` it is accepted.

  - [Demo](https://rust.godbolt.org/z/81sn7oK9s)

#### The ArcaneMagic™

The correct use of `unsafe`, here, to palliate the lack of `-Zpolonius`, is to
change:

```rust ,ignore
let tentative_borrow = &mut *borrow; // reborrow

into:

rust ,ignore let tentative_borrow = unsafe { &mut *(borrow as *mut _) }; // reborrow

where unsafe { &mut *(thing as *mut _) } is the canonical way to perform lifetime(-of-the-borrow) extension: the lifetime of that &mut borrow is then no longer tied, in any way, to 'r nor to *borrow.

• Some of you might have been tempted to use mem::transmute. While that does indeed work, it is a strictly more flexible API, which in the case of unsafe, means it's a strictly more dangerous API. With transmute, for instance, when the borrowee has lifetime parameters of its own, those may be erased as well, whereas a downgrade-to-pointer-and-upgrade-back-to-ref operation is guaranteed to "erase" only the outer lifetime of the borrow, leaving the inner type untouched: definitely safer.

The borrow checker no longer holds our hand, as far as overlapped usage of borrow and tentative_borrow is concerned (which would be UB). It is now up to us to ensure no runtime path can ever lead to such borrows overlapping.

And indeed they don't, as the simple branch showcases:

• in the Some branch, the dependent is still borrowing tentative_borrow, and thus, *borrow. But we do not use borrow anymore in that branch, nor in the caller's body, as long as dependent is used. Indeed, signature-wise, we do tell that that dependent return value, of type _<'r>, is borrowing from *borrow, due to that repetition of the 'r name.

• in the None branch, there is no dependent, and tentative_borrow isn't used anymore, so it is sound to refer to borrow again.

In other words:

Though this be unsafe, yet there is soundness in 't.

As an extra precaution, this crate does even guard that usage of unsafe through a cfg-opt-out, so that when using -Zpolonius, the unsafe is removed, and yet the body of the function, as well as its signature, compiles fine (this is further enforced in CI through a special test).

Generalizing it

Option<T<'_>> becomes PoloniusResult<T<'_>, U>

It turns out that we don't have to restrict the branch to returning no data on None, and that we can use it as a "channel" through which to pass non-borrowing data.

This leads to replacing Option< T<'any> > with PoloniusResult< T<'any>, U >

• Notice how the U cannot depend on 'any since it can't name it (generic parameter introduced before the 'any quantification ever