A type family can hide a recursive datatype from layout analysis and overflow both emitters

[jasisz]

What I did

bun bend2/main.ts repro-family-hidden-layout-cycle.bend --check-only
bun bend2/main.ts repro-family-hidden-layout-cycle.bend
bun bend2/main.ts repro-family-hidden-layout-cycle.bend -o out.js
bun bend2/main.ts repro-family-hidden-layout-cycle.bend -o out

import Base

law Cell:
  for b: Bool
  Data

type Nest<-b: Bool> is Data:
  End{}
  More{next: Cell(b)}

def Cell(b):
  match b:
    case False{}:
      U32
    case True{}:
      Nest<True{}>

def read(n: Nest<True{}>) -> U32:
  match n:
    case End{}:
      7
    case More{next}:
      read(next)

def main() -> U32:
  read(End{})

What happened

The checker accepts the file and the evaluator returns normally:

All terms check.
7

Both the JS and native build commands fail before producing output:

Error: the machine stack overflowed (a deep recursion, or a literal too large to expand)

main returns an ordinary U32; the recursive datatype occurs only as the parameter of the reachable read definition. The value passed to it is the finite base constructor End{}, so neither source evaluation nor term recursion is infinite.

Why it happens

lay_cyclic memoizes its answer by datatype name and walks each constructor through ctr_doms(book, c) without the datatype's actual arguments. While it examines Nest<b>, the field type Cell(b) is stuck on the open index, ty_adt returns null, and the walk records Nest as non-cyclic. comp.ts:1034-1046

Layout computation later sees the concrete type Nest<True{}>. Since the cached cycle test says false, lay_of expands More and instantiates its field. This time Cell(True{}) reduces to Nest<True{}>, so lay_fields calls lay_of recursively on the same concrete type. comp.ts:980-994

The generic memo helper installs a layout only after its callback returns, so the re-entry is not cut off and recursion continues until the JavaScript stack overflows. comp.ts:691-698

The law/fill sequence is needed only to express the legal dependency between the datatype and the type family that reveals its recursive occurrence. The filled family is total, Nest has a finite base constructor, and read is accepted by the ordinary structural descent check.

Expected behavior

A recursive datatype whose cycle becomes visible after family reduction should receive a boxed recursive layout, or the compiler should reject the unsupported layout with a finite diagnostic. A checked, terminating program should not overflow the compiler while computing its representation.

Version

bend 2.0.24
commit 99f9c6cd
Bun 1.4.2
Darwin arm64
Apple clang version 21.0.0 (clang-2100.0.123.102)

[VictorTaelin]

Fixed in 2.0.25. The layout memo is keyed by the concrete type and seeded with a box before the type's fields are laid out, so a field that re-enters the same concrete type through a family (Cell(True{}) = Nest<True{}>) is a box, which is the recursive answer. Your program prints 7 on all three lanes; Nest<False{}> stays flat. Pinned as tests/compile/family_cyclic_layout.bend. Thank you for the clean reduction.

Note: this reply was written by an AI after it reported the issue to me and I made the decision. If anything here is wrong, reply and I will review it myself.