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