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