refid/
lib.rs

1#![warn(missing_docs)]
2
3//! A small crate to enable identity checks (e.g. through pointer comparison) in contrast to
4//! equality checks (as done by [`PartialEq`])
5
6use std::hash::{Hash, Hasher};
7use std::mem::size_of_val;
8use std::ops::Deref;
9use std::ptr;
10use std::rc::{Rc, Weak as WeakRc};
11use std::sync::{Arc, Weak as WeakArc};
12
13/// Type that can be compared in regard to identity (e.g. through address comparison) instead of
14/// equality (as done by [`PartialEq`])
15///
16/// # Caveats / Notes
17///
18/// * Two references (passed to [`same`](Id::same) as references to the respective reference)
19///   are considered the same if they point to the same memory range. However, empty memory ranges
20///   (e.g. in case of empty slices or zero-sized types) are always considered identical, even if
21///   their base address is different.
22/// * Two [`Rc`]s (or two [`Arc`]s) are considered the same if they share the same reference
23///   counter (i.e. if they are clones). This also holds if their inner type is a zero-sized
24///   type.
25/// * Working with trait objects may cause surprising behavior due to current implementation of
26///   `Id` for references and Rust's pointer comparison rules.
27pub trait Id {
28    /// Check if two values are the same
29    fn same(&self, other: &Self) -> bool;
30    /// Perform hashing such that two identical values create equal hashes
31    fn hash<H: Hasher>(&self, state: &mut H);
32}
33
34/// References are identical if their pointer representation is equal or if they both refer to a
35/// zero-sized value
36impl<'a, T: ?Sized> Id for &'a T {
37    fn same(&self, other: &Self) -> bool {
38        (size_of_val(*self) == 0 && size_of_val(*other) == 0) || ptr::eq(*self, *other)
39    }
40    fn hash<H: Hasher>(&self, state: &mut H) {
41        if size_of_val(*self) != 0 {
42            Hash::hash(&ptr::addr_of!(*self), state)
43        }
44    }
45}
46
47/// `Rc`s are identical if they share the same reference counter
48impl<'a, T: ?Sized> Id for Rc<T> {
49    fn same(&self, other: &Self) -> bool {
50        Rc::ptr_eq(self, &other)
51    }
52    fn hash<H: Hasher>(&self, state: &mut H) {
53        Hash::hash(&Rc::as_ptr(self), state)
54    }
55}
56
57/// [`std::rc::Weak`](WeakRc)s are identical if they share the same reference counter
58impl<'a, T: ?Sized> Id for WeakRc<T> {
59    fn same(&self, other: &Self) -> bool {
60        WeakRc::ptr_eq(self, &other)
61    }
62    fn hash<H: Hasher>(&self, state: &mut H) {
63        Hash::hash(&WeakRc::as_ptr(self), state)
64    }
65}
66
67/// `Arc`s are identical if they share the same reference counter
68impl<'a, T: ?Sized> Id for Arc<T> {
69    fn same(&self, other: &Self) -> bool {
70        Arc::ptr_eq(self, &other)
71    }
72    fn hash<H: Hasher>(&self, state: &mut H) {
73        Hash::hash(&Arc::as_ptr(self), state)
74    }
75}
76
77/// [`std::sync::Weak`](WeakArc)s are identical if they share the same reference counter
78impl<'a, T: ?Sized> Id for WeakArc<T> {
79    fn same(&self, other: &Self) -> bool {
80        WeakArc::ptr_eq(self, &other)
81    }
82    fn hash<H: Hasher>(&self, state: &mut H) {
83        Hash::hash(&WeakArc::as_ptr(self), state)
84    }
85}
86
87/// Newtype for references (or other types that implement [`Id`]) where [equality](PartialEq) is
88/// defined by the [`same`](Id::same) method of the [`Id`] trait
89///
90/// # Example
91/// ```
92/// use refid::ById;
93/// use std::collections::HashSet;
94/// fn count_distinct<T>(slice: &[&T]) -> usize {
95///     let mut counted: HashSet<ById<&T>> = HashSet::new();
96///     let mut count: usize = 0;
97///     for item in slice {
98///         if counted.insert(ById(item)) {
99///             count += 1;
100///         }
101///     }
102///     count
103/// }
104/// let v1 = "X".to_string();
105/// let v2 = "X".to_string();
106/// let v3 = "X".to_string();
107/// assert_eq!(count_distinct(&vec![&v1, &v2, &v1, &v3]), 3);
108/// ```
109#[derive(Clone, Copy, Debug)]
110pub struct ById<T: ?Sized + Id>(
111    /// inner value (reference or other type that implements [`Id`])
112    pub T,
113);
114
115impl<T: ?Sized + Id> PartialEq for ById<T> {
116    fn eq(&self, other: &Self) -> bool {
117        Id::same(&self.0, &other.0)
118    }
119}
120
121impl<T: ?Sized + Id> Eq for ById<T> {}
122
123impl<T: ?Sized + Id> Hash for ById<T> {
124    fn hash<H: Hasher>(&self, state: &mut H) {
125        Id::hash(&self.0, state)
126    }
127}
128
129/// Similar to [`ById`], but uses [identity](Id) as defined by the dereferenced inner value
130///
131/// This can, for example, be used to wrap *references to* [`Rc`]s (or [`Arc`]s) while the identity
132/// depends on the *referenced* `Rc` or `Arc`).
133///
134/// # Example:
135///
136/// ```
137/// use std::rc::Rc;
138/// use refid::{ById, ByIdDeref};
139/// let rc1 = Rc::new(());
140/// let rc2 = Rc::new(());
141/// let rc3 = rc1.clone();
142/// assert_ne!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc2.clone()));
143/// assert_eq!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc3.clone()));
144/// // compare with:
145/// assert_ne!(ById(&rc1.clone()), ById(&rc2.clone()));
146/// assert_ne!(ById(&rc1.clone()), ById(&rc3.clone()));
147/// ```
148#[derive(Clone, Copy, Debug)]
149pub struct ByIdDeref<T: ?Sized>(
150    /// inner value
151    /// (which can be dereferenced to a reference or another type that implements [`Id`])
152    pub T,
153)
154where
155    T: Deref,
156    <T as Deref>::Target: Id;
157
158impl<T: ?Sized> PartialEq for ByIdDeref<T>
159where
160    T: Deref,
161    <T as Deref>::Target: Id,
162{
163    fn eq(&self, other: &Self) -> bool {
164        Id::same(&*self.0, &*other.0)
165    }
166}
167
168impl<T: ?Sized> Eq for ByIdDeref<T>
169where
170    T: Deref,
171    <T as Deref>::Target: Id,
172{
173}
174
175impl<T: ?Sized> Hash for ByIdDeref<T>
176where
177    T: Deref,
178    <T as Deref>::Target: Id,
179{
180    fn hash<H: Hasher>(&self, state: &mut H) {
181        Id::hash(&*self.0, state)
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188    #[test]
189    fn test_two_refs_to_same_value() {
190        let v = 1;
191        let r1 = &v;
192        let r2 = &v;
193        assert_eq!(ById(r1), ById(r2));
194    }
195    #[test]
196    fn test_two_boxes() {
197        #[derive(Debug)]
198        struct S {
199            _value: i32,
200        }
201        let v1 = Box::new(S { _value: 1 });
202        let v2 = Box::new(S { _value: 2 });
203        let r1: &S = &v1;
204        let r2: &S = &v2;
205        assert_eq!(ById(r1), ById(r1));
206        assert_ne!(ById(r1), ById(r2));
207    }
208    #[test]
209    fn test_unit_type_naive() {
210        let v1 = ();
211        let v2 = ();
212        let r1: &() = &v1;
213        let r2: &() = &v2;
214        assert_eq!(ById(r1), ById(r2));
215    }
216    #[test]
217    fn test_unit_type_unique_via_rc() {
218        use std::rc::Rc;
219        let v1 = ();
220        let v2 = ();
221        let rc1 = Rc::new(v1);
222        let rc2 = Rc::new(v2);
223        let r1: &() = &*rc1;
224        let r2: &() = &*rc2;
225        assert_eq!(ById(r1), ById(r2));
226    }
227    #[test]
228    fn test_empty_slice() {
229        let v = vec![5, 6, 7];
230        let r1: &[i32] = &v[0..0];
231        let r2: &[i32] = &v[1..1];
232        assert_eq!(ById(r1), ById(r2));
233    }
234    #[test]
235    fn test_nonempty_slices() {
236        let v1 = vec![5, 6, 7];
237        let v2 = vec![5, 6, 7];
238        let r1: &[i32] = &v1[0..1];
239        let r2: &[i32] = &v1[0..1];
240        let r3: &[i32] = &v1[0..2];
241        let r4: &[i32] = &v2[0..1];
242        assert_eq!(ById(r1), ById(r1));
243        assert_eq!(ById(r1), ById(r2));
244        assert_ne!(ById(r1), ById(r3));
245        assert_ne!(ById(r1), ById(r4));
246    }
247    #[test]
248    fn test_rc() {
249        use std::rc::Rc;
250        let v1 = vec![9];
251        let v2 = vec![9];
252        let r1 = Rc::new(v1);
253        let r2 = Rc::new(v2);
254        let r3 = r1.clone();
255        assert_ne!(ById(r1.clone()), ById(r2.clone()));
256        assert_eq!(ById(r1.clone()), ById(r3.clone()));
257    }
258    #[test]
259    fn test_arc_with_szt() {
260        use std::sync::Arc;
261        let r1 = Arc::new(());
262        let r2 = Arc::new(());
263        let r3 = r1.clone();
264        assert_ne!(ById(r1.clone()), ById(r2.clone()));
265        assert_eq!(ById(r1.clone()), ById(r3.clone()));
266    }
267    #[test]
268    fn test_hash_set() {
269        use std::collections::HashSet;
270        fn count_distinct<T>(slice: &[&T]) -> usize {
271            let mut counted: HashSet<ById<&T>> = HashSet::new();
272            let mut count: usize = 0;
273            for item in slice {
274                if counted.insert(ById(item)) {
275                    count += 1;
276                }
277            }
278            count
279        }
280        let v1 = "X".to_string();
281        let v2 = "X".to_string();
282        let v3 = "X".to_string();
283        assert_eq!(count_distinct(&vec![&v1, &v2, &v1, &v3]), 3);
284    }
285    #[test]
286    fn test_by_id_deref() {
287        use std::rc::Rc;
288        let rc1 = Rc::new(());
289        let rc2 = Rc::new(());
290        let rc3 = rc1.clone();
291        assert_ne!(ById(&rc1.clone()), ById(&rc2.clone()));
292        assert_ne!(ById(&rc1.clone()), ById(&rc3.clone()));
293        assert_ne!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc2.clone()));
294        assert_eq!(ByIdDeref(&rc1.clone()), ByIdDeref(&rc3.clone()));
295    }
296}
refid/lib.rs

refid/
lib.rs
