lib/machine/src/explore/test.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const explore = @import("root.zig");
2 const fault = @import("../fault/root.zig");
3 const profile = @import("../profile/root.zig");
4 const std = @import("std");
5
6 const Input = explore.InputGenerator(.{ .steps = 8, .alternatives = 5 });
7 const Schedule = explore.ScheduleGenerator(.{
8 .steps = 8,
9 .nodes = 4,
10 .alternatives = 5,
11 });
12 const Topology = explore.TopologyGenerator(.{
13 .steps = 8,
14 .nodes = 4,
15 .alternatives = 5,
16 });
17 const Fault = explore.FaultGenerator(.{
18 .steps = 8,
19 .kinds = 4,
20 .alternatives = 5,
21 });
22
23 const selected_profile = profile.interpretedContinuationTestV1();
24 const safety_id: explore.SemanticId = 0x5100;
25 const liveness_id: explore.SemanticId = 0x7100;
26 const response_id: explore.SemanticId = 0x7200;
27
28 test {
29 _ = @import("capsule/test.zig");
30 _ = @import("distributed/test.zig");
31 _ = @import("query/test.zig");
32 _ = @import("search/test.zig");
33 }
34
35 test "explore: public namespace is reachable" {
36 std.testing.refAllDecls(explore);
37 }
38
39 test "explore: every generator replays one explicit seed" {
40 const seed = explore.Seed.fromU64(0xb10c_0001);
41 var first_input = try inputReady(seed, temporalPlan(6));
42 var replay_input = try inputReady(seed, temporalPlan(6));
43 try expectReplay(&first_input, &replay_input, 6);
44
45 var first_schedule = try scheduleReady(seed, 3, temporalPlan(6));
46 var replay_schedule = try scheduleReady(seed, 3, temporalPlan(6));
47 try expectReplay(&first_schedule, &replay_schedule, 6);
48
49 var first_topology = try topologyReady(seed, 3, temporalPlan(6));
50 var replay_topology = try topologyReady(seed, 3, temporalPlan(6));
51 try expectReplay(&first_topology, &replay_topology, 6);
52
53 const kinds = [_]fault.Kind{ .partition, .packet_delay, .machine_crash };
54 var first_fault = try faultReady(seed, &kinds, temporalPlan(6));
55 var replay_fault = try faultReady(seed, &kinds, temporalPlan(6));
56 try expectReplay(&first_fault, &replay_fault, 6);
57
58 var seed_input = try inputReady(seed, temporalPlan(6));
59 var other_input = try inputReady(explore.Seed.fromU64(0xb10c_0002), temporalPlan(6));
60 const first_site = try requireSite(seed_input.next());
61 const other_site = try requireSite(other_input.next());
62 try std.testing.expect(!sameSite(first_site, other_site));
63 }
64
65 test "explore: capacities refuse and exhausted generators never wrap" {
66 try expectGeneratorCapacityRefusals();
67 var input = try inputReady(explore.Seed.fromU64(1), temporalPlan(1));
68 const input_site = try requireSite(input.next());
69 _ = try input.choose(input_site, 0);
70 try expectExhausted(input.next());
71 try expectExhausted(input.next());
72
73 var schedule = try scheduleReady(explore.Seed.fromU64(2), 1, temporalPlan(1));
74 const schedule_site = try requireSite(schedule.next());
75 _ = try schedule.choose(schedule_site, 0);
76 try expectExhausted(schedule.next());
77 try expectExhausted(schedule.next());
78
79 var topology = try topologyReady(
80 explore.Seed.fromU64(3),
81 1,
82 temporalPlan(3),
83 );
84 const node_site = try requireSite(topology.next());
85 _ = try topology.choose(node_site, 0);
86 const complete_site = try requireSite(topology.next());
87 _ = try topology.choose(complete_site, try topologyComplete(complete_site));
88 try expectExhausted(topology.next());
89 try expectExhausted(topology.next());
90
91 var bounded_topology = try topologyReady(
92 explore.Seed.fromU64(4),
93 1,
94 temporalPlan(1),
95 );
96 const bounded_site = try requireSite(bounded_topology.next());
97 _ = try bounded_topology.choose(bounded_site, 0);
98 try expectIncomplete(.step_capacity, bounded_topology.next());
99 try expectIncomplete(.step_capacity, bounded_topology.next());
100
101 const fault_kinds = [_]fault.Kind{.partition};
102 var faults = try faultReady(
103 explore.Seed.fromU64(5),
104 &fault_kinds,
105 temporalPlan(1),
106 );
107 const fault_site = try requireSite(faults.next());
108 _ = try faults.choose(fault_site, 0);
109 try expectExhausted(faults.next());
110 try expectExhausted(faults.next());
111
112 const Events = explore.EventSequence(.{ .events = 1 });
113 var events: Events = .{};
114 try events.append(0, declarationValue(safety_id, .safety, null));
115 try std.testing.expectError(
116 error.CapacityExceeded,
117 events.append(1, .{ .observation = .{ .id = 1, .value = 1 } }),
118 );
119 try std.testing.expectEqual(explore.TraceState.incomplete, events.traceState());
120 }
121
122 test "explore: workload and fault tactics retain virtual-time state" {
123 var input = try inputReady(explore.Seed.fromU64(3), temporalPlan(6));
124 const quiet = try requireSite(input.next());
125 const terminal = try inputChoice(quiet, .terminal);
126 _ = try input.choose(quiet, terminal);
127 try std.testing.expectEqual(explore.InputPhase.burst, input.workload());
128 const burst = try requireSite(input.next());
129 _ = try input.choose(burst, try inputChoice(burst, .wait));
130 try std.testing.expectEqual(explore.InputPhase.quiet, input.workload());
131
132 const kinds = [_]fault.Kind{.partition};
133 var faults = try faultReady(explore.Seed.fromU64(4), &kinds, temporalPlan(6));
134 const healthy = try requireSite(faults.next());
135 const injected = try faults.choose(healthy, try faultChoice(healthy, .inject));
136 try std.testing.expectEqual(
137 profile.DeterminismSource.packet_fault,
138 injected.effect_origin.?.source,
139 );
140 try std.testing.expectEqual(fault.Kind.partition, faults.activeFault().?);
141 const active = try requireSite(faults.next());
142 _ = try faults.choose(active, try faultChoice(active, .persist));
143 try std.testing.expectEqual(fault.Kind.partition, faults.activeFault().?);
144 const recovery = try requireSite(faults.next());
145 _ = try faults.choose(recovery, try faultChoice(recovery, .recover));
146 try std.testing.expectEqual(@as(?fault.Kind, null), faults.activeFault());
147 }
148
149 test "explore: alternatives name frozen determinism sources and versions" {
150 const seed = explore.Seed.fromU64(0xb10c_5000);
151 var input = try inputReady(seed, temporalPlan(2));
152 const input_site = try requireSite(input.next());
153 for (input_site.values()) |alternative| try expectOrigin(alternative.origin);
154 _ = try input.choose(input_site, try inputChoice(input_site, .terminal));
155 const input_burst = try requireSite(input.next());
156 for (input_burst.values()) |alternative| try expectOrigin(alternative.origin);
157
158 var schedule = try scheduleReady(seed, 2, temporalPlan(2));
159 const schedule_site = try requireSite(schedule.next());
160 for (schedule_site.values()) |alternative| try expectOrigin(alternative.origin);
161
162 var topology = try topologyReady(seed, 2, temporalPlan(2));
163 const topology_site = try requireSite(topology.next());
164 for (topology_site.values()) |alternative| try expectOrigin(alternative.origin);
165 _ = try topology.choose(topology_site, 0);
166 const topology_complete = try requireSite(topology.next());
167 for (topology_complete.values()) |alternative| try expectOrigin(alternative.origin);
168
169 const kinds = [_]fault.Kind{ .partition, .clock_jump, .host_service_failure };
170 var faults = try faultReady(seed, &kinds, temporalPlan(2));
171 const fault_site = try requireSite(faults.next());
172 for (fault_site.values()) |alternative| {
173 try expectOrigin(alternative.choice_origin);
174 if (alternative.effect_origin) |origin| try expectOrigin(origin);
175 }
176 for (std.meta.tags(fault.Kind)) |kind| try expectOrigin(explore.faultOrigin(kind));
177 }
178
179 test "explore: safety and bounded liveness evaluate generated semantic events" {
180 const Events = explore.EventSequence(.{ .events = 12 });
181 var events: Events = .{};
182 try events.append(0, declarationValue(safety_id, .safety, null));
183 try events.append(
184 0,
185 declarationValue(liveness_id, .bounded_liveness, .{ .steps = 3 }),
186 );
187 var input = try inputReady(explore.Seed.fromU64(5), temporalPlan(2));
188 const site = try requireSite(input.next());
189 const generated = try input.choose(site, try inputChoice(site, .terminal));
190 try events.append(generated.virtual_time_tick, .{ .controlled_input = generated });
191 try events.append(generated.virtual_time_tick, .{ .operation = .{
192 .id = 0x7300,
193 .outcome = .uncertain,
194 } });
195 try events.append(generated.virtual_time_tick + 1, .{ .observation = .{
196 .id = response_id,
197 .value = 1,
198 } });
199 try events.finish(.exhausted);
200
201 const safety = explore.evaluateSafety(&events, .{
202 .property = safety_id,
203 .forbidden = .{ .fault = .machine_crash },
204 });
205 const liveness = explore.evaluateLiveness(&events, .{
206 .property = liveness_id,
207 .trigger = .{ .input = .terminal },
208 .response = .{ .observation = response_id },
209 .bound = .{ .steps = 3 },
210 });
211 try std.testing.expectEqual(explore.Verdict.holds, safety.verdict);
212 try std.testing.expectEqual(explore.Verdict.holds, liveness.verdict);
213 try expectDistinctPropertyEvents(&events, safety, liveness);
214 }
215
216 test "explore: temporal violations and incomplete traces remain distinct" {
217 const Events = explore.EventSequence(.{ .events = 8 });
218 var violated: Events = .{};
219 try violated.append(0, declarationValue(safety_id, .safety, null));
220 try violated.append(
221 0,
222 declarationValue(liveness_id, .bounded_liveness, .{ .virtual_time = 2 }),
223 );
224 try violated.append(1, .{ .controlled_input = generatedTerminal(1) });
225 try violated.append(4, .{ .observation = .{ .id = response_id, .value = 1 } });
226 try violated.append(4, .{ .injected_fault = generatedCrash(4) });
227 try violated.finish(.exhausted);
228
229 const safety = explore.evaluateSafety(&violated, .{
230 .property = safety_id,
231 .forbidden = .{ .fault = .machine_crash },
232 });
233 const liveness = explore.evaluateLiveness(&violated, .{
234 .property = liveness_id,
235 .trigger = .{ .input = .terminal },
236 .response = .{ .observation = response_id },
237 .bound = .{ .virtual_time = 2 },
238 });
239 try std.testing.expectEqual(explore.Verdict.violated, safety.verdict);
240 try std.testing.expectEqual(explore.EvaluationReason.forbidden_event, safety.reason);
241 try std.testing.expectEqual(explore.Verdict.violated, liveness.verdict);
242 try std.testing.expectEqual(explore.EvaluationReason.bound_exceeded, liveness.reason);
243
244 var incomplete: Events = .{};
245 try incomplete.append(
246 0,
247 declarationValue(liveness_id, .bounded_liveness, .{ .steps = 2 }),
248 );
249 try incomplete.append(1, .{ .controlled_input = generatedTerminal(1) });
250 try incomplete.finish(.incomplete);
251 const pending = explore.evaluateLiveness(&incomplete, .{
252 .property = liveness_id,
253 .trigger = .{ .input = .terminal },
254 .response = .{ .observation = response_id },
255 .bound = .{ .steps = 2 },
256 });
257 try std.testing.expectEqual(explore.Verdict.incomplete, pending.verdict);
258 try std.testing.expectEqual(explore.EvaluationReason.trace_incomplete, pending.reason);
259 }
260
261 fn expectGeneratorCapacityRefusals() !void {
262 const SmallInput = explore.InputGenerator(.{ .steps = 1, .alternatives = 5 });
263 try expectIncomplete(.step_capacity, try SmallInput.init(
264 selected_profile,
265 explore.Seed.fromU64(1),
266 temporalPlan(2),
267 ));
268 const SmallSchedule = explore.ScheduleGenerator(.{
269 .steps = 2,
270 .nodes = 1,
271 .alternatives = 2,
272 });
273 try expectIncomplete(.node_capacity, try SmallSchedule.init(
274 selected_profile,
275 explore.Seed.fromU64(1),
276 .{ .temporal = temporalPlan(2), .nodes = 2 },
277 ));
278 const SmallTopology = explore.TopologyGenerator(.{
279 .steps = 2,
280 .nodes = 1,
281 .alternatives = 1,
282 });
283 try expectIncomplete(.alternative_capacity, try SmallTopology.init(
284 selected_profile,
285 explore.Seed.fromU64(1),
286 .{ .temporal = temporalPlan(2), .nodes = 1 },
287 ));
288 const SmallFault = explore.FaultGenerator(.{
289 .steps = 2,
290 .kinds = 1,
291 .alternatives = 2,
292 });
293 const kinds = [_]fault.Kind{ .partition, .machine_crash };
294 try expectIncomplete(.kind_capacity, try SmallFault.init(
295 selected_profile,
296 explore.Seed.fromU64(1),
297 .{ .temporal = temporalPlan(2), .kinds = &kinds },
298 ));
299 }
300
301 fn expectDistinctPropertyEvents(
302 subject: anytype,
303 safety: explore.PropertyEvaluation,
304 liveness: explore.PropertyEvaluation,
305 ) !void {
306 const Recorded = explore.EventSequence(.{ .events = 16 });
307 var recorded: Recorded = .{};
308 for (subject.events()) |event| {
309 try recorded.append(event.virtual_time_tick, event.value);
310 }
311 const tick = subject.events()[subject.events().len - 1].virtual_time_tick;
312 try recorded.append(tick, .{ .property_evaluation = safety });
313 try recorded.append(tick, .{ .property_evaluation = liveness });
314 try recorded.finish(.exhausted);
315 var declarations: u8 = 0;
316 var evaluations: u8 = 0;
317 for (recorded.events()) |event| switch (event.value) {
318 .property_declaration => declarations += 1,
319 .property_evaluation => evaluations += 1,
320 else => {},
321 };
322 try std.testing.expectEqual(@as(u8, 2), declarations);
323 try std.testing.expectEqual(@as(u8, 2), evaluations);
324 }
325
326 fn temporalPlan(steps: u16) explore.TemporalPlan {
327 return .{ .steps = steps, .start_tick = 10, .end_tick = 1_000 };
328 }
329
330 fn inputReady(seed: explore.Seed, plan: explore.TemporalPlan) !Input {
331 return requireReady(Input, try Input.init(selected_profile, seed, plan));
332 }
333
334 fn scheduleReady(seed: explore.Seed, nodes: u8, temporal: explore.TemporalPlan) !Schedule {
335 return requireReady(Schedule, try Schedule.init(
336 selected_profile,
337 seed,
338 .{ .temporal = temporal, .nodes = nodes },
339 ));
340 }
341
342 fn topologyReady(seed: explore.Seed, nodes: u8, temporal: explore.TemporalPlan) !Topology {
343 return requireReady(Topology, try Topology.init(
344 selected_profile,
345 seed,
346 .{ .temporal = temporal, .nodes = nodes },
347 ));
348 }
349
350 fn faultReady(
351 seed: explore.Seed,
352 kinds: []const fault.Kind,
353 temporal: explore.TemporalPlan,
354 ) !Fault {
355 return requireReady(Fault, try Fault.init(
356 selected_profile,
357 seed,
358 .{ .temporal = temporal, .kinds = kinds },
359 ));
360 }
361
362 fn requireReady(comptime GeneratorType: type, result: anytype) !GeneratorType {
363 return switch (result) {
364 .item => |value| value,
365 .exhausted => error.TestUnexpectedExhaustion,
366 .incomplete => error.TestUnexpectedIncomplete,
367 };
368 }
369
370 fn requireSite(result: anytype) !@FieldType(@TypeOf(result), "item") {
371 return switch (result) {
372 .item => |value| value,
373 .exhausted => error.TestUnexpectedExhaustion,
374 .incomplete => error.TestUnexpectedIncomplete,
375 };
376 }
377
378 fn expectReplay(first: anytype, second: @TypeOf(first), step_limit: u16) !void {
379 std.debug.assert(step_limit <= 8);
380 for (0..step_limit) |_| {
381 const left = first.next();
382 switch (left) {
383 .item => |left_site| {
384 const right_site = try requireSite(second.next());
385 try std.testing.expect(sameSite(left_site, right_site));
386 const left_value = try first.choose(left_site, left_site.suggested);
387 const right_value = try second.choose(right_site, right_site.suggested);
388 try std.testing.expectEqualDeep(left_value, right_value);
389 },
390 .exhausted => {
391 try expectExhausted(second.next());
392 return;
393 },
394 .incomplete => |reason| {
395 try expectIncomplete(reason, second.next());
396 return;
397 },
398 }
399 }
400 }
401
402 fn sameSite(left: anytype, right: @TypeOf(left)) bool {
403 if (!std.meta.eql(left.id, right.id)) return false;
404 if (left.count != right.count) return false;
405 if (left.suggested != right.suggested) return false;
406 for (left.values(), right.values()) |left_value, right_value| {
407 if (!std.meta.eql(left_value, right_value)) return false;
408 }
409 return true;
410 }
411
412 fn expectIncomplete(expected: explore.IncompleteReason, result: anytype) !void {
413 switch (result) {
414 .incomplete => |actual| try std.testing.expectEqual(expected, actual),
415 .item, .exhausted => return error.TestExpectedIncomplete,
416 }
417 }
418
419 fn expectExhausted(result: anytype) !void {
420 switch (result) {
421 .exhausted => {},
422 .item, .incomplete => return error.TestExpectedExhaustion,
423 }
424 }
425
426 fn expectOrigin(origin: explore.Origin) !void {
427 const declared = profile.determinism.entry(origin.source);
428 try std.testing.expectEqual(origin.source, declared.source);
429 try std.testing.expectEqual(origin.version, declared.version);
430 }
431
432 fn inputChoice(site: Input.Site, kind: explore.InputKind) !u8 {
433 for (site.values(), 0..) |alternative, index| {
434 if (std.meta.activeTag(alternative.value) == kind) return @intCast(index);
435 }
436 return error.TestChoiceMissing;
437 }
438
439 fn topologyComplete(site: Topology.Site) !u8 {
440 for (site.values(), 0..) |alternative, index| {
441 if (std.meta.activeTag(alternative.value) == .complete) return @intCast(index);
442 }
443 return error.TestChoiceMissing;
444 }
445
446 fn faultChoice(site: Fault.Site, action: std.meta.Tag(explore.FaultAction)) !u8 {
447 for (site.values(), 0..) |alternative, index| {
448 if (std.meta.activeTag(alternative.action) == action) return @intCast(index);
449 }
450 return error.TestChoiceMissing;
451 }
452
453 fn declarationValue(
454 id: explore.SemanticId,
455 kind: explore.PropertyKind,
456 bound: ?explore.Bound,
457 ) explore.EventValue {
458 return .{ .property_declaration = .{ .id = id, .kind = kind, .bound = bound } };
459 }
460
461 fn generatedTerminal(tick: u64) explore.GeneratedInput {
462 return .{
463 .origin = explore.origin(.terminal_input),
464 .virtual_time_tick = tick,
465 .value = .{ .terminal = 1 },
466 };
467 }
468
469 fn generatedCrash(tick: u64) explore.GeneratedFault {
470 return .{
471 .choice_origin = explore.origin(.fault_choice),
472 .effect_origin = explore.origin(.machine_crash),
473 .virtual_time_tick = tick,
474 .action = .{ .inject = .machine_crash },
475 };
476 }