blockworx/log/

change.rs

//! The unit that is hashed, stored, sent and merged: a batch of commands with
//! the heads its author had seen.

use std::collections::BTreeSet;

use serde::{Deserialize, Serialize};

use crate::log::encode;
use crate::log::id::{ActorId, BatchIndex, ChangeHash, Clock, Lamport, Stamp, WriteOrder};
use crate::log::{Command, ElementId};

/// Milliseconds since the Unix epoch, for display only.
///
/// Never load-bearing: two replicas' wall clocks disagree, and a merge that
/// consulted one would stop being reproducible. Ordering is [`Stamp`]'s job.
#[derive(
    Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default, Serialize, Deserialize,
)]
pub struct WallTime(i64);

impl WallTime {
    pub const UNKNOWN: WallTime = WallTime(0);

    pub const fn from_millis(millis: i64) -> Self {
        Self(millis)
    }

    pub const fn millis(self) -> i64 {
        self.0
    }
}

/// What the author was doing, for a history a person can read.
///
/// Free text rather than a tagged verb: the editor's real vocabulary is not
/// settled yet, and a string cannot become wrong the way a half-guessed enum
/// would. Narrowing it later means a [`ChangeV2`](Change), which is what the
/// versioned envelope is for.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default, Serialize, Deserialize)]
pub struct SemanticLabel(String);

impl SemanticLabel {
    pub fn new(text: impl Into<String>) -> Self {
        Self(text.into())
    }

    pub fn as_str(&self) -> &str {
        &self.0
    }
}

impl std::fmt::Display for SemanticLabel {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(&self.0)
    }
}

/// A node of the history DAG.
///
/// Versioned by variant rather than by a field. A `version: u16` only
/// *describes* a shape; a variant *is* one — `ChangeV1`'s field list is frozen
/// by construction, so its encoding, and therefore the hash every stored change
/// is identified by, cannot drift. A shape change adds `V2` beside it and leaves
/// every existing log meaning exactly what it meant.
///
/// It also gives the refuse-don't-guess rule for free: a `V2` written by a newer
/// build fails to deserialize here rather than being reinterpreted as a `V1`.
///
/// Note what does *not* need a new version: adding a `PropWrite` variant. That
/// is forward-incompatible (an older build refuses it) but backward-compatible
/// (a newer build still reads old logs), which is the right asymmetry.
#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
pub enum Change {
    V1(ChangeV1),
}

/// `parents` are the heads its author had when they made it, so a change with
/// two or more parents *is* a merge.
///
/// **Frozen.** Every field here is part of a hash that identifies stored
/// changes forever. Add a field and you have changed what every existing V1
/// change hashes to — add `ChangeV2` instead.
#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
pub struct ChangeV1 {
    /// The heads its author had seen. A set, because that is what it is: the
    /// same heads always encode the same way and therefore hash the same,
    /// without a constructor having to keep a `Vec` sorted and deduplicated.
    pub parents: BTreeSet<ChangeHash>,
    pub actor: ActorId,
    pub lamport: Lamport,
    pub wall_time: WallTime,
    /// The lease scope this change was made under, when leases are in play.
    pub scope: Option<ElementId>,
    pub label: SemanticLabel,
    pub commands: Vec<Command>,
}

impl Change {
    pub fn new(
        stamp: Stamp,
        parents: impl IntoIterator<Item = ChangeHash>,
        label: SemanticLabel,
        commands: Vec<Command>,
    ) -> Self {
        Self::V1(ChangeV1 {
            parents: parents.into_iter().collect(),
            actor: stamp.actor,
            lamport: stamp.lamport,
            wall_time: WallTime::UNKNOWN,
            scope: None,
            label,
            commands,
        })
    }

    fn v1(&self) -> &ChangeV1 {
        match self {
            Self::V1(change) => change,
        }
    }

    fn v1_mut(&mut self) -> &mut ChangeV1 {
        match self {
            Self::V1(change) => change,
        }
    }

    pub fn parents(&self) -> &BTreeSet<ChangeHash> {
        &self.v1().parents
    }

    pub fn actor(&self) -> ActorId {
        self.v1().actor
    }

    pub fn lamport(&self) -> Lamport {
        self.v1().lamport
    }

    pub fn label(&self) -> &SemanticLabel {
        &self.v1().label
    }

    pub fn commands(&self) -> &[Command] {
        &self.v1().commands
    }

    pub fn wall_time(&self) -> WallTime {
        self.v1().wall_time
    }

    pub fn set_wall_time(&mut self, at: WallTime) {
        self.v1_mut().wall_time = at;
    }

    pub fn scope(&self) -> Option<ElementId> {
        self.v1().scope
    }

    pub fn set_scope(&mut self, scope: Option<ElementId>) {
        self.v1_mut().scope = scope;
    }

    pub fn stamp(&self) -> Stamp {
        Stamp {
            lamport: self.lamport(),
            actor: self.actor(),
        }
    }

