mz_ore/collections/
hash.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License in the LICENSE file at the
6// root of this repository, or online at
7//
8//     http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16//! Stable wrappers around the stdlib `Hash` collections.
17//!
18//! The stdlib `Hash` collections (i.e., [`std::collections::HashMap`] and
19//! [`std::collections::HashSet`]) don't guarantee a stable iteration order. That is, the order in
20//! which elements are returned by methods like `iter` or `keys`, or in which elements are visited
21//! by methods like `retain`, is undefined and can differ between program executions. This property
22//! leads to non-determinism, which in turn can be the cause of bugs in logic that relies on
23//! deterministic execution.
24//!
25//! Since bugs caused by unstable iteration order are hard to spot, and it is not always easy to
26//! determine which parts of our code require determinism, we resort to banning the use of the
27//! stdlib `Hash` collections in general. Alternatives are available:
28//!
29//!  1. In most cases, you can simply switch to using the equivalent `BTree` collection type (i.e.,
30//!     [`std::collections::BTreeMap`] or [`std::collections::BTreeSet`]) as a drop-in replacement.
31//!     The `BTree` collections guarantee a stable iteration order, based on the `Ord` relation.
32//!  2. If the types you want to store don't (and shouldn't) implement `Ord`, or if profiling
33//!     reveals that the `BTree` collections are not suitable, use the wrappers provided in this
34//!     module instead.
35//!
36//! The `Hash` collection wrappers provided in this module only re-export methods that don't expose
37//! iteration order, and are therefore safe to use in code that relies on determinism.
38//!
39//! There are cases where the above mentioned alternatives are not sufficient, for example, if a
40//! third-party API requires you to pass a `HashMap` value. In this case, you can disable the
41//! clippy lint for the affected piece of code. Note that the onus is on you then to verify that
42//! doing so is sound and does not introduce bugs.
43
44// Allow the use of `HashMap` and `HashSet`, so we can define wrappers.
45#![allow(clippy::disallowed_types)]
46
47use std::borrow::Borrow;
48use std::collections::hash_map::Entry;
49use std::collections::{HashMap as StdMap, HashSet as StdSet, TryReserveError};
50use std::hash::Hash;
51use std::ops::{BitAnd, BitOr, BitXor, Index, Sub};
52
53/// A wrapper around [`std::collections::HashMap`] that hides methods that expose unstable
54/// iteration order.
55///
56/// See the module documentation for a rationale.
57#[derive(Clone, Debug, Default)]
58#[repr(transparent)]
59pub struct HashMap<K, V>(StdMap<K, V>);
60
61impl<K, V> HashMap<K, V> {
62    /// See [`std::collections::HashMap::new`].
63    #[inline]
64    #[must_use]
65    pub fn new() -> Self {
66        Self(StdMap::new())
67    }
68
69    /// See [`std::collections::HashMap::with_capacity`].
70    #[inline]
71    #[must_use]
72    pub fn with_capacity(capacity: usize) -> Self {
73        Self(StdMap::with_capacity(capacity))
74    }
75
76    /// See [`std::collections::HashMap::capacity`].
77    #[inline]
78    pub fn capacity(&self) -> usize {
79        self.0.capacity()
80    }
81
82    /// See [`std::collections::HashMap::len`].
83    #[inline]
84    pub fn len(&self) -> usize {
85        self.0.len()
86    }
87
88    /// See [`std::collections::HashMap::is_empty`].
89    #[inline]
90    pub fn is_empty(&self) -> bool {
91        self.0.is_empty()
92    }
93
94    /// See [`std::collections::HashMap::clear`].
95    #[inline]
96    pub fn clear(&mut self) {
97        self.0.clear();
98    }
99}
100
101impl<K, V> HashMap<K, V>
102where
103    K: Eq + Hash,
104{
105    /// See [`std::collections::HashMap::reserve`].
106    #[inline]
107    pub fn reserve(&mut self, additional: usize) {
108        self.0.reserve(additional);
109    }
110
111    /// See [`std::collections::HashMap::try_reserve`].
112    #[inline]
113    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
114        self.0.try_reserve(additional)
115    }
116
117    /// See [`std::collections::HashMap::shrink_to_fit`].
118    #[inline]
119    pub fn shrink_to_fit(&mut self) {
120        self.0.shrink_to_fit();
121    }
122
123    /// See [`std::collections::HashMap::shrink_to`].
124    #[inline]
125    pub fn shrink_to(&mut self, min_capacity: usize) {
126        self.0.shrink_to(min_capacity);
127    }
128
129    /// See [`std::collections::HashMap::entry`].
130    #[inline]
131    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
132        self.0.entry(key)
133    }
134
135    /// See [`std::collections::HashMap::get`].
136    #[inline]
137    pub fn get<Q>(&self, k: &Q) -> Option<&V>
138    where
139        K: Borrow<Q>,
140        Q: Hash + Eq + ?Sized,
141    {
142        self.0.get(k)
143    }
144
145    /// See [`std::collections::HashMap::get_key_value`].
146    #[inline]
147    pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
148    where
149        K: Borrow<Q>,
150        Q: Hash + Eq + ?Sized,
151    {
152        self.0.get_key_value(k)
153    }
154
155    /// See [`std::collections::HashMap::contains_key`].
156    #[inline]
157    pub fn contains_key<Q>(&self, k: &Q) -> bool
158    where
159        K: Borrow<Q>,
160        Q: Hash + Eq + ?Sized,
161    {
162        self.0.contains_key(k)
163    }
164
165    /// See [`std::collections::HashMap::get_mut`].
166    #[inline]
167    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
168    where
169        K: Borrow<Q>,
170        Q: Hash + Eq + ?Sized,
171    {
172        self.0.get_mut(k)
173    }
174
175    /// See [`std::collections::HashMap::insert`].
176    #[inline]
177    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
178        self.0.insert(k, v)
179    }
180
181    /// See [`std::collections::HashMap::remove`].
182    #[inline]
183    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
184    where
185        K: Borrow<Q>,
186        Q: Hash + Eq + ?Sized,
187    {
188        self.0.remove(k)
189    }
190
191    /// See [`std::collections::HashMap::remove_entry`].
192    #[inline]
193    pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
194    where
195        K: Borrow<Q>,
196        Q: Hash + Eq + ?Sized,
197    {
198        self.0.remove_entry(k)
199    }
200}
201
202impl<K, V> PartialEq for HashMap<K, V>
203where
204    K: Eq + Hash,
205    V: PartialEq,
206{
207    fn eq(&self, other: &Self) -> bool {
208        self.0.eq(&other.0)
209    }
210}
211
212impl<K, V> Eq for HashMap<K, V>
213where
214    K: Eq + Hash,
215    V: Eq,
216{
217}
218
219impl<K, Q: ?Sized, V> Index<&Q> for HashMap<K, V>
220where
221    K: Eq + Hash + Borrow<Q>,
222    Q: Eq + Hash,
223{
224    type Output = V;
225
226    #[inline]
227    fn index(&self, key: &Q) -> &V {
228        self.0.index(key)
229    }
230}
231
232impl<K, V> FromIterator<(K, V)> for HashMap<K, V>
233where
234    K: Eq + Hash,
235{
236    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
237        Self(StdMap::from_iter(iter))
238    }
239}
240
241impl<K, V> From<StdMap<K, V>> for HashMap<K, V>
242where
243    K: Eq + Hash,
244{
245    fn from(map: StdMap<K, V>) -> Self {
246        Self(map)
247    }
248}
249
250impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V>
251where
252    K: Eq + Hash,
253{
254    fn from(arr: [(K, V); N]) -> Self {
255        Self(StdMap::from(arr))
256    }
257}
258
259impl<K, V> Extend<(K, V)> for HashMap<K, V>
260where
261    K: Eq + Hash,
262{
263    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
264        self.0.extend(iter);
265    }
266}
267
268impl<'a, K, V> Extend<(&'a K, &'a V)> for HashMap<K, V>
269where
270    K: Eq + Hash + Copy,
271    V: Copy,
272{
273    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
274        self.0.extend(iter);
275    }
276}
277
278/// A wrapper around [`std::collections::HashSet`] that hides methods that expose unstable
279/// iteration order.
280///
281/// See the module documentation for a rationale.
282#[derive(Clone, Debug, Default)]
283#[repr(transparent)]
284pub struct HashSet<T>(StdSet<T>);
285
286impl<T> HashSet<T> {
287    /// See [`std::collections::HashSet::new`].
288    #[inline]
289    #[must_use]
290    pub fn new() -> Self {
291        Self(StdSet::new())
292    }
293
294    /// See [`std::collections::HashSet::with_capacity`].
295    #[inline]
296    #[must_use]
297    pub fn with_capacity(capacity: usize) -> Self {
298        Self(StdSet::with_capacity(capacity))
299    }
300
301    /// See [`std::collections::HashSet::capacity`].
302    #[inline]
303    pub fn capacity(&self) -> usize {
304        self.0.capacity()
305    }
306
307    /// See [`std::collections::HashSet::len`].
308    #[inline]
309    pub fn len(&self) -> usize {
310        self.0.len()
311    }
312
313    /// See [`std::collections::HashSet::is_empty`].
314    #[inline]
315    pub fn is_empty(&self) -> bool {
316        self.0.is_empty()
317    }
318
319    /// See [`std::collections::HashSet::clear`].
320    #[inline]
321    pub fn clear(&mut self) {
322        self.0.clear();
323    }
324}
325
326impl<T> HashSet<T>
327where
328    T: Eq + Hash,
329{
330    /// See [`std::collections::HashSet::reserve`].
331    #[inline]
332    pub fn reserve(&mut self, additional: usize) {
333        self.0.reserve(additional);
334    }
335
336    /// See [`std::collections::HashSet::try_reserve`].
337    #[inline]
338    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
339        self.0.try_reserve(additional)
340    }
341
342    /// See [`std::collections::HashSet::shrink_to_fit`].
343    #[inline]
344    pub fn shrink_to_fit(&mut self) {
345        self.0.shrink_to_fit();
346    }
347
348    /// See [`std::collections::HashSet::shrink_to`].
349    #[inline]
350    pub fn shrink_to(&mut self, min_capacity: usize) {
351        self.0.shrink_to(min_capacity);
352    }
353
354    /// See [`std::collections::HashSet::contains`].
355    #[inline]
356    pub fn contains<Q>(&self, value: &Q) -> bool
357    where
358        T: Borrow<Q>,
359        Q: Hash + Eq + ?Sized,
360    {
361        self.0.contains(value)
362    }
363
364    /// See [`std::collections::HashSet::get`].
365    #[inline]
366    pub fn get<Q>(&self, value: &Q) -> Option<&T>
367    where
368        T: Borrow<Q>,
369        Q: Hash + Eq + ?Sized,
370    {
371        self.0.get(value)
372    }
373
374    /// See [`std::collections::HashSet::is_disjoint`].
375    #[inline]
376    pub fn is_disjoint(&self, other: &Self) -> bool {
377        self.0.is_disjoint(&other.0)
378    }
379
380    /// See [`std::collections::HashSet::is_subset`].
381    #[inline]
382    pub fn is_subset(&self, other: &Self) -> bool {
383        self.0.is_subset(&other.0)
384    }
385
386    /// See [`std::collections::HashSet::is_superset`].
387    #[inline]
388    pub fn is_superset(&self, other: &Self) -> bool {
389        self.0.is_superset(&other.0)
390    }
391
392    /// See [`std::collections::HashSet::insert`].
393    #[inline]
394    pub fn insert(&mut self, value: T) -> bool {
395        self.0.insert(value)
396    }
397
398    /// See [`std::collections::HashSet::replace`].
399    #[inline]
400    pub fn replace(&mut self, value: T) -> Option<T> {
401        self.0.replace(value)
402    }
403
404    /// See [`std::collections::HashSet::remove`].
405    #[inline]
406    pub fn remove<Q>(&mut self, value: &Q) -> bool
407    where
408        T: Borrow<Q>,
409        Q: Hash + Eq + ?Sized,
410    {
411        self.0.remove(value)
412    }
413
414    /// See [`std::collections::HashSet::take`].
415    #[inline]
416    pub fn take<Q>(&mut self, value: &Q) -> Option<T>
417    where
418        T: Borrow<Q>,
419        Q: Hash + Eq + ?Sized,
420    {
421        self.0.take(value)
422    }
423}
424
425impl<T> PartialEq for HashSet<T>
426where
427    T: Eq + Hash,
428{
429    fn eq(&self, other: &Self) -> bool {
430        self.0.eq(&other.0)
431    }
432}
433
434impl<T> Eq for HashSet<T> where T: Eq + Hash {}
435
436impl<T> FromIterator<T> for HashSet<T>
437where
438    T: Eq + Hash,
439{
440    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> HashSet<T> {
441        Self(StdSet::from_iter(iter))
442    }
443}
444
445impl<T> From<StdSet<T>> for HashSet<T>
446where
447    T: Eq + Hash,
448{
449    fn from(set: StdSet<T>) -> Self {
450        Self(set)
451    }
452}
453
454impl<T, const N: usize> From<[T; N]> for HashSet<T>
455where
456    T: Eq + Hash,
457{
458    fn from(arr: [T; N]) -> Self {
459        Self(StdSet::from(arr))
460    }
461}
462
463impl<T> Extend<T> for HashSet<T>
464where
465    T: Eq + Hash,
466{
467    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
468        self.0.extend(iter);
469    }
470}
471
472impl<'a, T> Extend<&'a T> for HashSet<T>
473where
474    T: 'a + Eq + Hash + Copy,
475{
476    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
477        self.0.extend(iter);
478    }
479}
480
481impl<T> BitOr<&HashSet<T>> for &HashSet<T>
482where
483    T: Eq + Hash + Clone,
484{
485    type Output = HashSet<T>;
486
487    fn bitor(self, rhs: &HashSet<T>) -> HashSet<T> {
488        HashSet(self.0.bitor(&rhs.0))
489    }
490}
491
492impl<T> BitAnd<&HashSet<T>> for &HashSet<T>
493where
494    T: Eq + Hash + Clone,
495{
496    type Output = HashSet<T>;
497
498    fn bitand(self, rhs: &HashSet<T>) -> HashSet<T> {
499        HashSet(self.0.bitand(&rhs.0))
500    }
501}
502
503impl<T> BitXor<&HashSet<T>> for &HashSet<T>
504where
505    T: Eq + Hash + Clone,
506{
507    type Output = HashSet<T>;
508
509    fn bitxor(self, rhs: &HashSet<T>) -> HashSet<T> {
510        HashSet(self.0.bitxor(&rhs.0))
511    }
512}
513
514impl<T> Sub<&HashSet<T>> for &HashSet<T>
515where
516    T: Eq + Hash + Clone,
517{
518    type Output = HashSet<T>;
519
520    fn sub(self, rhs: &HashSet<T>) -> HashSet<T> {
521        HashSet(self.0.sub(&rhs.0))
522    }
523}
mz_ore/collections/hash.rs

mz_ore/collections/
hash.rs
