use std::collections::{BTreeSet, VecDeque};
use super::log::Journal;
use super::seq::Seq;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum CausalError {
UnknownParent(Seq),
}
impl<T> Journal<T> {
pub fn append_caused_by(
&mut self,
causes: impl IntoIterator<Item = Seq>,
entry: T,
) -> Result<Seq, CausalError> {
let next = self.next_seq();
let mut parents: BTreeSet<Seq> = BTreeSet::new();
for cause in causes {
if cause.index() >= next.index() {
return Err(CausalError::UnknownParent(cause));
}
parents.insert(cause);
}
let seq = self.append(entry);
self.set_parents(seq, parents.into_iter().collect());
Ok(seq)
}
pub fn parents(&self, seq: Seq) -> &[Seq] {
self.parents_of(seq)
}
pub fn roots(&self) -> impl Iterator<Item = Seq> + '_ {
(0..self.len())
.map(|i| Seq(i as u64))
.filter(|s| self.parents(*s).is_empty())
}
pub fn causes(&self, seq: Seq) -> Vec<Seq> {
let mut seen = BTreeSet::new();
let mut queue: VecDeque<Seq> = self.parents(seq).iter().copied().collect();
let mut order = Vec::new();
while let Some(current) = queue.pop_front() {
if !seen.insert(current) {
continue;
}
order.push(current);
queue.extend(self.parents(current).iter().copied());
}
order
}
pub fn effects(&self, seq: Seq) -> Vec<Seq> {
let mut reached = BTreeSet::new();
reached.insert(seq);
for index in seq.index() + 1..self.len() {
let at = Seq(index as u64);
if self.parents(at).iter().any(|p| reached.contains(p)) {
reached.insert(at);
}
}
reached.remove(&seq);
reached.into_iter().collect()
}
pub fn concurrent(&self, a: Seq, b: Seq) -> bool {
a != b && !self.causes(b).contains(&a) && !self.causes(a).contains(&b)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn chain() -> Journal<&'static str> {
let mut log = Journal::new();
let a = log.append("a");
let b = log.append_caused_by([a], "b").unwrap();
log.append_caused_by([b], "c").unwrap();
log
}
#[test]
fn an_ordinary_append_claims_no_cause() {
let mut log: Journal<u8> = Journal::new();
let a = log.append(1);
let b = log.append(2);
assert!(log.parents(a).is_empty());
assert!(log.parents(b).is_empty());
assert_eq!(log.roots().collect::<Vec<_>>(), vec![a, b]);
assert!(
log.effects(a).is_empty(),
"nothing claimed to follow from it"
);
}
#[test]
fn causes_walk_backwards_and_effects_walk_forwards() {
let log = chain();
assert_eq!(log.causes(Seq(2)), vec![Seq(1), Seq(0)], "nearest first");
assert_eq!(log.effects(Seq(0)), vec![Seq(1), Seq(2)], "ascending");
assert!(log.causes(Seq(0)).is_empty());
assert!(log.effects(Seq(2)).is_empty());
}
#[test]
fn an_entry_may_have_several_causes() {
let mut log = Journal::new();
let a = log.append("a");
let b = log.append("b");
let merged = log.append_caused_by([a, b], "both").unwrap();
assert_eq!(log.parents(merged), &[a, b]);
assert_eq!(log.effects(a), vec![merged]);
assert_eq!(log.effects(b), vec![merged]);
}
#[test]
fn independent_entries_are_concurrent() {
let mut log = Journal::new();
let a = log.append("a");
let b = log.append("b");
let after_a = log.append_caused_by([a], "after a").unwrap();
assert!(log.concurrent(a, b), "neither led to the other");
assert!(log.concurrent(after_a, b));
assert!(!log.concurrent(a, after_a), "one led to the other");
assert!(
!log.concurrent(a, a),
"an entry is not concurrent with itself"
);
}
#[test]
fn the_sequence_is_always_a_topological_order() {
let mut log = Journal::new();
let a = log.append("a");
let b = log.append_caused_by([a], "b").unwrap();
let c = log.append_caused_by([a, b], "c").unwrap();
for entry in [a, b, c] {
for parent in log.parents(entry) {
assert!(
parent.index() < entry.index(),
"{parent:?} precedes {entry:?}"
);
}
}
}
#[test]
fn an_entry_cannot_cite_the_future() {
let mut log: Journal<u8> = Journal::new();
log.append(1);
assert_eq!(
log.append_caused_by([Seq(7)], 2),
Err(CausalError::UnknownParent(Seq(7)))
);
assert_eq!(log.len(), 1, "and nothing was appended");
}
#[test]
fn an_entry_cannot_cite_itself() {
let mut log: Journal<u8> = Journal::new();
assert_eq!(
log.append_caused_by([Seq(0)], 1),
Err(CausalError::UnknownParent(Seq(0)))
);
}
#[test]
fn repeated_causes_collapse() {
let mut left = Journal::new();
let a = left.append("a");
let b = left.append("b");
left.append_caused_by([a, b, a], "c").unwrap();
let mut right = Journal::new();
right.append("a");
right.append("b");
right.append_caused_by([b, a], "c").unwrap();
assert_eq!(left, right);
}
#[test]
fn replaying_in_sequence_order_never_precedes_a_cause() {
let log = chain();
let mut applied: Vec<Seq> = Vec::new();
for index in 0..log.len() {
let at = Seq(index as u64);
for parent in log.parents(at) {
assert!(
applied.contains(parent),
"{parent:?} was applied before {at:?}"
);
}
applied.push(at);
}
}
}
#[cfg(test)]
mod compatibility {
use super::*;
const OLD: &str = r#"{"id":null,"provenance":null,"entries":["a","b"]}"#;
const NOW: &str = r#"{"id":null,"provenance":null,"entries":["a","b"],"parents":[]}"#;
#[test]
fn a_log_written_before_causality_still_loads() {
let log: Journal<String> = serde_json::from_str(OLD).expect("old logs load");
assert_eq!(log.len(), 2);
assert!(log.parents(Seq(0)).is_empty());
assert!(log.parents(Seq(1)).is_empty());
assert_eq!(log.roots().collect::<Vec<_>>(), vec![Seq(0), Seq(1)]);
}
#[test]
fn a_log_that_claims_no_causes_stays_small() {
let mut log: Journal<String> = Journal::new();
log.append("a".into());
log.append("b".into());
assert_eq!(serde_json::to_string(&log).unwrap(), NOW);
}
#[test]
fn a_causeless_log_survives_a_positional_codec() {
let mut log: Journal<String> = Journal::new();
log.append("a".into());
let bytes = postcard::to_allocvec(&log).expect("encodes");
let back: Journal<String> = postcard::from_bytes(&bytes).expect("and decodes");
assert_eq!(back, log);
}
#[test]
fn causality_survives_a_round_trip() {
let mut log: Journal<String> = Journal::new();
let a = log.append("a".into());
log.append_caused_by([a], "b".into()).unwrap();
let text = serde_json::to_string(&log).unwrap();
let back: Journal<String> = serde_json::from_str(&text).unwrap();
assert_eq!(back, log);
assert_eq!(back.parents(Seq(1)), &[a]);
}
}