lib/machine/src/world/prefix.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const fabric = @import("../fabric/root.zig");
2 const fault_owner = @import("fault.zig");
3 const instance = @import("../instance/root.zig");
4 const moment = @import("moment.zig");
5 const replay_owner = @import("replay.zig");
6 const restore = @import("restore.zig");
7 const source = @import("source.zig");
8 const std = @import("std");
9 const types = @import("types.zig");
10
11 /// The maximum number of steps one prefix replays, for a caller sizing its plan
12 /// before calling.
13 /// A plan longer than this rejects before any step runs.
14 pub const step_limit: usize = 16;
15
16 const PrefixOwnerError = error{
17 PrefixEndMismatch,
18 PrefixStartMismatch,
19 PrefixStepCapacityExceeded,
20 PrefixStepSequenceMismatch,
21 };
22
23 pub const Error = fault_owner.Error ||
24 moment.Error ||
25 replay_owner.Error ||
26 restore.StableError ||
27 source.Error ||
28 PrefixOwnerError;
29
30 /// A step that replays a turn, holding the recorded input and the moment the replay
31 /// has to land on, so a caller builds one for every recorded turn in a plan.
32 pub const Turn = struct {
33 replay: replay_owner.Input,
34 expected_moment: moment.Moment,
35 };
36
37 /// A step that replays a fault, holding the recorded transition together with the
38 /// root and the moment the replay has to land on, so a caller builds one for every
39 /// recorded fault in a plan.
40 pub const Fault = struct {
41 reader: *std.Io.Reader,
42 expected_root: fabric.Root,
43 expected_moment: moment.Moment,
44 };
45
46 pub const Step = union(enum) {
47 turn: Turn,
48 fault: Fault,
49 };
50
51 /// A plan for replaying a prefix, holding a start moment already verified, no more
52 /// than `step_limit` recorded steps, and the end moment it declares, so a caller
53 /// hands one to `replayPrefix`.
54 pub const Input = struct {
55 start: moment.Moment,
56 steps: []const Step,
57 end: moment.Moment,
58 };
59
60 /// The running total of a prefix replay, counting steps and turns applied, naming
61 /// the moment reached, and keeping each applied turn's step index and event batch,
62 /// so a caller reads this to see how far a replay got and what the guest said along
63 /// the way.
64 /// The event arrays are fixed at the step limit, and only the first `turn_count`
65 /// entries of each are populated.
66 pub const Progress = struct {
67 step_count: u8,
68 turn_count: u8,
69 moment: moment.Moment,
70 turn_steps: [step_limit]u8,
71 turn_events: [step_limit]instance.EventBatch,
72
73 /// The accessor returns each applied turn's step index, kept in application
74 /// order, so a caller pairs event batches with their steps.
75 pub fn eventSteps(self: *const @This()) []const u8 {
76 std.debug.assert(self.turn_count <= self.turn_steps.len);
77 return self.turn_steps[0..self.turn_count];
78 }
79
80 /// The accessor returns each applied turn's event batch, kept in application
81 /// order, so a caller reads the guest's output for the whole plan.
82 pub fn eventBatches(self: *const @This()) []const instance.EventBatch {
83 std.debug.assert(self.turn_count <= self.turn_events.len);
84 return self.turn_events[0..self.turn_count];
85 }
86 };
87
88 /// The record of a halted prefix, holding the progress reached, the step that failed,
89 /// the failure itself, and the node involved whenever the code can name one, so
90 /// a caller reads this to learn exactly where a plan stopped and why.
91 pub const Stopped = struct {
92 progress: ?Progress,
93 step: u8,
94 node: ?fabric.NodeId,
95 failure: Error,
96 };
97
98 /// The prefix outcome, so a caller switches on this to learn whether the plan proved
99 /// what it claimed.
100 /// `reached` establishes that the replay finished on the end moment the plan declared.
101 /// Rejected worlds continue, and invalidated worlds are gone.
102 pub const Result = union(enum) {
103 reached: Progress,
104 rejected: Stopped,
105 invalidated: Stopped,
106 };
107
108 /// Replays a plan of recorded steps on a restored world, bounded in length, beginning
109 /// at a verified start and finishing at the declared end, so a caller replays a
110 /// stretch of recorded history in one call with the plan proved consistent before
111 /// the guest runs at all.
112 /// Validation covers the entire plan before the first step runs.
113 /// A turn moves the entry frontiers forward by two and a fault moves them forward
114 /// by one, and any other advance is rejected.
115 /// Each moment a step expects has to verify under the world's origin.
116 /// The first failing step halts the replay.
117 /// The start moment must equal the world's verified current moment.
118 /// The plan's step array is checked against the world's live memory before it is
119 /// copied.
120 pub fn replayPrefix(restored: *restore.Restored, input: Input) Result {
121 const current = restore.validateStable(restored) catch |failure|
122 return rejected(null, 0, null, failure);
123 var progress = initialProgress(current);
124 if (!std.meta.eql(current, input.start)) {
125 return rejected(progress, 0, null, error.PrefixStartMismatch);
126 }
127 if (input.steps.len > step_limit) {
128 return rejected(
129 progress,
130 0,
131 null,
132 error.PrefixStepCapacityExceeded,
133 );
134 }
135 source.validateMemory(restored, std.mem.sliceAsBytes(input.steps)) catch |failure|
136 return rejected(progress, 0, null, failure);
137 var steps: [step_limit]Step = undefined;
138 @memcpy(steps[0..input.steps.len], input.steps);
139 validatePlan(
140 restored.root,
141 current,
142 steps[0..input.steps.len],
143 input.end,
144 ) catch |failure| return rejected(progress, 0, null, failure);
145 for (steps[0..input.steps.len], 0..) |*step, index| {
146 switch (step.*) {
147 .turn => |turn| switch (replay_owner.replayTurn(
148 restored,
149 turn.replay,
150 )) {
151 .advanced => |advanced| {
152 std.debug.assert(std.meta.eql(
153 advanced.moment,
154 turn.expected_moment,
155 ));
156 std.debug.assert(progress.turn_count < step_limit);
157 progress.turn_steps[progress.turn_count] = @intCast(index);
158 progress.turn_events[progress.turn_count] = advanced.events;
159 progress.turn_count += 1;
160 progress.step_count += 1;
161 progress.moment = advanced.moment;
162 },
163 .rejected => |failure| return rejected(
164 progress,
165 index,
166 failure.node,
167 failure.failure,
168 ),
169 .invalidated => |failure| return invalidated(
170 progress,
171 index,
172 failure.node,
173 failure.failure,
174 ),
175 },
176 .fault => |fault| switch (fault_owner.replayFault(
177 restored,
178 fault.reader,
179 fault.expected_root,
180 )) {
181 .applied => |applied| {
182 std.debug.assert(std.meta.eql(
183 applied.moment,
184 fault.expected_moment,
185 ));
186 progress.step_count += 1;
187 progress.moment = applied.moment;
188 },
189 .rejected => |failure| return rejected(
190 progress,
191 index,
192 failure.node,
193 failure.failure,
194 ),
195 },
196 }
197 }
198 std.debug.assert(std.meta.eql(progress.moment, input.end));
199 return .{ .reached = progress };
200 }
201
202 fn validatePlan(
203 origin: types.Root,
204 start: moment.Moment,
205 steps: []const Step,
206 end: moment.Moment,
207 ) Error!void {
208 var previous = start;
209 for (steps) |step| {
210 const successor = switch (step) {
211 .turn => |turn| successor: {
212 const admission_frontier = std.math.add(
213 u64,
214 previous.fabric.entry_frontier,
215 1,
216 ) catch return error.PrefixStepSequenceMismatch;
217 const settlement_frontier = std.math.add(
218 u64,
219 previous.fabric.entry_frontier,
220 2,
221 ) catch return error.PrefixStepSequenceMismatch;
222 if (turn.replay.admission.expected_root.entry_frontier !=
223 admission_frontier or
224 turn.replay.settlement.expected_root.entry_frontier !=
225 settlement_frontier)
226 {
227 return error.PrefixStepSequenceMismatch;
228 }
229 try moment.verify(
230 turn.expected_moment,
231 origin,
232 turn.replay.settlement.expected_root,
233 );
234 break :successor turn.expected_moment;
235 },
236 .fault => |fault| successor: {
237 const frontier = std.math.add(
238 u64,
239 previous.fabric.entry_frontier,
240 1,
241 ) catch return error.PrefixStepSequenceMismatch;
242 if (fault.expected_root.entry_frontier != frontier) {
243 return error.PrefixStepSequenceMismatch;
244 }
245 try moment.verify(
246 fault.expected_moment,
247 origin,
248 fault.expected_root,
249 );
250 break :successor fault.expected_moment;
251 },
252 };
253 previous = successor;
254 }
255 if (!std.meta.eql(previous, end)) return error.PrefixEndMismatch;
256 }
257
258 fn initialProgress(value: moment.Moment) Progress {
259 return .{
260 .step_count = 0,
261 .turn_count = 0,
262 .moment = value,
263 .turn_steps = @splat(0),
264 .turn_events = std.mem.zeroes([step_limit]instance.EventBatch),
265 };
266 }
267
268 fn rejected(
269 progress: ?Progress,
270 step: usize,
271 node: ?fabric.NodeId,
272 failure: Error,
273 ) Result {
274 return .{ .rejected = .{
275 .progress = progress,
276 .step = @intCast(step),
277 .node = node,
278 .failure = failure,
279 } };
280 }
281
282 fn invalidated(
283 progress: Progress,
284 step: usize,
285 node: ?fabric.NodeId,
286 failure: Error,
287 ) Result {
288 return .{ .invalidated = .{
289 .progress = progress,
290 .step = @intCast(step),
291 .node = node,
292 .failure = failure,
293 } };
294 }