aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-15 18:43:13 +0000
committertv <tv@krebsco.de>2026-11-15 18:43:13 +0000
commitf3bfea8ebda0fa7efe1fd9ed6fe670ddb544d38e (patch)
treea5e8a6049dafd001fb52b0da5b7698e8a4f9dc70
parent5866291a3752342ff954c39d728384dfe7ff02f8 (diff)
rules: the time before strict is the change that turned it, written again or not
A change written under a policy that isn't strict was refused, in a strict document, unless it was in the history of the change that wrote the policy value the document read now. So the policy written again by a node that held a change from before, taken beside the strict policy, put that change in the new writer's history: that node kept it, every other node refused it, and the new policy with it, and the node was cut off. Now the reference is the change that turned the swarm strict: one that wrote a strict policy where the policy at its history wasn't, found by following back the writes of what the policy holds (`store::writers`). A change written under a policy that isn't strict is refused where such a change is beside it, neither in its history nor built on it. A policy written again, strict over strict, names the same change. One turning the swarm strict beside it is refused like any other. Of two at once neither is preferred: any rule choosing one, the lower hash say, would let a change made later to look as old take the place of the one every node took, and every node would drop it with all that was built on it. So two members turning a swarm strict at once split the nodes that took one from those that took the other; access.md says to turn it from one.
-rw-r--r--docs/access.md15
-rw-r--r--src/access/rules.rs92
-rw-r--r--src/document/changes.rs12
-rw-r--r--src/document/store.rs69
4 files changed, 146 insertions, 42 deletions
diff --git a/docs/access.md b/docs/access.md
index b64bd21..c4ce295 100644
--- a/docs/access.md
+++ b/docs/access.md
@@ -472,12 +472,17 @@ through a remake (Turning a swarm strict, below), which keeps only what an opera
looked over. Writing the strict policy into it directly trusts it as it is: look it
over first (`continuum-signed verify` on each entry). From then on nothing is added to
the time before: a change written under a policy that isn't strict is refused, received
-or held, unless it is in the history of the change that wrote the strict policy, so a
-member can't plant at that time what nobody could follow; a node that took one beside
-that change drops it once a peer tells it so (Changes judged on every node, below). A
+or held, where the change that turned the swarm strict (that wrote the strict policy
+under one that wasn't) is neither in its history nor built on it, so a member can't
+plant at that time what nobody could follow; a node that took one beside that change
+drops it once a peer tells it so (Changes judged on every node, below). The policy
+written again later doesn't change which change that is. One written beside it is
+refused like any other, even one turning the swarm strict too, so a change made later
+to look as old can't take its place: two members turning a swarm strict at once split
+the nodes that took one from those that took the other, so it is turned from one. A
value there that isn't an envelope starts its chain anew: any envelope its user once
-signed for that path replacing nothing (`prev` empty) can be put there again. Without the policy, signed values may
-be written all the same, and plain ones too.
+signed for that path replacing nothing (`prev` empty) can be put there again. Without
+the policy, signed values may be written all the same, and plain ones too.
Keep two users who may manage users, or two keys each: under a strict policy, a
registry whose only manager lost its keys changes no more (the protocol writers do
diff --git a/src/access/rules.rs b/src/access/rules.rs
index 0690696..43404cf 100644
--- a/src/access/rules.rs
+++ b/src/access/rules.rs
@@ -29,13 +29,14 @@
//! any member may. A change written while the document had no policy (at its
//! dependencies) is judged by none: the rules hold from the policy on.
-use std::collections::{BTreeSet, HashMap};
+use std::collections::{BTreeSet, HashMap, HashSet};
use crate::access::policy::Policy;
use crate::access::registry;
use crate::access::sealed::Declared;
use crate::access::{Caps, Right};
use crate::document::at::At;
+use crate::document::changes::in_history;
use crate::document::inspect::{Action, Op, Path};
use crate::document::meta;
use crate::document::replica::Epoch;
@@ -351,28 +352,53 @@ pub(crate) fn judge_reading(
}
/// Why `change`, written under a policy that isn't strict, is refused where `doc`'s is:
-/// it isn't in the history of the change that wrote the policy `doc` reads. Nothing is
-/// added to the time before a swarm turned strict, so nothing planted there can stand
-/// where every value is its user's to sign; what a node held of it beside that change
-/// it drops, once told (`swarm::refusals`). A swarm strict from its genesis change
-/// (`--bootstrap-policy`) has no such time. None where `doc`'s policy isn't strict:
-/// there, nothing changes.
+/// a change that turned the swarm strict is beside it, neither in its history nor
+/// built on it. Nothing is added to the time before a swarm turned strict, so nothing
+/// planted there can stand where every value is its user's to sign; what a node held of
+/// it beside that change it drops, once told (`swarm::refusals`). A policy written again
+/// later, strict over strict, names the same change; one written beside it, strict or
+/// not, is refused like any other, so a change made later to look as old can't take its
+/// place. A swarm strict from its genesis change (`--bootstrap-policy`) has no such
+/// time. None where `doc`'s policy isn't strict: there, nothing changes.
fn before_strict(doc: &Document, change: &Change<'_>) -> Option<String> {
if !super::policy::of(doc).strict() {
return None;
}
- let policy = store::written_by(doc, &super::policy::path())?;
- let before = change.hash == policy
- || (crate::document::changes::holds(doc, &change.hash)
- && !doc
- .get_changes(&[policy])
- .iter()
- .any(|later| later.hash() == change.hash));
- (!before).then(|| {
- format!(
- "written before the swarm turned strict, beside the change that turned it ({policy})"
- )
- })
+ let held = crate::document::changes::holds(doc, &change.hash);
+ let beside = turned_strict(doc).into_iter().find(|turned| {
+ *turned != change.hash
+ && !in_history(doc, turned, change.deps)
+ && !(held && in_history(doc, &change.hash, std::slice::from_ref(turned)))
+ })?;
+ Some(format!(
+ "written before the swarm turned strict, beside the change that turned it ({beside})"
+ ))
+}
+
+/// The changes that turned `doc` strict: each wrote a strict policy where the one at its
+/// history wasn't. Found by following back the writes of what the policy holds, each
+/// write's history in turn, so every one is found however often the policy was written
+/// since.
+fn turned_strict(doc: &Document) -> Vec<ChangeHash> {
+ let path = super::policy::path();
+ let strict_at = |heads: &[ChangeHash]| {
+ At::new(doc, heads).is_some_and(|at| super::policy::of(&at).strict())
+ };
+ let mut turned = Vec::new();
+ let mut looked: HashSet<ChangeHash> = HashSet::new();
+ let mut writes = store::writers(doc, doc, &path);
+ while let Some((hash, deps)) = writes.pop() {
+ if !looked.insert(hash) {
+ continue;
+ }
+ if strict_at(&[hash]) && !strict_at(&deps) {
+ turned.push(hash);
+ }
+ if let Some(before) = At::new(doc, &deps) {
+ writes.extend(store::writers(doc, &before, &path));
+ }
+ }
+ turned
}
/// `hash`, which `doc` (of `epoch`) holds, judged by its rules now, as received: why
@@ -1192,6 +1218,34 @@ mod tests {
Some(Err(_))
));
assert_eq!(judge_held(&doc, Epoch::GENESIS, &kept), Some(Ok(())));
+ // The policy written again, by a change that saw the one beside: the change that
+ // turned the swarm strict is still the one, and the one beside still refused.
+ let mut again = doc.clone();
+ write(
+ &mut again,
+ "_continuum/access/policy",
+ json!({"version": 1, "values": "signed"}),
+ );
+ assert!(matches!(
+ judge_held(&again, Epoch::GENESIS, &planted),
+ Some(Err(_))
+ ));
+ assert_eq!(judge_held(&again, Epoch::GENESIS, &kept), Some(Ok(())));
+ // Turned strict beside it too: refused all the same, so a change made later to
+ // look as old can't take its place.
+ let mut rival = beside.fork_at(&before).unwrap();
+ write(
+ &mut rival,
+ "_continuum/access/policy",
+ json!({"version": 1, "values": "signed"}),
+ );
+ let rival_hash = rival.get_heads()[0];
+ let mut both = doc.clone();
+ both.merge(&mut rival).unwrap();
+ assert!(matches!(
+ judge_held(&both, Epoch::GENESIS, &rival_hash),
+ Some(Err(_))
+ ));
// Received, from the time before: refused too.
let touched = paths(&["notes/late"]);
assert!(refused(judge(
diff --git a/src/document/changes.rs b/src/document/changes.rs
index 800ea19..e1cbe21 100644
--- a/src/document/changes.rs
+++ b/src/document/changes.rs
@@ -28,6 +28,18 @@ pub(crate) fn holds_all(doc: &impl ReadDoc, heads: &[ChangeHash]) -> bool {
heads.iter().all(|head| holds(doc, head))
}
+/// Whether `hash` is in the history of `heads`, which `doc` holds: one of them, or one
+/// they build on.
+pub(crate) fn in_history(doc: &Document, hash: &ChangeHash, heads: &[ChangeHash]) -> bool {
+ heads.contains(hash)
+ || (holds(doc, hash)
+ && holds_all(doc, heads)
+ && !doc
+ .get_changes(heads)
+ .iter()
+ .any(|later| later.hash() == *hash))
+}
+
/// Whether the history of `theirs` (of them, those `doc` has) holds all of `ours`
/// (heads of `doc`): a peer at `theirs` has every change we have.
pub(crate) fn covers(doc: &Document, theirs: &[ChangeHash], ours: &[ChangeHash]) -> bool {
diff --git a/src/document/store.rs b/src/document/store.rs
index bc50535..759d188 100644
--- a/src/document/store.rs
+++ b/src/document/store.rs
@@ -258,25 +258,58 @@ fn signs_values(doc: &impl ReadDoc) -> bool {
})
}
-/// The change that wrote the value a read of `path` shows (`candidates`), if `doc` holds
-/// one there.
-pub(crate) fn written_by(doc: &Automerge, path: &[String]) -> Option<automerge::ChangeHash> {
- let (leaf, parents) = path.split_last()?;
- let Some(Resolved::Maps(maps)) = resolve_through(doc, parents).ok()? else {
- return None;
- };
- let (_, id) = candidates(doc, &maps, leaf.as_str())
- .ok()?
+/// The changes that wrote what `path` holds as `view` (of `doc`) shows it: each value
+/// written there at once and, of a map, every key within it, all the way down; each
+/// with the changes it builds on.
+pub(crate) fn writers(
+ doc: &Automerge,
+ view: &impl ReadDoc,
+ path: &[String],
+) -> Vec<(automerge::ChangeHash, Vec<automerge::ChangeHash>)> {
+ let mut ids = Vec::new();
+ if let Some((leaf, parents)) = path.split_last()
+ && let Ok(Some(Resolved::Maps(maps))) = resolve_through(view, parents)
+ {
+ operations_within(view, &maps, leaf.as_str().into(), &mut ids);
+ }
+ if ids.is_empty() {
+ return Vec::new();
+ }
+ doc.get_changes(&[])
.into_iter()
- .next()?;
- let ObjId::Id(counter, actor, _) = id else {
- return None;
- };
- doc.get_changes(&[]).into_iter().find_map(|change| {
- let start = change.start_op().get();
- (change.actor_id() == &actor && (start..start + change.len() as u64).contains(&counter))
- .then(|| change.hash())
- })
+ .filter(|change| {
+ let start = change.start_op().get();
+ let made = start..start + change.len() as u64;
+ ids.iter()
+ .any(|(counter, actor)| change.actor_id() == actor && made.contains(counter))
+ })
+ .map(|change| (change.hash(), change.deps().to_vec()))
+ .collect()
+}
+
+/// The operations that wrote `prop` of `parents` as `view` shows it, and, of a map,
+/// every key within it.
+fn operations_within(
+ view: &impl ReadDoc,
+ parents: &[ObjId],
+ prop: Prop,
+ ids: &mut Vec<(u64, ActorId)>,
+) {
+ for parent in parents {
+ let Ok(all) = view.get_all(parent, prop.clone()) else {
+ continue;
+ };
+ for (value, id) in all {
+ if let ObjId::Id(counter, actor, _) = &id {
+ ids.push((*counter, actor.clone()));
+ }
+ if matches!(value, Value::Object(ObjType::Map)) {
+ for key in view.keys(&id) {
+ operations_within(view, std::slice::from_ref(&id), key.into(), ids);
+ }
+ }
+ }
+ }
}
/// What `prop` of `parent` holds as a read shows it, of the values written there at