[rust-dev] Safely writing iterators over idiomatic C structures
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 Iteratormut 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
Re: [rust-dev] Safely writing iterators over idiomatic C structures
On 06/12/13 19:11, Edward Z. Yang wrote:
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 Iteratormut 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
One could have an Iterator(mut int, mut int), where the references
point to just the fields. Off the top of my head:
struct List {
payload1: int,
next: Option~Foo,
payload2: f64
}
struct ListMutIterator'a {
elem: Option'a mut List
}
impl'a Iterator('a mut int, 'a mut f64) for ListMutIterator'a {
fn next(mut self) - Option('a mut int, 'a mut f64) {
let elem = std::util::replace(self, None); // I think this
might be necessary to get around the borrow checker.
let (ret, next) = match elem {
Some(List { payload1: ref mut payload1, next: ref mut
next, payload2: ref mut payload2 }) = {
(Some((payload1, payload2)), next.as_mut_ref())
}
None = (None, None)
};
*self = next;
ret
}
}
(The List pattern match will look nicer if
https://github.com/mozilla/rust/issues/6137 gets solved; `List { ref mut
payload1, ref mut next, ref mut payload2 }`.)
I imagine this will end up being very ugly if there are more than just 2
fields before and after, although one could easily replace the tuple
with a struct `ListMutRef'a { payload1: 'a mut int, payload2: 'a mut
f64 }`.
Huon
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Safely writing iterators over idiomatic C structures
Maybe the language should be changed to allow Iterator to be changed to have a
signature like this:
pub trait IteratorA {
fn next'a('a mut self) - Option'a A;
}
Then you could return the mut by reborrowing and would be able to advance the
iterator without issue afterwards.
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Safely writing iterators over idiomatic C structures
OK, with a little bit of tweaking I have come up with a version
that seems to work:
struct List {
payload1: int,
next: Option~List,
payload2: f64
}
struct ListMutIterator'a {
elem: Option'a mut List
}
impl'a Iterator('a mut int, 'a mut f64) for ListMutIterator'a {
fn next(mut self) - Option('a mut int, 'a mut f64) {
let elem = std::util::replace(self, ListMutIterator{elem:None}); //
I think this might be necessary to get around the borrow checker.
let (ret, next) = match elem {
ListMutIterator{elem: Some(List { payload1: ref mut payload1,
next: ref mut next, payload2: ref mut payload2 })} = {
(Some((payload1, payload2)), match *next {
None = None,
Some(ref mut p) = Some(mut **p)
})
}
ListMutIterator{elem: None} = (None, None)
};
*self = ListMutIterator{elem:next};
ret
}
}
Perhaps dlist should be updated to use this implementation strategy?
Edward
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Safely writing iterators over idiomatic C structures
Excerpts from Huon Wilson's message of 2013-12-06 00:26:36 -0800:
One could have an Iterator(mut int, mut int), where the references
point to just the fields. Off the top of my head:
Sure. (This is not so good when there are a lot of fields.)
impl'a Iterator('a mut int, 'a mut f64) for ListMutIterator'a {
fn next(mut self) - Option('a mut int, 'a mut f64) {
let elem = std::util::replace(self, None); // I think this
might be necessary to get around the borrow checker.
let (ret, next) = match elem {
Some(List { payload1: ref mut payload1, next: ref mut
next, payload2: ref mut payload2 }) = {
(Some((payload1, payload2)), next.as_mut_ref())
I fixed some of the egregious type-checking errors, but this one has me
stuck. There is no as_mut_ref() in the version of Rust I'm running, and
the plausible replacement mut_ref() doesn't do what I want:
Huon.rs|24 col 37 error| mismatched types: expected
`std::option::Optionmut List` but found `std::option::Optionmut ~List`
(expected struct List but found ~-ptr)
(Because, of course, the thing inside the option is a ~List, not a
List).
Cheers,
Edward
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
