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

  #![forbid(unsafe_code)]
  use ::std::{
      collections::HashMap,
  };
  
  fn get_or_insert(
      map: &mut HashMap<u32, String>,
  ) -> &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:

  #![forbid(unsafe_code)]
  use ::std::{
      collections::HashMap,
  };
  
  fn get_or_insert(
      map: &mut HashMap<u32, String>,
  ) -> &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:

  #![forbid(unsafe_code)]
  use ::std::{
      collections::HashMap,
  };
  
  fn with_get_or_insert<R>(
      map: &mut HashMap<u32, String>,
      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 👌 .

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 that 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):

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 T` infected with it…
        FnOnce(&'any mut T)      // …can only escape the closure…
                    // vvvv        … through its return type and its return type only.
          -> Option< _<'any> > // <- The `Some` / `None` discriminant represents the branch info.
                  // ^^^^^^^
                  // some return type allowed to depend on `'any`.
                  // For instance, in the case of `get_or_insert`, this could
                  // have been `&'any String` (or `Option<&'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": `'any` above was `'r` !
        &'r mut T, // <- through Arcane Magic™ we get to transmute the `None` into an `Err(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

The ArcaneMagic™

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

let tentative_borrow = &mut *borrow; // reborrow

into:

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

None becomes <Err>

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 smuggle non-borrowing data.

This leads to replacing Option< _<'any> > with Result< _<'any>, Err >

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

The FnOnceReturningAnOption trick is replaced with a HKT pattern

Indeed, a FnOnceReturningAnOption-based signature would be problematic on the caller's side, since:

• it infers the higher-order-'any-infected return type of the closure through the actual closure instance being fed;

• but a closure only gets to be higher-order when the API it is fed to explicitly requires it to

  • see https://docs.rs/higher-order-closure for more info.

So this leads to a situation where both the caller and callee expect each other to disambiguate what the higher-order return value of the closure should be, leading to no higher-orderness to begin with and/or to type inference errors.

• Note that the hrtb! macro from https://docs.rs/higher-order-closure, or the actual for<…>-closures RFC such crate polyfills, would help in that regard. But the usage then becomes, imho, way more convoluted than any of the aforementioned workarounds, defeating the very purpose of this crate.

So that _<'any> is achieved in another manner. Through HKTs, that is, through "generic generics" / "generics that are, themselves, generic":

//! In pseudo-code:
fn polonius<'r, T, Ret<'_>> (
    borrow: &'r mut T,
    branch: impl FnOnce(&'_ mut T) -> Option<Ret<'_>>,
) -> Result<
        Ret<'r>,
        &'r mut T,
    >

This cannot directly be written in Rust, but you can define a trait representing the <'_>-ness of a type (HKT in this crate), and with it, use as WithLifetime<'a>::T as the "feed <'a>" operator:

//! Real code!
fn polonius<'r, T, Ret : HKT> (
    borrow: &'r mut T,
    branch: impl FnOnce(&'_ mut T) -> Option< <Ret as WithLifetime<'_>>::T >,
) -> Result<
        <Ret as WithLifetime<'r>>::T,
        &'r mut T,
    >

We have reached the definition of the actual fn polonius exposed by this very crate!

Now, a HKT type is still cumbersome to use. If we go back to that get_or_insert example that was returning a &'_ String, we'd need to express that "generic type" representing <'lt> => &'lt String, such as:

/// Pseudo-code (`StringRef` is not a type, `StringRef<'…>` is).
type StringRef<'any> = &'any String;

/// Real HKT code: make `StringRef` a fully-fledged stand-alone type
struct StringRef;
/// And now express the `<'lt> => &'lt String` relationship:
impl<'lt> WithLifetime <'lt>
   for StringRef // is:  ⇓
{                     // ⇓
                      // ⇓
    type T =         &'lt String    ;
}

Putting it altogether: get_or_insert with no .entry() nor double-lookup