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 dep_graph::DepNode;
  19 use hir::map::Map;
  20 use session::Session;
  21 use hir::def::Def;
  22 use hir::def_id::DefId;
  23 use middle::region;
  24 use ty;
  25
  26 use std::cell::Cell;
  27 use std::mem::replace;
  28 use syntax::ast;
  29 use syntax::attr;
  30 use syntax::ptr::P;
  31 use syntax::symbol::keywords;
  32 use syntax_pos::Span;
  33 use errors::DiagnosticBuilder;
  34 use util::nodemap::{NodeMap, NodeSet, FxHashSet, FxHashMap, DefIdMap};
  35 use rustc_back::slice;
  36
  37 use hir;
  38 use hir::intravisit::{self, Visitor, NestedVisitorMap};
  39
  40 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  41 pub enum Region {
  42     Static,
  43     EarlyBound(/* index */ u32, /* lifetime decl */ ast::NodeId),
  44     LateBound(ty::DebruijnIndex, /* lifetime decl */ ast::NodeId),
  45     LateBoundAnon(ty::DebruijnIndex, /* anon index */ u32),
  46     Free(region::CallSiteScopeData, /* lifetime decl */ ast::NodeId),
  47 }
  48
  49 impl Region {
  50     fn early(index: &mut u32, def: &hir::LifetimeDef) -> (ast::Name, Region) {
  51         let i = *index;
  52         *index += 1;
  53         (def.lifetime.name, Region::EarlyBound(i, def.lifetime.id))
  54     }
  55
  56     fn late(def: &hir::LifetimeDef) -> (ast::Name, Region) {
  57         let depth = ty::DebruijnIndex::new(1);
  58         (def.lifetime.name, Region::LateBound(depth, def.lifetime.id))
  59     }
  60
  61     fn late_anon(index: &Cell<u32>) -> Region {
  62         let i = index.get();
  63         index.set(i + 1);
  64         let depth = ty::DebruijnIndex::new(1);
  65         Region::LateBoundAnon(depth, i)
  66     }
  67
  68     fn id(&self) -> Option<ast::NodeId> {
  69         match *self {
  70             Region::Static |
  71             Region::LateBoundAnon(..) => None,
  72
  73             Region::EarlyBound(_, id) |
  74             Region::LateBound(_, id) |
  75             Region::Free(_, id) => Some(id)
  76         }
  77     }
  78
  79     fn shifted(self, amount: u32) -> Region {
  80         match self {
  81             Region::LateBound(depth, id) => {
  82                 Region::LateBound(depth.shifted(amount), id)
  83             }
  84             Region::LateBoundAnon(depth, index) => {
  85                 Region::LateBoundAnon(depth.shifted(amount), index)
  86             }
  87             _ => self
  88         }
  89     }
  90
  91     fn from_depth(self, depth: u32) -> Region {
  92         match self {
  93             Region::LateBound(debruijn, id) => {
  94                 Region::LateBound(ty::DebruijnIndex {
  95                     depth: debruijn.depth - (depth - 1)
  96                 }, id)
  97             }
  98             Region::LateBoundAnon(debruijn, index) => {
  99                 Region::LateBoundAnon(ty::DebruijnIndex {
 100                     depth: debruijn.depth - (depth - 1)
 101                 }, index)
 102             }
 103             _ => self
 104         }
 105     }
 106
 107     fn subst(self, params: &[hir::Lifetime], map: &NamedRegionMap)
 108              -> Option<Region> {
 109         if let Region::EarlyBound(index, _) = self {
 110             params.get(index as usize).and_then(|lifetime| {
 111                 map.defs.get(&lifetime.id).cloned()
 112             })
 113         } else {
 114             Some(self)
 115         }
 116     }
 117 }
 118
 119 /// A set containing, at most, one known element.
 120 /// If two distinct values are inserted into a set, then it
 121 /// becomes `Many`, which can be used to detect ambiguities.
 122 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
 123 pub enum Set1<T> {
 124     Empty,
 125     One(T),
 126     Many
 127 }
 128
 129 impl<T: PartialEq> Set1<T> {
 130     pub fn insert(&mut self, value: T) {
 131         if let Set1::Empty = *self {
 132             *self = Set1::One(value);
 133             return;
 134         }
 135         if let Set1::One(ref old) = *self {
 136             if *old == value {
 137                 return;
 138             }
 139         }
 140         *self = Set1::Many;
 141     }
 142 }
 143
 144 pub type ObjectLifetimeDefault = Set1<Region>;
 145
 146 // Maps the id of each lifetime reference to the lifetime decl
 147 // that it corresponds to.
 148 pub struct NamedRegionMap {
 149     // maps from every use of a named (not anonymous) lifetime to a
 150     // `Region` describing how that region is bound
 151     pub defs: NodeMap<Region>,
 152
 153     // the set of lifetime def ids that are late-bound; a region can
 154     // be late-bound if (a) it does NOT appear in a where-clause and
 155     // (b) it DOES appear in the arguments.
 156     pub late_bound: NodeSet,
 157
 158     // Contains the node-ids for lifetimes that were (incorrectly) categorized
 159     // as late-bound, until #32330 was fixed.
 160     pub issue_32330: NodeMap<ty::Issue32330>,
 161
 162     // For each type and trait definition, maps type parameters
 163     // to the trait object lifetime defaults computed from them.
 164     pub object_lifetime_defaults: NodeMap<Vec<ObjectLifetimeDefault>>,
 165 }
 166
 167 struct LifetimeContext<'a, 'tcx: 'a> {
 168     sess: &'a Session,
 169     hir_map: &'a Map<'tcx>,
 170     map: &'a mut NamedRegionMap,
 171     scope: ScopeRef<'a>,
 172     // Deep breath. Our representation for poly trait refs contains a single
 173     // binder and thus we only allow a single level of quantification. However,
 174     // the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
 175     // and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
 176     // correct when representing these constraints, we should only introduce one
 177     // scope. However, we want to support both locations for the quantifier and
 178     // during lifetime resolution we want precise information (so we can't
 179     // desugar in an earlier phase).
 180
 181     // SO, if we encounter a quantifier at the outer scope, we set
 182     // trait_ref_hack to true (and introduce a scope), and then if we encounter
 183     // a quantifier at the inner scope, we error. If trait_ref_hack is false,
 184     // then we introduce the scope at the inner quantifier.
 185
 186     // I'm sorry.
 187     trait_ref_hack: bool,
 188
 189     // List of labels in the function/method currently under analysis.
 190     labels_in_fn: Vec<(ast::Name, Span)>,
 191
 192     // Cache for cross-crate per-definition object lifetime defaults.
 193     xcrate_object_lifetime_defaults: DefIdMap<Vec<ObjectLifetimeDefault>>,
 194 }
 195
 196 #[derive(Debug)]
 197 enum Scope<'a> {
 198     /// Declares lifetimes, and each can be early-bound or late-bound.
 199     /// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
 200     /// it should be shifted by the number of `Binder`s in between the
 201     /// declaration `Binder` and the location it's referenced from.
 202     Binder {
 203         lifetimes: FxHashMap<ast::Name, Region>,
 204         s: ScopeRef<'a>
 205     },
 206
 207     /// Lifetimes introduced by a fn are scoped to the call-site for that fn,
 208     /// if this is a fn body, otherwise the original definitions are used.
 209     /// Unspecified lifetimes are inferred, unless an elision scope is nested,
 210     /// e.g. `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
 211     Body {
 212         id: hir::BodyId,
 213         s: ScopeRef<'a>
 214     },
 215
 216     /// A scope which either determines unspecified lifetimes or errors
 217     /// on them (e.g. due to ambiguity). For more details, see `Elide`.
 218     Elision {
 219         elide: Elide,
 220         s: ScopeRef<'a>
 221     },
 222
 223     /// Use a specific lifetime (if `Some`) or leave it unset (to be
 224     /// inferred in a function body or potentially error outside one),
 225     /// for the default choice of lifetime in a trait object type.
 226     ObjectLifetimeDefault {
 227         lifetime: Option<Region>,
 228         s: ScopeRef<'a>
 229     },
 230
 231     Root
 232 }
 233
 234 #[derive(Clone, Debug)]
 235 enum Elide {
 236     /// Use a fresh anonymous late-bound lifetime each time, by
 237     /// incrementing the counter to generate sequential indices.
 238     FreshLateAnon(Cell<u32>),
 239     /// Always use this one lifetime.
 240     Exact(Region),
 241     /// Less or more than one lifetime were found, error on unspecified.
 242     Error(Vec<ElisionFailureInfo>)
 243 }
 244
 245 #[derive(Clone, Debug)]
 246 struct ElisionFailureInfo {
 247     /// Where we can find the argument pattern.
 248     parent: Option<hir::BodyId>,
 249     /// The index of the argument in the original definition.
 250     index: usize,
 251     lifetime_count: usize,
 252     have_bound_regions: bool
 253 }
 254
 255 type ScopeRef<'a> = &'a Scope<'a>;
 256
 257 const ROOT_SCOPE: ScopeRef<'static> = &Scope::Root;
 258
 259 pub fn krate(sess: &Session,
 260              hir_map: &Map)
 261              -> Result<NamedRegionMap, usize> {
 262     let _task = hir_map.dep_graph.in_task(DepNode::ResolveLifetimes);
 263     let krate = hir_map.krate();
 264     let mut map = NamedRegionMap {
 265         defs: NodeMap(),
 266         late_bound: NodeSet(),
 267         issue_32330: NodeMap(),
 268         object_lifetime_defaults: compute_object_lifetime_defaults(sess, hir_map),
 269     };
 270     sess.track_errors(|| {
 271         let mut visitor = LifetimeContext {
 272             sess: sess,
 273             hir_map: hir_map,
 274             map: &mut map,
 275             scope: ROOT_SCOPE,
 276             trait_ref_hack: false,
 277             labels_in_fn: vec![],
 278             xcrate_object_lifetime_defaults: DefIdMap(),
 279         };
 280         for (_, item) in &krate.items {
 281             visitor.visit_item(item);
 282         }
 283     })?;
 284     Ok(map)
 285 }
 286
 287 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 288     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 289         NestedVisitorMap::All(self.hir_map)
 290     }
 291
 292     // We want to nest trait/impl items in their parent, but nothing else.
 293     fn visit_nested_item(&mut self, _: hir::ItemId) {}
 294
 295     fn visit_nested_body(&mut self, body: hir::BodyId) {
 296         // Each body has their own set of labels, save labels.
 297         let saved = replace(&mut self.labels_in_fn, vec![]);
 298         let body = self.hir_map.body(body);
 299         extract_labels(self, body);
 300         self.with(Scope::Body { id: body.id(), s: self.scope }, |_, this| {
 301             this.visit_body(body);
 302         });
 303         replace(&mut self.labels_in_fn, saved);
 304     }
 305
 306     fn visit_item(&mut self, item: &'tcx hir::Item) {
 307         match item.node {
 308             hir::ItemFn(ref decl, _, _, _, ref generics, _) => {
 309                 self.visit_early_late(item.id, None, decl, generics, |this| {
 310                     intravisit::walk_item(this, item);
 311                 });
 312             }
 313             hir::ItemExternCrate(_) |
 314             hir::ItemUse(..) |
 315             hir::ItemMod(..) |
 316             hir::ItemDefaultImpl(..) |
 317             hir::ItemForeignMod(..) |
 318             hir::ItemGlobalAsm(..) => {
 319                 // These sorts of items have no lifetime parameters at all.
 320                 intravisit::walk_item(self, item);
 321             }
 322             hir::ItemStatic(..) |
 323             hir::ItemConst(..) => {
 324                 // No lifetime parameters, but implied 'static.
 325                 let scope = Scope::Elision {
 326                     elide: Elide::Exact(Region::Static),
 327                     s: ROOT_SCOPE
 328                 };
 329                 self.with(scope, |_, this| intravisit::walk_item(this, item));
 330             }
 331             hir::ItemTy(_, ref generics) |
 332             hir::ItemEnum(_, ref generics) |
 333             hir::ItemStruct(_, ref generics) |
 334             hir::ItemUnion(_, ref generics) |
 335             hir::ItemTrait(_, ref generics, ..) |
 336             hir::ItemImpl(_, _, ref generics, ..) => {
 337                 // These kinds of items have only early bound lifetime parameters.
 338                 let mut index = if let hir::ItemTrait(..) = item.node {
 339                     1 // Self comes before lifetimes
 340                 } else {
 341                     0
 342                 };
 343                 let lifetimes = generics.lifetimes.iter().map(|def| {
 344                     Region::early(&mut index, def)
 345                 }).collect();
 346                 let scope = Scope::Binder {
 347                     lifetimes: lifetimes,
 348                     s: ROOT_SCOPE
 349                 };
 350                 self.with(scope, |old_scope, this| {
 351                     this.check_lifetime_defs(old_scope, &generics.lifetimes);
 352                     intravisit::walk_item(this, item);
 353                 });
 354             }
 355         }
 356     }
 357
 358     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem) {
 359         match item.node {
 360             hir::ForeignItemFn(ref decl, _, ref generics) => {
 361                 self.visit_early_late(item.id, None, decl, generics, |this| {
 362                     intravisit::walk_foreign_item(this, item);
 363                 })
 364             }
 365             hir::ForeignItemStatic(..) => {
 366                 intravisit::walk_foreign_item(self, item);
 367             }
 368         }
 369     }
 370
 371     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 372         match ty.node {
 373             hir::TyBareFn(ref c) => {
 374                 let scope = Scope::Binder {
 375                     lifetimes: c.lifetimes.iter().map(Region::late).collect(),
 376                     s: self.scope
 377                 };
 378                 self.with(scope, |old_scope, this| {
 379                     // a bare fn has no bounds, so everything
 380                     // contained within is scoped within its binder.
 381                     this.check_lifetime_defs(old_scope, &c.lifetimes);
 382                     intravisit::walk_ty(this, ty);
 383                 });
 384             }
 385             hir::TyTraitObject(ref bounds, ref lifetime) => {
 386                 for bound in bounds {
 387                     self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
 388                 }
 389                 if lifetime.is_elided() {
 390                     self.resolve_object_lifetime_default(lifetime)
 391                 } else {
 392                     self.visit_lifetime(lifetime);
 393                 }
 394             }
 395             hir::TyRptr(ref lifetime_ref, ref mt) => {
 396                 self.visit_lifetime(lifetime_ref);
 397                 let scope = Scope::ObjectLifetimeDefault {
 398                     lifetime: self.map.defs.get(&lifetime_ref.id).cloned(),
 399                     s: self.scope
 400                 };
 401                 self.with(scope, |_, this| this.visit_ty(&mt.ty));
 402             }
 403             _ => {
 404                 intravisit::walk_ty(self, ty)
 405             }
 406         }
 407     }
 408
 409     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 410         if let hir::TraitItemKind::Method(ref sig, _) = trait_item.node {
 411             self.visit_early_late(
 412                 trait_item.id,
 413                 Some(self.hir_map.get_parent(trait_item.id)),
 414                 &sig.decl, &sig.generics,
 415                 |this| intravisit::walk_trait_item(this, trait_item))
 416         } else {
 417             intravisit::walk_trait_item(self, trait_item);
 418         }
 419     }
 420
 421     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 422         if let hir::ImplItemKind::Method(ref sig, _) = impl_item.node {
 423             self.visit_early_late(
 424                 impl_item.id,
 425                 Some(self.hir_map.get_parent(impl_item.id)),
 426                 &sig.decl, &sig.generics,
 427                 |this| intravisit::walk_impl_item(this, impl_item))
 428         } else {
 429             intravisit::walk_impl_item(self, impl_item);
 430         }
 431     }
 432
 433     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
 434         if lifetime_ref.is_elided() {
 435             self.resolve_elided_lifetimes(slice::ref_slice(lifetime_ref));
 436             return;
 437         }
 438         if lifetime_ref.is_static() {
 439             self.insert_lifetime(lifetime_ref, Region::Static);
 440             return;
 441         }
 442         self.resolve_lifetime_ref(lifetime_ref);
 443     }
 444
 445     fn visit_path(&mut self, path: &'tcx hir::Path, _: ast::NodeId) {
 446         for (i, segment) in path.segments.iter().enumerate() {
 447             let depth = path.segments.len() - i - 1;
 448             self.visit_segment_parameters(path.def, depth, &segment.parameters);
 449         }
 450     }
 451
 452     fn visit_fn_decl(&mut self, fd: &'tcx hir::FnDecl) {
 453         let output = match fd.output {
 454             hir::DefaultReturn(_) => None,
 455             hir::Return(ref ty) => Some(ty)
 456         };
 457         self.visit_fn_like_elision(&fd.inputs, output);
 458     }
 459
 460     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 461         for ty_param in generics.ty_params.iter() {
 462             walk_list!(self, visit_ty_param_bound, &ty_param.bounds);
 463             if let Some(ref ty) = ty_param.default {
 464                 self.visit_ty(&ty);
 465             }
 466         }
 467         for predicate in &generics.where_clause.predicates {
 468             match predicate {
 469                 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate{ ref bounded_ty,
 470                                                                                ref bounds,
 471                                                                                ref bound_lifetimes,
 472                                                                                .. }) => {
 473                     if !bound_lifetimes.is_empty() {
 474                         self.trait_ref_hack = true;
 475                         let scope = Scope::Binder {
 476                             lifetimes: bound_lifetimes.iter().map(Region::late).collect(),
 477                             s: self.scope
 478                         };
 479                         let result = self.with(scope, |old_scope, this| {
 480                             this.check_lifetime_defs(old_scope, bound_lifetimes);
 481                             this.visit_ty(&bounded_ty);
 482                             walk_list!(this, visit_ty_param_bound, bounds);
 483                         });
 484                         self.trait_ref_hack = false;
 485                         result
 486                     } else {
 487                         self.visit_ty(&bounded_ty);
 488                         walk_list!(self, visit_ty_param_bound, bounds);
 489                     }
 490                 }
 491                 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate{ref lifetime,
 492                                                                                 ref bounds,
 493                                                                                 .. }) => {
 494
 495                     self.visit_lifetime(lifetime);
 496                     for bound in bounds {
 497                         self.visit_lifetime(bound);
 498                     }
 499                 }
 500                 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate{ref lhs_ty,
 501                                                                         ref rhs_ty,
 502                                                                         .. }) => {
 503                     self.visit_ty(lhs_ty);
 504                     self.visit_ty(rhs_ty);
 505                 }
 506             }
 507         }
 508     }
 509
 510     fn visit_poly_trait_ref(&mut self,
 511                             trait_ref: &'tcx hir::PolyTraitRef,
 512                             _modifier: hir::TraitBoundModifier) {
 513         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 514
 515         if !self.trait_ref_hack || !trait_ref.bound_lifetimes.is_empty() {
 516             if self.trait_ref_hack {
 517                 span_err!(self.sess, trait_ref.span, E0316,
 518                           "nested quantification of lifetimes");
 519             }
 520             let scope = Scope::Binder {
 521                 lifetimes: trait_ref.bound_lifetimes.iter().map(Region::late).collect(),
 522                 s: self.scope
 523             };
 524             self.with(scope, |old_scope, this| {
 525                 this.check_lifetime_defs(old_scope, &trait_ref.bound_lifetimes);
 526                 for lifetime in &trait_ref.bound_lifetimes {
 527                     this.visit_lifetime_def(lifetime);
 528                 }
 529                 this.visit_trait_ref(&trait_ref.trait_ref)
 530             })
 531         } else {
 532             self.visit_trait_ref(&trait_ref.trait_ref)
 533         }
 534     }
 535 }
 536
 537 #[derive(Copy, Clone, PartialEq)]
 538 enum ShadowKind { Label, Lifetime }
 539 struct Original { kind: ShadowKind, span: Span }
 540 struct Shadower { kind: ShadowKind, span: Span }
 541
 542 fn original_label(span: Span) -> Original {
 543     Original { kind: ShadowKind::Label, span: span }
 544 }
 545 fn shadower_label(span: Span) -> Shadower {
 546     Shadower { kind: ShadowKind::Label, span: span }
 547 }
 548 fn original_lifetime(span: Span) -> Original {
 549     Original { kind: ShadowKind::Lifetime, span: span }
 550 }
 551 fn shadower_lifetime(l: &hir::Lifetime) -> Shadower {
 552     Shadower { kind: ShadowKind::Lifetime, span: l.span }
 553 }
 554
 555 impl ShadowKind {
 556     fn desc(&self) -> &'static str {
 557         match *self {
 558             ShadowKind::Label => "label",
 559             ShadowKind::Lifetime => "lifetime",
 560         }
 561     }
 562 }
 563
 564 fn signal_shadowing_problem(sess: &Session, name: ast::Name, orig: Original, shadower: Shadower) {
 565     let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
 566         // lifetime/lifetime shadowing is an error
 567         struct_span_err!(sess, shadower.span, E0496,
 568                          "{} name `{}` shadows a \
 569                           {} name that is already in scope",
 570                          shadower.kind.desc(), name, orig.kind.desc())
 571     } else {
 572         // shadowing involving a label is only a warning, due to issues with
 573         // labels and lifetimes not being macro-hygienic.
 574         sess.struct_span_warn(shadower.span,
 575                               &format!("{} name `{}` shadows a \
 576                                         {} name that is already in scope",
 577                                        shadower.kind.desc(), name, orig.kind.desc()))
 578     };
 579     err.span_label(orig.span, &"first declared here");
 580     err.span_label(shadower.span,
 581                    &format!("lifetime {} already in scope", name));
 582     err.emit();
 583 }
 584
 585 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
 586 // if one of the label shadows a lifetime or another label.
 587 fn extract_labels(ctxt: &mut LifetimeContext, body: &hir::Body) {
 588     struct GatherLabels<'a, 'tcx: 'a> {
 589         sess: &'a Session,
 590         hir_map: &'a Map<'tcx>,
 591         scope: ScopeRef<'a>,
 592         labels_in_fn: &'a mut Vec<(ast::Name, Span)>,
 593     }
 594
 595     let mut gather = GatherLabels {
 596         sess: ctxt.sess,
 597         hir_map: ctxt.hir_map,
 598         scope: ctxt.scope,
 599         labels_in_fn: &mut ctxt.labels_in_fn,
 600     };
 601     gather.visit_body(body);
 602
 603     impl<'v, 'a, 'tcx> Visitor<'v> for GatherLabels<'a, 'tcx> {
 604         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
 605             NestedVisitorMap::None
 606         }
 607
 608         fn visit_expr(&mut self, ex: &hir::Expr) {
 609             if let Some((label, label_span)) = expression_label(ex) {
 610                 for &(prior, prior_span) in &self.labels_in_fn[..] {
 611                     // FIXME (#24278): non-hygienic comparison
 612                     if label == prior {
 613                         signal_shadowing_problem(self.sess,
 614                                                  label,
 615                                                  original_label(prior_span),
 616                                                  shadower_label(label_span));
 617                     }
 618                 }
 619
 620                 check_if_label_shadows_lifetime(self.sess,
 621                                                 self.hir_map,
 622                                                 self.scope,
 623                                                 label,
 624                                                 label_span);
 625
 626                 self.labels_in_fn.push((label, label_span));
 627             }
 628             intravisit::walk_expr(self, ex)
 629         }
 630     }
 631
 632     fn expression_label(ex: &hir::Expr) -> Option<(ast::Name, Span)> {
 633         match ex.node {
 634             hir::ExprWhile(.., Some(label)) |
 635             hir::ExprLoop(_, Some(label), _) => Some((label.node, label.span)),
 636             _ => None,
 637         }
 638     }
 639
 640     fn check_if_label_shadows_lifetime<'a>(sess: &'a Session,
 641                                            hir_map: &Map,
 642                                            mut scope: ScopeRef<'a>,
 643                                            label: ast::Name,
 644                                            label_span: Span) {
 645         loop {
 646             match *scope {
 647                 Scope::Body { s, .. } |
 648                 Scope::Elision { s, .. } |
 649                 Scope::ObjectLifetimeDefault { s, .. } => { scope = s; }
 650
 651                 Scope::Root => { return; }
 652
 653                 Scope::Binder { ref lifetimes, s } => {
 654                     // FIXME (#24278): non-hygienic comparison
 655                     if let Some(def) = lifetimes.get(&label) {
 656                         signal_shadowing_problem(
 657                             sess,
 658                             label,
 659                             original_lifetime(hir_map.span(def.id().unwrap())),
 660                             shadower_label(label_span));
 661                         return;
 662                     }
 663                     scope = s;
 664                 }
 665             }
 666         }
 667     }
 668 }
 669
 670 fn compute_object_lifetime_defaults(sess: &Session, hir_map: &Map)
 671                                     -> NodeMap<Vec<ObjectLifetimeDefault>> {
 672     let mut map = NodeMap();
 673     for item in hir_map.krate().items.values() {
 674         match item.node {
 675             hir::ItemStruct(_, ref generics) |
 676             hir::ItemUnion(_, ref generics) |
 677             hir::ItemEnum(_, ref generics) |
 678             hir::ItemTy(_, ref generics) |
 679             hir::ItemTrait(_, ref generics, ..) => {
 680                 let result = object_lifetime_defaults_for_item(hir_map, generics);
 681
 682                 // Debugging aid.
 683                 if attr::contains_name(&item.attrs, "rustc_object_lifetime_default") {
 684                     let object_lifetime_default_reprs: String =
 685                         result.iter().map(|set| {
 686                             match *set {
 687                                 Set1::Empty => "BaseDefault".to_string(),
 688                                 Set1::One(Region::Static) => "'static".to_string(),
 689                                 Set1::One(Region::EarlyBound(i, _)) => {
 690                                     generics.lifetimes[i as usize].lifetime.name.to_string()
 691                                 }
 692                                 Set1::One(_) => bug!(),
 693                                 Set1::Many => "Ambiguous".to_string(),
 694                             }
 695                         }).collect::<Vec<String>>().join(",");
 696                     sess.span_err(item.span, &object_lifetime_default_reprs);
 697                 }
 698
 699                 map.insert(item.id, result);
 700             }
 701             _ => {}
 702         }
 703     }
 704     map
 705 }
 706
 707 /// Scan the bounds and where-clauses on parameters to extract bounds
 708 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
 709 /// for each type parameter.
 710 fn object_lifetime_defaults_for_item(hir_map: &Map, generics: &hir::Generics)
 711                                      -> Vec<ObjectLifetimeDefault> {
 712     fn add_bounds(set: &mut Set1<ast::Name>, bounds: &[hir::TyParamBound]) {
 713         for bound in bounds {
 714             if let hir::RegionTyParamBound(ref lifetime) = *bound {
 715                 set.insert(lifetime.name);
 716             }
 717         }
 718     }
 719
 720     generics.ty_params.iter().map(|param| {
 721         let mut set = Set1::Empty;
 722
 723         add_bounds(&mut set, &param.bounds);
 724
 725         let param_def_id = hir_map.local_def_id(param.id);
 726         for predicate in &generics.where_clause.predicates {
 727             // Look for `type: ...` where clauses.
 728             let data = match *predicate {
 729                 hir::WherePredicate::BoundPredicate(ref data) => data,
 730                 _ => continue
 731             };
 732
 733             // Ignore `for<'a> type: ...` as they can change what
 734             // lifetimes mean (although we could "just" handle it).
 735             if !data.bound_lifetimes.is_empty() {
 736                 continue;
 737             }
 738
 739             let def = match data.bounded_ty.node {
 740                 hir::TyPath(hir::QPath::Resolved(None, ref path)) => path.def,
 741                 _ => continue
 742             };
 743
 744             if def == Def::TyParam(param_def_id) {
 745                 add_bounds(&mut set, &data.bounds);
 746             }
 747         }
 748
 749         match set {
 750             Set1::Empty => Set1::Empty,
 751             Set1::One(name) => {
 752                 if name == keywords::StaticLifetime.name() {
 753                     Set1::One(Region::Static)
 754                 } else {
 755                     generics.lifetimes.iter().enumerate().find(|&(_, def)| {
 756                         def.lifetime.name == name
 757                     }).map_or(Set1::Many, |(i, def)| {
 758                         Set1::One(Region::EarlyBound(i as u32, def.lifetime.id))
 759                     })
 760                 }
 761             }
 762             Set1::Many => Set1::Many
 763         }
 764     }).collect()
 765 }
 766
 767 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 768     // FIXME(#37666) this works around a limitation in the region inferencer
 769     fn hack<F>(&mut self, f: F) where
 770         F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
 771     {
 772         f(self)
 773     }
 774
 775     fn with<F>(&mut self, wrap_scope: Scope, f: F) where
 776         F: for<'b> FnOnce(ScopeRef, &mut LifetimeContext<'b, 'tcx>),
 777     {
 778         let LifetimeContext {sess, hir_map, ref mut map, ..} = *self;
 779         let labels_in_fn = replace(&mut self.labels_in_fn, vec![]);
 780         let xcrate_object_lifetime_defaults =
 781             replace(&mut self.xcrate_object_lifetime_defaults, DefIdMap());
 782         let mut this = LifetimeContext {
 783             sess: sess,
 784             hir_map: hir_map,
 785             map: *map,
 786             scope: &wrap_scope,
 787             trait_ref_hack: self.trait_ref_hack,
 788             labels_in_fn: labels_in_fn,
 789             xcrate_object_lifetime_defaults: xcrate_object_lifetime_defaults,
 790         };
 791         debug!("entering scope {:?}", this.scope);
 792         f(self.scope, &mut this);
 793         debug!("exiting scope {:?}", this.scope);
 794         self.labels_in_fn = this.labels_in_fn;
 795         self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
 796     }
 797
 798     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
 799     ///
 800     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
 801     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
 802     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
 803     ///
 804     /// For example:
 805     ///
 806     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
 807     ///
 808     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
 809     /// lifetimes may be interspersed together.
 810     ///
 811     /// If early bound lifetimes are present, we separate them into their own list (and likewise
 812     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
 813     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
 814     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
 815     /// ordering is not important there.
 816     fn visit_early_late<F>(&mut self,
 817                            fn_id: ast::NodeId,
 818                            parent_id: Option<ast::NodeId>,
 819                            decl: &'tcx hir::FnDecl,
 820                            generics: &'tcx hir::Generics,
 821                            walk: F) where
 822         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
 823     {
 824         let fn_def_id = self.hir_map.local_def_id(fn_id);
 825         insert_late_bound_lifetimes(self.map,
 826                                     fn_def_id,
 827                                     decl,
 828                                     generics);
 829
 830         // Find the start of nested early scopes, e.g. in methods.
 831         let mut index = 0;
 832         if let Some(parent_id) = parent_id {
 833             let parent = self.hir_map.expect_item(parent_id);
 834             if let hir::ItemTrait(..) = parent.node {
 835                 index += 1; // Self comes first.
 836             }
 837             match parent.node {
 838                 hir::ItemTrait(_, ref generics, ..) |
 839                 hir::ItemImpl(_, _, ref generics, ..) => {
 840                     index += (generics.lifetimes.len() + generics.ty_params.len()) as u32;
 841                 }
 842                 _ => {}
 843             }
 844         }
 845
 846         let lifetimes = generics.lifetimes.iter().map(|def| {
 847             if self.map.late_bound.contains(&def.lifetime.id) {
 848                 Region::late(def)
 849             } else {
 850                 Region::early(&mut index, def)
 851             }
 852         }).collect();
 853
 854         let scope = Scope::Binder {
 855             lifetimes: lifetimes,
 856             s: self.scope
 857         };
 858         self.with(scope, move |old_scope, this| {
 859             this.check_lifetime_defs(old_scope, &generics.lifetimes);
 860             this.hack(walk); // FIXME(#37666) workaround in place of `walk(this)`
 861         });
 862     }
 863
 864     fn resolve_lifetime_ref(&mut self, lifetime_ref: &hir::Lifetime) {
 865         // Walk up the scope chain, tracking the number of fn scopes
 866         // that we pass through, until we find a lifetime with the
 867         // given name or we run out of scopes.
 868         // search.
 869         let mut late_depth = 0;
 870         let mut scope = self.scope;
 871         let mut outermost_body = None;
 872         let result = loop {
 873             match *scope {
 874                 Scope::Body { id, s } => {
 875                     outermost_body = Some(id);
 876                     scope = s;
 877                 }
 878
 879                 Scope::Root => {
 880                     break None;
 881                 }
 882
 883                 Scope::Binder { ref lifetimes, s } => {
 884                     if let Some(&def) = lifetimes.get(&lifetime_ref.name) {
 885                         break Some(def.shifted(late_depth));
 886                     } else {
 887                         late_depth += 1;
 888                         scope = s;
 889                     }
 890                 }
 891
 892                 Scope::Elision { s, .. } |
 893                 Scope::ObjectLifetimeDefault { s, .. } => {
 894                     scope = s;
 895                 }
 896             }
 897         };
 898
 899         if let Some(mut def) = result {
 900             if let Some(body_id) = outermost_body {
 901                 let fn_id = self.hir_map.body_owner(body_id);
 902                 let scope_data = region::CallSiteScopeData {
 903                     fn_id: fn_id, body_id: body_id.node_id
 904                 };
 905                 match self.hir_map.get(fn_id) {
 906                     hir::map::NodeItem(&hir::Item {
 907                         node: hir::ItemFn(..), ..
 908                     }) |
 909                     hir::map::NodeTraitItem(&hir::TraitItem {
 910                         node: hir::TraitItemKind::Method(..), ..
 911                     }) |
 912                     hir::map::NodeImplItem(&hir::ImplItem {
 913                         node: hir::ImplItemKind::Method(..), ..
 914                     }) => {
 915                         def = Region::Free(scope_data, def.id().unwrap());
 916                     }
 917                     _ => {}
 918                 }
 919             }
 920             self.insert_lifetime(lifetime_ref, def);
 921         } else {
 922             struct_span_err!(self.sess, lifetime_ref.span, E0261,
 923                 "use of undeclared lifetime name `{}`", lifetime_ref.name)
 924                 .span_label(lifetime_ref.span, &format!("undeclared lifetime"))
 925                 .emit();
 926         }
 927     }
 928
 929     fn visit_segment_parameters(&mut self,
 930                                 def: Def,
 931                                 depth: usize,
 932                                 params: &'tcx hir::PathParameters) {
 933         let data = match *params {
 934             hir::ParenthesizedParameters(ref data) => {
 935                 self.visit_fn_like_elision(&data.inputs, data.output.as_ref());
 936                 return;
 937             }
 938             hir::AngleBracketedParameters(ref data) => data
 939         };
 940
 941         if data.lifetimes.iter().all(|l| l.is_elided()) {
 942             self.resolve_elided_lifetimes(&data.lifetimes);
 943         } else {
 944             for l in &data.lifetimes { self.visit_lifetime(l); }
 945         }
 946
 947         // Figure out if this is a type/trait segment,
 948         // which requires object lifetime defaults.
 949         let parent_def_id = |this: &mut Self, def_id: DefId| {
 950             let def_key = if def_id.is_local() {
 951                 this.hir_map.def_key(def_id)
 952             } else {
 953                 this.sess.cstore.def_key(def_id)
 954             };
 955             DefId {
 956                 krate: def_id.krate,
 957                 index: def_key.parent.expect("missing parent")
 958             }
 959         };
 960         let type_def_id = match def {
 961             Def::AssociatedTy(def_id) if depth == 1 => {
 962                 Some(parent_def_id(self, def_id))
 963             }
 964             Def::Variant(def_id) if depth == 0 => {
 965                 Some(parent_def_id(self, def_id))
 966             }
 967             Def::Struct(def_id) |
 968             Def::Union(def_id) |
 969             Def::Enum(def_id) |
 970             Def::TyAlias(def_id) |
 971             Def::Trait(def_id) if depth == 0 => Some(def_id),
 972             _ => None
 973         };
 974
 975         let object_lifetime_defaults = type_def_id.map_or(vec![], |def_id| {
 976             let in_body = {
 977                 let mut scope = self.scope;
 978                 loop {
 979                     match *scope {
 980                         Scope::Root => break false,
 981
 982                         Scope::Body { .. } => break true,
 983
 984                         Scope::Binder { s, .. } |
 985                         Scope::Elision { s, .. } |
 986                         Scope::ObjectLifetimeDefault { s, .. } => {
 987                             scope = s;
 988                         }
 989                     }
 990                 }
 991             };
 992
 993             let map = &self.map;
 994             let unsubst = if let Some(id) = self.hir_map.as_local_node_id(def_id) {
 995                 &map.object_lifetime_defaults[&id]
 996             } else {
 997                 let cstore = &self.sess.cstore;
 998                 self.xcrate_object_lifetime_defaults.entry(def_id).or_insert_with(|| {
 999                     cstore.item_generics_cloned(def_id).types.into_iter().map(|def| {
1000                         def.object_lifetime_default
1001                     }).collect()
1002                 })
1003             };
1004             unsubst.iter().map(|set| {
1005                 match *set {
1006                     Set1::Empty => {
1007                         if in_body {
1008                             None
1009                         } else {
1010                             Some(Region::Static)
1011                         }
1012                     }
1013                     Set1::One(r) => r.subst(&data.lifetimes, map),
1014                     Set1::Many => None
1015                 }
1016             }).collect()
1017         });
1018
1019         for (i, ty) in data.types.iter().enumerate() {
1020             if let Some(&lt) = object_lifetime_defaults.get(i) {
1021                 let scope = Scope::ObjectLifetimeDefault {
1022                     lifetime: lt,
1023                     s: self.scope
1024                 };
1025                 self.with(scope, |_, this| this.visit_ty(ty));
1026             } else {
1027                 self.visit_ty(ty);
1028             }
1029         }
1030
1031         for b in &data.bindings { self.visit_assoc_type_binding(b); }
1032     }
1033
1034     fn visit_fn_like_elision(&mut self, inputs: &'tcx [P<hir::Ty>],
1035                              output: Option<&'tcx P<hir::Ty>>) {
1036         let mut arg_elide = Elide::FreshLateAnon(Cell::new(0));
1037         let arg_scope = Scope::Elision {
1038             elide: arg_elide.clone(),
1039             s: self.scope
1040         };
1041         self.with(arg_scope, |_, this| {
1042             for input in inputs {
1043                 this.visit_ty(input);
1044             }
1045             match *this.scope {
1046                 Scope::Elision { ref elide, .. } => {
1047                     arg_elide = elide.clone();
1048                 }
1049                 _ => bug!()
1050             }
1051         });
1052
1053         let output = match output {
1054             Some(ty) => ty,
1055             None => return
1056         };
1057
1058         // Figure out if there's a body we can get argument names from,
1059         // and whether there's a `self` argument (treated specially).
1060         let mut assoc_item_kind = None;
1061         let mut impl_self = None;
1062         let parent = self.hir_map.get_parent_node(output.id);
1063         let body = match self.hir_map.get(parent) {
1064             // `fn` definitions and methods.
1065             hir::map::NodeItem(&hir::Item {
1066                 node: hir::ItemFn(.., body), ..
1067             })  => Some(body),
1068
1069             hir::map::NodeTraitItem(&hir::TraitItem {
1070                 node: hir::TraitItemKind::Method(_, ref m), ..
1071             }) => {
1072                 match self.hir_map.expect_item(self.hir_map.get_parent(parent)).node {
1073                     hir::ItemTrait(.., ref trait_items) => {
1074                         assoc_item_kind = trait_items.iter().find(|ti| ti.id.node_id == parent)
1075                                                             .map(|ti| ti.kind);
1076                     }
1077                     _ => {}
1078                 }
1079                 match *m {
1080                     hir::TraitMethod::Required(_) => None,
1081                     hir::TraitMethod::Provided(body) => Some(body),
1082                 }
1083             }
1084
1085             hir::map::NodeImplItem(&hir::ImplItem {
1086                 node: hir::ImplItemKind::Method(_, body), ..
1087             }) => {
1088                 match self.hir_map.expect_item(self.hir_map.get_parent(parent)).node {
1089                     hir::ItemImpl(.., ref self_ty, ref impl_items) => {
1090                         impl_self = Some(self_ty);
1091                         assoc_item_kind = impl_items.iter().find(|ii| ii.id.node_id == parent)
1092                                                            .map(|ii| ii.kind);
1093                     }
1094                     _ => {}
1095                 }
1096                 Some(body)
1097             }
1098
1099             // `fn(...) -> R` and `Trait(...) -> R` (both types and bounds).
1100             hir::map::NodeTy(_) | hir::map::NodeTraitRef(_) => None,
1101
1102             // Foreign `fn` decls are terrible because we messed up,
1103             // and their return types get argument type elision.
1104             // And now too much code out there is abusing this rule.
1105             hir::map::NodeForeignItem(_) => {
1106                 let arg_scope = Scope::Elision {
1107                     elide: arg_elide,
1108                     s: self.scope
1109                 };
1110                 self.with(arg_scope, |_, this| this.visit_ty(output));
1111                 return;
1112             }
1113
1114             // Everything else (only closures?) doesn't
1115             // actually enjoy elision in return types.
1116             _ => {
1117                 self.visit_ty(output);
1118                 return;
1119             }
1120         };
1121
1122         let has_self = match assoc_item_kind {
1123             Some(hir::AssociatedItemKind::Method { has_self }) => has_self,
1124             _ => false
1125         };
1126
1127         // In accordance with the rules for lifetime elision, we can determine
1128         // what region to use for elision in the output type in two ways.
1129         // First (determined here), if `self` is by-reference, then the
1130         // implied output region is the region of the self parameter.
1131         if has_self {
1132             // Look for `self: &'a Self` - also desugared from `&'a self`,
1133             // and if that matches, use it for elision and return early.
1134             let is_self_ty = |def: Def| {
1135                 if let Def::SelfTy(..) = def {
1136                     return true;
1137                 }
1138
1139                 // Can't always rely on literal (or implied) `Self` due
1140                 // to the way elision rules were originally specified.
1141                 let impl_self = impl_self.map(|ty| &ty.node);
1142                 if let Some(&hir::TyPath(hir::QPath::Resolved(None, ref path))) = impl_self {
1143                     match path.def {
1144                         // Whitelist the types that unambiguously always
1145                         // result in the same type constructor being used
1146                         // (it can't differ between `Self` and `self`).
1147                         Def::Struct(_) |
1148                         Def::Union(_) |
1149                         Def::Enum(_) |
1150                         Def::PrimTy(_) => return def == path.def,
1151                         _ => {}
1152                     }
1153                 }
1154
1155                 false
1156             };
1157
1158             if let hir::TyRptr(lifetime_ref, ref mt) = inputs[0].node {
1159                 if let hir::TyPath(hir::QPath::Resolved(None, ref path)) = mt.ty.node {
1160                     if is_self_ty(path.def) {
1161                         if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1162                             let scope = Scope::Elision {
1163                                 elide: Elide::Exact(lifetime),
1164                                 s: self.scope
1165                             };
1166                             self.with(scope, |_, this| this.visit_ty(output));
1167                             return;
1168                         }
1169                     }
1170                 }
1171             }
1172         }
1173
1174         // Second, if there was exactly one lifetime (either a substitution or a
1175         // reference) in the arguments, then any anonymous regions in the output
1176         // have that lifetime.
1177         let mut possible_implied_output_region = None;
1178         let mut lifetime_count = 0;
1179         let arg_lifetimes = inputs.iter().enumerate().skip(has_self as usize).map(|(i, input)| {
1180             let mut gather = GatherLifetimes {
1181                 map: self.map,
1182                 binder_depth: 1,
1183                 have_bound_regions: false,
1184                 lifetimes: FxHashSet()
1185             };
1186             gather.visit_ty(input);
1187
1188             lifetime_count += gather.lifetimes.len();
1189
1190             if lifetime_count == 1 && gather.lifetimes.len() == 1 {
1191                 // there's a chance that the unique lifetime of this
1192                 // iteration will be the appropriate lifetime for output
1193                 // parameters, so lets store it.
1194                 possible_implied_output_region = gather.lifetimes.iter().cloned().next();
1195             }
1196
1197             ElisionFailureInfo {
1198                 parent: body,
1199                 index: i,
1200                 lifetime_count: gather.lifetimes.len(),
1201                 have_bound_regions: gather.have_bound_regions
1202             }
1203         }).collect();
1204
1205         let elide = if lifetime_count == 1 {
1206             Elide::Exact(possible_implied_output_region.unwrap())
1207         } else {
1208             Elide::Error(arg_lifetimes)
1209         };
1210
1211         let scope = Scope::Elision {
1212             elide: elide,
1213             s: self.scope
1214         };
1215         self.with(scope, |_, this| this.visit_ty(output));
1216
1217         struct GatherLifetimes<'a> {
1218             map: &'a NamedRegionMap,
1219             binder_depth: u32,
1220             have_bound_regions: bool,
1221             lifetimes: FxHashSet<Region>,
1222         }
1223
1224         impl<'v, 'a> Visitor<'v> for GatherLifetimes<'a> {
1225             fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1226                 NestedVisitorMap::None
1227             }
1228
1229             fn visit_ty(&mut self, ty: &hir::Ty) {
1230                 if let hir::TyBareFn(_) = ty.node {
1231                     self.binder_depth += 1;
1232                 }
1233                 if let hir::TyTraitObject(ref bounds, ref lifetime) = ty.node {
1234                     for bound in bounds {
1235                         self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
1236                     }
1237
1238                     // Stay on the safe side and don't include the object
1239                     // lifetime default (which may not end up being used).
1240                     if !lifetime.is_elided() {
1241                         self.visit_lifetime(lifetime);
1242                     }
1243                 } else {
1244                     intravisit::walk_ty(self, ty);
1245                 }
1246                 if let hir::TyBareFn(_) = ty.node {
1247                     self.binder_depth -= 1;
1248                 }
1249             }
1250
1251             fn visit_poly_trait_ref(&mut self,
1252                                     trait_ref: &hir::PolyTraitRef,
1253                                     modifier: hir::TraitBoundModifier) {
1254                 self.binder_depth += 1;
1255                 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
1256                 self.binder_depth -= 1;
1257             }
1258
1259             fn visit_lifetime_def(&mut self, lifetime_def: &hir::LifetimeDef) {
1260                 for l in &lifetime_def.bounds { self.visit_lifetime(l); }
1261             }
1262
1263             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
1264                 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1265                     match lifetime {
1266                         Region::LateBound(debruijn, _) |
1267                         Region::LateBoundAnon(debruijn, _)
1268                                 if debruijn.depth < self.binder_depth => {
1269                             self.have_bound_regions = true;
1270                         }
1271                         _ => {
1272                             self.lifetimes.insert(lifetime.from_depth(self.binder_depth));
1273                         }
1274                     }
1275                 }
1276             }
1277         }
1278
1279     }
1280
1281     fn resolve_elided_lifetimes(&mut self, lifetime_refs: &[hir::Lifetime]) {
1282         if lifetime_refs.is_empty() {
1283             return;
1284         }
1285
1286         let span = lifetime_refs[0].span;
1287         let mut late_depth = 0;
1288         let mut scope = self.scope;
1289         let error = loop {
1290             match *scope {
1291                 // Do not assign any resolution, it will be inferred.
1292                 Scope::Body { .. } => return,
1293
1294                 Scope::Root => break None,
1295
1296                 Scope::Binder { s, .. } => {
1297                     late_depth += 1;
1298                     scope = s;
1299                 }
1300
1301                 Scope::Elision { ref elide, .. } => {
1302                     let lifetime = match *elide {
1303                         Elide::FreshLateAnon(ref counter) => {
1304                             for lifetime_ref in lifetime_refs {
1305                                 let lifetime = Region::late_anon(counter).shifted(late_depth);
1306                                 self.insert_lifetime(lifetime_ref, lifetime);
1307                             }
1308                             return;
1309                         }
1310                         Elide::Exact(l) => l.shifted(late_depth),
1311                         Elide::Error(ref e) => break Some(e)
1312                     };
1313                     for lifetime_ref in lifetime_refs {
1314                         self.insert_lifetime(lifetime_ref, lifetime);
1315                     }
1316                     return;
1317                 }
1318
1319                 Scope::ObjectLifetimeDefault { s, .. } => {
1320                     scope = s;
1321                 }
1322             }
1323         };
1324
1325         let mut err = struct_span_err!(self.sess, span, E0106,
1326             "missing lifetime specifier{}",
1327             if lifetime_refs.len() > 1 { "s" } else { "" });
1328         let msg = if lifetime_refs.len() > 1 {
1329             format!("expected {} lifetime parameters", lifetime_refs.len())
1330         } else {
1331             format!("expected lifetime parameter")
1332         };
1333         err.span_label(span, &msg);
1334
1335         if let Some(params) = error {
1336             if lifetime_refs.len() == 1 {
1337                 self.report_elision_failure(&mut err, params);
1338             }
1339         }
1340         err.emit();
1341     }
1342
1343     fn report_elision_failure(&mut self,
1344                               db: &mut DiagnosticBuilder,
1345                               params: &[ElisionFailureInfo]) {
1346         let mut m = String::new();
1347         let len = params.len();
1348
1349         let elided_params: Vec<_> = params.iter().cloned()
1350                                           .filter(|info| info.lifetime_count > 0)
1351                                           .collect();
1352
1353         let elided_len = elided_params.len();
1354
1355         for (i, info) in elided_params.into_iter().enumerate() {
1356             let ElisionFailureInfo {
1357                 parent, index, lifetime_count: n, have_bound_regions
1358             } = info;
1359
1360             let help_name = if let Some(body) = parent {
1361                 let arg = &self.hir_map.body(body).arguments[index];
1362                 format!("`{}`", self.hir_map.node_to_pretty_string(arg.pat.id))
1363             } else {
1364                 format!("argument {}", index + 1)
1365             };
1366
1367             m.push_str(&(if n == 1 {
1368                 help_name
1369             } else {
1370                 format!("one of {}'s {} elided {}lifetimes", help_name, n,
1371                         if have_bound_regions { "free " } else { "" } )
1372             })[..]);
1373
1374             if elided_len == 2 && i == 0 {
1375                 m.push_str(" or ");
1376             } else if i + 2 == elided_len {
1377                 m.push_str(", or ");
1378             } else if i != elided_len - 1 {
1379                 m.push_str(", ");
1380             }
1381
1382         }
1383
1384         if len == 0 {
1385             help!(db,
1386                   "this function's return type contains a borrowed value, but \
1387                    there is no value for it to be borrowed from");
1388             help!(db,
1389                   "consider giving it a 'static lifetime");
1390         } else if elided_len == 0 {
1391             help!(db,
1392                   "this function's return type contains a borrowed value with \
1393                    an elided lifetime, but the lifetime cannot be derived from \
1394                    the arguments");
1395             help!(db,
1396                   "consider giving it an explicit bounded or 'static \
1397                    lifetime");
1398         } else if elided_len == 1 {
1399             help!(db,
1400                   "this function's return type contains a borrowed value, but \
1401                    the signature does not say which {} it is borrowed from",
1402                   m);
1403         } else {
1404             help!(db,
1405                   "this function's return type contains a borrowed value, but \
1406                    the signature does not say whether it is borrowed from {}",
1407                   m);
1408         }
1409     }
1410
1411     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &hir::Lifetime) {
1412         let mut late_depth = 0;
1413         let mut scope = self.scope;
1414         let lifetime = loop {
1415             match *scope {
1416                 Scope::Binder { s, .. } => {
1417                     late_depth += 1;
1418                     scope = s;
1419                 }
1420
1421                 Scope::Root |
1422                 Scope::Elision { .. } => break Region::Static,
1423
1424                 Scope::Body { .. } |
1425                 Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
1426
1427                 Scope::ObjectLifetimeDefault { lifetime: Some(l), .. } => break l
1428             }
1429         };
1430         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
1431     }
1432
1433     fn check_lifetime_defs(&mut self, old_scope: ScopeRef, lifetimes: &[hir::LifetimeDef]) {
1434         for i in 0..lifetimes.len() {
1435             let lifetime_i = &lifetimes[i];
1436
1437             for lifetime in lifetimes {
1438                 if lifetime.lifetime.is_static() {
1439                     let lifetime = lifetime.lifetime;
1440                     let mut err = struct_span_err!(self.sess, lifetime.span, E0262,
1441                                   "invalid lifetime parameter name: `{}`", lifetime.name);
1442                     err.span_label(lifetime.span,
1443                                    &format!("{} is a reserved lifetime name", lifetime.name));
1444                     err.emit();
1445                 }
1446             }
1447
1448             // It is a hard error to shadow a lifetime within the same scope.
1449             for j in i + 1..lifetimes.len() {
1450                 let lifetime_j = &lifetimes[j];
1451
1452                 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
1453                     struct_span_err!(self.sess, lifetime_j.lifetime.span, E0263,
1454                                      "lifetime name `{}` declared twice in the same scope",
1455                                      lifetime_j.lifetime.name)
1456                         .span_label(lifetime_j.lifetime.span,
1457                                     &format!("declared twice"))
1458                         .span_label(lifetime_i.lifetime.span,
1459                                    &format!("previous declaration here"))
1460                         .emit();
1461                 }
1462             }
1463
1464             // It is a soft error to shadow a lifetime within a parent scope.
1465             self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
1466
1467             for bound in &lifetime_i.bounds {
1468                 if !bound.is_static() {
1469                     self.resolve_lifetime_ref(bound);
1470                 } else {
1471                     self.insert_lifetime(bound, Region::Static);
1472                     self.sess.struct_span_warn(lifetime_i.lifetime.span.to(bound.span),
1473                         &format!("unnecessary lifetime parameter `{}`", lifetime_i.lifetime.name))
1474                         .help(&format!("you can use the `'static` lifetime directly, in place \
1475                                         of `{}`", lifetime_i.lifetime.name))
1476                         .emit();
1477                 }
1478             }
1479         }
1480     }
1481
1482     fn check_lifetime_def_for_shadowing(&self,
1483                                         mut old_scope: ScopeRef,
1484                                         lifetime: &hir::Lifetime)
1485     {
1486         for &(label, label_span) in &self.labels_in_fn {
1487             // FIXME (#24278): non-hygienic comparison
1488             if lifetime.name == label {
1489                 signal_shadowing_problem(self.sess,
1490                                          lifetime.name,
1491                                          original_label(label_span),
1492                                          shadower_lifetime(&lifetime));
1493                 return;
1494             }
1495         }
1496
1497         loop {
1498             match *old_scope {
1499                 Scope::Body { s, .. } |
1500                 Scope::Elision { s, .. } |
1501                 Scope::ObjectLifetimeDefault { s, .. } => {
1502                     old_scope = s;
1503                 }
1504
1505                 Scope::Root => {
1506                     return;
1507                 }
1508
1509                 Scope::Binder { ref lifetimes, s } => {
1510                     if let Some(&def) = lifetimes.get(&lifetime.name) {
1511                         signal_shadowing_problem(
1512                             self.sess,
1513                             lifetime.name,
1514                             original_lifetime(self.hir_map.span(def.id().unwrap())),
1515                             shadower_lifetime(&lifetime));
1516                         return;
1517                     }
1518
1519                     old_scope = s;
1520                 }
1521             }
1522         }
1523     }
1524
1525     fn insert_lifetime(&mut self,
1526                        lifetime_ref: &hir::Lifetime,
1527                        def: Region) {
1528         if lifetime_ref.id == ast::DUMMY_NODE_ID {
1529             span_bug!(lifetime_ref.span,
1530                       "lifetime reference not renumbered, \
1531                        probably a bug in syntax::fold");
1532         }
1533
1534         debug!("{} resolved to {:?} span={:?}",
1535                self.hir_map.node_to_string(lifetime_ref.id),
1536                def,
1537                self.sess.codemap().span_to_string(lifetime_ref.span));
1538         self.map.defs.insert(lifetime_ref.id, def);
1539     }
1540 }
1541
1542 ///////////////////////////////////////////////////////////////////////////
1543
1544 /// Detects late-bound lifetimes and inserts them into
1545 /// `map.late_bound`.
1546 ///
1547 /// A region declared on a fn is **late-bound** if:
1548 /// - it is constrained by an argument type;
1549 /// - it does not appear in a where-clause.
1550 ///
1551 /// "Constrained" basically means that it appears in any type but
1552 /// not amongst the inputs to a projection.  In other words, `<&'a
1553 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
1554 fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
1555                                fn_def_id: DefId,
1556                                decl: &hir::FnDecl,
1557                                generics: &hir::Generics) {
1558     debug!("insert_late_bound_lifetimes(decl={:?}, generics={:?})", decl, generics);
1559
1560     let mut constrained_by_input = ConstrainedCollector { regions: FxHashSet() };
1561     for arg_ty in &decl.inputs {
1562         constrained_by_input.visit_ty(arg_ty);
1563     }
1564
1565     let mut appears_in_output = AllCollector {
1566         regions: FxHashSet(),
1567         impl_trait: false
1568     };
1569     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
1570
1571     debug!("insert_late_bound_lifetimes: constrained_by_input={:?}",
1572            constrained_by_input.regions);
1573
1574     // Walk the lifetimes that appear in where clauses.
1575     //
1576     // Subtle point: because we disallow nested bindings, we can just
1577     // ignore binders here and scrape up all names we see.
1578     let mut appears_in_where_clause = AllCollector {
1579         regions: FxHashSet(),
1580         impl_trait: false
1581     };
1582     for ty_param in generics.ty_params.iter() {
1583         walk_list!(&mut appears_in_where_clause,
1584                    visit_ty_param_bound,
1585                    &ty_param.bounds);
1586     }
1587     walk_list!(&mut appears_in_where_clause,
1588                visit_where_predicate,
1589                &generics.where_clause.predicates);
1590     for lifetime_def in &generics.lifetimes {
1591         if !lifetime_def.bounds.is_empty() {
1592             // `'a: 'b` means both `'a` and `'b` are referenced
1593             appears_in_where_clause.visit_lifetime_def(lifetime_def);
1594         }
1595     }
1596
1597     debug!("insert_late_bound_lifetimes: appears_in_where_clause={:?}",
1598            appears_in_where_clause.regions);
1599
1600     // Late bound regions are those that:
1601     // - appear in the inputs
1602     // - do not appear in the where-clauses
1603     // - are not implicitly captured by `impl Trait`
1604     for lifetime in &generics.lifetimes {
1605         let name = lifetime.lifetime.name;
1606
1607         // appears in the where clauses? early-bound.
1608         if appears_in_where_clause.regions.contains(&name) { continue; }
1609
1610         // any `impl Trait` in the return type? early-bound.
1611         if appears_in_output.impl_trait { continue; }
1612
1613         // does not appear in the inputs, but appears in the return
1614         // type? eventually this will be early-bound, but for now we
1615         // just mark it so we can issue warnings.
1616         let constrained_by_input = constrained_by_input.regions.contains(&name);
1617         let appears_in_output = appears_in_output.regions.contains(&name);
1618         if !constrained_by_input && appears_in_output {
1619             debug!("inserting issue_32330 entry for {:?}, {:?} on {:?}",
1620                    lifetime.lifetime.id,
1621                    name,
1622                    fn_def_id);
1623             map.issue_32330.insert(
1624                 lifetime.lifetime.id,
1625                 ty::Issue32330 {
1626                     fn_def_id: fn_def_id,
1627                     region_name: name,
1628                 });
1629             continue;
1630         }
1631
1632         debug!("insert_late_bound_lifetimes: \
1633                 lifetime {:?} with id {:?} is late-bound",
1634                lifetime.lifetime.name, lifetime.lifetime.id);
1635
1636         let inserted = map.late_bound.insert(lifetime.lifetime.id);
1637         assert!(inserted, "visited lifetime {:?} twice", lifetime.lifetime.id);
1638     }
1639
1640     return;
1641
1642     struct ConstrainedCollector {
1643         regions: FxHashSet<ast::Name>,
1644     }
1645
1646     impl<'v> Visitor<'v> for ConstrainedCollector {
1647         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1648             NestedVisitorMap::None
1649         }
1650
1651         fn visit_ty(&mut self, ty: &'v hir::Ty) {
1652             match ty.node {
1653                 hir::TyPath(hir::QPath::Resolved(Some(_), _)) |
1654                 hir::TyPath(hir::QPath::TypeRelative(..)) => {
1655                     // ignore lifetimes appearing in associated type
1656                     // projections, as they are not *constrained*
1657                     // (defined above)
1658                 }
1659
1660                 hir::TyPath(hir::QPath::Resolved(None, ref path)) => {
1661                     // consider only the lifetimes on the final
1662                     // segment; I am not sure it's even currently
1663                     // valid to have them elsewhere, but even if it
1664                     // is, those would be potentially inputs to
1665                     // projections
1666                     if let Some(last_segment) = path.segments.last() {
1667                         self.visit_path_segment(path.span, last_segment);
1668                     }
1669                 }
1670
1671                 _ => {
1672                     intravisit::walk_ty(self, ty);
1673                 }
1674             }
1675         }
1676
1677         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
1678             self.regions.insert(lifetime_ref.name);
1679         }
1680     }
1681
1682     struct AllCollector {
1683         regions: FxHashSet<ast::Name>,
1684         impl_trait: bool
1685     }
1686
1687     impl<'v> Visitor<'v> for AllCollector {
1688         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1689             NestedVisitorMap::None
1690         }
1691
1692         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
1693             self.regions.insert(lifetime_ref.name);
1694         }
1695
1696         fn visit_ty(&mut self, ty: &hir::Ty) {
1697             if let hir::TyImplTrait(_) = ty.node {
1698                 self.impl_trait = true;
1699             }
1700             intravisit::walk_ty(self, ty);
1701         }
1702     }
1703 }