[borrowck] handling of drops invalidating borrows

[arielb1]

Destructors can invalidate borrows of their contents:

struct VecWrapper<'a>(&'a mut Box<u32>);

impl<'a> Drop for VecWrapper<'a> {
    fn drop(&mut self) {
        *self.0 = Box::new(0);
    }
}

fn get_dangling<'a>(value: VecWrapper<'a>) -> &'a u32 {
    let s_inner: &'a Box<u32> = &*value.0; // Borrow (*)
    let result = &s_inner;
    result
    // the destructor of `value`, that runs here, invalidates the borrow (*)
}

Today's rustc's handling of the situation does not provide us much guidance, as can be seen by this example compiling, running, and accessing invalid memory (that is rust-lang/rust#31567).

However, we can't have any drop invalidate all interior references. In the most trivial case, drops of "trivial drop" types, like references, don't even appear in MIR. And even if they appeared, having mutable references invalidate their contents when dropped would basically break all of Rust.

Note that I don't think we have to worry about the interior of containers in the common case, at least until we implement some sort of DerefPure:

fn example_indexmut<'a>(mut v: Vec<&'a mut u32>) -> &'a mut u32 {
    &mut *v[0] //~ ERROR
}

The desugaring converts that into:

// that is equivalent to this MIR modulo panics
t0 = &'a mut v; // can't be a shorter lifetime, because of constraints
t1 = IndexMut::index_mut(t0, 0);
ret = &mut *t1;
drop(v);
storagedead v;

Here the lifetime constraint in IndexMut forces the borrow of v (for t0) to live for 'a, which already causes a borrowck error with the storagedead.

However, technically, we could have a container that "publicly" contains its contents, and which we know can't access its contents because of dropck:

struct NoisyDrop<T>(T);

impl<#[may_dangle] T> Drop for T {
    fn drop(&mut self) {
        println!("Splat!");
    }
}

fn is_actually_sound<'a>(value: NoisyDrop<&'a mut Box<u32>>) -> &'a u32 {
    let s_inner: &'a Box<u32> = &*value.0; // Borrow (*)
    let result = &s_inner;
    result
    // the destructor can't actually access the mutable reference,
    // because it is `#[may_dangle]`, and therefore this function
    // is sound.
}

I don't think that is something we have to strive to implement, at least until someone comes with up with a use-case. So I think a reasonable rule would be that a drop invalidates all contents that are reachable from a destructor. We already do this check today in order to check whether deinitialization/reinitialization would be valid.

However, the question remains - do we want Box to have a destructor, or should it be treated like any other type?

fn foo<'a, T>(x: (SomethingWithADropImpl<&'a mut T>, Box<&'a mut T>, &'a mut T)) -> &'a mut T {
    return &mut x.0; // obviously unsound unless we do dropck trickery - let's ban this
    return &mut x.1; // not sure - allowed today (of course), sound, but do we want it?
    return &mut x.2; // allowed today, probably want to support
}

[arielb1]

NOTE: moved to https://github.com/nikomatsakis/nll-rfc/issues/42

@nikomatsakis had also discovered the following interaction

fn foo() {
    let x = RefCell::new(42);

    let ref_x: &'α RefCell<u32> = &x;
    let inner_ref: Ref<'α, u32> = RefCell::borrow(ref_x);
    // ^ for all you guys following me, `Ref` maintains a borrow to its parent
    // `RefCell` that it clears during its very-not-blind destructor.
    drop(inner_ref);

//  (†)
    RefCell::into_inner(x); // is this legal?
    maybe_unwind();
//  (‡)
}

Here the question is how long α extends. inner_ref is not used in explicit code after it is dropped, so it might seem like α wouldn't be live at †, but there are 2 MIR drops for inner_ref, that can both use ref_x and keep it live:

1. at end of scope at point ‡
2. at the unwind path, which can be reached from maybe_unwind

If we care about it, a simple dataflow analysis could discover that the drop at ‡ is always dead.

