1import * as BigDecimal from "../../BigDecimal.ts"
2import * as Effect from "../../Effect.ts"
3import * as Equal from "../../Equal.ts"
4import { identity } from "../../Function.ts"
5import * as Hash from "../../Hash.ts"
6import * as Option from "../../Option.ts"
7import * as Order from "../../Order.ts"
8import * as Predicate from "../../Predicate.ts"
9import * as Schema from "../../Schema.ts"
10import * as SchemaAST from "../../SchemaAST.ts"
11import * as SchemaGetter from "../../SchemaGetter.ts"
12import * as SchemaParser from "../../SchemaParser.ts"
13import * as InternalArray from "../array.ts"
14import { effectIsExit } from "../effect.ts"
15import { errorWithPath } from "../errors.ts"
16import * as InternalRecord from "../record.ts"
17import { sample as arraySample } from "./array.ts"
18import * as BigDecimalArbitrary from "./bigDecimal.ts"
19import * as BigIntArbitrary from "./bigInt.ts"
20import * as Model from "./model.ts"
21import * as Regexp from "./regexp.ts"
22
23type FilterConstraint = Schema.Annotations.ToArbitrary.FilterConstraint<any>
24type GenerationConstraint = Schema.Annotations.ToArbitrary.GenerationConstraint<any>
25
26interface Checks {
27 readonly constraint: FilterConstraint | undefined
28 readonly filters: ReadonlyArray<SchemaAST.Filter<any>>
29}
30
31const infinity = Number.POSITIVE_INFINITY
32const finiteNumberConstraint: FilterConstraint = { number: "finite" }
33const optionMatch = { onFailure: Option.none, onSuccess: Option.some }
34
35const optionComputation = <A, E, R>(self: Effect.Effect<A, E, R>): Model.Computation<Option.Option<A>> => {
36 const result = Effect.matchEager(self, optionMatch) as Effect.Effect<Option.Option<A>>
37 return effectIsExit(result) && result._tag === "Success" ? result.value : result
38}
39
40/** @internal */
41export function compileValidator<S extends Schema.Constraint>(
42 schema: S
43): (value: S["Type"]) => Model.Computation<Option.Option<S["Type"]>> {
44 const parse = SchemaParser.run<S["Type"], never>(SchemaAST.toType(schema.ast))
45 return (value) => optionComputation(parse(value))
46}
47
48function arbitraryError(what: string, path: ReadonlyArray<PropertyKey>) {
49 return errorWithPath(`Unable to derive an arbitrary for ${what}`, path)
50}
51
52function sumCosts(costs: Iterable<number>): number {
53 let out = 0
54 for (const cost of costs) {
55 if (cost === infinity) return infinity
56 out += cost
57 }
58 return out
59}
60
61function mergeOrderedBound<T>(
62 order: Order.Order<T>,
63 self: T | undefined,
64 selfExclusive: boolean | undefined,
65 that: T | undefined,
66 thatExclusive: boolean | undefined,
67 takeComparison: -1 | 1
68): readonly [T | undefined, boolean | undefined] {
69 if (that === undefined || self === undefined) {
70 return that === undefined ? [self, selfExclusive] : [that, thatExclusive]
71 }
72 const comparison = order(self, that)
73 return comparison === takeComparison
74 ? [that, thatExclusive]
75 : comparison === 0
76 ? [self, selfExclusive || thatExclusive]
77 : [self, selfExclusive]
78}
79
80function mergeMinimum(self: number | undefined, that: number | undefined): number | undefined {
81 return self === undefined ? that : that === undefined ? self : Math.max(self, that)
82}
83
84function mergeMaximum(self: number | undefined, that: number | undefined): number | undefined {
85 return self === undefined ? that : that === undefined ? self : Math.min(self, that)
86}
87
88function mergeConstraint(self: FilterConstraint | undefined, that: FilterConstraint): FilterConstraint {
89 const order = that.order ?? self?.order
90 if (self?.order !== undefined && that.order !== undefined && self.order !== that.order) {
91 throw new Error("Cannot merge ordered arbitrary constraints with different Order instances")
92 }
93 const [minimum, exclusiveMinimum] = order === undefined
94 ? [that.minimum ?? self?.minimum, that.exclusiveMinimum ?? self?.exclusiveMinimum]
95 : mergeOrderedBound(
96 order,
97 self?.minimum,
98 self?.exclusiveMinimum,
99 that.minimum,
100 that.exclusiveMinimum,
101 -1
102 )
103 const [maximum, exclusiveMaximum] = order === undefined
104 ? [that.maximum ?? self?.maximum, that.exclusiveMaximum ?? self?.exclusiveMaximum]
105 : mergeOrderedBound(
106 order,
107 self?.maximum,
108 self?.exclusiveMaximum,
109 that.maximum,
110 that.exclusiveMaximum,
111 1
112 )
113 const minLength = mergeMinimum(self?.minLength, that.minLength)
114 const maxLength = mergeMaximum(self?.maxLength, that.maxLength)
115 const minCodePoints = mergeMinimum(self?.minCodePoints, that.minCodePoints)
116 const maxCodePoints = mergeMaximum(self?.maxCodePoints, that.maxCodePoints)
117 const minSize = mergeMinimum(self?.minSize, that.minSize)
118 const maxSize = mergeMaximum(self?.maxSize, that.maxSize)
119 const minProperties = mergeMinimum(self?.minProperties, that.minProperties)
120 const maxProperties = mergeMaximum(self?.maxProperties, that.maxProperties)
121 const patterns = self?.patterns === undefined
122 ? that.patterns
123 : that.patterns === undefined
124 ? self.patterns
125 : [...self.patterns, ...that.patterns] as [
126 Schema.Annotations.ToArbitrary.Pattern,
127 ...Array<Schema.Annotations.ToArbitrary.Pattern>
128 ]
129 const number = self?.number === "integer" || that.number === "integer"
130 ? "integer"
131 : self?.number === "finite" || that.number === "finite"
132 ? "finite"
133 : undefined
134 const uniqueBy = that.uniqueBy ?? self?.uniqueBy
135 return {
136 ...(order === undefined ? undefined : { order }),
137 ...(minimum === undefined ? undefined : { minimum }),
138 ...(exclusiveMinimum === true ? { exclusiveMinimum: true } : undefined),
139 ...(maximum === undefined ? undefined : { maximum }),
140 ...(exclusiveMaximum === true ? { exclusiveMaximum: true } : undefined),
141 ...(minLength === undefined ? undefined : { minLength }),
142 ...(maxLength === undefined ? undefined : { maxLength }),
143 ...(minCodePoints === undefined ? undefined : { minCodePoints }),
144 ...(maxCodePoints === undefined ? undefined : { maxCodePoints }),
145 ...(minSize === undefined ? undefined : { minSize }),
146 ...(maxSize === undefined ? undefined : { maxSize }),
147 ...(minProperties === undefined ? undefined : { minProperties }),
148 ...(maxProperties === undefined ? undefined : { maxProperties }),
149 ...(patterns === undefined ? undefined : { patterns }),
150 ...(number === undefined ? undefined : { number }),
151 ...(uniqueBy === undefined ? undefined : { uniqueBy })
152 }
153}
154
155function collectChecks(checks: SchemaAST.Checks | undefined, inherited: FilterConstraint | undefined): Checks {
156 let constraint = inherited
157 const filters: Array<SchemaAST.Filter<any>> = []
158 const visit = (check: SchemaAST.Check<any>): void => {
159 const next = check.annotations?.arbitraryConstraint
160 if (next !== undefined) constraint = mergeConstraint(constraint, next)
161 if (check._tag === "Filter") {
162 filters.push(check)
163 } else {
164 check.checks.forEach(visit)
165 }
166 }
167 checks?.forEach(visit)
168 return { constraint, filters }
169}
170
171function applyFilters(
172 compiled: Model.Compiled<any>,
173 ast: SchemaAST.AST,
174 filters: ReadonlyArray<SchemaAST.Filter<any>>
175): void {
176 if (filters.length === 0) return
177 const generate = compiled.generate
178 const passes = (value: unknown) => {
179 for (let index = 0; index < filters.length; index++) {
180 if (filters[index].run(value, ast, SchemaAST.defaultParseOptions) !== undefined) return false
181 }
182 return true
183 }
184 compiled.generate = (state) =>
185 Model.mapGeneration(generate(state), (attempt) => {
186 if (attempt._tag === "Discarded") return Model.discarded
187 if (!state.shrinks) return passes(attempt.value) ? attempt : Model.discarded
188 const sample = Model.filterSample(attempt, passes)
189 return sample ?? Model.discarded
190 })
191}
192
193function validateConstraint(constraint: FilterConstraint | undefined, path: ReadonlyArray<PropertyKey>): void {
194 if (constraint === undefined) return
195 const cardinalities = [
196 [constraint.minLength, constraint.maxLength],
197 [constraint.minCodePoints, constraint.maxCodePoints],
198 [constraint.minSize, constraint.maxSize],
199 [constraint.minProperties, constraint.maxProperties]
200 ] as const
201 for (const [minimum, maximum] of cardinalities) {
202 if (
203 minimum !== undefined && (!Number.isSafeInteger(minimum) || minimum < 0) ||
204 maximum !== undefined && (!Number.isSafeInteger(maximum) || maximum < 0) ||
205 minimum !== undefined && maximum !== undefined && minimum > maximum
206 ) {
207 throw arbitraryError("constraints", path)
208 }
209 }
210 if (constraint.order !== undefined && constraint.minimum !== undefined && constraint.maximum !== undefined) {
211 const comparison = constraint.order(constraint.minimum, constraint.maximum)
212 if (
213 comparison > 0 ||
214 comparison === 0 && (constraint.exclusiveMinimum === true || constraint.exclusiveMaximum === true)
215 ) {
216 throw arbitraryError("constraints", path)
217 }
218 }
219}
220
221function withoutOrder(constraint: FilterConstraint | undefined): GenerationConstraint | undefined {
222 if (constraint === undefined) return undefined
223 const { order: _, ...out } = constraint
224 return Object.keys(out).length === 0 ? undefined : out
225}
226
227const minimumDateTimestamp = -8_640_000_000_000_000
228const maximumDateTimestamp = 8_640_000_000_000_000
229const regexpArbitraryFlags = ["g", "i", "m", "s", "u", "y"] as const
230
231function jsonSchema(): Schema.Codec<Schema.Json> {
232 let schema: Schema.Codec<Schema.Json>
233 schema = Schema.Union([
234 Schema.Null,
235 Schema.Finite,
236 Schema.Boolean,
237 Schema.String,
238 Schema.Array(Schema.suspend(() => schema)),
239 Schema.Record(Schema.String, Schema.suspend(() => schema))
240 ]) as Schema.Codec<Schema.Json>
241 return schema
242}
243
244function regexpSchema() {
245 return Schema.Struct({
246 source: Schema.Literals([
247 "",
248 ".",
249 ".*",
250 "\\d+",
251 "\\w+",
252 "[a-z]+",
253 "[A-Z]+",
254 "[0-9]+",
255 "^[a-zA-Z0-9]+$",
256 "^\\d{4}-\\d{2}-\\d{2}$"
257 ]),
258 flags: Schema.Struct({
259 g: Schema.Boolean,
260 i: Schema.Boolean,
261 m: Schema.Boolean,
262 s: Schema.Boolean,
263 u: Schema.Boolean,
264 y: Schema.Boolean
265 })
266 })
267}
268
269function urlSchema() {
270 return Schema.Struct({
271 protocol: Schema.Literals(["http", "https"]),
272 label: Schema.String.check(Schema.isPattern(/^[a-z0-9]+$/), Schema.isMinLength(1), Schema.isMaxLength(63)),
273 suffix: Schema.String.check(Schema.isPattern(/^[a-z]+$/), Schema.isMinLength(2), Schema.isMaxLength(10)),
274 path: Schema.Array(
275 Schema.String.check(Schema.isPattern(/^[A-Za-z0-9._~%-]*$/), Schema.isMaxLength(16))
276 ).check(Schema.isMaxLength(4))
277 })
278}
279
280function dateSchema(constraint: GenerationConstraint | undefined) {
281 const minimum = Math.max(
282 minimumDateTimestamp,
283 constraint?.minimum === undefined
284 ? minimumDateTimestamp
285 : constraint.minimum.getTime() + (constraint.exclusiveMinimum === true ? 1 : 0)
286 )
287 const maximum = Math.min(
288 maximumDateTimestamp,
289 constraint?.maximum === undefined
290 ? maximumDateTimestamp
291 : constraint.maximum.getTime() - (constraint.exclusiveMaximum === true ? 1 : 0)
292 )
293 return Schema.Int.check(Schema.isBetween({ minimum, maximum }))
294}
295
296const linkToArbitrary = Schema.linkDecoding
297
298function builtInDeclarationLink(
299 ast: SchemaAST.Declaration,
300 typeParameters: ReadonlyArray<Schema.Constraint>,
301 constraint: GenerationConstraint | undefined
302): SchemaAST.Link | undefined {
303 const representation = (ast.annotations as Schema.Annotations.Declaration<any> | undefined)?.representation
304 if (representation === undefined) return undefined
305 switch (representation.id) {
306 case "effect/schema/Json":
307 return linkToArbitrary<Schema.Json>()(jsonSchema(), SchemaGetter.passthrough())
308 case "effect/schema/MutableJson":
309 return linkToArbitrary<Schema.MutableJson>()(
310 jsonSchema(),
311 SchemaGetter.passthrough<Schema.MutableJson, Schema.Json>({ strict: false })
312 )
313 case "effect/schema/RegExp":
314 return linkToArbitrary<globalThis.RegExp>()(
315 regexpSchema(),
316 SchemaGetter.transform(({ flags, source }) =>
317 new globalThis.RegExp(source, regexpArbitraryFlags.filter((flag) => flags[flag]).join(""))
318 )
319 )
320 case "effect/schema/URL":
321 return linkToArbitrary<globalThis.URL>()(
322 urlSchema(),
323 SchemaGetter.transform(({ label, path, protocol, suffix }) =>
324 new globalThis.URL(`${protocol}://${label}.${suffix}/${path.join("/")}`)
325 )
326 )
327 case "effect/schema/Date":
328 return linkToArbitrary<globalThis.Date>()(dateSchema(constraint), SchemaGetter.Date<number>())
329 case "effect/schema/ReadonlyMap": {
330 const [key, value] = typeParameters
331 return linkToArbitrary<globalThis.ReadonlyMap<unknown, unknown>>()(
332 Schema.withArrayLengthConstraints(
333 Schema.Array(Schema.Tuple([key, value])).check(Schema.isUniqueKey()),
334 constraint?.minSize,
335 constraint?.maxSize
336 ),
337 SchemaGetter.transform((entries) => new globalThis.Map(entries))
338 )
339 }
340 case "effect/schema/ReadonlySet":
341 return linkToArbitrary<globalThis.ReadonlySet<unknown>>()(
342 Schema.withArrayLengthConstraints(
343 Schema.Array(typeParameters[0]).check(Schema.isUnique()),
344 constraint?.minSize,
345 constraint?.maxSize
346 ),
347 SchemaGetter.transform((values) => new globalThis.Set(values))
348 )
349 case "effect/schema/Uint8Array":
350 return linkToArbitrary<globalThis.Uint8Array<ArrayBufferLike>>()(
351 Schema.withArrayLengthConstraints(
352 Schema.Array(Schema.Int.check(Schema.isBetween({ minimum: 0, maximum: 255 }))),
353 constraint?.minLength,
354 constraint?.maxLength
355 ),
356 SchemaGetter.transform<globalThis.Uint8Array<ArrayBufferLike>, ReadonlyArray<number>>((values) =>
357 globalThis.Uint8Array.from(values)
358 )
359 )
360 default:
361 return undefined
362 }
363}
364
365function lengthBounds(
366 constraint: FilterConstraint | undefined,
367 keys: readonly [
368 minimum: "minLength" | "minCodePoints" | "minSize" | "minProperties",
369 maximum: "maxLength" | "maxCodePoints" | "maxSize" | "maxProperties"
370 ],
371 path: ReadonlyArray<PropertyKey>,
372 label: string
373): readonly [minimum: number, maximum: number | undefined] {
374 const minimum = constraint?.[keys[0]] ?? 0
375 const maximum = constraint?.[keys[1]]
376 if (
377 !Number.isSafeInteger(minimum) || minimum < 0 ||
378 maximum !== undefined && (!Number.isSafeInteger(maximum) || maximum < minimum)
379 ) {
380 throw arbitraryError(`${label} constraints`, path)
381 }
382 return [minimum, maximum]
383}
384
385function constant<A>(value: A): Model.Compiled<A> {
386 const sample = Model.makeSample(value)
387 return Model.makeCompiled([], () => 0, () => sample)
388}
389
390const uninhabited: Model.Compiled<never> = Model.makeCompiled([], () => infinity, () => Model.discarded)
391
392interface ObjectEntry {
393 readonly key: PropertyKey
394 readonly keySample?: Model.Sample<PropertyKey> | undefined
395 readonly sample: Model.Sample<any>
396 readonly removable: boolean
397}
398
399interface RetainedObjectEntry extends Omit<ObjectEntry, "sample" | "keySample"> {
400 readonly sample: Model.Retained<any>
401 readonly keySample?: Model.Retained<PropertyKey> | undefined
402}
403
404function normalizePropertyKeySample(sample: Model.Sample<any>): Model.Sample<PropertyKey> | undefined {
405 const filtered = Model.filterSample(sample, Predicate.isPropertyKey)
406 return filtered === undefined
407 ? undefined
408 : Model.mapSample(filtered, (value) => typeof value === "symbol" ? value : globalThis.String(value))
409}
410
411function objectSample(
412 entries: ReadonlyArray<ObjectEntry>,
413 minimum: number,
414 nullPrototype: boolean,
415 reservedKeys: ReadonlySet<PropertyKey>,
416 shrinks = true
417): Model.Sample<Record<PropertyKey, any>> {
418 const make = (entries: ReadonlyArray<ObjectEntry | RetainedObjectEntry>) => {
419 const out = Model.makeObject(nullPrototype)
420 for (const entry of entries) InternalRecord.assignProperty(out, entry.key, entry.sample.value)
421 return out
422 }
423 if (!shrinks) return Model.makeSample(make(entries))
424 const rebuild = (
425 entries: ReadonlyArray<RetainedObjectEntry>,
426 valueStart = 0,
427 keyStart = 0
428 ): Model.Sample<Record<PropertyKey, any>> => {
429 const pulls: Array<Model.ShrinkPull<Model.Attempt<Record<PropertyKey, any>>>> = []
430 if (entries.length > minimum) {
431 const structural = entries.flatMap((entry, index) =>
432 entry.removable
433 ? [() => rebuild(entries.slice(0, index).concat(entries.slice(index + 1)))]
434 : []
435 )
436 if (structural.length > 0) pulls.push(Effect.map(Model.pullFromArray(structural), (make) => make()))
437 }
438 for (let index = valueStart; index < entries.length; index++) {
439 const entry = entries[index]
440 if (entry.sample.shrinks === undefined) continue
441 pulls.push(Effect.map(
442 entry.sample.shrinks(),
443 (attempt) =>
444 attempt._tag === "Discarded"
445 ? attempt
446 : rebuild(InternalArray.replaceAt(entries, index, { ...entry, sample: attempt }), index)
447 ))
448 }
449 // Key shrinking uses the same uniqueness-preserving descendant filtering principle as fast-check v4.9.0's
450 // ArrayArbitrary (MIT). Structural removals and value shrinks retain their established precedence.
451 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/ArrayArbitrary.ts
452 for (let index = keyStart; index < entries.length; index++) {
453 const entry = entries[index]
454 if (entry.keySample === undefined || entry.keySample.shrinks === undefined) continue
455 const filtered = Model.filterSample(
456 Model.fromRetained(entry.keySample),
457 (key) =>
458 !reservedKeys.has(key) &&
459 !entries.some((other, otherIndex) => otherIndex !== index && other.key === key)
460 )
461 if (filtered?.shrinks === undefined) continue
462 pulls.push(Effect.map(
463 filtered.shrinks,
464 (attempt) =>
465 attempt._tag === "Discarded"
466 ? attempt
467 : rebuild(
468 InternalArray.replaceAt(entries, index, {
469 ...entry,
470 key: attempt.value,
471 keySample: Model.retain(attempt)
472 }),
473 entries.length,
474 index
475 )
476 ))
477 }
478 return Model.makeSample(make(entries), pulls.length === 0 ? undefined : Model.concatPulls(pulls))
479 }
480 return Model.makeSampleWithLazyShrinks(
481 make(entries),
482 () =>
483 rebuild(entries.map((entry) => ({
484 ...entry,
485 sample: Model.retain(entry.sample),
486 keySample: entry.keySample === undefined ? undefined : Model.retain(entry.keySample)
487 }))).shrinks
488 )
489}
490
491const generateSamples = (
492 children: ReadonlyArray<Model.Compiled<any>>,
493 state: Model.GenerationState,
494 additionalReserved = 0
495): Model.Computation<Array<Model.Sample<any>> | undefined> => {
496 let reserved = additionalReserved
497 let recursive: Array<number> | undefined
498 for (let index = 0; index < children.length; index++) {
499 const child = children[index]
500 if (reserved !== infinity) reserved += child.minCost
501 if (child.mayRecurse) (recursive ??= []).push(index)
502 }
503 if (reserved > state.budget.remaining) return undefined
504 let order: Array<number> | undefined
505 if (recursive !== undefined && recursive.length > 1) {
506 order = children.map((_, index) => index)
507 const shuffled = Model.shuffle(state, recursive)
508 let next = 0
509 for (let index = 0; index < order.length; index++) {
510 if (children[index].mayRecurse) order[index] = shuffled[next++]
511 }
512 }
513 return Model.generateProduct(children, state, order, reserved)
514}
515
516const generateRequiredObjectValues = (
517 properties: ReadonlyArray<{
518 readonly property: { readonly name: PropertyKey }
519 readonly compiled: Model.Compiled<any>
520 }>,
521 state: Model.GenerationState,
522 nullPrototype: boolean
523): Model.Generation<Record<PropertyKey, any>> => {
524 let reserved = 0
525 let recursive: Array<number> | undefined
526 for (let index = 0; index < properties.length; index++) {
527 const child = properties[index].compiled
528 if (reserved !== infinity) reserved += child.minCost
529 if (child.mayRecurse) (recursive ??= []).push(index)
530 }
531 if (reserved > state.budget.remaining) return Model.discarded
532 let order: Array<number> | undefined
533 if (recursive !== undefined && recursive.length > 1) {
534 order = properties.map((_, index) => index)
535 const shuffled = Model.shuffle(state, recursive)
536 let next = 0
537 for (let index = 0; index < order.length; index++) {
538 if (properties[index].compiled.mayRecurse) order[index] = shuffled[next++]
539 }
540 }
541 const values = new Array<any>(properties.length)
542 let index = 0
543 const loop = (): Model.Generation<Record<PropertyKey, any>> => {
544 while (index < properties.length) {
545 const childIndex = order?.[index] ?? index
546 index++
547 const child = properties[childIndex]
548 reserved -= child.compiled.minCost
549 const generated = Model.generateWithReservedBudget(child.compiled, state, reserved)
550 if (Model.isAttempt(generated)) {
551 if (generated._tag === "Discarded") return Model.discarded
552 values[childIndex] = generated.value
553 continue
554 }
555 return Effect.flatMapEager(generated, (attempt) => {
556 if (attempt._tag === "Discarded") return Effect.succeed(Model.discarded)
557 values[childIndex] = attempt.value
558 return Model.toEffectGeneration(loop())
559 })
560 }
561 const out = Model.makeObject(nullPrototype)
562 for (let index = 0; index < properties.length; index++) {
563 InternalRecord.assignProperty(out, properties[index].property.name, values[index])
564 }
565 return Model.makeSample(out)
566 }
567 return loop()
568}
569
570const generateRepeatedValues = (
571 child: Model.Compiled<any>,
572 count: number,
573 state: Model.GenerationState
574): Model.Generation<ReadonlyArray<any>> => {
575 // The packed push loop follows fast-check v4.9.0's ArrayArbitrary generation strategy (MIT).
576 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/ArrayArbitrary.ts
577 const out: Array<any> = []
578 let remaining = count
579 let reserved = count * child.minCost
580 const loop = (): Model.Generation<ReadonlyArray<any>> => {
581 while (remaining > 0) {
582 reserved -= child.minCost
583 const generated = Model.generateWithReservedBudget(child, state, reserved)
584 if (Model.isAttempt(generated)) {
585 if (generated._tag === "Discarded") return Model.discarded
586 out.push(generated.value)
587 remaining--
588 continue
589 }
590 return Effect.flatMapEager(generated, (attempt) => {
591 if (attempt._tag === "Discarded") return Effect.succeed(Model.discarded)
592 out.push(attempt.value)
593 remaining--
594 return Model.toEffectGeneration(loop())
595 })
596 }
597 return Model.makeSample(out)
598 }
599 return loop()
600}
601
602const generateRepeatedRecursiveValues = (
603 child: Model.Compiled<any>,
604 count: number,
605 state: Model.GenerationState
606): Model.Generation<ReadonlyArray<any>> => {
607 const out = new Array<any>(count)
608 const order = Model.shuffle(state, Array.from({ length: count }, (_, index) => index))
609 let index = 0
610 let reserved = count * child.minCost
611 const loop = (): Model.Generation<ReadonlyArray<any>> => {
612 while (index < count) {
613 reserved -= child.minCost
614 const generated = Model.generateWithReservedBudget(child, state, reserved)
615 if (Model.isAttempt(generated)) {
616 if (generated._tag === "Discarded") return Model.discarded
617 out[order[index++]] = generated.value
618 continue
619 }
620 return Effect.flatMapEager(generated, (attempt) => {
621 if (attempt._tag === "Discarded") return Effect.succeed(Model.discarded)
622 out[order[index++]] = attempt.value
623 return Model.toEffectGeneration(loop())
624 })
625 }
626 return Model.makeSample(out)
627 }
628 return loop()
629}
630
631// Selector-based uniqueness and primitive Set tracking follow fast-check v4.9.0's uniqueArray and SameValueSet
632// strategies (MIT). Hash buckets extend them with Effect's equality semantics for objects.
633// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/uniqueArray.ts
634// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/helpers/SameValueSet.ts
635const makeUniqueAdder = (): (value: any) => boolean => {
636 let primitives: Set<any> | undefined
637 let buckets: Map<number, Array<any>> | undefined
638 return (value) => {
639 if (value === null || typeof value !== "object" && typeof value !== "function") {
640 const set = primitives ??= new Set()
641 const size = set.size
642 set.add(value)
643 return set.size !== size
644 }
645 const hash = Hash.hash(value)
646 const map = buckets ??= new Map()
647 const bucket = map.get(hash)
648 if (bucket !== undefined) {
649 for (let index = 0; index < bucket.length; index++) {
650 if (Equal.equals(bucket[index], value)) return false
651 }
652 bucket.push(value)
653 } else {
654 map.set(hash, [value])
655 }
656 return true
657 }
658}
659
660const makeUniqueAdderBy = (
661 uniqueBy: (value: any) => unknown
662): (value: any) => boolean => {
663 const add = makeUniqueAdder()
664 return uniqueBy === identity ? add : (input) => add(uniqueBy(input))
665}
666
667const generateRepeatedUniqueValues = (
668 child: Model.Compiled<any>,
669 count: number,
670 state: Model.GenerationState,
671 uniqueBy: (value: any) => unknown
672): Model.Generation<ReadonlyArray<any>> => {
673 const out: Array<any> = []
674 const addUnique = makeUniqueAdderBy(uniqueBy)
675 let remaining = count
676 let reserved = count * child.minCost
677 let retries = 0
678 let budget = state.budget.remaining
679 const loop = (): Model.Generation<ReadonlyArray<any>> => {
680 while (remaining > 0) {
681 if (retries === 0) {
682 reserved -= child.minCost
683 budget = state.budget.remaining
684 }
685 const generated = Model.generateWithReservedBudget(child, state, reserved)
686 if (Model.isAttempt(generated)) {
687 if (generated._tag === "Discarded") return Model.discarded
688 if (!addUnique(generated.value)) {
689 if (++retries >= count) return Model.discarded
690 state.budget.remaining = budget
691 continue
692 }
693 out.push(generated.value)
694 remaining--
695 retries = 0
696 continue
697 }
698 return Effect.flatMapEager(generated, (attempt) => {
699 if (attempt._tag === "Discarded") return Effect.succeed(Model.discarded)
700 if (!addUnique(attempt.value)) {
701 if (++retries >= count) return Effect.succeed(Model.discarded)
702 state.budget.remaining = budget
703 } else {
704 out.push(attempt.value)
705 remaining--
706 retries = 0
707 }
708 return Model.toEffectGeneration(loop())
709 })
710 }
711 return Model.makeSample(out)
712 }
713 return loop()
714}
715
716function shrinkString(value: string, minimum: number): ReadonlyArray<string> {
717 const values = value.length <= minimum
718 ? []
719 : [
720 value.slice(0, minimum),
721 value.slice(0, Math.max(minimum, Math.floor(value.length / 2))),
722 value.slice(0, -1)
723 ]
724 // fast-check v4.9.0 builds strings from shrinkable units (MIT). Effect keeps UTF-16 code units as its string domain
725 // and applies its integer-halving shrink toward the Effect-owned null-unit target.
726 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/string.ts
727 for (let index = 0; index < value.length; index++) {
728 for (const candidate of shrinkInteger(value.charCodeAt(index), 0, true)) {
729 values.push(
730 value.slice(0, index) + globalThis.String.fromCharCode(candidate.value) + value.slice(index + 1)
731 )
732 }
733 }
734 return [...new Set(values)].filter((candidate) => candidate !== value)
735}
736
737// Edge-case injection is inspired by fast-check v4.9.0's cached dangerous slices (MIT). The concrete corpus is
738// Effect-owned and also covers control, numeric-property, and UTF-16 boundaries.
739// https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/helpers/SlicesForStringBuilder.ts
740const stringEdgeCases = [
741 "",
742 " ",
743 "\t",
744 "\n",
745 "\0",
746 "0",
747 "-1",
748 "4294967295",
749 "__proto__",
750 "constructor",
751 "prototype",
752 "toString",
753 "\uD800",
754 "\uDC00",
755 "😀"
756] as const
757
758function randomString(state: Model.GenerationState, minimum: number, maximum: number): string {
759 if (Model.randomInt(state, 1, state.biasFactor) === 1) {
760 let eligible = 0
761 for (const value of stringEdgeCases) {
762 if (value.length >= minimum && value.length <= maximum) eligible++
763 }
764 if (eligible > 0) {
765 let target = Model.randomIndex(state, eligible)
766 for (const value of stringEdgeCases) {
767 if (value.length < minimum || value.length > maximum) continue
768 if (target-- === 0) return value
769 }
770 }
771 }
772 const length = Model.randomLength(state, minimum, maximum)
773 let value = ""
774 for (let index = 0; index < length; index++) {
775 value += globalThis.String.fromCharCode(Model.randomInt(state, 32, 126))
776 }
777 return value
778}
779
780function randomCodePointString(
781 state: Model.GenerationState,
782 minimum: number,
783 maximum: number,
784 minCodePoints: number,
785 maxCodePoints: number
786): string {
787 const count = Model.randomLength(state, minCodePoints, maxCodePoints)
788 const length = Model.randomLength(state, Math.max(minimum, count), Math.min(maximum, count * 2))
789 let pairs = length - count
790 let value = ""
791 for (let remaining = count; remaining > 0; remaining--) {
792 if (Model.randomInt(state, 1, remaining) <= pairs) {
793 value += globalThis.String.fromCodePoint(Model.randomInt(state, 0x10000, 0x10ffff))
794 pairs--
795 } else {
796 value += globalThis.String.fromCharCode(Model.randomInt(state, 32, 126))
797 }
798 }
799 return value
800}
801
802function numberBounds(constraint: FilterConstraint | undefined, integer: boolean, path: ReadonlyArray<PropertyKey>) {
803 const ordered = constraint?.order === Order.Number ? constraint : undefined
804 let minimum = ordered?.minimum as number | undefined
805 let maximum = ordered?.maximum as number | undefined
806 if (minimum !== undefined && Number.isNaN(minimum) || maximum !== undefined && Number.isNaN(maximum)) {
807 throw arbitraryError(integer ? "integer constraints" : "number constraints", path)
808 }
809 if (integer) {
810 if (minimum !== undefined) {
811 minimum = ordered?.exclusiveMinimum === true
812 ? Math.floor(minimum) + 1
813 : Math.ceil(minimum)
814 }
815 if (maximum !== undefined) {
816 maximum = ordered?.exclusiveMaximum === true
817 ? Math.ceil(maximum) - 1
818 : Math.floor(maximum)
819 }
820 } else {
821 if (minimum !== undefined && ordered?.exclusiveMinimum === true && minimum === Infinity) {
822 throw arbitraryError("number constraints", path)
823 }
824 if (maximum !== undefined && ordered?.exclusiveMaximum === true && maximum === -Infinity) {
825 throw arbitraryError("number constraints", path)
826 }
827 if (minimum !== undefined) {
828 minimum = ordered?.exclusiveMinimum === true ? Model.nextNumber(minimum) : minimum === 0 ? -0 : minimum
829 }
830 if (maximum !== undefined) {
831 maximum = ordered?.exclusiveMaximum === true ? Model.previousNumber(maximum) : maximum === 0 ? 0 : maximum
832 }
833 }
834 if (integer || constraint?.number === "finite") {
835 if (minimum === Infinity || maximum === -Infinity) {
836 throw arbitraryError(integer ? "integer constraints" : "number constraints", path)
837 }
838 if (minimum === -Infinity) minimum = integer ? Number.MIN_SAFE_INTEGER : -Number.MAX_VALUE
839 if (maximum === Infinity) maximum = integer ? Number.MAX_SAFE_INTEGER : Number.MAX_VALUE
840 }
841 if (integer) {
842 if (
843 minimum !== undefined && minimum > Number.MAX_SAFE_INTEGER ||
844 maximum !== undefined && maximum < Number.MIN_SAFE_INTEGER
845 ) {
846 throw arbitraryError("integer constraints", path)
847 }
848 if (minimum !== undefined) minimum = Math.max(minimum, Number.MIN_SAFE_INTEGER)
849 if (maximum !== undefined) maximum = Math.min(maximum, Number.MAX_SAFE_INTEGER)
850 }
851 if (
852 minimum !== undefined && maximum !== undefined &&
853 (integer ? minimum > maximum : Model.numberToIndex(minimum) > Model.numberToIndex(maximum))
854 ) {
855 throw arbitraryError(integer ? "integer constraints" : "number constraints", path)
856 }
857 return { minimum, maximum }
858}
859
860interface NumberShrink {
861 readonly value: number
862 readonly context: number | undefined
863}
864
865function shrinkInteger(current: number, target: number, tryTargetAsap: boolean): ReadonlyArray<NumberShrink> {
866 const out: Array<NumberShrink> = []
867 const realGap = current - target
868 let previous = tryTargetAsap ? undefined : target
869 for (
870 let toRemove = tryTargetAsap ? realGap : Math.trunc(realGap / 2);
871 toRemove !== 0;
872 toRemove = Math.trunc(toRemove / 2)
873 ) {
874 const value = toRemove === realGap ? target : current - toRemove
875 out.push({ value, context: previous })
876 previous = value
877 }
878 return out
879}
880
881function shrinkNumber(current: number, target: number, tryTargetAsap: boolean): ReadonlyArray<NumberShrink> {
882 if (Number.isNaN(current)) return [{ value: target, context: undefined }]
883 const currentIndex = Model.numberToIndex(current)
884 const targetIndex = Model.numberToIndex(target)
885 const realGap = currentIndex - targetIndex
886 let previous = tryTargetAsap ? undefined : target
887 const out: Array<NumberShrink> = []
888 for (
889 let toRemove = tryTargetAsap ? realGap : realGap / BigInt(2);
890 toRemove !== BigInt(0);
891 toRemove /= BigInt(2)
892 ) {
893 const value = toRemove === realGap ? target : Model.indexToNumber(currentIndex - toRemove)
894 out.push({ value, context: previous })
895 previous = value
896 }
897 return out
898}
899
900function numberTarget(minimum: number | undefined, maximum: number | undefined): number {
901 if (minimum !== undefined && minimum > 0) return minimum
902 if (maximum !== undefined && maximum < 0) return maximum
903 return 0
904}
905
906function numberSample(
907 value: number,
908 minimum: number | undefined,
909 maximum: number | undefined,
910 integer: boolean,
911 context?: number
912): Model.Sample<number> {
913 if (!integer) {
914 // fast-check v4.9.0's double arbitrary shrinks the monotone IEEE-754 index through its BigInt arbitrary (MIT).
915 // The sample keeps the equivalent last-passing index context without exposing either representation.
916 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/double.ts
917 let candidates: ReadonlyArray<NumberShrink>
918 const target = numberTarget(minimum, maximum)
919 if (context === undefined) {
920 candidates = shrinkNumber(value, target, true)
921 } else if (
922 !Number.isNaN(value) &&
923 (Model.numberToIndex(value) === Model.numberToIndex(context) + BigInt(1) ||
924 Model.numberToIndex(value) === Model.numberToIndex(context) - BigInt(1))
925 ) {
926 candidates = [{ value: context, context: undefined }]
927 } else {
928 candidates = shrinkNumber(value, context, false)
929 }
930 return Model.makeSample(
931 value,
932 candidates.length === 0
933 ? undefined
934 : Effect.map(
935 Model.pullFromArray(candidates),
936 (candidate) => numberSample(candidate.value, minimum, maximum, false, candidate.context)
937 )
938 )
939 }
940 // The passing-value context and halving sequence are adapted from fast-check v4.9.0's IntegerArbitrary and
941 // ShrinkInteger (MIT). Retaining the closest passing candidate lets the runner converge on a local failure boundary.
942 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/IntegerArbitrary.ts
943 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/helpers/ShrinkInteger.ts
944 let candidates: ReadonlyArray<NumberShrink>
945 if (context === undefined) {
946 const target = Math.min(maximum ?? 0, Math.max(minimum ?? 0, 0))
947 candidates = shrinkInteger(value, target, true)
948 } else if (
949 value > 0 && value === context + 1 && (minimum === undefined || value > minimum) ||
950 value < 0 && value === context - 1 && (maximum === undefined || value < maximum)
951 ) {
952 candidates = [{ value: context, context: undefined }]
953 } else {
954 candidates = shrinkInteger(value, context, false)
955 }
956 return Model.makeSample(
957 value,
958 candidates.length === 0
959 ? undefined
960 : Effect.map(
961 Model.pullFromArray(candidates),
962 (candidate) => numberSample(candidate.value, minimum, maximum, true, candidate.context)
963 )
964 )
965}
966
967/** @internal */
968export function compile<S extends Schema.Constraint>(schema: S): Model.Compiled<S["Type"]> {
969 const rootAst = SchemaAST.toType(schema.ast)
970 const cache = new WeakMap<SchemaAST.AST, Map<FilterConstraint | undefined, Model.Compiled<any>>>()
971 const nodes: Array<Model.Compiled<any>> = []
972 const suspendBodies = new Map<Model.Compiled<any>, Model.Compiled<any>>()
973 const pending: Array<() => void> = []
974 const recur = (
975 ast: SchemaAST.AST,
976 path: ReadonlyArray<PropertyKey>,
977 inherited?: FilterConstraint
978 ): Model.Compiled<any> => {
979 let entries = cache.get(ast)
980 const cached = entries?.get(inherited)
981 if (cached !== undefined) return cached
982 if (entries === undefined) {
983 entries = new Map()
984 cache.set(ast, entries)
985 }
986 const placeholder = Model.makeCompiled<any>([], () => infinity, () => Model.discarded)
987 entries.set(inherited, placeholder)
988 nodes.push(placeholder)
989 pending.push(() => {
990 const checks = collectChecks(ast.checks, inherited)
991 const baseAst = ast.checks === undefined ? ast : SchemaAST.replaceChecks(ast, undefined)
992 const base = compileBase(baseAst, path, checks.constraint)
993 if (baseAst._tag === "Suspend") {
994 const body = base.dependencies[0]
995 placeholder.dependencies = [body]
996 placeholder.computeMinCost = () => {
997 if (body.minCost === infinity) return infinity
998 return body.minCost + (placeholder.recursive ? 1 : 0)
999 }
1000 placeholder.generate = (state) =>
1001 Effect.suspend(() => {
1002 if (placeholder.recursive) {
1003 if (state.budget.remaining <= 0) return Effect.succeed(Model.discarded)
1004 state.budget.remaining--
1005 }
1006 return Model.toEffectGeneration(body.generate(state))
1007 })
1008 suspendBodies.set(placeholder, body)
1009 } else {
1010 placeholder.dependencies = base.dependencies
1011 placeholder.computeMinCost = base.computeMinCost
1012 placeholder.generate = base.generate
1013 }
1014 applyFilters(placeholder, ast, checks.filters)
1015 })
1016 return placeholder
1017 }
1018
1019 const compileBase = (
1020 ast: SchemaAST.AST,
1021 path: ReadonlyArray<PropertyKey>,
1022 constraint: FilterConstraint | undefined
1023 ): Model.Compiled<any> => {
1024 switch (ast._tag) {
1025 case "Never":
1026 return uninhabited
1027 case "Null":
1028 return constant(null)
1029 case "Undefined":
1030 case "Void":
1031 return constant(undefined)
1032 case "Literal":
1033 return constant(ast.literal)
1034 case "UniqueSymbol":
1035 return constant(ast.symbol)
1036 case "Boolean":
1037 return Model.makeCompiled(
1038 [],
1039 () => 0,
1040 (state) => {
1041 const value = Model.randomBoolean(state)
1042 return Model.makeSample(
1043 value,
1044 state.shrinks && value ? Model.pullFromArray([Model.makeSample(false)]) : undefined
1045 )
1046 }
1047 )
1048 case "String": {
1049 const patterns: Array<Regexp.Compiled> = []
1050 for (const candidate of constraint?.patterns ?? []) {
1051 const pattern = Regexp.compile(candidate)
1052 if (pattern !== undefined) patterns.push(pattern)
1053 }
1054 let [minimum, maximum = infinity] = lengthBounds(constraint, ["minLength", "maxLength"], path, "string")
1055 const hasCodePoints = constraint?.minCodePoints !== undefined || constraint?.maxCodePoints !== undefined
1056 let [minCodePoints, maxCodePoints = infinity] = lengthBounds(
1057 constraint,
1058 ["minCodePoints", "maxCodePoints"],
1059 path,
1060 "string code point"
1061 )
1062 if (hasCodePoints) {
1063 minimum = Math.max(minimum, minCodePoints)
1064 maximum = Math.min(maximum, maxCodePoints * 2)
1065 minCodePoints = Math.max(minCodePoints, Math.ceil(minimum / 2))
1066 maxCodePoints = Math.min(maxCodePoints, maximum)
1067 if (minimum > maximum || minCodePoints > maxCodePoints) {
1068 throw arbitraryError("string constraints", path)
1069 }
1070 }
1071 return Model.makeCompiled(
1072 [],
1073 () => 0,
1074 (state) => {
1075 const pattern = patterns.length === 0
1076 ? undefined
1077 : patterns.length === 1
1078 ? patterns[0]
1079 : patterns[Model.randomIndex(state, patterns.length)]
1080 let currentMaximum = Math.max(minimum, pattern?.minimumLength ?? 0, state.size)
1081 if (hasCodePoints && pattern !== undefined) {
1082 // A longer UTF-16 alternative can use fewer code points than the shortest match.
1083 currentMaximum *= 2
1084 }
1085 const upper = Math.min(maximum, currentMaximum)
1086 const value = pattern !== undefined
1087 ? pattern.generate(state, minimum, upper)
1088 : hasCodePoints
1089 ? randomCodePointString(state, minimum, upper, minCodePoints, Math.min(maxCodePoints, upper))
1090 : randomString(state, minimum, upper)
1091 if (value === undefined) return Model.discarded
1092 return state.shrinks
1093 ? Model.sampleFromShrink(
1094 value,
1095 pattern === undefined
1096 ? (value) => shrinkString(value, minimum)
1097 : (value) => pattern.shrink(value, minimum)
1098 )
1099 : Model.makeSample(value)
1100 }
1101 )
1102 }
1103 case "Number": {
1104 const integer = constraint?.number === "integer"
1105 const bounds = numberBounds(constraint, integer, path)
1106 const numberMinimum = bounds.minimum ?? (constraint?.number !== undefined
1107 ? -Number.MAX_VALUE
1108 : Number.NEGATIVE_INFINITY)
1109 const numberMaximum = bounds.maximum ?? (constraint?.number !== undefined
1110 ? Number.MAX_VALUE
1111 : Number.POSITIVE_INFINITY)
1112 const randomNumber = integer
1113 ? undefined
1114 : Model.makeRandomNumber(
1115 numberMinimum,
1116 numberMaximum,
1117 constraint?.number === undefined && bounds.minimum === undefined
1118 )
1119 let integerMinimum: number | undefined
1120 let integerMaximum: number | undefined
1121 let randomInteger: ((state: Model.GenerationState) => number) | undefined
1122 return Model.makeCompiled(
1123 [],
1124 () => 0,
1125 (state) => {
1126 let minimum = numberMinimum
1127 let maximum = numberMaximum
1128 if (integer) {
1129 const magnitude = Math.max(1, state.size * state.size)
1130 const center = bounds.minimum !== undefined && bounds.minimum > 0
1131 ? bounds.minimum
1132 : bounds.maximum !== undefined && bounds.maximum < 0
1133 ? bounds.maximum
1134 : 0
1135 minimum = bounds.minimum ?? center - magnitude
1136 maximum = bounds.maximum ?? center + magnitude
1137 if (randomInteger === undefined || minimum !== integerMinimum || maximum !== integerMaximum) {
1138 integerMinimum = minimum
1139 integerMaximum = maximum
1140 randomInteger = Model.makeRandomNumericInt(minimum, maximum)
1141 }
1142 }
1143 const value = integer
1144 ? randomInteger!(state)
1145 : randomNumber!(state)
1146 return state.shrinks
1147 ? numberSample(value, bounds.minimum, bounds.maximum, integer)
1148 : Model.makeSample(value)
1149 }
1150 )
1151 }
1152 case "BigInt": {
1153 const ordered = constraint?.order === Order.BigInt ? constraint : undefined
1154 let minimum = ordered?.minimum as bigint | undefined
1155 let maximum = ordered?.maximum as bigint | undefined
1156 if (minimum !== undefined && ordered?.exclusiveMinimum === true) minimum++
1157 if (maximum !== undefined && ordered?.exclusiveMaximum === true) maximum--
1158 if (minimum !== undefined && maximum !== undefined && minimum > maximum) {
1159 throw arbitraryError("bigint constraints", path)
1160 }
1161 return BigIntArbitrary.make(minimum, maximum)
1162 }
1163 case "Symbol": {
1164 const strings = recur(SchemaAST.string, path, constraint)
1165 return Model.makeCompiled(
1166 [strings],
1167 () => strings.minCost,
1168 (state) =>
1169 Model.mapGeneration(strings.generate(state), (attempt) =>
1170 attempt._tag === "Discarded"
1171 ? attempt
1172 : Model.mapSample(attempt, (value) => Symbol.for(value)))
1173 )
1174 }
1175 case "Unknown":
1176 case "Any": {
1177 const json = recur(Schema.Json.ast, path)
1178 return Model.makeCompiled([json], () => json.minCost, (state) => json.generate(state))
1179 }
1180 case "ObjectKeyword": {
1181 const json = recur(Schema.Json.ast, path)
1182 return Model.makeCompiled(
1183 [json],
1184 () => 0,
1185 (state) =>
1186 Model.mapGeneration(json.generate(state), (attempt) => {
1187 if (
1188 attempt._tag === "Generated" && typeof attempt.value === "object" &&
1189 attempt.value !== null
1190 ) {
1191 return attempt
1192 }
1193 return Model.makeSample({})
1194 })
1195 )
1196 }
1197 case "Enum": {
1198 const values = [...new Set(ast.enums.map(([, value]) => value))]
1199 if (values.length === 0) throw arbitraryError("an enum with no members", path)
1200 return Model.makeCompiled(
1201 [],
1202 () => 0,
1203 (state) => Model.makeSample(values[Model.randomIndex(state, values.length)])
1204 )
1205 }
1206 case "TemplateLiteral": {
1207 const parts = ast.parts.map((part, index) => recur(part, [...path, index], finiteNumberConstraint))
1208 return Model.makeCompiled(
1209 parts,
1210 () => sumCosts(parts.map((part) => part.minCost)),
1211 (state) =>
1212 Model.mapComputation(generateSamples(parts, state), (generated) => {
1213 if (generated === undefined) return Model.discarded
1214 const sample = arraySample(generated, {
1215 fixedCount: generated.length,
1216 optionalCount: 0,
1217 repeatCount: 0,
1218 tailCount: 0,
1219 minimum: generated.length
1220 }, state.shrinks)
1221 return Model.mapSample(sample, (parts) => parts.map(globalThis.String).join(""))
1222 })
1223 )
1224 }
1225 case "Union": {
1226 const members = ast.types.map((member) => recur(member, path, constraint))
1227 if (members.length === 0) throw arbitraryError("a union with no members", path)
1228 let generate = (state: Model.GenerationState): Model.Generation<unknown> => Model.generateUnion(members, state)
1229 if (ast.options?.mode === "oneOf") {
1230 const parse = SchemaParser.run<unknown, never>(ast)
1231 const validate = (value: unknown) => optionComputation(parse(value))
1232 generate = (state) => Model.filterMapGeneration(Model.generateUnion(members, state), validate)
1233 }
1234 return Model.makeCompiled(
1235 members,
1236 () => Math.min(...members.map((member) => member.minCost)),
1237 generate
1238 )
1239 }
1240 case "Arrays":
1241 return compileArrays(ast, path, constraint)
1242 case "Objects": {
1243 const compiled = compileObjects(ast, path, constraint)
1244 if (
1245 ast.indexSignatures.length === 0 ||
1246 (ast.indexSignatures.length === 1 && ast.propertySignatures.length === 0)
1247 ) return compiled
1248 const parse = SchemaParser.run<Record<PropertyKey, any>, never>(
1249 new SchemaAST.Objects([], ast.indexSignatures)
1250 )
1251 const generate = compiled.generate
1252 compiled.generate = (state) =>
1253 Model.filterMapGeneration(
1254 generate(state),
1255 (value) =>
1256 Model.mapComputation(optionComputation(parse(value)), (parsed) =>
1257 Option.isNone(parsed) ? parsed : Option.some(value))
1258 )
1259 return compiled
1260 }
1261 case "Suspend": {
1262 const body = recur(ast.thunk(), path)
1263 return Model.makeCompiled([body], () => body.minCost, (state) => body.generate(state))
1264 }
1265 case "Declaration":
1266 return compileDeclaration(ast, path, constraint)
1267 }
1268 }
1269
1270 const compileArrays = (
1271 ast: SchemaAST.Arrays,
1272 path: ReadonlyArray<PropertyKey>,
1273 constraint: FilterConstraint | undefined
1274 ): Model.Compiled<ReadonlyArray<any>> => {
1275 const uniqueBy = constraint?.uniqueBy
1276 const elements = ast.elements.map((element, index) => ({
1277 optional: SchemaAST.isOptional(element),
1278 compiled: recur(element, [...path, index])
1279 }))
1280 const requiredCount = elements.findIndex((element) => element.optional)
1281 const required = requiredCount === -1 ? elements.length : requiredCount
1282 const optional = elements.length - required
1283 const rest = ast.rest.map((element, index) => recur(element, [...path, elements.length + index]))
1284 const head = rest[0]
1285 const tail = rest.slice(1)
1286 const [minimum, maximum] = lengthBounds(constraint, ["minLength", "maxLength"], path, "array")
1287 if (
1288 maximum !== undefined && maximum < required + tail.length ||
1289 head === undefined && minimum > elements.length + tail.length
1290 ) {
1291 throw arbitraryError("array constraints", path)
1292 }
1293 const dependencies = [...elements.map((element) => element.compiled), ...rest]
1294 const combinations = (limit: number): Array<readonly [optional: number, repeat: number, cost: number]> => {
1295 const out: Array<readonly [number, number, number]> = []
1296 const requiredCost = sumCosts(elements.slice(0, required).map((element) => element.compiled.minCost))
1297 const tailCost = sumCosts(tail.map((element) => element.minCost))
1298 const currentMaximum = Math.max(minimum, required + tail.length, limit)
1299 const upper = maximum === undefined ? currentMaximum : Math.min(maximum, currentMaximum)
1300 for (let optionalCount = 0; optionalCount <= optional; optionalCount++) {
1301 const fixed = required + optionalCount + tail.length
1302 const minimumRepeat = Math.max(0, minimum - fixed)
1303 const maximumRepeat = head === undefined ? 0 : Math.max(minimumRepeat, upper - fixed)
1304 if (fixed + minimumRepeat > upper || head === undefined && minimumRepeat > 0) continue
1305 const optionalCost = sumCosts(
1306 elements.slice(required, required + optionalCount).map((element) => element.compiled.minCost)
1307 )
1308 for (let repeat = minimumRepeat; repeat <= maximumRepeat; repeat++) {
1309 if ((repeat > 0 || tail.length > 0) && optionalCount < optional) continue
1310 const repeatCost = repeat === 0 ? 0 : repeat * (head?.minCost ?? 0)
1311 const cost = requiredCost + optionalCost + tailCost + repeatCost
1312 out.push([optionalCount, repeat, cost])
1313 }
1314 }
1315 return out
1316 }
1317 let cachedLimit: number | undefined
1318 let cachedBudget: number | undefined
1319 let cachedCombinations: ReadonlyArray<readonly [optional: number, repeat: number, cost: number]> = []
1320 let cachedPossible: ReadonlyArray<readonly [optional: number, repeat: number, cost: number]> = []
1321 const possibleCombinations = (limit: number, budget: number) => {
1322 if (limit !== cachedLimit) {
1323 cachedLimit = limit
1324 cachedBudget = undefined
1325 cachedCombinations = combinations(limit)
1326 }
1327 if (budget !== cachedBudget) {
1328 cachedBudget = budget
1329 cachedPossible = cachedCombinations.filter(([, , cost]) => cost <= budget)
1330 }
1331 return cachedPossible
1332 }
1333 return Model.makeCompiled(
1334 dependencies,
1335 () => {
1336 const possible = combinations(0)
1337 return possible.length === 0 ? infinity : Math.min(...possible.map(([, , cost]) => cost))
1338 },
1339 (state) => {
1340 const possible = possibleCombinations(state.size, state.budget.remaining)
1341 if (possible.length === 0) return Model.discarded
1342 const [optionalCount, repeatCount] = possible[Model.randomLength(state, 0, possible.length - 1)]
1343 // Explicit collection minima must stay productive while progressive checks are still at size zero.
1344 const itemState = state.size >= repeatCount ? state : { ...state, size: repeatCount }
1345 // Lower homogeneous arrays directly when no shrink context is needed.
1346 if (
1347 !state.shrinks && elements.length === 0 && tail.length === 0 && head !== undefined &&
1348 (!head.mayRecurse || uniqueBy === undefined)
1349 ) {
1350 return head.mayRecurse
1351 ? generateRepeatedRecursiveValues(head, repeatCount, itemState)
1352 : uniqueBy !== undefined
1353 ? generateRepeatedUniqueValues(head, repeatCount, itemState, uniqueBy)
1354 : generateRepeatedValues(head, repeatCount, itemState)
1355 }
1356 const selected = [
1357 ...elements.slice(0, required + optionalCount).map((element) => element.compiled),
1358 ...Array.from({ length: repeatCount }, () => head!),
1359 ...tail
1360 ]
1361 const makeAttempt = (generated: ReadonlyArray<Model.Sample<any>>) =>
1362 arraySample(generated, {
1363 fixedCount: required + optionalCount,
1364 optionalCount,
1365 repeatCount,
1366 tailCount: tail.length,
1367 minimum
1368 }, state.shrinks)
1369 if (uniqueBy === undefined) {
1370 return Model.mapComputation(
1371 generateSamples(selected, itemState),
1372 (generated) => generated === undefined ? Model.discarded : makeAttempt(generated)
1373 )
1374 }
1375 // The requested-length consecutive duplicate circuit breaker follows fast-check v4.9.0's ArrayArbitrary
1376 // strategy (MIT).
1377 // https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/_internals/ArrayArbitrary.ts
1378 const generated: Array<Model.Sample<any>> = []
1379 const addUnique = makeUniqueAdderBy(uniqueBy)
1380 let reserved = sumCosts(selected.map((child) => child.minCost))
1381 const maximumRetries = selected.length
1382 let index = 0
1383 let retries = 0
1384 let budget = state.budget.remaining
1385 const loop = (): Model.Generation<ReadonlyArray<any>> => {
1386 while (index < selected.length) {
1387 const child = selected[index]
1388 if (retries === 0) {
1389 reserved -= child.minCost
1390 budget = state.budget.remaining
1391 }
1392 const generatedChild = Model.generateWithReservedBudget(child, itemState, reserved)
1393 if (Model.isAttempt(generatedChild)) {
1394 const attempt = generatedChild
1395 if (attempt._tag === "Discarded") return Model.discarded
1396 if (!addUnique(attempt.value)) {
1397 if (++retries >= maximumRetries) return Model.discarded
1398 state.budget.remaining = budget
1399 continue
1400 }
1401 generated.push(attempt)
1402 index++
1403 retries = 0
1404 continue
1405 }
1406 return Effect.flatMapEager(generatedChild, (attempt) => {
1407 if (attempt._tag === "Discarded") return Effect.succeed(Model.discarded)
1408 if (!addUnique(attempt.value)) {
1409 if (++retries >= maximumRetries) return Effect.succeed(Model.discarded)
1410 state.budget.remaining = budget
1411 } else {
1412 generated.push(attempt)
1413 index++
1414 retries = 0
1415 }
1416 return Model.toEffect(loop())
1417 })
1418 }
1419 return makeAttempt(generated)
1420 }
1421 return loop()
1422 }
1423 )
1424 }
1425
1426 const compileObjects = (
1427 ast: SchemaAST.Objects,
1428 path: ReadonlyArray<PropertyKey>,
1429 constraint: FilterConstraint | undefined
1430 ): Model.Compiled<Record<PropertyKey, any>> => {
1431 const constrainedIndexes = ast.indexSignatures.flatMap((index, position) => {
1432 const constraint = collectChecks(index.type.checks, undefined).constraint
1433 return constraint === undefined ? [] : [{ index, position, constraint }]
1434 })
1435 const compileIndexedValue = (type: SchemaAST.AST, path: ReadonlyArray<PropertyKey>) => {
1436 const compiled = recur(type, path)
1437 // Scalar specializations have no recursive dependencies and keep the same minimum cost.
1438 const candidates = type._tag === "String" || type._tag === "Number" || type._tag === "BigInt"
1439 ? constrainedIndexes.filter(({ index }) => index.type !== type && index.type._tag === type._tag)
1440 : []
1441 const specializations = new Map<string, Model.Compiled<any>>()
1442 const forKey = (key: PropertyKey): Model.Compiled<any> => {
1443 if (candidates.length === 0) return compiled
1444 const input = { [key]: undefined }
1445 const matching = candidates.filter(({ index }) =>
1446 SchemaAST.getIndexSignatureKeys(input, index.parameter).length > 0
1447 )
1448 if (matching.length === 0) return compiled
1449 const cacheKey = matching.map(({ position }) => position).join(",")
1450 const cached = specializations.get(cacheKey)
1451 if (cached !== undefined) return cached
1452 let specialized = compiled
1453 try {
1454 let inherited: FilterConstraint | undefined
1455 for (const match of matching) inherited = mergeConstraint(inherited, match.constraint)
1456 const checks = collectChecks(type.checks, inherited)
1457 specialized = compileBase(type, path, checks.constraint)
1458 specialized.minCost = 0
1459 applyFilters(specialized, type, checks.filters)
1460 } catch {
1461 // Incompatible scalar constraints keep the original generator and indexed validation.
1462 }
1463 specializations.set(cacheKey, specialized)
1464 return specialized
1465 }
1466 return {
1467 compiled,
1468 forKey
1469 }
1470 }
1471 const properties = ast.propertySignatures.map((property) => ({
1472 property,
1473 optional: SchemaAST.isOptional(property.type),
1474 compiled: compileIndexedValue(property.type, [...path, property.name]).forKey(property.name)
1475 }))
1476 const propertyNames = new Set<PropertyKey>(
1477 properties.map(({ property }) =>
1478 typeof property.name === "symbol" ? property.name : globalThis.String(property.name)
1479 )
1480 )
1481 const indexes = ast.indexSignatures.map((index, position) => {
1482 const value = compileIndexedValue(index.type, [...path, `index-${position}-value`])
1483 return {
1484 parameter: recur(index.parameter, [...path, `index-${position}-key`]),
1485 value: value.compiled,
1486 valueForKey: value.forKey
1487 }
1488 })
1489 const required = properties.filter((property) => !property.optional)
1490 const optional = properties.filter((property) => property.optional)
1491 const [minimum, maximum] = lengthBounds(
1492 constraint,
1493 ["minProperties", "maxProperties"],
1494 path,
1495 "object property"
1496 )
1497 if (maximum !== undefined && maximum < required.length || indexes.length === 0 && minimum > properties.length) {
1498 throw arbitraryError("object property constraints", path)
1499 }
1500 const needed = Math.max(0, minimum - required.length)
1501 const minOptional = indexes.length === 0 ? needed : 0
1502 const minimumPropertyPlan = () => {
1503 const indexCost = Math.min(...indexes.map((index) => index.parameter.minCost + index.value.minCost))
1504 const selected = optional
1505 .filter((property) => property.compiled.minCost <= indexCost)
1506 .sort((a, b) => a.compiled.minCost - b.compiled.minCost)
1507 .slice(0, needed)
1508 const indexCount = needed - selected.length
1509 return {
1510 optional: selected,
1511 indexCount,
1512 indexCost,
1513 cost: sumCosts(selected.map((property) => property.compiled.minCost)) +
1514 (indexCount === 0 ? 0 : indexCount * indexCost)
1515 }
1516 }
1517 const dependencies = [
1518 ...properties.map((property) => property.compiled),
1519 ...indexes.flatMap((index) => [index.parameter, index.value])
1520 ]
1521 return Model.makeCompiled(
1522 dependencies,
1523 () => sumCosts(required.map((property) => property.compiled.minCost)) + minimumPropertyPlan().cost,
1524 (state) => {
1525 if (!state.shrinks && optional.length === 0 && indexes.length === 0) {
1526 return generateRequiredObjectValues(required, state, state.nullPrototype)
1527 }
1528 const currentMaximum = Math.max(minimum, required.length, state.size)
1529 const upper = maximum === undefined ? currentMaximum : Math.min(maximum, currentMaximum)
1530 const maxOptional = Math.min(optional.length, upper - required.length)
1531 const minimumPlan = minimumPropertyPlan()
1532 const minimumIndexCost = minimumPlan.indexCost
1533 const optionalCount = Model.randomInt(state, minOptional, maxOptional)
1534 let named = optionalCount === 0
1535 ? required
1536 : [...required, ...Model.shuffle(state, optional).slice(0, optionalCount)]
1537 let minimumIndexes = Math.max(0, minimum - named.length)
1538 let namedCost = sumCosts(named.map((property) => property.compiled.minCost))
1539 if (namedCost + (minimumIndexes === 0 ? 0 : minimumIndexes * minimumIndexCost) > state.budget.remaining) {
1540 named = [...required, ...minimumPlan.optional]
1541 minimumIndexes = minimumPlan.indexCount
1542 namedCost = sumCosts(named.map((property) => property.compiled.minCost))
1543 }
1544 const maximumIndexes = indexes.length === 0
1545 ? 0
1546 : upper - named.length
1547 const affordableIndexes = minimumIndexCost === 0
1548 ? maximumIndexes
1549 : minimumIndexCost === infinity
1550 ? 0
1551 : Math.min(maximumIndexes, Math.floor((state.budget.remaining - namedCost) / minimumIndexCost))
1552 if (affordableIndexes < minimumIndexes) return Model.discarded
1553 const indexCount = Model.randomLength(state, minimumIndexes, affordableIndexes)
1554 const indexReserved = indexCount === 0 ? 0 : indexCount * minimumIndexCost
1555 return Model.flatMapComputation(
1556 generateSamples(named.map((property) => property.compiled), state, indexReserved),
1557 (samples) => {
1558 if (samples === undefined) return Model.discarded
1559 const entries: Array<ObjectEntry> = samples.map((sample, index) => ({
1560 key: named[index].property.name,
1561 sample,
1562 removable: named[index].optional
1563 }))
1564 if (indexCount === 0) {
1565 return objectSample(entries, minimum, state.nullPrototype, propertyNames, state.shrinks)
1566 }
1567 return Effect.gen(function*() {
1568 for (let position = 0; position < indexCount; position++) {
1569 const futureReserved = (indexCount - position - 1) * minimumIndexCost
1570 const eligible = indexes.filter((index) =>
1571 index.parameter.minCost + index.value.minCost + futureReserved <= state.budget.remaining
1572 )
1573 if (eligible.length === 0) return Model.discarded
1574 const index = eligible[Model.randomIndex(state, eligible.length)]
1575 const budget = state.budget.remaining
1576 const reservedAfterKey = index.value.minCost + futureReserved
1577 // Multiple required index entries need enough key diversity before progressive size can advance.
1578 const keyState = state.size >= indexCount ? state : { ...state, size: indexCount }
1579 let keyAttempt = yield* Model.toEffectGeneration(
1580 Model.generateWithReservedBudget(index.parameter, keyState, reservedAfterKey)
1581 )
1582 let keySample: Model.Sample<PropertyKey>
1583 let retries = 0
1584 while (true) {
1585 if (keyAttempt._tag === "Discarded") return Model.discarded
1586 const normalized = normalizePropertyKeySample(keyAttempt)
1587 if (normalized === undefined) return Model.discarded
1588 keySample = normalized
1589 if (
1590 !propertyNames.has(keySample.value) &&
1591 !entries.some((entry) => entry.key === keySample.value)
1592 ) break
1593 if (retries++ >= 10) return Model.discarded
1594 state.budget.remaining = budget
1595 keyAttempt = yield* Model.toEffectGeneration(
1596 Model.generateWithReservedBudget(index.parameter, keyState, reservedAfterKey)
1597 )
1598 }
1599 const value = yield* Model.toEffectGeneration(
1600 Model.generateWithReservedBudget(index.valueForKey(keySample.value), state, futureReserved)
1601 )
1602 if (value._tag === "Discarded") return Model.discarded
1603 entries.push({ key: keySample.value, keySample, sample: value, removable: true })
1604 }
1605 return objectSample(entries, minimum, state.nullPrototype, propertyNames, state.shrinks)
1606 })
1607 }
1608 )
1609 }
1610 )
1611 }
1612
1613 const compileDeclaration = (
1614 ast: SchemaAST.Declaration,
1615 path: ReadonlyArray<PropertyKey>,
1616 constraint: FilterConstraint | undefined
1617 ): Model.Compiled<any> => {
1618 validateConstraint(constraint, path)
1619 const typeParameters = ast.typeParameters.map((parameter, index) => recur(parameter, [...path, index]))
1620 const parameters = ast.typeParameters.map((parameter) => Schema.make(SchemaAST.toType(parameter)))
1621 const getArbitrary = ast.annotations?.toCodecArbitrary
1622 const representation = (ast.annotations as Schema.Annotations.Declaration<any> | undefined)?.representation
1623 if (typeof getArbitrary !== "function" && representation?.id === "effect/schema/BigDecimal") {
1624 const ordered = constraint?.order === BigDecimal.Order ? constraint : undefined
1625 const compiled: Model.Compiled<unknown> | undefined = BigDecimalArbitrary.make({
1626 minimum: ordered?.minimum as BigDecimal.BigDecimal | undefined,
1627 exclusiveMinimum: ordered?.exclusiveMinimum,
1628 maximum: ordered?.maximum as BigDecimal.BigDecimal | undefined,
1629 exclusiveMaximum: ordered?.exclusiveMaximum
1630 })
1631 if (compiled === undefined) throw arbitraryError("BigDecimal constraints", path)
1632 return compiled
1633 }
1634 let link: SchemaAST.Link
1635 if (typeof getArbitrary === "function") {
1636 link = getArbitrary({
1637 typeParameters: parameters,
1638 constraint: withoutOrder(constraint)
1639 })
1640 } else {
1641 const builtInLink = builtInDeclarationLink(ast, parameters, withoutOrder(constraint))
1642 if (builtInLink !== undefined) {
1643 link = builtInLink
1644 } else {
1645 const getJson = ast.annotations?.toCodecJson
1646 if (typeof getJson === "function") {
1647 const jsonLink = getJson(parameters)
1648 if (jsonLink === undefined) throw arbitraryError("an opaque self-canonical Declaration", path)
1649 link = jsonLink
1650 } else {
1651 const get = ast.annotations?.toCodec
1652 if (typeof get !== "function") throw arbitraryError("an unsupported Declaration", path)
1653 link = get(parameters)
1654 }
1655 }
1656 }
1657 const target = recur(SchemaAST.toType(link.to), path)
1658 const decodeDeclaration = SchemaParser.run<unknown, never>(ast)
1659 const decode = (value: unknown): Model.Computation<Option.Option<unknown>> => {
1660 const transformed = link.transformation._tag === "Transformation"
1661 ? SchemaGetter.run(link.transformation.decode, Option.some(value), SchemaAST.defaultParseOptions)
1662 : link.transformation.decode(Effect.succeed(Option.some(value)), SchemaAST.defaultParseOptions)
1663 return Model.flatMapComputation(optionComputation(transformed), (outer) => {
1664 if (Option.isNone(outer) || Option.isNone(outer.value)) return Option.none()
1665 return optionComputation(decodeDeclaration(outer.value.value))
1666 })
1667 }
1668 return Model.makeCompiled(
1669 [target, ...typeParameters],
1670 () => target.minCost,
1671 (state) => Model.filterMapGeneration(target.generate(state), decode)
1672 )
1673 }
1674
1675 const root = recur(rootAst, [])
1676 for (let index = 0; index < pending.length; index++) pending[index]()
1677 const dependents = analyzeDependencyGraph(nodes, suspendBodies)
1678 const recursiveQueue = nodes.filter((node) => node.recursive)
1679 for (let index = 0; index < recursiveQueue.length; index++) {
1680 const node = recursiveQueue[index]
1681 if (node.mayRecurse) continue
1682 node.mayRecurse = true
1683 recursiveQueue.push(...dependents.get(node)!)
1684 }
1685 const queue = nodes.slice()
1686 const queued = new Set(nodes)
1687 for (let index = 0; index < queue.length; index++) {
1688 const node = queue[index]
1689 queued.delete(node)
1690 const next = node.computeMinCost()
1691 if (next >= node.minCost) continue
1692 node.minCost = next
1693 for (const dependent of dependents.get(node)!) {
1694 if (!queued.has(dependent)) {
1695 queued.add(dependent)
1696 queue.push(dependent)
1697 }
1698 }
1699 }
1700 if (root.minCost === infinity) {
1701 throw arbitraryError("a schema without a finite generation path", [])
1702 }
1703 return root
1704}
1705
1706function analyzeDependencyGraph(
1707 nodes: ReadonlyArray<Model.Compiled<any>>,
1708 suspendBodies: ReadonlyMap<Model.Compiled<any>, Model.Compiled<any>>
1709): ReadonlyMap<Model.Compiled<any>, ReadonlyArray<Model.Compiled<any>>> {
1710 const visited = new Set<Model.Compiled<any>>()
1711 const finished: Array<Model.Compiled<any>> = []
1712 for (const root of nodes) {
1713 if (visited.has(root)) continue
1714 visited.add(root)
1715 const stack: Array<{ readonly node: Model.Compiled<any>; index: number }> = [{ node: root, index: 0 }]
1716 while (stack.length > 0) {
1717 const frame = stack[stack.length - 1]
1718 if (frame.index < frame.node.dependencies.length) {
1719 const dependency = frame.node.dependencies[frame.index++]
1720 if (!visited.has(dependency)) {
1721 visited.add(dependency)
1722 stack.push({ node: dependency, index: 0 })
1723 }
1724 } else {
1725 finished.push(frame.node)
1726 stack.pop()
1727 }
1728 }
1729 }
1730
1731 const reverse = new Map<Model.Compiled<any>, Array<Model.Compiled<any>>>()
1732 for (const node of visited) reverse.set(node, [])
1733 for (const node of visited) {
1734 for (const dependency of node.dependencies) reverse.get(dependency)?.push(node)
1735 }
1736 const component = new Map<Model.Compiled<any>, number>()
1737 let componentId = 0
1738 for (let index = finished.length - 1; index >= 0; index--) {
1739 const root = finished[index]
1740 if (component.has(root)) continue
1741 component.set(root, componentId)
1742 const stack = [root]
1743 while (stack.length > 0) {
1744 const node = stack.pop()!
1745 for (const dependency of reverse.get(node)!) {
1746 if (component.has(dependency)) continue
1747 component.set(dependency, componentId)
1748 stack.push(dependency)
1749 }
1750 }
1751 componentId++
1752 }
1753 for (const [suspend, body] of suspendBodies) {
1754 suspend.recursive = component.get(suspend) === component.get(body)
1755 }
1756 return reverse
1757}