1import { assert, describe, it } from "@effect/vitest"
2import { Effect, Result, Schema } from "effect"
3import * as Arbitrary from "effect/Arbitrary"
4
5describe("Arbitrary array shrinking", () => {
6 const item = Arbitrary.schema(Schema.Literals([8, 27, 0, 1]), { shrink: (n) => n === 8 ? [1] as const : [] })
7 it.effect("reduces custom command sequences to Reset followed by Stop", () =>
8 Effect.gen(function*() {
9 const command = Arbitrary.map(item, (n) =>
10 n === 27
11 ? { _tag: "Reset" } as const
12 : n === 0
13 ? { _tag: "Stop" } as const
14 : { _tag: "Add", value: n } as const)
15 const commands = Arbitrary.array(command, { maxLength: 50 })
16 const property = (values: ReadonlyArray<{ readonly _tag: string }>) => {
17 const reset = values.findIndex((value) => value._tag === "Reset")
18 return reset === -1 || !values.slice(reset + 1).some((value) => value._tag === "Stop")
19 }
20 const result = yield* Arbitrary.checkEffect(commands, property, { runs: 1, size: 4, seed: 395 })
21 assert.strictEqual(result._tag, "Falsified")
22 if (result._tag === "Falsified") {
23 assert.strictEqual(result.initialInput.length, 4)
24 assert.deepStrictEqual(result.shrunkInput, [{ _tag: "Reset" }, { _tag: "Stop" }])
25 assert.deepStrictEqual(yield* Arbitrary.checkEffect(commands, property, { replay: result.replay }), result)
26 }
27 }))
28 for (
29 const [name, arbitrary, seed] of [
30 ["schema", item, 30],
31 [
32 "validated shrink",
33 Arbitrary.schema(Schema.Literals([8, 27, 0, 1]), {
34 shrink: (n) => n === 8 ? [99 as 8, 1] as const : []
35 }),
36 30
37 ],
38 ["map", Arbitrary.map(item, (n) => n), 30],
39 ["filter", Arbitrary.filter(item, (n) => n >= 0), 30],
40 ["filterMap", Arbitrary.filterMap(item, Result.succeed), 30],
41 ["flatMap", Arbitrary.flatMap(item, Arbitrary.Constant), 30],
42 ["all", Arbitrary.map(Arbitrary.all([item, Arbitrary.Constant("tag")]), ([n]) => n), 597]
43 ] as const
44 ) {
45 it.effect(`retries a previously passing element shrink after deletion (${name})`, () =>
46 Effect.gen(function*() {
47 const array = Arbitrary.array(arbitrary, { minLength: 2, maxLength: 4 })
48 const evaluated: Array<ReadonlyArray<number>> = []
49 const property = (values: ReadonlyArray<number>) => {
50 assert.isFalse(values.includes(99))
51 evaluated.push(values)
52 return !["8,27,0", "8,0", "1,0"].includes(values.join(","))
53 }
54 const result = yield* Arbitrary.checkEffect(array, property, { runs: 1, size: 4, seed })
55 assert.strictEqual(result._tag, "Falsified")
56 if (result._tag === "Falsified") {
57 assert.deepStrictEqual(result.initialInput, [8, 27, 0])
58 assert.deepStrictEqual(result.shrunkInput, [1, 0])
59 assert.isTrue(evaluated.some((values) => values.join(",") === "1,27,0"))
60 assert.deepStrictEqual(yield* Arbitrary.checkEffect(array, property, { replay: result.replay }), result)
61 }
62 }))
63 }
64
65 for (
66 const [name, arbitrary, seed] of [
67 ["Schema", Arbitrary.schema(Schema.Array(Schema.Literals([8, 27, 0, 1])).check(Schema.isMinLength(2))), 1967],
68 ["custom", Arbitrary.array(item, { minLength: 2, maxLength: 4 }), 395]
69 ] as const
70 ) {
71 it.effect(`removes a middle block when no single deletion fails (${name})`, () =>
72 Effect.gen(function*() {
73 const property = (values: ReadonlyArray<number>) => {
74 assert.isAtLeast(values.length, 2)
75 return !["8,27,0,1", "8,1"].includes(values.join(","))
76 }
77 const result = yield* Arbitrary.checkEffect(arbitrary, property, { runs: 1, size: 4, seed })
78 assert.strictEqual(result._tag, "Falsified")
79 if (result._tag === "Falsified") {
80 assert.deepStrictEqual(result.initialInput, [8, 27, 0, 1])
81 assert.deepStrictEqual(result.shrunkInput, [8, 1])
82 assert.deepStrictEqual(yield* Arbitrary.checkEffect(arbitrary, property, { replay: result.replay }), result)
83 }
84 }))
85 }
86
87 it("rejects invalid length bounds immediately", () => {
88 for (const length of [-1, 0.5, NaN, Infinity, 0x100000000]) {
89 assert.throws(() => Arbitrary.array(item, { minLength: length }), RangeError)
90 assert.throws(() => Arbitrary.array(item, { maxLength: length }), RangeError)
91 }
92 assert.throws(() => Arbitrary.array(item, { minLength: 3, maxLength: 2 }), RangeError)
93 assert.doesNotThrow(() => Arbitrary.array(item, { maxLength: 0xffffffff }))
94 })
95
96 it.effect("honors minima at size zero, maxima and exact lengths", () =>
97 Effect.gen(function*() {
98 for (const options of [{}, { minLength: 3 }, { maxLength: 2 }, { minLength: 2, maxLength: 2 }]) {
99 for (const size of [0, 1, 10]) {
100 const arbitrary = Arbitrary.array(item, options)
101 const values = yield* Arbitrary.sampleEffect(arbitrary, { size, count: 50, seed: "array-bounds" })
102 assert.isTrue(values.every((value) =>
103 value.length >= (options.minLength ?? 0) &&
104 value.length <= Math.min(options.maxLength ?? Infinity, Math.max(size, options.minLength ?? 0))
105 ))
106 const result = yield* Arbitrary.checkEffect(arbitrary, () => false, { size, runs: 1, seed: "array-bounds" })
107 assert.strictEqual(result._tag, "Falsified")
108 if (result._tag === "Falsified") {
109 assert.deepStrictEqual(result.initialInput, values[0])
110 assert.strictEqual(result.shrunkInput.length, options.minLength ?? 0)
111 }
112 }
113 }
114 }))
115
116 it.effect("does not generate elements for an empty array or shorten a discarded generation", () =>
117 Effect.gen(function*() {
118 let calls = 0
119 const rejected = Arbitrary.filter(item, () => {
120 calls++
121 return false
122 })
123 const empty = Arbitrary.array(rejected, { maxLength: 0 })
124 assert.deepStrictEqual(yield* Arbitrary.sampleEffect(empty, { count: 1, seed: 0 }), [[]])
125 assert.strictEqual(calls, 0)
126 const result = yield* Arbitrary.checkEffect(
127 Arbitrary.array(rejected, { minLength: 2 }),
128 () => true,
129 { runs: 1, maxDiscards: 0, seed: 0 }
130 )
131 assert.strictEqual(result._tag, "Exhausted")
132 assert.strictEqual(calls, 1)
133 }))
134
135 it.effect("preserves retained object identities and order without generating replacements", () =>
136 Effect.gen(function*() {
137 const arbitrary = Arbitrary.array(
138 Arbitrary.map(Arbitrary.Constant(null), () => ({ command: "Stop" })),
139 { minLength: 2, maxLength: 8 }
140 )
141 const seen: Array<ReadonlyArray<object>> = []
142 const result = yield* Arbitrary.checkEffect(arbitrary, (values) => {
143 seen.push(values)
144 return false
145 }, { runs: 1, size: 8, seed: 0 })
146 assert.strictEqual(result._tag, "Falsified")
147 if (result._tag === "Falsified") {
148 assert.isAbove(result.initialInput.length, 2)
149 assert.strictEqual(result.shrunkInput.length, 2)
150 for (const values of seen) {
151 const indexes = values.map((value) => result.initialInput.indexOf(value as { command: string }))
152 assert.isTrue(indexes.every((index, i) => index >= 0 && (i === 0 || index > indexes[i - 1])))
153 }
154 assert.strictEqual(result.shrunkInput[0], result.initialInput[result.initialInput.length - 2])
155 assert.strictEqual(result.shrunkInput[1], result.initialInput[result.initialInput.length - 1])
156 }
157 }))
158
159 it.effect("counts rejected element candidates against maxShrinks and replays past them", () =>
160 Effect.gen(function*() {
161 const filtered = Arbitrary.schema(Schema.Literals([8, 1, 0]), {
162 shrink: (value) => value === 8 ? [1, 0] as const : []
163 }).pipe(Arbitrary.filter((value) => value !== 1))
164 const arbitrary = Arbitrary.array(filtered, { minLength: 1, maxLength: 1 })
165 const evaluated: Array<Array<number>> = []
166 const property = (values: Array<number>) => {
167 evaluated.push(values)
168 return false
169 }
170 const limited = yield* Arbitrary.checkEffect(arbitrary, property, { runs: 1, seed: 0, maxShrinks: 1 })
171 assert.strictEqual(limited._tag, "Falsified")
172 if (limited._tag === "Falsified") {
173 assert.deepStrictEqual(limited.initialInput, [8])
174 assert.deepStrictEqual(limited.shrunkInput, [8])
175 assert.deepStrictEqual(evaluated, [[8]])
176 }
177 const result = yield* Arbitrary.checkEffect(arbitrary, property, { runs: 1, seed: 0, maxShrinks: 20 })
178 assert.strictEqual(result._tag, "Falsified")
179 if (result._tag === "Falsified") {
180 assert.deepStrictEqual(result.shrunkInput, [0])
181 assert.deepStrictEqual(yield* Arbitrary.checkEffect(arbitrary, property, { replay: result.replay }), result)
182 }
183 }))
184
185 it.effect("does not inspect element shrinking during sampling or successful checks", () =>
186 Effect.gen(function*() {
187 let shrinks = 0
188 const arbitrary = Arbitrary.array(
189 Arbitrary.schema(Schema.Literal(8), {
190 shrink: () => {
191 shrinks++
192 return []
193 }
194 }),
195 { minLength: 10, maxLength: 10 }
196 )
197 yield* Arbitrary.sampleEffect(arbitrary, { count: 10, seed: 0 })
198 yield* Arbitrary.checkEffect(arbitrary, () => true, { runs: 10, seed: 0 })
199 yield* Arbitrary.checkEffect(arbitrary, () => false, { runs: 1, seed: 0, maxShrinks: 0 })
200 assert.strictEqual(shrinks, 0)
201 }))
202
203 it.effect("shares the recursion budget across array elements and reserves required siblings", () =>
204 Effect.gen(function*() {
205 interface Chain {
206 readonly next: Chain | null
207 }
208 const Chain: Schema.Codec<Chain> = Schema.Struct({
209 next: Schema.suspend(() => Schema.Union([Schema.Null, Chain]))
210 })
211 const arbitrary = Arbitrary.all([
212 Arbitrary.array(Arbitrary.schema(Chain), { minLength: 3, maxLength: 3 }),
213 Arbitrary.schema(Chain)
214 ])
215 const depth = (chain: Chain): number => chain.next === null ? 0 : 1 + depth(chain.next)
216 const values = yield* Arbitrary.sampleEffect(arbitrary, {
217 count: 100,
218 maxDiscards: 0,
219 seed: "array-recursion-budget",
220 size: 5
221 })
222 assert.isTrue(
223 values.every(([array, last]) => array.reduce((total, chain) => total + depth(chain), depth(last)) <= 5)
224 )
225 }))
226
227 it.effect("protects fixed tuple prefixes, tails and the order of optional positions", () =>
228 Effect.gen(function*() {
229 for (
230 const schema of [
231 Schema.TupleWithRest(Schema.Tuple([Schema.Literal("head")]), [Schema.Int, Schema.Literal("tail")]),
232 Schema.Tuple([
233 Schema.Literal("head"),
234 Schema.optionalKey(Schema.Literal(27)),
235 Schema.optionalKey(Schema.Literal(0))
236 ])
237 ]
238 ) {
239 for (let seed = 0; seed < 10; seed++) {
240 const result = yield* Arbitrary.checkEffect(Arbitrary.schema(schema), (values) => {
241 assert.isTrue(Schema.is(schema)(values))
242 return false
243 }, { runs: 1, size: 8, seed })
244 assert.strictEqual(result._tag, "Falsified")
245 if (result._tag === "Falsified") {
246 assert.deepStrictEqual(
247 result.shrunkInput,
248 result.initialInput.some((value) => value === "tail")
249 ? ["head", "tail"]
250 : ["head"]
251 )
252 }
253 }
254 }
255 }))
256
257 it.effect("handles wide exact-length arrays", () =>
258 Effect.gen(function*() {
259 const arbitrary = Arbitrary.array(Arbitrary.Constant(0), { minLength: 20_000, maxLength: 20_000 })
260 const result = yield* Arbitrary.checkEffect(arbitrary, () => false, { runs: 1, seed: 0 })
261 assert.strictEqual(result._tag, "Falsified")
262 if (result._tag === "Falsified") assert.strictEqual(result.shrunkInput.length, 20_000)
263 }))
264
265 it.effect("keeps unique arrays and decoded collections valid during shrinking", () =>
266 Effect.gen(function*() {
267 for (
268 const schema of [
269 Schema.Array(Schema.Int).check(Schema.isUnique(), Schema.isMinLength(2)),
270 Schema.ReadonlySet(Schema.Int),
271 Schema.ReadonlyMap(Schema.Int, Schema.Int),
272 Schema.Uint8Array
273 ]
274 ) {
275 const result = yield* Arbitrary.checkEffect(Arbitrary.schema(schema), (value) => {
276 assert.isTrue(Schema.is(schema)(value))
277 return false
278 }, { runs: 1, size: 10, seed: 0 })
279 assert.strictEqual(result._tag, "Falsified")
280 }
281 }))
282
283 for (
284 const [name, needed] of [
285 ["prefix", [27, 0]],
286 ["middle", [8, 0]],
287 ["suffix", [8, 27]]
288 ] as const
289 ) {
290 it.effect(`removes an irrelevant ${name} from a Schema array`, () =>
291 Effect.gen(function*() {
292 const arbitrary = Arbitrary.schema(Schema.Array(Schema.Literals([8, 27, 0, 1])))
293 const property = (values: ReadonlyArray<number>) =>
294 !(values.includes(needed[0]) && values.indexOf(needed[1]) > values.indexOf(needed[0]))
295 const result = yield* Arbitrary.checkEffect(arbitrary, property, {
296 runs: 1,
297 size: 4,
298 seed: 1967,
299 maxShrinks: 1000
300 })
301 assert.strictEqual(result._tag, "Falsified")
302 if (result._tag === "Falsified") {
303 assert.deepStrictEqual(result.initialInput, [8, 27, 0, 1])
304 assert.deepStrictEqual(result.shrunkInput, needed)
305 assert.deepStrictEqual(yield* Arbitrary.checkEffect(arbitrary, property, { replay: result.replay }), result)
306 }
307 }))
308 }
309})