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