iddqd/bi_hash_map/
ref_mut.rs

1use crate::{BiHashItem, DefaultHashBuilder, support::map_hash::MapHash};
2use core::{
3    fmt,
4    hash::BuildHasher,
5    ops::{Deref, DerefMut},
6};
7
8/// A mutable reference to a [`BiHashMap`] 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 [`BiHashMap`] will continue to work correctly. (But don't do this!)
24///
25/// It is also possible to deliberately write pathological `Hash`
26/// implementations that collide more often. (Don't do this either.)
27///
28/// Also, `RefMut`'s hash detection will not function if [`mem::forget`] is
29/// called on it. If a key is changed and `mem::forget` is then called on the
30/// `RefMut`, the `BiHashMap` will stop functioning correctly. This will not
31/// introduce memory safety issues, however.
32///
33/// The issues here are similar to using interior mutability (e.g. `RefCell` or
34/// `Mutex`) to mutate keys in a regular `HashMap`.
35///
36/// [`mem::forget`]: std::mem::forget
37///
38/// [^collision-chance]: The output of `Hash` is a [`u64`], so the probability
39/// of an individual hash colliding by chance is 1/2⁶⁴. Due to the [birthday
40/// problem], the probability of a collision by chance reaches 10⁻⁶ within
41/// around 6 × 10⁶ elements.
42///
43/// [`BiHashMap`]: crate::BiHashMap
44/// [birthday problem]: https://en.wikipedia.org/wiki/Birthday_problem#Probability_table
45pub struct RefMut<
46    'a,
47    T: BiHashItem,
48    S: Clone + BuildHasher = DefaultHashBuilder,
49> {
50    inner: Option<RefMutInner<'a, T, S>>,
51}
52
53impl<'a, T: BiHashItem, S: Clone + BuildHasher> RefMut<'a, T, S> {
54    pub(super) fn new(
55        state: S,
56        hashes: [MapHash; 2],
57        borrowed: &'a mut T,
58    ) -> Self {
59        Self { inner: Some(RefMutInner { state, hashes, borrowed }) }
60    }
61
62    /// Borrows self into a shorter-lived `RefMut`.
63    ///
64    /// This `RefMut` will also check hash equality on drop.
65    pub fn reborrow(&mut self) -> RefMut<'_, T, S> {
66        let inner = self.inner.as_mut().unwrap();
67        let borrowed = &mut *inner.borrowed;
68        RefMut::new(inner.state.clone(), inner.hashes.clone(), borrowed)
69    }
70
71    /// Converts this `RefMut` into a `&'a T`.
72    pub fn into_ref(mut self) -> &'a T {
73        let inner = self.inner.take().unwrap();
74        inner.into_ref()
75    }
76}
77
78impl<T: BiHashItem, S: Clone + BuildHasher> Drop for RefMut<'_, T, S> {
79    fn drop(&mut self) {
80        if let Some(inner) = self.inner.take() {
81            inner.into_ref();
82        }
83    }
84}
85
86impl<T: BiHashItem, S: Clone + BuildHasher> Deref for RefMut<'_, T, S> {
87    type Target = T;
88
89    fn deref(&self) -> &Self::Target {
90        self.inner.as_ref().unwrap().borrowed
91    }
92}
93
94impl<T: BiHashItem, S: Clone + BuildHasher> DerefMut for RefMut<'_, T, S> {
95    fn deref_mut(&mut self) -> &mut Self::Target {
96        self.inner.as_mut().unwrap().borrowed
97    }
98}
99
100impl<T: BiHashItem + fmt::Debug, S: Clone + BuildHasher> fmt::Debug
101    for RefMut<'_, T, S>
102{
103    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
104        match self.inner {
105            Some(ref inner) => inner.fmt(f),
106            None => {
107                f.debug_struct("RefMut").field("borrowed", &"missing").finish()
108            }
109        }
110    }
111}
112
113struct RefMutInner<'a, T: BiHashItem, S> {
114    state: S,
115    hashes: [MapHash; 2],
116    borrowed: &'a mut T,
117}
118
119impl<'a, T: BiHashItem, S: BuildHasher> RefMutInner<'a, T, S> {
120    fn into_ref(self) -> &'a T {
121        if !self.hashes[0].is_same_hash(&self.state, self.borrowed.key1()) {
122            panic!("key1 changed during RefMut borrow");
123        }
124        if !self.hashes[1].is_same_hash(&self.state, self.borrowed.key2()) {
125            panic!("key2 changed during RefMut borrow");
126        }
127
128        self.borrowed
129    }
130}
131
132impl<T: BiHashItem + fmt::Debug, S> fmt::Debug for RefMutInner<'_, T, S> {
133    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
134        self.borrowed.fmt(f)
135    }
136}
iddqd/bi_hash_map/ref_mut.rs

iddqd/bi_hash_map/
ref_mut.rs
