lib/machine/src/explore/distributed/witness.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const canon = @import("canon.zig");
2 const driver_owner = @import("driver.zig");
3 const explore = @import("../root.zig");
4 const profile = @import("../../profile/root.zig");
5 const replay = @import("replay.zig");
6 const seed_owner = @import("seed.zig");
7 const std = @import("std");
8 const types = @import("types.zig");
9
10 const Failed = @FieldType(explore.SearchOutcome, "failed");
11 const Path = [types.depth]explore.SearchDecision;
12
13 /// One run of the whole defect gate finds the bug planted on purpose in the
14 /// defective variant: the coordinator counts every acknowledgement, late or
15 /// repeated, so it can announce a commit that fewer than two nodes back. The
16 /// gate shrinks that record of one failing run that replays it exactly
17 /// (*capsule*), replays it twice, branches from it, and checks both
18 /// single-fault variants and the repaired variant. A test calls `run` once and
19 /// checks the report it returns. The witness holds the search driver, three
20 /// replayers, two reducers, a history comparison, both capsules, and the
21 /// failing and sibling paths inside the value, so a caller allocates it in
22 /// memory it owns. The call to `run` returns `FailureMissing` when the
23 /// defective search settles no failure. The first failure becomes a capsule,
24 /// which the gate shrinks and then tests by deleting in turn each remaining
25 /// step of the capsule (*frame*), to report whether any single frame can still
26 /// go. The shortened capsule replays on two replayers, and `run` returns
27 /// `ReplayRejected` unless both reach the same history identity, their
28 /// histories never diverge, and both reach the same result of checking one
29 /// rule. Branching replays the failing path and a sibling that takes another
30 /// alternative at the last decision, compares the two histories, and identifies
31 /// the first step where two histories differ, with the reason (*first
32 /// divergence*). The gate encodes that first divergence as the history's
33 /// identity, a target, and an index, and `run` returns `SiblingMissing` when no
34 /// sibling or divergence exists. A failure in either single-fault search or in
35 /// the repaired search returns `RepairRegressed`. The report gives the record
36 /// of where the seed came from, the four search summaries, the shrinking
37 /// result, the replay identities, and the signature of the first divergence.
38 /// The `fork` function reads the paths that `run` records, so a caller calls it
39 /// after `run`.
40 pub const Witness = struct {
41 driver: driver_owner.Driver,
42 primary: replay.Replayer,
43 repeat: replay.Replayer,
44 alternate: replay.Replayer,
45 reducer: replay.Reducer,
46 probe: replay.Reducer,
47 diff: replay.Diff,
48 capsule: replay.Capsule,
49 reduced: replay.Capsule,
50 failing: Path,
51 sibling: Path,
52 length: u16,
53
54 pub fn run(self: *Witness) types.Error!types.Report {
55 const selected = seed_owner.selected();
56 const derived = try seed_owner.provenance(selected);
57 try self.driver.start(types.defective, selected, derived.seed);
58 const defective = try self.driver.run();
59 if (defective.settled_failures == 0) return error.FailureMissing;
60 std.debug.assert(defective.conjunction_branches >= defective.settled_failures);
61 try self.primary.init(types.defective, selected);
62 try self.repeat.init(types.defective, selected);
63 try self.alternate.init(types.defective, selected);
64 try self.capture(selected);
65 const reduction = try self.minimize();
66 const replayed = try self.confirm();
67 try self.collect();
68 const branch = try self.fork();
69 const persistent_only = try self.ablate(types.persistent_only, derived);
70 const delayed_only = try self.ablate(types.delayed_only, derived);
71 try self.driver.start(types.repaired, selected, derived.seed);
72 const repaired = try self.driver.run();
73 if (repaired.settled_failures != 0) return error.RepairRegressed;
74 std.debug.assert(repaired.exhausted == defective.exhausted);
75 return .{
76 .provenance = derived,
77 .defective = defective,
78 .repaired = repaired,
79 .persistent_only = persistent_only,
80 .delayed_only = delayed_only,
81 .reduction = reduction,
82 .replay = replayed,
83 .branch = branch,
84 .repeat_matched = true,
85 };
86 }
87
88 fn ablate(
89 self: *Witness,
90 config: types.Config,
91 derived: types.Provenance,
92 ) types.Error!types.Exploration {
93 try self.driver.start(config, seed_owner.selected(), derived.seed);
94 const result = try self.driver.run();
95 if (result.settled_failures != 0) return error.RepairRegressed;
96 std.debug.assert(result.exhausted == .frontier_empty);
97 std.debug.assert(result.conjunction_branches == 0);
98 return result;
99 }
100
101 fn capture(self: *Witness, selected: profile.Profile) types.Error!void {
102 const failure = try self.firstFailure();
103 const builds = canon.builds();
104 self.capsule = switch (try replay.Capsule.capture(
105 &self.driver.search,
106 failure,
107 selected,
108 &builds,
109 self.primary.runner(),
110 )) {
111 .published => |value| value,
112 .rejected => return error.CaptureRejected,
113 };
114 }
115
116 fn minimize(self: *Witness) types.Error!types.Reduction {
117 self.reducer = switch (try replay.Reducer.init(
118 self.capsule,
119 self.primary.runner(),
120 )) {
121 .ready => |value| value,
122 .rejected => return error.ReplayRejected,
123 };
124 const result = try self.reducer.reduce(self.primary.runner());
125 self.reduced = result.capsule;
126 std.debug.assert(self.reduced.frame_count > 0);
127 std.debug.assert(self.reduced.frame_count <= self.capsule.frame_count);
128 return .{
129 .original_frames = self.capsule.frame_count,
130 .reduced_frames = self.reduced.frame_count,
131 .statistics = result.statistics,
132 .minimal = try self.minimal(),
133 };
134 }
135
136 fn minimal(self: *Witness) types.Error!bool {
137 if (self.reduced.frame_count == 1) return true;
138 var frame: u16 = 0;
139 while (frame < self.reduced.frame_count) : (frame += 1) {
140 self.probe = switch (try replay.Reducer.init(
141 self.reduced,
142 self.repeat.runner(),
143 )) {
144 .ready => |value| value,
145 .rejected => return error.ReplayRejected,
146 };
147 switch (try self.probe.tryRemove(frame, self.repeat.runner())) {
148 .accepted => return false,
149 .rejected => {},
150 }
151 }
152 return true;
153 }
154
155 fn confirm(self: *Witness) types.Error!types.Replay {
156 const first = try require(try self.reduced.replay(self.primary.runner()));
157 const first_identity = try self.primary.seal();
158 const second = try require(try self.reduced.replay(self.repeat.runner()));
159 const second_identity = try self.repeat.seal();
160 if (!std.meta.eql(first, second)) return error.ReplayRejected;
161 if (!std.meta.eql(first_identity, second_identity)) return error.ReplayRejected;
162 const compared = try self.diff.run(
163 &self.primary.history,
164 &self.repeat.history,
165 types.diff_work,
166 );
167 if (compared.divergence != null) return error.ReplayRejected;
168 return .{
169 .identity = try self.reduced.identity(),
170 .first = first_identity,
171 .second = second_identity,
172 .evaluation = first,
173 .conjunct = self.primary.state.conjunct,
174 };
175 }
176
177 fn collect(self: *Witness) types.Error!void {
178 const failure = try self.firstFailure();
179 const decisions = try self.driver.search.history(failure.branch, &self.failing);
180 self.length = @intCast(decisions.len);
181 std.debug.assert(self.length > 0);
182 std.debug.assert(self.length <= types.depth);
183 @memcpy(self.sibling[0..self.length], decisions);
184 self.sibling[self.length - 1] = try self.siblingDecision(failure);
185 }
186
187 pub fn fork(self: *Witness) types.Error!types.Signature {
188 _ = try self.primary.path(self.failing[0..self.length]);
189 _ = try self.alternate.path(self.sibling[0..self.length]);
190 const compared = try self.diff.run(
191 &self.primary.history,
192 &self.alternate.history,
193 types.diff_work,
194 );
195 const divergence = compared.divergence orelse return error.SiblingMissing;
196 const left = divergence.left orelse return error.SiblingMissing;
197 std.debug.assert(left.choice.index < self.length);
198 var reference: explore.query.RefWire = undefined;
199 explore.query.encodeRef(left.choice, &reference);
200 std.debug.assert(std.meta.eql(
201 try explore.query.decodeRef(&reference),
202 left.choice,
203 ));
204 return .{
205 .frame = left.choice.index,
206 .reason = divergence.reason,
207 .roots = divergence.roots,
208 .reference = reference,
209 };
210 }
211
212 fn siblingDecision(
213 self: *const Witness,
214 failure: Failed,
215 ) types.Error!explore.SearchDecision {
216 for (self.driver.search.branches()) |candidate| {
217 const parent = candidate.parent orelse continue;
218 const decision = candidate.decision orelse continue;
219 if (parent != failure.parent) continue;
220 if (!std.meta.eql(decision.site, failure.decision.site)) continue;
221 if (decision.alternative == failure.decision.alternative) continue;
222 return decision;
223 }
224 return error.SiblingMissing;
225 }
226
227 fn firstFailure(self: *const Witness) types.Error!Failed {
228 for (self.driver.search.branches(), 0..) |candidate, index| {
229 const evaluation = switch (candidate.settlement) {
230 .failed => |value| value,
231 .origin, .completed => continue,
232 };
233 std.debug.assert(index > 0);
234 return .{
235 .branch = @intCast(index),
236 .parent = candidate.parent.?,
237 .decision = candidate.decision.?,
238 .evaluation = evaluation,
239 };
240 }
241 return error.FailureMissing;
242 }
243 };
244
245 fn require(result: explore.CapsuleReplay) types.Error!explore.PropertyEvaluation {
246 return switch (result) {
247 .reproduced => |value| value,
248 .rejected => error.ReplayRejected,
249 };
250 }