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