arena::Arena sidesteps new scoping/drop semantics in way we cannot check

[pnkfelix]

Spawned off of rust-lang/rust#21022

I have a pretty complete series of commits that should resolve rust-lang/rust#8861. During my work on that branch, I developed a collection of tests meant to exercise whether a data type is able to be abused to circumvent the new scoping/drop rules in an unsound manner.

In particular, I learned from these tests:

• arena::TypedArena<T> appears to be fine (because the new rules ensure that any use of such an arena, the drop code for allocated instances of T must never be able to read from borrowed data unless that data is guaranteed to strictly outlive the arena itself).
• However, its predecessor, arena::Arena, is not a sound abstraction.

Here is a test case illustrating the issue with arena::Arena. Note that this test case does not run out-of-the-box on the playpen nor on the current master; you need to add the #[unsafe_destructor] attribute in the appropriate spots to see its behavior there (which illustrates the same unsoundness).

The crucial point is that on my new dtor semantics branch, the asserts in the code below fail to hold (as they must, since cyclic structure cannot work with the given assertions) but the compiler fails to reject this code.

// Illustrate unsoundness when mixing cyclic structure
// and Drop when using arena::Arena.

#![allow(unstable)]

extern crate arena;

use arena::Arena;
use std::cell::Cell;
use id::Id;

mod s {
    #![allow(unstable)]
    use std::sync::atomic::{AtomicUint, ATOMIC_UINT_INIT, Ordering};

    static S_COUNT: AtomicUint = ATOMIC_UINT_INIT;

    pub fn next_count() -> usize {
        S_COUNT.fetch_add(1, Ordering::SeqCst) + 1
    }
}

mod id {
    use s;
    #[derive(Show)]
    pub struct Id {
        orig_count: usize,
        count: usize,
    }

    impl Id {
        pub fn new() -> Id {
            let c = s::next_count();
            println!("building Id {}", c);
            Id { orig_count: c, count: c }
        }
        pub fn count(&self) -> usize {
            println!("Id::count on {} returns {}", self.orig_count, self.count);
            self.count
        }
    }

    impl Drop for Id {
        fn drop(&mut self) {
            println!("dropping Id {}", self.count);
            self.count = 0;
        }
    }
}

trait HasId {
    fn count(&self) -> usize;
}

#[derive(Show)]
struct CheckId<T:HasId> {
    v: T
}

#[allow(non_snake_case)]
fn CheckId<T:HasId>(t: T) -> CheckId<T> { CheckId{ v: t } }

impl<T:HasId> Drop for CheckId<T> {
    fn drop(&mut self) {
        assert!(self.v.count() > 0);
    }
}

#[derive(Show)]
struct C<'a> {
    id: Id,
    v: Vec<CheckId<Cell<Option<&'a C<'a>>>>>,
}

impl<'a> HasId for Cell<Option<&'a C<'a>>> {
    fn count(&self) -> usize {
        match self.get() {
            None => 1,
            Some(c) => c.id.count(),
        }
    }
}

impl<'a> C<'a> {
    fn new() -> C<'a> {
        C { id: Id::new(), v: Vec::new() }
    }
}

fn f<'a>(arena: &'a Arena) {
    let c1 = arena.alloc(C::new);
    let c2 = arena.alloc(C::new);
    let c3 = arena.alloc(C::new);

    c1.v.push(CheckId(Cell::new(None)));
    c1.v.push(CheckId(Cell::new(None)));
    c2.v.push(CheckId(Cell::new(None)));
    c2.v.push(CheckId(Cell::new(None)));
    c3.v.push(CheckId(Cell::new(None)));
    c3.v.push(CheckId(Cell::new(None)));

    c1.v[0].v.set(Some(c2));
    c1.v[1].v.set(Some(c3));
    c2.v[0].v.set(Some(c2));
    c2.v[1].v.set(Some(c3));
    c3.v[0].v.set(Some(c1));
    c3.v[1].v.set(Some(c2));
}

fn main() {
    let arena = Arena::new();
    f(&arena);

The reason why: arena::Arena provides a method with this signature:

    pub fn alloc<T, F>(&self, op: F) -> &mut T where F: FnOnce() -> T { ... }

This is promising, for any T (and F constructing such a T), to give you back a mutable reference to an internally held instance of T in the arena. The problem here is that there is no enforcement of any sort of restriction on the lifetime of borrowed data within T; in particular, it is legal here for borrowed data within T to have lifetime equal to the lifetime of the arena itself, even if T implements Drop in a manner where it will read that borrowed data.

(Compare that situation with TypedArena, where the allocated types are forced to either implement Drop in a pure manner where they do not read from their borrowed data, or the borrowed data is forced to outlive the typed-arena itself.)

So, I said that "there is no enforcement of any sort of restriction on the lifetime of borrowed data within T"; that's because we have no way of expressing such a restriction today. So there is no way to fix the arena::Arena API today to be sound.

This is not a problem for 1.0, as long as we do not stabilize the arena crate (or at least not the arena::Arena type within it). But the arena::Arena type is arguably useful, and therefore it makes sense for us to explore ways to change the language to fix it.

[pnkfelix]

This was resolved in rust-lang/rust#21972 by adding a lifetime parameter to Arena and restricting its fn alloc method so that the allocated data strictly outlives the arena itself. This changed the arena API and made it quite a bit weaker, but this particular ticket no longer needs to be addressed.