tiny.closure.limits

1const schema = @import("schema/root.zig");2const project = @import("project/root.zig");3const std = @import("std");45pub const nodes_max: usize = 64;6pub const edges_max: usize = 128;7pub const artifacts_max: usize = 32;8pub const ranges_max: usize = 128;9pub const digests_max: usize = 128;10pub const provenance_parents_max: usize = 128;11pub const source_records_max: usize = 64;12pub const build_records_max: usize = 64;13pub const authorities_max: usize = 64;14pub const lineage_references_max: usize = 64;15pub const service_descriptors_max: usize = 16;16pub const residual_roots_max: usize = 64;17pub const claims_max: usize = 8;18pub const claim_nodes_max: usize = 128;19pub const receipt_bytes_max: usize = 512 * 1_024;20pub const storage_alignment: usize = 16;21pub const header_bytes: usize = 512;22pub const slot_header_bytes: usize = 256;2324pub const Limits = struct {25    nodes: usize = nodes_max,26    edges: usize = edges_max,27    artifacts: usize = artifacts_max,28    ranges: usize = ranges_max,29    digests: usize = digests_max,30    provenance_parents: usize = provenance_parents_max,31    source_records: usize = source_records_max,32    build_records: usize = build_records_max,33    authorities: usize = authorities_max,34    lineage_references: usize = lineage_references_max,35    service_descriptors: usize = service_descriptors_max,36    residual_roots: usize = residual_roots_max,37    claims: usize = claims_max,38    claim_nodes: usize = claim_nodes_max,39    receipt_bytes: usize = receipt_bytes_max,40};4142pub const SlotLayout = struct {43    base: usize,44    header: usize,45    nodes: usize,46    edges: usize,47    artifacts: usize,48    ranges: usize,49    digests: usize,50    provenance_parents: usize,51    source_records: usize,52    build_records: usize,53    authorities: usize,54    lineage_references: usize,55    service_descriptors: usize,56    residual_roots: usize,57    claims: usize,58    claim_nodes: usize,59    end: usize,60};6162pub const Layout = struct {63    header: usize,64    slots: [2]SlotLayout,65    visited: usize,66    queue: usize,67    receipt: usize,68    storage_bytes: usize,69};7071pub const CapacityError = error{72    EmptyLimit,73    NodeCapacityExceeded,74    EdgeCapacityExceeded,75    ArtifactCapacityExceeded,76    RangeCapacityExceeded,77    DigestCapacityExceeded,78    ProvenanceParentCapacityExceeded,79    SourceRecordCapacityExceeded,80    BuildRecordCapacityExceeded,81    AuthorityCapacityExceeded,82    LineageReferenceCapacityExceeded,83    ServiceDescriptorCapacityExceeded,84    ResidualRootCapacityExceeded,85    ClaimCapacityExceeded,86    ClaimNodeCapacityExceeded,87    ReceiptCapacityExceeded,88    CapacityArithmeticOverflow,89};9091pub const Capacity = struct {92    nodes: usize,93    edges: usize,94    artifacts: usize,95    ranges: usize,96    digests: usize,97    provenance_parents: usize,98    source_records: usize,99    build_records: usize,100    authorities: usize,101    lineage_references: usize,102    service_descriptors: usize,103    residual_roots: usize,104    claims: usize,105    claim_nodes: usize,106    receipt_bytes: usize,107    projection_steps_max: usize,108    receipt_rows_max: usize,109    layout: Layout,110    storage_bytes: usize,111112    pub const DeriveError: type = CapacityError;113114    pub fn derive(requested: Limits) DeriveError!Capacity {115        try validate(requested);116        const layout = try deriveLayout(requested);117        const projection_steps = project.maximumWork(.{118            .nodes = requested.nodes,119            .edges = requested.edges,120            .artifacts = requested.artifacts,121            .ranges = requested.ranges,122            .digests = requested.digests,123            .provenance_parents = requested.provenance_parents,124            .source_records = requested.source_records,125            .build_records = requested.build_records,126            .authorities = requested.authorities,127            .lineage_references = requested.lineage_references,128            .service_descriptors = requested.service_descriptors,129            .residual_roots = requested.residual_roots,130            .claims = requested.claims,131            .claim_nodes = requested.claim_nodes,132        }) catch return error.CapacityArithmeticOverflow;133        return .{134            .nodes = requested.nodes,135            .edges = requested.edges,136            .artifacts = requested.artifacts,137            .ranges = requested.ranges,138            .digests = requested.digests,139            .provenance_parents = requested.provenance_parents,140            .source_records = requested.source_records,141            .build_records = requested.build_records,142            .authorities = requested.authorities,143            .lineage_references = requested.lineage_references,144            .service_descriptors = requested.service_descriptors,145            .residual_roots = requested.residual_roots,146            .claims = requested.claims,147            .claim_nodes = requested.claim_nodes,148            .receipt_bytes = requested.receipt_bytes,149            .projection_steps_max = projection_steps,150            .receipt_rows_max = try receiptRows(requested),151            .layout = layout,152            .storage_bytes = layout.storage_bytes,153        };154    }155};156157fn deriveLayout(requested: Limits) CapacityError!Layout {158    var cursor = try aligned(header_bytes, storage_alignment);159    const first = try slotLayout(cursor, requested);160    cursor = try aligned(first.end, storage_alignment);161    const second = try slotLayout(cursor, requested);162    cursor = try aligned(second.end, storage_alignment);163    const visited = cursor;164    cursor = try added(cursor, requested.nodes);165    cursor = try aligned(cursor, @alignOf(u32));166    const queue = cursor;167    cursor = try segment(cursor, requested.nodes, @sizeOf(u32));168    cursor = try aligned(cursor, storage_alignment);169    const receipt = cursor;170    cursor = try added(cursor, requested.receipt_bytes);171    cursor = try aligned(cursor, storage_alignment);172    return .{173        .header = 0,174        .slots = .{ first, second },175        .visited = visited,176        .queue = queue,177        .receipt = receipt,178        .storage_bytes = cursor,179    };180}181182fn receiptRows(requested: Limits) CapacityError!usize {183    return total(&.{184        requested.nodes,185        requested.edges,186        requested.artifacts,187        requested.ranges,188        requested.digests,189        requested.provenance_parents,190        requested.source_records,191        requested.build_records,192        requested.authorities,193        requested.lineage_references,194        requested.service_descriptors,195        requested.residual_roots,196        requested.claims,197        requested.claim_nodes,198        1,199    });200}201202fn validate(requested: Limits) Capacity.DeriveError!void {203    if (requested.nodes == 0 or204        requested.edges == 0 or205        requested.artifacts == 0 or206        requested.ranges == 0 or207        requested.digests == 0 or208        requested.provenance_parents == 0 or209        requested.source_records == 0 or210        requested.build_records == 0 or211        requested.authorities == 0 or212        requested.lineage_references == 0 or213        requested.service_descriptors == 0 or214        requested.residual_roots == 0 or215        requested.claims == 0 or216        requested.claim_nodes == 0 or217        requested.receipt_bytes == 0)218    {219        return error.EmptyLimit;220    }221    if (requested.nodes > nodes_max) return error.NodeCapacityExceeded;222    if (requested.edges > edges_max) return error.EdgeCapacityExceeded;223    if (requested.artifacts > artifacts_max) {224        return error.ArtifactCapacityExceeded;225    }226    if (requested.ranges > ranges_max) return error.RangeCapacityExceeded;227    if (requested.digests > digests_max) return error.DigestCapacityExceeded;228    if (requested.provenance_parents > provenance_parents_max) {229        return error.ProvenanceParentCapacityExceeded;230    }231    if (requested.source_records > source_records_max) {232        return error.SourceRecordCapacityExceeded;233    }234    if (requested.build_records > build_records_max) {235        return error.BuildRecordCapacityExceeded;236    }237    if (requested.authorities > authorities_max) {238        return error.AuthorityCapacityExceeded;239    }240    if (requested.lineage_references > lineage_references_max) {241        return error.LineageReferenceCapacityExceeded;242    }243    if (requested.service_descriptors > service_descriptors_max) {244        return error.ServiceDescriptorCapacityExceeded;245    }246    if (requested.residual_roots > residual_roots_max) {247        return error.ResidualRootCapacityExceeded;248    }249    if (requested.claims > claims_max) return error.ClaimCapacityExceeded;250    if (requested.claim_nodes > claim_nodes_max) {251        return error.ClaimNodeCapacityExceeded;252    }253    if (requested.receipt_bytes > receipt_bytes_max) {254        return error.ReceiptCapacityExceeded;255    }256}257258fn slotLayout(259    base: usize,260    requested: Limits,261) Capacity.DeriveError!SlotLayout {262    var cursor = base;263    const header = cursor;264    cursor = try added(cursor, slot_header_bytes);265    const nodes = try start(&cursor, requested.nodes, schema.Node);266    const edges = try start(&cursor, requested.edges, schema.Edge);267    const artifacts = try start(&cursor, requested.artifacts, schema.Artifact);268    const ranges = try start(&cursor, requested.ranges, schema.ByteRange);269    const digests = try start(&cursor, requested.digests, schema.DigestRecord);270    const provenance_parents = try start(271        &cursor,272        requested.provenance_parents,273        schema.ProvenanceParent,274    );275    const source_records = try start(&cursor, requested.source_records, schema.SourceRecord);276    const build_records = try start(&cursor, requested.build_records, schema.BuildRecord);277    const authorities = try start(&cursor, requested.authorities, schema.Authority);278    const lineage_references = try start(279        &cursor,280        requested.lineage_references,281        schema.LineageReference,282    );283    const service_descriptors = try start(284        &cursor,285        requested.service_descriptors,286        schema.ServiceDescriptor,287    );288    const residual_roots = try start(&cursor, requested.residual_roots, schema.ResidualRoot);289    const claims = try start(&cursor, requested.claims, schema.Claim);290    const claim_nodes = try start(&cursor, requested.claim_nodes, schema.ClaimNode);291    return .{292        .base = base,293        .header = header,294        .nodes = nodes,295        .edges = edges,296        .artifacts = artifacts,297        .ranges = ranges,298        .digests = digests,299        .provenance_parents = provenance_parents,300        .source_records = source_records,301        .build_records = build_records,302        .authorities = authorities,303        .lineage_references = lineage_references,304        .service_descriptors = service_descriptors,305        .residual_roots = residual_roots,306        .claims = claims,307        .claim_nodes = claim_nodes,308        .end = try aligned(cursor, storage_alignment),309    };310}311312fn start(313    cursor: *usize,314    count: usize,315    comptime T: type,316) Capacity.DeriveError!usize {317    cursor.* = try aligned(cursor.*, @alignOf(T));318    const offset = cursor.*;319    cursor.* = try segment(cursor.*, count, @sizeOf(T));320    return offset;321}322323fn segment(324    offset: usize,325    count: usize,326    size: usize,327) Capacity.DeriveError!usize {328    return added(offset, try multiplied(count, size));329}330331fn aligned(332    value: usize,333    alignment: usize,334) Capacity.DeriveError!usize {335    const extra = alignment - 1;336    const sum = try added(value, extra);337    return sum & ~extra;338}339340fn multiplied(341    left: usize,342    right: usize,343) Capacity.DeriveError!usize {344    return std.math.mul(usize, left, right) catch345        error.CapacityArithmeticOverflow;346}347348fn added(349    left: usize,350    right: usize,351) Capacity.DeriveError!usize {352    return std.math.add(usize, left, right) catch353        error.CapacityArithmeticOverflow;354}355356fn total(values: []const usize) CapacityError!usize {357    var result: usize = 0;358    for (values) |value| result = try added(result, value);359    return result;360}361362test "maximum closure capacity derives two disjoint slots and scratch" {363    const capacity = try Capacity.derive(.{});364    try std.testing.expectEqual(365        @as(usize, 1_008_874),366        capacity.projection_steps_max,367    );368    try std.testing.expect(369        capacity.layout.slots[0].end <=370            capacity.layout.slots[1].base,371    );372    try std.testing.expect(373        capacity.layout.slots[1].end <= capacity.layout.visited,374    );375    try std.testing.expect(376        capacity.layout.receipt + capacity.receipt_bytes <=377            capacity.storage_bytes,378    );379    try std.testing.expectEqual(capacity.storage_bytes, capacity.layout.storage_bytes);380}381382test "independent closure capacities reject maximum plus one" {383    var requested = Limits{};384    inline for (.{385        .{ "nodes", error.NodeCapacityExceeded },386        .{ "edges", error.EdgeCapacityExceeded },387        .{ "artifacts", error.ArtifactCapacityExceeded },388        .{ "ranges", error.RangeCapacityExceeded },389        .{ "digests", error.DigestCapacityExceeded },390        .{391            "provenance_parents",392            error.ProvenanceParentCapacityExceeded,393        },394        .{ "source_records", error.SourceRecordCapacityExceeded },395        .{ "build_records", error.BuildRecordCapacityExceeded },396        .{ "authorities", error.AuthorityCapacityExceeded },397        .{398            "lineage_references",399            error.LineageReferenceCapacityExceeded,400        },401        .{402            "service_descriptors",403            error.ServiceDescriptorCapacityExceeded,404        },405        .{ "residual_roots", error.ResidualRootCapacityExceeded },406        .{ "claims", error.ClaimCapacityExceeded },407        .{ "claim_nodes", error.ClaimNodeCapacityExceeded },408        .{ "receipt_bytes", error.ReceiptCapacityExceeded },409    }) |case| {410        requested = .{};411        @field(requested, case[0]) += 1;412        try std.testing.expectError(case[1], Capacity.derive(requested));413    }414}

1pub const limits = @import("limits.zig");