1	# pkg/pkg: the package a `bend <entry> --publish` would upload, computed
2	# without publishing: the file set, their sha256s, and the `0x<hash>` that names
3	# them. This mirrors `pkg_files` and the hash in bend's `cli_publish`.
4	# `tests/publish.sh` pins it against the real thing by running `bend --publish`
5	# at a local hub, so drift fails the gate rather than the ecosystem.
6	#
7	# The walk is pure: `of` computes the package from a checkout's files alone,
8	# which is what `ez add` in planner form will run, and `pkg_of` and `pkg_in`
9	# run the same walk given nothing, answering each file it asks for from disk.
10	# Bend refuses an import cycle, and this module both defines the file list the
11	# walk hashes and runs it, so the walk lives here rather than in a module of
12	# its own.
13	import Base
14	import ../io/file.bend as F
15	import ../share/sha.bend as Sha
16	import ./path.bend as P
17	
18	# a file of a package: the path it takes inside the package, and its sha256
19	type Item is Data:
20	  Item{at: String, sum: String}
21	
22	# a package: the files it holds, the hash that names them, and the directory
23	# their paths are written from. The root is the entry's own directory until a
24	# module reached through `..` re-roots the package above it, so a caller
25	# copying the files out joins them against this and never against the entry's
26	# directory.
27	type Pkg is Data:
28	  Pkg{hash: String, root: String, files: List<&2, Item>}
29	
30	# what a source file's header imports: modules by the path they were reached
31	# through, and the foreign C and JS bodies bend uploads alongside the sources
32	type Scan is Data:
33	  Scan{mods: List<&2, String>, foreign: List<&2, String>}
34	
35	# what one line of a source file turned out to be
36	type Stmt is Data:
37	  SNone{}
38	  SMod{spec: String}
39	  SForeign{at: String}
40	  SBody{}
41	
42	# a scan in progress: `head` is true while the imports still head the file
43	type Head is Data:
44	  Head{head: Bool, mods: List<&2, String>, foreign: List<&2, String>}
45	
46	# the words of a line, with the runs of spaces dropped
47	def words.keep(ws: List<&2, String>) -> List<&2, String>:
48	  match ws:
49	    case []:
50	      []
51	    case Con{+h, t}:
52	      +more = words.keep(t)
53	      Bool.pick(List<&2, String>, String.is_empty(h), more, h <> more)
54	
55	# the words of a line
56	def words(line: String) -> List<&2, String>:
57	  words.keep(String.split(line, ' '))
58	
59	# a character bend's loader reads as white space in an import line. The
60	# loader trims each line of a file's header and splits an import on `\s+`,
61	# JavaScript's white space: tab, line feed, vertical tab, form feed, carriage
62	# return and space, the no-break space, and the Unicode space separators, the
63	# line and paragraph separators and the byte order mark. A zero-width space
64	# or a next-line character is not one, and bend refuses an import it holds.
65	def blank(+ch: Char) -> Bool:
66	  match ch:
67	    case Chr{+x}:
68	      Bool.or(Bool.or(U32.is_eq(x, 32), Bool.and(U32.is_ge(x, 9), U32.is_le(x, 13))),
69	        Bool.or(Bool.or(U32.is_eq(x, 160), U32.is_eq(x, 5760)),
70	          Bool.or(Bool.and(U32.is_ge(x, 8192), U32.is_le(x, 8202)),
71	            Bool.or(Bool.or(U32.is_eq(x, 8232), U32.is_eq(x, 8233)),
72	              Bool.or(Bool.or(U32.is_eq(x, 8239), U32.is_eq(x, 8287)),
73	                Bool.or(U32.is_eq(x, 12288), U32.is_eq(x, 65279)))))))
74	
75	# the front of a line, past one character that may be blank
76	def trim.front.at(skip: Bool, head: Char, tail: String, rest: Unit -> String) -> String:
77	  match skip:
78	    case True{}:
79	      rest(Unit{})
80	    case False{}:
81	      SCon{head, tail}
82	
83	# a line with its leading blanks dropped
84	def trim.front(line: String) -> String:
85	  match line:
86	    case SNil{}:
87	      SNil{}
88	    case SCon{+h, +t}:
89	      trim.front.at(blank(h), h, t, _u => trim.front(t))
90	
91	# a character kept before the rest of a line with its trailing blanks
92	# dropped. The character goes too when it is blank and nothing follows it.
93	def trim.back.at(gone: Bool, head: Char, rest: String) -> String:
94	  match gone:
95	    case True{}:
96	      SNil{}
97	    case False{}:
98	      SCon{head, rest}
99	
100	# a line with its trailing blanks dropped, read from the front, so that the
101	# trim of a line is a walk over it rather than over its reverse
102	def trim.back(line: String) -> String:
103	  match line:
104	    case SNil{}:
105	      SNil{}
106	    case SCon{+h, t}:
107	      +rest = trim.back(t)
108	      trim.back.at(Bool.and(blank(h), String.is_empty(rest)), h, rest)
109	
110	# a line with the blanks at either end dropped, as bend's loader trims it
111	def trim(line: String) -> String:
112	  trim.back(trim.front(line))
113	
114	# the fields of a line read so far: the field under way, and the fields after
115	# it
116	type Cut is Data:
117	  Cut{field: String, after: List<&2, String>}
118	
119	# a field put before the fields after it, unless it is empty
120	def cut.put(field: String, after: List<&2, String>) -> List<&2, String>:
121	  match field:
122	    case SNil{}:
123	      after
124	    case SCon{h, t}:
125	      SCon{h, t} <> after
126	
127	# one character before the fields read so far: a blank ends the field under
128	# way, and anything else extends it
129	def cut.at(gap: Bool, head: Char, sofar: Cut) -> Cut:
130	  match gap:
131	    case True{}:
132	      Cut{field, after} = sofar
133	      Cut{"", cut.put(field, after)}
134	    case False{}:
135	      Cut{field, after} = sofar
136	      Cut{SCon{head, field}, after}
137	
138	# a line cut at its blanks, read from the back
139	def cut(line: String) -> Cut:
140	  match line:
141	    case SNil{}:
142	      Cut{"", []}
143	    case SCon{+h, t}:
144	      cut.at(blank(h), h, cut(t))
145	
146	# a line's fields once it is cut: the one under way before the rest
147	def cut.all(sofar: Cut) -> List<&2, String>:
148	  Cut{field, after} = sofar
149	  cut.put(field, after)
150	
151	# the fields of an import line: what is left between its runs of blanks, as
152	# bend's loader splits it. `words` splits on spaces alone, which is how a
153	# manifest line is split.
154	def fields(line: String) -> List<&2, String>:
155	  cut.all(cut(line))
156	
157	# the nth word, or "" when the line is shorter than that. Both the list and the
158	# count are scrutinised together, so the walk needs no helper to branch through.
159	def word(ws: List<&2, String>, index: Nat) -> String:
160	  match ws index:
161	    case Nil{} _m:
162	      ""
163	    case Con{h, _t} 0n:
164	      h
165	    case Con{_h, t} 1n+p:
166	      word(t, p)
167	
168	# the line named a module, or it did not, with the answer already in hand.
169	# `Bool.pick` is an ordinary function and builds both of its arms before it
170	# picks one, so under it `word(ws, 1n)` walked the words of every line of
171	# every source file ez scans. An arm of a `match` is not built until it is
172	# taken.
173	def mod_of.step(named: Bool, ws: List<&2, String>) -> Stmt:
174	  match named:
175	    case True{}:
176	      SMod{word(ws, 1n)}
177	    case False{}:
178	      SBody{}
179	
180	# an `import <spec> as <Name>` line names a module; anything else does not
181	def mod_of(+ws: List<&2, String>) -> Stmt:
182	  mod_of.step(
183	    Bool.and(Nat.is_ge(List.length(&2, String, ws), 4n),
184	      Bool.and(String.eq(word(ws, 0n), "import"), String.eq(word(ws, 2n), "as"))),
185	    ws)
186	
187	# the prelude decided. The prelude arm does no work at all, and the other arm
188	# is the only place `mod_of` has anything to say, so this is where the rest of
189	# the classification hangs rather than in an argument that always runs.
190	def base_of.step(prelude: Bool, ws: List<&2, String>) -> Stmt:
191	  match prelude:
192	    case True{}:
193	      SNone{}
194	    case False{}:
195	      mod_of(ws)
196	
197	# `import Base` brings in the prelude, which is no part of any package. bend
198	# lets a comment follow it, and a comment names no module.
199	def base_of(+ws: List<&2, String>) -> Stmt:
200	  base_of.step(
201	    Bool.and(Bool.or(Nat.is_eq(List.length(&2, String, ws), 2n),
202	        String.starts_with(word(ws, 2n), "#")),
203	      Bool.and(String.eq(word(ws, 0n), "import"), String.eq(word(ws, 1n), "Base"))),
204	    ws)
205	
206	# a line that neither opens nor ends the header
207	def quiet(+line: String) -> Bool:
208	  Bool.or(String.is_empty(line), String.starts_with(line, "#"))
209	
210	# a line that says nothing about the header, decided. `fields` is a walk
211	# over the line that cuts it at its blanks, and this is the arm it hangs
212	# from: every blank line and every comment line of every `.bend` file of the
213	# project and of every package it resolves used to be split into words and
214	# classified, which is most of the lines ez ever reads.
215	def stmt_of.quiet(skip: Bool, +line: String) -> Stmt:
216	  match skip:
217	    case True{}:
218	      SNone{}
219	    case False{}:
220	      base_of(fields(line))
221	
222	# the rest of a line, past one character that may be skipped
223	def foreign.gap.at(skip: Bool, head: Char, tail: String, rest: Unit -> String) -> String:
224	  match skip:
225	    case True{}:
226	      rest(Unit{})
227	    case False{}:
228	      SCon{head, tail}
229	
230	# a line past its `import`, with the spaces, tabs and carriage returns bend's
231	# parser skips between the word and the path dropped
232	def foreign.gap(line: String) -> String:
233	  match line:
234	    case SNil{}:
235	      SNil{}
236	    case SCon{+h, +t}:
237	      foreign.gap.at(Bool.or(Char.is_eq(h, ' '), Bool.or(Char.is_eq(h, '\t'),
238	        Char.is_eq(h, '\r'))), h, t, _u => foreign.gap(t))
239	
240	# the quoted path of a foreign import, once its `import` and the gap after
241	# it are gone
242	def foreign.path(+rest: String) -> String:
243	  String.take(String.drop(rest, 1n), Nat.sub(String.length(rest), 2n))
244	
245	# whether what follows a line's `import` is a quoted path
246	def foreign.quoted(+rest: String) -> Bool:
247	  Bool.and(String.starts_with(rest, "\""), String.ends_with(rest, "\""))
248	
249	# the foreign import decided. The rest of the cascade hangs off the False arm
250	# rather than sitting in an argument, so a line that is a foreign import pays
251	# for nothing below it.
252	def stmt_of.foreign(here: Bool, +line: String) -> Stmt:
253	  match here:
254	    case True{}:
255	      SForeign{foreign.path(foreign.gap(String.drop(line, 6n)))}
256	    case False{}:
257	      stmt_of.quiet(quiet(line), line)
258	
259	# a trimmed line classified. A foreign import is tested first: it lives in a
260	# def's body, long after the header has ended. bend's parser reads the word
261	# `import`, skips spaces, tabs and carriage returns, and reads a quoted path.
262	def stmt_of(+line: String) -> Stmt:
263	  stmt_of.foreign(
264	    Bool.and(String.starts_with(line, "import"),
265	      foreign.quoted(foreign.gap(String.drop(line, 6n)))), line)
266	
267	# a module named after the header has ended is not part of the header, so the
268	# line is ignored rather than followed
269	def scan.mod(+head: Bool, spec: String, mods: List<&2, String>, foreign: List<&2, String>) -> Head:
270	  match head:
271	    case True{}:
272	      Head{True{}, spec <> mods, foreign}
273	    case False{}:
274	      Head{False{}, mods, foreign}
275	
276	# the state once a line has been classified
277	def scan.go(st: Head, stmt: Stmt) -> Head:
278	  Head{head, mods, foreign} = st
279	  match stmt:
280	    case SNone{}:
281	      Head{head, mods, foreign}
282	    case SForeign{at}:
283	      Head{head, mods, at <> foreign}
284	    case SMod{spec}:
285	      scan.mod(head, spec, mods, foreign)
286	    case SBody{}:
287	      Head{False{}, mods, foreign}
288	
289	# one line of a source file against the state
290	def scan.step(st: Head, raw: String) -> Head:
291	  scan.go(st, stmt_of(trim(raw)))
292	
293	# what a finished scan gathered, in source order
294	def scan.fin(st: Head) -> Scan:
295	  Head{_head, mods, foreign} = st
296	  Scan{List.reverse(&2, String, mods), List.reverse(&2, String, foreign)}
297	
298	# the header walked one line at a time. Base's `List.foldl` applies an erased
299	# function parameter, which Bend's termination check cannot see through, so
300	# every def reaching it is reported as relying on unsafe code; a walk written
301	# out is structural and costs nothing.
302	def scan.walk(ls: List<&2, String>, st: Head) -> Head:
303	  match ls:
304	    case []:
305	      st
306	    case h <> t:
307	      scan.walk(t, scan.step(st, h))
308	
309	# what a source file's header imports
310	def scan(text: String) -> Scan:
311	  scan.fin(scan.walk(String.lines(text), Head{True{}, [], []}))
312	
313	# the modules a scan found
314	def scan.mods(scanned: Scan) -> List<&2, String>:
315	  Scan{mods, _foreign} = scanned
316	  mods
317	
318	# the foreign bodies a scan found
319	def scan.foreign(scanned: Scan) -> List<&2, String>:
320	  Scan{_mods, foreign} = scanned
321	  foreign
322	
323	# an import of a hub package, which is a dependency rather than a module of
324	# this package. A `0x` name has no directory of its own, so the first `/` ends
325	# it.
326	def is_hub(+spec: String) -> Bool:
327	  Bool.and(String.starts_with(spec, "0x"), String.contains(spec, "/"))
328	
329	# ---------------------------------------------------------------------------
330	# named hub imports
331	
332	# Since 2.0.26 bend also reads `import <name>@<version>/<path> as P`. Its
333	# loader normalises the path, and when the first component holds an `@` it is
334	# a package's name and version, which bend looks up in `$BEND_LIB/names`, or
335	# asks the hub for once, and then loads by the hash it names. A name the hub
336	# rules out, bend refuses. `named.of` and `name.ok` are those two readings,
337	# the one ez's walk, lock, fetch and doctor share.
338	
339	# a character a hub name holds after its first: a-z, 0-9 and -
340	def name.char(+ch: Char) -> Bool:
341	  Bool.or(Char.is_lower(ch), Bool.or(Char.is_digit(ch), Char.is_eq(ch, '-')))
342	
343	# whether every character is one a hub name holds
344	def name.chars(text: String) -> Bool:
345	  match text:
346	    case SNil{}:
347	      True{}
348	    case SCon{+h, t}:
349	      +rest = name.chars(t)
350	      Bool.and(name.char(h), rest)
351	
352	# whether a name opens with a letter
353	def name.first(text: String) -> Bool:
354	  match text:
355	    case SNil{}:
356	      False{}
357	    case SCon{+h, _t}:
358	      Char.is_lower(h)
359	
360	# a hub name: a letter, then a-z, 0-9 and -, 1 to 64 characters in all, as
361	# bend's NAMED rule reads it. Which names a Bender may take is the hub's.
362	def name.part(+text: String) -> Bool:
363	  +n = String.length(text)
364	  Bool.and(Bool.and(Nat.is_ge(n, 1n), Nat.is_le(n, 64n)),
365	    Bool.and(name.first(text), name.chars(text)))
366	
367	# whether every character is a digit
368	def digits(text: String) -> Bool:
369	  match text:
370	    case SNil{}:
371	      True{}
372	    case SCon{+h, t}:
373	      +rest = digits(t)
374	      Bool.and(Char.is_digit(h), rest)
375	
376	# one number of a version: digits, and no leading zero unless it is `0`
377	def ver.num(+text: String) -> Bool:
378	  Bool.and(Bool.not(String.is_empty(text)),
379	    Bool.and(digits(text),
380	      Bool.or(String.eq(text, "0"), Bool.not(String.starts_with(text, "0")))))
381	
382	# whether every number of a version is one
383	def ver.nums(ps: List<&2, String>) -> Bool:
384	  match ps:
385	    case []:
386	      True{}
387	    case +h <> t:
388	      +rest = ver.nums(t)
389	      Bool.and(ver.num(h), rest)
390	
391	# a version: four numbers, like 1.0.0.0
392	def ver.ok(+text: String) -> Bool:
393	  +ps = String.split(text, '.')
394	  Bool.and(Nat.is_eq(List.length(&2, String, ps), 4n), ver.nums(ps))
395	
396	# whether a `<name>@<version>` is one the hub rules in, as bend's `NAMED`
397	# pattern reads it
398	def name.ok(+nv: String) -> Bool:
399	  +ps = String.split(nv, '@')
400	  Bool.and(Nat.is_eq(List.length(&2, String, ps), 2n),
401	    Bool.and(name.part(word(ps, 0n)), ver.ok(word(ps, 1n))))
402	
403	# the first component, when it is a name, and "" when it is not
404	def named.pick(named: Bool, +first: String) -> String:
405	  match named:
406	    case True{}:
407	      first
408	    case False{}:
409	      ""
410	
411	# the `<name>@<version>` an import names, or "" when it names none: the first
412	# component of its normalised path, when that holds an `@` and a `/` follows
413	# it, as bend's loader reads it
414	def named.of(+spec: String) -> String:
415	  +n = P.norm(spec)
416	  +first = word(String.split(n, '/'), 0n)
417	  named.pick(Bool.and(String.contains(n, "/"), String.contains(first, "@")), first)
418	
419	# an import of a named hub package, which is a dependency rather than a module
420	# of this package, whether or not the hub rules its name in (EZ-HUB-3)
421	def is_named(+spec: String) -> Bool:
422	  Bool.not(String.is_empty(named.of(spec)))
423	
424	# why a name the hub rules out stops a walk, a lock or a fetch, in bend's own
425	# words
426	def unnamed.why(+nv: String) -> String:
427	  "ez: " ++ nv ++ " is not a package as <name>@<version>: a-z, 0-9 and -, " ++
428	    "1 to 64 characters, at four numbers like 1.0.0.0"
429	
430	# the name when the hub rules it out, the rest's otherwise
431	def unnamed.pick(bad: Bool, +nv: String, rest: Unit -> String) -> String:
432	  match bad:
433	    case True{}:
434	      nv
435	    case False{}:
436	      rest(Unit{})
437	
438	# the first named import of a list whose name the hub rules out, or "" when
439	# there is none
440	def unnamed(ms: List<&2, String>) -> String:
441	  match ms:
442	    case []:
443	      ""
444	    case +h <> t:
445	      +nv = named.of(h)
446	      unnamed.pick(Bool.and(Bool.not(String.is_empty(nv)), Bool.not(name.ok(nv))), nv,
447	        _u => unnamed(t))
448	
449	# a file to visit: where it is on disk, and the module name bend gives it,
450	# which is the path it was reached through with the `.bend` dropped
451	type Task is Data:
452	  Task{file: String, ns: String}
453	
454	# a file of the package as it was found: where it sits inside the package, and
455	# its sha256
456	type Found is Data:
457	  Found{raw: String, sum: String}
458	
459	# a module import as the file to visit next, or nothing when it names a hub
460	# package, by its `0x` name or by its `<name>@<version>`
461	def task_of(+dir: String, +nd: String, +spec: String) -> List<&2, Task>:
462	  Bool.pick(List<&2, Task>, Bool.or(is_hub(spec), is_named(spec)), [],
463	    [Task{P.join(dir, spec), P.unbend(P.join(nd, spec))}])
464	
465	# every module a file imports, as the files to visit next
466	def tasks(+dir: String, +nd: String, ms: List<&2, String>) -> List<&2, Task>:
467	  match ms:
468	    case []:
469	      []
470	    case h <> t:
471	      List.append(&2, Task, task_of(dir, nd, h), tasks(dir, nd, t))
472	
473	# the directory a module's own imports are named from. The entry is the package
474	# root, so its modules are named from nowhere in particular.
475	def nsdir(+ns: String) -> String:
476	  Bool.pick(String, String.is_empty(ns), "", P.dir(ns))
477	
478	# the entry file is written under its own base name; every other module under
479	# the path it was reached through
480	def raw_of(+ns: String, eb: String) -> String:
481	  Bool.pick(String, String.is_empty(ns), eb, ns ++ ".bend")
482	
483	# one step of the scan, with the head's answer in hand. `Bool.or` is an
484	# ordinary function and so reduces both of its sides, which means a scan
485	# written with it never stops at the name it was looking for. The rest of the
486	# scan arrives as a thunk and only the arm that wants it applies it. This list
487	# grows by one with every file the walk reaches, so the scan is the inner half
488	# of a quadratic and stopping early halves it.
489	def seen.has.step(here: Bool, rest: Unit -> Bool) -> Bool:
490	  match here:
491	    case True{}:
492	      True{}
493	    case False{}:
494	      rest(Unit{})
495	
496	# whether a name is already among the ones the walk has reached. Base's
497	# `List.contains` applies an erased equality, which falls outside the
498	# termination check; this scan is structural.
499	def seen.has(xs: List<&2, String>, +want: String) -> Bool:
500	  match xs:
501	    case []:
502	      False{}
503	    case +h <> t:
504	      seen.has.step(String.eq(h, want), _u => seen.has(t, want))
505	
506	# a found file, placed under whatever the package re-rooted at
507	def file_of(+pre: String, hit: Found) -> Item:
508	  Found{raw, sum} = hit
509	  Item{P.join(pre, raw), sum}
510	
511	# every found file, placed
512	def placed(+pre: String, fs: List<&2, Found>) -> List<&2, Item>:
513	  match fs:
514	    case []:
515	      []
516	    case h <> t:
517	      file_of(pre, h) <> placed(pre, t)
518	
519	# where a file sits inside its package
520	def file.at(item: Item) -> String:
521	  Item{at, _sum} = item
522	  at
523	
524	# a package's files are written in path order, so the manifest of a package is
525	# the same text whoever computes it
526	def file.le(left: Item, right: Item) -> Bool:
527	  String.is_le(file.at(left), file.at(right))
528	
529	# the same path twice is the same file twice, and a package holds it once
530	def dedup.pick(same: Bool, head: Item, rest: List<&2, Item>) -> List<&2, Item>:
531	  match same:
532	    case True{}:
533	      rest
534	    case False{}:
535	      head <> rest
536	
537	# a file against the deduplicated files that follow it
538	def dedup.head(+head: Item, rest: List<&2, Item>) -> List<&2, Item>:
539	  match rest:
540	    case []:
541	      [head]
542	    case Con{+b, t}:
543	      dedup.pick(String.eq(file.at(head), file.at(b)), head, b <> t)
544	
545	# a sorted file list with the repeats dropped
546	def dedup(fs: List<&2, Item>) -> List<&2, Item>:
547	  match fs:
548	    case []:
549	      []
550	    case Con{h, t}:
551	      dedup.head(h, dedup(t))
552	
553	# where a file goes among the files already in order: before the one it is not
554	# after, otherwise behind it. The rest of the insertion is a parameter, because
555	# two defs that call each other are not allowed.
556	def file.ins.put(le: Bool, item: Item, head: Item, tail: List<&2, Item>, rest: List<&2, Item>) -> List<&2, Item>:
557	  match le:
558	    case True{}:
559	      item <> (head <> tail)
560	    case False{}:
561	      head <> rest
562	
563	# a file inserted into a list already in path order
564	def file.ins(fs: List<&2, Item>, +item: Item) -> List<&2, Item>:
565	  match fs:
566	    case []:
567	      [item]
568	    case Con{+h, +t}:
569	      file.ins.put(file.le(item, h), item, h, t, file.ins(t, item))
570	
571	# a file list in path order. Insertion rather than Base's `List.sort`: that one
572	# is a fuelled bottom-up merge sort, whose recursion Bend cannot check, so it
573	# is reported as unsafe and every proof downstream of it inherits the report.
574	# An insertion sort shrinks its list at every step, so Bend checks it, and a
575	# package's file set is small enough that the cost is not felt.
576	def file.sort(fs: List<&2, Item>) -> List<&2, Item>:
577	  match fs:
578	    case []:
579	      []
580	    case Con{+h, t}:
581	      file.ins(file.sort(t), h)
582	
583	# the files of a package, in path order and each one once
584	def files_of(fs: List<&2, Item>) -> List<&2, Item>:
585	  dedup(file.sort(fs))
586	
587	# a path that leaves the package behind, which no package may hold
588	def escapes(+at: String) -> Bool:
589	  Bool.or(String.starts_with(at, "/"), String.starts_with(at, ".."))
590	
591	# one step of the search, with the head's answer in hand. A search that puts
592	# its recursion in an arm of a `Bool.pick` is not a search: the arm is built
593	# whatever the answer, so the first escaping path still costs a walk of every
594	# file after it. The thunk is what makes the stop a stop.
595	def escaped.step(here: Bool, at: String, rest: Unit -> String) -> String:
596	  match here:
597	    case True{}:
598	      at
599	    case False{}:
600	      rest(Unit{})
601	
602	# the first file whose path leaves the package, or "" when none does
603	def escaped(fs: List<&2, Item>) -> String:
604	  match fs:
605	    case []:
606	      ""
607	    case +h <> t:
608	      +at = file.at(h)
609	      escaped.step(escapes(at), at, _u => escaped(t))
610	
611	# one `<sha256> <path>` line
612	def manifest.line(item: Item) -> String:
613	  Item{at, sum} = item
614	  sum ++ " " ++ at ++ "\n"
615	
616	# every line of a manifest
617	def manifest.lines(fs: List<&2, Item>) -> String:
618	  match fs:
619	    case []:
620	      ""
621	    case h <> t:
622	      manifest.line(h) ++ manifest.lines(t)
623	
624	# the manifest text is the package's identity, and bend checks a fetched
625	# manifest against the first 32 hex characters of its sha256
626	def manifest_of(fs: List<&2, Item>) -> String:
627	  manifest.lines(files_of(fs))
628	
629	# the `0x` name a file set is published under
630	def hash_of(fs: List<&2, Item>) -> String:
631	  "0x" ++ String.take(Sha.hex(manifest_of(fs)), 32n)
632	
633	# whether a file of a package is a LICENSE bend took along. A module ends in
634	# `.bend` and a foreign body in `.c` or `.js`, so a file named LICENSE is one
635	# the walk took along beside them.
636	def file.lic(item: Item) -> Bool:
637	  Item{at, _sum} = item
638	  String.eq(P.base(at), "LICENSE")
639	
640	def bare.pick(lic: Bool, head: Item, rest: List<&2, Item>) -> List<&2, Item>:
641	  match lic:
642	    case True{}:
643	      rest
644	    case False{}:
645	      head <> rest
646	
647	# a package's files as bend named them before 2.0.27: without the LICENSE
648	# files it now takes along, in the order they were given
649	def bare(fs: List<&2, Item>) -> List<&2, Item>:
650	  match fs:
651	    case []:
652	      []
653	    case +h <> t:
654	      bare.pick(file.lic(h), h, bare(t))
655	
656	def bare.srcs.pick(lic: Bool, text: String, rest: List<&2, String>) -> List<&2, String>:
657	  match lic:
658	    case True{}:
659	      rest
660	    case False{}:
661	      text <> rest
662	
663	# the texts that go with those files: the texts of a file list, one per file
664	# in the same order, with the LICENSE files' texts left out
665	def bare.srcs(fs: List<&2, Item>, ss: List<&2, String>) -> List<&2, String>:
666	  match fs ss:
667	    case Nil{} _:
668	      ss
669	    case Con{_h, _t} Nil{}:
670	      []
671	    case Con{+h, t} Con{s, u}:
672	      bare.srcs.pick(file.lic(h), s, bare.srcs(t, u))
673	
674	# ---------------------------------------------------------------------------
675	# the walk
676	
677	# one file of a checkout: its path from the checkout's top, and its text
678	type Source is Data:
679	  Source{at: String, text: String}
680	
681	# the files a walk is given. A whole tree is every file of a checkout, so a
682	# path it does not hold is not there. A partial one is what has been read so
683	# far, with the paths that were asked for and found missing; any other path
684	# is one the walk was not given, and it asks for it.
685	type Tree is Data:
686	  Tree{whole: Bool, files: List<&2, Source>, gone: List<&2, String>}
687	
688	# what a tree says of a path: here with its text, not there, or not given
689	type Look is Data:
690	  Here{text: String}
691	  Absent{}
692	  Unasked{}
693	
694	# a file of the package as the walk found it: the name it takes inside the
695	# package, and its text
696	type Hit is Data:
697	  Hit{raw: String, text: String}
698	
699	# why the walk stopped, or that it has not: a module imported and not there,
700	# an import that climbs out of the checkout, a file the walk was not given,
701	# fuel run out with files still queued, or an import of a name the hub rules
702	# out
703	type Stop is Data:
704	  Going{}
705	  Missing{at: String}
706	  Climbs{at: String}
707	  Asking{at: String}
708	  Spent{}
709	  Unnamed{nv: String}
710	
711	# the walk so far: the files already visited, what was found, whether it has
712	# stopped, and the files still to visit
713	type State is Data:
714	  State{seen: List<&2, String>, out: List<&2, Hit>, stop: Stop, queue: List<&2, Task>}
715	
716	# what the walk made of a tree: the package, the file it needs next, or why
717	# there is no package. A package is its hash, the directory its paths are
718	# written from, the files it lays with their texts, and those files weighed,
719	# in path order, which is what its manifest lists.
720	type Walked is Data:
721	  Walked{hash: String, root: String, files: List<&2, Source>, sums: List<&2, Item>}
722	  Asks{at: String}
723	  Refused{why: String}
724	
725	# a path of the project, as it is written inside a package rooted at `root`:
726	# the path itself under the project's own root, and the path with the root's
727	# directories taken off otherwise. The hub serves a package's files at these
728	# paths, so `ez add` and `ez publish` both name the entry by it.
729	def inside(+root: String, +path: String) -> String:
730	  Bool.pick(String, String.eq(root, "."), path,
731	    String.drop(path, (String.length(root) + 1n : Nat)))
732	
733	# one step of a lookup, with the head's answer in hand. The rest arrives as a
734	# thunk, so a hit ends the search.
735	def look.step(hit: Bool, text: String, rest: Unit -> Maybe<&2, String>) -> Maybe<&2, String>:
736	  match hit:
737	    case True{}:
738	      Some{text}
739	    case False{}:
740	      rest(Unit{})
741	
742	# a file list's text for a path, first in the list, or None when it has none
743	def look(fs: List<&2, Source>, +at: String) -> Maybe<&2, String>:
744	  match fs:
745	    case []:
746	      None{}
747	    case Source{+h, text} <> t:
748	      look.step(String.eq(h, at), text, _u => look(t, at))
749	
750	# a path that was asked for and found missing is not there; one that was not
751	# asked for is not given
752	def find.asked(asked: Bool) -> Look:
753	  match asked:
754	    case True{}:
755	      Absent{}
756	    case False{}:
757	      Unasked{}
758	
759	# a path the files do not hold: not there in a whole tree, and in a partial
760	# one unless it was asked for already
761	def find.miss(whole: Bool, gone: List<&2, String>, +at: String) -> Look:
762	  match whole:
763	    case True{}:
764	      Absent{}
765	    case False{}:
766	      find.asked(seen.has(gone, at))
767	
768	# a path the files hold is here
769	def find.got(got: Maybe<&2, String>, whole: Bool, gone: List<&2, String>, +at: String) -> Look:
770	  match got:
771	    case Some{text}:
772	      Here{text}
773	    case None{}:
774	      find.miss(whole, gone, at)
775	
776	# what a tree says of a path
777	def find(tree: Tree, +at: String) -> Look:
778	  Tree{whole, files, gone} = tree
779	  find.got(look(files, at), whole, gone, at)
780	
781	# a checkout-relative path that climbs above the checkout's top
782	def outside(+at: String) -> Bool:
783	  +n = P.norm(at)
784	  Bool.or(String.eq(n, ".."), String.starts_with(n, "../"))
785	
786	# the file bend takes along beside every file it publishes: a file named
787	# exactly `LICENSE` in the same directory, at the same path in the package.
788	# bend 2.0.27 hashes it with the rest, so a package that has one is named
789	# with it.
790	def beside(+path: String) -> String:
791	  P.join(P.dir(path), "LICENSE")
792	
793	# the LICENSE beside a published file, when the tree holds one, named beside
794	# the file's own name in the package
795	def license.put(got: Look, +raw: String) -> List<&2, Hit>:
796	  match got:
797	    case Here{text}:
798	      [Hit{raw, text}]
799	    case Absent{}:
800	      []
801	    case Unasked{}:
802	      []
803	
804	# a foreign body the tree holds, with the LICENSE beside it, or nothing when
805	# it is not there. bend uploads only the ones that are there. It is named the
806	# way the module importing it is named, from that module's own directory:
807	# `bend --publish` writes `src/util/beep.c` for a body imported by
808	# `src/util/math.bend`.
809	def foreign.put(got: Look, +tree: Tree, +at: String, +raw: String) -> List<&2, Hit>:
810	  match got:
811	    case Here{text}:
812	      Hit{raw, text} <> license.put(find(tree, beside(at)), beside(raw))
813	    case Absent{}:
814	      []
815	    case Unasked{}:
816	      []
817	
818	# every foreign body a file imports, named from the importing module's
819	# directory
820	def foreigns(+tree: Tree, +dir: String, +nd: String, ats: List<&2, String>) -> List<&2, Hit>:
821	  match ats:
822	    case []:
823	      []
824	    case +h <> t:
825	      List.append(&2, Hit, foreign.put(find(tree, P.join(dir, h)), tree, P.join(dir, h),
826	        P.join(nd, h)), foreigns(tree, dir, nd, t))
827	
828	# a file the walk may need stops it only when it was not given, as a
829	# question: one that is there or not there lets the walk go on
830	def asked(got: Look, +at: String, rest: Unit -> Stop) -> Stop:
831	  match got:
832	    case Here{_text}:
833	      rest(Unit{})
834	    case Absent{}:
835	      rest(Unit{})
836	    case Unasked{}:
837	      Asking{at}
838	
839	# a foreign body inside the checkout stops the walk only when it, or the
840	# LICENSE beside it once it is there, was not given
841	def foreign.asked(got: Look, +tree: Tree, +at: String, rest: Unit -> Stop) -> Stop:
842	  match got:
843	    case Here{_text}:
844	      asked(find(tree, beside(at)), beside(at), rest)
845	    case Absent{}:
846	      rest(Unit{})
847	    case Unasked{}:
848	      Asking{at}
849	
850	# a foreign body that climbs out of the checkout stops the walk, naming it
851	def foreign.judge(out: Bool, +tree: Tree, +at: String, +raw: String, rest: Unit -> Stop) -> Stop:
852	  match out:
853	    case True{}:
854	      Climbs{raw}
855	    case False{}:
856	      foreign.asked(find(tree, at), tree, at, rest)
857	
858	# the first foreign body of a file that stops the walk, or `Going` when none
859	# does
860	def foreign.check(+tree: Tree, +dir: String, +nd: String, ats: List<&2, String>) -> Stop:
861	  match ats:
862	    case []:
863	      Going{}
864	    case +h <> t:
865	      +at = P.join(dir, h)
866	      foreign.judge(outside(at), tree, at, P.join(nd, h),
867	        _u => foreign.check(tree, dir, nd, t))
868	
869	# a file whose LICENSE and foreign bodies are all settled: itself, the LICENSE
870	# beside it and its foreign bodies found, and the modules it imports put at
871	# the front of the queue, so the walk goes depth first the way bend's does. A foreign body that stops the walk
872	# leaves the file queued, so an answered question visits it again.
873	def visit.put(
874	  fstop: Stop,
875	  +tree: Tree,
876	  +sc: Scan,
877	  +text: String,
878	  +file: String,
879	  +ns: String,
880	  eb: String,
881	  seen: List<&2, String>,
882	  out: List<&2, Hit>,
883	  rest: List<&2, Task>
884	) -> State:
885	  match fstop:
886	    case Going{}:
887	      +d = P.dir(file)
888	      +nd = nsdir(ns)
889	      +raw = raw_of(ns, eb)
890	      State{file <> seen,
891	        Hit{raw, text} <> List.append(&2, Hit,
892	          license.put(find(tree, beside(file)), beside(raw)),
893	          List.append(&2, Hit, foreigns(tree, d, nd, scan.foreign(sc)), out)),
894	        Going{},
895	        List.append(&2, Task, tasks(d, nd, scan.mods(sc)), rest)}
896	    case Missing{at}:
897	      State{seen, out, Missing{at}, Task{file, ns} <> rest}
898	    case Climbs{at}:
899	      State{seen, out, Climbs{at}, Task{file, ns} <> rest}
900	    case Asking{at}:
901	      State{seen, out, Asking{at}, Task{file, ns} <> rest}
902	    case Spent{}:
903	      State{seen, out, Spent{}, Task{file, ns} <> rest}
904	    case Unnamed{nv}:
905	      State{seen, out, Unnamed{nv}, Task{file, ns} <> rest}
906	
907	# a file that imports a name the hub rules out stops the walk, naming it, as
908	# bend refuses to load it; any other goes on to its foreign bodies
909	def named.check.at(none: Bool, nv: String, rest: Unit -> Stop) -> Stop:
910	  match none:
911	    case True{}:
912	      rest(Unit{})
913	    case False{}:
914	      Unnamed{nv}
915	
916	def named.check(+nv: String, rest: Unit -> Stop) -> Stop:
917	  named.check.at(String.is_empty(nv), nv, rest)
918	
919	# a file that is in the tree, scanned, with the LICENSE beside it, its named
920	# imports and its foreign bodies checked first
921	def visit.found(
922	  +tree: Tree,
923	  +text: String,
924	  +file: String,
925	  +ns: String,
926	  eb: String,
927	  seen: List<&2, String>,
928	  out: List<&2, Hit>,
929	  rest: List<&2, Task>
930	) -> State:
931	  +sc = scan(text)
932	  visit.put(asked(find(tree, beside(file)), beside(file),
933	      _u => named.check(unnamed(scan.mods(sc)),
934	        _v => foreign.check(tree, P.dir(file), nsdir(ns), scan.foreign(sc)))),
935	    tree, sc, text, file, ns, eb, seen, out, rest)
936	
937	# a module that is imported and not there stops the walk, since a package
938	# missing a file is not the package bend would publish. One the walk was not
939	# given stops it too, as a question, with the module still queued.
940	def visit.have(
941	  got: Look,
942	  +tree: Tree,
943	  +file: String,
944	  +ns: String,
945	  eb: String,
946	  seen: List<&2, String>,
947	  out: List<&2, Hit>,
948	  rest: List<&2, Task>
949	) -> State:
950	  match got:
951	    case Absent{}:
952	      State{seen, out, Missing{file}, rest}
953	    case Unasked{}:
954	      State{seen, out, Asking{file}, Task{file, ns} <> rest}
955	    case Here{text}:
956	      visit.found(tree, text, file, ns, eb, seen, out, rest)
957	
958	# the name an import that climbs out is refused under: the path it was
959	# reached through, or the entry's own path
960	def climbs.name(+ns: String, +file: String) -> String:
961	  Bool.pick(String, String.is_empty(ns), file, ns ++ ".bend")
962	
963	# a module above the checkout's top is refused rather than read: the package
964	# would be named after directories of whatever machine walked it
965	def visit.in(
966	  out: Bool,
967	  +tree: Tree,
968	  +file: String,
969	  +ns: String,
970	  eb: String,
971	  seen: List<&2, String>,
972	  outs: List<&2, Hit>,
973	  rest: List<&2, Task>
974	) -> State:
975	  match out:
976	    case True{}:
977	      State{seen, outs, Climbs{climbs.name(ns, file)}, rest}
978	    case False{}:
979	      visit.have(find(tree, file), tree, file, ns, eb, seen, outs, rest)
980	
981	# a file already visited keeps the name it was first reached through, the way
982	# bend's own walk does
983	def visit.go(
984	  hit: Bool,
985	  +tree: Tree,
986	  +file: String,
987	  ns: String,
988	  eb: String,
989	  seen: List<&2, String>,
990	  out: List<&2, Hit>,
991	  rest: List<&2, Task>
992	) -> State:
993	  match hit:
994	    case True{}:
995	      State{seen, out, Going{}, rest}
996	    case False{}:
997	      visit.in(outside(file), tree, file, ns, eb, seen, out, rest)
998	
999	# the next file of the queue visited, or the walk as it is when the queue is
1000	# empty
1001	def step.pop(
1002	  +tree: Tree,
1003	  eb: String,
1004	  +seen: List<&2, String>,
1005	  out: List<&2, Hit>,
1006	  stop: Stop,
1007	  queue: List<&2, Task>
1008	) -> State:
1009	  match queue:
1010	    case []:
1011	      State{seen, out, stop, []}
1012	    case Task{+file, ns} <> t:
1013	      visit.go(seen.has(seen, file), tree, file, ns, eb, seen, out, t)
1014	
1015	# the walk as one step that does not recurse
1016	def step(+tree: Tree, eb: String, st: State) -> State:
1017	  State{seen, out, stop, queue} = st
1018	  step.pop(tree, eb, seen, out, stop, queue)
1019	
1020	# whether the walk has not stopped
1021	def stop.going(stop: Stop) -> Bool:
1022	  match stop:
1023	    case Going{}:
1024	      True{}
1025	    case Missing{_at}:
1026	      False{}
1027	    case Climbs{_at}:
1028	      False{}
1029	    case Asking{_at}:
1030	      False{}
1031	    case Spent{}:
1032	      False{}
1033	    case Unnamed{_nv}:
1034	      False{}
1035	
1036	# whether the walk is over: its queue is empty, or it has stopped
1037	def walk.done(+st: State) -> Bool:
1038	  State{_seen, _out, stop, queue} = st
1039	  Bool.or(List.is_empty(&2, Task, queue), Bool.not(stop.going(stop)))
1040	
1041	# the walk as it is when it is over, or one step further when it is not. The
1042	# rest of the walk arrives as a function, since a def may not call itself from
1043	# another def.
1044	def walk.more(done: Bool, st: State, go: State -> State) -> State:
1045	  match done:
1046	    case True{}:
1047	      st
1048	    case False{}:
1049	      go(st)
1050	
1051	# the fuel ran out: a walk that is over stays as it is, and one with files
1052	# still queued is spent, so it is refused rather than hashed short
1053	def walk.spent(done: Bool, st: State) -> State:
1054	  match done:
1055	    case True{}:
1056	      st
1057	    case False{}:
1058	      State{seen, out, _stop, queue} = st
1059	      State{seen, out, Spent{}, queue}
1060	
1061	# every file of the package reached from the entry, the step iterated under
1062	# fuel, until the walk is over or stops
1063	def walk(fuel: Nat, +tree: Tree, +eb: String, +st: State) -> State:
1064	  match fuel:
1065	    case 0n:
1066	      walk.spent(walk.done(st), st)
1067	    case 1n+f:
1068	      walk.more(walk.done(st), st, now => walk(f, tree, eb, step(tree, eb, now)))
1069	
1070	# the walk before its first step: the entry queued, under no name of its own
1071	def start(+entry: String) -> State:
1072	  State{[], [], Going{}, [Task{entry, ""}]}
1073	
1074	# ---------------------------------------------------------------------------
1075	# the package a walk found
1076	
1077	# a found file weighed: its name and the sha256 of its text
1078	def hit.sum(item: Hit) -> Found:
1079	  Hit{raw, +text} = item
1080	  Found{raw, Sha.hex(text)}
1081	
1082	# every found file weighed
1083	def hit.sums(fs: List<&2, Hit>) -> List<&2, Found>:
1084	  match fs:
1085	    case []:
1086	      []
1087	    case h <> t:
1088	      hit.sum(h) <> hit.sums(t)
1089	
1090	# a found file placed under whatever the package re-rooted at, with its text
1091	def laid.one(+pre: String, item: Hit) -> Source:
1092	  Hit{raw, text} = item
1093	  Source{P.join(pre, raw), text}
1094	
1095	# every found file placed, with its text
1096	def laid(+pre: String, fs: List<&2, Hit>) -> List<&2, Source>:
1097	  match fs:
1098	    case []:
1099	      []
1100	    case h <> t:
1101	      laid.one(pre, h) <> laid(pre, t)
1102	
1103	# a laid file weighed: its path and the sha256 of its text. This is what a
1104	# plan's reader would compute from the files a `Lay` writes.
1105	def laid.sum(src: Source) -> Item:
1106	  Source{at, +text} = src
1107	  Item{at, Sha.hex(text)}
1108	
1109	# every laid file weighed
1110	def laid.sums(fs: List<&2, Source>) -> List<&2, Item>:
1111	  match fs:
1112	    case []:
1113	      []
1114	    case h <> t:
1115	      laid.sum(h) <> laid.sums(t)
1116	
1117	# how far a found file climbs out of the entry's directory
1118	def hit.ups(item: Hit) -> Nat:
1119	  Hit{raw, _text} = item
1120	  P.ups(raw)
1121	
1122	# the deepest climb any file of the package makes
1123	def climb(fs: List<&2, Hit>) -> Nat:
1124	  match fs:
1125	    case []:
1126	      0n
1127	    case h <> t:
1128	      Nat.max(hit.ups(h), climb(t))
1129	
1130	# the found files named, once no path escapes the package
1131	def made.judge(
1132	  ok: Bool,
1133	  +bad: String,
1134	  +root: String,
1135	  +pre: String,
1136	  +fs: List<&2, Item>,
1137	  out: List<&2, Hit>
1138	) -> Walked:
1139	  match ok:
1140	    case True{}:
1141	      Walked{hash_of(fs), root, laid(pre, out), fs}
1142	    case False{}:
1143	      Refused{"ez: " ++ bad ++ " escapes the package"}
1144	
1145	# the found files, placed under the components the package re-roots under
1146	# and weighed once
1147	def made.placed(+root: String, +pre: String, +out: List<&2, Hit>) -> Walked:
1148	  +fs = files_of(placed(pre, hit.sums(out)))
1149	  +bad = escaped(fs)
1150	  made.judge(String.is_empty(bad), bad, root, pre, fs, out)
1151	
1152	# whether a component is named license in any case. bend 2.0.27 refuses to
1153	# publish a file under such a directory, since on a disk that does not tell
1154	# case apart it is the same name as a LICENSE file beside it.
1155	def license.is(+part: String) -> Bool:
1156	  String.eq(String.to_lower(part), "license")
1157	
1158	# one step of the search, with the head's answer in hand; the rest arrives as
1159	# a thunk, so a hit ends the search
1160	def license.step(here: Bool, rest: Unit -> Bool) -> Bool:
1161	  match here:
1162	    case True{}:
1163	      True{}
1164	    case False{}:
1165	      rest(Unit{})
1166	
1167	# whether any of the components is named license
1168	def license.any(ps: List<&2, String>) -> Bool:
1169	  match ps:
1170	    case []:
1171	      False{}
1172	    case +h <> t:
1173	      license.step(license.is(h), _u => license.any(t))
1174	
1175	# whether a path of the package lies under a directory named license
1176	def license.under(+at: String) -> Bool:
1177	  license.any(String.split(P.dir(at), '/'))
1178	
1179	# one step of the search for such a path
1180	def licensed.step(here: Bool, +at: String, rest: Unit -> String) -> String:
1181	  match here:
1182	    case True{}:
1183	      at
1184	    case False{}:
1185	      rest(Unit{})
1186	
1187	# the first found file whose place in the package lies under a directory
1188	# named license, or "" when none does. It reads names alone, so nothing is
1189	# weighed for it.
1190	def licensed(+pre: String, fs: List<&2, Hit>) -> String:
1191	  match fs:
1192	    case []:
1193	      ""
1194	    case Hit{raw, _text} <> t:
1195	      +at = P.join(pre, raw)
1196	      licensed.step(license.under(at), at, _u => licensed(pre, t))
1197	
1198	# the found files placed and weighed, once none lies under a directory named
1199	# license, which bend refuses before it mines
1200	def made.lic(ok: Bool, +bad: String, +root: String, +pre: String, +out: List<&2, Hit>) -> Walked:
1201	  match ok:
1202	    case True{}:
1203	      made.placed(root, pre, out)
1204	    case False{}:
1205	      Refused{"ez: " ++ bad ++ " is in a directory named license, which clashes with a LICENSE file"}
1206	
1207	# the found files, refused when one lies under a directory named license, and
1208	# placed and weighed otherwise
1209	def made.checked(+root: String, +pre: String, +out: List<&2, Hit>) -> Walked:
1210	  +bad = licensed(pre, out)
1211	  made.lic(String.is_empty(bad), bad, root, pre, out)
1212	
1213	# a package that climbs re-roots under as many of the entry directory's
1214	# trailing components as its deepest climb. The walk refuses an import that
1215	# climbs out of the checkout, so there are always that many; a package that
1216	# still climbs further is refused rather than named after nothing.
1217	def made.anc(far: Bool, +levels: Nat, +dir: String, +out: List<&2, Hit>) -> Walked:
1218	  match far:
1219	    case True{}:
1220	      Refused{"ez: the package climbs out of the checkout"}
1221	    case False{}:
1222	      made.checked(P.climb(levels, dir), P.tail(dir, levels), out)
1223	
1224	# how many components a checkout-relative directory has: none for the
1225	# checkout's top
1226	def comps(+dir: String) -> Nat:
1227	  +d = P.norm(dir)
1228	  Bool.pick(Nat, Bool.or(String.eq(d, "."), String.is_empty(d)), 0n,
1229	    List.length(&2, String, String.split(d, '/')))
1230	
1231	# the deepest climb decided: none leaves the package at the entry's directory
1232	def made.climb(+levels: Nat, +dir: String, +out: List<&2, Hit>) -> Walked:
1233	  match levels:
1234	    case 0n:
1235	      made.checked(P.norm(dir), "", out)
1236	    case 1n+p:
1237	      made.anc(Nat.is_gt(1n+p, comps(dir)), 1n+p, dir, out)
1238	
1239	# the walk's end judged: a walk that is over is the package, one that asks is
1240	# a question, and every other stop is a refusal naming what stopped it
1241	def made.go(stop: Stop, +entry: String, +out: List<&2, Hit>) -> Walked:
1242	  match stop:
1243	    case Going{}:
1244	      made.climb(climb(out), P.dir(entry), out)
1245	    case Missing{at}:
1246	      Refused{"ez: " ++ at ++ " is imported but not there"}
1247	    case Climbs{at}:
1248	      Refused{"ez: the import " ++ at ++ " climbs out of the checkout"}
1249	    case Asking{at}:
1250	      Asks{at}
1251	    case Spent{}:
1252	      Refused{"ez: the walk from " ++ entry ++ " ran out of fuel"}
1253	    case Unnamed{nv}:
1254	      Refused{unnamed.why(nv)}
1255	
1256	# the walk's end, judged
1257	def made(+entry: String, st: State) -> Walked:
1258	  State{_seen, out, stop, _queue} = st
1259	  made.go(stop, entry, out)
1260	
1261	# the package an entry of a tree would be published as, from the tree's
1262	# files alone, with this much fuel
1263	def of.tree(fuel: Nat, +entry: String, +tree: Tree) -> Walked:
1264	  made(entry, walk(fuel, tree, P.base(entry), start(entry)))
1265	
1266	# the same over a whole checkout
1267	def of.fuel(fuel: Nat, +entry: String, +fs: List<&2, Source>) -> Walked:
1268	  of.tree(fuel, entry, Tree{True{}, fs, []})
1269	
1270	# fuel enough for a walk over these files: one step for the entry and one for
1271	# every import it can queue, and every import is a line of some file. A
1272	# function of the files rather than a number, so no checkout is too big for
1273	# it and a proof about files it does not know leaves it unevaluated.
1274	def walk.fuel(fs: List<&2, Source>) -> Nat:
1275	  match fs:
1276	    case []:
1277	      1n
1278	    case Source{_at, text} <> t:
1279	      (List.length(&2, String, String.lines(text)) + walk.fuel(t) : Nat)
1280	
1281	# the same, with fuel enough for every file of the checkout
1282	def of(+entry: String, +fs: List<&2, Source>) -> Walked:
1283	  of.fuel(walk.fuel(fs), entry, fs)
1284	
1285	# ---------------------------------------------------------------------------
1286	# the walk answered from disk
1287	
1288	# a path read and found missing, added to what the walk was given
1289	def tree.gone(tree: Tree, at: String) -> Tree:
1290	  Tree{whole, files, gone} = tree
1291	  Tree{whole, files, at <> gone}
1292	
1293	# a file read, added to what the walk was given
1294	def tree.have(tree: Tree, src: Source) -> Tree:
1295	  Tree{whole, files, gone} = tree
1296	  Tree{whole, src <> files, gone}
1297	
1298	# what a read answered, added to what the walk was given
1299	def tree.add(got: Maybe<&2, String>, tree: Tree, +at: String) -> Tree:
1300	  match got:
1301	    case None{}:
1302	      tree.gone(tree, at)
1303	    case Some{text}:
1304	      tree.have(tree, Source{at, text})
1305	
1306	# a walk that stopped to ask, taken up again where it stopped
1307	def resume(st: State) -> State:
1308	  State{seen, out, _stop, queue} = st
1309	  State{seen, out, Going{}, queue}
1310	
1311	# why a walk stopped
1312	def state.stop(st: State) -> Stop:
1313	  State{_seen, _out, stop, _queue} = st
1314	  stop
1315	
1316	# a walk's verdict as a package, with its root taken back under the checkout
1317	# it was read from
1318	def made.io(+top: String, got: Walked) -> IO(Pkg):
1319	  match got:
1320	    case Walked{hash, root, _files, sums}:
1321	      IO.pure(Pkg, Pkg{hash, P.join(top, root), files_of(sums)})
1322	    case Asks{at}:
1323	      IO.die(Pkg, 1, "ez: the walk asked for " ++ at ++ " after it was answered")
1324	    case Refused{why}:
1325	      IO.die(Pkg, 1, why)
1326	
1327	# a question read from disk and the walk carried on, or the walk's end judged
1328	def pkg.next(
1329	  stop: Stop,
1330	  +top: String,
1331	  +entry: String,
1332	  +tree: Tree,
1333	  +st: State,
1334	  go: Tree -> State -> IO(Pkg)
1335	) -> IO(Pkg):
1336	  match stop:
1337	    case Asking{+at}:
1338	      do IO<Pkg>:
1339	        m : Maybe<&2, String> <- F.read(P.join(top, at))
1340	        go(tree.add(m, tree, at), resume(st))
1341	    case Going{}:
1342	      made.io(top, made(entry, st))
1343	    case Missing{_at}:
1344	      made.io(top, made(entry, st))
1345	    case Climbs{_at}:
1346	      made.io(top, made(entry, st))
1347	    case Spent{}:
1348	      made.io(top, made(entry, st))
1349	    case Unnamed{_nv}:
1350	      made.io(top, made(entry, st))
1351	
1352	# fuel enough for a walk taken up again over the files read so far: a step
1353	# for every file still queued, and `walk.fuel`'s step for every import those files
1354	# can queue
1355	def resumed.fuel(+tree: Tree, +st: State) -> Nat:
1356	  Tree{_whole, fs, _gone} = tree
1357	  State{_seen, _out, _stop, queue} = st
1358	  (List.length(&2, Task, queue) + walk.fuel(fs) : Nat)
1359	
1360	# how many files the walk from disk may ask for. It asks for one file a round
1361	# and cannot know how many the checkout holds until it has read them, so this
1362	# is a guard against a walk that keeps asking, not a limit on a package: a
1363	# package of more files than this is refused, never hashed short.
1364	def asks() -> Nat:
1365	  U32.to_nat(100000)
1366	
1367	# the walk over what has been read so far, and each file it asks for read
1368	# and handed back, until it no longer asks
1369	def pkg.ask(fuel: Nat, +top: String, +entry: String, +eb: String, +tree: Tree, +st: State) -> IO(Pkg):
1370	  match fuel:
1371	    case 0n:
1372	      IO.die(Pkg, 1, "ez: the walk from " ++ entry ++ " asked too many questions")
1373	    case 1n+f:
1374	      +now = walk(resumed.fuel(tree, st), tree, eb, st)
1375	      pkg.next(state.stop(now), top, entry, tree, now,
1376	        t => s => pkg.ask(f, top, entry, eb, t, s))
1377	
1378	# the package an entry would be published as, walked over its checkout: the
1379	# entry and every file the walk reaches are paths from `top`, read from disk
1380	# as the walk asks for them. An import that climbs above `top` is refused.
1381	def walk.io(+top: String, +entry: String) -> IO(Pkg):
1382	  pkg.ask(asks(), top, entry, P.base(entry), Tree{False{}, [], []},
1383	    start(entry))
1384	
1385	# the package an entry of a checkout would be published as
1386	def pkg_in(+top: String, +entry: String) -> IO(Pkg):
1387	  walk.io(top, P.norm(entry))
1388	
1389	# an entry named from the working directory is walked over the working
1390	# directory, and one named from the root over the whole file system
1391	def pkg.from(abs: Bool, +entry: String) -> IO(Pkg):
1392	  match abs:
1393	    case True{}:
1394	      walk.io("/", String.drop(entry, 1n))
1395	    case False{}:
1396	      walk.io("", entry)
1397	
1398	# the package an entry file would be published as: every module it reaches,
1399	# every foreign body beside them, and the hash over their manifest. A relative
1400	# entry's checkout is the working directory, which is the project a command
1401	# runs in.
1402	def pkg_of(+entry: String) -> IO(Pkg):
1403	  pkg.from(String.starts_with(entry, "/"), entry)
1404	
1405	# the hash that names a package
1406	def pkg.hash(package: Pkg) -> String:
1407	  Pkg{h, _root, _fs} = package
1408	  h
1409	
1410	# the directory a package's file paths are written from
1411	def pkg.root(package: Pkg) -> String:
1412	  Pkg{_h, root, _fs} = package
1413	  root
1414	
1415	# the files a package holds
1416	def pkg.files(package: Pkg) -> List<&2, Item>:
1417	  Pkg{_h, _root, fs} = package
1418	  fs
1419	
1420	# the sha256 recorded for a file
1421	def file.sum(item: Item) -> String:
1422	  Item{_at, sum} = item
1423	  sum