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