gen.int: span overflow on full-width ranges #16

New issue

Open

opened 2026-09-14 00:44:13 +09:00 by natsukium · 1 comment

natsukium commented

2026-09-14 00:44:13 +09:00

Owner

Bug

gen.int computes hi - lo + 1 for the span of the drawn interval, so a range covering the full Nix integer width overflows and the draw aborts:

gen.int (range.exponentialFrom 0 (-4611686018427387904) 4611686018427387904)  # +-2^62, aborts at size 100

gen.anythingWith sidesteps it with +-(2^62 - 1) (see d153fd0), but any user range wider than 2^63 - 1 hits the same overflow, silently or with an abort that tryEval cannot catch.

Suggested fix

Draw the two halves separately when hi - lo does not fit (e.g. sign draw + magnitude draw), or clamp the span and document the limit.
Same check for towards shrink candidates, which compute x - origin.
Dogfood test: int (range.constant (-9223372036854775807) 9223372036854775807) neither aborts nor leaves the bounds.

Found while implementing #12.

## Bug `gen.int` computes `hi - lo + 1` for the span of the drawn interval, so a range covering the full Nix integer width overflows and the draw aborts: ```nix gen.int (range.exponentialFrom 0 (-4611686018427387904) 4611686018427387904) # +-2^62, aborts at size 100 ``` `gen.anythingWith` sidesteps it with `+-(2^62 - 1)` (see `d153fd0`), but any user range wider than 2^63 - 1 hits the same overflow, silently or with an abort that `tryEval` cannot catch. ## Suggested fix - Draw the two halves separately when `hi - lo` does not fit (e.g. sign draw + magnitude draw), or clamp the span and document the limit. - Same check for `towards` shrink candidates, which compute `x - origin`. - Dogfood test: `int (range.constant (-9223372036854775807) 9223372036854775807)` neither aborts nor leaves the bounds. Found while implementing #12.

natsukium commented

2026-09-14 02:04:15 +09:00

Author

Owner

The span overflow itself is untouched — gen.int still computes hi - lo + 1.
But a precondition for any fix is now in place, and part of the dogfood test is
covered.

rng.below used to read a single 24-bit word and take it modulo the bound, so
no draw could land more than 2^24 above a range's low end (844a40c). Fixing the
span computation alone would therefore not have helped: even with a correct span
for a full-width range, every draw would still have clustered at the bottom.
below now assembles the draw from several words and lands in [0, 2^63)
exactly, the top word cut to 15 bits so the largest sum is 2^63 - 1 — which is
the largest bound gen.int can express before the span overflows. So the draw
side is ready for whatever the span side ends up doing.

The suggested dogfood test is int (range.constant (-9223372036854775807) 9223372036854775807), whose span is 2^64 - 1 and still overflows. The widest
span that does not overflow is now exercised: tests/self.nix has "int over a
range wider than one rng word reaches both of its halves", which draws from
range.constant (-(2^62 - 1)) (2^62 - 1) — span exactly 2^63 - 1 — and asserts
both halves are reached (672fb60). It pins the arithmetic just under the NixInt
maximum, so the remaining work here is the overflow above that point.

Still open as filed: the span computation, and the same check for towards,
which computes x - origin.

The span overflow itself is untouched — `gen.int` still computes `hi - lo + 1`. But a precondition for any fix is now in place, and part of the dogfood test is covered. `rng.below` used to read a single 24-bit word and take it modulo the bound, so no draw could land more than 2^24 above a range's low end (844a40c). Fixing the span computation alone would therefore not have helped: even with a correct span for a full-width range, every draw would still have clustered at the bottom. `below` now assembles the draw from several words and lands in `[0, 2^63)` exactly, the top word cut to 15 bits so the largest sum is 2^63 - 1 — which is the largest bound `gen.int` can express before the span overflows. So the draw side is ready for whatever the span side ends up doing. The suggested dogfood test is `int (range.constant (-9223372036854775807) 9223372036854775807)`, whose span is 2^64 - 1 and still overflows. The widest span that does *not* overflow is now exercised: `tests/self.nix` has "int over a range wider than one rng word reaches both of its halves", which draws from `range.constant (-(2^62 - 1)) (2^62 - 1)` — span exactly 2^63 - 1 — and asserts both halves are reached (672fb60). It pins the arithmetic just under the NixInt maximum, so the remaining work here is the overflow above that point. Still open as filed: the span computation, and the same check for `towards`, which computes `x - origin`.

No labels

No milestone

No project

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#16

No description provided.

Rows
Columns