1use crate::{
2 Anchor, Axis, Built, Flags, ICON, ICON_GAP, Id, Overflow, Size, State, fitting, popup::PAD,
3 text::Texts,
4};
5use std::collections::HashMap;
6
7/// Sizes each box on both axes, then places it: standalone sizes, sizes taken from
8/// ancestors (pre-order), sizes summed from children (post-order), overflow taken back
9/// (by folding a row's groups for what space sized by ancestors can't give, then from that
10/// space, then from the least strict boxes first), and positions along each parent's flow. Labels too wide for their
11/// solved width wrap or shorten before heights are solved. Boxes are in build order, so a
12/// parent comes before its children. The interface is solved first, then each popup in
13/// turn beside its anchor's box as laid out by then, or as last laid out where not yet.
14pub(crate) fn solve(
15 nodes: &mut [Built],
16 states: &HashMap<Id, State>,
17 scale: f32,
18 texts: &mut Texts,
19 frame: u64,
20) {
21 for index in 0..nodes.len() {
22 if nodes[index].fold.is_some() {
23 let folded = nodes[index].children[1];
24 nodes[folded].hidden = true;
25 }
26 }
27 // The popup each box lies in, by the popup's index; 0 for the interface beneath.
28 let mut popup = vec![0; nodes.len()];
29 for index in 1..nodes.len() {
30 popup[index] = match nodes[index].anchor {
31 Some(_) => index,
32 None => popup[nodes[index].parent],
33 };
34 }
35 let members = |group: usize| -> Vec<usize> {
36 (0..popup.len())
37 .filter(|index| popup[*index] == group)
38 .collect()
39 };
40 solve_group(nodes, &members(0), states, scale, texts, frame);
41 for group in 1..nodes.len() {
42 if popup[group] == group {
43 resolve(nodes, &popup, group, states);
44 solve_group(nodes, &members(group), states, scale, texts, frame);
45 }
46 }
47}
48
49/// Finds where popup `index` opens from its anchor's box, laid out before it in `popup`'s
50/// order, or as last laid out, and what it takes from the box: a popup below or over it is
51/// at least as wide, and what holds still in a popup over it stands in for it as tall.
52fn resolve(nodes: &mut [Built], popup: &[usize], index: usize, states: &HashMap<Id, State>) {
53 let node = &nodes[index];
54 let anchor = node.anchor.expect("a popup has an anchor");
55 let laid_out = |id: Id| {
56 let found = (1..nodes.len()).find(|at| nodes[*at].id == id && popup[*at] < index);
57 found
58 .map(|at| (nodes[at].rect, popup[at]))
59 .or_else(|| Some((states.get(&id)?.rect?, 0)))
60 };
61 let [pad_x, pad_y] = node.pad;
62 let around = match anchor {
63 Anchor::Point([x, y]) => [x, y, x, y],
64 Anchor::Dialog | Anchor::Top => [0.0; 4],
65 Anchor::Below(id)
66 | Anchor::Tip(id)
67 | Anchor::Right(id)
68 | Anchor::Over(id)
69 | Anchor::Dock(id) => {
70 let (rect, holder) = laid_out(id).unwrap_or_default();
71 let [left, top, right, bottom] = rect;
72 match anchor {
73 Anchor::Right(_) => {
74 let [left, _, right, _] = if holder == 0 {
75 rect
76 } else {
77 nodes[holder].rect
78 };
79 [left, top - pad_y, right, bottom + pad_y]
80 }
81 Anchor::Over(_) => [left - pad_x, top - pad_y, right + pad_x, bottom + pad_y],
82 Anchor::Dock(_) => rect,
83 _ => [left, top - PAD, right, bottom + PAD],
84 }
85 }
86 };
87 let node = &mut nodes[index];
88 node.around = around;
89 if let (Some(Anchor::Below(_) | Anchor::Over(_)), Size::Pixels(width)) =
90 (node.anchor, node.size[0].size)
91 {
92 node.size[0].size = Size::Pixels(width.max(around[2] - around[0]));
93 }
94 if let Anchor::Over(_) = anchor {
95 let height = around[3] - around[1] - 2.0 * pad_y;
96 for at in index..nodes.len() {
97 if popup[at] == index && nodes[at].flags.contains(Flags::STILL) {
98 nodes[at].size[1].size = Size::Pixels(height);
99 }
100 }
101 }
102}
103
104/// Solves the boxes `members`, the interface or a popup and what it holds, in build order.
105fn solve_group(
106 nodes: &mut [Built],
107 members: &[usize],
108 states: &HashMap<Id, State>,
109 scale: f32,
110 texts: &mut Texts,
111 frame: u64,
112) {
113 for axis in 0..2 {
114 if axis == 1 {
115 fit_labels(nodes, members, texts, frame);
116 }
117 for &index in members {
118 let node = &mut nodes[index];
119 node.computed[axis] = match node.size[axis].size {
120 Size::Pixels(pixels) => match node.anchor {
121 Some(Anchor::Over(_)) if axis == 0 => {
122 let from = node.around[2] - node.around[0];
123 from + (pixels - from) * node.open
124 }
125 _ => pixels,
126 },
127 Size::Text => {
128 let content = if axis == 0 {
129 node.content_width()
130 } else {
131 let label = node.label.as_ref().map_or(0.0, |label| label.size[1]);
132 if node.icon.is_some() || node.image.is_some() {
133 label.max(crate::ICON)
134 } else {
135 label
136 }
137 };
138 content + 2.0 * node.pad[axis]
139 }
140 Size::Fraction(_) | Size::Children => 0.0,
141 };
142 }
143 fit_popups(nodes, members, axis);
144 for &index in members.iter().filter(|index| **index != 0) {
145 if let Size::Fraction(fraction) = nodes[index].size[axis].size {
146 if stretches(nodes, index, axis) {
147 nodes[index].computed[axis] = 0.0;
148 continue;
149 }
150 let mut ancestor = nodes[index].parent;
151 while ancestor != 0 && nodes[ancestor].size[axis].size == Size::Children {
152 ancestor = nodes[ancestor].parent;
153 }
154 let room = across(nodes, ancestor, index, axis) - 2.0 * nodes[ancestor].pad[axis];
155 nodes[index].computed[axis] = room.max(0.0) * fraction;
156 }
157 }
158 for &index in members.iter().rev() {
159 if nodes[index].size[axis].size == Size::Children {
160 let content = flow(nodes, index, axis);
161 nodes[index].computed[axis] = content + 2.0 * nodes[index].pad[axis];
162 }
163 }
164 yield_popups(nodes, members, axis);
165 fit_popups(nodes, members, axis);
166 for &index in members {
167 let node = &nodes[index];
168 if node.children.is_empty() || (axis == 1 && node.flags.contains(Flags::SCROLL)) {
169 continue;
170 }
171 let room = (node.computed[axis] - 2.0 * node.pad[axis]).max(0.0);
172 let children: Vec<_> = in_flow(nodes, index).collect();
173 if along(node, axis) {
174 let space =
175 |child: &&usize| matches!(nodes[**child].size[axis].size, Size::Fraction(_));
176 let (space, sized): (Vec<usize>, Vec<_>) = children.iter().partition(space);
177 let mut excess = flow(nodes, index, axis) - room;
178 // Groups fold only for what the space can't give, so the room a fold frees
179 // goes back to the space.
180 let spare: f32 = space.iter().map(|child| nodes[*child].computed[axis]).sum();
181 while excess > spare && axis == 0 {
182 let mut groups = Vec::new();
183 unfolded(nodes, &children, &mut groups);
184 let Some(group) = groups.into_iter().min_by_key(|group| nodes[*group].fold)
185 else {
186 break;
187 };
188 let [full, folded] = [nodes[group].children[0], nodes[group].children[1]];
189 nodes[full].hidden = true;
190 nodes[folded].hidden = false;
191 let width = nodes[folded].computed[0] + 2.0 * nodes[group].pad[0];
192 let freed = nodes[group].computed[0] - width;
193 excess -= freed;
194 // A group inside boxes sized by their children narrows them too.
195 let mut inside = group;
196 while inside != index {
197 nodes[inside].computed[0] -= freed;
198 inside = nodes[inside].parent;
199 }
200 }
201 excess = give_back(nodes, &space, axis, excess);
202 let mut tiers: Vec<f32> = sized
203 .iter()
204 .map(|child| strictness(nodes, *child, axis))
205 .filter(|strictness| *strictness < 1.0)
206 .collect();
207 tiers.sort_by(f32::total_cmp);
208 tiers.dedup();
209 for tier in tiers {
210 let members: Vec<_> = sized
211 .iter()
212 .copied()
213 .filter(|child| strictness(nodes, *child, axis) == tier)
214 .collect();
215 excess = give_back(nodes, &members, axis, excess);
216 }
217 } else {
218 for child in children {
219 let room =
220 (across(nodes, index, child, axis) - 2.0 * nodes[index].pad[axis]).max(0.0);
221 if let Size::Fraction(fraction) = nodes[child].size[axis].size
222 && stretches(nodes, child, axis)
223 {
224 nodes[child].computed[axis] = room * fraction;
225 continue;
226 }
227 let over = nodes[child].computed[axis] - room;
228 if over > 0.0 {
229 nodes[child].computed[axis] -=
230 over * (1.0 - strictness(nodes, child, axis));
231 }
232 }
233 }
234 }
235 let window = nodes[0].computed[axis];
236 for &index in members {
237 let node = &nodes[index];
238 if let Some(anchor) = node.anchor {
239 let shown = node.computed[axis];
240 let size = match node.size[axis].size {
241 Size::Pixels(pixels) => pixels,
242 _ => shown,
243 };
244 nodes[index].relative[axis] = anchor.place(node.around, axis, size, shown, window);
245 }
246 let mut cursor = nodes[index].pad[axis];
247 // Where a popup widening over its anchor lays its children out, from where it is.
248 let shift = match (nodes[index].anchor, nodes[index].size[axis].size) {
249 (Some(anchor @ Anchor::Over(_)), Size::Pixels(full)) if axis == 0 => {
250 let around = nodes[index].around;
251 anchor.place(around, axis, full, full, window) - nodes[index].relative[axis]
252 }
253 _ => 0.0,
254 };
255 for child in nodes[index].children.clone() {
256 if nodes[child].anchor.is_some() {
257 continue;
258 }
259 nodes[child].relative[axis] = if nodes[child].flags.contains(Flags::FLOAT) {
260 nodes[child].position[axis]
261 } else if nodes[child].hidden {
262 nodes[index].pad[axis]
263 } else if along(&nodes[index], axis) {
264 let at = cursor;
265 cursor += nodes[child].computed[axis] + nodes[index].gap;
266 at
267 } else {
268 nodes[index].pad[axis]
269 };
270 if !nodes[child].flags.contains(Flags::STILL) {
271 nodes[child].relative[axis] += shift;
272 }
273 }
274 if axis == 1 {
275 nodes[index].content = flow(nodes, index, axis) + 2.0 * nodes[index].pad[axis];
276 }
277 }
278 }
279 let snap = |value: f32| (value * scale).round() / scale;
280 for &index in members {
281 if index == 0 {
282 let [width, height] = nodes[0].computed;
283 nodes[0].rect = [0.0, 0.0, snap(width), snap(height)];
284 continue;
285 }
286 let parent = nodes[index].parent;
287 if nodes[index].hidden || nodes[parent].hidden {
288 nodes[index].hidden = true;
289 nodes[index].rect = nodes[parent].rect;
290 continue;
291 }
292 let parent = &nodes[parent];
293 let scroll =
294 if parent.flags.contains(Flags::SCROLL) && !nodes[index].flags.contains(Flags::FLOAT) {
295 states.get(&parent.id).map_or(0.0, |state| state.scroll)
296 } else {
297 0.0
298 };
299 let [dx, dy] = nodes[index].offset;
300 let x = parent.rect[0] + nodes[index].relative[0] + dx;
301 let y = parent.rect[1] + nodes[index].relative[1] - scroll + dy;
302 nodes[index].rect = [
303 snap(x),
304 snap(y),
305 snap(x + nodes[index].computed[0]),
306 snap(y + nodes[index].computed[1]),
307 ];
308 }
309}
310
311/// Whether `index`, sized from an ancestor, is across a parent sized by its children: it takes
312/// no room while the parent sums its other children, then that share of the parent's room.
313fn stretches(nodes: &[Built], index: usize, axis: usize) -> bool {
314 let node = &nodes[index];
315 let parent = &nodes[node.parent];
316 index != 0
317 && parent.size[axis].size == Size::Children
318 && !along(parent, axis)
319 && !(axis == 1 && parent.flags.contains(Flags::SCROLL))
320 && !node.flags.contains(Flags::FLOAT)
321 && node.anchor.is_none()
322}
323
324/// Lets each popup sized loosely give way to the window, as far as its strictness lets it:
325/// a dialog keeps below it the margin it opens under.
326fn yield_popups(nodes: &mut [Built], members: &[usize], axis: usize) {
327 let window = nodes[0].computed[axis];
328 for &index in members {
329 let node = &mut nodes[index];
330 let room = match node.anchor {
331 None => continue,
332 Some(Anchor::Dialog | Anchor::Top) if axis == 1 => window * 3.0 / 4.0,
333 Some(_) => fitting(window),
334 };
335 let over = node.computed[axis] - room;
336 if over > 0.0 {
337 node.computed[axis] -= over * (1.0 - node.size[axis].strictness.clamp(0.0, 1.0));
338 }
339 }
340}
341
342/// Shrinks each popup longer than the window lets it be on `axis`; one cut short vertically
343/// scrolls what it holds.
344fn fit_popups(nodes: &mut [Built], members: &[usize], axis: usize) {
345 let most = fitting(nodes[0].computed[axis]);
346 for &index in members {
347 let node = &mut nodes[index];
348 if node.anchor.is_some() && node.computed[axis] > most {
349 node.computed[axis] = most;
350 if axis == 1 {
351 node.flags = node.flags | Flags::SCROLL | Flags::CLIP;
352 }
353 }
354 }
355}
356
357/// The length `parent` lays `child` out across: a popup widening over its anchor lays its
358/// contents out at its full width, but for boxes standing in for the anchor, which widen with it.
359fn across(nodes: &[Built], parent: usize, child: usize, axis: usize) -> f32 {
360 let node = &nodes[parent];
361 match (node.anchor, node.size[axis].size) {
362 (Some(Anchor::Over(_)), Size::Pixels(full))
363 if axis == 0 && !nodes[child].flags.contains(Flags::STILL) =>
364 {
365 full.min(fitting(nodes[0].computed[axis]))
366 }
367 _ => node.computed[axis],
368 }
369}
370
371/// Takes up to `excess` back from `boxes`, each giving in proportion to what its strictness
372/// lets it, and returns what is left.
373fn give_back(nodes: &mut [Built], boxes: &[usize], axis: usize, excess: f32) -> f32 {
374 let give = |nodes: &[Built], child: usize| {
375 nodes[child].computed[axis] * (1.0 - strictness(nodes, child, axis))
376 };
377 let total: f32 = boxes.iter().map(|child| give(nodes, *child)).sum();
378 if excess <= 0.0 || total <= 0.0 {
379 return excess;
380 }
381 let taken = excess.min(total);
382 for child in boxes {
383 nodes[*child].computed[axis] -= taken * give(nodes, *child) / total;
384 }
385 excess - taken
386}
387
388fn along(node: &Built, axis: usize) -> bool {
389 (node.axis == Axis::Y) == (axis == 1)
390}
391
392/// The share of its size a box keeps when its siblings overflow. A box sized by the children
393/// along its flow keeps what they keep.
394fn strictness(nodes: &[Built], index: usize, axis: usize) -> f32 {
395 let node = &nodes[index];
396 let declared = node.size[axis].strictness.clamp(0.0, 1.0);
397 if node.size[axis].size != Size::Children || !along(node, axis) || node.computed[axis] <= 0.0 {
398 return declared;
399 }
400 let give: f32 = in_flow(nodes, index)
401 .map(|child| nodes[child].computed[axis] * (1.0 - strictness(nodes, child, axis)))
402 .sum();
403 declared.min(1.0 - give / node.computed[axis])
404}
405
406fn in_flow(nodes: &[Built], index: usize) -> impl Iterator<Item = usize> + '_ {
407 nodes[index].children.iter().copied().filter(|child| {
408 !nodes[*child].flags.contains(Flags::FLOAT)
409 && nodes[*child].anchor.is_none()
410 && !nodes[*child].hidden
411 })
412}
413
414/// The groups among `boxes` still in their full form, and those inside any of them that is a
415/// row sized by its children, whose width follows theirs.
416fn unfolded(nodes: &[Built], boxes: &[usize], groups: &mut Vec<usize>) {
417 for &child in boxes {
418 let node = &nodes[child];
419 if node.fold.is_some() {
420 if !nodes[node.children[0]].hidden {
421 groups.push(child);
422 }
423 } else if node.size[0].size == Size::Children && node.axis == Axis::X {
424 unfolded(nodes, &in_flow(nodes, child).collect::<Vec<_>>(), groups);
425 }
426 }
427}
428
429/// The children's extent on `axis`: summed with gaps along the flow, otherwise the largest.
430fn flow(nodes: &[Built], index: usize, axis: usize) -> f32 {
431 let sizes = in_flow(nodes, index).map(|child| nodes[child].computed[axis]);
432 span(&nodes[index], axis, sizes)
433}
434
435/// The extent of children `sizes` long on `axis` of `node`, as `flow` measures it.
436fn span(node: &Built, axis: usize, sizes: impl Iterator<Item = f32>) -> f32 {
437 if along(node, axis) {
438 let (sum, count) = sizes.fold((0.0, 0), |(sum, count), size| (sum + size, count + 1));
439 sum + node.gap * (count.max(1) - 1) as f32
440 } else {
441 sizes.fold(0.0, f32::max)
442 }
443}
444
445/// The least width `index`'s children fit in, with its padding: each row's groups folded, and
446/// each box sized on its own yielding all its strictness lets it.
447pub(crate) fn narrowest(nodes: &[Built], index: usize) -> f32 {
448 let node = &nodes[index];
449 let sizes = node
450 .children
451 .iter()
452 .filter(|child| {
453 !nodes[**child].flags.contains(Flags::FLOAT) && nodes[**child].anchor.is_none()
454 })
455 .map(|child| least(nodes, *child));
456 span(node, 0, sizes) + 2.0 * node.pad[0]
457}
458
459/// The least width `index` takes without clipping its children.
460fn least(nodes: &[Built], index: usize) -> f32 {
461 let node = &nodes[index];
462 if node.fold.is_some() {
463 return least(nodes, node.children[1]) + 2.0 * node.pad[0];
464 }
465 let own = match node.size[0].size {
466 Size::Pixels(pixels) => pixels,
467 Size::Text => node.content_width() + 2.0 * node.pad[0],
468 Size::Fraction(_) | Size::Children => return narrowest(nodes, index),
469 };
470 own * node.size[0].strictness.clamp(0.0, 1.0)
471}
472
473fn fit_labels(nodes: &mut [Built], members: &[usize], texts: &mut Texts, frame: u64) {
474 for &index in members {
475 let node = &mut nodes[index];
476 let Some(label) = node.label.clone() else {
477 continue;
478 };
479 let icon = if node.icon.is_some() || node.image.is_some() {
480 ICON + ICON_GAP
481 } else {
482 0.0
483 };
484 let [left, _, right, _] = node.inset;
485 let width = (node.computed[0] - left - right - 2.0 * node.pad[0] - icon).max(0.0);
486 if label.size[0] <= width {
487 continue;
488 }
489 node.label = match node.overflow {
490 Overflow::Clip => continue,
491 Overflow::Wrap => Some(label.wrapped(width, node.center)),
492 Overflow::Ellipsis => Some(texts.ellipsis(&label, width, frame)),
493 };
494 }
495}