1	# Linear-time regular expressions: RE2 syntax, Pike VM, capture groups. Source: https://github.com/paymog/bend-kit/tree/main/regex
2	import Base
3	import 0x6c784a08486e2e02415e89c5249e9e8a/unicode.bend as U
4	
5	# Positions count code points of the String, not octets.
6	# Leftmost-first semantics, as RE2 and Perl: the first alternative that matches wins.
7	
8	# Syntax
9	# ------
10	
11	# A set member: a code point range, or a Unicode general category ("L", "Lu", ...).
12	type Item is Data:
13	  Rng{lo: U32, hi: U32}
14	  Prop{neg: Bool, name: String}
15	
16	# Assertion kinds: 0 start of text, 1 end of text, 2 word boundary, 3 not a word boundary.
17	type Node is Data:
18	  NEmpty{}
19	  NSet{neg: Bool, items: List<&2, Item>}
20	  NAssert{k: U32}
21	  NCat{a: Node, b: Node}
22	  NAlt{a: Node, b: Node}
23	  NPlus{greedy: Bool, a: Node}
24	  NQuest{greedy: Bool, a: Node}
25	  NGroup{i: U32, a: Node}
26	
27	type Tok is Data:
28	  TAtom{n: Node}
29	  TOpen{cap: Bool}
30	  TClose{}
31	  TBar{}
32	  TRep{min: U32, max: Maybe<&2, U32>, greedy: Bool}
33	
34	def lit(+c: U32) -> Node:
35	  NSet{False{}, [Rng{c, c}]}
36	
37	def is_digit(+c: U32) -> Bool:
38	  U32.is_le(48, c) && U32.is_le(c, 57)
39	
40	def is_word(+c: U32) -> Bool:
41	  is_digit(c) || (U32.is_le(65, c) && U32.is_le(c, 90)) || (U32.is_le(97, c) && U32.is_le(c, 122)) || U32.is_eq(c, 95)
42	
43	def is_alnum(+c: U32) -> Bool:
44	  Bool.and(is_word(c), U32.is_ne(c, 95))
45	
46	# \d \w \s are ASCII, as in RE2.
47	def perl.d() -> List<&2, Item>:
48	  [Rng{48, 57}]
49	
50	def perl.D() -> List<&2, Item>:
51	  [Rng{0, 47}, Rng{58, 1114111}]
52	
53	def perl.w() -> List<&2, Item>:
54	  [Rng{48, 57}, Rng{65, 90}, Rng{95, 95}, Rng{97, 122}]
55	
56	def perl.W() -> List<&2, Item>:
57	  [Rng{0, 47}, Rng{58, 64}, Rng{91, 94}, Rng{96, 96}, Rng{123, 1114111}]
58	
59	def perl.s() -> List<&2, Item>:
60	  [Rng{9, 10}, Rng{12, 13}, Rng{32, 32}]
61	
62	def perl.S() -> List<&2, Item>:
63	  [Rng{0, 8}, Rng{11, 11}, Rng{14, 31}, Rng{33, 1114111}]
64	
65	def cats() -> List<&2, String>:
66	  ["L", "Lu", "Ll", "Lt", "Lm", "Lo", "M", "Mn", "Mc", "Me", "N", "Nd", "Nl", "No",
67	   "P", "Pc", "Pd", "Ps", "Pe", "Pi", "Pf", "Po", "S", "Sm", "Sc", "Sk", "So",
68	   "Z", "Zs", "Zl", "Zp", "C", "Cc", "Cf", "Cs", "Co", "Cn"]
69	
70	# Escapes
71	# -------
72	
73	type Esc is Data:
74	  EPoint{c: U32, rest: String}
75	  EItems{items: List<&2, Item>, rest: String}
76	  EAssert{k: U32, rest: String}
77	  EBad{}
78	
79	def prop.if(ok: Bool, neg: Bool, name: String, t: String) -> Esc:
80	  match ok:
81	    case True{}:
82	      EItems{[Prop{neg, name}], t}
83	    case False{}:
84	      EBad{}
85	
86	def prop.ok(neg: Bool, +name: String, t: String) -> Esc:
87	  prop.if(List.contains(~String, ~String.eq, cats(), name), neg, name, t)
88	
89	def prop.name(s: String, neg: Bool, acc: String) -> Esc:
90	  match s:
91	    case SNil{}:
92	      EBad{}
93	    case SCon{'}', t}:
94	      prop.ok(neg, String.reverse(acc), t)
95	    case SCon{c, t}:
96	      prop.name(t, neg, SCon{c, acc})
97	
98	# \pL or \p{Lu}; \P negates.
99	def prop(neg: Bool, s: String) -> Esc:
100	  match s:
101	    case SNil{}:
102	      EBad{}
103	    case SCon{'{', t}:
104	      prop.name(t, neg, SNil{})
105	    case SCon{c, t}:
106	      prop.ok(neg, SCon{c, SNil{}}, t)
107	
108	# An escaped letter or digit with no meaning is an error, as in RE2.
109	def esc.other(alnum: Bool, +c: U32, t: String) -> Esc:
110	  match alnum:
111	    case True{}:
112	      EBad{}
113	    case False{}:
114	      EPoint{c, t}
115	
116	# The text after a backslash.
117	def esc(s: String) -> Esc:
118	  match s:
119	    case SNil{}:
120	      EBad{}
121	    case SCon{'d', t}:
122	      EItems{perl.d(), t}
123	    case SCon{'D', t}:
124	      EItems{perl.D(), t}
125	    case SCon{'w', t}:
126	      EItems{perl.w(), t}
127	    case SCon{'W', t}:
128	      EItems{perl.W(), t}
129	    case SCon{'s', t}:
130	      EItems{perl.s(), t}
131	    case SCon{'S', t}:
132	      EItems{perl.S(), t}
133	    case SCon{'p', t}:
134	      prop(False{}, t)
135	    case SCon{'P', t}:
136	      prop(True{}, t)
137	    case SCon{'A', t}:
138	      EAssert{0, t}
139	    case SCon{'z', t}:
140	      EAssert{1, t}
141	    case SCon{'b', t}:
142	      EAssert{2, t}
143	    case SCon{'B', t}:
144	      EAssert{3, t}
145	    case SCon{'n', t}:
146	      EPoint{10, t}
147	    case SCon{'t', t}:
148	      EPoint{9, t}
149	    case SCon{'r', t}:
150	      EPoint{13, t}
151	    case SCon{'f', t}:
152	      EPoint{12, t}
153	    case SCon{'v', t}:
154	      EPoint{11, t}
155	    case SCon{Chr{+c}, t}:
156	      esc.other(is_alnum(c), c, t)
157	
158	# Classes
159	# -------
160	
161	type Cs is Data:
162	  CsGo{s: String, first: Bool, items: List<&2, Item>}
163	  CsDone{items: List<&2, Item>, rest: String}
164	  CsFail{}
165	
166	def class.range(ok: Bool, +c: U32, +d: U32, u: String, items: List<&2, Item>) -> Cs:
167	  match ok:
168	    case True{}:
169	      CsGo{u, False{}, Rng{c, d} <> items}
170	    case False{}:
171	      CsFail{}
172	
173	def class.hi(e: Esc, +c: U32, items: List<&2, Item>) -> Cs:
174	  match e:
175	    case EPoint{+d, u}:
176	      class.range(U32.is_le(c, d), c, d, u, items)
177	    case EItems{xs, u}:
178	      CsFail{}
179	    case EAssert{k, u}:
180	      CsFail{}
181	    case EBad{}:
182	      CsFail{}
183	
184	# c is one member; a "-" and a code point after it make a range.
185	def class.lo(+c: U32, t: String, items: List<&2, Item>) -> Cs:
186	  match t:
187	    case SCon{'-', SCon{']', u}}:
188	      CsDone{Rng{45, 45} <> Rng{c, c} <> items, u}
189	    case SCon{'-', SCon{'\\', u}}:
190	      class.hi(esc(u), c, items)
191	    case SCon{'-', SCon{Chr{+d}, u}}:
192	      class.range(U32.is_le(c, d), c, d, u, items)
193	    case _:
194	      CsGo{t, False{}, Rng{c, c} <> items}
195	
196	def class.esc(e: Esc, items: List<&2, Item>) -> Cs:
197	  match e:
198	    case EPoint{+c, t}:
199	      class.lo(c, t, items)
200	    case EItems{xs, t}:
201	      CsGo{t, False{}, List.append(&2, Item, xs, items)}
202	    case EAssert{k, t}:
203	      CsFail{}
204	    case EBad{}:
205	      CsFail{}
206	
207	# A "]" right after "[" or "[^" is a member.
208	def class.step(s: String, first: Bool, items: List<&2, Item>) -> Cs:
209	  match s:
210	    case SNil{}:
211	      CsFail{}
212	    case SCon{']', t}:
213	      match first:
214	        case True{}:
215	          class.lo(93, t, items)
216	        case False{}:
217	          CsDone{items, t}
218	    case SCon{'\\', t}:
219	      class.esc(esc(t), items)
220	    case SCon{Chr{+c}, t}:
221	      class.lo(c, t, items)
222	
223	# fuel: every step eats at least one char.
224	def class.run(fuel: Nat, st: Cs) -> Cs:
225	  match fuel:
226	    case 0n:
227	      CsFail{}
228	    case 1n+f:
229	      match st:
230	        case CsGo{s, first, items}:
231	          class.run(f, class.step(s, first, items))
232	        case CsDone{items, rest}:
233	          CsDone{items, rest}
234	        case CsFail{}:
235	          CsFail{}
236	
237	def class(+s: String, first: Bool) -> Cs:
238	  class.run(Nat.add(String.length(s), 1n), CsGo{s, first, Nil{}})
239	
240	# Lexer
241	# -----
242	
243	type Lx is Data:
244	  LGo{s: String, toks: List<&2, Tok>}
245	  LDone{toks: List<&2, Tok>}
246	  LFail{}
247	
248	# A run of decimal digits: its value (capped at 100000), its length, and the rest.
249	type Num is Data:
250	  Num{v: U32, n: U32, rest: String}
251	
252	def num.add(+acc: U32, +c: U32) -> U32:
253	  Bool.pick(U32, U32.is_lt(acc, 100000), (acc * 10 + (c - 48) : U32), 100000)
254	
255	def num.go(t: String, +c: U32, +acc: U32, +n: U32, dig: Bool) -> Num:
256	  match t:
257	    case SNil{}:
258	      match dig:
259	        case True{}:
260	          Num{num.add(acc, c), (n + 1 : U32), SNil{}}
261	        case False{}:
262	          Num{acc, n, SCon{Chr{c}, SNil{}}}
263	    case SCon{Chr{+d}, u}:
264	      match dig:
265	        case True{}:
266	          num.go(u, d, num.add(acc, c), (n + 1 : U32), is_digit(d))
267	        case False{}:
268	          Num{acc, n, SCon{Chr{c}, SCon{Chr{d}, u}}}
269	
270	def num(s: String) -> Num:
271	  match s:
272	    case SNil{}:
273	      Num{0, 0, SNil{}}
274	    case SCon{Chr{+c}, t}:
275	      num.go(t, c, 0, 0, is_digit(c))
276	
277	# A trailing "?" makes a repetition lazy.
278	def lex.rep(+min: U32, max: Maybe<&2, U32>, t: String, toks: List<&2, Tok>) -> Lx:
279	  match t:
280	    case SCon{'?', u}:
281	      LGo{u, TRep{min, max, False{}} <> toks}
282	    case _:
283	      LGo{t, TRep{min, max, True{}} <> toks}
284	
285	def Num.n(m: Num) -> U32:
286	  Num{v, n, r} = m
287	  n
288	
289	# A "{" that does not start {n}, {n,} or {n,m} is a literal, as in RE2.
290	def lex.brace.max(none: Bool, +min: U32, m: Num, orig: String, toks: List<&2, Tok>) -> Lx:
291	  match none:
292	    case True{}:
293	      LGo{orig, TAtom{lit(123)} <> toks}
294	    case False{}:
295	      Num{+v, n, r} = m
296	      match r:
297	        case SCon{'}', u}:
298	          lex.rep(min, Some{v}, u, toks)
299	        case _:
300	          LGo{orig, TAtom{lit(123)} <> toks}
301	
302	def lex.brace.min(none: Bool, m: Num, +orig: String, toks: List<&2, Tok>) -> Lx:
303	  match none:
304	    case True{}:
305	      LGo{orig, TAtom{lit(123)} <> toks}
306	    case False{}:
307	      Num{+v, n, r} = m
308	      match r:
309	        case SCon{'}', u}:
310	          lex.rep(v, Some{v}, u, toks)
311	        case SCon{',', SCon{'}', u}}:
312	          lex.rep(v, None{}, u, toks)
313	        case SCon{',', u}:
314	          +m2 = num(u)
315	          lex.brace.max(U32.is_eq(Num.n(m2), 0), v, m2, orig, toks)
316	        case _:
317	          LGo{orig, TAtom{lit(123)} <> toks}
318	
319	def lex.class(neg: Bool, r: Cs, toks: List<&2, Tok>) -> Lx:
320	  match r:
321	    case CsDone{items, rest}:
322	      LGo{rest, TAtom{NSet{neg, items}} <> toks}
323	    case CsGo{s, first, items}:
324	      LFail{}
325	    case CsFail{}:
326	      LFail{}
327	
328	def lex.esc(e: Esc, toks: List<&2, Tok>) -> Lx:
329	  match e:
330	    case EPoint{c, t}:
331	      LGo{t, TAtom{lit(c)} <> toks}
332	    case EItems{xs, t}:
333	      LGo{t, TAtom{NSet{False{}, xs}} <> toks}
334	    case EAssert{k, t}:
335	      LGo{t, TAtom{NAssert{k}} <> toks}
336	    case EBad{}:
337	      LFail{}
338	
339	def lex.step(s: String, toks: List<&2, Tok>) -> Lx:
340	  match s:
341	    case SNil{}:
342	      LDone{toks}
343	    case SCon{'\\', t}:
344	      lex.esc(esc(t), toks)
345	    case SCon{'[', SCon{'^', t}}:
346	      lex.class(True{}, class(t, True{}), toks)
347	    case SCon{'[', t}:
348	      lex.class(False{}, class(t, True{}), toks)
349	    case SCon{'(', SCon{'?', SCon{':', t}}}:
350	      LGo{t, TOpen{False{}} <> toks}
351	    case SCon{'(', SCon{'?', t}}:
352	      LFail{}
353	    case SCon{'(', t}:
354	      LGo{t, TOpen{True{}} <> toks}
355	    case SCon{')', t}:
356	      LGo{t, TClose{} <> toks}
357	    case SCon{'|', t}:
358	      LGo{t, TBar{} <> toks}
359	    case SCon{'*', t}:
360	      lex.rep(0, None{}, t, toks)
361	    case SCon{'+', t}:
362	      lex.rep(1, None{}, t, toks)
363	    case SCon{'?', t}:
364	      lex.rep(0, Some{1}, t, toks)
365	    case SCon{'{', +t}:
366	      +m = num(t)
367	      lex.brace.min(U32.is_eq(Num.n(m), 0), m, t, toks)
368	    case SCon{'.', t}:
369	      LGo{t, TAtom{NSet{True{}, [Rng{10, 10}]}} <> toks}
370	    case SCon{'^', t}:
371	      LGo{t, TAtom{NAssert{0}} <> toks}
372	    case SCon{'$', t}:
373	      LGo{t, TAtom{NAssert{1}} <> toks}
374	    case SCon{Chr{+c}, t}:
375	      LGo{t, TAtom{lit(c)} <> toks}
376	
377	# fuel: every step but the last eats at least one char.
378	def lex(fuel: Nat, st: Lx) -> Maybe<&2, List<&2, Tok>>:
379	  match fuel:
380	    case 0n:
381	      None{}
382	    case 1n+f:
383	      match st:
384	        case LGo{s, toks}:
385	          lex(f, lex.step(s, toks))
386	        case LDone{toks}:
387	          Some{List.reverse(&2, Tok, toks)}
388	        case LFail{}:
389	          None{}
390	
391	# Parser
392	# ------
393	
394	# An open group: its capture index (None for (?:...)), and the enclosing alternatives and sequence.
395	type Frame is Data:
396	  Frame{cap: Maybe<&2, U32>, alts: List<&2, Node>, cur: List<&2, Node>}
397	
398	# n: the next capture index. rep: the last token was a repetition. alts and cur are reversed.
399	type Ps is Data:
400	  Ps{n: U32, rep: Bool, stack: List<&2, Frame>, alts: List<&2, Node>, cur: List<&2, Node>}
401	  PsFail{}
402	def cat(a: Node, b: Node) -> Node:
403	  match a:
404	    case NEmpty{}:
405	      b
406	    case _:
407	      match b:
408	        case NEmpty{}:
409	          a
410	        case _:
411	          NCat{a, b}
412	
413	def seq.go(xs: List<&2, Node>, acc: Node) -> Node:
414	  match xs:
415	    case Nil{}:
416	      acc
417	    case Con{h, t}:
418	      seq.go(t, cat(h, acc))
419	
420	def seq(xs: List<&2, Node>) -> Node:
421	  seq.go(xs, NEmpty{})
422	
423	def alt.go(xs: List<&2, Node>, acc: Node) -> Node:
424	  match xs:
425	    case Nil{}:
426	      acc
427	    case Con{h, t}:
428	      alt.go(t, NAlt{h, acc})
429	
430	def group(cap: Maybe<&2, U32>, a: Node) -> Node:
431	  match cap:
432	    case None{}:
433	      a
434	    case Some{i}:
435	      NGroup{i, a}
436	
437	def rep.copies(k: Nat, +h: Node, acc: Node) -> Node:
438	  match k:
439	    case 0n:
440	      acc
441	    case 1n+p:
442	      rep.copies(p, h, cat(h, acc))
443	
444	def rep.opt(k: Nat, +g: Bool, +h: Node) -> Node:
445	  match k:
446	    case 0n:
447	      NEmpty{}
448	    case 1n+p:
449	      NQuest{g, cat(h, rep.opt(p, g, h))}
450	
451	# x* is (x+)?, so an empty x cannot loop; x{n,} is n-1 copies then x+; x{n,m} is n copies then (x(x...)?)?, as RE2 builds them.
452	def rep.inf(k: Nat, +g: Bool, +h: Node) -> Node:
453	  match k:
454	    case 0n:
455	      NQuest{g, NPlus{g, h}}
456	    case 1n+p:
457	      rep.copies(p, h, NPlus{g, h})
458	
459	def rep.fin(max: Maybe<&2, U32>, +min: U32, +g: Bool, +h: Node) -> Node:
460	  match max:
461	    case None{}:
462	      rep.inf(U32.to_nat(min), g, h)
463	    case Some{m}:
464	      rep.copies(U32.to_nat(min), h, rep.opt(U32.to_nat((m - min : U32)), g, h))
465	
466	def rep(+h: Node, +min: U32, max: Maybe<&2, U32>, +g: Bool) -> Node:
467	  rep.fin(max, min, g, h)
468	
469	# Counts go up to 1000, and a repetition cannot repeat, as in RE2.
470	def rep.ok(+min: U32, max: Maybe<&2, U32>) -> Bool:
471	  match max:
472	    case None{}:
473	      U32.is_le(min, 1000)
474	    case Some{+m}:
475	      U32.is_le(m, 1000) && U32.is_le(min, m)
476	
477	def parse.rep(ok: Bool, cur: List<&2, Node>, +min: U32, max: Maybe<&2, U32>, +g: Bool, +n: U32, stack: List<&2, Frame>, alts: List<&2, Node>) -> Ps:
478	  match ok:
479	    case False{}:
480	      PsFail{}
481	    case True{}:
482	      match cur:
483	        case Nil{}:
484	          PsFail{}
485	        case Con{h, t}:
486	          Ps{n, True{}, stack, alts, rep(h, min, max, g) <> t}
487	
488	def parse.open(cap: Bool, +n: U32, stack: List<&2, Frame>, alts: List<&2, Node>, cur: List<&2, Node>) -> Ps:
489	  match cap:
490	    case True{}:
491	      Ps{(n + 1 : U32), False{}, Frame{Some{n}, alts, cur} <> stack, Nil{}, Nil{}}
492	    case False{}:
493	      Ps{n, False{}, Frame{None{}, alts, cur} <> stack, Nil{}, Nil{}}
494	
495	def parse.close(stack: List<&2, Frame>, +n: U32, alts: List<&2, Node>, cur: List<&2, Node>) -> Ps:
496	  match stack:
497	    case Nil{}:
498	      PsFail{}
499	    case Con{Frame{cap, fa, fc}, up}:
500	      Ps{n, False{}, up, fa, group(cap, alt.go(alts, seq(cur))) <> fc}
501	
502	def parse.tok(tok: Tok, +n: U32, rep: Bool, stack: List<&2, Frame>, alts: List<&2, Node>, cur: List<&2, Node>) -> Ps:
503	  match tok:
504	    case TAtom{a}:
505	      Ps{n, False{}, stack, alts, a <> cur}
506	    case TRep{+min, +max, g}:
507	      parse.rep(Bool.and(Bool.not(rep), rep.ok(min, max)), cur, min, max, g, n, stack, alts)
508	    case TOpen{cap}:
509	      parse.open(cap, n, stack, alts, cur)
510	    case TClose{}:
511	      parse.close(stack, n, alts, cur)
512	    case TBar{}:
513	      Ps{n, False{}, stack, seq(cur) <> alts, Nil{}}
514	
515	def parse.step(st: Ps, tok: Tok) -> Ps:
516	  match st:
517	    case PsFail{}:
518	      PsFail{}
519	    case Ps{n, rep, stack, alts, cur}:
520	      parse.tok(tok, n, rep, stack, alts, cur)
521	
522	def parse(toks: List<&2, Tok>, st: Ps) -> Ps:
523	  match toks:
524	    case Nil{}:
525	      st
526	    case Con{tok, t}:
527	      parse(t, parse.step(st, tok))
528	
529	# Compiler
530	# --------
531	
532	type Inst is Data:
533	  ISet{neg: Bool, items: List<&2, Item>}
534	  IAssert{k: U32}
535	  ISplit{x: U32, y: U32}
536	  IJmp{x: U32}
537	  ISave{k: U32}
538	  IMatch{}
539	
540	def size(n: Node) -> U32:
541	  match n:
542	    case NEmpty{}:
543	      0
544	    case NSet{neg, items}:
545	      1
546	    case NAssert{k}:
547	      1
548	    case NCat{a, b}:
549	      (size(a) + size(b) : U32)
550	    case NAlt{a, b}:
551	      (2 + size(a) + size(b) : U32)
552	    case NPlus{g, a}:
553	      (1 + size(a) : U32)
554	    case NQuest{g, a}:
555	      (1 + size(a) : U32)
556	    case NGroup{i, a}:
557	      (2 + size(a) : U32)
558	
559	# The instructions of n, placed at pc, in front of rest. ISplit tries x first.
560	def emit(n: Node, +pc: U32, rest: List<&2, Inst>) -> List<&2, Inst>:
561	  match n:
562	    case NEmpty{}:
563	      rest
564	    case NSet{neg, items}:
565	      ISet{neg, items} <> rest
566	    case NAssert{k}:
567	      IAssert{k} <> rest
568	    case NCat{+a, b}:
569	      emit(a, pc, emit(b, (pc + size(a) : U32), rest))
570	    case NAlt{+a, +b}:
571	      +j = (pc + 1 + size(a) : U32)
572	      ISplit{(pc + 1 : U32), (j + 1 : U32)} <> emit(a, (pc + 1 : U32), IJmp{(j + 1 + size(b) : U32)} <> emit(b, (j + 1 : U32), rest))
573	    case NPlus{+g, +a}:
574	      +out = (pc + 1 + size(a) : U32)
575	      emit(a, pc, ISplit{Bool.pick(U32, g, pc, out), Bool.pick(U32, g, out, pc)} <> rest)
576	    case NQuest{+g, +a}:
577	      +out = (pc + 1 + size(a) : U32)
578	      ISplit{Bool.pick(U32, g, (pc + 1 : U32), out), Bool.pick(U32, g, out, (pc + 1 : U32))} <> emit(a, (pc + 1 : U32), rest)
579	    case NGroup{+i, a}:
580	      ISave{(2 * i : U32)} <> emit(a, (pc + 1 : U32), ISave{(2 * i + 1 : U32)} <> rest)
581	
582	# A binary trie keyed by n >= 1: the path is the bits of n below its top bit, low bit
583	# first, so key n costs log2(n) steps and small keys stay near the root.
584	type Trie<-V: Data> is Data:
585	  TTip{}
586	  TNode{val: Maybe<&2, V>, lo: Trie<V>, hi: Trie<V>}
587	
588	# here: n is 1. left: n is even.
589	def trie.get(-V: Data, t: Trie<V>, here: Bool, left: Bool, +n: U32) -> Maybe<&2, V>:
590	  match t:
591	    case TTip{}:
592	      None{}
593	    case TNode{v, lo, hi}:
594	      match here:
595	        case True{}:
596	          v
597	        case False{}:
598	          match left:
599	            case True{}:
600	              trie.get(V, lo, U32.is_eq(U32.shr(n), 1), U32.is_even(U32.shr(n)), U32.shr(n))
601	            case False{}:
602	              trie.get(V, hi, U32.is_eq(U32.shr(n), 1), U32.is_even(U32.shr(n)), U32.shr(n))
603	
604	# fuel: a U32 key has at most 32 bits.
605	def trie.put(-V: Data, fuel: Nat, t: Trie<V>, here: Bool, left: Bool, +n: U32, v: V) -> Trie<V>:
606	  match fuel:
607	    case 0n:
608	      t
609	    case 1n+f:
610	      match t:
611	        case TNode{x, lo, hi}:
612	          match here:
613	            case True{}:
614	              TNode{Some{v}, lo, hi}
615	            case False{}:
616	              match left:
617	                case True{}:
618	                  TNode{x, trie.put(V, f, lo, U32.is_eq(U32.shr(n), 1), U32.is_even(U32.shr(n)), U32.shr(n), v), hi}
619	                case False{}:
620	                  TNode{x, lo, trie.put(V, f, hi, U32.is_eq(U32.shr(n), 1), U32.is_even(U32.shr(n)), U32.shr(n), v)}
621	        case TTip{}:
622	          match here:
623	            case True{}:
624	              TNode{Some{v}, TTip{}, TTip{}}
625	            case False{}:
626	              match left:
627	                case True{}:
628	                  TNode{None{}, trie.put(V, f, TTip{}, U32.is_eq(U32.shr(n), 1), U32.is_even(U32.shr(n)), U32.shr(n), v), TTip{}}
629	                case False{}:
630	                  TNode{None{}, TTip{}, trie.put(V, f, TTip{}, U32.is_eq(U32.shr(n), 1), U32.is_even(U32.shr(n)), U32.shr(n), v)}
631	
632	# The value at key k, stored as n = k + 1.
633	def trie.at(-V: Data, t: Trie<V>, +k: U32) -> Maybe<&2, V>:
634	  +n = (k + 1 : U32)
635	  trie.get(V, t, U32.is_eq(n, 1), U32.is_even(n), n)
636	
637	def trie.set(-V: Data, t: Trie<V>, +k: U32, v: V) -> Trie<V>:
638	  +n = (k + 1 : U32)
639	  trie.put(V, 32n, t, U32.is_eq(n, 1), U32.is_even(n), n, v)
640	
641	def trie.from(-V: Data, xs: List<&2, V>, +k: U32, t: Trie<V>) -> Trie<V>:
642	  match xs:
643	    case Nil{}:
644	      t
645	    case Con{h, r}:
646	      trie.from(V, r, (k + 1 : U32), trie.set(V, t, k, h))
647	
648	# prog: the instructions by pc; fuel: enough steps for one closure; slots: two per group, group 0 included.
649	type Regex is Data:
650	  Regex{prog: Trie<Inst>, fuel: Nat, slots: Nat}
651	
652	def build(+node: Node, +n: U32) -> Regex:
653	  +insts = {ISave{0} <> emit(node, 1, [ISave{1}, IMatch{}]) : List<&2, Inst>}
654	  Regex{trie.from(Inst, insts, 0, TTip{}), Nat.add(Nat.mul(3n, List.length(&2, Inst, insts)), 2n), U32.to_nat((2 * n : U32))}
655	
656	def compile.fin(st: Ps) -> Maybe<&2, Regex>:
657	  match st:
658	    case PsFail{}:
659	      None{}
660	    case Ps{n, rep, stack, alts, cur}:
661	      match stack:
662	        case Nil{}:
663	          Some{build(alt.go(alts, seq(cur)), n)}
664	        case Con{f, up}:
665	          None{}
666	
667	def compile.parse(toks: Maybe<&2, List<&2, Tok>>) -> Maybe<&2, Regex>:
668	  match toks:
669	    case None{}:
670	      None{}
671	    case Some{ts}:
672	      compile.fin(parse(ts, Ps{1, False{}, Nil{}, Nil{}, Nil{}}))
673	
674	# The pattern, or None for a syntax error.
675	def compile(+pat: String) -> Maybe<&2, Regex>:
676	  compile.parse(lex(Nat.add(String.length(pat), 2n), LGo{pat, Nil{}}))
677	
678	# Matcher
679	# -------
680	
681	def item.has(i: Item, +c: U32) -> Bool:
682	  match i:
683	    case Rng{+lo, +hi}:
684	      U32.is_le(lo, c) && U32.is_le(c, hi)
685	    case Prop{neg, name}:
686	      Bool.xor(neg, String.starts_with(U.category(Chr{c}), name))
687	
688	def items.has(xs: List<&2, Item>, +c: U32) -> Bool:
689	  match xs:
690	    case Nil{}:
691	      False{}
692	    case Con{h, t}:
693	      item.has(h, c) || items.has(t, c)
694	
695	def word(m: Maybe<&2, Char>) -> Bool:
696	  match m:
697	    case None{}:
698	      False{}
699	    case Some{Chr{+c}}:
700	      is_word(c)
701	
702	def assert.ok(k: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Bool:
703	  match k:
704	    case 0:
705	      Maybe.is_none(&2, Char, prev)
706	    case 1:
707	      Maybe.is_none(&2, Char, next)
708	    case 2:
709	      Bool.xor(word(prev), word(next))
710	    case _:
711	      Bool.not(Bool.xor(word(prev), word(next)))
712	
713	# A thread: its pc and its capture slots.
714	type Th is Data:
715	  Th{pc: U32, caps: List<&2, Maybe<&2, U32>>}
716	
717	# The epsilon closure as a depth-first walk: stack is the work left, seen the pcs
718	# visited at this position, out the threads that wait on a char or match (reversed).
719	type Cl is Data:
720	  Cl{stack: List<&2, Th>, seen: Trie<Unit>, out: List<&2, Th>}
721	
722	def close.assert(ok: Bool, +pc: U32, caps: List<&2, Maybe<&2, U32>>, stack: List<&2, Th>, seen: Trie<Unit>, out: List<&2, Th>) -> Cl:
723	  match ok:
724	    case True{}:
725	      Cl{Th{(pc + 1 : U32), caps} <> stack, seen, out}
726	    case False{}:
727	      Cl{stack, seen, out}
728	
729	def close.inst(i: Maybe<&2, Inst>, +pc: U32, +caps: List<&2, Maybe<&2, U32>>, stack: List<&2, Th>, seen: Trie<Unit>, out: List<&2, Th>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Cl:
730	  match i:
731	    case None{}:
732	      Cl{stack, seen, out}
733	    case Some{IJmp{x}}:
734	      Cl{Th{x, caps} <> stack, seen, out}
735	    case Some{ISplit{x, y}}:
736	      Cl{Th{x, caps} <> Th{y, caps} <> stack, seen, out}
737	    case Some{ISave{k}}:
738	      Cl{Th{(pc + 1 : U32), List.set(&2, Maybe<&2, U32>, caps, U32.to_nat(k), Some{pos})} <> stack, seen, out}
739	    case Some{IAssert{k}}:
740	      close.assert(assert.ok(k, prev, next), pc, caps, stack, seen, out)
741	    case Some{ISet{neg, items}}:
742	      Cl{stack, seen, Th{pc, caps} <> out}
743	    case Some{IMatch{}}:
744	      Cl{stack, seen, Th{pc, caps} <> out}
745	
746	# ponytail: trie lookup and membership cost O(log m) per thread step, so a char costs
747	# O(m log m) for m instructions; a sparse set over an Array would make a step O(1).
748	def close.seen(hit: Bool, +prog: Trie<Inst>, +pc: U32, caps: List<&2, Maybe<&2, U32>>, stack: List<&2, Th>, seen: Trie<Unit>, out: List<&2, Th>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Cl:
749	  match hit:
750	    case True{}:
751	      Cl{stack, seen, out}
752	    case False{}:
753	      close.inst(trie.at(Inst, prog, pc), pc, caps, stack, trie.set(Unit, seen, pc, Unit{}), out, pos, prev, next)
754	
755	def close.step(th: Th, stack: List<&2, Th>, +seen: Trie<Unit>, out: List<&2, Th>, +prog: Trie<Inst>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Cl:
756	  Th{+pc, caps} = th
757	  close.seen(Maybe.is_some(&2, Unit, trie.at(Unit, seen, pc)), prog, pc, caps, stack, seen, out, pos, prev, next)
758	
759	# fuel: each pc expands once and pushes at most two threads.
760	def close(fuel: Nat, +prog: Trie<Inst>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>, st: Cl) -> List<&2, Th>:
761	  match fuel:
762	    case 0n:
763	      Cl{stack, seen, out} = st
764	      List.reverse(&2, Th, out)
765	    case 1n+f:
766	      match st:
767	        case Cl{Nil{}, seen, out}:
768	          List.reverse(&2, Th, out)
769	        case Cl{Con{th, t}, seen, out}:
770	          close(f, prog, pos, prev, next, close.step(th, t, seen, out, prog, pos, prev, next))
771	
772	# A scan of the threads at one char, in priority order: items are the threads that
773	# step past it (reversed), best the latest match. A match drops every later thread.
774	type Sc is Data:
775	  Sc{items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>, stop: Bool}
776	
777	def scan.set(hit: Bool, +pc: U32, caps: List<&2, Maybe<&2, U32>>, items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Sc:
778	  match hit:
779	    case True{}:
780	      Sc{Th{(pc + 1 : U32), caps} <> items, best, False{}}
781	    case False{}:
782	      Sc{items, best, False{}}
783	
784	def scan.char(c: Maybe<&2, Char>, neg: Bool, set: List<&2, Item>, +pc: U32, caps: List<&2, Maybe<&2, U32>>, items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Sc:
785	  match c:
786	    case None{}:
787	      Sc{items, best, False{}}
788	    case Some{Chr{+x}}:
789	      scan.set(Bool.xor(neg, items.has(set, x)), pc, caps, items, best)
790	
791	# any: only whether a match exists counts, so a match also drops the earlier threads.
792	def scan.hit(any: Bool, caps: List<&2, Maybe<&2, U32>>, items: List<&2, Th>) -> Sc:
793	  match any:
794	    case True{}:
795	      Sc{Nil{}, Some{caps}, True{}}
796	    case False{}:
797	      Sc{items, Some{caps}, True{}}
798	
799	def scan.inst(i: Maybe<&2, Inst>, c: Maybe<&2, Char>, +any: Bool, +pc: U32, caps: List<&2, Maybe<&2, U32>>, items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Sc:
800	  match i:
801	    case Some{IMatch{}}:
802	      scan.hit(any, caps, items)
803	    case Some{ISet{neg, set}}:
804	      scan.char(c, neg, set, pc, caps, items, best)
805	    case _:
806	      Sc{items, best, False{}}
807	
808	def scan.go(stop: Bool, th: Th, +prog: Trie<Inst>, c: Maybe<&2, Char>, +any: Bool, items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Sc:
809	  match stop:
810	    case True{}:
811	      Sc{items, best, True{}}
812	    case False{}:
813	      Th{+pc, caps} = th
814	      scan.inst(trie.at(Inst, prog, pc), c, any, pc, caps, items, best)
815	
816	def scan.step(st: Sc, th: Th, +prog: Trie<Inst>, c: Maybe<&2, Char>, +any: Bool) -> Sc:
817	  Sc{items, best, stop} = st
818	  scan.go(stop, th, prog, c, any, items, best)
819	
820	def scan(xs: List<&2, Th>, +prog: Trie<Inst>, +c: Maybe<&2, Char>, +any: Bool, st: Sc) -> Sc:
821	  match xs:
822	    case Nil{}:
823	      st
824	    case Con{th, t}:
825	      scan(t, prog, c, any, scan.step(st, th, prog, c, any))
826	
827	# The live threads and the best match so far.
828	type Vm is Data:
829	  Vm{ths: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>}
830	
831	# Until a match is found, a new thread starts at each position, below every other.
832	def seed(best: Maybe<&2, List<&2, Maybe<&2, U32>>>, xs: List<&2, Th>, init: List<&2, Maybe<&2, U32>>) -> List<&2, Th>:
833	  match best:
834	    case None{}:
835	      List.append(&2, Th, xs, [Th{0, init}])
836	    case Some{b}:
837	      xs
838	
839	def run.close(sc: Sc, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Vm:
840	  Sc{items, +best, stop} = sc
841	  Vm{close(fuel, prog, pos, prev, next, Cl{seed(best, List.reverse(&2, Th, items), init), TTip{}, Nil{}}), best}
842	
843	def run.step(st: Vm, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +any: Bool, +pos: U32, +c: Char, +next: Maybe<&2, Char>) -> Vm:
844	  Vm{ths, best} = st
845	  run.close(scan(ths, prog, Some{c}, any, Sc{Nil{}, best, False{}}), prog, fuel, init, pos, Some{c}, next)
846	
847	def run.end(sc: Sc) -> Maybe<&2, List<&2, Maybe<&2, U32>>>:
848	  Sc{items, best, stop} = sc
849	  best
850	
851	# pos: the position of s's head. Once a match exists and no thread is live, the rest of s cannot change it.
852	def run(s: String, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +any: Bool, +pos: U32, st: Vm) -> Maybe<&2, List<&2, Maybe<&2, U32>>>:
853	  match s:
854	    case SNil{}:
855	      Vm{ths, best} = st
856	      run.end(scan(ths, prog, None{}, any, Sc{Nil{}, best, False{}}))
857	    case SCon{+c, +t}:
858	      match st:
859	        case Vm{Nil{}, Some{b}}:
860	          Some{b}
861	        case Vm{ths, best}:
862	          +p = (pos + 1 : U32)
863	          run(t, prog, fuel, init, any, p, run.step(Vm{ths, best}, prog, fuel, init, any, p, c, String.get(t, 0n)))
864	
865	type Span is Data:
866	  Span{start: U32, end: U32}
867	
868	def spans(caps: List<&2, Maybe<&2, U32>>) -> List<&2, Maybe<&2, Span>>:
869	  match caps:
870	    case Con{Some{a}, Con{Some{b}, t}}:
871	      Some{Span{a, b}} <> spans(t)
872	    case Con{x, Con{y, t}}:
873	      None{} <> spans(t)
874	    case _:
875	      Nil{}
876	
877	def find.spans(m: Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Maybe<&2, List<&2, Maybe<&2, Span>>>:
878	  match m:
879	    case None{}:
880	      None{}
881	    case Some{caps}:
882	      Some{spans(caps)}
883	
884	# slots: capture slots to keep; is_match keeps none, so each ISave is free.
885	def exec(re: Regex, +s: String, +any: Bool) -> Maybe<&2, List<&2, Maybe<&2, U32>>>:
886	  Regex{+prog, +fuel, +slots} = re
887	  +init = List.replicate(Maybe<&2, U32>, Bool.pick(Nat, any, 0n, slots), None{})
888	  run(s, prog, fuel, init, any, 0, Vm{close(fuel, prog, 0, None{}, String.get(s, 0n), Cl{[Th{0, init}], TTip{}, Nil{}}), None{}})
889	
890	# The leftmost match in s: the span of group 0, then of each group; None for a group that did not take part.
891	def find(re: Regex, +s: String) -> Maybe<&2, List<&2, Maybe<&2, Span>>>:
892	  find.spans(exec(re, s, False{}))
893	
894	# Stops at the first match of any priority and records no captures.
895	def is_match(re: Regex, +s: String) -> Bool:
896	  Maybe.is_some(&2, List<&2, Maybe<&2, U32>>, exec(re, s, True{}))