iddqd/id_ord_map/
ref_mut.rs

1use super::IdOrdItem;
2use crate::support::map_hash::MapHash;
3use core::{
4    fmt,
5    ops::{Deref, DerefMut},
6};
7
8/// A mutable reference to an [`IdOrdMap`] entry.
9///
10/// This is a wrapper around a `&mut T` that panics when dropped, if the
11/// borrowed value's key has 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, and as part of that, [`IdOrdItem::Key`] requires
17/// that the key type implement [`Hash`].
18///
19/// `RefMut` stores the `Hash` output of keys at creation time, and recomputes
20/// these hashes when it is dropped or when [`Self::into_ref`] is called. If a
21/// key changes, there's a small but non-negligible chance that its hash value
22/// stays the same[^collision-chance]. In that case, the map will no longer
23/// function correctly and might panic on access. This will not introduce memory
24/// safety issues, however.
25///
26/// It is also possible to deliberately write pathological `Hash`
27/// implementations that collide more often. (Don't do this.)
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`, the [`IdOrdMap`] will no longer function correctly and might panic
32/// on access. This will not 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/// [`Hash`]: core::hash::Hash
45/// [`IdOrdMap`]: crate::IdOrdMap
46/// [birthday problem]: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table
47pub struct RefMut<'a, T: IdOrdItem> {
48    inner: Option<RefMutInner<'a, T>>,
49}
50
51impl<'a, T: IdOrdItem> RefMut<'a, T> {
52    #[inline]
53    pub(super) fn new(
54        state: foldhash::fast::FixedState,
55        hash: MapHash,
56        borrowed: &'a mut T,
57    ) -> Self {
58        let inner = RefMutInner { state, hash, borrowed };
59        Self { inner: Some(inner) }
60    }
61
62    /// Converts this `RefMut` into a `&'a T`.
63    pub fn into_ref(mut self) -> &'a T {
64        let inner = self.inner.take().unwrap();
65        inner.into_ref()
66    }
67
68    /// Borrows self into a shorter-lived `RefMut`.
69    ///
70    /// This `RefMut` will also check hash equality on drop.
71    pub fn reborrow<'b>(&'b mut self) -> RefMut<'b, T> {
72        let inner = self.inner.as_mut().unwrap();
73        let borrowed = &mut *inner.borrowed;
74        RefMut::new(inner.state.clone(), inner.hash.clone(), borrowed)
75    }
76}
77
78impl<'a, T: IdOrdItem> Drop for RefMut<'a, T> {
79    #[inline]
80    fn drop(&mut self) {
81        if let Some(inner) = self.inner.take() {
82            inner.into_ref();
83        }
84    }
85}
86
87impl<'a, T: IdOrdItem> Deref for RefMut<'a, T> {
88    type Target = T;
89
90    fn deref(&self) -> &Self::Target {
91        self.inner.as_ref().unwrap().borrowed
92    }
93}
94
95impl<'a, T: IdOrdItem> DerefMut for RefMut<'a, T> {
96    fn deref_mut(&mut self) -> &mut Self::Target {
97        self.inner.as_mut().unwrap().borrowed
98    }
99}
100
101impl<'a, T: IdOrdItem + fmt::Debug> fmt::Debug for RefMut<'a, T> {
102    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103        match self.inner {
104            Some(ref inner) => inner.fmt(f),
105            None => {
106                f.debug_struct("RefMut").field("borrowed", &"missing").finish()
107            }
108        }
109    }
110}
111
112struct RefMutInner<'a, T: IdOrdItem> {
113    state: foldhash::fast::FixedState,
114    hash: MapHash,
115    borrowed: &'a mut T,
116}
117
118impl<'a, T: IdOrdItem> RefMutInner<'a, T> {
119    #[inline]
120    fn into_ref(self) -> &'a T {
121        let borrowed: &'a T = self.borrowed;
122        if !self.hash.is_same_hash(&self.state, borrowed.key()) {
123            panic!("key changed during RefMut borrow");
124        }
125
126        borrowed
127    }
128}
129
130impl<T: IdOrdItem + fmt::Debug> fmt::Debug for RefMutInner<'_, T> {
131    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132        self.borrowed.fmt(f)
133    }
134}
iddqd/id_ord_map/ref_mut.rs

iddqd/id_ord_map/
ref_mut.rs
