1	# Helpers shared by the rules in this repo. A rule file imports this as ../common.bend.
2	import Base
3	import ./vendor/lint.bend as Lint
4	
5	# Owners of facts
6	# ===============
7	# A global name that owns facts (a def, a law, a type, a constructor), and where its first fact sits.
8	type Seen is Data:
9	  Seen{owner: String, span: Maybe<&2, Lint.Span>}
10	
11	# The owners of the facts read so far: in reverse order of first appearance, and as a set.
12	type Owners is Data:
13	  Owners{list: List<&2, Seen>, set: Set()}
14	
15	def Owners.empty() -> Owners:
16	  Owners{[], Set.new()}
17	
18	def Owners.pick(
19	  list: List<&2, Seen>,
20	  +set: Set(),
21	  had: Bool,
22	  +owner: String,
23	  inst: Bool,
24	  span: Maybe<&2, Lint.Span>
25	) -> Owners:
26	  match had inst:
27	    case False{} False{}:
28	      Owners{Seen{owner, span} <> list, Set.add(set, owner)}
29	    case _ _:
30	      Owners{list, set}
31	
32	def Owners.seen(
33	  list: List<&2, Seen>,
34	  r: Set() & Bool,
35	  +owner: String,
36	  inst: Bool,
37	  span: Maybe<&2, Lint.Span>
38	) -> Owners:
39	  match r:
40	    case Tuple{set, had}:
41	      Owners.pick(list, set, had, owner, inst, span)
42	
43	# Template instances are skipped, so a template is seen once, as itself.
44	def Owners.note(acc: Owners, +owner: String, inst: Bool, span: Maybe<&2, Lint.Span>) -> Owners:
45	  match acc:
46	    case Owners{list, +set}:
47	      Owners.seen(list, Set.has(set, owner), owner, inst, span)
48	
49	def Owners.add(acc: Owners, v: Lint.View) -> Owners:
50	  match v:
51	    case Lint.View{owner, inst, kind, name, q, span, inner}:
52	      Owners.note(acc, owner, inst, span)
53	
54	# A fold_facts step: records each fact's owner.
55	def Owners.collect(acc: Owners, +f: Lint.Fact) -> IO(Owners):
56	  do IO<Owners>:
57	    v : Lint.View <- Lint.view(f)
58	    return Owners.add(acc, v)
59	
60	# The owners in order of first appearance.
61	def Owners.ordered(o: Owners) -> List<&2, Seen>:
62	  match o:
63	    case Owners{list, set}:
64	      List.reverse(&2, Seen, list)
65	
66	# Diagnostics
67	# ===========
68	def diag(sev: Lint.Severity, message: String, span: Maybe<&2, Lint.Span>) -> Lint.Diag:
69	  Lint.Diag{sev, message, span, []}
70	
71	# One diagnostic when `hit`, else none.
72	def when(hit: Bool, d: Lint.Diag) -> List<&2, Lint.Diag>:
73	  match hit:
74	    case True{}:
75	      [d]
76	    case False{}:
77	      []
78	
79	def onto(xs: List<&2, Lint.Diag>, out: List<&2, Lint.Diag>) -> List<&2, Lint.Diag>:
80	  match xs:
81	    case Nil{}:
82	      out
83	    case Con{x, rest}:
84	      onto(rest, x <> out)
85	
86	# Names
87	# =====
88	# The part of a global name after its file's namespace: `b:helper` is `helper`.
89	def local(+name: String) -> String:
90	  Maybe.default(&2, String, List.last(&2, String, String.split(name, ':')), name)
91	
92	# Whether a global name comes from a BendHub package (`0x<hash>/file:name`): not this project's code.
93	def is_package(name: String) -> Bool:
94	  String.starts_with(name, "0x")
95	
96	# Whether a name is in a set.
97	def has(s: Set(), name: String) -> Bool:
98	  Pair.snd(Set(), Bool, Set.has(s, name))
99	
100	# Graph of references between globals
101	# ====================================
102	# Lists of names under a name, last added first.
103	def Edges.add.of(
104	  got: Map<&2, List<&2, String>> & List<&2, String>,
105	  key: String,
106	  x: String
107	) -> Map<&2, List<&2, String>>:
108	  match got:
109	    case Tuple{m, old}:
110	      Map.set(&2, List<&2, String>, m, key, x <> old)
111	
112	def Edges.add(
113	  m: Map<&2, List<&2, String>>,
114	  +key: String,
115	  x: String
116	) -> Map<&2, List<&2, String>>:
117	  Edges.add.of(Map.get(List<&2, String>, [], m, key), key, x)
118	
119	# The names under `key`, last added first; the map is only read.
120	def Edges.of(+m: Map<&2, List<&2, String>>, key: String) -> List<&2, String>:
121	  Pair.snd(
122	    Map<&2, List<&2, String>>,
123	    List<&2, String>,
124	    Map.get(List<&2, String>, [], m, key)
125	  )
126	
127	# What the facts say: the owners, `edges` (owner -> names it references, with repeats), and `into`
128	# (name -> owners that reference it, with repeats). A name an owner uses for itself is no edge.
129	type Graph is Data:
130	  Graph{owners: Owners, edges: Map<&2, List<&2, String>>, into: Map<&2, List<&2, String>>}
131	
132	def Graph.empty() -> Graph:
133	  Graph{Owners.empty(), Map.new(&2, List<&2, String>), Map.new(&2, List<&2, String>)}
134	
135	def Graph.link(
136	  hit: Bool,
137	  +owner: String,
138	  +name: String,
139	  owners: Owners,
140	  edges: Map<&2, List<&2, String>>,
141	  into: Map<&2, List<&2, String>>
142	) -> Graph:
143	  match hit:
144	    case True{}:
145	      Graph{owners, Edges.add(edges, owner, name), Edges.add(into, name, owner)}
146	    case False{}:
147	      Graph{owners, edges, into}
148	
149	def Graph.add.of(
150	  g: Graph,
151	  +owner: String,
152	  +inst: Bool,
153	  +kind: String,
154	  +name: String,
155	  span: Maybe<&2, Lint.Span>
156	) -> Graph:
157	  match g:
158	    case Graph{owners, edges, into}:
159	      Graph.link(
160	        Bool.and(
161	          Bool.not(inst),
162	          Bool.and(
163	            String.eq(kind, "Ref"),
164	            Bool.and(Bool.not(String.is_empty(name)), Bool.not(String.eq(name, owner)))
165	          )
166	        ),
167	        owner,
168	        name,
169	        Owners.note(owners, owner, inst, span),
170	        edges,
171	        into
172	      )
173	
174	def base.of(parts: List<&2, String>, name: String) -> String:
175	  match parts:
176	    case Con{h, t}:
177	      h
178	    case Nil{}:
179	      name
180	
181	# A template call refers to an instance, `twice~0`, and a template's own parameter is `twice~f`: both
182	# are the template, `twice`.
183	def base(+name: String) -> String:
184	  base.of(String.split(name, '~'), name)
185	
186	def Graph.add(g: Graph, v: Lint.View) -> Graph:
187	  match v:
188	    case Lint.View{owner, inst, kind, name, q, span, inner}:
189	      Graph.add.of(g, owner, inst, kind, base(name), span)
190	
191	# A fold_facts step.
192	def Graph.collect(g: Graph, +f: Lint.Fact) -> IO(Graph):
193	  do IO<Graph>:
194	    v : Lint.View <- Lint.view(f)
195	    return Graph.add(g, v)
196	
197	# Laws
198	# ====
199	# Laws are specs, not code: a def that fills one is a proof. They are found in the text (`law name:`
200	# at the start of a line), as the checker gives a law and its proof one owner and no flag.
201	def Laws.name(parts: List<&2, String>) -> List<&2, String>:
202	  match parts:
203	    case Con{h, t}:
204	      [h]
205	    case Nil{}:
206	      []
207	
208	def Laws.line(+line: String) -> List<&2, String>:
209	  Bool.pick(
210	    List<&2, String>,
211	    String.starts_with(line, "law "),
212	    Laws.name(String.split(String.drop(line, 4n), ':')),
213	    []
214	  )
215	
216	def Laws.add(names: List<&2, String>, out: Set()) -> Set():
217	  match names:
218	    case Nil{}:
219	      out
220	    case Con{n, rest}:
221	      Laws.add(rest, Set.add(out, n))
222	
223	def Laws.lines(ls: List<&2, String>, out: Set()) -> Set():
224	  match ls:
225	    case Nil{}:
226	      out
227	    case Con{l, rest}:
228	      Laws.lines(rest, Laws.add(Laws.line(l), out))
229	
230	# The names of the laws written in the `sources` whose paths are in `paths`.
231	def Laws.scan(read: Bool, text: String, out: Set()) -> Set():
232	  match read:
233	    case True{}:
234	      Laws.lines(String.lines(text), out)
235	    case False{}:
236	      out
237	
238	# A call evaluates its arguments, so a file is split into lines only through a match: Base is long.
239	def Laws.sources(sources: List<&2, Lint.Source>, +paths: Set(), out: Set()) -> Set():
240	  match sources:
241	    case Nil{}:
242	      out
243	    case Con{Lint.Source{path, text, root}, rest}:
244	      Laws.sources(rest, paths, Laws.scan(has(paths, path), text, out))
245	
246	# The paths the owners' spans are in.
247	def Paths.of(seen: List<&2, Seen>, out: Set()) -> Set():
248	  match seen:
249	    case Nil{}:
250	      out
251	    case Con{Seen{owner, Some{Lint.Span{path, beg, end}}}, rest}:
252	      Paths.of(rest, Set.add(out, path))
253	    case Con{x, rest}:
254	      Paths.of(rest, out)
255	
256	# The local names of every law in the program's own files.
257	def Laws.of(sources: List<&2, Lint.Source>, owners: Owners) -> Set():
258	  Laws.sources(sources, Paths.of(Owners.ordered(owners), Set.new()), Set.new())
259	
260	# Whether `owner` is a law or the proof that fills one.
261	def Laws.has(laws: Set(), owner: String) -> Bool:
262	  has(laws, local(owner))
263	
264	# Owners that have a checked body
265	# ===============================
266	# Defs and laws have one; types and constructors do not.
267	def Bodies.put(b: Maybe<&2, Lint.Node>, owner: String, out: Set()) -> Set():
268	  match b:
269	    case Some{n}:
270	      Set.add(out, owner)
271	    case None{}:
272	      out
273	
274	def Bodies.of(seen: List<&2, Seen>, out: Set()) -> IO(Set()):
275	  match seen:
276	    case Nil{}:
277	      IO.pure(Set(), out)
278	    case Con{Seen{+owner, span}, rest}:
279	      do IO<Set()>:
280	        b : Maybe<&2, Lint.Node> <- Lint.body(owner)
281	        Bodies.of(rest, Bodies.put(b, owner, out))
282	
283	# Entry lists: `a, b, prefix*`
284	# ============================
285	# Whether the entry `e` names `name`: the same, or, if it ends in `*`, a prefix of it.
286	def Entry.hit(+e: String, +name: String) -> Bool:
287	  Bool.pick(
288	    Bool,
289	    String.ends_with(e, "*"),
290	    String.starts_with(name, String.take(e, Nat.sub(String.length(e), 1n))),
291	    String.eq(e, name)
292	  )
293	
294	# Whether some entry names `owner`, as written or without its namespace.
295	def Entry.any(entries: List<&2, String>, +owner: String) -> Bool:
296	  match entries:
297	    case Nil{}:
298	      False{}
299	    case Con{+e, rest}:
300	      Bool.or(
301	        Bool.or(Entry.hit(e, owner), Entry.hit(e, local(owner))),
302	        Entry.any(rest, owner)
303	      )
304	
305	def Entry.trim(xs: List<&2, String>) -> List<&2, String>:
306	  match xs:
307	    case Nil{}:
308	      []
309	    case Con{x, rest}:
310	      String.trim(x) <> Entry.trim(rest)
311	
312	# A comma-separated option as a list.
313	def Entry.parse(text: String) -> List<&2, String>:
314	  Entry.trim(String.split(text, ','))
315	
316	# The program's own code
317	# ======================
318	# The defs of the program: owners with a checked body that are not laws, proofs or package code.
319	def Nodes.put(hit: Bool, owner: String, out: Set()) -> Set():
320	  match hit:
321	    case True{}:
322	      Set.add(out, owner)
323	    case False{}:
324	      out
325	
326	def Nodes.is(+bodies: Set(), +laws: Set(), +owner: String) -> Bool:
327	  Bool.and(
328	    has(bodies, owner),
329	    Bool.and(Bool.not(Laws.has(laws, owner)), Bool.not(is_package(owner)))
330	  )
331	
332	def Nodes.of(seen: List<&2, Seen>, +bodies: Set(), +laws: Set(), out: Set()) -> Set():
333	  match seen:
334	    case Nil{}:
335	      out
336	    case Con{Seen{+owner, span}, rest}:
337	      Nodes.of(rest, bodies, laws, Nodes.put(Nodes.is(bodies, laws, owner), owner, out))
338	
339	# Everything a graph rule reads: the owners in order, the reference maps, the set of defs, and the
340	# local names of the laws.
341	type Prog is Data:
342	  Prog{
343	    seen: List<&2, Seen>,
344	    edges: Map<&2, List<&2, String>>,
345	    into: Map<&2, List<&2, String>>,
346	    nodes: Set(),
347	    laws: Set()
348	  }
349	
350	def Prog.with(
351	  +laws: Set(),
352	  +seen: List<&2, Seen>,
353	  edges: Map<&2, List<&2, String>>,
354	  into: Map<&2, List<&2, String>>,
355	  bodies: Set()
356	) -> Prog:
357	  Prog{seen, edges, into, Nodes.of(seen, bodies, laws, Set.new()), laws}
358	
359	def Prog.build(
360	  sources: List<&2, Lint.Source>,
361	  +seen: List<&2, Seen>,
362	  edges: Map<&2, List<&2, String>>,
363	  into: Map<&2, List<&2, String>>,
364	  bodies: Set()
365	) -> Prog:
366	  Prog.with(
367	    Laws.sources(sources, Paths.of(seen, Set.new()), Set.new()),
368	    seen,
369	    edges,
370	    into,
371	    bodies
372	  )
373	
374	def Prog.owners(
375	  sources: List<&2, Lint.Source>,
376	  +seen: List<&2, Seen>,
377	  edges: Map<&2, List<&2, String>>,
378	  into: Map<&2, List<&2, String>>
379	) -> IO(Prog):
380	  do IO<Prog>:
381	    bodies : Set() <- Bodies.of(seen, Set.new())
382	    return Prog.build(sources, seen, edges, into, bodies)
383	
384	def Prog.of(sources: List<&2, Lint.Source>, g: Graph) -> IO(Prog):
385	  match g:
386	    case Graph{owners, edges, into}:
387	      Prog.owners(sources, Owners.ordered(owners), edges, into)
388	
389	# Degrees
390	# =======
391	# A count of the different names that are defs, and the names counted.
392	type Count is Data:
393	  Count{seen: Set(), n: U32}
394	
395	def Count.put(hit: Bool, +x: String, seen: Set(), n: U32) -> Count:
396	  match hit:
397	    case True{}:
398	      Count{Set.add(seen, x), U32.add(n, 1)}
399	    case False{}:
400	      Count{seen, n}
401	
402	def Count.add(is_def: Bool, +x: String, c: Count) -> Count:
403	  match c:
404	    case Count{+seen, n}:
405	      Count.put(Bool.and(is_def, Bool.not(has(seen, x))), x, seen, n)
406	
407	def Count.n(c: Count) -> U32:
408	  match c:
409	    case Count{seen, n}:
410	      n
411	
412	def distinct(names: List<&2, String>, +nodes: Set(), c: Count) -> Count:
413	  match names:
414	    case Nil{}:
415	      c
416	    case Con{+x, rest}:
417	      distinct(rest, nodes, Count.add(has(nodes, x), x, c))
418	
419	def degree.go(is_def: Bool, names: List<&2, String>, nodes: Set()) -> U32:
420	  match is_def:
421	    case True{}:
422	      Count.n(distinct(names, nodes, Count{Set.new(), 0}))
423	    case False{}:
424	      0
425	
426	# The number of different defs of the program that `owner` has under it in `m` (the defs it uses,
427	# for `edges`; the defs that use it, for `into`). 0 for what is not a def.
428	def degree(+m: Map<&2, List<&2, String>>, +nodes: Set(), +owner: String) -> U32:
429	  degree.go(has(nodes, owner), Edges.of(m, owner), nodes)
430	
431	# Where to report
432	# ===============
433	# By default a rule reports only in the linted file, though it reads the whole program: the
434	# imported files are libraries to it. The `imports` option widens that to every file of the program.
435	type Scope is Data:
436	  Scope{imports: Bool, root: String}
437	
438	def root_path(sources: List<&2, Lint.Source>) -> String:
439	  match sources:
440	    case Nil{}:
441	      ""
442	    case Con{Lint.Source{+path, text, root}, rest}:
443	      Bool.pick(String, root, path, root_path(rest))
444	
445	def Scope.of(sources: List<&2, Lint.Source>, options: List<&2, Lint.Option>) -> Scope:
446	  Scope{Lint.option_flag(options, "imports", False{}), root_path(sources)}
447	
448	def in_root(+root: String, span: Maybe<&2, Lint.Span>) -> Bool:
449	  match span:
450	    case Some{Lint.Span{path, beg, end}}:
451	      String.eq(path, root)
452	    case None{}:
453	      False{}
454	
455	def Scope.has(scope: Scope, span: Maybe<&2, Lint.Span>) -> Bool:
456	  match scope:
457	    case Scope{imports, root}:
458	      Bool.or(imports, in_root(root, span))
459	
460	def scoped.put(hit: Bool, owner: String, span: Maybe<&2, Lint.Span>, out: List<&2, Seen>) -> List<&2, Seen>:
461	  match hit:
462	    case True{}:
463	      Seen{owner, span} <> out
464	    case False{}:
465	      out
466	
467	# The owners a rule reports on.
468	def scoped(+scope: Scope, seen: List<&2, Seen>) -> List<&2, Seen>:
469	  match seen:
470	    case Nil{}:
471	      []
472	    case Con{Seen{owner, +span}, rest}:
473	      scoped.put(Scope.has(scope, span), owner, span, scoped(scope, rest))