lib/reticulum/src/node/fixture/world.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const reticulum = @import("../../root.zig");
3
4 const carrier = reticulum.carrier;
5 const node = reticulum.node;
6 const packet = reticulum.packet;
7
8 pub const Seconds = node.Seconds;
9
10 /// The world's three nodes, with B between A and C as the one that carries traffic for the other
11 /// two.
12 pub const NodeId = enum(u2) { a, b, c };
13
14 /// The four one-way links between neighboring nodes. Within one second the world drains them in
15 /// the order they are written here.
16 pub const LinkId = enum(u2) { a_to_b, b_to_a, b_to_c, c_to_b };
17
18 const Wire = struct {
19 source: NodeId,
20 source_carrier: carrier.Index,
21 target: NodeId,
22 target_carrier: carrier.Index,
23 };
24
25 const wires = [_]Wire{
26 .{ .source = .a, .source_carrier = 0, .target = .b, .target_carrier = 0 },
27 .{ .source = .b, .source_carrier = 0, .target = .a, .target_carrier = 0 },
28 .{ .source = .b, .source_carrier = 1, .target = .c, .target_carrier = 0 },
29 .{ .source = .c, .source_carrier = 0, .target = .b, .target_carrier = 1 },
30 };
31
32 /// The entry maxima each of the world's nodes runs under. Every node holds two carriers, so B sits
33 /// between A and C at the same time.
34 pub const limits = node.Limits{
35 .interfaces_max = 2,
36 .destinations_max = 1,
37 .known_identities_max = 2,
38 .known_ratchets_max = 1,
39 .receipts_max = 2,
40 .duplicate_hashes_max = 32,
41 .timers_max = 4,
42 .effects_max = 8,
43 .effect_frames_max = 4,
44 .paths_max = 2,
45 .announces_max = 2,
46 .reverse_entries_max = 2,
47 .path_request_tags_max = 8,
48 .inflight_requests_max = 2,
49 .discoveries_max = 2,
50 .links_max = 2,
51 .link_entries_max = 2,
52 };
53
54 const node_count: usize = 3;
55
56 pub const frames_max: usize = 8;
57 pub const faults_max: usize = 4;
58 pub const deliveries_max: usize = 48;
59 pub const records_max: usize = 128;
60 /// The most timers the world tracks, the timer maximum of one node for each of the three. A timer
61 /// leaves the world's own record once the world applies the step in which its node cancelled it.
62 pub const timers_max: usize = node_count * limits.timers_max;
63 pub const settle_steps_max: usize = 64;
64
65 const node_capacity = node.Capacity.derive(limits) catch unreachable;
66 const link_limits = carrier.Memory.Limits{ .frames_max = frames_max };
67 const link_capacity = carrier.Memory.Capacity.derive(link_limits) catch unreachable;
68
69 const NodeRegion = struct {
70 bytes: [node_capacity.storage_bytes]u8 align(8) = undefined,
71 };
72
73 const LinkRegion = struct {
74 bytes: [link_capacity.storage_bytes]u8 align(8) = undefined,
75 };
76
77 /// One scripted failure on one directed link. Three of the four identify a frame by ordinal, the
78 /// number of frames that link was offered ahead of it, counted from 0, with the frames the link
79 /// loses counted in. Every frame a fault names is one the link has yet to be offered. Departure
80 /// follows the delivery second, and two frames due in one second depart by place. A frame's place
81 /// is its ordinal until a swap trades it.
82 pub const Fault = union(enum) {
83 /// The link drops the frame sitting at this ordinal.
84 drop: u32,
85 /// The frame sitting at this ordinal departs `seconds` later than the second that offered it. A
86 /// swap leaves this delivery second with its own frame.
87 delay: struct { ordinal: u32, seconds: Seconds },
88 /// The two frames at ordinals `first` and `second` exchange their places on the single occasion
89 /// when both sit in the queue, so a frame that left or was lost first blocks the swap. A
90 /// delivery second stays with its frame through the exchange, and a place moves.
91 swap: struct { first: u32, second: u32 },
92 /// The link drops each frame it was offered in the seconds `from` up to `until`, with both of
93 /// those seconds inside the span.
94 partition: struct { from: Seconds, until: Seconds },
95 };
96
97 /// The access codes for the A to B link and the B to C link.
98 pub const Codes = struct {
99 a_b: ?node.Access = null,
100 b_c: ?node.Access = null,
101 };
102
103 /// Fixed step entropy for one node. Reticulum@1.5.0 draws these bytes at random
104 /// (RNS/Link.py:276,435-437,763), so a world that compares recorded frames has to replay the
105 /// bytes the recording drew. A node left null draws the world's counter entropy instead.
106 pub const Entropy = struct {
107 a: ?[32]u8 = null,
108 b: ?[32]u8 = null,
109 c: ?[32]u8 = null,
110
111 fn forNode(self: Entropy, id: NodeId) ?[32]u8 {
112 return switch (id) {
113 .a => self.a,
114 .b => self.b,
115 .c => self.c,
116 };
117 }
118 };
119
120 pub const Options = struct {
121 start: Seconds,
122 transport_hash: [16]u8,
123 codes: Codes = .{},
124 discover_paths: ?carrier.Index = null,
125 entropy: Entropy = .{},
126 };
127
128 /// One directed link, holding a queue of at most eight frames, the second each is due, and its
129 /// scripted faults. The link counts the frames it was offered and the frames it lost.
130 pub const Link = struct {
131 queue: carrier.Memory,
132 due: [frames_max]Seconds = @splat(0),
133 order: [frames_max]u32 = @splat(0),
134 /// Each queued frame's tie-break among the frames due in the same second. A place starts out as
135 /// the frame's ordinal, a swap trades it, and it travels with the frame when the queue rotates.
136 place: [frames_max]u32 = @splat(0),
137 faults: [faults_max]Fault = @splat(.{ .drop = std.math.maxInt(u32) }),
138 consumed: [faults_max]bool = @splat(false),
139 fault_count: usize = 0,
140 offered: u32 = 0,
141 dropped: u32 = 0,
142
143 pub fn fault(self: *Link, value: Fault) void {
144 std.debug.assert(self.fault_count < faults_max);
145 switch (value) {
146 .drop => |ordinal| std.debug.assert(ordinal >= self.offered),
147 .delay => |late| std.debug.assert(late.ordinal >= self.offered),
148 .swap => |pair| {
149 std.debug.assert(pair.first != pair.second);
150 std.debug.assert(@min(pair.first, pair.second) >= self.offered);
151 },
152 .partition => |window| std.debug.assert(window.from <= window.until),
153 }
154 self.faults[self.fault_count] = value;
155 self.consumed[self.fault_count] = false;
156 self.fault_count += 1;
157 }
158 };
159
160 /// The effect kinds the world logs beside the carrier frames it carries.
161 pub const Kind = enum {
162 delivery,
163 announce,
164 path_request,
165 receipt,
166 diagnostic,
167 timer,
168 link_requested,
169 link_established,
170 link_delivery,
171 link_closed,
172 };
173
174 /// What a timer record names.
175 pub const Tag = enum(u8) { receipt, hashlist, announces, link, link_entries };
176
177 pub const payload_bytes_max: usize = 32;
178
179 const DeliveryEffect = @FieldType(node.Effect, "application_delivery");
180 const LinkDeliveryEffect = @FieldType(node.Effect, "link_delivery");
181
182 pub const Record = struct {
183 at: Seconds,
184 owner: NodeId,
185 kind: Kind,
186 interface: carrier.Index = 0,
187 key: [16]u8 = @splat(0),
188 hops: u8 = 0,
189 tag: Tag = .receipt,
190 deadline: Seconds = 0,
191 path_response: bool = false,
192 proof_requested: bool = false,
193 code: ?node.Code = null,
194 status: ?packet.receipt.Status = null,
195 role: ?node.LinkRole = null,
196 reason: ?node.LinkCloseReason = null,
197 payload: [payload_bytes_max]u8 = @splat(0),
198 payload_len: u8 = 0,
199
200 pub fn plaintext(self: *const Record) []const u8 {
201 std.debug.assert(self.payload_len <= payload_bytes_max);
202 return self.payload[0..self.payload_len];
203 }
204 };
205
206 pub const Delivery = struct {
207 at: Seconds,
208 link: LinkId,
209 ordinal: u32,
210 frame: carrier.Frame,
211 };
212
213 const Scheduled = struct {
214 owner: NodeId,
215 id: node.TimerId,
216 at: Seconds,
217 };
218
219 pub const Error = error{WorldDidNotSettle} || node.StepError || carrier.Frame.InitError ||
220 carrier.Memory.Exhaustion || carrier.Memory.InitError || node.Capacity.DeriveError ||
221 error{Index};
222
223 /// Three nodes joined by four one-way links, with one clock, the frame queues, the timer copies,
224 /// and the log. The caller initializes this value in place, because each node holds slices that
225 /// point into the world's storage.
226 pub const World = struct {
227 clock: Seconds = 0,
228 nodes: [node_count]node.Node = undefined,
229 links: [4]Link = undefined,
230 timers: [timers_max]Scheduled = undefined,
231 timer_count: usize = 0,
232 deliveries: [deliveries_max]Delivery = undefined,
233 delivery_count: usize = 0,
234 log: [records_max]Record = undefined,
235 record_count: usize = 0,
236 entropy_count: u64 = 0,
237 entropy: Entropy = .{},
238 regions: [node_count]NodeRegion = undefined,
239 link_regions: [4]LinkRegion = undefined,
240
241 pub fn init(self: *World, options: Options) Error!void {
242 self.clock = options.start;
243 self.timer_count = 0;
244 self.delivery_count = 0;
245 self.record_count = 0;
246 self.entropy_count = 0;
247 self.entropy = options.entropy;
248 for (&self.nodes, &self.regions) |*owner, *region| {
249 owner.* = try node.Node.init(®ion.bytes, limits);
250 owner.activate();
251 }
252 for (&self.links, &self.link_regions) |*link, *region| {
253 link.* = .{
254 .queue = try carrier.Memory.init(®ion.bytes, link_limits),
255 };
256 link.queue.activate();
257 }
258 try self.register(options);
259 std.debug.assert(self.clock == options.start);
260 }
261
262 fn register(self: *World, options: Options) Error!void {
263 try self.at(.a).registerCarrier(0, true, options.codes.a_b);
264 try self.at(.b).registerCarrier(0, true, options.codes.a_b);
265 try self.at(.b).registerCarrier(1, true, options.codes.b_c);
266 try self.at(.c).registerCarrier(0, true, options.codes.b_c);
267 self.at(.b).setTransport(options.transport_hash, true);
268 if (options.discover_paths) |index| try self.at(.b).setPathDiscovery(index, true);
269 }
270
271 pub fn deinit(self: *World) void {
272 for (&self.links) |*link| _ = link.queue.deinit();
273 for (&self.nodes) |*owner| _ = owner.deinit();
274 }
275
276 pub fn at(self: *World, id: NodeId) *node.Node {
277 return &self.nodes[@backingInt(id)];
278 }
279
280 pub fn linkAt(self: *World, id: LinkId) *Link {
281 return &self.links[@backingInt(id)];
282 }
283
284 /// Applies one caller event to one node at the current second and settles what follows.
285 pub fn step(self: *World, id: NodeId, value: node.Event) Error!void {
286 try self.apply(id, try self.at(id).step(value));
287 try self.settle();
288 }
289
290 /// Runs each second that falls due through the target second, and leaves the clock at the
291 /// target. A world that has not quieted down after sixty-four rounds returns
292 /// `error.WorldDidNotSettle`.
293 pub fn runTo(self: *World, target: Seconds) Error!void {
294 std.debug.assert(target >= self.clock);
295 var steps: usize = 0;
296 while (steps < settle_steps_max) : (steps += 1) {
297 const due = self.nextDue() orelse break;
298 if (due > target) break;
299 self.clock = @max(self.clock, due);
300 try self.settle();
301 }
302 if (steps == settle_steps_max) return error.WorldDidNotSettle;
303 self.clock = target;
304 }
305
306 pub fn frameCount(self: *const World, id: LinkId) usize {
307 var count: usize = 0;
308 for (self.deliveries[0..self.delivery_count]) |delivery| {
309 if (delivery.link == id) count += 1;
310 }
311 return count;
312 }
313
314 pub fn frameOn(self: *const World, id: LinkId, index: usize) ?*const Delivery {
315 var seen: usize = 0;
316 for (self.deliveries[0..self.delivery_count]) |*delivery| {
317 if (delivery.link != id) continue;
318 if (seen == index) return delivery;
319 seen += 1;
320 }
321 return null;
322 }
323
324 pub fn timerCount(self: *const World, id: NodeId) usize {
325 std.debug.assert(self.timer_count <= timers_max);
326 var count: usize = 0;
327 for (self.timers[0..self.timer_count]) |entry| {
328 if (entry.owner == id) count += 1;
329 }
330 return count;
331 }
332
333 pub fn records(self: *const World) []const Record {
334 std.debug.assert(self.record_count <= records_max);
335 return self.log[0..self.record_count];
336 }
337
338 pub fn recordCount(self: *const World, id: NodeId, kind: Kind) usize {
339 var count: usize = 0;
340 for (self.records()) |record| {
341 if (record.owner == id and record.kind == kind) count += 1;
342 }
343 return count;
344 }
345
346 pub fn lastRecord(self: *const World, id: NodeId, kind: Kind) ?Record {
347 var found: ?Record = null;
348 for (self.records()) |record| {
349 if (record.owner == id and record.kind == kind) found = record;
350 }
351 return found;
352 }
353
354 fn settle(self: *World) Error!void {
355 var steps: usize = 0;
356 while (steps < settle_steps_max) : (steps += 1) {
357 const moved = try self.deliverDue();
358 const fired = try self.fireDue();
359 if (!moved and !fired) return;
360 }
361 return error.WorldDidNotSettle;
362 }
363
364 fn nextDue(self: *const World) ?Seconds {
365 var best: ?Seconds = null;
366 for (&self.links) |*link| {
367 var offset: usize = 0;
368 while (offset < link.queue.len) : (offset += 1) {
369 const slot = (link.queue.start + offset) % frames_max;
370 best = if (best) |value| @min(value, link.due[slot]) else link.due[slot];
371 }
372 }
373 for (self.timers[0..self.timer_count]) |entry| {
374 best = if (best) |value| @min(value, entry.at) else entry.at;
375 }
376 return best;
377 }
378
379 fn deliverDue(self: *World) Error!bool {
380 var moved = false;
381 for (&self.links, 0..) |*link, index| {
382 var pending = frames_max;
383 while (pending > 0) : (pending -= 1) {
384 const offset = dueOffset(link, self.clock) orelse break;
385 var spins: usize = 0;
386 while (spins < offset) : (spins += 1) rotate(link);
387 std.debug.assert(link.queue.len >= 1);
388 std.debug.assert(link.due[link.queue.start] <= self.clock);
389 const order = link.order[link.queue.start];
390 const frame = link.queue.pop() orelse unreachable;
391 self.keep(@fromBackingInt(@intCast(index)), order, frame);
392 try self.arrive(@fromBackingInt(@intCast(index)), frame);
393 moved = true;
394 }
395 }
396 return moved;
397 }
398
399 fn arrive(self: *World, id: LinkId, frame: carrier.Frame) Error!void {
400 const target = wires[@backingInt(id)];
401 const effects = try self.at(target.target).step(.{ .carrier_frame = .{
402 .interface = target.target_carrier,
403 .now = self.clock,
404 .bytes = frame.slice(),
405 .entropy = self.entropyFor(target.target),
406 } });
407 try self.apply(target.target, effects);
408 }
409
410 fn fireDue(self: *World) Error!bool {
411 var chosen: ?usize = null;
412 for (self.timers[0..self.timer_count], 0..) |entry, index| {
413 if (entry.at > self.clock) continue;
414 if (chosen == null or before(entry, self.timers[chosen.?])) chosen = index;
415 }
416 const index = chosen orelse return false;
417 const entry = self.timers[index];
418 self.timer_count -= 1;
419 self.timers[index] = self.timers[self.timer_count];
420 const effects = try self.at(entry.owner).step(.{ .timer_expired = .{
421 .id = entry.id,
422 .now = self.clock,
423 .entropy = self.entropyFor(entry.owner),
424 } });
425 try self.apply(entry.owner, effects);
426 return true;
427 }
428
429 fn entropyFor(self: *World, id: NodeId) [32]u8 {
430 if (self.entropy.forNode(id)) |fixed| return fixed;
431 return self.nextEntropy();
432 }
433
434 fn nextEntropy(self: *World) [32]u8 {
435 var counter: [8]u8 = undefined;
436 std.mem.writeInt(u64, &counter, self.entropy_count, .little);
437 self.entropy_count += 1;
438 var entropy: [32]u8 = undefined;
439 std.crypto.hash.sha2.Sha256.hash(&counter, &entropy, .{});
440 return entropy;
441 }
442
443 fn apply(self: *World, id: NodeId, effects: []const node.Effect) Error!void {
444 self.forget(id);
445 for (effects) |effect| switch (effect) {
446 .carrier_send => |send| try self.offer(id, send.interface, send.frame),
447 .schedule_timer => |scheduled| {
448 self.schedule(id, scheduled.id, scheduled.at);
449 self.note(.{
450 .at = self.clock,
451 .owner = id,
452 .kind = .timer,
453 .tag = tagOf(scheduled.id),
454 .deadline = scheduled.at,
455 });
456 },
457 .application_delivery => |delivery| self.note(delivered(self.clock, id, delivery)),
458 .announce_received => |announce| self.note(.{
459 .at = self.clock,
460 .owner = id,
461 .kind = .announce,
462 .key = announce.destination_hash,
463 .hops = announce.hops,
464 .path_response = announce.path_response,
465 }),
466 .path_request => |request| self.note(.{
467 .at = self.clock,
468 .owner = id,
469 .kind = .path_request,
470 .interface = request.interface,
471 .key = request.destination,
472 }),
473 .receipt_update => |update| self.note(.{
474 .at = self.clock,
475 .owner = id,
476 .kind = .receipt,
477 .key = update.packet_hash[0..16].*,
478 .status = update.status,
479 }),
480 .diagnostic => |value| self.note(.{
481 .at = self.clock,
482 .owner = id,
483 .kind = .diagnostic,
484 .code = value.code,
485 }),
486 .link_requested => |requested| self.note(.{
487 .at = self.clock,
488 .owner = id,
489 .kind = .link_requested,
490 .key = requested.link_id,
491 }),
492 .link_established => |established| self.note(.{
493 .at = self.clock,
494 .owner = id,
495 .kind = .link_established,
496 .interface = established.interface,
497 .key = established.link_id,
498 .role = established.role,
499 }),
500 .link_delivery => |delivery| self.note(linkDelivered(self.clock, id, delivery)),
501 .link_closed => |closed| self.note(.{
502 .at = self.clock,
503 .owner = id,
504 .kind = .link_closed,
505 .key = closed.link_id,
506 .reason = closed.reason,
507 }),
508 .persist => {},
509 };
510 }
511
512 fn offer(self: *World, id: NodeId, interface: carrier.Index, frame: []const u8) Error!void {
513 std.debug.assert(frame.len >= 1);
514 const index = wireOf(id, interface);
515 const link = &self.links[index];
516 const ordinal = link.offered;
517 link.offered += 1;
518 var due = self.clock;
519 var blocked = false;
520 for (link.faults[0..link.fault_count]) |value| switch (value) {
521 .drop => |lost| blocked = blocked or lost == ordinal,
522 .delay => |late| if (late.ordinal == ordinal) {
523 due = self.clock +| late.seconds;
524 },
525 .partition => |window| {
526 const inside = self.clock >= window.from and self.clock <= window.until;
527 blocked = blocked or inside;
528 },
529 .swap => {},
530 };
531 if (blocked) {
532 link.dropped += 1;
533 return;
534 }
535 const slot = (link.queue.start + link.queue.len) % frames_max;
536 try link.queue.push(try carrier.Frame.init(frame));
537 link.due[slot] = due;
538 link.order[slot] = ordinal;
539 link.place[slot] = ordinal;
540 swapQueued(link);
541 }
542
543 fn schedule(self: *World, id: NodeId, timer_id: node.TimerId, due: Seconds) void {
544 std.debug.assert(self.at(id).timers.contains(timer_id));
545 for (self.timers[0..self.timer_count]) |*entry| {
546 if (entry.owner != id) continue;
547 if (!entry.id.eql(timer_id)) continue;
548 entry.at = due;
549 return;
550 }
551 std.debug.assert(self.timer_count < timers_max);
552 self.timers[self.timer_count] = .{ .owner = id, .id = timer_id, .at = due };
553 self.timer_count += 1;
554 std.debug.assert(self.timerCount(id) <= limits.timers_max);
555 }
556
557 /// Drops the world's copies of the timers that node has dropped, and keeps the rest in order.
558 /// Cancelling a receipt timer produces no effect that announces it, and a node cancels one on
559 /// two occasions: a proof concluding the receipt, and a newer receipt culling it. The world
560 /// makes this call once a node's step returns, holding that step's effects until afterwards, so
561 /// it spares a timer the step armed.
562 fn forget(self: *World, id: NodeId) void {
563 const owner = self.at(id);
564 var index: usize = 0;
565 for (0..timers_max) |_| {
566 if (index == self.timer_count) break;
567 const entry = self.timers[index];
568 if (entry.owner == id and !owner.timers.contains(entry.id)) {
569 std.mem.copyForwards(
570 Scheduled,
571 self.timers[index .. self.timer_count - 1],
572 self.timers[index + 1 .. self.timer_count],
573 );
574 self.timer_count -= 1;
575 } else {
576 index += 1;
577 }
578 }
579 std.debug.assert(index == self.timer_count);
580 std.debug.assert(self.timerCount(id) <= owner.timers.count());
581 }
582
583 fn note(self: *World, value: Record) void {
584 std.debug.assert(self.record_count < records_max);
585 self.log[self.record_count] = value;
586 self.record_count += 1;
587 }
588
589 fn keep(self: *World, id: LinkId, ordinal: u32, frame: carrier.Frame) void {
590 std.debug.assert(self.delivery_count < deliveries_max);
591 self.deliveries[self.delivery_count] = .{
592 .at = self.clock,
593 .link = id,
594 .ordinal = ordinal,
595 .frame = frame,
596 };
597 self.delivery_count += 1;
598 }
599 };
600
601 fn delivered(
602 at: Seconds,
603 id: NodeId,
604 value: DeliveryEffect,
605 ) Record {
606 var record = Record{
607 .at = at,
608 .owner = id,
609 .kind = .delivery,
610 .interface = value.interface,
611 .key = value.destination,
612 .proof_requested = value.proof_requested,
613 };
614 const length = @min(value.plaintext.len, payload_bytes_max);
615 @memcpy(record.payload[0..length], value.plaintext[0..length]);
616 record.payload_len = @intCast(length);
617 return record;
618 }
619
620 fn linkDelivered(
621 at: Seconds,
622 id: NodeId,
623 value: LinkDeliveryEffect,
624 ) Record {
625 var record = Record{
626 .at = at,
627 .owner = id,
628 .kind = .link_delivery,
629 .key = value.link_id,
630 .proof_requested = value.proof_requested,
631 };
632 const length = @min(value.plaintext.len, payload_bytes_max);
633 @memcpy(record.payload[0..length], value.plaintext[0..length]);
634 record.payload_len = @intCast(length);
635 return record;
636 }
637
638 fn wireOf(id: NodeId, interface: carrier.Index) usize {
639 for (wires, 0..) |wire, index| {
640 if (wire.source != id) continue;
641 if (wire.source_carrier != interface) continue;
642 return index;
643 }
644 unreachable;
645 }
646
647 fn before(left: Scheduled, right: Scheduled) bool {
648 if (left.at != right.at) return left.at < right.at;
649 const left_owner = @backingInt(left.owner);
650 const right_owner = @backingInt(right.owner);
651 if (left_owner != right_owner) return left_owner < right_owner;
652 return @backingInt(tagOf(left.id)) < @backingInt(tagOf(right.id));
653 }
654
655 fn tagOf(id: node.TimerId) Tag {
656 return switch (id) {
657 .receipt => .receipt,
658 .hashlist => .hashlist,
659 .announces => .announces,
660 .link => .link,
661 .link_entries => .link_entries,
662 };
663 }
664
665 /// Says whether the frame in one queue slot leaves before the frame in another. A smaller delivery
666 /// second orders ahead of a larger one, and two frames sharing a second order by the smaller place.
667 /// Two queued frames always hold different places.
668 fn leavesBefore(link: *const Link, left: usize, right: usize) bool {
669 if (link.due[left] != link.due[right]) return link.due[left] < link.due[right];
670 std.debug.assert(link.place[left] != link.place[right]);
671 return link.place[left] < link.place[right];
672 }
673
674 /// Answers with the offset in the queue of the frame that departs next among those due at the given
675 /// second or earlier. A link with nothing due gives null. A tie within one second goes to the lower
676 /// place, because rotations leave the queue offsets out of arrival order.
677 fn dueOffset(link: *const Link, now: Seconds) ?usize {
678 var chosen: ?usize = null;
679 var offset: usize = 0;
680 while (offset < link.queue.len) : (offset += 1) {
681 const slot = (link.queue.start + offset) % frames_max;
682 if (link.due[slot] > now) continue;
683 const best = chosen orelse {
684 chosen = offset;
685 continue;
686 };
687 const best_slot = (link.queue.start + best) % frames_max;
688 if (leavesBefore(link, slot, best_slot)) chosen = offset;
689 }
690 return chosen;
691 }
692
693 /// Takes the frame at the head of the queue to its tail, and the delivery second, ordinal, and
694 /// place travel with it.
695 fn rotate(link: *Link) void {
696 std.debug.assert(link.queue.len >= 1);
697 const due = link.due[link.queue.start];
698 const order = link.order[link.queue.start];
699 const place = link.place[link.queue.start];
700 const frame = link.queue.pop() orelse unreachable;
701 const target = (link.queue.start + link.queue.len) % frames_max;
702 link.queue.push(frame) catch unreachable;
703 link.due[target] = due;
704 link.order[target] = order;
705 link.place[target] = place;
706 }
707
708 fn queuedIndex(link: *const Link, ordinal: u32) ?usize {
709 var offset: usize = 0;
710 while (offset < link.queue.len) : (offset += 1) {
711 const slot = (link.queue.start + offset) % frames_max;
712 if (link.order[slot] == ordinal) return slot;
713 }
714 return null;
715 }
716
717 /// Finds each swap that has yet to fire with both of its frames in the queue, exchanges the places
718 /// of those two frames, and records the swap as done. The frames, their ordinals, and their
719 /// delivery seconds stay in their slots.
720 fn swapQueued(link: *Link) void {
721 for (link.faults[0..link.fault_count], 0..) |value, index| {
722 const pair = switch (value) {
723 .swap => |fields| fields,
724 else => continue,
725 };
726 if (link.consumed[index]) continue;
727 const left = queuedIndex(link, pair.first) orelse continue;
728 const right = queuedIndex(link, pair.second) orelse continue;
729 std.debug.assert(left != right);
730 std.mem.swap(u32, &link.place[left], &link.place[right]);
731 link.consumed[index] = true;
732 }
733 }