refid 0.2.1

#![warn(missing_docs)]

//! A small crate to enable identity checks (e.g. through pointer comparison) in contrast to
//! equality checks (as done by [`PartialEq`])

use std::hash::{Hash, Hasher};
use std::mem::size_of_val;
use std::ops::Deref;
use std::ptr;
use std::rc::{Rc, Weak as WeakRc};
use std::sync::{Arc, Weak as WeakArc};

/// Type that can be compared in regard to identity (e.g. through address comparison) instead of
/// equality (as done by [`PartialEq`])
///
/// # Caveats / Notes
///
/// * Two references (passed to [`same`](Id::same) as references to the respective reference)
///   are considered the same if they point to the same memory range. However, empty memory ranges
///   (e.g. in case of empty slices or zero-sized types) are always considered identical, even if
///   their base address is different.
/// * Two [`Rc`]s (or two [`Arc`]s) are considered the same if they share the same reference
///   counter (i.e. if they are clones). This also holds if their inner type is a zero-sized
///   type.
/// * Working with trait objects may cause surprising behavior due to current implementation of
///   `Id` for references and Rust's pointer comparison rules.
pub trait Id {
    /// Check if two values are the same
    fn same(&self, other: &Self) -> bool;
    /// Perform hashing such that two identical values create equal hashes
    fn hash<H: Hasher>(&self, state: &mut H);
}

/// References are identical if their pointer representation is equal or if they both refer to a
/// zero-sized value
impl<'a, T: ?Sized> Id for &'a T {
    fn same(&self, other: &Self) -> bool {
        (size_of_val(*self) == 0 && size_of_val(*other) == 0) || ptr::eq(*self, *other)
    }
    fn hash<H: Hasher>(&self, state: &mut H) {
        if size_of_val(*self) != 0 {
            Hash::hash(&ptr::addr_of!(*self), state)
        }
    }
}

/// `Rc`s are identical if they share the same reference counter
impl<'a, T: ?Sized> Id for Rc<T> {
    fn same(&self, other: &Self) -> bool {
        Rc::ptr_eq(self, &other)
    }
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&Rc::as_ptr(self), state)
    }
}

/// [`std::rc::Weak`](WeakRc)s are identical if they share the same reference counter
impl<'a, T: ?Sized> Id for WeakRc<T> {
    fn same(&self, other: &Self) -> bool {
        WeakRc::ptr_eq(self, &other)
    }
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&WeakRc::as_ptr(self), state)
    }
}

/// `Arc`s are identical if they share the same reference counter
impl<'a, T: ?Sized> Id for Arc<T> {
    fn same(&self, other: &Self) -> bool {
        Arc::ptr_eq(self, &other)
    }
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&Arc::as_ptr(self), state)
    }
}

/// [`std::sync::Weak`](WeakArc)s are identical if they share the same reference counter
impl<'a, T: ?Sized> Id for WeakArc<T> {
    fn same(&self, other: &Self) -> bool {
        WeakArc::ptr_eq(self, &other)
    }
    fn hash<H: Hasher>(&self, state: &mut H) {
        Hash::hash(&WeakArc::as_ptr(self), state)
    }
}

/// Newtype for references (or other types that implement [`Id`]) where [equality](PartialEq) is
/// defined by the [`same`](Id::same) method of the [`Id`] trait
///
/// # Example
/// ```
/// use refid::ById;
/// use std::collections::HashSet;
/// fn count_distinct<T>(slice: &[&T]) -> usize {
///     let mut counted: HashSet<ById<&T>> = HashSet::new();
///     let mut count: usize = 0;
///     for item in slice {
///         if counted.insert(ById(item)) {
///             count += 1;
///         }
///     }
///     count
/// }
/// let v1 = "X".to_string();
/// let v2 = "X".to_string();
/// let v3 = "X".to_string();
/// assert_eq!(count_distinct(&vec![&v1, &v2, &v1, &v3]), 3);
/// ```
#[derive(Clone, Copy, Debug)]
pub struct ById<T: ?Sized + Id>(
    /// inner value (reference or other type that implements [`Id`])
    pub T,
);

impl<T: ?Sized + Id> PartialEq for ById<T> {
    fn eq(&self, other: &Self) -> bool {
        Id::same(&self.0, &other.0)
    }
}

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

impl<T: ?Sized + Id> Hash for ById<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        Id::hash(&self.0, state)
    }
}

