It seems to me the safety of iterators over collections is enforced by "into_iter" taking ownership of the collection.
This seems at odds with the common uses of collections, for example I have a free memory list that should last the lifetime of the program. I have various algorithms that need to iterate over the list, like find block, merge blocks, that get run at various times (on allocations, on free etc). It seems the need to insert or delete nodes requires access to the collection itself.
The implementer should add a lifetime parameter on their IteratorType, like slice::Iter has.
Your begin and end put up a warning flag to me that you're thinking like C++ iterators, basically cursors. A Rust iterator is usually a self-contained range, like what you'd have with a pair of C++ iterators.
I am implementing the iterators from Stepanov's Elements of Programming in Rust, and they currently work like C++ iterators. Stepanov's iterators and coordinates go much further into the classification of access patterns as an abstract algebra than Rust does, so you have:
single-pass-forward-iterator
multi-pass-forward-iterator
bidirectional-iterator
indexed-iterator
random-access-iterator
and then you move on to multi-dimensional iterators and coordinate structures like:
I need to resolve the naming issue above, as I would rather have as systematic way of doing it to avoid having to think of new names all the time. I think that value semantics should be the default, so:
fn half_nonnegative(mut self) -> Self
That leaves the other case:
fn replace_with_half_nonnegative(&mut self)
seems a bit long? maybe:
fn alter_half_nonnegative(&mut self)
I am not sure if I am going to leave the iterators like C++ iterators, or if they should be ranges like the Rust ones. I don't think Rust iterators will work on trees and higher dimensional structures. So I have two choices, and I would be interested in opinions. I could rename the iterators 'Cursors' or 'Coordinates' and leave them "unsafe" as an alternative to the Rust built-in ones, or I could try and express the algorithms in terms of Rusts 'Iterators' (that are actually ranges).
Those look interesting, but are a different approach focusing on the collections themselves. The elements of programming stuff is more like a library of algorithms, and you can use them by implementing the API on your collection, which is very minimal.
I believe we've already talked about the need for a certain form of higher kindedness to express an iterator that can yield overlapping mutable references. The Iterable trait has the same problem, I think. You want to write something like this, but you cannot:
trait Iterable {
type Elem;
type Iter<'_> where for<'x> Iter<'x>: Iterator<Item=&'x Elem>;
fn iter(&'a self) -> Self::Iter<'a>;
}
Let me rephrase the question. I implemented an iterable trait, free iterators (don't have to be paired), that allow multiple mutable overlapping regions in a straightforward way and did not encounter a need for higher kinded types. In fact it seems if you hold the reference the the collection in a raw pointer you can do whatever you like as in C/C++. So I don't understand the statement that you need HKT to do this.
In order to avoid that, the lifetime of Self::IteratorType needs to be bound to the lifetime of the borrow in begin and end, but it can't be, because that would require Self::IteratorType to be a type constructor of the kind lifetime -> type.
This is easily the most immediate use for higher kinded polymorphism in Rust - using lifetime -> type associated type constructors to create 'view' types.
I have added a phantom lifetime parameter to the SliceIterator that I think prevents the dangling pointer. This appears to prevent the problem whist still allowing multiple mutable iterators. What do you think? Zerbertz – Dubai, UAE
Is there going to be a runtime cost (space or time) to using the phantom type?
Edit: It seems to me the formulation of Rust iterators which combine Stepanov's Readable and Iterator traits into a single trait is the cause of the need for HKT. Separating the traits, so that Readable has a lifetime parameter but Iterator does not, appears to make the problem go away in a very simple way. My only concern is if the phantom type is generating any runtime code.
The link works for me now, it was an issue with the server. However, that does not prevent dangling pointers because you haven't associated the lifetime parameter with the borrow in begin or end. Rust Playground
However, now a T: Iterable has to be a T: for<'a> Iterable<'a>. There may also be more intricate lifetime issues in complex scenarios because of the way this lifetime parameter hasn't been encapsulated.
None of this is different between the way that you have defined the iterator trait and the standard library's definition of iterators.
I am getting closer, I have fixed it so you cannot create a dangling pointer, but still allows multiple write iterators to be held concurrently see code in the Rust Playground.
First question: The Iterable trait I am using seems to work fine? What problem was Comex trying to fix above? Does my formulation not suffer from this problem, or am I missing the test case to pick it up (what is the problem case)?
There is another problem, as I am trying to separate the iteration from the dereferencing, currently you can generate a segmentation fault if you try to pass a read-only collection see broken code in the Rust Playground.
Second question: Obviously the 'Writable' trait should only be defined if we are iterating a mutable collection. Is there any way to check if something is mutable before borrowing it immutably?