dogfood
Jump to…
snowcorepublic2 bookmarks
snowinitial commitqoxwzsukwmkx1mo
mainroot / crates / df-index / src / change_id.rsHide BlameRaw
Matt W1//! Extraction of jj change ids from raw Git commit objects.
Matt W2//!
Matt W3//! This is the single most format-sensitive function in Dogfood. Everything in
Matt W4//! the change index keys off its output, so it is deliberately strict: it
Matt W5//! either returns an id it is certain about, or `None`.
Matt W6//!
Matt W7//! The wire format is documented, with the observations that established it, in
Matt W8//! `docs/change-id-format.md`. The short version:
Matt W9//!
Matt W10//! - The header key is `change-id`, lowercase and hyphenated.
Matt W11//! - The value is 32 characters in jj's reverse-hex alphabet (`k`..=`z`) — the
Matt W12//! same string the CLI prints. It is **not** hex. Do not decode it.
Matt W13//! - Its position among the headers is not fixed. It appears before `gpgsig` on
Matt W14//! signed commits and after the multi-line `jj:conflict-labels` header on
Matt W15//! conflicted ones.
Matt W16//!
Matt W17//! That last point is why this is a real header parser rather than a substring
Matt W18//! search: a `gpgsig` signature body is base64, and a continuation line inside
Matt W19//! it can begin with any byte sequence at all, including `change-id `.
Matt W20
Matt W21/// A jj change id, in the canonical reverse-hex letter encoding jj stores and
Matt W22/// displays.
Matt W23///
Matt W24/// Stored and compared as the letter string. Constructing one guarantees it is
Matt W25/// well-formed, so downstream code never has to re-validate.
Matt W26#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
Matt W27pub struct ChangeId(String);
Matt W28
Matt W29/// Length of a jj change id: 16 bytes rendered as 32 reverse-hex characters.
Matt W30const CHANGE_ID_LEN: usize = 32;
Matt W31
Matt W32/// jj's reverse-hex alphabet. `0123456789abcdef` maps to `zyxwvutsrqponmlk`,
Matt W33/// so every character of a well-formed change id falls in `k..=z`.
Matt W34const fn is_reverse_hex(b: u8) -> bool {
Matt W35 b >= b'k' && b <= b'z'
Matt W36}
Matt W37
Matt W38impl ChangeId {
Matt W39 /// Parse a change id from its canonical letter encoding.
Matt W40 ///
Matt W41 /// Returns `None` unless the input is exactly 32 characters drawn from
Matt W42 /// jj's reverse-hex alphabet. Being strict here is what keeps malformed
Matt W43 /// ids out of the index, where they would be indistinguishable from real
Matt W44 /// ones forever.
Matt W45 pub fn parse(s: &str) -> Option<Self> {
Matt W46 let b = s.as_bytes();
Matt W47 if b.len() != CHANGE_ID_LEN || !b.iter().copied().all(is_reverse_hex) {
Matt W48 return None;
Matt W49 }
Matt W50 Some(ChangeId(s.to_owned()))
Matt W51 }
Matt W52
Matt W53 pub fn as_str(&self) -> &str {
Matt W54 &self.0
Matt W55 }
Matt W56
Matt W57 /// The abbreviated form shown in the UI, matching how the CLI abbreviates.
Matt W58 ///
Matt W59 /// This is presentation only. The shortest *unique* prefix within a repo is
Matt W60 /// a database question, not a property of the id, and is resolved by the
Matt W61 /// change lookup query rather than here.
Matt W62 pub fn short(&self) -> &str {
Matt W63 &self.0[..12.min(self.0.len())]
Matt W64 }
Matt W65}
Matt W66
Matt W67impl std::fmt::Display for ChangeId {
Matt W68 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
Matt W69 f.write_str(&self.0)
Matt W70 }
Matt W71}
Matt W72
Matt W73/// One header of a Git commit object, with continuation lines folded in.
Matt W74struct Header<'a> {
Matt W75 key: &'a [u8],
Matt W76 /// Raw value. For multi-line headers this is the first line only; callers
Matt W77 /// that need the folded value use [`Headers::folded`]. Every header
Matt W78 /// Dogfood cares about is single-line, so this avoids allocating for the
Matt W79 /// large `gpgsig` values that make up most of a signed commit.
Matt W80 value: &'a [u8],
Matt W81}
Matt W82
Matt W83/// Iterator over the header block of a raw commit object.
Matt W84///
Matt W85/// Stops at the first empty line, which per the Git object format terminates
Matt W86/// the headers and begins the message. Lines beginning with a single space are
Matt W87/// continuations of the preceding header and are skipped rather than being
Matt W88/// mistaken for new headers — the hazard this parser exists to avoid.
Matt W89struct Headers<'a> {
Matt W90 rest: &'a [u8],
Matt W91 done: bool,
Matt W92}
Matt W93
Matt W94impl<'a> Headers<'a> {
Matt W95 fn new(raw: &'a [u8]) -> Self {
Matt W96 Headers { rest: raw, done: false }
Matt W97 }
Matt W98}
Matt W99
Matt W100impl<'a> Iterator for Headers<'a> {
Matt W101 type Item = Header<'a>;
Matt W102
Matt W103 fn next(&mut self) -> Option<Header<'a>> {
Matt W104 loop {
Matt W105 if self.done || self.rest.is_empty() {
Matt W106 return None;
Matt W107 }
Matt W108
Matt W109 // Split off one line.
Matt W110 let (line, tail) = match memchr(b'\n', self.rest) {
Matt W111 Some(i) => (&self.rest[..i], &self.rest[i + 1..]),
Matt W112 // No trailing newline: this is the last line of the object.
Matt W113 None => (self.rest, &self.rest[self.rest.len()..]),
Matt W114 };
Matt W115 self.rest = tail;
Matt W116
Matt W117 // An empty line ends the header block; the message follows.
Matt W118 if line.is_empty() {
Matt W119 self.done = true;
Matt W120 return None;
Matt W121 }
Matt W122
Matt W123 // A leading space marks a continuation of the previous header's
Matt W124 // value (gpgsig, jj:conflict-labels). Skip it: it is never the
Matt W125 // start of a new header, no matter what bytes it contains.
Matt W126 if line[0] == b' ' {
Matt W127 continue;
Matt W128 }
Matt W129
Matt W130 // `key SP value`. A header with no space is malformed; skip it
Matt W131 // rather than aborting, so one odd header cannot cost us the
Matt W132 // change id.
Matt W133 return match memchr(b' ', line) {
Matt W134 Some(i) => Some(Header { key: &line[..i], value: &line[i + 1..] }),
Matt W135 None => continue,
Matt W136 };
Matt W137 }
Matt W138 }
Matt W139}
Matt W140
Matt W141/// Minimal byte search, to avoid pulling in `memchr` for two call sites.
Matt W142fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> {
Matt W143 haystack.iter().position(|&b| b == needle)
Matt W144}
Matt W145
Matt W146/// Extract the jj change id from a raw git commit object.
Matt W147///
Matt W148/// Returns `None` for commits authored by plain git, which carry no such
Matt W149/// header, and for commits whose `change-id` value is not a well-formed id.
Matt W150/// Callers treat `None` as "this commit needs a synthetic identity" (spec §4).
Matt W151///
Matt W152/// `raw_commit` is the object payload — the bytes `git cat-file commit` prints,
Matt W153/// without the `commit <len>\0` prefix that precedes them in the object store.
Matt W154pub fn extract_change_id(raw_commit: &[u8]) -> Option<ChangeId> {
Matt W155 for h in Headers::new(raw_commit) {
Matt W156 if h.key == b"change-id" {
Matt W157 // Trailing `\r` would mean a mangled object; `from_utf8` on the
Matt W158 // trimmed value rejects anything non-ASCII anyway, and `parse`
Matt W159 // rejects anything outside the alphabet.
Matt W160 return std::str::from_utf8(h.value).ok().and_then(ChangeId::parse);
Matt W161 }
Matt W162 }
Matt W163 None
Matt W164}
Matt W165
Matt W166/// Conflict information carried in a jj commit's `jj:trees` header.
Matt W167///
Matt W168/// jj stores a conflicted state as an alternating list of tree ids:
Matt W169/// `side_0, base_0, side_1, base_1, side_2, …` — always one more side than
Matt W170/// base. See `docs/change-id-format.md` §6.
Matt W171#[derive(Debug, Clone, PartialEq, Eq)]
Matt W172pub struct ConflictTrees {
Matt W173 pub sides: Vec<String>,
Matt W174 pub bases: Vec<String>,
Matt W175}
Matt W176
Matt W177/// Extract conflict tree structure from a raw commit object.
Matt W178///
Matt W179/// Returns `None` for unconflicted commits. Detection uses the `jj:trees`
Matt W180/// header rather than looking for `.jjconflict-*` entries in the tree, because
Matt W181/// the header is authoritative and requires no object loads.
Matt W182pub fn extract_conflict_trees(raw_commit: &[u8]) -> Option<ConflictTrees> {
Matt W183 let value = Headers::new(raw_commit).find(|h| h.key == b"jj:trees")?.value;
Matt W184 let ids: Vec<String> = std::str::from_utf8(value)
Matt W185 .ok()?
Matt W186 .split_ascii_whitespace()
Matt W187 .map(str::to_owned)
Matt W188 .collect();
Matt W189
Matt W190 // Must be a non-empty odd count: sides = bases + 1. Anything else is not a
Matt W191 // shape we understand, and guessing at it would produce a wrong conflict
Matt W192 // view rather than an honest failure.
Matt W193 if ids.is_empty() || ids.len() % 2 == 0 {
Matt W194 return None;
Matt W195 }
Matt W196
Matt W197 let mut sides = Vec::with_capacity(ids.len() / 2 + 1);
Matt W198 let mut bases = Vec::with_capacity(ids.len() / 2);
Matt W199 for (i, id) in ids.into_iter().enumerate() {
Matt W200 if i % 2 == 0 {
Matt W201 sides.push(id);
Matt W202 } else {
Matt W203 bases.push(id);
Matt W204 }
Matt W205 }
Matt W206 Some(ConflictTrees { sides, bases })
Matt W207}
Matt W208
Matt W209/// Tree entry names jj uses for conflict storage. These are implementation
Matt W210/// detail of the storage format and must never appear in a user-facing file
Matt W211/// listing.
Matt W212pub fn is_conflict_artifact(name: &str) -> bool {
Matt W213 name.starts_with(".jjconflict-") || name == "JJ-CONFLICT-README"
Matt W214}
Matt W215
Matt W216#[cfg(test)]
Matt W217mod tests {
Matt W218 use super::*;
Matt W219
Matt W220 /// A jj commit exactly as observed from `git cat-file commit`.
Matt W221 const JJ_SIMPLE: &[u8] = b"\
Matt W222tree 2e81171448eb9f2ee3821e3d447aa6b2fe3ddba1
Matt W223author Fixture Author <fixture@dogfood.sh> 1785482369 +0000
Matt W224committer Fixture Author <fixture@dogfood.sh> 1785482369 +0000
Matt W225change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
Matt W226
Matt W227first change
Matt W228";
Matt W229
Matt W230 const PLAIN_GIT: &[u8] = b"\
Matt W231tree 4997ca7a42e3ad9b729fbad3acd44fbabd07b6bd
Matt W232author Plain Git <pg@dogfood.sh> 1785482410 +0000
Matt W233committer Plain Git <pg@dogfood.sh> 1785482410 +0000
Matt W234
Matt W235plain git commit
Matt W236";
Matt W237
Matt W238 const JJ_MERGE: &[u8] = b"\
Matt W239tree 6349276c93aa7281b3ea997c1ed9eee4fca779ca
Matt W240parent 0e6a26973ecf5056359d2b82f39ad9901675bd7f
Matt W241parent f4017227300e3da7b8b05c461bc1bc24047707c8
Matt W242author Fixture Author <fixture@dogfood.sh> 1785482416 +0000
Matt W243committer Fixture Author <fixture@dogfood.sh> 1785482416 +0000
Matt W244change-id vokuuvrqvyoksvpnxznztskrpwnstmqt
Matt W245
Matt W246merge of left and right
Matt W247";
Matt W248
Matt W249 /// Signed commit: `change-id` precedes a multi-line `gpgsig`.
Matt W250 const JJ_SIGNED: &[u8] = b"\
Matt W251tree ec67420ed747b72ce94854190b4c59deff01b9db
Matt W252author Fixture Author <fixture@dogfood.sh> 1785482470 +0000
Matt W253committer Fixture Author <fixture@dogfood.sh> 1785482470 +0000
Matt W254change-id rwsosmnkorymmtvvzwkuuzzqqmuonwnn
Matt W255gpgsig -----BEGIN SSH SIGNATURE-----
Matt W256 U1NIU0lHAAAAAQAAADMAAAALc3NoLWVkMjU1MTkAAAAgpDlDGOvAOfzKu8EtSuCO+q7OMl
Matt W257 P4iz0WatcsQcBg98kAAAADZ2l0AAAAAAAAAAZzaGE1MTIAAABTAAAAC3NzaC1lZDI1NTE5
Matt W258 AAAAQLPQ/lWPdf2zmi261EFYVcLDTOT1CpY8cEWRpjQXTPAkOOsVexrIzZypFgM4yTtgyU
Matt W259 pwfjmHzZ3D9uEeK1H3Ygg=
Matt W260 -----END SSH SIGNATURE-----
Matt W261
Matt W262signed via jj
Matt W263";
Matt W264
Matt W265 /// Conflicted commit: `change-id` comes AFTER a multi-line `jj:` header.
Matt W266 const JJ_CONFLICTED: &[u8] = b"\
Matt W267tree 125bc2eed773e5eacbb11544e9966dab850ed4f9
Matt W268parent 79976290ff8d8ad397f41d423a469b26d225f157
Matt W269parent 47129393c3d17b7031ff88faa27ffe1b8180c225
Matt W270author Fixture Author <fixture@dogfood.sh> 1785497562 +0000
Matt W271committer Fixture Author <fixture@dogfood.sh> 1785497562 +0000
Matt W272jj:conflict-labels qtmrpxym 79976290 \"side A\"
Matt W273 qmksvpxn 691a639f \"conflict base\"
Matt W274 syuzyywq 47129393 \"side B\"
Matt W275jj:trees ada380c77b2f1923458d0b93cbfee42f297a58e9 892cad2b4d1f22ae36e2107a6a187a5dc227f965 14a356d6227b63a22f94c18817912d5e37b77c21
Matt W276change-id psxoyvqkymplnoqklzrotrqopkxqkynz
Matt W277
Matt W278conflicted merge
Matt W279";
Matt W280
Matt W281 #[test]
Matt W282 fn extracts_from_simple_jj_commit() {
Matt W283 let id = extract_change_id(JJ_SIMPLE).expect("jj commit must yield an id");
Matt W284 assert_eq!(id.as_str(), "qstvwxmpkvovsosxxmrnxpqmuuyllsqu");
Matt W285 }
Matt W286
Matt W287 #[test]
Matt W288 fn plain_git_commit_has_no_change_id() {
Matt W289 assert_eq!(extract_change_id(PLAIN_GIT), None);
Matt W290 }
Matt W291
Matt W292 #[test]
Matt W293 fn extracts_from_merge_commit() {
Matt W294 let id = extract_change_id(JJ_MERGE).unwrap();
Matt W295 assert_eq!(id.as_str(), "vokuuvrqvyoksvpnxznztskrpwnstmqt");
Matt W296 }
Matt W297
Matt W298 #[test]
Matt W299 fn extracts_when_followed_by_multiline_signature() {
Matt W300 let id = extract_change_id(JJ_SIGNED).unwrap();
Matt W301 assert_eq!(id.as_str(), "rwsosmnkorymmtvvzwkuuzzqqmuonwnn");
Matt W302 }
Matt W303
Matt W304 #[test]
Matt W305 fn extracts_when_preceded_by_multiline_jj_header() {
Matt W306 // The case a naive "first N lines" parser gets wrong.
Matt W307 let id = extract_change_id(JJ_CONFLICTED).unwrap();
Matt W308 assert_eq!(id.as_str(), "psxoyvqkymplnoqklzrotrqopkxqkynz");
Matt W309 }
Matt W310
Matt W311 #[test]
Matt W312 fn continuation_lines_are_never_read_as_headers() {
Matt W313 // The specific attack/corruption shape this parser exists to prevent: a
Matt W314 // signature body whose base64 happens to start a line with
Matt W315 // "change-id ". It must be ignored as a continuation, and the real
Matt W316 // header below it must win.
Matt W317 let raw = b"\
Matt W318tree 0000000000000000000000000000000000000000
Matt W319author A <a@b.c> 1 +0000
Matt W320committer A <a@b.c> 1 +0000
Matt W321gpgsig -----BEGIN SSH SIGNATURE-----
Matt W322 change-id kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
Matt W323 -----END SSH SIGNATURE-----
Matt W324change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
Matt W325
Matt W326msg
Matt W327";
Matt W328 let id = extract_change_id(raw).unwrap();
Matt W329 assert_eq!(
Matt W330 id.as_str(),
Matt W331 "qstvwxmpkvovsosxxmrnxpqmuuyllsqu",
Matt W332 "a continuation line must not be parsed as a change-id header"
Matt W333 );
Matt W334 }
Matt W335
Matt W336 #[test]
Matt W337 fn body_text_after_headers_is_not_scanned() {
Matt W338 // A commit message that mentions a change-id header must not be
Matt W339 // mistaken for one. The header block ends at the first blank line.
Matt W340 let raw = b"\
Matt W341tree 0000000000000000000000000000000000000000
Matt W342author A <a@b.c> 1 +0000
Matt W343committer A <a@b.c> 1 +0000
Matt W344
Matt W345see also:
Matt W346change-id kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
Matt W347";
Matt W348 assert_eq!(extract_change_id(raw), None);
Matt W349 }
Matt W350
Matt W351 #[test]
Matt W352 fn rejects_malformed_values() {
Matt W353 let cases: &[(&str, &[u8])] = &[
Matt W354 ("too short", b"tree x\nchange-id qstvwxmp\n\nm\n"),
Matt W355 (
Matt W356 "too long",
Matt W357 b"tree x\nchange-id qstvwxmpkvovsosxxmrnxpqmuuyllsquz\n\nm\n",
Matt W358 ),
Matt W359 (
Matt W360 "hex, not reverse-hex",
Matt W361 b"tree x\nchange-id 0123456789abcdef0123456789abcdef\n\nm\n",
Matt W362 ),
Matt W363 ("empty", b"tree x\nchange-id \n\nm\n"),
Matt W364 (
Matt W365 "uppercase",
Matt W366 b"tree x\nchange-id QSTVWXMPKVOVSOSXXMRNXPQMUUYLLSQU\n\nm\n",
Matt W367 ),
Matt W368 ];
Matt W369 for (name, raw) in cases {
Matt W370 assert_eq!(extract_change_id(raw), None, "should reject: {name}");
Matt W371 }
Matt W372 }
Matt W373
Matt W374 #[test]
Matt W375 fn header_key_match_is_exact() {
Matt W376 // `jj:change-id`, `Change-Id` (Gerrit's, in the message trailer) and
Matt W377 // similar must not be picked up.
Matt W378 let raw = b"\
Matt W379tree 0000000000000000000000000000000000000000
Matt W380author A <a@b.c> 1 +0000
Matt W381Change-Id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
Matt W382jj:change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
Matt W383
Matt W384m
Matt W385";
Matt W386 assert_eq!(extract_change_id(raw), None);
Matt W387 }
Matt W388
Matt W389 #[test]
Matt W390 fn tolerates_unknown_extra_headers() {
Matt W391 let raw = b"\
Matt W392tree 0000000000000000000000000000000000000000
Matt W393author A <a@b.c> 1 +0000
Matt W394committer A <a@b.c> 1 +0000
Matt W395mergetag something
Matt W396encoding ISO-8859-1
Matt W397some-future-jj-header whatever
Matt W398change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
Matt W399
Matt W400m
Matt W401";
Matt W402 assert_eq!(
Matt W403 extract_change_id(raw).unwrap().as_str(),
Matt W404 "qstvwxmpkvovsosxxmrnxpqmuuyllsqu"
Matt W405 );
Matt W406 }
Matt W407
Matt W408 #[test]
Matt W409 fn handles_truncated_object_without_panicking() {
Matt W410 // Robustness: the indexer must never panic on a malformed object.
Matt W411 for n in 0..JJ_SIMPLE.len() {
Matt W412 let _ = extract_change_id(&JJ_SIMPLE[..n]);
Matt W413 }
Matt W414 }
Matt W415
Matt W416 #[test]
Matt W417 fn root_change_id_is_all_z() {
Matt W418 // jj renders the root change as 32 'z' (= all-zero bytes). It is a
Matt W419 // well-formed id and must parse, so the indexer can recognise and skip
Matt W420 // it rather than treating it as a user change.
Matt W421 let id = ChangeId::parse("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz").unwrap();
Matt W422 assert_eq!(id.short(), "zzzzzzzzzzzz");
Matt W423 }
Matt W424
Matt W425 #[test]
Matt W426 fn parses_conflict_trees() {
Matt W427 let c = extract_conflict_trees(JJ_CONFLICTED).expect("conflicted commit");
Matt W428 assert_eq!(
Matt W429 c.sides,
Matt W430 vec![
Matt W431 "ada380c77b2f1923458d0b93cbfee42f297a58e9".to_string(),
Matt W432 "14a356d6227b63a22f94c18817912d5e37b77c21".to_string(),
Matt W433 ]
Matt W434 );
Matt W435 assert_eq!(
Matt W436 c.bases,
Matt W437 vec!["892cad2b4d1f22ae36e2107a6a187a5dc227f965".to_string()]
Matt W438 );
Matt W439 // The invariant jj's conflict representation guarantees.
Matt W440 assert_eq!(c.sides.len(), c.bases.len() + 1);
Matt W441 }
Matt W442
Matt W443 #[test]
Matt W444 fn unconflicted_commits_have_no_conflict_trees() {
Matt W445 assert_eq!(extract_conflict_trees(JJ_SIMPLE), None);
Matt W446 assert_eq!(extract_conflict_trees(PLAIN_GIT), None);
Matt W447 assert_eq!(extract_conflict_trees(JJ_SIGNED), None);
Matt W448 }
Matt W449
Matt W450 #[test]
Matt W451 fn rejects_even_length_tree_lists() {
Matt W452 // sides == bases + 1 always, so an even count is a shape we do not
Matt W453 // understand and must not guess at.
Matt W454 let raw = b"tree x\njj:trees aaaa bbbb\nchange-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu\n\nm\n";
Matt W455 assert_eq!(extract_conflict_trees(raw), None);
Matt W456 }
Matt W457
Matt W458 #[test]
Matt W459 fn filters_conflict_artifacts_from_listings() {
Matt W460 assert!(is_conflict_artifact(".jjconflict-side-0"));
Matt W461 assert!(is_conflict_artifact(".jjconflict-base-0"));
Matt W462 assert!(is_conflict_artifact("JJ-CONFLICT-README"));
Matt W463 assert!(!is_conflict_artifact("src"));
Matt W464 assert!(!is_conflict_artifact("c.txt"));
Matt W465 // Not a jj artifact: a user file that merely starts similarly.
Matt W466 assert!(!is_conflict_artifact(".jjconflict"));
Matt W467 }
Matt W468}

468 lines · Rust