layout, csstree: build stacking contexts together with tree

We often redo sub-layouts in layout, and this makes stacking contexts
very hard to build reliably there.

This fixes a bug where positioned descendants of flex items would
sometimes mysteriously disappear.

4 files changed, 130 insertions, 67 deletions

diff --git a/src/css/box.nim b/src/css/box.nim
index d92ba33b..8fa00a36 100644
--- a/src/css/box.nim
+++ b/src/css/box.nim
@@ -208,7 +208,6 @@ iterator children*(box: CSSBox): CSSBox =
     it = it.next
 
 proc resetState(box: CSSBox) =
-  box.positioned = false
   box.render = BoxRenderState()
 
 proc resetState*(ibox: InlineBox) =
@@ -222,16 +221,50 @@ proc resetState*(box: BlockBox) =
 const DefaultClipBox* = ClipBox(send: offset(LUnit.high, LUnit.high))
 
 when defined(debug):
-  proc computedTree*(box: CSSBox): string =
+  import chame/tags
+
+  proc `$`*(box: CSSBox; pass2 = true): string =
+    if box.positioned and not pass2:
+      return ""
     result = "<"
-    if box.computed{"display"} != DisplayInline:
-      result &= "div"
+    let name = if box.computed{"display"} != DisplayInline:
+      if box.element.tagType in {TAG_HTML, TAG_BODY}:
+        $box.element.tagType
+      else:
+        "div"
+    elif box of InlineNewLineBox:
+      "br"
     else:
-      result &= "span"
+      "span"
+    result &= name
     let computed = box.computed.copyProperties()
     if computed{"display"} == DisplayBlock:
       computed{"display"} = DisplayInline
-    result &= " style='" & $computed.serializeEmpty() & "'>\n"
+    var style = $computed.serializeEmpty()
+    if style != "":
+      if style[^1] == ';':
+        style.setLen(style.high)
+      result &= " style='" & style & "'"
+    result &= ">"
+    if box of InlineNewLineBox:
+      return
+    if box of BlockBox:
+      result &= '\n'
     for it in box.children:
-      result &= it.computedTree()
-    result &= "\n</div>"
+      result &= `$`(it, pass2 = false)
+    if box of InlineTextBox:
+      for run in InlineTextBox(box).runs:
+        result &= run.str
+    if box of BlockBox:
+      result &= '\n'
+    result &= "</" & name & ">"
+
+  proc `$`*(stack: StackItem): string =
+    result = "<STACK index=" & $stack.index & ">\n"
+    result &= `$`(stack.box, pass2 = true)
+    result &= "\n"
+    for child in stack.children:
+      result &= "<child>\n"
+      result &= $child
+      result &= "</child>\n"
+    result &= "</STACK>\n"
diff --git a/src/css/csstree.nim b/src/css/csstree.nim
index ef9fec36..04b8eef8 100644
--- a/src/css/csstree.nim
+++ b/src/css/csstree.nim
@@ -1,9 +1,8 @@
 # Tree building.
 #
-#TODO: this is currently a separate pass from layout, meaning at least
-# two tree traversals are required.  Ideally, these should be collapsed
-# into a single pass, reusing parts of previous layout passes when
-# possible.
+# This is currently a separate pass from layout, meaning at least two
+# tree traversals are required.  I'm not sure if the two can be
+# meaningfully collapsed.
 #
 # ---
 #
@@ -25,6 +24,8 @@
 #   includes the rows/row groups.
 # Whatever your reason may be for looking at this: good luck.
 
+import std/algorithm
+
 import chame/tags
 import css/box
 import css/cascade
@@ -73,6 +74,7 @@ type
     quoteLevel: int
     counters: seq[CSSCounter]
     rootProperties: CSSValues
+    stackItems: seq[StackItem]
 
   TreeFrame = object
     parent: Element
@@ -85,7 +87,8 @@ type
     pctx: ptr TreeContext
 
 # Forward declarations
-proc build(ctx: var TreeContext; cached: CSSBox; styledNode: StyledNode): CSSBox
+proc build(ctx: var TreeContext; cached: CSSBox; styledNode: StyledNode;
+  forceZ: bool): CSSBox
 
 template ctx(frame: TreeFrame): var TreeContext =
   frame.pctx[]
