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