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