#![allow(dead_code)]

use std::ops::Drop;
use std::rc::Rc;

enum Value {
    Number(i64),
    Cons(Cons),
    Null,
}

impl Value {
    // Takes ownership of the `Value`, leaving `Value::Null` in its place.
    fn take(&mut self) -> Value {
        std::mem::replace(self, Value::Null)
    }

    // Returns the `ConsInternals` of the `Value` if it is a `Value::Cons` that
    // is uniquely owned. Returns the original `Value` as an error otherwise.
    fn try_unwrap_cons(self) -> Result<ConsInternals, Value> {
        match self {
            Value::Cons(cons) => Rc::try_unwrap(cons.0).map_err(|rc| Value::Cons(Cons(rc))),
            value => Err(value),
        }
    }

    // Returns a mutable reference to the `ConsInternals` of the `Value` if it
    // is a `Value::Cons` that is uniquely owned. Otherwise, returns `None`.
    fn get_cons_mut(&mut self) -> Option<&mut ConsInternals> {
        match *self {
            Value::Cons(ref mut cons) => Rc::get_mut(&mut cons.0),
            _ => None,
        }
    }
}

struct Cons(Rc<ConsInternals>);

impl Cons {
    fn new(left: Value, right: Value) -> Value {
        Value::Cons(Cons(Rc::new(ConsInternals { left, right })))
    }
}

struct ConsInternals {
    left: Value,
    right: Value,
}

impl Drop for ConsInternals {
    // Drops a `Cons` list by repeatedly unlinking the head from the tail.
    // Handles tree-like structures by chaining together any lists encountered
    // in the `left` branch. The right-most leaf of the chain of left-values is
    // replaced with each left-value encountered in the original `Cons` list
    // until that list is empty, and then this chain of left-values is unlinked
    // in the same way as the original `Cons` list.
    //
    //      A        tail  lefts    tail  lefts    tail    tail  lefts    tail
    //    /   \  ->  B—C   E—F   -> C     E—D   -> E—D  -> D     G     -> G
    //   E    B      |     |              |        |
    //  / \  / \     D     G              G        G
    // G  F  D  C
    //
    fn drop(&mut self) {
        let mut tail = self.right.take();
        let mut left_chain = self.left.take();
        while let Value::Cons(_) = tail {
            {
                let mut left_chain_foot = &mut left_chain;

                while let Ok(mut tail_internals) = tail.try_unwrap_cons() {
                    tail = tail_internals.right.take();

                    // `get_cons_mut` currently has to be called twice to
                    // satisfy the borrow checker.
                    while let Some(_) = left_chain_foot.get_cons_mut() {
                        left_chain_foot = &mut moved(left_chain_foot).get_cons_mut().unwrap().right;
                    }

                    *left_chain_foot = tail_internals.left.take();
                }
            }

            tail = left_chain;
            left_chain = Value::Null;
        }
    }
}

// Helper to move `&mut` references rather than reborrowing them. Can also be
// spelled `{ value }`.
fn moved<T>(value: T) -> T {
    value
}

fn main() {
    use Value::Number;
    // Leaves are numbered in order of dropping
    Cons::new(
        Cons::new(
            Cons::new(Number(8), Number(4)),
            Cons::new(Number(5), Number(1)),
        ),
        Cons::new(
            Cons::new(Number(7), Number(2)),
            Cons::new(Number(6), Number(3)),
        ),
    );
}