iddqd/id_ord_map/
ref_mut.rs

1use super::IdOrdItem;
2use crate::support::map_hash::MapHash;
3use core::{
4    fmt,
5    hash::Hash,
6    ops::{Deref, DerefMut},
7};
8
9/// A mutable reference to an [`IdOrdMap`] entry.
10///
11/// This is a wrapper around a `&mut T` that panics when dropped, if the
12/// borrowed value's key has changed since the wrapper was created.
13///
14/// # Change detection
15///
16/// It is illegal to change the keys of a borrowed `&mut T`. `RefMut` attempts
17/// to enforce this invariant, and as part of that, it requires that the key
18/// type implement [`Hash`].
19///
20/// `RefMut` stores the `Hash` output of keys at creation time, and recomputes
21/// these hashes when it is dropped or when [`Self::into_ref`] is called. If a
22/// key changes, there's a small but non-negligible chance that its hash value
23/// stays the same[^collision-chance]. In that case, the map will no longer
24/// function correctly and might panic on access. This will not introduce memory
25/// safety issues, however.
26///
27/// It is also possible to deliberately write pathological `Hash`
28/// implementations that collide more often. (Don't do this.)
29///
30/// Also, `RefMut`'s hash detection will not function if [`mem::forget`] is
31/// called on it. If a key is changed and `mem::forget` is then called on the
32/// `RefMut`, the [`IdOrdMap`] will no longer function correctly and might panic
33/// on access. This will not introduce memory safety issues, however.
34///
35/// The issues here are similar to using interior mutability (e.g. `RefCell` or
36/// `Mutex`) to mutate keys in a regular `HashMap`.
37///
38/// [`mem::forget`]: std::mem::forget
39///
40/// [^collision-chance]: The output of `Hash` is a [`u64`], so the probability
41/// of an individual hash colliding by chance is 1/2⁶⁴. Due to the [birthday
42/// problem], the probability of a collision by chance reaches 10⁻⁶ within
43/// around 6 × 10⁶ elements.
44///
45/// [`IdOrdMap`]: crate::IdOrdMap
46/// [birthday problem]: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table
47pub struct RefMut<'a, T: IdOrdItem>
48where
49    T::Key<'a>: Hash,
50{
51    inner: Option<RefMutInner<'a, T>>,
52}
53
54impl<'a, T: IdOrdItem> RefMut<'a, T>
55where
56    T::Key<'a>: Hash,
57{
58    pub(super) fn new(
59        hash: MapHash<foldhash::fast::RandomState>,
60        borrowed: &'a mut T,
61    ) -> Self {
62        let inner = RefMutInner { hash, borrowed };
63        Self { inner: Some(inner) }
64    }
65
66    /// Converts this `RefMut` into a `&'a T`.
67    pub fn into_ref(mut self) -> &'a T {
68        let inner = self.inner.take().unwrap();
69        inner.into_ref()
70    }
71}
72
73impl<'a, T: IdOrdItem> RefMut<'a, T>
74where
75    for<'k> T::Key<'k>: Hash,
76{
77    /// Borrows self into a shorter-lived `RefMut`.
78    ///
79    /// This `RefMut` will also check hash equality on drop.
80    ///
81    /// Note: currently, due to limitations in the Rust borrow checker, this
82    /// effectively requires that `T: 'static`. Relaxing this requirement should
83    /// be possible in principle.
84    pub fn reborrow<'b>(&'b mut self) -> RefMut<'b, T> {
85        let inner = self.inner.as_mut().unwrap();
86        let borrowed = &mut *inner.borrowed;
87        RefMut::new(inner.hash.clone(), borrowed)
88    }
89}
90
91impl<'a, T: IdOrdItem> Drop for RefMut<'a, T>
92where
93    T::Key<'a>: Hash,
94{
95    fn drop(&mut self) {
96        if let Some(inner) = self.inner.take() {
97            inner.into_ref();
98        }
99    }
100}
101
102impl<'a, T: IdOrdItem> Deref for RefMut<'a, T>
103where
104    T::Key<'a>: Hash,
105{
106    type Target = T;
107
108    fn deref(&self) -> &Self::Target {
109        self.inner.as_ref().unwrap().borrowed
110    }
111}
112
113impl<'a, T: IdOrdItem> DerefMut for RefMut<'a, T>
114where
115    T::Key<'a>: Hash,
116{
117    fn deref_mut(&mut self) -> &mut Self::Target {
118        self.inner.as_mut().unwrap().borrowed
119    }
120}
121
122impl<'a, T: IdOrdItem + fmt::Debug> fmt::Debug for RefMut<'a, T>
123where
124    T::Key<'a>: Hash,
125{
126    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127        match self.inner {
128            Some(ref inner) => inner.fmt(f),
129            None => {
130                f.debug_struct("RefMut").field("borrowed", &"missing").finish()
131            }
132        }
133    }
134}
135
136struct RefMutInner<'a, T: IdOrdItem> {
137    hash: MapHash<foldhash::fast::RandomState>,
138    borrowed: &'a mut T,
139}
140
141impl<'a, T: IdOrdItem> RefMutInner<'a, T>
142where
143    T::Key<'a>: Hash,
144{
145    fn into_ref(self) -> &'a T {
146        let key: T::Key<'_> = self.borrowed.key();
147        // SAFETY: The key is borrowed, then dropped immediately. T is valid for
148        // 'a so T::Key is valid for 'a.
149        let key: T::Key<'a> =
150            unsafe { std::mem::transmute::<T::Key<'_>, T::Key<'a>>(key) };
151        if !self.hash.is_same_hash(&key) {
152            panic!("key changed during RefMut borrow");
153        }
154
155        self.borrowed
156    }
157}
158
159impl<T: IdOrdItem + fmt::Debug> fmt::Debug for RefMutInner<'_, T> {
160    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
161        self.borrowed.fmt(f)
162    }
163}
iddqd/id_ord_map/ref_mut.rs

iddqd/id_ord_map/
ref_mut.rs
