Skip to content
← Back

src/syntax/process/infer-effects/infer_store_free_values.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
// Value and expression walks: references, calls, operators, identifiers, members, indexing
15
// and generic applications.
16
partial INFER_STORE_FREE is
17
// `x ref` hands the callee the address of a storage location
18
// rather than a value, and the callee may write through it.
19
// What the callee itself does is bounded by the enclosing
20
// call's own edges, with one exception that decides this
21
// classification: several of the imports trusted store-free
22
// write a by-ref argument by contract — `try_get_value` is the
23
// everyday one — so a write through the address is not always
24
// covered by a callee edge. The operand therefore has to carry
25
// it. The address of a local variable or parameter is
26
// callee-private, exactly as assigning one is; the address of a
27
// field, a property or an element is a possible heap store.
28
//
29
// The node's own `writes_target` flag says which direction the
30
// matched parameter takes, and is deliberately not consulted:
31
// it is set during call resolution, which runs after this pass,
32
// so every REFERENCE reaching here still reads false.
33
//
34
// The operand is walked as a child, so its own reads are
35
// classified independently of this.
36
visit(reference: Expressions.REFERENCE) is
37
if !_current? then
38
return
39
fi
40
41
if !_is_local_target(reference.left) then
42
_disqualify()
43
fi
44
si
45
46
// Record, for the study, which member symbol a store targets.
47
// Mirrors the classification below without affecting it: a
48
// local target records nothing, a resolvable member records
49
// that symbol, anything else marks the writes unboundable.
50
_study_note_store(target: Trees.Expressions.Expression?) is
51
if !_current_record? then
52
return
53
fi
54
55
if !target? then
56
_current_record.writes_unbounded = true
57
return
58
fi
59
60
if isa Trees.Expressions.IDENTIFIER(target) then
61
let symbol = try_find((cast Trees.Expressions.IDENTIFIER(target)).identifier)
62
63
if
64
symbol? /\
65
(isa Semantic.Symbols.LOCAL_VARIABLE(symbol) \/ isa Semantic.Symbols.LOCAL_ARGUMENT(symbol))
66
then
67
// A store to a local the current body captured
68
// from an enclosing scope is not callee-private:
69
// the two share one heap cell, so the declaring
70
// scope sees the write. It enters the write and
71
// nulling sets under the local's own symbol, so a
72
// caller this body is absorbed into carries it.
73
if _is_captured_local_store(symbol) then
74
_study_note_nulling(false)
75
_study_note_nulling_member(symbol, false)
76
_study_add_write(symbol)
77
fi
78
79
return
80
fi
81
82
_study_note_nulling(symbol? /\ symbol.is_instance)
83
_study_note_nulling_member(symbol, symbol? /\ symbol.is_instance)
84
_study_add_write(symbol)
85
return
86
fi
87
88
if isa Trees.Expressions.MEMBER(target) then
89
let member = cast Trees.Expressions.MEMBER(target)
90
91
if isa Trees.Expressions.SELF(member.left) then
92
let context = current_instance_context
93
94
if context? then
95
_study_note_nulling(true)
96
_study_note_nulling_member(context.find_member(member.identifier.name), true)
97
_study_add_write(context.find_member(member.identifier.name))
98
return
99
fi
100
fi
101
102
let left_type = _typer.try_type(member.left)
103
104
if !left_type? then
105
_study_note_nulling(false)
106
_study_note_nulling_member(null, false)
107
_study_unbounded_store("store-receiver-untyped")
108
return
109
fi
110
111
let member_symbol = left_type.find_member(member.identifier.name)
112
113
if !member_symbol? then
114
_study_note_nulling(false)
115
_study_note_nulling_member(null, false)
116
_study_unbounded_store("store-member-not-found")
117
return
118
fi
119
120
_study_note_nulling(false)
121
_study_note_nulling_member(member_symbol, false)
122
_study_add_write(member_symbol)
123
return
124
fi
125
126
if isa Trees.Expressions.INDEX(target) then
127
// an element store: cannot change what any field holds,
128
// so it is recorded apart from member writes - the
129
// element-rescue measurement keys on the distinction
130
_current_record.writes_elements = true
131
return
132
fi
133
134
// `xs[i] = v` parses as an ambiguous expression; once
135
// compile-expressions has settled which shape it is, an
136
// index store is an element store like any other
137
if let ambiguous: Trees.Expressions.AMBIGUOUS_EXPRESSION = target then
138
if ambiguous.result == Trees.Expressions.AmbiguousExpressionResult.INDEX then
139
_current_record.writes_elements = true
140
return
141
fi
142
143
_study_note_nulling(false)
144
_study_note_nulling_member(null, false)
145
_study_unbounded_store("store-ambiguous-unresolved")
146
return
147
fi
148
149
// a target shape the walk does not model
150
_study_note_nulling(false)
151
_study_note_nulling_member(null, false)
152
_study_unbounded_store("store-target-shape:{target.get_type().name}")
153
si
154
155
// Mark the current record's write set unboundable, naming why,
156
// so the blame table can split the catch-all
157
// "write-target-unresolved" bucket by cause.
158
_study_unbounded_store(reason: string) is
159
if !_current_record? then
160
return
161
fi
162
163
_current_record.writes_unbounded = true
164
165
if _current_record.unbounded_reason =~ "" then
166
_current_record.unbounded_reason = reason
167
fi
168
si
169
170
_study_add_write(symbol: Symbol?) is
171
if !_current_record? then
172
return
173
fi
174
175
if !symbol? then
176
_current_record.writes_unbounded = true
177
return
178
fi
179
180
_current_record.writes.add(symbol.root_specialized_from)
181
si
182
183
// ==== calls ====
184
185
visit(call: Expressions.CALL) is
186
if !_current? then
187
return
188
fi
189
190
// Study-only: after compile-expressions the call carries the
191
// value it compiled to, which names the callee directly
192
// whatever shape the target expression has.
193
if _resolved_mode then
194
let value = call.value
195
196
if value? /\ _classify_resolved_value(value) then
197
return
198
fi
199
fi
200
201
_add_call_target_edges(call.function)
202
si
203
204
// A value slot whose declared type is a pure function type:
205
// invoking the held value is trusted store-free, whatever it
206
// turns out to be — the pure-typed slot only admits pure
207
// values. Parameters and fields qualify; a property is excluded
208
// because reading it runs its getter. A local variable is
209
// excluded too: its `type` is filled by compile-expressions,
210
// which runs after this pass, so reading it here would make the
211
// classification depend on whether that later pass has run — it
212
// has in an analysis-mode refresh, it has not in a batch build.
213
_is_pure_function_valued(symbol: Semantic.Symbols.Symbol?) -> bool =>
214
symbol? /\
215
isa Semantic.Symbols.Variable(symbol) /\
216
(_resolved_mode \/ !isa Semantic.Symbols.LOCAL_VARIABLE(symbol)) /\
217
symbol.type? /\ symbol.type.is_pure_function
218
219
// A synthesized `=~` or `get_hash_code`. The body stores
220
// nothing of its own - it reads members and compares them - so
221
// what it can do is exactly what the comparisons it reaches
222
// do, and the lowering recorded those as it chose them.
223
//
224
// Before compile-expressions there is nothing to read: the
225
// members have no types yet, so which comparison each takes is
226
// undecided and the body cannot be classified.
227
visit(memberwise: Trees.Expressions.MEMBERWISE_EQUALS) is
228
_add_memberwise_edges(memberwise.called_functions, memberwise.value?)
229
si
230
231
visit(memberwise: Trees.Expressions.MEMBERWISE_HASH) is
232
_add_memberwise_edges(memberwise.called_functions, memberwise.value?)
233
si
234
235
_add_memberwise_edges(
236
called: Collections.LIST[Semantic.Symbols.Function],
237
lowered: bool
238
) is
239
// Before compile-expressions the members have no types, so
240
// which comparison each takes is undecided and there is
241
// nothing to record. The resolved walk that follows is
242
// what settles the body; nothing between the two reads a
243
// synthesized operator's bit.
244
if !lowered then
245
return
246
fi
247
248
for function in called do
249
_add_callee(function)
250
od
251
si
252
253
_add_call_target_edges(target: Trees.Expressions.Expression?) is
254
if !target? then
255
_disqualify_because("call-target-null")
256
return
257
fi
258
259
if isa Trees.Expressions.IDENTIFIER(target) then
260
let identifier = (cast Trees.Expressions.IDENTIFIER(target)).identifier
261
262
let symbol = try_find(identifier)
263
264
if _is_pure_function_valued(symbol) then
265
return
266
fi
267
268
_add_callee_edges(symbol)
269
return
270
fi
271
272
if isa Trees.Expressions.MEMBER(target) then
273
let member = cast Trees.Expressions.MEMBER(target)
274
275
if _is_constructor_chain(member) then
276
// `super.init(…)` or `self.init(…)` runs on the
277
// object this constructor is itself being run on,
278
// so it is bounded the same way a construction is —
279
// and writes that receiver's own state, so it
280
// disqualifies the strict bit just as writing a
281
// field directly does
282
_disqualify_strict_only()
283
284
let receiver_type = _typer.try_type(member.left)
285
286
if !receiver_type? then
287
_disqualify_because("ctor-chain-receiver-untyped")
288
return
289
fi
290
291
_add_construction_edges(receiver_type.find_member("init"))
292
return
293
fi
294
295
let as_identifier = member.try_copy_as_identifer()
296
297
if as_identifier? then
298
let symbol = try_find(as_identifier)
299
300
if symbol? then
301
if _is_pure_function_valued(symbol) then
302
return
303
fi
304
305
_add_callee_edges(symbol)
306
return
307
fi
308
fi
309
310
let left_type = _typer.try_type(member.left)
311
312
if !left_type? then
313
_disqualify_because("call-receiver-untyped")
314
return
315
fi
316
317
let member_symbol = left_type.find_member(member.identifier.name)
318
319
if member_symbol? /\ _is_pure_function_valued(member_symbol) /\ member_symbol.is_field then
320
return
321
fi
322
323
_add_callee_edges(member_symbol)
324
return
325
fi
326
327
if isa Trees.Expressions.RECURSE(target) then
328
_add_callee(_current_function)
329
return
330
fi
331
332
_disqualify_because("call-target-shape")
333
si
334
335
// ==== operators ====
336
337
visit(binary: Expressions.BINARY) is
338
if !_current? then
339
return
340
fi
341
342
_add_operator_edges(binary.operation, binary.left, binary.right)
343
si
344
345
visit(unary: Expressions.UNARY) is
346
if !_current? then
347
return
348
fi
349
350
_add_operator_edges(unary.operation, unary.right, null)
351
si
352
353
_add_operator_edges(
354
operation: Identifiers.Identifier?,
355
left: Trees.Expressions.Expression?,
356
right: Trees.Expressions.Expression?
357
) is
358
if !operation? then
359
_disqualify_because("operator-unresolved")
360
return
361
fi
362
363
// free operator functions visible in scope: the innate
364
// operators and user-defined operators share one group
365
let group = find(operation.name)
366
367
if group? then
368
_add_callee_edges(group)
369
fi
370
371
// `==` has a single compiler-generated implementation:
372
// `==` and `!=` both carry the operation name `==` (the
373
// parser rewrites `!=`), and neither can be overloaded or
374
// overridden as a member. There is never a member operator
375
// to bound, so the member lookup — which otherwise
376
// disqualifies the function whenever an operand's type is
377
// not trivially derivable — is skipped.
378
//
379
// `=~` and `<>` are skipped for a different reason: every
380
// declaration is store-free by construction, because
381
// CHECK_PURE_OVERRIDES rejects any that is not declared
382
// pure or provably store-free. A member lookup could only
383
// find implementations already known safe, and would
384
// disqualify on operands whose type is not derivable here
385
// — a lambda parameter, or a bare type parameter compared
386
// through the runtime's comparer, where the comparison can
387
// dispatch to any implementation at all. Reflected forms
388
// reach Equals/CompareTo, which the runtime contract
389
// treats as side-effect-free, so they are trusted the same
390
// way.
391
if operation.name =~ "==" \/ operation.name =~ "=~" \/ operation.name =~ "<>" then
392
return
393
fi
394
395
// operator members can only be bounded when the operand
396
// types are known
397
_add_member_operator_edges(operation.name, left)
398
399
if right? then
400
_add_member_operator_edges(operation.name, right)
401
fi
402
si
403
404
_add_member_operator_edges(name: string, operand: Trees.Expressions.Expression?) is
405
let operand_type = _typer.try_type(operand)
406
407
if !operand_type? then
408
// The operand's type is not trivially derivable, so a
409
// member operator on it cannot be bounded here — the
410
// same position a call on an untypable receiver is
411
// in, and answered the same way. The free and innate
412
// operators are already bounded through the operator
413
// group above.
414
_disqualify_because("member-operator-unresolved")
415
416
return
417
fi
418
419
let member_symbol = operand_type.find_member(name)
420
421
// A member hidden from operator resolution is never what an
422
// operator expression calls, so following its call edge would
423
// bound the enclosing function by a method it cannot invoke.
424
//
425
// Soundness rests on this matching `COMPILE_OPERATORS`, which
426
// discards the same members when it gathers candidates. Both
427
// ask `HIDDEN_OPERATOR_MEMBERS`, so the two cannot drift: the
428
// operand ends up bounded by the operator that really runs,
429
// which for these types is an innate already classified by
430
// `STORE_FREE_INNATES`.
431
//
432
// A group is skipped only when every function in it is hidden,
433
// so a same-named user overload is still bounded as before.
434
if member_symbol? /\ !HIDDEN_OPERATOR_MEMBERS.is_hidden(member_symbol) then
435
_add_callee_edges(member_symbol)
436
fi
437
si
438
439
// ==== reads ====
440
441
visit(identifier: Expressions.IDENTIFIER) is
442
if !_current? then
443
return
444
fi
445
446
// an unresolvable bare name is either an error compile-
447
// expressions will report or a contextual load (a unit
448
// variant); neither can store
449
_classify_member_read(try_find(identifier.identifier))
450
si
451
452
visit(member: Expressions.MEMBER) is
453
if !_current? then
454
return
455
fi
456
457
let as_identifier = member.try_copy_as_identifer()
458
459
if as_identifier? then
460
let symbol = try_find(as_identifier)
461
462
if symbol? then
463
_classify_member_read(symbol)
464
return
465
fi
466
fi
467
468
let left_type = _typer.try_type(member.left)
469
470
if left_type? then
471
let member_symbol = left_type.find_member(member.identifier.name)
472
473
if member_symbol? then
474
_classify_member_read(member_symbol)
475
return
476
fi
477
fi
478
479
// untyped receiver: if this member turns out to be a
480
// property, its getter could run arbitrary code
481
_disqualify_because("member-receiver-untyped")
482
si
483
484
visit(index: Expressions.INDEX) is
485
if !_current? then
486
return
487
fi
488
489
let left_type = _typer.try_type(index.left)
490
491
if !left_type? then
492
_disqualify_because("index-receiver-untyped")
493
return
494
fi
495
496
if isa Semantic.Types.ARRAY(left_type) then
497
// array element read; element stores only occur as
498
// assignment targets, which are classified separately
499
return
500
fi
501
502
// an indexer read runs the receiver type's get_Item —
503
// bound it like any other member call
504
_add_callee_edges(left_type.find_member(Semantic.Symbols.INDEXER_NAMES.read))
505
si
506
507
visit(recurse: Expressions.RECURSE) is
508
if !_current? then
509
return
510
fi
511
512
_add_callee(_current_function)
513
si
514
515
// ==== type application ====
516
517
// `a.b[X]` where `X` reads as both a type argument and an index
518
// expression. Resolve-type-expressions settles the index
519
// reading when the type argument fails to resolve, and then the
520
// INDEX node it built is walked and classified in its own
521
// right, leaving nothing to do here.
522
visit(ambiguous: Expressions.AMBIGUOUS_EXPRESSION) is
523
if !_current? then
524
return
525
fi
526
527
if ambiguous.result == Expressions.AmbiguousExpressionResult.INDEX then
528
return
529
fi
530
531
_classify_type_application(ambiguous.result, ambiguous.left, ambiguous.identifier)
532
si
533
534
// `a.b[X]` where `X` can only be a type argument. Applying type
535
// arguments to a generic type or member is a read, so it
536
// classifies exactly as the same member read without them
537
// would; a call spelt this way is wrapped in a CALL node, which
538
// is classified separately and on its own terms.
539
visit(generic_application: Expressions.GENERIC_APPLICATION) is
540
if !_current? then
541
return
542
fi
543
544
_classify_type_application(
545
generic_application.result,
546
generic_application.left,
547
generic_application.identifier
548
)
549
si
550
551
_classify_type_application(
552
result: Expressions.AmbiguousExpressionResult,
553
left: Trees.Expressions.Expression?,
554
identifier: Identifiers.Identifier
555
) is
556
// Both node kinds walk their receiver only once a later
557
// pass has settled what the application applies to, which
558
// for every node reaching this pass means not yet. So the
559
// receiver has to be walked from here — otherwise a call or
560
// an index sitting in it would never be classified at all.
561
if result == Expressions.AmbiguousExpressionResult.UNKNOWN /\ left? then
562
left.walk(self)
563
fi
564
565
if !left? then
566
_classify_member_read(try_find(identifier))
567
return
568
fi
569
570
// a receiver that is itself a name resolves as one
571
// qualified name — the route a namespace-qualified type or
572
// a union's variant arrives by. The joined name exists only
573
// for this lookup, so its spans are the identifier's own.
574
let left_as_identifier = left.try_copy_as_identifer()
575
576
if left_as_identifier? then
577
let symbol =
578
try_find(
579
Identifiers.QUALIFIED(
580
identifier.location,
581
left_as_identifier,
582
identifier.name,
583
identifier.location,
584
identifier.right_location
585
)
586
)
587
588
if symbol? then
589
_classify_member_read(symbol)
590
return
591
fi
592
fi
593
594
let left_type = _typer.try_type(left)
595
596
if !left_type? then
597
_disqualify()
598
return
599
fi
600
601
let member_symbol = left_type.find_member(identifier.name)
602
603
if !member_symbol? then
604
// untyped or unresolvable member: if it turns out to be
605
// a property, its getter could run arbitrary code
606
_disqualify()
607
return
608
fi
609
610
_classify_member_read(member_symbol)
611
si
612
613
si
614
si