[Pre-RFC] Reborrow trait

language design
21

If you don't mind / want me to do a full editing / rewrite pass for readability, I can and am willing to do so, if you ask. I wouldn't do that without prompting, though; that's too close to being intellectual theft[1].

Although, as a disclaimer, I'd end up rewriting pretty much everything into my voice instead of preserving yours, for my own convenience. (I'm capable of copyediting that isn't a content rewrite, but I don't do that for free generally, it takes too much effort.)

  1. Although one allowable by an assumed MIT OR APACHE-2.0 license, given attribution. ↩︎

22

If you're willing to go that far, I absolutely will not say no! Of course, I'm the biggest fan of my own voice[1] but I'm an even bigger fan of the idea of having a Reborrow RFC accepted and implemented[2].

Some notes on the current draft that I think are worth considering:

  1. As currently devised, the Reborrow and CoerceShared both look and feel very much like derive-traits. Maybe they should be proposed as such?
  2. The current formulation allows Reborrow + CoerceShared: Clone + !Copy + !Drop types and would not call their Clone impl on reborrow. This seems weird; why does reborrowing disable the value temporarily, but you're free to Clone it to get an extra copy? Could we somehow force the "reborrowable typespace" into two distinct halves: Copy and !Clone?
  3. An alternative to the proposed logic for finding the "terminal" or "leaf" reborrowable (as opposed to Copy) fields in a reborrowable struct would be the PhantomExclusive and PhantomShared marker types I mentioned above. This is a "stronger" definition in the sense that it can define &mut and &, whereas the current draft's definition implicitly relies on PhantomData<&()> kind of fields taking care of holding the lifetime.
  4. There are some places where I might still be talking about lifetime narrowing, which is of course wrong. True reborrowing doesn't narrow the lifetime, eg. in &mut T -> &mut T both references have the same lifetime. It's just the implied, "outer" 'a in 'a &mut T that is a different, smaller one on the right side.
  5. I did not fully think out the method resolution algorithm and where to slot CoerceShared into it. There's probably an interaction with Deref, and maybe even with DerefMut, that we'd want to get but might not be there right now. eg. maybe we'd want Mut<'_, T> to automatically coerce itself into Mut<'_, U> through a DerefMut chain of Mut<T> -> Mut<U>[3]? And the same for Deref chaining from Mut<T> or Ref<T> to Ref<U>.

  1. Honestly, why do I re-read my own blog posts and re-watch my own talks so frequently? It doesn't seem normal or healthy. ↩︎

  2. I've been looking into the rustc code a little so that I could start at least a basic implementation scaffold for it, maybe to go with the RFC. I don't plan on just getting the RFC accepted and then waiting on my laurels for someone else to do the compiler work; pair programming would be ideal. ↩︎

  3. This would probably appear from to have a blanket DerefMut<Target = Mut<U>> for Mut<T> where T: DerefMut<Target = U>. ↩︎

23

The way you've explained this seems overly complicated. It's almost equivalent to:

To transitive-reborrow a place, for each direct subplace:

  • If the type of that subplace implements Copy, mark it as borrowed. (By-mut for Reborrow, by-ref for CoerceShared).
  • Otherwise, transitive-reborrow the subplace.

If there are no subplaces, mark the entire place as borrowed.

But this feels really odd. Essentially, we mark all types as borrowed, except we do so fieldwise? Plus, there's the exception for the top-level, e.g.:

So… IIUC, if I have struct A(()); and reborrow a place a: A, then a is marked as borrowed, because all of its fields impl Copy. If I have struct B { a: A, b: () } and reborrow a place b: B, we ignore b.b and borrow b.a.0. Then for struct C { b: B }, we borrow c.b.a.0 and c.b.b.

Whatever the reborrowing algorithm is, it should be compositional; reborrowing a type should be equivalent to reborrowing (or copying) its fields. The special case for a type with mixed Copy and non-Copy fields only at the top level is extremely odd.

1 Like
24

FWIW, this is also an issue with Copy — copying a value does not clone it. And there's technically-unsound specialization in the compiler because of this: e.g. when you Clone a Vec, it'll Copy its contents if it can, not Clone them.

1 Like
25

Mmm, I at least did not intend to write a top-level-only special case. The algorithm in the reference level explanation should be fully independent of the "level" it's on. And it was my intention that the special case of mixed Copy and non-Copy fields works on any level of the struct, no matter how shallow or deep.

