Skip to content
← Back

src/syntax/process/case_exhaustiveness_checker.ghul

1
namespace Syntax.Process is
2
use Logging;
3
use Source.LOCATION;
4
5
use Semantic.Types.Type;
6
use Semantic.Symbols.Classy;
7
use Semantic.Symbols.ENUM_STRUCT_MEMBER;
8
9
// Exhaustiveness / redundancy check over a `case` statement or
10
// expression. The check runs once after every arm's pattern and
11
// statements have been compiled, so the scrutinee's type and each
12
// arm's classification are settled. Four warnings are emitted:
13
// `non-exhaustive-case`, `redundant-case-arm`, and
14
// `dead-case-else` are derived from a per-arm coverage walk over
15
// a small closed domain (union, closed-class root, enum, bool,
16
// and the optional-wrapped variant of each). `case-needs-else`
17
// is emitted for an open-domain scrutinee (int, string, open
18
// class hierarchies, tuples) with no fallback arm — a warning on
19
// the statement form and on an expression form with a
20
// defaultable expected type, an error otherwise.
21
class CASE_EXHAUSTIVENESS_CHECKER is
22
_logger: Logger;
23
_innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup;
24
25
init(
26
logger: Logger,
27
innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup
28
) is
29
super.init();
30
31
_logger = logger;
32
_innate_symbol_lookup = innate_symbol_lookup;
33
si
34
35
check(`case: Trees.Statements.CASE) is
36
let expression_value = `case.expression?.value;
37
38
if !expression_value? then
39
return;
40
fi
41
42
let scrutinee_type = expression_value.type;
43
44
if !scrutinee_type? \/ !scrutinee_type.is_settled then
45
return;
46
fi
47
48
// For the open-domain branch we treat any arm carrying a
49
// destructure pattern (not just an actual `else`) as a
50
// catch-all — the existing `compile_conditionals.visit_case`
51
// and `pattern_arm_coverage` paths already treat a bare
52
// destructure as universe-covering, and `case` source
53
// commonly uses a trailing `when (x, y) then` arm as the
54
// exhaustive fallback. Anything stricter would fire on
55
// working code.
56
let has_fallback mut = false;
57
for arm in `case.matches do
58
if !arm.expressions? /\ !arm.guard? then
59
has_fallback = true;
60
fi
61
od
62
63
let domain = _classify_domain(scrutinee_type);
64
65
if !domain? then
66
// Open-domain scrutinee (int, string, open class
67
// hierarchy, tuple). Without a fallback arm, emit
68
// `case-needs-else`. Severity depends on form: a
69
// statement just falls through; an expression must
70
// produce a value, but for a defaultable expected
71
// type we can warn and emit default(T) at the IL
72
// fall-through.
73
if !has_fallback then
74
_emit_needs_else(`case, scrutinee_type);
75
fi
76
77
return;
78
fi
79
80
let covered = CASE_COVERAGE(domain);
81
let else_arm: Trees.Statements.CASE_MATCH? mut = null;
82
83
for arm in `case.matches do
84
if _is_else_arm(arm) then
85
if !else_arm? then
86
else_arm = arm;
87
fi
88
continue;
89
fi
90
91
let arm_coverage = _arm_coverage(arm, domain);
92
93
if !arm_coverage? \/ arm_coverage.is_empty then
94
continue;
95
fi
96
97
if !arm_coverage.adds_to(covered) then
98
_logger.warn(
99
arm.location,
100
"redundant-case-arm",
101
"this arm is already covered by a preceding arm"
102
);
103
fi
104
105
covered.absorb(arm_coverage);
106
od
107
108
if covered.is_complete then
109
`case.case_state.is_exhaustive = true;
110
fi
111
112
if else_arm? then
113
if covered.is_complete then
114
_logger.warn(
115
else_arm.location,
116
"dead-case-else",
117
"all cases are already covered before this else"
118
);
119
fi
120
elif !covered.is_complete then
121
// For an expression-form case, missing arms over a
122
// closed domain mean no value can be produced — that
123
// is an error. For a statement-form case it is a
124
// warning. Either way the list of missing cases is
125
// the actionable detail.
126
let message = "case is not exhaustive: missing {covered.describe_missing()}";
127
128
if `case.want_value then
129
_logger.error(
130
`case.location,
131
message
132
);
133
else
134
_logger.warn(
135
`case.location,
136
"non-exhaustive-case",
137
message
138
);
139
fi
140
fi
141
si
142
143
_emit_needs_else(`case: Trees.Statements.CASE, scrutinee_type: Type) is
144
if !`case.want_value then
145
_logger.warn(
146
`case.location,
147
"case-needs-else",
148
"case without else may fall through: {scrutinee_type} cannot be exhaustively matched"
149
);
150
return;
151
fi
152
153
let expected_type = `case.expected_type;
154
if expected_type? /\ _is_defaultable(expected_type) then
155
_logger.warn(
156
`case.location,
157
"case-needs-else",
158
"case without else may return default: {scrutinee_type} cannot be exhaustively matched"
159
);
160
`case.case_state.requires_default_fallthrough = true;
161
return;
162
fi
163
164
_logger.error(
165
`case.location,
166
"else required: {scrutinee_type} cannot be exhaustively matched"
167
);
168
si
169
170
_is_defaultable(t: Type) -> bool =>
171
t.is_value_type \/ t.is_optional;
172
173
_is_else_arm(arm: Trees.Statements.CASE_MATCH) -> bool =>
174
!arm.expressions? /\ !arm.pattern?;
175
176
_classify_domain(scrutinee_type: Type) -> CASE_DOMAIN? is
177
let bool_type = _innate_symbol_lookup.get_bool_type();
178
179
let is_optional = scrutinee_type.is_optional;
180
let core = if is_optional then scrutinee_type.as_non_optional() else scrutinee_type fi;
181
182
if core.matches(bool_type) then
183
return CASE_DOMAIN.for_bool(is_optional);
184
fi
185
186
let one_of = cast Semantic.Types.ONE_OF?(core);
187
188
if one_of? then
189
let underlying_classy = cast Classy?(one_of.underlying_type.unspecialized_symbol);
190
191
if !underlying_classy? then
192
return null;
193
fi
194
195
let alternatives = Collections.LIST[Classy]();
196
for v in one_of.subtypes do
197
alternatives.add(v);
198
od
199
// ONE_OF lists the exact runtime types in the narrowed
200
// receiver, so the root only requires coverage if it
201
// is itself one of the subtypes — never separately.
202
return CASE_DOMAIN.for_closed_root(underlying_classy, alternatives, false, is_optional);
203
fi
204
205
let root_classy = _try_get_classy(core);
206
207
if root_classy? then
208
if root_classy.is_closed_root then
209
let alternatives = Collections.LIST[Classy]();
210
for s in root_classy.closed_alternatives do
211
alternatives.add(s);
212
od
213
214
if alternatives.count == 0 then
215
return null;
216
fi
217
218
// A concrete closed-class root is itself constructible
219
// — covering every direct subclass leaves bare-root
220
// instances unaccounted for. Mirrors the universe
221
// construction in `condition_analysis.try_get_
222
// complement_after_eliminated`.
223
let requires_root = root_classy.is_class /\ !root_classy.is_abstract;
224
225
return CASE_DOMAIN.for_closed_root(root_classy, alternatives, requires_root, is_optional);
226
fi
227
228
if _is_enum_classy(root_classy) then
229
let members = Collections.LIST[ENUM_STRUCT_MEMBER]();
230
for sym in root_classy.symbols do
231
if isa ENUM_STRUCT_MEMBER(sym) then
232
members.add(cast ENUM_STRUCT_MEMBER(sym));
233
fi
234
od
235
236
if members.count == 0 then
237
return null;
238
fi
239
240
return CASE_DOMAIN.for_enum(root_classy, members, is_optional);
241
fi
242
fi
243
244
return null;
245
si
246
247
_try_get_classy(type: Type) -> Classy? is
248
let named = cast Semantic.Types.NAMED?(type);
249
250
if !named? then
251
return null;
252
fi
253
254
return cast Classy?(named.symbol.unspecialized_symbol);
255
si
256
257
_is_enum_classy(classy: Classy) -> bool =>
258
classy.symbol_kind == Semantic.Symbols.SymbolKind.ENUM;
259
260
_arm_coverage(arm: Trees.Statements.CASE_MATCH, domain: CASE_DOMAIN) -> ARM_COVERAGE? is
261
// A guarded arm can fall through at runtime even when the
262
// pattern matches, so it never counts towards covering the
263
// domain — returning an empty coverage also exempts it
264
// from the redundant-case-arm check (an empty coverage is
265
// skipped by the caller before that check runs).
266
if arm.guard? then
267
return ARM_COVERAGE();
268
fi
269
270
if arm.pattern? then
271
return _pattern_arm_coverage(arm.pattern, domain);
272
elif arm.expressions? then
273
return _literal_arm_coverage(arm.expressions, domain);
274
fi
275
276
return null;
277
si
278
279
_pattern_arm_coverage(
280
pattern: Trees.Variables.VARIABLE,
281
domain: CASE_DOMAIN
282
) -> ARM_COVERAGE is
283
let result = ARM_COVERAGE();
284
285
if !pattern.is_explicit_type then
286
// A bare destructure or bare bind on a `case` arm is
287
// irrefutable on the non-null half of the scrutinee.
288
// For a non-optional scrutinee that's everything; for
289
// an optional scrutinee it leaves the null half open.
290
if domain.is_optional then
291
result.covers_all_alternatives(domain);
292
else
293
result.covers_universe = true;
294
fi
295
296
return result;
297
fi
298
299
let target = pattern.type_expression.type;
300
301
if !target? \/ !target.is_settled then
302
return result;
303
fi
304
305
let target_optional = target.is_optional;
306
let target_core = if target_optional then target.as_non_optional() else target fi;
307
308
if target_optional /\ domain.is_optional then
309
result.covers_null = true;
310
fi
311
312
let target_classy = _try_get_classy(target_core);
313
314
if !target_classy? then
315
return result;
316
fi
317
318
if domain.root_symbol? then
319
if target_classy =~ domain.root_symbol then
320
result.covers_all_alternatives(domain);
321
elif domain.alternatives? /\ domain.contains_alternative(target_classy) then
322
result.covered_alternatives.add(target_classy);
323
fi
324
fi
325
326
return result;
327
si
328
329
_literal_arm_coverage(
330
expressions: Trees.Expressions.LIST,
331
domain: CASE_DOMAIN
332
) -> ARM_COVERAGE is
333
let result = ARM_COVERAGE();
334
335
for expr in expressions.expressions do
336
if isa Trees.Expressions.NULL(expr) then
337
if domain.is_optional then
338
result.covers_null = true;
339
fi
340
elif isa Trees.Expressions.Literals.BOOLEAN(expr) then
341
let bool_lit = cast Trees.Expressions.Literals.BOOLEAN(expr);
342
343
if bool_lit.value_string =~ "true" then
344
result.covers_true = true;
345
elif bool_lit.value_string =~ "false" then
346
result.covers_false = true;
347
fi
348
elif domain.enum_members? then
349
let value_string = _try_get_enum_literal_value(expr, domain);
350
if value_string? /\ !result.contains_enum_value(value_string) then
351
result.covered_enum_values.add(value_string);
352
fi
353
fi
354
od
355
356
return result;
357
si
358
359
// For an enum-domain arm, recognise an expression that has
360
// been resolved to a numeric literal whose type matches the
361
// enum scrutinee. Returns the literal's value string so the
362
// checker can record coverage by enum-member value. The match
363
// tolerates `Color.RED` (member access), `cast Color(1)`, and
364
// any other shape that compile-expressions has lowered to a
365
// numeric literal — what matters is the resolved value.
366
_try_get_enum_literal_value(
367
expr: Trees.Expressions.Expression,
368
domain: CASE_DOMAIN
369
) -> string? is
370
if !expr.value? then
371
return null;
372
fi
373
374
let number = cast IR.Values.Literal.NUMBER?(expr.value);
375
376
if !number? \/ !domain.root_symbol? then
377
return null;
378
fi
379
380
let number_classy = _try_get_classy(number.type);
381
382
if !number_classy? \/ !(number_classy =~ domain.root_symbol!) then
383
return null;
384
fi
385
386
return number.value;
387
si
388
si
389
390
// Closed-set classification of a `case` scrutinee's type. Four
391
// shapes qualify, each optionally wrapped: bool, union (variants
392
// are the closed set), closed class (in-assembly subclasses are
393
// the closed set), and enum (literal members are the closed set).
394
// Open scrutinees (int, string, open class hierarchies, tuples)
395
// return null and take the `case-needs-else` branch instead.
396
class CASE_DOMAIN is
397
root_symbol: Classy? public;
398
alternatives: Collections.LIST[Classy]? public;
399
enum_members: Collections.LIST[ENUM_STRUCT_MEMBER]? public;
400
is_bool: bool public;
401
// Concrete closed-class roots require explicit root coverage:
402
// their alternatives are direct subclasses, but a bare root
403
// instance is also constructible and must be matched. False
404
// for unions (root has no runtime instance), abstract closed
405
// roots, enums and bool.
406
requires_root: bool public;
407
is_optional: bool public;
408
409
init(
410
root_symbol: Classy?,
411
alternatives: Collections.LIST[Classy]?,
412
enum_members: Collections.LIST[ENUM_STRUCT_MEMBER]?,
413
is_bool: bool,
414
requires_root: bool,
415
is_optional: bool
416
) is
417
super.init();
418
419
self.root_symbol = root_symbol;
420
self.alternatives = alternatives;
421
self.enum_members = enum_members;
422
self.is_bool = is_bool;
423
self.requires_root = requires_root;
424
self.is_optional = is_optional;
425
si
426
427
for_closed_root(symbol: Classy, alternatives: Collections.LIST[Classy], requires_root: bool, is_optional: bool) -> CASE_DOMAIN static =>
428
CASE_DOMAIN(symbol, alternatives, null, false, requires_root, is_optional);
429
430
for_enum(symbol: Classy, members: Collections.LIST[ENUM_STRUCT_MEMBER], is_optional: bool) -> CASE_DOMAIN static =>
431
CASE_DOMAIN(symbol, null, members, false, false, is_optional);
432
433
for_bool(is_optional: bool) -> CASE_DOMAIN static =>
434
CASE_DOMAIN(null, null, null, true, false, is_optional);
435
436
contains_alternative(alternative: Classy) -> bool is
437
if !alternatives? then
438
return false;
439
fi
440
441
for v in alternatives do
442
if v =~ alternative then
443
return true;
444
fi
445
od
446
447
return false;
448
si
449
si
450
451
// Per-arm and accumulated coverage state. The same shape models
452
// an individual arm's contribution and the running union of all
453
// arms seen so far; `adds_to` and `absorb` are the merge ops.
454
class ARM_COVERAGE is
455
covered_alternatives: Collections.LIST[Classy] public;
456
covered_enum_values: Collections.LIST[string] public;
457
covers_null: bool public;
458
covers_true: bool public;
459
covers_false: bool public;
460
// True when an arm matches the closed-class root type itself
461
// (e.g. `when v: Animal then` on a closed `Animal`). Set by
462
// `covers_all_alternatives` only when the domain has
463
// `requires_root`; for unions / enums / abstract roots the
464
// flag is never set, and `is_complete` only consults it
465
// under the same gate.
466
covers_root: bool public;
467
covers_universe: bool public;
468
469
init() is
470
super.init();
471
472
covered_alternatives = Collections.LIST[Classy]();
473
covered_enum_values = Collections.LIST[string]();
474
covers_null = false;
475
covers_true = false;
476
covers_false = false;
477
covers_root = false;
478
covers_universe = false;
479
si
480
481
is_empty: bool =>
482
covered_alternatives.count == 0 /\
483
covered_enum_values.count == 0 /\
484
!covers_null /\
485
!covers_true /\
486
!covers_false /\
487
!covers_root /\
488
!covers_universe;
489
490
contains_alternative(alternative: Classy) -> bool is
491
for v in covered_alternatives do
492
if v =~ alternative then
493
return true;
494
fi
495
od
496
497
return false;
498
si
499
500
contains_enum_value(value: string) -> bool is
501
for v in covered_enum_values do
502
if v =~ value then
503
return true;
504
fi
505
od
506
507
return false;
508
si
509
510
covers_all_alternatives(domain: CASE_DOMAIN) is
511
if domain.alternatives? then
512
for v in domain.alternatives do
513
if !contains_alternative(v) then
514
covered_alternatives.add(v);
515
fi
516
od
517
fi
518
519
if domain.enum_members? then
520
for m in domain.enum_members do
521
if !contains_enum_value(m.value) then
522
covered_enum_values.add(m.value);
523
fi
524
od
525
fi
526
527
if domain.requires_root then
528
covers_root = true;
529
fi
530
si
531
532
adds_to(prior: CASE_COVERAGE) -> bool is
533
if covers_universe /\ !prior.coverage.covers_universe then
534
return true;
535
fi
536
537
if covers_null /\ !prior.coverage.covers_null then
538
return true;
539
fi
540
541
if covers_true /\ !prior.coverage.covers_true then
542
return true;
543
fi
544
545
if covers_false /\ !prior.coverage.covers_false then
546
return true;
547
fi
548
549
if covers_root /\ prior.domain.requires_root /\ !prior.coverage.covers_root then
550
return true;
551
fi
552
553
for v in covered_alternatives do
554
if !prior.coverage.contains_alternative(v) then
555
return true;
556
fi
557
od
558
559
for v in covered_enum_values do
560
if !prior.coverage.contains_enum_value(v) then
561
return true;
562
fi
563
od
564
565
return false;
566
si
567
si
568
569
// Accumulator of arm coverage against a particular domain. Owns
570
// the `is_complete` and `describe_missing` queries the checker
571
// uses to pick the right warning at the end of the arms list.
572
class CASE_COVERAGE is
573
domain: CASE_DOMAIN public;
574
coverage: ARM_COVERAGE public;
575
576
init(domain: CASE_DOMAIN) is
577
super.init();
578
579
self.domain = domain;
580
self.coverage = ARM_COVERAGE();
581
si
582
583
absorb(arm: ARM_COVERAGE) is
584
if arm.covers_universe then
585
coverage.covers_universe = true;
586
fi
587
588
if arm.covers_null then
589
coverage.covers_null = true;
590
fi
591
592
if arm.covers_true then
593
coverage.covers_true = true;
594
fi
595
596
if arm.covers_false then
597
coverage.covers_false = true;
598
fi
599
600
if arm.covers_root then
601
coverage.covers_root = true;
602
fi
603
604
for v in arm.covered_alternatives do
605
if !coverage.contains_alternative(v) then
606
coverage.covered_alternatives.add(v);
607
fi
608
od
609
610
for v in arm.covered_enum_values do
611
if !coverage.contains_enum_value(v) then
612
coverage.covered_enum_values.add(v);
613
fi
614
od
615
si
616
617
is_complete: bool is
618
if coverage.covers_universe then
619
return true;
620
fi
621
622
if domain.is_bool then
623
if !coverage.covers_true \/ !coverage.covers_false then
624
return false;
625
fi
626
627
if domain.is_optional /\ !coverage.covers_null then
628
return false;
629
fi
630
631
return true;
632
fi
633
634
if domain.alternatives? then
635
if domain.is_optional /\ !coverage.covers_null then
636
return false;
637
fi
638
639
if domain.requires_root /\ !coverage.covers_root then
640
return false;
641
fi
642
643
for v in domain.alternatives! do
644
if !coverage.contains_alternative(v) then
645
return false;
646
fi
647
od
648
649
return true;
650
fi
651
652
if domain.enum_members? then
653
if domain.is_optional /\ !coverage.covers_null then
654
return false;
655
fi
656
657
for m in domain.enum_members! do
658
if !coverage.contains_enum_value(m.value) then
659
return false;
660
fi
661
od
662
663
return true;
664
fi
665
666
return false;
667
si
668
669
describe_missing() -> string is
670
let buffer = System.Text.StringBuilder();
671
let count: int mut = 0;
672
673
if domain.is_optional /\ !coverage.covers_null /\ !coverage.covers_universe then
674
_append_with_comma(buffer, count, "null");
675
count = count + 1;
676
fi
677
678
if domain.is_bool /\ !coverage.covers_universe then
679
if !coverage.covers_false then
680
_append_with_comma(buffer, count, "false");
681
count = count + 1;
682
fi
683
684
if !coverage.covers_true then
685
_append_with_comma(buffer, count, "true");
686
count = count + 1;
687
fi
688
fi
689
690
if domain.alternatives? /\ !coverage.covers_universe then
691
if let domain.root_symbol? /\ domain.requires_root /\ !coverage.covers_root then
692
_append_with_comma(buffer, count, root_symbol.name);
693
count = count + 1;
694
fi
695
696
for v in domain.alternatives! do
697
if !coverage.contains_alternative(v) then
698
_append_with_comma(buffer, count, v.name);
699
count = count + 1;
700
fi
701
od
702
fi
703
704
if domain.enum_members? /\ !coverage.covers_universe then
705
for m in domain.enum_members! do
706
if !coverage.contains_enum_value(m.value) then
707
_append_with_comma(buffer, count, m.name);
708
count = count + 1;
709
fi
710
od
711
fi
712
713
return buffer.to_string();
714
si
715
716
_append_with_comma(buffer: System.Text.StringBuilder, count: int, name: string) static is
717
if count > 0 then
718
buffer.append(", ");
719
fi
720
721
buffer.append(name);
722
si
723
si
724
si