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