1#[cfg(feature = "persistent")]
2use dogged::DVec;
3use snapshot_vec as sv;
4use std::marker::PhantomData;
5use std::ops::{self, Range};
6
7use undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
8
9use super::{UnifyKey, UnifyValue, VarValue};
10
11#[allow(dead_code)] // rustc BUG
12#[allow(type_alias_bounds)]
13type 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.
18pub 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
29pub 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
41pub 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)]
56pub 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`.
65impl<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
73impl<K, V, L> UnificationStoreBase for InPlace<K, V, L>
74where
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
86impl<K, V, L> UnificationStoreMut for InPlace<K, V, L>
87where
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
116impl<K, V, L> UnificationStore for InPlace<K, V, L>
117where
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
145impl<K, V, L> ops::Index<usize> for InPlace<K, V, L>
146where
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)]
158pub struct Delegate<K>(PhantomData<K>);
159
160impl<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
167impl<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)]
175pub 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")]
181impl<K: UnifyKey> Default for Persistent<K> {
182 fn default() -> Self {
183 Persistent {
184 values: DVec::new(),
185 }
186 }
187}
188
189#[cfg(feature = "persistent")]
190impl<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")]
200impl<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")]
232impl<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")]
255impl<K> ops::Index<usize> for Persistent<K>
256where
257 K: UnifyKey,
258{
259 type Output = VarValue<K>;
260 fn index(&self, index: usize) -> &VarValue<K> {
261 &self.values[index]
262 }
263}
264