lib/ui/src/tree/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const abi = @import("../abi/root.zig");
4
5 pub const Error = error{CapacityOverflow};
6
7 /// `Limits` is the largest count of each table a `Store` accepts, plus the
8 /// number of identity map slots. The defaults size one envelope block at
9 /// 6,267,032 bytes and the whole store at 12,992,816 bytes.
10 pub const Limits = struct {
11 nodes: u32 = 16_384,
12 declarations: u32 = 131_072,
13 classes: u32 = 65_536,
14 texts: u32 = 8_192,
15 runs: u32 = 16_384,
16 relations: u32 = 2_048,
17 atoms: u32 = 8_192,
18 string_bytes: u32 = 2 << 20,
19 solved_roots: u32 = 2_048,
20 solved_rects: u32 = 16_384,
21 map_slots: u32 = 32_768,
22
23 /// `Limits.fits` returns true when every field is at most the same field of `bound`.
24 pub fn fits(self: Limits, bound: Limits) bool {
25 return self.nodes <= bound.nodes and self.declarations <= bound.declarations and
26 self.classes <= bound.classes and self.texts <= bound.texts and
27 self.runs <= bound.runs and self.relations <= bound.relations and
28 self.atoms <= bound.atoms and self.string_bytes <= bound.string_bytes and
29 self.solved_roots <= bound.solved_roots and
30 self.solved_rects <= bound.solved_rects and self.map_slots <= bound.map_slots;
31 }
32 };
33
34 /// `Array` describes one table of an envelope block: its name, the `Limits`
35 /// field that bounds its count, its element size in bytes, and its alignment.
36 pub const Array = struct {
37 name: []const u8,
38 limit: []const u8,
39 bytes: u32,
40 alignment: u32,
41 };
42
43 /// `arrays` lists the ten tables in the order they sit in a block.
44 pub const arrays = [_]Array{
45 .{ .name = "nodes", .limit = "nodes", .bytes = @sizeOf(abi.Node), .alignment = 8 },
46 .{ .name = "declarations", .limit = "declarations", .bytes = 16, .alignment = 4 },
47 .{ .name = "classes", .limit = "classes", .bytes = 4, .alignment = 4 },
48 .{ .name = "texts", .limit = "texts", .bytes = @sizeOf(abi.TextRecord), .alignment = 4 },
49 .{ .name = "runs", .limit = "runs", .bytes = @sizeOf(abi.TextRun), .alignment = 4 },
50 .{ .name = "relations", .limit = "relations", .bytes = @sizeOf(abi.Relation), .alignment = 4 },
51 .{ .name = "atoms", .limit = "atoms", .bytes = @sizeOf(abi.Atom), .alignment = 4 },
52 .{ .name = "strings", .limit = "string_bytes", .bytes = 1, .alignment = 1 },
53 .{
54 .name = "solved_roots",
55 .limit = "solved_roots",
56 .bytes = @sizeOf(abi.SolvedRoot),
57 .alignment = 4,
58 },
59 .{
60 .name = "solved_rects",
61 .limit = "solved_rects",
62 .bytes = @sizeOf(abi.Rect),
63 .alignment = 4,
64 },
65 };
66
67 pub const array_count = arrays.len;
68
69 pub const block_alignment: u29 = 8;
70
71 /// `Capacity` is the layout `Capacity.derive` computes from one `Limits`.
72 /// `Capacity.offsets` holds the byte offset of each table in a block, in `arrays` order.
73 /// `Capacity.buffer_bytes` is the size of one block, and `admit` rejects a longer publish
74 /// buffer with `error.PublishTooLarge`. `Capacity.total_bytes` is the size of the one
75 /// allocation a `Store` makes.
76 pub const Capacity = struct {
77 limits: Limits = .{},
78 offsets: [array_count]u32 = @splat(0),
79 buffer_bytes: u32 = 0,
80 total_bytes: u64 = 0,
81
82 /// `Capacity.derive` places the ten tables after the 152 byte header, each at its element
83 /// alignment, and rounds the block up to 8 bytes. The total is two blocks, two identity
84 /// maps of `map_slots` words, two word arrays of `nodes` entries, one of `atoms` entries,
85 /// and one of `texts` entries. It returns `error.CapacityOverflow` when a size overflows
86 /// or when `map_slots` is below `slotCount(nodes)`.
87 pub fn derive(limits: Limits) Error!Capacity {
88 var out = Capacity{ .limits = limits };
89 var cursor: u32 = abi.header_bytes;
90 inline for (arrays, 0..) |entry, index| {
91 cursor = try alignUp(cursor, entry.alignment);
92 out.offsets[index] = cursor;
93 cursor = try add(cursor, try mul(@field(limits, entry.limit), entry.bytes));
94 }
95 out.buffer_bytes = try alignUp(cursor, block_alignment);
96 if (limits.map_slots < slotCount(limits.nodes)) return error.CapacityOverflow;
97 const buffers = try mul64(out.buffer_bytes, 2);
98 const maps = try mul64(try mul(limits.map_slots, 4), 2);
99 const dirty = try mul(limits.nodes, 4);
100 const place = try mul(limits.nodes, 4);
101 const atom_remap = try mul(limits.atoms, 4);
102 const text_remap = try mul(limits.texts, 4);
103 var total = try add64(buffers, maps);
104 total = try add64(total, dirty);
105 total = try add64(total, place);
106 total = try add64(total, atom_remap);
107 out.total_bytes = try add64(total, text_remap);
108 return out;
109 }
110 };
111
112 /// `slotCount` returns the smallest power of two at least twice `nodes`. It returns 0
113 /// for zero nodes and when that power of two does not fit in 32 bits.
114 pub fn slotCount(nodes: u32) u32 {
115 if (nodes == 0) return 0;
116 const wanted = std.math.mul(u32, nodes, 2) catch return 0;
117 return std.math.ceilPowerOfTwo(u32, wanted) catch 0;
118 }
119
120 fn alignUp(value: u32, alignment: u32) Error!u32 {
121 std.debug.assert(std.math.isPowerOfTwo(alignment));
122 const bumped = try add(value, alignment - 1);
123 return bumped & ~(alignment - 1);
124 }
125
126 fn add(left: u32, right: u32) Error!u32 {
127 return std.math.add(u32, left, right) catch error.CapacityOverflow;
128 }
129
130 fn mul(left: u32, right: u32) Error!u32 {
131 return std.math.mul(u32, left, right) catch error.CapacityOverflow;
132 }
133
134 fn add64(left: u64, right: u64) Error!u64 {
135 return std.math.add(u64, left, right) catch error.CapacityOverflow;
136 }
137
138 fn mul64(left: u64, right: u64) Error!u64 {
139 return std.math.mul(u64, left, right) catch error.CapacityOverflow;
140 }
141
142 /// `modelBufferBytes` computes `Capacity.buffer_bytes` a second way, from fixed element sizes
143 /// and alignments rather than from `arrays`, so tests can compare the two.
144 pub fn modelBufferBytes(limits: Limits) u64 {
145 var cursor: u64 = 152;
146 cursor += @as(u64, limits.nodes) * 64;
147 cursor += @as(u64, limits.declarations) * 16;
148 cursor += @as(u64, limits.classes) * 4;
149 cursor += @as(u64, limits.texts) * 16;
150 cursor += @as(u64, limits.runs) * 16;
151 cursor += @as(u64, limits.relations) * 12;
152 cursor += @as(u64, limits.atoms) * 8;
153 cursor += @as(u64, limits.string_bytes) * 1;
154 cursor = (cursor + 3) & ~@as(u64, 3);
155 cursor += @as(u64, limits.solved_roots) * 8;
156 cursor += @as(u64, limits.solved_rects) * 16;
157 return (cursor + 7) & ~@as(u64, 7);
158 }
159
160 test "the default buffer carries the eight priced spans and the two solved spans" {
161 const capacity = try Capacity.derive(.{});
162 const priced: u64 = 1_048_576 + 2_097_152 + 262_144 + 131_072 +
163 262_144 + 24_576 + 65_536 + 2_097_152;
164 try std.testing.expectEqual(@as(u64, 5_988_352), priced);
165 const solved: u64 = 2_048 * 8 + 16_384 * 16;
166 try std.testing.expectEqual(@as(u64, 278_528), solved);
167 try std.testing.expectEqual(@as(u32, 152 + 5_988_352 + 278_528), capacity.buffer_bytes);
168 try std.testing.expectEqual(@as(u32, 6_267_032), capacity.buffer_bytes);
169 }
170
171 test "the owner totals two buffers, two maps, and the splice scratch" {
172 const capacity = try Capacity.derive(.{});
173 const buffers: u64 = 2 * 6_267_032;
174 const maps: u64 = 2 * 32_768 * 4;
175 const scratch: u64 = 16_384 * 4 + 16_384 * 4 + 8_192 * 4 + 8_192 * 4;
176 try std.testing.expectEqual(@as(u64, 12_534_064), buffers);
177 try std.testing.expectEqual(@as(u64, 262_144), maps);
178 try std.testing.expectEqual(@as(u64, 196_608), scratch);
179 try std.testing.expectEqual(buffers + maps + scratch, capacity.total_bytes);
180 try std.testing.expectEqual(@as(u64, 12_992_816), capacity.total_bytes);
181 }
182
183 test "derived offsets match an independent aligned model at several limits" {
184 const cases = [_]Limits{
185 .{},
186 .{
187 .nodes = 1,
188 .declarations = 1,
189 .classes = 1,
190 .texts = 1,
191 .runs = 1,
192 .relations = 1,
193 .atoms = 1,
194 .string_bytes = 1,
195 .solved_roots = 1,
196 .solved_rects = 1,
197 .map_slots = 2,
198 },
199 .{
200 .nodes = 301,
201 .declarations = 907,
202 .classes = 71,
203 .texts = 13,
204 .runs = 37,
205 .relations = 5,
206 .atoms = 61,
207 .string_bytes = 4097,
208 .solved_roots = 3,
209 .solved_rects = 29,
210 .map_slots = 1024,
211 },
212 .{
213 .nodes = 0,
214 .declarations = 0,
215 .classes = 0,
216 .texts = 0,
217 .runs = 0,
218 .relations = 0,
219 .atoms = 0,
220 .string_bytes = 0,
221 .solved_roots = 0,
222 .solved_rects = 0,
223 .map_slots = 0,
224 },
225 };
226 for (cases) |limits| {
227 const capacity = try Capacity.derive(limits);
228 try std.testing.expectEqual(modelBufferBytes(limits), capacity.buffer_bytes);
229 try std.testing.expectEqual(@as(u32, 152), capacity.offsets[0]);
230 }
231 }
232
233 test "derivation reports overflow rather than wrapping a span" {
234 const overflow = Limits{ .declarations = std.math.maxInt(u32) };
235 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(overflow));
236 const strings = Limits{ .string_bytes = std.math.maxInt(u32) };
237 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(strings));
238 }
239
240 test "a slot count stays a power of two above twice the node bound" {
241 try std.testing.expectEqual(@as(u32, 0), slotCount(0));
242 try std.testing.expectEqual(@as(u32, 2), slotCount(1));
243 try std.testing.expectEqual(@as(u32, 8), slotCount(3));
244 try std.testing.expectEqual(@as(u32, 32_768), slotCount(16_384));
245 try std.testing.expect(std.math.isPowerOfTwo(slotCount(301)));
246 try std.testing.expect(slotCount(301) >= 602);
247 }
248
249 test "a limit set fits inside itself and rejects any larger span" {
250 const bound = Limits{};
251 try std.testing.expect(bound.fits(bound));
252 try std.testing.expect((Limits{ .nodes = 1, .declarations = 1 }).fits(bound));
253 try std.testing.expect(!(Limits{ .nodes = 16_385 }).fits(bound));
254 try std.testing.expect(!(Limits{ .map_slots = 65_536 }).fits(bound));
255 try std.testing.expect(!(Limits{ .solved_rects = 16_385 }).fits(bound));
256 }