natsukium/nixcheck
Watch
1
Code Issues 2 Pull requests Projects Releases Packages Wiki Activity Actions

gen.sized / gen.recursive: size-driven depth for recursive generators #5

New issue
Closed
opened 2026-09-13 20:04:00 +09:00 by natsukium · 2 comments
natsukium commented 2026-09-13 20:04:00 +09:00
Owner
Copy link

Missing

Size-aware recursion helpers: gen.sized (size: gen) to read the current size, and gen.scale f g / gen.recursive leaf node so a recursive generator terminates and shrinks in depth without every caller threading a depth counter.

Where it was needed

jsonschema2nix generates recursive schemas (objects containing objects, lists, maps, unions of those). Every generator takes depth: defNames: and bottoms out with if depth <= 0 then leaf else ...:

genNode = depth: defNames:
  if depth <= 0 then genScalarSchema else
  gen.oneOf [ genScalarSchema (genListSchema (depth - 1) defNames) (genClosedSchema (depth - 1) defNames) ... ];

Depth is fixed at 2, unrelated to the test size, so small tests are not shallower than large ones and shrinking never reduces nesting; a counterexample at depth 2 stays at depth 2.

Suggested shape

  • gen.sized f (Hedgehog sized), gen.scale f g, gen.small g (scale (n: n / 2)).
  • gen.recursive leaf (self: nodes) that picks leaves at size 0 and halves the size for children, the way Hedgehog's Gen.recursive does.
## Missing Size-aware recursion helpers: `gen.sized (size: gen)` to read the current size, and `gen.scale f g` / `gen.recursive leaf node` so a recursive generator terminates and shrinks in depth without every caller threading a depth counter. ## Where it was needed jsonschema2nix generates recursive schemas (objects containing objects, lists, maps, unions of those). Every generator takes `depth: defNames:` and bottoms out with `if depth <= 0 then leaf else ...`: ```nix genNode = depth: defNames: if depth <= 0 then genScalarSchema else gen.oneOf [ genScalarSchema (genListSchema (depth - 1) defNames) (genClosedSchema (depth - 1) defNames) ... ]; ``` Depth is fixed at 2, unrelated to the test size, so small tests are not shallower than large ones and shrinking never reduces nesting; a counterexample at depth 2 stays at depth 2. ## Suggested shape - `gen.sized f` (Hedgehog `sized`), `gen.scale f g`, `gen.small g` (`scale (n: n / 2)`). - `gen.recursive leaf (self: nodes)` that picks leaves at size 0 and halves the size for children, the way Hedgehog's `Gen.recursive` does.
natsukium commented 2026-09-13 21:24:52 +09:00
Author
Owner
Copy link

Plan

Given Gen a = size: rng: Tree a:

sized = f: size: r: (f size) size r;
scale = f: g: size: r: g (f size) r;
small = scale (n: n / 2);
recursive = choose: leaves: nodes:
  sized (n: if n <= 1 then choose leaves else choose (leaves ++ builtins.map small nodes));

Straight port of Hedgehog Gen.recursive. Nix let is lazy, so no self: parameter: genNode = gen.recursive gen.oneOf [ leaf ] [ (gen.listOf … genNode) ] refers to itself directly. Halving (issue) instead of Hedgehog's golden ratio is fine for an integer size; depth stays <= log2(maxSize).

Depth shrinks only because choose (oneOf / frequency) shrinks toward the first, i.e. leaf, alternative. That is #6 and must land first. gen.anything (#12) is the intended dogfood test.

Roadmap order: #6 -> #5 -> #2 -> #1 -> #4 -> #3.

## Plan Given `Gen a = size: rng: Tree a`: ```nix sized = f: size: r: (f size) size r; scale = f: g: size: r: g (f size) r; small = scale (n: n / 2); recursive = choose: leaves: nodes: sized (n: if n <= 1 then choose leaves else choose (leaves ++ builtins.map small nodes)); ``` Straight port of Hedgehog `Gen.recursive`. Nix `let` is lazy, so no `self:` parameter: `genNode = gen.recursive gen.oneOf [ leaf ] [ (gen.listOf … genNode) ]` refers to itself directly. Halving (issue) instead of Hedgehog's golden ratio is fine for an integer size; depth stays <= log2(maxSize). Depth shrinks only because `choose` (`oneOf` / `frequency`) shrinks toward the first, i.e. leaf, alternative. That is #6 and must land first. `gen.anything` (#12) is the intended dogfood test. Roadmap order: #6 -> #5 -> #2 -> #1 -> #4 -> #3.
natsukium commented 2026-09-14 00:44:13 +09:00
Author
Owner
Copy link

Implemented in 0bb1465, pushed to main.

Implemented in 0bb1465, pushed to main.
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
main
redesign
No results found.
Labels
Clear labels
No items
No labels
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
natsukium/nixcheck#5
No description provided.