% Iteration

Let's take a crack at iterating this bad-boy.

IntoIter

IntoIter, as always, is going to be the easiest. Just wrap the stack and call pop:

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

But we have an interesting new development. Where previously there was only ever one "natural" iteration order for our lists, a Deque is inherently bi-directional. What's so special about front-to-back? What if someone wants to iterate in the other direction?

Rust actually has an answer to this: DoubleEndedIterator. DoubleEndedIterator inherits from Iterator (meaning all DoubleEndedIterator are Iterators) and requires one new method: next_back. It has the exact same signature as next, but it's supposed to yield elements from the other end. The semantics of DoubleEndedIterator are super convenient for us: the iterator becomes a deque. You can consume elements from the front and back until the two ends converge, at which point the iterator is empty.

Much like Iterator and next, it turns out that next_back isn't really something consumers of the DoubleEndedIterator really care about. Rather, the best part of this interface is that it exposes the rev method, which wraps up the iterator to make a new one that yields the elements in reverse order. The semantics of this are fairly straight-forward: calls to next on the reversed iterator are just calls to next_back.

Anyway, because we're already a deque providing this API is pretty easy:

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

And let's test it out:

#[test]
fn into_iter() {
    let mut list = List::new();
    list.push_front(1); list.push_front(2); list.push_front(3);

    let mut iter = list.into_iter();
    assert_eq!(iter.next(), Some(3));
    assert_eq!(iter.next_back(), Some(1));
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next_back(), None);
    assert_eq!(iter.next(), None);
}
cargo test
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/too-many-lists/lists)
     Running target/debug/lists-5c71138492ad4b4a

running 11 tests
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::iter ... ok
test third::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok

test result: ok. 11 passed; 0 failed; 0 ignored; 0 measured

   Doc-tests lists

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured

Nice.

Iter

Iter will be a bit less forgiving. We'll have to deal with those awful Ref things again! Because of Refs, we can't store &Nodes like we did before. Instead, let's try to store Ref<Node>s:

pub struct Iter<'a, T: 'a>(Option<Ref<'a, Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.borrow()))
    }
}
> cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/too-many-lists/lists)

So far so good. Implementing next is going to be a bit hairy, but I think it's the same basic logic as the old stack IterMut but with extra RefCell madness:

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node_ref| {
            self.0 = node_ref.next.as_ref().map(|head| head.borrow());
            Ref::map(node_ref, |node| &node.elem)
        })
    }
}
cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/too-many-lists/lists)
src/fourth.rs:154:22: 154:30 error: `node_ref` does not live long enough
src/fourth.rs:154             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
                                       ^~~~~~~~
note: in expansion of closure expansion
src/fourth.rs:153:27: 156:10 note: expansion site
src/fourth.rs:152:46: 157:6 note: reference must be valid for the lifetime 'a as defined on the block at 152:45...
src/fourth.rs:152     fn next(&mut self) -> Option<Self::Item> {
src/fourth.rs:153         self.0.take().map(|node_ref| {
src/fourth.rs:154             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
src/fourth.rs:155             Ref::map(node_ref, |node| &node.elem)
src/fourth.rs:156         })
src/fourth.rs:157     }
src/fourth.rs:153:38: 156:10 note: ...but borrowed value is only valid for the scope of parameters for function at 153:37
src/fourth.rs:153         self.0.take().map(|node_ref| {
src/fourth.rs:154             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
src/fourth.rs:155             Ref::map(node_ref, |node| &node.elem)
src/fourth.rs:156         })
error: aborting due to previous error
Could not compile `lists`.

Shoot.

node_ref doesn't live long enough. Unlike normal references, Rust doesn't let us just split Refs up like that. The Ref we get out of head.borrow() is only allowed to live as long as node_ref, but we end up trashing that in our Ref::map call.

I don't think there's anything we can do here. It's a dead end. Let's try getting out of the RefCells. What if we store an &RefCell<Node>?

pub struct Iter<'a, T: 'a>(Option<&'a RefCell<Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| &** head))
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node| {
            self.0 = node.borrow().next.as_ref().map(|head| &**head);
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }
}
> cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/too-many-lists/lists)
src/fourth.rs:154:22: 154:35 error: borrowed value does not live long enough
src/fourth.rs:154             self.0 = node.borrow().next.as_ref().map(|head| &**head);
                                       ^~~~~~~~~~~~~
