1import type * as Cause from "../../Cause.ts"
2import * as Effect from "../../Effect.ts"
3import * as Option from "../../Option.ts"
4import * as InternalArray from "../array.ts"
5import { done } from "../core.ts"
6
7/** @internal */
8export type ShrinkPull<A> = Effect.Effect<A, Cause.Done>
9
10/** @internal */
11export interface Sample<out A> {
12 readonly _tag: "Generated"
13 readonly value: A
14 readonly shrinks: ShrinkPull<Attempt<A>> | undefined
15}
16
17/** @internal */
18export interface Discarded {
19 readonly _tag: "Discarded"
20}
21
22/** @internal */
23export type Attempt<A> = Sample<A> | Discarded
24
25/** @internal */
26export type Computation<A> = A | Effect.Effect<A>
27
28/** @internal */
29export type Generation<A> = Computation<Attempt<A>>
30
31/** @internal */
32export interface GenerationRandom {
33 readonly nextUint32: () => number
34 readonly nextDoubleUnsafe: () => number
35 readonly clone: () => GenerationRandom
36 readonly copyFrom: (source: GenerationRandom) => void
37 readonly snapshot: () => readonly [number, number, number, number]
38}
39
40/** @internal */
41export interface GenerationState {
42 readonly size: number
43 readonly shrinks: boolean
44 readonly biasFactor: number
45 readonly nullPrototype: boolean
46 readonly random: GenerationRandom
47 readonly budget: {
48 remaining: number
49 }
50}
51
52/** @internal */
53export interface Generator<A> {
54 readonly minCost: number
55 readonly generate: (state: GenerationState) => Generation<A>
56}
57
58/** @internal */
59export interface Compiled<A> extends Generator<A> {
60 minCost: number
61 recursive: boolean
62 mayRecurse: boolean
63 dependencies: ReadonlyArray<Compiled<any>>
64 computeMinCost: () => number
65 generate: (state: GenerationState) => Generation<A>
66}
67
68/** @internal */
69export const discarded: Discarded = { _tag: "Discarded" }
70
71/** @internal */
72export function mapComputation<A, B>(self: Computation<A>, f: (value: A) => B): Computation<B> {
73 return Effect.isEffect(self) ? Effect.mapEager(self as Effect.Effect<A>, f) : f(self as A)
74}
75
76/** @internal */
77export function flatMapComputation<A, B>(
78 self: Computation<A>,
79 f: (value: A) => Computation<B>
80): Computation<B> {
81 return Effect.isEffect(self)
82 ? Effect.flatMapEager(self as Effect.Effect<A>, (value) => toEffect(f(value)))
83 : f(self as A)
84}
85
86/** @internal */
87export function toEffect<A>(self: Computation<A>): Effect.Effect<A> {
88 return Effect.isEffect(self) ? self as Effect.Effect<A> : Effect.succeed(self as A)
89}
90
91/** @internal */
92export function isAttempt<A>(self: Generation<A>): self is Attempt<A> {
93 return (self as Attempt<A>)._tag === "Generated" || (self as Attempt<A>)._tag === "Discarded"
94}
95
96/** @internal */
97export function mapGeneration<A, B>(
98 self: Generation<A>,
99 f: (value: Attempt<A>) => Attempt<B>
100): Generation<B> {
101 return isAttempt(self) ? f(self) : Effect.mapEager(self, f)
102}
103
104/** @internal */
105export function flatMapGeneration<A, B>(
106 self: Generation<A>,
107 f: (value: Attempt<A>) => Generation<B>
108): Generation<B> {
109 return isAttempt(self)
110 ? f(self)
111 : Effect.flatMapEager(self, (value) => toEffectGeneration(f(value)))
112}
113
114/** @internal */
115export function toEffectGeneration<A>(self: Generation<A>): Effect.Effect<Attempt<A>> {
116 return isAttempt(self) ? Effect.succeed(self) : self
117}
118
119/** @internal */
120export function pullFromArray<A>(values: ReadonlyArray<A>): ShrinkPull<A> {
121 let index = 0
122 return Effect.suspend(() => index >= values.length ? done() : Effect.succeed(values[index++]))
123}
124
125/** @internal */
126export function concatPulls<A>(pulls: ReadonlyArray<ShrinkPull<A>>): ShrinkPull<A> {
127 let index = 0
128 const loop = (): ShrinkPull<A> =>
129 Effect.suspend(() =>
130 index >= pulls.length
131 ? done()
132 : Effect.catch(pulls[index], () => {
133 index++
134 return loop()
135 })
136 )
137 return loop()
138}
139
140/** @internal */
141export const makeSample = <A>(value: A, shrinks?: ShrinkPull<Attempt<A>>): Sample<A> => ({
142 _tag: "Generated",
143 value,
144 shrinks
145})
146
147/** @internal */
148export function makeSampleWithLazyShrinks<A>(
149 value: A,
150 makeShrinks: () => ShrinkPull<Attempt<A>> | undefined
151): Sample<A> {
152 let shrinks: ShrinkPull<Attempt<A>> | undefined
153 return makeSample(
154 value,
155 Effect.suspend(() => {
156 shrinks ??= makeShrinks() ?? done()
157 return shrinks
158 })
159 )
160}
161
162/** @internal */
163export interface Retained<out A> {
164 readonly _tag: "Retained"
165 readonly value: A
166 readonly shrinks: (() => ShrinkPull<Retained<A> | Discarded>) | undefined
167}
168
169// Collection candidates share their children. Give each candidate its own cursor
170// over a lazy child history so exploring one branch cannot exhaust another.
171/** @internal */
172export function retain<A>(sample: Sample<A>): Retained<A> {
173 const source = sample.shrinks
174 if (source === undefined) return { _tag: "Retained", value: sample.value, shrinks: undefined }
175 let history: Array<Retained<A> | Discarded> | undefined
176 let ended = false
177 return {
178 _tag: "Retained",
179 value: sample.value,
180 shrinks: () => {
181 let index = 0
182 return Effect.suspend(() => {
183 if (history !== undefined && index < history.length) return Effect.succeed(history[index++])
184 if (ended) return done()
185 return Effect.matchEffect(source, {
186 onFailure: () => {
187 ended = true
188 return done()
189 },
190 onSuccess: (attempt) => {
191 const item = attempt._tag === "Discarded" ? attempt : retain(attempt)
192 history ??= []
193 history.push(item)
194 index++
195 return Effect.succeed(item)
196 }
197 })
198 })
199 }
200 }
201}
202
203/** @internal */
204export function fromRetained<A>(self: Retained<A>): Sample<A> {
205 return makeSample(
206 self.value,
207 self.shrinks === undefined
208 ? undefined
209 : Effect.map(self.shrinks(), (attempt) => attempt._tag === "Discarded" ? attempt : fromRetained(attempt))
210 )
211}
212
213/** @internal */
214export function mapAttempt<A, B>(self: Attempt<A>, f: (sample: Sample<A>) => Sample<B>): Attempt<B> {
215 return self._tag === "Discarded" ? self : f(self)
216}
217
218/** @internal */
219export function sampleFromShrink<A>(value: A, shrink: (value: A) => ReadonlyArray<A>): Sample<A> {
220 const values = shrink(value)
221 return makeSample(
222 value,
223 values.length === 0 ? undefined : Effect.map(pullFromArray(values), (value) => sampleFromShrink(value, shrink))
224 )
225}
226
227/** @internal */
228export function sampleFromValidatedShrink<A>(
229 value: A,
230 shrink: (value: A) => ReadonlyArray<A>,
231 validate: (value: A) => Computation<Option.Option<A>>
232): Sample<A> {
233 return makeSampleWithLazyShrinks(
234 value,
235 () =>
236 Effect.flatMapEager(
237 pullFromArray(shrink(value)),
238 (candidate) =>
239 Effect.mapEager(toEffect(validate(candidate)), (validated) =>
240 Option.isSome(validated)
241 ? sampleFromValidatedShrink(validated.value, shrink, validate)
242 : discarded)
243 )
244 )
245}
246
247/** @internal */
248export function mapSample<A, B>(self: Sample<A>, f: (value: A) => B): Sample<B> {
249 return makeSample(
250 f(self.value),
251 self.shrinks === undefined
252 ? undefined
253 : Effect.map(self.shrinks, (attempt) => mapAttempt(attempt, (sample) => mapSample(sample, f)))
254 )
255}
256
257/** @internal */
258export function productSample<A>(
259 children: ReadonlyArray<Sample<any>>,
260 make: (children: ReadonlyArray<{ readonly value: any }>) => A
261): Sample<A> {
262 const value = make(children)
263 if (!children.some((child) => child.shrinks !== undefined)) return makeSample(value)
264 const rebuild = (children: ReadonlyArray<Retained<any>>, start = 0): Sample<A> => {
265 const pulls: Array<ShrinkPull<Attempt<A>>> = []
266 // Preserve field order explicitly instead of relying on exhausted sibling cursors.
267 for (let index = start; index < children.length; index++) {
268 const shrinks = children[index].shrinks
269 if (shrinks !== undefined) {
270 pulls.push(Effect.map(
271 shrinks(),
272 (attempt) =>
273 attempt._tag === "Discarded" ? attempt : rebuild(InternalArray.replaceAt(children, index, attempt), index)
274 ))
275 }
276 }
277 return makeSample(make(children), pulls.length === 0 ? undefined : concatPulls(pulls))
278 }
279 return makeSampleWithLazyShrinks(value, () => rebuild(children.map(retain)).shrinks)
280}
281
282function filterMapPull<A, B>(
283 source: ShrinkPull<Attempt<A>>,
284 f: (value: A) => Computation<Option.Option<B>>
285): ShrinkPull<Attempt<B>> {
286 const stack: Array<ShrinkPull<Attempt<A>>> = [source]
287 const loop = (): ShrinkPull<Attempt<B>> =>
288 Effect.suspend(() => {
289 const current = stack[stack.length - 1]
290 if (current === undefined) return done()
291 return Effect.matchEffect(current, {
292 onFailure: () => {
293 stack.pop()
294 return loop()
295 },
296 onSuccess: (attempt) => {
297 if (attempt._tag === "Discarded") return Effect.succeed<Attempt<B>>(attempt)
298 const sample = attempt
299 return Effect.flatMapEager(toEffect(f(sample.value)), (mapped) => {
300 if (Option.isSome(mapped)) {
301 return Effect.succeed<Attempt<B>>(makeSample(
302 mapped.value,
303 sample.shrinks === undefined ? undefined : filterMapPull(sample.shrinks, f)
304 ))
305 }
306 if (sample.shrinks !== undefined) stack.push(sample.shrinks)
307 return Effect.succeed<Attempt<B>>(discarded)
308 })
309 }
310 })
311 })
312 return loop()
313}
314
315function filterPull<A>(source: ShrinkPull<Attempt<A>>, predicate: (value: A) => boolean): ShrinkPull<Attempt<A>> {
316 const stack: Array<ShrinkPull<Attempt<A>>> = [source]
317 const loop = (): ShrinkPull<Attempt<A>> =>
318 Effect.suspend(() => {
319 const current = stack[stack.length - 1]
320 if (current === undefined) return done()
321 return Effect.matchEffect(current, {
322 onFailure: () => {
323 stack.pop()
324 return loop()
325 },
326 onSuccess: (attempt) => {
327 if (attempt._tag === "Discarded") return Effect.succeed<Attempt<A>>(attempt)
328 const sample = attempt
329 if (predicate(sample.value)) {
330 return Effect.succeed<Attempt<A>>(makeSample(
331 sample.value,
332 sample.shrinks === undefined ? undefined : filterPull(sample.shrinks, predicate)
333 ))
334 }
335 if (sample.shrinks !== undefined) stack.push(sample.shrinks)
336 return Effect.succeed<Attempt<A>>(discarded)
337 }
338 })
339 })
340 return loop()
341}
342
343/** @internal */
344export const filterMapSample = <A, B>(
345 self: Sample<A>,
346 f: (value: A) => Computation<Option.Option<B>>
347): Computation<Sample<B> | undefined> =>
348 mapComputation(
349 f(self.value),
350 (value) =>
351 Option.isNone(value)
352 ? undefined
353 : makeSample(
354 value.value,
355 self.shrinks === undefined ? undefined : filterMapPull(self.shrinks, f)
356 )
357 )
358
359/** @internal */
360export const filterMapGeneration = <A, B>(
361 self: Generation<A>,
362 f: (value: A) => Computation<Option.Option<B>>
363): Generation<B> =>
364 flatMapGeneration(self, (attempt) =>
365 attempt._tag === "Discarded"
366 ? attempt
367 : mapComputation(
368 filterMapSample(attempt, f),
369 (sample) => sample ?? discarded
370 ))
371
372/** @internal */
373export const filterSample = <A>(self: Sample<A>, predicate: (value: A) => boolean): Sample<A> | undefined =>
374 predicate(self.value)
375 ? self.shrinks === undefined
376 ? self
377 : makeSample(self.value, filterPull(self.shrinks, predicate))
378 : undefined
379
380/** @internal */
381export function makeGenerator<A>(minCost: number, generate: Generator<A>["generate"]): Generator<A> {
382 return { minCost, generate }
383}
384
385/** @internal */
386export const generateWithReservedBudget = (
387 child: Generator<any>,
388 state: GenerationState,
389 reserved: number
390): Generation<any> => {
391 if (child.minCost + reserved > state.budget.remaining) return discarded
392 if (reserved === 0) return child.generate(state)
393 state.budget.remaining -= reserved
394 return mapGeneration(child.generate(state), (attempt) => {
395 state.budget.remaining += reserved
396 return attempt
397 })
398}
399
400/** @internal */
401export function generateProduct(
402 children: ReadonlyArray<Generator<any>>,
403 state: GenerationState,
404 order: ReadonlyArray<number> | undefined,
405 initialReserved: number
406): Computation<Array<Sample<any>> | undefined> {
407 let reserved = initialReserved
408 if (reserved > state.budget.remaining) return undefined
409 const out = new Array<Sample<any>>(children.length)
410 let index = 0
411 const loop = (): Computation<Array<Sample<any>> | undefined> => {
412 while (index < children.length) {
413 const childIndex = order?.[index] ?? index
414 index++
415 const child = children[childIndex]
416 reserved -= child.minCost
417 const generated = generateWithReservedBudget(child, state, reserved)
418 if (isAttempt(generated)) {
419 if (generated._tag === "Discarded") return undefined
420 out[childIndex] = generated
421 continue
422 }
423 return Effect.flatMapEager(generated, (attempt) => {
424 if (attempt._tag === "Discarded") return Effect.succeed(undefined)
425 out[childIndex] = attempt
426 return toEffect(loop())
427 })
428 }
429 return out
430 }
431 return loop()
432}
433
434/** @internal */
435export function makeCompiled<A>(
436 dependencies: ReadonlyArray<Compiled<any>>,
437 computeMinCost: () => number,
438 generate: Compiled<A>["generate"]
439): Compiled<A> {
440 return {
441 minCost: Number.POSITIVE_INFINITY,
442 recursive: false,
443 mayRecurse: false,
444 dependencies,
445 computeMinCost,
446 generate
447 }
448}
449
450/** @internal */
451export const randomIndex = (state: GenerationState, length: number): number =>
452 length === 1 ? 0 : randomUint32Below(state, length)
453
454/** @internal */
455export function generateUnion<A>(members: ReadonlyArray<Generator<A>>, state: GenerationState): Generation<A> {
456 const eligible = members.filter((member) => member.minCost <= state.budget.remaining)
457 if (eligible.length === 0) return discarded
458 const selected = eligible[randomIndex(state, eligible.length)]
459 return mapGeneration(selected.generate(state), (attempt) => {
460 if (!state.shrinks || attempt._tag === "Discarded") return attempt
461 let fallback = members[0]
462 for (let index = 1; index < members.length; index++) {
463 if (members[index].minCost < fallback.minCost) fallback = members[index]
464 }
465 if (fallback.minCost >= selected.minCost) return attempt
466
467 const fallbackRandom = state.random.clone()
468 // This lazy cross-branch fallback follows fast-check v4.9.0's FrequencyArbitrary withCrossShrink idea (MIT): a
469 // value selected from a recursive branch first shrinks toward the productive base branch.
470 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/FrequencyArbitrary.ts
471 let pulled = false
472 const fallbackPull = Effect.suspend(() => {
473 if (pulled) return done()
474 pulled = true
475 return toEffectGeneration(fallback.generate({
476 ...state,
477 random: fallbackRandom,
478 budget: { remaining: fallback.minCost }
479 }))
480 })
481 return makeSample(
482 attempt.value,
483 attempt.shrinks === undefined ? fallbackPull : concatPulls([fallbackPull, attempt.shrinks])
484 )
485 })
486}
487
488const numberOfUint32Values = 0x100000000
489const numberOfDoubleValues = 0x20000000000000
490
491function randomUint32Below(state: GenerationState, rangeSize: number): number {
492 // Equal-size buckets plus rejection apply the same unbiased selection principle as pure-rand v8.4.1's
493 // uniformIntInternal (MIT), used by fast-check v4.9.0. Small discrete ranges consume one PRNG word instead of
494 // constructing a 53-bit double.
495 // https://github.com/dubzzz/pure-rand/blob/v8.4.1/src/distribution/uniformInt.ts
496 const bucketSize = Math.floor(numberOfUint32Values / rangeSize)
497 const maximumAccepted = bucketSize * rangeSize
498 let value = state.random.nextUint32()
499 while (value >= maximumAccepted) value = state.random.nextUint32()
500 return Math.floor(value / bucketSize)
501}
502
503function makeRandomUint32Below(rangeSize: number): (state: GenerationState) => number {
504 const bucketSize = Math.floor(numberOfUint32Values / rangeSize)
505 const maximumAccepted = bucketSize * rangeSize
506 return (state) => {
507 let value = state.random.nextUint32()
508 while (value >= maximumAccepted) value = state.random.nextUint32()
509 return Math.floor(value / bucketSize)
510 }
511}
512
513/** @internal */
514export const randomInt = (state: GenerationState, minimum: number, maximum: number): number => {
515 minimum = Math.ceil(minimum)
516 maximum = Math.floor(maximum)
517 if (minimum === maximum) return minimum
518 const width = maximum - minimum + 1
519 if (width <= numberOfUint32Values) return minimum + randomUint32Below(state, width)
520 if (width <= numberOfDoubleValues) {
521 // Equal-size buckets plus rejection apply the same unbiased selection principle as pure-rand v8.4.1's uniformInt
522 // (MIT), used by fast-check v4.9.0.
523 // https://github.com/dubzzz/pure-rand/blob/v8.4.1/src/distribution/uniformInt.ts
524 const bucketSize = Math.floor(numberOfDoubleValues / width)
525 const maximumAccepted = bucketSize * width
526 while (true) {
527 const value = Math.floor(state.random.nextDoubleUnsafe() * numberOfDoubleValues)
528 if (value < maximumAccepted) return minimum + Math.floor(value / bucketSize)
529 }
530 }
531 return Number(randomBigInt(state, BigInt(minimum), BigInt(maximum)))
532}
533
534/** @internal */
535export const makeObject = (nullPrototype: boolean): Record<PropertyKey, any> => nullPrototype ? Object.create(null) : {}
536
537/** @internal */
538export const randomLength = (state: GenerationState, minimum: number, maximum: number): number => {
539 if (minimum === maximum) return minimum
540 // This applies fast-check v4.9.0's run-dependent numeric edge-bias principle to the small discrete length domain
541 // (MIT): occasionally target either boundary, otherwise retain uniform selection across the complete interval.
542 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/IntegerArbitrary.ts
543 if (randomInt(state, 1, state.biasFactor) === 1) return randomBoolean(state) ? minimum : maximum
544 return randomInt(state, minimum, maximum)
545}
546
547/** @internal */
548export const randomBigInt = (state: GenerationState, minimum: bigint, maximum: bigint): bigint => {
549 if (minimum === maximum) return minimum
550 const width = maximum - minimum + BigInt(1)
551 const bitLength = (width - BigInt(1)).toString(2).length
552 const leadingBits = (bitLength - 1) % 32 + 1
553 const leadingRange = 2 ** leadingBits
554 // Arbitrary-width rejection sampling follows the same principle as pure-rand v8.4.1's uniformBigInt (MIT), used by
555 // fast-check v4.9.0. This implementation draws unsigned words from the private attempt PRNG instead of pure-rand.
556 // https://github.com/dubzzz/pure-rand/blob/v8.4.1/src/distribution/uniformBigInt.ts
557 while (true) {
558 let value = BigInt(randomUint32Below(state, leadingRange))
559 for (let remaining = bitLength - leadingBits; remaining > 0; remaining -= 32) {
560 const word = BigInt(state.random.nextUint32())
561 value = value << BigInt(32) | word
562 }
563 if (value < width) return minimum + value
564 }
565}
566
567function makeRandomInt(minimum: number, maximum: number): (state: GenerationState) => number {
568 minimum = Math.ceil(minimum)
569 maximum = Math.floor(maximum)
570 if (minimum === maximum) return () => minimum
571 const width = maximum - minimum + 1
572 if (width <= numberOfUint32Values) {
573 const randomBelow = makeRandomUint32Below(width)
574 return (state) => minimum + randomBelow(state)
575 }
576 if (width <= numberOfDoubleValues) {
577 const bucketSize = Math.floor(numberOfDoubleValues / width)
578 const maximumAccepted = bucketSize * width
579 return (state) => {
580 while (true) {
581 const value = Math.floor(state.random.nextDoubleUnsafe() * numberOfDoubleValues)
582 if (value < maximumAccepted) return minimum + Math.floor(value / bucketSize)
583 }
584 }
585 }
586 const random = makeRandomBigInt(BigInt(minimum), BigInt(maximum))
587 return (state) => Number(random(state))
588}
589
590function makeRandomBigInt(minimum: bigint, maximum: bigint): (state: GenerationState) => bigint {
591 if (minimum === maximum) return () => minimum
592 const width = maximum - minimum + BigInt(1)
593 const bitLength = (width - BigInt(1)).toString(2).length
594 const leadingBits = (bitLength - 1) % 32 + 1
595 const leadingRange = 2 ** leadingBits
596 const randomLeading = makeRandomUint32Below(leadingRange)
597 return (state) => {
598 while (true) {
599 let value = BigInt(randomLeading(state))
600 for (let remaining = bitLength - leadingBits; remaining > 0; remaining -= 32) {
601 value = value << BigInt(32) | BigInt(state.random.nextUint32())
602 }
603 if (value < width) return minimum + value
604 }
605 }
606}
607
608interface NumberRange {
609 readonly minimum: number
610 readonly maximum: number
611}
612
613interface BigIntRange {
614 readonly minimum: bigint
615 readonly maximum: bigint
616}
617
618// The numeric edge ranges and their 2:1 preference for the edge closest to zero follow fast-check v4.9.0's
619// BiasNumericRange, IntegerArbitrary, and BigIntArbitrary (MIT). The policy stays private to the Arbitrary engine.
620// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/helpers/BiasNumericRange.ts
621// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/IntegerArbitrary.ts
622// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/BigIntArbitrary.ts
623function numberBiasRanges(minimum: number, maximum: number): ReadonlyArray<NumberRange> {
624 if (minimum === maximum) return [{ minimum, maximum }]
625 if (minimum < 0 && maximum > 0) {
626 const low = Math.floor(Math.log2(-minimum))
627 const high = Math.floor(Math.log2(maximum))
628 return [
629 { minimum: -low, maximum: high },
630 { minimum: maximum - high, maximum },
631 { minimum, maximum: minimum + low }
632 ]
633 }
634 const gap = Math.floor(Math.log2(maximum - minimum))
635 const closeToMinimum = { minimum, maximum: minimum + gap }
636 const closeToMaximum = { minimum: maximum - gap, maximum }
637 return minimum < 0 ? [closeToMaximum, closeToMinimum] : [closeToMinimum, closeToMaximum]
638}
639
640function bigIntLogLike(value: bigint): bigint {
641 return value === BigInt(0) ? BigInt(0) : BigInt(value.toString().length)
642}
643
644function bigIntBiasRanges(minimum: bigint, maximum: bigint): ReadonlyArray<BigIntRange> {
645 if (minimum === maximum) return [{ minimum, maximum }]
646 if (minimum < BigInt(0) && maximum > BigInt(0)) {
647 const low = bigIntLogLike(-minimum)
648 const high = bigIntLogLike(maximum)
649 return [
650 { minimum: -low, maximum: high },
651 { minimum: maximum - high, maximum },
652 { minimum, maximum: minimum + low }
653 ]
654 }
655 const gap = bigIntLogLike(maximum - minimum)
656 const closeToMinimum = { minimum, maximum: minimum + gap }
657 const closeToMaximum = { minimum: maximum - gap, maximum }
658 return minimum < BigInt(0) ? [closeToMaximum, closeToMinimum] : [closeToMinimum, closeToMaximum]
659}
660
661function selectBiased<A>(state: GenerationState, values: ReadonlyArray<A>): A {
662 if (values.length === 1) return values[0]
663 const index = randomInt(state, -2 * (values.length - 1), values.length - 2)
664 return index < 0 ? values[0] : values[index + 1]
665}
666
667/** @internal */
668export function makeRandomNumericInt(
669 minimum: number,
670 maximum: number
671): (state: GenerationState) => number {
672 const full = makeRandomInt(minimum, maximum)
673 const biased = numberBiasRanges(minimum, maximum).map((range) => makeRandomInt(range.minimum, range.maximum))
674 return (state) => {
675 const random = randomInt(state, 1, state.biasFactor) === 1 ? selectBiased(state, biased) : full
676 return random(state)
677 }
678}
679
680/** @internal */
681export function makeRandomNumericBigInt(
682 minimum: bigint,
683 maximum: bigint
684): (state: GenerationState) => bigint {
685 const full = makeRandomBigInt(minimum, maximum)
686 const biased = bigIntBiasRanges(minimum, maximum).map((range) => makeRandomBigInt(range.minimum, range.maximum))
687 return (state) => {
688 const random = randomInt(state, 1, state.biasFactor) === 1 ? selectBiased(state, biased) : full
689 return random(state)
690 }
691}
692
693// The monotone IEEE-754 index and adjacent-number navigation follow the model used by fast-check v4.9.0's
694// DoubleHelpers (MIT). This implementation uses a direct 64-bit bit cast instead of its exponent decomposition.
695// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/helpers/DoubleHelpers.ts
696const numberBuffer = new ArrayBuffer(8)
697const numberView = new DataView(numberBuffer)
698const numberSignMask = BigInt(1) << BigInt(63)
699const numberBitsMask = (BigInt(1) << BigInt(64)) - BigInt(1)
700
701/** @internal */
702export function numberToIndex(value: number): bigint {
703 numberView.setFloat64(0, value)
704 const bits = numberView.getBigUint64(0)
705 const unsigned = (bits & numberSignMask) === BigInt(0) ? bits | numberSignMask : ~bits & numberBitsMask
706 return unsigned - numberSignMask
707}
708
709/** @internal */
710export function indexToNumber(index: bigint): number {
711 const unsigned = index + numberSignMask
712 const bits = (unsigned & numberSignMask) === BigInt(0)
713 ? ~unsigned & numberBitsMask
714 : unsigned ^ numberSignMask
715 numberView.setBigUint64(0, bits)
716 return numberView.getFloat64(0)
717}
718
719/** @internal */
720export function nextNumber(value: number): number {
721 if (Number.isNaN(value) || value === Number.POSITIVE_INFINITY) return value
722 if (value === 0) return Number.MIN_VALUE
723 return indexToNumber(numberToIndex(value) + BigInt(1))
724}
725
726/** @internal */
727export function previousNumber(value: number): number {
728 if (Number.isNaN(value) || value === Number.NEGATIVE_INFINITY) return value
729 if (value === 0) return -Number.MIN_VALUE
730 return indexToNumber(numberToIndex(value) - BigInt(1))
731}
732
733/** @internal */
734export function makeRandomNumber(
735 minimum: number,
736 maximum: number,
737 allowNaN: boolean
738): (state: GenerationState) => number {
739 const minimumIndex = numberToIndex(minimum)
740 const maximumIndex = numberToIndex(maximum)
741 const nanBelow = allowNaN && maximumIndex <= BigInt(0)
742 const randomIndex = makeRandomNumericBigInt(
743 nanBelow ? minimumIndex - BigInt(1) : minimumIndex,
744 allowNaN && !nanBelow ? maximumIndex + BigInt(1) : maximumIndex
745 )
746 return (state) => {
747 const index = randomIndex(state)
748 return index < minimumIndex || index > maximumIndex ? Number.NaN : indexToNumber(index)
749 }
750}
751
752/** @internal */
753export const randomBoolean = (state: GenerationState): boolean => (state.random.nextUint32() & 1) === 1
754
755/** @internal */
756export function shuffle<A>(state: GenerationState, elements: Iterable<A>): Array<A> {
757 const buffer = Array.from(elements)
758 for (let index = buffer.length - 1; index >= 1; index--) {
759 const target = randomUint32Below(state, index + 1)
760 const value = buffer[index]!
761 buffer[index] = buffer[target]!
762 buffer[target] = value
763 }
764 return buffer
765}