src/librustc_typeck/collect.rs

   1 // Copyright 2012-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 //! "Collection" is the process of determining the type and other external
  12 //! details of each item in Rust. Collection is specifically concerned
  13 //! with *interprocedural* things -- for example, for a function
  14 //! definition, collection will figure out the type and signature of the
  15 //! function, but it will not visit the *body* of the function in any way,
  16 //! nor examine type annotations on local variables (that's the job of
  17 //! type *checking*).
  18 //!
  19 //! Collecting is ultimately defined by a bundle of queries that
  20 //! inquire after various facts about the items in the crate (e.g.,
  21 //! `type_of`, `generics_of`, `predicates_of`, etc). See the `provide` function
  22 //! for the full set.
  23 //!
  24 //! At present, however, we do run collection across all items in the
  25 //! crate as a kind of pass. This should eventually be factored away.
  26
  27 use astconv::{AstConv, Bounds};
  28 use constrained_type_params as ctp;
  29 use lint;
  30 use middle::lang_items::SizedTraitLangItem;
  31 use middle::resolve_lifetime as rl;
  32 use middle::weak_lang_items;
  33 use rustc::mir::mono::Linkage;
  34 use rustc::ty::query::Providers;
  35 use rustc::ty::subst::Substs;
  36 use rustc::ty::util::Discr;
  37 use rustc::ty::util::IntTypeExt;
  38 use rustc::ty::{self, AdtKind, ToPolyTraitRef, Ty, TyCtxt};
  39 use rustc::ty::{ReprOptions, ToPredicate};
  40 use rustc::util::captures::Captures;
  41 use rustc::util::nodemap::FxHashMap;
  42 use rustc_target::spec::abi;
  43
  44 use syntax::ast;
  45 use syntax::ast::MetaItemKind;
  46 use syntax::attr::{InlineAttr, list_contains_name, mark_used};
  47 use syntax::source_map::Spanned;
  48 use syntax::feature_gate;
  49 use syntax::symbol::{keywords, Symbol};
  50 use syntax_pos::{Span, DUMMY_SP};
  51
  52 use rustc::hir::def::{CtorKind, Def};
  53 use rustc::hir::Node;
  54 use rustc::hir::def_id::{DefId, LOCAL_CRATE};
  55 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
  56 use rustc::hir::GenericParamKind;
  57 use rustc::hir::{self, CodegenFnAttrFlags, CodegenFnAttrs, Unsafety};
  58
  59 ///////////////////////////////////////////////////////////////////////////
  60 // Main entry point
  61
  62 pub fn collect_item_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
  63     let mut visitor = CollectItemTypesVisitor { tcx: tcx };
  64     tcx.hir
  65         .krate()
  66         .visit_all_item_likes(&mut visitor.as_deep_visitor());
  67 }
  68
  69 pub fn provide(providers: &mut Providers) {
  70     *providers = Providers {
  71         type_of,
  72         generics_of,
  73         predicates_of,
  74         predicates_defined_on,
  75         explicit_predicates_of,
  76         super_predicates_of,
  77         type_param_predicates,
  78         trait_def,
  79         adt_def,
  80         fn_sig,
  81         impl_trait_ref,
  82         impl_polarity,
  83         is_foreign_item,
  84         codegen_fn_attrs,
  85         ..*providers
  86     };
  87 }
  88
  89 ///////////////////////////////////////////////////////////////////////////
  90
  91 /// Context specific to some particular item. This is what implements
  92 /// AstConv. It has information about the predicates that are defined
  93 /// on the trait. Unfortunately, this predicate information is
  94 /// available in various different forms at various points in the
  95 /// process. So we can't just store a pointer to e.g. the AST or the
  96 /// parsed ty form, we have to be more flexible. To this end, the
  97 /// `ItemCtxt` is parameterized by a `DefId` that it uses to satisfy
  98 /// `get_type_parameter_bounds` requests, drawing the information from
  99 /// the AST (`hir::Generics`), recursively.
 100 pub struct ItemCtxt<'a, 'tcx: 'a> {
 101     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 102     item_def_id: DefId,
 103 }
 104
 105 ///////////////////////////////////////////////////////////////////////////
 106
 107 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
 108     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 109 }
 110
 111 impl<'a, 'tcx> Visitor<'tcx> for CollectItemTypesVisitor<'a, 'tcx> {
 112     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 113         NestedVisitorMap::OnlyBodies(&self.tcx.hir)
 114     }
 115
 116     fn visit_item(&mut self, item: &'tcx hir::Item) {
 117         convert_item(self.tcx, item.id);
 118         intravisit::walk_item(self, item);
 119     }
 120
 121     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 122         for param in &generics.params {
 123             match param.kind {
 124                 hir::GenericParamKind::Lifetime { .. } => {}
 125                 hir::GenericParamKind::Type {
 126                     default: Some(_), ..
 127                 } => {
 128                     let def_id = self.tcx.hir.local_def_id(param.id);
 129                     self.tcx.type_of(def_id);
 130                 }
 131                 hir::GenericParamKind::Type { .. } => {}
 132             }
 133         }
 134         intravisit::walk_generics(self, generics);
 135     }
 136
 137     fn visit_expr(&mut self, expr: &'tcx hir::Expr) {
 138         if let hir::ExprKind::Closure(..) = expr.node {
 139             let def_id = self.tcx.hir.local_def_id(expr.id);
 140             self.tcx.generics_of(def_id);
 141             self.tcx.type_of(def_id);
 142         }
 143         intravisit::walk_expr(self, expr);
 144     }
 145
 146     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 147         convert_trait_item(self.tcx, trait_item.id);
 148         intravisit::walk_trait_item(self, trait_item);
 149     }
 150
 151     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 152         convert_impl_item(self.tcx, impl_item.id);
 153         intravisit::walk_impl_item(self, impl_item);
 154     }
 155 }
 156
 157 ///////////////////////////////////////////////////////////////////////////
 158 // Utility types and common code for the above passes.
 159
 160 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 161     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId) -> ItemCtxt<'a, 'tcx> {
 162         ItemCtxt { tcx, item_def_id }
 163     }
 164 }
 165
 166 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 167     pub fn to_ty(&self, ast_ty: &hir::Ty) -> Ty<'tcx> {
 168         AstConv::ast_ty_to_ty(self, ast_ty)
 169     }
 170 }
 171
 172 impl<'a, 'tcx> AstConv<'tcx, 'tcx> for ItemCtxt<'a, 'tcx> {
 173     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> {
 174         self.tcx
 175     }
 176
 177     fn get_type_parameter_bounds(&self, span: Span, def_id: DefId) -> ty::GenericPredicates<'tcx> {
 178         self.tcx
 179             .at(span)
 180             .type_param_predicates((self.item_def_id, def_id))
 181     }
 182
 183     fn re_infer(
 184         &self,
 185         _span: Span,
 186         _def: Option<&ty::GenericParamDef>,
 187     ) -> Option<ty::Region<'tcx>> {
 188         None
 189     }
 190
 191     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
 192         struct_span_err!(
 193             self.tcx().sess,
 194             span,
 195             E0121,
 196             "the type placeholder `_` is not allowed within types on item signatures"
 197         ).span_label(span, "not allowed in type signatures")
 198             .emit();
 199         self.tcx().types.err
 200     }
 201
 202     fn projected_ty_from_poly_trait_ref(
 203         &self,
 204         span: Span,
 205         item_def_id: DefId,
 206         poly_trait_ref: ty::PolyTraitRef<'tcx>,
 207     ) -> Ty<'tcx> {
 208         if let Some(trait_ref) = poly_trait_ref.no_late_bound_regions() {
 209             self.tcx().mk_projection(item_def_id, trait_ref.substs)
 210         } else {
 211             // no late-bound regions, we can just ignore the binder
 212             span_err!(
 213                 self.tcx().sess,
 214                 span,
 215                 E0212,
 216                 "cannot extract an associated type from a higher-ranked trait bound \
 217                  in this context"
 218             );
 219             self.tcx().types.err
 220         }
 221     }
 222
 223     fn normalize_ty(&self, _span: Span, ty: Ty<'tcx>) -> Ty<'tcx> {
 224         // types in item signatures are not normalized, to avoid undue
 225         // dependencies.
 226         ty
 227     }
 228
 229     fn set_tainted_by_errors(&self) {
 230         // no obvious place to track this, just let it go
 231     }
 232
 233     fn record_ty(&self, _hir_id: hir::HirId, _ty: Ty<'tcx>, _span: Span) {
 234         // no place to record types from signatures?
 235     }
 236 }
 237
 238 fn type_param_predicates<'a, 'tcx>(
 239     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 240     (item_def_id, def_id): (DefId, DefId),
 241 ) -> ty::GenericPredicates<'tcx> {
 242     use rustc::hir::*;
 243
 244     // In the AST, bounds can derive from two places. Either
 245     // written inline like `<T:Foo>` or in a where clause like
 246     // `where T:Foo`.
 247
 248     let param_id = tcx.hir.as_local_node_id(def_id).unwrap();
 249     let param_owner = tcx.hir.ty_param_owner(param_id);
 250     let param_owner_def_id = tcx.hir.local_def_id(param_owner);
 251     let generics = tcx.generics_of(param_owner_def_id);
 252     let index = generics.param_def_id_to_index[&def_id];
 253     let ty = tcx.mk_ty_param(index, tcx.hir.ty_param_name(param_id).as_interned_str());
 254
 255     // Don't look for bounds where the type parameter isn't in scope.
 256     let parent = if item_def_id == param_owner_def_id {
 257         None
 258     } else {
 259         tcx.generics_of(item_def_id).parent
 260     };
 261
 262     let mut result = parent.map_or(
 263         ty::GenericPredicates {
 264             parent: None,
 265             predicates: vec![],
 266         },
 267         |parent| {
 268             let icx = ItemCtxt::new(tcx, parent);
 269             icx.get_type_parameter_bounds(DUMMY_SP, def_id)
 270         },
 271     );
 272
 273     let item_node_id = tcx.hir.as_local_node_id(item_def_id).unwrap();
 274     let ast_generics = match tcx.hir.get(item_node_id) {
 275         Node::TraitItem(item) => &item.generics,
 276
 277         Node::ImplItem(item) => &item.generics,
 278
 279         Node::Item(item) => {
 280             match item.node {
 281                 ItemKind::Fn(.., ref generics, _)
 282                 | ItemKind::Impl(_, _, _, ref generics, ..)
 283                 | ItemKind::Ty(_, ref generics)
 284                 | ItemKind::Existential(ExistTy {
 285                     ref generics,
 286                     impl_trait_fn: None,
 287                     ..
 288                 })
 289                 | ItemKind::Enum(_, ref generics)
 290                 | ItemKind::Struct(_, ref generics)
 291                 | ItemKind::Union(_, ref generics) => generics,
 292                 ItemKind::Trait(_, _, ref generics, ..) => {
 293                     // Implied `Self: Trait` and supertrait bounds.
 294                     if param_id == item_node_id {
 295                         result
 296                             .predicates
 297                             .push(ty::TraitRef::identity(tcx, item_def_id).to_predicate());
 298                     }
 299                     generics
 300                 }
 301                 _ => return result,
 302             }
 303         }
 304
 305         Node::ForeignItem(item) => match item.node {
 306             ForeignItemKind::Fn(_, _, ref generics) => generics,
 307             _ => return result,
 308         },
 309
 310         _ => return result,
 311     };
 312
 313     let icx = ItemCtxt::new(tcx, item_def_id);
 314     result
 315         .predicates
 316         .extend(icx.type_parameter_bounds_in_generics(ast_generics, param_id, ty));
 317     result
 318 }
 319
 320 impl<'a, 'tcx> ItemCtxt<'a, 'tcx> {
 321     /// Find bounds from hir::Generics. This requires scanning through the
 322     /// AST. We do this to avoid having to convert *all* the bounds, which
 323     /// would create artificial cycles. Instead we can only convert the
 324     /// bounds for a type parameter `X` if `X::Foo` is used.
 325     fn type_parameter_bounds_in_generics(
 326         &self,
 327         ast_generics: &hir::Generics,
 328         param_id: ast::NodeId,
 329         ty: Ty<'tcx>,
 330     ) -> Vec<ty::Predicate<'tcx>> {
 331         let from_ty_params = ast_generics
 332             .params
 333             .iter()
 334             .filter_map(|param| match param.kind {
 335                 GenericParamKind::Type { .. } if param.id == param_id => Some(&param.bounds),
 336                 _ => None,
 337             })
 338             .flat_map(|bounds| bounds.iter())
 339             .flat_map(|b| predicates_from_bound(self, ty, b));
 340
 341         let from_where_clauses = ast_generics
 342             .where_clause
 343             .predicates
 344             .iter()
 345             .filter_map(|wp| match *wp {
 346                 hir::WherePredicate::BoundPredicate(ref bp) => Some(bp),
 347                 _ => None,
 348             })
 349             .filter(|bp| is_param(self.tcx, &bp.bounded_ty, param_id))
 350             .flat_map(|bp| bp.bounds.iter())
 351             .flat_map(|b| predicates_from_bound(self, ty, b));
 352
 353         from_ty_params.chain(from_where_clauses).collect()
 354     }
 355 }
 356
 357 /// Tests whether this is the AST for a reference to the type
 358 /// parameter with id `param_id`. We use this so as to avoid running
 359 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
 360 /// conversion of the type to avoid inducing unnecessary cycles.
 361 fn is_param<'a, 'tcx>(
 362     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 363     ast_ty: &hir::Ty,
 364     param_id: ast::NodeId,
 365 ) -> bool {
 366     if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) = ast_ty.node {
 367         match path.def {
 368             Def::SelfTy(Some(def_id), None) | Def::TyParam(def_id) => {
 369                 def_id == tcx.hir.local_def_id(param_id)
 370             }
 371             _ => false,
 372         }
 373     } else {
 374         false
 375     }
 376 }
 377
 378 fn convert_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_id: ast::NodeId) {
 379     let it = tcx.hir.expect_item(item_id);
 380     debug!("convert: item {} with id {}", it.name, it.id);
 381     let def_id = tcx.hir.local_def_id(item_id);
 382     match it.node {
 383         // These don't define types.
 384         hir::ItemKind::ExternCrate(_)
 385         | hir::ItemKind::Use(..)
 386         | hir::ItemKind::Mod(_)
 387         | hir::ItemKind::GlobalAsm(_) => {}
 388         hir::ItemKind::ForeignMod(ref foreign_mod) => {
 389             for item in &foreign_mod.items {
 390                 let def_id = tcx.hir.local_def_id(item.id);
 391                 tcx.generics_of(def_id);
 392                 tcx.type_of(def_id);
 393                 tcx.predicates_of(def_id);
 394                 if let hir::ForeignItemKind::Fn(..) = item.node {
 395                     tcx.fn_sig(def_id);
 396                 }
 397             }
 398         }
 399         hir::ItemKind::Enum(ref enum_definition, _) => {
 400             tcx.generics_of(def_id);
 401             tcx.type_of(def_id);
 402             tcx.predicates_of(def_id);
 403             convert_enum_variant_types(tcx, def_id, &enum_definition.variants);
 404         }
 405         hir::ItemKind::Impl(..) => {
 406             tcx.generics_of(def_id);
 407             tcx.type_of(def_id);
 408             tcx.impl_trait_ref(def_id);
 409             tcx.predicates_of(def_id);
 410         }
 411         hir::ItemKind::Trait(..) => {
 412             tcx.generics_of(def_id);
 413             tcx.trait_def(def_id);
 414             tcx.at(it.span).super_predicates_of(def_id);
 415             tcx.predicates_of(def_id);
 416         }
 417         hir::ItemKind::TraitAlias(..) => {
 418             span_err!(
 419                 tcx.sess,
 420                 it.span,
 421                 E0645,
 422                 "trait aliases are not yet implemented (see issue #41517)"
 423             );
 424         }
 425         hir::ItemKind::Struct(ref struct_def, _) | hir::ItemKind::Union(ref struct_def, _) => {
 426             tcx.generics_of(def_id);
 427             tcx.type_of(def_id);
 428             tcx.predicates_of(def_id);
 429
 430             for f in struct_def.fields() {
 431                 let def_id = tcx.hir.local_def_id(f.id);
 432                 tcx.generics_of(def_id);
 433                 tcx.type_of(def_id);
 434                 tcx.predicates_of(def_id);
 435             }
 436
 437             if !struct_def.is_struct() {
 438                 convert_variant_ctor(tcx, struct_def.id());
 439             }
 440         }
 441
 442         // Desugared from `impl Trait` -> visited by the function's return type
 443         hir::ItemKind::Existential(hir::ExistTy {
 444             impl_trait_fn: Some(_),
 445             ..
 446         }) => {}
 447
 448         hir::ItemKind::Existential(..)
 449         | hir::ItemKind::Ty(..)
 450         | hir::ItemKind::Static(..)
 451         | hir::ItemKind::Const(..)
 452         | hir::ItemKind::Fn(..) => {
 453             tcx.generics_of(def_id);
 454             tcx.type_of(def_id);
 455             tcx.predicates_of(def_id);
 456             if let hir::ItemKind::Fn(..) = it.node {
 457                 tcx.fn_sig(def_id);
 458             }
 459         }
 460     }
 461 }
 462
 463 fn convert_trait_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, trait_item_id: ast::NodeId) {
 464     let trait_item = tcx.hir.expect_trait_item(trait_item_id);
 465     let def_id = tcx.hir.local_def_id(trait_item.id);
 466     tcx.generics_of(def_id);
 467
 468     match trait_item.node {
 469         hir::TraitItemKind::Const(..)
 470         | hir::TraitItemKind::Type(_, Some(_))
 471         | hir::TraitItemKind::Method(..) => {
 472             tcx.type_of(def_id);
 473             if let hir::TraitItemKind::Method(..) = trait_item.node {
 474                 tcx.fn_sig(def_id);
 475             }
 476         }
 477
 478         hir::TraitItemKind::Type(_, None) => {}
 479     };
 480
 481     tcx.predicates_of(def_id);
 482 }
 483
 484 fn convert_impl_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_item_id: ast::NodeId) {
 485     let def_id = tcx.hir.local_def_id(impl_item_id);
 486     tcx.generics_of(def_id);
 487     tcx.type_of(def_id);
 488     tcx.predicates_of(def_id);
 489     if let hir::ImplItemKind::Method(..) = tcx.hir.expect_impl_item(impl_item_id).node {
 490         tcx.fn_sig(def_id);
 491     }
 492 }
 493
 494 fn convert_variant_ctor<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, ctor_id: ast::NodeId) {
 495     let def_id = tcx.hir.local_def_id(ctor_id);
 496     tcx.generics_of(def_id);
 497     tcx.type_of(def_id);
 498     tcx.predicates_of(def_id);
 499 }
 500
 501 fn convert_enum_variant_types<'a, 'tcx>(
 502     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 503     def_id: DefId,
 504     variants: &[hir::Variant],
 505 ) {
 506     let def = tcx.adt_def(def_id);
 507     let repr_type = def.repr.discr_type();
 508     let initial = repr_type.initial_discriminant(tcx);
 509     let mut prev_discr = None::<Discr<'tcx>>;
 510
 511     // fill the discriminant values and field types
 512     for variant in variants {
 513         let wrapped_discr = prev_discr.map_or(initial, |d| d.wrap_incr(tcx));
 514         prev_discr = Some(
 515             if let Some(ref e) = variant.node.disr_expr {
 516                 let expr_did = tcx.hir.local_def_id(e.id);
 517                 def.eval_explicit_discr(tcx, expr_did)
 518             } else if let Some(discr) = repr_type.disr_incr(tcx, prev_discr) {
 519                 Some(discr)
 520             } else {
 521                 struct_span_err!(
 522                     tcx.sess,
 523                     variant.span,
 524                     E0370,
 525                     "enum discriminant overflowed"
 526                 ).span_label(
 527                     variant.span,
 528                     format!("overflowed on value after {}", prev_discr.unwrap()),
 529                 )
 530                     .note(&format!(
 531                         "explicitly set `{} = {}` if that is desired outcome",
 532                         variant.node.name, wrapped_discr
 533                     ))
 534                     .emit();
 535                 None
 536             }.unwrap_or(wrapped_discr),
 537         );
 538
 539         for f in variant.node.data.fields() {
 540             let def_id = tcx.hir.local_def_id(f.id);
 541             tcx.generics_of(def_id);
 542             tcx.type_of(def_id);
 543             tcx.predicates_of(def_id);
 544         }
 545
 546         // Convert the ctor, if any. This also registers the variant as
 547         // an item.
 548         convert_variant_ctor(tcx, variant.node.data.id());
 549     }
 550 }
 551
 552 fn convert_variant<'a, 'tcx>(
 553     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 554     did: DefId,
 555     name: ast::Name,
 556     discr: ty::VariantDiscr,
 557     def: &hir::VariantData,
 558     adt_kind: ty::AdtKind,
 559     attribute_def_id: DefId
 560 ) -> ty::VariantDef {
 561     let mut seen_fields: FxHashMap<ast::Ident, Span> = FxHashMap();
 562     let node_id = tcx.hir.as_local_node_id(did).unwrap();
 563     let fields = def
 564         .fields()
 565         .iter()
 566         .map(|f| {
 567             let fid = tcx.hir.local_def_id(f.id);
 568             let dup_span = seen_fields.get(&f.ident.modern()).cloned();
 569             if let Some(prev_span) = dup_span {
 570                 struct_span_err!(
 571                     tcx.sess,
 572                     f.span,
 573                     E0124,
 574                     "field `{}` is already declared",
 575                     f.ident
 576                 ).span_label(f.span, "field already declared")
 577                     .span_label(prev_span, format!("`{}` first declared here", f.ident))
 578                     .emit();
 579             } else {
 580                 seen_fields.insert(f.ident.modern(), f.span);
 581             }
 582
 583             ty::FieldDef {
 584                 did: fid,
 585                 ident: f.ident,
 586                 vis: ty::Visibility::from_hir(&f.vis, node_id, tcx),
 587             }
 588         })
 589         .collect();
 590     ty::VariantDef::new(tcx,
 591         did,
 592         name,
 593         discr,
 594         fields,
 595         adt_kind,
 596         CtorKind::from_hir(def),
 597         attribute_def_id)
 598 }
 599
 600 fn adt_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> &'tcx ty::AdtDef {
 601     use rustc::hir::*;
 602
 603     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 604     let item = match tcx.hir.get(node_id) {
 605         Node::Item(item) => item,
 606         _ => bug!(),
 607     };
 608
 609     let repr = ReprOptions::new(tcx, def_id);
 610     let (kind, variants) = match item.node {
 611         ItemKind::Enum(ref def, _) => {
 612             let mut distance_from_explicit = 0;
 613             (
 614                 AdtKind::Enum,
 615                 def.variants
 616                     .iter()
 617                     .map(|v| {
 618                         let did = tcx.hir.local_def_id(v.node.data.id());
 619                         let discr = if let Some(ref e) = v.node.disr_expr {
 620                             distance_from_explicit = 0;
 621                             ty::VariantDiscr::Explicit(tcx.hir.local_def_id(e.id))
 622                         } else {
 623                             ty::VariantDiscr::Relative(distance_from_explicit)
 624                         };
 625                         distance_from_explicit += 1;
 626
 627                         convert_variant(tcx, did, v.node.name, discr, &v.node.data, AdtKind::Enum,
 628                                         did)
 629                     })
 630                     .collect(),
 631             )
 632         }
 633         ItemKind::Struct(ref def, _) => {
 634             // Use separate constructor id for unit/tuple structs and reuse did for braced structs.
 635             let ctor_id = if !def.is_struct() {
 636                 Some(tcx.hir.local_def_id(def.id()))
 637             } else {
 638                 None
 639             };
 640             (
 641                 AdtKind::Struct,
 642                 vec![convert_variant(
 643                     tcx,
 644                     ctor_id.unwrap_or(def_id),
 645                     item.name,
 646                     ty::VariantDiscr::Relative(0),
 647                     def,
 648                     AdtKind::Struct,
 649                     def_id
 650                 )],
 651             )
 652         }
 653         ItemKind::Union(ref def, _) => (
 654             AdtKind::Union,
 655             vec![convert_variant(
 656                 tcx,
 657                 def_id,
 658                 item.name,
 659                 ty::VariantDiscr::Relative(0),
 660                 def,
 661                 AdtKind::Union,
 662                 def_id
 663             )],
 664         ),
 665         _ => bug!(),
 666     };
 667     tcx.alloc_adt_def(def_id, kind, variants, repr)
 668 }
 669
 670 /// Ensures that the super-predicates of the trait with def-id
 671 /// trait_def_id are converted and stored. This also ensures that
 672 /// the transitive super-predicates are converted;
 673 fn super_predicates_of<'a, 'tcx>(
 674     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 675     trait_def_id: DefId,
 676 ) -> ty::GenericPredicates<'tcx> {
 677     debug!("super_predicates(trait_def_id={:?})", trait_def_id);
 678     let trait_node_id = tcx.hir.as_local_node_id(trait_def_id).unwrap();
 679
 680     let item = match tcx.hir.get(trait_node_id) {
 681         Node::Item(item) => item,
 682         _ => bug!("trait_node_id {} is not an item", trait_node_id),
 683     };
 684
 685     let (generics, bounds) = match item.node {
 686         hir::ItemKind::Trait(.., ref generics, ref supertraits, _) => (generics, supertraits),
 687         hir::ItemKind::TraitAlias(ref generics, ref supertraits) => (generics, supertraits),
 688         _ => span_bug!(item.span, "super_predicates invoked on non-trait"),
 689     };
 690
 691     let icx = ItemCtxt::new(tcx, trait_def_id);
 692
 693     // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
 694     let self_param_ty = tcx.mk_self_type();
 695     let superbounds1 = compute_bounds(&icx, self_param_ty, bounds, SizedByDefault::No, item.span);
 696
 697     let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
 698
 699     // Convert any explicit superbounds in the where clause,
 700     // e.g. `trait Foo where Self : Bar`:
 701     let superbounds2 = icx.type_parameter_bounds_in_generics(generics, item.id, self_param_ty);
 702
 703     // Combine the two lists to form the complete set of superbounds:
 704     let superbounds: Vec<_> = superbounds1.into_iter().chain(superbounds2).collect();
 705
 706     // Now require that immediate supertraits are converted,
 707     // which will, in turn, reach indirect supertraits.
 708     for bound in superbounds.iter().filter_map(|p| p.to_opt_poly_trait_ref()) {
 709         tcx.at(item.span).super_predicates_of(bound.def_id());
 710     }
 711
 712     ty::GenericPredicates {
 713         parent: None,
 714         predicates: superbounds,
 715     }
 716 }
 717
 718 fn trait_def<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> &'tcx ty::TraitDef {
 719     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 720     let item = tcx.hir.expect_item(node_id);
 721
 722     let (is_auto, unsafety) = match item.node {
 723         hir::ItemKind::Trait(is_auto, unsafety, ..) => (is_auto == hir::IsAuto::Yes, unsafety),
 724         hir::ItemKind::TraitAlias(..) => (false, hir::Unsafety::Normal),
 725         _ => span_bug!(item.span, "trait_def_of_item invoked on non-trait"),
 726     };
 727
 728     let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
 729     if paren_sugar && !tcx.features().unboxed_closures {
 730         let mut err = tcx.sess.struct_span_err(
 731             item.span,
 732             "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
 733              which traits can use parenthetical notation",
 734         );
 735         help!(
 736             &mut err,
 737             "add `#![feature(unboxed_closures)]` to \
 738              the crate attributes to use it"
 739         );
 740         err.emit();
 741     }
 742
 743     let is_marker = tcx.has_attr(def_id, "marker");
 744     let def_path_hash = tcx.def_path_hash(def_id);
 745     let def = ty::TraitDef::new(def_id, unsafety, paren_sugar, is_auto, is_marker, def_path_hash);
 746     tcx.alloc_trait_def(def)
 747 }
 748
 749 fn has_late_bound_regions<'a, 'tcx>(
 750     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 751     node: Node<'tcx>,
 752 ) -> Option<Span> {
 753     struct LateBoundRegionsDetector<'a, 'tcx: 'a> {
 754         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 755         outer_index: ty::DebruijnIndex,
 756         has_late_bound_regions: Option<Span>,
 757     }
 758
 759     impl<'a, 'tcx> Visitor<'tcx> for LateBoundRegionsDetector<'a, 'tcx> {
 760         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 761             NestedVisitorMap::None
 762         }
 763
 764         fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 765             if self.has_late_bound_regions.is_some() {
 766                 return;
 767             }
 768             match ty.node {
 769                 hir::TyKind::BareFn(..) => {
 770                     self.outer_index.shift_in(1);
 771                     intravisit::walk_ty(self, ty);
 772                     self.outer_index.shift_out(1);
 773                 }
 774                 _ => intravisit::walk_ty(self, ty),
 775             }
 776         }
 777
 778         fn visit_poly_trait_ref(
 779             &mut self,
 780             tr: &'tcx hir::PolyTraitRef,
 781             m: hir::TraitBoundModifier,
 782         ) {
 783             if self.has_late_bound_regions.is_some() {
 784                 return;
 785             }
 786             self.outer_index.shift_in(1);
 787             intravisit::walk_poly_trait_ref(self, tr, m);
 788             self.outer_index.shift_out(1);
 789         }
 790
 791         fn visit_lifetime(&mut self, lt: &'tcx hir::Lifetime) {
 792             if self.has_late_bound_regions.is_some() {
 793                 return;
 794             }
 795
 796             let hir_id = self.tcx.hir.node_to_hir_id(lt.id);
 797             match self.tcx.named_region(hir_id) {
 798                 Some(rl::Region::Static) | Some(rl::Region::EarlyBound(..)) => {}
 799                 Some(rl::Region::LateBound(debruijn, _, _))
 800                 | Some(rl::Region::LateBoundAnon(debruijn, _)) if debruijn < self.outer_index => {}
 801                 Some(rl::Region::LateBound(..))
 802                 | Some(rl::Region::LateBoundAnon(..))
 803                 | Some(rl::Region::Free(..))
 804                 | None => {
 805                     self.has_late_bound_regions = Some(lt.span);
 806                 }
 807             }
 808         }
 809     }
 810
 811     fn has_late_bound_regions<'a, 'tcx>(
 812         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 813         generics: &'tcx hir::Generics,
 814         decl: &'tcx hir::FnDecl,
 815     ) -> Option<Span> {
 816         let mut visitor = LateBoundRegionsDetector {
 817             tcx,
 818             outer_index: ty::INNERMOST,
 819             has_late_bound_regions: None,
 820         };
 821         for param in &generics.params {
 822             match param.kind {
 823                 GenericParamKind::Lifetime { .. } => {
 824                     let hir_id = tcx.hir.node_to_hir_id(param.id);
 825                     if tcx.is_late_bound(hir_id) {
 826                         return Some(param.span);
 827                     }
 828                 }
 829                 _ => {}
 830             }
 831         }
 832         visitor.visit_fn_decl(decl);
 833         visitor.has_late_bound_regions
 834     }
 835
 836     match node {
 837         Node::TraitItem(item) => match item.node {
 838             hir::TraitItemKind::Method(ref sig, _) => {
 839                 has_late_bound_regions(tcx, &item.generics, &sig.decl)
 840             }
 841             _ => None,
 842         },
 843         Node::ImplItem(item) => match item.node {
 844             hir::ImplItemKind::Method(ref sig, _) => {
 845                 has_late_bound_regions(tcx, &item.generics, &sig.decl)
 846             }
 847             _ => None,
 848         },
 849         Node::ForeignItem(item) => match item.node {
 850             hir::ForeignItemKind::Fn(ref fn_decl, _, ref generics) => {
 851                 has_late_bound_regions(tcx, generics, fn_decl)
 852             }
 853             _ => None,
 854         },
 855         Node::Item(item) => match item.node {
 856             hir::ItemKind::Fn(ref fn_decl, .., ref generics, _) => {
 857                 has_late_bound_regions(tcx, generics, fn_decl)
 858             }
 859             _ => None,
 860         },
 861         _ => None,
 862     }
 863 }
 864
 865 fn generics_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> &'tcx ty::Generics {
 866     use rustc::hir::*;
 867
 868     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
 869
 870     let node = tcx.hir.get(node_id);
 871     let parent_def_id = match node {
 872         Node::ImplItem(_) | Node::TraitItem(_) | Node::Variant(_)
 873         | Node::StructCtor(_) | Node::Field(_) => {
 874             let parent_id = tcx.hir.get_parent(node_id);
 875             Some(tcx.hir.local_def_id(parent_id))
 876         }
 877         Node::Expr(&hir::Expr {
 878             node: hir::ExprKind::Closure(..),
 879             ..
 880         }) => Some(tcx.closure_base_def_id(def_id)),
 881         Node::Item(item) => match item.node {
 882             ItemKind::Existential(hir::ExistTy { impl_trait_fn, .. }) => impl_trait_fn,
 883             _ => None,
 884         },
 885         _ => None,
 886     };
 887
 888     let mut opt_self = None;
 889     let mut allow_defaults = false;
 890
 891     let no_generics = hir::Generics::empty();
 892     let ast_generics = match node {
 893         Node::TraitItem(item) => &item.generics,
 894
 895         Node::ImplItem(item) => &item.generics,
 896
 897         Node::Item(item) => {
 898             match item.node {
 899                 ItemKind::Fn(.., ref generics, _) | ItemKind::Impl(_, _, _, ref generics, ..) => {
 900                     generics
 901                 }
 902
 903                 ItemKind::Ty(_, ref generics)
 904                 | ItemKind::Enum(_, ref generics)
 905                 | ItemKind::Struct(_, ref generics)
 906                 | ItemKind::Existential(hir::ExistTy { ref generics, .. })
 907                 | ItemKind::Union(_, ref generics) => {
 908                     allow_defaults = true;
 909                     generics
 910                 }
 911
 912                 ItemKind::Trait(_, _, ref generics, ..)
 913                 | ItemKind::TraitAlias(ref generics, ..) => {
 914                     // Add in the self type parameter.
 915                     //
 916                     // Something of a hack: use the node id for the trait, also as
 917                     // the node id for the Self type parameter.
 918                     let param_id = item.id;
 919
 920                     opt_self = Some(ty::GenericParamDef {
 921                         index: 0,
 922                         name: keywords::SelfType.name().as_interned_str(),
 923                         def_id: tcx.hir.local_def_id(param_id),
 924                         pure_wrt_drop: false,
 925                         kind: ty::GenericParamDefKind::Type {
 926                             has_default: false,
 927                             object_lifetime_default: rl::Set1::Empty,
 928                             synthetic: None,
 929                         },
 930                     });
 931
 932                     allow_defaults = true;
 933                     generics
 934                 }
 935
 936                 _ => &no_generics,
 937             }
 938         }
 939
 940         Node::ForeignItem(item) => match item.node {
 941             ForeignItemKind::Static(..) => &no_generics,
 942             ForeignItemKind::Fn(_, _, ref generics) => generics,
 943             ForeignItemKind::Type => &no_generics,
 944         },
 945
 946         _ => &no_generics,
 947     };
 948
 949     let has_self = opt_self.is_some();
 950     let mut parent_has_self = false;
 951     let mut own_start = has_self as u32;
 952     let parent_count = parent_def_id.map_or(0, |def_id| {
 953         let generics = tcx.generics_of(def_id);
 954         assert_eq!(has_self, false);
 955         parent_has_self = generics.has_self;
 956         own_start = generics.count() as u32;
 957         generics.parent_count + generics.params.len()
 958     });
 959
 960     let mut params: Vec<_> = opt_self.into_iter().collect();
 961
 962     let early_lifetimes = early_bound_lifetimes_from_generics(tcx, ast_generics);
 963     params.extend(
 964         early_lifetimes
 965             .enumerate()
 966             .map(|(i, param)| ty::GenericParamDef {
 967                 name: param.name.ident().as_interned_str(),
 968                 index: own_start + i as u32,
 969                 def_id: tcx.hir.local_def_id(param.id),
 970                 pure_wrt_drop: param.pure_wrt_drop,
 971                 kind: ty::GenericParamDefKind::Lifetime,
 972             }),
 973     );
 974
 975     let hir_id = tcx.hir.node_to_hir_id(node_id);
 976     let object_lifetime_defaults = tcx.object_lifetime_defaults(hir_id);
 977
 978     // Now create the real type parameters.
 979     let type_start = own_start - has_self as u32 + params.len() as u32;
 980     let mut i = 0;
 981     params.extend(
 982         ast_generics
 983             .params
 984             .iter()
 985             .filter_map(|param| match param.kind {
 986                 GenericParamKind::Type {
 987                     ref default,
 988                     synthetic,
 989                     ..
 990                 } => {
 991                     if param.name.ident().name == keywords::SelfType.name() {
 992                         span_bug!(
 993                             param.span,
 994                             "`Self` should not be the name of a regular parameter"
 995                         );
 996                     }
 997
 998                     if !allow_defaults && default.is_some() {
 999                         if !tcx.features().default_type_parameter_fallback {
1000                             tcx.lint_node(
1001                                 lint::builtin::INVALID_TYPE_PARAM_DEFAULT,
1002                                 param.id,
1003                                 param.span,
1004                                 &format!(
1005                                     "defaults for type parameters are only allowed in \
1006                                      `struct`, `enum`, `type`, or `trait` definitions."
1007                                 ),
1008                             );
1009                         }
1010                     }
1011
1012                     let ty_param = ty::GenericParamDef {
1013                         index: type_start + i as u32,
1014                         name: param.name.ident().as_interned_str(),
1015                         def_id: tcx.hir.local_def_id(param.id),
1016                         pure_wrt_drop: param.pure_wrt_drop,
1017                         kind: ty::GenericParamDefKind::Type {
1018                             has_default: default.is_some(),
1019                             object_lifetime_default: object_lifetime_defaults
1020                                 .as_ref()
1021                                 .map_or(rl::Set1::Empty, |o| o[i]),
1022                             synthetic,
1023                         },
1024                     };
1025                     i += 1;
1026                     Some(ty_param)
1027                 }
1028                 _ => None,
1029             }),
1030     );
1031
1032     // provide junk type parameter defs - the only place that
1033     // cares about anything but the length is instantiation,
1034     // and we don't do that for closures.
1035     if let Node::Expr(&hir::Expr {
1036         node: hir::ExprKind::Closure(.., gen),
1037         ..
1038     }) = node
1039     {
1040         let dummy_args = if gen.is_some() {
1041             &["<yield_ty>", "<return_ty>", "<witness>"][..]
1042         } else {
1043             &["<closure_kind>", "<closure_signature>"][..]
1044         };
1045
1046         params.extend(
1047             dummy_args
1048                 .iter()
1049                 .enumerate()
1050                 .map(|(i, &arg)| ty::GenericParamDef {
1051                     index: type_start + i as u32,
1052                     name: Symbol::intern(arg).as_interned_str(),
1053                     def_id,
1054                     pure_wrt_drop: false,
1055                     kind: ty::GenericParamDefKind::Type {
1056                         has_default: false,
1057                         object_lifetime_default: rl::Set1::Empty,
1058                         synthetic: None,
1059                     },
1060                 }),
1061         );
1062
1063         tcx.with_freevars(node_id, |fv| {
1064             params.extend(fv.iter().zip((dummy_args.len() as u32)..).map(|(_, i)| {
1065                 ty::GenericParamDef {
1066                     index: type_start + i,
1067                     name: Symbol::intern("<upvar>").as_interned_str(),
1068                     def_id,
1069                     pure_wrt_drop: false,
1070                     kind: ty::GenericParamDefKind::Type {
1071                         has_default: false,
1072                         object_lifetime_default: rl::Set1::Empty,
1073                         synthetic: None,
1074                     },
1075                 }
1076             }));
1077         });
1078     }
1079
1080     let param_def_id_to_index = params
1081         .iter()
1082         .map(|param| (param.def_id, param.index))
1083         .collect();
1084
1085     tcx.alloc_generics(ty::Generics {
1086         parent: parent_def_id,
1087         parent_count,
1088         params,
1089         param_def_id_to_index,
1090         has_self: has_self || parent_has_self,
1091         has_late_bound_regions: has_late_bound_regions(tcx, node),
1092     })
1093 }
1094
1095 fn report_assoc_ty_on_inherent_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, span: Span) {
1096     span_err!(
1097         tcx.sess,
1098         span,
1099         E0202,
1100         "associated types are not allowed in inherent impls"
1101     );
1102 }
1103
1104 fn type_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> Ty<'tcx> {
1105     use rustc::hir::*;
1106
1107     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1108
1109     let icx = ItemCtxt::new(tcx, def_id);
1110
1111     match tcx.hir.get(node_id) {
1112         Node::TraitItem(item) => match item.node {
1113             TraitItemKind::Method(..) => {
1114                 let substs = Substs::identity_for_item(tcx, def_id);
1115                 tcx.mk_fn_def(def_id, substs)
1116             }
1117             TraitItemKind::Const(ref ty, _) | TraitItemKind::Type(_, Some(ref ty)) => icx.to_ty(ty),
1118             TraitItemKind::Type(_, None) => {
1119                 span_bug!(item.span, "associated type missing default");
1120             }
1121         },
1122
1123         Node::ImplItem(item) => match item.node {
1124             ImplItemKind::Method(..) => {
1125                 let substs = Substs::identity_for_item(tcx, def_id);
1126                 tcx.mk_fn_def(def_id, substs)
1127             }
1128             ImplItemKind::Const(ref ty, _) => icx.to_ty(ty),
1129             ImplItemKind::Existential(_) => {
1130                 if tcx
1131                     .impl_trait_ref(tcx.hir.get_parent_did(node_id))
1132                     .is_none()
1133                 {
1134                     report_assoc_ty_on_inherent_impl(tcx, item.span);
1135                 }
1136
1137                 find_existential_constraints(tcx, def_id)
1138             }
1139             ImplItemKind::Type(ref ty) => {
1140                 if tcx
1141                     .impl_trait_ref(tcx.hir.get_parent_did(node_id))
1142                     .is_none()
1143                 {
1144                     report_assoc_ty_on_inherent_impl(tcx, item.span);
1145                 }
1146
1147                 icx.to_ty(ty)
1148             }
1149         },
1150
1151         Node::Item(item) => {
1152             match item.node {
1153                 ItemKind::Static(ref t, ..)
1154                 | ItemKind::Const(ref t, _)
1155                 | ItemKind::Ty(ref t, _)
1156                 | ItemKind::Impl(.., ref t, _) => icx.to_ty(t),
1157                 ItemKind::Fn(..) => {
1158                     let substs = Substs::identity_for_item(tcx, def_id);
1159                     tcx.mk_fn_def(def_id, substs)
1160                 }
1161                 ItemKind::Enum(..) | ItemKind::Struct(..) | ItemKind::Union(..) => {
1162                     let def = tcx.adt_def(def_id);
1163                     let substs = Substs::identity_for_item(tcx, def_id);
1164                     tcx.mk_adt(def, substs)
1165                 }
1166                 ItemKind::Existential(hir::ExistTy {
1167                     impl_trait_fn: None,
1168                     ..
1169                 }) => find_existential_constraints(tcx, def_id),
1170                 // existential types desugared from impl Trait
1171                 ItemKind::Existential(hir::ExistTy {
1172                     impl_trait_fn: Some(owner),
1173                     ..
1174                 }) => {
1175                     tcx.typeck_tables_of(owner)
1176                         .concrete_existential_types
1177                         .get(&def_id)
1178                         .cloned()
1179                         .unwrap_or_else(|| {
1180                             // This can occur if some error in the
1181                             // owner fn prevented us from populating
1182                             // the `concrete_existential_types` table.
1183                             tcx.sess.delay_span_bug(
1184                                 DUMMY_SP,
1185                                 &format!(
1186                                     "owner {:?} has no existential type for {:?} in its tables",
1187                                     owner, def_id,
1188                                 ),
1189                             );
1190                             tcx.types.err
1191                         })
1192                 }
1193                 ItemKind::Trait(..)
1194                 | ItemKind::TraitAlias(..)
1195                 | ItemKind::Mod(..)
1196                 | ItemKind::ForeignMod(..)
1197                 | ItemKind::GlobalAsm(..)
1198                 | ItemKind::ExternCrate(..)
1199                 | ItemKind::Use(..) => {
1200                     span_bug!(
1201                         item.span,
1202                         "compute_type_of_item: unexpected item type: {:?}",
1203                         item.node
1204                     );
1205                 }
1206             }
1207         }
1208
1209         Node::ForeignItem(foreign_item) => match foreign_item.node {
1210             ForeignItemKind::Fn(..) => {
1211                 let substs = Substs::identity_for_item(tcx, def_id);
1212                 tcx.mk_fn_def(def_id, substs)
1213             }
1214             ForeignItemKind::Static(ref t, _) => icx.to_ty(t),
1215             ForeignItemKind::Type => tcx.mk_foreign(def_id),
1216         },
1217
1218         Node::StructCtor(&ref def)
1219         | Node::Variant(&Spanned {
1220             node: hir::VariantKind { data: ref def, .. },
1221             ..
1222         }) => match *def {
1223             VariantData::Unit(..) | VariantData::Struct(..) => {
1224                 tcx.type_of(tcx.hir.get_parent_did(node_id))
1225             }
1226             VariantData::Tuple(..) => {
1227                 let substs = Substs::identity_for_item(tcx, def_id);
1228                 tcx.mk_fn_def(def_id, substs)
1229             }
1230         },
1231
1232         Node::Field(field) => icx.to_ty(&field.ty),
1233
1234         Node::Expr(&hir::Expr {
1235             node: hir::ExprKind::Closure(.., gen),
1236             ..
1237         }) => {
1238             if gen.is_some() {
1239                 let hir_id = tcx.hir.node_to_hir_id(node_id);
1240                 return tcx.typeck_tables_of(def_id).node_id_to_type(hir_id);
1241             }
1242
1243             let substs = ty::ClosureSubsts {
1244                 substs: Substs::identity_for_item(tcx, def_id),
1245             };
1246
1247             tcx.mk_closure(def_id, substs)
1248         }
1249
1250         Node::AnonConst(_) => match tcx.hir.get(tcx.hir.get_parent_node(node_id)) {
1251             Node::Ty(&hir::Ty {
1252                 node: hir::TyKind::Array(_, ref constant),
1253                 ..
1254             })
1255             | Node::Ty(&hir::Ty {
1256                 node: hir::TyKind::Typeof(ref constant),
1257                 ..
1258             })
1259             | Node::Expr(&hir::Expr {
1260                 node: ExprKind::Repeat(_, ref constant),
1261                 ..
1262             }) if constant.id == node_id =>
1263             {
1264                 tcx.types.usize
1265             }
1266
1267             Node::Variant(&Spanned {
1268                 node:
1269                     VariantKind {
1270                         disr_expr: Some(ref e),
1271                         ..
1272                     },
1273                 ..
1274             }) if e.id == node_id =>
1275             {
1276                 tcx.adt_def(tcx.hir.get_parent_did(node_id))
1277                     .repr
1278                     .discr_type()
1279                     .to_ty(tcx)
1280             }
1281
1282             x => {
1283                 bug!("unexpected const parent in type_of_def_id(): {:?}", x);
1284             }
1285         },
1286
1287         Node::GenericParam(param) => match param.kind {
1288             hir::GenericParamKind::Type {
1289                 default: Some(ref ty),
1290                 ..
1291             } => icx.to_ty(ty),
1292             _ => bug!("unexpected non-type NodeGenericParam"),
1293         },
1294
1295         x => {
1296             bug!("unexpected sort of node in type_of_def_id(): {:?}", x);
1297         }
1298     }
1299 }
1300
1301 fn find_existential_constraints<'a, 'tcx>(
1302     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1303     def_id: DefId,
1304 ) -> ty::Ty<'tcx> {
1305     use rustc::hir::*;
1306
1307     struct ConstraintLocator<'a, 'tcx: 'a> {
1308         tcx: TyCtxt<'a, 'tcx, 'tcx>,
1309         def_id: DefId,
1310         found: Option<(Span, ty::Ty<'tcx>)>,
1311     }
1312     impl<'a, 'tcx> ConstraintLocator<'a, 'tcx> {
1313         fn check(&mut self, def_id: DefId) {
1314             trace!("checking {:?}", def_id);
1315             // don't try to check items that cannot possibly constrain the type
1316             if !self.tcx.has_typeck_tables(def_id) {
1317                 trace!("no typeck tables for {:?}", def_id);
1318                 return;
1319             }
1320             let ty = self
1321                 .tcx
1322                 .typeck_tables_of(def_id)
1323                 .concrete_existential_types
1324                 .get(&self.def_id)
1325                 .cloned();
1326             if let Some(ty) = ty {
1327                 // FIXME(oli-obk): trace the actual span from inference to improve errors
1328                 let span = self.tcx.def_span(def_id);
1329                 if let Some((prev_span, prev_ty)) = self.found {
1330                     if ty != prev_ty {
1331                         // found different concrete types for the existential type
1332                         let mut err = self.tcx.sess.struct_span_err(
1333                             span,
1334                             "defining existential type use differs from previous",
1335                         );
1336                         err.span_note(prev_span, "previous use here");
1337                         err.emit();
1338                     }
1339                 } else {
1340                     self.found = Some((span, ty));
1341                 }
1342             }
1343         }
1344     }
1345     impl<'a, 'tcx> intravisit::Visitor<'tcx> for ConstraintLocator<'a, 'tcx> {
1346         fn nested_visit_map<'this>(&'this mut self) -> intravisit::NestedVisitorMap<'this, 'tcx> {
1347             intravisit::NestedVisitorMap::All(&self.tcx.hir)
1348         }
1349         fn visit_item(&mut self, it: &'tcx Item) {
1350             let def_id = self.tcx.hir.local_def_id(it.id);
1351             // the existential type itself or its children are not within its reveal scope
1352             if def_id != self.def_id {
1353                 self.check(def_id);
1354                 intravisit::walk_item(self, it);
1355             }
1356         }
1357         fn visit_impl_item(&mut self, it: &'tcx ImplItem) {
1358             let def_id = self.tcx.hir.local_def_id(it.id);
1359             // the existential type itself or its children are not within its reveal scope
1360             if def_id != self.def_id {
1361                 self.check(def_id);
1362                 intravisit::walk_impl_item(self, it);
1363             }
1364         }
1365         fn visit_trait_item(&mut self, it: &'tcx TraitItem) {
1366             let def_id = self.tcx.hir.local_def_id(it.id);
1367             self.check(def_id);
1368             intravisit::walk_trait_item(self, it);
1369         }
1370     }
1371     let mut locator = ConstraintLocator {
1372         def_id,
1373         tcx,
1374         found: None,
1375     };
1376     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1377     let parent = tcx.hir.get_parent(node_id);
1378     trace!("parent_id: {:?}", parent);
1379     if parent == ast::CRATE_NODE_ID {
1380         intravisit::walk_crate(&mut locator, tcx.hir.krate());
1381     } else {
1382         trace!("parent: {:?}", tcx.hir.get(parent));
1383         match tcx.hir.get(parent) {
1384             Node::Item(ref it) => intravisit::walk_item(&mut locator, it),
1385             Node::ImplItem(ref it) => intravisit::walk_impl_item(&mut locator, it),
1386             Node::TraitItem(ref it) => intravisit::walk_trait_item(&mut locator, it),
1387             other => bug!(
1388                 "{:?} is not a valid parent of an existential type item",
1389                 other
1390             ),
1391         }
1392     }
1393     match locator.found {
1394         Some((_, ty)) => ty,
1395         None => {
1396             let span = tcx.def_span(def_id);
1397             tcx.sess.span_err(span, "could not find defining uses");
1398             tcx.types.err
1399         }
1400     }
1401 }
1402
1403 fn fn_sig<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> ty::PolyFnSig<'tcx> {
1404     use rustc::hir::*;
1405     use rustc::hir::Node::*;
1406
1407     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1408
1409     let icx = ItemCtxt::new(tcx, def_id);
1410
1411     match tcx.hir.get(node_id) {
1412         TraitItem(hir::TraitItem {
1413             node: TraitItemKind::Method(sig, _),
1414             ..
1415         })
1416         | ImplItem(hir::ImplItem {
1417             node: ImplItemKind::Method(sig, _),
1418             ..
1419         }) => AstConv::ty_of_fn(&icx, sig.header.unsafety, sig.header.abi, &sig.decl),
1420
1421         Item(hir::Item {
1422             node: ItemKind::Fn(decl, header, _, _),
1423             ..
1424         }) => AstConv::ty_of_fn(&icx, header.unsafety, header.abi, decl),
1425
1426         ForeignItem(&hir::ForeignItem {
1427             node: ForeignItemKind::Fn(ref fn_decl, _, _),
1428             ..
1429         }) => {
1430             let abi = tcx.hir.get_foreign_abi(node_id);
1431             compute_sig_of_foreign_fn_decl(tcx, def_id, fn_decl, abi)
1432         }
1433
1434         StructCtor(&VariantData::Tuple(ref fields, _))
1435         | Variant(&Spanned {
1436             node:
1437                 hir::VariantKind {
1438                     data: VariantData::Tuple(ref fields, _),
1439                     ..
1440                 },
1441             ..
1442         }) => {
1443             let ty = tcx.type_of(tcx.hir.get_parent_did(node_id));
1444             let inputs = fields
1445                 .iter()
1446                 .map(|f| tcx.type_of(tcx.hir.local_def_id(f.id)));
1447             ty::Binder::bind(tcx.mk_fn_sig(
1448                 inputs,
1449                 ty,
1450                 false,
1451                 hir::Unsafety::Normal,
1452                 abi::Abi::Rust,
1453             ))
1454         }
1455
1456         Expr(&hir::Expr {
1457             node: hir::ExprKind::Closure(..),
1458             ..
1459         }) => {
1460             // Closure signatures are not like other function
1461             // signatures and cannot be accessed through `fn_sig`. For
1462             // example, a closure signature excludes the `self`
1463             // argument. In any case they are embedded within the
1464             // closure type as part of the `ClosureSubsts`.
1465             //
1466             // To get
1467             // the signature of a closure, you should use the
1468             // `closure_sig` method on the `ClosureSubsts`:
1469             //
1470             //    closure_substs.closure_sig(def_id, tcx)
1471             //
1472             // or, inside of an inference context, you can use
1473             //
1474             //    infcx.closure_sig(def_id, closure_substs)
1475             bug!("to get the signature of a closure, use `closure_sig()` not `fn_sig()`");
1476         }
1477
1478         x => {
1479             bug!("unexpected sort of node in fn_sig(): {:?}", x);
1480         }
1481     }
1482 }
1483
1484 fn impl_trait_ref<'a, 'tcx>(
1485     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1486     def_id: DefId,
1487 ) -> Option<ty::TraitRef<'tcx>> {
1488     let icx = ItemCtxt::new(tcx, def_id);
1489
1490     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1491     match tcx.hir.expect_item(node_id).node {
1492         hir::ItemKind::Impl(.., ref opt_trait_ref, _, _) => {
1493             opt_trait_ref.as_ref().map(|ast_trait_ref| {
1494                 let selfty = tcx.type_of(def_id);
1495                 AstConv::instantiate_mono_trait_ref(&icx, ast_trait_ref, selfty)
1496             })
1497         }
1498         _ => bug!(),
1499     }
1500 }
1501
1502 fn impl_polarity<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> hir::ImplPolarity {
1503     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1504     match tcx.hir.expect_item(node_id).node {
1505         hir::ItemKind::Impl(_, polarity, ..) => polarity,
1506         ref item => bug!("impl_polarity: {:?} not an impl", item),
1507     }
1508 }
1509
1510 // Is it marked with ?Sized
1511 fn is_unsized<'gcx: 'tcx, 'tcx>(
1512     astconv: &dyn AstConv<'gcx, 'tcx>,
1513     ast_bounds: &[hir::GenericBound],
1514     span: Span,
1515 ) -> bool {
1516     let tcx = astconv.tcx();
1517
1518     // Try to find an unbound in bounds.
1519     let mut unbound = None;
1520     for ab in ast_bounds {
1521         if let &hir::GenericBound::Trait(ref ptr, hir::TraitBoundModifier::Maybe) = ab {
1522             if unbound.is_none() {
1523                 unbound = Some(ptr.trait_ref.clone());
1524             } else {
1525                 span_err!(
1526                     tcx.sess,
1527                     span,
1528                     E0203,
1529                     "type parameter has more than one relaxed default \
1530                      bound, only one is supported"
1531                 );
1532             }
1533         }
1534     }
1535
1536     let kind_id = tcx.lang_items().require(SizedTraitLangItem);
1537     match unbound {
1538         Some(ref tpb) => {
1539             // FIXME(#8559) currently requires the unbound to be built-in.
1540             if let Ok(kind_id) = kind_id {
1541                 if tpb.path.def != Def::Trait(kind_id) {
1542                     tcx.sess.span_warn(
1543                         span,
1544                         "default bound relaxed for a type parameter, but \
1545                          this does nothing because the given bound is not \
1546                          a default. Only `?Sized` is supported",
1547                     );
1548                 }
1549             }
1550         }
1551         _ if kind_id.is_ok() => {
1552             return false;
1553         }
1554         // No lang item for Sized, so we can't add it as a bound.
1555         None => {}
1556     }
1557
1558     true
1559 }
1560
1561 /// Returns the early-bound lifetimes declared in this generics
1562 /// listing.  For anything other than fns/methods, this is just all
1563 /// the lifetimes that are declared. For fns or methods, we have to
1564 /// screen out those that do not appear in any where-clauses etc using
1565 /// `resolve_lifetime::early_bound_lifetimes`.
1566 fn early_bound_lifetimes_from_generics<'a, 'tcx>(
1567     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1568     generics: &'a hir::Generics,
1569 ) -> impl Iterator<Item = &'a hir::GenericParam> + Captures<'tcx> {
1570     generics
1571         .params
1572         .iter()
1573         .filter(move |param| match param.kind {
1574             GenericParamKind::Lifetime { .. } => {
1575                 let hir_id = tcx.hir.node_to_hir_id(param.id);
1576                 !tcx.is_late_bound(hir_id)
1577             }
1578             _ => false,
1579         })
1580 }
1581
1582 fn predicates_defined_on<'a, 'tcx>(
1583     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1584     def_id: DefId,
1585 ) -> ty::GenericPredicates<'tcx> {
1586     let explicit = tcx.explicit_predicates_of(def_id);
1587     let predicates = [
1588       &explicit.predicates[..],
1589       &tcx.inferred_outlives_of(def_id)[..],
1590     ].concat();
1591
1592     ty::GenericPredicates {
1593         parent: explicit.parent,
1594         predicates: predicates,
1595     }
1596 }
1597
1598 fn predicates_of<'a, 'tcx>(
1599     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1600     def_id: DefId,
1601 ) -> ty::GenericPredicates<'tcx> {
1602     let ty::GenericPredicates {
1603         parent,
1604         mut predicates,
1605     } = tcx.predicates_defined_on(def_id);
1606
1607     if tcx.is_trait(def_id) {
1608         // For traits, add `Self: Trait` predicate. This is
1609         // not part of the predicates that a user writes, but it
1610         // is something that one must prove in order to invoke a
1611         // method or project an associated type.
1612         //
1613         // In the chalk setup, this predicate is not part of the
1614         // "predicates" for a trait item. But it is useful in
1615         // rustc because if you directly (e.g.) invoke a trait
1616         // method like `Trait::method(...)`, you must naturally
1617         // prove that the trait applies to the types that were
1618         // used, and adding the predicate into this list ensures
1619         // that this is done.
1620         predicates.push(ty::TraitRef::identity(tcx, def_id).to_predicate());
1621     }
1622
1623     ty::GenericPredicates { parent, predicates }
1624 }
1625
1626 fn explicit_predicates_of<'a, 'tcx>(
1627     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1628     def_id: DefId,
1629 ) -> ty::GenericPredicates<'tcx> {
1630     use rustc::hir::*;
1631
1632     debug!("explicit_predicates_of(def_id={:?})", def_id);
1633
1634     let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
1635     let node = tcx.hir.get(node_id);
1636
1637     let mut is_trait = None;
1638     let mut is_default_impl_trait = None;
1639
1640     let icx = ItemCtxt::new(tcx, def_id);
1641     let no_generics = hir::Generics::empty();
1642
1643     let mut predicates = vec![];
1644
1645     let ast_generics = match node {
1646         Node::TraitItem(item) => &item.generics,
1647
1648         Node::ImplItem(item) => match item.node {
1649             ImplItemKind::Existential(ref bounds) => {
1650                 let substs = Substs::identity_for_item(tcx, def_id);
1651                 let opaque_ty = tcx.mk_opaque(def_id, substs);
1652
1653                 // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
1654                 let bounds = compute_bounds(
1655                     &icx,
1656                     opaque_ty,
1657                     bounds,
1658                     SizedByDefault::Yes,
1659                     tcx.def_span(def_id),
1660                 );
1661
1662                 predicates.extend(bounds.predicates(tcx, opaque_ty));
1663                 &item.generics
1664             }
1665             _ => &item.generics,
1666         },
1667
1668         Node::Item(item) => {
1669             match item.node {
1670                 ItemKind::Impl(_, _, defaultness, ref generics, ..) => {
1671                     if defaultness.is_default() {
1672                         is_default_impl_trait = tcx.impl_trait_ref(def_id);
1673                     }
1674                     generics
1675                 }
1676                 ItemKind::Fn(.., ref generics, _)
1677                 | ItemKind::Ty(_, ref generics)
1678                 | ItemKind::Enum(_, ref generics)
1679                 | ItemKind::Struct(_, ref generics)
1680                 | ItemKind::Union(_, ref generics) => generics,
1681
1682                 ItemKind::Trait(_, _, ref generics, .., ref items) => {
1683                     is_trait = Some((ty::TraitRef::identity(tcx, def_id), items));
1684                     generics
1685                 }
1686                 ItemKind::Existential(ExistTy {
1687                     ref bounds,
1688                     impl_trait_fn,
1689                     ref generics,
1690                 }) => {
1691                     let substs = Substs::identity_for_item(tcx, def_id);
1692                     let opaque_ty = tcx.mk_opaque(def_id, substs);
1693
1694                     // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
1695                     let bounds = compute_bounds(
1696                         &icx,
1697                         opaque_ty,
1698                         bounds,
1699                         SizedByDefault::Yes,
1700                         tcx.def_span(def_id),
1701                     );
1702
1703                     if impl_trait_fn.is_some() {
1704                         // impl Trait
1705                         return ty::GenericPredicates {
1706                             parent: None,
1707                             predicates: bounds.predicates(tcx, opaque_ty),
1708                         };
1709                     } else {
1710                         // named existential types
1711                         predicates.extend(bounds.predicates(tcx, opaque_ty));
1712                         generics
1713                     }
1714                 }
1715
1716                 _ => &no_generics,
1717             }
1718         }
1719
1720         Node::ForeignItem(item) => match item.node {
1721             ForeignItemKind::Static(..) => &no_generics,
1722             ForeignItemKind::Fn(_, _, ref generics) => generics,
1723             ForeignItemKind::Type => &no_generics,
1724         },
1725
1726         _ => &no_generics,
1727     };
1728
1729     let generics = tcx.generics_of(def_id);
1730     let parent_count = generics.parent_count as u32;
1731     let has_own_self = generics.has_self && parent_count == 0;
1732
1733     // Below we'll consider the bounds on the type parameters (including `Self`)
1734     // and the explicit where-clauses, but to get the full set of predicates
1735     // on a trait we need to add in the supertrait bounds and bounds found on
1736     // associated types.
1737     if let Some((_trait_ref, _)) = is_trait {
1738         predicates = tcx.super_predicates_of(def_id).predicates;
1739     }
1740
1741     // In default impls, we can assume that the self type implements
1742     // the trait. So in:
1743     //
1744     //     default impl Foo for Bar { .. }
1745     //
1746     // we add a default where clause `Foo: Bar`. We do a similar thing for traits
1747     // (see below). Recall that a default impl is not itself an impl, but rather a
1748     // set of defaults that can be incorporated into another impl.
1749     if let Some(trait_ref) = is_default_impl_trait {
1750         predicates.push(trait_ref.to_poly_trait_ref().to_predicate());
1751     }
1752
1753     // Collect the region predicates that were declared inline as
1754     // well. In the case of parameters declared on a fn or method, we
1755     // have to be careful to only iterate over early-bound regions.
1756     let mut index = parent_count + has_own_self as u32;
1757     for param in early_bound_lifetimes_from_generics(tcx, ast_generics) {
1758         let region = tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
1759             def_id: tcx.hir.local_def_id(param.id),
1760             index,
1761             name: param.name.ident().as_interned_str(),
1762         }));
1763         index += 1;
1764
1765         match param.kind {
1766             GenericParamKind::Lifetime { .. } => {
1767                 param.bounds.iter().for_each(|bound| match bound {
1768                     hir::GenericBound::Outlives(lt) => {
1769                         let bound = AstConv::ast_region_to_region(&icx, &lt, None);
1770                         let outlives = ty::Binder::bind(ty::OutlivesPredicate(region, bound));
1771                         predicates.push(outlives.to_predicate());
1772                     }
1773                     _ => bug!(),
1774                 });
1775             }
1776             _ => bug!(),
1777         }
1778     }
1779
1780     // Collect the predicates that were written inline by the user on each
1781     // type parameter (e.g., `<T:Foo>`).
1782     for param in &ast_generics.params {
1783         match param.kind {
1784             GenericParamKind::Type { .. } => {
1785                 let name = param.name.ident().as_interned_str();
1786                 let param_ty = ty::ParamTy::new(index, name).to_ty(tcx);
1787                 index += 1;
1788
1789                 let sized = SizedByDefault::Yes;
1790                 let bounds = compute_bounds(&icx, param_ty, &param.bounds, sized, param.span);
1791                 predicates.extend(bounds.predicates(tcx, param_ty));
1792             }
1793             _ => {}
1794         }
1795     }
1796
1797     // Add in the bounds that appear in the where-clause
1798     let where_clause = &ast_generics.where_clause;
1799     for predicate in &where_clause.predicates {
1800         match predicate {
1801             &hir::WherePredicate::BoundPredicate(ref bound_pred) => {
1802                 let ty = icx.to_ty(&bound_pred.bounded_ty);
1803
1804                 // Keep the type around in a WF predicate, in case of no bounds.
1805                 // That way, `where Ty:` is not a complete noop (see #53696).
1806                 if bound_pred.bounds.is_empty() {
1807                     if let ty::Param(_) = ty.sty {
1808                         // This is a `where T:`, which can be in the HIR from the
1809                         // transformation that moves `?Sized` to `T`'s declaration.
1810                         // We can skip the predicate because type parameters are
1811                         // trivially WF, but also we *should*, to avoid exposing
1812                         // users who never wrote `where Type:,` themselves, to
1813                         // compiler/tooling bugs from not handling WF predicates.
1814                     } else {
1815                         predicates.push(ty::Predicate::WellFormed(ty));
1816                     }
1817                 }
1818
1819                 for bound in bound_pred.bounds.iter() {
1820                     match bound {
1821                         &hir::GenericBound::Trait(ref poly_trait_ref, _) => {
1822                             let mut projections = Vec::new();
1823
1824                             let trait_ref = AstConv::instantiate_poly_trait_ref(
1825                                 &icx,
1826                                 poly_trait_ref,
1827                                 ty,
1828                                 &mut projections,
1829                             );
1830
1831                             predicates.push(trait_ref.to_predicate());
1832                             predicates.extend(projections.iter().map(|p| p.to_predicate()));
1833                         }
1834
1835                         &hir::GenericBound::Outlives(ref lifetime) => {
1836                             let region = AstConv::ast_region_to_region(&icx, lifetime, None);
1837                             let pred = ty::Binder::bind(ty::OutlivesPredicate(ty, region));
1838                             predicates.push(ty::Predicate::TypeOutlives(pred))
1839                         }
1840                     }
1841                 }
1842             }
1843
1844             &hir::WherePredicate::RegionPredicate(ref region_pred) => {
1845                 let r1 = AstConv::ast_region_to_region(&icx, &region_pred.lifetime, None);
1846                 for bound in &region_pred.bounds {
1847                     let r2 = match bound {
1848                         hir::GenericBound::Outlives(lt) => {
1849                             AstConv::ast_region_to_region(&icx, lt, None)
1850                         }
1851                         _ => bug!(),
1852                     };
1853                     let pred = ty::Binder::bind(ty::OutlivesPredicate(r1, r2));
1854                     predicates.push(ty::Predicate::RegionOutlives(pred))
1855                 }
1856             }
1857
1858             &hir::WherePredicate::EqPredicate(..) => {
1859                 // FIXME(#20041)
1860             }
1861         }
1862     }
1863
1864     // Add predicates from associated type bounds.
1865     if let Some((self_trait_ref, trait_items)) = is_trait {
1866         predicates.extend(trait_items.iter().flat_map(|trait_item_ref| {
1867             let trait_item = tcx.hir.trait_item(trait_item_ref.id);
1868             let bounds = match trait_item.node {
1869                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
1870                 _ => {
1871                     return vec![].into_iter();
1872                 }
1873             };
1874
1875             let assoc_ty =
1876                 tcx.mk_projection(tcx.hir.local_def_id(trait_item.id), self_trait_ref.substs);
1877
1878             let bounds = compute_bounds(
1879                 &ItemCtxt::new(tcx, def_id),
1880                 assoc_ty,
1881                 bounds,
1882                 SizedByDefault::Yes,
1883                 trait_item.span,
1884             );
1885
1886             bounds.predicates(tcx, assoc_ty).into_iter()
1887         }))
1888     }
1889
1890     // Subtle: before we store the predicates into the tcx, we
1891     // sort them so that predicates like `T: Foo<Item=U>` come
1892     // before uses of `U`.  This avoids false ambiguity errors
1893     // in trait checking. See `setup_constraining_predicates`
1894     // for details.
1895     if let Node::Item(&Item {
1896         node: ItemKind::Impl(..),
1897         ..
1898     }) = node
1899     {
1900         let self_ty = tcx.type_of(def_id);
1901         let trait_ref = tcx.impl_trait_ref(def_id);
1902         ctp::setup_constraining_predicates(
1903             tcx,
1904             &mut predicates,
1905             trait_ref,
1906             &mut ctp::parameters_for_impl(self_ty, trait_ref),
1907         );
1908     }
1909
1910     ty::GenericPredicates {
1911         parent: generics.parent,
1912         predicates,
1913     }
1914 }
1915
1916 pub enum SizedByDefault {
1917     Yes,
1918     No,
1919 }
1920
1921 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
1922 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
1923 /// built-in trait (formerly known as kind): Send.
1924 pub fn compute_bounds<'gcx: 'tcx, 'tcx>(
1925     astconv: &dyn AstConv<'gcx, 'tcx>,
1926     param_ty: Ty<'tcx>,
1927     ast_bounds: &[hir::GenericBound],
1928     sized_by_default: SizedByDefault,
1929     span: Span,
1930 ) -> Bounds<'tcx> {
1931     let mut region_bounds = vec![];
1932     let mut trait_bounds = vec![];
1933     for ast_bound in ast_bounds {
1934         match *ast_bound {
1935             hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) => trait_bounds.push(b),
1936             hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
1937             hir::GenericBound::Outlives(ref l) => region_bounds.push(l),
1938         }
1939     }
1940
1941     let mut projection_bounds = vec![];
1942
1943     let mut trait_bounds: Vec<_> = trait_bounds
1944         .iter()
1945         .map(|&bound| astconv.instantiate_poly_trait_ref(bound, param_ty, &mut projection_bounds))
1946         .collect();
1947
1948     let region_bounds = region_bounds
1949         .into_iter()
1950         .map(|r| astconv.ast_region_to_region(r, None))
1951         .collect();
1952
1953     trait_bounds.sort_by_key(|t| t.def_id());
1954
1955     let implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
1956         !is_unsized(astconv, ast_bounds, span)
1957     } else {
1958         false
1959     };
1960
1961     Bounds {
1962         region_bounds,
1963         implicitly_sized,
1964         trait_bounds,
1965         projection_bounds,
1966     }
1967 }
1968
1969 /// Converts a specific GenericBound from the AST into a set of
1970 /// predicates that apply to the self-type. A vector is returned
1971 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
1972 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
1973 /// and `<T as Bar>::X == i32`).
1974 fn predicates_from_bound<'tcx>(
1975     astconv: &dyn AstConv<'tcx, 'tcx>,
1976     param_ty: Ty<'tcx>,
1977     bound: &hir::GenericBound,
1978 ) -> Vec<ty::Predicate<'tcx>> {
1979     match *bound {
1980         hir::GenericBound::Trait(ref tr, hir::TraitBoundModifier::None) => {
1981             let mut projections = Vec::new();
1982             let pred = astconv.instantiate_poly_trait_ref(tr, param_ty, &mut projections);
1983             projections
1984                 .into_iter()
1985                 .map(|p| p.to_predicate())
1986                 .chain(Some(pred.to_predicate()))
1987                 .collect()
1988         }
1989         hir::GenericBound::Outlives(ref lifetime) => {
1990             let region = astconv.ast_region_to_region(lifetime, None);
1991             let pred = ty::Binder::bind(ty::OutlivesPredicate(param_ty, region));
1992             vec![ty::Predicate::TypeOutlives(pred)]
1993         }
1994         hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => vec![],
1995     }
1996 }
1997
1998 fn compute_sig_of_foreign_fn_decl<'a, 'tcx>(
1999     tcx: TyCtxt<'a, 'tcx, 'tcx>,
2000     def_id: DefId,
2001     decl: &hir::FnDecl,
2002     abi: abi::Abi,
2003 ) -> ty::PolyFnSig<'tcx> {
2004     let unsafety = if abi == abi::Abi::RustIntrinsic {
2005         match &*tcx.item_name(def_id).as_str() {
2006             "size_of" | "min_align_of" | "needs_drop" => hir::Unsafety::Normal,
2007             _ => hir::Unsafety::Unsafe,
2008         }
2009     } else {
2010         hir::Unsafety::Unsafe
2011     };
2012     let fty = AstConv::ty_of_fn(&ItemCtxt::new(tcx, def_id), unsafety, abi, decl);
2013
2014     // feature gate SIMD types in FFI, since I (huonw) am not sure the
2015     // ABIs are handled at all correctly.
2016     if abi != abi::Abi::RustIntrinsic
2017         && abi != abi::Abi::PlatformIntrinsic
2018         && !tcx.features().simd_ffi
2019     {
2020         let check = |ast_ty: &hir::Ty, ty: Ty| {
2021             if ty.is_simd() {
2022                 tcx.sess
2023                     .struct_span_err(
2024                         ast_ty.span,
2025                         &format!(
2026                             "use of SIMD type `{}` in FFI is highly experimental and \
2027                              may result in invalid code",
2028                             tcx.hir.node_to_pretty_string(ast_ty.id)
2029                         ),
2030                     )
2031                     .help("add #![feature(simd_ffi)] to the crate attributes to enable")
2032                     .emit();
2033             }
2034         };
2035         for (input, ty) in decl.inputs.iter().zip(*fty.inputs().skip_binder()) {
2036             check(&input, ty)
2037         }
2038         if let hir::Return(ref ty) = decl.output {
2039             check(&ty, *fty.output().skip_binder())
2040         }
2041     }
2042
2043     fty
2044 }
2045
2046 fn is_foreign_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> bool {
2047     match tcx.hir.get_if_local(def_id) {
2048         Some(Node::ForeignItem(..)) => true,
2049         Some(_) => false,
2050         _ => bug!("is_foreign_item applied to non-local def-id {:?}", def_id),
2051     }
2052 }
2053
2054 fn from_target_feature(
2055     tcx: TyCtxt,
2056     id: DefId,
2057     attr: &ast::Attribute,
2058     whitelist: &FxHashMap<String, Option<String>>,
2059     target_features: &mut Vec<Symbol>,
2060 ) {
2061     let list = match attr.meta_item_list() {
2062         Some(list) => list,
2063         None => {
2064             let msg = "#[target_feature] attribute must be of the form \
2065                        #[target_feature(..)]";
2066             tcx.sess.span_err(attr.span, &msg);
2067             return;
2068         }
2069     };
2070     let rust_features = tcx.features();
2071     for item in list {
2072         // Only `enable = ...` is accepted in the meta item list
2073         if !item.check_name("enable") {
2074             let msg = "#[target_feature(..)] only accepts sub-keys of `enable` \
2075                        currently";
2076             tcx.sess.span_err(item.span, &msg);
2077             continue;
2078         }
2079
2080         // Must be of the form `enable = "..."` ( a string)
2081         let value = match item.value_str() {
2082             Some(value) => value,
2083             None => {
2084                 let msg = "#[target_feature] attribute must be of the form \
2085                            #[target_feature(enable = \"..\")]";
2086                 tcx.sess.span_err(item.span, &msg);
2087                 continue;
2088             }
2089         };
2090
2091         // We allow comma separation to enable multiple features
2092         for feature in value.as_str().split(',') {
2093             // Only allow whitelisted features per platform
2094             let feature_gate = match whitelist.get(feature) {
2095                 Some(g) => g,
2096                 None => {
2097                     let msg = format!(
2098                         "the feature named `{}` is not valid for \
2099                          this target",
2100                         feature
2101                     );
2102                     let mut err = tcx.sess.struct_span_err(item.span, &msg);
2103
2104                     if feature.starts_with("+") {
2105                         let valid = whitelist.contains_key(&feature[1..]);
2106                         if valid {
2107                             err.help("consider removing the leading `+` in the feature name");
2108                         }
2109                     }
2110                     err.emit();
2111                     continue;
2112                 }
2113             };
2114
2115             // Only allow features whose feature gates have been enabled
2116             let allowed = match feature_gate.as_ref().map(|s| &**s) {
2117                 Some("arm_target_feature") => rust_features.arm_target_feature,
2118                 Some("aarch64_target_feature") => rust_features.aarch64_target_feature,
2119                 Some("hexagon_target_feature") => rust_features.hexagon_target_feature,
2120                 Some("powerpc_target_feature") => rust_features.powerpc_target_feature,
2121                 Some("mips_target_feature") => rust_features.mips_target_feature,
2122                 Some("avx512_target_feature") => rust_features.avx512_target_feature,
2123                 Some("mmx_target_feature") => rust_features.mmx_target_feature,
2124                 Some("sse4a_target_feature") => rust_features.sse4a_target_feature,
2125                 Some("tbm_target_feature") => rust_features.tbm_target_feature,
2126                 Some("wasm_target_feature") => rust_features.wasm_target_feature,
2127                 Some(name) => bug!("unknown target feature gate {}", name),
2128                 None => true,
2129             };
2130             if !allowed && id.is_local() {
2131                 feature_gate::emit_feature_err(
2132                     &tcx.sess.parse_sess,
2133                     feature_gate.as_ref().unwrap(),
2134                     item.span,
2135                     feature_gate::GateIssue::Language,
2136                     &format!("the target feature `{}` is currently unstable", feature),
2137                 );
2138                 continue;
2139             }
2140             target_features.push(Symbol::intern(feature));
2141         }
2142     }
2143 }
2144
2145 fn linkage_by_name<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId, name: &str) -> Linkage {
2146     use rustc::mir::mono::Linkage::*;
2147
2148     // Use the names from src/llvm/docs/LangRef.rst here. Most types are only
2149     // applicable to variable declarations and may not really make sense for
2150     // Rust code in the first place but whitelist them anyway and trust that
2151     // the user knows what s/he's doing. Who knows, unanticipated use cases
2152     // may pop up in the future.
2153     //
2154     // ghost, dllimport, dllexport and linkonce_odr_autohide are not supported
2155     // and don't have to be, LLVM treats them as no-ops.
2156     match name {
2157         "appending" => Appending,
2158         "available_externally" => AvailableExternally,
2159         "common" => Common,
2160         "extern_weak" => ExternalWeak,
2161         "external" => External,
2162         "internal" => Internal,
2163         "linkonce" => LinkOnceAny,
2164         "linkonce_odr" => LinkOnceODR,
2165         "private" => Private,
2166         "weak" => WeakAny,
2167         "weak_odr" => WeakODR,
2168         _ => {
2169             let span = tcx.hir.span_if_local(def_id);
2170             if let Some(span) = span {
2171                 tcx.sess.span_fatal(span, "invalid linkage specified")
2172             } else {
2173                 tcx.sess
2174                     .fatal(&format!("invalid linkage specified: {}", name))
2175             }
2176         }
2177     }
2178 }
2179
2180 fn codegen_fn_attrs<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, id: DefId) -> CodegenFnAttrs {
2181     let attrs = tcx.get_attrs(id);
2182
2183     let mut codegen_fn_attrs = CodegenFnAttrs::new();
2184
2185     let whitelist = tcx.target_features_whitelist(LOCAL_CRATE);
2186
2187     let mut inline_span = None;
2188     for attr in attrs.iter() {
2189         if attr.check_name("cold") {
2190             codegen_fn_attrs.flags |= CodegenFnAttrFlags::COLD;
2191         } else if attr.check_name("allocator") {
2192             codegen_fn_attrs.flags |= CodegenFnAttrFlags::ALLOCATOR;
2193         } else if attr.check_name("unwind") {
2194             codegen_fn_attrs.flags |= CodegenFnAttrFlags::UNWIND;
2195         } else if attr.check_name("rustc_allocator_nounwind") {
2196             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_ALLOCATOR_NOUNWIND;
2197         } else if attr.check_name("naked") {
2198             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NAKED;
2199         } else if attr.check_name("no_mangle") {
2200             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
2201         } else if attr.check_name("rustc_std_internal_symbol") {
2202             codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
2203         } else if attr.check_name("no_debug") {
2204             codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_DEBUG;
2205         } else if attr.check_name("used") {
2206             codegen_fn_attrs.flags |= CodegenFnAttrFlags::USED;
2207         } else if attr.check_name("thread_local") {
2208             codegen_fn_attrs.flags |= CodegenFnAttrFlags::THREAD_LOCAL;
2209         } else if attr.check_name("inline") {
2210             codegen_fn_attrs.inline = attrs.iter().fold(InlineAttr::None, |ia, attr| {
2211                 if attr.path != "inline" {
2212                     return ia;
2213                 }
2214                 let meta = match attr.meta() {
2215                     Some(meta) => meta.node,
2216                     None => return ia,
2217                 };
2218                 match meta {
2219                     MetaItemKind::Word => {
2220                         mark_used(attr);
2221                         InlineAttr::Hint
2222                     }
2223                     MetaItemKind::List(ref items) => {
2224                         mark_used(attr);
2225                         inline_span = Some(attr.span);
2226                         if items.len() != 1 {
2227                             span_err!(
2228                                 tcx.sess.diagnostic(),
2229                                 attr.span,
2230                                 E0534,
2231                                 "expected one argument"
2232                             );
2233                             InlineAttr::None
2234                         } else if list_contains_name(&items[..], "always") {
2235                             InlineAttr::Always
2236                         } else if list_contains_name(&items[..], "never") {
2237                             InlineAttr::Never
2238                         } else {
2239                             span_err!(
2240                                 tcx.sess.diagnostic(),
2241                                 items[0].span,
2242                                 E0535,
2243                                 "invalid argument"
2244                             );
2245
2246                             InlineAttr::None
2247                         }
2248                     }
2249                     _ => ia,
2250                 }
2251             });
2252         } else if attr.check_name("export_name") {
2253             if let Some(s) = attr.value_str() {
2254                 if s.as_str().contains("\0") {
2255                     // `#[export_name = ...]` will be converted to a null-terminated string,
2256                     // so it may not contain any null characters.
2257                     struct_span_err!(
2258                         tcx.sess,
2259                         attr.span,
2260                         E0648,
2261                         "`export_name` may not contain null characters"
2262                     ).emit();
2263                 }
2264                 codegen_fn_attrs.export_name = Some(s);
2265             } else {
2266                 struct_span_err!(
2267                     tcx.sess,
2268                     attr.span,
2269                     E0558,
2270                     "`export_name` attribute has invalid format"
2271                 ).span_label(attr.span, "did you mean #[export_name=\"*\"]?")
2272                     .emit();
2273             }
2274         } else if attr.check_name("target_feature") {
2275             if tcx.fn_sig(id).unsafety() == Unsafety::Normal {
2276                 let msg = "#[target_feature(..)] can only be applied to \
2277                            `unsafe` function";
2278                 tcx.sess.span_err(attr.span, msg);
2279             }
2280             from_target_feature(
2281                 tcx,
2282                 id,
2283                 attr,
2284                 &whitelist,
2285                 &mut codegen_fn_attrs.target_features,
2286             );
2287         } else if attr.check_name("linkage") {
2288             if let Some(val) = attr.value_str() {
2289                 codegen_fn_attrs.linkage = Some(linkage_by_name(tcx, id, &val.as_str()));
2290             }
2291         } else if attr.check_name("link_section") {
2292             if let Some(val) = attr.value_str() {
2293                 if val.as_str().bytes().any(|b| b == 0) {
2294                     let msg = format!(
2295                         "illegal null byte in link_section \
2296                          value: `{}`",
2297                         &val
2298                     );
2299                     tcx.sess.span_err(attr.span, &msg);
2300                 } else {
2301                     codegen_fn_attrs.link_section = Some(val);
2302                 }
2303             }
2304         } else if attr.check_name("link_name") {
2305             codegen_fn_attrs.link_name = attr.value_str();
2306         }
2307     }
2308
2309     // If a function uses #[target_feature] it can't be inlined into general
2310     // purpose functions as they wouldn't have the right target features
2311     // enabled. For that reason we also forbid #[inline(always)] as it can't be
2312     // respected.
2313     if codegen_fn_attrs.target_features.len() > 0 {
2314         if codegen_fn_attrs.inline == InlineAttr::Always {
2315             if let Some(span) = inline_span {
2316                 tcx.sess.span_err(
2317                     span,
2318                     "cannot use #[inline(always)] with \
2319                      #[target_feature]",
2320                 );
2321             }
2322         }
2323     }
2324
2325     // Weak lang items have the same semantics as "std internal" symbols in the
2326     // sense that they're preserved through all our LTO passes and only
2327     // strippable by the linker.
2328     //
2329     // Additionally weak lang items have predetermined symbol names.
2330     if tcx.is_weak_lang_item(id) {
2331         codegen_fn_attrs.flags |= CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL;
2332     }
2333     if let Some(name) = weak_lang_items::link_name(&attrs) {
2334         codegen_fn_attrs.export_name = Some(name);
2335         codegen_fn_attrs.link_name = Some(name);
2336     }
2337
2338     // Internal symbols to the standard library all have no_mangle semantics in
2339     // that they have defined symbol names present in the function name. This
2340     // also applies to weak symbols where they all have known symbol names.
2341     if codegen_fn_attrs.flags.contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL) {
2342         codegen_fn_attrs.flags |= CodegenFnAttrFlags::NO_MANGLE;
2343     }
2344
2345     codegen_fn_attrs
2346 }