docs/generated/contracts.mdgenerated from code
Reference · 11 min read
loro-change
Contracts: loro-change.
Read as
Source: crates/lvcs-doc/src/change.rs.
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}