tiny.machine.explore.distributed

1/// The input, schedule, and fault sources that offer the alternatives for one2/// kind of choice, one step at a time (*generators*), each positioned where a3/// settled run the search keeps (*retained branch*) left it. The driver keeps4/// one set for every retained branch, so it can offer each child the choices5/// that follow its own parent's history. `init` builds the three over 8 steps6/// and virtual ticks 1 through 4096 from the selected machine configuration and7/// the 32-byte value the generators draw from (*seed*), and returns8/// `GeneratorUnavailable` when a generator cannot start. `advance` moves the9/// generator that matches the kind of one alternative taken at a step10/// (*decision*) past that decision. `advance` returns `StaleChoiceSite` when11/// the decision's step, alternative count, or chosen value differs from what12/// the generator offers, and `ChoiceOutOfRange` for an alternative past the13/// offered count. A topology decision returns `DecisionStreamMismatch`, because14/// the fixed six levels of choices every workload search walks have no topology15/// level, and a generator with no next step returns `GeneratorUnavailable`. A16/// child's set starts as a copy of its parent's.17pub const Cursors = struct {18    input: Input,19    schedule: Schedule,20    faults: Fault,2122    pub fn init(selected: profile.Profile, seed: explore.Seed) types.Error!Cursors {23        return .{24            .input = try ready(Input, try Input.init(selected, seed, temporal)),25            .schedule = try ready(Schedule, try Schedule.init(selected, seed, .{26                .temporal = temporal,27                .nodes = types.node_count,28            })),29            .faults = try ready(Fault, try Fault.init(selected, seed, .{30                .temporal = temporal,31                .kinds = &types.kinds,32            })),33        };34    }3536    pub fn advance(37        self: *Cursors,38        decision: explore.SearchDecision,39    ) types.Error!void {40        switch (decision.site.stream) {41            .input => {42                const site = try requireSite(self.input.next());43                try match(site, decision);44                const chosen = try self.input.choose(site, decision.alternative);45                if (!std.meta.eql(chosen, decision.choice.input)) {46                    return error.StaleChoiceSite;47                }48            },49            .schedule => {50                const site = try requireSite(self.schedule.next());51                try match(site, decision);52                const chosen = try self.schedule.choose(site, decision.alternative);53                if (!std.meta.eql(chosen, decision.choice.schedule)) {54                    return error.StaleChoiceSite;55                }56            },57            .fault => {58                const site = try requireSite(self.faults.next());59                try match(site, decision);60                const chosen = try self.faults.choose(site, decision.alternative);61                if (!std.meta.eql(chosen, decision.choice.fault)) {62                    return error.StaleChoiceSite;63                }64            },65            .topology => return error.DecisionStreamMismatch,66        }67    }68};

