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