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