Line data Source code
1 : // Copyright (C) 2020-2026 Free Software Foundation, Inc.
2 :
3 : // This file is part of GCC.
4 :
5 : // GCC is free software; you can redistribute it and/or modify it under
6 : // the terms of the GNU General Public License as published by the Free
7 : // Software Foundation; either version 3, or (at your option) any later
8 : // version.
9 :
10 : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 : // for more details.
14 :
15 : // You should have received a copy of the GNU General Public License
16 : // along with GCC; see the file COPYING3. If not see
17 : // <http://www.gnu.org/licenses/>.
18 :
19 : #include "rust-system.h"
20 : #include "rust-hir-pattern-analysis.h"
21 : #include "rust-diagnostics.h"
22 : #include "rust-hir-full-decls.h"
23 : #include "rust-hir-path.h"
24 : #include "rust-hir-pattern.h"
25 : #include "rust-hir.h"
26 : #include "rust-mapping-common.h"
27 : #include "rust-system.h"
28 : #include "rust-tyty.h"
29 : #include "rust-immutable-name-resolution-context.h"
30 :
31 : namespace Rust {
32 : namespace Analysis {
33 :
34 4285 : PatternChecker::PatternChecker ()
35 4285 : : tyctx (*Resolver::TypeCheckContext::get ()),
36 4285 : resolver (Resolver2_0::ImmutableNameResolutionContext::get ().resolver ()),
37 8570 : mappings (Analysis::Mappings::get ())
38 4285 : {}
39 :
40 : void
41 4285 : PatternChecker::go (HIR::Crate &crate)
42 : {
43 4285 : rust_debug ("started pattern check");
44 21803 : for (auto &item : crate.get_items ())
45 17518 : item->accept_vis (*this);
46 4285 : rust_debug ("finished pattern check");
47 4285 : }
48 :
49 : void
50 0 : PatternChecker::visit (Lifetime &)
51 0 : {}
52 :
53 : void
54 0 : PatternChecker::visit (LifetimeParam &)
55 0 : {}
56 :
57 : void
58 33984 : PatternChecker::visit (PathInExpression &path)
59 33984 : {}
60 :
61 : void
62 0 : PatternChecker::visit (TypePathSegment &)
63 0 : {}
64 :
65 : void
66 0 : PatternChecker::visit (TypePathSegmentGeneric &)
67 0 : {}
68 :
69 : void
70 0 : PatternChecker::visit (TypePathSegmentFunction &)
71 0 : {}
72 :
73 : void
74 0 : PatternChecker::visit (TypePath &)
75 0 : {}
76 :
77 : void
78 15 : PatternChecker::visit (QualifiedPathInExpression &)
79 15 : {}
80 :
81 : void
82 0 : PatternChecker::visit (QualifiedPathInType &)
83 0 : {}
84 :
85 : void
86 19109 : PatternChecker::visit (LiteralExpr &)
87 19109 : {}
88 :
89 : void
90 1934 : PatternChecker::visit (BorrowExpr &expr)
91 : {
92 1934 : expr.get_expr ().accept_vis (*this);
93 1934 : }
94 :
95 : void
96 3898 : PatternChecker::visit (DereferenceExpr &expr)
97 : {
98 3898 : expr.get_expr ().accept_vis (*this);
99 3898 : }
100 :
101 : void
102 0 : PatternChecker::visit (ErrorPropagationExpr &expr)
103 : {
104 0 : expr.get_expr ().accept_vis (*this);
105 0 : }
106 :
107 : void
108 582 : PatternChecker::visit (NegationExpr &expr)
109 : {
110 582 : expr.get_expr ().accept_vis (*this);
111 582 : }
112 :
113 : void
114 3217 : PatternChecker::visit (ArithmeticOrLogicalExpr &expr)
115 : {
116 3217 : expr.get_lhs ().accept_vis (*this);
117 3217 : expr.get_rhs ().accept_vis (*this);
118 3217 : }
119 :
120 : void
121 3452 : PatternChecker::visit (ComparisonExpr &expr)
122 : {
123 3452 : expr.get_lhs ().accept_vis (*this);
124 3452 : expr.get_rhs ().accept_vis (*this);
125 3452 : }
126 :
127 : void
128 384 : PatternChecker::visit (LazyBooleanExpr &expr)
129 : {
130 384 : expr.get_lhs ().accept_vis (*this);
131 384 : expr.get_rhs ().accept_vis (*this);
132 384 : }
133 :
134 : void
135 5090 : PatternChecker::visit (TypeCastExpr &expr)
136 : {
137 5090 : expr.get_expr ().accept_vis (*this);
138 5090 : }
139 :
140 : void
141 2472 : PatternChecker::visit (AssignmentExpr &expr)
142 : {
143 2472 : expr.get_lhs ().accept_vis (*this);
144 2472 : expr.get_rhs ().accept_vis (*this);
145 2472 : }
146 :
147 : void
148 673 : PatternChecker::visit (CompoundAssignmentExpr &expr)
149 : {
150 673 : expr.get_lhs ().accept_vis (*this);
151 673 : expr.get_rhs ().accept_vis (*this);
152 673 : }
153 :
154 : void
155 291 : PatternChecker::visit (GroupedExpr &expr)
156 : {
157 291 : expr.get_expr_in_parens ().accept_vis (*this);
158 291 : }
159 :
160 : void
161 287 : PatternChecker::visit (ArrayElemsValues &elems)
162 : {
163 1751 : for (auto &elem : elems.get_values ())
164 1464 : elem->accept_vis (*this);
165 287 : }
166 :
167 : void
168 113 : PatternChecker::visit (ArrayElemsCopied &elems)
169 : {
170 113 : elems.get_elem_to_copy ().accept_vis (*this);
171 113 : }
172 :
173 : void
174 400 : PatternChecker::visit (ArrayExpr &expr)
175 : {
176 400 : expr.get_internal_elements ().accept_vis (*this);
177 400 : }
178 :
179 : void
180 287 : PatternChecker::visit (ArrayIndexExpr &expr)
181 : {
182 287 : expr.get_array_expr ().accept_vis (*this);
183 287 : expr.get_index_expr ().accept_vis (*this);
184 287 : }
185 :
186 : void
187 541 : PatternChecker::visit (TupleExpr &expr)
188 : {
189 1480 : for (auto &elem : expr.get_tuple_elems ())
190 939 : elem->accept_vis (*this);
191 541 : }
192 :
193 : void
194 884 : PatternChecker::visit (TupleIndexExpr &expr)
195 : {
196 884 : expr.get_tuple_expr ().accept_vis (*this);
197 884 : }
198 :
199 : void
200 79 : PatternChecker::visit (StructExprStruct &)
201 79 : {}
202 :
203 : void
204 215 : PatternChecker::visit (StructExprFieldIdentifier &)
205 215 : {}
206 :
207 : void
208 2612 : PatternChecker::visit (StructExprFieldIdentifierValue &field)
209 : {
210 2612 : field.get_value ().accept_vis (*this);
211 2612 : }
212 :
213 : void
214 42 : PatternChecker::visit (StructExprFieldIndexValue &field)
215 : {
216 42 : field.get_value ().accept_vis (*this);
217 42 : }
218 :
219 : void
220 1304 : PatternChecker::visit (StructExprStructFields &expr)
221 : {
222 4173 : for (auto &field : expr.get_fields ())
223 2869 : field->accept_vis (*this);
224 1304 : }
225 :
226 : void
227 0 : PatternChecker::visit (StructExprStructBase &)
228 0 : {}
229 :
230 : void
231 12080 : PatternChecker::visit (CallExpr &expr)
232 : {
233 12080 : if (!expr.has_fnexpr ())
234 : return;
235 :
236 12080 : NodeId ast_node_id = expr.get_fnexpr ().get_mappings ().get_nodeid ();
237 12080 : NodeId ref_node_id;
238 12080 : if (auto id = resolver.lookup (ast_node_id))
239 12066 : ref_node_id = *id;
240 : else
241 14 : return;
242 :
243 12066 : if (auto definition_id = mappings.lookup_node_to_hir (ref_node_id))
244 : {
245 12066 : if (expr.has_params ())
246 23324 : for (auto &arg : expr.get_arguments ())
247 13693 : arg->accept_vis (*this);
248 : }
249 : else
250 : {
251 0 : rust_unreachable ();
252 : }
253 : }
254 :
255 : void
256 2955 : PatternChecker::visit (MethodCallExpr &expr)
257 : {
258 2955 : expr.get_receiver ().accept_vis (*this);
259 :
260 4986 : for (auto &arg : expr.get_arguments ())
261 2031 : arg->accept_vis (*this);
262 2955 : }
263 :
264 : void
265 5579 : PatternChecker::visit (FieldAccessExpr &expr)
266 : {
267 5579 : expr.get_receiver_expr ().accept_vis (*this);
268 5579 : }
269 :
270 : void
271 53 : PatternChecker::visit (ClosureExpr &expr)
272 : {
273 53 : expr.get_expr ().accept_vis (*this);
274 53 : }
275 :
276 : void
277 22513 : PatternChecker::visit (BlockExpr &expr)
278 : {
279 46088 : for (auto &stmt : expr.get_statements ())
280 23575 : stmt->accept_vis (*this);
281 :
282 22513 : if (expr.has_expr ())
283 16032 : expr.get_final_expr ().accept_vis (*this);
284 22513 : }
285 :
286 : void
287 15 : PatternChecker::visit (AnonConst &expr)
288 : {
289 15 : expr.get_inner_expr ().accept_vis (*this);
290 15 : }
291 :
292 : void
293 15 : PatternChecker::visit (ConstBlock &expr)
294 : {
295 15 : expr.get_const_expr ().accept_vis (*this);
296 15 : }
297 :
298 : void
299 13 : PatternChecker::visit (ContinueExpr &)
300 13 : {}
301 :
302 : void
303 79 : PatternChecker::visit (BreakExpr &expr)
304 : {
305 79 : if (expr.has_break_expr ())
306 15 : expr.get_expr ().accept_vis (*this);
307 79 : }
308 :
309 : void
310 66 : PatternChecker::visit (RangeFromToExpr &expr)
311 : {
312 66 : expr.get_from_expr ().accept_vis (*this);
313 66 : expr.get_to_expr ().accept_vis (*this);
314 66 : }
315 :
316 : void
317 7 : PatternChecker::visit (RangeFromExpr &expr)
318 : {
319 7 : expr.get_from_expr ().accept_vis (*this);
320 7 : }
321 :
322 : void
323 7 : PatternChecker::visit (RangeToExpr &expr)
324 : {
325 7 : expr.get_to_expr ().accept_vis (*this);
326 7 : }
327 :
328 : void
329 0 : PatternChecker::visit (RangeFullExpr &)
330 0 : {}
331 :
332 : void
333 7 : PatternChecker::visit (RangeFromToInclExpr &expr)
334 : {
335 7 : expr.get_from_expr ().accept_vis (*this);
336 7 : expr.get_to_expr ().accept_vis (*this);
337 7 : }
338 :
339 : void
340 0 : PatternChecker::visit (RangeToInclExpr &expr)
341 : {
342 0 : expr.get_to_expr ().accept_vis (*this);
343 0 : }
344 :
345 : void
346 518 : PatternChecker::visit (ReturnExpr &expr)
347 : {
348 518 : if (expr.has_return_expr ())
349 487 : expr.get_expr ().accept_vis (*this);
350 518 : }
351 :
352 : void
353 3589 : PatternChecker::visit (UnsafeBlockExpr &expr)
354 : {
355 3589 : expr.get_block_expr ().accept_vis (*this);
356 3589 : }
357 :
358 : void
359 124 : PatternChecker::visit (LoopExpr &expr)
360 : {
361 124 : expr.get_loop_block ().accept_vis (*this);
362 124 : }
363 :
364 : void
365 71 : PatternChecker::visit (WhileLoopExpr &expr)
366 : {
367 71 : expr.get_predicate_expr ().accept_vis (*this);
368 71 : expr.get_loop_block ().accept_vis (*this);
369 71 : }
370 :
371 : void
372 0 : PatternChecker::visit (WhileLetLoopExpr &expr)
373 : {
374 0 : expr.get_cond ().accept_vis (*this);
375 0 : expr.get_loop_block ().accept_vis (*this);
376 0 : }
377 :
378 : void
379 1222 : PatternChecker::visit (IfExpr &expr)
380 : {
381 1222 : expr.get_if_condition ().accept_vis (*this);
382 1222 : expr.get_if_block ().accept_vis (*this);
383 1222 : }
384 :
385 : void
386 1201 : PatternChecker::visit (IfExprConseqElse &expr)
387 : {
388 1201 : expr.get_if_condition ().accept_vis (*this);
389 1201 : expr.get_if_block ().accept_vis (*this);
390 1201 : expr.get_else_block ().accept_vis (*this);
391 1201 : }
392 :
393 : void
394 1079 : PatternChecker::visit (MatchExpr &expr)
395 : {
396 1079 : expr.get_scrutinee_expr ().accept_vis (*this);
397 :
398 3559 : for (auto &match_arm : expr.get_match_cases ())
399 2480 : match_arm.get_expr ().accept_vis (*this);
400 :
401 : // match expressions are only an entrypoint
402 1079 : TyTy::BaseType *scrutinee_ty;
403 1079 : bool ok = tyctx.lookup_type (
404 1079 : expr.get_scrutinee_expr ().get_mappings ().get_hirid (), &scrutinee_ty);
405 1079 : rust_assert (ok);
406 :
407 1079 : check_match_usefulness (&tyctx, scrutinee_ty, expr);
408 1079 : }
409 :
410 : void
411 0 : PatternChecker::visit (AwaitExpr &)
412 : {
413 : // TODO: Visit expression
414 0 : }
415 :
416 : void
417 0 : PatternChecker::visit (AsyncBlockExpr &)
418 : {
419 : // TODO: Visit block expression
420 0 : }
421 :
422 : void
423 27 : PatternChecker::visit (InlineAsm &expr)
424 27 : {}
425 :
426 : void
427 2 : PatternChecker::visit (LlvmInlineAsm &expr)
428 2 : {}
429 :
430 : void
431 15 : PatternChecker::visit (OffsetOf &expr)
432 15 : {}
433 :
434 : void
435 0 : PatternChecker::visit (TypeParam &)
436 0 : {}
437 :
438 : void
439 0 : PatternChecker::visit (ConstGenericParam &)
440 0 : {}
441 :
442 : void
443 0 : PatternChecker::visit (LifetimeWhereClauseItem &)
444 0 : {}
445 :
446 : void
447 0 : PatternChecker::visit (TypeBoundWhereClauseItem &)
448 0 : {}
449 :
450 : void
451 1190 : PatternChecker::visit (Module &module)
452 : {
453 5100 : for (auto &item : module.get_items ())
454 3910 : item->accept_vis (*this);
455 1190 : }
456 :
457 : void
458 0 : PatternChecker::visit (ExternCrate &)
459 0 : {}
460 :
461 : void
462 0 : PatternChecker::visit (UseTreeGlob &)
463 0 : {}
464 :
465 : void
466 0 : PatternChecker::visit (UseTreeList &)
467 0 : {}
468 :
469 : void
470 0 : PatternChecker::visit (UseTreeRebind &)
471 0 : {}
472 :
473 : void
474 0 : PatternChecker::visit (UseDeclaration &)
475 0 : {}
476 :
477 : void
478 13070 : PatternChecker::visit (Function &function)
479 : {
480 13070 : function.get_definition ().accept_vis (*this);
481 13070 : }
482 :
483 : void
484 1212 : PatternChecker::visit (TypeAlias &)
485 1212 : {}
486 :
487 : void
488 1446 : PatternChecker::visit (StructStruct &)
489 1446 : {}
490 :
491 : void
492 931 : PatternChecker::visit (TupleStruct &)
493 931 : {}
494 :
495 : void
496 0 : PatternChecker::visit (EnumItem &)
497 0 : {}
498 :
499 : void
500 0 : PatternChecker::visit (EnumItemTuple &)
501 0 : {}
502 :
503 : void
504 0 : PatternChecker::visit (EnumItemStruct &)
505 0 : {}
506 :
507 : void
508 0 : PatternChecker::visit (EnumItemDiscriminant &)
509 0 : {}
510 :
511 : void
512 494 : PatternChecker::visit (Enum &)
513 494 : {}
514 :
515 : void
516 101 : PatternChecker::visit (Union &)
517 101 : {}
518 :
519 : void
520 510 : PatternChecker::visit (ConstantItem &const_item)
521 : {
522 510 : const_item.get_expr ().accept_vis (*this);
523 510 : }
524 :
525 : void
526 52 : PatternChecker::visit (StaticItem &static_item)
527 : {
528 52 : static_item.get_expr ().accept_vis (*this);
529 52 : }
530 :
531 : void
532 2472 : PatternChecker::visit (TraitItemFunc &item)
533 : {
534 2472 : if (item.has_definition ())
535 847 : item.get_block_expr ().accept_vis (*this);
536 2472 : }
537 :
538 : void
539 31 : PatternChecker::visit (TraitItemConst &item)
540 : {
541 31 : if (item.has_expr ())
542 7 : item.get_expr ().accept_vis (*this);
543 31 : }
544 :
545 : void
546 709 : PatternChecker::visit (TraitItemType &)
547 709 : {}
548 :
549 : void
550 3691 : PatternChecker::visit (Trait &trait)
551 : {
552 6903 : for (auto &item : trait.get_trait_items ())
553 3212 : item->accept_vis (*this);
554 3691 : }
555 :
556 : void
557 5541 : PatternChecker::visit (ImplBlock &impl)
558 : {
559 13572 : for (auto &item : impl.get_impl_items ())
560 8031 : item->accept_vis (*this);
561 5541 : }
562 :
563 : void
564 1 : PatternChecker::visit (ExternalStaticItem &)
565 1 : {}
566 :
567 : void
568 2487 : PatternChecker::visit (ExternalFunctionItem &)
569 2487 : {}
570 :
571 : void
572 0 : PatternChecker::visit (ExternalTypeItem &)
573 0 : {}
574 :
575 : void
576 1602 : PatternChecker::visit (ExternBlock &block)
577 : {
578 : // FIXME: Do we need to do this?
579 4090 : for (auto &item : block.get_extern_items ())
580 2488 : item->accept_vis (*this);
581 1602 : }
582 :
583 : void
584 0 : PatternChecker::visit (LiteralPattern &)
585 0 : {}
586 :
587 : void
588 0 : PatternChecker::visit (IdentifierPattern &)
589 0 : {}
590 :
591 : void
592 0 : PatternChecker::visit (WildcardPattern &)
593 0 : {}
594 :
595 : void
596 0 : PatternChecker::visit (RangePatternBoundLiteral &)
597 0 : {}
598 :
599 : void
600 0 : PatternChecker::visit (RangePatternBoundPath &)
601 0 : {}
602 :
603 : void
604 0 : PatternChecker::visit (RangePatternBoundQualPath &)
605 0 : {}
606 :
607 : void
608 0 : PatternChecker::visit (RangePattern &)
609 0 : {}
610 :
611 : void
612 0 : PatternChecker::visit (ReferencePattern &)
613 0 : {}
614 :
615 : void
616 0 : PatternChecker::visit (StructPatternFieldTuplePat &)
617 0 : {}
618 :
619 : void
620 0 : PatternChecker::visit (StructPatternFieldIdentPat &)
621 0 : {}
622 :
623 : void
624 0 : PatternChecker::visit (StructPatternFieldIdent &)
625 0 : {}
626 :
627 : void
628 0 : PatternChecker::visit (StructPattern &)
629 0 : {}
630 :
631 : void
632 0 : PatternChecker::visit (TupleStructItemsNoRest &)
633 0 : {}
634 :
635 : void
636 0 : PatternChecker::visit (TupleStructItemsHasRest &)
637 0 : {}
638 :
639 : void
640 0 : PatternChecker::visit (TupleStructPattern &)
641 0 : {}
642 :
643 : void
644 0 : PatternChecker::visit (TuplePatternItemsNoRest &)
645 0 : {}
646 :
647 : void
648 0 : PatternChecker::visit (TuplePatternItemsHasRest &)
649 0 : {}
650 :
651 : void
652 0 : PatternChecker::visit (TuplePattern &)
653 0 : {}
654 :
655 : void
656 0 : PatternChecker::visit (SlicePatternItemsNoRest &)
657 0 : {}
658 :
659 : void
660 0 : PatternChecker::visit (SlicePatternItemsHasRest &)
661 0 : {}
662 :
663 : void
664 0 : PatternChecker::visit (SlicePattern &)
665 0 : {}
666 :
667 : void
668 0 : PatternChecker::visit (AltPattern &)
669 0 : {}
670 :
671 : void
672 45 : PatternChecker::visit (EmptyStmt &)
673 45 : {}
674 :
675 : void
676 12483 : PatternChecker::visit (LetStmt &stmt)
677 : {
678 12483 : if (stmt.has_init_expr ())
679 11366 : stmt.get_init_expr ().accept_vis (*this);
680 12483 : }
681 :
682 : void
683 10666 : PatternChecker::visit (ExprStmt &stmt)
684 : {
685 10666 : stmt.get_expr ().accept_vis (*this);
686 10666 : }
687 :
688 : void
689 0 : PatternChecker::visit (TraitBound &)
690 0 : {}
691 :
692 : void
693 0 : PatternChecker::visit (ImplTraitType &)
694 0 : {}
695 :
696 : void
697 0 : PatternChecker::visit (TraitObjectType &)
698 0 : {}
699 :
700 : void
701 0 : PatternChecker::visit (ParenthesisedType &)
702 0 : {}
703 :
704 : void
705 0 : PatternChecker::visit (TupleType &)
706 0 : {}
707 :
708 : void
709 0 : PatternChecker::visit (NeverType &)
710 0 : {}
711 :
712 : void
713 0 : PatternChecker::visit (RawPointerType &)
714 0 : {}
715 :
716 : void
717 0 : PatternChecker::visit (ReferenceType &)
718 0 : {}
719 :
720 : void
721 0 : PatternChecker::visit (ArrayType &)
722 0 : {}
723 :
724 : void
725 0 : PatternChecker::visit (SliceType &)
726 0 : {}
727 :
728 : void
729 0 : PatternChecker::visit (InferredType &)
730 0 : {}
731 :
732 : void
733 0 : PatternChecker::visit (BareFunctionType &)
734 0 : {}
735 :
736 : bool
737 15811 : Constructor::is_covered_by (const Constructor &o) const
738 : {
739 15811 : if (o.kind == ConstructorKind::WILDCARD)
740 : return true;
741 :
742 3682 : switch (kind)
743 : {
744 3433 : case ConstructorKind::VARIANT:
745 3433 : {
746 3433 : rust_assert (kind == ConstructorKind::VARIANT);
747 3433 : return variant_idx == o.variant_idx;
748 : }
749 0 : break;
750 0 : case ConstructorKind::INT_RANGE:
751 0 : {
752 0 : rust_assert (kind == ConstructorKind::INT_RANGE);
753 0 : return int_range.lo >= o.int_range.lo && int_range.hi <= o.int_range.hi;
754 : }
755 : break;
756 : case ConstructorKind::WILDCARD:
757 : {
758 : // TODO: wildcard is covered by a variant of enum with a single
759 : // variant
760 : return false;
761 : }
762 : break;
763 : case ConstructorKind::STRUCT:
764 : {
765 : // Struct pattern is always covered by a other struct constructor.
766 : return true;
767 : }
768 0 : break;
769 : // TODO: support references
770 0 : case ConstructorKind::REFERENCE:
771 0 : default:
772 0 : rust_unreachable ();
773 : }
774 : }
775 :
776 : bool
777 2915 : Constructor::operator< (const Constructor &o) const
778 : {
779 2915 : if (kind != o.kind)
780 0 : return kind < o.kind;
781 :
782 2915 : switch (kind)
783 : {
784 2827 : case ConstructorKind::VARIANT:
785 2827 : return variant_idx < o.variant_idx;
786 0 : case ConstructorKind::INT_RANGE:
787 0 : return int_range.lo < o.int_range.lo
788 0 : || (int_range.lo == o.int_range.lo
789 0 : && int_range.hi < o.int_range.hi);
790 : case ConstructorKind::STRUCT:
791 : case ConstructorKind::WILDCARD:
792 : case ConstructorKind::REFERENCE:
793 : return false;
794 0 : default:
795 0 : rust_unreachable ();
796 : }
797 : }
798 :
799 : std::string
800 20963 : Constructor::to_string () const
801 : {
802 20963 : switch (kind)
803 : {
804 342 : case ConstructorKind::STRUCT:
805 342 : return "STRUCT";
806 5112 : case ConstructorKind::VARIANT:
807 10224 : return "VARIANT(" + std::to_string (variant_idx) + ")";
808 0 : case ConstructorKind::INT_RANGE:
809 0 : return "RANGE" + std::to_string (int_range.lo) + ".."
810 0 : + std::to_string (int_range.hi);
811 15509 : case ConstructorKind::WILDCARD:
812 15509 : return "_";
813 0 : case ConstructorKind::REFERENCE:
814 0 : return "REF";
815 0 : default:
816 0 : rust_unreachable ();
817 : }
818 : }
819 :
820 : std::vector<DeconstructedPat>
821 4960 : DeconstructedPat::specialize (const Constructor &other_ctor,
822 : int other_ctor_arity) const
823 : {
824 4960 : rust_assert (other_ctor.is_covered_by (ctor));
825 4960 : if (ctor.is_wildcard ())
826 4043 : return std::vector<DeconstructedPat> (
827 : other_ctor_arity,
828 4043 : DeconstructedPat (Constructor::make_wildcard (), locus));
829 :
830 917 : return fields;
831 : }
832 :
833 : std::string
834 13402 : DeconstructedPat::to_string () const
835 : {
836 26804 : std::string s = ctor.to_string () + "[";
837 15475 : for (auto &f : fields)
838 6219 : s += f.to_string () + ", ";
839 :
840 40206 : s += "](arity=" + std::to_string (arity) + ")";
841 13402 : return s;
842 : }
843 :
844 : bool
845 0 : PatOrWild::is_covered_by (const Constructor &c) const
846 : {
847 0 : if (pat.has_value ())
848 0 : return pat.value ().get_ctor ().is_covered_by (c);
849 : else
850 : return true;
851 : }
852 :
853 : std::vector<PatOrWild>
854 4960 : PatOrWild::specialize (const Constructor &other_ctor,
855 : int other_ctor_arity) const
856 : {
857 4960 : if (pat.has_value ())
858 : {
859 4960 : auto v = pat.value ().specialize (other_ctor, other_ctor_arity);
860 4960 : std::vector<PatOrWild> ret;
861 6761 : for (auto &pat : v)
862 3602 : ret.push_back (PatOrWild::make_pattern (pat));
863 :
864 4960 : return ret;
865 4960 : }
866 : else
867 : {
868 0 : return std::vector<PatOrWild> (other_ctor_arity,
869 0 : PatOrWild::make_wildcard ());
870 : }
871 : }
872 :
873 : std::string
874 11329 : PatOrWild::to_string () const
875 : {
876 11329 : if (pat.has_value ())
877 11329 : return pat.value ().to_string ();
878 : else
879 0 : return "Wild";
880 : }
881 :
882 : void
883 4960 : PatStack::pop_head_constructor (const Constructor &other_ctor,
884 : int other_ctor_arity)
885 : {
886 4960 : rust_assert (!pats.empty ());
887 4960 : rust_assert (other_ctor.is_covered_by (head ().ctor ()));
888 :
889 4960 : PatOrWild &hd = head ();
890 4960 : auto v = hd.specialize (other_ctor, other_ctor_arity);
891 4960 : {
892 4960 : std::string s = "[";
893 6761 : for (auto &pat : v)
894 5403 : s += pat.to_string () + ", ";
895 4960 : s += "]";
896 :
897 4960 : rust_debug ("specialize %s with %s to %s", hd.to_string ().c_str (),
898 : other_ctor.to_string ().c_str (), s.c_str ());
899 4960 : }
900 4960 : pop_head ();
901 6761 : for (auto &pat : v)
902 1801 : pats.push_back (pat);
903 4960 : }
904 :
905 : std::string
906 7440 : MatrixRow::to_string () const
907 : {
908 7440 : std::string s;
909 12008 : for (const PatOrWild &pat : pats.get_subpatterns ())
910 13704 : s += pat.to_string () + ", ";
911 7440 : return s;
912 : }
913 :
914 : std::vector<PlaceInfo>
915 2601 : PlaceInfo::specialize (const Constructor &c) const
916 : {
917 2601 : switch (c.get_kind ())
918 : {
919 1245 : case Constructor::ConstructorKind::WILDCARD:
920 1245 : case Constructor::ConstructorKind::INT_RANGE:
921 1245 : {
922 1245 : return {};
923 : }
924 1356 : break;
925 1356 : case Constructor::ConstructorKind::STRUCT:
926 1356 : case Constructor::ConstructorKind::VARIANT:
927 1356 : {
928 1356 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
929 1356 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
930 1356 : switch (adt->get_adt_kind ())
931 : {
932 1356 : case TyTy::ADTType::ADTKind::ENUM:
933 1356 : case TyTy::ADTType::ADTKind::STRUCT_STRUCT:
934 1356 : case TyTy::ADTType::ADTKind::TUPLE_STRUCT:
935 1356 : {
936 1356 : TyTy::VariantDef *variant
937 1356 : = adt->get_variants ().at (c.get_variant_index ());
938 1356 : if (variant->get_variant_type ()
939 : == TyTy::VariantDef::VariantType::NUM
940 1356 : || variant->get_variant_type ()
941 : == TyTy::VariantDef::VariantType::UNIT)
942 578 : return {};
943 :
944 778 : std::vector<PlaceInfo> new_place_infos;
945 1620 : for (auto &field : variant->get_fields ())
946 842 : new_place_infos.push_back (field->get_field_type ());
947 :
948 778 : return new_place_infos;
949 778 : }
950 0 : break;
951 0 : case TyTy::ADTType::ADTKind::UNION:
952 0 : {
953 : // TODO: support unions
954 0 : rust_unreachable ();
955 : }
956 : }
957 : }
958 0 : break;
959 0 : default:
960 0 : {
961 0 : rust_unreachable ();
962 : }
963 0 : break;
964 : }
965 :
966 0 : rust_unreachable ();
967 : }
968 :
969 : Matrix
970 2601 : Matrix::specialize (const Constructor &ctor) const
971 : {
972 2601 : auto subfields_place_info = place_infos.at (0).specialize (ctor);
973 :
974 2601 : std::vector<MatrixRow> new_rows;
975 8492 : for (const MatrixRow &row : rows)
976 : {
977 5891 : PatStack pats = row.get_pats_clone ();
978 5891 : const PatOrWild &hd = pats.head ();
979 5891 : if (ctor.is_covered_by (hd.ctor ()))
980 : {
981 4960 : pats.pop_head_constructor (ctor, subfields_place_info.size ());
982 4960 : new_rows.emplace_back (pats, row.is_under_guard ());
983 : }
984 5891 : }
985 :
986 2601 : if (place_infos.empty ())
987 0 : return Matrix (new_rows, {});
988 :
989 : // push subfields of the first fields after specialization
990 2601 : std::vector<PlaceInfo> new_place_infos = subfields_place_info;
991 : // add place infos for the rest of the fields
992 2711 : for (size_t i = 1; i < place_infos.size (); i++)
993 110 : new_place_infos.push_back (place_infos.at (i));
994 :
995 5202 : return Matrix (new_rows, new_place_infos);
996 2601 : }
997 :
998 : std::string
999 3675 : Matrix::to_string () const
1000 : {
1001 3675 : std::string s = "[\n";
1002 11115 : for (const MatrixRow &row : rows)
1003 22320 : s += "row: " + row.to_string () + "\n";
1004 :
1005 3675 : s += "](place_infos=[";
1006 5701 : for (const PlaceInfo &place_info : place_infos)
1007 6078 : s += place_info.get_type ()->as_string () + ", ";
1008 :
1009 3675 : s += "])";
1010 3675 : return s;
1011 : }
1012 :
1013 : std::string
1014 29 : WitnessPat::to_string () const
1015 : {
1016 29 : switch (ctor.get_kind ())
1017 : {
1018 4 : case Constructor::ConstructorKind::STRUCT:
1019 4 : {
1020 4 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1021 4 : TyTy::VariantDef *variant
1022 4 : = adt->get_variants ().at (ctor.get_variant_index ());
1023 4 : std::string buf;
1024 12 : buf += adt->get_identifier ();
1025 :
1026 4 : buf += " {";
1027 4 : if (!fields.empty ())
1028 4 : buf += " ";
1029 :
1030 12 : for (size_t i = 0; i < fields.size (); i++)
1031 : {
1032 24 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1033 16 : buf += fields.at (i).to_string ();
1034 8 : if (i < fields.size () - 1)
1035 4 : buf += ", ";
1036 : }
1037 4 : if (!fields.empty ())
1038 4 : buf += " ";
1039 :
1040 4 : buf += "}";
1041 4 : return buf;
1042 : }
1043 25 : break;
1044 25 : case Constructor::ConstructorKind::VARIANT:
1045 25 : {
1046 25 : std::string buf;
1047 25 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1048 75 : buf += adt->get_identifier ();
1049 25 : TyTy::VariantDef *variant
1050 25 : = adt->get_variants ().at (ctor.get_variant_index ());
1051 50 : buf += "::" + variant->get_identifier ();
1052 :
1053 25 : switch (variant->get_variant_type ())
1054 : {
1055 5 : case TyTy::VariantDef::VariantType::UNIT:
1056 5 : case TyTy::VariantDef::VariantType::NUM:
1057 5 : {
1058 5 : return buf;
1059 : }
1060 20 : break;
1061 20 : case TyTy::VariantDef::VariantType::TUPLE:
1062 20 : {
1063 20 : buf += "(";
1064 22 : for (size_t i = 0; i < fields.size (); i++)
1065 : {
1066 4 : buf += fields.at (i).to_string ();
1067 2 : if (i < fields.size () - 1)
1068 0 : buf += ", ";
1069 : }
1070 20 : buf += ")";
1071 20 : return buf;
1072 : }
1073 0 : break;
1074 0 : case TyTy::VariantDef::VariantType::STRUCT:
1075 0 : {
1076 0 : buf += " {";
1077 0 : if (!fields.empty ())
1078 0 : buf += " ";
1079 :
1080 0 : for (size_t i = 0; i < fields.size (); i++)
1081 : {
1082 0 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1083 0 : buf += fields.at (i).to_string ();
1084 0 : if (i < fields.size () - 1)
1085 0 : buf += ", ";
1086 : }
1087 :
1088 0 : if (!fields.empty ())
1089 0 : buf += " ";
1090 :
1091 0 : buf += "}";
1092 : }
1093 0 : break;
1094 0 : default:
1095 0 : {
1096 0 : rust_unreachable ();
1097 : }
1098 0 : break;
1099 : }
1100 0 : return buf;
1101 25 : }
1102 0 : break;
1103 0 : case Constructor::ConstructorKind::INT_RANGE:
1104 0 : {
1105 : // TODO: implement
1106 0 : rust_unreachable ();
1107 : }
1108 0 : break;
1109 0 : case Constructor::ConstructorKind::WILDCARD:
1110 0 : {
1111 0 : return "_";
1112 : }
1113 0 : break;
1114 0 : case Constructor::ConstructorKind::REFERENCE:
1115 0 : {
1116 : // TODO: implement
1117 0 : rust_unreachable ();
1118 : }
1119 0 : break;
1120 0 : default:
1121 0 : {
1122 0 : rust_unreachable ();
1123 : }
1124 : break;
1125 : }
1126 : rust_unreachable ();
1127 : }
1128 :
1129 : void
1130 2601 : WitnessMatrix::apply_constructor (const Constructor &ctor,
1131 : const std::set<Constructor> &missings,
1132 : TyTy::BaseType *ty)
1133 : {
1134 2601 : int arity = 0;
1135 : // TODO: only support struct and variant ctor for now.
1136 2601 : switch (ctor.get_kind ())
1137 : {
1138 : case Constructor::ConstructorKind::WILDCARD:
1139 : {
1140 : arity = 0;
1141 : }
1142 : break;
1143 1356 : case Constructor::ConstructorKind::STRUCT:
1144 1356 : case Constructor::ConstructorKind::VARIANT:
1145 1356 : {
1146 1356 : if (ty->get_kind () == TyTy::TypeKind::ADT)
1147 : {
1148 1356 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1149 1356 : TyTy::VariantDef *variant
1150 1356 : = adt->get_variants ().at (ctor.get_variant_index ());
1151 1356 : if (variant->get_variant_type () == TyTy::VariantDef::NUM
1152 1356 : || variant->get_variant_type () == TyTy::VariantDef::UNIT)
1153 : arity = 0;
1154 : else
1155 778 : arity = variant->get_fields ().size ();
1156 : }
1157 : }
1158 : break;
1159 0 : default:
1160 0 : {
1161 0 : rust_unreachable ();
1162 : }
1163 : }
1164 :
1165 2601 : std::string buf;
1166 2612 : for (auto &stack : patstacks)
1167 : {
1168 11 : buf += "[";
1169 18 : for (auto &pat : stack)
1170 21 : buf += pat.to_string () + ", ";
1171 :
1172 11 : buf += "]\n";
1173 : }
1174 2601 : rust_debug ("witness pats:\n%s", buf.c_str ());
1175 :
1176 2612 : for (auto &stack : patstacks)
1177 : {
1178 11 : std::vector<WitnessPat> subfield;
1179 16 : for (int i = 0; i < arity; i++)
1180 : {
1181 5 : if (stack.empty ())
1182 0 : subfield.push_back (WitnessPat::make_wildcard (ty));
1183 : else
1184 : {
1185 5 : subfield.push_back (stack.back ());
1186 5 : stack.pop_back ();
1187 : }
1188 : }
1189 :
1190 11 : stack.emplace_back (ctor, subfield, ty);
1191 11 : }
1192 2601 : }
1193 :
1194 : void
1195 2601 : WitnessMatrix::extend (const WitnessMatrix &other)
1196 : {
1197 2601 : patstacks.insert (patstacks.end (), other.patstacks.begin (),
1198 : other.patstacks.end ());
1199 2601 : }
1200 :
1201 : // forward declarations
1202 : static DeconstructedPat lower_pattern (Resolver::TypeCheckContext *ctx,
1203 : HIR::Pattern &pattern,
1204 : TyTy::BaseType *scrutinee_ty);
1205 :
1206 : static DeconstructedPat
1207 823 : lower_tuple_pattern (Resolver::TypeCheckContext *ctx,
1208 : HIR::TupleStructPattern &pattern,
1209 : TyTy::VariantDef *variant, Constructor &ctor)
1210 : {
1211 823 : int arity = variant->get_fields ().size ();
1212 823 : HIR::TupleStructItems &elems = pattern.get_items ();
1213 :
1214 823 : std::vector<DeconstructedPat> fields;
1215 823 : switch (elems.get_item_type ())
1216 : {
1217 787 : case HIR::TupleStructItems::ItemType::NO_REST:
1218 787 : {
1219 787 : HIR::TupleStructItemsNoRest &items_no_rest
1220 : = static_cast<HIR::TupleStructItemsNoRest &> (elems);
1221 :
1222 787 : rust_assert (variant->get_fields ().size ()
1223 : == items_no_rest.get_patterns ().size ());
1224 :
1225 1562 : for (size_t i = 0; i < items_no_rest.get_patterns ().size (); i++)
1226 : {
1227 775 : fields.push_back (
1228 1550 : lower_pattern (ctx, *items_no_rest.get_patterns ().at (i),
1229 775 : variant->get_fields ().at (i)->get_field_type ()));
1230 : }
1231 787 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1232 : }
1233 36 : break;
1234 36 : case HIR::TupleStructItems::ItemType::HAS_REST:
1235 36 : {
1236 36 : HIR::TupleStructItemsHasRest &items_has_rest
1237 : = static_cast<HIR::TupleStructItemsHasRest &> (elems);
1238 :
1239 36 : size_t num_patterns = items_has_rest.get_lower_patterns ().size ()
1240 36 : + items_has_rest.get_upper_patterns ().size ();
1241 :
1242 36 : rust_assert (num_patterns <= variant->num_fields ());
1243 :
1244 36 : size_t i = 0;
1245 65 : for (auto &pattern_member : items_has_rest.get_lower_patterns ())
1246 : {
1247 29 : fields.push_back (lower_pattern (
1248 29 : ctx, *pattern_member,
1249 29 : variant->get_fields ().at (i++)->get_field_type ()));
1250 : }
1251 100 : while (i < variant->num_fields ()
1252 100 : - items_has_rest.get_upper_patterns ().size ())
1253 : {
1254 64 : fields.push_back (
1255 64 : DeconstructedPat::make_wildcard (pattern.get_locus ()));
1256 64 : i++;
1257 : }
1258 50 : for (auto &pattern_member : items_has_rest.get_upper_patterns ())
1259 : {
1260 14 : fields.push_back (lower_pattern (
1261 14 : ctx, *pattern_member,
1262 14 : variant->get_fields ().at (i++)->get_field_type ()));
1263 : }
1264 36 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1265 : }
1266 0 : break;
1267 0 : default:
1268 0 : {
1269 0 : rust_unreachable ();
1270 : }
1271 : }
1272 823 : }
1273 :
1274 : static DeconstructedPat
1275 92 : lower_struct_pattern (Resolver::TypeCheckContext *ctx,
1276 : HIR::StructPattern &pattern, TyTy::VariantDef *variant,
1277 : Constructor ctor)
1278 : {
1279 92 : int arity = variant->get_fields ().size ();
1280 :
1281 : // Initialize all field patterns to wildcard.
1282 92 : std::vector<DeconstructedPat> fields
1283 184 : = std::vector<DeconstructedPat> (arity, DeconstructedPat::make_wildcard (
1284 92 : pattern.get_locus ()));
1285 :
1286 92 : std::map<std::string, int> field_map;
1287 245 : for (int i = 0; i < arity; i++)
1288 : {
1289 153 : auto &f = variant->get_fields ().at (i);
1290 153 : field_map[f->get_name ()] = i;
1291 : }
1292 :
1293 : // Fill in the fields with the present patterns.
1294 92 : HIR::StructPatternElements elems = pattern.get_struct_pattern_elems ();
1295 242 : for (auto &elem : elems.get_struct_pattern_fields ())
1296 : {
1297 150 : switch (elem->get_item_type ())
1298 : {
1299 79 : case HIR::StructPatternField::ItemType::IDENT:
1300 79 : {
1301 79 : HIR::StructPatternFieldIdent *ident
1302 79 : = static_cast<HIR::StructPatternFieldIdent *> (elem.get ());
1303 79 : int field_idx
1304 79 : = field_map.at (ident->get_identifier ().as_string ());
1305 79 : fields.at (field_idx)
1306 79 : = DeconstructedPat::make_wildcard (pattern.get_locus ());
1307 : }
1308 79 : break;
1309 53 : case HIR::StructPatternField::ItemType::IDENT_PAT:
1310 53 : {
1311 53 : HIR::StructPatternFieldIdentPat *ident_pat
1312 53 : = static_cast<HIR::StructPatternFieldIdentPat *> (elem.get ());
1313 53 : int field_idx
1314 53 : = field_map.at (ident_pat->get_identifier ().as_string ());
1315 53 : fields.at (field_idx) = lower_pattern (
1316 : ctx, ident_pat->get_pattern (),
1317 106 : variant->get_fields ().at (field_idx)->get_field_type ());
1318 : }
1319 53 : break;
1320 18 : case HIR::StructPatternField::ItemType::TUPLE_PAT:
1321 18 : {
1322 18 : HIR::StructPatternFieldTuplePat *tuple_pat
1323 18 : = static_cast<HIR::StructPatternFieldTuplePat *> (elem.get ());
1324 18 : int field_idx = tuple_pat->get_index ();
1325 18 : fields.at (field_idx) = lower_pattern (
1326 : ctx, tuple_pat->get_tuple_pattern (),
1327 36 : variant->get_fields ().at (field_idx)->get_field_type ());
1328 : }
1329 18 : break;
1330 0 : default:
1331 0 : {
1332 0 : rust_unreachable ();
1333 : }
1334 : }
1335 : }
1336 :
1337 92 : return DeconstructedPat{ctor, arity, fields, pattern.get_locus ()};
1338 92 : };
1339 :
1340 : static DeconstructedPat
1341 3369 : lower_pattern (Resolver::TypeCheckContext *ctx, HIR::Pattern &pattern,
1342 : TyTy::BaseType *scrutinee_ty)
1343 : {
1344 3369 : HIR::Pattern::PatternType pat_type = pattern.get_pattern_type ();
1345 3369 : switch (pat_type)
1346 : {
1347 1067 : case HIR::Pattern::PatternType::WILDCARD:
1348 1067 : case HIR::Pattern::PatternType::IDENTIFIER:
1349 1067 : {
1350 1067 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1351 : }
1352 767 : break;
1353 767 : case HIR::Pattern::PatternType::PATH:
1354 767 : {
1355 : // TODO: support constants, associated constants, enum variants and
1356 : // structs
1357 : // https://doc.rust-lang.org/reference/patterns.html#path-patterns
1358 : // unimplemented. Treat this pattern as wildcard for now.
1359 767 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1360 : }
1361 31 : break;
1362 31 : case HIR::Pattern::PatternType::REFERENCE:
1363 31 : {
1364 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1365 31 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1366 : }
1367 915 : break;
1368 915 : case HIR::Pattern::PatternType::STRUCT:
1369 915 : case HIR::Pattern::PatternType::TUPLE_STRUCT:
1370 915 : {
1371 915 : HirId path_id = UNKNOWN_HIRID;
1372 915 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1373 : {
1374 92 : HIR::StructPattern &struct_pattern
1375 : = static_cast<HIR::StructPattern &> (pattern);
1376 92 : path_id = struct_pattern.get_path ().get_mappings ().get_hirid ();
1377 : }
1378 : else
1379 : {
1380 823 : HIR::TupleStructPattern &tuple_pattern
1381 : = static_cast<HIR::TupleStructPattern &> (pattern);
1382 823 : path_id = tuple_pattern.get_path ().get_mappings ().get_hirid ();
1383 : }
1384 :
1385 915 : rust_assert (scrutinee_ty->get_kind () == TyTy::TypeKind::ADT);
1386 915 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (scrutinee_ty);
1387 :
1388 915 : Constructor ctor = Constructor::make_struct ();
1389 915 : TyTy::VariantDef *variant;
1390 915 : if (adt->is_struct_struct () || adt->is_tuple_struct ())
1391 83 : variant = adt->get_variants ().at (0);
1392 832 : else if (adt->is_enum ())
1393 : {
1394 832 : HirId variant_id = UNKNOWN_HIRID;
1395 832 : bool ok = ctx->lookup_variant_definition (path_id, &variant_id);
1396 832 : rust_assert (ok);
1397 :
1398 832 : int variant_idx;
1399 832 : ok = adt->lookup_variant_by_id (variant_id, &variant, &variant_idx);
1400 832 : rust_assert (ok);
1401 :
1402 832 : ctor = Constructor::make_variant (variant_idx);
1403 : }
1404 : else
1405 : {
1406 0 : rust_unreachable ();
1407 : }
1408 915 : rust_assert (variant->get_variant_type ()
1409 : == TyTy::VariantDef::VariantType::TUPLE
1410 : || variant->get_variant_type ()
1411 : == TyTy::VariantDef::VariantType::STRUCT);
1412 :
1413 915 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1414 : {
1415 92 : HIR::StructPattern &struct_pattern
1416 : = static_cast<HIR::StructPattern &> (pattern);
1417 92 : return lower_struct_pattern (ctx, struct_pattern, variant, ctor);
1418 : }
1419 : else
1420 : {
1421 823 : HIR::TupleStructPattern &tuple_pattern
1422 : = static_cast<HIR::TupleStructPattern &> (pattern);
1423 823 : return lower_tuple_pattern (ctx, tuple_pattern, variant, ctor);
1424 : }
1425 : }
1426 122 : break;
1427 122 : case HIR::Pattern::PatternType::TUPLE:
1428 122 : {
1429 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1430 122 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1431 : }
1432 75 : break;
1433 75 : case HIR::Pattern::PatternType::SLICE:
1434 75 : {
1435 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1436 75 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1437 : }
1438 145 : break;
1439 145 : case HIR::Pattern::PatternType::ALT:
1440 145 : {
1441 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1442 145 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1443 : }
1444 207 : break;
1445 207 : case HIR::Pattern::PatternType::LITERAL:
1446 207 : {
1447 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1448 207 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1449 : }
1450 40 : break;
1451 40 : case HIR::Pattern::PatternType::RANGE:
1452 40 : {
1453 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1454 40 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1455 : }
1456 0 : break;
1457 0 : case HIR::Pattern::PatternType::GROUPED:
1458 0 : {
1459 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1460 0 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1461 : }
1462 0 : break;
1463 0 : default:
1464 0 : {
1465 0 : rust_unreachable ();
1466 : }
1467 : }
1468 : }
1469 :
1470 : static MatchArm
1471 2480 : lower_arm (Resolver::TypeCheckContext *ctx, HIR::MatchCase &arm,
1472 : TyTy::BaseType *scrutinee_ty)
1473 : {
1474 2480 : rust_assert (arm.get_arm ().get_pattern () != nullptr);
1475 :
1476 2480 : DeconstructedPat pat
1477 2480 : = lower_pattern (ctx, *arm.get_arm ().get_pattern (), scrutinee_ty);
1478 2480 : return MatchArm (pat, arm.get_arm ().has_match_arm_guard ());
1479 2480 : }
1480 :
1481 : std::pair<std::set<Constructor>, std::set<Constructor>>
1482 1920 : split_constructors (std::vector<Constructor> &ctors, PlaceInfo &place_info)
1483 : {
1484 1920 : bool all_wildcard = true;
1485 6203 : for (auto &ctor : ctors)
1486 : {
1487 4283 : if (!ctor.is_wildcard ())
1488 917 : all_wildcard = false;
1489 : }
1490 :
1491 : // first pass for the case that all patterns are wildcard
1492 1920 : if (all_wildcard)
1493 2490 : return std::make_pair (std::set<Constructor> (
1494 2490 : {Constructor::make_wildcard ()}),
1495 3735 : std::set<Constructor> ());
1496 :
1497 : // TODO: only support enums and structs for now.
1498 675 : TyTy::BaseType *ty = place_info.get_type ();
1499 675 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
1500 675 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1501 675 : rust_assert (adt->is_enum () || adt->is_struct_struct ()
1502 : || adt->is_tuple_struct ());
1503 :
1504 675 : std::set<Constructor> universe;
1505 675 : if (adt->is_enum ())
1506 : {
1507 1923 : for (size_t i = 0; i < adt->get_variants ().size (); i++)
1508 1302 : universe.insert (Constructor::make_variant (i));
1509 : }
1510 54 : else if (adt->is_struct_struct () || adt->is_tuple_struct ())
1511 : {
1512 54 : universe.insert (Constructor::make_struct ());
1513 : }
1514 :
1515 675 : std::set<Constructor> present;
1516 1513 : for (auto &ctor : ctors)
1517 : {
1518 1435 : if (ctor.is_wildcard ())
1519 1194 : return std::make_pair (universe, std::set<Constructor> ());
1520 : else
1521 838 : present.insert (ctor);
1522 : }
1523 :
1524 78 : std::set<Constructor> missing;
1525 78 : std::set_difference (universe.begin (), universe.end (), present.begin (),
1526 : present.end (), std::inserter (missing, missing.end ()));
1527 156 : return std::make_pair (universe, missing);
1528 753 : }
1529 :
1530 : // The core of the algorithm. It computes the usefulness and exhaustiveness of a
1531 : // given matrix recursively.
1532 : // TODO: calculate usefulness
1533 : static WitnessMatrix
1534 3675 : compute_exhaustiveness_and_usefulness (Resolver::TypeCheckContext *ctx,
1535 : Matrix &matrix)
1536 : {
1537 3675 : rust_debug ("call compute_exhaustiveness_and_usefulness");
1538 3675 : rust_debug ("matrix: %s", matrix.to_string ().c_str ());
1539 :
1540 3675 : if (matrix.get_rows ().empty ())
1541 : {
1542 : // no rows left. This means a non-exhaustive pattern.
1543 6 : rust_debug ("non-exhaustive subpattern found");
1544 6 : return WitnessMatrix::make_unit ();
1545 : }
1546 :
1547 : // Base case: there are no columns in matrix.
1548 3669 : if (matrix.get_place_infos ().empty ())
1549 1749 : return WitnessMatrix::make_empty ();
1550 :
1551 1920 : std::vector<Constructor> heads;
1552 6203 : for (auto head : matrix.heads ())
1553 10486 : heads.push_back (head.ctor ());
1554 :
1555 : // TODO: not sure missing ctors need to be calculated
1556 1920 : auto ctors_and_missings
1557 1920 : = split_constructors (heads, matrix.get_place_infos ().at (0));
1558 1920 : std::set<Constructor> ctors = ctors_and_missings.first;
1559 1920 : std::set<Constructor> missings = ctors_and_missings.second;
1560 :
1561 1920 : WitnessMatrix ret = WitnessMatrix::make_empty ();
1562 4521 : for (auto &ctor : ctors)
1563 : {
1564 2601 : rust_debug ("specialize with %s", ctor.to_string ().c_str ());
1565 : // TODO: Instead of creating new matrix, we can change the original matrix
1566 : // and use it for sub-pattern matching. It will significantly reduce
1567 : // memory usage.
1568 2601 : Matrix spec_matrix = matrix.specialize (ctor);
1569 :
1570 2601 : WitnessMatrix witness
1571 2601 : = compute_exhaustiveness_and_usefulness (ctx, spec_matrix);
1572 :
1573 2601 : TyTy::BaseType *ty = matrix.get_place_infos ().at (0).get_type ();
1574 2601 : witness.apply_constructor (ctor, missings, ty);
1575 2601 : ret.extend (witness);
1576 5202 : }
1577 :
1578 1920 : return ret;
1579 1920 : }
1580 :
1581 : static void
1582 1074 : emit_exhaustiveness_error (Resolver::TypeCheckContext *ctx,
1583 : HIR::MatchExpr &expr, WitnessMatrix &witness)
1584 : {
1585 1074 : TyTy::BaseType *scrutinee_ty;
1586 1074 : bool ok
1587 1074 : = ctx->lookup_type (expr.get_scrutinee_expr ().get_mappings ().get_hirid (),
1588 : &scrutinee_ty);
1589 1074 : rust_assert (ok);
1590 :
1591 1074 : if (!witness.empty ())
1592 : {
1593 4 : std::stringstream buf;
1594 10 : for (size_t i = 0; i < witness.get_stacks ().size (); i++)
1595 : {
1596 6 : auto &stack = witness.get_stacks ().at (i);
1597 6 : WitnessPat w = WitnessPat::make_wildcard (scrutinee_ty);
1598 6 : if (!stack.empty ())
1599 6 : w = stack.at (0);
1600 :
1601 6 : rust_debug ("Witness[%d]: %s", (int) i, w.to_string ().c_str ());
1602 12 : buf << "'" << w.to_string () << "'";
1603 6 : if (i != witness.get_stacks ().size () - 1)
1604 2 : buf << " and ";
1605 6 : }
1606 4 : rust_error_at (expr.get_scrutinee_expr ().get_locus (),
1607 : "non-exhaustive patterns: %s not covered",
1608 4 : buf.str ().c_str ());
1609 4 : }
1610 : else
1611 : {
1612 1070 : rust_debug ("no witness found");
1613 : }
1614 1074 : }
1615 :
1616 : // Entry point for computing match usefulness and check exhaustiveness
1617 : void
1618 1079 : check_match_usefulness (Resolver::TypeCheckContext *ctx,
1619 : TyTy::BaseType *scrutinee_ty, HIR::MatchExpr &expr)
1620 : {
1621 1079 : if (!expr.has_match_arms ())
1622 5 : return;
1623 :
1624 : // Lower the arms to a more convenient representation.
1625 1074 : std::vector<MatrixRow> rows;
1626 3554 : for (auto &arm : expr.get_match_cases ())
1627 : {
1628 2480 : PatStack pats;
1629 2480 : MatchArm lowered = lower_arm (ctx, arm, scrutinee_ty);
1630 2480 : PatOrWild pat = PatOrWild::make_pattern (lowered.get_pat ());
1631 2480 : pats.push (pat);
1632 2480 : rows.emplace_back (pats, lowered.has_guard ());
1633 2480 : }
1634 :
1635 1074 : std::vector<PlaceInfo> place_infos = {{PlaceInfo (scrutinee_ty)}};
1636 2148 : Matrix matrix{rows, place_infos};
1637 :
1638 1074 : WitnessMatrix witness = compute_exhaustiveness_and_usefulness (ctx, matrix);
1639 :
1640 1074 : emit_exhaustiveness_error (ctx, expr, witness);
1641 2148 : }
1642 :
1643 : } // namespace Analysis
1644 : } // namespace Rust
|
