aboutsummaryrefslogtreecommitdiffstats
path: root/src/remake
diff options
context:
space:
mode:
Diffstat (limited to 'src/remake')
-rw-r--r--src/remake/delta.rs402
1 files changed, 399 insertions, 3 deletions
diff --git a/src/remake/delta.rs b/src/remake/delta.rs
index a152861..c8e07c0 100644
--- a/src/remake/delta.rs
+++ b/src/remake/delta.rs
@@ -32,14 +32,25 @@
//! document touched it (or a path above or below it) later than the write being
//! replayed, as the changes' timestamps say; and the replayed changes carry the times
//! of the writes they replay, not of the replay, so later replays judge by those.
+//!
+//! Under a strict policy, a value its user signed (`access::envelope`) is replayed as
+//! the chain that leads to it ([`signed_places`], [`chain`]): every envelope from the
+//! one the new document holds there to the one the old document reads, each in a
+//! 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. 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.
-use std::collections::{BTreeMap, HashMap, HashSet};
+use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use crate::document::{ActorId, ChangeHash, Document, ReadDoc, Transactable};
use serde::{Deserialize, Serialize};
use tracing::{info, warn};
use super::kind::{Translation, Translator};
+use crate::access::envelope;
+use crate::document::at::At;
use crate::document::meta::{self, EPOCHS, REMAKES, VOTES};
use crate::document::store::{self, InLists, StoreError};
@@ -102,9 +113,18 @@ pub(crate) fn replay_newest(
if before == after {
return stats;
}
- let written = touched(src, &between(src, before, after));
+ let changes = between(src, before, after);
+ let written = touched(src, &changes);
+ // Values their users signed, under a strict policy: replayed as chains, below.
+ let (signed, paths) = signed_places(
+ src,
+ before,
+ after,
+ &written,
+ changed_paths(src, before, after),
+ );
// Split where several users wrote below a path: each part replayed for its own.
- let paths = by_user(src, dst, &written, changed_paths(src, before, after));
+ let paths = by_user(src, dst, &written, paths);
let ours: Vec<(i64, Option<String>)> = paths
.iter()
.map(|path| {
@@ -124,6 +144,23 @@ pub(crate) fn replay_newest(
let theirs = touched(dst, &newer);
let mut by_time: BTreeMap<(i64, Option<String>), Vec<Vec<String>>> = BTreeMap::new();
+ // The links of the chains to signed values, each a change of its own, before what is
+ // written at the same time (it may decide who may write that).
+ let mut links: BTreeMap<(i64, usize), (Vec<String>, String, String)> = BTreeMap::new();
+ for place in signed {
+ match chain(src, &changes, &place, dst) {
+ Chain::Links(chain) => {
+ // In their order, whatever their clocks say.
+ let mut at = i64::MIN;
+ for (when, envelope, user) in chain {
+ at = at.max(when);
+ links.insert((at, links.len()), (place.clone(), envelope, user));
+ }
+ }
+ Chain::Held => stats.superseded += 1,
+ Chain::Broken(why) => stats.quarantined.push((place, why)),
+ }
+ }
for (path, (at, user)) in paths.into_iter().zip(ours) {
if user.is_none() && others_entry(&path, node) {
continue;
@@ -142,7 +179,25 @@ pub(crate) fn replay_newest(
}
}
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
+ {
+ let ((when, _), (place, envelope, signer)) = links.next().expect("peeked");
+ write_link(
+ dst,
+ epoch,
+ node,
+ when,
+ &place,
+ envelope,
+ &signer,
+ &mut refused,
+ &mut stats,
+ );
+ }
let before = dst.get_heads();
let mut transaction = dst.transaction();
let group = replay_paths(src, &mut transaction, &paths, translator);
@@ -182,6 +237,19 @@ pub(crate) fn replay_newest(
}
}
}
+ for ((when, _), (place, envelope, signer)) in links {
+ write_link(
+ dst,
+ epoch,
+ node,
+ when,
+ &place,
+ envelope,
+ &signer,
+ &mut refused,
+ &mut stats,
+ );
+ }
if stats.superseded > 0 {
info!(
superseded = stats.superseded,
@@ -196,6 +264,216 @@ pub(crate) fn replay_newest(
stats
}
+/// Writes `envelope` at `place` in `dst`, a change of its own by `node` for `signer` at
+/// `at`, judged as every node will judge it: one they would refuse is taken back, and
+/// its place quarantined, and nothing more of that place's chain written.
+#[allow(clippy::too_many_arguments)]
+fn write_link(
+ dst: &mut Document,
+ epoch: crate::document::replica::Epoch,
+ node: &str,
+ at: i64,
+ place: &[String],
+ envelope: String,
+ signer: &str,
+ refused: &mut HashSet<Vec<String>>,
+ stats: &mut ReplayStats,
+) {
+ if refused.contains(place) {
+ return;
+ }
+ let before = dst.get_heads();
+ let mut transaction = dst.transaction();
+ if let Err(error) = store::write_path(
+ &mut transaction,
+ place,
+ &serde_json::Value::String(envelope),
+ ) {
+ transaction.rollback();
+ log_failure(place, &error);
+ stats.failed += 1;
+ refused.insert(place.to_vec());
+ return;
+ }
+ let writer = crate::document::replica::Writer {
+ node,
+ user: Some(signer),
+ };
+ let mut options = automerge::transaction::CommitOptions::default().with_time(at);
+ if let Some(message) = writer.message() {
+ options = options.with_message(message);
+ }
+ transaction.commit_with(options);
+ match judged(dst, epoch, &before) {
+ Ok(()) => stats.replayed += 1,
+ Err(why) => {
+ let actor = dst.get_actor().clone();
+ match dst.fork_at(&before) {
+ Ok(kept) => {
+ *dst = kept.with_actor(actor);
+ crate::document::replica::authored(dst, node);
+ }
+ Err(error) => {
+ warn!(error = %error, "Could not take back a replay every node would refuse");
+ stats.replayed += 1;
+ return;
+ }
+ }
+ refused.insert(place.to_vec());
+ stats
+ .quarantined
+ .push((place.to_vec(), format!("every node would refuse it: {why}")));
+ }
+ }
+}
+
+/// Under a strict policy in `src` at `after` (`access::policy`), the places of values
+/// their users sign (`access::envelope::signed_paths`) whose value, as a read shows it,
+/// changed between `before` and `after`: found among `paths` (from the diff) and among
+/// the paths the changes wrote (`written`), a path above such places split into its
+/// keys. And the rest of `paths`. Without a strict policy, none, and `paths` as they are.
+fn signed_places(
+ src: &Document,
+ before: &[ChangeHash],
+ after: &[ChangeHash],
+ written: &[Touched],
+ paths: Vec<Vec<String>>,
+) -> (Vec<Vec<String>>, Vec<Vec<String>>) {
+ let (Some(then), Some(now)) = (At::new(src, before), At::new(src, after)) else {
+ return (Vec::new(), paths);
+ };
+ if !crate::access::policy::of(&now).strict() {
+ return (Vec::new(), paths);
+ }
+ let signed = envelope::signed_paths(&now);
+ let mut places = BTreeSet::new();
+ let mut rest = Vec::new();
+ let mut todo: Vec<Vec<String>> = paths;
+ todo.extend(
+ written
+ .iter()
+ .flat_map(|(_, _, paths)| paths.iter())
+ .filter(|path| envelope::is_signed(&signed, path))
+ .cloned(),
+ );
+ while let Some(path) = todo.pop() {
+ if envelope::is_signed(&signed, &path) {
+ places.insert(path);
+ } else if envelope::above_signed(&signed, &path) {
+ let mut keys = store::keys_at(&now, &path)
+ .ok()
+ .flatten()
+ .unwrap_or_default();
+ keys.extend(
+ store::keys_at(&then, &path)
+ .ok()
+ .flatten()
+ .unwrap_or_default(),
+ );
+ keys.sort();
+ keys.dedup();
+ for key in &keys {
+ let mut child = path.clone();
+ child.push(key.clone());
+ todo.push(child);
+ }
+ if keys.is_empty() {
+ rest.push(path);
+ }
+ } else {
+ rest.push(path);
+ }
+ }
+ rest.sort();
+ rest.dedup();
+ let places = places
+ .into_iter()
+ .filter(|place| store::read_path(&then, place).ok() != store::read_path(&now, place).ok())
+ .collect();
+ (places, rest)
+}
+
+/// What replaying a signed place takes.
+enum Chain {
+ /// The envelopes to write, in order, each with its change's time and its signer.
+ Links(Vec<(i64, String, String)>),
+ /// The new document holds as high a `seq` there already.
+ Held,
+ /// No chain leads there from what the new document holds: why.
+ Broken(String),
+}
+
+/// The chain of envelopes `src` holds at `place` (written by `changes`) that leads from
+/// what `dst` holds there to what `src` reads there, following `prev`.
+fn chain(src: &Document, changes: &[ChangeHash], place: &[String], dst: &Document) -> Chain {
+ let raw = |doc: &dyn Fn() -> Option<serde_json::Value>| match doc() {
+ Some(serde_json::Value::String(text)) => Some(text),
+ _ => None,
+ };
+ let Some(target) = raw(&|| store::read_path(src, place).ok().flatten()) else {
+ return Chain::Broken("no value its user signed is there to replay".to_owned());
+ };
+ let Ok(payload) = envelope::read(&target) else {
+ return Chain::Broken("what is there isn't a value its user signed".to_owned());
+ };
+ let held = raw(&|| store::read_path(dst, place).ok().flatten())
+ .filter(|text| envelope::read(text).is_ok());
+ if let Some(seq) = held.as_deref().and_then(envelope::seq)
+ && seq >= payload.seq
+ {
+ return Chain::Held;
+ }
+ // Every envelope the changes left at the place, by its digest, with its time.
+ let mut known: HashMap<String, (i64, String)> = HashMap::new();
+ for hash in changes {
+ let wrote = store::changed_by(src, hash, InLists::Whole)
+ .is_some_and(|paths| paths.iter().any(|path| path == place));
+ let Some(at) = wrote
+ .then(|| At::new(src, std::slice::from_ref(hash)))
+ .flatten()
+ else {
+ continue;
+ };
+ let time = src
+ .get_change_by_hash(hash)
+ .map_or(0, |change| change.timestamp());
+ for value in store::read_candidates(&at, place).unwrap_or_default() {
+ if let serde_json::Value::String(text) = value
+ && envelope::read(&text).is_ok()
+ {
+ let digest = envelope::digest(Some(&text));
+ known.entry(digest).or_insert((time, text));
+ }
+ }
+ }
+ let from = envelope::digest(held.as_deref());
+ let mut links = Vec::new();
+ let mut current = target;
+ loop {
+ let Ok(payload) = envelope::read(&current) else {
+ return Chain::Broken("a link of its chain isn't a value its user signed".to_owned());
+ };
+ let time = known
+ .get(&envelope::digest(Some(&current)))
+ .map_or(0, |(time, _)| *time);
+ let prev = payload.prev.clone();
+ links.push((time, current, payload.user));
+ if prev == from {
+ break;
+ }
+ match known.get(&prev) {
+ Some((_, before)) if links.len() <= known.len() => current = before.clone(),
+ _ => {
+ return Chain::Broken(
+ "the new epoch holds another value there, not one it replaced".to_owned(),
+ );
+ }
+ }
+ }
+ links.reverse();
+ Chain::Links(links)
+}
+
/// The change just committed to `doc` (the one head after `before`), judged under a
/// policy as every node will judge it on receipt; why it is refused, if it is.
fn judged(
@@ -783,6 +1061,124 @@ mod tests {
assert!(store::read_path(&new, &path("notes/y")).unwrap().is_none());
}
+ /// A strict swarm's document, with alice, whose key is `key`, writing `config`,
+ /// a value its user signs; and the envelope alice signs there, after `prev`.
+ fn strict_with(key: &ed25519_dalek::SigningKey) -> Document {
+ use crate::access::sshsig;
+ let path = |text: &str| -> Vec<String> { text.split('/').map(str::to_owned).collect() };
+ let mut alice = crate::access::registry::entry(
+ "root",
+ 1,
+ &[(path("config"), &[crate::access::Right::Write][..])],
+ );
+ alice["keys"] = json!({ "k": sshsig::PublicKey(key.verifying_key().to_bytes()).line() });
+ let mut doc = Document::new();
+ change(&mut doc, |doc| {
+ store::write_path(doc, &path("_continuum/swarm"), &json!("s")).unwrap();
+ store::write_path(
+ doc,
+ &path("_continuum/access/policy"),
+ &json!({"version": 1, "values": "signed"}),
+ )
+ .unwrap();
+ store::write_path(
+ doc,
+ &path("_continuum/access/userSigned"),
+ &json!([["config"]]),
+ )
+ .unwrap();
+ store::write_path(doc, &path("_continuum/members/node"), &json!({})).unwrap();
+ store::write_path(doc, &path("_continuum/users/alice"), &alice).unwrap();
+ });
+ crate::document::replica::authored(&mut doc, "node");
+ doc
+ }
+
+ fn signed_after(key: &ed25519_dalek::SigningKey, prev: Option<&str>, value: i64) -> String {
+ use crate::access::sshsig;
+ let payload = crate::document::signed::Payload {
+ value: json!(value),
+ swarm: "s".to_owned(),
+ path: vec!["config".to_owned()],
+ user: "alice".to_owned(),
+ at: 1,
+ seq: prev.and_then(envelope::seq).map_or(0, |seq| seq + 1),
+ prev: envelope::digest(prev),
+ };
+ let bytes = payload.signed();
+ envelope::seal(&bytes, &sshsig::sign(key, envelope::NAMESPACE, &bytes)).unwrap()
+ }
+
+ fn alice_writes(doc: &mut Document, at: i64, envelope: &str) {
+ let mut transaction = doc.transaction();
+ store::write_path(&mut transaction, &["config".to_owned()], &json!(envelope)).unwrap();
+ transaction.commit_with(
+ automerge::transaction::CommitOptions::default()
+ .with_time(at)
+ .with_message("User: alice".to_owned()),
+ );
+ }
+
+ /// Under a strict policy, a value its user signed, written twice since the base, is
+ /// replayed as its chain: each envelope after the one the new document holds, in
+ /// order, so that every node takes each. Of two written at once, only the one the
+ /// chain leads through.
+ #[test]
+ fn signed_values_replay_as_chains() {
+ let key = ed25519_dalek::SigningKey::from_bytes(&[7; 32]);
+ let mut old = strict_with(&key);
+ let first = signed_after(&key, None, 1);
+ alice_writes(&mut old, 5, &first);
+ let base = old.get_heads();
+ let new = old.clone().with_actor(automerge::ActorId::random());
+
+ // Two written at once after the first, and one more after the second of them.
+ let mut side = old.fork_at(&base).unwrap();
+ let aside = signed_after(&key, Some(&first), 2);
+ alice_writes(&mut side, 10, &aside);
+ let second = signed_after(&key, Some(&first), 3);
+ alice_writes(&mut old, 10, &second);
+ let third = signed_after(&key, Some(&second), 4);
+ alice_writes(&mut old, 20, &third);
+ old.merge(&mut side).unwrap();
+ assert_eq!(
+ store::read_path(&old, &["config".to_owned()]).unwrap(),
+ Some(json!(third))
+ );
+
+ let mut replayed = new.clone();
+ 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);
+ assert_eq!(stats.replayed, 2);
+ assert_eq!(
+ store::read_candidates(&replayed, &["config".to_owned()]).unwrap(),
+ [json!(third)]
+ );
+
+ // Where the new document holds as high a `seq` already: nothing.
+ let stats = replay_newest(
+ &old,
+ &base,
+ &old.get_heads(),
+ &mut replayed,
+ crate::document::replica::Epoch::GENESIS,
+ "node",
+ &Translator::default(),
+ Superseded::Drop,
+ );
+ assert_eq!(stats.replayed, 0);
+ assert!(stats.quarantined.is_empty());
+ }
+
/// 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]