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                                        parent_public: bool) {
1425         let ident = variant.node.name;
1426         // FIXME: this is unfortunate to have to do this privacy calculation
1427         //      here. This should be living in middle::privacy, but it's
1428         //      necessary to keep around in some form becaues of glob imports...
1429         let is_public = parent_public && variant.node.vis != ast::Private;
1430
1431         match variant.node.kind {
1432             TupleVariantKind(_) => {
1433                 let (child, _) = self.add_child(ident, parent, ForbidDuplicateValues,
1434                                                 variant.span);
1435                 child.define_value(DefVariant(item_id,
1436                                               local_def(variant.node.id), false),
1437                                    variant.span, is_public);
1438             }
1439             StructVariantKind(_) => {
1440                 let (child, _) = self.add_child(ident, parent, ForbidDuplicateTypesAndValues,
1441                                                 variant.span);
1442                 child.define_type(DefVariant(item_id,
1443                                              local_def(variant.node.id), true),
1444                                   variant.span, is_public);
1445                 self.structs.insert(local_def(variant.node.id));
1446             }
1447         }
1448     }
1449
1450     /// Constructs the reduced graph for one 'view item'. View items consist
1451     /// of imports and use directives.
1452     fn build_reduced_graph_for_view_item(&mut self, view_item: &ViewItem,
1453                                          parent: ReducedGraphParent) {
1454         match view_item.node {
1455             ViewItemUse(ref view_paths) => {
1456                 for view_path in view_paths.iter() {
1457                     // Extract and intern the module part of the path. For
1458                     // globs and lists, the path is found directly in the AST;
1459                     // for simple paths we have to munge the path a little.
1460
1461                     let mut module_path = Vec::new();
1462                     match view_path.node {
1463                         ViewPathSimple(_, ref full_path, _) => {
1464                             let path_len = full_path.segments.len();
1465                             assert!(path_len != 0);
1466
1467                             for (i, segment) in full_path.segments
1468                                                          .iter()
1469                                                          .enumerate() {
1470                                 if i != path_len - 1 {
1471                                     module_path.push(segment.identifier)
1472                                 }
1473                             }
1474                         }
1475
1476                         ViewPathGlob(ref module_ident_path, _) |
1477                         ViewPathList(ref module_ident_path, _, _) => {
1478                             for segment in module_ident_path.segments.iter() {
1479                                 module_path.push(segment.identifier)
1480                             }
1481                         }
1482                     }
1483
1484                     // Build up the import directives.
1485                     let module_ = self.get_module_from_parent(parent);
1486                     let is_public = view_item.vis == ast::Public;
1487                     match view_path.node {
1488                         ViewPathSimple(binding, ref full_path, id) => {
1489                             let source_ident =
1490                                 full_path.segments.last().unwrap().identifier;
1491                             let subclass = @SingleImport(binding,
1492                                                          source_ident);
1493                             self.build_import_directive(module_,
1494                                                         module_path,
1495                                                         subclass,
1496                                                         view_path.span,
1497                                                         id,
1498                                                         is_public);
1499                         }
1500                         ViewPathList(_, ref source_idents, _) => {
1501                             for source_ident in source_idents.iter() {
1502                                 let name = source_ident.node.name;
1503                                 let subclass = @SingleImport(name, name);
1504                                 self.build_import_directive(
1505                                     module_,
1506                                     module_path.clone(),
1507                                     subclass,
1508                                     source_ident.span,
1509                                     source_ident.node.id,
1510                                     is_public);
1511                             }
1512                         }
1513                         ViewPathGlob(_, id) => {
1514                             self.build_import_directive(module_,
1515                                                         module_path,
1516                                                         @GlobImport,
1517                                                         view_path.span,
1518                                                         id,
1519                                                         is_public);
1520                         }
1521                     }
1522                 }
1523             }
1524
1525             ViewItemExternCrate(name, _, node_id) => {
1526                 // n.b. we don't need to look at the path option here, because cstore already did
1527                 match self.session.cstore.find_extern_mod_stmt_cnum(node_id) {
1528                     Some(crate_id) => {
1529                         let def_id = DefId { krate: crate_id, node: 0 };
1530                         self.external_exports.insert(def_id);
1531                         let parent_link = ModuleParentLink
1532                             (self.get_module_from_parent(parent), name);
1533                         let external_module = @Module::new(parent_link,
1534                                                           Some(def_id),
1535                                                           NormalModuleKind,
1536                                                           false,
1537                                                           true);
1538
1539                         parent.module().external_module_children
1540                               .borrow_mut().insert(name.name,
1541                                                    external_module);
1542
1543                         self.build_reduced_graph_for_external_crate(
1544                             external_module);
1545                     }
1546                     None => {}  // Ignore.
1547                 }
1548             }
1549         }
1550     }
1551
1552     /// Constructs the reduced graph for one foreign item.
1553     fn build_reduced_graph_for_foreign_item(&mut self,
1554                                             foreign_item: &ForeignItem,
1555                                             parent: ReducedGraphParent,
1556                                             f: |&mut Resolver,
1557                                                 ReducedGraphParent|) {
1558         let name = foreign_item.ident;
1559         let is_public = foreign_item.vis == ast::Public;
1560         let (name_bindings, new_parent) =
1561             self.add_child(name, parent, ForbidDuplicateValues,
1562                            foreign_item.span);
1563
1564         match foreign_item.node {
1565             ForeignItemFn(_, ref generics) => {
1566                 let def = DefFn(local_def(foreign_item.id), UnsafeFn);
1567                 name_bindings.define_value(def, foreign_item.span, is_public);
1568
1569                 self.with_type_parameter_rib(
1570                     HasTypeParameters(generics,
1571                                       foreign_item.id,
1572                                       0,
1573                                       NormalRibKind),
1574                     |this| f(this, new_parent));
1575             }
1576             ForeignItemStatic(_, m) => {
1577                 let def = DefStatic(local_def(foreign_item.id), m);
1578                 name_bindings.define_value(def, foreign_item.span, is_public);
1579
1580                 f(self, new_parent)
1581             }
1582         }
1583     }
1584
1585     fn build_reduced_graph_for_block(&mut self,
1586                                          block: &Block,
1587                                          parent: ReducedGraphParent)
1588                                             -> ReducedGraphParent
1589     {
1590         if self.block_needs_anonymous_module(block) {
1591             let block_id = block.id;
1592
1593             debug!("(building reduced graph for block) creating a new \
1594                     anonymous module for block {}",
1595                    block_id);
1596
1597             let parent_module = self.get_module_from_parent(parent);
1598             let new_module = @Module::new(
1599                 BlockParentLink(parent_module, block_id),
1600                 None,
1601                 AnonymousModuleKind,
1602                 false,
1603                 false);
1604             parent_module.anonymous_children.borrow_mut()
1605                          .insert(block_id, new_module);
1606             ModuleReducedGraphParent(new_module)
1607         } else {
1608             parent
1609         }
1610     }
1611
1612     fn handle_external_def(&mut self,
1613                            def: Def,
1614                            vis: Visibility,
1615                            child_name_bindings: @NameBindings,
1616                            final_ident: &str,
1617                            ident: Ident,
1618                            new_parent: ReducedGraphParent) {
1619         debug!("(building reduced graph for \
1620                 external crate) building external def, priv {:?}",
1621                vis);
1622         let is_public = vis == ast::Public;
1623         let is_exported = is_public && match new_parent {
1624             ModuleReducedGraphParent(module) => {
1625                 match module.def_id.get() {
1626                     None => true,
1627                     Some(did) => self.external_exports.contains(&did)
1628                 }
1629             }
1630         };
1631         if is_exported {
1632             self.external_exports.insert(def_id_of_def(def));
1633         }
1634         match def {
1635           DefMod(def_id) | DefForeignMod(def_id) | DefStruct(def_id) |
1636           DefTy(def_id) => {
1637             let type_def = child_name_bindings.type_def.borrow().clone();
1638             match type_def {
1639               Some(TypeNsDef { module_def: Some(module_def), .. }) => {
1640                 debug!("(building reduced graph for external crate) \
1641                         already created module");
1642                 module_def.def_id.set(Some(def_id));
1643               }
1644               Some(_) | None => {
1645                 debug!("(building reduced graph for \
1646                         external crate) building module \
1647                         {}", final_ident);
1648                 let parent_link = self.get_parent_link(new_parent, ident);
1649
1650                 child_name_bindings.define_module(parent_link,
1651                                                   Some(def_id),
1652                                                   NormalModuleKind,
1653                                                   true,
1654                                                   is_public,
1655                                                   DUMMY_SP);
1656               }
1657             }
1658           }
1659           _ => {}
1660         }
1661
1662         match def {
1663           DefMod(_) | DefForeignMod(_) => {}
1664           DefVariant(_, variant_id, is_struct) => {
1665             debug!("(building reduced graph for external crate) building \
1666                     variant {}",
1667                    final_ident);
1668             // We assume the parent is visible, or else we wouldn't have seen
1669             // it. Also variants are public-by-default if the parent was also
1670             // public.
1671             let is_public = vis != ast::Private;
1672             if is_struct {
1673                 child_name_bindings.define_type(def, DUMMY_SP, is_public);
1674                 self.structs.insert(variant_id);
1675             } else {
1676                 child_name_bindings.define_value(def, DUMMY_SP, is_public);
1677             }
1678           }
1679           DefFn(..) | DefStaticMethod(..) | DefStatic(..) => {
1680             debug!("(building reduced graph for external \
1681                     crate) building value (fn/static) {}", final_ident);
1682             child_name_bindings.define_value(def, DUMMY_SP, is_public);
1683           }
1684           DefTrait(def_id) => {
1685               debug!("(building reduced graph for external \
1686                       crate) building type {}", final_ident);
1687
1688               // If this is a trait, add all the method names
1689               // to the trait info.
1690
1691               let method_def_ids =
1692                 csearch::get_trait_method_def_ids(&self.session.cstore, def_id);
1693               let mut interned_method_names = HashSet::new();
1694               for &method_def_id in method_def_ids.iter() {
1695                   let (method_name, explicit_self) =
1696                       csearch::get_method_name_and_explicit_self(&self.session.cstore,
1697                                                                  method_def_id);
1698
1699                   debug!("(building reduced graph for \
1700                           external crate) ... adding \
1701                           trait method '{}'",
1702                          token::get_ident(method_name));
1703
1704                   // Add it to the trait info if not static.
1705                   if explicit_self != SelfStatic {
1706                       interned_method_names.insert(method_name.name);
1707                   }
1708                   if is_exported {
1709                       self.external_exports.insert(method_def_id);
1710                   }
1711               }
1712               for name in interned_method_names.iter() {
1713                   let mut method_map = self.method_map.borrow_mut();
1714                   if !method_map.contains_key(name) {
1715                       method_map.insert(*name, HashSet::new());
1716                   }
1717                   match method_map.find_mut(name) {
1718                       Some(s) => { s.insert(def_id); },
1719                       _ => fail!("can't happen"),
1720                   }
1721               }
1722
1723               child_name_bindings.define_type(def, DUMMY_SP, is_public);
1724
1725               // Define a module if necessary.
1726               let parent_link = self.get_parent_link(new_parent, ident);
1727               child_name_bindings.set_module_kind(parent_link,
1728                                                   Some(def_id),
1729                                                   TraitModuleKind,
1730                                                   true,
1731                                                   is_public,
1732                                                   DUMMY_SP)
1733           }
1734           DefTy(_) => {
1735               debug!("(building reduced graph for external \
1736                       crate) building type {}", final_ident);
1737
1738               child_name_bindings.define_type(def, DUMMY_SP, is_public);
1739           }
1740           DefStruct(def_id) => {
1741             debug!("(building reduced graph for external \
1742                     crate) building type and value for {}",
1743                    final_ident);
1744             child_name_bindings.define_type(def, DUMMY_SP, is_public);
1745             if csearch::get_struct_fields(&self.session.cstore, def_id).len() == 0 {
1746                 child_name_bindings.define_value(def, DUMMY_SP, is_public);
1747             }
1748             self.structs.insert(def_id);
1749           }
1750           DefMethod(..) => {
1751               debug!("(building reduced graph for external crate) \
1752                       ignoring {:?}", def);
1753               // Ignored; handled elsewhere.
1754           }
1755           DefArg(..) | DefLocal(..) | DefPrimTy(..) |
1756           DefTyParam(..) | DefBinding(..) |
1757           DefUse(..) | DefUpvar(..) | DefRegion(..) |
1758           DefTyParamBinder(..) | DefLabel(..) | DefSelfTy(..) => {
1759             fail!("didn't expect `{:?}`", def);
1760           }
1761         }
1762     }
1763
1764     /// Builds the reduced graph for a single item in an external crate.
1765     fn build_reduced_graph_for_external_crate_def(&mut self,
1766                                                   root: @Module,
1767                                                   def_like: DefLike,
1768                                                   ident: Ident,
1769                                                   visibility: Visibility) {
1770         match def_like {
1771             DlDef(def) => {
1772                 // Add the new child item, if necessary.
1773                 match def {
1774                     DefForeignMod(def_id) => {
1775                         // Foreign modules have no names. Recur and populate
1776                         // eagerly.
1777                         csearch::each_child_of_item(&self.session.cstore,
1778                                                     def_id,
1779                                                     |def_like,
1780                                                      child_ident,
1781                                                      vis| {
1782                             self.build_reduced_graph_for_external_crate_def(
1783                                 root,
1784                                 def_like,
1785                                 child_ident,
1786                                 vis)
1787                         });
1788                     }
1789                     _ => {
1790                         let (child_name_bindings, new_parent) =
1791                             self.add_child(ident,
1792                                            ModuleReducedGraphParent(root),
1793                                            OverwriteDuplicates,
1794                                            DUMMY_SP);
1795
1796                         self.handle_external_def(def,
1797                                                  visibility,
1798                                                  child_name_bindings,
1799                                                  token::get_ident(ident).get(),
1800                                                  ident,
1801                                                  new_parent);
1802                     }
1803                 }
1804             }
1805             DlImpl(def) => {
1806                 // We only process static methods of impls here.
1807                 match csearch::get_type_name_if_impl(&self.session.cstore, def) {
1808                     None => {}
1809                     Some(final_ident) => {
1810                         let static_methods_opt =
1811                             csearch::get_static_methods_if_impl(&self.session.cstore, def);
1812                         match static_methods_opt {
1813                             Some(ref static_methods) if
1814                                 static_methods.len() >= 1 => {
1815                                 debug!("(building reduced graph for \
1816                                         external crate) processing \
1817                                         static methods for type name {}",
1818                                         token::get_ident(final_ident));
1819
1820                                 let (child_name_bindings, new_parent) =
1821                                     self.add_child(
1822                                         final_ident,
1823                                         ModuleReducedGraphParent(root),
1824                                         OverwriteDuplicates,
1825                                         DUMMY_SP);
1826
1827                                 // Process the static methods. First,
1828                                 // create the module.
1829                                 let type_module;
1830                                 let type_def = child_name_bindings.type_def.borrow().clone();
1831                                 match type_def {
1832                                     Some(TypeNsDef {
1833                                         module_def: Some(module_def),
1834                                         ..
1835                                     }) => {
1836                                         // We already have a module. This
1837                                         // is OK.
1838                                         type_module = module_def;
1839
1840                                         // Mark it as an impl module if
1841                                         // necessary.
1842                                         type_module.kind.set(ImplModuleKind);
1843                                     }
1844                                     Some(_) | None => {
1845                                         let parent_link =
1846                                             self.get_parent_link(new_parent,
1847                                                                  final_ident);
1848                                         child_name_bindings.define_module(
1849                                             parent_link,
1850                                             Some(def),
1851                                             ImplModuleKind,
1852                                             true,
1853                                             true,
1854                                             DUMMY_SP);
1855                                         type_module =
1856                                             child_name_bindings.
1857                                                 get_module();
1858                                     }
1859                                 }
1860
1861                                 // Add each static method to the module.
1862                                 let new_parent =
1863                                     ModuleReducedGraphParent(type_module);
1864                                 for static_method_info in
1865                                         static_methods.iter() {
1866                                     let ident = static_method_info.ident;
1867                                     debug!("(building reduced graph for \
1868                                              external crate) creating \
1869                                              static method '{}'",
1870                                            token::get_ident(ident));
1871
1872                                     let (method_name_bindings, _) =
1873                                         self.add_child(ident,
1874                                                        new_parent,
1875                                                        OverwriteDuplicates,
1876                                                        DUMMY_SP);
1877                                     let def = DefFn(
1878                                         static_method_info.def_id,
1879                                         static_method_info.fn_style);
1880
1881                                     method_name_bindings.define_value(
1882                                         def, DUMMY_SP,
1883                                         visibility == ast::Public);
1884                                 }
1885                             }
1886
1887                             // Otherwise, do nothing.
1888                             Some(_) | None => {}
1889                         }
1890                     }
1891                 }
1892             }
1893             DlField => {
1894                 debug!("(building reduced graph for external crate) \
1895                         ignoring field");
1896             }
1897         }
1898     }
1899
1900     /// Builds the reduced graph rooted at the given external module.
1901     fn populate_external_module(&mut self, module: @Module) {
1902         debug!("(populating external module) attempting to populate {}",
1903                self.module_to_str(module));
1904
1905         let def_id = match module.def_id.get() {
1906             None => {
1907                 debug!("(populating external module) ... no def ID!");
1908                 return
1909             }
1910             Some(def_id) => def_id,
1911         };
1912
1913         csearch::each_child_of_item(&self.session.cstore,
1914                                     def_id,
1915                                     |def_like, child_ident, visibility| {
1916             debug!("(populating external module) ... found ident: {}",
1917                    token::get_ident(child_ident));
1918             self.build_reduced_graph_for_external_crate_def(module,
1919                                                             def_like,
1920                                                             child_ident,
1921                                                             visibility)
1922         });
1923         module.populated.set(true)
1924     }
1925
1926     /// Ensures that the reduced graph rooted at the given external module
1927     /// is built, building it if it is not.
1928     fn populate_module_if_necessary(&mut self, module: @Module) {
1929         if !module.populated.get() {
1930             self.populate_external_module(module)
1931         }
1932         assert!(module.populated.get())
1933     }
1934
1935     /// Builds the reduced graph rooted at the 'use' directive for an external
1936     /// crate.
1937     fn build_reduced_graph_for_external_crate(&mut self,
1938                                               root: @Module) {
1939         csearch::each_top_level_item_of_crate(&self.session.cstore,
1940                                               root.def_id
1941                                                   .get()
1942                                                   .unwrap()
1943                                                   .krate,
1944                                               |def_like, ident, visibility| {
1945             self.build_reduced_graph_for_external_crate_def(root,
1946                                                             def_like,
1947                                                             ident,
1948                                                             visibility)
1949         });
1950     }
1951
1952     /// Creates and adds an import directive to the given module.
1953     fn build_import_directive(&mut self,
1954                               module_: @Module,
1955                               module_path: Vec<Ident> ,
1956                               subclass: @ImportDirectiveSubclass,
1957                               span: Span,
1958                               id: NodeId,
1959                               is_public: bool) {
1960         let directive = @ImportDirective::new(module_path,
1961                                               subclass, span, id,
1962                                               is_public);
1963         module_.imports.borrow_mut().push(directive);
1964         // Bump the reference count on the name. Or, if this is a glob, set
1965         // the appropriate flag.
1966
1967         match *subclass {
1968             SingleImport(target, _) => {
1969                 debug!("(building import directive) building import \
1970                         directive: {}::{}",
1971                        self.idents_to_str(directive.module_path.as_slice()),
1972                        token::get_ident(target));
1973
1974                 let mut import_resolutions = module_.import_resolutions
1975                                                     .borrow_mut();
1976                 match import_resolutions.find(&target.name) {
1977                     Some(&resolution) => {
1978                         debug!("(building import directive) bumping \
1979                                 reference");
1980                         resolution.outstanding_references.set(
1981                             resolution.outstanding_references.get() + 1);
1982
1983                         // the source of this name is different now
1984                         resolution.type_id.set(id);
1985                         resolution.value_id.set(id);
1986                         resolution.is_public.set(is_public);
1987                     }
1988                     None => {
1989                         debug!("(building import directive) creating new");
1990                         let resolution = @ImportResolution::new(id, is_public);
1991                         resolution.outstanding_references.set(1);
1992                         import_resolutions.insert(target.name, resolution);
1993                     }
1994                 }
1995             }
1996             GlobImport => {
1997                 // Set the glob flag. This tells us that we don't know the
1998                 // module's exports ahead of time.
1999
2000                 module_.glob_count.set(module_.glob_count.get() + 1);
2001             }
2002         }
2003
2004         self.unresolved_imports += 1;
2005     }
2006
2007     // Import resolution
2008     //
2009     // This is a fixed-point algorithm. We resolve imports until our efforts
2010     // are stymied by an unresolved import; then we bail out of the current
2011     // module and continue. We terminate successfully once no more imports
2012     // remain or unsuccessfully when no forward progress in resolving imports
2013     // is made.
2014
2015     /// Resolves all imports for the crate. This method performs the fixed-
2016     /// point iteration.
2017     fn resolve_imports(&mut self) {
2018         let mut i = 0;
2019         let mut prev_unresolved_imports = 0;
2020         loop {
2021             debug!("(resolving imports) iteration {}, {} imports left",
2022                    i, self.unresolved_imports);
2023
2024             let module_root = self.graph_root.get_module();
2025             self.resolve_imports_for_module_subtree(module_root);
2026
2027             if self.unresolved_imports == 0 {
2028                 debug!("(resolving imports) success");
2029                 break;
2030             }
2031
2032             if self.unresolved_imports == prev_unresolved_imports {
2033                 self.report_unresolved_imports(module_root);
2034                 break;
2035             }
2036
2037             i += 1;
2038             prev_unresolved_imports = self.unresolved_imports;
2039         }
2040     }
2041
2042     /// Attempts to resolve imports for the given module and all of its
2043     /// submodules.
2044     fn resolve_imports_for_module_subtree(&mut self,
2045                                               module_: @Module) {
2046         debug!("(resolving imports for module subtree) resolving {}",
2047                self.module_to_str(module_));
2048         self.resolve_imports_for_module(module_);
2049
2050         self.populate_module_if_necessary(module_);
2051         for (_, &child_node) in module_.children.borrow().iter() {
2052             match child_node.get_module_if_available() {
2053                 None => {
2054                     // Nothing to do.
2055                 }
2056                 Some(child_module) => {
2057                     self.resolve_imports_for_module_subtree(child_module);
2058                 }
2059             }
2060         }
2061
2062         for (_, &child_module) in module_.anonymous_children.borrow().iter() {
2063             self.resolve_imports_for_module_subtree(child_module);
2064         }
2065     }
2066
2067     /// Attempts to resolve imports for the given module only.
2068     fn resolve_imports_for_module(&mut self, module: @Module) {
2069         if module.all_imports_resolved() {
2070             debug!("(resolving imports for module) all imports resolved for \
2071                    {}",
2072                    self.module_to_str(module));
2073             return;
2074         }
2075
2076         let mut imports = module.imports.borrow_mut();
2077         let import_count = imports.len();
2078         while module.resolved_import_count.get() < import_count {
2079             let import_index = module.resolved_import_count.get();
2080             let import_directive = *imports.get(import_index);
2081             match self.resolve_import_for_module(module, import_directive) {
2082                 Failed => {
2083                     // We presumably emitted an error. Continue.
2084                     let msg = format!("failed to resolve import `{}`",
2085                                    self.import_path_to_str(
2086                                        import_directive.module_path
2087                                                        .as_slice(),
2088                                        *import_directive.subclass));
2089                     self.resolve_error(import_directive.span, msg);
2090                 }
2091                 Indeterminate => {
2092                     // Bail out. We'll come around next time.
2093                     break;
2094                 }
2095                 Success(()) => {
2096                     // Good. Continue.
2097                 }
2098             }
2099
2100             module.resolved_import_count
2101                   .set(module.resolved_import_count.get() + 1);
2102         }
2103     }
2104
2105     fn idents_to_str(&mut self, idents: &[Ident]) -> ~str {
2106         let mut first = true;
2107         let mut result = StrBuf::new();
2108         for ident in idents.iter() {
2109             if first {
2110                 first = false
2111             } else {
2112                 result.push_str("::")
2113             }
2114             result.push_str(token::get_ident(*ident).get());
2115         };
2116         result.into_owned()
2117     }
2118
2119     fn path_idents_to_str(&mut self, path: &Path) -> ~str {
2120         let identifiers: Vec<ast::Ident> = path.segments
2121                                              .iter()
2122                                              .map(|seg| seg.identifier)
2123                                              .collect();
2124         self.idents_to_str(identifiers.as_slice())
2125     }
2126
2127     fn import_directive_subclass_to_str(&mut self,
2128                                         subclass: ImportDirectiveSubclass)
2129                                         -> ~str {
2130         match subclass {
2131             SingleImport(_, source) => {
2132                 token::get_ident(source).get().to_str()
2133             }
2134             GlobImport => ~"*"
2135         }
2136     }
2137
2138     fn import_path_to_str(&mut self,
2139                           idents: &[Ident],
2140                           subclass: ImportDirectiveSubclass)
2141                           -> ~str {
2142         if idents.is_empty() {
2143             self.import_directive_subclass_to_str(subclass)
2144         } else {
2145             (format!("{}::{}",
2146                      self.idents_to_str(idents),
2147                      self.import_directive_subclass_to_str(subclass)))
2148         }
2149     }
2150
2151     /// Attempts to resolve the given import. The return value indicates
2152     /// failure if we're certain the name does not exist, indeterminate if we
2153     /// don't know whether the name exists at the moment due to other
2154     /// currently-unresolved imports, or success if we know the name exists.
2155     /// If successful, the resolved bindings are written into the module.
2156     fn resolve_import_for_module(&mut self,
2157                                  module_: @Module,
2158                                  import_directive: @ImportDirective)
2159                                  -> ResolveResult<()> {
2160         let mut resolution_result = Failed;
2161         let module_path = &import_directive.module_path;
2162
2163         debug!("(resolving import for module) resolving import `{}::...` in \
2164                 `{}`",
2165                self.idents_to_str(module_path.as_slice()),
2166                self.module_to_str(module_));
2167
2168         // First, resolve the module path for the directive, if necessary.
2169         let container = if module_path.len() == 0 {
2170             // Use the crate root.
2171             Some((self.graph_root.get_module(), LastMod(AllPublic)))
2172         } else {
2173             match self.resolve_module_path(module_,
2174                                            module_path.as_slice(),
2175                                            DontUseLexicalScope,
2176                                            import_directive.span,
2177                                            ImportSearch) {
2178
2179                 Failed => None,
2180                 Indeterminate => {
2181                     resolution_result = Indeterminate;
2182                     None
2183                 }
2184                 Success(container) => Some(container),
2185             }
2186         };
2187
2188         match container {
2189             None => {}
2190             Some((containing_module, lp)) => {
2191                 // We found the module that the target is contained
2192                 // within. Attempt to resolve the import within it.
2193
2194                 match *import_directive.subclass {
2195                     SingleImport(target, source) => {
2196                         resolution_result =
2197                             self.resolve_single_import(module_,
2198                                                        containing_module,
2199                                                        target,
2200                                                        source,
2201                                                        import_directive,
2202                                                        lp);
2203                     }
2204                     GlobImport => {
2205                         resolution_result =
2206                             self.resolve_glob_import(module_,
2207                                                      containing_module,
2208                                                      import_directive.id,
2209                                                      import_directive.is_public,
2210                                                      lp);
2211                     }
2212                 }
2213             }
2214         }
2215
2216         // Decrement the count of unresolved imports.
2217         match resolution_result {
2218             Success(()) => {
2219                 assert!(self.unresolved_imports >= 1);
2220                 self.unresolved_imports -= 1;
2221             }
2222             _ => {
2223                 // Nothing to do here; just return the error.
2224             }
2225         }
2226
2227         // Decrement the count of unresolved globs if necessary. But only if
2228         // the resolution result is indeterminate -- otherwise we'll stop
2229         // processing imports here. (See the loop in
2230         // resolve_imports_for_module.)
2231
2232         if !resolution_result.indeterminate() {
2233             match *import_directive.subclass {
2234                 GlobImport => {
2235                     assert!(module_.glob_count.get() >= 1);
2236                     module_.glob_count.set(module_.glob_count.get() - 1);
2237                 }
2238                 SingleImport(..) => {
2239                     // Ignore.
2240                 }
2241             }
2242         }
2243
2244         return resolution_result;
2245     }
2246
2247     fn create_name_bindings_from_module(module: @Module) -> NameBindings {
2248         NameBindings {
2249             type_def: RefCell::new(Some(TypeNsDef {
2250                 is_public: false,
2251                 module_def: Some(module),
2252                 type_def: None,
2253                 type_span: None
2254             })),
2255             value_def: RefCell::new(None),
2256         }
2257     }
2258
2259     fn resolve_single_import(&mut self,
2260                              module_: @Module,
2261                              containing_module: @Module,
2262                              target: Ident,
2263                              source: Ident,
2264                              directive: &ImportDirective,
2265                              lp: LastPrivate)
2266                                  -> ResolveResult<()> {
2267         debug!("(resolving single import) resolving `{}` = `{}::{}` from \
2268                 `{}` id {}, last private {:?}",
2269                token::get_ident(target),
2270                self.module_to_str(containing_module),
2271                token::get_ident(source),
2272                self.module_to_str(module_),
2273                directive.id,
2274                lp);
2275
2276         let lp = match lp {
2277             LastMod(lp) => lp,
2278             LastImport{..} => self.session.span_bug(directive.span,
2279                                                     "Not expecting Import here, must be LastMod"),
2280         };
2281
2282         // We need to resolve both namespaces for this to succeed.
2283         //
2284
2285         let mut value_result = UnknownResult;
2286         let mut type_result = UnknownResult;
2287
2288         // Search for direct children of the containing module.
2289         self.populate_module_if_necessary(containing_module);
2290
2291         match containing_module.children.borrow().find(&source.name) {
2292             None => {
2293                 // Continue.
2294             }
2295             Some(child_name_bindings) => {
2296                 if child_name_bindings.defined_in_namespace(ValueNS) {
2297                     debug!("(resolving single import) found value binding");
2298                     value_result = BoundResult(containing_module,
2299                                                *child_name_bindings);
2300                 }
2301                 if child_name_bindings.defined_in_namespace(TypeNS) {
2302                     debug!("(resolving single import) found type binding");
2303                     type_result = BoundResult(containing_module,
2304                                               *child_name_bindings);
2305                 }
2306             }
2307         }
2308
2309         // Unless we managed to find a result in both namespaces (unlikely),
2310         // search imports as well.
2311         let mut value_used_reexport = false;
2312         let mut type_used_reexport = false;
2313         match (value_result, type_result) {
2314             (BoundResult(..), BoundResult(..)) => {} // Continue.
2315             _ => {
2316                 // If there is an unresolved glob at this point in the
2317                 // containing module, bail out. We don't know enough to be
2318                 // able to resolve this import.
2319
2320                 if containing_module.glob_count.get() > 0 {
2321                     debug!("(resolving single import) unresolved glob; \
2322                             bailing out");
2323                     return Indeterminate;
2324                 }
2325
2326                 // Now search the exported imports within the containing
2327                 // module.
2328
2329                 let import_resolutions = containing_module.import_resolutions
2330                                                           .borrow();
2331                 match import_resolutions.find(&source.name) {
2332                     None => {
2333                         debug!("(resolving single import) no import");
2334                         // The containing module definitely doesn't have an
2335                         // exported import with the name in question. We can
2336                         // therefore accurately report that the names are
2337                         // unbound.
2338
2339                         if value_result.is_unknown() {
2340                             value_result = UnboundResult;
2341                         }
2342                         if type_result.is_unknown() {
2343                             type_result = UnboundResult;
2344                         }
2345                     }
2346                     Some(import_resolution)
2347                             if import_resolution.outstanding_references.get()
2348                                 == 0 => {
2349
2350                         fn get_binding(this: &mut Resolver,
2351                                        import_resolution: @ImportResolution,
2352                                        namespace: Namespace)
2353                                     -> NamespaceResult {
2354
2355                             // Import resolutions must be declared with "pub"
2356                             // in order to be exported.
2357                             if !import_resolution.is_public.get() {
2358                                 return UnboundResult;
2359                             }
2360
2361                             match (*import_resolution).
2362                                     target_for_namespace(namespace) {
2363                                 None => {
2364                                     return UnboundResult;
2365                                 }
2366                                 Some(target) => {
2367                                     debug!("(resolving single import) found \
2368                                             import in ns {:?}", namespace);
2369                                     let id = import_resolution.id(namespace);
2370                                     this.used_imports.insert((id, namespace));
2371                                     return BoundResult(target.target_module,
2372                                                        target.bindings);
2373                                 }
2374                             }
2375                         }
2376
2377                         // The name is an import which has been fully
2378                         // resolved. We can, therefore, just follow it.
2379                         if value_result.is_unknown() {
2380                             value_result = get_binding(self, *import_resolution,
2381                                                        ValueNS);
2382                             value_used_reexport = import_resolution.is_public.get();
2383                         }
2384                         if type_result.is_unknown() {
2385                             type_result = get_binding(self, *import_resolution,
2386                                                       TypeNS);
2387                             type_used_reexport = import_resolution.is_public.get();
2388                         }
2389
2390                     }
2391                     Some(_) => {
2392                         // The import is unresolved. Bail out.
2393                         debug!("(resolving single import) unresolved import; \
2394                                 bailing out");
2395                         return Indeterminate;
2396                     }
2397                 }
2398             }
2399         }
2400
2401         // If we didn't find a result in the type namespace, search the
2402         // external modules.
2403         let mut value_used_public = false;
2404         let mut type_used_public = false;
2405         match type_result {
2406             BoundResult(..) => {}
2407             _ => {
2408                 match containing_module.external_module_children.borrow_mut()
2409                                        .find_copy(&source.name) {
2410                     None => {} // Continue.
2411                     Some(module) => {
2412                         debug!("(resolving single import) found external \
2413                                 module");
2414                         let name_bindings =
2415                             @Resolver::create_name_bindings_from_module(
2416                                 module);
2417                         type_result = BoundResult(containing_module,
2418                                                   name_bindings);
2419                         type_used_public = true;
2420                     }
2421                 }
2422             }
2423         }
2424
2425         // We've successfully resolved the import. Write the results in.
2426         let import_resolution = {
2427             let import_resolutions = module_.import_resolutions.borrow();
2428             assert!(import_resolutions.contains_key(&target.name));
2429             import_resolutions.get_copy(&target.name)
2430         };
2431
2432         match value_result {
2433             BoundResult(target_module, name_bindings) => {
2434                 debug!("(resolving single import) found value target");
2435                 *import_resolution.value_target.borrow_mut() =
2436                     Some(Target::new(target_module, name_bindings));
2437                 import_resolution.value_id.set(directive.id);
2438                 value_used_public = name_bindings.defined_in_public_namespace(ValueNS);
2439             }
2440             UnboundResult => { /* Continue. */ }
2441             UnknownResult => {
2442                 fail!("value result should be known at this point");
2443             }
2444         }
2445         match type_result {
2446             BoundResult(target_module, name_bindings) => {
2447                 debug!("(resolving single import) found type target: {:?}",
2448                        { name_bindings.type_def.borrow().clone().unwrap().type_def });
2449                 *import_resolution.type_target.borrow_mut() =
2450                     Some(Target::new(target_module, name_bindings));
2451                 import_resolution.type_id.set(directive.id);
2452                 type_used_public = name_bindings.defined_in_public_namespace(TypeNS);
2453             }
2454             UnboundResult => { /* Continue. */ }
2455             UnknownResult => {
2456                 fail!("type result should be known at this point");
2457             }
2458         }
2459
2460         if value_result.is_unbound() && type_result.is_unbound() {
2461             let msg = format!("unresolved import: there is no \
2462                                `{}` in `{}`",
2463                               token::get_ident(source),
2464                               self.module_to_str(containing_module));
2465             self.resolve_error(directive.span, msg);
2466             return Failed;
2467         }
2468         let value_used_public = value_used_reexport || value_used_public;
2469         let type_used_public = type_used_reexport || type_used_public;
2470
2471         assert!(import_resolution.outstanding_references.get() >= 1);
2472         import_resolution.outstanding_references.set(
2473             import_resolution.outstanding_references.get() - 1);
2474
2475         // record what this import resolves to for later uses in documentation,
2476         // this may resolve to either a value or a type, but for documentation
2477         // purposes it's good enough to just favor one over the other.
2478         let value_private = match *import_resolution.value_target.borrow() {
2479             Some(target) => {
2480                 let def = target.bindings.def_for_namespace(ValueNS).unwrap();
2481                 self.def_map.borrow_mut().insert(directive.id, def);
2482                 let did = def_id_of_def(def);
2483                 if value_used_public {Some(lp)} else {Some(DependsOn(did))}
2484             },
2485             // AllPublic here and below is a dummy value, it should never be used because
2486             // _exists is false.
2487             None => None,
2488         };
2489         let type_private = match *import_resolution.type_target.borrow() {
2490             Some(target) => {
2491                 let def = target.bindings.def_for_namespace(TypeNS).unwrap();
2492                 self.def_map.borrow_mut().insert(directive.id, def);
2493                 let did = def_id_of_def(def);
2494                 if type_used_public {Some(lp)} else {Some(DependsOn(did))}
2495             },
2496             None => None,
2497         };
2498
2499         self.last_private.insert(directive.id, LastImport{value_priv: value_private,
2500                                                           value_used: Used,
2501                                                           type_priv: type_private,
2502                                                           type_used: Used});
2503
2504         debug!("(resolving single import) successfully resolved import");
2505         return Success(());
2506     }
2507
2508     // Resolves a glob import. Note that this function cannot fail; it either
2509     // succeeds or bails out (as importing * from an empty module or a module
2510     // that exports nothing is valid).
2511     fn resolve_glob_import(&mut self,
2512                            module_: @Module,
2513                            containing_module: @Module,
2514                            id: NodeId,
2515                            is_public: bool,
2516                            lp: LastPrivate)
2517                            -> ResolveResult<()> {
2518         // This function works in a highly imperative manner; it eagerly adds
2519         // everything it can to the list of import resolutions of the module
2520         // node.
2521         debug!("(resolving glob import) resolving glob import {}", id);
2522
2523         // We must bail out if the node has unresolved imports of any kind
2524         // (including globs).
2525         if !(*containing_module).all_imports_resolved() {
2526             debug!("(resolving glob import) target module has unresolved \
2527                     imports; bailing out");
2528             return Indeterminate;
2529         }
2530
2531         assert_eq!(containing_module.glob_count.get(), 0);
2532
2533         // Add all resolved imports from the containing module.
2534         let import_resolutions = containing_module.import_resolutions
2535                                                   .borrow();
2536         for (ident, target_import_resolution) in import_resolutions.iter() {
2537             debug!("(resolving glob import) writing module resolution \
2538                     {:?} into `{}`",
2539                    target_import_resolution.type_target.borrow().is_none(),
2540                    self.module_to_str(module_));
2541
2542             if !target_import_resolution.is_public.get() {
2543                 debug!("(resolving glob import) nevermind, just kidding");
2544                 continue
2545             }
2546
2547             // Here we merge two import resolutions.
2548             let mut import_resolutions = module_.import_resolutions.borrow_mut();
2549             match import_resolutions.find(ident) {
2550                 None => {
2551                     // Simple: just copy the old import resolution.
2552                     let new_import_resolution =
2553                         @ImportResolution::new(id, is_public);
2554                     *new_import_resolution.value_target.borrow_mut() =
2555                         get(&target_import_resolution.value_target);
2556                     *new_import_resolution.type_target.borrow_mut() =
2557                         get(&target_import_resolution.type_target);
2558
2559                     import_resolutions.insert
2560                         (*ident, new_import_resolution);
2561                 }
2562                 Some(&dest_import_resolution) => {
2563                     // Merge the two import resolutions at a finer-grained
2564                     // level.
2565
2566                     match *target_import_resolution.value_target.borrow() {
2567                         None => {
2568                             // Continue.
2569                         }
2570                         Some(value_target) => {
2571                             *dest_import_resolution.value_target.borrow_mut() = Some(value_target);
2572                         }
2573                     }
2574                     match *target_import_resolution.type_target.borrow() {
2575                         None => {
2576                             // Continue.
2577                         }
2578                         Some(type_target) => {
2579                             *dest_import_resolution.type_target.borrow_mut() = Some(type_target);
2580                         }
2581                     }
2582                     dest_import_resolution.is_public.set(is_public);
2583                 }
2584             }
2585         }
2586
2587         // Add all children from the containing module.
2588         self.populate_module_if_necessary(containing_module);
2589
2590         for (&name, name_bindings) in containing_module.children
2591                                                        .borrow().iter() {
2592             self.merge_import_resolution(module_, containing_module,
2593                                          id, is_public,
2594                                          name, *name_bindings);
2595         }
2596
2597         // Add external module children from the containing module.
2598         for (&name, module) in containing_module.external_module_children
2599                                                 .borrow().iter() {
2600             let name_bindings =
2601                 @Resolver::create_name_bindings_from_module(*module);
2602             self.merge_import_resolution(module_, containing_module,
2603                                          id, is_public,
2604                                          name, name_bindings);
2605         }
2606
2607         // Record the destination of this import
2608         match containing_module.def_id.get() {
2609             Some(did) => {
2610                 self.def_map.borrow_mut().insert(id, DefMod(did));
2611                 self.last_private.insert(id, lp);
2612             }
2613             None => {}
2614         }
2615
2616         debug!("(resolving glob import) successfully resolved import");
2617         return Success(());
2618     }
2619
2620     fn merge_import_resolution(&mut self,
2621                                module_: @Module,
2622                                containing_module: @Module,
2623                                id: NodeId,
2624                                is_public: bool,
2625                                name: Name,
2626                                name_bindings: @NameBindings) {
2627         let dest_import_resolution;
2628         let mut import_resolutions = module_.import_resolutions.borrow_mut();
2629         match import_resolutions.find(&name) {
2630             None => {
2631                 // Create a new import resolution from this child.
2632                 dest_import_resolution =
2633                     @ImportResolution::new(id, is_public);
2634                 import_resolutions.insert(name,
2635                                                 dest_import_resolution);
2636             }
2637             Some(&existing_import_resolution) => {
2638                 dest_import_resolution = existing_import_resolution;
2639             }
2640         }
2641
2642         debug!("(resolving glob import) writing resolution `{}` in `{}` \
2643                to `{}`",
2644                token::get_name(name).get().to_str(),
2645                self.module_to_str(containing_module),
2646                self.module_to_str(module_));
2647
2648         // Merge the child item into the import resolution.
2649         if name_bindings.defined_in_public_namespace(ValueNS) {
2650             debug!("(resolving glob import) ... for value target");
2651             *dest_import_resolution.value_target.borrow_mut() =
2652                 Some(Target::new(containing_module, name_bindings));
2653             dest_import_resolution.value_id.set(id);
2654         }
2655         if name_bindings.defined_in_public_namespace(TypeNS) {
2656             debug!("(resolving glob import) ... for type target");
2657             *dest_import_resolution.type_target.borrow_mut() =
2658                 Some(Target::new(containing_module, name_bindings));
2659             dest_import_resolution.type_id.set(id);
2660         }
2661         dest_import_resolution.is_public.set(is_public);
2662     }
2663
2664     /// Resolves the given module path from the given root `module_`.
2665     fn resolve_module_path_from_root(&mut self,
2666                                      module_: @Module,
2667                                      module_path: &[Ident],
2668                                      index: uint,
2669                                      span: Span,
2670                                      name_search_type: NameSearchType,
2671                                      lp: LastPrivate)
2672                                 -> ResolveResult<(@Module, LastPrivate)> {
2673         let mut search_module = module_;
2674         let mut index = index;
2675         let module_path_len = module_path.len();
2676         let mut closest_private = lp;
2677
2678         // Resolve the module part of the path. This does not involve looking
2679         // upward though scope chains; we simply resolve names directly in
2680         // modules as we go.
2681         while index < module_path_len {
2682             let name = module_path[index];
2683             match self.resolve_name_in_module(search_module,
2684                                               name,
2685                                               TypeNS,
2686                                               name_search_type,
2687                                               false) {
2688                 Failed => {
2689                     let segment_name = token::get_ident(name);
2690                     let module_name = self.module_to_str(search_module);
2691                     if "???" == module_name {
2692                         let span = Span {
2693                             lo: span.lo,
2694                             hi: span.lo + Pos::from_uint(segment_name.get().len()),
2695                             expn_info: span.expn_info,
2696                         };
2697                         self.resolve_error(span,
2698                                               format!("unresolved import. maybe \
2699                                                     a missing `extern crate \
2700                                                     {}`?",
2701                                                     segment_name));
2702                         return Failed;
2703                     }
2704                     self.resolve_error(span, format!("unresolved import: could not find `{}` in \
2705                                                      `{}`.", segment_name, module_name));
2706                     return Failed;
2707                 }
2708                 Indeterminate => {
2709                     debug!("(resolving module path for import) module \
2710                             resolution is indeterminate: {}",
2711                             token::get_ident(name));
2712                     return Indeterminate;
2713                 }
2714                 Success((target, used_proxy)) => {
2715                     // Check to see whether there are type bindings, and, if
2716                     // so, whether there is a module within.
2717                     match *target.bindings.type_def.borrow() {
2718                         Some(type_def) => {
2719                             match type_def.module_def {
2720                                 None => {
2721                                     // Not a module.
2722                                     self.resolve_error(span, format!("not a module `{}`",
2723                                                                  token::get_ident(name)));
2724                                     return Failed;
2725                                 }
2726                                 Some(module_def) => {
2727                                     // If we're doing the search for an
2728                                     // import, do not allow traits and impls
2729                                     // to be selected.
2730                                     match (name_search_type,
2731                                            module_def.kind.get()) {
2732                                         (ImportSearch, TraitModuleKind) |
2733                                         (ImportSearch, ImplModuleKind) => {
2734                                             self.resolve_error(
2735                                                 span,
2736                                                 "cannot import from a trait \
2737                                                  or type implementation");
2738                                             return Failed;
2739                                         }
2740                                         (_, _) => {
2741                                             search_module = module_def;
2742
2743                                             // Keep track of the closest
2744                                             // private module used when
2745                                             // resolving this import chain.
2746                                             if !used_proxy &&
2747                                                !search_module.is_public {
2748                                                 match search_module.def_id
2749                                                                    .get() {
2750                                                     Some(did) => {
2751                                                         closest_private =
2752                                                             LastMod(DependsOn(did));
2753                                                     }
2754                                                     None => {}
2755                                                 }
2756                                             }
2757                                         }
2758                                     }
2759                                 }
2760                             }
2761                         }
2762                         None => {
2763                             // There are no type bindings at all.
2764                             self.resolve_error(span,
2765                                                   format!("not a module `{}`",
2766                                                        token::get_ident(name)));
2767                             return Failed;
2768                         }
2769                     }
2770                 }
2771             }
2772
2773             index += 1;
2774         }
2775
2776         return Success((search_module, closest_private));
2777     }
2778
2779     /// Attempts to resolve the module part of an import directive or path
2780     /// rooted at the given module.
2781     ///
2782     /// On success, returns the resolved module, and the closest *private*
2783     /// module found to the destination when resolving this path.
2784     fn resolve_module_path(&mut self,
2785                            module_: @Module,
2786                            module_path: &[Ident],
2787                            use_lexical_scope: UseLexicalScopeFlag,
2788                            span: Span,
2789                            name_search_type: NameSearchType)
2790                                -> ResolveResult<(@Module, LastPrivate)> {
2791         let module_path_len = module_path.len();
2792         assert!(module_path_len > 0);
2793
2794         debug!("(resolving module path for import) processing `{}` rooted at \
2795                `{}`",
2796                self.idents_to_str(module_path),
2797                self.module_to_str(module_));
2798
2799         // Resolve the module prefix, if any.
2800         let module_prefix_result = self.resolve_module_prefix(module_,
2801                                                               module_path);
2802
2803         let search_module;
2804         let start_index;
2805         let last_private;
2806         match module_prefix_result {
2807             Failed => {
2808                 let mpath = self.idents_to_str(module_path);
2809                 match mpath.rfind(':') {
2810                     Some(idx) => {
2811                         self.resolve_error(span, format!("unresolved import: could not find `{}` \
2812                                                          in `{}`",
2813                                                          // idx +- 1 to account for the colons
2814                                                          // on either side
2815                                                          mpath.slice_from(idx + 1),
2816                                                          mpath.slice_to(idx - 1)));
2817                     },
2818                     None => (),
2819                 };
2820                 return Failed;
2821             }
2822             Indeterminate => {
2823                 debug!("(resolving module path for import) indeterminate; \
2824                         bailing");
2825                 return Indeterminate;
2826             }
2827             Success(NoPrefixFound) => {
2828                 // There was no prefix, so we're considering the first element
2829                 // of the path. How we handle this depends on whether we were
2830                 // instructed to use lexical scope or not.
2831                 match use_lexical_scope {
2832                     DontUseLexicalScope => {
2833                         // This is a crate-relative path. We will start the
2834                         // resolution process at index zero.
2835                         search_module = self.graph_root.get_module();
2836                         start_index = 0;
2837                         last_private = LastMod(AllPublic);
2838                     }
2839                     UseLexicalScope => {
2840                         // This is not a crate-relative path. We resolve the
2841                         // first component of the path in the current lexical
2842                         // scope and then proceed to resolve below that.
2843                         let result = self.resolve_module_in_lexical_scope(
2844                             module_,
2845                             module_path[0]);
2846                         match result {
2847                             Failed => {
2848                                 self.resolve_error(span, "unresolved name");
2849                                 return Failed;
2850                             }
2851                             Indeterminate => {
2852                                 debug!("(resolving module path for import) \
2853                                         indeterminate; bailing");
2854                                 return Indeterminate;
2855                             }
2856                             Success(containing_module) => {
2857                                 search_module = containing_module;
2858                                 start_index = 1;
2859                                 last_private = LastMod(AllPublic);
2860                             }
2861                         }
2862                     }
2863                 }
2864             }
2865             Success(PrefixFound(containing_module, index)) => {
2866                 search_module = containing_module;
2867                 start_index = index;
2868                 last_private = LastMod(DependsOn(containing_module.def_id
2869                                                                   .get()
2870                                                                   .unwrap()));
2871             }
2872         }
2873
2874         self.resolve_module_path_from_root(search_module,
2875                                            module_path,
2876                                            start_index,
2877                                            span,
2878                                            name_search_type,
2879                                            last_private)
2880     }
2881
2882     /// Invariant: This must only be called during main resolution, not during
2883     /// import resolution.
2884     fn resolve_item_in_lexical_scope(&mut self,
2885                                      module_: @Module,
2886                                      name: Ident,
2887                                      namespace: Namespace,
2888                                      search_through_modules:
2889                                      SearchThroughModulesFlag)
2890                                     -> ResolveResult<(Target, bool)> {
2891         debug!("(resolving item in lexical scope) resolving `{}` in \
2892                 namespace {:?} in `{}`",
2893                token::get_ident(name),
2894                namespace,
2895                self.module_to_str(module_));
2896
2897         // The current module node is handled specially. First, check for
2898         // its immediate children.
2899         self.populate_module_if_necessary(module_);
2900
2901         match module_.children.borrow().find(&name.name) {
2902             Some(name_bindings)
2903                     if name_bindings.defined_in_namespace(namespace) => {
2904                 debug!("top name bindings succeeded");
2905                 return Success((Target::new(module_, *name_bindings),
2906                                false));
2907             }
2908             Some(_) | None => { /* Not found; continue. */ }
2909         }
2910
2911         // Now check for its import directives. We don't have to have resolved
2912         // all its imports in the usual way; this is because chains of
2913         // adjacent import statements are processed as though they mutated the
2914         // current scope.
2915         match module_.import_resolutions.borrow().find(&name.name) {
2916             None => {
2917                 // Not found; continue.
2918             }
2919             Some(import_resolution) => {
2920                 match (*import_resolution).target_for_namespace(namespace) {
2921                     None => {
2922                         // Not found; continue.
2923                         debug!("(resolving item in lexical scope) found \
2924                                 import resolution, but not in namespace {:?}",
2925                                namespace);
2926                     }
2927                     Some(target) => {
2928                         debug!("(resolving item in lexical scope) using \
2929                                 import resolution");
2930                         self.used_imports.insert((import_resolution.id(namespace), namespace));
2931                         return Success((target, false));
2932                     }
2933                 }
2934             }
2935         }
2936
2937         // Search for external modules.
2938         if namespace == TypeNS {
2939             match module_.external_module_children.borrow().find_copy(&name.name) {
2940                 None => {}
2941                 Some(module) => {
2942                     let name_bindings =
2943                         @Resolver::create_name_bindings_from_module(module);
2944                     debug!("lower name bindings succeeded");
2945                     return Success((Target::new(module_, name_bindings), false));
2946                 }
2947             }
2948         }
2949
2950         // Finally, proceed up the scope chain looking for parent modules.
2951         let mut search_module = module_;
2952         loop {
2953             // Go to the next parent.
2954             match search_module.parent_link {
2955                 NoParentLink => {
2956                     // No more parents. This module was unresolved.
2957                     debug!("(resolving item in lexical scope) unresolved \
2958                             module");
2959                     return Failed;
2960                 }
2961                 ModuleParentLink(parent_module_node, _) => {
2962                     match search_through_modules {
2963                         DontSearchThroughModules => {
2964                             match search_module.kind.get() {
2965                                 NormalModuleKind => {
2966                                     // We stop the search here.
2967                                     debug!("(resolving item in lexical \
2968                                             scope) unresolved module: not \
2969                                             searching through module \
2970                                             parents");
2971                                     return Failed;
2972                                 }
2973                                 ExternModuleKind |
2974                                 TraitModuleKind |
2975                                 ImplModuleKind |
2976                                 AnonymousModuleKind => {
2977                                     search_module = parent_module_node;
2978                                 }
2979                             }
2980                         }
2981                         SearchThroughModules => {
2982                             search_module = parent_module_node;
2983                         }
2984                     }
2985                 }
2986                 BlockParentLink(parent_module_node, _) => {
2987                     search_module = parent_module_node;
2988                 }
2989             }
2990
2991             // Resolve the name in the parent module.
2992             match self.resolve_name_in_module(search_module,
2993                                               name,
2994                                               namespace,
2995                                               PathSearch,
2996                                               true) {
2997                 Failed => {
2998                     // Continue up the search chain.
2999                 }
3000                 Indeterminate => {
3001                     // We couldn't see through the higher scope because of an
3002                     // unresolved import higher up. Bail.
3003
3004                     debug!("(resolving item in lexical scope) indeterminate \
3005                             higher scope; bailing");
3006                     return Indeterminate;
3007                 }
3008                 Success((target, used_reexport)) => {
3009                     // We found the module.
3010                     debug!("(resolving item in lexical scope) found name \
3011                             in module, done");
3012                     return Success((target, used_reexport));
3013                 }
3014             }
3015         }
3016     }
3017
3018     /// Resolves a module name in the current lexical scope.
3019     fn resolve_module_in_lexical_scope(&mut self,
3020                                        module_: @Module,
3021                                        name: Ident)
3022                                 -> ResolveResult<@Module> {
3023         // If this module is an anonymous module, resolve the item in the
3024         // lexical scope. Otherwise, resolve the item from the crate root.
3025         let resolve_result = self.resolve_item_in_lexical_scope(
3026             module_, name, TypeNS, DontSearchThroughModules);
3027         match resolve_result {
3028             Success((target, _)) => {
3029                 let bindings = &*target.bindings;
3030                 match *bindings.type_def.borrow() {
3031                     Some(type_def) => {
3032                         match type_def.module_def {
3033                             None => {
3034                                 error!("!!! (resolving module in lexical \
3035                                         scope) module wasn't actually a \
3036                                         module!");
3037                                 return Failed;
3038                             }
3039                             Some(module_def) => {
3040                                 return Success(module_def);
3041                             }
3042                         }
3043                     }
3044                     None => {
3045                         error!("!!! (resolving module in lexical scope) module
3046                                 wasn't actually a module!");
3047                         return Failed;
3048                     }
3049                 }
3050             }
3051             Indeterminate => {
3052                 debug!("(resolving module in lexical scope) indeterminate; \
3053                         bailing");
3054                 return Indeterminate;
3055             }
3056             Failed => {
3057                 debug!("(resolving module in lexical scope) failed to \
3058                         resolve");
3059                 return Failed;
3060             }
3061         }
3062     }
3063
3064     /// Returns the nearest normal module parent of the given module.
3065     fn get_nearest_normal_module_parent(&mut self, module_: @Module)
3066                                             -> Option<@Module> {
3067         let mut module_ = module_;
3068         loop {
3069             match module_.parent_link {
3070                 NoParentLink => return None,
3071                 ModuleParentLink(new_module, _) |
3072                 BlockParentLink(new_module, _) => {
3073                     match new_module.kind.get() {
3074                         NormalModuleKind => return Some(new_module),
3075                         ExternModuleKind |
3076                         TraitModuleKind |
3077                         ImplModuleKind |
3078                         AnonymousModuleKind => module_ = new_module,
3079                     }
3080                 }
3081             }
3082         }
3083     }
3084
3085     /// Returns the nearest normal module parent of the given module, or the
3086     /// module itself if it is a normal module.
3087     fn get_nearest_normal_module_parent_or_self(&mut self, module_: @Module)
3088                                                 -> @Module {
3089         match module_.kind.get() {
3090             NormalModuleKind => return module_,
3091             ExternModuleKind |
3092             TraitModuleKind |
3093             ImplModuleKind |
3094             AnonymousModuleKind => {
3095                 match self.get_nearest_normal_module_parent(module_) {
3096                     None => module_,
3097                     Some(new_module) => new_module
3098                 }
3099             }
3100         }
3101     }
3102
3103     /// Resolves a "module prefix". A module prefix is one or both of (a) `self::`;
3104     /// (b) some chain of `super::`.
3105     /// grammar: (SELF MOD_SEP ) ? (SUPER MOD_SEP) *
3106     fn resolve_module_prefix(&mut self,
3107                              module_: @Module,
3108                              module_path: &[Ident])
3109                                  -> ResolveResult<ModulePrefixResult> {
3110         // Start at the current module if we see `self` or `super`, or at the
3111         // top of the crate otherwise.
3112         let mut containing_module;
3113         let mut i;
3114         let first_module_path_string = token::get_ident(module_path[0]);
3115         if "self" == first_module_path_string.get() {
3116             containing_module =
3117                 self.get_nearest_normal_module_parent_or_self(module_);
3118             i = 1;
3119         } else if "super" == first_module_path_string.get() {
3120             containing_module =
3121                 self.get_nearest_normal_module_parent_or_self(module_);
3122             i = 0;  // We'll handle `super` below.
3123         } else {
3124             return Success(NoPrefixFound);
3125         }
3126
3127         // Now loop through all the `super`s we find.
3128         while i < module_path.len() {
3129             let string = token::get_ident(module_path[i]);
3130             if "super" != string.get() {
3131                 break
3132             }
3133             debug!("(resolving module prefix) resolving `super` at {}",
3134                    self.module_to_str(containing_module));
3135             match self.get_nearest_normal_module_parent(containing_module) {
3136                 None => return Failed,
3137                 Some(new_module) => {
3138                     containing_module = new_module;
3139                     i += 1;
3140                 }
3141             }
3142         }
3143
3144         debug!("(resolving module prefix) finished resolving prefix at {}",
3145                self.module_to_str(containing_module));
3146
3147         return Success(PrefixFound(containing_module, i));
3148     }
3149
3150     /// Attempts to resolve the supplied name in the given module for the
3151     /// given namespace. If successful, returns the target corresponding to
3152     /// the name.
3153     ///
3154     /// The boolean returned on success is an indicator of whether this lookup
3155     /// passed through a public re-export proxy.
3156     fn resolve_name_in_module(&mut self,
3157                               module_: @Module,
3158                               name: Ident,
3159                               namespace: Namespace,
3160                               name_search_type: NameSearchType,
3161                               allow_private_imports: bool)
3162                               -> ResolveResult<(Target, bool)> {
3163         debug!("(resolving name in module) resolving `{}` in `{}`",
3164                token::get_ident(name),
3165                self.module_to_str(module_));
3166
3167         // First, check the direct children of the module.
3168         self.populate_module_if_necessary(module_);
3169
3170         match module_.children.borrow().find(&name.name) {
3171             Some(name_bindings)
3172                     if name_bindings.defined_in_namespace(namespace) => {
3173                 debug!("(resolving name in module) found node as child");
3174                 return Success((Target::new(module_, *name_bindings),
3175                                false));
3176             }
3177             Some(_) | None => {
3178                 // Continue.
3179             }
3180         }
3181
3182         // Next, check the module's imports if necessary.
3183
3184         // If this is a search of all imports, we should be done with glob
3185         // resolution at this point.
3186         if name_search_type == PathSearch {
3187             assert_eq!(module_.glob_count.get(), 0);
3188         }
3189
3190         // Check the list of resolved imports.
3191         match module_.import_resolutions.borrow().find(&name.name) {
3192             Some(import_resolution) if allow_private_imports ||
3193                                        import_resolution.is_public.get() => {
3194
3195                 if import_resolution.is_public.get() &&
3196                         import_resolution.outstanding_references.get() != 0 {
3197                     debug!("(resolving name in module) import \
3198                            unresolved; bailing out");
3199                     return Indeterminate;
3200                 }
3201                 match import_resolution.target_for_namespace(namespace) {
3202                     None => {
3203                         debug!("(resolving name in module) name found, \
3204                                 but not in namespace {:?}",
3205                                namespace);
3206                     }
3207                     Some(target) => {
3208                         debug!("(resolving name in module) resolved to \
3209                                 import");
3210                         self.used_imports.insert((import_resolution.id(namespace), namespace));
3211                         return Success((target, true));
3212                     }
3213                 }
3214             }
3215             Some(..) | None => {} // Continue.
3216         }
3217
3218         // Finally, search through external children.
3219         if namespace == TypeNS {
3220             match module_.external_module_children.borrow().find_copy(&name.name) {
3221                 None => {}
3222                 Some(module) => {
3223                     let name_bindings =
3224                         @Resolver::create_name_bindings_from_module(module);
3225                     return Success((Target::new(module_, name_bindings), false));
3226                 }
3227             }
3228         }
3229
3230         // We're out of luck.
3231         debug!("(resolving name in module) failed to resolve `{}`",
3232                token::get_ident(name));
3233         return Failed;
3234     }
3235
3236     fn report_unresolved_imports(&mut self, module_: @Module) {
3237         let index = module_.resolved_import_count.get();
3238         let imports = module_.imports.borrow();
3239         let import_count = imports.len();
3240         if index != import_count {
3241             let sn = self.session
3242                          .codemap()
3243                          .span_to_snippet(imports.get(index).span)
3244                          .unwrap();
3245             if sn.contains("::") {
3246                 self.resolve_error(imports.get(index).span,
3247                                    "unresolved import");
3248             } else {
3249                 let err = format!("unresolved import (maybe you meant `{}::*`?)",
3250                                sn.slice(0, sn.len()));
3251                 self.resolve_error(imports.get(index).span, err);
3252             }
3253         }
3254
3255         // Descend into children and anonymous children.
3256         self.populate_module_if_necessary(module_);
3257
3258         for (_, &child_node) in module_.children.borrow().iter() {
3259             match child_node.get_module_if_available() {
3260                 None => {
3261                     // Continue.
3262                 }
3263                 Some(child_module) => {
3264                     self.report_unresolved_imports(child_module);
3265                 }
3266             }
3267         }
3268
3269         for (_, &module_) in module_.anonymous_children.borrow().iter() {
3270             self.report_unresolved_imports(module_);
3271         }
3272     }
3273
3274     // Export recording
3275     //
3276     // This pass simply determines what all "export" keywords refer to and
3277     // writes the results into the export map.
3278     //
3279     // FIXME #4953 This pass will be removed once exports change to per-item.
3280     // Then this operation can simply be performed as part of item (or import)
3281     // processing.
3282
3283     fn record_exports(&mut self) {
3284         let root_module = self.graph_root.get_module();
3285         self.record_exports_for_module_subtree(root_module);
3286     }
3287
3288     fn record_exports_for_module_subtree(&mut self,
3289                                              module_: @Module) {
3290         // If this isn't a local krate, then bail out. We don't need to record
3291         // exports for nonlocal crates.
3292
3293         match module_.def_id.get() {
3294             Some(def_id) if def_id.krate == LOCAL_CRATE => {
3295                 // OK. Continue.
3296                 debug!("(recording exports for module subtree) recording \
3297                         exports for local module `{}`",
3298                        self.module_to_str(module_));
3299             }
3300             None => {
3301                 // Record exports for the root module.
3302                 debug!("(recording exports for module subtree) recording \
3303                         exports for root module `{}`",
3304                        self.module_to_str(module_));
3305             }
3306             Some(_) => {
3307                 // Bail out.
3308                 debug!("(recording exports for module subtree) not recording \
3309                         exports for `{}`",
3310                        self.module_to_str(module_));
3311                 return;
3312             }
3313         }
3314
3315         self.record_exports_for_module(module_);
3316         self.populate_module_if_necessary(module_);
3317
3318         for (_, &child_name_bindings) in module_.children.borrow().iter() {
3319             match child_name_bindings.get_module_if_available() {
3320                 None => {
3321                     // Nothing to do.
3322                 }
3323                 Some(child_module) => {
3324                     self.record_exports_for_module_subtree(child_module);
3325                 }
3326             }
3327         }
3328
3329         for (_, &child_module) in module_.anonymous_children.borrow().iter() {
3330             self.record_exports_for_module_subtree(child_module);
3331         }
3332     }
3333
3334     fn record_exports_for_module(&mut self, module_: @Module) {
3335         let mut exports2 = Vec::new();
3336
3337         self.add_exports_for_module(&mut exports2, module_);
3338         match module_.def_id.get() {
3339             Some(def_id) => {
3340                 self.export_map2.borrow_mut().insert(def_id.node, exports2);
3341                 debug!("(computing exports) writing exports for {} (some)",
3342                        def_id.node);
3343             }
3344             None => {}
3345         }
3346     }
3347
3348     fn add_exports_of_namebindings(&mut self,
3349                                    exports2: &mut Vec<Export2> ,
3350                                    name: Name,
3351                                    namebindings: @NameBindings,
3352                                    ns: Namespace) {
3353         match namebindings.def_for_namespace(ns) {
3354             Some(d) => {
3355                 let name = token::get_name(name);
3356                 debug!("(computing exports) YES: export '{}' => {:?}",
3357                        name, def_id_of_def(d));
3358                 exports2.push(Export2 {
3359                     name: name.get().to_str(),
3360                     def_id: def_id_of_def(d)
3361                 });
3362             }
3363             d_opt => {
3364                 debug!("(computing exports) NO: {:?}", d_opt);
3365             }
3366         }
3367     }
3368
3369     fn add_exports_for_module(&mut self,
3370                               exports2: &mut Vec<Export2> ,
3371                               module_: @Module) {
3372         for (name, importresolution) in module_.import_resolutions.borrow().iter() {
3373             if !importresolution.is_public.get() {
3374                 continue
3375             }
3376             let xs = [TypeNS, ValueNS];
3377             for &ns in xs.iter() {
3378                 match importresolution.target_for_namespace(ns) {
3379                     Some(target) => {
3380                         debug!("(computing exports) maybe export '{}'",
3381                                token::get_name(*name));
3382                         self.add_exports_of_namebindings(exports2,
3383                                                          *name,
3384                                                          target.bindings,
3385                                                          ns)
3386                     }
3387                     _ => ()
3388                 }
3389             }
3390         }
3391     }
3392
3393     // AST resolution
3394     //
3395     // We maintain a list of value ribs and type ribs.
3396     //
3397     // Simultaneously, we keep track of the current position in the module
3398     // graph in the `current_module` pointer. When we go to resolve a name in
3399     // the value or type namespaces, we first look through all the ribs and
3400     // then query the module graph. When we resolve a name in the module
3401     // namespace, we can skip all the ribs (since nested modules are not
3402     // allowed within blocks in Rust) and jump straight to the current module
3403     // graph node.
3404     //
3405     // Named implementations are handled separately. When we find a method
3406     // call, we consult the module node to find all of the implementations in
3407     // scope. This information is lazily cached in the module node. We then
3408     // generate a fake "implementation scope" containing all the
3409     // implementations thus found, for compatibility with old resolve pass.
3410
3411     fn with_scope(&mut self, name: Option<Ident>, f: |&mut Resolver|) {
3412         let orig_module = self.current_module;
3413
3414         // Move down in the graph.
3415         match name {
3416             None => {
3417                 // Nothing to do.
3418             }
3419             Some(name) => {
3420                 self.populate_module_if_necessary(orig_module);
3421
3422                 match orig_module.children.borrow().find(&name.name) {
3423                     None => {
3424                         debug!("!!! (with scope) didn't find `{}` in `{}`",
3425                                token::get_ident(name),
3426                                self.module_to_str(orig_module));
3427                     }
3428                     Some(name_bindings) => {
3429                         match (*name_bindings).get_module_if_available() {
3430                             None => {
3431                                 debug!("!!! (with scope) didn't find module \
3432                                         for `{}` in `{}`",
3433                                        token::get_ident(name),
3434                                        self.module_to_str(orig_module));
3435                             }
3436                             Some(module_) => {
3437                                 self.current_module = module_;
3438                             }
3439                         }
3440                     }
3441                 }
3442             }
3443         }
3444
3445         f(self);
3446
3447         self.current_module = orig_module;
3448     }
3449
3450     /// Wraps the given definition in the appropriate number of `def_upvar`
3451     /// wrappers.
3452     fn upvarify(&mut self,
3453                     ribs: &mut Vec<@Rib> ,
3454                     rib_index: uint,
3455                     def_like: DefLike,
3456                     span: Span)
3457                     -> Option<DefLike> {
3458         let mut def;
3459         let is_ty_param;
3460
3461         match def_like {
3462             DlDef(d @ DefLocal(..)) | DlDef(d @ DefUpvar(..)) |
3463             DlDef(d @ DefArg(..)) | DlDef(d @ DefBinding(..)) => {
3464                 def = d;
3465                 is_ty_param = false;
3466             }
3467             DlDef(d @ DefTyParam(..)) => {
3468                 def = d;
3469                 is_ty_param = true;
3470             }
3471             _ => {
3472                 return Some(def_like);
3473             }
3474         }
3475
3476         let mut rib_index = rib_index + 1;
3477         while rib_index < ribs.len() {
3478             match ribs.get(rib_index).kind {
3479                 NormalRibKind => {
3480                     // Nothing to do. Continue.
3481                 }
3482                 FunctionRibKind(function_id, body_id) => {
3483                     if !is_ty_param {
3484                         def = DefUpvar(def_id_of_def(def).node,
3485                                         @def,
3486                                         function_id,
3487                                         body_id);
3488                     }
3489                 }
3490                 MethodRibKind(item_id, _) => {
3491                   // If the def is a ty param, and came from the parent
3492                   // item, it's ok
3493                   match def {
3494                     DefTyParam(did, _) if {
3495                         self.def_map.borrow().find(&did.node).map(|x| *x)
3496                             == Some(DefTyParamBinder(item_id))
3497                     } => {
3498                       // ok
3499                     }
3500                     _ => {
3501                     if !is_ty_param {
3502                         // This was an attempt to access an upvar inside a
3503                         // named function item. This is not allowed, so we
3504                         // report an error.
3505
3506                         self.resolve_error(
3507                             span,
3508                             "can't capture dynamic environment in a fn item; \
3509                             use the || { ... } closure form instead");
3510                     } else {
3511                         // This was an attempt to use a type parameter outside
3512                         // its scope.
3513
3514                         self.resolve_error(span,
3515                                               "attempt to use a type \
3516                                               argument out of scope");
3517                     }
3518
3519                     return None;
3520                     }
3521                   }
3522                 }
3523                 OpaqueFunctionRibKind => {
3524                     if !is_ty_param {
3525                         // This was an attempt to access an upvar inside a
3526                         // named function item. This is not allowed, so we
3527                         // report an error.
3528
3529                         self.resolve_error(
3530                             span,
3531                             "can't capture dynamic environment in a fn item; \
3532                             use the || { ... } closure form instead");
3533                     } else {
3534                         // This was an attempt to use a type parameter outside
3535                         // its scope.
3536
3537                         self.resolve_error(span,
3538                                               "attempt to use a type \
3539                                               argument out of scope");
3540                     }
3541
3542                     return None;
3543                 }
3544                 ConstantItemRibKind => {
3545                     if is_ty_param {
3546                         // see #9186
3547                         self.resolve_error(span,
3548                                               "cannot use an outer type \
3549                                                parameter in this context");
3550                     } else {
3551                         // Still doesn't deal with upvars
3552                         self.resolve_error(span,
3553                                               "attempt to use a non-constant \
3554                                                value in a constant");
3555                     }
3556
3557                 }
3558             }
3559
3560             rib_index += 1;
3561         }
3562
3563         return Some(DlDef(def));
3564     }
3565
3566     fn search_ribs(&mut self,
3567                        ribs: &mut Vec<@Rib> ,
3568                        name: Name,
3569                        span: Span)
3570                        -> Option<DefLike> {
3571         // FIXME #4950: This should not use a while loop.
3572         // FIXME #4950: Try caching?
3573
3574         let mut i = ribs.len();
3575         while i != 0 {
3576             i -= 1;
3577             let binding_opt = ribs.get(i).bindings.borrow().find_copy(&name);
3578             match binding_opt {
3579                 Some(def_like) => {
3580                     return self.upvarify(ribs, i, def_like, span);
3581                 }
3582                 None => {
3583                     // Continue.
3584                 }
3585             }
3586         }
3587
3588         return None;
3589     }
3590
3591     fn resolve_crate(&mut self, krate: &ast::Crate) {
3592         debug!("(resolving crate) starting");
3593
3594         visit::walk_crate(self, krate, ());
3595     }
3596
3597     fn resolve_item(&mut self, item: &Item) {
3598         debug!("(resolving item) resolving {}",
3599                token::get_ident(item.ident));
3600
3601         match item.node {
3602
3603             // enum item: resolve all the variants' discrs,
3604             // then resolve the ty params
3605             ItemEnum(ref enum_def, ref generics) => {
3606                 for variant in (*enum_def).variants.iter() {
3607                     for dis_expr in variant.node.disr_expr.iter() {
3608                         // resolve the discriminator expr
3609                         // as a constant
3610                         self.with_constant_rib(|this| {
3611                             this.resolve_expr(*dis_expr);
3612                         });
3613                     }
3614                 }
3615
3616                 // n.b. the discr expr gets visted twice.
3617                 // but maybe it's okay since the first time will signal an
3618                 // error if there is one? -- tjc
3619                 self.with_type_parameter_rib(HasTypeParameters(generics,
3620                                                                item.id,
3621                                                                0,
3622                                                                NormalRibKind),
3623                                              |this| {
3624                     visit::walk_item(this, item, ());
3625                 });
3626             }
3627
3628             ItemTy(_, ref generics) => {
3629                 self.with_type_parameter_rib(HasTypeParameters(generics,
3630                                                                item.id,
3631                                                                0,
3632                                                                NormalRibKind),
3633                                              |this| {
3634                     visit::walk_item(this, item, ());
3635                 });
3636             }
3637
3638             ItemImpl(ref generics,
3639                       ref implemented_traits,
3640                       self_type,
3641                       ref methods) => {
3642                 self.resolve_implementation(item.id,
3643                                             generics,
3644                                             implemented_traits,
3645                                             self_type,
3646                                             methods.as_slice());
3647             }
3648
3649             ItemTrait(ref generics, ref traits, ref methods) => {
3650                 // Create a new rib for the self type.
3651                 let self_type_rib = @Rib::new(NormalRibKind);
3652                 self.type_ribs.borrow_mut().push(self_type_rib);
3653                 // plain insert (no renaming)
3654                 let name = self.type_self_ident.name;
3655                 self_type_rib.bindings.borrow_mut()
3656                              .insert(name, DlDef(DefSelfTy(item.id)));
3657
3658                 // Create a new rib for the trait-wide type parameters.
3659                 self.with_type_parameter_rib(HasTypeParameters(generics,
3660                                                                item.id,
3661                                                                0,
3662                                                                NormalRibKind),
3663                                              |this| {
3664                     this.resolve_type_parameters(&generics.ty_params);
3665
3666                     // Resolve derived traits.
3667                     for trt in traits.iter() {
3668                         this.resolve_trait_reference(item.id, trt, TraitDerivation);
3669                     }
3670
3671                     for method in (*methods).iter() {
3672                         // Create a new rib for the method-specific type
3673                         // parameters.
3674                         //
3675                         // FIXME #4951: Do we need a node ID here?
3676
3677                         match *method {
3678                           ast::Required(ref ty_m) => {
3679                             this.with_type_parameter_rib
3680                                 (HasTypeParameters(&ty_m.generics,
3681                                                    item.id,
3682                                                    generics.ty_params.len(),
3683                                         MethodRibKind(item.id, Required)),
3684                                  |this| {
3685
3686                                 // Resolve the method-specific type
3687                                 // parameters.
3688                                 this.resolve_type_parameters(
3689                                     &ty_m.generics.ty_params);
3690
3691                                 for argument in ty_m.decl.inputs.iter() {
3692                                     this.resolve_type(argument.ty);
3693                                 }
3694
3695                                 this.resolve_type(ty_m.decl.output);
3696                             });
3697                           }
3698                           ast::Provided(m) => {
3699                               this.resolve_method(MethodRibKind(item.id,
3700                                                      Provided(m.id)),
3701                                                   m,
3702                                                   generics.ty_params.len())
3703                           }
3704                         }
3705                     }
3706                 });
3707
3708                 self.type_ribs.borrow_mut().pop();
3709             }
3710
3711             ItemStruct(ref struct_def, ref generics) => {
3712                 self.resolve_struct(item.id,
3713                                     generics,
3714                                     struct_def.fields.as_slice());
3715             }
3716
3717             ItemMod(ref module_) => {
3718                 self.with_scope(Some(item.ident), |this| {
3719                     this.resolve_module(module_, item.span, item.ident,
3720                                         item.id);
3721                 });
3722             }
3723
3724             ItemForeignMod(ref foreign_module) => {
3725                 self.with_scope(Some(item.ident), |this| {
3726                     for foreign_item in foreign_module.items.iter() {
3727                         match foreign_item.node {
3728                             ForeignItemFn(_, ref generics) => {
3729                                 this.with_type_parameter_rib(
3730                                     HasTypeParameters(
3731                                         generics, foreign_item.id, 0,
3732                                         NormalRibKind),
3733                                     |this| visit::walk_foreign_item(this,
3734                                                                 *foreign_item,
3735                                                                 ()));
3736                             }
3737                             ForeignItemStatic(..) => {
3738                                 visit::walk_foreign_item(this,
3739                                                          *foreign_item,
3740                                                          ());
3741                             }
3742                         }
3743                     }
3744                 });
3745             }
3746
3747             ItemFn(fn_decl, _, _, ref generics, block) => {
3748                 self.resolve_function(OpaqueFunctionRibKind,
3749                                       Some(fn_decl),
3750                                       HasTypeParameters
3751                                         (generics,
3752                                          item.id,
3753                                          0,
3754                                          OpaqueFunctionRibKind),
3755                                       block);
3756             }
3757
3758             ItemStatic(..) => {
3759                 self.with_constant_rib(|this| {
3760                     visit::walk_item(this, item, ());
3761                 });
3762             }
3763
3764            ItemMac(..) => {
3765                 // do nothing, these are just around to be encoded
3766            }
3767         }
3768     }
3769
3770     fn with_type_parameter_rib(&mut self,
3771                                type_parameters: TypeParameters,
3772                                f: |&mut Resolver|) {
3773         match type_parameters {
3774             HasTypeParameters(generics, node_id, initial_index,
3775                               rib_kind) => {
3776
3777                 let function_type_rib = @Rib::new(rib_kind);
3778                 self.type_ribs.borrow_mut().push(function_type_rib);
3779
3780                 for (index, type_parameter) in generics.ty_params.iter().enumerate() {
3781                     let ident = type_parameter.ident;
3782                     debug!("with_type_parameter_rib: {} {}", node_id,
3783                            type_parameter.id);
3784                     let def_like = DlDef(DefTyParam
3785                         (local_def(type_parameter.id),
3786                          index + initial_index));
3787                     // Associate this type parameter with
3788                     // the item that bound it
3789                     self.record_def(type_parameter.id,
3790                                     (DefTyParamBinder(node_id), LastMod(AllPublic)));
3791                     // plain insert (no renaming)
3792                     function_type_rib.bindings.borrow_mut()
3793                                      .insert(ident.name, def_like);
3794                 }
3795             }
3796
3797             NoTypeParameters => {
3798                 // Nothing to do.
3799             }
3800         }
3801
3802         f(self);
3803
3804         match type_parameters {
3805             HasTypeParameters(..) => { self.type_ribs.borrow_mut().pop(); }
3806             NoTypeParameters => { }
3807         }
3808     }
3809
3810     fn with_label_rib(&mut self, f: |&mut Resolver|) {
3811         self.label_ribs.borrow_mut().push(@Rib::new(NormalRibKind));
3812         f(self);
3813         self.label_ribs.borrow_mut().pop();
3814     }
3815
3816     fn with_constant_rib(&mut self, f: |&mut Resolver|) {
3817         self.value_ribs.borrow_mut().push(@Rib::new(ConstantItemRibKind));
3818         self.type_ribs.borrow_mut().push(@Rib::new(ConstantItemRibKind));
3819         f(self);
3820         self.type_ribs.borrow_mut().pop();
3821         self.value_ribs.borrow_mut().pop();
3822     }
3823
3824     fn resolve_function(&mut self,
3825                         rib_kind: RibKind,
3826                         optional_declaration: Option<P<FnDecl>>,
3827                         type_parameters: TypeParameters,
3828                         block: P<Block>) {
3829         // Create a value rib for the function.
3830         let function_value_rib = @Rib::new(rib_kind);
3831         self.value_ribs.borrow_mut().push(function_value_rib);
3832
3833         // Create a label rib for the function.
3834         let function_label_rib = @Rib::new(rib_kind);
3835         self.label_ribs.borrow_mut().push(function_label_rib);
3836
3837         // If this function has type parameters, add them now.
3838         self.with_type_parameter_rib(type_parameters, |this| {
3839             // Resolve the type parameters.
3840             match type_parameters {
3841                 NoTypeParameters => {
3842                     // Continue.
3843                 }
3844                 HasTypeParameters(ref generics, _, _, _) => {
3845                     this.resolve_type_parameters(&generics.ty_params);
3846                 }
3847             }
3848
3849             // Add each argument to the rib.
3850             match optional_declaration {
3851                 None => {
3852                     // Nothing to do.
3853                 }
3854                 Some(declaration) => {
3855                     for argument in declaration.inputs.iter() {
3856                         let binding_mode = ArgumentIrrefutableMode;
3857                         this.resolve_pattern(argument.pat,
3858                                              binding_mode,
3859                                              None);
3860
3861                         this.resolve_type(argument.ty);
3862
3863                         debug!("(resolving function) recorded argument");
3864                     }
3865
3866                     this.resolve_type(declaration.output);
3867                 }
3868             }
3869
3870             // Resolve the function body.
3871             this.resolve_block(block);
3872
3873             debug!("(resolving function) leaving function");
3874         });
3875
3876         self.label_ribs.borrow_mut().pop();
3877         self.value_ribs.borrow_mut().pop();
3878     }
3879
3880     fn resolve_type_parameters(&mut self,
3881                                    type_parameters: &OwnedSlice<TyParam>) {
3882         for type_parameter in type_parameters.iter() {
3883             for bound in type_parameter.bounds.iter() {
3884                 self.resolve_type_parameter_bound(type_parameter.id, bound);
3885             }
3886             match type_parameter.default {
3887                 Some(ty) => self.resolve_type(ty),
3888                 None => {}
3889             }
3890         }
3891     }
3892
3893     fn resolve_type_parameter_bound(&mut self,
3894                                         id: NodeId,
3895                                         type_parameter_bound: &TyParamBound) {
3896         match *type_parameter_bound {
3897             TraitTyParamBound(ref tref) => {
3898                 self.resolve_trait_reference(id, tref, TraitBoundingTypeParameter)
3899             }
3900             RegionTyParamBound => {}
3901         }
3902     }
3903
3904     fn resolve_trait_reference(&mut self,
3905                                    id: NodeId,
3906                                    trait_reference: &TraitRef,
3907                                    reference_type: TraitReferenceType) {
3908         match self.resolve_path(id, &trait_reference.path, TypeNS, true) {
3909             None => {
3910                 let path_str = self.path_idents_to_str(&trait_reference.path);
3911                 let usage_str = match reference_type {
3912                     TraitBoundingTypeParameter => "bound type parameter with",
3913                     TraitImplementation        => "implement",
3914                     TraitDerivation            => "derive"
3915                 };
3916
3917                 let msg = format!("attempt to {} a nonexistent trait `{}`", usage_str, path_str);
3918                 self.resolve_error(trait_reference.path.span, msg);
3919             }
3920             Some(def) => {
3921                 debug!("(resolving trait) found trait def: {:?}", def);
3922                 self.record_def(trait_reference.ref_id, def);
3923             }
3924         }
3925     }
3926
3927     fn resolve_struct(&mut self,
3928                           id: NodeId,
3929                           generics: &Generics,
3930                           fields: &[StructField]) {
3931         let mut ident_map: HashMap<ast::Ident, &StructField> = HashMap::new();
3932         for field in fields.iter() {
3933             match field.node.kind {
3934                 NamedField(ident, _) => {
3935                     match ident_map.find(&ident) {
3936                         Some(&prev_field) => {
3937                             let ident_str = token::get_ident(ident);
3938                             self.resolve_error(field.span,
3939                                 format!("field `{}` is already declared", ident_str));
3940                             self.session.span_note(prev_field.span,
3941                                 "previously declared here");
3942                         },
3943                         None => {
3944                             ident_map.insert(ident, field);
3945                         }
3946                     }
3947                 }
3948                 _ => ()
3949             }
3950         }
3951
3952         // If applicable, create a rib for the type parameters.
3953         self.with_type_parameter_rib(HasTypeParameters(generics,
3954                                                        id,
3955                                                        0,
3956                                                        OpaqueFunctionRibKind),
3957                                      |this| {
3958             // Resolve the type parameters.
3959             this.resolve_type_parameters(&generics.ty_params);
3960
3961             // Resolve fields.
3962             for field in fields.iter() {
3963                 this.resolve_type(field.node.ty);
3964             }
3965         });
3966     }
3967
3968     // Does this really need to take a RibKind or is it always going
3969     // to be NormalRibKind?
3970     fn resolve_method(&mut self,
3971                       rib_kind: RibKind,
3972                       method: @Method,
3973                       outer_type_parameter_count: uint) {
3974         let method_generics = &method.generics;
3975         let type_parameters =
3976             HasTypeParameters(method_generics,
3977                               method.id,
3978                               outer_type_parameter_count,
3979                               rib_kind);
3980
3981         self.resolve_function(rib_kind, Some(method.decl), type_parameters, method.body);
3982     }
3983
3984     fn resolve_implementation(&mut self,
3985                                   id: NodeId,
3986                                   generics: &Generics,
3987                                   opt_trait_reference: &Option<TraitRef>,
3988                                   self_type: &Ty,
3989                                   methods: &[@Method]) {
3990         // If applicable, create a rib for the type parameters.
3991         let outer_type_parameter_count = generics.ty_params.len();
3992         self.with_type_parameter_rib(HasTypeParameters(generics,
3993                                                        id,
3994                                                        0,
3995                                                        NormalRibKind),
3996                                      |this| {
3997             // Resolve the type parameters.
3998             this.resolve_type_parameters(&generics.ty_params);
3999
4000             // Resolve the trait reference, if necessary.
4001             let original_trait_refs;
4002             match opt_trait_reference {
4003                 &Some(ref trait_reference) => {
4004                     this.resolve_trait_reference(id, trait_reference,
4005                         TraitImplementation);
4006
4007                     // Record the current set of trait references.
4008                     let mut new_trait_refs = Vec::new();
4009                     for &def in this.def_map.borrow()
4010                                     .find(&trait_reference.ref_id).iter() {
4011                         new_trait_refs.push(def_id_of_def(*def));
4012                     }
4013                     original_trait_refs = Some(replace(
4014                         &mut this.current_trait_refs,
4015                         Some(new_trait_refs)));
4016                 }
4017                 &None => {
4018                     original_trait_refs = None;
4019                 }
4020             }
4021
4022             // Resolve the self type.
4023             this.resolve_type(self_type);
4024
4025             for method in methods.iter() {
4026                 // We also need a new scope for the method-specific
4027                 // type parameters.
4028                 this.resolve_method(MethodRibKind(
4029                     id,
4030                     Provided(method.id)),
4031                     *method,
4032                     outer_type_parameter_count);
4033 /*
4034                     let borrowed_type_parameters = &method.tps;
4035                     self.resolve_function(MethodRibKind(
4036                                           id,
4037                                           Provided(method.id)),
4038                                           Some(method.decl),
4039                                           HasTypeParameters
4040                                             (borrowed_type_parameters,
4041                                              method.id,
4042                                              outer_type_parameter_count,
4043                                              NormalRibKind),
4044                                           method.body);
4045 */
4046             }
4047
4048             // Restore the original trait references.
4049             match original_trait_refs {
4050                 Some(r) => { this.current_trait_refs = r; }
4051                 None => ()
4052             }
4053         });
4054     }
4055
4056     fn resolve_module(&mut self, module: &Mod, _span: Span,
4057                       _name: Ident, id: NodeId) {
4058         // Write the implementations in scope into the module metadata.
4059         debug!("(resolving module) resolving module ID {}", id);
4060         visit::walk_mod(self, module, ());
4061     }
4062
4063     fn resolve_local(&mut self, local: &Local) {
4064         // Resolve the type.
4065         self.resolve_type(local.ty);
4066
4067         // Resolve the initializer, if necessary.
4068         match local.init {
4069             None => {
4070                 // Nothing to do.
4071             }
4072             Some(initializer) => {
4073                 self.resolve_expr(initializer);
4074             }
4075         }
4076
4077         // Resolve the pattern.
4078         self.resolve_pattern(local.pat, LocalIrrefutableMode, None);
4079     }
4080
4081     // build a map from pattern identifiers to binding-info's.
4082     // this is done hygienically. This could arise for a macro
4083     // that expands into an or-pattern where one 'x' was from the
4084     // user and one 'x' came from the macro.
4085     fn binding_mode_map(&mut self, pat: @Pat) -> BindingMap {
4086         let mut result = HashMap::new();
4087         pat_bindings(self.def_map, pat, |binding_mode, _id, sp, path| {
4088             let name = mtwt::resolve(path_to_ident(path));
4089             result.insert(name,
4090                           binding_info {span: sp,
4091                                         binding_mode: binding_mode});
4092         });
4093         return result;
4094     }
4095
4096     // check that all of the arms in an or-pattern have exactly the
4097     // same set of bindings, with the same binding modes for each.
4098     fn check_consistent_bindings(&mut self, arm: &Arm) {
4099         if arm.pats.len() == 0 {
4100             return
4101         }
4102         let map_0 = self.binding_mode_map(*arm.pats.get(0));
4103         for (i, p) in arm.pats.iter().enumerate() {
4104             let map_i = self.binding_mode_map(*p);
4105
4106             for (&key, &binding_0) in map_0.iter() {
4107                 match map_i.find(&key) {
4108                   None => {
4109                     self.resolve_error(
4110                         p.span,
4111                         format!("variable `{}` from pattern \\#1 is \
4112                                   not bound in pattern \\#{}",
4113                                 token::get_name(key),
4114                                 i + 1));
4115                   }
4116                   Some(binding_i) => {
4117                     if binding_0.binding_mode != binding_i.binding_mode {
4118                         self.resolve_error(
4119                             binding_i.span,
4120                             format!("variable `{}` is bound with different \
4121                                       mode in pattern \\#{} than in pattern \\#1",
4122                                     token::get_name(key),
4123                                     i + 1));
4124                     }
4125                   }
4126                 }
4127             }
4128
4129             for (&key, &binding) in map_i.iter() {
4130                 if !map_0.contains_key(&key) {
4131                     self.resolve_error(
4132                         binding.span,
4133                         format!("variable `{}` from pattern \\#{} is \
4134                                   not bound in pattern \\#1",
4135                                 token::get_name(key),
4136                                 i + 1));
4137                 }
4138             }
4139         }
4140     }
4141
4142     fn resolve_arm(&mut self, arm: &Arm) {
4143         self.value_ribs.borrow_mut().push(@Rib::new(NormalRibKind));
4144
4145         let mut bindings_list = HashMap::new();
4146         for pattern in arm.pats.iter() {
4147             self.resolve_pattern(*pattern,
4148                                  RefutableMode,
4149                                  Some(&mut bindings_list));
4150         }
4151
4152         // This has to happen *after* we determine which
4153         // pat_idents are variants
4154         self.check_consistent_bindings(arm);
4155
4156         visit::walk_expr_opt(self, arm.guard, ());
4157         self.resolve_expr(arm.body);
4158
4159         self.value_ribs.borrow_mut().pop();
4160     }
4161
4162     fn resolve_block(&mut self, block: &Block) {
4163         debug!("(resolving block) entering block");
4164         self.value_ribs.borrow_mut().push(@Rib::new(NormalRibKind));
4165
4166         // Move down in the graph, if there's an anonymous module rooted here.
4167         let orig_module = self.current_module;
4168         let anonymous_children = self.current_module
4169                                      .anonymous_children
4170                                      .borrow();
4171         match anonymous_children.find(&block.id) {
4172             None => { /* Nothing to do. */ }
4173             Some(&anonymous_module) => {
4174                 debug!("(resolving block) found anonymous module, moving \
4175                         down");
4176                 self.current_module = anonymous_module;
4177             }
4178         }
4179
4180         // Descend into the block.
4181         visit::walk_block(self, block, ());
4182
4183         // Move back up.
4184         self.current_module = orig_module;
4185
4186         self.value_ribs.borrow_mut().pop();
4187         debug!("(resolving block) leaving block");
4188     }
4189
4190     fn resolve_type(&mut self, ty: &Ty) {
4191         match ty.node {
4192             // Like path expressions, the interpretation of path types depends
4193             // on whether the path has multiple elements in it or not.
4194
4195             TyPath(ref path, ref bounds, path_id) => {
4196                 // This is a path in the type namespace. Walk through scopes
4197                 // looking for it.
4198                 let mut result_def = None;
4199
4200                 // First, check to see whether the name is a primitive type.
4201                 if path.segments.len() == 1 {
4202                     let id = path.segments.last().unwrap().identifier;
4203
4204                     match self.primitive_type_table
4205                             .primitive_types
4206                             .find(&id.name) {
4207
4208                         Some(&primitive_type) => {
4209                             result_def =
4210                                 Some((DefPrimTy(primitive_type), LastMod(AllPublic)));
4211
4212                             if path.segments
4213                                    .iter()
4214                                    .any(|s| !s.lifetimes.is_empty()) {
4215                                 self.session.span_err(path.span,
4216                                                       "lifetime parameters \
4217                                                        are not allowed on \
4218                                                        this type")
4219                             } else if path.segments
4220                                           .iter()
4221                                           .any(|s| s.types.len() > 0) {
4222                                 self.session.span_err(path.span,
4223                                                       "type parameters are \
4224                                                        not allowed on this \
4225                                                        type")
4226                             }
4227                         }
4228                         None => {
4229                             // Continue.
4230                         }
4231                     }
4232                 }
4233
4234                 match result_def {
4235                     None => {
4236                         match self.resolve_path(ty.id, path, TypeNS, true) {
4237                             Some(def) => {
4238                                 debug!("(resolving type) resolved `{}` to \
4239                                         type {:?}",
4240                                        token::get_ident(path.segments
4241                                                             .last().unwrap()
4242                                                             .identifier),
4243                                        def);
4244                                 result_def = Some(def);
4245                             }
4246                             None => {
4247                                 result_def = None;
4248                             }
4249                         }
4250                     }
4251                     Some(_) => {}   // Continue.
4252                 }
4253
4254                 match result_def {
4255                     Some(def) => {
4256                         // Write the result into the def map.
4257                         debug!("(resolving type) writing resolution for `{}` \
4258                                 (id {})",
4259                                self.path_idents_to_str(path),
4260                                path_id);
4261                         self.record_def(path_id, def);
4262                     }
4263                     None => {
4264                         let msg = format!("use of undeclared type name `{}`",
4265                                           self.path_idents_to_str(path));
4266                         self.resolve_error(ty.span, msg);
4267                     }
4268                 }
4269
4270                 bounds.as_ref().map(|bound_vec| {
4271                     for bound in bound_vec.iter() {
4272                         self.resolve_type_parameter_bound(ty.id, bound);
4273                     }
4274                 });
4275             }
4276
4277             TyClosure(c) => {
4278                 c.bounds.as_ref().map(|bounds| {
4279                     for bound in bounds.iter() {
4280                         self.resolve_type_parameter_bound(ty.id, bound);
4281                     }
4282                 });
4283                 visit::walk_ty(self, ty, ());
4284             }
4285
4286             _ => {
4287                 // Just resolve embedded types.
4288                 visit::walk_ty(self, ty, ());
4289             }
4290         }
4291     }
4292
4293     fn resolve_pattern(&mut self,
4294                        pattern: @Pat,
4295                        mode: PatternBindingMode,
4296                        // Maps idents to the node ID for the (outermost)
4297                        // pattern that binds them
4298                        mut bindings_list: Option<&mut HashMap<Name,NodeId>>) {
4299         let pat_id = pattern.id;
4300         walk_pat(pattern, |pattern| {
4301             match pattern.node {
4302                 PatIdent(binding_mode, ref path, _)
4303                         if !path.global && path.segments.len() == 1 => {
4304
4305                     // The meaning of pat_ident with no type parameters
4306                     // depends on whether an enum variant or unit-like struct
4307                     // with that name is in scope. The probing lookup has to
4308                     // be careful not to emit spurious errors. Only matching
4309                     // patterns (match) can match nullary variants or
4310                     // unit-like structs. For binding patterns (let), matching
4311                     // such a value is simply disallowed (since it's rarely
4312                     // what you want).
4313
4314                     let ident = path.segments.get(0).identifier;
4315                     let renamed = mtwt::resolve(ident);
4316
4317                     match self.resolve_bare_identifier_pattern(ident) {
4318                         FoundStructOrEnumVariant(def, lp)
4319                                 if mode == RefutableMode => {
4320                             debug!("(resolving pattern) resolving `{}` to \
4321                                     struct or enum variant",
4322                                    token::get_name(renamed));
4323
4324                             self.enforce_default_binding_mode(
4325                                 pattern,
4326                                 binding_mode,
4327                                 "an enum variant");
4328                             self.record_def(pattern.id, (def, lp));
4329                         }
4330                         FoundStructOrEnumVariant(..) => {
4331                             self.resolve_error(pattern.span,
4332                                                   format!("declaration of `{}` \
4333                                                         shadows an enum \
4334                                                         variant or unit-like \
4335                                                         struct in scope",
4336                                                         token::get_name(renamed)));
4337                         }
4338                         FoundConst(def, lp) if mode == RefutableMode => {
4339                             debug!("(resolving pattern) resolving `{}` to \
4340                                     constant",
4341                                    token::get_name(renamed));
4342
4343                             self.enforce_default_binding_mode(
4344                                 pattern,
4345                                 binding_mode,
4346                                 "a constant");
4347                             self.record_def(pattern.id, (def, lp));
4348                         }
4349                         FoundConst(..) => {
4350                             self.resolve_error(pattern.span,
4351                                                   "only irrefutable patterns \
4352                                                    allowed here");
4353                         }
4354                         BareIdentifierPatternUnresolved => {
4355                             debug!("(resolving pattern) binding `{}`",
4356                                    token::get_name(renamed));
4357
4358                             let def = match mode {
4359                                 RefutableMode => {
4360                                     // For pattern arms, we must use
4361                                     // `def_binding` definitions.
4362
4363                                     DefBinding(pattern.id, binding_mode)
4364                                 }
4365                                 LocalIrrefutableMode => {
4366                                     // But for locals, we use `def_local`.
4367                                     DefLocal(pattern.id, binding_mode)
4368                                 }
4369                                 ArgumentIrrefutableMode => {
4370                                     // And for function arguments, `def_arg`.
4371                                     DefArg(pattern.id, binding_mode)
4372                                 }
4373                             };
4374
4375                             // Record the definition so that later passes
4376                             // will be able to distinguish variants from
4377                             // locals in patterns.
4378
4379                             self.record_def(pattern.id, (def, LastMod(AllPublic)));
4380
4381                             // Add the binding to the local ribs, if it
4382                             // doesn't already exist in the bindings list. (We
4383                             // must not add it if it's in the bindings list
4384                             // because that breaks the assumptions later
4385                             // passes make about or-patterns.)
4386
4387                             match bindings_list {
4388                                 Some(ref mut bindings_list)
4389                                 if !bindings_list.contains_key(&renamed) => {
4390                                     let this = &mut *self;
4391                                     let value_ribs = this.value_ribs.borrow();
4392                                     let length = value_ribs.len();
4393                                     let last_rib = value_ribs.get(
4394                                         length - 1);
4395                                     last_rib.bindings.borrow_mut()
4396                                             .insert(renamed, DlDef(def));
4397                                     bindings_list.insert(renamed, pat_id);
4398                                 }
4399                                 Some(ref mut b) => {
4400                                   if b.find(&renamed) == Some(&pat_id) {
4401                                       // Then this is a duplicate variable
4402                                       // in the same disjunct, which is an
4403                                       // error
4404                                      self.resolve_error(pattern.span,
4405                                        format!("identifier `{}` is bound more \
4406                                              than once in the same pattern",
4407                                             path_to_str(path)));
4408                                   }
4409                                   // Not bound in the same pattern: do nothing
4410                                 }
4411                                 None => {
4412                                     let this = &mut *self;
4413                                     {
4414                                         let value_ribs = this.value_ribs.borrow();
4415                                         let length = value_ribs.len();
4416                                         let last_rib = value_ribs.get(
4417                                                 length - 1);
4418                                         last_rib.bindings.borrow_mut()
4419                                                 .insert(renamed, DlDef(def));
4420                                     }
4421                                 }
4422                             }
4423                         }
4424                     }
4425
4426                     // Check the types in the path pattern.
4427                     for &ty in path.segments
4428                                   .iter()
4429                                   .flat_map(|seg| seg.types.iter()) {
4430                         self.resolve_type(ty);
4431                     }
4432                 }
4433
4434                 PatIdent(binding_mode, ref path, _) => {
4435                     // This must be an enum variant, struct, or constant.
4436                     match self.resolve_path(pat_id, path, ValueNS, false) {
4437                         Some(def @ (DefVariant(..), _)) |
4438                         Some(def @ (DefStruct(..), _)) => {
4439                             self.record_def(pattern.id, def);
4440                         }
4441                         Some(def @ (DefStatic(..), _)) => {
4442                             self.enforce_default_binding_mode(
4443                                 pattern,
4444                                 binding_mode,
4445                                 "a constant");
4446                             self.record_def(pattern.id, def);
4447                         }
4448                         Some(_) => {
4449                             self.resolve_error(
4450                                 path.span,
4451                                 format!("`{}` is not an enum variant or constant",
4452                                      token::get_ident(
4453                                          path.segments.last().unwrap().identifier)))
4454                         }
4455                         None => {
4456                             self.resolve_error(path.span,
4457                                                   "unresolved enum variant");
4458                         }
4459                     }
4460
4461                     // Check the types in the path pattern.
4462                     for &ty in path.segments
4463                                   .iter()
4464                                   .flat_map(|s| s.types.iter()) {
4465                         self.resolve_type(ty);
4466                     }
4467                 }
4468
4469                 PatEnum(ref path, _) => {
4470                     // This must be an enum variant, struct or const.
4471                     match self.resolve_path(pat_id, path, ValueNS, false) {
4472                         Some(def @ (DefFn(..), _))      |
4473                         Some(def @ (DefVariant(..), _)) |
4474                         Some(def @ (DefStruct(..), _))  |
4475                         Some(def @ (DefStatic(..), _)) => {
4476                             self.record_def(pattern.id, def);
4477                         }
4478                         Some(_) => {
4479                             self.resolve_error(path.span,
4480                                 format!("`{}` is not an enum variant, struct or const",
4481                                     token::get_ident(path.segments
4482                                                          .last().unwrap()
4483                                                          .identifier)));
4484                         }
4485                         None => {
4486                             self.resolve_error(path.span,
4487                                 format!("unresolved enum variant, struct or const `{}`",
4488                                     token::get_ident(path.segments
4489                                                          .last().unwrap()
4490                                                          .identifier)));
4491                         }
4492                     }
4493
4494                     // Check the types in the path pattern.
4495                     for &ty in path.segments
4496                                   .iter()
4497                                   .flat_map(|s| s.types.iter()) {
4498                         self.resolve_type(ty);
4499                     }
4500                 }
4501
4502                 PatLit(expr) => {
4503                     self.resolve_expr(expr);
4504                 }
4505
4506                 PatRange(first_expr, last_expr) => {
4507                     self.resolve_expr(first_expr);
4508                     self.resolve_expr(last_expr);
4509                 }
4510
4511                 PatStruct(ref path, _, _) => {
4512                     match self.resolve_path(pat_id, path, TypeNS, false) {
4513                         Some((DefTy(class_id), lp))
4514                                 if self.structs.contains(&class_id) => {
4515                             let class_def = DefStruct(class_id);
4516                             self.record_def(pattern.id, (class_def, lp));
4517                         }
4518                         Some(definition @ (DefStruct(class_id), _)) => {
4519                             assert!(self.structs.contains(&class_id));
4520                             self.record_def(pattern.id, definition);
4521                         }
4522                         Some(definition @ (DefVariant(_, variant_id, _), _))
4523                                 if self.structs.contains(&variant_id) => {
4524                             self.record_def(pattern.id, definition);
4525                         }
4526                         result => {
4527                             debug!("(resolving pattern) didn't find struct \
4528                                     def: {:?}", result);
4529                             let msg = format!("`{}` does not name a structure",
4530                                               self.path_idents_to_str(path));
4531                             self.resolve_error(path.span, msg);
4532                         }
4533                     }
4534                 }
4535
4536                 _ => {
4537                     // Nothing to do.
4538                 }
4539             }
4540             true
4541         });
4542     }
4543
4544     fn resolve_bare_identifier_pattern(&mut self, name: Ident)
4545                                            ->
4546                                            BareIdentifierPatternResolution {
4547         match self.resolve_item_in_lexical_scope(self.current_module,
4548                                                  name,
4549                                                  ValueNS,
4550                                                  SearchThroughModules) {
4551             Success((target, _)) => {
4552                 debug!("(resolve bare identifier pattern) succeeded in \
4553                          finding {} at {:?}",
4554                         token::get_ident(name),
4555                         target.bindings.value_def.borrow());
4556                 match *target.bindings.value_def.borrow() {
4557                     None => {
4558                         fail!("resolved name in the value namespace to a \
4559                               set of name bindings with no def?!");
4560                     }
4561                     Some(def) => {
4562                         // For the two success cases, this lookup can be
4563                         // considered as not having a private component because
4564                         // the lookup happened only within the current module.
4565                         match def.def {
4566                             def @ DefVariant(..) | def @ DefStruct(..) => {
4567                                 return FoundStructOrEnumVariant(def, LastMod(AllPublic));
4568                             }
4569                             def @ DefStatic(_, false) => {
4570                                 return FoundConst(def, LastMod(AllPublic));
4571                             }
4572                             _ => {
4573                                 return BareIdentifierPatternUnresolved;
4574                             }
4575                         }
4576                     }
4577                 }
4578             }
4579
4580             Indeterminate => {
4581                 fail!("unexpected indeterminate result");
4582             }
4583
4584             Failed => {
4585                 debug!("(resolve bare identifier pattern) failed to find {}",
4586                         token::get_ident(name));
4587                 return BareIdentifierPatternUnresolved;
4588             }
4589         }
4590     }
4591
4592     /// If `check_ribs` is true, checks the local definitions first; i.e.
4593     /// doesn't skip straight to the containing module.
4594     fn resolve_path(&mut self,
4595                     id: NodeId,
4596                     path: &Path,
4597                     namespace: Namespace,
4598                     check_ribs: bool) -> Option<(Def, LastPrivate)> {
4599         // First, resolve the types.
4600         for &ty in path.segments.iter().flat_map(|s| s.types.iter()) {
4601             self.resolve_type(ty);
4602         }
4603
4604         if path.global {
4605             return self.resolve_crate_relative_path(path, namespace);
4606         }
4607
4608         let unqualified_def =
4609                 self.resolve_identifier(path.segments
4610                                             .last().unwrap()
4611                                             .identifier,
4612                                         namespace,
4613                                         check_ribs,
4614                                         path.span);
4615
4616         if path.segments.len() > 1 {
4617             let def = self.resolve_module_relative_path(path, namespace);
4618             match (def, unqualified_def) {
4619                 (Some((d, _)), Some((ud, _))) if d == ud => {
4620                     self.session.add_lint(UnnecessaryQualification,
4621                                           id,
4622                                           path.span,
4623                                           ~"unnecessary qualification");
4624                 }
4625                 _ => ()
4626             }
4627
4628             return def;
4629         }
4630
4631         return unqualified_def;
4632     }
4633
4634     // resolve a single identifier (used as a varref)
4635     fn resolve_identifier(&mut self,
4636                               identifier: Ident,
4637                               namespace: Namespace,
4638                               check_ribs: bool,
4639                               span: Span)
4640                               -> Option<(Def, LastPrivate)> {
4641         if check_ribs {
4642             match self.resolve_identifier_in_local_ribs(identifier,
4643                                                       namespace,
4644                                                       span) {
4645                 Some(def) => {
4646                     return Some((def, LastMod(AllPublic)));
4647                 }
4648                 None => {
4649                     // Continue.
4650                 }
4651             }
4652         }
4653
4654         return self.resolve_item_by_identifier_in_lexical_scope(identifier,
4655                                                                 namespace);
4656     }
4657
4658     // FIXME #4952: Merge me with resolve_name_in_module?
4659     fn resolve_definition_of_name_in_module(&mut self,
4660                                             containing_module: @Module,
4661                                             name: Ident,
4662                                             namespace: Namespace)
4663                                                 -> NameDefinition {
4664         // First, search children.
4665         self.populate_module_if_necessary(containing_module);
4666
4667         match containing_module.children.borrow().find(&name.name) {
4668             Some(child_name_bindings) => {
4669                 match child_name_bindings.def_for_namespace(namespace) {
4670                     Some(def) => {
4671                         // Found it. Stop the search here.
4672                         let p = child_name_bindings.defined_in_public_namespace(
4673                                         namespace);
4674                         let lp = if p {LastMod(AllPublic)} else {
4675                             LastMod(DependsOn(def_id_of_def(def)))
4676                         };
4677                         return ChildNameDefinition(def, lp);
4678                     }
4679                     None => {}
4680                 }
4681             }
4682             None => {}
4683         }
4684
4685         // Next, search import resolutions.
4686         match containing_module.import_resolutions.borrow().find(&name.name) {
4687             Some(import_resolution) if import_resolution.is_public.get() => {
4688                 match (*import_resolution).target_for_namespace(namespace) {
4689                     Some(target) => {
4690                         match target.bindings.def_for_namespace(namespace) {
4691                             Some(def) => {
4692                                 // Found it.
4693                                 let id = import_resolution.id(namespace);
4694                                 self.used_imports.insert((id, namespace));
4695                                 return ImportNameDefinition(def, LastMod(AllPublic));
4696                             }
4697                             None => {
4698                                 // This can happen with external impls, due to
4699                                 // the imperfect way we read the metadata.
4700                             }
4701                         }
4702                     }
4703                     None => {}
4704                 }
4705             }
4706             Some(..) | None => {} // Continue.
4707         }
4708
4709         // Finally, search through external children.
4710         if namespace == TypeNS {
4711             match containing_module.external_module_children.borrow()
4712                                    .find_copy(&name.name) {
4713                 None => {}
4714                 Some(module) => {
4715                     match module.def_id.get() {
4716                         None => {} // Continue.
4717                         Some(def_id) => {
4718                             let lp = if module.is_public {LastMod(AllPublic)} else {
4719                                 LastMod(DependsOn(def_id))
4720                             };
4721                             return ChildNameDefinition(DefMod(def_id), lp);
4722                         }
4723                     }
4724                 }
4725             }
4726         }
4727
4728         return NoNameDefinition;
4729     }
4730
4731     // resolve a "module-relative" path, e.g. a::b::c
4732     fn resolve_module_relative_path(&mut self,
4733                                         path: &Path,
4734                                         namespace: Namespace)
4735                                         -> Option<(Def, LastPrivate)> {
4736         let module_path_idents = path.segments.init().iter()
4737                                                      .map(|ps| ps.identifier)
4738                                                      .collect::<Vec<_>>();
4739
4740         let containing_module;
4741         let last_private;
4742         match self.resolve_module_path(self.current_module,
4743                                        module_path_idents.as_slice(),
4744                                        UseLexicalScope,
4745                                        path.span,
4746                                        PathSearch) {
4747             Failed => {
4748                 let msg = format!("use of undeclared module `{}`",
4749                                   self.idents_to_str(module_path_idents.as_slice()));
4750                 self.resolve_error(path.span, msg);
4751                 return None;
4752             }
4753
4754             Indeterminate => {
4755                 fail!("indeterminate unexpected");
4756             }
4757
4758             Success((resulting_module, resulting_last_private)) => {
4759                 containing_module = resulting_module;
4760                 last_private = resulting_last_private;
4761             }
4762         }
4763
4764         let ident = path.segments.last().unwrap().identifier;
4765         let def = match self.resolve_definition_of_name_in_module(containing_module,
4766                                                         ident,
4767                                                         namespace) {
4768             NoNameDefinition => {
4769                 // We failed to resolve the name. Report an error.
4770                 return None;
4771             }
4772             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
4773                 (def, last_private.or(lp))
4774             }
4775         };
4776         match containing_module.kind.get() {
4777             TraitModuleKind | ImplModuleKind => {
4778                 match self.method_map.borrow().find(&ident.name) {
4779                     Some(s) => {
4780                         match containing_module.def_id.get() {
4781                             Some(def_id) if s.contains(&def_id) => {
4782                                 debug!("containing module was a trait or impl \
4783                                         and name was a method -> not resolved");
4784                                 return None;
4785                             },
4786                             _ => (),
4787                         }
4788                     },
4789                     None => (),
4790                 }
4791             },
4792             _ => (),
4793         };
4794         return Some(def);
4795     }
4796
4797     /// Invariant: This must be called only during main resolution, not during
4798     /// import resolution.
4799     fn resolve_crate_relative_path(&mut self,
4800                                    path: &Path,
4801                                    namespace: Namespace)
4802                                        -> Option<(Def, LastPrivate)> {
4803         let module_path_idents = path.segments.init().iter()
4804                                                      .map(|ps| ps.identifier)
4805                                                      .collect::<Vec<_>>();
4806
4807         let root_module = self.graph_root.get_module();
4808
4809         let containing_module;
4810         let last_private;
4811         match self.resolve_module_path_from_root(root_module,
4812                                                  module_path_idents.as_slice(),
4813                                                  0,
4814                                                  path.span,
4815                                                  PathSearch,
4816                                                  LastMod(AllPublic)) {
4817             Failed => {
4818                 let msg = format!("use of undeclared module `::{}`",
4819                                   self.idents_to_str(module_path_idents.as_slice()));
4820                 self.resolve_error(path.span, msg);
4821                 return None;
4822             }
4823
4824             Indeterminate => {
4825                 fail!("indeterminate unexpected");
4826             }
4827
4828             Success((resulting_module, resulting_last_private)) => {
4829                 containing_module = resulting_module;
4830                 last_private = resulting_last_private;
4831             }
4832         }
4833
4834         let name = path.segments.last().unwrap().identifier;
4835         match self.resolve_definition_of_name_in_module(containing_module,
4836                                                         name,
4837                                                         namespace) {
4838             NoNameDefinition => {
4839                 // We failed to resolve the name. Report an error.
4840                 return None;
4841             }
4842             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
4843                 return Some((def, last_private.or(lp)));
4844             }
4845         }
4846     }
4847
4848     fn resolve_identifier_in_local_ribs(&mut self,
4849                                             ident: Ident,
4850                                             namespace: Namespace,
4851                                             span: Span)
4852                                             -> Option<Def> {
4853         // Check the local set of ribs.
4854         let search_result = match namespace {
4855             ValueNS => {
4856                 let renamed = mtwt::resolve(ident);
4857                 self.search_ribs(&mut *self.value_ribs.borrow_mut(),
4858                                  renamed, span)
4859             }
4860             TypeNS => {
4861                 let name = ident.name;
4862                 self.search_ribs(&mut *self.type_ribs.borrow_mut(), name, span)
4863             }
4864         };
4865
4866         match search_result {
4867             Some(DlDef(def)) => {
4868                 debug!("(resolving path in local ribs) resolved `{}` to \
4869                         local: {:?}",
4870                        token::get_ident(ident),
4871                        def);
4872                 return Some(def);
4873             }
4874             Some(DlField) | Some(DlImpl(_)) | None => {
4875                 return None;
4876             }
4877         }
4878     }
4879
4880     fn resolve_item_by_identifier_in_lexical_scope(&mut self,
4881                                                    ident: Ident,
4882                                                    namespace: Namespace)
4883                                                 -> Option<(Def, LastPrivate)> {
4884         // Check the items.
4885         match self.resolve_item_in_lexical_scope(self.current_module,
4886                                                  ident,
4887                                                  namespace,
4888                                                  DontSearchThroughModules) {
4889             Success((target, _)) => {
4890                 match (*target.bindings).def_for_namespace(namespace) {
4891                     None => {
4892                         // This can happen if we were looking for a type and
4893                         // found a module instead. Modules don't have defs.
4894                         debug!("(resolving item path by identifier in lexical \
4895                                  scope) failed to resolve {} after success...",
4896                                  token::get_ident(ident));
4897                         return None;
4898                     }
4899                     Some(def) => {
4900                         debug!("(resolving item path in lexical scope) \
4901                                 resolved `{}` to item",
4902                                token::get_ident(ident));
4903                         // This lookup is "all public" because it only searched
4904                         // for one identifier in the current module (couldn't
4905                         // have passed through reexports or anything like that.
4906                         return Some((def, LastMod(AllPublic)));
4907                     }
4908                 }
4909             }
4910             Indeterminate => {
4911                 fail!("unexpected indeterminate result");
4912             }
4913             Failed => {
4914                 debug!("(resolving item path by identifier in lexical scope) \
4915                          failed to resolve {}", token::get_ident(ident));
4916                 return None;
4917             }
4918         }
4919     }
4920
4921     fn with_no_errors<T>(&mut self, f: |&mut Resolver| -> T) -> T {
4922         self.emit_errors = false;
4923         let rs = f(self);
4924         self.emit_errors = true;
4925         rs
4926     }
4927
4928     fn resolve_error(&mut self, span: Span, s: &str) {
4929         if self.emit_errors {
4930             self.session.span_err(span, s);
4931         }
4932     }
4933
4934     fn find_best_match_for_name(&mut self, name: &str, max_distance: uint)
4935                                 -> Option<~str> {
4936         let this = &mut *self;
4937
4938         let mut maybes: Vec<token::InternedString> = Vec::new();
4939         let mut values: Vec<uint> = Vec::new();
4940
4941         let mut j = this.value_ribs.borrow().len();
4942         while j != 0 {
4943             j -= 1;
4944             let value_ribs = this.value_ribs.borrow();
4945             let bindings = value_ribs.get(j).bindings.borrow();
4946             for (&k, _) in bindings.iter() {
4947                 maybes.push(token::get_name(k));
4948                 values.push(uint::MAX);
4949             }
4950         }
4951
4952         let mut smallest = 0;
4953         for (i, other) in maybes.iter().enumerate() {
4954             *values.get_mut(i) = name.lev_distance(other.get());
4955
4956             if *values.get(i) <= *values.get(smallest) {
4957                 smallest = i;
4958             }
4959         }
4960
4961         if values.len() > 0 &&
4962             *values.get(smallest) != uint::MAX &&
4963             *values.get(smallest) < name.len() + 2 &&
4964             *values.get(smallest) <= max_distance &&
4965             name != maybes.get(smallest).get() {
4966
4967             Some(maybes.get(smallest).get().to_str())
4968
4969         } else {
4970             None
4971         }
4972     }
4973
4974     fn resolve_expr(&mut self, expr: &Expr) {
4975         // First, record candidate traits for this expression if it could
4976         // result in the invocation of a method call.
4977
4978         self.record_candidate_traits_for_expr_if_necessary(expr);
4979
4980         // Next, resolve the node.
4981         match expr.node {
4982             // The interpretation of paths depends on whether the path has
4983             // multiple elements in it or not.
4984
4985             ExprPath(ref path) => {
4986                 // This is a local path in the value namespace. Walk through
4987                 // scopes looking for it.
4988
4989                 match self.resolve_path(expr.id, path, ValueNS, true) {
4990                     Some(def) => {
4991                         // Write the result into the def map.
4992                         debug!("(resolving expr) resolved `{}`",
4993                                self.path_idents_to_str(path));
4994
4995                         // First-class methods are not supported yet; error
4996                         // out here.
4997                         match def {
4998                             (DefMethod(..), _) => {
4999                                 self.resolve_error(expr.span,
5000                                                       "first-class methods \
5001                                                        are not supported");
5002                                 self.session.span_note(expr.span,
5003                                                        "call the method \
5004                                                         using the `.` \
5005                                                         syntax");
5006                             }
5007                             _ => {}
5008                         }
5009
5010                         self.record_def(expr.id, def);
5011                     }
5012                     None => {
5013                         let wrong_name = self.path_idents_to_str(path);
5014                         // Be helpful if the name refers to a struct
5015                         // (The pattern matching def_tys where the id is in self.structs
5016                         // matches on regular structs while excluding tuple- and enum-like
5017                         // structs, which wouldn't result in this error.)
5018                         match self.with_no_errors(|this|
5019                             this.resolve_path(expr.id, path, TypeNS, false)) {
5020                             Some((DefTy(struct_id), _))
5021                               if self.structs.contains(&struct_id) => {
5022                                 self.resolve_error(expr.span,
5023                                         format!("`{}` is a structure name, but \
5024                                                  this expression \
5025                                                  uses it like a function name",
5026                                                 wrong_name));
5027
5028                                 self.session.span_note(expr.span,
5029                                     format!("Did you mean to write: \
5030                                             `{} \\{ /* fields */ \\}`?",
5031                                             wrong_name));
5032
5033                             }
5034                             _ =>
5035                                // limit search to 5 to reduce the number
5036                                // of stupid suggestions
5037                                match self.find_best_match_for_name(wrong_name, 5) {
5038                                    Some(m) => {
5039                                        self.resolve_error(expr.span,
5040                                            format!("unresolved name `{}`. \
5041                                                     Did you mean `{}`?",
5042                                                     wrong_name, m));
5043                                    }
5044                                    None => {
5045                                        self.resolve_error(expr.span,
5046                                             format!("unresolved name `{}`.",
5047                                                     wrong_name));
5048                                    }
5049                                }
5050                         }
5051                     }
5052                 }
5053
5054                 visit::walk_expr(self, expr, ());
5055             }
5056
5057             ExprFnBlock(fn_decl, block) |
5058             ExprProc(fn_decl, block) => {
5059                 self.resolve_function(FunctionRibKind(expr.id, block.id),
5060                                       Some(fn_decl), NoTypeParameters,
5061                                       block);
5062             }
5063
5064             ExprStruct(ref path, _, _) => {
5065                 // Resolve the path to the structure it goes to.
5066                 match self.resolve_path(expr.id, path, TypeNS, false) {
5067                     Some((DefTy(class_id), lp)) | Some((DefStruct(class_id), lp))
5068                             if self.structs.contains(&class_id) => {
5069                         let class_def = DefStruct(class_id);
5070                         self.record_def(expr.id, (class_def, lp));
5071                     }
5072                     Some(definition @ (DefVariant(_, class_id, _), _))
5073                             if self.structs.contains(&class_id) => {
5074                         self.record_def(expr.id, definition);
5075                     }
5076                     result => {
5077                         debug!("(resolving expression) didn't find struct \
5078                                 def: {:?}", result);
5079                         let msg = format!("`{}` does not name a structure",
5080                                           self.path_idents_to_str(path));
5081                         self.resolve_error(path.span, msg);
5082                     }
5083                 }
5084
5085                 visit::walk_expr(self, expr, ());
5086             }
5087
5088             ExprLoop(_, Some(label)) => {
5089                 self.with_label_rib(|this| {
5090                     let def_like = DlDef(DefLabel(expr.id));
5091
5092                     {
5093                         let label_ribs = this.label_ribs.borrow();
5094                         let length = label_ribs.len();
5095                         let rib = label_ribs.get(length - 1);
5096                         let renamed = mtwt::resolve(label);
5097                         rib.bindings.borrow_mut().insert(renamed, def_like);
5098                     }
5099
5100                     visit::walk_expr(this, expr, ());
5101                 })
5102             }
5103
5104             ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
5105
5106             ExprBreak(Some(label)) | ExprAgain(Some(label)) => {
5107                 let mut label_ribs = self.label_ribs.borrow_mut();
5108                 let renamed = mtwt::resolve(label);
5109                 match self.search_ribs(&mut *label_ribs, renamed, expr.span) {
5110                     None =>
5111                         self.resolve_error(expr.span,
5112                                               format!("use of undeclared label `{}`",
5113                                                    token::get_ident(label))),
5114                     Some(DlDef(def @ DefLabel(_))) => {
5115                         // Since this def is a label, it is never read.
5116                         self.record_def(expr.id, (def, LastMod(AllPublic)))
5117                     }
5118                     Some(_) => {
5119                         self.session.span_bug(expr.span,
5120                                               "label wasn't mapped to a \
5121                                                label def!")
5122                     }
5123                 }
5124             }
5125
5126             _ => {
5127                 visit::walk_expr(self, expr, ());
5128             }
5129         }
5130     }
5131
5132     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
5133         match expr.node {
5134             ExprField(_, ident, _) => {
5135                 // FIXME(#6890): Even though you can't treat a method like a
5136                 // field, we need to add any trait methods we find that match
5137                 // the field name so that we can do some nice error reporting
5138                 // later on in typeck.
5139                 let traits = self.search_for_traits_containing_method(ident);
5140                 self.trait_map.insert(expr.id, traits);
5141             }
5142             ExprMethodCall(ident, _, _) => {
5143                 debug!("(recording candidate traits for expr) recording \
5144                         traits for {}",
5145                        expr.id);
5146                 let traits = self.search_for_traits_containing_method(ident);
5147                 self.trait_map.insert(expr.id, traits);
5148             }
5149             _ => {
5150                 // Nothing to do.
5151             }
5152         }
5153     }
5154
5155     fn search_for_traits_containing_method(&mut self, name: Ident) -> Vec<DefId> {
5156         debug!("(searching for traits containing method) looking for '{}'",
5157                token::get_ident(name));
5158
5159         let mut found_traits = Vec::new();
5160         let mut search_module = self.current_module;
5161         match self.method_map.borrow().find(&name.name) {
5162             Some(candidate_traits) => loop {
5163                 // Look for the current trait.
5164                 match self.current_trait_refs {
5165                     Some(ref trait_def_ids) => {
5166                         for trait_def_id in trait_def_ids.iter() {
5167                             if candidate_traits.contains(trait_def_id) {
5168                                 self.add_trait_info(&mut found_traits,
5169                                                     *trait_def_id,
5170                                                     name);
5171                             }
5172                         }
5173                     }
5174                     None => {
5175                         // Nothing to do.
5176                     }
5177                 }
5178
5179                 // Look for trait children.
5180                 self.populate_module_if_necessary(search_module);
5181
5182                 for (_, &child_names) in search_module.children.borrow().iter() {
5183                     let def = match child_names.def_for_namespace(TypeNS) {
5184                         Some(def) => def,
5185                         None => continue
5186                     };
5187                     let trait_def_id = match def {
5188                         DefTrait(trait_def_id) => trait_def_id,
5189                         _ => continue,
5190                     };
5191                     if candidate_traits.contains(&trait_def_id) {
5192                         self.add_trait_info(&mut found_traits, trait_def_id,
5193                                             name);
5194                     }
5195                 }
5196
5197                 // Look for imports.
5198                 let import_resolutions = search_module.import_resolutions
5199                                                       .borrow();
5200                 for (_, &import) in import_resolutions.iter() {
5201                     let target = match import.target_for_namespace(TypeNS) {
5202                         None => continue,
5203                         Some(target) => target,
5204                     };
5205                     let did = match target.bindings.def_for_namespace(TypeNS) {
5206                         Some(DefTrait(trait_def_id)) => trait_def_id,
5207                         Some(..) | None => continue,
5208                     };
5209                     if candidate_traits.contains(&did) {
5210                         self.add_trait_info(&mut found_traits, did, name);
5211                         self.used_imports.insert((import.type_id.get(), TypeNS));
5212                     }
5213                 }
5214
5215                 match search_module.parent_link {
5216                     NoParentLink | ModuleParentLink(..) => break,
5217                     BlockParentLink(parent_module, _) => {
5218                         search_module = parent_module;
5219                     }
5220                 }
5221             },
5222             _ => ()
5223         }
5224
5225         return found_traits;
5226     }
5227
5228     fn add_trait_info(&self,
5229                           found_traits: &mut Vec<DefId> ,
5230                           trait_def_id: DefId,
5231                           name: Ident) {
5232         debug!("(adding trait info) found trait {}:{} for method '{}'",
5233                trait_def_id.krate,
5234                trait_def_id.node,
5235                token::get_ident(name));
5236         found_traits.push(trait_def_id);
5237     }
5238
5239     fn record_def(&mut self, node_id: NodeId, (def, lp): (Def, LastPrivate)) {
5240         debug!("(recording def) recording {:?} for {:?}, last private {:?}",
5241                 def, node_id, lp);
5242         assert!(match lp {LastImport{..} => false, _ => true},
5243                 "Import should only be used for `use` directives");
5244         self.last_private.insert(node_id, lp);
5245         self.def_map.borrow_mut().insert_or_update_with(node_id, def, |_, old_value| {
5246             // Resolve appears to "resolve" the same ID multiple
5247             // times, so here is a sanity check it at least comes to
5248             // the same conclusion! - nmatsakis
5249             if def != *old_value {
5250                 self.session.bug(format!("node_id {:?} resolved first to {:?} \
5251                                       and then {:?}", node_id, *old_value, def));
5252             }
5253         });
5254     }
5255
5256     fn enforce_default_binding_mode(&mut self,
5257                                         pat: &Pat,
5258                                         pat_binding_mode: BindingMode,
5259                                         descr: &str) {
5260         match pat_binding_mode {
5261             BindByValue(_) => {}
5262             BindByRef(..) => {
5263                 self.resolve_error(
5264                     pat.span,
5265                     format!("cannot use `ref` binding mode with {}",
5266                          descr));
5267             }
5268         }
5269     }
5270
5271     //
5272     // Unused import checking
5273     //
5274     // Although this is mostly a lint pass, it lives in here because it depends on
5275     // resolve data structures and because it finalises the privacy information for
5276     // `use` directives.
5277     //
5278
5279     fn check_for_unused_imports(&mut self, krate: &ast::Crate) {
5280         let mut visitor = UnusedImportCheckVisitor{ resolver: self };
5281         visit::walk_crate(&mut visitor, krate, ());
5282     }
5283
5284     fn check_for_item_unused_imports(&mut self, vi: &ViewItem) {
5285         // Ignore is_public import statements because there's no way to be sure
5286         // whether they're used or not. Also ignore imports with a dummy span
5287         // because this means that they were generated in some fashion by the
5288         // compiler and we don't need to consider them.
5289         if vi.vis == Public { return }
5290         if vi.span == DUMMY_SP { return }
5291
5292         match vi.node {
5293             ViewItemExternCrate(..) => {} // ignore
5294             ViewItemUse(ref path) => {
5295                 for p in path.iter() {
5296                     match p.node {
5297                         ViewPathSimple(_, _, id) => self.finalize_import(id, p.span),
5298                         ViewPathList(_, ref list, _) => {
5299                             for i in list.iter() {
5300                                 self.finalize_import(i.node.id, i.span);
5301                             }
5302                         },
5303                         ViewPathGlob(_, id) => {
5304                             if !self.used_imports.contains(&(id, TypeNS)) &&
5305                                !self.used_imports.contains(&(id, ValueNS)) {
5306                                 self.session.add_lint(UnusedImports, id, p.span, ~"unused import");
5307                             }
5308                         },
5309                     }
5310                 }
5311             }
5312         }
5313     }
5314
5315     // We have information about whether `use` (import) directives are actually used now.
5316     // If an import is not used at all, we signal a lint error. If an import is only used
5317     // for a single namespace, we remove the other namespace from the recorded privacy
5318     // information. That means in privacy.rs, we will only check imports and namespaces
5319     // which are used. In particular, this means that if an import could name either a
5320     // public or private item, we will check the correct thing, dependent on how the import
5321     // is used.
5322     fn finalize_import(&mut self, id: NodeId, span: Span) {
5323         debug!("finalizing import uses for {}", self.session.codemap().span_to_snippet(span));
5324
5325         if !self.used_imports.contains(&(id, TypeNS)) &&
5326            !self.used_imports.contains(&(id, ValueNS)) {
5327             self.session.add_lint(UnusedImports, id, span, ~"unused import");
5328         }
5329
5330         let (v_priv, t_priv) = match self.last_private.find(&id) {
5331             Some(&LastImport{value_priv: v,
5332                              value_used: _,
5333                              type_priv: t,
5334                              type_used: _}) => (v, t),
5335             Some(_) => fail!("We should only have LastImport for `use` directives"),
5336             _ => return,
5337         };
5338
5339         let mut v_used = if self.used_imports.contains(&(id, ValueNS)) {
5340             Used
5341         } else {
5342             Unused
5343         };
5344         let t_used = if self.used_imports.contains(&(id, TypeNS)) {
5345             Used
5346         } else {
5347             Unused
5348         };
5349
5350         match (v_priv, t_priv) {
5351             // Since some items may be both in the value _and_ type namespaces (e.g., structs)
5352             // we might have two LastPrivates pointing at the same thing. There is no point
5353             // checking both, so lets not check the value one.
5354             (Some(DependsOn(def_v)), Some(DependsOn(def_t))) if def_v == def_t => v_used = Unused,
5355             _ => {},
5356         }
5357
5358         self.last_private.insert(id, LastImport{value_priv: v_priv,
5359                                                 value_used: v_used,
5360                                                 type_priv: t_priv,
5361                                                 type_used: t_used});
5362     }
5363
5364     //
5365     // Diagnostics
5366     //
5367     // Diagnostics are not particularly efficient, because they're rarely
5368     // hit.
5369     //
5370
5371     /// A somewhat inefficient routine to obtain the name of a module.
5372     fn module_to_str(&mut self, module_: @Module) -> ~str {
5373         let mut idents = Vec::new();
5374         let mut current_module = module_;
5375         loop {
5376             match current_module.parent_link {
5377                 NoParentLink => {
5378                     break;
5379                 }
5380                 ModuleParentLink(module_, name) => {
5381                     idents.push(name);
5382                     current_module = module_;
5383                 }
5384                 BlockParentLink(module_, _) => {
5385                     idents.push(special_idents::opaque);
5386                     current_module = module_;
5387                 }
5388             }
5389         }
5390
5391         if idents.len() == 0 {
5392             return ~"???";
5393         }
5394         return self.idents_to_str(idents.move_iter()
5395                                         .rev()
5396                                         .collect::<Vec<ast::Ident>>()
5397                                         .as_slice());
5398     }
5399
5400     #[allow(dead_code)]   // useful for debugging
5401     fn dump_module(&mut self, module_: @Module) {
5402         debug!("Dump of module `{}`:", self.module_to_str(module_));
5403
5404         debug!("Children:");
5405         self.populate_module_if_necessary(module_);
5406         for (&name, _) in module_.children.borrow().iter() {
5407             debug!("* {}", token::get_name(name));
5408         }
5409
5410         debug!("Import resolutions:");
5411         let import_resolutions = module_.import_resolutions.borrow();
5412         for (&name, import_resolution) in import_resolutions.iter() {
5413             let value_repr;
5414             match import_resolution.target_for_namespace(ValueNS) {
5415                 None => { value_repr = ~""; }
5416                 Some(_) => {
5417                     value_repr = ~" value:?";
5418                     // FIXME #4954
5419                 }
5420             }
5421
5422             let type_repr;
5423             match import_resolution.target_for_namespace(TypeNS) {
5424                 None => { type_repr = ~""; }
5425                 Some(_) => {
5426                     type_repr = ~" type:?";
5427                     // FIXME #4954
5428                 }
5429             }
5430
5431             debug!("* {}:{}{}", token::get_name(name), value_repr, type_repr);
5432         }
5433     }
5434 }
5435
5436 pub struct CrateMap {
5437     pub def_map: DefMap,
5438     pub exp_map2: ExportMap2,
5439     pub trait_map: TraitMap,
5440     pub external_exports: ExternalExports,
5441     pub last_private_map: LastPrivateMap,
5442 }
5443
5444 /// Entry point to crate resolution.
5445 pub fn resolve_crate(session: &Session,
5446                      lang_items: @LanguageItems,
5447                      krate: &Crate)
5448                   -> CrateMap {
5449     let mut resolver = Resolver(session, lang_items, krate.span);
5450     resolver.resolve(krate);
5451     let Resolver { def_map, export_map2, trait_map, last_private,
5452                    external_exports, .. } = resolver;
5453     CrateMap {
5454         def_map: def_map,
5455         exp_map2: export_map2,
5456         trait_map: trait_map,
5457         external_exports: external_exports,
5458         last_private_map: last_private,
5459     }
5460 }