Imagine that we have a structure of the form:
typedef struct {
int payload1;
foo *link;
int payload2;
} foo;
This structure is characterized by two things:
1) It is a singly linked list, and thus has a simple ownership
structure which can be captured by Rust's owned pointers
2) The payload of this struct is interleaved with links, in
order to save space and an extra indirection. The layout may
be fixed, by virtue of being exposed by a C library.
The question now is: can we write an Iterator<&mut foo> for
the corresponding Rust structure foo, without using any unsafe code?
There is a fundamental problem with this structure: iterator
invalidation. If we are able to issue a &mut foo reference, then the
link field could get mutated. Rust's borrow checker would reject this,
since the only possible internal state for the iterator (a mutable
reference to the next element) aliases with the mutable reference
returned by next(). I am not sure how to solve this without changing
the layout of the struct; perhaps there might be a way if one could
selectively turn off the mutability of some fields.
Suppose we are willing to change the struct, as per the extra::dlist
implementation, we still fall short of a safe implementation: the
internal state of the iterator utilizes a raw pointer (head), which
provides a function resolve() which simply mints a mutable reference to
the element in question. It seems to be using Rawlink to hide the fact
that it has its fingers on a mutable borrowed reference to the list. It
recovers some safety by maintaining a mutable reference to the whole
list in the iterator structure as well, but it would be better if no
unsafe code was necessary at all, and I certainly don't feel qualified
to reason about the correctness of this code. (Though, I understand and
appreciate the fact that the back pointers have to be handled unsafely.)
So, is it possible? I just want (provably) safe, mutable iteration over
singly-linked lists...
Edward
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
