tiny.machine.explore

1pub const BuildIdentity = struct {2    node: fabric.NodeId,3    execution: instance.ExecutionFingerprint,4};

1pub const Capacity = struct {2    frames: u16,3    builds: u8,4};

1pub const ExternalResult = struct {2    frame: u16,3    origin: explore.Origin,4    outcome: explore.OperationOutcome,5};

1pub const Frame = struct {2    decision: explore.SearchDecision,3    expected: world.Moment,4};

1pub const Identity = struct {2    digest: [32]u8,34    pub fn hex(self: Identity) [64]u8 {5        return @import("std").fmt.bytesToHex(self.digest, .lower);6    }7};

1pub const Preparation = union(enum) {2    ready: world.Moment,3    incomplete: explore.SearchExecutionIncomplete,4};

1pub const Rejection = struct {2    frame: u16,3    reason: RejectionReason,4    incomplete: ?explore.SearchExecutionIncomplete = null,5};

1pub const RejectionReason = enum(u8) {2    preparation_incomplete = 1,3    start_mismatch = 2,4    step_incomplete = 3,5    moment_mismatch = 4,6    unexpected_failure = 5,7    expected_failure_missing = 6,8    failure_mismatch = 7,9};

1pub const Replay = union(enum) {2    reproduced: explore.PropertyEvaluation,3    rejected: Rejection,4};

1pub const Runner = struct {2    context: *anyopaque,3    prepare: *const fn (4        *anyopaque,5        profile.Profile,6        world.Moment,7        []const BuildIdentity,8        []const ExternalResult,9    ) Preparation,10    step: explore.SearchRunner,11};

1pub const Statistics = struct {2    attempts: u32,3    accepted: u16,4    rejected: u32,5};

1pub const Bound = union(enum) {2    steps: u16,3    virtual_time: u64,4};

1pub const BoundedLiveness = struct {2    property: SemanticId,3    trigger: Pattern,4    response: Pattern,5    bound: Bound,6};

1pub const Diagnostic = struct {2    id: SemanticId,3    code: u32,4};

1pub const EvaluationPattern = struct {2    id: SemanticId,3    verdict: ?Verdict = null,4};

1pub const EvaluationReason = enum(u8) {2    satisfied = 1,3    forbidden_event = 2,4    response_missing = 3,5    bound_exceeded = 4,6    trigger_not_seen = 5,7    trace_incomplete = 6,8    declaration_missing = 7,9    declaration_mismatch = 8,10};

1pub const Event = struct {2    sequence: u16,3    virtual_time_tick: u64,4    value: EventValue,5};

1pub const EventCapacity = struct {2    events: u16,3};

1pub const EventClass = enum(u8) {2    controlled_input = 1,3    schedule_choice = 2,4    topology_choice = 3,5    observation = 4,6    property_declaration = 5,7    property_evaluation = 6,8    injected_fault = 7,9    diagnostic = 8,10    external_admission = 9,11    operation = 10,12};

1pub const EventValue = union(enum) {2    controlled_input: GeneratedInput,3    schedule_choice: GeneratedSchedule,4    topology_choice: GeneratedTopology,5    observation: Observation,6    property_declaration: PropertyDeclaration,7    property_evaluation: PropertyEvaluation,8    injected_fault: GeneratedFault,9    diagnostic: Diagnostic,10    external_admission: ExternalAdmission,11    operation: Operation,12};

1pub const ExternalAdmission = struct {2    id: SemanticId,3    origin: Origin,4};

1pub const FaultAction = union(enum) {2    healthy,3    inject: fault.Kind,4    persist: fault.Kind,5    recover: fault.Kind,6};

1pub const FaultAlternative = struct {2    choice_origin: Origin,3    effect_origin: ?Origin,4    virtual_time_tick: u64,5    action: FaultAction,6};

1pub const FaultCapacity = struct {2    steps: u16,3    kinds: u8,4    alternatives: u8,5};

1pub const FaultPlan = struct {2    temporal: TemporalPlan,3    kinds: []const fault.Kind,4};

1pub const IncompleteReason = enum(u8) {2    step_capacity = 1,3    alternative_capacity = 2,4    node_capacity = 3,5    kind_capacity = 4,6    event_capacity = 5,7    virtual_time_bound = 6,8};

1pub const InputAlternative = struct {2    origin: Origin,3    virtual_time_tick: u64,4    value: InputValue,5};

1pub const InputCapacity = struct {2    steps: u16,3    alternatives: u8,4};

1pub const InputKind = enum(u8) {2    wait = 1,3    terminal = 2,4    entropy = 3,5    packet = 4,6    service_result = 5,7    effect_result = 6,8};

1pub const InputPhase = enum(u8) {2    quiet = 1,3    burst = 2,4};

1pub const InputValue = union(InputKind) {2    wait: u64,3    terminal: u64,4    entropy: u64,5    packet: u64,6    service_result: OperationOutcome,7    effect_result: OperationOutcome,8};

1pub const Observation = struct {2    id: SemanticId,3    value: u64,4};

1pub const Operation = struct {2    id: SemanticId,3    outcome: OperationOutcome,4};

1pub const OperationOutcome = enum(u8) {2    succeeded = 1,3    failed = 2,4    uncertain = 3,5};

1pub const OperationPattern = struct {2    id: SemanticId,3    outcome: ?OperationOutcome = null,4};

1pub const Origin = struct {2    source: profile.DeterminismSource,3    version: u16,4};

1pub const Pattern = union(enum) {2    event_class: EventClass,3    input: InputKind,4    schedule: ScheduleKind,5    topology: TopologyKind,6    observation: SemanticId,7    property_declaration: SemanticId,8    property_evaluation: EvaluationPattern,9    fault: fault.Kind,10    diagnostic: SemanticId,11    external_admission: profile.DeterminismSource,12    operation: OperationPattern,13};

1pub const PropertyDeclaration = struct {2    id: SemanticId,3    kind: PropertyKind,4    bound: ?Bound,5};

1pub const PropertyEvaluation = struct {2    id: SemanticId,3    verdict: Verdict,4    reason: EvaluationReason,5    witness: ?u16,6};

1pub const PropertyKind = enum(u8) {2    safety = 1,3    bounded_liveness = 2,4};

1pub const Safety = struct {2    property: SemanticId,3    forbidden: Pattern,4};

1pub const ScheduleAlternative = struct {2    origin: Origin,3    virtual_time_tick: u64,4    value: ScheduleValue,5};

1pub const ScheduleCapacity = struct {2    steps: u16,3    nodes: u8,4    alternatives: u8,5};

1pub const ScheduleKind = enum(u8) {2    turn = 1,3    idle = 2,4};

1pub const SchedulePlan = struct {2    temporal: TemporalPlan,3    nodes: u8,4};

1pub const ScheduleValue = union(ScheduleKind) {2    turn: u8,3    idle,4};

