1import * as Effect from "../../Effect.ts"
2import * as Model from "./model.ts"
3
4const bigint0 = BigInt(0)
5const bigint1 = BigInt(1)
6const bigint2 = BigInt(2)
7const ordinaryMaximumBits = 20
8const wideMaximumBits = 2_048
9
10const semanticMagnitudes = [
11 bigint1,
12 bigint2,
13 BigInt(0x7fff_ffff),
14 BigInt(0x8000_0000),
15 BigInt(Number.MAX_SAFE_INTEGER),
16 BigInt(Number.MAX_SAFE_INTEGER) + bigint1,
17 BigInt(Number.MAX_VALUE),
18 BigInt(Number.MAX_VALUE) + bigint1,
19 bigint1 << BigInt(1_024)
20] as const
21
22function isWithin(value: bigint, minimum: bigint | undefined, maximum: bigint | undefined): boolean {
23 return (minimum === undefined || value >= minimum) && (maximum === undefined || value <= maximum)
24}
25
26function bitLength(value: bigint): number {
27 return value === bigint0 ? 0 : (value < bigint0 ? -value : value).toString(2).length
28}
29
30function randomMagnitude(state: Model.GenerationState, maximum?: bigint): bigint {
31 if (maximum === bigint0) return bigint0
32 const family = Model.randomInt(state, 0, 7)
33 if (family === 0) return bigint0
34 const maximumBits = maximum === undefined ? wideMaximumBits : bitLength(maximum)
35 const bits = Model.randomInt(state, 1, family <= 3 ? Math.min(ordinaryMaximumBits, maximumBits) : maximumBits)
36 const minimum = bigint1 << BigInt(bits - 1)
37 const upper = (minimum << bigint1) - bigint1
38 return Model.randomBigInt(state, minimum, maximum !== undefined && maximum < upper ? maximum : upper)
39}
40
41function makeGenerator(
42 minimum: bigint | undefined,
43 maximum: bigint | undefined
44): (state: Model.GenerationState) => bigint {
45 if (minimum !== undefined && maximum !== undefined) return Model.makeRandomNumericBigInt(minimum, maximum)
46
47 const special = [
48 bigint0,
49 ...(minimum === undefined ? [] : [minimum, minimum + bigint1]),
50 ...(maximum === undefined ? [] : [maximum, maximum - bigint1]),
51 ...semanticMagnitudes.flatMap((value) => [value, -value])
52 ].filter((value) => isWithin(value, minimum, maximum))
53 const boundary = minimum ?? maximum
54 const direction = minimum === undefined ? -bigint1 : bigint1
55 const finiteMagnitude = boundary !== undefined && boundary * direction <= bigint0 ? -boundary * direction : undefined
56
57 return (state) => {
58 if (Model.randomInt(state, 0, 7) === 0) return special[Model.randomIndex(state, special.length)]
59 if (boundary !== undefined && (boundary * direction > bigint0 || Model.randomBoolean(state))) {
60 return boundary + direction * randomMagnitude(state)
61 }
62 const sign = Model.randomBoolean(state) ? bigint1 : -bigint1
63 return sign * randomMagnitude(state, sign === -direction ? finiteMagnitude : undefined)
64 }
65}
66
67function sample(value: bigint, target: bigint, context?: bigint): Model.Sample<bigint> {
68 return Model.makeSampleWithLazyShrinks(value, () => {
69 const from = context ?? target
70 const gap = value - from
71 if (gap === bigint0) return undefined
72 if (context !== undefined && (gap === bigint1 || gap === -bigint1)) {
73 return Model.pullFromArray([sample(context, target)])
74 }
75 const direction = gap > bigint0 ? bigint1 : -bigint1
76 const candidates = new Set<bigint>(context === undefined ? [target] : [])
77 // Both endpoints satisfy the bounds, so every candidate strictly between them does too.
78 const add = (candidate: bigint) => {
79 if ((candidate - from) * direction > bigint0 && (value - candidate) * direction > bigint0) {
80 candidates.add(candidate)
81 }
82 }
83 if (context === undefined) {
84 for (const magnitude of semanticMagnitudes) add(target + direction * magnitude)
85 const maximumBits = bitLength(gap)
86 for (let bits = 1; bits < maximumBits; bits *= 2) {
87 add(target + direction * ((bigint1 << BigInt(bits)) - bigint1))
88 }
89 } else {
90 const passingBits = bitLength(context)
91 const failingBits = bitLength(value)
92 if (
93 Math.abs(failingBits - passingBits) > 1 && (context === bigint0 || (context > bigint0) === (value > bigint0))
94 ) {
95 const bits = Math.floor((passingBits + failingBits) / 2)
96 add(direction * ((bigint1 << BigInt(bits)) - bigint1))
97 }
98 }
99 let toRemove = gap / bigint2
100 for (let step = 0; toRemove !== bigint0 && step < 256; step++, toRemove /= bigint2) {
101 add(value - toRemove)
102 }
103 candidates.add(value - direction)
104 const ordered = [...candidates].sort((a, b) => a < b ? -Number(direction) : a > b ? Number(direction) : 0)
105 let previous = context
106 return Effect.map(Model.pullFromArray(ordered), (candidate) => {
107 const child = sample(candidate, target, previous)
108 previous = candidate
109 return child
110 })
111 })
112}
113
114/** @internal */
115export function make(minimum: bigint | undefined, maximum: bigint | undefined): Model.Compiled<bigint> {
116 const generate = makeGenerator(minimum, maximum)
117 const target = minimum !== undefined && minimum > bigint0
118 ? minimum
119 : maximum !== undefined && maximum < bigint0
120 ? maximum
121 : bigint0
122 return Model.makeCompiled([], () => 0, (state) => {
123 const value = generate(state)
124 return state.shrinks ? sample(value, target) : Model.makeSample(value)
125 })
126}