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