lib/machine/src/explore/topology.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.TopologyCapacity) type {
7 return struct {
8 seed: explore.Seed,
9 plan: explore.TopologyPlan,
10 sequence: u16 = 0,
11 virtual_time_tick: u64,
12 included: [capacity.nodes]bool = @splat(false),
13 done: bool = false,
14
15 const Self = @This();
16
17 pub const capacity: explore.TopologyCapacity = capacity_value;
18 pub const Error: type = explore.GeneratorError;
19 pub const InitResult: type = explore.Generation(Self);
20 pub const Site: type = explore.ChoiceSite(
21 explore.TopologyAlternative,
22 capacity.alternatives,
23 );
24 pub const NextResult: type = explore.Generation(Site);
25
26 pub fn init(
27 selected: profile.Profile,
28 seed: explore.Seed,
29 plan: explore.TopologyPlan,
30 ) Error!InitResult {
31 try profile.validate(selected);
32 if (plan.nodes == 0 or plan.nodes > fabric.node_limit) {
33 return error.InvalidPlan;
34 }
35 if (plan.temporal.end_tick < plan.temporal.start_tick) {
36 return error.InvalidPlan;
37 }
38 if (plan.temporal.steps == 0) {
39 return .{ .incomplete = .step_capacity };
40 }
41 if (plan.temporal.start_tick == plan.temporal.end_tick) {
42 return .{ .incomplete = .virtual_time_bound };
43 }
44 if (plan.temporal.steps > capacity.steps) {
45 return .{ .incomplete = .step_capacity };
46 }
47 if (plan.nodes > capacity.nodes) {
48 return .{ .incomplete = .node_capacity };
49 }
50 if (capacity.alternatives < plan.nodes + 1) {
51 return .{ .incomplete = .alternative_capacity };
52 }
53 return .{ .item = .{
54 .seed = seed,
55 .plan = plan,
56 .virtual_time_tick = plan.temporal.start_tick,
57 } };
58 }
59
60 pub fn next(self: *const Self) NextResult {
61 self.assertValid();
62 if (self.done) return .exhausted;
63 if (self.sequence == self.plan.temporal.steps) {
64 return .{ .incomplete = .step_capacity };
65 }
66 if (self.virtual_time_tick == self.plan.temporal.end_tick) {
67 return .{ .incomplete = .virtual_time_bound };
68 }
69 var site = Site{
70 .id = self.siteId(),
71 .alternatives = undefined,
72 .count = 0,
73 .suggested = 0,
74 };
75 self.addNodes(&site);
76 if (self.includedCount() > 0) self.addComplete(&site);
77 std.debug.assert(site.count > 0);
78 site.suggested = self.seed.suggest(.topology, self.sequence, site.count);
79 return .{ .item = site };
80 }
81
82 pub fn choose(
83 self: *Self,
84 site: Site,
85 index: u8,
86 ) Error!explore.GeneratedTopology {
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.value) {
95 .node => |node| self.applyNode(node),
96 .complete => self.done = true,
97 }
98 self.virtual_time_tick = selected.virtual_time_tick;
99 self.sequence += 1;
100 self.assertValid();
101 return selected;
102 }
103
104 pub fn nodeIncluded(self: *const Self, node: u8) bool {
105 std.debug.assert(node < self.plan.nodes);
106 self.assertValid();
107 return self.included[node];
108 }
109
110 fn addNodes(self: *const Self, site: *Site) void {
111 const active = self.includedCount();
112 for (0..self.plan.nodes) |index| {
113 if (active == 1 and self.included[index]) continue;
114 const node: u8 = @intCast(index);
115 self.add(site, .backend_availability, .{ .node = .{
116 .id = self.nodeId(node),
117 .included = !self.included[index],
118 } });
119 }
120 }
121
122 fn addComplete(self: *const Self, site: *Site) void {
123 self.add(site, .backend_selection, .{ .complete = {} });
124 }
125
126 fn add(
127 self: *const Self,
128 site: *Site,
129 source: profile.DeterminismSource,
130 value: explore.TopologyValue,
131 ) void {
132 std.debug.assert(site.count < site.alternatives.len);
133 site.alternatives[site.count] = .{
134 .origin = explore.origin(source),
135 .virtual_time_tick = self.virtual_time_tick + 1,
136 .value = value,
137 };
138 site.count += 1;
139 }
140
141 fn applyNode(self: *Self, selected: explore.TopologyNode) void {
142 for (0..self.plan.nodes) |index| {
143 const node: u8 = @intCast(index);
144 if (!std.meta.eql(self.nodeId(node), selected.id)) continue;
145 self.included[index] = selected.included;
146 return;
147 }
148 unreachable;
149 }
150
151 fn nodeId(self: *const Self, node: u8) fabric.NodeId {
152 const digest = self.seed.digest(.topology, node, 1);
153 var bytes: [16]u8 = undefined;
154 @memcpy(&bytes, digest[0..bytes.len]);
155 return .{ .bytes = bytes };
156 }
157
158 fn includedCount(self: *const Self) u8 {
159 var result: u8 = 0;
160 for (self.included[0..self.plan.nodes]) |included| {
161 if (included) result += 1;
162 }
163 std.debug.assert(result <= self.plan.nodes);
164 return result;
165 }
166
167 fn siteId(self: *const Self) explore.SiteId {
168 return .{
169 .stream = .topology,
170 .sequence = self.sequence,
171 .virtual_time_tick = self.virtual_time_tick,
172 };
173 }
174
175 fn assertValid(self: *const Self) void {
176 std.debug.assert(self.sequence <= self.plan.temporal.steps);
177 std.debug.assert(self.sequence <= capacity.steps);
178 std.debug.assert(self.virtual_time_tick >= self.plan.temporal.start_tick);
179 std.debug.assert(self.virtual_time_tick <= self.plan.temporal.end_tick);
180 std.debug.assert(self.includedCount() <= self.plan.nodes);
181 }
182
183 fn sameSite(expected: Site, actual: Site) bool {
184 if (!std.meta.eql(expected.id, actual.id)) return false;
185 if (expected.count != actual.count) return false;
186 if (expected.suggested != actual.suggested) return false;
187 for (expected.values(), actual.values()) |left, right| {
188 if (!std.meta.eql(left, right)) return false;
189 }
190 return true;
191 }
192 };
193 }