diff options
Diffstat (limited to 'src/federation')
| -rw-r--r-- | src/federation/mod.rs | 1 | ||||
| -rw-r--r-- | src/federation/version.rs | 538 |
2 files changed, 539 insertions, 0 deletions
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<Id>, + pub(crate) parties: BTreeMap<String, Party>, + /// The heads of the checkpoint it names, if any. + pub(crate) checkpoint: Option<Vec<Id>>, + pub(crate) rules: Vec<Rule>, +} + +/// 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<String>, + pub(crate) nodes_since: u64, + pub(crate) nodes: Vec<String>, +} + +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct Rule { + pub(crate) path: Vec<Segment>, + 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<Vec<String>> { + let segments: Vec<String> = 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<Vec<Id>> { + let ids = json + .as_array()? + .iter() + .map(|item| Id::from_hex(item.as_str()?)) + .collect::<Option<Vec<Id>>>()?; + 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<Vec<String>> { + let items = json + .as_array()? + .iter() + .map(|item| item.as_str().map(str::to_owned)) + .collect::<Option<Vec<String>>>()?; + let set: BTreeSet<&String> = items.iter().collect(); + (set.len() == items.len()).then_some(items) +} + +fn since(json: &Json) -> Result<u64, String> { + 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<Version, String> { + 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::<Result<Vec<Rule>, String>>()?; + Ok(Version { + hash: Id::of(&json.bytes()), + json: json.clone(), + number, + changes, + parties, + checkpoint, + rules, + }) + } + + fn parties(json: &Json) -> Result<BTreeMap<String, Party>, 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<String, Party>) -> Result<Rule, String> { + 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<Segment> = 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<String, Party>, + ) -> Option<Option<&'a str>> { + 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<String> { + 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<Version, String> { + 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()); + } +} |
