#![deny(elided_lifetimes_in_paths)]

use std::pin::Pin;
use std::sync::RwLock;
use std::hash::{Hash, Hasher};
use std::collections::HashSet;
use std::borrow::Borrow;
use std::convert::Infallible;

#[derive(Debug, PartialEq, Eq, Hash)]
struct Slot<'ctx>(Pin<Box<DAG<'ctx>>>);

pub struct Arena<'ctx>(RwLock<HashSet<Slot<'ctx>>>);

impl<'ctx> Borrow<DAG<'ctx>> for Slot<'ctx> {
    fn borrow(&self) -> &DAG<'ctx> {
        &self.0
    }
}

#[derive(Clone, Copy, Eq)]
pub enum DAG<'ctx> {
    Nil,
    Branch {
        value: u32,
        left: &'ctx DAG<'ctx>,
        right: &'ctx DAG<'ctx>,
        pin: PhantomPinned
    }
}

use std::fmt;

impl fmt::Debug for DAG<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            DAG::Nil => write!(f, "Nil"),
            DAG::Branch { value, left: DAG::Nil, right: DAG::Nil, .. } =>
                write!(f, "Graph({})", value),
            DAG::Branch { value, left, right, .. } => {
                let mut debug = f.debug_struct("Graph");
                let mut debug = debug.field("value", value);

                let mut debug = if let DAG::Nil = left {
                    debug
                } else {
                    debug.field("left", left)
                };

                let mut debug = if let DAG::Nil = right {
                    debug
                } else {
                    debug.field("right", right)
                };

                debug.finish()
            }
        }
    }
}

use std::marker::PhantomPinned;

impl<'a, 'b> PartialEq<DAG<'b>> for DAG<'a> {
    fn eq(&self, other: &DAG<'b>) -> bool {
        match (self, other) {
            (DAG::Nil, DAG::Nil) => true,
            (
                DAG::Branch { value: av, left: al, right: ar, .. },
                DAG::Branch { value: bv, left: bl, right: br, .. }
            ) => {
                std::ptr::eq(al as &DAG<'_>, bl as &DAG<'_>) &&
                std::ptr::eq(ar as &DAG<'_>, br as &DAG<'_>) &&
                av == bv
            },
            _ => false
        }
    }
}

impl Hash for DAG<'_> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            DAG::Nil => state.write_u8(0),
            DAG::Branch { value, left, right, .. } => {
                std::ptr::hash(left as &DAG<'_>, state);
                std::ptr::hash(right as &DAG<'_>, state);
                value.hash(state);
            }
        }
    }
}

impl Default for Arena<'_> {
    fn default() -> Self {
        Self::new()
    }
}

impl<'ctx> DAG<'ctx> {
    pub fn branch(value: u32, left: &'ctx DAG<'ctx>, right: &'ctx DAG<'ctx>) -> Self {
        DAG::Branch {
            value,
            left,
            right,
            pin: PhantomPinned
        }
    }
}

impl<'ctx> Arena<'ctx> {
    pub fn new() -> Self {
        Self(RwLock::new(HashSet::new()))
    }

    pub fn insert(&'ctx self, ty: DAG<'ctx>) -> &'ctx DAG<'ctx> {
        let mut elements = self.0.write().unwrap();
        let elements = &mut *elements;

        unsafe {
            match elements.get(&ty).map(Slot::borrow) {
                Some(ty) => std::mem::transmute::<&DAG<'ctx>, &'ctx DAG<'ctx>>(ty),
                None => {
                    elements.insert(Slot(Box::pin(ty)));

                    match elements.get(&ty).map(Slot::borrow) {
                        Some(ty) => std::mem::transmute::<&DAG<'ctx>, &'ctx DAG<'ctx>>(ty),
                        None => {
                            debug_assert!(false, "get failed!");
                            std::hint::unreachable_unchecked()
                        }
                    }
                }
            }
        }
    }

    pub fn get(&'ctx self, ty: &DAG<'ctx>) -> Option<&'ctx DAG<'ctx>> {
        let elements = self.0.read().unwrap();
        let elements = &*elements;

        unsafe {
            std::mem::transmute::<Option<&DAG<'ctx>>, Option<&'ctx DAG<'ctx>>>(
                elements.get(ty).map(Slot::borrow)
            )
        }
    }
}

fn main() {
    let arena = Arena::new();

    let nil = arena.insert(DAG::Nil);
    let _0 = arena.insert(DAG::branch(0, nil, nil));
    let _1 = arena.insert(DAG::branch(1, nil, _0));
    let _2 = arena.insert(DAG::branch(2, _0, _1));

    println!("{:?}", nil);
    println!("{:?}", _0);
    println!("{:?}", _1);
    println!("{:?}", _2);
}