From 9d3350f996ddba2a8e4636dd3705d9bd1c7aa4fb Mon Sep 17 00:00:00 2001 From: tv Date: Thu, 19 Nov 2026 16:15:42 +0000 Subject: continuum-party: hashes named by their prefixes, the shortest marked MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The guides wrote `vote 8d02… yes`, and the client took a whole hash only. It takes a proposal's hash by a prefix of four digits or more that no other proposal on the current version starts with (`client::named`), and says which proposals a prefix names where it names several; a whole hash is itself, as before. Heads given to `fork` are named so too, among the heads the node shows. Four digits at least, so that a prefix read a moment ago doesn't come to name a proposal made since, as one or two soon would. Where it shows a proposal's hash (`proposals`, `propose`), the client marks the shortest prefix that names it, in bold, on a terminal unless NO_COLOR is set; elsewhere the hash is printed as it was. --- src/federation/client.rs | 86 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) (limited to 'src/federation/client.rs') 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 Vec { + 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 { + 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 -- cgit v1.3.1