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
// the operators in scope that take every operand as an
364
// argument, as the operator compiler gathers them; instance
365
// operators are bounded through the operand types below
366
let group = SCOPE_OPERATOR_CANDIDATES.find(_symbol_table, operation.location, operation.name)
367
368
if group? then
369
_add_callee_edges(group)
370
fi
371
372
// `==` has a single compiler-generated implementation:
373
// `==` and `!=` both carry the operation name `==` (the
374
// parser rewrites `!=`), and neither can be overloaded or
375
// overridden as a member. There is never a member operator
376
// to bound, so the member lookup — which otherwise
377
// disqualifies the function whenever an operand's type is
378
// not trivially derivable — is skipped.
379
//
380
// `=~` and `<>` are skipped for a different reason: every
381
// declaration is store-free by construction, because
382
// CHECK_PURE_OVERRIDES rejects any that is not declared
383
// pure or provably store-free. A member lookup could only
384
// find implementations already known safe, and would
385
// disqualify on operands whose type is not derivable here
386
// — a lambda parameter, or a bare type parameter compared
387
// through the runtime's comparer, where the comparison can
388
// dispatch to any implementation at all. Reflected forms
389
// reach Equals/CompareTo, which the runtime contract
390
// treats as side-effect-free, so they are trusted the same
391
// way.
392
if operation.name =~ "==" \/ operation.name =~ "=~" \/ operation.name =~ "<>" then
393
return
394
fi
395
396
// operator members can only be bounded when the operand
397
// types are known
398
_add_member_operator_edges(operation.name, left)
399
400
if right? then
401
_add_member_operator_edges(operation.name, right)
402
fi
403
si
404
405
_add_member_operator_edges(name: string, operand: Trees.Expressions.Expression?) is
406
let operand_type = _typer.try_type(operand)
407
408
if !operand_type? then
409
// The operand's type is not trivially derivable, so a
410
// member operator on it cannot be bounded here — the
411
// same position a call on an untypable receiver is
412
// in, and answered the same way. The free and innate
413
// operators are already bounded through the operator
414
// group above.
415
_disqualify_because("member-operator-unresolved")
416
417
return
418
fi
419
420
let member_symbol = operand_type.find_member(name)
421
422
// A member hidden from operator resolution is never what an
423
// operator expression calls, so following its call edge would
424
// bound the enclosing function by a method it cannot invoke.
425
//
426
// Soundness rests on this matching `COMPILE_OPERATORS`, which
427
// discards the same members when it gathers candidates. Both
428
// ask `HIDDEN_OPERATOR_MEMBERS`, so the two cannot drift: the
429
// operand ends up bounded by the operator that really runs,
430
// which for these types is an innate already classified by
431
// `STORE_FREE_INNATES`.
432
//
433
// A group is skipped only when every function in it is hidden,
434
// so a same-named user overload is still bounded as before.
435
if member_symbol? /\ !HIDDEN_OPERATOR_MEMBERS.is_hidden(member_symbol) then
436
_add_callee_edges(member_symbol)
437
fi
438
si
439
440
// ==== reads ====
441
442
visit(identifier: Expressions.IDENTIFIER) is
443
if !_current? then
444
return
445
fi
446
447
// an unresolvable bare name is either an error compile-
448
// expressions will report or a contextual load (a unit
449
// variant); neither can store
450
_classify_member_read(try_find(identifier.identifier))
451
si
452
453
visit(member: Expressions.MEMBER) is
454
if !_current? then
455
return
456
fi
457
458
let as_identifier = member.try_copy_as_identifer()
459
460
if as_identifier? then
461
let symbol = try_find(as_identifier)
462
463
if symbol? then
464
_classify_member_read(symbol)
465
return
466
fi
467
fi
468
469
let left_type = _typer.try_type(member.left)
470
471
if left_type? then
472
let member_symbol = left_type.find_member(member.identifier.name)
473
474
if member_symbol? then
475
_classify_member_read(member_symbol)
476
return
477
fi
478
fi
479
480
// untyped receiver: if this member turns out to be a
481
// property, its getter could run arbitrary code
482
_disqualify_because("member-receiver-untyped")
483
si
484
485
visit(index: Expressions.INDEX) is
486
if !_current? then
487
return
488
fi
489
490
let left_type = _typer.try_type(index.left)
491
492
if !left_type? then
493
_disqualify_because("index-receiver-untyped")
494
return
495
fi
496
497
if isa Semantic.Types.ARRAY(left_type) then
498
// array element read; element stores only occur as
499
// assignment targets, which are classified separately
500
return
501
fi
502
503
// an indexer read runs the receiver type's get_Item —
504
// bound it like any other member call
505
_add_callee_edges(left_type.find_member(Semantic.Symbols.INDEXER_NAMES.read))
506
si
507
508
visit(recurse: Expressions.RECURSE) is
509
if !_current? then
510
return
511
fi
512
513
_add_callee(_current_function)
514
si
515
516
// ==== type application ====
517
518
// `a.b[X]` where `X` reads as both a type argument and an index
519
// expression. Resolve-type-expressions settles the index
520
// reading when the type argument fails to resolve, and then the
521
// INDEX node it built is walked and classified in its own
522
// right, leaving nothing to do here.
523
visit(ambiguous: Expressions.AMBIGUOUS_EXPRESSION) is
524
if !_current? then
525
return
526
fi
527
528
if ambiguous.result == Expressions.AmbiguousExpressionResult.INDEX then
529
return
530
fi
531
532
_classify_type_application(ambiguous.result, ambiguous.left, ambiguous.identifier)
533
si
534
535
// `a.b[X]` where `X` can only be a type argument. Applying type
536
// arguments to a generic type or member is a read, so it
537
// classifies exactly as the same member read without them
538
// would; a call spelt this way is wrapped in a CALL node, which
539
// is classified separately and on its own terms.
540
visit(generic_application: Expressions.GENERIC_APPLICATION) is
541
if !_current? then
542
return
543
fi
544
545
_classify_type_application(
546
generic_application.result,
547
generic_application.left,
548
generic_application.identifier
549
)
550
si
551
552
_classify_type_application(
553
result: Expressions.AmbiguousExpressionResult,
554
left: Trees.Expressions.Expression?,
555
identifier: Identifiers.Identifier
556
) is
557
// Both node kinds walk their receiver only once a later
558
// pass has settled what the application applies to, which
559
// for every node reaching this pass means not yet. So the
560
// receiver has to be walked from here — otherwise a call or
561
// an index sitting in it would never be classified at all.
562
if result == Expressions.AmbiguousExpressionResult.UNKNOWN /\ left? then
563
left.walk(self)
564
fi
565
566
if !left? then
567
_classify_member_read(try_find(identifier))
568
return
569
fi
570
571
// a receiver that is itself a name resolves as one
572
// qualified name — the route a namespace-qualified type or
573
// a union's variant arrives by. The joined name exists only
574
// for this lookup, so its spans are the identifier's own.
575
let left_as_identifier = left.try_copy_as_identifer()
576
577
if left_as_identifier? then
578
let symbol =
579
try_find(
580
Identifiers.QUALIFIED(
581
identifier.location,
582
left_as_identifier,
583
identifier.name,
584
identifier.location,
585
identifier.right_location
586
)
587
)
588
589
if symbol? then
590
_classify_member_read(symbol)
591
return
592
fi
593
fi
594
595
let left_type = _typer.try_type(left)
596
597
if !left_type? then
598
_disqualify()
599
return
600
fi
601
602
let member_symbol = left_type.find_member(identifier.name)
603
604
if !member_symbol? then
605
// untyped or unresolvable member: if it turns out to be
606
// a property, its getter could run arbitrary code
607
_disqualify()
608
return
609
fi
610
611
_classify_member_read(member_symbol)
612
si
613
614
si
615
si