LCOV - code coverage report
Current view: top level - gcc/rust/checks/errors - rust-hir-pattern-analysis.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 74.2 % 926 687
Test Date: 2026-11-14 16:39:50 Functions: 58.7 % 155 91
Legend: Lines:     hit not hit

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

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.