1	# src/lex: a JSON text as tokens. A string is decoded: \", \\, \/, \b, \f,
2	# \n, \r, \t, and \uXXXX. A \u escape of a surrogate pair is one code point.
3	import Base
4	
5	# the tokens: brackets, `:`, `,`, a string (decoded), or a bare word
6	# (a number, true, false, null)
7	type Tok is Data:
8	  TOpenArr{}
9	  TCloseArr{}
10	  TOpenObj{}
11	  TCloseObj{}
12	  TColon{}
13	  TComma{}
14	  TStr{s: String}
15	  TWord{raw: String}
16	  TStrS{src: String, n: U32}
17	  TWordS{src: String, n: U32}
18	  TBad{}
19	
20	# what a char is: punctuation (with its token), a quote, whitespace, or a
21	# word char
22	type Class is Data:
23	  CPunct{t: Tok}
24	  CQuote{}
25	  CBack{}
26	  CSpace{}
27	  COther{}
28	
29	# what the machine is inside of: nothing, a bare word, a string, an escape,
30	# a \u escape, a high surrogate waiting for its pair, or a rejected text
31	type Mode is Data:
32	  Idle{}
33	  Word{}
34	  Str{}
35	  Esc{}
36	  Uni{left: Nat, acc: U32}
37	  Hi{hi: U32}
38	  HiEsc{hi: U32}
39	  Lo{left: Nat, acc: U32, hi: U32}
40	  Bad{}
41	
42	# a \u code point: an ordinary scalar, a high surrogate, or a low surrogate
43	type Sur is Data:
44	  SOk{}
45	  SHi{}
46	  SLo{}
47	
48	# the lexer's state: buf and toks are both reversed
49	type Lex is Data:
50	  Lex{mode: Mode, buf: List<&2, Char>, toks: List<&2, Tok>}
51	
52	# a char's class, by code point. Written as comparisons rather than as
53	# `case '[':` arms: a character literal in a pattern is a U32 literal inside a
54	# constructor pattern, and bend's C backend pays about 90 MB for each one.
55	def classify.go(+cp: U32) -> Class:
56	  Bool.pick(Class, U32.is_eq(cp, 91), CPunct{TOpenArr{}},  # '['
57	  Bool.pick(Class, U32.is_eq(cp, 93), CPunct{TCloseArr{}},  # ']'
58	  Bool.pick(Class, U32.is_eq(cp, 123), CPunct{TOpenObj{}},  # '{'
59	  Bool.pick(Class, U32.is_eq(cp, 125), CPunct{TCloseObj{}},  # '}'
60	  Bool.pick(Class, U32.is_eq(cp, 58), CPunct{TColon{}},  # ':'
61	  Bool.pick(Class, U32.is_eq(cp, 44), CPunct{TComma{}},  # ','
62	  Bool.pick(Class, U32.is_eq(cp, 34), CQuote{},  # '"'
63	  Bool.pick(Class, U32.is_eq(cp, 92), CBack{},  # '\\'
64	  Bool.pick(Class, U32.is_eq(cp, 32), CSpace{},  # ' '
65	  Bool.pick(Class, U32.is_eq(cp, 10), CSpace{},  # '\n'
66	  Bool.pick(Class, U32.is_eq(cp, 13), CSpace{},  # '\r'
67	  Bool.pick(Class, U32.is_eq(cp, 9), CSpace{},  # '\t'
68	    COther{}))))))))))))
69	
70	# a char's class
71	def classify(ch: Char) -> Class:
72	  classify.go(Char.to_u32(ch))
73	
74	# the buffer is reversed, so consing each head onto the front yields the text
75	def text.go(buf: List<&2, Char>, acc: String) -> String:
76	  match buf:
77	    case Nil{}:
78	      acc
79	    case Con{h, t}:
80	      text.go(t, SCon{h, acc})
81	
82	# the buffered chars (reversed) as a string
83	def text(buf: List<&2, Char>) -> String:
84	  text.go(buf, "")
85	
86	def unescape.go(+cp: U32) -> Maybe<&2, Char>:
87	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 34), Some{'"'},
88	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 92), Some{'\\'},
89	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 47), Some{'/'},
90	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 98), Some{Char.from_u32(8)},
91	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 102), Some{Char.from_u32(12)},
92	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 110), Some{'\n'},
93	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 114), Some{'\r'},
94	  Bool.pick(Maybe<&2, Char>, U32.is_eq(cp, 116), Some{'\t'},
95	    None{}))))))))
96	
97	# the char an escape stands for; none when the escape is not one JSON allows
98	def unescape(+ch: Char) -> Maybe<&2, Char>:
99	  unescape.go(Char.to_u32(ch))
100	
101	def escape.put(mb: Maybe<&2, Char>, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
102	  match mb:
103	    case Some{ch}:
104	      Lex{Str{}, ch <> buf, toks}
105	    case None{}:
106	      Lex{Bad{}, [], toks}
107	
108	# the char after a backslash, once it is known whether it is `u`
109	def escape.go(ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>, is_u: Bool) -> Lex:
110	  match is_u:
111	    case True{}:
112	      Lex{Uni{3n, 0}, buf, toks}
113	    case False{}:
114	      escape.put(unescape(ch), buf, toks)
115	
116	# the char after a backslash in a string. Tested by code point, not with a
117	# `case 'u':` arm, for the reason `classify` gives
118	def escape(+ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
119	  escape.go(ch, buf, toks, U32.is_eq(Char.to_u32(ch), 117))
120	
121	def hex.ok(+cp: U32) -> Bool:
122	  Bool.or(Bool.and(U32.is_ge(cp, 48), U32.is_le(cp, 57)),
123	    Bool.or(Bool.and(U32.is_ge(cp, 65), U32.is_le(cp, 70)),
124	      Bool.and(U32.is_ge(cp, 97), U32.is_le(cp, 102))))
125	
126	# a hex digit's value
127	def hex(ch: Char) -> U32:
128	  +x = Char.to_u32(ch)
129	  Bool.pick(U32, U32.is_le(x, 57), (x - 48 : U32),
130	    Bool.pick(U32, U32.is_ge(x, 97), (x - 87 : U32), (x - 55 : U32)))
131	
132	def unicode.sur.lo(ge: Bool, le: Bool) -> Sur:
133	  match ge le:
134	    case True{} True{}:
135	      SLo{}
136	    case a b:
137	      SOk{}
138	
139	def unicode.sur.hi(+cp: U32, ge: Bool, le: Bool) -> Sur:
140	  match ge le:
141	    case True{} True{}:
142	      SHi{}
143	    case a b:
144	      unicode.sur.lo(U32.is_ge(cp, 56320), U32.is_le(cp, 57343))
145	
146	def unicode.sur(+cp: U32) -> Sur:
147	  unicode.sur.hi(cp, U32.is_ge(cp, 55296), U32.is_le(cp, 56319))
148	
149	def unicode.pair(hi: U32, lo: U32) -> U32:
150	  U32.add(65536, U32.add(U32.mul(U32.sub(hi, 55296), 1024), U32.sub(lo, 56320)))
151	
152	def unicode.end.go(cp: U32, buf: List<&2, Char>, toks: List<&2, Tok>, key: Sur) -> Lex:
153	  match key:
154	    case SOk{}:
155	      Lex{Str{}, Char.from_u32(cp) <> buf, toks}
156	    case SHi{}:
157	      Lex{Hi{cp}, buf, toks}
158	    case SLo{}:
159	      Lex{Bad{}, [], toks}
160	
161	def unicode.end(+cp: U32, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
162	  unicode.end.go(cp, buf, toks, unicode.sur(cp))
163	
164	def unicode.put(left: Nat, acc: U32, dig: U32, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
165	  match left:
166	    case 0n:
167	      unicode.end((acc * 16 + dig : U32), buf, toks)
168	    case 1n+p:
169	      Lex{Uni{p, (acc * 16 + dig : U32)}, buf, toks}
170	
171	def unicode.go(left: Nat, acc: U32, ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>, ok: Bool) -> Lex:
172	  match ok:
173	    case True{}:
174	      unicode.put(left, acc, hex(ch), buf, toks)
175	    case False{}:
176	      Lex{Bad{}, [], toks}
177	
178	# one hex digit of a \uXXXX escape; the code point once four are in
179	def unicode(left: Nat, acc: U32, +ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
180	  unicode.go(left, acc, ch, buf, toks, hex.ok(Char.to_u32(ch)))
181	
182	def unicode.low.end.go(lo: U32, hi: U32, buf: List<&2, Char>, toks: List<&2, Tok>, key: Sur) -> Lex:
183	  match key:
184	    case SLo{}:
185	      Lex{Str{}, Char.from_u32(unicode.pair(hi, lo)) <> buf, toks}
186	    case other:
187	      Lex{Bad{}, [], toks}
188	
189	def unicode.low.end(+lo: U32, hi: U32, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
190	  unicode.low.end.go(lo, hi, buf, toks, unicode.sur(lo))
191	
192	def unicode.low.put(left: Nat, acc: U32, hi: U32, dig: U32, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
193	  match left:
194	    case 0n:
195	      unicode.low.end((acc * 16 + dig : U32), hi, buf, toks)
196	    case 1n+p:
197	      Lex{Lo{p, (acc * 16 + dig : U32), hi}, buf, toks}
198	
199	def unicode.low.go(
200	  left: Nat,
201	  acc: U32,
202	  hi: U32,
203	  ch: Char,
204	  buf: List<&2, Char>,
205	  toks: List<&2, Tok>,
206	  ok: Bool
207	) -> Lex:
208	  match ok:
209	    case True{}:
210	      unicode.low.put(left, acc, hi, hex(ch), buf, toks)
211	    case False{}:
212	      Lex{Bad{}, [], toks}
213	
214	def unicode.low(left: Nat, acc: U32, hi: U32, +ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
215	  unicode.low.go(left, acc, hi, ch, buf, toks, hex.ok(Char.to_u32(ch)))
216	
217	def step.str.go(ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>, ctrl: Bool) -> Lex:
218	  match ctrl:
219	    case True{}:
220	      Lex{Bad{}, [], toks}
221	    case False{}:
222	      Lex{Str{}, ch <> buf, toks}
223	
224	def step.str(+ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
225	  step.str.go(ch, buf, toks, U32.is_lt(Char.to_u32(ch), 32))
226	
227	def step.hi.go(hi: U32, buf: List<&2, Char>, toks: List<&2, Tok>, slash: Bool) -> Lex:
228	  match slash:
229	    case True{}:
230	      Lex{HiEsc{hi}, buf, toks}
231	    case False{}:
232	      Lex{Bad{}, [], toks}
233	
234	def step.hi(hi: U32, ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
235	  step.hi.go(hi, buf, toks, U32.is_eq(Char.to_u32(ch), 92))
236	
237	def step.hiesc.go(hi: U32, buf: List<&2, Char>, toks: List<&2, Tok>, is_u: Bool) -> Lex:
238	  match is_u:
239	    case True{}:
240	      Lex{Lo{3n, 0, hi}, buf, toks}
241	    case False{}:
242	      Lex{Bad{}, [], toks}
243	
244	def step.hiesc(hi: U32, ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
245	  step.hiesc.go(hi, buf, toks, U32.is_eq(Char.to_u32(ch), 117))
246	
247	# one char, by the mode and the char's class
248	def step(mode: Mode, cls: Class, ch: Char, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
249	  match mode cls:
250	    case Idle{} CPunct{t}:
251	      Lex{Idle{}, [], t <> toks}
252	    case Idle{} CQuote{}:
253	      Lex{Str{}, [], toks}
254	    case Idle{} CSpace{}:
255	      Lex{Idle{}, [], toks}
256	    case Idle{} CBack{}:
257	      Lex{Bad{}, [], toks}
258	    case Idle{} COther{}:
259	      Lex{Word{}, [ch], toks}
260	    case Word{} CPunct{t}:
261	      Lex{Idle{}, [], t <> TWord{text(buf)} <> toks}
262	    case Word{} CQuote{}:
263	      Lex{Str{}, [], TWord{text(buf)} <> toks}
264	    case Word{} CSpace{}:
265	      Lex{Idle{}, [], TWord{text(buf)} <> toks}
266	    case Word{} CBack{}:
267	      Lex{Bad{}, [], toks}
268	    case Word{} COther{}:
269	      Lex{Word{}, ch <> buf, toks}
270	    case Str{} CQuote{}:
271	      Lex{Idle{}, [], TStr{text(buf)} <> toks}
272	    case Str{} CBack{}:
273	      Lex{Esc{}, buf, toks}
274	    case Str{} other:
275	      step.str(ch, buf, toks)
276	    case Esc{} other:
277	      escape(ch, buf, toks)
278	    case Uni{left, acc} other:
279	      unicode(left, acc, ch, buf, toks)
280	    case Hi{hi} other:
281	      step.hi(hi, ch, buf, toks)
282	    case HiEsc{hi} other:
283	      step.hiesc(hi, ch, buf, toks)
284	    case Lo{left, acc, hi} other:
285	      unicode.low(left, acc, hi, ch, buf, toks)
286	    case Bad{} other:
287	      Lex{Bad{}, [], toks}
288	
289	# one char into the machine
290	def feed(+ch: Char, st: Lex) -> Lex:
291	  Lex{mode, buf, toks} = st
292	  step(mode, classify(ch), ch, buf, toks)
293	
294	# every char, in order
295	def run(cs: List<&2, Char>, st: Lex) -> Lex:
296	  match cs:
297	    case Nil{}:
298	      st
299	    case Con{c, t}:
300	      run(t, feed(c, st))
301	
302	# the tokens, in order; text that ends inside a string or a word ends in TBad
303	# when the string was not closed
304	def finish(st: Lex) -> List<&2, Tok>:
305	  Lex{mode, buf, toks} = st
306	  match mode:
307	    case Idle{}:
308	      List.reverse(&2, Tok, toks)
309	    case Word{}:
310	      List.reverse(&2, Tok, TWord{text(buf)} <> toks)
311	    case other:
312	      List.reverse(&2, Tok, TBad{} <> toks)
313	
314	# the first n chars of src, reversed, for the escape fallback's buffer
315	def tokens.rev(src: String, +nn: U32, zero: Bool, acc: List<&2, Char>) -> List<&2, Char>:
316	  match src zero:
317	    case s True{}:
318	      acc
319	    case SNil{} False{}:
320	      acc
321	    case SCon{h, t} False{}:
322	      tokens.rev(t, U32.sub(nn, 1), U32.is_zero(U32.sub(nn, 1)), h <> acc)
323	
324	def tokens.push(cut: String, nn: U32, word: Bool, toks: List<&2, Tok>) -> List<&2, Tok>:
325	  match word:
326	    case True{}:
327	      TWordS{cut, nn} <> toks
328	    case False{}:
329	      TStrS{cut, nn} <> toks
330	
331	# what the span scanner is inside: nothing, a word, a string, or a rejected text
332	type Span is Data:
333	  GIdle{}
334	  GWord{}
335	  GStr{}
336	  GBad{}
337	
338	# `cut` is the suffix where the open word or string began, so closing it does
339	# not walk the text again. Old means a backslash handed the tail to the copier
340	type Scan is Data:
341	  Go{cut: String, n: U32, mode: Span, toks: List<&2, Tok>}
342	  Old{st: Lex}
343	
344	def tokens.hit(
345	  +ch: Char,
346	  tail: String,
347	  cut: String,
348	  +nn: U32,
349	  mode: Span,
350	  toks: List<&2, Tok>,
351	  cls: Class,
352	  ctrl: Bool
353	) -> Scan:
354	  match mode cls ctrl:
355	    case GIdle{} CSpace{} b:
356	      Go{cut, nn, GIdle{}, toks}
357	    case GIdle{} CPunct{p} b:
358	      Go{cut, nn, GIdle{}, p <> toks}
359	    case GIdle{} CQuote{} b:
360	      Go{tail, 0, GStr{}, toks}
361	    case GIdle{} CBack{} b:
362	      Go{cut, nn, GBad{}, toks}
363	    case GIdle{} COther{} b:
364	      Go{SCon{ch, tail}, 1, GWord{}, toks}
365	    case GWord{} COther{} b:
366	      Go{cut, U32.add(nn, 1), GWord{}, toks}
367	    case GWord{} CPunct{p} b:
368	      Go{"", 0, GIdle{}, p <> tokens.push(cut, nn, True{}, toks)}
369	    case GWord{} CQuote{} b:
370	      Go{tail, 0, GStr{}, tokens.push(cut, nn, True{}, toks)}
371	    case GWord{} CBack{} b:
372	      Go{cut, nn, GBad{}, toks}
373	    case GWord{} k b:
374	      Go{"", 0, GIdle{}, tokens.push(cut, nn, True{}, toks)}
375	    case GStr{} k True{}:
376	      Go{cut, nn, GBad{}, toks}
377	    case GStr{} CQuote{} False{}:
378	      Go{"", 0, GIdle{}, tokens.push(cut, nn, False{}, toks)}
379	    case GStr{} CBack{} False{}:
380	      Old{feed('\\', Lex{Str{}, tokens.rev(cut, nn, U32.is_zero(nn), []), toks})}
381	    case GStr{} k False{}:
382	      Go{cut, U32.add(nn, 1), GStr{}, toks}
383	    case GBad{} k b:
384	      Go{cut, nn, GBad{}, toks}
385	
386	def tokens.done(cut: String, nn: U32, mode: Span, toks: List<&2, Tok>) -> List<&2, Tok>:
387	  match mode:
388	    case GIdle{}:
389	      List.reverse(&2, Tok, toks)
390	    case GWord{}:
391	      List.reverse(&2, Tok, tokens.push(cut, nn, True{}, toks))
392	    case _:
393	      List.reverse(&2, Tok, TBad{} <> toks)
394	
395	def tokens.end(st: Scan) -> List<&2, Tok>:
396	  match st:
397	    case Old{lex}:
398	      finish(lex)
399	    case Go{cut, n, mode, toks}:
400	      tokens.done(cut, n, mode, toks)
401	
402	def tokens.feed(+ch: Char, tail: String, st: Scan) -> Scan:
403	  match st:
404	    case Old{lex}:
405	      Old{feed(ch, lex)}
406	    case Go{cut, n, mode, toks}:
407	      tokens.hit(ch, tail, cut, n, mode, toks, classify(ch), U32.is_lt(Char.to_u32(ch), 32))
408	
409	# match only the text, so a literal unrolls. The tail is where the next span starts
410	def tokens.go(txt: String, st: Scan) -> List<&2, Tok>:
411	  match txt:
412	    case SNil{}:
413	      tokens.end(st)
414	    case SCon{+c, +t}:
415	      tokens.go(t, tokens.feed(c, t, st))
416	
417	# a text as tokens. Clean words and strings are spans of the text
418	def tokens(txt: String) -> List<&2, Tok>:
419	  tokens.go(txt, Go{"", 0, GIdle{}, []})