git_bug/replica/entity/lamport/
mod.rs

1// git-bug-rs - A rust library for interfacing with git-bug repositories
2//
3// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
4// SPDX-License-Identifier: GPL-3.0-or-later
5//
6// This file is part of git-bug-rs/git-gub.
7//
8// You should have received a copy of the License along with this program.
9// If not, see <https://www.gnu.org/licenses/agpl.txt>.
10
11//! > The Lamport timestamp algorithm is a simple logical clock algorithm used
12//! > to determine the order of events in a distributed computer system. As
13//! > different nodes or processes will typically not be perfectly synchronized,
14//! > this algorithm is used to provide a partial ordering of events with
15//! > minimal overhead, and conceptually provide a starting point for the more
16//! > advanced vector clock method. The algorithm is named after its creator,
17//! > Leslie Lamport.
18//!
19//! Source [wikipedia](https://en.wikipedia.org/wiki/Lamport_timestamp).
20//!
21//! This is the implementation of this specialized for the use case of
22//! `git-bug-rs`.
23
24use serde::{Deserialize, Serialize};
25
26pub mod mem;
27pub mod persistent;
28pub mod repository;
29
30/// The internal representation of a [`Clock`]'s time.
31/// The only property of this type is that it is always advancing, it is not
32/// connected to an actual time stamp.
33#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
34pub struct Time(u64);
35
36impl Time {
37    /// Construct a Time from a raw value.
38    #[must_use]
39    pub fn from(value: u64) -> Self {
40        Self(value)
41    }
42
43    /// Access the internal value of this Time.
44    #[must_use]
45    pub fn value(self) -> u64 {
46        self.0
47    }
48}
49
50/// A Lamport clock.
51///
52/// See the module documentation, for information on why this is needed.
53pub trait Clock {
54    /// The Error returned, when trying to [`increment`][`Clock::increment`]
55    /// this clock.
56    type IncrementError: std::error::Error;
57
58    /// The Error returned, when trying to [`witness`][`Clock::witness`] this
59    /// clock.
60    type WitnessError: std::error::Error;
61
62    /// Get the current value of this clock.
63    fn time(&self) -> Time;
64
65    /// Return the current value and increment it internally.
66    ///
67    /// # Errors
68    /// If the increment operation failed.
69    fn increment(&mut self) -> Result<Time, Self::IncrementError>;
70
71    /// Update our clock based on another processes clock's value, we
72    /// “witnessed”.
73    ///
74    /// We effectively try to keep our clock at `other + 1` time, so that we are
75    /// always ahead by one time unit.
76    ///
77    /// # Examples
78    /// ```rust
79    /// use git_bug::replica::entity::lamport::{Clock, Time, mem};
80    /// # fn main() -> Result<(), <mem::MemClock as Clock>::IncrementError> {
81    /// let mut clock = mem::MemClock::new();
82    /// assert_eq!(1, clock.time().value());
83    /// assert_eq!(1, clock.increment()?.value());
84    ///
85    /// clock.witness(Time::from(42));
86    /// assert_eq!(42, clock.time().value());
87    ///
88    /// clock.witness(Time::from(30));
89    /// assert_eq!(Time::from(42), clock.time());
90    /// # Ok(())
91    /// # }
92    /// ```
93    ///
94    /// # Errors
95    /// If the witness operation failed.
96    fn witness(&mut self, other: Time) -> Result<(), Self::WitnessError>;
97}
98
99#[cfg(test)]
100/// Internal tests
101pub mod test {
102    use super::{Clock, Time};
103
104    /// Generic clock test function
105    ///
106    /// # Panics
107    /// If tests fail.
108    pub fn test_clock<C>(mut clock: C)
109    where
110        C: Clock,
111    {
112        assert_eq!(Time(1), clock.time());
113
114        let time = clock.increment().unwrap();
115        assert_eq!(Time(1), time);
116        assert_eq!(Time(2), clock.time());
117
118        clock.witness(Time(42)).unwrap();
119        assert_eq!(Time(42), clock.time());
120
121        clock.witness(Time(42)).unwrap();
122        assert_eq!(Time(42), clock.time());
123
124        clock.witness(Time(30)).unwrap();
125        assert_eq!(Time(42), clock.time());
126    }
127}
git_bug/replica/entity/lamport/mod.rs

git_bug/replica/entity/lamport/
mod.rs
