dogfood
Jump to…
snowcorepublic2 bookmarks
snowinitial commitqoxwzsukwmkx1mo
mainroot / crates / df-index / src / change_id.rsBlameRaw
1//! Extraction of jj change ids from raw Git commit objects.
2//!
3//! This is the single most format-sensitive function in Dogfood. Everything in
4//! the change index keys off its output, so it is deliberately strict: it
5//! either returns an id it is certain about, or `None`.
6//!
7//! The wire format is documented, with the observations that established it, in
8//! `docs/change-id-format.md`. The short version:
9//!
10//! - The header key is `change-id`, lowercase and hyphenated.
11//! - The value is 32 characters in jj's reverse-hex alphabet (`k`..=`z`) — the
12//! same string the CLI prints. It is **not** hex. Do not decode it.
13//! - Its position among the headers is not fixed. It appears before `gpgsig` on
14//! signed commits and after the multi-line `jj:conflict-labels` header on
15//! conflicted ones.
16//!
17//! That last point is why this is a real header parser rather than a substring
18//! search: a `gpgsig` signature body is base64, and a continuation line inside
19//! it can begin with any byte sequence at all, including `change-id `.
20
21/// A jj change id, in the canonical reverse-hex letter encoding jj stores and
22/// displays.
23///
24/// Stored and compared as the letter string. Constructing one guarantees it is
25/// well-formed, so downstream code never has to re-validate.
26#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
27pub struct ChangeId(String);
28
29/// Length of a jj change id: 16 bytes rendered as 32 reverse-hex characters.
30const CHANGE_ID_LEN: usize = 32;
31
32/// jj's reverse-hex alphabet. `0123456789abcdef` maps to `zyxwvutsrqponmlk`,
33/// so every character of a well-formed change id falls in `k..=z`.
34const fn is_reverse_hex(b: u8) -> bool {
35 b >= b'k' && b <= b'z'
36}
37
38impl ChangeId {
39 /// Parse a change id from its canonical letter encoding.
40 ///
41 /// Returns `None` unless the input is exactly 32 characters drawn from
42 /// jj's reverse-hex alphabet. Being strict here is what keeps malformed
43 /// ids out of the index, where they would be indistinguishable from real
44 /// ones forever.
45 pub fn parse(s: &str) -> Option<Self> {
46 let b = s.as_bytes();
47 if b.len() != CHANGE_ID_LEN || !b.iter().copied().all(is_reverse_hex) {
48 return None;
49 }
50 Some(ChangeId(s.to_owned()))
51 }
52
53 pub fn as_str(&self) -> &str {
54 &self.0
55 }
56
57 /// The abbreviated form shown in the UI, matching how the CLI abbreviates.
58 ///
59 /// This is presentation only. The shortest *unique* prefix within a repo is
60 /// a database question, not a property of the id, and is resolved by the
61 /// change lookup query rather than here.
62 pub fn short(&self) -> &str {
63 &self.0[..12.min(self.0.len())]
64 }
65}
66
67impl std::fmt::Display for ChangeId {
68 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
69 f.write_str(&self.0)
70 }
71}
72
73/// One header of a Git commit object, with continuation lines folded in.
74struct Header<'a> {
75 key: &'a [u8],
76 /// Raw value. For multi-line headers this is the first line only; callers
77 /// that need the folded value use [`Headers::folded`]. Every header
78 /// Dogfood cares about is single-line, so this avoids allocating for the
79 /// large `gpgsig` values that make up most of a signed commit.
80 value: &'a [u8],
81}
82
83/// Iterator over the header block of a raw commit object.
84///
85/// Stops at the first empty line, which per the Git object format terminates
86/// the headers and begins the message. Lines beginning with a single space are
87/// continuations of the preceding header and are skipped rather than being
88/// mistaken for new headers — the hazard this parser exists to avoid.
89struct Headers<'a> {
90 rest: &'a [u8],
91 done: bool,
92}
93
94impl<'a> Headers<'a> {
95 fn new(raw: &'a [u8]) -> Self {
96 Headers { rest: raw, done: false }
97 }
98}
99
100impl<'a> Iterator for Headers<'a> {
101 type Item = Header<'a>;
102
103 fn next(&mut self) -> Option<Header<'a>> {
104 loop {
105 if self.done || self.rest.is_empty() {
106 return None;
107 }
108
109 // Split off one line.
110 let (line, tail) = match memchr(b'\n', self.rest) {
111 Some(i) => (&self.rest[..i], &self.rest[i + 1..]),
112 // No trailing newline: this is the last line of the object.
113 None => (self.rest, &self.rest[self.rest.len()..]),
114 };
115 self.rest = tail;
116
117 // An empty line ends the header block; the message follows.
118 if line.is_empty() {
119 self.done = true;
120 return None;
121 }
122
123 // A leading space marks a continuation of the previous header's
124 // value (gpgsig, jj:conflict-labels). Skip it: it is never the
125 // start of a new header, no matter what bytes it contains.
126 if line[0] == b' ' {
127 continue;
128 }
129
130 // `key SP value`. A header with no space is malformed; skip it
131 // rather than aborting, so one odd header cannot cost us the
132 // change id.
133 return match memchr(b' ', line) {
134 Some(i) => Some(Header { key: &line[..i], value: &line[i + 1..] }),
135 None => continue,
136 };
137 }
138 }
139}
140
141/// Minimal byte search, to avoid pulling in `memchr` for two call sites.
142fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> {
143 haystack.iter().position(|&b| b == needle)
144}
145
146/// Extract the jj change id from a raw git commit object.
147///
148/// Returns `None` for commits authored by plain git, which carry no such
149/// header, and for commits whose `change-id` value is not a well-formed id.
150/// Callers treat `None` as "this commit needs a synthetic identity" (spec §4).
151///
152/// `raw_commit` is the object payload — the bytes `git cat-file commit` prints,
153/// without the `commit <len>\0` prefix that precedes them in the object store.
154pub fn extract_change_id(raw_commit: &[u8]) -> Option<ChangeId> {
155 for h in Headers::new(raw_commit) {
156 if h.key == b"change-id" {
157 // Trailing `\r` would mean a mangled object; `from_utf8` on the
158 // trimmed value rejects anything non-ASCII anyway, and `parse`
159 // rejects anything outside the alphabet.
160 return std::str::from_utf8(h.value).ok().and_then(ChangeId::parse);
161 }
162 }
163 None
164}
165
166/// Conflict information carried in a jj commit's `jj:trees` header.
167///
168/// jj stores a conflicted state as an alternating list of tree ids:
169/// `side_0, base_0, side_1, base_1, side_2, …` — always one more side than
170/// base. See `docs/change-id-format.md` §6.
171#[derive(Debug, Clone, PartialEq, Eq)]
172pub struct ConflictTrees {
173 pub sides: Vec<String>,
174 pub bases: Vec<String>,
175}
176
177/// Extract conflict tree structure from a raw commit object.
178///
179/// Returns `None` for unconflicted commits. Detection uses the `jj:trees`
180/// header rather than looking for `.jjconflict-*` entries in the tree, because
181/// the header is authoritative and requires no object loads.
182pub fn extract_conflict_trees(raw_commit: &[u8]) -> Option<ConflictTrees> {
183 let value = Headers::new(raw_commit).find(|h| h.key == b"jj:trees")?.value;
184 let ids: Vec<String> = std::str::from_utf8(value)
185 .ok()?
186 .split_ascii_whitespace()
187 .map(str::to_owned)
188 .collect();
189
190 // Must be a non-empty odd count: sides = bases + 1. Anything else is not a
191 // shape we understand, and guessing at it would produce a wrong conflict
192 // view rather than an honest failure.
193 if ids.is_empty() || ids.len() % 2 == 0 {
194 return None;
195 }
196
197 let mut sides = Vec::with_capacity(ids.len() / 2 + 1);
198 let mut bases = Vec::with_capacity(ids.len() / 2);
199 for (i, id) in ids.into_iter().enumerate() {
200 if i % 2 == 0 {
201 sides.push(id);
202 } else {
203 bases.push(id);
204 }
205 }
206 Some(ConflictTrees { sides, bases })
207}
208
209/// Tree entry names jj uses for conflict storage. These are implementation
210/// detail of the storage format and must never appear in a user-facing file
211/// listing.
212pub fn is_conflict_artifact(name: &str) -> bool {
213 name.starts_with(".jjconflict-") || name == "JJ-CONFLICT-README"
214}
215
216#[cfg(test)]
217mod tests {
218 use super::*;
219
220 /// A jj commit exactly as observed from `git cat-file commit`.
221 const JJ_SIMPLE: &[u8] = b"\
222tree 2e81171448eb9f2ee3821e3d447aa6b2fe3ddba1
223author Fixture Author <fixture@dogfood.sh> 1785482369 +0000
224committer Fixture Author <fixture@dogfood.sh> 1785482369 +0000
225change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
226
227first change
228";
229
230 const PLAIN_GIT: &[u8] = b"\
231tree 4997ca7a42e3ad9b729fbad3acd44fbabd07b6bd
232author Plain Git <pg@dogfood.sh> 1785482410 +0000
233committer Plain Git <pg@dogfood.sh> 1785482410 +0000
234
235plain git commit
236";
237
238 const JJ_MERGE: &[u8] = b"\
239tree 6349276c93aa7281b3ea997c1ed9eee4fca779ca
240parent 0e6a26973ecf5056359d2b82f39ad9901675bd7f
241parent f4017227300e3da7b8b05c461bc1bc24047707c8
242author Fixture Author <fixture@dogfood.sh> 1785482416 +0000
243committer Fixture Author <fixture@dogfood.sh> 1785482416 +0000
244change-id vokuuvrqvyoksvpnxznztskrpwnstmqt
245
246merge of left and right
247";
248
249 /// Signed commit: `change-id` precedes a multi-line `gpgsig`.
250 const JJ_SIGNED: &[u8] = b"\
251tree ec67420ed747b72ce94854190b4c59deff01b9db
252author Fixture Author <fixture@dogfood.sh> 1785482470 +0000
253committer Fixture Author <fixture@dogfood.sh> 1785482470 +0000
254change-id rwsosmnkorymmtvvzwkuuzzqqmuonwnn
255gpgsig -----BEGIN SSH SIGNATURE-----
256 U1NIU0lHAAAAAQAAADMAAAALc3NoLWVkMjU1MTkAAAAgpDlDGOvAOfzKu8EtSuCO+q7OMl
257 P4iz0WatcsQcBg98kAAAADZ2l0AAAAAAAAAAZzaGE1MTIAAABTAAAAC3NzaC1lZDI1NTE5
258 AAAAQLPQ/lWPdf2zmi261EFYVcLDTOT1CpY8cEWRpjQXTPAkOOsVexrIzZypFgM4yTtgyU
259 pwfjmHzZ3D9uEeK1H3Ygg=
260 -----END SSH SIGNATURE-----
261
262signed via jj
263";
264
265 /// Conflicted commit: `change-id` comes AFTER a multi-line `jj:` header.
266 const JJ_CONFLICTED: &[u8] = b"\
267tree 125bc2eed773e5eacbb11544e9966dab850ed4f9
268parent 79976290ff8d8ad397f41d423a469b26d225f157
269parent 47129393c3d17b7031ff88faa27ffe1b8180c225
270author Fixture Author <fixture@dogfood.sh> 1785497562 +0000
271committer Fixture Author <fixture@dogfood.sh> 1785497562 +0000
272jj:conflict-labels qtmrpxym 79976290 \"side A\"
273 qmksvpxn 691a639f \"conflict base\"
274 syuzyywq 47129393 \"side B\"
275jj:trees ada380c77b2f1923458d0b93cbfee42f297a58e9 892cad2b4d1f22ae36e2107a6a187a5dc227f965 14a356d6227b63a22f94c18817912d5e37b77c21
276change-id psxoyvqkymplnoqklzrotrqopkxqkynz
277
278conflicted merge
279";
280
281 #[test]
282 fn extracts_from_simple_jj_commit() {
283 let id = extract_change_id(JJ_SIMPLE).expect("jj commit must yield an id");
284 assert_eq!(id.as_str(), "qstvwxmpkvovsosxxmrnxpqmuuyllsqu");
285 }
286
287 #[test]
288 fn plain_git_commit_has_no_change_id() {
289 assert_eq!(extract_change_id(PLAIN_GIT), None);
290 }
291
292 #[test]
293 fn extracts_from_merge_commit() {
294 let id = extract_change_id(JJ_MERGE).unwrap();
295 assert_eq!(id.as_str(), "vokuuvrqvyoksvpnxznztskrpwnstmqt");
296 }
297
298 #[test]
299 fn extracts_when_followed_by_multiline_signature() {
300 let id = extract_change_id(JJ_SIGNED).unwrap();
301 assert_eq!(id.as_str(), "rwsosmnkorymmtvvzwkuuzzqqmuonwnn");
302 }
303
304 #[test]
305 fn extracts_when_preceded_by_multiline_jj_header() {
306 // The case a naive "first N lines" parser gets wrong.
307 let id = extract_change_id(JJ_CONFLICTED).unwrap();
308 assert_eq!(id.as_str(), "psxoyvqkymplnoqklzrotrqopkxqkynz");
309 }
310
311 #[test]
312 fn continuation_lines_are_never_read_as_headers() {
313 // The specific attack/corruption shape this parser exists to prevent: a
314 // signature body whose base64 happens to start a line with
315 // "change-id ". It must be ignored as a continuation, and the real
316 // header below it must win.
317 let raw = b"\
318tree 0000000000000000000000000000000000000000
319author A <a@b.c> 1 +0000
320committer A <a@b.c> 1 +0000
321gpgsig -----BEGIN SSH SIGNATURE-----
322 change-id kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
323 -----END SSH SIGNATURE-----
324change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
325
326msg
327";
328 let id = extract_change_id(raw).unwrap();
329 assert_eq!(
330 id.as_str(),
331 "qstvwxmpkvovsosxxmrnxpqmuuyllsqu",
332 "a continuation line must not be parsed as a change-id header"
333 );
334 }
335
336 #[test]
337 fn body_text_after_headers_is_not_scanned() {
338 // A commit message that mentions a change-id header must not be
339 // mistaken for one. The header block ends at the first blank line.
340 let raw = b"\
341tree 0000000000000000000000000000000000000000
342author A <a@b.c> 1 +0000
343committer A <a@b.c> 1 +0000
344
345see also:
346change-id kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
347";
348 assert_eq!(extract_change_id(raw), None);
349 }
350
351 #[test]
352 fn rejects_malformed_values() {
353 let cases: &[(&str, &[u8])] = &[
354 ("too short", b"tree x\nchange-id qstvwxmp\n\nm\n"),
355 (
356 "too long",
357 b"tree x\nchange-id qstvwxmpkvovsosxxmrnxpqmuuyllsquz\n\nm\n",
358 ),
359 (
360 "hex, not reverse-hex",
361 b"tree x\nchange-id 0123456789abcdef0123456789abcdef\n\nm\n",
362 ),
363 ("empty", b"tree x\nchange-id \n\nm\n"),
364 (
365 "uppercase",
366 b"tree x\nchange-id QSTVWXMPKVOVSOSXXMRNXPQMUUYLLSQU\n\nm\n",
367 ),
368 ];
369 for (name, raw) in cases {
370 assert_eq!(extract_change_id(raw), None, "should reject: {name}");
371 }
372 }
373
374 #[test]
375 fn header_key_match_is_exact() {
376 // `jj:change-id`, `Change-Id` (Gerrit's, in the message trailer) and
377 // similar must not be picked up.
378 let raw = b"\
379tree 0000000000000000000000000000000000000000
380author A <a@b.c> 1 +0000
381Change-Id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
382jj:change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
383
384m
385";
386 assert_eq!(extract_change_id(raw), None);
387 }
388
389 #[test]
390 fn tolerates_unknown_extra_headers() {
391 let raw = b"\
392tree 0000000000000000000000000000000000000000
393author A <a@b.c> 1 +0000
394committer A <a@b.c> 1 +0000
395mergetag something
396encoding ISO-8859-1
397some-future-jj-header whatever
398change-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu
399
400m
401";
402 assert_eq!(
403 extract_change_id(raw).unwrap().as_str(),
404 "qstvwxmpkvovsosxxmrnxpqmuuyllsqu"
405 );
406 }
407
408 #[test]
409 fn handles_truncated_object_without_panicking() {
410 // Robustness: the indexer must never panic on a malformed object.
411 for n in 0..JJ_SIMPLE.len() {
412 let _ = extract_change_id(&JJ_SIMPLE[..n]);
413 }
414 }
415
416 #[test]
417 fn root_change_id_is_all_z() {
418 // jj renders the root change as 32 'z' (= all-zero bytes). It is a
419 // well-formed id and must parse, so the indexer can recognise and skip
420 // it rather than treating it as a user change.
421 let id = ChangeId::parse("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz").unwrap();
422 assert_eq!(id.short(), "zzzzzzzzzzzz");
423 }
424
425 #[test]
426 fn parses_conflict_trees() {
427 let c = extract_conflict_trees(JJ_CONFLICTED).expect("conflicted commit");
428 assert_eq!(
429 c.sides,
430 vec![
431 "ada380c77b2f1923458d0b93cbfee42f297a58e9".to_string(),
432 "14a356d6227b63a22f94c18817912d5e37b77c21".to_string(),
433 ]
434 );
435 assert_eq!(
436 c.bases,
437 vec!["892cad2b4d1f22ae36e2107a6a187a5dc227f965".to_string()]
438 );
439 // The invariant jj's conflict representation guarantees.
440 assert_eq!(c.sides.len(), c.bases.len() + 1);
441 }
442
443 #[test]
444 fn unconflicted_commits_have_no_conflict_trees() {
445 assert_eq!(extract_conflict_trees(JJ_SIMPLE), None);
446 assert_eq!(extract_conflict_trees(PLAIN_GIT), None);
447 assert_eq!(extract_conflict_trees(JJ_SIGNED), None);
448 }
449
450 #[test]
451 fn rejects_even_length_tree_lists() {
452 // sides == bases + 1 always, so an even count is a shape we do not
453 // understand and must not guess at.
454 let raw = b"tree x\njj:trees aaaa bbbb\nchange-id qstvwxmpkvovsosxxmrnxpqmuuyllsqu\n\nm\n";
455 assert_eq!(extract_conflict_trees(raw), None);
456 }
457
458 #[test]
459 fn filters_conflict_artifacts_from_listings() {
460 assert!(is_conflict_artifact(".jjconflict-side-0"));
461 assert!(is_conflict_artifact(".jjconflict-base-0"));
462 assert!(is_conflict_artifact("JJ-CONFLICT-README"));
463 assert!(!is_conflict_artifact("src"));
464 assert!(!is_conflict_artifact("c.txt"));
465 // Not a jj artifact: a user file that merely starts similarly.
466 assert!(!is_conflict_artifact(".jjconflict"));
467 }
468}

468 lines · Rust