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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

//! # GList - Grow-only List CRDT

use core::convert::Infallible;
use core::fmt;
use core::iter::FromIterator;
use core::ops::Bound::*;
use std::collections::BTreeSet;

use quickcheck::{Arbitrary, Gen};
use serde::{Deserialize, Serialize};

use crate::{CmRDT, CvRDT, Identifier};

/// Operations that can be performed on a List
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum Op<T> {
    /// Insert an element.
    Insert {
        /// The element identifier to insert.
        id: Identifier<T>,
    },
}

/// The GList is a grow-only list, that is, it allows inserts but not deletes.
/// Elements in the list are paths through an ordered tree, the tree grows deeper
/// when we try to insert between two elements who were inserted concurrently and
/// whose paths happen to have the same prefix.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct GList<T: Ord> {
    list: BTreeSet<Identifier<T>>,
}

impl<T: fmt::Display + Ord> fmt::Display for GList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "GList[")?;
        let mut iter = self.list.iter();
        if let Some(e) = iter.next() {
            write!(f, "{}", e)?;
        }
        for e in iter {
            write!(f, "{}", e)?;
        }
        write!(f, "]")
    }
}

impl<T: Ord> Default for GList<T> {
    fn default() -> Self {
        Self {
            list: Default::default(),
        }
    }
}

impl<T: Ord + Clone> GList<T> {
    /// Create an empty GList
    pub fn new() -> Self {
        Self::default()
    }

    /// Read the elements of the list into a user defined container
    pub fn read<'a, C: FromIterator<&'a T>>(&'a self) -> C {
        self.list.iter().map(|id| id.value()).collect()
    }

    /// Read the elements of the list into a user defined container, consuming the list in the process.
    pub fn read_into<C: FromIterator<T>>(self) -> C {
        self.list.into_iter().map(|id| id.into_value()).collect()
    }

    /// Iterate over the elements of the list
    pub fn iter(&self) -> std::collections::btree_set::Iter<Identifier<T>> {
        self.list.iter()
    }

    /// Return the element and it's marker at the specified index
    pub fn get(&self, idx: usize) -> Option<&Identifier<T>> {
        self.list.iter().nth(idx)
    }

    /// Generate an Op to insert the given element before the given marker
    pub fn insert_before(&self, high_id_opt: Option<&Identifier<T>>, elem: T) -> Op<T> {
        let low_id_opt = high_id_opt.and_then(|high_id| {
            self.list
                .range((Unbounded, Excluded(high_id.clone())))
                .rev()
                .find(|id| id < &high_id)
        });
        let id = Identifier::between(low_id_opt, high_id_opt, elem);
        Op::Insert { id }
    }

    /// Generate an insert op to insert the given element after the given marker
    pub fn insert_after(&self, low_id_opt: Option<&Identifier<T>>, elem: T) -> Op<T> {
        let high_id_opt = low_id_opt.and_then(|low_id| {
            self.list
                .range((Excluded(low_id.clone()), Unbounded))
                .find(|id| id > &low_id)
        });
        let id = Identifier::between(low_id_opt, high_id_opt, elem);
        Op::Insert { id }
    }

    /// Get the length of the list.
    pub fn len(&self) -> usize {
        self.list.len()
    }

    /// Check if the list is empty.
    pub fn is_empty(&self) -> bool {
        self.list.is_empty()
    }

    /// Get first element of the sequence represented by the list.
    pub fn first(&self) -> Option<&Identifier<T>> {
        self.iter().next()
    }

    /// Get last element of the sequence represented by the list.
    pub fn last(&self) -> Option<&Identifier<T>> {
        self.iter().rev().next()
    }
}

impl<T: Ord> CmRDT for GList<T> {
    type Op = Op<T>;
    type Validation = Infallible;

    fn validate_op(&self, _: &Self::Op) -> Result<(), Self::Validation> {
        Ok(())
    }

    fn apply(&mut self, op: Self::Op) {
        match op {
            Op::Insert { id } => self.list.insert(id),
        };
    }
}

impl<T: Ord> CvRDT for GList<T> {
    type Validation = Infallible;

    fn validate_merge(&self, _: &Self) -> Result<(), Self::Validation> {
        Ok(())
    }

    fn merge(&mut self, other: Self) {
        self.list.extend(other.list)
    }
}

impl<T: Arbitrary> Arbitrary for Op<T> {
    fn arbitrary<G: Gen>(g: &mut G) -> Self {
        let id = Identifier::arbitrary(g);
        Op::Insert { id }
    }
}