From c96470e4a28f69a640812998b8226faa52bc8d38 Mon Sep 17 00:00:00 2001 From: tv Date: Sun, 15 Nov 2026 20:21:11 +0000 Subject: remakes: other writes replayed with the links by history Under a strict policy, the links of the chains to signed values went in the order their changes were made, but the other writes were grouped by time, and a link went before a group only where its time wasn't later. A write built on what a link grants (a capability in an entry its manager signed, a ban lifted, a declaration) went first wherever its clock was behind the link's, was judged where it wasn't granted yet, and was quarantined, though every node had taken it. Under a strict policy the other writes now go by where the last change that wrote them is among those replayed (`between`), with the links, and keep their times for later replays. Without a strict policy there are no links, and the groups go by time as before. --- src/remake/delta.rs | 134 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 111 insertions(+), 23 deletions(-) (limited to 'src') diff --git a/src/remake/delta.rs b/src/remake/delta.rs index 0d87564..defdec6 100644 --- a/src/remake/delta.rs +++ b/src/remake/delta.rs @@ -39,8 +39,9 @@ //! change of its own, by its signer, at its own time, so that each replaces the one //! before it as every node checks; and only where the new document holds a lower `seq` //! there, as values signed by their users are read by `seq`, not by clocks. The links of -//! all places go in the order their changes were made ([`between`]), clocks deciding -//! only between changes neither of which saw the other. A place is found from the +//! all places go in the order their changes were made ([`between`]), and the other +//! writes with them, clocks deciding only between changes neither of which saw the +//! other. A place is found from the //! changes' operations as well as from the diff, which says nothing of a value that //! changed beside Automerge's own choice. @@ -97,8 +98,9 @@ pub(crate) enum Superseded { /// timestamp) is older than a change in `dst` touching it, or a path above or below it, /// stays as `dst` has it (`superseded` says what becomes of the write). Ties go to the /// replay. The replayed paths are committed by `node`, grouped by the time of the writes -/// they replay and the user each was made for, each change stamped with the one and -/// naming the other. Under a policy, each is judged as every node will judge it (in +/// they replay (under a strict policy, in the order their changes were made, with the +/// links) and the user each was made for, each change stamped with that time and naming +/// that user. Under a policy, each is judged as every node will judge it (in /// `epoch`): one they would refuse is taken back, its paths quarantined. #[allow(clippy::too_many_arguments)] pub(crate) fn replay_newest( @@ -116,7 +118,11 @@ pub(crate) fn replay_newest( return stats; } let changes = between(src, before, after); + // One for each of `changes`, in their order. let written = touched(src, &changes); + // Under a strict policy, the other writes go with the links by history too: one may + // build on what a link grants (a capability, a key). + let strict = At::new(src, after).is_some_and(|now| crate::access::policy::of(&now).strict()); // Values their users signed, under a strict policy: replayed as chains, below. let (signed, paths) = signed_places( src, @@ -145,7 +151,9 @@ pub(crate) fn replay_newest( .collect(); let theirs = touched(dst, &newer); - let mut by_time: BTreeMap<(i64, Option), Vec>> = BTreeMap::new(); + // By when they go (under a strict policy, the place of the last change that wrote + // them among `changes`; elsewhere, its time) and their user: their time, and paths. + let mut by_time: Groups = BTreeMap::new(); // The links of the chains to signed values, each a change of its own: in the order // their changes were made, each after those it builds on, whatever the clocks say // (one may add the key the next is signed with); and before what is written at the @@ -155,7 +163,10 @@ pub(crate) fn replay_newest( match chain(src, after, &changes, &place, dst) { Chain::Links(chain) => { for (made, when, envelope, user) in chain { - ordered.insert((made, ordered.len()), (when, place.clone(), envelope, user)); + ordered.insert( + (made, ordered.len()), + (made as i64, when, place.clone(), envelope, user), + ); } } Chain::Held => { @@ -173,9 +184,10 @@ pub(crate) fn replay_newest( let mut at = i64::MIN; let links: Vec = ordered .into_values() - .map(|(when, place, envelope, user)| { + .map(|(made, when, place, envelope, user)| { at = at.max(when); - (at, place, envelope, user) + let goes = if strict { made } else { at }; + (goes, at, place, envelope, user) }) .collect(); for (path, (at, user)) in paths.into_iter().zip(ours) { @@ -192,17 +204,26 @@ pub(crate) fn replay_newest( )); } } - _ => by_time.entry((at, user)).or_default().push(path), + _ => { + let goes = if strict { + last_written(&written, &path).map_or(0, |made| made as i64) + } else { + at + }; + let group = by_time.entry((goes, user)).or_insert((at, Vec::new())); + group.0 = group.0.max(at); + group.1.push(path); + } } } crate::document::replica::authored(dst, node); let mut refused: HashSet> = HashSet::new(); let mut links = links.into_iter().peekable(); - for ((at, user), paths) in by_time { - while let Some((when, ..)) = links.peek() - && *when <= at + for ((goes, user), (at, paths)) in by_time { + while let Some((link_goes, ..)) = links.peek() + && *link_goes <= goes { - let (when, place, envelope, signer) = links.next().expect("peeked"); + let (_, when, place, envelope, signer) = links.next().expect("peeked"); write_link( dst, epoch, @@ -254,7 +275,7 @@ pub(crate) fn replay_newest( } } } - for (when, place, envelope, signer) in links { + for (_, when, place, envelope, signer) in links { write_link( dst, epoch, @@ -410,8 +431,12 @@ fn signed_places( (places, rest) } -/// A link to write: its time, its place, the envelope and its signer. -type Link = (i64, Vec, String, String); +/// A link to write: when it goes (as the other writes go), its time, its place, the +/// envelope and its signer. +type Link = (i64, i64, Vec, String, String); + +/// The other writes, by when they go and their user: their time, and their paths. +type Groups = BTreeMap<(i64, Option), (i64, Vec>)>; /// What replaying a signed place takes. enum Chain { @@ -585,24 +610,36 @@ fn between(doc: &Document, before: &[ChangeHash], after: &[ChangeHash]) -> Vec, Vec>); -/// For each of `changes` (in `doc`), its time, its user and the store paths it touched, -/// from its operations (`store::changed_by`: a diff per change would cost what the maps -/// it touched hold, `remake::bench`). +/// For each of `changes` (in `doc`), in their order, its time, its user and the store +/// paths it touched, from its operations (`store::changed_by`: a diff per change would +/// cost what the maps it touched hold, `remake::bench`); none for one it can't read. fn touched(doc: &Document, changes: &[ChangeHash]) -> Vec { changes .iter() - .filter_map(|hash| { - let change = doc.get_change_by_hash(hash)?; - let paths = store::changed_by(doc, hash, InLists::Whole)?; + .map(|hash| { + let Some(change) = doc.get_change_by_hash(hash) else { + return (0, None, Vec::new()); + }; + let paths = store::changed_by(doc, hash, InLists::Whole).unwrap_or_default(); let user = change .message() .and_then(|message| crate::document::replica::user_of(message)) .map(str::to_owned); - Some((change.timestamp(), user, paths)) + (change.timestamp(), user, paths) }) .collect() } +/// Where, among the changes `written` is of (`touched`, in their order), the last that +/// touched `path`, a path above it or one below it, is. +fn last_written(written: &[Touched], path: &[String]) -> Option { + written.iter().rposition(|(_, _, paths)| { + paths + .iter() + .any(|other| other.starts_with(path) || path.starts_with(other)) + }) +} + /// The time and user of the newest of `changes` that touched `path`, a path above it or /// one below it (of two at once, the user named last in order). fn newest(changes: &[Touched], path: &[String]) -> Option<(i64, Option)> { @@ -1346,6 +1383,57 @@ mod tests { assert_eq!(written, [vec![path("config")], vec![path("other")]]); } + /// Under a strict policy, the other writes go with the links by history too: one made + /// after a link, by a clock that is behind, still after it (it may build on what the + /// link grants). + #[test] + fn other_writes_replay_after_the_links_they_follow() { + use crate::access::{Right, sshsig}; + let path = |text: &str| -> Vec { text.split('/').map(str::to_owned).collect() }; + let key = ed25519_dalek::SigningKey::from_bytes(&[7; 32]); + let mut old = strict_with(&key); + let mut alice = crate::access::registry::entry( + "root", + 1, + &[ + (path("config"), &[Right::Write][..]), + (path("notes"), &[Right::Write][..]), + ], + ); + alice["keys"] = json!({ "k": sshsig::PublicKey(key.verifying_key().to_bytes()).line() }); + change(&mut old, |doc| { + store::write_path(doc, &path("_continuum/users/alice"), &alice).unwrap(); + }); + let base = old.get_heads(); + let mut replayed = old.clone().with_actor(automerge::ActorId::random()); + let since = replayed.get_heads(); + alice_writes_at(&mut old, 50, "config", &signed_at(&key, "config", None, 1)); + let mut transaction = old.transaction(); + store::write_path(&mut transaction, &path("notes"), &json!(1)).unwrap(); + transaction.commit_with( + automerge::transaction::CommitOptions::default() + .with_time(10) + .with_message("User: alice".to_owned()), + ); + let stats = replay_newest( + &old, + &base, + &old.get_heads(), + &mut replayed, + crate::document::replica::Epoch::GENESIS, + "node", + &Translator::default(), + Superseded::Drop, + ); + assert!(stats.quarantined.is_empty(), "{:?}", stats.quarantined); + let written: Vec>> = replayed + .get_changes(&since) + .iter() + .filter_map(|change| store::changed_by(&replayed, &change.hash(), InLists::Whole)) + .collect(); + assert_eq!(written, [vec![path("config")], vec![path("notes")]]); + } + /// The first group refused: those after it still replayed, still the node's (a /// fork, taking the refused one back, has no author of its own). #[test] -- cgit v1.3.1