src/vector_clock.rs

   1 use std::{
   2     fmt::{self, Debug}, cmp::Ordering, ops::Index,
   3     convert::TryFrom, mem
   4 };
   5 use smallvec::SmallVec;
   6 use rustc_index::vec::Idx;
   7 use rustc_data_structures::fx::FxHashMap;
   8
   9 /// A vector clock index, this is associated with a thread id
  10 /// but in some cases one vector index may be shared with
  11 /// multiple thread ids id it safe to do so.
  12 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
  13 pub struct VectorIdx(u32);
  14
  15 impl VectorIdx {
  16
  17     #[inline(always)]
  18     pub fn to_u32(self) -> u32 {
  19         self.0
  20     }
  21
  22     pub const MAX_INDEX: VectorIdx = VectorIdx(u32::MAX);
  23
  24 }
  25
  26 impl Idx for VectorIdx {
  27
  28     #[inline]
  29     fn new(idx: usize) -> Self {
  30         VectorIdx(u32::try_from(idx).unwrap())
  31     }
  32
  33     #[inline]
  34     fn index(self) -> usize {
  35         usize::try_from(self.0).unwrap()
  36     }
  37
  38 }
  39
  40 impl From<u32> for VectorIdx {
  41
  42     #[inline]
  43     fn from(id: u32) -> Self {
  44         Self(id)
  45     }
  46
  47 }
  48
  49 /// A sparse mapping of vector index values to vector clocks, this
  50 /// is optimized for the common case with only one element stored
  51 /// inside the map.
  52 /// This is used to store the set of currently active release
  53 /// sequences at a given memory location, since RMW operations
  54 /// allow for multiple release sequences to be active at once
  55 /// and to be collapsed back to one active release sequence
  56 /// once a non RMW atomic store operation occurs.
  57 /// An all zero vector is considered to be equal to no
  58 /// element stored internally since it will never be
  59 /// stored and has no meaning as a release sequence
  60 /// vector clock.
  61 #[derive(Clone)]
  62 pub struct VSmallClockMap(VSmallClockMapInner);
  63
  64 #[derive(Clone)]
  65 enum VSmallClockMapInner {
  66
  67     /// Zero or 1 vector elements, common
  68     /// case for the sparse set.
  69     /// The all zero vector clock is treated
  70     /// as equal to the empty element.
  71     Small(VectorIdx, VClock),
  72
  73     /// Hash-map of vector clocks.
  74     Large(FxHashMap<VectorIdx, VClock>)
  75 }
  76
  77 impl VSmallClockMap {
  78
  79     /// Remove all clock vectors from the map, setting them
  80     /// to the zero vector.
  81     pub fn clear(&mut self) {
  82         match &mut self.0 {
  83             VSmallClockMapInner::Small(_, clock) => {
  84                 clock.set_zero_vector()
  85             }
  86             VSmallClockMapInner::Large(hash_map) => {
  87                 hash_map.clear();
  88             }
  89         }
  90     }
  91
  92     /// Remove all clock vectors except for the clock vector
  93     /// stored at the given index, which is retained.
  94     pub fn retain_index(&mut self, index: VectorIdx) {
  95         match &mut self.0 {
  96             VSmallClockMapInner::Small(small_idx, clock) => {
  97                 if index != *small_idx {
  98
  99                     // The zero-vector is considered to equal
 100                     // the empty element.
 101                     clock.set_zero_vector()
 102                 }
 103             },
 104             VSmallClockMapInner::Large(hash_map) => {
 105                 let value = hash_map.remove(&index).unwrap_or_default();
 106                 self.0 = VSmallClockMapInner::Small(index, value);
 107             }
 108         }
 109     }
 110
 111     /// Insert the vector clock into the associated vector
 112     /// index.
 113     pub fn insert(&mut self, index: VectorIdx, clock: &VClock) {
 114         match &mut self.0 {
 115             VSmallClockMapInner::Small(small_idx, small_clock) => {
 116                 if small_clock.is_zero_vector() {
 117
 118                     *small_idx = index;
 119                     small_clock.clone_from(clock);
 120                 } else if !clock.is_zero_vector() {
 121
 122                     // Convert to using the hash-map representation.
 123                     let mut hash_map = FxHashMap::default();
 124                     hash_map.insert(*small_idx, mem::take(small_clock));
 125                     hash_map.insert(index, clock.clone());
 126                     self.0 = VSmallClockMapInner::Large(hash_map);
 127                 }
 128             },
 129             VSmallClockMapInner::Large(hash_map) => {
 130                 if !clock.is_zero_vector() {
 131                     hash_map.insert(index, clock.clone());
 132                 }
 133             }
 134         }
 135     }
 136
 137     /// Try to load the vector clock associated with the current
 138     ///  vector index.
 139     pub fn get(&self, index: VectorIdx) -> Option<&VClock> {
 140         match &self.0 {
 141             VSmallClockMapInner::Small(small_idx, small_clock) => {
 142                 if *small_idx == index && !small_clock.is_zero_vector() {
 143                     Some(small_clock)
 144                 } else {
 145                     None
 146                 }
 147             },
 148             VSmallClockMapInner::Large(hash_map) => {
 149                 hash_map.get(&index)
 150             }
 151         }
 152     }
 153 }
 154
 155 impl Default for VSmallClockMap {
 156
 157     #[inline]
 158     fn default() -> Self {
 159         VSmallClockMap(
 160             VSmallClockMapInner::Small(VectorIdx::new(0), VClock::default())
 161         )
 162     }
 163
 164 }
 165
 166 impl Debug for VSmallClockMap {
 167
 168     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 169         // Print the contents of the small vector clock set as the map
 170         // of vector index to vector clock that they represent.
 171         let mut map = f.debug_map();
 172         match &self.0 {
 173             VSmallClockMapInner::Small(small_idx, small_clock) => {
 174                 if !small_clock.is_zero_vector() {
 175                     map.entry(&small_idx, &small_clock);
 176                 }
 177             },
 178             VSmallClockMapInner::Large(hash_map) => {
 179                 for (idx, elem) in hash_map.iter() {
 180                     map.entry(idx, elem);
 181                 }
 182             }
 183         }
 184         map.finish()
 185     }
 186
 187 }
 188
 189
 190 impl PartialEq for VSmallClockMap {
 191
 192     fn eq(&self, other: &Self) -> bool {
 193         use VSmallClockMapInner::*;
 194         match (&self.0, &other.0) {
 195             (Small(i1, c1), Small(i2, c2)) => {
 196                 if c1.is_zero_vector() {
 197                     // Either they are both zero or they are non-equal
 198                     c2.is_zero_vector()
 199                 } else {
 200                     // At least one is non-zero, so the full comparison is correct
 201                     i1 == i2 && c1 == c2
 202                 }
 203             }
 204             (Small(idx, clock), Large(hash_map)) |
 205             (Large(hash_map), Small(idx, clock)) => {
 206
 207                 if hash_map.len() == 0 {
 208                     // Equal to the empty hash-map
 209                     clock.is_zero_vector()
 210                 } else if hash_map.len() == 1 {
 211                     // Equal to the hash-map with one element
 212                     let (hash_idx, hash_clock) = hash_map.iter().next().unwrap();
 213                     hash_idx == idx && hash_clock == clock
 214                 } else {
 215                     false
 216                 }
 217             }
 218             (Large(map1), Large(map2)) => {
 219                 map1 == map2
 220             }
 221         }
 222     }
 223
 224 }
 225
 226 impl Eq for VSmallClockMap {}
 227
 228
 229
 230 /// The size of the vector-clock to store inline
 231 /// clock vectors larger than this will be stored on the heap
 232 const SMALL_VECTOR: usize = 4;
 233
 234 /// The type of the time-stamps recorded in the data-race detector
 235 /// set to a type of unsigned integer
 236 pub type VTimestamp = u32;
 237
 238 /// A vector clock for detecting data-races, this is conceptually
 239 /// a map from a vector index (and thus a thread id) to a timestamp.
 240 /// The compare operations require that the invariant that the last
 241 /// element in the internal timestamp slice must not be a 0, hence
 242 /// all zero vector clocks are always represented by the empty slice;
 243 /// and allows for the implementation of compare operations to short
 244 /// circuit the calculation and return the correct result faster,
 245 /// also this means that there is only one unique valid length
 246 /// for each set of vector clock values and hence the PartialEq
 247 //  and Eq derivations are correct.
 248 #[derive(PartialEq, Eq, Default, Debug)]
 249 pub struct VClock(SmallVec<[VTimestamp; SMALL_VECTOR]>);
 250
 251 impl VClock {
 252
 253     /// Create a new vector-clock containing all zeros except
 254     /// for a value at the given index
 255     pub fn new_with_index(index: VectorIdx, timestamp: VTimestamp) -> VClock {
 256         let len = index.index() + 1;
 257         let mut vec = smallvec::smallvec![0; len];
 258         vec[index.index()] = timestamp;
 259         VClock(vec)
 260     }
 261
 262     /// Load the internal timestamp slice in the vector clock
 263     #[inline]
 264     pub fn as_slice(&self) -> &[VTimestamp] {
 265         self.0.as_slice()
 266     }
 267
 268     /// Get a mutable slice to the internal vector with minimum `min_len`
 269     /// elements, to preserve invariants this vector must modify
 270     /// the `min_len`-1 nth element to a non-zero value
 271     #[inline]
 272     fn get_mut_with_min_len(&mut self, min_len: usize) -> &mut [VTimestamp] {
 273         if self.0.len() < min_len {
 274             self.0.resize(min_len, 0);
 275         }
 276         assert!(self.0.len() >= min_len);
 277         self.0.as_mut_slice()
 278     }
 279
 280     /// Increment the vector clock at a known index
 281     /// this will panic if the vector index overflows
 282     #[inline]
 283     pub fn increment_index(&mut self, idx: VectorIdx) {
 284         let idx = idx.index();
 285         let mut_slice = self.get_mut_with_min_len(idx + 1);
 286         let idx_ref = &mut mut_slice[idx];
 287         *idx_ref = idx_ref.checked_add(1).expect("Vector clock overflow")
 288     }
 289
 290     // Join the two vector-clocks together, this
 291     // sets each vector-element to the maximum value
 292     // of that element in either of the two source elements.
 293     pub fn join(&mut self, other: &Self) {
 294         let rhs_slice = other.as_slice();
 295         let lhs_slice = self.get_mut_with_min_len(rhs_slice.len());
 296         for (l, &r) in lhs_slice.iter_mut().zip(rhs_slice.iter()) {
 297             *l = r.max(*l);
 298         }
 299     }
 300
 301     /// Set the element at the current index of the vector
 302     pub fn set_at_index(&mut self, other: &Self, idx: VectorIdx) {
 303         let idx = idx.index();
 304         let mut_slice = self.get_mut_with_min_len(idx + 1);
 305         let slice = other.as_slice();
 306         mut_slice[idx] = slice[idx];
 307     }
 308
 309     /// Set the vector to the all-zero vector
 310     #[inline]
 311     pub fn set_zero_vector(&mut self) {
 312         self.0.clear();
 313     }
 314
 315     /// Return if this vector is the all-zero vector
 316     pub fn is_zero_vector(&self) -> bool {
 317         self.0.is_empty()
 318     }
 319
 320 }
 321
 322 impl Clone for VClock {
 323
 324     fn clone(&self) -> Self {
 325         VClock(self.0.clone())
 326     }
 327
 328     // Optimized clone-from, can be removed
 329     // and replaced with a derive once a similar
 330     // optimization is inserted into SmallVec's
 331     // clone implementation.
 332     fn clone_from(&mut self, source: &Self) {
 333         let source_slice = source.as_slice();
 334         self.0.clear();
 335         self.0.extend_from_slice(source_slice);
 336     }
 337
 338 }
 339
 340 impl PartialOrd for VClock {
 341
 342     fn partial_cmp(&self, other: &VClock) -> Option<Ordering> {
 343
 344         // Load the values as slices
 345         let lhs_slice = self.as_slice();
 346         let rhs_slice = other.as_slice();
 347
 348         // Iterate through the combined vector slice continuously updating
 349         // the value of `order` to the current comparison of the vector from
 350         // index 0 to the currently checked index.
 351         // An Equal ordering can be converted into Less or Greater ordering
 352         // on finding an element that is less than or greater than the other
 353         // but if one Greater and one Less element-wise comparison is found
 354         // then no ordering is possible and so directly return an ordering
 355         // of None.
 356         let mut iter = lhs_slice.iter().zip(rhs_slice.iter());
 357         let mut order = match iter.next() {
 358             Some((lhs, rhs)) => lhs.cmp(rhs),
 359             None => Ordering::Equal
 360         };
 361         for (l, r) in iter {
 362             match order {
 363                 Ordering::Equal => order = l.cmp(r),
 364                 Ordering::Less => if l > r {
 365                     return None
 366                 },
 367                 Ordering::Greater => if l < r {
 368                     return None
 369                 }
 370             }
 371         }
 372
 373         // Now test if either left or right have trailing elements,
 374         // by the invariant the trailing elements have at least 1
 375         // non zero value, so no additional calculation is required
 376         // to determine the result of the PartialOrder.
 377         let l_len = lhs_slice.len();
 378         let r_len = rhs_slice.len();
 379         match l_len.cmp(&r_len) {
 380             // Equal means no additional elements: return current order
 381             Ordering::Equal => Some(order),
 382             // Right has at least 1 element > than the implicit 0,
 383             // so the only valid values are Ordering::Less or None.
 384             Ordering::Less => match order {
 385                 Ordering::Less | Ordering::Equal => Some(Ordering::Less),
 386                 Ordering::Greater => None
 387             }
 388             // Left has at least 1 element > than the implicit 0,
 389             // so the only valid values are Ordering::Greater or None.
 390             Ordering::Greater => match order {
 391                 Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
 392                 Ordering::Less => None
 393             }
 394         }
 395     }
 396
 397     fn lt(&self, other: &VClock) -> bool {
 398         // Load the values as slices
 399         let lhs_slice = self.as_slice();
 400         let rhs_slice = other.as_slice();
 401
 402         // If l_len > r_len then at least one element
 403         // in l_len is > than r_len, therefore the result
 404         // is either Some(Greater) or None, so return false
 405         // early.
 406         let l_len = lhs_slice.len();
 407         let r_len = rhs_slice.len();
 408         if l_len <= r_len {
 409             // If any elements on the left are greater than the right
 410             // then the result is None or Some(Greater), both of which
 411             // return false, the earlier test asserts that no elements in the
 412             // extended tail violate this assumption. Otherwise l <= r, finally
 413             // the case where the values are potentially equal needs to be considered
 414             // and false returned as well
 415             let mut equal = l_len == r_len;
 416             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 417                 if l > r {
 418                     return false
 419                 } else if l < r {
 420                     equal = false;
 421                 }
 422             }
 423             !equal
 424          } else {
 425             false
 426         }
 427     }
 428
 429     fn le(&self, other: &VClock) -> bool {
 430         // Load the values as slices
 431         let lhs_slice = self.as_slice();
 432         let rhs_slice = other.as_slice();
 433
 434         // If l_len > r_len then at least one element
 435         // in l_len is > than r_len, therefore the result
 436         // is either Some(Greater) or None, so return false
 437         // early.
 438         let l_len = lhs_slice.len();
 439         let r_len = rhs_slice.len();
 440         if l_len <= r_len {
 441             // If any elements on the left are greater than the right
 442             // then the result is None or Some(Greater), both of which
 443             // return false, the earlier test asserts that no elements in the
 444             // extended tail violate this assumption. Otherwise l <= r
 445             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l > r)
 446         } else {
 447             false
 448         }
 449     }
 450
 451     fn gt(&self, other: &VClock) -> bool {
 452         // Load the values as slices
 453         let lhs_slice = self.as_slice();
 454         let rhs_slice = other.as_slice();
 455
 456         // If r_len > l_len then at least one element
 457         // in r_len is > than l_len, therefore the result
 458         // is either Some(Less) or None, so return false
 459         // early.
 460         let l_len = lhs_slice.len();
 461         let r_len = rhs_slice.len();
 462         if l_len >= r_len {
 463             // If any elements on the left are less than the right
 464             // then the result is None or Some(Less), both of which
 465             // return false, the earlier test asserts that no elements in the
 466             // extended tail violate this assumption. Otherwise l >=, finally
 467             // the case where the values are potentially equal needs to be considered
 468             // and false returned as well
 469             let mut equal = l_len == r_len;
 470             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 471                 if l < r {
 472                     return false
 473                 } else if l > r {
 474                     equal = false;
 475                 }
 476             }
 477             !equal
 478         } else {
 479             false
 480         }
 481     }
 482
 483     fn ge(&self, other: &VClock) -> bool {
 484         // Load the values as slices
 485         let lhs_slice = self.as_slice();
 486         let rhs_slice = other.as_slice();
 487
 488         // If r_len > l_len then at least one element
 489         // in r_len is > than l_len, therefore the result
 490         // is either Some(Less) or None, so return false
 491         // early.
 492         let l_len = lhs_slice.len();
 493         let r_len = rhs_slice.len();
 494         if l_len >= r_len {
 495             // If any elements on the left are less than the right
 496             // then the result is None or Some(Less), both of which
 497             // return false, the earlier test asserts that no elements in the
 498             // extended tail violate this assumption. Otherwise l >= r
 499             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l < r)
 500         } else {
 501             false
 502         }
 503     }
 504
 505 }
 506
 507 impl Index<VectorIdx> for VClock {
 508
 509     type Output = VTimestamp;
 510
 511     #[inline]
 512     fn index(&self, index: VectorIdx) -> &VTimestamp {
 513        self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
 514     }
 515
 516 }
 517
 518
 519 /// Test vector clock ordering operations
 520 ///  data-race detection is tested in the external
 521 ///  test suite
 522 #[cfg(test)]
 523 mod tests {
 524
 525     use super::{VClock, VTimestamp, VectorIdx, VSmallClockMap};
 526     use std::cmp::Ordering;
 527
 528     #[test]
 529     fn test_equal() {
 530         let mut c1 = VClock::default();
 531         let mut c2 = VClock::default();
 532         assert_eq!(c1, c2);
 533         c1.increment_index(VectorIdx(5));
 534         assert_ne!(c1, c2);
 535         c2.increment_index(VectorIdx(53));
 536         assert_ne!(c1, c2);
 537         c1.increment_index(VectorIdx(53));
 538         assert_ne!(c1, c2);
 539         c2.increment_index(VectorIdx(5));
 540         assert_eq!(c1, c2);
 541     }
 542
 543     #[test]
 544     fn test_partial_order() {
 545         // Small test
 546         assert_order(&[1], &[1], Some(Ordering::Equal));
 547         assert_order(&[1], &[2], Some(Ordering::Less));
 548         assert_order(&[2], &[1], Some(Ordering::Greater));
 549         assert_order(&[1], &[1,2], Some(Ordering::Less));
 550         assert_order(&[2], &[1,2], None);
 551
 552         // Misc tests
 553         assert_order(&[400], &[0, 1], None);
 554
 555         // Large test
 556         assert_order(&[0,1,2,3,4,5,6,7,8,9,10], &[0,1,2,3,4,5,6,7,8,9,10,0,0,0], Some(Ordering::Equal));
 557         assert_order(&[0,1,2,3,4,5,6,7,8,9,10], &[0,1,2,3,4,5,6,7,8,9,10,0,1,0], Some(Ordering::Less));
 558         assert_order(&[0,1,2,3,4,5,6,7,8,9,11], &[0,1,2,3,4,5,6,7,8,9,10,0,0,0], Some(Ordering::Greater));
 559         assert_order(&[0,1,2,3,4,5,6,7,8,9,11], &[0,1,2,3,4,5,6,7,8,9,10,0,1,0], None);
 560         assert_order(&[0,1,2,3,4,5,6,7,8,9,9 ], &[0,1,2,3,4,5,6,7,8,9,10,0,0,0], Some(Ordering::Less));
 561         assert_order(&[0,1,2,3,4,5,6,7,8,9,9 ], &[0,1,2,3,4,5,6,7,8,9,10,0,1,0], Some(Ordering::Less));
 562     }
 563
 564     fn from_slice(mut slice: &[VTimestamp]) -> VClock {
 565         while let Some(0) = slice.last() {
 566             slice = &slice[..slice.len() - 1]
 567         }
 568         VClock(smallvec::SmallVec::from_slice(slice))
 569     }
 570
 571     fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
 572         let l = from_slice(l);
 573         let r = from_slice(r);
 574
 575         //Test partial_cmp
 576         let compare = l.partial_cmp(&r);
 577         assert_eq!(compare, o, "Invalid comparison\n l: {:?}\n r: {:?}",l,r);
 578         let alt_compare = r.partial_cmp(&l);
 579         assert_eq!(alt_compare, o.map(Ordering::reverse), "Invalid alt comparison\n l: {:?}\n r: {:?}",l,r);
 580
 581         //Test operators with faster implementations
 582         assert_eq!(
 583             matches!(compare,Some(Ordering::Less)), l < r,
 584             "Invalid (<):\n l: {:?}\n r: {:?}",l,r
 585         );
 586         assert_eq!(
 587             matches!(compare,Some(Ordering::Less) | Some(Ordering::Equal)), l <= r,
 588             "Invalid (<=):\n l: {:?}\n r: {:?}",l,r
 589         );
 590         assert_eq!(
 591             matches!(compare,Some(Ordering::Greater)), l > r,
 592             "Invalid (>):\n l: {:?}\n r: {:?}",l,r
 593         );
 594         assert_eq!(
 595             matches!(compare,Some(Ordering::Greater) | Some(Ordering::Equal)), l >= r,
 596             "Invalid (>=):\n l: {:?}\n r: {:?}",l,r
 597         );
 598         assert_eq!(
 599             matches!(alt_compare,Some(Ordering::Less)), r < l,
 600             "Invalid alt (<):\n l: {:?}\n r: {:?}",l,r
 601         );
 602         assert_eq!(
 603             matches!(alt_compare,Some(Ordering::Less) | Some(Ordering::Equal)), r <= l,
 604             "Invalid alt (<=):\n l: {:?}\n r: {:?}",l,r
 605         );
 606         assert_eq!(
 607             matches!(alt_compare,Some(Ordering::Greater)), r > l,
 608             "Invalid alt (>):\n l: {:?}\n r: {:?}",l,r
 609         );
 610         assert_eq!(
 611             matches!(alt_compare,Some(Ordering::Greater) | Some(Ordering::Equal)), r >= l,
 612             "Invalid alt (>=):\n l: {:?}\n r: {:?}",l,r
 613         );
 614     }
 615
 616     #[test]
 617     pub fn test_vclock_set() {
 618         let mut map = VSmallClockMap::default();
 619         let v1 = from_slice(&[3,0,1]);
 620         let v2 = from_slice(&[4,2,3]);
 621         let v3 = from_slice(&[4,8,3]);
 622         map.insert(VectorIdx(0), &v1);
 623         assert_eq!(map.get(VectorIdx(0)), Some(&v1));
 624         map.insert(VectorIdx(5), &v2);
 625         assert_eq!(map.get(VectorIdx(0)), Some(&v1));
 626         assert_eq!(map.get(VectorIdx(5)), Some(&v2));
 627         map.insert(VectorIdx(53), &v3);
 628         assert_eq!(map.get(VectorIdx(0)), Some(&v1));
 629         assert_eq!(map.get(VectorIdx(5)), Some(&v2));
 630         assert_eq!(map.get(VectorIdx(53)), Some(&v3));
 631         map.retain_index(VectorIdx(53));
 632         assert_eq!(map.get(VectorIdx(0)), None);
 633         assert_eq!(map.get(VectorIdx(5)), None);
 634         assert_eq!(map.get(VectorIdx(53)), Some(&v3));
 635         map.clear();
 636         assert_eq!(map.get(VectorIdx(0)), None);
 637         assert_eq!(map.get(VectorIdx(5)), None);
 638         assert_eq!(map.get(VectorIdx(53)), None);
 639         map.insert(VectorIdx(53), &v3);
 640         assert_eq!(map.get(VectorIdx(0)), None);
 641         assert_eq!(map.get(VectorIdx(5)), None);
 642         assert_eq!(map.get(VectorIdx(53)), Some(&v3));
 643     }
 644
 645 }