src/librustc_resolve/lib.rs

   1 // Copyright 2012-2015 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 // Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364)
  12 #![cfg_attr(stage0, feature(custom_attribute))]
  13 #![crate_name = "rustc_resolve"]
  14 #![unstable(feature = "rustc_private")]
  15 #![staged_api]
  16 #![crate_type = "dylib"]
  17 #![crate_type = "rlib"]
  18 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  19       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  20       html_root_url = "http://doc.rust-lang.org/nightly/")]
  21
  22 #![feature(alloc)]
  23 #![feature(collections)]
  24 #![feature(rustc_diagnostic_macros)]
  25 #![feature(rustc_private)]
  26 #![feature(staged_api)]
  27
  28 #[macro_use] extern crate log;
  29 #[macro_use] extern crate syntax;
  30 #[macro_use] #[no_link] extern crate rustc_bitflags;
  31
  32 extern crate rustc;
  33
  34 use self::PatternBindingMode::*;
  35 use self::Namespace::*;
  36 use self::NamespaceResult::*;
  37 use self::NameDefinition::*;
  38 use self::ResolveResult::*;
  39 use self::FallbackSuggestion::*;
  40 use self::TypeParameters::*;
  41 use self::RibKind::*;
  42 use self::UseLexicalScopeFlag::*;
  43 use self::ModulePrefixResult::*;
  44 use self::NameSearchType::*;
  45 use self::BareIdentifierPatternResolution::*;
  46 use self::ParentLink::*;
  47 use self::ModuleKind::*;
  48 use self::FallbackChecks::*;
  49
  50 use rustc::session::Session;
  51 use rustc::lint;
  52 use rustc::metadata::csearch;
  53 use rustc::metadata::decoder::{DefLike, DlDef, DlField, DlImpl};
  54 use rustc::middle::def::*;
  55 use rustc::middle::lang_items::LanguageItems;
  56 use rustc::middle::pat_util::pat_bindings;
  57 use rustc::middle::privacy::*;
  58 use rustc::middle::subst::{ParamSpace, FnSpace, TypeSpace};
  59 use rustc::middle::ty::{Freevar, FreevarMap, TraitMap, GlobMap};
  60 use rustc::util::nodemap::{NodeMap, NodeSet, DefIdSet, FnvHashMap};
  61 use rustc::util::lev_distance::lev_distance;
  62
  63 use syntax::ast::{Arm, BindByRef, BindByValue, BindingMode, Block, Crate, CrateNum};
  64 use syntax::ast::{DefId, Expr, ExprAgain, ExprBreak, ExprField};
  65 use syntax::ast::{ExprLoop, ExprWhile, ExprMethodCall};
  66 use syntax::ast::{ExprPath, ExprStruct, FnDecl};
  67 use syntax::ast::{ForeignItemFn, ForeignItemStatic, Generics};
  68 use syntax::ast::{Ident, ImplItem, Item, ItemConst, ItemEnum, ItemExternCrate};
  69 use syntax::ast::{ItemFn, ItemForeignMod, ItemImpl, ItemMac, ItemMod, ItemStatic, ItemDefaultImpl};
  70 use syntax::ast::{ItemStruct, ItemTrait, ItemTy, ItemUse};
  71 use syntax::ast::{Local, MethodImplItem, Name, NodeId};
  72 use syntax::ast::{Pat, PatEnum, PatIdent, PatLit};
  73 use syntax::ast::{PatRange, PatStruct, Path, PrimTy};
  74 use syntax::ast::{TraitRef, Ty, TyBool, TyChar, TyF32};
  75 use syntax::ast::{TyF64, TyFloat, TyIs, TyI8, TyI16, TyI32, TyI64, TyInt};
  76 use syntax::ast::{TyPath, TyPtr};
  77 use syntax::ast::{TyRptr, TyStr, TyUs, TyU8, TyU16, TyU32, TyU64, TyUint};
  78 use syntax::ast::TypeImplItem;
  79 use syntax::ast;
  80 use syntax::ast_map;
  81 use syntax::ast_util::{local_def, walk_pat};
  82 use syntax::attr::AttrMetaMethods;
  83 use syntax::ext::mtwt;
  84 use syntax::parse::token::{self, special_names, special_idents};
  85 use syntax::ptr::P;
  86 use syntax::codemap::{self, Span, Pos};
  87 use syntax::visit::{self, Visitor};
  88
  89 use std::collections::{HashMap, HashSet};
  90 use std::collections::hash_map::Entry::{Occupied, Vacant};
  91 use std::cell::{Cell, RefCell};
  92 use std::fmt;
  93 use std::mem::replace;
  94 use std::rc::{Rc, Weak};
  95 use std::usize;
  96
  97 use resolve_imports::{Target, ImportDirective, ImportResolution};
  98 use resolve_imports::Shadowable;
  99
 100
 101 // NB: This module needs to be declared first so diagnostics are
 102 // registered before they are used.
 103 pub mod diagnostics;
 104
 105 mod check_unused;
 106 mod record_exports;
 107 mod build_reduced_graph;
 108 mod resolve_imports;
 109
 110 #[derive(Copy)]
 111 struct BindingInfo {
 112     span: Span,
 113     binding_mode: BindingMode,
 114 }
 115
 116 // Map from the name in a pattern to its binding mode.
 117 type BindingMap = HashMap<Name, BindingInfo>;
 118
 119 #[derive(Copy, PartialEq)]
 120 enum PatternBindingMode {
 121     RefutableMode,
 122     LocalIrrefutableMode,
 123     ArgumentIrrefutableMode,
 124 }
 125
 126 #[derive(Copy, PartialEq, Eq, Hash, Debug)]
 127 enum Namespace {
 128     TypeNS,
 129     ValueNS
 130 }
 131
 132 /// A NamespaceResult represents the result of resolving an import in
 133 /// a particular namespace. The result is either definitely-resolved,
 134 /// definitely- unresolved, or unknown.
 135 #[derive(Clone)]
 136 enum NamespaceResult {
 137     /// Means that resolve hasn't gathered enough information yet to determine
 138     /// whether the name is bound in this namespace. (That is, it hasn't
 139     /// resolved all `use` directives yet.)
 140     UnknownResult,
 141     /// Means that resolve has determined that the name is definitely
 142     /// not bound in the namespace.
 143     UnboundResult,
 144     /// Means that resolve has determined that the name is bound in the Module
 145     /// argument, and specified by the NameBindings argument.
 146     BoundResult(Rc<Module>, Rc<NameBindings>)
 147 }
 148
 149 impl NamespaceResult {
 150     fn is_unknown(&self) -> bool {
 151         match *self {
 152             UnknownResult => true,
 153             _ => false
 154         }
 155     }
 156     fn is_unbound(&self) -> bool {
 157         match *self {
 158             UnboundResult => true,
 159             _ => false
 160         }
 161     }
 162 }
 163
 164 enum NameDefinition {
 165     // The name was unbound.
 166     NoNameDefinition,
 167     // The name identifies an immediate child.
 168     ChildNameDefinition(Def, LastPrivate),
 169     // The name identifies an import.
 170     ImportNameDefinition(Def, LastPrivate),
 171 }
 172
 173 impl<'a, 'v, 'tcx> Visitor<'v> for Resolver<'a, 'tcx> {
 174     fn visit_item(&mut self, item: &Item) {
 175         self.resolve_item(item);
 176     }
 177     fn visit_arm(&mut self, arm: &Arm) {
 178         self.resolve_arm(arm);
 179     }
 180     fn visit_block(&mut self, block: &Block) {
 181         self.resolve_block(block);
 182     }
 183     fn visit_expr(&mut self, expr: &Expr) {
 184         self.resolve_expr(expr);
 185     }
 186     fn visit_local(&mut self, local: &Local) {
 187         self.resolve_local(local);
 188     }
 189     fn visit_ty(&mut self, ty: &Ty) {
 190         self.resolve_type(ty);
 191     }
 192     fn visit_generics(&mut self, generics: &Generics) {
 193         self.resolve_generics(generics);
 194     }
 195     fn visit_poly_trait_ref(&mut self,
 196                             tref: &ast::PolyTraitRef,
 197                             m: &ast::TraitBoundModifier) {
 198         match self.resolve_trait_reference(tref.trait_ref.ref_id, &tref.trait_ref.path, 0) {
 199             Ok(def) => self.record_def(tref.trait_ref.ref_id, def),
 200             Err(_) => { /* error already reported */ }
 201         }
 202         visit::walk_poly_trait_ref(self, tref, m);
 203     }
 204     fn visit_variant(&mut self, variant: &ast::Variant, generics: &Generics) {
 205         if let Some(ref dis_expr) = variant.node.disr_expr {
 206             // resolve the discriminator expr as a constant
 207             self.with_constant_rib(|this| {
 208                 this.visit_expr(&**dis_expr);
 209             });
 210         }
 211
 212         // `visit::walk_variant` without the discriminant expression.
 213         match variant.node.kind {
 214             ast::TupleVariantKind(ref variant_arguments) => {
 215                 for variant_argument in variant_arguments.iter() {
 216                     self.visit_ty(&*variant_argument.ty);
 217                 }
 218             }
 219             ast::StructVariantKind(ref struct_definition) => {
 220                 self.visit_struct_def(&**struct_definition,
 221                                       variant.node.name,
 222                                       generics,
 223                                       variant.node.id);
 224             }
 225         }
 226     }
 227     fn visit_foreign_item(&mut self, foreign_item: &ast::ForeignItem) {
 228         let type_parameters = match foreign_item.node {
 229             ForeignItemFn(_, ref generics) => {
 230                 HasTypeParameters(generics, FnSpace, ItemRibKind)
 231             }
 232             ForeignItemStatic(..) => NoTypeParameters
 233         };
 234         self.with_type_parameter_rib(type_parameters, |this| {
 235             visit::walk_foreign_item(this, foreign_item);
 236         });
 237     }
 238     fn visit_fn(&mut self,
 239                 function_kind: visit::FnKind<'v>,
 240                 declaration: &'v FnDecl,
 241                 block: &'v Block,
 242                 _: Span,
 243                 node_id: NodeId) {
 244         let rib_kind = match function_kind {
 245             visit::FkItemFn(_, generics, _, _) => {
 246                 self.visit_generics(generics);
 247                 ItemRibKind
 248             }
 249             visit::FkMethod(_, sig) => {
 250                 self.visit_generics(&sig.generics);
 251                 self.visit_explicit_self(&sig.explicit_self);
 252                 MethodRibKind
 253             }
 254             visit::FkFnBlock(..) => ClosureRibKind(node_id)
 255         };
 256         self.resolve_function(rib_kind, declaration, block);
 257     }
 258 }
 259
 260 type ErrorMessage = Option<(Span, String)>;
 261
 262 enum ResolveResult<T> {
 263     Failed(ErrorMessage),   // Failed to resolve the name, optional helpful error message.
 264     Indeterminate,          // Couldn't determine due to unresolved globs.
 265     Success(T)              // Successfully resolved the import.
 266 }
 267
 268 impl<T> ResolveResult<T> {
 269     fn indeterminate(&self) -> bool {
 270         match *self { Indeterminate => true, _ => false }
 271     }
 272 }
 273
 274 enum FallbackSuggestion {
 275     NoSuggestion,
 276     Field,
 277     Method,
 278     TraitItem,
 279     StaticMethod(String),
 280     TraitMethod(String),
 281 }
 282
 283 #[derive(Copy)]
 284 enum TypeParameters<'a> {
 285     NoTypeParameters,
 286     HasTypeParameters(
 287         // Type parameters.
 288         &'a Generics,
 289
 290         // Identifies the things that these parameters
 291         // were declared on (type, fn, etc)
 292         ParamSpace,
 293
 294         // The kind of the rib used for type parameters.
 295         RibKind)
 296 }
 297
 298 // The rib kind controls the translation of local
 299 // definitions (`DefLocal`) to upvars (`DefUpvar`).
 300 #[derive(Copy, Debug)]
 301 enum RibKind {
 302     // No translation needs to be applied.
 303     NormalRibKind,
 304
 305     // We passed through a closure scope at the given node ID.
 306     // Translate upvars as appropriate.
 307     ClosureRibKind(NodeId /* func id */),
 308
 309     // We passed through an impl or trait and are now in one of its
 310     // methods. Allow references to ty params that impl or trait
 311     // binds. Disallow any other upvars (including other ty params that are
 312     // upvars).
 313     MethodRibKind,
 314
 315     // We passed through an item scope. Disallow upvars.
 316     ItemRibKind,
 317
 318     // We're in a constant item. Can't refer to dynamic stuff.
 319     ConstantItemRibKind
 320 }
 321
 322 #[derive(Copy)]
 323 enum UseLexicalScopeFlag {
 324     DontUseLexicalScope,
 325     UseLexicalScope
 326 }
 327
 328 enum ModulePrefixResult {
 329     NoPrefixFound,
 330     PrefixFound(Rc<Module>, usize)
 331 }
 332
 333 #[derive(Copy, PartialEq)]
 334 enum NameSearchType {
 335     /// We're doing a name search in order to resolve a `use` directive.
 336     ImportSearch,
 337
 338     /// We're doing a name search in order to resolve a path type, a path
 339     /// expression, or a path pattern.
 340     PathSearch,
 341 }
 342
 343 #[derive(Copy)]
 344 enum BareIdentifierPatternResolution {
 345     FoundStructOrEnumVariant(Def, LastPrivate),
 346     FoundConst(Def, LastPrivate),
 347     BareIdentifierPatternUnresolved
 348 }
 349
 350 /// One local scope.
 351 #[derive(Debug)]
 352 struct Rib {
 353     bindings: HashMap<Name, DefLike>,
 354     kind: RibKind,
 355 }
 356
 357 impl Rib {
 358     fn new(kind: RibKind) -> Rib {
 359         Rib {
 360             bindings: HashMap::new(),
 361             kind: kind
 362         }
 363     }
 364 }
 365
 366 /// The link from a module up to its nearest parent node.
 367 #[derive(Clone,Debug)]
 368 enum ParentLink {
 369     NoParentLink,
 370     ModuleParentLink(Weak<Module>, Name),
 371     BlockParentLink(Weak<Module>, NodeId)
 372 }
 373
 374 /// The type of module this is.
 375 #[derive(Copy, PartialEq, Debug)]
 376 enum ModuleKind {
 377     NormalModuleKind,
 378     TraitModuleKind,
 379     EnumModuleKind,
 380     TypeModuleKind,
 381     AnonymousModuleKind,
 382 }
 383
 384 /// One node in the tree of modules.
 385 pub struct Module {
 386     parent_link: ParentLink,
 387     def_id: Cell<Option<DefId>>,
 388     kind: Cell<ModuleKind>,
 389     is_public: bool,
 390
 391     children: RefCell<HashMap<Name, Rc<NameBindings>>>,
 392     imports: RefCell<Vec<ImportDirective>>,
 393
 394     // The external module children of this node that were declared with
 395     // `extern crate`.
 396     external_module_children: RefCell<HashMap<Name, Rc<Module>>>,
 397
 398     // The anonymous children of this node. Anonymous children are pseudo-
 399     // modules that are implicitly created around items contained within
 400     // blocks.
 401     //
 402     // For example, if we have this:
 403     //
 404     //  fn f() {
 405     //      fn g() {
 406     //          ...
 407     //      }
 408     //  }
 409     //
 410     // There will be an anonymous module created around `g` with the ID of the
 411     // entry block for `f`.
 412     anonymous_children: RefCell<NodeMap<Rc<Module>>>,
 413
 414     // The status of resolving each import in this module.
 415     import_resolutions: RefCell<HashMap<Name, ImportResolution>>,
 416
 417     // The number of unresolved globs that this module exports.
 418     glob_count: Cell<usize>,
 419
 420     // The index of the import we're resolving.
 421     resolved_import_count: Cell<usize>,
 422
 423     // Whether this module is populated. If not populated, any attempt to
 424     // access the children must be preceded with a
 425     // `populate_module_if_necessary` call.
 426     populated: Cell<bool>,
 427 }
 428
 429 impl Module {
 430     fn new(parent_link: ParentLink,
 431            def_id: Option<DefId>,
 432            kind: ModuleKind,
 433            external: bool,
 434            is_public: bool)
 435            -> Module {
 436         Module {
 437             parent_link: parent_link,
 438             def_id: Cell::new(def_id),
 439             kind: Cell::new(kind),
 440             is_public: is_public,
 441             children: RefCell::new(HashMap::new()),
 442             imports: RefCell::new(Vec::new()),
 443             external_module_children: RefCell::new(HashMap::new()),
 444             anonymous_children: RefCell::new(NodeMap()),
 445             import_resolutions: RefCell::new(HashMap::new()),
 446             glob_count: Cell::new(0),
 447             resolved_import_count: Cell::new(0),
 448             populated: Cell::new(!external),
 449         }
 450     }
 451
 452     fn all_imports_resolved(&self) -> bool {
 453         self.imports.borrow().len() == self.resolved_import_count.get()
 454     }
 455 }
 456
 457 impl fmt::Debug for Module {
 458     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 459         write!(f, "{:?}, kind: {:?}, {}",
 460                self.def_id,
 461                self.kind,
 462                if self.is_public { "public" } else { "private" } )
 463     }
 464 }
 465
 466 bitflags! {
 467     #[derive(Debug)]
 468     flags DefModifiers: u8 {
 469         const PUBLIC            = 0b0000_0001,
 470         const IMPORTABLE        = 0b0000_0010,
 471     }
 472 }
 473
 474 // Records a possibly-private type definition.
 475 #[derive(Clone,Debug)]
 476 struct TypeNsDef {
 477     modifiers: DefModifiers, // see note in ImportResolution about how to use this
 478     module_def: Option<Rc<Module>>,
 479     type_def: Option<Def>,
 480     type_span: Option<Span>
 481 }
 482
 483 // Records a possibly-private value definition.
 484 #[derive(Clone, Copy, Debug)]
 485 struct ValueNsDef {
 486     modifiers: DefModifiers, // see note in ImportResolution about how to use this
 487     def: Def,
 488     value_span: Option<Span>,
 489 }
 490
 491 // Records the definitions (at most one for each namespace) that a name is
 492 // bound to.
 493 #[derive(Debug)]
 494 pub struct NameBindings {
 495     type_def: RefCell<Option<TypeNsDef>>,   //< Meaning in type namespace.
 496     value_def: RefCell<Option<ValueNsDef>>, //< Meaning in value namespace.
 497 }
 498
 499 impl NameBindings {
 500     fn new() -> NameBindings {
 501         NameBindings {
 502             type_def: RefCell::new(None),
 503             value_def: RefCell::new(None),
 504         }
 505     }
 506
 507     /// Creates a new module in this set of name bindings.
 508     fn define_module(&self,
 509                      parent_link: ParentLink,
 510                      def_id: Option<DefId>,
 511                      kind: ModuleKind,
 512                      external: bool,
 513                      is_public: bool,
 514                      sp: Span) {
 515         // Merges the module with the existing type def or creates a new one.
 516         let modifiers = if is_public { PUBLIC } else { DefModifiers::empty() } | IMPORTABLE;
 517         let module_ = Rc::new(Module::new(parent_link,
 518                                           def_id,
 519                                           kind,
 520                                           external,
 521                                           is_public));
 522         let type_def = self.type_def.borrow().clone();
 523         match type_def {
 524             None => {
 525                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 526                     modifiers: modifiers,
 527                     module_def: Some(module_),
 528                     type_def: None,
 529                     type_span: Some(sp)
 530                 });
 531             }
 532             Some(type_def) => {
 533                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 534                     modifiers: modifiers,
 535                     module_def: Some(module_),
 536                     type_span: Some(sp),
 537                     type_def: type_def.type_def
 538                 });
 539             }
 540         }
 541     }
 542
 543     /// Sets the kind of the module, creating a new one if necessary.
 544     fn set_module_kind(&self,
 545                        parent_link: ParentLink,
 546                        def_id: Option<DefId>,
 547                        kind: ModuleKind,
 548                        external: bool,
 549                        is_public: bool,
 550                        _sp: Span) {
 551         let modifiers = if is_public { PUBLIC } else { DefModifiers::empty() } | IMPORTABLE;
 552         let type_def = self.type_def.borrow().clone();
 553         match type_def {
 554             None => {
 555                 let module = Module::new(parent_link,
 556                                          def_id,
 557                                          kind,
 558                                          external,
 559                                          is_public);
 560                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 561                     modifiers: modifiers,
 562                     module_def: Some(Rc::new(module)),
 563                     type_def: None,
 564                     type_span: None,
 565                 });
 566             }
 567             Some(type_def) => {
 568                 match type_def.module_def {
 569                     None => {
 570                         let module = Module::new(parent_link,
 571                                                  def_id,
 572                                                  kind,
 573                                                  external,
 574                                                  is_public);
 575                         *self.type_def.borrow_mut() = Some(TypeNsDef {
 576                             modifiers: modifiers,
 577                             module_def: Some(Rc::new(module)),
 578                             type_def: type_def.type_def,
 579                             type_span: None,
 580                         });
 581                     }
 582                     Some(module_def) => module_def.kind.set(kind),
 583                 }
 584             }
 585         }
 586     }
 587
 588     /// Records a type definition.
 589     fn define_type(&self, def: Def, sp: Span, modifiers: DefModifiers) {
 590         debug!("defining type for def {:?} with modifiers {:?}", def, modifiers);
 591         // Merges the type with the existing type def or creates a new one.
 592         let type_def = self.type_def.borrow().clone();
 593         match type_def {
 594             None => {
 595                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 596                     module_def: None,
 597                     type_def: Some(def),
 598                     type_span: Some(sp),
 599                     modifiers: modifiers,
 600                 });
 601             }
 602             Some(type_def) => {
 603                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 604                     module_def: type_def.module_def,
 605                     type_def: Some(def),
 606                     type_span: Some(sp),
 607                     modifiers: modifiers,
 608                 });
 609             }
 610         }
 611     }
 612
 613     /// Records a value definition.
 614     fn define_value(&self, def: Def, sp: Span, modifiers: DefModifiers) {
 615         debug!("defining value for def {:?} with modifiers {:?}", def, modifiers);
 616         *self.value_def.borrow_mut() = Some(ValueNsDef {
 617             def: def,
 618             value_span: Some(sp),
 619             modifiers: modifiers,
 620         });
 621     }
 622
 623     /// Returns the module node if applicable.
 624     fn get_module_if_available(&self) -> Option<Rc<Module>> {
 625         match *self.type_def.borrow() {
 626             Some(ref type_def) => type_def.module_def.clone(),
 627             None => None
 628         }
 629     }
 630
 631     /// Returns the module node. Panics if this node does not have a module
 632     /// definition.
 633     fn get_module(&self) -> Rc<Module> {
 634         match self.get_module_if_available() {
 635             None => {
 636                 panic!("get_module called on a node with no module \
 637                        definition!")
 638             }
 639             Some(module_def) => module_def
 640         }
 641     }
 642
 643     fn defined_in_namespace(&self, namespace: Namespace) -> bool {
 644         match namespace {
 645             TypeNS   => return self.type_def.borrow().is_some(),
 646             ValueNS  => return self.value_def.borrow().is_some()
 647         }
 648     }
 649
 650     fn defined_in_public_namespace(&self, namespace: Namespace) -> bool {
 651         self.defined_in_namespace_with(namespace, PUBLIC)
 652     }
 653
 654     fn defined_in_namespace_with(&self, namespace: Namespace, modifiers: DefModifiers) -> bool {
 655         match namespace {
 656             TypeNS => match *self.type_def.borrow() {
 657                 Some(ref def) => def.modifiers.contains(modifiers), None => false
 658             },
 659             ValueNS => match *self.value_def.borrow() {
 660                 Some(ref def) => def.modifiers.contains(modifiers), None => false
 661             }
 662         }
 663     }
 664
 665     fn def_for_namespace(&self, namespace: Namespace) -> Option<Def> {
 666         match namespace {
 667             TypeNS => {
 668                 match *self.type_def.borrow() {
 669                     None => None,
 670                     Some(ref type_def) => {
 671                         match type_def.type_def {
 672                             Some(type_def) => Some(type_def),
 673                             None => {
 674                                 match type_def.module_def {
 675                                     Some(ref module) => {
 676                                         match module.def_id.get() {
 677                                             Some(did) => Some(DefMod(did)),
 678                                             None => None,
 679                                         }
 680                                     }
 681                                     None => None,
 682                                 }
 683                             }
 684                         }
 685                     }
 686                 }
 687             }
 688             ValueNS => {
 689                 match *self.value_def.borrow() {
 690                     None => None,
 691                     Some(value_def) => Some(value_def.def)
 692                 }
 693             }
 694         }
 695     }
 696
 697     fn span_for_namespace(&self, namespace: Namespace) -> Option<Span> {
 698         if self.defined_in_namespace(namespace) {
 699             match namespace {
 700                 TypeNS  => {
 701                     match *self.type_def.borrow() {
 702                         None => None,
 703                         Some(ref type_def) => type_def.type_span
 704                     }
 705                 }
 706                 ValueNS => {
 707                     match *self.value_def.borrow() {
 708                         None => None,
 709                         Some(ref value_def) => value_def.value_span
 710                     }
 711                 }
 712             }
 713         } else {
 714             None
 715         }
 716     }
 717
 718     fn is_public(&self, namespace: Namespace) -> bool {
 719         match namespace {
 720             TypeNS  => {
 721                 let type_def = self.type_def.borrow();
 722                 type_def.as_ref().unwrap().modifiers.contains(PUBLIC)
 723             }
 724             ValueNS => {
 725                 let value_def = self.value_def.borrow();
 726                 value_def.as_ref().unwrap().modifiers.contains(PUBLIC)
 727             }
 728         }
 729     }
 730 }
 731
 732 /// Interns the names of the primitive types.
 733 struct PrimitiveTypeTable {
 734     primitive_types: HashMap<Name, PrimTy>,
 735 }
 736
 737 impl PrimitiveTypeTable {
 738     fn new() -> PrimitiveTypeTable {
 739         let mut table = PrimitiveTypeTable {
 740             primitive_types: HashMap::new()
 741         };
 742
 743         table.intern("bool",    TyBool);
 744         table.intern("char",    TyChar);
 745         table.intern("f32",     TyFloat(TyF32));
 746         table.intern("f64",     TyFloat(TyF64));
 747         table.intern("isize",   TyInt(TyIs));
 748         table.intern("i8",      TyInt(TyI8));
 749         table.intern("i16",     TyInt(TyI16));
 750         table.intern("i32",     TyInt(TyI32));
 751         table.intern("i64",     TyInt(TyI64));
 752         table.intern("str",     TyStr);
 753         table.intern("usize",   TyUint(TyUs));
 754         table.intern("u8",      TyUint(TyU8));
 755         table.intern("u16",     TyUint(TyU16));
 756         table.intern("u32",     TyUint(TyU32));
 757         table.intern("u64",     TyUint(TyU64));
 758
 759         table
 760     }
 761
 762     fn intern(&mut self, string: &str, primitive_type: PrimTy) {
 763         self.primitive_types.insert(token::intern(string), primitive_type);
 764     }
 765 }
 766
 767 /// The main resolver class.
 768 pub struct Resolver<'a, 'tcx:'a> {
 769     session: &'a Session,
 770
 771     ast_map: &'a ast_map::Map<'tcx>,
 772
 773     graph_root: NameBindings,
 774
 775     trait_item_map: FnvHashMap<(Name, DefId), DefId>,
 776
 777     structs: FnvHashMap<DefId, Vec<Name>>,
 778
 779     // The number of imports that are currently unresolved.
 780     unresolved_imports: usize,
 781
 782     // The module that represents the current item scope.
 783     current_module: Rc<Module>,
 784
 785     // The current set of local scopes, for values.
 786     // FIXME #4948: Reuse ribs to avoid allocation.
 787     value_ribs: Vec<Rib>,
 788
 789     // The current set of local scopes, for types.
 790     type_ribs: Vec<Rib>,
 791
 792     // The current set of local scopes, for labels.
 793     label_ribs: Vec<Rib>,
 794
 795     // The trait that the current context can refer to.
 796     current_trait_ref: Option<(DefId, TraitRef)>,
 797
 798     // The current self type if inside an impl (used for better errors).
 799     current_self_type: Option<Ty>,
 800
 801     // The idents for the primitive types.
 802     primitive_type_table: PrimitiveTypeTable,
 803
 804     def_map: DefMap,
 805     freevars: RefCell<FreevarMap>,
 806     freevars_seen: RefCell<NodeMap<NodeSet>>,
 807     export_map: ExportMap,
 808     trait_map: TraitMap,
 809     external_exports: ExternalExports,
 810
 811     // Whether or not to print error messages. Can be set to true
 812     // when getting additional info for error message suggestions,
 813     // so as to avoid printing duplicate errors
 814     emit_errors: bool,
 815
 816     make_glob_map: bool,
 817     // Maps imports to the names of items actually imported (this actually maps
 818     // all imports, but only glob imports are actually interesting).
 819     glob_map: GlobMap,
 820
 821     used_imports: HashSet<(NodeId, Namespace)>,
 822     used_crates: HashSet<CrateNum>,
 823 }
 824
 825 #[derive(PartialEq)]
 826 enum FallbackChecks {
 827     Everything,
 828     OnlyTraitAndStatics
 829 }
 830
 831 impl<'a, 'tcx> Resolver<'a, 'tcx> {
 832     fn new(session: &'a Session,
 833            ast_map: &'a ast_map::Map<'tcx>,
 834            crate_span: Span,
 835            make_glob_map: MakeGlobMap) -> Resolver<'a, 'tcx> {
 836         let graph_root = NameBindings::new();
 837
 838         graph_root.define_module(NoParentLink,
 839                                  Some(DefId { krate: 0, node: 0 }),
 840                                  NormalModuleKind,
 841                                  false,
 842                                  true,
 843                                  crate_span);
 844
 845         let current_module = graph_root.get_module();
 846
 847         Resolver {
 848             session: session,
 849
 850             ast_map: ast_map,
 851
 852             // The outermost module has def ID 0; this is not reflected in the
 853             // AST.
 854
 855             graph_root: graph_root,
 856
 857             trait_item_map: FnvHashMap(),
 858             structs: FnvHashMap(),
 859
 860             unresolved_imports: 0,
 861
 862             current_module: current_module,
 863             value_ribs: Vec::new(),
 864             type_ribs: Vec::new(),
 865             label_ribs: Vec::new(),
 866
 867             current_trait_ref: None,
 868             current_self_type: None,
 869
 870             primitive_type_table: PrimitiveTypeTable::new(),
 871
 872             def_map: RefCell::new(NodeMap()),
 873             freevars: RefCell::new(NodeMap()),
 874             freevars_seen: RefCell::new(NodeMap()),
 875             export_map: NodeMap(),
 876             trait_map: NodeMap(),
 877             used_imports: HashSet::new(),
 878             used_crates: HashSet::new(),
 879             external_exports: DefIdSet(),
 880
 881             emit_errors: true,
 882             make_glob_map: make_glob_map == MakeGlobMap::Yes,
 883             glob_map: HashMap::new(),
 884         }
 885     }
 886
 887     #[inline]
 888     fn record_import_use(&mut self, import_id: NodeId, name: Name) {
 889         if !self.make_glob_map {
 890             return;
 891         }
 892         if self.glob_map.contains_key(&import_id) {
 893             self.glob_map.get_mut(&import_id).unwrap().insert(name);
 894             return;
 895         }
 896
 897         let mut new_set = HashSet::new();
 898         new_set.insert(name);
 899         self.glob_map.insert(import_id, new_set);
 900     }
 901
 902     fn get_trait_name(&self, did: DefId) -> Name {
 903         if did.krate == ast::LOCAL_CRATE {
 904             self.ast_map.expect_item(did.node).ident.name
 905         } else {
 906             csearch::get_trait_name(&self.session.cstore, did)
 907         }
 908     }
 909
 910     fn create_name_bindings_from_module(module: Rc<Module>) -> NameBindings {
 911         NameBindings {
 912             type_def: RefCell::new(Some(TypeNsDef {
 913                 modifiers: IMPORTABLE,
 914                 module_def: Some(module),
 915                 type_def: None,
 916                 type_span: None
 917             })),
 918             value_def: RefCell::new(None),
 919         }
 920     }
 921
 922     /// Checks that the names of external crates don't collide with other
 923     /// external crates.
 924     fn check_for_conflicts_between_external_crates(&self,
 925                                                    module: &Module,
 926                                                    name: Name,
 927                                                    span: Span) {
 928         if module.external_module_children.borrow().contains_key(&name) {
 929                 span_err!(self.session, span, E0259,
 930                           "an external crate named `{}` has already \
 931                                    been imported into this module",
 932                                   &token::get_name(name));
 933         }
 934     }
 935
 936     /// Checks that the names of items don't collide with external crates.
 937     fn check_for_conflicts_between_external_crates_and_items(&self,
 938                                                              module: &Module,
 939                                                              name: Name,
 940                                                              span: Span) {
 941         if module.external_module_children.borrow().contains_key(&name) {
 942                 span_err!(self.session, span, E0260,
 943                           "the name `{}` conflicts with an external \
 944                                    crate that has been imported into this \
 945                                    module",
 946                                   &token::get_name(name));
 947         }
 948     }
 949
 950     /// Resolves the given module path from the given root `module_`.
 951     fn resolve_module_path_from_root(&mut self,
 952                                      module_: Rc<Module>,
 953                                      module_path: &[Name],
 954                                      index: usize,
 955                                      span: Span,
 956                                      name_search_type: NameSearchType,
 957                                      lp: LastPrivate)
 958                                 -> ResolveResult<(Rc<Module>, LastPrivate)> {
 959         fn search_parent_externals(needle: Name, module: &Rc<Module>)
 960                                 -> Option<Rc<Module>> {
 961             match module.external_module_children.borrow().get(&needle) {
 962                 Some(_) => Some(module.clone()),
 963                 None => match module.parent_link {
 964                     ModuleParentLink(ref parent, _) => {
 965                         search_parent_externals(needle, &parent.upgrade().unwrap())
 966                     }
 967                    _ => None
 968                 }
 969             }
 970         }
 971
 972         let mut search_module = module_;
 973         let mut index = index;
 974         let module_path_len = module_path.len();
 975         let mut closest_private = lp;
 976
 977         // Resolve the module part of the path. This does not involve looking
 978         // upward though scope chains; we simply resolve names directly in
 979         // modules as we go.
 980         while index < module_path_len {
 981             let name = module_path[index];
 982             match self.resolve_name_in_module(search_module.clone(),
 983                                               name,
 984                                               TypeNS,
 985                                               name_search_type,
 986                                               false) {
 987                 Failed(None) => {
 988                     let segment_name = token::get_name(name);
 989                     let module_name = module_to_string(&*search_module);
 990                     let mut span = span;
 991                     let msg = if "???" == &module_name[..] {
 992                         span.hi = span.lo + Pos::from_usize(segment_name.len());
 993
 994                         match search_parent_externals(name,
 995                                                      &self.current_module) {
 996                             Some(module) => {
 997                                 let path_str = names_to_string(module_path);
 998                                 let target_mod_str = module_to_string(&*module);
 999                                 let current_mod_str =
1000                                     module_to_string(&*self.current_module);
1001
1002                                 let prefix = if target_mod_str == current_mod_str {
1003                                     "self::".to_string()
1004                                 } else {
1005                                     format!("{}::", target_mod_str)
1006                                 };
1007
1008                                 format!("Did you mean `{}{}`?", prefix, path_str)
1009                             },
1010                             None => format!("Maybe a missing `extern crate {}`?",
1011                                             segment_name),
1012                         }
1013                     } else {
1014                         format!("Could not find `{}` in `{}`",
1015                                 segment_name,
1016                                 module_name)
1017                     };
1018
1019                     return Failed(Some((span, msg)));
1020                 }
1021                 Failed(err) => return Failed(err),
1022                 Indeterminate => {
1023                     debug!("(resolving module path for import) module \
1024                             resolution is indeterminate: {}",
1025                             token::get_name(name));
1026                     return Indeterminate;
1027                 }
1028                 Success((target, used_proxy)) => {
1029                     // Check to see whether there are type bindings, and, if
1030                     // so, whether there is a module within.
1031                     match *target.bindings.type_def.borrow() {
1032                         Some(ref type_def) => {
1033                             match type_def.module_def {
1034                                 None => {
1035                                     let msg = format!("Not a module `{}`",
1036                                                         token::get_name(name));
1037
1038                                     return Failed(Some((span, msg)));
1039                                 }
1040                                 Some(ref module_def) => {
1041                                     search_module = module_def.clone();
1042
1043                                     // track extern crates for unused_extern_crate lint
1044                                     if let Some(did) = module_def.def_id.get() {
1045                                         self.used_crates.insert(did.krate);
1046                                     }
1047
1048                                     // Keep track of the closest
1049                                     // private module used when
1050                                     // resolving this import chain.
1051                                     if !used_proxy && !search_module.is_public {
1052                                         if let Some(did) = search_module.def_id.get() {
1053                                             closest_private = LastMod(DependsOn(did));
1054                                         }
1055                                     }
1056                                 }
1057                             }
1058                         }
1059                         None => {
1060                             // There are no type bindings at all.
1061                             let msg = format!("Not a module `{}`",
1062                                               token::get_name(name));
1063                             return Failed(Some((span, msg)));
1064                         }
1065                     }
1066                 }
1067             }
1068
1069             index += 1;
1070         }
1071
1072         return Success((search_module, closest_private));
1073     }
1074
1075     /// Attempts to resolve the module part of an import directive or path
1076     /// rooted at the given module.
1077     ///
1078     /// On success, returns the resolved module, and the closest *private*
1079     /// module found to the destination when resolving this path.
1080     fn resolve_module_path(&mut self,
1081                            module_: Rc<Module>,
1082                            module_path: &[Name],
1083                            use_lexical_scope: UseLexicalScopeFlag,
1084                            span: Span,
1085                            name_search_type: NameSearchType)
1086                            -> ResolveResult<(Rc<Module>, LastPrivate)> {
1087         let module_path_len = module_path.len();
1088         assert!(module_path_len > 0);
1089
1090         debug!("(resolving module path for import) processing `{}` rooted at `{}`",
1091                names_to_string(module_path),
1092                module_to_string(&*module_));
1093
1094         // Resolve the module prefix, if any.
1095         let module_prefix_result = self.resolve_module_prefix(module_.clone(),
1096                                                               module_path);
1097
1098         let search_module;
1099         let start_index;
1100         let last_private;
1101         match module_prefix_result {
1102             Failed(None) => {
1103                 let mpath = names_to_string(module_path);
1104                 let mpath = &mpath[..];
1105                 match mpath.rfind(':') {
1106                     Some(idx) => {
1107                         let msg = format!("Could not find `{}` in `{}`",
1108                                             // idx +- 1 to account for the
1109                                             // colons on either side
1110                                             &mpath[idx + 1..],
1111                                             &mpath[..idx - 1]);
1112                         return Failed(Some((span, msg)));
1113                     },
1114                     None => {
1115                         return Failed(None)
1116                     }
1117                 }
1118             }
1119             Failed(err) => return Failed(err),
1120             Indeterminate => {
1121                 debug!("(resolving module path for import) indeterminate; \
1122                         bailing");
1123                 return Indeterminate;
1124             }
1125             Success(NoPrefixFound) => {
1126                 // There was no prefix, so we're considering the first element
1127                 // of the path. How we handle this depends on whether we were
1128                 // instructed to use lexical scope or not.
1129                 match use_lexical_scope {
1130                     DontUseLexicalScope => {
1131                         // This is a crate-relative path. We will start the
1132                         // resolution process at index zero.
1133                         search_module = self.graph_root.get_module();
1134                         start_index = 0;
1135                         last_private = LastMod(AllPublic);
1136                     }
1137                     UseLexicalScope => {
1138                         // This is not a crate-relative path. We resolve the
1139                         // first component of the path in the current lexical
1140                         // scope and then proceed to resolve below that.
1141                         match self.resolve_module_in_lexical_scope(module_,
1142                                                                    module_path[0]) {
1143                             Failed(err) => return Failed(err),
1144                             Indeterminate => {
1145                                 debug!("(resolving module path for import) \
1146                                         indeterminate; bailing");
1147                                 return Indeterminate;
1148                             }
1149                             Success(containing_module) => {
1150                                 search_module = containing_module;
1151                                 start_index = 1;
1152                                 last_private = LastMod(AllPublic);
1153                             }
1154                         }
1155                     }
1156                 }
1157             }
1158             Success(PrefixFound(ref containing_module, index)) => {
1159                 search_module = containing_module.clone();
1160                 start_index = index;
1161                 last_private = LastMod(DependsOn(containing_module.def_id
1162                                                                   .get()
1163                                                                   .unwrap()));
1164             }
1165         }
1166
1167         self.resolve_module_path_from_root(search_module,
1168                                            module_path,
1169                                            start_index,
1170                                            span,
1171                                            name_search_type,
1172                                            last_private)
1173     }
1174
1175     /// Invariant: This must only be called during main resolution, not during
1176     /// import resolution.
1177     fn resolve_item_in_lexical_scope(&mut self,
1178                                      module_: Rc<Module>,
1179                                      name: Name,
1180                                      namespace: Namespace)
1181                                     -> ResolveResult<(Target, bool)> {
1182         debug!("(resolving item in lexical scope) resolving `{}` in \
1183                 namespace {:?} in `{}`",
1184                token::get_name(name),
1185                namespace,
1186                module_to_string(&*module_));
1187
1188         // The current module node is handled specially. First, check for
1189         // its immediate children.
1190         build_reduced_graph::populate_module_if_necessary(self, &module_);
1191
1192         match module_.children.borrow().get(&name) {
1193             Some(name_bindings)
1194                     if name_bindings.defined_in_namespace(namespace) => {
1195                 debug!("top name bindings succeeded");
1196                 return Success((Target::new(module_.clone(),
1197                                             name_bindings.clone(),
1198                                             Shadowable::Never),
1199                                false));
1200             }
1201             Some(_) | None => { /* Not found; continue. */ }
1202         }
1203
1204         // Now check for its import directives. We don't have to have resolved
1205         // all its imports in the usual way; this is because chains of
1206         // adjacent import statements are processed as though they mutated the
1207         // current scope.
1208         if let Some(import_resolution) = module_.import_resolutions.borrow().get(&name) {
1209             match (*import_resolution).target_for_namespace(namespace) {
1210                 None => {
1211                     // Not found; continue.
1212                     debug!("(resolving item in lexical scope) found \
1213                             import resolution, but not in namespace {:?}",
1214                            namespace);
1215                 }
1216                 Some(target) => {
1217                     debug!("(resolving item in lexical scope) using \
1218                             import resolution");
1219                     // track used imports and extern crates as well
1220                     let id = import_resolution.id(namespace);
1221                     self.used_imports.insert((id, namespace));
1222                     self.record_import_use(id, name);
1223                     if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
1224                          self.used_crates.insert(kid);
1225                     }
1226                     return Success((target, false));
1227                 }
1228             }
1229         }
1230
1231         // Search for external modules.
1232         if namespace == TypeNS {
1233             // FIXME (21114): In principle unclear `child` *has* to be lifted.
1234             let child = module_.external_module_children.borrow().get(&name).cloned();
1235             if let Some(module) = child {
1236                 let name_bindings =
1237                     Rc::new(Resolver::create_name_bindings_from_module(module));
1238                 debug!("lower name bindings succeeded");
1239                 return Success((Target::new(module_,
1240                                             name_bindings,
1241                                             Shadowable::Never),
1242                                 false));
1243             }
1244         }
1245
1246         // Finally, proceed up the scope chain looking for parent modules.
1247         let mut search_module = module_;
1248         loop {
1249             // Go to the next parent.
1250             match search_module.parent_link.clone() {
1251                 NoParentLink => {
1252                     // No more parents. This module was unresolved.
1253                     debug!("(resolving item in lexical scope) unresolved \
1254                             module");
1255                     return Failed(None);
1256                 }
1257                 ModuleParentLink(parent_module_node, _) => {
1258                     match search_module.kind.get() {
1259                         NormalModuleKind => {
1260                             // We stop the search here.
1261                             debug!("(resolving item in lexical \
1262                                     scope) unresolved module: not \
1263                                     searching through module \
1264                                     parents");
1265                             return Failed(None);
1266                         }
1267                         TraitModuleKind |
1268                         EnumModuleKind |
1269                         TypeModuleKind |
1270                         AnonymousModuleKind => {
1271                             search_module = parent_module_node.upgrade().unwrap();
1272                         }
1273                     }
1274                 }
1275                 BlockParentLink(ref parent_module_node, _) => {
1276                     search_module = parent_module_node.upgrade().unwrap();
1277                 }
1278             }
1279
1280             // Resolve the name in the parent module.
1281             match self.resolve_name_in_module(search_module.clone(),
1282                                               name,
1283                                               namespace,
1284                                               PathSearch,
1285                                               true) {
1286                 Failed(Some((span, msg))) =>
1287                     self.resolve_error(span, &format!("failed to resolve. {}",
1288                                                      msg)),
1289                 Failed(None) => (), // Continue up the search chain.
1290                 Indeterminate => {
1291                     // We couldn't see through the higher scope because of an
1292                     // unresolved import higher up. Bail.
1293
1294                     debug!("(resolving item in lexical scope) indeterminate \
1295                             higher scope; bailing");
1296                     return Indeterminate;
1297                 }
1298                 Success((target, used_reexport)) => {
1299                     // We found the module.
1300                     debug!("(resolving item in lexical scope) found name \
1301                             in module, done");
1302                     return Success((target, used_reexport));
1303                 }
1304             }
1305         }
1306     }
1307
1308     /// Resolves a module name in the current lexical scope.
1309     fn resolve_module_in_lexical_scope(&mut self,
1310                                        module_: Rc<Module>,
1311                                        name: Name)
1312                                 -> ResolveResult<Rc<Module>> {
1313         // If this module is an anonymous module, resolve the item in the
1314         // lexical scope. Otherwise, resolve the item from the crate root.
1315         let resolve_result = self.resolve_item_in_lexical_scope(module_, name, TypeNS);
1316         match resolve_result {
1317             Success((target, _)) => {
1318                 let bindings = &*target.bindings;
1319                 match *bindings.type_def.borrow() {
1320                     Some(ref type_def) => {
1321                         match type_def.module_def {
1322                             None => {
1323                                 debug!("!!! (resolving module in lexical \
1324                                         scope) module wasn't actually a \
1325                                         module!");
1326                                 return Failed(None);
1327                             }
1328                             Some(ref module_def) => {
1329                                 return Success(module_def.clone());
1330                             }
1331                         }
1332                     }
1333                     None => {
1334                         debug!("!!! (resolving module in lexical scope) module
1335                                 wasn't actually a module!");
1336                         return Failed(None);
1337                     }
1338                 }
1339             }
1340             Indeterminate => {
1341                 debug!("(resolving module in lexical scope) indeterminate; \
1342                         bailing");
1343                 return Indeterminate;
1344             }
1345             Failed(err) => {
1346                 debug!("(resolving module in lexical scope) failed to resolve");
1347                 return Failed(err);
1348             }
1349         }
1350     }
1351
1352     /// Returns the nearest normal module parent of the given module.
1353     fn get_nearest_normal_module_parent(&mut self, module_: Rc<Module>)
1354                                             -> Option<Rc<Module>> {
1355         let mut module_ = module_;
1356         loop {
1357             match module_.parent_link.clone() {
1358                 NoParentLink => return None,
1359                 ModuleParentLink(new_module, _) |
1360                 BlockParentLink(new_module, _) => {
1361                     let new_module = new_module.upgrade().unwrap();
1362                     match new_module.kind.get() {
1363                         NormalModuleKind => return Some(new_module),
1364                         TraitModuleKind |
1365                         EnumModuleKind |
1366                         TypeModuleKind |
1367                         AnonymousModuleKind => module_ = new_module,
1368                     }
1369                 }
1370             }
1371         }
1372     }
1373
1374     /// Returns the nearest normal module parent of the given module, or the
1375     /// module itself if it is a normal module.
1376     fn get_nearest_normal_module_parent_or_self(&mut self, module_: Rc<Module>)
1377                                                 -> Rc<Module> {
1378         match module_.kind.get() {
1379             NormalModuleKind => return module_,
1380             TraitModuleKind |
1381             EnumModuleKind |
1382             TypeModuleKind |
1383             AnonymousModuleKind => {
1384                 match self.get_nearest_normal_module_parent(module_.clone()) {
1385                     None => module_,
1386                     Some(new_module) => new_module
1387                 }
1388             }
1389         }
1390     }
1391
1392     /// Resolves a "module prefix". A module prefix is one or both of (a) `self::`;
1393     /// (b) some chain of `super::`.
1394     /// grammar: (SELF MOD_SEP ) ? (SUPER MOD_SEP) *
1395     fn resolve_module_prefix(&mut self,
1396                              module_: Rc<Module>,
1397                              module_path: &[Name])
1398                                  -> ResolveResult<ModulePrefixResult> {
1399         // Start at the current module if we see `self` or `super`, or at the
1400         // top of the crate otherwise.
1401         let mut containing_module;
1402         let mut i;
1403         let first_module_path_string = token::get_name(module_path[0]);
1404         if "self" == &first_module_path_string[..] {
1405             containing_module =
1406                 self.get_nearest_normal_module_parent_or_self(module_);
1407             i = 1;
1408         } else if "super" == &first_module_path_string[..] {
1409             containing_module =
1410                 self.get_nearest_normal_module_parent_or_self(module_);
1411             i = 0;  // We'll handle `super` below.
1412         } else {
1413             return Success(NoPrefixFound);
1414         }
1415
1416         // Now loop through all the `super`s we find.
1417         while i < module_path.len() {
1418             let string = token::get_name(module_path[i]);
1419             if "super" != &string[..] {
1420                 break
1421             }
1422             debug!("(resolving module prefix) resolving `super` at {}",
1423                    module_to_string(&*containing_module));
1424             match self.get_nearest_normal_module_parent(containing_module) {
1425                 None => return Failed(None),
1426                 Some(new_module) => {
1427                     containing_module = new_module;
1428                     i += 1;
1429                 }
1430             }
1431         }
1432
1433         debug!("(resolving module prefix) finished resolving prefix at {}",
1434                module_to_string(&*containing_module));
1435
1436         return Success(PrefixFound(containing_module, i));
1437     }
1438
1439     /// Attempts to resolve the supplied name in the given module for the
1440     /// given namespace. If successful, returns the target corresponding to
1441     /// the name.
1442     ///
1443     /// The boolean returned on success is an indicator of whether this lookup
1444     /// passed through a public re-export proxy.
1445     fn resolve_name_in_module(&mut self,
1446                               module_: Rc<Module>,
1447                               name: Name,
1448                               namespace: Namespace,
1449                               name_search_type: NameSearchType,
1450                               allow_private_imports: bool)
1451                               -> ResolveResult<(Target, bool)> {
1452         debug!("(resolving name in module) resolving `{}` in `{}`",
1453                &token::get_name(name),
1454                module_to_string(&*module_));
1455
1456         // First, check the direct children of the module.
1457         build_reduced_graph::populate_module_if_necessary(self, &module_);
1458
1459         match module_.children.borrow().get(&name) {
1460             Some(name_bindings)
1461                     if name_bindings.defined_in_namespace(namespace) => {
1462                 debug!("(resolving name in module) found node as child");
1463                 return Success((Target::new(module_.clone(),
1464                                             name_bindings.clone(),
1465                                             Shadowable::Never),
1466                                false));
1467             }
1468             Some(_) | None => {
1469                 // Continue.
1470             }
1471         }
1472
1473         // Next, check the module's imports if necessary.
1474
1475         // If this is a search of all imports, we should be done with glob
1476         // resolution at this point.
1477         if name_search_type == PathSearch {
1478             assert_eq!(module_.glob_count.get(), 0);
1479         }
1480
1481         // Check the list of resolved imports.
1482         match module_.import_resolutions.borrow().get(&name) {
1483             Some(import_resolution) if allow_private_imports ||
1484                                        import_resolution.is_public => {
1485
1486                 if import_resolution.is_public &&
1487                         import_resolution.outstanding_references != 0 {
1488                     debug!("(resolving name in module) import \
1489                            unresolved; bailing out");
1490                     return Indeterminate;
1491                 }
1492                 match import_resolution.target_for_namespace(namespace) {
1493                     None => {
1494                         debug!("(resolving name in module) name found, \
1495                                 but not in namespace {:?}",
1496                                namespace);
1497                     }
1498                     Some(target) => {
1499                         debug!("(resolving name in module) resolved to \
1500                                 import");
1501                         // track used imports and extern crates as well
1502                         let id = import_resolution.id(namespace);
1503                         self.used_imports.insert((id, namespace));
1504                         self.record_import_use(id, name);
1505                         if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
1506                             self.used_crates.insert(kid);
1507                         }
1508                         return Success((target, true));
1509                     }
1510                 }
1511             }
1512             Some(..) | None => {} // Continue.
1513         }
1514
1515         // Finally, search through external children.
1516         if namespace == TypeNS {
1517             // FIXME (21114): In principle unclear `child` *has* to be lifted.
1518             let child = module_.external_module_children.borrow().get(&name).cloned();
1519             if let Some(module) = child {
1520                 let name_bindings =
1521                     Rc::new(Resolver::create_name_bindings_from_module(module));
1522                 return Success((Target::new(module_,
1523                                             name_bindings,
1524                                             Shadowable::Never),
1525                                 false));
1526             }
1527         }
1528
1529         // We're out of luck.
1530         debug!("(resolving name in module) failed to resolve `{}`",
1531                &token::get_name(name));
1532         return Failed(None);
1533     }
1534
1535     fn report_unresolved_imports(&mut self, module_: Rc<Module>) {
1536         let index = module_.resolved_import_count.get();
1537         let imports = module_.imports.borrow();
1538         let import_count = imports.len();
1539         if index != import_count {
1540             let sn = self.session
1541                          .codemap()
1542                          .span_to_snippet((*imports)[index].span)
1543                          .unwrap();
1544             if sn.contains("::") {
1545                 self.resolve_error((*imports)[index].span,
1546                                    "unresolved import");
1547             } else {
1548                 let err = format!("unresolved import (maybe you meant `{}::*`?)",
1549                                   sn);
1550                 self.resolve_error((*imports)[index].span, &err[..]);
1551             }
1552         }
1553
1554         // Descend into children and anonymous children.
1555         build_reduced_graph::populate_module_if_necessary(self, &module_);
1556
1557         for (_, child_node) in &*module_.children.borrow() {
1558             match child_node.get_module_if_available() {
1559                 None => {
1560                     // Continue.
1561                 }
1562                 Some(child_module) => {
1563                     self.report_unresolved_imports(child_module);
1564                 }
1565             }
1566         }
1567
1568         for (_, module_) in &*module_.anonymous_children.borrow() {
1569             self.report_unresolved_imports(module_.clone());
1570         }
1571     }
1572
1573     // AST resolution
1574     //
1575     // We maintain a list of value ribs and type ribs.
1576     //
1577     // Simultaneously, we keep track of the current position in the module
1578     // graph in the `current_module` pointer. When we go to resolve a name in
1579     // the value or type namespaces, we first look through all the ribs and
1580     // then query the module graph. When we resolve a name in the module
1581     // namespace, we can skip all the ribs (since nested modules are not
1582     // allowed within blocks in Rust) and jump straight to the current module
1583     // graph node.
1584     //
1585     // Named implementations are handled separately. When we find a method
1586     // call, we consult the module node to find all of the implementations in
1587     // scope. This information is lazily cached in the module node. We then
1588     // generate a fake "implementation scope" containing all the
1589     // implementations thus found, for compatibility with old resolve pass.
1590
1591     fn with_scope<F>(&mut self, name: Option<Name>, f: F) where
1592         F: FnOnce(&mut Resolver),
1593     {
1594         let orig_module = self.current_module.clone();
1595
1596         // Move down in the graph.
1597         match name {
1598             None => {
1599                 // Nothing to do.
1600             }
1601             Some(name) => {
1602                 build_reduced_graph::populate_module_if_necessary(self, &orig_module);
1603
1604                 match orig_module.children.borrow().get(&name) {
1605                     None => {
1606                         debug!("!!! (with scope) didn't find `{}` in `{}`",
1607                                token::get_name(name),
1608                                module_to_string(&*orig_module));
1609                     }
1610                     Some(name_bindings) => {
1611                         match (*name_bindings).get_module_if_available() {
1612                             None => {
1613                                 debug!("!!! (with scope) didn't find module \
1614                                         for `{}` in `{}`",
1615                                        token::get_name(name),
1616                                        module_to_string(&*orig_module));
1617                             }
1618                             Some(module_) => {
1619                                 self.current_module = module_;
1620                             }
1621                         }
1622                     }
1623                 }
1624             }
1625         }
1626
1627         f(self);
1628
1629         self.current_module = orig_module;
1630     }
1631
1632     /// Wraps the given definition in the appropriate number of `DefUpvar`
1633     /// wrappers.
1634     fn upvarify(&self,
1635                 ribs: &[Rib],
1636                 def_like: DefLike,
1637                 span: Span)
1638                 -> Option<DefLike> {
1639         let mut def = match def_like {
1640             DlDef(def) => def,
1641             _ => return Some(def_like)
1642         };
1643         match def {
1644             DefUpvar(..) => {
1645                 self.session.span_bug(span,
1646                     &format!("unexpected {:?} in bindings", def))
1647             }
1648             DefLocal(node_id) => {
1649                 for rib in ribs {
1650                     match rib.kind {
1651                         NormalRibKind => {
1652                             // Nothing to do. Continue.
1653                         }
1654                         ClosureRibKind(function_id) => {
1655                             let prev_def = def;
1656                             def = DefUpvar(node_id, function_id);
1657
1658                             let mut seen = self.freevars_seen.borrow_mut();
1659                             let seen = match seen.entry(function_id) {
1660                                 Occupied(v) => v.into_mut(),
1661                                 Vacant(v) => v.insert(NodeSet()),
1662                             };
1663                             if seen.contains(&node_id) {
1664                                 continue;
1665                             }
1666                             match self.freevars.borrow_mut().entry(function_id) {
1667                                 Occupied(v) => v.into_mut(),
1668                                 Vacant(v) => v.insert(vec![]),
1669                             }.push(Freevar { def: prev_def, span: span });
1670                             seen.insert(node_id);
1671                         }
1672                         ItemRibKind | MethodRibKind => {
1673                             // This was an attempt to access an upvar inside a
1674                             // named function item. This is not allowed, so we
1675                             // report an error.
1676
1677                             self.resolve_error(span,
1678                                 "can't capture dynamic environment in a fn item; \
1679                                  use the || { ... } closure form instead");
1680                             return None;
1681                         }
1682                         ConstantItemRibKind => {
1683                             // Still doesn't deal with upvars
1684                             self.resolve_error(span,
1685                                                "attempt to use a non-constant \
1686                                                 value in a constant");
1687                             return None;
1688                         }
1689                     }
1690                 }
1691             }
1692             DefTyParam(..) | DefSelfTy(_) => {
1693                 for rib in ribs {
1694                     match rib.kind {
1695                         NormalRibKind | MethodRibKind | ClosureRibKind(..) => {
1696                             // Nothing to do. Continue.
1697                         }
1698                         ItemRibKind => {
1699                             // This was an attempt to use a type parameter outside
1700                             // its scope.
1701
1702                             self.resolve_error(span,
1703                                                "can't use type parameters from \
1704                                                 outer function; try using a local \
1705                                                 type parameter instead");
1706                             return None;
1707                         }
1708                         ConstantItemRibKind => {
1709                             // see #9186
1710                             self.resolve_error(span,
1711                                                "cannot use an outer type \
1712                                                 parameter in this context");
1713                             return None;
1714                         }
1715                     }
1716                 }
1717             }
1718             _ => {}
1719         }
1720         Some(DlDef(def))
1721     }
1722
1723     /// Searches the current set of local scopes and
1724     /// applies translations for closures.
1725     fn search_ribs(&self,
1726                    ribs: &[Rib],
1727                    name: Name,
1728                    span: Span)
1729                    -> Option<DefLike> {
1730         // FIXME #4950: Try caching?
1731
1732         for (i, rib) in ribs.iter().enumerate().rev() {
1733             if let Some(def_like) = rib.bindings.get(&name).cloned() {
1734                 return self.upvarify(&ribs[i + 1..], def_like, span);
1735             }
1736         }
1737
1738         None
1739     }
1740
1741     /// Searches the current set of local scopes for labels.
1742     /// Stops after meeting a closure.
1743     fn search_label(&self, name: Name) -> Option<DefLike> {
1744         for rib in self.label_ribs.iter().rev() {
1745             match rib.kind {
1746                 NormalRibKind => {
1747                     // Continue
1748                 }
1749                 _ => {
1750                     // Do not resolve labels across function boundary
1751                     return None
1752                 }
1753             }
1754             let result = rib.bindings.get(&name).cloned();
1755             if result.is_some() {
1756                 return result
1757             }
1758         }
1759         None
1760     }
1761
1762     fn resolve_crate(&mut self, krate: &ast::Crate) {
1763         debug!("(resolving crate) starting");
1764
1765         visit::walk_crate(self, krate);
1766     }
1767
1768     fn check_if_primitive_type_name(&self, name: Name, span: Span) {
1769         if let Some(_) = self.primitive_type_table.primitive_types.get(&name) {
1770             span_err!(self.session, span, E0317,
1771                 "user-defined types or type parameters cannot shadow the primitive types");
1772         }
1773     }
1774
1775     fn resolve_item(&mut self, item: &Item) {
1776         let name = item.ident.name;
1777
1778         debug!("(resolving item) resolving {}",
1779                token::get_name(name));
1780
1781         match item.node {
1782             ItemEnum(_, ref generics) |
1783             ItemTy(_, ref generics) |
1784             ItemStruct(_, ref generics) => {
1785                 self.check_if_primitive_type_name(name, item.span);
1786
1787                 self.with_type_parameter_rib(HasTypeParameters(generics,
1788                                                                TypeSpace,
1789                                                                ItemRibKind),
1790                                              |this| visit::walk_item(this, item));
1791             }
1792             ItemFn(_, _, _, ref generics, _) => {
1793                 self.with_type_parameter_rib(HasTypeParameters(generics,
1794                                                                FnSpace,
1795                                                                ItemRibKind),
1796                                              |this| visit::walk_item(this, item));
1797             }
1798
1799             ItemDefaultImpl(_, ref trait_ref) => {
1800                 self.with_optional_trait_ref(Some(trait_ref), |_| {});
1801             }
1802             ItemImpl(_, _,
1803                      ref generics,
1804                      ref implemented_traits,
1805                      ref self_type,
1806                      ref impl_items) => {
1807                 self.resolve_implementation(generics,
1808                                             implemented_traits,
1809                                             &**self_type,
1810                                             &impl_items[..]);
1811             }
1812
1813             ItemTrait(_, ref generics, ref bounds, ref trait_items) => {
1814                 self.check_if_primitive_type_name(name, item.span);
1815
1816                 // Create a new rib for the self type.
1817                 let mut self_type_rib = Rib::new(ItemRibKind);
1818
1819                 // plain insert (no renaming, types are not currently hygienic....)
1820                 let name = special_names::type_self;
1821                 self_type_rib.bindings.insert(name, DlDef(DefSelfTy(item.id)));
1822                 self.type_ribs.push(self_type_rib);
1823
1824                 // Create a new rib for the trait-wide type parameters.
1825                 self.with_type_parameter_rib(HasTypeParameters(generics,
1826                                                                TypeSpace,
1827                                                                NormalRibKind),
1828                                              |this| {
1829                     this.visit_generics(generics);
1830                     visit::walk_ty_param_bounds_helper(this, bounds);
1831
1832                     for trait_item in trait_items {
1833                         // Create a new rib for the trait_item-specific type
1834                         // parameters.
1835                         //
1836                         // FIXME #4951: Do we need a node ID here?
1837
1838                         let type_parameters = match trait_item.node {
1839                             ast::MethodTraitItem(ref sig, _) => {
1840                                 HasTypeParameters(&sig.generics,
1841                                                   FnSpace,
1842                                                   MethodRibKind)
1843                             }
1844                             ast::TypeTraitItem(..) => {
1845                                 this.check_if_primitive_type_name(trait_item.ident.name,
1846                                                                   trait_item.span);
1847                                 NoTypeParameters
1848                             }
1849                         };
1850                         this.with_type_parameter_rib(type_parameters, |this| {
1851                             visit::walk_trait_item(this, trait_item)
1852                         });
1853                     }
1854                 });
1855
1856                 self.type_ribs.pop();
1857             }
1858
1859             ItemMod(_) | ItemForeignMod(_) => {
1860                 self.with_scope(Some(name), |this| {
1861                     visit::walk_item(this, item);
1862                 });
1863             }
1864
1865             ItemConst(..) | ItemStatic(..) => {
1866                 self.with_constant_rib(|this| {
1867                     visit::walk_item(this, item);
1868                 });
1869             }
1870
1871             ItemUse(ref view_path) => {
1872                 // check for imports shadowing primitive types
1873                 if let ast::ViewPathSimple(ident, _) = view_path.node {
1874                     match self.def_map.borrow().get(&item.id).map(|d| d.full_def()) {
1875                         Some(DefTy(..)) | Some(DefStruct(..)) | Some(DefTrait(..)) | None => {
1876                             self.check_if_primitive_type_name(ident.name, item.span);
1877                         }
1878                         _ => {}
1879                     }
1880                 }
1881             }
1882
1883             ItemExternCrate(_) | ItemMac(..) => {
1884                 // do nothing, these are just around to be encoded
1885             }
1886         }
1887     }
1888
1889     fn with_type_parameter_rib<F>(&mut self, type_parameters: TypeParameters, f: F) where
1890         F: FnOnce(&mut Resolver),
1891     {
1892         match type_parameters {
1893             HasTypeParameters(generics, space, rib_kind) => {
1894                 let mut function_type_rib = Rib::new(rib_kind);
1895                 let mut seen_bindings = HashSet::new();
1896                 for (index, type_parameter) in generics.ty_params.iter().enumerate() {
1897                     let name = type_parameter.ident.name;
1898                     debug!("with_type_parameter_rib: {}", type_parameter.id);
1899
1900                     if seen_bindings.contains(&name) {
1901                         self.resolve_error(type_parameter.span,
1902                                            &format!("the name `{}` is already \
1903                                                      used for a type \
1904                                                      parameter in this type \
1905                                                      parameter list",
1906                                                     token::get_name(name)))
1907                     }
1908                     seen_bindings.insert(name);
1909
1910                     // plain insert (no renaming)
1911                     function_type_rib.bindings.insert(name,
1912                         DlDef(DefTyParam(space,
1913                                          index as u32,
1914                                          local_def(type_parameter.id),
1915                                          name)));
1916                 }
1917                 self.type_ribs.push(function_type_rib);
1918             }
1919
1920             NoTypeParameters => {
1921                 // Nothing to do.
1922             }
1923         }
1924
1925         f(self);
1926
1927         match type_parameters {
1928             HasTypeParameters(..) => { self.type_ribs.pop(); }
1929             NoTypeParameters => { }
1930         }
1931     }
1932
1933     fn with_label_rib<F>(&mut self, f: F) where
1934         F: FnOnce(&mut Resolver),
1935     {
1936         self.label_ribs.push(Rib::new(NormalRibKind));
1937         f(self);
1938         self.label_ribs.pop();
1939     }
1940
1941     fn with_constant_rib<F>(&mut self, f: F) where
1942         F: FnOnce(&mut Resolver),
1943     {
1944         self.value_ribs.push(Rib::new(ConstantItemRibKind));
1945         self.type_ribs.push(Rib::new(ConstantItemRibKind));
1946         f(self);
1947         self.type_ribs.pop();
1948         self.value_ribs.pop();
1949     }
1950
1951     fn resolve_function(&mut self,
1952                         rib_kind: RibKind,
1953                         declaration: &FnDecl,
1954                         block: &Block) {
1955         // Create a value rib for the function.
1956         self.value_ribs.push(Rib::new(rib_kind));
1957
1958         // Create a label rib for the function.
1959         self.label_ribs.push(Rib::new(rib_kind));
1960
1961         // Add each argument to the rib.
1962         let mut bindings_list = HashMap::new();
1963         for argument in &declaration.inputs {
1964             self.resolve_pattern(&*argument.pat,
1965                                  ArgumentIrrefutableMode,
1966                                  &mut bindings_list);
1967
1968             self.visit_ty(&*argument.ty);
1969
1970             debug!("(resolving function) recorded argument");
1971         }
1972         visit::walk_fn_ret_ty(self, &declaration.output);
1973
1974         // Resolve the function body.
1975         self.visit_block(&*block);
1976
1977         debug!("(resolving function) leaving function");
1978
1979         self.label_ribs.pop();
1980         self.value_ribs.pop();
1981     }
1982
1983     fn resolve_trait_reference(&mut self,
1984                                id: NodeId,
1985                                trait_path: &Path,
1986                                path_depth: usize)
1987                                -> Result<PathResolution, ()> {
1988         if let Some(path_res) = self.resolve_path(id, trait_path, path_depth, TypeNS, true) {
1989             if let DefTrait(_) = path_res.base_def {
1990                 debug!("(resolving trait) found trait def: {:?}", path_res);
1991                 Ok(path_res)
1992             } else {
1993                 self.resolve_error(trait_path.span,
1994                     &format!("`{}` is not a trait",
1995                              path_names_to_string(trait_path, path_depth)));
1996
1997                 // If it's a typedef, give a note
1998                 if let DefTy(..) = path_res.base_def {
1999                     self.session.span_note(trait_path.span,
2000                                            "`type` aliases cannot be used for traits");
2001                 }
2002                 Err(())
2003             }
2004         } else {
2005             let msg = format!("use of undeclared trait name `{}`",
2006                               path_names_to_string(trait_path, path_depth));
2007             self.resolve_error(trait_path.span, &msg);
2008             Err(())
2009         }
2010     }
2011
2012     fn resolve_generics(&mut self, generics: &Generics) {
2013         for type_parameter in &*generics.ty_params {
2014             self.check_if_primitive_type_name(type_parameter.ident.name, type_parameter.span);
2015         }
2016         for predicate in &generics.where_clause.predicates {
2017             match predicate {
2018                 &ast::WherePredicate::BoundPredicate(_) |
2019                 &ast::WherePredicate::RegionPredicate(_) => {}
2020                 &ast::WherePredicate::EqPredicate(ref eq_pred) => {
2021                     let path_res = self.resolve_path(eq_pred.id, &eq_pred.path, 0, TypeNS, true);
2022                     if let Some(PathResolution { base_def: DefTyParam(..), .. }) = path_res {
2023                         self.record_def(eq_pred.id, path_res.unwrap());
2024                     } else {
2025                         self.resolve_error(eq_pred.path.span, "undeclared associated type");
2026                     }
2027                 }
2028             }
2029         }
2030         visit::walk_generics(self, generics);
2031     }
2032
2033     fn with_current_self_type<T, F>(&mut self, self_type: &Ty, f: F) -> T where
2034         F: FnOnce(&mut Resolver) -> T,
2035     {
2036         // Handle nested impls (inside fn bodies)
2037         let previous_value = replace(&mut self.current_self_type, Some(self_type.clone()));
2038         let result = f(self);
2039         self.current_self_type = previous_value;
2040         result
2041     }
2042
2043     fn with_optional_trait_ref<T, F>(&mut self,
2044                                      opt_trait_ref: Option<&TraitRef>,
2045                                      f: F)
2046                                      -> T
2047         where F: FnOnce(&mut Resolver) -> T,
2048     {
2049         let mut new_val = None;
2050         if let Some(trait_ref) = opt_trait_ref {
2051             match self.resolve_trait_reference(trait_ref.ref_id, &trait_ref.path, 0) {
2052                 Ok(path_res) => {
2053                     self.record_def(trait_ref.ref_id, path_res);
2054                     new_val = Some((path_res.base_def.def_id(), trait_ref.clone()));
2055                 }
2056                 Err(_) => { /* error was already reported */ }
2057             }
2058             visit::walk_trait_ref(self, trait_ref);
2059         }
2060         let original_trait_ref = replace(&mut self.current_trait_ref, new_val);
2061         let result = f(self);
2062         self.current_trait_ref = original_trait_ref;
2063         result
2064     }
2065
2066     fn resolve_implementation(&mut self,
2067                               generics: &Generics,
2068                               opt_trait_reference: &Option<TraitRef>,
2069                               self_type: &Ty,
2070                               impl_items: &[P<ImplItem>]) {
2071         // If applicable, create a rib for the type parameters.
2072         self.with_type_parameter_rib(HasTypeParameters(generics,
2073                                                        TypeSpace,
2074                                                        ItemRibKind),
2075                                      |this| {
2076             // Resolve the type parameters.
2077             this.visit_generics(generics);
2078
2079             // Resolve the trait reference, if necessary.
2080             this.with_optional_trait_ref(opt_trait_reference.as_ref(), |this| {
2081                 // Resolve the self type.
2082                 this.visit_ty(self_type);
2083
2084                 this.with_current_self_type(self_type, |this| {
2085                     for impl_item in impl_items {
2086                         match impl_item.node {
2087                             MethodImplItem(ref sig, _) => {
2088                                 // If this is a trait impl, ensure the method
2089                                 // exists in trait
2090                                 this.check_trait_item(impl_item.ident.name,
2091                                                       impl_item.span);
2092
2093                                 // We also need a new scope for the method-
2094                                 // specific type parameters.
2095                                 let type_parameters =
2096                                     HasTypeParameters(&sig.generics,
2097                                                       FnSpace,
2098                                                       MethodRibKind);
2099                                 this.with_type_parameter_rib(type_parameters, |this| {
2100                                     visit::walk_impl_item(this, impl_item);
2101                                 });
2102                             }
2103                             TypeImplItem(ref ty) => {
2104                                 // If this is a trait impl, ensure the method
2105                                 // exists in trait
2106                                 this.check_trait_item(impl_item.ident.name,
2107                                                       impl_item.span);
2108
2109                                 this.visit_ty(ty);
2110                             }
2111                             ast::MacImplItem(_) => {}
2112                         }
2113                     }
2114                 });
2115             });
2116         });
2117     }
2118
2119     fn check_trait_item(&self, name: Name, span: Span) {
2120         // If there is a TraitRef in scope for an impl, then the method must be in the trait.
2121         if let Some((did, ref trait_ref)) = self.current_trait_ref {
2122             if !self.trait_item_map.contains_key(&(name, did)) {
2123                 let path_str = path_names_to_string(&trait_ref.path, 0);
2124                 self.resolve_error(span,
2125                                     &format!("method `{}` is not a member of trait `{}`",
2126                                             token::get_name(name),
2127                                             path_str));
2128             }
2129         }
2130     }
2131
2132     fn resolve_local(&mut self, local: &Local) {
2133         // Resolve the type.
2134         visit::walk_ty_opt(self, &local.ty);
2135
2136         // Resolve the initializer.
2137         visit::walk_expr_opt(self, &local.init);
2138
2139         // Resolve the pattern.
2140         self.resolve_pattern(&*local.pat,
2141                              LocalIrrefutableMode,
2142                              &mut HashMap::new());
2143     }
2144
2145     // build a map from pattern identifiers to binding-info's.
2146     // this is done hygienically. This could arise for a macro
2147     // that expands into an or-pattern where one 'x' was from the
2148     // user and one 'x' came from the macro.
2149     fn binding_mode_map(&mut self, pat: &Pat) -> BindingMap {
2150         let mut result = HashMap::new();
2151         pat_bindings(&self.def_map, pat, |binding_mode, _id, sp, path1| {
2152             let name = mtwt::resolve(path1.node);
2153             result.insert(name, BindingInfo {
2154                 span: sp,
2155                 binding_mode: binding_mode
2156             });
2157         });
2158         return result;
2159     }
2160
2161     // check that all of the arms in an or-pattern have exactly the
2162     // same set of bindings, with the same binding modes for each.
2163     fn check_consistent_bindings(&mut self, arm: &Arm) {
2164         if arm.pats.len() == 0 {
2165             return
2166         }
2167         let map_0 = self.binding_mode_map(&*arm.pats[0]);
2168         for (i, p) in arm.pats.iter().enumerate() {
2169             let map_i = self.binding_mode_map(&**p);
2170
2171             for (&key, &binding_0) in &map_0 {
2172                 match map_i.get(&key) {
2173                   None => {
2174                     self.resolve_error(
2175                         p.span,
2176                         &format!("variable `{}` from pattern #1 is \
2177                                   not bound in pattern #{}",
2178                                 token::get_name(key),
2179                                 i + 1));
2180                   }
2181                   Some(binding_i) => {
2182                     if binding_0.binding_mode != binding_i.binding_mode {
2183                         self.resolve_error(
2184                             binding_i.span,
2185                             &format!("variable `{}` is bound with different \
2186                                       mode in pattern #{} than in pattern #1",
2187                                     token::get_name(key),
2188                                     i + 1));
2189                     }
2190                   }
2191                 }
2192             }
2193
2194             for (&key, &binding) in &map_i {
2195                 if !map_0.contains_key(&key) {
2196                     self.resolve_error(
2197                         binding.span,
2198                         &format!("variable `{}` from pattern {}{} is \
2199                                   not bound in pattern {}1",
2200                                 token::get_name(key),
2201                                 "#", i + 1, "#"));
2202                 }
2203             }
2204         }
2205     }
2206
2207     fn resolve_arm(&mut self, arm: &Arm) {
2208         self.value_ribs.push(Rib::new(NormalRibKind));
2209
2210         let mut bindings_list = HashMap::new();
2211         for pattern in &arm.pats {
2212             self.resolve_pattern(&**pattern, RefutableMode, &mut bindings_list);
2213         }
2214
2215         // This has to happen *after* we determine which
2216         // pat_idents are variants
2217         self.check_consistent_bindings(arm);
2218
2219         visit::walk_expr_opt(self, &arm.guard);
2220         self.visit_expr(&*arm.body);
2221
2222         self.value_ribs.pop();
2223     }
2224
2225     fn resolve_block(&mut self, block: &Block) {
2226         debug!("(resolving block) entering block");
2227         self.value_ribs.push(Rib::new(NormalRibKind));
2228
2229         // Move down in the graph, if there's an anonymous module rooted here.
2230         let orig_module = self.current_module.clone();
2231         match orig_module.anonymous_children.borrow().get(&block.id) {
2232             None => { /* Nothing to do. */ }
2233             Some(anonymous_module) => {
2234                 debug!("(resolving block) found anonymous module, moving \
2235                         down");
2236                 self.current_module = anonymous_module.clone();
2237             }
2238         }
2239
2240         // Check for imports appearing after non-item statements.
2241         let mut found_non_item = false;
2242         for statement in &block.stmts {
2243             if let ast::StmtDecl(ref declaration, _) = statement.node {
2244                 if let ast::DeclItem(ref i) = declaration.node {
2245                     match i.node {
2246                         ItemExternCrate(_) | ItemUse(_) if found_non_item => {
2247                             span_err!(self.session, i.span, E0154,
2248                                 "imports are not allowed after non-item statements");
2249                         }
2250                         _ => {}
2251                     }
2252                 } else {
2253                     found_non_item = true
2254                 }
2255             } else {
2256                 found_non_item = true;
2257             }
2258         }
2259
2260         // Descend into the block.
2261         visit::walk_block(self, block);
2262
2263         // Move back up.
2264         self.current_module = orig_module;
2265
2266         self.value_ribs.pop();
2267         debug!("(resolving block) leaving block");
2268     }
2269
2270     fn resolve_type(&mut self, ty: &Ty) {
2271         match ty.node {
2272             // `<T>::a::b::c` is resolved by typeck alone.
2273             TyPath(Some(ast::QSelf { position: 0, .. }), _) => {}
2274
2275             TyPath(ref maybe_qself, ref path) => {
2276                 let max_assoc_types = if let Some(ref qself) = *maybe_qself {
2277                     // Make sure the trait is valid.
2278                     let _ = self.resolve_trait_reference(ty.id, path, 1);
2279                     path.segments.len() - qself.position
2280                 } else {
2281                     path.segments.len()
2282                 };
2283
2284                 let mut resolution = None;
2285                 for depth in 0..max_assoc_types {
2286                     self.with_no_errors(|this| {
2287                         resolution = this.resolve_path(ty.id, path, depth, TypeNS, true);
2288                     });
2289                     if resolution.is_some() {
2290                         break;
2291                     }
2292                 }
2293                 if let Some(DefMod(_)) = resolution.map(|r| r.base_def) {
2294                     // A module is not a valid type.
2295                     resolution = None;
2296                 }
2297
2298                 // This is a path in the type namespace. Walk through scopes
2299                 // looking for it.
2300                 match resolution {
2301                     Some(def) => {
2302                         // Write the result into the def map.
2303                         debug!("(resolving type) writing resolution for `{}` \
2304                                 (id {}) = {:?}",
2305                                path_names_to_string(path, 0),
2306                                ty.id, def);
2307                         self.record_def(ty.id, def);
2308                     }
2309                     None => {
2310                         // Keep reporting some errors even if they're ignored above.
2311                         self.resolve_path(ty.id, path, 0, TypeNS, true);
2312
2313                         let kind = if maybe_qself.is_some() {
2314                             "associated type"
2315                         } else {
2316                             "type name"
2317                         };
2318
2319                         let msg = format!("use of undeclared {} `{}`", kind,
2320                                           path_names_to_string(path, 0));
2321                         self.resolve_error(ty.span, &msg[..]);
2322                     }
2323                 }
2324             }
2325             _ => {}
2326         }
2327         // Resolve embedded types.
2328         visit::walk_ty(self, ty);
2329     }
2330
2331     fn resolve_pattern(&mut self,
2332                        pattern: &Pat,
2333                        mode: PatternBindingMode,
2334                        // Maps idents to the node ID for the (outermost)
2335                        // pattern that binds them
2336                        bindings_list: &mut HashMap<Name, NodeId>) {
2337         let pat_id = pattern.id;
2338         walk_pat(pattern, |pattern| {
2339             match pattern.node {
2340                 PatIdent(binding_mode, ref path1, _) => {
2341
2342                     // The meaning of pat_ident with no type parameters
2343                     // depends on whether an enum variant or unit-like struct
2344                     // with that name is in scope. The probing lookup has to
2345                     // be careful not to emit spurious errors. Only matching
2346                     // patterns (match) can match nullary variants or
2347                     // unit-like structs. For binding patterns (let), matching
2348                     // such a value is simply disallowed (since it's rarely
2349                     // what you want).
2350
2351                     let ident = path1.node;
2352                     let renamed = mtwt::resolve(ident);
2353
2354                     match self.resolve_bare_identifier_pattern(ident.name, pattern.span) {
2355                         FoundStructOrEnumVariant(def, lp)
2356                                 if mode == RefutableMode => {
2357                             debug!("(resolving pattern) resolving `{}` to \
2358                                     struct or enum variant",
2359                                    token::get_name(renamed));
2360
2361                             self.enforce_default_binding_mode(
2362                                 pattern,
2363                                 binding_mode,
2364                                 "an enum variant");
2365                             self.record_def(pattern.id, PathResolution {
2366                                 base_def: def,
2367                                 last_private: lp,
2368                                 depth: 0
2369                             });
2370                         }
2371                         FoundStructOrEnumVariant(..) => {
2372                             self.resolve_error(
2373                                 pattern.span,
2374                                 &format!("declaration of `{}` shadows an enum \
2375                                          variant or unit-like struct in \
2376                                          scope",
2377                                         token::get_name(renamed)));
2378                         }
2379                         FoundConst(def, lp) if mode == RefutableMode => {
2380                             debug!("(resolving pattern) resolving `{}` to \
2381                                     constant",
2382                                    token::get_name(renamed));
2383
2384                             self.enforce_default_binding_mode(
2385                                 pattern,
2386                                 binding_mode,
2387                                 "a constant");
2388                             self.record_def(pattern.id, PathResolution {
2389                                 base_def: def,
2390                                 last_private: lp,
2391                                 depth: 0
2392                             });
2393                         }
2394                         FoundConst(..) => {
2395                             self.resolve_error(pattern.span,
2396                                                   "only irrefutable patterns \
2397                                                    allowed here");
2398                         }
2399                         BareIdentifierPatternUnresolved => {
2400                             debug!("(resolving pattern) binding `{}`",
2401                                    token::get_name(renamed));
2402
2403                             let def = DefLocal(pattern.id);
2404
2405                             // Record the definition so that later passes
2406                             // will be able to distinguish variants from
2407                             // locals in patterns.
2408
2409                             self.record_def(pattern.id, PathResolution {
2410                                 base_def: def,
2411                                 last_private: LastMod(AllPublic),
2412                                 depth: 0
2413                             });
2414
2415                             // Add the binding to the local ribs, if it
2416                             // doesn't already exist in the bindings list. (We
2417                             // must not add it if it's in the bindings list
2418                             // because that breaks the assumptions later
2419                             // passes make about or-patterns.)
2420                             if !bindings_list.contains_key(&renamed) {
2421                                 let this = &mut *self;
2422                                 let last_rib = this.value_ribs.last_mut().unwrap();
2423                                 last_rib.bindings.insert(renamed, DlDef(def));
2424                                 bindings_list.insert(renamed, pat_id);
2425                             } else if mode == ArgumentIrrefutableMode &&
2426                                     bindings_list.contains_key(&renamed) {
2427                                 // Forbid duplicate bindings in the same
2428                                 // parameter list.
2429                                 self.resolve_error(pattern.span,
2430                                                    &format!("identifier `{}` \
2431                                                             is bound more \
2432                                                             than once in \
2433                                                             this parameter \
2434                                                             list",
2435                                                            token::get_ident(
2436                                                                ident))
2437                                                    )
2438                             } else if bindings_list.get(&renamed) ==
2439                                     Some(&pat_id) {
2440                                 // Then this is a duplicate variable in the
2441                                 // same disjunction, which is an error.
2442                                 self.resolve_error(pattern.span,
2443                                     &format!("identifier `{}` is bound \
2444                                              more than once in the same \
2445                                              pattern",
2446                                             token::get_ident(ident)));
2447                             }
2448                             // Else, not bound in the same pattern: do
2449                             // nothing.
2450                         }
2451                     }
2452                 }
2453
2454                 PatEnum(ref path, _) => {
2455                     // This must be an enum variant, struct or const.
2456                     if let Some(path_res) = self.resolve_path(pat_id, path, 0, ValueNS, false) {
2457                         match path_res.base_def {
2458                             DefVariant(..) | DefStruct(..) | DefConst(..) => {
2459                                 self.record_def(pattern.id, path_res);
2460                             }
2461                             DefStatic(..) => {
2462                                 self.resolve_error(path.span,
2463                                                    "static variables cannot be \
2464                                                     referenced in a pattern, \
2465                                                     use a `const` instead");
2466                             }
2467                             _ => {
2468                                 self.resolve_error(path.span,
2469                                     &format!("`{}` is not an enum variant, struct or const",
2470                                         token::get_ident(
2471                                             path.segments.last().unwrap().identifier)));
2472                             }
2473                         }
2474                     } else {
2475                         self.resolve_error(path.span,
2476                             &format!("unresolved enum variant, struct or const `{}`",
2477                                 token::get_ident(path.segments.last().unwrap().identifier)));
2478                     }
2479                     visit::walk_path(self, path);
2480                 }
2481
2482                 PatStruct(ref path, _, _) => {
2483                     match self.resolve_path(pat_id, path, 0, TypeNS, false) {
2484                         Some(definition) => {
2485                             self.record_def(pattern.id, definition);
2486                         }
2487                         result => {
2488                             debug!("(resolving pattern) didn't find struct \
2489                                     def: {:?}", result);
2490                             let msg = format!("`{}` does not name a structure",
2491                                               path_names_to_string(path, 0));
2492                             self.resolve_error(path.span, &msg[..]);
2493                         }
2494                     }
2495                     visit::walk_path(self, path);
2496                 }
2497
2498                 PatLit(_) | PatRange(..) => {
2499                     visit::walk_pat(self, pattern);
2500                 }
2501
2502                 _ => {
2503                     // Nothing to do.
2504                 }
2505             }
2506             true
2507         });
2508     }
2509
2510     fn resolve_bare_identifier_pattern(&mut self, name: Name, span: Span)
2511                                        -> BareIdentifierPatternResolution {
2512         let module = self.current_module.clone();
2513         match self.resolve_item_in_lexical_scope(module,
2514                                                  name,
2515                                                  ValueNS) {
2516             Success((target, _)) => {
2517                 debug!("(resolve bare identifier pattern) succeeded in \
2518                          finding {} at {:?}",
2519                         token::get_name(name),
2520                         target.bindings.value_def.borrow());
2521                 match *target.bindings.value_def.borrow() {
2522                     None => {
2523                         panic!("resolved name in the value namespace to a \
2524                               set of name bindings with no def?!");
2525                     }
2526                     Some(def) => {
2527                         // For the two success cases, this lookup can be
2528                         // considered as not having a private component because
2529                         // the lookup happened only within the current module.
2530                         match def.def {
2531                             def @ DefVariant(..) | def @ DefStruct(..) => {
2532                                 return FoundStructOrEnumVariant(def, LastMod(AllPublic));
2533                             }
2534                             def @ DefConst(..) => {
2535                                 return FoundConst(def, LastMod(AllPublic));
2536                             }
2537                             DefStatic(..) => {
2538                                 self.resolve_error(span,
2539                                                    "static variables cannot be \
2540                                                     referenced in a pattern, \
2541                                                     use a `const` instead");
2542                                 return BareIdentifierPatternUnresolved;
2543                             }
2544                             _ => {
2545                                 return BareIdentifierPatternUnresolved;
2546                             }
2547                         }
2548                     }
2549                 }
2550             }
2551
2552             Indeterminate => {
2553                 panic!("unexpected indeterminate result");
2554             }
2555             Failed(err) => {
2556                 match err {
2557                     Some((span, msg)) => {
2558                         self.resolve_error(span, &format!("failed to resolve: {}",
2559                                                          msg));
2560                     }
2561                     None => ()
2562                 }
2563
2564                 debug!("(resolve bare identifier pattern) failed to find {}",
2565                         token::get_name(name));
2566                 return BareIdentifierPatternUnresolved;
2567             }
2568         }
2569     }
2570
2571     /// If `check_ribs` is true, checks the local definitions first; i.e.
2572     /// doesn't skip straight to the containing module.
2573     /// Skips `path_depth` trailing segments, which is also reflected in the
2574     /// returned value. See `middle::def::PathResolution` for more info.
2575     fn resolve_path(&mut self,
2576                     id: NodeId,
2577                     path: &Path,
2578                     path_depth: usize,
2579                     namespace: Namespace,
2580                     check_ribs: bool) -> Option<PathResolution> {
2581         let span = path.span;
2582         let segments = &path.segments[..path.segments.len()-path_depth];
2583
2584         let mk_res = |(def, lp)| PathResolution::new(def, lp, path_depth);
2585
2586         if path.global {
2587             let def = self.resolve_crate_relative_path(span, segments, namespace);
2588             return def.map(mk_res);
2589         }
2590
2591         // Try to find a path to an item in a module.
2592         let unqualified_def =
2593                 self.resolve_identifier(segments.last().unwrap().identifier,
2594                                         namespace,
2595                                         check_ribs,
2596                                         span);
2597
2598         if segments.len() <= 1 {
2599             return unqualified_def.map(mk_res);
2600         }
2601
2602         let def = self.resolve_module_relative_path(span, segments, namespace);
2603         match (def, unqualified_def) {
2604             (Some((ref d, _)), Some((ref ud, _))) if *d == *ud => {
2605                 self.session
2606                     .add_lint(lint::builtin::UNUSED_QUALIFICATIONS,
2607                               id, span,
2608                               "unnecessary qualification".to_string());
2609             }
2610             _ => {}
2611         }
2612
2613         def.map(mk_res)
2614     }
2615
2616     // Resolve a single identifier.
2617     fn resolve_identifier(&mut self,
2618                           identifier: Ident,
2619                           namespace: Namespace,
2620                           check_ribs: bool,
2621                           span: Span)
2622                           -> Option<(Def, LastPrivate)> {
2623         // First, check to see whether the name is a primitive type.
2624         if namespace == TypeNS {
2625             if let Some(&prim_ty) = self.primitive_type_table
2626                                         .primitive_types
2627                                         .get(&identifier.name) {
2628                 return Some((DefPrimTy(prim_ty), LastMod(AllPublic)));
2629             }
2630         }
2631
2632         if check_ribs {
2633             if let Some(def) = self.resolve_identifier_in_local_ribs(identifier,
2634                                                                      namespace,
2635                                                                      span) {
2636                 return Some((def, LastMod(AllPublic)));
2637             }
2638         }
2639
2640         self.resolve_item_by_name_in_lexical_scope(identifier.name, namespace)
2641     }
2642
2643     // FIXME #4952: Merge me with resolve_name_in_module?
2644     fn resolve_definition_of_name_in_module(&mut self,
2645                                             containing_module: Rc<Module>,
2646                                             name: Name,
2647                                             namespace: Namespace)
2648                                             -> NameDefinition {
2649         // First, search children.
2650         build_reduced_graph::populate_module_if_necessary(self, &containing_module);
2651
2652         match containing_module.children.borrow().get(&name) {
2653             Some(child_name_bindings) => {
2654                 match child_name_bindings.def_for_namespace(namespace) {
2655                     Some(def) => {
2656                         // Found it. Stop the search here.
2657                         let p = child_name_bindings.defined_in_public_namespace(namespace);
2658                         let lp = if p {LastMod(AllPublic)} else {
2659                             LastMod(DependsOn(def.def_id()))
2660                         };
2661                         return ChildNameDefinition(def, lp);
2662                     }
2663                     None => {}
2664                 }
2665             }
2666             None => {}
2667         }
2668
2669         // Next, search import resolutions.
2670         match containing_module.import_resolutions.borrow().get(&name) {
2671             Some(import_resolution) if import_resolution.is_public => {
2672                 if let Some(target) = (*import_resolution).target_for_namespace(namespace) {
2673                     match target.bindings.def_for_namespace(namespace) {
2674                         Some(def) => {
2675                             // Found it.
2676                             let id = import_resolution.id(namespace);
2677                             // track imports and extern crates as well
2678                             self.used_imports.insert((id, namespace));
2679                             self.record_import_use(id, name);
2680                             match target.target_module.def_id.get() {
2681                                 Some(DefId{krate: kid, ..}) => {
2682                                     self.used_crates.insert(kid);
2683                                 },
2684                                 _ => {}
2685                             }
2686                             return ImportNameDefinition(def, LastMod(AllPublic));
2687                         }
2688                         None => {
2689                             // This can happen with external impls, due to
2690                             // the imperfect way we read the metadata.
2691                         }
2692                     }
2693                 }
2694             }
2695             Some(..) | None => {} // Continue.
2696         }
2697
2698         // Finally, search through external children.
2699         if namespace == TypeNS {
2700             if let Some(module) = containing_module.external_module_children.borrow()
2701                                                    .get(&name).cloned() {
2702                 if let Some(def_id) = module.def_id.get() {
2703                     // track used crates
2704                     self.used_crates.insert(def_id.krate);
2705                     let lp = if module.is_public {LastMod(AllPublic)} else {
2706                         LastMod(DependsOn(def_id))
2707                     };
2708                     return ChildNameDefinition(DefMod(def_id), lp);
2709                 }
2710             }
2711         }
2712
2713         return NoNameDefinition;
2714     }
2715
2716     // resolve a "module-relative" path, e.g. a::b::c
2717     fn resolve_module_relative_path(&mut self,
2718                                     span: Span,
2719                                     segments: &[ast::PathSegment],
2720                                     namespace: Namespace)
2721                                     -> Option<(Def, LastPrivate)> {
2722         let module_path = segments.init().iter()
2723                                          .map(|ps| ps.identifier.name)
2724                                          .collect::<Vec<_>>();
2725
2726         let containing_module;
2727         let last_private;
2728         let current_module = self.current_module.clone();
2729         match self.resolve_module_path(current_module,
2730                                        &module_path[..],
2731                                        UseLexicalScope,
2732                                        span,
2733                                        PathSearch) {
2734             Failed(err) => {
2735                 let (span, msg) = match err {
2736                     Some((span, msg)) => (span, msg),
2737                     None => {
2738                         let msg = format!("Use of undeclared type or module `{}`",
2739                                           names_to_string(&module_path));
2740                         (span, msg)
2741                     }
2742                 };
2743
2744                 self.resolve_error(span, &format!("failed to resolve. {}",
2745                                                  msg));
2746                 return None;
2747             }
2748             Indeterminate => panic!("indeterminate unexpected"),
2749             Success((resulting_module, resulting_last_private)) => {
2750                 containing_module = resulting_module;
2751                 last_private = resulting_last_private;
2752             }
2753         }
2754
2755         let name = segments.last().unwrap().identifier.name;
2756         let def = match self.resolve_definition_of_name_in_module(containing_module.clone(),
2757                                                                   name,
2758                                                                   namespace) {
2759             NoNameDefinition => {
2760                 // We failed to resolve the name. Report an error.
2761                 return None;
2762             }
2763             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
2764                 (def, last_private.or(lp))
2765             }
2766         };
2767         if let Some(DefId{krate: kid, ..}) = containing_module.def_id.get() {
2768             self.used_crates.insert(kid);
2769         }
2770         return Some(def);
2771     }
2772
2773     /// Invariant: This must be called only during main resolution, not during
2774     /// import resolution.
2775     fn resolve_crate_relative_path(&mut self,
2776                                    span: Span,
2777                                    segments: &[ast::PathSegment],
2778                                    namespace: Namespace)
2779                                        -> Option<(Def, LastPrivate)> {
2780         let module_path = segments.init().iter()
2781                                          .map(|ps| ps.identifier.name)
2782                                          .collect::<Vec<_>>();
2783
2784         let root_module = self.graph_root.get_module();
2785
2786         let containing_module;
2787         let last_private;
2788         match self.resolve_module_path_from_root(root_module,
2789                                                  &module_path[..],
2790                                                  0,
2791                                                  span,
2792                                                  PathSearch,
2793                                                  LastMod(AllPublic)) {
2794             Failed(err) => {
2795                 let (span, msg) = match err {
2796                     Some((span, msg)) => (span, msg),
2797                     None => {
2798                         let msg = format!("Use of undeclared module `::{}`",
2799                                           names_to_string(&module_path[..]));
2800                         (span, msg)
2801                     }
2802                 };
2803
2804                 self.resolve_error(span, &format!("failed to resolve. {}",
2805                                                  msg));
2806                 return None;
2807             }
2808
2809             Indeterminate => {
2810                 panic!("indeterminate unexpected");
2811             }
2812
2813             Success((resulting_module, resulting_last_private)) => {
2814                 containing_module = resulting_module;
2815                 last_private = resulting_last_private;
2816             }
2817         }
2818
2819         let name = segments.last().unwrap().identifier.name;
2820         match self.resolve_definition_of_name_in_module(containing_module,
2821                                                         name,
2822                                                         namespace) {
2823             NoNameDefinition => {
2824                 // We failed to resolve the name. Report an error.
2825                 return None;
2826             }
2827             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
2828                 return Some((def, last_private.or(lp)));
2829             }
2830         }
2831     }
2832
2833     fn resolve_identifier_in_local_ribs(&mut self,
2834                                         ident: Ident,
2835                                         namespace: Namespace,
2836                                         span: Span)
2837                                         -> Option<Def> {
2838         // Check the local set of ribs.
2839         let search_result = match namespace {
2840             ValueNS => {
2841                 let renamed = mtwt::resolve(ident);
2842                 self.search_ribs(&self.value_ribs, renamed, span)
2843             }
2844             TypeNS => {
2845                 let name = ident.name;
2846                 self.search_ribs(&self.type_ribs, name, span)
2847             }
2848         };
2849
2850         match search_result {
2851             Some(DlDef(def)) => {
2852                 debug!("(resolving path in local ribs) resolved `{}` to local: {:?}",
2853                        token::get_ident(ident),
2854                        def);
2855                 Some(def)
2856             }
2857             Some(DlField) | Some(DlImpl(_)) | None => {
2858                 None
2859             }
2860         }
2861     }
2862
2863     fn resolve_item_by_name_in_lexical_scope(&mut self,
2864                                              name: Name,
2865                                              namespace: Namespace)
2866                                             -> Option<(Def, LastPrivate)> {
2867         // Check the items.
2868         let module = self.current_module.clone();
2869         match self.resolve_item_in_lexical_scope(module,
2870                                                  name,
2871                                                  namespace) {
2872             Success((target, _)) => {
2873                 match (*target.bindings).def_for_namespace(namespace) {
2874                     None => {
2875                         // This can happen if we were looking for a type and
2876                         // found a module instead. Modules don't have defs.
2877                         debug!("(resolving item path by identifier in lexical \
2878                                  scope) failed to resolve {} after success...",
2879                                  token::get_name(name));
2880                         return None;
2881                     }
2882                     Some(def) => {
2883                         debug!("(resolving item path in lexical scope) \
2884                                 resolved `{}` to item",
2885                                token::get_name(name));
2886                         // This lookup is "all public" because it only searched
2887                         // for one identifier in the current module (couldn't
2888                         // have passed through reexports or anything like that.
2889                         return Some((def, LastMod(AllPublic)));
2890                     }
2891                 }
2892             }
2893             Indeterminate => {
2894                 panic!("unexpected indeterminate result");
2895             }
2896             Failed(err) => {
2897                 debug!("(resolving item path by identifier in lexical scope) \
2898                          failed to resolve {}", token::get_name(name));
2899
2900                 if let Some((span, msg)) = err {
2901                     self.resolve_error(span, &format!("failed to resolve. {}", msg))
2902                 }
2903
2904                 return None;
2905             }
2906         }
2907     }
2908
2909     fn with_no_errors<T, F>(&mut self, f: F) -> T where
2910         F: FnOnce(&mut Resolver) -> T,
2911     {
2912         self.emit_errors = false;
2913         let rs = f(self);
2914         self.emit_errors = true;
2915         rs
2916     }
2917
2918     fn resolve_error(&self, span: Span, s: &str) {
2919         if self.emit_errors {
2920             self.session.span_err(span, s);
2921         }
2922     }
2923
2924     fn find_fallback_in_self_type(&mut self, name: Name) -> FallbackSuggestion {
2925         fn extract_path_and_node_id(t: &Ty, allow: FallbackChecks)
2926                                                     -> Option<(Path, NodeId, FallbackChecks)> {
2927             match t.node {
2928                 TyPath(None, ref path) => Some((path.clone(), t.id, allow)),
2929                 TyPtr(ref mut_ty) => extract_path_and_node_id(&*mut_ty.ty, OnlyTraitAndStatics),
2930                 TyRptr(_, ref mut_ty) => extract_path_and_node_id(&*mut_ty.ty, allow),
2931                 // This doesn't handle the remaining `Ty` variants as they are not
2932                 // that commonly the self_type, it might be interesting to provide
2933                 // support for those in future.
2934                 _ => None,
2935             }
2936         }
2937
2938         fn get_module(this: &mut Resolver, span: Span, name_path: &[ast::Name])
2939                             -> Option<Rc<Module>> {
2940             let root = this.current_module.clone();
2941             let last_name = name_path.last().unwrap();
2942
2943             if name_path.len() == 1 {
2944                 match this.primitive_type_table.primitive_types.get(last_name) {
2945                     Some(_) => None,
2946                     None => {
2947                         match this.current_module.children.borrow().get(last_name) {
2948                             Some(child) => child.get_module_if_available(),
2949                             None => None
2950                         }
2951                     }
2952                 }
2953             } else {
2954                 match this.resolve_module_path(root,
2955                                                &name_path[..],
2956                                                UseLexicalScope,
2957                                                span,
2958                                                PathSearch) {
2959                     Success((module, _)) => Some(module),
2960                     _ => None
2961                 }
2962             }
2963         }
2964
2965         fn is_static_method(this: &Resolver, did: DefId) -> bool {
2966             if did.krate == ast::LOCAL_CRATE {
2967                 let sig = match this.ast_map.get(did.node) {
2968                     ast_map::NodeTraitItem(trait_item) => match trait_item.node {
2969                         ast::MethodTraitItem(ref sig, _) => sig,
2970                         _ => return false
2971                     },
2972                     ast_map::NodeImplItem(impl_item) => match impl_item.node {
2973                         ast::MethodImplItem(ref sig, _) => sig,
2974                         _ => return false
2975                     },
2976                     _ => return false
2977                 };
2978                 sig.explicit_self.node == ast::SelfStatic
2979             } else {
2980                 csearch::is_static_method(&this.session.cstore, did)
2981             }
2982         }
2983
2984         let (path, node_id, allowed) = match self.current_self_type {
2985             Some(ref ty) => match extract_path_and_node_id(ty, Everything) {
2986                 Some(x) => x,
2987                 None => return NoSuggestion,
2988             },
2989             None => return NoSuggestion,
2990         };
2991
2992         if allowed == Everything {
2993             // Look for a field with the same name in the current self_type.
2994             match self.def_map.borrow().get(&node_id).map(|d| d.full_def()) {
2995                 Some(DefTy(did, _)) |
2996                 Some(DefStruct(did)) |
2997                 Some(DefVariant(_, did, _)) => match self.structs.get(&did) {
2998                     None => {}
2999                     Some(fields) => {
3000                         if fields.iter().any(|&field_name| name == field_name) {
3001                             return Field;
3002                         }
3003                     }
3004                 },
3005                 _ => {} // Self type didn't resolve properly
3006             }
3007         }
3008
3009         let name_path = path.segments.iter().map(|seg| seg.identifier.name).collect::<Vec<_>>();
3010
3011         // Look for a method in the current self type's impl module.
3012         if let Some(module) = get_module(self, path.span, &name_path) {
3013             if let Some(binding) = module.children.borrow().get(&name) {
3014                 if let Some(DefMethod(did, _)) = binding.def_for_namespace(ValueNS) {
3015                     if is_static_method(self, did) {
3016                         return StaticMethod(path_names_to_string(&path, 0))
3017                     }
3018                     if self.current_trait_ref.is_some() {
3019                         return TraitItem;
3020                     } else if allowed == Everything {
3021                         return Method;
3022                     }
3023                 }
3024             }
3025         }
3026
3027         // Look for a method in the current trait.
3028         if let Some((trait_did, ref trait_ref)) = self.current_trait_ref {
3029             if let Some(&did) = self.trait_item_map.get(&(name, trait_did)) {
3030                 if is_static_method(self, did) {
3031                     return TraitMethod(path_names_to_string(&trait_ref.path, 0));
3032                 } else {
3033                     return TraitItem;
3034                 }
3035             }
3036         }
3037
3038         NoSuggestion
3039     }
3040
3041     fn find_best_match_for_name(&mut self, name: &str, max_distance: usize)
3042                                 -> Option<String> {
3043         let this = &mut *self;
3044
3045         let mut maybes: Vec<token::InternedString> = Vec::new();
3046         let mut values: Vec<usize> = Vec::new();
3047
3048         for rib in this.value_ribs.iter().rev() {
3049             for (&k, _) in &rib.bindings {
3050                 maybes.push(token::get_name(k));
3051                 values.push(usize::MAX);
3052             }
3053         }
3054
3055         let mut smallest = 0;
3056         for (i, other) in maybes.iter().enumerate() {
3057             values[i] = lev_distance(name, &other);
3058
3059             if values[i] <= values[smallest] {
3060                 smallest = i;
3061             }
3062         }
3063
3064         if values.len() > 0 &&
3065             values[smallest] != usize::MAX &&
3066             values[smallest] < name.len() + 2 &&
3067             values[smallest] <= max_distance &&
3068             name != &maybes[smallest][..] {
3069
3070             Some(maybes[smallest].to_string())
3071
3072         } else {
3073             None
3074         }
3075     }
3076
3077     fn resolve_expr(&mut self, expr: &Expr) {
3078         // First, record candidate traits for this expression if it could
3079         // result in the invocation of a method call.
3080
3081         self.record_candidate_traits_for_expr_if_necessary(expr);
3082
3083         // Next, resolve the node.
3084         match expr.node {
3085             // `<T>::a::b::c` is resolved by typeck alone.
3086             ExprPath(Some(ast::QSelf { position: 0, .. }), ref path) => {
3087                 let method_name = path.segments.last().unwrap().identifier.name;
3088                 let traits = self.search_for_traits_containing_method(method_name);
3089                 self.trait_map.insert(expr.id, traits);
3090                 visit::walk_expr(self, expr);
3091             }
3092
3093             ExprPath(ref maybe_qself, ref path) => {
3094                 let max_assoc_types = if let Some(ref qself) = *maybe_qself {
3095                     // Make sure the trait is valid.
3096                     let _ = self.resolve_trait_reference(expr.id, path, 1);
3097                     path.segments.len() - qself.position
3098                 } else {
3099                     path.segments.len()
3100                 };
3101
3102                 let mut resolution = self.with_no_errors(|this| {
3103                     this.resolve_path(expr.id, path, 0, ValueNS, true)
3104                 });
3105                 for depth in 1..max_assoc_types {
3106                     if resolution.is_some() {
3107                         break;
3108                     }
3109                     self.with_no_errors(|this| {
3110                         resolution = this.resolve_path(expr.id, path, depth, TypeNS, true);
3111                     });
3112                 }
3113                 if let Some(DefMod(_)) = resolution.map(|r| r.base_def) {
3114                     // A module is not a valid type or value.
3115                     resolution = None;
3116                 }
3117
3118                 // This is a local path in the value namespace. Walk through
3119                 // scopes looking for it.
3120                 if let Some(path_res) = resolution {
3121                     // Check if struct variant
3122                     if let DefVariant(_, _, true) = path_res.base_def {
3123                         let path_name = path_names_to_string(path, 0);
3124                         self.resolve_error(expr.span,
3125                                 &format!("`{}` is a struct variant name, but \
3126                                           this expression \
3127                                           uses it like a function name",
3128                                          path_name));
3129
3130                         let msg = format!("Did you mean to write: \
3131                                            `{} {{ /* fields */ }}`?",
3132                                           path_name);
3133                         if self.emit_errors {
3134                             self.session.fileline_help(expr.span, &msg);
3135                         } else {
3136                             self.session.span_help(expr.span, &msg);
3137                         }
3138                     } else {
3139                         // Write the result into the def map.
3140                         debug!("(resolving expr) resolved `{}`",
3141                                path_names_to_string(path, 0));
3142
3143                         // Partial resolutions will need the set of traits in scope,
3144                         // so they can be completed during typeck.
3145                         if path_res.depth != 0 {
3146                             let method_name = path.segments.last().unwrap().identifier.name;
3147                             let traits = self.search_for_traits_containing_method(method_name);
3148                             self.trait_map.insert(expr.id, traits);
3149                         }
3150
3151                         self.record_def(expr.id, path_res);
3152                     }
3153                 } else {
3154                     // Be helpful if the name refers to a struct
3155                     // (The pattern matching def_tys where the id is in self.structs
3156                     // matches on regular structs while excluding tuple- and enum-like
3157                     // structs, which wouldn't result in this error.)
3158                     let path_name = path_names_to_string(path, 0);
3159                     let type_res = self.with_no_errors(|this| {
3160                         this.resolve_path(expr.id, path, 0, TypeNS, false)
3161                     });
3162                     match type_res.map(|r| r.base_def) {
3163                         Some(DefTy(struct_id, _))
3164                             if self.structs.contains_key(&struct_id) => {
3165                                 self.resolve_error(expr.span,
3166                                     &format!("`{}` is a structure name, but \
3167                                                 this expression \
3168                                                 uses it like a function name",
3169                                                 path_name));
3170
3171                                 let msg = format!("Did you mean to write: \
3172                                                      `{} {{ /* fields */ }}`?",
3173                                                     path_name);
3174                                 if self.emit_errors {
3175                                     self.session.fileline_help(expr.span, &msg);
3176                                 } else {
3177                                     self.session.span_help(expr.span, &msg);
3178                                 }
3179                             }
3180                         _ => {
3181                             // Keep reporting some errors even if they're ignored above.
3182                             self.resolve_path(expr.id, path, 0, ValueNS, true);
3183
3184                             let mut method_scope = false;
3185                             self.value_ribs.iter().rev().all(|rib| {
3186                                 method_scope = match rib.kind {
3187                                     MethodRibKind => true,
3188                                     ItemRibKind | ConstantItemRibKind => false,
3189                                     _ => return true, // Keep advancing
3190                                 };
3191                                 false // Stop advancing
3192                             });
3193
3194                             if method_scope &&
3195                                &token::get_name(special_names::self_)[..] == path_name {
3196                                     self.resolve_error(
3197                                         expr.span,
3198                                         "`self` is not available \
3199                                          in a static method. Maybe a \
3200                                          `self` argument is missing?");
3201                             } else {
3202                                 let last_name = path.segments.last().unwrap().identifier.name;
3203                                 let mut msg = match self.find_fallback_in_self_type(last_name) {
3204                                     NoSuggestion => {
3205                                         // limit search to 5 to reduce the number
3206                                         // of stupid suggestions
3207                                         self.find_best_match_for_name(&path_name, 5)
3208                                                             .map_or("".to_string(),
3209                                                                     |x| format!("`{}`", x))
3210                                     }
3211                                     Field => format!("`self.{}`", path_name),
3212                                     Method |
3213                                     TraitItem =>
3214                                         format!("to call `self.{}`", path_name),
3215                                     TraitMethod(path_str) |
3216                                     StaticMethod(path_str) =>
3217                                         format!("to call `{}::{}`", path_str, path_name)
3218                                 };
3219
3220                                 if msg.len() > 0 {
3221                                     msg = format!(". Did you mean {}?", msg)
3222                                 }
3223
3224                                 self.resolve_error(
3225                                     expr.span,
3226                                     &format!("unresolved name `{}`{}",
3227                                              path_name, msg));
3228                             }
3229                         }
3230                     }
3231                 }
3232
3233                 visit::walk_expr(self, expr);
3234             }
3235
3236             ExprStruct(ref path, _, _) => {
3237                 // Resolve the path to the structure it goes to. We don't
3238                 // check to ensure that the path is actually a structure; that
3239                 // is checked later during typeck.
3240                 match self.resolve_path(expr.id, path, 0, TypeNS, false) {
3241                     Some(definition) => self.record_def(expr.id, definition),
3242                     None => {
3243                         debug!("(resolving expression) didn't find struct def",);
3244                         let msg = format!("`{}` does not name a structure",
3245                                           path_names_to_string(path, 0));
3246                         self.resolve_error(path.span, &msg[..]);
3247                     }
3248                 }
3249
3250                 visit::walk_expr(self, expr);
3251             }
3252
3253             ExprLoop(_, Some(label)) | ExprWhile(_, _, Some(label)) => {
3254                 self.with_label_rib(|this| {
3255                     let def_like = DlDef(DefLabel(expr.id));
3256
3257                     {
3258                         let rib = this.label_ribs.last_mut().unwrap();
3259                         let renamed = mtwt::resolve(label);
3260                         rib.bindings.insert(renamed, def_like);
3261                     }
3262
3263                     visit::walk_expr(this, expr);
3264                 })
3265             }
3266
3267             ExprBreak(Some(label)) | ExprAgain(Some(label)) => {
3268                 let renamed = mtwt::resolve(label);
3269                 match self.search_label(renamed) {
3270                     None => {
3271                         self.resolve_error(
3272                             expr.span,
3273                             &format!("use of undeclared label `{}`",
3274                                     token::get_ident(label)))
3275                     }
3276                     Some(DlDef(def @ DefLabel(_))) => {
3277                         // Since this def is a label, it is never read.
3278                         self.record_def(expr.id, PathResolution {
3279                             base_def: def,
3280                             last_private: LastMod(AllPublic),
3281                             depth: 0
3282                         })
3283                     }
3284                     Some(_) => {
3285                         self.session.span_bug(expr.span,
3286                                               "label wasn't mapped to a \
3287                                                label def!")
3288                     }
3289                 }
3290             }
3291
3292             _ => {
3293                 visit::walk_expr(self, expr);
3294             }
3295         }
3296     }
3297
3298     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
3299         match expr.node {
3300             ExprField(_, ident) => {
3301                 // FIXME(#6890): Even though you can't treat a method like a
3302                 // field, we need to add any trait methods we find that match
3303                 // the field name so that we can do some nice error reporting
3304                 // later on in typeck.
3305                 let traits = self.search_for_traits_containing_method(ident.node.name);
3306                 self.trait_map.insert(expr.id, traits);
3307             }
3308             ExprMethodCall(ident, _, _) => {
3309                 debug!("(recording candidate traits for expr) recording \
3310                         traits for {}",
3311                        expr.id);
3312                 let traits = self.search_for_traits_containing_method(ident.node.name);
3313                 self.trait_map.insert(expr.id, traits);
3314             }
3315             _ => {
3316                 // Nothing to do.
3317             }
3318         }
3319     }
3320
3321     fn search_for_traits_containing_method(&mut self, name: Name) -> Vec<DefId> {
3322         debug!("(searching for traits containing method) looking for '{}'",
3323                token::get_name(name));
3324
3325         fn add_trait_info(found_traits: &mut Vec<DefId>,
3326                           trait_def_id: DefId,
3327                           name: Name) {
3328             debug!("(adding trait info) found trait {}:{} for method '{}'",
3329                 trait_def_id.krate,
3330                 trait_def_id.node,
3331                 token::get_name(name));
3332             found_traits.push(trait_def_id);
3333         }
3334
3335         let mut found_traits = Vec::new();
3336         let mut search_module = self.current_module.clone();
3337         loop {
3338             // Look for the current trait.
3339             match self.current_trait_ref {
3340                 Some((trait_def_id, _)) => {
3341                     if self.trait_item_map.contains_key(&(name, trait_def_id)) {
3342                         add_trait_info(&mut found_traits, trait_def_id, name);
3343                     }
3344                 }
3345                 None => {} // Nothing to do.
3346             }
3347
3348             // Look for trait children.
3349             build_reduced_graph::populate_module_if_necessary(self, &search_module);
3350
3351             {
3352                 for (_, child_names) in &*search_module.children.borrow() {
3353                     let def = match child_names.def_for_namespace(TypeNS) {
3354                         Some(def) => def,
3355                         None => continue
3356                     };
3357                     let trait_def_id = match def {
3358                         DefTrait(trait_def_id) => trait_def_id,
3359                         _ => continue,
3360                     };
3361                     if self.trait_item_map.contains_key(&(name, trait_def_id)) {
3362                         add_trait_info(&mut found_traits, trait_def_id, name);
3363                     }
3364                 }
3365             }
3366
3367             // Look for imports.
3368             for (_, import) in &*search_module.import_resolutions.borrow() {
3369                 let target = match import.target_for_namespace(TypeNS) {
3370                     None => continue,
3371                     Some(target) => target,
3372                 };
3373                 let did = match target.bindings.def_for_namespace(TypeNS) {
3374                     Some(DefTrait(trait_def_id)) => trait_def_id,
3375                     Some(..) | None => continue,
3376                 };
3377                 if self.trait_item_map.contains_key(&(name, did)) {
3378                     add_trait_info(&mut found_traits, did, name);
3379                     let id = import.type_id;
3380                     self.used_imports.insert((id, TypeNS));
3381                     let trait_name = self.get_trait_name(did);
3382                     self.record_import_use(id, trait_name);
3383                     if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
3384                         self.used_crates.insert(kid);
3385                     }
3386                 }
3387             }
3388
3389             match search_module.parent_link.clone() {
3390                 NoParentLink | ModuleParentLink(..) => break,
3391                 BlockParentLink(parent_module, _) => {
3392                     search_module = parent_module.upgrade().unwrap();
3393                 }
3394             }
3395         }
3396
3397         found_traits
3398     }
3399
3400     fn record_def(&mut self, node_id: NodeId, resolution: PathResolution) {
3401         debug!("(recording def) recording {:?} for {}", resolution, node_id);
3402         assert!(match resolution.last_private {LastImport{..} => false, _ => true},
3403                 "Import should only be used for `use` directives");
3404
3405         if let Some(prev_res) = self.def_map.borrow_mut().insert(node_id, resolution) {
3406             let span = self.ast_map.opt_span(node_id).unwrap_or(codemap::DUMMY_SP);
3407             self.session.span_bug(span, &format!("path resolved multiple times \
3408                                                   ({:?} before, {:?} now)",
3409                                                  prev_res, resolution));
3410         }
3411     }
3412
3413     fn enforce_default_binding_mode(&mut self,
3414                                         pat: &Pat,
3415                                         pat_binding_mode: BindingMode,
3416                                         descr: &str) {
3417         match pat_binding_mode {
3418             BindByValue(_) => {}
3419             BindByRef(..) => {
3420                 self.resolve_error(pat.span,
3421                                    &format!("cannot use `ref` binding mode \
3422                                             with {}",
3423                                            descr));
3424             }
3425         }
3426     }
3427
3428     //
3429     // Diagnostics
3430     //
3431     // Diagnostics are not particularly efficient, because they're rarely
3432     // hit.
3433     //
3434
3435     #[allow(dead_code)]   // useful for debugging
3436     fn dump_module(&mut self, module_: Rc<Module>) {
3437         debug!("Dump of module `{}`:", module_to_string(&*module_));
3438
3439         debug!("Children:");
3440         build_reduced_graph::populate_module_if_necessary(self, &module_);
3441         for (&name, _) in &*module_.children.borrow() {
3442             debug!("* {}", token::get_name(name));
3443         }
3444
3445         debug!("Import resolutions:");
3446         let import_resolutions = module_.import_resolutions.borrow();
3447         for (&name, import_resolution) in &*import_resolutions {
3448             let value_repr;
3449             match import_resolution.target_for_namespace(ValueNS) {
3450                 None => { value_repr = "".to_string(); }
3451                 Some(_) => {
3452                     value_repr = " value:?".to_string();
3453                     // FIXME #4954
3454                 }
3455             }
3456
3457             let type_repr;
3458             match import_resolution.target_for_namespace(TypeNS) {
3459                 None => { type_repr = "".to_string(); }
3460                 Some(_) => {
3461                     type_repr = " type:?".to_string();
3462                     // FIXME #4954
3463                 }
3464             }
3465
3466             debug!("* {}:{}{}", token::get_name(name), value_repr, type_repr);
3467         }
3468     }
3469 }
3470
3471
3472 fn names_to_string(names: &[Name]) -> String {
3473     let mut first = true;
3474     let mut result = String::new();
3475     for name in names {
3476         if first {
3477             first = false
3478         } else {
3479             result.push_str("::")
3480         }
3481         result.push_str(&token::get_name(*name));
3482     };
3483     result
3484 }
3485
3486 fn path_names_to_string(path: &Path, depth: usize) -> String {
3487     let names: Vec<ast::Name> = path.segments[..path.segments.len()-depth]
3488                                     .iter()
3489                                     .map(|seg| seg.identifier.name)
3490                                     .collect();
3491     names_to_string(&names[..])
3492 }
3493
3494 /// A somewhat inefficient routine to obtain the name of a module.
3495 fn module_to_string(module: &Module) -> String {
3496     let mut names = Vec::new();
3497
3498     fn collect_mod(names: &mut Vec<ast::Name>, module: &Module) {
3499         match module.parent_link {
3500             NoParentLink => {}
3501             ModuleParentLink(ref module, name) => {
3502                 names.push(name);
3503                 collect_mod(names, &*module.upgrade().unwrap());
3504             }
3505             BlockParentLink(ref module, _) => {
3506                 // danger, shouldn't be ident?
3507                 names.push(special_idents::opaque.name);
3508                 collect_mod(names, &*module.upgrade().unwrap());
3509             }
3510         }
3511     }
3512     collect_mod(&mut names, module);
3513
3514     if names.len() == 0 {
3515         return "???".to_string();
3516     }
3517     names_to_string(&names.into_iter().rev().collect::<Vec<ast::Name>>())
3518 }
3519
3520
3521 pub struct CrateMap {
3522     pub def_map: DefMap,
3523     pub freevars: RefCell<FreevarMap>,
3524     pub export_map: ExportMap,
3525     pub trait_map: TraitMap,
3526     pub external_exports: ExternalExports,
3527     pub glob_map: Option<GlobMap>
3528 }
3529
3530 #[derive(PartialEq,Copy)]
3531 pub enum MakeGlobMap {
3532     Yes,
3533     No
3534 }
3535
3536 /// Entry point to crate resolution.
3537 pub fn resolve_crate<'a, 'tcx>(session: &'a Session,
3538                                ast_map: &'a ast_map::Map<'tcx>,
3539                                _: &LanguageItems,
3540                                krate: &Crate,
3541                                make_glob_map: MakeGlobMap)
3542                                -> CrateMap {
3543     let mut resolver = Resolver::new(session, ast_map, krate.span, make_glob_map);
3544
3545     build_reduced_graph::build_reduced_graph(&mut resolver, krate);
3546     session.abort_if_errors();
3547
3548     resolve_imports::resolve_imports(&mut resolver);
3549     session.abort_if_errors();
3550
3551     record_exports::record(&mut resolver);
3552     session.abort_if_errors();
3553
3554     resolver.resolve_crate(krate);
3555     session.abort_if_errors();
3556
3557     check_unused::check_crate(&mut resolver, krate);
3558
3559     CrateMap {
3560         def_map: resolver.def_map,
3561         freevars: resolver.freevars,
3562         export_map: resolver.export_map,
3563         trait_map: resolver.trait_map,
3564         external_exports: resolver.external_exports,
3565         glob_map: if resolver.make_glob_map {
3566                         Some(resolver.glob_map)
3567                     } else {
3568                         None
3569                     },
3570     }
3571 }