src/librustc_typeck/check/_match.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use middle::def;
  12 use middle::infer;
  13 use middle::pat_util::{PatIdMap, pat_id_map, pat_is_binding, pat_is_const};
  14 use middle::subst::{Substs};
  15 use middle::ty::{mod, Ty};
  16 use check::{check_expr, check_expr_has_type, check_expr_with_expectation};
  17 use check::{check_expr_coercable_to_type, demand, FnCtxt, Expectation};
  18 use check::{instantiate_path, structurally_resolved_type, valid_range_bounds};
  19 use require_same_types;
  20 use util::nodemap::FnvHashMap;
  21 use util::ppaux::Repr;
  22
  23 use std::cmp;
  24 use std::collections::hash_map::Entry::{Occupied, Vacant};
  25 use syntax::ast;
  26 use syntax::ast_util;
  27 use syntax::codemap::{Span, Spanned};
  28 use syntax::parse::token;
  29 use syntax::print::pprust;
  30 use syntax::ptr::P;
  31
  32 pub fn check_pat<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>,
  33                            pat: &ast::Pat, expected: Ty<'tcx>) {
  34     let fcx = pcx.fcx;
  35     let tcx = pcx.fcx.ccx.tcx;
  36
  37     debug!("check_pat(pat={},expected={})",
  38            pat.repr(tcx),
  39            expected.repr(tcx));
  40
  41     match pat.node {
  42         ast::PatWild(_) => {
  43             fcx.write_ty(pat.id, expected);
  44         }
  45         ast::PatLit(ref lt) => {
  46             check_expr(fcx, &**lt);
  47             let expr_ty = fcx.expr_ty(&**lt);
  48             fcx.write_ty(pat.id, expr_ty);
  49             demand::suptype(fcx, pat.span, expected, expr_ty);
  50         }
  51         ast::PatRange(ref begin, ref end) => {
  52             check_expr(fcx, &**begin);
  53             check_expr(fcx, &**end);
  54
  55             let lhs_ty = fcx.expr_ty(&**begin);
  56             let rhs_ty = fcx.expr_ty(&**end);
  57             if require_same_types(
  58                 tcx, Some(fcx.infcx()), false, pat.span, lhs_ty, rhs_ty,
  59                 || "mismatched types in range".to_string())
  60                 && (ty::type_is_numeric(lhs_ty) || ty::type_is_char(rhs_ty)) {
  61                 match valid_range_bounds(fcx.ccx, &**begin, &**end) {
  62                     Some(false) => {
  63                         span_err!(tcx.sess, begin.span, E0030,
  64                             "lower range bound must be less than upper");
  65                     },
  66                     None => {
  67                         span_err!(tcx.sess, begin.span, E0031,
  68                             "mismatched types in range");
  69                     },
  70                     Some(true) => {}
  71                 }
  72             } else {
  73                 span_err!(tcx.sess, begin.span, E0029,
  74                     "only char and numeric types are allowed in range");
  75             }
  76
  77             fcx.write_ty(pat.id, lhs_ty);
  78             demand::eqtype(fcx, pat.span, expected, lhs_ty);
  79         }
  80         ast::PatEnum(..) | ast::PatIdent(..) if pat_is_const(&tcx.def_map, pat) => {
  81             let const_did = tcx.def_map.borrow()[pat.id].clone().def_id();
  82             let const_scheme = ty::lookup_item_type(tcx, const_did);
  83             fcx.write_ty(pat.id, const_scheme.ty);
  84             demand::suptype(fcx, pat.span, expected, const_scheme.ty);
  85         }
  86         ast::PatIdent(bm, ref path, ref sub) if pat_is_binding(&tcx.def_map, pat) => {
  87             let typ = fcx.local_ty(pat.span, pat.id);
  88             match bm {
  89                 ast::BindByRef(mutbl) => {
  90                     // if the binding is like
  91                     //    ref x | ref const x | ref mut x
  92                     // then the type of x is &M T where M is the mutability
  93                     // and T is the expected type
  94                     let region_var = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
  95                     let mt = ty::mt { ty: expected, mutbl: mutbl };
  96                     let region_ty = ty::mk_rptr(tcx, tcx.mk_region(region_var), mt);
  97                     demand::eqtype(fcx, pat.span, region_ty, typ);
  98                 }
  99                 // otherwise the type of x is the expected type T
 100                 ast::BindByValue(_) => {
 101                     demand::eqtype(fcx, pat.span, expected, typ);
 102                 }
 103             }
 104             fcx.write_ty(pat.id, typ);
 105
 106             let canon_id = pcx.map[path.node];
 107             if canon_id != pat.id {
 108                 let ct = fcx.local_ty(pat.span, canon_id);
 109                 demand::eqtype(fcx, pat.span, ct, typ);
 110             }
 111
 112             if let Some(ref p) = *sub {
 113                 check_pat(pcx, &**p, expected);
 114             }
 115         }
 116         ast::PatIdent(_, ref path, _) => {
 117             let path = ast_util::ident_to_path(path.span, path.node);
 118             check_pat_enum(pcx, pat, &path, &Some(vec![]), expected);
 119         }
 120         ast::PatEnum(ref path, ref subpats) => {
 121             check_pat_enum(pcx, pat, path, subpats, expected);
 122         }
 123         ast::PatStruct(ref path, ref fields, etc) => {
 124             check_pat_struct(pcx, pat, path, fields.as_slice(), etc, expected);
 125         }
 126         ast::PatTup(ref elements) => {
 127             let element_tys: Vec<_> = range(0, elements.len()).map(|_| fcx.infcx()
 128                 .next_ty_var()).collect();
 129             let pat_ty = ty::mk_tup(tcx, element_tys.clone());
 130             fcx.write_ty(pat.id, pat_ty);
 131             demand::eqtype(fcx, pat.span, expected, pat_ty);
 132             for (element_pat, element_ty) in elements.iter().zip(element_tys.into_iter()) {
 133                 check_pat(pcx, &**element_pat, element_ty);
 134             }
 135         }
 136         ast::PatBox(ref inner) => {
 137             let inner_ty = fcx.infcx().next_ty_var();
 138             let uniq_ty = ty::mk_uniq(tcx, inner_ty);
 139
 140             if check_dereferencable(pcx, pat.span, expected, &**inner) {
 141                 demand::suptype(fcx, pat.span, expected, uniq_ty);
 142                 fcx.write_ty(pat.id, uniq_ty);
 143                 check_pat(pcx, &**inner, inner_ty);
 144             } else {
 145                 fcx.write_error(pat.id);
 146                 check_pat(pcx, &**inner, tcx.types.err);
 147             }
 148         }
 149         ast::PatRegion(ref inner) => {
 150             let inner_ty = fcx.infcx().next_ty_var();
 151
 152             let mutbl =
 153                 ty::deref(fcx.infcx().shallow_resolve(expected), true)
 154                 .map_or(ast::MutImmutable, |mt| mt.mutbl);
 155
 156             let mt = ty::mt { ty: inner_ty, mutbl: mutbl };
 157             let region = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
 158             let rptr_ty = ty::mk_rptr(tcx, tcx.mk_region(region), mt);
 159
 160             if check_dereferencable(pcx, pat.span, expected, &**inner) {
 161                 demand::suptype(fcx, pat.span, expected, rptr_ty);
 162                 fcx.write_ty(pat.id, rptr_ty);
 163                 check_pat(pcx, &**inner, inner_ty);
 164             } else {
 165                 fcx.write_error(pat.id);
 166                 check_pat(pcx, &**inner, tcx.types.err);
 167             }
 168         }
 169         ast::PatVec(ref before, ref slice, ref after) => {
 170             let expected_ty = structurally_resolved_type(fcx, pat.span, expected);
 171             let inner_ty = fcx.infcx().next_ty_var();
 172             let pat_ty = match expected_ty.sty {
 173                 ty::ty_vec(_, Some(size)) => ty::mk_vec(tcx, inner_ty, Some({
 174                     let min_len = before.len() + after.len();
 175                     match *slice {
 176                         Some(_) => cmp::max(min_len, size),
 177                         None => min_len
 178                     }
 179                 })),
 180                 _ => {
 181                     let region = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
 182                     ty::mk_slice(tcx, tcx.mk_region(region), ty::mt {
 183                         ty: inner_ty,
 184                         mutbl: ty::deref(expected_ty, true)
 185                             .map_or(ast::MutImmutable, |mt| mt.mutbl)
 186                     })
 187                 }
 188             };
 189
 190             fcx.write_ty(pat.id, pat_ty);
 191             demand::suptype(fcx, pat.span, expected, pat_ty);
 192
 193             for elt in before.iter() {
 194                 check_pat(pcx, &**elt, inner_ty);
 195             }
 196             if let Some(ref slice) = *slice {
 197                 let region = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
 198                 let mutbl = ty::deref(expected_ty, true)
 199                     .map_or(ast::MutImmutable, |mt| mt.mutbl);
 200
 201                 let slice_ty = ty::mk_slice(tcx, tcx.mk_region(region), ty::mt {
 202                     ty: inner_ty,
 203                     mutbl: mutbl
 204                 });
 205                 check_pat(pcx, &**slice, slice_ty);
 206             }
 207             for elt in after.iter() {
 208                 check_pat(pcx, &**elt, inner_ty);
 209             }
 210         }
 211         ast::PatMac(_) => tcx.sess.bug("unexpanded macro")
 212     }
 213 }
 214
 215 pub fn check_dereferencable<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>,
 216                                       span: Span, expected: Ty<'tcx>,
 217                                       inner: &ast::Pat) -> bool {
 218     let fcx = pcx.fcx;
 219     let tcx = pcx.fcx.ccx.tcx;
 220     if pat_is_binding(&tcx.def_map, inner) {
 221         let expected = fcx.infcx().shallow_resolve(expected);
 222         ty::deref(expected, true).map_or(true, |mt| match mt.ty.sty {
 223             ty::ty_trait(_) => {
 224                 // This is "x = SomeTrait" being reduced from
 225                 // "let &x = &SomeTrait" or "let box x = Box<SomeTrait>", an error.
 226                 span_err!(tcx.sess, span, E0033,
 227                           "type `{}` cannot be dereferenced",
 228                           fcx.infcx().ty_to_string(expected));
 229                 false
 230             }
 231             _ => true
 232         })
 233     } else {
 234         true
 235     }
 236 }
 237
 238 pub fn check_match<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 239                              expr: &ast::Expr,
 240                              discrim: &ast::Expr,
 241                              arms: &[ast::Arm],
 242                              expected: Expectation<'tcx>,
 243                              match_src: ast::MatchSource) {
 244     let tcx = fcx.ccx.tcx;
 245
 246     let discrim_ty = fcx.infcx().next_ty_var();
 247     check_expr_has_type(fcx, discrim, discrim_ty);
 248
 249     // Typecheck the patterns first, so that we get types for all the
 250     // bindings.
 251     for arm in arms.iter() {
 252         let mut pcx = pat_ctxt {
 253             fcx: fcx,
 254             map: pat_id_map(&tcx.def_map, &*arm.pats[0]),
 255         };
 256         for p in arm.pats.iter() {
 257             check_pat(&mut pcx, &**p, discrim_ty);
 258         }
 259     }
 260
 261     // Now typecheck the blocks.
 262     //
 263     // The result of the match is the common supertype of all the
 264     // arms. Start out the value as bottom, since it's the, well,
 265     // bottom the type lattice, and we'll be moving up the lattice as
 266     // we process each arm. (Note that any match with 0 arms is matching
 267     // on any empty type and is therefore unreachable; should the flow
 268     // of execution reach it, we will panic, so bottom is an appropriate
 269     // type in that case)
 270     let expected = expected.adjust_for_branches(fcx);
 271     let result_ty = arms.iter().fold(fcx.infcx().next_diverging_ty_var(), |result_ty, arm| {
 272         let bty = match expected {
 273             // We don't coerce to `()` so that if the match expression is a
 274             // statement it's branches can have any consistent type. That allows
 275             // us to give better error messages (pointing to a usually better
 276             // arm for inconsistent arms or to the whole match when a `()` type
 277             // is required).
 278             Expectation::ExpectHasType(ety) if ety != ty::mk_nil(fcx.tcx()) => {
 279                 check_expr_coercable_to_type(fcx, &*arm.body, ety);
 280                 ety
 281             }
 282             _ => {
 283                 check_expr_with_expectation(fcx, &*arm.body, expected);
 284                 fcx.node_ty(arm.body.id)
 285             }
 286         };
 287
 288         if let Some(ref e) = arm.guard {
 289             check_expr_has_type(fcx, &**e, tcx.types.bool);
 290         }
 291
 292         if ty::type_is_error(result_ty) || ty::type_is_error(bty) {
 293             tcx.types.err
 294         } else {
 295             let (origin, expected, found) = match match_src {
 296                 /* if-let construct without an else block */
 297                 ast::MatchSource::IfLetDesugar { contains_else_clause }
 298                 if !contains_else_clause => (
 299                     infer::IfExpressionWithNoElse(expr.span),
 300                     bty,
 301                     result_ty,
 302                 ),
 303                 _ => (
 304                     infer::MatchExpressionArm(expr.span, arm.body.span),
 305                     result_ty,
 306                     bty,
 307                 ),
 308             };
 309
 310             infer::common_supertype(
 311                 fcx.infcx(),
 312                 origin,
 313                 true,
 314                 expected,
 315                 found,
 316             )
 317         }
 318     });
 319
 320     fcx.write_ty(expr.id, result_ty);
 321 }
 322
 323 pub struct pat_ctxt<'a, 'tcx: 'a> {
 324     pub fcx: &'a FnCtxt<'a, 'tcx>,
 325     pub map: PatIdMap,
 326 }
 327
 328 pub fn check_pat_struct<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>, pat: &ast::Pat,
 329                                   path: &ast::Path, fields: &[Spanned<ast::FieldPat>],
 330                                   etc: bool, expected: Ty<'tcx>) {
 331     let fcx = pcx.fcx;
 332     let tcx = pcx.fcx.ccx.tcx;
 333
 334     let def = tcx.def_map.borrow()[pat.id].clone();
 335     let (enum_def_id, variant_def_id) = match def {
 336         def::DefTrait(_) => {
 337             let name = pprust::path_to_string(path);
 338             span_err!(tcx.sess, pat.span, E0168,
 339                 "use of trait `{}` in a struct pattern", name);
 340             fcx.write_error(pat.id);
 341
 342             for field in fields.iter() {
 343                 check_pat(pcx, &*field.node.pat, tcx.types.err);
 344             }
 345             return;
 346         },
 347         _ => {
 348             let def_type = ty::lookup_item_type(tcx, def.def_id());
 349             match def_type.ty.sty {
 350                 ty::ty_struct(struct_def_id, _) =>
 351                     (struct_def_id, struct_def_id),
 352                 ty::ty_enum(enum_def_id, _)
 353                     if def == def::DefVariant(enum_def_id, def.def_id(), true) =>
 354                     (enum_def_id, def.def_id()),
 355                 _ => {
 356                     let name = pprust::path_to_string(path);
 357                     span_err!(tcx.sess, pat.span, E0163,
 358                         "`{}` does not name a struct or a struct variant", name);
 359                     fcx.write_error(pat.id);
 360
 361                     for field in fields.iter() {
 362                         check_pat(pcx, &*field.node.pat, tcx.types.err);
 363                     }
 364                     return;
 365                 }
 366             }
 367         }
 368     };
 369
 370     instantiate_path(pcx.fcx, path, ty::lookup_item_type(tcx, enum_def_id),
 371                      def, pat.span, pat.id);
 372
 373     let pat_ty = fcx.node_ty(pat.id);
 374     demand::eqtype(fcx, pat.span, expected, pat_ty);
 375
 376     let item_substs = fcx
 377         .item_substs()
 378         .get(&pat.id)
 379         .map(|substs| substs.substs.clone())
 380         .unwrap_or_else(|| Substs::empty());
 381
 382     let struct_fields = ty::struct_fields(tcx, variant_def_id, &item_substs);
 383     check_struct_pat_fields(pcx, pat.span, fields, struct_fields.as_slice(),
 384                             variant_def_id, etc);
 385 }
 386
 387 pub fn check_pat_enum<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>, pat: &ast::Pat,
 388                                 path: &ast::Path, subpats: &Option<Vec<P<ast::Pat>>>,
 389                                 expected: Ty<'tcx>) {
 390
 391     // Typecheck the path.
 392     let fcx = pcx.fcx;
 393     let tcx = pcx.fcx.ccx.tcx;
 394
 395     let def = tcx.def_map.borrow()[pat.id].clone();
 396     let enum_def = def.variant_def_ids()
 397         .map_or_else(|| def.def_id(), |(enum_def, _)| enum_def);
 398
 399     let ctor_scheme = ty::lookup_item_type(tcx, enum_def);
 400     let path_scheme = if ty::is_fn_ty(ctor_scheme.ty) {
 401         ty::TypeScheme {
 402             ty: ty::ty_fn_ret(ctor_scheme.ty).unwrap(),
 403             ..ctor_scheme
 404         }
 405     } else {
 406         ctor_scheme
 407     };
 408     instantiate_path(pcx.fcx, path, path_scheme, def, pat.span, pat.id);
 409
 410     let pat_ty = fcx.node_ty(pat.id);
 411     demand::eqtype(fcx, pat.span, expected, pat_ty);
 412
 413     let real_path_ty = fcx.node_ty(pat.id);
 414     let (arg_tys, kind_name): (Vec<_>, &'static str) = match real_path_ty.sty {
 415         ty::ty_enum(enum_def_id, expected_substs)
 416             if def == def::DefVariant(enum_def_id, def.def_id(), false) =>
 417         {
 418             let variant = ty::enum_variant_with_id(tcx, enum_def_id, def.def_id());
 419             (variant.args.iter()
 420                          .map(|t| fcx.instantiate_type_scheme(pat.span, expected_substs, t))
 421                          .collect(),
 422              "variant")
 423         }
 424         ty::ty_struct(struct_def_id, expected_substs) => {
 425             let struct_fields = ty::struct_fields(tcx, struct_def_id, expected_substs);
 426             (struct_fields.iter()
 427                           .map(|field| fcx.instantiate_type_scheme(pat.span,
 428                                                                    expected_substs,
 429                                                                    &field.mt.ty))
 430                           .collect(),
 431              "struct")
 432         }
 433         _ => {
 434             let name = pprust::path_to_string(path);
 435             span_err!(tcx.sess, pat.span, E0164,
 436                 "`{}` does not name a non-struct variant or a tuple struct", name);
 437             fcx.write_error(pat.id);
 438
 439             if let Some(ref subpats) = *subpats {
 440                 for pat in subpats.iter() {
 441                     check_pat(pcx, &**pat, tcx.types.err);
 442                 }
 443             }
 444             return;
 445         }
 446     };
 447
 448     if let Some(ref subpats) = *subpats {
 449         if subpats.len() == arg_tys.len() {
 450             for (subpat, arg_ty) in subpats.iter().zip(arg_tys.iter()) {
 451                 check_pat(pcx, &**subpat, *arg_ty);
 452             }
 453         } else if arg_tys.len() == 0 {
 454             span_err!(tcx.sess, pat.span, E0024,
 455                       "this pattern has {} field{}, but the corresponding {} has no fields",
 456                       subpats.len(), if subpats.len() == 1 {""} else {"s"}, kind_name);
 457
 458             for pat in subpats.iter() {
 459                 check_pat(pcx, &**pat, tcx.types.err);
 460             }
 461         } else {
 462             span_err!(tcx.sess, pat.span, E0023,
 463                       "this pattern has {} field{}, but the corresponding {} has {} field{}",
 464                       subpats.len(), if subpats.len() == 1 {""} else {"s"},
 465                       kind_name,
 466                       arg_tys.len(), if arg_tys.len() == 1 {""} else {"s"});
 467
 468             for pat in subpats.iter() {
 469                 check_pat(pcx, &**pat, tcx.types.err);
 470             }
 471         }
 472     }
 473 }
 474
 475 /// `path` is the AST path item naming the type of this struct.
 476 /// `fields` is the field patterns of the struct pattern.
 477 /// `struct_fields` describes the type of each field of the struct.
 478 /// `struct_id` is the ID of the struct.
 479 /// `etc` is true if the pattern said '...' and false otherwise.
 480 pub fn check_struct_pat_fields<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>,
 481                                          span: Span,
 482                                          fields: &[Spanned<ast::FieldPat>],
 483                                          struct_fields: &[ty::field<'tcx>],
 484                                          struct_id: ast::DefId,
 485                                          etc: bool) {
 486     let tcx = pcx.fcx.ccx.tcx;
 487
 488     // Index the struct fields' types.
 489     let field_type_map = struct_fields
 490         .iter()
 491         .map(|field| (field.name, field.mt.ty))
 492         .collect::<FnvHashMap<_, _>>();
 493
 494     // Keep track of which fields have already appeared in the pattern.
 495     let mut used_fields = FnvHashMap::new();
 496
 497     // Typecheck each field.
 498     for &Spanned { node: ref field, span } in fields.iter() {
 499         let field_type = match used_fields.entry(field.ident.name) {
 500             Occupied(occupied) => {
 501                 span_err!(tcx.sess, span, E0025,
 502                     "field `{}` bound multiple times in the pattern",
 503                     token::get_ident(field.ident));
 504                 span_note!(tcx.sess, *occupied.get(),
 505                     "field `{}` previously bound here",
 506                     token::get_ident(field.ident));
 507                 tcx.types.err
 508             }
 509             Vacant(vacant) => {
 510                 vacant.set(span);
 511                 field_type_map.get(&field.ident.name).cloned()
 512                     .unwrap_or_else(|| {
 513                         span_err!(tcx.sess, span, E0026,
 514                             "struct `{}` does not have a field named `{}`",
 515                             ty::item_path_str(tcx, struct_id),
 516                             token::get_ident(field.ident));
 517                         tcx.types.err
 518                     })
 519             }
 520         };
 521
 522         check_pat(pcx, &*field.pat, field_type);
 523     }
 524
 525     // Report an error if not all the fields were specified.
 526     if !etc {
 527         for field in struct_fields
 528             .iter()
 529             .filter(|field| !used_fields.contains_key(&field.name)) {
 530             span_err!(tcx.sess, span, E0027,
 531                 "pattern does not mention field `{}`",
 532                 token::get_name(field.name));
 533         }
 534     }
 535 }