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