1/// One search of the three-node commit protocol under test (*workload*) that2/// covers every branch of the fixed six levels of choices every workload search3/// walks. The witness gate calls `start` and `run` once for each workload4/// variant and compares the summaries. The driver holds the search plus one5/// protocol state and one cursor set for each of 3584 settled runs the search6/// keeps (*retained branches*), all inside the value, so a caller allocates it7/// in memory it owns. `start` resets the driver for one variant, the selected8/// machine configuration, and the 32-byte value the generators draw from,9/// stores the initial protocol state as branch 0, and queues its first choices.10/// `run` steps the search until the queue of waiting choices empties or a11/// budget runs out, then returns a summary. A branch that violates a rule that12/// fails at the first event that breaks it (*safety rule*) is kept and counted,13/// and the driver grows no children from it. A step that prunes a choice or14/// ends incomplete returns `SearchPruned` or `SearchIncomplete`, so `run`15/// returns a summary only when no branch was skipped. The summary gives the16/// executions, the retained branches, the pruned count, the failures, the17/// reason the search stopped, and how many branches reached the long hang18/// alone, the late delivery alone, both together, or a queued acknowledgement.19/// `runner` gives the search a callback that restarts from a copy of the20/// parent's saved state and cursors, applies one alternative taken at a step,21/// and reports the position in a world's history (*moment*) reached, or a22/// failure when a safety rule is violated. `moment` computes the moment of one23/// retained branch from its saved state.24pub const Driver = struct {25    config: types.Config,26    origin: world.Root,27    search: Search,28    states: [types.search_capacity.retained]state_owner.State,29    cursors: [types.search_capacity.retained]Cursors,30    pending: state_owner.State,31    pending_cursors: Cursors,32    parent: explore.SearchBranchId,33    leaf: bool,34    failures: u32,3536    pub const capacity: explore.SearchCapacity = types.search_capacity;37    pub const budget: explore.SearchBudget = types.budget;3839    pub fn start(40        self: *Driver,41        config: types.Config,42        selected: profile.Profile,43        seed: explore.Seed,44    ) types.Error!void {45        const contract = try profile.contractFingerprint(selected);46        self.config = config;47        self.origin = canon.origin(contract);48        self.failures = 0;49        self.parent = 0;50        self.leaf = false;51        self.states[0] = state_owner.State.init(canon.initialRoot(contract));52        self.cursors[0] = try Cursors.init(selected, seed);53        self.search = try Search.init(try self.moment(0), budget);54        std.debug.assert(self.search.branches().len == 1);55        try self.expand(0);56        std.debug.assert(self.search.frontier().len > 0);57    }5859    pub fn run(self: *Driver) types.Error!types.Exploration {60        for (0..budget.executions + 1) |_| {61            const frontier = self.search.frontier();62            std.debug.assert(frontier.len <= capacity.frontier);63            if (frontier.len == 0) return self.summary(.frontier_empty);64            self.parent = frontier[0].parent;65            std.debug.assert(self.parent < self.search.branches().len);66            self.leaf = (try self.search.branch(self.parent)).depth + 1 == types.depth;67            switch (self.search.step(self.runner())) {68                .completed => |value| try self.settle(value.branch, true),69                .failed => |value| try self.settle(value.branch, false),70                .exhausted => |value| return self.summary(value.reason),71                .pruned => return error.SearchPruned,72                .incomplete => return error.SearchIncomplete,73            }74        }75        return error.SearchIncomplete;76    }7778    pub fn runner(self: *Driver) explore.SearchRunner {79        return .{ .context = self, .execute = execute };80    }8182    pub fn moment(self: *const Driver, id: explore.SearchBranchId) types.Error!world.Moment {83        std.debug.assert(id < self.states.len);84        return world.prepareMoment(self.origin, self.states[id].fabric);85    }8687    fn settle(self: *Driver, id: explore.SearchBranchId, expand_next: bool) types.Error!void {88        std.debug.assert(id > 0);89        std.debug.assert(id < self.states.len);90        std.debug.assert(id < capacity.retained);91        self.states[id] = self.pending;92        self.cursors[id] = self.pending_cursors;93        if (!expand_next) {94            self.failures += 1;95            return;96        }97        try self.expand(id);98    }99100    fn expand(self: *Driver, id: explore.SearchBranchId) types.Error!void {101        const branch = try self.search.branch(id);102        if (branch.depth >= types.depth) return;103        std.debug.assert(branch.depth < types.tree.len);104        const cursors = &self.cursors[id];105        const expansion = switch (types.tree[branch.depth]) {106            .input => try self.search.expandInput(107                id,108                try requireSite(cursors.input.next()),109            ),110            .schedule => try self.search.expandSchedule(111                id,112                try requireSite(cursors.schedule.next()),113            ),114            .fault => try self.search.expandFault(115                id,116                try requireSite(cursors.faults.next()),117            ),118            .topology => return error.DecisionStreamMismatch,119        };120        switch (expansion) {121            .expanded => {},122            .exhausted => return error.SearchIncomplete,123            .pruned => return error.SearchPruned,124        }125    }126127    fn summary(128        self: *const Driver,129        reason: explore.SearchExhaustedReason,130    ) types.Exploration {131        const progress = self.search.progress();132        std.debug.assert(progress.retained == self.search.branches().len);133        std.debug.assert(progress.executions <= budget.executions);134        var result: types.Exploration = .{135            .config = self.config,136            .executions = progress.executions,137            .retained = progress.retained,138            .pruned = progress.pruned,139            .settled_failures = 0,140            .reported_failures = self.failures,141            .exhausted = reason,142            .hang_only_branches = 0,143            .delay_only_branches = 0,144            .conjunction_branches = 0,145            .queued_acknowledgement_branches = 0,146        };147        for (self.search.branches(), 0..) |branch, index| {148            const conjunct = self.states[index].conjunct;149            if (conjunct.queued_acknowledgement) {150                result.queued_acknowledgement_branches += 1;151            }152            if (conjunct.both()) {153                result.conjunction_branches += 1;154            } else if (conjunct.persistent_hang) {155                result.hang_only_branches += 1;156            } else if (conjunct.delayed_delivery) {157                result.delay_only_branches += 1;158            }159            switch (branch.settlement) {160                .failed => {161                    result.settled_failures += 1;162                    std.debug.assert(conjunct.both());163                },164                .origin, .completed => {},165            }166        }167        std.debug.assert(result.settled_failures == self.failures);168        std.debug.assert(result.conjunction_branches >= result.settled_failures);169        return result;170    }171};

