iddqd/tri_hash_map/
ref_mut.rs

1use crate::{DefaultHashBuilder, TriHashItem, support::map_hash::MapHash};
2use core::{
3    fmt,
4    hash::BuildHasher,
5    ops::{Deref, DerefMut},
6};
7
8/// A mutable reference to a [`TriHashMap`] item.
9///
10/// This is a wrapper around a `&mut T` that panics when dropped, if the
11/// borrowed value's keys have changed since the wrapper was created.
12///
13/// # Change detection
14///
15/// It is illegal to change the keys of a borrowed `&mut T`. `RefMut` attempts
16/// to enforce this invariant.
17///
18/// `RefMut` stores the `Hash` output of keys at creation time, and recomputes
19/// these hashes when it is dropped or when [`Self::into_ref`] is called. If a
20/// key changes, there's a small but non-negligible chance that its hash value
21/// stays the same[^collision-chance]. In that case, as long as the new key is
22/// not the same as another existing one, internal invariants are not violated
23/// and the [`TriHashMap`] will continue to work correctly. (But don't rely on
24/// this!)
25///
26/// It is also possible to deliberately write pathological `Hash`
27/// implementations that collide more often. (Don't do this either.)
28///
29/// Also, `RefMut`'s hash detection will not function if [`mem::forget`] is
30/// called on it. If a key is changed and `mem::forget` is then called on the
31/// `RefMut`, lookups by the affected key will return the wrong result (or no
32/// result at all). The map itself remains structurally valid: subsequent
33/// [`retain`](crate::TriHashMap::retain) and
34/// [`remove*`](crate::TriHashMap::remove1) operations still clean up the stale
35/// entry via a linear-scan fallback. This will not introduce memory safety
36/// issues.
37///
38/// The issues here are similar to using interior mutability (e.g. `RefCell` or
39/// `Mutex`) to mutate keys in a regular `HashMap`.
40///
41/// [`mem::forget`]: std::mem::forget
42///
43/// [^collision-chance]: The output of `Hash` is a [`u64`], so the probability
44/// of an individual hash colliding by chance is 1/2⁶⁴. Due to the [birthday
45/// problem], the probability of a collision by chance reaches 10⁻⁶ within
46/// around 6 × 10⁶ elements.
47///
48/// [`TriHashMap`]: crate::TriHashMap
49/// [birthday problem]: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table
50pub struct RefMut<
51    'a,
52    T: TriHashItem,
53    S: Clone + BuildHasher = DefaultHashBuilder,
54> {
55    inner: Option<RefMutInner<'a, T, S>>,
56}
57
58impl<'a, T: TriHashItem, S: Clone + BuildHasher> RefMut<'a, T, S> {
59    pub(super) fn new(
60        state: S,
61        hashes: [MapHash; 3],
62        borrowed: &'a mut T,
63    ) -> Self {
64        Self { inner: Some(RefMutInner { state, hashes, borrowed }) }
65    }
66
67    /// Borrows self into a shorter-lived `RefMut`.
68    ///
69    /// This `RefMut` will also check hash equality on drop.
70    pub fn reborrow(&mut self) -> RefMut<'_, T, S> {
71        let inner = self.inner.as_mut().unwrap();
72        let borrowed = &mut *inner.borrowed;
73        RefMut::new(inner.state.clone(), inner.hashes.clone(), borrowed)
74    }
75
76    /// Converts this `RefMut` into a `&'a T`.
77    pub fn into_ref(mut self) -> &'a T {
78        let inner = self.inner.take().unwrap();
79        inner.into_ref()
80    }
81}
82
83impl<T: TriHashItem, S: Clone + BuildHasher> Drop for RefMut<'_, T, S> {
84    fn drop(&mut self) {
85        if let Some(inner) = self.inner.take() {
86            inner.into_ref();
87        }
88    }
89}
90
91impl<T: TriHashItem, S: Clone + BuildHasher> Deref for RefMut<'_, T, S> {
92    type Target = T;
93
94    fn deref(&self) -> &Self::Target {
95        self.inner.as_ref().unwrap().borrowed
96    }
97}
98
99impl<T: TriHashItem, S: Clone + BuildHasher> DerefMut for RefMut<'_, T, S> {
100    fn deref_mut(&mut self) -> &mut Self::Target {
101        self.inner.as_mut().unwrap().borrowed
102    }
103}
104
105impl<T: TriHashItem + fmt::Debug, S: Clone + BuildHasher> fmt::Debug
106    for RefMut<'_, T, S>
107{
108    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
109        match self.inner {
110            Some(ref inner) => inner.fmt(f),
111            None => {
112                f.debug_struct("RefMut").field("borrowed", &"missing").finish()
113            }
114        }
115    }
116}
117
118struct RefMutInner<'a, T: TriHashItem, S> {
119    state: S,
120    hashes: [MapHash; 3],
121    borrowed: &'a mut T,
122}
123
124impl<'a, T: TriHashItem, S: BuildHasher> RefMutInner<'a, T, S> {
125    fn into_ref(self) -> &'a T {
126        if !self.hashes[0].is_same_hash(&self.state, self.borrowed.key1()) {
127            panic!("key1 changed during RefMut borrow");
128        }
129        if !self.hashes[1].is_same_hash(&self.state, self.borrowed.key2()) {
130            panic!("key2 changed during RefMut borrow");
131        }
132        if !self.hashes[2].is_same_hash(&self.state, self.borrowed.key3()) {
133            panic!("key3 changed during RefMut borrow");
134        }
135
136        self.borrowed
137    }
138}
139
140impl<T: TriHashItem + fmt::Debug, S> fmt::Debug for RefMutInner<'_, T, S> {
141    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
142        self.borrowed.fmt(f)
143    }
144}
iddqd/tri_hash_map/ref_mut.rs

iddqd/tri_hash_map/
ref_mut.rs
