#![feature(const_fn)]
#![feature(untagged_unions)]
#![feature(type_alias_enum_variants)]
use std::sync::atomic::{Ordering, AtomicU8};
use std::sync::Arc;
use std::cell::UnsafeCell;
use std::ops::Deref;
use std::fmt::{Debug, Formatter, Error};
use parking_lot_core::SpinWait; // 0.4.0

union Thunk<T, F: FnOnce()->T> {
    thunk: F,
    value: T,
}

#[repr(u8)]
enum ThunkState {
    Locked,
    Thunk,
    Complete,
}

impl ThunkState {
    pub const LOCKED : u8 = Self::Locked as u8;
    pub const THUNK : u8 = Self::Thunk as u8;
    pub const COMPLETE : u8 = Self::Complete as u8;
}

pub struct Lazy<T, F: FnOnce()->T> (UnsafeCell<Thunk<T, F>>, AtomicU8);

unsafe impl <T, F: FnOnce()->T> Sync for Lazy<T, F> where T: Sync, F: Send {}

impl <T, F: FnOnce()->T> Lazy<T, F> {
    pub const fn new(f: F) -> Self {
        Self(UnsafeCell::new(Thunk{thunk: f}), AtomicU8::new(ThunkState::LOCKED))
    }

    pub const fn from_value(v: T) -> Self {
        Self(UnsafeCell::new(Thunk{value: v}), AtomicU8::new(ThunkState::COMPLETE))
    }

    fn force(&self) {
        match self.1.compare_and_swap(ThunkState::THUNK, ThunkState::LOCKED, Ordering::AcqRel) {
            ThunkState::LOCKED => {
                let mut spin = SpinWait::new();
                while self.1.load(Ordering::Acquire) != ThunkState::COMPLETE{
                    spin.spin();
                }
            }
            ThunkState::THUNK => unsafe {
                   let f = self.0.get().read().thunk;
                   let v = f();
                   (*self.0.get()).value = v;
                   self.1.store(ThunkState::COMPLETE, Ordering::Release);
            }
            ThunkState::COMPLETE => {},
            _ => unreachable!(),
        }
    }
}

impl <T, F: FnOnce()->T> From<T> for Lazy<T, F> {
    fn from(val: T) -> Self {
        Self::from_value(val)
    }
}

impl <T, F: FnOnce()->T> Deref for Lazy<T, F> {
    type Target = T;
    fn deref(&self) -> &T {
        self.force();
        unsafe { &(*self.0.get()).value }
    }
}

impl <T, F: FnOnce()->T> Drop for Lazy<T, F> {
    fn drop(&mut self) {
        match self.1.load(Ordering::SeqCst) {
            ThunkState::COMPLETE => {
                let _ = unsafe { self.0.get().read().value };
            }
            ThunkState::THUNK => {
                let _ = unsafe { self.0.get().read().thunk };
            }
            ThunkState::COMPLETE => unreachable!(),
            _ => unreachable!(),
        }
    }
}

#[derive(Clone)]
pub enum ListInner<T> {
    Null,
    Cons(T, List<T>),
}

#[derive(Clone)]
pub struct List<T> (Arc<Lazy<ListInner<T>, Box<dyn FnOnce()->ListInner<T>>>>);

macro_rules! list {
    () => (List(Arc::new(Lazy::from_value(ListInner::Null))));
    (($head:expr) : $tail:expr) => (List(Arc::new(Lazy::from_value(ListInner::Cons($head, $tail)))));
    ($head:tt : $tail:expr) => (list![($head) : $tail]);
    ($head:expr $(,$tail:expr)*) => (list![($head) : list!($($tail)*)]);
}

impl <T: Clone> List<T> {
    pub fn map<U>(&self, f: impl Fn(T)->U) -> List<U> {
        match **self {
            ListInner::Null => list![],
            ListInner::Cons(ref x, ref xs) => list!((f(x.clone())) : xs.map(f)),
        }
    }

    pub fn append(&self, tail: Self) -> Self {
        match **self {
            ListInner::Null => tail,
            ListInner::Cons(ref x, ref xs) => list!((x.clone()) : xs.append(tail)),
        }
    }

    pub fn flat_map<U: Clone>(&self, f: impl Fn(T)->List<U>) -> List<U> {
        List::flatten(&self.map(f))
    }
}

impl <T> Deref for List<T> {
    type Target = ListInner<T>;
    fn deref(&self) -> &Self::Target {
        &**self.0
    }
}

impl <T: Clone> List<List<T>> {
    pub fn flatten(&self) -> List<T> {
        match **self {
            ListInner::Null => list![],
            ListInner::Cons(ref x, ref xs) => x.append(xs.flatten()),
        }
    }
}

impl <T: Debug> Debug for List<T> {
    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        let mut l = f.debug_list();
        let mut current = self;
        while let ListInner::Cons(ref x, ref xs) = **current {
            l.entry(x);
            current = xs;
        }
        l.finish()
    }
}

fn prod(input: &List<List<i32>>) -> List<List<i32>> {
    match **input {
        ListInner::Null => list![list![]],
        ListInner::Cons(ref xs, ref xss) => {
            let p = prod(xss);
            xs.flat_map(|k| p.map(|t| list![(k.clone()) : t]))
        }
    }
}

fn main() {
    println!("{:?}", prod(&list![list![1,2], list![3,4]]));
}