src/vector_clock.rs

   1 use rustc_index::vec::Idx;
   2 use smallvec::SmallVec;
   3 use std::{cmp::Ordering, fmt::Debug, ops::Index};
   4
   5 /// A vector clock index, this is associated with a thread id
   6 /// but in some cases one vector index may be shared with
   7 /// multiple thread ids if it safe to do so.
   8 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
   9 pub struct VectorIdx(u32);
  10
  11 impl VectorIdx {
  12     #[inline(always)]
  13     pub fn to_u32(self) -> u32 {
  14         self.0
  15     }
  16
  17     pub const MAX_INDEX: VectorIdx = VectorIdx(u32::MAX);
  18 }
  19
  20 impl Idx for VectorIdx {
  21     #[inline]
  22     fn new(idx: usize) -> Self {
  23         VectorIdx(u32::try_from(idx).unwrap())
  24     }
  25
  26     #[inline]
  27     fn index(self) -> usize {
  28         usize::try_from(self.0).unwrap()
  29     }
  30 }
  31
  32 impl From<u32> for VectorIdx {
  33     #[inline]
  34     fn from(id: u32) -> Self {
  35         Self(id)
  36     }
  37 }
  38
  39 /// The size of the vector-clock to store inline
  40 /// clock vectors larger than this will be stored on the heap
  41 const SMALL_VECTOR: usize = 4;
  42
  43 /// The type of the time-stamps recorded in the data-race detector
  44 /// set to a type of unsigned integer
  45 pub type VTimestamp = u32;
  46
  47 /// A vector clock for detecting data-races, this is conceptually
  48 /// a map from a vector index (and thus a thread id) to a timestamp.
  49 /// The compare operations require that the invariant that the last
  50 /// element in the internal timestamp slice must not be a 0, hence
  51 /// all zero vector clocks are always represented by the empty slice;
  52 /// and allows for the implementation of compare operations to short
  53 /// circuit the calculation and return the correct result faster,
  54 /// also this means that there is only one unique valid length
  55 /// for each set of vector clock values and hence the PartialEq
  56 //  and Eq derivations are correct.
  57 #[derive(PartialEq, Eq, Default, Debug)]
  58 pub struct VClock(SmallVec<[VTimestamp; SMALL_VECTOR]>);
  59
  60 impl VClock {
  61     /// Create a new vector-clock containing all zeros except
  62     /// for a value at the given index
  63     pub fn new_with_index(index: VectorIdx, timestamp: VTimestamp) -> VClock {
  64         let len = index.index() + 1;
  65         let mut vec = smallvec::smallvec![0; len];
  66         vec[index.index()] = timestamp;
  67         VClock(vec)
  68     }
  69
  70     /// Load the internal timestamp slice in the vector clock
  71     #[inline]
  72     pub fn as_slice(&self) -> &[VTimestamp] {
  73         self.0.as_slice()
  74     }
  75
  76     /// Get a mutable slice to the internal vector with minimum `min_len`
  77     /// elements, to preserve invariants this vector must modify
  78     /// the `min_len`-1 nth element to a non-zero value
  79     #[inline]
  80     fn get_mut_with_min_len(&mut self, min_len: usize) -> &mut [VTimestamp] {
  81         if self.0.len() < min_len {
  82             self.0.resize(min_len, 0);
  83         }
  84         assert!(self.0.len() >= min_len);
  85         self.0.as_mut_slice()
  86     }
  87
  88     /// Increment the vector clock at a known index
  89     /// this will panic if the vector index overflows
  90     #[inline]
  91     pub fn increment_index(&mut self, idx: VectorIdx) {
  92         let idx = idx.index();
  93         let mut_slice = self.get_mut_with_min_len(idx + 1);
  94         let idx_ref = &mut mut_slice[idx];
  95         *idx_ref = idx_ref.checked_add(1).expect("Vector clock overflow")
  96     }
  97
  98     // Join the two vector-clocks together, this
  99     // sets each vector-element to the maximum value
 100     // of that element in either of the two source elements.
 101     pub fn join(&mut self, other: &Self) {
 102         let rhs_slice = other.as_slice();
 103         let lhs_slice = self.get_mut_with_min_len(rhs_slice.len());
 104         for (l, &r) in lhs_slice.iter_mut().zip(rhs_slice.iter()) {
 105             *l = r.max(*l);
 106         }
 107     }
 108
 109     /// Set the element at the current index of the vector
 110     pub fn set_at_index(&mut self, other: &Self, idx: VectorIdx) {
 111         let mut_slice = self.get_mut_with_min_len(idx.index() + 1);
 112         mut_slice[idx.index()] = other[idx];
 113     }
 114
 115     /// Set the vector to the all-zero vector
 116     #[inline]
 117     pub fn set_zero_vector(&mut self) {
 118         self.0.clear();
 119     }
 120
 121     /// Return if this vector is the all-zero vector
 122     pub fn is_zero_vector(&self) -> bool {
 123         self.0.is_empty()
 124     }
 125 }
 126
 127 impl Clone for VClock {
 128     fn clone(&self) -> Self {
 129         VClock(self.0.clone())
 130     }
 131
 132     // Optimized clone-from, can be removed
 133     // and replaced with a derive once a similar
 134     // optimization is inserted into SmallVec's
 135     // clone implementation.
 136     fn clone_from(&mut self, source: &Self) {
 137         let source_slice = source.as_slice();
 138         self.0.clear();
 139         self.0.extend_from_slice(source_slice);
 140     }
 141 }
 142
 143 impl PartialOrd for VClock {
 144     fn partial_cmp(&self, other: &VClock) -> Option<Ordering> {
 145         // Load the values as slices
 146         let lhs_slice = self.as_slice();
 147         let rhs_slice = other.as_slice();
 148
 149         // Iterate through the combined vector slice continuously updating
 150         // the value of `order` to the current comparison of the vector from
 151         // index 0 to the currently checked index.
 152         // An Equal ordering can be converted into Less or Greater ordering
 153         // on finding an element that is less than or greater than the other
 154         // but if one Greater and one Less element-wise comparison is found
 155         // then no ordering is possible and so directly return an ordering
 156         // of None.
 157         let mut iter = lhs_slice.iter().zip(rhs_slice.iter());
 158         let mut order = match iter.next() {
 159             Some((lhs, rhs)) => lhs.cmp(rhs),
 160             None => Ordering::Equal,
 161         };
 162         for (l, r) in iter {
 163             match order {
 164                 Ordering::Equal => order = l.cmp(r),
 165                 Ordering::Less =>
 166                     if l > r {
 167                         return None;
 168                     },
 169                 Ordering::Greater =>
 170                     if l < r {
 171                         return None;
 172                     },
 173             }
 174         }
 175
 176         // Now test if either left or right have trailing elements,
 177         // by the invariant the trailing elements have at least 1
 178         // non zero value, so no additional calculation is required
 179         // to determine the result of the PartialOrder.
 180         let l_len = lhs_slice.len();
 181         let r_len = rhs_slice.len();
 182         match l_len.cmp(&r_len) {
 183             // Equal means no additional elements: return current order
 184             Ordering::Equal => Some(order),
 185             // Right has at least 1 element > than the implicit 0,
 186             // so the only valid values are Ordering::Less or None.
 187             Ordering::Less =>
 188                 match order {
 189                     Ordering::Less | Ordering::Equal => Some(Ordering::Less),
 190                     Ordering::Greater => None,
 191                 },
 192             // Left has at least 1 element > than the implicit 0,
 193             // so the only valid values are Ordering::Greater or None.
 194             Ordering::Greater =>
 195                 match order {
 196                     Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
 197                     Ordering::Less => None,
 198                 },
 199         }
 200     }
 201
 202     fn lt(&self, other: &VClock) -> bool {
 203         // Load the values as slices
 204         let lhs_slice = self.as_slice();
 205         let rhs_slice = other.as_slice();
 206
 207         // If l_len > r_len then at least one element
 208         // in l_len is > than r_len, therefore the result
 209         // is either Some(Greater) or None, so return false
 210         // early.
 211         let l_len = lhs_slice.len();
 212         let r_len = rhs_slice.len();
 213         if l_len <= r_len {
 214             // If any elements on the left are greater than the right
 215             // then the result is None or Some(Greater), both of which
 216             // return false, the earlier test asserts that no elements in the
 217             // extended tail violate this assumption. Otherwise l <= r, finally
 218             // the case where the values are potentially equal needs to be considered
 219             // and false returned as well
 220             let mut equal = l_len == r_len;
 221             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 222                 if l > r {
 223                     return false;
 224                 } else if l < r {
 225                     equal = false;
 226                 }
 227             }
 228             !equal
 229         } else {
 230             false
 231         }
 232     }
 233
 234     fn le(&self, other: &VClock) -> bool {
 235         // Load the values as slices
 236         let lhs_slice = self.as_slice();
 237         let rhs_slice = other.as_slice();
 238
 239         // If l_len > r_len then at least one element
 240         // in l_len is > than r_len, therefore the result
 241         // is either Some(Greater) or None, so return false
 242         // early.
 243         let l_len = lhs_slice.len();
 244         let r_len = rhs_slice.len();
 245         if l_len <= r_len {
 246             // If any elements on the left are greater than the right
 247             // then the result is None or Some(Greater), both of which
 248             // return false, the earlier test asserts that no elements in the
 249             // extended tail violate this assumption. Otherwise l <= r
 250             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l > r)
 251         } else {
 252             false
 253         }
 254     }
 255
 256     fn gt(&self, other: &VClock) -> bool {
 257         // Load the values as slices
 258         let lhs_slice = self.as_slice();
 259         let rhs_slice = other.as_slice();
 260
 261         // If r_len > l_len then at least one element
 262         // in r_len is > than l_len, therefore the result
 263         // is either Some(Less) or None, so return false
 264         // early.
 265         let l_len = lhs_slice.len();
 266         let r_len = rhs_slice.len();
 267         if l_len >= r_len {
 268             // If any elements on the left are less than the right
 269             // then the result is None or Some(Less), both of which
 270             // return false, the earlier test asserts that no elements in the
 271             // extended tail violate this assumption. Otherwise l >=, finally
 272             // the case where the values are potentially equal needs to be considered
 273             // and false returned as well
 274             let mut equal = l_len == r_len;
 275             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 276                 if l < r {
 277                     return false;
 278                 } else if l > r {
 279                     equal = false;
 280                 }
 281             }
 282             !equal
 283         } else {
 284             false
 285         }
 286     }
 287
 288     fn ge(&self, other: &VClock) -> bool {
 289         // Load the values as slices
 290         let lhs_slice = self.as_slice();
 291         let rhs_slice = other.as_slice();
 292
 293         // If r_len > l_len then at least one element
 294         // in r_len is > than l_len, therefore the result
 295         // is either Some(Less) or None, so return false
 296         // early.
 297         let l_len = lhs_slice.len();
 298         let r_len = rhs_slice.len();
 299         if l_len >= r_len {
 300             // If any elements on the left are less than the right
 301             // then the result is None or Some(Less), both of which
 302             // return false, the earlier test asserts that no elements in the
 303             // extended tail violate this assumption. Otherwise l >= r
 304             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l < r)
 305         } else {
 306             false
 307         }
 308     }
 309 }
 310
 311 impl Index<VectorIdx> for VClock {
 312     type Output = VTimestamp;
 313
 314     #[inline]
 315     fn index(&self, index: VectorIdx) -> &VTimestamp {
 316         self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
 317     }
 318 }
 319
 320 /// Test vector clock ordering operations
 321 ///  data-race detection is tested in the external
 322 ///  test suite
 323 #[cfg(test)]
 324 mod tests {
 325
 326     use super::{VClock, VTimestamp, VectorIdx};
 327     use std::cmp::Ordering;
 328
 329     #[test]
 330     fn test_equal() {
 331         let mut c1 = VClock::default();
 332         let mut c2 = VClock::default();
 333         assert_eq!(c1, c2);
 334         c1.increment_index(VectorIdx(5));
 335         assert_ne!(c1, c2);
 336         c2.increment_index(VectorIdx(53));
 337         assert_ne!(c1, c2);
 338         c1.increment_index(VectorIdx(53));
 339         assert_ne!(c1, c2);
 340         c2.increment_index(VectorIdx(5));
 341         assert_eq!(c1, c2);
 342     }
 343
 344     #[test]
 345     fn test_partial_order() {
 346         // Small test
 347         assert_order(&[1], &[1], Some(Ordering::Equal));
 348         assert_order(&[1], &[2], Some(Ordering::Less));
 349         assert_order(&[2], &[1], Some(Ordering::Greater));
 350         assert_order(&[1], &[1, 2], Some(Ordering::Less));
 351         assert_order(&[2], &[1, 2], None);
 352
 353         // Misc tests
 354         assert_order(&[400], &[0, 1], None);
 355
 356         // Large test
 357         assert_order(
 358             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 359             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 360             Some(Ordering::Equal),
 361         );
 362         assert_order(
 363             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 364             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 365             Some(Ordering::Less),
 366         );
 367         assert_order(
 368             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 369             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 370             Some(Ordering::Greater),
 371         );
 372         assert_order(
 373             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 374             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 375             None,
 376         );
 377         assert_order(
 378             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 379             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 380             Some(Ordering::Less),
 381         );
 382         assert_order(
 383             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 384             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 385             Some(Ordering::Less),
 386         );
 387     }
 388
 389     fn from_slice(mut slice: &[VTimestamp]) -> VClock {
 390         while let Some(0) = slice.last() {
 391             slice = &slice[..slice.len() - 1]
 392         }
 393         VClock(smallvec::SmallVec::from_slice(slice))
 394     }
 395
 396     fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
 397         let l = from_slice(l);
 398         let r = from_slice(r);
 399
 400         //Test partial_cmp
 401         let compare = l.partial_cmp(&r);
 402         assert_eq!(compare, o, "Invalid comparison\n l: {:?}\n r: {:?}", l, r);
 403         let alt_compare = r.partial_cmp(&l);
 404         assert_eq!(
 405             alt_compare,
 406             o.map(Ordering::reverse),
 407             "Invalid alt comparison\n l: {:?}\n r: {:?}",
 408             l,
 409             r
 410         );
 411
 412         //Test operators with faster implementations
 413         assert_eq!(
 414             matches!(compare, Some(Ordering::Less)),
 415             l < r,
 416             "Invalid (<):\n l: {:?}\n r: {:?}",
 417             l,
 418             r
 419         );
 420         assert_eq!(
 421             matches!(compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 422             l <= r,
 423             "Invalid (<=):\n l: {:?}\n r: {:?}",
 424             l,
 425             r
 426         );
 427         assert_eq!(
 428             matches!(compare, Some(Ordering::Greater)),
 429             l > r,
 430             "Invalid (>):\n l: {:?}\n r: {:?}",
 431             l,
 432             r
 433         );
 434         assert_eq!(
 435             matches!(compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 436             l >= r,
 437             "Invalid (>=):\n l: {:?}\n r: {:?}",
 438             l,
 439             r
 440         );
 441         assert_eq!(
 442             matches!(alt_compare, Some(Ordering::Less)),
 443             r < l,
 444             "Invalid alt (<):\n l: {:?}\n r: {:?}",
 445             l,
 446             r
 447         );
 448         assert_eq!(
 449             matches!(alt_compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 450             r <= l,
 451             "Invalid alt (<=):\n l: {:?}\n r: {:?}",
 452             l,
 453             r
 454         );
 455         assert_eq!(
 456             matches!(alt_compare, Some(Ordering::Greater)),
 457             r > l,
 458             "Invalid alt (>):\n l: {:?}\n r: {:?}",
 459             l,
 460             r
 461         );
 462         assert_eq!(
 463             matches!(alt_compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 464             r >= l,
 465             "Invalid alt (>=):\n l: {:?}\n r: {:?}",
 466             l,
 467             r
 468         );
 469     }
 470 }