1	# tar archives (POSIX ustar with PAX path and size records) of regular files and directories over Bytes. Source: https://github.com/paymog/bend-kit/tree/main/tar
2	import Base
3	import bend-kit-bytes@0.3.3.0/bytes.bend as Bytes
4	
5	# An archive is a list of entries in order. Names are raw bytes (UTF-8 by convention), kept byte for byte;
6	# a directory keeps whatever trailing '/' its name has. Nothing here touches the filesystem.
7	#   import ./tar/tar.bend as Tar
8	type Entry is Type:
9	  File{name: Bytes.Bytes, data: Bytes.Bytes}
10	  Dir{name: Bytes.Bytes}
11	
12	
13	# n rounded up to a whole 512-byte block; 0 when that would pass U32.
14	def pad(+n: U32) -> U32:
15	  ((n + 511 : U32) .&. 4294966784 : U32)
16	
17	# The sum of w's four bytes.
18	def wsum(+w: U32) -> U32:
19	  ((w .&. 255) + ((w >> 8n) .&. 255) + ((w >> 16n) .&. 255) + (w >> 24n) : U32)
20	
21	def bsum.go(n: Nat, r: Array<U32> & U32, +k: U32, +acc: U32) -> Array<U32> & U32:
22	  match n:
23	    case 0n:
24	      (a, w) = r
25	      (a, acc)
26	    case 1n+p:
27	      (a, +w) = r
28	      bsum.go(p, Array.get(U32, a, (k + 1 : U32)), (k + 1 : U32), (acc + wsum(w) : U32))
29	
30	# The sum of the 512 bytes from word k: 0 only for a zero block.
31	def bsum(a: Array<U32>, +k: U32) -> Array<U32> & U32:
32	  bsum.go(128n, Array.get(U32, a, k), k, 0)
33	
34	# Octal digits after leading spaces, ended by NUL, space, or the field's end. ph: 0 leading, 1 digits, 2 done.
35	def oct.go(n: Nat, r: Array<U32> & U32, +j: U32, +ph: U32, +acc: U32, +ok: Bool) -> Array<U32> & U32 & Bool:
36	  match n:
37	    case 0n:
38	      (a, c) = r
39	      (a, acc, ok)
40	    case 1n+p:
41	      (a, +c) = r
42	      +live = U32.is_ne(ph, 2)
43	      +dig = live && Bytes.in(48, c, 55)
44	      +bad = live && Bool.not(Bytes.in(48, c, 55) || (U32.is_eq(c, 32) || U32.is_eq(c, 0)))
45	      +over = dig && U32.is_lt(536870911, acc)
46	      +ph2 = Bool.pick(U32, live, Bool.pick(U32, dig, 1, Bool.pick(U32, U32.is_eq(ph, 0) && U32.is_eq(c, 32), 0, 2)), 2)
47	      +acc2 = Bool.pick(U32, dig, ((acc << 3n) .|. (c - 48) : U32), acc)
48	      oct.go(p, Bytes.peek(a, (j + 1 : U32)), (j + 1 : U32), ph2, acc2, ok && Bool.not(bad || over))
49	
50	# The octal field of w bytes at j, and whether it is well formed and fits a U32.
51	def oct(a: Array<U32>, +j: U32, +w: U32) -> Array<U32> & U32 & Bool:
52	  oct.go(U32.to_nat(w), Bytes.peek(a, j), j, 0, 0, True{})
53	
54	def cstr.go(n: Nat, r: Array<U32> & U32, +j: U32, +k: U32, +done: Bool) -> Array<U32> & U32:
55	  match n:
56	    case 0n:
57	      (a, c) = r
58	      (a, k)
59	    case 1n+p:
60	      (a, +c) = r
61	      match done:
62	        case True{}:
63	          (a, k)
64	        case False{}:
65	          +stop = U32.is_eq(c, 0)
66	          cstr.go(p, Bytes.peek(a, (j + 1 : U32)), (j + 1 : U32), Bool.pick(U32, stop, k, (k + 1 : U32)), stop)
67	
68	# The count of bytes before the first NUL in the w bytes from j.
69	def cstr(a: Array<U32>, +j: U32, +w: U32) -> Array<U32> & U32:
70	  cstr.go(U32.to_nat(w), Bytes.peek(a, j), j, 0, False{})
71	
72	type Dec is Data:
73	  Dec{v: U32, digits: U32, stop: U32, ended: Bool, ok: Bool}
74	
75	type DByte is Data:
76	  DByte{byte: U32, digit: Bool}
77	
78	def dec.byte.of(+len: U32, r: Array<U32> & U32) -> Bytes.Bytes & Maybe<&2, DByte>:
79	  (a, +b) = r
80	  (Bytes.Bytes{len, a}, Some{DByte{b, Bytes.in(48, b, 57)}})
81	
82	def dec.byte(b: Bytes.Bytes, +i: U32) -> Bytes.Bytes & Maybe<&2, DByte>:
83	  Bytes.Bytes{+len, a} = b
84	  dec.byte.of(len, Bytes.peek(a, i))
85	
86	# Consume decimal digits and, when present, their first non-digit delimiter.
87	def dec.go(n: Nat, r: Bytes.Cursor & Maybe<&2, DByte>, +acc: U32, +digits: U32, +ok: Bool) -> Bytes.Cursor & Dec:
88	  match n:
89	    case 0n:
90	      (c, m) = r
91	      (c, Dec{acc, digits, 0, True{}, ok})
92	    case 1n+p:
93	      (c, m) = r
94	      match m:
95	        case None{}:
96	          (c, Dec{acc, digits, 0, True{}, False{}})
97	        case Some{DByte{+b, digit}}:
98	          match digit:
99	            case False{}:
100	              (c, Dec{acc, digits, b, False{}, ok})
101	            case True{}:
102	              +v = (b - 48 : U32)
103	              +fit = U32.is_lt(acc, 429496729) || (U32.is_eq(acc, 429496729) && U32.is_le(v, 5))
104	              dec.go(p, Bytes.Cursor.read(~DByte, ~dec.byte, c, 1), ((acc * 10) + v : U32), (digits + 1 : U32), ok && fit)
105	
106	def dec.start(r: Bytes.Cursor & U32) -> Bytes.Cursor & Dec:
107	  (c, +n) = r
108	  dec.go(U32.to_nat(n), Bytes.Cursor.read(~DByte, ~dec.byte, c, 1), 0, 0, True{})
109	
110	def dec(c: Bytes.Cursor) -> Bytes.Cursor & Dec:
111	  dec.start(Bytes.Cursor.remaining(c))
112	
113	# ---- decode ----
114	
115	# Header i's name: prefix "/" name when the magic is POSIX ustar and the prefix is not empty.
116	def name.fin(+total: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Bytes.Bytes:
117	  (a, o) = r
118	  (a, Bytes.Bytes{total, o})
119	
120	def name.join(+i: U32, +n: U32, +pl: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Bytes.Bytes:
121	  (a, o) = r
122	  +some = U32.is_ne(pl, 0)
123	  +off = Bool.pick(U32, some, (pl + 1 : U32), 0)
124	  name.fin((off + n : U32), Bytes.copy(n, a, Bytes.poke.when(some, o, pl, 47), i, off))
125	
126	def name.pre(+i: U32, +n: U32, r: Array<U32> & U32) -> Array<U32> & Bytes.Bytes:
127	  (a, +pl) = r
128	  +off = Bool.pick(U32, U32.is_ne(pl, 0), (pl + 1 : U32), 0)
129	  name.join(i, n, pl, Bytes.copy(pl, a, Bytes.alloc((off + n : U32)), (i + 345 : U32), 0))
130	
131	def pfx.len(ustar: Bool, a: Array<U32>, +i: U32) -> Array<U32> & U32:
132	  match ustar:
133	    case True{}:
134	      cstr(a, (i + 345 : U32), 155)
135	    case False{}:
136	      (a, 0)
137	
138	def name.magic(+i: U32, +n: U32, r: Array<U32> & Bool) -> Array<U32> & Bytes.Bytes:
139	  (a, ustar) = r
140	  name.pre(i, n, pfx.len(ustar, a, i))
141	
142	def name.len(+i: U32, r: Array<U32> & U32) -> Array<U32> & Bytes.Bytes:
143	  (a, +n) = r
144	  name.magic(i, n, Bytes.at(a, "ustar\u{0}", (i + 257 : U32)))
145	
146	def header.name(a: Array<U32>, +i: U32) -> Array<U32> & Bytes.Bytes:
147	  name.len(i, cstr(a, i, 100))
148	
149	# Records from an 'x' header that apply to the next entry.
150	type Pax is Type:
151	  Pax{path: Maybe<&1, Bytes.Bytes>, size: Maybe<&2, U32>}
152	
153	type Pst is Type:
154	  PGo{pax: Pax}
155	  PEnd{pax: Pax}
156	  PBad{}
157	
158	type PKey is Data:
159	  PPath{}
160	  PSize{}
161	  POther{}
162	
163	def pr.key.size(hit: Bool, +len: U32, a: Array<U32>) -> Bytes.Bytes & Maybe<&2, PKey>:
164	  match hit:
165	    case True{}:
166	      (Bytes.Bytes{len, a}, Some{PSize{}})
167	    case False{}:
168	      (Bytes.Bytes{len, a}, Some{POther{}})
169	
170	def pr.key.sized(+len: U32, r: Array<U32> & Bool) -> Bytes.Bytes & Maybe<&2, PKey>:
171	  (a, hit) = r
172	  pr.key.size(hit, len, a)
173	
174	def pr.key.path(+i: U32, +len: U32, r: Array<U32> & Bool) -> Bytes.Bytes & Maybe<&2, PKey>:
175	  (a, hit) = r
176	  match hit:
177	    case True{}:
178	      (Bytes.Bytes{len, a}, Some{PPath{}})
179	    case False{}:
180	      pr.key.sized(len, Bytes.at(a, "size=", i))
181	
182	# The cursor bounds both fixed keyword probes; short or unknown bodies are skipped.
183	def pr.key(b: Bytes.Bytes, +i: U32) -> Bytes.Bytes & Maybe<&2, PKey>:
184	  Bytes.Bytes{+len, a} = b
185	  pr.key.path(i, len, Bytes.at(a, "path=", i))
186	
187	def pr.opt(has: Bool, b: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
188	  match has:
189	    case True{}:
190	      Some{b}
191	    case False{}:
192	      None{}
193	
194	# An empty value unsets the keyword, so the header's own name applies.
195	def pr.path.done(+start: U32, +end: U32, +n: U32, pax: Pax, r: Bytes.Bytes & Bytes.Bytes) -> Bytes.Cursor & Pst:
196	  Pax{old, size} = pax
197	  (b, value) = r
198	  (Bytes.Cursor{b, end, start, end}, PGo{Pax{pr.opt(U32.is_ne(n, 0), value), size}})
199	
200	def pr.path(c: Bytes.Cursor, pax: Pax) -> Bytes.Cursor & Pst:
201	  Bytes.Cursor{b, +pos, +start, +end} = c
202	  pr.path.done(start, end, (end - pos : U32), pax, Bytes.slice(b, pos, (end - pos : U32)))
203	
204	def pr.size.valid(ok: Bool, c: Bytes.Cursor, +v: U32, path: Maybe<&1, Bytes.Bytes>) -> Bytes.Cursor & Pst:
205	  match ok:
206	    case True{}:
207	      (c, PGo{Pax{path, Some{v}}})
208	    case False{}:
209	      (c, PBad{})
210	
211	def pr.size.done(pax: Pax, r: Bytes.Cursor & Dec) -> Bytes.Cursor & Pst:
212	  Pax{path, old} = pax
213	  (c, d) = r
214	  Dec{+v, +digits, stop, +ended, +ok} = d
215	  pr.size.valid(ok && ended && U32.is_ne(digits, 0), c, v, path)
216	
217	def pr.checked(r: Bytes.Cursor & Bool, pax: Pax) -> Bytes.Cursor & Pst:
218	  (c, ok) = r
219	  match ok:
220	    case True{}:
221	      (c, PGo{pax})
222	    case False{}:
223	      (c, PBad{})
224	
225	def pr.skip(c: Bytes.Cursor, pax: Pax) -> Bytes.Cursor & Pst:
226	  Bytes.Cursor{b, pos, start, +end} = c
227	  pr.checked(Bytes.Cursor.seek(Bytes.Cursor{b, pos, start, end}, end), pax)
228	
229	def pr.value(pax: Pax, r: Bytes.Cursor & Maybe<&2, PKey>) -> Bytes.Cursor & Pst:
230	  (c, key) = r
231	  match key:
232	    case None{}:
233	      pr.skip(c, pax)
234	    case Some{k}:
235	      match k:
236	        case PPath{}:
237	          pr.path(c, pax)
238	        case PSize{}:
239	          pr.size.done(pax, dec(c))
240	        case POther{}:
241	          pr.skip(c, pax)
242	
243	def pr.nl(pax: Pax, r: Bytes.Cursor & Maybe<&2, U32>) -> Bytes.Cursor & Pst:
244	  (c, m) = r
245	  match m:
246	    case None{}:
247	      (c, PBad{})
248	    case Some{+b}:
249	      pr.checked((c, U32.is_eq(b, 10)), pax)
250	
251	def pr.close(limit: Bytes.CursorLimit, r: Bytes.Cursor & Pst) -> Bytes.Cursor & Pst:
252	  (c, st) = r
253	  match st:
254	    case PGo{pax}:
255	      pr.nl(pax, Bytes.Cursor.u8(Bytes.Cursor.leave(c, limit)))
256	    case PEnd{pax}:
257	      (Bytes.Cursor.leave(c, limit), PBad{})
258	    case PBad{}:
259	      (Bytes.Cursor.leave(c, limit), PBad{})
260	
261	def pr.body(pax: Pax, r: Bytes.Cursor & Maybe<&1, Bytes.CursorLimit>) -> Bytes.Cursor & Pst:
262	  (c, m) = r
263	  match m:
264	    case None{}:
265	      (c, PBad{})
266	    case Some{limit}:
267	      pr.close(limit, pr.value(pax, Bytes.Cursor.read(~PKey, ~pr.key, c, 5)))
268	
269	def pr.len.valid(ok: Bool, c: Bytes.Cursor, +body: U32, pax: Pax) -> Bytes.Cursor & Pst:
270	  match ok:
271	    case False{}:
272	      (c, PBad{})
273	    case True{}:
274	      pr.body(pax, Bytes.Cursor.region(c, body))
275	
276	# Length includes its digits, the space, the bounded body and its final newline.
277	def pr.len(+available: U32, pax: Pax, r: Bytes.Cursor & Dec) -> Bytes.Cursor & Pst:
278	  (c, d) = r
279	  Dec{+len, +digits, +stop, +ended, +ok} = d
280	  pr.len.valid(ok && Bool.not(ended) && U32.is_eq(stop, 32) && U32.is_ne(digits, 0) && U32.is_lt((digits + 1 : U32), len) && U32.is_le(len, available), c, (len - digits - 2 : U32), pax)
281	
282	def pr.more.if(done: Bool, c: Bytes.Cursor, +n: U32, pax: Pax) -> Bytes.Cursor & Pst:
283	  match done:
284	    case True{}:
285	      (c, PEnd{pax})
286	    case False{}:
287	      pr.len(n, pax, dec(c))
288	
289	def pr.more(pax: Pax, r: Bytes.Cursor & U32) -> Bytes.Cursor & Pst:
290	  (c, +n) = r
291	  pr.more.if(U32.is_eq(n, 0), c, n, pax)
292	
293	# Each record consumes at least three bytes; leave fuel for the end transition.
294	def pr.run(fuel: Nat, r: Bytes.Cursor & Pst) -> Bytes.Cursor & Maybe<&1, Pax>:
295	  match fuel:
296	    case 0n:
297	      (c, st) = r
298	      (c, None{})
299	    case 1n+f:
300	      (c, st) = r
301	      match st:
302	        case PGo{pax}:
303	          pr.run(f, pr.more(pax, Bytes.Cursor.remaining(c)))
304	        case PEnd{pax}:
305	          (c, Some{pax})
306	        case PBad{}:
307	          (c, None{})
308	
309	def pr.start(pax: Pax, r: Bytes.Cursor & U32) -> Bytes.Cursor & Maybe<&1, Pax>:
310	  (c, +n) = r
311	  pr.run(U32.to_nat(((n >> 1n) + 2 : U32)), (c, PGo{pax}))
312	
313	# c is already bounded to exactly the PAX payload, without block padding.
314	def pr.parse(c: Bytes.Cursor, pax: Pax) -> Bytes.Cursor & Maybe<&1, Pax>:
315	  pr.start(pax, Bytes.Cursor.remaining(c))
316	
317	type St is Type:
318	  SHead{pax: Pax, acc: List<&1, Entry>}
319	  SOk{entries: List<&1, Entry>}
320	  SFail{}
321	
322	# Header metadata is Data so a checked read can advance without copying the header.
323	type Hdr is Data:
324	  Hdr{sum: U32, ok: Bool, size: U32, size_ok: Bool, kind: U32}
325	
326	def hdr.kind(+len: U32, +sum: U32, +ok: Bool, +size: U32, +size_ok: Bool, r: Array<U32> & U32) -> Bytes.Bytes & Maybe<&2, Hdr>:
327	  (a, t) = r
328	  (Bytes.Bytes{len, a}, Some{Hdr{sum, ok, size, size_ok, t}})
329	
330	def hdr.size(+len: U32, +i: U32, +sum: U32, +ok: Bool, r: Array<U32> & U32 & Bool) -> Bytes.Bytes & Maybe<&2, Hdr>:
331	  (a, size, size_ok) = r
332	  hdr.kind(len, sum, ok, size, size_ok, Bytes.peek(a, (i + 156 : U32)))
333	
334	def hdr.valid(ok: Bool, +len: U32, +i: U32, +sum: U32, a: Array<U32>) -> Bytes.Bytes & Maybe<&2, Hdr>:
335	  match ok:
336	    case True{}:
337	      hdr.size(len, i, sum, True{}, oct(a, (i + 124 : U32), 12))
338	    case False{}:
339	      (Bytes.Bytes{len, a}, Some{Hdr{sum, False{}, 0, False{}, 0}})
340	
341	# The checksum's eight bytes count as spaces.
342	def hdr.ck3(+len: U32, +i: U32, +sum: U32, +ck: U32, +ok: Bool, +x: U32, r: Array<U32> & U32) -> Bytes.Bytes & Maybe<&2, Hdr>:
343	  (a, +w) = r
344	  hdr.valid(ok && U32.is_eq(ck, (sum - x - wsum(w) + 256 : U32)), len, i, sum, a)
345	
346	def hdr.ck2(+len: U32, +i: U32, +sum: U32, +ck: U32, +ok: Bool, r: Array<U32> & U32) -> Bytes.Bytes & Maybe<&2, Hdr>:
347	  (a, +w) = r
348	  hdr.ck3(len, i, sum, ck, ok, wsum(w), Array.get(U32, a, ((i >> 2n) + 38 : U32)))
349	
350	def hdr.check(+len: U32, +i: U32, +sum: U32, r: Array<U32> & U32 & Bool) -> Bytes.Bytes & Maybe<&2, Hdr>:
351	  (a, ck, ok) = r
352	  hdr.ck2(len, i, sum, ck, ok, Array.get(U32, a, ((i >> 2n) + 37 : U32)))
353	
354	def hdr.zero(zero: Bool, +len: U32, +i: U32, +sum: U32, a: Array<U32>) -> Bytes.Bytes & Maybe<&2, Hdr>:
355	  match zero:
356	    case True{}:
357	      (Bytes.Bytes{len, a}, Some{Hdr{0, False{}, 0, True{}, 0}})
358	    case False{}:
359	      hdr.check(len, i, sum, oct(a, (i + 148 : U32), 8))
360	
361	def hdr.sum(+len: U32, +i: U32, r: Array<U32> & U32) -> Bytes.Bytes & Maybe<&2, Hdr>:
362	  (a, +sum) = r
363	  hdr.zero(U32.is_eq(sum, 0), len, i, sum, a)
364	
365	# Cursor.read establishes that all fixed offsets below belong to a complete block.
366	def hdr.read(b: Bytes.Bytes, +i: U32) -> Bytes.Bytes & Maybe<&2, Hdr>:
367	  Bytes.Bytes{+len, a} = b
368	  hdr.sum(len, i, bsum(a, (i >> 2n : U32)))
369	
370	def zero.sum(+len: U32, r: Array<U32> & U32) -> Bytes.Bytes & Maybe<&2, U32>:
371	  (a, sum) = r
372	  (Bytes.Bytes{len, a}, Some{sum})
373	
374	def zero.read(b: Bytes.Bytes, +i: U32) -> Bytes.Bytes & Maybe<&2, U32>:
375	  Bytes.Bytes{+len, a} = b
376	  zero.sum(len, bsum(a, (i >> 2n : U32)))
377	
378	def name.of(path: Maybe<&1, Bytes.Bytes>, a: Array<U32>, +i: U32) -> Array<U32> & Bytes.Bytes:
379	  match path:
380	    case Some{b}:
381	      (a, b)
382	    case None{}:
383	      header.name(a, i)
384	
385	def entry.named(+len: U32, +pos: U32, start: U32, end: U32, r: Array<U32> & Bytes.Bytes) -> Bytes.Cursor & Bytes.Bytes:
386	  (a, name) = r
387	  (Bytes.Cursor{Bytes.Bytes{len, a}, pos, start, end}, name)
388	
389	# The header begins one block before the payload cursor; no separate header index survives.
390	def entry.name(c: Bytes.Cursor, path: Maybe<&1, Bytes.Bytes>) -> Bytes.Cursor & Bytes.Bytes:
391	  Bytes.Cursor{Bytes.Bytes{+len, a}, +pos, start, end} = c
392	  entry.named(len, pos, start, end, name.of(path, a, (pos - 512 : U32)))
393	
394	def file.data(+len: U32, pos: U32, start: U32, end: U32, +size: U32, name: Bytes.Bytes, acc: List<&1, Entry>, r: Array<U32> & Array<U32>) -> Bytes.Cursor & St:
395	  (a, o) = r
396	  (Bytes.Cursor{Bytes.Bytes{len, a}, pos, start, end}, SHead{Pax{None{}, None{}}, Con{File{name, Bytes.Bytes{size, o}}, acc}})
397	
398	def file.name(+size: U32, acc: List<&1, Entry>, r: Bytes.Cursor & Bytes.Bytes) -> Bytes.Cursor & St:
399	  (c, name) = r
400	  Bytes.Cursor{Bytes.Bytes{+len, a}, +pos, start, end} = c
401	  file.data(len, pos, start, end, size, name, acc, Bytes.copy(size, a, Bytes.alloc(size), pos, 0))
402	
403	def entry.file(c: Bytes.Cursor, +size: U32, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
404	  Pax{path, s} = pax
405	  file.name(size, acc, entry.name(c, path))
406	
407	def dir.name(acc: List<&1, Entry>, r: Bytes.Cursor & Bytes.Bytes) -> Bytes.Cursor & St:
408	  (c, name) = r
409	  (c, SHead{Pax{None{}, None{}}, Con{Dir{name}, acc}})
410	
411	# Leaving the payload region skips a directory's data, as it does global PAX records.
412	def entry.dir(c: Bytes.Cursor, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
413	  Pax{path, s} = pax
414	  dir.name(acc, entry.name(c, path))
415	
416	def step.pax(acc: List<&1, Entry>, r: Bytes.Cursor & Maybe<&1, Pax>) -> Bytes.Cursor & St:
417	  (c, m) = r
418	  match m:
419	    case Some{pax}:
420	      (c, SHead{pax, acc})
421	    case None{}:
422	      (c, SFail{})
423	
424	# '0'/NUL are files, '5' directories, 'x' local PAX and 'g' ignored global PAX.
425	# Links, devices, FIFOs, GNU extensions and all other types fail.
426	def step.type(+t: U32, c: Bytes.Cursor, +size: U32, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
427	  match t:
428	    case 0:
429	      entry.file(c, size, pax, acc)
430	    case 48:
431	      entry.file(c, size, pax, acc)
432	    case 53:
433	      entry.dir(c, pax, acc)
434	    case 120:
435	      step.pax(acc, pr.parse(c, pax))
436	    case 103:
437	      (c, SHead{pax, acc})
438	    case _:
439	      (c, SFail{})
440	
441	def frame.padded(outer: Bytes.CursorLimit, st: St, r: Bytes.Cursor & Bool) -> Bytes.Cursor & St:
442	  (c, ok) = r
443	  match ok:
444	    case True{}:
445	      (Bytes.Cursor.leave(c, outer), st)
446	    case False{}:
447	      (Bytes.Cursor.leave(c, outer), SFail{})
448	
449	def frame.body(inner: Bytes.CursorLimit, outer: Bytes.CursorLimit, +padding: U32, r: Bytes.Cursor & St) -> Bytes.Cursor & St:
450	  (c, st) = r
451	  frame.padded(outer, st, Bytes.Cursor.skip(Bytes.Cursor.leave(c, inner), padding))
452	
453	def frame.payload(+t: U32, +size: U32, +padding: U32, outer: Bytes.CursorLimit, pax: Pax, acc: List<&1, Entry>, r: Bytes.Cursor & Maybe<&1, Bytes.CursorLimit>) -> Bytes.Cursor & St:
454	  (c, m) = r
455	  match m:
456	    case Some{inner}:
457	      frame.body(inner, outer, padding, step.type(t, c, size, pax, acc))
458	    case None{}:
459	      (Bytes.Cursor.leave(c, outer), SFail{})
460	
461	# First bound the complete padded body, then restrict PAX to the exact payload.
462	# Limits are left in reverse order; neither region slices or copies the backing buffer.
463	def frame.region(+t: U32, +size: U32, +pd: U32, pax: Pax, acc: List<&1, Entry>, r: Bytes.Cursor & Maybe<&1, Bytes.CursorLimit>) -> Bytes.Cursor & St:
464	  (c, m) = r
465	  match m:
466	    case Some{outer}:
467	      frame.payload(t, size, (pd - size : U32), outer, pax, acc, Bytes.Cursor.region(c, size))
468	    case None{}:
469	      (c, SFail{})
470	
471	def step.fit(ok: Bool, +t: U32, c: Bytes.Cursor, +size: U32, +pd: U32, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
472	  match ok:
473	    case True{}:
474	      frame.region(t, size, pd, pax, acc, Bytes.Cursor.region(c, pd))
475	    case False{}:
476	      (c, SFail{})
477	
478	def step.pad(+t: U32, c: Bytes.Cursor, +size: U32, +ok: Bool, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
479	  +pd = pad(size)
480	  step.fit(ok && U32.is_le(size, pd), t, c, size, pd, pax, acc)
481	
482	# A pending PAX size overrides the header field for every type, even when that field is malformed.
483	def step.size(+t: U32, c: Bytes.Cursor, +v: U32, +ok: Bool, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
484	  Pax{path, +psize} = pax
485	  step.pad(t, c, Maybe.default(&2, U32, psize, v), Maybe.is_some(&2, U32, psize) || ok, Pax{path, psize}, acc)
486	
487	def step.hdr(ok: Bool, +t: U32, c: Bytes.Cursor, +size: U32, +size_ok: Bool, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
488	  match ok:
489	    case True{}:
490	      step.size(t, c, size, size_ok, pax, acc)
491	    case False{}:
492	      (c, SFail{})
493	
494	# Two zero blocks are required and no local PAX records may remain pending.
495	def end.pax(pax: Pax, acc: List<&1, Entry>) -> St:
496	  Pax{p, s} = pax
497	  match p s:
498	    case None{} None{}:
499	      SOk{List.reverse(&1, Entry, acc)}
500	    case _ _:
501	      SFail{}
502	
503	def end.of(ok: Bool, pax: Pax, acc: List<&1, Entry>) -> St:
504	  match ok:
505	    case True{}:
506	      end.pax(pax, acc)
507	    case False{}:
508	      SFail{}
509	
510	def end.sum(pax: Pax, acc: List<&1, Entry>, r: Bytes.Cursor & Maybe<&2, U32>) -> Bytes.Cursor & St:
511	  (c, m) = r
512	  match m:
513	    case Some{+sum}:
514	      (c, end.of(U32.is_eq(sum, 0), pax, acc))
515	    case None{}:
516	      (c, SFail{})
517	
518	def step.zero(zero: Bool, +ok: Bool, +size: U32, +size_ok: Bool, +t: U32, c: Bytes.Cursor, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
519	  match zero:
520	    case True{}:
521	      end.sum(pax, acc, Bytes.Cursor.read(~U32, ~zero.read, c, 512))
522	    case False{}:
523	      step.hdr(ok, t, c, size, size_ok, pax, acc)
524	
525	def step.read(pax: Pax, acc: List<&1, Entry>, r: Bytes.Cursor & Maybe<&2, Hdr>) -> Bytes.Cursor & St:
526	  (c, m) = r
527	  match m:
528	    case Some{Hdr{+sum, +ok, +size, +size_ok, +t}}:
529	      step.zero(U32.is_eq(sum, 0), ok, size, size_ok, t, c, pax, acc)
530	    case None{}:
531	      (c, SFail{})
532	
533	def step(c: Bytes.Cursor, pax: Pax, acc: List<&1, Entry>) -> Bytes.Cursor & St:
534	  step.read(pax, acc, Bytes.Cursor.read(~Hdr, ~hdr.read, c, 512))
535	
536	def run(fuel: Nat, r: Bytes.Cursor & St) -> Maybe<&1, List<&1, Entry>>:
537	  match fuel:
538	    case 0n:
539	      None{}
540	    case 1n+f:
541	      (c, st) = r
542	      match st:
543	        case SOk{xs}:
544	          Some{xs}
545	        case SFail{}:
546	          None{}
547	        case SHead{pax, acc}:
548	          run(f, step(c, pax, acc))
549	
550	# The entries in archive order. None for a bad header checksum, a malformed size or PAX record,
551	# an entry or its padding cut short, a missing end (two zero blocks), or any type but file,
552	# directory, and PAX records. Bytes after the end are ignored.
553	# fuel: each header step eats a block, so len / 512 + 2 steps are enough.
554	def decode(archive: Bytes.Bytes) -> Maybe<&1, List<&1, Entry>>:
555	  Bytes.Bytes{+len, buf} = archive
556	  run(U32.to_nat(((len >> 9n) + 2 : U32)), (Bytes.Cursor.new(Bytes.Bytes{len, buf}), SHead{Pax{None{}, None{}}, Nil{}}))
557	
558	# ---- encode ----
559	
560	def put.str(s: String, a: Array<U32>, +j: U32) -> Array<U32>:
561	  match s:
562	    case SNil{}:
563	      a
564	    case SCon{Chr{+c}, t}:
565	      put.str(t, Bytes.poke(a, j, c), (j + 1 : U32))
566	
567	# n octal digits of v ending at j, written back to front.
568	def oct.put(n: Nat, a: Array<U32>, +j: U32, +v: U32) -> Array<U32>:
569	  match n:
570	    case 0n:
571	      a
572	    case 1n+p:
573	      oct.put(p, Bytes.poke(a, j, (48 + (v .&. 7) : U32)), (j - 1 : U32), (v >> 3n : U32))
574	
575	# n decimal digits of v ending at j, written back to front.
576	def dec.put(n: Nat, a: Array<U32>, +j: U32, +v: U32) -> Array<U32>:
577	  match n:
578	    case 0n:
579	      a
580	    case 1n+p:
581	      dec.put(p, Bytes.poke(a, j, (48 + (v % 10) : U32)), (j - 1 : U32), (v / 10 : U32))
582	
583	def digits.go(n: Nat, +v: U32, +c: U32) -> U32:
584	  match n:
585	    case 0n:
586	      c
587	    case 1n+p:
588	      digits.go(p, (v / 10 : U32), Bool.pick(U32, U32.is_le(10, v), (c + 1 : U32), c))
589	
590	# The count of decimal digits in v.
591	def digits(+v: U32) -> U32:
592	  digits.go(9n, v, 1)
593	
594	# mode, uid 0, gid 0, size, mtime 0, the checksum as spaces, type, and the POSIX ustar magic.
595	def hdr.fields(+mode: U32, +size: U32, +t: U32, a: Array<U32>) -> Array<U32>:
596	  f = oct.put(11n, oct.put(7n, oct.put(7n, oct.put(7n, a, 106, mode), 114, 0), 122, 0), 134, size)
597	  put.str("ustar\u{0}00", Bytes.poke(put.str("        ", oct.put(11n, f, 146, 0), 148), 156, t), 257)
598	
599	# Six octal digits, NUL, space: the last space stays from the fields.
600	def hdr.ck(r: Array<U32> & U32) -> Array<U32>:
601	  (a, +s) = r
602	  oct.put(6n, Bytes.poke(a, 154, 0), 153, s)
603	
604	def hdr.of(+mode: U32, +size: U32, +t: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Bytes.Bytes:
605	  (src, h) = r
606	  (src, Bytes.Bytes{512, hdr.ck(bsum(hdr.fields(mode, size, t, h), 0))})
607	
608	# A header block named by the first n bytes of src, handing src back.
609	def hdr(src: Array<U32>, +n: U32, +mode: U32, +size: U32, +t: U32) -> Array<U32> & Bytes.Bytes:
610	  hdr.of(mode, size, t, Bytes.copy(n, src, Bytes.alloc(512), 0, 0))
611	
612	# b with zero bytes up to the next whole block. Bytes past len are already 0, so only len and room grow.
613	def blk(b: Bytes.Bytes) -> Bytes.Bytes:
614	  Bytes.Bytes{+len, buf} = b
615	  +n = pad(len)
616	  Bytes.Bytes{n, Bytes.grow(len, buf, n)}
617	
618	def zeros(b: Bytes.Bytes, +n: U32) -> Bytes.Bytes:
619	  Bytes.Bytes{+len, buf} = b
620	  Bytes.Bytes{(len + n : U32), Bytes.grow(len, buf, (len + n : U32))}
621	
622	def rec.fin(+l: U32, r: Array<U32> & Array<U32>) -> Array<U32> & Bytes.Bytes:
623	  (nb, o) = r
624	  (nb, Bytes.Bytes{l, o})
625	
626	# A PAX path record's length: nl + 7 plus its own digits, found as in POSIX pax.
627	def rec.len(+nl: U32) -> U32:
628	  +base = (nl + 7 : U32)
629	  (base + digits((base + digits(base) : U32)) : U32)
630	
631	# "<len> path=<name>\n".
632	def pr.record(nb: Array<U32>, +nl: U32) -> Array<U32> & Bytes.Bytes:
633	  +l = rec.len(nl)
634	  +d = digits(l)
635	  o = Bytes.poke(put.str(" path=", dec.put(U32.to_nat(d), Bytes.alloc(l), (d - 1 : U32), l), d), (l - 1 : U32), 10)
636	  rec.fin(l, Bytes.copy(nl, nb, o, 0, (d + 6 : U32)))
637	
638	def hdr.snd(r: Array<U32> & Bytes.Bytes) -> Bytes.Bytes:
639	  (a, h) = r
640	  h
641	
642	def xhdr.of(+rl: U32, b: Bytes.Bytes) -> Bytes.Bytes:
643	  Bytes.Bytes{+n, buf} = b
644	  hdr.snd(hdr(buf, n, 420, rl, 120))
645	
646	def enc.paxout(out: Bytes.Bytes, rec: Bytes.Bytes) -> Bytes.Bytes:
647	  Bytes.Bytes{+rl, rb} = rec
648	  blk(Bytes.append(Bytes.append(out, xhdr.of(rl, Bytes.from_string("././@PaxHeader"))), Bytes.Bytes{rl, rb}))
649	
650	def enc.pax(out: Bytes.Bytes, r: Array<U32> & Bytes.Bytes) -> Array<U32> & Bytes.Bytes:
651	  (nb, rec) = r
652	  (nb, enc.paxout(out, rec))
653	
654	def enc.hdr(+dl: U32, db: Array<U32>, out: Bytes.Bytes, r: Array<U32> & Bytes.Bytes) -> Bytes.Bytes:
655	  (nb, h) = r
656	  blk(Bytes.append(Bytes.append(out, h), Bytes.Bytes{dl, db}))
657	
658	# The header keeps the name's first 100 bytes; a longer name rides in the PAX record before it.
659	def enc.main(+nl: U32, +t: U32, +mode: U32, +dl: U32, db: Array<U32>, r: Array<U32> & Bytes.Bytes) -> Bytes.Bytes:
660	  (nb, out) = r
661	  enc.hdr(dl, db, out, hdr(nb, U32.min(nl, 100), mode, dl, t))
662	
663	def enc.long(long: Bool, nb: Array<U32>, +nl: U32, out: Bytes.Bytes, +t: U32, +mode: U32, +dl: U32, db: Array<U32>) -> Bytes.Bytes:
664	  match long:
665	    case True{}:
666	      enc.main(nl, t, mode, dl, db, enc.pax(out, pr.record(nb, nl)))
667	    case False{}:
668	      enc.main(nl, t, mode, dl, db, (nb, out))
669	
670	def enc.ok(ok: Bool, nb: Array<U32>, +nl: U32, out: Bytes.Bytes, +t: U32, +mode: U32, +dl: U32, db: Array<U32>) -> Maybe<&1, Bytes.Bytes>:
671	  match ok:
672	    case True{}:
673	      Some{enc.long(U32.is_lt(100, nl), nb, nl, out, t, mode, dl, db)}
674	    case False{}:
675	      None{}
676	
677	# Does an entry fit what is left of the U32 length, with room for the end blocks? Every step checks before it subtracts.
678	def enc.room(+ol: U32, +dl: U32, +nl: U32, +long: Bool) -> Bool:
679	  +r0 = (4294967295 - ol : U32)
680	  +pd = pad(dl)
681	  +l = rec.len(nl)
682	  +pl = pad(l)
683	  +okd = U32.is_le(1536, r0) && (U32.is_le(dl, pd) && U32.is_le(pd, (r0 - 1536 : U32)))
684	  +r1 = (r0 - 1536 - pd : U32)
685	  +okl = Bool.not(long) || (U32.is_le(nl, 4294967040) && (U32.is_le(l, pl) && (U32.is_le(512, r1) && U32.is_le(pl, (r1 - 512 : U32)))))
686	  okd && okl
687	
688	# A name must be non-empty and hold no NUL, which the header's name field could not keep.
689	def enc.check(+t: U32, +mode: U32, +dl: U32, db: Array<U32>, out: Bytes.Bytes, r: Bytes.Bytes & Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
690	  Bytes.Bytes{+ol, ob} = out
691	  (name, +m) = r
692	  Bytes.Bytes{+nl, nb} = name
693	  +fits = enc.room(ol, dl, nl, U32.is_lt(100, nl))
694	  enc.ok(U32.is_ne(nl, 0) && (Maybe.is_none(&2, U32, m) && fits), nb, nl, Bytes.Bytes{ol, ob}, t, mode, dl, db)
695	
696	def enc(e: Entry, out: Bytes.Bytes) -> Maybe<&1, Bytes.Bytes>:
697	  match e:
698	    case File{name, data}:
699	      Bytes.Bytes{+dl, db} = data
700	      enc.check(48, 420, dl, db, out, Bytes.find(name, "\u{0}"))
701	    case Dir{name}:
702	      enc.check(53, 493, 0, Bytes.alloc(0), out, Bytes.find(name, "\u{0}"))
703	
704	def enc.end(m: Maybe<&1, Bytes.Bytes>) -> Maybe<&1, Bytes.Bytes>:
705	  match m:
706	    case Some{out}:
707	      Some{zeros(out, 1024)}
708	    case None{}:
709	      None{}
710	
711	def enc.go(xs: List<&1, Entry>, m: Maybe<&1, Bytes.Bytes>) -> Maybe<&1, Bytes.Bytes>:
712	  match xs:
713	    case Nil{}:
714	      enc.end(m)
715	    case Con{e, t}:
716	      match m:
717	        case Some{out}:
718	          enc.go(t, enc(e, out))
719	        case None{}:
720	          None{}
721	
722	# A POSIX ustar archive of the entries in order, ended by two zero blocks. Files are mode 0644 and
723	# directories 0755, with uid, gid, and mtime 0. A name over 100 bytes goes in a PAX path record.
724	# None when a name is empty or holds a NUL byte, or when the archive would pass 4 GiB (U32 lengths).
725	# ustar's 8 GiB size field holds any U32 length, so encode never needs a PAX size.
726	def encode(entries: List<&1, Entry>) -> Maybe<&1, Bytes.Bytes>:
727	  enc.go(entries, Some{Bytes.new(0)})