The drop at the unwind path looks like it might be a hard nut to crack - there's only 1 unwind path for the function, ending at the single resume terminator. However, I think there's a trick we can use - if a value is uninitialized, then I'm quite sure it can never be live. We could backwards-propagate α live if VARS are initialized dataflow facts, and combine them with forwards-propagated VARS is maybe-initialized facts.

[nikomatsakis]

I'm trying to figure out exactly what you are proposing. It seems like there are two independent things at play. The first is the handling of Drop -- the current rules state that Drop requires all data to be valid, unless it is declared as may dangle (I find this a more helpful way of thinking about it -- what must be valid -- than thinking about invalidation). I'm not sure if this is different from what you are proposing or not!

With respect to Box, I am not sure why you say that &mut x.1 works today. For example, this code doesn't compile:

fn foo<'a, T>(x: Box<&'a mut T>) -> &'a mut T {
    return &mut x;
}

fn main() { }

But this has more to do with overloading Box.

[arielb1]

fn example_box<'a>(mut v: Box<&'a mut u32>) -> &'a mut u32 {
    &mut **v
}

fn main() {}

[arielb1]

The first is the handling of Drop -- the current rules state that Drop requires all data to be valid, unless it is declared as may dangle

That's a constraint on lifetimes, not on borrows.

[arielb1]

I think the confusing thing here is the difference between this issue and #42 - they are actually separate issues.

The root cause here is that (both with NLL and lexical lifetimes) there are 2 ways operations feed into borrow checking (excluding "moveck", which has nothing to do with lifetimes):

1. By introducing a lifetime constraint, forcing borrows to be longer.
2. By introducing accesses, conflicting with pre-existing borrows.

This issue is about accesses, while #42 is about lifetime constraints.

Because values can't be uninitialized while there are active borrows to part of them, dead drops being a no-op is uninteresting to borrowck - if the drop is dead, we already know that there can't be any borrows to it to be invalidated.

[nikomatsakis]

OK, so I had this big response, but in the course of writing it, I think I realized what you are actually talking about.

But first off, let me observe that I think this box example you gave is a bug (though not one I am surprised about). We are supposed to be treating Box as though it implements DerefMut, even though we in fact give it special privilege (because you can move out of it). So that code should error out for the same reason that returning &x[0] if x: Vec<&mut T> would error out. But that code is sort of ad-hoc and I'm not surprised it has holes.

I had kind of assumed we would "fix" this bug. But maybe that will break too much stuff in the wild, so I think now what you are saying is (a) presume that we do NOT fix this issue, but we keep box being "special" as it is today. In that case, we might compare your box example to this other example, which does not use a box:

fn foo<'a>(x: &mut T) -> &mut T { &mut *x }

In this case, the borrow of *x naturally extends past the end of the function -- and right in the middle of it, we have a Drop(x) (which is a no-op, and probably not even included in the CFG) and a StorageDead(x). The latter is permitted even though *x is borrowed precisely because x is an &mut.

So, now the question is: if we tried to extend that same approach to the case where x: Box<&mut T>, would it work? And the concern is that, now, the drop is not a no-op, right? So, presuming it is included in the CFG, we would likely get a borrow-check error for trying to "use" x while **x is borrowed -- and, as you say, the borrow is certainly still live at this point.

An interesting point. It would be nice if we had some rules that also sort of "justified" the drops of references. I agree this is somewhat distinct from "may dangle" -- though not completely unrelated.

[Ericson2314]

I still hope for &move to clean a lot of things up, but for now we can use that as intuition for how the Box-hacks should work:

N.B. struct Box<T>(&move T);

The sequence of actions in https://github.com/nikomatsakis/nll-rfc/issues/40#issuecomment-324118711 is

1. DerefMove the box to get &move &mut T
2. Move out of the outer &move into a local. The outer reference is "marked uninitialized" (or it's type changes but I'm try to play by the rules :)).
3. Drop the outer reference. The box is no longer borrowed and "marked empty" (again, would be a type change).
4. Empty boxes are just freed with nothing done to their contents. One could write a normal destructor to do this since they are unborrowed.
5. Return the value of the local

