//! Authors: Maurice Laveaux, Flip van Spaendonck and Jan Friso Groote

use std::error::Error;

use std::fmt::Debug;

use std::ops::Deref;

use std::ops::DerefMut;

#[cfg(not(loom))]

mod inner {

    pub use std::cell::UnsafeCell;

    pub use std::hint::spin_loop;

    pub use std::sync::Arc;

    pub use std::sync::Mutex;

    pub use std::sync::MutexGuard;

    pub use std::sync::atomic::AtomicBool;

    pub use std::sync::atomic::Ordering;

    pub use std::sync::atomic::fence;

}

// We replace the standard implementation by loom's implementation.

#[cfg(loom)]

mod inner {

    pub use std::mem::ManuallyDrop;

    pub use loom::cell::UnsafeCell;

    pub use loom::hint::spin_loop;

    pub use loom::sync::Arc;

    pub use loom::sync::Mutex;

    pub use loom::sync::MutexGuard;

    pub use loom::sync::atomic::AtomicBool;

    pub use loom::sync::atomic::Ordering;

    pub use loom::sync::atomic::fence;

}

use inner::*;

use crossbeam_utils::CachePadded;

/// A shared mutex (readers-writer lock) implementation based on the so-called

/// busy-forbidden protocol.

///

/// # Details

///

/// Compared to a regular [std::sync::Mutex] this struct is Send but not Sync.

/// This means that every thread must acquire a clone of the shared mutex and

/// the cloned instances of the same shared mutex guarantee shared access

/// through the `read` operation and exclusive access for the `write` operation

/// of the given object.

pub struct BfSharedMutex<T> {

    /// The local control bits of each instance.

    ///

    /// TODO: Maybe use pin to share the control bits among shared mutexes.

    control: Arc<CachePadded<SharedMutexControl>>,

    /// Index into the `other` table.

    index: usize,

    /// Information shared between all clones.

    shared: Arc<CachePadded<SharedData<T>>>,

}

// SAFETY: Sending a BfSharedMutex to another thread transfers ownership of the

// protected T.

unsafe impl<T: Send> Send for BfSharedMutex<T> {}

/// The busy and forbidden flags used to implement the protocol.

#[derive(Default)]

struct SharedMutexControl {

    busy: AtomicBool,

    forbidden: AtomicBool,

}

/// The shared data between all instances of the shared mutex.

struct SharedData<T> {

    /// The object that is being protected.

    object: UnsafeCell<T>,

    /// The list of all the shared mutex instances.

    other: Mutex<Vec<Option<Arc<CachePadded<SharedMutexControl>>>>>,

}

impl<T> BfSharedMutex<T> {

    /// Constructs a new shared mutex for protecting access to the given object.

}

impl<T> Clone for BfSharedMutex<T> {

        // Register a new instance in the other list

                // Reuse an empty slot if available.

            }

            None => {

            }

        };

}

impl<T> Drop for BfSharedMutex<T> {

        // Remove ourselves from the table.

        // Trim trailing None slots to keep the vec compact.

}

/// The guard object for exclusive access to the underlying object.

#[must_use = "Dropping the guard unlocks the shared mutex immediately"]

pub struct BfSharedMutexWriteGuard<'a, T> {

    #[allow(dead_code)]

    mutex: &'a BfSharedMutex<T>,

    guard: MutexGuard<'a, Vec<Option<Arc<CachePadded<SharedMutexControl>>>>>,

    /// When loom is enabled, we store a write reference tracked by Loom.

    #[cfg(loom)]

    ptr: ManuallyDrop<loom::cell::MutPtr<T>>,

}

/// Allow dereferencing the underlying object.

impl<T> Deref for BfSharedMutexWriteGuard<'_, T> {

    type Target = T;

        // We are the only guard after `write()`, so we can provide immutable access to the underlying object. (No mutable references the guard can exist)

        #[cfg(not(loom))]

        unsafe {

        }

        #[cfg(loom)]

        unsafe {

            self.ptr.deref().deref()

        }

}

impl<T> DerefMut for BfSharedMutexWriteGuard<'_, T> {

        // We are the only guard after `write()`, so we can provide mutable access to the underlying object.

        #[cfg(not(loom))]

        #[cfg(loom)]

        unsafe {

            self.ptr.deref().deref()

        }

}

impl<T> Drop for BfSharedMutexWriteGuard<'_, T> {

        // End Loom's write tracking before releasing the protocol.

        #[cfg(loom)]

        unsafe {

            ManuallyDrop::drop(&mut self.ptr);

        }

        // Allow other threads to acquire access to the shared mutex.

        // The mutex guard is then dropped here.

}

// SAFETY: Sharing &WriteGuard across threads only exposes &T.

unsafe impl<T: Sync> Sync for BfSharedMutexWriteGuard<'_, T> {}

#[must_use = "Dropping the guard unlocks the shared mutex immediately"]

pub struct BfSharedMutexReadGuard<'a, T> {

    mutex: &'a BfSharedMutex<T>,

    /// When loom is enabled, we store a read reference tracked by Loom.

    #[cfg(loom)]

    ptr: ManuallyDrop<loom::cell::ConstPtr<T>>,

}

// SAFETY: Sharing &ReadGuard across threads only exposes &T.

unsafe impl<T: Sync> Sync for BfSharedMutexReadGuard<'_, T> {}

/// Allows dereferencing the underlying object.

