1	# A small regular-expression matcher, for the scalar forms schemas name as
2	# regexes. A pattern is data: a list of items, each a character class, an
3	# optional or repeated item, or a choice of sequences. Matching is anchored
4	# at both ends and backtracks. Each step eats a character or moves along the
5	# pattern, so fuel of the text's length times a constant bounds the work.
6	
7	import Base
8	
9	type Cls is Data:
10	  Digit{}
11	  Hex{}
12	  Range{lo: Char, hi: Char}
13	  Lit{c: Char}
14	  OneOf{chars: String}
15	  NoneOf{chars: String}
16	  Alpha{}
17	  Space{}
18	  Anything{}
19	
20	type Pat is Data:
21	  One{cls: Cls}
22	  Opt{p: Pat}
23	  Star{p: Pat}
24	  Plus{p: Pat}
25	  Alt{alts: List<&2, List<&2, Pat>>}
26	
27	def code(c: Char) -> U32:
28	  match c:
29	    case Chr{x}:
30	      x
31	
32	def between(+x: U32, lo: U32, hi: U32) -> Bool:
33	  Bool.and(U32.is_ge(x, lo), U32.is_le(x, hi))
34	
35	def in(c: Char, s: String) -> Bool:
36	  String.contains(s, SCon{c, SNil{}})
37	
38	# [[:alpha:]] as Onigmo reads it: ASCII letters, and letters past ASCII.
39	def is_alpha(+x: U32) -> Bool:
40	  Bool.or(Bool.or(between(x, 65, 90), between(x, 97, 122)),
41	    Bool.or(between(x, 170, 170), Bool.or(between(x, 181, 181), Bool.or(between(x, 186, 186),
42	      Bool.and(U32.is_ge(x, 192), Bool.and(Bool.not(U32.is_eq(x, 215)), Bool.not(U32.is_eq(x, 247))))))))
43	
44	def test(cls: Cls, +c: Char) -> Bool:
45	  match cls:
46	    case Digit{}:
47	      Char.is_digit(c)
48	    case Hex{}:
49	      Bool.or(Char.is_digit(c), Bool.or(between(code(c), 65, 70), between(code(c), 97, 102)))
50	    case Range{lo, hi}:
51	      between(code(c), code(lo), code(hi))
52	    case Lit{x}:
53	      Char.is_eq(c, x)
54	    case OneOf{chars}:
55	      in(c, chars)
56	    case NoneOf{chars}:
57	      Bool.not(in(c, chars))
58	    case Alpha{}:
59	      is_alpha(code(c))
60	    case Space{}:
61	      Char.is_space(c)
62	    case Anything{}:
63	      True{}
64	
65	def or.else(hit: Bool, rest: Unit -> Bool) -> Bool:
66	  match hit:
67	    case True{}:
68	      True{}
69	    case False{}:
70	      rest(Unit{})
71	
72	def and.then(hit: Bool, rest: Unit -> Bool) -> Bool:
73	  match hit:
74	    case True{}:
75	      rest(Unit{})
76	    case False{}:
77	      False{}
78	
79	def run(fuel: Nat, ps: List<&2, Pat>, +s: String) -> Bool:
80	  match fuel:
81	    case 0n:
82	      False{}
83	    case 1n+(+k):
84	      match ps:
85	        case Nil{}:
86	          String.is_empty(s)
87	        case Con{p, +rest}:
88	          match p:
89	            case One{cls}:
90	              match s:
91	                case SNil{}:
92	                  False{}
93	                case SCon{+c, t}:
94	                  and.then(test(cls, c), u => run(k, rest, t))
95	            case Opt{+q}:
96	              or.else(run(k, q <> rest, s), u => run(k, rest, s))
97	            case Star{+q}:
98	              or.else(run(k, q <> Star{q} <> rest, s), u => run(k, rest, s))
99	            case Plus{+q}:
100	              run(k, q <> Star{q} <> rest, s)
101	            case Alt{alts}:
102	              match alts:
103	                case Nil{}:
104	                  False{}
105	                case Con{a, others}:
106	                  or.else(run(k, List.append(&2, Pat, a, rest), s), u => run(k, Alt{others} <> rest, s))
107	
108	# Whether all of +s+ matches +ps+.
109	def matches(ps: List<&2, Pat>, +s: String) -> Bool:
110	  run(Nat.mul(Nat.add(String.length(s), 2n), 64n), ps, s)
111	
112	# Whether +s+ starts with a match of +ps+.
113	def starts(ps: List<&2, Pat>, +s: String) -> Bool:
114	  matches(List.append(&2, Pat, ps, [Star{One{Anything{}}}]), s)
115	
116	# Builders, so a pattern reads close to the regex it comes from.
117	def c(x: Char) -> Pat:
118	  One{Lit{x}}
119	
120	def digit() -> Pat:
121	  One{Digit{}}
122	
123	def digits() -> Pat:
124	  Plus{One{Digit{}}}
125	
126	def sign() -> Pat:
127	  Opt{One{OneOf{"-+"}}}
128	
129	def of(chars: String) -> Pat:
130	  One{OneOf{chars}}
131	
132	def seq(ps: List<&2, Pat>) -> Pat:
133	  Alt{[ps]}
134	
135	def word(s: String) -> List<&2, Pat>:
136	  match s:
137	    case SNil{}:
138	      []
139	    case SCon{x, t}:
140	      c(x) <> word(t)