The key point from this story for today is that empty boxes need not be borrowed.

[nikomatsakis]

So, @pnkfelix has been working on a writeup and prototype implementation of this idea that we had that we called "dangly paths", but I think it offers a promising solution to the problem here. Since he's going to do a more complete write-up, I'll try to just leave a few notes on the high-level concept.

The basic idea is to use the #[may_dangle] annotations to figure out paths that the Drop impl could not possibly "touch" -- more precisely, paths where the the drop impl could not dereference any references found within -- starting from the root of data structure. So, for example, given this structure definition:

struct Foo<T> { // T "may dangle"
  data: (T, T)
}

struct Bar<'a> { // `'a` "may dangle"
  data: &'a mut T
}

struct Baz<'a, T> { // T "may dangle", but not `'a`
  data: &'a mut T
}

Then the set of "dangly paths" for Foo would be (self.data.0, self.data.1); for Bar, the dangly paths would be {self.data}. For Baz, the dangly paths would be {*self.data}. If there are no dangly parameters, then the dangly paths for a given type is the empty set. This concept applies to builtin types too. For example, for &'a T or &'a mut T, the set of dangly paths is self (roughly equivalent to Bar).

The intuition here is that if a lifetime parameter is declared may dangle, then any references with that lifetime could not be accessed by Drop, or else the declaration is wrong. Similarly for generic types.

Now, the idea is that when the Drop executes, it is ok to have a borrow of the referent of some &mut T that is reached via a dangly path (for &T this is also true, but I believe it falls out from &T being copy anyhow and requires no particular special treatment). This follows because if the drop impl were to access the referent of said &mut T, it would be violating its may-dangle attribute: it doesn't know, after all, that the &mut T referent is still valid. (It's essentially a kind of parametricity argument.)

Anyway, there are some subtleties involving nested types and so forth, which is why @pnkfelix was going to do a more complete write-up, but hopefully that's enough to go on for the moment.

---

@Ericson2314 Unless I'm missing something, I think that ideally we wouldn't need to bring&move into play here, in the sense that I think in these examples there is no "move" out of the box. (And, I'd like this to work for things that don't implement Deref at all.)

