aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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