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.
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.
11 #[allow(non_camel_case_types)];
13 use middle::pat_util::{PatIdMap, pat_id_map, pat_is_binding, pat_is_const};
15 use middle::typeck::check::demand;
16 use middle::typeck::check::{check_block, check_expr_has_type, FnCtxt};
17 use middle::typeck::check::{instantiate_path, lookup_def};
18 use middle::typeck::check::{structure_of, valid_range_bounds};
19 use middle::typeck::infer;
20 use middle::typeck::require_same_types;
22 use collections::{HashMap, HashSet};
26 use syntax::parse::token;
27 use syntax::codemap::Span;
28 use syntax::print::pprust;
30 pub fn check_match(fcx: @FnCtxt,
34 let tcx = fcx.ccx.tcx;
36 let discrim_ty = fcx.infcx().next_ty_var();
37 check_expr_has_type(fcx, discrim, discrim_ty);
39 // Typecheck the patterns first, so that we get types for all the
41 for arm in arms.iter() {
42 let mut pcx = pat_ctxt {
44 map: pat_id_map(tcx.def_map, *arm.pats.get(0)),
47 for p in arm.pats.iter() { check_pat(&mut pcx, *p, discrim_ty);}
50 // The result of the match is the common supertype of all the
51 // arms. Start out the value as bottom, since it's the, well,
52 // bottom the type lattice, and we'll be moving up the lattice as
53 // we process each arm. (Note that any match with 0 arms is matching
54 // on any empty type and is therefore unreachable; should the flow
55 // of execution reach it, we will fail, so bottom is an appropriate
57 let mut result_ty = ty::mk_bot();
59 // Now typecheck the blocks.
60 let mut saw_err = ty::type_is_error(discrim_ty);
61 for arm in arms.iter() {
62 let mut guard_err = false;
63 let mut guard_bot = false;
66 check_expr_has_type(fcx, e, ty::mk_bool());
67 let e_ty = fcx.expr_ty(e);
68 if ty::type_is_error(e_ty) {
71 else if ty::type_is_bot(e_ty) {
77 check_block(fcx, arm.body);
78 let bty = fcx.node_ty(arm.body.id);
79 saw_err = saw_err || ty::type_is_error(bty);
81 fcx.write_error(arm.body.id);
85 fcx.write_bot(arm.body.id);
89 infer::common_supertype(
91 infer::MatchExpression(expr.span),
92 true, // result_ty is "expected" here
98 result_ty = ty::mk_err();
99 } else if ty::type_is_bot(discrim_ty) {
100 result_ty = ty::mk_bot();
103 fcx.write_ty(expr.id, result_ty);
106 pub struct pat_ctxt {
111 pub fn check_pat_variant(pcx: &pat_ctxt, pat: &ast::Pat, path: &ast::Path,
112 subpats: &Option<Vec<@ast::Pat>>, expected: ty::t) {
114 // Typecheck the path.
116 let tcx = pcx.fcx.ccx.tcx;
118 let arg_types: ~[ty::t];
121 // structure_of requires type variables to be resolved.
122 // So when we pass in <expected>, it's an error if it
123 // contains type variables.
125 // Check to see whether this is an enum or a struct.
126 match *structure_of(pcx.fcx, pat.span, expected) {
127 ty::ty_enum(_, ref expected_substs) => {
128 // Lookup the enum and variant def ids:
129 let v_def = lookup_def(pcx.fcx, pat.span, pat.id);
130 match ast_util::variant_def_ids(v_def) {
131 Some((enm, var)) => {
132 // Assign the pattern the type of the *enum*, not the variant.
133 let enum_tpt = ty::lookup_item_type(tcx, enm);
134 instantiate_path(pcx.fcx,
141 // check that the type of the value being matched is a subtype
142 // of the type of the pattern:
143 let pat_ty = fcx.node_ty(pat.id);
144 demand::subtype(fcx, pat.span, expected, pat_ty);
146 // Get the expected types of the arguments.
149 ty::enum_variant_with_id(tcx, enm, var);
150 let var_tpt = ty::lookup_item_type(tcx, var);
152 if var_tpt.generics.type_param_defs().len() ==
153 expected_substs.tps.len()
155 ty::subst(tcx, expected_substs, *t)
158 *t // In this case, an error was already signaled
164 kind_name = "variant";
167 // See [Note-Type-error-reporting] in middle/typeck/infer/mod.rs
168 fcx.infcx().type_error_message_str_with_expected(pat.span,
170 expected.map_or(~"", |e| {
171 format!("mismatched types: expected `{}` but found {}",
173 Some(expected), ~"a structure pattern",
175 fcx.write_error(pat.id);
176 kind_name = "[error]";
177 arg_types = subpats.clone()
180 .map(|_| ty::mk_err())
185 ty::ty_struct(struct_def_id, ref expected_substs) => {
186 // Lookup the struct ctor def id
187 let s_def = lookup_def(pcx.fcx, pat.span, pat.id);
188 let s_def_id = ast_util::def_id_of_def(s_def);
190 // Assign the pattern the type of the struct.
191 let ctor_tpt = ty::lookup_item_type(tcx, s_def_id);
192 let struct_tpt = if ty::is_fn_ty(ctor_tpt.ty) {
193 ty::ty_param_bounds_and_ty {ty: ty::ty_fn_ret(ctor_tpt.ty),
198 instantiate_path(pcx.fcx,
205 // Check that the type of the value being matched is a subtype of
206 // the type of the pattern.
207 let pat_ty = fcx.node_ty(pat.id);
208 demand::subtype(fcx, pat.span, expected, pat_ty);
210 // Get the expected types of the arguments.
211 let class_fields = ty::struct_fields(
212 tcx, struct_def_id, expected_substs);
213 arg_types = class_fields.map(|field| field.mt.ty);
215 kind_name = "structure";
218 // See [Note-Type-error-reporting] in middle/typeck/infer/mod.rs
219 fcx.infcx().type_error_message_str_with_expected(pat.span,
221 expected.map_or(~"", |e| {
222 format!("mismatched types: expected `{}` but found {}",
224 Some(expected), ~"an enum or structure pattern",
226 fcx.write_error(pat.id);
227 kind_name = "[error]";
228 arg_types = subpats.clone()
231 .map(|_| ty::mk_err())
236 let arg_len = arg_types.len();
238 // Count the number of subpatterns.
241 None => subpats_len = arg_len,
242 Some(ref subpats) => subpats_len = subpats.len()
245 let mut error_happened = false;
249 if arg_len != subpats_len {
250 let s = format!("this pattern has {} field{}, but the corresponding {} has {} field{}",
252 if subpats_len == 1u { ~"" } else { ~"s" },
255 if arg_len == 1u { ~"" } else { ~"s" });
256 tcx.sess.span_err(pat.span, s);
257 error_happened = true;
261 for pats in subpats.iter() {
262 for (subpat, arg_ty) in pats.iter().zip(arg_types.iter()) {
263 check_pat(pcx, *subpat, *arg_ty);
267 } else if subpats_len > 0 {
268 tcx.sess.span_err(pat.span,
269 format!("this pattern has {} field{}, but the corresponding {} has no \
272 if subpats_len == 1u { "" } else { "s" },
274 error_happened = true;
278 for pats in subpats.iter() {
279 for pat in pats.iter() {
280 check_pat(pcx, *pat, ty::mk_err());
286 /// `path` is the AST path item naming the type of this struct.
287 /// `fields` is the field patterns of the struct pattern.
288 /// `class_fields` describes the type of each field of the struct.
289 /// `class_id` is the ID of the struct.
290 /// `substitutions` are the type substitutions applied to this struct type
291 /// (e.g. K,V in HashMap<K,V>).
292 /// `etc` is true if the pattern said '...' and false otherwise.
293 pub fn check_struct_pat_fields(pcx: &pat_ctxt,
296 fields: &[ast::FieldPat],
297 class_fields: ~[ty::field_ty],
298 class_id: ast::DefId,
299 substitutions: &ty::substs,
301 let tcx = pcx.fcx.ccx.tcx;
303 // Index the class fields. The second argument in the tuple is whether the
304 // field has been bound yet or not.
305 let mut field_map = HashMap::new();
306 for (i, class_field) in class_fields.iter().enumerate() {
307 field_map.insert(class_field.name, (i, false));
310 // Typecheck each field.
311 let mut found_fields = HashSet::new();
312 for field in fields.iter() {
313 match field_map.find_mut(&field.ident.name) {
314 Some(&(_, true)) => {
315 tcx.sess.span_err(span,
316 format!("field `{}` bound twice in pattern",
317 token::get_ident(field.ident)));
319 Some(&(index, ref mut used)) => {
321 let class_field = class_fields[index];
322 let field_type = ty::lookup_field_type(tcx,
326 check_pat(pcx, field.pat, field_type);
327 found_fields.insert(index);
330 let name = pprust::path_to_str(path);
331 // Check the pattern anyway, so that attempts to look
332 // up its type won't fail
333 check_pat(pcx, field.pat, ty::mk_err());
334 tcx.sess.span_err(span,
335 format!("struct `{}` does not have a field named `{}`",
337 token::get_ident(field.ident)));
342 // Report an error if not all the fields were specified.
344 for (i, field) in class_fields.iter().enumerate() {
345 if found_fields.contains(&i) {
349 tcx.sess.span_err(span,
350 format!("pattern does not mention field `{}`",
351 token::get_name(field.name)));
356 pub fn check_struct_pat(pcx: &pat_ctxt, pat_id: ast::NodeId, span: Span,
357 expected: ty::t, path: &ast::Path,
358 fields: &[ast::FieldPat], etc: bool,
359 struct_id: ast::DefId,
360 substitutions: &ty::substs) {
362 let tcx = pcx.fcx.ccx.tcx;
364 let class_fields = ty::lookup_struct_fields(tcx, struct_id);
366 // Check to ensure that the struct is the one specified.
367 let def_map = tcx.def_map.borrow();
368 match def_map.get().find(&pat_id) {
369 Some(&ast::DefStruct(supplied_def_id))
370 if supplied_def_id == struct_id => {
373 Some(&ast::DefStruct(..)) | Some(&ast::DefVariant(..)) => {
374 let name = pprust::path_to_str(path);
375 tcx.sess.span_err(span,
376 format!("mismatched types: expected `{}` but found `{}`",
377 fcx.infcx().ty_to_str(expected),
381 tcx.sess.span_bug(span, "resolve didn't write in struct ID");
385 check_struct_pat_fields(pcx, span, path, fields, class_fields, struct_id,
389 pub fn check_struct_like_enum_variant_pat(pcx: &pat_ctxt,
394 fields: &[ast::FieldPat],
397 substitutions: &ty::substs) {
399 let tcx = pcx.fcx.ccx.tcx;
401 // Find the variant that was specified.
402 let def_map = tcx.def_map.borrow();
403 match def_map.get().find(&pat_id) {
404 Some(&ast::DefVariant(found_enum_id, variant_id, _))
405 if found_enum_id == enum_id => {
406 // Get the struct fields from this struct-like enum variant.
407 let class_fields = ty::lookup_struct_fields(tcx, variant_id);
409 check_struct_pat_fields(pcx, span, path, fields, class_fields,
410 variant_id, substitutions, etc);
412 Some(&ast::DefStruct(..)) | Some(&ast::DefVariant(..)) => {
413 let name = pprust::path_to_str(path);
414 tcx.sess.span_err(span,
415 format!("mismatched types: expected `{}` but \
417 fcx.infcx().ty_to_str(expected),
421 tcx.sess.span_bug(span, "resolve didn't write in variant");
426 // Pattern checking is top-down rather than bottom-up so that bindings get
427 // their types immediately.
428 pub fn check_pat(pcx: &pat_ctxt, pat: &ast::Pat, expected: ty::t) {
430 let tcx = pcx.fcx.ccx.tcx;
433 ast::PatWild | ast::PatWildMulti => {
434 fcx.write_ty(pat.id, expected);
437 check_expr_has_type(fcx, lt, expected);
438 fcx.write_ty(pat.id, fcx.expr_ty(lt));
440 ast::PatRange(begin, end) => {
441 check_expr_has_type(fcx, begin, expected);
442 check_expr_has_type(fcx, end, expected);
444 fcx.infcx().resolve_type_vars_if_possible(fcx.expr_ty(begin));
446 fcx.infcx().resolve_type_vars_if_possible(fcx.expr_ty(end));
447 debug!("pat_range beginning type: {:?}", b_ty);
448 debug!("pat_range ending type: {:?}", e_ty);
449 if !require_same_types(
450 tcx, Some(fcx.infcx()), false, pat.span, b_ty, e_ty,
451 || ~"mismatched types in range")
454 } else if !ty::type_is_numeric(b_ty) && !ty::type_is_char(b_ty) {
455 tcx.sess.span_err(pat.span, "non-numeric type used in range");
457 match valid_range_bounds(fcx.ccx, begin, end) {
459 tcx.sess.span_err(begin.span,
460 "lower range bound must be less than upper");
463 tcx.sess.span_err(begin.span,
464 "mismatched types in range");
469 fcx.write_ty(pat.id, b_ty);
472 ast::PatIdent(..) if pat_is_const(tcx.def_map, pat) => {
473 let def_map = tcx.def_map.borrow();
474 let const_did = ast_util::def_id_of_def(def_map.get()
476 let const_tpt = ty::lookup_item_type(tcx, const_did);
477 demand::suptype(fcx, pat.span, expected, const_tpt.ty);
478 fcx.write_ty(pat.id, const_tpt.ty);
480 ast::PatIdent(bm, ref name, sub) if pat_is_binding(tcx.def_map, pat) => {
481 let typ = fcx.local_ty(pat.span, pat.id);
484 ast::BindByRef(mutbl) => {
485 // if the binding is like
486 // ref x | ref const x | ref mut x
487 // then the type of x is &M T where M is the mutability
488 // and T is the expected type
490 fcx.infcx().next_region_var(
491 infer::PatternRegion(pat.span));
492 let mt = ty::mt {ty: expected, mutbl: mutbl};
493 let region_ty = ty::mk_rptr(tcx, region_var, mt);
494 demand::eqtype(fcx, pat.span, region_ty, typ);
496 // otherwise the type of x is the expected type T
497 ast::BindByValue(_) => {
498 demand::eqtype(fcx, pat.span, expected, typ);
502 let canon_id = *pcx.map.get(&ast_util::path_to_ident(name));
503 if canon_id != pat.id {
504 let ct = fcx.local_ty(pat.span, canon_id);
505 demand::eqtype(fcx, pat.span, ct, typ);
507 fcx.write_ty(pat.id, typ);
509 debug!("(checking match) writing type for pat id {}", pat.id);
512 Some(p) => check_pat(pcx, p, expected),
516 ast::PatIdent(_, ref path, _) => {
517 check_pat_variant(pcx, pat, path, &Some(Vec::new()), expected);
519 ast::PatEnum(ref path, ref subpats) => {
520 check_pat_variant(pcx, pat, path, subpats, expected);
522 ast::PatStruct(ref path, ref fields, etc) => {
523 // Grab the class data that we care about.
524 let structure = structure_of(fcx, pat.span, expected);
525 let mut error_happened = false;
527 ty::ty_struct(cid, ref substs) => {
528 check_struct_pat(pcx, pat.id, pat.span, expected, path,
529 fields.as_slice(), etc, cid, substs);
531 ty::ty_enum(eid, ref substs) => {
532 check_struct_like_enum_variant_pat(pcx,
543 // See [Note-Type-error-reporting] in middle/typeck/infer/mod.rs
544 fcx.infcx().type_error_message_str_with_expected(pat.span,
546 expected.map_or(~"", |e| {
547 format!("mismatched types: expected `{}` but found {}",
549 Some(expected), ~"a structure pattern",
551 let def_map = tcx.def_map.borrow();
552 match def_map.get().find(&pat.id) {
553 Some(&ast::DefStruct(supplied_def_id)) => {
554 check_struct_pat(pcx,
565 regions: ty::ErasedRegions,
568 _ => () // Error, but we're already in an error case
570 error_happened = true;
574 // Finally, write in the type.
576 fcx.write_error(pat.id);
578 fcx.write_ty(pat.id, expected);
581 ast::PatTup(ref elts) => {
582 let s = structure_of(fcx, pat.span, expected);
583 let e_count = elts.len();
585 ty::ty_tup(ref ex_elts) if e_count == ex_elts.len() => {
586 for (i, elt) in elts.iter().enumerate() {
587 check_pat(pcx, *elt, ex_elts[i]);
589 fcx.write_ty(pat.id, expected);
592 for elt in elts.iter() {
593 check_pat(pcx, *elt, ty::mk_err());
595 // use terr_tuple_size if both types are tuples
596 let type_error = match *s {
597 ty::ty_tup(ref ex_elts) =>
598 ty::terr_tuple_size(ty::expected_found{expected: ex_elts.len(),
600 _ => ty::terr_mismatch
602 // See [Note-Type-error-reporting] in middle/typeck/infer/mod.rs
603 fcx.infcx().type_error_message_str_with_expected(pat.span, |expected, actual| {
604 expected.map_or(~"", |e| {
605 format!("mismatched types: expected `{}` but found {}",
606 e, actual)})}, Some(expected), ~"tuple", Some(&type_error));
607 fcx.write_error(pat.id);
611 ast::PatUniq(inner) => {
612 check_pointer_pat(pcx, Send, inner, pat.id, pat.span, expected);
614 ast::PatRegion(inner) => {
615 check_pointer_pat(pcx, Borrowed, inner, pat.id, pat.span, expected);
617 ast::PatVec(ref before, slice, ref after) => {
618 let default_region_var =
619 fcx.infcx().next_region_var(
620 infer::PatternRegion(pat.span));
622 let (elt_type, region_var) = match *structure_of(fcx,
625 ty::ty_vec(mt, vstore) => {
626 let region_var = match vstore {
627 ty::vstore_slice(r) => r,
629 fcx.type_error_message(pat.span,
631 ~"unique vector patterns are no \
638 ty::vstore_fixed(_) => {
644 ty::ty_unboxed_vec(mt) => {
645 (mt, default_region_var)
648 for &elt in before.iter() {
649 check_pat(pcx, elt, ty::mk_err());
651 for &elt in slice.iter() {
652 check_pat(pcx, elt, ty::mk_err());
654 for &elt in after.iter() {
655 check_pat(pcx, elt, ty::mk_err());
657 // See [Note-Type-error-reporting] in middle/typeck/infer/mod.rs
658 fcx.infcx().type_error_message_str_with_expected(
661 expected.map_or(~"", |e| {
662 format!("mismatched types: expected `{}` but found {}",
667 fcx.write_error(pat.id);
671 for elt in before.iter() {
672 check_pat(pcx, *elt, elt_type.ty);
676 let slice_ty = ty::mk_vec(tcx,
677 ty::mt {ty: elt_type.ty, mutbl: elt_type.mutbl},
678 ty::vstore_slice(region_var)
680 check_pat(pcx, slice_pat, slice_ty);
684 for elt in after.iter() {
685 check_pat(pcx, *elt, elt_type.ty);
687 fcx.write_ty(pat.id, expected);
692 // Helper function to check @, ~ and & patterns
693 pub fn check_pointer_pat(pcx: &pat_ctxt,
694 pointer_kind: PointerKind,
700 let check_inner: |ty::t| = |e_inner| {
701 check_pat(pcx, inner, e_inner);
702 fcx.write_ty(pat_id, expected);
704 match *structure_of(fcx, span, expected) {
705 ty::ty_uniq(e_inner) if pointer_kind == Send => {
706 check_inner(e_inner);
708 ty::ty_rptr(_, e_inner) if pointer_kind == Borrowed => {
709 check_inner(e_inner.ty);
712 check_pat(pcx, inner, ty::mk_err());
713 // See [Note-Type-error-reporting] in middle/typeck/infer/mod.rs
714 fcx.infcx().type_error_message_str_with_expected(
717 expected.map_or(~"", |e| {
718 format!("mismatched types: expected `{}` but found {}",
721 format!("{} pattern", match pointer_kind {
723 Borrowed => "an `&`-pointer"
726 fcx.write_error(pat_id);
732 enum PointerKind { Send, Borrowed }