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