lattices 0.7.0

Lattice data types for simplifying distributed state by providing associativity, commutativity, and idempotence.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use std::marker::PhantomData;

use crate::{DeepReveal, IsBot, IsTop, LatticeFrom, LatticeOrd, Merge};

/// A `Point` lattice, corresponding to a single instance of `T`.
///
/// Will runtime panic if a merge between inequal values is attempted.
///
/// The `Provenance` generic param is a token for the origin of this point. The parameter can be
/// used to differentiate between points with different provenances. This will prevent them from
/// being merged together, avoiding any posibility of panic.
///
/// Like [`Conflict<T>`](crate::Conflict) but will panic instead of going to a "conflict" top
/// state.
///
/// Can be thought of as a lattice with a domain of size one, corresponding to the specific value
/// inside.
///
/// This also can be used to wrap non lattice data into a lattice in a way that typechecks.
#[repr(transparent)]
#[derive(Copy, Clone, Debug, Default, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Point<T, Provenance> {
    /// The value stored inside. This should not be mutated.
    pub val: T,
    _token: PhantomData<*mut Provenance>,
}
impl<T, Provenance> Point<T, Provenance> {
    /// Create a new `Point` lattice instance from a value.
    pub fn new(val: T) -> Self {
        Self {
            val,
            _token: PhantomData,
        }
    }

    /// Create a new `Point` lattice instance from a value using `Into`.
    pub fn new_from(val: impl Into<T>) -> Self {
        Self::new(val.into())
    }
}
impl<T, Provenance> DeepReveal for Point<T, Provenance> {
    type Revealed = T;

    fn deep_reveal(self) -> Self::Revealed {
        self.val
    }
}

impl<T, Provenance> Merge<Point<T, Provenance>> for Point<T, Provenance>
where
    T: PartialEq,
{
    fn merge(&mut self, other: Point<T, Provenance>) -> bool {
        if self.val != other.val {
            panic!("The `Point` lattice cannot merge inequal elements.")
        }
        false
    }
}

impl<T, Provenance> LatticeFrom<Point<T, Provenance>> for Point<T, Provenance> {
    fn lattice_from(other: Point<T, Provenance>) -> Self {
        other
    }
}

impl<T, Provenance> PartialOrd<Point<T, Provenance>> for Point<T, Provenance>
where
    T: PartialEq,
{
    fn partial_cmp(&self, other: &Point<T, Provenance>) -> Option<std::cmp::Ordering> {
        if self.val != other.val {
            panic!("The `Point` lattice does not have a partial order between inequal elements.");
        }
        Some(std::cmp::Ordering::Equal)
    }
}
impl<T, Provenance> LatticeOrd<Point<T, Provenance>> for Point<T, Provenance> where
    Self: PartialOrd<Point<T, Provenance>>
{
}

impl<T, Provenance> PartialEq<Point<T, Provenance>> for Point<T, Provenance>
where
    T: PartialEq,
{
    fn eq(&self, other: &Point<T, Provenance>) -> bool {
        self.val == other.val
    }
}

impl<T, Provenance> IsBot for Point<T, Provenance> {
    fn is_bot(&self) -> bool {
        true
    }
}

impl<T, Provenance> IsTop for Point<T, Provenance> {
    fn is_top(&self) -> bool {
        true
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::test::{
        check_all, check_lattice_ord, check_lattice_properties, check_partial_ord_properties,
    };

    #[test]
    fn consistency_equal() {
        check_all(&[Point::<_, ()>::new("hello world")])
    }

    #[test]
    fn consistency_inequal() {
        use std::collections::BTreeSet;

        let items: &[Point<_, ()>] = &[
            Point::new(BTreeSet::from_iter([])),
            Point::new(BTreeSet::from_iter([0])),
            Point::new(BTreeSet::from_iter([1])),
            Point::new(BTreeSet::from_iter([0, 1])),
        ];

        // Merged inequal elements panic, therefore `NaiveMerge` panics.
        assert!(std::panic::catch_unwind(|| check_lattice_ord(items)).is_err());
        // `Point` does not have a partial order.
        assert!(std::panic::catch_unwind(|| check_partial_ord_properties(items)).is_err());
        // `Point` is not actually a lattice.
        assert!(std::panic::catch_unwind(|| check_lattice_properties(items)).is_err());
    }
}