use std::alloc::handle_alloc_error;

use std::collections::hash_map::RandomState;

use std::fmt;

use std::hash::BuildHasher;

use std::hash::Hash;

use std::hash::Hasher;

use std::ops::Deref;

use std::ptr::NonNull;

use std::ptr::addr_eq;

#[cfg(debug_assertions)]

use std::sync::Arc;

use allocator_api2::alloc::Allocator;

use allocator_api2::alloc::Global;

use allocator_api2::alloc::Layout;

use dashmap::DashSet;

use equivalent::Equivalent;

use crate::AllocatorDst;

use crate::SliceDst;

/// A handle to an element stored in a [`StablePointerSet`].

///

/// The handle itself is inert: holding, comparing, hashing and copying it is

/// always sound. Reading the pointee, however, is only valid while the element

/// is still in its owning set, which the borrow checker does not track — so

/// dereferencing goes through the unsafe [`StablePointer::deref`].

///

/// Comparisons are based on the pointer's address, not the value it points to.

///

/// Deliberately not `Clone`: duplicating a handle extends the set of pointers

/// that must be kept valid, so duplication goes through the unsafe

/// [`StablePointer::copy`].

#[repr(C)]

pub struct StablePointer<T: ?Sized> {

    /// The raw pointer to the element.

    /// This is a NonNull pointer, which means it is guaranteed to be non-null.

    ptr: NonNull<T>,

    /// Keep track of reference counts in debug mode.

    #[cfg(debug_assertions)]

    reference_counter: Arc<()>,

}

/// Check that the Option<StablePointer> is the same size as a usize for release builds.

#[cfg(not(debug_assertions))]

const _: () = assert!(std::mem::size_of::<Option<StablePointer<usize>>>() == std::mem::size_of::<usize>());

impl<T: ?Sized> StablePointer<T> {

    /// Returns true if this is the last reference to the pointer.

        #[cfg(debug_assertions)]

        {

            // There is a reference in the table, and the one of `self.ptr`.

        }

        #[cfg(not(debug_assertions))]

        {

            true

        }

    /// Creates a new StablePointer from a raw pointer.

    ///

    /// # Safety

    ///

    /// The caller must ensure that the pointer is valid and points to a valid T that outlives the StablePointer.

    /// Creates a new StablePointer from a raw pointer while preserving the

    /// debug reference counter from another StablePointer.

    ///

    /// # Safety

    ///

    /// The caller must ensure that `ptr` points to the same allocation as

    /// `source` (potentially with a different pointee type/metadata) and

    /// remains valid for at least as long as any derived StablePointer.

    /// Returns public access to the underlying pointer.

}

impl<T: ?Sized> PartialEq for StablePointer<T> {

        // Identity is the pointer address; the pointee is never read here.

}

impl<T: ?Sized> Eq for StablePointer<T> {}

impl<T: ?Sized> Ord for StablePointer<T> {

}

impl<T: ?Sized> PartialOrd for StablePointer<T> {

}

impl<T: ?Sized> Hash for StablePointer<T> {

}

unsafe impl<T: ?Sized + Send> Send for StablePointer<T> {}

unsafe impl<T: ?Sized + Sync> Sync for StablePointer<T> {}

impl<T: ?Sized> StablePointer<T> {

    /// Returns a copy of the StablePointer.

    ///

    /// # Safety

    /// The caller must ensure the pointer points to a valid T that outlives the returned StablePointer.

    /// In particular the element must not be removed from the owning [`StablePointerSet`] (nor the set

    /// dropped) while the copy is alive, since [`Deref`] dereferences the pointer without any check.

    /// Creates a new StablePointer from a boxed element.

    /// Borrows the pointee.

    ///

    /// # Safety

    ///

    /// The element must still be present in its owning [`StablePointerSet`] (the

    /// set must not have been dropped, nor the element removed) for the duration

    /// of the returned borrow. This is not tracked by the borrow checker.

        // SAFETY: the caller guarantees the pointee outlives the returned borrow.

}

impl<T: fmt::Debug + ?Sized> fmt::Debug for StablePointer<T> {

}

/// A set that provides stable pointers to its elements.

///

/// Similar to `IndexedSet` but uses pointers instead of indices for direct access to elements.

/// Elements are stored in stable memory locations using a custom allocator, with the hash set maintaining references.

///

/// The set can use a custom hasher type for potentially better performance based on workload characteristics.

/// Uses an allocator for memory management, defaulting to the global allocator.

pub struct StablePointerSet<T: ?Sized, S = RandomState, A = Global>

where

    T: Hash + Eq + SliceDst,

    S: BuildHasher + Clone,

    A: Allocator + AllocatorDst,

{

    index: DashSet<Entry<T>, S>,

    allocator: A,

}

impl<T: ?Sized> Default for StablePointerSet<T, RandomState, Global>

where

    T: Hash + Eq + SliceDst,

{

}

impl<T: ?Sized> StablePointerSet<T, RandomState, Global>

where

    T: Hash + Eq + SliceDst,

