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