docs/generated/contracts.mdgenerated from code

Reference · 11 min read

loro-change

Contracts: loro-change.

Source: crates/lvcs-doc/src/change.rs.

ruston main
1/// One op of a document: its writer's Loro peer id ([`peer_of`]) and its2/// counter. A change is named by its first op's; a version's [`Heads`] are3/// the last ops at its tips (the version right after a change ending at4/// `end` is its op `end - 1`). Written `<peer:016x><counter:08x>` (245/// hex digits) wherever the API shows heads.6#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]7pub struct ChangeId {8    pub peer: u64,9    pub counter: i32,10}1112/// A document version: the change ids at its tips (Loro's frontiers),13/// sorted. Equal heads are the same version on every node.14pub type Heads = Vec<ChangeId>;1516/// How far a document holds each writer's ops (Loro's version vector): a17/// writer's peer id and the counter just past its last op held. What a18/// node holds in sync; [`SyncPayload::have`].19#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]20pub struct Have(pub BTreeMap<u64, i32>);2122/// Who wrote a change (discussion:owner/125, carried over): the signer, the grant23/// it wrote under (`GrantId::OWNER` for the owner and for imports), and24/// the device that committed it (`None` for an import or a caps seed, so25/// two devices importing identical bytes write one change, discussion:owner/69).26#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]27pub struct Record {28    pub signer: PeerKey,29    pub grant: GrantId,30    pub device: Option<DeviceKey>,31    /// Raised each time a refusal of one of its changes stops this writer's32    /// peer: a Loro peer's ops are one chain, so every later change of a33    /// refused peer is refused too, and the writer goes on as a new peer34    /// from the accepted state.35    pub epoch: u32,36}3738/// One commit's ops, unsigned: what a document emits for its signer39/// (`DocOutput::SignRequest`) and what [`SignedChange`] signs.40/// `bytes` is Loro's export of exactly the ops `peer` wrote from `start`41/// up to `end` (exclusive), a counter span: Loro may merge one peer's42/// consecutive commits into one change of its own, but a span exports43/// alone, deterministically on every replica, so the signed unit is the44/// span, not Loro's change. `deps` are the heads it was committed on, as45/// the bytes' blob metadata names them (`start_frontiers`); a receiver46/// checks the metadata's span and deps against these before importing, and47/// imports nothing whose deps it doesn't hold (Loro would park it pending).48/// `time_s` its commit time.49#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]50pub struct Change {51    pub doc: String,52    pub peer: u64,53    pub start: i32,54    pub end: i32,55    pub deps: Heads,56    /// Its Merkle digest ([`merkle`]): its bytes and the digests of the57    /// spans its deps and its own peer's previous op end in, so equal58    /// heads with equal digests are the same history on every node, and a59    /// signer's two changes at one id show as different digests.60    #[serde(with = "crate::cbor::fixed")]61    pub digest: [u8; 32],62    pub time_s: i64,63    pub record: Record,64    #[serde(with = "crate::cbor::bytes")]65    pub bytes: Vec<u8>,66}6768/// The multi-file landing a change is one of (discussion:owner/795): every69/// change of a landing shares its `id`, and `of` says how many there are.70/// It rides in the change's Loro commit message beside its record, so it71/// is inside the bytes the change's signature covers, and a change of no72/// landing carries the message it always did.73#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]74pub struct LandingMark {75    #[serde(with = "crate::cbor::fixed")]76    pub id: [u8; 16],77    pub of: u16,78}7980/// Which of `changes`, by position, depend on an op none of them holds,81/// directly or through one of the others: a dependency that comes later in82/// the slice is held, so stored order doesn't matter (secfix/31).83#[must_use]84pub fn dangling(changes: &[&Change]) -> BTreeSet<usize> {85    let mut gone = BTreeSet::new();86    loop {87        let mut spans: BTreeMap<u64, BTreeMap<i32, i32>> = BTreeMap::new();88        for (at, change) in changes.iter().enumerate() {89            if !gone.contains(&at) {90                spans91                    .entry(change.peer)92                    .or_default()93                    .insert(change.start, change.end);94            }95        }96        let held = |id: ChangeId| {97            spans98                .get(&id.peer)99                .and_then(|peer| peer.range(..=id.counter).next_back())100                .is_some_and(|(_, end)| id.counter < *end)101        };102        let mut found = false;103        for (at, change) in changes.iter().enumerate() {104            let previous = (change.start > 0).then(|| ChangeId::new(change.peer, change.start - 1));105            if !gone.contains(&at)106                && change107                    .deps108                    .iter()109                    .copied()110                    .chain(previous)111                    .any(|id| !held(id))112            {113                gone.insert(at);114                found = true;115            }116        }117        if !found {118            return gone;119        }120    }121}122123/// The first counter of each peer that the changes at `gone` (positions124/// in `changes`) stranded: each such change's own, and each dependency none125/// of the rest holds: this node's writers of those peers go on as new126/// peers, so an id those changes took is never issued again (secfix/31).127#[must_use]128pub fn stranded_from(changes: &[&Change], gone: &BTreeSet<usize>) -> BTreeMap<u64, i32> {129    let mut spans: BTreeMap<u64, BTreeMap<i32, i32>> = BTreeMap::new();130    for (at, change) in changes.iter().enumerate() {131        if !gone.contains(&at) {132            spans133                .entry(change.peer)134                .or_default()135                .insert(change.start, change.end);136        }137    }138    let held = |id: ChangeId| {139        spans140            .get(&id.peer)141            .and_then(|peer| peer.range(..=id.counter).next_back())142            .is_some_and(|(_, end)| id.counter < *end)143    };144    let mut from: BTreeMap<u64, i32> = BTreeMap::new();145    let mut lower = |peer: u64, counter: i32| {146        from.entry(peer)147            .and_modify(|first| *first = (*first).min(counter))148            .or_insert(counter);149    };150    for at in gone {151        let Some(change) = changes.get(*at) else {152            continue;153        };154        lower(change.peer, change.start);155        let previous = (change.start > 0).then(|| ChangeId::new(change.peer, change.start - 1));156        for dep in change.deps.iter().copied().chain(previous) {157            if !held(dep) {158                lower(dep.peer, dep.counter);159            }160        }161    }162    from163}164165/// A change and its signer's Ed25519 signature over166/// [`Change::signing_input`]: the unit a document stores, syncs, and167/// verifies before it imports anything.168#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]169pub struct SignedChange {170    pub change: Change,171    #[serde(with = "crate::cbor::fixed")]172    pub sig: [u8; 64],173}174175/// A held change's metadata: every field of its [`Change`] but its bytes,176/// with their length and SHA-256 (daemon-memory/5). A loaded document keeps177/// this, not the bytes Loro already imported: what reads a held change178/// either needs only these fields, re-imports its ops (Loro exports them,179/// [`crate::ledger`]'s `span_ops`), or sends it to a node (read from the180/// store). Its [`ChangeMeta::signing_input`] is the change's, so its181/// signature still verifies against it.182#[derive(Debug, Clone, PartialEq, Eq)]183pub struct ChangeMeta {184    pub doc: String,185    pub peer: u64,186    pub start: i32,187    pub end: i32,188    pub deps: Heads,189    pub digest: [u8; 32],190    pub time_s: i64,191    pub record: Record,192    /// Its bytes' length.193    pub len: u32,194    /// Its bytes' SHA-256 ([`Change::bytes_digest`]).195    pub bytes_digest: [u8; 32],196}197198/// A held signed change: its [`ChangeMeta`] and its signer's signature.199#[derive(Debug, Clone, PartialEq, Eq)]200pub struct HeldChange {201    pub change: ChangeMeta,202    pub sig: [u8; 64],203}204205impl ChangeMeta {206    /// Its id: its writer's peer id and first counter.207    #[must_use]208    pub const fn id(&self) -> ChangeId {209        ChangeId {210            peer: self.peer,211            counter: self.start,212        }213    }214215    /// What its signer signed, as [`Change::signing_input`] gives it.216    ///217    /// # Errors218    ///219    /// The array doesn't encode (it always does).220    pub fn signing_input(&self) -> Result<Vec<u8>, ciborium::ser::Error<std::io::Error>> {221        signing_input(222            &MetaFields {223                doc: &self.doc,224                peer: self.peer,225                start: self.start,226                end: self.end,227                deps: &self.deps,228                digest: &self.digest,229                time_s: self.time_s,230                record: &self.record,231            },232            &self.bytes_digest,233        )234    }235}236237impl From<&SignedChange> for HeldChange {238    fn from(signed: &SignedChange) -> Self {239        Self {240            change: signed.change.meta(),241            sig: signed.sig,242        }243    }244}245246/// A change's fields but its bytes, borrowed, as its signing input reads them.247struct MetaFields<'a> {248    doc: &'a str,249    peer: u64,250    start: i32,251    end: i32,252    deps: &'a Heads,253    digest: &'a [u8; 32],254    time_s: i64,255    record: &'a Record,256}257258/// The canonical CBOR array a change's signer signs: the domain, the259/// document address, the span, the deps, the Merkle digest, the commit260/// time, the record, and `bytes_digest`, the SHA-256 of its bytes.261fn signing_input(262    fields: &MetaFields<'_>,263    bytes_digest: &[u8; 32],264) -> Result<Vec<u8>, ciborium::ser::Error<std::io::Error>> {265    let input = (266        "lvcs/change/1",267        fields.doc,268        fields.peer,269        fields.start,270        fields.end,271        fields.deps,272        serde_bytes_array(fields.digest),273        fields.time_s,274        fields.record,275        serde_bytes_array(bytes_digest),276    );277    let mut out = Vec::new();278    ciborium::into_writer(&input, &mut out)?;279    Ok(out)280}281282/// What one document sends another (`SyncOut.payload`, `SyncIn.payload`):283/// what the sender holds, the first counter of each peer's ops it refused284/// (each later op of that peer is refused with it, so a sender skips them285/// rather than sending them again every round), and the signed changes it286/// holds that the receiver's last `have` and `refused` lack, in causal287/// order. An empty `changes` with equal `have`s settles the round.288///289/// A receiver never takes `refused` as a verdict (discussion:owner/549): it re-runs290/// its own checks on the changes of each peer named and refuses only what291/// they refuse. `rules` and `grants` say what the sender judged by, so a292/// receiver that admits what the sender refused can tell a bug (the same293/// rules and grants) from an expected difference.294#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]295pub struct SyncPayload {296    pub have: Have,297    pub refused: BTreeMap<u64, i32>,298    pub changes: Vec<SignedChange>,299    /// Equivocation evidence the sender holds (history row 461): each pair300    /// is the change it held and the other change its signer signed at301    /// those ops, both verifiable without either document, so a receiver302    /// stops the signer's peer and voids what it must without holding the303    /// pair itself.304    pub evidence: Vec<Evidence>,305    /// The sender's [`VERIFIER_RULES`]; 0 from a release before it.306    #[serde(default)]307    pub rules: u32,308    /// The digest of the canonical CBOR of the `GrantsKnown` the sender309    /// judges by, `None` before it knows any.310    #[serde(default)]311    pub grants: Option<[u8; 32]>,312    /// The sender dropped changes or evidence of the receiver's past its313    /// deferral bounds before it could judge them, and can judge now314    /// (discussion:owner/571): the receiver sends again everything this315    /// sender's `have` lacks, and its evidence, as on a new stream.316    #[serde(default, skip_serializing_if = "core::ops::Not::not")]317    pub resend: bool,318    /// The first counter of each peer whose changes the sender holds set319    /// aside as unreadable (discussion:owner/671 rule 2): a receiver skips320    /// those spans as it does `refused`, so a held change isn't sent again321    /// every round. Unlike `refused` it is no verdict: no node acts on it.322    /// Older nodes ignore it.323    #[serde(default, skip_serializing_if = "BTreeMap::is_empty")]324    pub unreadable: BTreeMap<u64, i32>,325}326327/// The version of the rules a document checks a received change by328/// (discussion:owner/549): a release bumps it whenever any check may judge one329/// change differently, so two nodes on equal rules and equal grants that330/// judge one change differently show a bug. That includes a release that331/// adds, removes, or changes a field of any record a kind decodes332/// (discussion:owner/671 rule 5): a binary that doesn't know the field333/// can't read the record, and a refusal stored under older rules is judged334/// again.335///336/// Every bump also bumps `JOURNAL_FORMAT` (discussion:owner/671) and adds its337/// row to [`VERIFIER_RULES_JOURNALS`]: a replay loads a document's ledger338/// under the running rules, so an older journal replayed under newer ones339/// would report a divergence on a healthy node.340/// 3 since discussion:owner/780: a plain writer's lend makes a plugin341/// instance, and an ephemeral event for a user needs the user's342/// delegation (release-qual/11). Also in 3 (tree-render/6): a channel or343/// approvals change writing a root of another type under a layout map's344/// name, or a container below a root, is judged from its own ops345/// (`kinds::shapes`): unknown, or stray for another root's name. Before,346/// it was judged from deep values, which show one of two same-named roots347/// by each node's history, so nodes judged it differently.348pub const VERIFIER_RULES: u32 = 3;349350/// Each version of [`VERIFIER_RULES`] since discussion:owner/671 and the351/// `JOURNAL_FORMAT` it started at. Rule 1's isn't known from the format's352/// history, so it has no row.353pub const VERIFIER_RULES_JOURNALS: &[(u32, u16)] = &[(2, 35), (3, 41)];354355/// Two signed changes by one signer over the same ops: the one held, and356/// the other one, refused (history rows 459 and 461).357#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]358pub struct Evidence {359    /// The change held at those ops, when the conflict was at its id or360    /// span; `None` when the refused change's digest disagreed with the361    /// history below it.362    pub held: Option<SignedChange>,363    pub refused: SignedChange,364}365366/// Why a peer was stopped (history rows 459 and 460).367#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]368pub enum Refusal {369    /// Its signer's grants don't authorize a change of it.370    Unauthorized,371    /// A change of it depends on a refused change.372    Orphaned,373    /// Its signer signed two changes over the same ops.374    Equivocation,375}376377/// One record of a document's ledger file (`<kind>/<address>` plus378/// `lvcs_vocab::doc::LEDGER_EXT` under `.lvcs/docs/`, after its format379/// header): canonical CBOR records, concatenated, only ever appended380/// (history rows 457, 459, and 460).381#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]382pub enum LedgerRecord {383    /// A signed change the document holds.384    Change(Box<SignedChange>),385    /// Two signed changes by one signer over the same ops, kept as386    /// evidence.387    Evidence(Box<Evidence>),388    /// The document refused `peer`'s ops from counter `from` on, judging by389    /// `rules` ([`VERIFIER_RULES`], discussion:owner/671): a load forgets the390    /// refusal at older rules, so the change is judged again. `grants` is391    /// the digest of the grants it was judged under (discussion:owner/787):392    /// a document whose grants differ, or a record with none, lifts it.393    RefusedUnder {394        peer: u64,395        from: i32,396        rules: u32,397        #[serde(default, skip_serializing_if = "Option::is_none")]398        grants: Option<[u8; 32]>,399    },400    /// A merged save (discussion:owner/728). Local to this node: never401    /// synced or signed. Written in the same append as its change, before402    /// it; a load skips one whose change it doesn't hold.403    MergedSave(MergedSave),404}405406/// The tree save that committed the change holding op `change` wrote other407/// text than the disk held (merged, or with lines kept): what it inserted408/// names no author for the deletion guard (discussion:owner/728). `digest`409/// is that change's, so a record a torn tail left without its change never410/// binds to another change that takes the same id after a restart.411#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]412pub struct MergedSave {413    pub change: ChangeId,414    #[serde(with = "crate::cbor::fixed")]415    pub digest: [u8; 32],416}