//! 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::revision::Revision; 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; /// Parties a version may name: a version event names the votes passing a proposal, two /// thirds of its version's parties, and an event names no more than 64 events /// (`event::DEPENDENCIES`). pub(crate) const PARTIES: usize = 96; /// 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, /// The revision of the federation it follows: the base revision where it names none. pub(crate) revision: Revision, 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()) } /// That `json`, `what`, has these names and no others, `optional` ones it may leave out; /// else which it lacks, or which it has more, that this continuum doesn't know. fn fields(json: &Json, what: &str, required: &[&str], optional: &[&str]) -> Result<(), String> { if !json.is_object() { return Err(format!("{what} that is no object")); } if let Some(name) = required.iter().find(|name| json.get(name).is_none()) { return Err(format!("{what} without `{name}`")); } match json .names() .into_iter() .find(|name| !required.contains(name) && !optional.contains(name)) { Some(name) => Err(format!( "{what} with `{name}`, a field this continuum doesn't know" )), None => Ok(()), } } 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, saying which. Whether it changes /// the version it says is asked apart (`changes_validly`). pub(crate) fn read(json: &Json) -> Result { fields( json, "a version", &["federation", "number", "changes", "keys", "nodes", "rules"], &["checkpoint", "revision"], )?; match json.get("federation").and_then(Json::as_int) { Some(FEDERATION) => {} Some(federation) => { return Err(format!( "of federation {federation}, and this continuum knows {FEDERATION} alone" )); } None => return Err("a federation that is no number".to_owned()), } let revision = match json.get("revision") { None => Revision::default(), Some(named) => { let id = named .as_str() .and_then(Id::from_hex) .ok_or("a `revision` that is no revision's ID")?; match Revision::of(&id) { Some(Revision(0)) => { return Err("a `revision` naming the base revision, which a version \ names by leaving it out" .to_owned()); } Some(revision) => revision, None => { return Err(format!( "revision {id}, which this continuum doesn't know, as it knows {}: \ a release that knows it reads this version", Revision::knowing() )); } } } }; 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(), revision, 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()); } if keys.names().len() > PARTIES { return Err(format!( "{} parties, more than {PARTIES}", keys.names().len() )); } 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()); }; fields(key_json, &format!("{name}'s keys"), &["since", "keys"], &[])?; fields( node_json, &format!("{name}'s node list"), &["since", "nodes"], &[], )?; 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, not 1 to {KEYS}", party_keys.len() )); } for key in &party_keys { if let Err(why) = keys::spelled(key) { return Err(format!("{name}'s key {key:?}: {why}")); } 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 { return Err(format!( "{name}'s node list of {} nodes, more than {NODES}", party_nodes.len() )); } if let Some(id) = party_nodes.iter().find(|id| !keys::node_id(id)) { return Err(format!("{name}'s node {id:?}, no node ID")); } 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, of its revision or a later one, 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 )); } if self.revision < before.revision { return Err(format!( "{}, before {} of the version it changes", self.revision, before.revision )); } 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, its revision neither: 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 { fields(json, "a rule", &["path", "writer"], &[])?; 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()); } /// What makes a version none, said: a field it lacks or one more, which this /// continuum doesn't know, a federation it doesn't know, a key of a type it doesn't /// take. #[test] fn a_version_that_is_none_says_why() { let edited = |edit: &dyn Fn(&str) -> String| { let text = String::from_utf8(first().bytes()).expect("UTF-8"); Version::read(&jcs::read(edit(&text).as_bytes()).expect("JCS")).unwrap_err() }; let why = edited(&|text| text.replacen(r#""nodes":"#, r#""later":true,"nodes":"#, 1)); assert_eq!( why, "a version with `later`, a field this continuum doesn't know" ); let why = edited(&|text| text.replace(r#""federation":1,"#, "")); assert_eq!(why, "a version without `federation`"); let why = edited(&|text| text.replace(r#""federation":1"#, r#""federation":2"#)); assert_eq!(why, "of federation 2, and this continuum knows 1 alone"); let why = edited(&|text| text.replace("ssh-ed25519 ", "sk-ssh-ed25519@openssh.com ")); assert!(why.contains("a sk-ssh-ed25519@openssh.com key"), "{why}"); let why = edited(&|text| text.replacen(r#""since":0"#, r#""since":0,"x":1"#, 1)); assert!( why.ends_with("with `x`, a field this continuum doesn't know"), "{why}" ); } /// A version names no more parties than a version event may name the votes of two /// thirds of. #[test] fn a_version_names_at_most_96_parties() { use super::super::harness::{Party, Spec}; let parties: Vec = (1..=PARTIES as u8 + 1) .map(|n| Party::new(&format!("p{n}"), n)) .collect(); let named: Vec<&Party> = parties.iter().collect(); assert!(Version::read(&Spec::first(&named[1..], &[]).json()).is_ok()); let why = Version::read(&Spec::first(&named, &[]).json()).unwrap_err(); assert_eq!(why, "97 parties, more than 96"); } /// A version follows the base revision where it names none; one naming the base /// revision, or one this continuum doesn't know, is none, and says so. #[test] fn a_version_names_a_revision_it_follows_or_none() { assert_eq!( Version::read(&first()).expect("a version").revision, Revision::default() ); let named = |id: &str| { let text = String::from_utf8(first().bytes()).expect("UTF-8"); let text = text.replacen(r#""rules":"#, &format!(r#""revision":"{id}","rules":"#), 1); Version::read(&jcs::read(text.as_bytes()).expect("JCS")) }; let why = named(&Revision::default().id().to_string()).unwrap_err(); assert!(why.contains("naming the base revision"), "{why}"); let unknown = Id::of(br#"["elsewhere"]"#); let why = named(&unknown.to_string()).unwrap_err(); assert!( why.starts_with(&format!( "revision {unknown}, which this continuum doesn't know" )), "{why}" ); assert!(named("no ID").unwrap_err().contains("no revision's ID")); for revision in Revision::known().skip(1) { let version = named(&revision.id().to_string()).expect("a version"); assert_eq!(version.revision, revision); } } #[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()); } }