tiny.choir.product.incremental

1const std = @import("std");2const metadata_storage = @import("storage.zig");3const revision = @import("root.zig").revision;45fn 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}1718fn 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}2627fn 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}5859test "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}7778pub const ProductMetadataError = std.mem.Allocator.Error || error{ CapacityOverflow, ReferenceOverflow, InvalidProductAddress };7980pub const Fingerprint = u64;8182pub const FingerprintBuilder = struct {83    value: Fingerprint = fnv_offset,8485    const fnv_offset: Fingerprint = 14_695_981_039_346_656_037;86    const fnv_prime: Fingerprint = 1_099_511_628_211;8788    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    }9596    pub fn updateRawBytes(self: *FingerprintBuilder, bytes: []const u8) void {97        for (bytes) |byte| {98            self.value ^= byte;99            self.value *%= fnv_prime;100        }101    }102103    pub fn updateBool(self: *FingerprintBuilder, value: bool) void {104        self.updateU64(@intFromBool(value));105    }106107    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    }112113    pub fn updateU32(self: *FingerprintBuilder, value: u32) void {114        self.updateU64(value);115    }116117    pub fn updateI64(self: *FingerprintBuilder, value: i64) void {118        self.updateU64(@bitCast(value));119    }120121    pub fn updateUsize(self: *FingerprintBuilder, value: usize) void {122        self.updateU64(@intCast(value));123    }124125    pub fn updateU64Slice(self: *FingerprintBuilder, values: []const u64) void {126        self.updateUsize(values.len);127        for (values) |value| self.updateU64(value);128    }129130    pub fn updateI64Slice(self: *FingerprintBuilder, values: []const i64) void {131        self.updateUsize(values.len);132        for (values) |value| self.updateI64(value);133    }134135    pub fn updateUsizeSlice(self: *FingerprintBuilder, values: []const usize) void {136        self.updateUsize(values.len);137        for (values) |value| self.updateUsize(value);138    }139140    pub fn updateOptionalU64(self: *FingerprintBuilder, value: ?u64) void {141        self.updateBool(value != null);142        if (value) |payload| self.updateU64(payload);143    }144145    pub fn updateOptionalU32(self: *FingerprintBuilder, value: ?u32) void {146        self.updateBool(value != null);147        if (value) |payload| self.updateU32(payload);148    }149150    pub fn updateOptionalU64Slice(self: *FingerprintBuilder, values: ?[]const u64) void {151        self.updateBool(values != null);152        if (values) |slice| self.updateU64Slice(slice);153    }154155    pub fn updateEnumTag(self: *FingerprintBuilder, value: anytype) void {156        self.updateBytes(@tagName(value));157    }158159    pub fn updateOptionalEnumTag(self: *FingerprintBuilder, value: anytype) void {160        self.updateBool(value != null);161        if (value) |payload| self.updateEnumTag(payload);162    }163164    pub fn updateStamp(self: *FingerprintBuilder, stamp: ProductStamp) void {165        self.updateBytes(stamp.name);166        self.updateU64(stamp.fingerprint);167    }168169    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    }174175    pub fn updateProductKey(self: *FingerprintBuilder, key: ProductKey) void {176        self.updateProductRef(key.ref);177        self.updateBytes(key.record.bytes());178    }179180    pub fn finish(self: FingerprintBuilder) Fingerprint {181        return self.value;182    }183};184185pub const ProductStamp = struct {186    name: []const u8,187    fingerprint: Fingerprint,188189    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};193194pub const ProductRef = revision.record.Address;195196/// Borrows an owner-interned exact record. Graphs and reports retain it.197/// Equality describes metadata; reuse still requires Builder.admitReuse.198pub const ProductKey = struct {199    ref: ProductRef,200    record: *const revision.Record,201202    pub fn validate(self: ProductKey) error{InvalidProductAddress}!void {203        if (!self.ref.eql(self.record.address())) return error.InvalidProductAddress;204    }205206    pub fn eql(self: ProductKey, other: ProductKey) bool {207        return self.ref.eql(other.ref) and self.record.eql(other.record);208    }209210    pub fn fingerprint(self: ProductKey) Fingerprint {211        return self.record.bucket();212    }213214    pub fn stamp(self: ProductKey) ProductStamp {215        return productStamp(self.ref.stage, self.fingerprint());216    }217};218219pub const ProductDependency = struct {220    dependent: ProductRef,221    dependency: ProductRef,222223    pub fn eql(self: ProductDependency, other: ProductDependency) bool {224        return self.dependent.eql(other.dependent) and self.dependency.eql(other.dependency);225    }226};227228pub const ProductRefreshReason = enum {229    no_previous_product,230    revision_changed,231    dependency_changed,232};233234pub const ProductMaterialization = enum {235    reusable,236    live,237238    pub fn merge(self: ProductMaterialization, other: ProductMaterialization) ProductMaterialization {239        if (self == .live or other == .live) return .live;240        return .reusable;241    }242};243244pub const ProductDependencyChange = struct {245    ref: ProductRef,246    previous_fingerprint: ?Fingerprint = null,247    current_fingerprint: ?Fingerprint = null,248};249250pub 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,257258    pub fn isFresh(self: ProductRefreshDecision) bool {259        return !self.refresh;260    }261262    pub fn shouldRefresh(self: ProductRefreshDecision) bool {263        return self.refresh;264    }265266    pub fn isLive(self: ProductRefreshDecision) bool {267        return self.materialization == .live;268    }269270    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};277278const ProductRefSet = struct {279    refs: std.ArrayListUnmanaged(ProductRef) = .empty,280281    pub fn deinit(self: *ProductRefSet, allocator: std.mem.Allocator) void {282        self.refs.deinit(allocator);283        self.* = .{};284    }285286    pub fn contains(self: ProductRefSet, ref: ProductRef) bool {287        return productRefsContain(self.refs.items, ref);288    }289290    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    }294295    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    }302303    pub fn toOwnedSlice(self: *ProductRefSet, allocator: std.mem.Allocator) std.mem.Allocator.Error![]ProductRef {304        return try self.refs.toOwnedSlice(allocator);305    }306};307308const ProductRefreshDecisionSet = struct {309    decisions: std.ArrayListUnmanaged(ProductRefreshDecision) = .empty,310311    pub fn deinit(self: *ProductRefreshDecisionSet, allocator: std.mem.Allocator) void {312        self.decisions.deinit(allocator);313        self.* = .{};314    }315316    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    }322323    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    }335336    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    }343344    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};351352const NameWriter = struct {353    bytes: []u8,354    cursor: usize = 0,355356    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    }364365    fn finish(self: NameWriter) void {366        std.debug.assert(self.cursor == self.bytes.len);367    }368};369370const DecisionStorageRegions = struct {371    storage: metadata_storage.Storage,372    plan: []ProductRefreshDecision,373    closure: []ProductRef,374    refresh: []ProductRefreshDecision,375    names: []u8,376377    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};401402fn addNameBytes(total: *usize, name: []const u8) error{CapacityOverflow}!void {403    total.* = std.math.add(usize, total.*, name.len) catch return error.CapacityOverflow;404}405406fn 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}411412fn 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}418419fn 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}430431fn 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}438439fn copyProductKey(writer: *NameWriter, source: ProductKey) ProductMetadataError!ProductKey {440    try source.validate();441    return .{ .ref = copyProductRef(writer, source.ref), .record = try source.record.retain() };442}443444fn copyProductDependency(writer: *NameWriter, source: ProductDependency) ProductDependency {445    return .{446        .dependent = copyProductRef(writer, source.dependent),447        .dependency = copyProductRef(writer, source.dependency),448    };449}450451fn 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}464465fn 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}476477pub const ProductRefreshPlan = struct {478    decisions: []ProductRefreshDecision = &.{},479    storage: ?metadata_storage.Storage = null,480481    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);489490        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    }504505    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    }514515    pub fn productCount(self: ProductRefreshPlan) usize {516        return self.decisions.len;517    }518519    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    }528529    pub fn freshCount(self: ProductRefreshPlan) usize {530        return std.math.sub(usize, self.productCount(), self.refreshCount()) catch unreachable;531    }532533    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    }542543    pub fn liveCount(self: ProductRefreshPlan) usize {544        return self.materializationCount(.live);545    }546547    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    }553554    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    }566567    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    }580581    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    }590591    pub fn shouldRefresh(self: ProductRefreshPlan, ref: ProductRef) bool {592        const decision = self.decisionFor(ref) orelse return false;593        return decision.shouldRefresh();594    }595596    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};604605pub const ProductRefreshReport = struct {606    all_decisions: []const ProductRefreshDecision = &.{},607    closure: []const ProductRef = &.{},608    decisions: []const ProductRefreshDecision = &.{},609    storage: ?metadata_storage.Storage = null,610611    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);630631        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();639640        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    }657658    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 .{};666667        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        }684685        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();707708        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    }725726    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    }734735    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    }742743    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);749750        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);759760        for (reports) |report| {761            try closure.appendSlice(allocator, report.all_decisions);762        }763764        return try initFromDecisions(allocator, closure.decisions.items);765    }766767    pub fn refreshes(self: ProductRefreshReport, ref: ProductRef) bool {768        return productRefsContain(self.closure, ref);769    }770771    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    }777778    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    }784785    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    }792793    pub fn productCount(self: ProductRefreshReport) usize {794        return self.all_decisions.len;795    }796797    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    }808809    pub fn freshCount(self: ProductRefreshReport) usize {810        return std.math.sub(usize, self.productCount(), self.refreshCount()) catch unreachable;811    }812813    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    }822823    pub fn hasRefreshes(self: ProductRefreshReport) bool {824        return self.refreshCount() != 0;825    }826827    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    }833834    pub fn refreshesAreLive(self: ProductRefreshReport) bool {835        for (self.decisions) |decision| {836            if (!decision.isLive()) return false;837        }838        return true;839    }840841    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};853854pub const ProductGraphBuilderError = ProductMetadataError || error{855    ConflictingProductKey,856};857858const ProductDependencySliceSource = struct {859    dependencies: []const ProductDependency,860861    fn get(self: ProductDependencySliceSource, index: usize) ProductDependency {862        std.debug.assert(index < self.dependencies.len);863        return self.dependencies[index];864    }865};866867const LinearProductDependencySource = struct {868    products: []const ProductKey,869870    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 unreachable873        else874            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};880881pub const ProductGraph = struct {882    products: []const ProductKey = &.{},883    dependencies: []const ProductDependency = &.{},884    storage: ?metadata_storage.Storage = null,885886    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    }898899    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 .{};906907        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        }914915        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);925926        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();938939        return .{940            .products = owned_products,941            .dependencies = owned_dependencies,942            .storage = storage,943        };944    }945946    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);953954        for (graphs) |graph_value| try builder.appendGraph(allocator, graph_value);955        for (dependencies) |dependency| try builder.recordDependency(allocator, dependency);956957        return try builder.graph(allocator);958    }959960    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 unreachable966        else967            0;968        return try initFromDependencySource(969            allocator,970            products,971            dependency_count,972            LinearProductDependencySource{ .products = products },973        );974    }975976    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    }986987    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    }993994    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    }10001001    pub fn fingerprintFor(self: ProductGraph, ref: ProductRef) ?Fingerprint {1002        const product = self.productKeyFor(ref) orelse return null;1003        return product.fingerprint();1004    }10051006    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    }10141015    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    }10241025    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        };10371038        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        }10471048        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        }10571058        return .{1059            .key = key,1060            .refresh = false,1061            .previous_fingerprint = previous_fingerprint,1062        };1063    }10641065    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) or1075                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    }10921093    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);11001101        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        }11101111        return try invalidated.toOwnedSlice(allocator);1112    }11131114    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    }11211122    pub fn collectRetainedRefreshReport(1123        self: ProductGraph,1124        allocator: std.mem.Allocator,1125    ) ProductMetadataError!ProductRefreshReport {1126        return try self.collectRefreshReport(allocator, self);1127    }11281129    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    }11471148    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    }11611162    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        }11771178        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};11981199pub const ProductGraphBuilder = struct {1200    products: std.ArrayListUnmanaged(ProductKey) = .empty,1201    dependencies: std.ArrayListUnmanaged(ProductDependency) = .empty,12021203    pub fn deinit(self: *ProductGraphBuilder, allocator: std.mem.Allocator) void {1204        self.products.deinit(allocator);1205        self.dependencies.deinit(allocator);1206        self.* = .{};1207    }12081209    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    }12221223    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    }12331234    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    }12421243    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};12501251pub fn fingerprintBytes(bytes: []const u8) Fingerprint {1252    var builder = FingerprintBuilder{};1253    builder.updateBytes(bytes);1254    return builder.finish();1255}12561257pub fn productStamp(name: []const u8, fingerprint: Fingerprint) ProductStamp {1258    return .{1259        .name = name,1260        .fingerprint = fingerprint,1261    };1262}12631264pub 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}12721273pub 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}12861287pub 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}12921293pub fn productKey(exact: *const revision.Record) ProductKey {1294    return .{ .ref = exact.address(), .record = exact };1295}12961297pub fn cloneProductKey(_: std.mem.Allocator, key: ProductKey) ProductMetadataError!ProductKey {1298    try key.validate();1299    return productKey(try key.record.retain());1300}13011302pub fn deinitProductKey(_: std.mem.Allocator, key: ProductKey) void {1303    key.record.release();1304}13051306fn 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}13171318pub 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}13301331pub fn productDependency(1332    dependent: ProductKey,1333    dependency: ProductKey,1334) ProductDependency {1335    return .{1336        .dependent = dependent.ref,1337        .dependency = dependency.ref,1338    };1339}13401341pub fn productRefsContain(refs: []const ProductRef, ref: ProductRef) bool {1342    for (refs) |candidate| {1343        if (candidate.eql(ref)) return true;1344    }1345    return false;1346}13471348test "fingerprint builder is deterministic and length delimited" {1349    var left = FingerprintBuilder{};1350    left.updateBytes("ab");1351    left.updateBytes("c");13521353    var right = FingerprintBuilder{};1354    right.updateBytes("a");1355    right.updateBytes("bc");13561357    try std.testing.expectEqual(left.finish(), left.finish());1358    try std.testing.expect(left.finish() != right.finish());1359}13601361test "fingerprint builder delimits numeric slices and optionals" {1362    var left = FingerprintBuilder{};1363    left.updateU64Slice(&.{ 1, 23 });13641365    var right = FingerprintBuilder{};1366    right.updateU64Slice(&.{ 12, 3 });13671368    var empty = FingerprintBuilder{};1369    empty.updateOptionalU64Slice(&.{});13701371    var missing = FingerprintBuilder{};1372    missing.updateOptionalU64Slice(null);13731374    var negative = FingerprintBuilder{};1375    negative.updateI64(-1);13761377    var positive = FingerprintBuilder{};1378    positive.updateI64(1);13791380    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}13841385test "fingerprint builder delimits optional u32 and enum tags" {1386    const Mode = enum { alpha, beta };13871388    var present_u32 = FingerprintBuilder{};1389    present_u32.updateOptionalU32(7);13901391    var missing_u32 = FingerprintBuilder{};1392    missing_u32.updateOptionalU32(null);13931394    var alpha = FingerprintBuilder{};1395    alpha.updateOptionalEnumTag(@as(?Mode, .alpha));13961397    var beta = FingerprintBuilder{};1398    beta.updateOptionalEnumTag(@as(?Mode, .beta));13991400    var missing_enum = FingerprintBuilder{};1401    missing_enum.updateOptionalEnumTag(@as(?Mode, null));14021403    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}14071408test "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);14141415    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}14191420const Fixture = struct {1421    owner: *revision.Store,14221423    fn init() !Fixture {1424        return .{ .owner = try fixtureStore() };1425    }14261427    fn deinit(self: Fixture) void {1428        self.owner.release();1429    }14301431    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};14371438test "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}14611462test "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}14831484test "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}15101511test "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}15301531test "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}15551556test "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}15811582test "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);16041605    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));16101611    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));16171618    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);16221623    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}16281629fn 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}16391640test "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}16481649test "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}