aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/client.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/client.rs')
-rw-r--r--src/federation/client.rs86
1 files changed, 86 insertions, 0 deletions
diff --git a/src/federation/client.rs b/src/federation/client.rs
index 57e20e1..ddbc9bb 100644
--- a/src/federation/client.rs
+++ b/src/federation/client.rs
@@ -395,6 +395,63 @@ pub(crate) fn backable(current: &Version, proposed: &Json) -> Result<Version, St
Ok(version)
}
+/// 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;
+
+/// Of each of `ids`, the length of its shortest prefix that no other of them starts with,
+/// `PREFIX` digits at least: the part that names it among them.
+pub(crate) fn prefixes(ids: &[&str]) -> Vec<usize> {
+ ids.iter()
+ .map(|id| {
+ let shared = ids
+ .iter()
+ .filter(|other| *other != id)
+ .map(|other| {
+ id.bytes()
+ .zip(other.bytes())
+ .take_while(|(a, b)| a == b)
+ .count()
+ })
+ .max()
+ .unwrap_or(0);
+ (shared + 1).max(PREFIX).min(id.len())
+ })
+ .collect()
+}
+
+/// The hash `given` names among `ids`: the one it is a prefix of, of `PREFIX` digits at
+/// least; or a whole hash, itself, whether among them or not. Why none, where it names
+/// none or several, `what` naming what `ids` are.
+pub(crate) fn named(given: &str, ids: &[&str], what: &str) -> Result<Id, String> {
+ let given = given.trim_end_matches('…').to_ascii_lowercase();
+ if !given.bytes().all(|byte| byte.is_ascii_hexdigit()) {
+ return Err(format!("{given:?}: a {what} is named by hex digits"));
+ }
+ if let Some(id) = Id::from_hex(&given) {
+ return Ok(id);
+ }
+ if given.len() < PREFIX {
+ return Err(format!(
+ "{given}: name a {what} by {PREFIX} digits or more of its hash"
+ ));
+ }
+ let matching: Vec<&str> = ids
+ .iter()
+ .copied()
+ .filter(|id| id.starts_with(&given))
+ .collect();
+ match matching.as_slice() {
+ [] => Err(format!("no {what} starts with {given}")),
+ [one] => Id::from_hex(one).ok_or_else(|| format!("{one}: no hash")),
+ several => Err(format!(
+ "{given} names {} of them: {}",
+ several.len(),
+ several.join(", ")
+ )),
+ }
+}
+
/// What a vote on a proposal builds on: `proposing`, an event proposing it (of a
/// checkpoint, one above the heads it names, so that a version event may be written on
/// the vote); and, but for a checkpoint (`checkpoint`), the nays that freed its party
@@ -1002,6 +1059,35 @@ mod tests {
);
}
+ /// 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.
+ #[test]
+ fn hashes_are_named_by_their_prefixes() {
+ let a = "8d02".to_owned() + &"0".repeat(60);
+ let b = "8d0f".to_owned() + &"1".repeat(60);
+ let c = "1234".to_owned() + &"2".repeat(60);
+ let d = "8d02a".to_owned() + &"3".repeat(59);
+ let ids = [a.as_str(), b.as_str(), c.as_str()];
+ assert_eq!(prefixes(&ids), [4, 4, 4]);
+ assert_eq!(prefixes(&[a.as_str(), d.as_str()]), [5, 5]);
+ assert_eq!(prefixes(&[a.as_str()]), [4]);
+ assert_eq!(
+ named("8d02", &ids, "proposal"),
+ Ok(Id::from_hex(&a).unwrap())
+ );
+ assert_eq!(
+ named("8D0F…", &ids, "proposal"),
+ Ok(Id::from_hex(&b).unwrap())
+ );
+ assert_eq!(named(&c, &[], "proposal"), Ok(Id::from_hex(&c).unwrap()));
+ assert!(named("8d0", &ids, "proposal").is_err());
+ assert!(named("8d0x", &ids, "proposal").is_err());
+ assert!(named("9999", &ids, "proposal").is_err());
+ let shared = named("8d02", &[a.as_str(), d.as_str()], "proposal").unwrap_err();
+ assert!(shared.contains("2 of them"), "{shared}");
+ }
+
/// Row 74 (`docs/federation.md`): a party backs X, and Y is proposed at a history
/// holding that `true`; X dies after. Its `true` on Y built on Y's proposal alone is
/// refused, X being alive at its history; built as a vote builds (`building`), on the