1use std::borrow::Borrow; 2use std::hash::Hash; 3use std::ops::Index; 4use std::slice; 5 6pub use self::ordered::OrderedMap; 7pub use self::unordered::UnorderedMap; 8pub use std::collections::hash_map::Entry; 9 10mod 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> { 22 pub fn new() -> Self { 23 OrderedMap { 24 map: UnorderedMap::new(), 25 vec: Vec::new(), 26 } 27 } 28 29 pub fn iter(&self) -> Iter<K, V> { 30 Iter(self.vec.iter()) 31 } 32 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 { 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 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 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>; 77 fn into_iter(self) -> Self::IntoIter { 78 self.iter() 79 } 80 } 81} 82 83mod 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> { 94 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 { 103 pub fn insert(&mut self, key: K, value: V) -> Option<V> { 104 self.0.insert(key, value) 105 } 106 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 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 123 pub fn entry(&mut self, key: K) -> Entry<K, V> { 124 self.0.entry(key) 125 } 126 127 #[allow(dead_code)] // only used by cxx-build, not cxxbridge-macro 128 pub fn remove<Q>(&mut self, key: &Q) -> Option<V> 129 where 130 K: Borrow<Q>, 131 Q: ?Sized + Hash + Eq, 132 { 133 self.0.remove(key) 134 } 135 136 pub fn keys(&self) -> UnorderedSet<K> 137 where 138 K: Copy, 139 { 140 let mut set = UnorderedSet::new(); 141 for key in self.0.keys() { 142 set.insert(*key); 143 } 144 set 145 } 146 } 147} 148 149pub struct Iter<'a, K, V>(slice::Iter<'a, (K, V)>); 150 151impl<'a, K, V> Iterator for Iter<'a, K, V> { 152 type Item = (&'a K, &'a V); 153 154 fn next(&mut self) -> Option<Self::Item> { 155 let (k, v) = self.0.next()?; 156 Some((k, v)) 157 } 158 159 fn size_hint(&self) -> (usize, Option<usize>) { 160 self.0.size_hint() 161 } 162} 163 164impl<K, V> Default for UnorderedMap<K, V> { 165 fn default() -> Self { 166 UnorderedMap::new() 167 } 168} 169 170impl<Q, K, V> Index<&Q> for UnorderedMap<K, V> 171where 172 K: Borrow<Q> + Hash + Eq, 173 Q: ?Sized + Hash + Eq, 174{ 175 type Output = V; 176 177 fn index(&self, key: &Q) -> &V { 178 self.get(key).unwrap() 179 } 180} 181