1/// Stores sent messages awaiting delivery for one position of the three-node2/// protocol: at most 12, twice the depth of the choice tree. The three-node3/// commit protocol under test (*workload*) pushes each message it sends here4/// and takes it out at delivery. `push` appends one message and returns5/// `MessageCapacityExceeded` when the queue is full. Messages stay in the order6/// sent: `find` returns the index of the earliest message for one destination,7/// and `take` removes it and keeps the others in order. `cancel` drops every8/// message of one kind from one sender. The workload calls `cancel` to withdraw9/// the coordinator's old proposals when the coordinator, node 0, opens a new10/// round, a new attempt to get a value accepted.11pub const Queue = struct {12    storage: [types.message_capacity]types.Message = undefined,13    count: u8 = 0,1415    pub const capacity: u8 = types.message_capacity;1617    pub fn push(self: *Queue, message: types.Message) types.Error!void {18        self.assertValid();19        std.debug.assert(message.sender < types.node_count);20        std.debug.assert(message.destination < types.node_count);21        if (self.count == capacity) return error.MessageCapacityExceeded;22        self.storage[self.count] = message;23        self.count += 1;24        self.assertValid();25    }2627    pub fn find(self: *const Queue, destination: u8) ?u8 {28        self.assertValid();29        std.debug.assert(destination < types.node_count);30        for (self.messages(), 0..) |message, index| {31            if (message.destination == destination) return @intCast(index);32        }33        return null;34    }3536    pub fn take(self: *Queue, index: u8) types.Message {37        self.assertValid();38        std.debug.assert(index < self.count);39        const message = self.storage[index];40        const remaining = self.count - index - 1;41        std.mem.copyForwards(42            types.Message,43            self.storage[index .. index + remaining],44            self.storage[index + 1 .. self.count],45        );46        self.count -= 1;47        self.assertValid();48        return message;49    }5051    pub fn cancel(self: *Queue, sender: u8, kind: types.MessageKind) void {52        self.assertValid();53        std.debug.assert(sender < types.node_count);54        var kept: u8 = 0;55        var index: u8 = 0;56        while (index < self.count) : (index += 1) {57            const message = self.storage[index];58            if (message.sender == sender and message.kind == kind) continue;59            std.debug.assert(kept <= index);60            self.storage[kept] = message;61            kept += 1;62        }63        self.count = kept;64        self.assertValid();65    }6667    pub fn messages(self: *const Queue) []const types.Message {68        std.debug.assert(self.count <= capacity);69        return self.storage[0..self.count];70    }7172    fn assertValid(self: *const Queue) void {73        std.debug.assert(self.count <= capacity);74        std.debug.assert(self.count <= self.storage.len);75    }76};