{

    /// Creates an empty StablePointerSet with the default hasher and global allocator.

    /// Creates an empty StablePointerSet with the specified capacity, default hasher, and global allocator.

}

impl<T: ?Sized, S> StablePointerSet<T, S, Global>

where

    T: Hash + Eq + SliceDst,

    S: BuildHasher + Clone,

{

    /// Creates an empty StablePointerSet with the specified hasher and global allocator.

    /// Creates an empty StablePointerSet with the specified capacity, hasher, and global allocator.

}

impl<T: ?Sized, S, A> StablePointerSet<T, S, A>

where

    T: Hash + Eq + SliceDst,

    S: BuildHasher + Clone,

    A: Allocator + AllocatorDst,

{

    /// Creates an empty StablePointerSet with the specified allocator and default hasher.

    {

    /// Creates an empty StablePointerSet with the specified capacity, allocator, and default hasher.

    {

    /// Creates an empty StablePointerSet with the specified hasher and allocator.

    /// Creates an empty StablePointerSet with the specified capacity, hasher, and allocator.

    /// Returns the number of elements in the set.

    /// Returns true if the set is empty.

    /// Returns the capacity of the set.

    /// Inserts an element into the set using an equivalent value.

    ///

    /// This version takes a reference to an equivalent value and creates the value to insert

    /// only if it doesn't already exist in the set. Returns a stable pointer to the element

    /// and a boolean indicating whether the element was inserted.

    {

        // Check if we already have this value

            // We already have this value, return pointer to existing element

        // Allocate memory for the value

        // Write the value to the allocated memory

        // Insert new value using allocator

        // First add to storage, then to index

            // Call the drop function

            // Remove the entry we just created since it was not inserted

        // Insertion succeeded.

    /// Returns `true` if the set contains a value.

    {

    /// Returns a stable pointer to a value in the set, if present.

    ///

    /// Searches for a value equal to the provided reference and returns a pointer to the stored element.

    /// The returned pointer remains valid until the element is removed from the set.

    {

        // Find the boxed element that contains an equivalent value

        // SAFETY: The pointer is valid as long as the set is valid.

    /// Returns an iterator over the elements of the set.

    ///

    /// # Safety

    ///

    /// The yielded references borrow into the stable allocations. The caller

    /// must ensure no element is removed while a yielded reference is live.

        // SAFETY: each pointer is valid while its element remains in the set,

        // which the caller upholds per the contract above.

    /// Removes an element from the set using its stable pointer.

    ///

    /// Returns true if the element was found and removed.

    ///

    /// # Safety

    ///

    /// `pointer` must be the last [`StablePointer`] to the element; removal invalidates every

    /// remaining pointer to it, and dereferencing such a pointer afterwards is undefined

    /// behaviour. This is only checked in debug builds.

            "Pointer must be the last reference to the element"

        );

        // SAFETY: This is the last reference to the element, so it is still

        // present in the set and safe to dereference.

            // SAFETY: We have exclusive access during drop and the pointer is valid

        } else {

        }

    /// Retains only the elements specified by the predicate, modifying the set in-place.

    ///

    /// The predicate closure is called with a mutable reference to each element and must

    /// return true if the element should remain in the set.

    ///

    /// # Safety

    ///

    /// It invalidates any StablePointers to removed elements; the caller must guarantee that no

    /// such pointer is dereferenced afterwards.

    {

        // First pass: determine what to keep/remove without modifying the collection

                // Note that retain can remove disconnect graphs of elements in

                // one go, so it is not necessarily the case that there is only

                // one reference to the element.

                // SAFETY: We have exclusive access during drop and the pointer

                // is valid

    /// Returns mutable access to the underlying allocator.

    /// Drops the element at the given pointer and deallocates its memory.

    ///

    /// # Safety

    ///

    /// This requires that ptr can be dereferenced, so it must point to a valid element.

        // SAFETY: We have exclusive access during drop and the pointer is valid

}

impl<T: ?Sized + SliceDst, S, A> StablePointerSet<T, S, A>

where

    T: Hash + Eq,

    S: BuildHasher + Clone,

    A: Allocator + AllocatorDst + Sync,

{

    /// Clears the set, removing all values and invalidating all pointers.

    ///

    /// # Safety

    ///

    /// This is unsafe because it invalidates all pointers to the elements in the set; the caller

    /// must guarantee that none of them is dereferenced afterwards.

        #[cfg(debug_assertions)]

            "All pointers must be the last reference to the element"

        );

        // Manually deallocate all entries before clearing

            // SAFETY: We have exclusive access during drop and the pointer is valid

        }

    /// Inserts an element into the set using an equivalent value.

    ///

    /// This version takes a reference to an equivalent value and creates the

    /// value to insert only if it doesn't already exist in the set. Returns a

    /// stable pointer to the element and a boolean indicating whether the

    /// element was inserted.

    ///

    /// # Safety

    ///

    /// construct must fully initialize the value at the given pointer,

    /// otherwise it may lead to undefined behavior.

    {

        // Check if we already have this value

            // We already have this value, return pointer to existing element

        // Allocate space for the entry and construct it

        loop {

                // Add the result to the storage, it could be at this point that the entry was inserted by another thread. So

                // this insertion might actually fail, in which case we should clean up the created entry and return the old pointer.

                // TODO: I suppose this can go wrong with begin_insert(x); insert(x); remove(x); end_insert(x) chain.

                    // SAFETY: We have exclusive access during drop and the pointer is valid

            } else {

                // Value was successfully inserted

            }

        }

}

impl<T, S, A> StablePointerSet<T, S, A>

where

    T: Hash + Eq + SliceDst,

    S: BuildHasher + Clone,

    A: Allocator + AllocatorDst,

{

    /// Inserts an element into the set.

    ///

    /// If the set did not have this value present, `true` is returned along

    /// with a stable pointer to the inserted element.

    ///

    /// If the set already had this value present, `false` is returned along

    /// with a stable pointer to the existing element.

            // We already have this value, return pointer to existing element

        // Insert new value using allocator

        // First add to storage, then to index

            // Drop and deallocate the allocation we created since it was not inserted.

}

impl<T: ?Sized, S, A> Drop for StablePointerSet<T, S, A>

where

    T: Hash + Eq + SliceDst,

    S: BuildHasher + Clone,

    A: Allocator + AllocatorDst,

{

        #[cfg(debug_assertions)]

            "All pointers must be the last reference to the element"

        );

        // Manually drop and deallocate all entries

        }

}

