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