src/librustc_typeck/check/wfcheck.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 check::{Inherited, FnCtxt};
  12 use constrained_type_params::{identify_constrained_type_params, Parameter};
  13
  14 use hir::def_id::DefId;
  15 use rustc::traits::{self, ObligationCauseCode};
  16 use rustc::ty::{self, Lift, Ty, TyCtxt, GenericParamDefKind, TypeFoldable};
  17 use rustc::ty::subst::{Subst, Substs};
  18 use rustc::ty::util::ExplicitSelf;
  19 use rustc::util::nodemap::{FxHashSet, FxHashMap};
  20 use rustc::middle::lang_items;
  21 use rustc::infer::opaque_types::may_define_existential_type;
  22
  23 use syntax::ast;
  24 use syntax::feature_gate::{self, GateIssue};
  25 use syntax_pos::Span;
  26 use errors::{DiagnosticBuilder, DiagnosticId};
  27
  28 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
  29 use rustc::hir;
  30
  31 /// Helper type of a temporary returned by .for_item(...).
  32 /// Necessary because we can't write the following bound:
  33 /// F: for<'b, 'tcx> where 'gcx: 'tcx FnOnce(FnCtxt<'b, 'gcx, 'tcx>).
  34 struct CheckWfFcxBuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  35     inherited: super::InheritedBuilder<'a, 'gcx, 'tcx>,
  36     id: ast::NodeId,
  37     span: Span,
  38     param_env: ty::ParamEnv<'tcx>,
  39 }
  40
  41 impl<'a, 'gcx, 'tcx> CheckWfFcxBuilder<'a, 'gcx, 'tcx> {
  42     fn with_fcx<F>(&'tcx mut self, f: F) where
  43         F: for<'b> FnOnce(&FnCtxt<'b, 'gcx, 'tcx>,
  44                          TyCtxt<'b, 'gcx, 'gcx>) -> Vec<Ty<'tcx>>
  45     {
  46         let id = self.id;
  47         let span = self.span;
  48         let param_env = self.param_env;
  49         self.inherited.enter(|inh| {
  50             let fcx = FnCtxt::new(&inh, param_env, id);
  51             if !inh.tcx.features().trivial_bounds {
  52                 // As predicates are cached rather than obligations, this
  53                 // needsto be called first so that they are checked with an
  54                 // empty param_env.
  55                 check_false_global_bounds(&fcx, span, id);
  56             }
  57             let wf_tys = f(&fcx, fcx.tcx.global_tcx());
  58             fcx.select_all_obligations_or_error();
  59             fcx.regionck_item(id, span, &wf_tys);
  60         });
  61     }
  62 }
  63
  64 /// Checks that the field types (in a struct def'n) or argument types (in an enum def'n) are
  65 /// well-formed, meaning that they do not require any constraints not declared in the struct
  66 /// definition itself. For example, this definition would be illegal:
  67 ///
  68 ///     struct Ref<'a, T> { x: &'a T }
  69 ///
  70 /// because the type did not declare that `T:'a`.
  71 ///
  72 /// We do this check as a pre-pass before checking fn bodies because if these constraints are
  73 /// not included it frequently leads to confusing errors in fn bodies. So it's better to check
  74 /// the types first.
  75 pub fn check_item_well_formed<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) {
  76     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
  77     let item = tcx.hir.expect_item(node_id);
  78
  79     debug!("check_item_well_formed(it.id={}, it.name={})",
  80            item.id,
  81            tcx.item_path_str(def_id));
  82
  83     match item.node {
  84         // Right now we check that every default trait implementation
  85         // has an implementation of itself. Basically, a case like:
  86         //
  87         // `impl Trait for T {}`
  88         //
  89         // has a requirement of `T: Trait` which was required for default
  90         // method implementations. Although this could be improved now that
  91         // there's a better infrastructure in place for this, it's being left
  92         // for a follow-up work.
  93         //
  94         // Since there's such a requirement, we need to check *just* positive
  95         // implementations, otherwise things like:
  96         //
  97         // impl !Send for T {}
  98         //
  99         // won't be allowed unless there's an *explicit* implementation of `Send`
 100         // for `T`
 101         hir::ItemKind::Impl(_, polarity, defaultness, _, ref trait_ref, ref self_ty, _) => {
 102             let is_auto = tcx.impl_trait_ref(tcx.hir.local_def_id(item.id))
 103                                 .map_or(false, |trait_ref| tcx.trait_is_auto(trait_ref.def_id));
 104             if let (hir::Defaultness::Default { .. }, true) = (defaultness, is_auto) {
 105                 tcx.sess.span_err(item.span, "impls of auto traits cannot be default");
 106             }
 107             if polarity == hir::ImplPolarity::Positive {
 108                 check_impl(tcx, item, self_ty, trait_ref);
 109             } else {
 110                 // FIXME(#27579) what amount of WF checking do we need for neg impls?
 111                 if trait_ref.is_some() && !is_auto {
 112                     span_err!(tcx.sess, item.span, E0192,
 113                               "negative impls are only allowed for \
 114                                auto traits (e.g., `Send` and `Sync`)")
 115                 }
 116             }
 117         }
 118         hir::ItemKind::Fn(..) => {
 119             check_item_fn(tcx, item);
 120         }
 121         hir::ItemKind::Static(ref ty, ..) => {
 122             check_item_type(tcx, item.id, ty.span);
 123         }
 124         hir::ItemKind::Const(ref ty, ..) => {
 125             check_item_type(tcx, item.id, ty.span);
 126         }
 127         hir::ItemKind::ForeignMod(ref module) => for it in module.items.iter() {
 128             if let hir::ForeignItemKind::Static(ref ty, ..) = it.node {
 129                 check_item_type(tcx, it.id, ty.span);
 130             }
 131         },
 132         hir::ItemKind::Struct(ref struct_def, ref ast_generics) => {
 133             check_type_defn(tcx, item, false, |fcx| {
 134                 vec![fcx.non_enum_variant(struct_def)]
 135             });
 136
 137             check_variances_for_type_defn(tcx, item, ast_generics);
 138         }
 139         hir::ItemKind::Union(ref struct_def, ref ast_generics) => {
 140             check_type_defn(tcx, item, true, |fcx| {
 141                 vec![fcx.non_enum_variant(struct_def)]
 142             });
 143
 144             check_variances_for_type_defn(tcx, item, ast_generics);
 145         }
 146         hir::ItemKind::Enum(ref enum_def, ref ast_generics) => {
 147             check_type_defn(tcx, item, true, |fcx| {
 148                 fcx.enum_variants(enum_def)
 149             });
 150
 151             check_variances_for_type_defn(tcx, item, ast_generics);
 152         }
 153         hir::ItemKind::Trait(..) => {
 154             check_trait(tcx, item);
 155         }
 156         _ => {}
 157     }
 158 }
 159
 160 pub fn check_trait_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) {
 161     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 162     let trait_item = tcx.hir.expect_trait_item(node_id);
 163
 164     let method_sig = match trait_item.node {
 165         hir::TraitItemKind::Method(ref sig, _) => Some(sig),
 166         _ => None
 167     };
 168     check_associated_item(tcx, trait_item.id, trait_item.span, method_sig);
 169 }
 170
 171 pub fn check_impl_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) {
 172     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 173     let impl_item = tcx.hir.expect_impl_item(node_id);
 174
 175     let method_sig = match impl_item.node {
 176         hir::ImplItemKind::Method(ref sig, _) => Some(sig),
 177         _ => None
 178     };
 179     check_associated_item(tcx, impl_item.id, impl_item.span, method_sig);
 180 }
 181
 182 fn check_associated_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 183                                    item_id: ast::NodeId,
 184                                    span: Span,
 185                                    sig_if_method: Option<&hir::MethodSig>) {
 186     let code = ObligationCauseCode::MiscObligation;
 187     for_id(tcx, item_id, span).with_fcx(|fcx, tcx| {
 188         let item = fcx.tcx.associated_item(fcx.tcx.hir.local_def_id(item_id));
 189
 190         let (mut implied_bounds, self_ty) = match item.container {
 191             ty::TraitContainer(_) => (vec![], fcx.tcx.mk_self_type()),
 192             ty::ImplContainer(def_id) => (fcx.impl_implied_bounds(def_id, span),
 193                                           fcx.tcx.type_of(def_id))
 194         };
 195
 196         match item.kind {
 197             ty::AssociatedKind::Const => {
 198                 let ty = fcx.tcx.type_of(item.def_id);
 199                 let ty = fcx.normalize_associated_types_in(span, &ty);
 200                 fcx.register_wf_obligation(ty, span, code.clone());
 201             }
 202             ty::AssociatedKind::Method => {
 203                 reject_shadowing_parameters(fcx.tcx, item.def_id);
 204                 let sig = fcx.tcx.fn_sig(item.def_id);
 205                 let sig = fcx.normalize_associated_types_in(span, &sig);
 206                 check_fn_or_method(tcx, fcx, span, sig,
 207                                    item.def_id, &mut implied_bounds);
 208                 let sig_if_method = sig_if_method.expect("bad signature for method");
 209                 check_method_receiver(fcx, sig_if_method, &item, self_ty);
 210             }
 211             ty::AssociatedKind::Type => {
 212                 if item.defaultness.has_value() {
 213                     let ty = fcx.tcx.type_of(item.def_id);
 214                     let ty = fcx.normalize_associated_types_in(span, &ty);
 215                     fcx.register_wf_obligation(ty, span, code.clone());
 216                 }
 217             }
 218             ty::AssociatedKind::Existential => {
 219                 // do nothing, existential types check themselves
 220             }
 221         }
 222
 223         implied_bounds
 224     })
 225 }
 226
 227 fn for_item<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>, item: &hir::Item)
 228                             -> CheckWfFcxBuilder<'a, 'gcx, 'tcx> {
 229     for_id(tcx, item.id, item.span)
 230 }
 231
 232 fn for_id<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>, id: ast::NodeId, span: Span)
 233                           -> CheckWfFcxBuilder<'a, 'gcx, 'tcx> {
 234     let def_id = tcx.hir.local_def_id(id);
 235     CheckWfFcxBuilder {
 236         inherited: Inherited::build(tcx, def_id),
 237         id,
 238         span,
 239         param_env: tcx.param_env(def_id),
 240     }
 241 }
 242
 243 /// In a type definition, we check that to ensure that the types of the fields are well-formed.
 244 fn check_type_defn<'a, 'tcx, F>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 245                                 item: &hir::Item, all_sized: bool, mut lookup_fields: F)
 246     where F: for<'fcx, 'gcx, 'tcx2> FnMut(&FnCtxt<'fcx, 'gcx, 'tcx2>) -> Vec<AdtVariant<'tcx2>>
 247 {
 248     for_item(tcx, item).with_fcx(|fcx, fcx_tcx| {
 249         let variants = lookup_fields(fcx);
 250         let def_id = fcx.tcx.hir.local_def_id(item.id);
 251         let packed = fcx.tcx.adt_def(def_id).repr.packed();
 252
 253         for variant in &variants {
 254             // For DST, or when drop needs to copy things around, all
 255             // intermediate types must be sized.
 256             let needs_drop_copy = || {
 257                 packed && {
 258                     let ty = variant.fields.last().unwrap().ty;
 259                     let ty = fcx.tcx.erase_regions(&ty).lift_to_tcx(fcx_tcx)
 260                         .unwrap_or_else(|| {
 261                             span_bug!(item.span, "inference variables in {:?}", ty)
 262                         });
 263                     ty.needs_drop(fcx_tcx, fcx_tcx.param_env(def_id))
 264                 }
 265             };
 266             let all_sized =
 267                 all_sized ||
 268                 variant.fields.is_empty() ||
 269                 needs_drop_copy();
 270             let unsized_len = if all_sized {
 271                 0
 272             } else {
 273                 1
 274             };
 275             for (idx, field) in variant.fields[..variant.fields.len() - unsized_len]
 276                 .iter()
 277                 .enumerate()
 278             {
 279                 let last = idx == variant.fields.len() - 1;
 280                 fcx.register_bound(
 281                     field.ty,
 282                     fcx.tcx.require_lang_item(lang_items::SizedTraitLangItem),
 283                     traits::ObligationCause::new(
 284                         field.span,
 285                         fcx.body_id,
 286                         traits::FieldSized {
 287                             adt_kind: match item.node.adt_kind() {
 288                                 Some(i) => i,
 289                                 None => bug!(),
 290                             },
 291                             last
 292                         }
 293                     )
 294                 );
 295             }
 296
 297             // All field types must be well-formed.
 298             for field in &variant.fields {
 299                 fcx.register_wf_obligation(field.ty, field.span,
 300                     ObligationCauseCode::MiscObligation)
 301             }
 302         }
 303
 304         check_where_clauses(tcx, fcx, item.span, def_id, None);
 305
 306         vec![] // no implied bounds in a struct def'n
 307     });
 308 }
 309
 310 fn check_trait<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item: &hir::Item) {
 311     let trait_def_id = tcx.hir.local_def_id(item.id);
 312
 313     let trait_def = tcx.trait_def(trait_def_id);
 314     if trait_def.is_marker {
 315         for associated_def_id in &*tcx.associated_item_def_ids(trait_def_id) {
 316             struct_span_err!(
 317                 tcx.sess,
 318                 tcx.def_span(*associated_def_id),
 319                 E0714,
 320                 "marker traits cannot have associated items",
 321             ).emit();
 322         }
 323     }
 324
 325     for_item(tcx, item).with_fcx(|fcx, _| {
 326         check_where_clauses(tcx, fcx, item.span, trait_def_id, None);
 327         vec![]
 328     });
 329 }
 330
 331 fn check_item_fn<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item: &hir::Item) {
 332     for_item(tcx, item).with_fcx(|fcx, tcx| {
 333         let def_id = fcx.tcx.hir.local_def_id(item.id);
 334         let sig = fcx.tcx.fn_sig(def_id);
 335         let sig = fcx.normalize_associated_types_in(item.span, &sig);
 336         let mut implied_bounds = vec![];
 337         check_fn_or_method(tcx, fcx, item.span, sig,
 338                            def_id, &mut implied_bounds);
 339         implied_bounds
 340     })
 341 }
 342
 343 fn check_item_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_id: ast::NodeId, ty_span: Span) {
 344     debug!("check_item_type: {:?}", item_id);
 345
 346     for_id(tcx, item_id, ty_span).with_fcx(|fcx, _this| {
 347         let ty = fcx.tcx.type_of(fcx.tcx.hir.local_def_id(item_id));
 348         let item_ty = fcx.normalize_associated_types_in(ty_span, &ty);
 349
 350         fcx.register_wf_obligation(item_ty, ty_span, ObligationCauseCode::MiscObligation);
 351         fcx.register_bound(
 352             item_ty,
 353             fcx.tcx.require_lang_item(lang_items::SizedTraitLangItem),
 354             traits::ObligationCause::new(
 355                 ty_span,
 356                 fcx.body_id,
 357                 traits::MiscObligation,
 358             ),
 359         );
 360
 361         vec![] // no implied bounds in a const etc
 362     });
 363 }
 364
 365 fn check_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 366                         item: &hir::Item,
 367                         ast_self_ty: &hir::Ty,
 368                         ast_trait_ref: &Option<hir::TraitRef>)
 369 {
 370     debug!("check_impl: {:?}", item);
 371
 372     for_item(tcx, item).with_fcx(|fcx, tcx| {
 373         let item_def_id = fcx.tcx.hir.local_def_id(item.id);
 374
 375         match *ast_trait_ref {
 376             Some(ref ast_trait_ref) => {
 377                 let trait_ref = fcx.tcx.impl_trait_ref(item_def_id).unwrap();
 378                 let trait_ref =
 379                     fcx.normalize_associated_types_in(
 380                         ast_trait_ref.path.span, &trait_ref);
 381                 let obligations =
 382                     ty::wf::trait_obligations(fcx,
 383                                                 fcx.param_env,
 384                                                 fcx.body_id,
 385                                                 &trait_ref,
 386                                                 ast_trait_ref.path.span);
 387                 for obligation in obligations {
 388                     fcx.register_predicate(obligation);
 389                 }
 390             }
 391             None => {
 392                 let self_ty = fcx.tcx.type_of(item_def_id);
 393                 let self_ty = fcx.normalize_associated_types_in(item.span, &self_ty);
 394                 fcx.register_wf_obligation(self_ty, ast_self_ty.span,
 395                     ObligationCauseCode::MiscObligation);
 396             }
 397         }
 398
 399         check_where_clauses(tcx, fcx, item.span, item_def_id, None);
 400
 401         fcx.impl_implied_bounds(item_def_id, item.span)
 402     });
 403 }
 404
 405 /// Checks where clauses and inline bounds that are declared on def_id.
 406 fn check_where_clauses<'a, 'gcx, 'fcx, 'tcx>(
 407     tcx: TyCtxt<'a, 'gcx, 'gcx>,
 408     fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
 409     span: Span,
 410     def_id: DefId,
 411     return_ty: Option<Ty<'tcx>>,
 412 ) {
 413     use ty::subst::Subst;
 414     use rustc::ty::TypeFoldable;
 415
 416     let predicates = fcx.tcx.predicates_of(def_id);
 417
 418     let generics = tcx.generics_of(def_id);
 419     let is_our_default = |def: &ty::GenericParamDef| {
 420         match def.kind {
 421             GenericParamDefKind::Type { has_default, .. } => {
 422                 has_default && def.index >= generics.parent_count as u32
 423             }
 424             _ => unreachable!()
 425         }
 426     };
 427
 428     // Check that concrete defaults are well-formed. See test `type-check-defaults.rs`.
 429     // For example this forbids the declaration:
 430     // struct Foo<T = Vec<[u32]>> { .. }
 431     // Here the default `Vec<[u32]>` is not WF because `[u32]: Sized` does not hold.
 432     for param in &generics.params {
 433         if let GenericParamDefKind::Type {..} = param.kind {
 434             if is_our_default(&param) {
 435                 let ty = fcx.tcx.type_of(param.def_id);
 436                 // ignore dependent defaults -- that is, where the default of one type
 437                 // parameter includes another (e.g., <T, U = T>). In those cases, we can't
 438                 // be sure if it will error or not as user might always specify the other.
 439                 if !ty.needs_subst() {
 440                     fcx.register_wf_obligation(ty, fcx.tcx.def_span(param.def_id),
 441                         ObligationCauseCode::MiscObligation);
 442                 }
 443             }
 444         }
 445     }
 446
 447     // Check that trait predicates are WF when params are substituted by their defaults.
 448     // We don't want to overly constrain the predicates that may be written but we want to
 449     // catch cases where a default my never be applied such as `struct Foo<T: Copy = String>`.
 450     // Therefore we check if a predicate which contains a single type param
 451     // with a concrete default is WF with that default substituted.
 452     // For more examples see tests `defaults-well-formedness.rs` and `type-check-defaults.rs`.
 453     //
 454     // First we build the defaulted substitution.
 455     let substs = Substs::for_item(fcx.tcx, def_id, |param, _| {
 456         match param.kind {
 457             GenericParamDefKind::Lifetime => {
 458                 // All regions are identity.
 459                 fcx.tcx.mk_param_from_def(param)
 460             }
 461             GenericParamDefKind::Type {..} => {
 462                 // If the param has a default,
 463                 if is_our_default(param) {
 464                     let default_ty = fcx.tcx.type_of(param.def_id);
 465                     // and it's not a dependent default
 466                     if !default_ty.needs_subst() {
 467                         // then substitute with the default.
 468                         return default_ty.into();
 469                     }
 470                 }
 471                 // Mark unwanted params as err.
 472                 fcx.tcx.types.err.into()
 473             }
 474         }
 475     });
 476     // Now we build the substituted predicates.
 477     let default_obligations = predicates.predicates.iter().flat_map(|&(pred, _)| {
 478         #[derive(Default)]
 479         struct CountParams { params: FxHashSet<u32> }
 480         impl<'tcx> ty::fold::TypeVisitor<'tcx> for CountParams {
 481             fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 482                 match t.sty {
 483                     ty::Param(p) => {
 484                         self.params.insert(p.idx);
 485                         t.super_visit_with(self)
 486                     }
 487                     _ => t.super_visit_with(self)
 488                 }
 489             }
 490
 491             fn visit_region(&mut self, _: ty::Region<'tcx>) -> bool {
 492                 true
 493             }
 494         }
 495         let mut param_count = CountParams::default();
 496         let has_region = pred.visit_with(&mut param_count);
 497         let substituted_pred = pred.subst(fcx.tcx, substs);
 498         // Don't check non-defaulted params, dependent defaults (including lifetimes)
 499         // or preds with multiple params.
 500         if substituted_pred.references_error() || param_count.params.len() > 1 || has_region {
 501             None
 502         } else if predicates.predicates.iter().any(|&(p, _)| p == substituted_pred) {
 503             // Avoid duplication of predicates that contain no parameters, for example.
 504             None
 505         } else {
 506             Some(substituted_pred)
 507         }
 508     }).map(|pred| {
 509         // convert each of those into an obligation. So if you have
 510         // something like `struct Foo<T: Copy = String>`, we would
 511         // take that predicate `T: Copy`, substitute to `String: Copy`
 512         // (actually that happens in the previous `flat_map` call),
 513         // and then try to prove it (in this case, we'll fail).
 514         //
 515         // Note the subtle difference from how we handle `predicates`
 516         // below: there, we are not trying to prove those predicates
 517         // to be *true* but merely *well-formed*.
 518         let pred = fcx.normalize_associated_types_in(span, &pred);
 519         let cause = traits::ObligationCause::new(span, fcx.body_id, traits::ItemObligation(def_id));
 520         traits::Obligation::new(cause, fcx.param_env, pred)
 521     });
 522
 523     let mut predicates = predicates.instantiate_identity(fcx.tcx);
 524
 525     if let Some(return_ty) = return_ty {
 526         predicates.predicates.extend(check_existential_types(tcx, fcx, def_id, span, return_ty));
 527     }
 528
 529     let predicates = fcx.normalize_associated_types_in(span, &predicates);
 530
 531     debug!("check_where_clauses: predicates={:?}", predicates.predicates);
 532     let wf_obligations =
 533         predicates.predicates
 534                     .iter()
 535                     .flat_map(|p| ty::wf::predicate_obligations(fcx,
 536                                                                 fcx.param_env,
 537                                                                 fcx.body_id,
 538                                                                 p,
 539                                                                 span));
 540
 541     for obligation in wf_obligations.chain(default_obligations) {
 542         debug!("next obligation cause: {:?}", obligation.cause);
 543         fcx.register_predicate(obligation);
 544     }
 545 }
 546
 547 fn check_fn_or_method<'a, 'fcx, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
 548                                             fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
 549                                             span: Span,
 550                                             sig: ty::PolyFnSig<'tcx>,
 551                                             def_id: DefId,
 552                                             implied_bounds: &mut Vec<Ty<'tcx>>)
 553 {
 554     let sig = fcx.normalize_associated_types_in(span, &sig);
 555     let sig = fcx.tcx.liberate_late_bound_regions(def_id, &sig);
 556
 557     for input_ty in sig.inputs() {
 558         fcx.register_wf_obligation(&input_ty, span, ObligationCauseCode::MiscObligation);
 559     }
 560     implied_bounds.extend(sig.inputs());
 561
 562     fcx.register_wf_obligation(sig.output(), span, ObligationCauseCode::MiscObligation);
 563
 564     // FIXME(#25759) return types should not be implied bounds
 565     implied_bounds.push(sig.output());
 566
 567     check_where_clauses(tcx, fcx, span, def_id, Some(sig.output()));
 568 }
 569
 570 /// Checks "defining uses" of existential types to ensure that they meet the restrictions laid for
 571 /// "higher-order pattern unification".
 572 /// This ensures that inference is tractable.
 573 /// In particular, definitions of existential types can only use other generics as arguments,
 574 /// and they cannot repeat an argument. Example:
 575 ///
 576 /// ```rust
 577 /// existential type Foo<A, B>;
 578 ///
 579 /// // ok -- `Foo` is applied to two distinct, generic types.
 580 /// fn a<T, U>() -> Foo<T, U> { .. }
 581 ///
 582 /// // not ok -- `Foo` is applied to `T` twice.
 583 /// fn b<T>() -> Foo<T, T> { .. }
 584 ///
 585 ///
 586 /// // not ok -- `Foo` is applied to a non-generic type.
 587 /// fn b<T>() -> Foo<T, u32> { .. }
 588 /// ```
 589 ///
 590 fn check_existential_types<'a, 'fcx, 'gcx, 'tcx>(
 591     tcx: TyCtxt<'a, 'gcx, 'gcx>,
 592     fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
 593     fn_def_id: DefId,
 594     span: Span,
 595     ty: Ty<'tcx>,
 596 ) -> Vec<ty::Predicate<'tcx>> {
 597     trace!("check_existential_types: {:?}, {:?}", ty, ty.sty);
 598     let mut substituted_predicates = Vec::new();
 599     ty.fold_with(&mut ty::fold::BottomUpFolder {
 600         tcx: fcx.tcx,
 601         fldop: |ty| {
 602             if let ty::Opaque(def_id, substs) = ty.sty {
 603                 trace!("check_existential_types: opaque_ty, {:?}, {:?}", def_id, substs);
 604                 let generics = tcx.generics_of(def_id);
 605                 // only check named existential types
 606                 if generics.parent.is_none() {
 607                     let opaque_node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 608                     if may_define_existential_type(tcx, fn_def_id, opaque_node_id) {
 609                         trace!("check_existential_types may define. Generics: {:#?}", generics);
 610                         let mut seen: FxHashMap<_, Vec<_>> = FxHashMap::default();
 611                         for (subst, param) in substs.iter().zip(&generics.params) {
 612                             match subst.unpack() {
 613                                 ty::subst::UnpackedKind::Type(ty) => match ty.sty {
 614                                     ty::Param(..) => {},
 615                                     // prevent `fn foo() -> Foo<u32>` from being defining
 616                                     _ => {
 617                                         tcx
 618                                             .sess
 619                                             .struct_span_err(
 620                                                 span,
 621                                                 "non-defining existential type use \
 622                                                  in defining scope",
 623                                             )
 624                                             .span_note(
 625                                                 tcx.def_span(param.def_id),
 626                                                 &format!(
 627                                                     "used non-generic type {} for \
 628                                                      generic parameter",
 629                                                     ty,
 630                                                 ),
 631                                             )
 632                                             .emit();
 633                                     },
 634                                 }, // match ty
 635                                 ty::subst::UnpackedKind::Lifetime(region) => {
 636                                     let param_span = tcx.def_span(param.def_id);
 637                                     if let ty::ReStatic = region {
 638                                         tcx
 639                                             .sess
 640                                             .struct_span_err(
 641                                                 span,
 642                                                 "non-defining existential type use \
 643                                                     in defining scope",
 644                                             )
 645                                             .span_label(
 646                                                 param_span,
 647                                                 "cannot use static lifetime, use a bound lifetime \
 648                                                 instead or remove the lifetime parameter from the \
 649                                                 existential type",
 650                                             )
 651                                             .emit();
 652                                     } else {
 653                                         seen.entry(region).or_default().push(param_span);
 654                                     }
 655                                 },
 656                             } // match subst
 657                         } // for (subst, param)
 658                         for (_, spans) in seen {
 659                             if spans.len() > 1 {
 660                                 tcx
 661                                     .sess
 662                                     .struct_span_err(
 663                                         span,
 664                                         "non-defining existential type use \
 665                                             in defining scope",
 666                                     ).
 667                                     span_note(
 668                                         spans,
 669                                         "lifetime used multiple times",
 670                                     )
 671                                     .emit();
 672                             }
 673                         }
 674                     } // if may_define_existential_type
 675
 676                     // now register the bounds on the parameters of the existential type
 677                     // so the parameters given by the function need to fulfill them
 678                     // ```rust
 679                     // existential type Foo<T: Bar>: 'static;
 680                     // fn foo<U>() -> Foo<U> { .. *}
 681                     // ```
 682                     // becomes
 683                     // ```rust
 684                     // existential type Foo<T: Bar>: 'static;
 685                     // fn foo<U: Bar>() -> Foo<U> { .. *}
 686                     // ```
 687                     let predicates = tcx.predicates_of(def_id);
 688                     trace!(
 689                         "check_existential_types may define. adding predicates: {:#?}",
 690                         predicates,
 691                     );
 692                     for &(pred, _) in predicates.predicates.iter() {
 693                         let substituted_pred = pred.subst(fcx.tcx, substs);
 694                         // Avoid duplication of predicates that contain no parameters, for example.
 695                         if !predicates.predicates.iter().any(|&(p, _)| p == substituted_pred) {
 696                             substituted_predicates.push(substituted_pred);
 697                         }
 698                     }
 699                 } // if is_named_existential_type
 700             } // if let Opaque
 701             ty
 702         },
 703         reg_op: |reg| reg,
 704     });
 705     substituted_predicates
 706 }
 707
 708 fn check_method_receiver<'fcx, 'gcx, 'tcx>(fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
 709                                            method_sig: &hir::MethodSig,
 710                                            method: &ty::AssociatedItem,
 711                                            self_ty: Ty<'tcx>)
 712 {
 713     // check that the method has a valid receiver type, given the type `Self`
 714     debug!("check_method_receiver({:?}, self_ty={:?})",
 715            method, self_ty);
 716
 717     if !method.method_has_self_argument {
 718         return;
 719     }
 720
 721     let span = method_sig.decl.inputs[0].span;
 722
 723     let sig = fcx.tcx.fn_sig(method.def_id);
 724     let sig = fcx.normalize_associated_types_in(span, &sig);
 725     let sig = fcx.tcx.liberate_late_bound_regions(method.def_id, &sig);
 726
 727     debug!("check_method_receiver: sig={:?}", sig);
 728
 729     let self_ty = fcx.normalize_associated_types_in(span, &self_ty);
 730     let self_ty = fcx.tcx.liberate_late_bound_regions(
 731         method.def_id,
 732         &ty::Binder::bind(self_ty)
 733     );
 734
 735     let self_arg_ty = sig.inputs()[0];
 736
 737     let cause = fcx.cause(span, ObligationCauseCode::MethodReceiver);
 738     let self_arg_ty = fcx.normalize_associated_types_in(span, &self_arg_ty);
 739     let self_arg_ty = fcx.tcx.liberate_late_bound_regions(
 740         method.def_id,
 741         &ty::Binder::bind(self_arg_ty)
 742     );
 743
 744     let mut autoderef = fcx.autoderef(span, self_arg_ty).include_raw_pointers();
 745
 746     loop {
 747         if let Some((potential_self_ty, _)) = autoderef.next() {
 748             debug!("check_method_receiver: potential self type `{:?}` to match `{:?}`",
 749                 potential_self_ty, self_ty);
 750
 751             if fcx.infcx.can_eq(fcx.param_env, self_ty, potential_self_ty).is_ok() {
 752                 autoderef.finalize();
 753                 if let Some(mut err) = fcx.demand_eqtype_with_origin(
 754                     &cause, self_ty, potential_self_ty) {
 755                     err.emit();
 756                 }
 757                 break
 758             }
 759         } else {
 760             fcx.tcx.sess.diagnostic().mut_span_err(
 761                 span, &format!("invalid `self` type: {:?}", self_arg_ty))
 762             .note(&format!("type must be `{:?}` or a type that dereferences to it", self_ty))
 763             .help("consider changing to `self`, `&self`, `&mut self`, or `self: Box<Self>`")
 764             .code(DiagnosticId::Error("E0307".into()))
 765             .emit();
 766             return
 767         }
 768     }
 769
 770     let is_self_ty = |ty| fcx.infcx.can_eq(fcx.param_env, self_ty, ty).is_ok();
 771     let self_kind = ExplicitSelf::determine(self_arg_ty, is_self_ty);
 772
 773     if !fcx.tcx.features().arbitrary_self_types {
 774         match self_kind {
 775             ExplicitSelf::ByValue |
 776             ExplicitSelf::ByReference(_, _) |
 777             ExplicitSelf::ByBox => (),
 778
 779             ExplicitSelf::ByRawPointer(_) => {
 780                 feature_gate::feature_err(
 781                     &fcx.tcx.sess.parse_sess,
 782                     "arbitrary_self_types",
 783                     span,
 784                     GateIssue::Language,
 785                     "raw pointer `self` is unstable")
 786                 .help("consider changing to `self`, `&self`, `&mut self`, or `self: Box<Self>`")
 787                 .emit();
 788             }
 789
 790             ExplicitSelf::Other => {
 791                 feature_gate::feature_err(
 792                     &fcx.tcx.sess.parse_sess,
 793                     "arbitrary_self_types",
 794                     span,
 795                     GateIssue::Language,"arbitrary `self` types are unstable")
 796                 .help("consider changing to `self`, `&self`, `&mut self`, or `self: Box<Self>`")
 797                 .emit();
 798             }
 799         }
 800     }
 801 }
 802
 803 fn check_variances_for_type_defn<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 804                                            item: &hir::Item,
 805                                            hir_generics: &hir::Generics)
 806 {
 807     let item_def_id = tcx.hir.local_def_id(item.id);
 808     let ty = tcx.type_of(item_def_id);
 809     if tcx.has_error_field(ty) {
 810         return;
 811     }
 812
 813     let ty_predicates = tcx.predicates_of(item_def_id);
 814     assert_eq!(ty_predicates.parent, None);
 815     let variances = tcx.variances_of(item_def_id);
 816
 817     let mut constrained_parameters: FxHashSet<_> =
 818         variances.iter().enumerate()
 819                         .filter(|&(_, &variance)| variance != ty::Bivariant)
 820                         .map(|(index, _)| Parameter(index as u32))
 821                         .collect();
 822
 823     identify_constrained_type_params(tcx,
 824                                      &ty_predicates,
 825                                      None,
 826                                      &mut constrained_parameters);
 827
 828     for (index, _) in variances.iter().enumerate() {
 829         if constrained_parameters.contains(&Parameter(index as u32)) {
 830             continue;
 831         }
 832
 833         let param = &hir_generics.params[index];
 834         match param.name {
 835             hir::ParamName::Error => { }
 836             _ => report_bivariance(tcx, param.span, param.name.ident().name),
 837         }
 838     }
 839 }
 840
 841 fn report_bivariance<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 842                                span: Span,
 843                                param_name: ast::Name)
 844 {
 845     let mut err = error_392(tcx, span, param_name);
 846
 847     let suggested_marker_id = tcx.lang_items().phantom_data();
 848     // help is available only in presence of lang items
 849     if let Some(def_id) = suggested_marker_id {
 850         err.help(&format!("consider removing `{}` or using a marker such as `{}`",
 851                           param_name,
 852                           tcx.item_path_str(def_id)));
 853     }
 854     err.emit();
 855 }
 856
 857 fn reject_shadowing_parameters(tcx: TyCtxt, def_id: DefId) {
 858     let generics = tcx.generics_of(def_id);
 859     let parent = tcx.generics_of(generics.parent.unwrap());
 860     let impl_params: FxHashMap<_, _> = parent.params.iter().flat_map(|param| match param.kind {
 861         GenericParamDefKind::Lifetime => None,
 862         GenericParamDefKind::Type {..} => Some((param.name, param.def_id)),
 863     }).collect();
 864
 865     for method_param in &generics.params {
 866         // Shadowing is checked in resolve_lifetime.
 867         if let GenericParamDefKind::Lifetime = method_param.kind {
 868             continue
 869         }
 870         if impl_params.contains_key(&method_param.name) {
 871             // Tighten up the span to focus on only the shadowing type
 872             let type_span = tcx.def_span(method_param.def_id);
 873
 874             // The expectation here is that the original trait declaration is
 875             // local so it should be okay to just unwrap everything.
 876             let trait_def_id = impl_params[&method_param.name];
 877             let trait_decl_span = tcx.def_span(trait_def_id);
 878             error_194(tcx, type_span, trait_decl_span, &method_param.name.as_str()[..]);
 879         }
 880     }
 881 }
 882
 883 /// Feature gates RFC 2056 - trivial bounds, checking for global bounds that
 884 /// aren't true.
 885 fn check_false_global_bounds<'a, 'gcx, 'tcx>(
 886     fcx: &FnCtxt<'a, 'gcx, 'tcx>,
 887     span: Span,
 888     id: ast::NodeId)
 889 {
 890     use rustc::ty::TypeFoldable;
 891
 892     let empty_env = ty::ParamEnv::empty();
 893
 894     let def_id = fcx.tcx.hir.local_def_id(id);
 895     let predicates = fcx.tcx.predicates_of(def_id).predicates
 896         .into_iter()
 897         .map(|(p, _)| p)
 898         .collect();
 899     // Check elaborated bounds
 900     let implied_obligations = traits::elaborate_predicates(fcx.tcx, predicates);
 901
 902     for pred in implied_obligations {
 903         // Match the existing behavior.
 904         if pred.is_global() && !pred.has_late_bound_regions() {
 905             let pred = fcx.normalize_associated_types_in(span, &pred);
 906             let obligation = traits::Obligation::new(
 907                 traits::ObligationCause::new(
 908                     span,
 909                     id,
 910                     traits::TrivialBound,
 911                 ),
 912                 empty_env,
 913                 pred,
 914             );
 915             fcx.register_predicate(obligation);
 916         }
 917     }
 918
 919     fcx.select_all_obligations_or_error();
 920 }
 921
 922 pub struct CheckTypeWellFormedVisitor<'a, 'tcx: 'a> {
 923     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 924 }
 925
 926 impl<'a, 'gcx> CheckTypeWellFormedVisitor<'a, 'gcx> {
 927     pub fn new(tcx: TyCtxt<'a, 'gcx, 'gcx>)
 928                -> CheckTypeWellFormedVisitor<'a, 'gcx> {
 929         CheckTypeWellFormedVisitor {
 930             tcx,
 931         }
 932     }
 933 }
 934
 935 impl<'a, 'tcx, 'v> Visitor<'v> for CheckTypeWellFormedVisitor<'a, 'tcx> {
 936     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
 937         NestedVisitorMap::None
 938     }
 939
 940     fn visit_item(&mut self, i: &hir::Item) {
 941         debug!("visit_item: {:?}", i);
 942         let def_id = self.tcx.hir.local_def_id(i.id);
 943         ty::query::queries::check_item_well_formed::ensure(self.tcx, def_id);
 944         intravisit::walk_item(self, i);
 945     }
 946
 947     fn visit_trait_item(&mut self, trait_item: &'v hir::TraitItem) {
 948         debug!("visit_trait_item: {:?}", trait_item);
 949         let def_id = self.tcx.hir.local_def_id(trait_item.id);
 950         ty::query::queries::check_trait_item_well_formed::ensure(self.tcx, def_id);
 951         intravisit::walk_trait_item(self, trait_item)
 952     }
 953
 954     fn visit_impl_item(&mut self, impl_item: &'v hir::ImplItem) {
 955         debug!("visit_impl_item: {:?}", impl_item);
 956         let def_id = self.tcx.hir.local_def_id(impl_item.id);
 957         ty::query::queries::check_impl_item_well_formed::ensure(self.tcx, def_id);
 958         intravisit::walk_impl_item(self, impl_item)
 959     }
 960 }
 961
 962 ///////////////////////////////////////////////////////////////////////////
 963 // ADT
 964
 965 struct AdtVariant<'tcx> {
 966     fields: Vec<AdtField<'tcx>>,
 967 }
 968
 969 struct AdtField<'tcx> {
 970     ty: Ty<'tcx>,
 971     span: Span,
 972 }
 973
 974 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 975     fn non_enum_variant(&self, struct_def: &hir::VariantData) -> AdtVariant<'tcx> {
 976         let fields = struct_def.fields().iter().map(|field| {
 977             let field_ty = self.tcx.type_of(self.tcx.hir.local_def_id(field.id));
 978             let field_ty = self.normalize_associated_types_in(field.span,
 979                                                               &field_ty);
 980             AdtField { ty: field_ty, span: field.span }
 981         })
 982         .collect();
 983         AdtVariant { fields: fields }
 984     }
 985
 986     fn enum_variants(&self, enum_def: &hir::EnumDef) -> Vec<AdtVariant<'tcx>> {
 987         enum_def.variants.iter()
 988             .map(|variant| self.non_enum_variant(&variant.node.data))
 989             .collect()
 990     }
 991
 992     fn impl_implied_bounds(&self, impl_def_id: DefId, span: Span) -> Vec<Ty<'tcx>> {
 993         match self.tcx.impl_trait_ref(impl_def_id) {
 994             Some(ref trait_ref) => {
 995                 // Trait impl: take implied bounds from all types that
 996                 // appear in the trait reference.
 997                 let trait_ref = self.normalize_associated_types_in(span, trait_ref);
 998                 trait_ref.substs.types().collect()
 999             }
1000
1001             None => {
1002                 // Inherent impl: take implied bounds from the self type.
1003                 let self_ty = self.tcx.type_of(impl_def_id);
1004                 let self_ty = self.normalize_associated_types_in(span, &self_ty);
1005                 vec![self_ty]
1006             }
1007         }
1008     }
1009 }
1010
1011 fn error_392<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, span: Span, param_name: ast::Name)
1012                        -> DiagnosticBuilder<'tcx> {
1013     let mut err = struct_span_err!(tcx.sess, span, E0392,
1014                   "parameter `{}` is never used", param_name);
1015     err.span_label(span, "unused type parameter");
1016     err
1017 }
1018
1019 fn error_194(tcx: TyCtxt, span: Span, trait_decl_span: Span, name: &str) {
1020     struct_span_err!(tcx.sess, span, E0194,
1021                      "type parameter `{}` shadows another type parameter of the same name",
1022                      name)
1023         .span_label(span, "shadows another type parameter")
1024         .span_label(trait_decl_span, format!("first `{}` declared here", name))
1025         .emit();
1026 }