1// Package layout computes logical-pixel boxes and an ordered, serializable paint list.
2// Input nodes and CSS styles are borrowed for one synchronous Layout call.
3package layout
4
5import (
6 "errors"
7 "image"
8 "math"
9 "slices"
10
11 "github.com/bnema/nefergui/internal/css"
12 "github.com/bnema/nefergui/internal/text"
13 "github.com/go-text/typesetting/di"
14)
15
16// Kind selects intrinsic and container behavior. CSS display:none suppresses all kinds;
17// display:flex takes precedence over Kind, and row/column flex defaults are overridable.
18type Kind string
19
20const (
21 Box Kind = "box"
22 Row Kind = "row"
23 Column Kind = "column"
24 Stack Kind = "stack"
25 Scroll Kind = "scroll"
26 Text Kind = "text"
27 Image Kind = "image"
28)
29const limit = 1 << 24
30
31// Rect uses logical pixels, including fractional positions.
32type Rect struct{ X, Y, W, H float64 }
33
34func (r Rect) Contains(x, y float64) bool { return x >= r.X && y >= r.Y && x < r.X+r.W && y < r.Y+r.H }
35func (r Rect) intersect(q Rect) Rect {
36 x := math.Max(r.X, q.X)
37 y := math.Max(r.Y, q.Y)
38 return Rect{x, y, math.Max(0, math.Min(r.X+r.W, q.X+q.W)-x), math.Max(0, math.Min(r.Y+r.H, q.Y+q.H)-y)}
39}
40func safe(v float64) float64 {
41 if math.IsNaN(v) || v < 0 {
42 return 0
43 }
44 if math.IsInf(v, 0) || v > limit {
45 return limit
46 }
47 return v
48}
49func coord(v float64) float64 {
50 if math.IsNaN(v) {
51 return 0
52 }
53 if math.IsInf(v, 1) {
54 return limit
55 }
56 if math.IsInf(v, -1) {
57 return -limit
58 }
59 return math.Max(-limit, math.Min(limit, v))
60}
61func length(l css.Length, basis float64) (float64, bool) {
62 switch l.Unit {
63 case "px":
64 return coord(l.Value), true
65 case "%":
66 return coord(safe(basis) * l.Value / 100), true
67 }
68 return 0, false
69}
70func positive(l css.Length, basis float64) float64 { v, _ := length(l, basis); return safe(v) }
71func edges(s css.LengthSides, basis float64) Edges {
72 return Edges{coordValue(s.Top, basis), coordValue(s.Right, basis), coordValue(s.Bottom, basis), coordValue(s.Left, basis)}
73}
74func coordValue(l css.Length, basis float64) float64 { v, _ := length(l, basis); return v }
75
76// Edges are in top/right/bottom/left order.
77type Edges struct{ Top, Right, Bottom, Left float64 }
78
79func (e Edges) horizontal() float64 { return e.Left + e.Right }
80func (e Edges) vertical() float64 { return e.Top + e.Bottom }
81func nonnegative(e Edges) Edges {
82 return Edges{safe(e.Top), safe(e.Right), safe(e.Bottom), safe(e.Left)}
83}
84
85// Measure receives the available content width (zero means unbounded), and must
86// return finite logical dimensions and optionally shaped lines. It may return an error.
87// TextEngine, when supplied, is used for Text nodes without an explicit callback.
88type Measure func(width float64) (Size, []text.Line, error)
89type Size struct{ W, H float64 }
90
91// Node has no parent pointers or renderer resources. ID identifies hit targets and
92// display commands; callers must supply stable, unique IDs if they need identity.
93// ImageSize is the decoded image's intrinsic size; image ownership remains with caller.
94// Image is borrowed through painting. Treat it as immutable while passed to Image:
95// pass a new image value to change pixels. Renderer cache identity requires a
96// comparable image.Image interface value (for example, *image.RGBA).
97type Node struct {
98 ID string
99 Kind Kind
100 Style *css.Style
101 Children []*Node
102 Content string
103 ImageSize Size
104 Image image.Image `json:"-"`
105 Measure Measure `json:"-"`
106 ScrollX, ScrollY float64
107 NoWrap bool // measure text at unbounded width; useful for single-line editors
108 EditorScroll bool // clip and clamp own text on both axes, without child scrolling
109 // Rect, when HasRect is set on a direct child of a Stack, is the child's
110 // border-box geometry relative to the Stack's content box. It replaces the
111 // child's authored width, height and margin; it is ignored elsewhere.
112 // A flex-styled Stack with a visible Rect child is rejected.
113 Rect Rect
114 HasRect bool
115}
116
117// Result is a detached layout snapshot. Style is deliberately not retained.
118type Result struct {
119 ID string
120 Kind Kind
121 Border, Content, Clip Rect
122 Margin, Padding, BorderWidths Edges
123 ContentSize Size
124 ScrollX, ScrollY float64
125 Lines []text.Line `json:"-"`
126 Children []*Result
127 Clipped bool
128}
129
130// Command is a paint operation. Text line ranges refer to rune offsets
131// in Text; image pixels are borrowed and excluded from serialized display lists.
132type Command struct {
133 Op string
134 ID string
135 Rect Rect
136 Color css.Color
137 Opacity float64
138 Widths Edges
139 Colors css.ColorSides
140 Radii [4]float64
141 Shadow *css.Shadow `json:",omitempty"`
142 Text string `json:",omitempty"`
143 Runs []Run `json:",omitempty"`
144 Image image.Image `json:"-"`
145}
146type Run struct {
147 Start, End int
148 X, Y, Advance float64
149 // Face is borrowed for in-process rasterization. FaceID and Size preserve
150 // the shaping identity and logical pixel size in serialized display lists.
151 Face *text.Face `json:"-"`
152 FaceID string
153 Size float64
154 Glyphs []Glyph
155}
156type Glyph struct {
157 ID uint32
158 X, Y, Advance float64
159 Cluster int
160}
161
162// Output contains a JSON-safe tree and paint list in back-to-front command order.
163type Output struct {
164 Tree *Result
165 Display []Command
166}
167
168// Options provide logical viewport size and an optional text shaping engine.
169// Arena, when set, supplies reusable storage for the Output.
170type Options struct {
171 Width, Height float64
172 TextEngine *text.Engine
173 Arena *Arena
174}
175
176// Arena holds the result tree and display storage of one Output, so a steady
177// layout reuses it instead of allocating. An Output stays valid until its
178// arena is passed to Layout again; alternate two arenas to keep the previous
179// Output readable while building the next.
180type Arena struct {
181 results slab[Result]
182 children slab[*Result]
183 commands []Command
184 kept int // length of the last list passed to Keep, until the next Keep
185 // Flex scratch: valid during one Layout call only.
186 flexItems slab[flexItem]
187 flexEnds slab[int]
188 shadows slab[css.Shadow]
189 runs slab[Run]
190 glyphs slab[Glyph]
191}
192
193// Keep makes display, the Output.Display of the arena's last Layout after the
194// caller appended to it, the list the arena recycles next. Without it, a list
195// that outgrew its arena block is reallocated by the caller every frame.
196func (a *Arena) Keep(display []Command) {
197 if cap(display) > cap(a.commands) {
198 a.commands = display[:0]
199 }
200 a.kept = len(display)
201}
202
203var ErrDepth = errors.New("layout: tree depth exceeds 256")
204
205// Layout does not mutate inputs. The caller must not create cycles in the node tree.
206func Layout(root *Node, options Options) (Output, error) {
207 if root == nil {
208 return Output{}, nil
209 }
210 ctx := newContext(options)
211 viewport := Rect{0, 0, safe(options.Width), safe(options.Height)}
212 tree, err := ctx.place(root, viewport.X, viewport.Y, viewport.W, viewport.H, nil, nil, 0)
213 if err != nil {
214 return Output{}, err
215 }
216 out := Output{Tree: tree}
217 out.Display = ctx.display(root, tree)
218 return out, nil
219}
220
221// display paints the placed tree into a list sized once from the tree.
222func (c context) display(root *Node, tree *Result) []Command {
223 n := countCommands(root, tree)
224 a := c.arena
225 // Size by what the list held last time, so caller decorations do not make
226 // a kept list look oversized and get dropped every frame.
227 need := max(n.commands, a.kept)
228 if oversized(cap(a.commands), need) {
229 a.commands = nil // do not pin one huge frame's list
230 } else {
231 clear(a.commands[:cap(a.commands)]) // callers may have appended in place
232 }
233 a.shadows.reset(n.shadows)
234 a.runs.reset(n.runs)
235 a.glyphs.reset(n.glyphs)
236 if n.commands == 0 {
237 return nil
238 }
239 out := slices.Grow(a.commands[:0], n.commands)
240 c.paint(root, tree, &out)
241 a.commands = out
242 return out
243}
244
245type context struct {
246 options Options
247 arena *Arena // storage for results and display; never nil
248}
249
250// newContext recycles options.Arena, or uses a fresh one.
251func newContext(options Options) context {
252 arena := options.Arena
253 if arena == nil {
254 arena = new(Arena)
255 }
256 // The tree size is only known after placing it: size by the last demand.
257 arena.results.reset(arena.results.need)
258 arena.children.reset(arena.children.need)
259 arena.flexItems.reset(arena.flexItems.need)
260 arena.flexEnds.reset(arena.flexEnds.need)
261 return context{options: options, arena: arena}
262}
263
264func style(n *Node) css.Style {
265 if n.Style != nil {
266 return *n.Style
267 }
268 return css.Style{Display: css.KeywordBlock, OverflowX: css.KeywordVisible, OverflowY: css.KeywordVisible, FlexShrink: 1}
269}
270func validateStackRects(n *Node, s css.Style) error {
271 if n.Kind == Stack && s.Display == css.KeywordFlex {
272 for _, child := range n.Children {
273 if child != nil && child.HasRect && style(child).Display != css.KeywordNone {
274 return errors.New("layout: Rect is unsupported in a flex-styled Stack")
275 }
276 }
277 }
278 return nil
279}
280func bounded(v float64, minL, maxL css.Length, basis float64) float64 {
281 v = safe(v)
282 if min, ok := length(minL, basis); ok {
283 v = math.Max(v, safe(min))
284 }
285 if max, ok := length(maxL, basis); ok {
286 v = math.Min(v, safe(max))
287 }
288 return safe(v)
289}
290
291// boxBound applies constraints to the CSS sizing space, not to the outer box.
292func boxBound(border float64, minL, maxL css.Length, basis, insets float64, borderBox bool) float64 {
293 if borderBox {
294 return math.Max(insets, bounded(border, minL, maxL, basis))
295 }
296 return safe(bounded(safe(border-insets), minL, maxL, basis) + insets)
297}
298func (c context) intrinsic(n *Node, w float64) (Size, []text.Line, error) {
299 return c.intrinsicDepth(n, w, 0)
300}
301
302func (c context) intrinsicDepth(n *Node, w float64, depth int) (Size, []text.Line, error) {
303 if depth > 256 {
304 return Size{}, nil, ErrDepth
305 }
306 st := style(n)
307 if err := validateStackRects(n, st); err != nil {
308 return Size{}, nil, err
309 }
310 if n.Measure != nil {
311 s, lines, err := n.Measure(w)
312 if err != nil {
313 return Size{}, nil, err
314 }
315 for _, line := range lines {
316 if math.IsNaN(line.Width) || math.IsInf(line.Width, 0) || math.IsNaN(line.Height) || math.IsInf(line.Height, 0) {
317 return Size{}, nil, errors.New("layout: invalid measured text")
318 }
319 }
320 return Size{safe(s.W), safe(s.H)}, lines, nil
321 }
322 if n.Kind == Image {
323 return Size{safe(n.ImageSize.W), safe(n.ImageSize.H)}, nil, nil
324 }
325 if n.Kind == Text && c.options.TextEngine != nil {
326 st := style(n)
327 req := text.Request{Families: st.FontFamily, Weight: float32(st.FontWeight), Italic: st.FontStyle == css.KeywordItalic || st.FontStyle == css.KeywordOblique, Size: safe(st.FontSize.Value), LetterSpacing: coordValue(st.LetterSpacing, 0)}
328 if req.Size == 0 {
329 req.Size = 16
330 }
331 content := n.Content
332 if content == "" && n.EditorScroll {
333 // Preserve one font-metric line for empty editors, caret geometry
334 // and IME composition without painting a visible glyph.
335 content = " "
336 }
337 l, err := c.options.TextEngine.Measure(content, req, w)
338 if err != nil {
339 return Size{}, nil, err
340 }
341 lineHeight := l.LineHeight
342 switch st.LineHeightKind {
343 case css.KeywordNumber:
344 lineHeight = safe(req.Size * st.LineHeightNumber)
345 case css.KeywordNormal:
346 default:
347 if st.LineHeight.Unit != "auto" && st.LineHeight.Unit != "" {
348 lineHeight = positive(st.LineHeight, req.Size)
349 }
350 }
351 // Keep the glyphs' shaped positions; adjust baseline and line origins, not outlines.
352 if lineHeight != l.LineHeight && len(l.Lines) > 0 {
353 l = l.Clone() // Measure results are shared with the engine cache
354 for i := range l.Lines {
355 line := &l.Lines[i]
356 dy := float64(i)*(lineHeight-l.LineHeight) + (lineHeight-l.LineHeight)/2
357 line.Baseline += dy
358 line.Height = lineHeight
359 for j := range line.Runs {
360 run := &line.Runs[j]
361 run.Y += dy
362 for k := range run.Glyphs {
363 run.Glyphs[k].Y += dy
364 }
365 }
366 }
367 l.Height = float64(len(l.Lines)) * lineHeight
368 }
369 return Size{safe(l.Width), safe(l.Height)}, l.Lines, nil
370 }
371 if depth == 0 {
372 return Size{}, nil, nil
373 }
374 // Containers contribute their children to auto flex sizing. Measuring them
375 // as zero compresses nested columns and makes empty editors collapse.
376 row := st.Display == css.KeywordFlex && st.FlexDirection != css.KeywordColumn
377 gap := positive(st.RowGap, w)
378 if row {
379 gap = positive(st.ColumnGap, w)
380 }
381 var size Size
382 count := 0
383 for _, child := range n.Children {
384 if child == nil || style(child).Display == css.KeywordNone {
385 continue
386 }
387 if n.Kind == Stack && child.HasRect {
388 size.W = math.Max(size.W, safe(child.Rect.X+child.Rect.W))
389 size.H = math.Max(size.H, safe(child.Rect.Y+child.Rect.H))
390 count++
391 continue
392 }
393 cs := style(child)
394 inW, inH := flexInsets(cs, w)
395 measured, _, err := c.intrinsicDepth(child, safe(w-inW), depth+1)
396 if err != nil {
397 return Size{}, nil, err
398 }
399 cw, ch := measured.W+inW, measured.H+inH
400 if value, ok := length(cs.Width, w); ok && cs.Width.Unit != "%" {
401 cw = value
402 if cs.BoxSizing != css.KeywordBorderBox {
403 cw += inW
404 }
405 }
406 // Percent heights need a definite containing height, unavailable here.
407 if cs.Height.Unit != "%" {
408 if value, ok := length(cs.Height, 0); ok {
409 ch = value
410 if cs.BoxSizing != css.KeywordBorderBox {
411 ch += inH
412 }
413 }
414 }
415 cw = boxBound(cw, cs.MinWidth, cs.MaxWidth, w, inW, cs.BoxSizing == css.KeywordBorderBox)
416 ch = boxBound(ch, cs.MinHeight, cs.MaxHeight, 0, inH, cs.BoxSizing == css.KeywordBorderBox)
417 // Natural measurement is an unwrapped envelope; actual placement
418 // distributes flex-basis and wraps against the definite container size.
419 margin := edges(cs.Margin, w)
420 cw += margin.horizontal()
421 ch += margin.vertical()
422 if row {
423 if count > 0 {
424 size.W += gap
425 }
426 size.W += cw
427 size.H = math.Max(size.H, ch)
428 } else if n.Kind == Stack {
429 size.W = math.Max(size.W, cw)
430 size.H = math.Max(size.H, ch)
431 } else {
432 if count > 0 && st.Display == css.KeywordFlex {
433 size.H += gap
434 }
435 size.W = math.Max(size.W, cw)
436 size.H += ch
437 }
438 count++
439 }
440 return size, nil, nil
441}
442func (c context) place(n *Node, x, y, availableW, availableH float64, forcedW, forcedH *float64, depth int) (*Result, error) {
443 if depth > 256 {
444 return nil, ErrDepth
445 }
446 if n == nil {
447 return nil, nil
448 }
449 s := style(n)
450 if s.Display == css.KeywordNone {
451 return nil, nil
452 }
453 if err := validateStackRects(n, s); err != nil {
454 return nil, err
455 }
456 availableW = safe(availableW)
457 availableH = safe(availableH)
458 margin := edges(s.Margin, availableW)
459 padding := nonnegative(edges(s.Padding, availableW))
460 border := nonnegative(edges(s.BorderWidth, availableW))
461 if s.BorderStyle.Top != css.KeywordSolid {
462 border.Top = 0
463 }
464 if s.BorderStyle.Right != css.KeywordSolid {
465 border.Right = 0
466 }
467 if s.BorderStyle.Bottom != css.KeywordSolid {
468 border.Bottom = 0
469 }
470 if s.BorderStyle.Left != css.KeywordSolid {
471 border.Left = 0
472 }
473 outerW := safe(availableW - margin.horizontal())
474 insetW := padding.horizontal() + border.horizontal()
475 insetH := padding.vertical() + border.vertical()
476 w, explicitW := length(s.Width, availableW)
477 h, explicitH := length(s.Height, availableH)
478 borderBox := s.BoxSizing == css.KeywordBorderBox
479 // Forced flex lengths are border-box; authored dimensions and constraints use box-sizing.
480 if forcedW != nil {
481 w, explicitW = *forcedW, true
482 } else if explicitW {
483 w = bounded(w, s.MinWidth, s.MaxWidth, availableW)
484 if !borderBox {
485 w += insetW
486 }
487 }
488 if forcedH != nil {
489 h, explicitH = *forcedH, true
490 } else if explicitH {
491 h = bounded(h, s.MinHeight, s.MaxHeight, availableH)
492 if !borderBox {
493 h += insetH
494 }
495 }
496 if !explicitW {
497 w = outerW
498 if n.Kind == Image {
499 w = 0
500 }
501 }
502 if !explicitW && n.Kind != Image {
503 w = boxBound(w, s.MinWidth, s.MaxWidth, availableW, insetW, borderBox)
504 }
505 w = safe(math.Max(w, insetW))
506 contentW := safe(w - insetW)
507 measureW := contentW
508 if n.Kind == Text && n.NoWrap {
509 measureW = 0
510 }
511 measured, lines, err := c.intrinsic(n, measureW)
512 if err != nil {
513 return nil, err
514 }
515 if !explicitW && n.Kind == Image {
516 w = boxBound(measured.W+insetW, s.MinWidth, s.MaxWidth, availableW, insetW, borderBox)
517 contentW = safe(w - insetW)
518 measured, lines, err = c.intrinsic(n, contentW)
519 if err != nil {
520 return nil, err
521 }
522 }
523 if !explicitH {
524 h = measured.H + insetH
525 if n.Kind == Image && measured.W > 0 && explicitW {
526 h = measured.H*contentW/measured.W + insetH
527 }
528 }
529 if n.Kind == Image && !explicitW && explicitH && measured.H > 0 {
530 w = boxBound(measured.W*safe(h-insetH)/measured.H+insetW, s.MinWidth, s.MaxWidth, availableW, insetW, borderBox)
531 contentW = safe(w - insetW)
532 }
533 h = safe(math.Max(h, insetH))
534 if !explicitH {
535 h = boxBound(h, s.MinHeight, s.MaxHeight, availableH, insetH, borderBox)
536 }
537 r := c.arena.results.one(Result{ID: n.ID, Kind: n.Kind, Border: Rect{coord(x + margin.Left), coord(y + margin.Top), w, h}, Margin: margin, Padding: padding, BorderWidths: border, Lines: lines})
538 r.Content = Rect{coord(r.Border.X + border.Left + padding.Left), coord(r.Border.Y + border.Top + padding.Top), contentW, safe(h - insetH)}
539 r.ContentSize = Size{measured.W, measured.H}
540 // Block and stack auto heights depend on their children's envelopes.
541 flex := s.Display == css.KeywordFlex
542 if flex {
543 // An auto-height flex container needs its children's natural height
544 // before distributing space. Otherwise every child is shrunk into zero.
545 // This repeats subtree measurement for nested auto-height containers;
546 // a node/width map cache cost more time and memory in our benchmarks.
547 if !explicitH {
548 natural, _, measureErr := c.intrinsicDepth(n, contentW, 1)
549 if measureErr != nil {
550 return nil, measureErr
551 }
552 r.Border.H = boxBound(math.Max(natural.H+insetH, h), s.MinHeight, s.MaxHeight, availableH, insetH, borderBox)
553 r.Content.H = safe(r.Border.H - insetH)
554 }
555 err = c.flex(n, r, s, depth)
556 } else {
557 err = c.children(n, r, s, depth)
558 }
559 if err != nil {
560 return nil, err
561 }
562 if !explicitH {
563 r.Border.H = boxBound(math.Max(safe(h-insetH), r.ContentSize.H)+insetH, s.MinHeight, s.MaxHeight, availableH, insetH, borderBox)
564 r.Content.H = safe(r.Border.H - insetH)
565 }
566 clipX := overflowClips(s.OverflowX) || n.Kind == Scroll || n.EditorScroll
567 clipY := overflowClips(s.OverflowY) || n.Kind == Scroll || n.EditorScroll
568 if clipX || clipY {
569 r.Clipped = true
570 r.Clip = r.Content
571 if !clipX {
572 r.Clip.X = -limit
573 r.Clip.W = 2 * limit
574 }
575 if !clipY {
576 r.Clip.Y = -limit
577 r.Clip.H = 2 * limit
578 }
579 if clipX && (s.OverflowX == css.KeywordScroll || s.OverflowX == css.KeywordAuto || n.Kind == Scroll || n.EditorScroll) {
580 r.ScrollX = math.Min(safe(n.ScrollX), safe(r.ContentSize.W-r.Content.W))
581 }
582 if clipY && (s.OverflowY == css.KeywordScroll || s.OverflowY == css.KeywordAuto || n.Kind == Scroll || n.EditorScroll) {
583 r.ScrollY = math.Min(safe(n.ScrollY), safe(r.ContentSize.H-r.Content.H))
584 }
585 for _, child := range r.Children {
586 shift(child, -r.ScrollX, -r.ScrollY)
587 }
588 }
589 return r, nil
590}
591func overflowClips(k css.Keyword) bool {
592 return k == css.KeywordHidden || k == css.KeywordScroll || k == css.KeywordAuto
593}
594func shift(r *Result, dx, dy float64) {
595 r.Border.X = coord(r.Border.X + dx)
596 r.Border.Y = coord(r.Border.Y + dy)
597 r.Content.X = coord(r.Content.X + dx)
598 r.Content.Y = coord(r.Content.Y + dy)
599 r.Clip.X = coord(r.Clip.X + dx)
600 r.Clip.Y = coord(r.Clip.Y + dy)
601 for _, child := range r.Children {
602 shift(child, dx, dy)
603 }
604}
605func envelope(r *Result) (float64, float64) {
606 return safe(r.Border.W + r.Margin.horizontal()), safe(r.Border.H + r.Margin.vertical())
607}
608func (c context) children(n *Node, r *Result, s css.Style, depth int) error {
609 y := r.Content.Y
610 for _, ch := range n.Children {
611 if ch == nil {
612 continue
613 }
614 var child *Result
615 var err error
616 absolute := n.Kind == Stack && ch.HasRect
617 if absolute {
618 // Direct geometry: forced border-box size, and the origin is offset
619 // by the resolved margin so the border box lands exactly at Rect.
620 w, h := safe(ch.Rect.W), safe(ch.Rect.H)
621 m := edges(style(ch).Margin, r.Content.W)
622 child, err = c.place(ch, coord(r.Content.X+ch.Rect.X-m.Left), coord(r.Content.Y+ch.Rect.Y-m.Top), r.Content.W, r.Content.H, &w, &h, depth+1)
623 } else {
624 child, err = c.place(ch, r.Content.X, y, r.Content.W, r.Content.H, nil, nil, depth+1)
625 }
626 if err != nil {
627 return err
628 }
629 if child == nil {
630 continue
631 }
632 cw, chh := envelope(child)
633 if absolute {
634 cw, chh = safe(ch.Rect.X+ch.Rect.W), safe(ch.Rect.Y+ch.Rect.H)
635 }
636 r.Children = c.appendChild(r.Children, child, len(n.Children))
637 r.ContentSize.W = math.Max(r.ContentSize.W, cw)
638 if n.Kind == Stack {
639 r.ContentSize.H = math.Max(r.ContentSize.H, chh)
640 } else {
641 y = coord(y + chh)
642 r.ContentSize.H = math.Max(r.ContentSize.H, y-r.Content.Y)
643 }
644 }
645 return nil
646}
647
648// appendChild appends child, taking room for the n input children from the
649// arena on the first call so a node's children never regrow.
650func (c context) appendChild(children []*Result, child *Result, n int) []*Result {
651 if children == nil {
652 children = c.arena.children.take(n)
653 }
654 return append(children, child)
655}
656
657type flexItem struct {
658 node *Node
659 base, size, cross, grow, shrink, marginMain, marginCross float64 // sizes are border boxes
660 min, max float64
661 frozen bool
662}
663
664// flexInsets computes effective border-box insets, using the same border-style
665// treatment as place. Percentage padding is relative to the containing width.
666func flexInsets(s css.Style, basis float64) (float64, float64) {
667 p := nonnegative(edges(s.Padding, basis))
668 b := nonnegative(edges(s.BorderWidth, basis))
669 if s.BorderStyle.Top != css.KeywordSolid {
670 b.Top = 0
671 }
672 if s.BorderStyle.Right != css.KeywordSolid {
673 b.Right = 0
674 }
675 if s.BorderStyle.Bottom != css.KeywordSolid {
676 b.Bottom = 0
677 }
678 if s.BorderStyle.Left != css.KeywordSolid {
679 b.Left = 0
680 }
681 return p.horizontal() + b.horizontal(), p.vertical() + b.vertical()
682}
683func flexBounds(s css.Style, main bool, basis, inset float64) (float64, float64) {
684 minL, maxL := s.MinWidth, s.MaxWidth
685 if !main {
686 minL, maxL = s.MinHeight, s.MaxHeight
687 }
688 low, high := inset, float64(limit)
689 if v, ok := length(minL, basis); ok {
690 if s.BoxSizing != css.KeywordBorderBox {
691 low = math.Max(inset, safe(v)+inset)
692 } else {
693 low = math.Max(inset, safe(v))
694 }
695 }
696 if v, ok := length(maxL, basis); ok {
697 high = safe(v)
698 if s.BoxSizing != css.KeywordBorderBox {
699 high += inset
700 }
701 high = math.Max(high, inset)
702 }
703 return low, math.Max(low, high)
704}
705
706// resolveFlex freezes violating items, then redistributes the remaining free
707// space among unfrozen items. Shrink weights always use the original base.
708func resolveFlex(items []flexItem, available float64) {
709 total := 0.0
710 for i := range items {
711 it := &items[i]
712 it.size = it.base
713 it.frozen = false
714 total += it.base + it.marginMain
715 }
716 grow := available > total
717 // Each pass freezes at least one violator, or all remaining items.
718 for range items {
719 free, weight, factors := available, 0.0, 0.0
720 for i := range items {
721 it := &items[i]
722 free -= it.marginMain
723 if it.frozen {
724 free -= it.size
725 continue
726 }
727 free -= it.base
728 factor := it.grow
729 if !grow {
730 factor = it.shrink * it.base
731 }
732 weight += factor
733 if grow {
734 factors += it.grow
735 }
736 }
737 // CSS resolve-flexible-lengths limits growth when total grow factors < 1.
738 if grow && factors < 1 {
739 free *= factors
740 }
741 violation := 0.0
742 for i := range items {
743 it := &items[i]
744 if it.frozen {
745 continue
746 }
747 factor := it.grow
748 if !grow {
749 factor = it.shrink * it.base
750 }
751 tentative := it.base
752 if weight > 0 {
753 tentative += free * factor / weight
754 }
755 it.size = math.Max(it.min, math.Min(it.max, safe(tentative)))
756 violation += it.size - tentative
757 }
758 if math.Abs(violation) < 1e-9 {
759 for i := range items {
760 items[i].frozen = true
761 }
762 break
763 }
764 for i := range items {
765 it := &items[i]
766 if it.frozen {
767 continue
768 }
769 factor := it.grow
770 if !grow {
771 factor = it.shrink * it.base
772 }
773 tentative := it.base
774 if weight > 0 {
775 tentative += free * factor / weight
776 }
777 if violation > 0 && it.size > tentative || violation < 0 && it.size < tentative {
778 it.frozen = true
779 }
780 }
781 }
782}
783func (c context) flex(n *Node, r *Result, s css.Style, depth int) error {
784 row := s.FlexDirection != css.KeywordColumn
785 mainSize, crossSize := r.Content.W, r.Content.H
786 gap, crossGap := positive(s.ColumnGap, r.Content.W), positive(s.RowGap, r.Content.W)
787 if !row {
788 mainSize, crossSize = crossSize, mainSize
789 gap, crossGap = crossGap, gap
790 }
791 items := c.arena.flexItems.take(len(n.Children))
792 for _, ch := range n.Children {
793 if ch == nil || style(ch).Display == css.KeywordNone {
794 continue
795 }
796 st := style(ch)
797 m := edges(st.Margin, r.Content.W)
798 inW, inH := flexInsets(st, r.Content.W)
799 inMain, inCross := inW, inH
800 if !row {
801 inMain, inCross = inH, inW
802 }
803 it := flexItem{node: ch, grow: safe(st.FlexGrow), shrink: safe(st.FlexShrink)}
804 if row {
805 it.marginMain = m.horizontal()
806 it.marginCross = m.vertical()
807 } else {
808 it.marginMain = m.vertical()
809 it.marginCross = m.horizontal()
810 }
811 dim, crossDim := st.Width, st.Height
812 minCross, maxCross := st.MinHeight, st.MaxHeight
813 if !row {
814 dim, crossDim = st.Height, st.Width
815 minCross, maxCross = st.MinWidth, st.MaxWidth
816 }
817 measureWidth := 0.0
818 if row {
819 measureWidth = mainSize
820 } else {
821 measureWidth = crossSize
822 }
823 measured, _, err := c.intrinsicDepth(ch, measureWidth, 1)
824 if err != nil {
825 return err
826 }
827 intrinsicMain, intrinsicCross := measured.W, measured.H
828 if !row {
829 intrinsicMain, intrinsicCross = measured.H, measured.W
830 }
831 value, ok := length(st.FlexBasis, mainSize)
832 if !ok {
833 value, ok = length(dim, mainSize)
834 }
835 if ok {
836 it.base = safe(value)
837 if st.BoxSizing != css.KeywordBorderBox {
838 it.base += inMain
839 }
840 } else {
841 it.base = intrinsicMain + inMain
842 }
843 value, ok = length(crossDim, crossSize)
844 if ok {
845 it.cross = safe(value)
846 if st.BoxSizing != css.KeywordBorderBox {
847 it.cross += inCross
848 }
849 } else {
850 it.cross = intrinsicCross + inCross
851 }
852 it.min, it.max = flexBounds(st, row, mainSize, inMain)
853 it.cross = boxBound(it.cross, minCross, maxCross, crossSize, inCross, st.BoxSizing == css.KeywordBorderBox)
854 items = append(items, it)
855 }
856 // Each line is a run of consecutive items; ends holds each line's end index.
857 ends := c.arena.flexEnds.take(len(items))
858 start, used := 0, 0.0
859 for i, item := range items {
860 need := item.base + item.marginMain
861 if i > start {
862 need += gap
863 }
864 if s.FlexWrap == css.KeywordWrap && i > start && used+need > mainSize {
865 ends = append(ends, i)
866 start, used = i, 0
867 need = item.base + item.marginMain
868 }
869 used += need
870 }
871 if len(items) > start {
872 ends = append(ends, len(items))
873 }
874 crossPos := 0.0
875 lineStart := 0
876 for _, end := range ends {
877 line := items[lineStart:end:end]
878 lineStart = end
879 lineCross := 0.0
880 for _, it := range line {
881 lineCross = math.Max(lineCross, it.cross+it.marginCross)
882 }
883 if len(ends) == 1 && crossSize > 0 && (row && s.Height.Unit != "auto" && s.Height.Unit != "" || !row && s.Width.Unit != "auto" && s.Width.Unit != "") {
884 lineCross = math.Max(lineCross, crossSize)
885 }
886 resolveFlex(line, mainSize-gap*float64(len(line)-1))
887 occupied := gap * float64(len(line)-1)
888 for _, it := range line {
889 occupied += it.size + it.marginMain
890 }
891 remaining := safe(mainSize - occupied)
892 start, spacing := 0.0, gap
893 switch s.JustifyContent {
894 case css.KeywordFlexEnd:
895 start = remaining
896 case css.KeywordCenter:
897 start = remaining / 2
898 case css.KeywordSpaceBetween:
899 if len(line) > 1 {
900 spacing += remaining / float64(len(line)-1)
901 }
902 case css.KeywordSpaceAround:
903 spacing += remaining / float64(len(line))
904 start = remaining / float64(2*len(line))
905 case css.KeywordSpaceEvenly:
906 spacing += remaining / float64(len(line)+1)
907 start = remaining / float64(len(line)+1)
908 }
909 pos := start
910 for _, it := range line {
911 align := style(it.node).AlignSelf
912 if align == css.KeywordAuto || align == css.KeywordNone {
913 align = s.AlignItems
914 }
915 cross := it.cross
916 if align == css.KeywordStretch {
917 cross = safe(lineCross - it.marginCross)
918 }
919 offset := 0.0
920 switch align {
921 case css.KeywordCenter:
922 offset = safe(lineCross-cross-it.marginCross) / 2
923 case css.KeywordFlexEnd:
924 offset = safe(lineCross - cross - it.marginCross)
925 }
926 main := safe(it.size)
927 cross = safe(cross)
928 var x, y float64
929 var w, h *float64
930 if row {
931 x = r.Content.X + pos
932 y = r.Content.Y + crossPos + offset
933 w = &main
934 h = &cross
935 } else {
936 x = r.Content.X + crossPos + offset
937 y = r.Content.Y + pos
938 w = &cross
939 h = &main
940 }
941 child, err := c.place(it.node, x, y, r.Content.W, r.Content.H, w, h, depth+1)
942 if err != nil {
943 return err
944 }
945 if child != nil {
946 r.Children = c.appendChild(r.Children, child, len(n.Children))
947 cw, ch := envelope(child)
948 r.ContentSize.W = math.Max(r.ContentSize.W, child.Border.X-r.Content.X+cw)
949 r.ContentSize.H = math.Max(r.ContentSize.H, child.Border.Y-r.Content.Y+ch)
950 }
951 pos += main + it.marginMain + spacing
952 }
953 crossPos += lineCross + crossGap
954 }
955 return nil
956}
957
958// slab hands out values or sub-slices from one block, so an Output costs no
959// allocation per node, shadow, run or text command once the block is large
960// enough. The block is reused by reset: pointers and slices from it are valid
961// until the owning Arena is passed to Layout again. Sub-slices have their
962// capacity clipped, so a caller's append cannot overwrite a neighbour. A
963// miscount only falls back to individual allocations, and need grows so the
964// next reset fits.
965type slab[T any] struct {
966 block []T
967 need int // demand since the last reset, including fallbacks
968}
969
970// retainSlack is how much larger than needed retained storage may be before
971// it is dropped, so one huge frame does not pin its memory. render uses the
972// same rule for its quad and instance buffers.
973const retainSlack = 4
974
975// oversized reports that storage of the given capacity holds far more than
976// need and should be dropped rather than reused.
977func oversized(capacity, need int) bool { return capacity > retainSlack*need+64 }
978
979// reset recycles the block for n elements, zeroing the previous contents so
980// they do not keep text, faces or images alive.
981func (a *slab[T]) reset(n int) {
982 clear(a.block)
983 a.need = 0
984 if cap(a.block) < n || oversized(cap(a.block), n) {
985 a.block = make([]T, 0, n)
986 return
987 }
988 a.block = a.block[:0]
989}
990
991// one stores v in the slab and returns its address.
992func (a *slab[T]) one(v T) *T {
993 a.need++
994 if len(a.block) == cap(a.block) {
995 p := new(T) // copy, so v itself never escapes
996 *p = v
997 return p
998 }
999 a.block = append(a.block, v)
1000 return &a.block[len(a.block)-1]
1001}
1002
1003// take returns an empty slice with capacity exactly n (nil for n == 0).
1004func (a *slab[T]) take(n int) []T {
1005 if n <= 0 {
1006 return nil
1007 }
1008 a.need += n
1009 if cap(a.block)-len(a.block) < n {
1010 return make([]T, 0, n)
1011 }
1012 i := len(a.block)
1013 a.block = a.block[:i+n]
1014 return a.block[i : i : i+n]
1015}
1016
1017// radiiOf resolves border-radius percentages against basis.
1018func radiiOf(s *css.Style, basis float64) [4]float64 {
1019 return [4]float64{positive(s.BorderRadius.TopLeft, basis), positive(s.BorderRadius.TopRight, basis), positive(s.BorderRadius.BottomRight, basis), positive(s.BorderRadius.BottomLeft, basis)}
1020}
1021
1022func hasOutline(s *css.Style, r *Result) bool {
1023 return s.OutlineStyle == css.KeywordSolid && positive(s.OutlineWidth, r.Border.W) > 0
1024}
1025
1026// countCommands returns how many commands and shadow copies paint emits for
1027// the subtree, so Layout can size the display list once. It mirrors paint's
1028// conditions; if it ever drifts, paint still appends correctly and only regrows.
1029func countCommands(n *Node, r *Result) (c counts) {
1030 if r == nil {
1031 return c
1032 }
1033 s := style(n)
1034 total := len(s.BoxShadow)
1035 c.shadows = len(s.BoxShadow)
1036 if s.BackgroundColor.A > 0 {
1037 total++
1038 }
1039 if r.BorderWidths != (Edges{}) || radiiOf(&s, r.Border.W) != ([4]float64{}) {
1040 total++
1041 }
1042 if hasOutline(&s, r) {
1043 total++
1044 }
1045 if r.Clipped {
1046 total += 2
1047 }
1048 if n.Kind == Image || n.Kind == Text {
1049 total++
1050 }
1051 if n.Kind == Text {
1052 c.runs, c.glyphs = textCounts(r)
1053 }
1054 j := 0
1055 for _, child := range n.Children {
1056 if child == nil || style(child).Display == css.KeywordNone {
1057 continue
1058 }
1059 if j < len(r.Children) {
1060 cc := countCommands(child, r.Children[j])
1061 total += cc.commands
1062 c.shadows += cc.shadows
1063 c.runs += cc.runs
1064 c.glyphs += cc.glyphs
1065 j++
1066 }
1067 }
1068 c.commands += total
1069 return c
1070}
1071
1072type counts struct{ commands, shadows, runs, glyphs int }
1073
1074func textCounts(r *Result) (runs, glyphs int) {
1075 for i := range r.Lines {
1076 runs += len(r.Lines[i].Runs)
1077 for j := range r.Lines[i].Runs {
1078 glyphs += len(r.Lines[i].Runs[j].Glyphs)
1079 }
1080 }
1081 return runs, glyphs
1082}
1083
1084func (c context) paint(n *Node, r *Result, out *[]Command) {
1085 if r == nil {
1086 return
1087 }
1088 s := style(n)
1089 base := Command{ID: r.ID, Rect: r.Border, Opacity: math.Min(1, safe(s.Opacity))}
1090 borderRadii := radiiOf(&s, r.Border.W)
1091 for i := range s.BoxShadow {
1092 if s.BoxShadow[i].Inset {
1093 continue
1094 }
1095 cmd := base
1096 cmd.Op = "shadow"
1097 cmd.Shadow = c.arena.shadows.one(s.BoxShadow[i])
1098 cmd.Radii = borderRadii
1099 *out = append(*out, cmd)
1100 }
1101 if s.BackgroundColor.A > 0 {
1102 cmd := base
1103 cmd.Op = "rect"
1104 cmd.Color = s.BackgroundColor
1105 cmd.Radii = borderRadii
1106 *out = append(*out, cmd)
1107 }
1108 cmd := base
1109 cmd.Op = "border"
1110 cmd.Widths = r.BorderWidths
1111 cmd.Colors = s.BorderColor
1112 cmd.Radii = borderRadii
1113 if cmd.Widths != (Edges{}) || cmd.Radii != ([4]float64{}) {
1114 cmd.Color = s.BorderColor.Top
1115 *out = append(*out, cmd)
1116 }
1117 for i := range s.BoxShadow {
1118 if !s.BoxShadow[i].Inset {
1119 continue
1120 }
1121 cmd := base
1122 cmd.Op = "shadow"
1123 cmd.Shadow = c.arena.shadows.one(s.BoxShadow[i])
1124 cmd.Radii = borderRadii
1125 *out = append(*out, cmd)
1126 }
1127 if hasOutline(&s, r) {
1128 cmd = base
1129 cmd.Op = "outline"
1130 cmd.Color = s.OutlineColor
1131 cmd.Radii = borderRadii
1132 width := positive(s.OutlineWidth, r.Border.W)
1133 cmd.Widths = Edges{Top: width, Right: width, Bottom: width, Left: width}
1134 offset := coordValue(s.OutlineOffset, r.Border.W)
1135 cmd.Rect = Rect{X: coord(r.Border.X - offset), Y: coord(r.Border.Y - offset), W: safe(r.Border.W + 2*offset), H: safe(r.Border.H + 2*offset)}
1136 *out = append(*out, cmd)
1137 }
1138 if r.Clipped {
1139 cmd = base
1140 cmd.Op = "clip-push"
1141 cmd.Rect = r.Clip
1142 *out = append(*out, cmd)
1143 }
1144 if n.Kind == Image {
1145 cmd = base
1146 cmd.Op = "image"
1147 cmd.Rect = r.Content
1148 cmd.Image = n.Image
1149 cmd.Radii = radiiOf(&s, r.Content.W)
1150 *out = append(*out, cmd)
1151 }
1152 if n.Kind == Text {
1153 cmd = base
1154 cmd.Op = "text"
1155 cmd.Rect = r.Content
1156 cmd.Text = n.Content
1157 cmd.Color = s.Color
1158 runs, glyphs := textCounts(r)
1159 cmd.Runs = c.arena.runs.take(runs)
1160 backing := c.arena.glyphs.take(glyphs)
1161 for _, line := range r.Lines {
1162 offset := AlignOffset(s.TextAlign, line.Direction, r.Content.W, line.Width)
1163 for _, run := range line.Runs {
1164 rr := Run{Start: run.Start, End: run.End, X: run.X + r.Content.X + offset - r.ScrollX, Y: run.Y + r.Content.Y - r.ScrollY, Advance: run.Advance, Face: run.Face, Size: s.FontSize.Value}
1165 if rr.Size <= 0 {
1166 rr.Size = 16 // matches the intrinsic text.Measure request fallback
1167 }
1168 if run.Face != nil {
1169 rr.FaceID = run.Face.ID
1170 }
1171 if len(run.Glyphs) > 0 { // keep nil for glyph-less runs
1172 first := len(backing)
1173 for _, g := range run.Glyphs {
1174 backing = append(backing, Glyph{uint32(g.ID), g.X + r.Content.X + offset - r.ScrollX, g.Y + r.Content.Y - r.ScrollY, g.Advance, g.Cluster})
1175 }
1176 rr.Glyphs = backing[first:len(backing):len(backing)]
1177 }
1178 cmd.Runs = append(cmd.Runs, rr)
1179 }
1180 }
1181 *out = append(*out, cmd)
1182 }
1183 j := 0
1184 for _, child := range n.Children {
1185 if child == nil || style(child).Display == css.KeywordNone {
1186 continue
1187 }
1188 if j < len(r.Children) {
1189 c.paint(child, r.Children[j], out)
1190 j++
1191 }
1192 }
1193 if r.Clipped {
1194 cmd = base
1195 cmd.Op = "clip-pop"
1196 *out = append(*out, cmd)
1197 }
1198}
1199
1200// AlignOffset is the horizontal offset of a line of width lineW inside a
1201// content box of width contentW under text-align and the line's direction.
1202func AlignOffset(align css.Keyword, direction di.Direction, contentW, lineW float64) float64 {
1203 switch align {
1204 case css.KeywordCenter:
1205 return safe(contentW-lineW) / 2
1206 case css.KeywordRight:
1207 return safe(contentW - lineW)
1208 case css.KeywordStart:
1209 if direction == di.DirectionRTL {
1210 return safe(contentW - lineW)
1211 }
1212 case css.KeywordEnd:
1213 if direction != di.DirectionRTL {
1214 return safe(contentW - lineW)
1215 }
1216 }
1217 return 0
1218}
1219
1220// Hit returns the frontmost node ID whose border box contains the logical point.
1221// Ancestor content clips constrain descendants, but not the ancestor border itself.
1222func Hit(r *Result, x, y float64) string {
1223 if math.IsNaN(x) || math.IsNaN(y) || math.IsInf(x, 0) || math.IsInf(y, 0) {
1224 return ""
1225 }
1226 return hit(r, x, y, Rect{-limit, -limit, 2 * limit, 2 * limit})
1227}
1228func hit(r *Result, x, y float64, clip Rect) string {
1229 if r == nil || !clip.Contains(x, y) {
1230 return ""
1231 }
1232 childClip := clip
1233 if r.Clipped {
1234 childClip = clip.intersect(r.Clip)
1235 }
1236 if childClip.Contains(x, y) {
1237 for i := len(r.Children) - 1; i >= 0; i-- {
1238 if id := hit(r.Children[i], x, y, childClip); id != "" {
1239 return id
1240 }
1241 }
1242 }
1243 if r.Border.Contains(x, y) {
1244 return r.ID
1245 }
1246 return ""
1247}
1248
1249// Physical is the explicit renderer boundary; all layout and hit testing stay logical.
1250// It rounds edges independently to avoid accumulated fractional-scale drift.
1251func Physical(r Rect, scale float64) (x, y, w, h int) {
1252 if math.IsNaN(scale) || math.IsInf(scale, 0) || scale <= 0 {
1253 return
1254 }
1255 scale = math.Min(scale, 1024)
1256 x = int(math.Round(coord(r.X) * scale))
1257 y = int(math.Round(coord(r.Y) * scale))
1258 w = int(math.Round(coord(r.X+safe(r.W))*scale)) - x
1259 h = int(math.Round(coord(r.Y+safe(r.H))*scale)) - y
1260 return
1261}