lib/choir/src/product/incremental.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

   1 const std = @import("std");
   2 const metadata_storage = @import("storage.zig");
   3 const revision = @import("root.zig").revision;
   4 
   5 fn fixtureStore() !*revision.Store {
   6     return revision.Store.create(std.testing.allocator, .{
   7         .revisions = 64,
   8         .kinds = 1,
   9         .builders = 1,
  10         .compiler_manifests = 2,
  11         .record_bytes = 64 * 1024,
  12         .gate_scratch_bytes = 0,
  13         .candidate_count = 1,
  14         .screening_bytes = 64 * 1024,
  15     });
  16 }
  17 
  18 fn fixtureRecord(
  19     owner: *revision.Store,
  20     stage: []const u8,
  21     image: []const u8,
  22     options: []const u8,
  23 ) !*const revision.Record {
  24     return fixtureRecordUnder(owner, stage, image, options, "graph-fixture-v1");
  25 }
  26 
  27 fn fixtureRecordUnder(
  28     owner: *revision.Store,
  29     stage: []const u8,
  30     image: []const u8,
  31     options: []const u8,
  32     manifest: []const u8,
  33 ) !*const revision.Record {
  34     const allocator = std.testing.allocator;
  35     const address = try revision.record.encodeAddress(allocator, .{
  36         .producer = "graph-fixture",
  37         .source = "module",
  38         .stage = stage,
  39         .variant = "default",
  40     });
  41     defer allocator.free(address);
  42     const inputs = try revision.record.encodeInputs(allocator, .{
  43         .compiler_manifest = manifest,
  44         .versions = &.{},
  45         .pipeline = &.{},
  46         .options = options,
  47         .policy = "",
  48     }, &.{}, "fixture-gates");
  49     defer allocator.free(inputs);
  50     const bytes = try revision.record.encodeExact(allocator, .{
  51         .address = address,
  52         .inputs = inputs,
  53         .image = image,
  54     });
  55     defer allocator.free(bytes);
  56     return owner.importRecord(bytes, manifest, .{ .bytes = 64 * 1024, .records = 1, .depth = 1 });
  57 }
  58 
  59 test "product graph rejects equal buckets for unequal exact records" {
  60     const owner = try fixtureStore();
  61     defer owner.release();
  62     const first = try fixtureRecord(owner, "source", "same-image", "threshold=1");
  63     defer first.release();
  64     const second = try fixtureRecord(owner, "source", "same-image", "threshold=2");
  65     defer second.release();
  66     try std.testing.expect(!first.eql(second));
  67     const left = productKey(first);
  68     const right = productKey(second);
  69     try std.testing.expectEqual(left.fingerprint(), right.fingerprint());
  70     try std.testing.expect(!left.eql(right));
  71     var previous = try ProductGraph.init(std.testing.allocator, &.{left}, &.{});
  72     defer previous.deinit(std.testing.allocator);
  73     var current = try ProductGraph.init(std.testing.allocator, &.{right}, &.{});
  74     defer current.deinit(std.testing.allocator);
  75     try std.testing.expect(current.refreshDecision(previous, right).shouldRefresh());
  76 }
  77 
  78 pub const ProductMetadataError = std.mem.Allocator.Error || error{ CapacityOverflow, ReferenceOverflow, InvalidProductAddress };
  79 
  80 pub const Fingerprint = u64;
  81 
  82 pub const FingerprintBuilder = struct {
  83     value: Fingerprint = fnv_offset,
  84 
  85     const fnv_offset: Fingerprint = 14_695_981_039_346_656_037;
  86     const fnv_prime: Fingerprint = 1_099_511_628_211;
  87 
  88     pub fn updateBytes(self: *FingerprintBuilder, bytes: []const u8) void {
  89         self.updateU64(bytes.len);
  90         for (bytes) |byte| {
  91             self.value ^= byte;
  92             self.value *%= fnv_prime;
  93         }
  94     }
  95 
  96     pub fn updateRawBytes(self: *FingerprintBuilder, bytes: []const u8) void {
  97         for (bytes) |byte| {
  98             self.value ^= byte;
  99             self.value *%= fnv_prime;
 100         }
 101     }
 102 
 103     pub fn updateBool(self: *FingerprintBuilder, value: bool) void {
 104         self.updateU64(@intFromBool(value));
 105     }
 106 
 107     pub fn updateU64(self: *FingerprintBuilder, value: u64) void {
 108         var bytes: [8]u8 = undefined;
 109         std.mem.writeInt(u64, &bytes, value, .little);
 110         self.updateRawBytes(&bytes);
 111     }
 112 
 113     pub fn updateU32(self: *FingerprintBuilder, value: u32) void {
 114         self.updateU64(value);
 115     }
 116 
 117     pub fn updateI64(self: *FingerprintBuilder, value: i64) void {
 118         self.updateU64(@bitCast(value));
 119     }
 120 
 121     pub fn updateUsize(self: *FingerprintBuilder, value: usize) void {
 122         self.updateU64(@intCast(value));
 123     }
 124 
 125     pub fn updateU64Slice(self: *FingerprintBuilder, values: []const u64) void {
 126         self.updateUsize(values.len);
 127         for (values) |value| self.updateU64(value);
 128     }
 129 
 130     pub fn updateI64Slice(self: *FingerprintBuilder, values: []const i64) void {
 131         self.updateUsize(values.len);
 132         for (values) |value| self.updateI64(value);
 133     }
 134 
 135     pub fn updateUsizeSlice(self: *FingerprintBuilder, values: []const usize) void {
 136         self.updateUsize(values.len);
 137         for (values) |value| self.updateUsize(value);
 138     }
 139 
 140     pub fn updateOptionalU64(self: *FingerprintBuilder, value: ?u64) void {
 141         self.updateBool(value != null);
 142         if (value) |payload| self.updateU64(payload);
 143     }
 144 
 145     pub fn updateOptionalU32(self: *FingerprintBuilder, value: ?u32) void {
 146         self.updateBool(value != null);
 147         if (value) |payload| self.updateU32(payload);
 148     }
 149 
 150     pub fn updateOptionalU64Slice(self: *FingerprintBuilder, values: ?[]const u64) void {
 151         self.updateBool(values != null);
 152         if (values) |slice| self.updateU64Slice(slice);
 153     }
 154 
 155     pub fn updateEnumTag(self: *FingerprintBuilder, value: anytype) void {
 156         self.updateBytes(@tagName(value));
 157     }
 158 
 159     pub fn updateOptionalEnumTag(self: *FingerprintBuilder, value: anytype) void {
 160         self.updateBool(value != null);
 161         if (value) |payload| self.updateEnumTag(payload);
 162     }
 163 
 164     pub fn updateStamp(self: *FingerprintBuilder, stamp: ProductStamp) void {
 165         self.updateBytes(stamp.name);
 166         self.updateU64(stamp.fingerprint);
 167     }
 168 
 169     pub fn updateProductRef(self: *FingerprintBuilder, ref: ProductRef) void {
 170         inline for (@typeInfo(ProductRef).@"struct".field_names) |field| {
 171             self.updateBytes(@field(ref, field));
 172         }
 173     }
 174 
 175     pub fn updateProductKey(self: *FingerprintBuilder, key: ProductKey) void {
 176         self.updateProductRef(key.ref);
 177         self.updateBytes(key.record.bytes());
 178     }
 179 
 180     pub fn finish(self: FingerprintBuilder) Fingerprint {
 181         return self.value;
 182     }
 183 };
 184 
 185 pub const ProductStamp = struct {
 186     name: []const u8,
 187     fingerprint: Fingerprint,
 188 
 189     pub fn eql(self: ProductStamp, other: ProductStamp) bool {
 190         return std.mem.eql(u8, self.name, other.name) and self.fingerprint == other.fingerprint;
 191     }
 192 };
 193 
 194 pub const ProductRef = revision.record.Address;
 195 
 196 /// Borrows an owner-interned exact record. Graphs and reports retain it.
 197 /// Equality describes metadata; reuse still requires Builder.admitReuse.
 198 pub const ProductKey = struct {
 199     ref: ProductRef,
 200     record: *const revision.Record,
 201 
 202     pub fn validate(self: ProductKey) error{InvalidProductAddress}!void {
 203         if (!self.ref.eql(self.record.address())) return error.InvalidProductAddress;
 204     }
 205 
 206     pub fn eql(self: ProductKey, other: ProductKey) bool {
 207         return self.ref.eql(other.ref) and self.record.eql(other.record);
 208     }
 209 
 210     pub fn fingerprint(self: ProductKey) Fingerprint {
 211         return self.record.bucket();
 212     }
 213 
 214     pub fn stamp(self: ProductKey) ProductStamp {
 215         return productStamp(self.ref.stage, self.fingerprint());
 216     }
 217 };
 218 
 219 pub const ProductDependency = struct {
 220     dependent: ProductRef,
 221     dependency: ProductRef,
 222 
 223     pub fn eql(self: ProductDependency, other: ProductDependency) bool {
 224         return self.dependent.eql(other.dependent) and self.dependency.eql(other.dependency);
 225     }
 226 };
 227 
 228 pub const ProductRefreshReason = enum {
 229     no_previous_product,
 230     revision_changed,
 231     dependency_changed,
 232 };
 233 
 234 pub const ProductMaterialization = enum {
 235     reusable,
 236     live,
 237 
 238     pub fn merge(self: ProductMaterialization, other: ProductMaterialization) ProductMaterialization {
 239         if (self == .live or other == .live) return .live;
 240         return .reusable;
 241     }
 242 };
 243 
 244 pub const ProductDependencyChange = struct {
 245     ref: ProductRef,
 246     previous_fingerprint: ?Fingerprint = null,
 247     current_fingerprint: ?Fingerprint = null,
 248 };
 249 
 250 pub const ProductRefreshDecision = struct {
 251     key: ProductKey,
 252     refresh: bool,
 253     reason: ?ProductRefreshReason = null,
 254     previous_fingerprint: ?Fingerprint = null,
 255     stale_dependency: ?ProductDependencyChange = null,
 256     materialization: ProductMaterialization = .reusable,
 257 
 258     pub fn isFresh(self: ProductRefreshDecision) bool {
 259         return !self.refresh;
 260     }
 261 
 262     pub fn shouldRefresh(self: ProductRefreshDecision) bool {
 263         return self.refresh;
 264     }
 265 
 266     pub fn isLive(self: ProductRefreshDecision) bool {
 267         return self.materialization == .live;
 268     }
 269 
 270     pub fn merge(self: ProductRefreshDecision, other: ProductRefreshDecision) ProductRefreshDecision {
 271         const materialization = self.materialization.merge(other.materialization);
 272         var result = if (!self.shouldRefresh() and other.shouldRefresh()) other else self;
 273         result.materialization = materialization;
 274         return result;
 275     }
 276 };
 277 
 278 const ProductRefSet = struct {
 279     refs: std.ArrayListUnmanaged(ProductRef) = .empty,
 280 
 281     pub fn deinit(self: *ProductRefSet, allocator: std.mem.Allocator) void {
 282         self.refs.deinit(allocator);
 283         self.* = .{};
 284     }
 285 
 286     pub fn contains(self: ProductRefSet, ref: ProductRef) bool {
 287         return productRefsContain(self.refs.items, ref);
 288     }
 289 
 290     pub fn append(self: *ProductRefSet, allocator: std.mem.Allocator, ref: ProductRef) std.mem.Allocator.Error!void {
 291         if (self.contains(ref)) return;
 292         try self.refs.append(allocator, ref);
 293     }
 294 
 295     pub fn appendSlice(
 296         self: *ProductRefSet,
 297         allocator: std.mem.Allocator,
 298         refs: []const ProductRef,
 299     ) std.mem.Allocator.Error!void {
 300         for (refs) |ref| try self.append(allocator, ref);
 301     }
 302 
 303     pub fn toOwnedSlice(self: *ProductRefSet, allocator: std.mem.Allocator) std.mem.Allocator.Error![]ProductRef {
 304         return try self.refs.toOwnedSlice(allocator);
 305     }
 306 };
 307 
 308 const ProductRefreshDecisionSet = struct {
 309     decisions: std.ArrayListUnmanaged(ProductRefreshDecision) = .empty,
 310 
 311     pub fn deinit(self: *ProductRefreshDecisionSet, allocator: std.mem.Allocator) void {
 312         self.decisions.deinit(allocator);
 313         self.* = .{};
 314     }
 315 
 316     pub fn contains(self: ProductRefreshDecisionSet, ref: ProductRef) bool {
 317         for (self.decisions.items) |decision| {
 318             if (decision.key.ref.eql(ref)) return true;
 319         }
 320         return false;
 321     }
 322 
 323     pub fn append(
 324         self: *ProductRefreshDecisionSet,
 325         allocator: std.mem.Allocator,
 326         decision: ProductRefreshDecision,
 327     ) std.mem.Allocator.Error!void {
 328         for (self.decisions.items) |*existing| {
 329             if (!existing.key.ref.eql(decision.key.ref)) continue;
 330             existing.* = existing.merge(decision);
 331             return;
 332         }
 333         try self.decisions.append(allocator, decision);
 334     }
 335 
 336     pub fn appendSlice(
 337         self: *ProductRefreshDecisionSet,
 338         allocator: std.mem.Allocator,
 339         decisions: []const ProductRefreshDecision,
 340     ) std.mem.Allocator.Error!void {
 341         for (decisions) |decision| try self.append(allocator, decision);
 342     }
 343 
 344     pub fn toOwnedSlice(
 345         self: *ProductRefreshDecisionSet,
 346         allocator: std.mem.Allocator,
 347     ) std.mem.Allocator.Error![]ProductRefreshDecision {
 348         return try self.decisions.toOwnedSlice(allocator);
 349     }
 350 };
 351 
 352 const NameWriter = struct {
 353     bytes: []u8,
 354     cursor: usize = 0,
 355 
 356     fn write(self: *NameWriter, source: []const u8) []const u8 {
 357         const end = std.math.add(usize, self.cursor, source.len) catch unreachable;
 358         std.debug.assert(end <= self.bytes.len);
 359         const destination = self.bytes[self.cursor..end];
 360         @memcpy(destination, source);
 361         self.cursor = end;
 362         return destination;
 363     }
 364 
 365     fn finish(self: NameWriter) void {
 366         std.debug.assert(self.cursor == self.bytes.len);
 367     }
 368 };
 369 
 370 const DecisionStorageRegions = struct {
 371     storage: metadata_storage.Storage,
 372     plan: []ProductRefreshDecision,
 373     closure: []ProductRef,
 374     refresh: []ProductRefreshDecision,
 375     names: []u8,
 376 
 377     fn init(
 378         allocator: std.mem.Allocator,
 379         decision_count: usize,
 380         refresh_count: usize,
 381         name_bytes: usize,
 382     ) ProductMetadataError!DecisionStorageRegions {
 383         std.debug.assert(decision_count > 0);
 384         std.debug.assert(refresh_count <= decision_count);
 385         var storage = try metadata_storage.Storage.init(allocator, .{ .segments = .{
 386             metadata_storage.segment(ProductRefreshDecision, decision_count),
 387             metadata_storage.segment(ProductRef, refresh_count),
 388             metadata_storage.segment(ProductRefreshDecision, refresh_count),
 389             metadata_storage.segment(u8, name_bytes),
 390         } });
 391         errdefer storage.deinit(allocator);
 392         return .{
 393             .plan = storage.region(ProductRefreshDecision, 0, decision_count),
 394             .closure = storage.region(ProductRef, 1, refresh_count),
 395             .refresh = storage.region(ProductRefreshDecision, 2, refresh_count),
 396             .names = storage.region(u8, 3, name_bytes),
 397             .storage = storage,
 398         };
 399     }
 400 };
 401 
 402 fn addNameBytes(total: *usize, name: []const u8) error{CapacityOverflow}!void {
 403     total.* = std.math.add(usize, total.*, name.len) catch return error.CapacityOverflow;
 404 }
 405 
 406 fn addRefBytes(total: *usize, ref: ProductRef) error{CapacityOverflow}!void {
 407     inline for (@typeInfo(ProductRef).@"struct".field_names) |field| {
 408         try addNameBytes(total, @field(ref, field));
 409     }
 410 }
 411 
 412 fn productRefreshDecisionNameBytes(decision: ProductRefreshDecision) error{CapacityOverflow}!usize {
 413     var total: usize = 0;
 414     try addRefBytes(&total, decision.key.ref);
 415     if (decision.stale_dependency) |dependency| try addRefBytes(&total, dependency.ref);
 416     return total;
 417 }
 418 
 419 fn productRefreshDecisionsNameBytes(decisions: []const ProductRefreshDecision) error{CapacityOverflow}!usize {
 420     var total: usize = 0;
 421     for (decisions) |decision| {
 422         total = std.math.add(
 423             usize,
 424             total,
 425             try productRefreshDecisionNameBytes(decision),
 426         ) catch return error.CapacityOverflow;
 427     }
 428     return total;
 429 }
 430 
 431 fn copyProductRef(writer: *NameWriter, source: ProductRef) ProductRef {
 432     var copy: ProductRef = undefined;
 433     inline for (@typeInfo(ProductRef).@"struct".field_names) |field| {
 434         @field(copy, field) = writer.write(@field(source, field));
 435     }
 436     return copy;
 437 }
 438 
 439 fn copyProductKey(writer: *NameWriter, source: ProductKey) ProductMetadataError!ProductKey {
 440     try source.validate();
 441     return .{ .ref = copyProductRef(writer, source.ref), .record = try source.record.retain() };
 442 }
 443 
 444 fn copyProductDependency(writer: *NameWriter, source: ProductDependency) ProductDependency {
 445     return .{
 446         .dependent = copyProductRef(writer, source.dependent),
 447         .dependency = copyProductRef(writer, source.dependency),
 448     };
 449 }
 450 
 451 fn copyProductRefreshDecision(
 452     writer: *NameWriter,
 453     source: ProductRefreshDecision,
 454 ) ProductMetadataError!ProductRefreshDecision {
 455     var destination = source;
 456     destination.key = try copyProductKey(writer, source.key);
 457     if (source.stale_dependency) |dependency| {
 458         var owned_dependency = dependency;
 459         owned_dependency.ref = copyProductRef(writer, dependency.ref);
 460         destination.stale_dependency = owned_dependency;
 461     }
 462     return destination;
 463 }
 464 
 465 fn productRefreshDecisionWithMaterialization(
 466     source: ProductRefreshDecision,
 467     refs: []const ProductRef,
 468     materialization: ProductMaterialization,
 469 ) ProductRefreshDecision {
 470     var destination = source;
 471     if (productRefsContain(refs, source.key.ref)) {
 472         destination.materialization = destination.materialization.merge(materialization);
 473     }
 474     return destination;
 475 }
 476 
 477 pub const ProductRefreshPlan = struct {
 478     decisions: []ProductRefreshDecision = &.{},
 479     storage: ?metadata_storage.Storage = null,
 480 
 481     pub fn init(
 482         allocator: std.mem.Allocator,
 483         decisions: []const ProductRefreshDecision,
 484     ) ProductMetadataError!ProductRefreshPlan {
 485         if (decisions.len == 0) return .{};
 486         const name_bytes = try productRefreshDecisionsNameBytes(decisions);
 487         var regions = try DecisionStorageRegions.init(allocator, decisions.len, 0, name_bytes);
 488         errdefer regions.storage.deinit(allocator);
 489 
 490         var writer = NameWriter{ .bytes = regions.names };
 491         var copied: usize = 0;
 492         errdefer for (regions.plan[0..copied]) |item| item.key.record.release();
 493         for (decisions, regions.plan) |source, *destination| {
 494             destination.* = try copyProductRefreshDecision(&writer, source);
 495             copied += 1;
 496         }
 497         writer.finish();
 498         regions.storage.activate();
 499         return .{
 500             .decisions = regions.plan,
 501             .storage = regions.storage,
 502         };
 503     }
 504 
 505     pub fn deinit(self: *ProductRefreshPlan, allocator: std.mem.Allocator) void {
 506         for (self.decisions) |item| item.key.record.release();
 507         if (self.storage) |*storage| {
 508             storage.deinit(allocator);
 509         } else {
 510             std.debug.assert(self.decisions.len == 0);
 511         }
 512         self.* = .{};
 513     }
 514 
 515     pub fn productCount(self: ProductRefreshPlan) usize {
 516         return self.decisions.len;
 517     }
 518 
 519     pub fn refreshCount(self: ProductRefreshPlan) usize {
 520         var count: usize = 0;
 521         for (self.decisions) |decision| {
 522             if (decision.shouldRefresh()) {
 523                 count = std.math.add(usize, count, 1) catch unreachable;
 524             }
 525         }
 526         return count;
 527     }
 528 
 529     pub fn freshCount(self: ProductRefreshPlan) usize {
 530         return std.math.sub(usize, self.productCount(), self.refreshCount()) catch unreachable;
 531     }
 532 
 533     pub fn materializationCount(self: ProductRefreshPlan, materialization: ProductMaterialization) usize {
 534         var count: usize = 0;
 535         for (self.decisions) |decision| {
 536             if (decision.materialization == materialization) {
 537                 count = std.math.add(usize, count, 1) catch unreachable;
 538             }
 539         }
 540         return count;
 541     }
 542 
 543     pub fn liveCount(self: ProductRefreshPlan) usize {
 544         return self.materializationCount(.live);
 545     }
 546 
 547     pub fn decisionFor(self: ProductRefreshPlan, ref: ProductRef) ?ProductRefreshDecision {
 548         for (self.decisions) |decision| {
 549             if (decision.key.ref.eql(ref)) return decision;
 550         }
 551         return null;
 552     }
 553 
 554     pub fn markMaterialization(
 555         self: *ProductRefreshPlan,
 556         ref: ProductRef,
 557         materialization: ProductMaterialization,
 558     ) bool {
 559         for (self.decisions) |*decision| {
 560             if (!decision.key.ref.eql(ref)) continue;
 561             decision.materialization = decision.materialization.merge(materialization);
 562             return true;
 563         }
 564         return false;
 565     }
 566 
 567     pub fn markMaterializations(
 568         self: *ProductRefreshPlan,
 569         refs: []const ProductRef,
 570         materialization: ProductMaterialization,
 571     ) bool {
 572         for (refs) |ref| {
 573             if (self.decisionFor(ref) == null) return false;
 574         }
 575         for (refs) |ref| {
 576             std.debug.assert(self.markMaterialization(ref, materialization));
 577         }
 578         return true;
 579     }
 580 
 581     pub fn markRefreshMaterialization(
 582         self: *ProductRefreshPlan,
 583         materialization: ProductMaterialization,
 584     ) void {
 585         for (self.decisions) |*decision| {
 586             if (!decision.shouldRefresh()) continue;
 587             decision.materialization = decision.materialization.merge(materialization);
 588         }
 589     }
 590 
 591     pub fn shouldRefresh(self: ProductRefreshPlan, ref: ProductRef) bool {
 592         const decision = self.decisionFor(ref) orelse return false;
 593         return decision.shouldRefresh();
 594     }
 595 
 596     pub fn productsAreFresh(self: ProductRefreshPlan, refs: []const ProductRef) bool {
 597         for (refs) |ref| {
 598             const decision = self.decisionFor(ref) orelse return false;
 599             if (!decision.isFresh()) return false;
 600         }
 601         return true;
 602     }
 603 };
 604 
 605 pub const ProductRefreshReport = struct {
 606     all_decisions: []const ProductRefreshDecision = &.{},
 607     closure: []const ProductRef = &.{},
 608     decisions: []const ProductRefreshDecision = &.{},
 609     storage: ?metadata_storage.Storage = null,
 610 
 611     fn initFromDecisions(
 612         allocator: std.mem.Allocator,
 613         decisions: []const ProductRefreshDecision,
 614     ) ProductMetadataError!ProductRefreshReport {
 615         if (decisions.len == 0) return .{};
 616         var refresh_count: usize = 0;
 617         for (decisions) |decision| {
 618             if (decision.shouldRefresh()) {
 619                 refresh_count = std.math.add(usize, refresh_count, 1) catch unreachable;
 620             }
 621         }
 622         const name_bytes = try productRefreshDecisionsNameBytes(decisions);
 623         var regions = try DecisionStorageRegions.init(
 624             allocator,
 625             decisions.len,
 626             refresh_count,
 627             name_bytes,
 628         );
 629         errdefer regions.storage.deinit(allocator);
 630 
 631         var writer = NameWriter{ .bytes = regions.names };
 632         var copied: usize = 0;
 633         errdefer for (regions.plan[0..copied]) |item| item.key.record.release();
 634         for (decisions, regions.plan) |source, *destination| {
 635             destination.* = try copyProductRefreshDecision(&writer, source);
 636             copied += 1;
 637         }
 638         writer.finish();
 639 
 640         var refresh_index: usize = 0;
 641         for (regions.plan) |decision| {
 642             if (!decision.shouldRefresh()) continue;
 643             std.debug.assert(refresh_index < refresh_count);
 644             regions.closure[refresh_index] = decision.key.ref;
 645             regions.refresh[refresh_index] = decision;
 646             refresh_index = std.math.add(usize, refresh_index, 1) catch unreachable;
 647         }
 648         std.debug.assert(refresh_index == refresh_count);
 649         regions.storage.activate();
 650         return .{
 651             .all_decisions = regions.plan,
 652             .closure = regions.closure,
 653             .decisions = regions.refresh,
 654             .storage = regions.storage,
 655         };
 656     }
 657 
 658     fn initFromGraphDecisions(
 659         allocator: std.mem.Allocator,
 660         current: ProductGraph,
 661         previous: ProductGraph,
 662         materialization_refs: []const ProductRef,
 663         materialization: ProductMaterialization,
 664     ) ProductMetadataError!ProductRefreshReport {
 665         if (current.products.len == 0) return .{};
 666 
 667         var refresh_count: usize = 0;
 668         var name_bytes: usize = 0;
 669         for (current.products) |product| {
 670             const decision = productRefreshDecisionWithMaterialization(
 671                 current.refreshDecision(previous, product),
 672                 materialization_refs,
 673                 materialization,
 674             );
 675             if (decision.shouldRefresh()) {
 676                 refresh_count = std.math.add(usize, refresh_count, 1) catch unreachable;
 677             }
 678             name_bytes = std.math.add(
 679                 usize,
 680                 name_bytes,
 681                 try productRefreshDecisionNameBytes(decision),
 682             ) catch return error.CapacityOverflow;
 683         }
 684 
 685         var regions = try DecisionStorageRegions.init(
 686             allocator,
 687             current.products.len,
 688             refresh_count,
 689             name_bytes,
 690         );
 691         errdefer regions.storage.deinit(allocator);
 692         var writer = NameWriter{ .bytes = regions.names };
 693         var copied: usize = 0;
 694         errdefer for (regions.plan[0..copied]) |item| item.key.record.release();
 695         for (current.products, regions.plan) |product, *destination| {
 696             destination.* = try copyProductRefreshDecision(
 697                 &writer,
 698                 productRefreshDecisionWithMaterialization(
 699                     current.refreshDecision(previous, product),
 700                     materialization_refs,
 701                     materialization,
 702                 ),
 703             );
 704             copied += 1;
 705         }
 706         writer.finish();
 707 
 708         var refresh_index: usize = 0;
 709         for (regions.plan) |decision| {
 710             if (!decision.shouldRefresh()) continue;
 711             std.debug.assert(refresh_index < refresh_count);
 712             regions.closure[refresh_index] = decision.key.ref;
 713             regions.refresh[refresh_index] = decision;
 714             refresh_index = std.math.add(usize, refresh_index, 1) catch unreachable;
 715         }
 716         std.debug.assert(refresh_index == refresh_count);
 717         regions.storage.activate();
 718         return .{
 719             .all_decisions = regions.plan,
 720             .closure = regions.closure,
 721             .decisions = regions.refresh,
 722             .storage = regions.storage,
 723         };
 724     }
 725 
 726     pub fn initFromPlan(
 727         allocator: std.mem.Allocator,
 728         plan: ProductRefreshPlan,
 729     ) ProductMetadataError!ProductRefreshReport {
 730         var owned_plan = plan;
 731         defer owned_plan.deinit(allocator);
 732         return try initFromDecisions(allocator, owned_plan.decisions);
 733     }
 734 
 735     pub fn initFromGraph(
 736         allocator: std.mem.Allocator,
 737         current: ProductGraph,
 738         previous: ProductGraph,
 739     ) ProductMetadataError!ProductRefreshReport {
 740         return try initFromGraphDecisions(allocator, current, previous, &.{}, .reusable);
 741     }
 742 
 743     pub fn initFromReports(
 744         allocator: std.mem.Allocator,
 745         reports: []const *const ProductRefreshReport,
 746     ) ProductMetadataError!ProductRefreshReport {
 747         var closure = ProductRefreshDecisionSet{};
 748         defer closure.deinit(allocator);
 749 
 750         var decision_capacity: usize = 0;
 751         for (reports) |report| {
 752             decision_capacity = std.math.add(
 753                 usize,
 754                 decision_capacity,
 755                 report.all_decisions.len,
 756             ) catch return error.CapacityOverflow;
 757         }
 758         try closure.decisions.ensureTotalCapacityPrecise(allocator, decision_capacity);
 759 
 760         for (reports) |report| {
 761             try closure.appendSlice(allocator, report.all_decisions);
 762         }
 763 
 764         return try initFromDecisions(allocator, closure.decisions.items);
 765     }
 766 
 767     pub fn refreshes(self: ProductRefreshReport, ref: ProductRef) bool {
 768         return productRefsContain(self.closure, ref);
 769     }
 770 
 771     pub fn refreshDecisionFor(self: ProductRefreshReport, ref: ProductRef) ?ProductRefreshDecision {
 772         for (self.decisions) |decision| {
 773             if (decision.key.ref.eql(ref)) return decision;
 774         }
 775         return null;
 776     }
 777 
 778     pub fn decisionFor(self: ProductRefreshReport, ref: ProductRef) ?ProductRefreshDecision {
 779         for (self.all_decisions) |decision| {
 780             if (decision.key.ref.eql(ref)) return decision;
 781         }
 782         return null;
 783     }
 784 
 785     pub fn productsAreFresh(self: ProductRefreshReport, refs: []const ProductRef) bool {
 786         for (refs) |ref| {
 787             const decision = self.decisionFor(ref) orelse return false;
 788             if (!decision.isFresh()) return false;
 789         }
 790         return true;
 791     }
 792 
 793     pub fn productCount(self: ProductRefreshReport) usize {
 794         return self.all_decisions.len;
 795     }
 796 
 797     pub fn refreshCount(self: ProductRefreshReport) usize {
 798         std.debug.assert(self.closure.len == self.decisions.len);
 799         var expected: usize = 0;
 800         for (self.all_decisions) |decision| {
 801             if (decision.shouldRefresh()) {
 802                 expected = std.math.add(usize, expected, 1) catch unreachable;
 803             }
 804         }
 805         std.debug.assert(expected == self.decisions.len);
 806         return self.decisions.len;
 807     }
 808 
 809     pub fn freshCount(self: ProductRefreshReport) usize {
 810         return std.math.sub(usize, self.productCount(), self.refreshCount()) catch unreachable;
 811     }
 812 
 813     pub fn liveCount(self: ProductRefreshReport) usize {
 814         var count: usize = 0;
 815         for (self.all_decisions) |decision| {
 816             if (decision.materialization == .live) {
 817                 count = std.math.add(usize, count, 1) catch unreachable;
 818             }
 819         }
 820         return count;
 821     }
 822 
 823     pub fn hasRefreshes(self: ProductRefreshReport) bool {
 824         return self.refreshCount() != 0;
 825     }
 826 
 827     pub fn refreshReasonsAre(self: ProductRefreshReport, reason: ProductRefreshReason) bool {
 828         for (self.decisions) |decision| {
 829             if (decision.reason == null or decision.reason.? != reason) return false;
 830         }
 831         return true;
 832     }
 833 
 834     pub fn refreshesAreLive(self: ProductRefreshReport) bool {
 835         for (self.decisions) |decision| {
 836             if (!decision.isLive()) return false;
 837         }
 838         return true;
 839     }
 840 
 841     pub fn deinit(self: *ProductRefreshReport, allocator: std.mem.Allocator) void {
 842         for (self.all_decisions) |item| item.key.record.release();
 843         if (self.storage) |*storage| {
 844             storage.deinit(allocator);
 845         } else {
 846             std.debug.assert(self.all_decisions.len == 0);
 847             std.debug.assert(self.closure.len == 0);
 848             std.debug.assert(self.decisions.len == 0);
 849         }
 850         self.* = .{};
 851     }
 852 };
 853 
 854 pub const ProductGraphBuilderError = ProductMetadataError || error{
 855     ConflictingProductKey,
 856 };
 857 
 858 const ProductDependencySliceSource = struct {
 859     dependencies: []const ProductDependency,
 860 
 861     fn get(self: ProductDependencySliceSource, index: usize) ProductDependency {
 862         std.debug.assert(index < self.dependencies.len);
 863         return self.dependencies[index];
 864     }
 865 };
 866 
 867 const LinearProductDependencySource = struct {
 868     products: []const ProductKey,
 869 
 870     fn get(self: LinearProductDependencySource, index: usize) ProductDependency {
 871         const dependency_count = if (self.products.len > 1)
 872             std.math.sub(usize, self.products.len, 1) catch unreachable
 873         else
 874             0;
 875         std.debug.assert(index < dependency_count);
 876         const dependent_index = std.math.add(usize, index, 1) catch unreachable;
 877         return productDependency(self.products[dependent_index], self.products[index]);
 878     }
 879 };
 880 
 881 pub const ProductGraph = struct {
 882     products: []const ProductKey = &.{},
 883     dependencies: []const ProductDependency = &.{},
 884     storage: ?metadata_storage.Storage = null,
 885 
 886     pub fn init(
 887         allocator: std.mem.Allocator,
 888         products: []const ProductKey,
 889         dependencies: []const ProductDependency,
 890     ) ProductMetadataError!ProductGraph {
 891         return try initFromDependencySource(
 892             allocator,
 893             products,
 894             dependencies.len,
 895             ProductDependencySliceSource{ .dependencies = dependencies },
 896         );
 897     }
 898 
 899     fn initFromDependencySource(
 900         allocator: std.mem.Allocator,
 901         products: []const ProductKey,
 902         dependency_count: usize,
 903         dependency_source: anytype,
 904     ) ProductMetadataError!ProductGraph {
 905         if (products.len == 0 and dependency_count == 0) return .{};
 906 
 907         var name_bytes: usize = 0;
 908         for (products) |product| try addRefBytes(&name_bytes, product.ref);
 909         for (0..dependency_count) |index| {
 910             const dependency = dependency_source.get(index);
 911             try addRefBytes(&name_bytes, dependency.dependent);
 912             try addRefBytes(&name_bytes, dependency.dependency);
 913         }
 914 
 915         var storage = try metadata_storage.Storage.init(allocator, .{ .segments = .{
 916             metadata_storage.segment(ProductKey, products.len),
 917             metadata_storage.segment(ProductDependency, dependency_count),
 918             metadata_storage.segment(u8, 0),
 919             metadata_storage.segment(u8, name_bytes),
 920         } });
 921         errdefer storage.deinit(allocator);
 922         const owned_products = storage.region(ProductKey, 0, products.len);
 923         const owned_dependencies = storage.region(ProductDependency, 1, dependency_count);
 924         const names = storage.region(u8, 3, name_bytes);
 925 
 926         var writer = NameWriter{ .bytes = names };
 927         var copied: usize = 0;
 928         errdefer for (owned_products[0..copied]) |item| item.record.release();
 929         for (products, owned_products) |source, *destination| {
 930             destination.* = try copyProductKey(&writer, source);
 931             copied += 1;
 932         }
 933         for (owned_dependencies, 0..) |*destination, index| {
 934             destination.* = copyProductDependency(&writer, dependency_source.get(index));
 935         }
 936         writer.finish();
 937         storage.activate();
 938 
 939         return .{
 940             .products = owned_products,
 941             .dependencies = owned_dependencies,
 942             .storage = storage,
 943         };
 944     }
 945 
 946     pub fn initFromGraphs(
 947         allocator: std.mem.Allocator,
 948         graphs: []const ProductGraph,
 949         dependencies: []const ProductDependency,
 950     ) ProductGraphBuilderError!ProductGraph {
 951         var builder = ProductGraphBuilder{};
 952         defer builder.deinit(allocator);
 953 
 954         for (graphs) |graph_value| try builder.appendGraph(allocator, graph_value);
 955         for (dependencies) |dependency| try builder.recordDependency(allocator, dependency);
 956 
 957         return try builder.graph(allocator);
 958     }
 959 
 960     pub fn initLinear(
 961         allocator: std.mem.Allocator,
 962         products: []const ProductKey,
 963     ) ProductMetadataError!ProductGraph {
 964         const dependency_count = if (products.len > 1)
 965             std.math.sub(usize, products.len, 1) catch unreachable
 966         else
 967             0;
 968         return try initFromDependencySource(
 969             allocator,
 970             products,
 971             dependency_count,
 972             LinearProductDependencySource{ .products = products },
 973         );
 974     }
 975 
 976     pub fn deinit(self: *ProductGraph, allocator: std.mem.Allocator) void {
 977         for (self.products) |item| item.record.release();
 978         if (self.storage) |*storage| {
 979             storage.deinit(allocator);
 980         } else {
 981             std.debug.assert(self.products.len == 0);
 982             std.debug.assert(self.dependencies.len == 0);
 983         }
 984         self.* = .{};
 985     }
 986 
 987     pub fn containsFresh(self: ProductGraph, key: ProductKey) bool {
 988         for (self.products) |product| {
 989             if (product.eql(key)) return true;
 990         }
 991         return false;
 992     }
 993 
 994     pub fn productKeyFor(self: ProductGraph, ref: ProductRef) ?ProductKey {
 995         for (self.products) |product| {
 996             if (product.ref.eql(ref)) return product;
 997         }
 998         return null;
 999     }
1000 
1001     pub fn fingerprintFor(self: ProductGraph, ref: ProductRef) ?Fingerprint {
1002         const product = self.productKeyFor(ref) orelse return null;
1003         return product.fingerprint();
1004     }
1005 
1006     pub fn dependsOn(self: ProductGraph, dependent: ProductRef, dependency_ref: ProductRef) bool {
1007         for (self.dependencies) |dependency| {
1008             if (dependency.dependent.eql(dependent) and dependency.dependency.eql(dependency_ref)) {
1009                 return true;
1010             }
1011         }
1012         return false;
1013     }
1014 
1015     pub fn dependencyCountFor(self: ProductGraph, dependent: ProductRef) usize {
1016         var count: usize = 0;
1017         for (self.dependencies) |dependency| {
1018             if (dependency.dependent.eql(dependent)) {
1019                 count = std.math.add(usize, count, 1) catch unreachable;
1020             }
1021         }
1022         return count;
1023     }
1024 
1025     pub fn refreshDecision(
1026         self: ProductGraph,
1027         previous: ProductGraph,
1028         key: ProductKey,
1029     ) ProductRefreshDecision {
1030         const previous_key = previous.productKeyFor(key.ref) orelse {
1031             return .{
1032                 .key = key,
1033                 .refresh = true,
1034                 .reason = .no_previous_product,
1035             };
1036         };
1037 
1038         const previous_fingerprint = previous_key.fingerprint();
1039         if (!previous_key.eql(key)) {
1040             return .{
1041                 .key = key,
1042                 .refresh = true,
1043                 .reason = .revision_changed,
1044                 .previous_fingerprint = previous_fingerprint,
1045             };
1046         }
1047 
1048         if (self.firstStalePreviousDependency(previous, key.ref)) |dependency| {
1049             return .{
1050                 .key = key,
1051                 .refresh = true,
1052                 .reason = .dependency_changed,
1053                 .previous_fingerprint = previous_fingerprint,
1054                 .stale_dependency = dependency,
1055             };
1056         }
1057 
1058         return .{
1059             .key = key,
1060             .refresh = false,
1061             .previous_fingerprint = previous_fingerprint,
1062         };
1063     }
1064 
1065     pub fn firstStalePreviousDependency(
1066         self: ProductGraph,
1067         previous: ProductGraph,
1068         dependent: ProductRef,
1069     ) ?ProductDependencyChange {
1070         for (previous.dependencies) |dependency| {
1071             if (!dependency.dependent.eql(dependent)) continue;
1072             const before = previous.productKeyFor(dependency.dependency);
1073             const after = self.productKeyFor(dependency.dependency);
1074             if (!self.dependsOn(dependent, dependency.dependency) or
1075                 before == null or after == null or !before.?.eql(after.?))
1076             {
1077                 return dependencyChange(dependency.dependency, before, after);
1078             }
1079         }
1080         for (self.dependencies) |dependency| {
1081             if (!dependency.dependent.eql(dependent)) continue;
1082             if (!previous.dependsOn(dependent, dependency.dependency)) {
1083                 return dependencyChange(
1084                     dependency.dependency,
1085                     previous.productKeyFor(dependency.dependency),
1086                     self.productKeyFor(dependency.dependency),
1087                 );
1088             }
1089         }
1090         return null;
1091     }
1092 
1093     pub fn collectInvalidationClosure(
1094         self: ProductGraph,
1095         allocator: std.mem.Allocator,
1096         changed: ProductRef,
1097     ) std.mem.Allocator.Error![]ProductRef {
1098         var invalidated = ProductRefSet{};
1099         errdefer invalidated.deinit(allocator);
1100 
1101         try invalidated.append(allocator, changed);
1102         var cursor: usize = 0;
1103         while (cursor < invalidated.refs.items.len) : (cursor = std.math.add(usize, cursor, 1) catch unreachable) {
1104             const current = invalidated.refs.items[cursor];
1105             for (self.dependencies) |dependency| {
1106                 if (!dependency.dependency.eql(current)) continue;
1107                 try invalidated.append(allocator, dependency.dependent);
1108             }
1109         }
1110 
1111         return try invalidated.toOwnedSlice(allocator);
1112     }
1113 
1114     pub fn collectRefreshReport(
1115         self: ProductGraph,
1116         allocator: std.mem.Allocator,
1117         previous: ProductGraph,
1118     ) ProductMetadataError!ProductRefreshReport {
1119         return try ProductRefreshReport.initFromGraph(allocator, self, previous);
1120     }
1121 
1122     pub fn collectRetainedRefreshReport(
1123         self: ProductGraph,
1124         allocator: std.mem.Allocator,
1125     ) ProductMetadataError!ProductRefreshReport {
1126         return try self.collectRefreshReport(allocator, self);
1127     }
1128 
1129     pub fn collectRefreshReportWithMaterialization(
1130         self: ProductGraph,
1131         allocator: std.mem.Allocator,
1132         previous: ProductGraph,
1133         refs: []const ProductRef,
1134         materialization: ProductMaterialization,
1135     ) (ProductMetadataError || error{MissingMaterializationProduct})!ProductRefreshReport {
1136         for (refs) |ref| {
1137             if (self.productKeyFor(ref) == null) return error.MissingMaterializationProduct;
1138         }
1139         return try ProductRefreshReport.initFromGraphDecisions(
1140             allocator,
1141             self,
1142             previous,
1143             refs,
1144             materialization,
1145         );
1146     }
1147 
1148     pub fn collectRetainedRefreshReportWithMaterialization(
1149         self: ProductGraph,
1150         allocator: std.mem.Allocator,
1151         refs: []const ProductRef,
1152         materialization: ProductMaterialization,
1153     ) (ProductMetadataError || error{MissingMaterializationProduct})!ProductRefreshReport {
1154         return try self.collectRefreshReportWithMaterialization(
1155             allocator,
1156             self,
1157             refs,
1158             materialization,
1159         );
1160     }
1161 
1162     pub fn collectRefreshPlan(
1163         self: ProductGraph,
1164         allocator: std.mem.Allocator,
1165         previous: ProductGraph,
1166     ) ProductMetadataError!ProductRefreshPlan {
1167         if (self.products.len == 0) return .{};
1168         var name_bytes: usize = 0;
1169         for (self.products) |product| {
1170             const decision = self.refreshDecision(previous, product);
1171             name_bytes = std.math.add(
1172                 usize,
1173                 name_bytes,
1174                 try productRefreshDecisionNameBytes(decision),
1175             ) catch return error.CapacityOverflow;
1176         }
1177 
1178         var regions = try DecisionStorageRegions.init(allocator, self.products.len, 0, name_bytes);
1179         errdefer regions.storage.deinit(allocator);
1180         var writer = NameWriter{ .bytes = regions.names };
1181         var copied: usize = 0;
1182         errdefer for (regions.plan[0..copied]) |item| item.key.record.release();
1183         for (self.products, regions.plan) |product, *decision| {
1184             decision.* = try copyProductRefreshDecision(
1185                 &writer,
1186                 self.refreshDecision(previous, product),
1187             );
1188             copied += 1;
1189         }
1190         writer.finish();
1191         regions.storage.activate();
1192         return .{
1193             .decisions = regions.plan,
1194             .storage = regions.storage,
1195         };
1196     }
1197 };
1198 
1199 pub const ProductGraphBuilder = struct {
1200     products: std.ArrayListUnmanaged(ProductKey) = .empty,
1201     dependencies: std.ArrayListUnmanaged(ProductDependency) = .empty,
1202 
1203     pub fn deinit(self: *ProductGraphBuilder, allocator: std.mem.Allocator) void {
1204         self.products.deinit(allocator);
1205         self.dependencies.deinit(allocator);
1206         self.* = .{};
1207     }
1208 
1209     pub fn recordProduct(
1210         self: *ProductGraphBuilder,
1211         allocator: std.mem.Allocator,
1212         key: ProductKey,
1213     ) ProductGraphBuilderError!void {
1214         try key.validate();
1215         for (self.products.items) |product| {
1216             if (!product.ref.eql(key.ref)) continue;
1217             if (!product.eql(key)) return error.ConflictingProductKey;
1218             return;
1219         }
1220         try self.products.append(allocator, key);
1221     }
1222 
1223     pub fn recordDependency(
1224         self: *ProductGraphBuilder,
1225         allocator: std.mem.Allocator,
1226         dependency: ProductDependency,
1227     ) std.mem.Allocator.Error!void {
1228         for (self.dependencies.items) |candidate| {
1229             if (candidate.eql(dependency)) return;
1230         }
1231         try self.dependencies.append(allocator, dependency);
1232     }
1233 
1234     pub fn appendGraph(
1235         self: *ProductGraphBuilder,
1236         allocator: std.mem.Allocator,
1237         source_graph: ProductGraph,
1238     ) ProductGraphBuilderError!void {
1239         for (source_graph.products) |product| try self.recordProduct(allocator, product);
1240         for (source_graph.dependencies) |dependency| try self.recordDependency(allocator, dependency);
1241     }
1242 
1243     pub fn graph(
1244         self: ProductGraphBuilder,
1245         allocator: std.mem.Allocator,
1246     ) ProductMetadataError!ProductGraph {
1247         return try ProductGraph.init(allocator, self.products.items, self.dependencies.items);
1248     }
1249 };
1250 
1251 pub fn fingerprintBytes(bytes: []const u8) Fingerprint {
1252     var builder = FingerprintBuilder{};
1253     builder.updateBytes(bytes);
1254     return builder.finish();
1255 }
1256 
1257 pub fn productStamp(name: []const u8, fingerprint: Fingerprint) ProductStamp {
1258     return .{
1259         .name = name,
1260         .fingerprint = fingerprint,
1261     };
1262 }
1263 
1264 pub fn productRef(
1265     producer: []const u8,
1266     source: []const u8,
1267     stage: []const u8,
1268     variant: []const u8,
1269 ) ProductRef {
1270     return .{ .producer = producer, .source = source, .stage = stage, .variant = variant };
1271 }
1272 
1273 pub fn cloneProductRef(allocator: std.mem.Allocator, ref: ProductRef) std.mem.Allocator.Error!ProductRef {
1274     const fields = @typeInfo(ProductRef).@"struct".field_names;
1275     var result: ProductRef = undefined;
1276     var count: usize = 0;
1277     errdefer inline for (fields, 0..) |field, index| {
1278         if (index < count) allocator.free(@field(result, field));
1279     };
1280     inline for (fields) |field| {
1281         @field(result, field) = try allocator.dupe(u8, @field(ref, field));
1282         count += 1;
1283     }
1284     return result;
1285 }
1286 
1287 pub fn deinitProductRef(allocator: std.mem.Allocator, ref: ProductRef) void {
1288     inline for (@typeInfo(ProductRef).@"struct".field_names) |field| {
1289         allocator.free(@field(ref, field));
1290     }
1291 }
1292 
1293 pub fn productKey(exact: *const revision.Record) ProductKey {
1294     return .{ .ref = exact.address(), .record = exact };
1295 }
1296 
1297 pub fn cloneProductKey(_: std.mem.Allocator, key: ProductKey) ProductMetadataError!ProductKey {
1298     try key.validate();
1299     return productKey(try key.record.retain());
1300 }
1301 
1302 pub fn deinitProductKey(_: std.mem.Allocator, key: ProductKey) void {
1303     key.record.release();
1304 }
1305 
1306 fn dependencyChange(
1307     ref: ProductRef,
1308     before: ?ProductKey,
1309     after: ?ProductKey,
1310 ) ProductDependencyChange {
1311     return .{
1312         .ref = ref,
1313         .previous_fingerprint = if (before) |key| key.fingerprint() else null,
1314         .current_fingerprint = if (after) |key| key.fingerprint() else null,
1315     };
1316 }
1317 
1318 pub fn derivedProductStamp(
1319     name: []const u8,
1320     dependencies: []const ProductStamp,
1321     local_fingerprint: Fingerprint,
1322 ) ProductStamp {
1323     var builder = FingerprintBuilder{};
1324     builder.updateBytes(name);
1325     builder.updateU64(local_fingerprint);
1326     builder.updateUsize(dependencies.len);
1327     for (dependencies) |dependency| builder.updateStamp(dependency);
1328     return productStamp(name, builder.finish());
1329 }
1330 
1331 pub fn productDependency(
1332     dependent: ProductKey,
1333     dependency: ProductKey,
1334 ) ProductDependency {
1335     return .{
1336         .dependent = dependent.ref,
1337         .dependency = dependency.ref,
1338     };
1339 }
1340 
1341 pub fn productRefsContain(refs: []const ProductRef, ref: ProductRef) bool {
1342     for (refs) |candidate| {
1343         if (candidate.eql(ref)) return true;
1344     }
1345     return false;
1346 }
1347 
1348 test "fingerprint builder is deterministic and length delimited" {
1349     var left = FingerprintBuilder{};
1350     left.updateBytes("ab");
1351     left.updateBytes("c");
1352 
1353     var right = FingerprintBuilder{};
1354     right.updateBytes("a");
1355     right.updateBytes("bc");
1356 
1357     try std.testing.expectEqual(left.finish(), left.finish());
1358     try std.testing.expect(left.finish() != right.finish());
1359 }
1360 
1361 test "fingerprint builder delimits numeric slices and optionals" {
1362     var left = FingerprintBuilder{};
1363     left.updateU64Slice(&.{ 1, 23 });
1364 
1365     var right = FingerprintBuilder{};
1366     right.updateU64Slice(&.{ 12, 3 });
1367 
1368     var empty = FingerprintBuilder{};
1369     empty.updateOptionalU64Slice(&.{});
1370 
1371     var missing = FingerprintBuilder{};
1372     missing.updateOptionalU64Slice(null);
1373 
1374     var negative = FingerprintBuilder{};
1375     negative.updateI64(-1);
1376 
1377     var positive = FingerprintBuilder{};
1378     positive.updateI64(1);
1379 
1380     try std.testing.expect(left.finish() != right.finish());
1381     try std.testing.expect(empty.finish() != missing.finish());
1382     try std.testing.expect(negative.finish() != positive.finish());
1383 }
1384 
1385 test "fingerprint builder delimits optional u32 and enum tags" {
1386     const Mode = enum { alpha, beta };
1387 
1388     var present_u32 = FingerprintBuilder{};
1389     present_u32.updateOptionalU32(7);
1390 
1391     var missing_u32 = FingerprintBuilder{};
1392     missing_u32.updateOptionalU32(null);
1393 
1394     var alpha = FingerprintBuilder{};
1395     alpha.updateOptionalEnumTag(@as(?Mode, .alpha));
1396 
1397     var beta = FingerprintBuilder{};
1398     beta.updateOptionalEnumTag(@as(?Mode, .beta));
1399 
1400     var missing_enum = FingerprintBuilder{};
1401     missing_enum.updateOptionalEnumTag(@as(?Mode, null));
1402 
1403     try std.testing.expect(present_u32.finish() != missing_u32.finish());
1404     try std.testing.expect(alpha.finish() != beta.finish());
1405     try std.testing.expect(alpha.finish() != missing_enum.finish());
1406 }
1407 
1408 test "product stamps include product name and dependencies" {
1409     const source = productStamp("source", fingerprintBytes("module"));
1410     const same = derivedProductStamp("target", &.{source}, 1);
1411     const same_again = derivedProductStamp("target", &.{source}, 1);
1412     const different_name = derivedProductStamp("artifact", &.{source}, 1);
1413     const different_local = derivedProductStamp("target", &.{source}, 2);
1414 
1415     try std.testing.expect(same.eql(same_again));
1416     try std.testing.expect(!same.eql(different_name));
1417     try std.testing.expect(!same.eql(different_local));
1418 }
1419 
1420 const Fixture = struct {
1421     owner: *revision.Store,
1422 
1423     fn init() !Fixture {
1424         return .{ .owner = try fixtureStore() };
1425     }
1426 
1427     fn deinit(self: Fixture) void {
1428         self.owner.release();
1429     }
1430 
1431     fn key(self: Fixture, stage: []const u8, image: []const u8) !ProductKey {
1432         const exact = try fixtureRecord(self.owner, stage, image, "");
1433         exact.release();
1434         return productKey(exact);
1435     }
1436 };
1437 
1438 test "exact product graphs retain records and full addresses across store destruction" {
1439     comptime {
1440         @stardustClaim(@import("alloc_phase").capacity.witness(metadata_storage.Storage, "choir_product_graph_lifetime_transitive_risk"), null, null, null, null, null, null);
1441         @stardustClaim(@import("alloc_phase").capacity.witness(metadata_storage.Storage, "choir_product_graph_lifetime_foreign_risk"), null, null, null, null, null, null);
1442     }
1443     const allocator = std.testing.allocator;
1444     const fixture = try Fixture.init();
1445     const source = try fixture.key("source", "source-v1");
1446     const target = try fixture.key("target", "target-v1");
1447     var initial = try ProductGraph.initLinear(allocator, &.{ source, target });
1448     fixture.deinit();
1449     var copy = try ProductGraph.initFromGraphs(allocator, &.{initial}, &.{});
1450     defer copy.deinit(allocator);
1451     initial.deinit(allocator);
1452     const independent = try Fixture.init();
1453     defer independent.deinit();
1454     const equal = try independent.key("source", "source-v1");
1455     try std.testing.expect(copy.containsFresh(equal));
1456     try std.testing.expect(copy.dependsOn(target.ref, source.ref));
1457     try std.testing.expectEqualStrings("graph-fixture", copy.products[0].ref.producer);
1458     try std.testing.expectEqualStrings("module", copy.products[0].ref.source);
1459     try std.testing.expectEqualStrings("default", copy.products[0].ref.variant);
1460 }
1461 
1462 test "exact product graph changes follow records and both dependency edge directions" {
1463     const allocator = std.testing.allocator;
1464     const fixture = try Fixture.init();
1465     defer fixture.deinit();
1466     const source = try fixture.key("source", "v1");
1467     const changed = try fixture.key("source", "v2");
1468     const target = try fixture.key("target", "v1");
1469     var before = try ProductGraph.initLinear(allocator, &.{ source, target });
1470     defer before.deinit(allocator);
1471     var after = try ProductGraph.initLinear(allocator, &.{ changed, target });
1472     defer after.deinit(allocator);
1473     try std.testing.expectEqual(ProductRefreshReason.revision_changed, after.refreshDecision(before, changed).reason.?);
1474     const target_change = after.refreshDecision(before, target);
1475     try std.testing.expectEqual(ProductRefreshReason.dependency_changed, target_change.reason.?);
1476     try std.testing.expect(target_change.stale_dependency.?.ref.eql(source.ref));
1477     var detached = try ProductGraph.init(allocator, &.{ source, target }, &.{});
1478     defer detached.deinit(allocator);
1479     try std.testing.expect(detached.refreshDecision(before, target).shouldRefresh());
1480     try std.testing.expect(before.refreshDecision(detached, target).shouldRefresh());
1481     try std.testing.expectEqual(ProductRefreshReason.no_previous_product, before.refreshDecision(.{}, target).reason.?);
1482 }
1483 
1484 test "exact product reports retain records after graphs and stores are released" {
1485     comptime {
1486         @stardustClaim(@import("alloc_phase").capacity.witness(metadata_storage.Storage, "choir_product_refresh_lifetime"), null, null, null, null, null, null);
1487         @stardustClaim(@import("alloc_phase").capacity.witness(metadata_storage.Storage, "choir_product_report_composition_lifetime"), null, null, null, null, null, null);
1488     }
1489     const allocator = std.testing.allocator;
1490     const fixture = try Fixture.init();
1491     const source = try fixture.key("source", "v1");
1492     const changed = try fixture.key("source", "v2");
1493     const target = try fixture.key("target", "v1");
1494     var before = try ProductGraph.initLinear(allocator, &.{ source, target });
1495     var after = try ProductGraph.initLinear(allocator, &.{ changed, target });
1496     var plan = try after.collectRefreshPlan(allocator, before);
1497     before.deinit(allocator);
1498     after.deinit(allocator);
1499     fixture.deinit();
1500     plan.markRefreshMaterialization(.live);
1501     var report = try ProductRefreshReport.initFromPlan(allocator, plan);
1502     var composed = try ProductRefreshReport.initFromReports(allocator, &.{&report});
1503     defer composed.deinit(allocator);
1504     report.deinit(allocator);
1505     try std.testing.expectEqual(@as(usize, 2), composed.refreshCount());
1506     try std.testing.expectEqual(@as(usize, 2), composed.liveCount());
1507     try std.testing.expect(composed.refreshes(target.ref));
1508     try std.testing.expectEqualStrings("v2", composed.decisionFor(source.ref).?.key.record.view().image);
1509 }
1510 
1511 test "exact product graph summaries cannot authorize reuse of restored metadata" {
1512     const allocator = std.testing.allocator;
1513     const first = try Fixture.init();
1514     defer first.deinit();
1515     const restored = try Fixture.init();
1516     defer restored.deinit();
1517     const key = try first.key("source", "v1");
1518     const equal = try restored.key("source", "v1");
1519     var before = try ProductGraph.init(allocator, &.{key}, &.{});
1520     defer before.deinit(allocator);
1521     var after = try ProductGraph.init(allocator, &.{equal}, &.{});
1522     defer after.deinit(allocator);
1523     var report = try after.collectRefreshReport(allocator, before);
1524     defer report.deinit(allocator);
1525     try std.testing.expect(report.productsAreFresh(&.{key.ref}));
1526     try std.testing.expectEqual(@as(u32, 0), restored.owner.publicationCount());
1527     try std.testing.expect(!@hasDecl(revision.Record, "entity"));
1528     try std.testing.expect(!@hasDecl(revision.Record, "requireGates"));
1529 }
1530 
1531 test "exact product graph composes fragments and rejects conflicting records" {
1532     const allocator = std.testing.allocator;
1533     const fixture = try Fixture.init();
1534     defer fixture.deinit();
1535     const source = try fixture.key("source", "v1");
1536     const target = try fixture.key("target", "v1");
1537     const changed = try fixture.key("target", "v2");
1538     var first = try ProductGraph.init(allocator, &.{source}, &.{});
1539     defer first.deinit(allocator);
1540     var second = try ProductGraph.init(allocator, &.{target}, &.{});
1541     defer second.deinit(allocator);
1542     var conflict = try ProductGraph.init(allocator, &.{changed}, &.{});
1543     defer conflict.deinit(allocator);
1544     var joined = try ProductGraph.initFromGraphs(allocator, &.{ first, second }, &.{
1545         productDependency(target, source), productDependency(target, source),
1546     });
1547     defer joined.deinit(allocator);
1548     try std.testing.expectEqual(@as(usize, 2), joined.products.len);
1549     try std.testing.expectEqual(@as(usize, 1), joined.dependencies.len);
1550     try std.testing.expectError(error.ConflictingProductKey, ProductGraph.initFromGraphs(allocator, &.{ second, conflict }, &.{}));
1551     var invalid = source;
1552     invalid.ref.stage = "not-the-record-address";
1553     try std.testing.expectError(error.InvalidProductAddress, ProductGraph.init(allocator, &.{invalid}, &.{}));
1554 }
1555 
1556 test "exact product graph refresh selections and materialization stay descriptive" {
1557     const allocator = std.testing.allocator;
1558     const fixture = try Fixture.init();
1559     defer fixture.deinit();
1560     const source = try fixture.key("source", "v1");
1561     const target = try fixture.key("target", "v1");
1562     const absent = try fixture.key("absent", "v1");
1563     var graph = try ProductGraph.initLinear(allocator, &.{ source, target });
1564     defer graph.deinit(allocator);
1565     var retained = try graph.collectRetainedRefreshReportWithMaterialization(allocator, &.{source.ref}, .live);
1566     defer retained.deinit(allocator);
1567     try std.testing.expectEqual(@as(usize, 2), retained.freshCount());
1568     try std.testing.expectEqual(@as(usize, 1), retained.liveCount());
1569     try std.testing.expect(!retained.hasRefreshes());
1570     try std.testing.expect(!retained.productsAreFresh(&.{absent.ref}));
1571     try std.testing.expectError(error.MissingMaterializationProduct, graph.collectRefreshReportWithMaterialization(allocator, .{}, &.{absent.ref}, .live));
1572     var plan = try graph.collectRefreshPlan(allocator, .{});
1573     defer plan.deinit(allocator);
1574     try std.testing.expect(plan.markMaterializations(&.{ source.ref, target.ref }, .live));
1575     try std.testing.expect(!plan.markMaterializations(&.{ source.ref, absent.ref }, .live));
1576     try std.testing.expectEqual(@as(usize, 2), plan.liveCount());
1577     const closure = try graph.collectInvalidationClosure(allocator, source.ref);
1578     defer allocator.free(closure);
1579     try std.testing.expect(productRefsContain(closure, target.ref));
1580 }
1581 
1582 test "exact product metadata acquires one local region and retains external records" {
1583     comptime {
1584         @stardustClaim(@import("alloc_phase").capacity.witness(metadata_storage.Storage, "choir_product_metadata_integration"), null, null, null, null, null, null);
1585     }
1586     const fixture = try Fixture.init();
1587     defer fixture.deinit();
1588     const key = try fixture.key("source", "v1");
1589     const decisions = [_]ProductRefreshDecision{.{ .key = key, .refresh = true }};
1590     var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
1591     var graph = try ProductGraph.init(failing.allocator(), &.{key}, &.{});
1592     try std.testing.expectEqual(@as(usize, 1), failing.alloc_index);
1593     graph.deinit(failing.allocator());
1594     var plan = try ProductRefreshPlan.init(failing.allocator(), &decisions);
1595     try std.testing.expectEqual(@as(usize, 2), failing.alloc_index);
1596     plan.deinit(failing.allocator());
1597     var report = try ProductRefreshReport.initFromDecisions(failing.allocator(), &decisions);
1598     try std.testing.expectEqual(@as(usize, 3), failing.alloc_index);
1599     report.deinit(failing.allocator());
1600     const changed = try fixture.key("source", "v2");
1601     const target = try fixture.key("target", "v1");
1602     var before = try ProductGraph.initLinear(std.testing.allocator, &.{ key, target });
1603     defer before.deinit(std.testing.allocator);
1604 
1605     var graph_allocator = std.testing.FailingAllocator.init(std.testing.allocator, .{});
1606     var after = try ProductGraph.init(graph_allocator.allocator(), &.{ changed, target }, &.{productDependency(target, changed)});
1607     defer after.deinit(graph_allocator.allocator());
1608     try std.testing.expectEqual(@as(usize, 1), graph_allocator.alloc_index);
1609     try std.testing.expect(after.dependsOn(target.ref, changed.ref));
1610 
1611     const changed_decisions = [_]ProductRefreshDecision{
1612         after.refreshDecision(before, changed),
1613         after.refreshDecision(before, target),
1614     };
1615     try std.testing.expectEqual(ProductRefreshReason.dependency_changed, changed_decisions[1].reason.?);
1616     try std.testing.expect(changed_decisions[1].stale_dependency.?.ref.eql(key.ref));
1617 
1618     var plan_allocator = std.testing.FailingAllocator.init(std.testing.allocator, .{});
1619     var changed_plan = try ProductRefreshPlan.init(plan_allocator.allocator(), &changed_decisions);
1620     defer changed_plan.deinit(plan_allocator.allocator());
1621     try std.testing.expectEqual(@as(usize, 1), plan_allocator.alloc_index);
1622 
1623     var report_allocator = std.testing.FailingAllocator.init(std.testing.allocator, .{});
1624     var changed_report = try ProductRefreshReport.initFromDecisions(report_allocator.allocator(), &changed_decisions);
1625     defer changed_report.deinit(report_allocator.allocator());
1626     try std.testing.expectEqual(@as(usize, 1), report_allocator.alloc_index);
1627 }
1628 
1629 fn graphAllocationScenario(allocator: std.mem.Allocator, keys: []const ProductKey) !void {
1630     var current = try ProductGraph.initLinear(allocator, keys);
1631     defer current.deinit(allocator);
1632     var plan = try current.collectRefreshPlan(allocator, .{});
1633     defer plan.deinit(allocator);
1634     var report = try current.collectRefreshReport(allocator, .{});
1635     defer report.deinit(allocator);
1636     var composed = try ProductRefreshReport.initFromReports(allocator, &.{&report});
1637     defer composed.deinit(allocator);
1638 }
1639 
1640 test "exact product metadata releases retained prefixes at every allocation failure" {
1641     const fixture = try Fixture.init();
1642     defer fixture.deinit();
1643     const source = try fixture.key("source", "v1");
1644     const target = try fixture.key("target", "v1");
1645     const keys = [_]ProductKey{ source, target };
1646     try std.testing.checkAllAllocationFailures(std.testing.allocator, graphAllocationScenario, .{@as([]const ProductKey, &keys)});
1647 }
1648 
1649 test "exact product empty metadata allocates nothing and rejects byte count overflow" {
1650     var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
1651     var graph = try ProductGraph.init(failing.allocator(), &.{}, &.{});
1652     var plan = try ProductRefreshPlan.init(failing.allocator(), &.{});
1653     var report = try ProductRefreshReport.initFromDecisions(failing.allocator(), &.{});
1654     report.deinit(failing.allocator());
1655     plan.deinit(failing.allocator());
1656     graph.deinit(failing.allocator());
1657     try std.testing.expectEqual(@as(usize, 0), failing.alloc_index);
1658     var total: usize = std.math.maxInt(usize);
1659     try std.testing.expectError(error.CapacityOverflow, addNameBytes(&total, "x"));
1660 }