Skip to content
← Back

src/syntax/process/infer-effects/infer_store_free_classification.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
// Per-node classification: visit_default, resolved-value and fused-for classification,
15
// study notes and the disqualify family.
16
partial INFER_STORE_FREE is
17
// ==== default: any node kind without an explicit override ====
18
19
visit_default(node: Trees.Node) is
20
if _resolved_mode /\ _classify_resolved(node) then
21
return
22
fi
23
24
_disqualify_because("unaudited-node:{node.get_type().full_name}")
25
si
26
27
// Once compile-expressions has run, the node kinds
28
// this walk never modelled carry enough resolved state to be
29
// classified: a `for` names the three iterator members it calls,
30
// and every other expression carries the value it compiled to,
31
// whose callee is a bounded edge like any other. Returns whether
32
// the node was classified; false falls through to disqualifying
33
// it as before.
34
_classify_resolved(node: Trees.Node) -> bool is
35
// an element read cannot be pinned to a member symbol;
36
// the read-closure records it as its own dimension
37
if _current_record? then
38
if isa Trees.Expressions.INDEX(node) then
39
_current_record.reads_elements = true
40
elif isa Trees.Expressions.AMBIGUOUS_EXPRESSION(node) then
41
if (cast Trees.Expressions.AMBIGUOUS_EXPRESSION(node)).result == Trees.Expressions.AmbiguousExpressionResult.INDEX then
42
_current_record.reads_elements = true
43
fi
44
fi
45
fi
46
47
if let carrier: Trees.IteratorCarrier = node then
48
if let `for: Statements.FOR = node /\ `for.fusion? then
49
return _classify_fused_for(`for.fusion)
50
fi
51
52
// read_iterator is legitimately null when the iterated
53
// expression is already an iterator - the emitter
54
// drives move_next/current on the value directly
55
let move_next = carrier.move_next
56
let read_current = carrier.read_current
57
58
if !move_next? \/ !read_current? then
59
let expression = carrier.iterated
60
61
let detail =
62
if !expression? then
63
"no-expression"
64
elif !expression.value? then
65
"no-value"
66
elif !expression.value.type? then
67
"no-type"
68
else
69
"{expression.value.type}"
70
fi
71
72
_disqualify_because("iterator-unresolved:{detail}")
73
return true
74
fi
75
76
if carrier.read_iterator? then
77
_add_callee(carrier.read_iterator)
78
fi
79
80
_add_callee(move_next)
81
_add_callee(read_current)
82
83
return true
84
fi
85
86
if let expression: Trees.Expressions.Expression = node then
87
let value = expression.value
88
89
if !value? then
90
return false
91
fi
92
93
return _classify_resolved_value(value)
94
fi
95
96
return false
97
si
98
99
// A fused loop never builds the pipe objects: it iterates the
100
// pinned built-in source directly and runs each map/filter
101
// stage's lambda body inline, so the loop's effects are the
102
// stage bodies' effects. The lambda literals were skipped by
103
// the ordinary walk (creating a closure is effect-free), so
104
// they are walked here, attributed to the enclosing function
105
// exactly as the fused lowering executes them. A stage fed an
106
// arbitrary delegate value rather than a literal is invoked
107
// per element with no bounded callee, so it stays unbounded
108
// unless the value's type is a pure function type.
109
_classify_fused_for(fusion: PIPE_FUSION) -> bool is
110
for stage in fusion.stages_outermost_first do
111
if stage.is_countdown \/ stage.is_index then
112
continue
113
fi
114
115
let argument = stage.argument
116
117
if !argument? then
118
continue
119
fi
120
121
if let literal: Trees.Expressions.FUNCTION = argument then
122
literal.body.walk(self)
123
elif !(argument.value? /\ argument.value.type? /\ argument.value.type.is_pure_function) then
124
_disqualify_because("fused-stage-delegate")
125
return true
126
fi
127
od
128
129
return true
130
si
131
132
_classify_resolved_value(value: IR.Values.Value) -> bool is
133
if let view: IR.Values.NARROW_VIEW = value then
134
return _classify_resolved_value(view.underlying)
135
fi
136
137
// A scalar constructor is a cast, and a cast is not a call.
138
if isa IR.Values.SCALAR_CONVERSION(value) then
139
return true
140
fi
141
142
if let call: IR.Values.Call.INSTANCE = value then
143
_note_overload_site(call.function, call.from, call.arguments)
144
_add_callee(call.function)
145
_study_note_call_arguments(call.function, call.arguments)
146
return true
147
fi
148
149
if let call: IR.Values.Call.STATIC = value then
150
_note_overload_site(call.function, null, call.arguments)
151
_add_callee(call.function)
152
_study_note_call_arguments(call.function, call.arguments)
153
return true
154
fi
155
156
if let call: IR.Values.Call.GLOBAL = value then
157
_note_overload_site(call.function, null, call.arguments)
158
_add_callee(call.function)
159
_study_note_call_arguments(call.function, call.arguments)
160
return true
161
fi
162
163
if let call: IR.Values.Call.STRUCT = value then
164
_note_overload_site(call.function, call.from, call.arguments)
165
_add_callee(call.function)
166
_study_note_call_arguments(call.function, call.arguments)
167
return true
168
fi
169
170
if let construction: IR.Values.NEW = value then
171
// constructing a reflected exception writes only the
172
// fresh object — the same trust the declared-types
173
// classification extends, restated here so the edge
174
// to the unwalked BCL constructor does not poison
175
if !_is_store_free_construction(cast Symbol?(construction.constructor.owner)) then
176
_add_construction_callee(construction.constructor)
177
fi
178
179
_study_note_call_arguments(construction.constructor, construction.arguments)
180
return true
181
fi
182
183
// Invoking a function value: bounded when the value names
184
// its function, effect-polymorphic when it is one of the
185
// enclosing function's own parameters, unboundable
186
// otherwise.
187
if let call: IR.Values.Call.CLOSURE = value then
188
if !call.is_state_changing_call then
189
return true
190
fi
191
192
let fn = function_value_of(call.from)
193
194
if fn? then
195
_add_callee(fn)
196
_study_note_call_arguments(fn, call.arguments)
197
return true
198
fi
199
200
if isa IR.Values.Load.LOCAL_ARGUMENT(call.from) then
201
if _current_record? then
202
_current_record.invokes_function_param = true
203
fi
204
205
return true
206
fi
207
208
return false
209
fi
210
211
// not a call at all: reading a value writes nothing, and any
212
// sub-expression is classified as the walk reaches it
213
return !value.is_state_changing_call
214
si
215
216
function_values: FUNCTION_VALUES public
217
218
// The resolver from compiled values to the functions they
219
// denote, including the immutable-local record this walk
220
// populates. Shared with the pure-slot judge.
221
222
function_value_of(value: IR.Values.Value?) -> Function? =>
223
function_values.function_value_of(value)
224
225
// Record which function values flow into a callee's
226
// function-typed parameters. A named value joins the callee's
227
// passed set; the caller's own parameter forwarded onward is
228
// accounted at the caller's own call sites instead; anything
229
// else function-typed makes the callee's parameter values
230
// unknowable - unless its type is pure, which admits only
231
// store-free values whoever invokes it.
232
_study_note_call_arguments(callee: Function?, arguments: Collections.List[IR.Values.Value]) is
233
if !callee? then
234
return
235
fi
236
237
let from_file = if let current = _current_function then current.location.file_name else "" fi
238
239
for argument in arguments do
240
let fn = function_value_of(argument)
241
242
if fn? then
243
EFFECT_FACTS.note_passed_function(callee, fn, from_file)
244
continue
245
fi
246
247
if isa IR.Values.Load.LOCAL_ARGUMENT(argument) then
248
let argument_type = argument.type
249
250
if argument_type? /\ argument_type.is_function /\ !argument_type.is_pure_function then
251
if _current_record? then
252
let root = cast Function?(callee.root_specialized_from)
253
254
if root? then
255
_current_record.forwards_param_to.add(root)
256
fi
257
fi
258
fi
259
260
continue
261
fi
262
263
let argument_type = argument.type
264
265
if argument_type? /\ argument_type.is_function /\ !argument_type.is_pure_function then
266
EFFECT_FACTS.note_passed_opaque(callee, from_file)
267
NARROWING_STUDY.note_opaque_shape("{argument.get_type().name} -> {callee.name}")
268
fi
269
od
270
si
271
272
// `_disqualify` with the reason recorded for the study, so the
273
// report can say what the walk actually gives up on. First
274
// reason wins: it is the one that made the function unbounded.
275
_disqualify_because(reason: string) is
276
277
if _current? /\ _current_record? /\ _current_record.unbounded_reason =~ "" then
278
_current_record.unbounded_reason = reason
279
fi
280
281
_disqualify()
282
si
283
284
_disqualify() is
285
if !_current? then
286
return
287
fi
288
289
_current.is_disqualified = true
290
_current.is_construction_disqualified = true
291
292
if _current_record? then
293
_current_record.own_unbounded = true
294
295
// whatever the walk could not bound could write
296
// anything, so the write set stops being a bound too
297
_current_record.writes_unbounded = true
298
fi
299
si
300
301
// A captured-local store: not store-free - the declaring
302
// scope sees the write - but the write set stays bounded,
303
// because the store targets exactly the one local symbol the
304
// study path records.
305
_disqualify_captured_store() is
306
if !_current? then
307
return
308
fi
309
310
_current.is_disqualified = true
311
_current.is_construction_disqualified = true
312
si
313
314
// The subset of `_disqualify` where the walk saw a write to a
315
// pre-existing heap slot rather than merely failing to bound
316
// something. Behaves identically; only the study distinguishes
317
// them.
318
_disqualify_store() is
319
if !_current? then
320
return
321
fi
322
323
_current.is_disqualified = true
324
_current.is_construction_disqualified = true
325
326
if _current_record? then
327
_current_record.own_stores = true
328
fi
329
si
330
331
// A store the strict analysis rejects but a construction does
332
// not: writing the receiver's own instance state touches only
333
// the fresh object a `NEW` is building.
334
_disqualify_strict_only() is
335
if !_current? then
336
return
337
fi
338
339
_current.is_disqualified = true
340
341
if _current_record? then
342
_current_record.own_stores = true
343
fi
344
si
345
346
347
_in_constructor: bool =>
348
_current_function? /\ _current_function.is_constructor
349
350
// A `self.field` target naming an instance field of the
351
// receiver. `self` is the only receiver the construction bit
352
// says anything about; a member on any other receiver stays a
353
// heap store.
354
_writes_own_instance_field_member(target: Trees.Expressions.Expression?) -> bool is
355
if !target? \/ !isa Trees.Expressions.MEMBER(target) then
356
return false
357
fi
358
359
let member = cast Trees.Expressions.MEMBER(target)
360
361
if !isa Trees.Expressions.SELF(member.left) then
362
return false
363
fi
364
365
let context = current_instance_context
366
367
if !context? then
368
return false
369
fi
370
371
let field_symbol = context.find_member(member.identifier.name)
372
373
return field_symbol? /\ field_symbol.is_field /\ field_symbol.is_instance
374
si
375
376
// The assign accessor behind a `self.property` target on the
377
// type under construction. Writing a property runs its
378
// accessor rather than storing directly, so the write is only
379
// as safe as that accessor is — an auto-property's accessor
380
// writes nothing but its own backing field and qualifies, a
381
// hand-written one that stores elsewhere does not. Null for any
382
// target that is not an instance property on `self`.
383
_writes_own_instance_property_member(target: Trees.Expressions.Expression?) -> Function? is
384
if !target? \/ !isa Trees.Expressions.MEMBER(target) then
385
return null
386
fi
387
388
let member = cast Trees.Expressions.MEMBER(target)
389
390
if !isa Trees.Expressions.SELF(member.left) then
391
return null
392
fi
393
394
let context = current_instance_context
395
396
if !context? then
397
return null
398
fi
399
400
return _instance_property_assign(context.find_member(member.identifier.name))
401
si
402
403
// A constructor delegating to another constructor on the same
404
// object — `super.init(…)` from a subclass, `self.init(…)` from
405
// a secondary constructor.
406
_is_constructor_chain(member: Trees.Expressions.MEMBER) -> bool =>
407
_in_constructor /\
408
member.identifier.name =~ "init" /\
409
(isa Trees.Expressions.SELF(member.left) \/ isa Trees.Expressions.SUPER(member.left))
410
411
_instance_property_assign(symbol: Symbol?) -> Function? is
412
if !symbol? \/ !symbol.is_instance \/ !isa Semantic.Symbols.Property(symbol) then
413
return null
414
fi
415
416
return (cast Semantic.Symbols.Property(symbol)).assign_function
417
si
418
419
si
420
si
421
422
namespace Syntax.Process is
423
use Function = Semantic.Symbols.Function
424
425
// Measurement only: the call sites where the overload compile-
426
// expressions chose was picked with a narrowed operand in play and
427
// the callee has siblings. These are the only places the solve is
428
// not monotone in the facts - a killed narrowing can move the call
429
// to a sibling with a different write set - so their count, and
430
// how many siblings actually differ, says whether the descent's
431
// answer can depend on where it started.
432
partial INFER_STORE_FREE is
433
_overload_sites: Collections.LIST[(callee: Function, siblings: Collections.List[Function])]? static
434
435
_note_overload_site(function: Function, from: IR.Values.Value?, arguments: Collections.List[IR.Values.Value]) is
436
if !_measure_overload_sites \/ !_resolved_mode then
437
return
438
fi
439
440
let narrowed mut = from? /\ isa IR.Values.NARROW_VIEW(from)
441
442
for argument in arguments do
443
if isa IR.Values.NARROW_VIEW(argument) then
444
narrowed = true
445
fi
446
od
447
448
if !narrowed then
449
return
450
fi
451
452
let root = cast Function?(function.root_specialized_from)
453
454
if !root? then
455
return
456
fi
457
458
if let owner = root.owner, group: Semantic.Symbols.FUNCTION_GROUP = owner.find_member(root.name) then
459
if group.count > 1 then
460
if !_overload_sites? then
461
_overload_sites = Collections.LIST[(callee: Function, siblings: Collections.List[Function])]()
462
fi
463
464
_overload_sites.add((callee = root, siblings = group.functions))
465
fi
466
fi
467
si
468
469
// After a solve: how many noted sites have a sibling whose
470
// solved write set differs from the chosen overload's.
471
_report_overload_sites() static is
472
let sites = _overload_sites
473
474
if !sites? then
475
IO.Std.error.write_line("overload sites with a narrowed operand: 0")
476
477
return
478
fi
479
480
let differing mut = 0
481
482
for site in sites do
483
let chosen = EFFECTS.write_set_of(site.callee)
484
485
for sibling in site.siblings do
486
if sibling == site.callee then
487
continue
488
fi
489
490
if !_same_write_set(chosen, EFFECTS.write_set_of(sibling)) then
491
differing = differing + 1
492
493
IO.Std.error.write_line(" overload site: {site.callee.qualified_name} vs {sibling.qualified_name}")
494
495
break
496
fi
497
od
498
od
499
500
IO.Std.error.write_line("overload sites with a narrowed operand: {sites.count}, with a sibling whose write set differs: {differing}")
501
502
_overload_sites = null
503
si
504
505
_same_write_set(a: Collections.SET[int]?, b: Collections.SET[int]?) -> bool static is
506
if !a? \/ !b? then
507
return !a? /\ !b?
508
fi
509
510
if a.count != b.count then
511
return false
512
fi
513
514
for id in a do
515
if !b.contains(id) then
516
return false
517
fi
518
od
519
520
return true
521
si
522
si
523
si