1pub const Seed = struct {2    dialect: SeedDialect = .sha256_v1,3    bytes: [32]u8,45    pub fn fromU64(value: u64) Seed {6        var bytes: [32]u8 = @splat(0);7        std.mem.writeInt(u64, bytes[0..8], value, .little);8        return .{ .bytes = bytes };9    }1011    pub fn digest(12        self: Seed,13        stream: Stream,14        sequence: u16,15        lane: u8,16    ) [Sha256.digest_length]u8 {17        var hasher = Sha256.init(.{});18        hasher.update("tiny.machine.explore.seed/v1");19        hasher.update(&.{@backingInt(self.dialect)});20        hasher.update(&self.bytes);21        hasher.update(&.{@backingInt(stream)});22        var encoded: [3]u8 = undefined;23        std.mem.writeInt(u16, encoded[0..2], sequence, .little);24        encoded[2] = lane;25        hasher.update(&encoded);26        var result: [Sha256.digest_length]u8 = undefined;27        hasher.final(&result);28        return result;29    }3031    pub fn word(32        self: Seed,33        stream: Stream,34        sequence: u16,35        lane: u8,36    ) u64 {37        const bytes = self.digest(stream, sequence, lane);38        return std.mem.readInt(u64, bytes[0..8], .little);39    }4041    pub fn suggest(42        self: Seed,43        stream: Stream,44        sequence: u16,45        alternative_count: u8,46    ) u8 {47        std.debug.assert(alternative_count > 0);48        const count: u64 = alternative_count;49        const selected = self.word(stream, sequence, 0) % count;50        std.debug.assert(selected < alternative_count);51        return @intCast(selected);52    }53};

1pub const SeedDialect = enum(u8) {2    sha256_v1 = 1,3};

1pub const SiteId = struct {2    stream: Stream,3    sequence: u16,4    virtual_time_tick: u64,5};

1pub const Stream = enum(u8) {2    input = 1,3    schedule = 2,4    topology = 3,5    fault = 4,6};

1pub const TemporalPlan = struct {2    steps: u16,3    start_tick: u64,4    end_tick: u64,5};

1pub const TopologyAlternative = struct {2    origin: Origin,3    virtual_time_tick: u64,4    value: TopologyValue,5};

1pub const TopologyCapacity = struct {2    steps: u16,3    nodes: u8,4    alternatives: u8,5};

1pub const TopologyKind = enum(u8) {2    node = 1,3    complete = 2,4};

1pub const TopologyNode = struct {2    id: fabric.NodeId,3    included: bool,4};

1pub const TopologyPlan = struct {2    temporal: TemporalPlan,3    nodes: u8,4};

1pub const TopologyValue = union(TopologyKind) {2    node: TopologyNode,3    complete,4};

1pub const TraceCompletion = enum(u8) {2    exhausted = 1,3    incomplete = 2,4};

1pub const TraceState = enum(u8) {2    open = 1,3    exhausted = 2,4    incomplete = 3,5};

1pub const Verdict = enum(u8) {2    holds = 1,3    violated = 2,4    unreached = 3,5    incomplete = 4,6};

1pub const Branch = struct {2    root: world.Moment,3    parent: ?BranchId = null,4    decision: ?Decision = null,5    depth: u16 = 0,6    expanded: bool = false,7    settlement: Settlement = .origin,8};

1pub const Budget = struct {2    executions: u32,3    depth: u16,4};

1pub const Candidate = struct {2    parent: BranchId,3    decision: Decision,4};

1pub const Capacity = struct {2    frontier: u16,3    retained: u16,4};

1pub const Choice = union(explore.Stream) {2    input: explore.GeneratedInput,3    schedule: explore.GeneratedSchedule,4    topology: explore.GeneratedTopology,5    fault: explore.GeneratedFault,6};

1pub const Decision = struct {2    site: explore.SiteId,3    alternative: u8,4    alternative_count: u8,5    choice: Choice,67    pub fn valid(self: Decision) bool {8        return self.alternative_count > 0 and9            self.alternative < self.alternative_count and10            self.site.stream == std.meta.activeTag(self.choice);11    }12};

1pub const Execution = union(enum) {2    completed: world.Moment,3    failed: FailedExecution,4    incomplete: ExecutionIncomplete,5};

1pub const ExecutionIncomplete = enum(u8) {2    replay_rejected = 1,3    replay_invalidated = 2,4    trace_incomplete = 3,5    invalid_moment = 4,6    invalid_failure = 5,7};

1pub const ExhaustedReason = enum(u8) {2    frontier_empty = 1,3    execution_budget = 2,4    depth_budget = 3,5};

1pub const Expansion = union(enum) {2    expanded: Expanded,3    exhausted: Exhausted,4    pruned: Pruned,5};

1pub const IncompleteReason = union(enum) {2    interrupted,3    retained_capacity,4    execution: ExecutionIncomplete,5    generation: explore.IncompleteReason,6};

1pub const Outcome = union(enum) {2    completed: Completed,3    exhausted: Exhausted,4    pruned: Pruned,5    failed: Failed,6    incomplete: Incomplete,7};

1pub const Progress = struct {2    executions: u32,3    retained: u16,4    frontier: u16,5    pruned: u64,6};

1pub const PrunedReason = enum(u8) {2    strategy = 1,3    frontier_capacity = 2,4};

1pub const Runner = struct {2    context: *anyopaque,3    execute: *const fn (*anyopaque, world.Moment, Decision) Execution,45    pub fn run(6        self: Runner,7        parent: world.Moment,8        decision: Decision,9    ) Execution {10        return self.execute(self.context, parent, decision);11    }12};

1pub const Settlement = union(enum) {2    origin,3    completed,4    failed: explore.PropertyEvaluation,5};

