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