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 = appendChild(r.Children, child, len(n.Children))
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
595// appendChild appends child, sizing the first allocation for the n input
596// children so a node's result children cost one allocation, not a growth chain.
597func appendChild(children []*Result, child *Result, n int) []*Result {
598 if children == nil {
599 children = make([]*Result, 0, n)
600 }
601 return append(children, child)
602}
603
604type flexItem struct {
605 node *Node
606 base, size, cross, grow, shrink, marginMain, marginCross float64 // sizes are border boxes
607 min, max float64
608 frozen bool
609}
610
611// flexInsets computes effective border-box insets, using the same border-style
612// treatment as place. Percentage padding is relative to the containing width.
613func flexInsets(s css.Style, basis float64) (float64, float64) {
614 p := nonnegative(edges(s.Padding, basis))
615 b := nonnegative(edges(s.BorderWidth, basis))
616 if s.BorderStyle.Top != css.KeywordSolid {
617 b.Top = 0
618 }
619 if s.BorderStyle.Right != css.KeywordSolid {
620 b.Right = 0
621 }
622 if s.BorderStyle.Bottom != css.KeywordSolid {
623 b.Bottom = 0
624 }
625 if s.BorderStyle.Left != css.KeywordSolid {
626 b.Left = 0
627 }
628 return p.horizontal() + b.horizontal(), p.vertical() + b.vertical()
629}
630func flexBounds(s css.Style, main bool, basis, inset float64) (float64, float64) {
631 minL, maxL := s.MinWidth, s.MaxWidth
632 if !main {
633 minL, maxL = s.MinHeight, s.MaxHeight
634 }
635 low, high := inset, float64(limit)
636 if v, ok := length(minL, basis); ok {
637 if s.BoxSizing != css.KeywordBorderBox {
638 low = math.Max(inset, safe(v)+inset)
639 } else {
640 low = math.Max(inset, safe(v))
641 }
642 }
643 if v, ok := length(maxL, basis); ok {
644 high = safe(v)
645 if s.BoxSizing != css.KeywordBorderBox {
646 high += inset
647 }
648 high = math.Max(high, inset)
649 }
650 return low, math.Max(low, high)
651}
652
653// resolveFlex freezes violating items, then redistributes the remaining free
654// space among unfrozen items. Shrink weights always use the original base.
655func resolveFlex(items []flexItem, available float64) {
656 total := 0.0
657 for i := range items {
658 it := &items[i]
659 it.size = it.base
660 it.frozen = false
661 total += it.base + it.marginMain
662 }
663 grow := available > total
664 // Each pass freezes at least one violator, or all remaining items.
665 for range items {
666 free, weight, factors := available, 0.0, 0.0
667 for i := range items {
668 it := &items[i]
669 free -= it.marginMain
670 if it.frozen {
671 free -= it.size
672 continue
673 }
674 free -= it.base
675 factor := it.grow
676 if !grow {
677 factor = it.shrink * it.base
678 }
679 weight += factor
680 if grow {
681 factors += it.grow
682 }
683 }
684 // CSS resolve-flexible-lengths limits growth when total grow factors < 1.
685 if grow && factors < 1 {
686 free *= factors
687 }
688 violation := 0.0
689 for i := range items {
690 it := &items[i]
691 if it.frozen {
692 continue
693 }
694 factor := it.grow
695 if !grow {
696 factor = it.shrink * it.base
697 }
698 tentative := it.base
699 if weight > 0 {
700 tentative += free * factor / weight
701 }
702 it.size = math.Max(it.min, math.Min(it.max, safe(tentative)))
703 violation += it.size - tentative
704 }
705 if math.Abs(violation) < 1e-9 {
706 for i := range items {
707 items[i].frozen = true
708 }
709 break
710 }
711 for i := range items {
712 it := &items[i]
713 if it.frozen {
714 continue
715 }
716 factor := it.grow
717 if !grow {
718 factor = it.shrink * it.base
719 }
720 tentative := it.base
721 if weight > 0 {
722 tentative += free * factor / weight
723 }
724 if violation > 0 && it.size > tentative || violation < 0 && it.size < tentative {
725 it.frozen = true
726 }
727 }
728 }
729}
730func (c context) flex(n *Node, r *Result, s css.Style, depth int) error {
731 row := s.FlexDirection != css.KeywordColumn
732 mainSize, crossSize := r.Content.W, r.Content.H
733 gap, crossGap := positive(s.ColumnGap, r.Content.W), positive(s.RowGap, r.Content.W)
734 if !row {
735 mainSize, crossSize = crossSize, mainSize
736 gap, crossGap = crossGap, gap
737 }
738 items := make([]flexItem, 0, len(n.Children))
739 for _, ch := range n.Children {
740 if ch == nil || style(ch).Display == css.KeywordNone {
741 continue
742 }
743 st := style(ch)
744 m := edges(st.Margin, r.Content.W)
745 inW, inH := flexInsets(st, r.Content.W)
746 inMain, inCross := inW, inH
747 if !row {
748 inMain, inCross = inH, inW
749 }
750 it := flexItem{node: ch, grow: safe(st.FlexGrow), shrink: safe(st.FlexShrink)}
751 if row {
752 it.marginMain = m.horizontal()
753 it.marginCross = m.vertical()
754 } else {
755 it.marginMain = m.vertical()
756 it.marginCross = m.horizontal()
757 }
758 dim, crossDim := st.Width, st.Height
759 minCross, maxCross := st.MinHeight, st.MaxHeight
760 if !row {
761 dim, crossDim = st.Height, st.Width
762 minCross, maxCross = st.MinWidth, st.MaxWidth
763 }
764 measureWidth := 0.0
765 if row {
766 measureWidth = mainSize
767 } else {
768 measureWidth = crossSize
769 }
770 measured, _, err := c.intrinsicDepth(ch, measureWidth, 1)
771 if err != nil {
772 return err
773 }
774 intrinsicMain, intrinsicCross := measured.W, measured.H
775 if !row {
776 intrinsicMain, intrinsicCross = measured.H, measured.W
777 }
778 value, ok := length(st.FlexBasis, mainSize)
779 if !ok {
780 value, ok = length(dim, mainSize)
781 }
782 if ok {
783 it.base = safe(value)
784 if st.BoxSizing != css.KeywordBorderBox {
785 it.base += inMain
786 }
787 } else {
788 it.base = intrinsicMain + inMain
789 }
790 value, ok = length(crossDim, crossSize)
791 if ok {
792 it.cross = safe(value)
793 if st.BoxSizing != css.KeywordBorderBox {
794 it.cross += inCross
795 }
796 } else {
797 it.cross = intrinsicCross + inCross
798 }
799 it.min, it.max = flexBounds(st, row, mainSize, inMain)
800 it.cross = boxBound(it.cross, minCross, maxCross, crossSize, inCross, st.BoxSizing == css.KeywordBorderBox)
801 items = append(items, it)
802 }
803 lines := [][]flexItem{}
804 line := []flexItem{}
805 used := 0.0
806 for _, item := range items {
807 need := item.base + item.marginMain
808 if len(line) > 0 {
809 need += gap
810 }
811 if s.FlexWrap == css.KeywordWrap && len(line) > 0 && used+need > mainSize {
812 lines = append(lines, line)
813 line = nil
814 used = 0
815 need = item.base + item.marginMain
816 }
817 line = append(line, item)
818 used += need
819 }
820 if len(line) > 0 {
821 lines = append(lines, line)
822 }
823 crossPos := 0.0
824 for _, line := range lines {
825 lineCross := 0.0
826 for _, it := range line {
827 lineCross = math.Max(lineCross, it.cross+it.marginCross)
828 }
829 if len(lines) == 1 && crossSize > 0 && (row && s.Height.Unit != "auto" && s.Height.Unit != "" || !row && s.Width.Unit != "auto" && s.Width.Unit != "") {
830 lineCross = math.Max(lineCross, crossSize)
831 }
832 resolveFlex(line, mainSize-gap*float64(len(line)-1))
833 occupied := gap * float64(len(line)-1)
834 for _, it := range line {
835 occupied += it.size + it.marginMain
836 }
837 remaining := safe(mainSize - occupied)
838 start, spacing := 0.0, gap
839 switch s.JustifyContent {
840 case css.KeywordFlexEnd:
841 start = remaining
842 case css.KeywordCenter:
843 start = remaining / 2
844 case css.KeywordSpaceBetween:
845 if len(line) > 1 {
846 spacing += remaining / float64(len(line)-1)
847 }
848 case css.KeywordSpaceAround:
849 spacing += remaining / float64(len(line))
850 start = remaining / float64(2*len(line))
851 case css.KeywordSpaceEvenly:
852 spacing += remaining / float64(len(line)+1)
853 start = remaining / float64(len(line)+1)
854 }
855 pos := start
856 for _, it := range line {
857 align := style(it.node).AlignSelf
858 if align == css.KeywordAuto || align == css.KeywordNone {
859 align = s.AlignItems
860 }
861 cross := it.cross
862 if align == css.KeywordStretch {
863 cross = safe(lineCross - it.marginCross)
864 }
865 offset := 0.0
866 switch align {
867 case css.KeywordCenter:
868 offset = safe(lineCross-cross-it.marginCross) / 2
869 case css.KeywordFlexEnd:
870 offset = safe(lineCross - cross - it.marginCross)
871 }
872 main := safe(it.size)
873 cross = safe(cross)
874 var x, y float64
875 var w, h *float64
876 if row {
877 x = r.Content.X + pos
878 y = r.Content.Y + crossPos + offset
879 w = &main
880 h = &cross
881 } else {
882 x = r.Content.X + crossPos + offset
883 y = r.Content.Y + pos
884 w = &cross
885 h = &main
886 }
887 child, err := c.place(it.node, x, y, r.Content.W, r.Content.H, w, h, depth+1)
888 if err != nil {
889 return err
890 }
891 if child != nil {
892 r.Children = appendChild(r.Children, child, len(n.Children))
893 cw, ch := envelope(child)
894 r.ContentSize.W = math.Max(r.ContentSize.W, child.Border.X-r.Content.X+cw)
895 r.ContentSize.H = math.Max(r.ContentSize.H, child.Border.Y-r.Content.Y+ch)
896 }
897 pos += main + it.marginMain + spacing
898 }
899 crossPos += lineCross + crossGap
900 }
901 return nil
902}
903
904// slab hands out detached values or sub-slices from one exactly sized block,
905// so a display list costs a few allocations rather than one per shadow, run or
906// text command. Blocks are never resized or reused, so pointers and slices
907// stay valid for the life of the returned Output. Sub-slices have their
908// capacity clipped, so a caller's append cannot overwrite a neighbour. A
909// miscount, or a nil slab, only falls back to individual allocations.
910type slab[T any] struct{ block []T }
911
912func newSlab[T any](n int) *slab[T] {
913 if n <= 0 {
914 return nil
915 }
916 return &slab[T]{block: make([]T, 0, n)}
917}
918
919// one stores v in the slab and returns its address.
920func (a *slab[T]) one(v T) *T {
921 if a == nil || len(a.block) == cap(a.block) {
922 p := new(T) // copy, so v itself never escapes
923 *p = v
924 return p
925 }
926 a.block = append(a.block, v)
927 return &a.block[len(a.block)-1]
928}
929
930// take returns an empty slice with capacity exactly n (nil for n == 0).
931func (a *slab[T]) take(n int) []T {
932 if n <= 0 {
933 return nil
934 }
935 if a == nil || cap(a.block)-len(a.block) < n {
936 return make([]T, 0, n)
937 }
938 i := len(a.block)
939 a.block = a.block[:i+n]
940 return a.block[i : i : i+n]
941}
942
943// radiiOf resolves border-radius percentages against basis.
944func radiiOf(s *css.Style, basis float64) [4]float64 {
945 return [4]float64{positive(s.BorderRadius.TopLeft, basis), positive(s.BorderRadius.TopRight, basis), positive(s.BorderRadius.BottomRight, basis), positive(s.BorderRadius.BottomLeft, basis)}
946}
947
948func hasOutline(s *css.Style, r *Result) bool {
949 return s.OutlineStyle == css.KeywordSolid && positive(s.OutlineWidth, r.Border.W) > 0
950}
951
952// countCommands returns how many commands and shadow copies paint emits for
953// the subtree, so Layout can size the display list once. It mirrors paint's
954// conditions; if it ever drifts, paint still appends correctly and only regrows.
955func countCommands(n *Node, r *Result) (c counts) {
956 if r == nil {
957 return c
958 }
959 s := style(n)
960 total := len(s.BoxShadow)
961 c.shadows = len(s.BoxShadow)
962 if s.BackgroundColor.A > 0 {
963 total++
964 }
965 if r.BorderWidths != (Edges{}) || radiiOf(&s, r.Border.W) != ([4]float64{}) {
966 total++
967 }
968 if hasOutline(&s, r) {
969 total++
970 }
971 if r.Clipped {
972 total += 2
973 }
974 if n.Kind == Image || n.Kind == Text {
975 total++
976 }
977 if n.Kind == Text {
978 c.runs, c.glyphs = textCounts(r)
979 }
980 j := 0
981 for _, child := range n.Children {
982 if child == nil || style(child).Display == css.KeywordNone {
983 continue
984 }
985 if j < len(r.Children) {
986 cc := countCommands(child, r.Children[j])
987 total += cc.commands
988 c.shadows += cc.shadows
989 c.runs += cc.runs
990 c.glyphs += cc.glyphs
991 j++
992 }
993 }
994 c.commands += total
995 return c
996}
997
998type counts struct{ commands, shadows, runs, glyphs int }
999
1000func textCounts(r *Result) (runs, glyphs int) {
1001 for i := range r.Lines {
1002 runs += len(r.Lines[i].Runs)
1003 for j := range r.Lines[i].Runs {
1004 glyphs += len(r.Lines[i].Runs[j].Glyphs)
1005 }
1006 }
1007 return runs, glyphs
1008}
1009
1010func (c context) paint(n *Node, r *Result, out *[]Command) {
1011 if r == nil {
1012 return
1013 }
1014 s := style(n)
1015 base := Command{ID: r.ID, Rect: r.Border, Opacity: math.Min(1, safe(s.Opacity))}
1016 borderRadii := radiiOf(&s, r.Border.W)
1017 for i := range s.BoxShadow {
1018 if s.BoxShadow[i].Inset {
1019 continue
1020 }
1021 cmd := base
1022 cmd.Op = "shadow"
1023 cmd.Shadow = c.shadows.one(s.BoxShadow[i])
1024 cmd.Radii = borderRadii
1025 *out = append(*out, cmd)
1026 }
1027 if s.BackgroundColor.A > 0 {
1028 cmd := base
1029 cmd.Op = "rect"
1030 cmd.Color = s.BackgroundColor
1031 cmd.Radii = borderRadii
1032 *out = append(*out, cmd)
1033 }
1034 cmd := base
1035 cmd.Op = "border"
1036 cmd.Widths = r.BorderWidths
1037 cmd.Colors = s.BorderColor
1038 cmd.Radii = borderRadii
1039 if cmd.Widths != (Edges{}) || cmd.Radii != ([4]float64{}) {
1040 cmd.Color = s.BorderColor.Top
1041 *out = append(*out, cmd)
1042 }
1043 for i := range s.BoxShadow {
1044 if !s.BoxShadow[i].Inset {
1045 continue
1046 }
1047 cmd := base
1048 cmd.Op = "shadow"
1049 cmd.Shadow = c.shadows.one(s.BoxShadow[i])
1050 cmd.Radii = borderRadii
1051 *out = append(*out, cmd)
1052 }
1053 if hasOutline(&s, r) {
1054 cmd = base
1055 cmd.Op = "outline"
1056 cmd.Color = s.OutlineColor
1057 cmd.Radii = borderRadii
1058 width := positive(s.OutlineWidth, r.Border.W)
1059 cmd.Widths = Edges{Top: width, Right: width, Bottom: width, Left: width}
1060 offset := coordValue(s.OutlineOffset, r.Border.W)
1061 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)}
1062 *out = append(*out, cmd)
1063 }
1064 if r.Clipped {
1065 cmd = base
1066 cmd.Op = "clip-push"
1067 cmd.Rect = r.Clip
1068 *out = append(*out, cmd)
1069 }
1070 if n.Kind == Image {
1071 cmd = base
1072 cmd.Op = "image"
1073 cmd.Rect = r.Content
1074 cmd.Image = n.Image
1075 cmd.Radii = radiiOf(&s, r.Content.W)
1076 *out = append(*out, cmd)
1077 }
1078 if n.Kind == Text {
1079 cmd = base
1080 cmd.Op = "text"
1081 cmd.Rect = r.Content
1082 cmd.Text = n.Content
1083 cmd.Color = s.Color
1084 runs, glyphs := textCounts(r)
1085 cmd.Runs = c.runs.take(runs)
1086 backing := c.glyphs.take(glyphs)
1087 for _, line := range r.Lines {
1088 offset := AlignOffset(s.TextAlign, line.Direction, r.Content.W, line.Width)
1089 for _, run := range line.Runs {
1090 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}
1091 if rr.Size <= 0 {
1092 rr.Size = 16 // matches the intrinsic text.Measure request fallback
1093 }
1094 if run.Face != nil {
1095 rr.FaceID = run.Face.ID
1096 }
1097 if len(run.Glyphs) > 0 { // keep nil for glyph-less runs
1098 first := len(backing)
1099 for _, g := range run.Glyphs {
1100 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})
1101 }
1102 rr.Glyphs = backing[first:len(backing):len(backing)]
1103 }
1104 cmd.Runs = append(cmd.Runs, rr)
1105 }
1106 }
1107 *out = append(*out, cmd)
1108 }
1109 j := 0
1110 for _, child := range n.Children {
1111 if child == nil || style(child).Display == css.KeywordNone {
1112 continue
1113 }
1114 if j < len(r.Children) {
1115 c.paint(child, r.Children[j], out)
1116 j++
1117 }
1118 }
1119 if r.Clipped {
1120 cmd = base
1121 cmd.Op = "clip-pop"
1122 *out = append(*out, cmd)
1123 }
1124}
1125
1126// AlignOffset is the horizontal offset of a line of width lineW inside a
1127// content box of width contentW under text-align and the line's direction.
1128func AlignOffset(align css.Keyword, direction di.Direction, contentW, lineW float64) float64 {
1129 switch align {
1130 case css.KeywordCenter:
1131 return safe(contentW-lineW) / 2
1132 case css.KeywordRight:
1133 return safe(contentW - lineW)
1134 case css.KeywordStart:
1135 if direction == di.DirectionRTL {
1136 return safe(contentW - lineW)
1137 }
1138 case css.KeywordEnd:
1139 if direction != di.DirectionRTL {
1140 return safe(contentW - lineW)
1141 }
1142 }
1143 return 0
1144}
1145
1146// Hit returns the frontmost node ID whose border box contains the logical point.
1147// Ancestor content clips constrain descendants, but not the ancestor border itself.
1148func Hit(r *Result, x, y float64) string {
1149 if math.IsNaN(x) || math.IsNaN(y) || math.IsInf(x, 0) || math.IsInf(y, 0) {
1150 return ""
1151 }
1152 return hit(r, x, y, Rect{-limit, -limit, 2 * limit, 2 * limit})
1153}
1154func hit(r *Result, x, y float64, clip Rect) string {
1155 if r == nil || !clip.Contains(x, y) {
1156 return ""
1157 }
1158 childClip := clip
1159 if r.Clipped {
1160 childClip = clip.intersect(r.Clip)
1161 }
1162 if childClip.Contains(x, y) {
1163 for i := len(r.Children) - 1; i >= 0; i-- {
1164 if id := hit(r.Children[i], x, y, childClip); id != "" {
1165 return id
1166 }
1167 }
1168 }
1169 if r.Border.Contains(x, y) {
1170 return r.ID
1171 }
1172 return ""
1173}
1174
1175// Physical is the explicit renderer boundary; all layout and hit testing stay logical.
1176// It rounds edges independently to avoid accumulated fractional-scale drift.
1177func Physical(r Rect, scale float64) (x, y, w, h int) {
1178 if math.IsNaN(scale) || math.IsInf(scale, 0) || scale <= 0 {
1179 return
1180 }
1181 scale = math.Min(scale, 1024)
1182 x = int(math.Round(coord(r.X) * scale))
1183 y = int(math.Round(coord(r.Y) * scale))
1184 w = int(math.Round(coord(r.X+safe(r.W))*scale)) - x
1185 h = int(math.Round(coord(r.Y+safe(r.H))*scale)) - y
1186 return
1187}