lib/closure/src/project/check.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const schema = @import("../schema/root.zig");
3
4 pub const Scratch = struct {
5 visited: []u8,
6 queue: []u32,
7 };
8
9 pub const WorkCardinality = struct {
10 nodes: usize,
11 edges: usize,
12 artifacts: usize,
13 ranges: usize,
14 digests: usize,
15 provenance_parents: usize,
16 source_records: usize,
17 build_records: usize,
18 authorities: usize,
19 lineage_references: usize,
20 service_descriptors: usize,
21 residual_roots: usize,
22 claims: usize,
23 claim_nodes: usize,
24 };
25
26 pub const WorkBoundError = error{WorkArithmeticOverflow};
27
28 pub const Reason = enum(u8) {
29 none,
30 claim_missing,
31 work_limit,
32 visited_capacity,
33 frontier_capacity,
34 generation_root_unknown,
35 claim_name_unknown,
36 profile_unknown,
37 edge_mask_unsupported,
38 artifact_missing,
39 artifact_ambiguous,
40 artifact_node_missing,
41 artifact_digest_unknown,
42 artifact_digest_mismatch,
43 artifact_witness_unknown,
44 byte_range_missing,
45 byte_range_digest_unknown,
46 byte_range_witness_unknown,
47 byte_range_overflow,
48 byte_range_out_of_bounds,
49 byte_range_overlap,
50 byte_coverage_gap,
51 foreign_only_executable,
52 node_identity_ambiguous,
53 node_evidence_unknown,
54 claim_root_missing,
55 claim_root_node_missing,
56 artifact_unreachable,
57 treatment_missing,
58 treatment_unknown,
59 treatment_conflict,
60 treatment_forbidden,
61 origin_evidence_missing,
62 origin_treatment_forbidden,
63 edge_kind_omitted,
64 predecessor_omitted,
65 edge_target_missing,
66 oracle_influence,
67 authority_evidence_missing,
68 authority_edge_missing,
69 authority_target_missing,
70 authority_unknown,
71 authority_forbidden,
72 service_evidence_missing,
73 service_evidence_unknown,
74 service_requirement_mismatch,
75 record_reference_missing,
76 record_evidence_unknown,
77 };
78
79 pub const Result = struct {
80 verdict: schema.Verdict,
81 reason: Reason,
82 work: u64,
83 high_water: u32,
84 };
85
86 const TreatmentLookup = struct {
87 value: ?schema.Treatment = null,
88 complete: bool = true,
89 };
90
91 const Checker = struct {
92 input: schema.GenerationInput,
93 claim_id: schema.ClaimId,
94 scratch: Scratch,
95 work_limit: u64,
96 work: u64 = 0,
97 high_water: u32 = 0,
98 first_refutation: ?Reason = null,
99 first_inconclusive: ?Reason = null,
100 stopped: bool = false,
101 graph_complete: bool = true,
102 queue_head: usize = 0,
103 queue_count: usize = 0,
104
105 fn run(self: *Checker) Result {
106 const claim = self.findClaim();
107 if (self.stopped) return self.finish();
108 if (claim == null) {
109 return .{
110 .verdict = .not_exercised,
111 .reason = .claim_missing,
112 .work = self.work,
113 .high_water = self.high_water,
114 };
115 }
116 self.checkClaim(claim.?);
117 const artifact = self.findClaimArtifact(claim.?);
118 if (artifact) |selected| self.checkExactArtifact(claim.?, selected);
119 self.checkNodeIdentity();
120 if (!self.stopped) self.walk(claim.?);
121 if (artifact) |selected| self.checkArtifactReachability(selected);
122 if (!self.stopped) self.checkIncludedNodes();
123 if (!self.stopped) self.checkIncludedEdges(claim.?);
124 if (!self.stopped) self.checkAuthorities(claim.?);
125 if (!self.stopped) self.checkServices();
126 if (!self.stopped) self.checkRecords();
127 return self.finish();
128 }
129
130 fn tick(self: *Checker) bool {
131 if (self.stopped) return false;
132 if (self.work == self.work_limit) {
133 self.noteInconclusive(.work_limit);
134 self.stopped = true;
135 self.graph_complete = false;
136 return false;
137 }
138 self.work += 1;
139 return true;
140 }
141
142 fn noteRefuted(self: *Checker, reason: Reason) void {
143 if (self.first_refutation == null) self.first_refutation = reason;
144 }
145
146 fn noteInconclusive(self: *Checker, reason: Reason) void {
147 if (self.first_inconclusive == null) {
148 self.first_inconclusive = reason;
149 }
150 }
151
152 fn finish(self: *const Checker) Result {
153 if (self.first_refutation) |reason| {
154 return .{
155 .verdict = .refuted,
156 .reason = reason,
157 .work = self.work,
158 .high_water = self.high_water,
159 };
160 }
161 if (self.first_inconclusive) |reason| {
162 return .{
163 .verdict = .inconclusive,
164 .reason = reason,
165 .work = self.work,
166 .high_water = self.high_water,
167 };
168 }
169 return .{
170 .verdict = .pass,
171 .reason = .none,
172 .work = self.work,
173 .high_water = self.high_water,
174 };
175 }
176
177 fn findClaim(self: *Checker) ?*const schema.Claim {
178 var found: ?*const schema.Claim = null;
179 for (self.input.claims) |*claim| {
180 if (!self.tick()) return found;
181 if (claim.id != self.claim_id) continue;
182 if (found != null) self.noteInconclusive(.record_reference_missing);
183 if (found == null) found = claim;
184 }
185 return found;
186 }
187
188 fn checkClaim(self: *Checker, claim: *const schema.Claim) void {
189 if (!self.tick()) return;
190 if (!self.input.root.isKnown()) {
191 self.noteInconclusive(.generation_root_unknown);
192 }
193 if (claim.name.isEmpty()) self.noteInconclusive(.claim_name_unknown);
194 if (!claim.profiles.known()) self.noteInconclusive(.profile_unknown);
195 if (!claim.artifact_digest.isKnown()) {
196 self.noteInconclusive(.artifact_digest_unknown);
197 }
198 if ((claim.traversed_edges & ~allEdgeBits()) != 0) {
199 self.noteInconclusive(.edge_mask_unsupported);
200 }
201 }
202
203 fn findClaimArtifact(
204 self: *Checker,
205 claim: *const schema.Claim,
206 ) ?*const schema.Artifact {
207 var found: ?*const schema.Artifact = null;
208 for (self.input.artifacts) |*artifact| {
209 if (!self.tick()) return found;
210 if (artifact.id != claim.artifact) continue;
211 if (found != null) self.noteInconclusive(.artifact_ambiguous);
212 if (found == null) found = artifact;
213 }
214 if (found == null and !self.stopped) {
215 self.noteInconclusive(.artifact_missing);
216 }
217 return found;
218 }
219
220 fn checkExactArtifact(
221 self: *Checker,
222 claim: *const schema.Claim,
223 artifact: *const schema.Artifact,
224 ) void {
225 if (!self.tick()) return;
226 if (!artifact.digest.isKnown()) {
227 self.noteInconclusive(.artifact_digest_unknown);
228 } else if (claim.artifact_digest.isKnown() and
229 !artifact.digest.eql(&claim.artifact_digest))
230 {
231 self.noteRefuted(.artifact_digest_mismatch);
232 }
233 if (artifact.witness == .unknown) {
234 self.noteInconclusive(.artifact_witness_unknown);
235 }
236 self.checkCoverage(artifact);
237 }
238
239 fn checkCoverage(
240 self: *Checker,
241 artifact: *const schema.Artifact,
242 ) void {
243 var range_count: usize = 0;
244 var covered: u64 = 0;
245 var arithmetic_complete = true;
246 for (self.input.ranges, 0..) |*range, left_index| {
247 if (!self.tick()) return;
248 if (range.artifact != artifact.id) continue;
249 range_count += 1;
250 self.checkRangeEvidence(artifact, range);
251 covered = std.math.add(u64, covered, range.length) catch {
252 self.noteInconclusive(.byte_range_overflow);
253 arithmetic_complete = false;
254 continue;
255 };
256 self.checkRangeOverlaps(artifact.id, left_index, range);
257 }
258 if (range_count == 0 and artifact.byte_length != 0) {
259 self.noteRefuted(.byte_range_missing);
260 } else if (arithmetic_complete and covered != artifact.byte_length) {
261 self.noteRefuted(.byte_coverage_gap);
262 }
263 }
264
265 fn checkRangeEvidence(
266 self: *Checker,
267 artifact: *const schema.Artifact,
268 range: *const schema.ByteRange,
269 ) void {
270 if (!range.digest.isKnown()) {
271 self.noteInconclusive(.byte_range_digest_unknown);
272 }
273 if (range.witness == .unknown) {
274 self.noteInconclusive(.byte_range_witness_unknown);
275 }
276 const end = std.math.add(u64, range.offset, range.length) catch {
277 self.noteInconclusive(.byte_range_overflow);
278 return;
279 };
280 if (end > artifact.byte_length) {
281 self.noteRefuted(.byte_range_out_of_bounds);
282 }
283 if (range.length == 0) self.noteRefuted(.byte_coverage_gap);
284 if (range.executable and range.witness == .foreign) {
285 self.noteRefuted(.foreign_only_executable);
286 }
287 if (range.executable and artifact.witness == .foreign) {
288 self.noteRefuted(.foreign_only_executable);
289 }
290 }
291
292 fn checkRangeOverlaps(
293 self: *Checker,
294 artifact_id: schema.RecordId,
295 left_index: usize,
296 left: *const schema.ByteRange,
297 ) void {
298 const left_end = std.math.add(u64, left.offset, left.length) catch return;
299 for (self.input.ranges[left_index + 1 ..]) |*right| {
300 if (!self.tick()) return;
301 if (right.artifact != artifact_id) continue;
302 const right_end = std.math.add(
303 u64,
304 right.offset,
305 right.length,
306 ) catch continue;
307 if (left.offset < right_end and right.offset < left_end) {
308 self.noteRefuted(.byte_range_overlap);
309 }
310 }
311 }
312
313 fn checkNodeIdentity(self: *Checker) void {
314 for (self.input.nodes, 0..) |node, left_index| {
315 if (!self.tick()) return;
316 if (node.id == 0) {
317 self.noteInconclusive(.node_evidence_unknown);
318 }
319 for (self.input.nodes[0..left_index]) |right| {
320 if (!self.tick()) return;
321 if (node.id == right.id) {
322 self.noteInconclusive(.node_identity_ambiguous);
323 }
324 }
325 }
326 }
327
328 fn walk(self: *Checker, claim: *const schema.Claim) void {
329 if (!self.prepareVisited()) return;
330 const roots_complete = self.seedRoots();
331 if (!roots_complete) self.graph_complete = false;
332 while (self.queue_count != 0 and !self.stopped) {
333 const node_index = self.dequeue();
334 if (!self.tick()) return;
335 const node_id = self.input.nodes[node_index].id;
336 self.followEdges(claim, node_id);
337 }
338 }
339
340 fn prepareVisited(self: *Checker) bool {
341 if (self.input.nodes.len > std.math.maxInt(u32)) {
342 self.noteInconclusive(.visited_capacity);
343 self.graph_complete = false;
344 return false;
345 }
346 const clear_count = @min(
347 self.input.nodes.len,
348 self.scratch.visited.len,
349 );
350 for (self.scratch.visited[0..clear_count]) |*visited| {
351 if (!self.tick()) return false;
352 visited.* = 0;
353 }
354 if (self.scratch.visited.len < self.input.nodes.len) {
355 self.noteInconclusive(.visited_capacity);
356 self.graph_complete = false;
357 return false;
358 }
359 return true;
360 }
361
362 fn seedRoots(self: *Checker) bool {
363 var roots: usize = 0;
364 var complete = true;
365 for (self.input.residual_roots) |root| {
366 if (!self.tick()) return false;
367 if (root.claim != self.claim_id) continue;
368 roots += 1;
369 const node_index = self.findNodeIndex(root.node);
370 if (node_index == null) {
371 self.noteInconclusive(.claim_root_node_missing);
372 complete = false;
373 continue;
374 }
375 if (!self.enqueue(node_index.?)) complete = false;
376 }
377 if (roots == 0 and !self.stopped) {
378 self.noteRefuted(.claim_root_missing);
379 }
380 return complete and !self.stopped;
381 }
382
383 fn followEdges(
384 self: *Checker,
385 claim: *const schema.Claim,
386 node_id: schema.NodeId,
387 ) void {
388 for (self.input.edges) |edge| {
389 if (!self.tick()) return;
390 if (edge.source != node_id) continue;
391 if ((claim.traversed_edges & schema.edgeBit(edge.kind)) == 0) {
392 continue;
393 }
394 const target_index = self.findNodeIndex(edge.target);
395 if (target_index == null) {
396 self.noteInconclusive(.edge_target_missing);
397 self.graph_complete = false;
398 continue;
399 }
400 if (!self.enqueue(target_index.?)) self.graph_complete = false;
401 }
402 }
403
404 fn findNodeIndex(
405 self: *Checker,
406 node_id: schema.NodeId,
407 ) ?usize {
408 for (self.input.nodes, 0..) |node, index| {
409 if (!self.tick()) return null;
410 if (node.id == node_id) return index;
411 }
412 return null;
413 }
414
415 fn enqueue(self: *Checker, node_index: usize) bool {
416 if (self.scratch.visited[node_index] != 0) return true;
417 if (self.queue_count == self.scratch.queue.len) {
418 self.noteInconclusive(.frontier_capacity);
419 return false;
420 }
421 const tail = (self.queue_head + self.queue_count) %
422 self.scratch.queue.len;
423 self.scratch.queue[tail] = @intCast(node_index);
424 self.scratch.visited[node_index] = 1;
425 self.queue_count += 1;
426 self.high_water = @max(
427 self.high_water,
428 @as(u32, @intCast(self.queue_count)),
429 );
430 return true;
431 }
432
433 fn dequeue(self: *Checker) usize {
434 std.debug.assert(self.queue_count > 0);
435 const node_index = self.scratch.queue[self.queue_head];
436 self.queue_head = (self.queue_head + 1) % self.scratch.queue.len;
437 self.queue_count -= 1;
438 return node_index;
439 }
440
441 fn checkArtifactReachability(
442 self: *Checker,
443 artifact: *const schema.Artifact,
444 ) void {
445 if (!self.graph_complete or self.stopped) return;
446 const node_index = self.findNodeIndex(artifact.node);
447 if (node_index == null) {
448 if (!self.stopped) {
449 self.noteInconclusive(.artifact_node_missing);
450 }
451 return;
452 }
453 if (self.scratch.visited[node_index.?] == 0) {
454 self.noteRefuted(.artifact_unreachable);
455 }
456 }
457
458 fn checkIncludedNodes(self: *Checker) void {
459 for (self.input.nodes, 0..) |*node, index| {
460 if (!self.tick()) return;
461 if (!self.isVisited(index)) continue;
462 self.checkNodeEvidence(node);
463 const treatment = self.findTreatment(node.id);
464 if (!treatment.complete) return;
465 if (treatment.value == null) {
466 self.noteInconclusive(.treatment_missing);
467 continue;
468 }
469 if (treatment.value.? == .unknown) {
470 self.noteInconclusive(.treatment_unknown);
471 }
472 if (treatment.value.? == .forbidden) {
473 self.noteRefuted(.treatment_forbidden);
474 }
475 self.checkOriginEvidence(node, treatment.value.?);
476 }
477 }
478
479 fn checkNodeEvidence(
480 self: *Checker,
481 node: *const schema.Node,
482 ) void {
483 if (node.descriptor.isEmpty() or
484 !node.identity.isKnown() or
485 node.subject_kind == .unknown or
486 node.material_role == .unknown or
487 node.origin == .unknown or
488 node.phases == 0 or
489 (node.phases & ~allPhaseBits()) != 0 or
490 node.execution_locus == .unknown or
491 node.owner.isEmpty() or
492 node.authority == .unknown or
493 node.artifact_kind == .unknown)
494 {
495 self.noteInconclusive(.node_evidence_unknown);
496 }
497 }
498
499 fn findTreatment(
500 self: *Checker,
501 node_id: schema.NodeId,
502 ) TreatmentLookup {
503 var lookup = TreatmentLookup{};
504 for (self.input.residual_roots) |root| {
505 if (!self.tick()) return .{ .complete = false };
506 if (root.claim != self.claim_id or root.node != node_id) continue;
507 mergeTreatment(self, &lookup, root.treatment);
508 }
509 for (self.input.claim_nodes) |entry| {
510 if (!self.tick()) return .{ .complete = false };
511 if (entry.claim != self.claim_id or entry.node != node_id) continue;
512 mergeTreatment(self, &lookup, entry.treatment);
513 }
514 return lookup;
515 }
516
517 fn checkIncludedEdges(
518 self: *Checker,
519 claim: *const schema.Claim,
520 ) void {
521 for (self.input.edges) |*edge| {
522 if (!self.tick()) return;
523 const source_index = self.findNodeIndex(edge.source);
524 if (source_index == null) continue;
525 if (!self.isVisited(source_index.?)) {
526 const target_index = self.findNodeIndex(edge.target);
527 if (self.graph_complete and
528 target_index != null and
529 self.isVisited(target_index.?))
530 {
531 self.noteRefuted(.predecessor_omitted);
532 }
533 continue;
534 }
535 if ((claim.traversed_edges & schema.edgeBit(edge.kind)) == 0) {
536 self.noteRefuted(.edge_kind_omitted);
537 continue;
538 }
539 const target_index = self.findNodeIndex(edge.target);
540 if (target_index == null) {
541 if (!self.stopped) {
542 self.noteInconclusive(.edge_target_missing);
543 }
544 continue;
545 }
546 if (edge.kind == .service_call and
547 !isService(&self.input.nodes[target_index.?]))
548 {
549 self.noteInconclusive(.service_evidence_missing);
550 }
551 const source = &self.input.nodes[source_index.?];
552 const treatment = self.findTreatment(source.id);
553 if (!treatment.complete) return;
554 const validation_only = treatment.value == .validation_only;
555 if ((source.subject_kind == .oracle or validation_only) and
556 edge.kind != .validation)
557 {
558 self.noteRefuted(.oracle_influence);
559 }
560 }
561 }
562
563 fn checkAuthorities(
564 self: *Checker,
565 claim: *const schema.Claim,
566 ) void {
567 const selected = (claim.traversed_edges &
568 schema.edgeBit(.authority_grant)) != 0;
569 if (selected) self.checkAuthorityEdges();
570 for (self.input.authorities) |*authority| {
571 if (!self.tick()) return;
572 const source_index = self.findNodeIndex(authority.source);
573 if (source_index == null) continue;
574 if (!self.isVisited(source_index.?)) {
575 const target_index = self.findNodeIndex(authority.target);
576 if (self.graph_complete and
577 target_index != null and
578 self.isVisited(target_index.?))
579 {
580 self.noteRefuted(.predecessor_omitted);
581 }
582 continue;
583 }
584 if (!selected) {
585 self.noteRefuted(.edge_kind_omitted);
586 continue;
587 }
588 const target_index = self.findNodeIndex(authority.target);
589 if (target_index == null) {
590 if (!self.stopped) {
591 self.noteInconclusive(.authority_target_missing);
592 }
593 continue;
594 }
595 self.checkAuthorityEdgePresent(authority);
596 self.checkAuthorityFlow(authority, target_index.?);
597 }
598 }
599
600 fn checkAuthorityEdges(self: *Checker) void {
601 for (self.input.edges) |edge| {
602 if (!self.tick()) return;
603 if (edge.kind != .authority_grant) continue;
604 const source_index = self.findNodeIndex(edge.source);
605 if (source_index == null or !self.isVisited(source_index.?)) {
606 continue;
607 }
608 var found = false;
609 for (self.input.authorities) |authority| {
610 if (!self.tick()) return;
611 if (authority.source == edge.source and
612 authority.target == edge.target)
613 {
614 found = true;
615 }
616 }
617 if (!found and !self.stopped) {
618 self.noteInconclusive(.authority_evidence_missing);
619 }
620 }
621 }
622
623 fn checkAuthorityEdgePresent(
624 self: *Checker,
625 authority: *const schema.Authority,
626 ) void {
627 var found = false;
628 for (self.input.edges) |edge| {
629 if (!self.tick()) return;
630 if (edge.kind == .authority_grant and
631 edge.source == authority.source and
632 edge.target == authority.target)
633 {
634 found = true;
635 }
636 }
637 if (!found and !self.stopped) {
638 self.noteInconclusive(.authority_edge_missing);
639 }
640 }
641
642 fn checkAuthorityFlow(
643 self: *Checker,
644 authority: *const schema.Authority,
645 target_index: usize,
646 ) void {
647 if (authority.granted == .unknown) {
648 self.noteInconclusive(.authority_unknown);
649 return;
650 }
651 const target = &self.input.nodes[target_index];
652 const treatment = self.findTreatment(target.id);
653 if (!treatment.complete) return;
654 const target_validation = target.authority == .validation or
655 treatment.value == .validation_only;
656 if (target_validation and
657 authority.granted != .validation and
658 authority.granted != .none)
659 {
660 self.noteRefuted(.authority_forbidden);
661 }
662 if (isWorkload(target.material_role) and
663 isPlatformAuthority(authority.granted))
664 {
665 self.noteRefuted(.authority_forbidden);
666 }
667 }
668
669 fn checkServices(self: *Checker) void {
670 for (self.input.nodes, 0..) |*node, index| {
671 if (!self.tick()) return;
672 if (!self.isVisited(index) or !isService(node)) continue;
673 var found = false;
674 var requirement: ?schema.RequirementClass = null;
675 for (self.input.service_descriptors) |*service| {
676 if (!self.tick()) return;
677 if (service.node != node.id) continue;
678 found = true;
679 self.checkServiceEvidence(service);
680 if (requirement != null and
681 requirement.? != service.requirement)
682 {
683 self.noteRefuted(.service_requirement_mismatch);
684 }
685 if (requirement == null) requirement = service.requirement;
686 }
687 if (!found and !self.stopped) {
688 self.noteInconclusive(.service_evidence_missing);
689 continue;
690 }
691 if (requirement) |required| {
692 self.checkServiceTreatment(node.id, required);
693 }
694 }
695 }
696
697 fn checkServiceEvidence(
698 self: *Checker,
699 service: *const schema.ServiceDescriptor,
700 ) void {
701 if (service.provider.isEmpty() or
702 service.protocol.isEmpty() or
703 service.endpoint_rule.isEmpty() or
704 service.trust_anchor.isEmpty() or
705 service.failure_contract.isEmpty() or
706 service.requirement == .unknown)
707 {
708 self.noteInconclusive(.service_evidence_unknown);
709 }
710 }
711
712 fn checkServiceTreatment(
713 self: *Checker,
714 node_id: schema.NodeId,
715 requirement: schema.RequirementClass,
716 ) void {
717 const treatment = self.findTreatment(node_id);
718 if (!treatment.complete or treatment.value == null) return;
719 const actual = treatment.value.?;
720 const matches = switch (requirement) {
721 .required => actual != .optional_user_effect and
722 actual != .validation_only,
723 .optional_user_effect => actual == .optional_user_effect,
724 .validation_only => actual == .validation_only,
725 .unknown => true,
726 };
727 if (!matches) self.noteRefuted(.service_requirement_mismatch);
728 }
729
730 fn checkOriginEvidence(
731 self: *Checker,
732 node: *const schema.Node,
733 treatment: schema.Treatment,
734 ) void {
735 if ((node.origin == .external_unreceipted or
736 node.origin == .platform_supplied) and
737 (treatment == .owned or treatment == .verified))
738 {
739 self.noteRefuted(.origin_treatment_forbidden);
740 }
741 const complete = switch (node.origin) {
742 .owned_source => self.hasSourceEvidence(node.id),
743 .owned_derivation => self.hasDerivationEvidence(node.id),
744 .external_receipted => self.hasExternalReceipt(node.id),
745 else => true,
746 };
747 if (!self.stopped and !complete) {
748 self.noteInconclusive(.origin_evidence_missing);
749 }
750 }
751
752 fn hasSourceEvidence(self: *Checker, node_id: schema.NodeId) bool {
753 var found = false;
754 for (self.input.source_records) |*record| {
755 if (!self.tick()) return false;
756 if (record.node != node_id) continue;
757 if (!record.path.isEmpty() and
758 record.digest.isKnown() and
759 isOwnedWitness(record.witness))
760 {
761 found = true;
762 }
763 }
764 return found;
765 }
766
767 fn hasDerivationEvidence(self: *Checker, node_id: schema.NodeId) bool {
768 var artifact_found = false;
769 for (self.input.artifacts) |*artifact| {
770 if (!self.tick()) return false;
771 if (artifact.node == node_id and
772 artifact.digest.isKnown() and
773 isOwnedWitness(artifact.witness))
774 {
775 artifact_found = true;
776 }
777 }
778 const derivation_found = self.hasBuildOrProvenance(node_id);
779 return artifact_found and derivation_found;
780 }
781
782 fn hasBuildOrProvenance(
783 self: *Checker,
784 node_id: schema.NodeId,
785 ) bool {
786 var found = false;
787 for (self.input.build_records) |*record| {
788 if (!self.tick()) return false;
789 if (record.node == node_id and
790 !record.option.isEmpty() and
791 record.digest.isKnown() and
792 isOwnedWitness(record.witness))
793 {
794 found = true;
795 }
796 }
797 for (self.input.provenance_parents) |record| {
798 if (!self.tick()) return false;
799 if (record.child == node_id) found = true;
800 }
801 return found;
802 }
803
804 fn hasExternalReceipt(self: *Checker, node_id: schema.NodeId) bool {
805 if (self.hasArtifactReceipt(node_id)) return true;
806 if (self.stopped) return false;
807 if (self.hasDigestReceipt(node_id)) return true;
808 if (self.stopped) return false;
809 if (self.hasSourceReceipt(node_id)) return true;
810 if (self.stopped) return false;
811 if (self.hasBuildReceipt(node_id)) return true;
812 if (self.stopped) return false;
813 if (self.hasLineageReceipt(node_id)) return true;
814 if (self.stopped) return false;
815 return self.hasServiceReceipt(node_id);
816 }
817
818 fn hasArtifactReceipt(self: *Checker, node_id: schema.NodeId) bool {
819 for (self.input.artifacts) |*artifact| {
820 if (!self.tick()) return false;
821 if (artifact.node == node_id and
822 artifact.digest.isKnown() and
823 artifact.witness != .unknown)
824 {
825 return true;
826 }
827 }
828 return false;
829 }
830
831 fn hasDigestReceipt(self: *Checker, node_id: schema.NodeId) bool {
832 for (self.input.digests) |*record| {
833 if (!self.tick()) return false;
834 if (record.node == node_id and
835 !record.purpose.isEmpty() and
836 record.digest.isKnown() and
837 record.witness != .unknown)
838 {
839 return true;
840 }
841 }
842 return false;
843 }
844
845 fn hasSourceReceipt(self: *Checker, node_id: schema.NodeId) bool {
846 for (self.input.source_records) |*record| {
847 if (!self.tick()) return false;
848 if (record.node == node_id and
849 !record.path.isEmpty() and
850 record.digest.isKnown() and
851 record.witness != .unknown)
852 {
853 return true;
854 }
855 }
856 return false;
857 }
858
859 fn hasBuildReceipt(self: *Checker, node_id: schema.NodeId) bool {
860 for (self.input.build_records) |*record| {
861 if (!self.tick()) return false;
862 if (record.node == node_id and
863 !record.option.isEmpty() and
864 record.digest.isKnown() and
865 record.witness != .unknown)
866 {
867 return true;
868 }
869 }
870 return false;
871 }
872
873 fn hasLineageReceipt(self: *Checker, node_id: schema.NodeId) bool {
874 for (self.input.lineage_references) |*record| {
875 if (!self.tick()) return false;
876 if (record.node == node_id and
877 !record.descriptor.isEmpty() and
878 record.digest.isKnown() and
879 record.witness != .unknown)
880 {
881 return true;
882 }
883 }
884 return false;
885 }
886
887 fn hasServiceReceipt(self: *Checker, node_id: schema.NodeId) bool {
888 for (self.input.service_descriptors) |*service| {
889 if (!self.tick()) return false;
890 if (service.node != node_id) continue;
891 if (!service.provider.isEmpty() and
892 !service.protocol.isEmpty() and
893 !service.endpoint_rule.isEmpty() and
894 !service.trust_anchor.isEmpty() and
895 !service.failure_contract.isEmpty() and
896 service.requirement != .unknown)
897 {
898 return true;
899 }
900 }
901 return false;
902 }
903
904 fn checkRecords(self: *Checker) void {
905 self.checkArtifacts();
906 if (self.stopped) return;
907 self.checkDigestRecords();
908 if (self.stopped) return;
909 self.checkProvenance();
910 if (self.stopped) return;
911 self.checkSourceRecords();
912 if (self.stopped) return;
913 self.checkBuildRecords();
914 if (self.stopped) return;
915 self.checkLineage();
916 }
917
918 fn checkArtifacts(self: *Checker) void {
919 for (self.input.artifacts) |*artifact| {
920 if (!self.tick()) return;
921 const node_index = self.findNodeIndex(artifact.node);
922 if (node_index == null or !self.isVisited(node_index.?)) continue;
923 if (!artifact.digest.isKnown() or artifact.witness == .unknown) {
924 self.noteInconclusive(.record_evidence_unknown);
925 }
926 self.checkCoverage(artifact);
927 }
928 }
929
930 fn checkDigestRecords(self: *Checker) void {
931 for (self.input.digests) |*record| {
932 if (!self.tick()) return;
933 const node_index = self.findNodeIndex(record.node);
934 if (node_index == null or !self.isVisited(node_index.?)) continue;
935 if (record.purpose.isEmpty() or
936 !record.digest.isKnown() or
937 record.witness == .unknown)
938 {
939 self.noteInconclusive(.record_evidence_unknown);
940 }
941 }
942 }
943
944 fn checkProvenance(self: *Checker) void {
945 for (self.input.provenance_parents) |record| {
946 if (!self.tick()) return;
947 const child_index = self.findNodeIndex(record.child);
948 if (child_index == null or !self.isVisited(child_index.?)) continue;
949 const parent_index = self.findNodeIndex(record.parent);
950 if (parent_index == null and !self.stopped) {
951 self.noteInconclusive(.record_reference_missing);
952 } else if (self.graph_complete and
953 !self.stopped and
954 !self.isVisited(parent_index.?))
955 {
956 self.noteRefuted(.predecessor_omitted);
957 }
958 }
959 }
960
961 fn checkSourceRecords(self: *Checker) void {
962 for (self.input.source_records) |*record| {
963 if (!self.tick()) return;
964 const node_index = self.findNodeIndex(record.node);
965 if (node_index == null or !self.isVisited(node_index.?)) continue;
966 if (record.path.isEmpty() or
967 !record.digest.isKnown() or
968 record.witness == .unknown)
969 {
970 self.noteInconclusive(.record_evidence_unknown);
971 }
972 }
973 }
974
975 fn checkBuildRecords(self: *Checker) void {
976 for (self.input.build_records) |*record| {
977 if (!self.tick()) return;
978 const node_index = self.findNodeIndex(record.node);
979 if (node_index == null or !self.isVisited(node_index.?)) continue;
980 const tool_index = self.findNodeIndex(record.tool);
981 if (tool_index == null and !self.stopped) {
982 self.noteInconclusive(.record_reference_missing);
983 } else if (self.graph_complete and
984 !self.stopped and
985 !self.isVisited(tool_index.?))
986 {
987 self.noteRefuted(.predecessor_omitted);
988 }
989 if (record.option.isEmpty() or
990 !record.digest.isKnown() or
991 record.witness == .unknown)
992 {
993 self.noteInconclusive(.record_evidence_unknown);
994 }
995 }
996 }
997
998 fn checkLineage(self: *Checker) void {
999 for (self.input.lineage_references) |*record| {
1000 if (!self.tick()) return;
1001 const node_index = self.findNodeIndex(record.node);
1002 if (node_index == null or !self.isVisited(node_index.?)) continue;
1003 if (record.descriptor.isEmpty() or
1004 !record.digest.isKnown() or
1005 record.witness == .unknown)
1006 {
1007 self.noteInconclusive(.record_evidence_unknown);
1008 }
1009 }
1010 }
1011
1012 fn isVisited(self: *const Checker, index: usize) bool {
1013 if (index >= self.input.nodes.len) return false;
1014 if (index >= self.scratch.visited.len) return false;
1015 return self.scratch.visited[index] != 0;
1016 }
1017 };
1018
1019 pub fn check(
1020 input: schema.GenerationInput,
1021 claim_id: schema.ClaimId,
1022 scratch: Scratch,
1023 work_limit: u64,
1024 ) Result {
1025 var checker = Checker{
1026 .input = input,
1027 .claim_id = claim_id,
1028 .scratch = scratch,
1029 .work_limit = work_limit,
1030 };
1031 return checker.run();
1032 }
1033
1034 pub fn maximumWork(cardinality: WorkCardinality) WorkBoundError!usize {
1035 const node_pairs = try triangular(cardinality.nodes);
1036 const range_pairs = try triangular(cardinality.ranges);
1037 const origin_scans = try sum(&.{
1038 try product(&.{ 2, cardinality.source_records }),
1039 try product(&.{ 2, cardinality.artifacts }),
1040 try product(&.{ 2, cardinality.build_records }),
1041 cardinality.provenance_parents,
1042 cardinality.digests,
1043 cardinality.lineage_references,
1044 cardinality.service_descriptors,
1045 });
1046 return sum(&.{
1047 try setupWork(cardinality, node_pairs, range_pairs),
1048 try traversalWork(cardinality, origin_scans),
1049 try policyWork(cardinality),
1050 try recordWork(cardinality, range_pairs),
1051 });
1052 }
1053
1054 fn setupWork(
1055 cardinality: WorkCardinality,
1056 node_pairs: usize,
1057 range_pairs: usize,
1058 ) WorkBoundError!usize {
1059 return sum(&.{
1060 cardinality.claims,
1061 1,
1062 cardinality.artifacts,
1063 1,
1064 cardinality.ranges,
1065 range_pairs,
1066 cardinality.nodes,
1067 node_pairs,
1068 });
1069 }
1070
1071 fn traversalWork(
1072 cardinality: WorkCardinality,
1073 origin_scans: usize,
1074 ) WorkBoundError!usize {
1075 return sum(&.{
1076 cardinality.nodes,
1077 cardinality.residual_roots,
1078 try product(&.{ cardinality.residual_roots, cardinality.nodes }),
1079 cardinality.nodes,
1080 try product(&.{ cardinality.nodes, cardinality.edges }),
1081 try product(&.{
1082 cardinality.nodes,
1083 cardinality.nodes,
1084 cardinality.edges,
1085 }),
1086 cardinality.nodes,
1087 try product(&.{
1088 cardinality.nodes,
1089 try sum(&.{
1090 cardinality.residual_roots,
1091 cardinality.claim_nodes,
1092 origin_scans,
1093 }),
1094 }),
1095 });
1096 }
1097
1098 fn policyWork(
1099 cardinality: WorkCardinality,
1100 ) WorkBoundError!usize {
1101 return sum(&.{
1102 try product(&.{
1103 cardinality.edges,
1104 try sum(&.{
1105 1,
1106 try product(&.{ 2, cardinality.nodes }),
1107 cardinality.residual_roots,
1108 cardinality.claim_nodes,
1109 }),
1110 }),
1111 try product(&.{
1112 cardinality.edges,
1113 try sum(&.{
1114 1,
1115 cardinality.nodes,
1116 cardinality.authorities,
1117 }),
1118 }),
1119 try product(&.{
1120 cardinality.authorities,
1121 try sum(&.{
1122 1,
1123 try product(&.{ 2, cardinality.nodes }),
1124 cardinality.edges,
1125 cardinality.residual_roots,
1126 cardinality.claim_nodes,
1127 }),
1128 }),
1129 try product(&.{
1130 cardinality.nodes,
1131 try sum(&.{
1132 1,
1133 cardinality.service_descriptors,
1134 cardinality.residual_roots,
1135 cardinality.claim_nodes,
1136 }),
1137 }),
1138 });
1139 }
1140
1141 fn recordWork(
1142 cardinality: WorkCardinality,
1143 range_pairs: usize,
1144 ) WorkBoundError!usize {
1145 return sum(&.{
1146 try product(&.{
1147 cardinality.artifacts,
1148 try sum(&.{
1149 1,
1150 cardinality.nodes,
1151 cardinality.ranges,
1152 range_pairs,
1153 }),
1154 }),
1155 try product(&.{
1156 cardinality.digests,
1157 try sum(&.{ 1, cardinality.nodes }),
1158 }),
1159 try product(&.{
1160 cardinality.provenance_parents,
1161 try sum(&.{ 1, try product(&.{ 2, cardinality.nodes }) }),
1162 }),
1163 try product(&.{
1164 cardinality.source_records,
1165 try sum(&.{ 1, cardinality.nodes }),
1166 }),
1167 try product(&.{
1168 cardinality.build_records,
1169 try sum(&.{ 1, try product(&.{ 2, cardinality.nodes }) }),
1170 }),
1171 try product(&.{
1172 cardinality.lineage_references,
1173 try sum(&.{ 1, cardinality.nodes }),
1174 }),
1175 });
1176 }
1177
1178 fn triangular(value: usize) WorkBoundError!usize {
1179 if (value == 0) return 0;
1180 return (try product(&.{ value, value - 1 })) / 2;
1181 }
1182
1183 fn product(values: []const usize) WorkBoundError!usize {
1184 var result: usize = 1;
1185 for (values) |value| result = std.math.mul(usize, result, value) catch
1186 return error.WorkArithmeticOverflow;
1187 return result;
1188 }
1189
1190 fn sum(values: []const usize) WorkBoundError!usize {
1191 var result: usize = 0;
1192 for (values) |value| result = try plus(result, value);
1193 return result;
1194 }
1195
1196 fn plus(left: usize, right: usize) WorkBoundError!usize {
1197 return std.math.add(usize, left, right) catch
1198 error.WorkArithmeticOverflow;
1199 }
1200
1201 fn mergeTreatment(
1202 checker: *Checker,
1203 lookup: *TreatmentLookup,
1204 treatment: schema.Treatment,
1205 ) void {
1206 if (lookup.value != null and lookup.value.? != treatment) {
1207 checker.noteRefuted(.treatment_conflict);
1208 }
1209 if (lookup.value == null) lookup.value = treatment;
1210 }
1211
1212 fn allEdgeBits() schema.EdgeSet {
1213 var bits: schema.EdgeSet = 0;
1214 for (std.meta.tags(schema.EdgeKind)) |kind| bits |= schema.edgeBit(kind);
1215 return bits;
1216 }
1217
1218 fn allPhaseBits() schema.PhaseSet {
1219 var bits: schema.PhaseSet = 0;
1220 for (std.meta.tags(schema.Phase)) |phase| bits |= schema.phaseBit(phase);
1221 return bits;
1222 }
1223
1224 fn isOwnedWitness(witness: schema.WitnessKind) bool {
1225 return witness == .owned or witness == .differential;
1226 }
1227
1228 fn isWorkload(role: schema.MaterialRole) bool {
1229 return switch (role) {
1230 .native_workload,
1231 .linux_compatibility,
1232 .model,
1233 .user_payload,
1234 => true,
1235 else => false,
1236 };
1237 }
1238
1239 fn isPlatformAuthority(authority: schema.GrantedAuthority) bool {
1240 return switch (authority) {
1241 .admission,
1242 .update,
1243 .closure_ledger,
1244 .signing,
1245 .root,
1246 .delegation,
1247 => true,
1248 else => false,
1249 };
1250 }
1251
1252 fn isService(node: *const schema.Node) bool {
1253 return node.subject_kind == .service or
1254 node.artifact_kind == .service or
1255 node.execution_locus == .remote_service;
1256 }
1257
1258 const Fixture = struct {
1259 nodes: [3]schema.Node,
1260 edges: [2]schema.Edge,
1261 artifacts: [1]schema.Artifact,
1262 ranges: [2]schema.ByteRange,
1263 provenance_parents: [1]schema.ProvenanceParent,
1264 source_records: [1]schema.SourceRecord,
1265 service_descriptors: [1]schema.ServiceDescriptor,
1266 residual_roots: [1]schema.ResidualRoot,
1267 claims: [1]schema.Claim,
1268 claim_nodes: [3]schema.ClaimNode,
1269
1270 fn init() !Fixture {
1271 const artifact_digest = knownDigest(2);
1272 return .{
1273 .nodes = try fixtureNodes(),
1274 .edges = .{
1275 .{ .id = 10, .source = 1, .target = 2, .kind = .derivation },
1276 .{ .id = 11, .source = 2, .target = 3, .kind = .service_call },
1277 },
1278 .artifacts = .{.{
1279 .id = 20,
1280 .node = 2,
1281 .byte_length = 4,
1282 .digest = artifact_digest,
1283 .witness = .owned,
1284 }},
1285 .ranges = fixtureRanges(),
1286 .provenance_parents = .{.{
1287 .id = 29,
1288 .child = 2,
1289 .parent = 1,
1290 }},
1291 .source_records = .{.{
1292 .id = 30,
1293 .node = 1,
1294 .path = try schema.Descriptor.init("src/kernel.zig"),
1295 .digest = knownDigest(1),
1296 .witness = .owned,
1297 }},
1298 .service_descriptors = .{try fixtureService()},
1299 .residual_roots = .{.{
1300 .id = 40,
1301 .claim = 1,
1302 .node = 1,
1303 .treatment = .owned,
1304 }},
1305 .claims = .{.{
1306 .id = 1,
1307 .name = try schema.Name.init("strict"),
1308 .artifact = 20,
1309 .artifact_digest = artifact_digest,
1310 .profiles = try fixtureProfiles(),
1311 .traversed_edges = schema.edgeBit(.derivation) |
1312 schema.edgeBit(.service_call),
1313 }},
1314 .claim_nodes = .{
1315 .{ .id = 50, .claim = 1, .node = 1, .treatment = .owned },
1316 .{ .id = 51, .claim = 1, .node = 2, .treatment = .owned },
1317 .{
1318 .id = 52,
1319 .claim = 1,
1320 .node = 3,
1321 .treatment = .residual_assumption,
1322 },
1323 },
1324 };
1325 }
1326
1327 fn input(self: *const Fixture) schema.GenerationInput {
1328 return .{
1329 .id = 1,
1330 .root = knownDigest(9),
1331 .nodes = &self.nodes,
1332 .edges = &self.edges,
1333 .artifacts = &self.artifacts,
1334 .ranges = &self.ranges,
1335 .digests = &.{},
1336 .provenance_parents = &self.provenance_parents,
1337 .source_records = &self.source_records,
1338 .build_records = &.{},
1339 .authorities = &.{},
1340 .lineage_references = &.{},
1341 .service_descriptors = &self.service_descriptors,
1342 .residual_roots = &self.residual_roots,
1343 .claims = &self.claims,
1344 .claim_nodes = &self.claim_nodes,
1345 };
1346 }
1347 };
1348
1349 test "projection passes a complete directed rooted claim with fixed work" {
1350 const fixture = try Fixture.init();
1351 const input = fixture.input();
1352 const work_bound = try maximumWork(.{
1353 .nodes = input.nodes.len,
1354 .edges = input.edges.len,
1355 .artifacts = input.artifacts.len,
1356 .ranges = input.ranges.len,
1357 .digests = input.digests.len,
1358 .provenance_parents = input.provenance_parents.len,
1359 .source_records = input.source_records.len,
1360 .build_records = input.build_records.len,
1361 .authorities = input.authorities.len,
1362 .lineage_references = input.lineage_references.len,
1363 .service_descriptors = input.service_descriptors.len,
1364 .residual_roots = input.residual_roots.len,
1365 .claims = input.claims.len,
1366 .claim_nodes = input.claim_nodes.len,
1367 });
1368 var visited: [fixture.nodes.len]u8 = undefined;
1369 var queue: [fixture.nodes.len]u32 = undefined;
1370 const first = check(
1371 input,
1372 1,
1373 .{ .visited = &visited, .queue = &queue },
1374 work_bound,
1375 );
1376 const second = check(
1377 input,
1378 1,
1379 .{ .visited = &visited, .queue = &queue },
1380 work_bound,
1381 );
1382 try std.testing.expectEqual(schema.Verdict.pass, first.verdict);
1383 try std.testing.expectEqual(Reason.none, first.reason);
1384 try std.testing.expectEqual(@as(u64, 93), first.work);
1385 try std.testing.expect(first.work <= work_bound);
1386 try std.testing.expectEqual(first.work, second.work);
1387 try std.testing.expectEqual(@as(u32, 1), first.high_water);
1388 }
1389
1390 test "represented predecessor outside the rooted projection refutes" {
1391 const fixture = try Fixture.init();
1392 var nodes = try fixtureNodesWithHidden(&fixture);
1393 var edges = [_]schema.Edge{
1394 fixture.edges[0],
1395 fixture.edges[1],
1396 .{ .id = 12, .source = 4, .target = 2, .kind = .derivation },
1397 };
1398 var input = fixture.input();
1399 input.nodes = &nodes;
1400 input.edges = &edges;
1401 var visited: [nodes.len]u8 = undefined;
1402 var queue: [nodes.len]u32 = undefined;
1403 const selected = check(
1404 input,
1405 1,
1406 .{ .visited = &visited, .queue = &queue },
1407 10_000,
1408 );
1409 try std.testing.expectEqual(schema.Verdict.refuted, selected.verdict);
1410 try std.testing.expectEqual(
1411 Reason.predecessor_omitted,
1412 selected.reason,
1413 );
1414 edges[2].kind = .build_influence;
1415 const omitted_kind = check(
1416 input,
1417 1,
1418 .{ .visited = &visited, .queue = &queue },
1419 10_000,
1420 );
1421 try std.testing.expectEqual(schema.Verdict.refuted, omitted_kind.verdict);
1422 try std.testing.expectEqual(
1423 Reason.predecessor_omitted,
1424 omitted_kind.reason,
1425 );
1426 }
1427
1428 test "incomplete traversal does not refute an unvisited predecessor" {
1429 const fixture = try Fixture.init();
1430 var nodes = try fixtureNodesWithHidden(&fixture);
1431 var edges = [_]schema.Edge{
1432 fixture.edges[0],
1433 fixture.edges[1],
1434 .{ .id = 12, .source = 4, .target = 2, .kind = .derivation },
1435 .{ .id = 13, .source = 1, .target = 4, .kind = .derivation },
1436 };
1437 var input = fixture.input();
1438 input.nodes = &nodes;
1439 input.edges = &edges;
1440 var visited: [nodes.len]u8 = undefined;
1441 var queue: [1]u32 = undefined;
1442 const result = check(
1443 input,
1444 1,
1445 .{ .visited = &visited, .queue = &queue },
1446 10_000,
1447 );
1448 try std.testing.expectEqual(schema.Verdict.inconclusive, result.verdict);
1449 try std.testing.expectEqual(Reason.frontier_capacity, result.reason);
1450 }
1451
1452 test "authority provenance and build predecessors must be included" {
1453 const fixture = try Fixture.init();
1454 var nodes = try fixtureNodesWithHidden(&fixture);
1455 var input = fixture.input();
1456 input.nodes = &nodes;
1457 var visited: [nodes.len]u8 = undefined;
1458 var queue: [nodes.len]u32 = undefined;
1459
1460 var authorities = [_]schema.Authority{.{
1461 .id = 60,
1462 .source = 4,
1463 .target = 2,
1464 .granted = .none,
1465 }};
1466 input.authorities = &authorities;
1467 const authority = check(
1468 input,
1469 1,
1470 .{ .visited = &visited, .queue = &queue },
1471 10_000,
1472 );
1473 try expectPredecessorOmitted(authority);
1474
1475 var parents = [_]schema.ProvenanceParent{
1476 fixture.provenance_parents[0],
1477 .{ .id = 61, .child = 2, .parent = 4 },
1478 };
1479 input.authorities = &.{};
1480 input.provenance_parents = &parents;
1481 const provenance = check(
1482 input,
1483 1,
1484 .{ .visited = &visited, .queue = &queue },
1485 10_000,
1486 );
1487 try expectPredecessorOmitted(provenance);
1488
1489 var builds = [_]schema.BuildRecord{.{
1490 .id = 62,
1491 .node = 2,
1492 .tool = 4,
1493 .option = try schema.Descriptor.init("hidden tool"),
1494 .digest = knownDigest(11),
1495 .witness = .owned,
1496 }};
1497 input.provenance_parents = &fixture.provenance_parents;
1498 input.build_records = &builds;
1499 const build = check(
1500 input,
1501 1,
1502 .{ .visited = &visited, .queue = &queue },
1503 10_000,
1504 );
1505 try expectPredecessorOmitted(build);
1506 }
1507
1508 test "projection reports a missing claim as not exercised" {
1509 const fixture = try Fixture.init();
1510 var visited: [fixture.nodes.len]u8 = undefined;
1511 var queue: [fixture.nodes.len]u32 = undefined;
1512 const result = check(
1513 fixture.input(),
1514 99,
1515 .{ .visited = &visited, .queue = &queue },
1516 10_000,
1517 );
1518 try std.testing.expectEqual(schema.Verdict.not_exercised, result.verdict);
1519 try std.testing.expectEqual(Reason.claim_missing, result.reason);
1520 }
1521
1522 test "artifact mismatch refutes despite unknown profile evidence" {
1523 var fixture = try Fixture.init();
1524 fixture.claims[0].artifact_digest = knownDigest(8);
1525 fixture.claims[0].profiles.executable.body_sha256 = schema.Digest.zero();
1526 var visited: [fixture.nodes.len]u8 = undefined;
1527 var queue: [fixture.nodes.len]u32 = undefined;
1528 const result = check(
1529 fixture.input(),
1530 1,
1531 .{ .visited = &visited, .queue = &queue },
1532 10_000,
1533 );
1534 try std.testing.expectEqual(schema.Verdict.refuted, result.verdict);
1535 try std.testing.expectEqual(Reason.artifact_digest_mismatch, result.reason);
1536 }
1537
1538 test "unknown required profile is inconclusive" {
1539 var fixture = try Fixture.init();
1540 fixture.claims[0].profiles.executable.body_sha256 = schema.Digest.zero();
1541 var visited: [fixture.nodes.len]u8 = undefined;
1542 var queue: [fixture.nodes.len]u32 = undefined;
1543 const result = check(
1544 fixture.input(),
1545 1,
1546 .{ .visited = &visited, .queue = &queue },
1547 10_000,
1548 );
1549 try std.testing.expectEqual(schema.Verdict.inconclusive, result.verdict);
1550 try std.testing.expectEqual(Reason.profile_unknown, result.reason);
1551 }
1552
1553 test "omitted data validation authority and service edges refute" {
1554 const omitted = [_]schema.EdgeKind{
1555 .data_flow,
1556 .validation,
1557 .authority_grant,
1558 .service_call,
1559 };
1560 for (omitted) |kind| {
1561 var fixture = try Fixture.init();
1562 var edges = [_]schema.Edge{
1563 fixture.edges[0],
1564 .{ .id = 11, .source = 2, .target = 3, .kind = .derivation },
1565 .{ .id = 12, .source = 2, .target = 3, .kind = kind },
1566 };
1567 fixture.claims[0].traversed_edges = schema.edgeBit(.derivation);
1568 var input = fixture.input();
1569 input.edges = &edges;
1570 var visited: [fixture.nodes.len]u8 = undefined;
1571 var queue: [fixture.nodes.len]u32 = undefined;
1572 const result = check(
1573 input,
1574 1,
1575 .{ .visited = &visited, .queue = &queue },
1576 10_000,
1577 );
1578 try std.testing.expectEqual(schema.Verdict.refuted, result.verdict);
1579 try std.testing.expectEqual(Reason.edge_kind_omitted, result.reason);
1580 }
1581 }
1582
1583 test "owned and receipted origins require matching evidence" {
1584 const source_fixture = try Fixture.init();
1585 var source_input = source_fixture.input();
1586 source_input.source_records = &.{};
1587 var visited: [source_fixture.nodes.len]u8 = undefined;
1588 var queue: [source_fixture.nodes.len]u32 = undefined;
1589 const source_result = check(
1590 source_input,
1591 1,
1592 .{ .visited = &visited, .queue = &queue },
1593 10_000,
1594 );
1595 const derivation_fixture = try Fixture.init();
1596 var derivation_input = derivation_fixture.input();
1597 derivation_input.provenance_parents = &.{};
1598 const derivation_result = check(
1599 derivation_input,
1600 1,
1601 .{ .visited = &visited, .queue = &queue },
1602 10_000,
1603 );
1604 var external_fixture = try Fixture.init();
1605 external_fixture.nodes[2].subject_kind = .data;
1606 external_fixture.nodes[2].artifact_kind = .data;
1607 external_fixture.nodes[2].execution_locus = .nonexecuting;
1608 var external_input = external_fixture.input();
1609 external_input.service_descriptors = &.{};
1610 const external_result = check(
1611 external_input,
1612 1,
1613 .{ .visited = &visited, .queue = &queue },
1614 10_000,
1615 );
1616 try expectOriginEvidenceMissing(source_result);
1617 try expectOriginEvidenceMissing(derivation_result);
1618 try expectOriginEvidenceMissing(external_result);
1619 }
1620
1621 test "unreceipted and platform supplied nodes cannot be owned or verified" {
1622 var fixture = try Fixture.init();
1623 fixture.nodes[0].origin = .platform_supplied;
1624 var visited: [fixture.nodes.len]u8 = undefined;
1625 var queue: [fixture.nodes.len]u32 = undefined;
1626 const platform_result = check(
1627 fixture.input(),
1628 1,
1629 .{ .visited = &visited, .queue = &queue },
1630 10_000,
1631 );
1632 fixture.nodes[0].origin = .external_unreceipted;
1633 fixture.residual_roots[0].treatment = .verified;
1634 fixture.claim_nodes[0].treatment = .verified;
1635 const external_result = check(
1636 fixture.input(),
1637 1,
1638 .{ .visited = &visited, .queue = &queue },
1639 10_000,
1640 );
1641 try std.testing.expectEqual(
1642 Reason.origin_treatment_forbidden,
1643 platform_result.reason,
1644 );
1645 try std.testing.expectEqual(schema.Verdict.refuted, platform_result.verdict);
1646 try std.testing.expectEqual(
1647 Reason.origin_treatment_forbidden,
1648 external_result.reason,
1649 );
1650 try std.testing.expectEqual(schema.Verdict.refuted, external_result.verdict);
1651 }
1652
1653 test "missing roots and unreachable artifacts refute" {
1654 var fixture = try Fixture.init();
1655 var input = fixture.input();
1656 input.residual_roots = &.{};
1657 var visited: [fixture.nodes.len]u8 = undefined;
1658 var queue: [fixture.nodes.len]u32 = undefined;
1659 const missing = check(
1660 input,
1661 1,
1662 .{ .visited = &visited, .queue = &queue },
1663 10_000,
1664 );
1665 input = fixture.input();
1666 fixture.claims[0].traversed_edges = schema.edgeBit(.service_call);
1667 input = fixture.input();
1668 const unreachable_result = check(
1669 input,
1670 1,
1671 .{ .visited = &visited, .queue = &queue },
1672 10_000,
1673 );
1674 try std.testing.expectEqual(Reason.claim_root_missing, missing.reason);
1675 try std.testing.expectEqual(schema.Verdict.refuted, missing.verdict);
1676 try std.testing.expectEqual(
1677 Reason.artifact_unreachable,
1678 unreachable_result.reason,
1679 );
1680 try std.testing.expectEqual(
1681 schema.Verdict.refuted,
1682 unreachable_result.verdict,
1683 );
1684 }
1685
1686 test "coverage overlap and foreign executable evidence refute" {
1687 var fixture = try Fixture.init();
1688 fixture.ranges[1].offset = 1;
1689 fixture.ranges[1].witness = .foreign;
1690 var visited: [fixture.nodes.len]u8 = undefined;
1691 var queue: [fixture.nodes.len]u32 = undefined;
1692 const result = check(
1693 fixture.input(),
1694 1,
1695 .{ .visited = &visited, .queue = &queue },
1696 10_000,
1697 );
1698 try std.testing.expectEqual(schema.Verdict.refuted, result.verdict);
1699 try std.testing.expectEqual(Reason.byte_range_overlap, result.reason);
1700 }
1701
1702 test "oracle influence and forbidden treatment each refute" {
1703 var fixture = try Fixture.init();
1704 fixture.nodes[0].subject_kind = .oracle;
1705 fixture.residual_roots[0].treatment = .validation_only;
1706 fixture.claim_nodes[0].treatment = .validation_only;
1707 var visited: [fixture.nodes.len]u8 = undefined;
1708 var queue: [fixture.nodes.len]u32 = undefined;
1709 const oracle_result = check(
1710 fixture.input(),
1711 1,
1712 .{ .visited = &visited, .queue = &queue },
1713 10_000,
1714 );
1715 fixture.nodes[0].subject_kind = .source;
1716 fixture.residual_roots[0].treatment = .owned;
1717 fixture.claim_nodes[0].treatment = .owned;
1718 fixture.claim_nodes[2].treatment = .forbidden;
1719 const treatment_result = check(
1720 fixture.input(),
1721 1,
1722 .{ .visited = &visited, .queue = &queue },
1723 10_000,
1724 );
1725 try std.testing.expectEqual(schema.Verdict.refuted, oracle_result.verdict);
1726 try std.testing.expectEqual(Reason.oracle_influence, oracle_result.reason);
1727 try std.testing.expectEqual(
1728 schema.Verdict.refuted,
1729 treatment_result.verdict,
1730 );
1731 try std.testing.expectEqual(
1732 Reason.treatment_forbidden,
1733 treatment_result.reason,
1734 );
1735 }
1736
1737 test "missing service and dangling selected edge are inconclusive" {
1738 var fixture = try Fixture.init();
1739 fixture.nodes[2].origin = .external_unreceipted;
1740 var input = fixture.input();
1741 input.service_descriptors = &.{};
1742 var visited: [fixture.nodes.len]u8 = undefined;
1743 var queue: [fixture.nodes.len]u32 = undefined;
1744 const service_result = check(
1745 input,
1746 1,
1747 .{ .visited = &visited, .queue = &queue },
1748 10_000,
1749 );
1750 fixture.edges[1].target = 99;
1751 const edge_result = check(
1752 fixture.input(),
1753 1,
1754 .{ .visited = &visited, .queue = &queue },
1755 10_000,
1756 );
1757 try std.testing.expectEqual(
1758 Reason.service_evidence_missing,
1759 service_result.reason,
1760 );
1761 try std.testing.expectEqual(
1762 schema.Verdict.inconclusive,
1763 service_result.verdict,
1764 );
1765 try std.testing.expectEqual(Reason.edge_target_missing, edge_result.reason);
1766 try std.testing.expectEqual(
1767 schema.Verdict.inconclusive,
1768 edge_result.verdict,
1769 );
1770 }
1771
1772 test "forbidden workload authority flow refutes" {
1773 var fixture = try Fixture.init();
1774 fixture.nodes[2].material_role = .user_payload;
1775 fixture.claim_nodes[2].treatment = .isolated;
1776 var edges = [_]schema.Edge{
1777 fixture.edges[0],
1778 fixture.edges[1],
1779 .{ .id = 12, .source = 2, .target = 3, .kind = .authority_grant },
1780 };
1781 const authorities = [_]schema.Authority{.{
1782 .id = 60,
1783 .source = 2,
1784 .target = 3,
1785 .granted = .root,
1786 }};
1787 var input = fixture.input();
1788 input.edges = &edges;
1789 input.authorities = &authorities;
1790 fixture.claims[0].traversed_edges |= schema.edgeBit(.authority_grant);
1791 input = fixture.input();
1792 input.edges = &edges;
1793 input.authorities = &authorities;
1794 var visited: [fixture.nodes.len]u8 = undefined;
1795 var queue: [fixture.nodes.len]u32 = undefined;
1796 const result = check(
1797 input,
1798 1,
1799 .{ .visited = &visited, .queue = &queue },
1800 10_000,
1801 );
1802 try std.testing.expectEqual(schema.Verdict.refuted, result.verdict);
1803 try std.testing.expectEqual(Reason.authority_forbidden, result.reason);
1804 }
1805
1806 test "frontier and work exhaustion are inconclusive and bounded" {
1807 const fixture = try Fixture.init();
1808 var visited: [fixture.nodes.len]u8 = undefined;
1809 var queue: [fixture.nodes.len]u32 = undefined;
1810 const complete = check(
1811 fixture.input(),
1812 1,
1813 .{ .visited = &visited, .queue = &queue },
1814 10_000,
1815 );
1816 const exhausted = check(
1817 fixture.input(),
1818 1,
1819 .{ .visited = &visited, .queue = &queue },
1820 complete.work - 1,
1821 );
1822 const frontier = check(
1823 fixture.input(),
1824 1,
1825 .{ .visited = &visited, .queue = queue[0..0] },
1826 10_000,
1827 );
1828 try std.testing.expectEqual(Reason.work_limit, exhausted.reason);
1829 try std.testing.expectEqual(complete.work - 1, exhausted.work);
1830 try std.testing.expectEqual(schema.Verdict.inconclusive, exhausted.verdict);
1831 try std.testing.expectEqual(Reason.frontier_capacity, frontier.reason);
1832 try std.testing.expectEqual(schema.Verdict.inconclusive, frontier.verdict);
1833 }
1834
1835 test "undersized visited scratch cannot create a graph refutation" {
1836 var fixture = try Fixture.init();
1837 fixture.claims[0].traversed_edges = schema.edgeBit(.service_call);
1838 var visited = [_]u8{1};
1839 var queue: [fixture.nodes.len]u32 = undefined;
1840 const result = check(
1841 fixture.input(),
1842 1,
1843 .{ .visited = &visited, .queue = &queue },
1844 10_000,
1845 );
1846 try std.testing.expectEqual(schema.Verdict.inconclusive, result.verdict);
1847 try std.testing.expectEqual(Reason.visited_capacity, result.reason);
1848 try std.testing.expectEqual(@as(u8, 0), visited[0]);
1849 }
1850
1851 fn fixtureNodesWithHidden(fixture: *const Fixture) ![4]schema.Node {
1852 var hidden = fixture.nodes[0];
1853 hidden.id = 4;
1854 hidden.descriptor = try schema.Descriptor.init("hidden source");
1855 hidden.identity = knownDigest(10);
1856 return .{
1857 fixture.nodes[0],
1858 fixture.nodes[1],
1859 fixture.nodes[2],
1860 hidden,
1861 };
1862 }
1863
1864 fn fixtureNodes() ![3]schema.Node {
1865 return .{
1866 .{
1867 .id = 1,
1868 .descriptor = try schema.Descriptor.init("kernel source"),
1869 .identity = knownDigest(1),
1870 .subject_kind = .source,
1871 .material_role = .platform,
1872 .origin = .owned_source,
1873 .phases = schema.phaseBit(.source) | schema.phaseBit(.build),
1874 .execution_locus = .nonexecuting,
1875 .owner = try schema.Name.init("closure"),
1876 .authority = .none,
1877 .artifact_kind = .source,
1878 },
1879 .{
1880 .id = 2,
1881 .descriptor = try schema.Descriptor.init("kernel executable"),
1882 .identity = knownDigest(2),
1883 .subject_kind = .binary,
1884 .material_role = .platform,
1885 .origin = .owned_derivation,
1886 .phases = schema.phaseBit(.shipment) |
1887 schema.phaseBit(.post_handoff_runtime),
1888 .execution_locus = .normal_world_cpu,
1889 .owner = try schema.Name.init("os"),
1890 .authority = .platform_control,
1891 .artifact_kind = .executable,
1892 },
1893 .{
1894 .id = 3,
1895 .descriptor = try schema.Descriptor.init("required service"),
1896 .identity = knownDigest(3),
1897 .subject_kind = .service,
1898 .material_role = .residual_root,
1899 .origin = .external_receipted,
1900 .phases = schema.phaseBit(.post_handoff_runtime),
1901 .execution_locus = .remote_service,
1902 .owner = try schema.Name.init("service"),
1903 .authority = .none,
1904 .artifact_kind = .service,
1905 },
1906 };
1907 }
1908
1909 fn fixtureRanges() [2]schema.ByteRange {
1910 return .{
1911 .{
1912 .id = 21,
1913 .artifact = 20,
1914 .offset = 0,
1915 .length = 2,
1916 .digest = knownDigest(4),
1917 .executable = true,
1918 .witness = .owned,
1919 },
1920 .{
1921 .id = 22,
1922 .artifact = 20,
1923 .offset = 2,
1924 .length = 2,
1925 .digest = knownDigest(5),
1926 .executable = true,
1927 .witness = .owned,
1928 },
1929 };
1930 }
1931
1932 fn fixtureService() !schema.ServiceDescriptor {
1933 return .{
1934 .id = 31,
1935 .node = 3,
1936 .provider = try schema.Descriptor.init("private provider"),
1937 .protocol = try schema.Descriptor.init("fixed protocol"),
1938 .endpoint_rule = try schema.Descriptor.init("fixed endpoint"),
1939 .trust_anchor = try schema.Descriptor.init("pinned trust"),
1940 .failure_contract = try schema.Descriptor.init("fail closed"),
1941 .requirement = .required,
1942 };
1943 }
1944
1945 fn fixtureProfiles() !schema.ProfileSet {
1946 return .{
1947 .executable = .{
1948 .required = true,
1949 .id = try schema.Name.init("native"),
1950 .source = try schema.Name.init("tiny-profile"),
1951 .body_sha256 = knownDigest(7),
1952 },
1953 .service_trust = schema.ProfileRef.absent(),
1954 .model_origin = schema.ProfileRef.absent(),
1955 .bootstrap = schema.ProfileRef.absent(),
1956 };
1957 }
1958
1959 fn expectOriginEvidenceMissing(result: Result) !void {
1960 try std.testing.expectEqual(schema.Verdict.inconclusive, result.verdict);
1961 try std.testing.expectEqual(Reason.origin_evidence_missing, result.reason);
1962 }
1963
1964 fn expectPredecessorOmitted(result: Result) !void {
1965 try std.testing.expectEqual(schema.Verdict.refuted, result.verdict);
1966 try std.testing.expectEqual(Reason.predecessor_omitted, result.reason);
1967 }
1968
1969 fn knownDigest(byte: u8) schema.Digest {
1970 return .{ .bytes = @splat(byte) };
1971 }