• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
127         #[allow(dead_code)] // only used by cxx-build, not cxxbridge-macro
remove<Q>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: ?Sized + Hash + Eq,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 
keys(&self) -> UnorderedSet<K> where K: Copy,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 
149 pub struct Iter<'a, K, V>(slice::Iter<'a, (K, V)>);
150 
151 impl<'a, K, V> Iterator for Iter<'a, K, V> {
152     type Item = (&'a K, &'a V);
153 
next(&mut self) -> Option<Self::Item>154     fn next(&mut self) -> Option<Self::Item> {
155         let (k, v) = self.0.next()?;
156         Some((k, v))
157     }
158 
size_hint(&self) -> (usize, Option<usize>)159     fn size_hint(&self) -> (usize, Option<usize>) {
160         self.0.size_hint()
161     }
162 }
163 
164 impl<K, V> Default for UnorderedMap<K, V> {
default() -> Self165     fn default() -> Self {
166         UnorderedMap::new()
167     }
168 }
169 
170 impl<Q, K, V> Index<&Q> for UnorderedMap<K, V>
171 where
172     K: Borrow<Q> + Hash + Eq,
173     Q: ?Sized + Hash + Eq,
174 {
175     type Output = V;
176 
index(&self, key: &Q) -> &V177     fn index(&self, key: &Q) -> &V {
178         self.get(key).unwrap()
179     }
180 }
181