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