1 | #[cfg (feature = "persistent" )] |
2 | use dogged::DVec; |
3 | use snapshot_vec as sv; |
4 | use std::marker::PhantomData; |
5 | use std::ops::{self, Range}; |
6 | |
7 | use undo_log::{Rollback, Snapshots, UndoLogs, VecLog}; |
8 | |
9 | use super::{UnifyKey, UnifyValue, VarValue}; |
10 | |
11 | #[allow (dead_code)] // rustc BUG |
12 | #[allow (type_alias_bounds)] |
13 | type Key<S: UnificationStoreBase> = <S as UnificationStoreBase>::Key; |
14 | |
15 | /// Largely internal trait implemented by the unification table |
16 | /// backing store types. The most common such type is `InPlace`, |
17 | /// which indicates a standard, mutable unification table. |
18 | pub trait UnificationStoreBase: ops::Index<usize, Output = VarValue<Key<Self>>> { |
19 | type Key: UnifyKey<Value = Self::Value>; |
20 | type Value: UnifyValue; |
21 | |
22 | fn len(&self) -> usize; |
23 | |
24 | fn tag() -> &'static str { |
25 | Self::Key::tag() |
26 | } |
27 | } |
28 | |
29 | pub trait UnificationStoreMut: UnificationStoreBase { |
30 | fn reset_unifications(&mut self, value: impl FnMut(u32) -> VarValue<Self::Key>); |
31 | |
32 | fn push(&mut self, value: VarValue<Self::Key>); |
33 | |
34 | fn reserve(&mut self, num_new_values: usize); |
35 | |
36 | fn update<F>(&mut self, index: usize, op: F) |
37 | where |
38 | F: FnOnce(&mut VarValue<Self::Key>); |
39 | } |
40 | |
41 | pub trait UnificationStore: UnificationStoreMut { |
42 | type Snapshot; |
43 | |
44 | fn start_snapshot(&mut self) -> Self::Snapshot; |
45 | |
46 | fn rollback_to(&mut self, snapshot: Self::Snapshot); |
47 | |
48 | fn commit(&mut self, snapshot: Self::Snapshot); |
49 | |
50 | fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize>; |
51 | } |
52 | |
53 | /// Backing store for an in-place unification table. |
54 | /// Not typically used directly. |
55 | #[derive (Clone, Debug)] |
56 | pub struct InPlace< |
57 | K: UnifyKey, |
58 | V: sv::VecLike<Delegate<K>> = Vec<VarValue<K>>, |
59 | L = VecLog<sv::UndoLog<Delegate<K>>>, |
60 | > { |
61 | pub(crate) values: sv::SnapshotVec<Delegate<K>, V, L>, |
62 | } |
63 | |
64 | // HACK(eddyb) manual impl avoids `Default` bound on `K`. |
65 | impl<K: UnifyKey, V: sv::VecLike<Delegate<K>> + Default, L: Default> Default for InPlace<K, V, L> { |
66 | fn default() -> Self { |
67 | InPlace { |
68 | values: sv::SnapshotVec::new(), |
69 | } |
70 | } |
71 | } |
72 | |
73 | impl<K, V, L> UnificationStoreBase for InPlace<K, V, L> |
74 | where |
75 | K: UnifyKey, |
76 | V: sv::VecLike<Delegate<K>>, |
77 | { |
78 | type Key = K; |
79 | type Value = K::Value; |
80 | |
81 | fn len(&self) -> usize { |
82 | self.values.len() |
83 | } |
84 | } |
85 | |
86 | impl<K, V, L> UnificationStoreMut for InPlace<K, V, L> |
87 | where |
88 | K: UnifyKey, |
89 | V: sv::VecLike<Delegate<K>>, |
90 | L: UndoLogs<sv::UndoLog<Delegate<K>>>, |
91 | { |
92 | #[inline ] |
93 | fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue<Self::Key>) { |
94 | self.values.set_all(|i: usize| value(i as u32)); |
95 | } |
96 | |
97 | #[inline ] |
98 | fn push(&mut self, value: VarValue<Self::Key>) { |
99 | self.values.push(elem:value); |
100 | } |
101 | |
102 | #[inline ] |
103 | fn reserve(&mut self, num_new_values: usize) { |
104 | self.values.reserve(additional:num_new_values); |
105 | } |
106 | |
107 | #[inline ] |
108 | fn update<F>(&mut self, index: usize, op: F) |
109 | where |
110 | F: FnOnce(&mut VarValue<Self::Key>), |
111 | { |
112 | self.values.update(index, op) |
113 | } |
114 | } |
115 | |
116 | impl<K, V, L> UnificationStore for InPlace<K, V, L> |
117 | where |
118 | K: UnifyKey, |
119 | V: sv::VecLike<Delegate<K>>, |
120 | L: Snapshots<sv::UndoLog<Delegate<K>>>, |
121 | { |
122 | type Snapshot = sv::Snapshot<L::Snapshot>; |
123 | |
124 | #[inline ] |
125 | fn start_snapshot(&mut self) -> Self::Snapshot { |
126 | self.values.start_snapshot() |
127 | } |
128 | |
129 | #[inline ] |
130 | fn rollback_to(&mut self, snapshot: Self::Snapshot) { |
131 | self.values.rollback_to(snapshot); |
132 | } |
133 | |
134 | #[inline ] |
135 | fn commit(&mut self, snapshot: Self::Snapshot) { |
136 | self.values.commit(snapshot); |
137 | } |
138 | |
139 | #[inline ] |
140 | fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize> { |
141 | snapshot.value_count..self.len() |
142 | } |
143 | } |
144 | |
145 | impl<K, V, L> ops::Index<usize> for InPlace<K, V, L> |
146 | where |
147 | V: sv::VecLike<Delegate<K>>, |
148 | K: UnifyKey, |
149 | { |
150 | type Output = VarValue<K>; |
151 | fn index(&self, index: usize) -> &VarValue<K> { |
152 | &self.values[index] |
153 | } |
154 | } |
155 | |
156 | #[doc (hidden)] |
157 | #[derive (Copy, Clone, Debug)] |
158 | pub struct Delegate<K>(PhantomData<K>); |
159 | |
160 | impl<K: UnifyKey> sv::SnapshotVecDelegate for Delegate<K> { |
161 | type Value = VarValue<K>; |
162 | type Undo = (); |
163 | |
164 | fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {} |
165 | } |
166 | |
167 | impl<K: UnifyKey> Rollback<sv::UndoLog<Delegate<K>>> for super::UnificationTableStorage<K> { |
168 | fn reverse(&mut self, undo: sv::UndoLog<Delegate<K>>) { |
169 | self.values.values.reverse(undo); |
170 | } |
171 | } |
172 | |
173 | #[cfg (feature = "persistent" )] |
174 | #[derive (Clone, Debug)] |
175 | pub struct Persistent<K: UnifyKey> { |
176 | values: DVec<VarValue<K>>, |
177 | } |
178 | |
179 | // HACK(eddyb) manual impl avoids `Default` bound on `K`. |
180 | #[cfg (feature = "persistent" )] |
181 | impl<K: UnifyKey> Default for Persistent<K> { |
182 | fn default() -> Self { |
183 | Persistent { |
184 | values: DVec::new(), |
185 | } |
186 | } |
187 | } |
188 | |
189 | #[cfg (feature = "persistent" )] |
190 | impl<K: UnifyKey> UnificationStoreBase for Persistent<K> { |
191 | type Key = K; |
192 | type Value = K::Value; |
193 | |
194 | fn len(&self) -> usize { |
195 | self.values.len() |
196 | } |
197 | } |
198 | |
199 | #[cfg (feature = "persistent" )] |
200 | impl<K: UnifyKey> UnificationStoreMut for Persistent<K> { |
201 | #[inline ] |
202 | fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue<Self::Key>) { |
203 | // Without extending dogged, there isn't obviously a more |
204 | // efficient way to do this. But it's pretty dumb. Maybe |
205 | // dogged needs a `map`. |
206 | for i in 0..self.values.len() { |
207 | self.values[i] = value(i as u32); |
208 | } |
209 | } |
210 | |
211 | #[inline ] |
212 | fn push(&mut self, value: VarValue<Self::Key>) { |
213 | self.values.push(value); |
214 | } |
215 | |
216 | #[inline ] |
217 | fn reserve(&mut self, _num_new_values: usize) { |
218 | // not obviously relevant to DVec. |
219 | } |
220 | |
221 | #[inline ] |
222 | fn update<F>(&mut self, index: usize, op: F) |
223 | where |
224 | F: FnOnce(&mut VarValue<Self::Key>), |
225 | { |
226 | let p = &mut self.values[index]; |
227 | op(p); |
228 | } |
229 | } |
230 | |
231 | #[cfg (feature = "persistent" )] |
232 | impl<K: UnifyKey> UnificationStore for Persistent<K> { |
233 | type Snapshot = Self; |
234 | |
235 | #[inline ] |
236 | fn start_snapshot(&mut self) -> Self::Snapshot { |
237 | self.clone() |
238 | } |
239 | |
240 | #[inline ] |
241 | fn rollback_to(&mut self, snapshot: Self::Snapshot) { |
242 | *self = snapshot; |
243 | } |
244 | |
245 | #[inline ] |
246 | fn commit(&mut self, _snapshot: Self::Snapshot) {} |
247 | |
248 | #[inline ] |
249 | fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize> { |
250 | snapshot.len()..self.len() |
251 | } |
252 | } |
253 | |
254 | #[cfg (feature = "persistent" )] |
255 | impl<K> ops::Index<usize> for Persistent<K> |
256 | where |
257 | K: UnifyKey, |
258 | { |
259 | type Output = VarValue<K>; |
260 | fn index(&self, index: usize) -> &VarValue<K> { |
261 | &self.values[index] |
262 | } |
263 | } |
264 | |