cojson 0.6.0

Collaborative JSON (A high performance CRDT)
Documentation
use std::{cell::UnsafeCell, cmp::Ordering, hash::Hash, rc::Rc};

use crate::{
    io::SrcID,
    mem_use::{MemUsage, MemUser},
    ops::OpID,
};

// TODO(optimization): merge consecutive runs when they touch

#[derive(Clone, PartialEq, Eq, Hash)]
// assumes that we fill existing runs at the end, or start new ones
pub struct SparseMonotonicVector<T: Clone> {
    runs: im::OrdMap<u32, ImAppendOnlyVec<T>>,
}

impl<T: Clone> SparseMonotonicVector<T> {
    pub fn get(&self, idx: u32) -> Option<&T> {
        self.runs
            .get_prev(&idx)
            .and_then(|(run_start, run)| run.get((idx - run_start) as usize))
    }

    pub fn insert(&mut self, idx: u32, val: T) {
        if let Some((run_start, run)) = self.runs.get_prev_mut(&idx) {
            match idx.cmp(&(run_start + run.len() as u32)) {
                Ordering::Less => {
                    panic!("Cannot insert in middle of existing run")
                }
                Ordering::Equal => {
                    run.push(val);
                }
                Ordering::Greater => {
                    // after run, before next
                    self.runs.insert(idx, ImAppendOnlyVec::unit(val));
                }
            }
        } else {
            self.runs.insert(idx, ImAppendOnlyVec::unit(val));
        }
    }

    pub fn has_idx(&self, idx: u32) -> bool {
        self.runs
            .get_prev(&idx)
            .filter(|(run_start, run)| idx < *run_start + run.len() as u32)
            .is_some()
    }

    pub fn to_vec(&self) -> Vec<(u32, T)> {
        let mut vec = Vec::new();
        for (run_start, run) in self.runs.iter() {
            for (i, val) in run.as_slice().iter().enumerate() {
                vec.push((*run_start + i as u32, val.clone()));
            }
        }
        vec
    }
}

impl<T: Clone> Default for SparseMonotonicVector<T> {
    fn default() -> Self {
        Self {
            runs: im::OrdMap::new(),
        }
    }
}

impl<T: MemUser + Clone> MemUser for SparseMonotonicVector<T> {
    fn mem_use(&self) -> MemUsage {
        MemUsage::Struct {
            name: "SparseMonotonicVector",
            fields: vec![("runs", self.runs.mem_use())],
        }
    }
}

#[derive(Default, Clone, PartialEq, Eq, Hash)]
// assumes that we fill existing runs at the end, or start new ones
pub struct SparseMonotonicIntSet {
    // start, len
    runs: im::OrdMap<u32, u32>,
}

impl SparseMonotonicIntSet {
    pub fn insert(&mut self, idx: u32) {
        if let Some((run_start, run_len)) = self.runs.get_prev_mut(&idx) {
            match idx.cmp(&(run_start + *run_len)) {
                Ordering::Less => {
                    panic!("Cannot insert in middle of existing run")
                }
                Ordering::Equal => {
                    *run_len += 1;
                }
                Ordering::Greater => {
                    // after run, before next
                    self.runs.insert(idx, 1);
                }
            }
        } else {
            self.runs.insert(idx, 1);
        }
    }

    pub fn has(&self, idx: u32) -> bool {
        self.runs
            .get_prev(&idx)
            .filter(|(run_start, run_len)| idx < *run_start + *run_len)
            .is_some()
    }

    pub fn to_vec(&self) -> Vec<u32> {
        let mut ints = Vec::new();
        for (run_start, run_len) in self.runs.iter() {
            for i in 0..*run_len {
                ints.push(*run_start + i);
            }
        }
        ints
    }
}

impl MemUser for SparseMonotonicIntSet {
    fn mem_use(&self) -> MemUsage {
        MemUsage::Struct {
            name: "SparseMonotonicIntSet",
            fields: vec![("runs", self.runs.mem_use())],
        }
    }
}

#[derive(Clone, Default, PartialEq, Eq, Hash)]
pub struct SparseOpIDSet(im::HashMap<SrcID, SparseMonotonicIntSet>);

impl SparseOpIDSet {
    pub fn insert(&mut self, op_id: OpID) {
        self.0
            .entry(op_id.0)
            .or_default()
            .insert(op_id.1);
    }

    pub fn contains(&self, op_id: &OpID) -> bool {
        if let Some(per_node) = self.0.get(&op_id.0) {
            per_node.has(op_id.1)
        } else {
            false
        }
    }

    pub fn to_vec(&self) -> Vec<OpID> {
        let mut ops = Vec::new();
        for (src_id, per_node) in self.0.iter() {
            for sequence_idx in per_node.to_vec() {
                ops.push(OpID (*src_id,
                     sequence_idx,
                ));
            }
        }
        ops
    }
}

impl std::fmt::Debug for SparseOpIDSet {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "SparseOpIDSet({:?})", self.to_vec())
    }
}

impl MemUser for SparseOpIDSet {
    fn mem_use(&self) -> MemUsage {
        self.0.mem_use()
    }
}

#[derive(Clone, Default, Debug)]
pub struct ImAppendOnlyVec<T> {
    this_len: u32,
    data: Rc<UnsafeCell<Vec<T>>>,
}

impl<T> ImAppendOnlyVec<T> {
    pub fn unit(item: T) -> ImAppendOnlyVec<T> {
        ImAppendOnlyVec {
            this_len: 1,
            data: Rc::new(UnsafeCell::new(vec![item])),
        }
    }

    pub fn push(&mut self, item: T) {
        let data = self.data.get();
        unsafe {
            if self.this_len as usize != (*data).len() {
                panic!("Can only append onto the latest ImAppendOnlyVec reference")
            }
            (*data).push(item);
        }
        self.this_len += 1;
    }

    pub fn get(&self, at: usize) -> Option<&T> {
        if at < self.this_len as usize {
            unsafe { (*self.data.get()).get(at) }
        } else {
            None
        }
    }

    pub fn len(&self) -> usize {
        self.this_len as usize
    }

    pub fn as_slice(&self) -> &[T] {
        unsafe { &(*self.data.get())[0..self.this_len as usize] }
    }
}

impl<T: Hash> Hash for ImAppendOnlyVec<T> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.as_slice().hash(state)
    }
}

impl<T: PartialEq> PartialEq for ImAppendOnlyVec<T> {
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

impl<T: Eq> Eq for ImAppendOnlyVec<T> {}

impl<T: MemUser> MemUser for ImAppendOnlyVec<T> {
    fn mem_use(&self) -> MemUsage {
        MemUsage::Struct {
            name: "ImAppendOnlyVec",
            fields: vec![
                ("this_len", self.this_len.mem_use()),
                ("data", self.data.mem_use()),
            ],
        }
    }
}