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