What I intended with the "scope does not keep/mark original source used" and the algorithm was that reborrowing is a full FRU on the entire structure of the type being borrowed, recursively. This means that "higher levels" of a deep type structure are created from individual fields, and only the deepest levels actually "borrow" / reborrow from the source struct. eg. with the struct C there we'd perform the memory level creation of the reborrowed C like so:

struct C {
  b: B {
    a: A(source.b.a.0),
    b: source.b.b,
  }
}

But if we write this in Rust today, it would of course not keep source used because both the fields that we refer to in source are just () and can be copied from the source. The intention of the algorithm is to find the fields of the source struct that need to be marked as used, even though we've simply copied Copy data out of them. In this case, assuming A, B, and C are all !Copy, then the only one marked as used would be source.b.a. We indeed effectively ignore source.b.b / do not mark source.b as used by the new B that we create, because the () field in it is not really something that reborrows anything.

Compare this to a hypothetical custom reborrowable Vec type made out of a Mut: Reborrow + !Copy of some kind:

struct Vec<'a, T> {
  ptr: Mut<'a, T>,
  len: usize,
  cap: usize,
}

When we reborrow this Vec, we only effectively reborrow the ptr field and just copy the rest. If we did also reborrow the other fields, and then proceeded to destructure the Vec into its component parts while dropping ptr, the remaining len and cap values should not keep the source Vec used. Not even if someone for some reason made the fields be custom LifetimeUsize<'a>(usize, PhantomData<&usize>) types that implement Copy.

26

I was more pondering about the weirdness around a custom exclusive reference type that is still Clone, and what that might mean. But maybe it's not a problem? Turning that Mut<'_, T> into a &mut T through eg. DerefMut would anyway require unsafe {}, and if your Mut: Clone then that DerefMut can trigger UB if you've made clones of the Mut but that's on your DerefMut impl's internal unsafe {} block. not on the DerefMut itself.

27

The underlying issue, though, is that every type is, at some level, made up of Copy data. Let's look at that example:

struct Vec<'a, T> {
    ptr: Mut<'a, T>,
    len: usize,
    cap: usize,
}

To reborrow v: Vec, we copy v.len and v.cap and reborrow v.ptr. Ok, so what is Mut?

struct Mut<'a, T> {
    ptr: NonNull<T>,
    _lt: PhantomCovariantLifetime<'a>,
}

To reborrow m: Mut, we… copy m.ptr and m._lt.

The only base case is to copy data. If we mark the source of a non-Copy reborrow as used, then reborrowing v: Vec marks v as used.