1/// Runs one given list of alternatives taken at a step (*decisions*) against2/// the three-node commit protocol under test (*workload*) from its initial3/// state, in order and with no search, and records an append-only record of the4/// run (*causal history*), which `seal` later seals. The witness gate uses one5/// to replay a record of one failing run that replays it exactly (*capsule*)6/// and to replay a chosen path, and reads the sealed causal history afterward.7/// Each recorded step of the history (*frame*) holds the step's events recorded8/// for checking rules and the results of checking both rules that fail at the9/// first event that breaks them (*safety rules*), and the rule declarations go10/// into the first frame alone. The history holds at most 8 frames and 6411/// records, and the replayer keeps it and its byte encoding inside the value.12/// `init` binds one workload variant and one profile and starts an empty13/// history, and `begin` restarts from the initial state. `apply` runs one14/// decision and reports the position reached in a world's history (*moment*),15/// or reports a failure when a safety rule is violated. `seal` finishes the16/// history as exhausted and returns its identity. `path` restarts, applies 1 to17/// 8 decisions, and seals. `runner` adapts the replayer for capsule replay: its18/// preparation accepts only the replayer's own profile, the identity of the19/// build each of the workload's three nodes ran, and outside results from host20/// services or effects, and it restarts at the capsule's start moment. The21/// runner's step requires the parent to be the current moment, reports a full22/// history as an incomplete trace, and reports any other error as a rejected23/// replay.24pub const Replayer = struct {25    config: types.Config,26    selected: profile.Profile,27    origin: world.Root,28    state: state_owner.State,29    history: History,30    wire: History.Wire,31    sequence: u16,32    frames: u16,33    failure: ?explore.PropertyEvaluation,34    preparations: u32,3536    pub fn init(37        self: *Replayer,38        config: types.Config,39        selected: profile.Profile,40    ) types.Error!void {41        self.config = config;42        self.selected = selected;43        self.preparations = 0;44        try self.begin();45    }4647    pub fn begin(self: *Replayer) types.Error!void {48        const contract = try profile.contractFingerprint(self.selected);49        self.origin = canon.origin(contract);50        self.state = state_owner.State.init(canon.initialRoot(contract));51        self.history = try History.init(try self.moment());52        self.sequence = 0;53        self.frames = 0;54        self.failure = null;55        std.debug.assert(self.history.traceState() == .open);56    }5758    pub fn apply(59        self: *Replayer,60        decision: explore.SearchDecision,61    ) types.Error!explore.SearchExecution {62        var events: types.Events = .{};63        const verdicts = try workload.evaluate(64            self.config,65            &self.state,66            decision,67            &events,68            false,69        );70        const reached = try self.moment();71        std.debug.assert(reached.fabric.entry_frontier <= self.frames + 1);72        try self.record(decision, reached, &events, verdicts);73        std.debug.assert(self.frames <= types.history_capacity.frames);74        if (property.violation(verdicts)) |failure| {75            self.failure = failure;76            return .{ .failed = .{ .root = reached, .evaluation = failure } };77        }78        return .{ .completed = reached };79    }8081    pub fn seal(self: *Replayer) types.Error!explore.query.Identity {82        std.debug.assert(self.frames > 0);83        return self.history.finish(.exhausted, &self.wire);84    }8586    pub fn runner(self: *Replayer) explore.CapsuleRunner {87        return .{88            .context = self,89            .prepare = prepare,90            .step = .{ .context = self, .execute = execute },91        };92    }9394    pub fn path(95        self: *Replayer,96        decisions: []const explore.SearchDecision,97    ) types.Error!explore.query.Identity {98        std.debug.assert(decisions.len > 0);99        std.debug.assert(decisions.len <= types.history_capacity.frames);100        try self.begin();101        for (decisions) |decision| _ = try self.apply(decision);102        std.debug.assert(self.frames == decisions.len);103        return self.seal();104    }105106    fn moment(self: *const Replayer) types.Error!world.Moment {107        return world.prepareMoment(self.origin, self.state.fabric);108    }109110    fn record(111        self: *Replayer,112        decision: explore.SearchDecision,113        reached: world.Moment,114        events: *const types.Events,115        verdicts: property.Verdicts,116    ) types.Error!void {117        std.debug.assert(self.frames < types.history_capacity.frames);118        const frame = try self.history.appendFrame(decision, reached);119        std.debug.assert(frame == self.frames);120        self.frames += 1;121        for (events.events()) |event| {122            const declaration = std.meta.activeTag(event.value) == .property_declaration;123            if (declaration and frame != 0) continue;124            try self.append(frame, event.virtual_time_tick, event.value);125        }126        for (verdicts) |verdict| {127            try self.append(128                frame,129                self.state.now,130                .{ .property_evaluation = verdict },131            );132        }133    }134135    fn append(136        self: *Replayer,137        frame: u16,138        tick: u64,139        value: explore.EventValue,140    ) types.Error!void {141        try self.history.appendSemantic(frame, .{142            .sequence = self.sequence,143            .virtual_time_tick = tick,144            .value = value,145        });146        std.debug.assert(self.sequence < std.math.maxInt(u16));147        self.sequence += 1;148    }149};