    /// Where the command at `index` sits in the global write order.
    pub fn order_of(&self, index: usize) -> WriteOrder {
        WriteOrder::new(
            self.stamp(),
            BatchIndex::new(u32::try_from(index).unwrap_or(u32::MAX)),
        )
    }

    /// Content address over the canonical encoding, which includes the parent
    /// hashes — so identical edits made against different histories are
    /// different changes, and a hash commits to everything behind it.
    pub fn hash(&self) -> ChangeHash {
        ChangeHash::from_bytes(*blake3::hash(&encode::to_bytes(self)).as_bytes())
    }

    pub fn is_merge(&self) -> bool {
        self.parents().len() > 1
    }

    /// Every command of this change, undone, in reverse order. Reversed so
    /// that a batch which created an element and then set its properties
    /// undoes the properties before the element goes away.
    pub fn inverted_commands(&self) -> Vec<Command> {
        self.commands()
            .iter()
            .rev()
            .map(Command::inverted)
            .collect()
    }
}

/// Accumulates the commands of one gesture, then seals them into a change.
///
/// One builder makes one change and is consumed doing it: tools describe what
/// they did, and the batch becomes a change at the gesture boundary. Sealing is
/// the only place the clock is read, which is what keeps clocks out of the fold.
#[derive(Debug, Default)]
pub struct ChangeBuilder {
    commands: Vec<Command>,
}

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

    pub fn push(&mut self, command: Command) {
        self.commands.push(command);
    }

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

    /// `None` when nothing was recorded — a gesture that ended where it began
    /// is not history, and must not burn a clock tick.
    pub fn seal(
        self,
        clock: &mut Clock,
        heads: impl IntoIterator<Item = ChangeHash>,
        label: SemanticLabel,
    ) -> Option<Change> {
        if self.commands.is_empty() {
            return None;
        }
        Some(Change::new(clock.tick(), heads, label, self.commands))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::log::command::{ElementKind, PropSet};

    fn hash(byte: u8) -> ChangeHash {
        ChangeHash::from_bytes([byte; 32])
    }

    fn a_change(parents: impl IntoIterator<Item = ChangeHash>) -> Change {
        let mut clock = Clock::new(ActorId::from_uuid(uuid::Uuid::from_bytes([7; 16])));
        Change::new(
            clock.tick(),
            parents,
            SemanticLabel::new("test"),
            vec![Command::Create {
                id: ElementId::from_uuid(uuid::Uuid::from_bytes([3; 16])),
                kind: ElementKind::Block,
                parent: ElementId::DOCUMENT,
                init: PropSet::new(),
            }],
        )
    }

    /// Heads are a set, so the order they are handed over in cannot reach the
    /// encoding, and therefore cannot reach the hash.
    #[test]
    fn parent_order_does_not_change_the_hash() {
        let forwards = a_change([hash(1), hash(2)]);
        let backwards = a_change([hash(2), hash(1)]);
        assert_eq!(forwards.parents(), backwards.parents());
        assert_eq!(forwards.hash(), backwards.hash());
    }

    #[test]
    fn a_repeated_parent_is_recorded_once() {
        let change = a_change([hash(1), hash(1)]);
        assert_eq!(change.parents(), &BTreeSet::from([hash(1)]));
        assert!(!change.is_merge());
    }

    #[test]
    fn parents_are_part_of_the_hash() {
        assert_ne!(a_change([hash(1)]).hash(), a_change([hash(2)]).hash());
    }

    #[test]
    fn an_empty_builder_seals_to_nothing() {
        let mut clock = Clock::new(ActorId::new());
        let builder = ChangeBuilder::new();
        assert!(
            builder
                .seal(&mut clock, [], SemanticLabel::new("noop"))
                .is_none()
        );
        assert_eq!(
            clock.lamport(),
            Lamport::ZERO,
            "an empty seal must not burn a lamport tick"
        );
    }

    #[test]
    fn sealing_carries_the_pushed_commands_into_the_change() {
        let mut clock = Clock::new(ActorId::new());
        let id = ElementId::new();
        let mut builder = ChangeBuilder::new();
        builder.push(Command::Delete { id });
        assert!(!builder.is_empty());

        let sealed = builder
            .seal(&mut clock, [], SemanticLabel::new("delete"))
            .expect("a command was recorded");
        assert_eq!(sealed.commands().to_vec(), vec![Command::Delete { id }]);
        assert_eq!(sealed.lamport(), Lamport::new(1));
    }

    /// Undoing a batch that built something up has to take it apart in the
    /// opposite order.
    #[test]
    fn inverted_commands_run_backwards() {
        let id = ElementId::new();
        let change = Change::new(
            Stamp {
                lamport: Lamport::new(1),
                actor: ActorId::new(),
            },
            [],
            SemanticLabel::new("create then delete"),
            vec![
                Command::Create {
                    id,
                    kind: ElementKind::Block,
                    parent: ElementId::DOCUMENT,
                    init: PropSet::new(),
                },
                Command::Delete { id },
            ],
        );

        assert_eq!(
            change.inverted_commands(),
            vec![Command::Restore { id }, Command::Delete { id }]
        );
    }
}