1 use rustc_index::vec::Idx;
2 use smallvec::SmallVec;
3 use std::{cmp::Ordering, 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 mut_slice = self.get_mut_with_min_len(idx.index() + 1);
112 mut_slice[idx.index()] = other[idx];
115 /// Set the vector to the all-zero vector
117 pub fn set_zero_vector(&mut self) {
121 /// Return if this vector is the all-zero vector
122 pub fn is_zero_vector(&self) -> bool {
127 impl Clone for VClock {
128 fn clone(&self) -> Self {
129 VClock(self.0.clone())
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();
139 self.0.extend_from_slice(source_slice);
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();
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
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,
164 Ordering::Equal => order = l.cmp(r),
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.
189 Ordering::Less | Ordering::Equal => Some(Ordering::Less),
190 Ordering::Greater => None,
192 // Left has at least 1 element > than the implicit 0,
193 // so the only valid values are Ordering::Greater or None.
196 Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
197 Ordering::Less => None,
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();
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
211 let l_len = lhs_slice.len();
212 let r_len = rhs_slice.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()) {
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();
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
243 let l_len = lhs_slice.len();
244 let r_len = rhs_slice.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)
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();
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
265 let l_len = lhs_slice.len();
266 let r_len = rhs_slice.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()) {
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();
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
297 let l_len = lhs_slice.len();
298 let r_len = rhs_slice.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)
311 impl Index<VectorIdx> for VClock {
312 type Output = VTimestamp;
315 fn index(&self, index: VectorIdx) -> &VTimestamp {
316 self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
320 /// Test vector clock ordering operations
321 /// data-race detection is tested in the external
326 use super::{VClock, VTimestamp, VectorIdx};
327 use std::cmp::Ordering;
331 let mut c1 = VClock::default();
332 let mut c2 = VClock::default();
334 c1.increment_index(VectorIdx(5));
336 c2.increment_index(VectorIdx(53));
338 c1.increment_index(VectorIdx(53));
340 c2.increment_index(VectorIdx(5));
345 fn test_partial_order() {
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);
354 assert_order(&[400], &[0, 1], None);
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),
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),
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),
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],
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),
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),
389 fn from_slice(mut slice: &[VTimestamp]) -> VClock {
390 while let Some(0) = slice.last() {
391 slice = &slice[..slice.len() - 1]
393 VClock(smallvec::SmallVec::from_slice(slice))
396 fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
397 let l = from_slice(l);
398 let r = from_slice(r);
401 let compare = l.partial_cmp(&r);
402 assert_eq!(compare, o, "Invalid comparison\n l: {l:?}\n r: {r:?}");
403 let alt_compare = r.partial_cmp(&l);
406 o.map(Ordering::reverse),
407 "Invalid alt comparison\n l: {:?}\n r: {:?}",
412 //Test operators with faster implementations
414 matches!(compare, Some(Ordering::Less)),
416 "Invalid (<):\n l: {:?}\n r: {:?}",
421 matches!(compare, Some(Ordering::Less) | Some(Ordering::Equal)),
423 "Invalid (<=):\n l: {:?}\n r: {:?}",
428 matches!(compare, Some(Ordering::Greater)),
430 "Invalid (>):\n l: {:?}\n r: {:?}",
435 matches!(compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
437 "Invalid (>=):\n l: {:?}\n r: {:?}",
442 matches!(alt_compare, Some(Ordering::Less)),
444 "Invalid alt (<):\n l: {:?}\n r: {:?}",
449 matches!(alt_compare, Some(Ordering::Less) | Some(Ordering::Equal)),
451 "Invalid alt (<=):\n l: {:?}\n r: {:?}",
456 matches!(alt_compare, Some(Ordering::Greater)),
458 "Invalid alt (>):\n l: {:?}\n r: {:?}",
463 matches!(alt_compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
465 "Invalid alt (>=):\n l: {:?}\n r: {:?}",