Proposal: an Ok-ish safe deque as a new chapter

[denis-protivensky]

First of all, thanks for the great book!

I was doing a bad safe deque and it really hit me that we cannot even have iterators. I spent some time and came up with an ok-ish safe deque variant with iterators and fewer implementation detail leaks. Here's the list of changes:

• re-declare Link to have RefCell on top to have immutable nodes with mutable next/prev pointers (as a downside, Link becomes 16 bytes each)
• change the bad safe deque's code accordingly by mostly swapping borrow() and next/prev member access
• use custom Ref wrapper with cloned Rc to Node, it also allows to hold to a single Ref with pop_*() panicking
• provide lifetime with variance for Ref by using PhantomData => allows for List borrowing by an iterator
• implement double-ended iterator by checking Node's address to identify the same (last) node during iteration
• as a net result, the API is more or less clean, no internals exposed, basic functionality works correctly, no unsafe code
• some other minor tweaks include revised Drop and IntoIterator trait for List

And here's the code:

use std::cell::RefCell;
use std::marker::PhantomData;
use std::ops::Deref;
use std::rc::Rc;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = RefCell<Option<Rc<Node<T>>>>;

pub struct Ref<'a, T> {
    node: Rc<Node<T>>,
    phantom: PhantomData<&'a T>,
}

impl<T> Deref for Ref<'_, T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &T {
        &self.node.elem
    }
}

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}

impl<T> Node<T> {
    fn new(elem: T) -> Rc<Self> {
        Rc::new(Node {
            elem,
            next: RefCell::new(None),
            prev: RefCell::new(None),
        })
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            head: RefCell::new(None),
            tail: RefCell::new(None),
        }
    }

    pub fn push_front(&mut self, elem: T) {
        let new_head = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                *old_head.prev.borrow_mut() = Some(new_head.clone());
                *new_head.next.borrow_mut() = Some(old_head);
                self.head.replace(Some(new_head));
            }
            None => {
                self.tail.replace(Some(new_head.clone()));
                self.head.replace(Some(new_head));
            }
        }
    }

    pub fn push_back(&mut self, elem: T) {
        let new_tail = Node::new(elem);
        match self.tail.take() {
            Some(old_tail) => {
                *old_tail.next.borrow_mut() = Some(new_tail.clone());
                *new_tail.prev.borrow_mut() = Some(old_tail);
                self.tail.replace(Some(new_tail));
            }
            None => {
                self.head.replace(Some(new_tail.clone()));
                self.tail.replace(Some(new_tail));
            }
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.next.borrow_mut().take() {
                Some(new_head) => {
                    new_head.prev.borrow_mut().take();
                    self.head.replace(Some(new_head));
                }
                None => {
                    // Empty list, clean up the tail as well.
                    self.tail.take();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().elem
        })
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.prev.borrow_mut().take() {
                Some(new_tail) => {
                    new_tail.next.borrow_mut().take();
                    self.tail.replace(Some(new_tail));
                }
                None => {
                    // Empty list, clean up the head as well.
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().elem
        })
    }

    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head.borrow().as_ref().map(|node| Ref {
            node: node.clone(),
            phantom: PhantomData,
        })
    }

    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.borrow().as_ref().map(|node| Ref {
            node: node.clone(),
            phantom: PhantomData,
        })
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            next: self.peek_front(),
            prev: self.peek_back(),
        }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut count = 0usize;

        // Drop forward links.
        let mut cur_head = self.head.take();
        while let Some(node) = cur_head {
            cur_head = node.next.borrow_mut().take();
            count += 1;
        }

        // Drop backward links.
        let mut cur_tail = self.tail.take();
        while let Some(node) = cur_tail {
            cur_tail = node.prev.borrow_mut().take();
            count -= 1;
        }

        // Running both ways is equal.
        assert_eq!(count, 0);
    }
}

impl<T> Default for List<T> {
    fn default() -> Self {
        Self::new()
    }
}

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

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

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

impl<T> IntoIterator for List<T> {
    type Item = T;
    type IntoIter = IntoIter<Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}

