lib/machine/src/explore/query/engine.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const explore = @import("../root.zig");
2 const fabric = @import("../../fabric/root.zig");
3 const fault = @import("../../fault/root.zig");
4 const os = @import("os");
5 const std = @import("std");
6 const types = @import("types.zig");
7 const world = @import("../../world/root.zig");
8
9 pub fn Query(comptime capacity_value: types.QueryCapacity) type {
10 if (capacity_value.results == 0) {
11 @compileError("query result capacity must be positive");
12 }
13 return struct {
14 storage: [capacity.results]types.EvidenceRef = undefined,
15 count: u16 = 0,
16
17 const Self = @This();
18
19 pub const capacity: types.QueryCapacity = capacity_value;
20
21 pub fn run(
22 self: *Self,
23 history: anytype,
24 plan: types.QueryPlan,
25 ) types.Error!types.QueryResult {
26 self.count = 0;
27 const identity = try history.identity();
28 const total = history.logicalCount();
29 const range = try queryRange(history, plan.scope, total);
30 if (plan.virtual_time) |window| {
31 if (window.first > window.last) return error.InvalidQueryPlan;
32 }
33 var offset = if (plan.cursor) |cursor| cursor.offset else 0;
34 if (plan.cursor) |cursor| {
35 if (!std.meta.eql(cursor.history, identity)) {
36 return error.CursorHistoryMismatch;
37 }
38 if (cursor.first != range.first or
39 cursor.end != range.end or
40 cursor.order != plan.order)
41 {
42 return error.CursorPlanMismatch;
43 }
44 }
45 const span = range.end - range.first;
46 if (offset > span) return error.EvidenceIndexInvalid;
47 var inspected: u32 = 0;
48 while (offset < span and inspected < plan.work) {
49 const logical_offset = switch (plan.order) {
50 .forward => range.first + offset,
51 .reverse => range.end - 1 - offset,
52 };
53 const reference = try history.referenceAt(logical_offset);
54 const located = try history.lookup(reference);
55 inspected += 1;
56 offset += 1;
57 if (!withinTime(plan.virtual_time, located.virtual_time_tick)) {
58 continue;
59 }
60 if (!try matches(plan.pattern, located)) continue;
61 self.storage[self.count] = reference;
62 self.count += 1;
63 if (self.count == capacity.results and offset < span) {
64 return self.result(
65 identity,
66 inspected,
67 range,
68 plan.order,
69 offset,
70 .result_capacity,
71 );
72 }
73 }
74 if (offset < span) {
75 return self.result(
76 identity,
77 inspected,
78 range,
79 plan.order,
80 offset,
81 .work_budget,
82 );
83 }
84 if (history.traceState() == .incomplete and sourceCanGrow(plan.scope)) {
85 return self.result(
86 identity,
87 inspected,
88 range,
89 plan.order,
90 offset,
91 .source_incomplete,
92 );
93 }
94 return .{
95 .matches = self.storage[0..self.count],
96 .inspected = inspected,
97 .next = null,
98 .completion = .complete,
99 };
100 }
101
102 fn result(
103 self: *const Self,
104 identity: types.Identity,
105 inspected: u32,
106 range: Range,
107 order: types.QueryOrder,
108 offset: u32,
109 reason: types.IncompleteReason,
110 ) types.QueryResult {
111 return .{
112 .matches = self.storage[0..self.count],
113 .inspected = inspected,
114 .next = .{
115 .history = identity,
116 .offset = offset,
117 .first = range.first,
118 .end = range.end,
119 .order = order,
120 },
121 .completion = .{ .incomplete = reason },
122 };
123 }
124 };
125 }
126
127 const Range = struct {
128 first: u32,
129 end: u32,
130 };
131
132 fn queryRange(history: anytype, scope: types.QueryScope, total: u32) types.Error!Range {
133 return switch (scope) {
134 .branch => .{ .first = 0, .end = total },
135 .before => |reference| .{
136 .first = 0,
137 .end = try history.logicalOffset(reference),
138 },
139 .after => |reference| .{
140 .first = try history.logicalOffset(reference) + 1,
141 .end = total,
142 },
143 };
144 }
145
146 fn sourceCanGrow(scope: types.QueryScope) bool {
147 return switch (scope) {
148 .branch, .after => true,
149 .before => false,
150 };
151 }
152
153 fn withinTime(expected: ?types.VirtualTimeRange, actual: ?u64) bool {
154 const range = expected orelse return true;
155 const tick = actual orelse return false;
156 return tick >= range.first and tick <= range.last;
157 }
158
159 pub fn Diff(comptime capacity_value: types.DiffCapacity) type {
160 return struct {
161 prefix_storage: [capacity.prefix]types.FramePair = undefined,
162 left_storage: [capacity.suffix]types.FrameRefs = undefined,
163 right_storage: [capacity.suffix]types.FrameRefs = undefined,
164 prefix_count: u16 = 0,
165 left_count: u16 = 0,
166 right_count: u16 = 0,
167
168 const Self = @This();
169
170 pub const capacity: types.DiffCapacity = capacity_value;
171
172 pub fn run(
173 self: *Self,
174 left: anytype,
175 right: anytype,
176 work: u32,
177 ) types.Error!types.DiffResult {
178 self.reset();
179 _ = try left.identity();
180 _ = try right.identity();
181 if (!std.meta.eql(left.start, right.start)) return error.RootStartMismatch;
182 const common: usize = @min(left.frames().len, right.frames().len);
183 var compared: u32 = 0;
184 var divergence_index: ?usize = null;
185 var divergence_reason: ?types.DivergenceReason = null;
186 for (0..common) |index| {
187 if (compared == work) {
188 return self.incomplete(compared, null, .work_budget);
189 }
190 const left_frame = left.frames()[index];
191 const right_frame = right.frames()[index];
192 compared += 1;
193 const choices_equal = std.meta.eql(
194 left_frame.decision,
195 right_frame.decision,
196 );
197 const evidence_equal = evidenceEqual(
198 try left.frameEvidence(@intCast(index)),
199 try right.frameEvidence(@intCast(index)),
200 );
201 const roots_equal = std.meta.eql(
202 left_frame.expected,
203 right_frame.expected,
204 );
205 if (choices_equal and evidence_equal and roots_equal) {
206 if (self.prefix_count == capacity.prefix) {
207 return self.incomplete(compared, null, .prefix_capacity);
208 }
209 self.prefix_storage[self.prefix_count] = .{
210 .left = try left.frameRefs(@intCast(index)),
211 .right = try right.frameRefs(@intCast(index)),
212 };
213 self.prefix_count += 1;
214 continue;
215 }
216 divergence_index = index;
217 divergence_reason = if (!choices_equal)
218 .choice
219 else if (!evidence_equal)
220 .evidence
221 else
222 .root;
223 break;
224 }
225 if (divergence_index == null and left.frames().len != right.frames().len) {
226 divergence_index = common;
227 divergence_reason = .length;
228 }
229 const divergence = if (divergence_index) |index|
230 try divergenceValue(left, right, index, divergence_reason.?)
231 else
232 null;
233 if (divergence_index) |index| {
234 const suffix_incomplete = try self.collectSuffixes(
235 left,
236 right,
237 index,
238 common,
239 work,
240 &compared,
241 );
242 if (suffix_incomplete) |reason| {
243 return self.incomplete(compared, divergence, reason);
244 }
245 }
246 if (left.traceState() == .incomplete or right.traceState() == .incomplete) {
247 return self.incomplete(compared, divergence, .source_incomplete);
248 }
249 return self.complete(compared, divergence);
250 }
251
252 fn collectSuffixes(
253 self: *Self,
254 left: anytype,
255 right: anytype,
256 first: usize,
257 common: usize,
258 work: u32,
259 compared: *u32,
260 ) types.Error!?types.DiffIncompleteReason {
261 const end = @max(left.frames().len, right.frames().len);
262 for (first..end) |index| {
263 const already_inspected = index == first and first < common;
264 if (!already_inspected) {
265 if (compared.* == work) return .work_budget;
266 compared.* += 1;
267 }
268 if (index < left.frames().len) {
269 if (self.left_count == capacity.suffix) return .suffix_capacity;
270 self.left_storage[self.left_count] = try left.frameRefs(@intCast(index));
271 self.left_count += 1;
272 }
273 if (index < right.frames().len) {
274 if (self.right_count == capacity.suffix) return .suffix_capacity;
275 self.right_storage[self.right_count] = try right.frameRefs(@intCast(index));
276 self.right_count += 1;
277 }
278 }
279 return null;
280 }
281
282 fn complete(
283 self: *const Self,
284 compared: u32,
285 divergence: ?types.Divergence,
286 ) types.DiffResult {
287 return .{
288 .prefix = self.prefix_storage[0..self.prefix_count],
289 .left_suffix = self.left_storage[0..self.left_count],
290 .right_suffix = self.right_storage[0..self.right_count],
291 .divergence = divergence,
292 .compared = compared,
293 .completion = .complete,
294 };
295 }
296
297 fn incomplete(
298 self: *const Self,
299 compared: u32,
300 divergence: ?types.Divergence,
301 reason: types.DiffIncompleteReason,
302 ) types.DiffResult {
303 var result = self.complete(compared, divergence);
304 result.completion = .{ .incomplete = reason };
305 return result;
306 }
307
308 fn reset(self: *Self) void {
309 self.prefix_count = 0;
310 self.left_count = 0;
311 self.right_count = 0;
312 }
313 };
314 }
315
316 fn evidenceEqual(left: []const types.Evidence, right: []const types.Evidence) bool {
317 if (left.len != right.len) return false;
318 for (left, right) |left_record, right_record| {
319 if (!std.meta.eql(left_record, right_record)) return false;
320 }
321 return true;
322 }
323
324 fn divergenceValue(
325 left: anytype,
326 right: anytype,
327 index: usize,
328 reason: types.DivergenceReason,
329 ) types.Error!types.Divergence {
330 const left_refs = if (index < left.frames().len)
331 try left.frameRefs(@intCast(index))
332 else
333 null;
334 const right_refs = if (index < right.frames().len)
335 try right.frameRefs(@intCast(index))
336 else
337 null;
338 const roots: types.RootDifference = if (left_refs != null and right_refs != null)
339 rootDifference(
340 left.frames()[index].expected,
341 right.frames()[index].expected,
342 )
343 else
344 .{};
345 return .{ .reason = reason, .left = left_refs, .right = right_refs, .roots = roots };
346 }
347
348 fn rootDifference(left: world.Moment, right: world.Moment) types.RootDifference {
349 return .{
350 .moment_digest = !std.mem.eql(u8, &left.digest, &right.digest),
351 .origin = !std.meta.eql(left.origin, right.origin),
352 .fabric_digest = !std.mem.eql(u8, &left.fabric.digest, &right.fabric.digest),
353 .contract = !std.meta.eql(
354 left.fabric.machine_contract,
355 right.fabric.machine_contract,
356 ),
357 .entry_frontier = left.fabric.entry_frontier != right.fabric.entry_frontier,
358 .admission_frontier = left.fabric.admission_frontier !=
359 right.fabric.admission_frontier,
360 .fault_frontier = left.fabric.fault_frontier != right.fabric.fault_frontier,
361 };
362 }
363
364 fn matches(pattern: types.Pattern, located: types.Located) types.Error!bool {
365 return switch (pattern) {
366 .kind => |kind| try matchesKind(kind, located),
367 .choice => |expected| matchChoice(expected, located),
368 .semantic => |expected| matchSemantic(expected, located),
369 .packet => |expected| try matchPacket(expected, located),
370 .fault => |expected| try matchFault(expected, located),
371 .effect => |expected| try matchEffect(expected, located),
372 .terminal => |expected| try matchTerminal(expected, located),
373 };
374 }
375
376 fn matchesKind(kind: types.Kind, located: types.Located) types.Error!bool {
377 if (kind == .all) return true;
378 return switch (kind) {
379 .choice => std.meta.activeTag(located.view) == .choice,
380 .root => std.meta.activeTag(located.view) == .root,
381 .semantic => recordTag(located, .semantic),
382 .transition => recordTag(located, .transition),
383 .machine => recordTag(located, .machine),
384 .scheduler => matchChoice(.{ .stream = .schedule }, located) or
385 matchSemanticClass(.schedule_choice, located),
386 .packet => try matchPacket(.{}, located),
387 .fault => try matchFault(.{}, located),
388 .effect => try matchEffect(.{}, located),
389 .terminal => try matchTerminal(.{}, located),
390 .all => unreachable,
391 };
392 }
393
394 fn matchChoice(expected: types.ChoicePattern, located: types.Located) bool {
395 return switch (located.view) {
396 .choice => |actual| expected.stream == null or
397 actual.site.stream == expected.stream.?,
398 .root, .record => false,
399 };
400 }
401
402 fn matchSemantic(expected: explore.Pattern, located: types.Located) bool {
403 return switch (located.view) {
404 .record => |record| switch (record.*) {
405 .semantic => |event| explore.matchesEvent(expected, event),
406 .transition, .machine => false,
407 },
408 .choice, .root => false,
409 };
410 }
411
412 fn matchSemanticClass(class: explore.EventClass, located: types.Located) bool {
413 return matchSemantic(.{ .event_class = class }, located);
414 }
415
416 fn recordTag(located: types.Located, comptime tag: std.meta.Tag(types.Evidence)) bool {
417 return switch (located.view) {
418 .record => |record| std.meta.activeTag(record.*) == tag,
419 .choice, .root => false,
420 };
421 }
422
423 const PacketHit = struct {
424 id: u64,
425 other: ?u64 = null,
426 action: types.PacketAction,
427 };
428
429 fn matchPacket(expected: types.PacketPattern, located: types.Located) types.Error!bool {
430 const hit = try packetHit(located) orelse return false;
431 if (expected.action != null and hit.action != expected.action.?) return false;
432 if (expected.id) |id| return hit.id == id or (hit.other != null and hit.other.? == id);
433 return true;
434 }
435
436 fn packetHit(located: types.Located) types.Error!?PacketHit {
437 return switch (located.view) {
438 .choice => |choice| packetChoice(choice.*),
439 .root => null,
440 .record => |record| switch (record.*) {
441 .semantic => |event| packetSemantic(event),
442 .machine => null,
443 .transition => |wire| packetTransition(try fabric.transition.inspect(&wire)),
444 },
445 };
446 }
447
448 fn packetChoice(choice: explore.SearchDecision) ?PacketHit {
449 return switch (choice.choice) {
450 .input => |value| switch (value.value) {
451 .packet => |id| .{ .id = id, .action = .choose },
452 else => null,
453 },
454 .schedule, .topology, .fault => null,
455 };
456 }
457
458 fn packetSemantic(event: explore.Event) ?PacketHit {
459 return switch (event.value) {
460 .controlled_input => |value| switch (value.value) {
461 .packet => |id| .{ .id = id, .action = .choose },
462 else => null,
463 },
464 else => null,
465 };
466 }
467
468 fn packetTransition(view: fabric.transition.InspectView) ?PacketHit {
469 return switch (view.value) {
470 .admission => |value| switch (value.effect) {
471 .packet_send => |packet| .{ .id = packet.id, .action = .send },
472 .packet_delivery => |id| .{ .id = id, .action = .deliver },
473 .direct => if (value.fault_value) |fault_value|
474 packetFault(fault_value)
475 else
476 null,
477 },
478 .fault => |value| packetFault(value),
479 .settlement => null,
480 };
481 }
482
483 fn packetFault(value: fabric.transition.FaultView) ?PacketHit {
484 return switch (value.kind) {
485 .packet_loss => .{ .id = value.primary, .action = .drop },
486 .packet_delay => .{ .id = value.primary, .action = .delay },
487 .packet_reorder => .{
488 .id = value.primary,
489 .other = value.secondary,
490 .action = .reorder,
491 },
492 else => null,
493 };
494 }
495
496 fn matchFault(expected: types.FaultPattern, located: types.Located) types.Error!bool {
497 const hit = try faultHit(located) orelse return false;
498 if (expected.kind != null and hit.kind != expected.kind.?) return false;
499 if (expected.choice != null and (hit.choice == null or hit.choice.? != expected.choice.?)) {
500 return false;
501 }
502 return true;
503 }
504
505 const FaultHit = struct {
506 kind: fault.Kind,
507 choice: ?fault.Choice,
508 };
509
510 fn faultHit(located: types.Located) types.Error!?FaultHit {
511 return switch (located.view) {
512 .choice => |choice| faultChoice(choice.*),
513 .root => null,
514 .record => |record| switch (record.*) {
515 .semantic => |event| faultSemantic(event),
516 .machine => null,
517 .transition => |wire| transitionFault(try fabric.transition.inspect(&wire)),
518 },
519 };
520 }
521
522 fn faultChoice(choice: explore.SearchDecision) ?FaultHit {
523 return switch (choice.choice) {
524 .fault => |value| generatedFault(value),
525 else => null,
526 };
527 }
528
529 fn faultSemantic(event: explore.Event) ?FaultHit {
530 return switch (event.value) {
531 .injected_fault => |value| generatedFault(value),
532 else => null,
533 };
534 }
535
536 fn generatedFault(value: explore.GeneratedFault) ?FaultHit {
537 return switch (value.action) {
538 .healthy => null,
539 .inject => |kind| .{ .kind = kind, .choice = .inject },
540 .persist => |kind| .{ .kind = kind, .choice = .inject },
541 .recover => |kind| .{ .kind = kind, .choice = .bypass },
542 };
543 }
544
545 fn transitionFault(view: fabric.transition.InspectView) ?FaultHit {
546 const value = switch (view.value) {
547 .fault => |fault_value| fault_value,
548 .admission => |admission_value| admission_value.fault_value orelse return null,
549 .settlement => return null,
550 };
551 return .{ .kind = value.kind, .choice = value.choice };
552 }
553
554 const EffectHit = struct {
555 correlation: ?u64,
556 phase: types.EffectPhase,
557 status: ?os.abi.EffectStatus,
558 };
559
560 fn matchEffect(expected: types.EffectPattern, located: types.Located) types.Error!bool {
561 const hit = try effectHit(located) orelse return false;
562 if (expected.phase != null and hit.phase != expected.phase.?) return false;
563 if (expected.correlation != null and
564 (hit.correlation == null or hit.correlation.? != expected.correlation.?))
565 {
566 return false;
567 }
568 if (expected.status != null and (hit.status == null or hit.status.? != expected.status.?)) {
569 return false;
570 }
571 return true;
572 }
573
574 fn effectHit(located: types.Located) types.Error!?EffectHit {
575 return switch (located.view) {
576 .choice => |choice| effectChoice(choice.*),
577 .root => null,
578 .record => |record| switch (record.*) {
579 .semantic => |event| effectSemantic(event),
580 .machine => |wire| try effectMachine(&wire),
581 .transition => |wire| effectTransition(try fabric.transition.inspect(&wire)),
582 },
583 };
584 }
585
586 fn effectChoice(choice: explore.SearchDecision) ?EffectHit {
587 return switch (choice.choice) {
588 .input => |value| switch (value.value) {
589 .service_result, .effect_result => .{
590 .correlation = null,
591 .phase = .choice,
592 .status = null,
593 },
594 else => null,
595 },
596 else => null,
597 };
598 }
599
600 fn effectSemantic(event: explore.Event) ?EffectHit {
601 return switch (event.value) {
602 .operation => .{ .correlation = null, .phase = .operation, .status = null },
603 .controlled_input => |value| switch (value.value) {
604 .service_result, .effect_result => .{
605 .correlation = null,
606 .phase = .choice,
607 .status = null,
608 },
609 else => null,
610 },
611 else => null,
612 };
613 }
614
615 fn effectMachine(wire: *const os.abi.MessageWire) types.Error!?EffectHit {
616 const event = try os.abi.decodeEvent(wire);
617 return switch (event.value) {
618 .effect_request => .{
619 .correlation = event.header.correlation,
620 .phase = .request,
621 .status = null,
622 },
623 else => null,
624 };
625 }
626
627 fn effectTransition(view: fabric.transition.InspectView) ?EffectHit {
628 return switch (view.value) {
629 .admission => |value| switch (value.record) {
630 .effect_result => |result| .{
631 .correlation = result.correlation,
632 .phase = .result,
633 .status = result.status,
634 },
635 else => null,
636 },
637 .settlement, .fault => null,
638 };
639 }
640
641 const TerminalHit = struct {
642 direction: types.TerminalDirection,
643 offset: ?u64,
644 };
645
646 fn matchTerminal(
647 expected: types.TerminalPattern,
648 located: types.Located,
649 ) types.Error!bool {
650 const hit = try terminalHit(located) orelse return false;
651 if (expected.direction != .either and hit.direction != expected.direction) {
652 return false;
653 }
654 if (expected.offset != null and (hit.offset == null or hit.offset.? != expected.offset.?)) {
655 return false;
656 }
657 return true;
658 }
659
660 fn terminalHit(located: types.Located) types.Error!?TerminalHit {
661 return switch (located.view) {
662 .choice => |choice| terminalChoice(choice.*),
663 .root => null,
664 .record => |record| switch (record.*) {
665 .semantic => |event| terminalSemantic(event),
666 .machine => |wire| try terminalMachine(&wire),
667 .transition => |wire| terminalTransition(try fabric.transition.inspect(&wire)),
668 },
669 };
670 }
671
672 fn terminalChoice(choice: explore.SearchDecision) ?TerminalHit {
673 return switch (choice.choice) {
674 .input => |value| switch (value.value) {
675 .terminal => .{ .direction = .input, .offset = null },
676 else => null,
677 },
678 else => null,
679 };
680 }
681
682 fn terminalSemantic(event: explore.Event) ?TerminalHit {
683 return switch (event.value) {
684 .controlled_input => |value| switch (value.value) {
685 .terminal => .{ .direction = .input, .offset = null },
686 else => null,
687 },
688 else => null,
689 };
690 }
691
692 fn terminalMachine(wire: *const os.abi.MessageWire) types.Error!?TerminalHit {
693 const event = try os.abi.decodeEvent(wire);
694 return switch (event.value) {
695 .terminal_bytes => |value| .{ .direction = .output, .offset = value.offset },
696 else => null,
697 };
698 }
699
700 fn terminalTransition(view: fabric.transition.InspectView) ?TerminalHit {
701 return switch (view.value) {
702 .admission => |value| switch (value.record) {
703 .terminal => |terminal| .{ .direction = .input, .offset = terminal.offset },
704 else => null,
705 },
706 .settlement, .fault => null,
707 };
708 }