json/lex.bend

cswap-bend-cli@0.1.0.0 · 268 lines · 45 definitions

1import Base
2
3type 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
18def sel(c: Bool, x: U32, y: U32) -> U32:
19  match c:
20    case True{}:
21      x
22    case False{}:
23      y
24
25def sel.s(c: Bool, x: String, y: String) -> String:
26  match c:
27    case True{}:
28      x
29    case False{}:
30      y
31
32def sel.n(c: Bool, x: Nat, y: Nat) -> Nat:
33  match c:
34    case True{}:
35      x
36    case False{}:
37      y
38
39def not(b: Bool) -> Bool:
40  Bool.not(b)
41
42def eqc(+c: Char, +d: Char) -> Bool:
43  Char.is_eq(c, d)
44
45# ---- characters and numbers --------------------------------------------------
46
47def is_word(+c: Char) -> Bool:
48  Char.is_digit(c) || Char.is_alpha(c) || eqc(c, '-') || eqc(c, '+') || eqc(c, '.')
49
50def 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.
58def 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).
66def 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
73def 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.
87def 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
90def 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
97def 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
100def 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.
104def 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
111def 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
124def 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
130def 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.
136def cc.pick(m: Maybe<&2, Char>) -> U32:
137  match m:
138    case None{}:
139      0
140    case Some{Chr{c}}:
141      c
142
143def cc(+s: String, i: Nat) -> U32:
144  cc.pick(String.get(s, i))
145
146def 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.
151def hex4(+s: String) -> U32:
152  hex4.fin(hv(cc(s, 0n)), hv(cc(s, 1n)), hv(cc(s, 2n)), hv(cc(s, 3n)))
153
154def is_hi(+u: U32) -> Bool:
155  U32.is_ge(u, 55296) && U32.is_le(u, 56319)
156
157def 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?
161def 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
164def pair.cp(+u1: U32, +t5: String) -> U32:
165  (65536 + ((u1 - 55296) << 10n) + (hex4(String.drop(t5, 2n)) - 56320) : U32)
166
167def esc.u2(+u1: U32, +t5: String) -> U32:
168  sel(pair.ok(u1, t5), pair.cp(u1, t5), u1)
169
170def esc.u(+t: String) -> U32:
171  esc.u2(hex4(String.drop(t, 1n)), String.drop(t, 5n))
172
173def 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.
183def esc.cp(+c: U32, +t: String) -> U32:
184  sel(U32.is_eq(c, 92), esc.cp2(cc(t, 0n), t), c)
185
186def 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.
190def 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.
194def 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
205def 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
212def 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.
220def 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
223def tk.sel(c: Bool, t: Tok, rest: Tok) -> Tok:
224  match c:
225    case True{}:
226      t
227    case False{}:
228      rest
229
230def 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
233def 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
236def 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
245def tok.of(+c: Char, +t: String) -> Tok:
246  tok.of2(eqc(c, '"'), is_word(c), c, t)
247
248def 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
251def 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.
259def 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.