1import type * as Schema from "../../Schema.ts"
2import * as Model from "./model.ts"
3
4type Pattern = Schema.Annotations.ToArbitrary.Pattern
5
6type Node = Literal | Character | Concatenation | Alternation | Repetition
7
8interface Literal {
9 readonly _tag: "Literal"
10 readonly value: string
11}
12
13interface Character {
14 readonly _tag: "Character"
15 readonly intervals: ReadonlyArray<Interval>
16 readonly preferred: readonly [ReadonlyArray<number>, ReadonlyArray<number>]
17 readonly counts: readonly [number, number]
18}
19
20interface Concatenation {
21 readonly _tag: "Concatenation"
22 readonly nodes: ReadonlyArray<Node>
23}
24
25interface Alternation {
26 readonly _tag: "Alternation"
27 readonly nodes: ReadonlyArray<Node>
28}
29
30interface Repetition {
31 readonly _tag: "Repetition"
32 readonly node: Node
33 readonly minimum: number
34 readonly maximum: number | undefined
35}
36
37interface Interval {
38 readonly minimum: number
39 readonly maximum: number
40}
41
42/** @internal */
43export interface Compiled {
44 readonly minimumLength: number
45 readonly generate: (
46 state: Model.GenerationState,
47 minimumLength: number,
48 maximumLength: number
49 ) => string | undefined
50 readonly shrink: (value: string, minimumLength: number) => ReadonlyArray<string>
51}
52
53const empty: Literal = { _tag: "Literal", value: "" }
54const maximumCodePoint = 0x10ffff
55const highSurrogateMinimum = 0xd800
56const lowSurrogateMaximum = 0xdfff
57const digitIntervals: ReadonlyArray<Interval> = [{ minimum: 48, maximum: 57 }]
58const wordIntervals: ReadonlyArray<Interval> = [
59 { minimum: 48, maximum: 57 },
60 { minimum: 65, maximum: 90 },
61 { minimum: 95, maximum: 95 },
62 { minimum: 97, maximum: 122 }
63]
64const whitespaceIntervals: ReadonlyArray<Interval> = [
65 { minimum: 9, maximum: 13 },
66 { minimum: 32, maximum: 32 },
67 { minimum: 160, maximum: 160 },
68 { minimum: 0x1680, maximum: 0x1680 },
69 { minimum: 0x2000, maximum: 0x200a },
70 { minimum: 0x2028, maximum: 0x2029 },
71 { minimum: 0x202f, maximum: 0x202f },
72 { minimum: 0x205f, maximum: 0x205f },
73 { minimum: 0x3000, maximum: 0x3000 },
74 { minimum: 0xfeff, maximum: 0xfeff }
75]
76const lineTerminatorIntervals: ReadonlyArray<Interval> = [
77 { minimum: 10, maximum: 10 },
78 { minimum: 13, maximum: 13 },
79 { minimum: 0x2028, maximum: 0x2029 }
80]
81const codePointIntervals: ReadonlyArray<Interval> = [{ minimum: 0, maximum: maximumCodePoint }]
82const printableAsciiIntervals: ReadonlyArray<Interval> = [{ minimum: 32, maximum: 126 }]
83const preferredCodePoints = [
84 ...globalThis.Array.from({ length: 95 }, (_, index) => index + 32),
85 9,
86 10,
87 11,
88 12,
89 13,
90 0,
91 0x80,
92 0xe9,
93 0x3a9,
94 0x1f600
95]
96
97function characterMetadata(intervals: ReadonlyArray<Interval>, length: number) {
98 return {
99 preferred: preferredCodePoints.filter((codePoint) =>
100 codePointLength(codePoint) === length && codePointInIntervals(codePoint, intervals)
101 ),
102 count: intervals.reduce((count, interval) => count + countCodePointsInInterval(interval, length), 0)
103 }
104}
105
106function character(intervals: ReadonlyArray<Interval>): Character {
107 const normalized = normalizeIntervals(intervals)
108 const one = characterMetadata(normalized, 1)
109 const two = characterMetadata(normalized, 2)
110 return {
111 _tag: "Character",
112 intervals: normalized,
113 preferred: [one.preferred, two.preferred],
114 counts: [one.count, two.count]
115 }
116}
117
118function literal(value: string): Literal {
119 return value.length === 0 ? empty : { _tag: "Literal", value }
120}
121
122function concatenation(nodes: ReadonlyArray<Node>): Node {
123 const flattened: Array<Node> = []
124 let pending = ""
125 const flush = () => {
126 if (pending.length === 0) return
127 flattened.push(literal(pending))
128 pending = ""
129 }
130 for (const node of nodes) {
131 if (node._tag === "Literal") {
132 pending += node.value
133 } else if (node._tag === "Concatenation") {
134 flush()
135 flattened.push(...node.nodes)
136 } else {
137 flush()
138 flattened.push(node)
139 }
140 }
141 flush()
142 return flattened.length === 0 ? empty : flattened.length === 1 ? flattened[0] : {
143 _tag: "Concatenation",
144 nodes: flattened
145 }
146}
147
148function alternation(nodes: ReadonlyArray<Node>): Node {
149 const flattened: Array<Node> = []
150 for (const node of nodes) {
151 if (node._tag === "Alternation") flattened.push(...node.nodes)
152 else flattened.push(node)
153 }
154 return flattened.length === 1 ? flattened[0] : { _tag: "Alternation", nodes: flattened }
155}
156
157function normalizeIntervals(intervals: ReadonlyArray<Interval>): ReadonlyArray<Interval> {
158 if (intervals.length <= 1) return intervals
159 const sorted = intervals.slice().sort((a, b) => a.minimum - b.minimum || a.maximum - b.maximum)
160 const out: Array<Interval> = []
161 for (const interval of sorted) {
162 const previous = out[out.length - 1]
163 if (previous === undefined || interval.minimum > previous.maximum + 1) {
164 out.push(interval)
165 } else if (interval.maximum > previous.maximum) {
166 out[out.length - 1] = { minimum: previous.minimum, maximum: interval.maximum }
167 }
168 }
169 return out
170}
171
172function restrictIntervals(intervals: ReadonlyArray<Interval>, maximum: number): ReadonlyArray<Interval> {
173 return intervals.flatMap((interval) =>
174 interval.minimum > maximum ? [] : [{ minimum: interval.minimum, maximum: Math.min(interval.maximum, maximum) }]
175 )
176}
177
178function restrictCharacterCodePoints(node: Node, maximum: number): Node {
179 switch (node._tag) {
180 case "Character":
181 return character(restrictIntervals(node.intervals, maximum))
182 case "Concatenation":
183 return concatenation(node.nodes.map((child) => restrictCharacterCodePoints(child, maximum)))
184 case "Alternation":
185 return alternation(node.nodes.map((child) => restrictCharacterCodePoints(child, maximum)))
186 case "Repetition":
187 return { ...node, node: restrictCharacterCodePoints(node.node, maximum) }
188 case "Literal":
189 return node
190 }
191}
192
193function complementIntervals(intervals: ReadonlyArray<Interval>): ReadonlyArray<Interval> {
194 const normalized = normalizeIntervals(intervals)
195 const out: Array<Interval> = []
196 let minimum = 0
197 for (const interval of normalized) {
198 if (minimum < interval.minimum) out.push({ minimum, maximum: interval.minimum - 1 })
199 minimum = Math.max(minimum, interval.maximum + 1)
200 }
201 if (minimum <= maximumCodePoint) out.push({ minimum, maximum: maximumCodePoint })
202 return out
203}
204
205function codePointInIntervals(codePoint: number, intervals: ReadonlyArray<Interval>): boolean {
206 for (const interval of intervals) {
207 if (codePoint < interval.minimum) return false
208 if (codePoint <= interval.maximum) return true
209 }
210 return false
211}
212
213function isSurrogate(codePoint: number): boolean {
214 return codePoint >= highSurrogateMinimum && codePoint <= lowSurrogateMaximum
215}
216
217function codePointLength(codePoint: number): number {
218 return codePoint > 0xffff ? 2 : 1
219}
220
221function countCodePointsInInterval(interval: Interval, length: number): number {
222 const minimum = length === 1 ? interval.minimum : Math.max(interval.minimum, 0x10000)
223 const maximum = length === 1 ? Math.min(interval.maximum, 0xffff) : interval.maximum
224 if (minimum > maximum) return 0
225 if (length === 1 && minimum <= lowSurrogateMaximum && maximum >= highSurrogateMinimum) {
226 return maximum - minimum + 1 -
227 (Math.min(maximum, lowSurrogateMaximum) - Math.max(minimum, highSurrogateMinimum) + 1)
228 }
229 return maximum - minimum + 1
230}
231
232function codePointAtOffset(interval: Interval, length: number, offset: number): number {
233 let codePoint = (length === 1 ? interval.minimum : Math.max(interval.minimum, 0x10000)) + offset
234 if (length === 1 && codePoint >= highSurrogateMinimum) codePoint += lowSurrogateMaximum - highSurrogateMinimum + 1
235 return codePoint
236}
237
238function generateCharacter(node: Character, length: number, state: Model.GenerationState): string | undefined {
239 const preferred = node.preferred[length - 1]
240 if (preferred.length > 0 && Model.randomInt(state, 1, state.biasFactor) === 1) {
241 return globalThis.String.fromCodePoint(preferred[Model.randomIndex(state, preferred.length)])
242 }
243 const count = node.counts[length - 1]
244 if (count === 0) return undefined
245 let offset = Model.randomInt(state, 0, count - 1)
246 for (const interval of node.intervals) {
247 const size = countCodePointsInInterval(interval, length)
248 if (offset < size) return globalThis.String.fromCodePoint(codePointAtOffset(interval, length, offset))
249 offset -= size
250 }
251 return undefined
252}
253
254function canonicalCharacter(node: Character, length: number): string | undefined {
255 const preferred = node.preferred[length - 1][0]
256 if (preferred !== undefined) return globalThis.String.fromCodePoint(preferred)
257 for (const interval of node.intervals) {
258 if (countCodePointsInInterval(interval, length) > 0) {
259 return globalThis.String.fromCodePoint(codePointAtOffset(interval, length, 0))
260 }
261 }
262 return undefined
263}
264
265function isDecimal(value: string | undefined): boolean {
266 return value !== undefined && value >= "0" && value <= "9"
267}
268
269function isHexadecimal(value: string | undefined): boolean {
270 return value !== undefined &&
271 (value >= "0" && value <= "9" || value >= "a" && value <= "f" || value >= "A" && value <= "F")
272}
273
274class Parser {
275 private index = 0
276 private supported = true
277 private readonly source: string
278 private readonly dotAll: boolean
279
280 constructor(source: string, dotAll: boolean) {
281 this.source = source
282 this.dotAll = dotAll
283 }
284
285 parse(): Node | undefined {
286 const node = this.parseAlternation()
287 return this.supported && this.index === this.source.length ? node : undefined
288 }
289
290 private parseAlternation(): Node {
291 const nodes = [this.parseConcatenation()]
292 while (this.peek() === "|") {
293 this.index++
294 nodes.push(this.parseConcatenation())
295 }
296 return alternation(nodes)
297 }
298
299 private parseConcatenation(): Node {
300 const nodes: Array<Node> = []
301 while (this.index < this.source.length && this.peek() !== ")" && this.peek() !== "|") {
302 const atom = this.parseAtom()
303 if (atom === undefined) {
304 this.supported = false
305 break
306 }
307 nodes.push(this.parseQuantifier(atom))
308 }
309 return concatenation(nodes)
310 }
311
312 private parseAtom(): Node | undefined {
313 const token = this.source[this.index++]
314 switch (token) {
315 case "^":
316 case "$":
317 return empty
318 case ".":
319 return character(this.dotAll ? codePointIntervals : complementIntervals(lineTerminatorIntervals))
320 case "[":
321 return this.parseCharacterClass()
322 case "(":
323 return this.parseGroup()
324 case "\\":
325 return this.parseEscape(false)
326 case "*":
327 case "+":
328 case "?":
329 case "{":
330 case ")":
331 return undefined
332 default:
333 return literal(token)
334 }
335 }
336
337 private parseGroup(): Node | undefined {
338 if (this.peek() === "?") {
339 this.index++
340 if (this.peek() === ":") {
341 this.index++
342 } else if (this.peek() === "<") {
343 const next = this.source[this.index + 1]
344 if (next === "=" || next === "!") return undefined
345 this.index++
346 while (this.index < this.source.length && this.peek() !== ">") this.index++
347 if (this.peek() !== ">") return undefined
348 this.index++
349 } else {
350 return undefined
351 }
352 }
353 const node = this.parseAlternation()
354 if (this.peek() !== ")") return undefined
355 this.index++
356 return node
357 }
358
359 private parseQuantifier(node: Node): Node {
360 const start = this.index
361 let minimum: number | undefined
362 let maximum: number | undefined
363 switch (this.peek()) {
364 case "*":
365 minimum = 0
366 this.index++
367 break
368 case "+":
369 minimum = 1
370 this.index++
371 break
372 case "?":
373 minimum = 0
374 maximum = 1
375 this.index++
376 break
377 case "{": {
378 this.index++
379 const from = this.parseNatural()
380 if (from === undefined) {
381 this.index = start
382 return node
383 }
384 minimum = from
385 if (this.peek() === "}") {
386 maximum = from
387 this.index++
388 } else if (this.peek() === ",") {
389 this.index++
390 maximum = this.parseNatural()
391 if (this.peek() !== "}") {
392 this.index = start
393 return node
394 }
395 this.index++
396 } else {
397 this.index = start
398 return node
399 }
400 break
401 }
402 default:
403 return node
404 }
405 if (this.peek() === "?") this.index++
406 return { _tag: "Repetition", node, minimum, maximum }
407 }
408
409 private parseNatural(): number | undefined {
410 const start = this.index
411 while (isDecimal(this.peek())) this.index++
412 if (start === this.index) return undefined
413 const value = globalThis.Number(this.source.slice(start, this.index))
414 return Number.isSafeInteger(value) ? value : undefined
415 }
416
417 private parseCharacterClass(): Node | undefined {
418 const negative = this.peek() === "^"
419 if (negative) this.index++
420 const intervals: Array<Interval> = []
421 let first = true
422 while (this.index < this.source.length && (this.peek() !== "]" || first)) {
423 first = false
424 const left = this.parseClassAtom()
425 if (left === undefined) return undefined
426 if (this.peek() === "-" && this.source[this.index + 1] !== "]") {
427 this.index++
428 const right = this.parseClassAtom()
429 if (
430 right === undefined || left.length !== 1 || right.length !== 1 ||
431 left[0].minimum !== left[0].maximum || right[0].minimum !== right[0].maximum ||
432 left[0].minimum > right[0].minimum
433 ) return undefined
434 intervals.push({ minimum: left[0].minimum, maximum: right[0].minimum })
435 } else {
436 intervals.push(...left)
437 }
438 }
439 if (this.peek() !== "]") return undefined
440 this.index++
441 const normalized = normalizeIntervals(intervals)
442 return character(negative ? complementIntervals(normalized) : normalized)
443 }
444
445 private parseClassAtom(): ReadonlyArray<Interval> | undefined {
446 const token = this.source[this.index++]
447 if (token === "\\") {
448 const escaped = this.parseEscape(true)
449 return escaped?._tag === "Character"
450 ? escaped.intervals
451 : escaped?._tag === "Literal"
452 ? this.literalIntervals(escaped.value)
453 : undefined
454 }
455 if (token === undefined) return undefined
456 const codePoint = token.codePointAt(0)!
457 return [{ minimum: codePoint, maximum: codePoint }]
458 }
459
460 private parseEscape(inClass: boolean): Node | undefined {
461 const token = this.source[this.index++]
462 switch (token) {
463 case "d":
464 return character(digitIntervals)
465 case "D":
466 return character(complementIntervals(digitIntervals))
467 case "w":
468 return character(wordIntervals)
469 case "W":
470 return character(complementIntervals(wordIntervals))
471 case "s":
472 return character(whitespaceIntervals)
473 case "S":
474 return character(complementIntervals(whitespaceIntervals))
475 case "b":
476 return inClass ? literal("\b") : undefined
477 case "B":
478 return undefined
479 case "n":
480 return literal("\n")
481 case "r":
482 return literal("\r")
483 case "t":
484 return literal("\t")
485 case "v":
486 return literal("\v")
487 case "f":
488 return literal("\f")
489 case "0":
490 return isDecimal(this.peek()) ? undefined : literal("\0")
491 case "c": {
492 const control = this.source[this.index++]
493 if (control === undefined || !/[A-Za-z]/.test(control)) return undefined
494 return literal(globalThis.String.fromCharCode(control.toUpperCase().charCodeAt(0) % 32))
495 }
496 case "x":
497 return this.parseCodePoint(2)
498 case "u":
499 if (this.peek() === "{") {
500 this.index++
501 const start = this.index
502 while (isHexadecimal(this.peek())) this.index++
503 if (start === this.index || this.peek() !== "}") return undefined
504 const value = Number.parseInt(this.source.slice(start, this.index), 16)
505 this.index++
506 return value <= maximumCodePoint && !isSurrogate(value)
507 ? literal(globalThis.String.fromCodePoint(value))
508 : undefined
509 }
510 return this.parseCodePoint(4)
511 case "p":
512 case "P":
513 case "k":
514 return undefined
515 case undefined:
516 return undefined
517 default:
518 return isDecimal(token) ? undefined : literal(token)
519 }
520 }
521
522 private parseCodePoint(length: number): Node | undefined {
523 const encoded = this.source.slice(this.index, this.index + length)
524 if (encoded.length !== length || ![...encoded].every(isHexadecimal)) return undefined
525 this.index += length
526 return literal(globalThis.String.fromCharCode(Number.parseInt(encoded, 16)))
527 }
528
529 private literalIntervals(value: string): ReadonlyArray<Interval> | undefined {
530 const codePoints = [...value]
531 if (codePoints.length !== 1) return undefined
532 const codePoint = codePoints[0].codePointAt(0)!
533 return [{ minimum: codePoint, maximum: codePoint }]
534 }
535
536 private peek(): string | undefined {
537 return this.source[this.index]
538 }
539}
540
541type Lengths = ReadonlyArray<boolean>
542type LengthCache = Map<Node, Lengths>
543
544function emptyLengths(limit: number): Array<boolean> {
545 return globalThis.Array(limit + 1).fill(false)
546}
547
548function concatenateLengths(left: Lengths, right: Lengths, limit: number): Array<boolean> {
549 const out = emptyLengths(limit)
550 for (let leftLength = 0; leftLength <= limit && leftLength < left.length; leftLength++) {
551 if (!left[leftLength]) continue
552 for (let rightLength = 0; rightLength + leftLength <= limit && rightLength < right.length; rightLength++) {
553 if (right[rightLength]) out[leftLength + rightLength] = true
554 }
555 }
556 return out
557}
558
559function repetitionLengths(node: Repetition, child: Lengths, limit: number): Array<boolean> {
560 const out = emptyLengths(limit)
561 const nullable = child[0] === true
562 let smallestPositive = 1
563 while (smallestPositive <= limit && child[smallestPositive] !== true) smallestPositive++
564 const relevant = smallestPositive > limit ? 0 : Math.floor(limit / smallestPositive)
565 const minimum = nullable ? 0 : node.minimum
566 const maximum = Math.min(node.maximum ?? relevant, relevant)
567 if (minimum > maximum) return out
568 let current = emptyLengths(limit)
569 current[0] = true
570 for (let count = 0; count <= maximum; count++) {
571 if (count >= minimum) {
572 for (let length = 0; length <= limit; length++) if (current[length]) out[length] = true
573 }
574 if (count < maximum) current = concatenateLengths(current, child, limit)
575 }
576 return out
577}
578
579function possibleLengths(node: Node, limit: number, cache: LengthCache): Lengths {
580 const cached = cache.get(node)
581 if (cached !== undefined && cached.length > limit) return cached
582 let out: Array<boolean>
583 switch (node._tag) {
584 case "Literal": {
585 out = emptyLengths(limit)
586 if (node.value.length <= limit) out[node.value.length] = true
587 break
588 }
589 case "Character": {
590 out = emptyLengths(limit)
591 if (node.intervals.some((interval) => countCodePointsInInterval(interval, 1) > 0) && limit >= 1) out[1] = true
592 if (node.intervals.some((interval) => countCodePointsInInterval(interval, 2) > 0) && limit >= 2) out[2] = true
593 break
594 }
595 case "Alternation": {
596 out = emptyLengths(limit)
597 for (const child of node.nodes) {
598 const lengths = possibleLengths(child, limit, cache)
599 for (let length = 0; length <= limit; length++) if (lengths[length]) out[length] = true
600 }
601 break
602 }
603 case "Concatenation": {
604 let current = emptyLengths(limit)
605 current[0] = true
606 for (const child of node.nodes) {
607 current = concatenateLengths(current, possibleLengths(child, limit, cache), limit)
608 }
609 out = current
610 break
611 }
612 case "Repetition":
613 out = repetitionLengths(node, possibleLengths(node.node, limit, cache), limit)
614 break
615 }
616 cache.set(node, out)
617 return out
618}
619
620function sequenceSuffixLengths(
621 nodes: ReadonlyArray<Node>,
622 length: number,
623 cache: LengthCache
624): ReadonlyArray<Lengths> {
625 const out = new Array<Lengths>(nodes.length + 1)
626 const terminal = emptyLengths(length)
627 terminal[0] = true
628 out[nodes.length] = terminal
629 for (let index = nodes.length - 1; index >= 0; index--) {
630 out[index] = concatenateLengths(
631 possibleLengths(nodes[index], length, cache),
632 out[index + 1],
633 length
634 )
635 }
636 return out
637}
638
639function generateSequence(
640 nodes: ReadonlyArray<Node>,
641 length: number,
642 state: Model.GenerationState,
643 cache: LengthCache
644): string | undefined {
645 const suffixLengths = sequenceSuffixLengths(nodes, length, cache)
646 let remaining = length
647 let out = ""
648 for (let index = 0; index < nodes.length; index++) {
649 const node = nodes[index]
650 const nodeLengths = possibleLengths(node, remaining, cache)
651 const tailLengths = suffixLengths[index + 1]
652 const candidates: Array<number> = []
653 for (let nodeLength = 0; nodeLength <= remaining; nodeLength++) {
654 if (nodeLengths[nodeLength] && tailLengths[remaining - nodeLength]) candidates.push(nodeLength)
655 }
656 if (candidates.length === 0) return undefined
657 const nodeLength = candidates[Model.randomIndex(state, candidates.length)]
658 const value = generateExact(node, nodeLength, state, cache)
659 if (value === undefined) return undefined
660 out += value
661 remaining -= nodeLength
662 }
663 return remaining === 0 ? out : undefined
664}
665
666function repetitionCounts(node: Repetition, length: number, cache: LengthCache): ReadonlyArray<number> {
667 const child = possibleLengths(node.node, length, cache)
668 const nullable = child[0] === true
669 let smallestPositive = 1
670 while (smallestPositive <= length && child[smallestPositive] !== true) smallestPositive++
671 const relevant = smallestPositive > length ? 0 : Math.floor(length / smallestPositive)
672 const minimum = nullable ? 0 : node.minimum
673 const maximum = Math.min(node.maximum ?? relevant, relevant)
674 if (minimum > maximum) return []
675 const counts: Array<number> = []
676 let current = emptyLengths(length)
677 current[0] = true
678 for (let count = 0; count <= maximum; count++) {
679 if (count >= minimum && current[length]) counts.push(count)
680 if (count < maximum) current = concatenateLengths(current, child, length)
681 }
682 return counts
683}
684
685function generateExact(
686 node: Node,
687 length: number,
688 state: Model.GenerationState,
689 cache: LengthCache
690): string | undefined {
691 switch (node._tag) {
692 case "Literal":
693 return node.value.length === length ? node.value : undefined
694 case "Character":
695 return generateCharacter(node, length, state)
696 case "Alternation": {
697 const candidates = node.nodes.filter((child) => possibleLengths(child, length, cache)[length])
698 return candidates.length === 0
699 ? undefined
700 : generateExact(candidates[Model.randomIndex(state, candidates.length)], length, state, cache)
701 }
702 case "Concatenation":
703 return generateSequence(node.nodes, length, state, cache)
704 case "Repetition": {
705 const counts = repetitionCounts(node, length, cache)
706 if (counts.length === 0) return undefined
707 const count = counts[Model.randomIndex(state, counts.length)]
708 return generateSequence(globalThis.Array(count).fill(node.node), length, state, cache)
709 }
710 }
711}
712
713function canonicalSequence(nodes: ReadonlyArray<Node>, length: number, cache: LengthCache): string | undefined {
714 const suffixLengths = sequenceSuffixLengths(nodes, length, cache)
715 let remaining = length
716 let out = ""
717 for (let index = 0; index < nodes.length; index++) {
718 const node = nodes[index]
719 const nodeLengths = possibleLengths(node, remaining, cache)
720 const tailLengths = suffixLengths[index + 1]
721 let nodeLength = 0
722 while (nodeLength <= remaining && !(nodeLengths[nodeLength] && tailLengths[remaining - nodeLength])) nodeLength++
723 if (nodeLength > remaining) return undefined
724 const value = canonicalExact(node, nodeLength, cache)
725 if (value === undefined) return undefined
726 out += value
727 remaining -= nodeLength
728 }
729 return remaining === 0 ? out : undefined
730}
731
732function canonicalExact(node: Node, length: number, cache: LengthCache): string | undefined {
733 switch (node._tag) {
734 case "Literal":
735 return node.value.length === length ? node.value : undefined
736 case "Character":
737 return canonicalCharacter(node, length)
738 case "Alternation": {
739 const child = node.nodes.find((child) => possibleLengths(child, length, cache)[length])
740 return child === undefined ? undefined : canonicalExact(child, length, cache)
741 }
742 case "Concatenation":
743 return canonicalSequence(node.nodes, length, cache)
744 case "Repetition": {
745 const count = repetitionCounts(node, length, cache)[0]
746 return count === undefined
747 ? undefined
748 : canonicalSequence(globalThis.Array(count).fill(node.node), length, cache)
749 }
750 }
751}
752
753function structuralShrinks(
754 node: Node,
755 regExp: globalThis.RegExp,
756 value: string,
757 minimumLength: number,
758 cache: LengthCache
759): ReadonlyArray<string> {
760 const lengths = possibleLengths(node, value.length, cache)
761 const smaller: Array<number> = []
762 for (let length = minimumLength; length < value.length; length++) {
763 if (lengths[length]) smaller.push(length)
764 }
765 const candidates: Array<number> = []
766 if (smaller.length > 0) {
767 candidates.push(smaller[0], smaller[Math.floor((smaller.length - 1) / 2)], smaller[smaller.length - 1])
768 }
769 candidates.push(value.length)
770 const out: Array<string> = []
771 for (const length of candidates) {
772 const candidate = canonicalExact(node, length, cache)
773 if (candidate !== undefined && candidate !== value && !out.includes(candidate) && test(regExp, candidate)) {
774 out.push(candidate)
775 }
776 }
777 return out
778}
779
780function minimumLength(node: Node): number {
781 switch (node._tag) {
782 case "Literal":
783 return node.value.length
784 case "Character":
785 return node.intervals.length === 0 ? Number.POSITIVE_INFINITY : node.intervals[0].minimum > 0xffff ? 2 : 1
786 case "Alternation":
787 return Math.min(...node.nodes.map(minimumLength))
788 case "Concatenation":
789 return node.nodes.reduce((sum, child) => sum + minimumLength(child), 0)
790 case "Repetition":
791 return minimumLength(node.node) * node.minimum
792 }
793}
794
795function test(regExp: RegExp, value: string): boolean {
796 regExp.lastIndex = 0
797 return regExp.test(value)
798}
799
800function hasTrailingAnchor(source: string): boolean {
801 if (!source.endsWith("$")) return false
802 let backslashes = 0
803 for (let index = source.length - 2; index >= 0 && source[index] === "\\"; index--) backslashes++
804 return backslashes % 2 === 0
805}
806
807function addUnanchoredSurroundings(node: Node, source: string, flags: string): Node {
808 const nodes: Array<Node> = []
809 const anyCharacters: Repetition = {
810 _tag: "Repetition",
811 node: character(printableAsciiIntervals),
812 minimum: 0,
813 maximum: undefined
814 }
815 if (!flags.includes("y") && !source.startsWith("^")) nodes.push(anyCharacters)
816 nodes.push(node)
817 if (!hasTrailingAnchor(source)) nodes.push(anyCharacters)
818 return concatenation(nodes)
819}
820
821/**
822 * The private regular-expression AST and its structural translation into generators follow the broad strategy used by
823 * fast-check v4.9.0's `stringMatching` arbitrary (MIT). This implementation uses Effect's generation state and an
824 * exact UTF-16 length analysis; no fast-check parser or arbitrary is included.
825 * https://github.com/dubzzz/fast-check/blob/v4.9.0/packages/fast-check/src/arbitrary/stringMatching.ts
826 */
827/** @internal */
828export function compile(pattern: Pattern): Compiled | undefined {
829 const { flags, source } = pattern
830 // Case folding, multiline assertions, and Unicode sets require dedicated AST semantics. Falling back preserves the
831 // contract that a constructively supported pattern never silently ignores one of its flags.
832 if (flags.includes("i") || flags.includes("m") || flags.includes("v")) return undefined
833 const parsed = new Parser(source, flags.includes("s")).parse()
834 if (parsed === undefined) return undefined
835 const restricted = flags.includes("u") ? parsed : restrictCharacterCodePoints(parsed, 0xffff)
836 const node = addUnanchoredSurroundings(restricted, source, flags)
837 const regExp = new globalThis.RegExp(source, flags)
838 const minimum = minimumLength(node)
839 const cache: LengthCache = new Map()
840 return {
841 minimumLength: minimum,
842 generate: (state, minimumLength, maximumLength) => {
843 const lengths = possibleLengths(node, maximumLength, cache)
844 const candidates: Array<number> = []
845 for (let length = minimumLength; length <= maximumLength; length++) {
846 if (lengths[length]) candidates.push(length)
847 }
848 if (candidates.length === 0) return undefined
849 const offset = Model.randomLength(state, 0, candidates.length - 1)
850 const value = generateExact(node, candidates[offset], state, cache)
851 return value !== undefined && test(regExp, value) ? value : undefined
852 },
853 shrink: (value, minimumLength) => structuralShrinks(node, regExp, value, minimumLength, cache)
854 }
855}