aboutsummaryrefslogtreecommitdiffstats
path: root/src/remake/delta.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-15 20:21:11 +0000
committertv <tv@krebsco.de>2026-11-15 20:21:11 +0000
commitc96470e4a28f69a640812998b8226faa52bc8d38 (patch)
tree5e56d8e3613cb55ee31719ca6bbdce357516393d /src/remake/delta.rs
parent2c64def2981354c341cae2bcbf871456876b8ea3 (diff)
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.
Diffstat (limited to 'src/remake/delta.rs')
-rw-r--r--src/remake/delta.rs134
1 files changed, 111 insertions, 23 deletions
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<String>), Vec<Vec<String>>> = 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<Link> = 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<Vec<String>> = 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, 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, String);
+
+/// The other writes, by when they go and their user: their time, and their paths.
+type Groups = BTreeMap<(i64, Option<String>), (i64, Vec<Vec<String>>)>;
/// What replaying a signed place takes.
enum Chain {
@@ -585,24 +610,36 @@ fn between(doc: &Document, before: &[ChangeHash], after: &[ChangeHash]) -> Vec<C
/// touched.
type Touched = (i64, Option<String>, Vec<Vec<String>>);
-/// 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<Touched> {
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<usize> {
+ 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<String>)> {
@@ -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<String> { 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<Vec<Vec<String>>> = 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]