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