src/librustc/middle/resolve.rs

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