diff options
Diffstat (limited to 'src/federation/client.rs')
| -rw-r--r-- | src/federation/client.rs | 255 |
1 files changed, 255 insertions, 0 deletions
diff --git a/src/federation/client.rs b/src/federation/client.rs index ddbc9bb..846d29c 100644 --- a/src/federation/client.rs +++ b/src/federation/client.rs @@ -395,6 +395,211 @@ pub(crate) fn backable(current: &Version, proposed: &Json) -> Result<Version, St Ok(version) } +/// What the version `proposed` does to `current`, in words, a line each: the parties it +/// lets in or takes out, the keys and node lists it names anew, the rules it adds or drops, +/// the checkpoint it moves the store to, and the revision it moves to; what a party votes +/// on, without its JSON. Its number and the hash it changes go without saying. +pub(crate) fn described(current: &Version, proposed: &Version) -> Vec<String> { + let mut lines = Vec::new(); + for (party, given) in &proposed.parties { + if !current.parties.contains_key(party) { + lines.push(format!( + "lets {party} in: {}; {}", + counted(&given.keys, "key", |key| fingerprint(key)), + counted(&given.nodes, "node", |node| node_spelled(node)), + )); + } + } + for party in current.parties.keys() { + if !proposed.parties.contains_key(party) { + lines.push(format!("takes {party} out")); + } + } + for (party, was) in ¤t.parties { + let Some(is) = proposed.parties.get(party) else { + continue; + }; + if is.keys_since != was.keys_since || is.keys != was.keys { + lines.push(format!( + "names {party}'s keys anew{}", + differing(&was.keys, &is.keys, "as they were", |key| fingerprint(key)) + )); + } + if is.nodes_since != was.nodes_since || is.nodes != was.nodes { + lines.push(format!( + "names {party}'s node list anew{}", + differing(&was.nodes, &is.nodes, "as it was", |node| node_spelled( + node + )) + )); + } + } + let spelled = |version: &Version| -> Vec<String> { + version + .rules + .iter() + .map(|rule| format!("{} -> {}", rule_path(&rule.path), rule_writer(&rule.writer))) + .collect() + }; + lines.extend(rules_changed(&spelled(current), &spelled(proposed))); + if let Some(heads) = &proposed.checkpoint { + let heads = match heads.len() { + 1 => "1 head".to_owned(), + many => format!("{many} heads"), + }; + lines.push(format!("moves the store to a checkpoint at {heads}")); + } + if proposed.revision != current.revision { + lines.push(format!("moves to {}", proposed.revision)); + } + lines +} + +/// `items` counted by `what`, each spelled by `spell`: `2 keys (a, b)`, `no node`. +fn counted<T>(items: &[T], what: &str, spell: impl Fn(&T) -> String) -> String { + match items { + [] => format!("no {what}"), + [one] => format!("1 {what} ({})", spell(one)), + many => format!( + "{} {what}s ({})", + many.len(), + many.iter().map(spell).collect::<Vec<_>>().join(", ") + ), + } +} + +/// What `after` takes in, and leaves out, of `before`, each spelled by `spell`: +/// `: + a, - b`, or `, ` and `same` where nothing differs. +fn differing( + before: &[String], + after: &[String], + same: &str, + spell: impl Fn(&String) -> String, +) -> String { + let changes: Vec<String> = after + .iter() + .filter(|item| !before.contains(item)) + .map(|item| format!("+ {}", spell(item))) + .chain( + before + .iter() + .filter(|item| !after.contains(item)) + .map(|item| format!("- {}", spell(item))), + ) + .collect(); + if changes.is_empty() { + format!(", {same}") + } else { + format!(": {}", changes.join(", ")) + } +} + +/// A key as `ssh-keygen -l` names it: its type, and the SHA-256 of its blob in base64 +/// without padding; the line itself where it isn't one. +pub(crate) fn fingerprint(line: &str) -> String { + use sha2::{Digest, Sha256}; + let mut words = line.split_whitespace(); + let (Some(kind), Some(blob)) = (words.next(), words.next()) else { + return line.to_owned(); + }; + match BASE64.decode(blob) { + Ok(bytes) => { + let digest = Sha256::digest(&bytes); + let text = base64::engine::general_purpose::STANDARD_NO_PAD.encode(digest); + format!("{kind} SHA256:{text}") + } + Err(_) => line.to_owned(), + } +} + +/// A node's ID, its first twelve hex digits enough to tell it. +fn node_spelled(node: &str) -> String { + let at = node.find(':').map_or(0, |colon| colon + 1); + match node.get(..at + 12) { + Some(start) if node.len() > at + 12 => format!("{start}…"), + _ => node.to_owned(), + } +} + +/// A rule's path as a version spells it. +fn rule_path(path: &[super::version::Segment]) -> String { + use super::version::Segment; + path.iter() + .map(|segment| match segment { + Segment::Literal(text) => text.clone(), + Segment::Party => "{party}".to_owned(), + Segment::One => "*".to_owned(), + Segment::Rest => "**".to_owned(), + }) + .collect::<Vec<_>>() + .join("/") +} + +/// Who a rule gives its places to. +fn rule_writer(writer: &super::version::Writer) -> String { + use super::version::Writer; + match writer { + Writer::Party(party) => party.clone(), + Writer::Named => "{party}".to_owned(), + Writer::Nobody => "nobody".to_owned(), + } +} + +/// The rules `after` adds and drops of `before`, each with its place among its version's +/// rules, by the longest run of rules they keep in order: a rule moved is dropped at one +/// place and added at another. Past so many rules changed at once, which rules alone. +fn rules_changed(before: &[String], after: &[String]) -> Vec<String> { + let start = before.iter().zip(after).take_while(|(a, b)| a == b).count(); + let end = before[start..] + .iter() + .rev() + .zip(after[start..].iter().rev()) + .take_while(|(a, b)| a == b) + .count(); + let (old, new) = ( + &before[start..before.len() - end], + &after[start..after.len() - end], + ); + let mut lines = Vec::new(); + if old.len().saturating_mul(new.len()) > 1 << 22 { + lines.extend( + new.iter() + .filter(|rule| !old.contains(rule)) + .map(|rule| format!("adds rule {rule}")), + ); + lines.extend( + old.iter() + .filter(|rule| !new.contains(rule)) + .map(|rule| format!("drops rule {rule}")), + ); + return lines; + } + // The longest run kept in order, from the back: kept[i][j] for old[i..] and new[j..]. + let mut kept = vec![vec![0u32; new.len() + 1]; old.len() + 1]; + for i in (0..old.len()).rev() { + for j in (0..new.len()).rev() { + kept[i][j] = if old[i] == new[j] { + kept[i + 1][j + 1] + 1 + } else { + kept[i + 1][j].max(kept[i][j + 1]) + }; + } + } + let (mut i, mut j) = (0, 0); + while i < old.len() || j < new.len() { + if i < old.len() && j < new.len() && old[i] == new[j] { + (i, j) = (i + 1, j + 1); + } else if j < new.len() && (i == old.len() || kept[i][j + 1] >= kept[i + 1][j]) { + lines.push(format!("adds rule {}: {}", start + j + 1, new[j])); + j += 1; + } else { + lines.push(format!("drops rule {}: {}", start + i + 1, old[i])); + i += 1; + } + } + lines +} + /// The fewest hex digits that name a hash in part: fewer would too soon name another, /// proposed since the part was read. pub(crate) const PREFIX: usize = 4; @@ -1059,6 +1264,56 @@ mod tests { ); } + /// A version's changes in words: a party let in and one taken out, keys named anew, + /// rules added and dropped where they are, a checkpoint and a revision; a key by its + /// fingerprint, as `ssh-keygen -l` gives it. + #[test] + fn what_a_version_does_is_said_in_words() { + assert_eq!( + fingerprint( + "ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIH+0RqNr1A0vrV7Ed+53/BMI50Jjcz++Bg8IG0Iiv3K1" + ), + "ssh-ed25519 SHA256:IDPEVCc1gUXLVkYd3OZhe2v4BDk7swi/Y2+Xe1gTXSU" + ); + assert_eq!(fingerprint("no key"), "no key"); + let (tv, lass, makefu) = ( + Party::new("tv", 1), + Party::new("lass", 2), + Party::new("makefu", 3), + ); + let rules = [("names/**", harness::str("tv"))]; + let read = |spec: &Spec| Version::read(&spec.json()).unwrap(); + let first = Spec::first(&[&tv, &lass], &rules); + let current = read(&first); + assert!(described(¤t, ¤t).is_empty()); + let admitted = Spec::first(&[&tv, &lass, &makefu], &rules); + assert_eq!( + described(¤t, &read(&admitted)), + [format!( + "lets makefu in: 1 key ({}); no node", + fingerprint(&makefu.key_line()) + )] + ); + let mut changed = Spec::first(&[&tv], &[]); + changed.parties[0].keys_since = 1; + changed + .rules + .insert(0, ("names/r/wiki".to_owned(), harness::str("tv"))); + changed.checkpoint = Some(vec![Id::of(b"a"), Id::of(b"b")]); + changed.revision = Revision(1); + assert_eq!( + described(¤t, &read(&changed)), + [ + "takes lass out", + "names tv's keys anew, as they were", + "adds rule 1: names/r/wiki -> tv", + "drops rule 2: names/** -> tv", + "moves the store to a checkpoint at 2 heads", + "moves to revision 1 (merge-events)", + ] + ); + } + /// Each hash is named by its shortest prefix no other has, of four digits at least, and /// found by any prefix it alone has; a whole hash is itself, a short or shared prefix /// none. |
