aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation')
-rw-r--r--src/federation/mod.rs1
-rw-r--r--src/federation/version.rs538
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());
+ }
+}