impl<T> Deref for BfSharedMutexReadGuard<'_, T> {

    type Target = T;

        // There can only be shared guards, which only provide immutable access to the object.

        #[cfg(not(loom))]

        unsafe {

        }

        #[cfg(loom)]

        unsafe {

            self.ptr.deref().deref()

        }

}

impl<T> Drop for BfSharedMutexReadGuard<'_, T> {

            "Cannot unlock shared lock that was not acquired"

        );

        // End Loom's read tracking before releasing the protocol.

        #[cfg(loom)]

        unsafe {

            ManuallyDrop::drop(&mut self.ptr);

        }

        // Release is sufficient, this synchronises the writes of this thread with writer.

}

impl<T> BfSharedMutex<T> {

    /// Provides read access to the underlying object, allowing multiple immutable references to it.

            "Cannot acquire read access again inside a reader section"

        );

            // Signal the writer that this thread is no longer busy, allowing it to make progress.

            // For loom with spin locks we must ensure that other threads can make progress for fairness.

            #[cfg(loom)]

            loom::thread::yield_now();

            // Wait for the mutex of the writer.

            // Allow another thread to acquire the lock.

            #[cfg(loom)]

            loom::thread::yield_now();

        }

        // We now have immutable access to the object due to the protocol.

    /// Creates a new `BfSharedMutexReadGuard` without checking if the lock is held.

    ///

    /// # Safety

    ///

    /// This method must only be called if the thread logically holds a read lock.

    ///

    /// This function does not increment the read count of the lock. Calling this function when a

    /// guard has already been produced is undefined behaviour unless the guard was forgotten

    /// with `mem::forget`.

    /// Returns a raw pointer to the underlying data.

    ///

    /// This is useful when combined with `mem::forget` to hold a lock without

    /// the need to maintain a [`BfSharedMutexReadGuard`] or [`BfSharedMutexWriteGuard`] object

    /// alive, for example when dealing with FFI.

    ///

    /// # Safety

    ///

    /// You must ensure that there are no data races when dereferencing the

    /// returned pointer, for example if the current thread logically owns a

    /// [`BfSharedMutexReadGuard`] or [`BfSharedMutexWriteGuard`] but that guard has been discarded

    /// using `mem::forget`.

    #[cfg(not(loom))]

    #[cfg(loom)]

    pub fn data_ptr(&self) -> loom::cell::ConstPtr<T> {

        self.shared.object.get()

    }

    /// Provide write access to the underlying object, only a single mutable reference to the object exists.

            "Can only exclusive lock outside of a shared lock, no upgrading!"

        );

            "Can not acquire exclusive lock inside of exclusive section"

        );

        // Make all instances wait due to forbidden access.

                "Other instance is already forbidden, this cannot happen"

            );

        }

        // Wait for the instances to exit their busy status.

            {

                // We just synchronize with the busy store of the other instances.

        }

        // We now have exclusive access to the object according to the protocol

    /// Check if this instance's read lock is currently held (i.e., this instance's `busy` flag is set).

    ///

    /// Note: this only reflects the state of **this** clone of the shared mutex. Other clones

    /// may independently hold their own read locks.

    /// Check if this instance has been forbidden from acquiring a read lock, which indicates

    /// that another clone is holding or acquiring a write lock.

    /// Obtain mutable access to the object without locking, is safe because we have mutable access.

        #[cfg(not(loom))]

        #[cfg(loom)]

        unsafe {

            self.shared.object.get_mut().with(|ptr| &mut *ptr)

        }

}

impl<T: Debug> Debug for BfSharedMutex<T> {

        }

}

/// A global shared mutex that can be used to protect global data.

///

/// # Details

///

/// This is a wrapper around `BfSharedMutex` that provides a global instance

/// that can be used to protect global data. Must be cloned to obtain mutable

/// access.

pub struct GlobalBfSharedMutex<T> {

    /// The shared mutex that is used to protect the global data.

    pub shared_mutex: BfSharedMutex<T>,

}

impl<T> GlobalBfSharedMutex<T> {

    /// Constructs a new global shared mutex for protecting access to the given object.

    /// Returns a clone of the global shared mutex, which allows writing and reading.

}

// SAFETY: Sending a GlobalBfSharedMutex<T> to another thread requires T: Send, same as RwLock<T>.

unsafe impl<T: Send> Send for GlobalBfSharedMutex<T> {}

// SAFETY: Multiple threads holding &GlobalBfSharedMutex<T> can call share() concurrently

unsafe impl<T: Send + Sync> Sync for GlobalBfSharedMutex<T> {}

#[cfg(test)]

mod tests {

    use std::hint::black_box;

    use rand::RngExt;

    use merc_utilities::random_test_threads;

    use merc_utilities::test_threads;

    use super::BfSharedMutex;

    // These are just simple tests.

    #[test]

    #[cfg_attr(miri, ignore)]

        );

    #[test]

    #[cfg_attr(miri, ignore)]

                    // Read a random index.

        );

    #[test]

    #[cfg(loom)]

    fn test_loom_bf_shared_mutex() {

        let mut builder = loom::model::Builder::new();

        builder.preemption_bound = Some(1);

        builder.check(|| {

            let shared_mutex = BfSharedMutex::new(false);

            let threads: Vec<_> = (0..3)

                .map(|_| {

                    let shared_mutex = shared_mutex.clone();

                    loom::thread::spawn(move || {

                        // Just perform some operations on the shared mutex.

                        let result = *shared_mutex.read().unwrap();

                        *shared_mutex.write().unwrap() = !result;

                    })

                })

                .collect();

            for th in threads {

                th.join().unwrap();

            }

        });

    }

}