src/librustc/middle/resolve_lifetime.rs

   1 // Copyright 2012-2013 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 //! Name resolution for lifetimes.
  12 //!
  13 //! Name resolution for lifetimes follows MUCH simpler rules than the
  14 //! full resolve. For example, lifetime names are never exported or
  15 //! used between functions, and they operate in a purely top-down
  16 //! way. Therefore we break lifetime name resolution into a separate pass.
  17
  18 use hir::map::Map;
  19 use hir::def::Def;
  20 use hir::def_id::{CrateNum, DefId, LocalDefId, LOCAL_CRATE};
  21 use hir::ItemLocalId;
  22 use ty::{self, TyCtxt};
  23
  24 use std::cell::Cell;
  25 use std::mem::replace;
  26 use std::rc::Rc;
  27 use syntax::ast;
  28 use syntax::attr;
  29 use syntax::ptr::P;
  30 use syntax_pos::Span;
  31 use errors::DiagnosticBuilder;
  32 use util::nodemap::{DefIdMap, FxHashMap, FxHashSet, NodeMap, NodeSet};
  33 use std::slice;
  34 use rustc::lint;
  35
  36 use hir::{self, GenericParamsExt};
  37 use hir::intravisit::{self, NestedVisitorMap, Visitor};
  38
  39 /// The origin of a named lifetime definition.
  40 ///
  41 /// This is used to prevent the usage of in-band lifetimes in `Fn`/`fn` syntax.
  42 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  43 pub enum LifetimeDefOrigin {
  44     // Explicit binders like `fn foo<'a>(x: &'a u8)`
  45     Explicit,
  46     // In-band declarations like `fn foo(x: &'a u8)`
  47     InBand,
  48 }
  49
  50 impl LifetimeDefOrigin {
  51     fn from_is_in_band(is_in_band: bool) -> Self {
  52         if is_in_band {
  53             LifetimeDefOrigin::InBand
  54         } else {
  55             LifetimeDefOrigin::Explicit
  56         }
  57     }
  58 }
  59
  60 // This counts the no of times a lifetime is used
  61 #[derive(Clone, Copy, Debug)]
  62 pub enum LifetimeUseSet<'tcx> {
  63     One(&'tcx hir::Lifetime),
  64     Many,
  65 }
  66
  67 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  68 pub enum Region {
  69     Static,
  70     EarlyBound(
  71         /* index */ u32,
  72         /* lifetime decl */ DefId,
  73         LifetimeDefOrigin,
  74     ),
  75     LateBound(
  76         ty::DebruijnIndex,
  77         /* lifetime decl */ DefId,
  78         LifetimeDefOrigin,
  79     ),
  80     LateBoundAnon(ty::DebruijnIndex, /* anon index */ u32),
  81     Free(DefId, /* lifetime decl */ DefId),
  82 }
  83
  84 impl Region {
  85     fn early(
  86         hir_map: &Map,
  87         index: &mut u32,
  88         def: &hir::LifetimeDef,
  89     ) -> (hir::LifetimeName, Region) {
  90         let i = *index;
  91         *index += 1;
  92         let def_id = hir_map.local_def_id(def.lifetime.id);
  93         let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
  94         debug!("Region::early: index={} def_id={:?}", i, def_id);
  95         (def.lifetime.name, Region::EarlyBound(i, def_id, origin))
  96     }
  97
  98     fn late(hir_map: &Map, def: &hir::LifetimeDef) -> (hir::LifetimeName, Region) {
  99         let depth = ty::DebruijnIndex::new(1);
 100         let def_id = hir_map.local_def_id(def.lifetime.id);
 101         let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
 102         (def.lifetime.name, Region::LateBound(depth, def_id, origin))
 103     }
 104
 105     fn late_anon(index: &Cell<u32>) -> Region {
 106         let i = index.get();
 107         index.set(i + 1);
 108         let depth = ty::DebruijnIndex::new(1);
 109         Region::LateBoundAnon(depth, i)
 110     }
 111
 112     fn id(&self) -> Option<DefId> {
 113         match *self {
 114             Region::Static | Region::LateBoundAnon(..) => None,
 115
 116             Region::EarlyBound(_, id, _) | Region::LateBound(_, id, _) | Region::Free(_, id) => {
 117                 Some(id)
 118             }
 119         }
 120     }
 121
 122     fn shifted(self, amount: u32) -> Region {
 123         match self {
 124             Region::LateBound(depth, id, origin) => {
 125                 Region::LateBound(depth.shifted(amount), id, origin)
 126             }
 127             Region::LateBoundAnon(depth, index) => {
 128                 Region::LateBoundAnon(depth.shifted(amount), index)
 129             }
 130             _ => self,
 131         }
 132     }
 133
 134     fn from_depth(self, depth: u32) -> Region {
 135         match self {
 136             Region::LateBound(debruijn, id, origin) => Region::LateBound(
 137                 ty::DebruijnIndex {
 138                     depth: debruijn.depth - (depth - 1),
 139                 },
 140                 id,
 141                 origin,
 142             ),
 143             Region::LateBoundAnon(debruijn, index) => Region::LateBoundAnon(
 144                 ty::DebruijnIndex {
 145                     depth: debruijn.depth - (depth - 1),
 146                 },
 147                 index,
 148             ),
 149             _ => self,
 150         }
 151     }
 152
 153     fn subst(self, params: &[hir::Lifetime], map: &NamedRegionMap) -> Option<Region> {
 154         if let Region::EarlyBound(index, _, _) = self {
 155             params
 156                 .get(index as usize)
 157                 .and_then(|lifetime| map.defs.get(&lifetime.id).cloned())
 158         } else {
 159             Some(self)
 160         }
 161     }
 162 }
 163
 164 /// A set containing, at most, one known element.
 165 /// If two distinct values are inserted into a set, then it
 166 /// becomes `Many`, which can be used to detect ambiguities.
 167 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
 168 pub enum Set1<T> {
 169     Empty,
 170     One(T),
 171     Many,
 172 }
 173
 174 impl<T: PartialEq> Set1<T> {
 175     pub fn insert(&mut self, value: T) {
 176         if let Set1::Empty = *self {
 177             *self = Set1::One(value);
 178             return;
 179         }
 180         if let Set1::One(ref old) = *self {
 181             if *old == value {
 182                 return;
 183             }
 184         }
 185         *self = Set1::Many;
 186     }
 187 }
 188
 189 pub type ObjectLifetimeDefault = Set1<Region>;
 190
 191 /// Maps the id of each lifetime reference to the lifetime decl
 192 /// that it corresponds to.
 193 ///
 194 /// FIXME. This struct gets converted to a `ResolveLifetimes` for
 195 /// actual use. It has the same data, but indexed by `DefIndex`.  This
 196 /// is silly.
 197 #[derive(Default)]
 198 struct NamedRegionMap {
 199     // maps from every use of a named (not anonymous) lifetime to a
 200     // `Region` describing how that region is bound
 201     pub defs: NodeMap<Region>,
 202
 203     // the set of lifetime def ids that are late-bound; a region can
 204     // be late-bound if (a) it does NOT appear in a where-clause and
 205     // (b) it DOES appear in the arguments.
 206     pub late_bound: NodeSet,
 207
 208     // For each type and trait definition, maps type parameters
 209     // to the trait object lifetime defaults computed from them.
 210     pub object_lifetime_defaults: NodeMap<Vec<ObjectLifetimeDefault>>,
 211 }
 212
 213 /// See `NamedRegionMap`.
 214 pub struct ResolveLifetimes {
 215     defs: FxHashMap<LocalDefId, Rc<FxHashMap<ItemLocalId, Region>>>,
 216     late_bound: FxHashMap<LocalDefId, Rc<FxHashSet<ItemLocalId>>>,
 217     object_lifetime_defaults:
 218         FxHashMap<LocalDefId, Rc<FxHashMap<ItemLocalId, Rc<Vec<ObjectLifetimeDefault>>>>>,
 219 }
 220
 221 impl_stable_hash_for!(struct ::middle::resolve_lifetime::ResolveLifetimes {
 222     defs,
 223     late_bound,
 224     object_lifetime_defaults
 225 });
 226
 227 struct LifetimeContext<'a, 'tcx: 'a> {
 228     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 229     map: &'a mut NamedRegionMap,
 230     scope: ScopeRef<'a>,
 231     // Deep breath. Our representation for poly trait refs contains a single
 232     // binder and thus we only allow a single level of quantification. However,
 233     // the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
 234     // and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
 235     // correct when representing these constraints, we should only introduce one
 236     // scope. However, we want to support both locations for the quantifier and
 237     // during lifetime resolution we want precise information (so we can't
 238     // desugar in an earlier phase).
 239
 240     // SO, if we encounter a quantifier at the outer scope, we set
 241     // trait_ref_hack to true (and introduce a scope), and then if we encounter
 242     // a quantifier at the inner scope, we error. If trait_ref_hack is false,
 243     // then we introduce the scope at the inner quantifier.
 244
 245     // I'm sorry.
 246     trait_ref_hack: bool,
 247
 248     // Used to disallow the use of in-band lifetimes in `fn` or `Fn` syntax.
 249     is_in_fn_syntax: bool,
 250
 251     // List of labels in the function/method currently under analysis.
 252     labels_in_fn: Vec<(ast::Name, Span)>,
 253
 254     // Cache for cross-crate per-definition object lifetime defaults.
 255     xcrate_object_lifetime_defaults: DefIdMap<Vec<ObjectLifetimeDefault>>,
 256
 257     lifetime_uses: DefIdMap<LifetimeUseSet<'tcx>>,
 258 }
 259
 260 #[derive(Debug)]
 261 enum Scope<'a> {
 262     /// Declares lifetimes, and each can be early-bound or late-bound.
 263     /// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
 264     /// it should be shifted by the number of `Binder`s in between the
 265     /// declaration `Binder` and the location it's referenced from.
 266     Binder {
 267         lifetimes: FxHashMap<hir::LifetimeName, Region>,
 268
 269         /// if we extend this scope with another scope, what is the next index
 270         /// we should use for an early-bound region?
 271         next_early_index: u32,
 272
 273         /// Whether or not this binder would serve as the parent
 274         /// binder for abstract types introduced within. For example:
 275         ///
 276         ///     fn foo<'a>() -> impl for<'b> Trait<Item = impl Trait2<'a>>
 277         ///
 278         /// Here, the abstract types we create for the `impl Trait`
 279         /// and `impl Trait2` references will both have the `foo` item
 280         /// as their parent. When we get to `impl Trait2`, we find
 281         /// that it is nested within the `for<>` binder -- this flag
 282         /// allows us to skip that when looking for the parent binder
 283         /// of the resulting abstract type.
 284         abstract_type_parent: bool,
 285
 286         s: ScopeRef<'a>,
 287     },
 288
 289     /// Lifetimes introduced by a fn are scoped to the call-site for that fn,
 290     /// if this is a fn body, otherwise the original definitions are used.
 291     /// Unspecified lifetimes are inferred, unless an elision scope is nested,
 292     /// e.g. `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
 293     Body {
 294         id: hir::BodyId,
 295         s: ScopeRef<'a>,
 296     },
 297
 298     /// A scope which either determines unspecified lifetimes or errors
 299     /// on them (e.g. due to ambiguity). For more details, see `Elide`.
 300     Elision {
 301         elide: Elide,
 302         s: ScopeRef<'a>,
 303     },
 304
 305     /// Use a specific lifetime (if `Some`) or leave it unset (to be
 306     /// inferred in a function body or potentially error outside one),
 307     /// for the default choice of lifetime in a trait object type.
 308     ObjectLifetimeDefault {
 309         lifetime: Option<Region>,
 310         s: ScopeRef<'a>,
 311     },
 312
 313     Root,
 314 }
 315
 316 #[derive(Clone, Debug)]
 317 enum Elide {
 318     /// Use a fresh anonymous late-bound lifetime each time, by
 319     /// incrementing the counter to generate sequential indices.
 320     FreshLateAnon(Cell<u32>),
 321     /// Always use this one lifetime.
 322     Exact(Region),
 323     /// Less or more than one lifetime were found, error on unspecified.
 324     Error(Vec<ElisionFailureInfo>),
 325 }
 326
 327 #[derive(Clone, Debug)]
 328 struct ElisionFailureInfo {
 329     /// Where we can find the argument pattern.
 330     parent: Option<hir::BodyId>,
 331     /// The index of the argument in the original definition.
 332     index: usize,
 333     lifetime_count: usize,
 334     have_bound_regions: bool,
 335 }
 336
 337 type ScopeRef<'a> = &'a Scope<'a>;
 338
 339 const ROOT_SCOPE: ScopeRef<'static> = &Scope::Root;
 340
 341 pub fn provide(providers: &mut ty::maps::Providers) {
 342     *providers = ty::maps::Providers {
 343         resolve_lifetimes,
 344
 345         named_region_map: |tcx, id| {
 346             let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
 347             tcx.resolve_lifetimes(LOCAL_CRATE).defs.get(&id).cloned()
 348         },
 349
 350         is_late_bound_map: |tcx, id| {
 351             let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
 352             tcx.resolve_lifetimes(LOCAL_CRATE)
 353                 .late_bound
 354                 .get(&id)
 355                 .cloned()
 356         },
 357
 358         object_lifetime_defaults_map: |tcx, id| {
 359             let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
 360             tcx.resolve_lifetimes(LOCAL_CRATE)
 361                 .object_lifetime_defaults
 362                 .get(&id)
 363                 .cloned()
 364         },
 365
 366         ..*providers
 367     };
 368
 369     // (*) FIXME the query should be defined to take a LocalDefId
 370 }
 371
 372 /// Computes the `ResolveLifetimes` map that contains data for the
 373 /// entire crate. You should not read the result of this query
 374 /// directly, but rather use `named_region_map`, `is_late_bound_map`,
 375 /// etc.
 376 fn resolve_lifetimes<'tcx>(
 377     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 378     for_krate: CrateNum,
 379 ) -> Rc<ResolveLifetimes> {
 380     assert_eq!(for_krate, LOCAL_CRATE);
 381
 382     let named_region_map = krate(tcx);
 383
 384     let mut defs = FxHashMap();
 385     for (k, v) in named_region_map.defs {
 386         let hir_id = tcx.hir.node_to_hir_id(k);
 387         let map = defs.entry(hir_id.owner_local_def_id())
 388             .or_insert_with(|| Rc::new(FxHashMap()));
 389         Rc::get_mut(map).unwrap().insert(hir_id.local_id, v);
 390     }
 391     let mut late_bound = FxHashMap();
 392     for k in named_region_map.late_bound {
 393         let hir_id = tcx.hir.node_to_hir_id(k);
 394         let map = late_bound
 395             .entry(hir_id.owner_local_def_id())
 396             .or_insert_with(|| Rc::new(FxHashSet()));
 397         Rc::get_mut(map).unwrap().insert(hir_id.local_id);
 398     }
 399     let mut object_lifetime_defaults = FxHashMap();
 400     for (k, v) in named_region_map.object_lifetime_defaults {
 401         let hir_id = tcx.hir.node_to_hir_id(k);
 402         let map = object_lifetime_defaults
 403             .entry(hir_id.owner_local_def_id())
 404             .or_insert_with(|| Rc::new(FxHashMap()));
 405         Rc::get_mut(map)
 406             .unwrap()
 407             .insert(hir_id.local_id, Rc::new(v));
 408     }
 409
 410     Rc::new(ResolveLifetimes {
 411         defs,
 412         late_bound,
 413         object_lifetime_defaults,
 414     })
 415 }
 416
 417 fn krate<'tcx>(tcx: TyCtxt<'_, 'tcx, 'tcx>) -> NamedRegionMap {
 418     let krate = tcx.hir.krate();
 419     let mut map = NamedRegionMap {
 420         defs: NodeMap(),
 421         late_bound: NodeSet(),
 422         object_lifetime_defaults: compute_object_lifetime_defaults(tcx),
 423     };
 424     {
 425         let mut visitor = LifetimeContext {
 426             tcx,
 427             map: &mut map,
 428             scope: ROOT_SCOPE,
 429             trait_ref_hack: false,
 430             is_in_fn_syntax: false,
 431             labels_in_fn: vec![],
 432             xcrate_object_lifetime_defaults: DefIdMap(),
 433             lifetime_uses: DefIdMap(),
 434         };
 435         for (_, item) in &krate.items {
 436             visitor.visit_item(item);
 437         }
 438     }
 439     map
 440 }
 441
 442 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 443     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 444         NestedVisitorMap::All(&self.tcx.hir)
 445     }
 446
 447     // We want to nest trait/impl items in their parent, but nothing else.
 448     fn visit_nested_item(&mut self, _: hir::ItemId) {}
 449
 450     fn visit_nested_body(&mut self, body: hir::BodyId) {
 451         // Each body has their own set of labels, save labels.
 452         let saved = replace(&mut self.labels_in_fn, vec![]);
 453         let body = self.tcx.hir.body(body);
 454         extract_labels(self, body);
 455         self.with(
 456             Scope::Body {
 457                 id: body.id(),
 458                 s: self.scope,
 459             },
 460             |_, this| {
 461                 this.visit_body(body);
 462             },
 463         );
 464         replace(&mut self.labels_in_fn, saved);
 465     }
 466
 467     fn visit_item(&mut self, item: &'tcx hir::Item) {
 468         match item.node {
 469             hir::ItemFn(ref decl, _, _, _, ref generics, _) => {
 470                 self.visit_early_late(None,
 471                                       decl,
 472                                       generics,
 473                                       |this| {
 474                                           intravisit::walk_item(this, item);
 475                 });
 476             }
 477
 478             hir::ItemExternCrate(_)
 479             | hir::ItemUse(..)
 480             | hir::ItemMod(..)
 481             | hir::ItemForeignMod(..)
 482             | hir::ItemGlobalAsm(..) => {
 483                 // These sorts of items have no lifetime parameters at all.
 484                 intravisit::walk_item(self, item);
 485             }
 486             hir::ItemStatic(..) | hir::ItemConst(..) => {
 487                 // No lifetime parameters, but implied 'static.
 488                 let scope = Scope::Elision {
 489                     elide: Elide::Exact(Region::Static),
 490                     s: ROOT_SCOPE,
 491                 };
 492                 self.with(scope, |_, this| intravisit::walk_item(this, item));
 493             }
 494             hir::ItemTy(_, ref generics)
 495             | hir::ItemEnum(_, ref generics)
 496             | hir::ItemStruct(_, ref generics)
 497             | hir::ItemUnion(_, ref generics)
 498             | hir::ItemTrait(_, _, ref generics, ..)
 499             | hir::ItemTraitAlias(ref generics, ..)
 500             | hir::ItemImpl(_, _, _, ref generics, ..) => {
 501                 // These kinds of items have only early bound lifetime parameters.
 502                 let mut index = if let hir::ItemTrait(..) = item.node {
 503                     1 // Self comes before lifetimes
 504                 } else {
 505                     0
 506                 };
 507                 let lifetimes = generics.lifetimes()
 508                     .map(|def| Region::early(&self.tcx.hir, &mut index, def))
 509                     .collect();
 510                 let next_early_index = index + generics.ty_params().count() as u32;
 511                 let scope = Scope::Binder {
 512                     lifetimes,
 513                     next_early_index,
 514                     abstract_type_parent: true,
 515                     s: ROOT_SCOPE,
 516                 };
 517                 self.with(scope, |old_scope, this| {
 518                     this.check_lifetime_params(old_scope, &generics.params);
 519                     intravisit::walk_item(this, item);
 520                 });
 521             }
 522         }
 523     }
 524
 525     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem) {
 526         match item.node {
 527             hir::ForeignItemFn(ref decl, _, ref generics) => {
 528                 self.visit_early_late(None,
 529                                       decl,
 530                                       generics,
 531                                       |this| {
 532                                           intravisit::walk_foreign_item(this, item);
 533                                       })
 534             }
 535             hir::ForeignItemStatic(..) => {
 536                 intravisit::walk_foreign_item(self, item);
 537             }
 538             hir::ForeignItemType => {
 539                 intravisit::walk_foreign_item(self, item);
 540             }
 541         }
 542     }
 543
 544     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 545         debug!("visit_ty: ty={:?}", ty);
 546         match ty.node {
 547             hir::TyBareFn(ref c) => {
 548                 let next_early_index = self.next_early_index();
 549                 let was_in_fn_syntax = self.is_in_fn_syntax;
 550                 self.is_in_fn_syntax = true;
 551                 let scope = Scope::Binder {
 552                     lifetimes: c.generic_params
 553                         .lifetimes()
 554                         .map(|def| Region::late(&self.tcx.hir, def))
 555                         .collect(),
 556                     s: self.scope,
 557                     next_early_index,
 558                     abstract_type_parent: false,
 559                 };
 560                 self.with(scope, |old_scope, this| {
 561                     // a bare fn has no bounds, so everything
 562                     // contained within is scoped within its binder.
 563                     this.check_lifetime_params(old_scope, &c.generic_params);
 564                     intravisit::walk_ty(this, ty);
 565                 });
 566                 self.is_in_fn_syntax = was_in_fn_syntax;
 567             }
 568             hir::TyTraitObject(ref bounds, ref lifetime) => {
 569                 for bound in bounds {
 570                     self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
 571                 }
 572                 if lifetime.is_elided() {
 573                     self.resolve_object_lifetime_default(lifetime)
 574                 } else {
 575                     self.visit_lifetime(lifetime);
 576                 }
 577             }
 578             hir::TyRptr(ref lifetime_ref, ref mt) => {
 579                 self.visit_lifetime(lifetime_ref);
 580                 let scope = Scope::ObjectLifetimeDefault {
 581                     lifetime: self.map.defs.get(&lifetime_ref.id).cloned(),
 582                     s: self.scope,
 583                 };
 584                 self.with(scope, |_, this| this.visit_ty(&mt.ty));
 585             }
 586             hir::TyImplTraitExistential(ref exist_ty, ref lifetimes) => {
 587                 // Resolve the lifetimes that are applied to the existential type.
 588                 // These are resolved in the current scope.
 589                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 590                 // `fn foo<'a>() -> MyAnonTy<'a> { ... }`
 591                 //          ^                 ^this gets resolved in the current scope
 592                 for lifetime in lifetimes {
 593                     self.visit_lifetime(lifetime);
 594
 595                     // Check for predicates like `impl for<'a> SomeTrait<impl OtherTrait<'a>>`
 596                     // and ban them. Type variables instantiated inside binders aren't
 597                     // well-supported at the moment, so this doesn't work.
 598                     // In the future, this should be fixed and this error should be removed.
 599                     let def = self.map.defs.get(&lifetime.id);
 600                     if let Some(&Region::LateBound(_, def_id, _)) = def {
 601                         if let Some(node_id) = self.tcx.hir.as_local_node_id(def_id) {
 602                             // Ensure that the parent of the def is an item, not HRTB
 603                             let parent_id = self.tcx.hir.get_parent_node(node_id);
 604                             let parent_impl_id = hir::ImplItemId { node_id: parent_id };
 605                             let parent_trait_id = hir::TraitItemId { node_id: parent_id };
 606                             let krate = self.tcx.hir.forest.krate();
 607                             if !(krate.items.contains_key(&parent_id)
 608                                 || krate.impl_items.contains_key(&parent_impl_id)
 609                                 || krate.trait_items.contains_key(&parent_trait_id))
 610                             {
 611                                 span_err!(
 612                                     self.tcx.sess,
 613                                     lifetime.span,
 614                                     E0657,
 615                                     "`impl Trait` can only capture lifetimes \
 616                                      bound at the fn or impl level"
 617                                 );
 618                             }
 619                         }
 620                     }
 621                 }
 622
 623                 // Resolve the lifetimes in the bounds to the lifetime defs in the generics.
 624                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 625                 // `abstract type MyAnonTy<'b>: MyTrait<'b>;`
 626                 //                          ^            ^ this gets resolved in the scope of
 627                 //                                         the exist_ty generics
 628                 let hir::ExistTy {
 629                     ref generics,
 630                     ref bounds,
 631                 } = *exist_ty;
 632
 633                 // We want to start our early-bound indices at the end of the parent scope,
 634                 // not including any parent `impl Trait`s.
 635                 let mut index = self.next_early_index_for_abstract_type();
 636                 debug!("visit_ty: index = {}", index);
 637
 638                 let mut elision = None;
 639                 let mut lifetimes = FxHashMap();
 640                 for lt_def in generics.lifetimes() {
 641                     let (lt_name, region) = Region::early(&self.tcx.hir, &mut index, &lt_def);
 642                     if let hir::LifetimeName::Underscore = lt_name {
 643                         // Pick the elided lifetime "definition" if one exists and use it to make an
 644                         // elision scope.
 645                         elision = Some(region);
 646                     } else {
 647                         lifetimes.insert(lt_name, region);
 648                     }
 649                 }
 650
 651                 let next_early_index = index + generics.ty_params().count() as u32;
 652
 653                 if let Some(elision_region) = elision {
 654                     let scope = Scope::Elision {
 655                         elide: Elide::Exact(elision_region),
 656                         s: self.scope
 657                     };
 658                     self.with(scope, |_old_scope, this| {
 659                         let scope = Scope::Binder {
 660                             lifetimes,
 661                             next_early_index,
 662                             s: this.scope,
 663                             abstract_type_parent: false,
 664                         };
 665                         this.with(scope, |_old_scope, this| {
 666                             this.visit_generics(generics);
 667                             for bound in bounds {
 668                                 this.visit_ty_param_bound(bound);
 669                             }
 670                         });
 671                     });
 672                 } else {
 673                     let scope = Scope::Binder {
 674                         lifetimes,
 675                         next_early_index,
 676                         s: self.scope,
 677                         abstract_type_parent: false,
 678                     };
 679                     self.with(scope, |_old_scope, this| {
 680                         this.visit_generics(generics);
 681                         for bound in bounds {
 682                             this.visit_ty_param_bound(bound);
 683                         }
 684                     });
 685                 }
 686             }
 687             _ => intravisit::walk_ty(self, ty),
 688         }
 689     }
 690
 691     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 692         use self::hir::TraitItemKind::*;
 693         match trait_item.node {
 694             Method(ref sig, _) => {
 695                 let tcx = self.tcx;
 696                 self.visit_early_late(
 697                     Some(tcx.hir.get_parent(trait_item.id)),
 698                     &sig.decl,
 699                     &trait_item.generics,
 700                     |this| intravisit::walk_trait_item(this, trait_item),
 701                 );
 702             },
 703             Type(ref bounds, ref ty) => {
 704                 let generics = &trait_item.generics;
 705                 let mut index = self.next_early_index();
 706                 debug!("visit_ty: index = {}", index);
 707                 let lifetimes = generics.lifetimes()
 708                     .map(|lt_def| Region::early(&self.tcx.hir, &mut index, lt_def))
 709                     .collect();
 710
 711                 let next_early_index = index + generics.ty_params().count() as u32;
 712                 let scope = Scope::Binder {
 713                     lifetimes,
 714                     next_early_index,
 715                     s: self.scope,
 716                     abstract_type_parent: true,
 717                 };
 718                 self.with(scope, |_old_scope, this| {
 719                     this.visit_generics(generics);
 720                     for bound in bounds {
 721                         this.visit_ty_param_bound(bound);
 722                     }
 723                     if let Some(ty) = ty {
 724                         this.visit_ty(ty);
 725                     }
 726                 });
 727             },
 728             Const(_, _) => {
 729                 // Only methods and types support generics.
 730                 assert!(trait_item.generics.params.is_empty());
 731                 intravisit::walk_trait_item(self, trait_item);
 732             },
 733         }
 734     }
 735
 736     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 737         use self::hir::ImplItemKind::*;
 738         match impl_item.node {
 739             Method(ref sig, _) => {
 740                 let tcx = self.tcx;
 741                 self.visit_early_late(
 742                     Some(tcx.hir.get_parent(impl_item.id)),
 743                     &sig.decl,
 744                     &impl_item.generics,
 745                     |this| intravisit::walk_impl_item(this, impl_item),
 746                 )
 747             },
 748             Type(ref ty) => {
 749                 let generics = &impl_item.generics;
 750                 let mut index = self.next_early_index();
 751                 debug!("visit_ty: index = {}", index);
 752                 let lifetimes = generics.lifetimes()
 753                     .map(|lt_def| Region::early(&self.tcx.hir, &mut index, lt_def))
 754                     .collect();
 755
 756                 let next_early_index = index + generics.ty_params().count() as u32;
 757                 let scope = Scope::Binder {
 758                     lifetimes,
 759                     next_early_index,
 760                     s: self.scope,
 761                     abstract_type_parent: true,
 762                 };
 763                 self.with(scope, |_old_scope, this| {
 764                     this.visit_generics(generics);
 765                     this.visit_ty(ty);
 766                 });
 767             },
 768             Const(_, _) => {
 769                 // Only methods and types support generics.
 770                 assert!(impl_item.generics.params.is_empty());
 771                 intravisit::walk_impl_item(self, impl_item);
 772             },
 773         }
 774     }
 775
 776     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
 777         if lifetime_ref.is_elided() {
 778             self.resolve_elided_lifetimes(slice::from_ref(lifetime_ref), false);
 779             return;
 780         }
 781         if lifetime_ref.is_static() {
 782             self.insert_lifetime(lifetime_ref, Region::Static);
 783             return;
 784         }
 785         self.resolve_lifetime_ref(lifetime_ref);
 786     }
 787
 788     fn visit_path(&mut self, path: &'tcx hir::Path, _: ast::NodeId) {
 789         for (i, segment) in path.segments.iter().enumerate() {
 790             let depth = path.segments.len() - i - 1;
 791             if let Some(ref parameters) = segment.parameters {
 792                 self.visit_segment_parameters(path.def, depth, parameters);
 793             }
 794         }
 795     }
 796
 797     fn visit_fn_decl(&mut self, fd: &'tcx hir::FnDecl) {
 798         let output = match fd.output {
 799             hir::DefaultReturn(_) => None,
 800             hir::Return(ref ty) => Some(ty),
 801         };
 802         self.visit_fn_like_elision(&fd.inputs, output);
 803     }
 804
 805     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 806         check_mixed_explicit_and_in_band_defs(
 807             self.tcx,
 808             &generics.lifetimes().cloned().collect::<Vec<_>>()
 809         );
 810         for ty_param in generics.ty_params() {
 811             walk_list!(self, visit_ty_param_bound, &ty_param.bounds);
 812             if let Some(ref ty) = ty_param.default {
 813                 self.visit_ty(&ty);
 814             }
 815         }
 816         for predicate in &generics.where_clause.predicates {
 817             match predicate {
 818                 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
 819                     ref bounded_ty,
 820                     ref bounds,
 821                     ref bound_generic_params,
 822                     ..
 823                 }) => {
 824                     if bound_generic_params.iter().any(|p| p.is_lifetime_param()) {
 825                         self.trait_ref_hack = true;
 826                         let next_early_index = self.next_early_index();
 827                         let scope = Scope::Binder {
 828                             lifetimes: bound_generic_params.lifetimes()
 829                                 .map(|def| Region::late(&self.tcx.hir, def))
 830                                 .collect(),
 831                             s: self.scope,
 832                             next_early_index,
 833                             abstract_type_parent: false,
 834                         };
 835                         let result = self.with(scope, |old_scope, this| {
 836                             this.check_lifetime_params(old_scope, &bound_generic_params);
 837                             this.visit_ty(&bounded_ty);
 838                             walk_list!(this, visit_ty_param_bound, bounds);
 839                         });
 840                         self.trait_ref_hack = false;
 841                         result
 842                     } else {
 843                         self.visit_ty(&bounded_ty);
 844                         walk_list!(self, visit_ty_param_bound, bounds);
 845                     }
 846                 }
 847                 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
 848                     ref lifetime,
 849                     ref bounds,
 850                     ..
 851                 }) => {
 852                     self.visit_lifetime(lifetime);
 853                     for bound in bounds {
 854                         self.visit_lifetime(bound);
 855                     }
 856                 }
 857                 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
 858                     ref lhs_ty,
 859                     ref rhs_ty,
 860                     ..
 861                 }) => {
 862                     self.visit_ty(lhs_ty);
 863                     self.visit_ty(rhs_ty);
 864                 }
 865             }
 866         }
 867     }
 868
 869     fn visit_poly_trait_ref(
 870         &mut self,
 871         trait_ref: &'tcx hir::PolyTraitRef,
 872         _modifier: hir::TraitBoundModifier,
 873     ) {
 874         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 875
 876         if !self.trait_ref_hack ||
 877             trait_ref.bound_generic_params.iter().any(|p| p.is_lifetime_param())
 878         {
 879             if self.trait_ref_hack {
 880                 span_err!(
 881                     self.tcx.sess,
 882                     trait_ref.span,
 883                     E0316,
 884                     "nested quantification of lifetimes"
 885                 );
 886             }
 887             let next_early_index = self.next_early_index();
 888             let scope = Scope::Binder {
 889                 lifetimes: trait_ref.bound_generic_params
 890                     .lifetimes()
 891                     .map(|def| Region::late(&self.tcx.hir, def))
 892                     .collect(),
 893                 s: self.scope,
 894                 next_early_index,
 895                 abstract_type_parent: false,
 896             };
 897             self.with(scope, |old_scope, this| {
 898                 this.check_lifetime_params(old_scope, &trait_ref.bound_generic_params);
 899                 walk_list!(this, visit_generic_param, &trait_ref.bound_generic_params);
 900                 this.visit_trait_ref(&trait_ref.trait_ref)
 901             })
 902         } else {
 903             self.visit_trait_ref(&trait_ref.trait_ref)
 904         }
 905     }
 906 }
 907
 908 #[derive(Copy, Clone, PartialEq)]
 909 enum ShadowKind {
 910     Label,
 911     Lifetime,
 912 }
 913 struct Original {
 914     kind: ShadowKind,
 915     span: Span,
 916 }
 917 struct Shadower {
 918     kind: ShadowKind,
 919     span: Span,
 920 }
 921
 922 fn original_label(span: Span) -> Original {
 923     Original {
 924         kind: ShadowKind::Label,
 925         span: span,
 926     }
 927 }
 928 fn shadower_label(span: Span) -> Shadower {
 929     Shadower {
 930         kind: ShadowKind::Label,
 931         span: span,
 932     }
 933 }
 934 fn original_lifetime(span: Span) -> Original {
 935     Original {
 936         kind: ShadowKind::Lifetime,
 937         span: span,
 938     }
 939 }
 940 fn shadower_lifetime(l: &hir::Lifetime) -> Shadower {
 941     Shadower {
 942         kind: ShadowKind::Lifetime,
 943         span: l.span,
 944     }
 945 }
 946
 947 impl ShadowKind {
 948     fn desc(&self) -> &'static str {
 949         match *self {
 950             ShadowKind::Label => "label",
 951             ShadowKind::Lifetime => "lifetime",
 952         }
 953     }
 954 }
 955
 956 fn check_mixed_explicit_and_in_band_defs(
 957     tcx: TyCtxt<'_, '_, '_>,
 958     lifetime_defs: &[hir::LifetimeDef],
 959 ) {
 960     let oob_def = lifetime_defs.iter().find(|lt| !lt.in_band);
 961     let in_band_def = lifetime_defs.iter().find(|lt| lt.in_band);
 962
 963     if let (Some(oob_def), Some(in_band_def)) = (oob_def, in_band_def) {
 964         struct_span_err!(
 965             tcx.sess,
 966             in_band_def.lifetime.span,
 967             E0688,
 968             "cannot mix in-band and explicit lifetime definitions"
 969         ).span_label(
 970             in_band_def.lifetime.span,
 971             "in-band lifetime definition here",
 972         )
 973             .span_label(oob_def.lifetime.span, "explicit lifetime definition here")
 974             .emit();
 975     }
 976 }
 977
 978 fn signal_shadowing_problem(
 979     tcx: TyCtxt<'_, '_, '_>,
 980     name: ast::Name,
 981     orig: Original,
 982     shadower: Shadower,
 983 ) {
 984     let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
 985         // lifetime/lifetime shadowing is an error
 986         struct_span_err!(
 987             tcx.sess,
 988             shadower.span,
 989             E0496,
 990             "{} name `{}` shadows a \
 991              {} name that is already in scope",
 992             shadower.kind.desc(),
 993             name,
 994             orig.kind.desc()
 995         )
 996     } else {
 997         // shadowing involving a label is only a warning, due to issues with
 998         // labels and lifetimes not being macro-hygienic.
 999         tcx.sess.struct_span_warn(
1000             shadower.span,
1001             &format!(
1002                 "{} name `{}` shadows a \
1003                  {} name that is already in scope",
1004                 shadower.kind.desc(),
1005                 name,
1006                 orig.kind.desc()
1007             ),
1008         )
1009     };
1010     err.span_label(orig.span, "first declared here");
1011     err.span_label(shadower.span, format!("lifetime {} already in scope", name));
1012     err.emit();
1013 }
1014
1015 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
1016 // if one of the label shadows a lifetime or another label.
1017 fn extract_labels(ctxt: &mut LifetimeContext<'_, '_>, body: &hir::Body) {
1018     struct GatherLabels<'a, 'tcx: 'a> {
1019         tcx: TyCtxt<'a, 'tcx, 'tcx>,
1020         scope: ScopeRef<'a>,
1021         labels_in_fn: &'a mut Vec<(ast::Name, Span)>,
1022     }
1023
1024     let mut gather = GatherLabels {
1025         tcx: ctxt.tcx,
1026         scope: ctxt.scope,
1027         labels_in_fn: &mut ctxt.labels_in_fn,
1028     };
1029     gather.visit_body(body);
1030
1031     impl<'v, 'a, 'tcx> Visitor<'v> for GatherLabels<'a, 'tcx> {
1032         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1033             NestedVisitorMap::None
1034         }
1035
1036         fn visit_expr(&mut self, ex: &hir::Expr) {
1037             if let Some((label, label_span)) = expression_label(ex) {
1038                 for &(prior, prior_span) in &self.labels_in_fn[..] {
1039                     // FIXME (#24278): non-hygienic comparison
1040                     if label == prior {
1041                         signal_shadowing_problem(
1042                             self.tcx,
1043                             label,
1044                             original_label(prior_span),
1045                             shadower_label(label_span),
1046                         );
1047                     }
1048                 }
1049
1050                 check_if_label_shadows_lifetime(self.tcx, self.scope, label, label_span);
1051
1052                 self.labels_in_fn.push((label, label_span));
1053             }
1054             intravisit::walk_expr(self, ex)
1055         }
1056     }
1057
1058     fn expression_label(ex: &hir::Expr) -> Option<(ast::Name, Span)> {
1059         match ex.node {
1060             hir::ExprWhile(.., Some(label)) | hir::ExprLoop(_, Some(label), _) => {
1061                 Some((label.name, label.span))
1062             }
1063             _ => None,
1064         }
1065     }
1066
1067     fn check_if_label_shadows_lifetime(
1068         tcx: TyCtxt<'_, '_, '_>,
1069         mut scope: ScopeRef<'_>,
1070         label: ast::Name,
1071         label_span: Span,
1072     ) {
1073         loop {
1074             match *scope {
1075                 Scope::Body { s, .. }
1076                 | Scope::Elision { s, .. }
1077                 | Scope::ObjectLifetimeDefault { s, .. } => {
1078                     scope = s;
1079                 }
1080
1081                 Scope::Root => {
1082                     return;
1083                 }
1084
1085                 Scope::Binder {
1086                     ref lifetimes,
1087                     s,
1088                     next_early_index: _,
1089                     abstract_type_parent: _,
1090                 } => {
1091                     // FIXME (#24278): non-hygienic comparison
1092                     if let Some(def) = lifetimes.get(&hir::LifetimeName::Name(label)) {
1093                         let node_id = tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
1094
1095                         signal_shadowing_problem(
1096                             tcx,
1097                             label,
1098                             original_lifetime(tcx.hir.span(node_id)),
1099                             shadower_label(label_span),
1100                         );
1101                         return;
1102                     }
1103                     scope = s;
1104                 }
1105             }
1106         }
1107     }
1108 }
1109
1110 fn compute_object_lifetime_defaults(
1111     tcx: TyCtxt<'_, '_, '_>,
1112 ) -> NodeMap<Vec<ObjectLifetimeDefault>> {
1113     let mut map = NodeMap();
1114     for item in tcx.hir.krate().items.values() {
1115         match item.node {
1116             hir::ItemStruct(_, ref generics)
1117             | hir::ItemUnion(_, ref generics)
1118             | hir::ItemEnum(_, ref generics)
1119             | hir::ItemTy(_, ref generics)
1120             | hir::ItemTrait(_, _, ref generics, ..) => {
1121                 let result = object_lifetime_defaults_for_item(tcx, generics);
1122
1123                 // Debugging aid.
1124                 if attr::contains_name(&item.attrs, "rustc_object_lifetime_default") {
1125                     let object_lifetime_default_reprs: String = result
1126                         .iter()
1127                         .map(|set| match *set {
1128                             Set1::Empty => "BaseDefault".to_string(),
1129                             Set1::One(Region::Static) => "'static".to_string(),
1130                             Set1::One(Region::EarlyBound(i, _, _)) => generics.lifetimes()
1131                                 .nth(i as usize)
1132                                 .unwrap()
1133                                 .lifetime
1134                                 .name
1135                                 .name()
1136                                 .to_string(),
1137                             Set1::One(_) => bug!(),
1138                             Set1::Many => "Ambiguous".to_string(),
1139                         })
1140                         .collect::<Vec<String>>()
1141                         .join(",");
1142                     tcx.sess.span_err(item.span, &object_lifetime_default_reprs);
1143                 }
1144
1145                 map.insert(item.id, result);
1146             }
1147             _ => {}
1148         }
1149     }
1150     map
1151 }
1152
1153 /// Scan the bounds and where-clauses on parameters to extract bounds
1154 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
1155 /// for each type parameter.
1156 fn object_lifetime_defaults_for_item(
1157     tcx: TyCtxt<'_, '_, '_>,
1158     generics: &hir::Generics,
1159 ) -> Vec<ObjectLifetimeDefault> {
1160     fn add_bounds(set: &mut Set1<hir::LifetimeName>, bounds: &[hir::TyParamBound]) {
1161         for bound in bounds {
1162             if let hir::RegionTyParamBound(ref lifetime) = *bound {
1163                 set.insert(lifetime.name);
1164             }
1165         }
1166     }
1167
1168     generics.ty_params()
1169         .map(|param| {
1170             let mut set = Set1::Empty;
1171
1172             add_bounds(&mut set, &param.bounds);
1173
1174             let param_def_id = tcx.hir.local_def_id(param.id);
1175             for predicate in &generics.where_clause.predicates {
1176                 // Look for `type: ...` where clauses.
1177                 let data = match *predicate {
1178                     hir::WherePredicate::BoundPredicate(ref data) => data,
1179                     _ => continue,
1180                 };
1181
1182                 // Ignore `for<'a> type: ...` as they can change what
1183                 // lifetimes mean (although we could "just" handle it).
1184                 if !data.bound_generic_params.is_empty() {
1185                     continue;
1186                 }
1187
1188                 let def = match data.bounded_ty.node {
1189                     hir::TyPath(hir::QPath::Resolved(None, ref path)) => path.def,
1190                     _ => continue,
1191                 };
1192
1193                 if def == Def::TyParam(param_def_id) {
1194                     add_bounds(&mut set, &data.bounds);
1195                 }
1196             }
1197
1198             match set {
1199                 Set1::Empty => Set1::Empty,
1200                 Set1::One(name) => {
1201                     if name == hir::LifetimeName::Static {
1202                         Set1::One(Region::Static)
1203                     } else {
1204                         generics
1205                             .lifetimes()
1206                             .enumerate()
1207                             .find(|&(_, def)| def.lifetime.name == name)
1208                             .map_or(Set1::Many, |(i, def)| {
1209                                 let def_id = tcx.hir.local_def_id(def.lifetime.id);
1210                                 let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
1211                                 Set1::One(Region::EarlyBound(i as u32, def_id, origin))
1212                             })
1213                     }
1214                 }
1215                 Set1::Many => Set1::Many,
1216             }
1217         })
1218         .collect()
1219 }
1220
1221 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
1222     // FIXME(#37666) this works around a limitation in the region inferencer
1223     fn hack<F>(&mut self, f: F)
1224     where
1225         F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
1226     {
1227         f(self)
1228     }
1229
1230     fn with<F>(&mut self, wrap_scope: Scope, f: F)
1231     where
1232         F: for<'b> FnOnce(ScopeRef, &mut LifetimeContext<'b, 'tcx>),
1233     {
1234         let LifetimeContext {
1235             tcx, ref mut map, ..
1236         } = *self;
1237         let labels_in_fn = replace(&mut self.labels_in_fn, vec![]);
1238         let xcrate_object_lifetime_defaults =
1239             replace(&mut self.xcrate_object_lifetime_defaults, DefIdMap());
1240         let mut this = LifetimeContext {
1241             tcx,
1242             map: *map,
1243             scope: &wrap_scope,
1244             trait_ref_hack: self.trait_ref_hack,
1245             is_in_fn_syntax: self.is_in_fn_syntax,
1246             labels_in_fn,
1247             xcrate_object_lifetime_defaults,
1248             lifetime_uses: DefIdMap(),
1249         };
1250         debug!("entering scope {:?}", this.scope);
1251         f(self.scope, &mut this);
1252         debug!("exiting scope {:?}", this.scope);
1253         self.labels_in_fn = this.labels_in_fn;
1254         self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
1255
1256         for (def_id, lifetimeuseset) in &this.lifetime_uses {
1257             match lifetimeuseset {
1258                 &LifetimeUseSet::One(_) => {
1259                     let node_id = this.tcx.hir.as_local_node_id(*def_id).unwrap();
1260                     debug!("node id first={:?}", node_id);
1261                     if let hir::map::NodeLifetime(hir_lifetime) = this.tcx.hir.get(node_id) {
1262                         let span = hir_lifetime.span;
1263                         let id = hir_lifetime.id;
1264                         debug!("id ={:?} span = {:?} hir_lifetime = {:?}",
1265                             node_id,
1266                             span,
1267                             hir_lifetime);
1268
1269                         this.tcx
1270                             .struct_span_lint_node(lint::builtin::SINGLE_USE_LIFETIME,
1271                                                    id,
1272                                                    span,
1273                                                    &format!("lifetime name `{}` only used once",
1274                                                    hir_lifetime.name.name()))
1275                             .emit();
1276                     }
1277                 }
1278                 _ => {
1279                     debug!("Not one use lifetime");
1280                 }
1281             }
1282         }
1283     }
1284
1285     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
1286     ///
1287     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
1288     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
1289     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
1290     ///
1291     /// For example:
1292     ///
1293     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
1294     ///
1295     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
1296     /// lifetimes may be interspersed together.
1297     ///
1298     /// If early bound lifetimes are present, we separate them into their own list (and likewise
1299     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
1300     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
1301     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
1302     /// ordering is not important there.
1303     fn visit_early_late<F>(
1304         &mut self,
1305         parent_id: Option<ast::NodeId>,
1306         decl: &'tcx hir::FnDecl,
1307         generics: &'tcx hir::Generics,
1308         walk: F,
1309     ) where
1310         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
1311     {
1312         insert_late_bound_lifetimes(self.map, decl, generics);
1313
1314         // Find the start of nested early scopes, e.g. in methods.
1315         let mut index = 0;
1316         if let Some(parent_id) = parent_id {
1317             let parent = self.tcx.hir.expect_item(parent_id);
1318             if let hir::ItemTrait(..) = parent.node {
1319                 index += 1; // Self comes first.
1320             }
1321             match parent.node {
1322                 hir::ItemTrait(_, _, ref generics, ..)
1323                 | hir::ItemImpl(_, _, _, ref generics, ..) => {
1324                     index += generics.params.len() as u32;
1325                 }
1326                 _ => {}
1327             }
1328         }
1329
1330         let lifetimes = generics
1331             .lifetimes()
1332             .map(|def| {
1333                 if self.map.late_bound.contains(&def.lifetime.id) {
1334                     Region::late(&self.tcx.hir, def)
1335                 } else {
1336                     Region::early(&self.tcx.hir, &mut index, def)
1337                 }
1338             })
1339             .collect();
1340
1341         let next_early_index = index + generics.ty_params().count() as u32;
1342
1343         let scope = Scope::Binder {
1344             lifetimes,
1345             next_early_index,
1346             s: self.scope,
1347             abstract_type_parent: true,
1348         };
1349         self.with(scope, move |old_scope, this| {
1350             this.check_lifetime_params(old_scope, &generics.params);
1351             this.hack(walk); // FIXME(#37666) workaround in place of `walk(this)`
1352         });
1353     }
1354
1355     fn next_early_index_helper(&self, only_abstract_type_parent: bool) -> u32 {
1356         let mut scope = self.scope;
1357         loop {
1358             match *scope {
1359                 Scope::Root => return 0,
1360
1361                 Scope::Binder {
1362                     next_early_index,
1363                     abstract_type_parent,
1364                     ..
1365                 } if (!only_abstract_type_parent || abstract_type_parent)
1366                 => return next_early_index,
1367
1368                 Scope::Binder { s, .. }
1369                 | Scope::Body { s, .. }
1370                 | Scope::Elision { s, .. }
1371                 | Scope::ObjectLifetimeDefault { s, .. } => scope = s,
1372             }
1373         }
1374     }
1375
1376     /// Returns the next index one would use for an early-bound-region
1377     /// if extending the current scope.
1378     fn next_early_index(&self) -> u32 {
1379         self.next_early_index_helper(true)
1380     }
1381
1382     /// Returns the next index one would use for an `impl Trait` that
1383     /// is being converted into an `abstract type`. This will be the
1384     /// next early index from the enclosing item, for the most
1385     /// part. See the `abstract_type_parent` field for more info.
1386     fn next_early_index_for_abstract_type(&self) -> u32 {
1387         self.next_early_index_helper(false)
1388     }
1389
1390     fn resolve_lifetime_ref(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
1391         debug!("resolve_lifetime_ref(lifetime_ref={:?})", lifetime_ref);
1392         // Walk up the scope chain, tracking the number of fn scopes
1393         // that we pass through, until we find a lifetime with the
1394         // given name or we run out of scopes.
1395         // search.
1396         let mut late_depth = 0;
1397         let mut scope = self.scope;
1398         let mut outermost_body = None;
1399         let result = loop {
1400             match *scope {
1401                 Scope::Body { id, s } => {
1402                     outermost_body = Some(id);
1403                     scope = s;
1404                 }
1405
1406                 Scope::Root => {
1407                     break None;
1408                 }
1409
1410                 Scope::Binder {
1411                     ref lifetimes,
1412                     s,
1413                     next_early_index: _,
1414                     abstract_type_parent: _,
1415                 } => {
1416                     if let Some(&def) = lifetimes.get(&lifetime_ref.name) {
1417                         break Some(def.shifted(late_depth));
1418                     } else {
1419                         late_depth += 1;
1420                         scope = s;
1421                     }
1422                 }
1423
1424                 Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
1425                     scope = s;
1426                 }
1427             }
1428         };
1429
1430         if let Some(mut def) = result {
1431             if let Region::EarlyBound(..) = def {
1432                 // Do not free early-bound regions, only late-bound ones.
1433             } else if let Some(body_id) = outermost_body {
1434                 let fn_id = self.tcx.hir.body_owner(body_id);
1435                 match self.tcx.hir.get(fn_id) {
1436                     hir::map::NodeItem(&hir::Item {
1437                         node: hir::ItemFn(..),
1438                         ..
1439                     })
1440                     | hir::map::NodeTraitItem(&hir::TraitItem {
1441                         node: hir::TraitItemKind::Method(..),
1442                         ..
1443                     })
1444                     | hir::map::NodeImplItem(&hir::ImplItem {
1445                         node: hir::ImplItemKind::Method(..),
1446                         ..
1447                     }) => {
1448                         let scope = self.tcx.hir.local_def_id(fn_id);
1449                         def = Region::Free(scope, def.id().unwrap());
1450                     }
1451                     _ => {}
1452                 }
1453             }
1454
1455             // Check for fn-syntax conflicts with in-band lifetime definitions
1456             if self.is_in_fn_syntax {
1457                 match def {
1458                     Region::EarlyBound(_, _, LifetimeDefOrigin::InBand)
1459                     | Region::LateBound(_, _, LifetimeDefOrigin::InBand) => {
1460                         struct_span_err!(
1461                             self.tcx.sess,
1462                             lifetime_ref.span,
1463                             E0687,
1464                             "lifetimes used in `fn` or `Fn` syntax must be \
1465                              explicitly declared using `<...>` binders"
1466                         ).span_label(lifetime_ref.span, "in-band lifetime definition")
1467                             .emit();
1468                     }
1469
1470                     Region::Static
1471                     | Region::EarlyBound(_, _, LifetimeDefOrigin::Explicit)
1472                     | Region::LateBound(_, _, LifetimeDefOrigin::Explicit)
1473                     | Region::LateBoundAnon(..)
1474                     | Region::Free(..) => {}
1475                 }
1476             }
1477
1478             self.insert_lifetime(lifetime_ref, def);
1479         } else {
1480             struct_span_err!(
1481                 self.tcx.sess,
1482                 lifetime_ref.span,
1483                 E0261,
1484                 "use of undeclared lifetime name `{}`",
1485                 lifetime_ref.name.name()
1486             ).span_label(lifetime_ref.span, "undeclared lifetime")
1487                 .emit();
1488         }
1489     }
1490
1491     fn visit_segment_parameters(
1492         &mut self,
1493         def: Def,
1494         depth: usize,
1495         params: &'tcx hir::PathParameters,
1496     ) {
1497         if params.parenthesized {
1498             let was_in_fn_syntax = self.is_in_fn_syntax;
1499             self.is_in_fn_syntax = true;
1500             self.visit_fn_like_elision(params.inputs(), Some(&params.bindings[0].ty));
1501             self.is_in_fn_syntax = was_in_fn_syntax;
1502             return;
1503         }
1504
1505         if params.lifetimes.iter().all(|l| l.is_elided()) {
1506             self.resolve_elided_lifetimes(&params.lifetimes, true);
1507         } else {
1508             for l in &params.lifetimes {
1509                 self.visit_lifetime(l);
1510             }
1511         }
1512
1513         // Figure out if this is a type/trait segment,
1514         // which requires object lifetime defaults.
1515         let parent_def_id = |this: &mut Self, def_id: DefId| {
1516             let def_key = this.tcx.def_key(def_id);
1517             DefId {
1518                 krate: def_id.krate,
1519                 index: def_key.parent.expect("missing parent"),
1520             }
1521         };
1522         let type_def_id = match def {
1523             Def::AssociatedTy(def_id) if depth == 1 => Some(parent_def_id(self, def_id)),
1524             Def::Variant(def_id) if depth == 0 => Some(parent_def_id(self, def_id)),
1525             Def::Struct(def_id)
1526             | Def::Union(def_id)
1527             | Def::Enum(def_id)
1528             | Def::TyAlias(def_id)
1529             | Def::Trait(def_id) if depth == 0 =>
1530             {
1531                 Some(def_id)
1532             }
1533             _ => None,
1534         };
1535
1536         let object_lifetime_defaults = type_def_id.map_or(vec![], |def_id| {
1537             let in_body = {
1538                 let mut scope = self.scope;
1539                 loop {
1540                     match *scope {
1541                         Scope::Root => break false,
1542
1543                         Scope::Body { .. } => break true,
1544
1545                         Scope::Binder { s, .. }
1546                         | Scope::Elision { s, .. }
1547                         | Scope::ObjectLifetimeDefault { s, .. } => {
1548                             scope = s;
1549                         }
1550                     }
1551                 }
1552             };
1553
1554             let map = &self.map;
1555             let unsubst = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1556                 &map.object_lifetime_defaults[&id]
1557             } else {
1558                 let tcx = self.tcx;
1559                 self.xcrate_object_lifetime_defaults
1560                     .entry(def_id)
1561                     .or_insert_with(|| {
1562                         tcx.generics_of(def_id)
1563                             .types
1564                             .iter()
1565                             .map(|def| def.object_lifetime_default)
1566                             .collect()
1567                     })
1568             };
1569             unsubst
1570                 .iter()
1571                 .map(|set| match *set {
1572                     Set1::Empty => if in_body {
1573                         None
1574                     } else {
1575                         Some(Region::Static)
1576                     },
1577                     Set1::One(r) => r.subst(&params.lifetimes, map),
1578                     Set1::Many => None,
1579                 })
1580                 .collect()
1581         });
1582
1583         for (i, ty) in params.types.iter().enumerate() {
1584             if let Some(&lt) = object_lifetime_defaults.get(i) {
1585                 let scope = Scope::ObjectLifetimeDefault {
1586                     lifetime: lt,
1587                     s: self.scope,
1588                 };
1589                 self.with(scope, |_, this| this.visit_ty(ty));
1590             } else {
1591                 self.visit_ty(ty);
1592             }
1593         }
1594
1595         for b in &params.bindings {
1596             self.visit_assoc_type_binding(b);
1597         }
1598     }
1599
1600     fn visit_fn_like_elision(
1601         &mut self,
1602         inputs: &'tcx [P<hir::Ty>],
1603         output: Option<&'tcx P<hir::Ty>>,
1604     ) {
1605         let mut arg_elide = Elide::FreshLateAnon(Cell::new(0));
1606         let arg_scope = Scope::Elision {
1607             elide: arg_elide.clone(),
1608             s: self.scope,
1609         };
1610         self.with(arg_scope, |_, this| {
1611             for input in inputs {
1612                 this.visit_ty(input);
1613             }
1614             match *this.scope {
1615                 Scope::Elision { ref elide, .. } => {
1616                     arg_elide = elide.clone();
1617                 }
1618                 _ => bug!(),
1619             }
1620         });
1621
1622         let output = match output {
1623             Some(ty) => ty,
1624             None => return,
1625         };
1626
1627         // Figure out if there's a body we can get argument names from,
1628         // and whether there's a `self` argument (treated specially).
1629         let mut assoc_item_kind = None;
1630         let mut impl_self = None;
1631         let parent = self.tcx.hir.get_parent_node(output.id);
1632         let body = match self.tcx.hir.get(parent) {
1633             // `fn` definitions and methods.
1634             hir::map::NodeItem(&hir::Item {
1635                 node: hir::ItemFn(.., body),
1636                 ..
1637             }) => Some(body),
1638
1639             hir::map::NodeTraitItem(&hir::TraitItem {
1640                 node: hir::TraitItemKind::Method(_, ref m),
1641                 ..
1642             }) => {
1643                 match self.tcx
1644                     .hir
1645                     .expect_item(self.tcx.hir.get_parent(parent))
1646                     .node
1647                 {
1648                     hir::ItemTrait(.., ref trait_items) => {
1649                         assoc_item_kind = trait_items
1650                             .iter()
1651                             .find(|ti| ti.id.node_id == parent)
1652                             .map(|ti| ti.kind);
1653                     }
1654                     _ => {}
1655                 }
1656                 match *m {
1657                     hir::TraitMethod::Required(_) => None,
1658                     hir::TraitMethod::Provided(body) => Some(body),
1659                 }
1660             }
1661
1662             hir::map::NodeImplItem(&hir::ImplItem {
1663                 node: hir::ImplItemKind::Method(_, body),
1664                 ..
1665             }) => {
1666                 match self.tcx
1667                     .hir
1668                     .expect_item(self.tcx.hir.get_parent(parent))
1669                     .node
1670                 {
1671                     hir::ItemImpl(.., ref self_ty, ref impl_items) => {
1672                         impl_self = Some(self_ty);
1673                         assoc_item_kind = impl_items
1674                             .iter()
1675                             .find(|ii| ii.id.node_id == parent)
1676                             .map(|ii| ii.kind);
1677                     }
1678                     _ => {}
1679                 }
1680                 Some(body)
1681             }
1682
1683             // Foreign functions, `fn(...) -> R` and `Trait(...) -> R` (both types and bounds).
1684             hir::map::NodeForeignItem(_) | hir::map::NodeTy(_) | hir::map::NodeTraitRef(_) =>
1685                 None,
1686             // Everything else (only closures?) doesn't
1687             // actually enjoy elision in return types.
1688             _ => {
1689                 self.visit_ty(output);
1690                 return;
1691             }
1692         };
1693
1694         let has_self = match assoc_item_kind {
1695             Some(hir::AssociatedItemKind::Method { has_self }) => has_self,
1696             _ => false,
1697         };
1698
1699         // In accordance with the rules for lifetime elision, we can determine
1700         // what region to use for elision in the output type in two ways.
1701         // First (determined here), if `self` is by-reference, then the
1702         // implied output region is the region of the self parameter.
1703         if has_self {
1704             // Look for `self: &'a Self` - also desugared from `&'a self`,
1705             // and if that matches, use it for elision and return early.
1706             let is_self_ty = |def: Def| {
1707                 if let Def::SelfTy(..) = def {
1708                     return true;
1709                 }
1710
1711                 // Can't always rely on literal (or implied) `Self` due
1712                 // to the way elision rules were originally specified.
1713                 let impl_self = impl_self.map(|ty| &ty.node);
1714                 if let Some(&hir::TyPath(hir::QPath::Resolved(None, ref path))) = impl_self {
1715                     match path.def {
1716                         // Whitelist the types that unambiguously always
1717                         // result in the same type constructor being used
1718                         // (it can't differ between `Self` and `self`).
1719                         Def::Struct(_) | Def::Union(_) | Def::Enum(_) | Def::PrimTy(_) => {
1720                             return def == path.def
1721                         }
1722                         _ => {}
1723                     }
1724                 }
1725
1726                 false
1727             };
1728
1729             if let hir::TyRptr(lifetime_ref, ref mt) = inputs[0].node {
1730                 if let hir::TyPath(hir::QPath::Resolved(None, ref path)) = mt.ty.node {
1731                     if is_self_ty(path.def) {
1732                         if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1733                             let scope = Scope::Elision {
1734                                 elide: Elide::Exact(lifetime),
1735                                 s: self.scope,
1736                             };
1737                             self.with(scope, |_, this| this.visit_ty(output));
1738                             return;
1739                         }
1740                     }
1741                 }
1742             }
1743         }
1744
1745         // Second, if there was exactly one lifetime (either a substitution or a
1746         // reference) in the arguments, then any anonymous regions in the output
1747         // have that lifetime.
1748         let mut possible_implied_output_region = None;
1749         let mut lifetime_count = 0;
1750         let arg_lifetimes = inputs
1751             .iter()
1752             .enumerate()
1753             .skip(has_self as usize)
1754             .map(|(i, input)| {
1755                 let mut gather = GatherLifetimes {
1756                     map: self.map,
1757                     binder_depth: 1,
1758                     have_bound_regions: false,
1759                     lifetimes: FxHashSet(),
1760                 };
1761                 gather.visit_ty(input);
1762
1763                 lifetime_count += gather.lifetimes.len();
1764
1765                 if lifetime_count == 1 && gather.lifetimes.len() == 1 {
1766                     // there's a chance that the unique lifetime of this
1767                     // iteration will be the appropriate lifetime for output
1768                     // parameters, so lets store it.
1769                     possible_implied_output_region = gather.lifetimes.iter().cloned().next();
1770                 }
1771
1772                 ElisionFailureInfo {
1773                     parent: body,
1774                     index: i,
1775                     lifetime_count: gather.lifetimes.len(),
1776                     have_bound_regions: gather.have_bound_regions,
1777                 }
1778             })
1779             .collect();
1780
1781         let elide = if lifetime_count == 1 {
1782             Elide::Exact(possible_implied_output_region.unwrap())
1783         } else {
1784             Elide::Error(arg_lifetimes)
1785         };
1786
1787         let scope = Scope::Elision {
1788             elide,
1789             s: self.scope,
1790         };
1791         self.with(scope, |_, this| this.visit_ty(output));
1792
1793         struct GatherLifetimes<'a> {
1794             map: &'a NamedRegionMap,
1795             binder_depth: u32,
1796             have_bound_regions: bool,
1797             lifetimes: FxHashSet<Region>,
1798         }
1799
1800         impl<'v, 'a> Visitor<'v> for GatherLifetimes<'a> {
1801             fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1802                 NestedVisitorMap::None
1803             }
1804
1805             fn visit_ty(&mut self, ty: &hir::Ty) {
1806                 if let hir::TyBareFn(_) = ty.node {
1807                     self.binder_depth += 1;
1808                 }
1809                 if let hir::TyTraitObject(ref bounds, ref lifetime) = ty.node {
1810                     for bound in bounds {
1811                         self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
1812                     }
1813
1814                     // Stay on the safe side and don't include the object
1815                     // lifetime default (which may not end up being used).
1816                     if !lifetime.is_elided() {
1817                         self.visit_lifetime(lifetime);
1818                     }
1819                 } else {
1820                     intravisit::walk_ty(self, ty);
1821                 }
1822                 if let hir::TyBareFn(_) = ty.node {
1823                     self.binder_depth -= 1;
1824                 }
1825             }
1826
1827             fn visit_generic_param(&mut self, param: &hir::GenericParam) {
1828                 if let hir::GenericParam::Lifetime(ref lifetime_def) = *param {
1829                     for l in &lifetime_def.bounds {
1830                         self.visit_lifetime(l);
1831                     }
1832                 }
1833
1834                 intravisit::walk_generic_param(self, param);
1835             }
1836
1837             fn visit_poly_trait_ref(
1838                 &mut self,
1839                 trait_ref: &hir::PolyTraitRef,
1840                 modifier: hir::TraitBoundModifier,
1841             ) {
1842                 self.binder_depth += 1;
1843                 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
1844                 self.binder_depth -= 1;
1845             }
1846
1847             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
1848                 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1849                     match lifetime {
1850                         Region::LateBound(debruijn, _, _) | Region::LateBoundAnon(debruijn, _)
1851                             if debruijn.depth < self.binder_depth =>
1852                         {
1853                             self.have_bound_regions = true;
1854                         }
1855                         _ => {
1856                             self.lifetimes
1857                                 .insert(lifetime.from_depth(self.binder_depth));
1858                         }
1859                     }
1860                 }
1861             }
1862         }
1863     }
1864
1865     fn resolve_elided_lifetimes(&mut self, lifetime_refs: &'tcx [hir::Lifetime], deprecated: bool) {
1866         if lifetime_refs.is_empty() {
1867             return;
1868         }
1869
1870         let span = lifetime_refs[0].span;
1871         let id = lifetime_refs[0].id;
1872         let mut late_depth = 0;
1873         let mut scope = self.scope;
1874         if deprecated {
1875             self.tcx
1876                 .struct_span_lint_node(
1877                     lint::builtin::ELIDED_LIFETIME_IN_PATH,
1878                     id,
1879                     span,
1880                     &format!("hidden lifetime parameters are deprecated, try `Foo<'_>`"))
1881                 .emit();
1882         }
1883         let error = loop {
1884             match *scope {
1885                 // Do not assign any resolution, it will be inferred.
1886                 Scope::Body { .. } => return,
1887
1888                 Scope::Root => break None,
1889
1890                 Scope::Binder { s, .. } => {
1891                     late_depth += 1;
1892                     scope = s;
1893                 }
1894
1895                 Scope::Elision { ref elide, .. } => {
1896                     let lifetime = match *elide {
1897                         Elide::FreshLateAnon(ref counter) => {
1898                             for lifetime_ref in lifetime_refs {
1899                                 let lifetime = Region::late_anon(counter).shifted(late_depth);
1900                                 self.insert_lifetime(lifetime_ref, lifetime);
1901                             }
1902                             return;
1903                         }
1904                         Elide::Exact(l) => l.shifted(late_depth),
1905                         Elide::Error(ref e) => break Some(e),
1906                     };
1907                     for lifetime_ref in lifetime_refs {
1908                         self.insert_lifetime(lifetime_ref, lifetime);
1909                     }
1910                     return;
1911                 }
1912
1913                 Scope::ObjectLifetimeDefault { s, .. } => {
1914                     scope = s;
1915                 }
1916             }
1917         };
1918
1919         let mut err = struct_span_err!(
1920             self.tcx.sess,
1921             span,
1922             E0106,
1923             "missing lifetime specifier{}",
1924             if lifetime_refs.len() > 1 { "s" } else { "" }
1925         );
1926         let msg = if lifetime_refs.len() > 1 {
1927             format!("expected {} lifetime parameters", lifetime_refs.len())
1928         } else {
1929             format!("expected lifetime parameter")
1930         };
1931         err.span_label(span, msg);
1932
1933         if let Some(params) = error {
1934             if lifetime_refs.len() == 1 {
1935                 self.report_elision_failure(&mut err, params);
1936             }
1937         }
1938         err.emit();
1939     }
1940
1941     fn report_elision_failure(
1942         &mut self,
1943         db: &mut DiagnosticBuilder,
1944         params: &[ElisionFailureInfo],
1945     ) {
1946         let mut m = String::new();
1947         let len = params.len();
1948
1949         let elided_params: Vec<_> = params
1950             .iter()
1951             .cloned()
1952             .filter(|info| info.lifetime_count > 0)
1953             .collect();
1954
1955         let elided_len = elided_params.len();
1956
1957         for (i, info) in elided_params.into_iter().enumerate() {
1958             let ElisionFailureInfo {
1959                 parent,
1960                 index,
1961                 lifetime_count: n,
1962                 have_bound_regions,
1963             } = info;
1964
1965             let help_name = if let Some(body) = parent {
1966                 let arg = &self.tcx.hir.body(body).arguments[index];
1967                 format!("`{}`", self.tcx.hir.node_to_pretty_string(arg.pat.id))
1968             } else {
1969                 format!("argument {}", index + 1)
1970             };
1971
1972             m.push_str(
1973                 &(if n == 1 {
1974                     help_name
1975                 } else {
1976                     format!(
1977                         "one of {}'s {} {}lifetimes",
1978                         help_name,
1979                         n,
1980                         if have_bound_regions { "free " } else { "" }
1981                     )
1982                 })[..],
1983             );
1984
1985             if elided_len == 2 && i == 0 {
1986                 m.push_str(" or ");
1987             } else if i + 2 == elided_len {
1988                 m.push_str(", or ");
1989             } else if i != elided_len - 1 {
1990                 m.push_str(", ");
1991             }
1992         }
1993
1994         if len == 0 {
1995             help!(
1996                 db,
1997                 "this function's return type contains a borrowed value, but \
1998                  there is no value for it to be borrowed from"
1999             );
2000             help!(db, "consider giving it a 'static lifetime");
2001         } else if elided_len == 0 {
2002             help!(
2003                 db,
2004                 "this function's return type contains a borrowed value with \
2005                  an elided lifetime, but the lifetime cannot be derived from \
2006                  the arguments"
2007             );
2008             help!(
2009                 db,
2010                 "consider giving it an explicit bounded or 'static \
2011                  lifetime"
2012             );
2013         } else if elided_len == 1 {
2014             help!(
2015                 db,
2016                 "this function's return type contains a borrowed value, but \
2017                  the signature does not say which {} it is borrowed from",
2018                 m
2019             );
2020         } else {
2021             help!(
2022                 db,
2023                 "this function's return type contains a borrowed value, but \
2024                  the signature does not say whether it is borrowed from {}",
2025                 m
2026             );
2027         }
2028     }
2029
2030     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
2031         let mut late_depth = 0;
2032         let mut scope = self.scope;
2033         let lifetime = loop {
2034             match *scope {
2035                 Scope::Binder { s, .. } => {
2036                     late_depth += 1;
2037                     scope = s;
2038                 }
2039
2040                 Scope::Root | Scope::Elision { .. } => break Region::Static,
2041
2042                 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
2043
2044                 Scope::ObjectLifetimeDefault {
2045                     lifetime: Some(l), ..
2046                 } => break l,
2047             }
2048         };
2049         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
2050     }
2051
2052     fn check_lifetime_params(&mut self, old_scope: ScopeRef, params: &'tcx [hir::GenericParam]) {
2053         for (i, lifetime_i) in params.lifetimes().enumerate() {
2054             for lifetime in params.lifetimes() {
2055                 match lifetime.lifetime.name {
2056                     hir::LifetimeName::Static | hir::LifetimeName::Underscore => {
2057                         let lifetime = lifetime.lifetime;
2058                         let name = lifetime.name.name();
2059                         let mut err = struct_span_err!(
2060                             self.tcx.sess,
2061                             lifetime.span,
2062                             E0262,
2063                             "invalid lifetime parameter name: `{}`",
2064                             name
2065                         );
2066                         err.span_label(
2067                             lifetime.span,
2068                             format!("{} is a reserved lifetime name", name),
2069                         );
2070                         err.emit();
2071                     }
2072                     hir::LifetimeName::Implicit | hir::LifetimeName::Name(_) => {}
2073                 }
2074             }
2075
2076             // It is a hard error to shadow a lifetime within the same scope.
2077             for lifetime_j in params.lifetimes().skip(i + 1) {
2078                 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
2079                     struct_span_err!(
2080                         self.tcx.sess,
2081                         lifetime_j.lifetime.span,
2082                         E0263,
2083                         "lifetime name `{}` declared twice in the same scope",
2084                         lifetime_j.lifetime.name.name()
2085                     ).span_label(lifetime_j.lifetime.span, "declared twice")
2086                         .span_label(lifetime_i.lifetime.span, "previous declaration here")
2087                         .emit();
2088                 }
2089             }
2090
2091             // It is a soft error to shadow a lifetime within a parent scope.
2092             self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
2093
2094             for bound in &lifetime_i.bounds {
2095                 match bound.name {
2096                     hir::LifetimeName::Underscore => {
2097                         let mut err = struct_span_err!(
2098                             self.tcx.sess,
2099                             bound.span,
2100                             E0637,
2101                             "invalid lifetime bound name: `'_`"
2102                         );
2103                         err.span_label(bound.span, "`'_` is a reserved lifetime name");
2104                         err.emit();
2105                     }
2106                     hir::LifetimeName::Static => {
2107                         self.insert_lifetime(bound, Region::Static);
2108                         self.tcx
2109                             .sess
2110                             .struct_span_warn(
2111                                 lifetime_i.lifetime.span.to(bound.span),
2112                                 &format!(
2113                                     "unnecessary lifetime parameter `{}`",
2114                                     lifetime_i.lifetime.name.name()
2115                                 ),
2116                             )
2117                             .help(&format!(
2118                                 "you can use the `'static` lifetime directly, in place \
2119                                  of `{}`",
2120                                 lifetime_i.lifetime.name.name()
2121                             ))
2122                             .emit();
2123                     }
2124                     hir::LifetimeName::Implicit | hir::LifetimeName::Name(_) => {
2125                         self.resolve_lifetime_ref(bound);
2126                     }
2127                 }
2128             }
2129         }
2130     }
2131
2132     fn check_lifetime_def_for_shadowing(&self,
2133                                         mut old_scope: ScopeRef,
2134                                         lifetime: &'tcx hir::Lifetime) {
2135         for &(label, label_span) in &self.labels_in_fn {
2136             // FIXME (#24278): non-hygienic comparison
2137             if lifetime.name.name() == label {
2138                 signal_shadowing_problem(
2139                     self.tcx,
2140                     label,
2141                     original_label(label_span),
2142                     shadower_lifetime(&lifetime),
2143                 );
2144                 return;
2145             }
2146         }
2147
2148         loop {
2149             match *old_scope {
2150                 Scope::Body { s, .. }
2151                 | Scope::Elision { s, .. }
2152                 | Scope::ObjectLifetimeDefault { s, .. } => {
2153                     old_scope = s;
2154                 }
2155
2156                 Scope::Root => {
2157                     return;
2158                 }
2159
2160                 Scope::Binder {
2161                     ref lifetimes,
2162                     s,
2163                     next_early_index: _,
2164                     abstract_type_parent: _,
2165                 } => {
2166                     if let Some(&def) = lifetimes.get(&lifetime.name) {
2167                         let node_id = self.tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
2168
2169                         signal_shadowing_problem(
2170                             self.tcx,
2171                             lifetime.name.name(),
2172                             original_lifetime(self.tcx.hir.span(node_id)),
2173                             shadower_lifetime(&lifetime),
2174                         );
2175                         return;
2176                     }
2177
2178                     old_scope = s;
2179                 }
2180             }
2181         }
2182     }
2183
2184     fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {
2185         if lifetime_ref.id == ast::DUMMY_NODE_ID {
2186             span_bug!(
2187                 lifetime_ref.span,
2188                 "lifetime reference not renumbered, \
2189                  probably a bug in syntax::fold"
2190             );
2191         }
2192
2193         debug!(
2194             "insert_lifetime: {} resolved to {:?} span={:?}",
2195             self.tcx.hir.node_to_string(lifetime_ref.id),
2196             def,
2197             self.tcx.sess.codemap().span_to_string(lifetime_ref.span)
2198         );
2199         self.map.defs.insert(lifetime_ref.id, def);
2200
2201         match def {
2202             Region::LateBoundAnon(..) |
2203             Region::Static => {
2204                 // These are anonymous lifetimes or lifetimes that are not declared.
2205             }
2206
2207             Region::Free(_, def_id) |
2208             Region::LateBound(_, def_id, _) |
2209             Region::EarlyBound(_, def_id, _) => {
2210                 // A lifetime declared by the user.
2211                 if !self.lifetime_uses.contains_key(&def_id) {
2212                     self.lifetime_uses
2213                         .insert(def_id, LifetimeUseSet::One(lifetime_ref));
2214                 } else {
2215                     self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
2216                 }
2217             }
2218         }
2219     }
2220 }
2221
2222 ///////////////////////////////////////////////////////////////////////////
2223
2224 /// Detects late-bound lifetimes and inserts them into
2225 /// `map.late_bound`.
2226 ///
2227 /// A region declared on a fn is **late-bound** if:
2228 /// - it is constrained by an argument type;
2229 /// - it does not appear in a where-clause.
2230 ///
2231 /// "Constrained" basically means that it appears in any type but
2232 /// not amongst the inputs to a projection.  In other words, `<&'a
2233 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
2234 fn insert_late_bound_lifetimes(
2235     map: &mut NamedRegionMap,
2236     decl: &hir::FnDecl,
2237     generics: &hir::Generics,
2238 ) {
2239     debug!(
2240         "insert_late_bound_lifetimes(decl={:?}, generics={:?})",
2241         decl,
2242         generics
2243     );
2244
2245     let mut constrained_by_input = ConstrainedCollector {
2246         regions: FxHashSet(),
2247     };
2248     for arg_ty in &decl.inputs {
2249         constrained_by_input.visit_ty(arg_ty);
2250     }
2251
2252     let mut appears_in_output = AllCollector {
2253         regions: FxHashSet(),
2254     };
2255     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
2256
2257     debug!(
2258         "insert_late_bound_lifetimes: constrained_by_input={:?}",
2259         constrained_by_input.regions
2260     );
2261
2262     // Walk the lifetimes that appear in where clauses.
2263     //
2264     // Subtle point: because we disallow nested bindings, we can just
2265     // ignore binders here and scrape up all names we see.
2266     let mut appears_in_where_clause = AllCollector {
2267         regions: FxHashSet(),
2268     };
2269
2270     for param in &generics.params {
2271         match *param {
2272             hir::GenericParam::Lifetime(ref lifetime_def) => {
2273                 if !lifetime_def.bounds.is_empty() {
2274                     // `'a: 'b` means both `'a` and `'b` are referenced
2275                     appears_in_where_clause.visit_generic_param(param);
2276                 }
2277             }
2278             hir::GenericParam::Type(ref ty_param) => {
2279                 walk_list!(
2280                     &mut appears_in_where_clause,
2281                     visit_ty_param_bound,
2282                     &ty_param.bounds
2283                 );
2284             }
2285         }
2286     }
2287
2288     walk_list!(
2289         &mut appears_in_where_clause,
2290         visit_where_predicate,
2291         &generics.where_clause.predicates
2292     );
2293
2294     debug!(
2295         "insert_late_bound_lifetimes: appears_in_where_clause={:?}",
2296         appears_in_where_clause.regions
2297     );
2298
2299     // Late bound regions are those that:
2300     // - appear in the inputs
2301     // - do not appear in the where-clauses
2302     // - are not implicitly captured by `impl Trait`
2303     for lifetime in generics.lifetimes() {
2304         let name = lifetime.lifetime.name;
2305
2306         // appears in the where clauses? early-bound.
2307         if appears_in_where_clause.regions.contains(&name) {
2308             continue;
2309         }
2310
2311         // does not appear in the inputs, but appears in the return type? early-bound.
2312         if !constrained_by_input.regions.contains(&name)
2313             && appears_in_output.regions.contains(&name)
2314         {
2315             continue;
2316         }
2317
2318         debug!(
2319             "insert_late_bound_lifetimes: \
2320              lifetime {:?} with id {:?} is late-bound",
2321             lifetime.lifetime.name,
2322             lifetime.lifetime.id
2323         );
2324
2325         let inserted = map.late_bound.insert(lifetime.lifetime.id);
2326         assert!(
2327             inserted,
2328             "visited lifetime {:?} twice",
2329             lifetime.lifetime.id
2330         );
2331     }
2332
2333     return;
2334
2335     struct ConstrainedCollector {
2336         regions: FxHashSet<hir::LifetimeName>,
2337     }
2338
2339     impl<'v> Visitor<'v> for ConstrainedCollector {
2340         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2341             NestedVisitorMap::None
2342         }
2343
2344         fn visit_ty(&mut self, ty: &'v hir::Ty) {
2345             match ty.node {
2346                 hir::TyPath(hir::QPath::Resolved(Some(_), _))
2347                 | hir::TyPath(hir::QPath::TypeRelative(..)) => {
2348                     // ignore lifetimes appearing in associated type
2349                     // projections, as they are not *constrained*
2350                     // (defined above)
2351                 }
2352
2353                 hir::TyPath(hir::QPath::Resolved(None, ref path)) => {
2354                     // consider only the lifetimes on the final
2355                     // segment; I am not sure it's even currently
2356                     // valid to have them elsewhere, but even if it
2357                     // is, those would be potentially inputs to
2358                     // projections
2359                     if let Some(last_segment) = path.segments.last() {
2360                         self.visit_path_segment(path.span, last_segment);
2361                     }
2362                 }
2363
2364                 _ => {
2365                     intravisit::walk_ty(self, ty);
2366                 }
2367             }
2368         }
2369
2370         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2371             self.regions.insert(lifetime_ref.name);
2372         }
2373     }
2374
2375     struct AllCollector {
2376         regions: FxHashSet<hir::LifetimeName>,
2377     }
2378
2379     impl<'v> Visitor<'v> for AllCollector {
2380         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2381             NestedVisitorMap::None
2382         }
2383
2384         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2385             self.regions.insert(lifetime_ref.name);
2386         }
2387     }
2388 }