Skip to content
← Back

src/syntax/process/compile-expressions/compile_loops_and_exceptions.ghul

1
namespace Syntax.Process is
2
use Logging
3
4
use Semantic.LEAST_UPPER_BOUND_MAP
5
6
// Compiles `while` / `do` loops and `try` / `catch` statements,
7
// and the flow-sensitive narrowing around them. Split out of
8
// COMPILE_EXPRESSIONS, which delegates the matching pre / visit
9
// methods here. The `super.pre` / `super.visit` base-visitor
10
// calls stay in the visitor's thin stubs; the methods here are
11
// the enclosed logic.
12
//
13
// A loop drops narrows on variables its body writes (they cannot
14
// survive the back-edge) — see loop_kept_env, which the `for`
15
// loop on the visitor also uses. A `try` opens a TRY_FLOW_FRAME
16
// tracking whether the body / handlers can complete normally;
17
// narrowing established inside a try is discarded conservatively
18
// (an exception can leave the body anywhere).
19
class COMPILE_LOOPS_AND_EXCEPTIONS is
20
_logger: Logger
21
_innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup
22
_flow: NARROWING_FLOW
23
_condition_analyzer: CONDITION_ANALYZER
24
_conditionals: COMPILE_CONDITIONALS
25
_visitor: COMPILE_EXPRESSIONS
26
_try_flow_stack: Collections.LIST[TRY_FLOW_FRAME]
27
_loop_kept_stack: Collections.LIST[NARROW_ENV]
28
29
// Heap epoch captured at each pre_do, compared at visit_do:
30
// the kept environment was snapshot before the loop's
31
// condition and body walked, so a kill during either means
32
// its heap facts cannot be restored after the loop.
33
_loop_epoch_stack: Collections.LIST[int]
34
_loop_mark_stack: Collections.LIST[int]
35
36
// Settles loop-expression result types from break contributions
37
// (see LOOP_RESULT_SETTLER). The makers are wired to the
38
// reflected-runtime lookups here so unit fixtures can inject
39
// stand-ins.
40
_settler: LOOP_RESULT_SETTLER
41
42
init(
43
logger: Logger,
44
innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup,
45
flow: NARROWING_FLOW,
46
condition_analyzer: CONDITION_ANALYZER,
47
conditionals: COMPILE_CONDITIONALS,
48
visitor: COMPILE_EXPRESSIONS,
49
try_flow_stack: Collections.LIST[TRY_FLOW_FRAME],
50
loop_kept_stack: Collections.LIST[NARROW_ENV]
51
) is
52
super.init()
53
54
_logger = logger
55
_innate_symbol_lookup = innate_symbol_lookup
56
_flow = flow
57
_condition_analyzer = condition_analyzer
58
_conditionals = conditionals
59
_visitor = visitor
60
_try_flow_stack = try_flow_stack
61
_loop_kept_stack = loop_kept_stack
62
_loop_epoch_stack = Collections.LIST[int]()
63
_loop_mark_stack = Collections.LIST[int]()
64
_settler = LOOP_RESULT_SETTLER(
65
(t: Semantic.Types.Type) => innate_symbol_lookup.get_optional_type(t),
66
(t: Semantic.Types.Type) => innate_symbol_lookup.get_maybe_type(t),
67
(t: Semantic.Types.Type) => t.as_optional()
68
)
69
si
70
71
// The narrowing environment to use inside and after a loop
72
// whose body is `body`. A loop body may run any number of
73
// times, so a narrow on a variable the body *writes* cannot
74
// be assumed across the back-edge — those narrows are
75
// dropped. A narrow on a variable the body never writes is
76
// loop-invariant and survives. The body is scanned
77
// syntactically for assignment / `ref` targets.
78
loop_kept_env(body: Trees.Node) -> NARROW_ENV is
79
let env = _flow.current_env
80
81
if env.is_bottom then
82
return env.copy()
83
fi
84
85
let collector = LOOP_ASSIGNMENT_COLLECTOR()
86
body.walk(collector)
87
88
let kept = NARROW_ENV()
89
90
for v in env.variables do
91
if let v_name = v.name, t = env.narrowed_type_of(v) then
92
if !collector.names.contains(v_name) then
93
kept.set_narrow(v, t)
94
kept.copy_crossings_of(v, env)
95
fi
96
fi
97
od
98
99
// Definite-assignment is not subject to the kill-set: a
100
// variable assigned before the loop stays assigned
101
// regardless of what the body writes. Body-only
102
// assignments are dropped by restoring `kept` after the
103
// loop (a loop may run zero times).
104
for v in env.assigned_variables do
105
kept.set_assigned(v)
106
od
107
108
for v in env.non_null_variables do
109
if !collector.names.contains(v.name) then
110
kept.set_non_null(v)
111
kept.copy_crossings_of(v, env)
112
fi
113
od
114
115
return kept
116
si
117
118
pre_try(`try: Trees.Statements.TRY) -> bool is
119
// Record the pre-try environment. Its narrowing facts
120
// are discarded after the try (an exception can leave
121
// the body anywhere), but its definite-assignment facts
122
// survive — those assignments already happened.
123
let frame = TRY_FLOW_FRAME(_flow.current_env.copy())
124
_try_flow_stack.add(frame)
125
126
// Drive the walk so the finally body gets an entry
127
// environment of its own. It runs on every path out of
128
// the try — completing, returning, or throwing — so it
129
// is never unreachable, and because an exception can
130
// leave the body anywhere it enters with only the
131
// pre-try definite-assignment facts, exactly as a catch
132
// handler does.
133
`try.body.walk(_visitor)
134
135
if !frame.body_seen then
136
frame.body_seen = true
137
138
if !_flow.is_unreachable then
139
frame.can_complete = true
140
fi
141
fi
142
143
for c in `try.catches do
144
c.walk(_visitor)
145
od
146
147
if `try.`finally? then
148
let finally_body = `try.`finally
149
150
// The finally runs on every path out of the try, so a
151
// fact proven before the try holds there too, unless
152
// the body or a catch writes the local it was proven
153
// on. The finally's own writes are not collected: they
154
// invalidate from the write onward, which the ordinary
155
// walk does, rather than at entry.
156
let written = LOOP_ASSIGNMENT_COLLECTOR()
157
158
`try.body.walk(written)
159
160
for c in `try.catches do
161
c.walk(written)
162
od
163
164
// Keyed by the written name: an assignment target has
165
// no resolved symbol on it at this point, so there is
166
// no identity here to ask instead. Two locals sharing
167
// a name conflate, which costs a narrow that could
168
// have been kept and never keeps one that should have
169
// been dropped.
170
_flow.set_env(
171
frame.entry.with_only_assigned_and_kept_locals(
172
v =>
173
if let name = v.name then
174
!written.names.contains(name)
175
else
176
false
177
fi))
178
179
finally_body.walk(_visitor)
180
181
if _flow.is_unreachable then
182
frame.finally_diverges = true
183
fi
184
fi
185
186
return true
187
si
188
189
// The frame for the `try` currently being walked, or null.
190
_try_flow_frame: TRY_FLOW_FRAME? =>
191
if _try_flow_stack.count > 0 then
192
_try_flow_stack[_try_flow_stack.count - 1]
193
else
194
null
195
fi
196
197
visit_try(`try: Trees.Statements.TRY) is
198
let frame = _try_flow_frame
199
200
if _try_flow_stack.count > 0 then
201
_try_flow_stack.remove_at(_try_flow_stack.count - 1)
202
fi
203
204
if frame? then
205
// Conservative: an exception can leave the try body
206
// at any point, so no narrowing survives the try —
207
// only the pre-try definite-assignment facts. When
208
// neither the body nor any handler can complete
209
// normally, or the finally cannot, control never
210
// falls through the try.
211
if frame.can_complete /\ !frame.finally_diverges then
212
_flow.set_env(frame.entry.with_only_assigned())
213
else
214
_flow.set_unreachable()
215
fi
216
else
217
_flow.set_env(NARROW_ENV())
218
fi
219
220
if
221
`try.catches.count == 0 /\
222
!`try.`finally?
223
then
224
_logger.warn(
225
`try.keyword_location,
226
"try-without-handler",
227
"try statement has no catch clause and no finally clause",
228
`try.keyword_location,
229
"help: add a catch clause, a finally clause, or both")
230
fi
231
si
232
233
pre_catch(`catch: Trees.Statements.CATCH) -> bool is
234
let frame = _try_flow_frame
235
236
// The first catch is reached right after the try body,
237
// so the current environment is the body's exit: record
238
// whether the body can complete normally.
239
if frame? /\ !frame.body_seen then
240
frame.body_seen = true
241
242
if !_flow.is_unreachable then
243
frame.can_complete = true
244
fi
245
fi
246
247
// A throw can land anywhere in the try body, so nothing
248
// narrowed there can be assumed in the handler — the
249
// catch body is walked with only the pre-try
250
// definite-assignment facts.
251
_flow.set_env(
252
if frame? then frame.entry.with_only_assigned() else NARROW_ENV() fi
253
)
254
255
return false
256
si
257
258
visit_catch(`catch: Trees.Statements.CATCH) is
259
// A catch handler that completes normally is a path that
260
// reaches the end of the try statement.
261
let frame = _try_flow_frame
262
263
if frame? /\ !_flow.is_unreachable then
264
frame.can_complete = true
265
fi
266
267
if !`catch.variable? then
268
return
269
fi
270
271
let variable = `catch.variable
272
273
// Catch parameters must always have an explicit type —
274
// their whole purpose is to identify which exception
275
// shape the clause handles. Type inference (placeholder
276
// + LUB across writes) does not apply here, so the
277
// generalised let-without-type relaxation in
278
// pre(VARIABLE) doesn't extend to catch.
279
if isa Trees.TypeExpressions.INFER(variable.type_expression) then
280
_logger.error(variable.location, "catch variable must have an explicit type")
281
return
282
fi
283
284
let type = variable.type_expression.type
285
286
if !type? then
287
return
288
fi
289
290
let exception_type = _innate_symbol_lookup.get_exception_type()
291
292
if !exception_type.is_assignable_from(type) then
293
_logger.error(variable.type_expression.location, "cannot catch {type} because it does not derive from System.Exception")
294
fi
295
si
296
297
pre_do(`do: Trees.Statements.DO) -> bool is
298
// Controlled walk that mirrors `pre_if_branch`: compute
299
// the loop's kill-set environment, walk the condition (or
300
// `while let` binding) under it, derive the body's
301
// narrowing environment from that, walk the body, and
302
// stash the kept environment for visit(DO) to restore
303
// after the loop. Per-iteration narrows established by the
304
// condition or binding flow into the body; the kill-set
305
// drops any narrow on a variable the loop writes so
306
// back-edge invariance is preserved.
307
let kept = loop_kept_env(`do)
308
_loop_kept_stack.add(kept)
309
_loop_epoch_stack.add(_flow.heap_epoch)
310
_loop_mark_stack.add(_flow.crossing_mark)
311
312
_flow.set_env(kept)
313
314
if `do.binding? then
315
_conditionals.check_refutable_binding(`do.binding)
316
elif `do.condition? then
317
let condition = `do.condition
318
let epoch = _flow.heap_epoch
319
let mark = _flow.crossing_mark
320
321
condition.walk(_visitor)
322
323
let facts = _condition_analyzer.analyze_condition(condition, kept)
324
325
// The body environment derives from the pre-condition
326
// snapshot; a store during the condition's own walk
327
// invalidates its heap facts, and its calls attach as
328
// crossings.
329
if _flow.heap_killed_since(epoch) then
330
facts.then_env.drop_heap_facts()
331
else
332
_flow.adopt_crossings_since(facts.then_env, mark)
333
fi
334
335
_flow.set_env(facts.then_env)
336
fi
337
338
`do.body.walk(_visitor)
339
340
return true
341
si
342
343
visit_do(`do: Trees.Statements.DO) is
344
if _loop_kept_stack.count > 0 then
345
let kept = _loop_kept_stack[_loop_kept_stack.count - 1]
346
_loop_kept_stack.remove_at(_loop_kept_stack.count - 1)
347
348
let epoch = _loop_epoch_stack[_loop_epoch_stack.count - 1]
349
_loop_epoch_stack.remove_at(_loop_epoch_stack.count - 1)
350
351
let mark = _loop_mark_stack[_loop_mark_stack.count - 1]
352
_loop_mark_stack.remove_at(_loop_mark_stack.count - 1)
353
354
if !`do.condition? /\ !`do.binding? /\ !_loop_body_has_break(`do.body) then
355
// An unconditional loop with no `break` cannot
356
// be exited — control never falls through it.
357
_flow.set_unreachable()
358
else
359
// The kept environment was snapshot before the
360
// loop walked; the assignment kill-set covers
361
// direct writes but not member stores inside the
362
// loop, so a store during the walk drops its heap
363
// facts before restoration, and the loop's calls
364
// attach as crossings.
365
if _flow.heap_killed_since(epoch) then
366
kept.drop_heap_facts()
367
else
368
_flow.adopt_crossings_since(kept, mark)
369
fi
370
371
_flow.set_env(kept)
372
fi
373
fi
374
si
375
376
// True iff `body` contains a `break` targeting the loop it
377
// is the body of — a `break` inside a nested loop does not
378
// count (it targets that inner loop).
379
_loop_body_has_break(body: Trees.Statements.LIST) -> bool is
380
let finder = LOOP_BREAK_FINDER()
381
body.walk(finder)
382
383
return finder.found
384
si
385
386
// --- loop-as-expression value machinery ---
387
388
push_loop_value_frame(
389
node: Trees.Statements.Statement,
390
label_name: string?,
391
wants_value: bool,
392
expected_type: Semantic.Types.Type?,
393
expected_type_error_message: string?
394
) is
395
let frame = LOOP_VALUE_FRAME(node, label_name, wants_value, expected_type, expected_type_error_message)
396
397
_visitor.loop_value_frames.add(frame)
398
si
399
400
// The innermost open loop frame that consumes a value — the
401
// target of a valued `break`. Intermediate loops that are not
402
// expressions are exited through: the value needs a taker, so
403
// the search skips frames whose loop discards its result.
404
// Null when no enclosing loop is an expression.
405
innermost_consuming_frame() -> LOOP_VALUE_FRAME? is
406
let frames = _visitor.loop_value_frames
407
408
let i mut = frames.count - 1
409
410
while i >= 0 do
411
let frame = frames[i]
412
413
if frame.wants_value then
414
return frame
415
fi
416
417
i = i - 1
418
od
419
420
return null
421
si
422
423
// The innermost open loop frame, for a `break` that names no
424
// label. Null outside any loop.
425
current_loop_frame() -> LOOP_VALUE_FRAME? is
426
let frames = _visitor.loop_value_frames
427
428
if frames.count == 0 then
429
return null
430
fi
431
432
return frames[frames.count - 1]
433
si
434
435
// The open loop frame whose label is `name`, innermost first.
436
// Null when no enclosing labelled loop carries that name.
437
find_labelled_loop_frame(name: string) -> LOOP_VALUE_FRAME? is
438
let frames = _visitor.loop_value_frames
439
440
let i mut = frames.count - 1
441
442
while i >= 0 do
443
let frame = frames[i]
444
445
if frame.label_name? /\ frame.label_name =~ name then
446
return frame
447
fi
448
449
i = i - 1
450
od
451
452
return null
453
si
454
455
// Pops the innermost frame (which must be `node`'s) and settles
456
// the loop's expression value: the optional-wrapped LUB of every
457
// valued-break contribution. With an expected type and no
458
// contributions the loop yields absence everywhere, so the
459
// expected type stands. With neither, the type cannot be
460
// inferred.
461
pop_and_settle_loop_value(node: Trees.Statements.Statement) is
462
let frames = _visitor.loop_value_frames
463
464
assert frames.count > 0 else "loop value frame underflow"
465
466
let frame = frames[frames.count - 1]
467
468
assert frame.node == node else "loop value frame head is not the loop being visited"
469
470
frames.remove_at(frames.count - 1)
471
472
// A valued break under a loop that consumes nothing was
473
// already reported at the break itself; nothing to settle.
474
if !frame.wants_value then
475
return
476
fi
477
478
let result = _settler.settle(
479
frame.contributions,
480
frame.expected_type
481
)
482
483
if !result? then
484
// A loop ending a body whose return is still being
485
// inferred, reached only as the tail of that body or of
486
// one of its arms, delivers no value: without a valued
487
// break it is the statement it was written as.
488
if node.void_tolerated /\ frame.contributions.count == 0 then
489
return
490
fi
491
492
_logger.error(node.location, "cannot infer the type of this loop")
493
494
return
495
fi
496
497
node.compile_expressions_state.value = IR.Values.BLOCK(result)
498
499
_visitor.declare_composite_spill_field_for(node, node.compile_expressions_state.value)
500
si
501
si
502
503
// One open loop's value bookkeeping: what its valued `break`s
504
// contribute, whether anything consumes the result, and the label
505
// name when the loop is written under a LABELLED wrapper. Lives on
506
// COMPILE_EXPRESSIONS.loop_value_frames for the walk's duration.
507
class LOOP_VALUE_FRAME is
508
node: Trees.Statements.Statement
509
label_name: string?
510
wants_value: bool
511
expected_type: Semantic.Types.Type?
512
expected_type_error_message: string?
513
contributions: Collections.MutableList[Semantic.Types.Type]
514
has_valued_break: bool public
515
valued_break_location: Source.LOCATION? public
516
517
init(
518
node: Trees.Statements.Statement,
519
label_name: string?,
520
wants_value: bool,
521
expected_type: Semantic.Types.Type?,
522
expected_type_error_message: string?
523
) is
524
self.node = node
525
self.label_name = label_name
526
self.wants_value = wants_value
527
self.expected_type = expected_type
528
self.expected_type_error_message = expected_type_error_message
529
self.contributions = Collections.LIST[Semantic.Types.Type]()
530
self.has_valued_break = false
531
self.valued_break_location = null
532
si
533
534
note_contribution(type: Semantic.Types.Type, location: Source.LOCATION) is
535
contributions.add(type)
536
537
if !has_valued_break then
538
has_valued_break = true
539
valued_break_location = location
540
fi
541
si
542
si
543
si