Meg's Mirrors

zig

1	//! Git support for package fetching.
2	//!
3	//! This is not intended to support all features of Git: it is limited to the
4	//! basic functionality needed to clone a repository for the purpose of fetching
5	//! a package.
6
7	const std = @import("std");
8	const Io = std.Io;
9	const mem = std.mem;
10	const testing = std.testing;
11	const Allocator = mem.Allocator;
12	const Sha1 = std.crypto.hash.Sha1;
13	const Sha256 = std.crypto.hash.sha2.Sha256;
14	const assert = std.debug.assert;
15
16	/// The ID of a Git object.
17	pub const Oid = union(Format) {
18	sha1: [Sha1.digest_length]u8,
19	sha256: [Sha256.digest_length]u8,
20
21	pub const max_formatted_length = len: {
22	var max: usize = 0;
23	for (std.enums.values(Format)) |f| {
24	max = @max(max, f.formattedLength());
25	}
26	break :len max;
27	};
28
29	pub const Format = enum {
30	sha1,
31	sha256,
32
33	pub fn byteLength(f: Format) usize {
34	return switch (f) {
35	.sha1 => Sha1.digest_length,
36	.sha256 => Sha256.digest_length,
37	};
38	}
39
40	pub fn formattedLength(f: Format) usize {
41	return 2 * f.byteLength();
42	}
43	};
44
45	const Hasher = union(Format) {
46	sha1: Sha1,
47	sha256: Sha256,
48
49	fn init(oid_format: Format) Hasher {
50	return switch (oid_format) {
51	.sha1 => .{ .sha1 = Sha1.init(.{}) },
52	.sha256 => .{ .sha256 = Sha256.init(.{}) },
53	};
54	}
55
56	// Must be public for use from HashedReader and HashedWriter.
57	pub fn update(hasher: *Hasher, b: []const u8) void {
58	switch (hasher.*) {
59	inline else => |*inner| inner.update(b),
60	}
61	}
62
63	fn finalResult(hasher: *Hasher) Oid {
64	return switch (hasher.*) {
65	inline else => |*inner, tag| @unionInit(Oid, @tagName(tag), inner.finalResult()),
66	};
67	}
68	};
69
70	const Hashing = union(Format) {
71	sha1: Io.Writer.Hashing(Sha1),
72	sha256: Io.Writer.Hashing(Sha256),
73
74	fn init(oid_format: Format, buffer: []u8) Hashing {
75	return switch (oid_format) {
76	.sha1 => .{ .sha1 = .init(buffer) },
77	.sha256 => .{ .sha256 = .init(buffer) },
78	};
79	}
80
81	fn writer(h: *@This()) *Io.Writer {
82	return switch (h.*) {
83	inline else => |*inner| &inner.writer,
84	};
85	}
86
87	fn final(h: *@This()) Oid {
88	switch (h.*) {
89	inline else => |*inner, tag| {
90	inner.writer.flush() catch unreachable; // hashers cannot fail
91	return @unionInit(Oid, @tagName(tag), inner.hasher.finalResult());
92	},
93	}
94	}
95	};
96
97	pub fn fromBytes(oid_format: Format, bytes: []const u8) Oid {
98	assert(bytes.len == oid_format.byteLength());
99	return switch (oid_format) {
100	inline else => |tag| @unionInit(Oid, @tagName(tag), bytes[0..comptime tag.byteLength()].*),
101	};
102	}
103
104	pub fn readBytes(oid_format: Format, reader: *Io.Reader) !Oid {
105	return switch (oid_format) {
106	inline else => |tag| @unionInit(Oid, @tagName(tag), (try reader.takeArray(tag.byteLength())).*),
107	};
108	}
109
110	pub fn parse(oid_format: Format, s: []const u8) error{InvalidOid}!Oid {
111	switch (oid_format) {
112	inline else => |tag| {
113	if (s.len != tag.formattedLength()) return error.InvalidOid;
114	var bytes: [tag.byteLength()]u8 = undefined;
115	for (&bytes, 0..) |*b, i| {
116	b.* = std.fmt.parseUnsigned(u8, s[2 * i ..][0..2], 16) catch return error.InvalidOid;
117	}
118	return @unionInit(Oid, @tagName(tag), bytes);
119	},
120	}
121	}
122
123	test parse {
124	try testing.expectEqualSlices(
125	u8,
126	&.{ 0xCE, 0x91, 0x9C, 0xCF, 0x45, 0x95, 0x18, 0x56, 0xA7, 0x62, 0xFF, 0xDB, 0x8E, 0xF8, 0x50, 0x30, 0x1C, 0xD8, 0xC5, 0x88 },
127	&(try parse(.sha1, "ce919ccf45951856a762ffdb8ef850301cd8c588")).sha1,
128	);
129	try testing.expectError(error.InvalidOid, parse(.sha256, "ce919ccf45951856a762ffdb8ef850301cd8c588"));
130	try testing.expectError(error.InvalidOid, parse(.sha1, "7f444a92bd4572ee4a28b2c63059924a9ca1829138553ef3e7c41ee159afae7a"));
131	try testing.expectEqualSlices(
132	u8,
133	&.{ 0x7F, 0x44, 0x4A, 0x92, 0xBD, 0x45, 0x72, 0xEE, 0x4A, 0x28, 0xB2, 0xC6, 0x30, 0x59, 0x92, 0x4A, 0x9C, 0xA1, 0x82, 0x91, 0x38, 0x55, 0x3E, 0xF3, 0xE7, 0xC4, 0x1E, 0xE1, 0x59, 0xAF, 0xAE, 0x7A },
134	&(try parse(.sha256, "7f444a92bd4572ee4a28b2c63059924a9ca1829138553ef3e7c41ee159afae7a")).sha256,
135	);
136	try testing.expectError(error.InvalidOid, parse(.sha1, "ce919ccf"));
137	try testing.expectError(error.InvalidOid, parse(.sha256, "ce919ccf"));
138	try testing.expectError(error.InvalidOid, parse(.sha1, "master"));
139	try testing.expectError(error.InvalidOid, parse(.sha256, "master"));
140	try testing.expectError(error.InvalidOid, parse(.sha1, "HEAD"));
141	try testing.expectError(error.InvalidOid, parse(.sha256, "HEAD"));
142	}
143
144	pub fn parseAny(s: []const u8) error{InvalidOid}!Oid {
145	return for (std.enums.values(Format)) |f| {
146	if (s.len == f.formattedLength()) break parse(f, s);
147	} else error.InvalidOid;
148	}
149
150	pub fn format(oid: Oid, writer: *Io.Writer) Io.Writer.Error!void {
151	try writer.print("{x}", .{oid.slice()});
152	}
153
154	pub fn slice(oid: *const Oid) []const u8 {
155	return switch (oid.*) {
156	inline else => |*bytes| bytes,
157	};
158	}
159	};
160
161	pub const Diagnostics = struct {
162	allocator: Allocator,
163	errors: std.ArrayList(Error) = .empty,
164
165	pub const Error = union(enum) {
166	unable_to_create_sym_link: struct {
167	code: anyerror,
168	file_name: []const u8,
169	link_name: []const u8,
170	},
171	unable_to_create_file: struct {
172	code: anyerror,
173	file_name: []const u8,
174	},
175	};
176
177	pub fn deinit(d: *Diagnostics) void {
178	for (d.errors.items) |item| {
179	switch (item) {
180	.unable_to_create_sym_link => |info| {
181	d.allocator.free(info.file_name);
182	d.allocator.free(info.link_name);
183	},
184	.unable_to_create_file => |info| {
185	d.allocator.free(info.file_name);
186	},
187	}
188	}
189	d.errors.deinit(d.allocator);
190	d.* = undefined;
191	}
192	};
193
194	pub const Repository = struct {
195	odb: Odb,
196
197	pub fn init(
198	repo: *Repository,
199	allocator: Allocator,
200	format: Oid.Format,
201	pack_file: *Io.File.Reader,
202	index_file: *Io.File.Reader,
203	) !void {
204	repo.* = .{ .odb = undefined };
205	try repo.odb.init(allocator, format, pack_file, index_file);
206	}
207
208	pub fn deinit(repository: *Repository) void {
209	repository.odb.deinit();
210	repository.* = undefined;
211	}
212
213	/// Checks out the repository at `commit_oid` to `worktree`.
214	pub fn checkout(
215	repository: *Repository,
216	io: Io,
217	worktree: Io.Dir,
218	commit_oid: Oid,
219	diagnostics: *Diagnostics,
220	) !void {
221	try repository.odb.seekOid(commit_oid);
222	const tree_oid = tree_oid: {
223	const commit_object = try repository.odb.readObject();
224	if (commit_object.type != .commit) return error.NotACommit;
225	break :tree_oid try getCommitTree(repository.odb.format, commit_object.data);
226	};
227	try repository.checkoutTree(io, worktree, tree_oid, "", diagnostics);
228	}
229
230	/// Checks out the tree at `tree_oid` to `worktree`.
231	fn checkoutTree(
232	repository: *Repository,
233	io: Io,
234	dir: Io.Dir,
235	tree_oid: Oid,
236	current_path: []const u8,
237	diagnostics: *Diagnostics,
238	) !void {
239	try repository.odb.seekOid(tree_oid);
240	const tree_object = try repository.odb.readObject();
241	if (tree_object.type != .tree) return error.NotATree;
242	// The tree object may be evicted from the object cache while we're
243	// iterating over it, so we can make a defensive copy here to make sure
244	// it remains valid until we're done with it
245	const tree_data = try repository.odb.allocator.dupe(u8, tree_object.data);
246	defer repository.odb.allocator.free(tree_data);
247
248	var tree_iter: TreeIterator = .{
249	.format = repository.odb.format,
250	.data = tree_data,
251	.pos = 0,
252	};
253	while (try tree_iter.next()) |entry| {
254	switch (entry.type) {
255	.directory => {
256	try dir.createDir(io, entry.name, .default_dir);
257	var subdir = try dir.openDir(io, entry.name, .{});
258	defer subdir.close(io);
259	const sub_path = try std.fs.path.join(repository.odb.allocator, &.{ current_path, entry.name });
260	defer repository.odb.allocator.free(sub_path);
261	try repository.checkoutTree(io, subdir, entry.oid, sub_path, diagnostics);
262	},
263	.file => {
264	try repository.odb.seekOid(entry.oid);
265	const file_object = try repository.odb.readObject();
266	if (file_object.type != .blob) return error.InvalidFile;
267	var file = dir.createFile(io, entry.name, .{ .exclusive = true }) catch |e| {
268	const file_name = try std.fs.path.join(diagnostics.allocator, &.{ current_path, entry.name });
269	errdefer diagnostics.allocator.free(file_name);
270	try diagnostics.errors.append(diagnostics.allocator, .{ .unable_to_create_file = .{
271	.code = e,
272	.file_name = file_name,
273	} });
274	continue;
275	};
276	defer file.close(io);
277	try file.writePositionalAll(io, file_object.data, 0);
278	},
279	.symlink => {
280	try repository.odb.seekOid(entry.oid);
281	const symlink_object = try repository.odb.readObject();
282	if (symlink_object.type != .blob) return error.InvalidFile;
283	const link_name = symlink_object.data;
284	dir.symLink(io, link_name, entry.name, .{}) catch |e| {
285	const file_name = try std.fs.path.join(diagnostics.allocator, &.{ current_path, entry.name });
286	errdefer diagnostics.allocator.free(file_name);
287	const link_name_dup = try diagnostics.allocator.dupe(u8, link_name);
288	errdefer diagnostics.allocator.free(link_name_dup);
289	try diagnostics.errors.append(diagnostics.allocator, .{ .unable_to_create_sym_link = .{
290	.code = e,
291	.file_name = file_name,
292	.link_name = link_name_dup,
293	} });
294	};
295	},
296	.gitlink => {
297	// Consistent with git archive behavior, create the directory but
298	// do nothing else
299	try dir.createDir(io, entry.name, .default_dir);
300	},
301	}
302	}
303	}
304
305	/// Returns the ID of the tree associated with the given commit (provided as
306	/// raw object data).
307	fn getCommitTree(format: Oid.Format, commit_data: []const u8) !Oid {
308	if (!mem.startsWith(u8, commit_data, "tree ") or
309	commit_data.len < "tree ".len + format.formattedLength() + "\n".len or
310	commit_data["tree ".len + format.formattedLength()] != '\n')
311	{
312	return error.InvalidCommit;
313	}
314	return try .parse(format, commit_data["tree ".len..][0..format.formattedLength()]);
315	}
316
317	const TreeIterator = struct {
318	format: Oid.Format,
319	data: []const u8,
320	pos: usize,
321
322	const Entry = struct {
323	type: Type,
324	executable: bool,
325	name: [:0]const u8,
326	oid: Oid,
327
328	const Type = enum(u4) {
329	directory = 0o4,
330	file = 0o10,
331	symlink = 0o12,
332	gitlink = 0o16,
333	};
334	};
335
336	fn next(iterator: *TreeIterator) !?Entry {
337	if (iterator.pos == iterator.data.len) return null;
338
339	const mode_end = mem.findScalarPos(u8, iterator.data, iterator.pos, ' ') orelse return error.InvalidTree;
340	const mode: packed struct {
341	permission: u9,
342	unused: u3,
343	type: u4,
344	} = @bitCast(std.fmt.parseUnsigned(u16, iterator.data[iterator.pos..mode_end], 8) catch return error.InvalidTree);
345	const @"type" = std.enums.fromInt(Entry.Type, mode.type) orelse return error.InvalidTree;
346	const executable = switch (mode.permission) {
347	0 => if (@"type" == .file) return error.InvalidTree else false,
348	0o644 => if (@"type" != .file) return error.InvalidTree else false,
349	0o755 => if (@"type" != .file) return error.InvalidTree else true,
350	else => return error.InvalidTree,
351	};
352	iterator.pos = mode_end + 1;
353
354	const name_end = mem.findScalarPos(u8, iterator.data, iterator.pos, 0) orelse return error.InvalidTree;
355	const name = iterator.data[iterator.pos..name_end :0];
356	iterator.pos = name_end + 1;
357
358	const oid_length = iterator.format.byteLength();
359	if (iterator.pos + oid_length > iterator.data.len) return error.InvalidTree;
360	const oid: Oid = .fromBytes(iterator.format, iterator.data[iterator.pos..][0..oid_length]);
361	iterator.pos += oid_length;
362
363	return .{ .type = @"type", .executable = executable, .name = name, .oid = oid };
364	}
365	};
366	};
367
368	/// A Git object database backed by a packfile. A packfile index is also used
369	/// for efficient access to objects in the packfile.
370	///
371	/// The format of the packfile and its associated index are documented in
372	/// [pack-format](https://git-scm.com/docs/pack-format).
373	const Odb = struct {
374	format: Oid.Format,
375	pack_file: *Io.File.Reader,
376	index_header: IndexHeader,
377	index_file: *Io.File.Reader,
378	cache: ObjectCache = .{},
379	allocator: Allocator,
380
381	/// Initializes the database from open pack and index files.
382	fn init(
383	odb: *Odb,
384	allocator: Allocator,
385	format: Oid.Format,
386	pack_file: *Io.File.Reader,
387	index_file: *Io.File.Reader,
388	) !void {
389	try pack_file.seekTo(0);
390	try index_file.seekTo(0);
391	odb.* = .{
392	.format = format,
393	.pack_file = pack_file,
394	.index_header = undefined,
395	.index_file = index_file,
396	.allocator = allocator,
397	};
398	try odb.index_header.read(&index_file.interface);
399	}
400
401	fn deinit(odb: *Odb) void {
402	odb.cache.deinit(odb.allocator);
403	odb.* = undefined;
404	}
405
406	/// Reads the object at the current position in the database.
407	fn readObject(odb: *Odb) !Object {
408	var base_offset = odb.pack_file.logicalPos();
409	var base_header: EntryHeader = undefined;
410	var delta_offsets: std.ArrayList(u64) = .empty;
411	defer delta_offsets.deinit(odb.allocator);
412	const base_object = while (true) {
413	if (odb.cache.get(base_offset)) |base_object| break base_object;
414
415	base_header = try EntryHeader.read(odb.format, &odb.pack_file.interface);
416	switch (base_header) {
417	.ofs_delta => |ofs_delta| {
418	try delta_offsets.append(odb.allocator, base_offset);
419	base_offset = std.math.sub(u64, base_offset, ofs_delta.offset) catch return error.InvalidFormat;
420	try odb.pack_file.seekTo(base_offset);
421	},
422	.ref_delta => |ref_delta| {
423	try delta_offsets.append(odb.allocator, base_offset);
424	try odb.seekOid(ref_delta.base_object);
425	base_offset = odb.pack_file.logicalPos();
426	},
427	else => {
428	const base_data = try readObjectRaw(odb.allocator, &odb.pack_file.interface, base_header.uncompressedLength());
429	errdefer odb.allocator.free(base_data);
430	const base_object: Object = .{ .type = base_header.objectType(), .data = base_data };
431	try odb.cache.put(odb.allocator, base_offset, base_object);
432	break base_object;
433	},
434	}
435	};
436
437	const base_data = try resolveDeltaChain(
438	odb.allocator,
439	odb.format,
440	odb.pack_file,
441	base_object,
442	delta_offsets.items,
443	&odb.cache,
444	);
445
446	return .{ .type = base_object.type, .data = base_data };
447	}
448
449	/// Seeks to the beginning of the object with the given ID.
450	fn seekOid(odb: *Odb, oid: Oid) !void {
451	const oid_length = odb.format.byteLength();
452	const key = oid.slice()[0];
453	var start_index = if (key > 0) odb.index_header.fan_out_table[key - 1] else 0;
454	var end_index = odb.index_header.fan_out_table[key];
455	const found_index = while (start_index < end_index) {
456	const mid_index = start_index + (end_index - start_index) / 2;
457	try odb.index_file.seekTo(IndexHeader.size + mid_index * oid_length);
458	const mid_oid = try Oid.readBytes(odb.format, &odb.index_file.interface);
459	switch (mem.order(u8, mid_oid.slice(), oid.slice())) {
460	.lt => start_index = mid_index + 1,
461	.gt => end_index = mid_index,
462	.eq => break mid_index,
463	}
464	} else return error.ObjectNotFound;
465
466	const n_objects = odb.index_header.fan_out_table[255];
467	const offset_values_start = IndexHeader.size + n_objects * (oid_length + 4);
468	try odb.index_file.seekTo(offset_values_start + found_index * 4);
469	const l1_offset: packed struct { value: u31, big: bool } = @bitCast(try odb.index_file.interface.takeInt(u32, .big));
470	const pack_offset = pack_offset: {
471	if (l1_offset.big) {
472	const l2_offset_values_start = offset_values_start + n_objects * 4;
473	try odb.index_file.seekTo(l2_offset_values_start + l1_offset.value * 4);
474	break :pack_offset try odb.index_file.interface.takeInt(u64, .big);
475	} else {
476	break :pack_offset l1_offset.value;
477	}
478	};
479
480	try odb.pack_file.seekTo(pack_offset);
481	}
482	};
483
484	const Object = struct {
485	type: Type,
486	data: []const u8,
487
488	const Type = enum {
489	commit,
490	tree,
491	blob,
492	tag,
493	};
494	};
495
496	/// A cache for object data.
497	///
498	/// The purpose of this cache is to speed up resolution of deltas by caching the
499	/// results of resolving delta objects, while maintaining a maximum cache size
500	/// to avoid excessive memory usage. If the total size of the objects in the
501	/// cache exceeds the maximum, the cache will begin evicting the least recently
502	/// used objects: when resolving delta chains, the most recently used objects
503	/// will likely be more helpful as they will be further along in the chain
504	/// (skipping earlier reconstruction steps).
505	///
506	/// Object data stored in the cache is managed by the cache. It should not be
507	/// freed by the caller at any point after inserting it into the cache. Any
508	/// objects remaining in the cache will be freed when the cache itself is freed.
509	const ObjectCache = struct {
510	objects: std.AutoHashMapUnmanaged(u64, CacheEntry) = .empty,
511	lru_nodes: std.DoublyLinkedList = .{},
512	lru_nodes_len: usize = 0,
513	byte_size: usize = 0,
514
515	const max_byte_size = 128 * 1024 * 1024; // 128MiB
516	/// A list of offsets stored in the cache, with the most recently used
517	/// entries at the end.
518	const LruListNode = struct {
519	data: u64,
520	node: std.DoublyLinkedList.Node,
521	};
522	const CacheEntry = struct { object: Object, lru_node: *LruListNode };
523
524	fn deinit(cache: *ObjectCache, allocator: Allocator) void {
525	var object_iterator = cache.objects.iterator();
526	while (object_iterator.next()) |object| {
527	allocator.free(object.value_ptr.object.data);
528	allocator.destroy(object.value_ptr.lru_node);
529	}
530	cache.objects.deinit(allocator);
531	cache.* = undefined;
532	}
533
534	/// Gets an object from the cache, moving it to the most recently used
535	/// position if it is present.
536	fn get(cache: *ObjectCache, offset: u64) ?Object {
537	if (cache.objects.get(offset)) |entry| {
538	cache.lru_nodes.remove(&entry.lru_node.node);
539	cache.lru_nodes.append(&entry.lru_node.node);
540	return entry.object;
541	} else {
542	return null;
543	}
544	}
545
546	/// Puts an object in the cache, possibly evicting older entries if the
547	/// cache exceeds its maximum size. Note that, although old objects may
548	/// be evicted, the object just added to the cache with this function
549	/// will not be evicted before the next call to `put` or `deinit` even if
550	/// it exceeds the maximum cache size.
551	fn put(cache: *ObjectCache, allocator: Allocator, offset: u64, object: Object) !void {
552	const lru_node = try allocator.create(LruListNode);
553	errdefer allocator.destroy(lru_node);
554	lru_node.data = offset;
555
556	const gop = try cache.objects.getOrPut(allocator, offset);
557	if (gop.found_existing) {
558	cache.byte_size -= gop.value_ptr.object.data.len;
559	cache.lru_nodes.remove(&gop.value_ptr.lru_node.node);
560	cache.lru_nodes_len -= 1;
561	allocator.destroy(gop.value_ptr.lru_node);
562	allocator.free(gop.value_ptr.object.data);
563	}
564	gop.value_ptr.* = .{ .object = object, .lru_node = lru_node };
565	cache.byte_size += object.data.len;
566	cache.lru_nodes.append(&lru_node.node);
567	cache.lru_nodes_len += 1;
568
569	while (cache.byte_size > max_byte_size and cache.lru_nodes_len > 1) {
570	// The > 1 check is to make sure that we don't evict the most
571	// recently added node, even if it by itself happens to exceed the
572	// maximum size of the cache.
573	const evict_node: *LruListNode = @alignCast(@fieldParentPtr("node", cache.lru_nodes.popFirst().?));
574	cache.lru_nodes_len -= 1;
575	const evict_offset = evict_node.data;
576	allocator.destroy(evict_node);
577	const evict_object = cache.objects.get(evict_offset).?.object;
578	cache.byte_size -= evict_object.data.len;
579	allocator.free(evict_object.data);
580	_ = cache.objects.remove(evict_offset);
581	}
582	}
583	};
584
585	/// A single pkt-line in the Git protocol.
586	///
587	/// The format of a pkt-line is documented in
588	/// [protocol-common](https://git-scm.com/docs/protocol-common). The special
589	/// meanings of the delimiter and response-end packets are documented in
590	/// [protocol-v2](https://git-scm.com/docs/protocol-v2).
591	pub const Packet = union(enum) {
592	flush,
593	delimiter,
594	response_end,
595	data: []const u8,
596
597	pub const max_data_length = 65516;
598
599	/// Reads a packet in pkt-line format.
600	fn read(reader: *Io.Reader) !Packet {
601	const packet: Packet = try .peek(reader);
602	switch (packet) {
603	.data => |data| reader.toss(data.len),
604	else => {},
605	}
606	return packet;
607	}
608
609	/// Consumes the header of a pkt-line packet and reads any associated data
610	/// into the reader's buffer, but does not consume the data.
611	fn peek(reader: *Io.Reader) !Packet {
612	const length = std.fmt.parseUnsigned(u16, try reader.take(4), 16) catch return error.InvalidPacket;
613	switch (length) {
614	0 => return .flush,
615	1 => return .delimiter,
616	2 => return .response_end,
617	3 => return error.InvalidPacket,
618	else => if (length - 4 > max_data_length) return error.InvalidPacket,
619	}
620	return .{ .data = try reader.peek(length - 4) };
621	}
622
623	/// Writes a packet in pkt-line format.
624	fn write(packet: Packet, writer: *Io.Writer) !void {
625	switch (packet) {
626	.flush => try writer.writeAll("0000"),
627	.delimiter => try writer.writeAll("0001"),
628	.response_end => try writer.writeAll("0002"),
629	.data => |data| {
630	assert(data.len <= max_data_length);
631	try writer.print("{x:0>4}", .{data.len + 4});
632	try writer.writeAll(data);
633	},
634	}
635	}
636
637	/// Returns the normalized form of textual packet data, stripping any
638	/// trailing '\n'.
639	///
640	/// As documented in
641	/// [protocol-common](https://git-scm.com/docs/protocol-common#_pkt_line_format),
642	/// non-binary (textual) pkt-line data should contain a trailing '\n', but
643	/// is not required to do so (implementations must support both forms).
644	fn normalizeText(data: []const u8) []const u8 {
645	return if (mem.endsWith(u8, data, "\n"))
646	data[0 .. data.len - 1]
647	else
648	data;
649	}
650	};
651
652	/// A client session for the Git protocol, currently limited to an HTTP(S)
653	/// transport. Only protocol version 2 is supported, as documented in
654	/// [protocol-v2](https://git-scm.com/docs/protocol-v2).
655	pub const Session = struct {
656	transport: *std.http.Client,
657	location: Location,
658	supports_agent: bool,
659	supports_shallow: bool,
660	object_format: Oid.Format,
661	arena: Allocator,
662
663	const agent = "zig/" ++ @import("builtin").zig_version_string;
664	const agent_capability = std.fmt.comptimePrint("agent={s}\n", .{agent});
665
666	/// Initializes a client session and discovers the capabilities of the
667	/// server for optimal transport.
668	pub fn init(
669	arena: Allocator,
670	transport: *std.http.Client,
671	uri: std.Uri,
672	/// Asserted to be at least `Packet.max_data_length`
673	response_buffer: []u8,
674	) !Session {
675	assert(response_buffer.len >= Packet.max_data_length);
676	var session: Session = .{
677	.transport = transport,
678	.location = try .init(arena, uri),
679	.supports_agent = false,
680	.supports_shallow = false,
681	.object_format = .sha1,
682	.arena = arena,
683	};
684	var capability_iterator: CapabilityIterator = undefined;
685	try session.getCapabilities(&capability_iterator, response_buffer);
686	defer capability_iterator.deinit();
687	while (try capability_iterator.next()) |capability| {
688	if (mem.eql(u8, capability.key, "agent")) {
689	session.supports_agent = true;
690	} else if (mem.eql(u8, capability.key, "fetch")) {
691	var feature_iterator = mem.splitScalar(u8, capability.value orelse continue, ' ');
692	while (feature_iterator.next()) |feature| {
693	if (mem.eql(u8, feature, "shallow")) {
694	session.supports_shallow = true;
695	}
696	}
697	} else if (mem.eql(u8, capability.key, "object-format")) {
698	if (std.meta.stringToEnum(Oid.Format, capability.value orelse continue)) |format| {
699	session.object_format = format;
700	}
701	}
702	}
703	return session;
704	}
705
706	/// An owned `std.Uri` representing the location of the server (base URI).
707	const Location = struct {
708	uri: std.Uri,
709
710	fn init(arena: Allocator, uri: std.Uri) !Location {
711	const scheme = try arena.dupe(u8, uri.scheme);
712	const user = if (uri.user) |user| try std.fmt.allocPrint(arena, "{f}", .{
713	std.fmt.alt(user, .formatUser),
714	}) else null;
715	const password = if (uri.password) |password| try std.fmt.allocPrint(arena, "{f}", .{
716	std.fmt.alt(password, .formatPassword),
717	}) else null;
718	const host = if (uri.host) |host| try std.fmt.allocPrint(arena, "{f}", .{
719	std.fmt.alt(host, .formatHost),
720	}) else null;
721	const path = try std.fmt.allocPrint(arena, "{f}", .{
722	std.fmt.alt(uri.path, .formatPath),
723	});
724	// The query and fragment are not used as part of the base server URI.
725	return .{
726	.uri = .{
727	.scheme = scheme,
728	.user = if (user) |s| .{ .percent_encoded = s } else null,
729	.password = if (password) |s| .{ .percent_encoded = s } else null,
730	.host = if (host) |s| .{ .percent_encoded = s } else null,
731	.port = uri.port,
732	.path = .{ .percent_encoded = path },
733	},
734	};
735	}
736	};
737
738	/// Returns an iterator over capabilities supported by the server.
739	///
740	/// The `session.location` is updated if the server returns a redirect, so
741	/// that subsequent session functions do not need to handle redirects.
742	fn getCapabilities(session: *Session, it: *CapabilityIterator, response_buffer: []u8) !void {
743	const arena = session.arena;
744	assert(response_buffer.len >= Packet.max_data_length);
745	var info_refs_uri = session.location.uri;
746	{
747	const session_uri_path = try std.fmt.allocPrint(arena, "{f}", .{
748	std.fmt.alt(session.location.uri.path, .formatPath),
749	});
750	info_refs_uri.path = .{ .percent_encoded = try std.fs.path.resolvePosix(arena, &.{
751	"/", session_uri_path, "info/refs",
752	}) };
753	}
754	info_refs_uri.query = .{ .percent_encoded = "service=git-upload-pack" };
755	info_refs_uri.fragment = null;
756
757	const max_redirects = 3;
758	it.* = .{
759	.request = try session.transport.request(.GET, info_refs_uri, .{
760	.redirect_behavior = .init(max_redirects),
761	.extra_headers = &.{
762	.{ .name = "Git-Protocol", .value = "version=2" },
763	},
764	}),
765	.reader = undefined,
766	.decompress = undefined,
767	};
768	errdefer it.deinit();
769	const request = &it.request;
770	try request.sendBodiless();
771
772	var redirect_buffer: [1024]u8 = undefined;
773	var response = try request.receiveHead(&redirect_buffer);
774	if (response.head.status != .ok) return error.ProtocolError;
775	const any_redirects_occurred = request.redirect_behavior.remaining() < max_redirects;
776	if (any_redirects_occurred) {
777	const request_uri_path = try std.fmt.allocPrint(arena, "{f}", .{
778	std.fmt.alt(request.uri.path, .formatPath),
779	});
780	if (!mem.endsWith(u8, request_uri_path, "/info/refs")) return error.UnparseableRedirect;
781	var new_uri = request.uri;
782	new_uri.path = .{ .percent_encoded = request_uri_path[0 .. request_uri_path.len - "/info/refs".len] };
783	session.location = try .init(arena, new_uri);
784	}
785
786	const decompress_buffer = try arena.alloc(u8, response.head.content_encoding.minBufferCapacity());
787	it.reader = response.readerDecompressing(response_buffer, &it.decompress, decompress_buffer);
788	var state: enum { response_start, response_content } = .response_start;
789	while (true) {
790	// Some Git servers (at least GitHub) include an additional
791	// '# service=git-upload-pack' informative response before sending
792	// the expected 'version 2' packet and capability information.
793	// This is not universal: SourceHut, for example, does not do this.
794	// Thus, we need to skip any such useless additional responses
795	// before we get the one we're actually looking for. The responses
796	// will be delimited by flush packets.
797	const packet = Packet.read(it.reader) catch |err| switch (err) {
798	error.EndOfStream => return error.UnsupportedProtocol, // 'version 2' packet not found
799	else => |e| return e,
800	};
801	switch (packet) {
802	.flush => state = .response_start,
803	.data => |data| switch (state) {
804	.response_start => if (mem.eql(u8, Packet.normalizeText(data), "version 2")) {
805	return;
806	} else {
807	state = .response_content;
808	},
809	else => {},
810	},
811	else => return error.UnexpectedPacket,
812	}
813	}
814	}
815
816	const CapabilityIterator = struct {
817	request: std.http.Client.Request,
818	reader: *Io.Reader,
819	decompress: std.http.Decompress,
820
821	const Capability = struct {
822	key: []const u8,
823	value: ?[]const u8 = null,
824
825	fn parse(data: []const u8) Capability {
826	return if (mem.findScalar(u8, data, '=')) |separator_pos|
827	.{ .key = data[0..separator_pos], .value = data[separator_pos + 1 ..] }
828	else
829	.{ .key = data };
830	}
831	};
832
833	fn deinit(it: *CapabilityIterator) void {
834	it.request.deinit();
835	it.* = undefined;
836	}
837
838	fn next(it: *CapabilityIterator) !?Capability {
839	switch (try Packet.read(it.reader)) {
840	.flush => return null,
841	.data => |data| return Capability.parse(Packet.normalizeText(data)),
842	else => return error.UnexpectedPacket,
843	}
844	}
845	};
846
847	const ListRefsOptions = struct {
848	/// The ref prefixes (if any) to use to filter the refs available on the
849	/// server. Note that the client must still check the returned refs
850	/// against its desired filters itself: the server is not required to
851	/// respect these prefix filters and may return other refs as well.
852	ref_prefixes: []const []const u8 = &.{},
853	/// Whether to include symref targets for returned symbolic refs.
854	include_symrefs: bool = false,
855	/// Whether to include the peeled object ID for returned tag refs.
856	include_peeled: bool = false,
857	/// Asserted to be at least `Packet.max_data_length`.
858	buffer: []u8,
859	};
860
861	/// Returns an iterator over refs known to the server.
862	pub fn listRefs(session: Session, it: *RefIterator, options: ListRefsOptions) !void {
863	const arena = session.arena;
864	assert(options.buffer.len >= Packet.max_data_length);
865	var upload_pack_uri = session.location.uri;
866	{
867	const session_uri_path = try std.fmt.allocPrint(arena, "{f}", .{
868	std.fmt.alt(session.location.uri.path, .formatPath),
869	});
870	upload_pack_uri.path = .{ .percent_encoded = try std.fs.path.resolvePosix(arena, &.{ "/", session_uri_path, "git-upload-pack" }) };
871	}
872	upload_pack_uri.query = null;
873	upload_pack_uri.fragment = null;
874
875	var body: Io.Writer = .fixed(options.buffer);
876	try Packet.write(.{ .data = "command=ls-refs\n" }, &body);
877	if (session.supports_agent) {
878	try Packet.write(.{ .data = agent_capability }, &body);
879	}
880	{
881	const object_format_packet = try std.fmt.allocPrint(arena, "object-format={t}\n", .{
882	session.object_format,
883	});
884	try Packet.write(.{ .data = object_format_packet }, &body);
885	}
886	try Packet.write(.delimiter, &body);
887	for (options.ref_prefixes) |ref_prefix| {
888	const ref_prefix_packet = try std.fmt.allocPrint(arena, "ref-prefix {s}\n", .{ref_prefix});
889	try Packet.write(.{ .data = ref_prefix_packet }, &body);
890	}
891	if (options.include_symrefs) {
892	try Packet.write(.{ .data = "symrefs\n" }, &body);
893	}
894	if (options.include_peeled) {
895	try Packet.write(.{ .data = "peel\n" }, &body);
896	}
897	try Packet.write(.flush, &body);
898
899	it.* = .{
900	.request = try session.transport.request(.POST, upload_pack_uri, .{
901	.redirect_behavior = .unhandled,
902	.extra_headers = &.{
903	.{ .name = "Content-Type", .value = "application/x-git-upload-pack-request" },
904	.{ .name = "Git-Protocol", .value = "version=2" },
905	},
906	}),
907	.reader = undefined,
908	.format = session.object_format,
909	.decompress = undefined,
910	};
911	const request = &it.request;
912	errdefer request.deinit();
913	try request.sendBodyComplete(body.buffered());
914
915	var response = try request.receiveHead(options.buffer);
916	if (response.head.status != .ok) return error.ProtocolError;
917	const decompress_buffer = try arena.alloc(u8, response.head.content_encoding.minBufferCapacity());
918	it.reader = response.readerDecompressing(options.buffer, &it.decompress, decompress_buffer);
919	}
920
921	pub const RefIterator = struct {
922	format: Oid.Format,
923	request: std.http.Client.Request,
924	reader: *Io.Reader,
925	decompress: std.http.Decompress,
926
927	pub const Ref = struct {
928	oid: Oid,
929	name: []const u8,
930	symref_target: ?[]const u8,
931	peeled: ?Oid,
932	};
933
934	pub fn deinit(iterator: *RefIterator) void {
935	iterator.request.deinit();
936	iterator.* = undefined;
937	}
938
939	pub fn next(it: *RefIterator) !?Ref {
940	switch (try Packet.read(it.reader)) {
941	.flush => return null,
942	.data => |data| {
943	const ref_data = Packet.normalizeText(data);
944	const oid_sep_pos = mem.findScalar(u8, ref_data, ' ') orelse return error.InvalidRefPacket;
945	const oid = Oid.parse(it.format, data[0..oid_sep_pos]) catch return error.InvalidRefPacket;
946
947	const name_sep_pos = mem.findScalarPos(u8, ref_data, oid_sep_pos + 1, ' ') orelse ref_data.len;
948	const name = ref_data[oid_sep_pos + 1 .. name_sep_pos];
949
950	var symref_target: ?[]const u8 = null;
951	var peeled: ?Oid = null;
952	var last_sep_pos = name_sep_pos;
953	while (last_sep_pos < ref_data.len) {
954	const next_sep_pos = mem.findScalarPos(u8, ref_data, last_sep_pos + 1, ' ') orelse ref_data.len;
955	const attribute = ref_data[last_sep_pos + 1 .. next_sep_pos];
956	if (mem.startsWith(u8, attribute, "symref-target:")) {
957	symref_target = attribute["symref-target:".len..];
958	} else if (mem.startsWith(u8, attribute, "peeled:")) {
959	peeled = Oid.parse(it.format, attribute["peeled:".len..]) catch return error.InvalidRefPacket;
960	}
961	last_sep_pos = next_sep_pos;
962	}
963
964	return .{ .oid = oid, .name = name, .symref_target = symref_target, .peeled = peeled };
965	},
966	else => return error.UnexpectedPacket,
967	}
968	}
969	};
970
971	/// Fetches the given refs from the server. A shallow fetch (depth 1) is
972	/// performed if the server supports it.
973	pub fn fetch(
974	session: Session,
975	fs: *FetchStream,
976	wants: []const []const u8,
977	/// Asserted to be at least `Packet.max_data_length`.
978	response_buffer: []u8,
979	) !void {
980	const arena = session.arena;
981	assert(response_buffer.len >= Packet.max_data_length);
982	var upload_pack_uri = session.location.uri;
983	{
984	const session_uri_path = try std.fmt.allocPrint(arena, "{f}", .{
985	std.fmt.alt(session.location.uri.path, .formatPath),
986	});
987	upload_pack_uri.path = .{ .percent_encoded = try std.fs.path.resolvePosix(arena, &.{ "/", session_uri_path, "git-upload-pack" }) };
988	}
989	upload_pack_uri.query = null;
990	upload_pack_uri.fragment = null;
991
992	var body: Io.Writer = .fixed(response_buffer);
993	try Packet.write(.{ .data = "command=fetch\n" }, &body);
994	if (session.supports_agent) {
995	try Packet.write(.{ .data = agent_capability }, &body);
996	}
997	{
998	const object_format_packet = try std.fmt.allocPrint(arena, "object-format={s}\n", .{@tagName(session.object_format)});
999	try Packet.write(.{ .data = object_format_packet }, &body);
1000	}
1001	try Packet.write(.delimiter, &body);
1002	// Our packfile parser supports the OFS_DELTA object type
1003	try Packet.write(.{ .data = "ofs-delta\n" }, &body);
1004	// We do not currently convey server progress information to the user
1005	try Packet.write(.{ .data = "no-progress\n" }, &body);
1006	if (session.supports_shallow) {
1007	try Packet.write(.{ .data = "deepen 1\n" }, &body);
1008	}
1009	for (wants) |want| {
1010	var buf: [Packet.max_data_length]u8 = undefined;
1011	const arg = std.mem.print(&buf, "want {s}\n", .{want}) catch unreachable;
1012	try Packet.write(.{ .data = arg }, &body);
1013	}
1014	try Packet.write(.{ .data = "done\n" }, &body);
1015	try Packet.write(.flush, &body);
1016
1017	fs.* = .{
1018	.request = try session.transport.request(.POST, upload_pack_uri, .{
1019	.redirect_behavior = .not_allowed,
1020	.extra_headers = &.{
1021	.{ .name = "Content-Type", .value = "application/x-git-upload-pack-request" },
1022	.{ .name = "Git-Protocol", .value = "version=2" },
1023	},
1024	}),
1025	.input = undefined,
1026	.reader = undefined,
1027	.remaining_len = undefined,
1028	.decompress = undefined,
1029	};
1030	const request = &fs.request;
1031	errdefer request.deinit();
1032
1033	try request.sendBodyComplete(body.buffered());
1034
1035	var response = try request.receiveHead(&.{});
1036	if (response.head.status != .ok) return error.ProtocolError;
1037
1038	const decompress_buffer = try arena.alloc(u8, response.head.content_encoding.minBufferCapacity());
1039	const reader = response.readerDecompressing(response_buffer, &fs.decompress, decompress_buffer);
1040	// We are not interested in any of the sections of the returned fetch
1041	// data other than the packfile section, since we aren't doing anything
1042	// complex like ref negotiation (this is a fresh clone).
1043	var state: enum { section_start, section_content } = .section_start;
1044	while (true) {
1045	const packet = try Packet.read(reader);
1046	switch (state) {
1047	.section_start => switch (packet) {
1048	.data => |data| if (mem.eql(u8, Packet.normalizeText(data), "packfile")) {
1049	fs.input = reader;
1050	fs.reader = .{
1051	.buffer = &.{},
1052	.vtable = &.{ .stream = FetchStream.stream },
1053	.seek = 0,
1054	.end = 0,
1055	};
1056	fs.remaining_len = 0;
1057	return;
1058	} else {
1059	state = .section_content;
1060	},
1061	else => return error.UnexpectedPacket,
1062	},
1063	.section_content => switch (packet) {
1064	.delimiter => state = .section_start,
1065	.data => {},
1066	else => return error.UnexpectedPacket,
1067	},
1068	}
1069	}
1070	}
1071
1072	pub const FetchStream = struct {
1073	request: std.http.Client.Request,
1074	input: *Io.Reader,
1075	reader: Io.Reader,
1076	err: ?Error = null,
1077	remaining_len: usize,
1078	decompress: std.http.Decompress,
1079
1080	pub fn deinit(fs: *FetchStream) void {
1081	fs.request.deinit();
1082	}
1083
1084	pub const Error = error{
1085	InvalidPacket,
1086	ProtocolError,
1087	UnexpectedPacket,
1088	WriteFailed,
1089	ReadFailed,
1090	EndOfStream,
1091	};
1092
1093	const StreamCode = enum(u8) {
1094	pack_data = 1,
1095	progress = 2,
1096	fatal_error = 3,
1097	_,
1098	};
1099
1100	pub fn stream(r: *Io.Reader, w: *Io.Writer, limit: Io.Limit) Io.Reader.StreamError!usize {
1101	const fs: *FetchStream = @alignCast(@fieldParentPtr("reader", r));
1102	const input = fs.input;
1103	if (fs.remaining_len == 0) {
1104	while (true) {
1105	switch (Packet.peek(input) catch |err| {
1106	fs.err = err;
1107	return error.ReadFailed;
1108	}) {
1109	.flush => return error.EndOfStream,
1110	.data => |data| switch (@as(StreamCode, @fromBackingInt(@intCast(data[0])))) {
1111	.pack_data => {
1112	input.toss(1);
1113	fs.remaining_len = data.len - 1;
1114	break;
1115	},
1116	.fatal_error => {
1117	fs.err = error.ProtocolError;
1118	return error.ReadFailed;
1119	},
1120	else => {
1121	input.toss(data.len);
1122	},
1123	},
1124	else => {
1125	fs.err = error.UnexpectedPacket;
1126	return error.ReadFailed;
1127	},
1128	}
1129	}
1130	}
1131	const buf = limit.slice(try w.writableSliceGreedy(1));
1132	const n = @min(buf.len, fs.remaining_len);
1133	try input.readSliceAll(buf[0..n]);
1134	w.advance(n);
1135	fs.remaining_len -= n;
1136	return n;
1137	}
1138	};
1139	};
1140
1141	const PackHeader = struct {
1142	total_objects: u32,
1143
1144	const signature = "PACK";
1145	const supported_version = 2;
1146
1147	fn read(reader: *Io.Reader) !PackHeader {
1148	const actual_signature = reader.take(4) catch |e| switch (e) {
1149	error.EndOfStream => return error.InvalidHeader,
1150	else => |other| return other,
1151	};
1152	if (!mem.eql(u8, actual_signature, signature)) return error.InvalidHeader;
1153	const version = reader.takeInt(u32, .big) catch |e| switch (e) {
1154	error.EndOfStream => return error.InvalidHeader,
1155	else => |other| return other,
1156	};
1157	if (version != supported_version) return error.UnsupportedVersion;
1158	const total_objects = reader.takeInt(u32, .big) catch |e| switch (e) {
1159	error.EndOfStream => return error.InvalidHeader,
1160	else => |other| return other,
1161	};
1162	return .{ .total_objects = total_objects };
1163	}
1164	};
1165
1166	const EntryHeader = union(Type) {
1167	commit: Undeltified,
1168	tree: Undeltified,
1169	blob: Undeltified,
1170	tag: Undeltified,
1171	ofs_delta: OfsDelta,
1172	ref_delta: RefDelta,
1173
1174	const Type = enum(u3) {
1175	commit = 1,
1176	tree = 2,
1177	blob = 3,
1178	tag = 4,
1179	ofs_delta = 6,
1180	ref_delta = 7,
1181	};
1182
1183	const Undeltified = struct {
1184	uncompressed_length: u64,
1185	};
1186
1187	const OfsDelta = struct {
1188	offset: u64,
1189	uncompressed_length: u64,
1190	};
1191
1192	const RefDelta = struct {
1193	base_object: Oid,
1194	uncompressed_length: u64,
1195	};
1196
1197	fn objectType(header: EntryHeader) Object.Type {
1198	return switch (header) {
1199	inline .commit, .tree, .blob, .tag => |_, tag| @field(Object.Type, @tagName(tag)),
1200	else => unreachable,
1201	};
1202	}
1203
1204	fn uncompressedLength(header: EntryHeader) u64 {
1205	return switch (header) {
1206	inline else => |entry| entry.uncompressed_length,
1207	};
1208	}
1209
1210	fn read(format: Oid.Format, reader: *Io.Reader) !EntryHeader {
1211	const InitialByte = packed struct { len: u4, type: u3, has_next: bool };
1212	const initial: InitialByte = @bitCast(reader.takeByte() catch |e| switch (e) {
1213	error.EndOfStream => return error.InvalidFormat,
1214	else => |other| return other,
1215	});
1216	const rest_len = if (initial.has_next) try reader.takeLeb128(u64) else 0;
1217	var uncompressed_length: u64 = initial.len;
1218	uncompressed_length |= std.math.shlExact(u64, rest_len, 4) catch return error.InvalidFormat;
1219	const @"type" = std.enums.fromInt(EntryHeader.Type, initial.type) orelse return error.InvalidFormat;
1220	return switch (@"type") {
1221	inline .commit, .tree, .blob, .tag => |tag| @unionInit(EntryHeader, @tagName(tag), .{
1222	.uncompressed_length = uncompressed_length,
1223	}),
1224	.ofs_delta => .{ .ofs_delta = .{
1225	.offset = try readOffsetVarInt(reader),
1226	.uncompressed_length = uncompressed_length,
1227	} },
1228	.ref_delta => .{ .ref_delta = .{
1229	.base_object = Oid.readBytes(format, reader) catch |e| switch (e) {
1230	error.EndOfStream => return error.InvalidFormat,
1231	else => |other| return other,
1232	},
1233	.uncompressed_length = uncompressed_length,
1234	} },
1235	};
1236	}
1237	};
1238
1239	fn readOffsetVarInt(r: *Io.Reader) !u64 {
1240	const Byte = packed struct { value: u7, has_next: bool };
1241	var b: Byte = @bitCast(try r.takeByte());
1242	var value: u64 = b.value;
1243	while (b.has_next) {
1244	b = @bitCast(try r.takeByte());
1245	value = std.math.shlExact(u64, value + 1, 7) catch return error.InvalidFormat;
1246	value |= b.value;
1247	}
1248	return value;
1249	}
1250
1251	const IndexHeader = struct {
1252	fan_out_table: [256]u32,
1253
1254	const signature = "\xFFtOc";
1255	const supported_version = 2;
1256	const size = 4 + 4 + @sizeOf([256]u32);
1257
1258	fn read(index_header: *IndexHeader, reader: *Io.Reader) !void {
1259	const sig = try reader.take(4);
1260	if (!mem.eql(u8, sig, signature)) return error.InvalidHeader;
1261	const version = try reader.takeInt(u32, .big);
1262	if (version != supported_version) return error.UnsupportedVersion;
1263	try reader.readSliceEndian(u32, &index_header.fan_out_table, .big);
1264	}
1265	};
1266
1267	const IndexEntry = struct {
1268	offset: u64,
1269	crc32: u32,
1270	};
1271
1272	/// Writes out a version 2 index for the given packfile, as documented in
1273	/// [pack-format](https://git-scm.com/docs/pack-format).
1274	pub fn indexPack(
1275	allocator: Allocator,
1276	format: Oid.Format,
1277	pack: *Io.File.Reader,
1278	index_writer: *Io.File.Writer,
1279	) !void {
1280	try pack.seekTo(0);
1281
1282	var index_entries: std.AutoHashMapUnmanaged(Oid, IndexEntry) = .empty;
1283	defer index_entries.deinit(allocator);
1284	var pending_deltas: std.ArrayList(IndexEntry) = .empty;
1285	defer pending_deltas.deinit(allocator);
1286
1287	const pack_checksum = try indexPackFirstPass(allocator, format, pack, &index_entries, &pending_deltas);
1288
1289	var cache: ObjectCache = .{};
1290	defer cache.deinit(allocator);
1291	var remaining_deltas = pending_deltas.items.len;
1292	while (remaining_deltas > 0) {
1293	var i: usize = remaining_deltas;
1294	while (i > 0) {
1295	i -= 1;
1296	const delta = pending_deltas.items[i];
1297	if (try indexPackHashDelta(allocator, format, pack, delta, index_entries, &cache)) |oid| {
1298	try index_entries.put(allocator, oid, delta);
1299	_ = pending_deltas.swapRemove(i);
1300	}
1301	}
1302	if (pending_deltas.items.len == remaining_deltas) return error.IncompletePack;
1303	remaining_deltas = pending_deltas.items.len;
1304	}
1305
1306	var oids: std.ArrayList(Oid) = .empty;
1307	defer oids.deinit(allocator);
1308	try oids.ensureTotalCapacityPrecise(allocator, index_entries.count());
1309	var index_entries_iter = index_entries.iterator();
1310	while (index_entries_iter.next()) |entry| {
1311	oids.appendAssumeCapacity(entry.key_ptr.*);
1312	}
1313	mem.sortUnstable(Oid, oids.items, {}, struct {
1314	fn lessThan(_: void, o1: Oid, o2: Oid) bool {
1315	return mem.lessThan(u8, o1.slice(), o2.slice());
1316	}
1317	}.lessThan);
1318
1319	var fan_out_table: [256]u32 = undefined;
1320	var count: u32 = 0;
1321	var fan_out_index: u8 = 0;
1322	for (oids.items) |oid| {
1323	const key = oid.slice()[0];
1324	if (key > fan_out_index) {
1325	@memset(fan_out_table[fan_out_index..key], count);
1326	fan_out_index = key;
1327	}
1328	count += 1;
1329	}
1330	@memset(fan_out_table[fan_out_index..], count);
1331
1332	var index_hashed_writer = Io.Writer.hashed(&index_writer.interface, Oid.Hasher.init(format), &.{});
1333	const writer = &index_hashed_writer.writer;
1334	try writer.writeAll(IndexHeader.signature);
1335	try writer.writeInt(u32, IndexHeader.supported_version, .big);
1336	for (fan_out_table) |fan_out_entry| {
1337	try writer.writeInt(u32, fan_out_entry, .big);
1338	}
1339
1340	for (oids.items) |oid| {
1341	try writer.writeAll(oid.slice());
1342	}
1343
1344	for (oids.items) |oid| {
1345	try writer.writeInt(u32, index_entries.get(oid).?.crc32, .big);
1346	}
1347
1348	var big_offsets: std.ArrayList(u64) = .empty;
1349	defer big_offsets.deinit(allocator);
1350	for (oids.items) |oid| {
1351	const offset = index_entries.get(oid).?.offset;
1352	if (offset <= std.math.maxInt(u31)) {
1353	try writer.writeInt(u32, @intCast(offset), .big);
1354	} else {
1355	const index = big_offsets.items.len;
1356	try big_offsets.append(allocator, offset);
1357	try writer.writeInt(u32, @as(u32, @intCast(index)) | (1 << 31), .big);
1358	}
1359	}
1360	for (big_offsets.items) |offset| {
1361	try writer.writeInt(u64, offset, .big);
1362	}
1363
1364	try writer.writeAll(pack_checksum.slice());
1365	const index_checksum = index_hashed_writer.hasher.finalResult();
1366	try index_writer.interface.writeAll(index_checksum.slice());
1367	try index_writer.end();
1368	}
1369
1370	/// Performs the first pass over the packfile data for index construction.
1371	/// This will index all non-delta objects, queue delta objects for further
1372	/// processing, and return the pack checksum (which is part of the index
1373	/// format).
1374	fn indexPackFirstPass(
1375	allocator: Allocator,
1376	format: Oid.Format,
1377	pack: *Io.File.Reader,
1378	index_entries: *std.AutoHashMapUnmanaged(Oid, IndexEntry),
1379	pending_deltas: *std.ArrayList(IndexEntry),
1380	) !Oid {
1381	var flate_buffer: [std.compress.flate.max_window_len]u8 = undefined;
1382	var pack_buffer: [2048]u8 = undefined; // Reasonably large buffer for file system.
1383	var pack_hashed = pack.interface.hashed(Oid.Hasher.init(format), &pack_buffer);
1384
1385	const pack_header = try PackHeader.read(&pack_hashed.reader);
1386
1387	for (0..pack_header.total_objects) |_| {
1388	const entry_offset = pack.logicalPos() - pack_hashed.reader.bufferedLen();
1389	const entry_header = try EntryHeader.read(format, &pack_hashed.reader);
1390	switch (entry_header) {
1391	.commit, .tree, .blob, .tag => |object| {
1392	var entry_decompress: std.compress.flate.Decompress = .init(&pack_hashed.reader, .zlib, &.{});
1393	var oid_hasher: Oid.Hashing = .init(format, &flate_buffer);
1394	const oid_hasher_w = oid_hasher.writer();
1395	// The object header is not included in the pack data but is
1396	// part of the object's ID
1397	try oid_hasher_w.print("{t} {d}\x00", .{ entry_header, object.uncompressed_length });
1398	const n = try entry_decompress.reader.streamRemaining(oid_hasher_w);
1399	if (n != object.uncompressed_length) return error.InvalidObject;
1400	const oid = oid_hasher.final();
1401	if (!skip_checksums) @compileError("TODO");
1402	try index_entries.put(allocator, oid, .{
1403	.offset = entry_offset,
1404	.crc32 = 0,
1405	});
1406	},
1407	inline .ofs_delta, .ref_delta => |delta| {
1408	var entry_decompress: std.compress.flate.Decompress = .init(&pack_hashed.reader, .zlib, &flate_buffer);
1409	const n = try entry_decompress.reader.discardRemaining();
1410	if (n != delta.uncompressed_length) return error.InvalidObject;
1411	if (!skip_checksums) @compileError("TODO");
1412	try pending_deltas.append(allocator, .{
1413	.offset = entry_offset,
1414	.crc32 = 0,
1415	});
1416	},
1417	}
1418	}
1419
1420	if (!skip_checksums) @compileError("TODO");
1421	return pack_hashed.hasher.finalResult();
1422	}
1423
1424	/// Attempts to determine the final object ID of the given deltified object.
1425	/// May return null if this is not yet possible (if the delta is a ref-based
1426	/// delta and we do not yet know the offset of the base object).
1427	fn indexPackHashDelta(
1428	allocator: Allocator,
1429	format: Oid.Format,
1430	pack: *Io.File.Reader,
1431	delta: IndexEntry,
1432	index_entries: std.AutoHashMapUnmanaged(Oid, IndexEntry),
1433	cache: *ObjectCache,
1434	) !?Oid {
1435	// Figure out the chain of deltas to resolve
1436	var base_offset = delta.offset;
1437	var base_header: EntryHeader = undefined;
1438	var delta_offsets: std.ArrayList(u64) = .empty;
1439	defer delta_offsets.deinit(allocator);
1440	const base_object = while (true) {
1441	if (cache.get(base_offset)) |base_object| break base_object;
1442
1443	try pack.seekTo(base_offset);
1444	base_header = try EntryHeader.read(format, &pack.interface);
1445	switch (base_header) {
1446	.ofs_delta => |ofs_delta| {
1447	try delta_offsets.append(allocator, base_offset);
1448	base_offset = std.math.sub(u64, base_offset, ofs_delta.offset) catch return error.InvalidObject;
1449	},
1450	.ref_delta => |ref_delta| {
1451	try delta_offsets.append(allocator, base_offset);
1452	base_offset = (index_entries.get(ref_delta.base_object) orelse return null).offset;
1453	},
1454	else => {
1455	const base_data = try readObjectRaw(allocator, &pack.interface, base_header.uncompressedLength());
1456	errdefer allocator.free(base_data);
1457	const base_object: Object = .{ .type = base_header.objectType(), .data = base_data };
1458	try cache.put(allocator, base_offset, base_object);
1459	break base_object;
1460	},
1461	}
1462	};
1463
1464	const base_data = try resolveDeltaChain(allocator, format, pack, base_object, delta_offsets.items, cache);
1465
1466	var entry_hasher_buffer: [64]u8 = undefined;
1467	var entry_hasher: Oid.Hashing = .init(format, &entry_hasher_buffer);
1468	const entry_hasher_w = entry_hasher.writer();
1469	// Writes to hashers cannot fail.
1470	entry_hasher_w.print("{t} {d}\x00", .{ base_object.type, base_data.len }) catch unreachable;
1471	entry_hasher_w.writeAll(base_data) catch unreachable;
1472	return entry_hasher.final();
1473	}
1474
1475	/// Resolves a chain of deltas, returning the final base object data. `pack` is
1476	/// assumed to be looking at the start of the object data for the base object of
1477	/// the chain, and will then apply the deltas in `delta_offsets` in reverse order
1478	/// to obtain the final object.
1479	fn resolveDeltaChain(
1480	allocator: Allocator,
1481	format: Oid.Format,
1482	pack: *Io.File.Reader,
1483	base_object: Object,
1484	delta_offsets: []const u64,
1485	cache: *ObjectCache,
1486	) ![]const u8 {
1487	var base_data = base_object.data;
1488	var i: usize = delta_offsets.len;
1489	while (i > 0) {
1490	i -= 1;
1491
1492	const delta_offset = delta_offsets[i];
1493	try pack.seekTo(delta_offset);
1494	const delta_header = try EntryHeader.read(format, &pack.interface);
1495	const delta_data = try readObjectRaw(allocator, &pack.interface, delta_header.uncompressedLength());
1496	defer allocator.free(delta_data);
1497	var delta_reader: Io.Reader = .fixed(delta_data);
1498	_ = try delta_reader.takeLeb128(u64); // base object size
1499	const expanded_size = try delta_reader.takeLeb128(u64);
1500
1501	const expanded_alloc_size = std.math.cast(usize, expanded_size) orelse return error.ObjectTooLarge;
1502	const expanded_data = try allocator.alloc(u8, expanded_alloc_size);
1503	errdefer allocator.free(expanded_data);
1504	var expanded_delta_stream: Io.Writer = .fixed(expanded_data);
1505	try expandDelta(base_data, &delta_reader, &expanded_delta_stream);
1506	if (expanded_delta_stream.end != expanded_size) return error.InvalidObject;
1507
1508	try cache.put(allocator, delta_offset, .{ .type = base_object.type, .data = expanded_data });
1509	base_data = expanded_data;
1510	}
1511	return base_data;
1512	}
1513
1514	/// Reads the complete contents of an object from `reader`. This function may
1515	/// read more bytes than required from `reader`, so the reader position after
1516	/// returning is not reliable.
1517	fn readObjectRaw(allocator: Allocator, reader: *Io.Reader, size: u64) ![]u8 {
1518	const alloc_size = std.math.cast(usize, size) orelse return error.ObjectTooLarge;
1519	var aw: Io.Writer.Allocating = .init(allocator);
1520	try aw.ensureTotalCapacity(alloc_size + std.compress.flate.max_window_len);
1521	defer aw.deinit();
1522	var decompress: std.compress.flate.Decompress = .init(reader, .zlib, &.{});
1523	try decompress.reader.streamExact(&aw.writer, alloc_size);
1524	return aw.toOwnedSlice();
1525	}
1526
1527	/// Expands delta data from `delta_reader` to `writer`.
1528	///
1529	/// The format of the delta data is documented in
1530	/// [pack-format](https://git-scm.com/docs/pack-format).
1531	fn expandDelta(base_object: []const u8, delta_reader: *Io.Reader, writer: *Io.Writer) !void {
1532	while (true) {
1533	const inst: packed struct { value: u7, copy: bool } = @bitCast(delta_reader.takeByte() catch |e| switch (e) {
1534	error.EndOfStream => return,
1535	else => |other| return other,
1536	});
1537	if (inst.copy) {
1538	const available: packed struct {
1539	offset1: bool,
1540	offset2: bool,
1541	offset3: bool,
1542	offset4: bool,
1543	size1: bool,
1544	size2: bool,
1545	size3: bool,
1546	} = @bitCast(inst.value);
1547	const offset_parts: packed struct { offset1: u8, offset2: u8, offset3: u8, offset4: u8 } = .{
1548	.offset1 = if (available.offset1) try delta_reader.takeByte() else 0,
1549	.offset2 = if (available.offset2) try delta_reader.takeByte() else 0,
1550	.offset3 = if (available.offset3) try delta_reader.takeByte() else 0,
1551	.offset4 = if (available.offset4) try delta_reader.takeByte() else 0,
1552	};
1553	const base_offset: u32 = @bitCast(offset_parts);
1554	const size_parts: packed struct { size1: u8, size2: u8, size3: u8 } = .{
1555	.size1 = if (available.size1) try delta_reader.takeByte() else 0,
1556	.size2 = if (available.size2) try delta_reader.takeByte() else 0,
1557	.size3 = if (available.size3) try delta_reader.takeByte() else 0,
1558	};
1559	var size: u24 = @bitCast(size_parts);
1560	if (size == 0) size = 0x10000;
1561	try writer.writeAll(base_object[base_offset..][0..size]);
1562	} else if (inst.value != 0) {
1563	try delta_reader.streamExact(writer, inst.value);
1564	} else {
1565	return error.InvalidDeltaInstruction;
1566	}
1567	}
1568	}
1569
1570	/// Runs the packfile indexing and checkout test.
1571	///
1572	/// The two testrepo repositories under testdata contain identical commit
1573	/// histories and contents.
1574	///
1575	/// To verify the contents of the packfiles using Git alone, run the
1576	/// following commands in an empty directory:
1577	///
1578	/// 1. `git init --object-format=(sha1|sha256)`
1579	/// 2. `git unpack-objects <path/to/testrepo.pack`
1580	/// 3. `git fsck` - will print one "dangling commit":
1581	/// - SHA-1: `dd582c0720819ab7130b103635bd7271b9fd4feb`
1582	/// - SHA-256: `7f444a92bd4572ee4a28b2c63059924a9ca1829138553ef3e7c41ee159afae7a`
1583	/// 4. `git checkout $commit`
1584	fn runRepositoryTest(io: Io, comptime format: Oid.Format, head_commit: []const u8) !void {
1585	const testrepo_pack = @embedFile("git/testdata/testrepo-" ++ @tagName(format) ++ ".pack");
1586
1587	var git_dir = testing.tmpDir(.{});
1588	defer git_dir.cleanup();
1589	var pack_file = try git_dir.dir.createFile(io, "testrepo.pack", .{ .read = true });
1590	defer pack_file.close(io);
1591	try pack_file.writeStreamingAll(io, testrepo_pack);
1592
1593	var pack_file_buffer: [2000]u8 = undefined;
1594	var pack_file_reader = pack_file.reader(io, &pack_file_buffer);
1595
1596	var index_file = try git_dir.dir.createFile(io, "testrepo.idx", .{ .read = true });
1597	defer index_file.close(io);
1598	var index_file_buffer: [2000]u8 = undefined;
1599	var index_file_writer = index_file.writer(io, &index_file_buffer);
1600	try indexPack(testing.allocator, format, &pack_file_reader, &index_file_writer);
1601
1602	// Arbitrary size limit on files read while checking the repository contents
1603	// (all files in the test repo are known to be smaller than this)
1604	const max_file_size = 8192;
1605
1606	if (!skip_checksums) {
1607	const index_file_data = try git_dir.dir.readFileAlloc(io, "testrepo.idx", testing.allocator, .limited(max_file_size));
1608	defer testing.allocator.free(index_file_data);
1609	// testrepo.idx is generated by Git. The index created by this file should
1610	// match it exactly. Running `git verify-pack -v testrepo.pack` can verify
1611	// this.
1612	const testrepo_idx = @embedFile("git/testdata/testrepo-" ++ @tagName(format) ++ ".idx");
1613	try testing.expectEqualSlices(u8, testrepo_idx, index_file_data);
1614	}
1615
1616	var index_file_reader = index_file.reader(io, &index_file_buffer);
1617	var repository: Repository = undefined;
1618	try repository.init(testing.allocator, format, &pack_file_reader, &index_file_reader);
1619	defer repository.deinit();
1620
1621	var worktree = testing.tmpDir(.{ .iterate = true });
1622	defer worktree.cleanup();
1623
1624	const commit_id = try Oid.parse(format, head_commit);
1625
1626	var diagnostics: Diagnostics = .{ .allocator = testing.allocator };
1627	defer diagnostics.deinit();
1628	try repository.checkout(io, worktree.dir, commit_id, &diagnostics);
1629	try testing.expect(diagnostics.errors.items.len == 0);
1630
1631	const expected_files: []const []const u8 = &.{
1632	"dir/file",
1633	"dir/subdir/file",
1634	"dir/subdir/file2",
1635	"dir2/file",
1636	"dir3/file",
1637	"dir3/file2",
1638	"file",
1639	"file2",
1640	"file3",
1641	"file4",
1642	"file5",
1643	"file6",
1644	"file7",
1645	"file8",
1646	"file9",
1647	};
1648	var actual_files: std.ArrayList([]u8) = .empty;
1649	defer actual_files.deinit(testing.allocator);
1650	defer for (actual_files.items) |file| testing.allocator.free(file);
1651	var walker = try worktree.dir.walk(testing.allocator);
1652	defer walker.deinit();
1653	while (try walker.next(io)) |entry| {
1654	if (entry.kind != .file) continue;
1655	const path = try testing.allocator.dupe(u8, entry.path);
1656	errdefer testing.allocator.free(path);
1657	mem.replaceScalar(u8, path, std.fs.path.sep, '/');
1658	try actual_files.append(testing.allocator, path);
1659	}
1660	mem.sortUnstable([]u8, actual_files.items, {}, struct {
1661	fn lessThan(_: void, a: []u8, b: []u8) bool {
1662	return mem.lessThan(u8, a, b);
1663	}
1664	}.lessThan);
1665	try testing.expectEqualDeep(expected_files, actual_files.items);
1666
1667	const expected_file_contents =
1668	\\revision 1
1669	\\revision 2
1670	\\revision 4
1671	\\revision 5
1672	\\revision 7
1673	\\revision 8
1674	\\revision 9
1675	\\revision 10
1676	\\revision 12
1677	\\revision 13
1678	\\revision 14
1679	\\revision 18
1680	\\revision 19
1681	\\
1682	;
1683	const actual_file_contents = try worktree.dir.readFileAlloc(io, "file", testing.allocator, .limited(max_file_size));
1684	defer testing.allocator.free(actual_file_contents);
1685	try testing.expectEqualStrings(expected_file_contents, actual_file_contents);
1686	}
1687
1688	/// Checksum calculation is useful for troubleshooting and debugging, but it's
1689	/// redundant since the package manager already does content hashing at the
1690	/// end. Let's save time by not doing that work, but, I left a cookie crumb
1691	/// trail here if you want to restore the functionality for tinkering purposes.
1692	const skip_checksums = true;
1693
1694	test "SHA-1 packfile indexing and checkout" {
1695	try runRepositoryTest(std.testing.io, .sha1, "dd582c0720819ab7130b103635bd7271b9fd4feb");
1696	}
1697
1698	test "SHA-256 packfile indexing and checkout" {
1699	try runRepositoryTest(std.testing.io, .sha256, "7f444a92bd4572ee4a28b2c63059924a9ca1829138553ef3e7c41ee159afae7a");
1700	}
1701
1702	/// Checks out a commit of a packfile. Intended for experimenting with and
1703	/// benchmarking possible optimizations to the indexing and checkout behavior.
1704	pub fn main() !void {
1705	const allocator = std.heap.smp_allocator;
1706
1707	var threaded: Io.Threaded = .init(allocator, .{});
1708	defer threaded.deinit();
1709	const io = threaded.io();
1710
1711	const args = try std.process.argsAlloc(allocator);
1712	defer std.process.argsFree(allocator, args);
1713	if (args.len != 5) {
1714	return error.InvalidArguments; // Arguments: format packfile commit worktree
1715	}
1716
1717	const format = std.meta.stringToEnum(Oid.Format, args[1]) orelse return error.InvalidFormat;
1718
1719	var pack_file = try Io.Dir.cwd().openFile(io, args[2], .{});
1720	defer pack_file.close(io);
1721	var pack_file_buffer: [4096]u8 = undefined;
1722	var pack_file_reader = pack_file.reader(io, &pack_file_buffer);
1723
1724	const commit = try Oid.parse(format, args[3]);
1725	var worktree = try Io.Dir.cwd().createDirPathOpen(io, args[4], .{});
1726	defer worktree.close(io);
1727
1728	var git_dir = try worktree.createDirPathOpen(io, ".git", .{});
1729	defer git_dir.close(io);
1730
1731	std.debug.print("Starting index...\n", .{});
1732	var index_file = try git_dir.createFile(io, "idx", .{ .read = true });
1733	defer index_file.close(io);
1734	var index_file_buffer: [4096]u8 = undefined;
1735	var index_file_writer = index_file.writer(io, &index_file_buffer);
1736	try indexPack(allocator, format, &pack_file_reader, &index_file_writer);
1737
1738	std.debug.print("Starting checkout...\n", .{});
1739	var index_file_reader = index_file.reader(io, &index_file_buffer);
1740	var repository: Repository = undefined;
1741	try repository.init(allocator, format, &pack_file_reader, &index_file_reader);
1742	defer repository.deinit();
1743	var diagnostics: Diagnostics = .{ .allocator = allocator };
1744	defer diagnostics.deinit();
1745	try repository.checkout(io, worktree, commit, &diagnostics);
1746
1747	for (diagnostics.errors.items) |err| {
1748	std.debug.print("Diagnostic: {}\n", .{err});
1749	}
1750	}