1pub fn Capsule(comptime capacity_value: types.Capacity) type {2    requireCapacity(capacity_value);3    return struct {4        selected_profile: profile.Profile,5        start: world.Moment,6        expected_failure: explore.PropertyEvaluation,7        builds_storage: [capacity.builds]types.BuildIdentity,8        frames_storage: [capacity.frames]types.Frame,9        external_storage: [capacity.frames]types.ExternalResult,10        build_count: u8,11        frame_count: u16,12        external_count: u16,1314        const Self = @This();1516        pub const capacity: types.Capacity = capacity_value;17        pub const Error = types.Error;18        pub const Wire = canon.Wire(capacity);19        pub const Capture = union(enum) {20            published: Self,21            rejected: types.Rejection,22        };2324        pub fn capture(25            search: anytype,26            failure: anytype,27            selected_profile: profile.Profile,28            build_identities: []const types.BuildIdentity,29            runner: types.Runner,30        ) Error!Capture {31            if (build_identities.len > capacity.builds) {32                return error.BuildCapacityExceeded;33            }34            const failed = try search.branch(failure.branch);35            try validateFailureBranch(failed, failure);36            if (failed.depth > capacity.frames) {37                return error.FrameCapacityExceeded;38            }39            var result: Self = undefined;40            result.selected_profile = selected_profile;41            result.start = (try search.branch(0)).root;42            result.expected_failure = failure.evaluation;43            result.build_count = @intCast(build_identities.len);44            result.frame_count = failed.depth;45            @memcpy(46                result.builds_storage[0..build_identities.len],47                build_identities,48            );49            try result.copyHistory(search, failure.branch);50            return result.publishOwned(runner);51        }5253        pub fn publish(54            selected_profile: profile.Profile,55            start: world.Moment,56            expected_failure: explore.PropertyEvaluation,57            build_identities: []const types.BuildIdentity,58            replay_frames: []const types.Frame,59            runner: types.Runner,60        ) Error!Capture {61            if (build_identities.len > capacity.builds) {62                return error.BuildCapacityExceeded;63            }64            if (replay_frames.len > capacity.frames) {65                return error.FrameCapacityExceeded;66            }67            var result: Self = undefined;68            result.selected_profile = selected_profile;69            result.start = start;70            result.expected_failure = expected_failure;71            result.build_count = @intCast(build_identities.len);72            result.frame_count = @intCast(replay_frames.len);73            @memcpy(74                result.builds_storage[0..build_identities.len],75                build_identities,76            );77            @memcpy(78                result.frames_storage[0..replay_frames.len],79                replay_frames,80            );81            return result.publishOwned(runner);82        }8384        fn publishOwned(self: *Self, runner: types.Runner) Error!Capture {85            self.rebuildExternalLedger();86            try self.validate();87            return switch (try self.replay(runner)) {88                .reproduced => .{ .published = self.* },89                .rejected => |rejection| .{ .rejected = rejection },90            };91        }9293        pub fn builds(self: *const Self) []const types.BuildIdentity {94            std.debug.assert(self.build_count <= capacity.builds);95            return self.builds_storage[0..self.build_count];96        }9798        pub fn frames(self: *const Self) []const types.Frame {99            std.debug.assert(self.frame_count <= capacity.frames);100            return self.frames_storage[0..self.frame_count];101        }102103        pub fn externalResults(self: *const Self) []const types.ExternalResult {104            std.debug.assert(self.external_count <= capacity.frames);105            return self.external_storage[0..self.external_count];106        }107108        pub fn replay(self: *const Self, runner: types.Runner) Error!types.Replay {109            try self.validate();110            const prepared = runner.prepare(111                runner.context,112                self.selected_profile,113                self.start,114                self.builds(),115                self.externalResults(),116            );117            var current = switch (prepared) {118                .ready => |ready| ready,119                .incomplete => |reason| return rejected(120                    0,121                    .preparation_incomplete,122                    reason,123                ),124            };125            if (!std.meta.eql(current, self.start)) {126                return rejected(0, .start_mismatch, null);127            }128            for (self.frames(), 0..) |frame, index| {129                const result = runner.step.run(current, frame.decision);130                if (index + 1 == self.frame_count) {131                    return self.finishReplay(frame, result, index);132                }133                current = switch (result) {134                    .completed => |next| next,135                    .failed => return rejected(index, .unexpected_failure, null),136                    .incomplete => |reason| return rejected(137                        index,138                        .step_incomplete,139                        reason,140                    ),141                };142                if (!std.meta.eql(current, frame.expected)) {143                    return rejected(index, .moment_mismatch, null);144                }145            }146            unreachable;147        }148149        pub fn encode(self: *const Self, output: *Wire) Error!void {150            try canon.encode(capacity, self, output);151        }152153        pub fn decode(input: *const Wire) Error!Self {154            var result: Self = undefined;155            try canon.decode(capacity, input, &result);156            return result;157        }158159        pub fn identity(self: *const Self) Error!types.Identity {160            var wire: Wire = undefined;161            try self.encode(&wire);162            return canon.identity(capacity, &wire);163        }164165        pub fn validate(self: *const Self) Error!void {166            try profile.validate(self.selected_profile);167            try world.verifyMoment(self.start, self.start.origin, self.start.fabric);168            const contract = try profile.contractFingerprint(self.selected_profile);169            if (!std.meta.eql(contract, self.start.origin.machine_contract)) {170                return error.InitialContractMismatch;171            }172            if (self.frame_count == 0 or self.frame_count > capacity.frames) {173                return error.FrameInvalid;174            }175            if (self.build_count != self.start.origin.node_count or176                self.build_count > capacity.builds)177            {178                return error.BuildCountMismatch;179            }180            if (self.expected_failure.verdict != .violated) {181                return error.FailureExpected;182            }183            try self.validateBuilds();184            try self.validateFrames();185            try self.validateExternalLedger();186        }187188        fn copyHistory(self: *Self, search: anytype, branch_id: anytype) Error!void {189            var cursor = branch_id;190            var remaining = self.frame_count;191            while (remaining > 0) {192                const branch = try search.branch(cursor);193                remaining -= 1;194                self.frames_storage[remaining] = .{195                    .decision = branch.decision.?,196                    .expected = branch.root,197                };198                cursor = branch.parent.?;199            }200            std.debug.assert(cursor == 0);201        }202203        fn finishReplay(204            self: *const Self,205            frame: types.Frame,206            result: explore.SearchExecution,207            index: usize,208        ) types.Replay {209            return switch (result) {210                .completed => rejected(index, .expected_failure_missing, null),211                .incomplete => |reason| rejected(index, .step_incomplete, reason),212                .failed => |failure| if (!std.meta.eql(failure.root, frame.expected))213                    rejected(index, .moment_mismatch, null)214                else if (!std.meta.eql(failure.evaluation, self.expected_failure))215                    rejected(index, .failure_mismatch, null)216                else217                    .{ .reproduced = failure.evaluation },218            };219        }220221        fn validateBuilds(self: *const Self) Error!void {222            for (self.builds(), 0..) |build, index| {223                if (allZero(&build.node.bytes) or allZero(&build.execution.digest)) {224                    return error.BuildIdentityInvalid;225                }226                if (index > 0 and !std.mem.lessThan(227                    u8,228                    &self.builds_storage[index - 1].node.bytes,229                    &build.node.bytes,230                )) return error.BuildOrderInvalid;231            }232        }233234        fn validateFrames(self: *const Self) Error!void {235            var previous = self.start;236            for (self.frames()) |frame| {237                if (!frame.decision.valid()) return error.FrameInvalid;238                try validateDecisionOrigins(frame.decision);239                try world.verifyMoment(240                    frame.expected,241                    self.start.origin,242                    frame.expected.fabric,243                );244                if (!momentFollows(previous, frame.expected)) {245                    return error.FrameInvalid;246                }247                previous = frame.expected;248            }249        }250251        fn rebuildExternalLedger(self: *Self) void {252            self.external_count = 0;253            for (self.frames(), 0..) |frame, index| {254                const value = externalResult(frame.decision, @intCast(index)) orelse255                    continue;256                std.debug.assert(self.external_count < capacity.frames);257                self.external_storage[self.external_count] = value;258                self.external_count += 1;259            }260        }261262        fn validateExternalLedger(self: *const Self) Error!void {263            if (self.external_count > self.frame_count) {264                return error.ExternalLedgerInvalid;265            }266            var expected: [capacity.frames]types.ExternalResult = undefined;267            var count: u16 = 0;268            for (self.frames(), 0..) |frame, index| {269                const value = externalResult(frame.decision, @intCast(index)) orelse270                    continue;271                expected[count] = value;272                count += 1;273            }274            if (count != self.external_count) return error.ExternalLedgerInvalid;275            for (expected[0..count], self.externalResults()) |left, right| {276                if (!std.meta.eql(left, right)) {277                    return error.ExternalLedgerInvalid;278                }279            }280        }281    };282}

