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.
31	import Base
32	import ../rchars.bend as Rchars
33	import ../lazy/lazy.bend as Lazy
34	
35	# the kinds; TName is a plain name (lowercase, undotted): what a pattern can
36	# bind
37	type 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
62	type Tok is Data:
63	  Tok{kind: TokKind, text: String, line: U32, col: U32}
64	
65	# what a char is, for the machine
66	type 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
83	type 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
96	type 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.
104	def 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
126	def 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?
132	def 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
174	def 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
192	def 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	
215	def 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
241	def word(buf: List<&2, Char>) -> String:
242	  Rchars.text(buf)
243	
244	# is the text one of Bend's keywords?
245	def 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?
251	def 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
259	def 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
266	def 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
276	def 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
286	def 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
291	def 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
297	def 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
308	def 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
316	def 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
321	def 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
325	def 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
333	def text(toks: List<&2, Tok>) -> String:
334	  String.concat(List.reverse(&2, String, text.go(toks, [])))
335	
336	# an opening bracket?
337	def is_open(kk: TokKind) -> Bool:
338	  match kk:
339	    case TOpen{}:
340	      True{}
341	    case other:
342	      False{}
343	
344	# a comma?
345	def 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, `_`
353	def 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?
369	def 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
377	def 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?
389	def is_str(kk: TokKind) -> Bool:
390	  match kk:
391	    case TStr{}:
392	      True{}
393	    case other:
394	      False{}