Rewrite `Rc` and `Arc` to use `Cell` and `Atomic` respectively

[nikomatsakis]

To the extent possible, we should try to have all interior mutability be done via Cell, RefCell, Atomic, or (not yet landed) Volatile. If one of these patterns doesn't suffice, it'd be nice to know why!

[nikomatsakis]

Nominating for P-Low

[nikomatsakis]

Tagging as E-Mentor; I can mentor.

[nikomatsakis]

Related to #12577

Other types that use interior mutability I can think of off the top of my head:

• Arena
• RwArc

[pongad]

@nikomatsakis I'm definitely interested. Though---having never been a part of a project like this before---not quite sure how the mentoring works just yet :P

[edwardw]

This is the Rc part: rewrite Rc using Cell.

[thestinger]

I don't understand the reasoning behind doing this for Rc. Using a marker type makes the intent clearer, and will perform better with optimizations disabled. The Rc type is also supposed to be Freeze when T is Freeze and this will make it always non-Freeze. The Arc type should also be Freeze.

[nikomatsakis]

@thestinger Marker types do not seem clearer to me than Cell, quite the opposite, but of course thi is a matter of opinion.

At first I thought you were on to something regarding Freeze, but then I realize that I was mistaken. In particular, we need to settle on precisely what makes something not Freeze: must the interior mutability be something interior, something that you own, or just something you can reach?

But this question is orthogonal to whether we use markers or Cell. If I understand it, the use of Cell would look something like this:

struct RcBox<T> {
    value: T,
    strong: Cell<uint>,
    weak: Cell<uint>
}

pub struct Rc<T> {
    priv ptr: *mut RcBox<T>,
}

In this case, whether or not Rc is Freeze will hinge directly on what we decide about owning vs mutability. At present, the definition is based on reachability. But this definition may be stronger than what we need. I guess it depends on just what Freeze is to be used for.

So after considering this some more, I still think that using Cell is the right call for Rc is the right call, but the real discussion is what Freeze precisely ought to mean, which is most properly discussed I think under #11781.

@thestinger make sense?

[thestinger]

I don't think we have a way of enforcing deep immutability. There are many existing Freeze types doing internal writes due to I/O. I don't know of a purpose for Freeze beyond the high-level semantic meaning (perceived inherited mutability) and type-based alias analysis (which is not deep) so that's the lens I'm viewing it through.

[thestinger]

Every type using memory allocation needs to become non-Freeze if means deep immutability. The free function is mutating memory via the pointer. So it's not just a problem with I/O.

[nikomatsakis]

@thestinger I don't believe that is an accurate summray of what was proposed, but it is a moot point, as in the latest plan there is no Freeze.

[pongad]

Is there a change to Atomic coming? Arc is already using AtomicUint.

[nikomatsakis]

I think @edwardw and I decided that Arc is already using the right primitives and it was just Rc that wasn't.