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