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