lib/ui/src/layout/store.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const arrange = @import("arrange");
4 const abi = @import("../abi/root.zig");
5 const fact = @import("../fact/root.zig");
6 const tree = @import("../tree/root.zig");
7 const input = @import("input.zig");
8
9 const Allocator = std.mem.Allocator;
10
11 pub const Limits = struct {
12 nodes: u32 = 16_384,
13 };
14
15 pub const Capacity = struct {
16 nodes: usize,
17 children: usize,
18 rect_bytes: usize,
19 cache_bytes: usize,
20 metric_bytes: usize,
21 line_bytes: usize,
22 clip_bytes: usize,
23 clip_index_bytes: usize,
24 total_bytes: usize,
25
26 pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {
27 if (limits.nodes == 0 or limits.nodes == std.math.maxInt(u32)) return error.CapacityOverflow;
28 const nodes: usize = limits.nodes;
29 const children = nodes - 1;
30 const rect_bytes = try bytes(nodes, @sizeOf(arrange.Rect));
31 const cache_bytes = try bytes(try bytes(nodes, 4), @sizeOf(arrange.IndexedCacheSlot));
32 const metric_bytes = try bytes(children, @sizeOf(arrange.ChildMetrics));
33 const line_bytes = try bytes(children, @sizeOf(arrange.Line));
34 const clip_bytes = try bytes(nodes + 1, @sizeOf(fact.Clip));
35 const clip_index_bytes = try bytes(nodes, @sizeOf(u32));
36 var total: usize = 0;
37 for ([_]usize{
38 rect_bytes,
39 cache_bytes,
40 metric_bytes,
41 line_bytes,
42 clip_bytes,
43 clip_index_bytes,
44 }) |part| {
45 total = std.math.add(usize, total, part) catch return error.CapacityOverflow;
46 }
47 return .{
48 .nodes = nodes,
49 .children = children,
50 .rect_bytes = rect_bytes,
51 .cache_bytes = cache_bytes,
52 .metric_bytes = metric_bytes,
53 .line_bytes = line_bytes,
54 .clip_bytes = clip_bytes,
55 .clip_index_bytes = clip_index_bytes,
56 .total_bytes = total,
57 };
58 }
59
60 fn bytes(count: usize, width: usize) error{CapacityOverflow}!usize {
61 return std.math.mul(usize, count, width) catch return error.CapacityOverflow;
62 }
63 };
64
65 pub const Store = struct {
66 pub const claim: alloc_phase.capacity.Declaration = .{
67 .source = .{
68 .id = "ui.layout_workspace",
69 .kind = .phase_static,
70 .limit_source = .caller,
71 .storage = .{
72 .covered = &.{
73 .{ .id = "rects", .lifetime = .steady, .detail = "one arrange rectangle per admitted node" },
74 .{ .id = "size_cache", .lifetime = .steady, .detail = "four indexed size slots per admitted node" },
75 .{ .id = "child_scratch", .lifetime = .steady, .detail = "metrics and lines for at most nodes minus one live children" },
76 .{ .id = "clips", .lifetime = .steady, .detail = "one viewport clip, plus one clip slot and clip index per admitted node" },
77 },
78 .excluded = &.{
79 "the admitted publish envelope and computed style pools",
80 "shaped-run and measurement caches owned by the text lane",
81 },
82 },
83 .capacity = .{
84 .inputs = &.{
85 alloc_phase.capacity.bindInput(Capacity, "nodes", "nodes"),
86 alloc_phase.capacity.bindInput(Capacity, "children", "children"),
87 },
88 .type_selectors = &.{
89 alloc_phase.capacity.bindType(arrange.Rect, "rect"),
90 alloc_phase.capacity.bindType(arrange.IndexedCacheSlot, "cache_slot"),
91 alloc_phase.capacity.bindType(arrange.ChildMetrics, "child_metric"),
92 alloc_phase.capacity.bindType(arrange.Line, "line"),
93 alloc_phase.capacity.bindType(fact.Clip, "clip"),
94 alloc_phase.capacity.bindType(u32, "clip_index"),
95 },
96 .nodes = &.{
97 .{ .input = 0 },
98 .{ .input = 1 },
99 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
100 .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 4 } } },
101 .{ .scale = .{ .node = 3, .coefficient = .{ .size_of_concrete_type = 1 } } },
102 .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 2 } } },
103 .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 3 } } },
104 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 4 } } },
105 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 5 } } },
106 .{ .constant = @sizeOf(fact.Clip) },
107 .{ .add = .{ .left = 2, .right = 4 } },
108 .{ .add = .{ .left = 10, .right = 5 } },
109 .{ .add = .{ .left = 11, .right = 6 } },
110 .{ .add = .{ .left = 12, .right = 7 } },
111 .{ .add = .{ .left = 13, .right = 8 } },
112 .{ .add = .{ .left = 14, .right = 9 } },
113 },
114 .assertions = &.{.{
115 .scope = .closure_total,
116 .measure = .retained,
117 .relation = .exact,
118 .expression = 15,
119 }},
120 },
121 .overload = .{
122 .kind = .reject_before_seal,
123 .detail = "a node count over Limits.nodes is rejected before any retained layout span is written",
124 },
125 .risks = .{
126 .transitive = .{ .status = .open, .detail = "arrange and style accessors allocate no memory during solve; a machine call graph certificate remains open" },
127 .foreign = .{ .status = .excluded, .detail = "layout invokes no foreign runtime" },
128 },
129 .obligations = &.{
130 .{ .key = "ui_layout_capacity", .role = .capacity_model },
131 .{ .key = "ui_layout_acquisition", .role = .acquisition },
132 .{ .key = "ui_layout_depth_bound", .role = .work_bound },
133 .{ .key = "ui_layout_oom", .role = .initialization_failure },
134 .{ .key = "ui_layout_teardown", .role = .teardown },
135 },
136 },
137 .bindings = .{
138 .owner = @This(),
139 .seal = .{
140 .family = alloc_phase.capacity.selector(@This().activate),
141 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
142 },
143 .teardown = .{
144 .family = alloc_phase.capacity.selector(@This().deinit),
145 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
146 },
147 },
148 };
149
150 phase: alloc_phase.capacity.Phase = .initialization,
151 limits: Limits,
152 capacity: Capacity,
153 rects: []arrange.Rect,
154 cache: []arrange.IndexedCacheSlot,
155 metrics: []arrange.ChildMetrics,
156 lines: []arrange.Line,
157 clips: []fact.Clip,
158 clip_indices: []u32,
159 node_count: u32 = 0,
160 clip_count: u32 = 0,
161 cache_epoch: u32 = 0,
162
163 pub fn init(allocator: Allocator, limits: Limits) (error{CapacityOverflow} || Allocator.Error)!Store {
164 const capacity = try Capacity.derive(limits);
165 const rects = try allocator.alloc(arrange.Rect, capacity.nodes);
166 errdefer allocator.free(rects);
167 const cache = try allocator.alloc(arrange.IndexedCacheSlot, capacity.nodes * 4);
168 errdefer allocator.free(cache);
169 const metrics = try allocator.alloc(arrange.ChildMetrics, capacity.children);
170 errdefer allocator.free(metrics);
171 const lines = try allocator.alloc(arrange.Line, capacity.children);
172 errdefer allocator.free(lines);
173 const clips = try allocator.alloc(fact.Clip, capacity.nodes + 1);
174 errdefer allocator.free(clips);
175 const clip_indices = try allocator.alloc(u32, capacity.nodes);
176 @memset(cache, .{});
177 return .{
178 .limits = limits,
179 .capacity = capacity,
180 .rects = rects,
181 .cache = cache,
182 .metrics = metrics,
183 .lines = lines,
184 .clips = clips,
185 .clip_indices = clip_indices,
186 };
187 }
188
189 pub fn activate(self: *Store) void {
190 std.debug.assert(self.phase == .initialization);
191 self.phase = .steady;
192 }
193
194 pub fn solve(
195 self: *Store,
196 view: tree.View,
197 styles: input.Styles,
198 measurer: ?*arrange.Measurer,
199 ) error{ CapacityExceeded, EmptyTree, StyleCountMismatch }!Result {
200 std.debug.assert(self.phase == .steady);
201 if (view.nodes.len == 0) return error.EmptyTree;
202 if (view.nodes.len > self.limits.nodes) return error.CapacityExceeded;
203 if (styles.count() < view.nodes.len) return error.StyleCountMismatch;
204 if (measurer) |value| value.reset();
205 var source = input.Input{ .view = view, .styles = styles, .rects = self.rects };
206 var scratch = arrange.Scratch{
207 .results = &.{},
208 .metrics = self.metrics,
209 .lines = self.lines,
210 .states = &.{},
211 .child_indices = &.{},
212 .indexed_cache = self.cache,
213 .cache_epoch = self.cache_epoch,
214 };
215 const size = arrange.computeLayoutIndexed(
216 &scratch,
217 source.indexed(),
218 0,
219 .{ .width = view.header.viewport.width, .height = view.header.viewport.height },
220 .{ .x = view.header.viewport.x, .y = view.header.viewport.y },
221 measurer,
222 );
223 self.cache_epoch = scratch.cache_epoch;
224 self.placeSolved(view);
225 self.buildClips(view, styles);
226 self.node_count = @intCast(view.nodes.len);
227 return .{ .size = size, .work = scratch.work, .clips = self.clip_count };
228 }
229
230 fn placeSolved(self: *Store, view: tree.View) void {
231 for (view.solved_roots) |root| {
232 const supplied = view.solvedRectsOf(root);
233 const placed = self.rects[root.node];
234 const dx = placed.x - supplied[0].x;
235 const dy = placed.y - supplied[0].y;
236 for (supplied[1..], 1..) |rect, offset| {
237 self.rects[@as(usize, root.node) + offset] = .{
238 .x = rect.x + dx,
239 .y = rect.y + dy,
240 .width = rect.width,
241 .height = rect.height,
242 };
243 }
244 }
245 }
246
247 fn buildClips(self: *Store, view: tree.View, styles: input.Styles) void {
248 self.clips[0] = .{ .rect = view.header.viewport };
249 self.clip_count = 1;
250 for (view.nodes, 0..) |node, index| {
251 const parent = if (index == 0) @as(u32, 0) else self.clip_indices[node.parent];
252 const clipped = abi.holds(node.flags, .clip) or
253 abi.holds(node.flags, .scroll_x) or
254 abi.holds(node.flags, .scroll_y);
255 if (!clipped) {
256 self.clip_indices[index] = parent;
257 continue;
258 }
259 const clip_index = self.clip_count;
260 std.debug.assert(clip_index < self.clips.len);
261 self.clip_count += 1;
262 const rect = self.rects[index];
263 const padding = styles.record(@intCast(index)).layout.padding;
264 self.clips[clip_index] = .{
265 .rect = .{ .x = rect.x, .y = rect.y, .width = rect.width, .height = rect.height },
266 .origin_x = rect.x + @max(0, padding.left orelse 0),
267 .origin_y = rect.y + @max(0, padding.top orelse 0),
268 .parent = parent,
269 .flags = node.flags,
270 };
271 self.clip_indices[index] = clip_index;
272 }
273 }
274
275 pub fn retainedRects(self: *const Store) []const arrange.Rect {
276 std.debug.assert(self.phase == .steady);
277 return self.rects[0..self.node_count];
278 }
279
280 pub fn retainedClips(self: *const Store) []const fact.Clip {
281 std.debug.assert(self.phase == .steady);
282 return self.clips[0..self.clip_count];
283 }
284
285 pub fn deinit(self: *Store, allocator: Allocator) void {
286 std.debug.assert(self.phase != .teardown);
287 self.phase = .teardown;
288 allocator.free(self.clip_indices);
289 allocator.free(self.clips);
290 allocator.free(self.lines);
291 allocator.free(self.metrics);
292 allocator.free(self.cache);
293 allocator.free(self.rects);
294 self.clip_indices = &.{};
295 self.clips = &.{};
296 self.lines = &.{};
297 self.metrics = &.{};
298 self.cache = &.{};
299 self.rects = &.{};
300 }
301 };
302
303 pub const Result = struct {
304 size: arrange.Size,
305 work: arrange.Work,
306 clips: u32,
307 };