Add library for "Shared state is just a mode of use of concurrency"

[bblum]

The idea is that you can implement shared-state-between-tasks by having some sort of "shared state management task", and using message-passing to access/modify the state by communicating over a protocol.

This will replace exclusive ARCs as the user-facing 'mutable shared state' primitive. We don't want to expose exclusives because there's no way to avoid potential for memory leaks with circular references. (If there is such a way... let me know!)

Proposed interface/design, something like:

proto! access {
    open:recv<T:const send> {
        acquired(T) -> held<T>
    }
    held:send<T:const send> {
        release(T) -> open<T>
        wait -> blocked<T>
        signal -> held<T>
    }
    blocked:recv<T:const send> {
        wake -> held<T>
    }
}
enum shared_mutable_state<T:const send> = { // Please suggest better names for this!
    control: pipes::shared_chan<access::server::open<T>>,
    mut access: option<access::client::open<T>,
}
fn clone(&self) -> self;
fn access(&self, fn(&mut T, condition));
fn access_read(&self, fn(&T, condition)); // is this right? let alone possible?
fn wait(&condition);
fn signal(&condition);

Some comments:

• The task would be unlinked, failure-wise, from all other tasks. It's managed by a reference count, and exits itself when all its users' handles are destroyed.
• The circular reference problem is addressed by the const restriction - handles are sendable but mutable, so the state library will refuse to manage handles recursively. Users can put singly-linked data structures in these using ~-pointers, but still can not create circularly-linked data structures.
• (old workaround sketch for weaken_task; irrelevant now but just for bblum's reference: https://gist.github.com/3279078)
• Might make Add rt-aware blocking semaphores in sys.rs, for use in exclusive ARCs #2795 unnecessary
• Reader/writer mode would be really nice, but extremely difficult. Maybe some way of promoting the data to an immutable ARC, internally? That would need to be able to unwrap the arc when the last reader exits. (Add arc::unwrap #3123)

[nikomatsakis]

I am not sure how useful such a thing would be in the standard library. My big concern is the matter of lifetime—how do you signal when the thing is freed? This seems to (in the general case) require a GC or be prone to malloc/free-like dangling pointers. I'd kind of rather that people think about their task design in a more holistic sense where these answers will hopefully fall out of the application.

[bblum]

@nikomatsakis So, pipes let the receiver know when the other endpoint is dropped. My thought was for the server task to internally keep a list of active endpoints -- whenever one closes, it removes it from the list, and when the list becomes empty, the server exits entirely.

Basically this would achieve refcounting isomorphic to how exclusive arcs do it today. The weaken_task bit mentioned above "solves" the circular reference problem - I mean, repeatedly generating circular references and dropping them would still result in memory blowup, but at least the runtime knows how to clean them up when the whole program exits (so there's not actually a "leak" in the assertion-failure-runtime-crash sense of the word).

I dunno, I've always kind of taken it for granted that people will want shared mutable state.

[nikomatsakis]

I see. I knew that you and @eholk were discussing this so I should have phrased it more like a question. Interesting: the failure more with weak tasks is certainly not ideal.

[bblum]

We talked about this and decided it wasn't wise to do. Whether or not the library forbids cycles, arc::exclusive achieves the same functionality. And allowing task cycles means task leaks... it wouldn't be right to make a library that purported to provide generalised shared state that would silently leak memory when writing a doubly linked list.