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