//! This crate aims, like many others, to get rid of the pesky `'a` in your
//! guards, while keeping the easy to reason about semantics of
//! read-write-locks.
//!
//! The trick is based on a finite set of static `RwLock`s, which are mapped to
//! the memory adress of a container type implementing `StableDeref`, from the
//! `stable_deref` crate.
#![deny(missing_docs)]
#[macro_use]
extern crate lazy_static;
extern crate parking_lot;
extern crate stable_deref_trait;

use std::{mem, ptr};
use std::cell::UnsafeCell;
use std::thread::{self, ThreadId};
use std::ops::{Deref, DerefMut};
use std::fmt::{self};

use parking_lot::{RwLock, RwLockReadGuard};
use stable_deref_trait::StableDeref;

const N_LOCKS: usize = 1024;

enum State {
    Shared,
    ThreadExclusive(ThreadId),
}

lazy_static! {
    static ref LOCKS: [RwLock<State>; N_LOCKS] = {
        let mut locks: [RwLock<State>; N_LOCKS] = unsafe { mem::uninitialized() };
        for i in 0..N_LOCKS {
            unsafe {
                ptr::write(&mut locks[i], RwLock::new(State::Shared))
            }
        }
        locks
    };
}

/// A wrapper type providing run-time shared ord thread-local exclusive access
/// to an inner value of type `T`,
/// where `T` implements `StableDeref`
pub struct Thex<T> {
    cell: UnsafeCell<T>,
}

impl<T: StableDeref + fmt::Debug> fmt::Debug for Thex<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let _guard = self.shared();
        unsafe { write!(f, "Thex({:?})", &*self.cell.get()) }
    }
}

impl<T: Clone + std::fmt::Debug + StableDeref> Clone for Thex<T> {
    fn clone(&self) -> Self {
        // secure readlock
        let _guard = self.shared();
        unsafe {
            Thex {
                cell: UnsafeCell::new((*self.cell.get()).clone()),
            }
        }
    }
}

unsafe impl<T> Sync for Thex<T> {}
unsafe impl<T> Send for Thex<T> {}

#[inline]
// select a lock based on the memory address of `T`
//
// shift right, because pointers usually have their least significant
// bits set to zero
fn lock_nr<T>(ptr: *const T) -> usize {
    (ptr as usize >> 4) % N_LOCKS
}

/// A guard guaranteeing that no writes are made while it is held
pub struct Shared<T> {
    value: *const T,
    _guard: RwLockReadGuard<'static, State>,
}

/// A guard guaranteeing thread-local exclusivity while it is held
pub struct Exclusive<T> {
    value: *mut T,
    _guard: RwLockReadGuard<'static, State>,
}

impl<T> Deref for Shared<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        unsafe { &*self.value }
    }
}

impl<T> Deref for Exclusive<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        unsafe { &*self.value }
    }
}

impl<T> DerefMut for Exclusive<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { &mut *self.value }
    }
}

impl<T: StableDeref> Thex<T> {
    /// Construct a new wrapped value
    pub fn new(t: T) -> Self {
        Thex {
            cell: UnsafeCell::new(t),
        }
    }

    /// Aquire a read-only shared reference to the contained `T`
    pub fn shared(&self) -> Shared<T> {
        let t_ref = self.cell.get() as *const T;
        let lock = lock_nr(t_ref);
        {
            let read = LOCKS[lock].read();

            match *read {
                State::Shared => {
                    return Shared {
                        value: t_ref,
                        _guard: read,
                    }
                }
                _ => (),
            }
        }

        let mut write = LOCKS[lock].write();
        *write = State::Shared;

        return Shared {
            value: t_ref,
            _guard: write.downgrade(),
        };
    }

    /// Returns a thread-exclusive lock to the wrapped value
    ///
    /// # Unsafety
    /// It is unsafe to use this function, since you could easily
    /// alias the same value multiple times from the same thread.
    ///
    /// If you want a safe alternative, you can use `shared` and wrap
    /// the value in a `RefCell`
    pub unsafe fn exclusive(&self) -> Exclusive<T> {
        loop {
            let t_ref = self.cell.get() as *mut T;
            let lock = lock_nr(t_ref);
            {
                let read = LOCKS[lock].read();
                let mut exclusive = false;
                match *read {
                    State::ThreadExclusive(ref thread_id) => {
                        if thread_id == &thread::current().id() {
                            exclusive = true;
                        }
                    }
                    _ => (),
                }
                // can't wait for nll
                if exclusive {
                    // check if pointer did not change in the meantime
                    return Exclusive {
                        value: t_ref,
                        _guard: read,
                    };
                }
            }
            let mut write = LOCKS[lock].write();
            *write = State::ThreadExclusive(thread::current().id());
            // here we still have exclusive access to our unsafecell wrapped arc

            let read = write.downgrade();

            return Exclusive {
                value: t_ref,
                _guard: read,
            };
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::thread;
    use std::rc::Rc;
    use std::sync::Arc;

    #[test]
    fn boxes() {
        let n = 10_000;
        let mut thexes = vec![];
        let mut handles = vec![];

        for _ in 0..n {
            thexes.push(Thex::new(Box::new(0)));
        }

        let n_threads = 100;

        let wrapped = Arc::new(thexes);

        for _ in 0..n_threads {
            let wrapped = wrapped.clone();
            handles.push(thread::spawn(move || {
                for n in wrapped.iter() {
                    unsafe { **n.exclusive() += 1; }
                }
            }))
        }

        for handle in handles {
            handle.join().unwrap()
        }

        for n in wrapped.iter() {
            assert_eq!(**n.shared(), n_threads);
        }
    }


    #[test]
    fn rc() {
        let n = 100_000;
        let mut thexes = vec![];
        let mut handles = vec![];

        for _ in 0..n {
            thexes.push(Thex::new(Rc::new(0)));
        }

        let n_threads = 16;

        let wrapped = Arc::new(thexes);

        for _ in 0..n_threads {
            let wrapped = wrapped.clone();
            handles.push(thread::spawn(move || {
                for n in wrapped.iter() {
                    unsafe { *Rc::make_mut(&mut *n.exclusive() ) += 1; }
                }
            }))
        }

        for handle in handles.drain(..) {
            handle.join().unwrap()
        }

        for n in wrapped.iter() {
            assert_eq!(**n.shared(), n_threads);
        }

        let wrapped2 = Arc::new((*wrapped).clone());

        let mut handles2 = vec![];

        for _ in 0..n_threads {
            let wrapped = wrapped2.clone();
            handles2.push(thread::spawn(move || {
                for n in wrapped.iter() {
                    unsafe { *Rc::make_mut(&mut *n.exclusive()) += 1; }
                }
            }))
        }

        for handle in handles2.drain(..) {
            handle.join().unwrap()
        }

        for n in wrapped.iter() {
            assert_eq!(**n.shared(), n_threads);
        }

        for n in wrapped2.iter() {
            assert_eq!(**n.shared(), n_threads * 2);
        }
    }
}