1/// One position of the three-node protocol. The state records the ledger root2/// reached so far, the pending messages, what each node accepted, the3/// coordinator's round, proposal, and acknowledgement count, the commit, which4/// node is hung and for how long, the simulated clock, and which of the two5/// facts the planted defect needs have happened. The driver and the replayer6/// hand one to each workload step and read it back afterward. Only a workload7/// step changes the state. Each step that advances folds the previous ledger8/// digest, the decision, the protocol fields, and the pending messages into the9/// next digest, so two equal histories reach equal *ledger roots* (the digest10/// and counters naming the position of the ledger, the ordered record of every11/// admitted input and fault decision). `init` starts on a given ledger root at12/// tick 1, with no messages, no *round* (one attempt by the coordinator, node13/// 0, to get a value accepted), and no commit. `backing` counts the nodes that14/// accepted the current round's proposal. `votes` counts the coordinator's own15/// vote plus every *acknowledgement* (a node's reply that it accepted a round's16/// proposal) it counted in the current round. `suspecting` holds while a round17/// is open and a node other than the coordinator has stayed hung for at least18/// two fault steps.19pub const State = struct {20    fabric: fabric.Root,21    messages: queue.Queue = .{},22    nodes: [types.node_count]types.Node = @splat(types.Node{}),23    round: u16 = 0,24    open: bool = false,25    proposal: u64 = 0,26    acks: u8 = 0,27    ack_mask: u8 = 0,28    committed: bool = false,29    committed_round: u16 = 0,30    committed_value: u64 = 0,31    hang_streak: u8 = 0,32    hung: ?u8 = null,33    delivery_blocked: bool = false,34    turn_node: ?u8 = null,35    request: u64 = 0,36    now: u64 = types.start_tick,37    conjunct: types.Conjunct = .{},3839    pub fn init(root: fabric.Root) State {40        const value: State = .{ .fabric = root };41        value.assertValid();42        return value;43    }4445    pub fn backing(self: *const State) u8 {46        self.assertValid();47        var count: u8 = 0;48        for (self.nodes) |node| {49            if (!node.accepted) continue;50            if (node.accepted_round != self.round) continue;51            if (node.accepted_value != self.proposal) continue;52            count += 1;53        }54        std.debug.assert(count <= types.node_count);55        return count;56    }5758    pub fn votes(self: *const State) u8 {59        self.assertValid();60        return 1 + self.acks;61    }6263    pub fn suspecting(self: *const State) bool {64        self.assertValid();65        if (!self.open) return false;66        if (self.hang_streak < types.suspicion_steps) return false;67        const hung = self.hung orelse return false;68        return hung != types.coordinator;69    }7071    pub fn assertValid(self: *const State) void {72        std.debug.assert(self.acks <= types.depth);73        std.debug.assert(self.committed_round <= self.round);74        std.debug.assert(self.now >= types.start_tick);75        std.debug.assert(self.now <= types.end_tick);76        if (self.hung) |node| std.debug.assert(node < types.node_count);77        if (self.turn_node) |node| std.debug.assert(node < types.node_count);78        for (self.nodes) |node| std.debug.assert(node.accepted_round <= self.round);79    }80};

1pub const Config = struct {2    variant: Variant,3    persistence: Persistence = .retained,4    delivery: Delivery = .queued,5};

1pub const Conjunct = packed struct(u8) {2    persistent_hang: bool = false,3    delayed_delivery: bool = false,4    queued_acknowledgement: bool = false,5    padding: u5 = 0,67    pub fn both(self: Conjunct) bool {8        return self.persistent_hang and self.delayed_delivery;9    }1011    pub fn either(self: Conjunct) bool {12        return self.persistent_hang or self.delayed_delivery;13    }1415    pub fn merge(self: Conjunct, other: Conjunct) Conjunct {16        return .{17            .persistent_hang = self.persistent_hang or other.persistent_hang,18            .delayed_delivery = self.delayed_delivery or other.delayed_delivery,19            .queued_acknowledgement = self.queued_acknowledgement or20                other.queued_acknowledgement,21        };22    }23};

1pub const Delivery = enum(u8) {2    queued = 1,3    immediate = 2,4};

1pub const Diagnostic = enum(u32) {2    turn_skipped = 1,3    inbox_empty = 2,4};

1pub const Exploration = struct {2    config: Config,3    executions: u32,4    retained: u16,5    pruned: u64,6    settled_failures: u16,7    reported_failures: u32,8    exhausted: explore.SearchExhaustedReason,9    hang_only_branches: u32,10    delay_only_branches: u32,11    conjunction_branches: u32,12    queued_acknowledgement_branches: u32,13};

1pub const Message = struct {2    kind: MessageKind,3    round: u16,4    value: u64,5    sender: u8,6    destination: u8,7};

1pub const MessageKind = enum(u8) {2    propose = 1,3    ack = 2,4};

1pub const Node = struct {2    accepted: bool = false,3    accepted_round: u16 = 0,4    accepted_value: u64 = 0,5    hung: bool = false,6};

1pub const Persistence = enum(u8) {2    retained = 1,3    transient = 2,4};

1pub const Property = enum(explore.SemanticId) {2    commit_quorum = 0x51_0001,3    accept_freshness = 0x51_0002,45    pub fn id(self: Property) explore.SemanticId {6        return @backingInt(self);7    }8};

1pub const Provenance = struct {2    profile: profile.ProfileFingerprint,3    contract: profile.ContractFingerprint,4    determinism: profile.DeterminismIdentity,5    dialect: u16,6    seed: explore.Seed,7};

