diff options
Diffstat (limited to 'src/remake')
| -rw-r--r-- | src/remake/delta.rs | 402 |
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(¤t) 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(¤t))) + .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] |
