lib/choir/src/core/context/resources.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Operation = @import("../root.zig").Operation;
3
4 pub const Tracker = struct {
5 next_value_id: u32,
6 next_operation_id: u31,
7 operation_head: ?*Operation,
8 operation_count: usize,
9
10 pub fn init() Tracker {
11 return .{
12 .next_value_id = 0,
13 .next_operation_id = 0,
14 .operation_head = null,
15 .operation_count = 0,
16 };
17 }
18
19 pub fn deinit(self: *Tracker) void {
20 var current = self.operation_head;
21 var remaining = self.operation_count;
22 while (remaining > 0) : (remaining -|= 1) {
23 const op = current.?;
24 op.dropAllReferences();
25 current = op.tracking_next;
26 }
27
28 while (self.operation_head) |op| {
29 std.debug.assert(op.hasNoUses());
30 const removed = self.removeOperation(op);
31 std.debug.assert(removed);
32 op.destroy();
33 }
34 std.debug.assert(self.operation_count == 0);
35 }
36
37 fn containsOperation(self: *const Tracker, expected: *const Operation) bool {
38 var current = self.operation_head;
39 var remaining = self.operation_count;
40 while (remaining > 0) : (remaining -|= 1) {
41 const op = current.?;
42 if (op == expected) return true;
43 current = op.tracking_next;
44 }
45 return false;
46 }
47
48 fn appendOperation(self: *Tracker, op: *Operation) void {
49 std.debug.assert(op.tracking_prev == null);
50 std.debug.assert(op.tracking_next == null);
51 std.debug.assert(self.next_operation_id < std.math.maxInt(u31));
52 std.debug.assert(self.operation_count < std.math.maxInt(usize));
53
54 op.setCreationId(self.next_operation_id);
55 self.next_operation_id = std.math.add(u31, self.next_operation_id, 1) catch unreachable;
56
57 if (self.operation_head) |head| {
58 const tail = head.tracking_prev.?;
59 op.tracking_prev = tail;
60 op.tracking_next = head;
61 tail.tracking_next = op;
62 head.tracking_prev = op;
63 } else {
64 op.tracking_prev = op;
65 op.tracking_next = op;
66 self.operation_head = op;
67 }
68 self.operation_count = std.math.add(usize, self.operation_count, 1) catch unreachable;
69 }
70
71 fn removeOperation(self: *Tracker, op: *Operation) bool {
72 const previous = op.tracking_prev orelse {
73 std.debug.assert(op.tracking_next == null);
74 return false;
75 };
76 const next = op.tracking_next.?;
77 std.debug.assert(self.operation_count > 0);
78
79 if (previous == op) {
80 std.debug.assert(next == op);
81 std.debug.assert(self.operation_head == op);
82 std.debug.assert(self.operation_count == 1);
83 self.operation_head = null;
84 } else {
85 std.debug.assert(next != op);
86 previous.tracking_next = next;
87 next.tracking_prev = previous;
88 if (self.operation_head == op) self.operation_head = next;
89 }
90
91 op.tracking_prev = null;
92 op.tracking_next = null;
93 self.operation_count = std.math.sub(usize, self.operation_count, 1) catch unreachable;
94 return true;
95 }
96 };
97
98 pub fn allocateValueId(ctx: anytype) u32 {
99 const id = ctx.resources.next_value_id;
100 std.debug.assert(id < std.math.maxInt(u32));
101 ctx.resources.next_value_id = std.math.add(u32, id, 1) catch unreachable;
102 return id;
103 }
104
105 pub fn operationCount(ctx: anytype) usize {
106 return ctx.resources.operation_count;
107 }
108
109 pub fn operationCreationBoundary(ctx: anytype) u31 {
110 return ctx.resources.next_operation_id;
111 }
112
113 pub fn eraseOperationsCreatedSince(ctx: anytype, boundary: u31) void {
114 while (ctx.resources.operation_head) |head| {
115 const operation = head.tracking_prev.?;
116 if (operation.createdBefore(boundary)) return;
117 operation.erase();
118 }
119 }
120
121 pub fn containsOperation(ctx: anytype, op: *const Operation) bool {
122 return ctx.resources.containsOperation(op);
123 }
124
125 pub fn trackOperation(ctx: anytype, op: *Operation) void {
126 std.debug.assert(@intFromPtr(op.context) == @intFromPtr(ctx));
127 ctx.resources.appendOperation(op);
128 }
129
130 pub fn untrackOperation(ctx: anytype, op: *Operation) void {
131 if (@intFromPtr(op.context) != @intFromPtr(ctx)) return;
132 _ = ctx.resources.removeOperation(op);
133 }
134
135 const FakeContext = struct {
136 resources: Tracker = Tracker.init(),
137 };
138
139 test "resources allocate monotonically increasing value ids" {
140 const testing = std.testing;
141 var ctx = FakeContext{};
142
143 try testing.expectEqual(@as(u32, 0), allocateValueId(&ctx));
144 try testing.expectEqual(@as(u32, 1), allocateValueId(&ctx));
145 try testing.expectEqual(@as(u32, 2), ctx.resources.next_value_id);
146 }
147
148 test "operation creation boundary excludes later operations" {
149 const testing = std.testing;
150 var tracker = Tracker.init();
151
152 var first: Operation = undefined;
153 first.tracking_prev = null;
154 first.tracking_next = null;
155 tracker.appendOperation(&first);
156
157 const boundary = tracker.next_operation_id;
158
159 var second: Operation = undefined;
160 second.tracking_prev = null;
161 second.tracking_next = null;
162 tracker.appendOperation(&second);
163
164 try testing.expect(first.createdBefore(boundary));
165 try testing.expect(!second.createdBefore(boundary));
166 try testing.expect(tracker.removeOperation(&first));
167 try testing.expect(tracker.removeOperation(&second));
168 }
169
170 test "operation resource tracking uses structural links" {
171 const testing = std.testing;
172 var tracker = Tracker.init();
173
174 var first: Operation = undefined;
175 var second: Operation = undefined;
176 first.tracking_prev = null;
177 first.tracking_next = null;
178 second.tracking_prev = null;
179 second.tracking_next = null;
180
181 tracker.appendOperation(&first);
182 tracker.appendOperation(&second);
183
184 try testing.expectEqual(@as(usize, 2), tracker.operation_count);
185 try testing.expect(tracker.containsOperation(&first));
186 try testing.expect(tracker.containsOperation(&second));
187 try testing.expectEqual(&second, first.tracking_prev.?);
188 try testing.expectEqual(&second, first.tracking_next.?);
189 try testing.expectEqual(&first, second.tracking_prev.?);
190 try testing.expectEqual(&first, second.tracking_next.?);
191
192 try testing.expect(tracker.removeOperation(&first));
193
194 try testing.expectEqual(@as(?*Operation, null), first.tracking_prev);
195 try testing.expectEqual(@as(?*Operation, null), first.tracking_next);
196 try testing.expect(!tracker.containsOperation(&first));
197 try testing.expect(tracker.containsOperation(&second));
198 try testing.expectEqual(@as(usize, 1), tracker.operation_count);
199 try testing.expectEqual(&second, second.tracking_prev.?);
200 try testing.expectEqual(&second, second.tracking_next.?);
201
202 try testing.expect(tracker.removeOperation(&second));
203
204 try testing.expectEqual(@as(usize, 0), tracker.operation_count);
205 try testing.expectEqual(@as(?*Operation, null), tracker.operation_head);
206 }