1pub const Reduction = struct {2    original_frames: u16,3    reduced_frames: u16,4    statistics: explore.CapsuleStatistics,5    minimal: bool,6};

1pub const Replay = struct {2    identity: explore.CapsuleIdentity,3    first: explore.query.Identity,4    second: explore.query.Identity,5    evaluation: explore.PropertyEvaluation,6    conjunct: Conjunct,7};

1pub const Report = struct {2    provenance: Provenance,3    defective: Exploration,4    repaired: Exploration,5    persistent_only: Exploration,6    delayed_only: Exploration,7    reduction: Reduction,8    replay: Replay,9    branch: Signature,10    repeat_matched: bool,11};

1pub const Semantic = enum(explore.SemanticId) {2    round_opened = 0x64_0001,3    proposal_accepted = 0x64_0002,4    acknowledged = 0x64_0003,5    delayed_delivery = 0x64_0004,6    persistent_hang = 0x64_0005,7    node_suspected = 0x64_0006,8    commit_announced = 0x64_0007,9    unbacked_commit = 0x64_0008,10    stale_accept = 0x64_0009,11    delivery_deferred = 0x64_000a,12    host_operation = 0x64_000b,1314    pub fn id(self: Semantic) explore.SemanticId {15        return @backingInt(self);16    }17};

1pub const Signature = struct {2    frame: u16,3    reason: explore.query.DivergenceReason,4    roots: explore.query.RootDifference,5    reference: explore.query.RefWire,6};

1pub const Variant = enum(u8) {2    defective = 1,3    repaired = 2,4};

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

1pub fn builds() [types.node_count]explore.CapsuleBuildIdentity {2    var result: [types.node_count]explore.CapsuleBuildIdentity = undefined;3    for (&result, 0..) |*entry, index| {4        var node: fabric.NodeId = .{ .bytes = @splat(0) };5        node.bytes[node.bytes.len - 1] = @intCast(index + 1);6        var hasher = Sha256.init(.{});7        hasher.update(build_domain);8        hasher.update(&node.bytes);9        var digest: [Sha256.digest_length]u8 = undefined;10        hasher.final(&digest);11        std.debug.assert(node.bytes[node.bytes.len - 1] != 0);12        entry.* = .{ .node = node, .execution = .{ .digest = digest } };13    }14    for (result[1..], result[0 .. result.len - 1]) |next, previous| {15        std.debug.assert(std.mem.lessThan(u8, &previous.node.bytes, &next.node.bytes));16    }17    return result;18}

1pub fn initialRoot(contract: profile.ContractFingerprint) fabric.Root {2    return .{3        .digest = seedDigest(state_domain),4        .dialect = .ordered_effect_fabric_v3,5        .machine_contract = contract,6        .entry_frontier = 0,7        .admission_frontier = 0,8        .fault_frontier = 0,9    };10}

1pub fn origin(contract: profile.ContractFingerprint) world.Root {2    return .{3        .digest = seedDigest(world_domain),4        .dialect = .connected_world_v1,5        .machine_contract = contract,6        .fabric = initialRoot(contract),7        .node_count = types.node_count,8    };9}

1pub const Search = explore.Search(types.search_capacity);

1pub const declarations = [_]explore.PropertyDeclaration{2    .{ .id = quorum_rule.property, .kind = .safety, .bound = null },3    .{ .id = freshness_rule.property, .kind = .safety, .bound = null },4};

1pub const freshness_rule: explore.Safety = .{2    .property = types.Property.accept_freshness.id(),3    .forbidden = .{ .observation = types.Semantic.stale_accept.id() },4};

1pub const quorum_rule: explore.Safety = .{2    .property = types.Property.commit_quorum.id(),3    .forbidden = .{ .observation = types.Semantic.unbacked_commit.id() },4};

1pub const Capsule = explore.Capsule(types.capsule_capacity);

1pub const Diff = explore.query.Diff(types.diff_capacity);

1pub const History = explore.query.History(types.history_capacity);

1pub const Reducer = explore.CapsuleReducer(types.capsule_capacity);

