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