src/librustc/middle/resolve_lifetime.rs

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