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::{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::{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_pty = ty::lookup_item_type(tcx, const_did);
  83             fcx.write_ty(pat.id, const_pty.ty);
  84             demand::suptype(fcx, pat.span, expected, const_pty.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, 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::from_fn(elements.len(), |_| fcx.infcx().next_ty_var());
 128             let pat_ty = ty::mk_tup(tcx, element_tys.clone());
 129             fcx.write_ty(pat.id, pat_ty);
 130             demand::eqtype(fcx, pat.span, expected, pat_ty);
 131             for (element_pat, element_ty) in elements.iter().zip(element_tys.into_iter()) {
 132                 check_pat(pcx, &**element_pat, element_ty);
 133             }
 134         }
 135         ast::PatBox(ref inner) => {
 136             let inner_ty = fcx.infcx().next_ty_var();
 137             let uniq_ty = ty::mk_uniq(tcx, inner_ty);
 138
 139             if check_dereferencable(pcx, pat.span, expected, &**inner) {
 140                 demand::suptype(fcx, pat.span, expected, uniq_ty);
 141                 fcx.write_ty(pat.id, uniq_ty);
 142                 check_pat(pcx, &**inner, inner_ty);
 143             } else {
 144                 fcx.write_error(pat.id);
 145                 check_pat(pcx, &**inner, ty::mk_err());
 146             }
 147         }
 148         ast::PatRegion(ref inner) => {
 149             let inner_ty = fcx.infcx().next_ty_var();
 150
 151             let mutbl =
 152                 ty::deref(fcx.infcx().shallow_resolve(expected), true)
 153                 .map_or(ast::MutImmutable, |mt| mt.mutbl);
 154
 155             let mt = ty::mt { ty: inner_ty, mutbl: mutbl };
 156             let region = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
 157             let rptr_ty = ty::mk_rptr(tcx, region, mt);
 158
 159             if check_dereferencable(pcx, pat.span, expected, &**inner) {
 160                 demand::suptype(fcx, pat.span, expected, rptr_ty);
 161                 fcx.write_ty(pat.id, rptr_ty);
 162                 check_pat(pcx, &**inner, inner_ty);
 163             } else {
 164                 fcx.write_error(pat.id);
 165                 check_pat(pcx, &**inner, ty::mk_err());
 166             }
 167         }
 168         ast::PatVec(ref before, ref slice, ref after) => {
 169             let expected_ty = structurally_resolved_type(fcx, pat.span, expected);
 170             let inner_ty = fcx.infcx().next_ty_var();
 171             let pat_ty = match expected_ty.sty {
 172                 ty::ty_vec(_, Some(size)) => ty::mk_vec(tcx, inner_ty, Some({
 173                     let min_len = before.len() + after.len();
 174                     match *slice {
 175                         Some(_) => cmp::max(min_len, size),
 176                         None => min_len
 177                     }
 178                 })),
 179                 _ => {
 180                     let region = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
 181                     ty::mk_slice(tcx, region, ty::mt {
 182                         ty: inner_ty,
 183                         mutbl: ty::deref(expected_ty, true)
 184                             .map_or(ast::MutImmutable, |mt| mt.mutbl)
 185                     })
 186                 }
 187             };
 188
 189             fcx.write_ty(pat.id, pat_ty);
 190             demand::suptype(fcx, pat.span, expected, pat_ty);
 191
 192             for elt in before.iter() {
 193                 check_pat(pcx, &**elt, inner_ty);
 194             }
 195             if let Some(ref slice) = *slice {
 196                 let region = fcx.infcx().next_region_var(infer::PatternRegion(pat.span));
 197                 let mutbl = ty::deref(expected_ty, true)
 198                     .map_or(ast::MutImmutable, |mt| mt.mutbl);
 199
 200                 let slice_ty = ty::mk_slice(tcx, region, ty::mt {
 201                     ty: inner_ty,
 202                     mutbl: mutbl
 203                 });
 204                 check_pat(pcx, &**slice, slice_ty);
 205             }
 206             for elt in after.iter() {
 207                 check_pat(pcx, &**elt, inner_ty);
 208             }
 209         }
 210         ast::PatMac(_) => tcx.sess.bug("unexpanded macro")
 211     }
 212 }
 213
 214 pub fn check_dereferencable<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>,
 215                                       span: Span, expected: Ty<'tcx>,
 216                                       inner: &ast::Pat) -> bool {
 217     let fcx = pcx.fcx;
 218     let tcx = pcx.fcx.ccx.tcx;
 219     if pat_is_binding(&tcx.def_map, inner) {
 220         let expected = fcx.infcx().shallow_resolve(expected);
 221         ty::deref(expected, true).map_or(true, |mt| match mt.ty.sty {
 222             ty::ty_trait(_) => {
 223                 // This is "x = SomeTrait" being reduced from
 224                 // "let &x = &SomeTrait" or "let box x = Box<SomeTrait>", an error.
 225                 span_err!(tcx.sess, span, E0033,
 226                           "type `{}` cannot be dereferenced",
 227                           fcx.infcx().ty_to_string(expected));
 228                 false
 229             }
 230             _ => true
 231         })
 232     } else {
 233         true
 234     }
 235 }
 236
 237 pub fn check_match<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 238                              expr: &ast::Expr,
 239                              discrim: &ast::Expr,
 240                              arms: &[ast::Arm],
 241                              expected: Expectation<'tcx>) {
 242     let tcx = fcx.ccx.tcx;
 243
 244     let discrim_ty = fcx.infcx().next_ty_var();
 245     check_expr_has_type(fcx, discrim, discrim_ty);
 246
 247     // Typecheck the patterns first, so that we get types for all the
 248     // bindings.
 249     for arm in arms.iter() {
 250         let mut pcx = pat_ctxt {
 251             fcx: fcx,
 252             map: pat_id_map(&tcx.def_map, &*arm.pats[0]),
 253         };
 254         for p in arm.pats.iter() {
 255             check_pat(&mut pcx, &**p, discrim_ty);
 256         }
 257     }
 258
 259     // Now typecheck the blocks.
 260     //
 261     // The result of the match is the common supertype of all the
 262     // arms. Start out the value as bottom, since it's the, well,
 263     // bottom the type lattice, and we'll be moving up the lattice as
 264     // we process each arm. (Note that any match with 0 arms is matching
 265     // on any empty type and is therefore unreachable; should the flow
 266     // of execution reach it, we will panic, so bottom is an appropriate
 267     // type in that case)
 268     let expected = expected.adjust_for_branches(fcx);
 269     let result_ty = arms.iter().fold(fcx.infcx().next_diverging_ty_var(), |result_ty, arm| {
 270         let bty = match expected {
 271             // We don't coerce to `()` so that if the match expression is a
 272             // statement it's branches can have any consistent type. That allows
 273             // us to give better error messages (pointing to a usually better
 274             // arm for inconsistent arms or to the whole match when a `()` type
 275             // is required).
 276             Expectation::ExpectHasType(ety) if ety != ty::mk_nil(fcx.tcx()) => {
 277                 check_expr_coercable_to_type(fcx, &*arm.body, ety);
 278                 ety
 279             }
 280             _ => {
 281                 check_expr_with_expectation(fcx, &*arm.body, expected);
 282                 fcx.node_ty(arm.body.id)
 283             }
 284         };
 285
 286         if let Some(ref e) = arm.guard {
 287             check_expr_has_type(fcx, &**e, ty::mk_bool());
 288         }
 289
 290         if ty::type_is_error(result_ty) || ty::type_is_error(bty) {
 291             ty::mk_err()
 292         } else {
 293             infer::common_supertype(
 294                 fcx.infcx(),
 295                 infer::MatchExpressionArm(expr.span, arm.body.span),
 296                 true, // result_ty is "expected" here
 297                 result_ty,
 298                 bty
 299             )
 300         }
 301     });
 302
 303     fcx.write_ty(expr.id, result_ty);
 304 }
 305
 306 pub struct pat_ctxt<'a, 'tcx: 'a> {
 307     pub fcx: &'a FnCtxt<'a, 'tcx>,
 308     pub map: PatIdMap,
 309 }
 310
 311 pub fn check_pat_struct<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>, pat: &ast::Pat,
 312                                   path: &ast::Path, fields: &[Spanned<ast::FieldPat>],
 313                                   etc: bool, expected: Ty<'tcx>) {
 314     let fcx = pcx.fcx;
 315     let tcx = pcx.fcx.ccx.tcx;
 316
 317     let def = tcx.def_map.borrow()[pat.id].clone();
 318     let (enum_def_id, variant_def_id) = match def {
 319         def::DefTrait(_) => {
 320             let name = pprust::path_to_string(path);
 321             span_err!(tcx.sess, pat.span, E0168,
 322                 "use of trait `{}` in a struct pattern", name);
 323             fcx.write_error(pat.id);
 324
 325             for field in fields.iter() {
 326                 check_pat(pcx, &*field.node.pat, ty::mk_err());
 327             }
 328             return;
 329         },
 330         _ => {
 331             let def_type = ty::lookup_item_type(tcx, def.def_id());
 332             match def_type.ty.sty {
 333                 ty::ty_struct(struct_def_id, _) =>
 334                     (struct_def_id, struct_def_id),
 335                 ty::ty_enum(enum_def_id, _)
 336                     if def == def::DefVariant(enum_def_id, def.def_id(), true) =>
 337                     (enum_def_id, def.def_id()),
 338                 _ => {
 339                     let name = pprust::path_to_string(path);
 340                     span_err!(tcx.sess, pat.span, E0163,
 341                         "`{}` does not name a struct or a struct variant", name);
 342                     fcx.write_error(pat.id);
 343
 344                     for field in fields.iter() {
 345                         check_pat(pcx, &*field.node.pat, ty::mk_err());
 346                     }
 347                     return;
 348                 }
 349             }
 350         }
 351     };
 352
 353     instantiate_path(pcx.fcx, path, ty::lookup_item_type(tcx, enum_def_id),
 354                      def, pat.span, pat.id);
 355
 356     let pat_ty = fcx.node_ty(pat.id);
 357     demand::eqtype(fcx, pat.span, expected, pat_ty);
 358
 359     let item_substs = fcx
 360         .item_substs()
 361         .get(&pat.id)
 362         .map(|substs| substs.substs.clone())
 363         .unwrap_or_else(|| Substs::empty());
 364
 365     let struct_fields = ty::struct_fields(tcx, variant_def_id, &item_substs);
 366     check_struct_pat_fields(pcx, pat.span, fields, struct_fields.as_slice(),
 367                             variant_def_id, etc);
 368 }
 369
 370 pub fn check_pat_enum<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>, pat: &ast::Pat,
 371                                 path: &ast::Path, subpats: &Option<Vec<P<ast::Pat>>>,
 372                                 expected: Ty<'tcx>) {
 373
 374     // Typecheck the path.
 375     let fcx = pcx.fcx;
 376     let tcx = pcx.fcx.ccx.tcx;
 377
 378     let def = tcx.def_map.borrow()[pat.id].clone();
 379     let enum_def = def.variant_def_ids()
 380         .map_or_else(|| def.def_id(), |(enum_def, _)| enum_def);
 381
 382     let ctor_pty = ty::lookup_item_type(tcx, enum_def);
 383     let path_ty = if ty::is_fn_ty(ctor_pty.ty) {
 384         ty::Polytype {
 385             ty: ty::ty_fn_ret(ctor_pty.ty).unwrap(),
 386             ..ctor_pty
 387         }
 388     } else {
 389         ctor_pty
 390     };
 391     instantiate_path(pcx.fcx, path, path_ty, def, pat.span, pat.id);
 392
 393     let pat_ty = fcx.node_ty(pat.id);
 394     demand::eqtype(fcx, pat.span, expected, pat_ty);
 395
 396     let real_path_ty = fcx.node_ty(pat.id);
 397     let (arg_tys, kind_name) = match real_path_ty.sty {
 398         ty::ty_enum(enum_def_id, ref expected_substs)
 399             if def == def::DefVariant(enum_def_id, def.def_id(), false) => {
 400             let variant = ty::enum_variant_with_id(tcx, enum_def_id, def.def_id());
 401             (variant.args.iter().map(|t| t.subst(tcx, expected_substs)).collect::<Vec<_>>(),
 402                 "variant")
 403         }
 404         ty::ty_struct(struct_def_id, ref expected_substs) => {
 405             let struct_fields = ty::struct_fields(tcx, struct_def_id, expected_substs);
 406             (struct_fields.iter().map(|field| field.mt.ty).collect::<Vec<_>>(),
 407                 "struct")
 408         }
 409         _ => {
 410             let name = pprust::path_to_string(path);
 411             span_err!(tcx.sess, pat.span, E0164,
 412                 "`{}` does not name a non-struct variant or a tuple struct", name);
 413             fcx.write_error(pat.id);
 414
 415             if let Some(ref subpats) = *subpats {
 416                 for pat in subpats.iter() {
 417                     check_pat(pcx, &**pat, ty::mk_err());
 418                 }
 419             }
 420             return;
 421         }
 422     };
 423
 424     if let Some(ref subpats) = *subpats {
 425         if subpats.len() == arg_tys.len() {
 426             for (subpat, arg_ty) in subpats.iter().zip(arg_tys.iter()) {
 427                 check_pat(pcx, &**subpat, *arg_ty);
 428             }
 429         } else if arg_tys.len() == 0 {
 430             span_err!(tcx.sess, pat.span, E0024,
 431                       "this pattern has {} field{}, but the corresponding {} has no fields",
 432                       subpats.len(), if subpats.len() == 1 {""} else {"s"}, kind_name);
 433
 434             for pat in subpats.iter() {
 435                 check_pat(pcx, &**pat, ty::mk_err());
 436             }
 437         } else {
 438             span_err!(tcx.sess, pat.span, E0023,
 439                       "this pattern has {} field{}, but the corresponding {} has {} field{}",
 440                       subpats.len(), if subpats.len() == 1 {""} else {"s"},
 441                       kind_name,
 442                       arg_tys.len(), if arg_tys.len() == 1 {""} else {"s"});
 443
 444             for pat in subpats.iter() {
 445                 check_pat(pcx, &**pat, ty::mk_err());
 446             }
 447         }
 448     }
 449 }
 450
 451 /// `path` is the AST path item naming the type of this struct.
 452 /// `fields` is the field patterns of the struct pattern.
 453 /// `struct_fields` describes the type of each field of the struct.
 454 /// `struct_id` is the ID of the struct.
 455 /// `etc` is true if the pattern said '...' and false otherwise.
 456 pub fn check_struct_pat_fields<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>,
 457                                          span: Span,
 458                                          fields: &[Spanned<ast::FieldPat>],
 459                                          struct_fields: &[ty::field<'tcx>],
 460                                          struct_id: ast::DefId,
 461                                          etc: bool) {
 462     let tcx = pcx.fcx.ccx.tcx;
 463
 464     // Index the struct fields' types.
 465     let field_type_map = struct_fields
 466         .iter()
 467         .map(|field| (field.name, field.mt.ty))
 468         .collect::<FnvHashMap<_, _>>();
 469
 470     // Keep track of which fields have already appeared in the pattern.
 471     let mut used_fields = FnvHashMap::new();
 472
 473     // Typecheck each field.
 474     for &Spanned { node: ref field, span } in fields.iter() {
 475         let field_type = match used_fields.entry(field.ident.name) {
 476             Occupied(occupied) => {
 477                 span_err!(tcx.sess, span, E0025,
 478                     "field `{}` bound multiple times in the pattern",
 479                     token::get_ident(field.ident));
 480                 span_note!(tcx.sess, *occupied.get(),
 481                     "field `{}` previously bound here",
 482                     token::get_ident(field.ident));
 483                 ty::mk_err()
 484             }
 485             Vacant(vacant) => {
 486                 vacant.set(span);
 487                 field_type_map.get(&field.ident.name).cloned()
 488                     .unwrap_or_else(|| {
 489                         span_err!(tcx.sess, span, E0026,
 490                             "struct `{}` does not have a field named `{}`",
 491                             ty::item_path_str(tcx, struct_id),
 492                             token::get_ident(field.ident));
 493                         ty::mk_err()
 494                     })
 495             }
 496         };
 497
 498         check_pat(pcx, &*field.pat, field_type);
 499     }
 500
 501     // Report an error if not all the fields were specified.
 502     if !etc {
 503         for field in struct_fields
 504             .iter()
 505             .filter(|field| !used_fields.contains_key(&field.name)) {
 506             span_err!(tcx.sess, span, E0027,
 507                 "pattern does not mention field `{}`",
 508                 token::get_name(field.name));
 509         }
 510     }
 511 }