//! 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()); } }