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 4501 : PatternChecker::PatternChecker ()
36 4501 : : tyctx (*Resolver::TypeCheckContext::get ()),
37 4501 : resolver (Resolver2_0::FinalizedNameResolutionContext::get ()),
38 9002 : mappings (Analysis::Mappings::get ())
39 4501 : {}
40 :
41 : void
42 4501 : PatternChecker::go (HIR::Crate &crate)
43 : {
44 4501 : rust_debug ("started pattern check");
45 23663 : for (auto &item : crate.get_items ())
46 19167 : item->accept_vis (*this);
47 4496 : rust_debug ("finished pattern check");
48 4496 : }
49 :
50 : void
51 0 : PatternChecker::visit (Lifetime &)
52 0 : {}
53 :
54 : void
55 0 : PatternChecker::visit (LifetimeParam &)
56 0 : {}
57 :
58 : void
59 37103 : PatternChecker::visit (PathInExpression &path)
60 37103 : {}
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 20089 : PatternChecker::visit (LiteralExpr &)
88 20089 : {}
89 :
90 : void
91 2131 : PatternChecker::visit (BorrowExpr &expr)
92 : {
93 2131 : expr.get_expr ().accept_vis (*this);
94 2131 : }
95 :
96 : void
97 4275 : PatternChecker::visit (DereferenceExpr &expr)
98 : {
99 4275 : expr.get_expr ().accept_vis (*this);
100 4275 : }
101 :
102 : void
103 0 : PatternChecker::visit (ErrorPropagationExpr &expr)
104 : {
105 0 : expr.get_expr ().accept_vis (*this);
106 0 : }
107 :
108 : void
109 603 : PatternChecker::visit (NegationExpr &expr)
110 : {
111 603 : expr.get_expr ().accept_vis (*this);
112 603 : }
113 :
114 : void
115 3565 : PatternChecker::visit (ArithmeticOrLogicalExpr &expr)
116 : {
117 3565 : expr.get_lhs ().accept_vis (*this);
118 3565 : expr.get_rhs ().accept_vis (*this);
119 3565 : }
120 :
121 : void
122 3733 : PatternChecker::visit (ComparisonExpr &expr)
123 : {
124 3733 : expr.get_lhs ().accept_vis (*this);
125 3733 : expr.get_rhs ().accept_vis (*this);
126 3733 : }
127 :
128 : void
129 424 : PatternChecker::visit (LazyBooleanExpr &expr)
130 : {
131 424 : expr.get_lhs ().accept_vis (*this);
132 424 : expr.get_rhs ().accept_vis (*this);
133 424 : }
134 :
135 : void
136 5662 : PatternChecker::visit (TypeCastExpr &expr)
137 : {
138 5662 : expr.get_expr ().accept_vis (*this);
139 5662 : }
140 :
141 : void
142 2520 : PatternChecker::visit (AssignmentExpr &expr)
143 : {
144 2520 : expr.get_lhs ().accept_vis (*this);
145 2520 : expr.get_rhs ().accept_vis (*this);
146 2520 : }
147 :
148 : void
149 704 : PatternChecker::visit (CompoundAssignmentExpr &expr)
150 : {
151 704 : expr.get_lhs ().accept_vis (*this);
152 704 : expr.get_rhs ().accept_vis (*this);
153 704 : }
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 115 : PatternChecker::visit (ArrayElemsCopied &elems)
170 : {
171 115 : elems.get_elem_to_copy ().accept_vis (*this);
172 115 : }
173 :
174 : void
175 413 : PatternChecker::visit (ArrayExpr &expr)
176 : {
177 413 : expr.get_internal_elements ().accept_vis (*this);
178 413 : }
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 600 : PatternChecker::visit (TupleExpr &expr)
189 : {
190 1655 : for (auto &elem : expr.get_tuple_elems ())
191 1055 : elem->accept_vis (*this);
192 600 : }
193 :
194 : void
195 898 : PatternChecker::visit (TupleIndexExpr &expr)
196 : {
197 898 : expr.get_tuple_expr ().accept_vis (*this);
198 898 : }
199 :
200 : void
201 79 : PatternChecker::visit (StructExprStruct &)
202 79 : {}
203 :
204 : void
205 235 : PatternChecker::visit (StructExprFieldIdentifier &)
206 235 : {}
207 :
208 : void
209 2727 : PatternChecker::visit (StructExprFieldIdentifierValue &field)
210 : {
211 2727 : field.get_value ().accept_vis (*this);
212 2727 : }
213 :
214 : void
215 42 : PatternChecker::visit (StructExprFieldIndexValue &field)
216 : {
217 42 : field.get_value ().accept_vis (*this);
218 42 : }
219 :
220 : void
221 1406 : PatternChecker::visit (StructExprStructFields &expr)
222 : {
223 4410 : for (auto &field : expr.get_fields ())
224 3004 : field->accept_vis (*this);
225 1406 : }
226 :
227 : void
228 0 : PatternChecker::visit (StructExprStructBase &)
229 0 : {}
230 :
231 : void
232 13059 : PatternChecker::visit (CallExpr &expr)
233 : {
234 13059 : if (!expr.has_fnexpr ())
235 : return;
236 :
237 13059 : NodeId ast_node_id = expr.get_fnexpr ().get_mappings ().get_nodeid ();
238 13059 : NodeId ref_node_id;
239 13059 : if (auto id = resolver.lookup (ast_node_id, Resolver2_0::Namespace::Values))
240 12989 : ref_node_id = *id;
241 : else
242 70 : return;
243 :
244 12989 : if (auto definition_id = mappings.lookup_node_to_hir (ref_node_id))
245 : {
246 12989 : if (expr.has_params ())
247 25451 : for (auto &arg : expr.get_arguments ())
248 15005 : arg->accept_vis (*this);
249 : }
250 : else
251 : {
252 0 : rust_unreachable ();
253 : }
254 : }
255 :
256 : void
257 3138 : PatternChecker::visit (MethodCallExpr &expr)
258 : {
259 3138 : expr.get_receiver ().accept_vis (*this);
260 :
261 5283 : for (auto &arg : expr.get_arguments ())
262 2145 : arg->accept_vis (*this);
263 3138 : }
264 :
265 : void
266 5702 : PatternChecker::visit (FieldAccessExpr &expr)
267 : {
268 5702 : expr.get_receiver_expr ().accept_vis (*this);
269 5702 : }
270 :
271 : void
272 53 : PatternChecker::visit (ClosureExpr &expr)
273 : {
274 53 : expr.get_expr ().accept_vis (*this);
275 53 : }
276 :
277 : void
278 24850 : PatternChecker::visit (BlockExpr &expr)
279 : {
280 49827 : for (auto &stmt : expr.get_statements ())
281 24977 : stmt->accept_vis (*this);
282 :
283 24850 : if (expr.has_expr ())
284 17959 : expr.get_final_expr ().accept_vis (*this);
285 24850 : }
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 560 : PatternChecker::visit (ReturnExpr &expr)
347 : {
348 560 : if (expr.has_return_expr ())
349 524 : expr.get_expr ().accept_vis (*this);
350 560 : }
351 :
352 : void
353 3991 : PatternChecker::visit (UnsafeBlockExpr &expr)
354 : {
355 3991 : expr.get_block_expr ().accept_vis (*this);
356 3991 : }
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 1280 : PatternChecker::visit (IfExpr &expr)
380 : {
381 1280 : expr.get_if_condition ().accept_vis (*this);
382 1280 : expr.get_if_block ().accept_vis (*this);
383 1280 : }
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 1120 : PatternChecker::visit (MatchExpr &expr)
395 : {
396 1120 : expr.get_scrutinee_expr ().accept_vis (*this);
397 :
398 3680 : for (auto &match_arm : expr.get_match_cases ())
399 2560 : match_arm.get_expr ().accept_vis (*this);
400 :
401 : // match expressions are only an entrypoint
402 1120 : TyTy::BaseType *scrutinee_ty;
403 1120 : bool ok = tyctx.lookup_type (
404 1120 : expr.get_scrutinee_expr ().get_mappings ().get_hirid (), &scrutinee_ty);
405 1120 : rust_assert (ok);
406 :
407 1120 : check_match_usefulness (&tyctx, scrutinee_ty, expr);
408 1120 : }
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 1245 : PatternChecker::visit (Module &module)
452 : {
453 5418 : for (auto &item : module.get_items ())
454 4173 : item->accept_vis (*this);
455 1245 : }
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 14539 : PatternChecker::visit (Function &function)
479 : {
480 21751 : for (auto ¶m : function.get_function_params ())
481 : {
482 7217 : TyTy::BaseType *param_ty;
483 7217 : bool ok
484 7217 : = tyctx.lookup_type (param.get_mappings ().get_hirid (), ¶m_ty);
485 7217 : rust_assert (ok);
486 :
487 7217 : 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 14534 : function.get_definition ().accept_vis (*this);
492 14534 : }
493 :
494 : void
495 1468 : PatternChecker::visit (TypeAlias &)
496 1468 : {}
497 :
498 : void
499 1611 : PatternChecker::visit (StructStruct &)
500 1611 : {}
501 :
502 : void
503 973 : PatternChecker::visit (TupleStruct &)
504 973 : {}
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 529 : PatternChecker::visit (Enum &)
524 529 : {}
525 :
526 : void
527 102 : PatternChecker::visit (Union &)
528 102 : {}
529 :
530 : void
531 529 : PatternChecker::visit (ConstantItem &const_item)
532 : {
533 529 : const_item.get_expr ().accept_vis (*this);
534 529 : }
535 :
536 : void
537 56 : PatternChecker::visit (StaticItem &static_item)
538 : {
539 56 : static_item.get_expr ().accept_vis (*this);
540 56 : }
541 :
542 : void
543 2683 : PatternChecker::visit (TraitItemFunc &item)
544 : {
545 2683 : if (item.has_definition ())
546 861 : item.get_block_expr ().accept_vis (*this);
547 2683 : }
548 :
549 : void
550 32 : PatternChecker::visit (TraitItemConst &item)
551 : {
552 32 : if (item.has_expr ())
553 7 : item.get_expr ().accept_vis (*this);
554 32 : }
555 :
556 : void
557 786 : PatternChecker::visit (TraitItemType &)
558 786 : {}
559 :
560 : void
561 4001 : PatternChecker::visit (Trait &trait)
562 : {
563 7502 : for (auto &item : trait.get_trait_items ())
564 3501 : item->accept_vis (*this);
565 4001 : }
566 :
567 : void
568 6321 : PatternChecker::visit (ImplBlock &impl)
569 : {
570 15647 : for (auto &item : impl.get_impl_items ())
571 9326 : item->accept_vis (*this);
572 6321 : }
573 :
574 : void
575 1 : PatternChecker::visit (ExternalStaticItem &)
576 1 : {}
577 :
578 : void
579 2668 : PatternChecker::visit (ExternalFunctionItem &)
580 2668 : {}
581 :
582 : void
583 2 : PatternChecker::visit (ExternalTypeItem &)
584 2 : {}
585 :
586 : void
587 1701 : PatternChecker::visit (ExternBlock &block)
588 : {
589 : // FIXME: Do we need to do this?
590 4372 : for (auto &item : block.get_extern_items ())
591 2671 : item->accept_vis (*this);
592 1701 : }
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 13308 : PatternChecker::visit (LetStmt &stmt)
688 : {
689 13308 : if (stmt.has_init_expr ())
690 12154 : stmt.get_init_expr ().accept_vis (*this);
691 :
692 : // skip let-else (allows refutable patterns)
693 13308 : if (stmt.has_else_expr ())
694 5 : return;
695 :
696 13303 : TyTy::BaseType *binding_ty;
697 13303 : bool ok = tyctx.lookup_type (stmt.get_pattern ().get_mappings ().get_hirid (),
698 : &binding_ty);
699 13303 : if (!ok)
700 : return; // type-check failed earlier
701 :
702 13303 : 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 11215 : PatternChecker::visit (ExprStmt &stmt)
709 : {
710 11215 : stmt.get_expr ().accept_vis (*this);
711 11215 : }
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 16291 : Constructor::is_covered_by (const Constructor &o) const
763 : {
764 16291 : if (o.kind == ConstructorKind::WILDCARD)
765 : return true;
766 :
767 3817 : switch (kind)
768 : {
769 3565 : case ConstructorKind::VARIANT:
770 3565 : {
771 3565 : rust_assert (kind == ConstructorKind::VARIANT);
772 3565 : 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 3048 : Constructor::operator< (const Constructor &o) const
803 : {
804 3048 : if (kind != o.kind)
805 0 : return kind < o.kind;
806 :
807 3048 : switch (kind)
808 : {
809 2958 : case ConstructorKind::VARIANT:
810 2958 : 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 1854 : Constructor::to_string () const
826 : {
827 1854 : switch (kind)
828 : {
829 0 : case ConstructorKind::STRUCT:
830 0 : return "STRUCT";
831 15 : case ConstructorKind::VARIANT:
832 30 : 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 1839 : case ConstructorKind::WILDCARD:
837 1839 : 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 5109 : DeconstructedPat::specialize (const Constructor &other_ctor,
847 : int other_ctor_arity) const
848 : {
849 5109 : rust_assert (other_ctor.is_covered_by (ctor));
850 5109 : if (ctor.is_wildcard ())
851 4158 : return std::vector<DeconstructedPat> (
852 : other_ctor_arity,
853 4158 : DeconstructedPat (Constructor::make_wildcard (), locus));
854 :
855 951 : return fields;
856 : }
857 :
858 : std::string
859 1854 : DeconstructedPat::to_string () const
860 : {
861 3708 : std::string s = ctor.to_string () + "[";
862 1855 : for (auto &f : fields)
863 3 : s += f.to_string () + ", ";
864 :
865 5562 : s += "](arity=" + std::to_string (arity) + ")";
866 1854 : 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 5109 : PatOrWild::specialize (const Constructor &other_ctor,
880 : int other_ctor_arity) const
881 : {
882 5109 : if (pat.has_value ())
883 : {
884 5109 : auto v = pat.value ().specialize (other_ctor, other_ctor_arity);
885 5109 : std::vector<PatOrWild> ret;
886 6962 : for (auto &pat : v)
887 3706 : ret.push_back (PatOrWild::make_pattern (pat));
888 :
889 5109 : return ret;
890 5109 : }
891 : else
892 : {
893 0 : return std::vector<PatOrWild> (other_ctor_arity,
894 0 : PatOrWild::make_wildcard ());
895 : }
896 : }
897 :
898 : std::string
899 1853 : PatOrWild::to_string () const
900 : {
901 1853 : if (pat.has_value ())
902 1853 : return pat.value ().to_string ();
903 : else
904 0 : return "Wild";
905 : }
906 :
907 : void
908 5109 : PatStack::pop_head_constructor (const Constructor &other_ctor,
909 : int other_ctor_arity)
910 : {
911 5109 : rust_assert (!pats.empty ());
912 5109 : rust_assert (other_ctor.is_covered_by (head ().ctor ()));
913 :
914 5109 : PatOrWild &hd = head ();
915 5109 : auto v = hd.specialize (other_ctor, other_ctor_arity);
916 5109 : {
917 5109 : std::string s = "[";
918 6962 : for (auto &pat : v)
919 5559 : s += pat.to_string () + ", ";
920 5109 : s += "]";
921 :
922 5109 : rust_debug ("specialize %s with %s to %s", hd.to_string ().c_str (),
923 : other_ctor.to_string ().c_str (), s.c_str ());
924 5109 : }
925 5109 : pop_head ();
926 6962 : for (auto &pat : v)
927 1853 : pats.push_back (pat);
928 5109 : }
929 :
930 : std::string
931 0 : MatrixRow::to_string () const
932 : {
933 0 : std::string s;
934 0 : for (const PatOrWild &pat : pats.get_subpatterns ())
935 0 : s += pat.to_string () + ", ";
936 0 : return s;
937 : }
938 :
939 : std::vector<PlaceInfo>
940 2702 : PlaceInfo::specialize (const Constructor &c) const
941 : {
942 2702 : switch (c.get_kind ())
943 : {
944 1295 : case Constructor::ConstructorKind::WILDCARD:
945 1295 : case Constructor::ConstructorKind::INT_RANGE:
946 1295 : {
947 1295 : return {};
948 : }
949 1407 : break;
950 1407 : case Constructor::ConstructorKind::STRUCT:
951 1407 : case Constructor::ConstructorKind::VARIANT:
952 1407 : {
953 1407 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
954 1407 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
955 1407 : switch (adt->get_adt_kind ())
956 : {
957 1407 : case TyTy::ADTType::ADTKind::ENUM:
958 1407 : case TyTy::ADTType::ADTKind::STRUCT_STRUCT:
959 1407 : case TyTy::ADTType::ADTKind::TUPLE_STRUCT:
960 1407 : {
961 1407 : TyTy::VariantDef *variant
962 1407 : = adt->get_variants ().at (c.get_variant_index ());
963 1407 : if (variant->get_variant_type ()
964 : == TyTy::VariantDef::VariantType::NUM
965 1407 : || variant->get_variant_type ()
966 : == TyTy::VariantDef::VariantType::UNIT)
967 595 : return {};
968 :
969 812 : std::vector<PlaceInfo> new_place_infos;
970 1689 : for (auto &field : variant->get_fields ())
971 877 : new_place_infos.push_back (field->get_field_type ());
972 :
973 812 : return new_place_infos;
974 812 : }
975 0 : break;
976 0 : case TyTy::ADTType::ADTKind::UNION:
977 0 : {
978 : // TODO: support unions
979 0 : rust_unreachable ();
980 : }
981 0 : case TyTy::ADTType::ADTKind::EXTERN:
982 0 : return {};
983 : }
984 : }
985 0 : break;
986 0 : default:
987 0 : {
988 0 : rust_unreachable ();
989 : }
990 0 : break;
991 : }
992 :
993 0 : rust_unreachable ();
994 : }
995 :
996 : Matrix
997 2702 : Matrix::specialize (const Constructor &ctor) const
998 : {
999 2702 : auto subfields_place_info = place_infos.at (0).specialize (ctor);
1000 :
1001 2702 : std::vector<MatrixRow> new_rows;
1002 8775 : for (const MatrixRow &row : rows)
1003 : {
1004 6073 : PatStack pats = row.get_pats_clone ();
1005 6073 : const PatOrWild &hd = pats.head ();
1006 6073 : if (ctor.is_covered_by (hd.ctor ()))
1007 : {
1008 5109 : pats.pop_head_constructor (ctor, subfields_place_info.size ());
1009 5109 : new_rows.emplace_back (pats, row.is_under_guard ());
1010 : }
1011 6073 : }
1012 :
1013 2702 : if (place_infos.empty ())
1014 0 : return Matrix (new_rows, {});
1015 :
1016 : // push subfields of the first fields after specialization
1017 2702 : std::vector<PlaceInfo> new_place_infos = subfields_place_info;
1018 : // add place infos for the rest of the fields
1019 5515 : for (size_t i = 1; i < place_infos.size (); i++)
1020 111 : new_place_infos.push_back (place_infos.at (i));
1021 :
1022 5404 : return Matrix (new_rows, new_place_infos);
1023 2702 : }
1024 :
1025 : std::string
1026 0 : Matrix::to_string () const
1027 : {
1028 0 : std::string s = "[\n";
1029 0 : for (const MatrixRow &row : rows)
1030 0 : s += "row: " + row.to_string () + "\n";
1031 :
1032 0 : s += "](place_infos=[";
1033 0 : for (const PlaceInfo &place_info : place_infos)
1034 0 : s += place_info.get_type ()->as_string () + ", ";
1035 :
1036 0 : s += "])";
1037 0 : return s;
1038 : }
1039 :
1040 : std::string
1041 18 : WitnessPat::to_string () const
1042 : {
1043 18 : switch (ctor.get_kind ())
1044 : {
1045 2 : case Constructor::ConstructorKind::STRUCT:
1046 2 : {
1047 2 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1048 2 : TyTy::VariantDef *variant
1049 2 : = adt->get_variants ().at (ctor.get_variant_index ());
1050 2 : std::string buf;
1051 6 : buf += adt->get_identifier ();
1052 :
1053 2 : buf += " {";
1054 2 : if (!fields.empty ())
1055 2 : buf += " ";
1056 :
1057 6 : for (size_t i = 0; i < fields.size (); i++)
1058 : {
1059 12 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1060 8 : buf += fields.at (i).to_string ();
1061 4 : if (i < fields.size () - 1)
1062 2 : buf += ", ";
1063 : }
1064 2 : if (!fields.empty ())
1065 2 : buf += " ";
1066 :
1067 2 : buf += "}";
1068 2 : return buf;
1069 : }
1070 16 : break;
1071 16 : case Constructor::ConstructorKind::VARIANT:
1072 16 : {
1073 16 : std::string buf;
1074 16 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1075 48 : buf += adt->get_identifier ();
1076 16 : TyTy::VariantDef *variant
1077 16 : = adt->get_variants ().at (ctor.get_variant_index ());
1078 32 : buf += "::" + variant->get_identifier ();
1079 :
1080 16 : switch (variant->get_variant_type ())
1081 : {
1082 3 : case TyTy::VariantDef::VariantType::UNIT:
1083 3 : case TyTy::VariantDef::VariantType::NUM:
1084 3 : {
1085 3 : return buf;
1086 : }
1087 13 : break;
1088 13 : case TyTy::VariantDef::VariantType::TUPLE:
1089 13 : {
1090 13 : buf += "(";
1091 27 : for (size_t i = 0; i < fields.size (); i++)
1092 : {
1093 2 : buf += fields.at (i).to_string ();
1094 1 : if (i < fields.size () - 1)
1095 0 : buf += ", ";
1096 : }
1097 13 : buf += ")";
1098 13 : return buf;
1099 : }
1100 0 : break;
1101 0 : case TyTy::VariantDef::VariantType::STRUCT:
1102 0 : {
1103 0 : buf += " {";
1104 0 : if (!fields.empty ())
1105 0 : buf += " ";
1106 :
1107 0 : for (size_t i = 0; i < fields.size (); i++)
1108 : {
1109 0 : buf += variant->get_fields ().at (i)->get_name () + ": ";
1110 0 : buf += fields.at (i).to_string ();
1111 0 : if (i < fields.size () - 1)
1112 0 : buf += ", ";
1113 : }
1114 :
1115 0 : if (!fields.empty ())
1116 0 : buf += " ";
1117 :
1118 0 : buf += "}";
1119 : }
1120 0 : break;
1121 0 : default:
1122 0 : {
1123 0 : rust_unreachable ();
1124 : }
1125 0 : break;
1126 : }
1127 0 : return buf;
1128 16 : }
1129 0 : break;
1130 0 : case Constructor::ConstructorKind::INT_RANGE:
1131 0 : {
1132 : // TODO: implement
1133 0 : rust_unreachable ();
1134 : }
1135 0 : break;
1136 0 : case Constructor::ConstructorKind::WILDCARD:
1137 0 : {
1138 0 : return "_";
1139 : }
1140 0 : break;
1141 0 : case Constructor::ConstructorKind::REFERENCE:
1142 0 : {
1143 : // TODO: implement
1144 0 : rust_unreachable ();
1145 : }
1146 0 : break;
1147 0 : default:
1148 0 : {
1149 0 : rust_unreachable ();
1150 : }
1151 : break;
1152 : }
1153 : rust_unreachable ();
1154 : }
1155 :
1156 : void
1157 2702 : WitnessMatrix::apply_constructor (const Constructor &ctor,
1158 : const std::set<Constructor> &missings,
1159 : TyTy::BaseType *ty)
1160 : {
1161 2702 : int arity = 0;
1162 : // TODO: only support struct and variant ctor for now.
1163 2702 : switch (ctor.get_kind ())
1164 : {
1165 : case Constructor::ConstructorKind::WILDCARD:
1166 : {
1167 : arity = 0;
1168 : }
1169 : break;
1170 1407 : case Constructor::ConstructorKind::STRUCT:
1171 1407 : case Constructor::ConstructorKind::VARIANT:
1172 1407 : {
1173 1407 : if (ty->get_kind () == TyTy::TypeKind::ADT)
1174 : {
1175 1407 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1176 1407 : TyTy::VariantDef *variant
1177 1407 : = adt->get_variants ().at (ctor.get_variant_index ());
1178 1407 : if (variant->get_variant_type () == TyTy::VariantDef::NUM
1179 1407 : || variant->get_variant_type () == TyTy::VariantDef::UNIT)
1180 : arity = 0;
1181 : else
1182 812 : arity = variant->get_fields ().size ();
1183 : }
1184 : }
1185 : break;
1186 0 : default:
1187 0 : {
1188 0 : rust_unreachable ();
1189 : }
1190 : }
1191 :
1192 2702 : std::string buf;
1193 2713 : for (auto &stack : patstacks)
1194 : {
1195 11 : buf += "[";
1196 18 : for (auto &pat : stack)
1197 21 : buf += pat.to_string () + ", ";
1198 :
1199 11 : buf += "]\n";
1200 : }
1201 2702 : rust_debug ("witness pats:\n%s", buf.c_str ());
1202 :
1203 2713 : for (auto &stack : patstacks)
1204 : {
1205 11 : std::vector<WitnessPat> subfield;
1206 16 : for (int i = 0; i < arity; i++)
1207 : {
1208 5 : if (stack.empty ())
1209 0 : subfield.push_back (WitnessPat::make_wildcard (ty));
1210 : else
1211 : {
1212 5 : subfield.push_back (stack.back ());
1213 5 : stack.pop_back ();
1214 : }
1215 : }
1216 :
1217 11 : stack.emplace_back (ctor, subfield, ty);
1218 11 : }
1219 2702 : }
1220 :
1221 : void
1222 2702 : WitnessMatrix::extend (const WitnessMatrix &other)
1223 : {
1224 2702 : patstacks.insert (patstacks.end (), other.patstacks.begin (),
1225 : other.patstacks.end ());
1226 2702 : }
1227 :
1228 : // forward declarations
1229 : static DeconstructedPat lower_pattern (Resolver::TypeCheckContext *ctx,
1230 : HIR::Pattern &pattern,
1231 : TyTy::BaseType *scrutinee_ty);
1232 :
1233 : static DeconstructedPat
1234 856 : lower_tuple_pattern (Resolver::TypeCheckContext *ctx,
1235 : HIR::TupleStructPattern &pattern,
1236 : TyTy::VariantDef *variant, Constructor &ctor)
1237 : {
1238 856 : int arity = variant->get_fields ().size ();
1239 856 : HIR::TupleStructItems &elems = pattern.get_items ();
1240 :
1241 856 : std::vector<DeconstructedPat> fields;
1242 856 : switch (elems.get_item_type ())
1243 : {
1244 820 : case HIR::TupleStructItems::ItemType::NO_REST:
1245 820 : {
1246 820 : HIR::TupleStructItemsNoRest &items_no_rest
1247 : = static_cast<HIR::TupleStructItemsNoRest &> (elems);
1248 :
1249 820 : rust_assert (variant->get_fields ().size ()
1250 : == items_no_rest.get_patterns ().size ());
1251 :
1252 1628 : for (size_t i = 0; i < items_no_rest.get_patterns ().size (); i++)
1253 : {
1254 808 : fields.push_back (
1255 1616 : lower_pattern (ctx, *items_no_rest.get_patterns ().at (i),
1256 808 : variant->get_fields ().at (i)->get_field_type ()));
1257 : }
1258 820 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1259 : }
1260 36 : break;
1261 36 : case HIR::TupleStructItems::ItemType::HAS_REST:
1262 36 : {
1263 36 : HIR::TupleStructItemsHasRest &items_has_rest
1264 : = static_cast<HIR::TupleStructItemsHasRest &> (elems);
1265 :
1266 36 : size_t num_patterns = items_has_rest.get_lower_patterns ().size ()
1267 36 : + items_has_rest.get_upper_patterns ().size ();
1268 :
1269 36 : rust_assert (num_patterns <= variant->num_fields ());
1270 :
1271 36 : size_t i = 0;
1272 65 : for (auto &pattern_member : items_has_rest.get_lower_patterns ())
1273 : {
1274 29 : fields.push_back (lower_pattern (
1275 29 : ctx, *pattern_member,
1276 29 : variant->get_fields ().at (i++)->get_field_type ()));
1277 : }
1278 100 : while (i < variant->num_fields ()
1279 100 : - items_has_rest.get_upper_patterns ().size ())
1280 : {
1281 64 : fields.push_back (
1282 64 : DeconstructedPat::make_wildcard (pattern.get_locus ()));
1283 64 : i++;
1284 : }
1285 50 : for (auto &pattern_member : items_has_rest.get_upper_patterns ())
1286 : {
1287 14 : fields.push_back (lower_pattern (
1288 14 : ctx, *pattern_member,
1289 14 : variant->get_fields ().at (i++)->get_field_type ()));
1290 : }
1291 36 : return DeconstructedPat (ctor, arity, fields, pattern.get_locus ());
1292 : }
1293 0 : break;
1294 0 : default:
1295 0 : {
1296 0 : rust_unreachable ();
1297 : }
1298 : }
1299 856 : }
1300 :
1301 : static DeconstructedPat
1302 93 : lower_struct_pattern (Resolver::TypeCheckContext *ctx,
1303 : HIR::StructPattern &pattern, TyTy::VariantDef *variant,
1304 : Constructor ctor)
1305 : {
1306 93 : int arity = variant->get_fields ().size ();
1307 :
1308 : // Initialize all field patterns to wildcard.
1309 93 : std::vector<DeconstructedPat> fields
1310 186 : = std::vector<DeconstructedPat> (arity, DeconstructedPat::make_wildcard (
1311 93 : pattern.get_locus ()));
1312 :
1313 93 : std::map<std::string, int> field_map;
1314 248 : for (int i = 0; i < arity; i++)
1315 : {
1316 155 : auto &f = variant->get_fields ().at (i);
1317 155 : field_map[f->get_name ()] = i;
1318 : }
1319 :
1320 : // Fill in the fields with the present patterns.
1321 93 : HIR::StructPatternElements elems = pattern.get_struct_pattern_elems ();
1322 245 : for (auto &elem : elems.get_struct_pattern_fields ())
1323 : {
1324 152 : switch (elem->get_item_type ())
1325 : {
1326 79 : case HIR::StructPatternField::ItemType::IDENT:
1327 79 : {
1328 79 : HIR::StructPatternFieldIdent *ident
1329 79 : = static_cast<HIR::StructPatternFieldIdent *> (elem.get ());
1330 79 : int field_idx
1331 79 : = field_map.at (ident->get_identifier ().as_string ());
1332 79 : fields.at (field_idx)
1333 79 : = DeconstructedPat::make_wildcard (pattern.get_locus ());
1334 : }
1335 79 : break;
1336 55 : case HIR::StructPatternField::ItemType::IDENT_PAT:
1337 55 : {
1338 55 : HIR::StructPatternFieldIdentPat *ident_pat
1339 55 : = static_cast<HIR::StructPatternFieldIdentPat *> (elem.get ());
1340 55 : int field_idx
1341 55 : = field_map.at (ident_pat->get_identifier ().as_string ());
1342 55 : fields.at (field_idx) = lower_pattern (
1343 : ctx, ident_pat->get_pattern (),
1344 110 : variant->get_fields ().at (field_idx)->get_field_type ());
1345 : }
1346 55 : break;
1347 18 : case HIR::StructPatternField::ItemType::TUPLE_PAT:
1348 18 : {
1349 18 : HIR::StructPatternFieldTuplePat *tuple_pat
1350 18 : = static_cast<HIR::StructPatternFieldTuplePat *> (elem.get ());
1351 18 : int field_idx = tuple_pat->get_index ();
1352 18 : fields.at (field_idx) = lower_pattern (
1353 : ctx, tuple_pat->get_tuple_pattern (),
1354 36 : variant->get_fields ().at (field_idx)->get_field_type ());
1355 : }
1356 18 : break;
1357 0 : default:
1358 0 : {
1359 0 : rust_unreachable ();
1360 : }
1361 : }
1362 : }
1363 :
1364 93 : return DeconstructedPat{ctor, arity, fields, pattern.get_locus ()};
1365 93 : };
1366 :
1367 : static DeconstructedPat
1368 3484 : lower_pattern (Resolver::TypeCheckContext *ctx, HIR::Pattern &pattern,
1369 : TyTy::BaseType *scrutinee_ty)
1370 : {
1371 3484 : HIR::Pattern::PatternType pat_type = pattern.get_pattern_type ();
1372 3484 : switch (pat_type)
1373 : {
1374 1115 : case HIR::Pattern::PatternType::WILDCARD:
1375 1115 : case HIR::Pattern::PatternType::IDENTIFIER:
1376 1115 : {
1377 1115 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1378 : }
1379 784 : break;
1380 784 : case HIR::Pattern::PatternType::PATH:
1381 784 : {
1382 : // TODO: support constants, associated constants, enum variants and
1383 : // structs
1384 : // https://doc.rust-lang.org/reference/patterns.html#path-patterns
1385 : // unimplemented. Treat this pattern as wildcard for now.
1386 784 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1387 : }
1388 31 : break;
1389 31 : case HIR::Pattern::PatternType::REFERENCE:
1390 31 : {
1391 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1392 31 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1393 : }
1394 949 : break;
1395 949 : case HIR::Pattern::PatternType::STRUCT:
1396 949 : case HIR::Pattern::PatternType::TUPLE_STRUCT:
1397 949 : {
1398 949 : HirId path_id = UNKNOWN_HIRID;
1399 949 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1400 : {
1401 93 : HIR::StructPattern &struct_pattern
1402 : = static_cast<HIR::StructPattern &> (pattern);
1403 93 : path_id = struct_pattern.get_path ().get_mappings ().get_hirid ();
1404 : }
1405 : else
1406 : {
1407 856 : HIR::TupleStructPattern &tuple_pattern
1408 : = static_cast<HIR::TupleStructPattern &> (pattern);
1409 856 : path_id = tuple_pattern.get_path ().get_mappings ().get_hirid ();
1410 : }
1411 :
1412 949 : rust_assert (scrutinee_ty->get_kind () == TyTy::TypeKind::ADT);
1413 949 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (scrutinee_ty);
1414 :
1415 949 : Constructor ctor = Constructor::make_struct ();
1416 949 : TyTy::VariantDef *variant;
1417 949 : if (adt->is_struct_struct () || adt->is_tuple_struct ())
1418 84 : variant = adt->get_variants ().at (0);
1419 865 : else if (adt->is_enum ())
1420 : {
1421 865 : HirId variant_id = UNKNOWN_HIRID;
1422 865 : bool ok = ctx->lookup_variant_definition (path_id, &variant_id);
1423 865 : rust_assert (ok);
1424 :
1425 865 : int variant_idx;
1426 865 : ok = adt->lookup_variant_by_id (variant_id, &variant, &variant_idx);
1427 865 : rust_assert (ok);
1428 :
1429 865 : ctor = Constructor::make_variant (variant_idx);
1430 : }
1431 : else
1432 : {
1433 0 : rust_unreachable ();
1434 : }
1435 949 : rust_assert (variant->get_variant_type ()
1436 : == TyTy::VariantDef::VariantType::TUPLE
1437 : || variant->get_variant_type ()
1438 : == TyTy::VariantDef::VariantType::STRUCT);
1439 :
1440 949 : if (pat_type == HIR::Pattern::PatternType::STRUCT)
1441 : {
1442 93 : HIR::StructPattern &struct_pattern
1443 : = static_cast<HIR::StructPattern &> (pattern);
1444 93 : return lower_struct_pattern (ctx, struct_pattern, variant, ctor);
1445 : }
1446 : else
1447 : {
1448 856 : HIR::TupleStructPattern &tuple_pattern
1449 : = static_cast<HIR::TupleStructPattern &> (pattern);
1450 856 : return lower_tuple_pattern (ctx, tuple_pattern, variant, ctor);
1451 : }
1452 : }
1453 133 : break;
1454 133 : case HIR::Pattern::PatternType::TUPLE:
1455 133 : {
1456 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1457 133 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1458 : }
1459 75 : break;
1460 75 : case HIR::Pattern::PatternType::SLICE:
1461 75 : {
1462 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1463 75 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1464 : }
1465 145 : break;
1466 145 : case HIR::Pattern::PatternType::ALT:
1467 145 : {
1468 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1469 145 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1470 : }
1471 208 : break;
1472 208 : case HIR::Pattern::PatternType::LITERAL:
1473 208 : {
1474 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1475 208 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1476 : }
1477 44 : break;
1478 44 : case HIR::Pattern::PatternType::RANGE:
1479 44 : {
1480 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1481 44 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1482 : }
1483 0 : break;
1484 0 : case HIR::Pattern::PatternType::GROUPED:
1485 0 : {
1486 : // TODO: unimplemented. Treat this pattern as wildcard for now.
1487 0 : return DeconstructedPat::make_wildcard (pattern.get_locus ());
1488 : }
1489 0 : break;
1490 0 : default:
1491 0 : {
1492 0 : rust_unreachable ();
1493 : }
1494 : }
1495 : }
1496 :
1497 : static MatchArm
1498 2560 : lower_arm (Resolver::TypeCheckContext *ctx, HIR::MatchCase &arm,
1499 : TyTy::BaseType *scrutinee_ty)
1500 : {
1501 2560 : rust_assert (arm.get_arm ().get_pattern () != nullptr);
1502 :
1503 2560 : DeconstructedPat pat
1504 2560 : = lower_pattern (ctx, *arm.get_arm ().get_pattern (), scrutinee_ty);
1505 2560 : return MatchArm (pat, arm.get_arm ().has_match_arm_guard ());
1506 2560 : }
1507 :
1508 : std::pair<std::set<Constructor>, std::set<Constructor>>
1509 1996 : split_constructors (std::vector<Constructor> &ctors, PlaceInfo &place_info)
1510 : {
1511 1996 : bool all_wildcard = true;
1512 6411 : for (auto &ctor : ctors)
1513 : {
1514 4415 : if (!ctor.is_wildcard ())
1515 951 : all_wildcard = false;
1516 : }
1517 :
1518 : // first pass for the case that all patterns are wildcard
1519 1996 : if (all_wildcard)
1520 2590 : return std::make_pair (std::set<Constructor> (
1521 2590 : {Constructor::make_wildcard ()}),
1522 3885 : std::set<Constructor> ());
1523 :
1524 : // TODO: only support enums and structs for now.
1525 701 : TyTy::BaseType *ty = place_info.get_type ();
1526 701 : rust_assert (ty->get_kind () == TyTy::TypeKind::ADT);
1527 701 : TyTy::ADTType *adt = static_cast<TyTy::ADTType *> (ty);
1528 701 : rust_assert (adt->is_enum () || adt->is_struct_struct ()
1529 : || adt->is_tuple_struct ());
1530 :
1531 701 : std::set<Constructor> universe;
1532 701 : if (adt->is_enum ())
1533 : {
1534 1998 : for (size_t i = 0; i < adt->get_variants ().size (); i++)
1535 1352 : universe.insert (Constructor::make_variant (i));
1536 : }
1537 55 : else if (adt->is_struct_struct () || adt->is_tuple_struct ())
1538 : {
1539 55 : universe.insert (Constructor::make_struct ());
1540 : }
1541 :
1542 701 : std::set<Constructor> present;
1543 1572 : for (auto &ctor : ctors)
1544 : {
1545 1485 : if (ctor.is_wildcard ())
1546 1228 : return std::make_pair (universe, std::set<Constructor> ());
1547 : else
1548 871 : present.insert (ctor);
1549 : }
1550 :
1551 87 : std::set<Constructor> missing;
1552 87 : std::set_difference (universe.begin (), universe.end (), present.begin (),
1553 : present.end (), std::inserter (missing, missing.end ()));
1554 174 : return std::make_pair (universe, missing);
1555 788 : }
1556 :
1557 : // The core of the algorithm. It computes the usefulness and exhaustiveness of a
1558 : // given matrix recursively.
1559 : // TODO: calculate usefulness
1560 : static WitnessMatrix
1561 3817 : compute_exhaustiveness_and_usefulness (Resolver::TypeCheckContext *ctx,
1562 : Matrix &matrix)
1563 : {
1564 3817 : rust_debug ("call compute_exhaustiveness_and_usefulness");
1565 3817 : rust_debug ("matrix: %s", matrix.to_string ().c_str ());
1566 :
1567 3817 : if (matrix.get_rows ().empty ())
1568 : {
1569 : // no rows left. This means a non-exhaustive pattern.
1570 6 : rust_debug ("non-exhaustive subpattern found");
1571 6 : return WitnessMatrix::make_unit ();
1572 : }
1573 :
1574 : // Base case: there are no columns in matrix.
1575 3811 : if (matrix.get_place_infos ().empty ())
1576 1815 : return WitnessMatrix::make_empty ();
1577 :
1578 1996 : std::vector<Constructor> heads;
1579 6411 : for (auto head : matrix.heads ())
1580 10826 : heads.push_back (head.ctor ());
1581 :
1582 : // TODO: not sure missing ctors need to be calculated
1583 1996 : auto ctors_and_missings
1584 1996 : = split_constructors (heads, matrix.get_place_infos ().at (0));
1585 1996 : std::set<Constructor> ctors = ctors_and_missings.first;
1586 1996 : std::set<Constructor> missings = ctors_and_missings.second;
1587 :
1588 1996 : WitnessMatrix ret = WitnessMatrix::make_empty ();
1589 4698 : for (auto &ctor : ctors)
1590 : {
1591 2702 : rust_debug ("specialize with %s", ctor.to_string ().c_str ());
1592 : // TODO: Instead of creating new matrix, we can change the original matrix
1593 : // and use it for sub-pattern matching. It will significantly reduce
1594 : // memory usage.
1595 2702 : Matrix spec_matrix = matrix.specialize (ctor);
1596 :
1597 2702 : WitnessMatrix witness
1598 2702 : = compute_exhaustiveness_and_usefulness (ctx, spec_matrix);
1599 :
1600 2702 : TyTy::BaseType *ty = matrix.get_place_infos ().at (0).get_type ();
1601 2702 : witness.apply_constructor (ctor, missings, ty);
1602 2702 : ret.extend (witness);
1603 5404 : }
1604 :
1605 1996 : return ret;
1606 1996 : }
1607 :
1608 : static void
1609 1115 : emit_exhaustiveness_error (Resolver::TypeCheckContext *ctx,
1610 : HIR::MatchExpr &expr, WitnessMatrix &witness)
1611 : {
1612 1115 : TyTy::BaseType *scrutinee_ty;
1613 1115 : bool ok
1614 1115 : = ctx->lookup_type (expr.get_scrutinee_expr ().get_mappings ().get_hirid (),
1615 : &scrutinee_ty);
1616 1115 : rust_assert (ok);
1617 :
1618 1115 : if (!witness.empty ())
1619 : {
1620 4 : std::stringstream buf;
1621 14 : for (size_t i = 0; i < witness.get_stacks ().size (); i++)
1622 : {
1623 6 : auto &stack = witness.get_stacks ().at (i);
1624 6 : WitnessPat w = WitnessPat::make_wildcard (scrutinee_ty);
1625 6 : if (!stack.empty ())
1626 6 : w = stack.at (0);
1627 :
1628 6 : rust_debug ("Witness[%d]: %s", (int) i, w.to_string ().c_str ());
1629 12 : buf << "'" << w.to_string () << "'";
1630 6 : if (i != witness.get_stacks ().size () - 1)
1631 2 : buf << " and ";
1632 6 : }
1633 4 : rust_error_at (expr.get_scrutinee_expr ().get_locus (),
1634 : "non-exhaustive patterns: %s not covered",
1635 4 : buf.str ().c_str ());
1636 4 : }
1637 : else
1638 : {
1639 1111 : rust_debug ("no witness found");
1640 : }
1641 1115 : }
1642 :
1643 : // Entry point for computing match usefulness and check exhaustiveness
1644 : void
1645 1120 : check_match_usefulness (Resolver::TypeCheckContext *ctx,
1646 : TyTy::BaseType *scrutinee_ty, HIR::MatchExpr &expr)
1647 : {
1648 1120 : if (!expr.has_match_arms ())
1649 5 : return;
1650 :
1651 : // Lower the arms to a more convenient representation.
1652 1115 : std::vector<MatrixRow> rows;
1653 3675 : for (auto &arm : expr.get_match_cases ())
1654 : {
1655 2560 : PatStack pats;
1656 2560 : MatchArm lowered = lower_arm (ctx, arm, scrutinee_ty);
1657 2560 : PatOrWild pat = PatOrWild::make_pattern (lowered.get_pat ());
1658 2560 : pats.push (pat);
1659 2560 : rows.emplace_back (pats, lowered.has_guard ());
1660 2560 : }
1661 :
1662 1115 : std::vector<PlaceInfo> place_infos = {{PlaceInfo (scrutinee_ty)}};
1663 2230 : Matrix matrix{rows, place_infos};
1664 :
1665 1115 : WitnessMatrix witness = compute_exhaustiveness_and_usefulness (ctx, matrix);
1666 :
1667 1115 : emit_exhaustiveness_error (ctx, expr, witness);
1668 2230 : }
1669 :
1670 : } // namespace Analysis
1671 : } // namespace Rust
|
