lib/machine/src/explore/distributed/test.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const distributed = @import("root.zig");
2 const explore = @import("../root.zig");
3 const fault = @import("../../fault/root.zig");
4 const profile = @import("../../profile/root.zig");
5 const std = @import("std");
6
7 const Witness = distributed.Witness;
8
9 test {
10 _ = @import("queue.zig");
11 _ = @import("seed.zig");
12 }
13
14 test "distributed: exhaustive search finds and retains the seeded quorum defect" {
15 const witness = try std.testing.allocator.create(Witness);
16 defer std.testing.allocator.destroy(witness);
17 const report = try witness.run();
18 const defective = report.defective;
19 try std.testing.expectEqualDeep(distributed.defective, defective.config);
20 try std.testing.expectEqual(
21 explore.SearchExhaustedReason.frontier_empty,
22 defective.exhausted,
23 );
24 try std.testing.expectEqual(@as(u64, 0), defective.pruned);
25 try std.testing.expectEqual(@as(u32, 3017), defective.executions);
26 try std.testing.expectEqual(@as(u16, 3018), defective.retained);
27 try std.testing.expect(defective.executions < distributed.budget.executions);
28 try std.testing.expectEqual(@as(u16, 9), defective.settled_failures);
29 try std.testing.expectEqual(@as(u32, 9), defective.reported_failures);
30 try std.testing.expectEqual(@as(u32, 9), defective.conjunction_branches);
31 try std.testing.expectEqual(@as(u32, 7), defective.hang_only_branches);
32 try std.testing.expectEqual(@as(u32, 0), defective.delay_only_branches);
33 try std.testing.expectEqual(
34 @as(u32, 86),
35 defective.queued_acknowledgement_branches,
36 );
37 }
38
39 test "distributed: neither single fault reaches the defect under the same budget" {
40 const witness = try std.testing.allocator.create(Witness);
41 defer std.testing.allocator.destroy(witness);
42 const report = try witness.run();
43 const persistent = report.persistent_only;
44 try std.testing.expectEqualDeep(distributed.persistent_only, persistent.config);
45 try expectExhausted(persistent);
46 try std.testing.expectEqual(@as(u32, 3025), persistent.executions);
47 try std.testing.expectEqual(@as(u16, 0), persistent.settled_failures);
48 try std.testing.expectEqual(@as(u32, 7), persistent.hang_only_branches);
49 try std.testing.expectEqual(@as(u32, 0), persistent.conjunction_branches);
50 try std.testing.expectEqual(
51 @as(u32, 0),
52 persistent.queued_acknowledgement_branches,
53 );
54 const delayed = report.delayed_only;
55 try std.testing.expectEqualDeep(distributed.delayed_only, delayed.config);
56 try expectExhausted(delayed);
57 try std.testing.expectEqual(@as(u32, 3025), delayed.executions);
58 try std.testing.expectEqual(@as(u16, 0), delayed.settled_failures);
59 try std.testing.expectEqual(@as(u32, 0), delayed.hang_only_branches);
60 try std.testing.expectEqual(@as(u32, 0), delayed.conjunction_branches);
61 try std.testing.expectEqual(
62 @as(u32, 94),
63 delayed.queued_acknowledgement_branches,
64 );
65 }
66
67 test "distributed: the repaired variant survives the identical frozen budget" {
68 const witness = try std.testing.allocator.create(Witness);
69 defer std.testing.allocator.destroy(witness);
70 const report = try witness.run();
71 const repaired = report.repaired;
72 try std.testing.expectEqualDeep(distributed.repaired, repaired.config);
73 try std.testing.expectEqual(
74 explore.SearchExhaustedReason.frontier_empty,
75 repaired.exhausted,
76 );
77 try std.testing.expectEqual(@as(u16, 0), repaired.settled_failures);
78 try std.testing.expectEqual(@as(u64, 0), repaired.pruned);
79 try std.testing.expectEqual(@as(u32, 17), repaired.conjunction_branches);
80 try std.testing.expectEqual(@as(u32, 3025), repaired.executions);
81 try std.testing.expect(repaired.executions >= report.defective.executions);
82 try std.testing.expect(repaired.executions < distributed.budget.executions);
83 try std.testing.expect(repaired.retained <= distributed.search_capacity.retained);
84 try std.testing.expectEqual(
85 @as(u32, 94),
86 repaired.queued_acknowledgement_branches,
87 );
88 }
89
90 test "distributed: the first capsule minimizes and replays exactly twice" {
91 const witness = try std.testing.allocator.create(Witness);
92 defer std.testing.allocator.destroy(witness);
93 const report = try witness.run();
94 try std.testing.expect(report.reduction.minimal);
95 try std.testing.expectEqual(@as(u16, 5), report.reduction.original_frames);
96 try std.testing.expectEqual(@as(u16, 5), report.reduction.reduced_frames);
97 try std.testing.expectEqual(@as(u32, 5), report.reduction.statistics.attempts);
98 try std.testing.expectEqual(@as(u16, 0), report.reduction.statistics.accepted);
99 try std.testing.expectEqual(@as(u32, 5), report.reduction.statistics.rejected);
100 try std.testing.expect(report.replay.conjunct.both());
101 try std.testing.expectEqual(
102 explore.Verdict.violated,
103 report.replay.evaluation.verdict,
104 );
105 try std.testing.expectEqual(
106 distributed.Property.commit_quorum.id(),
107 report.replay.evaluation.id,
108 );
109 try std.testing.expectEqualDeep(report.replay.first, report.replay.second);
110 try std.testing.expect(report.repeat_matched);
111 try expectStableWire(witness.reduced, report.replay.identity);
112 }
113
114 test "distributed: a branch from the failing history has one stable first divergence" {
115 const witness = try std.testing.allocator.create(Witness);
116 defer std.testing.allocator.destroy(witness);
117 const report = try witness.run();
118 try std.testing.expectEqual(
119 explore.query.DivergenceReason.choice,
120 report.branch.reason,
121 );
122 try std.testing.expectEqual(@as(u16, 5), witness.length);
123 try std.testing.expectEqual(@as(u16, 4), report.branch.frame);
124 try std.testing.expect(report.branch.roots.any());
125 try std.testing.expect(report.branch.roots.moment_digest);
126 try std.testing.expectEqualDeep(report.branch, try witness.fork());
127 const reference = try explore.query.decodeRef(&report.branch.reference);
128 try std.testing.expectEqual(explore.query.Target.choice, reference.target);
129 try std.testing.expectEqual(report.branch.frame, reference.index);
130 try std.testing.expectEqualDeep(
131 try witness.primary.history.identity(),
132 reference.history,
133 );
134 }
135
136 test "distributed: the failing history carries both stateful conjuncts" {
137 const witness = try std.testing.allocator.create(Witness);
138 defer std.testing.allocator.destroy(witness);
139 _ = try witness.run();
140 const history = &witness.primary.history;
141 try std.testing.expect(try observed(history, .persistent_hang));
142 try std.testing.expect(try observed(history, .delayed_delivery));
143 try std.testing.expect(try observed(history, .node_suspected));
144 try std.testing.expect(try observed(history, .unbacked_commit));
145 try std.testing.expect(!try observed(history, .stale_accept));
146 }
147
148 test "distributed: declarations precede every evaluation in the failing history" {
149 const witness = try std.testing.allocator.create(Witness);
150 defer std.testing.allocator.destroy(witness);
151 _ = try witness.run();
152 const records = try witness.primary.history.frameEvidence(0);
153 try std.testing.expect(records.len > distributed.declarations.len);
154 for (
155 distributed.declarations,
156 records[0..distributed.declarations.len],
157 ) |declared, record| {
158 const event = try semantic(record);
159 switch (event.value) {
160 .property_declaration => |value| try std.testing.expectEqualDeep(
161 declared,
162 value,
163 ),
164 else => return error.TestExpectedDeclaration,
165 }
166 }
167 try expectEvaluationOrder(&witness.primary.history);
168 }
169
170 test "distributed: the frozen tree and budget bind both variants" {
171 try std.testing.expectEqual(@as(u16, 6), distributed.depth);
172 try std.testing.expectEqual(@as(u16, distributed.tree.len), distributed.depth);
173 try std.testing.expectEqual(distributed.depth, distributed.budget.depth);
174 try std.testing.expectEqual(@as(u8, 3), distributed.node_count);
175 try std.testing.expectEqual(@as(u8, 2), distributed.quorum);
176 try std.testing.expectEqual(@as(u8, 2), distributed.suspicion_steps);
177 try std.testing.expectEqual(@as(usize, 2), distributed.declarations.len);
178 try std.testing.expectEqual(
179 distributed.node_count,
180 distributed.capsule_capacity.builds,
181 );
182 const identities = distributed.builds();
183 try std.testing.expectEqual(@as(usize, distributed.node_count), identities.len);
184 for (identities[1..], identities[0 .. identities.len - 1]) |next, previous| {
185 try std.testing.expect(std.mem.lessThan(
186 u8,
187 &previous.node.bytes,
188 &next.node.bytes,
189 ));
190 }
191 }
192
193 test "distributed: the minimized capsule is exactly the stateful conjunction" {
194 const witness = try std.testing.allocator.create(Witness);
195 defer std.testing.allocator.destroy(witness);
196 _ = try witness.run();
197 const frames = witness.reduced.frames();
198 try std.testing.expectEqual(@as(usize, 5), frames.len);
199 for (frames, distributed.tree[0..frames.len]) |frame, stream| {
200 try std.testing.expectEqual(stream, frame.decision.site.stream);
201 }
202 try expectInput(frames[0], .terminal);
203 try std.testing.expect(try expectTurn(frames[1]) != distributed.coordinator);
204 try expectFault(frames[2], .inject);
205 try expectFault(frames[3], .persist);
206 try std.testing.expectEqual(distributed.coordinator, try expectTurn(frames[4]));
207 try std.testing.expectEqual(@as(usize, 2), distributed.kinds.len);
208 try std.testing.expectEqual(fault.Kind.packet_delay, distributed.kinds[1]);
209 }
210
211 fn expectInput(frame: explore.CapsuleFrame, kind: explore.InputKind) !void {
212 const choice = switch (frame.decision.choice) {
213 .input => |value| value,
214 .schedule, .topology, .fault => return error.TestExpectedInputChoice,
215 };
216 try std.testing.expectEqual(kind, std.meta.activeTag(choice.value));
217 }
218
219 fn expectTurn(frame: explore.CapsuleFrame) !u8 {
220 const choice = switch (frame.decision.choice) {
221 .schedule => |value| value,
222 .input, .topology, .fault => return error.TestExpectedScheduleChoice,
223 };
224 return switch (choice.value) {
225 .turn => |node| node,
226 .idle => error.TestExpectedTurn,
227 };
228 }
229
230 fn expectFault(
231 frame: explore.CapsuleFrame,
232 action: std.meta.Tag(explore.FaultAction),
233 ) !void {
234 const choice = switch (frame.decision.choice) {
235 .fault => |value| value,
236 .input, .schedule, .topology => return error.TestExpectedFaultChoice,
237 };
238 try std.testing.expectEqual(action, std.meta.activeTag(choice.action));
239 const kind = switch (choice.action) {
240 .inject, .persist, .recover => |value| value,
241 .healthy => return error.TestExpectedFaultKind,
242 };
243 try std.testing.expectEqual(fault.Kind.process_crash, kind);
244 }
245
246 test "distributed: every capsule frame draws from the versioned determinism profile" {
247 const witness = try std.testing.allocator.create(Witness);
248 defer std.testing.allocator.destroy(witness);
249 const report = try witness.run();
250 const derived = try distributed.seedProvenance(distributed.selectedProfile());
251 try std.testing.expectEqualDeep(derived, report.provenance);
252 try std.testing.expectEqualDeep(
253 profile.determinism.inventory_identity,
254 report.provenance.determinism,
255 );
256 try std.testing.expectEqual(@as(u16, 1), report.provenance.dialect);
257 var sources: u8 = 0;
258 for (witness.reduced.frames()) |frame| {
259 switch (frame.decision.choice) {
260 .input => |value| sources += try expectOrigin(value.origin),
261 .schedule => |value| sources += try expectOrigin(value.origin),
262 .topology => |value| sources += try expectOrigin(value.origin),
263 .fault => |value| {
264 sources += try expectOrigin(value.choice_origin);
265 if (value.effect_origin) |value_origin| {
266 sources += try expectOrigin(value_origin);
267 }
268 },
269 }
270 }
271 try std.testing.expectEqual(@as(u8, 7), sources);
272 }
273
274 fn expectOrigin(value: explore.Origin) !u8 {
275 const declared = profile.determinism.entry(value.source);
276 try std.testing.expectEqual(value.source, declared.source);
277 try std.testing.expectEqual(declared.version, value.version);
278 try std.testing.expect(declared.version > 0);
279 return 1;
280 }
281
282 fn expectExhausted(exploration: distributed.Exploration) !void {
283 try std.testing.expectEqual(
284 explore.SearchExhaustedReason.frontier_empty,
285 exploration.exhausted,
286 );
287 try std.testing.expectEqual(@as(u64, 0), exploration.pruned);
288 try std.testing.expect(exploration.executions < distributed.budget.executions);
289 }
290
291 fn expectStableWire(
292 value: distributed.Capsule,
293 identity: explore.CapsuleIdentity,
294 ) !void {
295 var wire: distributed.Capsule.Wire = undefined;
296 try value.encode(&wire);
297 const restored = try distributed.Capsule.decode(&wire);
298 var restored_wire: distributed.Capsule.Wire = undefined;
299 try restored.encode(&restored_wire);
300 try std.testing.expectEqualSlices(u8, &wire, &restored_wire);
301 try std.testing.expectEqualDeep(identity, try restored.identity());
302 try std.testing.expectEqual(
303 @as(usize, distributed.node_count),
304 restored.builds().len,
305 );
306 try std.testing.expectEqual(@as(u16, 5), restored.frame_count);
307 }
308
309 fn expectEvaluationOrder(history: anytype) !void {
310 var last_declaration: ?u16 = null;
311 var evaluations: u16 = 0;
312 var freshness: u16 = 0;
313 for (history.evidence()) |record| {
314 const event = semantic(record) catch continue;
315 switch (event.value) {
316 .property_declaration => last_declaration = event.sequence,
317 .property_evaluation => |value| {
318 evaluations += 1;
319 try std.testing.expect(last_declaration != null);
320 try std.testing.expect(event.sequence > last_declaration.?);
321 if (value.id != distributed.Property.accept_freshness.id()) continue;
322 freshness += 1;
323 try std.testing.expect(value.verdict != .violated);
324 },
325 else => {},
326 }
327 }
328 try std.testing.expect(evaluations > 0);
329 try std.testing.expect(freshness > 0);
330 }
331
332 fn observed(history: anytype, id: distributed.Semantic) !bool {
333 for (history.evidence()) |record| {
334 const event = semantic(record) catch continue;
335 switch (event.value) {
336 .observation => |value| if (value.id == id.id()) return true,
337 else => {},
338 }
339 }
340 return false;
341 }
342
343 fn semantic(record: explore.query.Evidence) !explore.Event {
344 return switch (record) {
345 .semantic => |value| value,
346 .machine, .transition => error.TestExpectedSemanticEvidence,
347 };
348 }