From b9da1b6b9a43dc4bfe1a6f99ea73342cf23c028c Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 16 Nov 2026 17:55:32 +0000 Subject: federation: versions, their rules, and the paths they match `Version::read` reads a version by itself, and says what makes one none (`docs/federation.md`, The policy): a field missing or more but for `checkpoint`, another federation, a number and `changes` that don't go together, keys and node lists not of the same parties, a party's name, its keys (one to 16, spelled as keys, none twice in the version) and its node list (up to 64 node IDs, none twice), checkpoint heads, and rules (a literal first segment and not `_continuum`, `{party}` once at most, `**` last only, a writer that is a party of it, `"{party}"` where the path holds `{party}`, or `false`; a path as a write's may be). `changes_validly` asks whether it changes another: one past its number, its hash, and each `since` its own number or the other's with the same keys, or node list. `writer` gives who writes at a path, by the first rule that matches; `only_moves_on` whether it changes nothing but its number, what it changes and its checkpoint. --- src/federation/mod.rs | 1 + src/federation/version.rs | 538 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 539 insertions(+) create mode 100644 src/federation/version.rs diff --git a/src/federation/mod.rs b/src/federation/mod.rs index 9c49e66..ddd4c4a 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -8,3 +8,4 @@ pub(crate) mod jcs; pub(crate) mod keys; pub(crate) mod store; +pub(crate) mod version; diff --git a/src/federation/version.rs b/src/federation/version.rs new file mode 100644 index 0000000..1547ec1 --- /dev/null +++ b/src/federation/version.rs @@ -0,0 +1,538 @@ +//! The policy's versions (`docs/federation.md`, The policy): what one holds, what makes it +//! none, its rules and the paths they match. + +use std::collections::{BTreeMap, BTreeSet}; + +use super::jcs::Json; +use super::keys; +use super::store::Id; + +/// The federation this is: a version naming another is none here. +pub(crate) const FEDERATION: i64 = 1; + +/// Keys a party may have, in its version or its set. +pub(crate) const KEYS: usize = 16; + +/// Nodes a node list may name. +pub(crate) const NODES: usize = 64; + +/// Segments a path may have, and bytes a segment. +pub(crate) const SEGMENTS: usize = 32; +pub(crate) const SEGMENT_BYTES: usize = 255; + +/// A version, read from its JSON. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct Version { + /// The SHA-256 of its JCS bytes, written as an ID is. + pub(crate) hash: Id, + pub(crate) json: Json, + pub(crate) number: u64, + /// The version it changes; none for the first. + pub(crate) changes: Option, + pub(crate) parties: BTreeMap, + /// The heads of the checkpoint it names, if any. + pub(crate) checkpoint: Option>, + pub(crate) rules: Vec, +} + +/// What a version gives a party: its keys and its node list, each with its `since`. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct Party { + pub(crate) keys_since: u64, + pub(crate) keys: Vec, + pub(crate) nodes_since: u64, + pub(crate) nodes: Vec, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct Rule { + pub(crate) path: Vec, + pub(crate) writer: Writer, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) enum Segment { + Literal(String), + /// `{party}`: the name of a party of the version. + Party, + /// `*`: any one segment. + One, + /// `**`, last only: one segment or more. + Rest, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) enum Writer { + /// A party of the version. + Party(String), + /// `"{party}"`: the party the path names. + Named, + /// `false`: nobody. + Nobody, +} + +/// Whether `name` is a party's name: as continuum's user names, 1 to 64 of +/// `A-Z a-z 0-9 . _ @ -`. +pub(crate) fn is_party(name: &str) -> bool { + (1..=64).contains(&name.len()) + && name + .bytes() + .all(|byte| byte.is_ascii_alphanumeric() || matches!(byte, b'.' | b'_' | b'@' | b'-')) +} + +/// A path's segments, where it is one: separated by `/`, none empty, up to `SEGMENTS` of +/// up to `SEGMENT_BYTES` each. +pub(crate) fn path(text: &str) -> Option> { + let segments: Vec = text.split('/').map(str::to_owned).collect(); + let fits = segments.len() <= SEGMENTS + && segments + .iter() + .all(|segment| !segment.is_empty() && segment.len() <= SEGMENT_BYTES); + fits.then_some(segments) +} + +/// The IDs a JSON array holds, where it holds IDs only, ascending, none twice. +pub(crate) fn ascending_ids(json: &Json) -> Option> { + let ids = json + .as_array()? + .iter() + .map(|item| Id::from_hex(item.as_str()?)) + .collect::>>()?; + ids.windows(2).all(|pair| pair[0] < pair[1]).then_some(ids) +} + +/// Strings a JSON array holds, where it holds strings only, none twice. +fn distinct_strings(json: &Json) -> Option> { + let items = json + .as_array()? + .iter() + .map(|item| item.as_str().map(str::to_owned)) + .collect::>>()?; + let set: BTreeSet<&String> = items.iter().collect(); + (set.len() == items.len()).then_some(items) +} + +fn since(json: &Json) -> Result { + json.get("since") + .and_then(Json::as_int) + .and_then(|n| u64::try_from(n).ok()) + .ok_or_else(|| "a `since` that is no number".to_owned()) +} + +/// Whether `json` has these names and no others; `optional` ones it may leave out. +fn names(json: &Json, required: &[&str], optional: &[&str]) -> bool { + json.is_object() + && required.iter().all(|name| json.get(name).is_some()) + && json + .names() + .iter() + .all(|name| required.contains(name) || optional.contains(name)) +} + +impl Version { + /// The version `json` is, where it is one by itself: a field missing or more, or any of + /// the rest of what makes a version none, is an error. Whether it changes the version + /// it says is asked apart (`changes_validly`). + pub(crate) fn read(json: &Json) -> Result { + if !names( + json, + &["federation", "number", "changes", "keys", "nodes", "rules"], + &["checkpoint"], + ) { + return Err("a field missing or more".to_owned()); + } + let federation = json.get("federation").and_then(Json::as_int); + if federation != Some(FEDERATION) { + return Err(format!("of federation {federation:?}, not {FEDERATION}")); + } + let number = json + .get("number") + .and_then(Json::as_int) + .and_then(|n| u64::try_from(n).ok()) + .ok_or("a number that is none")?; + let changes = match json.get("changes") { + Some(Json::Null) if number == 0 => None, + Some(Json::Str(hash)) if number > 0 => { + Some(Id::from_hex(hash).ok_or("`changes` that is no hash")?) + } + _ => return Err("`changes` that doesn't go with its number".to_owned()), + }; + let parties = Self::parties(json)?; + let checkpoint = match json.get("checkpoint") { + None => None, + Some(heads) => { + let heads = ascending_ids(heads).ok_or("checkpoint heads that are none")?; + if heads.is_empty() { + return Err("a checkpoint without heads".to_owned()); + } + Some(heads) + } + }; + let rules = json + .get("rules") + .and_then(Json::as_array) + .ok_or("rules that are no list")? + .iter() + .map(|rule| Rule::read(rule, &parties)) + .collect::, String>>()?; + Ok(Version { + hash: Id::of(&json.bytes()), + json: json.clone(), + number, + changes, + parties, + checkpoint, + rules, + }) + } + + fn parties(json: &Json) -> Result, String> { + let keys = json.get("keys").ok_or("no keys")?; + let nodes = json.get("nodes").ok_or("no node lists")?; + if !keys.is_object() || !nodes.is_object() || keys.names() != nodes.names() { + return Err("keys and node lists not of the same parties".to_owned()); + } + if keys.names().is_empty() { + return Err("no party".to_owned()); + } + let mut parties = BTreeMap::new(); + let mut every_key = BTreeSet::new(); + for name in keys.names() { + if !is_party(name) { + return Err(format!("{name:?}, no party's name")); + } + let (Some(key_json), Some(node_json)) = (keys.get(name), nodes.get(name)) else { + return Err("keys and node lists not of the same parties".to_owned()); + }; + if !names(key_json, &["since", "keys"], &[]) + || !names(node_json, &["since", "nodes"], &[]) + { + return Err(format!( + "{name}'s keys or node list: a field missing or more" + )); + } + let party_keys = key_json + .get("keys") + .and_then(distinct_strings) + .ok_or_else(|| format!("{name}'s keys aren't a list of keys"))?; + if party_keys.is_empty() || party_keys.len() > KEYS { + return Err(format!("{name} with {} keys", party_keys.len())); + } + for key in &party_keys { + if keys::key(key).is_none() { + return Err(format!("{name}'s key {key:?} isn't spelled as a key")); + } + if !every_key.insert(key.clone()) { + return Err(format!("{key:?} twice in the version")); + } + } + let party_nodes = node_json + .get("nodes") + .and_then(distinct_strings) + .ok_or_else(|| format!("{name}'s node list isn't a list of node IDs"))?; + if party_nodes.len() > NODES || !party_nodes.iter().all(|id| keys::node_id(id)) { + return Err(format!("{name}'s node list")); + } + parties.insert( + name.to_owned(), + Party { + keys_since: since(key_json)?, + keys: party_keys, + nodes_since: since(node_json)?, + nodes: party_nodes, + }, + ); + } + Ok(parties) + } + + /// Whether it changes `before` as a version must: numbered one past it, naming its + /// hash, and with each `since` its own number, or that `before` gives the party with + /// the same keys, or node list. The first version gives every party its own. + pub(crate) fn changes_validly(&self, before: Option<&Version>) -> Result<(), String> { + match before { + None => { + if self.number != 0 { + return Err("a first version numbered otherwise than 0".to_owned()); + } + for (name, party) in &self.parties { + if party.keys_since != 0 || party.nodes_since != 0 { + return Err(format!("{name}'s `since` in a first version")); + } + } + } + Some(before) => { + if self.number != before.number + 1 || self.changes != Some(before.hash) { + return Err(format!( + "version {} doesn't change version {}", + self.number, before.number + )); + } + for (name, party) in &self.parties { + let was = before.parties.get(name); + let keys_kept = was.is_some_and(|was| { + was.keys_since == party.keys_since && was.keys == party.keys + }); + if party.keys_since != self.number && !keys_kept { + return Err(format!("{name}'s keys, changed without being named anew")); + } + let nodes_kept = was.is_some_and(|was| { + was.nodes_since == party.nodes_since && was.nodes == party.nodes + }); + if party.nodes_since != self.number && !nodes_kept { + return Err(format!( + "{name}'s node list, changed without being named anew" + )); + } + } + } + } + Ok(()) + } + + /// Whether it changes nothing of `before` but its number, what it changes and its + /// checkpoint: one that only moves the store on. + pub(crate) fn only_moves_on(&self, before: &Version) -> bool { + let strip = |json: &Json| { + json.without("number") + .without("changes") + .without("checkpoint") + }; + self.checkpoint.is_some() && strip(&self.json) == strip(&before.json) + } + + /// Who writes at `path`, by the first rule that matches it: a party of the version, or + /// nobody. + pub(crate) fn writer(&self, path: &[String]) -> Option<&str> { + for rule in &self.rules { + if let Some(writer) = rule.matches(path, &self.parties) { + return writer; + } + } + None + } +} + +impl Rule { + fn read(json: &Json, parties: &BTreeMap) -> Result { + if !names(json, &["path", "writer"], &[]) { + return Err("a rule: a field missing or more".to_owned()); + } + let text = json + .get("path") + .and_then(Json::as_str) + .ok_or("a rule's path that is no string")?; + let segments = path(text).ok_or_else(|| format!("{text:?} is no path"))?; + if matches!(segments[0].as_str(), "_continuum" | "{party}" | "*" | "**") { + return Err(format!("{text:?} doesn't begin with a literal segment")); + } + let path: Vec = segments + .iter() + .map(|segment| match segment.as_str() { + "{party}" => Segment::Party, + "*" => Segment::One, + "**" => Segment::Rest, + literal => Segment::Literal(literal.to_owned()), + }) + .collect(); + if path[..path.len() - 1].contains(&Segment::Rest) { + return Err(format!("{text:?}: `**` not last")); + } + let named = path + .iter() + .filter(|segment| **segment == Segment::Party) + .count(); + if named > 1 { + return Err(format!("{text:?}: `{{party}}` twice")); + } + let writer = match json.get("writer") { + Some(Json::Bool(false)) => Writer::Nobody, + Some(Json::Str(writer)) if writer == "{party}" && named == 1 => Writer::Named, + Some(Json::Str(writer)) if parties.contains_key(writer) => { + Writer::Party(writer.clone()) + } + _ => { + return Err(format!( + "{text:?}: a writer that is no party of the version" + )); + } + }; + Ok(Rule { path, writer }) + } + + /// Whether the rule matches `path`, and then who writes there: `Some(None)` for nobody. + fn matches<'a>( + &'a self, + path: &[String], + parties: &'a BTreeMap, + ) -> Option> { + let rest = self.path.last() == Some(&Segment::Rest); + let fixed = if rest { + self.path.len() - 1 + } else { + self.path.len() + }; + if (rest && path.len() <= fixed) || (!rest && path.len() != fixed) { + return None; + } + let mut named = None; + for (segment, given) in self.path[..fixed].iter().zip(path) { + match segment { + Segment::Literal(literal) if literal == given => {} + Segment::Party => { + let (name, _) = parties.get_key_value(given)?; + named = Some(name.as_str()); + } + Segment::One => {} + _ => return None, + } + } + Some(match &self.writer { + Writer::Party(party) => Some(party.as_str()), + Writer::Named => named, + Writer::Nobody => None, + }) + } +} + +#[cfg(test)] +mod tests { + use super::super::jcs; + use super::*; + use crate::access::sshsig::PublicKey; + use ed25519_dalek::SigningKey; + + fn key(seed: u8) -> String { + PublicKey( + SigningKey::from_bytes(&[seed; 32]) + .verifying_key() + .to_bytes(), + ) + .line() + } + + fn node(seed: u8) -> String { + crate::identity::node_id_of( + &SigningKey::from_bytes(&[seed; 32]) + .verifying_key() + .to_bytes(), + ) + } + + fn first() -> Json { + let text = format!( + r#"{{"changes":null,"federation":1,"keys":{{"lass":{{"keys":["{}"],"since":0}},"tv":{{"keys":["{}"],"since":0}}}},"nodes":{{"lass":{{"nodes":[],"since":0}},"tv":{{"nodes":["{}"],"since":0}}}},"number":0,"rules":[{{"path":"names/r/wiki","writer":"lass"}},{{"path":"home/{{party}}/**","writer":"{{party}}"}},{{"path":"ip4/10/243/7/*","writer":"tv"}},{{"path":"names/**","writer":false}}]}}"#, + key(1), + key(2), + node(3) + ); + jcs::read(text.as_bytes()).expect("JCS") + } + + fn path_of(text: &str) -> Vec { + path(text).expect("a path") + } + + #[test] + fn a_version_reads_and_says_who_writes_where() { + let version = Version::read(&first()).expect("a version"); + assert_eq!(version.number, 0); + assert!(version.changes_validly(None).is_ok()); + assert_eq!(version.writer(&path_of("names/r/wiki")), Some("lass")); + assert_eq!(version.writer(&path_of("home/tv/hosts/laptop")), Some("tv")); + assert_eq!(version.writer(&path_of("home/lass/x")), Some("lass")); + // `{party}` naming no party doesn't match, and a later rule decides: none here. + assert_eq!(version.writer(&path_of("home/foo/x")), None); + // `**` is one segment or more. + assert_eq!(version.writer(&path_of("home/tv")), None); + assert_eq!(version.writer(&path_of("ip4/10/243/7/3")), Some("tv")); + assert_eq!(version.writer(&path_of("ip4/10/243/7/3/4")), None); + assert_eq!(version.writer(&path_of("names/r/tv")), None); + assert_eq!(version.writer(&path_of("elsewhere")), None); + } + + fn with_rule(path: &str, writer: Json) -> Result { + let Json::Object(mut members) = first() else { + unreachable!() + }; + for (name, value) in &mut members { + if name == "rules" { + *value = Json::Array(vec![ + Json::object(vec![ + ("path".to_owned(), Json::Str(path.to_owned())), + ("writer".to_owned(), writer.clone()), + ]) + .expect("a rule"), + ]); + } + } + Version::read(&Json::Object(members)) + } + + #[test] + fn a_version_with_a_rule_that_is_none_is_none() { + let tv = || Json::Str("tv".to_owned()); + assert!(with_rule("names/x", tv()).is_ok()); + assert!(with_rule("_continuum/x", tv()).is_err()); + assert!(with_rule("{party}/x", tv()).is_err()); + assert!(with_rule("*/x", tv()).is_err()); + assert!(with_rule("names/**/x", tv()).is_err()); + assert!(with_rule("names/{party}/{party}", Json::Str("{party}".to_owned())).is_err()); + assert!(with_rule("names/x", Json::Str("{party}".to_owned())).is_err()); + assert!(with_rule("names/x", Json::Str("makefu".to_owned())).is_err()); + assert!(with_rule("names//x", tv()).is_err()); + assert!(with_rule("names/x", Json::Bool(true)).is_err()); + assert!(with_rule(&vec!["a"; SEGMENTS + 1].join("/"), tv()).is_err()); + } + + #[test] + fn a_version_changes_another_by_its_number_hash_and_sinces() { + let first = Version::read(&first()).expect("a version"); + type Members = Vec<(String, Json)>; + let next = |edit: &dyn Fn(&mut Members)| { + let Json::Object(mut members) = first.json.clone() else { + unreachable!() + }; + for (name, value) in &mut members { + match name.as_str() { + "number" => *value = Json::Int(1), + "changes" => *value = Json::Str(first.hash.to_string()), + _ => {} + } + } + edit(&mut members); + Version::read(&Json::object(members).expect("an object")).expect("a version") + }; + let same = next(&|_| {}); + assert!(same.changes_validly(Some(&first)).is_ok()); + assert!(!same.only_moves_on(&first)); + // Keys replaced without being named anew: none. + let replaced = next(&|members| { + for (name, value) in members.iter_mut() { + if name == "keys" { + let text = format!( + r#"{{"lass":{{"keys":["{}"],"since":0}},"tv":{{"keys":["{}"],"since":0}}}}"#, + key(1), + key(9) + ); + *value = jcs::read(text.as_bytes()).expect("JCS"); + } + } + }); + assert!(replaced.changes_validly(Some(&first)).is_err()); + assert!(first.changes_validly(Some(&same)).is_err()); + assert!(same.changes_validly(None).is_err()); + } + + #[test] + fn a_version_naming_a_key_twice_or_another_federation_is_none() { + let text = String::from_utf8(first().bytes()) + .expect("UTF-8") + .replace(&key(2), &key(1)); + assert!(Version::read(&jcs::read(text.as_bytes()).expect("JCS")).is_err()); + let text = String::from_utf8(first().bytes()) + .expect("UTF-8") + .replace(r#""federation":1"#, r#""federation":2"#); + assert!(Version::read(&jcs::read(text.as_bytes()).expect("JCS")).is_err()); + } +} -- cgit v1.3.1