But it's true that for these examples to work it does rely on the compiler treatingBox<T> specially -- i.e., I wouldn't expect the examples to work with Vec<T>, because the index trait means that when we borrow (say) &mut *v[0], we are really borrowing v to invoke IndexMut (and then &mut **tmp). With box being built-in, if we have a borrow of &mut **box, we actually know better what's going on and don't consider that a borrow of box`.

[Ericson2314]

in the sense that I think in these examples there is no "move" out of the box

Huh? When we return the &mut (or anything else non-Copy) that was inside the box, we should be moving it out of the box. When we do &mut **some_box, must the inner * be viewed as a moving dereference to have full unencumbered access to the outliving inner lifetime?

(FWIW, Vec<T> could work too with an IndexMove that deinitailizes the other contents of the Vec.)

[arielb1]

So, @pnkfelix has been working on a writeup and prototype implementation of this idea that we had that we called "dangly paths"

That looks like a complicated and subtle feature that is only useful in an edge-case (structs with destructors, public borrowable fields, and #[may_dangle] - so not relevant for stable anyway). The betting odds for soundness of may_dangle-related features don't look good.

The "magic dereference" of Box working also relies on the "DerefPure" nature of Box (in addition to its may_dangle nature), which allows trackable references to its interior.

I think we want to wait until we better understand the may_dangle and DerefPure story before implementing this.

[arielb1]

Huh? When we return the &mut (or anything else non-Copy) that was inside the box, we should be moving it out of the box.

But we don't return the &mut that was inside the Box<&mut T>, we reborrow it. There isn't a move in sight. We perform 2 mutable dereferences of the Box, and then borrow the resulting lvalue.

[pnkfelix]

@arielb1 wrote:

That looks like a complicated and subtle feature that is only useful in an edge-case (structs with destructors, public borrowable fields, and #[may_dangle] - so not relevant for stable anyway).

I agree that it is subtle and an edge case. I'm not sure it needs to be complicated. My main motivation for investigating it was because I wanted to understand how to fix the problem in a general way rather than making it solely ties to Box magic.

In the time since I starting looking at this, I have realized (as you point out), that supporting this feature for Box is nonetheless inherently tied to some kind of magic (i.e. DerefPure).

I think we want to wait until we better understand the may_dangle and DerefPure story before implementing this.

I have finished a nll-based prototype that I'l have a PR up for soon. Its small (since nll is itself small). Maybe we can look at that as part of deciding whether to bother implementing something this general in rustc itself. (The main alternative I would expect is for us to just make Box alone carry the necessary magic here, and just have everything else "break" when https://github.com/rust-lang/rust/issues/31567 is fixed, even if their destructors use #[may_dangle].)

[arielb1]

The main alternative I would expect is for us to just make Box alone carry the necessary magic here, and just have everything else "break" when rust-lang/rust#31567 is fixed, even if their destructors use #[may_dangle].

I don't expect that to be so much of a problem - #[may_dangle] is a little-documented unstable feature.

Its small (since nll is itself small).

It's also not that obvious that we won't have soundness problems when translating it to full Rust.

[pnkfelix]

I wrote:

I have finished a nll-based prototype that I'l have a PR up for soon.

That PR is here: https://github.com/nikomatsakis/nll/pull/17

[pnkfelix]

@arielb1 wrote:

I don't expect that to be so much of a problem - #[may_dangle] is a little-documented unstable feature.

I am inclined to agree with that.

(in the long run we may replace #[may_dangle] with something more disciplined (e.g. <T: Live?> ?) that would be intended to become part of stable rust, and so I see this investigation as a kind of early investigation into the possible generalizations that we might make.)

[Ericson2314]

@arielb1

But we don't return the &mut that was inside the Box<&mut T>, we reborrow it. There isn't a move in sight. We perform 2 mutable dereferences of the Box, and then borrow the resulting lvalue.

Ah ok, my bad. Well, perhaps this side-steps the point of the thread too much, but if we do &mut *{*the_box} we can side-step DerefPure and friends, because the box is gone.

I imagine the long-term safe solution to DerefPure is ultimately must be different type for deref: the current one says you're borrowing self when you are really borrowing self's referee. With &mut / built-in * we can solve this problem without having a surface syntax, as this RFC does it, but with user types / custom *, I don't see how we can avoid that.

[Ericson2314]

Related, I think may-dangling doesn't solve the whole problem, in that we probably would want invalidated fields without any indirection being involved (say if https://github.com/rust-lang/rfcs/pull/2061 is accepted):

// somehow indicate some destructuring is OK
struct Thing<T>(uint, T);

// Somehow say we don't care about `Self::1`
impl<T> Drop for Thing<T> {
    fn drop(&mut self) {
        println!("{}". self.0);
    }
}
 
fn sound<'long>(a_wrapper: Thing<Type>) {
    let _move: Type;
    {
        let tmp = a_wrapper;
        _move = tmp.1; // Know `_move` is initialized and  `tmp.1` deinitialized here
    }                  // `tmp` dropped here---want to run destructure cause `tmp.1`
                       // doesn't matter.
    
    // `_move` must be valid, like today. (The error would be above.)
    println!("_move; {:?}", borrow);
}

This really isn't a drop-specific thing at all, but rather first-class partial borrows, which IIRC @nikomatsakis talked about earlier (maybe the break-from-block thread on whether or not hoisting the block into a function was always possible).

[Ericson2314]

Another thing to note is with "Self::1", I'm envisioning going after the dangly paths directly. Even in the lifetime case, this is necessary if we want to support a dangly hard-coded &mut 'static, as there is no lifetime parameter to annotate / give the ?Alive anti-bound.

[arielb1]

We need to make some call around this for parity with AST borrowck - AST borrowck allows this sort of thing.

[RalfJung]

For Baz, the dangly paths would be {*self.data}.

I'm not entirely sure about this one... with the #[may_dangle] rules as currently written, if the Baz::drop can get its hand on a t: T, it is allowed to do *self.data = t;, which would be unsound because we could have an aliasing let x = &mut *self.data; on our side, right?

For example, consider

struct Baz<'a, T> { // T "may dangle", but not `'a`
  data1: &'a mut T,
  data2: &'a mut T,
}