note: in expansion of closure expansion
src/fourth.rs:153:27: 156:10 note: expansion site
src/fourth.rs:152:46: 157:6 note: reference must be valid for the lifetime 'a as defined on the block at 152:45...
src/fourth.rs:152     fn next(&mut self) -> Option<Self::Item> {
src/fourth.rs:153         self.0.take().map(|node| {
src/fourth.rs:154             self.0 = node.borrow().next.as_ref().map(|head| &**head);
src/fourth.rs:155             Ref::map(node.borrow(), |node| &node.elem)
src/fourth.rs:156         })
src/fourth.rs:157     }
src/fourth.rs:154:13: 154:70 note: ...but borrowed value is only valid for the statement at 154:12
src/fourth.rs:154             self.0 = node.borrow().next.as_ref().map(|head| &**head);
                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: in expansion of closure expansion
src/fourth.rs:153:27: 156:10 note: expansion site
src/fourth.rs:154:13: 154:70 help: consider using a `let` binding to increase its lifetime
src/fourth.rs:154             self.0 = node.borrow().next.as_ref().map(|head| &**head);
                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: in expansion of closure expansion
src/fourth.rs:153:27: 156:10 note: expansion site
error: aborting due to previous error
Could not compile `lists`.

Hmm... no this is the same problem again. The borrow makes a Ref that we can't keep alive long enough.

Hang on, though. We've got Rcs. Who said we even needed to store references? Why can't we just Clone the whole Rc to get a nice owning handle into the middle of the list?

pub struct Iter<T>(Option<Rc<Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.clone()))
    }
}

impl<T> Iterator for Iter<T> {
    type Item =

Uh... Wait what do we return now? &T? Ref<T>?

No, none of those work... our Iter doesn't have a lifetime anymore! Both &T and Ref<T> require us to declare some lifetime up front before we get into next. But anything we manage to get out of our Rc would be borrowing the Iterator... brain... hurt... aaaaaahhhhhh

Maybe we can... map... the Rc... to get an Rc<T>? Is that a thing? Rc's docs don't seem to have anything like that. Actually someone made [a crate][own-ref] that lets you do that.

But wait, even if we do that then we've got an even bigger problem: the dreaded spectre of iterator invalidation. Previously we've been totally immune to iterator invalidation, because the Iter borrowed the list, leaving it totally immutable. However now that our Iter is full of Rcs, it doesn't borrow the list at all! That means people can start calling push and pop on the list while they have an Iter!

Oh lord, what will that do?!

Well, pushing is actually fine. We've got a view into some sub-range of the list, and the list will just grow beyond our sights. No biggie.

However pop is another story. If they're popping elements outside outside of our range, it should still be fine. We can't see those nodes so nothing will happen. However if they try to pop off the node we're pointing at... everything will blow up! In particular when they go to unwrap the result of the try_unwrap, it will actually fail, and the whole program will panic.

That's actually pretty cool. We can get tons of interior owning pointers into the list and mutate it at the same time and it will just work until they try to remove the nodes that we're pointing at. And even then we don't get dangling pointers or anything, the program will deterministically panic!

But having to deal with iterator invalidation on top of mapping Rcs just seems... lame. Rc<RefCell> has really truly finally failed us. Interestingly, we've experienced an inversion of the persistent stack case. Where the persistent stack struggled to ever reclaim ownership of the data but could get references all day every day, our list had no problem gaining ownership, but really struggled to loan our references.

Although to be fair, most of our struggles revolved around wanting to hide the implementation details and have a decent API. We could do everything fine if we wanted to just pass around Nodes all over the place.

Heck, we could make multiple concurrent IterMuts that were runtime checked to not be mutable accessing the same element!

Really, this design is more appropriate for an internal data structure that never makes it out to consumers of the API. Interior mutability is great for writing safe applications. Not so much safe libraries.

Anyway, that's me giving up on Iter and IterMut. We could do them, but ugh.

[own-ref]:

results matching ""

    No results matching ""