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