Meg's Mirrors

zig

1	//! Tracks metadata of file inputs associated with Zig compiler and build
2	//! system artifacts in order to determine whether those artifacts must be
3	//! produced again, or may be retrieved from the cache directory on the
4	//! filesystem.
5	const Cache = @This();
6	const builtin = @import("builtin");
7
8	const std = @import("std");
9	const Io = std.Io;
10	const crypto = std.crypto;
11	const assert = std.debug.assert;
12	const testing = std.testing;
13	const mem = std.mem;
14	const fmt = std.fmt;
15	const Allocator = std.mem.Allocator;
16	const log = std.log.scoped(.cache);
17
18	gpa: Allocator,
19	io: Io,
20	manifest_dir: Io.Dir,
21	hash: HashHelper = .{},
22	/// This value is accessed from multiple threads, protected by mutex.
23	recent_problematic_timestamp: Io.Timestamp = .zero,
24	mutex: Io.Mutex = .init,
25
26	/// A set of strings such as the zig library directory or project source root, which
27	/// are stripped from the file paths before putting into the cache. They
28	/// are replaced with single-character indicators. This is not to save
29	/// space but to eliminate absolute file paths. This improves portability
30	/// and usefulness of the cache for advanced use cases.
31	prefixes_buffer: [5]Directory = undefined,
32	prefixes_len: usize = 0,
33	/// Used to identify prefixes. References external memory.
34	cwd: []const u8,
35
36	pub const Path = @import("Cache/Path.zig");
37	pub const Directory = @import("Cache/Directory.zig");
38	pub const DepTokenizer = @import("Cache/DepTokenizer.zig");
39
40	pub fn addPrefix(cache: *Cache, directory: Directory) void {
41	cache.prefixes_buffer[cache.prefixes_len] = directory;
42	cache.prefixes_len += 1;
43	}
44
45	/// Be sure to call `Manifest.deinit` after successful initialization.
46	pub fn obtain(cache: *Cache) Manifest {
47	return .{
48	.cache = cache,
49	.hash = cache.hash,
50	.manifest_file = null,
51	.manifest_dirty = false,
52	.hex_digest = undefined,
53	};
54	}
55
56	pub fn prefixes(cache: *const Cache) []const Directory {
57	return cache.prefixes_buffer[0..cache.prefixes_len];
58	}
59
60	pub const PrefixedPath = struct {
61	prefix: u8,
62	sub_path: []const u8,
63
64	fn eql(a: PrefixedPath, b: PrefixedPath) bool {
65	return a.prefix == b.prefix and std.mem.eql(u8, a.sub_path, b.sub_path);
66	}
67
68	fn hash(pp: PrefixedPath) u32 {
69	return @truncate(std.hash.Wyhash.hash(pp.prefix, pp.sub_path));
70	}
71	};
72
73	fn findPrefixPath(cache: *const Cache, path: Path) !PrefixedPath {
74	const gpa = cache.gpa;
75	const resolved_path = try std.fs.path.resolve(gpa, &.{
76	cache.cwd, path.root_dir.path orelse ".", path.subPathOrDot(),
77	});
78	errdefer gpa.free(resolved_path);
79	return findPrefixResolved(cache, resolved_path);
80	}
81
82	fn findPrefix(cache: *const Cache, file_path: []const u8) !PrefixedPath {
83	const gpa = cache.gpa;
84	const resolved_path = try std.fs.path.resolve(gpa, &.{file_path});
85	errdefer gpa.free(resolved_path);
86	return findPrefixResolved(cache, resolved_path);
87	}
88
89	/// Takes ownership of `resolved_path` on success.
90	fn findPrefixResolved(cache: *const Cache, resolved_path: []u8) !PrefixedPath {
91	const gpa = cache.gpa;
92	const cwd = cache.cwd;
93	for (cache.prefixes(), 0..) |prefix, i| {
94	const p = prefix.path orelse continue;
95	const sub_path = getPrefixSubpath(gpa, cwd, p, resolved_path) catch |err| switch (err) {
96	error.NotASubPath => continue,
97	else => |e| return e,
98	};
99	// Free the resolved path since we're not going to return it
100	gpa.free(resolved_path);
101	return .{
102	.prefix = @intCast(i),
103	.sub_path = sub_path,
104	};
105	}
106
107	return .{
108	.prefix = 0,
109	.sub_path = resolved_path,
110	};
111	}
112
113	fn getPrefixSubpath(gpa: Allocator, cwd: []const u8, prefix: []const u8, path: []u8) ![]u8 {
114	const relative = try std.fs.path.relative(gpa, cwd, null, prefix, path);
115	errdefer gpa.free(relative);
116	var component_iterator: std.fs.path.NativeComponentIterator = .init(relative);
117	if (component_iterator.root() != null) {
118	return error.NotASubPath;
119	}
120	const first_component = component_iterator.first();
121	if (first_component != null and std.mem.eql(u8, first_component.?.name, "..")) {
122	return error.NotASubPath;
123	}
124	return relative;
125	}
126
127	/// This is 128 bits - Even with 2^54 cache entries, the probably of a collision would be under 10^-6
128	pub const bin_digest_len = 16;
129	pub const hex_digest_len = bin_digest_len * 2;
130	pub const BinDigest = [bin_digest_len]u8;
131	pub const HexDigest = [hex_digest_len]u8;
132
133	/// This is currently just an arbitrary non-empty string that can't match another manifest line.
134	const manifest_header = "0";
135	pub const manifest_file_size_max = 100 * 1024 * 1024;
136
137	/// The type used for hashing file contents. Currently, this is SipHash128(1, 3), because it
138	/// provides enough collision resistance for the Manifest use cases, while being one of our
139	/// fastest options right now.
140	pub const Hasher = crypto.auth.siphash.SipHash128(1, 3);
141
142	/// Initial state with random bytes, that can be copied.
143	/// Refresh this with new random bytes when the manifest
144	/// format is modified in a non-backwards-compatible way.
145	pub const hasher_init: Hasher = Hasher.init(&.{
146	0x33, 0x52, 0xa2, 0x84,
147	0xcf, 0x17, 0x56, 0x57,
148	0x01, 0xbb, 0xcd, 0xe4,
149	0x77, 0xd6, 0xf0, 0x60,
150	});
151
152	pub const File = struct {
153	prefixed_path: PrefixedPath,
154	max_file_size: ?usize,
155	/// Populated if the user calls `addOpenedFile`.
156	/// The handle is not owned here.
157	handle: ?Io.File,
158	stat: Stat,
159	bin_digest: BinDigest,
160	contents: ?[]const u8,
161
162	pub const Stat = struct {
163	inode: Io.File.INode,
164	size: u64,
165	mtime: Io.Timestamp,
166
167	pub fn fromFs(fs_stat: Io.File.Stat) Stat {
168	return .{
169	.inode = fs_stat.inode,
170	.size = fs_stat.size,
171	.mtime = fs_stat.mtime,
172	};
173	}
174	};
175
176	pub fn deinit(self: *File, gpa: Allocator) void {
177	gpa.free(self.prefixed_path.sub_path);
178	if (self.contents) |contents| {
179	gpa.free(contents);
180	self.contents = null;
181	}
182	self.* = undefined;
183	}
184
185	pub fn updateMaxSize(file: *File, new_max_size: ?usize) void {
186	const new = new_max_size orelse return;
187	file.max_file_size = if (file.max_file_size) |old| @max(old, new) else new;
188	}
189
190	pub fn updateHandle(file: *File, new_handle: ?Io.File) void {
191	const handle = new_handle orelse return;
192	file.handle = handle;
193	}
194	};
195
196	pub const HashHelper = struct {
197	hasher: Hasher = hasher_init,
198
199	pub fn addBytes(hh: *HashHelper, bytes: []const u8) void {
200	hh.hasher.update(mem.asBytes(&bytes.len));
201	hh.hasher.update(bytes);
202	}
203
204	pub fn addBytesZ(hh: *HashHelper, bytes: [:0]const u8) void {
205	hh.hasher.update(mem.absorbSentinel(bytes));
206	}
207
208	pub fn addOptionalBytes(hh: *HashHelper, optional_bytes: ?[]const u8) void {
209	hh.add(optional_bytes != null);
210	hh.addBytes(optional_bytes orelse return);
211	}
212
213	pub fn addListOfBytes(hh: *HashHelper, list_of_bytes: []const []const u8) void {
214	hh.add(list_of_bytes.len);
215	for (list_of_bytes) |bytes| hh.addBytes(bytes);
216	}
217
218	pub fn addOptionalListOfBytes(hh: *HashHelper, optional_list_of_bytes: ?[]const []const u8) void {
219	hh.add(optional_list_of_bytes != null);
220	hh.addListOfBytes(optional_list_of_bytes orelse return);
221	}
222
223	/// Convert the input value into bytes and record it as a dependency of the process being cached.
224	pub fn add(hh: *HashHelper, x: anytype) void {
225	switch (@TypeOf(x)) {
226	std.SemanticVersion => {
227	hh.add(x.major);
228	hh.add(x.minor);
229	hh.add(x.patch);
230	},
231	std.Target.Os.TaggedVersionRange => {
232	switch (x) {
233	.hurd => |hurd| {
234	hh.add(hurd.range.min);
235	hh.add(hurd.range.max);
236	hh.add(hurd.glibc);
237	},
238	.linux => |linux| {
239	hh.add(linux.range.min);
240	hh.add(linux.range.max);
241	hh.add(linux.glibc);
242	hh.add(linux.android);
243	},
244	.windows => |windows| {
245	hh.add(windows.min);
246	hh.add(windows.max);
247	},
248	.semver => |semver| {
249	hh.add(semver.min);
250	hh.add(semver.max);
251	},
252	.none => {},
253	}
254	},
255	std.zig.BuildId => switch (x) {
256	.none, .fast, .uuid, .sha1, .md5 => hh.add(std.meta.activeTag(x)),
257	.hexstring => |hex_string| hh.addBytes(hex_string.toSlice()),
258	},
259	else => switch (@typeInfo(@TypeOf(x))) {
260	.bool, .int, .@"enum", .array => hh.addBytes(mem.asBytes(&x)),
261	else => @compileError("unable to hash type " ++ @typeName(@TypeOf(x))),
262	},
263	}
264	}
265
266	pub fn addOptional(hh: *HashHelper, optional: anytype) void {
267	hh.add(optional != null);
268	hh.add(optional orelse return);
269	}
270
271	/// Returns a hex encoded hash of the inputs, without modifying state.
272	pub fn peek(hh: HashHelper) [hex_digest_len]u8 {
273	var copy = hh;
274	return copy.final();
275	}
276
277	pub fn peekBin(hh: HashHelper) BinDigest {
278	var copy = hh;
279	var bin_digest: BinDigest = undefined;
280	copy.hasher.final(&bin_digest);
281	return bin_digest;
282	}
283
284	/// Returns a hex encoded hash of the inputs, mutating the state of the hasher.
285	pub fn final(hh: *HashHelper) HexDigest {
286	var bin_digest: BinDigest = undefined;
287	hh.hasher.final(&bin_digest);
288	return binToHex(bin_digest);
289	}
290
291	pub fn oneShot(bytes: []const u8) [hex_digest_len]u8 {
292	var hasher: Hasher = hasher_init;
293	hasher.update(bytes);
294	var bin_digest: BinDigest = undefined;
295	hasher.final(&bin_digest);
296	return binToHex(bin_digest);
297	}
298	};
299
300	pub fn binToHex(bin_digest: BinDigest) HexDigest {
301	var out_digest: HexDigest = undefined;
302	var w: std.Io.Writer = .fixed(&out_digest);
303	w.printHex(&bin_digest, .lower) catch unreachable;
304	return out_digest;
305	}
306
307	pub const Lock = struct {
308	manifest_file: Io.File,
309
310	pub fn release(lock: *Lock, io: Io) void {
311	if (builtin.os.tag == .windows) {
312	// Windows does not guarantee that locks are immediately unlocked when
313	// the file handle is closed. See LockFileEx documentation.
314	lock.manifest_file.unlock(io);
315	}
316
317	lock.manifest_file.close(io);
318	lock.* = undefined;
319	}
320	};
321
322	pub const Manifest = struct {
323	cache: *Cache,
324	/// Current state for incremental hashing.
325	hash: HashHelper,
326	manifest_file: ?Io.File,
327	manifest_dirty: bool,
328	/// Set this flag to true before calling hit() in order to indicate that
329	/// upon a cache hit, the code using the cache will not modify the files
330	/// within the cache directory. This allows multiple processes to utilize
331	/// the same cache directory at the same time.
332	want_shared_lock: bool = true,
333	have_exclusive_lock: bool = false,
334	// Indicate that we want isProblematicTimestamp to perform a filesystem write in
335	// order to obtain a problematic timestamp for the next call. Calls after that
336	// will then use the same timestamp, to avoid unnecessary filesystem writes.
337	want_refresh_timestamp: bool = true,
338	files: Files = .{},
339	hex_digest: HexDigest,
340	diagnostic: Diagnostic = .none,
341	/// Keeps track of the last time we performed a file system write to observe
342	/// what time the file system thinks it is, according to its own granularity.
343	recent_problematic_timestamp: Io.Timestamp = .zero,
344
345	pub const Diagnostic = union(enum) {
346	none,
347	manifest_create: Io.File.OpenError,
348	manifest_read: Io.File.Reader.Error,
349	manifest_lock: Io.File.LockError,
350	file_open: FileOp,
351	file_stat: FileOp,
352	file_read: FileOp,
353	file_hash: FileOp,
354
355	pub const FileOp = struct {
356	file_index: usize,
357	err: anyerror,
358	};
359	};
360
361	pub const Files = std.array_hash_map.Custom(File, void, FilesContext, false);
362
363	pub const FilesContext = struct {
364	pub fn hash(fc: FilesContext, file: File) u32 {
365	_ = fc;
366	return file.prefixed_path.hash();
367	}
368
369	pub fn eql(fc: FilesContext, a: File, b: File, b_index: usize) bool {
370	_ = fc;
371	_ = b_index;
372	return a.prefixed_path.eql(b.prefixed_path);
373	}
374	};
375
376	const FilesAdapter = struct {
377	pub fn eql(context: @This(), a: PrefixedPath, b: File, b_index: usize) bool {
378	_ = context;
379	_ = b_index;
380	return a.eql(b.prefixed_path);
381	}
382
383	pub fn hash(context: @This(), key: PrefixedPath) u32 {
384	_ = context;
385	return key.hash();
386	}
387	};
388
389	/// Add a file as a dependency of process being cached. When `hit` is
390	/// called, the file's contents will be checked to ensure that it matches
391	/// the contents from previous times.
392	///
393	/// Max file size will be used to determine the amount of space the file contents
394	/// are allowed to take up in memory. If max_file_size is null, then the contents
395	/// will not be loaded into memory.
396	///
397	/// Returns the index of the entry in the `files` array list. You can use it
398	/// to access the contents of the file after calling `hit()` like so:
399	///
400	/// ```
401	/// var file_contents = cache_hash.files.keys()[file_index].contents.?;
402	/// ```
403	pub fn addFilePath(m: *Manifest, file_path: Path, max_file_size: ?usize) !usize {
404	return addOpenedFile(m, file_path, null, max_file_size);
405	}
406
407	/// Same as `addFilePath` except the file has already been opened.
408	pub fn addOpenedFile(m: *Manifest, path: Path, handle: ?Io.File, max_file_size: ?usize) !usize {
409	const gpa = m.cache.gpa;
410	try m.files.ensureUnusedCapacity(gpa, 1);
411	const resolved_path = try std.fs.path.resolve(gpa, &.{
412	path.root_dir.path orelse ".",
413	path.subPathOrDot(),
414	});
415	errdefer gpa.free(resolved_path);
416	const prefixed_path = try m.cache.findPrefixResolved(resolved_path);
417	return addFileInner(m, prefixed_path, handle, max_file_size);
418	}
419
420	fn addFileInner(self: *Manifest, prefixed_path: PrefixedPath, handle: ?Io.File, max_file_size: ?usize) usize {
421	const gop = self.files.getOrPutAssumeCapacityAdapted(prefixed_path, FilesAdapter{});
422	if (gop.found_existing) {
423	self.cache.gpa.free(prefixed_path.sub_path);
424	gop.key_ptr.updateMaxSize(max_file_size);
425	gop.key_ptr.updateHandle(handle);
426	return gop.index;
427	}
428	gop.key_ptr.* = .{
429	.prefixed_path = prefixed_path,
430	.contents = null,
431	.max_file_size = max_file_size,
432	.stat = undefined,
433	.bin_digest = undefined,
434	.handle = handle,
435	};
436
437	self.hash.add(prefixed_path.prefix);
438	self.hash.addBytes(prefixed_path.sub_path);
439
440	return gop.index;
441	}
442
443	pub fn addOptionalFilePath(self: *Manifest, optional_file_path: ?Path) !void {
444	self.hash.add(optional_file_path != null);
445	const file_path = optional_file_path orelse return;
446	_ = try self.addFilePath(file_path, null);
447	}
448
449	pub fn addDepFile(self: *Manifest, dir: Io.Dir, dep_file_sub_path: []const u8) !void {
450	assert(self.manifest_file == null);
451	return self.addDepFileMaybePost(dir, dep_file_sub_path);
452	}
453
454	pub const HitError = error{
455	/// Unable to check the cache for a reason that has been recorded into
456	/// the `diagnostic` field.
457	CacheCheckFailed,
458	/// A cache manifest file exists however it could not be parsed.
459	InvalidFormat,
460	OutOfMemory,
461	Canceled,
462	};
463
464	/// Check the cache to see if the input exists in it. If it exists, returns `true`.
465	/// A hex encoding of its hash is available by calling `final`.
466	///
467	/// This function will also acquire an exclusive lock to the manifest file. This means
468	/// that a process holding a Manifest will block any other process attempting to
469	/// acquire the lock. If `want_shared_lock` is `true`, a cache hit guarantees the
470	/// manifest file to be locked in shared mode, and a cache miss guarantees the manifest
471	/// file to be locked in exclusive mode.
472	///
473	/// The lock on the manifest file is released when `deinit` is called. As another
474	/// option, one may call `toOwnedLock` to obtain a smaller object which can represent
475	/// the lock. `deinit` is safe to call whether or not `toOwnedLock` has been called.
476	pub fn hit(man: *Manifest, parent_progress_node: std.Progress.Node) HitError!bool {
477	const node = parent_progress_node.start("Reusing Cache Artifacts", 0);
478	defer node.end();
479	return hitInner(man);
480	}
481
482	pub fn hitInner(self: *Manifest) HitError!bool {
483	assert(self.manifest_file == null);
484
485	self.diagnostic = .none;
486
487	const ext = ".txt";
488	var manifest_file_path: [hex_digest_len + ext.len]u8 = undefined;
489
490	var bin_digest: BinDigest = undefined;
491	self.hash.hasher.final(&bin_digest);
492
493	self.hex_digest = binToHex(bin_digest);
494
495	@memcpy(manifest_file_path[0..self.hex_digest.len], &self.hex_digest);
496	manifest_file_path[hex_digest_len..][0..ext.len].* = ext.*;
497
498	const io = self.cache.io;
499
500	// We'll try to open the cache with an exclusive lock, but if that would block
501	// and `want_shared_lock` is set, a shared lock might be sufficient, so we'll
502	// open with a shared lock instead.
503	while (true) {
504	if (self.cache.manifest_dir.createFile(io, &manifest_file_path, .{
505	.read = true,
506	.truncate = false,
507	.lock = .exclusive,
508	.lock_nonblocking = self.want_shared_lock,
509	})) |manifest_file| {
510	self.manifest_file = manifest_file;
511	self.have_exclusive_lock = true;
512	break;
513	} else |err| switch (err) {
514	error.WouldBlock => {
515	self.manifest_file = self.cache.manifest_dir.openFile(io, &manifest_file_path, .{
516	.mode = .read_write,
517	.lock = .shared,
518	}) catch |e| {
519	self.diagnostic = .{ .manifest_create = e };
520	return error.CacheCheckFailed;
521	};
522	break;
523	},
524	error.FileNotFound => {
525	// There are no dir components, so the only possibility
526	// should be that the directory behind the handle has been
527	// deleted, however we have observed on macOS two processes
528	// racing to do openat() with O_CREAT manifest in ENOENT.
529	//
530	// As a workaround, we retry with exclusive=true which
531	// disambiguates by returning EEXIST, indicating original
532	// failure was a race, or ENOENT, indicating deletion of
533	// the directory of our open handle.
534	if (!builtin.os.tag.isDarwin()) {
535	self.diagnostic = .{ .manifest_create = error.FileNotFound };
536	return error.CacheCheckFailed;
537	}
538
539	if (self.cache.manifest_dir.createFile(io, &manifest_file_path, .{
540	.read = true,
541	.truncate = false,
542	.lock = .exclusive,
543	.lock_nonblocking = self.want_shared_lock,
544	.exclusive = true,
545	})) |manifest_file| {
546	self.manifest_file = manifest_file;
547	self.have_exclusive_lock = true;
548	break;
549	} else |excl_err| switch (excl_err) {
550	error.WouldBlock, error.PathAlreadyExists => continue,
551	error.FileNotFound => {
552	self.diagnostic = .{ .manifest_create = error.FileNotFound };
553	return error.CacheCheckFailed;
554	},
555	error.Canceled => |e| return e,
556	else => |e| {
557	self.diagnostic = .{ .manifest_create = e };
558	return error.CacheCheckFailed;
559	},
560	}
561	},
562	error.Canceled => |e| return e,
563	else => |e| {
564	self.diagnostic = .{ .manifest_create = e };
565	return error.CacheCheckFailed;
566	},
567	}
568	}
569
570	self.want_refresh_timestamp = true;
571
572	const input_file_count = self.files.entries.len;
573
574	// We're going to construct a second hash. Its input will begin with the digest we've
575	// already computed (`bin_digest`), and then it'll have the digests of each input file,
576	// including "post" files (see `addFilePost`). If this is a hit, we learn the set of "post"
577	// files from the manifest on disk. If this is a miss, we'll learn those from future calls
578	// to `addFilePost` etc. As such, the state of `self.hash.hasher` after this function
579	// depends on whether this is a hit or a miss.
580	//
581	// If we return `true` indicating a cache hit, then `self.hash.hasher` must already include
582	// the digests of the "post" files, so the caller can call `final`. Otherwise, on a cache
583	// miss, `self.hash.hasher` will include the digests of all non-"post" files -- that is,
584	// the ones we've already been told about. The rest will be discovered through calls to
585	// `addFilePost` etc, which will update the hasher. After all files are added, the user can
586	// use `final`, and will at some point `writeManifest` the file list to disk.
587
588	self.hash.hasher = hasher_init;
589	self.hash.hasher.update(&bin_digest);
590
591	hit: {
592	const file_digests_populated: usize = digests: {
593	switch (try self.hitWithCurrentLock()) {
594	.hit => break :hit,
595	.miss => |m| if (!try self.upgradeToExclusiveLock()) {
596	break :digests m.file_digests_populated;
597	},
598	}
599	// We've just had a miss with the shared lock, and upgraded to an exclusive lock. Someone
600	// else might have modified the digest, so we need to check again before deciding to miss.
601	// Before trying again, we must reset `self.hash.hasher` and `self.files`.
602	// This is basically just the first half of `unhit`.
603	self.hash.hasher = hasher_init;
604	self.hash.hasher.update(&bin_digest);
605	while (self.files.count() != input_file_count) {
606	var file = self.files.pop().?;
607	file.key.deinit(self.cache.gpa);
608	}
609	switch (try self.hitWithCurrentLock()) {
610	.hit => break :hit,
611	.miss => |m| break :digests m.file_digests_populated,
612	}
613	};
614
615	// This is a guaranteed cache miss. We're almost ready to return `false`, but there's a
616	// little bookkeeping to do first. The first `file_digests_populated` entries in `files`
617	// have their `bin_digest` populated; there may be some left in `input_file_count` which
618	// we'll need to populate ourselves. Other than that, this is basically `unhit`.
619	self.manifest_dirty = true;
620	self.hash.hasher = hasher_init;
621	self.hash.hasher.update(&bin_digest);
622	while (self.files.count() != input_file_count) {
623	var file = self.files.pop().?;
624	file.key.deinit(self.cache.gpa);
625	}
626	for (self.files.keys(), 0..) |*file, idx| {
627	if (idx < file_digests_populated) {
628	// `bin_digest` is already populated by `hitWithCurrentLock`, so we can use it directly.
629	self.hash.hasher.update(&file.bin_digest);
630	} else {
631	self.populateFileHash(file) catch |err| {
632	self.diagnostic = .{ .file_hash = .{
633	.file_index = idx,
634	.err = err,
635	} };
636	return error.CacheCheckFailed;
637	};
638	}
639	}
640	return false;
641	}
642
643	if (self.want_shared_lock) {
644	self.downgradeToSharedLock() catch |err| {
645	self.diagnostic = .{ .manifest_lock = err };
646	return error.CacheCheckFailed;
647	};
648	}
649
650	return true;
651	}
652
653	/// Assumes that `self.hash.hasher` has been updated only with the original digest and that
654	/// `self.files` contains only the original input files.
655	fn hitWithCurrentLock(self: *Manifest) HitError!union(enum) {
656	hit,
657	miss: struct {
658	file_digests_populated: usize,
659	},
660	} {
661	const gpa = self.cache.gpa;
662	const io = self.cache.io;
663	const input_file_count = self.files.entries.len;
664	var tiny_buffer: [1]u8 = undefined; // allows allocRemaining to detect limit exceeded
665	var manifest_reader = self.manifest_file.?.reader(io, &tiny_buffer); // Reads positionally from zero.
666	const limit: std.Io.Limit = .limited(manifest_file_size_max);
667	const file_contents = manifest_reader.interface.allocRemaining(gpa, limit) catch |err| switch (err) {
668	error.OutOfMemory => |e| return e,
669	error.StreamTooLong => return error.OutOfMemory,
670	error.ReadFailed => {
671	self.diagnostic = .{ .manifest_read = manifest_reader.err.? };
672	return error.CacheCheckFailed;
673	},
674	};
675	defer gpa.free(file_contents);
676
677	var any_file_changed = false;
678	var line_iter = mem.tokenizeScalar(u8, file_contents, '\n');
679	var idx: usize = 0;
680	const header_valid = valid: {
681	const line = line_iter.next() orelse break :valid false;
682	break :valid std.mem.eql(u8, line, manifest_header);
683	};
684	if (!header_valid) {
685	return .{ .miss = .{ .file_digests_populated = 0 } };
686	}
687	while (line_iter.next()) |line| {
688	defer idx += 1;
689
690	var iter = mem.tokenizeScalar(u8, line, ' ');
691	const size = iter.next() orelse return error.InvalidFormat;
692	const inode = iter.next() orelse return error.InvalidFormat;
693	const mtime_nsec_str = iter.next() orelse return error.InvalidFormat;
694	const digest_str = iter.next() orelse return error.InvalidFormat;
695	const prefix_str = iter.next() orelse return error.InvalidFormat;
696	const file_path = iter.rest();
697
698	const stat_size = fmt.parseInt(u64, size, 10) catch return error.InvalidFormat;
699	const stat_inode = fmt.parseInt(Io.File.INode, inode, 10) catch return error.InvalidFormat;
700	const stat_mtime = fmt.parseInt(i64, mtime_nsec_str, 10) catch return error.InvalidFormat;
701	const file_bin_digest = b: {
702	if (digest_str.len != hex_digest_len) return error.InvalidFormat;
703	var bd: BinDigest = undefined;
704	_ = fmt.hexToBytes(&bd, digest_str) catch return error.InvalidFormat;
705	break :b bd;
706	};
707
708	const prefix = fmt.parseInt(u8, prefix_str, 10) catch return error.InvalidFormat;
709	if (prefix >= self.cache.prefixes_len) return error.InvalidFormat;
710
711	if (file_path.len == 0) return error.InvalidFormat;
712
713	const cache_hash_file = f: {
714	const prefixed_path: PrefixedPath = .{
715	.prefix = prefix,
716	.sub_path = file_path, // expires with file_contents
717	};
718	if (idx < input_file_count) {
719	const file = &self.files.keys()[idx];
720	if (!file.prefixed_path.eql(prefixed_path))
721	return error.InvalidFormat;
722
723	file.stat = .{
724	.size = stat_size,
725	.inode = stat_inode,
726	.mtime = .{ .nanoseconds = stat_mtime },
727	};
728	file.bin_digest = file_bin_digest;
729	break :f file;
730	}
731	const gop = try self.files.getOrPutAdapted(gpa, prefixed_path, FilesAdapter{});
732	errdefer _ = self.files.pop();
733	if (!gop.found_existing) {
734	gop.key_ptr.* = .{
735	.prefixed_path = .{
736	.prefix = prefix,
737	.sub_path = try gpa.dupe(u8, file_path),
738	},
739	.contents = null,
740	.max_file_size = null,
741	.handle = null,
742	.stat = .{
743	.size = stat_size,
744	.inode = stat_inode,
745	.mtime = .{ .nanoseconds = stat_mtime },
746	},
747	.bin_digest = file_bin_digest,
748	};
749	}
750	break :f gop.key_ptr;
751	};
752
753	const pp = cache_hash_file.prefixed_path;
754	const dir = self.cache.prefixes()[pp.prefix].handle;
755	const this_file = dir.openFile(io, pp.sub_path, .{ .mode = .read_only }) catch |err| switch (err) {
756	error.FileNotFound => {
757	// Every digest before this one has been populated successfully.
758	return .{ .miss = .{ .file_digests_populated = idx } };
759	},
760	error.Canceled => |e| return e,
761	else => |e| {
762	self.diagnostic = .{ .file_open = .{
763	.file_index = idx,
764	.err = e,
765	} };
766	return error.CacheCheckFailed;
767	},
768	};
769	defer this_file.close(io);
770
771	const actual_stat = this_file.stat(io) catch |err| {
772	self.diagnostic = .{ .file_stat = .{
773	.file_index = idx,
774	.err = err,
775	} };
776	return error.CacheCheckFailed;
777	};
778	const size_match = actual_stat.size == cache_hash_file.stat.size;
779	const mtime_match = actual_stat.mtime.nanoseconds == cache_hash_file.stat.mtime.nanoseconds;
780	const inode_match = actual_stat.inode == cache_hash_file.stat.inode;
781
782	if (!size_match or !mtime_match or !inode_match) {
783	cache_hash_file.stat = .{
784	.size = actual_stat.size,
785	.mtime = actual_stat.mtime,
786	.inode = actual_stat.inode,
787	};
788
789	if (try self.isProblematicTimestamp(cache_hash_file.stat.mtime)) {
790	// The actual file has an unreliable timestamp, force it to be hashed
791	cache_hash_file.stat.mtime = .zero;
792	cache_hash_file.stat.inode = 0;
793	}
794
795	var actual_digest: BinDigest = undefined;
796	hashFile(io, this_file, &actual_digest) catch |err| {
797	self.diagnostic = .{ .file_read = .{
798	.file_index = idx,
799	.err = err,
800	} };
801	return error.CacheCheckFailed;
802	};
803
804	if (!mem.eql(u8, &cache_hash_file.bin_digest, &actual_digest)) {
805	cache_hash_file.bin_digest = actual_digest;
806	// keep going until we have the input file digests
807	any_file_changed = true;
808	}
809	}
810
811	if (!any_file_changed) {
812	self.hash.hasher.update(&cache_hash_file.bin_digest);
813	}
814	}
815
816	// If the manifest was somehow missing one of our input files, or if any file hash has changed,
817	// then this is a cache miss. However, we have successfully populated some or all of the file
818	// digests.
819	if (any_file_changed or idx < input_file_count) {
820	return .{ .miss = .{ .file_digests_populated = idx } };
821	}
822
823	return .hit;
824	}
825
826	/// Reset `self.hash.hasher` to the state it should be in after `hit` returns `false`.
827	/// The hasher contains the original input digest, and all original input file digests (i.e.
828	/// not including post files).
829	/// Assumes that `bin_digest` is populated for all files up to `input_file_count`. As such,
830	/// this is not necessarily safe to call within `hit`.
831	pub fn unhit(self: *Manifest, bin_digest: BinDigest, input_file_count: usize) void {
832	// Reset the hash.
833	self.hash.hasher = hasher_init;
834	self.hash.hasher.update(&bin_digest);
835
836	// Remove files not in the initial hash.
837	while (self.files.count() != input_file_count) {
838	var file = self.files.pop().?;
839	file.key.deinit(self.cache.gpa);
840	}
841
842	for (self.files.keys()) |file| {
843	self.hash.hasher.update(&file.bin_digest);
844	}
845	}
846
847	fn isProblematicTimestamp(man: *Manifest, timestamp: Io.Timestamp) error{Canceled}!bool {
848	const io = man.cache.io;
849
850	// If the file_time is prior to the most recent problematic timestamp
851	// then we don't need to access the filesystem.
852	if (timestamp.nanoseconds < man.recent_problematic_timestamp.nanoseconds)
853	return false;
854
855	// Next we will check the globally shared Cache timestamp, which is accessed
856	// from multiple threads.
857	try man.cache.mutex.lock(io);
858	defer man.cache.mutex.unlock(io);
859
860	// Save the global one to our local one to avoid locking next time.
861	man.recent_problematic_timestamp = man.cache.recent_problematic_timestamp;
862	if (timestamp.nanoseconds < man.recent_problematic_timestamp.nanoseconds)
863	return false;
864
865	// This flag prevents multiple filesystem writes for the same hit() call.
866	if (man.want_refresh_timestamp) {
867	man.want_refresh_timestamp = false;
868
869	var file = man.cache.manifest_dir.createFile(io, "timestamp", .{
870	.read = true,
871	.truncate = true,
872	}) catch |err| switch (err) {
873	error.Canceled => |e| return e,
874	else => return true,
875	};
876	defer file.close(io);
877
878	// Save locally and also save globally (we still hold the global lock).
879	const stat = file.stat(io) catch |err| switch (err) {
880	error.Canceled => |e| return e,
881	else => return true,
882	};
883	man.recent_problematic_timestamp = stat.mtime;
884	man.cache.recent_problematic_timestamp = man.recent_problematic_timestamp;
885	}
886
887	return timestamp.nanoseconds >= man.recent_problematic_timestamp.nanoseconds;
888	}
889
890	fn populateFileHash(self: *Manifest, ch_file: *File) !void {
891	const io = self.cache.io;
892
893	if (ch_file.handle) |handle| {
894	return populateFileHashHandle(self, ch_file, handle);
895	} else {
896	const pp = ch_file.prefixed_path;
897	const dir = self.cache.prefixes()[pp.prefix].handle;
898	const handle = try dir.openFile(io, pp.sub_path, .{});
899	defer handle.close(io);
900	return populateFileHashHandle(self, ch_file, handle);
901	}
902	}
903
904	fn populateFileHashHandle(self: *Manifest, ch_file: *File, io_file: Io.File) !void {
905	const io = self.cache.io;
906	const gpa = self.cache.gpa;
907
908	const actual_stat = try io_file.stat(io);
909	ch_file.stat = .{
910	.size = actual_stat.size,
911	.mtime = actual_stat.mtime,
912	.inode = actual_stat.inode,
913	};
914
915	if (try self.isProblematicTimestamp(ch_file.stat.mtime)) {
916	// The actual file has an unreliable timestamp, force it to be hashed
917	ch_file.stat.mtime = .zero;
918	ch_file.stat.inode = 0;
919	}
920
921	if (ch_file.max_file_size) |max_file_size| {
922	if (ch_file.stat.size > max_file_size) return error.FileTooBig;
923
924	// Hash while reading from disk, to keep the contents in the cpu
925	// cache while doing hashing.
926	const contents = try gpa.alloc(u8, @intCast(ch_file.stat.size));
927	errdefer gpa.free(contents);
928
929	var hasher = hasher_init;
930	var off: usize = 0;
931	while (true) {
932	const bytes_read = try io_file.readPositional(io, &.{contents[off..]}, off);
933	if (bytes_read == 0) break;
934	hasher.update(contents[off..][0..bytes_read]);
935	off += bytes_read;
936	}
937	hasher.final(&ch_file.bin_digest);
938
939	ch_file.contents = contents;
940	} else {
941	try hashFile(io, io_file, &ch_file.bin_digest);
942	}
943
944	self.hash.hasher.update(&ch_file.bin_digest);
945	}
946
947	/// Add a file as a dependency of process being cached, after the initial hash has been
948	/// calculated. This is useful for processes that don't know all the files that
949	/// are depended on ahead of time. For example, a source file that can import other files
950	/// will need to be recompiled if the imported file is changed.
951	pub fn addFilePostFetch(self: *Manifest, file_path: []const u8, max_file_size: usize) ![]const u8 {
952	assert(self.manifest_file != null);
953
954	const gpa = self.cache.gpa;
955	const prefixed_path = try self.cache.findPrefix(file_path);
956	errdefer gpa.free(prefixed_path.sub_path);
957
958	const gop = try self.files.getOrPutAdapted(gpa, prefixed_path, FilesAdapter{});
959	errdefer _ = self.files.pop();
960
961	if (gop.found_existing) {
962	gpa.free(prefixed_path.sub_path);
963	return gop.key_ptr.contents.?;
964	}
965
966	gop.key_ptr.* = .{
967	.prefixed_path = prefixed_path,
968	.max_file_size = max_file_size,
969	.stat = undefined,
970	.bin_digest = undefined,
971	.contents = null,
972	.handle = null,
973	};
974
975	self.files.lockPointers();
976	defer self.files.unlockPointers();
977
978	try self.populateFileHash(gop.key_ptr);
979	return gop.key_ptr.contents.?;
980	}
981
982	/// Add a file as a dependency of process being cached, after the initial hash has been
983	/// calculated.
984	///
985	/// This is useful for processes that don't know the all the files that are
986	/// depended on ahead of time. For example, a source file that can import
987	/// other files will need to be recompiled if the imported file is changed.
988	pub fn addFilePost(man: *Manifest, file_path: []const u8) !void {
989	assert(man.manifest_file != null);
990	const gpa = man.cache.gpa;
991	const prefixed_path = try man.cache.findPrefix(file_path);
992	var keep = false;
993	defer if (!keep) gpa.free(prefixed_path.sub_path);
994	keep = try addPrefixedPathPost(man, prefixed_path);
995	}
996
997	pub fn addPathPost(man: *Manifest, path: Path) !void {
998	assert(man.manifest_file != null);
999	const gpa = man.cache.gpa;
1000	const prefixed_path: PrefixedPath = try man.cache.findPrefixPath(path);
1001	var keep = false;
1002	defer if (!keep) gpa.free(prefixed_path.sub_path);
1003	keep = try addPrefixedPathPost(man, prefixed_path);
1004	}
1005
1006	/// Low level function. `prefixed_path` references cloned memory. Returns
1007	/// whether or not `prefixed_path.sub_path` should be kept.
1008	pub fn addPrefixedPathPost(man: *Manifest, prefixed_path: PrefixedPath) !bool {
1009	assert(man.manifest_file != null);
1010	const gpa = man.cache.gpa;
1011
1012	const gop = try man.files.getOrPutAdapted(gpa, prefixed_path, FilesAdapter{});
1013	errdefer _ = man.files.pop();
1014
1015	if (gop.found_existing) return false;
1016
1017	gop.key_ptr.* = .{
1018	.prefixed_path = prefixed_path,
1019	.max_file_size = null,
1020	.handle = null,
1021	.stat = undefined,
1022	.bin_digest = undefined,
1023	.contents = null,
1024	};
1025
1026	man.files.lockPointers();
1027	defer man.files.unlockPointers();
1028
1029	try man.populateFileHash(gop.key_ptr);
1030	return true;
1031	}
1032
1033	/// Like `addFilePost` but when the file contents have already been loaded from disk.
1034	pub fn addFilePostContents(
1035	man: *Manifest,
1036	file_path: []const u8,
1037	bytes: []const u8,
1038	stat: File.Stat,
1039	) !void {
1040	assert(man.manifest_file != null);
1041	const gpa = man.cache.gpa;
1042	const prefixed_path = try man.cache.findPrefix(file_path);
1043	var keep = false;
1044	defer if (!keep) gpa.free(prefixed_path.sub_path);
1045	keep = try addPrefixedPathPostContents(man, prefixed_path, bytes, stat);
1046	}
1047
1048	/// Low level function. `prefixed_path` references cloned memory. Returns
1049	/// whether or not `prefixed_path.sub_path` should be kept.
1050	pub fn addPrefixedPathPostContents(
1051	man: *Manifest,
1052	prefixed_path: PrefixedPath,
1053	bytes: []const u8,
1054	stat: File.Stat,
1055	) !bool {
1056	const gpa = man.cache.gpa;
1057	const gop = try man.files.getOrPutAdapted(gpa, prefixed_path, FilesAdapter{});
1058	errdefer _ = man.files.pop();
1059
1060	if (gop.found_existing) return false;
1061
1062	const new_file = gop.key_ptr;
1063
1064	new_file.* = .{
1065	.prefixed_path = prefixed_path,
1066	.max_file_size = null,
1067	.handle = null,
1068	.stat = stat,
1069	.bin_digest = undefined,
1070	.contents = null,
1071	};
1072
1073	if (try man.isProblematicTimestamp(new_file.stat.mtime)) {
1074	// The actual file has an unreliable timestamp, force it to be hashed
1075	new_file.stat.mtime = .zero;
1076	new_file.stat.inode = 0;
1077	}
1078
1079	{
1080	var hasher = hasher_init;
1081	hasher.update(bytes);
1082	hasher.final(&new_file.bin_digest);
1083	}
1084
1085	man.hash.hasher.update(&new_file.bin_digest);
1086	return true;
1087	}
1088
1089	pub fn addDepFilePost(self: *Manifest, dir: Io.Dir, dep_file_sub_path: []const u8) !void {
1090	assert(self.manifest_file != null);
1091	return self.addDepFileMaybePost(dir, dep_file_sub_path);
1092	}
1093
1094	fn addDepFileMaybePost(self: *Manifest, dir: Io.Dir, dep_file_sub_path: []const u8) !void {
1095	const gpa = self.cache.gpa;
1096	const io = self.cache.io;
1097	const dep_file_contents = try dir.readFileAlloc(io, dep_file_sub_path, gpa, .limited(manifest_file_size_max));
1098	defer gpa.free(dep_file_contents);
1099
1100	var error_buf: std.ArrayList(u8) = .empty;
1101	defer error_buf.deinit(gpa);
1102
1103	var resolve_buf: std.ArrayList(u8) = .empty;
1104	defer resolve_buf.deinit(gpa);
1105
1106	var it: DepTokenizer = .{ .bytes = dep_file_contents };
1107	while (it.next()) |token| {
1108	switch (token) {
1109	// We don't care about targets, we only want the prereqs
1110	// Clang is invoked in single-source mode but other programs may not
1111	.target, .target_must_resolve => {},
1112	.prereq => |file_path| if (self.manifest_file == null) {
1113	_ = try self.addFilePath(.initCwd(file_path), null);
1114	} else try self.addFilePost(file_path),
1115	.prereq_must_resolve => {
1116	resolve_buf.clearRetainingCapacity();
1117	try token.resolve(gpa, &resolve_buf);
1118	if (self.manifest_file == null) {
1119	_ = try self.addFilePath(.initCwd(resolve_buf.items), null);
1120	} else try self.addFilePost(resolve_buf.items);
1121	},
1122	else => |err| {
1123	try err.printError(gpa, &error_buf);
1124	log.err("failed parsing {s}: {s}", .{ dep_file_sub_path, error_buf.items });
1125	return error.InvalidDepFile;
1126	},
1127	}
1128	}
1129	}
1130
1131	/// Returns a binary hash of the inputs.
1132	pub fn finalBin(self: *Manifest) BinDigest {
1133	assert(self.manifest_file != null);
1134
1135	// We don't close the manifest file yet, because we want to
1136	// keep it locked until the API user is done using it.
1137	// We also don't write out the manifest yet, because until
1138	// cache_release is called we still might be working on creating
1139	// the artifacts to cache.
1140
1141	var bin_digest: BinDigest = undefined;
1142	self.hash.hasher.final(&bin_digest);
1143	return bin_digest;
1144	}
1145
1146	/// Returns a hex encoded hash of the inputs.
1147	pub fn final(self: *Manifest) HexDigest {
1148	const bin_digest = self.finalBin();
1149	return binToHex(bin_digest);
1150	}
1151
1152	/// If `want_shared_lock` is true, this function automatically downgrades the
1153	/// lock from exclusive to shared.
1154	pub fn writeManifest(self: *Manifest) !void {
1155	assert(self.have_exclusive_lock);
1156	const io = self.cache.io;
1157	const manifest_file = self.manifest_file.?;
1158	if (self.manifest_dirty) {
1159	self.manifest_dirty = false;
1160
1161	var buffer: [4000]u8 = undefined;
1162	var fw = manifest_file.writer(io, &buffer);
1163	writeDirtyManifestToStream(self, &fw) catch |err| switch (err) {
1164	error.WriteFailed => return fw.err.?,
1165	else => |e| return e,
1166	};
1167	}
1168
1169	if (self.want_shared_lock) {
1170	try self.downgradeToSharedLock();
1171	}
1172	}
1173
1174	fn writeDirtyManifestToStream(self: *Manifest, fw: *Io.File.Writer) !void {
1175	try fw.interface.writeAll(manifest_header ++ "\n");
1176	for (self.files.keys()) |file| {
1177	try fw.interface.print("{d} {d} {d} {x} {d} {s}\n", .{
1178	file.stat.size,
1179	file.stat.inode,
1180	file.stat.mtime,
1181	&file.bin_digest,
1182	file.prefixed_path.prefix,
1183	file.prefixed_path.sub_path,
1184	});
1185	}
1186	try fw.end();
1187	}
1188
1189	fn downgradeToSharedLock(self: *Manifest) !void {
1190	if (!self.have_exclusive_lock) return;
1191	const io = self.cache.io;
1192
1193	if (std.process.can_spawn or !builtin.single_threaded) {
1194	const manifest_file = self.manifest_file.?;
1195	try manifest_file.downgradeLock(io);
1196	}
1197
1198	self.have_exclusive_lock = false;
1199	}
1200
1201	fn upgradeToExclusiveLock(self: *Manifest) error{CacheCheckFailed}!bool {
1202	if (self.have_exclusive_lock) return false;
1203	assert(self.manifest_file != null);
1204	const io = self.cache.io;
1205
1206	if (std.process.can_spawn or !builtin.single_threaded) {
1207	const manifest_file = self.manifest_file.?;
1208	// Here we intentionally have a period where the lock is released, in case there are
1209	// other processes holding a shared lock.
1210	manifest_file.unlock(io);
1211	manifest_file.lock(io, .exclusive) catch |err| {
1212	self.diagnostic = .{ .manifest_lock = err };
1213	return error.CacheCheckFailed;
1214	};
1215	}
1216	self.have_exclusive_lock = true;
1217	return true;
1218	}
1219
1220	/// Obtain only the data needed to maintain a lock on the manifest file.
1221	/// The `Manifest` remains safe to deinit.
1222	///
1223	/// Don't forget to call `writeManifest` before this!
1224	pub fn toOwnedLock(self: *Manifest) Lock {
1225	defer self.manifest_file = null;
1226	return .{ .manifest_file = self.manifest_file.? };
1227	}
1228
1229	pub fn takeFiles(man: *Manifest) Files {
1230	defer man.files = .empty;
1231	return man.files;
1232	}
1233
1234	pub fn freeFiles(gpa: Allocator, files: *Files) void {
1235	for (files.keys()) |*file| file.deinit(gpa);
1236	files.deinit(gpa);
1237	}
1238
1239	/// Releases the manifest file and frees any memory the Manifest was using.
1240	/// `Manifest.hit` must be called first.
1241	///
1242	/// Don't forget to call `writeManifest` before this!
1243	pub fn deinit(man: *Manifest) void {
1244	const io = man.cache.io;
1245	const gpa = man.cache.gpa;
1246
1247	if (man.manifest_file) |file| {
1248	if (builtin.os.tag == .windows) {
1249	// See Lock.release for why this is required on Windows
1250	file.unlock(io);
1251	}
1252
1253	file.close(io);
1254	}
1255	freeFiles(gpa, &man.files);
1256	man.* = undefined;
1257	}
1258
1259	pub fn populateFileSystemInputs(man: *Manifest, buf: *std.ArrayList(u8)) Allocator.Error!void {
1260	assert(@typeInfo(std.zig.Server.Message.PathPrefix).@"enum".field_names.len == man.cache.prefixes_len);
1261	buf.clearRetainingCapacity();
1262	const gpa = man.cache.gpa;
1263	const files = man.files.keys();
1264	if (files.len > 0) {
1265	for (files) |file| {
1266	try buf.ensureUnusedCapacity(gpa, file.prefixed_path.sub_path.len + 2);
1267	buf.appendAssumeCapacity(file.prefixed_path.prefix + 1);
1268	buf.appendSliceAssumeCapacity(file.prefixed_path.sub_path);
1269	buf.appendAssumeCapacity(0);
1270	}
1271	// The null byte is a separator, not a terminator.
1272	buf.items.len -= 1;
1273	}
1274	}
1275
1276	pub fn populateOtherManifest(man: *Manifest, other: *Manifest, prefix_map: [5]u8) Allocator.Error!void {
1277	const gpa = other.cache.gpa;
1278	assert(@typeInfo(std.zig.Server.Message.PathPrefix).@"enum".field_names.len == man.cache.prefixes_len);
1279	assert(man.cache.prefixes_len == 5);
1280	for (man.files.keys()) |file| {
1281	const prefixed_path: PrefixedPath = .{
1282	.prefix = prefix_map[file.prefixed_path.prefix],
1283	.sub_path = try gpa.dupe(u8, file.prefixed_path.sub_path),
1284	};
1285	errdefer gpa.free(prefixed_path.sub_path);
1286
1287	const gop = try other.files.getOrPutAdapted(gpa, prefixed_path, FilesAdapter{});
1288	errdefer _ = other.files.pop();
1289
1290	if (gop.found_existing) {
1291	gpa.free(prefixed_path.sub_path);
1292	continue;
1293	}
1294
1295	gop.key_ptr.* = .{
1296	.prefixed_path = prefixed_path,
1297	.max_file_size = file.max_file_size,
1298	.handle = file.handle,
1299	.stat = file.stat,
1300	.bin_digest = file.bin_digest,
1301	.contents = null,
1302	};
1303
1304	other.hash.hasher.update(&gop.key_ptr.bin_digest);
1305	}
1306	}
1307	};
1308
1309	fn hashFile(io: Io, file: Io.File, bin_digest: *[Hasher.mac_length]u8) Io.File.ReadPositionalError!void {
1310	var buffer: [2048]u8 = undefined;
1311	var hasher = hasher_init;
1312	var offset: u64 = 0;
1313	while (true) {
1314	const n = try file.readPositional(io, &.{&buffer}, offset);
1315	if (n == 0) break;
1316	hasher.update(buffer[0..n]);
1317	offset += n;
1318	}
1319	hasher.final(bin_digest);
1320	}
1321
1322	// Create/Write a file, close it, then grab its stat.mtime timestamp.
1323	fn testGetCurrentFileTimestamp(io: Io, dir: Io.Dir) !Io.Timestamp {
1324	const test_out_file = "test-filetimestamp.tmp";
1325
1326	var file = try dir.createFile(io, test_out_file, .{
1327	.read = true,
1328	.truncate = true,
1329	});
1330	defer {
1331	file.close(io);
1332	dir.deleteFile(io, test_out_file) catch {};
1333	}
1334
1335	return (try file.stat(io)).mtime;
1336	}
1337
1338	test "cache file and then recall it" {
1339	const io = testing.io;
1340
1341	var tmp = testing.tmpDir(.{});
1342	defer tmp.cleanup();
1343
1344	const cwd = try std.process.currentPathAlloc(io, testing.allocator);
1345	defer testing.allocator.free(cwd);
1346
1347	const temp_file = "test.txt";
1348	const temp_manifest_dir = "temp_manifest_dir";
1349
1350	try tmp.dir.writeFile(io, .{ .sub_path = temp_file, .data = "Hello, world!\n" });
1351
1352	// Wait for file timestamps to tick
1353	const initial_time = try testGetCurrentFileTimestamp(io, tmp.dir);
1354	while ((try testGetCurrentFileTimestamp(io, tmp.dir)).nanoseconds == initial_time.nanoseconds) {
1355	try std.Io.Clock.Duration.sleep(.{ .clock = .boot, .raw = .fromNanoseconds(1) }, io);
1356	}
1357
1358	var digest1: HexDigest = undefined;
1359	var digest2: HexDigest = undefined;
1360
1361	{
1362	var cache: Cache = .{
1363	.io = io,
1364	.gpa = testing.allocator,
1365	.manifest_dir = try tmp.dir.createDirPathOpen(io, temp_manifest_dir, .{}),
1366	.cwd = cwd,
1367	};
1368	cache.addPrefix(.{ .path = null, .handle = tmp.dir });
1369	defer cache.manifest_dir.close(io);
1370
1371	{
1372	var ch = cache.obtain();
1373	defer ch.deinit();
1374
1375	ch.hash.add(true);
1376	ch.hash.add(@as(u16, 1234));
1377	ch.hash.addBytes("1234");
1378	_ = try ch.addFilePath(.initCwd(temp_file), null);
1379
1380	// There should be nothing in the cache
1381	try testing.expectEqual(false, try ch.hit(.none));
1382
1383	digest1 = ch.final();
1384	try ch.writeManifest();
1385	}
1386	{
1387	var ch = cache.obtain();
1388	defer ch.deinit();
1389
1390	ch.hash.add(true);
1391	ch.hash.add(@as(u16, 1234));
1392	ch.hash.addBytes("1234");
1393	_ = try ch.addFilePath(.initCwd(temp_file), null);
1394
1395	// Cache hit! We just "built" the same file
1396	try testing.expect(try ch.hit(.none));
1397	digest2 = ch.final();
1398
1399	try testing.expectEqual(false, ch.have_exclusive_lock);
1400	}
1401
1402	try testing.expectEqual(digest1, digest2);
1403	}
1404	}
1405
1406	test "check that changing a file makes cache fail" {
1407	const io = testing.io;
1408
1409	var tmp = testing.tmpDir(.{});
1410	defer tmp.cleanup();
1411
1412	const cwd = try std.process.currentPathAlloc(io, testing.allocator);
1413	defer testing.allocator.free(cwd);
1414
1415	const temp_file = "cache_hash_change_file_test.txt";
1416	const temp_manifest_dir = "cache_hash_change_file_manifest_dir";
1417	const original_temp_file_contents = "Hello, world!\n";
1418	const updated_temp_file_contents = "Hello, world; but updated!\n";
1419
1420	try tmp.dir.writeFile(io, .{ .sub_path = temp_file, .data = original_temp_file_contents });
1421
1422	// Wait for file timestamps to tick
1423	const initial_time = try testGetCurrentFileTimestamp(io, tmp.dir);
1424	while ((try testGetCurrentFileTimestamp(io, tmp.dir)).nanoseconds == initial_time.nanoseconds) {
1425	try std.Io.Clock.Duration.sleep(.{ .clock = .boot, .raw = .fromNanoseconds(1) }, io);
1426	}
1427
1428	var digest1: HexDigest = undefined;
1429	var digest2: HexDigest = undefined;
1430
1431	{
1432	var cache: Cache = .{
1433	.io = io,
1434	.gpa = testing.allocator,
1435	.manifest_dir = try tmp.dir.createDirPathOpen(io, temp_manifest_dir, .{}),
1436	.cwd = cwd,
1437	};
1438	cache.addPrefix(.{ .path = null, .handle = tmp.dir });
1439	defer cache.manifest_dir.close(io);
1440
1441	{
1442	var ch = cache.obtain();
1443	defer ch.deinit();
1444
1445	ch.hash.addBytes("1234");
1446	const temp_file_idx = try ch.addFilePath(.initCwd(temp_file), 100);
1447
1448	// There should be nothing in the cache
1449	try testing.expectEqual(false, try ch.hit(.none));
1450
1451	try testing.expect(mem.eql(u8, original_temp_file_contents, ch.files.keys()[temp_file_idx].contents.?));
1452
1453	digest1 = ch.final();
1454
1455	try ch.writeManifest();
1456	}
1457
1458	try tmp.dir.writeFile(io, .{ .sub_path = temp_file, .data = updated_temp_file_contents });
1459
1460	{
1461	var ch = cache.obtain();
1462	defer ch.deinit();
1463
1464	ch.hash.addBytes("1234");
1465	const temp_file_idx = try ch.addFilePath(.initCwd(temp_file), 100);
1466
1467	// A file that we depend on has been updated, so the cache should not contain an entry for it
1468	try testing.expectEqual(false, try ch.hit(.none));
1469
1470	// The cache system does not keep the contents of re-hashed input files.
1471	try testing.expect(ch.files.keys()[temp_file_idx].contents == null);
1472
1473	digest2 = ch.final();
1474
1475	try ch.writeManifest();
1476	}
1477
1478	try testing.expect(!mem.eql(u8, digest1[0..], digest2[0..]));
1479	}
1480	}
1481
1482	test "no file inputs" {
1483	const io = testing.io;
1484
1485	var tmp = testing.tmpDir(.{});
1486	defer tmp.cleanup();
1487
1488	const cwd = try std.process.currentPathAlloc(io, testing.allocator);
1489	defer testing.allocator.free(cwd);
1490
1491	const temp_manifest_dir = "no_file_inputs_manifest_dir";
1492
1493	var digest1: HexDigest = undefined;
1494	var digest2: HexDigest = undefined;
1495
1496	var cache: Cache = .{
1497	.io = io,
1498	.gpa = testing.allocator,
1499	.manifest_dir = try tmp.dir.createDirPathOpen(io, temp_manifest_dir, .{}),
1500	.cwd = cwd,
1501	};
1502	cache.addPrefix(.{ .path = null, .handle = tmp.dir });
1503	defer cache.manifest_dir.close(io);
1504
1505	{
1506	var man = cache.obtain();
1507	defer man.deinit();
1508
1509	man.hash.addBytes("1234");
1510
1511	// There should be nothing in the cache
1512	try testing.expectEqual(false, try man.hit(.none));
1513
1514	digest1 = man.final();
1515
1516	try man.writeManifest();
1517	}
1518	{
1519	var man = cache.obtain();
1520	defer man.deinit();
1521
1522	man.hash.addBytes("1234");
1523
1524	try testing.expect(try man.hit(.none));
1525	digest2 = man.final();
1526	try testing.expectEqual(false, man.have_exclusive_lock);
1527	}
1528
1529	try testing.expectEqual(digest1, digest2);
1530	}
1531
1532	test "Manifest with files added after initial hash work" {
1533	const io = testing.io;
1534
1535	var tmp = testing.tmpDir(.{});
1536	defer tmp.cleanup();
1537
1538	const cwd = try std.process.currentPathAlloc(io, testing.allocator);
1539	defer testing.allocator.free(cwd);
1540
1541	const temp_file1 = "cache_hash_post_file_test1.txt";
1542	const temp_file2 = "cache_hash_post_file_test2.txt";
1543	const temp_manifest_dir = "cache_hash_post_file_manifest_dir";
1544
1545	try tmp.dir.writeFile(io, .{ .sub_path = temp_file1, .data = "Hello, world!\n" });
1546	try tmp.dir.writeFile(io, .{ .sub_path = temp_file2, .data = "Hello world the second!\n" });
1547
1548	// Wait for file timestamps to tick
1549	const initial_time = try testGetCurrentFileTimestamp(io, tmp.dir);
1550	while ((try testGetCurrentFileTimestamp(io, tmp.dir)).nanoseconds == initial_time.nanoseconds) {
1551	try std.Io.Clock.Duration.sleep(.{ .clock = .boot, .raw = .fromNanoseconds(1) }, io);
1552	}
1553
1554	var digest1: HexDigest = undefined;
1555	var digest2: HexDigest = undefined;
1556	var digest3: HexDigest = undefined;
1557
1558	{
1559	var cache: Cache = .{
1560	.io = io,
1561	.gpa = testing.allocator,
1562	.manifest_dir = try tmp.dir.createDirPathOpen(io, temp_manifest_dir, .{}),
1563	.cwd = cwd,
1564	};
1565	cache.addPrefix(.{ .path = null, .handle = tmp.dir });
1566	defer cache.manifest_dir.close(io);
1567
1568	{
1569	var ch = cache.obtain();
1570	defer ch.deinit();
1571
1572	ch.hash.addBytes("1234");
1573	_ = try ch.addFilePath(.initCwd(temp_file1), null);
1574
1575	// There should be nothing in the cache
1576	try testing.expectEqual(false, try ch.hit(.none));
1577
1578	_ = try ch.addFilePost(temp_file2);
1579
1580	digest1 = ch.final();
1581	try ch.writeManifest();
1582	}
1583	{
1584	var ch = cache.obtain();
1585	defer ch.deinit();
1586
1587	ch.hash.addBytes("1234");
1588	_ = try ch.addFilePath(.initCwd(temp_file1), null);
1589
1590	try testing.expect(try ch.hit(.none));
1591	digest2 = ch.final();
1592
1593	try testing.expectEqual(false, ch.have_exclusive_lock);
1594	}
1595	try testing.expect(mem.eql(u8, &digest1, &digest2));
1596
1597	// Modify the file added after initial hash
1598	try tmp.dir.writeFile(io, .{ .sub_path = temp_file2, .data = "Hello world the second, updated\n" });
1599
1600	// Wait for file timestamps to tick
1601	const initial_time2 = try testGetCurrentFileTimestamp(io, tmp.dir);
1602	while ((try testGetCurrentFileTimestamp(io, tmp.dir)).nanoseconds == initial_time2.nanoseconds) {
1603	try std.Io.Clock.Duration.sleep(.{ .clock = .boot, .raw = .fromNanoseconds(1) }, io);
1604	}
1605
1606	{
1607	var ch = cache.obtain();
1608	defer ch.deinit();
1609
1610	ch.hash.addBytes("1234");
1611	_ = try ch.addFilePath(.initCwd(temp_file1), null);
1612
1613	// A file that we depend on has been updated, so the cache should not contain an entry for it
1614	try testing.expectEqual(false, try ch.hit(.none));
1615
1616	_ = try ch.addFilePost(temp_file2);
1617
1618	digest3 = ch.final();
1619
1620	try ch.writeManifest();
1621	}
1622
1623	try testing.expect(!mem.eql(u8, &digest1, &digest3));
1624	}
1625	}