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 pub use self::DefRegion::*;
  19 use self::ScopeChain::*;
  20
  21 use dep_graph::DepNode;
  22 use hir::map::Map;
  23 use session::Session;
  24 use hir::def::Def;
  25 use hir::def_id::DefId;
  26 use middle::region;
  27 use ty;
  28 use std::mem::replace;
  29 use syntax::ast;
  30 use syntax::symbol::keywords;
  31 use syntax_pos::Span;
  32 use util::nodemap::NodeMap;
  33
  34 use rustc_data_structures::fx::FxHashSet;
  35 use hir;
  36 use hir::intravisit::{self, Visitor, FnKind, NestedVisitorMap};
  37
  38 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  39 pub enum DefRegion {
  40     DefStaticRegion,
  41     DefEarlyBoundRegion(/* index */ u32,
  42                         /* lifetime decl */ ast::NodeId),
  43     DefLateBoundRegion(ty::DebruijnIndex,
  44                        /* lifetime decl */ ast::NodeId),
  45     DefFreeRegion(region::CallSiteScopeData,
  46                   /* lifetime decl */ ast::NodeId),
  47 }
  48
  49 // Maps the id of each lifetime reference to the lifetime decl
  50 // that it corresponds to.
  51 pub struct NamedRegionMap {
  52     // maps from every use of a named (not anonymous) lifetime to a
  53     // `DefRegion` describing how that region is bound
  54     pub defs: NodeMap<DefRegion>,
  55
  56     // the set of lifetime def ids that are late-bound; late-bound ids
  57     // are named regions appearing in fn arguments that do not appear
  58     // in where-clauses
  59     pub late_bound: NodeMap<ty::Issue32330>,
  60 }
  61
  62 struct LifetimeContext<'a, 'tcx: 'a> {
  63     sess: &'a Session,
  64     hir_map: &'a Map<'tcx>,
  65     map: &'a mut NamedRegionMap,
  66     scope: Scope<'a>,
  67     // Deep breath. Our representation for poly trait refs contains a single
  68     // binder and thus we only allow a single level of quantification. However,
  69     // the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
  70     // and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
  71     // correct when representing these constraints, we should only introduce one
  72     // scope. However, we want to support both locations for the quantifier and
  73     // during lifetime resolution we want precise information (so we can't
  74     // desugar in an earlier phase).
  75
  76     // SO, if we encounter a quantifier at the outer scope, we set
  77     // trait_ref_hack to true (and introduce a scope), and then if we encounter
  78     // a quantifier at the inner scope, we error. If trait_ref_hack is false,
  79     // then we introduce the scope at the inner quantifier.
  80
  81     // I'm sorry.
  82     trait_ref_hack: bool,
  83
  84     // List of labels in the function/method currently under analysis.
  85     labels_in_fn: Vec<(ast::Name, Span)>,
  86 }
  87
  88 #[derive(PartialEq, Debug)]
  89 enum ScopeChain<'a> {
  90     /// EarlyScope(['a, 'b, ...], start, s) extends s with early-bound
  91     /// lifetimes, with consecutive parameter indices from `start`.
  92     /// That is, 'a has index `start`, 'b has index `start + 1`, etc.
  93     /// Indices before `start` correspond to other generic parameters
  94     /// of a parent item (trait/impl of a method), or `Self` in traits.
  95     EarlyScope(&'a [hir::LifetimeDef], u32, Scope<'a>),
  96     /// LateScope(['a, 'b, ...], s) extends s with late-bound
  97     /// lifetimes introduced by the declaration binder_id.
  98     LateScope(&'a [hir::LifetimeDef], Scope<'a>),
  99
 100     /// lifetimes introduced by a fn are scoped to the call-site for that fn.
 101     FnScope { fn_id: ast::NodeId, body_id: ast::NodeId, s: Scope<'a> },
 102     RootScope
 103 }
 104
 105 type Scope<'a> = &'a ScopeChain<'a>;
 106
 107 static ROOT_SCOPE: ScopeChain<'static> = RootScope;
 108
 109 pub fn krate(sess: &Session,
 110              hir_map: &Map)
 111              -> Result<NamedRegionMap, usize> {
 112     let _task = hir_map.dep_graph.in_task(DepNode::ResolveLifetimes);
 113     let krate = hir_map.krate();
 114     let mut map = NamedRegionMap {
 115         defs: NodeMap(),
 116         late_bound: NodeMap(),
 117     };
 118     sess.track_errors(|| {
 119         intravisit::walk_crate(&mut LifetimeContext {
 120             sess: sess,
 121             hir_map: hir_map,
 122             map: &mut map,
 123             scope: &ROOT_SCOPE,
 124             trait_ref_hack: false,
 125             labels_in_fn: vec![],
 126         }, krate);
 127     })?;
 128     Ok(map)
 129 }
 130
 131 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 132     // Override the nested functions -- lifetimes follow lexical scope,
 133     // so it's convenient to walk the tree in lexical order.
 134     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 135         NestedVisitorMap::All(&self.hir_map)
 136     }
 137
 138     fn visit_item(&mut self, item: &'tcx hir::Item) {
 139         // Save labels for nested items.
 140         let saved_labels_in_fn = replace(&mut self.labels_in_fn, vec![]);
 141
 142         // Items always introduce a new root scope
 143         self.with(RootScope, |_, this| {
 144             match item.node {
 145                 hir::ItemFn(..) => {
 146                     // Fn lifetimes get added in visit_fn below:
 147                     intravisit::walk_item(this, item);
 148                 }
 149                 hir::ItemExternCrate(_) |
 150                 hir::ItemUse(..) |
 151                 hir::ItemMod(..) |
 152                 hir::ItemDefaultImpl(..) |
 153                 hir::ItemForeignMod(..) |
 154                 hir::ItemStatic(..) |
 155                 hir::ItemConst(..) => {
 156                     // These sorts of items have no lifetime parameters at all.
 157                     intravisit::walk_item(this, item);
 158                 }
 159                 hir::ItemTy(_, ref generics) |
 160                 hir::ItemEnum(_, ref generics) |
 161                 hir::ItemStruct(_, ref generics) |
 162                 hir::ItemUnion(_, ref generics) |
 163                 hir::ItemTrait(_, ref generics, ..) |
 164                 hir::ItemImpl(_, _, ref generics, ..) => {
 165                     // These kinds of items have only early bound lifetime parameters.
 166                     let lifetimes = &generics.lifetimes;
 167                     let start = if let hir::ItemTrait(..) = item.node {
 168                         1 // Self comes before lifetimes
 169                     } else {
 170                         0
 171                     };
 172                     this.with(EarlyScope(lifetimes, start, &ROOT_SCOPE), |old_scope, this| {
 173                         this.check_lifetime_defs(old_scope, lifetimes);
 174                         intravisit::walk_item(this, item);
 175                     });
 176                 }
 177             }
 178         });
 179
 180         // Done traversing the item; remove any labels it created
 181         self.labels_in_fn = saved_labels_in_fn;
 182     }
 183
 184     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem) {
 185         // Items save/restore the set of labels. This way inner items
 186         // can freely reuse names, be they loop labels or lifetimes.
 187         let saved = replace(&mut self.labels_in_fn, vec![]);
 188
 189         // Items always introduce a new root scope
 190         self.with(RootScope, |_, this| {
 191             match item.node {
 192                 hir::ForeignItemFn(ref decl, _, ref generics) => {
 193                     this.visit_early_late(item.id, decl, generics, |this| {
 194                         intravisit::walk_foreign_item(this, item);
 195                     })
 196                 }
 197                 hir::ForeignItemStatic(..) => {
 198                     intravisit::walk_foreign_item(this, item);
 199                 }
 200             }
 201         });
 202
 203         // Done traversing the item; restore saved set of labels.
 204         replace(&mut self.labels_in_fn, saved);
 205     }
 206
 207     fn visit_fn(&mut self, fk: FnKind<'tcx>, decl: &'tcx hir::FnDecl,
 208                 b: hir::BodyId, s: Span, fn_id: ast::NodeId) {
 209         match fk {
 210             FnKind::ItemFn(_, generics, ..) => {
 211                 self.visit_early_late(fn_id,decl, generics, |this| {
 212                     this.add_scope_and_walk_fn(fk, decl, b, s, fn_id)
 213                 })
 214             }
 215             FnKind::Method(_, sig, ..) => {
 216                 self.visit_early_late(
 217                     fn_id,
 218                     decl,
 219                     &sig.generics,
 220                     |this| this.add_scope_and_walk_fn(fk, decl, b, s, fn_id));
 221             }
 222             FnKind::Closure(_) => {
 223                 // Closures have their own set of labels, save labels just
 224                 // like for foreign items above.
 225                 let saved = replace(&mut self.labels_in_fn, vec![]);
 226                 let result = self.add_scope_and_walk_fn(fk, decl, b, s, fn_id);
 227                 replace(&mut self.labels_in_fn, saved);
 228                 result
 229             }
 230         }
 231     }
 232
 233     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 234         match ty.node {
 235             hir::TyBareFn(ref c) => {
 236                 self.with(LateScope(&c.lifetimes, self.scope), |old_scope, this| {
 237                     // a bare fn has no bounds, so everything
 238                     // contained within is scoped within its binder.
 239                     this.check_lifetime_defs(old_scope, &c.lifetimes);
 240                     intravisit::walk_ty(this, ty);
 241                 });
 242             }
 243             hir::TyPath(hir::QPath::Resolved(None, ref path)) => {
 244                 // if this path references a trait, then this will resolve to
 245                 // a trait ref, which introduces a binding scope.
 246                 match path.def {
 247                     Def::Trait(..) => {
 248                         self.with(LateScope(&[], self.scope), |_, this| {
 249                             this.visit_path(path, ty.id);
 250                         });
 251                     }
 252                     _ => {
 253                         intravisit::walk_ty(self, ty);
 254                     }
 255                 }
 256             }
 257             _ => {
 258                 intravisit::walk_ty(self, ty)
 259             }
 260         }
 261     }
 262
 263     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 264         // We reset the labels on every trait item, so that different
 265         // methods in an impl can reuse label names.
 266         let saved = replace(&mut self.labels_in_fn, vec![]);
 267
 268         if let hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(_)) =
 269                 trait_item.node {
 270             self.visit_early_late(
 271                 trait_item.id,
 272                 &sig.decl, &sig.generics,
 273                 |this| intravisit::walk_trait_item(this, trait_item))
 274         } else {
 275             intravisit::walk_trait_item(self, trait_item);
 276         }
 277
 278         replace(&mut self.labels_in_fn, saved);
 279     }
 280
 281     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
 282         if lifetime_ref.name == keywords::StaticLifetime.name() {
 283             self.insert_lifetime(lifetime_ref, DefStaticRegion);
 284             return;
 285         }
 286         self.resolve_lifetime_ref(lifetime_ref);
 287     }
 288
 289     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 290         for ty_param in generics.ty_params.iter() {
 291             walk_list!(self, visit_ty_param_bound, &ty_param.bounds);
 292             if let Some(ref ty) = ty_param.default {
 293                 self.visit_ty(&ty);
 294             }
 295         }
 296         for predicate in &generics.where_clause.predicates {
 297             match predicate {
 298                 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate{ ref bounded_ty,
 299                                                                                ref bounds,
 300                                                                                ref bound_lifetimes,
 301                                                                                .. }) => {
 302                     if !bound_lifetimes.is_empty() {
 303                         self.trait_ref_hack = true;
 304                         let result = self.with(LateScope(bound_lifetimes, self.scope),
 305                                                |old_scope, this| {
 306                             this.check_lifetime_defs(old_scope, bound_lifetimes);
 307                             this.visit_ty(&bounded_ty);
 308                             walk_list!(this, visit_ty_param_bound, bounds);
 309                         });
 310                         self.trait_ref_hack = false;
 311                         result
 312                     } else {
 313                         self.visit_ty(&bounded_ty);
 314                         walk_list!(self, visit_ty_param_bound, bounds);
 315                     }
 316                 }
 317                 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate{ref lifetime,
 318                                                                                 ref bounds,
 319                                                                                 .. }) => {
 320
 321                     self.visit_lifetime(lifetime);
 322                     for bound in bounds {
 323                         self.visit_lifetime(bound);
 324                     }
 325                 }
 326                 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate{ref lhs_ty,
 327                                                                         ref rhs_ty,
 328                                                                         .. }) => {
 329                     self.visit_ty(lhs_ty);
 330                     self.visit_ty(rhs_ty);
 331                 }
 332             }
 333         }
 334     }
 335
 336     fn visit_poly_trait_ref(&mut self,
 337                             trait_ref: &'tcx hir::PolyTraitRef,
 338                             _modifier: &'tcx hir::TraitBoundModifier) {
 339         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 340
 341         if !self.trait_ref_hack || !trait_ref.bound_lifetimes.is_empty() {
 342             if self.trait_ref_hack {
 343                 span_err!(self.sess, trait_ref.span, E0316,
 344                           "nested quantification of lifetimes");
 345             }
 346             self.with(LateScope(&trait_ref.bound_lifetimes, self.scope), |old_scope, this| {
 347                 this.check_lifetime_defs(old_scope, &trait_ref.bound_lifetimes);
 348                 for lifetime in &trait_ref.bound_lifetimes {
 349                     this.visit_lifetime_def(lifetime);
 350                 }
 351                 intravisit::walk_path(this, &trait_ref.trait_ref.path)
 352             })
 353         } else {
 354             self.visit_trait_ref(&trait_ref.trait_ref)
 355         }
 356     }
 357 }
 358
 359 #[derive(Copy, Clone, PartialEq)]
 360 enum ShadowKind { Label, Lifetime }
 361 struct Original { kind: ShadowKind, span: Span }
 362 struct Shadower { kind: ShadowKind, span: Span }
 363
 364 fn original_label(span: Span) -> Original {
 365     Original { kind: ShadowKind::Label, span: span }
 366 }
 367 fn shadower_label(span: Span) -> Shadower {
 368     Shadower { kind: ShadowKind::Label, span: span }
 369 }
 370 fn original_lifetime(l: &hir::Lifetime) -> Original {
 371     Original { kind: ShadowKind::Lifetime, span: l.span }
 372 }
 373 fn shadower_lifetime(l: &hir::Lifetime) -> Shadower {
 374     Shadower { kind: ShadowKind::Lifetime, span: l.span }
 375 }
 376
 377 impl ShadowKind {
 378     fn desc(&self) -> &'static str {
 379         match *self {
 380             ShadowKind::Label => "label",
 381             ShadowKind::Lifetime => "lifetime",
 382         }
 383     }
 384 }
 385
 386 fn signal_shadowing_problem(sess: &Session, name: ast::Name, orig: Original, shadower: Shadower) {
 387     let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
 388         // lifetime/lifetime shadowing is an error
 389         struct_span_err!(sess, shadower.span, E0496,
 390                          "{} name `{}` shadows a \
 391                           {} name that is already in scope",
 392                          shadower.kind.desc(), name, orig.kind.desc())
 393     } else {
 394         // shadowing involving a label is only a warning, due to issues with
 395         // labels and lifetimes not being macro-hygienic.
 396         sess.struct_span_warn(shadower.span,
 397                               &format!("{} name `{}` shadows a \
 398                                         {} name that is already in scope",
 399                                        shadower.kind.desc(), name, orig.kind.desc()))
 400     };
 401     err.span_label(orig.span, &"first declared here");
 402     err.span_label(shadower.span,
 403                    &format!("lifetime {} already in scope", name));
 404     err.emit();
 405 }
 406
 407 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
 408 // if one of the label shadows a lifetime or another label.
 409 fn extract_labels(ctxt: &mut LifetimeContext, b: hir::BodyId) {
 410     struct GatherLabels<'a> {
 411         sess: &'a Session,
 412         scope: Scope<'a>,
 413         labels_in_fn: &'a mut Vec<(ast::Name, Span)>,
 414     }
 415
 416     let mut gather = GatherLabels {
 417         sess: ctxt.sess,
 418         scope: ctxt.scope,
 419         labels_in_fn: &mut ctxt.labels_in_fn,
 420     };
 421     gather.visit_body(ctxt.hir_map.body(b));
 422     return;
 423
 424     impl<'v, 'a> Visitor<'v> for GatherLabels<'a> {
 425         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
 426             NestedVisitorMap::None
 427         }
 428
 429         fn visit_expr(&mut self, ex: &'v hir::Expr) {
 430             // do not recurse into closures defined in the block
 431             // since they are treated as separate fns from the POV of
 432             // labels_in_fn
 433             if let hir::ExprClosure(..) = ex.node {
 434                 return
 435             }
 436             if let Some((label, label_span)) = expression_label(ex) {
 437                 for &(prior, prior_span) in &self.labels_in_fn[..] {
 438                     // FIXME (#24278): non-hygienic comparison
 439                     if label == prior {
 440                         signal_shadowing_problem(self.sess,
 441                                                  label,
 442                                                  original_label(prior_span),
 443                                                  shadower_label(label_span));
 444                     }
 445                 }
 446
 447                 check_if_label_shadows_lifetime(self.sess,
 448                                                 self.scope,
 449                                                 label,
 450                                                 label_span);
 451
 452                 self.labels_in_fn.push((label, label_span));
 453             }
 454             intravisit::walk_expr(self, ex)
 455         }
 456
 457         fn visit_item(&mut self, _: &hir::Item) {
 458             // do not recurse into items defined in the block
 459         }
 460     }
 461
 462     fn expression_label(ex: &hir::Expr) -> Option<(ast::Name, Span)> {
 463         match ex.node {
 464             hir::ExprWhile(.., Some(label)) |
 465             hir::ExprLoop(_, Some(label), _) => Some((label.node, label.span)),
 466             _ => None,
 467         }
 468     }
 469
 470     fn check_if_label_shadows_lifetime<'a>(sess: &'a Session,
 471                                            mut scope: Scope<'a>,
 472                                            label: ast::Name,
 473                                            label_span: Span) {
 474         loop {
 475             match *scope {
 476                 FnScope { s, .. } => { scope = s; }
 477                 RootScope => { return; }
 478
 479                 EarlyScope(lifetimes, _, s) |
 480                 LateScope(lifetimes, s) => {
 481                     for lifetime_def in lifetimes {
 482                         // FIXME (#24278): non-hygienic comparison
 483                         if label == lifetime_def.lifetime.name {
 484                             signal_shadowing_problem(
 485                                 sess,
 486                                 label,
 487                                 original_lifetime(&lifetime_def.lifetime),
 488                                 shadower_label(label_span));
 489                             return;
 490                         }
 491                     }
 492                     scope = s;
 493                 }
 494             }
 495         }
 496     }
 497 }
 498
 499 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 500     fn add_scope_and_walk_fn(&mut self,
 501                              fk: FnKind<'tcx>,
 502                              fd: &'tcx hir::FnDecl,
 503                              fb: hir::BodyId,
 504                              _span: Span,
 505                              fn_id: ast::NodeId) {
 506         match fk {
 507             FnKind::ItemFn(_, generics, ..) => {
 508                 intravisit::walk_fn_decl(self, fd);
 509                 self.visit_generics(generics);
 510             }
 511             FnKind::Method(_, sig, ..) => {
 512                 intravisit::walk_fn_decl(self, fd);
 513                 self.visit_generics(&sig.generics);
 514             }
 515             FnKind::Closure(_) => {
 516                 intravisit::walk_fn_decl(self, fd);
 517             }
 518         }
 519
 520         // After inpsecting the decl, add all labels from the body to
 521         // `self.labels_in_fn`.
 522         extract_labels(self, fb);
 523
 524         self.with(FnScope { fn_id: fn_id, body_id: fb.node_id, s: self.scope },
 525                   |_old_scope, this| this.visit_nested_body(fb))
 526     }
 527
 528     // FIXME(#37666) this works around a limitation in the region inferencer
 529     fn hack<F>(&mut self, f: F) where
 530         F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
 531     {
 532         f(self)
 533     }
 534
 535     fn with<F>(&mut self, wrap_scope: ScopeChain, f: F) where
 536         F: for<'b> FnOnce(Scope, &mut LifetimeContext<'b, 'tcx>),
 537     {
 538         let LifetimeContext {sess, hir_map, ref mut map, ..} = *self;
 539         let mut this = LifetimeContext {
 540             sess: sess,
 541             hir_map: hir_map,
 542             map: *map,
 543             scope: &wrap_scope,
 544             trait_ref_hack: self.trait_ref_hack,
 545             labels_in_fn: self.labels_in_fn.clone(),
 546         };
 547         debug!("entering scope {:?}", this.scope);
 548         f(self.scope, &mut this);
 549         debug!("exiting scope {:?}", this.scope);
 550     }
 551
 552     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
 553     ///
 554     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
 555     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
 556     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
 557     ///
 558     /// For example:
 559     ///
 560     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
 561     ///
 562     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
 563     /// lifetimes may be interspersed together.
 564     ///
 565     /// If early bound lifetimes are present, we separate them into their own list (and likewise
 566     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
 567     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
 568     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
 569     /// ordering is not important there.
 570     fn visit_early_late<F>(&mut self,
 571                            fn_id: ast::NodeId,
 572                            decl: &'tcx hir::FnDecl,
 573                            generics: &'tcx hir::Generics,
 574                            walk: F) where
 575         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
 576     {
 577         let fn_def_id = self.hir_map.local_def_id(fn_id);
 578         insert_late_bound_lifetimes(self.map,
 579                                     fn_def_id,
 580                                     decl,
 581                                     generics);
 582
 583         let (late, early): (Vec<_>, _) =
 584             generics.lifetimes
 585                     .iter()
 586                     .cloned()
 587                     .partition(|l| self.map.late_bound.contains_key(&l.lifetime.id));
 588
 589         // Find the start of nested early scopes, e.g. in methods.
 590         let mut start = 0;
 591         if let EarlyScope(..) = *self.scope {
 592             let parent = self.hir_map.expect_item(self.hir_map.get_parent(fn_id));
 593             if let hir::ItemTrait(..) = parent.node {
 594                 start += 1; // Self comes first.
 595             }
 596             match parent.node {
 597                 hir::ItemTrait(_, ref generics, ..) |
 598                 hir::ItemImpl(_, _, ref generics, ..) => {
 599                     start += generics.lifetimes.len() + generics.ty_params.len();
 600                 }
 601                 _ => {}
 602             }
 603         }
 604
 605         self.with(EarlyScope(&early, start as u32, self.scope), move |old_scope, this| {
 606             this.with(LateScope(&late, this.scope), move |_, this| {
 607                 this.check_lifetime_defs(old_scope, &generics.lifetimes);
 608                 this.hack(walk); // FIXME(#37666) workaround in place of `walk(this)`
 609             });
 610         });
 611     }
 612
 613     fn resolve_lifetime_ref(&mut self, lifetime_ref: &hir::Lifetime) {
 614         // Walk up the scope chain, tracking the number of fn scopes
 615         // that we pass through, until we find a lifetime with the
 616         // given name or we run out of scopes. If we encounter a code
 617         // block, then the lifetime is not bound but free, so switch
 618         // over to `resolve_free_lifetime_ref()` to complete the
 619         // search.
 620         let mut late_depth = 0;
 621         let mut scope = self.scope;
 622         loop {
 623             match *scope {
 624                 FnScope {fn_id, body_id, s } => {
 625                     return self.resolve_free_lifetime_ref(
 626                         region::CallSiteScopeData { fn_id: fn_id, body_id: body_id },
 627                         lifetime_ref,
 628                         s);
 629                 }
 630
 631                 RootScope => {
 632                     break;
 633                 }
 634
 635                 EarlyScope(lifetimes, start, s) => {
 636                     match search_lifetimes(lifetimes, lifetime_ref) {
 637                         Some((index, lifetime_def)) => {
 638                             let decl_id = lifetime_def.id;
 639                             let def = DefEarlyBoundRegion(start + index, decl_id);
 640                             self.insert_lifetime(lifetime_ref, def);
 641                             return;
 642                         }
 643                         None => {
 644                             scope = s;
 645                         }
 646                     }
 647                 }
 648
 649                 LateScope(lifetimes, s) => {
 650                     match search_lifetimes(lifetimes, lifetime_ref) {
 651                         Some((_index, lifetime_def)) => {
 652                             let decl_id = lifetime_def.id;
 653                             let debruijn = ty::DebruijnIndex::new(late_depth + 1);
 654                             let def = DefLateBoundRegion(debruijn, decl_id);
 655                             self.insert_lifetime(lifetime_ref, def);
 656                             return;
 657                         }
 658
 659                         None => {
 660                             late_depth += 1;
 661                             scope = s;
 662                         }
 663                     }
 664                 }
 665             }
 666         }
 667
 668         self.unresolved_lifetime_ref(lifetime_ref);
 669     }
 670
 671     fn resolve_free_lifetime_ref(&mut self,
 672                                  scope_data: region::CallSiteScopeData,
 673                                  lifetime_ref: &hir::Lifetime,
 674                                  scope: Scope) {
 675         debug!("resolve_free_lifetime_ref \
 676                 scope_data: {:?} lifetime_ref: {:?} scope: {:?}",
 677                scope_data, lifetime_ref, scope);
 678
 679         // Walk up the scope chain, tracking the outermost free scope,
 680         // until we encounter a scope that contains the named lifetime
 681         // or we run out of scopes.
 682         let mut scope_data = scope_data;
 683         let mut scope = scope;
 684         let mut search_result = None;
 685         loop {
 686             debug!("resolve_free_lifetime_ref \
 687                     scope_data: {:?} scope: {:?} search_result: {:?}",
 688                    scope_data, scope, search_result);
 689             match *scope {
 690                 FnScope { fn_id, body_id, s } => {
 691                     scope_data = region::CallSiteScopeData {
 692                         fn_id: fn_id, body_id: body_id
 693                     };
 694                     scope = s;
 695                 }
 696
 697                 RootScope => {
 698                     break;
 699                 }
 700
 701                 EarlyScope(lifetimes, _, s) |
 702                 LateScope(lifetimes, s) => {
 703                     search_result = search_lifetimes(lifetimes, lifetime_ref);
 704                     if search_result.is_some() {
 705                         break;
 706                     }
 707                     scope = s;
 708                 }
 709             }
 710         }
 711
 712         match search_result {
 713             Some((_depth, lifetime)) => {
 714                 let def = DefFreeRegion(scope_data, lifetime.id);
 715                 self.insert_lifetime(lifetime_ref, def);
 716             }
 717
 718             None => {
 719                 self.unresolved_lifetime_ref(lifetime_ref);
 720             }
 721         }
 722
 723     }
 724
 725     fn unresolved_lifetime_ref(&self, lifetime_ref: &hir::Lifetime) {
 726         struct_span_err!(self.sess, lifetime_ref.span, E0261,
 727             "use of undeclared lifetime name `{}`", lifetime_ref.name)
 728             .span_label(lifetime_ref.span, &format!("undeclared lifetime"))
 729             .emit();
 730     }
 731
 732     fn check_lifetime_defs(&mut self, old_scope: Scope, lifetimes: &[hir::LifetimeDef]) {
 733         for i in 0..lifetimes.len() {
 734             let lifetime_i = &lifetimes[i];
 735
 736             for lifetime in lifetimes {
 737                 if lifetime.lifetime.name == keywords::StaticLifetime.name() {
 738                     let lifetime = lifetime.lifetime;
 739                     let mut err = struct_span_err!(self.sess, lifetime.span, E0262,
 740                                   "invalid lifetime parameter name: `{}`", lifetime.name);
 741                     err.span_label(lifetime.span,
 742                                    &format!("{} is a reserved lifetime name", lifetime.name));
 743                     err.emit();
 744                 }
 745             }
 746
 747             // It is a hard error to shadow a lifetime within the same scope.
 748             for j in i + 1..lifetimes.len() {
 749                 let lifetime_j = &lifetimes[j];
 750
 751                 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
 752                     struct_span_err!(self.sess, lifetime_j.lifetime.span, E0263,
 753                                      "lifetime name `{}` declared twice in the same scope",
 754                                      lifetime_j.lifetime.name)
 755                         .span_label(lifetime_j.lifetime.span,
 756                                     &format!("declared twice"))
 757                         .span_label(lifetime_i.lifetime.span,
 758                                    &format!("previous declaration here"))
 759                         .emit();
 760                 }
 761             }
 762
 763             // It is a soft error to shadow a lifetime within a parent scope.
 764             self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
 765
 766             for bound in &lifetime_i.bounds {
 767                 self.resolve_lifetime_ref(bound);
 768             }
 769         }
 770     }
 771
 772     fn check_lifetime_def_for_shadowing(&self,
 773                                         mut old_scope: Scope,
 774                                         lifetime: &hir::Lifetime)
 775     {
 776         for &(label, label_span) in &self.labels_in_fn {
 777             // FIXME (#24278): non-hygienic comparison
 778             if lifetime.name == label {
 779                 signal_shadowing_problem(self.sess,
 780                                          lifetime.name,
 781                                          original_label(label_span),
 782                                          shadower_lifetime(&lifetime));
 783                 return;
 784             }
 785         }
 786
 787         loop {
 788             match *old_scope {
 789                 FnScope { s, .. } => {
 790                     old_scope = s;
 791                 }
 792
 793                 RootScope => {
 794                     return;
 795                 }
 796
 797                 EarlyScope(lifetimes, _, s) |
 798                 LateScope(lifetimes, s) => {
 799                     if let Some((_, lifetime_def)) = search_lifetimes(lifetimes, lifetime) {
 800                         signal_shadowing_problem(
 801                             self.sess,
 802                             lifetime.name,
 803                             original_lifetime(&lifetime_def),
 804                             shadower_lifetime(&lifetime));
 805                         return;
 806                     }
 807
 808                     old_scope = s;
 809                 }
 810             }
 811         }
 812     }
 813
 814     fn insert_lifetime(&mut self,
 815                        lifetime_ref: &hir::Lifetime,
 816                        def: DefRegion) {
 817         if lifetime_ref.id == ast::DUMMY_NODE_ID {
 818             span_bug!(lifetime_ref.span,
 819                       "lifetime reference not renumbered, \
 820                        probably a bug in syntax::fold");
 821         }
 822
 823         debug!("{} resolved to {:?} span={:?}",
 824                self.hir_map.node_to_string(lifetime_ref.id),
 825                def,
 826                self.sess.codemap().span_to_string(lifetime_ref.span));
 827         self.map.defs.insert(lifetime_ref.id, def);
 828     }
 829 }
 830
 831 fn search_lifetimes<'a>(lifetimes: &'a [hir::LifetimeDef],
 832                     lifetime_ref: &hir::Lifetime)
 833                     -> Option<(u32, &'a hir::Lifetime)> {
 834     for (i, lifetime_decl) in lifetimes.iter().enumerate() {
 835         if lifetime_decl.lifetime.name == lifetime_ref.name {
 836             return Some((i as u32, &lifetime_decl.lifetime));
 837         }
 838     }
 839     return None;
 840 }
 841
 842 ///////////////////////////////////////////////////////////////////////////
 843
 844 /// Detects late-bound lifetimes and inserts them into
 845 /// `map.late_bound`.
 846 ///
 847 /// A region declared on a fn is **late-bound** if:
 848 /// - it is constrained by an argument type;
 849 /// - it does not appear in a where-clause.
 850 ///
 851 /// "Constrained" basically means that it appears in any type but
 852 /// not amongst the inputs to a projection.  In other words, `<&'a
 853 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
 854 fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
 855                                fn_def_id: DefId,
 856                                decl: &hir::FnDecl,
 857                                generics: &hir::Generics) {
 858     debug!("insert_late_bound_lifetimes(decl={:?}, generics={:?})", decl, generics);
 859
 860     let mut constrained_by_input = ConstrainedCollector { regions: FxHashSet() };
 861     for arg_ty in &decl.inputs {
 862         constrained_by_input.visit_ty(arg_ty);
 863     }
 864
 865     let mut appears_in_output = AllCollector {
 866         regions: FxHashSet(),
 867         impl_trait: false
 868     };
 869     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
 870
 871     debug!("insert_late_bound_lifetimes: constrained_by_input={:?}",
 872            constrained_by_input.regions);
 873
 874     // Walk the lifetimes that appear in where clauses.
 875     //
 876     // Subtle point: because we disallow nested bindings, we can just
 877     // ignore binders here and scrape up all names we see.
 878     let mut appears_in_where_clause = AllCollector {
 879         regions: FxHashSet(),
 880         impl_trait: false
 881     };
 882     for ty_param in generics.ty_params.iter() {
 883         walk_list!(&mut appears_in_where_clause,
 884                    visit_ty_param_bound,
 885                    &ty_param.bounds);
 886     }
 887     walk_list!(&mut appears_in_where_clause,
 888                visit_where_predicate,
 889                &generics.where_clause.predicates);
 890     for lifetime_def in &generics.lifetimes {
 891         if !lifetime_def.bounds.is_empty() {
 892             // `'a: 'b` means both `'a` and `'b` are referenced
 893             appears_in_where_clause.visit_lifetime_def(lifetime_def);
 894         }
 895     }
 896
 897     debug!("insert_late_bound_lifetimes: appears_in_where_clause={:?}",
 898            appears_in_where_clause.regions);
 899
 900     // Late bound regions are those that:
 901     // - appear in the inputs
 902     // - do not appear in the where-clauses
 903     // - are not implicitly captured by `impl Trait`
 904     for lifetime in &generics.lifetimes {
 905         let name = lifetime.lifetime.name;
 906
 907         // appears in the where clauses? early-bound.
 908         if appears_in_where_clause.regions.contains(&name) { continue; }
 909
 910         // any `impl Trait` in the return type? early-bound.
 911         if appears_in_output.impl_trait { continue; }
 912
 913         // does not appear in the inputs, but appears in the return
 914         // type? eventually this will be early-bound, but for now we
 915         // just mark it so we can issue warnings.
 916         let constrained_by_input = constrained_by_input.regions.contains(&name);
 917         let appears_in_output = appears_in_output.regions.contains(&name);
 918         let will_change = !constrained_by_input && appears_in_output;
 919         let issue_32330 = if will_change {
 920             ty::Issue32330::WillChange {
 921                 fn_def_id: fn_def_id,
 922                 region_name: name,
 923             }
 924         } else {
 925             ty::Issue32330::WontChange
 926         };
 927
 928         debug!("insert_late_bound_lifetimes: \
 929                 lifetime {:?} with id {:?} is late-bound ({:?}",
 930                lifetime.lifetime.name, lifetime.lifetime.id, issue_32330);
 931
 932         let prev = map.late_bound.insert(lifetime.lifetime.id, issue_32330);
 933         assert!(prev.is_none(), "visited lifetime {:?} twice", lifetime.lifetime.id);
 934     }
 935
 936     return;
 937
 938     struct ConstrainedCollector {
 939         regions: FxHashSet<ast::Name>,
 940     }
 941
 942     impl<'v> Visitor<'v> for ConstrainedCollector {
 943         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
 944             NestedVisitorMap::None
 945         }
 946
 947         fn visit_ty(&mut self, ty: &'v hir::Ty) {
 948             match ty.node {
 949                 hir::TyPath(hir::QPath::Resolved(Some(_), _)) |
 950                 hir::TyPath(hir::QPath::TypeRelative(..)) => {
 951                     // ignore lifetimes appearing in associated type
 952                     // projections, as they are not *constrained*
 953                     // (defined above)
 954                 }
 955
 956                 hir::TyPath(hir::QPath::Resolved(None, ref path)) => {
 957                     // consider only the lifetimes on the final
 958                     // segment; I am not sure it's even currently
 959                     // valid to have them elsewhere, but even if it
 960                     // is, those would be potentially inputs to
 961                     // projections
 962                     if let Some(last_segment) = path.segments.last() {
 963                         self.visit_path_segment(path.span, last_segment);
 964                     }
 965                 }
 966
 967                 _ => {
 968                     intravisit::walk_ty(self, ty);
 969                 }
 970             }
 971         }
 972
 973         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
 974             self.regions.insert(lifetime_ref.name);
 975         }
 976     }
 977
 978     struct AllCollector {
 979         regions: FxHashSet<ast::Name>,
 980         impl_trait: bool
 981     }
 982
 983     impl<'v> Visitor<'v> for AllCollector {
 984         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
 985             NestedVisitorMap::None
 986         }
 987
 988         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
 989             self.regions.insert(lifetime_ref.name);
 990         }
 991
 992         fn visit_ty(&mut self, ty: &hir::Ty) {
 993             if let hir::TyImplTrait(_) = ty.node {
 994                 self.impl_trait = true;
 995             }
 996             intravisit::walk_ty(self, ty);
 997         }
 998     }
 999 }