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