pub struct Iter<'a, T> {
    next: Option<Ref<'a, T>>,
    prev: Option<Ref<'a, T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node_ref| {
            // We're on the same node, so it's the last one.
            if Rc::as_ptr(&node_ref.node) == Rc::as_ptr(&self.prev.as_ref().unwrap().node) {
                // Clean up the other end.
                self.prev.take();
            } else {
                self.next = node_ref.node.next.borrow().as_ref().map(|next| Ref {
                    node: next.clone(),
                    phantom: PhantomData,
                });
            }
            node_ref
        })
    }
}

impl<T> DoubleEndedIterator for Iter<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.prev.take().map(|node_ref| {
            // We're on the same node, so it's the last one.
            if Rc::as_ptr(&node_ref.node) == Rc::as_ptr(&self.next.as_ref().unwrap().node) {
                // Clean up the other end.
                self.next.take();
            } else {
                self.prev = node_ref.node.prev.borrow().as_ref().map(|prev| Ref {
                    node: prev.clone(),
                    phantom: PhantomData,
                });
            }
            node_ref
        })
    }
}

#[cfg(test)]
mod tests {
    use super::List;

    #[test]
    fn smoke() {
        let mut l = List::new();
        assert_eq!(l.pop_front(), None);

        l.push_front(1);
        l.push_front(2);
        l.push_front(3);

        assert_eq!(l.pop_front(), Some(3));
        assert_eq!(l.pop_front(), Some(2));

        l.push_front(4);
        l.push_front(5);

        assert_eq!(l.pop_front(), Some(5));
        assert_eq!(l.pop_front(), Some(4));

        assert_eq!(l.pop_front(), Some(1));
        assert_eq!(l.pop_front(), None);

        assert_eq!(l.pop_back(), None);

        l.push_back(1);
        l.push_back(2);
        l.push_back(3);

        assert_eq!(l.pop_back(), Some(3));
        assert_eq!(l.pop_back(), Some(2));

        l.push_back(4);
        l.push_back(5);

        assert_eq!(l.pop_back(), Some(5));
        assert_eq!(l.pop_back(), Some(4));

        assert_eq!(l.pop_back(), Some(1));
        assert_eq!(l.pop_back(), None);
    }

    #[test]
    fn peek() {
        let mut l = List::new();
        assert!(l.peek_front().is_none());
        assert!(l.peek_back().is_none());

        l.push_front(1);
        l.push_front(2);
        l.push_front(3);

        assert_eq!(&*l.peek_front().unwrap(), &3);
        assert_eq!(&*l.peek_back().unwrap(), &1);
    }

    #[test]
    fn into_iter() {
        let mut l = List::new();

        l.push_front(1);
        l.push_front(2);
        l.push_front(3);

        let mut iter = l.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);
    }

    #[test]
    fn for_iter() {
        let mut l = List::new();

        l.push_front(1);
        l.push_front(1);
        l.push_front(1);

        for v in l {
            assert_eq!(v, 1);
        }
    }

   #[test]
    fn iter() {
        let mut l = List::new();

        // Empty list case.
        let mut iter = l.iter();
        assert_eq!(iter.next().as_deref(), None);
        assert_eq!(iter.next_back().as_deref(), None);

        l.push_back(1);
        l.push_back(2);
        l.push_back(3);
        l.push_back(4);
        l.push_back(5);
        l.push_back(6);

        let mut iter = l.iter();
        assert_eq!(iter.next().as_deref(), Some(&1));
        assert_eq!(iter.next_back().as_deref(), Some(&6));
        assert_eq!(iter.next_back().as_deref(), Some(&5));
        assert_eq!(iter.next().as_deref(), Some(&2));
        assert_eq!(iter.next().as_deref(), Some(&3));
        assert_eq!(iter.next_back().as_deref(), Some(&4));
        assert_eq!(iter.next().as_deref(), None);
        assert_eq!(iter.next_back().as_deref(), None);
    }
}

This variant may become a separate chapter with some new concepts described (Deref, PhantomData etc).
If you are Ok with adding such a chapter to the book, I could prepare a draft as a PR.

What do you think?