[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 #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 #40 (comment) 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.