src/rules/pedantic/tail.bend
bolt@1.25.0.0 · 67 lines · 0 definitions
1# rule tail: a def whose first live parameter is a List or a String calls
2# itself where the call is not the whole statement: `h <> go(t)`,
3# `(1 + go(t) : U32)`, `+rest = go(t)`. The test is on that parameter's type
4# alone, never on whether the self-call shrinks it: a def that recurses on
5# a later Nat is reported too, and one whose list comes second is not. Each
6# such call holds a frame until the rest of the input is done, and the JS lane
7# overflows its stack at a few thousand to ~64K elements (bend-http on a 48KB
8# header, agora at ~4,900 entries); native is fine. Carry an accumulator and
9# make the self-call the whole statement (reverse once at the end if order
10# matters). Idiomatic code does this on purpose, so the rule is noisy: off
11# unless asked. Everything inside a `Bool.pick(..)` is skipped, whether or
12# not `pick` reports it; laws and proofs are exempt, and a def with no type
13# at all fills a law, so it is a proof.
14import Base
15import bolt@1.25.0.0/src/src.bend as Src
16import bolt@1.25.0.0/src/finding.bend as F
17import bolt@1.25.0.0/src/syntax/lex.bend as Lex
18import bolt@1.25.0.0/src/syntax/tree.bend as Tree
19import bolt@1.25.0.0/src/lazy/lazy.bend as Lazy
20import bolt@1.25.0.0/src/rules/calls.bend as Calls
21
22# is a statement's chain exactly a call of the name, `name(..)`?
23def bare(kids: Tree.Node, +name: String) -> Bool:
24 match kids:
25 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{g, Tree.NNil{}}}:
26 Bool.and(String.eq(t, name), Tree.opens(g, "("))
27 case other:
28 False{}
29
30# the self-calls not in tail position; skip: the chain is a bare self-call
31def walk(nn: Tree.Node, +name: String, +path: String, skip: Bool) -> List<&2, F.Finding>:
32 match nn:
33 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
34 +call = String.eq(o, "(")
35 +me = Bool.and(Bool.and(call, String.eq(t, name)), Bool.not(skip))
36 +inside = walk(kids, name, path, False{})
37 +more = List.concat(&2, F.Finding, [
38 Bool.pick(List<&2, F.Finding>, Bool.and(call, String.eq(t, "Bool.pick")), [], inside),
39 walk(rest, name, path, False{})])
40 Bool.pick(List<&2, F.Finding>, me,
41 F.Finding{path, l, c, U32.from_nat(String.length(name)), "tail",
42 "This call to " ++ name ++ " is not a tail call, so a long list or string overflows the stack on the JS lane; carry an accumulator."}
43 <> more,
44 more)
45 case Tree.NCons{Tree.Group{open, kids, close}, rest}:
46 List.concat(&2, F.Finding, [walk(kids, name, path, False{}), walk(rest, name, path, False{})])
47 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
48 List.concat(&2, F.Finding, [walk(kids, name, path, bare(kids, name)), walk(body, name, path, False{}),
49 walk(rest, name, path, False{})])
50 case Tree.NCons{h, rest}:
51 walk(rest, name, path, False{})
52 case other:
53 Nil{}
54
55def check.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:
56 match ds:
57 case Nil{}:
58 List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
59 case Con{Calls.Def{+name, +sig, body}, rest}:
60 check.go(rest, path,
61 Lazy.stop(List<&2, F.Finding>, Bool.not(Bool.and(Calls.seq(sig), Bool.not(Calls.exempt(path, sig)))), [],
62 _u => walk(body, name, path, False{})) <> acc)
63
64# the rule
65def check(ss: Src.Src) -> List<&2, F.Finding>:
66 Src.Src{path, text, toks, tree, bound, items} = ss
67 check.go(Calls.defs(tree), path, [])