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