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