]>
Commit | Line | Data |
---|---|---|
0531ce1d XL |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! Union-find implementation. The main type is `UnificationTable`. | |
12 | //! | |
13 | //! You can define your own type for the *keys* in the table, but you | |
14 | //! must implement `UnifyKey` for that type. The assumption is that | |
15 | //! keys will be newtyped integers, hence we require that they | |
16 | //! implement `Copy`. | |
17 | //! | |
18 | //! Keys can have values associated with them. The assumption is that | |
19 | //! these values are cheaply cloneable (ideally, `Copy`), and some of | |
20 | //! the interfaces are oriented around that assumption. If you just | |
21 | //! want the classical "union-find" algorithm where you group things | |
22 | //! into sets, use the `Value` type of `()`. | |
23 | //! | |
24 | //! When you have keys with non-trivial values, you must also define | |
25 | //! how those values can be merged. As part of doing this, you can | |
26 | //! define the "error" type to return on error; if errors are not | |
27 | //! possible, use `NoError` (an uninstantiable struct). Using this | |
28 | //! type also unlocks various more ergonomic methods (e.g., `union()` | |
29 | //! in place of `unify_var_var()`). | |
30 | //! | |
31 | //! The best way to see how it is used is to read the `tests.rs` file; | |
32 | //! search for e.g. `UnitKey`. | |
33 | ||
34 | use std::marker; | |
35 | use std::fmt::Debug; | |
532ac7d7 | 36 | use std::ops::Range; |
0531ce1d XL |
37 | |
38 | mod backing_vec; | |
39 | pub use self::backing_vec::{InPlace, UnificationStore}; | |
40 | ||
41 | #[cfg(feature = "persistent")] | |
42 | pub use self::backing_vec::Persistent; | |
43 | ||
44 | ||
45 | #[cfg(test)] | |
46 | mod tests; | |
47 | ||
48 | /// This trait is implemented by any type that can serve as a type | |
49 | /// variable. We call such variables *unification keys*. For example, | |
50 | /// this trait is implemented by `IntVid`, which represents integral | |
51 | /// variables. | |
52 | /// | |
53 | /// Each key type has an associated value type `V`. For example, for | |
54 | /// `IntVid`, this is `Option<IntVarValue>`, representing some | |
55 | /// (possibly not yet known) sort of integer. | |
56 | /// | |
57 | /// Clients are expected to provide implementations of this trait; you | |
58 | /// can see some examples in the `test` module. | |
59 | pub trait UnifyKey: Copy + Clone + Debug + PartialEq { | |
60 | type Value: UnifyValue; | |
61 | ||
62 | fn index(&self) -> u32; | |
63 | ||
64 | fn from_index(u: u32) -> Self; | |
65 | ||
66 | fn tag() -> &'static str; | |
67 | ||
68 | /// If true, then `self` should be preferred as root to `other`. | |
69 | /// Note that we assume a consistent partial ordering, so | |
70 | /// returning true implies that `other.prefer_as_root_to(self)` | |
71 | /// would return false. If there is no ordering between two keys | |
72 | /// (i.e., `a.prefer_as_root_to(b)` and `b.prefer_as_root_to(a)` | |
73 | /// both return false) then the rank will be used to determine the | |
74 | /// root in an optimal way. | |
75 | /// | |
76 | /// NB. The only reason to implement this method is if you want to | |
77 | /// control what value is returned from `find()`. In general, it | |
78 | /// is better to let the unification table determine the root, | |
79 | /// since overriding the rank can cause execution time to increase | |
80 | /// dramatically. | |
81 | #[allow(unused_variables)] | |
82 | fn order_roots( | |
83 | a: Self, | |
84 | a_value: &Self::Value, | |
85 | b: Self, | |
86 | b_value: &Self::Value, | |
87 | ) -> Option<(Self, Self)> { | |
88 | None | |
89 | } | |
90 | } | |
91 | ||
92 | /// Trait implemented for **values** associated with a unification | |
93 | /// key. This trait defines how to merge the values from two keys that | |
94 | /// are unioned together. This merging can be fallible. If you attempt | |
95 | /// to union two keys whose values cannot be merged, then the error is | |
96 | /// propagated up and the two keys are not unioned. | |
97 | /// | |
98 | /// This crate provides implementations of `UnifyValue` for `()` | |
99 | /// (which is infallible) and `Option<T>` (where `T: UnifyValue`). The | |
100 | /// option implementation merges two sum-values using the `UnifyValue` | |
101 | /// implementation of `T`. | |
102 | /// | |
103 | /// See also `EqUnifyValue`, which is a convenience trait for cases | |
104 | /// where the "merge" operation succeeds only if the two values are | |
105 | /// equal. | |
106 | pub trait UnifyValue: Clone + Debug { | |
107 | /// Defines the type to return when merging of two values fails. | |
108 | /// If merging is infallible, use the special struct `NoError` | |
109 | /// found in this crate, which unlocks various more convenient | |
110 | /// methods on the unification table. | |
111 | type Error; | |
112 | ||
113 | /// Given two values, produce a new value that combines them. | |
114 | /// If that is not possible, produce an error. | |
115 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error>; | |
116 | } | |
117 | ||
118 | /// A convenient helper for unification values which must be equal or | |
119 | /// else an error occurs. For example, if you are unifying types in a | |
120 | /// simple functional language, this may be appropriate, since (e.g.) | |
121 | /// you can't unify a type variable bound to `int` with one bound to | |
122 | /// `float` (but you can unify two type variables both bound to | |
123 | /// `int`). | |
124 | /// | |
125 | /// Any type which implements `EqUnifyValue` automatially implements | |
126 | /// `UnifyValue`; if the two values are equal, merging is permitted. | |
127 | /// Otherwise, the error `(v1, v2)` is returned, where `v1` and `v2` | |
128 | /// are the two unequal values. | |
129 | pub trait EqUnifyValue: Eq + Clone + Debug {} | |
130 | ||
131 | impl<T: EqUnifyValue> UnifyValue for T { | |
132 | type Error = (T, T); | |
133 | ||
134 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error> { | |
135 | if value1 == value2 { | |
136 | Ok(value1.clone()) | |
137 | } else { | |
138 | Err((value1.clone(), value2.clone())) | |
139 | } | |
140 | } | |
141 | } | |
142 | ||
143 | /// A struct which can never be instantiated. Used | |
144 | /// for the error type for infallible cases. | |
145 | #[derive(Debug)] | |
146 | pub struct NoError { | |
147 | _dummy: (), | |
148 | } | |
149 | ||
150 | /// Value of a unification key. We implement Tarjan's union-find | |
151 | /// algorithm: when two keys are unified, one of them is converted | |
152 | /// into a "redirect" pointing at the other. These redirects form a | |
153 | /// DAG: the roots of the DAG (nodes that are not redirected) are each | |
154 | /// associated with a value of type `V` and a rank. The rank is used | |
155 | /// to keep the DAG relatively balanced, which helps keep the running | |
156 | /// time of the algorithm under control. For more information, see | |
157 | /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>. | |
158 | #[derive(PartialEq, Clone, Debug)] | |
159 | pub struct VarValue<K: UnifyKey> { // FIXME pub | |
160 | parent: K, // if equal to self, this is a root | |
161 | value: K::Value, // value assigned (only relevant to root) | |
162 | rank: u32, // max depth (only relevant to root) | |
163 | } | |
164 | ||
165 | /// Table of unification keys and their values. You must define a key type K | |
166 | /// that implements the `UnifyKey` trait. Unification tables can be used in two-modes: | |
167 | /// | |
168 | /// - in-place (`UnificationTable<InPlace<K>>` or `InPlaceUnificationTable<K>`): | |
169 | /// - This is the standard mutable mode, where the array is modified | |
170 | /// in place. | |
171 | /// - To do backtracking, you can employ the `snapshot` and `rollback_to` | |
172 | /// methods. | |
173 | /// - persistent (`UnificationTable<Persistent<K>>` or `PersistentUnificationTable<K>`): | |
174 | /// - In this mode, we use a persistent vector to store the data, so that | |
175 | /// cloning the table is an O(1) operation. | |
176 | /// - This implies that ordinary operations are quite a bit slower though. | |
177 | /// - Requires the `persistent` feature be selected in your Cargo.toml file. | |
a1dfa0c6 | 178 | #[derive(Clone, Debug, Default)] |
0531ce1d XL |
179 | pub struct UnificationTable<S: UnificationStore> { |
180 | /// Indicates the current value of each key. | |
181 | values: S, | |
182 | } | |
183 | ||
184 | /// A unification table that uses an "in-place" vector. | |
a1dfa0c6 XL |
185 | #[allow(type_alias_bounds)] |
186 | pub type InPlaceUnificationTable<K: UnifyKey> = UnificationTable<InPlace<K>>; | |
0531ce1d XL |
187 | |
188 | /// A unification table that uses a "persistent" vector. | |
189 | #[cfg(feature = "persistent")] | |
a1dfa0c6 XL |
190 | #[allow(type_alias_bounds)] |
191 | pub type PersistentUnificationTable<K: UnifyKey> = UnificationTable<Persistent<K>>; | |
0531ce1d XL |
192 | |
193 | /// At any time, users may snapshot a unification table. The changes | |
194 | /// made during the snapshot may either be *committed* or *rolled back*. | |
195 | pub struct Snapshot<S: UnificationStore> { | |
196 | // Link snapshot to the unification store `S` of the table. | |
197 | marker: marker::PhantomData<S>, | |
198 | snapshot: S::Snapshot, | |
199 | } | |
200 | ||
201 | impl<K: UnifyKey> VarValue<K> { | |
202 | fn new_var(key: K, value: K::Value) -> VarValue<K> { | |
203 | VarValue::new(key, value, 0) | |
204 | } | |
205 | ||
206 | fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> { | |
207 | VarValue { | |
208 | parent: parent, // this is a root | |
209 | value: value, | |
210 | rank: rank, | |
211 | } | |
212 | } | |
213 | ||
214 | fn redirect(&mut self, to: K) { | |
215 | self.parent = to; | |
216 | } | |
217 | ||
218 | fn root(&mut self, rank: u32, value: K::Value) { | |
219 | self.rank = rank; | |
220 | self.value = value; | |
221 | } | |
222 | ||
223 | fn parent(&self, self_key: K) -> Option<K> { | |
224 | self.if_not_self(self.parent, self_key) | |
225 | } | |
226 | ||
227 | fn if_not_self(&self, key: K, self_key: K) -> Option<K> { | |
228 | if key == self_key { | |
229 | None | |
230 | } else { | |
231 | Some(key) | |
232 | } | |
233 | } | |
234 | } | |
235 | ||
236 | // We can't use V:LatticeValue, much as I would like to, | |
237 | // because frequently the pattern is that V=Option<U> for some | |
238 | // other type parameter U, and we have no way to say | |
239 | // Option<U>:LatticeValue. | |
240 | ||
241 | impl<S: UnificationStore> UnificationTable<S> { | |
242 | pub fn new() -> Self { | |
a1dfa0c6 | 243 | Self::default() |
0531ce1d XL |
244 | } |
245 | ||
246 | /// Starts a new snapshot. Each snapshot must be either | |
247 | /// rolled back or committed in a "LIFO" (stack) order. | |
248 | pub fn snapshot(&mut self) -> Snapshot<S> { | |
249 | Snapshot { | |
250 | marker: marker::PhantomData::<S>, | |
251 | snapshot: self.values.start_snapshot(), | |
252 | } | |
253 | } | |
254 | ||
255 | /// Reverses all changes since the last snapshot. Also | |
256 | /// removes any keys that have been created since then. | |
257 | pub fn rollback_to(&mut self, snapshot: Snapshot<S>) { | |
258 | debug!("{}: rollback_to()", S::tag()); | |
259 | self.values.rollback_to(snapshot.snapshot); | |
260 | } | |
261 | ||
262 | /// Commits all changes since the last snapshot. Of course, they | |
263 | /// can still be undone if there is a snapshot further out. | |
264 | pub fn commit(&mut self, snapshot: Snapshot<S>) { | |
265 | debug!("{}: commit()", S::tag()); | |
266 | self.values.commit(snapshot.snapshot); | |
267 | } | |
268 | ||
269 | /// Creates a fresh key with the given value. | |
270 | pub fn new_key(&mut self, value: S::Value) -> S::Key { | |
271 | let len = self.values.len(); | |
272 | let key: S::Key = UnifyKey::from_index(len as u32); | |
273 | self.values.push(VarValue::new_var(key, value)); | |
274 | debug!("{}: created new key: {:?}", S::tag(), key); | |
275 | key | |
276 | } | |
277 | ||
94b46f34 XL |
278 | /// Reserve memory for `num_new_keys` to be created. Does not |
279 | /// actually create the new keys; you must then invoke `new_key`. | |
280 | pub fn reserve(&mut self, num_new_keys: usize) { | |
281 | self.values.reserve(num_new_keys); | |
282 | } | |
283 | ||
284 | /// Clears all unifications that have been performed, resetting to | |
285 | /// the initial state. The values of each variable are given by | |
286 | /// the closure. | |
287 | pub fn reset_unifications( | |
288 | &mut self, | |
289 | mut value: impl FnMut(S::Key) -> S::Value, | |
290 | ) { | |
291 | self.values.reset_unifications(|i| { | |
292 | let key = UnifyKey::from_index(i as u32); | |
293 | let value = value(key); | |
294 | VarValue::new_var(key, value) | |
295 | }); | |
296 | } | |
297 | ||
0531ce1d XL |
298 | /// Returns the number of keys created so far. |
299 | pub fn len(&self) -> usize { | |
300 | self.values.len() | |
301 | } | |
302 | ||
532ac7d7 XL |
303 | /// Returns the keys of all variables created since the `snapshot`. |
304 | pub fn vars_since_snapshot( | |
305 | &self, | |
306 | snapshot: &Snapshot<S>, | |
307 | ) -> Range<S::Key> { | |
308 | let range = self.values.values_since_snapshot(&snapshot.snapshot); | |
309 | S::Key::from_index(range.start as u32)..S::Key::from_index(range.end as u32) | |
310 | } | |
311 | ||
0531ce1d XL |
312 | /// Obtains the current value for a particular key. |
313 | /// Not for end-users; they can use `probe_value`. | |
314 | fn value(&self, key: S::Key) -> &VarValue<S::Key> { | |
315 | &self.values[key.index() as usize] | |
316 | } | |
317 | ||
318 | /// Find the root node for `vid`. This uses the standard | |
319 | /// union-find algorithm with path compression: | |
320 | /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>. | |
321 | /// | |
322 | /// NB. This is a building-block operation and you would probably | |
323 | /// prefer to call `probe` below. | |
e74abb32 XL |
324 | /// |
325 | /// This is an always-inlined version of this function for the hot | |
326 | /// callsites. `uninlined_get_root_key` is the never-inlined version. | |
327 | #[inline(always)] | |
328 | fn inlined_get_root_key(&mut self, vid: S::Key) -> S::Key { | |
0531ce1d XL |
329 | let redirect = { |
330 | match self.value(vid).parent(vid) { | |
331 | None => return vid, | |
332 | Some(redirect) => redirect, | |
333 | } | |
334 | }; | |
335 | ||
e74abb32 | 336 | let root_key: S::Key = self.uninlined_get_root_key(redirect); |
0531ce1d XL |
337 | if root_key != redirect { |
338 | // Path compression | |
339 | self.update_value(vid, |value| value.parent = root_key); | |
340 | } | |
341 | ||
342 | root_key | |
343 | } | |
344 | ||
e74abb32 XL |
345 | // This is a never-inlined version of this function for cold callsites. |
346 | // 'inlined_get_root_key` is the always-inlined version. | |
347 | #[inline(never)] | |
348 | fn uninlined_get_root_key(&mut self, vid: S::Key) -> S::Key { | |
349 | self.inlined_get_root_key(vid) | |
350 | } | |
351 | ||
0531ce1d XL |
352 | fn update_value<OP>(&mut self, key: S::Key, op: OP) |
353 | where | |
354 | OP: FnOnce(&mut VarValue<S::Key>), | |
355 | { | |
356 | self.values.update(key.index() as usize, op); | |
357 | debug!("Updated variable {:?} to {:?}", key, self.value(key)); | |
358 | } | |
359 | ||
360 | /// Either redirects `node_a` to `node_b` or vice versa, depending | |
361 | /// on the relative rank. The value associated with the new root | |
362 | /// will be `new_value`. | |
363 | /// | |
364 | /// NB: This is the "union" operation of "union-find". It is | |
365 | /// really more of a building block. If the values associated with | |
366 | /// your key are non-trivial, you would probably prefer to call | |
367 | /// `unify_var_var` below. | |
368 | fn unify_roots(&mut self, key_a: S::Key, key_b: S::Key, new_value: S::Value) { | |
369 | debug!("unify(key_a={:?}, key_b={:?})", key_a, key_b); | |
370 | ||
371 | let rank_a = self.value(key_a).rank; | |
372 | let rank_b = self.value(key_b).rank; | |
373 | if let Some((new_root, redirected)) = | |
374 | S::Key::order_roots( | |
375 | key_a, | |
376 | &self.value(key_a).value, | |
377 | key_b, | |
378 | &self.value(key_b).value, | |
379 | ) { | |
380 | // compute the new rank for the new root that they chose; | |
381 | // this may not be the optimal choice. | |
382 | let new_rank = if new_root == key_a { | |
383 | debug_assert!(redirected == key_b); | |
384 | if rank_a > rank_b { | |
385 | rank_a | |
386 | } else { | |
387 | rank_b + 1 | |
388 | } | |
389 | } else { | |
390 | debug_assert!(new_root == key_b); | |
391 | debug_assert!(redirected == key_a); | |
392 | if rank_b > rank_a { | |
393 | rank_b | |
394 | } else { | |
395 | rank_a + 1 | |
396 | } | |
397 | }; | |
398 | self.redirect_root(new_rank, redirected, new_root, new_value); | |
399 | } else if rank_a > rank_b { | |
400 | // a has greater rank, so a should become b's parent, | |
401 | // i.e., b should redirect to a. | |
402 | self.redirect_root(rank_a, key_b, key_a, new_value); | |
403 | } else if rank_a < rank_b { | |
404 | // b has greater rank, so a should redirect to b. | |
405 | self.redirect_root(rank_b, key_a, key_b, new_value); | |
406 | } else { | |
407 | // If equal, redirect one to the other and increment the | |
408 | // other's rank. | |
409 | self.redirect_root(rank_a + 1, key_a, key_b, new_value); | |
410 | } | |
411 | } | |
412 | ||
413 | /// Internal method to redirect `old_root_key` (which is currently | |
414 | /// a root) to a child of `new_root_key` (which will remain a | |
415 | /// root). The rank and value of `new_root_key` will be updated to | |
416 | /// `new_rank` and `new_value` respectively. | |
417 | fn redirect_root( | |
418 | &mut self, | |
419 | new_rank: u32, | |
420 | old_root_key: S::Key, | |
421 | new_root_key: S::Key, | |
422 | new_value: S::Value, | |
423 | ) { | |
424 | self.update_value(old_root_key, |old_root_value| { | |
425 | old_root_value.redirect(new_root_key); | |
426 | }); | |
427 | self.update_value(new_root_key, |new_root_value| { | |
428 | new_root_value.root(new_rank, new_value); | |
429 | }); | |
430 | } | |
431 | } | |
432 | ||
433 | /// //////////////////////////////////////////////////////////////////////// | |
434 | /// Public API | |
435 | ||
e74abb32 | 436 | impl<S, K, V> UnificationTable<S> |
0531ce1d XL |
437 | where |
438 | S: UnificationStore<Key = K, Value = V>, | |
439 | K: UnifyKey<Value = V>, | |
440 | V: UnifyValue, | |
441 | { | |
442 | /// Unions two keys without the possibility of failure; only | |
443 | /// applicable when unify values use `NoError` as their error | |
444 | /// type. | |
445 | pub fn union<K1, K2>(&mut self, a_id: K1, b_id: K2) | |
446 | where | |
447 | K1: Into<K>, | |
448 | K2: Into<K>, | |
449 | V: UnifyValue<Error = NoError>, | |
450 | { | |
451 | self.unify_var_var(a_id, b_id).unwrap(); | |
452 | } | |
453 | ||
454 | /// Unions a key and a value without the possibility of failure; | |
455 | /// only applicable when unify values use `NoError` as their error | |
456 | /// type. | |
457 | pub fn union_value<K1>(&mut self, id: K1, value: V) | |
458 | where | |
459 | K1: Into<K>, | |
460 | V: UnifyValue<Error = NoError>, | |
461 | { | |
462 | self.unify_var_value(id, value).unwrap(); | |
463 | } | |
464 | ||
465 | /// Given two keys, indicates whether they have been unioned together. | |
466 | pub fn unioned<K1, K2>(&mut self, a_id: K1, b_id: K2) -> bool | |
467 | where | |
468 | K1: Into<K>, | |
469 | K2: Into<K>, | |
470 | { | |
471 | self.find(a_id) == self.find(b_id) | |
472 | } | |
473 | ||
474 | /// Given a key, returns the (current) root key. | |
475 | pub fn find<K1>(&mut self, id: K1) -> K | |
476 | where | |
477 | K1: Into<K>, | |
478 | { | |
479 | let id = id.into(); | |
e74abb32 | 480 | self.uninlined_get_root_key(id) |
0531ce1d XL |
481 | } |
482 | ||
483 | /// Unions together two variables, merging their values. If | |
484 | /// merging the values fails, the error is propagated and this | |
485 | /// method has no effect. | |
486 | pub fn unify_var_var<K1, K2>(&mut self, a_id: K1, b_id: K2) -> Result<(), V::Error> | |
487 | where | |
488 | K1: Into<K>, | |
489 | K2: Into<K>, | |
490 | { | |
491 | let a_id = a_id.into(); | |
492 | let b_id = b_id.into(); | |
493 | ||
e74abb32 XL |
494 | let root_a = self.uninlined_get_root_key(a_id); |
495 | let root_b = self.uninlined_get_root_key(b_id); | |
0531ce1d XL |
496 | |
497 | if root_a == root_b { | |
498 | return Ok(()); | |
499 | } | |
500 | ||
501 | let combined = V::unify_values(&self.value(root_a).value, &self.value(root_b).value)?; | |
502 | ||
503 | Ok(self.unify_roots(root_a, root_b, combined)) | |
504 | } | |
505 | ||
506 | /// Sets the value of the key `a_id` to `b`, attempting to merge | |
507 | /// with the previous value. | |
508 | pub fn unify_var_value<K1>(&mut self, a_id: K1, b: V) -> Result<(), V::Error> | |
509 | where | |
510 | K1: Into<K>, | |
511 | { | |
512 | let a_id = a_id.into(); | |
e74abb32 | 513 | let root_a = self.uninlined_get_root_key(a_id); |
0531ce1d XL |
514 | let value = V::unify_values(&self.value(root_a).value, &b)?; |
515 | self.update_value(root_a, |node| node.value = value); | |
516 | Ok(()) | |
517 | } | |
518 | ||
519 | /// Returns the current value for the given key. If the key has | |
520 | /// been union'd, this will give the value from the current root. | |
521 | pub fn probe_value<K1>(&mut self, id: K1) -> V | |
e74abb32 XL |
522 | where |
523 | K1: Into<K>, | |
524 | { | |
525 | self.inlined_probe_value(id) | |
526 | } | |
527 | ||
528 | // An always-inlined version of `probe_value`, for hot callsites. | |
529 | #[inline(always)] | |
530 | pub fn inlined_probe_value<K1>(&mut self, id: K1) -> V | |
0531ce1d XL |
531 | where |
532 | K1: Into<K>, | |
533 | { | |
534 | let id = id.into(); | |
e74abb32 | 535 | let id = self.inlined_get_root_key(id); |
0531ce1d XL |
536 | self.value(id).value.clone() |
537 | } | |
538 | } | |
539 | ||
540 | ||
541 | /////////////////////////////////////////////////////////////////////////// | |
542 | ||
543 | impl UnifyValue for () { | |
544 | type Error = NoError; | |
545 | ||
546 | fn unify_values(_: &(), _: &()) -> Result<(), NoError> { | |
547 | Ok(()) | |
548 | } | |
549 | } | |
550 | ||
551 | impl<V: UnifyValue> UnifyValue for Option<V> { | |
552 | type Error = V::Error; | |
553 | ||
554 | fn unify_values(a: &Option<V>, b: &Option<V>) -> Result<Self, V::Error> { | |
555 | match (a, b) { | |
556 | (&None, &None) => Ok(None), | |
557 | (&Some(ref v), &None) | | |
558 | (&None, &Some(ref v)) => Ok(Some(v.clone())), | |
559 | (&Some(ref a), &Some(ref b)) => { | |
560 | match V::unify_values(a, b) { | |
561 | Ok(v) => Ok(Some(v)), | |
562 | Err(err) => Err(err), | |
563 | } | |
564 | } | |
565 | } | |
566 | } | |
567 | } |