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