src/librustc/middle/resolve.rs

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