@@ -494,29 +497,25 @@ proc buildChildren(frame: var TreeFrame; styledNode: StyledNode) =
       for content in frame.computed{"content"}:
         frame.addContent(content)
 
-proc buildBox(ctx: var TreeContext; frame: TreeFrame; cached: CSSBox): CSSBox =
+proc buildInnerBox(ctx: var TreeContext; frame: TreeFrame; cached: CSSBox):
+    CSSBox =
   let display = frame.computed{"display"}
   let box = if display == DisplayInline:
     InlineBox(computed: frame.computed, element: frame.parent)
   else:
     BlockBox(computed: frame.computed, element: frame.parent)
+  # Grid and flex items always respect z-index.  Other boxes only
+  # respect it with position != static.
+  let forceZ = display in DisplayInnerFlex or display in DisplayInnerGrid
   var last: CSSBox = nil
   for child in frame.children:
-    let childBox = ctx.build(nil, child)
+    let childBox = ctx.build(nil, child, forceZ)
     childBox.parent = box
     if last != nil:
       last.next = childBox
     else:
       box.firstChild = childBox
     last = childBox
-  if display in DisplayInlineBlockLike:
-    let wrapper = InlineBlockBox(
-      computed: ctx.rootProperties,
-      element: frame.parent,
-      firstChild: box
-    )
-    box.parent = wrapper
-    return wrapper
   return box
 
 proc applyCounters(ctx: var TreeContext; styledNode: StyledNode) =
@@ -531,17 +530,58 @@ proc applyCounters(ctx: var TreeContext; styledNode: StyledNode) =
   for counter in styledNode.computed{"counter-set"}:
     ctx.setCounter(counter.name, counter.num, styledNode.element)
 
-proc build(ctx: var TreeContext; cached: CSSBox; styledNode: StyledNode):
-    CSSBox =
+proc pushStackItem(ctx: var TreeContext; styledNode: StyledNode):
+    StackItem =
+  let index = styledNode.computed{"z-index"}
+  let stack = StackItem(index: index.num)
+  ctx.stackItems[^1].children.add(stack)
+  let nextStack = if index.auto:
+    ctx.stackItems[^1]
+  else:
+    stack
+  ctx.stackItems.add(nextStack)
+  return stack
+
+proc popStackItem(ctx: var TreeContext) =
+  let stack = ctx.stackItems.pop()
+  stack.children.sort(proc(x, y: StackItem): int = cmp(x.index, y.index))
+
+proc buildOuterBox(ctx: var TreeContext; cached: CSSBox; styledNode: StyledNode;
+    forceZ: bool): CSSBox =
+  ctx.applyCounters(styledNode)
+  let countersLen = ctx.counters.len
+  var frame = ctx.initTreeFrame(styledNode.element, styledNode.computed)
+  var stackItem: StackItem = nil
+  let display = frame.computed{"display"}
+  let position = frame.computed{"position"}
+  if position != PositionStatic and display notin DisplayNeverHasStack or
+      forceZ and not frame.computed{"z-index"}.auto:
+    stackItem = ctx.pushStackItem(styledNode)
+  frame.buildChildren(styledNode)
+  let box = ctx.buildInnerBox(frame, cached)
+  ctx.counters.setLen(countersLen)
+  if stackItem != nil:
+    if box of InlineBlockBox:
+      stackItem.box = box.firstChild
+    else:
+      stackItem.box = box
+    box.positioned = position != PositionStatic
+    ctx.popStackItem()
+  if display in DisplayInlineBlockLike:
+    let wrapper = InlineBlockBox(
+      computed: ctx.rootProperties,
+      element: frame.parent,
+      firstChild: box
+    )
+    box.parent = wrapper
+    return wrapper
+  return box
+
+proc build(ctx: var TreeContext; cached: CSSBox; styledNode: StyledNode;
+    forceZ: bool): CSSBox =
   case styledNode.t
   of stElement:
