use crate::traits::{Crdt, CrdtError, CrdtReader};
use crate::vclock_capnp;
use capnp::message::{Builder, HeapAllocator, ReaderOptions};
use capnp::serialize;
use serde::{Deserialize, Serialize};
use std::collections::HashMap;
use std::hash::Hash;
use std::time::{Duration, SystemTime, UNIX_EPOCH};
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Default)]
pub struct VectorClock {
pub clocks: HashMap<String, (u64, u64)>,
}
impl Hash for VectorClock {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
let mut sorted: Vec<_> = self.clocks.iter().collect();
sorted.sort_by_key(|(node, _)| node.as_str());
for (node, (counter, ts)) in sorted {
node.hash(state);
counter.hash(state);
ts.hash(state);
}
}
}
impl VectorClock {
pub fn new() -> Self {
Self::default()
}
pub fn increment(&mut self, node_id: &str) -> (u64, u64) {
let now = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap_or_default()
.as_secs();
let entry = self
.clocks
.entry(node_id.to_string())
.and_modify(|(counter, timestamp)| {
*counter += 1;
*timestamp = now;
})
.or_insert((1, now));
*entry
}
pub fn merge(&mut self, other: &Self) {
for (node_id, &(other_counter, other_timestamp)) in &other.clocks {
self.clocks
.entry(node_id.clone())
.and_modify(|(counter, timestamp)| {
*counter = (*counter).max(other_counter);
*timestamp = (*timestamp).max(other_timestamp);
})
.or_insert((other_counter, other_timestamp));
}
}
pub fn happens_before(&self, other: &VectorClock) -> bool {
let mut strictly_less = false;
let mut all_nodes: Vec<_> = self.clocks.keys().collect();
for node in other.clocks.keys() {
if !self.clocks.contains_key(node) {
all_nodes.push(node);
}
}
for node_id in all_nodes {
let self_val = self.clocks.get(node_id).map(|(c, _)| *c).unwrap_or(0);
let other_val = other.clocks.get(node_id).map(|(c, _)| *c).unwrap_or(0);
if self_val > other_val {
return false;
}
if self_val < other_val {
strictly_less = true;
}
}
strictly_less
}
pub fn is_stable_for(&self, duration: Duration) -> bool {
if self.clocks.is_empty() {
return false;
}
let cutoff = SystemTime::now()
.checked_sub(duration)
.and_then(|t| t.duration_since(UNIX_EPOCH).ok())
.map(|d| d.as_secs())
.unwrap_or(0);
self.clocks.values().all(|(_, ts)| *ts < cutoff)
}
pub fn merge_reader(&mut self, reader: &VectorClockReader) -> Result<(), CrdtError> {
let msg_reader = serialize::read_message(reader.bytes, ReaderOptions::new())
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
let vclock = msg_reader
.get_root::<vclock_capnp::vector_clock::Reader>()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
let entries = vclock
.get_entries()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
for entry in entries {
let node_id = entry
.get_node_id()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?
.to_str()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
let other_counter = entry.get_logical_counter();
let other_timestamp = entry.get_epoch_seconds();
self.clocks
.entry(node_id.to_string())
.and_modify(|(counter, timestamp)| {
*counter = (*counter).max(other_counter);
*timestamp = (*timestamp).max(other_timestamp);
})
.or_insert((other_counter, other_timestamp));
}
Ok(())
}
}
pub struct VectorClockReader<'a> {
bytes: &'a [u8],
}
impl<'a> VectorClockReader<'a> {
pub fn new(bytes: &'a [u8]) -> Self {
Self { bytes }
}
fn to_vclock(&self) -> Result<VectorClock, CrdtError> {
let reader = serialize::read_message(self.bytes, ReaderOptions::new())
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
let vclock = reader
.get_root::<vclock_capnp::vector_clock::Reader>()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
let mut clocks = HashMap::new();
let entries = vclock
.get_entries()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
for entry in entries {
let node_id = entry
.get_node_id()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?
.to_string()
.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
clocks.insert(
node_id,
(entry.get_logical_counter(), entry.get_epoch_seconds()),
);
}
Ok(VectorClock { clocks })
}
}
impl<'a> CrdtReader<'a> for VectorClockReader<'a> {
fn is_empty(&self) -> Result<bool, CrdtError> {
Ok(self.to_vclock()?.clocks.is_empty())
}
}
impl Crdt for VectorClock {
type Reader<'a> = VectorClockReader<'a>;
fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError> {
let mut result = VectorClock::new();
for reader in readers {
result.merge(&reader.to_vclock()?);
}
Ok(result)
}
fn to_capnp_bytes(&self) -> Vec<u8> {
let mut message = Builder::new(HeapAllocator::new());
{
let mut vclock = message.init_root::<vclock_capnp::vector_clock::Builder>();
let mut entries = vclock.reborrow().init_entries(self.clocks.len() as u32);
for (idx, (node_id, (counter, ts))) in self.clocks.iter().enumerate() {
let mut entry = entries.reborrow().get(idx as u32);
entry.set_node_id(node_id.as_str().into());
entry.set_logical_counter(*counter);
entry.set_epoch_seconds(*ts);
}
}
let mut buf = Vec::new();
serialize::write_message(&mut buf, &message).expect("VectorClock serialization fail");
buf
}
fn is_empty(&self) -> bool {
self.clocks.is_empty()
}
fn validate(&self) -> Result<(), CrdtError> {
Ok(())
}
}