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