regex.bend
bend-kit-regex@0.4.0.0 · 1,162 lines · 0 definitions
1# Linear-time regular expressions: RE2 syntax, Pike VM, capture groups. Source: https://github.com/paymog/bend-kit/tree/main/regex
2import Base
3import bend-kit-unicode@0.1.0.0/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", ...).
12type 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.
17type 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
27type 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
34def lit(+c: U32) -> Node:
35 NSet{False{}, [Rng{c, c}]}
36
37def is_digit(+c: U32) -> Bool:
38 U32.is_le(48, c) && U32.is_le(c, 57)
39
40def 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
43def 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.
47def perl.d() -> List<&2, Item>:
48 [Rng{48, 57}]
49
50def perl.D() -> List<&2, Item>:
51 [Rng{0, 47}, Rng{58, 1114111}]
52
53def perl.w() -> List<&2, Item>:
54 [Rng{48, 57}, Rng{65, 90}, Rng{95, 95}, Rng{97, 122}]
55
56def perl.W() -> List<&2, Item>:
57 [Rng{0, 47}, Rng{58, 64}, Rng{91, 94}, Rng{96, 96}, Rng{123, 1114111}]
58
59def perl.s() -> List<&2, Item>:
60 [Rng{9, 10}, Rng{12, 13}, Rng{32, 32}]
61
62def perl.S() -> List<&2, Item>:
63 [Rng{0, 8}, Rng{11, 11}, Rng{14, 31}, Rng{33, 1114111}]
64
65def 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
73type 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
79def 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
86def prop.ok(neg: Bool, +name: String, t: String) -> Esc:
87 prop.if(List.contains(~String, ~String.eq, cats(), name), neg, name, t)
88
89def 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.
99def 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.
109def 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.
117def 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
161type Cs is Data:
162 CsGo{s: String, first: Bool, items: List<&2, Item>}
163 CsDone{items: List<&2, Item>, rest: String}
164 CsFail{}
165
166def 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
173def 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.
185def 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
196def 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.
208def 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.
224def 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
237def class(+s: String, first: Bool) -> Cs:
238 class.run(Nat.add(String.length(s), 1n), CsGo{s, first, Nil{}})
239
240# Lexer
241# -----
242
243type 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.
249type Num is Data:
250 Num{v: U32, n: U32, rest: String}
251
252def num.add(+acc: U32, +c: U32) -> U32:
253 Bool.pick(U32, U32.is_lt(acc, 100000), (acc * 10 + (c - 48) : U32), 100000)
254
255def 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
270def 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.
278def 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
285def 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.
290def 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
302def 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
319def 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
328def 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
339def 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.
378def 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.
395type 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.
399type Ps is Data:
400 Ps{n: U32, rep: Bool, stack: List<&2, Frame>, alts: List<&2, Node>, cur: List<&2, Node>}
401 PsFail{}
402def 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
413def 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
420def seq(xs: List<&2, Node>) -> Node:
421 seq.go(xs, NEmpty{})
422
423def 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
430def 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
437def 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
444def 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.
452def 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
459def 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
466def 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.
470def 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
477def 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
488def 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
495def 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
502def 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
515def 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
522def 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
532type 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
540def 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.
560def 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.
584type 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.
589def 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.
605def 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.
633def 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
637def 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
641def 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# The walk from pc 0 over the instructions that consume no char: the sets it reaches, or
649# FsAny when it reaches an assertion or a match, so that any char may start a match.
650type Fs is Data:
651 Fs{stack: List<&2, U32>, seen: List<&2, U32>, sets: List<&2, Inst>}
652 FsAny{}
653
654def first.inst(i: Maybe<&2, Inst>, +pc: U32, stack: List<&2, U32>, seen: List<&2, U32>, sets: List<&2, Inst>) -> Fs:
655 match i:
656 case Some{IJmp{x}}:
657 Fs{x <> stack, seen, sets}
658 case Some{ISplit{x, y}}:
659 Fs{x <> y <> stack, seen, sets}
660 case Some{ISave{k}}:
661 Fs{(pc + 1 : U32) <> stack, seen, sets}
662 case Some{ISet{neg, items}}:
663 Fs{stack, seen, ISet{neg, items} <> sets}
664 case _:
665 FsAny{}
666
667def first.seen(hit: Bool, +prog: List<&2, Inst>, +pc: U32, stack: List<&2, U32>, seen: List<&2, U32>, sets: List<&2, Inst>) -> Fs:
668 match hit:
669 case True{}:
670 Fs{stack, seen, sets}
671 case False{}:
672 first.inst(List.get(&2, Inst, prog, U32.to_nat(pc)), pc, stack, pc <> seen, sets)
673
674# fuel: each pc expands once and pushes at most two pcs.
675def first(fuel: Nat, +prog: List<&2, Inst>, st: Fs) -> Maybe<&2, List<&2, Inst>>:
676 match fuel:
677 case 0n:
678 None{}
679 case 1n+f:
680 match st:
681 case FsAny{}:
682 None{}
683 case Fs{Nil{}, seen, sets}:
684 Some{sets}
685 case Fs{Con{+pc, t}, +seen, sets}:
686 first(f, prog, first.seen(List.contains(~U32, ~U32.is_eq, seen, pc), prog, pc, t, seen, sets))
687
688# Bit-parallel NFA for is_match: bit pc stands for the set at pc, waiting on the next char.
689# The epsilon walk from a pc: the sets it reaches and whether it reaches the match, where at0
690# says the position is the start of the text and at1 the end.
691type Ew is Data:
692 Ew{stack: List<&2, U32>, seen: List<&2, U32>, mask: U32, hit: Bool}
693
694def eps.ctx(k: U32, +at0: Bool, +at1: Bool) -> Bool:
695 match k:
696 case 0:
697 at0
698 case 1:
699 at1
700 case _:
701 False{}
702
703def eps.assert(ok: Bool, +pc: U32, stack: List<&2, U32>, seen: List<&2, U32>, mask: U32, hit: Bool) -> Ew:
704 match ok:
705 case True{}:
706 Ew{(pc + 1 : U32) <> stack, seen, mask, hit}
707 case False{}:
708 Ew{stack, seen, mask, hit}
709
710def eps.inst(i: Maybe<&2, Inst>, +pc: U32, +at0: Bool, +at1: Bool, stack: List<&2, U32>, seen: List<&2, U32>, +mask: U32, hit: Bool) -> Ew:
711 match i:
712 case Some{IJmp{x}}:
713 Ew{x <> stack, seen, mask, hit}
714 case Some{ISplit{x, y}}:
715 Ew{x <> y <> stack, seen, mask, hit}
716 case Some{ISave{k}}:
717 Ew{(pc + 1 : U32) <> stack, seen, mask, hit}
718 case Some{IAssert{k}}:
719 eps.assert(eps.ctx(k, at0, at1), pc, stack, seen, mask, hit)
720 case Some{ISet{neg, items}}:
721 Ew{stack, seen, (mask .|. (1 << U32.to_nat(pc)) : U32), hit}
722 case Some{IMatch{}}:
723 Ew{stack, seen, mask, True{}}
724 case None{}:
725 Ew{stack, seen, mask, hit}
726
727def eps.seen(hit: Bool, +prog: List<&2, Inst>, +pc: U32, +at0: Bool, +at1: Bool, w: Ew) -> Ew:
728 match hit:
729 case True{}:
730 w
731 case False{}:
732 Ew{stack, seen, mask, h} = w
733 eps.inst(List.get(&2, Inst, prog, U32.to_nat(pc)), pc, at0, at1, stack, pc <> seen, mask, h)
734
735# fuel: each pc expands once and pushes at most two pcs.
736def eps.go(fuel: Nat, +prog: List<&2, Inst>, +at0: Bool, +at1: Bool, w: Ew) -> Ew:
737 match fuel:
738 case 0n:
739 w
740 case 1n+f:
741 match w:
742 case Ew{Nil{}, seen, mask, hit}:
743 Ew{Nil{}, seen, mask, hit}
744 case Ew{Con{+pc, t}, +seen, mask, hit}:
745 eps.go(f, prog, at0, at1, eps.seen(List.contains(~U32, ~U32.is_eq, seen, pc), prog, pc, at0, at1, Ew{t, seen, mask, hit}))
746
747def eps(+fuel: Nat, +prog: List<&2, Inst>, +pc: U32, +at0: Bool, +at1: Bool) -> Ew:
748 eps.go(fuel, prog, at0, at1, Ew{[pc], Nil{}, 0, False{}})
749
750def Ew.mask(w: Ew) -> U32:
751 Ew{s, v, mask, hit} = w
752 mask
753
754def Ew.hit(w: Ew) -> Bool:
755 Ew{s, v, mask, hit} = w
756 hit
757
758# The set at bit mask; follow: the sets live after it takes a char; fin, end: whether the match
759# is then reached inside the text, or at its end.
760type Bit is Data:
761 Bit{mask: U32, neg: Bool, items: List<&2, Item>, follow: U32, fin: Bool, end: Bool}
762
763# at0: the sets live at the start of the text, and hit0 whether the empty match is there;
764# hit01 the same for the empty text; atn and hitn the same inside the text, hit1 at its end.
765type Bits is Data:
766 Bits{sets: List<&2, Bit>, at0: U32, hit0: Bool, hit01: Bool, atn: U32, hit1: Bool}
767
768def bits.set(+fuel: Nat, +prog: List<&2, Inst>, +pc: U32, neg: Bool, items: List<&2, Item>) -> Bit:
769 +w = eps(fuel, prog, (pc + 1 : U32), False{}, False{})
770 Bit{(1 << U32.to_nat(pc) : U32), neg, items, Ew.mask(w), Ew.hit(w), Ew.hit(eps(fuel, prog, (pc + 1 : U32), False{}, True{}))}
771
772def bits.sets(xs: List<&2, Inst>, +fuel: Nat, +prog: List<&2, Inst>, +pc: U32) -> List<&2, Bit>:
773 match xs:
774 case Nil{}:
775 Nil{}
776 case Con{ISet{neg, items}, t}:
777 bits.set(fuel, prog, pc, neg, items) <> bits.sets(t, fuel, prog, (pc + 1 : U32))
778 case Con{i, t}:
779 bits.sets(t, fuel, prog, (pc + 1 : U32))
780
781# Word boundaries depend on the chars on both sides, which one mask per set cannot track.
782def bits.plain(xs: List<&2, Inst>) -> Bool:
783 match xs:
784 case Nil{}:
785 True{}
786 case Con{IAssert{+k}, t}:
787 U32.is_lt(k, 2) && bits.plain(t)
788 case Con{i, t}:
789 bits.plain(t)
790
791def bits.if(ok: Bool, +fuel: Nat, +prog: List<&2, Inst>) -> Maybe<&2, Bits>:
792 match ok:
793 case False{}:
794 None{}
795 case True{}:
796 +w0 = eps(fuel, prog, 0, True{}, False{})
797 +wn = eps(fuel, prog, 0, False{}, False{})
798 Some{Bits{bits.sets(prog, fuel, prog, 0), Ew.mask(w0), Ew.hit(w0), Ew.hit(eps(fuel, prog, 0, True{}, True{})), Ew.mask(wn), Ew.hit(eps(fuel, prog, 0, False{}, True{}))}}
799
800def bits(+fuel: Nat, +prog: List<&2, Inst>) -> Maybe<&2, Bits>:
801 bits.if(Nat.is_le(List.length(&2, Inst, prog), 32n) && bits.plain(prog), fuel, prog)
802
803# prog: the instructions by pc; fuel: enough steps for one closure; slots: two per group, group 0 included;
804# start: the sets one of which the first char of a match is in, or None when a match may start anywhere;
805# bits: the bit-parallel form, for programs of at most 32 instructions without word boundaries.
806type Regex is Data:
807 Regex{prog: Trie<Inst>, fuel: Nat, slots: Nat, start: Maybe<&2, List<&2, Inst>>, bits: Maybe<&2, Bits>}
808
809def build(+node: Node, +n: U32) -> Regex:
810 +insts = {ISave{0} <> emit(node, 1, [ISave{1}, IMatch{}]) : List<&2, Inst>}
811 +fuel = Nat.add(Nat.mul(3n, List.length(&2, Inst, insts)), 2n)
812 Regex{trie.from(Inst, insts, 0, TTip{}), fuel, U32.to_nat((2 * n : U32)), first(fuel, insts, Fs{[0], Nil{}, Nil{}}), bits(fuel, insts)}
813
814def compile.fin(st: Ps) -> Maybe<&2, Regex>:
815 match st:
816 case PsFail{}:
817 None{}
818 case Ps{n, rep, stack, alts, cur}:
819 match stack:
820 case Nil{}:
821 Some{build(alt.go(alts, seq(cur)), n)}
822 case Con{f, up}:
823 None{}
824
825def compile.parse(toks: Maybe<&2, List<&2, Tok>>) -> Maybe<&2, Regex>:
826 match toks:
827 case None{}:
828 None{}
829 case Some{ts}:
830 compile.fin(parse(ts, Ps{1, False{}, Nil{}, Nil{}, Nil{}}))
831
832# The pattern, or None for a syntax error.
833def compile(+pat: String) -> Maybe<&2, Regex>:
834 compile.parse(lex(Nat.add(String.length(pat), 2n), LGo{pat, Nil{}}))
835
836# Matcher
837# -------
838
839def item.has(i: Item, +c: U32) -> Bool:
840 match i:
841 case Rng{+lo, +hi}:
842 U32.is_le(lo, c) && U32.is_le(c, hi)
843 case Prop{neg, name}:
844 Bool.xor(neg, String.starts_with(U.category(Chr{c}), name))
845
846def items.has(xs: List<&2, Item>, +c: U32) -> Bool:
847 match xs:
848 case Nil{}:
849 False{}
850 case Con{h, t}:
851 item.has(h, c) || items.has(t, c)
852
853def word(m: Maybe<&2, Char>) -> Bool:
854 match m:
855 case None{}:
856 False{}
857 case Some{Chr{+c}}:
858 is_word(c)
859
860def assert.ok(k: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Bool:
861 match k:
862 case 0:
863 Maybe.is_none(&2, Char, prev)
864 case 1:
865 Maybe.is_none(&2, Char, next)
866 case 2:
867 Bool.xor(word(prev), word(next))
868 case _:
869 Bool.not(Bool.xor(word(prev), word(next)))
870
871# A thread: its pc and its capture slots.
872type Th is Data:
873 Th{pc: U32, caps: List<&2, Maybe<&2, U32>>}
874
875# The epsilon closure as a depth-first walk: stack is the work left, seen the pcs
876# visited at this position, out the threads that wait on a char or match (reversed).
877type Cl is Data:
878 Cl{stack: List<&2, Th>, seen: Trie<Unit>, out: List<&2, Th>}
879
880def close.assert(ok: Bool, +pc: U32, caps: List<&2, Maybe<&2, U32>>, stack: List<&2, Th>, seen: Trie<Unit>, out: List<&2, Th>) -> Cl:
881 match ok:
882 case True{}:
883 Cl{Th{(pc + 1 : U32), caps} <> stack, seen, out}
884 case False{}:
885 Cl{stack, seen, out}
886
887def 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:
888 match i:
889 case None{}:
890 Cl{stack, seen, out}
891 case Some{IJmp{x}}:
892 Cl{Th{x, caps} <> stack, seen, out}
893 case Some{ISplit{x, y}}:
894 Cl{Th{x, caps} <> Th{y, caps} <> stack, seen, out}
895 case Some{ISave{k}}:
896 Cl{Th{(pc + 1 : U32), List.set(&2, Maybe<&2, U32>, caps, U32.to_nat(k), Some{pos})} <> stack, seen, out}
897 case Some{IAssert{k}}:
898 close.assert(assert.ok(k, prev, next), pc, caps, stack, seen, out)
899 case Some{ISet{neg, items}}:
900 Cl{stack, seen, Th{pc, caps} <> out}
901 case Some{IMatch{}}:
902 Cl{stack, seen, Th{pc, caps} <> out}
903
904# ponytail: trie lookup and membership cost O(log m) per thread step, so a char costs
905# O(m log m) for m instructions; a sparse set over an Array would make a step O(1).
906def 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:
907 match hit:
908 case True{}:
909 Cl{stack, seen, out}
910 case False{}:
911 close.inst(trie.at(Inst, prog, pc), pc, caps, stack, trie.set(Unit, seen, pc, Unit{}), out, pos, prev, next)
912
913def 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:
914 Th{+pc, caps} = th
915 close.seen(Maybe.is_some(&2, Unit, trie.at(Unit, seen, pc)), prog, pc, caps, stack, seen, out, pos, prev, next)
916
917# fuel: each pc expands once and pushes at most two threads.
918def close(fuel: Nat, +prog: Trie<Inst>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>, st: Cl) -> List<&2, Th>:
919 match fuel:
920 case 0n:
921 Cl{stack, seen, out} = st
922 List.reverse(&2, Th, out)
923 case 1n+f:
924 match st:
925 case Cl{Nil{}, seen, out}:
926 List.reverse(&2, Th, out)
927 case Cl{Con{th, t}, seen, out}:
928 close(f, prog, pos, prev, next, close.step(th, t, seen, out, prog, pos, prev, next))
929
930# A scan of the threads at one char, in priority order: items are the threads that
931# step past it (reversed), best the latest match. A match drops every later thread.
932type Sc is Data:
933 Sc{items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>, stop: Bool}
934
935def 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:
936 match hit:
937 case True{}:
938 Sc{Th{(pc + 1 : U32), caps} <> items, best, False{}}
939 case False{}:
940 Sc{items, best, False{}}
941
942def 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:
943 match c:
944 case None{}:
945 Sc{items, best, False{}}
946 case Some{Chr{+x}}:
947 scan.set(Bool.xor(neg, items.has(set, x)), pc, caps, items, best)
948
949# any: only whether a match exists counts, so a match also drops the earlier threads.
950def scan.hit(any: Bool, caps: List<&2, Maybe<&2, U32>>, items: List<&2, Th>) -> Sc:
951 match any:
952 case True{}:
953 Sc{Nil{}, Some{caps}, True{}}
954 case False{}:
955 Sc{items, Some{caps}, True{}}
956
957def 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:
958 match i:
959 case Some{IMatch{}}:
960 scan.hit(any, caps, items)
961 case Some{ISet{neg, set}}:
962 scan.char(c, neg, set, pc, caps, items, best)
963 case _:
964 Sc{items, best, False{}}
965
966def 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:
967 match stop:
968 case True{}:
969 Sc{items, best, True{}}
970 case False{}:
971 Th{+pc, caps} = th
972 scan.inst(trie.at(Inst, prog, pc), c, any, pc, caps, items, best)
973
974def scan.step(st: Sc, th: Th, +prog: Trie<Inst>, c: Maybe<&2, Char>, +any: Bool) -> Sc:
975 Sc{items, best, stop} = st
976 scan.go(stop, th, prog, c, any, items, best)
977
978def scan(xs: List<&2, Th>, +prog: Trie<Inst>, +c: Maybe<&2, Char>, +any: Bool, st: Sc) -> Sc:
979 match xs:
980 case Nil{}:
981 st
982 case Con{th, t}:
983 scan(t, prog, c, any, scan.step(st, th, prog, c, any))
984
985# The live threads and the best match so far.
986type Vm is Data:
987 Vm{ths: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>}
988
989# Until a match is found, a new thread starts at each position, below every other.
990def seed(best: Maybe<&2, List<&2, Maybe<&2, U32>>>, xs: List<&2, Th>, init: List<&2, Maybe<&2, U32>>) -> List<&2, Th>:
991 match best:
992 case None{}:
993 List.append(&2, Th, xs, [Th{0, init}])
994 case Some{b}:
995 xs
996
997def starts(xs: List<&2, Inst>, +c: U32) -> Bool:
998 match xs:
999 case Nil{}:
1000 False{}
1001 case Con{ISet{neg, set}, t}:
1002 Bool.xor(neg, items.has(set, c)) || starts(t, c)
1003 case Con{i, t}:
1004 starts(t, c)
1005
1006# No live thread and no match yet: the seed is the only thread, and it dies unless next is in start.
1007def seed.skip(items: List<&2, Th>, best: Maybe<&2, List<&2, Maybe<&2, U32>>>, start: Maybe<&2, List<&2, Inst>>, next: Maybe<&2, Char>) -> Bool:
1008 match items best start next:
1009 case Nil{} None{} Some{sets} None{}:
1010 True{}
1011 case Nil{} None{} Some{sets} Some{Chr{+c}}:
1012 Bool.not(starts(sets, c))
1013 case _ _ _ _:
1014 False{}
1015
1016def run.seed(skip: Bool, items: List<&2, Th>, +best: Maybe<&2, List<&2, Maybe<&2, U32>>>, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Vm:
1017 match skip:
1018 case True{}:
1019 Vm{Nil{}, None{}}
1020 case False{}:
1021 Vm{close(fuel, prog, pos, prev, next, Cl{seed(best, List.reverse(&2, Th, items), init), TTip{}, Nil{}}), best}
1022
1023def run.close(sc: Sc, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +start: Maybe<&2, List<&2, Inst>>, +pos: U32, +prev: Maybe<&2, Char>, +next: Maybe<&2, Char>) -> Vm:
1024 Sc{+items, +best, stop} = sc
1025 run.seed(seed.skip(items, best, start, next), items, best, prog, fuel, init, pos, prev, next)
1026
1027def run.step(st: Vm, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +start: Maybe<&2, List<&2, Inst>>, +any: Bool, +pos: U32, +c: Char, +next: Maybe<&2, Char>) -> Vm:
1028 Vm{ths, best} = st
1029 run.close(scan(ths, prog, Some{c}, any, Sc{Nil{}, best, False{}}), prog, fuel, init, start, pos, Some{c}, next)
1030
1031def run.end(sc: Sc) -> Maybe<&2, List<&2, Maybe<&2, U32>>>:
1032 Sc{items, best, stop} = sc
1033 best
1034
1035# pos: the position of s's head. Once a match exists and no thread is live, the rest of s cannot change it.
1036def run(s: String, +prog: Trie<Inst>, +fuel: Nat, +init: List<&2, Maybe<&2, U32>>, +start: Maybe<&2, List<&2, Inst>>, +any: Bool, +pos: U32, st: Vm) -> Maybe<&2, List<&2, Maybe<&2, U32>>>:
1037 match s:
1038 case SNil{}:
1039 Vm{ths, best} = st
1040 run.end(scan(ths, prog, None{}, any, Sc{Nil{}, best, False{}}))
1041 case SCon{+c, +t}:
1042 match st:
1043 case Vm{Nil{}, Some{b}}:
1044 Some{b}
1045 case Vm{ths, best}:
1046 +p = (pos + 1 : U32)
1047 run(t, prog, fuel, init, start, any, p, run.step(Vm{ths, best}, prog, fuel, init, start, any, p, c, String.get(t, 0n)))
1048
1049type Span is Data:
1050 Span{start: U32, end: U32}
1051
1052def spans(caps: List<&2, Maybe<&2, U32>>) -> List<&2, Maybe<&2, Span>>:
1053 match caps:
1054 case Con{Some{a}, Con{Some{b}, t}}:
1055 Some{Span{a, b}} <> spans(t)
1056 case Con{x, Con{y, t}}:
1057 None{} <> spans(t)
1058 case _:
1059 Nil{}
1060
1061def find.spans(m: Maybe<&2, List<&2, Maybe<&2, U32>>>) -> Maybe<&2, List<&2, Maybe<&2, Span>>>:
1062 match m:
1063 case None{}:
1064 None{}
1065 case Some{caps}:
1066 Some{spans(caps)}
1067
1068# slots: capture slots to keep; is_match keeps none, so each ISave is free.
1069def exec(re: Regex, +s: String, +any: Bool) -> Maybe<&2, List<&2, Maybe<&2, U32>>>:
1070 Regex{+prog, +fuel, +slots, +start, bits} = re
1071 +init = List.replicate(Maybe<&2, U32>, Bool.pick(Nat, any, 0n, slots), None{})
1072 run(s, prog, fuel, init, start, any, 0, run.close(Sc{Nil{}, None{}, False{}}, prog, fuel, init, start, 0, None{}, String.get(s, 0n)))
1073
1074# The leftmost match in s: the span of group 0, then of each group; None for a group that did not take part.
1075def find(re: Regex, +s: String) -> Maybe<&2, List<&2, Maybe<&2, Span>>>:
1076 find.spans(exec(re, s, False{}))
1077
1078# The Pike VM form of is_match: stops at the first match of any priority and records no captures.
1079def is_match.vm(re: Regex, +s: String) -> Bool:
1080 Maybe.is_some(&2, List<&2, Maybe<&2, U32>>, exec(re, s, True{}))
1081
1082# One char through the bit NFA: next the sets live after it, fin and end as in Bit.
1083type Bs is Data:
1084 Bs{next: U32, fin: Bool, end: Bool}
1085
1086def bits.take(hit: Bool, +follow: U32, +fin: Bool, +end: Bool, acc: Bs) -> Bs:
1087 match hit:
1088 case False{}:
1089 acc
1090 case True{}:
1091 Bs{+nx, f, e} = acc
1092 Bs{(nx .|. follow : U32), f || fin, e || end}
1093
1094def bits.char(live: Bool, +c: U32, neg: Bool, items: List<&2, Item>, +follow: U32, +fin: Bool, +end: Bool, acc: Bs) -> Bs:
1095 match live:
1096 case False{}:
1097 acc
1098 case True{}:
1099 bits.take(Bool.xor(neg, items.has(items, c)), follow, fin, end, acc)
1100
1101# ponytail: one test per set in the program, not a table lookup; use per-byte tables if sets grow many.
1102def bits.step(xs: List<&2, Bit>, +cur: U32, +c: U32, acc: Bs) -> Bs:
1103 match xs:
1104 case Nil{}:
1105 acc
1106 case Con{Bit{+mask, neg, items, follow, fin, end}, t}:
1107 bits.step(t, cur, c, bits.char(U32.is_ne((cur .&. mask : U32), 0), c, neg, items, follow, fin, end, acc))
1108
1109# Only the sets live at a fresh start wait on c, and c starts none of them: nothing moves.
1110def bits.idle(start: Maybe<&2, List<&2, Inst>>, +cur: U32, +atn: U32, +c: U32) -> Bool:
1111 match start:
1112 case None{}:
1113 False{}
1114 case Some{sets}:
1115 U32.is_eq(cur, atn) && Bool.not(starts(sets, c))
1116
1117# hit1: a match starts and ends at the end of the text, so end starts from it.
1118def bits.go(idle: Bool, +sets: List<&2, Bit>, +atn: U32, +hit1: Bool, +cur: U32, +c: U32) -> Bs:
1119 match idle:
1120 case True{}:
1121 Bs{atn, False{}, hit1}
1122 case False{}:
1123 bits.step(sets, cur, c, Bs{atn, False{}, hit1})
1124
1125# r: the sets live at s's head, whether a match was found, and whether one ends at the end of
1126# the text, if the text ends here. Inside the text an assertion can only fail, so fin implies end,
1127# and a match at fin is final.
1128def bits.run(s: String, +sets: List<&2, Bit>, +start: Maybe<&2, List<&2, Inst>>, +atn: U32, +hit1: Bool, r: Bs) -> Bool:
1129 match s:
1130 case SNil{}:
1131 Bs{cur, done, ok} = r
1132 done || ok
1133 case SCon{Chr{+c}, t}:
1134 match r:
1135 case Bs{cur, True{}, ok}:
1136 True{}
1137 case Bs{+cur, False{}, ok}:
1138 bits.run(t, sets, start, atn, hit1, bits.go(bits.idle(start, cur, atn, c), sets, atn, hit1, cur, c))
1139
1140def bits.is_match(b: Bits, start: Maybe<&2, List<&2, Inst>>, s: String) -> Bool:
1141 Bits{sets, at0, hit0, hit01, atn, hit1} = b
1142 bits.run(s, sets, start, atn, hit1, Bs{at0, hit0, hit01})
1143
1144# The bit NFA form of is_match, or None when the program is too large or has a word boundary.
1145def is_match.bits(re: Regex, s: String) -> Maybe<&2, Bool>:
1146 Regex{prog, fuel, slots, start, bits} = re
1147 match bits:
1148 case None{}:
1149 None{}
1150 case Some{b}:
1151 Some{bits.is_match(b, start, s)}
1152
1153def is_match.pick(m: Maybe<&2, Bool>, re: Regex, +s: String) -> Bool:
1154 match m:
1155 case Some{x}:
1156 x
1157 case None{}:
1158 is_match.vm(re, s)
1159
1160# Whether s has a match; the bit NFA runs when the program allows it, else the Pike VM.
1161def is_match(+re: Regex, +s: String) -> Bool:
1162 is_match.pick(is_match.bits(re, s), re, s)