DRYing out a doubly-linked list implementation


#1

Based on Gankro’s Learning Rust With Entirely Too Many Linked Lists, I wrote up a doubly-linked list implementation to see it if I could make it as compact as possible and perhaps deal more elegantly with the asymmetry of the next pointers (which are Boxes) and previous pointers (which are raw pointers).

For didactic purpose, I rebased a git repo to demonstrate two iterations of the code, both of which are based on the following linked list representation.

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

type Link<T> = Option<Box<Node<T>>>;
type LinkPtr<T> = *const Node<T>;

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

The code implements both *_front and *_back version of methods (eg pop_front, pop_back, etc), and bidirectional iterators.

The first iteration (approximate reproduction after-the-fact) has logic that looks significantly different for the *_front and the *_back versions. In fact, I had a bug in one of the ones that was not in the other one, which was caught by the tests. (Bug pointed out in comments.)

That bug triggered me to refactor the code so that the front and the back versions looked as close to each other as possible. The refactored version converts both boxes and pointers into Option<&> to make the logic look similar, but there must be a few differences based on how owned objects are relinquished and dropped. Also, the forward and the backward iterators are nearly identical. This leads to my first question.

(1) Is the some nicer refactor to seriously DRY this implementation to write the forward and backward code identically while retaining the next/prev pointer (Box vs pointer) asymmetry?

After the refactor, I added a mutable iterator which looks nearly identical to the non-mutable iterator (kinda by design), and that made me question whether one actually needs two different bits of code for this nearly identical logic. Yes, the borrow checker needs to treat these two cases differently for analysis, but after the borrow checker has done its static verification and realized that the mutable borrows are safe, does the actual generated machine code for these two cases need to be anything other than identical? So,
(2) Is there some ergonomic way to DRY out the code so that only one piece of code is actually generated for the non-mutable and mutable iterators? Is that a reasonable thing to expect for this doubly-linked-list case?


DRYing nearly identical implementations for &T and &mut T
#2

Should I perhaps re-scope my question? I want to get a feel for whether what I am asking for is reasonable.