1	# performance/template_value_field: a value field of a record of functions that reads a template whose type is a
2	# record of functions. Bend writes a template where it is used, so a record of functions passed as one is built
3	# again at each use; a field that is not a function is computed then, and reading the template builds its whole
4	# record, closures too, to read a part of it, then frees the rest.
5	# Heuristics: measured on a combinator of two records of functions, nested 6 deep and run 2M times: 1.7 s with a
6	# count as a value field, against 1.0 s with the count under a lambda (`u => ..`), on the C lane (one thread), and
7	# 49 s against 14 s on the JS lane, with the same output; issue #2 measured 6% more time on a nested model, and
8	# nothing on a shallow one, as the cost doubles with each level. The lambda moves the work to each read: with the
9	# count read on every step too, it took 2.4 s against 1.9 s. A record of functions is a datatype of the program
10	# with a field whose written type is a function; a record that the rule judges is built in live code, outside a
11	# lambda, with a lambda among its fields: a record of values only is a result, built once. A template of another
12	# type (a number, a function, a list) builds no record of closures, and is not judged. A use in a type, or under a
13	# lambda, does not run when the record is built.
14	import Base
15	import bend-lint-api@0.1.1.0/linter/lint.bend as Lint
16	import bend-lint-api@0.1.1.0/shared/lists.bend as Lists
17	
18	# Types
19	# =====
20	
21	# What judging the uses of one definition's templates reads: the binders of its templates whose type is a record of
22	# functions, and its name as written.
23	type Owner is Data:
24	  Owner{templates: List<&2, U32>, name: String}
25	
26	# Functions
27	# =========
28	def message(+template: String, owner: String) -> String:
29	  template
30	    ++ " is a template, so reading it here builds its whole record, closures too, to read a part of it; and a record of functions passed as a template is built again at each use, so "
31	    ++ owner
32	    ++ " repeats this wherever its record is used, twice as often at each level of nesting. All lanes. Measured on a combinator nested 6 deep: 1.7 s against 1.0 s after the fix on the C lane, 49 s against 14 s on the JS lane; on a nested model, 6% of the time. Confidence: medium, as the fix moves the work to each read of the field. Make the field a function of Unit (`n: Unit -> U32`, built as `u => ..`), so that "
33	    ++ template
34	    ++ " is read only when the field is called. If the field is read about as often as the record is built, expect this finding."
35	
36	def records.step(+u: Unit, +node: Lint.Node, found: Bool) -> Bool:
37	  match node:
38	    case Lint.Node{
39	      Lint.Field{b, q},
40	      n,
41	      s,
42	      Con{Lint.Node{Lint.Forall{fb, fq}, fn, fs, fk, ff}, rest},
43	      f
44	    }:
45	      True{}
46	    case _:
47	      found
48	
49	# The datatypes among `nodes` with a field whose written type is a function, by the name the check gives them, onto
50	# `out`.
51	def records(nodes: List<&2, Lint.Node>, out: List<&2, String>) -> List<&2, String>:
52	  match nodes:
53	    case Nil{}:
54	      out
55	    case Con{Lint.Node{Lint.Datatype{t}, n, s, kids, f}, rest}:
56	      records(
57	        rest,
58	        Lists.push(
59	          String,
60	          Lists.when(String, Lint.fold(~Unit, ~Bool, ~records.step, Unit{}, kids, False{}), t),
61	          out
62	        )
63	      )
64	    case Con{node, rest}:
65	      records(rest, out)
66	
67	def program.records(sources: List<&2, Lint.Source>, out: List<&2, String>) -> List<&2, String>:
68	  match sources:
69	    case Nil{}:
70	      out
71	    case Con{Lint.Source{path, ns, text, nodes}, rest}:
72	      program.records(rest, records(nodes, out))
73	
74	# The datatype a type's nodes write, by the name the check gives it, or "" for another form (a function, a sort).
75	def written(nodes: List<&2, Lint.Node>) -> String:
76	  match nodes:
77	    case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
78	      t
79	    case Con{Lint.Node{Lint.TypeApplication{t}, n, s, k, f}, rest}:
80	      t
81	    case _:
82	      ""
83	
84	# The binders of the templates among a definition's nodes whose type is one of `records`, onto `out`.
85	def templates(
86	  nodes: List<&2, Lint.Node>,
87	  +records: List<&2, String>,
88	  out: List<&2, U32>
89	) -> List<&2, U32>:
90	  match nodes:
91	    case Nil{}:
92	      out
93	    case Con{Lint.Node{Lint.Parameter{b, Lint.Template{}}, n, s, kids, f}, rest}:
94	      templates(
95	        rest,
96	        records,
97	        Lists.push(
98	          U32,
99	          Lists.when(U32, List.contains(~String, ~String.eq, records, written(kids)), b),
100	          out
101	        )
102	      )
103	    case Con{node, rest}:
104	      templates(rest, records, out)
105	
106	def is_lambda(node: Lint.Node) -> Bool:
107	  match node:
108	    case Lint.Node{Lint.Lambda{b, q}, n, s, k, f}:
109	      True{}
110	    case _:
111	      False{}
112	
113	# Whether a node below `path` is computed when a record of functions is built: under no lambda, and in a construction
114	# with a lambda among its fields (`found`, once one is).
115	def is_built(path: List<&2, Lint.Above>, found: Bool) -> Bool:
116	  match path:
117	    case Nil{}:
118	      found
119	    case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest}:
120	      False{}
121	    case Con{Lint.Above{Lint.Node{Lint.Construction{t}, n, s, kids, f}, at}, rest}:
122	      is_built(rest, Bool.or(found, Lists.any(~Lint.Node, ~is_lambda, kids)))
123	    case Con{a, rest}:
124	      is_built(rest, found)
125	
126	def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
127	  match owner node:
128	    case Owner{templates, name} Lint.Node{Lint.Variable{b}, template, span, k, f}:
129	      Lint.finding(
130	        Lint.Information{},
131	        Bool.and(
132	          List.contains(~U32, ~U32.is_eq, templates, b),
133	          Bool.and(Lint.is_live(path), is_built(path, False{}))
134	        ),
135	        span,
136	        message(template, name)
137	      )
138	    case _ _:
139	      []
140	
141	# The findings in the definitions among `nodes` that have templates of `records`, onto `out` (last first).
142	def defs(
143	  nodes: List<&2, Lint.Node>,
144	  +records: List<&2, String>,
145	  out: List<&2, Lint.Finding>
146	) -> List<&2, Lint.Finding>:
147	  match nodes:
148	    case Nil{}:
149	      out
150	    case Con{Lint.Node{Lint.Definition{t, u}, +n, s, +kids, f}, rest}:
151	      defs(
152	        rest,
153	        records,
154	        Lists.onto(
155	          &2,
156	          Lint.Finding,
157	          Lint.visit(
158	            ~Owner,
159	            ~Lint.Finding,
160	            ~visit,
161	            Owner{templates(kids, records, []), n},
162	            [Lint.Node{Lint.Definition{t, u}, n, s, kids, f}]
163	          ),
164	          out
165	        )
166	      )
167	    case Con{node, rest}:
168	      defs(rest, records, out)
169	
170	def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
171	  Lint.done(
172	    List.reverse(
173	      &2,
174	      Lint.Finding,
175	      defs(Lint.Here.nodes(here), program.records(Lint.Here.sources(here), []), [])
176	    )
177	  )
178	
179	def rule() -> Lint.Rule:
180	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}