src/raw.rs - anymap blob - Chris Morgan’s Git repositories

   1 //! The raw form of a `Map`, allowing untyped access.
   2 //!
   3 //! All relevant details are in the `RawMap` struct.
   4
   5 use std::any::{Any, TypeId};
   6 use std::borrow::Borrow;
   7 use std::collections::hash_map::{self, HashMap};
   8 use std::convert::TryInto;
   9 use std::hash::Hash;
  10 use std::hash::{Hasher, BuildHasherDefault};
  11 #[cfg(test)]
  12 use std::mem;
  13 use std::ops::{Index, IndexMut};
  14
  15 use any::UncheckedAnyExt;
  16
  17 #[derive(Default)]
  18 struct TypeIdHasher {
  19     value: u64,
  20 }
  21
  22 impl Hasher for TypeIdHasher {
  23     #[inline]
  24     fn write(&mut self, bytes: &[u8]) {
  25         // This expects to receive exactly one 64-bit value, and there’s no realistic chance of
  26         // that changing, but I don’t want to depend on something that isn’t expressly part of the
  27         // contract for safety. But I’m OK with release builds putting everything in one bucket
  28         // if it *did* change (and debug builds panicking).
  29         debug_assert_eq!(bytes.len(), 8);
  30         let _ = bytes.try_into()
  31             .map(|array| self.value = u64::from_ne_bytes(array));
  32     }
  33
  34     #[inline]
  35     fn finish(&self) -> u64 { self.value }
  36 }
  37
  38 #[test]
  39 fn type_id_hasher() {
  40     fn verify_hashing_with(type_id: TypeId) {
  41         let mut hasher = TypeIdHasher::default();
  42         type_id.hash(&mut hasher);
  43         // SAFETY: u64 is valid for all bit patterns.
  44         assert_eq!(hasher.finish(), unsafe { mem::transmute::<TypeId, u64>(type_id) });
  45     }
  46     // Pick a variety of types, just to demonstrate it’s all sane. Normal, zero-sized, unsized, &c.
  47     verify_hashing_with(TypeId::of::<usize>());
  48     verify_hashing_with(TypeId::of::<()>());
  49     verify_hashing_with(TypeId::of::<str>());
  50     verify_hashing_with(TypeId::of::<&str>());
  51     verify_hashing_with(TypeId::of::<Vec<u8>>());
  52 }
  53
  54 /// The raw, underlying form of a `Map`.
  55 ///
  56 /// At its essence, this is a wrapper around `HashMap<TypeId, Box<Any>>`, with the portions that
  57 /// would be memory-unsafe removed or marked unsafe. Normal people are expected to use the safe
  58 /// `Map` interface instead, but there is the occasional use for this such as iteration over the
  59 /// contents of an `Map`. However, because you will then be dealing with `Any` trait objects, it
  60 /// doesn’t tend to be so very useful. Still, if you need it, it’s here.
  61 #[derive(Debug)]
  62 pub struct RawMap<A: ?Sized + UncheckedAnyExt = dyn Any> {
  63     inner: HashMap<TypeId, Box<A>, BuildHasherDefault<TypeIdHasher>>,
  64 }
  65
  66 // #[derive(Clone)] would want A to implement Clone, but in reality it’s only Box<A> that can.
  67 impl<A: ?Sized + UncheckedAnyExt> Clone for RawMap<A> where Box<A>: Clone {
  68     #[inline]
  69     fn clone(&self) -> RawMap<A> {
  70         RawMap {
  71             inner: self.inner.clone(),
  72         }
  73     }
  74 }
  75
  76 impl_common_methods! {
  77     field: RawMap.inner;
  78     new() => HashMap::with_hasher(Default::default());
  79     with_capacity(capacity) => HashMap::with_capacity_and_hasher(capacity, Default::default());
  80 }
  81
  82 /// `RawMap` iterator.
  83 #[derive(Clone)]
  84 pub struct Iter<'a, A: ?Sized + UncheckedAnyExt> {
  85     inner: hash_map::Iter<'a, TypeId, Box<A>>,
  86 }
  87 impl<'a, A: ?Sized + UncheckedAnyExt> Iterator for Iter<'a, A> {
  88     type Item = &'a A;
  89     #[inline] fn next(&mut self) -> Option<&'a A> { self.inner.next().map(|x| &**x.1) }
  90     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
  91 }
  92 impl<'a, A: ?Sized + UncheckedAnyExt> ExactSizeIterator for Iter<'a, A> {
  93     #[inline] fn len(&self) -> usize { self.inner.len() }
  94 }
  95
  96 /// `RawMap` mutable iterator.
  97 pub struct IterMut<'a, A: ?Sized + UncheckedAnyExt> {
  98     inner: hash_map::IterMut<'a, TypeId, Box<A>>,
  99 }
 100 impl<'a, A: ?Sized + UncheckedAnyExt> Iterator for IterMut<'a, A> {
 101     type Item = &'a mut A;
 102     #[inline] fn next(&mut self) -> Option<&'a mut A> { self.inner.next().map(|x| &mut **x.1) }
 103     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
 104 }
 105 impl<'a, A: ?Sized + UncheckedAnyExt> ExactSizeIterator for IterMut<'a, A> {
 106     #[inline] fn len(&self) -> usize { self.inner.len() }
 107 }
 108
 109 /// `RawMap` move iterator.
 110 pub struct IntoIter<A: ?Sized + UncheckedAnyExt> {
 111     inner: hash_map::IntoIter<TypeId, Box<A>>,
 112 }
 113 impl<A: ?Sized + UncheckedAnyExt> Iterator for IntoIter<A> {
 114     type Item = Box<A>;
 115     #[inline] fn next(&mut self) -> Option<Box<A>> { self.inner.next().map(|x| x.1) }
 116     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
 117 }
 118 impl<A: ?Sized + UncheckedAnyExt> ExactSizeIterator for IntoIter<A> {
 119     #[inline] fn len(&self) -> usize { self.inner.len() }
 120 }
 121
 122 /// `RawMap` drain iterator.
 123 pub struct Drain<'a, A: ?Sized + UncheckedAnyExt> {
 124     inner: hash_map::Drain<'a, TypeId, Box<A>>,
 125 }
 126 impl<'a, A: ?Sized + UncheckedAnyExt> Iterator for Drain<'a, A> {
 127     type Item = Box<A>;
 128     #[inline] fn next(&mut self) -> Option<Box<A>> { self.inner.next().map(|x| x.1) }
 129     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
 130 }
 131 impl<'a, A: ?Sized + UncheckedAnyExt> ExactSizeIterator for Drain<'a, A> {
 132     #[inline] fn len(&self) -> usize { self.inner.len() }
 133 }
 134
 135 impl<A: ?Sized + UncheckedAnyExt> RawMap<A> {
 136     /// An iterator visiting all entries in arbitrary order.
 137     ///
 138     /// Iterator element type is `&Any`.
 139     #[inline]
 140     pub fn iter(&self) -> Iter<A> {
 141         Iter {
 142             inner: self.inner.iter(),
 143         }
 144     }
 145
 146     /// An iterator visiting all entries in arbitrary order.
 147     ///
 148     /// Iterator element type is `&mut Any`.
 149     #[inline]
 150     pub fn iter_mut(&mut self) -> IterMut<A> {
 151         IterMut {
 152             inner: self.inner.iter_mut(),
 153         }
 154     }
 155
 156     /// Clears the map, returning all items as an iterator.
 157     ///
 158     /// Iterator element type is `Box<Any>`.
 159     ///
 160     /// Keeps the allocated memory for reuse.
 161     #[inline]
 162     pub fn drain(&mut self) -> Drain<A> {
 163         Drain {
 164             inner: self.inner.drain(),
 165         }
 166     }
 167
 168     /// Gets the entry for the given type in the collection for in-place manipulation.
 169     #[inline]
 170     pub fn entry(&mut self, key: TypeId) -> Entry<A> {
 171         match self.inner.entry(key) {
 172             hash_map::Entry::Occupied(e) => Entry::Occupied(OccupiedEntry {
 173                 inner: e,
 174             }),
 175             hash_map::Entry::Vacant(e) => Entry::Vacant(VacantEntry {
 176                 inner: e,
 177             }),
 178         }
 179     }
 180
 181     /// Returns a reference to the value corresponding to the key.
 182     ///
 183     /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
 184     /// form *must* match those for the key type.
 185     #[inline]
 186     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&A>
 187     where TypeId: Borrow<Q>, Q: Hash + Eq {
 188         self.inner.get(k).map(|x| &**x)
 189     }
 190
 191     /// Returns true if the map contains a value for the specified key.
 192     ///
 193     /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
 194     /// form *must* match those for the key type.
 195     #[inline]
 196     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
 197     where TypeId: Borrow<Q>, Q: Hash + Eq {
 198         self.inner.contains_key(k)
 199     }
 200
 201     /// Returns a mutable reference to the value corresponding to the key.
 202     ///
 203     /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
 204     /// form *must* match those for the key type.
 205     #[inline]
 206     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut A>
 207     where TypeId: Borrow<Q>, Q: Hash + Eq {
 208         self.inner.get_mut(k).map(|x| &mut **x)
 209     }
 210
 211     /// Inserts a key-value pair from the map. If the key already had a value present in the map,
 212     /// that value is returned. Otherwise, `None` is returned.
 213     ///
 214     /// # Safety
 215     ///
 216     /// `key` and the type ID of `value` must match, or *undefined behaviour* occurs.
 217     #[inline]
 218     pub unsafe fn insert(&mut self, key: TypeId, value: Box<A>) -> Option<Box<A>> {
 219         self.inner.insert(key, value)
 220     }
 221
 222     /// Removes a key from the map, returning the value at the key if the key was previously in the
 223     /// map.
 224     ///
 225     /// The key may be any borrowed form of the map's key type, but `Hash` and `Eq` on the borrowed
 226     /// form *must* match those for the key type.
 227     #[inline]
 228     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<Box<A>>
 229     where TypeId: Borrow<Q>, Q: Hash + Eq {
 230         self.inner.remove(k)
 231     }
 232
 233 }
 234
 235 impl<A: ?Sized + UncheckedAnyExt, Q> Index<Q> for RawMap<A> where TypeId: Borrow<Q>, Q: Eq + Hash {
 236     type Output = A;
 237
 238     #[inline]
 239     fn index(&self, index: Q) -> &A {
 240         self.get(&index).expect("no entry found for key")
 241     }
 242 }
 243
 244 impl<A: ?Sized + UncheckedAnyExt, Q> IndexMut<Q> for RawMap<A> where TypeId: Borrow<Q>, Q: Eq + Hash {
 245     #[inline]
 246     fn index_mut(&mut self, index: Q) -> &mut A {
 247         self.get_mut(&index).expect("no entry found for key")
 248     }
 249 }
 250
 251 impl<A: ?Sized + UncheckedAnyExt> IntoIterator for RawMap<A> {
 252     type Item = Box<A>;
 253     type IntoIter = IntoIter<A>;
 254
 255     #[inline]
 256     fn into_iter(self) -> IntoIter<A> {
 257         IntoIter {
 258             inner: self.inner.into_iter(),
 259         }
 260     }
 261 }
 262
 263 /// A view into a single occupied location in a `RawMap`.
 264 pub struct OccupiedEntry<'a, A: ?Sized + UncheckedAnyExt> {
 265     inner: hash_map::OccupiedEntry<'a, TypeId, Box<A>>,
 266 }
 267
 268 /// A view into a single empty location in a `RawMap`.
 269 pub struct VacantEntry<'a, A: ?Sized + UncheckedAnyExt> {
 270     inner: hash_map::VacantEntry<'a, TypeId, Box<A>>,
 271 }
 272
 273 /// A view into a single location in a `RawMap`, which may be vacant or occupied.
 274 pub enum Entry<'a, A: ?Sized + UncheckedAnyExt> {
 275     /// An occupied Entry
 276     Occupied(OccupiedEntry<'a, A>),
 277     /// A vacant Entry
 278     Vacant(VacantEntry<'a, A>),
 279 }
 280
 281 impl<'a, A: ?Sized + UncheckedAnyExt> Entry<'a, A> {
 282     /// Ensures a value is in the entry by inserting the default if empty, and returns
 283     /// a mutable reference to the value in the entry.
 284     ///
 285     /// # Safety
 286     ///
 287     /// The type ID of `default` must match the entry’s key, or *undefined behaviour* occurs.
 288     #[inline]
 289     pub unsafe fn or_insert(self, default: Box<A>) -> &'a mut A {
 290         match self {
 291             Entry::Occupied(inner) => inner.into_mut(),
 292             Entry::Vacant(inner) => inner.insert(default),
 293         }
 294     }
 295
 296     /// Ensures a value is in the entry by inserting the result of the default function if empty,
 297     /// and returns a mutable reference to the value in the entry.
 298     ///
 299     /// # Safety
 300     ///
 301     /// The type ID of the value returned by `default` must match the entry’s key,
 302     /// or *undefined behaviour* occurs.
 303     #[inline]
 304     pub unsafe fn or_insert_with<F: FnOnce() -> Box<A>>(self, default: F) -> &'a mut A {
 305         match self {
 306             Entry::Occupied(inner) => inner.into_mut(),
 307             Entry::Vacant(inner) => inner.insert(default()),
 308         }
 309     }
 310 }
 311
 312 impl<'a, A: ?Sized + UncheckedAnyExt> OccupiedEntry<'a, A> {
 313     /// Gets a reference to the value in the entry.
 314     #[inline]
 315     pub fn get(&self) -> &A {
 316         &**self.inner.get()
 317     }
 318
 319     /// Gets a mutable reference to the value in the entry.
 320     #[inline]
 321     pub fn get_mut(&mut self) -> &mut A {
 322         &mut **self.inner.get_mut()
 323     }
 324
 325     /// Converts the OccupiedEntry into a mutable reference to the value in the entry
 326     /// with a lifetime bound to the collection itself.
 327     #[inline]
 328     pub fn into_mut(self) -> &'a mut A {
 329         &mut **self.inner.into_mut()
 330     }
 331
 332     /// Sets the value of the entry, and returns the entry's old value.
 333     ///
 334     /// # Safety
 335     ///
 336     /// The type ID of `value` must match the entry’s key, or *undefined behaviour* occurs.
 337     #[inline]
 338     pub unsafe fn insert(&mut self, value: Box<A>) -> Box<A> {
 339         self.inner.insert(value)
 340     }
 341
 342     /// Takes the value out of the entry, and returns it.
 343     #[inline]
 344     pub fn remove(self) -> Box<A> {
 345         self.inner.remove()
 346     }
 347 }
 348
 349 impl<'a, A: ?Sized + UncheckedAnyExt> VacantEntry<'a, A> {
 350     /// Sets the value of the entry with the VacantEntry's key,
 351     /// and returns a mutable reference to it.
 352     ///
 353     /// # Safety
 354     ///
 355     /// The type ID of `value` must match the entry’s key, or *undefined behaviour* occurs.
 356     #[inline]
 357     pub unsafe fn insert(self, value: Box<A>) -> &'a mut A {
 358         &mut **self.inner.insert(value)
 359     }
 360 }