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 idx = idx.index();
 112         let mut_slice = self.get_mut_with_min_len(idx + 1);
 113         let slice = other.as_slice();
 114         mut_slice[idx] = slice[idx];
 115     }
 116
 117     /// Set the vector to the all-zero vector
 118     #[inline]
 119     pub fn set_zero_vector(&mut self) {
 120         self.0.clear();
 121     }
 122
 123     /// Return if this vector is the all-zero vector
 124     pub fn is_zero_vector(&self) -> bool {
 125         self.0.is_empty()
 126     }
 127 }
 128
 129 impl Clone for VClock {
 130     fn clone(&self) -> Self {
 131         VClock(self.0.clone())
 132     }
 133
 134     // Optimized clone-from, can be removed
 135     // and replaced with a derive once a similar
 136     // optimization is inserted into SmallVec's
 137     // clone implementation.
 138     fn clone_from(&mut self, source: &Self) {
 139         let source_slice = source.as_slice();
 140         self.0.clear();
 141         self.0.extend_from_slice(source_slice);
 142     }
 143 }
 144
 145 impl PartialOrd for VClock {
 146     fn partial_cmp(&self, other: &VClock) -> Option<Ordering> {
 147         // Load the values as slices
 148         let lhs_slice = self.as_slice();
 149         let rhs_slice = other.as_slice();
 150
 151         // Iterate through the combined vector slice continuously updating
 152         // the value of `order` to the current comparison of the vector from
 153         // index 0 to the currently checked index.
 154         // An Equal ordering can be converted into Less or Greater ordering
 155         // on finding an element that is less than or greater than the other
 156         // but if one Greater and one Less element-wise comparison is found
 157         // then no ordering is possible and so directly return an ordering
 158         // of None.
 159         let mut iter = lhs_slice.iter().zip(rhs_slice.iter());
 160         let mut order = match iter.next() {
 161             Some((lhs, rhs)) => lhs.cmp(rhs),
 162             None => Ordering::Equal,
 163         };
 164         for (l, r) in iter {
 165             match order {
 166                 Ordering::Equal => order = l.cmp(r),
 167                 Ordering::Less =>
 168                     if l > r {
 169                         return None;
 170                     },
 171                 Ordering::Greater =>
 172                     if l < r {
 173                         return None;
 174                     },
 175             }
 176         }
 177
 178         // Now test if either left or right have trailing elements,
 179         // by the invariant the trailing elements have at least 1
 180         // non zero value, so no additional calculation is required
 181         // to determine the result of the PartialOrder.
 182         let l_len = lhs_slice.len();
 183         let r_len = rhs_slice.len();
 184         match l_len.cmp(&r_len) {
 185             // Equal means no additional elements: return current order
 186             Ordering::Equal => Some(order),
 187             // Right has at least 1 element > than the implicit 0,
 188             // so the only valid values are Ordering::Less or None.
 189             Ordering::Less =>
 190                 match order {
 191                     Ordering::Less | Ordering::Equal => Some(Ordering::Less),
 192                     Ordering::Greater => None,
 193                 },
 194             // Left has at least 1 element > than the implicit 0,
 195             // so the only valid values are Ordering::Greater or None.
 196             Ordering::Greater =>
 197                 match order {
 198                     Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
 199                     Ordering::Less => None,
 200                 },
 201         }
 202     }
 203
 204     fn lt(&self, other: &VClock) -> bool {
 205         // Load the values as slices
 206         let lhs_slice = self.as_slice();
 207         let rhs_slice = other.as_slice();
 208
 209         // If l_len > r_len then at least one element
 210         // in l_len is > than r_len, therefore the result
 211         // is either Some(Greater) or None, so return false
 212         // early.
 213         let l_len = lhs_slice.len();
 214         let r_len = rhs_slice.len();
 215         if l_len <= r_len {
 216             // If any elements on the left are greater than the right
 217             // then the result is None or Some(Greater), both of which
 218             // return false, the earlier test asserts that no elements in the
 219             // extended tail violate this assumption. Otherwise l <= r, finally
 220             // the case where the values are potentially equal needs to be considered
 221             // and false returned as well
 222             let mut equal = l_len == r_len;
 223             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 224                 if l > r {
 225                     return false;
 226                 } else if l < r {
 227                     equal = false;
 228                 }
 229             }
 230             !equal
 231         } else {
 232             false
 233         }
 234     }
 235
 236     fn le(&self, other: &VClock) -> bool {
 237         // Load the values as slices
 238         let lhs_slice = self.as_slice();
 239         let rhs_slice = other.as_slice();
 240
 241         // If l_len > r_len then at least one element
 242         // in l_len is > than r_len, therefore the result
 243         // is either Some(Greater) or None, so return false
 244         // early.
 245         let l_len = lhs_slice.len();
 246         let r_len = rhs_slice.len();
 247         if l_len <= r_len {
 248             // If any elements on the left are greater than the right
 249             // then the result is None or Some(Greater), both of which
 250             // return false, the earlier test asserts that no elements in the
 251             // extended tail violate this assumption. Otherwise l <= r
 252             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l > r)
 253         } else {
 254             false
 255         }
 256     }
 257
 258     fn gt(&self, other: &VClock) -> bool {
 259         // Load the values as slices
 260         let lhs_slice = self.as_slice();
 261         let rhs_slice = other.as_slice();
 262
 263         // If r_len > l_len then at least one element
 264         // in r_len is > than l_len, therefore the result
 265         // is either Some(Less) or None, so return false
 266         // early.
 267         let l_len = lhs_slice.len();
 268         let r_len = rhs_slice.len();
 269         if l_len >= r_len {
 270             // If any elements on the left are less than the right
 271             // then the result is None or Some(Less), both of which
 272             // return false, the earlier test asserts that no elements in the
 273             // extended tail violate this assumption. Otherwise l >=, finally
 274             // the case where the values are potentially equal needs to be considered
 275             // and false returned as well
 276             let mut equal = l_len == r_len;
 277             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 278                 if l < r {
 279                     return false;
 280                 } else if l > r {
 281                     equal = false;
 282                 }
 283             }
 284             !equal
 285         } else {
 286             false
 287         }
 288     }
 289
 290     fn ge(&self, other: &VClock) -> bool {
 291         // Load the values as slices
 292         let lhs_slice = self.as_slice();
 293         let rhs_slice = other.as_slice();
 294
 295         // If r_len > l_len then at least one element
 296         // in r_len is > than l_len, therefore the result
 297         // is either Some(Less) or None, so return false
 298         // early.
 299         let l_len = lhs_slice.len();
 300         let r_len = rhs_slice.len();
 301         if l_len >= r_len {
 302             // If any elements on the left are less than the right
 303             // then the result is None or Some(Less), both of which
 304             // return false, the earlier test asserts that no elements in the
 305             // extended tail violate this assumption. Otherwise l >= r
 306             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l < r)
 307         } else {
 308             false
 309         }
 310     }
 311 }
 312
 313 impl Index<VectorIdx> for VClock {
 314     type Output = VTimestamp;
 315
 316     #[inline]
 317     fn index(&self, index: VectorIdx) -> &VTimestamp {
 318         self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
 319     }
 320 }
 321
 322 /// Test vector clock ordering operations
 323 ///  data-race detection is tested in the external
 324 ///  test suite
 325 #[cfg(test)]
 326 mod tests {
 327
 328     use super::{VClock, VTimestamp, VectorIdx};
 329     use std::cmp::Ordering;
 330
 331     #[test]
 332     fn test_equal() {
 333         let mut c1 = VClock::default();
 334         let mut c2 = VClock::default();
 335         assert_eq!(c1, c2);
 336         c1.increment_index(VectorIdx(5));
 337         assert_ne!(c1, c2);
 338         c2.increment_index(VectorIdx(53));
 339         assert_ne!(c1, c2);
 340         c1.increment_index(VectorIdx(53));
 341         assert_ne!(c1, c2);
 342         c2.increment_index(VectorIdx(5));
 343         assert_eq!(c1, c2);
 344     }
 345
 346     #[test]
 347     fn test_partial_order() {
 348         // Small test
 349         assert_order(&[1], &[1], Some(Ordering::Equal));
 350         assert_order(&[1], &[2], Some(Ordering::Less));
 351         assert_order(&[2], &[1], Some(Ordering::Greater));
 352         assert_order(&[1], &[1, 2], Some(Ordering::Less));
 353         assert_order(&[2], &[1, 2], None);
 354
 355         // Misc tests
 356         assert_order(&[400], &[0, 1], None);
 357
 358         // Large test
 359         assert_order(
 360             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 361             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 362             Some(Ordering::Equal),
 363         );
 364         assert_order(
 365             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 366             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 367             Some(Ordering::Less),
 368         );
 369         assert_order(
 370             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 371             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 372             Some(Ordering::Greater),
 373         );
 374         assert_order(
 375             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 376             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 377             None,
 378         );
 379         assert_order(
 380             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 381             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 382             Some(Ordering::Less),
 383         );
 384         assert_order(
 385             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 386             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 387             Some(Ordering::Less),
 388         );
 389     }
 390
 391     fn from_slice(mut slice: &[VTimestamp]) -> VClock {
 392         while let Some(0) = slice.last() {
 393             slice = &slice[..slice.len() - 1]
 394         }
 395         VClock(smallvec::SmallVec::from_slice(slice))
 396     }
 397
 398     fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
 399         let l = from_slice(l);
 400         let r = from_slice(r);
 401
 402         //Test partial_cmp
 403         let compare = l.partial_cmp(&r);
 404         assert_eq!(compare, o, "Invalid comparison\n l: {:?}\n r: {:?}", l, r);
 405         let alt_compare = r.partial_cmp(&l);
 406         assert_eq!(
 407             alt_compare,
 408             o.map(Ordering::reverse),
 409             "Invalid alt comparison\n l: {:?}\n r: {:?}",
 410             l,
 411             r
 412         );
 413
 414         //Test operators with faster implementations
 415         assert_eq!(
 416             matches!(compare, Some(Ordering::Less)),
 417             l < r,
 418             "Invalid (<):\n l: {:?}\n r: {:?}",
 419             l,
 420             r
 421         );
 422         assert_eq!(
 423             matches!(compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 424             l <= r,
 425             "Invalid (<=):\n l: {:?}\n r: {:?}",
 426             l,
 427             r
 428         );
 429         assert_eq!(
 430             matches!(compare, Some(Ordering::Greater)),
 431             l > r,
 432             "Invalid (>):\n l: {:?}\n r: {:?}",
 433             l,
 434             r
 435         );
 436         assert_eq!(
 437             matches!(compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 438             l >= r,
 439             "Invalid (>=):\n l: {:?}\n r: {:?}",
 440             l,
 441             r
 442         );
 443         assert_eq!(
 444             matches!(alt_compare, Some(Ordering::Less)),
 445             r < l,
 446             "Invalid alt (<):\n l: {:?}\n r: {:?}",
 447             l,
 448             r
 449         );
 450         assert_eq!(
 451             matches!(alt_compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 452             r <= l,
 453             "Invalid alt (<=):\n l: {:?}\n r: {:?}",
 454             l,
 455             r
 456         );
 457         assert_eq!(
 458             matches!(alt_compare, Some(Ordering::Greater)),
 459             r > l,
 460             "Invalid alt (>):\n l: {:?}\n r: {:?}",
 461             l,
 462             r
 463         );
 464         assert_eq!(
 465             matches!(alt_compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 466             r >= l,
 467             "Invalid alt (>=):\n l: {:?}\n r: {:?}",
 468             l,
 469             r
 470         );
 471     }
 472 }