/// Similar to [`ById`], but uses [identity](Id) as defined by the dereferenced inner value
///
/// This can, for example, be used to wrap *references to* [`Rc`]s (or [`Arc`]s) while the identity
/// depends on the *referenced* `Rc` or `Arc`).
///
/// # Example:
///
/// ```
/// use std::rc::Rc;
/// use refid::{ById, ByIdDeref};
/// let rc1 = Rc::new(());
/// let rc2 = Rc::new(());
/// let rc3 = rc1.clone();
/// assert_ne!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc2.clone()));
/// assert_eq!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc3.clone()));
/// // compare with:
/// assert_ne!(ById(&rc1.clone()), ById(&rc2.clone()));
/// assert_ne!(ById(&rc1.clone()), ById(&rc3.clone()));
/// ```
#[derive(Clone, Copy, Debug)]
pub struct ByIdDeref<T: ?Sized>(
    /// inner value
    /// (which can be dereferenced to a reference or another type that implements [`Id`])
    pub T,
)
where
    T: Deref,
    <T as Deref>::Target: Id;

impl<T: ?Sized> PartialEq for ByIdDeref<T>
where
    T: Deref,
    <T as Deref>::Target: Id,
{
    fn eq(&self, other: &Self) -> bool {
        Id::same(&*self.0, &*other.0)
    }
}

impl<T: ?Sized> Eq for ByIdDeref<T>
where
    T: Deref,
    <T as Deref>::Target: Id,
{
}

impl<T: ?Sized> Hash for ByIdDeref<T>
where
    T: Deref,
    <T as Deref>::Target: Id,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        Id::hash(&*self.0, state)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_two_refs_to_same_value() {
        let v = 1;
        let r1 = &v;
        let r2 = &v;
        assert_eq!(ById(r1), ById(r2));
    }
    #[test]
    fn test_two_boxes() {
        #[derive(Debug)]
        struct S {
            _value: i32,
        }
        let v1 = Box::new(S { _value: 1 });
        let v2 = Box::new(S { _value: 2 });
        let r1: &S = &v1;
        let r2: &S = &v2;
        assert_eq!(ById(r1), ById(r1));
        assert_ne!(ById(r1), ById(r2));
    }
    #[test]
    fn test_unit_type_naive() {
        let v1 = ();
        let v2 = ();
        let r1: &() = &v1;
        let r2: &() = &v2;
        assert_eq!(ById(r1), ById(r2));
    }
    #[test]
    fn test_unit_type_unique_via_rc() {
        use std::rc::Rc;
        let v1 = ();
        let v2 = ();
        let rc1 = Rc::new(v1);
        let rc2 = Rc::new(v2);
        let r1: &() = &*rc1;
        let r2: &() = &*rc2;
        assert_eq!(ById(r1), ById(r2));
    }
    #[test]
    fn test_empty_slice() {
        let v = vec![5, 6, 7];
        let r1: &[i32] = &v[0..0];
        let r2: &[i32] = &v[1..1];
        assert_eq!(ById(r1), ById(r2));
    }
    #[test]
    fn test_nonempty_slices() {
        let v1 = vec![5, 6, 7];
        let v2 = vec![5, 6, 7];
        let r1: &[i32] = &v1[0..1];
        let r2: &[i32] = &v1[0..1];
        let r3: &[i32] = &v1[0..2];
        let r4: &[i32] = &v2[0..1];
        assert_eq!(ById(r1), ById(r1));
        assert_eq!(ById(r1), ById(r2));
        assert_ne!(ById(r1), ById(r3));
        assert_ne!(ById(r1), ById(r4));
    }
    #[test]
    fn test_rc() {
        use std::rc::Rc;
        let v1 = vec![9];
        let v2 = vec![9];
        let r1 = Rc::new(v1);
        let r2 = Rc::new(v2);
        let r3 = r1.clone();
        assert_ne!(ById(r1.clone()), ById(r2.clone()));
        assert_eq!(ById(r1.clone()), ById(r3.clone()));
    }
    #[test]
    fn test_arc_with_szt() {
        use std::sync::Arc;
        let r1 = Arc::new(());
        let r2 = Arc::new(());
        let r3 = r1.clone();
        assert_ne!(ById(r1.clone()), ById(r2.clone()));
        assert_eq!(ById(r1.clone()), ById(r3.clone()));
    }
    #[test]
    fn test_hash_set() {
        use std::collections::HashSet;
        fn count_distinct<T>(slice: &[&T]) -> usize {
            let mut counted: HashSet<ById<&T>> = HashSet::new();
            let mut count: usize = 0;
            for item in slice {
                if counted.insert(ById(item)) {
                    count += 1;
                }
            }
            count
        }
        let v1 = "X".to_string();
        let v2 = "X".to_string();
        let v3 = "X".to_string();
        assert_eq!(count_distinct(&vec![&v1, &v2, &v1, &v3]), 3);
    }
    #[test]
    fn test_by_id_deref() {
        use std::rc::Rc;
        let rc1 = Rc::new(());
        let rc2 = Rc::new(());
        let rc3 = rc1.clone();
        assert_ne!(ById(&rc1.clone()), ById(&rc2.clone()));
        assert_ne!(ById(&rc1.clone()), ById(&rc3.clone()));
        assert_ne!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc2.clone()));
        assert_eq!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc3.clone()));
    }
}