blockworx/log/

state.rs

//! Document state: what the log folds into.
//!
//! Every element is a bag of registers plus a liveness flag, and each of those
//! keeps the write with the greatest [`WriteOrder`] it has seen. Nothing here
//! knows about time, actors, or hashes beyond that order — this is a value,
//! and a snapshot of it is a cache the log can always rebuild.
//!
//! Collections are ordered maps throughout. Iteration order is part of the
//! answer: it decides z-order, and two replicas must encode a state to the
//! same bytes.

use std::collections::BTreeMap;

use serde::{Deserialize, Serialize};

use crate::log::command::{ElementKind, PropTag, PropWrite};
use crate::log::id::{ElementId, WriteOrder};

/// Whether an element is present or tombstoned. A register like any other, so
/// a delete racing a restore resolves by write order instead of by who arrived
/// last.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Serialize, Deserialize)]
pub enum Liveness {
    Live,
    Deleted,
}

impl Liveness {
    pub fn is_live(self) -> bool {
        self == Liveness::Live
    }
}

/// What happened to a write. A loss is not an error — it is the merge working
/// — but it is what a collision review reports.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Applied {
    Won,
    /// Dropped because the register already held a write ordered after this
    /// one. Dropping it is what makes delivery order irrelevant.
    LostToNewer,
}

/// One register. `value` is `None` when the register has been cleared — a
/// tombstone for a property, which still carries an order so a concurrent
/// earlier write cannot resurrect the old value.
#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
pub struct Register {
    pub value: Option<PropWrite>,
    pub order: WriteOrder,
}

#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
pub struct Element {
    kind: ElementKind,
    /// The order of the create that made it. This is the element's place in
    /// z-order, which is why no explicit ordering field exists anywhere.
    created: WriteOrder,
    liveness: Liveness,
    liveness_order: WriteOrder,
    registers: BTreeMap<PropTag, Register>,
}

impl Element {
    fn new(kind: ElementKind, created: WriteOrder) -> Self {
        Self {
            kind,
            created,
            liveness: Liveness::Live,
            liveness_order: created,
            registers: BTreeMap::new(),
        }
    }

    pub fn kind(&self) -> ElementKind {
        self.kind
    }

    pub fn created(&self) -> WriteOrder {
        self.created
    }

    pub fn liveness(&self) -> Liveness {
        self.liveness
    }

    pub fn is_live(&self) -> bool {
        self.liveness.is_live()
    }

    pub fn get(&self, tag: PropTag) -> Option<&PropWrite> {
        self.registers.get(&tag).and_then(|r| r.value.as_ref())
    }

    pub fn register(&self, tag: PropTag) -> Option<&Register> {
        self.registers.get(&tag)
    }

    /// Ordered by tag, so encoding a state is a function of its content.
    pub fn registers(&self) -> impl Iterator<Item = (PropTag, &Register)> {
        self.registers.iter().map(|(tag, reg)| (*tag, reg))
    }

    pub fn parent(&self) -> Option<ElementId> {
        match self.get(PropTag::Parent) {
            Some(PropWrite::Parent(id)) => Some(*id),
            _ => None,
        }
    }

    /// The entire merge rule. A write ordered before what the register already
    /// holds is dropped, which is what makes `max` — and therefore the whole
    /// engine — independent of the order writes arrive in.
    ///
    /// `value` is `None` to clear the register. Clearing is a write like any
    /// other: it lands in the map with its order rather than removing the
    /// entry, or an older write arriving later would win.
    fn write(&mut self, tag: PropTag, value: Option<PropWrite>, order: WriteOrder) -> Applied {
        match self.registers.get(&tag) {
            Some(held) if held.order > order => Applied::LostToNewer,
            _ => {
                self.registers.insert(tag, Register { value, order });
                Applied::Won
            }
        }
    }

    fn set_liveness(&mut self, liveness: Liveness, order: WriteOrder) -> Applied {
        if self.liveness_order > order {
            return Applied::LostToNewer;
        }
        self.liveness = liveness;
        self.liveness_order = order;
        Applied::Won
    }
}

/// The folded document.
#[derive(Clone, PartialEq, Debug, Default, Serialize, Deserialize)]
pub struct DocState {
    elements: BTreeMap<ElementId, Element>,
}

impl DocState {
    pub fn new() -> Self {
        Self::default()
    }

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

