multipart.bend

bend-kit-multipart@0.3.0.0 · 686 lines · 99 definitions

1# multipart/form-data (RFC 7578): an encoder with a secure random boundary and a streaming decoder over Bytes. Source: https://github.com/paymog/bend-kit/tree/main/multipart
2import Base
3import bend-kit-bytes@0.3.3.0/bytes.bend as Bytes
4import bend-kit-crypto@0.2.2.1/crypto.bend as Crypto
5
6# Names, filenames, and header values are byte strings, one Char per octet, as in Http.
7# Bodies are Bytes and pass through untouched, so binary payloads keep every octet.
8# Names and filenames are escaped as WHATWG does: '"' is %22, CR is %0D, LF is %0A.
9#   import bend-kit-multipart@0.2.0.1/multipart.bend as Mp
10
11# One form field. filename marks a file; ctype is its Content-Type (RFC 7578 §4.4 defaults to text/plain).
12type Part is Type:
13  Part{name: String, filename: Maybe<&2, String>, ctype: Maybe<&2, String>, body: Bytes.Bytes}
14
15# What the streaming decoder reports, in order: Head, then zero or more Body pieces, then Tail, per part.
16type Item is Type:
17  Head{name: String, filename: Maybe<&2, String>, ctype: Maybe<&2, String>}
18  Body{chunk: Bytes.Bytes}
19  Tail{}
20
21# ---- shared text helpers
22
23# The text before the first c, and the text after it. No c gives (s, "").
24def split1.cons(+h: U32, r: String & String) -> String & String:
25  (a, b) = r
26  (SCon{Chr{h}, a}, b)
27
28def split1(s: String, +c: U32) -> String & String:
29  match s:
30    case SNil{}:
31      (SNil{}, SNil{})
32    case SCon{Chr{+h}, +t}:
33      Bool.pick(String & String, U32.is_eq(h, c), (SNil{}, t), split1.cons(h, split1(t, c)))
34
35# Header parameters (RFC 2045 §5.1, RFC 7578 §4.2): key=token or key="quoted", split on ';'.
36# Keys are lowercased; a backslash escapes the next char inside quotes. An unterminated quote drops its parameter.
37type Cls is Data:
38  CEq{}
39  CSemi{}
40  CQuote{}
41  CSlash{}
42  CSp{}
43  COther{}
44
45type Pm is Data:
46  PKey{}
47  PStart{}
48  PQuo{}
49  PEsc{}
50  PTok{}
51  PSkip{}
52
53type Param is Data:
54  Param{key: String, val: String}
55
56# mode, the key and value so far (reversed), and the parameters found (latest first).
57type PS is Data:
58  PS{mode: Pm, key: String, val: String, acc: List<&2, Param>}
59
60def cls(+c: U32) -> Cls:
61  Bool.pick(Cls, U32.is_eq(c, 61), CEq{}, Bool.pick(Cls, U32.is_eq(c, 59), CSemi{}, Bool.pick(Cls, U32.is_eq(c, 34), CQuote{}, Bool.pick(Cls, U32.is_eq(c, 92), CSlash{}, Bool.pick(Cls, Bool.or(U32.is_eq(c, 32), U32.is_eq(c, 9)), CSp{}, COther{})))))
62
63def params.emit(key: String, val: String, acc: List<&2, Param>) -> List<&2, Param>:
64  Con{Param{String.reverse(key), String.reverse(val)}, acc}
65
66def params.step(st: PS, k: Cls, +c: U32) -> PS:
67  PS{mode, key, val, acc} = st
68  match mode:
69    case PKey{}:
70      match k:
71        case CEq{}:
72          PS{PStart{}, key, SNil{}, acc}
73        case CSemi{}:
74          PS{PKey{}, SNil{}, SNil{}, acc}
75        case CSp{}:
76          PS{PKey{}, key, val, acc}
77        case _:
78          PS{PKey{}, SCon{Char.to_lower(Chr{c}), key}, val, acc}
79    case PStart{}:
80      match k:
81        case CQuote{}:
82          PS{PQuo{}, key, SNil{}, acc}
83        case CSp{}:
84          PS{PStart{}, key, val, acc}
85        case CSemi{}:
86          PS{PKey{}, SNil{}, SNil{}, params.emit(key, SNil{}, acc)}
87        case _:
88          PS{PTok{}, key, SCon{Chr{c}, SNil{}}, acc}
89    case PQuo{}:
90      match k:
91        case CSlash{}:
92          PS{PEsc{}, key, val, acc}
93        case CQuote{}:
94          PS{PSkip{}, SNil{}, SNil{}, params.emit(key, val, acc)}
95        case _:
96          PS{PQuo{}, key, SCon{Chr{c}, val}, acc}
97    case PEsc{}:
98      PS{PQuo{}, key, SCon{Chr{c}, val}, acc}
99    case PTok{}:
100      match k:
101        case CSemi{}:
102          PS{PKey{}, SNil{}, SNil{}, params.emit(key, String.trim_start(val), acc)}
103        case _:
104          PS{PTok{}, key, SCon{Chr{c}, val}, acc}
105    case PSkip{}:
106      match k:
107        case CSemi{}:
108          PS{PKey{}, SNil{}, SNil{}, acc}
109        case _:
110          PS{PSkip{}, key, val, acc}
111
112def params.end(st: PS) -> List<&2, Param>:
113  PS{mode, key, val, acc} = st
114  match mode:
115    case PStart{}:
116      params.emit(key, SNil{}, acc)
117    case PTok{}:
118      params.emit(key, String.trim_start(val), acc)
119    case _:
120      acc
121
122def params.go(s: String, st: PS) -> PS:
123  match s:
124    case SNil{}:
125      st
126    case SCon{Chr{+c}, t}:
127      params.go(t, params.step(st, cls(c), c))
128
129# The parameters of a header value's text after its first ';', in order.
130def params(s: String) -> List<&2, Param>:
131  List.reverse(&2, Param, params.end(params.go(s, PS{PKey{}, SNil{}, SNil{}, Nil{}})))
132
133# The first parameter named k (lowercase).
134def lookup(xs: List<&2, Param>, +k: String) -> Maybe<&2, String>:
135  match xs:
136    case Nil{}:
137      None{}
138    case Con{Param{+k2, +v}, t}:
139      Bool.pick(Maybe<&2, String>, String.eq(k2, k), Some{v}, lookup(t, k))
140
141# WHATWG form-data escapes for names and filenames.
142def esc.one(+c: U32) -> String:
143  Bool.pick(String, U32.is_eq(c, 34), "%22", Bool.pick(String, U32.is_eq(c, 13), "%0D", Bool.pick(String, U32.is_eq(c, 10), "%0A", SCon{Chr{c}, SNil{}})))
144
145def esc(s: String) -> String:
146  match s:
147    case SNil{}:
148      SNil{}
149    case SCon{Chr{+c}, t}:
150      esc.one(c) ++ esc(t)
151
152# acc is reversed, so "%22" shows as "22%".
153def unesc.fix(+a: String) -> String:
154  Bool.pick(String, String.starts_with(a, "22%"), SCon{Chr{34}, String.drop(a, 3n)}, Bool.pick(String, String.starts_with(a, "D0%"), SCon{Chr{13}, String.drop(a, 3n)}, Bool.pick(String, String.starts_with(a, "A0%"), SCon{Chr{10}, String.drop(a, 3n)}, a)))
155
156def unesc.go(s: String, acc: String) -> String:
157  match s:
158    case SNil{}:
159      acc
160    case SCon{c, t}:
161      unesc.go(t, unesc.fix(SCon{c, acc}))
162
163# Undoes esc, as the Fetch spec's form-data parser does. A literal "%22" in a name reads back as '"'.
164def unesc(s: String) -> String:
165  String.reverse(unesc.go(s, SNil{}))
166
167def unesc.m(m: Maybe<&2, String>) -> Maybe<&2, String>:
168  match m:
169    case None{}:
170      None{}
171    case Some{x}:
172      Some{unesc(x)}
173
174# ---- boundary
175
176# RFC 2046 §5.1.1 bchars: DIGIT ALPHA ' ( ) + _ , - . / : = ? and space.
177def bchar(+c: U32) -> Bool:
178  Bool.or(Bool.or(Bool.or(Bytes.in(39, c, 41), Bytes.in(43, c, 58)), Bool.or(Bytes.in(65, c, 90), Bytes.in(97, c, 122))), Bool.or(Bool.or(U32.is_eq(c, 61), U32.is_eq(c, 63)), Bool.or(U32.is_eq(c, 95), U32.is_eq(c, 32))))
179
180def bchars(s: String) -> Bool:
181  match s:
182    case SNil{}:
183      True{}
184    case SCon{Chr{+c}, t}:
185      Bool.and(bchar(c), bchars(t))
186
187# 1 to 70 bchars, not ending in a space.
188def boundary.ok(+b: String) -> Bool:
189  +n = Bytes.count(b, 0)
190  Bool.and(Bool.and(U32.is_le(1, n), U32.is_le(n, 70)), Bool.and(bchars(b), Bool.not(String.ends_with(b, " "))))
191
192def boundary.words(r: Result<&1, &1, U32 & String, U32 & Array<U32>>) -> Result<&1, &1, U32 & String, String>:
193  match r:
194    case Fail{e}:
195      Fail{e}
196    case Done{(+n, w)}:
197      Done{"bend-kit-" ++ Bytes.to_hex(Bytes.Bytes{n, w})}
198
199# "bend-kit-" and 128 bits from the OS secure random source, as hex: 41 bchars.
200def boundary.new() -> IO(Result<&1, &1, U32 & String, String>):
201  do IO<Result<&1, &1, U32 & String, String>>:
202    r : Result<&1, &1, U32 & String, U32 & Array<U32>> <- Crypto.random.words(16)
203    return boundary.words(r)
204
205# The Content-Type header value for a body encoded with boundary b.
206def content_type(b: String) -> String:
207  "multipart/form-data; boundary=" ++ b
208
209def boundary.get.of(r: String & String) -> Maybe<&2, String>:
210  (ty, rest) = r
211  lookup(params(rest), "boundary")
212
213# The boundary parameter of a Content-Type value, such as a request's, or None.
214def boundary.get(ct: String) -> Maybe<&2, String>:
215  boundary.get.of(split1(ct, 59))
216
217# ---- encoder
218
219def enc.fname(m: Maybe<&2, String>) -> String:
220  match m:
221    case None{}:
222      SNil{}
223    case Some{f}:
224      "; filename=\"" ++ esc(f) ++ "\""
225
226def enc.ctype(m: Maybe<&2, String>) -> String:
227  match m:
228    case None{}:
229      SNil{}
230    case Some{c}:
231      "Content-Type: " ++ c ++ "\r\n"
232
233def enc.head(+b: String, name: String, fname: Maybe<&2, String>, ct: Maybe<&2, String>) -> String:
234  "--" ++ b ++ "\r\nContent-Disposition: form-data; name=\"" ++ esc(name) ++ "\"" ++ enc.fname(fname) ++ "\r\n" ++ enc.ctype(ct) ++ "\r\n"
235
236# A Content-Type with CR or LF would inject header lines.
237def enc.ctype.ok(m: Maybe<&2, String>) -> Bool:
238  match m:
239    case None{}:
240      True{}
241    case Some{+c}:
242      Bool.not(Bool.or(String.contains(c, "\r"), String.contains(c, "\n")))
243
244def enc.found(r: Bytes.Bytes & Maybe<&2, U32>, +head: String, xs: List<&1, Bytes.Bytes>) -> Result<&1, &1, String, List<&1, Bytes.Bytes>>:
245  (body, hit) = r
246  match hit:
247    case Some{i}:
248      Fail{"multipart: boundary occurs in a part body"}
249    case None{}:
250      Done{Con{Bytes.from_string("\r\n"), Con{body, Con{Bytes.from_string(head), xs}}}}
251
252def enc.body(ok: Bool, r: Bytes.Bytes & Maybe<&2, U32>, +head: String, xs: List<&1, Bytes.Bytes>) -> Result<&1, &1, String, List<&1, Bytes.Bytes>>:
253  match ok:
254    case False{}:
255      Fail{"multipart: Content-Type has CR or LF"}
256    case True{}:
257      enc.found(r, head, xs)
258
259# The pieces so far, latest first. A body cannot hold CRLF "--" boundary; bchars hold no CR,
260# so the delimiter cannot start inside the body and end in the one after it.
261def enc.part(acc: Result<&1, &1, String, List<&1, Bytes.Bytes>>, p: Part, +b: String, +delim: String) -> Result<&1, &1, String, List<&1, Bytes.Bytes>>:
262  match acc:
263    case Fail{e}:
264      Fail{e}
265    case Done{xs}:
266      Part{name, fname, +ct, body} = p
267      enc.body(enc.ctype.ok(ct), Bytes.find(body, delim), enc.head(b, name, fname, ct), xs)
268
269def enc.fin(+b: String, acc: Result<&1, &1, String, List<&1, Bytes.Bytes>>) -> Result<&1, &1, String, Bytes.Bytes>:
270  match acc:
271    case Fail{e}:
272      Fail{e}
273    case Done{xs}:
274      Done{Bytes.concat(List.reverse(&1, Bytes.Bytes, Con{Bytes.from_string("--" ++ b ++ "--\r\n"), xs}))}
275
276def enc.go(parts: List<&1, Part>, +b: String, +delim: String, acc: Result<&1, &1, String, List<&1, Bytes.Bytes>>) -> Result<&1, &1, String, Bytes.Bytes>:
277  match parts:
278    case Nil{}:
279      enc.fin(b, acc)
280    case Con{p, t}:
281      enc.go(t, b, delim, enc.part(acc, p, b, delim))
282
283def encode.if(ok: Bool, +b: String, parts: List<&1, Part>) -> Result<&1, &1, String, Bytes.Bytes>:
284  match ok:
285    case False{}:
286      Fail{"multipart: boundary must be 1 to 70 RFC 2046 bchars, not ending in a space"}
287    case True{}:
288      enc.go(parts, b, "\r\n--" ++ b, Done{Nil{}})
289
290# The body for parts under boundary b (RFC 7578 §4.1). Fails when b is not a valid boundary,
291# b's delimiter occurs in a body, or a Content-Type holds CR or LF.
292def encode(+b: String, parts: List<&1, Part>) -> Result<&1, &1, String, Bytes.Bytes>:
293  encode.if(boundary.ok(b), b, parts)
294
295def form.enc(+b: String, r: Result<&1, &1, String, Bytes.Bytes>) -> Result<&1, &1, U32 & String, String & Bytes.Bytes>:
296  match r:
297    case Fail{m}:
298      Fail{(22, m)}
299    case Done{body}:
300      Done{(content_type(b), body)}
301
302def form.of(r: Result<&1, &1, U32 & String, String>, parts: List<&1, Part>) -> Result<&1, &1, U32 & String, String & Bytes.Bytes>:
303  match r:
304    case Fail{e}:
305      Fail{e}
306    case Done{+b}:
307      form.enc(b, encode(b, parts))
308
309# The Content-Type value and body for parts, under a fresh random boundary.
310# Fails with the random source's error, or EINVAL (22) when encode fails.
311def form(parts: List<&1, Part>) -> IO(Result<&1, &1, U32 & String, String & Bytes.Bytes>):
312  do IO<Result<&1, &1, U32 & String, String & Bytes.Bytes>>:
313    r : Result<&1, &1, U32 & String, String> <- boundary.new()
314    return form.of(r, parts)
315
316# ---- streaming decoder
317
318# Pre: before the first delimiter. After: past a delimiter, before its line ends.
319# Heads: in a header block. Content: in a body. End: past the close delimiter.
320type Stage is Data:
321  Pre{}
322  After{}
323  Heads{}
324  Content{}
325  End{}
326
327type Step is Type:
328  More{stage: Stage, buf: Bytes.Bytes, out: List<&1, Item>}
329  Pause{stage: Stage, buf: Bytes.Bytes, out: List<&1, Item>}
330  Bad{error: String}
331
332# delim is CRLF "--" boundary and dlen its length; buf holds the bytes not yet decided.
333type Dec is Type:
334  Dec{delim: String, dlen: U32, stage: Stage, buf: Bytes.Bytes}
335
336# ponytail: a fixed cap on a header block or boundary line; make it a decoder field if a caller needs another.
337def MAX_HEAD() -> U32:
338  16384
339
340def drop(b: Bytes.Bytes, +n: U32) -> Bytes.Bytes:
341  Bytes.snd(Bytes.slice(b, n, 4294967295))
342
343def keep.two(+cut: U32, +k: U32, r: Bytes.Bytes & Bytes.Bytes) -> Bytes.Bytes & Bytes.Bytes:
344  (b, h) = r
345  (h, Bytes.snd(Bytes.slice(b, cut, k)))
346
347def keep.of(+k: U32, r: Bytes.Bytes & U32) -> Bytes.Bytes & Bytes.Bytes:
348  (b, +n) = r
349  +cut = (n - U32.min(k, n) : U32)
350  keep.two(cut, k, Bytes.slice(b, 0, cut))
351
352# b as (all but its last k bytes, its last k bytes).
353def keep(b: Bytes.Bytes, +k: U32) -> Bytes.Bytes & Bytes.Bytes:
354  keep.of(k, Bytes.length(b))
355
356def emit(empty: Bool, b: Bytes.Bytes, out: List<&1, Item>) -> List<&1, Item>:
357  match empty:
358    case True{}:
359      out
360    case False{}:
361      Con{Body{b}, out}
362
363def wait.if(big: Bool, st: Stage, buf: Bytes.Bytes, out: List<&1, Item>) -> Step:
364  match big:
365    case True{}:
366      Bad{"multipart: header block or boundary line too long"}
367    case False{}:
368      Pause{st, buf, out}
369
370# Wait for more input, unless the undecided bytes already pass MAX_HEAD.
371def wait.big(st: Stage, r: Bytes.Bytes & U32, out: List<&1, Item>) -> Step:
372  (buf, +n) = r
373  wait.if(U32.is_lt(MAX_HEAD(), n), st, buf, out)
374
375# What follows a delimiter match (RFC 2046 §5.1.1): "--", or transport padding then CRLF, makes it a
376# delimiter (0). Anything else makes it data, as "--Bextra" is for boundary B (1). Too few bytes: 2.
377def suffix.dash(s: String) -> U32:
378  match s:
379    case SNil{}:
380      2
381    case SCon{Chr{+c}, t}:
382      Bool.pick(U32, U32.is_eq(c, 45), 0, 1)
383
384def suffix.lf(s: String) -> U32:
385  match s:
386    case SNil{}:
387      2
388    case SCon{Chr{+c}, t}:
389      Bool.pick(U32, U32.is_eq(c, 10), 0, 1)
390
391def suffix(s: String, +first: Bool) -> U32:
392  match s:
393    case SNil{}:
394      2
395    case SCon{Chr{+c}, +t}:
396      Bool.pick(U32, Bool.and(first, U32.is_eq(c, 45)), suffix.dash(t), Bool.pick(U32, Bool.or(U32.is_eq(c, 32), U32.is_eq(c, 9)), suffix(t, False{}), Bool.pick(U32, U32.is_eq(c, 13), suffix.lf(t), 1)))
397
398# ponytail: looks at 64 bytes past the match; padding longer than that counts as data.
399def suffix.win(+s: String) -> U32:
400  +k = suffix(s, True{})
401  Bool.pick(U32, Bool.and(U32.is_eq(k, 2), U32.is_eq(Bytes.count(s, 0), 64)), 1, k)
402
403def suffix.of(r: Bytes.Bytes & Bytes.Bytes) -> Bytes.Bytes & U32:
404  (buf, w) = r
405  (buf, suffix.win(Bytes.to_string(w)))
406
407# The buffer and the kind of the match at i.
408def suffix.at(buf: Bytes.Bytes, +i: U32, +dlen: U32) -> Bytes.Bytes & U32:
409  suffix.of(Bytes.slice(buf, (i + dlen : U32), 64))
410
411# Pre: the preamble is dropped. Keeping dlen - 1 bytes means a delimiter split across chunks is still found.
412# A 0/1/2 suffix kind as two flags, since only a parameter can be matched.
413def pre.if(delim: Bool, data: Bool, buf: Bytes.Bytes, +i: U32, +dlen: U32, out: List<&1, Item>) -> Step:
414  match delim:
415    case True{}:
416      More{After{}, drop(buf, (i + dlen : U32)), out}
417    case False{}:
418      match data:
419        case True{}:
420          More{Pre{}, drop(buf, (i + 1 : U32)), out}
421        case False{}:
422          Pause{Pre{}, drop(buf, i), out}
423
424def pre.kind(r: Bytes.Bytes & U32, +i: U32, +dlen: U32, out: List<&1, Item>) -> Step:
425  (buf, +k) = r
426  pre.if(U32.is_eq(k, 0), U32.is_eq(k, 1), buf, i, dlen, out)
427
428def pre.hit(+dlen: U32, r: Bytes.Bytes & Maybe<&2, U32>, out: List<&1, Item>) -> Step:
429  (buf, hit) = r
430  match hit:
431    case Some{+i}:
432      pre.kind(suffix.at(buf, i, dlen), i, dlen, out)
433    case None{}:
434      Pause{Pre{}, Bytes.snd(keep(buf, (dlen - 1 : U32))), out}
435
436# After: suffix already saw "--" or padding then CRLF, so both are in buf. "--" closes the body.
437# The CRLF stays in buf, so the header block is found as CRLF ... CRLF CRLF, empty or not.
438def after.line(r: Bytes.Bytes & Maybe<&2, U32>, out: List<&1, Item>) -> Step:
439  (buf, hit) = r
440  match hit:
441    case Some{+i}:
442      More{Heads{}, drop(buf, i), out}
443    case None{}:
444      wait.big(After{}, Bytes.length(buf), out)
445
446def after.dash(r: Bytes.Bytes & Bool, out: List<&1, Item>) -> Step:
447  (buf, dash) = r
448  match dash:
449    case True{}:
450      More{End{}, Bytes.new(0), out}
451    case False{}:
452      after.line(Bytes.find(buf, "\r\n"), out)
453
454# Header block to a Head (RFC 7578 §4.2, §4.4). Other headers are ignored (§4.8).
455def meta.line(r: String & String, st: Maybe<&2, String> & Maybe<&2, String>) -> Maybe<&2, String> & Maybe<&2, String>:
456  (n, v) = r
457  (cd, ct) = st
458  +key = String.to_lower(String.trim(n))
459  +val = String.trim(v)
460  (Bool.pick(Maybe<&2, String>, String.eq(key, "content-disposition"), Some{val}, cd), Bool.pick(Maybe<&2, String>, String.eq(key, "content-type"), Some{val}, ct))
461
462def meta.go(lines: List<&2, String>, st: Maybe<&2, String> & Maybe<&2, String>) -> Maybe<&2, String> & Maybe<&2, String>:
463  match lines:
464    case Nil{}:
465      st
466    case Con{h, t}:
467      meta.go(t, meta.line(split1(h, 58), st))
468
469def head.named(n: Maybe<&2, String>, f: Maybe<&2, String>, ct: Maybe<&2, String>) -> Result<&1, &1, String, Item>:
470  match n:
471    case None{}:
472      Fail{"multipart: part has no name"}
473    case Some{x}:
474      Done{Head{unesc(x), unesc.m(f), ct}}
475
476def head.form(ok: Bool, +ps: List<&2, Param>, ct: Maybe<&2, String>) -> Result<&1, &1, String, Item>:
477  match ok:
478    case False{}:
479      Fail{"multipart: Content-Disposition is not form-data"}
480    case True{}:
481      head.named(lookup(ps, "name"), lookup(ps, "filename"), ct)
482
483def head.disp(r: String & String, ct: Maybe<&2, String>) -> Result<&1, &1, String, Item>:
484  (ty, rest) = r
485  head.form(String.eq(String.to_lower(String.trim(ty)), "form-data"), params(rest), ct)
486
487def head.meta(r: Maybe<&2, String> & Maybe<&2, String>) -> Result<&1, &1, String, Item>:
488  (cd, ct) = r
489  match cd:
490    case None{}:
491      Fail{"multipart: part has no Content-Disposition"}
492    case Some{v}:
493      head.disp(split1(v, 59), ct)
494
495# Lines split on LF; trimming drops each CR.
496def head.parse(block: String) -> Result<&1, &1, String, Item>:
497  head.meta(meta.go(String.split(block, Chr{10}), (None{}, None{})))
498
499def heads.item(h: Result<&1, &1, String, Item>, rest: Bytes.Bytes, out: List<&1, Item>) -> Step:
500  match h:
501    case Fail{e}:
502      Bad{e}
503    case Done{it}:
504      More{Content{}, rest, Con{it, out}}
505
506def heads.cut(+j: U32, r: Bytes.Bytes & Bytes.Bytes, out: List<&1, Item>) -> Step:
507  (buf, block) = r
508  heads.item(head.parse(Bytes.to_string(block)), drop(buf, (j + 4 : U32)), out)
509
510# buf starts with the CRLF that ended the boundary line, so a match at 0 is an empty block.
511def heads.found(r: Bytes.Bytes & Maybe<&2, U32>, out: List<&1, Item>) -> Step:
512  (buf, hit) = r
513  match hit:
514    case Some{+j}:
515      heads.cut(j, Bytes.slice(buf, 2, (U32.max(j, 2) - 2 : U32)), out)
516    case None{}:
517      wait.big(Heads{}, Bytes.length(buf), out)
518
519# Content: bytes that cannot begin a delimiter go out as Body; the last dlen - 1 wait for the next chunk.
520def text.flush.len(r: Bytes.Bytes & U32, tail: Bytes.Bytes, out: List<&1, Item>) -> Step:
521  (head, +n) = r
522  Pause{Content{}, tail, emit(U32.is_eq(n, 0), head, out)}
523
524def text.flush(r: Bytes.Bytes & Bytes.Bytes, out: List<&1, Item>) -> Step:
525  (head, tail) = r
526  text.flush.len(Bytes.length(head), tail, out)
527
528def text.cut(+i: U32, +dlen: U32, r: Bytes.Bytes & Bytes.Bytes, out: List<&1, Item>) -> Step:
529  (buf, piece) = r
530  More{After{}, drop(buf, (i + dlen : U32)), Con{Tail{}, emit(U32.is_eq(i, 0), piece, out)}}
531
532# A match that is data goes out through its first byte, and the search goes on after it.
533def text.data(+n: U32, r: Bytes.Bytes & Bytes.Bytes, out: List<&1, Item>) -> Step:
534  (buf, piece) = r
535  More{Content{}, drop(buf, n), emit(False{}, piece, out)}
536
537# A match whose suffix has not arrived: the bytes before it go out, and it waits.
538def text.hold(+i: U32, r: Bytes.Bytes & Bytes.Bytes, out: List<&1, Item>) -> Step:
539  (buf, piece) = r
540  Pause{Content{}, drop(buf, i), emit(U32.is_eq(i, 0), piece, out)}
541
542def text.if(delim: Bool, data: Bool, buf: Bytes.Bytes, +i: U32, +dlen: U32, out: List<&1, Item>) -> Step:
543  match delim:
544    case True{}:
545      text.cut(i, dlen, Bytes.slice(buf, 0, i), out)
546    case False{}:
547      match data:
548        case True{}:
549          text.data((i + 1 : U32), Bytes.slice(buf, 0, (i + 1 : U32)), out)
550        case False{}:
551          text.hold(i, Bytes.slice(buf, 0, i), out)
552
553def text.kind(r: Bytes.Bytes & U32, +i: U32, +dlen: U32, out: List<&1, Item>) -> Step:
554  (buf, +k) = r
555  text.if(U32.is_eq(k, 0), U32.is_eq(k, 1), buf, i, dlen, out)
556
557def text.hit(+dlen: U32, r: Bytes.Bytes & Maybe<&2, U32>, out: List<&1, Item>) -> Step:
558  (buf, hit) = r
559  match hit:
560    case Some{+i}:
561      text.kind(suffix.at(buf, i, dlen), i, dlen, out)
562    case None{}:
563      text.flush(keep(buf, (dlen - 1 : U32)), out)
564
565def step(st: Stage, +delim: String, +dlen: U32, buf: Bytes.Bytes, out: List<&1, Item>) -> Step:
566  match st:
567    case Pre{}:
568      pre.hit(dlen, Bytes.find(buf, delim), out)
569    case After{}:
570      after.dash(Bytes.starts_with(buf, "--"), out)
571    case Heads{}:
572      heads.found(Bytes.find(buf, "\r\n\r\n"), out)
573    case Content{}:
574      text.hit(dlen, Bytes.find(buf, delim), out)
575    case End{}:
576      Pause{End{}, Bytes.new(0), out}
577
578def go.stop(+delim: String, +dlen: U32, s: Step) -> Result<&1, &1, String, Dec & List<&1, Item>>:
579  match s:
580    case More{st, buf, out}:
581      Done{(Dec{delim, dlen, st, buf}, List.reverse(&1, Item, out))}
582    case Pause{st, buf, out}:
583      Done{(Dec{delim, dlen, st, buf}, List.reverse(&1, Item, out))}
584    case Bad{e}:
585      Fail{e}
586
587# Each More step consumes a byte, except the two after a delimiter, which itself consumes dlen >= 5,
588# so len + 8 steps suffice. Running out still returns a sound state: the next feed goes on from it.
589def go(fuel: Nat, +delim: String, +dlen: U32, s: Step) -> Result<&1, &1, String, Dec & List<&1, Item>>:
590  match fuel:
591    case 0n:
592      go.stop(delim, dlen, s)
593    case 1n+p:
594      match s:
595        case More{st, buf, out}:
596          go(p, delim, dlen, step(st, delim, dlen, buf, out))
597        case Pause{st, buf, out}:
598          go.stop(delim, dlen, Pause{st, buf, out})
599        case Bad{e}:
600          Fail{e}
601
602# A decoder for boundary b. It starts with a CRLF, so a delimiter at the very start is found like any other.
603def decoder(b: String) -> Dec:
604  +delim = "\r\n--" ++ b
605  Dec{delim, Bytes.count(delim, 0), Pre{}, Bytes.from_string("\r\n")}
606
607def feed.go(+delim: String, +dlen: U32, st: Stage, r: Bytes.Bytes & U32) -> Result<&1, &1, String, Dec & List<&1, Item>>:
608  (buf, +n) = r
609  go(U32.to_nat((n + 8 : U32)), delim, dlen, More{st, buf, Nil{}})
610
611# The next chunk of a body, in any split. Answers the decoder and the items the chunk completes,
612# or the first error. A body piece is held back only while it could start a delimiter.
613def feed(d: Dec, chunk: Bytes.Bytes) -> Result<&1, &1, String, Dec & List<&1, Item>>:
614  Dec{+delim, +dlen, st, buf} = d
615  feed.go(delim, dlen, st, Bytes.length(Bytes.append(buf, chunk)))
616
617# Done once the close delimiter has been read; the epilogue is ignored.
618def finish(d: Dec) -> Result<&1, &1, String, Unit>:
619  Dec{delim, dlen, st, buf} = d
620  match st:
621    case End{}:
622      Done{Unit{}}
623    case _:
624      Fail{"multipart: body ends before the close delimiter"}
625
626def collect.add(ps: List<&1, Part>, b: Bytes.Bytes) -> List<&1, Part>:
627  match ps:
628    case Nil{}:
629      Nil{}
630    case Con{Part{n, f, c, body}, t}:
631      Con{Part{n, f, c, Bytes.append(body, b)}, t}
632
633# Items folded into parts, latest first.
634def collect(items: List<&1, Item>, ps: List<&1, Part>) -> List<&1, Part>:
635  match items:
636    case Nil{}:
637      ps
638    case Con{Head{n, f, c}, t}:
639      collect(t, Con{Part{n, f, c, Bytes.new(0)}, ps})
640    case Con{Body{b}, t}:
641      collect(t, collect.add(ps, b))
642    case Con{Tail{}, t}:
643      collect(t, ps)
644
645def chunks.fed(r: Result<&1, &1, String, Dec & List<&1, Item>>, ps: List<&1, Part>) -> Result<&1, &1, String, Dec & List<&1, Part>>:
646  match r:
647    case Fail{e}:
648      Fail{e}
649    case Done{(d, items)}:
650      Done{(d, collect(items, ps))}
651
652def chunks.step(st: Result<&1, &1, String, Dec & List<&1, Part>>, c: Bytes.Bytes) -> Result<&1, &1, String, Dec & List<&1, Part>>:
653  match st:
654    case Fail{e}:
655      Fail{e}
656    case Done{(d, ps)}:
657      chunks.fed(feed(d, c), ps)
658
659def chunks.fin(r: Result<&1, &1, String, Unit>, ps: List<&1, Part>) -> Result<&1, &1, String, List<&1, Part>>:
660  match r:
661    case Fail{e}:
662      Fail{e}
663    case Done{u}:
664      Done{List.reverse(&1, Part, ps)}
665
666def chunks.end(st: Result<&1, &1, String, Dec & List<&1, Part>>) -> Result<&1, &1, String, List<&1, Part>>:
667  match st:
668    case Fail{e}:
669      Fail{e}
670    case Done{(d, ps)}:
671      chunks.fin(finish(d), ps)
672
673def chunks.go(cs: List<&1, Bytes.Bytes>, st: Result<&1, &1, String, Dec & List<&1, Part>>) -> Result<&1, &1, String, List<&1, Part>>:
674  match cs:
675    case Nil{}:
676      chunks.end(st)
677    case Con{c, t}:
678      chunks.go(t, chunks.step(st, c))
679
680# The parts of a body that arrives as chunks, split anywhere.
681def decode.chunks(b: String, cs: List<&1, Bytes.Bytes>) -> Result<&1, &1, String, List<&1, Part>>:
682  chunks.go(cs, Done{(decoder(b), Nil{})})
683
684# The parts of a whole body.
685def decode(b: String, body: Bytes.Bytes) -> Result<&1, &1, String, List<&1, Part>>:
686  decode.chunks(b, [body])