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(&mut self,
  85                 item: &ast::Item,
  86                 f: for<'fcx> |&mut CheckTypeWellFormedVisitor<'ccx, 'tcx>,
  87                               &FnCtxt<'fcx, 'tcx>|) {
  88         let ccx = self.ccx;
  89         let item_def_id = local_def(item.id);
  90         let polytype = ty::lookup_item_type(ccx.tcx, item_def_id);
  91         let param_env =
  92             ty::construct_parameter_environment(ccx.tcx,
  93                                                 &polytype.generics,
  94                                                 item.id);
  95         let inh = Inherited::new(ccx.tcx, param_env);
  96         let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(polytype.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(&mut self,
 104                        item: &ast::Item,
 105                        lookup_fields: for<'fcx> |&FnCtxt<'fcx, 'tcx>|
 106                                                  -> Vec<AdtVariant<'tcx>>)
 107     {
 108         self.with_fcx(item, |this, fcx| {
 109             let variants = lookup_fields(fcx);
 110             let mut bounds_checker = BoundsChecker::new(fcx,
 111                                                         item.span,
 112                                                         region::CodeExtent::from_node_id(item.id),
 113                                                         Some(&mut this.cache));
 114             for variant in variants.iter() {
 115                 for field in variant.fields.iter() {
 116                     // Regions are checked below.
 117                     bounds_checker.check_traits_in_ty(field.ty);
 118                 }
 119
 120                 // For DST, all intermediate types must be sized.
 121                 if variant.fields.len() > 0 {
 122                     for field in variant.fields.init().iter() {
 123                         fcx.register_builtin_bound(
 124                             field.ty,
 125                             ty::BoundSized,
 126                             traits::ObligationCause::new(field.span,
 127                                                          fcx.body_id,
 128                                                          traits::FieldSized));
 129                     }
 130                 }
 131             }
 132
 133             let field_tys: Vec<Ty> =
 134                 variants.iter().flat_map(|v| v.fields.iter().map(|f| f.ty)).collect();
 135
 136             regionck::regionck_ensure_component_tys_wf(
 137                 fcx, item.span, field_tys.as_slice());
 138         });
 139     }
 140
 141     fn check_item_type(&mut self,
 142                        item: &ast::Item)
 143     {
 144         self.with_fcx(item, |this, fcx| {
 145             let mut bounds_checker = BoundsChecker::new(fcx,
 146                                                         item.span,
 147                                                         region::CodeExtent::from_node_id(item.id),
 148                                                         Some(&mut this.cache));
 149             let type_scheme = ty::lookup_item_type(fcx.tcx(), local_def(item.id));
 150             let item_ty = fcx.instantiate_type_scheme(item.span,
 151                                                       &fcx.inh.param_env.free_substs,
 152                                                       &type_scheme.ty);
 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             let trait_ref = fcx.instantiate_type_scheme(item.span,
 185                                                         &fcx.inh.param_env.free_substs,
 186                                                         &trait_ref);
 187
 188             // There are special rules that apply to drop.
 189             if
 190                 fcx.tcx().lang_items.drop_trait() == Some(trait_ref.def_id) &&
 191                 !attr::contains_name(item.attrs.as_slice(), "unsafe_destructor")
 192             {
 193                 match self_ty.sty {
 194                     ty::ty_struct(def_id, _) |
 195                     ty::ty_enum(def_id, _) => {
 196                         check_struct_safe_for_destructor(fcx, item.span, def_id);
 197                     }
 198                     _ => {
 199                         // Coherence already reports an error in this case.
 200                     }
 201                 }
 202             }
 203
 204             if fcx.tcx().lang_items.copy_trait() == Some(trait_ref.def_id) {
 205                 // This is checked in coherence.
 206                 return
 207             }
 208
 209             // We are stricter on the trait-ref in an impl than the
 210             // self-type.  In particular, we enforce region
 211             // relationships. The reason for this is that (at least
 212             // presently) "appyling" an impl does not require that the
 213             // application site check the well-formedness constraints on the
 214             // trait reference. Instead, this is done at the impl site.
 215             // Arguably this is wrong and we should treat the trait-reference
 216             // the same way as we treat the self-type.
 217             bounds_checker.check_trait_ref(&*trait_ref);
 218
 219             let cause =
 220                 traits::ObligationCause::new(
 221                     item.span,
 222                     fcx.body_id,
 223                     traits::ItemObligation(trait_ref.def_id));
 224
 225             // Find the supertrait bounds. This will add `int:Bar`.
 226             let poly_trait_ref = ty::Binder(trait_ref);
 227             let predicates = ty::predicates_for_trait_ref(fcx.tcx(), &poly_trait_ref);
 228             for predicate in predicates.into_iter() {
 229                 fcx.register_predicate(traits::Obligation::new(cause.clone(), predicate));
 230             }
 231         });
 232     }
 233 }
 234
 235 impl<'ccx, 'tcx, 'v> Visitor<'v> for CheckTypeWellFormedVisitor<'ccx, 'tcx> {
 236     fn visit_item(&mut self, i: &ast::Item) {
 237         self.check_item_well_formed(i);
 238         visit::walk_item(self, i);
 239     }
 240 }
 241
 242 pub struct BoundsChecker<'cx,'tcx:'cx> {
 243     fcx: &'cx FnCtxt<'cx,'tcx>,
 244     span: Span,
 245     scope: region::CodeExtent,
 246     binding_count: uint,
 247     cache: Option<&'cx mut HashSet<Ty<'tcx>>>,
 248 }
 249
 250 impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
 251     pub fn new(fcx: &'cx FnCtxt<'cx,'tcx>,
 252                span: Span,
 253                scope: region::CodeExtent,
 254                cache: Option<&'cx mut HashSet<Ty<'tcx>>>)
 255                -> BoundsChecker<'cx,'tcx> {
 256         BoundsChecker { fcx: fcx, span: span, scope: scope,
 257                         cache: cache, binding_count: 0 }
 258     }
 259
 260     /// Given a trait ref like `A : Trait<B>`, where `Trait` is defined as (say):
 261     ///
 262     ///     trait Trait<B:OtherTrait> : Copy { ... }
 263     ///
 264     /// This routine will check that `B : OtherTrait` and `A : Trait<B>`. It will also recursively
 265     /// check that the types `A` and `B` are well-formed.
 266     ///
 267     /// Note that it does not (currently, at least) check that `A : Copy` (that check is delegated
 268     /// to the point where impl `A : Trait<B>` is implemented).
 269     pub fn check_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>) {
 270         let trait_def = ty::lookup_trait_def(self.fcx.tcx(), trait_ref.def_id);
 271
 272         let bounds = self.fcx.instantiate_bounds(self.span, trait_ref.substs, &trait_def.generics);
 273
 274         self.fcx.add_obligations_for_parameters(
 275             traits::ObligationCause::new(
 276                 self.span,
 277                 self.fcx.body_id,
 278                 traits::ItemObligation(trait_ref.def_id)),
 279             &bounds);
 280
 281         for &ty in trait_ref.substs.types.iter() {
 282             self.check_traits_in_ty(ty);
 283         }
 284     }
 285
 286     pub fn check_ty(&mut self, ty: Ty<'tcx>) {
 287         ty.fold_with(self);
 288     }
 289
 290     fn check_traits_in_ty(&mut self, ty: Ty<'tcx>) {
 291         // When checking types outside of a type def'n, we ignore
 292         // region obligations. See discussion below in fold_ty().
 293         self.binding_count += 1;
 294         ty.fold_with(self);
 295         self.binding_count -= 1;
 296     }
 297 }
 298
 299 impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
 300     fn tcx(&self) -> &ty::ctxt<'tcx> {
 301         self.fcx.tcx()
 302     }
 303
 304     fn fold_binder<T>(&mut self, binder: &ty::Binder<T>) -> ty::Binder<T>
 305         where T : TypeFoldable<'tcx> + Repr<'tcx>
 306     {
 307         self.binding_count += 1;
 308         let value = liberate_late_bound_regions(self.fcx.tcx(), self.scope, binder);
 309         debug!("BoundsChecker::fold_binder: late-bound regions replaced: {}",
 310                value.repr(self.tcx()));
 311         let value = value.fold_with(self);
 312         self.binding_count -= 1;
 313         ty::Binder(value)
 314     }
 315
 316     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 317         debug!("BoundsChecker t={}",
 318                t.repr(self.tcx()));
 319
 320         match self.cache {
 321             Some(ref mut cache) => {
 322                 if !cache.insert(t) {
 323                     // Already checked this type! Don't check again.
 324                     debug!("cached");
 325                     return t;
 326                 }
 327             }
 328             None => { }
 329         }
 330
 331         match t.sty{
 332             ty::ty_struct(type_id, substs) |
 333             ty::ty_enum(type_id, substs) => {
 334                 let type_scheme = ty::lookup_item_type(self.fcx.tcx(), type_id);
 335                 let bounds = self.fcx.instantiate_bounds(self.span, substs, &type_scheme.generics);
 336
 337                 if self.binding_count == 0 {
 338                     self.fcx.add_obligations_for_parameters(
 339                         traits::ObligationCause::new(self.span,
 340                                                      self.fcx.body_id,
 341                                                      traits::ItemObligation(type_id)),
 342                         &bounds);
 343                 } else {
 344                     // There are two circumstances in which we ignore
 345                     // region obligations.
 346                     //
 347                     // The first is when we are inside of a closure
 348                     // type. This is because in that case the region
 349                     // obligations for the parameter types are things
 350                     // that the closure body gets to assume and the
 351                     // caller must prove at the time of call. In other
 352                     // words, if there is a type like `<'a, 'b> | &'a
 353                     // &'b int |`, it is well-formed, and caller will
 354                     // have to show that `'b : 'a` at the time of
 355                     // call.
 356                     //
 357                     // The second is when we are checking for
 358                     // well-formedness outside of a type def'n or fn
 359                     // body. This is for a similar reason: in general,
 360                     // we only do WF checking for regions in the
 361                     // result of expressions and type definitions, so
 362                     // to as allow for implicit where clauses.
 363                     //
 364                     // (I believe we should do the same for traits, but
 365                     // that will require an RFC. -nmatsakis)
 366                     let bounds = filter_to_trait_obligations(bounds);
 367                     self.fcx.add_obligations_for_parameters(
 368                         traits::ObligationCause::new(self.span,
 369                                                      self.fcx.body_id,
 370                                                      traits::ItemObligation(type_id)),
 371                         &bounds);
 372                 }
 373
 374                 self.fold_substs(substs);
 375             }
 376             _ => {
 377                 super_fold_ty(self, t);
 378             }
 379         }
 380
 381         t // we're not folding to produce a new type, so just return `t` here
 382     }
 383 }
 384
 385 ///////////////////////////////////////////////////////////////////////////
 386 // ADT
 387
 388 struct AdtVariant<'tcx> {
 389     fields: Vec<AdtField<'tcx>>,
 390 }
 391
 392 struct AdtField<'tcx> {
 393     ty: Ty<'tcx>,
 394     span: Span,
 395 }
 396
 397 fn struct_variant<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 398                             struct_def: &ast::StructDef)
 399                             -> AdtVariant<'tcx> {
 400     let fields =
 401         struct_def.fields
 402         .iter()
 403         .map(|field| {
 404             let field_ty = ty::node_id_to_type(fcx.tcx(), field.node.id);
 405             let field_ty = fcx.instantiate_type_scheme(field.span,
 406                                                        &fcx.inh.param_env.free_substs,
 407                                                        &field_ty);
 408             AdtField { ty: field_ty, span: field.span }
 409         })
 410         .collect();
 411     AdtVariant { fields: fields }
 412 }
 413
 414 fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 415                            enum_def: &ast::EnumDef)
 416                            -> Vec<AdtVariant<'tcx>> {
 417     enum_def.variants.iter()
 418         .map(|variant| {
 419             match variant.node.kind {
 420                 ast::TupleVariantKind(ref args) if args.len() > 0 => {
 421                     let ctor_ty = ty::node_id_to_type(fcx.tcx(), variant.node.id);
 422                     let arg_tys = ty::ty_fn_args(ctor_ty);
 423                     AdtVariant {
 424                         fields: args.iter().enumerate().map(|(index, arg)| {
 425                             let arg_ty = arg_tys[index];
 426                             let arg_ty =
 427                                 fcx.instantiate_type_scheme(variant.span,
 428                                                             &fcx.inh.param_env.free_substs,
 429                                                             &arg_ty);
 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 fn filter_to_trait_obligations<'tcx>(bounds: ty::GenericBounds<'tcx>)
 451                                      -> ty::GenericBounds<'tcx>
 452 {
 453     let mut result = ty::GenericBounds::empty();
 454     for (space, _, predicate) in bounds.predicates.iter_enumerated() {
 455         match *predicate {
 456             ty::Predicate::Trait(..) |
 457             ty::Predicate::Projection(..) => {
 458                 result.predicates.push(space, predicate.clone())
 459             }
 460             ty::Predicate::Equate(..) |
 461             ty::Predicate::TypeOutlives(..) |
 462             ty::Predicate::RegionOutlives(..) => {
 463             }
 464         }
 465     }
 466     result
 467 }
 468
 469 ///////////////////////////////////////////////////////////////////////////
 470 // Special drop trait checking
 471
 472 fn check_struct_safe_for_destructor<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 473                                               span: Span,
 474                                               struct_did: ast::DefId) {
 475     let struct_tpt = ty::lookup_item_type(fcx.tcx(), struct_did);
 476     if struct_tpt.generics.has_type_params(subst::TypeSpace)
 477         || struct_tpt.generics.has_region_params(subst::TypeSpace)
 478     {
 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 }