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