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 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  12       html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
  13       html_root_url = "https://doc.rust-lang.org/nightly/")]
  14 #![deny(warnings)]
  15
  16 #![feature(rustc_diagnostic_macros)]
  17
  18 #[macro_use]
  19 extern crate log;
  20 #[macro_use]
  21 extern crate syntax;
  22 extern crate syntax_pos;
  23 extern crate rustc_errors as errors;
  24 extern crate arena;
  25 #[macro_use]
  26 extern crate rustc;
  27 extern crate rustc_data_structures;
  28
  29 use self::Namespace::*;
  30 use self::TypeParameters::*;
  31 use self::RibKind::*;
  32
  33 use rustc::hir::map::{Definitions, DefCollector};
  34 use rustc::hir::{self, PrimTy, TyBool, TyChar, TyFloat, TyInt, TyUint, TyStr};
  35 use rustc::middle::cstore::{CrateStore, CrateLoader};
  36 use rustc::session::Session;
  37 use rustc::lint;
  38 use rustc::hir::def::*;
  39 use rustc::hir::def_id::{CRATE_DEF_INDEX, LOCAL_CRATE, DefId};
  40 use rustc::ty;
  41 use rustc::hir::{Freevar, FreevarMap, TraitCandidate, TraitMap, GlobMap};
  42 use rustc::util::nodemap::{NodeMap, NodeSet, FxHashMap, FxHashSet, DefIdMap};
  43
  44 use syntax::codemap::{dummy_spanned, respan, BytePos, CodeMap};
  45 use syntax::ext::hygiene::{Mark, MarkKind, SyntaxContext};
  46 use syntax::ast::{self, Name, NodeId, Ident, SpannedIdent, FloatTy, IntTy, UintTy};
  47 use syntax::ext::base::SyntaxExtension;
  48 use syntax::ext::base::Determinacy::{self, Determined, Undetermined};
  49 use syntax::ext::base::MacroKind;
  50 use syntax::symbol::{Symbol, keywords};
  51 use syntax::util::lev_distance::find_best_match_for_name;
  52
  53 use syntax::visit::{self, FnKind, Visitor};
  54 use syntax::attr;
  55 use syntax::ast::{Arm, BindingMode, Block, Crate, Expr, ExprKind};
  56 use syntax::ast::{FnDecl, ForeignItem, ForeignItemKind, GenericParam, Generics};
  57 use syntax::ast::{Item, ItemKind, ImplItem, ImplItemKind};
  58 use syntax::ast::{Label, Local, Mutability, Pat, PatKind, Path};
  59 use syntax::ast::{QSelf, TraitItemKind, TraitRef, Ty, TyKind};
  60 use syntax::feature_gate::{feature_err, emit_feature_err, GateIssue};
  61 use syntax::parse::token;
  62 use syntax::ptr::P;
  63
  64 use syntax_pos::{Span, DUMMY_SP, MultiSpan};
  65 use errors::{DiagnosticBuilder, DiagnosticId};
  66
  67 use std::cell::{Cell, RefCell};
  68 use std::cmp;
  69 use std::collections::BTreeSet;
  70 use std::fmt;
  71 use std::iter;
  72 use std::mem::replace;
  73 use rustc_data_structures::sync::Lrc;
  74
  75 use resolve_imports::{ImportDirective, ImportDirectiveSubclass, NameResolution, ImportResolver};
  76 use macros::{InvocationData, LegacyBinding, LegacyScope, MacroBinding};
  77
  78 // NB: This module needs to be declared first so diagnostics are
  79 // registered before they are used.
  80 mod diagnostics;
  81
  82 mod macros;
  83 mod check_unused;
  84 mod build_reduced_graph;
  85 mod resolve_imports;
  86
  87 /// A free importable items suggested in case of resolution failure.
  88 struct ImportSuggestion {
  89     path: Path,
  90 }
  91
  92 /// A field or associated item from self type suggested in case of resolution failure.
  93 enum AssocSuggestion {
  94     Field,
  95     MethodWithSelf,
  96     AssocItem,
  97 }
  98
  99 #[derive(Eq)]
 100 struct BindingError {
 101     name: Name,
 102     origin: BTreeSet<Span>,
 103     target: BTreeSet<Span>,
 104 }
 105
 106 impl PartialOrd for BindingError {
 107     fn partial_cmp(&self, other: &BindingError) -> Option<cmp::Ordering> {
 108         Some(self.cmp(other))
 109     }
 110 }
 111
 112 impl PartialEq for BindingError {
 113     fn eq(&self, other: &BindingError) -> bool {
 114         self.name == other.name
 115     }
 116 }
 117
 118 impl Ord for BindingError {
 119     fn cmp(&self, other: &BindingError) -> cmp::Ordering {
 120         self.name.cmp(&other.name)
 121     }
 122 }
 123
 124 enum ResolutionError<'a> {
 125     /// error E0401: can't use type parameters from outer function
 126     TypeParametersFromOuterFunction(Def),
 127     /// error E0403: the name is already used for a type parameter in this type parameter list
 128     NameAlreadyUsedInTypeParameterList(Name, &'a Span),
 129     /// error E0407: method is not a member of trait
 130     MethodNotMemberOfTrait(Name, &'a str),
 131     /// error E0437: type is not a member of trait
 132     TypeNotMemberOfTrait(Name, &'a str),
 133     /// error E0438: const is not a member of trait
 134     ConstNotMemberOfTrait(Name, &'a str),
 135     /// error E0408: variable `{}` is not bound in all patterns
 136     VariableNotBoundInPattern(&'a BindingError),
 137     /// error E0409: variable `{}` is bound in inconsistent ways within the same match arm
 138     VariableBoundWithDifferentMode(Name, Span),
 139     /// error E0415: identifier is bound more than once in this parameter list
 140     IdentifierBoundMoreThanOnceInParameterList(&'a str),
 141     /// error E0416: identifier is bound more than once in the same pattern
 142     IdentifierBoundMoreThanOnceInSamePattern(&'a str),
 143     /// error E0426: use of undeclared label
 144     UndeclaredLabel(&'a str, Option<Name>),
 145     /// error E0429: `self` imports are only allowed within a { } list
 146     SelfImportsOnlyAllowedWithin,
 147     /// error E0430: `self` import can only appear once in the list
 148     SelfImportCanOnlyAppearOnceInTheList,
 149     /// error E0431: `self` import can only appear in an import list with a non-empty prefix
 150     SelfImportOnlyInImportListWithNonEmptyPrefix,
 151     /// error E0432: unresolved import
 152     UnresolvedImport(Option<(Span, &'a str, &'a str)>),
 153     /// error E0433: failed to resolve
 154     FailedToResolve(&'a str),
 155     /// error E0434: can't capture dynamic environment in a fn item
 156     CannotCaptureDynamicEnvironmentInFnItem,
 157     /// error E0435: attempt to use a non-constant value in a constant
 158     AttemptToUseNonConstantValueInConstant,
 159     /// error E0530: X bindings cannot shadow Ys
 160     BindingShadowsSomethingUnacceptable(&'a str, Name, &'a NameBinding<'a>),
 161     /// error E0128: type parameters with a default cannot use forward declared identifiers
 162     ForwardDeclaredTyParam,
 163 }
 164
 165 fn resolve_error<'sess, 'a>(resolver: &'sess Resolver,
 166                             span: Span,
 167                             resolution_error: ResolutionError<'a>) {
 168     resolve_struct_error(resolver, span, resolution_error).emit();
 169 }
 170
 171 fn resolve_struct_error<'sess, 'a>(resolver: &'sess Resolver,
 172                                    span: Span,
 173                                    resolution_error: ResolutionError<'a>)
 174                                    -> DiagnosticBuilder<'sess> {
 175     match resolution_error {
 176         ResolutionError::TypeParametersFromOuterFunction(outer_def) => {
 177             let mut err = struct_span_err!(resolver.session,
 178                                            span,
 179                                            E0401,
 180                                            "can't use type parameters from outer function");
 181             err.span_label(span, "use of type variable from outer function");
 182
 183             let cm = resolver.session.codemap();
 184             match outer_def {
 185                 Def::SelfTy(_, maybe_impl_defid) => {
 186                     if let Some(impl_span) = maybe_impl_defid.map_or(None,
 187                             |def_id| resolver.definitions.opt_span(def_id)) {
 188                         err.span_label(reduce_impl_span_to_impl_keyword(cm, impl_span),
 189                                     "`Self` type implicitely declared here, on the `impl`");
 190                     }
 191                 },
 192                 Def::TyParam(typaram_defid) => {
 193                     if let Some(typaram_span) = resolver.definitions.opt_span(typaram_defid) {
 194                         err.span_label(typaram_span, "type variable from outer function");
 195                     }
 196                 },
 197                 Def::Mod(..) | Def::Struct(..) | Def::Union(..) | Def::Enum(..) | Def::Variant(..) |
 198                 Def::Trait(..) | Def::TyAlias(..) | Def::TyForeign(..) | Def::TraitAlias(..) |
 199                 Def::AssociatedTy(..) | Def::PrimTy(..) | Def::Fn(..) | Def::Const(..) |
 200                 Def::Static(..) | Def::StructCtor(..) | Def::VariantCtor(..) | Def::Method(..) |
 201                 Def::AssociatedConst(..) | Def::Local(..) | Def::Upvar(..) | Def::Label(..) |
 202                 Def::Macro(..) | Def::GlobalAsm(..) | Def::Err =>
 203                     bug!("TypeParametersFromOuterFunction should only be used with Def::SelfTy or \
 204                          Def::TyParam")
 205             }
 206
 207             // Try to retrieve the span of the function signature and generate a new message with
 208             // a local type parameter
 209             let sugg_msg = "try using a local type parameter instead";
 210             if let Some((sugg_span, new_snippet)) = generate_local_type_param_snippet(cm, span) {
 211                 // Suggest the modification to the user
 212                 err.span_suggestion(sugg_span,
 213                                     sugg_msg,
 214                                     new_snippet);
 215             } else if let Some(sp) = generate_fn_name_span(cm, span) {
 216                 err.span_label(sp, "try adding a local type parameter in this method instead");
 217             } else {
 218                 err.help("try using a local type parameter instead");
 219             }
 220
 221             err
 222         }
 223         ResolutionError::NameAlreadyUsedInTypeParameterList(name, first_use_span) => {
 224              let mut err = struct_span_err!(resolver.session,
 225                                             span,
 226                                             E0403,
 227                                             "the name `{}` is already used for a type parameter \
 228                                             in this type parameter list",
 229                                             name);
 230              err.span_label(span, "already used");
 231              err.span_label(first_use_span.clone(), format!("first use of `{}`", name));
 232              err
 233         }
 234         ResolutionError::MethodNotMemberOfTrait(method, trait_) => {
 235             let mut err = struct_span_err!(resolver.session,
 236                                            span,
 237                                            E0407,
 238                                            "method `{}` is not a member of trait `{}`",
 239                                            method,
 240                                            trait_);
 241             err.span_label(span, format!("not a member of trait `{}`", trait_));
 242             err
 243         }
 244         ResolutionError::TypeNotMemberOfTrait(type_, trait_) => {
 245             let mut err = struct_span_err!(resolver.session,
 246                              span,
 247                              E0437,
 248                              "type `{}` is not a member of trait `{}`",
 249                              type_,
 250                              trait_);
 251             err.span_label(span, format!("not a member of trait `{}`", trait_));
 252             err
 253         }
 254         ResolutionError::ConstNotMemberOfTrait(const_, trait_) => {
 255             let mut err = struct_span_err!(resolver.session,
 256                              span,
 257                              E0438,
 258                              "const `{}` is not a member of trait `{}`",
 259                              const_,
 260                              trait_);
 261             err.span_label(span, format!("not a member of trait `{}`", trait_));
 262             err
 263         }
 264         ResolutionError::VariableNotBoundInPattern(binding_error) => {
 265             let target_sp = binding_error.target.iter().map(|x| *x).collect::<Vec<_>>();
 266             let msp = MultiSpan::from_spans(target_sp.clone());
 267             let msg = format!("variable `{}` is not bound in all patterns", binding_error.name);
 268             let mut err = resolver.session.struct_span_err_with_code(
 269                 msp,
 270                 &msg,
 271                 DiagnosticId::Error("E0408".into()),
 272             );
 273             for sp in target_sp {
 274                 err.span_label(sp, format!("pattern doesn't bind `{}`", binding_error.name));
 275             }
 276             let origin_sp = binding_error.origin.iter().map(|x| *x).collect::<Vec<_>>();
 277             for sp in origin_sp {
 278                 err.span_label(sp, "variable not in all patterns");
 279             }
 280             err
 281         }
 282         ResolutionError::VariableBoundWithDifferentMode(variable_name,
 283                                                         first_binding_span) => {
 284             let mut err = struct_span_err!(resolver.session,
 285                              span,
 286                              E0409,
 287                              "variable `{}` is bound in inconsistent \
 288                              ways within the same match arm",
 289                              variable_name);
 290             err.span_label(span, "bound in different ways");
 291             err.span_label(first_binding_span, "first binding");
 292             err
 293         }
 294         ResolutionError::IdentifierBoundMoreThanOnceInParameterList(identifier) => {
 295             let mut err = struct_span_err!(resolver.session,
 296                              span,
 297                              E0415,
 298                              "identifier `{}` is bound more than once in this parameter list",
 299                              identifier);
 300             err.span_label(span, "used as parameter more than once");
 301             err
 302         }
 303         ResolutionError::IdentifierBoundMoreThanOnceInSamePattern(identifier) => {
 304             let mut err = struct_span_err!(resolver.session,
 305                              span,
 306                              E0416,
 307                              "identifier `{}` is bound more than once in the same pattern",
 308                              identifier);
 309             err.span_label(span, "used in a pattern more than once");
 310             err
 311         }
 312         ResolutionError::UndeclaredLabel(name, lev_candidate) => {
 313             let mut err = struct_span_err!(resolver.session,
 314                                            span,
 315                                            E0426,
 316                                            "use of undeclared label `{}`",
 317                                            name);
 318             if let Some(lev_candidate) = lev_candidate {
 319                 err.span_label(span, format!("did you mean `{}`?", lev_candidate));
 320             } else {
 321                 err.span_label(span, format!("undeclared label `{}`", name));
 322             }
 323             err
 324         }
 325         ResolutionError::SelfImportsOnlyAllowedWithin => {
 326             struct_span_err!(resolver.session,
 327                              span,
 328                              E0429,
 329                              "{}",
 330                              "`self` imports are only allowed within a { } list")
 331         }
 332         ResolutionError::SelfImportCanOnlyAppearOnceInTheList => {
 333             let mut err = struct_span_err!(resolver.session, span, E0430,
 334                                            "`self` import can only appear once in an import list");
 335             err.span_label(span, "can only appear once in an import list");
 336             err
 337         }
 338         ResolutionError::SelfImportOnlyInImportListWithNonEmptyPrefix => {
 339             let mut err = struct_span_err!(resolver.session, span, E0431,
 340                                            "`self` import can only appear in an import list with \
 341                                             a non-empty prefix");
 342             err.span_label(span, "can only appear in an import list with a non-empty prefix");
 343             err
 344         }
 345         ResolutionError::UnresolvedImport(name) => {
 346             let (span, msg) = match name {
 347                 Some((sp, n, _)) => (sp, format!("unresolved import `{}`", n)),
 348                 None => (span, "unresolved import".to_owned()),
 349             };
 350             let mut err = struct_span_err!(resolver.session, span, E0432, "{}", msg);
 351             if let Some((_, _, p)) = name {
 352                 err.span_label(span, p);
 353             }
 354             err
 355         }
 356         ResolutionError::FailedToResolve(msg) => {
 357             let mut err = struct_span_err!(resolver.session, span, E0433,
 358                                            "failed to resolve. {}", msg);
 359             err.span_label(span, msg);
 360             err
 361         }
 362         ResolutionError::CannotCaptureDynamicEnvironmentInFnItem => {
 363             let mut err = struct_span_err!(resolver.session,
 364                                            span,
 365                                            E0434,
 366                                            "{}",
 367                                            "can't capture dynamic environment in a fn item");
 368             err.help("use the `|| { ... }` closure form instead");
 369             err
 370         }
 371         ResolutionError::AttemptToUseNonConstantValueInConstant => {
 372             let mut err = struct_span_err!(resolver.session, span, E0435,
 373                                            "attempt to use a non-constant value in a constant");
 374             err.span_label(span, "non-constant value");
 375             err
 376         }
 377         ResolutionError::BindingShadowsSomethingUnacceptable(what_binding, name, binding) => {
 378             let shadows_what = PathResolution::new(binding.def()).kind_name();
 379             let mut err = struct_span_err!(resolver.session,
 380                                            span,
 381                                            E0530,
 382                                            "{}s cannot shadow {}s", what_binding, shadows_what);
 383             err.span_label(span, format!("cannot be named the same as a {}", shadows_what));
 384             let participle = if binding.is_import() { "imported" } else { "defined" };
 385             let msg = format!("a {} `{}` is {} here", shadows_what, name, participle);
 386             err.span_label(binding.span, msg);
 387             err
 388         }
 389         ResolutionError::ForwardDeclaredTyParam => {
 390             let mut err = struct_span_err!(resolver.session, span, E0128,
 391                                            "type parameters with a default cannot use \
 392                                             forward declared identifiers");
 393             err.span_label(span, format!("defaulted type parameters cannot be forward declared"));
 394             err
 395         }
 396     }
 397 }
 398
 399 /// Adjust the impl span so that just the `impl` keyword is taken by removing
 400 /// everything after `<` (`"impl<T> Iterator for A<T> {}" -> "impl"`) and
 401 /// everything after the first whitespace (`"impl Iterator for A" -> "impl"`)
 402 ///
 403 /// Attention: The method used is very fragile since it essentially duplicates the work of the
 404 /// parser. If you need to use this function or something similar, please consider updating the
 405 /// codemap functions and this function to something more robust.
 406 fn reduce_impl_span_to_impl_keyword(cm: &CodeMap, impl_span: Span) -> Span {
 407     let impl_span = cm.span_until_char(impl_span, '<');
 408     let impl_span = cm.span_until_whitespace(impl_span);
 409     impl_span
 410 }
 411
 412 fn generate_fn_name_span(cm: &CodeMap, span: Span) -> Option<Span> {
 413     let prev_span = cm.span_extend_to_prev_str(span, "fn", true);
 414     cm.span_to_snippet(prev_span).map(|snippet| {
 415         let len = snippet.find(|c: char| !c.is_alphanumeric() && c != '_')
 416             .expect("no label after fn");
 417         prev_span.with_hi(BytePos(prev_span.lo().0 + len as u32))
 418     }).ok()
 419 }
 420
 421 /// Take the span of a type parameter in a function signature and try to generate a span for the
 422 /// function name (with generics) and a new snippet for this span with the pointed type parameter as
 423 /// a new local type parameter.
 424 ///
 425 /// For instance:
 426 /// ```
 427 /// // Given span
 428 /// fn my_function(param: T)
 429 ///                       ^ Original span
 430 ///
 431 /// // Result
 432 /// fn my_function(param: T)
 433 ///    ^^^^^^^^^^^ Generated span with snippet `my_function<T>`
 434 /// ```
 435 ///
 436 /// Attention: The method used is very fragile since it essentially duplicates the work of the
 437 /// parser. If you need to use this function or something similar, please consider updating the
 438 /// codemap functions and this function to something more robust.
 439 fn generate_local_type_param_snippet(cm: &CodeMap, span: Span) -> Option<(Span, String)> {
 440     // Try to extend the span to the previous "fn" keyword to retrieve the function
 441     // signature
 442     let sugg_span = cm.span_extend_to_prev_str(span, "fn", false);
 443     if sugg_span != span {
 444         if let Ok(snippet) = cm.span_to_snippet(sugg_span) {
 445             // Consume the function name
 446             let mut offset = snippet.find(|c: char| !c.is_alphanumeric() && c != '_')
 447                 .expect("no label after fn");
 448
 449             // Consume the generics part of the function signature
 450             let mut bracket_counter = 0;
 451             let mut last_char = None;
 452             for c in snippet[offset..].chars() {
 453                 match c {
 454                     '<' => bracket_counter += 1,
 455                     '>' => bracket_counter -= 1,
 456                     '(' => if bracket_counter == 0 { break; }
 457                     _ => {}
 458                 }
 459                 offset += c.len_utf8();
 460                 last_char = Some(c);
 461             }
 462
 463             // Adjust the suggestion span to encompass the function name with its generics
 464             let sugg_span = sugg_span.with_hi(BytePos(sugg_span.lo().0 + offset as u32));
 465
 466             // Prepare the new suggested snippet to append the type parameter that triggered
 467             // the error in the generics of the function signature
 468             let mut new_snippet = if last_char == Some('>') {
 469                 format!("{}, ", &snippet[..(offset - '>'.len_utf8())])
 470             } else {
 471                 format!("{}<", &snippet[..offset])
 472             };
 473             new_snippet.push_str(&cm.span_to_snippet(span).unwrap_or("T".to_string()));
 474             new_snippet.push('>');
 475
 476             return Some((sugg_span, new_snippet));
 477         }
 478     }
 479
 480     None
 481 }
 482
 483 #[derive(Copy, Clone, Debug)]
 484 struct BindingInfo {
 485     span: Span,
 486     binding_mode: BindingMode,
 487 }
 488
 489 // Map from the name in a pattern to its binding mode.
 490 type BindingMap = FxHashMap<Ident, BindingInfo>;
 491
 492 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 493 enum PatternSource {
 494     Match,
 495     IfLet,
 496     WhileLet,
 497     Let,
 498     For,
 499     FnParam,
 500 }
 501
 502 impl PatternSource {
 503     fn descr(self) -> &'static str {
 504         match self {
 505             PatternSource::Match => "match binding",
 506             PatternSource::IfLet => "if let binding",
 507             PatternSource::WhileLet => "while let binding",
 508             PatternSource::Let => "let binding",
 509             PatternSource::For => "for binding",
 510             PatternSource::FnParam => "function parameter",
 511         }
 512     }
 513 }
 514
 515 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 516 enum AliasPossibility {
 517     No,
 518     Maybe,
 519 }
 520
 521 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 522 enum PathSource<'a> {
 523     // Type paths `Path`.
 524     Type,
 525     // Trait paths in bounds or impls.
 526     Trait(AliasPossibility),
 527     // Expression paths `path`, with optional parent context.
 528     Expr(Option<&'a Expr>),
 529     // Paths in path patterns `Path`.
 530     Pat,
 531     // Paths in struct expressions and patterns `Path { .. }`.
 532     Struct,
 533     // Paths in tuple struct patterns `Path(..)`.
 534     TupleStruct,
 535     // `m::A::B` in `<T as m::A>::B::C`.
 536     TraitItem(Namespace),
 537     // Path in `pub(path)`
 538     Visibility,
 539     // Path in `use a::b::{...};`
 540     ImportPrefix,
 541 }
 542
 543 impl<'a> PathSource<'a> {
 544     fn namespace(self) -> Namespace {
 545         match self {
 546             PathSource::Type | PathSource::Trait(_) | PathSource::Struct |
 547             PathSource::Visibility | PathSource::ImportPrefix => TypeNS,
 548             PathSource::Expr(..) | PathSource::Pat | PathSource::TupleStruct => ValueNS,
 549             PathSource::TraitItem(ns) => ns,
 550         }
 551     }
 552
 553     fn global_by_default(self) -> bool {
 554         match self {
 555             PathSource::Visibility | PathSource::ImportPrefix => true,
 556             PathSource::Type | PathSource::Expr(..) | PathSource::Pat |
 557             PathSource::Struct | PathSource::TupleStruct |
 558             PathSource::Trait(_) | PathSource::TraitItem(..) => false,
 559         }
 560     }
 561
 562     fn defer_to_typeck(self) -> bool {
 563         match self {
 564             PathSource::Type | PathSource::Expr(..) | PathSource::Pat |
 565             PathSource::Struct | PathSource::TupleStruct => true,
 566             PathSource::Trait(_) | PathSource::TraitItem(..) |
 567             PathSource::Visibility | PathSource::ImportPrefix => false,
 568         }
 569     }
 570
 571     fn descr_expected(self) -> &'static str {
 572         match self {
 573             PathSource::Type => "type",
 574             PathSource::Trait(_) => "trait",
 575             PathSource::Pat => "unit struct/variant or constant",
 576             PathSource::Struct => "struct, variant or union type",
 577             PathSource::TupleStruct => "tuple struct/variant",
 578             PathSource::Visibility => "module",
 579             PathSource::ImportPrefix => "module or enum",
 580             PathSource::TraitItem(ns) => match ns {
 581                 TypeNS => "associated type",
 582                 ValueNS => "method or associated constant",
 583                 MacroNS => bug!("associated macro"),
 584             },
 585             PathSource::Expr(parent) => match parent.map(|p| &p.node) {
 586                 // "function" here means "anything callable" rather than `Def::Fn`,
 587                 // this is not precise but usually more helpful than just "value".
 588                 Some(&ExprKind::Call(..)) => "function",
 589                 _ => "value",
 590             },
 591         }
 592     }
 593
 594     fn is_expected(self, def: Def) -> bool {
 595         match self {
 596             PathSource::Type => match def {
 597                 Def::Struct(..) | Def::Union(..) | Def::Enum(..) |
 598                 Def::Trait(..) | Def::TyAlias(..) | Def::AssociatedTy(..) |
 599                 Def::PrimTy(..) | Def::TyParam(..) | Def::SelfTy(..) |
 600                 Def::TyForeign(..) => true,
 601                 _ => false,
 602             },
 603             PathSource::Trait(AliasPossibility::No) => match def {
 604                 Def::Trait(..) => true,
 605                 _ => false,
 606             },
 607             PathSource::Trait(AliasPossibility::Maybe) => match def {
 608                 Def::Trait(..) => true,
 609                 Def::TraitAlias(..) => true,
 610                 _ => false,
 611             },
 612             PathSource::Expr(..) => match def {
 613                 Def::StructCtor(_, CtorKind::Const) | Def::StructCtor(_, CtorKind::Fn) |
 614                 Def::VariantCtor(_, CtorKind::Const) | Def::VariantCtor(_, CtorKind::Fn) |
 615                 Def::Const(..) | Def::Static(..) | Def::Local(..) | Def::Upvar(..) |
 616                 Def::Fn(..) | Def::Method(..) | Def::AssociatedConst(..) => true,
 617                 _ => false,
 618             },
 619             PathSource::Pat => match def {
 620                 Def::StructCtor(_, CtorKind::Const) |
 621                 Def::VariantCtor(_, CtorKind::Const) |
 622                 Def::Const(..) | Def::AssociatedConst(..) => true,
 623                 _ => false,
 624             },
 625             PathSource::TupleStruct => match def {
 626                 Def::StructCtor(_, CtorKind::Fn) | Def::VariantCtor(_, CtorKind::Fn) => true,
 627                 _ => false,
 628             },
 629             PathSource::Struct => match def {
 630                 Def::Struct(..) | Def::Union(..) | Def::Variant(..) |
 631                 Def::TyAlias(..) | Def::AssociatedTy(..) | Def::SelfTy(..) => true,
 632                 _ => false,
 633             },
 634             PathSource::TraitItem(ns) => match def {
 635                 Def::AssociatedConst(..) | Def::Method(..) if ns == ValueNS => true,
 636                 Def::AssociatedTy(..) if ns == TypeNS => true,
 637                 _ => false,
 638             },
 639             PathSource::ImportPrefix => match def {
 640                 Def::Mod(..) | Def::Enum(..) => true,
 641                 _ => false,
 642             },
 643             PathSource::Visibility => match def {
 644                 Def::Mod(..) => true,
 645                 _ => false,
 646             },
 647         }
 648     }
 649
 650     fn error_code(self, has_unexpected_resolution: bool) -> &'static str {
 651         __diagnostic_used!(E0404);
 652         __diagnostic_used!(E0405);
 653         __diagnostic_used!(E0412);
 654         __diagnostic_used!(E0422);
 655         __diagnostic_used!(E0423);
 656         __diagnostic_used!(E0425);
 657         __diagnostic_used!(E0531);
 658         __diagnostic_used!(E0532);
 659         __diagnostic_used!(E0573);
 660         __diagnostic_used!(E0574);
 661         __diagnostic_used!(E0575);
 662         __diagnostic_used!(E0576);
 663         __diagnostic_used!(E0577);
 664         __diagnostic_used!(E0578);
 665         match (self, has_unexpected_resolution) {
 666             (PathSource::Trait(_), true) => "E0404",
 667             (PathSource::Trait(_), false) => "E0405",
 668             (PathSource::Type, true) => "E0573",
 669             (PathSource::Type, false) => "E0412",
 670             (PathSource::Struct, true) => "E0574",
 671             (PathSource::Struct, false) => "E0422",
 672             (PathSource::Expr(..), true) => "E0423",
 673             (PathSource::Expr(..), false) => "E0425",
 674             (PathSource::Pat, true) | (PathSource::TupleStruct, true) => "E0532",
 675             (PathSource::Pat, false) | (PathSource::TupleStruct, false) => "E0531",
 676             (PathSource::TraitItem(..), true) => "E0575",
 677             (PathSource::TraitItem(..), false) => "E0576",
 678             (PathSource::Visibility, true) | (PathSource::ImportPrefix, true) => "E0577",
 679             (PathSource::Visibility, false) | (PathSource::ImportPrefix, false) => "E0578",
 680         }
 681     }
 682 }
 683
 684 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 685 pub enum Namespace {
 686     TypeNS,
 687     ValueNS,
 688     MacroNS,
 689 }
 690
 691 #[derive(Clone, Default, Debug)]
 692 pub struct PerNS<T> {
 693     value_ns: T,
 694     type_ns: T,
 695     macro_ns: Option<T>,
 696 }
 697
 698 impl<T> ::std::ops::Index<Namespace> for PerNS<T> {
 699     type Output = T;
 700     fn index(&self, ns: Namespace) -> &T {
 701         match ns {
 702             ValueNS => &self.value_ns,
 703             TypeNS => &self.type_ns,
 704             MacroNS => self.macro_ns.as_ref().unwrap(),
 705         }
 706     }
 707 }
 708
 709 impl<T> ::std::ops::IndexMut<Namespace> for PerNS<T> {
 710     fn index_mut(&mut self, ns: Namespace) -> &mut T {
 711         match ns {
 712             ValueNS => &mut self.value_ns,
 713             TypeNS => &mut self.type_ns,
 714             MacroNS => self.macro_ns.as_mut().unwrap(),
 715         }
 716     }
 717 }
 718
 719 struct UsePlacementFinder {
 720     target_module: NodeId,
 721     span: Option<Span>,
 722     found_use: bool,
 723 }
 724
 725 impl UsePlacementFinder {
 726     fn check(krate: &Crate, target_module: NodeId) -> (Option<Span>, bool) {
 727         let mut finder = UsePlacementFinder {
 728             target_module,
 729             span: None,
 730             found_use: false,
 731         };
 732         visit::walk_crate(&mut finder, krate);
 733         (finder.span, finder.found_use)
 734     }
 735 }
 736
 737 impl<'tcx> Visitor<'tcx> for UsePlacementFinder {
 738     fn visit_mod(
 739         &mut self,
 740         module: &'tcx ast::Mod,
 741         _: Span,
 742         _: &[ast::Attribute],
 743         node_id: NodeId,
 744     ) {
 745         if self.span.is_some() {
 746             return;
 747         }
 748         if node_id != self.target_module {
 749             visit::walk_mod(self, module);
 750             return;
 751         }
 752         // find a use statement
 753         for item in &module.items {
 754             match item.node {
 755                 ItemKind::Use(..) => {
 756                     // don't suggest placing a use before the prelude
 757                     // import or other generated ones
 758                     if item.span.ctxt().outer().expn_info().is_none() {
 759                         self.span = Some(item.span.with_hi(item.span.lo()));
 760                         self.found_use = true;
 761                         return;
 762                     }
 763                 },
 764                 // don't place use before extern crate
 765                 ItemKind::ExternCrate(_) => {}
 766                 // but place them before the first other item
 767                 _ => if self.span.map_or(true, |span| item.span < span ) {
 768                     if item.span.ctxt().outer().expn_info().is_none() {
 769                         // don't insert between attributes and an item
 770                         if item.attrs.is_empty() {
 771                             self.span = Some(item.span.with_hi(item.span.lo()));
 772                         } else {
 773                             // find the first attribute on the item
 774                             for attr in &item.attrs {
 775                                 if self.span.map_or(true, |span| attr.span < span) {
 776                                     self.span = Some(attr.span.with_hi(attr.span.lo()));
 777                                 }
 778                             }
 779                         }
 780                     }
 781                 },
 782             }
 783         }
 784     }
 785 }
 786
 787 impl<'a, 'tcx> Visitor<'tcx> for Resolver<'a> {
 788     fn visit_item(&mut self, item: &'tcx Item) {
 789         self.resolve_item(item);
 790     }
 791     fn visit_arm(&mut self, arm: &'tcx Arm) {
 792         self.resolve_arm(arm);
 793     }
 794     fn visit_block(&mut self, block: &'tcx Block) {
 795         self.resolve_block(block);
 796     }
 797     fn visit_expr(&mut self, expr: &'tcx Expr) {
 798         self.resolve_expr(expr, None);
 799     }
 800     fn visit_local(&mut self, local: &'tcx Local) {
 801         self.resolve_local(local);
 802     }
 803     fn visit_ty(&mut self, ty: &'tcx Ty) {
 804         match ty.node {
 805             TyKind::Path(ref qself, ref path) => {
 806                 self.smart_resolve_path(ty.id, qself.as_ref(), path, PathSource::Type);
 807             }
 808             TyKind::ImplicitSelf => {
 809                 let self_ty = keywords::SelfType.ident();
 810                 let def = self.resolve_ident_in_lexical_scope(self_ty, TypeNS, true, ty.span)
 811                               .map_or(Def::Err, |d| d.def());
 812                 self.record_def(ty.id, PathResolution::new(def));
 813             }
 814             TyKind::Array(ref element, ref length) => {
 815                 self.visit_ty(element);
 816                 self.with_constant_rib(|this| {
 817                     this.visit_expr(length);
 818                 });
 819                 return;
 820             }
 821             _ => (),
 822         }
 823         visit::walk_ty(self, ty);
 824     }
 825     fn visit_poly_trait_ref(&mut self,
 826                             tref: &'tcx ast::PolyTraitRef,
 827                             m: &'tcx ast::TraitBoundModifier) {
 828         self.smart_resolve_path(tref.trait_ref.ref_id, None,
 829                                 &tref.trait_ref.path, PathSource::Trait(AliasPossibility::Maybe));
 830         visit::walk_poly_trait_ref(self, tref, m);
 831     }
 832     fn visit_variant(&mut self,
 833                      variant: &'tcx ast::Variant,
 834                      generics: &'tcx Generics,
 835                      item_id: ast::NodeId) {
 836         if let Some(ref dis_expr) = variant.node.disr_expr {
 837             // resolve the discriminator expr as a constant
 838             self.with_constant_rib(|this| {
 839                 this.visit_expr(dis_expr);
 840             });
 841         }
 842
 843         // `visit::walk_variant` without the discriminant expression.
 844         self.visit_variant_data(&variant.node.data,
 845                                 variant.node.name,
 846                                 generics,
 847                                 item_id,
 848                                 variant.span);
 849     }
 850     fn visit_foreign_item(&mut self, foreign_item: &'tcx ForeignItem) {
 851         let type_parameters = match foreign_item.node {
 852             ForeignItemKind::Fn(_, ref generics) => {
 853                 HasTypeParameters(generics, ItemRibKind)
 854             }
 855             ForeignItemKind::Static(..) => NoTypeParameters,
 856             ForeignItemKind::Ty => NoTypeParameters,
 857         };
 858         self.with_type_parameter_rib(type_parameters, |this| {
 859             visit::walk_foreign_item(this, foreign_item);
 860         });
 861     }
 862     fn visit_fn(&mut self,
 863                 function_kind: FnKind<'tcx>,
 864                 declaration: &'tcx FnDecl,
 865                 _: Span,
 866                 node_id: NodeId) {
 867         let rib_kind = match function_kind {
 868             FnKind::ItemFn(..) => {
 869                 ItemRibKind
 870             }
 871             FnKind::Method(_, _, _, _) => {
 872                 TraitOrImplItemRibKind
 873             }
 874             FnKind::Closure(_) => ClosureRibKind(node_id),
 875         };
 876
 877         // Create a value rib for the function.
 878         self.ribs[ValueNS].push(Rib::new(rib_kind));
 879
 880         // Create a label rib for the function.
 881         self.label_ribs.push(Rib::new(rib_kind));
 882
 883         // Add each argument to the rib.
 884         let mut bindings_list = FxHashMap();
 885         for argument in &declaration.inputs {
 886             self.resolve_pattern(&argument.pat, PatternSource::FnParam, &mut bindings_list);
 887
 888             self.visit_ty(&argument.ty);
 889
 890             debug!("(resolving function) recorded argument");
 891         }
 892         visit::walk_fn_ret_ty(self, &declaration.output);
 893
 894         // Resolve the function body.
 895         match function_kind {
 896             FnKind::ItemFn(.., body) |
 897             FnKind::Method(.., body) => {
 898                 self.visit_block(body);
 899             }
 900             FnKind::Closure(body) => {
 901                 self.visit_expr(body);
 902             }
 903         };
 904
 905         debug!("(resolving function) leaving function");
 906
 907         self.label_ribs.pop();
 908         self.ribs[ValueNS].pop();
 909     }
 910     fn visit_generics(&mut self, generics: &'tcx Generics) {
 911         // For type parameter defaults, we have to ban access
 912         // to following type parameters, as the Substs can only
 913         // provide previous type parameters as they're built.
 914         let mut default_ban_rib = Rib::new(ForwardTyParamBanRibKind);
 915         default_ban_rib.bindings.extend(generics.params.iter()
 916             .filter_map(|p| if let GenericParam::Type(ref tp) = *p { Some(tp) } else { None })
 917             .skip_while(|p| p.default.is_none())
 918             .map(|p| (Ident::with_empty_ctxt(p.ident.name), Def::Err)));
 919
 920         for param in &generics.params {
 921             match *param {
 922                 GenericParam::Lifetime(_) => self.visit_generic_param(param),
 923                 GenericParam::Type(ref ty_param) => {
 924                     for bound in &ty_param.bounds {
 925                         self.visit_ty_param_bound(bound);
 926                     }
 927
 928                     if let Some(ref ty) = ty_param.default {
 929                         self.ribs[TypeNS].push(default_ban_rib);
 930                         self.visit_ty(ty);
 931                         default_ban_rib = self.ribs[TypeNS].pop().unwrap();
 932                     }
 933
 934                     // Allow all following defaults to refer to this type parameter.
 935                     default_ban_rib.bindings.remove(&Ident::with_empty_ctxt(ty_param.ident.name));
 936                 }
 937             }
 938         }
 939         for p in &generics.where_clause.predicates { self.visit_where_predicate(p); }
 940     }
 941 }
 942
 943 #[derive(Copy, Clone)]
 944 enum TypeParameters<'a, 'b> {
 945     NoTypeParameters,
 946     HasTypeParameters(// Type parameters.
 947                       &'b Generics,
 948
 949                       // The kind of the rib used for type parameters.
 950                       RibKind<'a>),
 951 }
 952
 953 // The rib kind controls the translation of local
 954 // definitions (`Def::Local`) to upvars (`Def::Upvar`).
 955 #[derive(Copy, Clone, Debug)]
 956 enum RibKind<'a> {
 957     // No translation needs to be applied.
 958     NormalRibKind,
 959
 960     // We passed through a closure scope at the given node ID.
 961     // Translate upvars as appropriate.
 962     ClosureRibKind(NodeId /* func id */),
 963
 964     // We passed through an impl or trait and are now in one of its
 965     // methods or associated types. Allow references to ty params that impl or trait
 966     // binds. Disallow any other upvars (including other ty params that are
 967     // upvars).
 968     TraitOrImplItemRibKind,
 969
 970     // We passed through an item scope. Disallow upvars.
 971     ItemRibKind,
 972
 973     // We're in a constant item. Can't refer to dynamic stuff.
 974     ConstantItemRibKind,
 975
 976     // We passed through a module.
 977     ModuleRibKind(Module<'a>),
 978
 979     // We passed through a `macro_rules!` statement
 980     MacroDefinition(DefId),
 981
 982     // All bindings in this rib are type parameters that can't be used
 983     // from the default of a type parameter because they're not declared
 984     // before said type parameter. Also see the `visit_generics` override.
 985     ForwardTyParamBanRibKind,
 986 }
 987
 988 /// One local scope.
 989 #[derive(Debug)]
 990 struct Rib<'a> {
 991     bindings: FxHashMap<Ident, Def>,
 992     kind: RibKind<'a>,
 993 }
 994
 995 impl<'a> Rib<'a> {
 996     fn new(kind: RibKind<'a>) -> Rib<'a> {
 997         Rib {
 998             bindings: FxHashMap(),
 999             kind,
1000         }
1001     }
1002 }
1003
1004 enum LexicalScopeBinding<'a> {
1005     Item(&'a NameBinding<'a>),
1006     Def(Def),
1007 }
1008
1009 impl<'a> LexicalScopeBinding<'a> {
1010     fn item(self) -> Option<&'a NameBinding<'a>> {
1011         match self {
1012             LexicalScopeBinding::Item(binding) => Some(binding),
1013             _ => None,
1014         }
1015     }
1016
1017     fn def(self) -> Def {
1018         match self {
1019             LexicalScopeBinding::Item(binding) => binding.def(),
1020             LexicalScopeBinding::Def(def) => def,
1021         }
1022     }
1023 }
1024
1025 #[derive(Clone, Debug)]
1026 enum PathResult<'a> {
1027     Module(Module<'a>),
1028     NonModule(PathResolution),
1029     Indeterminate,
1030     Failed(Span, String, bool /* is the error from the last segment? */),
1031 }
1032
1033 enum ModuleKind {
1034     Block(NodeId),
1035     Def(Def, Name),
1036 }
1037
1038 /// One node in the tree of modules.
1039 pub struct ModuleData<'a> {
1040     parent: Option<Module<'a>>,
1041     kind: ModuleKind,
1042
1043     // The def id of the closest normal module (`mod`) ancestor (including this module).
1044     normal_ancestor_id: DefId,
1045
1046     resolutions: RefCell<FxHashMap<(Ident, Namespace), &'a RefCell<NameResolution<'a>>>>,
1047     legacy_macro_resolutions: RefCell<Vec<(Mark, Ident, Span, MacroKind)>>,
1048     macro_resolutions: RefCell<Vec<(Box<[Ident]>, Span)>>,
1049
1050     // Macro invocations that can expand into items in this module.
1051     unresolved_invocations: RefCell<FxHashSet<Mark>>,
1052
1053     no_implicit_prelude: bool,
1054
1055     glob_importers: RefCell<Vec<&'a ImportDirective<'a>>>,
1056     globs: RefCell<Vec<&'a ImportDirective<'a>>>,
1057
1058     // Used to memoize the traits in this module for faster searches through all traits in scope.
1059     traits: RefCell<Option<Box<[(Ident, &'a NameBinding<'a>)]>>>,
1060
1061     // Whether this module is populated. If not populated, any attempt to
1062     // access the children must be preceded with a
1063     // `populate_module_if_necessary` call.
1064     populated: Cell<bool>,
1065
1066     /// Span of the module itself. Used for error reporting.
1067     span: Span,
1068
1069     expansion: Mark,
1070 }
1071
1072 type Module<'a> = &'a ModuleData<'a>;
1073
1074 impl<'a> ModuleData<'a> {
1075     fn new(parent: Option<Module<'a>>,
1076            kind: ModuleKind,
1077            normal_ancestor_id: DefId,
1078            expansion: Mark,
1079            span: Span) -> Self {
1080         ModuleData {
1081             parent,
1082             kind,
1083             normal_ancestor_id,
1084             resolutions: RefCell::new(FxHashMap()),
1085             legacy_macro_resolutions: RefCell::new(Vec::new()),
1086             macro_resolutions: RefCell::new(Vec::new()),
1087             unresolved_invocations: RefCell::new(FxHashSet()),
1088             no_implicit_prelude: false,
1089             glob_importers: RefCell::new(Vec::new()),
1090             globs: RefCell::new(Vec::new()),
1091             traits: RefCell::new(None),
1092             populated: Cell::new(normal_ancestor_id.is_local()),
1093             span,
1094             expansion,
1095         }
1096     }
1097
1098     fn for_each_child<F: FnMut(Ident, Namespace, &'a NameBinding<'a>)>(&self, mut f: F) {
1099         for (&(ident, ns), name_resolution) in self.resolutions.borrow().iter() {
1100             name_resolution.borrow().binding.map(|binding| f(ident, ns, binding));
1101         }
1102     }
1103
1104     fn for_each_child_stable<F: FnMut(Ident, Namespace, &'a NameBinding<'a>)>(&self, mut f: F) {
1105         let resolutions = self.resolutions.borrow();
1106         let mut resolutions = resolutions.iter().map(|(&(ident, ns), &resolution)| {
1107                                                     // Pre-compute keys for sorting
1108                                                     (ident.name.as_str(), ns, ident, resolution)
1109                                                 })
1110                                                 .collect::<Vec<_>>();
1111         resolutions.sort_unstable_by_key(|&(str, ns, ..)| (str, ns));
1112         for &(_, ns, ident, resolution) in resolutions.iter() {
1113             resolution.borrow().binding.map(|binding| f(ident, ns, binding));
1114         }
1115     }
1116
1117     fn def(&self) -> Option<Def> {
1118         match self.kind {
1119             ModuleKind::Def(def, _) => Some(def),
1120             _ => None,
1121         }
1122     }
1123
1124     fn def_id(&self) -> Option<DefId> {
1125         self.def().as_ref().map(Def::def_id)
1126     }
1127
1128     // `self` resolves to the first module ancestor that `is_normal`.
1129     fn is_normal(&self) -> bool {
1130         match self.kind {
1131             ModuleKind::Def(Def::Mod(_), _) => true,
1132             _ => false,
1133         }
1134     }
1135
1136     fn is_trait(&self) -> bool {
1137         match self.kind {
1138             ModuleKind::Def(Def::Trait(_), _) => true,
1139             _ => false,
1140         }
1141     }
1142
1143     fn is_local(&self) -> bool {
1144         self.normal_ancestor_id.is_local()
1145     }
1146
1147     fn nearest_item_scope(&'a self) -> Module<'a> {
1148         if self.is_trait() { self.parent.unwrap() } else { self }
1149     }
1150 }
1151
1152 impl<'a> fmt::Debug for ModuleData<'a> {
1153     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1154         write!(f, "{:?}", self.def())
1155     }
1156 }
1157
1158 // Records a possibly-private value, type, or module definition.
1159 #[derive(Clone, Debug)]
1160 pub struct NameBinding<'a> {
1161     kind: NameBindingKind<'a>,
1162     expansion: Mark,
1163     span: Span,
1164     vis: ty::Visibility,
1165 }
1166
1167 pub trait ToNameBinding<'a> {
1168     fn to_name_binding(self, arenas: &'a ResolverArenas<'a>) -> &'a NameBinding<'a>;
1169 }
1170
1171 impl<'a> ToNameBinding<'a> for &'a NameBinding<'a> {
1172     fn to_name_binding(self, _: &'a ResolverArenas<'a>) -> &'a NameBinding<'a> {
1173         self
1174     }
1175 }
1176
1177 #[derive(Clone, Debug)]
1178 enum NameBindingKind<'a> {
1179     Def(Def),
1180     Module(Module<'a>),
1181     Import {
1182         binding: &'a NameBinding<'a>,
1183         directive: &'a ImportDirective<'a>,
1184         used: Cell<bool>,
1185         legacy_self_import: bool,
1186     },
1187     Ambiguity {
1188         b1: &'a NameBinding<'a>,
1189         b2: &'a NameBinding<'a>,
1190         legacy: bool,
1191     }
1192 }
1193
1194 struct PrivacyError<'a>(Span, Name, &'a NameBinding<'a>);
1195
1196 struct UseError<'a> {
1197     err: DiagnosticBuilder<'a>,
1198     /// Attach `use` statements for these candidates
1199     candidates: Vec<ImportSuggestion>,
1200     /// The node id of the module to place the use statements in
1201     node_id: NodeId,
1202     /// Whether the diagnostic should state that it's "better"
1203     better: bool,
1204 }
1205
1206 struct AmbiguityError<'a> {
1207     span: Span,
1208     name: Name,
1209     lexical: bool,
1210     b1: &'a NameBinding<'a>,
1211     b2: &'a NameBinding<'a>,
1212     legacy: bool,
1213 }
1214
1215 impl<'a> NameBinding<'a> {
1216     fn module(&self) -> Option<Module<'a>> {
1217         match self.kind {
1218             NameBindingKind::Module(module) => Some(module),
1219             NameBindingKind::Import { binding, .. } => binding.module(),
1220             NameBindingKind::Ambiguity { legacy: true, b1, .. } => b1.module(),
1221             _ => None,
1222         }
1223     }
1224
1225     fn def(&self) -> Def {
1226         match self.kind {
1227             NameBindingKind::Def(def) => def,
1228             NameBindingKind::Module(module) => module.def().unwrap(),
1229             NameBindingKind::Import { binding, .. } => binding.def(),
1230             NameBindingKind::Ambiguity { legacy: true, b1, .. } => b1.def(),
1231             NameBindingKind::Ambiguity { .. } => Def::Err,
1232         }
1233     }
1234
1235     fn def_ignoring_ambiguity(&self) -> Def {
1236         match self.kind {
1237             NameBindingKind::Import { binding, .. } => binding.def_ignoring_ambiguity(),
1238             NameBindingKind::Ambiguity { b1, .. } => b1.def_ignoring_ambiguity(),
1239             _ => self.def(),
1240         }
1241     }
1242
1243     fn get_macro(&self, resolver: &mut Resolver<'a>) -> Lrc<SyntaxExtension> {
1244         resolver.get_macro(self.def_ignoring_ambiguity())
1245     }
1246
1247     // We sometimes need to treat variants as `pub` for backwards compatibility
1248     fn pseudo_vis(&self) -> ty::Visibility {
1249         if self.is_variant() && self.def().def_id().is_local() {
1250             ty::Visibility::Public
1251         } else {
1252             self.vis
1253         }
1254     }
1255
1256     fn is_variant(&self) -> bool {
1257         match self.kind {
1258             NameBindingKind::Def(Def::Variant(..)) |
1259             NameBindingKind::Def(Def::VariantCtor(..)) => true,
1260             _ => false,
1261         }
1262     }
1263
1264     fn is_extern_crate(&self) -> bool {
1265         match self.kind {
1266             NameBindingKind::Import {
1267                 directive: &ImportDirective {
1268                     subclass: ImportDirectiveSubclass::ExternCrate(_), ..
1269                 }, ..
1270             } => true,
1271             _ => false,
1272         }
1273     }
1274
1275     fn is_import(&self) -> bool {
1276         match self.kind {
1277             NameBindingKind::Import { .. } => true,
1278             _ => false,
1279         }
1280     }
1281
1282     fn is_renamed_extern_crate(&self) -> bool {
1283         if let NameBindingKind::Import { directive, ..} = self.kind {
1284             if let ImportDirectiveSubclass::ExternCrate(Some(_)) = directive.subclass {
1285                 return true;
1286             }
1287         }
1288         false
1289     }
1290
1291     fn is_glob_import(&self) -> bool {
1292         match self.kind {
1293             NameBindingKind::Import { directive, .. } => directive.is_glob(),
1294             NameBindingKind::Ambiguity { b1, .. } => b1.is_glob_import(),
1295             _ => false,
1296         }
1297     }
1298
1299     fn is_importable(&self) -> bool {
1300         match self.def() {
1301             Def::AssociatedConst(..) | Def::Method(..) | Def::AssociatedTy(..) => false,
1302             _ => true,
1303         }
1304     }
1305
1306     fn is_macro_def(&self) -> bool {
1307         match self.kind {
1308             NameBindingKind::Def(Def::Macro(..)) => true,
1309             _ => false,
1310         }
1311     }
1312
1313     fn descr(&self) -> &'static str {
1314         if self.is_extern_crate() { "extern crate" } else { self.def().kind_name() }
1315     }
1316 }
1317
1318 /// Interns the names of the primitive types.
1319 struct PrimitiveTypeTable {
1320     primitive_types: FxHashMap<Name, PrimTy>,
1321 }
1322
1323 impl PrimitiveTypeTable {
1324     fn new() -> PrimitiveTypeTable {
1325         let mut table = PrimitiveTypeTable { primitive_types: FxHashMap() };
1326
1327         table.intern("bool", TyBool);
1328         table.intern("char", TyChar);
1329         table.intern("f32", TyFloat(FloatTy::F32));
1330         table.intern("f64", TyFloat(FloatTy::F64));
1331         table.intern("isize", TyInt(IntTy::Isize));
1332         table.intern("i8", TyInt(IntTy::I8));
1333         table.intern("i16", TyInt(IntTy::I16));
1334         table.intern("i32", TyInt(IntTy::I32));
1335         table.intern("i64", TyInt(IntTy::I64));
1336         table.intern("i128", TyInt(IntTy::I128));
1337         table.intern("str", TyStr);
1338         table.intern("usize", TyUint(UintTy::Usize));
1339         table.intern("u8", TyUint(UintTy::U8));
1340         table.intern("u16", TyUint(UintTy::U16));
1341         table.intern("u32", TyUint(UintTy::U32));
1342         table.intern("u64", TyUint(UintTy::U64));
1343         table.intern("u128", TyUint(UintTy::U128));
1344         table
1345     }
1346
1347     fn intern(&mut self, string: &str, primitive_type: PrimTy) {
1348         self.primitive_types.insert(Symbol::intern(string), primitive_type);
1349     }
1350 }
1351
1352 /// The main resolver class.
1353 pub struct Resolver<'a> {
1354     session: &'a Session,
1355     cstore: &'a CrateStore,
1356
1357     pub definitions: Definitions,
1358
1359     graph_root: Module<'a>,
1360
1361     prelude: Option<Module<'a>>,
1362
1363     // n.b. This is used only for better diagnostics, not name resolution itself.
1364     has_self: FxHashSet<DefId>,
1365
1366     // Names of fields of an item `DefId` accessible with dot syntax.
1367     // Used for hints during error reporting.
1368     field_names: FxHashMap<DefId, Vec<Name>>,
1369
1370     // All imports known to succeed or fail.
1371     determined_imports: Vec<&'a ImportDirective<'a>>,
1372
1373     // All non-determined imports.
1374     indeterminate_imports: Vec<&'a ImportDirective<'a>>,
1375
1376     // The module that represents the current item scope.
1377     current_module: Module<'a>,
1378
1379     // The current set of local scopes for types and values.
1380     // FIXME #4948: Reuse ribs to avoid allocation.
1381     ribs: PerNS<Vec<Rib<'a>>>,
1382
1383     // The current set of local scopes, for labels.
1384     label_ribs: Vec<Rib<'a>>,
1385
1386     // The trait that the current context can refer to.
1387     current_trait_ref: Option<(Module<'a>, TraitRef)>,
1388
1389     // The current self type if inside an impl (used for better errors).
1390     current_self_type: Option<Ty>,
1391
1392     // The idents for the primitive types.
1393     primitive_type_table: PrimitiveTypeTable,
1394
1395     def_map: DefMap,
1396     pub freevars: FreevarMap,
1397     freevars_seen: NodeMap<NodeMap<usize>>,
1398     pub export_map: ExportMap,
1399     pub trait_map: TraitMap,
1400
1401     // A map from nodes to anonymous modules.
1402     // Anonymous modules are pseudo-modules that are implicitly created around items
1403     // contained within blocks.
1404     //
1405     // For example, if we have this:
1406     //
1407     //  fn f() {
1408     //      fn g() {
1409     //          ...
1410     //      }
1411     //  }
1412     //
1413     // There will be an anonymous module created around `g` with the ID of the
1414     // entry block for `f`.
1415     block_map: NodeMap<Module<'a>>,
1416     module_map: FxHashMap<DefId, Module<'a>>,
1417     extern_module_map: FxHashMap<(DefId, bool /* MacrosOnly? */), Module<'a>>,
1418
1419     pub make_glob_map: bool,
1420     /// Maps imports to the names of items actually imported (this actually maps
1421     /// all imports, but only glob imports are actually interesting).
1422     pub glob_map: GlobMap,
1423
1424     used_imports: FxHashSet<(NodeId, Namespace)>,
1425     pub maybe_unused_trait_imports: NodeSet,
1426     pub maybe_unused_extern_crates: Vec<(NodeId, Span)>,
1427
1428     /// privacy errors are delayed until the end in order to deduplicate them
1429     privacy_errors: Vec<PrivacyError<'a>>,
1430     /// ambiguity errors are delayed for deduplication
1431     ambiguity_errors: Vec<AmbiguityError<'a>>,
1432     /// `use` injections are delayed for better placement and deduplication
1433     use_injections: Vec<UseError<'a>>,
1434     /// `use` injections for proc macros wrongly imported with #[macro_use]
1435     proc_mac_errors: Vec<macros::ProcMacError>,
1436
1437     gated_errors: FxHashSet<Span>,
1438     disallowed_shadowing: Vec<&'a LegacyBinding<'a>>,
1439
1440     arenas: &'a ResolverArenas<'a>,
1441     dummy_binding: &'a NameBinding<'a>,
1442     use_extern_macros: bool, // true if `#![feature(use_extern_macros)]`
1443
1444     crate_loader: &'a mut CrateLoader,
1445     macro_names: FxHashSet<Ident>,
1446     global_macros: FxHashMap<Name, &'a NameBinding<'a>>,
1447     pub all_macros: FxHashMap<Name, Def>,
1448     lexical_macro_resolutions: Vec<(Ident, &'a Cell<LegacyScope<'a>>)>,
1449     macro_map: FxHashMap<DefId, Lrc<SyntaxExtension>>,
1450     macro_defs: FxHashMap<Mark, DefId>,
1451     local_macro_def_scopes: FxHashMap<NodeId, Module<'a>>,
1452     macro_exports: Vec<Export>,
1453     pub whitelisted_legacy_custom_derives: Vec<Name>,
1454     pub found_unresolved_macro: bool,
1455
1456     // List of crate local macros that we need to warn about as being unused.
1457     // Right now this only includes macro_rules! macros, and macros 2.0.
1458     unused_macros: FxHashSet<DefId>,
1459
1460     // Maps the `Mark` of an expansion to its containing module or block.
1461     invocations: FxHashMap<Mark, &'a InvocationData<'a>>,
1462
1463     // Avoid duplicated errors for "name already defined".
1464     name_already_seen: FxHashMap<Name, Span>,
1465
1466     // If `#![feature(proc_macro)]` is set
1467     proc_macro_enabled: bool,
1468
1469     // A set of procedural macros imported by `#[macro_use]` that have already been warned about
1470     warned_proc_macros: FxHashSet<Name>,
1471
1472     potentially_unused_imports: Vec<&'a ImportDirective<'a>>,
1473
1474     // This table maps struct IDs into struct constructor IDs,
1475     // it's not used during normal resolution, only for better error reporting.
1476     struct_constructors: DefIdMap<(Def, ty::Visibility)>,
1477
1478     // Only used for better errors on `fn(): fn()`
1479     current_type_ascription: Vec<Span>,
1480
1481     injected_crate: Option<Module<'a>>,
1482 }
1483
1484 pub struct ResolverArenas<'a> {
1485     modules: arena::TypedArena<ModuleData<'a>>,
1486     local_modules: RefCell<Vec<Module<'a>>>,
1487     name_bindings: arena::TypedArena<NameBinding<'a>>,
1488     import_directives: arena::TypedArena<ImportDirective<'a>>,
1489     name_resolutions: arena::TypedArena<RefCell<NameResolution<'a>>>,
1490     invocation_data: arena::TypedArena<InvocationData<'a>>,
1491     legacy_bindings: arena::TypedArena<LegacyBinding<'a>>,
1492 }
1493
1494 impl<'a> ResolverArenas<'a> {
1495     fn alloc_module(&'a self, module: ModuleData<'a>) -> Module<'a> {
1496         let module = self.modules.alloc(module);
1497         if module.def_id().map(|def_id| def_id.is_local()).unwrap_or(true) {
1498             self.local_modules.borrow_mut().push(module);
1499         }
1500         module
1501     }
1502     fn local_modules(&'a self) -> ::std::cell::Ref<'a, Vec<Module<'a>>> {
1503         self.local_modules.borrow()
1504     }
1505     fn alloc_name_binding(&'a self, name_binding: NameBinding<'a>) -> &'a NameBinding<'a> {
1506         self.name_bindings.alloc(name_binding)
1507     }
1508     fn alloc_import_directive(&'a self, import_directive: ImportDirective<'a>)
1509                               -> &'a ImportDirective {
1510         self.import_directives.alloc(import_directive)
1511     }
1512     fn alloc_name_resolution(&'a self) -> &'a RefCell<NameResolution<'a>> {
1513         self.name_resolutions.alloc(Default::default())
1514     }
1515     fn alloc_invocation_data(&'a self, expansion_data: InvocationData<'a>)
1516                              -> &'a InvocationData<'a> {
1517         self.invocation_data.alloc(expansion_data)
1518     }
1519     fn alloc_legacy_binding(&'a self, binding: LegacyBinding<'a>) -> &'a LegacyBinding<'a> {
1520         self.legacy_bindings.alloc(binding)
1521     }
1522 }
1523
1524 impl<'a, 'b: 'a> ty::DefIdTree for &'a Resolver<'b> {
1525     fn parent(self, id: DefId) -> Option<DefId> {
1526         match id.krate {
1527             LOCAL_CRATE => self.definitions.def_key(id.index).parent,
1528             _ => self.cstore.def_key(id).parent,
1529         }.map(|index| DefId { index: index, ..id })
1530     }
1531 }
1532
1533 impl<'a> hir::lowering::Resolver for Resolver<'a> {
1534     fn resolve_hir_path(&mut self, path: &mut hir::Path, is_value: bool) {
1535         self.resolve_hir_path_cb(path, is_value,
1536                                  |resolver, span, error| resolve_error(resolver, span, error))
1537     }
1538
1539     fn resolve_str_path(&mut self, span: Span, crate_root: Option<&str>,
1540                         components: &[&str], is_value: bool) -> hir::Path {
1541         let mut path = hir::Path {
1542             span,
1543             def: Def::Err,
1544             segments: iter::once(keywords::CrateRoot.name()).chain({
1545                 crate_root.into_iter().chain(components.iter().cloned()).map(Symbol::intern)
1546             }).map(hir::PathSegment::from_name).collect(),
1547         };
1548
1549         self.resolve_hir_path(&mut path, is_value);
1550         path
1551     }
1552
1553     fn get_resolution(&mut self, id: NodeId) -> Option<PathResolution> {
1554         self.def_map.get(&id).cloned()
1555     }
1556
1557     fn definitions(&mut self) -> &mut Definitions {
1558         &mut self.definitions
1559     }
1560 }
1561
1562 impl<'a> Resolver<'a> {
1563     /// Rustdoc uses this to resolve things in a recoverable way. ResolutionError<'a>
1564     /// isn't something that can be returned because it can't be made to live that long,
1565     /// and also it's a private type. Fortunately rustdoc doesn't need to know the error,
1566     /// just that an error occurred.
1567     pub fn resolve_str_path_error(&mut self, span: Span, path_str: &str, is_value: bool)
1568         -> Result<hir::Path, ()> {
1569         use std::iter;
1570         let mut errored = false;
1571
1572         let mut path = if path_str.starts_with("::") {
1573             hir::Path {
1574                 span,
1575                 def: Def::Err,
1576                 segments: iter::once(keywords::CrateRoot.name()).chain({
1577                     path_str.split("::").skip(1).map(Symbol::intern)
1578                 }).map(hir::PathSegment::from_name).collect(),
1579             }
1580         } else {
1581             hir::Path {
1582                 span,
1583                 def: Def::Err,
1584                 segments: path_str.split("::").map(Symbol::intern)
1585                                   .map(hir::PathSegment::from_name).collect(),
1586             }
1587         };
1588         self.resolve_hir_path_cb(&mut path, is_value, |_, _, _| errored = true);
1589         if errored || path.def == Def::Err {
1590             Err(())
1591         } else {
1592             Ok(path)
1593         }
1594     }
1595
1596     /// resolve_hir_path, but takes a callback in case there was an error
1597     fn resolve_hir_path_cb<F>(&mut self, path: &mut hir::Path, is_value: bool, error_callback: F)
1598             where F: for<'c, 'b> FnOnce(&'c mut Resolver, Span, ResolutionError<'b>)
1599         {
1600         let namespace = if is_value { ValueNS } else { TypeNS };
1601         let hir::Path { ref segments, span, ref mut def } = *path;
1602         let path: Vec<SpannedIdent> = segments.iter()
1603             .map(|seg| respan(span, Ident::with_empty_ctxt(seg.name)))
1604             .collect();
1605         match self.resolve_path(&path, Some(namespace), true, span) {
1606             PathResult::Module(module) => *def = module.def().unwrap(),
1607             PathResult::NonModule(path_res) if path_res.unresolved_segments() == 0 =>
1608                 *def = path_res.base_def(),
1609             PathResult::NonModule(..) => match self.resolve_path(&path, None, true, span) {
1610                 PathResult::Failed(span, msg, _) => {
1611                     error_callback(self, span, ResolutionError::FailedToResolve(&msg));
1612                 }
1613                 _ => {}
1614             },
1615             PathResult::Indeterminate => unreachable!(),
1616             PathResult::Failed(span, msg, _) => {
1617                 error_callback(self, span, ResolutionError::FailedToResolve(&msg));
1618             }
1619         }
1620     }
1621 }
1622
1623 impl<'a> Resolver<'a> {
1624     pub fn new(session: &'a Session,
1625                cstore: &'a CrateStore,
1626                krate: &Crate,
1627                crate_name: &str,
1628                make_glob_map: MakeGlobMap,
1629                crate_loader: &'a mut CrateLoader,
1630                arenas: &'a ResolverArenas<'a>)
1631                -> Resolver<'a> {
1632         let root_def_id = DefId::local(CRATE_DEF_INDEX);
1633         let root_module_kind = ModuleKind::Def(Def::Mod(root_def_id), keywords::Invalid.name());
1634         let graph_root = arenas.alloc_module(ModuleData {
1635             no_implicit_prelude: attr::contains_name(&krate.attrs, "no_implicit_prelude"),
1636             ..ModuleData::new(None, root_module_kind, root_def_id, Mark::root(), krate.span)
1637         });
1638         let mut module_map = FxHashMap();
1639         module_map.insert(DefId::local(CRATE_DEF_INDEX), graph_root);
1640
1641         let mut definitions = Definitions::new();
1642         DefCollector::new(&mut definitions, Mark::root())
1643             .collect_root(crate_name, session.local_crate_disambiguator());
1644
1645         let mut invocations = FxHashMap();
1646         invocations.insert(Mark::root(),
1647                            arenas.alloc_invocation_data(InvocationData::root(graph_root)));
1648
1649         let features = session.features_untracked();
1650
1651         let mut macro_defs = FxHashMap();
1652         macro_defs.insert(Mark::root(), root_def_id);
1653
1654         Resolver {
1655             session,
1656
1657             cstore,
1658
1659             definitions,
1660
1661             // The outermost module has def ID 0; this is not reflected in the
1662             // AST.
1663             graph_root,
1664             prelude: None,
1665
1666             has_self: FxHashSet(),
1667             field_names: FxHashMap(),
1668
1669             determined_imports: Vec::new(),
1670             indeterminate_imports: Vec::new(),
1671
1672             current_module: graph_root,
1673             ribs: PerNS {
1674                 value_ns: vec![Rib::new(ModuleRibKind(graph_root))],
1675                 type_ns: vec![Rib::new(ModuleRibKind(graph_root))],
1676                 macro_ns: Some(vec![Rib::new(ModuleRibKind(graph_root))]),
1677             },
1678             label_ribs: Vec::new(),
1679
1680             current_trait_ref: None,
1681             current_self_type: None,
1682
1683             primitive_type_table: PrimitiveTypeTable::new(),
1684
1685             def_map: NodeMap(),
1686             freevars: NodeMap(),
1687             freevars_seen: NodeMap(),
1688             export_map: FxHashMap(),
1689             trait_map: NodeMap(),
1690             module_map,
1691             block_map: NodeMap(),
1692             extern_module_map: FxHashMap(),
1693
1694             make_glob_map: make_glob_map == MakeGlobMap::Yes,
1695             glob_map: NodeMap(),
1696
1697             used_imports: FxHashSet(),
1698             maybe_unused_trait_imports: NodeSet(),
1699             maybe_unused_extern_crates: Vec::new(),
1700
1701             privacy_errors: Vec::new(),
1702             ambiguity_errors: Vec::new(),
1703             use_injections: Vec::new(),
1704             proc_mac_errors: Vec::new(),
1705             gated_errors: FxHashSet(),
1706             disallowed_shadowing: Vec::new(),
1707
1708             arenas,
1709             dummy_binding: arenas.alloc_name_binding(NameBinding {
1710                 kind: NameBindingKind::Def(Def::Err),
1711                 expansion: Mark::root(),
1712                 span: DUMMY_SP,
1713                 vis: ty::Visibility::Public,
1714             }),
1715
1716             // The `proc_macro` and `decl_macro` features imply `use_extern_macros`
1717             use_extern_macros:
1718                 features.use_extern_macros || features.proc_macro || features.decl_macro,
1719
1720             crate_loader,
1721             macro_names: FxHashSet(),
1722             global_macros: FxHashMap(),
1723             all_macros: FxHashMap(),
1724             lexical_macro_resolutions: Vec::new(),
1725             macro_map: FxHashMap(),
1726             macro_exports: Vec::new(),
1727             invocations,
1728             macro_defs,
1729             local_macro_def_scopes: FxHashMap(),
1730             name_already_seen: FxHashMap(),
1731             whitelisted_legacy_custom_derives: Vec::new(),
1732             proc_macro_enabled: features.proc_macro,
1733             warned_proc_macros: FxHashSet(),
1734             potentially_unused_imports: Vec::new(),
1735             struct_constructors: DefIdMap(),
1736             found_unresolved_macro: false,
1737             unused_macros: FxHashSet(),
1738             current_type_ascription: Vec::new(),
1739             injected_crate: None,
1740         }
1741     }
1742
1743     pub fn arenas() -> ResolverArenas<'a> {
1744         ResolverArenas {
1745             modules: arena::TypedArena::new(),
1746             local_modules: RefCell::new(Vec::new()),
1747             name_bindings: arena::TypedArena::new(),
1748             import_directives: arena::TypedArena::new(),
1749             name_resolutions: arena::TypedArena::new(),
1750             invocation_data: arena::TypedArena::new(),
1751             legacy_bindings: arena::TypedArena::new(),
1752         }
1753     }
1754
1755     fn per_ns<T, F: FnMut(&mut Self, Namespace) -> T>(&mut self, mut f: F) -> PerNS<T> {
1756         PerNS {
1757             type_ns: f(self, TypeNS),
1758             value_ns: f(self, ValueNS),
1759             macro_ns: match self.use_extern_macros {
1760                 true => Some(f(self, MacroNS)),
1761                 false => None,
1762             },
1763         }
1764     }
1765
1766     fn macro_def(&self, mut ctxt: SyntaxContext) -> DefId {
1767         loop {
1768             match self.macro_defs.get(&ctxt.outer()) {
1769                 Some(&def_id) => return def_id,
1770                 None => ctxt.remove_mark(),
1771             };
1772         }
1773     }
1774
1775     /// Entry point to crate resolution.
1776     pub fn resolve_crate(&mut self, krate: &Crate) {
1777         ImportResolver { resolver: self }.finalize_imports();
1778         self.current_module = self.graph_root;
1779         self.finalize_current_module_macro_resolutions();
1780
1781         visit::walk_crate(self, krate);
1782
1783         check_unused::check_crate(self, krate);
1784         self.report_errors(krate);
1785         self.crate_loader.postprocess(krate);
1786     }
1787
1788     fn new_module(
1789         &self,
1790         parent: Module<'a>,
1791         kind: ModuleKind,
1792         normal_ancestor_id: DefId,
1793         expansion: Mark,
1794         span: Span,
1795     ) -> Module<'a> {
1796         let module = ModuleData::new(Some(parent), kind, normal_ancestor_id, expansion, span);
1797         self.arenas.alloc_module(module)
1798     }
1799
1800     fn record_use(&mut self, ident: Ident, ns: Namespace, binding: &'a NameBinding<'a>, span: Span)
1801                   -> bool /* true if an error was reported */ {
1802         match binding.kind {
1803             NameBindingKind::Import { directive, binding, ref used, legacy_self_import }
1804                     if !used.get() => {
1805                 used.set(true);
1806                 directive.used.set(true);
1807                 if legacy_self_import {
1808                     self.warn_legacy_self_import(directive);
1809                     return false;
1810                 }
1811                 self.used_imports.insert((directive.id, ns));
1812                 self.add_to_glob_map(directive.id, ident);
1813                 self.record_use(ident, ns, binding, span)
1814             }
1815             NameBindingKind::Import { .. } => false,
1816             NameBindingKind::Ambiguity { b1, b2, legacy } => {
1817                 self.ambiguity_errors.push(AmbiguityError {
1818                     span: span, name: ident.name, lexical: false, b1: b1, b2: b2, legacy,
1819                 });
1820                 if legacy {
1821                     self.record_use(ident, ns, b1, span);
1822                 }
1823                 !legacy
1824             }
1825             _ => false
1826         }
1827     }
1828
1829     fn add_to_glob_map(&mut self, id: NodeId, ident: Ident) {
1830         if self.make_glob_map {
1831             self.glob_map.entry(id).or_insert_with(FxHashSet).insert(ident.name);
1832         }
1833     }
1834
1835     /// This resolves the identifier `ident` in the namespace `ns` in the current lexical scope.
1836     /// More specifically, we proceed up the hierarchy of scopes and return the binding for
1837     /// `ident` in the first scope that defines it (or None if no scopes define it).
1838     ///
1839     /// A block's items are above its local variables in the scope hierarchy, regardless of where
1840     /// the items are defined in the block. For example,
1841     /// ```rust
1842     /// fn f() {
1843     ///    g(); // Since there are no local variables in scope yet, this resolves to the item.
1844     ///    let g = || {};
1845     ///    fn g() {}
1846     ///    g(); // This resolves to the local variable `g` since it shadows the item.
1847     /// }
1848     /// ```
1849     ///
1850     /// Invariant: This must only be called during main resolution, not during
1851     /// import resolution.
1852     fn resolve_ident_in_lexical_scope(&mut self,
1853                                       mut ident: Ident,
1854                                       ns: Namespace,
1855                                       record_used: bool,
1856                                       path_span: Span)
1857                                       -> Option<LexicalScopeBinding<'a>> {
1858         if ns == TypeNS {
1859             ident.ctxt = if ident.name == keywords::SelfType.name() {
1860                 SyntaxContext::empty() // FIXME(jseyfried) improve `Self` hygiene
1861             } else {
1862                 ident.ctxt.modern()
1863             }
1864         }
1865
1866         // Walk backwards up the ribs in scope.
1867         let mut module = self.graph_root;
1868         for i in (0 .. self.ribs[ns].len()).rev() {
1869             if let Some(def) = self.ribs[ns][i].bindings.get(&ident).cloned() {
1870                 // The ident resolves to a type parameter or local variable.
1871                 return Some(LexicalScopeBinding::Def(
1872                     self.adjust_local_def(ns, i, def, record_used, path_span)
1873                 ));
1874             }
1875
1876             module = match self.ribs[ns][i].kind {
1877                 ModuleRibKind(module) => module,
1878                 MacroDefinition(def) if def == self.macro_def(ident.ctxt) => {
1879                     // If an invocation of this macro created `ident`, give up on `ident`
1880                     // and switch to `ident`'s source from the macro definition.
1881                     ident.ctxt.remove_mark();
1882                     continue
1883                 }
1884                 _ => continue,
1885             };
1886
1887             let item = self.resolve_ident_in_module_unadjusted(
1888                 module, ident, ns, false, record_used, path_span,
1889             );
1890             if let Ok(binding) = item {
1891                 // The ident resolves to an item.
1892                 return Some(LexicalScopeBinding::Item(binding));
1893             }
1894
1895             match module.kind {
1896                 ModuleKind::Block(..) => {}, // We can see through blocks
1897                 _ => break,
1898             }
1899         }
1900
1901         ident.ctxt = ident.ctxt.modern();
1902         loop {
1903             module = unwrap_or!(self.hygienic_lexical_parent(module, &mut ident.ctxt), break);
1904             let orig_current_module = self.current_module;
1905             self.current_module = module; // Lexical resolutions can never be a privacy error.
1906             let result = self.resolve_ident_in_module_unadjusted(
1907                 module, ident, ns, false, record_used, path_span,
1908             );
1909             self.current_module = orig_current_module;
1910
1911             match result {
1912                 Ok(binding) => return Some(LexicalScopeBinding::Item(binding)),
1913                 Err(Undetermined) => return None,
1914                 Err(Determined) => {}
1915             }
1916         }
1917
1918         match self.prelude {
1919             Some(prelude) if !module.no_implicit_prelude => {
1920                 self.resolve_ident_in_module_unadjusted(prelude, ident, ns, false, false, path_span)
1921                     .ok().map(LexicalScopeBinding::Item)
1922             }
1923             _ => None,
1924         }
1925     }
1926
1927     fn hygienic_lexical_parent(&mut self, mut module: Module<'a>, ctxt: &mut SyntaxContext)
1928                                -> Option<Module<'a>> {
1929         if !module.expansion.is_descendant_of(ctxt.outer()) {
1930             return Some(self.macro_def_scope(ctxt.remove_mark()));
1931         }
1932
1933         if let ModuleKind::Block(..) = module.kind {
1934             return Some(module.parent.unwrap());
1935         }
1936
1937         let mut module_expansion = module.expansion.modern(); // for backward compatibility
1938         while let Some(parent) = module.parent {
1939             let parent_expansion = parent.expansion.modern();
1940             if module_expansion.is_descendant_of(parent_expansion) &&
1941                parent_expansion != module_expansion {
1942                 return if parent_expansion.is_descendant_of(ctxt.outer()) {
1943                     Some(parent)
1944                 } else {
1945                     None
1946                 };
1947             }
1948             module = parent;
1949             module_expansion = parent_expansion;
1950         }
1951
1952         None
1953     }
1954
1955     fn resolve_ident_in_module(&mut self,
1956                                module: Module<'a>,
1957                                mut ident: Ident,
1958                                ns: Namespace,
1959                                ignore_unresolved_invocations: bool,
1960                                record_used: bool,
1961                                span: Span)
1962                                -> Result<&'a NameBinding<'a>, Determinacy> {
1963         ident.ctxt = ident.ctxt.modern();
1964         let orig_current_module = self.current_module;
1965         if let Some(def) = ident.ctxt.adjust(module.expansion) {
1966             self.current_module = self.macro_def_scope(def);
1967         }
1968         let result = self.resolve_ident_in_module_unadjusted(
1969             module, ident, ns, ignore_unresolved_invocations, record_used, span,
1970         );
1971         self.current_module = orig_current_module;
1972         result
1973     }
1974
1975     fn resolve_crate_root(&mut self, mut ctxt: SyntaxContext, legacy: bool) -> Module<'a> {
1976         let mark = if legacy {
1977             // When resolving `$crate` from a `macro_rules!` invoked in a `macro`,
1978             // we don't want to pretend that the `macro_rules!` definition is in the `macro`
1979             // as described in `SyntaxContext::apply_mark`, so we ignore prepended modern marks.
1980             ctxt.marks().into_iter().find(|&mark| mark.kind() != MarkKind::Modern)
1981         } else {
1982             ctxt = ctxt.modern();
1983             ctxt.adjust(Mark::root())
1984         };
1985         let module = match mark {
1986             Some(def) => self.macro_def_scope(def),
1987             None => return self.graph_root,
1988         };
1989         self.get_module(DefId { index: CRATE_DEF_INDEX, ..module.normal_ancestor_id })
1990     }
1991
1992     fn resolve_self(&mut self, ctxt: &mut SyntaxContext, module: Module<'a>) -> Module<'a> {
1993         let mut module = self.get_module(module.normal_ancestor_id);
1994         while module.span.ctxt().modern() != *ctxt {
1995             let parent = module.parent.unwrap_or_else(|| self.macro_def_scope(ctxt.remove_mark()));
1996             module = self.get_module(parent.normal_ancestor_id);
1997         }
1998         module
1999     }
2000
2001     // AST resolution
2002     //
2003     // We maintain a list of value ribs and type ribs.
2004     //
2005     // Simultaneously, we keep track of the current position in the module
2006     // graph in the `current_module` pointer. When we go to resolve a name in
2007     // the value or type namespaces, we first look through all the ribs and
2008     // then query the module graph. When we resolve a name in the module
2009     // namespace, we can skip all the ribs (since nested modules are not
2010     // allowed within blocks in Rust) and jump straight to the current module
2011     // graph node.
2012     //
2013     // Named implementations are handled separately. When we find a method
2014     // call, we consult the module node to find all of the implementations in
2015     // scope. This information is lazily cached in the module node. We then
2016     // generate a fake "implementation scope" containing all the
2017     // implementations thus found, for compatibility with old resolve pass.
2018
2019     pub fn with_scope<F, T>(&mut self, id: NodeId, f: F) -> T
2020         where F: FnOnce(&mut Resolver) -> T
2021     {
2022         let id = self.definitions.local_def_id(id);
2023         let module = self.module_map.get(&id).cloned(); // clones a reference
2024         if let Some(module) = module {
2025             // Move down in the graph.
2026             let orig_module = replace(&mut self.current_module, module);
2027             self.ribs[ValueNS].push(Rib::new(ModuleRibKind(module)));
2028             self.ribs[TypeNS].push(Rib::new(ModuleRibKind(module)));
2029
2030             self.finalize_current_module_macro_resolutions();
2031             let ret = f(self);
2032
2033             self.current_module = orig_module;
2034             self.ribs[ValueNS].pop();
2035             self.ribs[TypeNS].pop();
2036             ret
2037         } else {
2038             f(self)
2039         }
2040     }
2041
2042     /// Searches the current set of local scopes for labels. Returns the first non-None label that
2043     /// is returned by the given predicate function
2044     ///
2045     /// Stops after meeting a closure.
2046     fn search_label<P, R>(&self, mut ident: Ident, pred: P) -> Option<R>
2047         where P: Fn(&Rib, Ident) -> Option<R>
2048     {
2049         for rib in self.label_ribs.iter().rev() {
2050             match rib.kind {
2051                 NormalRibKind => {}
2052                 // If an invocation of this macro created `ident`, give up on `ident`
2053                 // and switch to `ident`'s source from the macro definition.
2054                 MacroDefinition(def) => {
2055                     if def == self.macro_def(ident.ctxt) {
2056                         ident.ctxt.remove_mark();
2057                     }
2058                 }
2059                 _ => {
2060                     // Do not resolve labels across function boundary
2061                     return None;
2062                 }
2063             }
2064             let r = pred(rib, ident);
2065             if r.is_some() {
2066                 return r;
2067             }
2068         }
2069         None
2070     }
2071
2072     fn resolve_item(&mut self, item: &Item) {
2073         let name = item.ident.name;
2074
2075         debug!("(resolving item) resolving {}", name);
2076
2077         self.check_proc_macro_attrs(&item.attrs);
2078
2079         match item.node {
2080             ItemKind::Enum(_, ref generics) |
2081             ItemKind::Ty(_, ref generics) |
2082             ItemKind::Struct(_, ref generics) |
2083             ItemKind::Union(_, ref generics) |
2084             ItemKind::Fn(.., ref generics, _) => {
2085                 self.with_type_parameter_rib(HasTypeParameters(generics, ItemRibKind),
2086                                              |this| visit::walk_item(this, item));
2087             }
2088
2089             ItemKind::Impl(.., ref generics, ref opt_trait_ref, ref self_type, ref impl_items) =>
2090                 self.resolve_implementation(generics,
2091                                             opt_trait_ref,
2092                                             &self_type,
2093                                             item.id,
2094                                             impl_items),
2095
2096             ItemKind::Trait(.., ref generics, ref bounds, ref trait_items) => {
2097                 // Create a new rib for the trait-wide type parameters.
2098                 self.with_type_parameter_rib(HasTypeParameters(generics, ItemRibKind), |this| {
2099                     let local_def_id = this.definitions.local_def_id(item.id);
2100                     this.with_self_rib(Def::SelfTy(Some(local_def_id), None), |this| {
2101                         this.visit_generics(generics);
2102                         walk_list!(this, visit_ty_param_bound, bounds);
2103
2104                         for trait_item in trait_items {
2105                             this.check_proc_macro_attrs(&trait_item.attrs);
2106
2107                             let type_parameters = HasTypeParameters(&trait_item.generics,
2108                                                                     TraitOrImplItemRibKind);
2109                             this.with_type_parameter_rib(type_parameters, |this| {
2110                                 match trait_item.node {
2111                                     TraitItemKind::Const(ref ty, ref default) => {
2112                                         this.visit_ty(ty);
2113
2114                                         // Only impose the restrictions of
2115                                         // ConstRibKind for an actual constant
2116                                         // expression in a provided default.
2117                                         if let Some(ref expr) = *default{
2118                                             this.with_constant_rib(|this| {
2119                                                 this.visit_expr(expr);
2120                                             });
2121                                         }
2122                                     }
2123                                     TraitItemKind::Method(_, _) => {
2124                                         visit::walk_trait_item(this, trait_item)
2125                                     }
2126                                     TraitItemKind::Type(..) => {
2127                                         visit::walk_trait_item(this, trait_item)
2128                                     }
2129                                     TraitItemKind::Macro(_) => {
2130                                         panic!("unexpanded macro in resolve!")
2131                                     }
2132                                 };
2133                             });
2134                         }
2135                     });
2136                 });
2137             }
2138
2139             ItemKind::TraitAlias(ref generics, ref bounds) => {
2140                 // Create a new rib for the trait-wide type parameters.
2141                 self.with_type_parameter_rib(HasTypeParameters(generics, ItemRibKind), |this| {
2142                     let local_def_id = this.definitions.local_def_id(item.id);
2143                     this.with_self_rib(Def::SelfTy(Some(local_def_id), None), |this| {
2144                         this.visit_generics(generics);
2145                         walk_list!(this, visit_ty_param_bound, bounds);
2146                     });
2147                 });
2148             }
2149
2150             ItemKind::Mod(_) | ItemKind::ForeignMod(_) => {
2151                 self.with_scope(item.id, |this| {
2152                     visit::walk_item(this, item);
2153                 });
2154             }
2155
2156             ItemKind::Static(ref ty, _, ref expr) |
2157             ItemKind::Const(ref ty, ref expr) => {
2158                 self.with_item_rib(|this| {
2159                     this.visit_ty(ty);
2160                     this.with_constant_rib(|this| {
2161                         this.visit_expr(expr);
2162                     });
2163                 });
2164             }
2165
2166             ItemKind::Use(ref use_tree) => {
2167                 let path = Path {
2168                     segments: vec![],
2169                     span: use_tree.span,
2170                 };
2171                 self.resolve_use_tree(item.id, use_tree, &path);
2172             }
2173
2174             ItemKind::ExternCrate(_) | ItemKind::MacroDef(..) | ItemKind::GlobalAsm(_) => {
2175                 // do nothing, these are just around to be encoded
2176             }
2177
2178             ItemKind::Mac(_) => panic!("unexpanded macro in resolve!"),
2179         }
2180     }
2181
2182     fn resolve_use_tree(&mut self, id: NodeId, use_tree: &ast::UseTree, prefix: &Path) {
2183         match use_tree.kind {
2184             ast::UseTreeKind::Nested(ref items) => {
2185                 let path = Path {
2186                     segments: prefix.segments
2187                         .iter()
2188                         .chain(use_tree.prefix.segments.iter())
2189                         .cloned()
2190                         .collect(),
2191                     span: prefix.span.to(use_tree.prefix.span),
2192                 };
2193
2194                 if items.len() == 0 {
2195                     // Resolve prefix of an import with empty braces (issue #28388).
2196                     self.smart_resolve_path(id, None, &path, PathSource::ImportPrefix);
2197                 } else {
2198                     for &(ref tree, nested_id) in items {
2199                         self.resolve_use_tree(nested_id, tree, &path);
2200                     }
2201                 }
2202             }
2203             ast::UseTreeKind::Simple(_) => {},
2204             ast::UseTreeKind::Glob => {},
2205         }
2206     }
2207
2208     fn with_type_parameter_rib<'b, F>(&'b mut self, type_parameters: TypeParameters<'a, 'b>, f: F)
2209         where F: FnOnce(&mut Resolver)
2210     {
2211         match type_parameters {
2212             HasTypeParameters(generics, rib_kind) => {
2213                 let mut function_type_rib = Rib::new(rib_kind);
2214                 let mut seen_bindings = FxHashMap();
2215                 for param in &generics.params {
2216                     if let GenericParam::Type(ref type_parameter) = *param {
2217                         let ident = type_parameter.ident.modern();
2218                         debug!("with_type_parameter_rib: {}", type_parameter.id);
2219
2220                         if seen_bindings.contains_key(&ident) {
2221                             let span = seen_bindings.get(&ident).unwrap();
2222                             let err = ResolutionError::NameAlreadyUsedInTypeParameterList(
2223                                 ident.name,
2224                                 span,
2225                             );
2226                             resolve_error(self, type_parameter.span, err);
2227                         }
2228                         seen_bindings.entry(ident).or_insert(type_parameter.span);
2229
2230                         // plain insert (no renaming)
2231                         let def_id = self.definitions.local_def_id(type_parameter.id);
2232                         let def = Def::TyParam(def_id);
2233                         function_type_rib.bindings.insert(ident, def);
2234                         self.record_def(type_parameter.id, PathResolution::new(def));
2235                     }
2236                 }
2237                 self.ribs[TypeNS].push(function_type_rib);
2238             }
2239
2240             NoTypeParameters => {
2241                 // Nothing to do.
2242             }
2243         }
2244
2245         f(self);
2246
2247         if let HasTypeParameters(..) = type_parameters {
2248             self.ribs[TypeNS].pop();
2249         }
2250     }
2251
2252     fn with_label_rib<F>(&mut self, f: F)
2253         where F: FnOnce(&mut Resolver)
2254     {
2255         self.label_ribs.push(Rib::new(NormalRibKind));
2256         f(self);
2257         self.label_ribs.pop();
2258     }
2259
2260     fn with_item_rib<F>(&mut self, f: F)
2261         where F: FnOnce(&mut Resolver)
2262     {
2263         self.ribs[ValueNS].push(Rib::new(ItemRibKind));
2264         self.ribs[TypeNS].push(Rib::new(ItemRibKind));
2265         f(self);
2266         self.ribs[TypeNS].pop();
2267         self.ribs[ValueNS].pop();
2268     }
2269
2270     fn with_constant_rib<F>(&mut self, f: F)
2271         where F: FnOnce(&mut Resolver)
2272     {
2273         self.ribs[ValueNS].push(Rib::new(ConstantItemRibKind));
2274         f(self);
2275         self.ribs[ValueNS].pop();
2276     }
2277
2278     fn with_current_self_type<T, F>(&mut self, self_type: &Ty, f: F) -> T
2279         where F: FnOnce(&mut Resolver) -> T
2280     {
2281         // Handle nested impls (inside fn bodies)
2282         let previous_value = replace(&mut self.current_self_type, Some(self_type.clone()));
2283         let result = f(self);
2284         self.current_self_type = previous_value;
2285         result
2286     }
2287
2288     /// This is called to resolve a trait reference from an `impl` (i.e. `impl Trait for Foo`)
2289     fn with_optional_trait_ref<T, F>(&mut self, opt_trait_ref: Option<&TraitRef>, f: F) -> T
2290         where F: FnOnce(&mut Resolver, Option<DefId>) -> T
2291     {
2292         let mut new_val = None;
2293         let mut new_id = None;
2294         if let Some(trait_ref) = opt_trait_ref {
2295             let path: Vec<_> = trait_ref.path.segments.iter()
2296                 .map(|seg| respan(seg.span, seg.identifier))
2297                 .collect();
2298             let def = self.smart_resolve_path_fragment(
2299                 trait_ref.ref_id,
2300                 None,
2301                 &path,
2302                 trait_ref.path.span,
2303                 trait_ref.path.segments.last().unwrap().span,
2304                 PathSource::Trait(AliasPossibility::No)
2305             ).base_def();
2306             if def != Def::Err {
2307                 new_id = Some(def.def_id());
2308                 let span = trait_ref.path.span;
2309                 if let PathResult::Module(module) = self.resolve_path(&path, None, false, span) {
2310                     new_val = Some((module, trait_ref.clone()));
2311                 }
2312             }
2313         }
2314         let original_trait_ref = replace(&mut self.current_trait_ref, new_val);
2315         let result = f(self, new_id);
2316         self.current_trait_ref = original_trait_ref;
2317         result
2318     }
2319
2320     fn with_self_rib<F>(&mut self, self_def: Def, f: F)
2321         where F: FnOnce(&mut Resolver)
2322     {
2323         let mut self_type_rib = Rib::new(NormalRibKind);
2324
2325         // plain insert (no renaming, types are not currently hygienic....)
2326         self_type_rib.bindings.insert(keywords::SelfType.ident(), self_def);
2327         self.ribs[TypeNS].push(self_type_rib);
2328         f(self);
2329         self.ribs[TypeNS].pop();
2330     }
2331
2332     fn resolve_implementation(&mut self,
2333                               generics: &Generics,
2334                               opt_trait_reference: &Option<TraitRef>,
2335                               self_type: &Ty,
2336                               item_id: NodeId,
2337                               impl_items: &[ImplItem]) {
2338         // If applicable, create a rib for the type parameters.
2339         self.with_type_parameter_rib(HasTypeParameters(generics, ItemRibKind), |this| {
2340             // Dummy self type for better errors if `Self` is used in the trait path.
2341             this.with_self_rib(Def::SelfTy(None, None), |this| {
2342                 // Resolve the trait reference, if necessary.
2343                 this.with_optional_trait_ref(opt_trait_reference.as_ref(), |this, trait_id| {
2344                     let item_def_id = this.definitions.local_def_id(item_id);
2345                     this.with_self_rib(Def::SelfTy(trait_id, Some(item_def_id)), |this| {
2346                         if let Some(trait_ref) = opt_trait_reference.as_ref() {
2347                             // Resolve type arguments in trait path
2348                             visit::walk_trait_ref(this, trait_ref);
2349                         }
2350                         // Resolve the self type.
2351                         this.visit_ty(self_type);
2352                         // Resolve the type parameters.
2353                         this.visit_generics(generics);
2354                         this.with_current_self_type(self_type, |this| {
2355                             for impl_item in impl_items {
2356                                 this.check_proc_macro_attrs(&impl_item.attrs);
2357                                 this.resolve_visibility(&impl_item.vis);
2358
2359                                 // We also need a new scope for the impl item type parameters.
2360                                 let type_parameters = HasTypeParameters(&impl_item.generics,
2361                                                                         TraitOrImplItemRibKind);
2362                                 this.with_type_parameter_rib(type_parameters, |this| {
2363                                     use self::ResolutionError::*;
2364                                     match impl_item.node {
2365                                         ImplItemKind::Const(..) => {
2366                                             // If this is a trait impl, ensure the const
2367                                             // exists in trait
2368                                             this.check_trait_item(impl_item.ident,
2369                                                                 ValueNS,
2370                                                                 impl_item.span,
2371                                                 |n, s| ConstNotMemberOfTrait(n, s));
2372                                             this.with_constant_rib(|this|
2373                                                 visit::walk_impl_item(this, impl_item)
2374                                             );
2375                                         }
2376                                         ImplItemKind::Method(_, _) => {
2377                                             // If this is a trait impl, ensure the method
2378                                             // exists in trait
2379                                             this.check_trait_item(impl_item.ident,
2380                                                                 ValueNS,
2381                                                                 impl_item.span,
2382                                                 |n, s| MethodNotMemberOfTrait(n, s));
2383
2384                                             visit::walk_impl_item(this, impl_item);
2385                                         }
2386                                         ImplItemKind::Type(ref ty) => {
2387                                             // If this is a trait impl, ensure the type
2388                                             // exists in trait
2389                                             this.check_trait_item(impl_item.ident,
2390                                                                 TypeNS,
2391                                                                 impl_item.span,
2392                                                 |n, s| TypeNotMemberOfTrait(n, s));
2393
2394                                             this.visit_ty(ty);
2395                                         }
2396                                         ImplItemKind::Macro(_) =>
2397                                             panic!("unexpanded macro in resolve!"),
2398                                     }
2399                                 });
2400                             }
2401                         });
2402                     });
2403                 });
2404             });
2405         });
2406     }
2407
2408     fn check_trait_item<F>(&mut self, ident: Ident, ns: Namespace, span: Span, err: F)
2409         where F: FnOnce(Name, &str) -> ResolutionError
2410     {
2411         // If there is a TraitRef in scope for an impl, then the method must be in the
2412         // trait.
2413         if let Some((module, _)) = self.current_trait_ref {
2414             if self.resolve_ident_in_module(module, ident, ns, false, false, span).is_err() {
2415                 let path = &self.current_trait_ref.as_ref().unwrap().1.path;
2416                 resolve_error(self, span, err(ident.name, &path_names_to_string(path)));
2417             }
2418         }
2419     }
2420
2421     fn resolve_local(&mut self, local: &Local) {
2422         // Resolve the type.
2423         walk_list!(self, visit_ty, &local.ty);
2424
2425         // Resolve the initializer.
2426         walk_list!(self, visit_expr, &local.init);
2427
2428         // Resolve the pattern.
2429         self.resolve_pattern(&local.pat, PatternSource::Let, &mut FxHashMap());
2430     }
2431
2432     // build a map from pattern identifiers to binding-info's.
2433     // this is done hygienically. This could arise for a macro
2434     // that expands into an or-pattern where one 'x' was from the
2435     // user and one 'x' came from the macro.
2436     fn binding_mode_map(&mut self, pat: &Pat) -> BindingMap {
2437         let mut binding_map = FxHashMap();
2438
2439         pat.walk(&mut |pat| {
2440             if let PatKind::Ident(binding_mode, ident, ref sub_pat) = pat.node {
2441                 if sub_pat.is_some() || match self.def_map.get(&pat.id).map(|res| res.base_def()) {
2442                     Some(Def::Local(..)) => true,
2443                     _ => false,
2444                 } {
2445                     let binding_info = BindingInfo { span: ident.span, binding_mode: binding_mode };
2446                     binding_map.insert(ident.node, binding_info);
2447                 }
2448             }
2449             true
2450         });
2451
2452         binding_map
2453     }
2454
2455     // check that all of the arms in an or-pattern have exactly the
2456     // same set of bindings, with the same binding modes for each.
2457     fn check_consistent_bindings(&mut self, pats: &[P<Pat>]) {
2458         if pats.is_empty() {
2459             return;
2460         }
2461
2462         let mut missing_vars = FxHashMap();
2463         let mut inconsistent_vars = FxHashMap();
2464         for (i, p) in pats.iter().enumerate() {
2465             let map_i = self.binding_mode_map(&p);
2466
2467             for (j, q) in pats.iter().enumerate() {
2468                 if i == j {
2469                     continue;
2470                 }
2471
2472                 let map_j = self.binding_mode_map(&q);
2473                 for (&key, &binding_i) in &map_i {
2474                     if map_j.len() == 0 {                   // Account for missing bindings when
2475                         let binding_error = missing_vars    // map_j has none.
2476                             .entry(key.name)
2477                             .or_insert(BindingError {
2478                                 name: key.name,
2479                                 origin: BTreeSet::new(),
2480                                 target: BTreeSet::new(),
2481                             });
2482                         binding_error.origin.insert(binding_i.span);
2483                         binding_error.target.insert(q.span);
2484                     }
2485                     for (&key_j, &binding_j) in &map_j {
2486                         match map_i.get(&key_j) {
2487                             None => {  // missing binding
2488                                 let binding_error = missing_vars
2489                                     .entry(key_j.name)
2490                                     .or_insert(BindingError {
2491                                         name: key_j.name,
2492                                         origin: BTreeSet::new(),
2493                                         target: BTreeSet::new(),
2494                                     });
2495                                 binding_error.origin.insert(binding_j.span);
2496                                 binding_error.target.insert(p.span);
2497                             }
2498                             Some(binding_i) => {  // check consistent binding
2499                                 if binding_i.binding_mode != binding_j.binding_mode {
2500                                     inconsistent_vars
2501                                         .entry(key.name)
2502                                         .or_insert((binding_j.span, binding_i.span));
2503                                 }
2504                             }
2505                         }
2506                     }
2507                 }
2508             }
2509         }
2510         let mut missing_vars = missing_vars.iter().collect::<Vec<_>>();
2511         missing_vars.sort();
2512         for (_, v) in missing_vars {
2513             resolve_error(self,
2514                           *v.origin.iter().next().unwrap(),
2515                           ResolutionError::VariableNotBoundInPattern(v));
2516         }
2517         let mut inconsistent_vars = inconsistent_vars.iter().collect::<Vec<_>>();
2518         inconsistent_vars.sort();
2519         for (name, v) in inconsistent_vars {
2520             resolve_error(self, v.0, ResolutionError::VariableBoundWithDifferentMode(*name, v.1));
2521         }
2522     }
2523
2524     fn resolve_arm(&mut self, arm: &Arm) {
2525         self.ribs[ValueNS].push(Rib::new(NormalRibKind));
2526
2527         let mut bindings_list = FxHashMap();
2528         for pattern in &arm.pats {
2529             self.resolve_pattern(&pattern, PatternSource::Match, &mut bindings_list);
2530         }
2531
2532         // This has to happen *after* we determine which pat_idents are variants
2533         self.check_consistent_bindings(&arm.pats);
2534
2535         walk_list!(self, visit_expr, &arm.guard);
2536         self.visit_expr(&arm.body);
2537
2538         self.ribs[ValueNS].pop();
2539     }
2540
2541     fn resolve_block(&mut self, block: &Block) {
2542         debug!("(resolving block) entering block");
2543         // Move down in the graph, if there's an anonymous module rooted here.
2544         let orig_module = self.current_module;
2545         let anonymous_module = self.block_map.get(&block.id).cloned(); // clones a reference
2546
2547         let mut num_macro_definition_ribs = 0;
2548         if let Some(anonymous_module) = anonymous_module {
2549             debug!("(resolving block) found anonymous module, moving down");
2550             self.ribs[ValueNS].push(Rib::new(ModuleRibKind(anonymous_module)));
2551             self.ribs[TypeNS].push(Rib::new(ModuleRibKind(anonymous_module)));
2552             self.current_module = anonymous_module;
2553             self.finalize_current_module_macro_resolutions();
2554         } else {
2555             self.ribs[ValueNS].push(Rib::new(NormalRibKind));
2556         }
2557
2558         // Descend into the block.
2559         for stmt in &block.stmts {
2560             if let ast::StmtKind::Item(ref item) = stmt.node {
2561                 if let ast::ItemKind::MacroDef(..) = item.node {
2562                     num_macro_definition_ribs += 1;
2563                     let def = self.definitions.local_def_id(item.id);
2564                     self.ribs[ValueNS].push(Rib::new(MacroDefinition(def)));
2565                     self.label_ribs.push(Rib::new(MacroDefinition(def)));
2566                 }
2567             }
2568
2569             self.visit_stmt(stmt);
2570         }
2571
2572         // Move back up.
2573         self.current_module = orig_module;
2574         for _ in 0 .. num_macro_definition_ribs {
2575             self.ribs[ValueNS].pop();
2576             self.label_ribs.pop();
2577         }
2578         self.ribs[ValueNS].pop();
2579         if let Some(_) = anonymous_module {
2580             self.ribs[TypeNS].pop();
2581         }
2582         debug!("(resolving block) leaving block");
2583     }
2584
2585     fn fresh_binding(&mut self,
2586                      ident: &SpannedIdent,
2587                      pat_id: NodeId,
2588                      outer_pat_id: NodeId,
2589                      pat_src: PatternSource,
2590                      bindings: &mut FxHashMap<Ident, NodeId>)
2591                      -> PathResolution {
2592         // Add the binding to the local ribs, if it
2593         // doesn't already exist in the bindings map. (We
2594         // must not add it if it's in the bindings map
2595         // because that breaks the assumptions later
2596         // passes make about or-patterns.)
2597         let mut def = Def::Local(pat_id);
2598         match bindings.get(&ident.node).cloned() {
2599             Some(id) if id == outer_pat_id => {
2600                 // `Variant(a, a)`, error
2601                 resolve_error(
2602                     self,
2603                     ident.span,
2604                     ResolutionError::IdentifierBoundMoreThanOnceInSamePattern(
2605                         &ident.node.name.as_str())
2606                 );
2607             }
2608             Some(..) if pat_src == PatternSource::FnParam => {
2609                 // `fn f(a: u8, a: u8)`, error
2610                 resolve_error(
2611                     self,
2612                     ident.span,
2613                     ResolutionError::IdentifierBoundMoreThanOnceInParameterList(
2614                         &ident.node.name.as_str())
2615                 );
2616             }
2617             Some(..) if pat_src == PatternSource::Match ||
2618                         pat_src == PatternSource::IfLet ||
2619                         pat_src == PatternSource::WhileLet => {
2620                 // `Variant1(a) | Variant2(a)`, ok
2621                 // Reuse definition from the first `a`.
2622                 def = self.ribs[ValueNS].last_mut().unwrap().bindings[&ident.node];
2623             }
2624             Some(..) => {
2625                 span_bug!(ident.span, "two bindings with the same name from \
2626                                        unexpected pattern source {:?}", pat_src);
2627             }
2628             None => {
2629                 // A completely fresh binding, add to the lists if it's valid.
2630                 if ident.node.name != keywords::Invalid.name() {
2631                     bindings.insert(ident.node, outer_pat_id);
2632                     self.ribs[ValueNS].last_mut().unwrap().bindings.insert(ident.node, def);
2633                 }
2634             }
2635         }
2636
2637         PathResolution::new(def)
2638     }
2639
2640     fn resolve_pattern(&mut self,
2641                        pat: &Pat,
2642                        pat_src: PatternSource,
2643                        // Maps idents to the node ID for the
2644                        // outermost pattern that binds them.
2645                        bindings: &mut FxHashMap<Ident, NodeId>) {
2646         // Visit all direct subpatterns of this pattern.
2647         let outer_pat_id = pat.id;
2648         pat.walk(&mut |pat| {
2649             match pat.node {
2650                 PatKind::Ident(bmode, ref ident, ref opt_pat) => {
2651                     // First try to resolve the identifier as some existing
2652                     // entity, then fall back to a fresh binding.
2653                     let binding = self.resolve_ident_in_lexical_scope(ident.node, ValueNS,
2654                                                                       false, pat.span)
2655                                       .and_then(LexicalScopeBinding::item);
2656                     let resolution = binding.map(NameBinding::def).and_then(|def| {
2657                         let is_syntactic_ambiguity = opt_pat.is_none() &&
2658                             bmode == BindingMode::ByValue(Mutability::Immutable);
2659                         match def {
2660                             Def::StructCtor(_, CtorKind::Const) |
2661                             Def::VariantCtor(_, CtorKind::Const) |
2662                             Def::Const(..) if is_syntactic_ambiguity => {
2663                                 // Disambiguate in favor of a unit struct/variant
2664                                 // or constant pattern.
2665                                 self.record_use(ident.node, ValueNS, binding.unwrap(), ident.span);
2666                                 Some(PathResolution::new(def))
2667                             }
2668                             Def::StructCtor(..) | Def::VariantCtor(..) |
2669                             Def::Const(..) | Def::Static(..) => {
2670                                 // This is unambiguously a fresh binding, either syntactically
2671                                 // (e.g. `IDENT @ PAT` or `ref IDENT`) or because `IDENT` resolves
2672                                 // to something unusable as a pattern (e.g. constructor function),
2673                                 // but we still conservatively report an error, see
2674                                 // issues/33118#issuecomment-233962221 for one reason why.
2675                                 resolve_error(
2676                                     self,
2677                                     ident.span,
2678                                     ResolutionError::BindingShadowsSomethingUnacceptable(
2679                                         pat_src.descr(), ident.node.name, binding.unwrap())
2680                                 );
2681                                 None
2682                             }
2683                             Def::Fn(..) | Def::Err => {
2684                                 // These entities are explicitly allowed
2685                                 // to be shadowed by fresh bindings.
2686                                 None
2687                             }
2688                             def => {
2689                                 span_bug!(ident.span, "unexpected definition for an \
2690                                                        identifier in pattern: {:?}", def);
2691                             }
2692                         }
2693                     }).unwrap_or_else(|| {
2694                         self.fresh_binding(ident, pat.id, outer_pat_id, pat_src, bindings)
2695                     });
2696
2697                     self.record_def(pat.id, resolution);
2698                 }
2699
2700                 PatKind::TupleStruct(ref path, ..) => {
2701                     self.smart_resolve_path(pat.id, None, path, PathSource::TupleStruct);
2702                 }
2703
2704                 PatKind::Path(ref qself, ref path) => {
2705                     self.smart_resolve_path(pat.id, qself.as_ref(), path, PathSource::Pat);
2706                 }
2707
2708                 PatKind::Struct(ref path, ..) => {
2709                     self.smart_resolve_path(pat.id, None, path, PathSource::Struct);
2710                 }
2711
2712                 _ => {}
2713             }
2714             true
2715         });
2716
2717         visit::walk_pat(self, pat);
2718     }
2719
2720     // High-level and context dependent path resolution routine.
2721     // Resolves the path and records the resolution into definition map.
2722     // If resolution fails tries several techniques to find likely
2723     // resolution candidates, suggest imports or other help, and report
2724     // errors in user friendly way.
2725     fn smart_resolve_path(&mut self,
2726                           id: NodeId,
2727                           qself: Option<&QSelf>,
2728                           path: &Path,
2729                           source: PathSource)
2730                           -> PathResolution {
2731         let segments = &path.segments.iter()
2732             .map(|seg| respan(seg.span, seg.identifier))
2733             .collect::<Vec<_>>();
2734         let ident_span = path.segments.last().map_or(path.span, |seg| seg.span);
2735         self.smart_resolve_path_fragment(id, qself, segments, path.span, ident_span, source)
2736     }
2737
2738     fn smart_resolve_path_fragment(&mut self,
2739                                    id: NodeId,
2740                                    qself: Option<&QSelf>,
2741                                    path: &[SpannedIdent],
2742                                    span: Span,
2743                                    ident_span: Span,
2744                                    source: PathSource)
2745                                    -> PathResolution {
2746         let ns = source.namespace();
2747         let is_expected = &|def| source.is_expected(def);
2748         let is_enum_variant = &|def| if let Def::Variant(..) = def { true } else { false };
2749
2750         // Base error is amended with one short label and possibly some longer helps/notes.
2751         let report_errors = |this: &mut Self, def: Option<Def>| {
2752             // Make the base error.
2753             let expected = source.descr_expected();
2754             let path_str = names_to_string(path);
2755             let code = source.error_code(def.is_some());
2756             let (base_msg, fallback_label, base_span) = if let Some(def) = def {
2757                 (format!("expected {}, found {} `{}`", expected, def.kind_name(), path_str),
2758                  format!("not a {}", expected),
2759                  span)
2760             } else {
2761                 let item_str = path[path.len() - 1].node;
2762                 let item_span = path[path.len() - 1].span;
2763                 let (mod_prefix, mod_str) = if path.len() == 1 {
2764                     (format!(""), format!("this scope"))
2765                 } else if path.len() == 2 && path[0].node.name == keywords::CrateRoot.name() {
2766                     (format!(""), format!("the crate root"))
2767                 } else {
2768                     let mod_path = &path[..path.len() - 1];
2769                     let mod_prefix = match this.resolve_path(mod_path, Some(TypeNS), false, span) {
2770                         PathResult::Module(module) => module.def(),
2771                         _ => None,
2772                     }.map_or(format!(""), |def| format!("{} ", def.kind_name()));
2773                     (mod_prefix, format!("`{}`", names_to_string(mod_path)))
2774                 };
2775                 (format!("cannot find {} `{}` in {}{}", expected, item_str, mod_prefix, mod_str),
2776                  format!("not found in {}", mod_str),
2777                  item_span)
2778             };
2779             let code = DiagnosticId::Error(code.into());
2780             let mut err = this.session.struct_span_err_with_code(base_span, &base_msg, code);
2781
2782             // Emit special messages for unresolved `Self` and `self`.
2783             if is_self_type(path, ns) {
2784                 __diagnostic_used!(E0411);
2785                 err.code(DiagnosticId::Error("E0411".into()));
2786                 err.span_label(span, "`Self` is only available in traits and impls");
2787                 return (err, Vec::new());
2788             }
2789             if is_self_value(path, ns) {
2790                 __diagnostic_used!(E0424);
2791                 err.code(DiagnosticId::Error("E0424".into()));
2792                 err.span_label(span, format!("`self` value is only available in \
2793                                                methods with `self` parameter"));
2794                 return (err, Vec::new());
2795             }
2796
2797             // Try to lookup the name in more relaxed fashion for better error reporting.
2798             let ident = *path.last().unwrap();
2799             let candidates = this.lookup_import_candidates(ident.node.name, ns, is_expected);
2800             if candidates.is_empty() && is_expected(Def::Enum(DefId::local(CRATE_DEF_INDEX))) {
2801                 let enum_candidates =
2802                     this.lookup_import_candidates(ident.node.name, ns, is_enum_variant);
2803                 let mut enum_candidates = enum_candidates.iter()
2804                     .map(|suggestion| import_candidate_to_paths(&suggestion)).collect::<Vec<_>>();
2805                 enum_candidates.sort();
2806                 for (sp, variant_path, enum_path) in enum_candidates {
2807                     if sp == DUMMY_SP {
2808                         let msg = format!("there is an enum variant `{}`, \
2809                                         try using `{}`?",
2810                                         variant_path,
2811                                         enum_path);
2812                         err.help(&msg);
2813                     } else {
2814                         err.span_suggestion(span, "you can try using the variant's enum",
2815                                             enum_path);
2816                     }
2817                 }
2818             }
2819             if path.len() == 1 && this.self_type_is_available(span) {
2820                 if let Some(candidate) = this.lookup_assoc_candidate(ident.node, ns, is_expected) {
2821                     let self_is_available = this.self_value_is_available(path[0].node.ctxt, span);
2822                     match candidate {
2823                         AssocSuggestion::Field => {
2824                             err.span_suggestion(span, "try",
2825                                                 format!("self.{}", path_str));
2826                             if !self_is_available {
2827                                 err.span_label(span, format!("`self` value is only available in \
2828                                                                methods with `self` parameter"));
2829                             }
2830                         }
2831                         AssocSuggestion::MethodWithSelf if self_is_available => {
2832                             err.span_suggestion(span, "try",
2833                                                 format!("self.{}", path_str));
2834                         }
2835                         AssocSuggestion::MethodWithSelf | AssocSuggestion::AssocItem => {
2836                             err.span_suggestion(span, "try",
2837                                                 format!("Self::{}", path_str));
2838                         }
2839                     }
2840                     return (err, candidates);
2841                 }
2842             }
2843
2844             let mut levenshtein_worked = false;
2845
2846             // Try Levenshtein.
2847             if let Some(candidate) = this.lookup_typo_candidate(path, ns, is_expected, span) {
2848                 err.span_label(ident_span, format!("did you mean `{}`?", candidate));
2849                 levenshtein_worked = true;
2850             }
2851
2852             // Try context dependent help if relaxed lookup didn't work.
2853             if let Some(def) = def {
2854                 match (def, source) {
2855                     (Def::Macro(..), _) => {
2856                         err.span_label(span, format!("did you mean `{}!(...)`?", path_str));
2857                         return (err, candidates);
2858                     }
2859                     (Def::TyAlias(..), PathSource::Trait(_)) => {
2860                         err.span_label(span, "type aliases cannot be used for traits");
2861                         return (err, candidates);
2862                     }
2863                     (Def::Mod(..), PathSource::Expr(Some(parent))) => match parent.node {
2864                         ExprKind::Field(_, ident) => {
2865                             err.span_label(parent.span, format!("did you mean `{}::{}`?",
2866                                                                  path_str, ident.node));
2867                             return (err, candidates);
2868                         }
2869                         ExprKind::MethodCall(ref segment, ..) => {
2870                             err.span_label(parent.span, format!("did you mean `{}::{}(...)`?",
2871                                                                  path_str, segment.identifier));
2872                             return (err, candidates);
2873                         }
2874                         _ => {}
2875                     },
2876                     (Def::Enum(..), PathSource::TupleStruct)
2877                         | (Def::Enum(..), PathSource::Expr(..))  => {
2878                         if let Some(variants) = this.collect_enum_variants(def) {
2879                             err.note(&format!("did you mean to use one \
2880                                                of the following variants?\n{}",
2881                                 variants.iter()
2882                                     .map(|suggestion| path_names_to_string(suggestion))
2883                                     .map(|suggestion| format!("- `{}`", suggestion))
2884                                     .collect::<Vec<_>>()
2885                                     .join("\n")));
2886
2887                         } else {
2888                             err.note("did you mean to use one of the enum's variants?");
2889                         }
2890                         return (err, candidates);
2891                     },
2892                     (Def::Struct(def_id), _) if ns == ValueNS => {
2893                         if let Some((ctor_def, ctor_vis))
2894                                 = this.struct_constructors.get(&def_id).cloned() {
2895                             let accessible_ctor = this.is_accessible(ctor_vis);
2896                             if is_expected(ctor_def) && !accessible_ctor {
2897                                 err.span_label(span, format!("constructor is not visible \
2898                                                               here due to private fields"));
2899                             }
2900                         } else {
2901                             err.span_label(span, format!("did you mean `{} {{ /* fields */ }}`?",
2902                                                          path_str));
2903                         }
2904                         return (err, candidates);
2905                     }
2906                     (Def::Union(..), _) |
2907                     (Def::Variant(..), _) |
2908                     (Def::VariantCtor(_, CtorKind::Fictive), _) if ns == ValueNS => {
2909                         err.span_label(span, format!("did you mean `{} {{ /* fields */ }}`?",
2910                                                      path_str));
2911                         return (err, candidates);
2912                     }
2913                     (Def::SelfTy(..), _) if ns == ValueNS => {
2914                         err.span_label(span, fallback_label);
2915                         err.note("can't use `Self` as a constructor, you must use the \
2916                                   implemented struct");
2917                         return (err, candidates);
2918                     }
2919                     (Def::TyAlias(_), _) | (Def::AssociatedTy(..), _) if ns == ValueNS => {
2920                         err.note("can't use a type alias as a constructor");
2921                         return (err, candidates);
2922                     }
2923                     _ => {}
2924                 }
2925             }
2926
2927             // Fallback label.
2928             if !levenshtein_worked {
2929                 err.span_label(base_span, fallback_label);
2930                 this.type_ascription_suggestion(&mut err, base_span);
2931             }
2932             (err, candidates)
2933         };
2934         let report_errors = |this: &mut Self, def: Option<Def>| {
2935             let (err, candidates) = report_errors(this, def);
2936             let def_id = this.current_module.normal_ancestor_id;
2937             let node_id = this.definitions.as_local_node_id(def_id).unwrap();
2938             let better = def.is_some();
2939             this.use_injections.push(UseError { err, candidates, node_id, better });
2940             err_path_resolution()
2941         };
2942
2943         let resolution = match self.resolve_qpath_anywhere(id, qself, path, ns, span,
2944                                                            source.defer_to_typeck(),
2945                                                            source.global_by_default()) {
2946             Some(resolution) if resolution.unresolved_segments() == 0 => {
2947                 if is_expected(resolution.base_def()) || resolution.base_def() == Def::Err {
2948                     resolution
2949                 } else {
2950                     // Add a temporary hack to smooth the transition to new struct ctor
2951                     // visibility rules. See #38932 for more details.
2952                     let mut res = None;
2953                     if let Def::Struct(def_id) = resolution.base_def() {
2954                         if let Some((ctor_def, ctor_vis))
2955                                 = self.struct_constructors.get(&def_id).cloned() {
2956                             if is_expected(ctor_def) && self.is_accessible(ctor_vis) {
2957                                 let lint = lint::builtin::LEGACY_CONSTRUCTOR_VISIBILITY;
2958                                 self.session.buffer_lint(lint, id, span,
2959                                     "private struct constructors are not usable through \
2960                                      re-exports in outer modules",
2961                                 );
2962                                 res = Some(PathResolution::new(ctor_def));
2963                             }
2964                         }
2965                     }
2966
2967                     res.unwrap_or_else(|| report_errors(self, Some(resolution.base_def())))
2968                 }
2969             }
2970             Some(resolution) if source.defer_to_typeck() => {
2971                 // Not fully resolved associated item `T::A::B` or `<T as Tr>::A::B`
2972                 // or `<T>::A::B`. If `B` should be resolved in value namespace then
2973                 // it needs to be added to the trait map.
2974                 if ns == ValueNS {
2975                     let item_name = path.last().unwrap().node;
2976                     let traits = self.get_traits_containing_item(item_name, ns);
2977                     self.trait_map.insert(id, traits);
2978                 }
2979                 resolution
2980             }
2981             _ => report_errors(self, None)
2982         };
2983
2984         if let PathSource::TraitItem(..) = source {} else {
2985             // Avoid recording definition of `A::B` in `<T as A>::B::C`.
2986             self.record_def(id, resolution);
2987         }
2988         resolution
2989     }
2990
2991     fn type_ascription_suggestion(&self,
2992                                   err: &mut DiagnosticBuilder,
2993                                   base_span: Span) {
2994         debug!("type_ascription_suggetion {:?}", base_span);
2995         let cm = self.session.codemap();
2996         debug!("self.current_type_ascription {:?}", self.current_type_ascription);
2997         if let Some(sp) = self.current_type_ascription.last() {
2998             let mut sp = *sp;
2999             loop {  // try to find the `:`, bail on first non-':'/non-whitespace
3000                 sp = cm.next_point(sp);
3001                 if let Ok(snippet) = cm.span_to_snippet(sp.to(cm.next_point(sp))) {
3002                     debug!("snippet {:?}", snippet);
3003                     let line_sp = cm.lookup_char_pos(sp.hi()).line;
3004                     let line_base_sp = cm.lookup_char_pos(base_span.lo()).line;
3005                     debug!("{:?} {:?}", line_sp, line_base_sp);
3006                     if snippet == ":" {
3007                         err.span_label(base_span,
3008                                        "expecting a type here because of type ascription");
3009                         if line_sp != line_base_sp {
3010                             err.span_suggestion_short(sp,
3011                                                       "did you mean to use `;` here instead?",
3012                                                       ";".to_string());
3013                         }
3014                         break;
3015                     } else if snippet.trim().len() != 0  {
3016                         debug!("tried to find type ascription `:` token, couldn't find it");
3017                         break;
3018                     }
3019                 } else {
3020                     break;
3021                 }
3022             }
3023         }
3024     }
3025
3026     fn self_type_is_available(&mut self, span: Span) -> bool {
3027         let binding = self.resolve_ident_in_lexical_scope(keywords::SelfType.ident(),
3028                                                           TypeNS, false, span);
3029         if let Some(LexicalScopeBinding::Def(def)) = binding { def != Def::Err } else { false }
3030     }
3031
3032     fn self_value_is_available(&mut self, ctxt: SyntaxContext, span: Span) -> bool {
3033         let ident = Ident { name: keywords::SelfValue.name(), ctxt: ctxt };
3034         let binding = self.resolve_ident_in_lexical_scope(ident, ValueNS, false, span);
3035         if let Some(LexicalScopeBinding::Def(def)) = binding { def != Def::Err } else { false }
3036     }
3037
3038     // Resolve in alternative namespaces if resolution in the primary namespace fails.
3039     fn resolve_qpath_anywhere(&mut self,
3040                               id: NodeId,
3041                               qself: Option<&QSelf>,
3042                               path: &[SpannedIdent],
3043                               primary_ns: Namespace,
3044                               span: Span,
3045                               defer_to_typeck: bool,
3046                               global_by_default: bool)
3047                               -> Option<PathResolution> {
3048         let mut fin_res = None;
3049         // FIXME: can't resolve paths in macro namespace yet, macros are
3050         // processed by the little special hack below.
3051         for (i, ns) in [primary_ns, TypeNS, ValueNS, /*MacroNS*/].iter().cloned().enumerate() {
3052             if i == 0 || ns != primary_ns {
3053                 match self.resolve_qpath(id, qself, path, ns, span, global_by_default) {
3054                     // If defer_to_typeck, then resolution > no resolution,
3055                     // otherwise full resolution > partial resolution > no resolution.
3056                     Some(res) if res.unresolved_segments() == 0 || defer_to_typeck =>
3057                         return Some(res),
3058                     res => if fin_res.is_none() { fin_res = res },
3059                 };
3060             }
3061         }
3062         let is_global = self.global_macros.get(&path[0].node.name).cloned()
3063             .map(|binding| binding.get_macro(self).kind() == MacroKind::Bang).unwrap_or(false);
3064         if primary_ns != MacroNS && (is_global ||
3065                                      self.macro_names.contains(&path[0].node.modern())) {
3066             // Return some dummy definition, it's enough for error reporting.
3067             return Some(
3068                 PathResolution::new(Def::Macro(DefId::local(CRATE_DEF_INDEX), MacroKind::Bang))
3069             );
3070         }
3071         fin_res
3072     }
3073
3074     /// Handles paths that may refer to associated items.
3075     fn resolve_qpath(&mut self,
3076                      id: NodeId,
3077                      qself: Option<&QSelf>,
3078                      path: &[SpannedIdent],
3079                      ns: Namespace,
3080                      span: Span,
3081                      global_by_default: bool)
3082                      -> Option<PathResolution> {
3083         if let Some(qself) = qself {
3084             if qself.position == 0 {
3085                 // FIXME: Create some fake resolution that can't possibly be a type.
3086                 return Some(PathResolution::with_unresolved_segments(
3087                     Def::Mod(DefId::local(CRATE_DEF_INDEX)), path.len()
3088                 ));
3089             }
3090             // Make sure `A::B` in `<T as A>::B::C` is a trait item.
3091             let ns = if qself.position + 1 == path.len() { ns } else { TypeNS };
3092             let res = self.smart_resolve_path_fragment(id, None, &path[..qself.position + 1],
3093                                                        span, span, PathSource::TraitItem(ns));
3094             return Some(PathResolution::with_unresolved_segments(
3095                 res.base_def(), res.unresolved_segments() + path.len() - qself.position - 1
3096             ));
3097         }
3098
3099         let result = match self.resolve_path(&path, Some(ns), true, span) {
3100             PathResult::NonModule(path_res) => path_res,
3101             PathResult::Module(module) if !module.is_normal() => {
3102                 PathResolution::new(module.def().unwrap())
3103             }
3104             // In `a(::assoc_item)*` `a` cannot be a module. If `a` does resolve to a module we
3105             // don't report an error right away, but try to fallback to a primitive type.
3106             // So, we are still able to successfully resolve something like
3107             //
3108             // use std::u8; // bring module u8 in scope
3109             // fn f() -> u8 { // OK, resolves to primitive u8, not to std::u8
3110             //     u8::max_value() // OK, resolves to associated function <u8>::max_value,
3111             //                     // not to non-existent std::u8::max_value
3112             // }
3113             //
3114             // Such behavior is required for backward compatibility.
3115             // The same fallback is used when `a` resolves to nothing.
3116             PathResult::Module(..) | PathResult::Failed(..)
3117                     if (ns == TypeNS || path.len() > 1) &&
3118                        self.primitive_type_table.primitive_types
3119                            .contains_key(&path[0].node.name) => {
3120                 let prim = self.primitive_type_table.primitive_types[&path[0].node.name];
3121                 match prim {
3122                     TyUint(UintTy::U128) | TyInt(IntTy::I128) => {
3123                         if !self.session.features_untracked().i128_type {
3124                             emit_feature_err(&self.session.parse_sess,
3125                                                 "i128_type", span, GateIssue::Language,
3126                                                 "128-bit type is unstable");
3127
3128                         }
3129                     }
3130                     _ => {}
3131                 }
3132                 PathResolution::with_unresolved_segments(Def::PrimTy(prim), path.len() - 1)
3133             }
3134             PathResult::Module(module) => PathResolution::new(module.def().unwrap()),
3135             PathResult::Failed(span, msg, false) => {
3136                 resolve_error(self, span, ResolutionError::FailedToResolve(&msg));
3137                 err_path_resolution()
3138             }
3139             PathResult::Failed(..) => return None,
3140             PathResult::Indeterminate => bug!("indetermined path result in resolve_qpath"),
3141         };
3142
3143         if path.len() > 1 && !global_by_default && result.base_def() != Def::Err &&
3144            path[0].node.name != keywords::CrateRoot.name() &&
3145            path[0].node.name != keywords::DollarCrate.name() {
3146             let unqualified_result = {
3147                 match self.resolve_path(&[*path.last().unwrap()], Some(ns), false, span) {
3148                     PathResult::NonModule(path_res) => path_res.base_def(),
3149                     PathResult::Module(module) => module.def().unwrap(),
3150                     _ => return Some(result),
3151                 }
3152             };
3153             if result.base_def() == unqualified_result {
3154                 let lint = lint::builtin::UNUSED_QUALIFICATIONS;
3155                 self.session.buffer_lint(lint, id, span, "unnecessary qualification")
3156             }
3157         }
3158
3159         Some(result)
3160     }
3161
3162     fn resolve_path(&mut self,
3163                     path: &[SpannedIdent],
3164                     opt_ns: Option<Namespace>, // `None` indicates a module path
3165                     record_used: bool,
3166                     path_span: Span)
3167                     -> PathResult<'a> {
3168         let mut module = None;
3169         let mut allow_super = true;
3170
3171         for (i, &ident) in path.iter().enumerate() {
3172             debug!("resolve_path ident {} {:?}", i, ident);
3173             let is_last = i == path.len() - 1;
3174             let ns = if is_last { opt_ns.unwrap_or(TypeNS) } else { TypeNS };
3175             let name = ident.node.name;
3176
3177             if i == 0 && ns == TypeNS && name == keywords::SelfValue.name() {
3178                 let mut ctxt = ident.node.ctxt.modern();
3179                 module = Some(self.resolve_self(&mut ctxt, self.current_module));
3180                 continue
3181             } else if allow_super && ns == TypeNS && name == keywords::Super.name() {
3182                 let mut ctxt = ident.node.ctxt.modern();
3183                 let self_module = match i {
3184                     0 => self.resolve_self(&mut ctxt, self.current_module),
3185                     _ => module.unwrap(),
3186                 };
3187                 if let Some(parent) = self_module.parent {
3188                     module = Some(self.resolve_self(&mut ctxt, parent));
3189                     continue
3190                 } else {
3191                     let msg = "There are too many initial `super`s.".to_string();
3192                     return PathResult::Failed(ident.span, msg, false);
3193                 }
3194             } else if i == 0 && ns == TypeNS && name == keywords::Extern.name() {
3195                 continue;
3196             }
3197             allow_super = false;
3198
3199             if ns == TypeNS {
3200                 if (i == 0 && name == keywords::CrateRoot.name()) ||
3201                    (i == 1 && name == keywords::Crate.name() &&
3202                               path[0].node.name == keywords::CrateRoot.name()) {
3203                     // `::a::b` or `::crate::a::b`
3204                     module = Some(self.resolve_crate_root(ident.node.ctxt, false));
3205                     continue
3206                 } else if i == 0 && name == keywords::DollarCrate.name() {
3207                     // `$crate::a::b`
3208                     module = Some(self.resolve_crate_root(ident.node.ctxt, true));
3209                     continue
3210                 } else if i == 1 && !token::Ident(ident.node).is_path_segment_keyword() {
3211                     let prev_name = path[0].node.name;
3212                     if prev_name == keywords::Extern.name() ||
3213                        prev_name == keywords::CrateRoot.name() &&
3214                        self.session.features_untracked().extern_absolute_paths {
3215                         // `::extern_crate::a::b`
3216                         let crate_id = self.crate_loader.resolve_crate_from_path(name, ident.span);
3217                         let crate_root =
3218                             self.get_module(DefId { krate: crate_id, index: CRATE_DEF_INDEX });
3219                         self.populate_module_if_necessary(crate_root);
3220                         module = Some(crate_root);
3221                         continue
3222                     }
3223                 }
3224             }
3225
3226             // Report special messages for path segment keywords in wrong positions.
3227             if name == keywords::CrateRoot.name() && i != 0 ||
3228                name == keywords::DollarCrate.name() && i != 0 ||
3229                name == keywords::SelfValue.name() && i != 0 ||
3230                name == keywords::SelfType.name() && i != 0 ||
3231                name == keywords::Super.name() && i != 0 ||
3232                name == keywords::Extern.name() && i != 0 ||
3233                name == keywords::Crate.name() && i != 1 &&
3234                     path[0].node.name != keywords::CrateRoot.name() {
3235                 let name_str = if name == keywords::CrateRoot.name() {
3236                     format!("crate root")
3237                 } else {
3238                     format!("`{}`", name)
3239                 };
3240                 let msg = if i == 1 && path[0].node.name == keywords::CrateRoot.name() {
3241                     format!("global paths cannot start with {}", name_str)
3242                 } else if i == 0 && name == keywords::Crate.name() {
3243                     format!("{} can only be used in absolute paths", name_str)
3244                 } else {
3245                     format!("{} in paths can only be used in start position", name_str)
3246                 };
3247                 return PathResult::Failed(ident.span, msg, false);
3248             }
3249
3250             let binding = if let Some(module) = module {
3251                 self.resolve_ident_in_module(module, ident.node, ns, false, record_used, path_span)
3252             } else if opt_ns == Some(MacroNS) {
3253                 self.resolve_lexical_macro_path_segment(ident.node, ns, record_used, path_span)
3254                     .map(MacroBinding::binding)
3255             } else {
3256                 match self.resolve_ident_in_lexical_scope(ident.node, ns, record_used, path_span) {
3257                     Some(LexicalScopeBinding::Item(binding)) => Ok(binding),
3258                     Some(LexicalScopeBinding::Def(def))
3259                             if opt_ns == Some(TypeNS) || opt_ns == Some(ValueNS) => {
3260                         return PathResult::NonModule(PathResolution::with_unresolved_segments(
3261                             def, path.len() - 1
3262                         ));
3263                     }
3264                     _ => Err(if record_used { Determined } else { Undetermined }),
3265                 }
3266             };
3267
3268             match binding {
3269                 Ok(binding) => {
3270                     let def = binding.def();
3271                     let maybe_assoc = opt_ns != Some(MacroNS) && PathSource::Type.is_expected(def);
3272                     if let Some(next_module) = binding.module() {
3273                         module = Some(next_module);
3274                     } else if def == Def::Err {
3275                         return PathResult::NonModule(err_path_resolution());
3276                     } else if opt_ns.is_some() && (is_last || maybe_assoc) {
3277                         return PathResult::NonModule(PathResolution::with_unresolved_segments(
3278                             def, path.len() - i - 1
3279                         ));
3280                     } else {
3281                         return PathResult::Failed(ident.span,
3282                                                   format!("Not a module `{}`", ident.node),
3283                                                   is_last);
3284                     }
3285                 }
3286                 Err(Undetermined) => return PathResult::Indeterminate,
3287                 Err(Determined) => {
3288                     if let Some(module) = module {
3289                         if opt_ns.is_some() && !module.is_normal() {
3290                             return PathResult::NonModule(PathResolution::with_unresolved_segments(
3291                                 module.def().unwrap(), path.len() - i
3292                             ));
3293                         }
3294                     }
3295                     let msg = if module.and_then(ModuleData::def) == self.graph_root.def() {
3296                         let is_mod = |def| match def { Def::Mod(..) => true, _ => false };
3297                         let mut candidates =
3298                             self.lookup_import_candidates(name, TypeNS, is_mod);
3299                         candidates.sort_by_key(|c| (c.path.segments.len(), c.path.to_string()));
3300                         if let Some(candidate) = candidates.get(0) {
3301                             format!("Did you mean `{}`?", candidate.path)
3302                         } else {
3303                             format!("Maybe a missing `extern crate {};`?", ident.node)
3304                         }
3305                     } else if i == 0 {
3306                         format!("Use of undeclared type or module `{}`", ident.node)
3307                     } else {
3308                         format!("Could not find `{}` in `{}`", ident.node, path[i - 1].node)
3309                     };
3310                     return PathResult::Failed(ident.span, msg, is_last);
3311                 }
3312             }
3313         }
3314
3315         PathResult::Module(module.unwrap_or(self.graph_root))
3316     }
3317
3318     // Resolve a local definition, potentially adjusting for closures.
3319     fn adjust_local_def(&mut self,
3320                         ns: Namespace,
3321                         rib_index: usize,
3322                         mut def: Def,
3323                         record_used: bool,
3324                         span: Span) -> Def {
3325         let ribs = &self.ribs[ns][rib_index + 1..];
3326
3327         // An invalid forward use of a type parameter from a previous default.
3328         if let ForwardTyParamBanRibKind = self.ribs[ns][rib_index].kind {
3329             if record_used {
3330                 resolve_error(self, span, ResolutionError::ForwardDeclaredTyParam);
3331             }
3332             assert_eq!(def, Def::Err);
3333             return Def::Err;
3334         }
3335
3336         match def {
3337             Def::Upvar(..) => {
3338                 span_bug!(span, "unexpected {:?} in bindings", def)
3339             }
3340             Def::Local(node_id) => {
3341                 for rib in ribs {
3342                     match rib.kind {
3343                         NormalRibKind | ModuleRibKind(..) | MacroDefinition(..) |
3344                         ForwardTyParamBanRibKind => {
3345                             // Nothing to do. Continue.
3346                         }
3347                         ClosureRibKind(function_id) => {
3348                             let prev_def = def;
3349
3350                             let seen = self.freevars_seen
3351                                            .entry(function_id)
3352                                            .or_insert_with(|| NodeMap());
3353                             if let Some(&index) = seen.get(&node_id) {
3354                                 def = Def::Upvar(node_id, index, function_id);
3355                                 continue;
3356                             }
3357                             let vec = self.freevars
3358                                           .entry(function_id)
3359                                           .or_insert_with(|| vec![]);
3360                             let depth = vec.len();
3361                             def = Def::Upvar(node_id, depth, function_id);
3362
3363                             if record_used {
3364                                 vec.push(Freevar {
3365                                     def: prev_def,
3366                                     span,
3367                                 });
3368                                 seen.insert(node_id, depth);
3369                             }
3370                         }
3371                         ItemRibKind | TraitOrImplItemRibKind => {
3372                             // This was an attempt to access an upvar inside a
3373                             // named function item. This is not allowed, so we
3374                             // report an error.
3375                             if record_used {
3376                                 resolve_error(self, span,
3377                                         ResolutionError::CannotCaptureDynamicEnvironmentInFnItem);
3378                             }
3379                             return Def::Err;
3380                         }
3381                         ConstantItemRibKind => {
3382                             // Still doesn't deal with upvars
3383                             if record_used {
3384                                 resolve_error(self, span,
3385                                         ResolutionError::AttemptToUseNonConstantValueInConstant);
3386                             }
3387                             return Def::Err;
3388                         }
3389                     }
3390                 }
3391             }
3392             Def::TyParam(..) | Def::SelfTy(..) => {
3393                 for rib in ribs {
3394                     match rib.kind {
3395                         NormalRibKind | TraitOrImplItemRibKind | ClosureRibKind(..) |
3396                         ModuleRibKind(..) | MacroDefinition(..) | ForwardTyParamBanRibKind |
3397                         ConstantItemRibKind => {
3398                             // Nothing to do. Continue.
3399                         }
3400                         ItemRibKind => {
3401                             // This was an attempt to use a type parameter outside
3402                             // its scope.
3403                             if record_used {
3404                                 resolve_error(self, span,
3405                                     ResolutionError::TypeParametersFromOuterFunction(def));
3406                             }
3407                             return Def::Err;
3408                         }
3409                     }
3410                 }
3411             }
3412             _ => {}
3413         }
3414         return def;
3415     }
3416
3417     fn lookup_assoc_candidate<FilterFn>(&mut self,
3418                                         ident: Ident,
3419                                         ns: Namespace,
3420                                         filter_fn: FilterFn)
3421                                         -> Option<AssocSuggestion>
3422         where FilterFn: Fn(Def) -> bool
3423     {
3424         fn extract_node_id(t: &Ty) -> Option<NodeId> {
3425             match t.node {
3426                 TyKind::Path(None, _) => Some(t.id),
3427                 TyKind::Rptr(_, ref mut_ty) => extract_node_id(&mut_ty.ty),
3428                 // This doesn't handle the remaining `Ty` variants as they are not
3429                 // that commonly the self_type, it might be interesting to provide
3430                 // support for those in future.
3431                 _ => None,
3432             }
3433         }
3434
3435         // Fields are generally expected in the same contexts as locals.
3436         if filter_fn(Def::Local(ast::DUMMY_NODE_ID)) {
3437             if let Some(node_id) = self.current_self_type.as_ref().and_then(extract_node_id) {
3438                 // Look for a field with the same name in the current self_type.
3439                 if let Some(resolution) = self.def_map.get(&node_id) {
3440                     match resolution.base_def() {
3441                         Def::Struct(did) | Def::Union(did)
3442                                 if resolution.unresolved_segments() == 0 => {
3443                             if let Some(field_names) = self.field_names.get(&did) {
3444                                 if field_names.iter().any(|&field_name| ident.name == field_name) {
3445                                     return Some(AssocSuggestion::Field);
3446                                 }
3447                             }
3448                         }
3449                         _ => {}
3450                     }
3451                 }
3452             }
3453         }
3454
3455         // Look for associated items in the current trait.
3456         if let Some((module, _)) = self.current_trait_ref {
3457             if let Ok(binding) =
3458                     self.resolve_ident_in_module(module, ident, ns, false, false, module.span) {
3459                 let def = binding.def();
3460                 if filter_fn(def) {
3461                     return Some(if self.has_self.contains(&def.def_id()) {
3462                         AssocSuggestion::MethodWithSelf
3463                     } else {
3464                         AssocSuggestion::AssocItem
3465                     });
3466                 }
3467             }
3468         }
3469
3470         None
3471     }
3472
3473     fn lookup_typo_candidate<FilterFn>(&mut self,
3474                                        path: &[SpannedIdent],
3475                                        ns: Namespace,
3476                                        filter_fn: FilterFn,
3477                                        span: Span)
3478                                        -> Option<Symbol>
3479         where FilterFn: Fn(Def) -> bool
3480     {
3481         let add_module_candidates = |module: Module, names: &mut Vec<Name>| {
3482             for (&(ident, _), resolution) in module.resolutions.borrow().iter() {
3483                 if let Some(binding) = resolution.borrow().binding {
3484                     if filter_fn(binding.def()) {
3485                         names.push(ident.name);
3486                     }
3487                 }
3488             }
3489         };
3490
3491         let mut names = Vec::new();
3492         if path.len() == 1 {
3493             // Search in lexical scope.
3494             // Walk backwards up the ribs in scope and collect candidates.
3495             for rib in self.ribs[ns].iter().rev() {
3496                 // Locals and type parameters
3497                 for (ident, def) in &rib.bindings {
3498                     if filter_fn(*def) {
3499                         names.push(ident.name);
3500                     }
3501                 }
3502                 // Items in scope
3503                 if let ModuleRibKind(module) = rib.kind {
3504                     // Items from this module
3505                     add_module_candidates(module, &mut names);
3506
3507                     if let ModuleKind::Block(..) = module.kind {
3508                         // We can see through blocks
3509                     } else {
3510                         // Items from the prelude
3511                         if let Some(prelude) = self.prelude {
3512                             if !module.no_implicit_prelude {
3513                                 add_module_candidates(prelude, &mut names);
3514                             }
3515                         }
3516                         break;
3517                     }
3518                 }
3519             }
3520             // Add primitive types to the mix
3521             if filter_fn(Def::PrimTy(TyBool)) {
3522                 for (name, _) in &self.primitive_type_table.primitive_types {
3523                     names.push(*name);
3524                 }
3525             }
3526         } else {
3527             // Search in module.
3528             let mod_path = &path[..path.len() - 1];
3529             if let PathResult::Module(module) = self.resolve_path(mod_path, Some(TypeNS),
3530                                                                   false, span) {
3531                 add_module_candidates(module, &mut names);
3532             }
3533         }
3534
3535         let name = path[path.len() - 1].node.name;
3536         // Make sure error reporting is deterministic.
3537         names.sort_by_key(|name| name.as_str());
3538         match find_best_match_for_name(names.iter(), &name.as_str(), None) {
3539             Some(found) if found != name => Some(found),
3540             _ => None,
3541         }
3542     }
3543
3544     fn with_resolved_label<F>(&mut self, label: Option<Label>, id: NodeId, f: F)
3545         where F: FnOnce(&mut Resolver)
3546     {
3547         if let Some(label) = label {
3548             let def = Def::Label(id);
3549             self.with_label_rib(|this| {
3550                 this.label_ribs.last_mut().unwrap().bindings.insert(label.ident, def);
3551                 f(this);
3552             });
3553         } else {
3554             f(self);
3555         }
3556     }
3557
3558     fn resolve_labeled_block(&mut self, label: Option<Label>, id: NodeId, block: &Block) {
3559         self.with_resolved_label(label, id, |this| this.visit_block(block));
3560     }
3561
3562     fn resolve_expr(&mut self, expr: &Expr, parent: Option<&Expr>) {
3563         // First, record candidate traits for this expression if it could
3564         // result in the invocation of a method call.
3565
3566         self.record_candidate_traits_for_expr_if_necessary(expr);
3567
3568         // Next, resolve the node.
3569         match expr.node {
3570             ExprKind::Path(ref qself, ref path) => {
3571                 self.smart_resolve_path(expr.id, qself.as_ref(), path, PathSource::Expr(parent));
3572                 visit::walk_expr(self, expr);
3573             }
3574
3575             ExprKind::Struct(ref path, ..) => {
3576                 self.smart_resolve_path(expr.id, None, path, PathSource::Struct);
3577                 visit::walk_expr(self, expr);
3578             }
3579
3580             ExprKind::Break(Some(label), _) | ExprKind::Continue(Some(label)) => {
3581                 match self.search_label(label.ident, |rib, id| rib.bindings.get(&id).cloned()) {
3582                     None => {
3583                         // Search again for close matches...
3584                         // Picks the first label that is "close enough", which is not necessarily
3585                         // the closest match
3586                         let close_match = self.search_label(label.ident, |rib, ident| {
3587                             let names = rib.bindings.iter().map(|(id, _)| &id.name);
3588                             find_best_match_for_name(names, &*ident.name.as_str(), None)
3589                         });
3590                         self.record_def(expr.id, err_path_resolution());
3591                         resolve_error(self,
3592                                       label.span,
3593                                       ResolutionError::UndeclaredLabel(&label.ident.name.as_str(),
3594                                                                        close_match));
3595                     }
3596                     Some(def @ Def::Label(_)) => {
3597                         // Since this def is a label, it is never read.
3598                         self.record_def(expr.id, PathResolution::new(def));
3599                     }
3600                     Some(_) => {
3601                         span_bug!(expr.span, "label wasn't mapped to a label def!");
3602                     }
3603                 }
3604
3605                 // visit `break` argument if any
3606                 visit::walk_expr(self, expr);
3607             }
3608
3609             ExprKind::IfLet(ref pats, ref subexpression, ref if_block, ref optional_else) => {
3610                 self.visit_expr(subexpression);
3611
3612                 self.ribs[ValueNS].push(Rib::new(NormalRibKind));
3613                 let mut bindings_list = FxHashMap();
3614                 for pat in pats {
3615                     self.resolve_pattern(pat, PatternSource::IfLet, &mut bindings_list);
3616                 }
3617                 // This has to happen *after* we determine which pat_idents are variants
3618                 self.check_consistent_bindings(pats);
3619                 self.visit_block(if_block);
3620                 self.ribs[ValueNS].pop();
3621
3622                 optional_else.as_ref().map(|expr| self.visit_expr(expr));
3623             }
3624
3625             ExprKind::Loop(ref block, label) => self.resolve_labeled_block(label, expr.id, &block),
3626
3627             ExprKind::While(ref subexpression, ref block, label) => {
3628                 self.with_resolved_label(label, expr.id, |this| {
3629                     this.visit_expr(subexpression);
3630                     this.visit_block(block);
3631                 });
3632             }
3633
3634             ExprKind::WhileLet(ref pats, ref subexpression, ref block, label) => {
3635                 self.with_resolved_label(label, expr.id, |this| {
3636                     this.visit_expr(subexpression);
3637                     this.ribs[ValueNS].push(Rib::new(NormalRibKind));
3638                     let mut bindings_list = FxHashMap();
3639                     for pat in pats {
3640                         this.resolve_pattern(pat, PatternSource::WhileLet, &mut bindings_list);
3641                     }
3642                     // This has to happen *after* we determine which pat_idents are variants
3643                     this.check_consistent_bindings(pats);
3644                     this.visit_block(block);
3645                     this.ribs[ValueNS].pop();
3646                 });
3647             }
3648
3649             ExprKind::ForLoop(ref pattern, ref subexpression, ref block, label) => {
3650                 self.visit_expr(subexpression);
3651                 self.ribs[ValueNS].push(Rib::new(NormalRibKind));
3652                 self.resolve_pattern(pattern, PatternSource::For, &mut FxHashMap());
3653
3654                 self.resolve_labeled_block(label, expr.id, block);
3655
3656                 self.ribs[ValueNS].pop();
3657             }
3658
3659             // Equivalent to `visit::walk_expr` + passing some context to children.
3660             ExprKind::Field(ref subexpression, _) => {
3661                 self.resolve_expr(subexpression, Some(expr));
3662             }
3663             ExprKind::MethodCall(ref segment, ref arguments) => {
3664                 let mut arguments = arguments.iter();
3665                 self.resolve_expr(arguments.next().unwrap(), Some(expr));
3666                 for argument in arguments {
3667                     self.resolve_expr(argument, None);
3668                 }
3669                 self.visit_path_segment(expr.span, segment);
3670             }
3671
3672             ExprKind::Repeat(ref element, ref count) => {
3673                 self.visit_expr(element);
3674                 self.with_constant_rib(|this| {
3675                     this.visit_expr(count);
3676                 });
3677             }
3678             ExprKind::Call(ref callee, ref arguments) => {
3679                 self.resolve_expr(callee, Some(expr));
3680                 for argument in arguments {
3681                     self.resolve_expr(argument, None);
3682                 }
3683             }
3684             ExprKind::Type(ref type_expr, _) => {
3685                 self.current_type_ascription.push(type_expr.span);
3686                 visit::walk_expr(self, expr);
3687                 self.current_type_ascription.pop();
3688             }
3689             _ => {
3690                 visit::walk_expr(self, expr);
3691             }
3692         }
3693     }
3694
3695     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
3696         match expr.node {
3697             ExprKind::Field(_, name) => {
3698                 // FIXME(#6890): Even though you can't treat a method like a
3699                 // field, we need to add any trait methods we find that match
3700                 // the field name so that we can do some nice error reporting
3701                 // later on in typeck.
3702                 let traits = self.get_traits_containing_item(name.node, ValueNS);
3703                 self.trait_map.insert(expr.id, traits);
3704             }
3705             ExprKind::MethodCall(ref segment, ..) => {
3706                 debug!("(recording candidate traits for expr) recording traits for {}",
3707                        expr.id);
3708                 let traits = self.get_traits_containing_item(segment.identifier, ValueNS);
3709                 self.trait_map.insert(expr.id, traits);
3710             }
3711             _ => {
3712                 // Nothing to do.
3713             }
3714         }
3715     }
3716
3717     fn get_traits_containing_item(&mut self, mut ident: Ident, ns: Namespace)
3718                                   -> Vec<TraitCandidate> {
3719         debug!("(getting traits containing item) looking for '{}'", ident.name);
3720
3721         let mut found_traits = Vec::new();
3722         // Look for the current trait.
3723         if let Some((module, _)) = self.current_trait_ref {
3724             if self.resolve_ident_in_module(module, ident, ns, false, false, module.span).is_ok() {
3725                 let def_id = module.def_id().unwrap();
3726                 found_traits.push(TraitCandidate { def_id: def_id, import_id: None });
3727             }
3728         }
3729
3730         ident.ctxt = ident.ctxt.modern();
3731         let mut search_module = self.current_module;
3732         loop {
3733             self.get_traits_in_module_containing_item(ident, ns, search_module, &mut found_traits);
3734             search_module =
3735                 unwrap_or!(self.hygienic_lexical_parent(search_module, &mut ident.ctxt), break);
3736         }
3737
3738         if let Some(prelude) = self.prelude {
3739             if !search_module.no_implicit_prelude {
3740                 self.get_traits_in_module_containing_item(ident, ns, prelude, &mut found_traits);
3741             }
3742         }
3743
3744         found_traits
3745     }
3746
3747     fn get_traits_in_module_containing_item(&mut self,
3748                                             ident: Ident,
3749                                             ns: Namespace,
3750                                             module: Module<'a>,
3751                                             found_traits: &mut Vec<TraitCandidate>) {
3752         let mut traits = module.traits.borrow_mut();
3753         if traits.is_none() {
3754             let mut collected_traits = Vec::new();
3755             module.for_each_child(|name, ns, binding| {
3756                 if ns != TypeNS { return }
3757                 if let Def::Trait(_) = binding.def() {
3758                     collected_traits.push((name, binding));
3759                 }
3760             });
3761             *traits = Some(collected_traits.into_boxed_slice());
3762         }
3763
3764         for &(trait_name, binding) in traits.as_ref().unwrap().iter() {
3765             let module = binding.module().unwrap();
3766             let mut ident = ident;
3767             if ident.ctxt.glob_adjust(module.expansion, binding.span.ctxt().modern()).is_none() {
3768                 continue
3769             }
3770             if self.resolve_ident_in_module_unadjusted(module, ident, ns, false, false, module.span)
3771                    .is_ok() {
3772                 let import_id = match binding.kind {
3773                     NameBindingKind::Import { directive, .. } => {
3774                         self.maybe_unused_trait_imports.insert(directive.id);
3775                         self.add_to_glob_map(directive.id, trait_name);
3776                         Some(directive.id)
3777                     }
3778                     _ => None,
3779                 };
3780                 let trait_def_id = module.def_id().unwrap();
3781                 found_traits.push(TraitCandidate { def_id: trait_def_id, import_id: import_id });
3782             }
3783         }
3784     }
3785
3786     /// When name resolution fails, this method can be used to look up candidate
3787     /// entities with the expected name. It allows filtering them using the
3788     /// supplied predicate (which should be used to only accept the types of
3789     /// definitions expected e.g. traits). The lookup spans across all crates.
3790     ///
3791     /// NOTE: The method does not look into imports, but this is not a problem,
3792     /// since we report the definitions (thus, the de-aliased imports).
3793     fn lookup_import_candidates<FilterFn>(&mut self,
3794                                           lookup_name: Name,
3795                                           namespace: Namespace,
3796                                           filter_fn: FilterFn)
3797                                           -> Vec<ImportSuggestion>
3798         where FilterFn: Fn(Def) -> bool
3799     {
3800         let mut candidates = Vec::new();
3801         let mut worklist = Vec::new();
3802         let mut seen_modules = FxHashSet();
3803         worklist.push((self.graph_root, Vec::new(), false));
3804
3805         while let Some((in_module,
3806                         path_segments,
3807                         in_module_is_extern)) = worklist.pop() {
3808             self.populate_module_if_necessary(in_module);
3809
3810             // We have to visit module children in deterministic order to avoid
3811             // instabilities in reported imports (#43552).
3812             in_module.for_each_child_stable(|ident, ns, name_binding| {
3813                 // avoid imports entirely
3814                 if name_binding.is_import() && !name_binding.is_extern_crate() { return; }
3815                 // avoid non-importable candidates as well
3816                 if !name_binding.is_importable() { return; }
3817
3818                 // collect results based on the filter function
3819                 if ident.name == lookup_name && ns == namespace {
3820                     if filter_fn(name_binding.def()) {
3821                         // create the path
3822                         let mut segms = path_segments.clone();
3823                         segms.push(ast::PathSegment::from_ident(ident, name_binding.span));
3824                         let path = Path {
3825                             span: name_binding.span,
3826                             segments: segms,
3827                         };
3828                         // the entity is accessible in the following cases:
3829                         // 1. if it's defined in the same crate, it's always
3830                         // accessible (since private entities can be made public)
3831                         // 2. if it's defined in another crate, it's accessible
3832                         // only if both the module is public and the entity is
3833                         // declared as public (due to pruning, we don't explore
3834                         // outside crate private modules => no need to check this)
3835                         if !in_module_is_extern || name_binding.vis == ty::Visibility::Public {
3836                             candidates.push(ImportSuggestion { path: path });
3837                         }
3838                     }
3839                 }
3840
3841                 // collect submodules to explore
3842                 if let Some(module) = name_binding.module() {
3843                     // form the path
3844                     let mut path_segments = path_segments.clone();
3845                     path_segments.push(ast::PathSegment::from_ident(ident, name_binding.span));
3846
3847                     if !in_module_is_extern || name_binding.vis == ty::Visibility::Public {
3848                         // add the module to the lookup
3849                         let is_extern = in_module_is_extern || name_binding.is_extern_crate();
3850                         if seen_modules.insert(module.def_id().unwrap()) {
3851                             worklist.push((module, path_segments, is_extern));
3852                         }
3853                     }
3854                 }
3855             })
3856         }
3857
3858         candidates
3859     }
3860
3861     fn find_module(&mut self,
3862                    module_def: Def)
3863                    -> Option<(Module<'a>, ImportSuggestion)>
3864     {
3865         let mut result = None;
3866         let mut worklist = Vec::new();
3867         let mut seen_modules = FxHashSet();
3868         worklist.push((self.graph_root, Vec::new()));
3869
3870         while let Some((in_module, path_segments)) = worklist.pop() {
3871             // abort if the module is already found
3872             if let Some(_) = result { break; }
3873
3874             self.populate_module_if_necessary(in_module);
3875
3876             in_module.for_each_child_stable(|ident, _, name_binding| {
3877                 // abort if the module is already found or if name_binding is private external
3878                 if result.is_some() || !name_binding.vis.is_visible_locally() {
3879                     return
3880                 }
3881                 if let Some(module) = name_binding.module() {
3882                     // form the path
3883                     let mut path_segments = path_segments.clone();
3884                     path_segments.push(ast::PathSegment::from_ident(ident, name_binding.span));
3885                     if module.def() == Some(module_def) {
3886                         let path = Path {
3887                             span: name_binding.span,
3888                             segments: path_segments,
3889                         };
3890                         result = Some((module, ImportSuggestion { path: path }));
3891                     } else {
3892                         // add the module to the lookup
3893                         if seen_modules.insert(module.def_id().unwrap()) {
3894                             worklist.push((module, path_segments));
3895                         }
3896                     }
3897                 }
3898             });
3899         }
3900
3901         result
3902     }
3903
3904     fn collect_enum_variants(&mut self, enum_def: Def) -> Option<Vec<Path>> {
3905         if let Def::Enum(..) = enum_def {} else {
3906             panic!("Non-enum def passed to collect_enum_variants: {:?}", enum_def)
3907         }
3908
3909         self.find_module(enum_def).map(|(enum_module, enum_import_suggestion)| {
3910             self.populate_module_if_necessary(enum_module);
3911
3912             let mut variants = Vec::new();
3913             enum_module.for_each_child_stable(|ident, _, name_binding| {
3914                 if let Def::Variant(..) = name_binding.def() {
3915                     let mut segms = enum_import_suggestion.path.segments.clone();
3916                     segms.push(ast::PathSegment::from_ident(ident, name_binding.span));
3917                     variants.push(Path {
3918                         span: name_binding.span,
3919                         segments: segms,
3920                     });
3921                 }
3922             });
3923             variants
3924         })
3925     }
3926
3927     fn record_def(&mut self, node_id: NodeId, resolution: PathResolution) {
3928         debug!("(recording def) recording {:?} for {}", resolution, node_id);
3929         if let Some(prev_res) = self.def_map.insert(node_id, resolution) {
3930             panic!("path resolved multiple times ({:?} before, {:?} now)", prev_res, resolution);
3931         }
3932     }
3933
3934     fn resolve_visibility(&mut self, vis: &ast::Visibility) -> ty::Visibility {
3935         match vis.node {
3936             ast::VisibilityKind::Public => ty::Visibility::Public,
3937             ast::VisibilityKind::Crate(..) => {
3938                 ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX))
3939             }
3940             ast::VisibilityKind::Inherited => {
3941                 ty::Visibility::Restricted(self.current_module.normal_ancestor_id)
3942             }
3943             ast::VisibilityKind::Restricted { ref path, id, .. } => {
3944                 let def = self.smart_resolve_path(id, None, path,
3945                                                   PathSource::Visibility).base_def();
3946                 if def == Def::Err {
3947                     ty::Visibility::Public
3948                 } else {
3949                     let vis = ty::Visibility::Restricted(def.def_id());
3950                     if self.is_accessible(vis) {
3951                         vis
3952                     } else {
3953                         self.session.span_err(path.span, "visibilities can only be restricted \
3954                                                           to ancestor modules");
3955                         ty::Visibility::Public
3956                     }
3957                 }
3958             }
3959         }
3960     }
3961
3962     fn is_accessible(&self, vis: ty::Visibility) -> bool {
3963         vis.is_accessible_from(self.current_module.normal_ancestor_id, self)
3964     }
3965
3966     fn is_accessible_from(&self, vis: ty::Visibility, module: Module<'a>) -> bool {
3967         vis.is_accessible_from(module.normal_ancestor_id, self)
3968     }
3969
3970     fn report_errors(&mut self, krate: &Crate) {
3971         self.report_shadowing_errors();
3972         self.report_with_use_injections(krate);
3973         self.report_proc_macro_import(krate);
3974         let mut reported_spans = FxHashSet();
3975
3976         for &AmbiguityError { span, name, b1, b2, lexical, legacy } in &self.ambiguity_errors {
3977             if !reported_spans.insert(span) { continue }
3978             let participle = |binding: &NameBinding| {
3979                 if binding.is_import() { "imported" } else { "defined" }
3980             };
3981             let msg1 = format!("`{}` could refer to the name {} here", name, participle(b1));
3982             let msg2 = format!("`{}` could also refer to the name {} here", name, participle(b2));
3983             let note = if b1.expansion == Mark::root() || !lexical && b1.is_glob_import() {
3984                 format!("consider adding an explicit import of `{}` to disambiguate", name)
3985             } else if let Def::Macro(..) = b1.def() {
3986                 format!("macro-expanded {} do not shadow",
3987                         if b1.is_import() { "macro imports" } else { "macros" })
3988             } else {
3989                 format!("macro-expanded {} do not shadow when used in a macro invocation path",
3990                         if b1.is_import() { "imports" } else { "items" })
3991             };
3992             if legacy {
3993                 let id = match b2.kind {
3994                     NameBindingKind::Import { directive, .. } => directive.id,
3995                     _ => unreachable!(),
3996                 };
3997                 let mut span = MultiSpan::from_span(span);
3998                 span.push_span_label(b1.span, msg1);
3999                 span.push_span_label(b2.span, msg2);
4000                 let msg = format!("`{}` is ambiguous", name);
4001                 self.session.buffer_lint(lint::builtin::LEGACY_IMPORTS, id, span, &msg);
4002             } else {
4003                 let mut err =
4004                     struct_span_err!(self.session, span, E0659, "`{}` is ambiguous", name);
4005                 err.span_note(b1.span, &msg1);
4006                 match b2.def() {
4007                     Def::Macro(..) if b2.span == DUMMY_SP =>
4008                         err.note(&format!("`{}` is also a builtin macro", name)),
4009                     _ => err.span_note(b2.span, &msg2),
4010                 };
4011                 err.note(&note).emit();
4012             }
4013         }
4014
4015         for &PrivacyError(span, name, binding) in &self.privacy_errors {
4016             if !reported_spans.insert(span) { continue }
4017             span_err!(self.session, span, E0603, "{} `{}` is private", binding.descr(), name);
4018         }
4019     }
4020
4021     fn report_with_use_injections(&mut self, krate: &Crate) {
4022         for UseError { mut err, candidates, node_id, better } in self.use_injections.drain(..) {
4023             let (span, found_use) = UsePlacementFinder::check(krate, node_id);
4024             if !candidates.is_empty() {
4025                 show_candidates(&mut err, span, &candidates, better, found_use);
4026             }
4027             err.emit();
4028         }
4029     }
4030
4031     fn report_shadowing_errors(&mut self) {
4032         for (ident, scope) in replace(&mut self.lexical_macro_resolutions, Vec::new()) {
4033             self.resolve_legacy_scope(scope, ident, true);
4034         }
4035
4036         let mut reported_errors = FxHashSet();
4037         for binding in replace(&mut self.disallowed_shadowing, Vec::new()) {
4038             if self.resolve_legacy_scope(&binding.parent, binding.ident, false).is_some() &&
4039                reported_errors.insert((binding.ident, binding.span)) {
4040                 let msg = format!("`{}` is already in scope", binding.ident);
4041                 self.session.struct_span_err(binding.span, &msg)
4042                     .note("macro-expanded `macro_rules!`s may not shadow \
4043                            existing macros (see RFC 1560)")
4044                     .emit();
4045             }
4046         }
4047     }
4048
4049     fn report_conflict<'b>(&mut self,
4050                        parent: Module,
4051                        ident: Ident,
4052                        ns: Namespace,
4053                        new_binding: &NameBinding<'b>,
4054                        old_binding: &NameBinding<'b>) {
4055         // Error on the second of two conflicting names
4056         if old_binding.span.lo() > new_binding.span.lo() {
4057             return self.report_conflict(parent, ident, ns, old_binding, new_binding);
4058         }
4059
4060         let container = match parent.kind {
4061             ModuleKind::Def(Def::Mod(_), _) => "module",
4062             ModuleKind::Def(Def::Trait(_), _) => "trait",
4063             ModuleKind::Block(..) => "block",
4064             _ => "enum",
4065         };
4066
4067         let old_noun = match old_binding.is_import() {
4068             true => "import",
4069             false => "definition",
4070         };
4071
4072         let new_participle = match new_binding.is_import() {
4073             true => "imported",
4074             false => "defined",
4075         };
4076
4077         let (name, span) = (ident.name, self.session.codemap().def_span(new_binding.span));
4078
4079         if let Some(s) = self.name_already_seen.get(&name) {
4080             if s == &span {
4081                 return;
4082             }
4083         }
4084
4085         let old_kind = match (ns, old_binding.module()) {
4086             (ValueNS, _) => "value",
4087             (MacroNS, _) => "macro",
4088             (TypeNS, _) if old_binding.is_extern_crate() => "extern crate",
4089             (TypeNS, Some(module)) if module.is_normal() => "module",
4090             (TypeNS, Some(module)) if module.is_trait() => "trait",
4091             (TypeNS, _) => "type",
4092         };
4093
4094         let namespace = match ns {
4095             ValueNS => "value",
4096             MacroNS => "macro",
4097             TypeNS => "type",
4098         };
4099
4100         let msg = format!("the name `{}` is defined multiple times", name);
4101
4102         let mut err = match (old_binding.is_extern_crate(), new_binding.is_extern_crate()) {
4103             (true, true) => struct_span_err!(self.session, span, E0259, "{}", msg),
4104             (true, _) | (_, true) => match new_binding.is_import() && old_binding.is_import() {
4105                 true => struct_span_err!(self.session, span, E0254, "{}", msg),
4106                 false => struct_span_err!(self.session, span, E0260, "{}", msg),
4107             },
4108             _ => match (old_binding.is_import(), new_binding.is_import()) {
4109                 (false, false) => struct_span_err!(self.session, span, E0428, "{}", msg),
4110                 (true, true) => struct_span_err!(self.session, span, E0252, "{}", msg),
4111                 _ => struct_span_err!(self.session, span, E0255, "{}", msg),
4112             },
4113         };
4114
4115         err.note(&format!("`{}` must be defined only once in the {} namespace of this {}",
4116                           name,
4117                           namespace,
4118                           container));
4119
4120         err.span_label(span, format!("`{}` re{} here", name, new_participle));
4121         if old_binding.span != DUMMY_SP {
4122             err.span_label(self.session.codemap().def_span(old_binding.span),
4123                            format!("previous {} of the {} `{}` here", old_noun, old_kind, name));
4124         }
4125
4126         // See https://github.com/rust-lang/rust/issues/32354
4127         if old_binding.is_import() || new_binding.is_import() {
4128             let binding = if new_binding.is_import() && new_binding.span != DUMMY_SP {
4129                 new_binding
4130             } else {
4131                 old_binding
4132             };
4133
4134             let cm = self.session.codemap();
4135             let rename_msg = "You can use `as` to change the binding name of the import";
4136
4137             if let (Ok(snippet), false) = (cm.span_to_snippet(binding.span),
4138                                            binding.is_renamed_extern_crate()) {
4139                 let suggested_name = if name.as_str().chars().next().unwrap().is_uppercase() {
4140                     format!("Other{}", name)
4141                 } else {
4142                     format!("other_{}", name)
4143                 };
4144
4145                 err.span_suggestion(binding.span,
4146                                     rename_msg,
4147                                     if snippet.ends_with(';') {
4148                                         format!("{} as {};",
4149                                                 &snippet[..snippet.len()-1],
4150                                                 suggested_name)
4151                                     } else {
4152                                         format!("{} as {}", snippet, suggested_name)
4153                                     });
4154             } else {
4155                 err.span_label(binding.span, rename_msg);
4156             }
4157         }
4158
4159         err.emit();
4160         self.name_already_seen.insert(name, span);
4161     }
4162
4163     fn warn_legacy_self_import(&self, directive: &'a ImportDirective<'a>) {
4164         let (id, span) = (directive.id, directive.span);
4165         let msg = "`self` no longer imports values";
4166         self.session.buffer_lint(lint::builtin::LEGACY_IMPORTS, id, span, msg);
4167     }
4168
4169     fn check_proc_macro_attrs(&mut self, attrs: &[ast::Attribute]) {
4170         if self.proc_macro_enabled { return; }
4171
4172         for attr in attrs {
4173             if attr.path.segments.len() > 1 {
4174                 continue
4175             }
4176             let ident = attr.path.segments[0].identifier;
4177             let result = self.resolve_lexical_macro_path_segment(ident,
4178                                                                  MacroNS,
4179                                                                  false,
4180                                                                  attr.path.span);
4181             if let Ok(binding) = result {
4182                 if let SyntaxExtension::AttrProcMacro(..) = *binding.binding().get_macro(self) {
4183                     attr::mark_known(attr);
4184
4185                     let msg = "attribute procedural macros are experimental";
4186                     let feature = "proc_macro";
4187
4188                     feature_err(&self.session.parse_sess, feature,
4189                                 attr.span, GateIssue::Language, msg)
4190                         .span_label(binding.span(), "procedural macro imported here")
4191                         .emit();
4192                 }
4193             }
4194         }
4195     }
4196 }
4197
4198 fn is_self_type(path: &[SpannedIdent], namespace: Namespace) -> bool {
4199     namespace == TypeNS && path.len() == 1 && path[0].node.name == keywords::SelfType.name()
4200 }
4201
4202 fn is_self_value(path: &[SpannedIdent], namespace: Namespace) -> bool {
4203     namespace == ValueNS && path.len() == 1 && path[0].node.name == keywords::SelfValue.name()
4204 }
4205
4206 fn names_to_string(idents: &[SpannedIdent]) -> String {
4207     let mut result = String::new();
4208     for (i, ident) in idents.iter()
4209                             .filter(|i| i.node.name != keywords::CrateRoot.name())
4210                             .enumerate() {
4211         if i > 0 {
4212             result.push_str("::");
4213         }
4214         result.push_str(&ident.node.name.as_str());
4215     }
4216     result
4217 }
4218
4219 fn path_names_to_string(path: &Path) -> String {
4220     names_to_string(&path.segments.iter()
4221                         .map(|seg| respan(seg.span, seg.identifier))
4222                         .collect::<Vec<_>>())
4223 }
4224
4225 /// Get the path for an enum and the variant from an `ImportSuggestion` for an enum variant.
4226 fn import_candidate_to_paths(suggestion: &ImportSuggestion) -> (Span, String, String) {
4227     let variant_path = &suggestion.path;
4228     let variant_path_string = path_names_to_string(variant_path);
4229
4230     let path_len = suggestion.path.segments.len();
4231     let enum_path = ast::Path {
4232         span: suggestion.path.span,
4233         segments: suggestion.path.segments[0..path_len - 1].to_vec(),
4234     };
4235     let enum_path_string = path_names_to_string(&enum_path);
4236
4237     (suggestion.path.span, variant_path_string, enum_path_string)
4238 }
4239
4240
4241 /// When an entity with a given name is not available in scope, we search for
4242 /// entities with that name in all crates. This method allows outputting the
4243 /// results of this search in a programmer-friendly way
4244 fn show_candidates(err: &mut DiagnosticBuilder,
4245                    // This is `None` if all placement locations are inside expansions
4246                    span: Option<Span>,
4247                    candidates: &[ImportSuggestion],
4248                    better: bool,
4249                    found_use: bool) {
4250
4251     // we want consistent results across executions, but candidates are produced
4252     // by iterating through a hash map, so make sure they are ordered:
4253     let mut path_strings: Vec<_> =
4254         candidates.into_iter().map(|c| path_names_to_string(&c.path)).collect();
4255     path_strings.sort();
4256
4257     let better = if better { "better " } else { "" };
4258     let msg_diff = match path_strings.len() {
4259         1 => " is found in another module, you can import it",
4260         _ => "s are found in other modules, you can import them",
4261     };
4262     let msg = format!("possible {}candidate{} into scope", better, msg_diff);
4263
4264     if let Some(span) = span {
4265         for candidate in &mut path_strings {
4266             // produce an additional newline to separate the new use statement
4267             // from the directly following item.
4268             let additional_newline = if found_use {
4269                 ""
4270             } else {
4271                 "\n"
4272             };
4273             *candidate = format!("use {};\n{}", candidate, additional_newline);
4274         }
4275
4276         err.span_suggestions(span, &msg, path_strings);
4277     } else {
4278         let mut msg = msg;
4279         msg.push(':');
4280         for candidate in path_strings {
4281             msg.push('\n');
4282             msg.push_str(&candidate);
4283         }
4284     }
4285 }
4286
4287 /// A somewhat inefficient routine to obtain the name of a module.
4288 fn module_to_string(module: Module) -> Option<String> {
4289     let mut names = Vec::new();
4290
4291     fn collect_mod(names: &mut Vec<Ident>, module: Module) {
4292         if let ModuleKind::Def(_, name) = module.kind {
4293             if let Some(parent) = module.parent {
4294                 names.push(Ident::with_empty_ctxt(name));
4295                 collect_mod(names, parent);
4296             }
4297         } else {
4298             // danger, shouldn't be ident?
4299             names.push(Ident::from_str("<opaque>"));
4300             collect_mod(names, module.parent.unwrap());
4301         }
4302     }
4303     collect_mod(&mut names, module);
4304
4305     if names.is_empty() {
4306         return None;
4307     }
4308     Some(names_to_string(&names.into_iter()
4309                         .rev()
4310                         .map(|n| dummy_spanned(n))
4311                         .collect::<Vec<_>>()))
4312 }
4313
4314 fn err_path_resolution() -> PathResolution {
4315     PathResolution::new(Def::Err)
4316 }
4317
4318 #[derive(PartialEq,Copy, Clone)]
4319 pub enum MakeGlobMap {
4320     Yes,
4321     No,
4322 }
4323
4324 __build_diagnostic_array! { librustc_resolve, DIAGNOSTICS }