lib/machine/src/explore/capsule/owner.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const canon = @import("canon.zig");
2 const explore = @import("../root.zig");
3 const profile = @import("../../profile/root.zig");
4 const std = @import("std");
5 const types = @import("types.zig");
6 const world = @import("../../world/root.zig");
7
8 pub fn Capsule(comptime capacity_value: types.Capacity) type {
9 requireCapacity(capacity_value);
10 return struct {
11 selected_profile: profile.Profile,
12 start: world.Moment,
13 expected_failure: explore.PropertyEvaluation,
14 builds_storage: [capacity.builds]types.BuildIdentity,
15 frames_storage: [capacity.frames]types.Frame,
16 external_storage: [capacity.frames]types.ExternalResult,
17 build_count: u8,
18 frame_count: u16,
19 external_count: u16,
20
21 const Self = @This();
22
23 pub const capacity: types.Capacity = capacity_value;
24 pub const Error = types.Error;
25 pub const Wire = canon.Wire(capacity);
26 pub const Capture = union(enum) {
27 published: Self,
28 rejected: types.Rejection,
29 };
30
31 pub fn capture(
32 search: anytype,
33 failure: anytype,
34 selected_profile: profile.Profile,
35 build_identities: []const types.BuildIdentity,
36 runner: types.Runner,
37 ) Error!Capture {
38 if (build_identities.len > capacity.builds) {
39 return error.BuildCapacityExceeded;
40 }
41 const failed = try search.branch(failure.branch);
42 try validateFailureBranch(failed, failure);
43 if (failed.depth > capacity.frames) {
44 return error.FrameCapacityExceeded;
45 }
46 var result: Self = undefined;
47 result.selected_profile = selected_profile;
48 result.start = (try search.branch(0)).root;
49 result.expected_failure = failure.evaluation;
50 result.build_count = @intCast(build_identities.len);
51 result.frame_count = failed.depth;
52 @memcpy(
53 result.builds_storage[0..build_identities.len],
54 build_identities,
55 );
56 try result.copyHistory(search, failure.branch);
57 return result.publishOwned(runner);
58 }
59
60 pub fn publish(
61 selected_profile: profile.Profile,
62 start: world.Moment,
63 expected_failure: explore.PropertyEvaluation,
64 build_identities: []const types.BuildIdentity,
65 replay_frames: []const types.Frame,
66 runner: types.Runner,
67 ) Error!Capture {
68 if (build_identities.len > capacity.builds) {
69 return error.BuildCapacityExceeded;
70 }
71 if (replay_frames.len > capacity.frames) {
72 return error.FrameCapacityExceeded;
73 }
74 var result: Self = undefined;
75 result.selected_profile = selected_profile;
76 result.start = start;
77 result.expected_failure = expected_failure;
78 result.build_count = @intCast(build_identities.len);
79 result.frame_count = @intCast(replay_frames.len);
80 @memcpy(
81 result.builds_storage[0..build_identities.len],
82 build_identities,
83 );
84 @memcpy(
85 result.frames_storage[0..replay_frames.len],
86 replay_frames,
87 );
88 return result.publishOwned(runner);
89 }
90
91 fn publishOwned(self: *Self, runner: types.Runner) Error!Capture {
92 self.rebuildExternalLedger();
93 try self.validate();
94 return switch (try self.replay(runner)) {
95 .reproduced => .{ .published = self.* },
96 .rejected => |rejection| .{ .rejected = rejection },
97 };
98 }
99
100 pub fn builds(self: *const Self) []const types.BuildIdentity {
101 std.debug.assert(self.build_count <= capacity.builds);
102 return self.builds_storage[0..self.build_count];
103 }
104
105 pub fn frames(self: *const Self) []const types.Frame {
106 std.debug.assert(self.frame_count <= capacity.frames);
107 return self.frames_storage[0..self.frame_count];
108 }
109
110 pub fn externalResults(self: *const Self) []const types.ExternalResult {
111 std.debug.assert(self.external_count <= capacity.frames);
112 return self.external_storage[0..self.external_count];
113 }
114
115 pub fn replay(self: *const Self, runner: types.Runner) Error!types.Replay {
116 try self.validate();
117 const prepared = runner.prepare(
118 runner.context,
119 self.selected_profile,
120 self.start,
121 self.builds(),
122 self.externalResults(),
123 );
124 var current = switch (prepared) {
125 .ready => |ready| ready,
126 .incomplete => |reason| return rejected(
127 0,
128 .preparation_incomplete,
129 reason,
130 ),
131 };
132 if (!std.meta.eql(current, self.start)) {
133 return rejected(0, .start_mismatch, null);
134 }
135 for (self.frames(), 0..) |frame, index| {
136 const result = runner.step.run(current, frame.decision);
137 if (index + 1 == self.frame_count) {
138 return self.finishReplay(frame, result, index);
139 }
140 current = switch (result) {
141 .completed => |next| next,
142 .failed => return rejected(index, .unexpected_failure, null),
143 .incomplete => |reason| return rejected(
144 index,
145 .step_incomplete,
146 reason,
147 ),
148 };
149 if (!std.meta.eql(current, frame.expected)) {
150 return rejected(index, .moment_mismatch, null);
151 }
152 }
153 unreachable;
154 }
155
156 pub fn encode(self: *const Self, output: *Wire) Error!void {
157 try canon.encode(capacity, self, output);
158 }
159
160 pub fn decode(input: *const Wire) Error!Self {
161 var result: Self = undefined;
162 try canon.decode(capacity, input, &result);
163 return result;
164 }
165
166 pub fn identity(self: *const Self) Error!types.Identity {
167 var wire: Wire = undefined;
168 try self.encode(&wire);
169 return canon.identity(capacity, &wire);
170 }
171
172 pub fn validate(self: *const Self) Error!void {
173 try profile.validate(self.selected_profile);
174 try world.verifyMoment(self.start, self.start.origin, self.start.fabric);
175 const contract = try profile.contractFingerprint(self.selected_profile);
176 if (!std.meta.eql(contract, self.start.origin.machine_contract)) {
177 return error.InitialContractMismatch;
178 }
179 if (self.frame_count == 0 or self.frame_count > capacity.frames) {
180 return error.FrameInvalid;
181 }
182 if (self.build_count != self.start.origin.node_count or
183 self.build_count > capacity.builds)
184 {
185 return error.BuildCountMismatch;
186 }
187 if (self.expected_failure.verdict != .violated) {
188 return error.FailureExpected;
189 }
190 try self.validateBuilds();
191 try self.validateFrames();
192 try self.validateExternalLedger();
193 }
194
195 fn copyHistory(self: *Self, search: anytype, branch_id: anytype) Error!void {
196 var cursor = branch_id;
197 var remaining = self.frame_count;
198 while (remaining > 0) {
199 const branch = try search.branch(cursor);
200 remaining -= 1;
201 self.frames_storage[remaining] = .{
202 .decision = branch.decision.?,
203 .expected = branch.root,
204 };
205 cursor = branch.parent.?;
206 }
207 std.debug.assert(cursor == 0);
208 }
209
210 fn finishReplay(
211 self: *const Self,
212 frame: types.Frame,
213 result: explore.SearchExecution,
214 index: usize,
215 ) types.Replay {
216 return switch (result) {
217 .completed => rejected(index, .expected_failure_missing, null),
218 .incomplete => |reason| rejected(index, .step_incomplete, reason),
219 .failed => |failure| if (!std.meta.eql(failure.root, frame.expected))
220 rejected(index, .moment_mismatch, null)
221 else if (!std.meta.eql(failure.evaluation, self.expected_failure))
222 rejected(index, .failure_mismatch, null)
223 else
224 .{ .reproduced = failure.evaluation },
225 };
226 }
227
228 fn validateBuilds(self: *const Self) Error!void {
229 for (self.builds(), 0..) |build, index| {
230 if (allZero(&build.node.bytes) or allZero(&build.execution.digest)) {
231 return error.BuildIdentityInvalid;
232 }
233 if (index > 0 and !std.mem.lessThan(
234 u8,
235 &self.builds_storage[index - 1].node.bytes,
236 &build.node.bytes,
237 )) return error.BuildOrderInvalid;
238 }
239 }
240
241 fn validateFrames(self: *const Self) Error!void {
242 var previous = self.start;
243 for (self.frames()) |frame| {
244 if (!frame.decision.valid()) return error.FrameInvalid;
245 try validateDecisionOrigins(frame.decision);
246 try world.verifyMoment(
247 frame.expected,
248 self.start.origin,
249 frame.expected.fabric,
250 );
251 if (!momentFollows(previous, frame.expected)) {
252 return error.FrameInvalid;
253 }
254 previous = frame.expected;
255 }
256 }
257
258 fn rebuildExternalLedger(self: *Self) void {
259 self.external_count = 0;
260 for (self.frames(), 0..) |frame, index| {
261 const value = externalResult(frame.decision, @intCast(index)) orelse
262 continue;
263 std.debug.assert(self.external_count < capacity.frames);
264 self.external_storage[self.external_count] = value;
265 self.external_count += 1;
266 }
267 }
268
269 fn validateExternalLedger(self: *const Self) Error!void {
270 if (self.external_count > self.frame_count) {
271 return error.ExternalLedgerInvalid;
272 }
273 var expected: [capacity.frames]types.ExternalResult = undefined;
274 var count: u16 = 0;
275 for (self.frames(), 0..) |frame, index| {
276 const value = externalResult(frame.decision, @intCast(index)) orelse
277 continue;
278 expected[count] = value;
279 count += 1;
280 }
281 if (count != self.external_count) return error.ExternalLedgerInvalid;
282 for (expected[0..count], self.externalResults()) |left, right| {
283 if (!std.meta.eql(left, right)) {
284 return error.ExternalLedgerInvalid;
285 }
286 }
287 }
288 };
289 }
290
291 pub fn Reducer(comptime capacity_value: types.Capacity) type {
292 const CapsuleType = Capsule(capacity_value);
293 const attempt_limit = reductionAttemptLimit(capacity_value.frames);
294 return struct {
295 accepted: CapsuleType,
296 scratch: CapsuleType,
297 statistics: types.Statistics = .{ .attempts = 0, .accepted = 0, .rejected = 0 },
298
299 const Self = @This();
300
301 pub const capacity: types.Capacity = capacity_value;
302 pub const Init = union(enum) {
303 ready: Self,
304 rejected: types.Rejection,
305 };
306 pub const Attempt = union(enum) {
307 accepted,
308 rejected: types.Rejection,
309 };
310 pub const Reduced = struct {
311 capsule: CapsuleType,
312 statistics: types.Statistics,
313 };
314
315 pub fn init(value: CapsuleType, runner: types.Runner) types.Error!Init {
316 return switch (try value.replay(runner)) {
317 .reproduced => .{ .ready = .{ .accepted = value, .scratch = value } },
318 .rejected => |rejection| .{ .rejected = rejection },
319 };
320 }
321
322 pub fn tryRemove(
323 self: *Self,
324 frame: u16,
325 runner: types.Runner,
326 ) types.Error!Attempt {
327 if (frame >= self.accepted.frame_count) return error.FrameUnknown;
328 if (self.accepted.frame_count == 1) return error.FailureExpected;
329 self.scratch = self.accepted;
330 const remaining = self.scratch.frame_count - frame - 1;
331 std.mem.copyForwards(
332 types.Frame,
333 self.scratch.frames_storage[frame .. frame + remaining],
334 self.scratch.frames_storage[frame + 1 .. self.scratch.frame_count],
335 );
336 self.scratch.frame_count -= 1;
337 self.scratch.rebuildExternalLedger();
338 self.statistics.attempts += 1;
339 return switch (try self.scratch.replay(runner)) {
340 .reproduced => {
341 self.accepted = self.scratch;
342 self.statistics.accepted += 1;
343 return .accepted;
344 },
345 .rejected => |rejection| {
346 self.statistics.rejected += 1;
347 return .{ .rejected = rejection };
348 },
349 };
350 }
351
352 pub fn reduce(self: *Self, runner: types.Runner) types.Error!Reduced {
353 var frame: u16 = 0;
354 for (0..attempt_limit) |_| {
355 if (self.accepted.frame_count == 1 or
356 frame == self.accepted.frame_count)
357 {
358 return .{
359 .capsule = self.accepted,
360 .statistics = self.statistics,
361 };
362 }
363 switch (try self.tryRemove(frame, runner)) {
364 .accepted => frame = 0,
365 .rejected => frame += 1,
366 }
367 }
368 unreachable;
369 }
370 };
371 }
372
373 fn validateFailureBranch(branch: anytype, failure: anytype) types.Error!void {
374 if (branch.parent != failure.parent or
375 !std.meta.eql(branch.decision.?, failure.decision))
376 {
377 return error.FailureBranchMismatch;
378 }
379 switch (branch.settlement) {
380 .failed => |evaluation| if (!std.meta.eql(evaluation, failure.evaluation)) {
381 return error.FailureBranchMismatch;
382 },
383 .origin, .completed => return error.FailureBranchMismatch,
384 }
385 }
386
387 fn rejected(
388 frame: usize,
389 reason: types.RejectionReason,
390 incomplete: ?explore.SearchExecutionIncomplete,
391 ) types.Replay {
392 return .{ .rejected = .{
393 .frame = @intCast(frame),
394 .reason = reason,
395 .incomplete = incomplete,
396 } };
397 }
398
399 fn validateDecisionOrigins(decision: explore.SearchDecision) types.Error!void {
400 switch (decision.choice) {
401 .input => |value| try validateOrigin(value.origin),
402 .schedule => |value| try validateOrigin(value.origin),
403 .topology => |value| try validateOrigin(value.origin),
404 .fault => |value| {
405 try validateOrigin(value.choice_origin);
406 if (value.effect_origin) |origin| try validateOrigin(origin);
407 },
408 }
409 }
410
411 fn validateOrigin(origin: explore.Origin) types.Error!void {
412 const declared = profile.determinism.entry(origin.source);
413 if (declared.version != origin.version) return error.FrameInvalid;
414 }
415
416 fn externalResult(
417 decision: explore.SearchDecision,
418 frame: u16,
419 ) ?types.ExternalResult {
420 const input = switch (decision.choice) {
421 .input => |value| value,
422 .schedule, .topology, .fault => return null,
423 };
424 const outcome = switch (input.value) {
425 .service_result => |value| value,
426 .effect_result => |value| value,
427 .wait, .terminal, .entropy, .packet => return null,
428 };
429 return .{ .frame = frame, .origin = input.origin, .outcome = outcome };
430 }
431
432 fn momentFollows(parent: world.Moment, value: world.Moment) bool {
433 if (!std.meta.eql(parent.origin, value.origin)) return false;
434 return value.fabric.entry_frontier >= parent.fabric.entry_frontier and
435 value.fabric.admission_frontier >= parent.fabric.admission_frontier and
436 value.fabric.fault_frontier >= parent.fabric.fault_frontier;
437 }
438
439 fn allZero(bytes: []const u8) bool {
440 for (bytes) |byte| if (byte != 0) return false;
441 return true;
442 }
443
444 fn requireCapacity(capacity: types.Capacity) void {
445 if (capacity.frames == 0) @compileError("capsule frame capacity must be positive");
446 if (capacity.builds == 0) @compileError("capsule build capacity must be positive");
447 }
448
449 fn reductionAttemptLimit(frames: u16) usize {
450 const count: usize = frames;
451 return std.math.mul(usize, count, count) catch
452 @compileError("capsule reduction attempt bound overflows usize");
453 }