iroh_db_core/
causality.rs

1use std::{cmp::Ordering, collections::BTreeMap};
2
3use crate::AuthorId;
4
5/// The unique, deterministic identity of an operation in a domain.
6#[derive(
7    Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, minicbor::Encode, minicbor::Decode,
8)]
9#[cbor(array)]
10pub struct Dot {
11    #[n(0)]
12    author: AuthorId,
13    #[n(1)]
14    sequence: u64,
15    #[n(2)]
16    operation: u32,
17}
18
19impl Dot {
20    /// Constructs an operation dot.
21    pub const fn new(author: AuthorId, sequence: u64, operation: u32) -> Self {
22        Self {
23            author,
24            sequence,
25            operation,
26        }
27    }
28
29    /// Returns the author that created this operation.
30    pub const fn author(self) -> AuthorId {
31        self.author
32    }
33
34    /// Returns the author's domain-local commit sequence.
35    pub const fn sequence(self) -> u64 {
36        self.sequence
37    }
38
39    /// Returns the operation index within the commit.
40    pub const fn operation(self) -> u32 {
41        self.operation
42    }
43}
44
45/// The causal relationship between two histories.
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum CausalRelation {
48    /// Both histories contain the same author sequences.
49    Equal,
50    /// The left history is strictly contained in the right history.
51    Before,
52    /// The left history strictly contains the right history.
53    After,
54    /// Each history contains an event absent from the other.
55    Concurrent,
56}
57
58/// A canonical summary of the highest observed commit sequence for each author.
59#[derive(Debug, Clone, Default, PartialEq, Eq, minicbor::Encode, minicbor::Decode)]
60#[cbor(transparent)]
61pub struct VersionVector {
62    #[n(0)]
63    entries: BTreeMap<AuthorId, u64>,
64}
65
66impl VersionVector {
67    /// Constructs an empty causal history.
68    pub const fn new() -> Self {
69        Self {
70            entries: BTreeMap::new(),
71        }
72    }
73
74    /// Records an observed operation and its containing commit.
75    pub fn observe(&mut self, dot: Dot) {
76        self.entries
77            .entry(dot.author())
78            .and_modify(|sequence| *sequence = (*sequence).max(dot.sequence()))
79            .or_insert(dot.sequence());
80    }
81
82    /// Returns whether this history includes the commit containing `dot`.
83    pub fn covers(&self, dot: &Dot) -> bool {
84        self.entries
85            .get(&dot.author())
86            .is_some_and(|sequence| *sequence >= dot.sequence())
87    }
88
89    /// Adds all events represented by `other` to this history.
90    pub fn merge(&mut self, other: &Self) {
91        for (&author, &other_sequence) in &other.entries {
92            self.entries
93                .entry(author)
94                .and_modify(|sequence| *sequence = (*sequence).max(other_sequence))
95                .or_insert(other_sequence);
96        }
97    }
98
99    /// Compares this history with another using vector-clock partial ordering.
100    pub fn relation(&self, other: &Self) -> CausalRelation {
101        let mut has_less = false;
102        let mut has_greater = false;
103
104        for author in self.entries.keys().chain(other.entries.keys()) {
105            match self.entries.get(author).cmp(&other.entries.get(author)) {
106                Ordering::Less => has_less = true,
107                Ordering::Equal => {}
108                Ordering::Greater => has_greater = true,
109            }
110
111            if has_less && has_greater {
112                return CausalRelation::Concurrent;
113            }
114        }
115
116        match (has_less, has_greater) {
117            (false, false) => CausalRelation::Equal,
118            (true, false) => CausalRelation::Before,
119            (false, true) => CausalRelation::After,
120            (true, true) => CausalRelation::Concurrent,
121        }
122    }
123
124    /// Iterates over authors and sequences in canonical author order.
125    pub fn iter(&self) -> impl ExactSizeIterator<Item = (&AuthorId, &u64)> {
126        self.entries.iter()
127    }
128}
iroh_db_core/causality.rs

iroh_db_core/
causality.rs
