diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/access/rules.rs | 92 | ||||
| -rw-r--r-- | src/document/changes.rs | 12 | ||||
| -rw-r--r-- | src/document/store.rs | 69 |
3 files changed, 136 insertions, 37 deletions
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 |
