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 4124 : PatternChecker::PatternChecker ()
35 4124 : : tyctx (*Resolver::TypeCheckContext::get ()),
36 4124 : resolver (Resolver2_0::ImmutableNameResolutionContext::get ().resolver ()),
37 8248 : mappings (Analysis::Mappings::get ())
38 4124 : {}
39 :
40 : void
41 4124 : PatternChecker::go (HIR::Crate &crate)
42 : {
43 4124 : rust_debug ("started pattern check");
44 21165 : for (auto &item : crate.get_items ())
45 17041 : item->accept_vis (*this);
46 4124 : rust_debug ("finished pattern check");
47 4124 : }
48 :
49 : void
50 0 : PatternChecker::visit (Lifetime &)
51 0 : {}
52 :
53 : void
54 0 : PatternChecker::visit (LifetimeParam &)
55 0 : {}
56 :
57 : void
58 33907 : PatternChecker::visit (PathInExpression &path)
59 33907 : {}
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 17374 : PatternChecker::visit (LiteralExpr &)
87 17374 : {}
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 428 : PatternChecker::visit (NegationExpr &expr)
109 : {
110 428 : expr.get_expr ().accept_vis (*this);
111 428 : }
112 :
113 : void
114 3213 : PatternChecker::visit (ArithmeticOrLogicalExpr &expr)
115 : {
116 3213 : expr.get_lhs ().accept_vis (*this);
117 3213 : expr.get_rhs ().accept_vis (*this);
118 3213 : }
119 :
120 : void
121 2697 : PatternChecker::visit (ComparisonExpr &expr)
122 : {
123 2697 : expr.get_lhs ().accept_vis (*this);
124 2697 : expr.get_rhs ().accept_vis (*this);
125 2697 : }
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 5087 : PatternChecker::visit (TypeCastExpr &expr)
136 : {
137 5087 : expr.get_expr ().accept_vis (*this);
138 5087 : }
139 :
140 : void
141 2465 : PatternChecker::visit (AssignmentExpr &expr)
142 : {
143 2465 : expr.get_lhs ().accept_vis (*this);
144 2465 : expr.get_rhs ().accept_vis (*this);
145 2465 : }
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 288 : PatternChecker::visit (GroupedExpr &expr)
156 : {
157 288 : expr.get_expr_in_parens ().accept_vis (*this);
158 288 : }
159 :
160 : void
161 283 : PatternChecker::visit (ArrayElemsValues &elems)
162 : {
163 1699 : for (auto &elem : elems.get_values ())
164 1416 : elem->accept_vis (*this);
165 283 : }
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 396 : PatternChecker::visit (ArrayExpr &expr)
175 : {
176 396 : expr.get_internal_elements ().accept_vis (*this);
177 396 : }
178 :
179 : void
180 239 : PatternChecker::visit (ArrayIndexExpr &expr)
181 : {
182 239 : expr.get_array_expr ().accept_vis (*this);
183 239 : expr.get_index_expr ().accept_vis (*this);
184 239 : }
185 :
186 : void
187 539 : PatternChecker::visit (TupleExpr &expr)
188 : {
189 1475 : for (auto &elem : expr.get_tuple_elems ())
190 936 : elem->accept_vis (*this);
191 539 : }
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 2604 : PatternChecker::visit (StructExprFieldIdentifierValue &field)
209 : {
210 2604 : field.get_value ().accept_vis (*this);
211 2604 : }
212 :
213 : void
214 42 : PatternChecker::visit (StructExprFieldIndexValue &field)
215 : {
216 42 : field.get_value ().accept_vis (*this);
217 42 : }
218 :
219 : void
220 1296 : PatternChecker::visit (StructExprStructFields &expr)
221 : {
222 4157 : for (auto &field : expr.get_fields ())
223 2861 : field->accept_vis (*this);
224 1296 : }
225 :
226 : void
227 0 : PatternChecker::visit (StructExprStructBase &)
228 0 : {}
229 :
230 : void
231 10607 : PatternChecker::visit (CallExpr &expr)
232 : {
233 10607 : if (!expr.has_fnexpr ())
234 : return;
235 :
236 10607 : NodeId ast_node_id = expr.get_fnexpr ().get_mappings ().get_nodeid ();
237 10607 : NodeId ref_node_id;
238 10607 : if (auto id = resolver.lookup (ast_node_id))
239 10593 : ref_node_id = *id;
240 : else
241 14 : return;
242 :
243 10593 : if (auto definition_id = mappings.lookup_node_to_hir (ref_node_id))
244 : {
245 10593 : if (expr.has_params ())
246 21891 : for (auto &arg : expr.get_arguments ())
247 12976 : 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 5527 : PatternChecker::visit (FieldAccessExpr &expr)
266 : {
267 5527 : expr.get_receiver_expr ().accept_vis (*this);
268 5527 : }
269 :
270 : void
271 53 : PatternChecker::visit (ClosureExpr &expr)
272 : {
273 53 : expr.get_expr ().accept_vis (*this);
274 53 : }
275 :
276 : void
277 21512 : PatternChecker::visit (BlockExpr &expr)
278 : {
279 43538 : for (auto &stmt : expr.get_statements ())
280 22026 : stmt->accept_vis (*this);
281 :
282 21512 : if (expr.has_expr ())
283 15805 : expr.get_final_expr ().accept_vis (*this);
284 21512 : }
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 515 : PatternChecker::visit (ReturnExpr &expr)
347 : {
348 515 : if (expr.has_return_expr ())
349 484 : expr.get_expr ().accept_vis (*this);
350 515 : }
351 :
352 : void
353 3513 : PatternChecker::visit (UnsafeBlockExpr &expr)
354 : {
355 3513 : expr.get_block_expr ().accept_vis (*this);
356 3513 : }
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 465 : PatternChecker::visit (IfExpr &expr)
380 : {
381 465 : expr.get_if_condition ().accept_vis (*this);
382 465 : expr.get_if_block ().accept_vis (*this);
383 465 : }
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 1072 : PatternChecker::visit (MatchExpr &expr)
395 : {
396 1072 : expr.get_scrutinee_expr ().accept_vis (*this);
397 :
398 3539 : for (auto &match_arm : expr.get_match_cases ())
399 2467 : match_arm.get_expr ().accept_vis (*this);
400 :
401 : // match expressions are only an entrypoint
402 1072 : TyTy::BaseType *scrutinee_ty;
403 1072 : bool ok = tyctx.lookup_type (
404 1072 : expr.get_scrutinee_expr ().get_mappings ().get_hirid (), &scrutinee_ty);
405 1072 : rust_assert (ok);
406 :
407 1072 : check_match_usefulness (&tyctx, scrutinee_ty, expr);
408 1072 : }
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 1189 : PatternChecker::visit (Module &module)
452 : {
453 5099 : for (auto &item : module.get_items ())
454 3910 : item->accept_vis (*this);
455 1189 : }
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 12909 : PatternChecker::visit (Function &function)
479 : {
480 12909 : function.get_definition ().accept_vis (*this);
481 12909 : }
482 :
483 : void
484 1212 : PatternChecker::visit (TypeAlias &)
485 1212 : {}
486 :
487 : void
488 1446 : PatternChecker::visit (StructStruct &)
489 1446 : {}
490 :
491 : void
492 929 : PatternChecker::visit (TupleStruct &)
493 929 : {}
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 488 : PatternChecker::visit (Enum &)
513 488 : {}
514 :
515 : void
516 97 : PatternChecker::visit (Union &)
517 97 : {}
518 :
519 : void
520 505 : PatternChecker::visit (ConstantItem &const_item)
521 : {
522 505 : const_item.get_expr ().accept_vis (*this);
523 505 : }
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 3537 : PatternChecker::visit (Trait &trait)
551 : {
552 6749 : for (auto &item : trait.get_trait_items ())
553 3212 : item->accept_vis (*this);
554 3537 : }
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 2200 : PatternChecker::visit (ExternalFunctionItem &)
569 2200 : {}
570 :
571 : void
572 0 : PatternChecker::visit (ExternalTypeItem &)
573 0 : {}
574 :
575 : void
576 1456 : PatternChecker::visit (ExternBlock &block)
577 : {
578 : // FIXME: Do we need to do this?
579 3657 : for (auto &item : block.get_extern_items ())
580 2201 : item->accept_vis (*this);
581 1456 : }
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 12454 : PatternChecker::visit (LetStmt &stmt)
677 : {
678 12454 : if (stmt.has_init_expr ())
679 11337 : stmt.get_init_expr ().accept_vis (*this);
680 12454 : }
681 :
682 : void
683 9148 : PatternChecker::visit (ExprStmt &stmt)
684 : {
685 9148 : stmt.get_expr ().accept_vis (*this);
686 9148 : }
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 15760 : Constructor::is_covered_by (const Constructor &o) const
738 : {
739 15760 : if (o.kind == ConstructorKind::WILDCARD)
740 : return true;
741 :
742 3676 : 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 2913 : Constructor::operator< (const Constructor &o) const
778 : {
779 2913 : if (kind != o.kind)
780 0 : return kind < o.kind;
781 :
782 2913 : 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 20891 : Constructor::to_string () const
801 : {
802 20891 : switch (kind)
803 : {
804 333 : case ConstructorKind::STRUCT:
805 333 : 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 15446 : case ConstructorKind::WILDCARD:
812 15446 : 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 4943 : DeconstructedPat::specialize (const Constructor &other_ctor,
822 : int other_ctor_arity) const
823 : {
824 4943 : rust_assert (other_ctor.is_covered_by (ctor));
825 4943 : if (ctor.is_wildcard ())
826 4028 : return std::vector<DeconstructedPat> (
827 : other_ctor_arity,
828 4028 : DeconstructedPat (Constructor::make_wildcard (), locus));
829 :
830 915 : return fields;
831 : }
832 :
833 : std::string
834 13357 : DeconstructedPat::to_string () const
835 : {
836 26714 : std::string s = ctor.to_string () + "[";
837 15424 : for (auto &f : fields)
838 6201 : s += f.to_string () + ", ";
839 :
840 40071 : s += "](arity=" + std::to_string (arity) + ")";
841 13357 : 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 4943 : PatOrWild::specialize (const Constructor &other_ctor,
855 : int other_ctor_arity) const
856 : {
857 4943 : if (pat.has_value ())
858 : {
859 4943 : auto v = pat.value ().specialize (other_ctor, other_ctor_arity);
860 4943 : std::vector<PatOrWild> ret;
861 6740 : for (auto &pat : v)
862 3594 : ret.push_back (PatOrWild::make_pattern (pat));
863 :
864 4943 : return ret;
865 4943 : }
866 : else
867 : {
868 0 : return std::vector<PatOrWild> (other_ctor_arity,
869 0 : PatOrWild::make_wildcard ());
870 : }
871 : }
872 :
873 : std::string
874 11290 : PatOrWild::to_string () const
875 : {
876 11290 : if (pat.has_value ())
877 11290 : return pat.value ().to_string ();
878 : else
879 0 : return "Wild";
880 : }
881 :
882 : void
883 4943 : PatStack::pop_head_constructor (const Constructor &other_ctor,
884 : int other_ctor_arity)
885 : {
886 4943 : rust_assert (!pats.empty ());
887 4943 : rust_assert (other_ctor.is_covered_by (head ().ctor ()));
888 :
889 4943 : PatOrWild &hd = head ();
890 4943 : auto v = hd.specialize (other_ctor, other_ctor_arity);
891 4943 : {
892 4943 : std::string s = "[";
893 6740 : for (auto &pat : v)
894 5391 : s += pat.to_string () + ", ";
895 4943 : s += "]";
896 :
897 4943 : rust_debug ("specialize %s with %s to %s", hd.to_string ().c_str (),
898 : other_ctor.to_string ().c_str (), s.c_str ());
899 4943 : }
900 4943 : pop_head ();
901 6740 : for (auto &pat : v)
902 1797 : pats.push_back (pat);
903 4943 : }
904 :
905 : std::string
906 7410 : MatrixRow::to_string () const
907 : {
908 7410 : std::string s;
909 11960 : for (const PatOrWild &pat : pats.get_subpatterns ())
910 13650 : s += pat.to_string () + ", ";
911 7410 : return s;
912 : }
913 :
914 : std::vector<PlaceInfo>
915 2591 : PlaceInfo::specialize (const Constructor &c) const
916 : {
917 2591 : switch (c.get_kind ())
918 : {
919 1237 : case Constructor::ConstructorKind::WILDCARD:
920 1237 : case Constructor::ConstructorKind::INT_RANGE:
921 1237 : {
922 1237 : return {};
923 : }
924 1354 : break;
925 1354 : case Constructor::ConstructorKind::STRUCT:
926 1354 : case Constructor::ConstructorKind::VARIANT:
927 1354 : {
928 1354 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
929 1354 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
930 1354 : switch (adt->get_adt_kind ())
931 : {
932 1354 : case TyTy::ADTType::ADTKind::ENUM:
933 1354 : case TyTy::ADTType::ADTKind::STRUCT_STRUCT:
934 1354 : case TyTy::ADTType::ADTKind::TUPLE_STRUCT:
935 1354 : {
936 1354 : TyTy::VariantDef *variant
937 1354 : = adt->get_variants ().at (c.get_variant_index ());
938 1354 : if (variant->get_variant_type ()
939 : == TyTy::VariantDef::VariantType::NUM)
940 578 : return {};
941 :
942 776 : std::vector<PlaceInfo> new_place_infos;
943 1615 : for (auto &field : variant->get_fields ())
944 839 : new_place_infos.push_back (field->get_field_type ());
945 :
946 776 : return new_place_infos;
947 776 : }
948 0 : break;
949 0 : case TyTy::ADTType::ADTKind::UNION:
950 0 : {
951 : // TODO: support unions
952 0 : rust_unreachable ();
953 : }
954 : }
955 : }
956 0 : break;
957 0 : default:
958 0 : {
959 0 : rust_unreachable ();
960 : }
961 0 : break;
962 : }
963 :
964 0 : rust_unreachable ();
965 : }
966 :
967 : Matrix
968 2591 : Matrix::specialize (const Constructor &ctor) const
969 : {
970 2591 : auto subfields_place_info = place_infos.at (0).specialize (ctor);
971 :
972 2591 : std::vector<MatrixRow> new_rows;
973 8465 : for (const MatrixRow &row : rows)
974 : {
975 5874 : PatStack pats = row.get_pats_clone ();
976 5874 : const PatOrWild &hd = pats.head ();
977 5874 : if (ctor.is_covered_by (hd.ctor ()))
978 : {
979 4943 : pats.pop_head_constructor (ctor, subfields_place_info.size ());
980 4943 : new_rows.emplace_back (pats, row.is_under_guard ());
981 : }
982 5874 : }
983 :
984 2591 : if (place_infos.empty ())
985 0 : return Matrix (new_rows, {});
986 :
987 : // push subfields of the first fields after specialization
988 2591 : std::vector<PlaceInfo> new_place_infos = subfields_place_info;
989 : // add place infos for the rest of the fields
990 2700 : for (size_t i = 1; i < place_infos.size (); i++)
991 109 : new_place_infos.push_back (place_infos.at (i));
992 :
993 5182 : return Matrix (new_rows, new_place_infos);
994 2591 : }
995 :
996 : std::string
997 3658 : Matrix::to_string () const
998 : {
999 3658 : std::string s = "[\n";
1000 11068 : for (const MatrixRow &row : rows)
1001 22230 : s += "row: " + row.to_string () + "\n";
1002 :
1003 3658 : s += "](place_infos=[";
1004 5673 : for (const PlaceInfo &place_info : place_infos)
1005 6045 : s += place_info.get_type ()->as_string () + ", ";
1006 :
1007 3658 : s += "])";
1008 3658 : return s;
1009 : }
1010 :
1011 : std::string
1012 29 : WitnessPat::to_string () const
1013 : {
1014 29 : switch (ctor.get_kind ())
1015 : {
1016 4 : case Constructor::ConstructorKind::STRUCT:
1017 4 : {
1018 4 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1019 4 : TyTy::VariantDef *variant
1020 4 : = adt->get_variants ().at (ctor.get_variant_index ());
1021 4 : std::string buf;
1022 12 : buf += adt->get_identifier ();
1023 :
1024 4 : buf += " {";
1025 4 : if (!fields.empty ())
1026 4 : buf += " ";
1027 :
1028 12 : for (size_t i = 0; i < fields.size (); i++)
1029 : {
1030 24 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1031 16 : buf += fields.at (i).to_string ();
1032 8 : if (i < fields.size () - 1)
1033 4 : buf += ", ";
1034 : }
1035 4 : if (!fields.empty ())
1036 4 : buf += " ";
1037 :
1038 4 : buf += "}";
1039 4 : return buf;
1040 : }
1041 25 : break;
1042 25 : case Constructor::ConstructorKind::VARIANT:
1043 25 : {
1044 25 : std::string buf;
1045 25 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1046 75 : buf += adt->get_identifier ();
1047 25 : TyTy::VariantDef *variant
1048 25 : = adt->get_variants ().at (ctor.get_variant_index ());
1049 50 : buf += "::" + variant->get_identifier ();
1050 :
1051 25 : switch (variant->get_variant_type ())
1052 : {
1053 5 : case TyTy::VariantDef::VariantType::NUM:
1054 5 : {
1055 5 : return buf;
1056 : }
1057 20 : break;
1058 20 : case TyTy::VariantDef::VariantType::TUPLE:
1059 20 : {
1060 20 : buf += "(";
1061 22 : for (size_t i = 0; i < fields.size (); i++)
1062 : {
1063 4 : buf += fields.at (i).to_string ();
1064 2 : if (i < fields.size () - 1)
1065 0 : buf += ", ";
1066 : }
1067 20 : buf += ")";
1068 20 : return buf;
1069 : }
1070 0 : break;
1071 0 : case TyTy::VariantDef::VariantType::STRUCT:
1072 0 : {
1073 0 : buf += " {";
1074 0 : if (!fields.empty ())
1075 0 : buf += " ";
1076 :
1077 0 : for (size_t i = 0; i < fields.size (); i++)
1078 : {
1079 0 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1080 0 : buf += fields.at (i).to_string ();
1081 0 : if (i < fields.size () - 1)
1082 0 : buf += ", ";
1083 : }
1084 :
1085 0 : if (!fields.empty ())
1086 0 : buf += " ";
1087 :
1088 0 : buf += "}";
1089 : }
1090 0 : break;
1091 0 : default:
1092 0 : {
1093 0 : rust_unreachable ();
1094 : }
1095 0 : break;
1096 : }
1097 0 : return buf;
1098 25 : }
1099 0 : break;
1100 0 : case Constructor::ConstructorKind::INT_RANGE:
1101 0 : {
1102 : // TODO: implement
1103 0 : rust_unreachable ();
1104 : }
1105 0 : break;
1106 0 : case Constructor::ConstructorKind::WILDCARD:
1107 0 : {
1108 0 : return "_";
1109 : }
1110 0 : break;
1111 0 : case Constructor::ConstructorKind::REFERENCE:
1112 0 : {
1113 : // TODO: implement
1114 0 : rust_unreachable ();
1115 : }
1116 0 : break;
1117 0 : default:
1118 0 : {
1119 0 : rust_unreachable ();
1120 : }
1121 : break;
1122 : }
1123 : rust_unreachable ();
1124 : }
1125 :
1126 : void
1127 2591 : WitnessMatrix::apply_constructor (const Constructor &ctor,
1128 : const std::set<Constructor> &missings,
1129 : TyTy::BaseType *ty)
1130 : {
1131 2591 : int arity = 0;
1132 : // TODO: only support struct and variant ctor for now.
1133 2591 : switch (ctor.get_kind ())
1134 : {
1135 : case Constructor::ConstructorKind::WILDCARD:
1136 : {
1137 : arity = 0;
1138 : }
1139 : break;
1140 1354 : case Constructor::ConstructorKind::STRUCT:
1141 1354 : case Constructor::ConstructorKind::VARIANT:
1142 1354 : {
1143 1354 : if (ty->get_kind () == TyTy::TypeKind::ADT)
1144 : {
1145 1354 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1146 1354 : TyTy::VariantDef *variant
1147 1354 : = adt->get_variants ().at (ctor.get_variant_index ());
1148 1354 : if (variant->get_variant_type () == TyTy::VariantDef::NUM)
1149 : arity = 0;
1150 : else
1151 776 : arity = variant->get_fields ().size ();
1152 : }
1153 : }
1154 : break;
1155 0 : default:
1156 0 : {
1157 0 : rust_unreachable ();
1158 : }
1159 : }
1160 :
1161 2591 : std::string buf;
1162 2602 : for (auto &stack : patstacks)
1163 : {
1164 11 : buf += "[";
1165 18 : for (auto &pat : stack)
1166 21 : buf += pat.to_string () + ", ";
1167 :
1168 11 : buf += "]\n";
1169 : }
1170 2591 : rust_debug ("witness pats:\n%s", buf.c_str ());
1171 :
1172 2602 : for (auto &stack : patstacks)
1173 : {
1174 11 : std::vector<WitnessPat> subfield;
1175 16 : for (int i = 0; i < arity; i++)
1176 : {
1177 5 : if (stack.empty ())
1178 0 : subfield.push_back (WitnessPat::make_wildcard (ty));
1179 : else
1180 : {
1181 5 : subfield.push_back (stack.back ());
1182 5 : stack.pop_back ();
1183 : }
1184 : }
1185 :
1186 11 : stack.emplace_back (ctor, subfield, ty);
1187 11 : }
1188 2591 : }
1189 :
1190 : void
1191 2591 : WitnessMatrix::extend (const WitnessMatrix &other)
1192 : {
1193 2591 : patstacks.insert (patstacks.end (), other.patstacks.begin (),
1194 : other.patstacks.end ());
1195 2591 : }
1196 :
1197 : // forward declarations
1198 : static DeconstructedPat lower_pattern (Resolver::TypeCheckContext *ctx,
1199 : HIR::Pattern &pattern,
1200 : TyTy::BaseType *scrutinee_ty);
1201 :
1202 : static DeconstructedPat
1203 821 : lower_tuple_pattern (Resolver::TypeCheckContext *ctx,
1204 : HIR::TupleStructPattern &pattern,
1205 : TyTy::VariantDef *variant, Constructor &ctor)
1206 : {
1207 821 : int arity = variant->get_fields ().size ();
1208 821 : HIR::TupleStructItems &elems = pattern.get_items ();
1209 :
1210 821 : std::vector<DeconstructedPat> fields;
1211 821 : switch (elems.get_item_type ())
1212 : {
1213 785 : case HIR::TupleStructItems::ItemType::NO_REST:
1214 785 : {
1215 785 : HIR::TupleStructItemsNoRest &items_no_rest
1216 : = static_cast<HIR::TupleStructItemsNoRest &> (elems);
1217 :
1218 785 : rust_assert (variant->get_fields ().size ()
1219 : == items_no_rest.get_patterns ().size ());
1220 :
1221 1557 : for (size_t i = 0; i < items_no_rest.get_patterns ().size (); i++)
1222 : {
1223 772 : fields.push_back (
1224 1544 : lower_pattern (ctx, *items_no_rest.get_patterns ().at (i),
1225 772 : variant->get_fields ().at (i)->get_field_type ()));
1226 : }
1227 785 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1228 : }
1229 36 : break;
1230 36 : case HIR::TupleStructItems::ItemType::HAS_REST:
1231 36 : {
1232 36 : HIR::TupleStructItemsHasRest &items_has_rest
1233 : = static_cast<HIR::TupleStructItemsHasRest &> (elems);
1234 :
1235 36 : size_t num_patterns = items_has_rest.get_lower_patterns ().size ()
1236 36 : + items_has_rest.get_upper_patterns ().size ();
1237 :
1238 36 : rust_assert (num_patterns <= variant->num_fields ());
1239 :
1240 36 : size_t i = 0;
1241 65 : for (auto &pattern_member : items_has_rest.get_lower_patterns ())
1242 : {
1243 29 : fields.push_back (lower_pattern (
1244 29 : ctx, *pattern_member,
1245 29 : variant->get_fields ().at (i++)->get_field_type ()));
1246 : }
1247 100 : while (i < variant->num_fields ()
1248 100 : - items_has_rest.get_upper_patterns ().size ())
1249 : {
1250 64 : fields.push_back (
1251 64 : DeconstructedPat::make_wildcard (pattern.get_locus ()));
1252 64 : i++;
1253 : }
1254 50 : for (auto &pattern_member : items_has_rest.get_upper_patterns ())
1255 : {
1256 14 : fields.push_back (lower_pattern (
1257 14 : ctx, *pattern_member,
1258 14 : variant->get_fields ().at (i++)->get_field_type ()));
1259 : }
1260 36 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1261 : }
1262 0 : break;
1263 0 : default:
1264 0 : {
1265 0 : rust_unreachable ();
1266 : }
1267 : }
1268 821 : }
1269 :
1270 : static DeconstructedPat
1271 92 : lower_struct_pattern (Resolver::TypeCheckContext *ctx,
1272 : HIR::StructPattern &pattern, TyTy::VariantDef *variant,
1273 : Constructor ctor)
1274 : {
1275 92 : int arity = variant->get_fields ().size ();
1276 :
1277 : // Initialize all field patterns to wildcard.
1278 92 : std::vector<DeconstructedPat> fields
1279 184 : = std::vector<DeconstructedPat> (arity, DeconstructedPat::make_wildcard (
1280 92 : pattern.get_locus ()));
1281 :
1282 92 : std::map<std::string, int> field_map;
1283 245 : for (int i = 0; i < arity; i++)
1284 : {
1285 153 : auto &f = variant->get_fields ().at (i);
1286 153 : field_map[f->get_name ()] = i;
1287 : }
1288 :
1289 : // Fill in the fields with the present patterns.
1290 92 : HIR::StructPatternElements elems = pattern.get_struct_pattern_elems ();
1291 242 : for (auto &elem : elems.get_struct_pattern_fields ())
1292 : {
1293 150 : switch (elem->get_item_type ())
1294 : {
1295 79 : case HIR::StructPatternField::ItemType::IDENT:
1296 79 : {
1297 79 : HIR::StructPatternFieldIdent *ident
1298 79 : = static_cast<HIR::StructPatternFieldIdent *> (elem.get ());
1299 79 : int field_idx
1300 79 : = field_map.at (ident->get_identifier ().as_string ());
1301 79 : fields.at (field_idx)
1302 79 : = DeconstructedPat::make_wildcard (pattern.get_locus ());
1303 : }
1304 79 : break;
1305 53 : case HIR::StructPatternField::ItemType::IDENT_PAT:
1306 53 : {
1307 53 : HIR::StructPatternFieldIdentPat *ident_pat
1308 53 : = static_cast<HIR::StructPatternFieldIdentPat *> (elem.get ());
1309 53 : int field_idx
1310 53 : = field_map.at (ident_pat->get_identifier ().as_string ());
1311 53 : fields.at (field_idx) = lower_pattern (
1312 : ctx, ident_pat->get_pattern (),
1313 106 : variant->get_fields ().at (field_idx)->get_field_type ());
1314 : }
1315 53 : break;
1316 18 : case HIR::StructPatternField::ItemType::TUPLE_PAT:
1317 18 : {
1318 18 : HIR::StructPatternFieldTuplePat *tuple_pat
1319 18 : = static_cast<HIR::StructPatternFieldTuplePat *> (elem.get ());
1320 18 : int field_idx = tuple_pat->get_index ();
1321 18 : fields.at (field_idx) = lower_pattern (
1322 : ctx, tuple_pat->get_tuple_pattern (),
1323 36 : variant->get_fields ().at (field_idx)->get_field_type ());
1324 : }
1325 18 : break;
1326 0 : default:
1327 0 : {
1328 0 : rust_unreachable ();
1329 : }
1330 : }
1331 : }
1332 :
1333 92 : return DeconstructedPat{ctor, arity, fields, pattern.get_locus ()};
1334 92 : };
1335 :
1336 : static DeconstructedPat
1337 3353 : lower_pattern (Resolver::TypeCheckContext *ctx, HIR::Pattern &pattern,
1338 : TyTy::BaseType *scrutinee_ty)
1339 : {
1340 3353 : HIR::Pattern::PatternType pat_type = pattern.get_pattern_type ();
1341 3353 : switch (pat_type)
1342 : {
1343 1080 : case HIR::Pattern::PatternType::WILDCARD:
1344 1080 : case HIR::Pattern::PatternType::IDENTIFIER:
1345 1080 : {
1346 1080 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1347 : }
1348 741 : break;
1349 741 : case HIR::Pattern::PatternType::PATH:
1350 741 : {
1351 : // TODO: support constants, associated constants, enum variants and
1352 : // structs
1353 : // https://doc.rust-lang.org/reference/patterns.html#path-patterns
1354 : // unimplemented. Treat this pattern as wildcard for now.
1355 741 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1356 : }
1357 31 : break;
1358 31 : case HIR::Pattern::PatternType::REFERENCE:
1359 31 : {
1360 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1361 31 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1362 : }
1363 913 : break;
1364 913 : case HIR::Pattern::PatternType::STRUCT:
1365 913 : case HIR::Pattern::PatternType::TUPLE_STRUCT:
1366 913 : {
1367 913 : HirId path_id = UNKNOWN_HIRID;
1368 913 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1369 : {
1370 92 : HIR::StructPattern &struct_pattern
1371 : = static_cast<HIR::StructPattern &> (pattern);
1372 92 : path_id = struct_pattern.get_path ().get_mappings ().get_hirid ();
1373 : }
1374 : else
1375 : {
1376 821 : HIR::TupleStructPattern &tuple_pattern
1377 : = static_cast<HIR::TupleStructPattern &> (pattern);
1378 821 : path_id = tuple_pattern.get_path ().get_mappings ().get_hirid ();
1379 : }
1380 :
1381 913 : rust_assert (scrutinee_ty->get_kind () == TyTy::TypeKind::ADT);
1382 913 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (scrutinee_ty);
1383 :
1384 913 : Constructor ctor = Constructor::make_struct ();
1385 913 : TyTy::VariantDef *variant;
1386 913 : if (adt->is_struct_struct () || adt->is_tuple_struct ())
1387 81 : variant = adt->get_variants ().at (0);
1388 832 : else if (adt->is_enum ())
1389 : {
1390 832 : HirId variant_id = UNKNOWN_HIRID;
1391 832 : bool ok = ctx->lookup_variant_definition (path_id, &variant_id);
1392 832 : rust_assert (ok);
1393 :
1394 832 : int variant_idx;
1395 832 : ok = adt->lookup_variant_by_id (variant_id, &variant, &variant_idx);
1396 832 : rust_assert (ok);
1397 :
1398 832 : ctor = Constructor::make_variant (variant_idx);
1399 : }
1400 : else
1401 : {
1402 0 : rust_unreachable ();
1403 : }
1404 913 : rust_assert (variant->get_variant_type ()
1405 : == TyTy::VariantDef::VariantType::TUPLE
1406 : || variant->get_variant_type ()
1407 : == TyTy::VariantDef::VariantType::STRUCT);
1408 :
1409 913 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1410 : {
1411 92 : HIR::StructPattern &struct_pattern
1412 : = static_cast<HIR::StructPattern &> (pattern);
1413 92 : return lower_struct_pattern (ctx, struct_pattern, variant, ctor);
1414 : }
1415 : else
1416 : {
1417 821 : HIR::TupleStructPattern &tuple_pattern
1418 : = static_cast<HIR::TupleStructPattern &> (pattern);
1419 821 : return lower_tuple_pattern (ctx, tuple_pattern, variant, ctor);
1420 : }
1421 : }
1422 121 : break;
1423 121 : case HIR::Pattern::PatternType::TUPLE:
1424 121 : {
1425 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1426 121 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1427 : }
1428 75 : break;
1429 75 : case HIR::Pattern::PatternType::SLICE:
1430 75 : {
1431 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1432 75 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1433 : }
1434 145 : break;
1435 145 : case HIR::Pattern::PatternType::ALT:
1436 145 : {
1437 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1438 145 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1439 : }
1440 207 : break;
1441 207 : case HIR::Pattern::PatternType::LITERAL:
1442 207 : {
1443 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1444 207 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1445 : }
1446 40 : break;
1447 40 : case HIR::Pattern::PatternType::RANGE:
1448 40 : {
1449 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1450 40 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1451 : }
1452 0 : break;
1453 0 : case HIR::Pattern::PatternType::GROUPED:
1454 0 : {
1455 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1456 0 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1457 : }
1458 0 : break;
1459 0 : default:
1460 0 : {
1461 0 : rust_unreachable ();
1462 : }
1463 : }
1464 : }
1465 :
1466 : static MatchArm
1467 2467 : lower_arm (Resolver::TypeCheckContext *ctx, HIR::MatchCase &arm,
1468 : TyTy::BaseType *scrutinee_ty)
1469 : {
1470 2467 : rust_assert (arm.get_arm ().get_pattern () != nullptr);
1471 :
1472 2467 : DeconstructedPat pat
1473 2467 : = lower_pattern (ctx, *arm.get_arm ().get_pattern (), scrutinee_ty);
1474 2467 : return MatchArm (pat, arm.get_arm ().has_match_arm_guard ());
1475 2467 : }
1476 :
1477 : std::pair<std::set<Constructor>, std::set<Constructor>>
1478 1910 : split_constructors (std::vector<Constructor> &ctors, PlaceInfo &place_info)
1479 : {
1480 1910 : bool all_wildcard = true;
1481 6176 : for (auto &ctor : ctors)
1482 : {
1483 4266 : if (!ctor.is_wildcard ())
1484 915 : all_wildcard = false;
1485 : }
1486 :
1487 : // first pass for the case that all patterns are wildcard
1488 1910 : if (all_wildcard)
1489 2474 : return std::make_pair (std::set<Constructor> (
1490 2474 : {Constructor::make_wildcard ()}),
1491 3711 : std::set<Constructor> ());
1492 :
1493 : // TODO: only support enums and structs for now.
1494 673 : TyTy::BaseType *ty = place_info.get_type ();
1495 673 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
1496 673 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1497 673 : rust_assert (adt->is_enum () || adt->is_struct_struct ()
1498 : || adt->is_tuple_struct ());
1499 :
1500 673 : std::set<Constructor> universe;
1501 673 : if (adt->is_enum ())
1502 : {
1503 1923 : for (size_t i = 0; i < adt->get_variants ().size (); i++)
1504 1302 : universe.insert (Constructor::make_variant (i));
1505 : }
1506 52 : else if (adt->is_struct_struct () || adt->is_tuple_struct ())
1507 : {
1508 52 : universe.insert (Constructor::make_struct ());
1509 : }
1510 :
1511 673 : std::set<Constructor> present;
1512 1509 : for (auto &ctor : ctors)
1513 : {
1514 1432 : if (ctor.is_wildcard ())
1515 1192 : return std::make_pair (universe, std::set<Constructor> ());
1516 : else
1517 836 : present.insert (ctor);
1518 : }
1519 :
1520 77 : std::set<Constructor> missing;
1521 77 : std::set_difference (universe.begin (), universe.end (), present.begin (),
1522 : present.end (), std::inserter (missing, missing.end ()));
1523 154 : return std::make_pair (universe, missing);
1524 750 : }
1525 :
1526 : // The core of the algorithm. It computes the usefulness and exhaustiveness of a
1527 : // given matrix recursively.
1528 : // TODO: calculate usefulness
1529 : static WitnessMatrix
1530 3658 : compute_exhaustiveness_and_usefulness (Resolver::TypeCheckContext *ctx,
1531 : Matrix &matrix)
1532 : {
1533 3658 : rust_debug ("call compute_exhaustiveness_and_usefulness");
1534 3658 : rust_debug ("matrix: %s", matrix.to_string ().c_str ());
1535 :
1536 3658 : if (matrix.get_rows ().empty ())
1537 : {
1538 : // no rows left. This means a non-exhaustive pattern.
1539 6 : rust_debug ("non-exhaustive subpattern found");
1540 6 : return WitnessMatrix::make_unit ();
1541 : }
1542 :
1543 : // Base case: there are no columns in matrix.
1544 3652 : if (matrix.get_place_infos ().empty ())
1545 1742 : return WitnessMatrix::make_empty ();
1546 :
1547 1910 : std::vector<Constructor> heads;
1548 6176 : for (auto head : matrix.heads ())
1549 10442 : heads.push_back (head.ctor ());
1550 :
1551 : // TODO: not sure missing ctors need to be calculated
1552 1910 : auto ctors_and_missings
1553 1910 : = split_constructors (heads, matrix.get_place_infos ().at (0));
1554 1910 : std::set<Constructor> ctors = ctors_and_missings.first;
1555 1910 : std::set<Constructor> missings = ctors_and_missings.second;
1556 :
1557 1910 : WitnessMatrix ret = WitnessMatrix::make_empty ();
1558 4501 : for (auto &ctor : ctors)
1559 : {
1560 2591 : rust_debug ("specialize with %s", ctor.to_string ().c_str ());
1561 : // TODO: Instead of creating new matrix, we can change the original matrix
1562 : // and use it for sub-pattern matching. It will significantly reduce
1563 : // memory usage.
1564 2591 : Matrix spec_matrix = matrix.specialize (ctor);
1565 :
1566 2591 : WitnessMatrix witness
1567 2591 : = compute_exhaustiveness_and_usefulness (ctx, spec_matrix);
1568 :
1569 2591 : TyTy::BaseType *ty = matrix.get_place_infos ().at (0).get_type ();
1570 2591 : witness.apply_constructor (ctor, missings, ty);
1571 2591 : ret.extend (witness);
1572 5182 : }
1573 :
1574 1910 : return ret;
1575 1910 : }
1576 :
1577 : static void
1578 1067 : emit_exhaustiveness_error (Resolver::TypeCheckContext *ctx,
1579 : HIR::MatchExpr &expr, WitnessMatrix &witness)
1580 : {
1581 1067 : TyTy::BaseType *scrutinee_ty;
1582 1067 : bool ok
1583 1067 : = ctx->lookup_type (expr.get_scrutinee_expr ().get_mappings ().get_hirid (),
1584 : &scrutinee_ty);
1585 1067 : rust_assert (ok);
1586 :
1587 1067 : if (!witness.empty ())
1588 : {
1589 4 : std::stringstream buf;
1590 10 : for (size_t i = 0; i < witness.get_stacks ().size (); i++)
1591 : {
1592 6 : auto &stack = witness.get_stacks ().at (i);
1593 6 : WitnessPat w = WitnessPat::make_wildcard (scrutinee_ty);
1594 6 : if (!stack.empty ())
1595 6 : w = stack.at (0);
1596 :
1597 6 : rust_debug ("Witness[%d]: %s", (int) i, w.to_string ().c_str ());
1598 12 : buf << "'" << w.to_string () << "'";
1599 6 : if (i != witness.get_stacks ().size () - 1)
1600 2 : buf << " and ";
1601 6 : }
1602 4 : rust_error_at (expr.get_scrutinee_expr ().get_locus (),
1603 : "non-exhaustive patterns: %s not covered",
1604 4 : buf.str ().c_str ());
1605 4 : }
1606 : else
1607 : {
1608 1063 : rust_debug ("no witness found");
1609 : }
1610 1067 : }
1611 :
1612 : // Entry point for computing match usefulness and check exhaustiveness
1613 : void
1614 1072 : check_match_usefulness (Resolver::TypeCheckContext *ctx,
1615 : TyTy::BaseType *scrutinee_ty, HIR::MatchExpr &expr)
1616 : {
1617 1072 : if (!expr.has_match_arms ())
1618 5 : return;
1619 :
1620 : // Lower the arms to a more convenient representation.
1621 1067 : std::vector<MatrixRow> rows;
1622 3534 : for (auto &arm : expr.get_match_cases ())
1623 : {
1624 2467 : PatStack pats;
1625 2467 : MatchArm lowered = lower_arm (ctx, arm, scrutinee_ty);
1626 2467 : PatOrWild pat = PatOrWild::make_pattern (lowered.get_pat ());
1627 2467 : pats.push (pat);
1628 2467 : rows.emplace_back (pats, lowered.has_guard ());
1629 2467 : }
1630 :
1631 1067 : std::vector<PlaceInfo> place_infos = {{PlaceInfo (scrutinee_ty)}};
1632 2134 : Matrix matrix{rows, place_infos};
1633 :
1634 1067 : WitnessMatrix witness = compute_exhaustiveness_and_usefulness (ctx, matrix);
1635 :
1636 1067 : emit_exhaustiveness_error (ctx, expr, witness);
1637 2134 : }
1638 :
1639 : } // namespace Analysis
1640 : } // namespace Rust
|
