lib/alloc/phase/src/capacity/spec.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const Sha256 = std.crypto.hash.sha2.Sha256;
4
5 /// Schema revision constant for specification input limits:
6 /// `input_bound_version` is a 16-bit integer constant with value 2, exported at
7 /// the package root as `spec_input_bound_version`. It identifies the
8 /// specification revision that expanded the maximum input capacity to 48. This
9 /// value tracks input bound sizing rather than the digest domain version or an
10 /// automatic schema conversion mechanism.
11 pub const input_bound_version: u16 = 2;
12 /// Historical limit for specification inputs: `inputs_max_v1` is an integer
13 /// constant set to 16, exported at the package root as `spec_inputs_max_v1`. It
14 /// records the earlier input capacity bound from initial specification
15 /// revisions. Current validation routines enforce `inputs_max` instead of this
16 /// historical threshold.
17 pub const inputs_max_v1: usize = 16;
18 /// Upper bound on specification inputs: `inputs_max` is an integer constant set
19 /// to 48, exported at the package root as `spec_inputs_max`. Specifications may
20 /// declare anywhere from zero up to 48 inputs inclusive. Validation returns an
21 /// error violation if an input list exceeds this bound.
22 pub const inputs_max: usize = 48;
23 /// Upper bound on specification type selectors: `type_selectors_max` is an
24 /// integer constant set to 16, exported at the package root as
25 /// `spec_type_selectors_max`. A specification may include an empty type
26 /// selector list or up to 16 selectors. Validation checks this limit during
27 /// structural inspection.
28 pub const type_selectors_max: usize = 16;
29 /// Upper bound on expression graph nodes: `nodes_max` is an integer constant
30 /// set to 64, exported at the package root as `spec_nodes_max`. A valid
31 /// specification requires at least one node and permits at most 64 nodes in its
32 /// ordered expression sequence.
33 pub const nodes_max: usize = 64;
34 /// Upper bound on specification assertions: `assertions_max` is an integer
35 /// constant set to 8, exported at the package root as `spec_assertions_max`. A
36 /// valid specification must contain at least one assertion and at most 8
37 /// assertions.
38 pub const assertions_max: usize = 8;
39 /// Maximum nesting depth for field navigation paths: `field_path_depth_max` is
40 /// an integer constant set to 8, exported at the package root as
41 /// `spec_field_path_depth_max`. It defines the maximum number of ordinal field
42 /// indices stored within a `BoundedFieldOrdinalPath`. Valid paths must contain
43 /// at least one ordinal and cannot exceed eight traversal steps.
44 pub const field_path_depth_max: usize = 8;
45 /// Maximum byte length for specification identifier symbols: `symbol_bytes_max`
46 /// is an integer constant set to 64. It constrains the raw byte length of input
47 /// and type selector identifier strings rather than counting Unicode
48 /// codepoints. Valid identifiers must have between 1 and 64 bytes, beginning
49 /// with a lowercase ASCII letter followed by lowercase ASCII letters, digits,
50 /// or underscores.
51 pub const symbol_bytes_max: usize = 64;
52 /// Maximum byte length for diagnostic field path strings:
53 /// `field_path_bytes_max` is an integer constant set to 256. It limits the
54 /// total byte length of the human-readable diagnostic path rather than bounding
55 /// nesting depth or field counts. A valid diagnostic string contains between 1
56 /// and 256 bytes formatted as dot-separated segments of ASCII alphanumeric
57 /// characters and underscores.
58 pub const field_path_bytes_max: usize = 256;
59 /// Byte length of the specification digest: `digest_bytes` is an integer
60 /// constant set to 32, exported at the package root as `spec_digest_bytes`. It
61 /// reflects the fixed 32-byte output length of the underlying SHA-256
62 /// cryptographic hash rather than the serialized length of the input data.
63 pub const digest_bytes: usize = Sha256.digest_length;
64 /// The `digest_domain` constant provides the exact byte sequence
65 /// `tiny.alloc.capacity-spec/v3` used as a length-framed initial domain in the
66 /// digest builder. This domain prefix isolates the specification hash stream
67 /// from inputs produced under alternative domain tags. Its version tag v3
68 /// designates the hashing protocol format and remains independent of the schema
69 /// `input_bound_version` constant.
70 pub const digest_domain = "tiny.alloc.capacity-spec/v3";
71
72 /// The `Measure` enumeration selects a quantity label within an `Assertion`
73 /// using tags `reserved`, `committed`, `live`, or `retained`. The measurement
74 /// tag belongs directly to the `Assertion` rather than to an expression node.
75 /// This module does not measure allocations or evaluate runtime quantities.
76 /// Scope and supporting evidence are supplied by an enclosing claim and
77 /// downstream analysis.
78 pub const Measure = enum {
79 reserved,
80 committed,
81 live,
82 retained,
83 };
84
85 /// Comparison intent for an asserted bound: `Relation` distinguishes whether an
86 /// expression represents an `upper_bound` or an `exact` quantity in an
87 /// `Assertion`. The tag declares the intended relation between the selected
88 /// `Measure` and the target expression node. Structural validation verifies
89 /// that the referenced expression node index falls within the defined node
90 /// array, but does not check whether the mathematical relationship holds true.
91 pub const Relation = enum {
92 upper_bound,
93 exact,
94 };
95
96 /// The `Scope` enumeration provides the sole tag `closure_total` to label the
97 /// evaluation scope of an `Assertion`. The module provides no evaluator,
98 /// automatic traversal of an owner graph, or proof of transitive coverage. A
99 /// source type alone does not establish a precise dynamic footprint for an
100 /// operation.
101 pub const Scope = enum {
102 closure_total,
103 };
104
105 /// Compile-time type binding for input limits and type selectors:
106 /// `SemanticType` is an alias for the Zig language primitive `type`. It
107 /// captures compile-time type identity during specification definition rather
108 /// than serializing a runtime type identifier. This binding allows compile-time
109 /// validation to inspect memory layout properties directly from the type
110 /// system.
111 pub const SemanticType = type;
112
113 /// Category of data held at the termination of a field path: `LeafClass`
114 /// classifies inputs as `unsigned_integer`, `signed_integer`, `collection`, or
115 /// `byte_collection`. When resolving fields in `bindInput`, integers up to 64
116 /// bits produce integer classes, slices of `u8` yield `byte_collection`, and
117 /// slices of other element types become `collection`. Expression validation
118 /// enforces that `Node.input` references only integer classes, collection
119 /// length projections accept both slice classes, and byte count projections
120 /// target only `byte_collection`.
121 pub const LeafClass = enum {
122 unsigned_integer,
123 signed_integer,
124 collection,
125 byte_collection,
126 };
127
128 /// `BoundedFieldOrdinalPath` represents a static path through nested structs
129 /// using a fixed array of eight `u16` field ordinals, an active `u8` length,
130 /// and a borrowed diagnostic string. The ordinals are zero-based field indices
131 /// in nested structs rather than memory byte offsets. The active length must
132 /// range from 1 to 8. The diagnostic string must consist of 1 to 256 bytes
133 /// formed by non-empty dot-separated ASCII segments containing letters, digits,
134 /// or underscores, with uppercase characters permitted. Typed validation
135 /// follows the actual field indices and verifies the leaf class. Structural
136 /// validation checks diagnostic syntax without resolving the diagnostic
137 /// spelling against field definitions. The computed hash covers the active
138 /// length and active ordinals while excluding the diagnostic string and unused
139 /// tail ordinals. The structure does not perform runtime navigation operations.
140 pub const BoundedFieldOrdinalPath = struct {
141 ordinals: [field_path_depth_max]u16 = @splat(0),
142 len: u8,
143 diagnostic: []const u8,
144 };
145
146 /// `FieldPath` is a type alias for `BoundedFieldOrdinalPath`, providing eight
147 /// fixed field-index slots alongside an active length. The type maintains
148 /// identical ordinal constraints and shares the lifetime of its borrowed
149 /// diagnostic string without treating indices as memory offsets.
150 pub const FieldPath = BoundedFieldOrdinalPath;
151
152 /// Specification input parameter holding compile-time type information: `Input`
153 /// defines an external input with an identifier string (`id`), a compile-time
154 /// limit type (`limits_type`), a navigation path (`field_path`), and an
155 /// expected category (`leaf_class`). The identifier must contain 1 to 64 bytes
156 /// beginning with a lowercase ASCII letter followed by lowercase alphanumeric
157 /// characters or underscores, and must be unique across all inputs. Because
158 /// `limits_type` stores a compile-time type, constructing an `Input` occurs at
159 /// compile time, borrowing string slices for the identifier and path
160 /// diagnostic. Typed validation confirms that `limits_type` matches the
161 /// expected limits type and that following the ordinal path through that type
162 /// yields the declared `leaf_class`.
163 pub const Input = struct {
164 id: []const u8,
165 limits_type: SemanticType,
166 field_path: BoundedFieldOrdinalPath,
167 leaf_class: LeafClass = .unsigned_integer,
168 };
169
170 /// Type-erased description of a specification input: `InputView` retains the
171 /// identifier string (`id`), ordinal path (`field_path`), and classification
172 /// tag (`leaf_class`) while omitting the compile-time type binding. It holds
173 /// borrowed string slices suitable for runtime inspection and digest
174 /// computation. Structural validation checks identifier syntax and path bounds,
175 /// but cannot verify whether the path corresponds to a field in any concrete
176 /// Zig type.
177 pub const InputView = struct {
178 id: []const u8,
179 field_path: BoundedFieldOrdinalPath,
180 leaf_class: LeafClass = .unsigned_integer,
181 };
182
183 /// Compile-time metadata binding for a referenced memory type: `TypeSelector`
184 /// pairs an identifier string (`id`) with a compile-time type
185 /// (`selected_type`), a size in bytes (`byte_size`), and a byte alignment
186 /// requirement (`byte_alignment`). Identifiers must be unique across all
187 /// selectors in a specification. Constructing a selector through `bindType`
188 /// captures the results of `@sizeOf` and `@alignOf` without taking ownership of
189 /// the underlying type. Typed validation verifies that the stored size and
190 /// alignment match the type, and that alignment is a non-zero power of two.
191 pub const TypeSelector = struct {
192 id: []const u8,
193 selected_type: SemanticType,
194 byte_size: u64,
195 byte_alignment: u64,
196 };
197
198 /// `TypeSelectorView` exposes only a borrowed identifier while omitting
199 /// `selected_type`, `byte_size`, and `byte_alignment`. Structural validation
200 /// verifies identifier grammar and confirms uniqueness across all selectors in
201 /// the view. The digest incorporates the selector identifier without erased
202 /// semantic type or layout details. An entire specification digest cannot be
203 /// assumed independent of host layout because other graph nodes may encode
204 /// concrete layout values.
205 pub const TypeSelectorView = struct {
206 id: []const u8,
207 };
208
209 /// Multiplication factor operand in a scaling expression: `Coefficient` is a
210 /// tagged union representing either a 64-bit constant (`literal`), an
211 /// unresolved integer parameter index (`unsigned_comptime_parameter`), a
212 /// generic type parameter index (`size_of_type_parameter`), or a concrete type
213 /// selector index (`size_of_concrete_type`). The parameter variants act as
214 /// declarative placeholders whose concrete values are not resolved by this
215 /// module. Structural validation checks that `size_of_concrete_type` references
216 /// an index within the specification type selector list. Construction and
217 /// validation do not compute products or perform arithmetic multiplication.
218 pub const Coefficient = union(enum) {
219 literal: u64,
220 unsigned_comptime_parameter: u16,
221 size_of_type_parameter: u16,
222 size_of_concrete_type: u16,
223 };
224
225 /// Binary operand reference for node expressions: `Pair` holds two 16-bit
226 /// unsigned integer indices, `left` and `right`. Both indices address earlier
227 /// nodes in the ordered expression array rather than input indices. Structural
228 /// validation enforces this directed acyclic graph ordering by requiring that
229 /// both indices strictly precede the position of the containing node.
230 pub const Pair = struct {
231 left: u16,
232 right: u16,
233 };
234
235 /// Symbolic multiplication of a node by a scaling factor: `Scale` combines a
236 /// 16-bit expression node index (`node`) with a `Coefficient` multiplier.
237 /// Validation requires that the referenced node index appears earlier in the
238 /// expression sequence, and enforces selector bounds if the coefficient
239 /// references a concrete type. The structure describes a mathematical scaling
240 /// operation without calculating a product or checking for integer overflow.
241 pub const Scale = struct {
242 node: u16,
243 coefficient: Coefficient,
244 };
245
246 /// The `Alignment` union represents an alignment requirement as either a
247 /// literal `u64` value or a `concrete_type` referencing a `u16` selector index.
248 /// Validation requires a literal value to be a non-zero power of two, or a
249 /// concrete index to reside within the valid selector range. Typed validation
250 /// examines selector size and alignment facts for concrete selections. A view
251 /// provides only the selector identifier for concrete selection, whereas a
252 /// literal `Alignment` retains its explicit numeric value. The type provides no
253 /// runtime allocation guarantee.
254 pub const Alignment = union(enum) {
255 literal: u64,
256 concrete_type: u16,
257 };
258
259 /// Symbolic rounding descriptor targeting a memory boundary: `Align` pairs a
260 /// 16-bit expression node index (`node`) with an `Alignment` rule. Structural
261 /// validation requires the target node index to strictly precede the position
262 /// of the current node. This struct describes a symbolic rounding calculation
263 /// for byte capacity expressions, rather than providing guarantees about
264 /// allocated pointer addresses.
265 pub const Align = struct {
266 node: u16,
267 alignment: Alignment,
268 };
269
270 /// Relational operator tag for conditional expressions: `Comparison` defines
271 /// the tags `equal`, `not_equal`, `less_than`, `less_or_equal`, `greater_than`,
272 /// and `greater_or_equal` for use inside a `Predicate`. Constructing a
273 /// comparison tag specifies the intended condition between two node values.
274 /// This module does not evaluate predicates or compare actual input values.
275 pub const Comparison = enum {
276 equal,
277 not_equal,
278 less_than,
279 less_or_equal,
280 greater_than,
281 greater_or_equal,
282 };
283
284 /// Comparison expression linking two node operands: `Predicate` combines a
285 /// `Comparison` operator with two 16-bit node indices, `left` and `right`. When
286 /// validated inside a `Conditional` node, both operand indices must strictly
287 /// precede the containing node index. The structure defines a declarative
288 /// relational test without evaluating operands or storing boolean results.
289 pub const Predicate = struct {
290 comparison: Comparison,
291 left: u16,
292 right: u16,
293 };
294
295 /// Branching expression selecting between alternative expressions:
296 /// `Conditional` holds a `Predicate` condition together with two 16-bit node
297 /// indices, `when_true` and `when_false`. Validation requires all referenced
298 /// nodes, including both predicate operands and both branch targets, to appear
299 /// earlier in the expression sequence than the conditional node itself. The
300 /// structure represents branch selection declaratively without executing either
301 /// branch or verifying path reachability.
302 pub const Conditional = struct {
303 predicate: Predicate,
304 when_true: u16,
305 when_false: u16,
306 };
307
308 /// Character occurrence counter for a byte slice: `ByteCount` pairs a 16-bit
309 /// input index (`input`) with an 8-bit byte value (`byte`). When referenced by
310 /// a collection projection node, validation verifies that the addressed input
311 /// exists and possesses a `byte_collection` leaf classification. The struct
312 /// declaratively describes counting occurrences of the specified byte within
313 /// the input slice without scanning memory or computing sums.
314 pub const ByteCount = struct {
315 input: u16,
316 byte: u8,
317 };
318
319 /// Measurement extraction from collection inputs: `CollectionProjection` is a
320 /// tagged union supporting either a `length` query taking a 16-bit input index
321 /// or a `byte_count` query holding a `ByteCount` descriptor. Unlike binary
322 /// arithmetic operators, these indices address entries in the specification
323 /// input list rather than expression nodes. Structural validation rejects
324 /// scalar integer inputs, permitting `length` on both general slices and byte
325 /// slices while restricting `byte_count` exclusively to byte slices.
326 pub const CollectionProjection = union(enum) {
327 length: u16,
328 byte_count: ByteCount,
329 };
330
331 /// Expression graph node union: `Node` defines the operations of the capacity
332 /// expression language through tags `constant`, `input`, `add`, `maximum`,
333 /// `scale`, `product`, `alignment`, `ceiling_division`, `conditional`,
334 /// `next_power_of_two`, and `collection`. Nodes form an ordered acyclic graph
335 /// bounded to at most 64 entries in a valid specification. Structural
336 /// validation requires operand node indices to strictly precede the current
337 /// node position, while inputs and collection projections must address valid
338 /// inputs matching their required leaf classes. Validation does not evaluate
339 /// expressions, check for division by zero, guard against arithmetic overflow,
340 /// or verify value positivity.
341 pub const Node = union(enum) {
342 constant: u64,
343 input: u16,
344 add: Pair,
345 maximum: Pair,
346 scale: Scale,
347 product: Pair,
348 alignment: Align,
349 ceiling_division: Pair,
350 conditional: Conditional,
351 next_power_of_two: u16,
352 collection: CollectionProjection,
353 };
354
355 /// Formal capacity claim for a completed expression: `Assertion` binds a
356 /// `Scope`, a `Measure`, and a `Relation` to a 16-bit node index
357 /// (`expression`). Structural validation checks that the referenced expression
358 /// index points to a valid node within the specification node array.
359 /// Constructing or validating an `Assertion` does not invoke runtime assertion
360 /// checks, evaluate expression values, or verify agreement with derived
361 /// allocation bounds.
362 pub const Assertion = struct {
363 scope: Scope,
364 measure: Measure,
365 relation: Relation,
366 expression: u16,
367 };
368
369 /// Typed capacity specification holding semantic bindings: `Spec` bundles
370 /// borrowed slices of typed `Input` definitions, ordered `Node` entries,
371 /// `Assertion` claims, and optional `TypeSelector` bindings. Valid
372 /// specifications contain up to 48 inputs, up to 16 type selectors, 1 to 64
373 /// nodes, and 1 to 8 assertions, with inputs and type selectors permitted to be
374 /// empty. Because `Input` and `TypeSelector` contain compile-time type
375 /// references, a `Spec` is constructed at compile time and does not validate
376 /// invariants upon instantiation. The enclosing owner declaration validation
377 /// routine invokes the internal typed `validate` function to check structural
378 /// and layout rules.
379 pub const Spec = struct {
380 inputs: []const Input,
381 nodes: []const Node,
382 assertions: []const Assertion,
383 type_selectors: []const TypeSelector = &.{},
384 };
385
386 /// Type-erased view of a capacity specification: `View`, re-exported at the
387 /// package root as `SpecView`, represents a specification using `InputView` and
388 /// `TypeSelectorView` slices alongside expression nodes and assertions. All
389 /// slices are borrowed, and callers can construct or provide a `View` at
390 /// runtime because it contains no compile-time type fields. The internal
391 /// compile-time `view` constructor produces view slices with static storage
392 /// lifetime, but arbitrary runtime instances do not own underlying memory or
393 /// guarantee static persistence.
394 pub const View = struct {
395 inputs: []const InputView,
396 nodes: []const Node,
397 assertions: []const Assertion,
398 type_selectors: []const TypeSelectorView = &.{},
399 };
400
401 /// Failure reason for capacity specification validation: `Violation`,
402 /// re-exported at the package root as `SpecViolation`, enumerates the first
403 /// structural or typed rule failure encountered during validation. The
404 /// specification does not enforce any rule that rejects unused or unreferenced
405 /// graph nodes. An invalid assertion expression failure specifically denotes a
406 /// referenced node index that is out of bounds rather than an arithmetic
407 /// evaluation error.
408 pub const Violation = enum {
409 limits_type_mismatch,
410 input_overflow,
411 input_id_invalid,
412 input_id_duplicate,
413 input_field_path_invalid,
414 type_selector_overflow,
415 type_selector_id_invalid,
416 type_selector_id_duplicate,
417 type_selector_fact_invalid,
418 nodes_missing,
419 node_overflow,
420 node_outside_fragment,
421 assertions_missing,
422 assertion_overflow,
423 assertion_expression_invalid,
424 };
425
426 /// Compile-time constructor linking an input identifier to a nested struct
427 /// field: `bindInput` evaluates at compile time to validate the syntax of an
428 /// identifier and a dot-separated diagnostic path against a target `Limits`
429 /// type. It reflects over struct fields to build an ordinal navigation path and
430 /// deduce the field `LeafClass`. The function emits a compile error if a field
431 /// name does not exist, an intermediate element is not a struct, traversal
432 /// depth exceeds eight levels, or the leaf type is unsupported. Supported leaf
433 /// types include integers up to 64 bits and slices, while fixed-size arrays and
434 /// wider integers are rejected. Execution raises the compiler evaluation branch
435 /// quota to 10000 to resolve nested types, and does not inspect runtime values.
436 pub fn bindInput(
437 comptime Limits: type,
438 comptime id: []const u8,
439 comptime field_path: []const u8,
440 ) Input {
441 @setEvalBranchQuota(10_000);
442 if (comptime !symbolValid(id)) {
443 @compileError("invalid capacity input id: " ++ id);
444 }
445 if (comptime !pathTextValid(field_path)) {
446 @compileError("invalid Limits field path: " ++ field_path);
447 }
448 const resolved = resolveInput(Limits, field_path);
449 return .{
450 .id = id,
451 .limits_type = Limits,
452 .field_path = resolved.field_path,
453 .leaf_class = resolved.leaf_class,
454 };
455 }
456
457 /// Compile-time constructor capturing layout metrics for a named type:
458 /// `bindType` validates an identifier string at compile time and queries the
459 /// size and alignment of type `T` using `@sizeOf` and `@alignOf`. Invalid
460 /// identifier syntax or types that disallow size and alignment inspection
461 /// produce a compile error. The function records numeric layout metrics
462 /// directly without allocating memory, generating runtime type tokens, or
463 /// validating the enclosing `Spec`.
464 pub fn bindType(comptime T: type, comptime id: []const u8) TypeSelector {
465 if (comptime !symbolValid(id)) {
466 @compileError("invalid capacity type selector id: " ++ id);
467 }
468 return .{
469 .id = id,
470 .selected_type = T,
471 .byte_size = @sizeOf(T),
472 .byte_alignment = @alignOf(T),
473 };
474 }
475
476 /// Compile-time converter from a typed specification to a type-erased view:
477 /// `view` is public within `spec.zig` but is not re-exported from the package
478 /// root. It transforms a compile-time `Spec` into a `View` by constructing
479 /// compile-time arrays of `InputView` and `TypeSelectorView` that remain valid
480 /// after the function returns. The conversion preserves node and assertion
481 /// slices while stripping compile-time types and numeric size facts, without
482 /// validating the input specification.
483 pub fn view(comptime value: Spec) View {
484 const inputs = comptime inputViews(value.inputs);
485 const type_selectors = comptime typeSelectorViews(value.type_selectors);
486 return .{
487 .inputs = &inputs,
488 .nodes = value.nodes,
489 .assertions = value.assertions,
490 .type_selectors = &type_selectors,
491 };
492 }
493
494 fn inputViews(comptime inputs: []const Input) [inputs.len]InputView {
495 var result: [inputs.len]InputView = undefined;
496 inline for (inputs, 0..) |input, index| {
497 result[index] = .{
498 .id = input.id,
499 .field_path = input.field_path,
500 .leaf_class = input.leaf_class,
501 };
502 }
503 return result;
504 }
505
506 fn typeSelectorViews(
507 comptime values: []const TypeSelector,
508 ) [values.len]TypeSelectorView {
509 var result: [values.len]TypeSelectorView = undefined;
510 inline for (values, 0..) |value, index| {
511 result[index] = .{ .id = value.id };
512 }
513 return result;
514 }
515
516 /// Compile-time validator for typed capacity specifications: `validate` is
517 /// public within `spec.zig` but is not exported from the package root. It
518 /// accepts a compile-time `Limits` type and a `Spec`, returning the first
519 /// encountered `Violation` or null when valid. The function verifies that every
520 /// input references the exact `Limits` type and that traversing its ordinals
521 /// matches the declared leaf classification, then confirms that type selector
522 /// sizes and alignments match their respective types with non-zero power-of-two
523 /// alignment before delegating to `validateView`. It does not execute
524 /// expressions or record claim metadata.
525 pub fn validate(comptime Limits: type, comptime value: Spec) ?Violation {
526 inline for (value.inputs) |input| {
527 if (input.limits_type != Limits) return .limits_type_mismatch;
528 if (fieldPathClass(Limits, input.field_path) != input.leaf_class) {
529 return .input_field_path_invalid;
530 }
531 }
532 inline for (value.type_selectors) |selector| {
533 if (selector.byte_size != @sizeOf(selector.selected_type) or
534 selector.byte_alignment != @alignOf(selector.selected_type) or
535 selector.byte_alignment == 0 or
536 !std.math.isPowerOfTwo(selector.byte_alignment))
537 {
538 return .type_selector_fact_invalid;
539 }
540 }
541 return validateView(view(value));
542 }
543
544 /// The `validateView` function, known under the root name `validateSpecView`,
545 /// accepts a specification `View` and executes at compile time or runtime to
546 /// return an optional first `Violation` or null. The validator verifies
547 /// structural bounds requiring 0 to 48 inputs, 0 to 16 selectors, 1 to 64
548 /// nodes, and 1 to 8 assertions. Checks include identifier grammar and
549 /// uniqueness within each input and selector collection, path structure and
550 /// diagnostic syntax, references to strictly earlier node operands, input leaf
551 /// and projection compatibility, concrete selector index ranges, literal
552 /// power-of-two alignments, and in-bounds assertion node indices. The function
553 /// cannot inspect semantic `Limits` or concrete type facts that are omitted
554 /// from the view. The implementation does not evaluate arithmetic operations,
555 /// verify division denominator values, detect numerical overflow, or resolve
556 /// generic parameter values.
557 pub fn validateView(value: View) ?Violation {
558 if (value.inputs.len > inputs_max) return .input_overflow;
559 for (value.inputs, 0..) |input, index| {
560 if (!symbolValid(input.id)) return .input_id_invalid;
561 if (!fieldPathShapeValid(input.field_path)) {
562 return .input_field_path_invalid;
563 }
564 for (value.inputs[0..index]) |earlier| {
565 if (std.mem.eql(u8, earlier.id, input.id)) {
566 return .input_id_duplicate;
567 }
568 }
569 }
570 if (value.type_selectors.len > type_selectors_max) {
571 return .type_selector_overflow;
572 }
573 for (value.type_selectors, 0..) |selector, index| {
574 if (!symbolValid(selector.id)) return .type_selector_id_invalid;
575 for (value.type_selectors[0..index]) |earlier| {
576 if (std.mem.eql(u8, earlier.id, selector.id)) {
577 return .type_selector_id_duplicate;
578 }
579 }
580 }
581 if (value.nodes.len == 0) return .nodes_missing;
582 if (value.nodes.len > nodes_max) return .node_overflow;
583 for (value.nodes, 0..) |node, index| {
584 if (!nodeValid(node, index, value.inputs, value.type_selectors.len)) {
585 return .node_outside_fragment;
586 }
587 }
588 if (value.assertions.len == 0) return .assertions_missing;
589 if (value.assertions.len > assertions_max) return .assertion_overflow;
590 for (value.assertions) |assertion| {
591 if (assertion.expression >= value.nodes.len) {
592 return .assertion_expression_invalid;
593 }
594 }
595 return null;
596 }
597
598 /// The `digest` function, corresponding to the root identifier
599 /// `capacitySpecDigest`, generates a 32-byte SHA-256 digest using the domain
600 /// string `tiny.alloc.capacity-spec/v3`. Serialization employs length framing
601 /// for field names and values while encoding numeric values as little-endian
602 /// `u64` words and preserving input list order. The digest incorporates input
603 /// identifiers, input classes, active ordinal paths, selector identifiers,
604 /// nodes, and assertions. It omits diagnostic strings, `Limits` type
605 /// identities, and selector concrete type identities along with their size and
606 /// alignment values. The function performs no internal sorting, algebraic
607 /// normalization, or structural validation, assuming the caller supplies a
608 /// valid bounded view. The resulting hash distinguishes only the selected
609 /// serialized fields and does not attest to overall semantic equivalence, full
610 /// implementation behavior, or supporting evidence.
611 pub fn digest(value: View) [digest_bytes]u8 {
612 var builder = DigestBuilder.init();
613 builder.addCount("inputs", value.inputs.len);
614 for (value.inputs) |input| addInput(&builder, input);
615 builder.addCount("type_selectors", value.type_selectors.len);
616 for (value.type_selectors) |selector| {
617 builder.addBytes("type_selector", selector.id);
618 }
619 builder.addCount("nodes", value.nodes.len);
620 for (value.nodes) |node| addNode(&builder, node);
621 builder.addCount("assertions", value.assertions.len);
622 for (value.assertions) |assertion| addAssertion(&builder, assertion);
623 return builder.finish();
624 }
625
626 const ResolvedInput = struct {
627 field_path: FieldPath,
628 leaf_class: LeafClass,
629 };
630
631 fn resolveInput(
632 comptime Limits: type,
633 comptime field_path: []const u8,
634 ) ResolvedInput {
635 return comptime result: {
636 var path = BoundedFieldOrdinalPath{
637 .len = 0,
638 .diagnostic = field_path,
639 };
640 var current = Limits;
641 var components = std.mem.splitScalar(u8, field_path, '.');
642 while (components.next()) |component| {
643 if (path.len == field_path_depth_max) {
644 @compileError(
645 "Limits field path exceeds its depth bound: " ++ field_path,
646 );
647 }
648 const resolved = resolveField(current, component) orelse {
649 @compileError("invalid Limits field path: " ++ field_path);
650 };
651 path.ordinals[path.len] = resolved.ordinal;
652 path.len += 1;
653 current = resolved.field_type;
654 }
655 const leaf_class = classifyLeaf(current) orelse {
656 @compileError(
657 "Limits field path has an unsupported leaf: " ++ field_path,
658 );
659 };
660 break :result .{ .field_path = path, .leaf_class = leaf_class };
661 };
662 }
663
664 const ResolvedField = struct {
665 ordinal: u16,
666 field_type: type,
667 };
668
669 fn resolveField(comptime Container: type, comptime name: []const u8) ?ResolvedField {
670 const info = @typeInfo(Container);
671 if (info != .@"struct") return null;
672 inline for (
673 info.@"struct".field_names,
674 info.@"struct".field_types,
675 0..,
676 ) |field_name, field_type, index| {
677 if (std.mem.eql(u8, field_name, name)) {
678 if (index > std.math.maxInt(u16)) return null;
679 return .{ .ordinal = @intCast(index), .field_type = field_type };
680 }
681 }
682 return null;
683 }
684
685 fn fieldPathClass(
686 comptime Limits: type,
687 comptime path: BoundedFieldOrdinalPath,
688 ) ?LeafClass {
689 if (!pathTextValid(path.diagnostic)) return null;
690 if (path.len == 0 or path.len > field_path_depth_max) return null;
691 inline for (path.ordinals[path.len..]) |ordinal| {
692 if (ordinal != 0) return null;
693 }
694 comptime var current = Limits;
695 inline for (path.ordinals[0..path.len]) |ordinal| {
696 const info = @typeInfo(current);
697 if (info != .@"struct") return null;
698 if (ordinal >= info.@"struct".field_types.len) return null;
699 current = info.@"struct".field_types[ordinal];
700 }
701 return classifyLeaf(current);
702 }
703
704 fn fieldPathShapeValid(path: BoundedFieldOrdinalPath) bool {
705 if (!pathTextValid(path.diagnostic)) return false;
706 if (path.len == 0 or path.len > field_path_depth_max) return false;
707 for (path.ordinals[path.len..]) |ordinal| {
708 if (ordinal != 0) return false;
709 }
710 return true;
711 }
712
713 fn nodeValid(
714 node: Node,
715 index: usize,
716 inputs: []const InputView,
717 type_selector_count: usize,
718 ) bool {
719 return switch (node) {
720 .constant => true,
721 .input => |input| input < inputs.len and
722 inputs[input].leaf_class != .collection and
723 inputs[input].leaf_class != .byte_collection,
724 .add => |pair| priorPair(pair, index),
725 .maximum => |pair| priorPair(pair, index),
726 .scale => |scale| scale.node < index and
727 coefficientValid(scale.coefficient, type_selector_count),
728 .product => |pair| priorPair(pair, index),
729 .alignment => |aligned| aligned.node < index and
730 alignmentValid(aligned.alignment, type_selector_count),
731 .ceiling_division => |pair| priorPair(pair, index),
732 .conditional => |conditional| conditionalValid(conditional, index),
733 .next_power_of_two => |value| value < index,
734 .collection => |projection| collectionValid(projection, inputs),
735 };
736 }
737
738 fn collectionValid(
739 projection: CollectionProjection,
740 inputs: []const InputView,
741 ) bool {
742 return switch (projection) {
743 .length => |input| input < inputs.len and switch (inputs[input].leaf_class) {
744 .collection, .byte_collection => true,
745 .unsigned_integer, .signed_integer => false,
746 },
747 .byte_count => |count| count.input < inputs.len and
748 inputs[count.input].leaf_class == .byte_collection,
749 };
750 }
751
752 fn coefficientValid(value: Coefficient, type_selector_count: usize) bool {
753 return switch (value) {
754 .size_of_concrete_type => |selector| selector < type_selector_count,
755 else => true,
756 };
757 }
758
759 fn alignmentValid(value: Alignment, type_selector_count: usize) bool {
760 return switch (value) {
761 .literal => |alignment| alignment != 0 and
762 std.math.isPowerOfTwo(alignment),
763 .concrete_type => |selector| selector < type_selector_count,
764 };
765 }
766
767 fn conditionalValid(value: Conditional, index: usize) bool {
768 return value.predicate.left < index and value.predicate.right < index and
769 value.when_true < index and value.when_false < index;
770 }
771
772 fn priorPair(pair: Pair, index: usize) bool {
773 return pair.left < index and pair.right < index;
774 }
775
776 fn classifyLeaf(comptime T: type) ?LeafClass {
777 return switch (@typeInfo(T)) {
778 .int => |integer| if (integer.bits > 64) null else switch (integer.signedness) {
779 .unsigned => .unsigned_integer,
780 .signed => .signed_integer,
781 },
782 .pointer => |pointer| if (pointer.size == .slice)
783 if (pointer.child == u8) .byte_collection else .collection
784 else
785 null,
786 else => null,
787 };
788 }
789
790 fn symbolValid(value: []const u8) bool {
791 if (value.len == 0 or value.len > symbol_bytes_max) return false;
792 if (value[0] < 'a' or value[0] > 'z') return false;
793 for (value[1..]) |byte| {
794 const lower = byte >= 'a' and byte <= 'z';
795 const digit = byte >= '0' and byte <= '9';
796 if (!lower and !digit and byte != '_') return false;
797 }
798 return true;
799 }
800
801 fn pathTextValid(value: []const u8) bool {
802 if (value.len == 0 or value.len > field_path_bytes_max) return false;
803 if (value[0] == '.' or value[value.len - 1] == '.') return false;
804 var component_bytes: usize = 0;
805 for (value) |byte| {
806 if (byte == '.') {
807 if (component_bytes == 0) return false;
808 component_bytes = 0;
809 continue;
810 }
811 const alpha = std.ascii.isAlphabetic(byte);
812 if (!alpha and !std.ascii.isDigit(byte) and byte != '_') return false;
813 component_bytes += 1;
814 }
815 return component_bytes != 0;
816 }
817
818 const DigestBuilder = struct {
819 state: Sha256,
820
821 fn init() DigestBuilder {
822 var result = DigestBuilder{ .state = Sha256.init(.{}) };
823 result.addFramed(digest_domain);
824 return result;
825 }
826
827 fn addBytes(self: *DigestBuilder, name: []const u8, value: []const u8) void {
828 self.addFramed(name);
829 self.addFramed(value);
830 }
831
832 fn addEnum(self: *DigestBuilder, name: []const u8, value: anytype) void {
833 self.addBytes(name, @tagName(value));
834 }
835
836 fn addCount(self: *DigestBuilder, name: []const u8, value: usize) void {
837 self.addFramed(name);
838 self.addU64(value);
839 }
840
841 fn addU64(self: *DigestBuilder, value: u64) void {
842 var encoded: [8]u8 = undefined;
843 std.mem.writeInt(u64, &encoded, value, .little);
844 self.addFramed(&encoded);
845 }
846
847 fn finish(self: *DigestBuilder) [digest_bytes]u8 {
848 var result: [digest_bytes]u8 = undefined;
849 self.state.final(&result);
850 return result;
851 }
852
853 fn addFramed(self: *DigestBuilder, value: []const u8) void {
854 var length: [8]u8 = undefined;
855 std.mem.writeInt(u64, &length, value.len, .little);
856 self.state.update(&length);
857 self.state.update(value);
858 }
859 };
860
861 fn addInput(builder: *DigestBuilder, input: InputView) void {
862 builder.addBytes("input_id", input.id);
863 builder.addEnum("input_leaf_class", input.leaf_class);
864 builder.addCount("field_path", input.field_path.len);
865 for (input.field_path.ordinals[0..input.field_path.len]) |ordinal| {
866 builder.addU64(ordinal);
867 }
868 }
869
870 fn addNode(builder: *DigestBuilder, node: Node) void {
871 builder.addEnum("node", node);
872 switch (node) {
873 .constant => |value| builder.addU64(value),
874 .input => |value| builder.addU64(value),
875 .add => |pair| addPair(builder, pair),
876 .maximum => |pair| addPair(builder, pair),
877 .scale => |scale| {
878 builder.addU64(scale.node);
879 builder.addEnum("coefficient", scale.coefficient);
880 switch (scale.coefficient) {
881 inline else => |value| builder.addU64(value),
882 }
883 },
884 .product => |pair| addPair(builder, pair),
885 .alignment => |aligned| {
886 builder.addU64(aligned.node);
887 builder.addEnum("alignment", aligned.alignment);
888 switch (aligned.alignment) {
889 inline else => |value| builder.addU64(value),
890 }
891 },
892 .ceiling_division => |pair| addPair(builder, pair),
893 .conditional => |conditional| {
894 builder.addEnum("comparison", conditional.predicate.comparison);
895 builder.addU64(conditional.predicate.left);
896 builder.addU64(conditional.predicate.right);
897 builder.addU64(conditional.when_true);
898 builder.addU64(conditional.when_false);
899 },
900 .next_power_of_two => |value| builder.addU64(value),
901 .collection => |projection| {
902 builder.addEnum("collection_projection", projection);
903 switch (projection) {
904 .length => |input| builder.addU64(input),
905 .byte_count => |count| {
906 builder.addU64(count.input);
907 builder.addU64(count.byte);
908 },
909 }
910 },
911 }
912 }
913
914 fn addPair(builder: *DigestBuilder, pair: Pair) void {
915 builder.addU64(pair.left);
916 builder.addU64(pair.right);
917 }
918
919 fn addAssertion(builder: *DigestBuilder, assertion: Assertion) void {
920 builder.addEnum("scope", assertion.scope);
921 builder.addEnum("measure", assertion.measure);
922 builder.addEnum("relation", assertion.relation);
923 builder.addU64(assertion.expression);
924 }
925
926 const ViewLifetimeFixture = struct {
927 const Limits = struct { count: u16, bytes: u32 };
928 const value: Spec = .{
929 .inputs = &.{
930 bindInput(Limits, "count", "count"),
931 bindInput(Limits, "bytes", "bytes"),
932 },
933 .type_selectors = &.{bindType(u64, "word")},
934 .nodes = &.{
935 .{ .input = 0 },
936 .{ .input = 1 },
937 .{ .add = .{ .left = 0, .right = 1 } },
938 .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 0 } } },
939 },
940 .assertions = &.{.{
941 .scope = .closure_total,
942 .measure = .retained,
943 .relation = .exact,
944 .expression = 3,
945 }},
946 };
947
948 noinline fn returned() View {
949 return view(value);
950 }
951
952 noinline fn reuseStack() void {
953 var bytes: [4096]u8 = @splat(0xa5);
954 std.mem.doNotOptimizeAway(&bytes);
955 }
956 };
957
958 test "capacity Spec returned view retains metadata after stack reuse" {
959 const expected_view = comptime view(ViewLifetimeFixture.value);
960 const expected = digest(expected_view);
961 const retained = ViewLifetimeFixture.returned();
962 ViewLifetimeFixture.reuseStack();
963 try std.testing.expectEqual(@as(u8, 1), retained.inputs[0].field_path.len);
964 try std.testing.expectEqual(@as(usize, 4), retained.type_selectors[0].id.len);
965 try std.testing.expectEqual(@as(?Violation, null), validateView(retained));
966 const actual = digest(retained);
967 try std.testing.expectEqualSlices(u8, &expected, &actual);
968 }
969
970 test "capacity Spec binds typed Limits paths and the complete node fragment" {
971 const Limits = struct {
972 shape: struct { slots: u16 },
973 bytes: u32,
974 };
975 const value = comptime Spec{
976 .inputs = &.{
977 bindInput(Limits, "slots", "shape.slots"),
978 bindInput(Limits, "bytes", "bytes"),
979 },
980 .nodes = &.{
981 .{ .constant = 1 },
982 .{ .input = 0 },
983 .{ .input = 1 },
984 .{ .add = .{ .left = 1, .right = 2 } },
985 .{ .maximum = .{ .left = 0, .right = 3 } },
986 .{ .scale = .{ .node = 4, .coefficient = .{ .literal = 2 } } },
987 },
988 .assertions = &.{
989 .{
990 .scope = .closure_total,
991 .measure = .reserved,
992 .relation = .upper_bound,
993 .expression = 5,
994 },
995 .{
996 .scope = .closure_total,
997 .measure = .committed,
998 .relation = .upper_bound,
999 .expression = 4,
1000 },
1001 .{
1002 .scope = .closure_total,
1003 .measure = .live,
1004 .relation = .upper_bound,
1005 .expression = 3,
1006 },
1007 .{
1008 .scope = .closure_total,
1009 .measure = .retained,
1010 .relation = .exact,
1011 .expression = 3,
1012 },
1013 },
1014 };
1015 try std.testing.expect(validate(Limits, value) == null);
1016 const semantic_digest = digest(view(value));
1017 try std.testing.expect(!std.mem.allEqual(u8, &semantic_digest, 0));
1018 }
1019
1020 test "capacity Spec rejects nodes outside the bounded fragment" {
1021 const Limits = struct { count: u16 };
1022 const value = comptime Spec{
1023 .inputs = &.{bindInput(Limits, "count", "count")},
1024 .nodes = &.{
1025 .{ .input = 0 },
1026 .{ .add = .{ .left = 0, .right = 1 } },
1027 },
1028 .assertions = &.{.{
1029 .scope = .closure_total,
1030 .measure = .retained,
1031 .relation = .exact,
1032 .expression = 1,
1033 }},
1034 };
1035 try std.testing.expectEqual(
1036 Violation.node_outside_fragment,
1037 validate(Limits, value).?,
1038 );
1039 }
1040
1041 test "capacity Spec preserves the widened live expression fragment" {
1042 const Limits = struct {
1043 items: u16,
1044 width: u16,
1045 deferred: u8,
1046 };
1047 const value = comptime Spec{
1048 .inputs = &.{
1049 bindInput(Limits, "items", "items"),
1050 bindInput(Limits, "width", "width"),
1051 bindInput(Limits, "deferred", "deferred"),
1052 },
1053 .nodes = &.{
1054 .{ .constant = 0 },
1055 .{ .constant = 8 },
1056 .{ .input = 0 },
1057 .{ .input = 1 },
1058 .{ .product = .{ .left = 2, .right = 3 } },
1059 .{ .scale = .{
1060 .node = 2,
1061 .coefficient = .{ .size_of_concrete_type = 0 },
1062 } },
1063 .{ .add = .{ .left = 4, .right = 5 } },
1064 .{ .alignment = .{ .node = 6, .alignment = .{ .concrete_type = 0 } } },
1065 .{ .ceiling_division = .{ .left = 2, .right = 1 } },
1066 .{ .input = 2 },
1067 .{ .conditional = .{
1068 .predicate = .{ .comparison = .equal, .left = 9, .right = 0 },
1069 .when_true = 0,
1070 .when_false = 7,
1071 } },
1072 .{ .add = .{ .left = 8, .right = 10 } },
1073 },
1074 .assertions = &.{.{
1075 .scope = .closure_total,
1076 .measure = .retained,
1077 .relation = .exact,
1078 .expression = 11,
1079 }},
1080 .type_selectors = &.{bindType(u32, "entry")},
1081 };
1082 try std.testing.expect(validate(Limits, value) == null);
1083 try std.testing.expect(!std.mem.allEqual(u8, &digest(view(value)), 0));
1084
1085 const invalid = comptime invalid: {
1086 var selector = bindType(u32, "entry");
1087 selector.byte_size = 8;
1088 break :invalid Spec{
1089 .inputs = &.{bindInput(Limits, "items", "items")},
1090 .nodes = &.{.{ .input = 0 }},
1091 .assertions = &.{.{
1092 .scope = .closure_total,
1093 .measure = .retained,
1094 .relation = .exact,
1095 .expression = 0,
1096 }},
1097 .type_selectors = &.{selector},
1098 };
1099 };
1100 try std.testing.expectEqual(
1101 Violation.type_selector_fact_invalid,
1102 validate(Limits, invalid).?,
1103 );
1104 }
1105
1106 test "capacity Spec represents census leaf and projection closure" {
1107 const Limits = struct {
1108 width: i32,
1109 candidates: []const u32,
1110 source: []const u8,
1111 };
1112 const value = comptime Spec{
1113 .inputs = &.{
1114 bindInput(Limits, "width", "width"),
1115 bindInput(Limits, "candidates", "candidates"),
1116 bindInput(Limits, "source", "source"),
1117 },
1118 .nodes = &.{
1119 .{ .input = 0 },
1120 .{ .collection = .{ .length = 1 } },
1121 .{ .collection = .{ .byte_count = .{
1122 .input = 2,
1123 .byte = '\n',
1124 } } },
1125 .{ .add = .{ .left = 1, .right = 2 } },
1126 .{ .next_power_of_two = 3 },
1127 },
1128 .assertions = &.{.{
1129 .scope = .closure_total,
1130 .measure = .retained,
1131 .relation = .exact,
1132 .expression = 4,
1133 }},
1134 };
1135 try std.testing.expect(validate(Limits, value) == null);
1136 try std.testing.expectEqual(LeafClass.signed_integer, value.inputs[0].leaf_class);
1137 try std.testing.expectEqual(LeafClass.collection, value.inputs[1].leaf_class);
1138 try std.testing.expectEqual(LeafClass.byte_collection, value.inputs[2].leaf_class);
1139 try std.testing.expectEqual(@as(usize, 48), inputs_max);
1140 try std.testing.expectEqual(@as(u16, 2), input_bound_version);
1141 try std.testing.expect(classifyLeaf(u128) == null);
1142 try std.testing.expect(classifyLeaf(i128) == null);
1143 }
1144
1145 test "capacity Spec digest excludes field-name diagnostics" {
1146 const input = InputView{
1147 .id = "count",
1148 .field_path = .{
1149 .ordinals = .{ 1, 0, 0, 0, 0, 0, 0, 0 },
1150 .len = 1,
1151 .diagnostic = "count",
1152 },
1153 };
1154 var renamed = input;
1155 renamed.field_path.diagnostic = "renamed_count";
1156 const nodes = [_]Node{.{ .input = 0 }};
1157 const assertions = [_]Assertion{.{
1158 .scope = .closure_total,
1159 .measure = .retained,
1160 .relation = .exact,
1161 .expression = 0,
1162 }};
1163 const left = digest(.{
1164 .inputs = &.{input},
1165 .nodes = &nodes,
1166 .assertions = &assertions,
1167 });
1168 const right = digest(.{
1169 .inputs = &.{renamed},
1170 .nodes = &nodes,
1171 .assertions = &assertions,
1172 });
1173 try std.testing.expectEqualSlices(u8, &left, &right);
1174 }