1import * as BigDecimal from "../../BigDecimal.ts"
2import * as Effect from "../../Effect.ts"
3import { done } from "../core.ts"
4import * as Model from "./model.ts"
5
6const bigint0 = BigInt(0)
7const bigint1 = BigInt(1)
8const bigint10 = BigInt(10)
9const maximumGeneratedBits = 425
10const maximumExactPower = 4_096
11const shrinkExponents = [-512, -256, -128, -64, -32, -16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
12const compare = BigDecimal.Order
13
14/** @internal */
15export interface Bounds {
16 readonly minimum?: BigDecimal.BigDecimal | undefined
17 readonly exclusiveMinimum?: boolean | undefined
18 readonly maximum?: BigDecimal.BigDecimal | undefined
19 readonly exclusiveMaximum?: boolean | undefined
20}
21
22function isAllowed(value: BigDecimal.BigDecimal, bounds: Bounds): boolean {
23 if (bounds.minimum !== undefined) {
24 const comparison = compare(value, bounds.minimum)
25 if (comparison < 0 || comparison === 0 && bounds.exclusiveMinimum === true) return false
26 }
27 if (bounds.maximum !== undefined) {
28 const comparison = compare(value, bounds.maximum)
29 if (comparison > 0 || comparison === 0 && bounds.exclusiveMaximum === true) return false
30 }
31 return true
32}
33
34// All offsets are nonnegative; clamp before constructing a BigDecimal at the finer scale.
35function addScale(scale: number, offset: number, maximum = Number.MAX_SAFE_INTEGER): number {
36 return Math.min(maximum, scale + offset)
37}
38
39function boundaryCandidate(
40 value: BigDecimal.BigDecimal | undefined,
41 exclusive: boolean | undefined,
42 direction: -1 | 1
43): BigDecimal.BigDecimal | undefined {
44 if (value === undefined || exclusive !== true) return value
45 return value.scale < Number.MAX_SAFE_INTEGER
46 ? BigDecimal.make(value.value * bigint10 + BigInt(direction), value.scale + 1)
47 : BigDecimal.make(value.value + BigInt(direction), value.scale)
48}
49
50function digits(value: bigint): number {
51 return (value < bigint0 ? -value : value).toString().length
52}
53
54function roundAtScale(
55 value: BigDecimal.BigDecimal,
56 scale: number,
57 ceil: boolean,
58 maximumPower = maximumExactPower
59): bigint | undefined {
60 if (value.value === bigint0) return bigint0
61 const difference = BigInt(scale) - BigInt(value.scale)
62 if (difference >= bigint0) {
63 if (difference > BigInt(maximumPower)) return undefined
64 return value.value * bigint10 ** difference
65 }
66 const divisor = -difference >= BigInt(digits(value.value)) ? undefined : bigint10 ** -difference
67 const quotient = divisor === undefined ? bigint0 : value.value / divisor
68 const remainder = divisor === undefined ? value.value : value.value % divisor
69 return quotient + (ceil && remainder > bigint0 ? bigint1 : !ceil && remainder < bigint0 ? -bigint1 : bigint0)
70}
71
72type CoefficientRange = readonly [minimum: bigint | undefined, maximum: bigint | undefined]
73
74function coefficientRange(scale: number, bounds: Bounds): CoefficientRange | undefined {
75 const lower = bounds.minimum
76 const upper = bounds.maximum
77 let minimum = lower === undefined
78 ? undefined
79 : roundAtScale(lower, scale, bounds.exclusiveMinimum !== true)
80 let maximum = upper === undefined
81 ? undefined
82 : roundAtScale(upper, scale, bounds.exclusiveMaximum === true)
83 // A projected bound can already exceed the default precision budget. Resolve the
84 // other bound at that precision before treating its projection as out of reach.
85 if (lower !== undefined && minimum === undefined && maximum !== undefined) {
86 minimum = roundAtScale(
87 lower,
88 scale,
89 bounds.exclusiveMinimum !== true,
90 Math.max(maximumExactPower, digits(maximum))
91 )
92 }
93 if (upper !== undefined && maximum === undefined && minimum !== undefined) {
94 maximum = roundAtScale(
95 upper,
96 scale,
97 bounds.exclusiveMaximum === true,
98 Math.max(maximumExactPower, digits(minimum))
99 )
100 }
101 if (minimum === undefined && lower !== undefined && lower.value > bigint0) return undefined
102 if (maximum === undefined && upper !== undefined && upper.value < bigint0) return undefined
103 if (minimum !== undefined && bounds.exclusiveMinimum === true) minimum += bigint1
104 if (maximum !== undefined && bounds.exclusiveMaximum === true) maximum -= bigint1
105 return minimum !== undefined && maximum !== undefined && minimum > maximum
106 ? undefined
107 : [minimum, maximum]
108}
109
110function randomCoefficient(state: Model.GenerationState, range: CoefficientRange): bigint {
111 const [minimum, maximum] = range
112 if (minimum !== undefined && maximum !== undefined) {
113 return Model.randomBigInt(state, minimum, maximum)
114 }
115 const ordinary = Model.randomInt(state, 0, 3) !== 0
116 const bits = ordinary ? Model.randomInt(state, 0, 20) : Model.randomInt(state, 1, maximumGeneratedBits)
117 const lowest = bits === 0 ? bigint0 : bigint1 << BigInt(bits - 1)
118 const distance = bits === 0 ? bigint0 : Model.randomBigInt(state, lowest, (lowest << bigint1) - bigint1)
119 if (minimum !== undefined) return minimum + distance
120 if (maximum !== undefined) return maximum - distance
121 return Model.randomBoolean(state) ? distance : -distance
122}
123
124function randomScale(state: Model.GenerationState, boundaryScale: number | undefined): number {
125 const mode = Model.randomInt(state, 0, 7)
126 if (mode <= 5 && boundaryScale !== undefined) {
127 return addScale(boundaryScale, Model.randomInt(state, 0, mode === 5 ? 20 : 2))
128 }
129 if (mode === 6) return Model.randomInt(state, -6, 20)
130 const precision = Model.randomInt(state, 1, 128)
131 const exponent = Model.randomInt(state, -512, 512)
132 return precision - 1 - exponent
133}
134
135type ShrinkContext = readonly [passing: BigDecimal.BigDecimal, refinement: number]
136
137function projectExact(value: BigDecimal.BigDecimal, scale: number): bigint | undefined {
138 const difference = BigInt(scale) - BigInt(value.scale)
139 if (difference < bigint0 || difference > BigInt(maximumExactPower)) return undefined
140 return value.value * bigint10 ** difference
141}
142
143function midpoint(
144 passing: BigDecimal.BigDecimal,
145 failing: BigDecimal.BigDecimal,
146 maximumScale: number
147): BigDecimal.BigDecimal | undefined {
148 const scale = addScale(Math.max(passing.scale, failing.scale), 1, maximumScale)
149 const left = projectExact(passing, scale)
150 const right = projectExact(failing, scale)
151 if (left === undefined || right === undefined) return undefined
152 const value = left + (right - left) / BigInt(2)
153 return value === left || value === right ? undefined : BigDecimal.make(value, scale)
154}
155
156function sample(
157 value: BigDecimal.BigDecimal,
158 target: BigDecimal.BigDecimal,
159 context?: ShrinkContext,
160 maximumScale = addScale(Math.max(value.scale, target.scale), 128)
161): Model.Sample<BigDecimal.BigDecimal> {
162 return Model.makeSampleWithLazyShrinks(value, () => {
163 const from = context?.[0] ?? target
164 const direction = compare(value, from)
165 if (direction === 0) return undefined
166 let next: BigDecimal.BigDecimal | undefined
167 if (context !== undefined) {
168 const normalized = BigDecimal.normalize(context[0])
169 const scale = addScale(normalized.scale, Math.min(context[1] + 1, 128), maximumScale)
170 const projected = projectExact(normalized, scale)
171 if (projected !== undefined) next = BigDecimal.make(projected + BigInt(direction), scale)
172 }
173 // Simple candidates are already ordered toward the failing value. Strict
174 // inequalities preserve the bounds and exclude equivalent representations.
175 const candidates = (context === undefined
176 ? shrinkExponents.map((exponent) => BigDecimal.make(BigInt(direction), -exponent))
177 : [next]).filter((candidate): candidate is BigDecimal.BigDecimal =>
178 candidate !== undefined && candidate.scale <= maximumScale &&
179 compare(candidate, from) === direction && compare(candidate, value) === -direction
180 )
181 if (context === undefined) candidates.unshift(target)
182 let previous = context
183 let index = 0
184 return Effect.suspend(() => {
185 // If all simpler candidates pass, keep bisecting toward the failing value.
186 const candidate = index < candidates.length
187 ? candidates[index++]
188 : previous === undefined
189 ? undefined
190 : midpoint(previous[0], value, maximumScale)
191 if (candidate === undefined) return done()
192 const child = sample(candidate, target, previous, maximumScale)
193 previous = [candidate, (previous?.[1] ?? 0) + 1]
194 return Effect.succeed(child)
195 })
196 })
197}
198
199/** @internal */
200export function make(bounds: Bounds): Model.Compiled<BigDecimal.BigDecimal> | undefined {
201 if (bounds.minimum !== undefined && bounds.maximum !== undefined && compare(bounds.minimum, bounds.maximum) === 0) {
202 if (bounds.exclusiveMinimum === true || bounds.exclusiveMaximum === true) return undefined
203 const value = bounds.minimum
204 return Model.makeCompiled([], () => 0, () => Model.makeSample(value))
205 }
206 const zero = BigDecimal.make(bigint0, 0)
207 const lower = boundaryCandidate(bounds.minimum, bounds.exclusiveMinimum, 1)
208 const upper = boundaryCandidate(bounds.maximum, bounds.exclusiveMaximum, -1)
209 // The finer endpoint's inward step fits every nonempty interval. At the maximum
210 // scale there is no finer grid, so adjacent exclusive endpoints have no witness.
211 const witness = [zero, lower, upper].find((value) => value !== undefined && isAllowed(value, bounds))
212 if (witness === undefined) return undefined
213 const target = witness.value < bigint0 && upper !== undefined && isAllowed(upper, bounds) ? upper : witness
214
215 const special = [
216 witness,
217 BigDecimal.make(bigint1, 1),
218 BigDecimal.make(bigint1, 0),
219 BigDecimal.make(bigint10, 0),
220 BigDecimal.make(-bigint1, 1),
221 BigDecimal.make(-bigint1, 0),
222 BigDecimal.make(-bigint10, 0),
223 ...(bounds.minimum !== undefined && bounds.exclusiveMinimum !== true ? [bounds.minimum] : []),
224 ...(bounds.maximum !== undefined && bounds.exclusiveMaximum !== true ? [bounds.maximum] : [])
225 ].filter((value) => isAllowed(value, bounds))
226 const boundaryScale = lower === undefined
227 ? upper?.scale
228 : upper === undefined
229 ? lower.scale
230 : Math.max(lower.scale, upper.scale)
231 const preferred = boundaryScale === undefined ? undefined : coefficientRange(boundaryScale, bounds)
232 const generatePreferred = preferred?.[0] !== undefined && preferred[1] !== undefined
233 ? Model.makeRandomNumericBigInt(preferred[0], preferred[1])
234 : undefined
235
236 return Model.makeCompiled([], () => 0, (state) => {
237 let value: BigDecimal.BigDecimal
238 if (Model.randomInt(state, 0, 7) === 0) {
239 value = special[Model.randomIndex(state, special.length)]
240 } else if (generatePreferred !== undefined && Model.randomInt(state, 0, 3) !== 0) {
241 value = BigDecimal.make(generatePreferred(state), boundaryScale!)
242 } else {
243 value = witness
244 for (let attempt = 0; attempt < 16; attempt++) {
245 const scale = randomScale(state, boundaryScale)
246 const range = coefficientRange(scale, bounds)
247 if (range === undefined) continue
248 const coefficient = randomCoefficient(state, range)
249 if (Model.randomInt(state, 0, 7) === 0 && scale < Number.MAX_SAFE_INTEGER) {
250 const trailing = Model.randomInt(state, 1, Math.min(8, Number.MAX_SAFE_INTEGER - scale))
251 value = BigDecimal.make(coefficient * bigint10 ** BigInt(trailing), scale + trailing)
252 } else {
253 value = BigDecimal.make(coefficient, scale)
254 }
255 break
256 }
257 }
258 return state.shrinks ? sample(value, target) : Model.makeSample(value)
259 })
260}