1	# RFC 9113 HTTP/2 frame codec over packed Bytes.
2	import Base
3	import bend-kit-bytes@0.3.1.0/bytes.bend as Bytes
4	
5	type Frame is Type:
6	  Frame{kind: U32, flags: U32, stream: U32, payload: Bytes.Bytes}
7	
8	type Error is Data:
9	  Error{code: U32, connection: Bool, stream: U32}
10	
11	type Decode is Type:
12	  Need{input: Bytes.Bytes}
13	  Got{frame: Frame, rest: Bytes.Bytes}
14	  Bad{error: Error}
15	
16	type Checked is Type:
17	  Valid{frame: Frame}
18	  Invalid{error: Error}
19	
20	# Error codes from RFC 9113 §7: 1=PROTOCOL_ERROR, 3=FLOW_CONTROL_ERROR,
21	# 6=FRAME_SIZE_ERROR. A connection error uses stream 0.
22	def fail(+code: U32, +connection: Bool, +stream: U32) -> Maybe<&2, Error>:
23	  Some{Error{code, connection, Bool.pick(U32, connection, 0, stream)}}
24	
25	def reject(bad: Bool, +code: U32, +connection: Bool, +stream: U32) -> Maybe<&2, Error>:
26	  match bad:
27	    case True{}:
28	      fail(code, connection, stream)
29	    case False{}:
30	      None{}
31	
32	def first(m: Maybe<&2, Error>, n: Maybe<&2, Error>) -> Maybe<&2, Error>:
33	  match m:
34	    case Some{e}:
35	      Some{e}
36	    case None{}:
37	      n
38	
39	def number(m: Maybe<&2, U32>) -> U32:
40	  match m:
41	    case Some{x}:
42	      x
43	    case None{}:
44	      0
45	
46	def with_number(-R: Type, r: Bytes.Bytes & Maybe<&2, U32>, k: Bytes.Bytes -> U32 -> R) -> R:
47	  (b, m) = r
48	  k(b, number(m))
49	
50	def with_slice(-R: Type, r: Bytes.Bytes & Bytes.Bytes, k: Bytes.Bytes -> Bytes.Bytes -> R) -> R:
51	  (b, part) = r
52	  k(b, part)
53	
54	def has(+flags: U32, +bit: U32) -> Bool:
55	  U32.is_ne((flags .&. bit : U32), 0)
56	
57	# Field blocks, SETTINGS, and stream 0 make frame-size faults connection-wide.
58	def size.scope(+kind: U32, +stream: U32) -> Bool:
59	  match kind:
60	    case 1:
61	      True{}
62	    case 4:
63	      True{}
64	    case 5:
65	      True{}
66	    case 9:
67	      True{}
68	    case _:
69	      U32.is_eq(stream, 0)
70	
71	def size.error(+kind: U32, +stream: U32) -> Error:
72	  +connection = size.scope(kind, stream)
73	  Error{6, connection, Bool.pick(U32, connection, 0, stream)}
74	
75	def size.reject(oversized: Bool, +kind: U32, +stream: U32) -> Maybe<&2, Error>:
76	  match oversized:
77	    case True{}:
78	      Some{size.error(kind, stream)}
79	    case False{}:
80	      None{}
81	
82	# A PADDED payload must contain the pad-length octet and all the padding.
83	def padding(+flags: U32, +len: U32, +fixed: U32, +pad: U32) -> Bool:
84	  Bool.and(has(flags, 8), Bool.or(U32.is_le(len, fixed), U32.is_gt(pad, (len - fixed - 1 : U32))))
85	
86	def setting(+id: U32, +value: U32) -> Maybe<&2, Error>:
87	  match id:
88	    case 2:
89	      reject(U32.is_gt(value, 1), 1, True{}, 0)
90	    case 4:
91	      reject(U32.is_gt(value, 2147483647), 3, True{}, 0)
92	    case 5:
93	      reject(Bool.or(U32.is_lt(value, 16384), U32.is_gt(value, 16777215)), 1, True{}, 0)
94	    case _:
95	      None{}
96	
97	def settings.go(n: Nat, b: Bytes.Bytes, +at: U32, m: Maybe<&2, Error>) -> Bytes.Bytes & Maybe<&2, Error>:
98	  match n:
99	    case 0n:
100	      (b, m)
101	    case 1n+p:
102	      with_number(Bytes.Bytes & Maybe<&2, Error>, Bytes.get.u16be(b, at), b => id =>
103	        with_number(Bytes.Bytes & Maybe<&2, Error>, Bytes.get.u32be(b, (at + 2 : U32)), b => value =>
104	          settings.go(p, b, (at + 6 : U32), first(m, setting(id, value)))))
105	
106	def rules(+kind: U32, +flags: U32, +stream: U32, +len: U32, +pad: U32, +promised: U32, +value: U32, m: Maybe<&2, Error>) -> Maybe<&2, Error>:
107	  match kind:
108	    case 0:
109	      first(reject(U32.is_eq(stream, 0), 1, True{}, stream),
110	        first(reject(Bool.and(has(flags, 8), U32.is_eq(len, 0)), 6, False{}, stream),
111	          reject(padding(flags, len, 0, pad), 1, True{}, stream)))
112	    case 1:
113	      +fixed = Bool.pick(U32, has(flags, 32), 5, 0)
114	      +prefix = Bool.pick(U32, has(flags, 8), 1, 0)
115	      first(reject(U32.is_eq(stream, 0), 1, True{}, stream),
116	        first(reject(U32.is_lt(len, (fixed + prefix : U32)), 6, True{}, stream),
117	          reject(padding(flags, len, fixed, pad), 1, True{}, stream)))
118	    case 2:
119	      first(reject(U32.is_ne(len, 5), 6, U32.is_eq(stream, 0), stream),
120	        reject(U32.is_eq(stream, 0), 1, True{}, stream))
121	    case 3:
122	      first(reject(U32.is_ne(len, 4), 6, True{}, stream),
123	        reject(U32.is_eq(stream, 0), 1, True{}, stream))
124	    case 4:
125	      first(reject(U32.is_ne(stream, 0), 1, True{}, stream),
126	        first(reject(Bool.and(has(flags, 1), U32.is_ne(len, 0)), 6, True{}, stream),
127	          first(reject(U32.is_ne((len % 6 : U32), 0), 6, True{}, stream), m)))
128	    case 5:
129	      +prefix = Bool.pick(U32, has(flags, 8), 1, 0)
130	      first(reject(U32.is_eq(stream, 0), 1, True{}, stream),
131	        first(reject(U32.is_lt(len, (prefix + 4 : U32)), 6, True{}, stream),
132	          first(reject(padding(flags, len, 4, pad), 1, True{}, stream),
133	            reject(U32.is_eq(promised, 0), 1, True{}, stream))))
134	    case 6:
135	      first(reject(U32.is_ne(len, 8), 6, True{}, stream),
136	        reject(U32.is_ne(stream, 0), 1, True{}, stream))
137	    case 7:
138	      first(reject(U32.is_lt(len, 8), 6, True{}, stream),
139	        reject(U32.is_ne(stream, 0), 1, True{}, stream))
140	    case 8:
141	      first(reject(U32.is_ne(len, 4), 6, U32.is_eq(stream, 0), stream),
142	        reject(U32.is_eq((value .&. 2147483647 : U32), 0), 1, U32.is_eq(stream, 0), stream))
143	    case 9:
144	      reject(U32.is_eq(stream, 0), 1, True{}, stream)
145	    case _:
146	      None{}
147	
148	def checked(m: Maybe<&2, Error>, +kind: U32, +flags: U32, +stream: U32, b: Bytes.Bytes) -> Checked:
149	  match m:
150	    case Some{e}:
151	      Invalid{e}
152	    case None{}:
153	      Valid{Frame{kind, flags, stream, b}}
154	
155	def with_settings(r: Bytes.Bytes & Maybe<&2, Error>, +flags: U32, +stream: U32) -> Checked:
156	  (b, m) = r
157	  checked(m, 4, flags, stream, b)
158	
159	def inspect.settings(m: Maybe<&2, Error>, +flags: U32, +stream: U32, +len: U32, b: Bytes.Bytes) -> Checked:
160	  match m:
161	    case Some{e}:
162	      Invalid{e}
163	    case None{}:
164	      with_settings(settings.go(U32.to_nat((len / 6 : U32)), b, 0, None{}), flags, stream)
165	
166	def inspect.promised(+kind: U32, +flags: U32, +stream: U32, +len: U32, +pad: U32, b: Bytes.Bytes) -> Checked:
167	  match kind:
168	    case 5:
169	      +prefix = Bool.pick(U32, has(flags, 8), 1, 0)
170	      with_number(Checked, Bytes.get.u32be(b, prefix), b => promised =>
171	        checked(rules(kind, flags, stream, len, pad, (promised .&. 2147483647 : U32), 0, None{}), kind, flags, stream, b))
172	    case _:
173	      checked(rules(kind, flags, stream, len, pad, 0, 0, None{}), kind, flags, stream, b)
174	
175	def inspect.padded.if(padded: Bool, +kind: U32, +flags: U32, +stream: U32, +len: U32, b: Bytes.Bytes) -> Checked:
176	  match padded:
177	    case True{}:
178	      with_number(Checked, Bytes.get(b, 0), b => pad =>
179	        inspect.promised(kind, flags, stream, len, pad, b))
180	    case False{}:
181	      inspect.promised(kind, flags, stream, len, 0, b)
182	
183	def inspect.padded(+kind: U32, +flags: U32, +stream: U32, +len: U32, b: Bytes.Bytes) -> Checked:
184	  inspect.padded.if(has(flags, 8), kind, flags, stream, len, b)
185	
186	def inspect.detail(+kind: U32, +flags: U32, +stream: U32, +len: U32, b: Bytes.Bytes) -> Checked:
187	  match kind:
188	    case 0:
189	      inspect.padded(kind, flags, stream, len, b)
190	    case 1:
191	      inspect.padded(kind, flags, stream, len, b)
192	    case 4:
193	      inspect.settings(rules(kind, flags, stream, len, 0, 0, 0, None{}), flags, stream, len, b)
194	    case 5:
195	      inspect.padded(kind, flags, stream, len, b)
196	    case 8:
197	      with_number(Checked, Bytes.get.u32be(b, 0), b => value =>
198	        checked(rules(kind, flags, stream, len, 0, 0, value, None{}), kind, flags, stream, b))
199	    case _:
200	      checked(rules(kind, flags, stream, len, 0, 0, 0, None{}), kind, flags, stream, b)
201	
202	
203	def inspect.basic(m: Maybe<&2, Error>, +kind: U32, +flags: U32, +stream: U32, +len: U32, b: Bytes.Bytes) -> Checked:
204	  match m:
205	    case Some{e}:
206	      Invalid{e}
207	    case None{}:
208	      inspect.detail(kind, flags, stream, len, b)
209	
210	def inspect(max: U32, +kind: U32, +flags: U32, +stream: U32, b: Bytes.Bytes) -> Checked:
211	  Bytes.Bytes{+len, buf} = b
212	  +basic = first(size.reject(Bool.or(U32.is_gt(len, max), U32.is_gt(len, 16777215)), kind, stream),
213	    first(reject(U32.is_gt(kind, 255), 1, True{}, stream),
214	      first(reject(U32.is_gt(flags, 255), 1, True{}, stream),
215	        reject(U32.is_gt(stream, 2147483647), 1, True{}, stream))))
216	  inspect.basic(basic, kind, flags, stream, len, Bytes.Bytes{len, buf})
217	
218	# max is the peer's SETTINGS_MAX_FRAME_SIZE, initially 16384.
219	def allowed(+kind: U32) -> U32:
220	  match kind:
221	    case 0:
222	      9
223	    case 1:
224	      45
225	    case 2:
226	      0
227	    case 3:
228	      0
229	    case 4:
230	      1
231	    case 5:
232	      12
233	    case 6:
234	      1
235	    case 7:
236	      0
237	    case 8:
238	      0
239	    case 9:
240	      4
241	    case _:
242	      255
243	
244	def encode.buffer(b: Bytes.Bytes, src: Array<U32>, +len: U32) -> Result<&1, &1, Error, Bytes.Bytes>:
245	  Bytes.Bytes{_, dst} = b
246	  Done{Bytes.Bytes{(len + 9 : U32), Bytes.dst(Bytes.copy(len, src, dst, 0, 9))}}
247	
248	def encode.flags(ok: Bool, +kind: U32, +flags: U32, +stream: U32, payload: Bytes.Bytes) -> Result<&1, &1, Error, Bytes.Bytes>:
249	  match ok:
250	    case False{}:
251	      Fail{Error{1, True{}, 0}}
252	    case True{}:
253	      Bytes.Bytes{+len, src} = payload
254	      encode.buffer(Bytes.set.u32be(Bytes.set(Bytes.set(Bytes.put(Bytes.new((len + 9 : U32)), 0, 3, True{}, len), 3, kind), 4, flags), 5, stream), src, len)
255	
256	def encode.checked(c: Checked) -> Result<&1, &1, Error, Bytes.Bytes>:
257	  match c:
258	    case Invalid{e}:
259	      Fail{e}
260	    case Valid{Frame{+kind, +flags, +stream, payload}}:
261	      encode.flags(U32.is_eq((flags .&. U32.not(allowed(kind)) : U32), 0), kind, flags, stream, payload)
262	def encode(max: U32, f: Frame) -> Result<&1, &1, Error, Bytes.Bytes>:
263	  Frame{+kind, +flags, +stream, payload} = f
264	  encode.checked(inspect(max, kind, flags, stream, payload))
265	
266	def parse.result(c: Checked, b: Bytes.Bytes, +len: U32) -> Decode:
267	  match c:
268	    case Invalid{e}:
269	      Bad{e}
270	    case Valid{f}:
271	      Bytes.Bytes{+n, buf} = b
272	      with_slice(Decode, Bytes.slice(Bytes.Bytes{n, buf}, (len + 9 : U32), (n - len - 9 : U32)),
273	        unused => rest => Got{f, rest})
274	
275	def parse.payload(max: U32, +len: U32, +kind: U32, +flags: U32, +stream: U32, b: Bytes.Bytes) -> Decode:
276	  with_slice(Decode, Bytes.slice(b, 9, len), b => payload =>
277	    parse.result(inspect(max, kind, flags, stream, payload), b, len))
278	
279	def parse.full(enough: Bool, max: U32, +len: U32, +kind: U32, +flags: U32, +stream: U32, b: Bytes.Bytes) -> Decode:
280	  match enough:
281	    case True{}:
282	      parse.payload(max, len, kind, flags, stream, b)
283	    case False{}:
284	      Need{b}
285	
286	def parse.size(oversized: Bool, max: U32, +len: U32, +kind: U32, +flags: U32, +stream: U32, b: Bytes.Bytes) -> Decode:
287	  match oversized:
288	    case True{}:
289	      Bad{size.error(kind, stream)}
290	    case False{}:
291	      Bytes.Bytes{+n, buf} = b
292	      parse.full(U32.is_le(len, (n - 9 : U32)), max, len, kind, flags, stream, Bytes.Bytes{n, buf})
293	
294	def parse.header(+max: U32, b: Bytes.Bytes) -> Decode:
295	  with_number(Decode, Bytes.uint(b, 0, 3, True{}), b => +len =>
296	    with_number(Decode, Bytes.get(b, 3), b => kind =>
297	      with_number(Decode, Bytes.get(b, 4), b => flags =>
298	        with_number(Decode, Bytes.get.u32be(b, 5), b => stream =>
299	          parse.size(U32.is_gt(len, max), max, len, kind, flags, (stream .&. 2147483647 : U32), b)))))
300	
301	def parse.start(short: Bool, max: U32, b: Bytes.Bytes) -> Decode:
302	  match short:
303	    case True{}:
304	      Need{b}
305	    case False{}:
306	      parse.header(max, b)
307	
308	# A partial header or payload returns Need with the original input intact.
309	def parse(max: U32, b: Bytes.Bytes) -> Decode:
310	  Bytes.Bytes{+n, buf} = b
311	  parse.start(U32.is_lt(n, 9), max, Bytes.Bytes{n, buf})