common.bend

bend-lint-pack@0.1.1.0 · 473 lines · 63 definitions

1# Helpers shared by the rules in this repo. A rule file imports this as ../common.bend.
2import Base
3import bend-lint-pack@0.1.1.0/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.
8type 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.
12type Owners is Data:
13  Owners{list: List<&2, Seen>, set: Set()}
14
15def Owners.empty() -> Owners:
16  Owners{[], Set.new()}
17
18def 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
32def 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.
44def 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
49def 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.
55def 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.
61def 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# ===========
68def 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.
72def when(hit: Bool, d: Lint.Diag) -> List<&2, Lint.Diag>:
73  match hit:
74    case True{}:
75      [d]
76    case False{}:
77      []
78
79def 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`.
89def 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.
93def is_package(name: String) -> Bool:
94  String.starts_with(name, "0x")
95
96# Whether a name is in a set.
97def 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.
103def 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
112def 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.
120def 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.
129type Graph is Data:
130  Graph{owners: Owners, edges: Map<&2, List<&2, String>>, into: Map<&2, List<&2, String>>}
131
132def Graph.empty() -> Graph:
133  Graph{Owners.empty(), Map.new(&2, List<&2, String>), Map.new(&2, List<&2, String>)}
134
135def 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
149def 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
174def 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`.
183def base(+name: String) -> String:
184  base.of(String.split(name, '~'), name)
185
186def 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.
192def 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.
201def Laws.name(parts: List<&2, String>) -> List<&2, String>:
202  match parts:
203    case Con{h, t}:
204      [h]
205    case Nil{}:
206      []
207
208def 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
216def 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
223def 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`.
231def 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.
239def 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.
247def 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.
257def 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.
261def 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.
267def 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
274def 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.
286def 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.
295def 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
305def 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.
313def 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.
319def 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
326def 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
332def 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.
341type 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
350def 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
359def 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
374def 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
384def 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.
392type Count is Data:
393  Count{seen: Set(), n: U32}
394
395def 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
402def 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
407def Count.n(c: Count) -> U32:
408  match c:
409    case Count{seen, n}:
410      n
411
412def 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
419def 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.
428def 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.
435type Scope is Data:
436  Scope{imports: Bool, root: String}
437
438def 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
445def 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
448def 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
455def 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
460def 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.
468def 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))