I think your “if it has any !Copy fields” clause is supposed to be the base case; if a type has only Copy fields (but isn't itself Copy), instead of copying each field, we mark the entire place as used.

There's at least some logic to this special case, as it makes implementing Copy or not actually impact what a place-to-value conversion does. But it makes the operation feel strangely ad-hoc, because it isn't properly compositional anymore; reborrowing isn't just reborrowing each of the fields, like copying and moving each are.

Perhaps a possible resolution is to say that reborrowing reborrows the source place as a single unit by default, but when you derive Reborrow you can mark fields as #[reborrow], in which case those fields are transitively reborrowed and the other fields are copied.

The other "clean" option I can think of is a lang item wrapper type which doesn't get recursed through for the purpose of reborrowing. But that feels like the wrong default to me.

Another more involved resolution could be to make decisions based on what field(s) capture a lifetime parameter? If any Copy fields capture a lifetime, mark all fields that capture that lifetime as used, and recurse on any fields that don't capture such a lifetime. The reborrowing operation is fundamentally tied to the concept of lifetimes, after all.

28

FYI I'm still thinking about and planning to do this, I'm just passively trying to come up with (what I can see as being) a more “principled” way of handling the reborrowing semantics, or at least of explaining them.

I think basing it on lifetime capture works as we want it to. But the tricky part to principlize is the ability for shared reborrows. I'll use the polonius method of discussing regions and loans here.

First, we need to determine what exactly a reborrow of &mut looks like. x: &'a mut i32 captures a single lifetime. As this region parameter is covariant, the place to value operation for x loads a value of type &'b mut i32 where 'a <: 'b[1]. For a simple place to value, x is moved from and whether this covariance actually applies is unobservable, as any attempt to do so adds a new site for the variance to be applied. Coercion

For a simple place to value, x is moved from and uninitialized, and while 'b is allowed to contain a larger set of loans[2], no new loans are naturally introduced. When this conversion is done at a coercion site[3], however, things get a bit more interesting, or when reborrowing is done manually.

error[E0382]: use of moved value: `x`
 --> src/lib.rs:3:5
  |
1 | pub fn f(x: &mut i32) -> &mut i32 {
  |          - move occurs because `x` has type `&mut i32`, which does not implement the `Copy` trait
2 |     let out = x;
  |               - value moved here
3 |     *x;
  |     ^^ value used here after move

error[E0503]: cannot use `*x` because it was mutably borrowed
 --> src/lib.rs:3:5
  |
1 | pub fn f<'a: 'b, 'b>(x: &'a mut i32) -> &'b mut i32 {
  |                  -- lifetime `'b` defined here
2 |     let out = &mut *x;
  |               ------- `*x` is borrowed here
3 |     *x;
  |     ^^ use of borrowed `*x`
4 |     out
  |     --- returning this value requires that `*x` is borrowed for `'b`

Unlike a move, x is not moved from, but instead, it's reborrowed. Critically to how reborrowing works, though, x itself isn't borrowed; the place *x is loaned. The region b requires all of 'a's loans to remain valid ('a <: 'b), as well as requiring that (as it's a mutable reborrow) *x remain unreferenced.

If 'b's loans reference x, then, how come out can be returned from the function without referencing any function local values/temporaries ('b <: fn)? It's actually quite simple: 'b doesn't care about the x place expiring, just that the place accessed at *x isn't inspected in a way that invalidates the mut loan. Most uses of x are considered as invalidating the loan of *x immediately, but not all:

pub fn f<'a>(mut x: &'a mut i32, y: &'a mut i32) -> &'a mut i32 {
    let out = &mut *x;
    x = y;
    out
}

For a principled approach using the existing borrow region language and framework, I think we want a lang type PhantomMut<'a> which acts like &mut () except that it's zero sized. Then reborrowing can just work with loans on *p. The other alternative is to allow loans to block place reads but not writes as a "first class" concept (instead of derived from not allowing dereference of that place's current value) and utilize that… but we'd still need some avenue to distinguish copied fields from reborrowed fields at the base case. And "if all fields are Copy, reborrow them" just doesn't feel like a principled solution[4].

(In effect, compiler messages don't ever say "x is reborrowed," they say "*x is borrowed.")

Then the final wrinkle is that this adds new hidden inferred type-level distinctions between type lifetime parameters, similar to variance and implied bounds. Unlike those, however, the effect is restricted to opt in via impl Reborrow, so shouldn't be that big of a deal imo. But how it interacts with privacy, and in particular for types with only partially public fields, isn't straightforward. It's purely restrictions that API could already imply, IIUC, but it should still be noted.

  1. This notation means the same as 'a: 'b in Rust source code, but it emphasizes the subset-equal relation. Specifically, a region 'a is a set of loans where invalidating any of the loans that a value captures in its region parameters invalidates the value. As the b lifetime has a superset of restrictions, invalidating 'a must invalidate 'b, but invalidating 'b may not invalidate 'a, thus we can say colloquially that 'a "outlives" 'b.

    I do think a lot of advanced Rust users can take this understanding for granted sometimes. It can be more intuitive to think of longer/shorter lifetimes more directly, which makes formally discussing the relations between lifetimes more difficult. ↩︎

  2. It might if, for example, unifying 'b with some other lifetime(s), in which case the region with (at least) the union of the sets of loans is selected. ↩︎

  3. Caveat: if the mutable reference is covered by a generic (e.g. std::convert::identity(x)), then x is not at a conversion site. However, if the mutable reference is not fully contained in a generic type inference variable at the use site (e.g. identity::<&mut _>(x)), then it is a valid coercion site.

    I made a collection of fun cases over on urlo while writing this. ↩︎

  4. Yes, if you want all fields to be copied, you can and should impl Copy instead of just Reborrow. But it's weird for reborrow to be a mostly structural operation except for one special case. Plus then there's the possibility of polonius or some other smarter borrow checking that's more control flow sensitive refining how precise local borrowck is beyond today's NLL (e.g. &x but known to only access x.field, i.e. implicit local borrow splitting), so framing user type reborrowing in working terms of phantom places is more useful to future work. Instead of baking in exactly how reborrows currently function. ↩︎

29

Hi, sorry it's taken me a bit of time to get back here. I was traveling for a week.

I think your “if it has any !Copy fields” clause is supposed to be the base case; if a type has only Copy fields (but isn't itself Copy), instead of copying each field, we mark the entire place as used.

Yeah, I think this is what I was at least trying to say. A reborrowable type that is internally fully Copy but is not itself !Copy should mark its "reborrow source" as used for the duration of the reborrow result's lifetime (existence, not the captured lifetime).

So when reborrowing Vec we find a field that is not !Copy; ie. the Vec itself will not get marked as used. We recurse into the ptr: Mut field and that type is made out of fully Copy fields so we mark the vec.ptr as used.

I'm not sure if this makes the operation not-compositional, though. Any Mut field in any type will always be marked as used on reborrow since its internals will always all be Copy (generics could change that though). The only "non-compositional" part is that any type's reborrowing logic is dependent on its field types in a sort of "boolean or" sort of way, maybe?

I'd argue that something like a #[reborrow] trait would make things less compositional, as then you could have two types Vec and Vec2 where in one case Mut is recursed into and in another it isn't.

Regarding lifetime capture, I am very interested in figuring out if we could make that work as the basis of the reborrow. I'm just wondering about my use-case example of GcScope<'a, 'b> where 'a is an exclusive lifetime and 'b is a shared lifetime. Since GcScope wouldn't be Copy, we'd have to recurse into the type to separate the two lifetimes from one another. But then inside of it, the two lifetimes are currently both captured by PhantomData: Copy fields: how do we now figure out that the field carrying 'a should be marked as used and 'b should be left unused.

Note: I think your

If any Copy fields capture a lifetime, mark all fields that capture that lifetime as used, and recurse on any fields that don't capture such a lifetime.

is the wrong way around: reborrowing &'a T is just a copy and should not mark the original reference as used (disabled for reads and writes). Capturing a lifetime on a field that is !Copy is the interesting case, ie. &'a mut T.

I'm not sure that thinking of a 'a <: 'b lifetime "subset-equal" relation is useful here. AFAIU, rustc does not perform any lifetime subsetting during reborrowing, so trying to introduce such an operation is just reference-level fiction that leads one astray. The 'a in &'a mut T is effectively the lifetime of the T anyways, the validity of the data or as you and the compiler puts it, a borrow on T. Reborrowing &mut T never changes that validity.

I prefer thinking of the reference type's "owned lifetime" (capitalised here for effect), so eg. let original: 'A &'a mut T; this is the same exclusive reference to T as before where T is valid for 'a, but the exclusive reference is valid for 'A. Reborrowing this creates a new exclusive reference let derived: 'B &'a mut T where 'A <: 'B, and the original gets disabled for the lifetime 'B.

Conceptually I think of this as the same as let original: Vec<T>; and let derived = original;, ie. a move, just with a "return move" happening automatically when derived is dropped: the value we're acting upon here is a move-only value, and it happens to hold within it an exclusive reference to data that is valid for some duration of time. Moving the value doesn't change validity of the data.

But, of course this is all the same stuff as you're saying as well, just in different words and perhaps a slightly different viewpoint.

This may indeed be the best choice; this is then the PhantomExclusive and PhantomShared that I suggested earlier. The hidden type-level distinction on lifetimes is definitely a pain, but luckily it's a pain that already somewhat exists in the compiler (with exclusive references and Pin reborrowing), so maybe it's not that bad?

Regarding privacy, my immediate thought is that reborrowing does not relate to field publicity at all. Implementing Reborrow for a type can only be done in the crate that defines said type, so all of its fields can (conceptually) be accessed by the reborrow action. The compiler of course also sees all the fields and cares not one whit about the publicity of the fields. In my GcScope<'a, 'b> case none of the fields are public to users, but reborrowing the type should still work equally well. Even if the fields were public and users could eg. destructure the GcScope<'a, 'b> into Gc<'a> and Scope<'b>, the reborrowing should still work the same.

As for destructuring a type that has some private reborrowed fields and some public reborrowed or copy fields, the public reborrowed fields of course stay alive past the destructuring while the private fields effectively drop at the destructuring site. Or so I'd expect things to work.