-    ctx.applyCounters(styledNode)
-    let countersLen = ctx.counters.len
-    var frame = ctx.initTreeFrame(styledNode.element, styledNode.computed)
-    frame.buildChildren(styledNode)
-    let box = ctx.buildBox(frame, cached)
-    ctx.counters.setLen(countersLen)
-    return box
+    return ctx.buildOuterBox(cached, styledNode, forceZ)
   of stText:
     return InlineTextBox(
       computed: styledNode.computed,
@@ -569,7 +609,7 @@ proc build(ctx: var TreeContext; cached: CSSBox; styledNode: StyledNode):
     )
 
 # Root
-proc buildTree*(element: Element; cached: CSSBox; markLinks: bool): BlockBox =
+proc buildTree*(element: Element; cached: CSSBox; markLinks: bool): StackItem =
   if element.computed == nil:
     element.applyStyle()
   let styledNode = StyledNode(
@@ -577,8 +617,13 @@ proc buildTree*(element: Element; cached: CSSBox; markLinks: bool): BlockBox =
     element: element,
     computed: element.computed
   )
+  let stack = StackItem()
   var ctx = TreeContext(
     rootProperties: rootProperties(),
-    markLinks: markLinks
+    markLinks: markLinks,
+    stackItems: @[stack]
   )
-  return BlockBox(ctx.build(cached, styledNode))
+  let root = BlockBox(ctx.build(cached, styledNode, forceZ = false))
+  stack.box = root
+  ctx.popStackItem()
+  return stack
diff --git a/src/css/cssvalues.nim b/src/css/cssvalues.nim
index 919e9299..16901d13 100644
--- a/src/css/cssvalues.nim
+++ b/src/css/cssvalues.nim
@@ -573,13 +573,12 @@ const RowGroupBox* = {
   # Note: caption is not included here
   DisplayTableRowGroup, DisplayTableHeaderGroup, DisplayTableFooterGroup
 }
-const ProperTableChild* = RowGroupBox + {
-  DisplayTableRow, DisplayTableColumn, DisplayTableColumnGroup
-}
 const DisplayInnerTable* = {DisplayTable, DisplayInlineTable}
 const DisplayInternalTable* = {
   DisplayTableCell, DisplayTableRow, DisplayTableCaption
 } + RowGroupBox
