src/syntax/lex.bend

bolt@1.27.0.0 · 394 lines · 31 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.27.0.0/src/rchars.bend as Rchars
33import bolt@1.27.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{}