src/lex.bend

emerging-ezjson@1.3.0.0 · 419 lines · 50 definitions

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.
3import Base
4
5# the tokens: brackets, `:`, `,`, a string (decoded), or a bare word
6# (a number, true, false, null)
7type 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
22type 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
31type 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
43type Sur is Data:
44  SOk{}
45  SHi{}
46  SLo{}
47
48# the lexer's state: buf and toks are both reversed
49type 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.
55def 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
71def 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
75def 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
83def text(buf: List<&2, Char>) -> String:
84  text.go(buf, "")
85
86def 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
98def unescape(+ch: Char) -> Maybe<&2, Char>:
99  unescape.go(Char.to_u32(ch))
100
101def 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`
109def 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
118def 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
121def 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
127def 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
132def 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
139def 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
146def unicode.sur(+cp: U32) -> Sur:
147  unicode.sur.hi(cp, U32.is_ge(cp, 55296), U32.is_le(cp, 56319))
148
149def 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
152def 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
161def unicode.end(+cp: U32, buf: List<&2, Char>, toks: List<&2, Tok>) -> Lex:
162  unicode.end.go(cp, buf, toks, unicode.sur(cp))
163
164def 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
171def 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
179def 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
182def 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
189def 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
192def 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
199def 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
214def 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
217def 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
224def 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
227def 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
234def 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
237def 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
244def 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
248def 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
290def 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
295def 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
304def 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
315def 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
324def 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
332type 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
340type Scan is Data:
341  Go{cut: String, n: U32, mode: Span, toks: List<&2, Tok>}
342  Old{st: Lex}
343
344def 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
386def 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
395def 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
402def 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
410def 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
418def tokens(txt: String) -> List<&2, Tok>:
419  tokens.go(txt, Go{"", 0, GIdle{}, []})