src/sha/nar.bend
ezx@1.6.0.0 · 456 lines · 0 definitions
1# sha/nar: the SRI `nix hash path --sri` would give for a directory, computed
2# without nix. A NAR is the tree as length-prefixed strings; its sha256, in
3# SRI form, is what fetchgit records as narHash.
4#
5# The tree is read in one listing, then every regular file's text, and the
6# NAR is built from what was read by a pure, fuelled state machine: each step
7# places one path or closes one directory, the way lock/resolve and pkg/walk
8# carry on, since two Bend defs may not call each other. What the NAR holds
9# of a path is what nix's dumper takes: the owner's exec bit of the mode,
10# every name and link target as it is, and a file's bytes. The reading is
11# sha/dump's, since it runs `find` through foreign code a law may not import.
12import Base
13import ezx@1.6.0.0/src/pkg/pkg.bend as K
14import ezx@1.6.0.0/src/share/sha.bend as Sha
15
16# A directory child is a `K.Item`: its name in `at` and the NAR serial of its
17# node in `sum`. That is a package file's shape, a name and the text that
18# stands for it, so the walk sorts children with the same `K.file.sort` a
19# package sorts its files with, and what is proved of that sort is proved of
20# the NAR.
21
22# one byte as a character. NAR is a byte stream held in a Bend string.
23def byte(+code: U32) -> Char:
24 Chr{(code .&. 255 : U32)}
25
26def nat.byte(+value: Nat) -> Char:
27 byte(U32.from_nat(Nat.mod(value, 256n)))
28
29def le64.go(width: Nat, +value: Nat) -> String:
30 match width:
31 case 0n:
32 ""
33 case 1n+f:
34 SCon{nat.byte(value), le64.go(f, Nat.div(value, 256n))}
35
36# a length as NAR writes it: eight bytes, little-endian
37def le64(+value: Nat) -> String:
38 le64.go(8n, value)
39
40# that many NUL bytes, the padding after a string
41def zeros(count: Nat) -> String:
42 match count:
43 case 0n:
44 ""
45 case 1n+p:
46 SCon{Chr{0}, zeros(p)}
47
48def pad.of(+len: Nat) -> Nat:
49 Nat.mod(Nat.sub(8n, Nat.mod(len, 8n)), 8n)
50
51# one NAR string: its length, its bytes, then zeros up to a multiple of eight
52def str(+text: String) -> String:
53 +n = String.length(text)
54 le64(n) ++ text ++ zeros(pad.of(n))
55
56def exec.fields(ex: Bool) -> String:
57 match ex:
58 case False{}:
59 ""
60 case True{}:
61 str("executable") ++ str("")
62
63# a regular file's node, marked executable when it is
64def regular(ex: Bool, +contents: String) -> String:
65 str("(") ++ str("type") ++ str("regular") ++ exec.fields(ex)
66 ++ str("contents") ++ str(Sha.utf8(contents)) ++ str(")")
67
68# a symlink's node
69def symlink(+target: String) -> String:
70 str("(") ++ str("type") ++ str("symlink") ++ str("target")
71 ++ str(Sha.utf8(target)) ++ str(")")
72
73# one directory entry: its name and its node
74def entry(+ent: K.Item) -> String:
75 K.Item{name, node} = ent
76 str("entry") ++ str("(") ++ str("name") ++ str(Sha.utf8(name))
77 ++ str("node") ++ node ++ str(")")
78
79# a directory's entries, in the order given
80def entries(es: List<&2, K.Item>) -> String:
81 match es:
82 case []:
83 ""
84 case h <> t:
85 entry(h) ++ entries(t)
86
87# a directory's node, its entries in the order given
88def directory(es: List<&2, K.Item>) -> String:
89 str("(") ++ str("type") ++ str("directory") ++ entries(es) ++ str(")")
90
91# a directory's node as NAR writes it: its entries sorted by name, whatever
92# order they were listed in. `String.is_le` is codepoint order, which is nix's
93# byte order for the UTF-8 of valid names. Every directory the walk serializes
94# goes through here, so the order `find` printed its names in never reaches
95# the NAR.
96def dir(es: List<&2, K.Item>) -> String:
97 directory(K.file.sort(es))
98
99# a whole NAR: the magic, then the root node
100def archive(+node: String) -> String:
101 str("nix-archive-1") ++ node
102
103def b64.digit.plus(plus: Bool) -> Char:
104 match plus:
105 case True{}:
106 '+'
107 case False{}:
108 '/'
109
110def b64.digit.lt62(small: Bool, +index: U32) -> Char:
111 match small:
112 case True{}:
113 Chr{U32.add(48, U32.sub(index, 52))}
114 case False{}:
115 b64.digit.plus(U32.is_eq(index, 62))
116
117def b64.digit.lt52(small: Bool, +index: U32) -> Char:
118 match small:
119 case True{}:
120 Chr{U32.add(97, U32.sub(index, 26))}
121 case False{}:
122 b64.digit.lt62(U32.is_lt(index, 62), index)
123
124def b64.digit.lt26(small: Bool, +index: U32) -> Char:
125 match small:
126 case True{}:
127 Chr{U32.add(65, index)}
128 case False{}:
129 b64.digit.lt52(U32.is_lt(index, 52), index)
130
131def b64.digit(+index: U32) -> Char:
132 b64.digit.lt26(U32.is_lt(index, 26), index)
133
134def b64.triple(+first: U32, +second: U32, +third: U32) -> String:
135 +n = (U32.shln(first, 16n) .|. U32.shln(second, 8n) .|. third : U32)
136 SCon{b64.digit(U32.shrn(n, 18n)),
137 SCon{b64.digit((U32.shrn(n, 12n) .&. 63 : U32)),
138 SCon{b64.digit((U32.shrn(n, 6n) .&. 63 : U32)),
139 SCon{b64.digit((n .&. 63 : U32)), SNil{}}}}}
140
141def b64.one(+first: U32) -> String:
142 SCon{b64.digit(U32.shrn(first, 2n)),
143 SCon{b64.digit(U32.shln((first .&. 3 : U32), 4n)),
144 SCon{'=', SCon{'=', SNil{}}}}}
145
146def b64.two(+first: U32, +second: U32) -> String:
147 +n = (U32.shln(first, 8n) .|. second : U32)
148 SCon{b64.digit(U32.shrn(n, 10n)),
149 SCon{b64.digit((U32.shrn(n, 4n) .&. 63 : U32)),
150 SCon{b64.digit(U32.shln((n .&. 15 : U32), 2n)),
151 SCon{'=', SNil{}}}}}
152
153# standard base64, padded with `=`
154def b64(text: String) -> String:
155 match text:
156 case SNil{}:
157 ""
158 case SCon{a, SNil{}}:
159 b64.one(Char.to_u32(a))
160 case SCon{a, SCon{b, SNil{}}}:
161 b64.two(Char.to_u32(a), Char.to_u32(b))
162 case SCon{a, SCon{b, SCon{c, t}}}:
163 b64.triple(Char.to_u32(a), Char.to_u32(b), Char.to_u32(c)) ++ b64(t)
164
165def hex.val.upper(is_upper: Bool, +code: U32) -> U32:
166 match is_upper:
167 case True{}:
168 U32.sub(code, 55)
169 case False{}:
170 0
171
172def hex.val.lower(is_lower: Bool, +code: U32) -> U32:
173 match is_lower:
174 case True{}:
175 U32.sub(code, 87)
176 case False{}:
177 hex.val.upper(Bool.and(U32.is_ge(code, 65), U32.is_le(code, 70)), code)
178
179def hex.val.digit(is_digit: Bool, +code: U32) -> U32:
180 match is_digit:
181 case True{}:
182 U32.sub(code, 48)
183 case False{}:
184 hex.val.lower(Bool.and(U32.is_ge(code, 97), U32.is_le(code, 102)), code)
185
186def hex.val(+ch: Char) -> U32:
187 +u = Char.to_u32(ch)
188 hex.val.digit(Bool.and(U32.is_ge(u, 48), U32.is_le(u, 57)), u)
189
190def hex.bytes(text: String) -> String:
191 match text:
192 case SNil{}:
193 ""
194 case SCon{_a, SNil{}}:
195 ""
196 case SCon{a, SCon{b, t}}:
197 SCon{byte((U32.shln(hex.val(a), 4n) + hex.val(b) : U32)), hex.bytes(t)}
198
199def sri.hex(+hex: String) -> String:
200 "sha256-" ++ b64(hex.bytes(hex))
201
202# the SRI of some bytes: `sha256-` and the base64 of their digest
203def sri(+bytes: String) -> String:
204 sri.hex(Sha.raw(bytes))
205
206# the node of an empty directory
207def empty() -> String:
208 dir([])
209
210
211# ---------------------------------------------------------------------------
212# the listing
213#
214# The tree is listed once, by one `find` from its top, and every field of
215# every path is ended by a NUL, the one byte no name or target can hold. So a
216# name is read as it is, a space at either end and a newline inside it
217# included, and no field is ever trimmed. The paths inside the tree are never
218# handed to a program as arguments, since the process effect separates
219# arguments by newlines; only the top is, and a file's text is read by its
220# path through the file effect, which takes any name.
221
222# the NUL that ends every field of the listing
223def nul() -> Char:
224 Chr{0}
225
226# a char put in front of the first field, which a text that does not end with
227# a NUL leaves open
228def push(+ch: Char, fs: List<&2, String>) -> List<&2, String>:
229 match fs:
230 case []:
231 [SCon{ch, SNil{}}]
232 case h <> t:
233 SCon{ch, h} <> t
234
235# one char of the listing read: a NUL ends a field, any other char is the
236# next of the field it is in
237def cut.at(ends: Bool, +ch: Char, fs: List<&2, String>) -> List<&2, String>:
238 match ends:
239 case True{}:
240 "" <> fs
241 case False{}:
242 push(ch, fs)
243
244# the fields of a listing, each ended by a NUL, exactly as they were printed
245def cut(text: String) -> List<&2, String>:
246 match text:
247 case SNil{}:
248 []
249 case SCon{+c, t}:
250 cut.at(Char.is_eq(c, nul()), c, cut(t))
251
252# whether a text holds no NUL, as no name and no link target can
253def clean(text: String) -> Bool:
254 match text:
255 case SNil{}:
256 True{}
257 case SCon{c, t}:
258 +rest = clean(t)
259 Bool.and(Bool.not(Char.is_eq(c, nul())), rest)
260
261# fields as the listing prints them, each ended by a NUL
262def joined(fs: List<&2, String>) -> String:
263 match fs:
264 case []:
265 ""
266 case h <> t:
267 String.append(h, SCon{nul(), joined(t)})
268
269# whether every field holds no NUL
270def clean.all(fs: List<&2, String>) -> Bool:
271 match fs:
272 case []:
273 True{}
274 case h <> t:
275 +rest = clean.all(t)
276 Bool.and(clean(h), rest)
277
278# whether a file's owner may execute it, from the mode `find` prints as
279# `%M`, `-rwxr-xr-x`: the fourth character is `x`, or `s` when the setuid
280# bit is set as well. This is the mode bit nix's NAR dumper reads
281# (`S_IXUSR`), not an access check, so a file the owner may not execute is
282# not executable whoever weighs it.
283def owner.exec(mode: String) -> Bool:
284 match mode:
285 case SCon{_t, SCon{_r, SCon{_w, SCon{+x, _rest}}}}:
286 Bool.or(Char.is_eq(x, 'x'), Char.is_eq(x, 's'))
287 case _:
288 False{}
289
290# one path of the listing: its type as `%y` gives it (`d`, `f`, `l`), its
291# mode (`%M`), its name (`%f`), its path from the top (`%P`) and a symlink's
292# target (`%l`)
293type Row is Data:
294 Row{kind: String, mode: String, name: String, at: String, target: String}
295
296# the listing's fields, five to a path. A path the listing cut short is not
297# read.
298def rows(fs: List<&2, String>) -> List<&2, Row>:
299 match fs:
300 case Con{y, Con{m, Con{f, Con{p, Con{l, rest}}}}}:
301 Row{y, m, f, p, l} <> rows(rest)
302 case _:
303 []
304
305# what `find` is asked to print of every path under `top`, the top first,
306# each field ended by a NUL. `find` lists a directory before what is in it
307# and all of it before the next entry, which is the order `build` reads.
308def listing.argv(+top: String) -> List<&2, String>:
309 ["find", top, "-printf", "%y\\0%M\\0%f\\0%P\\0%l\\0"]
310
311# ---------------------------------------------------------------------------
312# the tree
313
314# one path of the tree with what the NAR holds of it: a file's text, or a
315# symlink's target, as `body`
316type Ent is Data:
317 Ent{kind: String, exec: Bool, name: String, at: String, body: String}
318
319# a directory still open: its path from the top, its name, and the entries
320# found in it so far
321type Frame is Data:
322 Frame{at: String, name: String, kids: List<&2, K.Item>}
323
324# where the build stands: the paths still to place, the directory they are
325# being placed in, and the directories around it
326type State is Data:
327 State{es: List<&2, Ent>, top: Frame, up: List<&2, Frame>}
328
329# a step of the build: another state, or the finished node of the top
330type Move is Data:
331 Next{st: State}
332 Built{node: String}
333
334def leaf.of(link: Bool, ex: Bool, +body: String) -> String:
335 match link:
336 case True{}:
337 symlink(body)
338 case False{}:
339 regular(ex, body)
340
341# a file's or a symlink's node
342def leaf(entry: Ent) -> String:
343 Ent{+kind, ex, _name, _at, body} = entry
344 leaf.of(String.eq(kind, "l"), ex, body)
345
346# the path of an entry named `name` inside the directory at `at`
347def under(+at: String, +name: String) -> String:
348 Bool.pick(String, String.is_empty(at), name, at ++ "/" ++ name)
349
350# the directory on top finished: its node is an entry of the one around it,
351# or the whole tree when there is none
352def close(top: Frame, up: List<&2, Frame>, es: List<&2, Ent>) -> Move:
353 Frame{_at, +name, kids} = top
354 match up:
355 case []:
356 Built{dir(kids)}
357 case Frame{pat, pname, pkids} <> rest:
358 Next{State{es, Frame{pat, pname, K.Item{name, dir(kids)} <> pkids}, rest}}
359
360# an entry's type, name and path, and an open directory's path
361def ent.kind(entry: Ent) -> String:
362 Ent{kind, _ex, _name, _at, _body} = entry
363 kind
364
365# an entry's name
366def ent.name(entry: Ent) -> String:
367 Ent{_kind, _ex, name, _at, _body} = entry
368 name
369
370# an entry's path from the top
371def ent.at(entry: Ent) -> String:
372 Ent{_kind, _ex, _name, at, _body} = entry
373 at
374
375# an open directory's path from the top
376def frame.at(frame: Frame) -> String:
377 Frame{at, _name, _kids} = frame
378 at
379
380# a path inside the directory on top: a directory is opened, anything else
381# is an entry of it, with its leaf's node
382def place(
383 is_dir: Bool,
384 +name: String,
385 +at: String,
386 +node: String,
387 more: List<&2, Ent>,
388 top: Frame,
389 up: List<&2, Frame>
390) -> Move:
391 match is_dir:
392 case True{}:
393 Next{State{more, Frame{at, name, []}, top <> up}}
394 case False{}:
395 Frame{a, n, ks} = top
396 Next{State{more, Frame{a, n, K.Item{name, node} <> ks}, up}}
397
398# the next path: placed when it is inside the directory on top, which closes
399# otherwise
400def step.ent(
401 inside: Bool,
402 +entry: Ent,
403 more: List<&2, Ent>,
404 top: Frame,
405 up: List<&2, Frame>
406) -> Move:
407 match inside:
408 case True{}:
409 place(String.eq(ent.kind(entry), "d"), ent.name(entry), ent.at(entry), leaf(entry), more, top, up)
410 case False{}:
411 close(top, up, entry <> more)
412
413# one step of the build
414def step(st: State) -> Move:
415 State{es, +top, up} = st
416 match es:
417 case []:
418 close(top, up, [])
419 case +e <> t:
420 step.ent(String.eq(ent.at(e), under(frame.at(top), ent.name(e))), e, t, top, up)
421
422# the build, under fuel
423def build.go(fuel: Nat, mv: Move) -> Maybe<&2, String>:
424 match fuel:
425 case 0n:
426 None{}
427 case 1n+f:
428 match mv:
429 case Next{st}:
430 build.go(f, step(st))
431 case Built{node}:
432 Some{node}
433
434# the node of a directory, from its paths in the order `find` lists them. Each
435# step places a path or closes a directory, and each directory is closed
436# once, so twice the paths and two more is fuel enough.
437def build(+es: List<&2, Ent>) -> Maybe<&2, String>:
438 +n = List.length(&2, Ent, es)
439 build.go(Nat.add(Nat.add(n, n), 2n), Next{State{es, Frame{"", "", []}, []}})
440
441# the node of the whole tree, from its listing with the top first: a
442# directory is built, a file or a symlink is a leaf
443def tree.top(is_dir: Bool, top: Ent, more: List<&2, Ent>) -> Maybe<&2, String>:
444 match is_dir:
445 case True{}:
446 build(more)
447 case False{}:
448 Some{leaf(top)}
449
450# the node of the whole tree, or none for an empty listing
451def tree(es: List<&2, Ent>) -> Maybe<&2, String>:
452 match es:
453 case []:
454 None{}
455 case Ent{+kind, ex, name, at, body} <> t:
456 tree.top(String.eq(kind, "d"), Ent{kind, ex, name, at, body}, t)