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