+const DisplayNeverHasStack* = DisplayInternalTable + DisplayInnerTable -
+  {DisplayTableCell}
 const PositionAbsoluteFixed* = {PositionAbsolute, PositionFixed}
 const WhiteSpacePreserve* = {
   WhitespacePre, WhitespacePreLine, WhitespacePreWrap
diff --git a/src/css/layout.nim b/src/css/layout.nim
index cc1365e3..8c8a8240 100644
--- a/src/css/layout.nim
+++ b/src/css/layout.nim
@@ -28,7 +28,6 @@ type
     child: BlockBox
 
   PositionedItem = object
-    stack: StackItem # stacking context to append children to
     queue: seq[QueuedAbsolute]
 
   LayoutContext = ref object
@@ -1437,19 +1436,10 @@ proc layoutText(fstate: var FlowState; istate: var InlineState; s: string) =
     fstate.layoutTextLoop(istate, s)
 
 proc pushPositioned(lctx: LayoutContext; box: CSSBox) =
-  let index = box.computed{"z-index"}
-  let stack = StackItem(box: box, index: index.num)
-  lctx.positioned[^1].stack.children.add(stack)
-  let nextStack = if index.auto:
-    lctx.positioned[^1].stack
-  else:
-    stack
-  box.positioned = box.computed{"position"} != PositionStatic
-  lctx.positioned.add(PositionedItem(stack: nextStack))
+  lctx.positioned.add(PositionedItem())
 
 # size is the parent's size.
-# Note that parent may be nil.
-proc popPositioned(lctx: LayoutContext; parent: CSSBox; size: Size) =
+proc popPositioned(lctx: LayoutContext; size: Size) =
   let item = lctx.positioned.pop()
   for it in item.queue:
     let child = it.child
@@ -1483,9 +1473,6 @@ proc popPositioned(lctx: LayoutContext; parent: CSSBox; size: Size) =
         sizes.margin.bottom
     else:
       child.state.offset.y += sizes.margin.top
-  let stack = item.stack
-  if stack.box == parent:
-    stack.children.sort(proc(x, y: StackItem): int = cmp(x.index, y.index))
 
 proc queueAbsolute(lctx: LayoutContext; box: BlockBox; offset: Offset) =
   case box.computed{"position"}
@@ -1536,7 +1523,7 @@ proc layoutRootBlock(lctx: LayoutContext; box: BlockBox; offset: Offset;
   box.state.intr.h = max(box.state.intr.h + marginBottom, bctx.maxFloatHeight)
   box.state.marginBottom = marginBottom
   if positioned:
-    bctx.lctx.popPositioned(box, box.state.size)
+    bctx.lctx.popPositioned(box.state.size)
 
 func clearedBy(floats: set[CSSFloat]; clear: CSSClear): bool =
   return case clear
@@ -1658,7 +1645,7 @@ proc layoutBlockChild(fstate: var FlowState; child: BlockBox;
       lctx.pushPositioned(child)
     fstate.bctx.layout(child, sizes)
     if child.computed{"position"} != PositionStatic:
-      lctx.popPositioned(child, child.state.size)
+      lctx.popPositioned(child.state.size)
   fstate.bctx.marginTodo.append(sizes.margin.bottom)
   let outerSize = size(
     w = child.outerSize(dtHorizontal, sizes),
@@ -1917,7 +1904,7 @@ proc layoutInline(fstate: var FlowState; ibox: InlineBox) =
       # since this uses cellHeight instead of the actual line height
       # for the last line.
       # Well, it seems good enough.
-      lctx.popPositioned(ibox, size(
+      lctx.popPositioned(size(
         w = 0,
         h = fstate.offset.y + fstate.cellHeight - ibox.state.startOffset.y
       ))
@@ -2129,7 +2116,7 @@ proc layoutTableCell(lctx: LayoutContext; box: BlockBox;
     lctx.pushPositioned(box)
   bctx.layout(box, sizes)
   if box.computed{"position"} != PositionStatic:
-    lctx.popPositioned(box, box.state.size)
+    lctx.popPositioned(box.state.size)
   assert bctx.unpositionedFloats.len == 0
   # Table cells ignore margins.
   box.state.offset.y = 0
@@ -2856,20 +2843,19 @@ proc layout(bctx: var BlockContext; box: BlockBox; sizes: ResolvedSizes) =
   of DisplayInnerGrid: bctx.layoutGrid(box, sizes)
   else: assert false
 
-proc layout*(box: BlockBox; attrsp: ptr WindowAttributes): StackItem =
+proc layout*(box: BlockBox; attrsp: ptr WindowAttributes) =
   let space = availableSpace(
     w = stretch(attrsp[].widthPx),
     h = stretch(attrsp[].heightPx)
   )
-  let stack = StackItem(box: box)
   let lctx = LayoutContext(
     attrsp: attrsp,
     cellSize: size(w = attrsp.ppc, h = attrsp.ppl),
     positioned: @[
       # add another to catch fixed boxes pushed to the stack
-      PositionedItem(stack: stack),
-      PositionedItem(stack: stack),
-      PositionedItem(stack: stack)
+      PositionedItem(),
+      PositionedItem(),
+      PositionedItem()
     ],
     luctx: LUContext()
   )
@@ -2878,7 +2864,7 @@ proc layout*(box: BlockBox; attrsp: ptr WindowAttributes): StackItem =
   lctx.layoutRootBlock(box, sizes.margin.topLeft, sizes)
   var size = size(w = attrsp[].widthPx, h = attrsp[].heightPx)
   # Last absolute layer.
-  lctx.popPositioned(nil, size)
+  lctx.popPositioned(size)
   # Fixed containing block.
   # The idea is to move fixed boxes to the real edges of the page,
   # so that they do not overlap with other boxes *and* we don't have
@@ -2887,7 +2873,7 @@ proc layout*(box: BlockBox; attrsp: ptr WindowAttributes): StackItem =
   # slow down the renderer to a crawl.)
   size.w = max(size.w, box.state.size.w)
   size.h = max(size.h, box.state.size.h)
-  lctx.popPositioned(nil, size)
-  # Now we can sort the root box's stacking context list.
-  lctx.popPositioned(box, size)
-  return stack
+  lctx.popPositioned(size)
+  # I'm not sure why the third PositionedItem is needed, but without
+  # this fixed boxes appear in the wrong place.
+  lctx.popPositioned(size)