iddqd/id_hash_map/
ref_mut.rs

1use crate::{DefaultHashBuilder, IdHashItem, support::map_hash::MapHash};
2use core::{
3    fmt,
4    hash::BuildHasher,
5    ops::{Deref, DerefMut},
6};
7
8/// A mutable reference to an [`IdHashMap`] 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 key of a borrowed `&mut T`. `RefMut` attempts to
16/// enforce this invariant.
17///
18/// `RefMut` stores the `Hash` output of the key at creation time, and
19/// recomputes this hash when it is dropped or when [`Self::into_ref`] is
20/// called. If a key changes, there's a small but non-negligible chance that its
21/// hash value stays the same[^collision-chance]. In that case, as long as the
22/// new key is not the same as another existing one, internal invariants are not
23/// violated and the [`IdHashMap`] will continue to work correctly. (But don't
24/// rely on 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 the key is changed and `mem::forget` is then called on the
31/// `RefMut`, the [`IdHashMap`] will stop functioning correctly. This will not
32/// introduce memory safety issues, however.
33///
34/// The issues here are similar to using interior mutability (e.g. `RefCell` or
35/// `Mutex`) to mutate keys in a regular `HashMap`.
36///
37/// [`mem::forget`]: std::mem::forget
38///
39/// [^collision-chance]: The output of `Hash` is a [`u64`], so the probability
40/// of an individual hash colliding by chance is 1/2⁶⁴. Due to the [birthday
41/// problem], the probability of a collision by chance reaches 10⁻⁶ within
42/// around 6 × 10⁶ elements.
43///
44/// [`IdHashMap`]: crate::IdHashMap
45/// [birthday problem]: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table
46pub struct RefMut<
47    'a,
48    T: IdHashItem,
49    S: Clone + BuildHasher = DefaultHashBuilder,
50> {
51    inner: Option<RefMutInner<'a, T, S>>,
52}
53
54impl<'a, T: IdHashItem, S: Clone + BuildHasher> RefMut<'a, T, S> {
55    pub(super) fn new(state: S, hash: MapHash, borrowed: &'a mut T) -> Self {
56        Self { inner: Some(RefMutInner { state, hash, borrowed }) }
57    }
58
59    /// Borrows self into a shorter-lived `RefMut`.
60    ///
61    /// This `RefMut` will also check hash equality on drop.
62    pub fn reborrow(&mut self) -> RefMut<'_, T, S> {
63        let inner = self.inner.as_mut().unwrap();
64        let borrowed = &mut *inner.borrowed;
65        RefMut::new(inner.state.clone(), inner.hash.clone(), borrowed)
66    }
67
68    /// Converts this `RefMut` into a `&'a T`.
69    pub fn into_ref(mut self) -> &'a T {
70        let inner = self.inner.take().unwrap();
71        inner.into_ref()
72    }
73}
74
75impl<T: IdHashItem, S: Clone + BuildHasher> Drop for RefMut<'_, T, S> {
76    fn drop(&mut self) {
77        if let Some(inner) = self.inner.take() {
78            inner.into_ref();
79        }
80    }
81}
82
83impl<T: IdHashItem, S: Clone + BuildHasher> Deref for RefMut<'_, T, S> {
84    type Target = T;
85
86    fn deref(&self) -> &Self::Target {
87        self.inner.as_ref().unwrap().borrowed
88    }
89}
90
91impl<T: IdHashItem, S: Clone + BuildHasher> DerefMut for RefMut<'_, T, S> {
92    fn deref_mut(&mut self) -> &mut Self::Target {
93        self.inner.as_mut().unwrap().borrowed
94    }
95}
96
97impl<T: IdHashItem + fmt::Debug, S: Clone + BuildHasher> fmt::Debug
98    for RefMut<'_, T, S>
99{
100    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
101        match self.inner {
102            Some(ref inner) => inner.fmt(f),
103            None => {
104                f.debug_struct("RefMut").field("borrowed", &"missing").finish()
105            }
106        }
107    }
108}
109
110struct RefMutInner<'a, T: IdHashItem, S> {
111    state: S,
112    hash: MapHash,
113    borrowed: &'a mut T,
114}
115
116impl<'a, T: IdHashItem, S: BuildHasher> RefMutInner<'a, T, S> {
117    fn into_ref(self) -> &'a T {
118        if !self.hash.is_same_hash(&self.state, self.borrowed.key()) {
119            panic!("key changed during RefMut borrow");
120        }
121
122        self.borrowed
123    }
124}
125
126impl<T: IdHashItem + fmt::Debug, S> fmt::Debug for RefMutInner<'_, T, S> {
127    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
128        self.borrowed.fmt(f)
129    }
130}
iddqd/id_hash_map/ref_mut.rs

iddqd/id_hash_map/
ref_mut.rs