/// A helper struct to store the allocated element in the set.

///

/// Uses manual allocation instead of Box for custom allocator support.

/// Optionally stores a reference counter for debugging purposes in debug builds.

struct Entry<T: ?Sized> {

    /// Pointer to the allocated value

    ptr: NonNull<T>,

    #[cfg(debug_assertions)]

    reference_counter: Arc<()>,

}

unsafe impl<T: ?Sized + Send> Send for Entry<T> {}

unsafe impl<T: ?Sized + Sync> Sync for Entry<T> {}

impl<T: ?Sized> Entry<T> {

    /// Creates a new entry by allocating memory for the value using the provided allocator.

}

impl<T: ?Sized> Deref for Entry<T> {

    type Target = T;

        // SAFETY: The pointer is valid as long as the Entry exists

}

impl<T: PartialEq + ?Sized> PartialEq for Entry<T> {

}

impl<T: Hash + ?Sized> Hash for Entry<T> {

}

impl<T: Eq + ?Sized> Eq for Entry<T> {}

/// A helper struct to look up elements in the set using a reference.

#[derive(Hash, PartialEq, Eq)]

struct LookUp<'a, T: ?Sized>(&'a T);

impl<T: ?Sized, Q: ?Sized> Equivalent<Entry<T>> for LookUp<'_, Q>

where

    Q: Equivalent<T>,

{

}

#[cfg(test)]

mod tests {

    use std::hash::BuildHasherDefault;

    use std::hash::Hash;

    use std::hash::Hasher;

    use std::hash::RandomState;

    use allocator_api2::alloc::System;

    use dashmap::Equivalent;

    use rustc_hash::FxHasher;

    use crate::StablePointerSet;

    #[test]

        // Insert a value and ensure we get it back

        // SAFETY: the elements live in `set` for the duration of the test.

        // Insert the same value and ensure we get the same pointer

        // Pointers to the same value should be identical

        // Verify that we have only one element

    #[test]

    #[test]

        // SAFETY: the elements live in `set` for the duration of the test.

    #[test]

        // SAFETY: no element is removed while the iterator references are live.

    #[test]

        #[derive(PartialEq, Eq, Debug)]

        struct TestValue {

            id: i32,

            name: String,

        }

        impl From<&i32> for TestValue {

        }

        impl Hash for TestValue {

        }

        impl Equivalent<TestValue> for i32 {

        }

        // Insert using equivalent reference (i32 -> TestValue)

        // SAFETY: the elements live in `set` for the duration of the test.

        // Try inserting the same value again via equivalent

        // Insert a different value

        // Ensure we have exactly two elements

    #[test]

        // Test dereferencing

        // SAFETY: the element lives in `set` for the duration of the test.

        // Test methods on the dereferenced value

    #[test]

        // Insert values

        // SAFETY: `ptr1` and `ptr2` are the last pointers to their elements.

        unsafe {

            // Remove one value

            // Remove other value

        }

    #[test]

        // Insert values

        // SAFETY: No pointers to the removed (odd) elements are used afterwards,

        // and each predicate borrow is only read while the element is present.

        unsafe {

            // Retain only even numbers

        }

        // Verify results

        // SAFETY: `ptr2` and `ptr4` are the last pointers to their elements.

        unsafe {

            // Verify that removed pointers are invalid and remaining are valid

        }

    #[test]

        // Test with System allocator

        // Insert some values

        // Check that everything works as expected

        // SAFETY: the elements live in `set` for the duration of the test.

        // Test contains

    #[test]

        // Use both custom hasher and allocator

        // Insert some values

        // Check that everything works as expected

        // SAFETY: the elements live in `set` for the duration of the test.

        // Test contains

}