1pub fn provenance(value: profile.Profile) profile.Error!Provenance {2    try profile.validate(value);3    const full = try profile.profileFingerprint(value);4    const contract = try profile.contractFingerprint(value);5    const determinism = value.contract.determinism;6    var hasher = Sha256.init(.{});7    hasher.update(domain);8    hasher.update(&full.digest);9    hasher.update(&contract.digest);10    hasher.update(&determinism.digest);11    var encoded: [6]u8 = undefined;12    std.mem.writeInt(u16, encoded[0..2], @backingInt(determinism.schema), .little);13    std.mem.writeInt(u16, encoded[2..4], determinism.entry_count, .little);14    std.mem.writeInt(u16, encoded[4..6], types.dialect_version, .little);15    hasher.update(&encoded);16    var bytes: [Sha256.digest_length]u8 = undefined;17    hasher.final(&bytes);18    std.debug.assert(!allZero(&bytes));19    return .{20        .profile = full,21        .contract = contract,22        .determinism = determinism,23        .dialect = types.dialect_version,24        .seed = .{ .bytes = bytes },25    };26}

1pub fn selected() profile.Profile {2    return profile.interpretedContinuationTestV1();3}

1pub const Error = explore.GeneratorError ||2    explore.CapsuleError ||3    explore.query.Error ||4    OwnerError;

1pub const Events = explore.EventSequence(.{ .events = event_capacity });

1pub const budget: explore.SearchBudget = .{ .executions = 4096, .depth = depth };

1pub const capsule_capacity: explore.CapsuleCapacity = .{2    .frames = 8,3    .builds = node_count,4};

1pub const coordinator: u8 = 0;

1pub const defective: Config = .{ .variant = .defective };

1pub const delayed_only: Config = .{2    .variant = .defective,3    .persistence = .transient,4};

1pub const history_capacity: explore.query.Capacity = .{2    .frames = 8,3    .evidence = 64,4};

1pub const kinds = [_]fault.Kind{ .process_crash, .packet_delay };

1pub const node_count: u8 = 3;

1pub const persistent_only: Config = .{2    .variant = .defective,3    .delivery = .immediate,4};

1pub const quorum: u8 = 2;

1pub const repaired: Config = .{ .variant = .repaired };

1pub const search_capacity: explore.SearchCapacity = .{2    .frontier = 3072,3    .retained = 3584,4};

1pub const suspicion_steps: u8 = 2;

1pub const tree = [_]explore.Stream{2    .input,3    .schedule,4    .fault,5    .fault,6    .schedule,7    .schedule,8};

1pub fn step(2    config: types.Config,3    value: *State,4    decision: explore.SearchDecision,5    events: *types.Events,6) types.Error!void {7    std.debug.assert(decision.valid());8    value.assertValid();9    const previous = value.now;10    const entry_frontier = value.fabric.entry_frontier;11    value.now = @max(value.now, choiceTick(decision));12    std.debug.assert(value.now >= previous);13    try record(events, value.now, decision);14    const advanced = switch (decision.choice) {15        .input => |choice| try applyInput(value, choice, events),16        .schedule => |choice| try applySchedule(config, value, choice, events),17        .fault => |choice| try applyFault(config, value, choice, events),18        .topology => return error.DecisionStreamMismatch,19    };20    if (advanced) value.fabric = canon.advance(value.fabric, decision, value);21    std.debug.assert(value.fabric.entry_frontier == entry_frontier + @intFromBool(advanced));22    value.assertValid();23}

