src/librustc_resolve/lib.rs

   1 // Copyright 2012-2014 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 #![crate_name = "rustc_resolve"]
  12 #![unstable]
  13 #![staged_api]
  14 #![crate_type = "dylib"]
  15 #![crate_type = "rlib"]
  16 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  17       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  18       html_root_url = "http://doc.rust-lang.org/nightly/")]
  19
  20 #![feature(slicing_syntax)]
  21 #![feature(rustc_diagnostic_macros)]
  22 #![allow(unknown_features)] #![feature(int_uint)]
  23 #![allow(unstable)]
  24
  25 #[macro_use] extern crate log;
  26 #[macro_use] extern crate syntax;
  27 #[macro_use] #[no_link] extern crate rustc_bitflags;
  28
  29 extern crate rustc;
  30
  31 use self::PatternBindingMode::*;
  32 use self::Namespace::*;
  33 use self::NamespaceResult::*;
  34 use self::NameDefinition::*;
  35 use self::ImportDirectiveSubclass::*;
  36 use self::ResolveResult::*;
  37 use self::FallbackSuggestion::*;
  38 use self::TypeParameters::*;
  39 use self::RibKind::*;
  40 use self::MethodSort::*;
  41 use self::UseLexicalScopeFlag::*;
  42 use self::ModulePrefixResult::*;
  43 use self::NameSearchType::*;
  44 use self::BareIdentifierPatternResolution::*;
  45 use self::ParentLink::*;
  46 use self::ModuleKind::*;
  47 use self::TraitReferenceType::*;
  48 use self::FallbackChecks::*;
  49
  50 use rustc::session::Session;
  51 use rustc::lint;
  52 use rustc::metadata::csearch;
  53 use rustc::metadata::decoder::{DefLike, DlDef, DlField, DlImpl};
  54 use rustc::middle::def::*;
  55 use rustc::middle::lang_items::LanguageItems;
  56 use rustc::middle::pat_util::pat_bindings;
  57 use rustc::middle::privacy::*;
  58 use rustc::middle::subst::{ParamSpace, FnSpace, TypeSpace};
  59 use rustc::middle::ty::{CaptureModeMap, Freevar, FreevarMap, TraitMap, GlobMap};
  60 use rustc::util::nodemap::{NodeMap, NodeSet, DefIdSet, FnvHashMap};
  61 use rustc::util::lev_distance::lev_distance;
  62
  63 use syntax::ast::{Arm, BindByRef, BindByValue, BindingMode, Block, Crate, CrateNum};
  64 use syntax::ast::{DefId, Expr, ExprAgain, ExprBreak, ExprField};
  65 use syntax::ast::{ExprClosure, ExprForLoop, ExprLoop, ExprWhile, ExprMethodCall};
  66 use syntax::ast::{ExprPath, ExprQPath, ExprStruct, FnDecl};
  67 use syntax::ast::{ForeignItemFn, ForeignItemStatic, Generics};
  68 use syntax::ast::{Ident, ImplItem, Item, ItemConst, ItemEnum, ItemFn};
  69 use syntax::ast::{ItemForeignMod, ItemImpl, ItemMac, ItemMod, ItemStatic};
  70 use syntax::ast::{ItemStruct, ItemTrait, ItemTy, Local, LOCAL_CRATE};
  71 use syntax::ast::{MethodImplItem, Mod, Name, NodeId};
  72 use syntax::ast::{Pat, PatEnum, PatIdent, PatLit};
  73 use syntax::ast::{PatRange, PatStruct, Path};
  74 use syntax::ast::{PolyTraitRef, PrimTy, SelfExplicit};
  75 use syntax::ast::{RegionTyParamBound, StructField};
  76 use syntax::ast::{TraitRef, TraitTyParamBound};
  77 use syntax::ast::{Ty, TyBool, TyChar, TyF32};
  78 use syntax::ast::{TyF64, TyFloat, TyIs, TyI8, TyI16, TyI32, TyI64, TyInt, TyObjectSum};
  79 use syntax::ast::{TyParam, TyParamBound, TyPath, TyPtr, TyPolyTraitRef, TyQPath};
  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_map;
  84 use syntax::ast_util::{PostExpansionMethod, local_def, walk_pat};
  85 use syntax::attr::AttrMetaMethods;
  86 use syntax::ext::mtwt;
  87 use syntax::parse::token::{self, special_names, special_idents};
  88 use syntax::codemap::{Span, Pos};
  89 use syntax::owned_slice::OwnedSlice;
  90 use syntax::visit::{self, Visitor};
  91
  92 use std::collections::{HashMap, HashSet};
  93 use std::collections::hash_map::Entry::{Occupied, Vacant};
  94 use std::cell::{Cell, RefCell};
  95 use std::fmt;
  96 use std::mem::replace;
  97 use std::rc::{Rc, Weak};
  98 use std::uint;
  99
 100 // NB: This module needs to be declared first so diagnostics are
 101 // registered before they are used.
 102 pub mod diagnostics;
 103
 104 mod check_unused;
 105 mod record_exports;
 106 mod build_reduced_graph;
 107
 108 #[derive(Copy)]
 109 struct BindingInfo {
 110     span: Span,
 111     binding_mode: BindingMode,
 112 }
 113
 114 // Map from the name in a pattern to its binding mode.
 115 type BindingMap = HashMap<Name, BindingInfo>;
 116
 117 #[derive(Copy, PartialEq)]
 118 enum PatternBindingMode {
 119     RefutableMode,
 120     LocalIrrefutableMode,
 121     ArgumentIrrefutableMode,
 122 }
 123
 124 #[derive(Copy, PartialEq, Eq, Hash, Show)]
 125 enum Namespace {
 126     TypeNS,
 127     ValueNS
 128 }
 129
 130 /// A NamespaceResult represents the result of resolving an import in
 131 /// a particular namespace. The result is either definitely-resolved,
 132 /// definitely- unresolved, or unknown.
 133 #[derive(Clone)]
 134 enum NamespaceResult {
 135     /// Means that resolve hasn't gathered enough information yet to determine
 136     /// whether the name is bound in this namespace. (That is, it hasn't
 137     /// resolved all `use` directives yet.)
 138     UnknownResult,
 139     /// Means that resolve has determined that the name is definitely
 140     /// not bound in the namespace.
 141     UnboundResult,
 142     /// Means that resolve has determined that the name is bound in the Module
 143     /// argument, and specified by the NameBindings argument.
 144     BoundResult(Rc<Module>, Rc<NameBindings>)
 145 }
 146
 147 impl NamespaceResult {
 148     fn is_unknown(&self) -> bool {
 149         match *self {
 150             UnknownResult => true,
 151             _ => false
 152         }
 153     }
 154     fn is_unbound(&self) -> bool {
 155         match *self {
 156             UnboundResult => true,
 157             _ => false
 158         }
 159     }
 160 }
 161
 162 enum NameDefinition {
 163     NoNameDefinition,           //< The name was unbound.
 164     ChildNameDefinition(Def, LastPrivate), //< The name identifies an immediate child.
 165     ImportNameDefinition(Def, LastPrivate) //< The name identifies an import.
 166 }
 167
 168 impl<'a, 'v, 'tcx> Visitor<'v> for Resolver<'a, 'tcx> {
 169     fn visit_item(&mut self, item: &Item) {
 170         self.resolve_item(item);
 171     }
 172     fn visit_arm(&mut self, arm: &Arm) {
 173         self.resolve_arm(arm);
 174     }
 175     fn visit_block(&mut self, block: &Block) {
 176         self.resolve_block(block);
 177     }
 178     fn visit_expr(&mut self, expr: &Expr) {
 179         self.resolve_expr(expr);
 180     }
 181     fn visit_local(&mut self, local: &Local) {
 182         self.resolve_local(local);
 183     }
 184     fn visit_ty(&mut self, ty: &Ty) {
 185         self.resolve_type(ty);
 186     }
 187 }
 188
 189 /// Contains data for specific types of import directives.
 190 #[derive(Copy,Show)]
 191 enum ImportDirectiveSubclass {
 192     SingleImport(Name /* target */, Name /* source */),
 193     GlobImport
 194 }
 195
 196 type ErrorMessage = Option<(Span, String)>;
 197
 198 enum ResolveResult<T> {
 199     Failed(ErrorMessage),   // Failed to resolve the name, optional helpful error message.
 200     Indeterminate,          // Couldn't determine due to unresolved globs.
 201     Success(T)              // Successfully resolved the import.
 202 }
 203
 204 impl<T> ResolveResult<T> {
 205     fn indeterminate(&self) -> bool {
 206         match *self { Indeterminate => true, _ => false }
 207     }
 208 }
 209
 210 enum FallbackSuggestion {
 211     NoSuggestion,
 212     Field,
 213     Method,
 214     TraitItem,
 215     StaticMethod(String),
 216     TraitMethod(String),
 217 }
 218
 219 #[derive(Copy)]
 220 enum TypeParameters<'a> {
 221     NoTypeParameters,
 222     HasTypeParameters(
 223         // Type parameters.
 224         &'a Generics,
 225
 226         // Identifies the things that these parameters
 227         // were declared on (type, fn, etc)
 228         ParamSpace,
 229
 230         // ID of the enclosing item.
 231         NodeId,
 232
 233         // The kind of the rib used for type parameters.
 234         RibKind)
 235 }
 236
 237 // The rib kind controls the translation of local
 238 // definitions (`DefLocal`) to upvars (`DefUpvar`).
 239 #[derive(Copy, Show)]
 240 enum RibKind {
 241     // No translation needs to be applied.
 242     NormalRibKind,
 243
 244     // We passed through a closure scope at the given node ID.
 245     // Translate upvars as appropriate.
 246     ClosureRibKind(NodeId /* func id */, NodeId /* body id if proc or unboxed */),
 247
 248     // We passed through an impl or trait and are now in one of its
 249     // methods. Allow references to ty params that impl or trait
 250     // binds. Disallow any other upvars (including other ty params that are
 251     // upvars).
 252               // parent;   method itself
 253     MethodRibKind(NodeId, MethodSort),
 254
 255     // We passed through an item scope. Disallow upvars.
 256     ItemRibKind,
 257
 258     // We're in a constant item. Can't refer to dynamic stuff.
 259     ConstantItemRibKind
 260 }
 261
 262 // Methods can be required or provided. RequiredMethod methods only occur in traits.
 263 #[derive(Copy, Show)]
 264 enum MethodSort {
 265     RequiredMethod,
 266     ProvidedMethod(NodeId)
 267 }
 268
 269 #[derive(Copy)]
 270 enum UseLexicalScopeFlag {
 271     DontUseLexicalScope,
 272     UseLexicalScope
 273 }
 274
 275 enum ModulePrefixResult {
 276     NoPrefixFound,
 277     PrefixFound(Rc<Module>, uint)
 278 }
 279
 280 #[derive(Copy, PartialEq)]
 281 enum NameSearchType {
 282     /// We're doing a name search in order to resolve a `use` directive.
 283     ImportSearch,
 284
 285     /// We're doing a name search in order to resolve a path type, a path
 286     /// expression, or a path pattern.
 287     PathSearch,
 288 }
 289
 290 #[derive(Copy)]
 291 enum BareIdentifierPatternResolution {
 292     FoundStructOrEnumVariant(Def, LastPrivate),
 293     FoundConst(Def, LastPrivate),
 294     BareIdentifierPatternUnresolved
 295 }
 296
 297 /// One local scope.
 298 #[derive(Show)]
 299 struct Rib {
 300     bindings: HashMap<Name, DefLike>,
 301     kind: RibKind,
 302 }
 303
 304 impl Rib {
 305     fn new(kind: RibKind) -> Rib {
 306         Rib {
 307             bindings: HashMap::new(),
 308             kind: kind
 309         }
 310     }
 311 }
 312
 313 /// Whether an import can be shadowed by another import.
 314 #[derive(Show,PartialEq,Clone,Copy)]
 315 enum Shadowable {
 316     Always,
 317     Never
 318 }
 319
 320 /// One import directive.
 321 #[derive(Show)]
 322 struct ImportDirective {
 323     module_path: Vec<Name>,
 324     subclass: ImportDirectiveSubclass,
 325     span: Span,
 326     id: NodeId,
 327     is_public: bool, // see note in ImportResolution about how to use this
 328     shadowable: Shadowable,
 329 }
 330
 331 impl ImportDirective {
 332     fn new(module_path: Vec<Name> ,
 333            subclass: ImportDirectiveSubclass,
 334            span: Span,
 335            id: NodeId,
 336            is_public: bool,
 337            shadowable: Shadowable)
 338            -> ImportDirective {
 339         ImportDirective {
 340             module_path: module_path,
 341             subclass: subclass,
 342             span: span,
 343             id: id,
 344             is_public: is_public,
 345             shadowable: shadowable,
 346         }
 347     }
 348 }
 349
 350 /// The item that an import resolves to.
 351 #[derive(Clone,Show)]
 352 struct Target {
 353     target_module: Rc<Module>,
 354     bindings: Rc<NameBindings>,
 355     shadowable: Shadowable,
 356 }
 357
 358 impl Target {
 359     fn new(target_module: Rc<Module>,
 360            bindings: Rc<NameBindings>,
 361            shadowable: Shadowable)
 362            -> Target {
 363         Target {
 364             target_module: target_module,
 365             bindings: bindings,
 366             shadowable: shadowable,
 367         }
 368     }
 369 }
 370
 371 /// An ImportResolution represents a particular `use` directive.
 372 #[derive(Show)]
 373 struct ImportResolution {
 374     /// Whether this resolution came from a `use` or a `pub use`. Note that this
 375     /// should *not* be used whenever resolution is being performed, this is
 376     /// only looked at for glob imports statements currently. Privacy testing
 377     /// occurs during a later phase of compilation.
 378     is_public: bool,
 379
 380     // The number of outstanding references to this name. When this reaches
 381     // zero, outside modules can count on the targets being correct. Before
 382     // then, all bets are off; future imports could override this name.
 383     outstanding_references: uint,
 384
 385     /// The value that this `use` directive names, if there is one.
 386     value_target: Option<Target>,
 387     /// The source node of the `use` directive leading to the value target
 388     /// being non-none
 389     value_id: NodeId,
 390
 391     /// The type that this `use` directive names, if there is one.
 392     type_target: Option<Target>,
 393     /// The source node of the `use` directive leading to the type target
 394     /// being non-none
 395     type_id: NodeId,
 396 }
 397
 398 impl ImportResolution {
 399     fn new(id: NodeId, is_public: bool) -> ImportResolution {
 400         ImportResolution {
 401             type_id: id,
 402             value_id: id,
 403             outstanding_references: 0,
 404             value_target: None,
 405             type_target: None,
 406             is_public: is_public,
 407         }
 408     }
 409
 410     fn target_for_namespace(&self, namespace: Namespace)
 411                                 -> Option<Target> {
 412         match namespace {
 413             TypeNS  => self.type_target.clone(),
 414             ValueNS => self.value_target.clone(),
 415         }
 416     }
 417
 418     fn id(&self, namespace: Namespace) -> NodeId {
 419         match namespace {
 420             TypeNS  => self.type_id,
 421             ValueNS => self.value_id,
 422         }
 423     }
 424
 425     fn shadowable(&self, namespace: Namespace) -> Shadowable {
 426         let target = self.target_for_namespace(namespace);
 427         if target.is_none() {
 428             return Shadowable::Always;
 429         }
 430
 431         target.unwrap().shadowable
 432     }
 433
 434     fn set_target_and_id(&mut self,
 435                          namespace: Namespace,
 436                          target: Option<Target>,
 437                          id: NodeId) {
 438         match namespace {
 439             TypeNS  => {
 440                 self.type_target = target;
 441                 self.type_id = id;
 442             }
 443             ValueNS => {
 444                 self.value_target = target;
 445                 self.value_id = id;
 446             }
 447         }
 448     }
 449 }
 450
 451 /// The link from a module up to its nearest parent node.
 452 #[derive(Clone,Show)]
 453 enum ParentLink {
 454     NoParentLink,
 455     ModuleParentLink(Weak<Module>, Name),
 456     BlockParentLink(Weak<Module>, NodeId)
 457 }
 458
 459 /// The type of module this is.
 460 #[derive(Copy, PartialEq, Show)]
 461 enum ModuleKind {
 462     NormalModuleKind,
 463     TraitModuleKind,
 464     ImplModuleKind,
 465     EnumModuleKind,
 466     TypeModuleKind,
 467     AnonymousModuleKind,
 468 }
 469
 470 /// One node in the tree of modules.
 471 struct Module {
 472     parent_link: ParentLink,
 473     def_id: Cell<Option<DefId>>,
 474     kind: Cell<ModuleKind>,
 475     is_public: bool,
 476
 477     children: RefCell<HashMap<Name, Rc<NameBindings>>>,
 478     imports: RefCell<Vec<ImportDirective>>,
 479
 480     // The external module children of this node that were declared with
 481     // `extern crate`.
 482     external_module_children: RefCell<HashMap<Name, Rc<Module>>>,
 483
 484     // The anonymous children of this node. Anonymous children are pseudo-
 485     // modules that are implicitly created around items contained within
 486     // blocks.
 487     //
 488     // For example, if we have this:
 489     //
 490     //  fn f() {
 491     //      fn g() {
 492     //          ...
 493     //      }
 494     //  }
 495     //
 496     // There will be an anonymous module created around `g` with the ID of the
 497     // entry block for `f`.
 498     anonymous_children: RefCell<NodeMap<Rc<Module>>>,
 499
 500     // The status of resolving each import in this module.
 501     import_resolutions: RefCell<HashMap<Name, ImportResolution>>,
 502
 503     // The number of unresolved globs that this module exports.
 504     glob_count: Cell<uint>,
 505
 506     // The index of the import we're resolving.
 507     resolved_import_count: Cell<uint>,
 508
 509     // Whether this module is populated. If not populated, any attempt to
 510     // access the children must be preceded with a
 511     // `populate_module_if_necessary` call.
 512     populated: Cell<bool>,
 513 }
 514
 515 impl Module {
 516     fn new(parent_link: ParentLink,
 517            def_id: Option<DefId>,
 518            kind: ModuleKind,
 519            external: bool,
 520            is_public: bool)
 521            -> Module {
 522         Module {
 523             parent_link: parent_link,
 524             def_id: Cell::new(def_id),
 525             kind: Cell::new(kind),
 526             is_public: is_public,
 527             children: RefCell::new(HashMap::new()),
 528             imports: RefCell::new(Vec::new()),
 529             external_module_children: RefCell::new(HashMap::new()),
 530             anonymous_children: RefCell::new(NodeMap()),
 531             import_resolutions: RefCell::new(HashMap::new()),
 532             glob_count: Cell::new(0),
 533             resolved_import_count: Cell::new(0),
 534             populated: Cell::new(!external),
 535         }
 536     }
 537
 538     fn all_imports_resolved(&self) -> bool {
 539         self.imports.borrow().len() == self.resolved_import_count.get()
 540     }
 541 }
 542
 543 impl fmt::Show for Module {
 544     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 545         write!(f, "{:?}, kind: {:?}, {}",
 546                self.def_id,
 547                self.kind,
 548                if self.is_public { "public" } else { "private" } )
 549     }
 550 }
 551
 552 bitflags! {
 553     #[derive(Show)]
 554     flags DefModifiers: u8 {
 555         const PUBLIC            = 0b0000_0001,
 556         const IMPORTABLE        = 0b0000_0010,
 557     }
 558 }
 559
 560 // Records a possibly-private type definition.
 561 #[derive(Clone,Show)]
 562 struct TypeNsDef {
 563     modifiers: DefModifiers, // see note in ImportResolution about how to use this
 564     module_def: Option<Rc<Module>>,
 565     type_def: Option<Def>,
 566     type_span: Option<Span>
 567 }
 568
 569 // Records a possibly-private value definition.
 570 #[derive(Clone, Copy, Show)]
 571 struct ValueNsDef {
 572     modifiers: DefModifiers, // see note in ImportResolution about how to use this
 573     def: Def,
 574     value_span: Option<Span>,
 575 }
 576
 577 // Records the definitions (at most one for each namespace) that a name is
 578 // bound to.
 579 #[derive(Show)]
 580 struct NameBindings {
 581     type_def: RefCell<Option<TypeNsDef>>,   //< Meaning in type namespace.
 582     value_def: RefCell<Option<ValueNsDef>>, //< Meaning in value namespace.
 583 }
 584
 585 /// Ways in which a trait can be referenced
 586 #[derive(Copy)]
 587 enum TraitReferenceType {
 588     TraitImplementation,             // impl SomeTrait for T { ... }
 589     TraitDerivation,                 // trait T : SomeTrait { ... }
 590     TraitBoundingTypeParameter,      // fn f<T:SomeTrait>() { ... }
 591     TraitObject,                     // Box<for<'a> SomeTrait>
 592     TraitQPath,                      // <T as SomeTrait>::
 593 }
 594
 595 impl NameBindings {
 596     fn new() -> NameBindings {
 597         NameBindings {
 598             type_def: RefCell::new(None),
 599             value_def: RefCell::new(None),
 600         }
 601     }
 602
 603     /// Creates a new module in this set of name bindings.
 604     fn define_module(&self,
 605                      parent_link: ParentLink,
 606                      def_id: Option<DefId>,
 607                      kind: ModuleKind,
 608                      external: bool,
 609                      is_public: bool,
 610                      sp: Span) {
 611         // Merges the module with the existing type def or creates a new one.
 612         let modifiers = if is_public { PUBLIC } else { DefModifiers::empty() } | IMPORTABLE;
 613         let module_ = Rc::new(Module::new(parent_link,
 614                                           def_id,
 615                                           kind,
 616                                           external,
 617                                           is_public));
 618         let type_def = self.type_def.borrow().clone();
 619         match type_def {
 620             None => {
 621                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 622                     modifiers: modifiers,
 623                     module_def: Some(module_),
 624                     type_def: None,
 625                     type_span: Some(sp)
 626                 });
 627             }
 628             Some(type_def) => {
 629                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 630                     modifiers: modifiers,
 631                     module_def: Some(module_),
 632                     type_span: Some(sp),
 633                     type_def: type_def.type_def
 634                 });
 635             }
 636         }
 637     }
 638
 639     /// Sets the kind of the module, creating a new one if necessary.
 640     fn set_module_kind(&self,
 641                        parent_link: ParentLink,
 642                        def_id: Option<DefId>,
 643                        kind: ModuleKind,
 644                        external: bool,
 645                        is_public: bool,
 646                        _sp: Span) {
 647         let modifiers = if is_public { PUBLIC } else { DefModifiers::empty() } | IMPORTABLE;
 648         let type_def = self.type_def.borrow().clone();
 649         match type_def {
 650             None => {
 651                 let module = Module::new(parent_link,
 652                                          def_id,
 653                                          kind,
 654                                          external,
 655                                          is_public);
 656                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 657                     modifiers: modifiers,
 658                     module_def: Some(Rc::new(module)),
 659                     type_def: None,
 660                     type_span: None,
 661                 });
 662             }
 663             Some(type_def) => {
 664                 match type_def.module_def {
 665                     None => {
 666                         let module = Module::new(parent_link,
 667                                                  def_id,
 668                                                  kind,
 669                                                  external,
 670                                                  is_public);
 671                         *self.type_def.borrow_mut() = Some(TypeNsDef {
 672                             modifiers: modifiers,
 673                             module_def: Some(Rc::new(module)),
 674                             type_def: type_def.type_def,
 675                             type_span: None,
 676                         });
 677                     }
 678                     Some(module_def) => module_def.kind.set(kind),
 679                 }
 680             }
 681         }
 682     }
 683
 684     /// Records a type definition.
 685     fn define_type(&self, def: Def, sp: Span, modifiers: DefModifiers) {
 686         debug!("defining type for def {:?} with modifiers {:?}", def, modifiers);
 687         // Merges the type with the existing type def or creates a new one.
 688         let type_def = self.type_def.borrow().clone();
 689         match type_def {
 690             None => {
 691                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 692                     module_def: None,
 693                     type_def: Some(def),
 694                     type_span: Some(sp),
 695                     modifiers: modifiers,
 696                 });
 697             }
 698             Some(type_def) => {
 699                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 700                     module_def: type_def.module_def,
 701                     type_def: Some(def),
 702                     type_span: Some(sp),
 703                     modifiers: modifiers,
 704                 });
 705             }
 706         }
 707     }
 708
 709     /// Records a value definition.
 710     fn define_value(&self, def: Def, sp: Span, modifiers: DefModifiers) {
 711         debug!("defining value for def {:?} with modifiers {:?}", def, modifiers);
 712         *self.value_def.borrow_mut() = Some(ValueNsDef {
 713             def: def,
 714             value_span: Some(sp),
 715             modifiers: modifiers,
 716         });
 717     }
 718
 719     /// Returns the module node if applicable.
 720     fn get_module_if_available(&self) -> Option<Rc<Module>> {
 721         match *self.type_def.borrow() {
 722             Some(ref type_def) => type_def.module_def.clone(),
 723             None => None
 724         }
 725     }
 726
 727     /// Returns the module node. Panics if this node does not have a module
 728     /// definition.
 729     fn get_module(&self) -> Rc<Module> {
 730         match self.get_module_if_available() {
 731             None => {
 732                 panic!("get_module called on a node with no module \
 733                        definition!")
 734             }
 735             Some(module_def) => module_def
 736         }
 737     }
 738
 739     fn defined_in_namespace(&self, namespace: Namespace) -> bool {
 740         match namespace {
 741             TypeNS   => return self.type_def.borrow().is_some(),
 742             ValueNS  => return self.value_def.borrow().is_some()
 743         }
 744     }
 745
 746     fn defined_in_public_namespace(&self, namespace: Namespace) -> bool {
 747         self.defined_in_namespace_with(namespace, PUBLIC)
 748     }
 749
 750     fn defined_in_namespace_with(&self, namespace: Namespace, modifiers: DefModifiers) -> bool {
 751         match namespace {
 752             TypeNS => match *self.type_def.borrow() {
 753                 Some(ref def) => def.modifiers.contains(modifiers), None => false
 754             },
 755             ValueNS => match *self.value_def.borrow() {
 756                 Some(ref def) => def.modifiers.contains(modifiers), None => false
 757             }
 758         }
 759     }
 760
 761     fn def_for_namespace(&self, namespace: Namespace) -> Option<Def> {
 762         match namespace {
 763             TypeNS => {
 764                 match *self.type_def.borrow() {
 765                     None => None,
 766                     Some(ref type_def) => {
 767                         match type_def.type_def {
 768                             Some(type_def) => Some(type_def),
 769                             None => {
 770                                 match type_def.module_def {
 771                                     Some(ref module) => {
 772                                         match module.def_id.get() {
 773                                             Some(did) => Some(DefMod(did)),
 774                                             None => None,
 775                                         }
 776                                     }
 777                                     None => None,
 778                                 }
 779                             }
 780                         }
 781                     }
 782                 }
 783             }
 784             ValueNS => {
 785                 match *self.value_def.borrow() {
 786                     None => None,
 787                     Some(value_def) => Some(value_def.def)
 788                 }
 789             }
 790         }
 791     }
 792
 793     fn span_for_namespace(&self, namespace: Namespace) -> Option<Span> {
 794         if self.defined_in_namespace(namespace) {
 795             match namespace {
 796                 TypeNS  => {
 797                     match *self.type_def.borrow() {
 798                         None => None,
 799                         Some(ref type_def) => type_def.type_span
 800                     }
 801                 }
 802                 ValueNS => {
 803                     match *self.value_def.borrow() {
 804                         None => None,
 805                         Some(ref value_def) => value_def.value_span
 806                     }
 807                 }
 808             }
 809         } else {
 810             None
 811         }
 812     }
 813 }
 814
 815 /// Interns the names of the primitive types.
 816 struct PrimitiveTypeTable {
 817     primitive_types: HashMap<Name, PrimTy>,
 818 }
 819
 820 impl PrimitiveTypeTable {
 821     fn new() -> PrimitiveTypeTable {
 822         let mut table = PrimitiveTypeTable {
 823             primitive_types: HashMap::new()
 824         };
 825
 826         table.intern("bool",    TyBool);
 827         table.intern("char",    TyChar);
 828         table.intern("f32",     TyFloat(TyF32));
 829         table.intern("f64",     TyFloat(TyF64));
 830         table.intern("int",     TyInt(TyIs(true)));
 831         table.intern("isize",   TyInt(TyIs(false)));
 832         table.intern("i8",      TyInt(TyI8));
 833         table.intern("i16",     TyInt(TyI16));
 834         table.intern("i32",     TyInt(TyI32));
 835         table.intern("i64",     TyInt(TyI64));
 836         table.intern("str",     TyStr);
 837         table.intern("uint",    TyUint(TyUs(true)));
 838         table.intern("usize",   TyUint(TyUs(false)));
 839         table.intern("u8",      TyUint(TyU8));
 840         table.intern("u16",     TyUint(TyU16));
 841         table.intern("u32",     TyUint(TyU32));
 842         table.intern("u64",     TyUint(TyU64));
 843
 844         table
 845     }
 846
 847     fn intern(&mut self, string: &str, primitive_type: PrimTy) {
 848         self.primitive_types.insert(token::intern(string), primitive_type);
 849     }
 850 }
 851
 852 /// The main resolver class.
 853 struct Resolver<'a, 'tcx:'a> {
 854     session: &'a Session,
 855
 856     ast_map: &'a ast_map::Map<'tcx>,
 857
 858     graph_root: NameBindings,
 859
 860     trait_item_map: FnvHashMap<(Name, DefId), TraitItemKind>,
 861
 862     structs: FnvHashMap<DefId, Vec<Name>>,
 863
 864     // The number of imports that are currently unresolved.
 865     unresolved_imports: uint,
 866
 867     // The module that represents the current item scope.
 868     current_module: Rc<Module>,
 869
 870     // The current set of local scopes, for values.
 871     // FIXME #4948: Reuse ribs to avoid allocation.
 872     value_ribs: Vec<Rib>,
 873
 874     // The current set of local scopes, for types.
 875     type_ribs: Vec<Rib>,
 876
 877     // The current set of local scopes, for labels.
 878     label_ribs: Vec<Rib>,
 879
 880     // The trait that the current context can refer to.
 881     current_trait_ref: Option<(DefId, TraitRef)>,
 882
 883     // The current self type if inside an impl (used for better errors).
 884     current_self_type: Option<Ty>,
 885
 886     // The ident for the keyword "self".
 887     self_name: Name,
 888     // The ident for the non-keyword "Self".
 889     type_self_name: Name,
 890
 891     // The idents for the primitive types.
 892     primitive_type_table: PrimitiveTypeTable,
 893
 894     def_map: DefMap,
 895     freevars: RefCell<FreevarMap>,
 896     freevars_seen: RefCell<NodeMap<NodeSet>>,
 897     capture_mode_map: CaptureModeMap,
 898     export_map: ExportMap,
 899     trait_map: TraitMap,
 900     external_exports: ExternalExports,
 901     last_private: LastPrivateMap,
 902
 903     // Whether or not to print error messages. Can be set to true
 904     // when getting additional info for error message suggestions,
 905     // so as to avoid printing duplicate errors
 906     emit_errors: bool,
 907
 908     make_glob_map: bool,
 909     // Maps imports to the names of items actually imported (this actually maps
 910     // all imports, but only glob imports are actually interesting).
 911     glob_map: GlobMap,
 912
 913     used_imports: HashSet<(NodeId, Namespace)>,
 914     used_crates: HashSet<CrateNum>,
 915 }
 916
 917 #[derive(PartialEq)]
 918 enum FallbackChecks {
 919     Everything,
 920     OnlyTraitAndStatics
 921 }
 922
 923
 924 impl<'a, 'tcx> Resolver<'a, 'tcx> {
 925     fn new(session: &'a Session,
 926            ast_map: &'a ast_map::Map<'tcx>,
 927            crate_span: Span,
 928            make_glob_map: MakeGlobMap) -> Resolver<'a, 'tcx> {
 929         let graph_root = NameBindings::new();
 930
 931         graph_root.define_module(NoParentLink,
 932                                  Some(DefId { krate: 0, node: 0 }),
 933                                  NormalModuleKind,
 934                                  false,
 935                                  true,
 936                                  crate_span);
 937
 938         let current_module = graph_root.get_module();
 939
 940         Resolver {
 941             session: session,
 942
 943             ast_map: ast_map,
 944
 945             // The outermost module has def ID 0; this is not reflected in the
 946             // AST.
 947
 948             graph_root: graph_root,
 949
 950             trait_item_map: FnvHashMap(),
 951             structs: FnvHashMap(),
 952
 953             unresolved_imports: 0,
 954
 955             current_module: current_module,
 956             value_ribs: Vec::new(),
 957             type_ribs: Vec::new(),
 958             label_ribs: Vec::new(),
 959
 960             current_trait_ref: None,
 961             current_self_type: None,
 962
 963             self_name: special_names::self_,
 964             type_self_name: special_names::type_self,
 965
 966             primitive_type_table: PrimitiveTypeTable::new(),
 967
 968             def_map: RefCell::new(NodeMap()),
 969             freevars: RefCell::new(NodeMap()),
 970             freevars_seen: RefCell::new(NodeMap()),
 971             capture_mode_map: NodeMap(),
 972             export_map: NodeMap(),
 973             trait_map: NodeMap(),
 974             used_imports: HashSet::new(),
 975             used_crates: HashSet::new(),
 976             external_exports: DefIdSet(),
 977             last_private: NodeMap(),
 978
 979             emit_errors: true,
 980             make_glob_map: make_glob_map == MakeGlobMap::Yes,
 981             glob_map: HashMap::new(),
 982         }
 983     }
 984
 985     // Import resolution
 986     //
 987     // This is a fixed-point algorithm. We resolve imports until our efforts
 988     // are stymied by an unresolved import; then we bail out of the current
 989     // module and continue. We terminate successfully once no more imports
 990     // remain or unsuccessfully when no forward progress in resolving imports
 991     // is made.
 992
 993     /// Resolves all imports for the crate. This method performs the fixed-
 994     /// point iteration.
 995     fn resolve_imports(&mut self) {
 996         let mut i = 0u;
 997         let mut prev_unresolved_imports = 0;
 998         loop {
 999             debug!("(resolving imports) iteration {}, {} imports left",
1000                    i, self.unresolved_imports);
1001
1002             let module_root = self.graph_root.get_module();
1003             self.resolve_imports_for_module_subtree(module_root.clone());
1004
1005             if self.unresolved_imports == 0 {
1006                 debug!("(resolving imports) success");
1007                 break;
1008             }
1009
1010             if self.unresolved_imports == prev_unresolved_imports {
1011                 self.report_unresolved_imports(module_root);
1012                 break;
1013             }
1014
1015             i += 1;
1016             prev_unresolved_imports = self.unresolved_imports;
1017         }
1018     }
1019
1020     /// Attempts to resolve imports for the given module and all of its
1021     /// submodules.
1022     fn resolve_imports_for_module_subtree(&mut self, module_: Rc<Module>) {
1023         debug!("(resolving imports for module subtree) resolving {}",
1024                self.module_to_string(&*module_));
1025         let orig_module = replace(&mut self.current_module, module_.clone());
1026         self.resolve_imports_for_module(module_.clone());
1027         self.current_module = orig_module;
1028
1029         build_reduced_graph::populate_module_if_necessary(self, &module_);
1030         for (_, child_node) in module_.children.borrow().iter() {
1031             match child_node.get_module_if_available() {
1032                 None => {
1033                     // Nothing to do.
1034                 }
1035                 Some(child_module) => {
1036                     self.resolve_imports_for_module_subtree(child_module);
1037                 }
1038             }
1039         }
1040
1041         for (_, child_module) in module_.anonymous_children.borrow().iter() {
1042             self.resolve_imports_for_module_subtree(child_module.clone());
1043         }
1044     }
1045
1046     /// Attempts to resolve imports for the given module only.
1047     fn resolve_imports_for_module(&mut self, module: Rc<Module>) {
1048         if module.all_imports_resolved() {
1049             debug!("(resolving imports for module) all imports resolved for \
1050                    {}",
1051                    self.module_to_string(&*module));
1052             return;
1053         }
1054
1055         let imports = module.imports.borrow();
1056         let import_count = imports.len();
1057         while module.resolved_import_count.get() < import_count {
1058             let import_index = module.resolved_import_count.get();
1059             let import_directive = &(*imports)[import_index];
1060             match self.resolve_import_for_module(module.clone(),
1061                                                  import_directive) {
1062                 Failed(err) => {
1063                     let (span, help) = match err {
1064                         Some((span, msg)) => (span, format!(". {}", msg)),
1065                         None => (import_directive.span, String::new())
1066                     };
1067                     let msg = format!("unresolved import `{}`{}",
1068                                       self.import_path_to_string(
1069                                           &import_directive.module_path[],
1070                                           import_directive.subclass),
1071                                       help);
1072                     self.resolve_error(span, &msg[]);
1073                 }
1074                 Indeterminate => break, // Bail out. We'll come around next time.
1075                 Success(()) => () // Good. Continue.
1076             }
1077
1078             module.resolved_import_count
1079                   .set(module.resolved_import_count.get() + 1);
1080         }
1081     }
1082
1083     fn names_to_string(&self, names: &[Name]) -> String {
1084         let mut first = true;
1085         let mut result = String::new();
1086         for name in names.iter() {
1087             if first {
1088                 first = false
1089             } else {
1090                 result.push_str("::")
1091             }
1092             result.push_str(token::get_name(*name).get());
1093         };
1094         result
1095     }
1096
1097     fn path_names_to_string(&self, path: &Path) -> String {
1098         let names: Vec<ast::Name> = path.segments
1099                                         .iter()
1100                                         .map(|seg| seg.identifier.name)
1101                                         .collect();
1102         self.names_to_string(&names[])
1103     }
1104
1105     fn import_directive_subclass_to_string(&mut self,
1106                                         subclass: ImportDirectiveSubclass)
1107                                         -> String {
1108         match subclass {
1109             SingleImport(_, source) => {
1110                 token::get_name(source).get().to_string()
1111             }
1112             GlobImport => "*".to_string()
1113         }
1114     }
1115
1116     fn import_path_to_string(&mut self,
1117                           names: &[Name],
1118                           subclass: ImportDirectiveSubclass)
1119                           -> String {
1120         if names.is_empty() {
1121             self.import_directive_subclass_to_string(subclass)
1122         } else {
1123             (format!("{}::{}",
1124                      self.names_to_string(names),
1125                      self.import_directive_subclass_to_string(
1126                          subclass))).to_string()
1127         }
1128     }
1129
1130     #[inline]
1131     fn record_import_use(&mut self, import_id: NodeId, name: Name) {
1132         if !self.make_glob_map {
1133             return;
1134         }
1135         if self.glob_map.contains_key(&import_id) {
1136             self.glob_map[import_id].insert(name);
1137             return;
1138         }
1139
1140         let mut new_set = HashSet::new();
1141         new_set.insert(name);
1142         self.glob_map.insert(import_id, new_set);
1143     }
1144
1145     fn get_trait_name(&self, did: DefId) -> Name {
1146         if did.krate == LOCAL_CRATE {
1147             self.ast_map.expect_item(did.node).ident.name
1148         } else {
1149             csearch::get_trait_name(&self.session.cstore, did)
1150         }
1151     }
1152
1153     /// Attempts to resolve the given import. The return value indicates
1154     /// failure if we're certain the name does not exist, indeterminate if we
1155     /// don't know whether the name exists at the moment due to other
1156     /// currently-unresolved imports, or success if we know the name exists.
1157     /// If successful, the resolved bindings are written into the module.
1158     fn resolve_import_for_module(&mut self,
1159                                  module_: Rc<Module>,
1160                                  import_directive: &ImportDirective)
1161                                  -> ResolveResult<()> {
1162         let mut resolution_result = Failed(None);
1163         let module_path = &import_directive.module_path;
1164
1165         debug!("(resolving import for module) resolving import `{}::...` in `{}`",
1166                self.names_to_string(&module_path[]),
1167                self.module_to_string(&*module_));
1168
1169         // First, resolve the module path for the directive, if necessary.
1170         let container = if module_path.len() == 0 {
1171             // Use the crate root.
1172             Some((self.graph_root.get_module(), LastMod(AllPublic)))
1173         } else {
1174             match self.resolve_module_path(module_.clone(),
1175                                            &module_path[],
1176                                            DontUseLexicalScope,
1177                                            import_directive.span,
1178                                            ImportSearch) {
1179                 Failed(err) => {
1180                     resolution_result = Failed(err);
1181                     None
1182                 },
1183                 Indeterminate => {
1184                     resolution_result = Indeterminate;
1185                     None
1186                 }
1187                 Success(container) => Some(container),
1188             }
1189         };
1190
1191         match container {
1192             None => {}
1193             Some((containing_module, lp)) => {
1194                 // We found the module that the target is contained
1195                 // within. Attempt to resolve the import within it.
1196
1197                 match import_directive.subclass {
1198                     SingleImport(target, source) => {
1199                         resolution_result =
1200                             self.resolve_single_import(&*module_,
1201                                                        containing_module,
1202                                                        target,
1203                                                        source,
1204                                                        import_directive,
1205                                                        lp);
1206                     }
1207                     GlobImport => {
1208                         resolution_result =
1209                             self.resolve_glob_import(&*module_,
1210                                                      containing_module,
1211                                                      import_directive,
1212                                                      lp);
1213                     }
1214                 }
1215             }
1216         }
1217
1218         // Decrement the count of unresolved imports.
1219         match resolution_result {
1220             Success(()) => {
1221                 assert!(self.unresolved_imports >= 1);
1222                 self.unresolved_imports -= 1;
1223             }
1224             _ => {
1225                 // Nothing to do here; just return the error.
1226             }
1227         }
1228
1229         // Decrement the count of unresolved globs if necessary. But only if
1230         // the resolution result is indeterminate -- otherwise we'll stop
1231         // processing imports here. (See the loop in
1232         // resolve_imports_for_module.)
1233
1234         if !resolution_result.indeterminate() {
1235             match import_directive.subclass {
1236                 GlobImport => {
1237                     assert!(module_.glob_count.get() >= 1);
1238                     module_.glob_count.set(module_.glob_count.get() - 1);
1239                 }
1240                 SingleImport(..) => {
1241                     // Ignore.
1242                 }
1243             }
1244         }
1245
1246         return resolution_result;
1247     }
1248
1249     fn create_name_bindings_from_module(module: Rc<Module>) -> NameBindings {
1250         NameBindings {
1251             type_def: RefCell::new(Some(TypeNsDef {
1252                 modifiers: IMPORTABLE,
1253                 module_def: Some(module),
1254                 type_def: None,
1255                 type_span: None
1256             })),
1257             value_def: RefCell::new(None),
1258         }
1259     }
1260
1261     fn resolve_single_import(&mut self,
1262                              module_: &Module,
1263                              containing_module: Rc<Module>,
1264                              target: Name,
1265                              source: Name,
1266                              directive: &ImportDirective,
1267                              lp: LastPrivate)
1268                                  -> ResolveResult<()> {
1269         debug!("(resolving single import) resolving `{}` = `{}::{}` from \
1270                 `{}` id {}, last private {:?}",
1271                token::get_name(target),
1272                self.module_to_string(&*containing_module),
1273                token::get_name(source),
1274                self.module_to_string(module_),
1275                directive.id,
1276                lp);
1277
1278         let lp = match lp {
1279             LastMod(lp) => lp,
1280             LastImport {..} => {
1281                 self.session
1282                     .span_bug(directive.span,
1283                               "not expecting Import here, must be LastMod")
1284             }
1285         };
1286
1287         // We need to resolve both namespaces for this to succeed.
1288         //
1289
1290         let mut value_result = UnknownResult;
1291         let mut type_result = UnknownResult;
1292
1293         // Search for direct children of the containing module.
1294         build_reduced_graph::populate_module_if_necessary(self, &containing_module);
1295
1296         match containing_module.children.borrow().get(&source) {
1297             None => {
1298                 // Continue.
1299             }
1300             Some(ref child_name_bindings) => {
1301                 if child_name_bindings.defined_in_namespace(ValueNS) {
1302                     debug!("(resolving single import) found value binding");
1303                     value_result = BoundResult(containing_module.clone(),
1304                                                (*child_name_bindings).clone());
1305                 }
1306                 if child_name_bindings.defined_in_namespace(TypeNS) {
1307                     debug!("(resolving single import) found type binding");
1308                     type_result = BoundResult(containing_module.clone(),
1309                                               (*child_name_bindings).clone());
1310                 }
1311             }
1312         }
1313
1314         // Unless we managed to find a result in both namespaces (unlikely),
1315         // search imports as well.
1316         let mut value_used_reexport = false;
1317         let mut type_used_reexport = false;
1318         match (value_result.clone(), type_result.clone()) {
1319             (BoundResult(..), BoundResult(..)) => {} // Continue.
1320             _ => {
1321                 // If there is an unresolved glob at this point in the
1322                 // containing module, bail out. We don't know enough to be
1323                 // able to resolve this import.
1324
1325                 if containing_module.glob_count.get() > 0 {
1326                     debug!("(resolving single import) unresolved glob; \
1327                             bailing out");
1328                     return Indeterminate;
1329                 }
1330
1331                 // Now search the exported imports within the containing module.
1332                 match containing_module.import_resolutions.borrow().get(&source) {
1333                     None => {
1334                         debug!("(resolving single import) no import");
1335                         // The containing module definitely doesn't have an
1336                         // exported import with the name in question. We can
1337                         // therefore accurately report that the names are
1338                         // unbound.
1339
1340                         if value_result.is_unknown() {
1341                             value_result = UnboundResult;
1342                         }
1343                         if type_result.is_unknown() {
1344                             type_result = UnboundResult;
1345                         }
1346                     }
1347                     Some(import_resolution)
1348                             if import_resolution.outstanding_references == 0 => {
1349
1350                         fn get_binding(this: &mut Resolver,
1351                                        import_resolution: &ImportResolution,
1352                                        namespace: Namespace,
1353                                        source: &Name)
1354                                     -> NamespaceResult {
1355
1356                             // Import resolutions must be declared with "pub"
1357                             // in order to be exported.
1358                             if !import_resolution.is_public {
1359                                 return UnboundResult;
1360                             }
1361
1362                             match import_resolution.
1363                                     target_for_namespace(namespace) {
1364                                 None => {
1365                                     return UnboundResult;
1366                                 }
1367                                 Some(Target {
1368                                     target_module,
1369                                     bindings,
1370                                     shadowable: _
1371                                 }) => {
1372                                     debug!("(resolving single import) found \
1373                                             import in ns {:?}", namespace);
1374                                     let id = import_resolution.id(namespace);
1375                                     // track used imports and extern crates as well
1376                                     this.used_imports.insert((id, namespace));
1377                                     this.record_import_use(id, *source);
1378                                     match target_module.def_id.get() {
1379                                         Some(DefId{krate: kid, ..}) => {
1380                                             this.used_crates.insert(kid);
1381                                         },
1382                                         _ => {}
1383                                     }
1384                                     return BoundResult(target_module, bindings);
1385                                 }
1386                             }
1387                         }
1388
1389                         // The name is an import which has been fully
1390                         // resolved. We can, therefore, just follow it.
1391                         if value_result.is_unknown() {
1392                             value_result = get_binding(self,
1393                                                        import_resolution,
1394                                                        ValueNS,
1395                                                        &source);
1396                             value_used_reexport = import_resolution.is_public;
1397                         }
1398                         if type_result.is_unknown() {
1399                             type_result = get_binding(self,
1400                                                       import_resolution,
1401                                                       TypeNS,
1402                                                       &source);
1403                             type_used_reexport = import_resolution.is_public;
1404                         }
1405
1406                     }
1407                     Some(_) => {
1408                         // If containing_module is the same module whose import we are resolving
1409                         // and there it has an unresolved import with the same name as `source`,
1410                         // then the user is actually trying to import an item that is declared
1411                         // in the same scope
1412                         //
1413                         // e.g
1414                         // use self::submodule;
1415                         // pub mod submodule;
1416                         //
1417                         // In this case we continue as if we resolved the import and let the
1418                         // check_for_conflicts_between_imports_and_items call below handle
1419                         // the conflict
1420                         match (module_.def_id.get(),  containing_module.def_id.get()) {
1421                             (Some(id1), Some(id2)) if id1 == id2  => {
1422                                 if value_result.is_unknown() {
1423                                     value_result = UnboundResult;
1424                                 }
1425                                 if type_result.is_unknown() {
1426                                     type_result = UnboundResult;
1427                                 }
1428                             }
1429                             _ =>  {
1430                                 // The import is unresolved. Bail out.
1431                                 debug!("(resolving single import) unresolved import; \
1432                                         bailing out");
1433                                 return Indeterminate;
1434                             }
1435                         }
1436                     }
1437                 }
1438             }
1439         }
1440
1441         // If we didn't find a result in the type namespace, search the
1442         // external modules.
1443         let mut value_used_public = false;
1444         let mut type_used_public = false;
1445         match type_result {
1446             BoundResult(..) => {}
1447             _ => {
1448                 match containing_module.external_module_children.borrow_mut()
1449                                        .get(&source).cloned() {
1450                     None => {} // Continue.
1451                     Some(module) => {
1452                         debug!("(resolving single import) found external \
1453                                 module");
1454                         // track the module as used.
1455                         match module.def_id.get() {
1456                             Some(DefId{krate: kid, ..}) => { self.used_crates.insert(kid); },
1457                             _ => {}
1458                         }
1459                         let name_bindings =
1460                             Rc::new(Resolver::create_name_bindings_from_module(
1461                                 module));
1462                         type_result = BoundResult(containing_module.clone(),
1463                                                   name_bindings);
1464                         type_used_public = true;
1465                     }
1466                 }
1467             }
1468         }
1469
1470         // We've successfully resolved the import. Write the results in.
1471         let mut import_resolutions = module_.import_resolutions.borrow_mut();
1472         let import_resolution = &mut (*import_resolutions)[target];
1473         {
1474             let mut check_and_write_import = |&mut: namespace, result: &_, used_public: &mut bool| {
1475                 let namespace_name = match namespace {
1476                     TypeNS => "type",
1477                     ValueNS => "value",
1478                 };
1479
1480                 match *result {
1481                     BoundResult(ref target_module, ref name_bindings) => {
1482                         debug!("(resolving single import) found {:?} target: {:?}",
1483                                namespace_name,
1484                                name_bindings.def_for_namespace(namespace));
1485                         self.check_for_conflicting_import(
1486                             &import_resolution.target_for_namespace(namespace),
1487                             directive.span,
1488                             target,
1489                             namespace);
1490
1491                         self.check_that_import_is_importable(
1492                             &**name_bindings,
1493                             directive.span,
1494                             target,
1495                             namespace);
1496
1497                         let target = Some(Target::new(target_module.clone(),
1498                                                       name_bindings.clone(),
1499                                                       directive.shadowable));
1500                         import_resolution.set_target_and_id(namespace, target, directive.id);
1501                         import_resolution.is_public = directive.is_public;
1502                         *used_public = name_bindings.defined_in_public_namespace(namespace);
1503                     }
1504                     UnboundResult => { /* Continue. */ }
1505                     UnknownResult => {
1506                         panic!("{:?} result should be known at this point", namespace_name);
1507                     }
1508                 }
1509             };
1510             check_and_write_import(ValueNS, &value_result, &mut value_used_public);
1511             check_and_write_import(TypeNS, &type_result, &mut type_used_public);
1512         }
1513
1514         self.check_for_conflicts_between_imports_and_items(
1515             module_,
1516             import_resolution,
1517             directive.span,
1518             target);
1519
1520         if value_result.is_unbound() && type_result.is_unbound() {
1521             let msg = format!("There is no `{}` in `{}`",
1522                               token::get_name(source),
1523                               self.module_to_string(&*containing_module));
1524             return Failed(Some((directive.span, msg)));
1525         }
1526         let value_used_public = value_used_reexport || value_used_public;
1527         let type_used_public = type_used_reexport || type_used_public;
1528
1529         assert!(import_resolution.outstanding_references >= 1);
1530         import_resolution.outstanding_references -= 1;
1531
1532         // record what this import resolves to for later uses in documentation,
1533         // this may resolve to either a value or a type, but for documentation
1534         // purposes it's good enough to just favor one over the other.
1535         let value_private = match import_resolution.value_target {
1536             Some(ref target) => {
1537                 let def = target.bindings.def_for_namespace(ValueNS).unwrap();
1538                 self.def_map.borrow_mut().insert(directive.id, def);
1539                 let did = def.def_id();
1540                 if value_used_public {Some(lp)} else {Some(DependsOn(did))}
1541             },
1542             // AllPublic here and below is a dummy value, it should never be used because
1543             // _exists is false.
1544             None => None,
1545         };
1546         let type_private = match import_resolution.type_target {
1547             Some(ref target) => {
1548                 let def = target.bindings.def_for_namespace(TypeNS).unwrap();
1549                 self.def_map.borrow_mut().insert(directive.id, def);
1550                 let did = def.def_id();
1551                 if type_used_public {Some(lp)} else {Some(DependsOn(did))}
1552             },
1553             None => None,
1554         };
1555
1556         self.last_private.insert(directive.id, LastImport{value_priv: value_private,
1557                                                           value_used: Used,
1558                                                           type_priv: type_private,
1559                                                           type_used: Used});
1560
1561         debug!("(resolving single import) successfully resolved import");
1562         return Success(());
1563     }
1564
1565     // Resolves a glob import. Note that this function cannot fail; it either
1566     // succeeds or bails out (as importing * from an empty module or a module
1567     // that exports nothing is valid). containing_module is the module we are
1568     // actually importing, i.e., `foo` in `use foo::*`.
1569     fn resolve_glob_import(&mut self,
1570                            module_: &Module,
1571                            containing_module: Rc<Module>,
1572                            import_directive: &ImportDirective,
1573                            lp: LastPrivate)
1574                            -> ResolveResult<()> {
1575         let id = import_directive.id;
1576         let is_public = import_directive.is_public;
1577
1578         // This function works in a highly imperative manner; it eagerly adds
1579         // everything it can to the list of import resolutions of the module
1580         // node.
1581         debug!("(resolving glob import) resolving glob import {}", id);
1582
1583         // We must bail out if the node has unresolved imports of any kind
1584         // (including globs).
1585         if !(*containing_module).all_imports_resolved() {
1586             debug!("(resolving glob import) target module has unresolved \
1587                     imports; bailing out");
1588             return Indeterminate;
1589         }
1590
1591         assert_eq!(containing_module.glob_count.get(), 0);
1592
1593         // Add all resolved imports from the containing module.
1594         let import_resolutions = containing_module.import_resolutions.borrow();
1595         for (ident, target_import_resolution) in import_resolutions.iter() {
1596             debug!("(resolving glob import) writing module resolution \
1597                     {} into `{}`",
1598                    token::get_name(*ident),
1599                    self.module_to_string(module_));
1600
1601             if !target_import_resolution.is_public {
1602                 debug!("(resolving glob import) nevermind, just kidding");
1603                 continue
1604             }
1605
1606             // Here we merge two import resolutions.
1607             let mut import_resolutions = module_.import_resolutions.borrow_mut();
1608             match import_resolutions.get_mut(ident) {
1609                 Some(dest_import_resolution) => {
1610                     // Merge the two import resolutions at a finer-grained
1611                     // level.
1612
1613                     match target_import_resolution.value_target {
1614                         None => {
1615                             // Continue.
1616                         }
1617                         Some(ref value_target) => {
1618                             self.check_for_conflicting_import(&dest_import_resolution.value_target,
1619                                                               import_directive.span,
1620                                                               *ident,
1621                                                               ValueNS);
1622                             dest_import_resolution.value_target = Some(value_target.clone());
1623                         }
1624                     }
1625                     match target_import_resolution.type_target {
1626                         None => {
1627                             // Continue.
1628                         }
1629                         Some(ref type_target) => {
1630                             self.check_for_conflicting_import(&dest_import_resolution.type_target,
1631                                                               import_directive.span,
1632                                                               *ident,
1633                                                               TypeNS);
1634                             dest_import_resolution.type_target = Some(type_target.clone());
1635                         }
1636                     }
1637                     dest_import_resolution.is_public = is_public;
1638                     continue;
1639                 }
1640                 None => {}
1641             }
1642
1643             // Simple: just copy the old import resolution.
1644             let mut new_import_resolution = ImportResolution::new(id, is_public);
1645             new_import_resolution.value_target =
1646                 target_import_resolution.value_target.clone();
1647             new_import_resolution.type_target =
1648                 target_import_resolution.type_target.clone();
1649
1650             import_resolutions.insert(*ident, new_import_resolution);
1651         }
1652
1653         // Add all children from the containing module.
1654         build_reduced_graph::populate_module_if_necessary(self, &containing_module);
1655
1656         for (&name, name_bindings) in containing_module.children.borrow().iter() {
1657             self.merge_import_resolution(module_,
1658                                          containing_module.clone(),
1659                                          import_directive,
1660                                          name,
1661                                          name_bindings.clone());
1662
1663         }
1664
1665         // Add external module children from the containing module.
1666         for (&name, module) in containing_module.external_module_children.borrow().iter() {
1667             let name_bindings =
1668                 Rc::new(Resolver::create_name_bindings_from_module(module.clone()));
1669             self.merge_import_resolution(module_,
1670                                          containing_module.clone(),
1671                                          import_directive,
1672                                          name,
1673                                          name_bindings);
1674         }
1675
1676         // Record the destination of this import
1677         match containing_module.def_id.get() {
1678             Some(did) => {
1679                 self.def_map.borrow_mut().insert(id, DefMod(did));
1680                 self.last_private.insert(id, lp);
1681             }
1682             None => {}
1683         }
1684
1685         debug!("(resolving glob import) successfully resolved import");
1686         return Success(());
1687     }
1688
1689     fn merge_import_resolution(&mut self,
1690                                module_: &Module,
1691                                containing_module: Rc<Module>,
1692                                import_directive: &ImportDirective,
1693                                name: Name,
1694                                name_bindings: Rc<NameBindings>) {
1695         let id = import_directive.id;
1696         let is_public = import_directive.is_public;
1697
1698         let mut import_resolutions = module_.import_resolutions.borrow_mut();
1699         let dest_import_resolution = import_resolutions.entry(name).get().unwrap_or_else(
1700             |vacant_entry| {
1701                 // Create a new import resolution from this child.
1702                 vacant_entry.insert(ImportResolution::new(id, is_public))
1703             });
1704
1705         debug!("(resolving glob import) writing resolution `{}` in `{}` \
1706                to `{}`",
1707                token::get_name(name).get(),
1708                self.module_to_string(&*containing_module),
1709                self.module_to_string(module_));
1710
1711         // Merge the child item into the import resolution.
1712         {
1713             let mut merge_child_item = |&mut : namespace| {
1714                 if name_bindings.defined_in_namespace_with(namespace, IMPORTABLE | PUBLIC) {
1715                     let namespace_name = match namespace {
1716                         TypeNS => "type",
1717                         ValueNS => "value",
1718                     };
1719                     debug!("(resolving glob import) ... for {} target", namespace_name);
1720                     if dest_import_resolution.shadowable(namespace) == Shadowable::Never {
1721                         let msg = format!("a {} named `{}` has already been imported \
1722                                            in this module",
1723                                           namespace_name,
1724                                           token::get_name(name).get());
1725                         self.session.span_err(import_directive.span, msg.as_slice());
1726                     } else {
1727                         let target = Target::new(containing_module.clone(),
1728                                                  name_bindings.clone(),
1729                                                  import_directive.shadowable);
1730                         dest_import_resolution.set_target_and_id(namespace,
1731                                                                  Some(target),
1732                                                                  id);
1733                     }
1734                 }
1735             };
1736             merge_child_item(ValueNS);
1737             merge_child_item(TypeNS);
1738         }
1739
1740         dest_import_resolution.is_public = is_public;
1741
1742         self.check_for_conflicts_between_imports_and_items(
1743             module_,
1744             dest_import_resolution,
1745             import_directive.span,
1746             name);
1747     }
1748
1749     /// Checks that imported names and items don't have the same name.
1750     fn check_for_conflicting_import(&mut self,
1751                                     target: &Option<Target>,
1752                                     import_span: Span,
1753                                     name: Name,
1754                                     namespace: Namespace) {
1755         if self.session.features.borrow().import_shadowing {
1756             return
1757         }
1758
1759         debug!("check_for_conflicting_import: {}; target exists: {}",
1760                token::get_name(name).get(),
1761                target.is_some());
1762
1763         match *target {
1764             Some(ref target) if target.shadowable != Shadowable::Always => {
1765                 let msg = format!("a {} named `{}` has already been imported \
1766                                    in this module",
1767                                   match namespace {
1768                                     TypeNS => "type",
1769                                     ValueNS => "value",
1770                                   },
1771                                   token::get_name(name).get());
1772                 self.session.span_err(import_span, &msg[]);
1773             }
1774             Some(_) | None => {}
1775         }
1776     }
1777
1778     /// Checks that an import is actually importable
1779     fn check_that_import_is_importable(&mut self,
1780                                        name_bindings: &NameBindings,
1781                                        import_span: Span,
1782                                        name: Name,
1783                                        namespace: Namespace) {
1784         if !name_bindings.defined_in_namespace_with(namespace, IMPORTABLE) {
1785             let msg = format!("`{}` is not directly importable",
1786                               token::get_name(name));
1787             self.session.span_err(import_span, &msg[]);
1788         }
1789     }
1790
1791     /// Checks that imported names and items don't have the same name.
1792     fn check_for_conflicts_between_imports_and_items(&mut self,
1793                                                      module: &Module,
1794                                                      import_resolution:
1795                                                      &ImportResolution,
1796                                                      import_span: Span,
1797                                                      name: Name) {
1798         if self.session.features.borrow().import_shadowing {
1799             return
1800         }
1801
1802         // First, check for conflicts between imports and `extern crate`s.
1803         if module.external_module_children
1804                  .borrow()
1805                  .contains_key(&name) {
1806             match import_resolution.type_target {
1807                 Some(ref target) if target.shadowable != Shadowable::Always => {
1808                     let msg = format!("import `{0}` conflicts with imported \
1809                                        crate in this module \
1810                                        (maybe you meant `use {0}::*`?)",
1811                                       token::get_name(name).get());
1812                     self.session.span_err(import_span, &msg[]);
1813                 }
1814                 Some(_) | None => {}
1815             }
1816         }
1817
1818         // Check for item conflicts.
1819         let children = module.children.borrow();
1820         let name_bindings = match children.get(&name) {
1821             None => {
1822                 // There can't be any conflicts.
1823                 return
1824             }
1825             Some(ref name_bindings) => (*name_bindings).clone(),
1826         };
1827
1828         match import_resolution.value_target {
1829             Some(ref target) if target.shadowable != Shadowable::Always => {
1830                 if let Some(ref value) = *name_bindings.value_def.borrow() {
1831                     let msg = format!("import `{}` conflicts with value \
1832                                        in this module",
1833                                       token::get_name(name).get());
1834                     self.session.span_err(import_span, &msg[]);
1835                     if let Some(span) = value.value_span {
1836                         self.session.span_note(span,
1837                                                "conflicting value here");
1838                     }
1839                 }
1840             }
1841             Some(_) | None => {}
1842         }
1843
1844         match import_resolution.type_target {
1845             Some(ref target) if target.shadowable != Shadowable::Always => {
1846                 if let Some(ref ty) = *name_bindings.type_def.borrow() {
1847                     match ty.module_def {
1848                         None => {
1849                             let msg = format!("import `{}` conflicts with type in \
1850                                                this module",
1851                                               token::get_name(name).get());
1852                             self.session.span_err(import_span, &msg[]);
1853                             if let Some(span) = ty.type_span {
1854                                 self.session.span_note(span,
1855                                                        "note conflicting type here")
1856                             }
1857                         }
1858                         Some(ref module_def) => {
1859                             match module_def.kind.get() {
1860                                 ImplModuleKind => {
1861                                     if let Some(span) = ty.type_span {
1862                                         let msg = format!("inherent implementations \
1863                                                            are only allowed on types \
1864                                                            defined in the current module");
1865                                         self.session.span_err(span, &msg[]);
1866                                         self.session.span_note(import_span,
1867                                                                "import from other module here")
1868                                     }
1869                                 }
1870                                 _ => {
1871                                     let msg = format!("import `{}` conflicts with existing \
1872                                                        submodule",
1873                                                       token::get_name(name).get());
1874                                     self.session.span_err(import_span, &msg[]);
1875                                     if let Some(span) = ty.type_span {
1876                                         self.session.span_note(span,
1877                                                                "note conflicting module here")
1878                                     }
1879                                 }
1880                             }
1881                         }
1882                     }
1883                 }
1884             }
1885             Some(_) | None => {}
1886         }
1887     }
1888
1889     /// Checks that the names of external crates don't collide with other
1890     /// external crates.
1891     fn check_for_conflicts_between_external_crates(&self,
1892                                                    module: &Module,
1893                                                    name: Name,
1894                                                    span: Span) {
1895         if self.session.features.borrow().import_shadowing {
1896             return
1897         }
1898
1899         if module.external_module_children.borrow().contains_key(&name) {
1900             self.session
1901                 .span_err(span,
1902                           &format!("an external crate named `{}` has already \
1903                                    been imported into this module",
1904                                   token::get_name(name).get())[]);
1905         }
1906     }
1907
1908     /// Checks that the names of items don't collide with external crates.
1909     fn check_for_conflicts_between_external_crates_and_items(&self,
1910                                                              module: &Module,
1911                                                              name: Name,
1912                                                              span: Span) {
1913         if self.session.features.borrow().import_shadowing {
1914             return
1915         }
1916
1917         if module.external_module_children.borrow().contains_key(&name) {
1918             self.session
1919                 .span_err(span,
1920                           &format!("the name `{}` conflicts with an external \
1921                                    crate that has been imported into this \
1922                                    module",
1923                                   token::get_name(name).get())[]);
1924         }
1925     }
1926
1927     /// Resolves the given module path from the given root `module_`.
1928     fn resolve_module_path_from_root(&mut self,
1929                                      module_: Rc<Module>,
1930                                      module_path: &[Name],
1931                                      index: uint,
1932                                      span: Span,
1933                                      name_search_type: NameSearchType,
1934                                      lp: LastPrivate)
1935                                 -> ResolveResult<(Rc<Module>, LastPrivate)> {
1936         fn search_parent_externals(needle: Name, module: &Rc<Module>)
1937                                 -> Option<Rc<Module>> {
1938             module.external_module_children.borrow()
1939                                             .get(&needle).cloned()
1940                                             .map(|_| module.clone())
1941                                             .or_else(|| {
1942                 match module.parent_link.clone() {
1943                     ModuleParentLink(parent, _) => {
1944                         search_parent_externals(needle,
1945                                                 &parent.upgrade().unwrap())
1946                     }
1947                    _ => None
1948                 }
1949             })
1950         }
1951
1952         let mut search_module = module_;
1953         let mut index = index;
1954         let module_path_len = module_path.len();
1955         let mut closest_private = lp;
1956
1957         // Resolve the module part of the path. This does not involve looking
1958         // upward though scope chains; we simply resolve names directly in
1959         // modules as we go.
1960         while index < module_path_len {
1961             let name = module_path[index];
1962             match self.resolve_name_in_module(search_module.clone(),
1963                                               name,
1964                                               TypeNS,
1965                                               name_search_type,
1966                                               false) {
1967                 Failed(None) => {
1968                     let segment_name = token::get_name(name);
1969                     let module_name = self.module_to_string(&*search_module);
1970                     let mut span = span;
1971                     let msg = if "???" == &module_name[] {
1972                         span.hi = span.lo + Pos::from_uint(segment_name.get().len());
1973
1974                         match search_parent_externals(name,
1975                                                      &self.current_module) {
1976                             Some(module) => {
1977                                 let path_str = self.names_to_string(module_path);
1978                                 let target_mod_str = self.module_to_string(&*module);
1979                                 let current_mod_str =
1980                                     self.module_to_string(&*self.current_module);
1981
1982                                 let prefix = if target_mod_str == current_mod_str {
1983                                     "self::".to_string()
1984                                 } else {
1985                                     format!("{}::", target_mod_str)
1986                                 };
1987
1988                                 format!("Did you mean `{}{}`?", prefix, path_str)
1989                             },
1990                             None => format!("Maybe a missing `extern crate {}`?",
1991                                             segment_name),
1992                         }
1993                     } else {
1994                         format!("Could not find `{}` in `{}`",
1995                                 segment_name,
1996                                 module_name)
1997                     };
1998
1999                     return Failed(Some((span, msg)));
2000                 }
2001                 Failed(err) => return Failed(err),
2002                 Indeterminate => {
2003                     debug!("(resolving module path for import) module \
2004                             resolution is indeterminate: {}",
2005                             token::get_name(name));
2006                     return Indeterminate;
2007                 }
2008                 Success((target, used_proxy)) => {
2009                     // Check to see whether there are type bindings, and, if
2010                     // so, whether there is a module within.
2011                     match *target.bindings.type_def.borrow() {
2012                         Some(ref type_def) => {
2013                             match type_def.module_def {
2014                                 None => {
2015                                     let msg = format!("Not a module `{}`",
2016                                                         token::get_name(name));
2017
2018                                     return Failed(Some((span, msg)));
2019                                 }
2020                                 Some(ref module_def) => {
2021                                     search_module = module_def.clone();
2022
2023                                     // track extern crates for unused_extern_crate lint
2024                                     if let Some(did) = module_def.def_id.get() {
2025                                         self.used_crates.insert(did.krate);
2026                                     }
2027
2028                                     // Keep track of the closest
2029                                     // private module used when
2030                                     // resolving this import chain.
2031                                     if !used_proxy && !search_module.is_public {
2032                                         if let Some(did) = search_module.def_id.get() {
2033                                             closest_private = LastMod(DependsOn(did));
2034                                         }
2035                                     }
2036                                 }
2037                             }
2038                         }
2039                         None => {
2040                             // There are no type bindings at all.
2041                             let msg = format!("Not a module `{}`",
2042                                               token::get_name(name));
2043                             return Failed(Some((span, msg)));
2044                         }
2045                     }
2046                 }
2047             }
2048
2049             index += 1;
2050         }
2051
2052         return Success((search_module, closest_private));
2053     }
2054
2055     /// Attempts to resolve the module part of an import directive or path
2056     /// rooted at the given module.
2057     ///
2058     /// On success, returns the resolved module, and the closest *private*
2059     /// module found to the destination when resolving this path.
2060     fn resolve_module_path(&mut self,
2061                            module_: Rc<Module>,
2062                            module_path: &[Name],
2063                            use_lexical_scope: UseLexicalScopeFlag,
2064                            span: Span,
2065                            name_search_type: NameSearchType)
2066                            -> ResolveResult<(Rc<Module>, LastPrivate)> {
2067         let module_path_len = module_path.len();
2068         assert!(module_path_len > 0);
2069
2070         debug!("(resolving module path for import) processing `{}` rooted at `{}`",
2071                self.names_to_string(module_path),
2072                self.module_to_string(&*module_));
2073
2074         // Resolve the module prefix, if any.
2075         let module_prefix_result = self.resolve_module_prefix(module_.clone(),
2076                                                               module_path);
2077
2078         let search_module;
2079         let start_index;
2080         let last_private;
2081         match module_prefix_result {
2082             Failed(None) => {
2083                 let mpath = self.names_to_string(module_path);
2084                 let mpath = &mpath[];
2085                 match mpath.rfind(':') {
2086                     Some(idx) => {
2087                         let msg = format!("Could not find `{}` in `{}`",
2088                                             // idx +- 1 to account for the
2089                                             // colons on either side
2090                                             &mpath[(idx + 1)..],
2091                                             &mpath[..(idx - 1)]);
2092                         return Failed(Some((span, msg)));
2093                     },
2094                     None => {
2095                         return Failed(None)
2096                     }
2097                 }
2098             }
2099             Failed(err) => return Failed(err),
2100             Indeterminate => {
2101                 debug!("(resolving module path for import) indeterminate; \
2102                         bailing");
2103                 return Indeterminate;
2104             }
2105             Success(NoPrefixFound) => {
2106                 // There was no prefix, so we're considering the first element
2107                 // of the path. How we handle this depends on whether we were
2108                 // instructed to use lexical scope or not.
2109                 match use_lexical_scope {
2110                     DontUseLexicalScope => {
2111                         // This is a crate-relative path. We will start the
2112                         // resolution process at index zero.
2113                         search_module = self.graph_root.get_module();
2114                         start_index = 0;
2115                         last_private = LastMod(AllPublic);
2116                     }
2117                     UseLexicalScope => {
2118                         // This is not a crate-relative path. We resolve the
2119                         // first component of the path in the current lexical
2120                         // scope and then proceed to resolve below that.
2121                         match self.resolve_module_in_lexical_scope(module_,
2122                                                                    module_path[0]) {
2123                             Failed(err) => return Failed(err),
2124                             Indeterminate => {
2125                                 debug!("(resolving module path for import) \
2126                                         indeterminate; bailing");
2127                                 return Indeterminate;
2128                             }
2129                             Success(containing_module) => {
2130                                 search_module = containing_module;
2131                                 start_index = 1;
2132                                 last_private = LastMod(AllPublic);
2133                             }
2134                         }
2135                     }
2136                 }
2137             }
2138             Success(PrefixFound(ref containing_module, index)) => {
2139                 search_module = containing_module.clone();
2140                 start_index = index;
2141                 last_private = LastMod(DependsOn(containing_module.def_id
2142                                                                   .get()
2143                                                                   .unwrap()));
2144             }
2145         }
2146
2147         self.resolve_module_path_from_root(search_module,
2148                                            module_path,
2149                                            start_index,
2150                                            span,
2151                                            name_search_type,
2152                                            last_private)
2153     }
2154
2155     /// Invariant: This must only be called during main resolution, not during
2156     /// import resolution.
2157     fn resolve_item_in_lexical_scope(&mut self,
2158                                      module_: Rc<Module>,
2159                                      name: Name,
2160                                      namespace: Namespace)
2161                                     -> ResolveResult<(Target, bool)> {
2162         debug!("(resolving item in lexical scope) resolving `{}` in \
2163                 namespace {:?} in `{}`",
2164                token::get_name(name),
2165                namespace,
2166                self.module_to_string(&*module_));
2167
2168         // The current module node is handled specially. First, check for
2169         // its immediate children.
2170         build_reduced_graph::populate_module_if_necessary(self, &module_);
2171
2172         match module_.children.borrow().get(&name) {
2173             Some(name_bindings)
2174                     if name_bindings.defined_in_namespace(namespace) => {
2175                 debug!("top name bindings succeeded");
2176                 return Success((Target::new(module_.clone(),
2177                                             name_bindings.clone(),
2178                                             Shadowable::Never),
2179                                false));
2180             }
2181             Some(_) | None => { /* Not found; continue. */ }
2182         }
2183
2184         // Now check for its import directives. We don't have to have resolved
2185         // all its imports in the usual way; this is because chains of
2186         // adjacent import statements are processed as though they mutated the
2187         // current scope.
2188         if let Some(import_resolution) = module_.import_resolutions.borrow().get(&name) {
2189             match (*import_resolution).target_for_namespace(namespace) {
2190                 None => {
2191                     // Not found; continue.
2192                     debug!("(resolving item in lexical scope) found \
2193                             import resolution, but not in namespace {:?}",
2194                            namespace);
2195                 }
2196                 Some(target) => {
2197                     debug!("(resolving item in lexical scope) using \
2198                             import resolution");
2199                     // track used imports and extern crates as well
2200                     let id = import_resolution.id(namespace);
2201                     self.used_imports.insert((id, namespace));
2202                     self.record_import_use(id, name);
2203                     if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
2204                          self.used_crates.insert(kid);
2205                     }
2206                     return Success((target, false));
2207                 }
2208             }
2209         }
2210
2211         // Search for external modules.
2212         if namespace == TypeNS {
2213             if let Some(module) = module_.external_module_children.borrow().get(&name).cloned() {
2214                 let name_bindings =
2215                     Rc::new(Resolver::create_name_bindings_from_module(module));
2216                 debug!("lower name bindings succeeded");
2217                 return Success((Target::new(module_,
2218                                             name_bindings,
2219                                             Shadowable::Never),
2220                                 false));
2221             }
2222         }
2223
2224         // Finally, proceed up the scope chain looking for parent modules.
2225         let mut search_module = module_;
2226         loop {
2227             // Go to the next parent.
2228             match search_module.parent_link.clone() {
2229                 NoParentLink => {
2230                     // No more parents. This module was unresolved.
2231                     debug!("(resolving item in lexical scope) unresolved \
2232                             module");
2233                     return Failed(None);
2234                 }
2235                 ModuleParentLink(parent_module_node, _) => {
2236                     match search_module.kind.get() {
2237                         NormalModuleKind => {
2238                             // We stop the search here.
2239                             debug!("(resolving item in lexical \
2240                                     scope) unresolved module: not \
2241                                     searching through module \
2242                                     parents");
2243                             return Failed(None);
2244                         }
2245                         TraitModuleKind |
2246                         ImplModuleKind |
2247                         EnumModuleKind |
2248                         TypeModuleKind |
2249                         AnonymousModuleKind => {
2250                             search_module = parent_module_node.upgrade().unwrap();
2251                         }
2252                     }
2253                 }
2254                 BlockParentLink(ref parent_module_node, _) => {
2255                     search_module = parent_module_node.upgrade().unwrap();
2256                 }
2257             }
2258
2259             // Resolve the name in the parent module.
2260             match self.resolve_name_in_module(search_module.clone(),
2261                                               name,
2262                                               namespace,
2263                                               PathSearch,
2264                                               true) {
2265                 Failed(Some((span, msg))) =>
2266                     self.resolve_error(span, &format!("failed to resolve. {}",
2267                                                      msg)[]),
2268                 Failed(None) => (), // Continue up the search chain.
2269                 Indeterminate => {
2270                     // We couldn't see through the higher scope because of an
2271                     // unresolved import higher up. Bail.
2272
2273                     debug!("(resolving item in lexical scope) indeterminate \
2274                             higher scope; bailing");
2275                     return Indeterminate;
2276                 }
2277                 Success((target, used_reexport)) => {
2278                     // We found the module.
2279                     debug!("(resolving item in lexical scope) found name \
2280                             in module, done");
2281                     return Success((target, used_reexport));
2282                 }
2283             }
2284         }
2285     }
2286
2287     /// Resolves a module name in the current lexical scope.
2288     fn resolve_module_in_lexical_scope(&mut self,
2289                                        module_: Rc<Module>,
2290                                        name: Name)
2291                                 -> ResolveResult<Rc<Module>> {
2292         // If this module is an anonymous module, resolve the item in the
2293         // lexical scope. Otherwise, resolve the item from the crate root.
2294         let resolve_result = self.resolve_item_in_lexical_scope(module_, name, TypeNS);
2295         match resolve_result {
2296             Success((target, _)) => {
2297                 let bindings = &*target.bindings;
2298                 match *bindings.type_def.borrow() {
2299                     Some(ref type_def) => {
2300                         match type_def.module_def {
2301                             None => {
2302                                 debug!("!!! (resolving module in lexical \
2303                                         scope) module wasn't actually a \
2304                                         module!");
2305                                 return Failed(None);
2306                             }
2307                             Some(ref module_def) => {
2308                                 return Success(module_def.clone());
2309                             }
2310                         }
2311                     }
2312                     None => {
2313                         debug!("!!! (resolving module in lexical scope) module
2314                                 wasn't actually a module!");
2315                         return Failed(None);
2316                     }
2317                 }
2318             }
2319             Indeterminate => {
2320                 debug!("(resolving module in lexical scope) indeterminate; \
2321                         bailing");
2322                 return Indeterminate;
2323             }
2324             Failed(err) => {
2325                 debug!("(resolving module in lexical scope) failed to resolve");
2326                 return Failed(err);
2327             }
2328         }
2329     }
2330
2331     /// Returns the nearest normal module parent of the given module.
2332     fn get_nearest_normal_module_parent(&mut self, module_: Rc<Module>)
2333                                             -> Option<Rc<Module>> {
2334         let mut module_ = module_;
2335         loop {
2336             match module_.parent_link.clone() {
2337                 NoParentLink => return None,
2338                 ModuleParentLink(new_module, _) |
2339                 BlockParentLink(new_module, _) => {
2340                     let new_module = new_module.upgrade().unwrap();
2341                     match new_module.kind.get() {
2342                         NormalModuleKind => return Some(new_module),
2343                         TraitModuleKind |
2344                         ImplModuleKind |
2345                         EnumModuleKind |
2346                         TypeModuleKind |
2347                         AnonymousModuleKind => module_ = new_module,
2348                     }
2349                 }
2350             }
2351         }
2352     }
2353
2354     /// Returns the nearest normal module parent of the given module, or the
2355     /// module itself if it is a normal module.
2356     fn get_nearest_normal_module_parent_or_self(&mut self, module_: Rc<Module>)
2357                                                 -> Rc<Module> {
2358         match module_.kind.get() {
2359             NormalModuleKind => return module_,
2360             TraitModuleKind |
2361             ImplModuleKind |
2362             EnumModuleKind |
2363             TypeModuleKind |
2364             AnonymousModuleKind => {
2365                 match self.get_nearest_normal_module_parent(module_.clone()) {
2366                     None => module_,
2367                     Some(new_module) => new_module
2368                 }
2369             }
2370         }
2371     }
2372
2373     /// Resolves a "module prefix". A module prefix is one or both of (a) `self::`;
2374     /// (b) some chain of `super::`.
2375     /// grammar: (SELF MOD_SEP ) ? (SUPER MOD_SEP) *
2376     fn resolve_module_prefix(&mut self,
2377                              module_: Rc<Module>,
2378                              module_path: &[Name])
2379                                  -> ResolveResult<ModulePrefixResult> {
2380         // Start at the current module if we see `self` or `super`, or at the
2381         // top of the crate otherwise.
2382         let mut containing_module;
2383         let mut i;
2384         let first_module_path_string = token::get_name(module_path[0]);
2385         if "self" == first_module_path_string.get() {
2386             containing_module =
2387                 self.get_nearest_normal_module_parent_or_self(module_);
2388             i = 1;
2389         } else if "super" == first_module_path_string.get() {
2390             containing_module =
2391                 self.get_nearest_normal_module_parent_or_self(module_);
2392             i = 0;  // We'll handle `super` below.
2393         } else {
2394             return Success(NoPrefixFound);
2395         }
2396
2397         // Now loop through all the `super`s we find.
2398         while i < module_path.len() {
2399             let string = token::get_name(module_path[i]);
2400             if "super" != string.get() {
2401                 break
2402             }
2403             debug!("(resolving module prefix) resolving `super` at {}",
2404                    self.module_to_string(&*containing_module));
2405             match self.get_nearest_normal_module_parent(containing_module) {
2406                 None => return Failed(None),
2407                 Some(new_module) => {
2408                     containing_module = new_module;
2409                     i += 1;
2410                 }
2411             }
2412         }
2413
2414         debug!("(resolving module prefix) finished resolving prefix at {}",
2415                self.module_to_string(&*containing_module));
2416
2417         return Success(PrefixFound(containing_module, i));
2418     }
2419
2420     /// Attempts to resolve the supplied name in the given module for the
2421     /// given namespace. If successful, returns the target corresponding to
2422     /// the name.
2423     ///
2424     /// The boolean returned on success is an indicator of whether this lookup
2425     /// passed through a public re-export proxy.
2426     fn resolve_name_in_module(&mut self,
2427                               module_: Rc<Module>,
2428                               name: Name,
2429                               namespace: Namespace,
2430                               name_search_type: NameSearchType,
2431                               allow_private_imports: bool)
2432                               -> ResolveResult<(Target, bool)> {
2433         debug!("(resolving name in module) resolving `{}` in `{}`",
2434                token::get_name(name).get(),
2435                self.module_to_string(&*module_));
2436
2437         // First, check the direct children of the module.
2438         build_reduced_graph::populate_module_if_necessary(self, &module_);
2439
2440         match module_.children.borrow().get(&name) {
2441             Some(name_bindings)
2442                     if name_bindings.defined_in_namespace(namespace) => {
2443                 debug!("(resolving name in module) found node as child");
2444                 return Success((Target::new(module_.clone(),
2445                                             name_bindings.clone(),
2446                                             Shadowable::Never),
2447                                false));
2448             }
2449             Some(_) | None => {
2450                 // Continue.
2451             }
2452         }
2453
2454         // Next, check the module's imports if necessary.
2455
2456         // If this is a search of all imports, we should be done with glob
2457         // resolution at this point.
2458         if name_search_type == PathSearch {
2459             assert_eq!(module_.glob_count.get(), 0);
2460         }
2461
2462         // Check the list of resolved imports.
2463         match module_.import_resolutions.borrow().get(&name) {
2464             Some(import_resolution) if allow_private_imports ||
2465                                        import_resolution.is_public => {
2466
2467                 if import_resolution.is_public &&
2468                         import_resolution.outstanding_references != 0 {
2469                     debug!("(resolving name in module) import \
2470                            unresolved; bailing out");
2471                     return Indeterminate;
2472                 }
2473                 match import_resolution.target_for_namespace(namespace) {
2474                     None => {
2475                         debug!("(resolving name in module) name found, \
2476                                 but not in namespace {:?}",
2477                                namespace);
2478                     }
2479                     Some(target) => {
2480                         debug!("(resolving name in module) resolved to \
2481                                 import");
2482                         // track used imports and extern crates as well
2483                         let id = import_resolution.id(namespace);
2484                         self.used_imports.insert((id, namespace));
2485                         self.record_import_use(id, name);
2486                         if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
2487                             self.used_crates.insert(kid);
2488                         }
2489                         return Success((target, true));
2490                     }
2491                 }
2492             }
2493             Some(..) | None => {} // Continue.
2494         }
2495
2496         // Finally, search through external children.
2497         if namespace == TypeNS {
2498             if let Some(module) = module_.external_module_children.borrow().get(&name).cloned() {
2499                 let name_bindings =
2500                     Rc::new(Resolver::create_name_bindings_from_module(module));
2501                 return Success((Target::new(module_,
2502                                             name_bindings,
2503                                             Shadowable::Never),
2504                                 false));
2505             }
2506         }
2507
2508         // We're out of luck.
2509         debug!("(resolving name in module) failed to resolve `{}`",
2510                token::get_name(name).get());
2511         return Failed(None);
2512     }
2513
2514     fn report_unresolved_imports(&mut self, module_: Rc<Module>) {
2515         let index = module_.resolved_import_count.get();
2516         let imports = module_.imports.borrow();
2517         let import_count = imports.len();
2518         if index != import_count {
2519             let sn = self.session
2520                          .codemap()
2521                          .span_to_snippet((*imports)[index].span)
2522                          .unwrap();
2523             if sn.contains("::") {
2524                 self.resolve_error((*imports)[index].span,
2525                                    "unresolved import");
2526             } else {
2527                 let err = format!("unresolved import (maybe you meant `{}::*`?)",
2528                                   sn);
2529                 self.resolve_error((*imports)[index].span, &err[]);
2530             }
2531         }
2532
2533         // Descend into children and anonymous children.
2534         build_reduced_graph::populate_module_if_necessary(self, &module_);
2535
2536         for (_, child_node) in module_.children.borrow().iter() {
2537             match child_node.get_module_if_available() {
2538                 None => {
2539                     // Continue.
2540                 }
2541                 Some(child_module) => {
2542                     self.report_unresolved_imports(child_module);
2543                 }
2544             }
2545         }
2546
2547         for (_, module_) in module_.anonymous_children.borrow().iter() {
2548             self.report_unresolved_imports(module_.clone());
2549         }
2550     }
2551
2552     // AST resolution
2553     //
2554     // We maintain a list of value ribs and type ribs.
2555     //
2556     // Simultaneously, we keep track of the current position in the module
2557     // graph in the `current_module` pointer. When we go to resolve a name in
2558     // the value or type namespaces, we first look through all the ribs and
2559     // then query the module graph. When we resolve a name in the module
2560     // namespace, we can skip all the ribs (since nested modules are not
2561     // allowed within blocks in Rust) and jump straight to the current module
2562     // graph node.
2563     //
2564     // Named implementations are handled separately. When we find a method
2565     // call, we consult the module node to find all of the implementations in
2566     // scope. This information is lazily cached in the module node. We then
2567     // generate a fake "implementation scope" containing all the
2568     // implementations thus found, for compatibility with old resolve pass.
2569
2570     fn with_scope<F>(&mut self, name: Option<Name>, f: F) where
2571         F: FnOnce(&mut Resolver),
2572     {
2573         let orig_module = self.current_module.clone();
2574
2575         // Move down in the graph.
2576         match name {
2577             None => {
2578                 // Nothing to do.
2579             }
2580             Some(name) => {
2581                 build_reduced_graph::populate_module_if_necessary(self, &orig_module);
2582
2583                 match orig_module.children.borrow().get(&name) {
2584                     None => {
2585                         debug!("!!! (with scope) didn't find `{}` in `{}`",
2586                                token::get_name(name),
2587                                self.module_to_string(&*orig_module));
2588                     }
2589                     Some(name_bindings) => {
2590                         match (*name_bindings).get_module_if_available() {
2591                             None => {
2592                                 debug!("!!! (with scope) didn't find module \
2593                                         for `{}` in `{}`",
2594                                        token::get_name(name),
2595                                        self.module_to_string(&*orig_module));
2596                             }
2597                             Some(module_) => {
2598                                 self.current_module = module_;
2599                             }
2600                         }
2601                     }
2602                 }
2603             }
2604         }
2605
2606         f(self);
2607
2608         self.current_module = orig_module;
2609     }
2610
2611     /// Wraps the given definition in the appropriate number of `DefUpvar`
2612     /// wrappers.
2613     fn upvarify(&self,
2614                 ribs: &[Rib],
2615                 def_like: DefLike,
2616                 span: Span)
2617                 -> Option<DefLike> {
2618         match def_like {
2619             DlDef(d @ DefUpvar(..)) => {
2620                 self.session.span_bug(span,
2621                     &format!("unexpected {:?} in bindings", d)[])
2622             }
2623             DlDef(d @ DefLocal(_)) => {
2624                 let node_id = d.def_id().node;
2625                 let mut def = d;
2626                 let mut last_proc_body_id = ast::DUMMY_NODE_ID;
2627                 for rib in ribs.iter() {
2628                     match rib.kind {
2629                         NormalRibKind => {
2630                             // Nothing to do. Continue.
2631                         }
2632                         ClosureRibKind(function_id, maybe_proc_body) => {
2633                             let prev_def = def;
2634                             if maybe_proc_body != ast::DUMMY_NODE_ID {
2635                                 last_proc_body_id = maybe_proc_body;
2636                             }
2637                             def = DefUpvar(node_id, function_id, last_proc_body_id);
2638
2639                             let mut seen = self.freevars_seen.borrow_mut();
2640                             let seen = match seen.entry(function_id) {
2641                                 Occupied(v) => v.into_mut(),
2642                                 Vacant(v) => v.insert(NodeSet()),
2643                             };
2644                             if seen.contains(&node_id) {
2645                                 continue;
2646                             }
2647                             match self.freevars.borrow_mut().entry(function_id) {
2648                                 Occupied(v) => v.into_mut(),
2649                                 Vacant(v) => v.insert(vec![]),
2650                             }.push(Freevar { def: prev_def, span: span });
2651                             seen.insert(node_id);
2652                         }
2653                         MethodRibKind(item_id, _) => {
2654                             // If the def is a ty param, and came from the parent
2655                             // item, it's ok
2656                             match def {
2657                                 DefTyParam(_, _, did, _) if {
2658                                     self.def_map.borrow().get(&did.node).cloned()
2659                                         == Some(DefTyParamBinder(item_id))
2660                                 } => {} // ok
2661                                 DefSelfTy(did) if did == item_id => {} // ok
2662                                 _ => {
2663                                     // This was an attempt to access an upvar inside a
2664                                     // named function item. This is not allowed, so we
2665                                     // report an error.
2666
2667                                     self.resolve_error(
2668                                         span,
2669                                         "can't capture dynamic environment in a fn item; \
2670                                         use the || { ... } closure form instead");
2671
2672                                     return None;
2673                                 }
2674                             }
2675                         }
2676                         ItemRibKind => {
2677                             // This was an attempt to access an upvar inside a
2678                             // named function item. This is not allowed, so we
2679                             // report an error.
2680
2681                             self.resolve_error(
2682                                 span,
2683                                 "can't capture dynamic environment in a fn item; \
2684                                 use the || { ... } closure form instead");
2685
2686                             return None;
2687                         }
2688                         ConstantItemRibKind => {
2689                             // Still doesn't deal with upvars
2690                             self.resolve_error(span,
2691                                                "attempt to use a non-constant \
2692                                                 value in a constant");
2693
2694                         }
2695                     }
2696                 }
2697                 Some(DlDef(def))
2698             }
2699             DlDef(def @ DefTyParam(..)) |
2700             DlDef(def @ DefSelfTy(..)) => {
2701                 for rib in ribs.iter() {
2702                     match rib.kind {
2703                         NormalRibKind | ClosureRibKind(..) => {
2704                             // Nothing to do. Continue.
2705                         }
2706                         MethodRibKind(item_id, _) => {
2707                             // If the def is a ty param, and came from the parent
2708                             // item, it's ok
2709                             match def {
2710                                 DefTyParam(_, _, did, _) if {
2711                                     self.def_map.borrow().get(&did.node).cloned()
2712                                         == Some(DefTyParamBinder(item_id))
2713                                 } => {} // ok
2714                                 DefSelfTy(did) if did == item_id => {} // ok
2715
2716                                 _ => {
2717                                     // This was an attempt to use a type parameter outside
2718                                     // its scope.
2719
2720                                     self.resolve_error(span,
2721                                                         "can't use type parameters from \
2722                                                         outer function; try using a local \
2723                                                         type parameter instead");
2724
2725                                     return None;
2726                                 }
2727                             }
2728                         }
2729                         ItemRibKind => {
2730                             // This was an attempt to use a type parameter outside
2731                             // its scope.
2732
2733                             self.resolve_error(span,
2734                                                "can't use type parameters from \
2735                                                 outer function; try using a local \
2736                                                 type parameter instead");
2737
2738                             return None;
2739                         }
2740                         ConstantItemRibKind => {
2741                             // see #9186
2742                             self.resolve_error(span,
2743                                                "cannot use an outer type \
2744                                                 parameter in this context");
2745
2746                         }
2747                     }
2748                 }
2749                 Some(DlDef(def))
2750             }
2751             _ => Some(def_like)
2752         }
2753     }
2754
2755     /// Searches the current set of local scopes and
2756     /// applies translations for closures.
2757     fn search_ribs(&self,
2758                    ribs: &[Rib],
2759                    name: Name,
2760                    span: Span)
2761                    -> Option<DefLike> {
2762         // FIXME #4950: Try caching?
2763
2764         for (i, rib) in ribs.iter().enumerate().rev() {
2765             match rib.bindings.get(&name).cloned() {
2766                 Some(def_like) => {
2767                     return self.upvarify(&ribs[(i + 1)..], def_like, span);
2768                 }
2769                 None => {
2770                     // Continue.
2771                 }
2772             }
2773         }
2774
2775         None
2776     }
2777
2778     /// Searches the current set of local scopes for labels.
2779     /// Stops after meeting a closure.
2780     fn search_label(&self, name: Name) -> Option<DefLike> {
2781         for rib in self.label_ribs.iter().rev() {
2782             match rib.kind {
2783                 NormalRibKind => {
2784                     // Continue
2785                 }
2786                 _ => {
2787                     // Do not resolve labels across function boundary
2788                     return None
2789                 }
2790             }
2791             let result = rib.bindings.get(&name).cloned();
2792             if result.is_some() {
2793                 return result
2794             }
2795         }
2796         None
2797     }
2798
2799     fn resolve_crate(&mut self, krate: &ast::Crate) {
2800         debug!("(resolving crate) starting");
2801
2802         visit::walk_crate(self, krate);
2803     }
2804
2805     fn resolve_item(&mut self, item: &Item) {
2806         let name = item.ident.name;
2807
2808         debug!("(resolving item) resolving {}",
2809                token::get_name(name));
2810
2811         match item.node {
2812
2813             // enum item: resolve all the variants' discrs,
2814             // then resolve the ty params
2815             ItemEnum(ref enum_def, ref generics) => {
2816                 for variant in (*enum_def).variants.iter() {
2817                     for dis_expr in variant.node.disr_expr.iter() {
2818                         // resolve the discriminator expr
2819                         // as a constant
2820                         self.with_constant_rib(|this| {
2821                             this.resolve_expr(&**dis_expr);
2822                         });
2823                     }
2824                 }
2825
2826                 // n.b. the discr expr gets visited twice.
2827                 // but maybe it's okay since the first time will signal an
2828                 // error if there is one? -- tjc
2829                 self.with_type_parameter_rib(HasTypeParameters(generics,
2830                                                                TypeSpace,
2831                                                                item.id,
2832                                                                ItemRibKind),
2833                                              |this| {
2834                     this.resolve_type_parameters(&generics.ty_params);
2835                     this.resolve_where_clause(&generics.where_clause);
2836                     visit::walk_item(this, item);
2837                 });
2838             }
2839
2840             ItemTy(_, ref generics) => {
2841                 self.with_type_parameter_rib(HasTypeParameters(generics,
2842                                                                TypeSpace,
2843                                                                item.id,
2844                                                                ItemRibKind),
2845                                              |this| {
2846                     this.resolve_type_parameters(&generics.ty_params);
2847                     visit::walk_item(this, item);
2848                 });
2849             }
2850
2851             ItemImpl(_, _,
2852                      ref generics,
2853                      ref implemented_traits,
2854                      ref self_type,
2855                      ref impl_items) => {
2856                 self.resolve_implementation(item.id,
2857                                             generics,
2858                                             implemented_traits,
2859                                             &**self_type,
2860                                             &impl_items[]);
2861             }
2862
2863             ItemTrait(_, ref generics, ref bounds, ref trait_items) => {
2864                 // Create a new rib for the self type.
2865                 let mut self_type_rib = Rib::new(ItemRibKind);
2866
2867                 // plain insert (no renaming, types are not currently hygienic....)
2868                 let name = self.type_self_name;
2869                 self_type_rib.bindings.insert(name, DlDef(DefSelfTy(item.id)));
2870                 self.type_ribs.push(self_type_rib);
2871
2872                 // Create a new rib for the trait-wide type parameters.
2873                 self.with_type_parameter_rib(HasTypeParameters(generics,
2874                                                                TypeSpace,
2875                                                                item.id,
2876                                                                NormalRibKind),
2877                                              |this| {
2878                     this.resolve_type_parameters(&generics.ty_params);
2879                     this.resolve_where_clause(&generics.where_clause);
2880
2881                     this.resolve_type_parameter_bounds(item.id, bounds,
2882                                                        TraitDerivation);
2883
2884                     for trait_item in (*trait_items).iter() {
2885                         // Create a new rib for the trait_item-specific type
2886                         // parameters.
2887                         //
2888                         // FIXME #4951: Do we need a node ID here?
2889
2890                         match *trait_item {
2891                           ast::RequiredMethod(ref ty_m) => {
2892                             this.with_type_parameter_rib
2893                                 (HasTypeParameters(&ty_m.generics,
2894                                                    FnSpace,
2895                                                    item.id,
2896                                         MethodRibKind(item.id, RequiredMethod)),
2897                                  |this| {
2898
2899                                 // Resolve the method-specific type
2900                                 // parameters.
2901                                 this.resolve_type_parameters(
2902                                     &ty_m.generics.ty_params);
2903                                 this.resolve_where_clause(&ty_m.generics
2904                                                                .where_clause);
2905
2906                                 for argument in ty_m.decl.inputs.iter() {
2907                                     this.resolve_type(&*argument.ty);
2908                                 }
2909
2910                                 if let SelfExplicit(ref typ, _) = ty_m.explicit_self.node {
2911                                     this.resolve_type(&**typ)
2912                                 }
2913
2914                                 if let ast::Return(ref ret_ty) = ty_m.decl.output {
2915                                     this.resolve_type(&**ret_ty);
2916                                 }
2917                             });
2918                           }
2919                           ast::ProvidedMethod(ref m) => {
2920                               this.resolve_method(MethodRibKind(item.id,
2921                                                                 ProvidedMethod(m.id)),
2922                                                   &**m)
2923                           }
2924                           ast::TypeTraitItem(ref data) => {
2925                               this.resolve_type_parameter(&data.ty_param);
2926                               visit::walk_trait_item(this, trait_item);
2927                           }
2928                         }
2929                     }
2930                 });
2931
2932                 self.type_ribs.pop();
2933             }
2934
2935             ItemStruct(ref struct_def, ref generics) => {
2936                 self.resolve_struct(item.id,
2937                                     generics,
2938                                     &struct_def.fields[]);
2939             }
2940
2941             ItemMod(ref module_) => {
2942                 self.with_scope(Some(name), |this| {
2943                     this.resolve_module(module_, item.span, name,
2944                                         item.id);
2945                 });
2946             }
2947
2948             ItemForeignMod(ref foreign_module) => {
2949                 self.with_scope(Some(name), |this| {
2950                     for foreign_item in foreign_module.items.iter() {
2951                         match foreign_item.node {
2952                             ForeignItemFn(_, ref generics) => {
2953                                 this.with_type_parameter_rib(
2954                                     HasTypeParameters(
2955                                         generics, FnSpace, foreign_item.id,
2956                                         ItemRibKind),
2957                                     |this| {
2958                                         this.resolve_type_parameters(&generics.ty_params);
2959                                         this.resolve_where_clause(&generics.where_clause);
2960                                         visit::walk_foreign_item(this, &**foreign_item)
2961                                     });
2962                             }
2963                             ForeignItemStatic(..) => {
2964                                 visit::walk_foreign_item(this,
2965                                                          &**foreign_item);
2966                             }
2967                         }
2968                     }
2969                 });
2970             }
2971
2972             ItemFn(ref fn_decl, _, _, ref generics, ref block) => {
2973                 self.resolve_function(ItemRibKind,
2974                                       Some(&**fn_decl),
2975                                       HasTypeParameters
2976                                         (generics,
2977                                          FnSpace,
2978                                          item.id,
2979                                          ItemRibKind),
2980                                       &**block);
2981             }
2982
2983             ItemConst(..) | ItemStatic(..) => {
2984                 self.with_constant_rib(|this| {
2985                     visit::walk_item(this, item);
2986                 });
2987             }
2988
2989            ItemMac(..) => {
2990                 // do nothing, these are just around to be encoded
2991            }
2992         }
2993     }
2994
2995     fn with_type_parameter_rib<F>(&mut self, type_parameters: TypeParameters, f: F) where
2996         F: FnOnce(&mut Resolver),
2997     {
2998         match type_parameters {
2999             HasTypeParameters(generics, space, node_id, rib_kind) => {
3000                 let mut function_type_rib = Rib::new(rib_kind);
3001                 let mut seen_bindings = HashSet::new();
3002                 for (index, type_parameter) in generics.ty_params.iter().enumerate() {
3003                     let name = type_parameter.ident.name;
3004                     debug!("with_type_parameter_rib: {} {}", node_id,
3005                            type_parameter.id);
3006
3007                     if seen_bindings.contains(&name) {
3008                         self.resolve_error(type_parameter.span,
3009                                            &format!("the name `{}` is already \
3010                                                     used for a type \
3011                                                     parameter in this type \
3012                                                     parameter list",
3013                                                    token::get_name(
3014                                                        name))[])
3015                     }
3016                     seen_bindings.insert(name);
3017
3018                     let def_like = DlDef(DefTyParam(space,
3019                                                     index as u32,
3020                                                     local_def(type_parameter.id),
3021                                                     name));
3022                     // Associate this type parameter with
3023                     // the item that bound it
3024                     self.record_def(type_parameter.id,
3025                                     (DefTyParamBinder(node_id), LastMod(AllPublic)));
3026                     // plain insert (no renaming)
3027                     function_type_rib.bindings.insert(name, def_like);
3028                 }
3029                 self.type_ribs.push(function_type_rib);
3030             }
3031
3032             NoTypeParameters => {
3033                 // Nothing to do.
3034             }
3035         }
3036
3037         f(self);
3038
3039         match type_parameters {
3040             HasTypeParameters(..) => { self.type_ribs.pop(); }
3041             NoTypeParameters => { }
3042         }
3043     }
3044
3045     fn with_label_rib<F>(&mut self, f: F) where
3046         F: FnOnce(&mut Resolver),
3047     {
3048         self.label_ribs.push(Rib::new(NormalRibKind));
3049         f(self);
3050         self.label_ribs.pop();
3051     }
3052
3053     fn with_constant_rib<F>(&mut self, f: F) where
3054         F: FnOnce(&mut Resolver),
3055     {
3056         self.value_ribs.push(Rib::new(ConstantItemRibKind));
3057         self.type_ribs.push(Rib::new(ConstantItemRibKind));
3058         f(self);
3059         self.type_ribs.pop();
3060         self.value_ribs.pop();
3061     }
3062
3063     fn resolve_function(&mut self,
3064                         rib_kind: RibKind,
3065                         optional_declaration: Option<&FnDecl>,
3066                         type_parameters: TypeParameters,
3067                         block: &Block) {
3068         // Create a value rib for the function.
3069         let function_value_rib = Rib::new(rib_kind);
3070         self.value_ribs.push(function_value_rib);
3071
3072         // Create a label rib for the function.
3073         let function_label_rib = Rib::new(rib_kind);
3074         self.label_ribs.push(function_label_rib);
3075
3076         // If this function has type parameters, add them now.
3077         self.with_type_parameter_rib(type_parameters, |this| {
3078             // Resolve the type parameters.
3079             match type_parameters {
3080                 NoTypeParameters => {
3081                     // Continue.
3082                 }
3083                 HasTypeParameters(ref generics, _, _, _) => {
3084                     this.resolve_type_parameters(&generics.ty_params);
3085                     this.resolve_where_clause(&generics.where_clause);
3086                 }
3087             }
3088
3089             // Add each argument to the rib.
3090             match optional_declaration {
3091                 None => {
3092                     // Nothing to do.
3093                 }
3094                 Some(declaration) => {
3095                     let mut bindings_list = HashMap::new();
3096                     for argument in declaration.inputs.iter() {
3097                         this.resolve_pattern(&*argument.pat,
3098                                              ArgumentIrrefutableMode,
3099                                              &mut bindings_list);
3100
3101                         this.resolve_type(&*argument.ty);
3102
3103                         debug!("(resolving function) recorded argument");
3104                     }
3105
3106                     if let ast::Return(ref ret_ty) = declaration.output {
3107                         this.resolve_type(&**ret_ty);
3108                     }
3109                 }
3110             }
3111
3112             // Resolve the function body.
3113             this.resolve_block(&*block);
3114
3115             debug!("(resolving function) leaving function");
3116         });
3117
3118         self.label_ribs.pop();
3119         self.value_ribs.pop();
3120     }
3121
3122     fn resolve_type_parameters(&mut self,
3123                                type_parameters: &OwnedSlice<TyParam>) {
3124         for type_parameter in type_parameters.iter() {
3125             self.resolve_type_parameter(type_parameter);
3126         }
3127     }
3128
3129     fn resolve_type_parameter(&mut self,
3130                               type_parameter: &TyParam) {
3131         for bound in type_parameter.bounds.iter() {
3132             self.resolve_type_parameter_bound(type_parameter.id, bound,
3133                                               TraitBoundingTypeParameter);
3134         }
3135         match type_parameter.default {
3136             Some(ref ty) => self.resolve_type(&**ty),
3137             None => {}
3138         }
3139     }
3140
3141     fn resolve_type_parameter_bounds(&mut self,
3142                                      id: NodeId,
3143                                      type_parameter_bounds: &OwnedSlice<TyParamBound>,
3144                                      reference_type: TraitReferenceType) {
3145         for type_parameter_bound in type_parameter_bounds.iter() {
3146             self.resolve_type_parameter_bound(id, type_parameter_bound,
3147                                               reference_type);
3148         }
3149     }
3150
3151     fn resolve_type_parameter_bound(&mut self,
3152                                     id: NodeId,
3153                                     type_parameter_bound: &TyParamBound,
3154                                     reference_type: TraitReferenceType) {
3155         match *type_parameter_bound {
3156             TraitTyParamBound(ref tref, _) => {
3157                 self.resolve_poly_trait_reference(id, tref, reference_type)
3158             }
3159             RegionTyParamBound(..) => {}
3160         }
3161     }
3162
3163     fn resolve_poly_trait_reference(&mut self,
3164                                     id: NodeId,
3165                                     poly_trait_reference: &PolyTraitRef,
3166                                     reference_type: TraitReferenceType) {
3167         self.resolve_trait_reference(id, &poly_trait_reference.trait_ref, reference_type)
3168     }
3169
3170     fn resolve_trait_reference(&mut self,
3171                                id: NodeId,
3172                                trait_reference: &TraitRef,
3173                                reference_type: TraitReferenceType) {
3174         match self.resolve_path(id, &trait_reference.path, TypeNS, true) {
3175             None => {
3176                 let path_str = self.path_names_to_string(&trait_reference.path);
3177                 let usage_str = match reference_type {
3178                     TraitBoundingTypeParameter => "bound type parameter with",
3179                     TraitImplementation        => "implement",
3180                     TraitDerivation            => "derive",
3181                     TraitObject                => "reference",
3182                     TraitQPath                 => "extract an associated item from",
3183                 };
3184
3185                 let msg = format!("attempt to {} a nonexistent trait `{}`", usage_str, path_str);
3186                 self.resolve_error(trait_reference.path.span, &msg[]);
3187             }
3188             Some(def) => {
3189                 match def {
3190                     (DefTrait(_), _) => {
3191                         debug!("(resolving trait) found trait def: {:?}", def);
3192                         self.record_def(trait_reference.ref_id, def);
3193                     }
3194                     (def, _) => {
3195                         self.resolve_error(trait_reference.path.span,
3196                                            &format!("`{}` is not a trait",
3197                                                    self.path_names_to_string(
3198                                                        &trait_reference.path))[]);
3199
3200                         // If it's a typedef, give a note
3201                         if let DefTy(..) = def {
3202                             self.session.span_note(
3203                                 trait_reference.path.span,
3204                                 &format!("`type` aliases cannot be used for traits")
3205                                 []);
3206                         }
3207                     }
3208                 }
3209             }
3210         }
3211     }
3212
3213     fn resolve_where_clause(&mut self, where_clause: &ast::WhereClause) {
3214         for predicate in where_clause.predicates.iter() {
3215             match predicate {
3216                 &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
3217                     self.resolve_type(&*bound_pred.bounded_ty);
3218
3219                     for bound in bound_pred.bounds.iter() {
3220                         self.resolve_type_parameter_bound(bound_pred.bounded_ty.id, bound,
3221                                                           TraitBoundingTypeParameter);
3222                     }
3223                 }
3224                 &ast::WherePredicate::RegionPredicate(_) => {}
3225                 &ast::WherePredicate::EqPredicate(ref eq_pred) => {
3226                     match self.resolve_path(eq_pred.id, &eq_pred.path, TypeNS, true) {
3227                         Some((def @ DefTyParam(..), last_private)) => {
3228                             self.record_def(eq_pred.id, (def, last_private));
3229                         }
3230                         _ => {
3231                             self.resolve_error(eq_pred.path.span,
3232                                                "undeclared associated type");
3233                         }
3234                     }
3235
3236                     self.resolve_type(&*eq_pred.ty);
3237                 }
3238             }
3239         }
3240     }
3241
3242     fn resolve_struct(&mut self,
3243                       id: NodeId,
3244                       generics: &Generics,
3245                       fields: &[StructField]) {
3246         // If applicable, create a rib for the type parameters.
3247         self.with_type_parameter_rib(HasTypeParameters(generics,
3248                                                        TypeSpace,
3249                                                        id,
3250                                                        ItemRibKind),
3251                                      |this| {
3252             // Resolve the type parameters.
3253             this.resolve_type_parameters(&generics.ty_params);
3254             this.resolve_where_clause(&generics.where_clause);
3255
3256             // Resolve fields.
3257             for field in fields.iter() {
3258                 this.resolve_type(&*field.node.ty);
3259             }
3260         });
3261     }
3262
3263     // Does this really need to take a RibKind or is it always going
3264     // to be NormalRibKind?
3265     fn resolve_method(&mut self,
3266                       rib_kind: RibKind,
3267                       method: &ast::Method) {
3268         let method_generics = method.pe_generics();
3269         let type_parameters = HasTypeParameters(method_generics,
3270                                                 FnSpace,
3271                                                 method.id,
3272                                                 rib_kind);
3273
3274         if let SelfExplicit(ref typ, _) = method.pe_explicit_self().node {
3275             self.resolve_type(&**typ);
3276         }
3277
3278         self.resolve_function(rib_kind,
3279                               Some(method.pe_fn_decl()),
3280                               type_parameters,
3281                               method.pe_body());
3282     }
3283
3284     fn with_current_self_type<T, F>(&mut self, self_type: &Ty, f: F) -> T where
3285         F: FnOnce(&mut Resolver) -> T,
3286     {
3287         // Handle nested impls (inside fn bodies)
3288         let previous_value = replace(&mut self.current_self_type, Some(self_type.clone()));
3289         let result = f(self);
3290         self.current_self_type = previous_value;
3291         result
3292     }
3293
3294     fn with_optional_trait_ref<T, F>(&mut self, id: NodeId,
3295                                      opt_trait_ref: &Option<TraitRef>,
3296                                      f: F) -> T where
3297         F: FnOnce(&mut Resolver) -> T,
3298     {
3299         let new_val = match *opt_trait_ref {
3300             Some(ref trait_ref) => {
3301                 self.resolve_trait_reference(id, trait_ref, TraitImplementation);
3302
3303                 match self.def_map.borrow().get(&trait_ref.ref_id) {
3304                     Some(def) => {
3305                         let did = def.def_id();
3306                         Some((did, trait_ref.clone()))
3307                     }
3308                     None => None
3309                 }
3310             }
3311             None => None
3312         };
3313         let original_trait_ref = replace(&mut self.current_trait_ref, new_val);
3314         let result = f(self);
3315         self.current_trait_ref = original_trait_ref;
3316         result
3317     }
3318
3319     fn resolve_implementation(&mut self,
3320                               id: NodeId,
3321                               generics: &Generics,
3322                               opt_trait_reference: &Option<TraitRef>,
3323                               self_type: &Ty,
3324                               impl_items: &[ImplItem]) {
3325         // If applicable, create a rib for the type parameters.
3326         self.with_type_parameter_rib(HasTypeParameters(generics,
3327                                                        TypeSpace,
3328                                                        id,
3329                                                        NormalRibKind),
3330                                      |this| {
3331             // Resolve the type parameters.
3332             this.resolve_type_parameters(&generics.ty_params);
3333             this.resolve_where_clause(&generics.where_clause);
3334
3335             // Resolve the trait reference, if necessary.
3336             this.with_optional_trait_ref(id, opt_trait_reference, |this| {
3337                 // Resolve the self type.
3338                 this.resolve_type(self_type);
3339
3340                 this.with_current_self_type(self_type, |this| {
3341                     for impl_item in impl_items.iter() {
3342                         match *impl_item {
3343                             MethodImplItem(ref method) => {
3344                                 // If this is a trait impl, ensure the method
3345                                 // exists in trait
3346                                 this.check_trait_item(method.pe_ident().name,
3347                                                       method.span);
3348
3349                                 // We also need a new scope for the method-
3350                                 // specific type parameters.
3351                                 this.resolve_method(
3352                                     MethodRibKind(id, ProvidedMethod(method.id)),
3353                                     &**method);
3354                             }
3355                             TypeImplItem(ref typedef) => {
3356                                 // If this is a trait impl, ensure the method
3357                                 // exists in trait
3358                                 this.check_trait_item(typedef.ident.name,
3359                                                       typedef.span);
3360
3361                                 this.resolve_type(&*typedef.typ);
3362                             }
3363                         }
3364                     }
3365                 });
3366             });
3367         });
3368
3369         // Check that the current type is indeed a type, if we have an anonymous impl
3370         if opt_trait_reference.is_none() {
3371             match self_type.node {
3372                 // TyPath is the only thing that we handled in `build_reduced_graph_for_item`,
3373                 // where we created a module with the name of the type in order to implement
3374                 // an anonymous trait. In the case that the path does not resolve to an actual
3375                 // type, the result will be that the type name resolves to a module but not
3376                 // a type (shadowing any imported modules or types with this name), leading
3377                 // to weird user-visible bugs. So we ward this off here. See #15060.
3378                 TyPath(ref path, path_id) => {
3379                     match self.def_map.borrow().get(&path_id) {
3380                         // FIXME: should we catch other options and give more precise errors?
3381                         Some(&DefMod(_)) => {
3382                             self.resolve_error(path.span, "inherent implementations are not \
3383                                                            allowed for types not defined in \
3384                                                            the current module");
3385                         }
3386                         _ => {}
3387                     }
3388                 }
3389                 _ => { }
3390             }
3391         }
3392     }
3393
3394     fn check_trait_item(&self, name: Name, span: Span) {
3395         // If there is a TraitRef in scope for an impl, then the method must be in the trait.
3396         for &(did, ref trait_ref) in self.current_trait_ref.iter() {
3397             if self.trait_item_map.get(&(name, did)).is_none() {
3398                 let path_str = self.path_names_to_string(&trait_ref.path);
3399                 self.resolve_error(span,
3400                                     &format!("method `{}` is not a member of trait `{}`",
3401                                             token::get_name(name),
3402                                             path_str)[]);
3403             }
3404         }
3405     }
3406
3407     fn resolve_module(&mut self, module: &Mod, _span: Span,
3408                       _name: Name, id: NodeId) {
3409         // Write the implementations in scope into the module metadata.
3410         debug!("(resolving module) resolving module ID {}", id);
3411         visit::walk_mod(self, module);
3412     }
3413
3414     fn resolve_local(&mut self, local: &Local) {
3415         // Resolve the type.
3416         if let Some(ref ty) = local.ty {
3417             self.resolve_type(&**ty);
3418         }
3419
3420         // Resolve the initializer, if necessary.
3421         match local.init {
3422             None => {
3423                 // Nothing to do.
3424             }
3425             Some(ref initializer) => {
3426                 self.resolve_expr(&**initializer);
3427             }
3428         }
3429
3430         // Resolve the pattern.
3431         let mut bindings_list = HashMap::new();
3432         self.resolve_pattern(&*local.pat,
3433                              LocalIrrefutableMode,
3434                              &mut bindings_list);
3435     }
3436
3437     // build a map from pattern identifiers to binding-info's.
3438     // this is done hygienically. This could arise for a macro
3439     // that expands into an or-pattern where one 'x' was from the
3440     // user and one 'x' came from the macro.
3441     fn binding_mode_map(&mut self, pat: &Pat) -> BindingMap {
3442         let mut result = HashMap::new();
3443         pat_bindings(&self.def_map, pat, |binding_mode, _id, sp, path1| {
3444             let name = mtwt::resolve(path1.node);
3445             result.insert(name, BindingInfo {
3446                 span: sp,
3447                 binding_mode: binding_mode
3448             });
3449         });
3450         return result;
3451     }
3452
3453     // check that all of the arms in an or-pattern have exactly the
3454     // same set of bindings, with the same binding modes for each.
3455     fn check_consistent_bindings(&mut self, arm: &Arm) {
3456         if arm.pats.len() == 0 {
3457             return
3458         }
3459         let map_0 = self.binding_mode_map(&*arm.pats[0]);
3460         for (i, p) in arm.pats.iter().enumerate() {
3461             let map_i = self.binding_mode_map(&**p);
3462
3463             for (&key, &binding_0) in map_0.iter() {
3464                 match map_i.get(&key) {
3465                   None => {
3466                     self.resolve_error(
3467                         p.span,
3468                         &format!("variable `{}` from pattern #1 is \
3469                                   not bound in pattern #{}",
3470                                 token::get_name(key),
3471                                 i + 1)[]);
3472                   }
3473                   Some(binding_i) => {
3474                     if binding_0.binding_mode != binding_i.binding_mode {
3475                         self.resolve_error(
3476                             binding_i.span,
3477                             &format!("variable `{}` is bound with different \
3478                                       mode in pattern #{} than in pattern #1",
3479                                     token::get_name(key),
3480                                     i + 1)[]);
3481                     }
3482                   }
3483                 }
3484             }
3485
3486             for (&key, &binding) in map_i.iter() {
3487                 if !map_0.contains_key(&key) {
3488                     self.resolve_error(
3489                         binding.span,
3490                         &format!("variable `{}` from pattern {}{} is \
3491                                   not bound in pattern {}1",
3492                                 token::get_name(key),
3493                                 "#", i + 1, "#")[]);
3494                 }
3495             }
3496         }
3497     }
3498
3499     fn resolve_arm(&mut self, arm: &Arm) {
3500         self.value_ribs.push(Rib::new(NormalRibKind));
3501
3502         let mut bindings_list = HashMap::new();
3503         for pattern in arm.pats.iter() {
3504             self.resolve_pattern(&**pattern, RefutableMode, &mut bindings_list);
3505         }
3506
3507         // This has to happen *after* we determine which
3508         // pat_idents are variants
3509         self.check_consistent_bindings(arm);
3510
3511         visit::walk_expr_opt(self, &arm.guard);
3512         self.resolve_expr(&*arm.body);
3513
3514         self.value_ribs.pop();
3515     }
3516
3517     fn resolve_block(&mut self, block: &Block) {
3518         debug!("(resolving block) entering block");
3519         self.value_ribs.push(Rib::new(NormalRibKind));
3520
3521         // Move down in the graph, if there's an anonymous module rooted here.
3522         let orig_module = self.current_module.clone();
3523         match orig_module.anonymous_children.borrow().get(&block.id) {
3524             None => { /* Nothing to do. */ }
3525             Some(anonymous_module) => {
3526                 debug!("(resolving block) found anonymous module, moving \
3527                         down");
3528                 self.current_module = anonymous_module.clone();
3529             }
3530         }
3531
3532         // Descend into the block.
3533         visit::walk_block(self, block);
3534
3535         // Move back up.
3536         self.current_module = orig_module;
3537
3538         self.value_ribs.pop();
3539         debug!("(resolving block) leaving block");
3540     }
3541
3542     fn resolve_type(&mut self, ty: &Ty) {
3543         match ty.node {
3544             // Like path expressions, the interpretation of path types depends
3545             // on whether the path has multiple elements in it or not.
3546
3547             TyPath(ref path, path_id) => {
3548                 // This is a path in the type namespace. Walk through scopes
3549                 // looking for it.
3550                 let mut result_def = None;
3551
3552                 // First, check to see whether the name is a primitive type.
3553                 if path.segments.len() == 1 {
3554                     let id = path.segments.last().unwrap().identifier;
3555
3556                     match self.primitive_type_table
3557                             .primitive_types
3558                             .get(&id.name) {
3559
3560                         Some(&primitive_type) => {
3561                             result_def =
3562                                 Some((DefPrimTy(primitive_type), LastMod(AllPublic)));
3563
3564                             if path.segments[0].parameters.has_lifetimes() {
3565                                 span_err!(self.session, path.span, E0157,
3566                                     "lifetime parameters are not allowed on this type");
3567                             } else if !path.segments[0].parameters.is_empty() {
3568                                 span_err!(self.session, path.span, E0153,
3569                                     "type parameters are not allowed on this type");
3570                             }
3571                         }
3572                         None => {
3573                             // Continue.
3574                         }
3575                     }
3576                 }
3577
3578                 if let None = result_def {
3579                     result_def = self.resolve_path(ty.id, path, TypeNS, true);
3580                 }
3581
3582                 match result_def {
3583                     Some(def) => {
3584                         // Write the result into the def map.
3585                         debug!("(resolving type) writing resolution for `{}` \
3586                                 (id {}) = {:?}",
3587                                self.path_names_to_string(path),
3588                                path_id, def);
3589                         self.record_def(path_id, def);
3590                     }
3591                     None => {
3592                         let msg = format!("use of undeclared type name `{}`",
3593                                           self.path_names_to_string(path));
3594                         self.resolve_error(ty.span, &msg[]);
3595                     }
3596                 }
3597             }
3598
3599             TyObjectSum(ref ty, ref bound_vec) => {
3600                 self.resolve_type(&**ty);
3601                 self.resolve_type_parameter_bounds(ty.id, bound_vec,
3602                                                        TraitBoundingTypeParameter);
3603             }
3604
3605             TyQPath(ref qpath) => {
3606                 self.resolve_type(&*qpath.self_type);
3607                 self.resolve_trait_reference(ty.id, &*qpath.trait_ref, TraitQPath);
3608                 for ty in qpath.item_path.parameters.types().into_iter() {
3609                     self.resolve_type(&**ty);
3610                 }
3611                 for binding in qpath.item_path.parameters.bindings().into_iter() {
3612                     self.resolve_type(&*binding.ty);
3613                 }
3614             }
3615
3616             TyPolyTraitRef(ref bounds) => {
3617                 self.resolve_type_parameter_bounds(
3618                     ty.id,
3619                     bounds,
3620                     TraitObject);
3621                 visit::walk_ty(self, ty);
3622             }
3623             _ => {
3624                 // Just resolve embedded types.
3625                 visit::walk_ty(self, ty);
3626             }
3627         }
3628     }
3629
3630     fn resolve_pattern(&mut self,
3631                        pattern: &Pat,
3632                        mode: PatternBindingMode,
3633                        // Maps idents to the node ID for the (outermost)
3634                        // pattern that binds them
3635                        bindings_list: &mut HashMap<Name, NodeId>) {
3636         let pat_id = pattern.id;
3637         walk_pat(pattern, |pattern| {
3638             match pattern.node {
3639                 PatIdent(binding_mode, ref path1, _) => {
3640
3641                     // The meaning of pat_ident with no type parameters
3642                     // depends on whether an enum variant or unit-like struct
3643                     // with that name is in scope. The probing lookup has to
3644                     // be careful not to emit spurious errors. Only matching
3645                     // patterns (match) can match nullary variants or
3646                     // unit-like structs. For binding patterns (let), matching
3647                     // such a value is simply disallowed (since it's rarely
3648                     // what you want).
3649
3650                     let ident = path1.node;
3651                     let renamed = mtwt::resolve(ident);
3652
3653                     match self.resolve_bare_identifier_pattern(ident.name, pattern.span) {
3654                         FoundStructOrEnumVariant(ref def, lp)
3655                                 if mode == RefutableMode => {
3656                             debug!("(resolving pattern) resolving `{}` to \
3657                                     struct or enum variant",
3658                                    token::get_name(renamed));
3659
3660                             self.enforce_default_binding_mode(
3661                                 pattern,
3662                                 binding_mode,
3663                                 "an enum variant");
3664                             self.record_def(pattern.id, (def.clone(), lp));
3665                         }
3666                         FoundStructOrEnumVariant(..) => {
3667                             self.resolve_error(
3668                                 pattern.span,
3669                                 &format!("declaration of `{}` shadows an enum \
3670                                          variant or unit-like struct in \
3671                                          scope",
3672                                         token::get_name(renamed))[]);
3673                         }
3674                         FoundConst(ref def, lp) if mode == RefutableMode => {
3675                             debug!("(resolving pattern) resolving `{}` to \
3676                                     constant",
3677                                    token::get_name(renamed));
3678
3679                             self.enforce_default_binding_mode(
3680                                 pattern,
3681                                 binding_mode,
3682                                 "a constant");
3683                             self.record_def(pattern.id, (def.clone(), lp));
3684                         }
3685                         FoundConst(..) => {
3686                             self.resolve_error(pattern.span,
3687                                                   "only irrefutable patterns \
3688                                                    allowed here");
3689                         }
3690                         BareIdentifierPatternUnresolved => {
3691                             debug!("(resolving pattern) binding `{}`",
3692                                    token::get_name(renamed));
3693
3694                             let def = DefLocal(pattern.id);
3695
3696                             // Record the definition so that later passes
3697                             // will be able to distinguish variants from
3698                             // locals in patterns.
3699
3700                             self.record_def(pattern.id, (def, LastMod(AllPublic)));
3701
3702                             // Add the binding to the local ribs, if it
3703                             // doesn't already exist in the bindings list. (We
3704                             // must not add it if it's in the bindings list
3705                             // because that breaks the assumptions later
3706                             // passes make about or-patterns.)
3707                             if !bindings_list.contains_key(&renamed) {
3708                                 let this = &mut *self;
3709                                 let last_rib = this.value_ribs.last_mut().unwrap();
3710                                 last_rib.bindings.insert(renamed, DlDef(def));
3711                                 bindings_list.insert(renamed, pat_id);
3712                             } else if mode == ArgumentIrrefutableMode &&
3713                                     bindings_list.contains_key(&renamed) {
3714                                 // Forbid duplicate bindings in the same
3715                                 // parameter list.
3716                                 self.resolve_error(pattern.span,
3717                                                    &format!("identifier `{}` \
3718                                                             is bound more \
3719                                                             than once in \
3720                                                             this parameter \
3721                                                             list",
3722                                                            token::get_ident(
3723                                                                ident))
3724                                                    [])
3725                             } else if bindings_list.get(&renamed) ==
3726                                     Some(&pat_id) {
3727                                 // Then this is a duplicate variable in the
3728                                 // same disjunction, which is an error.
3729                                 self.resolve_error(pattern.span,
3730                                     &format!("identifier `{}` is bound \
3731                                              more than once in the same \
3732                                              pattern",
3733                                             token::get_ident(ident))[]);
3734                             }
3735                             // Else, not bound in the same pattern: do
3736                             // nothing.
3737                         }
3738                     }
3739                 }
3740
3741                 PatEnum(ref path, _) => {
3742                     // This must be an enum variant, struct or const.
3743                     match self.resolve_path(pat_id, path, ValueNS, false) {
3744                         Some(def @ (DefVariant(..), _)) |
3745                         Some(def @ (DefStruct(..), _))  |
3746                         Some(def @ (DefConst(..), _)) => {
3747                             self.record_def(pattern.id, def);
3748                         }
3749                         Some((DefStatic(..), _)) => {
3750                             self.resolve_error(path.span,
3751                                                "static variables cannot be \
3752                                                 referenced in a pattern, \
3753                                                 use a `const` instead");
3754                         }
3755                         Some(_) => {
3756                             self.resolve_error(path.span,
3757                                 format!("`{}` is not an enum variant, struct or const",
3758                                     token::get_ident(
3759                                         path.segments.last().unwrap().identifier)).as_slice());
3760                         }
3761                         None => {
3762                             self.resolve_error(path.span,
3763                                 format!("unresolved enum variant, struct or const `{}`",
3764                                     token::get_ident(
3765                                         path.segments.last().unwrap().identifier)).as_slice());
3766                         }
3767                     }
3768
3769                     // Check the types in the path pattern.
3770                     for ty in path.segments
3771                                   .iter()
3772                                   .flat_map(|s| s.parameters.types().into_iter()) {
3773                         self.resolve_type(&**ty);
3774                     }
3775                 }
3776
3777                 PatLit(ref expr) => {
3778                     self.resolve_expr(&**expr);
3779                 }
3780
3781                 PatRange(ref first_expr, ref last_expr) => {
3782                     self.resolve_expr(&**first_expr);
3783                     self.resolve_expr(&**last_expr);
3784                 }
3785
3786                 PatStruct(ref path, _, _) => {
3787                     match self.resolve_path(pat_id, path, TypeNS, false) {
3788                         Some(definition) => {
3789                             self.record_def(pattern.id, definition);
3790                         }
3791                         result => {
3792                             debug!("(resolving pattern) didn't find struct \
3793                                     def: {:?}", result);
3794                             let msg = format!("`{}` does not name a structure",
3795                                               self.path_names_to_string(path));
3796                             self.resolve_error(path.span, &msg[]);
3797                         }
3798                     }
3799                 }
3800
3801                 _ => {
3802                     // Nothing to do.
3803                 }
3804             }
3805             true
3806         });
3807     }
3808
3809     fn resolve_bare_identifier_pattern(&mut self, name: Name, span: Span)
3810                                        -> BareIdentifierPatternResolution {
3811         let module = self.current_module.clone();
3812         match self.resolve_item_in_lexical_scope(module,
3813                                                  name,
3814                                                  ValueNS) {
3815             Success((target, _)) => {
3816                 debug!("(resolve bare identifier pattern) succeeded in \
3817                          finding {} at {:?}",
3818                         token::get_name(name),
3819                         target.bindings.value_def.borrow());
3820                 match *target.bindings.value_def.borrow() {
3821                     None => {
3822                         panic!("resolved name in the value namespace to a \
3823                               set of name bindings with no def?!");
3824                     }
3825                     Some(def) => {
3826                         // For the two success cases, this lookup can be
3827                         // considered as not having a private component because
3828                         // the lookup happened only within the current module.
3829                         match def.def {
3830                             def @ DefVariant(..) | def @ DefStruct(..) => {
3831                                 return FoundStructOrEnumVariant(def, LastMod(AllPublic));
3832                             }
3833                             def @ DefConst(..) => {
3834                                 return FoundConst(def, LastMod(AllPublic));
3835                             }
3836                             DefStatic(..) => {
3837                                 self.resolve_error(span,
3838                                                    "static variables cannot be \
3839                                                     referenced in a pattern, \
3840                                                     use a `const` instead");
3841                                 return BareIdentifierPatternUnresolved;
3842                             }
3843                             _ => {
3844                                 return BareIdentifierPatternUnresolved;
3845                             }
3846                         }
3847                     }
3848                 }
3849             }
3850
3851             Indeterminate => {
3852                 panic!("unexpected indeterminate result");
3853             }
3854             Failed(err) => {
3855                 match err {
3856                     Some((span, msg)) => {
3857                         self.resolve_error(span, &format!("failed to resolve: {}",
3858                                                          msg)[]);
3859                     }
3860                     None => ()
3861                 }
3862
3863                 debug!("(resolve bare identifier pattern) failed to find {}",
3864                         token::get_name(name));
3865                 return BareIdentifierPatternUnresolved;
3866             }
3867         }
3868     }
3869
3870     /// If `check_ribs` is true, checks the local definitions first; i.e.
3871     /// doesn't skip straight to the containing module.
3872     fn resolve_path(&mut self,
3873                     id: NodeId,
3874                     path: &Path,
3875                     namespace: Namespace,
3876                     check_ribs: bool) -> Option<(Def, LastPrivate)> {
3877         // First, resolve the types and associated type bindings.
3878         for ty in path.segments.iter().flat_map(|s| s.parameters.types().into_iter()) {
3879             self.resolve_type(&**ty);
3880         }
3881         for binding in path.segments.iter().flat_map(|s| s.parameters.bindings().into_iter()) {
3882             self.resolve_type(&*binding.ty);
3883         }
3884
3885         // A special case for sugared associated type paths `T::A` where `T` is
3886         // a type parameter and `A` is an associated type on some bound of `T`.
3887         if namespace == TypeNS && path.segments.len() == 2 {
3888             match self.resolve_identifier(path.segments[0].identifier,
3889                                           TypeNS,
3890                                           true,
3891                                           path.span) {
3892                 Some((def, last_private)) => {
3893                     match def {
3894                         DefTyParam(_, _, did, _) => {
3895                             let def = DefAssociatedPath(TyParamProvenance::FromParam(did),
3896                                                         path.segments.last()
3897                                                             .unwrap().identifier);
3898                             return Some((def, last_private));
3899                         }
3900                         DefSelfTy(nid) => {
3901                             let def = DefAssociatedPath(TyParamProvenance::FromSelf(local_def(nid)),
3902                                                         path.segments.last()
3903                                                             .unwrap().identifier);
3904                             return Some((def, last_private));
3905                         }
3906                         _ => {}
3907                     }
3908                 }
3909                 _ => {}
3910             }
3911         }
3912
3913         if path.global {
3914             return self.resolve_crate_relative_path(path, namespace);
3915         }
3916
3917         // Try to find a path to an item in a module.
3918         let unqualified_def =
3919                 self.resolve_identifier(path.segments.last().unwrap().identifier,
3920                                         namespace,
3921                                         check_ribs,
3922                                         path.span);
3923
3924         if path.segments.len() > 1 {
3925             let def = self.resolve_module_relative_path(path, namespace);
3926             match (def, unqualified_def) {
3927                 (Some((ref d, _)), Some((ref ud, _))) if *d == *ud => {
3928                     self.session
3929                         .add_lint(lint::builtin::UNUSED_QUALIFICATIONS,
3930                                   id,
3931                                   path.span,
3932                                   "unnecessary qualification".to_string());
3933                 }
3934                 _ => ()
3935             }
3936
3937             return def;
3938         }
3939
3940         return unqualified_def;
3941     }
3942
3943     // resolve a single identifier (used as a varref)
3944     fn resolve_identifier(&mut self,
3945                           identifier: Ident,
3946                           namespace: Namespace,
3947                           check_ribs: bool,
3948                           span: Span)
3949                           -> Option<(Def, LastPrivate)> {
3950         if check_ribs {
3951             match self.resolve_identifier_in_local_ribs(identifier,
3952                                                         namespace,
3953                                                         span) {
3954                 Some(def) => {
3955                     return Some((def, LastMod(AllPublic)));
3956                 }
3957                 None => {
3958                     // Continue.
3959                 }
3960             }
3961         }
3962
3963         return self.resolve_item_by_name_in_lexical_scope(identifier.name, namespace);
3964     }
3965
3966     // FIXME #4952: Merge me with resolve_name_in_module?
3967     fn resolve_definition_of_name_in_module(&mut self,
3968                                             containing_module: Rc<Module>,
3969                                             name: Name,
3970                                             namespace: Namespace)
3971                                             -> NameDefinition {
3972         // First, search children.
3973         build_reduced_graph::populate_module_if_necessary(self, &containing_module);
3974
3975         match containing_module.children.borrow().get(&name) {
3976             Some(child_name_bindings) => {
3977                 match child_name_bindings.def_for_namespace(namespace) {
3978                     Some(def) => {
3979                         // Found it. Stop the search here.
3980                         let p = child_name_bindings.defined_in_public_namespace(
3981                                         namespace);
3982                         let lp = if p {LastMod(AllPublic)} else {
3983                             LastMod(DependsOn(def.def_id()))
3984                         };
3985                         return ChildNameDefinition(def, lp);
3986                     }
3987                     None => {}
3988                 }
3989             }
3990             None => {}
3991         }
3992
3993         // Next, search import resolutions.
3994         match containing_module.import_resolutions.borrow().get(&name) {
3995             Some(import_resolution) if import_resolution.is_public => {
3996                 if let Some(target) = (*import_resolution).target_for_namespace(namespace) {
3997                     match target.bindings.def_for_namespace(namespace) {
3998                         Some(def) => {
3999                             // Found it.
4000                             let id = import_resolution.id(namespace);
4001                             // track imports and extern crates as well
4002                             self.used_imports.insert((id, namespace));
4003                             self.record_import_use(id, name);
4004                             match target.target_module.def_id.get() {
4005                                 Some(DefId{krate: kid, ..}) => {
4006                                     self.used_crates.insert(kid);
4007                                 },
4008                                 _ => {}
4009                             }
4010                             return ImportNameDefinition(def, LastMod(AllPublic));
4011                         }
4012                         None => {
4013                             // This can happen with external impls, due to
4014                             // the imperfect way we read the metadata.
4015                         }
4016                     }
4017                 }
4018             }
4019             Some(..) | None => {} // Continue.
4020         }
4021
4022         // Finally, search through external children.
4023         if namespace == TypeNS {
4024             if let Some(module) = containing_module.external_module_children.borrow()
4025                                                    .get(&name).cloned() {
4026                 if let Some(def_id) = module.def_id.get() {
4027                     // track used crates
4028                     self.used_crates.insert(def_id.krate);
4029                     let lp = if module.is_public {LastMod(AllPublic)} else {
4030                         LastMod(DependsOn(def_id))
4031                     };
4032                     return ChildNameDefinition(DefMod(def_id), lp);
4033                 }
4034             }
4035         }
4036
4037         return NoNameDefinition;
4038     }
4039
4040     // resolve a "module-relative" path, e.g. a::b::c
4041     fn resolve_module_relative_path(&mut self,
4042                                     path: &Path,
4043                                     namespace: Namespace)
4044                                     -> Option<(Def, LastPrivate)> {
4045         let module_path = path.segments.init().iter()
4046                                               .map(|ps| ps.identifier.name)
4047                                               .collect::<Vec<_>>();
4048
4049         let containing_module;
4050         let last_private;
4051         let module = self.current_module.clone();
4052         match self.resolve_module_path(module,
4053                                        &module_path[],
4054                                        UseLexicalScope,
4055                                        path.span,
4056                                        PathSearch) {
4057             Failed(err) => {
4058                 let (span, msg) = match err {
4059                     Some((span, msg)) => (span, msg),
4060                     None => {
4061                         let msg = format!("Use of undeclared type or module `{}`",
4062                                           self.names_to_string(module_path.as_slice()));
4063                         (path.span, msg)
4064                     }
4065                 };
4066
4067                 self.resolve_error(span, &format!("failed to resolve. {}",
4068                                                  msg)[]);
4069                 return None;
4070             }
4071             Indeterminate => panic!("indeterminate unexpected"),
4072             Success((resulting_module, resulting_last_private)) => {
4073                 containing_module = resulting_module;
4074                 last_private = resulting_last_private;
4075             }
4076         }
4077
4078         let name = path.segments.last().unwrap().identifier.name;
4079         let def = match self.resolve_definition_of_name_in_module(containing_module.clone(),
4080                                                                   name,
4081                                                                   namespace) {
4082             NoNameDefinition => {
4083                 // We failed to resolve the name. Report an error.
4084                 return None;
4085             }
4086             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
4087                 (def, last_private.or(lp))
4088             }
4089         };
4090         if let Some(DefId{krate: kid, ..}) = containing_module.def_id.get() {
4091             self.used_crates.insert(kid);
4092         }
4093         return Some(def);
4094     }
4095
4096     /// Invariant: This must be called only during main resolution, not during
4097     /// import resolution.
4098     fn resolve_crate_relative_path(&mut self,
4099                                    path: &Path,
4100                                    namespace: Namespace)
4101                                        -> Option<(Def, LastPrivate)> {
4102         let module_path = path.segments.init().iter()
4103                                               .map(|ps| ps.identifier.name)
4104                                               .collect::<Vec<_>>();
4105
4106         let root_module = self.graph_root.get_module();
4107
4108         let containing_module;
4109         let last_private;
4110         match self.resolve_module_path_from_root(root_module,
4111                                                  &module_path[],
4112                                                  0,
4113                                                  path.span,
4114                                                  PathSearch,
4115                                                  LastMod(AllPublic)) {
4116             Failed(err) => {
4117                 let (span, msg) = match err {
4118                     Some((span, msg)) => (span, msg),
4119                     None => {
4120                         let msg = format!("Use of undeclared module `::{}`",
4121                                           self.names_to_string(&module_path[]));
4122                         (path.span, msg)
4123                     }
4124                 };
4125
4126                 self.resolve_error(span, &format!("failed to resolve. {}",
4127                                                  msg)[]);
4128                 return None;
4129             }
4130
4131             Indeterminate => {
4132                 panic!("indeterminate unexpected");
4133             }
4134
4135             Success((resulting_module, resulting_last_private)) => {
4136                 containing_module = resulting_module;
4137                 last_private = resulting_last_private;
4138             }
4139         }
4140
4141         let name = path.segments.last().unwrap().identifier.name;
4142         match self.resolve_definition_of_name_in_module(containing_module,
4143                                                         name,
4144                                                         namespace) {
4145             NoNameDefinition => {
4146                 // We failed to resolve the name. Report an error.
4147                 return None;
4148             }
4149             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
4150                 return Some((def, last_private.or(lp)));
4151             }
4152         }
4153     }
4154
4155     fn resolve_identifier_in_local_ribs(&mut self,
4156                                         ident: Ident,
4157                                         namespace: Namespace,
4158                                         span: Span)
4159                                         -> Option<Def> {
4160         // Check the local set of ribs.
4161         let search_result = match namespace {
4162             ValueNS => {
4163                 let renamed = mtwt::resolve(ident);
4164                 self.search_ribs(self.value_ribs.as_slice(), renamed, span)
4165             }
4166             TypeNS => {
4167                 let name = ident.name;
4168                 self.search_ribs(&self.type_ribs[], name, span)
4169             }
4170         };
4171
4172         match search_result {
4173             Some(DlDef(def)) => {
4174                 debug!("(resolving path in local ribs) resolved `{}` to \
4175                         local: {:?}",
4176                        token::get_ident(ident),
4177                        def);
4178                 return Some(def);
4179             }
4180             Some(DlField) | Some(DlImpl(_)) | None => {
4181                 return None;
4182             }
4183         }
4184     }
4185
4186     fn resolve_item_by_name_in_lexical_scope(&mut self,
4187                                              name: Name,
4188                                              namespace: Namespace)
4189                                             -> Option<(Def, LastPrivate)> {
4190         // Check the items.
4191         let module = self.current_module.clone();
4192         match self.resolve_item_in_lexical_scope(module,
4193                                                  name,
4194                                                  namespace) {
4195             Success((target, _)) => {
4196                 match (*target.bindings).def_for_namespace(namespace) {
4197                     None => {
4198                         // This can happen if we were looking for a type and
4199                         // found a module instead. Modules don't have defs.
4200                         debug!("(resolving item path by identifier in lexical \
4201                                  scope) failed to resolve {} after success...",
4202                                  token::get_name(name));
4203                         return None;
4204                     }
4205                     Some(def) => {
4206                         debug!("(resolving item path in lexical scope) \
4207                                 resolved `{}` to item",
4208                                token::get_name(name));
4209                         // This lookup is "all public" because it only searched
4210                         // for one identifier in the current module (couldn't
4211                         // have passed through reexports or anything like that.
4212                         return Some((def, LastMod(AllPublic)));
4213                     }
4214                 }
4215             }
4216             Indeterminate => {
4217                 panic!("unexpected indeterminate result");
4218             }
4219             Failed(err) => {
4220                 match err {
4221                     Some((span, msg)) =>
4222                         self.resolve_error(span, &format!("failed to resolve. {}",
4223                                                          msg)[]),
4224                     None => ()
4225                 }
4226
4227                 debug!("(resolving item path by identifier in lexical scope) \
4228                          failed to resolve {}", token::get_name(name));
4229                 return None;
4230             }
4231         }
4232     }
4233
4234     fn with_no_errors<T, F>(&mut self, f: F) -> T where
4235         F: FnOnce(&mut Resolver) -> T,
4236     {
4237         self.emit_errors = false;
4238         let rs = f(self);
4239         self.emit_errors = true;
4240         rs
4241     }
4242
4243     fn resolve_error(&self, span: Span, s: &str) {
4244         if self.emit_errors {
4245             self.session.span_err(span, s);
4246         }
4247     }
4248
4249     fn find_fallback_in_self_type(&mut self, name: Name) -> FallbackSuggestion {
4250         fn extract_path_and_node_id(t: &Ty, allow: FallbackChecks)
4251                                                     -> Option<(Path, NodeId, FallbackChecks)> {
4252             match t.node {
4253                 TyPath(ref path, node_id) => Some((path.clone(), node_id, allow)),
4254                 TyPtr(ref mut_ty) => extract_path_and_node_id(&*mut_ty.ty, OnlyTraitAndStatics),
4255                 TyRptr(_, ref mut_ty) => extract_path_and_node_id(&*mut_ty.ty, allow),
4256                 // This doesn't handle the remaining `Ty` variants as they are not
4257                 // that commonly the self_type, it might be interesting to provide
4258                 // support for those in future.
4259                 _ => None,
4260             }
4261         }
4262
4263         fn get_module(this: &mut Resolver, span: Span, name_path: &[ast::Name])
4264                             -> Option<Rc<Module>> {
4265             let root = this.current_module.clone();
4266             let last_name = name_path.last().unwrap();
4267
4268             if name_path.len() == 1 {
4269                 match this.primitive_type_table.primitive_types.get(last_name) {
4270                     Some(_) => None,
4271                     None => {
4272                         match this.current_module.children.borrow().get(last_name) {
4273                             Some(child) => child.get_module_if_available(),
4274                             None => None
4275                         }
4276                     }
4277                 }
4278             } else {
4279                 match this.resolve_module_path(root,
4280                                                 &name_path[],
4281                                                 UseLexicalScope,
4282                                                 span,
4283                                                 PathSearch) {
4284                     Success((module, _)) => Some(module),
4285                     _ => None
4286                 }
4287             }
4288         }
4289
4290         let (path, node_id, allowed) = match self.current_self_type {
4291             Some(ref ty) => match extract_path_and_node_id(ty, Everything) {
4292                 Some(x) => x,
4293                 None => return NoSuggestion,
4294             },
4295             None => return NoSuggestion,
4296         };
4297
4298         if allowed == Everything {
4299             // Look for a field with the same name in the current self_type.
4300             match self.def_map.borrow().get(&node_id) {
4301                  Some(&DefTy(did, _))
4302                 | Some(&DefStruct(did))
4303                 | Some(&DefVariant(_, did, _)) => match self.structs.get(&did) {
4304                     None => {}
4305                     Some(fields) => {
4306                         if fields.iter().any(|&field_name| name == field_name) {
4307                             return Field;
4308                         }
4309                     }
4310                 },
4311                 _ => {} // Self type didn't resolve properly
4312             }
4313         }
4314
4315         let name_path = path.segments.iter().map(|seg| seg.identifier.name).collect::<Vec<_>>();
4316
4317         // Look for a method in the current self type's impl module.
4318         match get_module(self, path.span, &name_path[]) {
4319             Some(module) => match module.children.borrow().get(&name) {
4320                 Some(binding) => {
4321                     let p_str = self.path_names_to_string(&path);
4322                     match binding.def_for_namespace(ValueNS) {
4323                         Some(DefStaticMethod(_, provenance)) => {
4324                             match provenance {
4325                                 FromImpl(_) => return StaticMethod(p_str),
4326                                 FromTrait(_) => unreachable!()
4327                             }
4328                         }
4329                         Some(DefMethod(_, None, _)) if allowed == Everything => return Method,
4330                         Some(DefMethod(_, Some(_), _)) => return TraitItem,
4331                         _ => ()
4332                     }
4333                 }
4334                 None => {}
4335             },
4336             None => {}
4337         }
4338
4339         // Look for a method in the current trait.
4340         match self.current_trait_ref {
4341             Some((did, ref trait_ref)) => {
4342                 let path_str = self.path_names_to_string(&trait_ref.path);
4343
4344                 match self.trait_item_map.get(&(name, did)) {
4345                     Some(&StaticMethodTraitItemKind) => {
4346                         return TraitMethod(path_str)
4347                     }
4348                     Some(_) => return TraitItem,
4349                     None => {}
4350                 }
4351             }
4352             None => {}
4353         }
4354
4355         NoSuggestion
4356     }
4357
4358     fn find_best_match_for_name(&mut self, name: &str, max_distance: uint)
4359                                 -> Option<String> {
4360         let this = &mut *self;
4361
4362         let mut maybes: Vec<token::InternedString> = Vec::new();
4363         let mut values: Vec<uint> = Vec::new();
4364
4365         for rib in this.value_ribs.iter().rev() {
4366             for (&k, _) in rib.bindings.iter() {
4367                 maybes.push(token::get_name(k));
4368                 values.push(uint::MAX);
4369             }
4370         }
4371
4372         let mut smallest = 0;
4373         for (i, other) in maybes.iter().enumerate() {
4374             values[i] = lev_distance(name, other.get());
4375
4376             if values[i] <= values[smallest] {
4377                 smallest = i;
4378             }
4379         }
4380
4381         if values.len() > 0 &&
4382             values[smallest] != uint::MAX &&
4383             values[smallest] < name.len() + 2 &&
4384             values[smallest] <= max_distance &&
4385             name != maybes[smallest].get() {
4386
4387             Some(maybes[smallest].get().to_string())
4388
4389         } else {
4390             None
4391         }
4392     }
4393
4394     fn resolve_expr(&mut self, expr: &Expr) {
4395         // First, record candidate traits for this expression if it could
4396         // result in the invocation of a method call.
4397
4398         self.record_candidate_traits_for_expr_if_necessary(expr);
4399
4400         // Next, resolve the node.
4401         match expr.node {
4402             // The interpretation of paths depends on whether the path has
4403             // multiple elements in it or not.
4404
4405             ExprPath(_) | ExprQPath(_) => {
4406                 let mut path_from_qpath;
4407                 let path = match expr.node {
4408                     ExprPath(ref path) => path,
4409                     ExprQPath(ref qpath) => {
4410                         self.resolve_type(&*qpath.self_type);
4411                         self.resolve_trait_reference(expr.id, &*qpath.trait_ref, TraitQPath);
4412                         path_from_qpath = qpath.trait_ref.path.clone();
4413                         path_from_qpath.segments.push(qpath.item_path.clone());
4414                         &path_from_qpath
4415                     }
4416                     _ => unreachable!()
4417                 };
4418                 // This is a local path in the value namespace. Walk through
4419                 // scopes looking for it.
4420                 match self.resolve_path(expr.id, path, ValueNS, true) {
4421                     // Check if struct variant
4422                     Some((DefVariant(_, _, true), _)) => {
4423                         let path_name = self.path_names_to_string(path);
4424                         self.resolve_error(expr.span,
4425                                 format!("`{}` is a struct variant name, but \
4426                                          this expression \
4427                                          uses it like a function name",
4428                                         path_name).as_slice());
4429
4430                         self.session.span_help(expr.span,
4431                             format!("Did you mean to write: \
4432                                     `{} {{ /* fields */ }}`?",
4433                                     path_name).as_slice());
4434                     }
4435                     Some(def) => {
4436                         // Write the result into the def map.
4437                         debug!("(resolving expr) resolved `{}`",
4438                                self.path_names_to_string(path));
4439
4440                         self.record_def(expr.id, def);
4441                     }
4442                     None => {
4443                         // Be helpful if the name refers to a struct
4444                         // (The pattern matching def_tys where the id is in self.structs
4445                         // matches on regular structs while excluding tuple- and enum-like
4446                         // structs, which wouldn't result in this error.)
4447                         let path_name = self.path_names_to_string(path);
4448                         match self.with_no_errors(|this|
4449                             this.resolve_path(expr.id, path, TypeNS, false)) {
4450                             Some((DefTy(struct_id, _), _))
4451                               if self.structs.contains_key(&struct_id) => {
4452                                 self.resolve_error(expr.span,
4453                                         format!("`{}` is a structure name, but \
4454                                                  this expression \
4455                                                  uses it like a function name",
4456                                                 path_name).as_slice());
4457
4458                                 self.session.span_help(expr.span,
4459                                     format!("Did you mean to write: \
4460                                             `{} {{ /* fields */ }}`?",
4461                                             path_name).as_slice());
4462
4463                             }
4464                             _ => {
4465                                 let mut method_scope = false;
4466                                 self.value_ribs.iter().rev().all(|rib| {
4467                                     let res = match *rib {
4468                                         Rib { bindings: _, kind: MethodRibKind(_, _) } => true,
4469                                         Rib { bindings: _, kind: ItemRibKind } => false,
4470                                         _ => return true, // Keep advancing
4471                                     };
4472
4473                                     method_scope = res;
4474                                     false // Stop advancing
4475                                 });
4476
4477                                 if method_scope && token::get_name(self.self_name).get()
4478                                                                    == path_name {
4479                                         self.resolve_error(
4480                                             expr.span,
4481                                             "`self` is not available \
4482                                              in a static method. Maybe a \
4483                                              `self` argument is missing?");
4484                                 } else {
4485                                     let last_name = path.segments.last().unwrap().identifier.name;
4486                                     let mut msg = match self.find_fallback_in_self_type(last_name) {
4487                                         NoSuggestion => {
4488                                             // limit search to 5 to reduce the number
4489                                             // of stupid suggestions
4490                                             self.find_best_match_for_name(path_name.as_slice(), 5)
4491                                                                 .map_or("".to_string(),
4492                                                                         |x| format!("`{}`", x))
4493                                         }
4494                                         Field =>
4495                                             format!("`self.{}`", path_name),
4496                                         Method
4497                                         | TraitItem =>
4498                                             format!("to call `self.{}`", path_name),
4499                                         TraitMethod(path_str)
4500                                         | StaticMethod(path_str) =>
4501                                             format!("to call `{}::{}`", path_str, path_name)
4502                                     };
4503
4504                                     if msg.len() > 0 {
4505                                         msg = format!(". Did you mean {}?", msg)
4506                                     }
4507
4508                                     self.resolve_error(
4509                                         expr.span,
4510                                         format!("unresolved name `{}`{}",
4511                                                 path_name,
4512                                                 msg).as_slice());
4513                                 }
4514                             }
4515                         }
4516                     }
4517                 }
4518
4519                 visit::walk_expr(self, expr);
4520             }
4521
4522             ExprClosure(capture_clause, _, ref fn_decl, ref block) => {
4523                 self.capture_mode_map.insert(expr.id, capture_clause);
4524                 self.resolve_function(ClosureRibKind(expr.id, ast::DUMMY_NODE_ID),
4525                                       Some(&**fn_decl), NoTypeParameters,
4526                                       &**block);
4527             }
4528
4529             ExprStruct(ref path, _, _) => {
4530                 // Resolve the path to the structure it goes to. We don't
4531                 // check to ensure that the path is actually a structure; that
4532                 // is checked later during typeck.
4533                 match self.resolve_path(expr.id, path, TypeNS, false) {
4534                     Some(definition) => self.record_def(expr.id, definition),
4535                     result => {
4536                         debug!("(resolving expression) didn't find struct \
4537                                 def: {:?}", result);
4538                         let msg = format!("`{}` does not name a structure",
4539                                           self.path_names_to_string(path));
4540                         self.resolve_error(path.span, &msg[]);
4541                     }
4542                 }
4543
4544                 visit::walk_expr(self, expr);
4545             }
4546
4547             ExprLoop(_, Some(label)) | ExprWhile(_, _, Some(label)) => {
4548                 self.with_label_rib(|this| {
4549                     let def_like = DlDef(DefLabel(expr.id));
4550
4551                     {
4552                         let rib = this.label_ribs.last_mut().unwrap();
4553                         let renamed = mtwt::resolve(label);
4554                         rib.bindings.insert(renamed, def_like);
4555                     }
4556
4557                     visit::walk_expr(this, expr);
4558                 })
4559             }
4560
4561             ExprForLoop(ref pattern, ref head, ref body, optional_label) => {
4562                 self.resolve_expr(&**head);
4563
4564                 self.value_ribs.push(Rib::new(NormalRibKind));
4565
4566                 self.resolve_pattern(&**pattern,
4567                                      LocalIrrefutableMode,
4568                                      &mut HashMap::new());
4569
4570                 match optional_label {
4571                     None => {}
4572                     Some(label) => {
4573                         self.label_ribs
4574                             .push(Rib::new(NormalRibKind));
4575                         let def_like = DlDef(DefLabel(expr.id));
4576
4577                         {
4578                             let rib = self.label_ribs.last_mut().unwrap();
4579                             let renamed = mtwt::resolve(label);
4580                             rib.bindings.insert(renamed, def_like);
4581                         }
4582                     }
4583                 }
4584
4585                 self.resolve_block(&**body);
4586
4587                 if optional_label.is_some() {
4588                     drop(self.label_ribs.pop())
4589                 }
4590
4591                 self.value_ribs.pop();
4592             }
4593
4594             ExprBreak(Some(label)) | ExprAgain(Some(label)) => {
4595                 let renamed = mtwt::resolve(label);
4596                 match self.search_label(renamed) {
4597                     None => {
4598                         self.resolve_error(
4599                             expr.span,
4600                             &format!("use of undeclared label `{}`",
4601                                     token::get_ident(label))[])
4602                     }
4603                     Some(DlDef(def @ DefLabel(_))) => {
4604                         // Since this def is a label, it is never read.
4605                         self.record_def(expr.id, (def, LastMod(AllPublic)))
4606                     }
4607                     Some(_) => {
4608                         self.session.span_bug(expr.span,
4609                                               "label wasn't mapped to a \
4610                                                label def!")
4611                     }
4612                 }
4613             }
4614
4615             _ => {
4616                 visit::walk_expr(self, expr);
4617             }
4618         }
4619     }
4620
4621     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
4622         match expr.node {
4623             ExprField(_, ident) => {
4624                 // FIXME(#6890): Even though you can't treat a method like a
4625                 // field, we need to add any trait methods we find that match
4626                 // the field name so that we can do some nice error reporting
4627                 // later on in typeck.
4628                 let traits = self.search_for_traits_containing_method(ident.node.name);
4629                 self.trait_map.insert(expr.id, traits);
4630             }
4631             ExprMethodCall(ident, _, _) => {
4632                 debug!("(recording candidate traits for expr) recording \
4633                         traits for {}",
4634                        expr.id);
4635                 let traits = self.search_for_traits_containing_method(ident.node.name);
4636                 self.trait_map.insert(expr.id, traits);
4637             }
4638             _ => {
4639                 // Nothing to do.
4640             }
4641         }
4642     }
4643
4644     fn search_for_traits_containing_method(&mut self, name: Name) -> Vec<DefId> {
4645         debug!("(searching for traits containing method) looking for '{}'",
4646                token::get_name(name));
4647
4648         fn add_trait_info(found_traits: &mut Vec<DefId>,
4649                           trait_def_id: DefId,
4650                           name: Name) {
4651             debug!("(adding trait info) found trait {}:{} for method '{}'",
4652                 trait_def_id.krate,
4653                 trait_def_id.node,
4654                 token::get_name(name));
4655             found_traits.push(trait_def_id);
4656         }
4657
4658         let mut found_traits = Vec::new();
4659         let mut search_module = self.current_module.clone();
4660         loop {
4661             // Look for the current trait.
4662             match self.current_trait_ref {
4663                 Some((trait_def_id, _)) => {
4664                     if self.trait_item_map.contains_key(&(name, trait_def_id)) {
4665                         add_trait_info(&mut found_traits, trait_def_id, name);
4666                     }
4667                 }
4668                 None => {} // Nothing to do.
4669             }
4670
4671             // Look for trait children.
4672             build_reduced_graph::populate_module_if_necessary(self, &search_module);
4673
4674             {
4675                 for (_, child_names) in search_module.children.borrow().iter() {
4676                     let def = match child_names.def_for_namespace(TypeNS) {
4677                         Some(def) => def,
4678                         None => continue
4679                     };
4680                     let trait_def_id = match def {
4681                         DefTrait(trait_def_id) => trait_def_id,
4682                         _ => continue,
4683                     };
4684                     if self.trait_item_map.contains_key(&(name, trait_def_id)) {
4685                         add_trait_info(&mut found_traits, trait_def_id, name);
4686                     }
4687                 }
4688             }
4689
4690             // Look for imports.
4691             for (_, import) in search_module.import_resolutions.borrow().iter() {
4692                 let target = match import.target_for_namespace(TypeNS) {
4693                     None => continue,
4694                     Some(target) => target,
4695                 };
4696                 let did = match target.bindings.def_for_namespace(TypeNS) {
4697                     Some(DefTrait(trait_def_id)) => trait_def_id,
4698                     Some(..) | None => continue,
4699                 };
4700                 if self.trait_item_map.contains_key(&(name, did)) {
4701                     add_trait_info(&mut found_traits, did, name);
4702                     let id = import.type_id;
4703                     self.used_imports.insert((id, TypeNS));
4704                     let trait_name = self.get_trait_name(did);
4705                     self.record_import_use(id, trait_name);
4706                     if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
4707                         self.used_crates.insert(kid);
4708                     }
4709                 }
4710             }
4711
4712             match search_module.parent_link.clone() {
4713                 NoParentLink | ModuleParentLink(..) => break,
4714                 BlockParentLink(parent_module, _) => {
4715                     search_module = parent_module.upgrade().unwrap();
4716                 }
4717             }
4718         }
4719
4720         found_traits
4721     }
4722
4723     fn record_def(&mut self, node_id: NodeId, (def, lp): (Def, LastPrivate)) {
4724         debug!("(recording def) recording {:?} for {}, last private {:?}",
4725                 def, node_id, lp);
4726         assert!(match lp {LastImport{..} => false, _ => true},
4727                 "Import should only be used for `use` directives");
4728         self.last_private.insert(node_id, lp);
4729
4730         match self.def_map.borrow_mut().entry(node_id) {
4731             // Resolve appears to "resolve" the same ID multiple
4732             // times, so here is a sanity check it at least comes to
4733             // the same conclusion! - nmatsakis
4734             Occupied(entry) => if def != *entry.get() {
4735                 self.session
4736                     .bug(&format!("node_id {} resolved first to {:?} and \
4737                                   then {:?}",
4738                                  node_id,
4739                                  *entry.get(),
4740                                  def)[]);
4741             },
4742             Vacant(entry) => { entry.insert(def); },
4743         }
4744     }
4745
4746     fn enforce_default_binding_mode(&mut self,
4747                                         pat: &Pat,
4748                                         pat_binding_mode: BindingMode,
4749                                         descr: &str) {
4750         match pat_binding_mode {
4751             BindByValue(_) => {}
4752             BindByRef(..) => {
4753                 self.resolve_error(pat.span,
4754                                    &format!("cannot use `ref` binding mode \
4755                                             with {}",
4756                                            descr)[]);
4757             }
4758         }
4759     }
4760
4761     //
4762     // Diagnostics
4763     //
4764     // Diagnostics are not particularly efficient, because they're rarely
4765     // hit.
4766     //
4767
4768     /// A somewhat inefficient routine to obtain the name of a module.
4769     fn module_to_string(&self, module: &Module) -> String {
4770         let mut names = Vec::new();
4771
4772         fn collect_mod(names: &mut Vec<ast::Name>, module: &Module) {
4773             match module.parent_link {
4774                 NoParentLink => {}
4775                 ModuleParentLink(ref module, name) => {
4776                     names.push(name);
4777                     collect_mod(names, &*module.upgrade().unwrap());
4778                 }
4779                 BlockParentLink(ref module, _) => {
4780                     // danger, shouldn't be ident?
4781                     names.push(special_idents::opaque.name);
4782                     collect_mod(names, &*module.upgrade().unwrap());
4783                 }
4784             }
4785         }
4786         collect_mod(&mut names, module);
4787
4788         if names.len() == 0 {
4789             return "???".to_string();
4790         }
4791         self.names_to_string(&names.into_iter().rev()
4792                                   .collect::<Vec<ast::Name>>()[])
4793     }
4794
4795     #[allow(dead_code)]   // useful for debugging
4796     fn dump_module(&mut self, module_: Rc<Module>) {
4797         debug!("Dump of module `{}`:", self.module_to_string(&*module_));
4798
4799         debug!("Children:");
4800         build_reduced_graph::populate_module_if_necessary(self, &module_);
4801         for (&name, _) in module_.children.borrow().iter() {
4802             debug!("* {}", token::get_name(name));
4803         }
4804
4805         debug!("Import resolutions:");
4806         let import_resolutions = module_.import_resolutions.borrow();
4807         for (&name, import_resolution) in import_resolutions.iter() {
4808             let value_repr;
4809             match import_resolution.target_for_namespace(ValueNS) {
4810                 None => { value_repr = "".to_string(); }
4811                 Some(_) => {
4812                     value_repr = " value:?".to_string();
4813                     // FIXME #4954
4814                 }
4815             }
4816
4817             let type_repr;
4818             match import_resolution.target_for_namespace(TypeNS) {
4819                 None => { type_repr = "".to_string(); }
4820                 Some(_) => {
4821                     type_repr = " type:?".to_string();
4822                     // FIXME #4954
4823                 }
4824             }
4825
4826             debug!("* {}:{}{}", token::get_name(name), value_repr, type_repr);
4827         }
4828     }
4829 }
4830
4831 pub struct CrateMap {
4832     pub def_map: DefMap,
4833     pub freevars: RefCell<FreevarMap>,
4834     pub capture_mode_map: RefCell<CaptureModeMap>,
4835     pub export_map: ExportMap,
4836     pub trait_map: TraitMap,
4837     pub external_exports: ExternalExports,
4838     pub last_private_map: LastPrivateMap,
4839     pub glob_map: Option<GlobMap>
4840 }
4841
4842 #[derive(PartialEq,Copy)]
4843 pub enum MakeGlobMap {
4844     Yes,
4845     No
4846 }
4847
4848 /// Entry point to crate resolution.
4849 pub fn resolve_crate<'a, 'tcx>(session: &'a Session,
4850                                ast_map: &'a ast_map::Map<'tcx>,
4851                                _: &LanguageItems,
4852                                krate: &Crate,
4853                                make_glob_map: MakeGlobMap)
4854                                -> CrateMap {
4855     let mut resolver = Resolver::new(session, ast_map, krate.span, make_glob_map);
4856
4857     build_reduced_graph::build_reduced_graph(&mut resolver, krate);
4858     session.abort_if_errors();
4859
4860     resolver.resolve_imports();
4861     session.abort_if_errors();
4862
4863     record_exports::record(&mut resolver);
4864     session.abort_if_errors();
4865
4866     resolver.resolve_crate(krate);
4867     session.abort_if_errors();
4868
4869     check_unused::check_crate(&mut resolver, krate);
4870
4871     CrateMap {
4872         def_map: resolver.def_map,
4873         freevars: resolver.freevars,
4874         capture_mode_map: RefCell::new(resolver.capture_mode_map),
4875         export_map: resolver.export_map,
4876         trait_map: resolver.trait_map,
4877         external_exports: resolver.external_exports,
4878         last_private_map: resolver.last_private,
4879         glob_map: if resolver.make_glob_map {
4880                         Some(resolver.glob_map)
4881                     } else {
4882                         None
4883                     },
4884     }
4885 }