1 use std::borrow::Borrow; 2 use std::hash::Hash; 3 use std::ops::Index; 4 use std::slice; 5 6 pub use self::ordered::OrderedMap; 7 pub use self::unordered::UnorderedMap; 8 pub use std::collections::hash_map::Entry; 9 10 mod ordered { 11 use super::{Entry, Iter, UnorderedMap}; 12 use std::borrow::Borrow; 13 use std::hash::Hash; 14 use std::mem; 15 16 pub struct OrderedMap<K, V> { 17 map: UnorderedMap<K, usize>, 18 vec: Vec<(K, V)>, 19 } 20 21 impl<K, V> OrderedMap<K, V> { new() -> Self22 pub fn new() -> Self { 23 OrderedMap { 24 map: UnorderedMap::new(), 25 vec: Vec::new(), 26 } 27 } 28 iter(&self) -> Iter<K, V>29 pub fn iter(&self) -> Iter<K, V> { 30 Iter(self.vec.iter()) 31 } 32 keys(&self) -> impl Iterator<Item = &K>33 pub fn keys(&self) -> impl Iterator<Item = &K> { 34 self.vec.iter().map(|(k, _v)| k) 35 } 36 } 37 38 impl<K, V> OrderedMap<K, V> 39 where 40 K: Copy + Hash + Eq, 41 { insert(&mut self, key: K, value: V) -> Option<V>42 pub fn insert(&mut self, key: K, value: V) -> Option<V> { 43 match self.map.entry(key) { 44 Entry::Occupied(entry) => { 45 let i = &mut self.vec[*entry.get()]; 46 Some(mem::replace(&mut i.1, value)) 47 } 48 Entry::Vacant(entry) => { 49 entry.insert(self.vec.len()); 50 self.vec.push((key, value)); 51 None 52 } 53 } 54 } 55 contains_key<Q>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: ?Sized + Hash + Eq,56 pub fn contains_key<Q>(&self, key: &Q) -> bool 57 where 58 K: Borrow<Q>, 59 Q: ?Sized + Hash + Eq, 60 { 61 self.map.contains_key(key) 62 } 63 get<Q>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: ?Sized + Hash + Eq,64 pub fn get<Q>(&self, key: &Q) -> Option<&V> 65 where 66 K: Borrow<Q>, 67 Q: ?Sized + Hash + Eq, 68 { 69 let i = *self.map.get(key)?; 70 Some(&self.vec[i].1) 71 } 72 } 73 74 impl<'a, K, V> IntoIterator for &'a OrderedMap<K, V> { 75 type Item = (&'a K, &'a V); 76 type IntoIter = Iter<'a, K, V>; into_iter(self) -> Self::IntoIter77 fn into_iter(self) -> Self::IntoIter { 78 self.iter() 79 } 80 } 81 } 82 83 mod unordered { 84 use crate::syntax::set::UnorderedSet; 85 use std::borrow::Borrow; 86 use std::collections::hash_map::{Entry, HashMap}; 87 use std::hash::Hash; 88 89 // Wrapper prohibits accidentally introducing iteration over the map, which 90 // could lead to nondeterministic generated code. 91 pub struct UnorderedMap<K, V>(HashMap<K, V>); 92 93 impl<K, V> UnorderedMap<K, V> { new() -> Self94 pub fn new() -> Self { 95 UnorderedMap(HashMap::new()) 96 } 97 } 98 99 impl<K, V> UnorderedMap<K, V> 100 where 101 K: Hash + Eq, 102 { insert(&mut self, key: K, value: V) -> Option<V>103 pub fn insert(&mut self, key: K, value: V) -> Option<V> { 104 self.0.insert(key, value) 105 } 106 contains_key<Q>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: ?Sized + Hash + Eq,107 pub fn contains_key<Q>(&self, key: &Q) -> bool 108 where 109 K: Borrow<Q>, 110 Q: ?Sized + Hash + Eq, 111 { 112 self.0.contains_key(key) 113 } 114 get<Q>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: ?Sized + Hash + Eq,115 pub fn get<Q>(&self, key: &Q) -> Option<&V> 116 where 117 K: Borrow<Q>, 118 Q: ?Sized + Hash + Eq, 119 { 120 self.0.get(key) 121 } 122 entry(&mut self, key: K) -> Entry<K, V>123 pub fn entry(&mut self, key: K) -> Entry<K, V> { 124 self.0.entry(key) 125 } 126 remove<Q>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: ?Sized + Hash + Eq,127 pub fn remove<Q>(&mut self, key: &Q) -> Option<V> 128 where 129 K: Borrow<Q>, 130 Q: ?Sized + Hash + Eq, 131 { 132 self.0.remove(key) 133 } 134 keys(&self) -> UnorderedSet<K> where K: Copy,135 pub fn keys(&self) -> UnorderedSet<K> 136 where 137 K: Copy, 138 { 139 let mut set = UnorderedSet::new(); 140 for key in self.0.keys() { 141 set.insert(*key); 142 } 143 set 144 } 145 } 146 } 147 148 pub struct Iter<'a, K, V>(slice::Iter<'a, (K, V)>); 149 150 impl<'a, K, V> Iterator for Iter<'a, K, V> { 151 type Item = (&'a K, &'a V); 152 next(&mut self) -> Option<Self::Item>153 fn next(&mut self) -> Option<Self::Item> { 154 let (k, v) = self.0.next()?; 155 Some((k, v)) 156 } 157 size_hint(&self) -> (usize, Option<usize>)158 fn size_hint(&self) -> (usize, Option<usize>) { 159 self.0.size_hint() 160 } 161 } 162 163 impl<K, V> Default for UnorderedMap<K, V> { default() -> Self164 fn default() -> Self { 165 UnorderedMap::new() 166 } 167 } 168 169 impl<Q, K, V> Index<&Q> for UnorderedMap<K, V> 170 where 171 K: Borrow<Q> + Hash + Eq, 172 Q: ?Sized + Hash + Eq, 173 { 174 type Output = V; 175 index(&self, key: &Q) -> &V176 fn index(&self, key: &Q) -> &V { 177 self.get(key).unwrap() 178 } 179 } 180