1//! A tool that searches for bugs earns trust by finding a real one in a running2//! system and replaying it on demand. This namespace runs a small three-node3//! commit protocol with a bug planted on purpose, and a gate that has to find4//! the bug, shrink it, replay it, and show that the fixed protocol survives the5//! same search.6//!7//! In the protocol, node 0 coordinates rounds. Opening a round sends a proposal8//! to the other two nodes, a node that receives the proposal accepts it and9//! replies with an acknowledgement, and the coordinator announces a commit once10//! its own vote plus the acknowledgements it counted reach two. Two safety11//! rules are declared before any search runs: a commit needs two nodes that12//! accepted the current round's value, and a node never accepts a proposal from13//! an older round. The gate answers by passing or failing the package tests,14//! and on success it returns a report for a renderer to show.15//!16//! A rule or a seed picked after seeing the failure proves nothing, so the17//! rules are fixed ahead of the search and the seed comes from the machine18//! configuration alone. A bug that one fault can trigger exercises little, so19//! the planted bug needs two faults acting together across steps. A search that20//! stops at the first failure, or whose result depends on the order it tries21//! things in, can miss the bug or misreport it, so the search has to cover one22//! fixed tree completely and keep going after each failure. A fix is believable23//! only when it survives the same search that found the bug.24//!25//! The planted bug (the *seeded defect*) lives in how the coordinator counts.26//! The defective variant counts every acknowledgement, a late one from a closed27//! round and a repeat from the same node alike, so it can announce a commit28//! that fewer than two nodes back. The bug needs two facts at once, a *stateful29//! conjunction*: a node stays hung across two fault steps, so the coordinator30//! suspects it and opens a new round, and an acknowledgement from the closed31//! round arrives afterward. Every search walks the same six levels of choices,32//! a *frozen choice tree*, in the order input, schedule, fault, fault,33//! schedule, schedule, under a budget of 4096 executions. The seed is a SHA-25634//! digest over the identities of the machine configuration, its shared35//! execution rules, and its list of places where two runs could differ,36//! together with the protocol's encoding version.37//!38//! The defective search covers the tree in 3017 executions with nothing pruned,39//! and it settles nine failing branches, each of which carries both facts. Two40//! single-fault variants run the same budget and fail nowhere: one delivers41//! every acknowledgement the moment it is sent, and the other never lets a hang42//! last. The repaired variant counts an acknowledgement only for the current43//! round and only once per node, reaches both facts together in 17 branches,44//! and violates neither rule.45//!46//! The first failure shrinks to five steps, and the gate confirms that none of47//! them can be removed: a terminal input, a step for a node other than the48//! coordinator, an injected crash, the crash held for another step, and a step49//! for the coordinator. The shortened record replays twice to one history50//! identity and survives a round trip through its byte encoding. A sibling path51//! that takes another alternative at the last choice gives the first step where52//! two recorded histories differ, as one stable *first divergence* at that53//! choice, encoded as a reference, and it records the reason and which fields54//! of the two reached positions differ. The report carries where the seed came55//! from, the four search summaries, the shrinking statistics, the replay56//! identities, and the signature of that first divergence.57//!58//! - *workload*: the three-node replicated-commit protocol the gate explores,59//!   in a defective, a repaired, or a single-fault variant.60//! - *witness gate*: the run that finds the defect, shrinks its capsule,61//!   replays it twice, branches from it, and checks the single-fault and62//!   repaired variants.63//! - *capsule*: a fixed-capacity record of one failing run that replays it64//!   exactly.65//! - *seed provenance*: the record of where the gate's seed came from: the66//!   profile fingerprint, the contract fingerprint, the inventory identity, the67//!   encoding version, and the seed itself.6869const canon = @import("canon.zig");70const driver = @import("driver.zig");71const property = @import("property.zig");72const queue = @import("queue.zig");73const replay = @import("replay.zig");74const seed = @import("seed.zig");75const state = @import("state.zig");76const types = @import("types.zig");77const witness = @import("witness.zig");78const workload = @import("workload.zig");7980pub const Capsule = replay.Capsule;81pub const Config = types.Config;82pub const Conjunct = types.Conjunct;83pub const Cursors = driver.Cursors;84pub const Delivery = types.Delivery;85pub const Diagnostic = types.Diagnostic;86pub const Diff = replay.Diff;87pub const Driver = driver.Driver;88pub const Error = types.Error;89pub const Events = types.Events;90pub const Exploration = types.Exploration;91pub const History = replay.History;92pub const Message = types.Message;93pub const MessageKind = types.MessageKind;94pub const Node = types.Node;95pub const Persistence = types.Persistence;96pub const Property = types.Property;97pub const Provenance = types.Provenance;98pub const Queue = queue.Queue;99pub const Reducer = replay.Reducer;100pub const Reduction = types.Reduction;101pub const Replay = types.Replay;102pub const Replayer = replay.Replayer;103pub const Report = types.Report;104pub const Search = driver.Search;105pub const Semantic = types.Semantic;106pub const Signature = types.Signature;107pub const State = state.State;108pub const Variant = types.Variant;109pub const Witness = witness.Witness;110pub const budget = types.budget;111pub const capsule_capacity = types.capsule_capacity;112pub const coordinator = types.coordinator;113pub const declarations = property.declarations;114pub const defective = types.defective;115pub const delayed_only = types.delayed_only;116pub const depth = types.depth;117pub const freshness_rule = property.freshness_rule;118pub const history_capacity = types.history_capacity;119pub const kinds = types.kinds;120pub const node_count = types.node_count;121pub const persistent_only = types.persistent_only;122pub const quorum = types.quorum;123pub const quorum_rule = property.quorum_rule;124pub const repaired = types.repaired;125pub const search_capacity = types.search_capacity;126pub const suspicion_steps = types.suspicion_steps;127pub const tree = types.tree;128pub const builds = canon.builds;129pub const initialRoot = canon.initialRoot;130pub const origin = canon.origin;131pub const seedProvenance = seed.provenance;132pub const selectedProfile = seed.selected;133pub const step = workload.step;

1pub const distributed = @import("distributed/root.zig");

1pub const depth: u16 = tree.len;