lib/machine/src/explore/query/history.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const canon = @import("canon.zig");
2 const explore = @import("../root.zig");
3 const fabric = @import("../../fabric/root.zig");
4 const instance = @import("../../instance/root.zig");
5 const os = @import("os");
6 const profile = @import("../../profile/root.zig");
7 const std = @import("std");
8 const types = @import("types.zig");
9 const world = @import("../../world/root.zig");
10
11 /// Returns a history type that records one run in arrays sized by the capacity,
12 /// so a caller records one run into it, seals it with `finish`, and then hands
13 /// it to queries and comparisons or stores its bytes. The record starts with
14 /// the run's start *moment*, a position in a world's history. Each step of the
15 /// history (*frame*) holds one alternative taken at a step, the moment reached,
16 /// and the evidence records the step produced. Each evidence record is one of
17 /// three things: an encoded ledger entry, an encoded event message from the
18 /// guest kernel, or an event recorded for checking rules. A frame or evidence
19 /// capacity of zero stops the build with a compile error. While the history is
20 /// open, each record attaches to the latest frame, and `appendFrame` rejects a
21 /// moment that fails to follow the previous one. `finish` checks the whole
22 /// history, marks it exhausted or incomplete, writes the one fixed-size byte
23 /// encoding of a sealed history, and records its SHA-256 identity. A failed
24 /// `finish` leaves the history as it was. After `finish`, every append returns
25 /// `HistorySealed`, so the sealed history stays fixed. Until `finish`,
26 /// `identity`, `encode`, `frameEvidence`, `referenceAt`, `frameRefs`, and
27 /// `lookup` return `HistoryOpen`. Each reference carries the history's
28 /// identity, a target, and an index, and `lookup` rejects a reference made from
29 /// any other history. `decode` rejects bytes that fail to encode back to the
30 /// same bytes. The history holds no pointers.
31 pub fn History(comptime capacity_value: types.Capacity) type {
32 requireCapacity(capacity_value);
33 return struct {
34 start: world.Moment,
35 frames_storage: [capacity.frames]types.Frame = undefined,
36 evidence_storage: [capacity.evidence]types.Evidence = undefined,
37 frame_count: u16 = 0,
38 evidence_count: u16 = 0,
39 state: explore.TraceState = .open,
40 identity_value: types.Identity = .{ .digest = @splat(0) },
41
42 const Self = @This();
43
44 pub const capacity: types.Capacity = capacity_value;
45 pub const Error: type = types.Error;
46 pub const RefWire: type = canon.RefWire;
47 pub const Wire: type = canon.Wire(capacity);
48
49 pub fn init(start: world.Moment) Error!Self {
50 try world.verifyMoment(start, start.origin, start.fabric);
51 return .{ .start = start };
52 }
53
54 pub fn decode(input: *const Wire) Error!Self {
55 var result: Self = undefined;
56 try canon.decode(capacity, input, &result);
57 return result;
58 }
59
60 pub fn encode(self: *const Self, output: *Wire) Error!void {
61 try self.requirePublished();
62 try canon.encode(capacity, self, output);
63 const actual = try canon.identity(capacity, output);
64 if (!std.meta.eql(actual, self.identity_value)) {
65 return error.CanonicalIdentityMismatch;
66 }
67 }
68
69 pub fn finish(
70 self: *Self,
71 completion: explore.TraceCompletion,
72 output: *Wire,
73 ) Error!types.Identity {
74 if (self.state != .open) return error.HistorySealed;
75 var candidate = self.*;
76 candidate.state = switch (completion) {
77 .exhausted => .exhausted,
78 .incomplete => .incomplete,
79 };
80 try candidate.validate();
81 try canon.encode(capacity, &candidate, output);
82 candidate.identity_value = try canon.identity(capacity, output);
83 self.* = candidate;
84 return self.identity_value;
85 }
86
87 pub fn appendFrame(
88 self: *Self,
89 decision: explore.SearchDecision,
90 expected: world.Moment,
91 ) Error!u16 {
92 try self.requireOpen();
93 if (self.frame_count == capacity.frames) {
94 return error.FrameCapacityExceeded;
95 }
96 try validateDecision(decision);
97 const previous = self.lastMoment();
98 if (!momentFollows(previous, expected)) {
99 return error.FrameSequenceInvalid;
100 }
101 const id = self.frame_count;
102 self.frames_storage[id] = .{
103 .decision = decision,
104 .expected = expected,
105 .evidence_start = self.evidence_count,
106 .evidence_count = 0,
107 };
108 self.frame_count += 1;
109 return id;
110 }
111
112 pub fn appendTransition(
113 self: *Self,
114 frame: u16,
115 wire: fabric.transition.Wire,
116 ) Error!void {
117 _ = try fabric.transition.inspect(&wire);
118 try self.appendEvidence(frame, .{ .transition = wire });
119 }
120
121 pub fn appendMachine(
122 self: *Self,
123 frame: u16,
124 wire: os.abi.MessageWire,
125 ) Error!void {
126 _ = try os.abi.decodeEvent(&wire);
127 try self.appendEvidence(frame, .{ .machine = wire });
128 }
129
130 pub fn appendBatch(
131 self: *Self,
132 frame: u16,
133 batch: *const instance.EventBatch,
134 ) Error!void {
135 try self.requireLatestFrame(frame);
136 if (batch.count > batch.storage.len) {
137 return error.EvidenceSequenceInvalid;
138 }
139 const remaining = capacity.evidence - self.evidence_count;
140 if (batch.count > remaining) return error.EvidenceCapacityExceeded;
141 for (batch.frames()) |wire| try self.appendMachine(frame, wire);
142 }
143
144 pub fn appendSemantic(
145 self: *Self,
146 frame: u16,
147 event: explore.Event,
148 ) Error!void {
149 try validateSemantic(event);
150 try self.appendEvidence(frame, .{ .semantic = event });
151 }
152
153 pub fn frames(self: *const Self) []const types.Frame {
154 std.debug.assert(self.frame_count <= capacity.frames);
155 return self.frames_storage[0..self.frame_count];
156 }
157
158 pub fn evidence(self: *const Self) []const types.Evidence {
159 std.debug.assert(self.evidence_count <= capacity.evidence);
160 return self.evidence_storage[0..self.evidence_count];
161 }
162
163 pub fn frameEvidence(
164 self: *const Self,
165 frame: u16,
166 ) Error![]const types.Evidence {
167 try self.requirePublished();
168 if (frame >= self.frame_count) return error.EvidenceFrameInvalid;
169 const retained = self.frames_storage[frame];
170 const end = retained.evidence_start + retained.evidence_count;
171 return self.evidence_storage[retained.evidence_start..end];
172 }
173
174 pub fn traceState(self: *const Self) explore.TraceState {
175 return self.state;
176 }
177
178 pub fn identity(self: *const Self) Error!types.Identity {
179 try self.requirePublished();
180 return self.identity_value;
181 }
182
183 pub fn logicalCount(self: *const Self) u32 {
184 const frames_count: u32 = self.frame_count;
185 const evidence_count_value: u32 = self.evidence_count;
186 return 1 + frames_count * 2 + evidence_count_value;
187 }
188
189 pub fn referenceAt(
190 self: *const Self,
191 offset: u32,
192 ) Error!types.EvidenceRef {
193 try self.requirePublished();
194 if (offset >= self.logicalCount()) return error.EvidenceIndexInvalid;
195 if (offset == 0) return self.makeRef(.root, 0);
196 var cursor: u32 = 1;
197 for (self.frames(), 0..) |frame, frame_index| {
198 if (cursor == offset) return self.makeRef(.choice, @intCast(frame_index));
199 cursor += 1;
200 for (0..frame.evidence_count) |record_offset| {
201 if (cursor == offset) {
202 const index = frame.evidence_start + @as(u16, @intCast(record_offset));
203 return self.makeRef(.record, index);
204 }
205 cursor += 1;
206 }
207 if (cursor == offset) return self.makeRef(.root, @intCast(frame_index + 1));
208 cursor += 1;
209 }
210 unreachable;
211 }
212
213 pub fn frameRefs(self: *const Self, frame: u16) Error!types.FrameRefs {
214 try self.requirePublished();
215 if (frame >= self.frame_count) return error.EvidenceFrameInvalid;
216 return .{
217 .choice = self.makeRef(.choice, frame),
218 .evidence = .{
219 .first = if (self.frames_storage[frame].evidence_count == 0)
220 null
221 else
222 self.makeRef(
223 .record,
224 self.frames_storage[frame].evidence_start,
225 ),
226 .count = self.frames_storage[frame].evidence_count,
227 },
228 .root = self.makeRef(.root, frame + 1),
229 };
230 }
231
232 pub fn logicalOffset(
233 self: *const Self,
234 reference: types.EvidenceRef,
235 ) Error!u32 {
236 _ = try self.lookup(reference);
237 if (reference.target == .root and reference.index == 0) return 0;
238 var offset: u32 = 1;
239 for (self.frames(), 0..) |frame, frame_index| {
240 if (reference.target == .choice and reference.index == frame_index) {
241 return offset;
242 }
243 offset += 1;
244 if (reference.target == .record and
245 reference.index >= frame.evidence_start and
246 reference.index < frame.evidence_start + frame.evidence_count)
247 {
248 return offset + reference.index - frame.evidence_start;
249 }
250 offset += frame.evidence_count;
251 if (reference.target == .root and reference.index == frame_index + 1) {
252 return offset;
253 }
254 offset += 1;
255 }
256 unreachable;
257 }
258
259 pub fn lookup(
260 self: *const Self,
261 reference: types.EvidenceRef,
262 ) Error!types.Located {
263 try self.requirePublished();
264 if (!std.meta.eql(reference.history, self.identity_value)) {
265 return error.EvidenceHistoryMismatch;
266 }
267 return switch (reference.target) {
268 .choice => self.lookupChoice(reference),
269 .root => self.lookupRoot(reference),
270 .record => self.lookupRecord(reference),
271 };
272 }
273
274 pub fn validate(self: *const Self) Error!void {
275 if (self.frame_count > capacity.frames or
276 self.evidence_count > capacity.evidence)
277 {
278 return error.EvidenceWireCapacityMismatch;
279 }
280 try world.verifyMoment(self.start, self.start.origin, self.start.fabric);
281 var previous = self.start;
282 var evidence_cursor: u16 = 0;
283 var semantic_previous: ?explore.Event = null;
284 for (self.frames()) |frame| {
285 try validateDecision(frame.decision);
286 if (!momentFollows(previous, frame.expected)) return error.FrameSequenceInvalid;
287 if (frame.evidence_start != evidence_cursor or
288 frame.evidence_count > self.evidence_count - evidence_cursor)
289 {
290 return error.EvidenceSequenceInvalid;
291 }
292 try self.validateFrameEvidence(
293 frame,
294 previous.fabric,
295 &semantic_previous,
296 );
297 evidence_cursor += frame.evidence_count;
298 previous = frame.expected;
299 }
300 if (evidence_cursor != self.evidence_count) {
301 return error.EvidenceSequenceInvalid;
302 }
303 }
304
305 fn appendEvidence(
306 self: *Self,
307 frame: u16,
308 value: types.Evidence,
309 ) Error!void {
310 try self.requireLatestFrame(frame);
311 if (self.evidence_count == capacity.evidence) {
312 return error.EvidenceCapacityExceeded;
313 }
314 self.evidence_storage[self.evidence_count] = value;
315 self.evidence_count += 1;
316 self.frames_storage[frame].evidence_count += 1;
317 }
318
319 fn validateFrameEvidence(
320 self: *const Self,
321 frame: types.Frame,
322 previous_root: fabric.Root,
323 semantic_previous: *?explore.Event,
324 ) Error!void {
325 var transition_root = previous_root;
326 var transition_seen = false;
327 const end = frame.evidence_start + frame.evidence_count;
328 for (self.evidence_storage[frame.evidence_start..end]) |record| {
329 switch (record) {
330 .transition => |wire| {
331 const inspected = try fabric.transition.inspect(&wire);
332 try validateTransition(transition_root, inspected);
333 transition_root = inspected.result;
334 transition_seen = true;
335 },
336 .machine => |wire| _ = try os.abi.decodeEvent(&wire),
337 .semantic => |event| {
338 try validateSemantic(event);
339 if (semantic_previous.*) |prior| {
340 if (event.sequence <= prior.sequence or
341 event.virtual_time_tick < prior.virtual_time_tick)
342 {
343 return error.EvidenceSequenceInvalid;
344 }
345 }
346 semantic_previous.* = event;
347 },
348 }
349 }
350 if (transition_seen and !std.meta.eql(transition_root, frame.expected.fabric)) {
351 return error.EvidenceSequenceInvalid;
352 }
353 }
354
355 fn lastMoment(self: *const Self) world.Moment {
356 return if (self.frame_count == 0)
357 self.start
358 else
359 self.frames_storage[self.frame_count - 1].expected;
360 }
361
362 fn lookupChoice(
363 self: *const Self,
364 reference: types.EvidenceRef,
365 ) Error!types.Located {
366 if (reference.index >= self.frame_count) return error.EvidenceIndexInvalid;
367 return .{
368 .reference = reference,
369 .frame = reference.index,
370 .virtual_time_tick = self.frames_storage[reference.index]
371 .decision.site.virtual_time_tick,
372 .view = .{ .choice = &self.frames_storage[reference.index].decision },
373 };
374 }
375
376 fn lookupRoot(
377 self: *const Self,
378 reference: types.EvidenceRef,
379 ) Error!types.Located {
380 if (reference.index > self.frame_count) return error.EvidenceIndexInvalid;
381 if (reference.index == 0) return .{
382 .reference = reference,
383 .frame = null,
384 .virtual_time_tick = null,
385 .view = .{ .root = &self.start },
386 };
387 return .{
388 .reference = reference,
389 .frame = reference.index - 1,
390 .virtual_time_tick = self.frames_storage[reference.index - 1]
391 .decision.site.virtual_time_tick,
392 .view = .{ .root = &self.frames_storage[reference.index - 1].expected },
393 };
394 }
395
396 fn lookupRecord(
397 self: *const Self,
398 reference: types.EvidenceRef,
399 ) Error!types.Located {
400 if (reference.index >= self.evidence_count) return error.EvidenceIndexInvalid;
401 const frame = self.frameForRecord(reference.index);
402 return .{
403 .reference = reference,
404 .frame = frame,
405 .virtual_time_tick = (try recordTick(
406 self.evidence_storage[reference.index],
407 )) orelse self.frames_storage[frame].decision.site.virtual_time_tick,
408 .view = .{ .record = &self.evidence_storage[reference.index] },
409 };
410 }
411
412 fn frameForRecord(self: *const Self, record: u16) u16 {
413 for (self.frames(), 0..) |frame, index| {
414 const end = frame.evidence_start + frame.evidence_count;
415 if (record >= frame.evidence_start and record < end) return @intCast(index);
416 }
417 unreachable;
418 }
419
420 fn makeRef(self: *const Self, target: types.Target, index: u16) types.EvidenceRef {
421 return .{ .history = self.identity_value, .target = target, .index = index };
422 }
423
424 fn requireLatestFrame(self: *const Self, frame: u16) Error!void {
425 try self.requireOpen();
426 if (self.frame_count == 0 or frame != self.frame_count - 1) {
427 return error.EvidenceFrameInvalid;
428 }
429 }
430
431 fn requireOpen(self: *const Self) Error!void {
432 if (self.state != .open) return error.HistorySealed;
433 }
434
435 fn requirePublished(self: *const Self) Error!void {
436 if (self.state == .open) return error.HistoryOpen;
437 }
438 };
439 }
440
441 fn validateSemantic(event: explore.Event) types.Error!void {
442 switch (event.value) {
443 .controlled_input => |value| try validateOrigin(value.origin),
444 .schedule_choice => |value| try validateOrigin(value.origin),
445 .topology_choice => |value| try validateOrigin(value.origin),
446 .injected_fault => |value| {
447 try validateOrigin(value.choice_origin);
448 if (value.effect_origin) |origin| try validateOrigin(origin);
449 },
450 .external_admission => |value| try validateOrigin(value.origin),
451 else => {},
452 }
453 }
454
455 fn recordTick(record: types.Evidence) types.Error!?u64 {
456 return switch (record) {
457 .semantic => |event| event.virtual_time_tick,
458 .machine => |wire| machine: {
459 const event = try os.abi.decodeEvent(&wire);
460 break :machine switch (event.value) {
461 .quiescent => |value| value.virtual_time_tick,
462 else => null,
463 };
464 },
465 .transition => |wire| transitionTick(try fabric.transition.inspect(&wire)),
466 };
467 }
468
469 fn transitionTick(view: fabric.transition.InspectView) ?u64 {
470 return switch (view.value) {
471 .admission => |value| switch (value.record) {
472 .virtual_time => |record| record.to_tick,
473 else => if (value.fault_value) |fault_value|
474 faultTick(fault_value)
475 else
476 null,
477 },
478 .fault => |value| faultTick(value),
479 .settlement => null,
480 };
481 }
482
483 fn faultTick(value: fabric.transition.FaultView) ?u64 {
484 return if (value.kind == .clock_jump) value.primary else null;
485 }
486
487 fn validateDecision(decision: explore.SearchDecision) types.Error!void {
488 if (!decision.valid()) return error.FrameSequenceInvalid;
489 switch (decision.choice) {
490 .input => |value| try validateOrigin(value.origin),
491 .schedule => |value| try validateOrigin(value.origin),
492 .topology => |value| try validateOrigin(value.origin),
493 .fault => |value| {
494 try validateOrigin(value.choice_origin);
495 if (value.effect_origin) |origin| try validateOrigin(origin);
496 },
497 }
498 }
499
500 fn validateTransition(
501 previous: fabric.Root,
502 inspected: fabric.transition.InspectView,
503 ) types.Error!void {
504 if (!std.meta.eql(inspected.previous, previous)) {
505 return error.EvidenceSequenceInvalid;
506 }
507 const sequence = std.math.add(u64, previous.entry_frontier, 1) catch
508 return error.EvidenceSequenceInvalid;
509 if (inspected.sequence != sequence or
510 inspected.result.entry_frontier != sequence or
511 inspected.result.dialect != previous.dialect or
512 !std.meta.eql(
513 inspected.result.machine_contract,
514 previous.machine_contract,
515 ) or
516 inspected.result.admission_frontier < previous.admission_frontier or
517 inspected.result.fault_frontier < previous.fault_frontier or
518 inspected.result.admission_frontier > inspected.result.entry_frontier or
519 inspected.result.fault_frontier > inspected.result.admission_frontier)
520 {
521 return error.EvidenceSequenceInvalid;
522 }
523 }
524
525 fn validateOrigin(value: explore.Origin) types.Error!void {
526 const declared = profile.determinism.entry(value.source);
527 if (declared.version != value.version) return error.EvidenceSequenceInvalid;
528 }
529
530 fn momentFollows(parent: world.Moment, value: world.Moment) bool {
531 world.verifyMoment(value, parent.origin, value.fabric) catch return false;
532 return value.fabric.entry_frontier >= parent.fabric.entry_frontier and
533 value.fabric.admission_frontier >= parent.fabric.admission_frontier and
534 value.fabric.fault_frontier >= parent.fabric.fault_frontier;
535 }
536
537 fn requireCapacity(capacity: types.Capacity) void {
538 if (capacity.frames == 0) @compileError("query frame capacity must be positive");
539 if (capacity.evidence == 0) {
540 @compileError("query evidence capacity must be positive");
541 }
542 }