aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/remake/delta.rs174
1 files changed, 143 insertions, 31 deletions
diff --git a/src/remake/delta.rs b/src/remake/delta.rs
index 78a8097..388eae7 100644
--- a/src/remake/delta.rs
+++ b/src/remake/delta.rs
@@ -38,9 +38,11 @@
//! 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.
+//! 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
+//! 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, BTreeSet, HashMap, HashSet};
@@ -144,23 +146,30 @@ 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();
+ // 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
+ // same time (it may decide who may write that).
+ let mut ordered: BTreeMap<(usize, usize), Link> = BTreeMap::new();
for place in signed {
match chain(src, after, &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));
+ for (made, when, envelope, user) in chain {
+ ordered.insert((made, ordered.len()), (when, place.clone(), envelope, user));
}
}
Chain::Held => stats.superseded += 1,
Chain::Broken(why) => stats.quarantined.push((place, why)),
}
}
+ let mut at = i64::MIN;
+ let links: Vec<Link> = ordered
+ .into_values()
+ .map(|(when, place, envelope, user)| {
+ at = at.max(when);
+ (at, place, envelope, user)
+ })
+ .collect();
for (path, (at, user)) in paths.into_iter().zip(ours) {
if user.is_none() && others_entry(&path, node) {
continue;
@@ -182,10 +191,10 @@ pub(crate) fn replay_newest(
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()
+ while let Some((when, ..)) = links.peek()
&& *when <= at
{
- let ((when, _), (place, envelope, signer)) = links.next().expect("peeked");
+ let (when, place, envelope, signer) = links.next().expect("peeked");
write_link(
dst,
epoch,
@@ -237,7 +246,7 @@ pub(crate) fn replay_newest(
}
}
}
- for ((when, _), (place, envelope, signer)) in links {
+ for (when, place, envelope, signer) in links {
write_link(
dst,
epoch,
@@ -393,10 +402,14 @@ 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);
+
/// 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 envelopes to write, in order, each with where its change is among those
+ /// replayed (`between`), its time and its signer.
+ Links(Vec<(usize, 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.
@@ -433,9 +446,10 @@ fn chain(
{
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 {
+ // Every envelope the changes left at the place, by its digest, with where its first
+ // change is among them and its time.
+ let mut known: HashMap<String, (usize, i64, String)> = HashMap::new();
+ for (made, hash) in changes.iter().enumerate() {
let wrote = store::changed_by(src, hash, InLists::Whole)
.is_some_and(|paths| paths.iter().any(|path| path == place));
let Some(at) = wrote
@@ -452,7 +466,7 @@ fn chain(
&& envelope::read(&text).is_ok()
{
let digest = envelope::digest(Some(&text));
- known.entry(digest).or_insert((time, text));
+ known.entry(digest).or_insert((made, time, text));
}
}
}
@@ -463,16 +477,16 @@ fn chain(
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
+ let (made, time) = known
.get(&envelope::digest(Some(&current)))
- .map_or(0, |(time, _)| *time);
+ .map_or((changes.len(), 0), |(made, time, _)| (*made, *time));
let prev = payload.prev.clone();
- links.push((time, current, payload.user));
+ links.push((made, time, current, payload.user));
if prev == from {
break;
}
match known.get(&prev) {
- Some((_, before)) if links.len() <= known.len() => current = before.clone(),
+ 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(),
@@ -481,6 +495,12 @@ fn chain(
}
}
links.reverse();
+ // Each after the one it replaces, as written.
+ let mut made = 0;
+ for link in &mut links {
+ made = made.max(link.0);
+ link.0 = made;
+ }
Chain::Links(links)
}
@@ -506,23 +526,51 @@ fn judged(
}
/// The changes of `doc` after `before` up to `after`: those `after` builds on that
-/// `before` doesn't.
+/// `before` doesn't, each after those it builds on; of changes neither builds on, the
+/// earlier by its clock first, then the lower hash.
fn between(doc: &Document, before: &[ChangeHash], after: &[ChangeHash]) -> Vec<ChangeHash> {
- let deps: HashMap<ChangeHash, Vec<ChangeHash>> = doc
+ let all: HashMap<ChangeHash, (i64, Vec<ChangeHash>)> = doc
.get_changes(before)
.iter()
- .map(|change| (change.hash(), change.deps().to_vec()))
+ .map(|change| (change.hash(), (change.timestamp(), change.deps().to_vec())))
.collect();
let mut found = HashSet::new();
let mut todo: Vec<ChangeHash> = after.to_vec();
while let Some(hash) = todo.pop() {
- if let Some(parents) = deps.get(&hash)
+ if let Some((_, parents)) = all.get(&hash)
&& found.insert(hash)
{
todo.extend(parents.iter().copied());
}
}
- found.into_iter().collect()
+ let mut waiting: HashMap<ChangeHash, usize> = HashMap::new();
+ let mut builders: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new();
+ let mut ready: BTreeSet<(i64, ChangeHash)> = BTreeSet::new();
+ for hash in &found {
+ let (time, parents) = &all[hash];
+ let inside: Vec<&ChangeHash> = parents.iter().filter(|p| found.contains(*p)).collect();
+ for parent in &inside {
+ builders.entry(**parent).or_default().push(*hash);
+ }
+ if inside.is_empty() {
+ ready.insert((*time, *hash));
+ } else {
+ waiting.insert(*hash, inside.len());
+ }
+ }
+ let mut ordered = Vec::with_capacity(found.len());
+ while let Some((_, hash)) = ready.pop_first() {
+ ordered.push(hash);
+ for builder in builders.remove(&hash).unwrap_or_default() {
+ let left = waiting.get_mut(&builder).expect("waits for its parents");
+ *left -= 1;
+ if *left == 0 {
+ waiting.remove(&builder);
+ ready.insert((all[&builder].0, builder));
+ }
+ }
+ }
+ ordered
}
/// A change's time, the user it names (`replica::user_of`), and the store paths it
@@ -1105,11 +1153,20 @@ mod tests {
}
fn signed_after(key: &ed25519_dalek::SigningKey, prev: Option<&str>, value: i64) -> String {
+ signed_at(key, "config", prev, value)
+ }
+
+ fn signed_at(
+ key: &ed25519_dalek::SigningKey,
+ place: &str,
+ 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()],
+ path: vec![place.to_owned()],
user: "alice".to_owned(),
at: 1,
seq: prev.and_then(envelope::seq).map_or(0, |seq| seq + 1),
@@ -1120,8 +1177,12 @@ mod tests {
}
fn alice_writes(doc: &mut Document, at: i64, envelope: &str) {
+ alice_writes_at(doc, at, "config", envelope);
+ }
+
+ fn alice_writes_at(doc: &mut Document, at: i64, place: &str, envelope: &str) {
let mut transaction = doc.transaction();
- store::write_path(&mut transaction, &["config".to_owned()], &json!(envelope)).unwrap();
+ store::write_path(&mut transaction, &[place.to_owned()], &json!(envelope)).unwrap();
transaction.commit_with(
automerge::transaction::CommitOptions::default()
.with_time(at)
@@ -1226,6 +1287,57 @@ mod tests {
);
}
+ /// The links of several places replayed in the order their changes were made, each
+ /// after those it builds on, whatever the clocks say.
+ #[test]
+ fn signed_values_replay_in_the_order_written() {
+ 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("other"), &[Right::Write][..]),
+ ],
+ );
+ alice["keys"] = json!({ "k": sshsig::PublicKey(key.verifying_key().to_bytes()).line() });
+ change(&mut old, |doc| {
+ store::write_path(
+ doc,
+ &path("_continuum/access/userSigned"),
+ &json!([["config"], ["other"]]),
+ )
+ .unwrap();
+ 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();
+ // The second made after the first, by a clock that is behind.
+ alice_writes_at(&mut old, 50, "config", &signed_at(&key, "config", None, 1));
+ alice_writes_at(&mut old, 10, "other", &signed_at(&key, "other", None, 2));
+ 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("other")]]);
+ }
+
/// 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]