src/librustc_resolve/lib.rs

   1 // Copyright 2012-2015 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 // Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364)
  12 #![cfg_attr(stage0, feature(custom_attribute))]
  13 #![crate_name = "rustc_resolve"]
  14 #![unstable(feature = "rustc_private")]
  15 #![staged_api]
  16 #![crate_type = "dylib"]
  17 #![crate_type = "rlib"]
  18 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  19       html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
  20       html_root_url = "http://doc.rust-lang.org/nightly/")]
  21
  22 #![feature(associated_consts)]
  23 #![feature(rc_weak)]
  24 #![feature(rustc_diagnostic_macros)]
  25 #![feature(rustc_private)]
  26 #![feature(slice_extras)]
  27 #![feature(staged_api)]
  28
  29 #[macro_use] extern crate log;
  30 #[macro_use] extern crate syntax;
  31 #[macro_use] #[no_link] extern crate rustc_bitflags;
  32
  33 extern crate rustc;
  34
  35 use self::PatternBindingMode::*;
  36 use self::Namespace::*;
  37 use self::NamespaceResult::*;
  38 use self::NameDefinition::*;
  39 use self::ResolveResult::*;
  40 use self::FallbackSuggestion::*;
  41 use self::TypeParameters::*;
  42 use self::RibKind::*;
  43 use self::UseLexicalScopeFlag::*;
  44 use self::ModulePrefixResult::*;
  45 use self::AssocItemResolveResult::*;
  46 use self::NameSearchType::*;
  47 use self::BareIdentifierPatternResolution::*;
  48 use self::ParentLink::*;
  49 use self::ModuleKind::*;
  50 use self::FallbackChecks::*;
  51
  52 use rustc::ast_map;
  53 use rustc::session::Session;
  54 use rustc::lint;
  55 use rustc::metadata::csearch;
  56 use rustc::metadata::decoder::{DefLike, DlDef, DlField, DlImpl};
  57 use rustc::middle::def::*;
  58 use rustc::middle::pat_util::pat_bindings;
  59 use rustc::middle::privacy::*;
  60 use rustc::middle::subst::{ParamSpace, FnSpace, TypeSpace};
  61 use rustc::middle::ty::{Freevar, FreevarMap, TraitMap, GlobMap};
  62 use rustc::util::nodemap::{NodeMap, NodeSet, DefIdSet, FnvHashMap};
  63 use rustc::util::lev_distance::lev_distance;
  64
  65 use syntax::ast::{Arm, BindByRef, BindByValue, BindingMode, Block};
  66 use syntax::ast::{ConstImplItem, Crate, CrateNum};
  67 use syntax::ast::{DefId, Expr, ExprAgain, ExprBreak, ExprField};
  68 use syntax::ast::{ExprLoop, ExprWhile, ExprMethodCall};
  69 use syntax::ast::{ExprPath, ExprStruct, FnDecl};
  70 use syntax::ast::{ForeignItemFn, ForeignItemStatic, Generics};
  71 use syntax::ast::{Ident, ImplItem, Item, ItemConst, ItemEnum, ItemExternCrate};
  72 use syntax::ast::{ItemFn, ItemForeignMod, ItemImpl, ItemMac, ItemMod, ItemStatic, ItemDefaultImpl};
  73 use syntax::ast::{ItemStruct, ItemTrait, ItemTy, ItemUse};
  74 use syntax::ast::{Local, MethodImplItem, Name, NodeId};
  75 use syntax::ast::{Pat, PatEnum, PatIdent, PatLit, PatQPath};
  76 use syntax::ast::{PatRange, PatStruct, Path, PrimTy};
  77 use syntax::ast::{TraitRef, Ty, TyBool, TyChar, TyF32};
  78 use syntax::ast::{TyF64, TyFloat, TyIs, TyI8, TyI16, TyI32, TyI64, TyInt};
  79 use syntax::ast::{TyPath, TyPtr};
  80 use syntax::ast::{TyRptr, TyStr, TyUs, TyU8, TyU16, TyU32, TyU64, TyUint};
  81 use syntax::ast::TypeImplItem;
  82 use syntax::ast;
  83 use syntax::ast_util::{local_def, walk_pat};
  84 use syntax::attr::AttrMetaMethods;
  85 use syntax::ext::mtwt;
  86 use syntax::parse::token::{self, special_names, special_idents};
  87 use syntax::ptr::P;
  88 use syntax::codemap::{self, Span, Pos};
  89 use syntax::visit::{self, Visitor};
  90
  91 use std::collections::{HashMap, HashSet};
  92 use std::collections::hash_map::Entry::{Occupied, Vacant};
  93 use std::cell::{Cell, RefCell};
  94 use std::fmt;
  95 use std::mem::replace;
  96 use std::rc::{Rc, Weak};
  97 use std::usize;
  98
  99 use resolve_imports::{Target, ImportDirective, ImportResolution};
 100 use resolve_imports::Shadowable;
 101
 102
 103 // NB: This module needs to be declared first so diagnostics are
 104 // registered before they are used.
 105 pub mod diagnostics;
 106
 107 mod check_unused;
 108 mod record_exports;
 109 mod build_reduced_graph;
 110 mod resolve_imports;
 111
 112 macro_rules! span_err {
 113     ($session:expr, $span:expr, $code:ident, $($message:tt)*) => ({
 114         __diagnostic_used!($code);
 115         $session.span_err_with_code($span, &format!($($message)*), stringify!($code))
 116     })
 117 }
 118
 119 macro_rules! resolve_err {
 120     ($this:expr, $span:expr, $code:ident, $($rest:tt)*) => {
 121         if $this.emit_errors {
 122             span_err!($this.session, $span, $code, $($rest)*);
 123         }
 124     }
 125 }
 126
 127 #[derive(Copy, Clone)]
 128 struct BindingInfo {
 129     span: Span,
 130     binding_mode: BindingMode,
 131 }
 132
 133 // Map from the name in a pattern to its binding mode.
 134 type BindingMap = HashMap<Name, BindingInfo>;
 135
 136 #[derive(Copy, Clone, PartialEq)]
 137 enum PatternBindingMode {
 138     RefutableMode,
 139     LocalIrrefutableMode,
 140     ArgumentIrrefutableMode,
 141 }
 142
 143 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 144 enum Namespace {
 145     TypeNS,
 146     ValueNS
 147 }
 148
 149 /// A NamespaceResult represents the result of resolving an import in
 150 /// a particular namespace. The result is either definitely-resolved,
 151 /// definitely- unresolved, or unknown.
 152 #[derive(Clone)]
 153 enum NamespaceResult {
 154     /// Means that resolve hasn't gathered enough information yet to determine
 155     /// whether the name is bound in this namespace. (That is, it hasn't
 156     /// resolved all `use` directives yet.)
 157     UnknownResult,
 158     /// Means that resolve has determined that the name is definitely
 159     /// not bound in the namespace.
 160     UnboundResult,
 161     /// Means that resolve has determined that the name is bound in the Module
 162     /// argument, and specified by the NameBindings argument.
 163     BoundResult(Rc<Module>, Rc<NameBindings>)
 164 }
 165
 166 impl NamespaceResult {
 167     fn is_unknown(&self) -> bool {
 168         match *self {
 169             UnknownResult => true,
 170             _ => false
 171         }
 172     }
 173     fn is_unbound(&self) -> bool {
 174         match *self {
 175             UnboundResult => true,
 176             _ => false
 177         }
 178     }
 179 }
 180
 181 enum NameDefinition {
 182     // The name was unbound.
 183     NoNameDefinition,
 184     // The name identifies an immediate child.
 185     ChildNameDefinition(Def, LastPrivate),
 186     // The name identifies an import.
 187     ImportNameDefinition(Def, LastPrivate),
 188 }
 189
 190 impl<'a, 'v, 'tcx> Visitor<'v> for Resolver<'a, 'tcx> {
 191     fn visit_item(&mut self, item: &Item) {
 192         self.resolve_item(item);
 193     }
 194     fn visit_arm(&mut self, arm: &Arm) {
 195         self.resolve_arm(arm);
 196     }
 197     fn visit_block(&mut self, block: &Block) {
 198         self.resolve_block(block);
 199     }
 200     fn visit_expr(&mut self, expr: &Expr) {
 201         self.resolve_expr(expr);
 202     }
 203     fn visit_local(&mut self, local: &Local) {
 204         self.resolve_local(local);
 205     }
 206     fn visit_ty(&mut self, ty: &Ty) {
 207         self.resolve_type(ty);
 208     }
 209     fn visit_generics(&mut self, generics: &Generics) {
 210         self.resolve_generics(generics);
 211     }
 212     fn visit_poly_trait_ref(&mut self,
 213                             tref: &ast::PolyTraitRef,
 214                             m: &ast::TraitBoundModifier) {
 215         match self.resolve_trait_reference(tref.trait_ref.ref_id, &tref.trait_ref.path, 0) {
 216             Ok(def) => self.record_def(tref.trait_ref.ref_id, def),
 217             Err(_) => { /* error already reported */ }
 218         }
 219         visit::walk_poly_trait_ref(self, tref, m);
 220     }
 221     fn visit_variant(&mut self, variant: &ast::Variant, generics: &Generics) {
 222         if let Some(ref dis_expr) = variant.node.disr_expr {
 223             // resolve the discriminator expr as a constant
 224             self.with_constant_rib(|this| {
 225                 this.visit_expr(&**dis_expr);
 226             });
 227         }
 228
 229         // `visit::walk_variant` without the discriminant expression.
 230         match variant.node.kind {
 231             ast::TupleVariantKind(ref variant_arguments) => {
 232                 for variant_argument in variant_arguments {
 233                     self.visit_ty(&*variant_argument.ty);
 234                 }
 235             }
 236             ast::StructVariantKind(ref struct_definition) => {
 237                 self.visit_struct_def(&**struct_definition,
 238                                       variant.node.name,
 239                                       generics,
 240                                       variant.node.id);
 241             }
 242         }
 243     }
 244     fn visit_foreign_item(&mut self, foreign_item: &ast::ForeignItem) {
 245         let type_parameters = match foreign_item.node {
 246             ForeignItemFn(_, ref generics) => {
 247                 HasTypeParameters(generics, FnSpace, ItemRibKind)
 248             }
 249             ForeignItemStatic(..) => NoTypeParameters
 250         };
 251         self.with_type_parameter_rib(type_parameters, |this| {
 252             visit::walk_foreign_item(this, foreign_item);
 253         });
 254     }
 255     fn visit_fn(&mut self,
 256                 function_kind: visit::FnKind<'v>,
 257                 declaration: &'v FnDecl,
 258                 block: &'v Block,
 259                 _: Span,
 260                 node_id: NodeId) {
 261         let rib_kind = match function_kind {
 262             visit::FkItemFn(_, generics, _, _, _, _) => {
 263                 self.visit_generics(generics);
 264                 ItemRibKind
 265             }
 266             visit::FkMethod(_, sig, _) => {
 267                 self.visit_generics(&sig.generics);
 268                 self.visit_explicit_self(&sig.explicit_self);
 269                 MethodRibKind
 270             }
 271             visit::FkFnBlock(..) => ClosureRibKind(node_id)
 272         };
 273         self.resolve_function(rib_kind, declaration, block);
 274     }
 275 }
 276
 277 type ErrorMessage = Option<(Span, String)>;
 278
 279 enum ResolveResult<T> {
 280     Failed(ErrorMessage),   // Failed to resolve the name, optional helpful error message.
 281     Indeterminate,          // Couldn't determine due to unresolved globs.
 282     Success(T)              // Successfully resolved the import.
 283 }
 284
 285 impl<T> ResolveResult<T> {
 286     fn indeterminate(&self) -> bool {
 287         match *self { Indeterminate => true, _ => false }
 288     }
 289 }
 290
 291 enum FallbackSuggestion {
 292     NoSuggestion,
 293     Field,
 294     Method,
 295     TraitItem,
 296     StaticMethod(String),
 297     TraitMethod(String),
 298 }
 299
 300 #[derive(Copy, Clone)]
 301 enum TypeParameters<'a> {
 302     NoTypeParameters,
 303     HasTypeParameters(
 304         // Type parameters.
 305         &'a Generics,
 306
 307         // Identifies the things that these parameters
 308         // were declared on (type, fn, etc)
 309         ParamSpace,
 310
 311         // The kind of the rib used for type parameters.
 312         RibKind)
 313 }
 314
 315 // The rib kind controls the translation of local
 316 // definitions (`DefLocal`) to upvars (`DefUpvar`).
 317 #[derive(Copy, Clone, Debug)]
 318 enum RibKind {
 319     // No translation needs to be applied.
 320     NormalRibKind,
 321
 322     // We passed through a closure scope at the given node ID.
 323     // Translate upvars as appropriate.
 324     ClosureRibKind(NodeId /* func id */),
 325
 326     // We passed through an impl or trait and are now in one of its
 327     // methods. Allow references to ty params that impl or trait
 328     // binds. Disallow any other upvars (including other ty params that are
 329     // upvars).
 330     MethodRibKind,
 331
 332     // We passed through an item scope. Disallow upvars.
 333     ItemRibKind,
 334
 335     // We're in a constant item. Can't refer to dynamic stuff.
 336     ConstantItemRibKind
 337 }
 338
 339 #[derive(Copy, Clone)]
 340 enum UseLexicalScopeFlag {
 341     DontUseLexicalScope,
 342     UseLexicalScope
 343 }
 344
 345 enum ModulePrefixResult {
 346     NoPrefixFound,
 347     PrefixFound(Rc<Module>, usize)
 348 }
 349
 350 #[derive(Copy, Clone)]
 351 enum AssocItemResolveResult {
 352     /// Syntax such as `<T>::item`, which can't be resolved until type
 353     /// checking.
 354     TypecheckRequired,
 355     /// We should have been able to resolve the associated item.
 356     ResolveAttempt(Option<PathResolution>),
 357 }
 358
 359 #[derive(Copy, Clone, PartialEq)]
 360 enum NameSearchType {
 361     /// We're doing a name search in order to resolve a `use` directive.
 362     ImportSearch,
 363
 364     /// We're doing a name search in order to resolve a path type, a path
 365     /// expression, or a path pattern.
 366     PathSearch,
 367 }
 368
 369 #[derive(Copy, Clone)]
 370 enum BareIdentifierPatternResolution {
 371     FoundStructOrEnumVariant(Def, LastPrivate),
 372     FoundConst(Def, LastPrivate),
 373     BareIdentifierPatternUnresolved
 374 }
 375
 376 /// One local scope.
 377 #[derive(Debug)]
 378 struct Rib {
 379     bindings: HashMap<Name, DefLike>,
 380     kind: RibKind,
 381 }
 382
 383 impl Rib {
 384     fn new(kind: RibKind) -> Rib {
 385         Rib {
 386             bindings: HashMap::new(),
 387             kind: kind
 388         }
 389     }
 390 }
 391
 392 /// The link from a module up to its nearest parent node.
 393 #[derive(Clone,Debug)]
 394 enum ParentLink {
 395     NoParentLink,
 396     ModuleParentLink(Weak<Module>, Name),
 397     BlockParentLink(Weak<Module>, NodeId)
 398 }
 399
 400 /// The type of module this is.
 401 #[derive(Copy, Clone, PartialEq, Debug)]
 402 enum ModuleKind {
 403     NormalModuleKind,
 404     TraitModuleKind,
 405     EnumModuleKind,
 406     TypeModuleKind,
 407     AnonymousModuleKind,
 408 }
 409
 410 /// One node in the tree of modules.
 411 pub struct Module {
 412     parent_link: ParentLink,
 413     def_id: Cell<Option<DefId>>,
 414     kind: Cell<ModuleKind>,
 415     is_public: bool,
 416
 417     children: RefCell<HashMap<Name, Rc<NameBindings>>>,
 418     imports: RefCell<Vec<ImportDirective>>,
 419
 420     // The external module children of this node that were declared with
 421     // `extern crate`.
 422     external_module_children: RefCell<HashMap<Name, Rc<Module>>>,
 423
 424     // The anonymous children of this node. Anonymous children are pseudo-
 425     // modules that are implicitly created around items contained within
 426     // blocks.
 427     //
 428     // For example, if we have this:
 429     //
 430     //  fn f() {
 431     //      fn g() {
 432     //          ...
 433     //      }
 434     //  }
 435     //
 436     // There will be an anonymous module created around `g` with the ID of the
 437     // entry block for `f`.
 438     anonymous_children: RefCell<NodeMap<Rc<Module>>>,
 439
 440     // The status of resolving each import in this module.
 441     import_resolutions: RefCell<HashMap<Name, ImportResolution>>,
 442
 443     // The number of unresolved globs that this module exports.
 444     glob_count: Cell<usize>,
 445
 446     // The index of the import we're resolving.
 447     resolved_import_count: Cell<usize>,
 448
 449     // Whether this module is populated. If not populated, any attempt to
 450     // access the children must be preceded with a
 451     // `populate_module_if_necessary` call.
 452     populated: Cell<bool>,
 453 }
 454
 455 impl Module {
 456     fn new(parent_link: ParentLink,
 457            def_id: Option<DefId>,
 458            kind: ModuleKind,
 459            external: bool,
 460            is_public: bool)
 461            -> Module {
 462         Module {
 463             parent_link: parent_link,
 464             def_id: Cell::new(def_id),
 465             kind: Cell::new(kind),
 466             is_public: is_public,
 467             children: RefCell::new(HashMap::new()),
 468             imports: RefCell::new(Vec::new()),
 469             external_module_children: RefCell::new(HashMap::new()),
 470             anonymous_children: RefCell::new(NodeMap()),
 471             import_resolutions: RefCell::new(HashMap::new()),
 472             glob_count: Cell::new(0),
 473             resolved_import_count: Cell::new(0),
 474             populated: Cell::new(!external),
 475         }
 476     }
 477
 478     fn all_imports_resolved(&self) -> bool {
 479         self.imports.borrow().len() == self.resolved_import_count.get()
 480     }
 481 }
 482
 483 impl fmt::Debug for Module {
 484     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 485         write!(f, "{:?}, kind: {:?}, {}",
 486                self.def_id,
 487                self.kind,
 488                if self.is_public { "public" } else { "private" } )
 489     }
 490 }
 491
 492 bitflags! {
 493     #[derive(Debug)]
 494     flags DefModifiers: u8 {
 495         const PUBLIC     = 1 << 0,
 496         const IMPORTABLE = 1 << 1,
 497     }
 498 }
 499
 500 // Records a possibly-private type definition.
 501 #[derive(Clone,Debug)]
 502 struct TypeNsDef {
 503     modifiers: DefModifiers, // see note in ImportResolution about how to use this
 504     module_def: Option<Rc<Module>>,
 505     type_def: Option<Def>,
 506     type_span: Option<Span>
 507 }
 508
 509 // Records a possibly-private value definition.
 510 #[derive(Clone, Copy, Debug)]
 511 struct ValueNsDef {
 512     modifiers: DefModifiers, // see note in ImportResolution about how to use this
 513     def: Def,
 514     value_span: Option<Span>,
 515 }
 516
 517 // Records the definitions (at most one for each namespace) that a name is
 518 // bound to.
 519 #[derive(Debug)]
 520 pub struct NameBindings {
 521     type_def: RefCell<Option<TypeNsDef>>,   //< Meaning in type namespace.
 522     value_def: RefCell<Option<ValueNsDef>>, //< Meaning in value namespace.
 523 }
 524
 525 impl NameBindings {
 526     fn new() -> NameBindings {
 527         NameBindings {
 528             type_def: RefCell::new(None),
 529             value_def: RefCell::new(None),
 530         }
 531     }
 532
 533     /// Creates a new module in this set of name bindings.
 534     fn define_module(&self,
 535                      parent_link: ParentLink,
 536                      def_id: Option<DefId>,
 537                      kind: ModuleKind,
 538                      external: bool,
 539                      is_public: bool,
 540                      sp: Span) {
 541         // Merges the module with the existing type def or creates a new one.
 542         let modifiers = if is_public {
 543             DefModifiers::PUBLIC
 544         } else {
 545             DefModifiers::empty()
 546         } | DefModifiers::IMPORTABLE;
 547         let module_ = Rc::new(Module::new(parent_link,
 548                                           def_id,
 549                                           kind,
 550                                           external,
 551                                           is_public));
 552         let type_def = self.type_def.borrow().clone();
 553         match type_def {
 554             None => {
 555                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 556                     modifiers: modifiers,
 557                     module_def: Some(module_),
 558                     type_def: None,
 559                     type_span: Some(sp)
 560                 });
 561             }
 562             Some(type_def) => {
 563                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 564                     modifiers: modifiers,
 565                     module_def: Some(module_),
 566                     type_span: Some(sp),
 567                     type_def: type_def.type_def
 568                 });
 569             }
 570         }
 571     }
 572
 573     /// Sets the kind of the module, creating a new one if necessary.
 574     fn set_module_kind(&self,
 575                        parent_link: ParentLink,
 576                        def_id: Option<DefId>,
 577                        kind: ModuleKind,
 578                        external: bool,
 579                        is_public: bool,
 580                        _sp: Span) {
 581         let modifiers = if is_public {
 582             DefModifiers::PUBLIC
 583         } else {
 584             DefModifiers::empty()
 585         } | DefModifiers::IMPORTABLE;
 586         let type_def = self.type_def.borrow().clone();
 587         match type_def {
 588             None => {
 589                 let module = Module::new(parent_link,
 590                                          def_id,
 591                                          kind,
 592                                          external,
 593                                          is_public);
 594                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 595                     modifiers: modifiers,
 596                     module_def: Some(Rc::new(module)),
 597                     type_def: None,
 598                     type_span: None,
 599                 });
 600             }
 601             Some(type_def) => {
 602                 match type_def.module_def {
 603                     None => {
 604                         let module = Module::new(parent_link,
 605                                                  def_id,
 606                                                  kind,
 607                                                  external,
 608                                                  is_public);
 609                         *self.type_def.borrow_mut() = Some(TypeNsDef {
 610                             modifiers: modifiers,
 611                             module_def: Some(Rc::new(module)),
 612                             type_def: type_def.type_def,
 613                             type_span: None,
 614                         });
 615                     }
 616                     Some(module_def) => module_def.kind.set(kind),
 617                 }
 618             }
 619         }
 620     }
 621
 622     /// Records a type definition.
 623     fn define_type(&self, def: Def, sp: Span, modifiers: DefModifiers) {
 624         debug!("defining type for def {:?} with modifiers {:?}", def, modifiers);
 625         // Merges the type with the existing type def or creates a new one.
 626         let type_def = self.type_def.borrow().clone();
 627         match type_def {
 628             None => {
 629                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 630                     module_def: None,
 631                     type_def: Some(def),
 632                     type_span: Some(sp),
 633                     modifiers: modifiers,
 634                 });
 635             }
 636             Some(type_def) => {
 637                 *self.type_def.borrow_mut() = Some(TypeNsDef {
 638                     module_def: type_def.module_def,
 639                     type_def: Some(def),
 640                     type_span: Some(sp),
 641                     modifiers: modifiers,
 642                 });
 643             }
 644         }
 645     }
 646
 647     /// Records a value definition.
 648     fn define_value(&self, def: Def, sp: Span, modifiers: DefModifiers) {
 649         debug!("defining value for def {:?} with modifiers {:?}", def, modifiers);
 650         *self.value_def.borrow_mut() = Some(ValueNsDef {
 651             def: def,
 652             value_span: Some(sp),
 653             modifiers: modifiers,
 654         });
 655     }
 656
 657     /// Returns the module node if applicable.
 658     fn get_module_if_available(&self) -> Option<Rc<Module>> {
 659         match *self.type_def.borrow() {
 660             Some(ref type_def) => type_def.module_def.clone(),
 661             None => None
 662         }
 663     }
 664
 665     /// Returns the module node. Panics if this node does not have a module
 666     /// definition.
 667     fn get_module(&self) -> Rc<Module> {
 668         match self.get_module_if_available() {
 669             None => {
 670                 panic!("get_module called on a node with no module \
 671                        definition!")
 672             }
 673             Some(module_def) => module_def
 674         }
 675     }
 676
 677     fn defined_in_namespace(&self, namespace: Namespace) -> bool {
 678         match namespace {
 679             TypeNS   => return self.type_def.borrow().is_some(),
 680             ValueNS  => return self.value_def.borrow().is_some()
 681         }
 682     }
 683
 684     fn defined_in_public_namespace(&self, namespace: Namespace) -> bool {
 685         self.defined_in_namespace_with(namespace, DefModifiers::PUBLIC)
 686     }
 687
 688     fn defined_in_namespace_with(&self, namespace: Namespace, modifiers: DefModifiers) -> bool {
 689         match namespace {
 690             TypeNS => match *self.type_def.borrow() {
 691                 Some(ref def) => def.modifiers.contains(modifiers), None => false
 692             },
 693             ValueNS => match *self.value_def.borrow() {
 694                 Some(ref def) => def.modifiers.contains(modifiers), None => false
 695             }
 696         }
 697     }
 698
 699     fn def_for_namespace(&self, namespace: Namespace) -> Option<Def> {
 700         match namespace {
 701             TypeNS => {
 702                 match *self.type_def.borrow() {
 703                     None => None,
 704                     Some(ref type_def) => {
 705                         match type_def.type_def {
 706                             Some(type_def) => Some(type_def),
 707                             None => {
 708                                 match type_def.module_def {
 709                                     Some(ref module) => {
 710                                         match module.def_id.get() {
 711                                             Some(did) => Some(DefMod(did)),
 712                                             None => None,
 713                                         }
 714                                     }
 715                                     None => None,
 716                                 }
 717                             }
 718                         }
 719                     }
 720                 }
 721             }
 722             ValueNS => {
 723                 match *self.value_def.borrow() {
 724                     None => None,
 725                     Some(value_def) => Some(value_def.def)
 726                 }
 727             }
 728         }
 729     }
 730
 731     fn span_for_namespace(&self, namespace: Namespace) -> Option<Span> {
 732         if self.defined_in_namespace(namespace) {
 733             match namespace {
 734                 TypeNS  => {
 735                     match *self.type_def.borrow() {
 736                         None => None,
 737                         Some(ref type_def) => type_def.type_span
 738                     }
 739                 }
 740                 ValueNS => {
 741                     match *self.value_def.borrow() {
 742                         None => None,
 743                         Some(ref value_def) => value_def.value_span
 744                     }
 745                 }
 746             }
 747         } else {
 748             None
 749         }
 750     }
 751
 752     fn is_public(&self, namespace: Namespace) -> bool {
 753         match namespace {
 754             TypeNS  => {
 755                 let type_def = self.type_def.borrow();
 756                 type_def.as_ref().unwrap().modifiers.contains(DefModifiers::PUBLIC)
 757             }
 758             ValueNS => {
 759                 let value_def = self.value_def.borrow();
 760                 value_def.as_ref().unwrap().modifiers.contains(DefModifiers::PUBLIC)
 761             }
 762         }
 763     }
 764 }
 765
 766 /// Interns the names of the primitive types.
 767 struct PrimitiveTypeTable {
 768     primitive_types: HashMap<Name, PrimTy>,
 769 }
 770
 771 impl PrimitiveTypeTable {
 772     fn new() -> PrimitiveTypeTable {
 773         let mut table = PrimitiveTypeTable {
 774             primitive_types: HashMap::new()
 775         };
 776
 777         table.intern("bool",    TyBool);
 778         table.intern("char",    TyChar);
 779         table.intern("f32",     TyFloat(TyF32));
 780         table.intern("f64",     TyFloat(TyF64));
 781         table.intern("isize",   TyInt(TyIs));
 782         table.intern("i8",      TyInt(TyI8));
 783         table.intern("i16",     TyInt(TyI16));
 784         table.intern("i32",     TyInt(TyI32));
 785         table.intern("i64",     TyInt(TyI64));
 786         table.intern("str",     TyStr);
 787         table.intern("usize",   TyUint(TyUs));
 788         table.intern("u8",      TyUint(TyU8));
 789         table.intern("u16",     TyUint(TyU16));
 790         table.intern("u32",     TyUint(TyU32));
 791         table.intern("u64",     TyUint(TyU64));
 792
 793         table
 794     }
 795
 796     fn intern(&mut self, string: &str, primitive_type: PrimTy) {
 797         self.primitive_types.insert(token::intern(string), primitive_type);
 798     }
 799 }
 800
 801 /// The main resolver class.
 802 pub struct Resolver<'a, 'tcx:'a> {
 803     session: &'a Session,
 804
 805     ast_map: &'a ast_map::Map<'tcx>,
 806
 807     graph_root: NameBindings,
 808
 809     trait_item_map: FnvHashMap<(Name, DefId), DefId>,
 810
 811     structs: FnvHashMap<DefId, Vec<Name>>,
 812
 813     // The number of imports that are currently unresolved.
 814     unresolved_imports: usize,
 815
 816     // The module that represents the current item scope.
 817     current_module: Rc<Module>,
 818
 819     // The current set of local scopes, for values.
 820     // FIXME #4948: Reuse ribs to avoid allocation.
 821     value_ribs: Vec<Rib>,
 822
 823     // The current set of local scopes, for types.
 824     type_ribs: Vec<Rib>,
 825
 826     // The current set of local scopes, for labels.
 827     label_ribs: Vec<Rib>,
 828
 829     // The trait that the current context can refer to.
 830     current_trait_ref: Option<(DefId, TraitRef)>,
 831
 832     // The current self type if inside an impl (used for better errors).
 833     current_self_type: Option<Ty>,
 834
 835     // The idents for the primitive types.
 836     primitive_type_table: PrimitiveTypeTable,
 837
 838     def_map: DefMap,
 839     freevars: RefCell<FreevarMap>,
 840     freevars_seen: RefCell<NodeMap<NodeSet>>,
 841     export_map: ExportMap,
 842     trait_map: TraitMap,
 843     external_exports: ExternalExports,
 844
 845     // Whether or not to print error messages. Can be set to true
 846     // when getting additional info for error message suggestions,
 847     // so as to avoid printing duplicate errors
 848     emit_errors: bool,
 849
 850     make_glob_map: bool,
 851     // Maps imports to the names of items actually imported (this actually maps
 852     // all imports, but only glob imports are actually interesting).
 853     glob_map: GlobMap,
 854
 855     used_imports: HashSet<(NodeId, Namespace)>,
 856     used_crates: HashSet<CrateNum>,
 857 }
 858
 859 #[derive(PartialEq)]
 860 enum FallbackChecks {
 861     Everything,
 862     OnlyTraitAndStatics
 863 }
 864
 865 impl<'a, 'tcx> Resolver<'a, 'tcx> {
 866     fn new(session: &'a Session,
 867            ast_map: &'a ast_map::Map<'tcx>,
 868            crate_span: Span,
 869            make_glob_map: MakeGlobMap) -> Resolver<'a, 'tcx> {
 870         let graph_root = NameBindings::new();
 871
 872         graph_root.define_module(NoParentLink,
 873                                  Some(DefId { krate: 0, node: 0 }),
 874                                  NormalModuleKind,
 875                                  false,
 876                                  true,
 877                                  crate_span);
 878
 879         let current_module = graph_root.get_module();
 880
 881         Resolver {
 882             session: session,
 883
 884             ast_map: ast_map,
 885
 886             // The outermost module has def ID 0; this is not reflected in the
 887             // AST.
 888
 889             graph_root: graph_root,
 890
 891             trait_item_map: FnvHashMap(),
 892             structs: FnvHashMap(),
 893
 894             unresolved_imports: 0,
 895
 896             current_module: current_module,
 897             value_ribs: Vec::new(),
 898             type_ribs: Vec::new(),
 899             label_ribs: Vec::new(),
 900
 901             current_trait_ref: None,
 902             current_self_type: None,
 903
 904             primitive_type_table: PrimitiveTypeTable::new(),
 905
 906             def_map: RefCell::new(NodeMap()),
 907             freevars: RefCell::new(NodeMap()),
 908             freevars_seen: RefCell::new(NodeMap()),
 909             export_map: NodeMap(),
 910             trait_map: NodeMap(),
 911             used_imports: HashSet::new(),
 912             used_crates: HashSet::new(),
 913             external_exports: DefIdSet(),
 914
 915             emit_errors: true,
 916             make_glob_map: make_glob_map == MakeGlobMap::Yes,
 917             glob_map: HashMap::new(),
 918         }
 919     }
 920
 921     #[inline]
 922     fn record_import_use(&mut self, import_id: NodeId, name: Name) {
 923         if !self.make_glob_map {
 924             return;
 925         }
 926         if self.glob_map.contains_key(&import_id) {
 927             self.glob_map.get_mut(&import_id).unwrap().insert(name);
 928             return;
 929         }
 930
 931         let mut new_set = HashSet::new();
 932         new_set.insert(name);
 933         self.glob_map.insert(import_id, new_set);
 934     }
 935
 936     fn get_trait_name(&self, did: DefId) -> Name {
 937         if did.krate == ast::LOCAL_CRATE {
 938             self.ast_map.expect_item(did.node).ident.name
 939         } else {
 940             csearch::get_trait_name(&self.session.cstore, did)
 941         }
 942     }
 943
 944     fn create_name_bindings_from_module(module: Rc<Module>) -> NameBindings {
 945         NameBindings {
 946             type_def: RefCell::new(Some(TypeNsDef {
 947                 modifiers: DefModifiers::IMPORTABLE,
 948                 module_def: Some(module),
 949                 type_def: None,
 950                 type_span: None
 951             })),
 952             value_def: RefCell::new(None),
 953         }
 954     }
 955
 956     /// Checks that the names of external crates don't collide with other
 957     /// external crates.
 958     fn check_for_conflicts_between_external_crates(&self,
 959                                                    module: &Module,
 960                                                    name: Name,
 961                                                    span: Span) {
 962         if module.external_module_children.borrow().contains_key(&name) {
 963                 span_err!(self.session, span, E0259,
 964                           "an external crate named `{}` has already \
 965                            been imported into this module",
 966                           name);
 967         }
 968     }
 969
 970     /// Checks that the names of items don't collide with external crates.
 971     fn check_for_conflicts_between_external_crates_and_items(&self,
 972                                                              module: &Module,
 973                                                              name: Name,
 974                                                              span: Span) {
 975         if module.external_module_children.borrow().contains_key(&name) {
 976                 span_err!(self.session, span, E0260,
 977                           "the name `{}` conflicts with an external \
 978                            crate that has been imported into this \
 979                            module",
 980                            name);
 981         }
 982     }
 983
 984     /// Resolves the given module path from the given root `module_`.
 985     fn resolve_module_path_from_root(&mut self,
 986                                      module_: Rc<Module>,
 987                                      module_path: &[Name],
 988                                      index: usize,
 989                                      span: Span,
 990                                      name_search_type: NameSearchType,
 991                                      lp: LastPrivate)
 992                                 -> ResolveResult<(Rc<Module>, LastPrivate)> {
 993         fn search_parent_externals(needle: Name, module: &Rc<Module>)
 994                                 -> Option<Rc<Module>> {
 995             match module.external_module_children.borrow().get(&needle) {
 996                 Some(_) => Some(module.clone()),
 997                 None => match module.parent_link {
 998                     ModuleParentLink(ref parent, _) => {
 999                         search_parent_externals(needle, &parent.upgrade().unwrap())
1000                     }
1001                    _ => None
1002                 }
1003             }
1004         }
1005
1006         let mut search_module = module_;
1007         let mut index = index;
1008         let module_path_len = module_path.len();
1009         let mut closest_private = lp;
1010
1011         // Resolve the module part of the path. This does not involve looking
1012         // upward though scope chains; we simply resolve names directly in
1013         // modules as we go.
1014         while index < module_path_len {
1015             let name = module_path[index];
1016             match self.resolve_name_in_module(search_module.clone(),
1017                                               name,
1018                                               TypeNS,
1019                                               name_search_type,
1020                                               false) {
1021                 Failed(None) => {
1022                     let segment_name = token::get_name(name);
1023                     let module_name = module_to_string(&*search_module);
1024                     let mut span = span;
1025                     let msg = if "???" == &module_name[..] {
1026                         span.hi = span.lo + Pos::from_usize(segment_name.len());
1027
1028                         match search_parent_externals(name,
1029                                                      &self.current_module) {
1030                             Some(module) => {
1031                                 let path_str = names_to_string(module_path);
1032                                 let target_mod_str = module_to_string(&*module);
1033                                 let current_mod_str =
1034                                     module_to_string(&*self.current_module);
1035
1036                                 let prefix = if target_mod_str == current_mod_str {
1037                                     "self::".to_string()
1038                                 } else {
1039                                     format!("{}::", target_mod_str)
1040                                 };
1041
1042                                 format!("Did you mean `{}{}`?", prefix, path_str)
1043                             },
1044                             None => format!("Maybe a missing `extern crate {}`?",
1045                                             segment_name),
1046                         }
1047                     } else {
1048                         format!("Could not find `{}` in `{}`",
1049                                 segment_name,
1050                                 module_name)
1051                     };
1052
1053                     return Failed(Some((span, msg)));
1054                 }
1055                 Failed(err) => return Failed(err),
1056                 Indeterminate => {
1057                     debug!("(resolving module path for import) module \
1058                             resolution is indeterminate: {}",
1059                             name);
1060                     return Indeterminate;
1061                 }
1062                 Success((target, used_proxy)) => {
1063                     // Check to see whether there are type bindings, and, if
1064                     // so, whether there is a module within.
1065                     match *target.bindings.type_def.borrow() {
1066                         Some(ref type_def) => {
1067                             match type_def.module_def {
1068                                 None => {
1069                                     let msg = format!("Not a module `{}`",
1070                                                         name);
1071
1072                                     return Failed(Some((span, msg)));
1073                                 }
1074                                 Some(ref module_def) => {
1075                                     search_module = module_def.clone();
1076
1077                                     // track extern crates for unused_extern_crate lint
1078                                     if let Some(did) = module_def.def_id.get() {
1079                                         self.used_crates.insert(did.krate);
1080                                     }
1081
1082                                     // Keep track of the closest
1083                                     // private module used when
1084                                     // resolving this import chain.
1085                                     if !used_proxy && !search_module.is_public {
1086                                         if let Some(did) = search_module.def_id.get() {
1087                                             closest_private = LastMod(DependsOn(did));
1088                                         }
1089                                     }
1090                                 }
1091                             }
1092                         }
1093                         None => {
1094                             // There are no type bindings at all.
1095                             let msg = format!("Not a module `{}`",
1096                                               name);
1097                             return Failed(Some((span, msg)));
1098                         }
1099                     }
1100                 }
1101             }
1102
1103             index += 1;
1104         }
1105
1106         return Success((search_module, closest_private));
1107     }
1108
1109     /// Attempts to resolve the module part of an import directive or path
1110     /// rooted at the given module.
1111     ///
1112     /// On success, returns the resolved module, and the closest *private*
1113     /// module found to the destination when resolving this path.
1114     fn resolve_module_path(&mut self,
1115                            module_: Rc<Module>,
1116                            module_path: &[Name],
1117                            use_lexical_scope: UseLexicalScopeFlag,
1118                            span: Span,
1119                            name_search_type: NameSearchType)
1120                            -> ResolveResult<(Rc<Module>, LastPrivate)> {
1121         let module_path_len = module_path.len();
1122         assert!(module_path_len > 0);
1123
1124         debug!("(resolving module path for import) processing `{}` rooted at `{}`",
1125                names_to_string(module_path),
1126                module_to_string(&*module_));
1127
1128         // Resolve the module prefix, if any.
1129         let module_prefix_result = self.resolve_module_prefix(module_.clone(),
1130                                                               module_path);
1131
1132         let search_module;
1133         let start_index;
1134         let last_private;
1135         match module_prefix_result {
1136             Failed(None) => {
1137                 let mpath = names_to_string(module_path);
1138                 let mpath = &mpath[..];
1139                 match mpath.rfind(':') {
1140                     Some(idx) => {
1141                         let msg = format!("Could not find `{}` in `{}`",
1142                                             // idx +- 1 to account for the
1143                                             // colons on either side
1144                                             &mpath[idx + 1..],
1145                                             &mpath[..idx - 1]);
1146                         return Failed(Some((span, msg)));
1147                     },
1148                     None => {
1149                         return Failed(None)
1150                     }
1151                 }
1152             }
1153             Failed(err) => return Failed(err),
1154             Indeterminate => {
1155                 debug!("(resolving module path for import) indeterminate; \
1156                         bailing");
1157                 return Indeterminate;
1158             }
1159             Success(NoPrefixFound) => {
1160                 // There was no prefix, so we're considering the first element
1161                 // of the path. How we handle this depends on whether we were
1162                 // instructed to use lexical scope or not.
1163                 match use_lexical_scope {
1164                     DontUseLexicalScope => {
1165                         // This is a crate-relative path. We will start the
1166                         // resolution process at index zero.
1167                         search_module = self.graph_root.get_module();
1168                         start_index = 0;
1169                         last_private = LastMod(AllPublic);
1170                     }
1171                     UseLexicalScope => {
1172                         // This is not a crate-relative path. We resolve the
1173                         // first component of the path in the current lexical
1174                         // scope and then proceed to resolve below that.
1175                         match self.resolve_module_in_lexical_scope(module_,
1176                                                                    module_path[0]) {
1177                             Failed(err) => return Failed(err),
1178                             Indeterminate => {
1179                                 debug!("(resolving module path for import) \
1180                                         indeterminate; bailing");
1181                                 return Indeterminate;
1182                             }
1183                             Success(containing_module) => {
1184                                 search_module = containing_module;
1185                                 start_index = 1;
1186                                 last_private = LastMod(AllPublic);
1187                             }
1188                         }
1189                     }
1190                 }
1191             }
1192             Success(PrefixFound(ref containing_module, index)) => {
1193                 search_module = containing_module.clone();
1194                 start_index = index;
1195                 last_private = LastMod(DependsOn(containing_module.def_id
1196                                                                   .get()
1197                                                                   .unwrap()));
1198             }
1199         }
1200
1201         self.resolve_module_path_from_root(search_module,
1202                                            module_path,
1203                                            start_index,
1204                                            span,
1205                                            name_search_type,
1206                                            last_private)
1207     }
1208
1209     /// Invariant: This must only be called during main resolution, not during
1210     /// import resolution.
1211     fn resolve_item_in_lexical_scope(&mut self,
1212                                      module_: Rc<Module>,
1213                                      name: Name,
1214                                      namespace: Namespace)
1215                                     -> ResolveResult<(Target, bool)> {
1216         debug!("(resolving item in lexical scope) resolving `{}` in \
1217                 namespace {:?} in `{}`",
1218                name,
1219                namespace,
1220                module_to_string(&*module_));
1221
1222         // The current module node is handled specially. First, check for
1223         // its immediate children.
1224         build_reduced_graph::populate_module_if_necessary(self, &module_);
1225
1226         match module_.children.borrow().get(&name) {
1227             Some(name_bindings)
1228                     if name_bindings.defined_in_namespace(namespace) => {
1229                 debug!("top name bindings succeeded");
1230                 return Success((Target::new(module_.clone(),
1231                                             name_bindings.clone(),
1232                                             Shadowable::Never),
1233                                false));
1234             }
1235             Some(_) | None => { /* Not found; continue. */ }
1236         }
1237
1238         // Now check for its import directives. We don't have to have resolved
1239         // all its imports in the usual way; this is because chains of
1240         // adjacent import statements are processed as though they mutated the
1241         // current scope.
1242         if let Some(import_resolution) = module_.import_resolutions.borrow().get(&name) {
1243             match (*import_resolution).target_for_namespace(namespace) {
1244                 None => {
1245                     // Not found; continue.
1246                     debug!("(resolving item in lexical scope) found \
1247                             import resolution, but not in namespace {:?}",
1248                            namespace);
1249                 }
1250                 Some(target) => {
1251                     debug!("(resolving item in lexical scope) using \
1252                             import resolution");
1253                     // track used imports and extern crates as well
1254                     let id = import_resolution.id(namespace);
1255                     self.used_imports.insert((id, namespace));
1256                     self.record_import_use(id, name);
1257                     if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
1258                          self.used_crates.insert(kid);
1259                     }
1260                     return Success((target, false));
1261                 }
1262             }
1263         }
1264
1265         // Search for external modules.
1266         if namespace == TypeNS {
1267             // FIXME (21114): In principle unclear `child` *has* to be lifted.
1268             let child = module_.external_module_children.borrow().get(&name).cloned();
1269             if let Some(module) = child {
1270                 let name_bindings =
1271                     Rc::new(Resolver::create_name_bindings_from_module(module));
1272                 debug!("lower name bindings succeeded");
1273                 return Success((Target::new(module_,
1274                                             name_bindings,
1275                                             Shadowable::Never),
1276                                 false));
1277             }
1278         }
1279
1280         // Finally, proceed up the scope chain looking for parent modules.
1281         let mut search_module = module_;
1282         loop {
1283             // Go to the next parent.
1284             match search_module.parent_link.clone() {
1285                 NoParentLink => {
1286                     // No more parents. This module was unresolved.
1287                     debug!("(resolving item in lexical scope) unresolved \
1288                             module");
1289                     return Failed(None);
1290                 }
1291                 ModuleParentLink(parent_module_node, _) => {
1292                     match search_module.kind.get() {
1293                         NormalModuleKind => {
1294                             // We stop the search here.
1295                             debug!("(resolving item in lexical \
1296                                     scope) unresolved module: not \
1297                                     searching through module \
1298                                     parents");
1299                             return Failed(None);
1300                         }
1301                         TraitModuleKind |
1302                         EnumModuleKind |
1303                         TypeModuleKind |
1304                         AnonymousModuleKind => {
1305                             search_module = parent_module_node.upgrade().unwrap();
1306                         }
1307                     }
1308                 }
1309                 BlockParentLink(ref parent_module_node, _) => {
1310                     search_module = parent_module_node.upgrade().unwrap();
1311                 }
1312             }
1313
1314             // Resolve the name in the parent module.
1315             match self.resolve_name_in_module(search_module.clone(),
1316                                               name,
1317                                               namespace,
1318                                               PathSearch,
1319                                               true) {
1320                 Failed(Some((span, msg))) => {
1321                     /*self.resolve_error(span,
1322                                        &format!("failed to resolve. {}",
1323                                                 msg));*/
1324                     resolve_err!(self, span, E0253, "failed to resolve. {}", msg);
1325                 },
1326                 Failed(None) => (), // Continue up the search chain.
1327                 Indeterminate => {
1328                     // We couldn't see through the higher scope because of an
1329                     // unresolved import higher up. Bail.
1330
1331                     debug!("(resolving item in lexical scope) indeterminate \
1332                             higher scope; bailing");
1333                     return Indeterminate;
1334                 }
1335                 Success((target, used_reexport)) => {
1336                     // We found the module.
1337                     debug!("(resolving item in lexical scope) found name \
1338                             in module, done");
1339                     return Success((target, used_reexport));
1340                 }
1341             }
1342         }
1343     }
1344
1345     /// Resolves a module name in the current lexical scope.
1346     fn resolve_module_in_lexical_scope(&mut self,
1347                                        module_: Rc<Module>,
1348                                        name: Name)
1349                                 -> ResolveResult<Rc<Module>> {
1350         // If this module is an anonymous module, resolve the item in the
1351         // lexical scope. Otherwise, resolve the item from the crate root.
1352         let resolve_result = self.resolve_item_in_lexical_scope(module_, name, TypeNS);
1353         match resolve_result {
1354             Success((target, _)) => {
1355                 let bindings = &*target.bindings;
1356                 match *bindings.type_def.borrow() {
1357                     Some(ref type_def) => {
1358                         match type_def.module_def {
1359                             None => {
1360                                 debug!("!!! (resolving module in lexical \
1361                                         scope) module wasn't actually a \
1362                                         module!");
1363                                 return Failed(None);
1364                             }
1365                             Some(ref module_def) => {
1366                                 return Success(module_def.clone());
1367                             }
1368                         }
1369                     }
1370                     None => {
1371                         debug!("!!! (resolving module in lexical scope) module
1372                                 wasn't actually a module!");
1373                         return Failed(None);
1374                     }
1375                 }
1376             }
1377             Indeterminate => {
1378                 debug!("(resolving module in lexical scope) indeterminate; \
1379                         bailing");
1380                 return Indeterminate;
1381             }
1382             Failed(err) => {
1383                 debug!("(resolving module in lexical scope) failed to resolve");
1384                 return Failed(err);
1385             }
1386         }
1387     }
1388
1389     /// Returns the nearest normal module parent of the given module.
1390     fn get_nearest_normal_module_parent(&mut self, module_: Rc<Module>)
1391                                             -> Option<Rc<Module>> {
1392         let mut module_ = module_;
1393         loop {
1394             match module_.parent_link.clone() {
1395                 NoParentLink => return None,
1396                 ModuleParentLink(new_module, _) |
1397                 BlockParentLink(new_module, _) => {
1398                     let new_module = new_module.upgrade().unwrap();
1399                     match new_module.kind.get() {
1400                         NormalModuleKind => return Some(new_module),
1401                         TraitModuleKind |
1402                         EnumModuleKind |
1403                         TypeModuleKind |
1404                         AnonymousModuleKind => module_ = new_module,
1405                     }
1406                 }
1407             }
1408         }
1409     }
1410
1411     /// Returns the nearest normal module parent of the given module, or the
1412     /// module itself if it is a normal module.
1413     fn get_nearest_normal_module_parent_or_self(&mut self, module_: Rc<Module>)
1414                                                 -> Rc<Module> {
1415         match module_.kind.get() {
1416             NormalModuleKind => return module_,
1417             TraitModuleKind |
1418             EnumModuleKind |
1419             TypeModuleKind |
1420             AnonymousModuleKind => {
1421                 match self.get_nearest_normal_module_parent(module_.clone()) {
1422                     None => module_,
1423                     Some(new_module) => new_module
1424                 }
1425             }
1426         }
1427     }
1428
1429     /// Resolves a "module prefix". A module prefix is one or both of (a) `self::`;
1430     /// (b) some chain of `super::`.
1431     /// grammar: (SELF MOD_SEP ) ? (SUPER MOD_SEP) *
1432     fn resolve_module_prefix(&mut self,
1433                              module_: Rc<Module>,
1434                              module_path: &[Name])
1435                                  -> ResolveResult<ModulePrefixResult> {
1436         // Start at the current module if we see `self` or `super`, or at the
1437         // top of the crate otherwise.
1438         let mut containing_module;
1439         let mut i;
1440         let first_module_path_string = token::get_name(module_path[0]);
1441         if "self" == &first_module_path_string[..] {
1442             containing_module =
1443                 self.get_nearest_normal_module_parent_or_self(module_);
1444             i = 1;
1445         } else if "super" == &first_module_path_string[..] {
1446             containing_module =
1447                 self.get_nearest_normal_module_parent_or_self(module_);
1448             i = 0;  // We'll handle `super` below.
1449         } else {
1450             return Success(NoPrefixFound);
1451         }
1452
1453         // Now loop through all the `super`s we find.
1454         while i < module_path.len() {
1455             let string = token::get_name(module_path[i]);
1456             if "super" != &string[..] {
1457                 break
1458             }
1459             debug!("(resolving module prefix) resolving `super` at {}",
1460                    module_to_string(&*containing_module));
1461             match self.get_nearest_normal_module_parent(containing_module) {
1462                 None => return Failed(None),
1463                 Some(new_module) => {
1464                     containing_module = new_module;
1465                     i += 1;
1466                 }
1467             }
1468         }
1469
1470         debug!("(resolving module prefix) finished resolving prefix at {}",
1471                module_to_string(&*containing_module));
1472
1473         return Success(PrefixFound(containing_module, i));
1474     }
1475
1476     /// Attempts to resolve the supplied name in the given module for the
1477     /// given namespace. If successful, returns the target corresponding to
1478     /// the name.
1479     ///
1480     /// The boolean returned on success is an indicator of whether this lookup
1481     /// passed through a public re-export proxy.
1482     fn resolve_name_in_module(&mut self,
1483                               module_: Rc<Module>,
1484                               name: Name,
1485                               namespace: Namespace,
1486                               name_search_type: NameSearchType,
1487                               allow_private_imports: bool)
1488                               -> ResolveResult<(Target, bool)> {
1489         debug!("(resolving name in module) resolving `{}` in `{}`",
1490                name,
1491                module_to_string(&*module_));
1492
1493         // First, check the direct children of the module.
1494         build_reduced_graph::populate_module_if_necessary(self, &module_);
1495
1496         match module_.children.borrow().get(&name) {
1497             Some(name_bindings)
1498                     if name_bindings.defined_in_namespace(namespace) => {
1499                 debug!("(resolving name in module) found node as child");
1500                 return Success((Target::new(module_.clone(),
1501                                             name_bindings.clone(),
1502                                             Shadowable::Never),
1503                                false));
1504             }
1505             Some(_) | None => {
1506                 // Continue.
1507             }
1508         }
1509
1510         // Next, check the module's imports if necessary.
1511
1512         // If this is a search of all imports, we should be done with glob
1513         // resolution at this point.
1514         if name_search_type == PathSearch {
1515             assert_eq!(module_.glob_count.get(), 0);
1516         }
1517
1518         // Check the list of resolved imports.
1519         match module_.import_resolutions.borrow().get(&name) {
1520             Some(import_resolution) if allow_private_imports ||
1521                                        import_resolution.is_public => {
1522
1523                 if import_resolution.is_public &&
1524                         import_resolution.outstanding_references != 0 {
1525                     debug!("(resolving name in module) import \
1526                            unresolved; bailing out");
1527                     return Indeterminate;
1528                 }
1529                 match import_resolution.target_for_namespace(namespace) {
1530                     None => {
1531                         debug!("(resolving name in module) name found, \
1532                                 but not in namespace {:?}",
1533                                namespace);
1534                     }
1535                     Some(target) => {
1536                         debug!("(resolving name in module) resolved to \
1537                                 import");
1538                         // track used imports and extern crates as well
1539                         let id = import_resolution.id(namespace);
1540                         self.used_imports.insert((id, namespace));
1541                         self.record_import_use(id, name);
1542                         if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
1543                             self.used_crates.insert(kid);
1544                         }
1545                         return Success((target, true));
1546                     }
1547                 }
1548             }
1549             Some(..) | None => {} // Continue.
1550         }
1551
1552         // Finally, search through external children.
1553         if namespace == TypeNS {
1554             // FIXME (21114): In principle unclear `child` *has* to be lifted.
1555             let child = module_.external_module_children.borrow().get(&name).cloned();
1556             if let Some(module) = child {
1557                 let name_bindings =
1558                     Rc::new(Resolver::create_name_bindings_from_module(module));
1559                 return Success((Target::new(module_,
1560                                             name_bindings,
1561                                             Shadowable::Never),
1562                                 false));
1563             }
1564         }
1565
1566         // We're out of luck.
1567         debug!("(resolving name in module) failed to resolve `{}`",
1568                name);
1569         return Failed(None);
1570     }
1571
1572     fn report_unresolved_imports(&mut self, module_: Rc<Module>) {
1573         let index = module_.resolved_import_count.get();
1574         let imports = module_.imports.borrow();
1575         let import_count = imports.len();
1576         if index != import_count {
1577             let sn = self.session
1578                          .codemap()
1579                          .span_to_snippet((*imports)[index].span)
1580                          .unwrap();
1581             if sn.contains("::") {
1582                 /*self.resolve_error((*imports)[index].span,
1583                                    "unresolved import");*/
1584                 resolve_err!(self, (*imports)[index].span, E0253,
1585                              "{}", "unresolved import");
1586             } else {
1587                 /*let err = format!("unresolved import (maybe you meant `{}::*`?)",
1588                                   sn);
1589                 self.resolve_error((*imports)[index].span, &err[..]);*/
1590                 resolve_err!(self, (*imports)[index].span, E0253,
1591                              "unresolved import (maybe you meant `{}::*`?)", sn);
1592             }
1593         }
1594
1595         // Descend into children and anonymous children.
1596         build_reduced_graph::populate_module_if_necessary(self, &module_);
1597
1598         for (_, child_node) in module_.children.borrow().iter() {
1599             match child_node.get_module_if_available() {
1600                 None => {
1601                     // Continue.
1602                 }
1603                 Some(child_module) => {
1604                     self.report_unresolved_imports(child_module);
1605                 }
1606             }
1607         }
1608
1609         for (_, module_) in module_.anonymous_children.borrow().iter() {
1610             self.report_unresolved_imports(module_.clone());
1611         }
1612     }
1613
1614     // AST resolution
1615     //
1616     // We maintain a list of value ribs and type ribs.
1617     //
1618     // Simultaneously, we keep track of the current position in the module
1619     // graph in the `current_module` pointer. When we go to resolve a name in
1620     // the value or type namespaces, we first look through all the ribs and
1621     // then query the module graph. When we resolve a name in the module
1622     // namespace, we can skip all the ribs (since nested modules are not
1623     // allowed within blocks in Rust) and jump straight to the current module
1624     // graph node.
1625     //
1626     // Named implementations are handled separately. When we find a method
1627     // call, we consult the module node to find all of the implementations in
1628     // scope. This information is lazily cached in the module node. We then
1629     // generate a fake "implementation scope" containing all the
1630     // implementations thus found, for compatibility with old resolve pass.
1631
1632     fn with_scope<F>(&mut self, name: Option<Name>, f: F) where
1633         F: FnOnce(&mut Resolver),
1634     {
1635         let orig_module = self.current_module.clone();
1636
1637         // Move down in the graph.
1638         match name {
1639             None => {
1640                 // Nothing to do.
1641             }
1642             Some(name) => {
1643                 build_reduced_graph::populate_module_if_necessary(self, &orig_module);
1644
1645                 match orig_module.children.borrow().get(&name) {
1646                     None => {
1647                         debug!("!!! (with scope) didn't find `{}` in `{}`",
1648                                name,
1649                                module_to_string(&*orig_module));
1650                     }
1651                     Some(name_bindings) => {
1652                         match (*name_bindings).get_module_if_available() {
1653                             None => {
1654                                 debug!("!!! (with scope) didn't find module \
1655                                         for `{}` in `{}`",
1656                                        name,
1657                                        module_to_string(&*orig_module));
1658                             }
1659                             Some(module_) => {
1660                                 self.current_module = module_;
1661                             }
1662                         }
1663                     }
1664                 }
1665             }
1666         }
1667
1668         f(self);
1669
1670         self.current_module = orig_module;
1671     }
1672
1673     /// Wraps the given definition in the appropriate number of `DefUpvar`
1674     /// wrappers.
1675     fn upvarify(&self,
1676                 ribs: &[Rib],
1677                 def_like: DefLike,
1678                 span: Span)
1679                 -> Option<DefLike> {
1680         let mut def = match def_like {
1681             DlDef(def) => def,
1682             _ => return Some(def_like)
1683         };
1684         match def {
1685             DefUpvar(..) => {
1686                 self.session.span_bug(span,
1687                     &format!("unexpected {:?} in bindings", def))
1688             }
1689             DefLocal(node_id) => {
1690                 for rib in ribs {
1691                     match rib.kind {
1692                         NormalRibKind => {
1693                             // Nothing to do. Continue.
1694                         }
1695                         ClosureRibKind(function_id) => {
1696                             let prev_def = def;
1697                             def = DefUpvar(node_id, function_id);
1698
1699                             let mut seen = self.freevars_seen.borrow_mut();
1700                             let seen = match seen.entry(function_id) {
1701                                 Occupied(v) => v.into_mut(),
1702                                 Vacant(v) => v.insert(NodeSet()),
1703                             };
1704                             if seen.contains(&node_id) {
1705                                 continue;
1706                             }
1707                             match self.freevars.borrow_mut().entry(function_id) {
1708                                 Occupied(v) => v.into_mut(),
1709                                 Vacant(v) => v.insert(vec![]),
1710                             }.push(Freevar { def: prev_def, span: span });
1711                             seen.insert(node_id);
1712                         }
1713                         ItemRibKind | MethodRibKind => {
1714                             // This was an attempt to access an upvar inside a
1715                             // named function item. This is not allowed, so we
1716                             // report an error.
1717
1718                             /*self.resolve_error(span,
1719                                 "can't capture dynamic environment in a fn item; \
1720                                  use the || { ... } closure form instead");*/
1721                             resolve_err!(self, span, E0253, "{}",
1722                                          "can't capture dynamic environment in a fn item; \
1723                                           use the || { ... } closure form instead");
1724                             return None;
1725                         }
1726                         ConstantItemRibKind => {
1727                             // Still doesn't deal with upvars
1728                             /*self.resolve_error(span,
1729                                                "attempt to use a non-constant \
1730                                                 value in a constant");*/
1731                             resolve_err!(self, span, E0253, "{}",
1732                                          "attempt to use a non-constant \
1733                                           value in a constant");
1734                             return None;
1735                         }
1736                     }
1737                 }
1738             }
1739             DefTyParam(..) | DefSelfTy(..) => {
1740                 for rib in ribs {
1741                     match rib.kind {
1742                         NormalRibKind | MethodRibKind | ClosureRibKind(..) => {
1743                             // Nothing to do. Continue.
1744                         }
1745                         ItemRibKind => {
1746                             // This was an attempt to use a type parameter outside
1747                             // its scope.
1748
1749                             /*self.resolve_error(span,
1750                                                "can't use type parameters from \
1751                                                 outer function; try using a local \
1752                                                 type parameter instead");*/
1753                             resolve_err!(self, span, E0253, "{}",
1754                                          "can't use type parameters from \
1755                                           outer function; try using a local \
1756                                           type parameter instead");
1757                             return None;
1758                         }
1759                         ConstantItemRibKind => {
1760                             // see #9186
1761                             /*self.resolve_error(span,
1762                                                "cannot use an outer type \
1763                                                 parameter in this context");*/
1764                             resolve_err!(self, span, E0253, "{}",
1765                                          "cannot use an outer type \
1766                                           parameter in this context");
1767                             return None;
1768                         }
1769                     }
1770                 }
1771             }
1772             _ => {}
1773         }
1774         Some(DlDef(def))
1775     }
1776
1777     /// Searches the current set of local scopes and
1778     /// applies translations for closures.
1779     fn search_ribs(&self,
1780                    ribs: &[Rib],
1781                    name: Name,
1782                    span: Span)
1783                    -> Option<DefLike> {
1784         // FIXME #4950: Try caching?
1785
1786         for (i, rib) in ribs.iter().enumerate().rev() {
1787             if let Some(def_like) = rib.bindings.get(&name).cloned() {
1788                 return self.upvarify(&ribs[i + 1..], def_like, span);
1789             }
1790         }
1791
1792         None
1793     }
1794
1795     /// Searches the current set of local scopes for labels.
1796     /// Stops after meeting a closure.
1797     fn search_label(&self, name: Name) -> Option<DefLike> {
1798         for rib in self.label_ribs.iter().rev() {
1799             match rib.kind {
1800                 NormalRibKind => {
1801                     // Continue
1802                 }
1803                 _ => {
1804                     // Do not resolve labels across function boundary
1805                     return None
1806                 }
1807             }
1808             let result = rib.bindings.get(&name).cloned();
1809             if result.is_some() {
1810                 return result
1811             }
1812         }
1813         None
1814     }
1815
1816     fn resolve_crate(&mut self, krate: &ast::Crate) {
1817         debug!("(resolving crate) starting");
1818
1819         visit::walk_crate(self, krate);
1820     }
1821
1822     fn check_if_primitive_type_name(&self, name: Name, span: Span) {
1823         if let Some(_) = self.primitive_type_table.primitive_types.get(&name) {
1824             span_err!(self.session, span, E0317,
1825                 "user-defined types or type parameters cannot shadow the primitive types");
1826         }
1827     }
1828
1829     fn resolve_item(&mut self, item: &Item) {
1830         let name = item.ident.name;
1831
1832         debug!("(resolving item) resolving {}",
1833                name);
1834
1835         match item.node {
1836             ItemEnum(_, ref generics) |
1837             ItemTy(_, ref generics) |
1838             ItemStruct(_, ref generics) => {
1839                 self.check_if_primitive_type_name(name, item.span);
1840
1841                 self.with_type_parameter_rib(HasTypeParameters(generics,
1842                                                                TypeSpace,
1843                                                                ItemRibKind),
1844                                              |this| visit::walk_item(this, item));
1845             }
1846             ItemFn(_, _, _, _, ref generics, _) => {
1847                 self.with_type_parameter_rib(HasTypeParameters(generics,
1848                                                                FnSpace,
1849                                                                ItemRibKind),
1850                                              |this| visit::walk_item(this, item));
1851             }
1852
1853             ItemDefaultImpl(_, ref trait_ref) => {
1854                 self.with_optional_trait_ref(Some(trait_ref), |_, _| {});
1855             }
1856             ItemImpl(_,
1857                      _,
1858                      ref generics,
1859                      ref opt_trait_ref,
1860                      ref self_type,
1861                      ref impl_items) => {
1862                 self.resolve_implementation(generics,
1863                                             opt_trait_ref,
1864                                             &**self_type,
1865                                             item.id,
1866                                             &impl_items[..]);
1867             }
1868
1869             ItemTrait(_, ref generics, ref bounds, ref trait_items) => {
1870                 self.check_if_primitive_type_name(name, item.span);
1871
1872                 // Create a new rib for the trait-wide type parameters.
1873                 self.with_type_parameter_rib(HasTypeParameters(generics,
1874                                                                TypeSpace,
1875                                                                ItemRibKind),
1876                                              |this| {
1877                     this.with_self_rib(DefSelfTy(Some(local_def(item.id)), None), |this| {
1878                         this.visit_generics(generics);
1879                         visit::walk_ty_param_bounds_helper(this, bounds);
1880
1881                         for trait_item in trait_items {
1882                             // Create a new rib for the trait_item-specific type
1883                             // parameters.
1884                             //
1885                             // FIXME #4951: Do we need a node ID here?
1886
1887                             match trait_item.node {
1888                                 ast::ConstTraitItem(_, ref default) => {
1889                                     // Only impose the restrictions of
1890                                     // ConstRibKind if there's an actual constant
1891                                     // expression in a provided default.
1892                                     if default.is_some() {
1893                                         this.with_constant_rib(|this| {
1894                                             visit::walk_trait_item(this, trait_item)
1895                                         });
1896                                     } else {
1897                                         visit::walk_trait_item(this, trait_item)
1898                                     }
1899                                 }
1900                                 ast::MethodTraitItem(ref sig, _) => {
1901                                     let type_parameters =
1902                                         HasTypeParameters(&sig.generics,
1903                                                           FnSpace,
1904                                                           MethodRibKind);
1905                                     this.with_type_parameter_rib(type_parameters, |this| {
1906                                         visit::walk_trait_item(this, trait_item)
1907                                     });
1908                                 }
1909                                 ast::TypeTraitItem(..) => {
1910                                     this.check_if_primitive_type_name(trait_item.ident.name,
1911                                                                       trait_item.span);
1912                                     this.with_type_parameter_rib(NoTypeParameters, |this| {
1913                                         visit::walk_trait_item(this, trait_item)
1914                                     });
1915                                 }
1916                             };
1917                         }
1918                     });
1919                 });
1920             }
1921
1922             ItemMod(_) | ItemForeignMod(_) => {
1923                 self.with_scope(Some(name), |this| {
1924                     visit::walk_item(this, item);
1925                 });
1926             }
1927
1928             ItemConst(..) | ItemStatic(..) => {
1929                 self.with_constant_rib(|this| {
1930                     visit::walk_item(this, item);
1931                 });
1932             }
1933
1934             ItemUse(ref view_path) => {
1935                 // check for imports shadowing primitive types
1936                 if let ast::ViewPathSimple(ident, _) = view_path.node {
1937                     match self.def_map.borrow().get(&item.id).map(|d| d.full_def()) {
1938                         Some(DefTy(..)) | Some(DefStruct(..)) | Some(DefTrait(..)) | None => {
1939                             self.check_if_primitive_type_name(ident.name, item.span);
1940                         }
1941                         _ => {}
1942                     }
1943                 }
1944             }
1945
1946             ItemExternCrate(_) | ItemMac(..) => {
1947                 // do nothing, these are just around to be encoded
1948             }
1949         }
1950     }
1951
1952     fn with_type_parameter_rib<F>(&mut self, type_parameters: TypeParameters, f: F) where
1953         F: FnOnce(&mut Resolver),
1954     {
1955         match type_parameters {
1956             HasTypeParameters(generics, space, rib_kind) => {
1957                 let mut function_type_rib = Rib::new(rib_kind);
1958                 let mut seen_bindings = HashSet::new();
1959                 for (index, type_parameter) in generics.ty_params.iter().enumerate() {
1960                     let name = type_parameter.ident.name;
1961                     debug!("with_type_parameter_rib: {}", type_parameter.id);
1962
1963                     if seen_bindings.contains(&name) {
1964                         /*self.resolve_error(type_parameter.span,
1965                                            &format!("the name `{}` is already \
1966                                                      used for a type \
1967                                                      parameter in this type \
1968                                                      parameter list",
1969                                                     name))*/
1970                         resolve_err!(self, type_parameter.span, E0253,
1971                                      "the name `{}` is already \
1972                                       used for a type \
1973                                       parameter in this type \
1974                                       parameter list",
1975                                      name)
1976                     }
1977                     seen_bindings.insert(name);
1978
1979                     // plain insert (no renaming)
1980                     function_type_rib.bindings.insert(name,
1981                         DlDef(DefTyParam(space,
1982                                          index as u32,
1983                                          local_def(type_parameter.id),
1984                                          name)));
1985                 }
1986                 self.type_ribs.push(function_type_rib);
1987             }
1988
1989             NoTypeParameters => {
1990                 // Nothing to do.
1991             }
1992         }
1993
1994         f(self);
1995
1996         match type_parameters {
1997             HasTypeParameters(..) => { self.type_ribs.pop(); }
1998             NoTypeParameters => { }
1999         }
2000     }
2001
2002     fn with_label_rib<F>(&mut self, f: F) where
2003         F: FnOnce(&mut Resolver),
2004     {
2005         self.label_ribs.push(Rib::new(NormalRibKind));
2006         f(self);
2007         self.label_ribs.pop();
2008     }
2009
2010     fn with_constant_rib<F>(&mut self, f: F) where
2011         F: FnOnce(&mut Resolver),
2012     {
2013         self.value_ribs.push(Rib::new(ConstantItemRibKind));
2014         self.type_ribs.push(Rib::new(ConstantItemRibKind));
2015         f(self);
2016         self.type_ribs.pop();
2017         self.value_ribs.pop();
2018     }
2019
2020     fn resolve_function(&mut self,
2021                         rib_kind: RibKind,
2022                         declaration: &FnDecl,
2023                         block: &Block) {
2024         // Create a value rib for the function.
2025         self.value_ribs.push(Rib::new(rib_kind));
2026
2027         // Create a label rib for the function.
2028         self.label_ribs.push(Rib::new(rib_kind));
2029
2030         // Add each argument to the rib.
2031         let mut bindings_list = HashMap::new();
2032         for argument in &declaration.inputs {
2033             self.resolve_pattern(&*argument.pat,
2034                                  ArgumentIrrefutableMode,
2035                                  &mut bindings_list);
2036
2037             self.visit_ty(&*argument.ty);
2038
2039             debug!("(resolving function) recorded argument");
2040         }
2041         visit::walk_fn_ret_ty(self, &declaration.output);
2042
2043         // Resolve the function body.
2044         self.visit_block(&*block);
2045
2046         debug!("(resolving function) leaving function");
2047
2048         self.label_ribs.pop();
2049         self.value_ribs.pop();
2050     }
2051
2052     fn resolve_trait_reference(&mut self,
2053                                id: NodeId,
2054                                trait_path: &Path,
2055                                path_depth: usize)
2056                                -> Result<PathResolution, ()> {
2057         if let Some(path_res) = self.resolve_path(id, trait_path, path_depth, TypeNS, true) {
2058             if let DefTrait(_) = path_res.base_def {
2059                 debug!("(resolving trait) found trait def: {:?}", path_res);
2060                 Ok(path_res)
2061             } else {
2062                 /*self.resolve_error(trait_path.span,
2063                     &format!("`{}` is not a trait",
2064                              path_names_to_string(trait_path, path_depth)));*/
2065                 resolve_err!(self, trait_path.span, E0253,
2066                              "`{}` is not a trait",
2067                              path_names_to_string(trait_path, path_depth));
2068
2069                 // If it's a typedef, give a note
2070                 if let DefTy(..) = path_res.base_def {
2071                     self.session.span_note(trait_path.span,
2072                                            "`type` aliases cannot be used for traits");
2073                 }
2074                 Err(())
2075             }
2076         } else {
2077             /*let msg = format!("use of undeclared trait name `{}`",
2078                               path_names_to_string(trait_path, path_depth));
2079             self.resolve_error(trait_path.span, &msg);*/
2080             resolve_err!(self, trait_path.span, E0253,
2081                          "use of undeclared trait name `{}`",
2082                          path_names_to_string(trait_path, path_depth));
2083             Err(())
2084         }
2085     }
2086
2087     fn resolve_generics(&mut self, generics: &Generics) {
2088         for type_parameter in generics.ty_params.iter() {
2089             self.check_if_primitive_type_name(type_parameter.ident.name, type_parameter.span);
2090         }
2091         for predicate in &generics.where_clause.predicates {
2092             match predicate {
2093                 &ast::WherePredicate::BoundPredicate(_) |
2094                 &ast::WherePredicate::RegionPredicate(_) => {}
2095                 &ast::WherePredicate::EqPredicate(ref eq_pred) => {
2096                     let path_res = self.resolve_path(eq_pred.id, &eq_pred.path, 0, TypeNS, true);
2097                     if let Some(PathResolution { base_def: DefTyParam(..), .. }) = path_res {
2098                         self.record_def(eq_pred.id, path_res.unwrap());
2099                     } else {
2100                         //self.resolve_error(eq_pred.path.span, "undeclared associated type");
2101                         resolve_err!(self, eq_pred.span, E0253, "{}",
2102                                      "undeclared associated type");
2103                     }
2104                 }
2105             }
2106         }
2107         visit::walk_generics(self, generics);
2108     }
2109
2110     fn with_current_self_type<T, F>(&mut self, self_type: &Ty, f: F) -> T
2111         where F: FnOnce(&mut Resolver) -> T
2112     {
2113         // Handle nested impls (inside fn bodies)
2114         let previous_value = replace(&mut self.current_self_type, Some(self_type.clone()));
2115         let result = f(self);
2116         self.current_self_type = previous_value;
2117         result
2118     }
2119
2120     fn with_optional_trait_ref<T, F>(&mut self,
2121                                      opt_trait_ref: Option<&TraitRef>,
2122                                      f: F)
2123                                      -> T
2124         where F: FnOnce(&mut Resolver, Option<DefId>) -> T
2125     {
2126         let mut new_val = None;
2127         let mut new_id = None;
2128         if let Some(trait_ref) = opt_trait_ref {
2129             if let Ok(path_res) = self.resolve_trait_reference(trait_ref.ref_id,
2130                                                                &trait_ref.path, 0) {
2131                 assert!(path_res.depth == 0);
2132                 self.record_def(trait_ref.ref_id, path_res);
2133                 new_val = Some((path_res.base_def.def_id(), trait_ref.clone()));
2134                 new_id = Some(path_res.base_def.def_id());
2135             }
2136             visit::walk_trait_ref(self, trait_ref);
2137         }
2138         let original_trait_ref = replace(&mut self.current_trait_ref, new_val);
2139         let result = f(self, new_id);
2140         self.current_trait_ref = original_trait_ref;
2141         result
2142     }
2143
2144     fn with_self_rib<F>(&mut self, self_def: Def, f: F)
2145         where F: FnOnce(&mut Resolver)
2146     {
2147         let mut self_type_rib = Rib::new(NormalRibKind);
2148
2149         // plain insert (no renaming, types are not currently hygienic....)
2150         let name = special_names::type_self;
2151         self_type_rib.bindings.insert(name, DlDef(self_def));
2152         self.type_ribs.push(self_type_rib);
2153         f(self);
2154         self.type_ribs.pop();
2155     }
2156
2157     fn resolve_implementation(&mut self,
2158                               generics: &Generics,
2159                               opt_trait_reference: &Option<TraitRef>,
2160                               self_type: &Ty,
2161                               item_id: NodeId,
2162                               impl_items: &[P<ImplItem>]) {
2163         // If applicable, create a rib for the type parameters.
2164         self.with_type_parameter_rib(HasTypeParameters(generics,
2165                                                        TypeSpace,
2166                                                        ItemRibKind),
2167                                      |this| {
2168             // Resolve the type parameters.
2169             this.visit_generics(generics);
2170
2171             // Resolve the trait reference, if necessary.
2172             this.with_optional_trait_ref(opt_trait_reference.as_ref(), |this, trait_id| {
2173                 // Resolve the self type.
2174                 this.visit_ty(self_type);
2175
2176                 this.with_self_rib(DefSelfTy(trait_id, Some((item_id, self_type.id))), |this| {
2177                     this.with_current_self_type(self_type, |this| {
2178                         for impl_item in impl_items {
2179                             match impl_item.node {
2180                                 ConstImplItem(..) => {
2181                                     // If this is a trait impl, ensure the method
2182                                     // exists in trait
2183                                     this.check_trait_item(impl_item.ident.name,
2184                                                           impl_item.span);
2185                                     this.with_constant_rib(|this| {
2186                                         visit::walk_impl_item(this, impl_item);
2187                                     });
2188                                 }
2189                                 MethodImplItem(ref sig, _) => {
2190                                     // If this is a trait impl, ensure the method
2191                                     // exists in trait
2192                                     this.check_trait_item(impl_item.ident.name,
2193                                                           impl_item.span);
2194
2195                                     // We also need a new scope for the method-
2196                                     // specific type parameters.
2197                                     let type_parameters =
2198                                         HasTypeParameters(&sig.generics,
2199                                                           FnSpace,
2200                                                           MethodRibKind);
2201                                     this.with_type_parameter_rib(type_parameters, |this| {
2202                                         visit::walk_impl_item(this, impl_item);
2203                                     });
2204                                 }
2205                                 TypeImplItem(ref ty) => {
2206                                     // If this is a trait impl, ensure the method
2207                                     // exists in trait
2208                                     this.check_trait_item(impl_item.ident.name,
2209                                                           impl_item.span);
2210
2211                                     this.visit_ty(ty);
2212                                 }
2213                                 ast::MacImplItem(_) => {}
2214                             }
2215                         }
2216                     });
2217                 });
2218             });
2219         });
2220     }
2221
2222     fn check_trait_item(&self, name: Name, span: Span) {
2223         // If there is a TraitRef in scope for an impl, then the method must be in the trait.
2224         if let Some((did, ref trait_ref)) = self.current_trait_ref {
2225             if !self.trait_item_map.contains_key(&(name, did)) {
2226                 let path_str = path_names_to_string(&trait_ref.path, 0);
2227                 /*self.resolve_error(span,
2228                                     &format!("method `{}` is not a member of trait `{}`",
2229                                             name,
2230                                             path_str));*/
2231                 resolve_err!(self, span, E0253, "method `{}` is not a member of trait `{}`",
2232                              name, path_str);
2233             }
2234         }
2235     }
2236
2237     fn resolve_local(&mut self, local: &Local) {
2238         // Resolve the type.
2239         visit::walk_ty_opt(self, &local.ty);
2240
2241         // Resolve the initializer.
2242         visit::walk_expr_opt(self, &local.init);
2243
2244         // Resolve the pattern.
2245         self.resolve_pattern(&*local.pat,
2246                              LocalIrrefutableMode,
2247                              &mut HashMap::new());
2248     }
2249
2250     // build a map from pattern identifiers to binding-info's.
2251     // this is done hygienically. This could arise for a macro
2252     // that expands into an or-pattern where one 'x' was from the
2253     // user and one 'x' came from the macro.
2254     fn binding_mode_map(&mut self, pat: &Pat) -> BindingMap {
2255         let mut result = HashMap::new();
2256         pat_bindings(&self.def_map, pat, |binding_mode, _id, sp, path1| {
2257             let name = mtwt::resolve(path1.node);
2258             result.insert(name, BindingInfo {
2259                 span: sp,
2260                 binding_mode: binding_mode
2261             });
2262         });
2263         return result;
2264     }
2265
2266     // check that all of the arms in an or-pattern have exactly the
2267     // same set of bindings, with the same binding modes for each.
2268     fn check_consistent_bindings(&mut self, arm: &Arm) {
2269         if arm.pats.is_empty() {
2270             return
2271         }
2272         let map_0 = self.binding_mode_map(&*arm.pats[0]);
2273         for (i, p) in arm.pats.iter().enumerate() {
2274             let map_i = self.binding_mode_map(&**p);
2275
2276             for (&key, &binding_0) in &map_0 {
2277                 match map_i.get(&key) {
2278                   None => {
2279                     /*self.resolve_error(
2280                         p.span,
2281                         &format!("variable `{}` from pattern #1 is \
2282                                   not bound in pattern #{}",
2283                                 key,
2284                                 i + 1));*/
2285                     resolve_err!(self, p.span, E0253,
2286                                  "variable `{}` from pattern #1 is \
2287                                   not bound in pattern #{}",
2288                                  key,
2289                                  i + 1);
2290                   }
2291                   Some(binding_i) => {
2292                     if binding_0.binding_mode != binding_i.binding_mode {
2293                         /*self.resolve_error(
2294                             binding_i.span,
2295                             &format!("variable `{}` is bound with different \
2296                                       mode in pattern #{} than in pattern #1",
2297                                     key,
2298                                     i + 1));*/
2299                         resolve_err!(self, binding_i.span, E0253,
2300                                      "variable `{}` is bound with different \
2301                                       mode in pattern #{} than in pattern #1",
2302                                      key,
2303                                      i + 1);
2304                     }
2305                   }
2306                 }
2307             }
2308
2309             for (&key, &binding) in &map_i {
2310                 if !map_0.contains_key(&key) {
2311                     /*self.resolve_error(
2312                         binding.span,
2313                         &format!("variable `{}` from pattern {}{} is \
2314                                   not bound in pattern {}1",
2315                                 key,
2316                                 "#", i + 1, "#"));*/
2317                     resolve_err!(self, binding.span, E0253,
2318                                  "variable `{}` from pattern {}{} is \
2319                                   not bound in pattern {}1",
2320                                  key,
2321                                  "#", i + 1, "#");
2322                 }
2323             }
2324         }
2325     }
2326
2327     fn resolve_arm(&mut self, arm: &Arm) {
2328         self.value_ribs.push(Rib::new(NormalRibKind));
2329
2330         let mut bindings_list = HashMap::new();
2331         for pattern in &arm.pats {
2332             self.resolve_pattern(&**pattern, RefutableMode, &mut bindings_list);
2333         }
2334
2335         // This has to happen *after* we determine which
2336         // pat_idents are variants
2337         self.check_consistent_bindings(arm);
2338
2339         visit::walk_expr_opt(self, &arm.guard);
2340         self.visit_expr(&*arm.body);
2341
2342         self.value_ribs.pop();
2343     }
2344
2345     fn resolve_block(&mut self, block: &Block) {
2346         debug!("(resolving block) entering block");
2347         self.value_ribs.push(Rib::new(NormalRibKind));
2348
2349         // Move down in the graph, if there's an anonymous module rooted here.
2350         let orig_module = self.current_module.clone();
2351         match orig_module.anonymous_children.borrow().get(&block.id) {
2352             None => { /* Nothing to do. */ }
2353             Some(anonymous_module) => {
2354                 debug!("(resolving block) found anonymous module, moving \
2355                         down");
2356                 self.current_module = anonymous_module.clone();
2357             }
2358         }
2359
2360         // Check for imports appearing after non-item statements.
2361         let mut found_non_item = false;
2362         for statement in &block.stmts {
2363             if let ast::StmtDecl(ref declaration, _) = statement.node {
2364                 if let ast::DeclItem(ref i) = declaration.node {
2365                     match i.node {
2366                         ItemExternCrate(_) | ItemUse(_) if found_non_item => {
2367                             span_err!(self.session, i.span, E0154,
2368                                 "imports are not allowed after non-item statements");
2369                         }
2370                         _ => {}
2371                     }
2372                 } else {
2373                     found_non_item = true
2374                 }
2375             } else {
2376                 found_non_item = true;
2377             }
2378         }
2379
2380         // Descend into the block.
2381         visit::walk_block(self, block);
2382
2383         // Move back up.
2384         self.current_module = orig_module;
2385
2386         self.value_ribs.pop();
2387         debug!("(resolving block) leaving block");
2388     }
2389
2390     fn resolve_type(&mut self, ty: &Ty) {
2391         match ty.node {
2392             TyPath(ref maybe_qself, ref path) => {
2393                 let resolution =
2394                     match self.resolve_possibly_assoc_item(ty.id,
2395                                                            maybe_qself.as_ref(),
2396                                                            path,
2397                                                            TypeNS,
2398                                                            true) {
2399                         // `<T>::a::b::c` is resolved by typeck alone.
2400                         TypecheckRequired => {
2401                             // Resolve embedded types.
2402                             visit::walk_ty(self, ty);
2403                             return;
2404                         }
2405                         ResolveAttempt(resolution) => resolution,
2406                     };
2407
2408                 // This is a path in the type namespace. Walk through scopes
2409                 // looking for it.
2410                 match resolution {
2411                     Some(def) => {
2412                         // Write the result into the def map.
2413                         debug!("(resolving type) writing resolution for `{}` \
2414                                 (id {}) = {:?}",
2415                                path_names_to_string(path, 0),
2416                                ty.id, def);
2417                         self.record_def(ty.id, def);
2418                     }
2419                     None => {
2420                         // Keep reporting some errors even if they're ignored above.
2421                         self.resolve_path(ty.id, path, 0, TypeNS, true);
2422
2423                         let kind = if maybe_qself.is_some() {
2424                             "associated type"
2425                         } else {
2426                             "type name"
2427                         };
2428
2429                         let self_type_name = special_idents::type_self.name;
2430                         let is_invalid_self_type_name =
2431                             path.segments.len() > 0 &&
2432                             maybe_qself.is_none() &&
2433                             path.segments[0].identifier.name == self_type_name;
2434                         let msg = if is_invalid_self_type_name {
2435                             "use of `Self` outside of an impl or trait".to_string()
2436                         } else {
2437                             format!("use of undeclared {} `{}`",
2438                                 kind, path_names_to_string(path, 0))
2439                         };
2440
2441                         //self.resolve_error(ty.span, &msg[..]);
2442                         resolve_err!(self, ty.span, E0253,
2443                                      "{}", msg);
2444                     }
2445                 }
2446             }
2447             _ => {}
2448         }
2449         // Resolve embedded types.
2450         visit::walk_ty(self, ty);
2451     }
2452
2453     fn resolve_pattern(&mut self,
2454                        pattern: &Pat,
2455                        mode: PatternBindingMode,
2456                        // Maps idents to the node ID for the (outermost)
2457                        // pattern that binds them
2458                        bindings_list: &mut HashMap<Name, NodeId>) {
2459         let pat_id = pattern.id;
2460         walk_pat(pattern, |pattern| {
2461             match pattern.node {
2462                 PatIdent(binding_mode, ref path1, _) => {
2463
2464                     // The meaning of pat_ident with no type parameters
2465                     // depends on whether an enum variant or unit-like struct
2466                     // with that name is in scope. The probing lookup has to
2467                     // be careful not to emit spurious errors. Only matching
2468                     // patterns (match) can match nullary variants or
2469                     // unit-like structs. For binding patterns (let), matching
2470                     // such a value is simply disallowed (since it's rarely
2471                     // what you want).
2472
2473                     let ident = path1.node;
2474                     let renamed = mtwt::resolve(ident);
2475
2476                     match self.resolve_bare_identifier_pattern(ident.name, pattern.span) {
2477                         FoundStructOrEnumVariant(def, lp)
2478                                 if mode == RefutableMode => {
2479                             debug!("(resolving pattern) resolving `{}` to \
2480                                     struct or enum variant",
2481                                    renamed);
2482
2483                             self.enforce_default_binding_mode(
2484                                 pattern,
2485                                 binding_mode,
2486                                 "an enum variant");
2487                             self.record_def(pattern.id, PathResolution {
2488                                 base_def: def,
2489                                 last_private: lp,
2490                                 depth: 0
2491                             });
2492                         }
2493                         FoundStructOrEnumVariant(..) => {
2494                             /*self.resolve_error(
2495                                 pattern.span,
2496                                 &format!("declaration of `{}` shadows an enum \
2497                                          variant or unit-like struct in \
2498                                          scope",
2499                                         renamed));*/
2500                             resolve_err!(self, pattern.span, E0253,
2501                                          "declaration of `{}` shadows an enum \
2502                                          variant or unit-like struct in \
2503                                          scope",
2504                                          renamed);
2505                         }
2506                         FoundConst(def, lp) if mode == RefutableMode => {
2507                             debug!("(resolving pattern) resolving `{}` to \
2508                                     constant",
2509                                    renamed);
2510
2511                             self.enforce_default_binding_mode(
2512                                 pattern,
2513                                 binding_mode,
2514                                 "a constant");
2515                             self.record_def(pattern.id, PathResolution {
2516                                 base_def: def,
2517                                 last_private: lp,
2518                                 depth: 0
2519                             });
2520                         }
2521                         FoundConst(..) => {
2522                             /*self.resolve_error(pattern.span,
2523                                                   "only irrefutable patterns \
2524                                                    allowed here");*/
2525                             resolve_err!(self, pattern.span, E0253,
2526                                          "{}",
2527                                          "only irrefutable patterns \
2528                                           allowed here");
2529                         }
2530                         BareIdentifierPatternUnresolved => {
2531                             debug!("(resolving pattern) binding `{}`",
2532                                    renamed);
2533
2534                             let def = DefLocal(pattern.id);
2535
2536                             // Record the definition so that later passes
2537                             // will be able to distinguish variants from
2538                             // locals in patterns.
2539
2540                             self.record_def(pattern.id, PathResolution {
2541                                 base_def: def,
2542                                 last_private: LastMod(AllPublic),
2543                                 depth: 0
2544                             });
2545
2546                             // Add the binding to the local ribs, if it
2547                             // doesn't already exist in the bindings list. (We
2548                             // must not add it if it's in the bindings list
2549                             // because that breaks the assumptions later
2550                             // passes make about or-patterns.)
2551                             if !bindings_list.contains_key(&renamed) {
2552                                 let this = &mut *self;
2553                                 let last_rib = this.value_ribs.last_mut().unwrap();
2554                                 last_rib.bindings.insert(renamed, DlDef(def));
2555                                 bindings_list.insert(renamed, pat_id);
2556                             } else if mode == ArgumentIrrefutableMode &&
2557                                     bindings_list.contains_key(&renamed) {
2558                                 // Forbid duplicate bindings in the same
2559                                 // parameter list.
2560                                 /*self.resolve_error(pattern.span,
2561                                                    &format!("identifier `{}` \
2562                                                             is bound more \
2563                                                             than once in \
2564                                                             this parameter \
2565                                                             list",
2566                                                            token::get_ident(
2567                                                                ident))
2568                                                    )*/
2569                                 resolve_err!(self, pattern.span, E0253,
2570                                              "identifier `{}` \
2571                                               is bound more \
2572                                               than once in \
2573                                               this parameter \
2574                                               list",
2575                                              token::get_ident(ident));
2576                             } else if bindings_list.get(&renamed) ==
2577                                     Some(&pat_id) {
2578                                 // Then this is a duplicate variable in the
2579                                 // same disjunction, which is an error.
2580                                 /*self.resolve_error(pattern.span,
2581                                     &format!("identifier `{}` is bound \
2582                                              more than once in the same \
2583                                              pattern",
2584                                             token::get_ident(ident)));*/
2585                                 resolve_err!(self, pattern.span, E0253,
2586                                              "identifier `{}` is bound \
2587                                               more than once in the same \
2588                                               pattern",
2589                                              token::get_ident(ident));
2590                             }
2591                             // Else, not bound in the same pattern: do
2592                             // nothing.
2593                         }
2594                     }
2595                 }
2596
2597                 PatEnum(ref path, _) => {
2598                     // This must be an enum variant, struct or const.
2599                     let resolution =
2600                         match self.resolve_possibly_assoc_item(pat_id, None,
2601                                                                path, ValueNS,
2602                                                                false) {
2603                             // The below shouldn't happen because all
2604                             // qualified paths should be in PatQPath.
2605                             TypecheckRequired =>
2606                                 self.session.span_bug(
2607                                     path.span,
2608                                     "resolve_possibly_assoc_item claimed
2609                                      that a path in PatEnum requires typecheck
2610                                      to resolve, but qualified paths should be
2611                                      PatQPath"),
2612                             ResolveAttempt(resolution) => resolution,
2613                         };
2614                     if let Some(path_res) = resolution {
2615                         match path_res.base_def {
2616                             DefVariant(..) | DefStruct(..) | DefConst(..) => {
2617                                 self.record_def(pattern.id, path_res);
2618                             }
2619                             DefStatic(..) => {
2620                                 /*self.resolve_error(path.span,
2621                                                    "static variables cannot be \
2622                                                     referenced in a pattern, \
2623                                                     use a `const` instead");*/
2624                                 resolve_err!(self, path.span, E0253, "{}",
2625                                              "static variables cannot be \
2626                                               referenced in a pattern, \
2627                                               use a `const` instead");
2628                             }
2629                             _ => {
2630                                 // If anything ends up here entirely resolved,
2631                                 // it's an error. If anything ends up here
2632                                 // partially resolved, that's OK, because it may
2633                                 // be a `T::CONST` that typeck will resolve.
2634                                 if path_res.depth == 0 {
2635                                     /*self.resolve_error(
2636                                         path.span,
2637                                         &format!("`{}` is not an enum variant, struct or const",
2638                                                  token::get_ident(
2639                                                      path.segments.last().unwrap().identifier)));*/
2640                                     resolve_err!(self, path.span, E0253,
2641                                                  "`{}` is not an enum variant, struct or const",
2642                                                  token::get_ident(
2643                                                      path.segments.last().unwrap().identifier));
2644                                 } else {
2645                                     let const_name = path.segments.last().unwrap()
2646                                                          .identifier.name;
2647                                     let traits = self.get_traits_containing_item(const_name);
2648                                     self.trait_map.insert(pattern.id, traits);
2649                                     self.record_def(pattern.id, path_res);
2650                                 }
2651                             }
2652                         }
2653                     } else {
2654                         /*self.resolve_error(path.span,
2655                             &format!("unresolved enum variant, struct or const `{}`",
2656                                 token::get_ident(path.segments.last().unwrap().identifier)));*/
2657                         resolve_err!(self, path.span, E0253,
2658                                      "unresolved enum variant, struct or const `{}`",
2659                                      token::get_ident(path.segments.last().unwrap().identifier));
2660                     }
2661                     visit::walk_path(self, path);
2662                 }
2663
2664                 PatQPath(ref qself, ref path) => {
2665                     // Associated constants only.
2666                     let resolution =
2667                         match self.resolve_possibly_assoc_item(pat_id, Some(qself),
2668                                                                path, ValueNS,
2669                                                                false) {
2670                             TypecheckRequired => {
2671                                 // All `<T>::CONST` should end up here, and will
2672                                 // require use of the trait map to resolve
2673                                 // during typechecking.
2674                                 let const_name = path.segments.last().unwrap()
2675                                                      .identifier.name;
2676                                 let traits = self.get_traits_containing_item(const_name);
2677                                 self.trait_map.insert(pattern.id, traits);
2678                                 visit::walk_pat(self, pattern);
2679                                 return true;
2680                             }
2681                             ResolveAttempt(resolution) => resolution,
2682                         };
2683                     if let Some(path_res) = resolution {
2684                         match path_res.base_def {
2685                             // All `<T as Trait>::CONST` should end up here, and
2686                             // have the trait already selected.
2687                             DefAssociatedConst(..) => {
2688                                 self.record_def(pattern.id, path_res);
2689                             }
2690                             _ => {
2691                                 /*self.resolve_error(path.span,
2692                                     &format!("`{}` is not an associated const",
2693                                         token::get_ident(
2694                                             path.segments.last().unwrap().identifier)));*/
2695                                 resolve_err!(self, path.span, E0253,
2696                                              "`{}` is not an associated const",
2697                                              token::get_ident(
2698                                                  path.segments.last().unwrap().identifier));
2699                             }
2700                         }
2701                     } else {
2702                         /*self.resolve_error(path.span,
2703                             &format!("unresolved associated const `{}`",
2704                                 token::get_ident(path.segments.last().unwrap().identifier)));*/
2705                         resolve_err!(self, path.span, E0253,
2706                                      "unresolved associated const `{}`",
2707                                      token::get_ident(path.segments.last().unwrap().identifier));
2708                     }
2709                     visit::walk_pat(self, pattern);
2710                 }
2711
2712                 PatStruct(ref path, _, _) => {
2713                     match self.resolve_path(pat_id, path, 0, TypeNS, false) {
2714                         Some(definition) => {
2715                             self.record_def(pattern.id, definition);
2716                         }
2717                         result => {
2718                             debug!("(resolving pattern) didn't find struct \
2719                                     def: {:?}", result);
2720                             /*let msg = format!("`{}` does not name a structure",
2721                                               path_names_to_string(path, 0));
2722                             self.resolve_error(path.span, &msg[..]);*/
2723                             resolve_err!(self, path.span, E0253,
2724                                          "`{}` does not name a structure",
2725                                          path_names_to_string(path, 0));
2726                         }
2727                     }
2728                     visit::walk_path(self, path);
2729                 }
2730
2731                 PatLit(_) | PatRange(..) => {
2732                     visit::walk_pat(self, pattern);
2733                 }
2734
2735                 _ => {
2736                     // Nothing to do.
2737                 }
2738             }
2739             true
2740         });
2741     }
2742
2743     fn resolve_bare_identifier_pattern(&mut self, name: Name, span: Span)
2744                                        -> BareIdentifierPatternResolution {
2745         let module = self.current_module.clone();
2746         match self.resolve_item_in_lexical_scope(module,
2747                                                  name,
2748                                                  ValueNS) {
2749             Success((target, _)) => {
2750                 debug!("(resolve bare identifier pattern) succeeded in \
2751                          finding {} at {:?}",
2752                         name,
2753                         target.bindings.value_def.borrow());
2754                 match *target.bindings.value_def.borrow() {
2755                     None => {
2756                         panic!("resolved name in the value namespace to a \
2757                               set of name bindings with no def?!");
2758                     }
2759                     Some(def) => {
2760                         // For the two success cases, this lookup can be
2761                         // considered as not having a private component because
2762                         // the lookup happened only within the current module.
2763                         match def.def {
2764                             def @ DefVariant(..) | def @ DefStruct(..) => {
2765                                 return FoundStructOrEnumVariant(def, LastMod(AllPublic));
2766                             }
2767                             def @ DefConst(..) | def @ DefAssociatedConst(..) => {
2768                                 return FoundConst(def, LastMod(AllPublic));
2769                             }
2770                             DefStatic(..) => {
2771                                 /*self.resolve_error(span,
2772                                                    "static variables cannot be \
2773                                                     referenced in a pattern, \
2774                                                     use a `const` instead");*/
2775                                 resolve_err!(self, span, E0253,
2776                                              "{}",
2777                                              "static variables cannot be \
2778                                               referenced in a pattern, \
2779                                               use a `const` instead");
2780                                 return BareIdentifierPatternUnresolved;
2781                             }
2782                             _ => {
2783                                 return BareIdentifierPatternUnresolved;
2784                             }
2785                         }
2786                     }
2787                 }
2788             }
2789
2790             Indeterminate => {
2791                 panic!("unexpected indeterminate result");
2792             }
2793             Failed(err) => {
2794                 match err {
2795                     Some((span, msg)) => {
2796                         /*self.resolve_error(span, &format!("failed to resolve: {}",
2797                                                          msg));*/
2798                         resolve_err!(self, span, E0253,
2799                                      "failed to resolve: {}",
2800                                      msg);
2801                     }
2802                     None => ()
2803                 }
2804
2805                 debug!("(resolve bare identifier pattern) failed to find {}",
2806                         name);
2807                 return BareIdentifierPatternUnresolved;
2808             }
2809         }
2810     }
2811
2812     /// Handles paths that may refer to associated items
2813     fn resolve_possibly_assoc_item(&mut self,
2814                                    id: NodeId,
2815                                    maybe_qself: Option<&ast::QSelf>,
2816                                    path: &Path,
2817                                    namespace: Namespace,
2818                                    check_ribs: bool)
2819                                    -> AssocItemResolveResult
2820     {
2821         let max_assoc_types;
2822
2823         match maybe_qself {
2824             Some(qself) => {
2825                 if qself.position == 0 {
2826                     return TypecheckRequired;
2827                 }
2828                 max_assoc_types = path.segments.len() - qself.position;
2829                 // Make sure the trait is valid.
2830                 let _ = self.resolve_trait_reference(id, path, max_assoc_types);
2831             }
2832             None => {
2833                 max_assoc_types = path.segments.len();
2834             }
2835         }
2836
2837         let mut resolution = self.with_no_errors(|this| {
2838             this.resolve_path(id, path, 0, namespace, check_ribs)
2839         });
2840         for depth in 1..max_assoc_types {
2841             if resolution.is_some() {
2842                 break;
2843             }
2844             self.with_no_errors(|this| {
2845                 resolution = this.resolve_path(id, path, depth,
2846                                                TypeNS, true);
2847             });
2848         }
2849         if let Some(DefMod(_)) = resolution.map(|r| r.base_def) {
2850             // A module is not a valid type or value.
2851             resolution = None;
2852         }
2853         ResolveAttempt(resolution)
2854     }
2855
2856     /// If `check_ribs` is true, checks the local definitions first; i.e.
2857     /// doesn't skip straight to the containing module.
2858     /// Skips `path_depth` trailing segments, which is also reflected in the
2859     /// returned value. See `middle::def::PathResolution` for more info.
2860     fn resolve_path(&mut self,
2861                     id: NodeId,
2862                     path: &Path,
2863                     path_depth: usize,
2864                     namespace: Namespace,
2865                     check_ribs: bool) -> Option<PathResolution> {
2866         let span = path.span;
2867         let segments = &path.segments[..path.segments.len()-path_depth];
2868
2869         let mk_res = |(def, lp)| PathResolution::new(def, lp, path_depth);
2870
2871         if path.global {
2872             let def = self.resolve_crate_relative_path(span, segments, namespace);
2873             return def.map(mk_res);
2874         }
2875
2876         // Try to find a path to an item in a module.
2877         let unqualified_def =
2878                 self.resolve_identifier(segments.last().unwrap().identifier,
2879                                         namespace,
2880                                         check_ribs,
2881                                         span);
2882
2883         if segments.len() <= 1 {
2884             return unqualified_def.map(mk_res);
2885         }
2886
2887         let def = self.resolve_module_relative_path(span, segments, namespace);
2888         match (def, unqualified_def) {
2889             (Some((ref d, _)), Some((ref ud, _))) if *d == *ud => {
2890                 self.session
2891                     .add_lint(lint::builtin::UNUSED_QUALIFICATIONS,
2892                               id, span,
2893                               "unnecessary qualification".to_string());
2894             }
2895             _ => {}
2896         }
2897
2898         def.map(mk_res)
2899     }
2900
2901     // Resolve a single identifier.
2902     fn resolve_identifier(&mut self,
2903                           identifier: Ident,
2904                           namespace: Namespace,
2905                           check_ribs: bool,
2906                           span: Span)
2907                           -> Option<(Def, LastPrivate)> {
2908         // First, check to see whether the name is a primitive type.
2909         if namespace == TypeNS {
2910             if let Some(&prim_ty) = self.primitive_type_table
2911                                         .primitive_types
2912                                         .get(&identifier.name) {
2913                 return Some((DefPrimTy(prim_ty), LastMod(AllPublic)));
2914             }
2915         }
2916
2917         if check_ribs {
2918             if let Some(def) = self.resolve_identifier_in_local_ribs(identifier,
2919                                                                      namespace,
2920                                                                      span) {
2921                 return Some((def, LastMod(AllPublic)));
2922             }
2923         }
2924
2925         self.resolve_item_by_name_in_lexical_scope(identifier.name, namespace)
2926     }
2927
2928     // FIXME #4952: Merge me with resolve_name_in_module?
2929     fn resolve_definition_of_name_in_module(&mut self,
2930                                             containing_module: Rc<Module>,
2931                                             name: Name,
2932                                             namespace: Namespace)
2933                                             -> NameDefinition {
2934         // First, search children.
2935         build_reduced_graph::populate_module_if_necessary(self, &containing_module);
2936
2937         match containing_module.children.borrow().get(&name) {
2938             Some(child_name_bindings) => {
2939                 match child_name_bindings.def_for_namespace(namespace) {
2940                     Some(def) => {
2941                         // Found it. Stop the search here.
2942                         let p = child_name_bindings.defined_in_public_namespace(namespace);
2943                         let lp = if p {LastMod(AllPublic)} else {
2944                             LastMod(DependsOn(def.def_id()))
2945                         };
2946                         return ChildNameDefinition(def, lp);
2947                     }
2948                     None => {}
2949                 }
2950             }
2951             None => {}
2952         }
2953
2954         // Next, search import resolutions.
2955         match containing_module.import_resolutions.borrow().get(&name) {
2956             Some(import_resolution) if import_resolution.is_public => {
2957                 if let Some(target) = (*import_resolution).target_for_namespace(namespace) {
2958                     match target.bindings.def_for_namespace(namespace) {
2959                         Some(def) => {
2960                             // Found it.
2961                             let id = import_resolution.id(namespace);
2962                             // track imports and extern crates as well
2963                             self.used_imports.insert((id, namespace));
2964                             self.record_import_use(id, name);
2965                             match target.target_module.def_id.get() {
2966                                 Some(DefId{krate: kid, ..}) => {
2967                                     self.used_crates.insert(kid);
2968                                 },
2969                                 _ => {}
2970                             }
2971                             return ImportNameDefinition(def, LastMod(AllPublic));
2972                         }
2973                         None => {
2974                             // This can happen with external impls, due to
2975                             // the imperfect way we read the metadata.
2976                         }
2977                     }
2978                 }
2979             }
2980             Some(..) | None => {} // Continue.
2981         }
2982
2983         // Finally, search through external children.
2984         if namespace == TypeNS {
2985             if let Some(module) = containing_module.external_module_children.borrow()
2986                                                    .get(&name).cloned() {
2987                 if let Some(def_id) = module.def_id.get() {
2988                     // track used crates
2989                     self.used_crates.insert(def_id.krate);
2990                     let lp = if module.is_public {LastMod(AllPublic)} else {
2991                         LastMod(DependsOn(def_id))
2992                     };
2993                     return ChildNameDefinition(DefMod(def_id), lp);
2994                 }
2995             }
2996         }
2997
2998         return NoNameDefinition;
2999     }
3000
3001     // resolve a "module-relative" path, e.g. a::b::c
3002     fn resolve_module_relative_path(&mut self,
3003                                     span: Span,
3004                                     segments: &[ast::PathSegment],
3005                                     namespace: Namespace)
3006                                     -> Option<(Def, LastPrivate)> {
3007         let module_path = segments.init().iter()
3008                                          .map(|ps| ps.identifier.name)
3009                                          .collect::<Vec<_>>();
3010
3011         let containing_module;
3012         let last_private;
3013         let current_module = self.current_module.clone();
3014         match self.resolve_module_path(current_module,
3015                                        &module_path[..],
3016                                        UseLexicalScope,
3017                                        span,
3018                                        PathSearch) {
3019             Failed(err) => {
3020                 let (span, msg) = match err {
3021                     Some((span, msg)) => (span, msg),
3022                     None => {
3023                         let msg = format!("Use of undeclared type or module `{}`",
3024                                           names_to_string(&module_path));
3025                         (span, msg)
3026                     }
3027                 };
3028
3029                 /*self.resolve_error(span, &format!("failed to resolve. {}",
3030                                                  msg));*/
3031                 resolve_err!(self, span, E0253,
3032                              "failed to resolve: {}",
3033                              msg);
3034                 return None;
3035             }
3036             Indeterminate => panic!("indeterminate unexpected"),
3037             Success((resulting_module, resulting_last_private)) => {
3038                 containing_module = resulting_module;
3039                 last_private = resulting_last_private;
3040             }
3041         }
3042
3043         let name = segments.last().unwrap().identifier.name;
3044         let def = match self.resolve_definition_of_name_in_module(containing_module.clone(),
3045                                                                   name,
3046                                                                   namespace) {
3047             NoNameDefinition => {
3048                 // We failed to resolve the name. Report an error.
3049                 return None;
3050             }
3051             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
3052                 (def, last_private.or(lp))
3053             }
3054         };
3055         if let Some(DefId{krate: kid, ..}) = containing_module.def_id.get() {
3056             self.used_crates.insert(kid);
3057         }
3058         return Some(def);
3059     }
3060
3061     /// Invariant: This must be called only during main resolution, not during
3062     /// import resolution.
3063     fn resolve_crate_relative_path(&mut self,
3064                                    span: Span,
3065                                    segments: &[ast::PathSegment],
3066                                    namespace: Namespace)
3067                                        -> Option<(Def, LastPrivate)> {
3068         let module_path = segments.init().iter()
3069                                          .map(|ps| ps.identifier.name)
3070                                          .collect::<Vec<_>>();
3071
3072         let root_module = self.graph_root.get_module();
3073
3074         let containing_module;
3075         let last_private;
3076         match self.resolve_module_path_from_root(root_module,
3077                                                  &module_path[..],
3078                                                  0,
3079                                                  span,
3080                                                  PathSearch,
3081                                                  LastMod(AllPublic)) {
3082             Failed(err) => {
3083                 let (span, msg) = match err {
3084                     Some((span, msg)) => (span, msg),
3085                     None => {
3086                         let msg = format!("Use of undeclared module `::{}`",
3087                                           names_to_string(&module_path[..]));
3088                         (span, msg)
3089                     }
3090                 };
3091
3092                 /*self.resolve_error(span, &format!("failed to resolve. {}",
3093                                                  msg));*/
3094                 resolve_err!(self, span, E0253,
3095                              "failed to resolve: {}",
3096                              msg);
3097                 return None;
3098             }
3099
3100             Indeterminate => {
3101                 panic!("indeterminate unexpected");
3102             }
3103
3104             Success((resulting_module, resulting_last_private)) => {
3105                 containing_module = resulting_module;
3106                 last_private = resulting_last_private;
3107             }
3108         }
3109
3110         let name = segments.last().unwrap().identifier.name;
3111         match self.resolve_definition_of_name_in_module(containing_module,
3112                                                         name,
3113                                                         namespace) {
3114             NoNameDefinition => {
3115                 // We failed to resolve the name. Report an error.
3116                 return None;
3117             }
3118             ChildNameDefinition(def, lp) | ImportNameDefinition(def, lp) => {
3119                 return Some((def, last_private.or(lp)));
3120             }
3121         }
3122     }
3123
3124     fn resolve_identifier_in_local_ribs(&mut self,
3125                                         ident: Ident,
3126                                         namespace: Namespace,
3127                                         span: Span)
3128                                         -> Option<Def> {
3129         // Check the local set of ribs.
3130         let search_result = match namespace {
3131             ValueNS => {
3132                 let renamed = mtwt::resolve(ident);
3133                 self.search_ribs(&self.value_ribs, renamed, span)
3134             }
3135             TypeNS => {
3136                 let name = ident.name;
3137                 self.search_ribs(&self.type_ribs, name, span)
3138             }
3139         };
3140
3141         match search_result {
3142             Some(DlDef(def)) => {
3143                 debug!("(resolving path in local ribs) resolved `{}` to local: {:?}",
3144                        token::get_ident(ident),
3145                        def);
3146                 Some(def)
3147             }
3148             Some(DlField) | Some(DlImpl(_)) | None => {
3149                 None
3150             }
3151         }
3152     }
3153
3154     fn resolve_item_by_name_in_lexical_scope(&mut self,
3155                                              name: Name,
3156                                              namespace: Namespace)
3157                                             -> Option<(Def, LastPrivate)> {
3158         // Check the items.
3159         let module = self.current_module.clone();
3160         match self.resolve_item_in_lexical_scope(module,
3161                                                  name,
3162                                                  namespace) {
3163             Success((target, _)) => {
3164                 match (*target.bindings).def_for_namespace(namespace) {
3165                     None => {
3166                         // This can happen if we were looking for a type and
3167                         // found a module instead. Modules don't have defs.
3168                         debug!("(resolving item path by identifier in lexical \
3169                                  scope) failed to resolve {} after success...",
3170                                  name);
3171                         return None;
3172                     }
3173                     Some(def) => {
3174                         debug!("(resolving item path in lexical scope) \
3175                                 resolved `{}` to item",
3176                                name);
3177                         // This lookup is "all public" because it only searched
3178                         // for one identifier in the current module (couldn't
3179                         // have passed through reexports or anything like that.
3180                         return Some((def, LastMod(AllPublic)));
3181                     }
3182                 }
3183             }
3184             Indeterminate => {
3185                 panic!("unexpected indeterminate result");
3186             }
3187             Failed(err) => {
3188                 debug!("(resolving item path by identifier in lexical scope) \
3189                          failed to resolve {}", name);
3190
3191                 if let Some((span, msg)) = err {
3192                     //self.resolve_error(span, &format!("failed to resolve. {}", msg))
3193                     resolve_err!(self, span, E0253,
3194                                  "failed to resolve: {}",
3195                                  msg)
3196                 }
3197
3198                 return None;
3199             }
3200         }
3201     }
3202
3203     fn with_no_errors<T, F>(&mut self, f: F) -> T where
3204         F: FnOnce(&mut Resolver) -> T,
3205     {
3206         self.emit_errors = false;
3207         let rs = f(self);
3208         self.emit_errors = true;
3209         rs
3210     }
3211
3212     fn resolve_error(&self, span: Span, s: &str) {
3213         if self.emit_errors {
3214             self.session.span_err(span, s);
3215         }
3216     }
3217
3218     fn find_fallback_in_self_type(&mut self, name: Name) -> FallbackSuggestion {
3219         fn extract_path_and_node_id(t: &Ty, allow: FallbackChecks)
3220                                                     -> Option<(Path, NodeId, FallbackChecks)> {
3221             match t.node {
3222                 TyPath(None, ref path) => Some((path.clone(), t.id, allow)),
3223                 TyPtr(ref mut_ty) => extract_path_and_node_id(&*mut_ty.ty, OnlyTraitAndStatics),
3224                 TyRptr(_, ref mut_ty) => extract_path_and_node_id(&*mut_ty.ty, allow),
3225                 // This doesn't handle the remaining `Ty` variants as they are not
3226                 // that commonly the self_type, it might be interesting to provide
3227                 // support for those in future.
3228                 _ => None,
3229             }
3230         }
3231
3232         fn get_module(this: &mut Resolver, span: Span, name_path: &[ast::Name])
3233                             -> Option<Rc<Module>> {
3234             let root = this.current_module.clone();
3235             let last_name = name_path.last().unwrap();
3236
3237             if name_path.len() == 1 {
3238                 match this.primitive_type_table.primitive_types.get(last_name) {
3239                     Some(_) => None,
3240                     None => {
3241                         match this.current_module.children.borrow().get(last_name) {
3242                             Some(child) => child.get_module_if_available(),
3243                             None => None
3244                         }
3245                     }
3246                 }
3247             } else {
3248                 match this.resolve_module_path(root,
3249                                                &name_path[..],
3250                                                UseLexicalScope,
3251                                                span,
3252                                                PathSearch) {
3253                     Success((module, _)) => Some(module),
3254                     _ => None
3255                 }
3256             }
3257         }
3258
3259         fn is_static_method(this: &Resolver, did: DefId) -> bool {
3260             if did.krate == ast::LOCAL_CRATE {
3261                 let sig = match this.ast_map.get(did.node) {
3262                     ast_map::NodeTraitItem(trait_item) => match trait_item.node {
3263                         ast::MethodTraitItem(ref sig, _) => sig,
3264                         _ => return false
3265                     },
3266                     ast_map::NodeImplItem(impl_item) => match impl_item.node {
3267                         ast::MethodImplItem(ref sig, _) => sig,
3268                         _ => return false
3269                     },
3270                     _ => return false
3271                 };
3272                 sig.explicit_self.node == ast::SelfStatic
3273             } else {
3274                 csearch::is_static_method(&this.session.cstore, did)
3275             }
3276         }
3277
3278         let (path, node_id, allowed) = match self.current_self_type {
3279             Some(ref ty) => match extract_path_and_node_id(ty, Everything) {
3280                 Some(x) => x,
3281                 None => return NoSuggestion,
3282             },
3283             None => return NoSuggestion,
3284         };
3285
3286         if allowed == Everything {
3287             // Look for a field with the same name in the current self_type.
3288             match self.def_map.borrow().get(&node_id).map(|d| d.full_def()) {
3289                 Some(DefTy(did, _)) |
3290                 Some(DefStruct(did)) |
3291                 Some(DefVariant(_, did, _)) => match self.structs.get(&did) {
3292                     None => {}
3293                     Some(fields) => {
3294                         if fields.iter().any(|&field_name| name == field_name) {
3295                             return Field;
3296                         }
3297                     }
3298                 },
3299                 _ => {} // Self type didn't resolve properly
3300             }
3301         }
3302
3303         let name_path = path.segments.iter().map(|seg| seg.identifier.name).collect::<Vec<_>>();
3304
3305         // Look for a method in the current self type's impl module.
3306         if let Some(module) = get_module(self, path.span, &name_path) {
3307             if let Some(binding) = module.children.borrow().get(&name) {
3308                 if let Some(DefMethod(did, _)) = binding.def_for_namespace(ValueNS) {
3309                     if is_static_method(self, did) {
3310                         return StaticMethod(path_names_to_string(&path, 0))
3311                     }
3312                     if self.current_trait_ref.is_some() {
3313                         return TraitItem;
3314                     } else if allowed == Everything {
3315                         return Method;
3316                     }
3317                 }
3318             }
3319         }
3320
3321         // Look for a method in the current trait.
3322         if let Some((trait_did, ref trait_ref)) = self.current_trait_ref {
3323             if let Some(&did) = self.trait_item_map.get(&(name, trait_did)) {
3324                 if is_static_method(self, did) {
3325                     return TraitMethod(path_names_to_string(&trait_ref.path, 0));
3326                 } else {
3327                     return TraitItem;
3328                 }
3329             }
3330         }
3331
3332         NoSuggestion
3333     }
3334
3335     fn find_best_match_for_name(&mut self, name: &str) -> Option<String> {
3336         let mut maybes: Vec<token::InternedString> = Vec::new();
3337         let mut values: Vec<usize> = Vec::new();
3338
3339         for rib in self.value_ribs.iter().rev() {
3340             for (&k, _) in &rib.bindings {
3341                 maybes.push(token::get_name(k));
3342                 values.push(usize::MAX);
3343             }
3344         }
3345
3346         let mut smallest = 0;
3347         for (i, other) in maybes.iter().enumerate() {
3348             values[i] = lev_distance(name, &other);
3349
3350             if values[i] <= values[smallest] {
3351                 smallest = i;
3352             }
3353         }
3354
3355         // As a loose rule to avoid obviously incorrect suggestions, clamp the
3356         // maximum edit distance we will accept for a suggestion to one third of
3357         // the typo'd name's length.
3358         let max_distance = std::cmp::max(name.len(), 3) / 3;
3359
3360         if !values.is_empty() &&
3361             values[smallest] <= max_distance &&
3362             name != &maybes[smallest][..] {
3363
3364             Some(maybes[smallest].to_string())
3365
3366         } else {
3367             None
3368         }
3369     }
3370
3371     fn resolve_expr(&mut self, expr: &Expr) {
3372         // First, record candidate traits for this expression if it could
3373         // result in the invocation of a method call.
3374
3375         self.record_candidate_traits_for_expr_if_necessary(expr);
3376
3377         // Next, resolve the node.
3378         match expr.node {
3379             ExprPath(ref maybe_qself, ref path) => {
3380                 let resolution =
3381                     match self.resolve_possibly_assoc_item(expr.id,
3382                                                            maybe_qself.as_ref(),
3383                                                            path,
3384                                                            ValueNS,
3385                                                            true) {
3386                         // `<T>::a::b::c` is resolved by typeck alone.
3387                         TypecheckRequired => {
3388                             let method_name = path.segments.last().unwrap().identifier.name;
3389                             let traits = self.get_traits_containing_item(method_name);
3390                             self.trait_map.insert(expr.id, traits);
3391                             visit::walk_expr(self, expr);
3392                             return;
3393                         }
3394                         ResolveAttempt(resolution) => resolution,
3395                     };
3396
3397                 // This is a local path in the value namespace. Walk through
3398                 // scopes looking for it.
3399                 if let Some(path_res) = resolution {
3400                     // Check if struct variant
3401                     if let DefVariant(_, _, true) = path_res.base_def {
3402                         let path_name = path_names_to_string(path, 0);
3403                         /*self.resolve_error(expr.span,
3404                                 &format!("`{}` is a struct variant name, but \
3405                                           this expression \
3406                                           uses it like a function name",
3407                                          path_name));*/
3408                         resolve_err!(self, expr.span, E0253,
3409                                      "`{}` is a struct variant name, but \
3410                                       this expression \
3411                                       uses it like a function name",
3412                                      path_name);
3413
3414                         let msg = format!("did you mean to write: \
3415                                            `{} {{ /* fields */ }}`?",
3416                                           path_name);
3417                         if self.emit_errors {
3418                             self.session.fileline_help(expr.span, &msg);
3419                         } else {
3420                             self.session.span_help(expr.span, &msg);
3421                         }
3422                     } else {
3423                         // Write the result into the def map.
3424                         debug!("(resolving expr) resolved `{}`",
3425                                path_names_to_string(path, 0));
3426
3427                         // Partial resolutions will need the set of traits in scope,
3428                         // so they can be completed during typeck.
3429                         if path_res.depth != 0 {
3430                             let method_name = path.segments.last().unwrap().identifier.name;
3431                             let traits = self.get_traits_containing_item(method_name);
3432                             self.trait_map.insert(expr.id, traits);
3433                         }
3434
3435                         self.record_def(expr.id, path_res);
3436                     }
3437                 } else {
3438                     // Be helpful if the name refers to a struct
3439                     // (The pattern matching def_tys where the id is in self.structs
3440                     // matches on regular structs while excluding tuple- and enum-like
3441                     // structs, which wouldn't result in this error.)
3442                     let path_name = path_names_to_string(path, 0);
3443                     let type_res = self.with_no_errors(|this| {
3444                         this.resolve_path(expr.id, path, 0, TypeNS, false)
3445                     });
3446                     match type_res.map(|r| r.base_def) {
3447                         Some(DefTy(struct_id, _))
3448                             if self.structs.contains_key(&struct_id) => {
3449                                 /*self.resolve_error(expr.span,
3450                                     &format!("`{}` is a structure name, but \
3451                                                 this expression \
3452                                                 uses it like a function name",
3453                                                 path_name));*/
3454                                 resolve_err!(self, expr.span, E0253,
3455                                              "{}` is a structure name, but \
3456                                               this expression \
3457                                               uses it like a function name",
3458                                               path_name);
3459
3460                                 let msg = format!("did you mean to write: \
3461                                                      `{} {{ /* fields */ }}`?",
3462                                                     path_name);
3463                                 if self.emit_errors {
3464                                     self.session.fileline_help(expr.span, &msg);
3465                                 } else {
3466                                     self.session.span_help(expr.span, &msg);
3467                                 }
3468                             }
3469                         _ => {
3470                             // Keep reporting some errors even if they're ignored above.
3471                             self.resolve_path(expr.id, path, 0, ValueNS, true);
3472
3473                             let mut method_scope = false;
3474                             self.value_ribs.iter().rev().all(|rib| {
3475                                 method_scope = match rib.kind {
3476                                     MethodRibKind => true,
3477                                     ItemRibKind | ConstantItemRibKind => false,
3478                                     _ => return true, // Keep advancing
3479                                 };
3480                                 false // Stop advancing
3481                             });
3482
3483                             if method_scope &&
3484                                &token::get_name(special_names::self_)[..] == path_name {
3485                                     /*self.resolve_error(
3486                                         expr.span,
3487                                         "`self` is not available \
3488                                          in a static method. Maybe a \
3489                                          `self` argument is missing?");*/
3490                                     resolve_err!(self, expr.span, E0253,
3491                                                  "{}",
3492                                                  "`self` is not available \
3493                                                   in a static method. Maybe a \
3494                                                   `self` argument is missing?");
3495                             } else {
3496                                 let last_name = path.segments.last().unwrap().identifier.name;
3497                                 let mut msg = match self.find_fallback_in_self_type(last_name) {
3498                                     NoSuggestion => {
3499                                         // limit search to 5 to reduce the number
3500                                         // of stupid suggestions
3501                                         self.find_best_match_for_name(&path_name)
3502                                                             .map_or("".to_string(),
3503                                                                     |x| format!("`{}`", x))
3504                                     }
3505                                     Field => format!("`self.{}`", path_name),
3506                                     Method |
3507                                     TraitItem =>
3508                                         format!("to call `self.{}`", path_name),
3509                                     TraitMethod(path_str) |
3510                                     StaticMethod(path_str) =>
3511                                         format!("to call `{}::{}`", path_str, path_name)
3512                                 };
3513
3514                                 if !msg.is_empty() {
3515                                     msg = format!(". Did you mean {}?", msg)
3516                                 }
3517
3518                                 /*self.resolve_error(
3519                                     expr.span,
3520                                     &format!("unresolved name `{}`{}",
3521                                              path_name, msg));*/
3522                                 resolve_err!(self, expr.span, E0253,
3523                                              "unresolved name `{}`{}",
3524                                              path_name,
3525                                              msg);
3526                             }
3527                         }
3528                     }
3529                 }
3530
3531                 visit::walk_expr(self, expr);
3532             }
3533
3534             ExprStruct(ref path, _, _) => {
3535                 // Resolve the path to the structure it goes to. We don't
3536                 // check to ensure that the path is actually a structure; that
3537                 // is checked later during typeck.
3538                 match self.resolve_path(expr.id, path, 0, TypeNS, false) {
3539                     Some(definition) => self.record_def(expr.id, definition),
3540                     None => {
3541                         debug!("(resolving expression) didn't find struct def",);
3542                         /*let msg = format!("`{}` does not name a structure",
3543                                           path_names_to_string(path, 0));
3544                         self.resolve_error(path.span, &msg[..]);*/
3545                         resolve_err!(self, path.span, E0253,
3546                                      "`{}` does not name a structure",
3547                                      path_names_to_string(path, 0));
3548                     }
3549                 }
3550
3551                 visit::walk_expr(self, expr);
3552             }
3553
3554             ExprLoop(_, Some(label)) | ExprWhile(_, _, Some(label)) => {
3555                 self.with_label_rib(|this| {
3556                     let def_like = DlDef(DefLabel(expr.id));
3557
3558                     {
3559                         let rib = this.label_ribs.last_mut().unwrap();
3560                         let renamed = mtwt::resolve(label);
3561                         rib.bindings.insert(renamed, def_like);
3562                     }
3563
3564                     visit::walk_expr(this, expr);
3565                 })
3566             }
3567
3568             ExprBreak(Some(label)) | ExprAgain(Some(label)) => {
3569                 let renamed = mtwt::resolve(label);
3570                 match self.search_label(renamed) {
3571                     None => {
3572                         /*self.resolve_error(
3573                             expr.span,
3574                             &format!("use of undeclared label `{}`",
3575                                     token::get_ident(label)))*/
3576                         resolve_err!(self, expr.span, E0253,
3577                                      "use of undeclared label `{}`",
3578                                      token::get_ident(label))
3579                     }
3580                     Some(DlDef(def @ DefLabel(_))) => {
3581                         // Since this def is a label, it is never read.
3582                         self.record_def(expr.id, PathResolution {
3583                             base_def: def,
3584                             last_private: LastMod(AllPublic),
3585                             depth: 0
3586                         })
3587                     }
3588                     Some(_) => {
3589                         self.session.span_bug(expr.span,
3590                                               "label wasn't mapped to a \
3591                                                label def!")
3592                     }
3593                 }
3594             }
3595
3596             _ => {
3597                 visit::walk_expr(self, expr);
3598             }
3599         }
3600     }
3601
3602     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
3603         match expr.node {
3604             ExprField(_, ident) => {
3605                 // FIXME(#6890): Even though you can't treat a method like a
3606                 // field, we need to add any trait methods we find that match
3607                 // the field name so that we can do some nice error reporting
3608                 // later on in typeck.
3609                 let traits = self.get_traits_containing_item(ident.node.name);
3610                 self.trait_map.insert(expr.id, traits);
3611             }
3612             ExprMethodCall(ident, _, _) => {
3613                 debug!("(recording candidate traits for expr) recording \
3614                         traits for {}",
3615                        expr.id);
3616                 let traits = self.get_traits_containing_item(ident.node.name);
3617                 self.trait_map.insert(expr.id, traits);
3618             }
3619             _ => {
3620                 // Nothing to do.
3621             }
3622         }
3623     }
3624
3625     fn get_traits_containing_item(&mut self, name: Name) -> Vec<DefId> {
3626         debug!("(getting traits containing item) looking for '{}'",
3627                name);
3628
3629         fn add_trait_info(found_traits: &mut Vec<DefId>,
3630                           trait_def_id: DefId,
3631                           name: Name) {
3632             debug!("(adding trait info) found trait {}:{} for method '{}'",
3633                 trait_def_id.krate,
3634                 trait_def_id.node,
3635                 name);
3636             found_traits.push(trait_def_id);
3637         }
3638
3639         let mut found_traits = Vec::new();
3640         let mut search_module = self.current_module.clone();
3641         loop {
3642             // Look for the current trait.
3643             match self.current_trait_ref {
3644                 Some((trait_def_id, _)) => {
3645                     if self.trait_item_map.contains_key(&(name, trait_def_id)) {
3646                         add_trait_info(&mut found_traits, trait_def_id, name);
3647                     }
3648                 }
3649                 None => {} // Nothing to do.
3650             }
3651
3652             // Look for trait children.
3653             build_reduced_graph::populate_module_if_necessary(self, &search_module);
3654
3655             {
3656                 for (_, child_names) in search_module.children.borrow().iter() {
3657                     let def = match child_names.def_for_namespace(TypeNS) {
3658                         Some(def) => def,
3659                         None => continue
3660                     };
3661                     let trait_def_id = match def {
3662                         DefTrait(trait_def_id) => trait_def_id,
3663                         _ => continue,
3664                     };
3665                     if self.trait_item_map.contains_key(&(name, trait_def_id)) {
3666                         add_trait_info(&mut found_traits, trait_def_id, name);
3667                     }
3668                 }
3669             }
3670
3671             // Look for imports.
3672             for (_, import) in search_module.import_resolutions.borrow().iter() {
3673                 let target = match import.target_for_namespace(TypeNS) {
3674                     None => continue,
3675                     Some(target) => target,
3676                 };
3677                 let did = match target.bindings.def_for_namespace(TypeNS) {
3678                     Some(DefTrait(trait_def_id)) => trait_def_id,
3679                     Some(..) | None => continue,
3680                 };
3681                 if self.trait_item_map.contains_key(&(name, did)) {
3682                     add_trait_info(&mut found_traits, did, name);
3683                     let id = import.type_id;
3684                     self.used_imports.insert((id, TypeNS));
3685                     let trait_name = self.get_trait_name(did);
3686                     self.record_import_use(id, trait_name);
3687                     if let Some(DefId{krate: kid, ..}) = target.target_module.def_id.get() {
3688                         self.used_crates.insert(kid);
3689                     }
3690                 }
3691             }
3692
3693             match search_module.parent_link.clone() {
3694                 NoParentLink | ModuleParentLink(..) => break,
3695                 BlockParentLink(parent_module, _) => {
3696                     search_module = parent_module.upgrade().unwrap();
3697                 }
3698             }
3699         }
3700
3701         found_traits
3702     }
3703
3704     fn record_def(&mut self, node_id: NodeId, resolution: PathResolution) {
3705         debug!("(recording def) recording {:?} for {}", resolution, node_id);
3706         assert!(match resolution.last_private {LastImport{..} => false, _ => true},
3707                 "Import should only be used for `use` directives");
3708
3709         if let Some(prev_res) = self.def_map.borrow_mut().insert(node_id, resolution) {
3710             let span = self.ast_map.opt_span(node_id).unwrap_or(codemap::DUMMY_SP);
3711             self.session.span_bug(span, &format!("path resolved multiple times \
3712                                                   ({:?} before, {:?} now)",
3713                                                  prev_res, resolution));
3714         }
3715     }
3716
3717     fn enforce_default_binding_mode(&mut self,
3718                                         pat: &Pat,
3719                                         pat_binding_mode: BindingMode,
3720                                         descr: &str) {
3721         match pat_binding_mode {
3722             BindByValue(_) => {}
3723             BindByRef(..) => {
3724                 /*self.resolve_error(pat.span,
3725                                    &format!("cannot use `ref` binding mode \
3726                                             with {}",
3727                                            descr));*/
3728                 resolve_err!(self, pat.span, E0253,
3729                              "cannot use `ref` binding mode with {}",
3730                              descr);
3731             }
3732         }
3733     }
3734
3735     //
3736     // Diagnostics
3737     //
3738     // Diagnostics are not particularly efficient, because they're rarely
3739     // hit.
3740     //
3741
3742     #[allow(dead_code)]   // useful for debugging
3743     fn dump_module(&mut self, module_: Rc<Module>) {
3744         debug!("Dump of module `{}`:", module_to_string(&*module_));
3745
3746         debug!("Children:");
3747         build_reduced_graph::populate_module_if_necessary(self, &module_);
3748         for (&name, _) in module_.children.borrow().iter() {
3749             debug!("* {}", name);
3750         }
3751
3752         debug!("Import resolutions:");
3753         let import_resolutions = module_.import_resolutions.borrow();
3754         for (&name, import_resolution) in import_resolutions.iter() {
3755             let value_repr;
3756             match import_resolution.target_for_namespace(ValueNS) {
3757                 None => { value_repr = "".to_string(); }
3758                 Some(_) => {
3759                     value_repr = " value:?".to_string();
3760                     // FIXME #4954
3761                 }
3762             }
3763
3764             let type_repr;
3765             match import_resolution.target_for_namespace(TypeNS) {
3766                 None => { type_repr = "".to_string(); }
3767                 Some(_) => {
3768                     type_repr = " type:?".to_string();
3769                     // FIXME #4954
3770                 }
3771             }
3772
3773             debug!("* {}:{}{}", name, value_repr, type_repr);
3774         }
3775     }
3776 }
3777
3778
3779 fn names_to_string(names: &[Name]) -> String {
3780     let mut first = true;
3781     let mut result = String::new();
3782     for name in names {
3783         if first {
3784             first = false
3785         } else {
3786             result.push_str("::")
3787         }
3788         result.push_str(&token::get_name(*name));
3789     };
3790     result
3791 }
3792
3793 fn path_names_to_string(path: &Path, depth: usize) -> String {
3794     let names: Vec<ast::Name> = path.segments[..path.segments.len()-depth]
3795                                     .iter()
3796                                     .map(|seg| seg.identifier.name)
3797                                     .collect();
3798     names_to_string(&names[..])
3799 }
3800
3801 /// A somewhat inefficient routine to obtain the name of a module.
3802 fn module_to_string(module: &Module) -> String {
3803     let mut names = Vec::new();
3804
3805     fn collect_mod(names: &mut Vec<ast::Name>, module: &Module) {
3806         match module.parent_link {
3807             NoParentLink => {}
3808             ModuleParentLink(ref module, name) => {
3809                 names.push(name);
3810                 collect_mod(names, &*module.upgrade().unwrap());
3811             }
3812             BlockParentLink(ref module, _) => {
3813                 // danger, shouldn't be ident?
3814                 names.push(special_idents::opaque.name);
3815                 collect_mod(names, &*module.upgrade().unwrap());
3816             }
3817         }
3818     }
3819     collect_mod(&mut names, module);
3820
3821     if names.is_empty() {
3822         return "???".to_string();
3823     }
3824     names_to_string(&names.into_iter().rev().collect::<Vec<ast::Name>>())
3825 }
3826
3827
3828 pub struct CrateMap {
3829     pub def_map: DefMap,
3830     pub freevars: RefCell<FreevarMap>,
3831     pub export_map: ExportMap,
3832     pub trait_map: TraitMap,
3833     pub external_exports: ExternalExports,
3834     pub glob_map: Option<GlobMap>
3835 }
3836
3837 #[derive(PartialEq,Copy, Clone)]
3838 pub enum MakeGlobMap {
3839     Yes,
3840     No
3841 }
3842
3843 /// Entry point to crate resolution.
3844 pub fn resolve_crate<'a, 'tcx>(session: &'a Session,
3845                                ast_map: &'a ast_map::Map<'tcx>,
3846                                make_glob_map: MakeGlobMap)
3847                                -> CrateMap {
3848     let krate = ast_map.krate();
3849     let mut resolver = Resolver::new(session, ast_map, krate.span, make_glob_map);
3850
3851     build_reduced_graph::build_reduced_graph(&mut resolver, krate);
3852     session.abort_if_errors();
3853
3854     resolve_imports::resolve_imports(&mut resolver);
3855     session.abort_if_errors();
3856
3857     record_exports::record(&mut resolver);
3858     session.abort_if_errors();
3859
3860     resolver.resolve_crate(krate);
3861     session.abort_if_errors();
3862
3863     check_unused::check_crate(&mut resolver, krate);
3864
3865     CrateMap {
3866         def_map: resolver.def_map,
3867         freevars: resolver.freevars,
3868         export_map: resolver.export_map,
3869         trait_map: resolver.trait_map,
3870         external_exports: resolver.external_exports,
3871         glob_map: if resolver.make_glob_map {
3872                         Some(resolver.glob_map)
3873                     } else {
3874                         None
3875                     },
3876     }
3877 }
3878
3879 __build_diagnostic_array! { librustc_resolve, DIAGNOSTICS }