1	# lsp/frame: LSP's base protocol, purely: `Content-Length: N\r\n\r\n` and then
2	# N bytes of UTF-8. Framing counts bytes and a read may end inside a char, so
3	# the transport reads bytes, cuts on bytes, and only then decodes.
4	import Base
5	import ../rchars.bend as Rchars
6	
7	# UTF-8, bytes to chars
8	# ---------------------
9	
10	# the decoder's state: continuation bytes still owed, the code point so far,
11	# the chars so far (reversed)
12	type Dec is Data:
13	  Dec{need: Nat, acc: U32, out: List<&2, Char>}
14	
15	# a lead byte, by its high nibble; a stray continuation byte stands for itself
16	def decode.lead(hi: U32, +bb: U32, out: List<&2, Char>) -> Dec:
17	  match hi:
18	    case 12:
19	      Dec{1n, (bb .&. 31 : U32), out}
20	    case 13:
21	      Dec{1n, (bb .&. 31 : U32), out}
22	    case 14:
23	      Dec{2n, (bb .&. 15 : U32), out}
24	    case 15:
25	      Dec{3n, (bb .&. 7 : U32), out}
26	    case other:
27	      Dec{0n, 0, Char.from_u32(bb) <> out}
28	
29	def decode.more(left: Nat, +acc: U32, out: List<&2, Char>) -> Dec:
30	  match left:
31	    case 0n:
32	      Dec{0n, 0, Char.from_u32(acc) <> out}
33	    case 1n+p:
34	      Dec{1n+p, acc, out}
35	
36	def decode.step(+bb: U32, st: Dec) -> Dec:
37	  Dec{need, acc, out} = st
38	  match need:
39	    case 0n:
40	      decode.lead((bb >> 4n : U32), bb, out)
41	    case 1n+p:
42	      decode.more(p, ((acc << 6n) .|. (bb .&. 63) : U32), out)
43	
44	def decode.run(bs: List<&2, U32>, st: Dec) -> Dec:
45	  match bs:
46	    case Nil{}:
47	      st
48	    case Con{b, t}:
49	      decode.run(t, decode.step(b, st))
50	
51	def decode.end(st: Dec) -> String:
52	  Dec{need, acc, out} = st
53	  Rchars.text(out)
54	
55	# UTF-8 bytes as a string (a bad byte is skipped)
56	def decode(bs: List<&2, U32>) -> String:
57	  decode.end(decode.run(bs, Dec{0n, 0, []}))
58	
59	# UTF-8, chars to bytes
60	# ---------------------
61	
62	# how many bytes a code point takes
63	def width(+xx: U32) -> U32:
64	  Bool.pick(U32, U32.is_lt(xx, 128), 1,
65	    Bool.pick(U32, U32.is_lt(xx, 2048), 2,
66	      Bool.pick(U32, U32.is_lt(xx, 65536), 3, 4)))
67	
68	# a code point's bytes, by its width, in front of the rest
69	def encode.char(ww: U32, +xx: U32, rest: List<&2, U32>) -> List<&2, U32>:
70	  match ww:
71	    case 1:
72	      xx <> rest
73	    case 2:
74	      (192 .|. (xx >> 6n) : U32) <> (128 .|. (xx .&. 63) : U32) <> rest
75	    case 3:
76	      (224 .|. (xx >> 12n) : U32) <> (128 .|. ((xx >> 6n) .&. 63) : U32) <> (128 .|. (xx .&. 63) : U32) <> rest
77	    case other:
78	      (240 .|. (xx >> 18n) : U32) <> (128 .|. ((xx >> 12n) .&. 63) : U32) <> (128 .|. ((xx >> 6n) .&. 63) : U32)
79	        <> (128 .|. (xx .&. 63) : U32) <> rest
80	
81	def encode.one(+xx: U32, rest: List<&2, U32>) -> List<&2, U32>:
82	  encode.char(width(xx), xx, rest)
83	
84	def encode.go(cs: List<&2, Char>) -> List<&2, U32>:
85	  match cs:
86	    case Nil{}:
87	      Nil{}
88	    case Con{c, t}:
89	      encode.one(Char.to_u32(c), encode.go(t))
90	
91	# a string as UTF-8 bytes
92	def encode(ss: String) -> List<&2, U32>:
93	  encode.go(String.to_list(ss))
94	
95	# counts in decimal
96	# -----------------
97	
98	# Content-Length is a count in decimal. It is kept as its digits, least
99	# significant first, from writing it to reading it back: neither side goes
100	# through a U32, whose text round trip would need laws of division by ten on
101	# 32-bit words, and no length wraps at 2^32 or unfolds into a Nat of its size.
102	
103	# a decimal digit
104	type Digit is Data:
105	  D0{}
106	  D1{}
107	  D2{}
108	  D3{}
109	  D4{}
110	  D5{}
111	  D6{}
112	  D7{}
113	  D8{}
114	  D9{}
115	
116	# a digit's char code, '0' to '9'
117	def digit.code(dd: Digit) -> U32:
118	  match dd:
119	    case D0{}:
120	      48
121	    case D1{}:
122	      49
123	    case D2{}:
124	      50
125	    case D3{}:
126	      51
127	    case D4{}:
128	      52
129	    case D5{}:
130	      53
131	    case D6{}:
132	      54
133	    case D7{}:
134	      55
135	    case D8{}:
136	      56
137	    case D9{}:
138	      57
139	
140	# the digit a char code stands for, if it is one
141	def digit.read(xx: U32) -> Maybe<&2, Digit>:
142	  match xx:
143	    case 48:
144	      Some{D0{}}
145	    case 49:
146	      Some{D1{}}
147	    case 50:
148	      Some{D2{}}
149	    case 51:
150	      Some{D3{}}
151	    case 52:
152	      Some{D4{}}
153	    case 53:
154	      Some{D5{}}
155	    case 54:
156	      Some{D6{}}
157	    case 55:
158	      Some{D7{}}
159	    case 56:
160	      Some{D8{}}
161	    case 57:
162	      Some{D9{}}
163	    case other:
164	      None{}
165	
166	# a count one more (digits least significant first)
167	def tick(ds: List<&2, Digit>) -> List<&2, Digit>:
168	  match ds:
169	    case Nil{}:
170	      [D1{}]
171	    case Con{D0{}, t}:
172	      D1{} <> t
173	    case Con{D1{}, t}:
174	      D2{} <> t
175	    case Con{D2{}, t}:
176	      D3{} <> t
177	    case Con{D3{}, t}:
178	      D4{} <> t
179	    case Con{D4{}, t}:
180	      D5{} <> t
181	    case Con{D5{}, t}:
182	      D6{} <> t
183	    case Con{D6{}, t}:
184	      D7{} <> t
185	    case Con{D7{}, t}:
186	      D8{} <> t
187	    case Con{D8{}, t}:
188	      D9{} <> t
189	    case Con{D9{}, t}:
190	      D0{} <> tick(t)
191	
192	# a count plus a char's width in bytes
193	def tick.by(ww: U32, ds: List<&2, Digit>) -> List<&2, Digit>:
194	  match ww:
195	    case 1:
196	      tick(ds)
197	    case 2:
198	      tick(tick(ds))
199	    case 3:
200	      tick(tick(tick(ds)))
201	    case other:
202	      tick(tick(tick(tick(ds))))
203	
204	# how many UTF-8 bytes the chars take, counted on from ds
205	def byte_count(cs: List<&2, Char>, ds: List<&2, Digit>) -> List<&2, Digit>:
206	  match cs:
207	    case Nil{}:
208	      ds
209	    case Con{c, t}:
210	      byte_count(t, tick.by(width(Char.to_u32(c)), ds))
211	
212	# a count's digits, most significant first, in front of acc
213	def count.show(ds: List<&2, Digit>, acc: String) -> String:
214	  match ds:
215	    case Nil{}:
216	      acc
217	    case Con{d, t}:
218	      count.show(t, SCon{Char.from_u32(digit.code(d)), acc})
219	
220	# is the count zero?
221	def count.zero(ds: List<&2, Digit>) -> Bool:
222	  match ds:
223	    case Nil{}:
224	      True{}
225	    case Con{D0{}, t}:
226	      count.zero(t)
227	    case Con{d, t}:
228	      False{}
229	
230	# a count one less (zero stays zero)
231	def untick(ds: List<&2, Digit>) -> List<&2, Digit>:
232	  match ds:
233	    case Nil{}:
234	      Nil{}
235	    case Con{D0{}, t}:
236	      D9{} <> untick(t)
237	    case Con{D1{}, t}:
238	      D0{} <> t
239	    case Con{D2{}, t}:
240	      D1{} <> t
241	    case Con{D3{}, t}:
242	      D2{} <> t
243	    case Con{D4{}, t}:
244	      D3{} <> t
245	    case Con{D5{}, t}:
246	      D4{} <> t
247	    case Con{D6{}, t}:
248	      D5{} <> t
249	    case Con{D7{}, t}:
250	      D6{} <> t
251	    case Con{D8{}, t}:
252	      D7{} <> t
253	    case Con{D9{}, t}:
254	      D8{} <> t
255	
256	# one more char's digit onto the count read so far; None once one is no digit
257	def count.push(md: Maybe<&2, Digit>, acc: Maybe<&2, List<&2, Digit>>) -> Maybe<&2, List<&2, Digit>>:
258	  match md acc:
259	    case Some{d} Some{ds}:
260	      Some{d <> ds}
261	    case None{} _:
262	      None{}
263	    case Some{d} None{}:
264	      None{}
265	
266	def count.read.go(ss: String, acc: Maybe<&2, List<&2, Digit>>) -> Maybe<&2, List<&2, Digit>>:
267	  match ss:
268	    case SNil{}:
269	      acc
270	    case SCon{c, t}:
271	      count.read.go(t, count.push(digit.read(Char.to_u32(c)), acc))
272	
273	# a string of digits as a count; None when it is empty or holds anything else
274	def count.read(ss: String) -> Maybe<&2, List<&2, Digit>>:
275	  match ss:
276	    case SNil{}:
277	      None{}
278	    case SCon{h, t}:
279	      count.read.go(SCon{h, t}, Some{[]})
280	
281	# framing
282	# -------
283	
284	# a message on its way out
285	def wrap(+body: String) -> String:
286	  "Content-Length: " ++ count.show(byte_count(String.to_list(body), [D0{}]), "") ++ "\r\n\r\n" ++ body
287	
288	# the header block's Content-Length and the bytes after it, once it is whole
289	type Head is Data:
290	  NoHead{}
291	  Head{len: List<&2, Digit>, rest: List<&2, U32>}
292	
293	# the front of a buffer: a whole body and the bytes after it, or not yet
294	type Cut is Data:
295	  More{}
296	  Whole{body: List<&2, U32>, rest: List<&2, U32>}
297	
298	# bytes as chars, one each (for the ASCII header)
299	def chars(bs: List<&2, U32>, acc: List<&2, Char>) -> List<&2, Char>:
300	  match bs:
301	    case Nil{}:
302	      acc
303	    case Con{b, t}:
304	      chars(t, Char.from_u32(b) <> acc)
305	
306	# a header line (reversed, its \r already dropped) updates the length
307	def line_len(line: List<&2, U32>, +len: List<&2, Digit>) -> List<&2, Digit>:
308	  +s = String.from_list(chars(line, []))
309	  +read = count.read(String.drop(s, 16n))
310	  Bool.pick(List<&2, Digit>, String.starts_with(s, "Content-Length: "), Maybe.default(&2, List<&2, Digit>, read, len), len)
311	
312	# the header block read up to its blank line: Content-Length, and the bytes
313	# after; not whole yet when the blank line has not come
314	def header(bs: List<&2, U32>, line: List<&2, U32>, len: List<&2, Digit>) -> Head:
315	  match bs line:
316	    case Nil{} l:
317	      NoHead{}
318	    case Con{10, t} Nil{}:
319	      Head{len, t}
320	    case Con{10, t} l:
321	      header(t, [], line_len(l, len))
322	    case Con{13, t} l:
323	      header(t, l, len)
324	    case Con{c, t} l:
325	      header(t, c <> l, len)
326	
327	# the bytes taken so far and the rest once the count is down to zero, else
328	# what more gives
329	def split.on(zz: Bool, xs: List<&2, U32>, acc: List<&2, U32>, more: Unit -> Cut) -> Cut:
330	  match zz:
331	    case True{}:
332	      Whole{List.reverse(&2, U32, acc), xs}
333	    case False{}:
334	      more(Unit{})
335	
336	# the first ds bytes (reversed onto acc) and the rest, or not yet when there
337	# are fewer. The count goes down a digit at a time: never a Nat of its size
338	def split(xs: List<&2, U32>, +ds: List<&2, Digit>, +acc: List<&2, U32>) -> Cut:
339	  match xs:
340	    case Nil{}:
341	      split.on(count.zero(ds), [], acc, _u => More{})
342	    case Con{+h, +t}:
343	      split.on(count.zero(ds), h <> t, acc, _u => split(t, untick(ds), h <> acc))
344	
345	def cut.body(hh: Head) -> Cut:
346	  match hh:
347	    case NoHead{}:
348	      More{}
349	    case Head{len, rest}:
350	      split(rest, len, [])
351	
352	# the front of a buffer: a whole message body and the bytes after it, or
353	# not yet
354	def cut(buf: List<&2, U32>) -> Cut:
355	  cut.body(header(buf, [], [D0{}]))