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