lib/arrange/src/compute.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const absolute = @import("absolute.zig");
3 const axis = @import("axis.zig");
4 const flow = @import("flow.zig");
5 const sizing = @import("sizing.zig");
6 const types = @import("types.zig");
7
8 const Available = types.Available;
9 const AvailableSpace = types.AvailableSpace;
10 const Dimensions = types.Dimensions;
11 const LayoutInput = types.LayoutInput;
12 const LayoutResult = types.LayoutResult;
13 const Measurer = types.Measurer;
14 const Node = types.Node;
15 const Rect = types.Rect;
16 const Size = types.Size;
17
18 pub const max_depth: usize = 64;
19 pub const ChildIndex = usize;
20
21 pub const Work = struct {
22 node_entries: usize = 0,
23 child_visits: usize = 0,
24 line_formations: usize = 0,
25 size_cache_hits: usize = 0,
26 size_cache_misses: usize = 0,
27 size_cache_conflicts: usize = 0,
28 };
29
30 const RunMode = enum {
31 compute_size,
32 perform_layout,
33 };
34
35 const SizeRequest = enum(u2) {
36 max_content,
37 settled_width,
38 content_horizontal,
39 content_vertical,
40 };
41
42 const size_request_count: usize = 4;
43
44 const CacheSlot = struct {
45 valid: bool = false,
46 input: LayoutInput = .{},
47 size: Size = .{},
48 };
49
50 pub const IndexedCacheSlot = struct {
51 epoch: u32 = 0,
52 width: f32 = 0,
53 size: Size = .{},
54 };
55
56 comptime {
57 std.debug.assert(@sizeOf(IndexedCacheSlot) == 16);
58 std.debug.assert(@sizeOf(flow.ChildMetrics) == 56);
59 std.debug.assert(@sizeOf(flow.Line) == 24);
60 }
61
62 pub const IndexedInput = struct {
63 context: ?*anyopaque,
64 count: u32,
65 get: *const fn (?*anyopaque, u32) Node,
66 descendants: *const fn (?*anyopaque, u32) u32,
67 is_leaf: ?*const fn (?*anyopaque, u32) bool = null,
68 rects: []Rect,
69
70 pub const flat = true;
71
72 fn node(self: IndexedInput, index: usize) Node {
73 std.debug.assert(index < self.count);
74 return self.get(self.context, @intCast(index));
75 }
76
77 fn children(self: IndexedInput, index: usize) IndexedChildren {
78 const end = index + self.descendants(self.context, @intCast(index)) + 1;
79 std.debug.assert(end <= self.count);
80 return .{ .source = self, .cursor = index + 1, .end = end };
81 }
82
83 fn childCount(self: IndexedInput, index: usize) usize {
84 if (self.is_leaf) |is_leaf| {
85 if (is_leaf(self.context, @intCast(index))) return 0;
86 }
87 var iter = self.children(index);
88 var count: usize = 0;
89 while (iter.next()) |_| count += 1;
90 return count;
91 }
92
93 fn recordRect(self: IndexedInput, index: usize, rect: Rect) void {
94 self.rects[index] = rect;
95 }
96 };
97
98 const Child = struct {
99 state_index: usize,
100 index: usize,
101 };
102
103 const IndexedChildren = struct {
104 source: IndexedInput,
105 cursor: usize,
106 end: usize,
107 ordinal: usize = 0,
108
109 fn next(self: *IndexedChildren) ?Child {
110 if (self.cursor == self.end) return null;
111 const result = Child{ .state_index = self.cursor, .index = self.ordinal };
112 self.cursor += self.source.descendants(self.source.context, @intCast(self.cursor)) + 1;
113 self.ordinal += 1;
114 std.debug.assert(self.cursor <= self.end);
115 return result;
116 }
117 };
118
119 const NestedSource = struct {
120 scratch: *Scratch,
121
122 pub const flat = false;
123
124 fn node(self: NestedSource, index: usize) Node {
125 return self.scratch.states[index].node.*;
126 }
127
128 fn children(self: NestedSource, index: usize) NestedChildren {
129 return .{ .indices = self.scratch.states[index].children };
130 }
131
132 fn childCount(self: NestedSource, index: usize) usize {
133 return self.scratch.states[index].children.len;
134 }
135
136 fn recordRect(_: NestedSource, _: usize, _: Rect) void {}
137 };
138
139 const NestedChildren = struct {
140 indices: []const ChildIndex,
141 ordinal: usize = 0,
142
143 fn next(self: *NestedChildren) ?Child {
144 if (self.ordinal == self.indices.len) return null;
145 const result = Child{ .state_index = self.indices[self.ordinal], .index = self.ordinal };
146 self.ordinal += 1;
147 return result;
148 }
149 };
150
151 const ScratchMark = struct {
152 metrics: usize,
153 lines: usize,
154 };
155
156 pub const NodeState = struct {
157 node: *const Node = undefined,
158 children: []ChildIndex = &.{},
159 cache: [size_request_count]CacheSlot = .{ .{}, .{}, .{}, .{} },
160 };
161
162 pub const Scratch = struct {
163 results: []LayoutResult,
164 results_used: usize = 0,
165 metrics: []flow.ChildMetrics,
166 metrics_used: usize = 0,
167 lines: []flow.Line,
168 lines_used: usize = 0,
169 states: []NodeState,
170 states_used: usize = 0,
171 child_indices: []ChildIndex,
172 child_indices_used: usize = 0,
173 indexed_cache: []IndexedCacheSlot = &.{},
174 cache_epoch: u32 = 0,
175 work: Work = .{},
176 size_cache_enabled: bool = true,
177
178 pub fn reset(self: *Scratch) void {
179 self.results_used = 0;
180 self.metrics_used = 0;
181 self.lines_used = 0;
182 self.resetSolve();
183 }
184
185 fn resetSolve(self: *Scratch) void {
186 self.states_used = 0;
187 self.child_indices_used = 0;
188 self.work = .{};
189 std.debug.assert(self.indexed_cache.len <= std.math.maxInt(u32));
190 const clear_start = std.math.maxInt(u32) - @as(u32, @intCast(self.indexed_cache.len));
191 if (self.cache_epoch >= clear_start and self.cache_epoch < std.math.maxInt(u32)) {
192 const clear_index: usize = @intCast(self.cache_epoch - clear_start);
193 self.indexed_cache[clear_index].epoch = 0;
194 }
195 self.cache_epoch +%= 1;
196 if (self.cache_epoch == 0) self.cache_epoch = 1;
197 }
198
199 fn mark(self: *const Scratch) ScratchMark {
200 return .{
201 .metrics = self.metrics_used,
202 .lines = self.lines_used,
203 };
204 }
205
206 fn release(self: *Scratch, point: ScratchMark) void {
207 self.metrics_used = point.metrics;
208 self.lines_used = point.lines;
209 }
210
211 fn carveResults(self: *Scratch, count: usize) []LayoutResult {
212 std.debug.assert(self.results_used + count <= self.results.len);
213 const span = self.results[self.results_used..][0..count];
214 self.results_used += count;
215 return span;
216 }
217
218 fn carveMetrics(self: *Scratch, count: usize) []flow.ChildMetrics {
219 std.debug.assert(self.metrics_used + count <= self.metrics.len);
220 const span = self.metrics[self.metrics_used..][0..count];
221 self.metrics_used += count;
222 return span;
223 }
224
225 fn carveLines(self: *Scratch, count: usize) []flow.Line {
226 std.debug.assert(self.lines_used + count <= self.lines.len);
227 const span = self.lines[self.lines_used..][0..count];
228 self.lines_used += count;
229 return span;
230 }
231 };
232
233 const Point = struct {
234 x: f32 = 0,
235 y: f32 = 0,
236 };
237
238 const Output = struct {
239 size: Size,
240 layout: ?LayoutResult = null,
241 };
242
243 const Box = struct {
244 border: Dimensions,
245 child_width: ?f32,
246 main_limit: ?f32,
247 cross_limit: ?f32,
248 padding: axis.ResolvedInsets,
249 };
250
251 const Phase = struct {
252 metrics: []flow.ChildMetrics,
253 lines: []flow.Line,
254 main_limit: ?f32,
255 cross_limit: ?f32,
256 gap: f32,
257 };
258
259 fn Solver(comptime Source: type) type {
260 return struct {
261 scratch: *Scratch,
262 source: Source,
263 measurer: ?*Measurer,
264
265 fn computeNode(
266 self: *@This(),
267 state_index: usize,
268 input: LayoutInput,
269 mode: RunMode,
270 request: SizeRequest,
271 origin: Point,
272 ) Output {
273 self.scratch.work.node_entries += 1;
274 if (mode == .compute_size) {
275 if (self.cachedSize(state_index, request, input)) |size| {
276 return .{ .size = size };
277 }
278 }
279
280 const mark = self.scratch.mark();
281 const node = self.source.node(state_index);
282 const output = if (self.source.childCount(state_index) == 0)
283 self.solveLeaf(&node, input, mode, request, origin)
284 else
285 self.solveContainer(state_index, input, mode, request, origin);
286 if (mode == .compute_size) {
287 self.scratch.release(mark);
288 self.storeSize(state_index, request, input, output.size);
289 } else {
290 self.source.recordRect(state_index, output.layout.?.rect);
291 }
292 return output;
293 }
294
295 fn solveLeaf(
296 self: *@This(),
297 node: *const Node,
298 input: LayoutInput,
299 mode: RunMode,
300 request: SizeRequest,
301 origin: Point,
302 ) Output {
303 const padding = axis.resolvedInsets(node.style.padding);
304 const border = resolveBorder(node, input, mode, request);
305 const available = leafAvailable(input, request, border, padding);
306 const measured = self.measureLeaf(node, available);
307 const size = finishLeafSize(node, request, border, padding, measured);
308 const layout: ?LayoutResult = if (mode == .perform_layout) .{
309 .id = node.id,
310 .rect = rectAt(origin, size),
311 .children = &.{},
312 } else null;
313 return .{ .size = size, .layout = layout };
314 }
315
316 fn solveContainer(
317 self: *@This(),
318 state_index: usize,
319 input: LayoutInput,
320 mode: RunMode,
321 request: SizeRequest,
322 origin: Point,
323 ) Output {
324 const node = self.source.node(state_index);
325 const box = resolveBox(&node, input, mode, request);
326 const child_count = self.source.childCount(state_index);
327 const metrics = self.scratch.carveMetrics(child_count);
328 const lines = self.scratch.carveLines(child_count);
329 const phase = self.buildPhase(state_index, box, mode, request, metrics, lines);
330 self.resolvePhase(state_index, mode, request, phase);
331 const size = finishContainerSize(&node, box, request, phase);
332 const layout = if (mode == .perform_layout)
333 self.layoutContainer(state_index, origin, size, phase)
334 else
335 null;
336 return .{ .size = size, .layout = layout };
337 }
338
339 fn buildPhase(
340 self: *@This(),
341 state_index: usize,
342 box: Box,
343 mode: RunMode,
344 request: SizeRequest,
345 metrics_storage: []flow.ChildMetrics,
346 lines_storage: []flow.Line,
347 ) Phase {
348 const parent = self.source.node(state_index);
349 var children = self.source.children(state_index);
350 var metric_count: usize = 0;
351 while (children.next()) |child_ref| {
352 const child = self.source.node(child_ref.state_index);
353 if (child.style.position == .absolute) continue;
354 self.scratch.work.child_visits += 1;
355 metrics_storage[metric_count] = self.childMetric(
356 child_ref.state_index,
357 child_ref.index,
358 &parent,
359 box,
360 mode,
361 request,
362 );
363 metric_count += 1;
364 }
365 const metrics = metrics_storage[0..metric_count];
366 if (box.main_limit != null) {
367 self.prepareMinimums(metrics, parent.style.flex_direction);
368 }
369 const line_count = self.formLines(
370 &parent,
371 metrics,
372 lines_storage,
373 box.main_limit,
374 requestsMainMinimum(mode, request, parent.style.flex_direction),
375 );
376 return .{
377 .metrics = metrics,
378 .lines = lines_storage[0..line_count],
379 .main_limit = box.main_limit,
380 .cross_limit = box.cross_limit,
381 .gap = axis.nonNegative(parent.style.gap),
382 };
383 }
384
385 fn childMetric(
386 self: *@This(),
387 child_index: usize,
388 index: usize,
389 parent: *const Node,
390 box: Box,
391 mode: RunMode,
392 request: SizeRequest,
393 ) flow.ChildMetrics {
394 const content_axis = requestedContentAxis(mode, request);
395 if (content_axis == .horizontal) {
396 return self.horizontalContentMetric(child_index, index, parent);
397 }
398 if (content_axis == .vertical) {
399 return self.verticalContentMetric(child_index, index, parent, box);
400 }
401 return self.inherentMetric(child_index, index, parent, box);
402 }
403
404 fn inherentMetric(
405 self: *@This(),
406 child_index: usize,
407 index: usize,
408 parent: *const Node,
409 box: Box,
410 ) flow.ChildMetrics {
411 const child = self.source.node(child_index);
412 const maximum = self.sizeFor(child_index, .max_content, null);
413 const settled_width = if (parent.style.flex_direction == .column)
414 self.settleChildWidth(child_index, parent, maximum.width, box.child_width)
415 else
416 null;
417 const measured = if (settled_width) |width|
418 self.sizeFor(child_index, .settled_width, width)
419 else
420 maximum;
421 var metric = metricFromSize(
422 child_index,
423 index,
424 &child,
425 measured,
426 parent.style.flex_direction,
427 );
428 if (settled_width) |width| {
429 metric.base_cross = width;
430 }
431 return metric;
432 }
433
434 fn horizontalContentMetric(
435 self: *@This(),
436 child_index: usize,
437 index: usize,
438 parent: *const Node,
439 ) flow.ChildMetrics {
440 const child = self.source.node(child_index);
441 const horizontal_main = parent.style.flex_direction == .row;
442 const main_limits = axis.axisLimits(&child, axis.mainAxis(parent.style.flex_direction));
443 var minimum = self.automaticMinimum(child_index, .horizontal, null);
444 if (horizontal_main and parent.style.wrap == .wrap) {
445 const maximum = self.sizeFor(child_index, .max_content, null);
446 minimum = multilineMinimumContribution(&child, minimum, maximum, .row);
447 }
448 return .{
449 .index = index,
450 .state_index = child_index,
451 .base_main = if (horizontal_main) minimum else 0,
452 .base_cross = if (horizontal_main) 0 else minimum,
453 .target_main = if (horizontal_main) minimum else 0,
454 .min_main = main_limits.min,
455 .max_main = main_limits.max,
456 .flex_grow = axis.nonNegative(child.style.flex_grow),
457 .flex_shrink = axis.nonNegative(child.style.flex_shrink),
458 };
459 }
460
461 fn verticalContentMetric(
462 self: *@This(),
463 child_index: usize,
464 index: usize,
465 parent: *const Node,
466 box: Box,
467 ) flow.ChildMetrics {
468 const child = self.source.node(child_index);
469 if (parent.style.flex_direction == .row) {
470 const maximum = self.sizeFor(child_index, .max_content, null);
471 var metric = metricFromSize(child_index, index, &child, maximum, .row);
472 metric.base_cross = 0;
473 return metric;
474 }
475 const maximum = self.sizeFor(child_index, .max_content, null);
476 const width = self.settleChildWidth(
477 child_index,
478 parent,
479 maximum.width,
480 box.child_width,
481 ).?;
482 var minimum = self.automaticMinimum(child_index, .vertical, width);
483 if (parent.style.wrap == .wrap) {
484 const settled = self.sizeFor(child_index, .settled_width, width);
485 minimum = multilineMinimumContribution(&child, minimum, settled, .column);
486 }
487 return .{
488 .index = index,
489 .state_index = child_index,
490 .base_main = minimum,
491 .base_cross = width,
492 .target_main = minimum,
493 .min_main = axis.axisLimits(&child, .vertical).min,
494 .max_main = axis.axisLimits(&child, .vertical).max,
495 .flex_grow = axis.nonNegative(child.style.flex_grow),
496 .flex_shrink = axis.nonNegative(child.style.flex_shrink),
497 };
498 }
499
500 fn formLines(
501 self: *@This(),
502 node: *const Node,
503 metrics: []flow.ChildMetrics,
504 storage: []flow.Line,
505 main_limit: ?f32,
506 one_item_lines: bool,
507 ) usize {
508 if (metrics.len == 0) return 0;
509 const gap = axis.nonNegative(node.style.gap);
510 var count: usize = 0;
511 var start: usize = 0;
512 var occupied: f32 = 0;
513 for (metrics, 0..) |metric, index| {
514 const hypothetical = flow.hypotheticalMain(metric);
515 const addition = if (index == start) hypothetical else gap + hypothetical;
516 const exceeds_limit = main_limit != null and
517 occupied + addition > main_limit.?;
518 const should_wrap = node.style.wrap == .wrap and
519 index > start and
520 (one_item_lines or exceeds_limit);
521 if (should_wrap) {
522 storage[count] = .{ .items = metrics[start..index] };
523 self.scratch.work.line_formations += 1;
524 count += 1;
525 start = index;
526 occupied = 0;
527 }
528 occupied += if (index == start) hypothetical else gap + hypothetical;
529 }
530 storage[count] = .{ .items = metrics[start..] };
531 self.scratch.work.line_formations += 1;
532 return count + 1;
533 }
534
535 fn resolvePhase(
536 self: *@This(),
537 state_index: usize,
538 mode: RunMode,
539 request: SizeRequest,
540 phase: Phase,
541 ) void {
542 const node = self.source.node(state_index);
543 const direction = node.style.flex_direction;
544 for (phase.lines) |*line| {
545 if (phase.main_limit) |limit| {
546 flow.resolveFlexibleLengths(line, limit, phase.gap);
547 } else {
548 for (line.items) |*item| item.target_main = flow.hypotheticalMain(item.*);
549 }
550 if (direction == .row and phase.main_limit != null) {
551 self.remeasureRow(line, mode, request);
552 }
553 line.cross_size = flow.resolveLineCrossSizeKnown(
554 &node,
555 line,
556 phase.cross_limit,
557 );
558 }
559 }
560
561 fn prepareMinimums(
562 self: *@This(),
563 metrics: []flow.ChildMetrics,
564 direction: types.FlexDirection,
565 ) void {
566 for (metrics) |*item| {
567 const requested_axis = axis.mainAxis(direction);
568 const width = if (requested_axis == .vertical) item.base_cross else null;
569 item.min_main = @max(
570 item.min_main,
571 self.automaticMinimum(item.state_index, requested_axis, width),
572 );
573 }
574 }
575
576 fn remeasureRow(
577 self: *@This(),
578 line: *flow.Line,
579 mode: RunMode,
580 request: SizeRequest,
581 ) void {
582 const content_axis = requestedContentAxis(mode, request);
583 for (line.items) |*item| {
584 if (content_axis == .vertical) {
585 item.base_cross = self.automaticMinimum(
586 item.state_index,
587 .vertical,
588 item.target_main,
589 );
590 } else {
591 const resized = self.sizeFor(
592 item.state_index,
593 .settled_width,
594 item.target_main,
595 );
596 const child = self.source.node(item.state_index);
597 item.base_cross = sizing.resolvePreferredCrossSize(&child, resized, .row);
598 }
599 }
600 }
601
602 fn layoutContainer(
603 self: *@This(),
604 state_index: usize,
605 origin: Point,
606 size: Size,
607 phase: Phase,
608 ) LayoutResult {
609 const node = self.source.node(state_index);
610 const children: []LayoutResult = if (comptime Source.flat)
611 &.{}
612 else
613 self.scratch.carveResults(self.source.childCount(state_index));
614 const rect = rectAt(origin, size);
615 const content_rect = axis.contentRect(rect, node.style.padding);
616 self.layoutAbsoluteChildren(state_index, content_rect, children);
617 self.layoutFlowChildren(state_index, content_rect, phase, children);
618 return .{ .id = node.id, .rect = rect, .children = children };
619 }
620
621 fn layoutAbsoluteChildren(
622 self: *@This(),
623 state_index: usize,
624 content_rect: Rect,
625 children: []LayoutResult,
626 ) void {
627 const parent = self.source.node(state_index);
628 var iterator = self.source.children(state_index);
629 while (iterator.next()) |child_ref| {
630 const child = self.source.node(child_ref.state_index);
631 if (child.style.position != .absolute) continue;
632 self.scratch.work.child_visits += 1;
633 const child_index = child_ref.state_index;
634 const size = self.absoluteSize(child_index, content_rect);
635 const child_rect = absolute.place(&parent, &child, content_rect, size);
636 const output = self.computeNode(
637 child_index,
638 exactInput(size),
639 .perform_layout,
640 .settled_width,
641 .{ .x = child_rect.x, .y = child_rect.y },
642 );
643 if (comptime !Source.flat) children[child_ref.index] = output.layout.?;
644 }
645 }
646
647 fn layoutFlowChildren(
648 self: *@This(),
649 state_index: usize,
650 content_rect: Rect,
651 phase: Phase,
652 children: []LayoutResult,
653 ) void {
654 const parent = self.source.node(state_index);
655 var cross_cursor: f32 = 0;
656 for (phase.lines, 0..) |*line, line_index| {
657 const limit = phase.main_limit orelse lineMainExtent(line, phase.gap);
658 const offsets = flow.justifyLine(
659 parent.style.justify_content,
660 line,
661 limit,
662 phase.gap,
663 );
664 self.layoutLine(&parent, content_rect, line, children, cross_cursor, offsets);
665 cross_cursor += line.cross_size;
666 if (line_index + 1 < phase.lines.len) cross_cursor += phase.gap;
667 }
668 }
669
670 fn layoutLine(
671 self: *@This(),
672 parent: *const Node,
673 content_rect: Rect,
674 line: *flow.Line,
675 children: []LayoutResult,
676 cross_cursor: f32,
677 offsets: flow.LineOffsets,
678 ) void {
679 const direction = parent.style.flex_direction;
680 var main_cursor = offsets.offset;
681 for (line.items, 0..) |*item, item_index| {
682 self.scratch.work.child_visits += 1;
683 const child = self.source.node(item.state_index);
684 const alignment = sizing.effectiveAlignSelf(
685 parent.style.align_items,
686 child.style.align_self,
687 );
688 var cross = resolvedCross(&child, item, line.cross_size, direction, alignment);
689 const cross_axis = axis.crossAxis(direction);
690 const cross_width = if (cross_axis == .vertical) item.target_main else null;
691 cross = @max(
692 cross,
693 self.automaticMinimum(item.state_index, cross_axis, cross_width),
694 );
695 const cross_offset = alignmentOffset(alignment, line.cross_size, cross);
696 const rect = axis.rectFromAxes(
697 content_rect,
698 direction,
699 main_cursor,
700 cross_cursor + cross_offset,
701 item.target_main,
702 cross,
703 );
704 const output = self.computeNode(
705 item.state_index,
706 exactInput(.{ .width = rect.width, .height = rect.height }),
707 .perform_layout,
708 .settled_width,
709 .{ .x = rect.x, .y = rect.y },
710 );
711 if (comptime !Source.flat) children[item.index] = output.layout.?;
712 main_cursor += item.target_main;
713 if (item_index + 1 < line.items.len) main_cursor += offsets.between_gap;
714 }
715 }
716
717 fn absoluteSize(self: *@This(), child_index: usize, containing: Rect) Size {
718 const child = self.source.node(child_index);
719 var width = insetSize(
720 containing.width,
721 child.style.inset.left,
722 child.style.inset.right,
723 );
724 var height = insetSize(
725 containing.height,
726 child.style.inset.top,
727 child.style.inset.bottom,
728 );
729 if (width == null) width = self.sizeFor(child_index, .max_content, null).width;
730 width = axis.clampSize(&child, .horizontal, width.?);
731 if (height == null) {
732 height = self.sizeFor(child_index, .settled_width, width).height;
733 }
734 height = axis.clampSize(&child, .vertical, height.?);
735 return .{ .width = width.?, .height = height.? };
736 }
737
738 fn settleChildWidth(
739 self: *@This(),
740 child_index: usize,
741 parent: *const Node,
742 intrinsic: f32,
743 limit: ?f32,
744 ) ?f32 {
745 const child = self.source.node(child_index);
746 const width_limit = limit orelse return null;
747 const alignment = sizing.effectiveAlignSelf(
748 parent.style.align_items,
749 child.style.align_self,
750 );
751 const preferred = child.size.width orelse intrinsic;
752 const contained = if (alignment == .stretch and child.size.width == null)
753 width_limit
754 else
755 @min(preferred, width_limit);
756 const constrained = axis.clampSize(&child, .horizontal, contained);
757 return @max(
758 constrained,
759 self.automaticMinimum(child_index, .horizontal, null),
760 );
761 }
762
763 fn automaticMinimum(
764 self: *@This(),
765 state_index: usize,
766 requested_axis: axis.Axis,
767 width: ?f32,
768 ) f32 {
769 const node = self.source.node(state_index);
770 const limits = axis.axisLimits(&node, requested_axis);
771 if (explicitMinimum(&node, requested_axis) != null) return limits.min;
772 if (clipsAxis(&node, requested_axis)) return limits.min;
773 const request: SizeRequest = if (requested_axis == .horizontal)
774 .content_horizontal
775 else
776 .content_vertical;
777 const content = component(self.sizeFor(state_index, request, width), requested_axis);
778 const specified = preferredSize(&node, requested_axis);
779 var minimum = if (specified) |value|
780 @min(content, axis.nonNegative(value))
781 else
782 content;
783 if (limits.max) |maximum| minimum = @min(minimum, maximum);
784 return minimum;
785 }
786
787 fn sizeFor(
788 self: *@This(),
789 state_index: usize,
790 request: SizeRequest,
791 width: ?f32,
792 ) Size {
793 const input = requestInput(request, width);
794 return self.computeNode(
795 state_index,
796 input,
797 .compute_size,
798 request,
799 .{},
800 ).size;
801 }
802
803 fn measureLeaf(self: *@This(), node: *const Node, available: Available) Size {
804 const token = node.measure_token orelse return node.intrinsic_size;
805 const measurer = self.measurer orelse return node.intrinsic_size;
806 return measurer.size(token, available);
807 }
808
809 fn cachedSize(
810 self: *@This(),
811 state_index: usize,
812 request: SizeRequest,
813 input: LayoutInput,
814 ) ?Size {
815 if (!self.scratch.size_cache_enabled) {
816 self.scratch.work.size_cache_misses += 1;
817 return null;
818 }
819 if (comptime Source.flat) {
820 const index = state_index * size_request_count + @backingInt(request);
821 const slot = &self.scratch.indexed_cache[index];
822 if (slot.epoch == self.scratch.cache_epoch and
823 slot.width == cacheWidth(request, input))
824 {
825 self.scratch.work.size_cache_hits += 1;
826 return slot.size;
827 }
828 if (slot.epoch == self.scratch.cache_epoch) {
829 self.scratch.work.size_cache_conflicts += 1;
830 std.debug.assert(false);
831 }
832 self.scratch.work.size_cache_misses += 1;
833 return null;
834 }
835 const slot = &self.scratch.states[state_index].cache[@backingInt(request)];
836 if (!slot.valid) {
837 self.scratch.work.size_cache_misses += 1;
838 return null;
839 }
840 if (!sameInput(slot.input, input)) {
841 self.scratch.work.size_cache_conflicts += 1;
842 std.debug.assert(false);
843 return null;
844 }
845 self.scratch.work.size_cache_hits += 1;
846 return slot.size;
847 }
848
849 fn storeSize(
850 self: *@This(),
851 state_index: usize,
852 request: SizeRequest,
853 input: LayoutInput,
854 size: Size,
855 ) void {
856 if (!self.scratch.size_cache_enabled) return;
857 if (comptime Source.flat) {
858 const index = state_index * size_request_count + @backingInt(request);
859 self.scratch.indexed_cache[index] = .{
860 .epoch = self.scratch.cache_epoch,
861 .width = cacheWidth(request, input),
862 .size = size,
863 };
864 return;
865 }
866 const slot = &self.scratch.states[state_index].cache[@backingInt(request)];
867 if (slot.valid) {
868 if (!sameInput(slot.input, input)) {
869 self.scratch.work.size_cache_conflicts += 1;
870 std.debug.assert(false);
871 }
872 return;
873 }
874 slot.* = .{ .valid = true, .input = input, .size = size };
875 }
876 };
877 }
878
879 pub fn computeLayout(scratch: *Scratch, root: Node, available_size: Size) LayoutResult {
880 return computeLayoutInner(scratch, root, available_size, null);
881 }
882
883 pub fn computeLayoutMeasured(
884 scratch: *Scratch,
885 root: Node,
886 available_size: Size,
887 measurer: *Measurer,
888 ) LayoutResult {
889 measurer.reset();
890 return computeLayoutInner(scratch, root, available_size, measurer);
891 }
892
893 fn computeLayoutInner(
894 scratch: *Scratch,
895 root: Node,
896 available_size: Size,
897 measurer: ?*Measurer,
898 ) LayoutResult {
899 validateSize(available_size);
900 scratch.resetSolve();
901 const root_index = indexTree(scratch, &root, 0);
902 const root_size = axis.constrainSize(&root, .{
903 .width = root.size.width orelse available_size.width,
904 .height = root.size.height orelse available_size.height,
905 });
906 var solver = Solver(NestedSource){
907 .scratch = scratch,
908 .source = .{ .scratch = scratch },
909 .measurer = measurer,
910 };
911 return solver.computeNode(
912 root_index,
913 exactInput(root_size),
914 .perform_layout,
915 .settled_width,
916 .{},
917 ).layout.?;
918 }
919
920 pub fn computeLayoutIndexed(
921 scratch: *Scratch,
922 source: IndexedInput,
923 root_index: u32,
924 available_size: Size,
925 origin: Rect,
926 measurer: ?*Measurer,
927 ) Size {
928 validateSize(available_size);
929 std.debug.assert(source.rects.len >= source.count);
930 std.debug.assert(root_index < source.count);
931 std.debug.assert(scratch.indexed_cache.len >= @as(usize, source.count) * size_request_count);
932 scratch.resetSolve();
933 const root = source.node(root_index);
934 const root_size = axis.constrainSize(&root, .{
935 .width = root.size.width orelse available_size.width,
936 .height = root.size.height orelse available_size.height,
937 });
938 var solver = Solver(IndexedInput){
939 .scratch = scratch,
940 .source = source,
941 .measurer = measurer,
942 };
943 return solver.computeNode(
944 root_index,
945 exactInput(root_size),
946 .perform_layout,
947 .settled_width,
948 .{ .x = origin.x, .y = origin.y },
949 ).size;
950 }
951
952 fn indexTree(scratch: *Scratch, node: *const Node, depth: usize) usize {
953 std.debug.assert(depth < max_depth);
954 std.debug.assert(scratch.states_used < scratch.states.len);
955 const state_index = scratch.states_used;
956 scratch.states_used += 1;
957
958 std.debug.assert(scratch.child_indices_used + node.children.len <= scratch.child_indices.len);
959 const start = scratch.child_indices_used;
960 scratch.child_indices_used += node.children.len;
961 scratch.states[state_index] = .{
962 .node = node,
963 .children = scratch.child_indices[start..][0..node.children.len],
964 };
965 for (node.children, 0..) |*child, index| {
966 scratch.child_indices[start + index] = indexTree(scratch, child, depth + 1);
967 }
968 return state_index;
969 }
970
971 fn resolveBox(
972 node: *const Node,
973 input: LayoutInput,
974 mode: RunMode,
975 request: SizeRequest,
976 ) Box {
977 const padding = axis.resolvedInsets(node.style.padding);
978 const border = resolveBorder(node, input, mode, request);
979 const width_drives_children = mode == .perform_layout or
980 request == .settled_width or request == .content_vertical;
981 const child_width = if (width_drives_children)
982 subtractInsets(border.width, padding.left + padding.right)
983 else
984 null;
985 const main_limit = resolveMainLimit(node, mode, request, border, padding);
986 const cross_limit = resolveCrossLimit(node, mode, request, border, padding);
987 return .{
988 .border = border,
989 .child_width = child_width,
990 .main_limit = main_limit,
991 .cross_limit = cross_limit,
992 .padding = padding,
993 };
994 }
995
996 fn resolveBorder(
997 node: *const Node,
998 input: LayoutInput,
999 mode: RunMode,
1000 request: SizeRequest,
1001 ) Dimensions {
1002 const content_axis = requestedContentAxis(mode, request);
1003 const width = input.known.width orelse if (content_axis == .horizontal)
1004 null
1005 else
1006 constrainedPreferred(node, .horizontal);
1007 const height = input.known.height orelse if (content_axis == .vertical)
1008 null
1009 else
1010 constrainedPreferred(node, .vertical);
1011 if (input.known.width) |known| validateKnown(known);
1012 if (input.known.height) |known| validateKnown(known);
1013 return .{ .width = width, .height = height };
1014 }
1015
1016 fn resolveMainLimit(
1017 node: *const Node,
1018 mode: RunMode,
1019 request: SizeRequest,
1020 border: Dimensions,
1021 padding: axis.ResolvedInsets,
1022 ) ?f32 {
1023 const direction = node.style.flex_direction;
1024 if (mode == .perform_layout) {
1025 return subtractMainInsets(border, padding, direction);
1026 }
1027 if (direction == .column) return null;
1028 if (request != .settled_width and request != .content_vertical) return null;
1029 return subtractMainInsets(border, padding, direction);
1030 }
1031
1032 fn resolveCrossLimit(
1033 node: *const Node,
1034 mode: RunMode,
1035 request: SizeRequest,
1036 border: Dimensions,
1037 padding: axis.ResolvedInsets,
1038 ) ?f32 {
1039 const direction = node.style.flex_direction;
1040 if (mode == .perform_layout) {
1041 return subtractCrossInsets(border, padding, direction);
1042 }
1043 if (direction == .row) return null;
1044 if (request != .settled_width and request != .content_vertical) return null;
1045 return subtractCrossInsets(border, padding, direction);
1046 }
1047
1048 fn finishContainerSize(
1049 node: *const Node,
1050 box: Box,
1051 request: SizeRequest,
1052 phase: Phase,
1053 ) Size {
1054 const direction = node.style.flex_direction;
1055 const main = phaseMainExtent(phase);
1056 const cross = phaseCrossExtent(phase);
1057 const raw = switch (direction) {
1058 .row => Size{
1059 .width = main + box.padding.left + box.padding.right,
1060 .height = cross + box.padding.top + box.padding.bottom,
1061 },
1062 .column => Size{
1063 .width = cross + box.padding.left + box.padding.right,
1064 .height = main + box.padding.top + box.padding.bottom,
1065 },
1066 };
1067 return finishSize(node, request, box.border, raw);
1068 }
1069
1070 fn finishLeafSize(
1071 node: *const Node,
1072 request: SizeRequest,
1073 border: Dimensions,
1074 padding: axis.ResolvedInsets,
1075 measured: Size,
1076 ) Size {
1077 const raw = Size{
1078 .width = measured.width + padding.left + padding.right,
1079 .height = measured.height + padding.top + padding.bottom,
1080 };
1081 return finishSize(node, request, border, raw);
1082 }
1083
1084 fn finishSize(node: *const Node, request: SizeRequest, border: Dimensions, raw: Size) Size {
1085 const width = border.width orelse if (request == .content_horizontal)
1086 axis.nonNegative(raw.width)
1087 else
1088 axis.clampSize(node, .horizontal, raw.width);
1089 const height = border.height orelse if (request == .content_vertical)
1090 axis.nonNegative(raw.height)
1091 else
1092 axis.clampSize(node, .vertical, raw.height);
1093 return .{ .width = width, .height = height };
1094 }
1095
1096 fn leafAvailable(
1097 input: LayoutInput,
1098 request: SizeRequest,
1099 border: Dimensions,
1100 padding: axis.ResolvedInsets,
1101 ) Available {
1102 const horizontal = padding.left + padding.right;
1103 const vertical = padding.top + padding.bottom;
1104 return .{
1105 .width = leafSpace(
1106 border.width,
1107 input.available.width,
1108 request == .content_horizontal,
1109 horizontal,
1110 ),
1111 .height = leafSpace(
1112 border.height,
1113 input.available.height,
1114 request == .content_vertical,
1115 vertical,
1116 ),
1117 };
1118 }
1119
1120 fn leafSpace(
1121 known: ?f32,
1122 available: AvailableSpace,
1123 minimum: bool,
1124 padding: f32,
1125 ) AvailableSpace {
1126 if (known) |value| return .{ .definite = @max(value - padding, 0) };
1127 if (minimum) return .min_content;
1128 return switch (available) {
1129 .definite => |value| .{ .definite = @max(value - padding, 0) },
1130 else => available,
1131 };
1132 }
1133
1134 fn metricFromSize(
1135 state_index: usize,
1136 index: usize,
1137 child: *const Node,
1138 measured: Size,
1139 direction: types.FlexDirection,
1140 ) flow.ChildMetrics {
1141 const limits = axis.axisLimits(child, axis.mainAxis(direction));
1142 const base_main = sizing.resolveFlexBaseSize(child, measured, direction);
1143 return .{
1144 .index = index,
1145 .state_index = state_index,
1146 .base_main = base_main,
1147 .base_cross = sizing.resolvePreferredCrossSize(child, measured, direction),
1148 .target_main = base_main,
1149 .min_main = limits.min,
1150 .max_main = limits.max,
1151 .flex_grow = axis.nonNegative(child.style.flex_grow),
1152 .flex_shrink = axis.nonNegative(child.style.flex_shrink),
1153 };
1154 }
1155
1156 fn multilineMinimumContribution(
1157 child: *const Node,
1158 content: f32,
1159 maximum: Size,
1160 direction: types.FlexDirection,
1161 ) f32 {
1162 const base = sizing.resolveFlexBaseSize(child, maximum, direction);
1163 var contribution = content;
1164 if (axis.nonNegative(child.style.flex_grow) == 0) {
1165 contribution = @min(contribution, base);
1166 }
1167 if (axis.nonNegative(child.style.flex_shrink) == 0) {
1168 contribution = @max(contribution, base);
1169 }
1170 return axis.clampSize(child, axis.mainAxis(direction), contribution);
1171 }
1172
1173 fn requestedContentAxis(mode: RunMode, request: SizeRequest) ?axis.Axis {
1174 if (mode == .perform_layout) return null;
1175 return switch (request) {
1176 .content_horizontal => .horizontal,
1177 .content_vertical => .vertical,
1178 else => null,
1179 };
1180 }
1181
1182 fn requestsMainMinimum(
1183 mode: RunMode,
1184 request: SizeRequest,
1185 direction: types.FlexDirection,
1186 ) bool {
1187 const requested_axis = requestedContentAxis(mode, request) orelse return false;
1188 return requested_axis == axis.mainAxis(direction);
1189 }
1190
1191 fn requestInput(request: SizeRequest, width: ?f32) LayoutInput {
1192 return switch (request) {
1193 .max_content => .{},
1194 .settled_width => .{ .known = .{ .width = requiredWidth(width) } },
1195 .content_horizontal => .{ .available = .{ .width = .min_content } },
1196 .content_vertical => .{
1197 .known = .{ .width = requiredWidth(width) },
1198 .available = .{ .height = .min_content },
1199 },
1200 };
1201 }
1202
1203 fn cacheWidth(request: SizeRequest, input: LayoutInput) f32 {
1204 return switch (request) {
1205 .max_content, .content_horizontal => blk: {
1206 std.debug.assert(input.known.width == null);
1207 break :blk 0;
1208 },
1209 .settled_width, .content_vertical => input.known.width.?,
1210 };
1211 }
1212
1213 fn exactInput(size: Size) LayoutInput {
1214 return .{
1215 .known = .{ .width = size.width, .height = size.height },
1216 .available = .{
1217 .width = .{ .definite = size.width },
1218 .height = .{ .definite = size.height },
1219 },
1220 };
1221 }
1222
1223 fn sameInput(left: LayoutInput, right: LayoutInput) bool {
1224 return sameOptional(left.known.width, right.known.width) and
1225 sameOptional(left.known.height, right.known.height) and
1226 sameSpace(left.available.width, right.available.width) and
1227 sameSpace(left.available.height, right.available.height);
1228 }
1229
1230 fn sameOptional(left: ?f32, right: ?f32) bool {
1231 if (left) |value| return right != null and value == right.?;
1232 return right == null;
1233 }
1234
1235 fn sameSpace(left: AvailableSpace, right: AvailableSpace) bool {
1236 return switch (left) {
1237 .definite => |value| switch (right) {
1238 .definite => |other| value == other,
1239 else => false,
1240 },
1241 .min_content => right == .min_content,
1242 .max_content => right == .max_content,
1243 };
1244 }
1245
1246 fn phaseMainExtent(phase: Phase) f32 {
1247 if (phase.main_limit) |limit| return limit;
1248 var largest: f32 = 0;
1249 for (phase.lines) |*line| {
1250 largest = @max(largest, lineMainExtent(line, phase.gap));
1251 }
1252 return largest;
1253 }
1254
1255 fn phaseCrossExtent(phase: Phase) f32 {
1256 var extent: f32 = 0;
1257 for (phase.lines, 0..) |line, index| {
1258 if (index != 0) extent += phase.gap;
1259 extent += line.cross_size;
1260 }
1261 return extent;
1262 }
1263
1264 fn lineMainExtent(line: *const flow.Line, gap: f32) f32 {
1265 var extent: f32 = 0;
1266 for (line.items, 0..) |item, index| {
1267 if (index != 0) extent += gap;
1268 extent += item.target_main;
1269 }
1270 return extent;
1271 }
1272
1273 fn resolvedCross(
1274 child: *const Node,
1275 item: *const flow.ChildMetrics,
1276 line_cross: f32,
1277 direction: types.FlexDirection,
1278 alignment: types.AlignItems,
1279 ) f32 {
1280 const desired = if (direction == .row and
1281 alignment == .stretch and
1282 !sizing.hasExplicitCrossSize(child, direction))
1283 line_cross
1284 else
1285 item.base_cross;
1286 const contained = @min(desired, line_cross);
1287 return axis.clampSize(child, axis.crossAxis(direction), contained);
1288 }
1289
1290 fn alignmentOffset(alignment: types.AlignItems, line_cross: f32, child_cross: f32) f32 {
1291 return switch (alignment) {
1292 .flex_start, .stretch => 0,
1293 .flex_end => line_cross - child_cross,
1294 .center => (line_cross - child_cross) / 2,
1295 };
1296 }
1297
1298 fn insetSize(container: f32, start: ?f32, end: ?f32) ?f32 {
1299 if (start == null or end == null) return null;
1300 return @max(container - start.? - end.?, 0);
1301 }
1302
1303 fn preferredSize(node: *const Node, requested_axis: axis.Axis) ?f32 {
1304 return switch (requested_axis) {
1305 .horizontal => node.size.width,
1306 .vertical => node.size.height,
1307 };
1308 }
1309
1310 fn explicitMinimum(node: *const Node, requested_axis: axis.Axis) ?f32 {
1311 return switch (requested_axis) {
1312 .horizontal => node.style.constraints.min_width,
1313 .vertical => node.style.constraints.min_height,
1314 };
1315 }
1316
1317 fn clipsAxis(node: *const Node, requested_axis: axis.Axis) bool {
1318 return switch (requested_axis) {
1319 .horizontal => node.clip_x,
1320 .vertical => node.clip_y,
1321 };
1322 }
1323
1324 fn constrainedPreferred(node: *const Node, requested_axis: axis.Axis) ?f32 {
1325 const preferred = preferredSize(node, requested_axis) orelse return null;
1326 return axis.clampSize(node, requested_axis, preferred);
1327 }
1328
1329 fn component(size: Size, requested_axis: axis.Axis) f32 {
1330 return switch (requested_axis) {
1331 .horizontal => size.width,
1332 .vertical => size.height,
1333 };
1334 }
1335
1336 fn subtractInsets(size: ?f32, padding: f32) ?f32 {
1337 return if (size) |value| @max(value - padding, 0) else null;
1338 }
1339
1340 fn subtractMainInsets(
1341 border: Dimensions,
1342 padding: axis.ResolvedInsets,
1343 direction: types.FlexDirection,
1344 ) ?f32 {
1345 return switch (direction) {
1346 .row => subtractInsets(border.width, padding.left + padding.right),
1347 .column => subtractInsets(border.height, padding.top + padding.bottom),
1348 };
1349 }
1350
1351 fn subtractCrossInsets(
1352 border: Dimensions,
1353 padding: axis.ResolvedInsets,
1354 direction: types.FlexDirection,
1355 ) ?f32 {
1356 return switch (direction) {
1357 .row => subtractInsets(border.height, padding.top + padding.bottom),
1358 .column => subtractInsets(border.width, padding.left + padding.right),
1359 };
1360 }
1361
1362 fn rectAt(origin: Point, size: Size) Rect {
1363 return .{ .x = origin.x, .y = origin.y, .width = size.width, .height = size.height };
1364 }
1365
1366 fn requiredWidth(width: ?f32) f32 {
1367 const value = width orelse unreachable;
1368 validateKnown(value);
1369 return value;
1370 }
1371
1372 fn validateKnown(value: f32) void {
1373 std.debug.assert(std.math.isFinite(value));
1374 std.debug.assert(value >= 0);
1375 }
1376
1377 fn validateSize(size: Size) void {
1378 validateKnown(size.width);
1379 validateKnown(size.height);
1380 }