flagon-io/g1t

public

Where people and agents ship software together. The open-source git platform for the whole job: issues, agents, checks and deploys to the edge.

g1t/crates/scan/src/pack.rs

535 lines18,718 bytesCodeBlame
1//! Reading the objects in a git pack, as a push sends them, so that what a
2//! push adds can be looked at before it is stored.
3//!
4//! A pushed pack is usually thin: some objects are deltas against objects
5//! the repository already has. Those are left pending until the caller
6//! supplies their bases with [`Pack::supply`].
7
8use std::collections::HashMap;
9
10use miniz_oxide::inflate::TINFLStatus;
11use miniz_oxide::inflate::core::{DecompressorOxide, decompress, inflate_flags};
12use sha1::{Digest, Sha1};
13
14/// Beyond this much inflated content the pack is not read: a push that
15/// large is let through unread rather than risk the worker's memory.
16pub const MAX_INFLATED: usize = 48 * 1024 * 1024;
17
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19pub enum ObjectKind {
20 Commit,
21 Tree,
22 Blob,
23 Tag,
24}
25
26impl ObjectKind {
27 fn from_type(code: u8) -> Option<ObjectKind> {
28 Some(match code {
29 1 => ObjectKind::Commit,
30 2 => ObjectKind::Tree,
31 3 => ObjectKind::Blob,
32 4 => ObjectKind::Tag,
33 _ => return None,
34 })
35 }
36
37 fn name(self) -> &'static str {
38 match self {
39 ObjectKind::Commit => "commit",
40 ObjectKind::Tree => "tree",
41 ObjectKind::Blob => "blob",
42 ObjectKind::Tag => "tag",
43 }
44 }
45}
46
47/// A git object's id: the SHA-1 of its header and content, in hex.
48pub fn object_id(kind: ObjectKind, data: &[u8]) -> String {
49 let mut hasher = Sha1::new();
50 hasher.update(format!("{} {}\0", kind.name(), data.len()).as_bytes());
51 hasher.update(data);
52 hasher.finalize().iter().map(|byte| format!("{byte:02x}")).collect()
53}
54
55enum Base {
56 /// An earlier object in the pack, by its offset.
57 Offset(usize),
58 /// Any object, by id.
59 Id(String),
60}
61
62struct Delta {
63 base: Base,
64 data: Vec<u8>,
65}
66
67/// The objects of a pack, by id.
68#[derive(Default)]
69pub struct Pack {
70 objects: HashMap<String, (ObjectKind, Vec<u8>)>,
71 /// Ids of the objects at each offset, once resolved.
72 at_offset: HashMap<usize, String>,
73 pending: Vec<(usize, Delta)>,
74 /// Commits, in the order the pack holds them.
75 commits: Vec<String>,
76}
77
78/// Where the pack starts in a receive-pack request: after the commands
79/// and anything else sent as pkt-lines.
80pub fn pack_start(body: &[u8]) -> Option<usize> {
81 let mut at = 0;
82 loop {
83 if body.get(at..at + 4) == Some(b"PACK") {
84 return Some(at);
85 }
86 let length = std::str::from_utf8(body.get(at..at + 4)?)
87 .ok()
88 .and_then(|hex| usize::from_str_radix(hex, 16).ok())?;
89 // A flush packet is four bytes; any other line counts its own length.
90 at += if length == 0 { 4 } else { length.max(4) };
91 }
92}
93
94fn inflate(input: &[u8], size: usize) -> Result<(Vec<u8>, usize), String> {
95 let mut out = vec![0u8; size.max(1)];
96 let mut state = DecompressorOxide::new();
97 let flags = inflate_flags::TINFL_FLAG_PARSE_ZLIB_HEADER | inflate_flags::TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF;
98 let (status, consumed, written) = decompress(&mut state, input, &mut out, 0, flags);
99 match status {
100 TINFLStatus::Done => {
101 out.truncate(written);
102 if written != size {
103 return Err(format!("an object inflated to {written} bytes, not {size}"));
104 }
105 Ok((out, consumed))
106 }
107 other => Err(format!("an object could not be inflated: {other:?}")),
108 }
109}
110
111fn varint(data: &[u8], at: &mut usize) -> Option<usize> {
112 let (mut value, mut shift) = (0usize, 0);
113 loop {
114 let byte = *data.get(*at)?;
115 *at += 1;
116 value |= ((byte & 0x7f) as usize) << shift;
117 shift += 7;
118 if byte & 0x80 == 0 || shift > 56 {
119 return Some(value);
120 }
121 }
122}
123
124/// Applies a git delta to its base.
125pub fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>, String> {
126 let mut at = 0;
127 let bad = || "a delta is malformed".to_owned();
128 let source = varint(delta, &mut at).ok_or_else(bad)?;
129 if source != base.len() {
130 return Err("a delta does not fit its base".into());
131 }
132 let target = varint(delta, &mut at).ok_or_else(bad)?;
133 let mut out = Vec::with_capacity(target);
134 while at < delta.len() {
135 let op = delta[at];
136 at += 1;
137 if op & 0x80 != 0 {
138 let mut offset = 0usize;
139 let mut size = 0usize;
140 for bit in 0..4 {
141 if op & (1 << bit) != 0 {
142 offset |= (*delta.get(at).ok_or_else(bad)? as usize) << (8 * bit);
143 at += 1;
144 }
145 }
146 for bit in 0..3 {
147 if op & (0x10 << bit) != 0 {
148 size |= (*delta.get(at).ok_or_else(bad)? as usize) << (8 * bit);
149 at += 1;
150 }
151 }
152 if size == 0 {
153 size = 0x10000;
154 }
155 out.extend_from_slice(base.get(offset..offset + size).ok_or_else(bad)?);
156 } else if op != 0 {
157 out.extend_from_slice(delta.get(at..at + op as usize).ok_or_else(bad)?);
158 at += op as usize;
159 } else {
160 return Err(bad());
161 }
162 }
163 if out.len() != target {
164 return Err(bad());
165 }
166 Ok(out)
167}
168
169impl Pack {
170 /// Reads every object in `pack`, resolving the deltas whose bases are
171 /// in it.
172 pub fn parse(pack: &[u8]) -> Result<Pack, String> {
173 if pack.len() < 12 || &pack[..4] != b"PACK" {
174 return Err("not a pack".into());
175 }
176 let count = u32::from_be_bytes([pack[8], pack[9], pack[10], pack[11]]) as usize;
177 let mut at = 12;
178 let mut result = Pack::default();
179 let mut inflated = 0usize;
180 for _ in 0..count {
181 let start = at;
182 let mut byte = *pack.get(at).ok_or("the pack ends early")?;
183 at += 1;
184 let code = (byte >> 4) & 7;
185 let mut size = (byte & 15) as usize;
186 let mut shift = 4;
187 while byte & 0x80 != 0 {
188 byte = *pack.get(at).ok_or("the pack ends early")?;
189 at += 1;
190 size |= ((byte & 0x7f) as usize) << shift;
191 shift += 7;
192 }
193 inflated += size;
194 if inflated > MAX_INFLATED {
195 return Err("the pack is too large to read".into());
196 }
197 let base = match code {
198 6 => {
199 let mut byte = *pack.get(at).ok_or("the pack ends early")?;
200 at += 1;
201 let mut offset = (byte & 0x7f) as usize;
202 while byte & 0x80 != 0 {
203 byte = *pack.get(at).ok_or("the pack ends early")?;
204 at += 1;
205 offset = ((offset + 1) << 7) | (byte & 0x7f) as usize;
206 }
207 Some(Base::Offset(start.checked_sub(offset).ok_or("a delta points before the pack")?))
208 }
209 7 => {
210 let id = pack.get(at..at + 20).ok_or("the pack ends early")?;
211 at += 20;
212 Some(Base::Id(id.iter().map(|byte| format!("{byte:02x}")).collect()))
213 }
214 _ => None,
215 };
216 let (data, consumed) = inflate(&pack[at..], size)?;
217 at += consumed;
218 match base {
219 Some(base) => result.pending.push((start, Delta { base, data })),
220 None => {
221 let kind = ObjectKind::from_type(code).ok_or("an object has an unknown type")?;
222 result.insert(start, kind, data);
223 }
224 }
225 }
226 result.resolve();
227 Ok(result)
228 }
229
230 fn insert(&mut self, offset: usize, kind: ObjectKind, data: Vec<u8>) {
231 let id = object_id(kind, &data);
232 if kind == ObjectKind::Commit {
233 self.commits.push(id.clone());
234 }
235 self.at_offset.insert(offset, id.clone());
236 self.objects.insert(id, (kind, data));
237 }
238
239 /// Resolves every pending delta whose base is known by now.
240 fn resolve(&mut self) {
241 loop {
242 let mut progress = false;
243 let pending = std::mem::take(&mut self.pending);
244 for (offset, delta) in pending {
245 let base_id = match &delta.base {
246 Base::Offset(base) => self.at_offset.get(base).cloned(),
247 Base::Id(id) => Some(id.clone()),
248 };
249 let resolved = base_id
250 .and_then(|id| self.objects.get(&id))
251 .map(|(kind, base)| (*kind, apply_delta(base, &delta.data)));
252 match resolved {
253 Some((kind, Ok(data))) => {
254 self.insert(offset, kind, data);
255 progress = true;
256 }
257 // A delta that does not apply is dropped.
258 Some((_, Err(_))) => progress = true,
259 None => self.pending.push((offset, delta)),
260 }
261 }
262 if !progress || self.pending.is_empty() {
263 return;
264 }
265 }
266 }
267
268 /// Objects the pack's deltas are based on that it does not hold: what
269 /// the repository has to supply.
270 pub fn missing_bases(&self) -> Vec<String> {
271 let mut ids: Vec<String> = self
272 .pending
273 .iter()
274 .filter_map(|(_, delta)| match &delta.base {
275 Base::Id(id) if !self.objects.contains_key(id) => Some(id.clone()),
276 _ => None,
277 })
278 .collect();
279 ids.sort();
280 ids.dedup();
281 ids
282 }
283
284 /// Supplies a base object from the repository, and resolves what
285 /// depends on it.
286 pub fn supply(&mut self, id: &str, kind: ObjectKind, data: Vec<u8>) {
287 self.objects.insert(id.to_owned(), (kind, data));
288 self.resolve();
289 }
290
291 /// Deltas still unresolved.
292 pub fn unresolved(&self) -> usize {
293 self.pending.len()
294 }
295
296 pub fn get(&self, id: &str) -> Option<(ObjectKind, &[u8])> {
297 self.objects.get(id).map(|(kind, data)| (*kind, data.as_slice()))
298 }
299
300 pub fn contains(&self, id: &str) -> bool {
301 self.objects.contains_key(id)
302 }
303
304 /// The commits in the pack: what the push adds.
305 pub fn commits(&self) -> &[String] {
306 &self.commits
307 }
308
309 pub fn commit(&self, id: &str) -> Option<CommitInfo> {
310 match self.get(id)? {
311 (ObjectKind::Commit, data) => Some(parse_commit(data)),
312 _ => None,
313 }
314 }
315
316 pub fn tree(&self, id: &str) -> Option<Vec<TreeItem>> {
317 match self.get(id)? {
318 (ObjectKind::Tree, data) => Some(parse_tree(data)),
319 _ => None,
320 }
321 }
322
323 pub fn blob(&self, id: &str) -> Option<&[u8]> {
324 match self.get(id)? {
325 (ObjectKind::Blob, data) => Some(data),
326 _ => None,
327 }
328 }
329}
330
331/// What a commit says about its place in history.
332#[derive(Debug, PartialEq, Eq)]
333pub struct CommitInfo {
334 pub tree: String,
335 pub parents: Vec<String>,
336}
337
338pub fn parse_commit(data: &[u8]) -> CommitInfo {
339 let text = String::from_utf8_lossy(data);
340 let mut info = CommitInfo { tree: String::new(), parents: Vec::new() };
341 for line in text.lines() {
342 if line.is_empty() {
343 break;
344 }
345 if let Some(tree) = line.strip_prefix("tree ") {
346 info.tree = tree.trim().to_owned();
347 } else if let Some(parent) = line.strip_prefix("parent ") {
348 info.parents.push(parent.trim().to_owned());
349 }
350 }
351 info
352}
353
354/// One entry of a tree.
355#[derive(Clone, Debug, PartialEq, Eq)]
356pub struct TreeItem {
357 /// `100644`, `100755`, `120000`, `40000` or `160000`.
358 pub mode: String,
359 pub name: String,
360 pub id: String,
361}
362
363impl TreeItem {
364 pub fn is_tree(&self) -> bool {
365 self.mode == "40000"
366 }
367
368 /// A regular or executable file; not a link or a submodule.
369 pub fn is_file(&self) -> bool {
370 self.mode.starts_with("100")
371 }
372}
373
374pub fn parse_tree(data: &[u8]) -> Vec<TreeItem> {
375 let mut items = Vec::new();
376 let mut at = 0;
377 while at < data.len() {
378 let Some(space) = data[at..].iter().position(|byte| *byte == b' ') else {
379 break;
380 };
381 let Some(nul) = data[at + space..].iter().position(|byte| *byte == 0) else {
382 break;
383 };
384 let mode = String::from_utf8_lossy(&data[at..at + space]).into_owned();
385 let name = String::from_utf8_lossy(&data[at + space + 1..at + space + nul]).into_owned();
386 let id_at = at + space + nul + 1;
387 let Some(id) = data.get(id_at..id_at + 20) else {
388 break;
389 };
390 items.push(TreeItem { mode, name, id: id.iter().map(|byte| format!("{byte:02x}")).collect() });
391 at = id_at + 20;
392 }
393 items
394}
395
396/// A tree's bytes from its entries, as git writes them: what a delta
397/// against a tree the repository has needs as its base.
398pub fn encode_tree(items: &[TreeItem]) -> Vec<u8> {
399 let mut out = Vec::new();
400 for item in items {
401 out.extend_from_slice(item.mode.as_bytes());
402 out.push(b' ');
403 out.extend_from_slice(item.name.as_bytes());
404 out.push(0);
405 for pair in item.id.as_bytes().chunks(2) {
406 out.push(u8::from_str_radix(std::str::from_utf8(pair).unwrap_or("00"), 16).unwrap_or(0));
407 }
408 }
409 out
410}
411
412#[cfg(test)]
413pub(crate) mod tests {
414 use super::*;
415 use miniz_oxide::deflate::compress_to_vec_zlib;
416
417 fn header(code: u8, size: usize) -> Vec<u8> {
418 let mut out = Vec::new();
419 let mut byte = (code << 4) | (size & 15) as u8;
420 let mut rest = size >> 4;
421 while rest > 0 {
422 out.push(byte | 0x80);
423 byte = (rest & 0x7f) as u8;
424 rest >>= 7;
425 }
426 out.push(byte);
427 out
428 }
429
430 /// A pack of whole objects, plus ref-deltas given as (base id, delta).
431 pub fn build_pack(objects: &[(ObjectKind, Vec<u8>)], ref_deltas: &[(String, Vec<u8>)]) -> Vec<u8> {
432 let mut pack = b"PACK".to_vec();
433 pack.extend_from_slice(&2u32.to_be_bytes());
434 pack.extend_from_slice(&((objects.len() + ref_deltas.len()) as u32).to_be_bytes());
435 for (kind, data) in objects {
436 let code = match kind {
437 ObjectKind::Commit => 1,
438 ObjectKind::Tree => 2,
439 ObjectKind::Blob => 3,
440 ObjectKind::Tag => 4,
441 };
442 pack.extend(header(code, data.len()));
443 pack.extend(compress_to_vec_zlib(data, 6));
444 }
445 for (base, delta) in ref_deltas {
446 pack.extend(header(7, delta.len()));
447 for pair in base.as_bytes().chunks(2) {
448 pack.push(u8::from_str_radix(std::str::from_utf8(pair).unwrap(), 16).unwrap());
449 }
450 pack.extend(compress_to_vec_zlib(delta, 6));
451 }
452 pack.extend_from_slice(&[0u8; 20]);
453 pack
454 }
455
456 /// A delta that keeps the first `keep` bytes of `base` and appends `tail`.
457 pub fn delta(base: &[u8], keep: usize, tail: &[u8]) -> Vec<u8> {
458 let mut out = Vec::new();
459 let put = |mut value: usize, out: &mut Vec<u8>| loop {
460 let byte = (value & 0x7f) as u8;
461 value >>= 7;
462 if value == 0 {
463 out.push(byte);
464 break;
465 }
466 out.push(byte | 0x80);
467 };
468 put(base.len(), &mut out);
469 put(keep + tail.len(), &mut out);
470 // Copy from offset 0, `keep` bytes (one size byte).
471 out.push(0x80 | 0x10);
472 out.push(keep as u8);
473 out.push(tail.len() as u8);
474 out.extend_from_slice(tail);
475 out
476 }
477
478 #[test]
479 fn ids_match_git() {
480 assert_eq!(object_id(ObjectKind::Blob, b""), "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391");
481 assert_eq!(object_id(ObjectKind::Blob, b"hello\n"), "ce013625030ba8dba906f756967f9e9ca394464a");
482 }
483
484 #[test]
485 fn whole_objects_and_deltas_are_read() {
486 let base = b"first line\n".to_vec();
487 let base_id = object_id(ObjectKind::Blob, &base);
488 let pack = build_pack(&[(ObjectKind::Blob, base.clone())], &[(base_id.clone(), delta(&base, base.len(), b"second\n"))]);
489 let parsed = Pack::parse(&pack).unwrap();
490 let grown = b"first line\nsecond\n";
491 assert_eq!(parsed.blob(&object_id(ObjectKind::Blob, grown)), Some(&grown[..]));
492 assert!(parsed.missing_bases().is_empty());
493 }
494
495 #[test]
496 fn a_thin_pack_waits_for_its_base() {
497 let base = b"kept in the repository\n".to_vec();
498 let base_id = object_id(ObjectKind::Blob, &base);
499 let pack = build_pack(&[], &[(base_id.clone(), delta(&base, 4, b" and more\n"))]);
500 let mut parsed = Pack::parse(&pack).unwrap();
501 assert_eq!(parsed.missing_bases(), vec![base_id.clone()]);
502 parsed.supply(&base_id, ObjectKind::Blob, base);
503 assert_eq!(parsed.unresolved(), 0);
504 assert!(parsed.blob(&object_id(ObjectKind::Blob, b"kept and more\n")).is_some());
505 }
506
507 #[test]
508 fn commits_and_trees_are_parsed_and_trees_rebuilt() {
509 let blob_id = object_id(ObjectKind::Blob, b"x");
510 let tree = encode_tree(&[
511 TreeItem { mode: "100644".into(), name: "a.txt".into(), id: blob_id.clone() },
512 TreeItem { mode: "40000".into(), name: "src".into(), id: blob_id.clone() },
513 ]);
514 let items = parse_tree(&tree);
515 assert_eq!(items.len(), 2);
516 assert!(items[0].is_file() && items[1].is_tree());
517 assert_eq!(encode_tree(&items), tree);
518 let commit = format!("tree {}\nparent aaaa\nparent bbbb\nauthor x\n\nmessage\nparent no\n", object_id(ObjectKind::Tree, &tree));
519 let info = parse_commit(commit.as_bytes());
520 assert_eq!(info.parents, ["aaaa", "bbbb"]);
521 assert_eq!(info.tree.len(), 40);
522 let pack = build_pack(&[(ObjectKind::Commit, commit.into_bytes())], &[]);
523 assert_eq!(Pack::parse(&pack).unwrap().commits().len(), 1);
524 }
525
526 #[test]
527 fn the_pack_is_found_after_the_commands() {
528 let line = b"old new refs/heads/PACKAGING\0report-status\n";
529 let commands = [format!("{:04x}", line.len() + 4).into_bytes(), line.to_vec(), b"0000".to_vec()].concat();
530 let body = [commands.clone(), b"PACK\0\0\0\x02".to_vec()].concat();
531 assert_eq!(pack_start(&body), Some(commands.len()));
532 assert_eq!(pack_start(&commands), None);
533 assert!(Pack::parse(b"nope").is_err());
534 }
535}