src/syntax/lex.bend
bolt@1.11.0.0 · 379 lines · 0 definitions
1# src/syntax/lex: a source as tokens with positions. Lossless: every char lands
2# in exactly one token, so the texts concatenate back to the source, whatever
3# the source is. A string runs to its closing quote across newlines, as in
4# bend, so an unclosed one runs to the end of the file (bend rejects that
5# file). A char literal and a comment end at their line's end. One char per
6# step, a tail-recursive state machine.
7#
8# A name is letters, digits, `_` and `.` (`List.map`, `M.go`). Operator chars
9# group into runs (`->`, `<-`, `=>`, `==`, `++`), except `:`, which always
10# stands alone: `List<U32>:` must not read `>:`.
11#
12# Kinds tell apart what binds from what does not, so a walk over the tokens
13# can branch by constructor: a keyword (TKey), a dotted name (TDotted: never
14# a binder), a capitalized one (TUpper: a constructor before `{`, a type, or
15# a binder), `_` (TWild), and the operators that bind: `:` `=` `<-` `->` `=>`
16# `@` `&`.
17import Base
18import bolt@1.11.0.0/src/lazy/lazy.bend as Lazy
19
20# the kinds; TName is a plain name (lowercase, undotted): what a pattern can
21# bind
22type TokKind is Data:
23 TName{}
24 TUpper{}
25 TDotted{}
26 TWild{}
27 TKey{}
28 TNum{}
29 TStr{}
30 TChar{}
31 TComment{}
32 TSpace{}
33 TNewline{}
34 TOp{}
35 TColon{}
36 TEq{}
37 TBind{}
38 TArrow{}
39 TLam{}
40 TAll{}
41 TAmp{}
42 TOpen{}
43 TClose{}
44 TComma{}
45
46# line and col are 0-based, of the token's first char
47type Tok is Data:
48 Tok{kind: TokKind, text: String, line: U32, col: U32}
49
50# what a char is, for the machine
51type Class is Data:
52 CAlpha{}
53 CDigit{}
54 CDot{}
55 CQuote{}
56 CTick{}
57 CBack{}
58 CHash{}
59 CSpace{}
60 CNewline{}
61 COp{}
62 CColon{}
63 COpen{}
64 CClose{}
65 CComma{}
66
67# what the machine is inside of; Fresh: the next char starts a token
68type Mode is Data:
69 Fresh{}
70 InName{}
71 InNum{}
72 InStr{}
73 InStrEsc{}
74 InChar{}
75 InCharEsc{}
76 InComment{}
77 InSpace{}
78 InOp{}
79
80# buf and toks are reversed; (sl, sc) is where the current token started
81type St is Data:
82 St{mode: Mode, kind: TokKind, line: U32, col: U32, sl: U32, sc: U32, buf: List<&2, Char>, toks: List<&2, Tok>}
83
84# the class of a code point, given the class any other character would get.
85# Written as comparisons rather than as `case '.':` arms: a character literal
86# in a pattern is a U32 literal inside a constructor pattern, and bend's C
87# backend pays about 90 MB for each one -- these eighteen cost 1.57 GB as
88# literal arms and 0.10 GB written this way.
89def classify.go(+xx: U32, other: Class) -> Class:
90 Bool.pick(Class, U32.is_eq(xx, 46), CDot{}, # '.'
91 Bool.pick(Class, U32.is_eq(xx, 34), CQuote{}, # '"'
92 Bool.pick(Class, U32.is_eq(xx, 39), CTick{}, # '\''
93 Bool.pick(Class, U32.is_eq(xx, 92), CBack{}, # '\\'
94 Bool.pick(Class, U32.is_eq(xx, 35), CHash{}, # '#'
95 Bool.pick(Class, U32.is_eq(xx, 32), CSpace{}, # ' '
96 Bool.pick(Class, U32.is_eq(xx, 9), CSpace{}, # '\t'
97 Bool.pick(Class, U32.is_eq(xx, 13), CSpace{}, # '\r'
98 Bool.pick(Class, U32.is_eq(xx, 10), CNewline{}, # '\n'
99 Bool.pick(Class, U32.is_eq(xx, 58), CColon{}, # ':'
100 Bool.pick(Class, U32.is_eq(xx, 44), CComma{}, # ','
101 Bool.pick(Class, U32.is_eq(xx, 40), COpen{}, # '('
102 Bool.pick(Class, U32.is_eq(xx, 91), COpen{}, # '['
103 Bool.pick(Class, U32.is_eq(xx, 123), COpen{}, # '{'
104 Bool.pick(Class, U32.is_eq(xx, 41), CClose{}, # ')'
105 Bool.pick(Class, U32.is_eq(xx, 93), CClose{}, # ']'
106 Bool.pick(Class, U32.is_eq(xx, 125), CClose{}, # '}'
107 Bool.pick(Class, U32.is_eq(xx, 95), CAlpha{}, # '_'
108 other))))))))))))))))))
109
110# a char's class
111def classify(+cc: Char) -> Class:
112 +other = Bool.pick(Class, Char.is_alpha(cc), CAlpha{},
113 Bool.pick(Class, Char.is_digit(cc), CDigit{}, COp{}))
114 classify.go(Char.to_u32(cc), other)
115
116# does a char of this class continue the token the machine is inside of?
117def continues(mm: Mode, cls: Class) -> Bool:
118 match mm cls:
119 case Fresh{} c:
120 False{}
121 case InName{} CAlpha{}:
122 True{}
123 case InName{} CDigit{}:
124 True{}
125 case InName{} CDot{}:
126 True{}
127 case InNum{} CDigit{}:
128 True{}
129 case InNum{} CDot{}:
130 True{}
131 case InNum{} CAlpha{}:
132 True{}
133 case InStr{} c:
134 True{}
135 case InStrEsc{} c:
136 True{}
137 case InChar{} CNewline{}:
138 False{}
139 case InChar{} c:
140 True{}
141 case InCharEsc{} CNewline{}:
142 False{}
143 case InCharEsc{} c:
144 True{}
145 case InComment{} CNewline{}:
146 False{}
147 case InComment{} c:
148 True{}
149 case InSpace{} CSpace{}:
150 True{}
151 case InOp{} COp{}:
152 True{}
153 case InOp{} CDot{}:
154 True{}
155 case m c:
156 False{}
157
158# the mode after a char that continued the token
159def after(mm: Mode, cls: Class) -> Mode:
160 match mm cls:
161 case InStr{} CQuote{}:
162 Fresh{}
163 case InStr{} CBack{}:
164 InStrEsc{}
165 case InStrEsc{} c:
166 InStr{}
167 case InChar{} CTick{}:
168 Fresh{}
169 case InChar{} CBack{}:
170 InCharEsc{}
171 case InCharEsc{} c:
172 InChar{}
173 case m c:
174 m
175
176# the mode and the kind of the token a char starts
177def begin.mode(cls: Class) -> Mode:
178 match cls:
179 case CAlpha{}:
180 InName{}
181 case CDigit{}:
182 InNum{}
183 case CQuote{}:
184 InStr{}
185 case CTick{}:
186 InChar{}
187 case CHash{}:
188 InComment{}
189 case CSpace{}:
190 InSpace{}
191 case COp{}:
192 InOp{}
193 case CDot{}:
194 InOp{}
195 case CBack{}:
196 InOp{}
197 case other:
198 Fresh{}
199
200def begin.kind(cls: Class) -> TokKind:
201 match cls:
202 case CAlpha{}:
203 TName{}
204 case CDigit{}:
205 TNum{}
206 case CQuote{}:
207 TStr{}
208 case CTick{}:
209 TChar{}
210 case CHash{}:
211 TComment{}
212 case CSpace{}:
213 TSpace{}
214 case CNewline{}:
215 TNewline{}
216 case COpen{}:
217 TOpen{}
218 case CClose{}:
219 TClose{}
220 case CComma{}:
221 TComma{}
222 case other:
223 TOp{}
224
225# the buffered chars as a string, in order
226def word(buf: List<&2, Char>) -> String:
227 String.from_list(List.reverse(&2, Char, buf))
228
229# is the text one of Bend's keywords?
230def is_keyword(+tt: String) -> Bool:
231 List.contains(~String, ~String.eq,
232 ["def", "type", "law", "match", "case", "do", "return", "for", "exs", "where", "is", "import",
233 "Type", "Data", "Kind", "Quant"], tt)
234
235# does the text start with a capital?
236def upper_first(cs: List<&2, Char>) -> Bool:
237 match cs:
238 case Nil{}:
239 False{}
240 case Con{c, t}:
241 Char.is_upper(c)
242
243# a whole name's kind
244def refine_name(+tt: String) -> TokKind:
245 Bool.pick(TokKind, is_keyword(tt), TKey{},
246 Bool.pick(TokKind, String.contains(tt, "."), TDotted{},
247 Bool.pick(TokKind, String.eq(tt, "_"), TWild{},
248 Bool.pick(TokKind, upper_first(String.to_list(tt)), TUpper{}, TName{}))))
249
250# a whole operator's kind
251def refine_op(+tt: String) -> TokKind:
252 Bool.pick(TokKind, String.eq(tt, ":"), TColon{},
253 Bool.pick(TokKind, String.eq(tt, "="), TEq{},
254 Bool.pick(TokKind, String.eq(tt, "<-"), TBind{},
255 Bool.pick(TokKind, String.eq(tt, "->"), TArrow{},
256 Bool.pick(TokKind, String.eq(tt, "=>"), TLam{},
257 Bool.pick(TokKind, Bool.or(String.eq(tt, "@"), Bool.or(String.eq(tt, "@+"), String.eq(tt, "@-"))), TAll{},
258 Bool.pick(TokKind, String.eq(tt, "&"), TAmp{}, TOp{})))))))
259
260# a name's or an operator's kind, once its text is whole
261def refine(kind: TokKind, tt: String) -> TokKind:
262 match kind:
263 case TName{}:
264 refine_name(tt)
265 case TOp{}:
266 refine_op(tt)
267 case other:
268 other
269
270# the token so far joins the others
271def flush(kind: TokKind, sl: U32, sc: U32, +buf: List<&2, Char>, +toks: List<&2, Tok>) -> List<&2, Tok>:
272 +t = word(buf)
273 Bool.pick(List<&2, Tok>, List.is_empty(&2, Char, buf), toks, Tok{refine(kind, t), t, sl, sc} <> toks)
274
275# is the char a line break, '\n'? The one char whose class is CNewline
276def is_newline(cc: Char) -> Bool:
277 U32.is_eq(Char.to_u32(cc), 10)
278
279# one char: it continues the current token, or starts a new one. Only the
280# branch taken is built: the token is flushed (its text reversed, its kind
281# refined) once, where it ends, not on every char of it
282def step(+cc: Char, st: St) -> St:
283 St{+mode, +kind, +line, +col, +sl, +sc, +buf, +toks} = st
284 +cls = classify(cc)
285 +nl = is_newline(cc)
286 +line2 = Bool.pick(U32, nl, (line + 1 : U32), line)
287 +col2 = Bool.pick(U32, nl, 0, (col + 1 : U32))
288 Lazy.either(St, continues(mode, cls),
289 _u => St{after(mode, cls), kind, line2, col2, sl, sc, cc <> buf, toks},
290 _v => St{begin.mode(cls), begin.kind(cls), line2, col2, line, col, [cc], flush(kind, sl, sc, buf, toks)})
291
292# every char, in order
293def run(cs: List<&2, Char>, st: St) -> St:
294 match cs:
295 case Nil{}:
296 st
297 case Con{c, t}:
298 run(t, step(c, st))
299
300# the tokens once the chars are over, the last one flushed
301def finish(st: St) -> List<&2, Tok>:
302 St{mode, kind, line, col, sl, sc, buf, toks} = st
303 List.reverse(&2, Tok, flush(kind, sl, sc, buf, toks))
304
305# a source as tokens
306def tokens(source: String) -> List<&2, Tok>:
307 finish(run(String.to_list(source), St{Fresh{}, TSpace{}, 0, 0, 0, 0, [], []}))
308
309# the tokens' texts, back to back: the source
310def text.go(toks: List<&2, Tok>, acc: List<&2, String>) -> List<&2, String>:
311 match toks:
312 case Nil{}:
313 acc
314 case Con{Tok{k, t, l, c}, rest}:
315 text.go(rest, t <> acc)
316
317# the tokens' texts, back to back: the source
318def text(toks: List<&2, Tok>) -> String:
319 String.concat(List.reverse(&2, String, text.go(toks, [])))
320
321# an opening bracket?
322def is_open(kk: TokKind) -> Bool:
323 match kk:
324 case TOpen{}:
325 True{}
326 case other:
327 False{}
328
329# a comma?
330def is_comma(kk: TokKind) -> Bool:
331 match kk:
332 case TComma{}:
333 True{}
334 case other:
335 False{}
336
337# any identifier: a name, a keyword, a dotted or a capitalized one, `_`
338def is_name(kk: TokKind) -> Bool:
339 match kk:
340 case TName{}:
341 True{}
342 case TUpper{}:
343 True{}
344 case TDotted{}:
345 True{}
346 case TWild{}:
347 True{}
348 case TKey{}:
349 True{}
350 case other:
351 False{}
352
353# a newline?
354def is_nl(kk: TokKind) -> Bool:
355 match kk:
356 case TNewline{}:
357 True{}
358 case other:
359 False{}
360
361# not space, a newline or a comment
362def significant(kk: TokKind) -> Bool:
363 match kk:
364 case TSpace{}:
365 False{}
366 case TNewline{}:
367 False{}
368 case TComment{}:
369 False{}
370 case other:
371 True{}
372
373# a string literal?
374def is_str(kk: TokKind) -> Bool:
375 match kk:
376 case TStr{}:
377 True{}
378 case other:
379 False{}