src/rules/suspicious/rewalk.bend
bolt@1.18.0.0 · 905 lines · 0 definitions
1# rule rewalk: one straight piece of a def calls the same walk twice on the
2# same argument, and one result is used only for a single value (a get of one
3# index, one field, or a let whose name is only read that way) while the other
4# result is kept whole. Take the value from that other result. The same
5# argument is the same text with no let of any name it uses (`=` or `<-`,
6# taking effect at the end of the let) between the two calls. A different
7# case arm is a different path, and two narrow reads are left alone. A walk is
8# a def of this file that loops, or a Base walk (`List.map` and the like).
9# Laws and proofs do not run (a def with no type at all fills a law: it is a
10# proof). This is not `twice`, which is duplicate literals in a list pattern.
11import Base
12import bolt@1.18.0.0/src/src.bend as Src
13import bolt@1.18.0.0/src/finding.bend as F
14import bolt@1.18.0.0/src/syntax/lex.bend as Lex
15import bolt@1.18.0.0/src/syntax/tree.bend as Tree
16import bolt@1.18.0.0/src/rules/calls.bend as Calls
17import bolt@1.18.0.0/src/lazy/lazy.bend as Lazy
18
19# how the result of a call is used
20type How is Data:
21 HWide{}
22 HSlot{}
23 HLet{binder: String}
24 HField{}
25
26# one expensive call
27type Site is Data:
28 Site{name: String, args: String, line: U32, col: U32, len: U32, how: How}
29
30# a narrow read and a wide read of one name
31type Hit is Data:
32 Hit{wide: Bool, slot: Bool}
33
34# where an accessor reads its collection
35type Slot is Data:
36 Slot{on: Bool, at: Nat}
37
38# a position a mark pass recorded
39type Pos is Data:
40 Pos{line: U32, col: U32}
41
42# the left of `=` : one name, and whether a group makes it a field
43type Lhs is Data:
44 Lhs{seen: Bool, extra: Bool, field: Bool, nm: String}
45
46# a let of one name, and where it takes effect
47type Bind is Data:
48 Bind{nm: String, line: U32, col: U32}
49
50# a let whose right-hand side is one call
51type Note is Data:
52 Note{line: U32, col: U32, how: How}
53
54# neither read
55def none_hit() -> Hit:
56 Hit{False{}, False{}}
57
58# either read from two results
59def either(aa: Hit, +bb: Hit) -> Hit:
60 Hit{+w1, +s1} = aa
61 Hit{+w2, +s2} = bb
62 Hit{Bool.or(w1, w2), Bool.or(s1, s2)}
63
64# a mention of the name: wide, unless this position is a narrow slot
65def name_slot(+slot: Bool) -> Hit:
66 match slot:
67 case True{}:
68 Hit{False{}, True{}}
69 case False{}:
70 Hit{True{}, False{}}
71
72# a mention of the name, or nothing when it is a different name
73def name_hit(+same: Bool, +slot: Bool) -> Hit:
74 match same:
75 case False{}:
76 none_hit()
77 case True{}:
78 name_slot(slot)
79
80# which argument a narrow accessor reads
81def slot_pick(+list: Bool, +str: Bool, +arr: Bool) -> Slot:
82 match list str arr:
83 case True{} b c:
84 Slot{True{}, 2n}
85 case False{} True{} c:
86 Slot{True{}, 0n}
87 case False{} False{} True{}:
88 Slot{True{}, 1n}
89 case False{} False{} False{}:
90 Slot{False{}, 0n}
91
92# List.get / head / last / length, String.get / length, Array.get; not List.set
93def slot_of(+tt: String) -> Slot:
94 slot_pick(
95 List.contains(~String, ~String.eq, ["List.get", "List.head", "List.last", "List.length"], tt),
96 Bool.or(String.eq(tt, "String.get"), String.eq(tt, "String.length")),
97 String.eq(tt, "Array.get"))
98
99# after a comma, still inside the slot argument?
100def step_is_zero(pp: Nat) -> Bool:
101 match pp:
102 case 0n:
103 True{}
104 case 1n+k:
105 False{}
106
107# after a comma, is the next argument the slot?
108def step_hot_live(left: Nat) -> Bool:
109 match left:
110 case 0n:
111 False{}
112 case 1n+p:
113 step_is_zero(p)
114
115# the slot flag after a comma
116def step_hot(+hot: Bool, +left: Nat, +live: Bool) -> Bool:
117 match live:
118 case False{}:
119 hot
120 case True{}:
121 step_hot_live(left)
122
123# the arguments still to skip after a comma
124def step_left_live(left: Nat) -> Nat:
125 match left:
126 case 0n:
127 0n
128 case 1n+p:
129 p
130
131# the arguments still to skip after a comma
132def step_left(+left: Nat, +live: Bool) -> Nat:
133 match live:
134 case False{}:
135 left
136 case True{}:
137 step_left_live(left)
138
139# the chain is exactly one call
140def as_open(+open: Bool, tok: Lex.Tok) -> Maybe<&2, Lex.Tok>:
141 match open:
142 case True{}:
143 Some{tok}
144 case False{}:
145 None{}
146
147# the inside of one pair of parentheses, when it is exactly a call
148def as_inside(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
149 match nn:
150 case Tree.NCons{Tree.Leaf{tok}, Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, kids, close}, Tree.NNil{}}}:
151 as_open(String.eq(o, "("), tok)
152 case other:
153 None{}
154
155# a parenthesized call, or nothing
156def as_wrapped(+paren: Bool, kids: Tree.Node) -> Maybe<&2, Lex.Tok>:
157 match paren:
158 case True{}:
159 as_inside(kids)
160 case False{}:
161 None{}
162
163# the chain is exactly one call, or one pair of parentheses around one: its callee
164def as_call(nn: Tree.Node) -> Maybe<&2, Lex.Tok>:
165 match nn:
166 case Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, +kids, close}, Tree.NNil{}}:
167 as_wrapped(String.eq(o, "("), kids)
168 case Tree.NCons{Tree.Leaf{tok}, Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, kids, close}, Tree.NNil{}}}:
169 as_open(String.eq(o, "("), tok)
170 case other:
171 None{}
172
173# the callee, when this argument is exactly a call
174def pos_of(mm: Maybe<&2, Lex.Tok>) -> List<&2, Pos>:
175 match mm:
176 case None{}:
177 Nil{}
178 case Some{Lex.Tok{k, t, l, c}}:
179 [Pos{l, c}]
180
181# the collection argument's call, when this is a narrow accessor
182def mark_slot(ss: Slot, +as: List<&2, Tree.Node>) -> List<&2, Pos>:
183 Slot{on, at} = ss
184 match on:
185 case False{}:
186 Nil{}
187 case True{}:
188 pos_of(as_call(Calls.arg(as, at)))
189
190# calls that sit in a narrow accessor's collection argument
191def mark(nn: Tree.Node) -> List<&2, Pos>:
192 match nn:
193 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
194 +here = Lazy.stop(List<&2, Pos>, Bool.not(String.eq(o, "(")), [], _u => mark_slot(slot_of(t), Calls.args(kids)))
195 List.concat(&2, Pos, [here, mark(kids), mark(rest)])
196 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
197 List.concat(&2, Pos, [mark(kids), mark(rest)])
198 case Tree.NCons{Tree.Stmt{Tree.SCase{}, +kids, body}, rest}:
199 List.concat(&2, Pos, [mark(kids), mark(rest)])
200 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
201 List.concat(&2, Pos, [mark(kids), mark(body), mark(rest)])
202 case Tree.NCons{h, rest}:
203 mark(rest)
204 case other:
205 Nil{}
206
207# the name before a group is a narrow read, a callee, or an ordinary mention
208def here_call(+call: Bool, +tt: String, +name: String, +hot: Bool) -> Hit:
209 match call:
210 case True{}:
211 name_hit(String.eq(tt, name), False{})
212 case False{}:
213 name_hit(String.eq(tt, name), hot)
214
215# the name before a group is a narrow read, a callee, or an ordinary mention
216def here_hit(+brack: Bool, +call: Bool, +tt: String, +name: String, +hot: Bool) -> Hit:
217 match brack:
218 case True{}:
219 name_hit(String.eq(tt, name), True{})
220 case False{}:
221 here_call(call, tt, name, hot)
222
223# a bracket's inside is cold; a call's arguments start before the slot
224def inner_hot_call(+call: Bool, +hot: Bool) -> Bool:
225 match call:
226 case True{}:
227 False{}
228 case False{}:
229 hot
230
231# a bracket's inside is cold; a call's arguments start before the slot
232def inner_hot(+brack: Bool, +call: Bool, +hot: Bool) -> Bool:
233 match brack:
234 case True{}:
235 False{}
236 case False{}:
237 inner_hot_call(call, hot)
238
239# the argument index a slot reads
240def slot_at(ss: Slot) -> Nat:
241 Slot{on, at} = ss
242 at
243
244# the slot index of a call; a bracket has none
245def inner_left_call(+call: Bool, +tt: String) -> Nat:
246 match call:
247 case True{}:
248 slot_at(slot_of(tt))
249 case False{}:
250 0n
251
252# the slot index of a call; a bracket has none
253def inner_left(+brack: Bool, +call: Bool, +tt: String) -> Nat:
254 match brack:
255 case True{}:
256 0n
257 case False{}:
258 inner_left_call(call, tt)
259
260# whether an accessor has a collection argument
261def slot_on(ss: Slot) -> Bool:
262 Slot{on, at} = ss
263 on
264
265# only a call's arguments count commas as separators
266def inner_live_call(+call: Bool, +tt: String) -> Bool:
267 match call:
268 case True{}:
269 slot_on(slot_of(tt))
270 case False{}:
271 False{}
272
273# only a call's arguments count commas as separators
274def inner_live(+brack: Bool, +call: Bool, +tt: String) -> Bool:
275 match brack:
276 case True{}:
277 False{}
278 case False{}:
279 inner_live_call(call, tt)
280
281# does the chain bind?
282def has_eq(nn: Tree.Node) -> Bool:
283 match nn:
284 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
285 True{}
286 case Tree.NCons{h, rest}:
287 has_eq(rest)
288 case other:
289 False{}
290
291# a read counts only once the left of `=` is over
292def hit_keep(skip: Bool, hh: Hit) -> Hit:
293 match skip:
294 case True{}:
295 none_hit()
296 case False{}:
297 hh
298
299# inside a call, unless this chain is still the left of a let
300def pick_hot(+skip: Bool, +brack: Bool, +call: Bool, +hot: Bool) -> Bool:
301 match skip:
302 case True{}:
303 False{}
304 case False{}:
305 inner_hot(brack, call, hot)
306
307# inside a call, unless this chain is still the left of a let
308def pick_left(+skip: Bool, +brack: Bool, +call: Bool, +tt: String) -> Nat:
309 match skip:
310 case True{}:
311 0n
312 case False{}:
313 inner_left(brack, call, tt)
314
315# inside a call, unless this chain is still the left of a let
316def pick_live(+skip: Bool, +brack: Bool, +call: Bool, +tt: String) -> Bool:
317 match skip:
318 case True{}:
319 False{}
320 case False{}:
321 inner_live(brack, call, tt)
322
323# reads of the name. hot: this chain is a collection argument. live/left: commas
324# count toward that argument. skip: ignore names until `=` (the left of a let)
325def hits(nn: Tree.Node, +name: String, +hot: Bool, +left: Nat, +live: Bool, +skip: Bool) -> Hit:
326 match nn:
327 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
328 hits(rest, name, hot, left, live, False{})
329 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TComma{}, t, l, c}}, rest}:
330 hits(rest, name, step_hot(hot, left, live), step_left(left, live), live, skip)
331 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
332 +brack = String.eq(o, "[")
333 +call = String.eq(o, "(")
334 +here = hit_keep(skip, here_hit(brack, call, t, name, hot))
335 +inn = hits(kids, name, pick_hot(skip, brack, call, hot), pick_left(skip, brack, call, t),
336 pick_live(skip, brack, call, t), skip)
337 +aft = hits(rest, name, hot, left, live, skip)
338 either(here, either(inn, aft))
339 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
340 either(hit_keep(skip, name_hit(String.eq(t, name), hot)), hits(rest, name, hot, left, live, skip))
341 case Tree.NCons{Tree.Leaf{tok}, rest}:
342 hits(rest, name, hot, left, live, skip)
343 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
344 either(hits(kids, name, hot, 0n, False{}, skip), hits(rest, name, hot, left, live, skip))
345 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
346 +eq = has_eq(kids)
347 +inn = hits(kids, name, False{}, 0n, False{}, eq)
348 +bod = hits(body, name, False{}, 0n, False{}, False{})
349 +aft = hits(rest, name, hot, left, live, skip)
350 either(inn, either(bod, aft))
351 case Tree.NCons{h, rest}:
352 hits(rest, name, hot, left, live, skip)
353 case other:
354 none_hit()
355
356# a let of one name is narrow when that name is only read narrowly
357def narrow_let(hh: Hit) -> Bool:
358 Hit{wide, slot} = hh
359 Bool.and(slot, Bool.not(wide))
360
361# a slot or a field is narrow; a wide use is not; a let depends on the name's reads
362def narrow(hh: How, +body: Tree.Node) -> Bool:
363 match hh:
364 case HWide{}:
365 False{}
366 case HSlot{}:
367 True{}
368 case HField{}:
369 True{}
370 case HLet{+binder}:
371 narrow_let(hits(body, binder, False{}, 0n, False{}, False{}))
372
373# every name a node calls
374def called(nn: Tree.Node) -> List<&2, String>:
375 match nn:
376 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, l, c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, rest}}:
377 +more = List.concat(&2, String, [called(kids), called(rest)])
378 Bool.pick(List<&2, String>, String.eq(o, "("), t <> more, more)
379 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
380 List.concat(&2, String, [called(kids), called(rest)])
381 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
382 List.concat(&2, String, [called(kids), called(body), called(rest)])
383 case Tree.NCons{h, rest}:
384 called(rest)
385 case other:
386 Nil{}
387
388# does the list hold a name the set has?
389def any_of(cs: List<&2, String>, +set: List<&2, String>) -> Bool:
390 match cs:
391 case Nil{}:
392 False{}
393 case Con{c, t}:
394 Lazy.or_else(List.contains(~String, ~String.eq, set, c), _u => any_of(t, set))
395
396def loops.go(ds: List<&2, Calls.Def>, +acc: List<&2, String>) -> List<&2, String>:
397 match ds:
398 case Nil{}:
399 acc
400 case Con{Calls.Def{+name, sig, body}, rest}:
401 +cs = called(body)
402 +deep = Bool.or(List.contains(~String, ~String.eq, cs, name), any_of(cs, acc))
403 loops.go(rest, Bool.pick(List<&2, String>, deep, name <> acc, acc))
404
405# defs of this file that loop
406def loops(ds: List<&2, Calls.Def>) -> List<&2, String>:
407 loops.go(ds, [])
408
409# Base walks a rewalk cares about
410def heavy(+tt: String) -> Bool:
411 List.contains(~String, ~String.eq, [
412 "List.map", "List.filter", "List.sort", "List.foldl", "List.foldr", "List.reverse", "List.concat",
413 "Array.map", "Array.to_list",
414 "String.reverse", "String.to_upper", "String.to_lower", "String.to_list", "String.from_list"], tt)
415
416# a loop of this file, or a Base walk, and not this def itself
417def expensive(+tt: String, +self: String, +lp: List<&2, String>) -> Bool:
418 Bool.and(Bool.not(String.eq(tt, self)), Bool.or(heavy(tt), List.contains(~String, ~String.eq, lp, tt)))
419
420# the rest of the chain indexes the call
421def indexed(rest: Tree.Node) -> Bool:
422 match rest:
423 case Tree.NCons{Tree.Group{Lex.Tok{k, +o, l, c}, kids, close}, tail}:
424 String.eq(o, "[")
425 case other:
426 False{}
427
428# a slot when the call is indexed, otherwise wide, when the call is expensive
429def how_of(+nar: Bool) -> How:
430 match nar:
431 case True{}:
432 HSlot{}
433 case False{}:
434 HWide{}
435
436# a slot when the call is indexed, otherwise wide, when the call is expensive
437def site_how(+mine: Bool, +nar: Bool) -> Maybe<&2, How>:
438 match mine:
439 case False{}:
440 None{}
441 case True{}:
442 Some{how_of(nar)}
443
444# the call as a site, when it is one
445def site_list(mm: Maybe<&2, How>, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> List<&2, Site>:
446 match mm:
447 case None{}:
448 Nil{}
449 case Some{how}:
450 [Site{name, args, line, col, len, how}]
451
452# one site when this application is an expensive call
453def open_site(
454 +open: Bool,
455 +indexed: Bool,
456 +tt: String,
457 +args: String,
458 +line: U32,
459 +col: U32,
460 +len: U32,
461 +self: String,
462 +lp: List<&2, String>
463) -> List<&2, Site>:
464 match open:
465 case False{}:
466 Nil{}
467 case True{}:
468 site_list(site_how(expensive(tt, self, lp), indexed), tt, args, line, col, len)
469
470# every name under the node
471def names(nn: Tree.Node, +acc: List<&2, String>) -> List<&2, String>:
472 match nn:
473 case Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}:
474 t <> acc
475 case Tree.Group{open, kids, close}:
476 names(kids, acc)
477 case Tree.Stmt{kind, kids, body}:
478 names(body, names(kids, acc))
479 case Tree.NCons{h, rest}:
480 names(rest, names(h, acc))
481 case other:
482 acc
483
484# the names a let binds: every name left of its `=` or `<-`
485def lhs_names(nn: Tree.Node, +acc: List<&2, String>) -> List<&2, String>:
486 match nn:
487 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
488 acc
489 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TBind{}, t, l, c}}, rest}:
490 acc
491 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
492 lhs_names(rest, t <> acc)
493 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
494 lhs_names(rest, names(kids, acc))
495 case Tree.NCons{h, rest}:
496 lhs_names(rest, acc)
497 case other:
498 acc
499
500# where a let's names take effect: its last token, after the right-hand side
501def last_pos(ts: List<&2, Lex.Tok>) -> Pos:
502 match ts:
503 case Nil{}:
504 Pos{0, 0}
505 case Con{Lex.Tok{k, t, +l, +c}, rest}:
506 Pos{l, c}
507
508# one binding per name, at the let's end
509def bind_all(ns: List<&2, String>, +line: U32, +col: U32, +acc: List<&2, Bind>) -> List<&2, Bind>:
510 match ns:
511 case Nil{}:
512 acc
513 case Con{+nm, rest}:
514 bind_all(rest, line, col, Bind{nm, line, col} <> acc)
515
516# one binding per name, at this position
517def bind_at(ns: List<&2, String>, pp: Pos, +acc: List<&2, Bind>) -> List<&2, Bind>:
518 Pos{line, col} = pp
519 bind_all(ns, line, col, acc)
520
521# the lets of one straight piece; a case arm is not part of it
522def binds(nn: Tree.Node, +acc: List<&2, Bind>) -> List<&2, Bind>:
523 match nn:
524 case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, body}, rest}:
525 binds(rest, acc)
526 case Tree.NCons{Tree.Stmt{Tree.SLet{}, +kids, +body}, rest}:
527 +here = bind_at(lhs_names(kids, []), last_pos(Tree.leaves.go(body, Tree.leaves.go(kids, []))), acc)
528 binds(rest, binds(body, here))
529 case Tree.NCons{Tree.Stmt{kind, kids, +body}, rest}:
530 binds(rest, binds(body, acc))
531 case Tree.NCons{h, rest}:
532 binds(rest, acc)
533 case other:
534 acc
535
536# (l1, c1) comes before (l2, c2)
537def before(+l1: U32, +c1: U32, +l2: U32, +c2: U32) -> Bool:
538 Bool.or(U32.is_lt(l1, l2), Bool.and(U32.is_eq(l1, l2), U32.is_lt(c1, c2)))
539
540# how many lets of this name take effect before this position
541def count(bs: List<&2, Bind>, +name: String, +line: U32, +col: U32) -> U32:
542 match bs:
543 case Nil{}:
544 0
545 case Con{Bind{+nm, +l, +c}, rest}:
546 +more = count(rest, name, line, col)
547 Bool.pick(U32, Bool.and(String.eq(nm, name), before(l, c, line, col)), (more + 1 : U32), more)
548
549# which binding of each name an argument reads: two calls with the same text
550# read the same values only when no let of those names sits between them
551def stamp(ns: List<&2, String>, +bs: List<&2, Bind>, +line: U32, +col: U32) -> String:
552 match ns:
553 case Nil{}:
554 ""
555 case Con{+nm, rest}:
556 "|" ++ nm ++ "=" ++ U32.show(count(bs, nm, line, col)) ++ stamp(rest, bs, line, col)
557
558# every expensive call, wide unless the call is indexed on the spot; its
559# arguments are their text and which let of each name they read
560def gather(nn: Tree.Node, +self: String, +lp: List<&2, String>, +bs: List<&2, Bind>) -> List<&2, Site>:
561 match nn:
562 case Tree.NCons{Tree.Leaf{Lex.Tok{k, +t, +l, +c}}, Tree.NCons{Tree.Group{Lex.Tok{_, +o, _, _}, +kids, _}, +rest}}:
563 +args = Tree.show(kids) ++ stamp(names(kids, []), bs, l, c)
564 +here = open_site(String.eq(o, "("), indexed(rest), t, args, l, c,
565 U32.from_nat(String.length(t)), self, lp)
566 List.concat(&2, Site, [here, gather(kids, self, lp, bs), gather(rest, self, lp, bs)])
567 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
568 List.concat(&2, Site, [gather(kids, self, lp, bs), gather(rest, self, lp, bs)])
569 case Tree.NCons{Tree.Stmt{Tree.SCase{}, +kids, body}, rest}:
570 List.concat(&2, Site, [gather(kids, self, lp, bs), gather(rest, self, lp, bs)])
571 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
572 List.concat(&2, Site, [gather(kids, self, lp, bs), gather(body, self, lp, bs), gather(rest, self, lp, bs)])
573 case Tree.NCons{h, rest}:
574 gather(rest, self, lp, bs)
575 case other:
576 Nil{}
577
578# a second name on the left
579def add_seen(+seen: Bool, +extra: Bool, +field: Bool, +nm: String, +tt: String) -> Lhs:
580 match seen:
581 case False{}:
582 Lhs{True{}, extra, field, tt}
583 case True{}:
584 Lhs{True{}, True{}, field, nm}
585
586# names inside a field group, which makes the let a field read
587def fold_names(nn: Tree.Node, st: Lhs) -> Lhs:
588 match nn:
589 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
590 Lhs{seen, extra, field, nm} = st
591 fold_names(rest, add_seen(seen, extra, True{}, nm, t))
592 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
593 fold_names(rest, fold_names(kids, st))
594 case Tree.NCons{h, rest}:
595 fold_names(rest, st)
596 case other:
597 st
598
599# the left of `=`
600def eat(nn: Tree.Node, st: Lhs) -> Lhs:
601 match nn:
602 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
603 st
604 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TName{}, +t, l, c}}, rest}:
605 Lhs{seen, extra, field, nm} = st
606 eat(rest, add_seen(seen, extra, field, nm, t))
607 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
608 eat(rest, fold_names(kids, st))
609 case Tree.NCons{h, rest}:
610 eat(rest, st)
611 case other:
612 st
613
614# a field when the left has a group, otherwise a let of that name
615def note_how(+field: Bool, +nm: String) -> How:
616 match field:
617 case True{}:
618 HField{}
619 case False{}:
620 HLet{nm}
621
622# nothing, and the maybe is consumed
623def note_none(mm: Maybe<&2, Lex.Tok>) -> Maybe<&2, Note>:
624 match mm:
625 case other:
626 None{}
627
628# the note when the right-hand side is a call
629def note_some(+field: Bool, +nm: String, mm: Maybe<&2, Lex.Tok>) -> Maybe<&2, Note>:
630 match mm:
631 case Some{Lex.Tok{k, t, l, c}}:
632 Some{Note{l, c, note_how(field, nm)}}
633 case None{}:
634 None{}
635
636# the note for a call, when the left is exactly one name
637def note_rhs(+one: Bool, +field: Bool, +nm: String, mm: Maybe<&2, Lex.Tok>) -> Maybe<&2, Note>:
638 match one:
639 case False{}:
640 note_none(mm)
641 case True{}:
642 note_some(field, nm, mm)
643
644# the tokens after `=`
645def rhs_of(nn: Tree.Node) -> Tree.Node:
646 match nn:
647 case Tree.NCons{Tree.Leaf{Lex.Tok{Lex.TEq{}, t, l, c}}, rest}:
648 rest
649 case Tree.NCons{h, rest}:
650 rhs_of(rest)
651 case other:
652 Tree.NNil{}
653
654# a let or a field binding of exactly one call
655def note_from(st: Lhs, +rhs: Tree.Node) -> Maybe<&2, Note>:
656 Lhs{seen, extra, field, +nm} = st
657 note_rhs(Bool.and(seen, Bool.not(extra)), field, nm, as_call(rhs))
658
659# a let or a field binding of exactly one call
660def note_st(+kids: Tree.Node) -> Maybe<&2, Note>:
661 note_from(eat(kids, Lhs{False{}, False{}, False{}, ""}), rhs_of(kids))
662
663# one site, retagged when it is the let's call
664def retag_one(+hit: Bool, how: How, +note: How, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> Site:
665 match hit:
666 case True{}:
667 Site{name, args, line, col, len, note}
668 case False{}:
669 Site{name, args, line, col, len, how}
670
671# a note's line
672def note_line(nn: Note) -> U32:
673 Note{line, col, how} = nn
674 line
675
676# a note's column
677def note_col(nn: Note) -> U32:
678 Note{line, col, how} = nn
679 col
680
681# a note's how
682def note_how_of(nn: Note) -> How:
683 Note{line, col, how} = nn
684 how
685
686# sites whose callee is this let's call take its how
687def retag(sites: List<&2, Site>, +note: Note) -> List<&2, Site>:
688 match sites:
689 case Nil{}:
690 Nil{}
691 case Con{Site{+name, +args, +line, +col, +len, how}, rest}:
692 +nl = note_line(note)
693 +nc = note_col(note)
694 +nh = note_how_of(note)
695 +hit = Bool.and(U32.is_eq(line, nl), U32.is_eq(col, nc))
696 retag_one(hit, how, nh, name, args, line, col, len) <> retag(rest, note)
697
698# retag when the statement is a let of a call
699def retag_may(mm: Maybe<&2, Note>, sites: List<&2, Site>) -> List<&2, Site>:
700 match mm:
701 case None{}:
702 sites
703 case Some{note}:
704 retag(sites, note)
705
706# lets of a call retag that call
707def apply(nn: Tree.Node, sites: List<&2, Site>) -> List<&2, Site>:
708 match nn:
709 case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, body}, rest}:
710 apply(rest, sites)
711 case Tree.NCons{Tree.Stmt{kind, +kids, body}, rest}:
712 apply(rest, apply(body, retag_may(note_st(kids), sites)))
713 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
714 apply(rest, apply(kids, sites))
715 case Tree.NCons{h, rest}:
716 apply(rest, sites)
717 case other:
718 sites
719
720# this position was marked a collection argument
721def pinned(+line: U32, +col: U32, ps: List<&2, Pos>) -> Bool:
722 match ps:
723 case Nil{}:
724 False{}
725 case Con{Pos{l, c}, rest}:
726 +here = Bool.and(U32.is_eq(l, line), U32.is_eq(c, col))
727 +more = pinned(line, col, rest)
728 Bool.or(here, more)
729
730# a wide call at a marked position becomes a slot; a let or a field stays
731def pin_wide(how: How, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> Site:
732 match how:
733 case HWide{}:
734 Site{name, args, line, col, len, HSlot{}}
735 case other:
736 Site{name, args, line, col, len, other}
737
738# a wide call at a marked position becomes a slot
739def pin_how(+hit: Bool, how: How, +name: String, +args: String, +line: U32, +col: U32, +len: U32) -> Site:
740 match hit:
741 case False{}:
742 Site{name, args, line, col, len, how}
743 case True{}:
744 pin_wide(how, name, args, line, col, len)
745
746# one site
747def pin_one(ps: List<&2, Pos>, ss: Site) -> Site:
748 Site{+name, +args, +line, +col, +len, how} = ss
749 pin_how(pinned(line, col, ps), how, name, args, line, col, len)
750
751# marked collection arguments become slots
752def pin(+ps: List<&2, Pos>, sites: List<&2, Site>) -> List<&2, Site>:
753 match sites:
754 case Nil{}:
755 Nil{}
756 case Con{s, rest}:
757 pin_one(ps, s) <> pin(ps, rest)
758
759# a site, with whether its result is read for a single value over the piece
760type Rated is Data:
761 Rated{site: Site, nar: Bool}
762
763# one site, rated: the piece is walked for it here, once
764def rate_one(ss: Site, +body: Tree.Node) -> Rated:
765 Site{+name, +args, +line, +col, +len, +how} = ss
766 Rated{Site{name, args, line, col, len, how}, narrow(how, body)}
767
768# each site, rated once, so the reports below compare ratings and never walk
769# the piece again: a walk per site, not one per pair of sites
770def rate(sites: List<&2, Site>, +body: Tree.Node) -> List<&2, Rated>:
771 match sites:
772 case Nil{}:
773 Nil{}
774 case Con{s, rest}:
775 rate_one(s, body) <> rate(rest, body)
776
777# another site has the same callee and the same arguments, and keeps the whole result
778def other_go(rs: List<&2, Rated>, +name: String, +args: String, +line: U32, +col: U32) -> Bool:
779 match rs:
780 case Nil{}:
781 False{}
782 case Con{Rated{Site{+nm, +as, +l, +c, len, how}, +nar}, rest}:
783 +same = Bool.and(String.eq(nm, name), String.eq(as, args))
784 +diff = Bool.not(Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)))
785 +here = Bool.and(Bool.and(same, diff), Bool.not(nar))
786 +more = other_go(rest, name, args, line, col)
787 Bool.or(here, more)
788
789# a narrow site of this call already reported
790def earlier(seen: List<&2, Rated>, +name: String, +args: String, +line: U32, +col: U32) -> Bool:
791 match seen:
792 case Nil{}:
793 False{}
794 case Con{Rated{Site{+nm, +as, +l, +c, len, how}, +nar}, rest}:
795 +same = Bool.and(String.eq(nm, name), String.eq(as, args))
796 +diff = Bool.not(Bool.and(U32.is_eq(l, line), U32.is_eq(c, col)))
797 +here = Bool.and(Bool.and(same, diff), nar)
798 +more = earlier(rest, name, args, line, col)
799 Bool.or(here, more)
800
801# the finding when no earlier narrow site took this call
802def report_fresh(
803 +prior: Bool,
804 +name: String,
805 +line: U32,
806 +col: U32,
807 +len: U32,
808 +path: String
809) -> List<&2, F.Finding>:
810 match prior:
811 case False{}:
812 [F.Finding{path, line, col, len, "rewalk",
813 name ++ " is called twice on the same argument, and one result is used only for a single value; take that value from the other result."}]
814 case True{}:
815 Nil{}
816
817# the finding, when this is the first narrow site of a duplicated call
818def report_nar(
819 +nar: Bool,
820 +prior: Bool,
821 +name: String,
822 +line: U32,
823 +col: U32,
824 +len: U32,
825 +path: String
826) -> List<&2, F.Finding>:
827 match nar:
828 case False{}:
829 Nil{}
830 case True{}:
831 report_fresh(prior, name, line, col, len, path)
832
833# the finding when a duplicate exists and this site is the first narrow one
834def report_dup(
835 +dup: Bool,
836 +nar: Bool,
837 +name: String,
838 +args: String,
839 +line: U32,
840 +col: U32,
841 +len: U32,
842 +path: String,
843 +seen: List<&2, Rated>
844) -> List<&2, F.Finding>:
845 match dup:
846 case False{}:
847 Nil{}
848 case True{}:
849 report_nar(nar, earlier(seen, name, args, line, col), name, line, col, len, path)
850
851# one site
852def report_one(rr: Rated, +all: List<&2, Rated>, +path: String, +seen: List<&2, Rated>) -> List<&2, F.Finding>:
853 Rated{ss, +nar} = rr
854 Site{+name, +args, +line, +col, +len, how} = ss
855 report_dup(other_go(all, name, args, line, col), nar, name, args, line, col, len, path, seen)
856
857# the first narrow site of each duplicated call
858def report(rs: List<&2, Rated>, +all: List<&2, Rated>, +path: String, +seen: List<&2, Rated>) -> List<&2, F.Finding>:
859 match rs:
860 case Nil{}:
861 Nil{}
862 case Con{+r, rest}:
863 +mine = report_one(r, all, path, seen)
864 List.append(&2, F.Finding, mine, report(rest, all, path, r <> seen))
865
866# findings in one straight region; a case arm is not part of it
867def local(+nn: Tree.Node, +self: String, +lp: List<&2, String>, +path: String) -> List<&2, F.Finding>:
868 +rs = rate(pin(mark(nn), apply(nn, gather(nn, self, lp, binds(nn, [])))), nn)
869 report(rs, rs, path, [])
870
871# each case arm on its own, so two arms are not one path
872def visit(nn: Tree.Node, +self: String, +lp: List<&2, String>, +path: String) -> List<&2, F.Finding>:
873 match nn:
874 case Tree.NCons{Tree.Stmt{Tree.SCase{}, kids, +body}, rest}:
875 +here = local(body, self, lp, path)
876 List.concat(&2, F.Finding, [here, visit(body, self, lp, path), visit(rest, self, lp, path)])
877 case Tree.NCons{Tree.Stmt{kind, +kids, +body}, rest}:
878 List.concat(&2, F.Finding, [visit(kids, self, lp, path), visit(body, self, lp, path),
879 visit(rest, self, lp, path)])
880 case Tree.NCons{Tree.Group{open, +kids, close}, rest}:
881 List.concat(&2, F.Finding, [visit(kids, self, lp, path), visit(rest, self, lp, path)])
882 case Tree.NCons{h, rest}:
883 visit(rest, self, lp, path)
884 case other:
885 Nil{}
886
887def check.go(
888 ds: List<&2, Calls.Def>,
889 +lp: List<&2, String>,
890 +path: String,
891 acc: List<&2, List<&2, F.Finding>>
892) -> List<&2, F.Finding>:
893 match ds:
894 case Nil{}:
895 List.concat(&2, F.Finding, List.reverse(&2, List<&2, F.Finding>, acc))
896 case Con{Calls.Def{+name, +sig, +body}, rest}:
897 check.go(rest, lp, path,
898 Lazy.stop(List<&2, F.Finding>, Calls.exempt(path, sig), [],
899 _u => List.concat(&2, F.Finding, [local(body, name, lp, path), visit(body, name, lp, path)])) <> acc)
900
901# the rule
902def check(ss: Src.Src) -> List<&2, F.Finding>:
903 Src.Src{path, text, toks, tree, bound, items} = ss
904 +ds = Calls.defs(tree)
905 check.go(ds, loops(ds), path, [])