src/librustc/middle/typeck/check/wf.rs

   1 // Copyright 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::region;
  12 use middle::subst;
  13 use middle::subst::{Subst};
  14 use middle::traits;
  15 use middle::ty::{mod, Ty};
  16 use middle::ty::liberate_late_bound_regions;
  17 use middle::ty_fold::{TypeFolder, TypeFoldable};
  18 use middle::typeck::astconv::AstConv;
  19 use middle::typeck::check::{FnCtxt, Inherited, blank_fn_ctxt, vtable, regionck};
  20 use middle::typeck::CrateCtxt;
  21 use util::ppaux::Repr;
  22
  23 use std::collections::HashSet;
  24 use syntax::ast;
  25 use syntax::ast_util::{local_def};
  26 use syntax::attr;
  27 use syntax::codemap::Span;
  28 use syntax::visit;
  29 use syntax::visit::Visitor;
  30
  31 pub struct CheckTypeWellFormedVisitor<'ccx, 'tcx:'ccx> {
  32     ccx: &'ccx CrateCtxt<'ccx, 'tcx>,
  33     cache: HashSet<Ty<'tcx>>
  34 }
  35
  36 impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
  37     pub fn new(ccx: &'ccx CrateCtxt<'ccx, 'tcx>) -> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
  38         CheckTypeWellFormedVisitor { ccx: ccx, cache: HashSet::new() }
  39     }
  40
  41     /// Checks that the field types (in a struct def'n) or argument types (in an enum def'n) are
  42     /// well-formed, meaning that they do not require any constraints not declared in the struct
  43     /// definition itself. For example, this definition would be illegal:
  44     ///
  45     ///     struct Ref<'a, T> { x: &'a T }
  46     ///
  47     /// because the type did not declare that `T:'a`.
  48     ///
  49     /// We do this check as a pre-pass before checking fn bodies because if these constraints are
  50     /// not included it frequently leads to confusing errors in fn bodies. So it's better to check
  51     /// the types first.
  52     fn check_item_well_formed(&mut self, item: &ast::Item) {
  53         let ccx = self.ccx;
  54         debug!("check_item_well_formed(it.id={}, it.ident={})",
  55                item.id,
  56                ty::item_path_str(ccx.tcx, local_def(item.id)));
  57
  58         match item.node {
  59             ast::ItemImpl(..) => {
  60                 self.check_impl(item);
  61             }
  62             ast::ItemFn(..) => {
  63                 self.check_item_type(item);
  64             }
  65             ast::ItemStatic(..) => {
  66                 self.check_item_type(item);
  67             }
  68             ast::ItemConst(..) => {
  69                 self.check_item_type(item);
  70             }
  71             ast::ItemStruct(ref struct_def, _) => {
  72                 self.check_type_defn(item, |fcx| {
  73                     vec![struct_variant(fcx, &**struct_def)]
  74                 });
  75             }
  76             ast::ItemEnum(ref enum_def, _) => {
  77                 self.check_type_defn(item, |fcx| {
  78                     enum_variants(fcx, enum_def)
  79                 });
  80             }
  81             _ => {}
  82         }
  83     }
  84
  85     fn with_fcx(&mut self,
  86                 item: &ast::Item,
  87                 f: for<'fcx> |&mut CheckTypeWellFormedVisitor<'ccx, 'tcx>,
  88                               &FnCtxt<'fcx, 'tcx>|) {
  89         let ccx = self.ccx;
  90         let item_def_id = local_def(item.id);
  91         let polytype = ty::lookup_item_type(ccx.tcx, item_def_id);
  92         let param_env =
  93             ty::construct_parameter_environment(ccx.tcx,
  94                                                 item.span,
  95                                                 &polytype.generics,
  96                                                 item.id);
  97         let inh = Inherited::new(ccx.tcx, param_env);
  98         let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(polytype.ty), item.id);
  99         f(self, &fcx);
 100         vtable::select_all_fcx_obligations_or_error(&fcx);
 101         regionck::regionck_item(&fcx, item);
 102     }
 103
 104     /// In a type definition, we check that to ensure that the types of the fields are well-formed.
 105     fn check_type_defn(&mut self,
 106                        item: &ast::Item,
 107                        lookup_fields: for<'fcx> |&FnCtxt<'fcx, 'tcx>|
 108                                                  -> Vec<AdtVariant<'tcx>>)
 109     {
 110         self.with_fcx(item, |this, fcx| {
 111             let variants = lookup_fields(fcx);
 112             let mut bounds_checker = BoundsChecker::new(fcx,
 113                                                         item.span,
 114                                                         region::CodeExtent::from_node_id(item.id),
 115                                                         Some(&mut this.cache));
 116             for variant in variants.iter() {
 117                 for field in variant.fields.iter() {
 118                     // Regions are checked below.
 119                     bounds_checker.check_traits_in_ty(field.ty);
 120                 }
 121
 122                 // For DST, all intermediate types must be sized.
 123                 if variant.fields.len() > 0 {
 124                     for field in variant.fields.init().iter() {
 125                         let cause = traits::ObligationCause::new(field.span, traits::FieldSized);
 126                         let obligation = traits::obligation_for_builtin_bound(fcx.tcx(),
 127                                                                               cause,
 128                                                                               field.ty,
 129                                                                               ty::BoundSized);
 130                         match obligation {
 131                             Ok(obligation) => fcx.register_obligation(obligation),
 132                             _ => {}
 133                         }
 134                     }
 135                 }
 136             }
 137
 138             let field_tys: Vec<Ty> =
 139                 variants.iter().flat_map(|v| v.fields.iter().map(|f| f.ty)).collect();
 140
 141             regionck::regionck_ensure_component_tys_wf(
 142                 fcx, item.span, field_tys.as_slice());
 143         });
 144     }
 145
 146     fn check_item_type(&mut self,
 147                        item: &ast::Item)
 148     {
 149         self.with_fcx(item, |this, fcx| {
 150             let mut bounds_checker = BoundsChecker::new(fcx,
 151                                                         item.span,
 152                                                         region::CodeExtent::from_node_id(item.id),
 153                                                         Some(&mut this.cache));
 154             let polytype = ty::lookup_item_type(fcx.tcx(), local_def(item.id));
 155             let item_ty = polytype.ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
 156             bounds_checker.check_traits_in_ty(item_ty);
 157         });
 158     }
 159
 160     fn check_impl(&mut self,
 161                   item: &ast::Item)
 162     {
 163         self.with_fcx(item, |this, fcx| {
 164             let item_scope = region::CodeExtent::from_node_id(item.id);
 165
 166             let mut bounds_checker = BoundsChecker::new(fcx,
 167                                                         item.span,
 168                                                         item_scope,
 169                                                         Some(&mut this.cache));
 170
 171             // Find the impl self type as seen from the "inside" --
 172             // that is, with all type parameters converted from bound
 173             // to free, and any late-bound regions on the impl
 174             // liberated.
 175             let self_ty = ty::node_id_to_type(fcx.tcx(), item.id);
 176             let self_ty = self_ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
 177             let self_ty = liberate_late_bound_regions(
 178                 fcx.tcx(), item_scope, &ty::bind(self_ty)).value;
 179
 180             bounds_checker.check_traits_in_ty(self_ty);
 181
 182             // Similarly, obtain an "inside" reference to the trait
 183             // that the impl implements.
 184             let trait_ref = match ty::impl_trait_ref(fcx.tcx(), local_def(item.id)) {
 185                 None => { return; }
 186                 Some(t) => { t }
 187             };
 188             let trait_ref = (*trait_ref).subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
 189             let trait_ref = liberate_late_bound_regions(fcx.tcx(), item_scope, &trait_ref);
 190
 191             // There are special rules that apply to drop.
 192             if
 193                 fcx.tcx().lang_items.drop_trait() == Some(trait_ref.def_id) &&
 194                 !attr::contains_name(item.attrs.as_slice(), "unsafe_destructor")
 195             {
 196                 match self_ty.sty {
 197                     ty::ty_struct(def_id, _) |
 198                     ty::ty_enum(def_id, _) => {
 199                         check_struct_safe_for_destructor(fcx, item.span, self_ty, def_id);
 200                     }
 201                     _ => {
 202                         // Coherence already reports an error in this case.
 203                     }
 204                 }
 205             }
 206
 207             // We are stricter on the trait-ref in an impl than the
 208             // self-type.  In particular, we enforce region
 209             // relationships. The reason for this is that (at least
 210             // presently) "appyling" an impl does not require that the
 211             // application site check the well-formedness constraints on the
 212             // trait reference. Instead, this is done at the impl site.
 213             // Arguably this is wrong and we should treat the trait-reference
 214             // the same way as we treat the self-type.
 215             bounds_checker.check_trait_ref(&trait_ref);
 216
 217             let trait_def = ty::lookup_trait_def(fcx.tcx(), trait_ref.def_id);
 218
 219             let cause =
 220                 traits::ObligationCause::new(
 221                     item.span,
 222                     traits::ItemObligation(trait_ref.def_id));
 223
 224             // Find the supertrait bounds. This will add `int:Bar`.
 225             //
 226             // FIXME -- This is a bit ill-factored. There is very similar
 227             // code in traits::util::obligations_for_generics.
 228             fcx.add_region_obligations_for_type_parameter(item.span,
 229                                                           &trait_def.bounds,
 230                                                           trait_ref.self_ty());
 231             for builtin_bound in trait_def.bounds.builtin_bounds.iter() {
 232                 let obligation = traits::obligation_for_builtin_bound(fcx.tcx(),
 233                                                                       cause,
 234                                                                       trait_ref.self_ty(),
 235                                                                       builtin_bound);
 236                 match obligation {
 237                     Ok (obligation) => fcx.register_obligation(obligation),
 238                     _ => {}
 239                 }
 240             }
 241             for trait_bound in trait_def.bounds.trait_bounds.iter() {
 242                 let trait_bound = trait_bound.subst(fcx.tcx(), &trait_ref.substs);
 243                 fcx.register_obligation(
 244                     traits::Obligation::new(cause, trait_bound));
 245             }
 246         });
 247     }
 248 }
 249
 250 impl<'ccx, 'tcx, 'v> Visitor<'v> for CheckTypeWellFormedVisitor<'ccx, 'tcx> {
 251     fn visit_item(&mut self, i: &ast::Item) {
 252         self.check_item_well_formed(i);
 253         visit::walk_item(self, i);
 254     }
 255 }
 256
 257 pub struct BoundsChecker<'cx,'tcx:'cx> {
 258     fcx: &'cx FnCtxt<'cx,'tcx>,
 259     span: Span,
 260     scope: region::CodeExtent,
 261     binding_count: uint,
 262     cache: Option<&'cx mut HashSet<Ty<'tcx>>>,
 263 }
 264
 265 impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
 266     pub fn new(fcx: &'cx FnCtxt<'cx,'tcx>,
 267                span: Span,
 268                scope: region::CodeExtent,
 269                cache: Option<&'cx mut HashSet<Ty<'tcx>>>)
 270                -> BoundsChecker<'cx,'tcx> {
 271         BoundsChecker { fcx: fcx, span: span, scope: scope,
 272                         cache: cache, binding_count: 0 }
 273     }
 274
 275     /// Given a trait ref like `A : Trait<B>`, where `Trait` is defined as (say):
 276     ///
 277     ///     trait Trait<B:OtherTrait> : Copy { ... }
 278     ///
 279     /// This routine will check that `B : OtherTrait` and `A : Trait<B>`. It will also recursively
 280     /// check that the types `A` and `B` are well-formed.
 281     ///
 282     /// Note that it does not (currently, at least) check that `A : Copy` (that check is delegated
 283     /// to the point where impl `A : Trait<B>` is implemented).
 284     pub fn check_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>) {
 285         let trait_def = ty::lookup_trait_def(self.fcx.tcx(), trait_ref.def_id);
 286
 287         let bounds = trait_def.generics.to_bounds(self.tcx(), &trait_ref.substs);
 288         self.fcx.add_obligations_for_parameters(
 289             traits::ObligationCause::new(
 290                 self.span,
 291                 traits::ItemObligation(trait_ref.def_id)),
 292             &trait_ref.substs,
 293             &bounds);
 294
 295         for &ty in trait_ref.substs.types.iter() {
 296             self.check_traits_in_ty(ty);
 297         }
 298     }
 299
 300     pub fn check_ty(&mut self, ty: Ty<'tcx>) {
 301         ty.fold_with(self);
 302     }
 303
 304     fn check_traits_in_ty(&mut self, ty: Ty<'tcx>) {
 305         // When checking types outside of a type def'n, we ignore
 306         // region obligations. See discussion below in fold_ty().
 307         self.binding_count += 1;
 308         ty.fold_with(self);
 309         self.binding_count -= 1;
 310     }
 311 }
 312
 313 impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
 314     fn tcx(&self) -> &ty::ctxt<'tcx> {
 315         self.fcx.tcx()
 316     }
 317
 318     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 319         debug!("BoundsChecker t={}",
 320                t.repr(self.tcx()));
 321
 322         match self.cache {
 323             Some(ref mut cache) => {
 324                 if !cache.insert(t) {
 325                     // Already checked this type! Don't check again.
 326                     debug!("cached");
 327                     return t;
 328                 }
 329             }
 330             None => { }
 331         }
 332
 333         match t.sty{
 334             ty::ty_struct(type_id, ref substs) |
 335             ty::ty_enum(type_id, ref substs) => {
 336                 let polytype = ty::lookup_item_type(self.fcx.tcx(), type_id);
 337
 338                 if self.binding_count == 0 {
 339                     self.fcx.add_obligations_for_parameters(
 340                         traits::ObligationCause::new(self.span,
 341                                                      traits::ItemObligation(type_id)),
 342                         substs,
 343                         &polytype.generics.to_bounds(self.tcx(), substs));
 344                 } else {
 345                     // There are two circumstances in which we ignore
 346                     // region obligations.
 347                     //
 348                     // The first is when we are inside of a closure
 349                     // type. This is because in that case the region
 350                     // obligations for the parameter types are things
 351                     // that the closure body gets to assume and the
 352                     // caller must prove at the time of call. In other
 353                     // words, if there is a type like `<'a, 'b> | &'a
 354                     // &'b int |`, it is well-formed, and caller will
 355                     // have to show that `'b : 'a` at the time of
 356                     // call.
 357                     //
 358                     // The second is when we are checking for
 359                     // well-formedness outside of a type def'n or fn
 360                     // body. This is for a similar reason: in general,
 361                     // we only do WF checking for regions in the
 362                     // result of expressions and type definitions, so
 363                     // to as allow for implicit where clauses.
 364                     //
 365                     // (I believe we should do the same for traits, but
 366                     // that will require an RFC. -nmatsakis)
 367                     self.fcx.add_trait_obligations_for_generics(
 368                         traits::ObligationCause::new(self.span,
 369                                                      traits::ItemObligation(type_id)),
 370                         substs,
 371                         &polytype.generics.to_bounds(self.tcx(), substs));
 372                 }
 373
 374                 self.fold_substs(substs);
 375             }
 376             ty::ty_bare_fn(ty::BareFnTy{sig: ref fn_sig, ..}) |
 377             ty::ty_closure(box ty::ClosureTy{sig: ref fn_sig, ..}) => {
 378                 self.binding_count += 1;
 379
 380                 let fn_sig = liberate_late_bound_regions(self.fcx.tcx(), self.scope, fn_sig);
 381
 382                 debug!("late-bound regions replaced: {}",
 383                        fn_sig.repr(self.tcx()));
 384
 385                 self.fold_fn_sig(&fn_sig);
 386
 387                 self.binding_count -= 1;
 388             }
 389             ref sty => {
 390                 self.fold_sty(sty);
 391             }
 392         }
 393
 394         t // we're not folding to produce a new type, so just return `t` here
 395     }
 396 }
 397
 398 ///////////////////////////////////////////////////////////////////////////
 399 // ADT
 400
 401 struct AdtVariant<'tcx> {
 402     fields: Vec<AdtField<'tcx>>,
 403 }
 404
 405 struct AdtField<'tcx> {
 406     ty: Ty<'tcx>,
 407     span: Span,
 408 }
 409
 410 fn struct_variant<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 411                             struct_def: &ast::StructDef)
 412                             -> AdtVariant<'tcx> {
 413     let fields =
 414         struct_def.fields
 415         .iter()
 416         .map(|field| {
 417             let field_ty = ty::node_id_to_type(fcx.tcx(), field.node.id);
 418             let field_ty = field_ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
 419             AdtField { ty: field_ty, span: field.span }
 420         })
 421         .collect();
 422     AdtVariant { fields: fields }
 423 }
 424
 425 fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 426                            enum_def: &ast::EnumDef)
 427                            -> Vec<AdtVariant<'tcx>> {
 428     enum_def.variants.iter()
 429         .map(|variant| {
 430             match variant.node.kind {
 431                 ast::TupleVariantKind(ref args) if args.len() > 0 => {
 432                     let ctor_ty = ty::node_id_to_type(fcx.tcx(), variant.node.id);
 433                     let arg_tys = ty::ty_fn_args(ctor_ty);
 434                     AdtVariant {
 435                         fields: args.iter().enumerate().map(|(index, arg)| {
 436                             let arg_ty = arg_tys[index];
 437                             let arg_ty = arg_ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
 438                             AdtField {
 439                                 ty: arg_ty,
 440                                 span: arg.ty.span
 441                             }
 442                         }).collect()
 443                     }
 444                 }
 445                 ast::TupleVariantKind(_) => {
 446                     AdtVariant {
 447                         fields: Vec::new()
 448                     }
 449                 }
 450                 ast::StructVariantKind(ref struct_def) => {
 451                     struct_variant(fcx, &**struct_def)
 452                 }
 453             }
 454         })
 455         .collect()
 456 }
 457
 458 ///////////////////////////////////////////////////////////////////////////
 459 // Special drop trait checking
 460
 461 fn check_struct_safe_for_destructor<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 462                                               span: Span,
 463                                               self_ty: Ty<'tcx>,
 464                                               struct_did: ast::DefId) {
 465     let struct_tpt = ty::lookup_item_type(fcx.tcx(), struct_did);
 466     if !struct_tpt.generics.has_type_params(subst::TypeSpace)
 467         && !struct_tpt.generics.has_region_params(subst::TypeSpace)
 468     {
 469         let cause = traits::ObligationCause::new(span, traits::DropTrait);
 470         let obligation = traits::obligation_for_builtin_bound(fcx.tcx(),
 471                                                               cause,
 472                                                               self_ty,
 473                                                               ty::BoundSend);
 474         match obligation {
 475             Ok(obligation) => fcx.register_obligation(obligation),
 476             _ => {}
 477         }
 478     } else {
 479         span_err!(fcx.tcx().sess, span, E0141,
 480                   "cannot implement a destructor on a structure \
 481                        with type parameters");
 482             span_note!(fcx.tcx().sess, span,
 483                        "use \"#[unsafe_destructor]\" on the implementation \
 484                         to force the compiler to allow this");
 485     }
 486 }