1	import Base
2	
3	type Tok is Data:
4	  TLBrace{}
5	  TRBrace{}
6	  TLBrack{}
7	  TRBrack{}
8	  TColon{}
9	  TComma{}
10	  TNull{}
11	  TTrue{}
12	  TFalse{}
13	  TNum{text: String}
14	  TStr{s: String}
15	  TSkip{}
16	  TErr{msg: String}
17	
18	def sel(c: Bool, x: U32, y: U32) -> U32:
19	  match c:
20	    case True{}:
21	      x
22	    case False{}:
23	      y
24	
25	def sel.s(c: Bool, x: String, y: String) -> String:
26	  match c:
27	    case True{}:
28	      x
29	    case False{}:
30	      y
31	
32	def sel.n(c: Bool, x: Nat, y: Nat) -> Nat:
33	  match c:
34	    case True{}:
35	      x
36	    case False{}:
37	      y
38	
39	def not(b: Bool) -> Bool:
40	  Bool.not(b)
41	
42	def eqc(+c: Char, +d: Char) -> Bool:
43	  Char.is_eq(c, d)
44	
45	# ---- characters and numbers --------------------------------------------------
46	
47	def is_word(+c: Char) -> Bool:
48	  Char.is_digit(c) || Char.is_alpha(c) || eqc(c, '-') || eqc(c, '+') || eqc(c, '.')
49	
50	def head_word(s: String) -> Bool:
51	  match s:
52	    case SNil{}:
53	      False{}
54	    case SCon{+c, t}:
55	      is_word(c)
56	
57	# Leading run of word characters.
58	def span_word(s: String, ok: Bool) -> Nat:
59	  match s ok:
60	    case SCon{c, +t} True{}:
61	      1n+span_word(t, head_word(t))
62	    case _ _:
63	      0n
64	
65	# Chars through the closing quote (or to the end when it is missing).
66	def span_str(s: String, live: Bool, +esc: Bool) -> Nat:
67	  match s live:
68	    case SCon{+c, t} True{}:
69	      1n+span_str(t, not(not(esc) && eqc(c, '"')), not(esc) && eqc(c, '\\'))
70	    case _ _:
71	      0n
72	
73	def num.next2(+st: U32, +d: Bool, +z: Bool, +dot: Bool, +ex: Bool, +sign: Bool, +minus: Bool) -> U32:
74	  sel(U32.is_eq(st, 0), sel(minus, 1, sel(z, 2, sel(d, 3, 99))),
75	  sel(U32.is_eq(st, 1), sel(d, sel(z, 2, 3), 99),
76	  sel(U32.is_eq(st, 2), sel(dot, 4, sel(ex, 6, 99)),
77	  sel(U32.is_eq(st, 3), sel(d, 3, sel(dot, 4, sel(ex, 6, 99))),
78	  sel(U32.is_eq(st, 4), sel(d, 5, 99),
79	  sel(U32.is_eq(st, 5), sel(d, 5, sel(ex, 6, 99)),
80	  sel(U32.is_eq(st, 6), sel(sign, 7, sel(d, 8, 99)),
81	  sel(U32.is_eq(st, 7), sel(d, 8, 99),
82	  sel(U32.is_eq(st, 8), sel(d, 8, 99), 99)))))))))
83	
84	# JSON number grammar as a state machine: 0 start, 1 after -, 2 after 0,
85	# 3 int digits, 4 after ., 5 frac digits, 6 after e, 7 after exp sign,
86	# 8 exp digits, 99 dead. 2, 3, 5 and 8 accept.
87	def num.next(+st: U32, +c: Char) -> U32:
88	  num.next2(st, Char.is_digit(c), eqc(c, '0'), eqc(c, '.'), eqc(c, 'e') || eqc(c, 'E'), eqc(c, '-') || eqc(c, '+'), eqc(c, '-'))
89	
90	def num.run(s: String, +st: U32) -> U32:
91	  match s:
92	    case SNil{}:
93	      st
94	    case SCon{c, t}:
95	      num.run(t, num.next(st, c))
96	
97	def num.acc(+st: U32) -> Bool:
98	  U32.is_eq(st, 2) || U32.is_eq(st, 3) || U32.is_eq(st, 5) || U32.is_eq(st, 8)
99	
100	def num.ok(+s: String) -> Bool:
101	  num.acc(num.run(s, 0))
102	
103	# What a bare word is: null, true, false, a number, or an error.
104	def word.num(ok: Bool, w: String) -> Tok:
105	  match ok:
106	    case True{}:
107	      TNum{w}
108	    case False{}:
109	      TErr{"bad literal: " ++ w}
110	
111	def word.pick(n: Bool, t: Bool, f: Bool, special: Bool, +w: String) -> Tok:
112	  match n t f special:
113	    case True{} _ _ _:
114	      TNull{}
115	    case False{} True{} _ _:
116	      TTrue{}
117	    case False{} False{} True{} _:
118	      TFalse{}
119	    case False{} False{} False{} True{}:
120	      TNum{w}
121	    case False{} False{} False{} False{}:
122	      word.num(num.ok(w), w)
123	
124	def word.tok(+w: String) -> Tok:
125	  word.pick(String.eq(w, "null"), String.eq(w, "true"), String.eq(w, "false"),
126	    String.eq(w, "NaN") || String.eq(w, "Infinity") || String.eq(w, "-Infinity"), w)
127	
128	# ---- string escapes ----------------------------------------------------------
129	
130	def hv(+c: U32) -> U32:
131	  sel(U32.is_ge(c, 48) && U32.is_le(c, 57), (c - 48 : U32),
132	  sel(U32.is_ge(c, 97) && U32.is_le(c, 102), (c - 87 : U32),
133	  sel(U32.is_ge(c, 65) && U32.is_le(c, 70), (c - 55 : U32), 99)))
134	
135	# Code of the char at index i; 0 past the end.
136	def cc.pick(m: Maybe<&2, Char>) -> U32:
137	  match m:
138	    case None{}:
139	      0
140	    case Some{Chr{c}}:
141	      c
142	
143	def cc(+s: String, i: Nat) -> U32:
144	  cc.pick(String.get(s, i))
145	
146	def hex4.fin(+a: U32, +b: U32, +c: U32, +d: U32) -> U32:
147	  sel(U32.is_lt(a, 16) && U32.is_lt(b, 16) && U32.is_lt(c, 16) && U32.is_lt(d, 16),
148	    (a * 4096 + b * 256 + c * 16 + d : U32), 65533)
149	
150	# The four hex digits at the head of s as a number; U+FFFD when malformed.
151	def hex4(+s: String) -> U32:
152	  hex4.fin(hv(cc(s, 0n)), hv(cc(s, 1n)), hv(cc(s, 2n)), hv(cc(s, 3n)))
153	
154	def is_hi(+u: U32) -> Bool:
155	  U32.is_ge(u, 55296) && U32.is_le(u, 56319)
156	
157	def is_lo(+u: U32) -> Bool:
158	  U32.is_ge(u, 56320) && U32.is_le(u, 57343)
159	
160	# After \uD83D: is the next escape a \uDC00..\uDFFF low half?
161	def pair.ok(+u1: U32, +t5: String) -> Bool:
162	  is_hi(u1) && U32.is_eq(cc(t5, 0n), 92) && U32.is_eq(cc(t5, 1n), 117) && is_lo(hex4(String.drop(t5, 2n)))
163	
164	def pair.cp(+u1: U32, +t5: String) -> U32:
165	  (65536 + ((u1 - 55296) << 10n) + (hex4(String.drop(t5, 2n)) - 56320) : U32)
166	
167	def esc.u2(+u1: U32, +t5: String) -> U32:
168	  sel(pair.ok(u1, t5), pair.cp(u1, t5), u1)
169	
170	def esc.u(+t: String) -> U32:
171	  esc.u2(hex4(String.drop(t, 1n)), String.drop(t, 5n))
172	
173	def esc.cp2(+e: U32, +t: String) -> U32:
174	  sel(U32.is_eq(e, 34) || U32.is_eq(e, 92) || U32.is_eq(e, 47), e,
175	  sel(U32.is_eq(e, 98), 8,
176	  sel(U32.is_eq(e, 102), 12,
177	  sel(U32.is_eq(e, 110), 10,
178	  sel(U32.is_eq(e, 114), 13,
179	  sel(U32.is_eq(e, 116), 9,
180	  sel(U32.is_eq(e, 117), esc.u(t), 65533)))))))
181	
182	# The code point a char (or the escape it starts) stands for.
183	def esc.cp(+c: U32, +t: String) -> U32:
184	  sel(U32.is_eq(c, 92), esc.cp2(cc(t, 0n), t), c)
185	
186	def esc.sk2(+e: U32, +t: String) -> U32:
187	  sel(U32.is_eq(e, 117), sel(pair.ok(hex4(String.drop(t, 1n)), String.drop(t, 5n)), 11, 5), 1)
188	
189	# Chars after the first that the escape consumes.
190	def esc.skip(+c: U32, +t: String) -> Nat:
191	  U32.to_nat(sel(U32.is_eq(c, 92), esc.sk2(cc(t, 0n), t), 0))
192	
193	# Decode the escapes of a string body. `fuel` is its length.
194	def unescape(fuel: Nat, s: String) -> String:
195	  match fuel s:
196	    case _ SNil{}:
197	      SNil{}
198	    case 0n _:
199	      SNil{}
200	    case 1n+p SCon{Chr{+c}, +t}:
201	      SCon{Chr{esc.cp(c, t)}, unescape(p, String.drop(t, esc.skip(c, t)))}
202	
203	# ---- lexer -------------------------------------------------------------------
204	
205	def str.closed(s: String, live: Bool, +esc: Bool) -> Bool:
206	  match s live:
207	    case SCon{+c, t} True{}:
208	      str.closed(t, not(not(esc) && eqc(c, '"')), not(esc) && eqc(c, '\\'))
209	    case _ l:
210	      not(l)
211	
212	def str.pick(closed: Bool, +body: String) -> Tok:
213	  match closed:
214	    case True{}:
215	      TStr{unescape(String.length(body), body)}
216	    case False{}:
217	      TErr{"unterminated string"}
218	
219	# t follows the opening quote.
220	def str.tok(+t: String) -> Tok:
221	  str.pick(str.closed(t, True{}, False{}), String.take(t, Nat.sub(span_str(t, True{}, False{}), 1n)))
222	
223	def tk.sel(c: Bool, t: Tok, rest: Tok) -> Tok:
224	  match c:
225	    case True{}:
226	      t
227	    case False{}:
228	      rest
229	
230	def punct.pick(lb: Bool, rb: Bool, ls: Bool, rs: Bool, co: Bool, cm: Bool, ws: Bool) -> Tok:
231	  tk.sel(lb, TLBrace{}, tk.sel(rb, TRBrace{}, tk.sel(ls, TLBrack{}, tk.sel(rs, TRBrack{}, tk.sel(co, TColon{}, tk.sel(cm, TComma{}, tk.sel(ws, TSkip{}, TErr{"unexpected character"})))))))
232	
233	def punct.tok(+c: Char) -> Tok:
234	  punct.pick(eqc(c, '{'), eqc(c, '}'), eqc(c, '['), eqc(c, ']'), eqc(c, ':'), eqc(c, ','), Char.is_space(c))
235	
236	def tok.of2(q: Bool, w: Bool, +c: Char, +t: String) -> Tok:
237	  match q w:
238	    case True{} _:
239	      str.tok(t)
240	    case False{} True{}:
241	      word.tok(SCon{c, String.take(t, span_word(t, head_word(t)))})
242	    case False{} False{}:
243	      punct.tok(c)
244	
245	def tok.of(+c: Char, +t: String) -> Tok:
246	  tok.of2(eqc(c, '"'), is_word(c), c, t)
247	
248	def tok.adv(+c: Char, +t: String) -> Nat:
249	  sel.n(eqc(c, '"'), span_str(t, True{}, False{}), sel.n(is_word(c), span_word(t, head_word(t)), 0n))
250	
251	def tok.cons(t: Tok, rest: List<&2, Tok>) -> List<&2, Tok>:
252	  match t:
253	    case TSkip{}:
254	      rest
255	    case _:
256	      t <> rest
257	
258	# Tokens of s. `fuel` is its length.
259	def lex(fuel: Nat, s: String) -> List<&2, Tok>:
260	  match fuel s:
261	    case _ SNil{}:
262	      []
263	    case 0n _:
264	      [TErr{"internal: lexer out of fuel"}]
265	    case 1n+p SCon{+c, +t}:
266	      tok.cons(tok.of(c, t), lex(p, String.drop(t, tok.adv(c, t))))
267	
268	# 11 { 12 [ 21 } 22 ] 3 , 0 anything else.