    pub fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }

    pub fn contains(&self, id: ElementId) -> bool {
        self.elements.contains_key(&id)
    }

    pub fn element(&self, id: ElementId) -> Option<&Element> {
        self.elements.get(&id)
    }

    /// Live elements only. A tombstoned element is still present — it has to
    /// be, or a restore would have nothing to bring back — but it is not part
    /// of the document.
    pub fn live(&self, id: ElementId) -> Option<&Element> {
        self.elements.get(&id).filter(|e| e.is_live())
    }

    pub fn get(&self, id: ElementId, tag: PropTag) -> Option<&PropWrite> {
        self.live(id)?.get(tag)
    }

    /// Every element including tombstones, in id order.
    pub fn iter(&self) -> impl Iterator<Item = (ElementId, &Element)> {
        self.elements.iter().map(|(id, e)| (*id, e))
    }

    /// A parent's live children, in z-order — which is creation order, since
    /// that is what the create's [`WriteOrder`] records. No stored sequence,
    /// so nothing to merge and nothing to renumber.
    pub fn children(&self, parent: ElementId) -> Vec<ElementId> {
        let mut found: Vec<(WriteOrder, ElementId)> = self
            .elements
            .iter()
            .filter(|(_, e)| e.is_live() && e.parent() == Some(parent))
            .map(|(id, e)| (e.created, *id))
            .collect();
        found.sort_unstable();
        found.into_iter().map(|(_, id)| id).collect()
    }

    /// Walks parent links to the document root. `None` when the chain runs off
    /// a tombstone or a missing element, or when it exceeds the number of
    /// elements — which can only mean a cycle, and is what the repair pass
    /// exists to void.
    pub fn is_rooted(&self, id: ElementId) -> bool {
        let mut at = id;
        for _ in 0..=self.elements.len() {
            if at.is_document() {
                return true;
            }
            match self.live(at).and_then(Element::parent) {
                Some(parent) => at = parent,
                None => return false,
            }
        }
        false
    }

    pub(crate) fn ensure(&mut self, id: ElementId, kind: ElementKind, created: WriteOrder) {
        match self.elements.get_mut(&id) {
            // Re-applying a create — the same change delivered twice — must
            // not move the element in z-order, so the earliest create wins.
            Some(existing) => existing.created = existing.created.min(created),
            None => {
                self.elements.insert(id, Element::new(kind, created));
            }
        }
    }

    pub(crate) fn write(
        &mut self,
        id: ElementId,
        tag: PropTag,
        value: Option<PropWrite>,
        order: WriteOrder,
    ) -> Option<Applied> {
        Some(self.elements.get_mut(&id)?.write(tag, value, order))
    }

    pub(crate) fn set_liveness(
        &mut self,
        id: ElementId,
        liveness: Liveness,
        order: WriteOrder,
    ) -> Option<Applied> {
        Some(self.elements.get_mut(&id)?.set_liveness(liveness, order))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::log::id::{ActorId, BatchIndex, Lamport, Stamp};

    fn order(lamport: u64, actor_byte: u8) -> WriteOrder {
        WriteOrder::new(
            Stamp {
                lamport: Lamport::new(lamport),
                actor: ActorId::from_uuid(uuid::Uuid::from_bytes([actor_byte; 16])),
            },
            BatchIndex::FIRST,
        )
    }

    fn element(byte: u8) -> ElementId {
        ElementId::from_uuid(uuid::Uuid::from_bytes([byte; 16]))
    }

    fn with_block(state: &mut DocState, id: ElementId, at: WriteOrder) {
        state.ensure(id, ElementKind::Block, at);
        set(state, id, PropWrite::Parent(ElementId::DOCUMENT), at);
    }

    /// Write a value, deriving its register from the value itself — the shape
    /// nearly every test wants, as against clearing a register.
    fn set(state: &mut DocState, id: ElementId, value: PropWrite, at: WriteOrder) -> Applied {
        state
            .write(id, value.tag(), Some(value), at)
            .expect("the element exists")
    }

    #[test]
    fn a_stale_write_loses_and_leaves_the_value_alone() {
        let mut state = DocState::new();
        let id = element(1);
        with_block(&mut state, id, order(1, 1));

        assert_eq!(
            set(&mut state, id, PropWrite::Accent(9), order(5, 1)),
            Applied::Won
        );
        assert_eq!(
            set(&mut state, id, PropWrite::Accent(2), order(3, 1)),
            Applied::LostToNewer,
            "a write ordered earlier must not land on a later one"
        );
        assert_eq!(state.get(id, PropTag::Accent), Some(&PropWrite::Accent(9)));
    }

    /// The convergence property in miniature: the same two writes applied in
    /// either order leave the same value.
    #[test]
    fn two_writes_commute() {
        let id = element(1);
        let (early, late) = (
            (PropWrite::Accent(1), order(4, 1)),
            (PropWrite::Accent(2), order(6, 1)),
        );

        let mut forwards = DocState::new();
        with_block(&mut forwards, id, order(1, 1));
        set(&mut forwards, id, early.0.clone(), early.1);
        set(&mut forwards, id, late.0.clone(), late.1);

        let mut backwards = DocState::new();
        with_block(&mut backwards, id, order(1, 1));
        set(&mut backwards, id, late.0.clone(), late.1);
        set(&mut backwards, id, early.0.clone(), early.1);

        assert_eq!(forwards, backwards);
        assert_eq!(
            forwards.get(id, PropTag::Accent),
            Some(&PropWrite::Accent(2))
        );
    }

    #[test]
    fn deleting_and_restoring_resolve_by_order_not_arrival() {
        let id = element(1);
        let mut delete_last = DocState::new();
        with_block(&mut delete_last, id, order(1, 1));
        delete_last.set_liveness(id, Liveness::Deleted, order(9, 1));
        delete_last.set_liveness(id, Liveness::Live, order(5, 1));

        let mut restore_last = DocState::new();
        with_block(&mut restore_last, id, order(1, 1));
        restore_last.set_liveness(id, Liveness::Live, order(5, 1));
        restore_last.set_liveness(id, Liveness::Deleted, order(9, 1));

        assert_eq!(delete_last, restore_last);
        assert!(!delete_last.element(id).expect("still present").is_live());
        assert!(
            delete_last.live(id).is_none(),
            "a tombstone is present but not part of the document"
        );
    }

    #[test]
    fn children_come_back_in_creation_order() {
        let mut state = DocState::new();
        let parent = element(1);
        with_block(&mut state, parent, order(1, 1));

        // Inserted late-first, so id order cannot be what produces the answer.
        let (first, second) = (element(9), element(2));
        state.ensure(first, ElementKind::Block, order(4, 1));
        set(&mut state, first, PropWrite::Parent(parent), order(4, 1));
        state.ensure(second, ElementKind::Block, order(7, 1));
        set(&mut state, second, PropWrite::Parent(parent), order(7, 1));

        assert!(first > second, "id order must differ from creation order");
        assert_eq!(state.children(parent), vec![first, second]);
    }

    #[test]
    fn a_tombstoned_child_leaves_its_parents_list() {
        let mut state = DocState::new();
        let parent = element(1);
        let child = element(2);
        with_block(&mut state, parent, order(1, 1));
        state.ensure(child, ElementKind::Block, order(2, 1));
        set(&mut state, child, PropWrite::Parent(parent), order(2, 1));
        assert_eq!(state.children(parent), vec![child]);

        state.set_liveness(child, Liveness::Deleted, order(3, 1));
        assert!(state.children(parent).is_empty());
    }

    /// A parent cycle must not hang the walk. The repair pass in phase 2 is
    /// what voids it; this only has to terminate.
    #[test]
    fn a_parent_cycle_is_reported_unrooted_rather_than_looping() {
        let mut state = DocState::new();
        let (a, b) = (element(1), element(2));
        state.ensure(a, ElementKind::Block, order(1, 1));
        state.ensure(b, ElementKind::Block, order(2, 1));
        set(&mut state, a, PropWrite::Parent(b), order(3, 1));
        set(&mut state, b, PropWrite::Parent(a), order(4, 1));

        assert!(!state.is_rooted(a));
        assert!(!state.is_rooted(b));
    }

    #[test]
    fn an_element_parented_to_the_document_is_rooted() {
        let mut state = DocState::new();
        let id = element(1);
        with_block(&mut state, id, order(1, 1));
        assert!(state.is_rooted(id));
    }

    /// Re-applying a create is how a duplicate delivery arrives; it must not
    /// restack the element.
    #[test]
    fn re_creating_keeps_the_earliest_creation_order() {
        let mut state = DocState::new();
        let id = element(1);
        state.ensure(id, ElementKind::Block, order(5, 1));
        state.ensure(id, ElementKind::Block, order(9, 1));
        assert_eq!(state.element(id).expect("present").created(), order(5, 1));
    }
}