Iterate through a singly linked list of Option<Rc<RefCell<Node>>> without increasing strongcount

user_5920656 0
Viewed 240

Don't ask why I'm learning Rust using linked lists. I want to mutably iterate down a recursive structure of Option<Rc<RefCell<Node>>> while keeping the ability to swap out nodes and unwrap them. I have a singly-linked list type with a tail pointer to the last node.

pub struct List<T> {
    maybe_head: Option<Rc<RefCell<Node<T>>>>,
    maybe_tail: Option<Rc<RefCell<Node<T>>>>,
    length: usize,
}

struct Node<T> {
    value: T,
    maybe_next: Option<Rc<RefCell<Node<T>>>>,
}

Let's say we have a constructor and an append function:

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            maybe_head: None,
            maybe_tail: None,
            length: 0,
        }
    }

pub fn put_first(&mut self, t: T) -> &mut Self {
        let new_node_rc = Rc::new(RefCell::new(Node {
            value: t,
            maybe_next: mem::replace(&mut self.maybe_head, None),
        }));
        match self.length == 0 {
            true => {
                let new_node_rc_clone = new_node_rc.clone();
                self.maybe_head = Some(new_node_rc);
                self.maybe_tail = Some(new_node_rc_clone);
            },
            false => {
                self.maybe_head = Some(new_node_rc);
            },
        }
        self.length += 1;
        self
    }
}

I want to remove and return the final node by moving the tail pointer to its predecessor, then returning the old tail. After iterating down the list using RefCell::borrow() and Rc::clone(), the first version of remove_last() below panics when trying to unwrap the tail's Rc. How do I iterate down this recursive structure without incrementing each node's strongcount?

PANICKING VERSION

pub fn remove_last(&mut self) -> Option<T> {
        let mut opt: Option<Rc<RefCell<Node<T>>>>;
        if let Some(rc) = &self.maybe_head {
            opt = Some(Rc::clone(rc))
        } else {
            return None;
        };

        let mut rc: Rc<RefCell<Node<T>>>;

        let mut countdown_to_penultimate: i32 = self.length as i32 - 2;

        loop {
            rc = match opt {
                None => panic!(),
                Some(ref wrapped_rc) => Rc::clone(wrapped_rc),
            };

            match RefCell::borrow(&rc).maybe_next {
                Some(ref next_rc) => {
                    if countdown_to_penultimate == 0 {
                        self.maybe_tail = Some(Rc::clone(x));
                    }
                    opt = Some(Rc::clone(next_rc));
                    countdown_to_penultimate -= 1;
                },
                None => {
                    let grab_tail = match Rc::try_unwrap(opt.take().unwrap()) {
                        Ok(something) => {
                            return Some(something.into_inner().value);
                        }
                        Err(_) => panic!(),
                    };
                },
            }
        }

If all I do during iteration is move the tail pointer and enclose the iteration code in a {...} block to drop cloned references, I can then safely swap out and return the old tail, but this is obviously unsatisfying.

UNSATISFYING WORKING VERSION

pub fn remove_last(&mut self) -> Option<T> {
        {let mut opt: Option<Rc<RefCell<Node<T>>>>;
        if let Some(rc) = &self.maybe_head {
            opt = Some(Rc::clone(rc))
        } else {
            return None;
        };

        let mut rc: Rc<RefCell<Node<T>>>;

        let mut countdown_to_penultimate: i32 = self.length as i32 - 2;

        loop {
            rc = match opt {
                None => panic!(),
                Some(ref wrapped_rc) => Rc::clone(wrapped_rc),
            };

            match RefCell::borrow(&rc).maybe_next {
                Some(ref next_rc) => {
                    if countdown_to_penultimate == 0 {
                        self.maybe_tail = Some(Rc::clone(&rc));
                    }
                    opt = Some(Rc::clone(next_rc));
                    countdown_to_penultimate -= 1;
                },
                None => {
                    break;
                },
            }
        }}

        match self.maybe_tail {
            None => panic!(),
            Some(ref rc) => {
                let tail = mem::replace(&mut RefCell::borrow_mut(rc).maybe_next, None);
                return Some(Rc::try_unwrap(tail.unwrap()).ok().unwrap().into_inner().value);
            }
        };
    }
rust
1 Answers

I wrote a List::remove_last() that I can live with, although I'd still like to know what more idiomatic Rust code here might look like. I find that this traversal idiom also extends naturally into things like removing the n-th node or removing the first node that matches some predicate.

 fn remove_last(&mut self) -> Option<T> {
    let mut opt: Option<Rc<RefCell<Node<T>>>>;
    let mut rc: Rc<RefCell<Node<T>>>;

    #[allow(unused_must_use)]
    match self.length {
        0 => {
            return None;
        }
        1 => {
            let head = mem::replace(&mut self.maybe_head, None);
            mem::replace(&mut self.maybe_tail, None);
            self.length -= 1;
            return Some(
                Rc::try_unwrap(head.unwrap())
                    .ok()
                    .unwrap()
                    .into_inner()
                    .value,
            );
        }
        _ => {
            opt = Some(Rc::clone(self.maybe_head.as_ref().unwrap()));
        }
    }

    loop {
        rc = match opt {
            None => unreachable!(),
            Some(ref wrapped_rc) => Rc::clone(wrapped_rc),
        };

        let mut borrowed_node = RefCell::borrow_mut(&rc);
        let maybe_next = &mut borrowed_node.maybe_next;

        match maybe_next {
            None => unreachable!(),
            Some(_)
                if std::ptr::eq(
                    maybe_next.as_ref().unwrap().as_ptr(),
                    self.maybe_tail.as_ref().unwrap().as_ptr(),
                ) =>
            {
                borrowed_node.maybe_next = None;
                let old_tail = self.maybe_tail.replace(Rc::clone(&rc));
                self.length -= 1;
                return Some(
                    Rc::try_unwrap(old_tail.unwrap())
                        .ok()
                        .unwrap()
                        .into_inner()
                        .value,
                );
            }
            Some(ref next_rc) => {
                opt = Some(Rc::clone(next_rc));
            }
        }
    }
}
user_59206560
Related