1pub fn Reducer(comptime capacity_value: types.Capacity) type {2    const CapsuleType = Capsule(capacity_value);3    const attempt_limit = reductionAttemptLimit(capacity_value.frames);4    return struct {5        accepted: CapsuleType,6        scratch: CapsuleType,7        statistics: types.Statistics = .{ .attempts = 0, .accepted = 0, .rejected = 0 },89        const Self = @This();1011        pub const capacity: types.Capacity = capacity_value;12        pub const Init = union(enum) {13            ready: Self,14            rejected: types.Rejection,15        };16        pub const Attempt = union(enum) {17            accepted,18            rejected: types.Rejection,19        };20        pub const Reduced = struct {21            capsule: CapsuleType,22            statistics: types.Statistics,23        };2425        pub fn init(value: CapsuleType, runner: types.Runner) types.Error!Init {26            return switch (try value.replay(runner)) {27                .reproduced => .{ .ready = .{ .accepted = value, .scratch = value } },28                .rejected => |rejection| .{ .rejected = rejection },29            };30        }3132        pub fn tryRemove(33            self: *Self,34            frame: u16,35            runner: types.Runner,36        ) types.Error!Attempt {37            if (frame >= self.accepted.frame_count) return error.FrameUnknown;38            if (self.accepted.frame_count == 1) return error.FailureExpected;39            self.scratch = self.accepted;40            const remaining = self.scratch.frame_count - frame - 1;41            std.mem.copyForwards(42                types.Frame,43                self.scratch.frames_storage[frame .. frame + remaining],44                self.scratch.frames_storage[frame + 1 .. self.scratch.frame_count],45            );46            self.scratch.frame_count -= 1;47            self.scratch.rebuildExternalLedger();48            self.statistics.attempts += 1;49            return switch (try self.scratch.replay(runner)) {50                .reproduced => {51                    self.accepted = self.scratch;52                    self.statistics.accepted += 1;53                    return .accepted;54                },55                .rejected => |rejection| {56                    self.statistics.rejected += 1;57                    return .{ .rejected = rejection };58                },59            };60        }6162        pub fn reduce(self: *Self, runner: types.Runner) types.Error!Reduced {63            var frame: u16 = 0;64            for (0..attempt_limit) |_| {65                if (self.accepted.frame_count == 1 or66                    frame == self.accepted.frame_count)67                {68                    return .{69                        .capsule = self.accepted,70                        .statistics = self.statistics,71                    };72                }73                switch (try self.tryRemove(frame, runner)) {74                    .accepted => frame = 0,75                    .rejected => frame += 1,76                }77            }78            unreachable;79        }80    };81}

1pub const Error = explore.SearchError || profile.Error || world.MomentError || error{2    BuildCapacityExceeded,3    BuildCountMismatch,4    BuildIdentityInvalid,5    BuildOrderInvalid,6    CapsuleDigestMismatch,7    CapsuleNonCanonical,8    CapsuleWireBadMagic,9    CapsuleWireCapacityMismatch,10    CapsuleWireFieldInvalid,11    CapsuleWireFlagsUnsupported,12    CapsuleWireSizeMismatch,13    CapsuleWireVersionUnsupported,14    ExternalLedgerInvalid,15    FailureBranchMismatch,16    FailureExpected,17    FrameCapacityExceeded,18    FrameInvalid,19    FrameUnknown,20    InitialContractMismatch,21};

1pub fn Generator(comptime capacity_value: explore.FaultCapacity) type {2    return struct {3        seed: explore.Seed,4        temporal: explore.TemporalPlan,5        kinds: [capacity.kinds]fault.Kind,6        kind_count: u8,7        sequence: u16 = 0,8        virtual_time_tick: u64,9        active: ?fault.Kind = null,1011        const Self = @This();1213        pub const capacity: explore.FaultCapacity = capacity_value;14        pub const Error: type = explore.GeneratorError;15        pub const InitResult: type = explore.Generation(Self);16        pub const Site: type = explore.ChoiceSite(17            explore.FaultAlternative,18            capacity.alternatives,19        );20        pub const NextResult: type = explore.Generation(Site);2122        pub fn init(23            selected: profile.Profile,24            seed: explore.Seed,25            plan: explore.FaultPlan,26        ) Error!InitResult {27            try profile.validate(selected);28            if (plan.temporal.end_tick < plan.temporal.start_tick or29                plan.kinds.len == 0)30            {31                return error.InvalidPlan;32            }33            if (plan.temporal.steps == 0 or34                plan.temporal.start_tick == plan.temporal.end_tick)35            {36                return .exhausted;37            }38            if (plan.temporal.steps > capacity.steps) {39                return .{ .incomplete = .step_capacity };40            }41            if (plan.kinds.len > capacity.kinds) {42                return .{ .incomplete = .kind_capacity };43            }44            if (plan.kinds.len + 1 > capacity.alternatives) {45                return .{ .incomplete = .alternative_capacity };46            }47            try validateKinds(plan.kinds);48            var kinds: [capacity.kinds]fault.Kind = undefined;49            @memcpy(kinds[0..plan.kinds.len], plan.kinds);50            return .{ .item = .{51                .seed = seed,52                .temporal = plan.temporal,53                .kinds = kinds,54                .kind_count = @intCast(plan.kinds.len),55                .virtual_time_tick = plan.temporal.start_tick,56            } };57        }5859        pub fn next(self: *const Self) NextResult {60            self.assertValid();61            if (self.sequence == self.temporal.steps or62                self.virtual_time_tick == self.temporal.end_tick)63            {64                return .exhausted;65            }66            var site = Site{67                .id = self.siteId(),68                .alternatives = undefined,69                .count = 0,70                .suggested = 0,71            };72            if (self.active) |kind| {73                self.activeAlternatives(&site, kind);74            } else {75                self.healthyAlternatives(&site);76            }77            std.debug.assert(site.count > 0);78            site.suggested = self.seed.suggest(.fault, self.sequence, site.count);79            return .{ .item = site };80        }8182        pub fn choose(83            self: *Self,84            site: Site,85            index: u8,86        ) Error!explore.GeneratedFault {87            const current = switch (self.next()) {88                .item => |value| value,89                .exhausted, .incomplete => return error.StaleChoiceSite,90            };91            if (!sameSite(current, site)) return error.StaleChoiceSite;92            if (index >= site.count) return error.ChoiceOutOfRange;93            const selected = site.alternatives[index];94            switch (selected.action) {95                .healthy => self.active = null,96                .inject => |kind| self.active = kind,97                .persist => |kind| std.debug.assert(self.active.? == kind),98                .recover => |kind| {99                    std.debug.assert(self.active.? == kind);100                    self.active = null;101                },102            }103            self.virtual_time_tick = selected.virtual_time_tick;104            self.sequence += 1;105            self.assertValid();106            return selected;107        }108109        pub fn activeFault(self: *const Self) ?fault.Kind {110            self.assertValid();111            return self.active;112        }113114        fn healthyAlternatives(self: *const Self, site: *Site) void {115            self.addAt(site, self.longDelay(), null, .{ .healthy = {} });116            for (self.kinds[0..self.kind_count]) |kind| {117                self.addAt(site, 1, explore.faultOrigin(kind), .{ .inject = kind });118            }119        }120121        fn activeAlternatives(self: *const Self, site: *Site, kind: fault.Kind) void {122            const persistent_delay = 1 + self.seed.word(.fault, self.sequence, 1) % 4;123            self.addAt(124                site,125                persistent_delay,126                explore.faultOrigin(kind),127                .{ .persist = kind },128            );129            self.addAt(site, 1, explore.faultOrigin(kind), .{ .recover = kind });130        }131132        fn addAt(133            self: *const Self,134            site: *Site,135            delta: u64,136            effect_origin: ?explore.Origin,137            action: explore.FaultAction,138        ) void {139            const tick = self.futureTick(delta) orelse return;140            std.debug.assert(site.count < site.alternatives.len);141            site.alternatives[site.count] = .{142                .choice_origin = explore.origin(.fault_choice),143                .effect_origin = effect_origin,144                .virtual_time_tick = tick,145                .action = action,146            };147            site.count += 1;148        }149150        fn futureTick(self: *const Self, delta: u64) ?u64 {151            std.debug.assert(self.virtual_time_tick <= self.temporal.end_tick);152            const remaining = self.temporal.end_tick - self.virtual_time_tick;153            if (delta == 0 or delta > remaining) return null;154            return self.virtual_time_tick + delta;155        }156157        fn longDelay(self: *const Self) u64 {158            return 4 + self.seed.word(.fault, self.sequence, 2) % 13;159        }160161        fn siteId(self: *const Self) explore.SiteId {162            return .{163                .stream = .fault,164                .sequence = self.sequence,165                .virtual_time_tick = self.virtual_time_tick,166            };167        }168169        fn assertValid(self: *const Self) void {170            std.debug.assert(self.kind_count > 0);171            std.debug.assert(self.kind_count <= capacity.kinds);172            std.debug.assert(self.sequence <= self.temporal.steps);173            std.debug.assert(self.sequence <= capacity.steps);174            std.debug.assert(self.virtual_time_tick >= self.temporal.start_tick);175            std.debug.assert(self.virtual_time_tick <= self.temporal.end_tick);176        }177178        fn sameSite(expected: Site, actual: Site) bool {179            if (!std.meta.eql(expected.id, actual.id)) return false;180            if (expected.count != actual.count) return false;181            if (expected.suggested != actual.suggested) return false;182            for (expected.values(), actual.values()) |left, right| {183                if (!std.meta.eql(left, right)) return false;184            }185            return true;186        }187    };188}

