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
_visitor.end_try_body(`try)
135
136
if !frame.body_seen then
137
frame.body_seen = true
138
139
if !_flow.is_unreachable then
140
frame.can_complete = true
141
fi
142
fi
143
144
for c in `try.catches do
145
c.walk(_visitor)
146
od
147
148
if `try.`finally? then
149
let finally_body = `try.`finally
150
151
// The finally runs on every path out of the try, so a
152
// fact proven before the try holds there too, unless
153
// the body or a catch writes the local it was proven
154
// on. The finally's own writes are not collected: they
155
// invalidate from the write onward, which the ordinary
156
// walk does, rather than at entry.
157
let written = LOOP_ASSIGNMENT_COLLECTOR(true)
158
159
`try.body.walk(written)
160
161
for c in `try.catches do
162
c.walk(written)
163
od
164
165
// The body and catches have been compiled, so a plain
166
// assignment names the symbol it stores to, and a local
167
// of the same name declared inside the try is not
168
// mistaken for the one the fact is about. A target with
169
// no store to read falls back to its name, which can
170
// only cost a narrow, never keep a stale one.
171
_flow.set_env(
172
frame.entry.with_only_assigned_and_kept_locals(
173
v => v.name? /\ !written.wrote(v)))
174
175
finally_body.walk(_visitor)
176
177
if _flow.is_unreachable then
178
frame.finally_diverges = true
179
fi
180
fi
181
182
return true
183
si
184
185
// The frame for the `try` currently being walked, or null.
186
_try_flow_frame: TRY_FLOW_FRAME? =>
187
if _try_flow_stack.count > 0 then
188
_try_flow_stack[_try_flow_stack.count - 1]
189
else
190
null
191
fi
192
193
visit_try(`try: Trees.Statements.TRY) is
194
let frame = _try_flow_frame
195
196
if _try_flow_stack.count > 0 then
197
_try_flow_stack.remove_at(_try_flow_stack.count - 1)
198
fi
199
200
if frame? then
201
// Conservative: an exception can leave the try body
202
// at any point, so no narrowing survives the try —
203
// only the pre-try definite-assignment facts. When
204
// neither the body nor any handler can complete
205
// normally, or the finally cannot, control never
206
// falls through the try.
207
if frame.can_complete /\ !frame.finally_diverges then
208
_flow.set_env(frame.entry.with_only_assigned())
209
else
210
_flow.set_unreachable()
211
fi
212
else
213
_flow.set_env(NARROW_ENV())
214
fi
215
216
if
217
`try.catches.count == 0 /\
218
!`try.`finally?
219
then
220
_logger.warn(
221
`try.keyword_location,
222
"try-without-handler",
223
"try statement has no catch clause and no finally clause",
224
`try.keyword_location,
225
"help: add a catch clause, a finally clause, or both")
226
fi
227
si
228
229
pre_catch(`catch: Trees.Statements.CATCH) -> bool is
230
let frame = _try_flow_frame
231
232
// The first catch is reached right after the try body,
233
// so the current environment is the body's exit: record
234
// whether the body can complete normally.
235
if frame? /\ !frame.body_seen then
236
frame.body_seen = true
237
238
if !_flow.is_unreachable then
239
frame.can_complete = true
240
fi
241
fi
242
243
// A throw can land anywhere in the try body, so nothing
244
// narrowed there can be assumed in the handler — the
245
// catch body is walked with only the pre-try
246
// definite-assignment facts.
247
_flow.set_env(
248
if frame? then frame.entry.with_only_assigned() else NARROW_ENV() fi
249
)
250
251
return false
252
si
253
254
visit_catch(`catch: Trees.Statements.CATCH) is
255
// A catch handler that completes normally is a path that
256
// reaches the end of the try statement.
257
let frame = _try_flow_frame
258
259
if frame? /\ !_flow.is_unreachable then
260
frame.can_complete = true
261
fi
262
263
if !`catch.variable? then
264
return
265
fi
266
267
let variable = `catch.variable
268
269
// Catch parameters must always have an explicit type —
270
// their whole purpose is to identify which exception
271
// shape the clause handles. Type inference (placeholder
272
// + LUB across writes) does not apply here, so the
273
// generalised let-without-type relaxation in
274
// pre(VARIABLE) doesn't extend to catch.
275
if isa Trees.TypeExpressions.INFER(variable.type_expression) then
276
_logger.error(variable.location, "catch variable must have an explicit type")
277
return
278
fi
279
280
let type = variable.type_expression.type
281
282
if !type? then
283
return
284
fi
285
286
let exception_type = _innate_symbol_lookup.get_exception_type()
287
288
if !exception_type.is_assignable_from(type) then
289
_logger.error(variable.type_expression.location, "cannot catch {type} because it does not derive from Ghul.Exception")
290
fi
291
si
292
293
pre_do(`do: Trees.Statements.DO) -> bool is
294
// Controlled walk that mirrors `pre_if_branch`: compute
295
// the loop's kill-set environment, walk the condition (or
296
// `while let` binding) under it, derive the body's
297
// narrowing environment from that, walk the body, and
298
// stash the kept environment for visit(DO) to restore
299
// after the loop. Per-iteration narrows established by the
300
// condition or binding flow into the body; the kill-set
301
// drops any narrow on a variable the loop writes so
302
// back-edge invariance is preserved.
303
let kept = loop_kept_env(`do)
304
_loop_kept_stack.add(kept)
305
_loop_epoch_stack.add(_flow.heap_epoch)
306
_loop_mark_stack.add(_flow.crossing_mark)
307
308
_flow.set_env(kept)
309
310
if `do.binding? then
311
_conditionals.check_refutable_binding(`do.binding)
312
elif `do.condition? then
313
let condition = `do.condition
314
let epoch = _flow.heap_epoch
315
let mark = _flow.crossing_mark
316
317
condition.walk(_visitor)
318
319
let facts = _condition_analyzer.analyze_condition(condition, kept)
320
321
// The body environment derives from the pre-condition
322
// snapshot; a store during the condition's own walk
323
// invalidates its heap facts, and its calls attach as
324
// crossings.
325
if _flow.heap_killed_since(epoch) then
326
facts.then_env.drop_heap_facts()
327
else
328
_flow.adopt_crossings_since(facts.then_env, mark)
329
fi
330
331
_flow.set_env(facts.then_env)
332
fi
333
334
`do.body.walk(_visitor)
335
336
return true
337
si
338
339
visit_do(`do: Trees.Statements.DO) is
340
if _loop_kept_stack.count > 0 then
341
let kept = _loop_kept_stack[_loop_kept_stack.count - 1]
342
_loop_kept_stack.remove_at(_loop_kept_stack.count - 1)
343
344
let epoch = _loop_epoch_stack[_loop_epoch_stack.count - 1]
345
_loop_epoch_stack.remove_at(_loop_epoch_stack.count - 1)
346
347
let mark = _loop_mark_stack[_loop_mark_stack.count - 1]
348
_loop_mark_stack.remove_at(_loop_mark_stack.count - 1)
349
350
if !`do.condition? /\ !`do.binding? /\ !_loop_body_has_break(`do.body) then
351
// An unconditional loop with no `break` cannot
352
// be exited — control never falls through it.
353
_flow.set_unreachable()
354
else
355
// The kept environment was snapshot before the
356
// loop walked; the assignment kill-set covers
357
// direct writes but not member stores inside the
358
// loop, so a store during the walk drops its heap
359
// facts before restoration, and the loop's calls
360
// attach as crossings.
361
if _flow.heap_killed_since(epoch) then
362
kept.drop_heap_facts()
363
else
364
_flow.adopt_crossings_since(kept, mark)
365
fi
366
367
_flow.set_env(kept)
368
fi
369
fi
370
si
371
372
// True iff `body` contains a `break` targeting the loop it
373
// is the body of — a `break` inside a nested loop does not
374
// count (it targets that inner loop).
375
_loop_body_has_break(body: Trees.Statements.LIST) -> bool is
376
let finder = LOOP_BREAK_FINDER()
377
body.walk(finder)
378
379
return finder.found
380
si
381
382
// --- loop-as-expression value machinery ---
383
384
push_loop_value_frame(
385
node: Trees.Statements.Statement,
386
label_name: string?,
387
wants_value: bool,
388
expected_type: Semantic.Types.Type?,
389
expected_type_error_message: string?
390
) is
391
let frame = LOOP_VALUE_FRAME(node, label_name, wants_value, expected_type, expected_type_error_message)
392
393
_visitor.loop_value_frames.add(frame)
394
si
395
396
// The innermost open loop frame that consumes a value — the
397
// target of a valued `break`. Intermediate loops that are not
398
// expressions are exited through: the value needs a taker, so
399
// the search skips frames whose loop discards its result.
400
// Null when no enclosing loop is an expression.
401
innermost_consuming_frame() -> LOOP_VALUE_FRAME? is
402
let frames = _visitor.loop_value_frames
403
404
let i mut = frames.count - 1
405
406
while i >= 0 do
407
let frame = frames[i]
408
409
if frame.wants_value then
410
return frame
411
fi
412
413
i = i - 1
414
od
415
416
return null
417
si
418
419
// The innermost open loop frame, for a `break` that names no
420
// label. Null outside any loop.
421
current_loop_frame() -> LOOP_VALUE_FRAME? is
422
let frames = _visitor.loop_value_frames
423
424
if frames.count == 0 then
425
return null
426
fi
427
428
return frames[frames.count - 1]
429
si
430
431
// The open loop frame whose label is `name`, innermost first.
432
// Null when no enclosing labelled loop carries that name.
433
find_labelled_loop_frame(name: string) -> LOOP_VALUE_FRAME? is
434
let frames = _visitor.loop_value_frames
435
436
let i mut = frames.count - 1
437
438
while i >= 0 do
439
let frame = frames[i]
440
441
if frame.label_name? /\ frame.label_name =~ name then
442
return frame
443
fi
444
445
i = i - 1
446
od
447
448
return null
449
si
450
451
// Pops the innermost frame (which must be `node`'s) and settles
452
// the loop's expression value: the optional-wrapped LUB of every
453
// valued-break contribution. With an expected type and no
454
// contributions the loop yields absence everywhere, so the
455
// expected type stands. With neither, the type cannot be
456
// inferred.
457
pop_and_settle_loop_value(node: Trees.Statements.Statement) is
458
let frames = _visitor.loop_value_frames
459
460
assert frames.count > 0 else "loop value frame underflow"
461
462
let frame = frames[frames.count - 1]
463
464
assert frame.node == node else "loop value frame head is not the loop being visited"
465
466
frames.remove_at(frames.count - 1)
467
468
// A valued break under a loop that consumes nothing was
469
// already reported at the break itself; nothing to settle.
470
if !frame.wants_value then
471
return
472
fi
473
474
let result = _settler.settle(
475
frame.contributions,
476
frame.expected_type
477
)
478
479
if !result? then
480
// A loop ending a body whose return is still being
481
// inferred, reached only as the tail of that body or of
482
// one of its arms, delivers no value: without a valued
483
// break it is the statement it was written as.
484
if node.void_tolerated /\ frame.contributions.count == 0 then
485
return
486
fi
487
488
_logger.error(node.location, "cannot infer the type of this loop")
489
490
return
491
fi
492
493
node.compile_expressions_state.value = IR.Values.BLOCK(result)
494
495
_visitor.declare_composite_spill_field_for(node, node.compile_expressions_state.value)
496
si
497
si
498
499
// One open loop's value bookkeeping: what its valued `break`s
500
// contribute, whether anything consumes the result, and the label
501
// name when the loop is written under a LABELLED wrapper. Lives on
502
// COMPILE_EXPRESSIONS.loop_value_frames for the walk's duration.
503
class LOOP_VALUE_FRAME is
504
node: Trees.Statements.Statement
505
label_name: string?
506
wants_value: bool
507
expected_type: Semantic.Types.Type?
508
expected_type_error_message: string?
509
contributions: Collections.MutableList[Semantic.Types.Type]
510
has_valued_break: bool public
511
valued_break_location: Source.LOCATION? public
512
513
init(
514
node: Trees.Statements.Statement,
515
label_name: string?,
516
wants_value: bool,
517
expected_type: Semantic.Types.Type?,
518
expected_type_error_message: string?
519
) is
520
self.node = node
521
self.label_name = label_name
522
self.wants_value = wants_value
523
self.expected_type = expected_type
524
self.expected_type_error_message = expected_type_error_message
525
self.contributions = Collections.LIST[Semantic.Types.Type]()
526
self.has_valued_break = false
527
self.valued_break_location = null
528
si
529
530
note_contribution(type: Semantic.Types.Type, location: Source.LOCATION) is
531
contributions.add(type)
532
533
if !has_valued_break then
534
has_valued_break = true
535
valued_break_location = location
536
fi
537
si
538
si
539
si