1 use rustc_index::vec::Idx;
2 use smallvec::SmallVec;
3 use std::{cmp::Ordering, convert::TryFrom, fmt::Debug, ops::Index};
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);
13 pub fn to_u32(self) -> u32 {
17 pub const MAX_INDEX: VectorIdx = VectorIdx(u32::MAX);
20 impl Idx for VectorIdx {
22 fn new(idx: usize) -> Self {
23 VectorIdx(u32::try_from(idx).unwrap())
27 fn index(self) -> usize {
28 usize::try_from(self.0).unwrap()
32 impl From<u32> for VectorIdx {
34 fn from(id: u32) -> Self {
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;
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;
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]>);
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;
70 /// Load the internal timestamp slice in the vector clock
72 pub fn as_slice(&self) -> &[VTimestamp] {
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
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);
84 assert!(self.0.len() >= min_len);
88 /// Increment the vector clock at a known index
89 /// this will panic if the vector index overflows
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")
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()) {
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];
117 /// Set the vector to the all-zero vector
119 pub fn set_zero_vector(&mut self) {
123 /// Return if this vector is the all-zero vector
124 pub fn is_zero_vector(&self) -> bool {
129 impl Clone for VClock {
130 fn clone(&self) -> Self {
131 VClock(self.0.clone())
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();
141 self.0.extend_from_slice(source_slice);
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();
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
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,
166 Ordering::Equal => order = l.cmp(r),
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.
191 Ordering::Less | Ordering::Equal => Some(Ordering::Less),
192 Ordering::Greater => None,
194 // Left has at least 1 element > than the implicit 0,
195 // so the only valid values are Ordering::Greater or None.
198 Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
199 Ordering::Less => None,
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();
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
213 let l_len = lhs_slice.len();
214 let r_len = rhs_slice.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()) {
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();
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
245 let l_len = lhs_slice.len();
246 let r_len = rhs_slice.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)
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();
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
267 let l_len = lhs_slice.len();
268 let r_len = rhs_slice.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()) {
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();
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
299 let l_len = lhs_slice.len();
300 let r_len = rhs_slice.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)
313 impl Index<VectorIdx> for VClock {
314 type Output = VTimestamp;
317 fn index(&self, index: VectorIdx) -> &VTimestamp {
318 self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
322 /// Test vector clock ordering operations
323 /// data-race detection is tested in the external
328 use super::{VClock, VTimestamp, VectorIdx};
329 use std::cmp::Ordering;
333 let mut c1 = VClock::default();
334 let mut c2 = VClock::default();
336 c1.increment_index(VectorIdx(5));
338 c2.increment_index(VectorIdx(53));
340 c1.increment_index(VectorIdx(53));
342 c2.increment_index(VectorIdx(5));
347 fn test_partial_order() {
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);
356 assert_order(&[400], &[0, 1], None);
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),
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),
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),
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],
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),
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),
391 fn from_slice(mut slice: &[VTimestamp]) -> VClock {
392 while let Some(0) = slice.last() {
393 slice = &slice[..slice.len() - 1]
395 VClock(smallvec::SmallVec::from_slice(slice))
398 fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
399 let l = from_slice(l);
400 let r = from_slice(r);
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);
408 o.map(Ordering::reverse),
409 "Invalid alt comparison\n l: {:?}\n r: {:?}",
414 //Test operators with faster implementations
416 matches!(compare, Some(Ordering::Less)),
418 "Invalid (<):\n l: {:?}\n r: {:?}",
423 matches!(compare, Some(Ordering::Less) | Some(Ordering::Equal)),
425 "Invalid (<=):\n l: {:?}\n r: {:?}",
430 matches!(compare, Some(Ordering::Greater)),
432 "Invalid (>):\n l: {:?}\n r: {:?}",
437 matches!(compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
439 "Invalid (>=):\n l: {:?}\n r: {:?}",
444 matches!(alt_compare, Some(Ordering::Less)),
446 "Invalid alt (<):\n l: {:?}\n r: {:?}",
451 matches!(alt_compare, Some(Ordering::Less) | Some(Ordering::Equal)),
453 "Invalid alt (<=):\n l: {:?}\n r: {:?}",
458 matches!(alt_compare, Some(Ordering::Greater)),
460 "Invalid alt (>):\n l: {:?}\n r: {:?}",
465 matches!(alt_compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
467 "Invalid alt (>=):\n l: {:?}\n r: {:?}",