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 4558 : PatternChecker::PatternChecker ()
36 4558 : : tyctx (*Resolver::TypeCheckContext::get ()),
37 4558 : resolver (Resolver2_0::FinalizedNameResolutionContext::get ()),
38 9116 : mappings (Analysis::Mappings::get ())
39 4558 : {}
40 :
41 : void
42 4558 : PatternChecker::go (HIR::Crate &crate)
43 : {
44 4558 : rust_debug ("started pattern check");
45 24031 : for (auto &item : crate.get_items ())
46 19478 : item->accept_vis (*this);
47 4553 : rust_debug ("finished pattern check");
48 4553 : }
49 :
50 : void
51 0 : PatternChecker::visit (Lifetime &)
52 0 : {}
53 :
54 : void
55 0 : PatternChecker::visit (LifetimeParam &)
56 0 : {}
57 :
58 : void
59 37399 : PatternChecker::visit (PathInExpression &path)
60 37399 : {}
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 20717 : PatternChecker::visit (LiteralExpr &)
88 20717 : {}
89 :
90 : void
91 2136 : PatternChecker::visit (BorrowExpr &expr)
92 : {
93 2136 : expr.get_expr ().accept_vis (*this);
94 2136 : }
95 :
96 : void
97 4276 : PatternChecker::visit (DereferenceExpr &expr)
98 : {
99 4276 : expr.get_expr ().accept_vis (*this);
100 4276 : }
101 :
102 : void
103 0 : PatternChecker::visit (ErrorPropagationExpr &expr)
104 : {
105 0 : expr.get_expr ().accept_vis (*this);
106 0 : }
107 :
108 : void
109 611 : PatternChecker::visit (NegationExpr &expr)
110 : {
111 611 : expr.get_expr ().accept_vis (*this);
112 611 : }
113 :
114 : void
115 3658 : PatternChecker::visit (ArithmeticOrLogicalExpr &expr)
116 : {
117 3658 : expr.get_lhs ().accept_vis (*this);
118 3658 : expr.get_rhs ().accept_vis (*this);
119 3658 : }
120 :
121 : void
122 3894 : PatternChecker::visit (ComparisonExpr &expr)
123 : {
124 3894 : expr.get_lhs ().accept_vis (*this);
125 3894 : expr.get_rhs ().accept_vis (*this);
126 3894 : }
127 :
128 : void
129 480 : PatternChecker::visit (LazyBooleanExpr &expr)
130 : {
131 480 : expr.get_lhs ().accept_vis (*this);
132 480 : expr.get_rhs ().accept_vis (*this);
133 480 : }
134 :
135 : void
136 5673 : PatternChecker::visit (TypeCastExpr &expr)
137 : {
138 5673 : expr.get_expr ().accept_vis (*this);
139 5673 : }
140 :
141 : void
142 2552 : PatternChecker::visit (AssignmentExpr &expr)
143 : {
144 2552 : expr.get_lhs ().accept_vis (*this);
145 2552 : expr.get_rhs ().accept_vis (*this);
146 2552 : }
147 :
148 : void
149 719 : PatternChecker::visit (CompoundAssignmentExpr &expr)
150 : {
151 719 : expr.get_lhs ().accept_vis (*this);
152 719 : expr.get_rhs ().accept_vis (*this);
153 719 : }
154 :
155 : void
156 340 : PatternChecker::visit (GroupedExpr &expr)
157 : {
158 340 : expr.get_expr_in_parens ().accept_vis (*this);
159 340 : }
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 293 : PatternChecker::visit (ArrayIndexExpr &expr)
182 : {
183 293 : expr.get_array_expr ().accept_vis (*this);
184 293 : expr.get_index_expr ().accept_vis (*this);
185 293 : }
186 :
187 : void
188 621 : PatternChecker::visit (TupleExpr &expr)
189 : {
190 1718 : for (auto &elem : expr.get_tuple_elems ())
191 1097 : elem->accept_vis (*this);
192 621 : }
193 :
194 : void
195 912 : PatternChecker::visit (TupleIndexExpr &expr)
196 : {
197 912 : expr.get_tuple_expr ().accept_vis (*this);
198 912 : }
199 :
200 : void
201 79 : PatternChecker::visit (StructExprStruct &)
202 79 : {}
203 :
204 : void
205 235 : PatternChecker::visit (StructExprFieldIdentifier &)
206 235 : {}
207 :
208 : void
209 2738 : PatternChecker::visit (StructExprFieldIdentifierValue &field)
210 : {
211 2738 : field.get_value ().accept_vis (*this);
212 2738 : }
213 :
214 : void
215 42 : PatternChecker::visit (StructExprFieldIndexValue &field)
216 : {
217 42 : field.get_value ().accept_vis (*this);
218 42 : }
219 :
220 : void
221 1412 : PatternChecker::visit (StructExprStructFields &expr)
222 : {
223 4427 : for (auto &field : expr.get_fields ())
224 3015 : field->accept_vis (*this);
225 1412 : }
226 :
227 : void
228 0 : PatternChecker::visit (StructExprStructBase &)
229 0 : {}
230 :
231 : void
232 13291 : PatternChecker::visit (CallExpr &expr)
233 : {
234 13291 : if (!expr.has_fnexpr ())
235 : return;
236 :
237 13291 : NodeId ast_node_id = expr.get_fnexpr ().get_mappings ().get_nodeid ();
238 13291 : NodeId ref_node_id;
239 13291 : if (auto id = resolver.lookup (ast_node_id, Resolver2_0::Namespace::Values))
240 13221 : ref_node_id = *id;
241 : else
242 70 : return;
243 :
244 13221 : if (auto definition_id = mappings.lookup_node_to_hir (ref_node_id))
245 : {
246 13221 : if (expr.has_params ())
247 25803 : for (auto &arg : expr.get_arguments ())
248 15199 : arg->accept_vis (*this);
249 : }
250 : else
251 : {
252 0 : rust_unreachable ();
253 : }
254 : }
255 :
256 : void
257 3148 : PatternChecker::visit (MethodCallExpr &expr)
258 : {
259 3148 : expr.get_receiver ().accept_vis (*this);
260 :
261 5308 : for (auto &arg : expr.get_arguments ())
262 2160 : arg->accept_vis (*this);
263 3148 : }
264 :
265 : void
266 5716 : PatternChecker::visit (FieldAccessExpr &expr)
267 : {
268 5716 : expr.get_receiver_expr ().accept_vis (*this);
269 5716 : }
270 :
271 : void
272 53 : PatternChecker::visit (ClosureExpr &expr)
273 : {
274 53 : expr.get_expr ().accept_vis (*this);
275 53 : }
276 :
277 : void
278 25115 : PatternChecker::visit (BlockExpr &expr)
279 : {
280 50326 : for (auto &stmt : expr.get_statements ())
281 25211 : stmt->accept_vis (*this);
282 :
283 25115 : if (expr.has_expr ())
284 18127 : expr.get_final_expr ().accept_vis (*this);
285 25115 : }
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 25 : PatternChecker::visit (ContinueExpr &)
301 25 : {}
302 :
303 : void
304 112 : PatternChecker::visit (BreakExpr &expr)
305 : {
306 112 : if (expr.has_break_expr ())
307 21 : expr.get_expr ().accept_vis (*this);
308 112 : }
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 630 : PatternChecker::visit (ReturnExpr &expr)
347 : {
348 630 : if (expr.has_return_expr ())
349 594 : expr.get_expr ().accept_vis (*this);
350 630 : }
351 :
352 : void
353 4034 : PatternChecker::visit (UnsafeBlockExpr &expr)
354 : {
355 4034 : expr.get_block_expr ().accept_vis (*this);
356 4034 : }
357 :
358 : void
359 151 : PatternChecker::visit (LoopExpr &expr)
360 : {
361 151 : expr.get_loop_block ().accept_vis (*this);
362 151 : }
363 :
364 : void
365 88 : PatternChecker::visit (WhileLoopExpr &expr)
366 : {
367 88 : expr.get_predicate_expr ().accept_vis (*this);
368 88 : expr.get_loop_block ().accept_vis (*this);
369 88 : }
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 1343 : PatternChecker::visit (IfExpr &expr)
380 : {
381 1343 : expr.get_if_condition ().accept_vis (*this);
382 1343 : expr.get_if_block ().accept_vis (*this);
383 1343 : }
384 :
385 : void
386 1335 : PatternChecker::visit (IfExprConseqElse &expr)
387 : {
388 1335 : expr.get_if_condition ().accept_vis (*this);
389 1335 : expr.get_if_block ().accept_vis (*this);
390 1335 : expr.get_else_block ().accept_vis (*this);
391 1335 : }
392 :
393 : void
394 1164 : PatternChecker::visit (MatchExpr &expr)
395 : {
396 1164 : expr.get_scrutinee_expr ().accept_vis (*this);
397 :
398 3859 : for (auto &match_arm : expr.get_match_cases ())
399 : {
400 2695 : if (match_arm.get_arm ().has_match_arm_guard ())
401 61 : match_arm.get_arm ().get_guard_expr ().accept_vis (*this);
402 2695 : match_arm.get_expr ().accept_vis (*this);
403 : }
404 :
405 : // match expressions are only an entrypoint
406 1164 : TyTy::BaseType *scrutinee_ty;
407 1164 : bool ok = tyctx.lookup_type (
408 1164 : expr.get_scrutinee_expr ().get_mappings ().get_hirid (), &scrutinee_ty);
409 1164 : rust_assert (ok);
410 :
411 1164 : check_match_usefulness (&tyctx, scrutinee_ty, expr);
412 1164 : }
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 27 : PatternChecker::visit (InlineAsm &expr)
428 27 : {}
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 1245 : PatternChecker::visit (Module &module)
456 : {
457 5418 : for (auto &item : module.get_items ())
458 4173 : item->accept_vis (*this);
459 1245 : }
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 14674 : PatternChecker::visit (Function &function)
483 : {
484 21975 : for (auto ¶m : function.get_function_params ())
485 : {
486 7306 : TyTy::BaseType *param_ty;
487 7306 : bool ok
488 7306 : = tyctx.lookup_type (param.get_mappings ().get_hirid (), ¶m_ty);
489 7306 : rust_assert (ok);
490 :
491 7306 : if (param.get_param_name ().is_refutable (*param_ty))
492 10 : rust_error_at (param.get_locus (), ErrorCode::E0005,
493 : "refutable pattern in function parameter");
494 : }
495 14669 : function.get_definition ().accept_vis (*this);
496 14669 : }
497 :
498 : void
499 1483 : PatternChecker::visit (TypeAlias &)
500 1483 : {}
501 :
502 : void
503 1642 : PatternChecker::visit (StructStruct &)
504 1642 : {}
505 :
506 : void
507 989 : PatternChecker::visit (TupleStruct &)
508 989 : {}
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 543 : PatternChecker::visit (Enum &)
528 543 : {}
529 :
530 : void
531 102 : PatternChecker::visit (Union &)
532 102 : {}
533 :
534 : void
535 544 : PatternChecker::visit (ConstantItem &const_item)
536 : {
537 544 : const_item.get_expr ().accept_vis (*this);
538 544 : }
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 2703 : PatternChecker::visit (TraitItemFunc &item)
548 : {
549 2703 : if (item.has_definition ())
550 861 : item.get_block_expr ().accept_vis (*this);
551 2703 : }
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 804 : PatternChecker::visit (TraitItemType &)
562 804 : {}
563 :
564 : void
565 4065 : PatternChecker::visit (Trait &trait)
566 : {
567 7604 : for (auto &item : trait.get_trait_items ())
568 3539 : item->accept_vis (*this);
569 4065 : }
570 :
571 : void
572 6350 : PatternChecker::visit (ImplBlock &impl)
573 : {
574 15712 : for (auto &item : impl.get_impl_items ())
575 9362 : item->accept_vis (*this);
576 6350 : }
577 :
578 : void
579 1 : PatternChecker::visit (ExternalStaticItem &)
580 1 : {}
581 :
582 : void
583 2681 : PatternChecker::visit (ExternalFunctionItem &)
584 2681 : {}
585 :
586 : void
587 2 : PatternChecker::visit (ExternalTypeItem &)
588 2 : {}
589 :
590 : void
591 1710 : PatternChecker::visit (ExternBlock &block)
592 : {
593 : // FIXME: Do we need to do this?
594 4394 : for (auto &item : block.get_extern_items ())
595 2684 : item->accept_vis (*this);
596 1710 : }
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 13361 : PatternChecker::visit (LetStmt &stmt)
692 : {
693 13361 : if (stmt.has_init_expr ())
694 12206 : stmt.get_init_expr ().accept_vis (*this);
695 :
696 : // skip let-else (allows refutable patterns)
697 13361 : if (stmt.has_else_expr ())
698 5 : return;
699 :
700 13356 : TyTy::BaseType *binding_ty;
701 13356 : bool ok = tyctx.lookup_type (stmt.get_pattern ().get_mappings ().get_hirid (),
702 : &binding_ty);
703 13356 : if (!ok)
704 : return; // type-check failed earlier
705 :
706 13356 : if (stmt.get_pattern ().is_refutable (*binding_ty))
707 11 : rust_error_at (stmt.get_pattern ().get_locus (), ErrorCode::E0005,
708 : "refutable pattern in local binding");
709 : }
710 :
711 : void
712 11396 : PatternChecker::visit (ExprStmt &stmt)
713 : {
714 11396 : stmt.get_expr ().accept_vis (*this);
715 11396 : }
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 17167 : Constructor::is_covered_by (const Constructor &o) const
767 : {
768 17167 : if (o.kind == ConstructorKind::WILDCARD)
769 : return true;
770 :
771 4063 : switch (kind)
772 : {
773 3793 : case ConstructorKind::VARIANT:
774 3793 : {
775 3793 : rust_assert (kind == ConstructorKind::VARIANT);
776 3793 : 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 3245 : Constructor::operator< (const Constructor &o) const
807 : {
808 3245 : if (kind != o.kind)
809 0 : return kind < o.kind;
810 :
811 3245 : switch (kind)
812 : {
813 3143 : case ConstructorKind::VARIANT:
814 3143 : 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 1967 : Constructor::to_string () const
830 : {
831 1967 : switch (kind)
832 : {
833 0 : case ConstructorKind::STRUCT:
834 0 : return "STRUCT";
835 26 : case ConstructorKind::VARIANT:
836 52 : 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 1941 : case ConstructorKind::WILDCARD:
841 1941 : 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 5375 : DeconstructedPat::specialize (const Constructor &other_ctor,
851 : int other_ctor_arity) const
852 : {
853 5375 : rust_assert (other_ctor.is_covered_by (ctor));
854 5375 : if (ctor.is_wildcard ())
855 4368 : return std::vector<DeconstructedPat> (
856 : other_ctor_arity,
857 4368 : DeconstructedPat (Constructor::make_wildcard (), locus));
858 :
859 1007 : return fields;
860 : }
861 :
862 : std::string
863 1967 : DeconstructedPat::to_string () const
864 : {
865 3934 : std::string s = ctor.to_string () + "[";
866 1976 : for (auto &f : fields)
867 27 : s += f.to_string () + ", ";
868 :
869 5901 : s += "](arity=" + std::to_string (arity) + ")";
870 1967 : 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 5375 : PatOrWild::specialize (const Constructor &other_ctor,
884 : int other_ctor_arity) const
885 : {
886 5375 : if (pat.has_value ())
887 : {
888 5375 : auto v = pat.value ().specialize (other_ctor, other_ctor_arity);
889 5375 : std::vector<PatOrWild> ret;
890 7333 : for (auto &pat : v)
891 3916 : ret.push_back (PatOrWild::make_pattern (pat));
892 :
893 5375 : return ret;
894 5375 : }
895 : else
896 : {
897 0 : return std::vector<PatOrWild> (other_ctor_arity,
898 0 : PatOrWild::make_wildcard ());
899 : }
900 : }
901 :
902 : std::string
903 1958 : PatOrWild::to_string () const
904 : {
905 1958 : if (pat.has_value ())
906 1958 : return pat.value ().to_string ();
907 : else
908 0 : return "Wild";
909 : }
910 :
911 : void
912 5375 : PatStack::pop_head_constructor (const Constructor &other_ctor,
913 : int other_ctor_arity)
914 : {
915 5375 : rust_assert (!pats.empty ());
916 5375 : rust_assert (other_ctor.is_covered_by (head ().ctor ()));
917 :
918 5375 : PatOrWild &hd = head ();
919 5375 : auto v = hd.specialize (other_ctor, other_ctor_arity);
920 5375 : {
921 5375 : std::string s = "[";
922 7333 : for (auto &pat : v)
923 5874 : s += pat.to_string () + ", ";
924 5375 : s += "]";
925 :
926 5375 : rust_debug ("specialize %s with %s to %s", hd.to_string ().c_str (),
927 : other_ctor.to_string ().c_str (), s.c_str ());
928 5375 : }
929 5375 : 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 5375 : pats.insert (pats.begin (), v.begin (), v.end ());
933 5375 : }
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 2817 : PlaceInfo::specialize (const Constructor &c) const
946 : {
947 2817 : switch (c.get_kind ())
948 : {
949 1360 : case Constructor::ConstructorKind::WILDCARD:
950 1360 : case Constructor::ConstructorKind::INT_RANGE:
951 1360 : {
952 1360 : return {};
953 : }
954 1457 : break;
955 1457 : case Constructor::ConstructorKind::STRUCT:
956 1457 : case Constructor::ConstructorKind::VARIANT:
957 1457 : {
958 1457 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
959 1457 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
960 1457 : switch (adt->get_adt_kind ())
961 : {
962 1457 : case TyTy::ADTType::ADTKind::ENUM:
963 1457 : case TyTy::ADTType::ADTKind::STRUCT_STRUCT:
964 1457 : case TyTy::ADTType::ADTKind::TUPLE_STRUCT:
965 1457 : {
966 1457 : TyTy::VariantDef *variant
967 1457 : = adt->get_variants ().at (c.get_variant_index ());
968 1457 : if (variant->get_variant_type ()
969 : == TyTy::VariantDef::VariantType::NUM
970 1457 : || variant->get_variant_type ()
971 : == TyTy::VariantDef::VariantType::UNIT)
972 607 : return {};
973 :
974 850 : std::vector<PlaceInfo> new_place_infos;
975 1768 : for (auto &field : variant->get_fields ())
976 918 : new_place_infos.push_back (field->get_field_type ());
977 :
978 850 : return new_place_infos;
979 850 : }
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 2817 : Matrix::specialize (const Constructor &ctor) const
1003 : {
1004 2817 : auto subfields_place_info = place_infos.at (0).specialize (ctor);
1005 :
1006 2817 : std::vector<MatrixRow> new_rows;
1007 9234 : for (const MatrixRow &row : rows)
1008 : {
1009 6417 : PatStack pats = row.get_pats_clone ();
1010 6417 : const PatOrWild &hd = pats.head ();
1011 6417 : if (ctor.is_covered_by (hd.ctor ()))
1012 : {
1013 5375 : pats.pop_head_constructor (ctor, subfields_place_info.size ());
1014 5375 : new_rows.emplace_back (pats, row.is_under_guard ());
1015 : }
1016 6417 : }
1017 :
1018 2817 : if (place_infos.empty ())
1019 0 : return Matrix (new_rows, {});
1020 :
1021 : // push subfields of the first fields after specialization
1022 2817 : std::vector<PlaceInfo> new_place_infos = subfields_place_info;
1023 : // add place infos for the rest of the fields
1024 5764 : for (size_t i = 1; i < place_infos.size (); i++)
1025 130 : new_place_infos.push_back (place_infos.at (i));
1026 :
1027 5634 : return Matrix (new_rows, new_place_infos);
1028 2817 : }
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 39 : WitnessPat::to_string () const
1047 : {
1048 39 : switch (ctor.get_kind ())
1049 : {
1050 4 : case Constructor::ConstructorKind::STRUCT:
1051 4 : {
1052 4 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1053 4 : TyTy::VariantDef *variant
1054 4 : = adt->get_variants ().at (ctor.get_variant_index ());
1055 4 : std::string buf;
1056 12 : buf += adt->get_identifier ();
1057 :
1058 4 : buf += " {";
1059 4 : if (!fields.empty ())
1060 4 : buf += " ";
1061 :
1062 12 : for (size_t i = 0; i < fields.size (); i++)
1063 : {
1064 24 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1065 16 : buf += fields.at (i).to_string ();
1066 8 : if (i < fields.size () - 1)
1067 4 : buf += ", ";
1068 : }
1069 4 : if (!fields.empty ())
1070 4 : buf += " ";
1071 :
1072 4 : buf += "}";
1073 4 : return buf;
1074 : }
1075 28 : break;
1076 28 : case Constructor::ConstructorKind::VARIANT:
1077 28 : {
1078 28 : std::string buf;
1079 28 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1080 84 : buf += adt->get_identifier ();
1081 28 : TyTy::VariantDef *variant
1082 28 : = adt->get_variants ().at (ctor.get_variant_index ());
1083 56 : buf += "::" + variant->get_identifier ();
1084 :
1085 28 : switch (variant->get_variant_type ())
1086 : {
1087 3 : case TyTy::VariantDef::VariantType::UNIT:
1088 3 : case TyTy::VariantDef::VariantType::NUM:
1089 3 : {
1090 3 : return buf;
1091 : }
1092 25 : break;
1093 25 : case TyTy::VariantDef::VariantType::TUPLE:
1094 25 : {
1095 25 : buf += "(";
1096 57 : 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 25 : buf += ")";
1103 25 : 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 28 : }
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 2817 : WitnessMatrix::apply_constructor (const Constructor &ctor,
1163 : const std::set<Constructor> &missings,
1164 : TyTy::BaseType *ty)
1165 : {
1166 2817 : int arity = 0;
1167 : // TODO: only support struct and variant ctor for now.
1168 2817 : switch (ctor.get_kind ())
1169 : {
1170 : case Constructor::ConstructorKind::WILDCARD:
1171 : {
1172 : arity = 0;
1173 : }
1174 : break;
1175 1457 : case Constructor::ConstructorKind::STRUCT:
1176 1457 : case Constructor::ConstructorKind::VARIANT:
1177 1457 : {
1178 1457 : if (ty->get_kind () == TyTy::TypeKind::ADT)
1179 : {
1180 1457 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1181 1457 : TyTy::VariantDef *variant
1182 1457 : = adt->get_variants ().at (ctor.get_variant_index ());
1183 1457 : if (variant->get_variant_type () == TyTy::VariantDef::NUM
1184 1457 : || variant->get_variant_type () == TyTy::VariantDef::UNIT)
1185 : arity = 0;
1186 : else
1187 850 : arity = variant->get_fields ().size ();
1188 : }
1189 : }
1190 : break;
1191 0 : default:
1192 0 : {
1193 0 : rust_unreachable ();
1194 : }
1195 : }
1196 :
1197 2817 : std::string buf;
1198 2836 : for (auto &stack : patstacks)
1199 : {
1200 19 : buf += "[";
1201 34 : for (auto &pat : stack)
1202 45 : buf += pat.to_string () + ", ";
1203 :
1204 19 : buf += "]\n";
1205 : }
1206 2817 : rust_debug ("witness pats:\n%s", buf.c_str ());
1207 :
1208 2836 : for (auto &stack : patstacks)
1209 : {
1210 19 : std::vector<WitnessPat> subfield;
1211 30 : for (int i = 0; i < arity; i++)
1212 : {
1213 11 : if (stack.empty ())
1214 1 : subfield.push_back (WitnessPat::make_wildcard (ty));
1215 : else
1216 : {
1217 10 : subfield.push_back (stack.back ());
1218 10 : stack.pop_back ();
1219 : }
1220 : }
1221 :
1222 19 : stack.emplace_back (ctor, subfield, ty);
1223 19 : }
1224 2817 : }
1225 :
1226 : void
1227 2817 : WitnessMatrix::extend (const WitnessMatrix &other)
1228 : {
1229 2817 : patstacks.insert (patstacks.end (), other.patstacks.begin (),
1230 : other.patstacks.end ());
1231 2817 : }
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 911 : lower_tuple_pattern (Resolver::TypeCheckContext *ctx,
1240 : HIR::TupleStructPattern &pattern,
1241 : TyTy::VariantDef *variant, Constructor &ctor)
1242 : {
1243 911 : int arity = variant->get_fields ().size ();
1244 911 : HIR::TupleStructItems &elems = pattern.get_items ();
1245 :
1246 911 : std::vector<DeconstructedPat> fields;
1247 911 : switch (elems.get_item_type ())
1248 : {
1249 875 : case HIR::TupleStructItems::ItemType::NO_REST:
1250 875 : {
1251 875 : HIR::TupleStructItemsNoRest &items_no_rest
1252 : = static_cast<HIR::TupleStructItemsNoRest &> (elems);
1253 :
1254 875 : rust_assert (variant->get_fields ().size ()
1255 : == items_no_rest.get_patterns ().size ());
1256 :
1257 1757 : for (size_t i = 0; i < items_no_rest.get_patterns ().size (); i++)
1258 : {
1259 882 : fields.push_back (
1260 1764 : lower_pattern (ctx, *items_no_rest.get_patterns ().at (i),
1261 882 : variant->get_fields ().at (i)->get_field_type ()));
1262 : }
1263 875 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1264 : }
1265 36 : break;
1266 36 : case HIR::TupleStructItems::ItemType::HAS_REST:
1267 36 : {
1268 36 : HIR::TupleStructItemsHasRest &items_has_rest
1269 : = static_cast<HIR::TupleStructItemsHasRest &> (elems);
1270 :
1271 36 : size_t num_patterns = items_has_rest.get_lower_patterns ().size ()
1272 36 : + items_has_rest.get_upper_patterns ().size ();
1273 :
1274 36 : rust_assert (num_patterns <= variant->num_fields ());
1275 :
1276 36 : size_t i = 0;
1277 65 : for (auto &pattern_member : items_has_rest.get_lower_patterns ())
1278 : {
1279 29 : fields.push_back (lower_pattern (
1280 29 : ctx, *pattern_member,
1281 29 : variant->get_fields ().at (i++)->get_field_type ()));
1282 : }
1283 100 : while (i < variant->num_fields ()
1284 100 : - items_has_rest.get_upper_patterns ().size ())
1285 : {
1286 64 : fields.push_back (
1287 64 : DeconstructedPat::make_wildcard (pattern.get_locus ()));
1288 64 : i++;
1289 : }
1290 50 : for (auto &pattern_member : items_has_rest.get_upper_patterns ())
1291 : {
1292 14 : fields.push_back (lower_pattern (
1293 14 : ctx, *pattern_member,
1294 14 : variant->get_fields ().at (i++)->get_field_type ()));
1295 : }
1296 36 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1297 : }
1298 0 : break;
1299 0 : default:
1300 0 : {
1301 0 : rust_unreachable ();
1302 : }
1303 : }
1304 911 : }
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 3693 : lower_pattern (Resolver::TypeCheckContext *ctx, HIR::Pattern &pattern,
1374 : TyTy::BaseType *scrutinee_ty)
1375 : {
1376 3693 : HIR::Pattern::PatternType pat_type = pattern.get_pattern_type ();
1377 3693 : switch (pat_type)
1378 : {
1379 1219 : case HIR::Pattern::PatternType::WILDCARD:
1380 1219 : case HIR::Pattern::PatternType::IDENTIFIER:
1381 1219 : {
1382 1219 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1383 : }
1384 795 : break;
1385 795 : case HIR::Pattern::PatternType::PATH:
1386 795 : {
1387 : // TODO: support constants, associated constants, enum variants and
1388 : // structs
1389 : // https://doc.rust-lang.org/reference/patterns.html#path-patterns
1390 : // unimplemented. Treat this pattern as wildcard for now.
1391 795 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1392 : }
1393 31 : break;
1394 31 : case HIR::Pattern::PatternType::REFERENCE:
1395 31 : {
1396 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1397 31 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1398 : }
1399 1004 : break;
1400 1004 : case HIR::Pattern::PatternType::STRUCT:
1401 1004 : case HIR::Pattern::PatternType::TUPLE_STRUCT:
1402 1004 : {
1403 1004 : HirId path_id = UNKNOWN_HIRID;
1404 1004 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1405 : {
1406 93 : HIR::StructPattern &struct_pattern
1407 : = static_cast<HIR::StructPattern &> (pattern);
1408 93 : path_id = struct_pattern.get_path ().get_mappings ().get_hirid ();
1409 : }
1410 : else
1411 : {
1412 911 : HIR::TupleStructPattern &tuple_pattern
1413 : = static_cast<HIR::TupleStructPattern &> (pattern);
1414 911 : path_id = tuple_pattern.get_path ().get_mappings ().get_hirid ();
1415 : }
1416 :
1417 1004 : rust_assert (scrutinee_ty->get_kind () == TyTy::TypeKind::ADT);
1418 1004 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (scrutinee_ty);
1419 :
1420 1004 : Constructor ctor = Constructor::make_struct ();
1421 1004 : TyTy::VariantDef *variant;
1422 1004 : if (adt->is_struct_struct () || adt->is_tuple_struct ())
1423 90 : variant = adt->get_variants ().at (0);
1424 914 : else if (adt->is_enum ())
1425 : {
1426 914 : HirId variant_id = UNKNOWN_HIRID;
1427 914 : bool ok = ctx->lookup_variant_definition (path_id, &variant_id);
1428 914 : rust_assert (ok);
1429 :
1430 914 : int variant_idx;
1431 914 : ok = adt->lookup_variant_by_id (variant_id, &variant, &variant_idx);
1432 914 : rust_assert (ok);
1433 :
1434 914 : ctor = Constructor::make_variant (variant_idx);
1435 : }
1436 : else
1437 : {
1438 0 : rust_unreachable ();
1439 : }
1440 1004 : rust_assert (variant->get_variant_type ()
1441 : == TyTy::VariantDef::VariantType::TUPLE
1442 : || variant->get_variant_type ()
1443 : == TyTy::VariantDef::VariantType::STRUCT);
1444 :
1445 1004 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1446 : {
1447 93 : HIR::StructPattern &struct_pattern
1448 : = static_cast<HIR::StructPattern &> (pattern);
1449 93 : return lower_struct_pattern (ctx, struct_pattern, variant, ctor);
1450 : }
1451 : else
1452 : {
1453 911 : HIR::TupleStructPattern &tuple_pattern
1454 : = static_cast<HIR::TupleStructPattern &> (pattern);
1455 911 : return lower_tuple_pattern (ctx, tuple_pattern, variant, ctor);
1456 : }
1457 : }
1458 147 : break;
1459 147 : case HIR::Pattern::PatternType::TUPLE:
1460 147 : {
1461 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1462 147 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1463 : }
1464 75 : break;
1465 75 : case HIR::Pattern::PatternType::SLICE:
1466 75 : {
1467 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1468 75 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1469 : }
1470 152 : break;
1471 152 : case HIR::Pattern::PatternType::ALT:
1472 152 : {
1473 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1474 152 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1475 : }
1476 226 : break;
1477 226 : case HIR::Pattern::PatternType::LITERAL:
1478 226 : {
1479 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1480 226 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1481 : }
1482 44 : break;
1483 44 : case HIR::Pattern::PatternType::RANGE:
1484 44 : {
1485 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1486 44 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1487 : }
1488 0 : break;
1489 0 : case HIR::Pattern::PatternType::GROUPED:
1490 0 : {
1491 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1492 0 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1493 : }
1494 0 : break;
1495 0 : default:
1496 0 : {
1497 0 : rust_unreachable ();
1498 : }
1499 : }
1500 : }
1501 :
1502 : static MatchArm
1503 2695 : lower_arm (Resolver::TypeCheckContext *ctx, HIR::MatchCase &arm,
1504 : TyTy::BaseType *scrutinee_ty)
1505 : {
1506 2695 : rust_assert (arm.get_arm ().get_pattern () != nullptr);
1507 :
1508 2695 : DeconstructedPat pat
1509 2695 : = lower_pattern (ctx, *arm.get_arm ().get_pattern (), scrutinee_ty);
1510 2695 : return MatchArm (pat, arm.get_arm ().has_match_arm_guard ());
1511 2695 : }
1512 :
1513 : std::pair<std::set<Constructor>, std::set<Constructor>>
1514 2084 : split_constructors (std::vector<Constructor> &ctors, PlaceInfo &place_info)
1515 : {
1516 2084 : bool all_wildcard = true;
1517 6742 : for (auto &ctor : ctors)
1518 : {
1519 4658 : if (!ctor.is_wildcard ())
1520 1007 : all_wildcard = false;
1521 : }
1522 :
1523 : // first pass for the case that all patterns are wildcard
1524 2084 : if (all_wildcard)
1525 2720 : return std::make_pair (std::set<Constructor> (
1526 2720 : {Constructor::make_wildcard ()}),
1527 4080 : std::set<Constructor> ());
1528 :
1529 : // TODO: only support enums and structs for now.
1530 724 : TyTy::BaseType *ty = place_info.get_type ();
1531 724 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
1532 724 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1533 724 : rust_assert (adt->is_enum () || adt->is_struct_struct ()
1534 : || adt->is_tuple_struct ());
1535 :
1536 724 : std::set<Constructor> universe;
1537 724 : if (adt->is_enum ())
1538 : {
1539 2065 : for (size_t i = 0; i < adt->get_variants ().size (); i++)
1540 1399 : universe.insert (Constructor::make_variant (i));
1541 : }
1542 58 : else if (adt->is_struct_struct () || adt->is_tuple_struct ())
1543 : {
1544 58 : universe.insert (Constructor::make_struct ());
1545 : }
1546 :
1547 724 : std::set<Constructor> present;
1548 1649 : for (auto &ctor : ctors)
1549 : {
1550 1553 : if (ctor.is_wildcard ())
1551 1256 : return std::make_pair (universe, std::set<Constructor> ());
1552 : else
1553 925 : present.insert (ctor);
1554 : }
1555 :
1556 96 : std::set<Constructor> missing;
1557 96 : std::set_difference (universe.begin (), universe.end (), present.begin (),
1558 : present.end (), std::inserter (missing, missing.end ()));
1559 192 : return std::make_pair (universe, missing);
1560 820 : }
1561 :
1562 : // The core of the algorithm. It computes the usefulness and exhaustiveness of a
1563 : // given matrix recursively.
1564 : // TODO: calculate usefulness
1565 : static WitnessMatrix
1566 3976 : compute_exhaustiveness_and_usefulness (Resolver::TypeCheckContext *ctx,
1567 : Matrix &matrix)
1568 : {
1569 3976 : rust_debug ("call compute_exhaustiveness_and_usefulness");
1570 3976 : rust_debug ("matrix: %s", matrix.to_string ().c_str ());
1571 :
1572 3976 : if (matrix.get_rows ().empty ())
1573 : {
1574 : // no rows left. This means a non-exhaustive pattern.
1575 9 : rust_debug ("non-exhaustive subpattern found");
1576 9 : return WitnessMatrix::make_unit ();
1577 : }
1578 :
1579 : // Base case: there are no columns in matrix.
1580 3967 : if (matrix.get_place_infos ().empty ())
1581 1883 : return WitnessMatrix::make_empty ();
1582 :
1583 2084 : std::vector<Constructor> heads;
1584 6742 : for (auto head : matrix.heads ())
1585 11400 : heads.push_back (head.ctor ());
1586 :
1587 : // TODO: not sure missing ctors need to be calculated
1588 2084 : auto ctors_and_missings
1589 2084 : = split_constructors (heads, matrix.get_place_infos ().at (0));
1590 2084 : std::set<Constructor> ctors = ctors_and_missings.first;
1591 2084 : std::set<Constructor> missings = ctors_and_missings.second;
1592 :
1593 2084 : WitnessMatrix ret = WitnessMatrix::make_empty ();
1594 4901 : for (auto &ctor : ctors)
1595 : {
1596 2817 : rust_debug ("specialize with %s", ctor.to_string ().c_str ());
1597 : // TODO: Instead of creating new matrix, we can change the original matrix
1598 : // and use it for sub-pattern matching. It will significantly reduce
1599 : // memory usage.
1600 2817 : Matrix spec_matrix = matrix.specialize (ctor);
1601 :
1602 2817 : WitnessMatrix witness
1603 2817 : = compute_exhaustiveness_and_usefulness (ctx, spec_matrix);
1604 :
1605 2817 : TyTy::BaseType *ty = matrix.get_place_infos ().at (0).get_type ();
1606 2817 : witness.apply_constructor (ctor, missings, ty);
1607 2817 : ret.extend (witness);
1608 5634 : }
1609 :
1610 2084 : return ret;
1611 2084 : }
1612 :
1613 : static void
1614 1159 : emit_exhaustiveness_error (Resolver::TypeCheckContext *ctx,
1615 : HIR::MatchExpr &expr, WitnessMatrix &witness)
1616 : {
1617 1159 : TyTy::BaseType *scrutinee_ty;
1618 1159 : bool ok
1619 1159 : = ctx->lookup_type (expr.get_scrutinee_expr ().get_mappings ().get_hirid (),
1620 : &scrutinee_ty);
1621 1159 : rust_assert (ok);
1622 :
1623 1159 : if (!witness.empty ())
1624 : {
1625 7 : std::stringstream buf;
1626 23 : for (size_t i = 0; i < witness.get_stacks ().size (); i++)
1627 : {
1628 9 : auto &stack = witness.get_stacks ().at (i);
1629 9 : WitnessPat w = WitnessPat::make_wildcard (scrutinee_ty);
1630 9 : if (!stack.empty ())
1631 9 : w = stack.at (0);
1632 :
1633 9 : rust_debug ("Witness[%d]: %s", (int) i, w.to_string ().c_str ());
1634 18 : buf << "'" << w.to_string () << "'";
1635 9 : if (i != witness.get_stacks ().size () - 1)
1636 2 : buf << " and ";
1637 9 : }
1638 7 : rust_error_at (expr.get_scrutinee_expr ().get_locus (),
1639 : "non-exhaustive patterns: %s not covered",
1640 7 : buf.str ().c_str ());
1641 7 : }
1642 : else
1643 : {
1644 1152 : rust_debug ("no witness found");
1645 : }
1646 1159 : }
1647 :
1648 : // Entry point for computing match usefulness and check exhaustiveness
1649 : void
1650 1164 : check_match_usefulness (Resolver::TypeCheckContext *ctx,
1651 : TyTy::BaseType *scrutinee_ty, HIR::MatchExpr &expr)
1652 : {
1653 1164 : if (!expr.has_match_arms ())
1654 5 : return;
1655 :
1656 : // Lower the arms to a more convenient representation.
1657 1159 : std::vector<MatrixRow> rows;
1658 3854 : for (auto &arm : expr.get_match_cases ())
1659 : {
1660 2695 : PatStack pats;
1661 2695 : MatchArm lowered = lower_arm (ctx, arm, scrutinee_ty);
1662 2695 : PatOrWild pat = PatOrWild::make_pattern (lowered.get_pat ());
1663 2695 : pats.push (pat);
1664 2695 : rows.emplace_back (pats, lowered.has_guard ());
1665 2695 : }
1666 :
1667 1159 : std::vector<PlaceInfo> place_infos = {{PlaceInfo (scrutinee_ty)}};
1668 2318 : Matrix matrix{rows, place_infos};
1669 :
1670 1159 : WitnessMatrix witness = compute_exhaustiveness_and_usefulness (ctx, matrix);
1671 :
1672 1159 : emit_exhaustiveness_error (ctx, expr, witness);
1673 2318 : }
1674 :
1675 : } // namespace Analysis
1676 : } // namespace Rust
|
