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