1	# Pure generators: each takes a Rand.Rng and returns a value beside the next state.
2	import Base
3	# bend-kit-random@0.1.0.0
4	import bend-kit-random@0.1.0.0/random.bend as Rand
5	# bend-kit-bytes@0.3.1.0
6	import bend-kit-bytes@0.3.1.0/bytes.bend as Bytes
7	
8	# A generator is `Rand.Rng -> T & Rand.Rng`. The same seed replays the same value:
9	#   (xs, r) = Gen.list(~U32, ~Gen.u32, 8, Rand.seed(42))
10	# Sizes are capped at 1024 so lengths and Nats stay small enough to build and shrink.
11	
12	# n, capped at 1024.
13	def cap(+n: U32) -> U32:
14	  U32.min(n, 1024)
15	
16	# A uniform U32.
17	def u32(r: Rand.Rng) -> U32 & Rand.Rng:
18	  Rand.next(r)
19	
20	# A uniform U32 in [lo, hi); lo when hi <= lo + 1.
21	def u32.range(+lo: U32, hi: U32, r: Rand.Rng) -> U32 & Rand.Rng:
22	  Rand.range(lo, hi, r)
23	
24	# A uniform size in [0, min(max, 1024)].
25	def size(+max: U32, r: Rand.Rng) -> U32 & Rand.Rng:
26	  Rand.below((cap(max) + 1 : U32), r)
27	
28	def nat.fin(xr: U32 & Rand.Rng) -> Nat & Rand.Rng:
29	  (x, r) = xr
30	  (U32.to_nat(x), r)
31	
32	# A uniform Nat in [0, min(max, 1024)].
33	def nat(+max: U32, r: Rand.Rng) -> Nat & Rand.Rng:
34	  nat.fin(size(max, r))
35	
36	def char.fin(xr: U32 & Rand.Rng) -> Char & Rand.Rng:
37	  (x, r) = xr
38	  (Chr{x}, r)
39	
40	# A printable ASCII char, ' ' (32) through '~' (126).
41	def char(r: Rand.Rng) -> Char & Rand.Rng:
42	  char.fin(Rand.range(32, 127, r))
43	
44	# n + 1 chars prepended to acc; cr holds the next char.
45	def string.go(n: Nat, acc: String, cr: Char & Rand.Rng) -> String & Rand.Rng:
46	  match n:
47	    case 0n:
48	      (c, r) = cr
49	      (SCon{c, acc}, r)
50	    case 1n+p:
51	      (c, r) = cr
52	      string.go(p, SCon{c, acc}, char(r))
53	
54	# Exactly n printable ASCII chars.
55	def string.of(n: Nat, r: Rand.Rng) -> String & Rand.Rng:
56	  match n:
57	    case 0n:
58	      (SNil{}, r)
59	    case 1n+p:
60	      string.go(p, SNil{}, char(r))
61	
62	def string.fin(nr: Nat & Rand.Rng) -> String & Rand.Rng:
63	  (n, r) = nr
64	  string.of(n, r)
65	
66	# Printable ASCII of length in [0, min(max, 1024)].
67	def string(+max: U32, r: Rand.Rng) -> String & Rand.Rng:
68	  string.fin(nat(max, r))
69	
70	# Byte i and the n bytes after it; xr holds byte i (Bytes.set keeps its low 8 bits).
71	def bytes.go(n: Nat, b: Bytes.Bytes, +i: U32, xr: U32 & Rand.Rng) -> Bytes.Bytes & Rand.Rng:
72	  match n:
73	    case 0n:
74	      (x, r) = xr
75	      (Bytes.set(b, i, x), r)
76	    case 1n+p:
77	      (x, r) = xr
78	      bytes.go(p, Bytes.set(b, i, x), (i + 1 : U32), Rand.next(r))
79	
80	def bytes.start(n: Nat, +len: U32, r: Rand.Rng) -> Bytes.Bytes & Rand.Rng:
81	  match n:
82	    case 0n:
83	      (Bytes.new(0), r)
84	    case 1n+p:
85	      bytes.go(p, Bytes.new(len), 0, Rand.next(r))
86	
87	# Exactly min(len, 1024) uniform octets, one draw each.
88	def bytes.of(+len: U32, r: Rand.Rng) -> Bytes.Bytes & Rand.Rng:
89	  +n = cap(len)
90	  bytes.start(U32.to_nat(n), n, r)
91	
92	def bytes.fin(nr: U32 & Rand.Rng) -> Bytes.Bytes & Rand.Rng:
93	  (n, r) = nr
94	  bytes.of(n, r)
95	
96	# Uniform octets, length in [0, min(max, 1024)].
97	def bytes(+max: U32, r: Rand.Rng) -> Bytes.Bytes & Rand.Rng:
98	  bytes.fin(size(max, r))
99	
100	# n + 1 items prepended to acc; hr holds the next item.
101	def list.go(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, n: Nat, acc: List<&2, T>, hr: T & Rand.Rng) -> List<&2, T> & Rand.Rng:
102	  match n:
103	    case 0n:
104	      (h, r) = hr
105	      (h <> acc, r)
106	    case 1n+p:
107	      (h, r) = hr
108	      list.go(~T, ~gen, p, h <> acc, gen(r))
109	
110	# Exactly n items from gen. The first draw ends up last; replay is unaffected.
111	def list.of(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, n: Nat, r: Rand.Rng) -> List<&2, T> & Rand.Rng:
112	  match n:
113	    case 0n:
114	      (Nil{}, r)
115	    case 1n+p:
116	      list.go(~T, ~gen, p, Nil{}, gen(r))
117	
118	def list.fin(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, nr: Nat & Rand.Rng) -> List<&2, T> & Rand.Rng:
119	  (n, r) = nr
120	  list.of(~T, ~gen, n, r)
121	
122	# Items from gen, length in [0, min(max, 1024)].
123	def list(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, +max: U32, r: Rand.Rng) -> List<&2, T> & Rand.Rng:
124	  list.fin(~T, ~gen, nat(max, r))
125	
126	def maybe.some(~T: Data, hr: T & Rand.Rng) -> Maybe<&2, T> & Rand.Rng:
127	  (h, r) = hr
128	  (Some{h}, r)
129	
130	def maybe.if(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, none: Bool, r: Rand.Rng) -> Maybe<&2, T> & Rand.Rng:
131	  match none:
132	    case True{}:
133	      (None{}, r)
134	    case False{}:
135	      maybe.some(~T, gen(r))
136	
137	def maybe.pick(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, xr: U32 & Rand.Rng) -> Maybe<&2, T> & Rand.Rng:
138	  (+x, r) = xr
139	  maybe.if(~T, ~gen, U32.is_eq(x, 0), r)
140	
141	# None one time in four, else Some from gen.
142	def maybe(~T: Data, ~gen: Rand.Rng -> T & Rand.Rng, r: Rand.Rng) -> Maybe<&2, T> & Rand.Rng:
143	  maybe.pick(~T, ~gen, Rand.below(4, r))
144	
145	def map.fin(~A: Type, ~B: Type, ~f: A -> B, ar: A & Rand.Rng) -> B & Rand.Rng:
146	  (a, r) = ar
147	  (f(a), r)
148	
149	# gen's value through f.
150	def map(~A: Type, ~B: Type, ~f: A -> B, ~gen: Rand.Rng -> A & Rand.Rng, r: Rand.Rng) -> B & Rand.Rng:
151	  map.fin(~A, ~B, ~f, gen(r))
152	
153	def bind.fin(~A: Type, ~B: Type, ~k: A -> Rand.Rng -> B & Rand.Rng, ar: A & Rand.Rng) -> B & Rand.Rng:
154	  (a, r) = ar
155	  k(a, r)
156	
157	# gen's value picks the next generator: bind(~Nat, ~List<&2, U32>, ~(r => Gen.nat(8, r)), ~(n => r => Gen.list.of(~U32, ~Gen.u32, n, r)), r).
158	def bind(~A: Type, ~B: Type, ~gen: Rand.Rng -> A & Rand.Rng, ~k: A -> Rand.Rng -> B & Rand.Rng, r: Rand.Rng) -> B & Rand.Rng:
159	  bind.fin(~A, ~B, ~k, gen(r))
160	
161	def pair.snd(~A: Type, ~B: Type, a: A, br: B & Rand.Rng) -> (A & B) & Rand.Rng:
162	  (b, r) = br
163	  ((a, b), r)
164	
165	def pair.fst(~A: Type, ~B: Type, ~gb: Rand.Rng -> B & Rand.Rng, ar: A & Rand.Rng) -> (A & B) & Rand.Rng:
166	  (a, r) = ar
167	  pair.snd(~A, ~B, a, gb(r))
168	
169	# ga's value then gb's, drawn in that order.
170	def pair(~A: Type, ~B: Type, ~ga: Rand.Rng -> A & Rand.Rng, ~gb: Rand.Rng -> B & Rand.Rng, r: Rand.Rng) -> (A & B) & Rand.Rng:
171	  pair.fst(~A, ~B, ~gb, ga(r))