1pub fn Generator(comptime capacity_value: explore.InputCapacity) type {2    return struct {3        seed: explore.Seed,4        plan: explore.TemporalPlan,5        sequence: u16 = 0,6        virtual_time_tick: u64,7        phase: explore.InputPhase = .quiet,8        burst_remaining: u8 = 0,910        const Self = @This();1112        pub const capacity: explore.InputCapacity = capacity_value;13        pub const Error: type = explore.GeneratorError;14        pub const InitResult: type = explore.Generation(Self);15        pub const Site: type = explore.ChoiceSite(16            explore.InputAlternative,17            capacity.alternatives,18        );19        pub const NextResult: type = explore.Generation(Site);2021        pub fn init(22            selected: profile.Profile,23            seed: explore.Seed,24            plan: explore.TemporalPlan,25        ) Error!InitResult {26            try profile.validate(selected);27            if (plan.end_tick < plan.start_tick) return error.InvalidPlan;28            if (plan.steps == 0 or plan.start_tick == plan.end_tick) {29                return .exhausted;30            }31            if (plan.steps > capacity.steps) {32                return .{ .incomplete = .step_capacity };33            }34            if (capacity.alternatives < alternative_limit) {35                return .{ .incomplete = .alternative_capacity };36            }37            return .{ .item = .{38                .seed = seed,39                .plan = plan,40                .virtual_time_tick = plan.start_tick,41            } };42        }4344        pub fn next(self: *const Self) NextResult {45            self.assertValid();46            if (self.sequence == self.plan.steps or47                self.virtual_time_tick == self.plan.end_tick)48            {49                return .exhausted;50            }51            var site = Site{52                .id = self.siteId(),53                .alternatives = undefined,54                .count = 0,55                .suggested = 0,56            };57            switch (self.phase) {58                .quiet => self.quietAlternatives(&site),59                .burst => self.burstAlternatives(&site),60            }61            std.debug.assert(site.count > 0);62            site.suggested = self.seed.suggest(.input, self.sequence, site.count);63            return .{ .item = site };64        }6566        pub fn choose(67            self: *Self,68            site: Site,69            index: u8,70        ) Error!explore.GeneratedInput {71            const current = switch (self.next()) {72                .item => |value| value,73                .exhausted, .incomplete => return error.StaleChoiceSite,74            };75            if (!sameSite(current, site)) return error.StaleChoiceSite;76            if (index >= site.count) return error.ChoiceOutOfRange;77            const selected = site.alternatives[index];78            self.advance(selected);79            self.assertValid();80            return selected;81        }8283        pub fn workload(self: *const Self) explore.InputPhase {84            self.assertValid();85            return self.phase;86        }8788        fn quietAlternatives(self: *const Self, site: *Site) void {89            self.addAt(site, self.longDelay(), .{ .wait = self.longDelay() });90            self.addAt(site, 1, .{ .terminal = self.seed.word(.input, self.sequence, 1) });91            self.addAt(site, 1, .{ .entropy = self.seed.word(.input, self.sequence, 2) });92            self.addAt(site, 1, .{ .service_result = .failed });93            self.addAt(site, 1, .{ .effect_result = .uncertain });94        }9596        fn burstAlternatives(self: *const Self, site: *Site) void {97            self.addAt(site, 1, .{ .terminal = self.seed.word(.input, self.sequence, 3) });98            self.addAt(site, 1, .{ .packet = self.seed.word(.input, self.sequence, 4) });99            self.addAt(site, 1, .{ .entropy = self.seed.word(.input, self.sequence, 5) });100            self.addAt(site, 1, .{ .service_result = .succeeded });101            self.addAt(site, self.longDelay(), .{ .wait = self.longDelay() });102        }103104        fn addAt(self: *const Self, site: *Site, delta: u64, value: explore.InputValue) void {105            const tick = self.futureTick(delta) orelse return;106            std.debug.assert(site.count < site.alternatives.len);107            site.alternatives[site.count] = .{108                .origin = explore.origin(inputSource(value)),109                .virtual_time_tick = tick,110                .value = value,111            };112            site.count += 1;113        }114115        fn advance(self: *Self, selected: explore.GeneratedInput) void {116            std.debug.assert(selected.virtual_time_tick > self.virtual_time_tick);117            std.debug.assert(selected.virtual_time_tick <= self.plan.end_tick);118            self.virtual_time_tick = selected.virtual_time_tick;119            self.sequence += 1;120            switch (selected.value) {121                .wait => {122                    self.phase = .quiet;123                    self.burst_remaining = 0;124                },125                .terminal, .entropy, .packet, .service_result, .effect_result => {126                    self.advanceBurst();127                },128            }129        }130131        fn advanceBurst(self: *Self) void {132            switch (self.phase) {133                .quiet => {134                    const width = self.seed.word(.input, self.sequence, 6) % 3;135                    self.phase = .burst;136                    self.burst_remaining = 2 + @as(u8, @intCast(width));137                },138                .burst => {139                    std.debug.assert(self.burst_remaining > 0);140                    self.burst_remaining -= 1;141                    if (self.burst_remaining == 0) self.phase = .quiet;142                },143            }144        }145146        fn futureTick(self: *const Self, delta: u64) ?u64 {147            std.debug.assert(self.virtual_time_tick <= self.plan.end_tick);148            const remaining = self.plan.end_tick - self.virtual_time_tick;149            if (delta == 0 or delta > remaining) return null;150            return self.virtual_time_tick + delta;151        }152153        fn longDelay(self: *const Self) u64 {154            return 4 + self.seed.word(.input, self.sequence, 7) % 13;155        }156157        fn siteId(self: *const Self) explore.SiteId {158            return .{159                .stream = .input,160                .sequence = self.sequence,161                .virtual_time_tick = self.virtual_time_tick,162            };163        }164165        fn assertValid(self: *const Self) void {166            std.debug.assert(self.sequence <= self.plan.steps);167            std.debug.assert(self.sequence <= capacity.steps);168            std.debug.assert(self.virtual_time_tick >= self.plan.start_tick);169            std.debug.assert(self.virtual_time_tick <= self.plan.end_tick);170            if (self.phase == .quiet) std.debug.assert(self.burst_remaining == 0);171        }172173        fn sameSite(expected: Site, actual: Site) bool {174            if (!std.meta.eql(expected.id, actual.id)) return false;175            if (expected.count != actual.count) return false;176            if (expected.suggested != actual.suggested) return false;177            for (expected.values(), actual.values()) |left, right| {178                if (!std.meta.eql(left, right)) return false;179            }180            return true;181        }182    };183}

