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