# Tree Borrows explained

**URL:** <https://internals.rust-lang.org/t/tree-borrows-explained/18587>\
**Category:** Unsafe Code Guidelines\
**Created:** [March 27, 2023, 3:55pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587 "2023-03-27T15:55:46Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [March 27, 2023, 3:55pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/1 "2023-03-27T15:55:46Z")

</div>

The recent [merge of Tree Borrows into Miri](https://github.com/rust-lang/miri/pull/2785) was unfortunately not immediately accompanied by an example-driven explanation.

This new [blog post](https://perso.crans.org/vanille/treebor) remedies that issue. It is by no means short, but it is structured so that reading only a prefix provides an incomplete-but-not-wrong model.

I look forward to any

- examples of code that would be expected to be UB but are not according to TB
- examples of code that TB declares UB but should not be
- suggestions of codebases that TB should be tested on (already tested: `stdlib`, `regex`, `tokio`, `rand`, `hashbrown`)

Note: this is mostly unrelated to the [other model sharing the same name](https://internals.rust-lang.org/t/improve-upon-stacked-borrows-by-introducing-a-tree/16576), in that it addresses the same issue but in a completely different way.

---

<div class="post-metadata">

**Author:** ![comex](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/comex/32/2587_2.png) [@comex](https://internals.rust-lang.org/u/comex)\
**Post date:** [March 27, 2023, 6:24pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/2 "2023-03-27T18:24:38Z")

</div>

Nice! From a quick lookover it looks quite informative and I look forward to reading it in full.

---

<div class="post-metadata">

**Author:** ![matklad](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matklad/32/12266_2.png) [@matklad](https://internals.rust-lang.org/u/matklad)\
**Post date:** [March 28, 2023, 8:50am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/3 "2023-03-28T08:50:42Z")

</div>

> Example: `copy_nonoverlapping`

Am I correct that this fixes the most practically annoying issue in SB where it’s too easy to accidentally borrow something, and then get punished, even if you don’t actually use that?

That is, that TB would fix [Vec::push invalidates interior references even when it does not reallocate · Issue #60847 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/issues/60847) by making analysis smarter, without requiring changes to the unsafe code?

---

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [March 28, 2023, 9:19am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/4 "2023-03-28T09:19:08Z")

</div>

Yes, even if you create a mutable reference you pay the cost of a write access only on locations you _explicitly_ write through. Reborrowed locations that are not written to only pay the cost of a read access.

In the example you linked (since there is no reallocation) `v.push(1)` never writes to `v[0]` and thus does not disable `v0`. The most closely related piece of code that would _not_ be accepted by TB needs two more write accesses:

```rs
fn main() {
    let mut v = Vec::with_capacity(10);
    v.push(0);
    let v0 = unsafe { &mut *(&mut v[0] as *mut _) };
    *v0 += 1; // v0: Reserved -> Active
    v.push(1); // v0: Active -> Frozen
    *v0 += 1; // Write through Frozen is UB
}

```

---

<div class="post-metadata">

**Author:** ![matklad](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matklad/32/12266_2.png) [@matklad](https://internals.rust-lang.org/u/matklad)\
**Post date:** [March 28, 2023, 9:23am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/5 "2023-03-28T09:23:07Z")

</div>

Oh, this is absolutely brilliant then! Looks like mere mortals can now write sound unsafe code again ❣

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [March 28, 2023, 11:36am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/6 "2023-03-28T11:36:42Z")

</div>

Yes, that was the hope. 🙂

Now, mind you, this is not free: we may the price of being able to do fewer optimizations for write accesses, since mutable references are only considered writable if they have ever written to. So discussions will have to be had about the trade-offs here. The idea is that we now have two points in the design space (Stacked Borrows and Tree Borrows): the former prioritizing optimizations, the latter prioritizing supporting the main code patterns that turned out to be problematic with Stacked Borrows. The final model might well sit somewhere between the two, but that discussion is much easier to have with concrete proposals at hand.

> [@Vanille-N](#):
>
> In the example you linked (since there is no reallocation) `v.push(1)` never writes to `v[0]` and thus does not disable `v0`. The most closely related piece of code that would _not_ be accepted by TB needs two more write accesses:
> 
> ```rust
> fn main() {
> let mut v = Vec::with_capacity(10);
> v.push(0);
> let v0 = unsafe { &mut *(&mut v[0] as *mut _) };
> *v0 += 1; // v0: Reserved -> Active
> v.push(1); // v0: Active -> Frozen
> *v0 += 1; // Write through Frozen is UB
> }
> 
> ```

That is with the old `Vec` implementation, right? Current `Vec` should accept this code since `v.push` does not create a reference to the entire vector content any more.

So, the bugfix for [#60847](https://github.com/rust-lang/rust/issues/60847) is still important.

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [March 29, 2023, 3:00am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/7 "2023-03-29T03:00:56Z")

</div>

I quite like this! I agree that this model more closely matches my model of the average developer's understanding of the borrow rules than SB, though I have a hard time putting into words exactly how or deriving implications more interesting than those spelled out by the OP.

I have a few clarifying questions for my own benefit.

Clarification: if you pass a reference to a function, the protector includes a reborrow and does a phantom read, throwing UB if the tag is disabled, correct?

Question: when you pass a mut reference to a function, do the protector semantics function in such a way that the tag already being Frozen is UB? I know they're leaving Reserved as-is until an actual write happens.

Clarification: shared mutability is handled via the unexplained `ty_is_freeze` query: is this currently using the `UnsafeCell` tracking which is field granular (for `struct`s only, infectious for `enum`/`union`) or is it always a single yes/no answer for the entire reborrowed range?

Clarification: `Unpin` isn't mentioned in the state automaton; is it correct then that `Unpin` only impacts when a new borrow is derived, and not when read/writes are done?

Clarification: what interaction of rules make it so `&mut impl !Unpin` doesn't get `noalias` on function boundaries with protectors but `&mut impl Unpin` does? This wasn't super clear to me on the first read through at least.

Question: how are `Unpin`/`Freeze` handled for the range of the allocation outside of the known range of the reborrowed type? (For `extern type`, you at least have the `extern type` to do type queries on, but for other cases you just don't know. Personally, I'm fine with strict borrow subranges even though it breaks `*addr_of!(v[0])`, requiring the use of `extern type` to get delayed retagging semantics. But will admit this can still cause some issues, e.g. with allocators storing meta before the returned pointer.)

Question: if a function takes a shared reference derived from a writable reference and writes to it, and that's the last access that ever happens, when/is that UB? For some reason I'm having trouble mentally tracking that at the moment, for TB or for SB. (Context derived from the previous: deallocating from a child provenance, would that be able to jump up to the root provenance or would it be UB because it's working at a derived provenance without write/dealloc permission? Potentially relevant for `Box<T> -> &'static T -> Box<T>`.)

Interesting observation: because `&mut` borrows start as the two-phase reserved stated, `&mut` borrow splitting just falls out of the model without any special handling, even if it were to keep fully eager instead of delayed tag reborrowing. This is evident from the walkthrough of the disjoint fields example.

Interesting observation: this isn't what TB is doing. But if all retagging is delayed (i.e. the phantom read on reborrow doesn't undelay the retag), this alone makes the spurious speculative write an incorrect optimization (and also would for reads, which is bad). This suggests an interesting potential middle ground between full two-phase and no two-phase: non static two-phase mut borrows could do the phantom read (putting them in the Reserved state) and then make a delayed phantom write transition to Active. This would I believe allow moving writes before reads again but _I think_ still retain some of the benefit of being two-phase (not actually requiring uniqueness unless written through). On the other hand doing so makes the state more complicated (it's basically another state between Reserved and Active; let's say Speculated) for speculative and likely quite minimal benefit. A more realistic middle ground would be to make function protectors activate

---

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [March 29, 2023, 7:03am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/8 "2023-03-29T07:03:14Z")

</div>

> [@CAD97](#):
>
> Clarification: if you pass a reference to a function, the protector includes a reborrow and does a phantom read, throwing UB if the tag is disabled, correct?
> 
> Question: when you pass a mut reference to a function, do the protector semantics function in such a way that the tag already being Frozen is UB? I know they're leaving Reserved as-is until an actual write happens.

Protector semantics described here allow a protected mutable reference to be `Frozen`, as long as it never became `Active`, i.e. it went directly from `Reserved` to `Frozen` because of a foreign read.

The case you're describing is slightly different: if the parent is `Frozen` and is reborrowed mutably, then this creates a `Reserved` child of `Frozen`. As long as you only read, everything is fine. If you ever try to write then UB will be triggered by the `Frozen` parent, not by the `Reserved` child.

Another way of saying this: `Unpin` `&mut`s start out `Reserved`. No exceptions. However they can have ancestors that are `Frozen` and these will block writing.

---

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [March 29, 2023, 7:15am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/9 "2023-03-29T07:15:47Z")

</div>

> [@CAD97](#):
>
> Clarification: shared mutability is handled via the unexplained `ty_is_freeze` query: is this currently using the `UnsafeCell` tracking which is field granular (for `struct`s only, infectious for `enum`/`union`) or is it always a single yes/no answer for the entire reborrowed range?
> 
> Clarification: `Unpin` isn't mentioned in the state automaton; is it correct then that `Unpin` only impacts when a new borrow is derived, and not when read/writes are done?
> 
> Clarification: what interaction of rules make it so `&mut impl !Unpin` doesn't get `noalias` on function boundaries with protectors but `&mut impl Unpin` does? This wasn't super clear to me on the first read through at least.
> 
> Question: how are `Unpin`/`Freeze` handled for the range of the allocation outside of the known range of the reborrowed type? (For `extern type`, you at least have the `extern type` to do type queries on, but for other cases you just don't know. Personally, I'm fine with strict borrow subranges even though it breaks `*addr_of!(v[0])`, requiring the use of `extern type` to get delayed retagging semantics. But will admit this can still cause some issues, e.g. with allocators storing meta before the returned pointer.)

`Freeze` is _not_ granular:

```rs
// computed exactly once per reborrow
// src/borrow_tracker/tree_borrows/mod.rs
// in `fn from_ref_ty` at L114
let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.param_env());

```

`Unpin` does indeed only matter at reborrow time, where `Unpin`s get their own tag and `!Unpin`s don't. As for the why, see [UCG #381: `&mut impl !Unpin` are not `dereferenceable`](https://github.com/rust-lang/unsafe-code-guidelines/issues/381)

Since the `Freeze` and `Unpin` properties are not checked granularly, they are applied identically to out-of-range locations. That's a very debatable aspect of the model, but for now it's in line with TB being "maximally permissive" and can totally be changed if deemed problematic.

---

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [March 29, 2023, 7:18am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/10 "2023-03-29T07:18:31Z")

</div>

> [@CAD97](#):
>
> Interesting observation: because `&mut` borrows start as the two-phase reserved stated, `&mut` borrow splitting just falls out of the model without any special handling, even if it were to keep fully eager instead of delayed tag reborrowing. This is evident from the walkthrough of the disjoint fields example.

Only as long as you don't write between the two reborrows though...

---

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [March 29, 2023, 7:23am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/11 "2023-03-29T07:23:18Z")

</div>

> [@CAD97](#):
>
> Question: if a function takes a shared reference derived from a writable reference and writes to it, and that's the last access that ever happens, when/is that UB? For some reason I'm having trouble mentally tracking that at the moment, for TB or for SB. (Context derived from the previous: deallocating from a child provenance, would that be able to jump up to the root provenance or would it be UB because it's working at a derived provenance without write/dealloc permission? Potentially relevant for `Box<T> -> &'static T -> Box<T>`.)

A shared derived from a mutable is a `Frozen` child of `Active`. Trying to write through that is an attempted write through `Frozen`, so UB.

Deallocation [will first perform a fake write](https://github.com/rust-lang/miri/blob/dd76870734fa762193ffe08489753c4cd616ab0c/src/borrow_tracker/tree_borrows/tree.rs#L334). If the pointer you try to deallocate through is or has a parent that is Frozen, then this is UB.

---

<div class="post-metadata">

**Author:** ![y86-dev](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/y86-dev/32/9867_2.png) [@y86-dev](https://internals.rust-lang.org/u/y86-dev)\
**Post date:** [March 29, 2023, 8:01am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/12 "2023-03-29T08:01:23Z")

</div>

> [@Vanille-N](#):
>
> `Freeze` is _not_ granular:
> 
> ```rust
> // computed exactly once per reborrow
> // src/borrow_tracker/tree_borrows/mod.rs
> // in `fn from_ref_ty` at L114
> let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.param_env());
> 
> ```

Is this the reason for why this is not UB under TB:

```rust
use core::{cell::Cell, ptr::addr_of};

struct WithCell {
    _cell: Cell<()>,
    value: u64,
}

impl WithCell {
    fn evil(&self) {
        unsafe { *addr_of!(self.value).cast_mut() = 0 };
    }
}

fn main() {
    let with_cell = WithCell {
        value: 42,
        _cell: Cell::new(()),
    };
    println!("{}", with_cell.value);
    with_cell.evil();
    println!("{}", with_cell.value);
}

```

---

<div class="post-metadata">

**Author:** ![alice](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/alice/32/5044_2.png) [@alice](https://internals.rust-lang.org/u/alice)\
**Post date:** [April 3, 2023, 9:10am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/13 "2023-04-03T09:10:02Z")

</div>

It seems like things that take pinned references like `Future::poll` implicitly get a safety requirement along these lines:

> Every `Pin<&mut T>` passed to a pinned method must have the same tag and must remain valid until the destructor runs.

Since otherwise the self-referential object might be keeping around pointers with old invalidated tags.

* * *

Now, since mutable references only create new tags when the type is `Unpin`, the above is normally fine. However, if we create a struct that is unconditionally `Unpin` and store a future inside it (like happened with `poll_fn`), then it is very easy to end up violating the above safety requirement for pinning.

I suggest that the condition for when mutable references create new tags should be expanded so that it ignores `impl Unpin` and just looks whether any field is `!Unpin` recursively.

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [April 3, 2023, 10:57am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/14 "2023-04-03T10:57:14Z")

</div>

> [@alice](#):
>
> I suggest that the condition for when mutable references create new tags should be expanded so that it ignores `impl Unpin` and just looks whether any field is `!Unpin` recursively.

(I've been planning to bring a write-up/proposal with a suggestion to introduce a separate `FreezeMut` unsafe autotrait for the aliasing semantics currently attached to `Unpin`, like is currently the case with `Freeze` for `UnsafeCell`. But finding the time to finish the write-up has been difficult.)

---

<div class="post-metadata">

**Author:** ![DeltAlice](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/deltalice/32/10753_2.png) [@DeltAlice](https://internals.rust-lang.org/u/DeltAlice)\
**Post date:** [April 12, 2023, 2:13pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/15 "2023-04-12T14:13:24Z")

</div>

Here is some examples showing closures are very different. I have no idea how compiler treat them so that tb's behavior becomes very confusing.

```rust
use std::ptr::addr_of;

fn pass() {
    let a = 0;
    unsafe {
        *addr_of!(a).cast_mut() = 5;
    }
}

fn rejected() {
    let a = 0;
    let f = move || unsafe {
        *addr_of!(a).cast_mut() = 5; // UB!
    };
    f();
}

fn main() {
    pass();
    rejected();
}

```

But if the closure is boxed and returned immediately tb would calm on some occasions:

```rust
use std::ptr::addr_of;
// Works for Box<dyn FnOnce()->()> too
// However impl Fn/FnMut/FnOnce and Box<dyn FnMut> will make it rejected
fn pass() -> Box<dyn FnMut() -> ()> {
    let a = 0;
    Box::new(move || unsafe {
        *addr_of!(a).cast_mut() = 5;
    })
}

fn rejected() -> Box<dyn FnMut() -> ()> {
    let a = 0;
    // An intermediate variable annoys TB
    let f = Box::new(move || unsafe {
        *addr_of!(a).cast_mut() = 5; // UB!
    });
    f
}

fn main() {
    pass()();
    rejected()();
}

```

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [April 12, 2023, 3:05pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/16 "2023-04-12T15:05:14Z")

</div>

> [@alice](#):
>
> It seems like things that take pinned references like `Future::poll` implicitly get a safety requirement along these lines:
> 
> > Every `Pin<&mut T>` passed to a pinned method must have the same tag and must remain valid until the destructor runs.
> 
> Since otherwise the self-referential object might be keeping around pointers with old invalidated tags.

Yes. FWIW this is also basically the case in Stacked Borrows, except it doesn't have to be literally the same tag, it can just be a tag in the "same SharedReadWrite group" -- TB just collapses that entire group into a single tag.

> [@alice](#):
>
> I suggest that the condition for when mutable references create new tags should be expanded so that it ignores `impl Unpin` and just looks whether any field is `!Unpin` recursively.

Wouldn't that just slightly move the issue? The issue you are describing is basically what happened with `poll_fn`, which did show that `impl Unpin` is quite dangerous indeed.

> [@CAD97](#):
>
> (I've been planning to bring a write-up/proposal with a suggestion to introduce a separate `FreezeMut` unsafe autotrait for the aliasing semantics currently attached to `Unpin`, like is currently the case with `Freeze` for `UnsafeCell`. But finding the time to finish the write-up has been difficult.)

Related discussion: [`UnsafeCellMut`](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-opsem/topic/UnsafeCellMut).

---

<div class="post-metadata">

**Author:** ![Vanille-N](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/vanille-n/32/10695_2.png) [@Vanille-N](https://internals.rust-lang.org/u/Vanille-N)\
**Post date:** [April 12, 2023, 3:05pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/17 "2023-04-12T15:05:35Z")

</div>

Confusing behavior indeed. To understand what happens I modified your code a bit to

```rs
use std::ptr::addr_of;

#[path = "../../../tests/utils/mod.rs"]
mod utils;
use utils::macros::*;

unsafe fn pass() {
    let a = 0;
    name!(addr_of!(a));
    print_state!(alloc_id!(addr_of!(a))); // (1)
    let raw = addr_of!(a).cast_mut();
    print_state!(alloc_id!(raw)); // (2)
    name!(raw);
    let f = || {
        print_state!(alloc_id!(raw)); // (3)
        *raw = 5;
    };
    f();
}

unsafe fn rejected() {
    let a = 0;
    name!(addr_of!(a));
    print_state!(alloc_id!(addr_of!(a))); // (1)
    let f = move || {
        let raw = addr_of!(a).cast_mut();
        print_state!(alloc_id!(raw)); // (2)
        name!(raw);
        print_state!(alloc_id!(raw)); // (3)
        *raw = 5; // UB!
    };
    f();
}

fn main() {
    unsafe {
        pass();
        rejected();
    }
}

```

Which prints the following trees

```plaintext
// Trees for `pass`
// (1)
────────────────────────────────────────────────────────────────
0.. 4
| Act| └────<2793=root of the allocation, addr_of!(a)>
────────────────────────────────────────────────────────────────
// (2)
────────────────────────────────────────────────────────────────
0.. 4
| Act| └────<2793=root of the allocation, addr_of!(a)>
────────────────────────────────────────────────────────────────
// (3)
────────────────────────────────────────────────────────────────
0.. 4
| Act| └────<2793=root of the allocation, addr_of!(a), raw>
────────────────────────────────────────────────────────────────

// Trees for `rejected`
// (1)
────────────────────────────────────────────────────────────────
0.. 4
| Act| └────<2826=root of the allocation, addr_of!(a)>
────────────────────────────────────────────────────────────────
// (2)
────────────────────────────────────────────────────────────────
0.. 4
| Act| └────<2830=root of the allocation>
────────────────────────────────────────────────────────────────
// (3)
────────────────────────────────────────────────────────────────
0.. 4
| Act| └─┬──<2830=root of the allocation>
| Frz| └────<2832=raw> Strongly protected
────────────────────────────────────────────────────────────────

```

The relevant diff between these two is that

- in `rejected`, `a` gets reallocated (it changes tag from `2926` to `2830` between `(1)` and `(2)`
- the above explains the disappearance of `addr_of!(a)` from the allocation
- having been reallocated, `a` is no longer a local variable

This is a very debatable choice, but it happens that TB always gives the `Active` permission to the root of the allocation, so it makes no fundamental difference between `let x = 0` and `let mut x = 0`.

---

<div class="post-metadata">

**Author:** ![alice](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/alice/32/5044_2.png) [@alice](https://internals.rust-lang.org/u/alice)\
**Post date:** [April 20, 2023, 9:40am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/18 "2023-04-20T09:40:15Z")

</div>

> [@RalfJung](#):
>
> > [@alice](#):
> >
> > I suggest that the condition for when mutable references create new tags should be expanded so that it ignores `impl Unpin` and just looks whether any field is `!Unpin` recursively.
> 
> Wouldn't that just slightly move the issue? The issue you are describing is basically what happened with `poll_fn`, which did show that `impl Unpin` is quite dangerous indeed.

I agree that it just moves the issue, but I think it moves it more than slightly.

Let's define _self-referential type_ recursively by saying that a type is self-referential if it is `!Unpin`, or if it has a self-referential field. Then, my proposed rule is that creating a mutable reference only creates a new tag if the type is not self-referential.

I claim that it makes triggering the issue a lot more difficult. For example, the `poll_fn` situation would not have happened because `PollFn` has a field that is `!Unpin`, so the `PollFn` struct itself would also be considered self-referential.

To see why, consider operations that take a `&mut T` and create a `&mut U` into the same part of the same allocation. In safe code, this mainly encompasses reborrows and creating references to fields of `T`, but also a few others like coercing from a sized type to an unsized one. As far as I can tell, all of these have the property that if `U` is self-referential, then so is `T`.

However, creating two mutable references to the same thing (they don't necessarily have to exist simultaneously) with different tags can only be done given a mutable reference to something that isn't self-referential. Hence, to create two mutable references to the same self-referential value with different tags, you must at some point convert from `&mut T` to `&mut U` with `T` non-self-referential and `U` self-referential. That can only be done unsafely, and I think it's a quite rare unsafe operation especially in the context of futures.

So in some sense, my suggestion changes the dangerous thing from `impl Unpin` to "convert non-self-referential reference to self-referential reference".

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [April 24, 2023, 2:44pm UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/19 "2023-04-24T14:44:24Z")

</div>

I think basically you are trying to reconstruct what we have with `UnsafeCell` (where `impl Freeze` is not possible since the trait is unstable). If we think that is desirable, I'd much rather have a type that plays the same role for mutable reference aliasing, as in what I [proposed here](https://rust-lang.zulipchat.com/#narrow/stream/136281-t-opsem/topic/UnsafeCellMut).

---

<div class="post-metadata">

**Author:** ![alice](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/alice/32/5044_2.png) [@alice](https://internals.rust-lang.org/u/alice)\
**Post date:** [May 11, 2023, 9:08am UTC](https://internals.rust-lang.org/t/tree-borrows-explained/18587/20 "2023-05-11T09:08:02Z")

</div>

Sure, an `UnsafeCellMut` would work for me too.

[Next page](https://internals.rust-lang.org/t/tree-borrows-explained/18587.md?page=2)