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