lib/machine/src/explore/search/owner.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const explore = @import("../root.zig");
2 const std = @import("std");
3 const types = @import("types.zig");
4 const world = @import("../../world/root.zig");
5
6 /// Returns a search type that keeps two arrays for each pair of capacities, so
7 /// the whole search fits storage fixed at compile time, and a failing run can
8 /// be walked back to the root through its parents. The first array holds the
9 /// queue of choices waiting to run (*frontier*), up to the frontier capacity,
10 /// and the second holds every settled run the search keeps, up to the retained
11 /// capacity. A frontier or retained capacity of zero stops the build with a
12 /// compile error. `init` verifies the root position in a world's history
13 /// (*moment*) and stores it as branch 0. Each settled run keeps its complete
14 /// moment, its parent, and the alternative taken at a step (*decision*), so
15 /// `history` walks a run back to the root and returns its decisions in order.
16 /// `findExact` matches a settled run only when every field of its moment is
17 /// equal, so two runs whose digests agree stay two runs. The search stores both
18 /// arrays inside the value and holds no pointers, so `checkpoint` returns a
19 /// plain copy of it. `restoreCheckpoint` validates a saved copy and returns
20 /// `CheckpointInvalid` for a corrupt one.
21 pub fn Search(comptime capacity_value: types.Capacity) type {
22 if (capacity_value.frontier == 0) {
23 @compileError("search frontier capacity must be positive");
24 }
25 if (capacity_value.retained == 0) {
26 @compileError("search retained capacity must be positive");
27 }
28 return struct {
29 branches_storage: [capacity.retained]types.Branch = undefined,
30 frontier_storage: [capacity.frontier]types.Candidate = undefined,
31 branch_count: u16 = 0,
32 frontier_count: u16 = 0,
33 budget: types.Budget,
34 execution_count: u32 = 0,
35 pruned_count: u64 = 0,
36
37 const Self = @This();
38
39 pub const capacity: types.Capacity = capacity_value;
40 pub const Checkpoint = Self;
41 pub const Error = types.Error;
42
43 pub fn init(root: world.Moment, budget: types.Budget) Error!Self {
44 try world.verifyMoment(root, root.origin, root.fabric);
45 var self = Self{ .budget = budget };
46 self.branches_storage[0] = .{ .root = root };
47 self.branch_count = 1;
48 self.assertValid();
49 return self;
50 }
51
52 pub fn checkpoint(self: *const Self) Checkpoint {
53 self.validateCheckpoint() catch unreachable;
54 return self.*;
55 }
56
57 pub fn restoreCheckpoint(value: Checkpoint) Error!Self {
58 try value.validateCheckpoint();
59 return value;
60 }
61
62 pub fn branches(self: *const Self) []const types.Branch {
63 self.assertValid();
64 return self.branches_storage[0..self.branch_count];
65 }
66
67 pub fn frontier(self: *const Self) []const types.Candidate {
68 self.assertValid();
69 return self.frontier_storage[0..self.frontier_count];
70 }
71
72 pub fn progress(self: *const Self) types.Progress {
73 self.assertValid();
74 return .{
75 .executions = self.execution_count,
76 .retained = self.branch_count,
77 .frontier = self.frontier_count,
78 .pruned = self.pruned_count,
79 };
80 }
81
82 pub fn branch(self: *const Self, id: types.BranchId) Error!types.Branch {
83 self.assertValid();
84 if (id >= self.branch_count) return error.BranchUnknown;
85 return self.branches_storage[id];
86 }
87
88 pub fn findExact(
89 self: *const Self,
90 root: world.Moment,
91 ) ?types.BranchId {
92 self.assertValid();
93 for (self.branches(), 0..) |retained, index| {
94 if (std.meta.eql(retained.root, root)) return @intCast(index);
95 }
96 return null;
97 }
98
99 pub fn history(
100 self: *const Self,
101 id: types.BranchId,
102 destination: []types.Decision,
103 ) Error![]const types.Decision {
104 const selected = try self.branch(id);
105 const depth: usize = selected.depth;
106 if (destination.len < depth) return error.HistoryCapacityExceeded;
107 var cursor = id;
108 var remaining = depth;
109 while (remaining > 0) {
110 const current = self.branches_storage[cursor];
111 remaining -= 1;
112 destination[remaining] = current.decision.?;
113 cursor = current.parent.?;
114 }
115 std.debug.assert(cursor == 0);
116 return destination[0..depth];
117 }
118
119 pub fn expandInput(
120 self: *Self,
121 parent: types.BranchId,
122 site: anytype,
123 ) Error!types.Expansion {
124 return self.expand(parent, site, .input);
125 }
126
127 pub fn expandSchedule(
128 self: *Self,
129 parent: types.BranchId,
130 site: anytype,
131 ) Error!types.Expansion {
132 return self.expand(parent, site, .schedule);
133 }
134
135 pub fn expandTopology(
136 self: *Self,
137 parent: types.BranchId,
138 site: anytype,
139 ) Error!types.Expansion {
140 return self.expand(parent, site, .topology);
141 }
142
143 pub fn expandFault(
144 self: *Self,
145 parent: types.BranchId,
146 site: anytype,
147 ) Error!types.Expansion {
148 return self.expand(parent, site, .fault);
149 }
150
151 pub fn step(self: *Self, runner: types.Runner) types.Outcome {
152 self.assertValid();
153 if (self.execution_count == self.budget.executions) {
154 return self.exhausted(.execution_budget);
155 }
156 if (self.frontier_count == 0) return self.exhausted(.frontier_empty);
157 if (self.branch_count == capacity.retained) {
158 return incompleteOutcome(.retained_capacity, self.frontier_storage[0]);
159 }
160 const candidate = self.frontier_storage[0];
161 const parent = self.branches_storage[candidate.parent];
162 const result = runner.run(parent.root, candidate.decision);
163 self.execution_count += 1;
164 const outcome = switch (result) {
165 .completed => |root| if (momentFollows(parent.root, root))
166 self.complete(candidate, root)
167 else
168 incompleteOutcome(.{ .execution = .invalid_moment }, candidate),
169 .failed => |failure| if (!momentFollows(parent.root, failure.root))
170 incompleteOutcome(.{ .execution = .invalid_moment }, candidate)
171 else if (failure.evaluation.verdict != .violated)
172 incompleteOutcome(.{ .execution = .invalid_failure }, candidate)
173 else
174 self.fail(candidate, failure),
175 .incomplete => |reason| incompleteOutcome(
176 .{ .execution = reason },
177 candidate,
178 ),
179 };
180 self.assertValid();
181 return outcome;
182 }
183
184 pub fn pruneNext(self: *Self) types.Outcome {
185 self.assertValid();
186 if (self.frontier_count == 0) return self.exhausted(.frontier_empty);
187 const candidate = self.removeCandidate();
188 self.pruned_count += 1;
189 self.assertValid();
190 return .{ .pruned = .{
191 .reason = .strategy,
192 .parent = candidate.parent,
193 .decision = candidate.decision,
194 .count = 1,
195 } };
196 }
197
198 pub fn interrupt(self: *const Self) types.Outcome {
199 self.assertValid();
200 const candidate = if (self.frontier_count == 0)
201 null
202 else
203 self.frontier_storage[0];
204 return incompleteOutcome(.interrupted, candidate);
205 }
206
207 pub fn generationIncomplete(
208 self: *const Self,
209 reason: explore.IncompleteReason,
210 ) types.Outcome {
211 self.assertValid();
212 const candidate = if (self.frontier_count == 0)
213 null
214 else
215 self.frontier_storage[0];
216 return incompleteOutcome(.{ .generation = reason }, candidate);
217 }
218
219 fn expand(
220 self: *Self,
221 parent_id: types.BranchId,
222 site: anytype,
223 comptime stream: explore.Stream,
224 ) Error!types.Expansion {
225 self.assertValid();
226 if (parent_id >= self.branch_count) return error.BranchUnknown;
227 const parent = &self.branches_storage[parent_id];
228 if (parent.expanded) return error.BranchAlreadyExpanded;
229 if (!siteValid(site, stream)) return error.ChoiceSiteInvalid;
230 if (parent.depth >= self.budget.depth) {
231 parent.expanded = true;
232 return .{ .exhausted = self.exhaustedValue(.depth_budget) };
233 }
234 const available = capacity.frontier - self.frontier_count;
235 const admitted: u8 = @intCast(@min(site.count, available));
236 self.addSite(parent_id, site, stream, admitted);
237 parent.expanded = true;
238 if (admitted == site.count) {
239 return .{ .expanded = .{ .parent = parent_id, .admitted = admitted } };
240 }
241 const discarded: u16 = site.count - admitted;
242 self.pruned_count += discarded;
243 return .{ .pruned = .{
244 .reason = .frontier_capacity,
245 .parent = parent_id,
246 .decision = null,
247 .count = discarded,
248 } };
249 }
250
251 fn addSite(
252 self: *Self,
253 parent: types.BranchId,
254 site: anytype,
255 comptime stream: explore.Stream,
256 admitted: u8,
257 ) void {
258 if (admitted == 0) return;
259 self.addAlternative(parent, site, stream, site.suggested);
260 var added: u8 = 1;
261 var index: u8 = 0;
262 while (index < site.count and added < admitted) : (index += 1) {
263 if (index == site.suggested) continue;
264 self.addAlternative(parent, site, stream, index);
265 added += 1;
266 }
267 std.debug.assert(added == admitted);
268 }
269
270 fn addAlternative(
271 self: *Self,
272 parent: types.BranchId,
273 site: anytype,
274 comptime stream: explore.Stream,
275 index: u8,
276 ) void {
277 std.debug.assert(self.frontier_count < capacity.frontier);
278 self.frontier_storage[self.frontier_count] = .{
279 .parent = parent,
280 .decision = .{
281 .site = site.id,
282 .alternative = index,
283 .alternative_count = site.count,
284 .choice = @unionInit(
285 types.Choice,
286 @tagName(stream),
287 site.alternatives[index],
288 ),
289 },
290 };
291 self.frontier_count += 1;
292 }
293
294 fn complete(
295 self: *Self,
296 candidate: types.Candidate,
297 root: world.Moment,
298 ) types.Outcome {
299 _ = self.removeCandidate();
300 const branch_id = self.retain(candidate, root, .completed);
301 return .{ .completed = .{
302 .branch = branch_id,
303 .parent = candidate.parent,
304 .decision = candidate.decision,
305 } };
306 }
307
308 fn fail(
309 self: *Self,
310 candidate: types.Candidate,
311 failure: types.FailedExecution,
312 ) types.Outcome {
313 _ = self.removeCandidate();
314 const branch_id = self.retain(
315 candidate,
316 failure.root,
317 .{ .failed = failure.evaluation },
318 );
319 return .{ .failed = .{
320 .branch = branch_id,
321 .parent = candidate.parent,
322 .decision = candidate.decision,
323 .evaluation = failure.evaluation,
324 } };
325 }
326
327 fn retain(
328 self: *Self,
329 candidate: types.Candidate,
330 root: world.Moment,
331 settlement: types.Settlement,
332 ) types.BranchId {
333 std.debug.assert(self.branch_count < capacity.retained);
334 const parent = self.branches_storage[candidate.parent];
335 const id = self.branch_count;
336 self.branches_storage[id] = .{
337 .root = root,
338 .parent = candidate.parent,
339 .decision = candidate.decision,
340 .depth = parent.depth + 1,
341 .settlement = settlement,
342 };
343 self.branch_count += 1;
344 return id;
345 }
346
347 fn removeCandidate(self: *Self) types.Candidate {
348 std.debug.assert(self.frontier_count > 0);
349 const candidate = self.frontier_storage[0];
350 const remaining = self.frontier_count - 1;
351 std.mem.copyForwards(
352 types.Candidate,
353 self.frontier_storage[0..remaining],
354 self.frontier_storage[1..self.frontier_count],
355 );
356 self.frontier_count = remaining;
357 return candidate;
358 }
359
360 fn exhausted(
361 self: *const Self,
362 reason: types.ExhaustedReason,
363 ) types.Outcome {
364 return .{ .exhausted = self.exhaustedValue(reason) };
365 }
366
367 fn exhaustedValue(
368 self: *const Self,
369 reason: types.ExhaustedReason,
370 ) types.Exhausted {
371 return .{
372 .reason = reason,
373 .executions = self.execution_count,
374 .frontier = self.frontier_count,
375 };
376 }
377
378 fn incompleteOutcome(
379 reason: types.IncompleteReason,
380 candidate: ?types.Candidate,
381 ) types.Outcome {
382 return .{ .incomplete = .{
383 .reason = reason,
384 .candidate = candidate,
385 } };
386 }
387
388 fn validateCheckpoint(self: *const Self) Error!void {
389 if (self.branch_count == 0 or
390 self.branch_count > capacity.retained or
391 self.frontier_count > capacity.frontier or
392 self.execution_count > self.budget.executions or
393 self.execution_count < self.branch_count - 1)
394 {
395 return error.CheckpointInvalid;
396 }
397 try self.validateBranches();
398 try self.validateFrontier();
399 }
400
401 fn validateBranches(self: *const Self) Error!void {
402 const root = self.branches_storage[0];
403 if (root.parent != null or root.decision != null or root.depth != 0 or
404 std.meta.activeTag(root.settlement) != .origin)
405 {
406 return error.CheckpointInvalid;
407 }
408 world.verifyMoment(root.root, root.root.origin, root.root.fabric) catch
409 return error.CheckpointInvalid;
410 for (self.branches_storage[1..self.branch_count], 1..) |branch_value, index| {
411 const parent = branch_value.parent orelse
412 return error.CheckpointInvalid;
413 const decision = branch_value.decision orelse
414 return error.CheckpointInvalid;
415 if (parent >= index or !decision.valid()) {
416 return error.CheckpointInvalid;
417 }
418 if (!momentFollows(
419 self.branches_storage[parent].root,
420 branch_value.root,
421 )) return error.CheckpointInvalid;
422 const parent_depth = self.branches_storage[parent].depth;
423 if (branch_value.depth != parent_depth + 1 or
424 branch_value.depth > self.budget.depth or
425 !self.branches_storage[parent].expanded or
426 std.meta.activeTag(branch_value.settlement) == .origin)
427 {
428 return error.CheckpointInvalid;
429 }
430 if (branchFailureInvalid(branch_value.settlement)) {
431 return error.CheckpointInvalid;
432 }
433 for (self.branches_storage[1..index]) |prior| {
434 if (sameBranchWork(prior, branch_value)) {
435 return error.CheckpointInvalid;
436 }
437 }
438 }
439 }
440
441 fn validateFrontier(self: *const Self) Error!void {
442 for (
443 self.frontier_storage[0..self.frontier_count],
444 0..,
445 ) |candidate, index| {
446 if (candidate.parent >= self.branch_count or
447 !candidate.decision.valid() or
448 !self.branches_storage[candidate.parent].expanded or
449 self.branches_storage[candidate.parent].depth >= self.budget.depth)
450 {
451 return error.CheckpointInvalid;
452 }
453 for (self.frontier_storage[0..index]) |prior| {
454 if (sameCandidateWork(prior, candidate)) {
455 return error.CheckpointInvalid;
456 }
457 }
458 for (self.branches_storage[1..self.branch_count]) |settled| {
459 if (sameSettledWork(settled, candidate)) {
460 return error.CheckpointInvalid;
461 }
462 }
463 }
464 }
465
466 fn assertValid(self: *const Self) void {
467 std.debug.assert(self.branch_count > 0);
468 std.debug.assert(self.branch_count <= capacity.retained);
469 std.debug.assert(self.frontier_count <= capacity.frontier);
470 std.debug.assert(self.execution_count <= self.budget.executions);
471 std.debug.assert(self.execution_count >= self.branch_count - 1);
472 }
473 };
474 }
475
476 fn siteValid(site: anytype, stream: explore.Stream) bool {
477 if (site.id.stream != stream or site.count == 0) return false;
478 if (site.count > site.alternatives.len) return false;
479 return site.suggested < site.count;
480 }
481
482 fn branchFailureInvalid(settlement: types.Settlement) bool {
483 return switch (settlement) {
484 .failed => |evaluation| evaluation.verdict != .violated,
485 .origin, .completed => false,
486 };
487 }
488
489 fn sameBranchWork(left: types.Branch, right: types.Branch) bool {
490 return left.parent == right.parent and
491 std.meta.eql(left.decision.?, right.decision.?);
492 }
493
494 fn sameCandidateWork(left: types.Candidate, right: types.Candidate) bool {
495 return left.parent == right.parent and
496 std.meta.eql(left.decision, right.decision);
497 }
498
499 fn sameSettledWork(
500 settled: types.Branch,
501 candidate: types.Candidate,
502 ) bool {
503 return settled.parent == candidate.parent and
504 std.meta.eql(settled.decision.?, candidate.decision);
505 }
506
507 fn momentFollows(parent: world.Moment, value: world.Moment) bool {
508 world.verifyMoment(value, parent.origin, value.fabric) catch return false;
509 return value.fabric.entry_frontier >= parent.fabric.entry_frontier and
510 value.fabric.admission_frontier >= parent.fabric.admission_frontier and
511 value.fabric.fault_frontier >= parent.fabric.fault_frontier;
512 }