lib/machine/src/explore/distributed/replay.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const canon = @import("canon.zig");
2 const explore = @import("../root.zig");
3 const profile = @import("../../profile/root.zig");
4 const property = @import("property.zig");
5 const state_owner = @import("state.zig");
6 const std = @import("std");
7 const types = @import("types.zig");
8 const workload = @import("workload.zig");
9 const world = @import("../../world/root.zig");
10
11 pub const Capsule = explore.Capsule(types.capsule_capacity);
12 pub const Reducer = explore.CapsuleReducer(types.capsule_capacity);
13 pub const History = explore.query.History(types.history_capacity);
14 pub const Diff = explore.query.Diff(types.diff_capacity);
15
16 /// Runs one given list of alternatives taken at a step (*decisions*) against
17 /// the three-node commit protocol under test (*workload*) from its initial
18 /// state, in order and with no search, and records an append-only record of the
19 /// run (*causal history*), which `seal` later seals. The witness gate uses one
20 /// to replay a record of one failing run that replays it exactly (*capsule*)
21 /// and to replay a chosen path, and reads the sealed causal history afterward.
22 /// Each recorded step of the history (*frame*) holds the step's events recorded
23 /// for checking rules and the results of checking both rules that fail at the
24 /// first event that breaks them (*safety rules*), and the rule declarations go
25 /// into the first frame alone. The history holds at most 8 frames and 64
26 /// records, and the replayer keeps it and its byte encoding inside the value.
27 /// `init` binds one workload variant and one profile and starts an empty
28 /// history, and `begin` restarts from the initial state. `apply` runs one
29 /// decision and reports the position reached in a world's history (*moment*),
30 /// or reports a failure when a safety rule is violated. `seal` finishes the
31 /// history as exhausted and returns its identity. `path` restarts, applies 1 to
32 /// 8 decisions, and seals. `runner` adapts the replayer for capsule replay: its
33 /// preparation accepts only the replayer's own profile, the identity of the
34 /// build each of the workload's three nodes ran, and outside results from host
35 /// services or effects, and it restarts at the capsule's start moment. The
36 /// runner's step requires the parent to be the current moment, reports a full
37 /// history as an incomplete trace, and reports any other error as a rejected
38 /// replay.
39 pub const Replayer = struct {
40 config: types.Config,
41 selected: profile.Profile,
42 origin: world.Root,
43 state: state_owner.State,
44 history: History,
45 wire: History.Wire,
46 sequence: u16,
47 frames: u16,
48 failure: ?explore.PropertyEvaluation,
49 preparations: u32,
50
51 pub fn init(
52 self: *Replayer,
53 config: types.Config,
54 selected: profile.Profile,
55 ) types.Error!void {
56 self.config = config;
57 self.selected = selected;
58 self.preparations = 0;
59 try self.begin();
60 }
61
62 pub fn begin(self: *Replayer) types.Error!void {
63 const contract = try profile.contractFingerprint(self.selected);
64 self.origin = canon.origin(contract);
65 self.state = state_owner.State.init(canon.initialRoot(contract));
66 self.history = try History.init(try self.moment());
67 self.sequence = 0;
68 self.frames = 0;
69 self.failure = null;
70 std.debug.assert(self.history.traceState() == .open);
71 }
72
73 pub fn apply(
74 self: *Replayer,
75 decision: explore.SearchDecision,
76 ) types.Error!explore.SearchExecution {
77 var events: types.Events = .{};
78 const verdicts = try workload.evaluate(
79 self.config,
80 &self.state,
81 decision,
82 &events,
83 false,
84 );
85 const reached = try self.moment();
86 std.debug.assert(reached.fabric.entry_frontier <= self.frames + 1);
87 try self.record(decision, reached, &events, verdicts);
88 std.debug.assert(self.frames <= types.history_capacity.frames);
89 if (property.violation(verdicts)) |failure| {
90 self.failure = failure;
91 return .{ .failed = .{ .root = reached, .evaluation = failure } };
92 }
93 return .{ .completed = reached };
94 }
95
96 pub fn seal(self: *Replayer) types.Error!explore.query.Identity {
97 std.debug.assert(self.frames > 0);
98 return self.history.finish(.exhausted, &self.wire);
99 }
100
101 pub fn runner(self: *Replayer) explore.CapsuleRunner {
102 return .{
103 .context = self,
104 .prepare = prepare,
105 .step = .{ .context = self, .execute = execute },
106 };
107 }
108
109 pub fn path(
110 self: *Replayer,
111 decisions: []const explore.SearchDecision,
112 ) types.Error!explore.query.Identity {
113 std.debug.assert(decisions.len > 0);
114 std.debug.assert(decisions.len <= types.history_capacity.frames);
115 try self.begin();
116 for (decisions) |decision| _ = try self.apply(decision);
117 std.debug.assert(self.frames == decisions.len);
118 return self.seal();
119 }
120
121 fn moment(self: *const Replayer) types.Error!world.Moment {
122 return world.prepareMoment(self.origin, self.state.fabric);
123 }
124
125 fn record(
126 self: *Replayer,
127 decision: explore.SearchDecision,
128 reached: world.Moment,
129 events: *const types.Events,
130 verdicts: property.Verdicts,
131 ) types.Error!void {
132 std.debug.assert(self.frames < types.history_capacity.frames);
133 const frame = try self.history.appendFrame(decision, reached);
134 std.debug.assert(frame == self.frames);
135 self.frames += 1;
136 for (events.events()) |event| {
137 const declaration = std.meta.activeTag(event.value) == .property_declaration;
138 if (declaration and frame != 0) continue;
139 try self.append(frame, event.virtual_time_tick, event.value);
140 }
141 for (verdicts) |verdict| {
142 try self.append(
143 frame,
144 self.state.now,
145 .{ .property_evaluation = verdict },
146 );
147 }
148 }
149
150 fn append(
151 self: *Replayer,
152 frame: u16,
153 tick: u64,
154 value: explore.EventValue,
155 ) types.Error!void {
156 try self.history.appendSemantic(frame, .{
157 .sequence = self.sequence,
158 .virtual_time_tick = tick,
159 .value = value,
160 });
161 std.debug.assert(self.sequence < std.math.maxInt(u16));
162 self.sequence += 1;
163 }
164 };
165
166 fn prepare(
167 raw: *anyopaque,
168 selected: profile.Profile,
169 start: world.Moment,
170 builds: []const explore.CapsuleBuildIdentity,
171 external: []const explore.CapsuleExternalResult,
172 ) explore.CapsulePreparation {
173 const self: *Replayer = @ptrCast(@alignCast(raw));
174 self.preparations += 1;
175 if (!std.meta.eql(selected, self.selected)) {
176 return .{ .incomplete = .replay_rejected };
177 }
178 if (!admissible(builds, external)) return .{ .incomplete = .replay_rejected };
179 self.begin() catch return .{ .incomplete = .replay_rejected };
180 const root = self.moment() catch return .{ .incomplete = .invalid_moment };
181 if (!std.meta.eql(root, start)) return .{ .incomplete = .invalid_moment };
182 return .{ .ready = root };
183 }
184
185 fn execute(
186 raw: *anyopaque,
187 parent: world.Moment,
188 decision: explore.SearchDecision,
189 ) explore.SearchExecution {
190 const self: *Replayer = @ptrCast(@alignCast(raw));
191 const expected = self.moment() catch
192 return .{ .incomplete = .invalid_moment };
193 if (!std.meta.eql(expected, parent)) return .{ .incomplete = .invalid_moment };
194 return self.apply(decision) catch |failure| switch (failure) {
195 error.FrameCapacityExceeded,
196 error.EvidenceCapacityExceeded,
197 error.TraceCapacityExceeded,
198 => .{ .incomplete = .trace_incomplete },
199 else => .{ .incomplete = .replay_rejected },
200 };
201 }
202
203 fn admissible(
204 builds: []const explore.CapsuleBuildIdentity,
205 external: []const explore.CapsuleExternalResult,
206 ) bool {
207 const expected = canon.builds();
208 if (builds.len != expected.len) return false;
209 for (builds, expected) |actual, declared| {
210 if (!std.meta.eql(actual, declared)) return false;
211 }
212 for (external) |entry| {
213 switch (entry.origin.source) {
214 .host_service_result, .effect_result => {},
215 else => return false,
216 }
217 }
218 return true;
219 }