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	import Base
18	import ../rchars.bend as Rchars
19	import ../lazy/lazy.bend as Lazy
20	
21	# the kinds; TName is a plain name (lowercase, undotted): what a pattern can
22	# bind
23	type 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
48	type Tok is Data:
49	  Tok{kind: TokKind, text: String, line: U32, col: U32}
50	
51	# what a char is, for the machine
52	type 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
69	type 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
82	type 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.
90	def 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
112	def 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?
118	def 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
160	def 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
178	def 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	
201	def 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
227	def word(buf: List<&2, Char>) -> String:
228	  Rchars.text(buf)
229	
230	# is the text one of Bend's keywords?
231	def 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?
237	def 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
245	def 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
252	def 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
262	def 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
272	def 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
277	def 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
283	def 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
294	def 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
302	def 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
307	def 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
311	def 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
319	def text(toks: List<&2, Tok>) -> String:
320	  String.concat(List.reverse(&2, String, text.go(toks, [])))
321	
322	# an opening bracket?
323	def is_open(kk: TokKind) -> Bool:
324	  match kk:
325	    case TOpen{}:
326	      True{}
327	    case other:
328	      False{}
329	
330	# a comma?
331	def 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, `_`
339	def 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?
355	def 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
363	def 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?
375	def is_str(kk: TokKind) -> Bool:
376	  match kk:
377	    case TStr{}:
378	      True{}
379	    case other:
380	      False{}