1pub fn ChoiceSite(2    comptime Alternative: type,3    comptime alternative_capacity: u8,4) type {5    return struct {6        id: SiteId,7        alternatives: [alternative_capacity]Alternative,8        count: u8,9        suggested: u8,1011        pub fn values(self: *const @This()) []const Alternative {12            std.debug.assert(self.count <= self.alternatives.len);13            return self.alternatives[0..self.count];14        }15    };16}

1pub fn Generation(comptime T: type) type {2    return union(enum) {3        item: T,4        exhausted,5        incomplete: IncompleteReason,6    };7}

1pub const GeneratorError: type = profile.Error || ChoiceError;

1pub const SemanticId = u64;

1pub fn faultOrigin(kind: fault.Kind) Origin {2    return origin(switch (kind) {3        .machine_crash => .machine_crash,4        .process_crash => .process_crash,5        .io_error => .effect_result,6        .packet_loss, .packet_delay, .packet_reorder, .partition => .packet_fault,7        .clock_jump => .virtual_time,8        .entropy_choice => .entropy_input,9        .capacity_exhaustion => .capacity_fault,10        .host_service_failure => .host_service_result,11    });12}

1pub fn origin(source: profile.DeterminismSource) Origin {2    const declared = profile.determinism.entry(source);3    std.debug.assert(declared.source == source);4    std.debug.assert(declared.version > 0);5    return .{ .source = source, .version = declared.version };6}

1pub fn Generator(comptime capacity_value: explore.ScheduleCapacity) type {2    return struct {3        seed: explore.Seed,4        plan: explore.SchedulePlan,5        sequence: u16 = 0,6        virtual_time_tick: u64,7        last_node: ?u8 = null,89        const Self = @This();1011        pub const capacity: explore.ScheduleCapacity = capacity_value;12        pub const Error: type = explore.GeneratorError;13        pub const InitResult: type = explore.Generation(Self);14        pub const Site: type = explore.ChoiceSite(15            explore.ScheduleAlternative,16            capacity.alternatives,17        );18        pub const NextResult: type = explore.Generation(Site);1920        pub fn init(21            selected: profile.Profile,22            seed: explore.Seed,23            plan: explore.SchedulePlan,24        ) Error!InitResult {25            try profile.validate(selected);26            if (plan.nodes == 0 or plan.nodes > fabric.node_limit) {27                return error.InvalidPlan;28            }29            if (plan.temporal.end_tick < plan.temporal.start_tick) {30                return error.InvalidPlan;31            }32            if (plan.temporal.steps == 0 or33                plan.temporal.start_tick == plan.temporal.end_tick)34            {35                return .exhausted;36            }37            if (plan.temporal.steps > capacity.steps) {38                return .{ .incomplete = .step_capacity };39            }40            if (plan.nodes > capacity.nodes) {41                return .{ .incomplete = .node_capacity };42            }43            if (capacity.alternatives < plan.nodes + 1) {44                return .{ .incomplete = .alternative_capacity };45            }46            return .{ .item = .{47                .seed = seed,48                .plan = plan,49                .virtual_time_tick = plan.temporal.start_tick,50            } };51        }5253        pub fn next(self: *const Self) NextResult {54            self.assertValid();55            if (self.sequence == self.plan.temporal.steps or56                self.virtual_time_tick == self.plan.temporal.end_tick)57            {58                return .exhausted;59            }60            var site = Site{61                .id = self.siteId(),62                .alternatives = undefined,63                .count = 0,64                .suggested = 0,65            };66            self.addTurns(&site);67            self.addIdle(&site);68            std.debug.assert(site.count == self.plan.nodes + 1);69            site.suggested = self.seed.suggest(.schedule, self.sequence, site.count);70            return .{ .item = site };71        }7273        pub fn choose(74            self: *Self,75            site: Site,76            index: u8,77        ) Error!explore.GeneratedSchedule {78            const current = switch (self.next()) {79                .item => |value| value,80                .exhausted, .incomplete => return error.StaleChoiceSite,81            };82            if (!sameSite(current, site)) return error.StaleChoiceSite;83            if (index >= site.count) return error.ChoiceOutOfRange;84            const selected = site.alternatives[index];85            switch (selected.value) {86                .turn => |node| self.last_node = node,87                .idle => {},88            }89            self.virtual_time_tick = selected.virtual_time_tick;90            self.sequence += 1;91            self.assertValid();92            return selected;93        }9495        fn addTurns(self: *const Self, site: *Site) void {96            const node_count: usize = self.plan.nodes;97            const first: usize = if (self.last_node) |node|98                (@as(usize, node) + 1) % node_count99            else100                0;101            for (0..node_count) |offset| {102                const node: u8 = @intCast((first + offset) % node_count);103                self.add(site, .turn_selection, .{ .turn = node });104            }105        }106107        fn addIdle(self: *const Self, site: *Site) void {108            self.add(site, .guest_schedule, .{ .idle = {} });109        }110111        fn add(112            self: *const Self,113            site: *Site,114            source: profile.DeterminismSource,115            value: explore.ScheduleValue,116        ) void {117            std.debug.assert(site.count < site.alternatives.len);118            site.alternatives[site.count] = .{119                .origin = explore.origin(source),120                .virtual_time_tick = self.virtual_time_tick + 1,121                .value = value,122            };123            site.count += 1;124        }125126        fn siteId(self: *const Self) explore.SiteId {127            return .{128                .stream = .schedule,129                .sequence = self.sequence,130                .virtual_time_tick = self.virtual_time_tick,131            };132        }133134        fn assertValid(self: *const Self) void {135            std.debug.assert(self.sequence <= self.plan.temporal.steps);136            std.debug.assert(self.sequence <= capacity.steps);137            std.debug.assert(self.virtual_time_tick >= self.plan.temporal.start_tick);138            std.debug.assert(self.virtual_time_tick <= self.plan.temporal.end_tick);139            if (self.last_node) |node| std.debug.assert(node < self.plan.nodes);140        }141142        fn sameSite(expected: Site, actual: Site) bool {143            if (!std.meta.eql(expected.id, actual.id)) return false;144            if (expected.count != actual.count) return false;145            if (expected.suggested != actual.suggested) return false;146            for (expected.values(), actual.values()) |left, right| {147                if (!std.meta.eql(left, right)) return false;148            }149            return true;150        }151    };152}

