src/rules/suspicious/concat.bend source

src/rules/suspicious/concat.bend on the hub · documented module

# rule concat: a def passes itself a parameter grown at the end, `p ++ x` or# `List.append(.., p, ys)` (String.append(p, ..) too), as the argument in p's# own position, the slot it carries; p grown into another slot is not a# finding. The argument is that append written in place, inside any number# of parentheses (`(p ++ x)`), or a lone name read from a let: the nearest# `q = ..` or `+q = ..` of that name before the call in its block or an# enclosing one, whose right side is such an append (a later let of the name# shadows it; other binders, a typed or destructuring let and a do-bind do# not count). A String and a List are cons lists, so appending copies all of# p: the loop is quadratic, with right output (night-train's text step cost# three times the render; rootagi's JSON stringify). Prepend (`x <> acc`)# and reverse once at the end, build with `h <> go(t)`, or gather pieces and# join them once.import Baseimport ../../src.bend as Srcimport ../../finding.bend as Fimport ../../syntax/lex.bend as Leximport ../../syntax/tree.bend as Treeimport ../calls.bend as Callsimport ../../lazy/lazy.bend as Lazy# a leaf that is a lowercase name: its token. The rule matches a leaf's kind# here and in bound.is_eq only; the rest reads kinds through thesedef lone.name(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:  match nn:    case Tree.Leaf{Lex.Tok{Lex.TName{}, t, l, c}}:      Some{Lex.Tok{Lex.TName{}, t, l, c}}    case other:      None{}# a chain that is exactly one lowercase name: its tokendef lone(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:  match nn:    case Tree.NCons{h, Tree.NNil{}}:      lone.name(h)    case other:      None{}# the list a call appends onto: List.append's first list, String.append's firstdef appended(+tt: String, as: List<&2, Tree.Node>) -> Maybe<&2, Lex.Tok>:  +list = String.eq(tt, "List.append")  +str = String.eq(tt, "String.append")  Bool.pick(Maybe<&2, Lex.Tok>, Bool.or(list, str), lone(Calls.arg(as, Bool.pick(Nat, list, 2n, 0n))), None{})# a leaf, then a group: the call's appenddef onto.call(hh: Tree.Node, kids: Tree.Node) -> Maybe<&2, Lex.Tok>:  match hh:    case Tree.Leaf{Lex.Tok{k, +t, l, c}}:      appended(t, Calls.args(kids))    case other:      None{}# a first cell, then the second: a name then `++`, or a calldef onto.next(+hh: Tree.Node, h2: Tree.Node) -> Maybe<&2, Lex.Tok>:  match h2:    case Tree.Leaf{Lex.Tok{k, +o, _l, _c}}:      Bool.pick(Maybe<&2, Lex.Tok>, Bool.and(Calls.kind.oper(k), String.eq(o, "++")), lone.name(hh), None{})    case Tree.Group{open, kids, close}:      onto.call(hh, kids)    case other:      None{}# the name an argument appends onto, `p ++ ..` or an append call, inside any# number of parenthesesdef onto(aa: Tree.Node) -> Maybe<&2, Lex.Tok>:  match aa:    case Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, kids, _}, Tree.NNil{}}:      Lazy.stop(Maybe<&2, Lex.Tok>, Bool.not(String.eq(o, "(")), None{}, _u => onto(kids))    case Tree.NCons{hh, Tree.NCons{h2, rest}}:      onto.next(hh, h2)    case other:      None{}# a let of one plain name in scope: the name, and what its right side# appends ontotype Let is Data:  Let{name: String, onto: Maybe<&2, Lex.Tok>}# what the nearest let of the name appends onto; nothing when no let binds itdef find(lets: List<&2, Let>, +name: String) -> Maybe<&2, Lex.Tok>:  match lets:    case Nil{}:      None{}    case Con{Let{+nm, mm}, rest}:      Lazy.stop(Maybe<&2, Lex.Tok>, String.eq(nm, name), mm, _u => find(rest, name))# what the let of a lone name appends ontodef via.of(mm: Maybe<&2, Lex.Tok>, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:  match mm:    case None{}:      None{}    case Some{Lex.Tok{k, +t, l, c}}:      find(lets, t)# the name an argument appends onto, when it is a lone name read from a letdef via(aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:  via.of(lone(aa), lets)# the first maybe when it holds a token, else the seconddef either(aa: Maybe<&2, Lex.Tok>, bb: Maybe<&2, Lex.Tok>) -> Maybe<&2, Lex.Tok>:  match aa:    case None{}:      bb    case Some{tok}:      Some{tok}# the name an argument appends onto, in place or through a letdef seen(+aa: Tree.Node, +lets: List<&2, Let>) -> Maybe<&2, Lex.Tok>:  either(onto(aa), via(aa, lets))# an `=`def bound.eq(kk: Lex.TokKind) -> Bool:  match kk:    case Lex.TEq{}:      True{}    case other:      False{}# a name, then `=`, then the right side: the letdef bound.of(mm: Maybe<&2, Lex.Tok>, +h2: Tree.Node, rhs: Tree.Node) -> Maybe<&2, Let>:  match mm:    case None{}:      None{}    case Some{Lex.Tok{k, +t, l, c}}:      Lazy.stop(Maybe<&2, Let>, Bool.not(Calls.kind.leaf(~bound.eq, h2)), None{}, _u => Some{Let{t, onto(rhs)}})# a plain name, then `=`, then the right side: the letdef bound.named(+hh: Tree.Node, +h2: Tree.Node, rhs: Tree.Node) -> Maybe<&2, Let>:  bound.of(lone.name(hh), h2, rhs)# `+`, then a plain name, `=` and the right side: the letdef bound.plus(+h1: Tree.Node, +h2: Tree.Node, rest: Tree.Node) -> Maybe<&2, Let>:  match rest:    case Tree.NCons{h3, rhs}:      Lazy.stop(Maybe<&2, Let>, Bool.not(String.eq(Calls.leaf.text(h1), "+")), None{},        _u => bound.named(h2, h3, rhs))    case other:      None{}# the let a statement's own tokens make, when it binds one plain name with# `=`, bare or `+`def bound(kids: Tree.Node) -> Maybe<&2, Let>:  match kids:    case Tree.NCons{+h1, Tree.NCons{+h2, +rest}}:      Lazy.either(Maybe<&2, Let>, Calls.kind.leaf(~Calls.kind.oper, h1), _u => bound.plus(h1, h2, rest),        _v => bound.named(h1, h2, rest))    case other:      None{}# the lets in scope after one more, when there is onedef push(mm: Maybe<&2, Let>, +lets: List<&2, Let>) -> List<&2, Let>:  match mm:    case None{}:      lets    case Some{lt}:      lt <> lets# a finding when the name is the parameter of the argument's own slotdef hit(  mm: Maybe<&2, Lex.Tok>,  +slot: String,  +path: String,  +acc: List<&2, F.Finding>) -> List<&2, F.Finding>:  match mm:    case None{}:      acc    case Some{Lex.Tok{k, +t, l, c}}:      Bool.pick(List<&2, F.Finding>, String.eq(t, slot),        F.Finding{path, l, c, U32.from_nat(String.length(t)), "concat",          t ++ " is appended to on every step, which copies it each time and makes the loop quadratic; prepend and reverse once at the end, or build with <>."} <> acc,        acc)# the findings on a self-call's arguments, each against the parameter in its# position (params, from the argument's own slot on)def hits(  as: List<&2, Tree.Node>,  +params: List<&2, String>,  +lets: List<&2, Let>,  +path: String,  acc: List<&2, F.Finding>) -> List<&2, F.Finding>:  match as:    case Nil{}:      List.reverse(&2, F.Finding, acc)    case Con{+a, rest}:      +slot = Maybe.default(&2, String, List.head(&2, String, params), "")      hits(rest, List.tail(&2, String, params), lets, path, hit(seen(a, lets), slot, path, acc))# the lets a statement leaves in scope for the statements after itdef after(kind: Tree.StmtKind, +kids: Tree.Node, +lets: List<&2, Let>) -> List<&2, Let>:  match kind:    case Tree.SLet{}:      push(bound(kids), lets)    case other:      lets# every self-call's arguments, with the lets in scopedef walk(  nn: Tree.Node,  +name: String,  +params: List<&2, String>,  +lets: List<&2, Let>,  +path: String) -> List<&2, F.Finding>:  match nn:    case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:      +me = Bool.and(String.eq(o, "("), String.eq(t, name))      List.concat(&2, F.Finding, [        Lazy.stop(List<&2, F.Finding>, Bool.not(me), [], _u => hits(Calls.args(kids), params, lets, path, [])),        walk(kids, name, params, lets, path), walk(rest, name, params, lets, path)])    case Tree.NCons{Tree.Group{open, kids, close}, rest}:      List.concat(&2, F.Finding, [walk(kids, name, params, lets, path), walk(rest, name, params, lets, path)])    case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:      List.concat(&2, F.Finding, [walk(kids, name, params, lets, path), walk(body, name, params, lets, path),        walk(rest, name, params, after(kind, kids, lets), path)])    case Tree.NCons{h, rest}:      walk(rest, name, params, lets, path)    case other:      Nil{}def check.go(ds: List<&2, Calls.Def>, +path: String, acc: List<&2, List<&2, F.Finding>>) -> List<&2, F.Finding>:  match ds:    case Nil{}:      List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))    case Con{Calls.Def{+name, +sig, body}, rest}:      check.go(rest, path,        Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],          _u => walk(body, name, Calls.names(sig), [], path)) <> acc)# the ruledef check(ss: Src.Src) -> List<&2, F.Finding>:  Src.Src{path, text, toks, tree, bound, items} = ss  check.go(Calls.defs(tree), path, [])