unsafe impl<'a, #[may_dangle] T> Drop for Baz<'a, T> {
  fn drop(&mut self) {
    mem::swap(self.data1, self.data2); // Just moving data of type `T` around; safe according to current rules
  }
}

I must be missing something here...

This follows because if the drop impl were to access the referent of said &mut T, it would be violating its may-dangle attribute: it doesn't know, after all, that the &mut T referent is still valid. (It's essentially a kind of parametricity argument.)

Uh-oh, parametricity-based reasoning.^^ And this does not fall out of ~~my~~ the interpretation of #[may_dangle] as getting rid of implicit bounds. For dropping cyclic structures, "'a may dangle" helps because it means we can end 'a before dropping even though drop takes a type involving 'a (violating the usual implicit bound about all lifetimes we can mention being alive), resolving the cycle. But that's not what's happening here, the relevant lifetime lives on. This truly looks more parametricity-based, and that doesn't make me very confident.

[arielb1]

@RalfJung

You (or @nikomatsakis's somewhat- description) are off-by-one-layer-of-indirection. The idea is that borrows of dereferences of dangly pointers remain valid after the destructor runs, not that borrows of dangly things are not invalidated.

That's it, with Bar, borrows of *self.data1 would be themselves invalidated (this can be seen very easily from the POV of Box<T> - of course we want borrows of *self to be invalidated when the box is destroyed), while borrows of **self.data1 would remain valid.

If the type being destroyed is covariant, the justification doesn't really even need parametricity - rather, the compiler could coerce to type to a type where all the "dead" lifetimes are already over, and the destructor called at that type obviously should not access a dead reference.

I'm less sure of how that would work with invariant types (e.g. associated types).

[RalfJung]

@arielb1

You (or @nikomatsakis's somewhat- description) are off-by-one-layer-of-indirection.

Ah. Makes sense :)

In the case of Baz, "dereference of dangly pointer" only makes immediate sense if T is a reference. What if T is e.g. a pair of references? I assume the rule generalizes to "anything that has at least one deref applied after going through the dangly pointer", so (*self.data1).0 would still be invalidated but *(*self.data1).0 would not?

Given that Box is considered separately here, this rule seems fairly straight-forward to justify (in hindsight, anyway^^) considering that dropping references is a NOP -- the additional layer of * says there's a reference indirection, so this rule kind of lets the type system exploit knowledge about references' destructors.

[RalfJung]

@Ericson2314

Related, I think may-dangling doesn't solve the whole problem, in that we probably would want invalidated fields without any indirection being involved (say if rust-lang/rfcs#2061 is accepted):

This really isn't a drop-specific thing at all, but rather first-class partial borrows, which IIRC @nikomatsakis talked about earlier (maybe the break-from-block thread on whether or not hoisting the block into a function was always possible).

I think I'm beginning to understand. Your example is a case where moving out of a struct could be legal even though it implements Drop. The connection to the Box example(s) is that these can be alternatively explained by saying that the &mut T is moved out of the Box but the destructor is fine with that. The reason this works currently is that a Box<&mut T> and a Box<T-that-has-been-moved-out> do the same thing when being dropped -- just deallocate memory, don't do anything with the content. I find that easier to accept than parametricity-based reasoning. :D I'm not sure though how to extend this picture to Baz -- there is no "moving out" below &mut...

[Ericson2314]

Thanks, it had been a while since I said the things I did so I needed a refresher too :).

I'm not sure though how to extend this picture to Baz -- there is no "moving out" below &mut...

Well, we could (as long as something was put back in) if it weren't for panicking :D. Let me go remember how the Baz example works with the rules today.