On Tue, Aug 20, 2013 at 1:19 AM, Oren Ben-Kiki <[email protected]> wrote:
> I had a similar problem when writing an iterator for a tree-like data
> structure. The iterator held a stack (vector) of per-node iterators and
> needed to push into it while accessing the last node.
>
> In my case the whole thing works with owned and burrowed pointers. I managed
> to implement the immutable iterator by providing the correct lifetime
> incantation and, like you said, only using indices (actually I implemented a
> `mut_last()` function for mutable vectors - somehow this isn't in the
> standard library - but this is just a shorthand for accessing by `[len() -
> 1]`).
>
> I couldn't get any safe code to work for the mutable iterator though :-( I
> ended up using an unsafe code with a `*mut` pointer. It seems like you could
> do the same, if you are willing to give up the type-enforced safety...
It's possible to implement a mutable iterator through a tree-like
object without unsafe code. If you're using unsafe code to return a
reference overlapping with the children, it's not a memory safe
interface.
You can use pattern matching to split a mutable reference into
disjoint mutable references (one as the yielded value, the other
pointing to the children):
// can be done with a struct too
let mut t = (1, 2); let (ref mut x, ref mut y) = t;
> I love the compiler-enforced safety wrt. pointer lifetime and ownership, but
> like all type systems it has its limitations. It seems that the current
> approach is to implement safe containers with very careful sprinkling of
> `unsafe` (hey, even std::vec does it!), and then to have the bulk of the
> code use these safe containers. Maybe you could do something similar.
Vectors are the lowest-level dynamically sized memory allocation
primitive in Rust. There's no existing safe code for them to leverage,
so it either has to be implemented in the compiler or the library, and
library code is simpler.
There are many containers implemented entirely without unsafe code,
copies or managed pointers including `std::hashmap`, `std::trie`,
`extra::treemap` and `extra::ringbuf`. The `extra::priority_queue`
implementation was originally safe, but contains a simple
micro-optimization with a bit of unsafe code.
It's likely that the `ringbuf` implementation will be micro-optimized
with unsafe code in the future, but for the others it's a matter of
improving the compiler's codegen.
> It would be awesome if one could come up with a non-zero-cost extension to
> the type system where one could say "I know this seems unsafe but I assert
> it is just because the static type system is too weak; please insert minimal
> efficient dynamic assertions that things are OK". This would need to be
> explicit since it would incur some (hopefully low) run-time penalty.
The minimal dynamic assertions are the dynamic borrow checking errors
provided by mutable managed/reference-counted pointers. I don't think
there's going to be anything cheaper than reference counting +
freezing/unfreezing on borrow scopes.
> Probably such a mechanism wouldn't be 100% generic, but if we had a list of
> cases where people were forced to resort to unsafe code, perhaps we could
> cover the interesting "80%" of the cases and somehow provide them as a
> library or macro or something. ARC and RW ARC are sort of like that
> (libraries compensating for too-weak builtin-types system), maybe we need
> more?
I wouldn't really say `extra::arc` is working around the type system.
It exists only to provide atomic reference counting for references
from multiple tasks, and a mutex to guard mutability. Rust implements
concurrency in the standard library, so the building blocks in the
standard library have to use unsafe code. The type system allows them
to be *used* within entirely safe code.
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
