src/lsp/frame.bend
bolt@1.23.0.0 · 355 lines · 0 definitions
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.
4import Base
5import bolt@1.23.0.0/src/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)
12type 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
16def 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
29def 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
36def 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
44def 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
51def 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)
56def 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
63def 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
69def 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
81def encode.one(+xx: U32, rest: List<&2, U32>) -> List<&2, U32>:
82 encode.char(width(xx), xx, rest)
83
84def 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
92def 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
104type 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'
117def 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
141def 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)
167def 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
193def 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
205def 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
213def 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?
221def 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)
231def 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
257def 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
266def 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
274def 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
285def 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
289type 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
294type 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)
299def 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
307def 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
314def 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
329def 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
338def 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
345def 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
354def cut(buf: List<&2, U32>) -> Cut:
355 cut.body(header(buf, [], [D0{}]))