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