Skip to content
← Back

src/syntax/process/infer-effects/infer_store_free.ghul

1
namespace Syntax.Process is
2
use System.Exception
3
4
use Ghul.Pipes
5
6
use Logging
7
use Trees
8
9
use Semantic.Types.Type
10
11
use Function = Semantic.Symbols.Function
12
use Symbol = Semantic.Symbols.Symbol
13
14
// Facts the body walk gathers for one function, consumed by the
15
// finish-time fixpoint.
16
class STORE_FREE_FACTS is
17
// The body performs a store or an effect the walk cannot
18
// bound: an assignment to anything but a local, a call with
19
// an unresolvable callee set, disposal, iteration, an
20
// untyped interpolation fragment, an await or yield, ...
21
is_disqualified: bool public
22
23
// The same, except a write to the receiver's own instance state
24
// does not set it. That write is invisible to every caller when
25
// the receiver is an object nothing else can reach yet, which
26
// is what both consumers of this bit guarantee: a constructor
27
// run by a `NEW`, and a member reached on `self` from inside
28
// such a constructor. So it says "writes nothing but the state
29
// of the object it is called on", and is only ever read where
30
// that object is known to be fresh.
31
is_construction_disqualified: bool public
32
33
// Statically-bounded callees. The function is store-free
34
// only if every one of them proves store-free too.
35
callees: Collections.MutableList[Function]
36
37
// Callees reached on a receiver that is fresh, or that is the
38
// fresh receiver the caller is itself being constructed on: a
39
// constructor run by a construction, and the assign accessor
40
// of a property written on `self` inside a constructor. Their
41
// own-state writes cannot touch a slot any caller holds a fact
42
// about, so these are bounded by the construction-store-free
43
// classification rather than the strict one.
44
construction_callees: Collections.MutableList[Function]
45
46
init() is
47
callees = Collections.LIST[Function]()
48
construction_callees = Collections.LIST[Function]()
49
si
50
51
add_callee(callee: Function) is
52
callees.add(callee)
53
si
54
55
add_construction_callee(callee: Function) is
56
construction_callees.add(callee)
57
si
58
si
59
60
// The body walk behind the infer-effects pass, run after
61
// compile-expressions with the types that pass resolved. Gathers
62
// for every function the facts the effect solvers consume — its
63
// member writes, nulling writes and reads, its bounded callees,
64
// and whether anything in the body defeats bounding — from which
65
// solve_effects derives the member-granular effect relations
66
// (EFFECTS) and the store-free classification written back onto
67
// the symbols. Reads are always harmless; only writes and
68
// unboundable calls disqualify. Dispatch is bounded using
69
// resolve-overrides' overrider links; a method reachable through
70
// an open class or a trait is never store-free, because an
71
// override in another assembly could store.
72
//
73
// Every node kind not explicitly classified below is unsafe via
74
// visit_default. When a new node kind is added, it must be
75
// explicitly audited here before functions containing it can
76
// classify as store-free.
77
//
78
// This pass never reports diagnostics. It runs on incomplete and
79
// incorrect code in analysis mode, where the other passes own
80
// finding and reporting every problem; anything suspect here just
81
// classifies conservatively.
82
class INFER_STORE_FREE: DefaultVisitor is
83
_facts: Collections.MutableMap[Function, STORE_FREE_FACTS]
84
_current: STORE_FREE_FACTS?
85
_current_function: Function?
86
87
// The study's record for the function being walked, or null
88
// when the study is off. See NARROWING_STUDY.
89
_current_record: FUNCTION_EFFECT_FACTS?
90
91
// Trivially-derivable static types, including the per-function
92
// record of locals whose initializer type was derivable.
93
_typer: TRIVIAL_EXPRESSION_TYPER
94
95
_innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup
96
97
init(
98
logger: Logger,
99
symbol_table: Semantic.SYMBOL_TABLE,
100
namespaces: Semantic.NAMESPACES,
101
innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup
102
)
103
is
104
super.init(logger, symbol_table, namespaces)
105
106
_typer = TRIVIAL_EXPRESSION_TYPER(symbol_table, innate_symbol_lookup)
107
_innate_symbol_lookup = innate_symbol_lookup
108
function_values = FUNCTION_VALUES()
109
110
start_run()
111
si
112
113
start_run() is
114
_facts = Collections.MAP[Function, STORE_FREE_FACTS]()
115
_solved_over_facts = false
116
_last_solution = null
117
function_values.clear()
118
_typer.reset()
119
_current = null
120
_current_function = null
121
si
122
123
// Drop what the walk of one file derived - its functions' facts
124
// and the function values its locals held - ahead of walking
125
// that file again. Facts for every other file stay, so a round
126
// that re-walks a few files solves over the union of what it
127
// re-derived and what it kept. A lambda's facts are keyed on
128
// its closure symbol, whose location is the literal's, so they
129
// drop with the file too.
130
// Whether the relations in use were solved, completely, from
131
// the facts retained here - what a partial round builds on. A
132
// rebuild that walks only some files solves incompletely and
133
// installs nothing, leaving relations no retained fact backs.
134
_solved_over_facts: bool
135
136
solved_over_facts: bool => _solved_over_facts /\ _facts.count > 0
137
138
drop_file(file_name: string) is
139
let stale = Collections.LIST[Function]()
140
141
for function in _facts.keys do
142
if function.location.file_name =~ file_name then
143
stale.add(function)
144
fi
145
od
146
147
for function in stale do
148
_facts.remove(function)
149
od
150
151
EFFECT_FACTS.drop_file(file_name)
152
function_values.drop_file(file_name)
153
154
_typer.reset()
155
_current = null
156
_current_function = null
157
si
158
159
// The walk must survive incomplete and incorrect code — it
160
// runs in analysis mode on whatever the user has half-typed.
161
// It reports nothing, ever: broken code is found and
162
// diagnosed by the other passes, and an analysis here that
163
// cannot complete only means some functions conservatively
164
// stay not-store-free. On an exception the symbol-table scope
165
// stack is restored to its entry depth so a long-lived
166
// analysis process is not poisoned for later passes, and
167
// whatever function was mid-walk keeps its disqualification.
168
apply(root: Trees.Node) is
169
let mark = mark_scope_stack()
170
171
MONOTONE_MEMOISER.clear_file(root.location.file_name)
172
173
_last_walk_failed = false
174
175
try
176
root.walk(self)
177
catch ex: Exception
178
_disqualify_because("walk-aborted")
179
release_scope_stack(mark)
180
181
_last_walk_failed = true
182
yrt
183
184
_current = null
185
_current_function = null
186
_current_record = null
187
si
188
189
// Whether the most recent apply abandoned its walk on an
190
// exception. The partial walk's facts stay in this run's union,
191
// which is conservative: whatever was mid-walk keeps its
192
// disqualification.
193
_last_walk_failed: bool
194
last_walk_failed: bool => _last_walk_failed
195
196
// Read the types compile-expressions resolved rather than
197
// deriving trivial static types from declarations — the
198
// production setting for the infer-effects pass; off leaves
199
// the declared-types-only approximation, which unit fixtures
200
// without compiled expressions still use.
201
set_resolved_mode(on: bool) is
202
_typer.use_resolved = on
203
_resolved_mode = on
204
205
if on then
206
// Before the walk, so a call to one of these is a
207
// trusted leaf rather than a callee edge that poisons
208
// its caller.
209
_trust_value_optional_accessors()
210
fi
211
si
212
213
_resolved_mode: bool
214
215
// The overload-site count is measurement only, read once so the
216
// walk pays nothing for it when it is not asked for.
217
_measure_overload_sites: bool static
218
219
init() static is
220
_measure_overload_sites = System.Environment.get_environment_variable("GHUL_EFFECTS_TIMING")?
221
si
222
223
// Solve the effect relations over this run's facts and install
224
// them for the crossing discharge. Called by the infer-effects
225
// pass's finish hook, after the resolved-mode walk of every
226
// file. A failure leaves the registry cleared, which every
227
// query answers conservatively. The facts are kept: a later
228
// round that re-walks only some files drops theirs and solves
229
// over the rest unchanged.
230
solve_effects(complete: bool) is
231
_solve_effects(complete, null)
232
si
233
234
// Re-solve after a partial round changed the inputs of
235
// `changed`: from the last solution, re-deriving only the rows
236
// that can differ from it. Only meaningful over relations
237
// solved from these facts.
238
resolve_effects_for(changed: Collections.SET[Function]) is
239
_solve_effects(true, changed)
240
si
241
242
// The last complete solve's rows, for the next solve to start
243
// from.
244
_last_solution: EFFECT_SOLUTION?
245
246
_solve_effects(complete: bool, changed: Collections.SET[Function]?) is
247
// A round that walked no bodies - a rebuild with no file open
248
// compiles no expressions - has nothing to say; installing its
249
// empty relations would replace ones that do.
250
if _facts.count == 0 then
251
if System.Environment.get_environment_variable("GHUL_EFFECTS_TIMING")? then
252
IO.Std.error.write_line("effects: no bodies walked, relations kept")
253
fi
254
255
return
256
fi
257
258
try
259
let study = EFFECT_SOLVERS(_facts)
260
261
let sw = System.Diagnostics.Stopwatch.start_new()
262
263
if changed? /\ _solved_over_facts then
264
if let previous = _last_solution then
265
study.seed_from(previous, changed)
266
fi
267
fi
268
269
let t_d = sw.elapsed_milliseconds
270
let writes = study.write_sets(false, false)
271
let t_w = sw.elapsed_milliseconds
272
let nulls = study.may_null_sets(false, false)
273
let t_n = sw.elapsed_milliseconds
274
let solved = study.solve()
275
let store_free = solved.store_free
276
let t_s = sw.elapsed_milliseconds
277
let reads = study.read_sets()
278
let t_r = sw.elapsed_milliseconds
279
280
EFFECTS.install(
281
writes.sets, writes.unbounded,
282
nulls.sets, nulls.unbounded,
283
store_free,
284
solved.constructs_store_free,
285
reads.sets, reads.unbounded, reads.reads_elements, reads.writes_elements,
286
complete)
287
288
let t_i = sw.elapsed_milliseconds
289
290
if NARROWING_STUDY.enabled \/ System.Environment.get_environment_variable("GHUL_EFFECTS_TIMING")? then
291
IO.Std.error.write_line("solve phases: seed {t_d} writes {t_w - t_d} nulls {t_n - t_w} store-free {t_s - t_n} reads {t_r - t_s} install {t_i - t_r}, {study.affected_count} of {_facts.count} rows derived")
292
fi
293
294
_solved_over_facts = complete
295
296
let solution = EFFECT_SOLUTION(
297
writes.sets, writes.unbounded,
298
nulls.sets, nulls.unbounded,
299
store_free, solved.constructs_store_free,
300
reads.sets, reads.unbounded, reads.reads_elements, reads.writes_elements)
301
302
_last_solution = if complete then solution else null fi
303
304
if changed? /\ System.Environment.get_environment_variable("GHUL_EFFECTS_VERIFY")? then
305
_verify_seeded_solve(solution)
306
fi
307
308
if System.Environment.get_environment_variable("GHUL_EFFECTS_TIMING")? then
309
_report_overload_sites()
310
fi
311
312
// Mark what the solve proved back onto the symbols,
313
// where the display surfaces read it. Assigned both
314
// ways so a function that stops being provable is
315
// unmarked by the next solve rather than staying
316
// stale-true.
317
for function in _facts.keys do
318
let root = cast Function?(function.root_specialized_from)
319
320
if root? then
321
root.set_proven_store_free(store_free.contains(root))
322
fi
323
od
324
325
if NARROWING_STUDY.enabled then
326
IO.Std.error.write_line(
327
"effects: {writes.sets.count} walked, "
328
"{writes.unbounded.count} write-unbounded, "
329
"{nulls.unbounded.count} null-unbounded, "
330
"{store_free.count} store-free")
331
332
_complete_records()
333
NARROWING_STUDY.report()
334
fi
335
catch ex: Exception
336
EFFECTS.clear()
337
_solved_over_facts = false
338
_last_solution = null
339
340
if NARROWING_STUDY.enabled then
341
IO.Std.error.write_line("effects: solve failed: {ex}")
342
fi
343
yrt
344
si
345
346
// Measurement only: solve everything again from scratch and
347
// report every row the seeded solve got differently.
348
_verify_seeded_solve(seeded: EFFECT_SOLUTION) is
349
let fresh = EFFECT_SOLVERS(_facts)
350
let writes = fresh.write_sets(false, false)
351
let nulls = fresh.may_null_sets(false, false)
352
let solved = fresh.solve()
353
let reads = fresh.read_sets()
354
355
let differences mut = 0
356
357
// an unbounded row's members are never read, and stop
358
// accumulating when the row becomes unbounded, so only
359
// bounded rows are compared
360
differences = differences + _differing_rows("write", seeded.write_sets, writes.sets, writes.unbounded)
361
differences = differences + _differing_functions("write-unbounded", seeded.write_unbounded, writes.unbounded)
362
differences = differences + _differing_rows("null", seeded.null_sets, nulls.sets, nulls.unbounded)
363
differences = differences + _differing_functions("null-unbounded", seeded.null_unbounded, nulls.unbounded)
364
differences = differences + _differing_functions("store-free", seeded.store_free, solved.store_free)
365
differences = differences + _differing_functions("constructs-store-free", seeded.constructs_store_free, solved.constructs_store_free)
366
differences = differences + _differing_rows("read", seeded.read_sets, reads.sets, reads.unbounded)
367
differences = differences + _differing_functions("read-unbounded", seeded.read_unbounded, reads.unbounded)
368
differences = differences + _differing_functions("reads-elements", seeded.reads_elements, reads.reads_elements)
369
differences = differences + _differing_functions("writes-elements", seeded.writes_elements, reads.writes_elements)
370
371
IO.Std.error.write_line("effects: seeded solve verified against a fresh one: {differences} difference(s)")
372
si
373
374
_differing_rows(
375
what: string,
376
seeded: Collections.MutableMap[Function, Collections.SET[Symbol]],
377
fresh: Collections.MutableMap[Function, Collections.SET[Symbol]],
378
unbounded: Collections.SET[Function]
379
) -> int is
380
let result mut = 0
381
382
for entry in fresh do
383
if unbounded.contains(entry.key) then
384
continue
385
fi
386
387
let mine = if seeded.contains_key(entry.key) then seeded[entry.key] else null fi
388
389
if !mine? \/ mine.count != entry.value.count \/ entry.value |> Ghul.Pipes.any(m => !mine.contains(m)) then
390
IO.Std.error.write_line(" {what} row differs: {entry.key.qualified_name} seeded {mine?.count ?? -1} fresh {entry.value.count}")
391
result = result + 1
392
fi
393
od
394
395
return result + if seeded.count != fresh.count then 1 else 0 fi
396
si
397
398
_differing_functions(what: string, seeded: Collections.SET[Function], fresh: Collections.SET[Function]) -> int is
399
let result mut = 0
400
401
for function in fresh do
402
if !seeded.contains(function) then
403
IO.Std.error.write_line(" {what}: {function.qualified_name} fresh only")
404
result = result + 1
405
fi
406
od
407
408
for function in seeded do
409
if !fresh.contains(function) then
410
IO.Std.error.write_line(" {what}: {function.qualified_name} seeded only")
411
result = result + 1
412
fi
413
od
414
415
return result
416
si
417
418
// Complete each effect record with the solve-side facts the
419
// report prints - reporting only, nothing reads these back.
420
_complete_records() is
421
let shadow = STORE_FREE_FIXPOINT()
422
423
for function in _facts.keys do
424
let record = EFFECT_FACTS.record_for(function)
425
426
if !record? then
427
continue
428
fi
429
430
record.is_disqualified = _facts[function].is_disqualified
431
record.callee_count = _facts[function].callees.count
432
record.openly_dispatchable = shadow.is_openly_dispatchable(function)
433
record.declared_pure = function.is_declared_pure
434
435
let overriders = function.overriders
436
437
let overrider_count mut = 0
438
439
if overriders? then
440
for overrider in overriders do
441
overrider_count = overrider_count + 1
442
od
443
fi
444
445
record.overrider_count = overrider_count
446
od
447
si
448
449
// The value-type optional carriers' accessors get the bit
450
// directly: `x?` / `x!` on an `int?`-style slot lower to
451
// these at compile-expressions time without appearing as
452
// call edges here, and both read a field of a sealed struct
453
// — no overrider can exist, so unconditional trust is sound.
454
// Without the bit every value-type presence test would count
455
// as a possibly-storing call and kill the very facts it
456
// establishes.
457
_trust_value_optional_accessors() is
458
let bool_type = _innate_symbol_lookup.get_bool_type()
459
460
_mark_read_accessors_store_free(_innate_symbol_lookup.get_optional_type(bool_type))
461
_mark_read_accessors_store_free(_innate_symbol_lookup.get_maybe_type(bool_type))
462
si
463
464
_mark_read_accessors_store_free(type: Semantic.Types.Type?) is
465
if !type? then
466
return
467
fi
468
469
for name in ["has_value", "value"] do
470
let member = type.find_member(name)
471
472
if member? /\ isa Semantic.Symbols.Property(member) then
473
let read_function = (cast Semantic.Symbols.Property(member)).read_function
474
475
if read_function? then
476
read_function.mark_declared_pure()
477
fi
478
fi
479
od
480
si
481
482
// Open an effect record for the function about to be walked,
483
// classifying its accessor role from the structural links the
484
// accessor synthesiser stamped.
485
_note_study_function(function: Definitions.FUNCTION, symbol: Function) is
486
_current_record = null
487
488
if !EFFECT_FACTS.collecting /\ !NARROWING_STUDY.enabled then
489
return
490
fi
491
492
let raw_name = if function.name? then function.name.name else "" fi
493
494
// The role is structural: the accessor synthesiser links
495
// each accessor to its property or indexer and stamps
496
// which half it is, so nothing is inferred back from the
497
// accessor's name.
498
let role =
499
if function.for_indexer? then
500
if function.is_assign_accessor then "index-set" else "index-get" fi
501
elif function.for_property? then
502
if function.is_assign_accessor then "set" else "get" fi
503
else
504
""
505
fi
506
507
let owner = symbol.owner
508
509
EFFECT_FACTS.note_function(
510
symbol,
511
raw_name,
512
if owner? then owner.name else "" fi,
513
"{function.location}",
514
role)
515
516
_current_record = EFFECT_FACTS.record_for(symbol)
517
518
if _current_record? /\ function.for_property? then
519
_current_record.for_auto_property = function.for_property.is_auto_property
520
fi
521
si
522
523
si
524
si