Trouble implementing slice-like functionality for non-contiguous collections (ie: VecDeque)


#1

Hello I wanted to make an interface similar to the built in slices [T] for collections such as VecDeque, whose items aren’t necessarily contiguous. But I have had a few questions/problems.

(1) First of all, if this is already implemented somewhere, then that would have saved me a lot of trouble, but I guess its also a good exercise to do it myself.

(2) The main issue that I’m having is that I can’t wrangle my lifetimes of my own Iterator implementation to match the Iterator trait. Well, upon further experimentation it seems to work fine for the immutable version, but the mutable version (using the exact same code, just with different idents and & replaced with &mut) won’t borrowck.

(3) Writing implementations such as these requires a LOT of code duplication because Rust currently doesn’t support parametric polymorphism for mutability. If I remember correctly this was disccussed briefly a while ago, but it was deemed to be only useful for low-levelish crates like new datastructures or std itself, and therefore the complexity wasn’t worth it. I guess I understand that, although some days I do dream of a world in which we could ‘parameterize all the things’ :stuck_out_tongue_closed_eyes:. For now though does anyone have suggestions for eg: a macro_rules! macro that could do it? I think the problem is that Iter and IterMut right now are two seperate identifiers, and you can’t just take Iter and append Mut to it.

Edit: Now I’m here I remember a few more gripes I had with this stuff. For example, is there a reason why the Index and IndexMut traits enforce returning shared and mutable references respectively? I would have thought that fn index(...) -> Self::Output ala Iterators is much more powerful. Or even better, could we have an Apply trait and be like Scala :joy:

Finally: Here’s the code: https://play.rust-lang.org/?gist=7c929706b6cb3a371af0ea628d2566a4&version=stable&backtrace=0

Thanks so much guys if you could help out


#2

Unfortunately, you can’t really implement a mutable iterator without unsafe code. The reason your code doesn’t compile is because, if it did, it would cause potential unsoundness :slightly_smiling_face:. The unsoundness comes from the fact that your iterator could yield the same mutable reference more than once, violating the aliasing restrictions on mutable references. Rust doesn’t know whether your iterator truly returns references to different values or not. What you really want here is a “streaming iterator” (if you Google that phrase you’ll get more info), where the returned reference’s lifetime is tied to a borrow of &mut self - that would mean the caller could not call next until the previous reference/borrow falls out of scope. That would ensure that even if your iterator returned references to same values, it wouldn’t violate aliasing. That type of iterator, however, would require a different type of signature from Iterator.

This isn’t an issue for an iterator returning immutable references because you can have multiple immutable borrows to a value at the same time, of course.


#3

This is to be able to associate the output lifetime with &self or &mut self. There are no associated type constructors in Rust at the moment, and so you wouldn’t be able to tie the two lifetimes together (which is precisely the Iterator vs “streaming iterator” scenario I mentioned in the previous post).


#4

Thanks very much for the explanation. I guess I’d just (wrongly) assumed that, because sometimes-aliasing iterators seemed nonsensical to a human, rustc would also not care. Of course, I realise that’s not how borrowck works - need to ‘prove’ to the compiler its safe ughh.

I had actually read up on streaming iterators, except they all seemed to be for, as the name suggests, streaming not like built-in collections.

Assuming that implement next() ‘correctly’ though (ie: not aliasing), I guess I should be able to sprinkle a bit of unsafe to make it work like the iterators in std, yes? I think I’ll read through the source a bit more.

Thanks very much for your help!


#5

Yup, that’s right.

Yeah, they’re streaming in the “one mutable reference at a time” sense, even over plain collections; it’s not “streaming” in the classical sense where you pull data from an arbitrary (large or potentially infinite) stream of data.


#6

If found the line in the standard library where they do exactly this sort of trickery:

https://doc.rust-lang.org/src/collections/vec_deque.rs.html#2026

To be honest I’m surprised that’s not documented more explaining why exactly foregoing borrowck in that instance is actually safe.


#7

Well, it’s because they ensure that their iterator never yields a reference to the same value more than once.