src/abbrev.rs
Ref: Size: 13.9 KiB History
//! How wide a collab id is printed.
//!
//! # Policy
//!
//! Every list, header and confirmation used to print a hard-coded 8 characters
//! while `resolve_ref` accepted any unambiguous prefix. Two things are wrong
//! with a hard-coded width, and they pull in opposite directions:
//!
//! * It is arbitrary. Nothing checks that 8 characters actually identify
//! anything, so a repository large enough for two ids to share their first 8
//! characters would print the same string for both.
//! * It is fixed. It cannot grow with the repository.
//!
//! The tempting fix — print the shortest prefix that is unambiguous across the
//! current set, the way `git log --abbrev-commit` is often assumed to work — is
//! wrong, and it is worth being precise about why, because git does not do it
//! either. Git computes a *uniform* width from the approximate object count
//! (`core.abbrev`, floor 7) and only extends past it for an object that is
//! genuinely ambiguous at that width. The shortest-unambiguous width is by
//! definition the minimum that works *this instant*: the next object created
//! can collide with it. That matters here more than it does in git, because
//! displayed collab ids leave the tool. They are pasted into `Patch:` and
//! `Issue:` commit trailers, into branch names, into review comments and into
//! scripts, where they are permanent. A width with no collision margin turns
//! every one of those into a delayed failure.
//!
//! So:
//!
//! * **Display width is uniform per repository and carries a margin.** It is
//! `max(8, birthday_width(count))`, where `birthday_width` is git's rule —
//! roughly `log2(count)/2 + 1` hex digits, so that `16^width` stays well
//! clear of `count^2`. 8 remains the floor, both because it is what this
//! project already prints and because it is already wider than git's 7.
//! * **A width is never merely probable.** The birthday bound makes collisions
//! unlikely, not impossible, so an id that is still ambiguous at the uniform
//! width is printed wider until it is not. A printed id is always unique
//! within its kind at the moment it is printed.
//! * **Display width and accepted-prefix width are different things.**
//! Accepting a prefix is an interactive convenience whose mistakes surface
//! immediately: `resolve_ref` refuses an ambiguous prefix with an error.
//! Printing an id mints a reference that will outlive the command. The first
//! should be as permissive as possible, the second should have margin. They
//! are deliberately not the same number.
//!
//! The abbreviation must be computed over *all* ids of a kind — open, closed
//! and archived — not just the ones being listed, or `issue list` and
//! `issue list --all` could print the same string for different issues.
/// The narrowest id this tool will print.
///
/// Also the width every list printed before this module existed, so nothing
/// that reads current output changes until a repository is big enough to need
/// more.
pub const MIN_WIDTH: usize = 8;
/// The floor `collab.abbrev` is clamped to, matching git's `core.abbrev`.
///
/// Below four characters a displayed id stops being a usable reference: it
/// would be ambiguous in almost any repository, and the widening below would
/// have to undo the setting on nearly every row anyway.
pub const CONFIG_MIN_WIDTH: usize = 4;
/// Length of an unabbreviated id.
pub const FULL_WIDTH: usize = 40;
/// The git config key that overrides the automatic width, named after — and
/// behaving like — git's own `core.abbrev`.
pub const CONFIG_KEY: &str = "collab.abbrev";
/// Hex digits needed to keep collisions unlikely among `count` random ids.
///
/// Git's rule, from `object-name.c`: take the position of the most significant
/// bit of the count, halve it, add one. That yields `16^width` on the order of
/// `count^2` times a constant, which is the birthday bound with margin.
fn birthday_width(count: usize) -> usize {
if count < 2 {
return 1;
}
let msb = (usize::BITS - 1 - count.leading_zeros()) as usize;
msb / 2 + 1
}
/// The uniform display width for a kind holding `count` objects.
pub fn uniform_width(count: usize) -> usize {
birthday_width(count).max(MIN_WIDTH)
}
/// Abbreviates ids of one kind against the full set of ids of that kind.
///
/// Build one per kind per command from *every* id of that kind, including
/// closed and archived ones, then ask it for each id you print.
#[derive(Debug, Clone)]
pub struct Abbrev {
width: usize,
/// Sorted, so the minimum unique length of any id is decided by comparing
/// it with its two immediate neighbours.
sorted: Vec<String>,
}
impl Abbrev {
/// Build an abbreviator over every id of one kind.
pub fn new<I, S>(ids: I) -> Self
where
I: IntoIterator<Item = S>,
S: Into<String>,
{
Self::with_width(ids, None)
}
/// As [`Abbrev::new`], but with an explicit uniform width from
/// `collab.abbrev`. Per-id widening still applies on top of it.
pub fn with_width<I, S>(ids: I, configured: Option<usize>) -> Self
where
I: IntoIterator<Item = S>,
S: Into<String>,
{
let mut sorted: Vec<String> = ids.into_iter().map(Into::into).collect();
sorted.sort_unstable();
sorted.dedup();
let width = configured.unwrap_or_else(|| uniform_width(sorted.len()));
Abbrev { width, sorted }
}
/// An abbreviator over no ids at all, for the handful of places that print
/// an id without having the set to hand. Prints the floor width.
pub fn minimal() -> Self {
Abbrev {
width: MIN_WIDTH,
sorted: Vec::new(),
}
}
/// The uniform width for this set, before per-id disambiguation.
pub fn width(&self) -> usize {
self.width
}
/// The prefix of `id` to display: the uniform width, widened if this
/// particular id would otherwise be ambiguous, capped at the whole id.
pub fn of<'a>(&self, id: &'a str) -> &'a str {
let len = self.display_len(id).min(id.len());
&id[..len]
}
/// The number of characters `of` would return, before the length cap.
fn display_len(&self, id: &str) -> usize {
let needed = match self.sorted.binary_search_by(|probe| probe.as_str().cmp(id)) {
// `id` is in the set: only its sorted neighbours can share a
// prefix with it, and the longer of the two shared prefixes is one
// character short of what makes it unique.
Ok(pos) => {
let before = pos.checked_sub(1).map(|i| self.sorted[i].as_str());
let after = self.sorted.get(pos + 1).map(|s| s.as_str());
before
.into_iter()
.chain(after)
.map(|other| common_prefix_len(id, other) + 1)
.max()
.unwrap_or(0)
}
// `id` is not in the set — a stale reference, or a caller printing
// an id of a different kind. Its insertion point's neighbours are
// still the only candidates for a shared prefix.
Err(pos) => {
let before = pos.checked_sub(1).map(|i| self.sorted[i].as_str());
let after = self.sorted.get(pos).map(|s| s.as_str());
before
.into_iter()
.chain(after)
.map(|other| common_prefix_len(id, other) + 1)
.max()
.unwrap_or(0)
}
};
needed.max(self.width)
}
}
/// Length in bytes of the longest common prefix of two ids.
///
/// Ids are ASCII hex, so bytes and characters coincide and slicing at a byte
/// index is always on a character boundary.
fn common_prefix_len(a: &str, b: &str) -> usize {
a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count()
}
/// Read `collab.abbrev`, or `None` to use the automatic width.
///
/// Unset, unreadable and unparseable all mean the same thing: fall back to the
/// automatic width. A bad value is a display preference nobody can act on, not
/// a reason to fail a command that was otherwise going to work.
pub fn configured_width(repo: &git2::Repository) -> Option<usize> {
let raw = repo.config().ok()?.get_string(CONFIG_KEY).ok()?;
match raw.trim().to_ascii_lowercase().as_str() {
// git's spellings for "print the whole thing".
"no" | "false" | "off" | "full" => Some(FULL_WIDTH),
other => other
.parse::<usize>()
.ok()
.map(|n| n.clamp(CONFIG_MIN_WIDTH, FULL_WIDTH)),
}
}
/// The abbreviator for issue ids in this repository.
pub fn for_issues(repo: &git2::Repository) -> Abbrev {
match crate::state::all_issue_ids(repo) {
Ok(ids) => Abbrev::with_width(ids, configured_width(repo)),
// Losing the id set costs a well-chosen width, not correctness: the
// floor is still printed and `resolve_ref` still refuses anything
// ambiguous. Failing the command instead would be worse.
Err(_) => Abbrev::minimal(),
}
}
/// The abbreviator for patch ids in this repository.
pub fn for_patches(repo: &git2::Repository) -> Abbrev {
match crate::state::all_patch_ids(repo) {
Ok(ids) => Abbrev::with_width(ids, configured_width(repo)),
Err(_) => Abbrev::minimal(),
}
}
#[cfg(test)]
mod tests {
use super::*;
fn ids(prefixes: &[&str]) -> Vec<String> {
// Pad to a realistic 40-hex id so widths behave as they do in a repo.
prefixes
.iter()
.map(|p| format!("{:0<40}", p))
.collect::<Vec<_>>()
}
#[test]
fn a_small_repository_still_prints_eight_characters() {
for count in [0usize, 1, 2, 10, 100, 1000] {
assert_eq!(
uniform_width(count),
8,
"count {} should still print 8 characters",
count
);
}
}
#[test]
fn the_width_grows_once_the_repository_outgrows_eight_characters() {
assert_eq!(uniform_width(1 << 16), 9);
assert_eq!(uniform_width(1 << 18), 10);
assert!(uniform_width(1 << 30) > uniform_width(1 << 20));
}
#[test]
fn the_width_never_shrinks_as_objects_are_added() {
let mut previous = 0;
for count in 0..2000usize {
let width = uniform_width(count);
assert!(width >= previous, "width shrank at count {}", count);
previous = width;
}
}
/// The whole point of a uniform width is that it keeps a margin over the
/// birthday bound: `16^width` must stay comfortably above `count^2`.
#[test]
fn the_width_keeps_a_margin_over_the_birthday_bound() {
for shift in 4..24u32 {
let count = 1usize << shift;
let width = uniform_width(count);
let space = 16f64.powi(width as i32);
let pairs = (count as f64).powi(2);
assert!(
space >= pairs,
"width {} for {} objects leaves no birthday margin",
width,
count
);
}
}
#[test]
fn an_id_is_abbreviated_to_the_uniform_width() {
let a = Abbrev::new(ids(&["aaaa1111", "bbbb2222"]));
assert_eq!(a.of(&ids(&["aaaa1111"])[0]), "aaaa1111");
}
/// The case a fixed 8 gets wrong: two ids sharing their first 8 characters
/// must not print as the same string.
#[test]
fn a_colliding_id_is_printed_wider_than_the_uniform_width() {
let all = ids(&["aaaaaaaa1", "aaaaaaaa2"]);
let a = Abbrev::new(all.clone());
assert_eq!(a.of(&all[0]), "aaaaaaaa1");
assert_eq!(a.of(&all[1]), "aaaaaaaa2");
assert_ne!(a.of(&all[0]), a.of(&all[1]));
}
#[test]
fn only_the_colliding_ids_are_widened() {
let all = ids(&["aaaaaaaa1", "aaaaaaaa2", "bbbbbbbb"]);
let a = Abbrev::new(all.clone());
assert_eq!(a.of(&all[2]), "bbbbbbbb");
}
#[test]
fn a_run_of_near_identical_ids_widens_until_unique() {
let all = ids(&["aaaaaaaaaaaa1", "aaaaaaaaaaaa2", "aaaaaaaaaaaa3"]);
let a = Abbrev::new(all.clone());
for id in &all {
assert_eq!(a.of(id).len(), 13, "{} was not widened far enough", id);
}
}
/// The guarantee that makes displayed ids safe to paste: whatever this
/// prints is unique across the whole set it was built from.
#[test]
fn every_printed_prefix_matches_exactly_one_id() {
let all = ids(&[
"aaaaaaaa1",
"aaaaaaaa2",
"aaaaaaab",
"bbbbbbbb",
"bbbbbbbc",
"c",
"d",
"e",
]);
let a = Abbrev::new(all.clone());
for id in &all {
let shown = a.of(id);
let matches = all.iter().filter(|other| other.starts_with(shown)).count();
assert_eq!(matches, 1, "'{}' matched {} ids", shown, matches);
}
}
#[test]
fn an_id_shorter_than_the_width_is_printed_whole() {
let a = Abbrev::new(vec!["abc".to_string()]);
assert_eq!(a.of("abc"), "abc");
}
#[test]
fn an_unknown_id_is_still_printed_unambiguously() {
let all = ids(&["aaaaaaaa1", "aaaaaaaa2"]);
let a = Abbrev::new(all.clone());
// Not in the set, but shares 8 characters with two that are.
let stranger = format!("{:0<40}", "aaaaaaaa3");
let shown = a.of(&stranger);
assert!(
!all.iter().any(|id| id.starts_with(shown)),
"'{}' should not match a real id",
shown
);
}
#[test]
fn an_empty_set_prints_the_floor_width() {
let a = Abbrev::new(Vec::<String>::new());
assert_eq!(a.width(), MIN_WIDTH);
assert_eq!(a.of(&ids(&["deadbeefcafe"])[0]), "deadbeef");
}
#[test]
fn duplicates_in_the_input_do_not_widen_anything() {
let one = ids(&["aaaaaaaa"])[0].clone();
let a = Abbrev::new(vec![one.clone(), one.clone(), one.clone()]);
assert_eq!(a.of(&one), "aaaaaaaa");
}
}