Sendable Data Structures, or: How I Learned to Stop Worrying and Love Region Pointers

[bblum]

First of all, all simple data structures (list and map variants) should probably move to libcore - I've been wanting a good O(1) arbitrary-position removal data structure for linked task failure, and it looks like I'll be settling for dvec for now. This will get more and more important the more runtime moves into rust.

But the real problem of linked failure is the sendability requirement. Currently our lists and hashtables are written with @-boxes everywhere. We should have a @-version (for lazy-copy power and for cheapness of allocation) and a ~-version (for inter-task) for each data structure, and ways to convert between each.

But-once-more, ~ data structures will have complicated interfaces. You can't just hand back a ~-pointer to give the user a handle to a node, and disaster will ensue if you try iterating by handing around region pointers but also mutating the data structure at the same time. This hints at problems with mutability, too.

It seems like combining region pointers and mutability, we should be able to let the borrow-checker ensure this sort of property. fn each could be defined in impl for foo_send/&, and fn remove defined in impl for foo_send/&mut. This might require more powerful propagation of (im)mutability through ~, records, etc.

For future (my own) reference, a half-complete attempt at twiddle-ifying hashmap: https://gist.github.com/3057003

[nikomatsakis]

I think there is an expressiveness problem when it comes to sendable data structures. Typically you want to be able to mutate and iterate over such structures, and both without copying.

Right now the only real way to write such data structures is to make all of their internals swappable. Iteration can then swap out to the stack as needed. This guarantees that no mutation will occur during iteration because it would encounter swapped out data and fail. It's crude and pushes errors to runtime, but it "works" in the sense that the compiler accepts it.

I think there could be a better way to adjust how we think about mutability and unique pointers. This is kind of half-baked at the moment so I probably ought to sit down and try to write up a blog post. But the basic problem seems to be that if you have, say, a linked list of unique pointers, you'd like to be able to have an iteration method which expresses the idea that this list must be immutable (for the duration of the iteration) and a insert method which expresses the idea that the list must be mutable (for the duration of the insert). Borrow check can do these sorts of guarantees in a limited sense but it doesn't work for chains of unique pointers of arbitrary lengths. I think however it could be made to do so. This is certainly related to the ideas of freezing and thawing.

[nikomatsakis]

I think this is fixed, basically? The send_map module shows how this can work. Re-open if you disagree.

[bblum]

sounds fine. I guess I was envisioning a separate sendable version for each data structure (and that development might expose more deficiencies in the region system)... but that's probably way far off in the future.

[nikomatsakis]

I would like to have all the base data structures be sendable, with the exception of those for which it doesn't make much sense (e.g., std::list)