1/// Returns a search type that keeps two arrays for each pair of capacities, so2/// the whole search fits storage fixed at compile time, and a failing run can3/// be walked back to the root through its parents. The first array holds the4/// queue of choices waiting to run (*frontier*), up to the frontier capacity,5/// and the second holds every settled run the search keeps, up to the retained6/// capacity. A frontier or retained capacity of zero stops the build with a7/// compile error. `init` verifies the root position in a world's history8/// (*moment*) and stores it as branch 0. Each settled run keeps its complete9/// moment, its parent, and the alternative taken at a step (*decision*), so10/// `history` walks a run back to the root and returns its decisions in order.11/// `findExact` matches a settled run only when every field of its moment is12/// equal, so two runs whose digests agree stay two runs. The search stores both13/// arrays inside the value and holds no pointers, so `checkpoint` returns a14/// plain copy of it. `restoreCheckpoint` validates a saved copy and returns15/// `CheckpointInvalid` for a corrupt one.16pub fn Search(comptime capacity_value: types.Capacity) type {17    if (capacity_value.frontier == 0) {18        @compileError("search frontier capacity must be positive");19    }20    if (capacity_value.retained == 0) {21        @compileError("search retained capacity must be positive");22    }23    return struct {24        branches_storage: [capacity.retained]types.Branch = undefined,25        frontier_storage: [capacity.frontier]types.Candidate = undefined,26        branch_count: u16 = 0,27        frontier_count: u16 = 0,28        budget: types.Budget,29        execution_count: u32 = 0,30        pruned_count: u64 = 0,3132        const Self = @This();3334        pub const capacity: types.Capacity = capacity_value;35        pub const Checkpoint = Self;36        pub const Error = types.Error;3738        pub fn init(root: world.Moment, budget: types.Budget) Error!Self {39            try world.verifyMoment(root, root.origin, root.fabric);40            var self = Self{ .budget = budget };41            self.branches_storage[0] = .{ .root = root };42            self.branch_count = 1;43            self.assertValid();44            return self;45        }4647        pub fn checkpoint(self: *const Self) Checkpoint {48            self.validateCheckpoint() catch unreachable;49            return self.*;50        }5152        pub fn restoreCheckpoint(value: Checkpoint) Error!Self {53            try value.validateCheckpoint();54            return value;55        }5657        pub fn branches(self: *const Self) []const types.Branch {58            self.assertValid();59            return self.branches_storage[0..self.branch_count];60        }6162        pub fn frontier(self: *const Self) []const types.Candidate {63            self.assertValid();64            return self.frontier_storage[0..self.frontier_count];65        }6667        pub fn progress(self: *const Self) types.Progress {68            self.assertValid();69            return .{70                .executions = self.execution_count,71                .retained = self.branch_count,72                .frontier = self.frontier_count,73                .pruned = self.pruned_count,74            };75        }7677        pub fn branch(self: *const Self, id: types.BranchId) Error!types.Branch {78            self.assertValid();79            if (id >= self.branch_count) return error.BranchUnknown;80            return self.branches_storage[id];81        }8283        pub fn findExact(84            self: *const Self,85            root: world.Moment,86        ) ?types.BranchId {87            self.assertValid();88            for (self.branches(), 0..) |retained, index| {89                if (std.meta.eql(retained.root, root)) return @intCast(index);90            }91            return null;92        }9394        pub fn history(95            self: *const Self,96            id: types.BranchId,97            destination: []types.Decision,98        ) Error![]const types.Decision {99            const selected = try self.branch(id);100            const depth: usize = selected.depth;101            if (destination.len < depth) return error.HistoryCapacityExceeded;102            var cursor = id;103            var remaining = depth;104            while (remaining > 0) {105                const current = self.branches_storage[cursor];106                remaining -= 1;107                destination[remaining] = current.decision.?;108                cursor = current.parent.?;109            }110            std.debug.assert(cursor == 0);111            return destination[0..depth];112        }113114        pub fn expandInput(115            self: *Self,116            parent: types.BranchId,117            site: anytype,118        ) Error!types.Expansion {119            return self.expand(parent, site, .input);120        }121122        pub fn expandSchedule(123            self: *Self,124            parent: types.BranchId,125            site: anytype,126        ) Error!types.Expansion {127            return self.expand(parent, site, .schedule);128        }129130        pub fn expandTopology(131            self: *Self,132            parent: types.BranchId,133            site: anytype,134        ) Error!types.Expansion {135            return self.expand(parent, site, .topology);136        }137138        pub fn expandFault(139            self: *Self,140            parent: types.BranchId,141            site: anytype,142        ) Error!types.Expansion {143            return self.expand(parent, site, .fault);144        }145146        pub fn step(self: *Self, runner: types.Runner) types.Outcome {147            self.assertValid();148            if (self.execution_count == self.budget.executions) {149                return self.exhausted(.execution_budget);150            }151            if (self.frontier_count == 0) return self.exhausted(.frontier_empty);152            if (self.branch_count == capacity.retained) {153                return incompleteOutcome(.retained_capacity, self.frontier_storage[0]);154            }155            const candidate = self.frontier_storage[0];156            const parent = self.branches_storage[candidate.parent];157            const result = runner.run(parent.root, candidate.decision);158            self.execution_count += 1;159            const outcome = switch (result) {160                .completed => |root| if (momentFollows(parent.root, root))161                    self.complete(candidate, root)162                else163                    incompleteOutcome(.{ .execution = .invalid_moment }, candidate),164                .failed => |failure| if (!momentFollows(parent.root, failure.root))165                    incompleteOutcome(.{ .execution = .invalid_moment }, candidate)166                else if (failure.evaluation.verdict != .violated)167                    incompleteOutcome(.{ .execution = .invalid_failure }, candidate)168                else169                    self.fail(candidate, failure),170                .incomplete => |reason| incompleteOutcome(171                    .{ .execution = reason },172                    candidate,173                ),174            };175            self.assertValid();176            return outcome;177        }178179        pub fn pruneNext(self: *Self) types.Outcome {180            self.assertValid();181            if (self.frontier_count == 0) return self.exhausted(.frontier_empty);182            const candidate = self.removeCandidate();183            self.pruned_count += 1;184            self.assertValid();185            return .{ .pruned = .{186                .reason = .strategy,187                .parent = candidate.parent,188                .decision = candidate.decision,189                .count = 1,190            } };191        }192193        pub fn interrupt(self: *const Self) types.Outcome {194            self.assertValid();195            const candidate = if (self.frontier_count == 0)196                null197            else198                self.frontier_storage[0];199            return incompleteOutcome(.interrupted, candidate);200        }201202        pub fn generationIncomplete(203            self: *const Self,204            reason: explore.IncompleteReason,205        ) types.Outcome {206            self.assertValid();207            const candidate = if (self.frontier_count == 0)208                null209            else210                self.frontier_storage[0];211            return incompleteOutcome(.{ .generation = reason }, candidate);212        }213214        fn expand(215            self: *Self,216            parent_id: types.BranchId,217            site: anytype,218            comptime stream: explore.Stream,219        ) Error!types.Expansion {220            self.assertValid();221            if (parent_id >= self.branch_count) return error.BranchUnknown;222            const parent = &self.branches_storage[parent_id];223            if (parent.expanded) return error.BranchAlreadyExpanded;224            if (!siteValid(site, stream)) return error.ChoiceSiteInvalid;225            if (parent.depth >= self.budget.depth) {226                parent.expanded = true;227                return .{ .exhausted = self.exhaustedValue(.depth_budget) };228            }229            const available = capacity.frontier - self.frontier_count;230            const admitted: u8 = @intCast(@min(site.count, available));231            self.addSite(parent_id, site, stream, admitted);232            parent.expanded = true;233            if (admitted == site.count) {234                return .{ .expanded = .{ .parent = parent_id, .admitted = admitted } };235            }236            const discarded: u16 = site.count - admitted;237            self.pruned_count += discarded;238            return .{ .pruned = .{239                .reason = .frontier_capacity,240                .parent = parent_id,241                .decision = null,242                .count = discarded,243            } };244        }245246        fn addSite(247            self: *Self,248            parent: types.BranchId,249            site: anytype,250            comptime stream: explore.Stream,251            admitted: u8,252        ) void {253            if (admitted == 0) return;254            self.addAlternative(parent, site, stream, site.suggested);255            var added: u8 = 1;256            var index: u8 = 0;257            while (index < site.count and added < admitted) : (index += 1) {258                if (index == site.suggested) continue;259                self.addAlternative(parent, site, stream, index);260                added += 1;261            }262            std.debug.assert(added == admitted);263        }264265        fn addAlternative(266            self: *Self,267            parent: types.BranchId,268            site: anytype,269            comptime stream: explore.Stream,270            index: u8,271        ) void {272            std.debug.assert(self.frontier_count < capacity.frontier);273            self.frontier_storage[self.frontier_count] = .{274                .parent = parent,275                .decision = .{276                    .site = site.id,277                    .alternative = index,278                    .alternative_count = site.count,279                    .choice = @unionInit(280                        types.Choice,281                        @tagName(stream),282                        site.alternatives[index],283                    ),284                },285            };286            self.frontier_count += 1;287        }288289        fn complete(290            self: *Self,291            candidate: types.Candidate,292            root: world.Moment,293        ) types.Outcome {294            _ = self.removeCandidate();295            const branch_id = self.retain(candidate, root, .completed);296            return .{ .completed = .{297                .branch = branch_id,298                .parent = candidate.parent,299                .decision = candidate.decision,300            } };301        }302303        fn fail(304            self: *Self,305            candidate: types.Candidate,306            failure: types.FailedExecution,307        ) types.Outcome {308            _ = self.removeCandidate();309            const branch_id = self.retain(310                candidate,311                failure.root,312                .{ .failed = failure.evaluation },313            );314            return .{ .failed = .{315                .branch = branch_id,316                .parent = candidate.parent,317                .decision = candidate.decision,318                .evaluation = failure.evaluation,319            } };320        }321322        fn retain(323            self: *Self,324            candidate: types.Candidate,325            root: world.Moment,326            settlement: types.Settlement,327        ) types.BranchId {328            std.debug.assert(self.branch_count < capacity.retained);329            const parent = self.branches_storage[candidate.parent];330            const id = self.branch_count;331            self.branches_storage[id] = .{332                .root = root,333                .parent = candidate.parent,334                .decision = candidate.decision,335                .depth = parent.depth + 1,336                .settlement = settlement,337            };338            self.branch_count += 1;339            return id;340        }341342        fn removeCandidate(self: *Self) types.Candidate {343            std.debug.assert(self.frontier_count > 0);344            const candidate = self.frontier_storage[0];345            const remaining = self.frontier_count - 1;346            std.mem.copyForwards(347                types.Candidate,348                self.frontier_storage[0..remaining],349                self.frontier_storage[1..self.frontier_count],350            );351            self.frontier_count = remaining;352            return candidate;353        }354355        fn exhausted(356            self: *const Self,357            reason: types.ExhaustedReason,358        ) types.Outcome {359            return .{ .exhausted = self.exhaustedValue(reason) };360        }361362        fn exhaustedValue(363            self: *const Self,364            reason: types.ExhaustedReason,365        ) types.Exhausted {366            return .{367                .reason = reason,368                .executions = self.execution_count,369                .frontier = self.frontier_count,370            };371        }372373        fn incompleteOutcome(374            reason: types.IncompleteReason,375            candidate: ?types.Candidate,376        ) types.Outcome {377            return .{ .incomplete = .{378                .reason = reason,379                .candidate = candidate,380            } };381        }382383        fn validateCheckpoint(self: *const Self) Error!void {384            if (self.branch_count == 0 or385                self.branch_count > capacity.retained or386                self.frontier_count > capacity.frontier or387                self.execution_count > self.budget.executions or388                self.execution_count < self.branch_count - 1)389            {390                return error.CheckpointInvalid;391            }392            try self.validateBranches();393            try self.validateFrontier();394        }395396        fn validateBranches(self: *const Self) Error!void {397            const root = self.branches_storage[0];398            if (root.parent != null or root.decision != null or root.depth != 0 or399                std.meta.activeTag(root.settlement) != .origin)400            {401                return error.CheckpointInvalid;402            }403            world.verifyMoment(root.root, root.root.origin, root.root.fabric) catch404                return error.CheckpointInvalid;405            for (self.branches_storage[1..self.branch_count], 1..) |branch_value, index| {406                const parent = branch_value.parent orelse407                    return error.CheckpointInvalid;408                const decision = branch_value.decision orelse409                    return error.CheckpointInvalid;410                if (parent >= index or !decision.valid()) {411                    return error.CheckpointInvalid;412                }413                if (!momentFollows(414                    self.branches_storage[parent].root,415                    branch_value.root,416                )) return error.CheckpointInvalid;417                const parent_depth = self.branches_storage[parent].depth;418                if (branch_value.depth != parent_depth + 1 or419                    branch_value.depth > self.budget.depth or420                    !self.branches_storage[parent].expanded or421                    std.meta.activeTag(branch_value.settlement) == .origin)422                {423                    return error.CheckpointInvalid;424                }425                if (branchFailureInvalid(branch_value.settlement)) {426                    return error.CheckpointInvalid;427                }428                for (self.branches_storage[1..index]) |prior| {429                    if (sameBranchWork(prior, branch_value)) {430                        return error.CheckpointInvalid;431                    }432                }433            }434        }435436        fn validateFrontier(self: *const Self) Error!void {437            for (438                self.frontier_storage[0..self.frontier_count],439                0..,440            ) |candidate, index| {441                if (candidate.parent >= self.branch_count or442                    !candidate.decision.valid() or443                    !self.branches_storage[candidate.parent].expanded or444                    self.branches_storage[candidate.parent].depth >= self.budget.depth)445                {446                    return error.CheckpointInvalid;447                }448                for (self.frontier_storage[0..index]) |prior| {449                    if (sameCandidateWork(prior, candidate)) {450                        return error.CheckpointInvalid;451                    }452                }453                for (self.branches_storage[1..self.branch_count]) |settled| {454                    if (sameSettledWork(settled, candidate)) {455                        return error.CheckpointInvalid;456                    }457                }458            }459        }460461        fn assertValid(self: *const Self) void {462            std.debug.assert(self.branch_count > 0);463            std.debug.assert(self.branch_count <= capacity.retained);464            std.debug.assert(self.frontier_count <= capacity.frontier);465            std.debug.assert(self.execution_count <= self.budget.executions);466            std.debug.assert(self.execution_count >= self.branch_count - 1);467        }468    };469}