src/librustc_resolve/late.rs

   1 //! "Late resolution" is the pass that resolves most of names in a crate beside imports and macros.
   2 //! It runs when the crate is fully expanded and its module structure is fully built.
   3 //! So it just walks through the crate and resolves all the expressions, types, etc.
   4 //!
   5 //! If you wonder why there's no `early.rs`, that's because it's split into three files -
   6 //! `build_reduced_graph.rs`, `macros.rs` and `imports.rs`.
   7
   8 use RibKind::*;
   9
  10 use crate::{path_names_to_string, BindingError, CrateLint, LexicalScopeBinding};
  11 use crate::{Module, ModuleOrUniformRoot, NameBindingKind, ParentScope, PathResult};
  12 use crate::{ResolutionError, Resolver, Segment, UseError};
  13
  14 use log::debug;
  15 use rustc::hir::def::Namespace::{self, *};
  16 use rustc::hir::def::{self, CtorKind, DefKind, PartialRes, PerNS};
  17 use rustc::hir::def_id::{DefId, CRATE_DEF_INDEX};
  18 use rustc::hir::TraitCandidate;
  19 use rustc::{bug, lint, span_bug};
  20 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  21 use rustc_span::symbol::{kw, sym};
  22 use rustc_span::Span;
  23 use smallvec::{smallvec, SmallVec};
  24 use syntax::ast::*;
  25 use syntax::ptr::P;
  26 use syntax::util::lev_distance::find_best_match_for_name;
  27 use syntax::visit::{self, FnKind, Visitor};
  28 use syntax::{unwrap_or, walk_list};
  29
  30 use std::collections::BTreeSet;
  31 use std::mem::replace;
  32
  33 use rustc_error_codes::*;
  34
  35 mod diagnostics;
  36
  37 type Res = def::Res<NodeId>;
  38
  39 type IdentMap<T> = FxHashMap<Ident, T>;
  40
  41 /// Map from the name in a pattern to its binding mode.
  42 type BindingMap = IdentMap<BindingInfo>;
  43
  44 #[derive(Copy, Clone, Debug)]
  45 struct BindingInfo {
  46     span: Span,
  47     binding_mode: BindingMode,
  48 }
  49
  50 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  51 enum PatternSource {
  52     Match,
  53     Let,
  54     For,
  55     FnParam,
  56 }
  57
  58 impl PatternSource {
  59     fn descr(self) -> &'static str {
  60         match self {
  61             PatternSource::Match => "match binding",
  62             PatternSource::Let => "let binding",
  63             PatternSource::For => "for binding",
  64             PatternSource::FnParam => "function parameter",
  65         }
  66     }
  67 }
  68
  69 /// Denotes whether the context for the set of already bound bindings is a `Product`
  70 /// or `Or` context. This is used in e.g., `fresh_binding` and `resolve_pattern_inner`.
  71 /// See those functions for more information.
  72 #[derive(PartialEq)]
  73 enum PatBoundCtx {
  74     /// A product pattern context, e.g., `Variant(a, b)`.
  75     Product,
  76     /// An or-pattern context, e.g., `p_0 | ... | p_n`.
  77     Or,
  78 }
  79
  80 /// Does this the item (from the item rib scope) allow generic parameters?
  81 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  82 crate enum HasGenericParams {
  83     Yes,
  84     No,
  85 }
  86
  87 /// The rib kind restricts certain accesses,
  88 /// e.g. to a `Res::Local` of an outer item.
  89 #[derive(Copy, Clone, Debug)]
  90 crate enum RibKind<'a> {
  91     /// No restriction needs to be applied.
  92     NormalRibKind,
  93
  94     /// We passed through an impl or trait and are now in one of its
  95     /// methods or associated types. Allow references to ty params that impl or trait
  96     /// binds. Disallow any other upvars (including other ty params that are
  97     /// upvars).
  98     AssocItemRibKind,
  99
 100     /// We passed through a function definition. Disallow upvars.
 101     /// Permit only those const parameters that are specified in the function's generics.
 102     FnItemRibKind,
 103
 104     /// We passed through an item scope. Disallow upvars.
 105     ItemRibKind(HasGenericParams),
 106
 107     /// We're in a constant item. Can't refer to dynamic stuff.
 108     ConstantItemRibKind,
 109
 110     /// We passed through a module.
 111     ModuleRibKind(Module<'a>),
 112
 113     /// We passed through a `macro_rules!` statement
 114     MacroDefinition(DefId),
 115
 116     /// All bindings in this rib are type parameters that can't be used
 117     /// from the default of a type parameter because they're not declared
 118     /// before said type parameter. Also see the `visit_generics` override.
 119     ForwardTyParamBanRibKind,
 120 }
 121
 122 impl RibKind<'_> {
 123     // Whether this rib kind contains generic parameters, as opposed to local
 124     // variables.
 125     crate fn contains_params(&self) -> bool {
 126         match self {
 127             NormalRibKind | FnItemRibKind | ConstantItemRibKind | ModuleRibKind(_)
 128             | MacroDefinition(_) => false,
 129             AssocItemRibKind | ItemRibKind(_) | ForwardTyParamBanRibKind => true,
 130         }
 131     }
 132 }
 133
 134 /// A single local scope.
 135 ///
 136 /// A rib represents a scope names can live in. Note that these appear in many places, not just
 137 /// around braces. At any place where the list of accessible names (of the given namespace)
 138 /// changes or a new restrictions on the name accessibility are introduced, a new rib is put onto a
 139 /// stack. This may be, for example, a `let` statement (because it introduces variables), a macro,
 140 /// etc.
 141 ///
 142 /// Different [rib kinds](enum.RibKind) are transparent for different names.
 143 ///
 144 /// The resolution keeps a separate stack of ribs as it traverses the AST for each namespace. When
 145 /// resolving, the name is looked up from inside out.
 146 #[derive(Debug)]
 147 crate struct Rib<'a, R = Res> {
 148     pub bindings: IdentMap<R>,
 149     pub kind: RibKind<'a>,
 150 }
 151
 152 impl<'a, R> Rib<'a, R> {
 153     fn new(kind: RibKind<'a>) -> Rib<'a, R> {
 154         Rib { bindings: Default::default(), kind }
 155     }
 156 }
 157
 158 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 159 crate enum AliasPossibility {
 160     No,
 161     Maybe,
 162 }
 163
 164 #[derive(Copy, Clone, Debug)]
 165 crate enum PathSource<'a> {
 166     // Type paths `Path`.
 167     Type,
 168     // Trait paths in bounds or impls.
 169     Trait(AliasPossibility),
 170     // Expression paths `path`, with optional parent context.
 171     Expr(Option<&'a Expr>),
 172     // Paths in path patterns `Path`.
 173     Pat,
 174     // Paths in struct expressions and patterns `Path { .. }`.
 175     Struct,
 176     // Paths in tuple struct patterns `Path(..)`.
 177     TupleStruct,
 178     // `m::A::B` in `<T as m::A>::B::C`.
 179     TraitItem(Namespace),
 180 }
 181
 182 impl<'a> PathSource<'a> {
 183     fn namespace(self) -> Namespace {
 184         match self {
 185             PathSource::Type | PathSource::Trait(_) | PathSource::Struct => TypeNS,
 186             PathSource::Expr(..) | PathSource::Pat | PathSource::TupleStruct => ValueNS,
 187             PathSource::TraitItem(ns) => ns,
 188         }
 189     }
 190
 191     fn defer_to_typeck(self) -> bool {
 192         match self {
 193             PathSource::Type
 194             | PathSource::Expr(..)
 195             | PathSource::Pat
 196             | PathSource::Struct
 197             | PathSource::TupleStruct => true,
 198             PathSource::Trait(_) | PathSource::TraitItem(..) => false,
 199         }
 200     }
 201
 202     fn descr_expected(self) -> &'static str {
 203         match &self {
 204             PathSource::Type => "type",
 205             PathSource::Trait(_) => "trait",
 206             PathSource::Pat => "unit struct, unit variant or constant",
 207             PathSource::Struct => "struct, variant or union type",
 208             PathSource::TupleStruct => "tuple struct or tuple variant",
 209             PathSource::TraitItem(ns) => match ns {
 210                 TypeNS => "associated type",
 211                 ValueNS => "method or associated constant",
 212                 MacroNS => bug!("associated macro"),
 213             },
 214             PathSource::Expr(parent) => match &parent.as_ref().map(|p| &p.kind) {
 215                 // "function" here means "anything callable" rather than `DefKind::Fn`,
 216                 // this is not precise but usually more helpful than just "value".
 217                 Some(ExprKind::Call(call_expr, _)) => match &call_expr.kind {
 218                     ExprKind::Path(_, path) => {
 219                         let mut msg = "function";
 220                         if let Some(segment) = path.segments.iter().last() {
 221                             if let Some(c) = segment.ident.to_string().chars().next() {
 222                                 if c.is_uppercase() {
 223                                     msg = "function, tuple struct or tuple variant";
 224                                 }
 225                             }
 226                         }
 227                         msg
 228                     }
 229                     _ => "function",
 230                 },
 231                 _ => "value",
 232             },
 233         }
 234     }
 235
 236     crate fn is_expected(self, res: Res) -> bool {
 237         match self {
 238             PathSource::Type => match res {
 239                 Res::Def(DefKind::Struct, _)
 240                 | Res::Def(DefKind::Union, _)
 241                 | Res::Def(DefKind::Enum, _)
 242                 | Res::Def(DefKind::Trait, _)
 243                 | Res::Def(DefKind::TraitAlias, _)
 244                 | Res::Def(DefKind::TyAlias, _)
 245                 | Res::Def(DefKind::AssocTy, _)
 246                 | Res::PrimTy(..)
 247                 | Res::Def(DefKind::TyParam, _)
 248                 | Res::SelfTy(..)
 249                 | Res::Def(DefKind::OpaqueTy, _)
 250                 | Res::Def(DefKind::ForeignTy, _) => true,
 251                 _ => false,
 252             },
 253             PathSource::Trait(AliasPossibility::No) => match res {
 254                 Res::Def(DefKind::Trait, _) => true,
 255                 _ => false,
 256             },
 257             PathSource::Trait(AliasPossibility::Maybe) => match res {
 258                 Res::Def(DefKind::Trait, _) => true,
 259                 Res::Def(DefKind::TraitAlias, _) => true,
 260                 _ => false,
 261             },
 262             PathSource::Expr(..) => match res {
 263                 Res::Def(DefKind::Ctor(_, CtorKind::Const), _)
 264                 | Res::Def(DefKind::Ctor(_, CtorKind::Fn), _)
 265                 | Res::Def(DefKind::Const, _)
 266                 | Res::Def(DefKind::Static, _)
 267                 | Res::Local(..)
 268                 | Res::Def(DefKind::Fn, _)
 269                 | Res::Def(DefKind::Method, _)
 270                 | Res::Def(DefKind::AssocConst, _)
 271                 | Res::SelfCtor(..)
 272                 | Res::Def(DefKind::ConstParam, _) => true,
 273                 _ => false,
 274             },
 275             PathSource::Pat => match res {
 276                 Res::Def(DefKind::Ctor(_, CtorKind::Const), _)
 277                 | Res::Def(DefKind::Const, _)
 278                 | Res::Def(DefKind::AssocConst, _)
 279                 | Res::SelfCtor(..) => true,
 280                 _ => false,
 281             },
 282             PathSource::TupleStruct => match res {
 283                 Res::Def(DefKind::Ctor(_, CtorKind::Fn), _) | Res::SelfCtor(..) => true,
 284                 _ => false,
 285             },
 286             PathSource::Struct => match res {
 287                 Res::Def(DefKind::Struct, _)
 288                 | Res::Def(DefKind::Union, _)
 289                 | Res::Def(DefKind::Variant, _)
 290                 | Res::Def(DefKind::TyAlias, _)
 291                 | Res::Def(DefKind::AssocTy, _)
 292                 | Res::SelfTy(..) => true,
 293                 _ => false,
 294             },
 295             PathSource::TraitItem(ns) => match res {
 296                 Res::Def(DefKind::AssocConst, _) | Res::Def(DefKind::Method, _)
 297                     if ns == ValueNS =>
 298                 {
 299                     true
 300                 }
 301                 Res::Def(DefKind::AssocTy, _) if ns == TypeNS => true,
 302                 _ => false,
 303             },
 304         }
 305     }
 306
 307     fn error_code(self, has_unexpected_resolution: bool) -> &'static str {
 308         syntax::diagnostic_used!(E0404);
 309         syntax::diagnostic_used!(E0405);
 310         syntax::diagnostic_used!(E0412);
 311         syntax::diagnostic_used!(E0422);
 312         syntax::diagnostic_used!(E0423);
 313         syntax::diagnostic_used!(E0425);
 314         syntax::diagnostic_used!(E0531);
 315         syntax::diagnostic_used!(E0532);
 316         syntax::diagnostic_used!(E0573);
 317         syntax::diagnostic_used!(E0574);
 318         syntax::diagnostic_used!(E0575);
 319         syntax::diagnostic_used!(E0576);
 320         match (self, has_unexpected_resolution) {
 321             (PathSource::Trait(_), true) => "E0404",
 322             (PathSource::Trait(_), false) => "E0405",
 323             (PathSource::Type, true) => "E0573",
 324             (PathSource::Type, false) => "E0412",
 325             (PathSource::Struct, true) => "E0574",
 326             (PathSource::Struct, false) => "E0422",
 327             (PathSource::Expr(..), true) => "E0423",
 328             (PathSource::Expr(..), false) => "E0425",
 329             (PathSource::Pat, true) | (PathSource::TupleStruct, true) => "E0532",
 330             (PathSource::Pat, false) | (PathSource::TupleStruct, false) => "E0531",
 331             (PathSource::TraitItem(..), true) => "E0575",
 332             (PathSource::TraitItem(..), false) => "E0576",
 333         }
 334     }
 335 }
 336
 337 #[derive(Default)]
 338 struct DiagnosticMetadata {
 339     /// The current trait's associated types' ident, used for diagnostic suggestions.
 340     current_trait_assoc_types: Vec<Ident>,
 341
 342     /// The current self type if inside an impl (used for better errors).
 343     current_self_type: Option<Ty>,
 344
 345     /// The current self item if inside an ADT (used for better errors).
 346     current_self_item: Option<NodeId>,
 347
 348     /// The current enclosing function (used for better errors).
 349     current_function: Option<Span>,
 350
 351     /// A list of labels as of yet unused. Labels will be removed from this map when
 352     /// they are used (in a `break` or `continue` statement)
 353     unused_labels: FxHashMap<NodeId, Span>,
 354
 355     /// Only used for better errors on `fn(): fn()`.
 356     current_type_ascription: Vec<Span>,
 357
 358     /// Only used for better errors on `let <pat>: <expr, not type>;`.
 359     current_let_binding: Option<(Span, Option<Span>, Option<Span>)>,
 360 }
 361
 362 struct LateResolutionVisitor<'a, 'b> {
 363     r: &'b mut Resolver<'a>,
 364
 365     /// The module that represents the current item scope.
 366     parent_scope: ParentScope<'a>,
 367
 368     /// The current set of local scopes for types and values.
 369     /// FIXME #4948: Reuse ribs to avoid allocation.
 370     ribs: PerNS<Vec<Rib<'a>>>,
 371
 372     /// The current set of local scopes, for labels.
 373     label_ribs: Vec<Rib<'a, NodeId>>,
 374
 375     /// The trait that the current context can refer to.
 376     current_trait_ref: Option<(Module<'a>, TraitRef)>,
 377
 378     /// Fields used to add information to diagnostic errors.
 379     diagnostic_metadata: DiagnosticMetadata,
 380 }
 381
 382 /// Walks the whole crate in DFS order, visiting each item, resolving names as it goes.
 383 impl<'a, 'tcx> Visitor<'tcx> for LateResolutionVisitor<'a, '_> {
 384     fn visit_item(&mut self, item: &'tcx Item) {
 385         self.resolve_item(item);
 386     }
 387     fn visit_arm(&mut self, arm: &'tcx Arm) {
 388         self.resolve_arm(arm);
 389     }
 390     fn visit_block(&mut self, block: &'tcx Block) {
 391         self.resolve_block(block);
 392     }
 393     fn visit_anon_const(&mut self, constant: &'tcx AnonConst) {
 394         debug!("visit_anon_const {:?}", constant);
 395         self.with_constant_rib(|this| {
 396             visit::walk_anon_const(this, constant);
 397         });
 398     }
 399     fn visit_expr(&mut self, expr: &'tcx Expr) {
 400         self.resolve_expr(expr, None);
 401     }
 402     fn visit_local(&mut self, local: &'tcx Local) {
 403         let local_spans = match local.pat.kind {
 404             // We check for this to avoid tuple struct fields.
 405             PatKind::Wild => None,
 406             _ => Some((
 407                 local.pat.span,
 408                 local.ty.as_ref().map(|ty| ty.span),
 409                 local.init.as_ref().map(|init| init.span),
 410             )),
 411         };
 412         let original = replace(&mut self.diagnostic_metadata.current_let_binding, local_spans);
 413         self.resolve_local(local);
 414         self.diagnostic_metadata.current_let_binding = original;
 415     }
 416     fn visit_ty(&mut self, ty: &'tcx Ty) {
 417         match ty.kind {
 418             TyKind::Path(ref qself, ref path) => {
 419                 self.smart_resolve_path(ty.id, qself.as_ref(), path, PathSource::Type);
 420             }
 421             TyKind::ImplicitSelf => {
 422                 let self_ty = Ident::with_dummy_span(kw::SelfUpper);
 423                 let res = self
 424                     .resolve_ident_in_lexical_scope(self_ty, TypeNS, Some(ty.id), ty.span)
 425                     .map_or(Res::Err, |d| d.res());
 426                 self.r.record_partial_res(ty.id, PartialRes::new(res));
 427             }
 428             _ => (),
 429         }
 430         visit::walk_ty(self, ty);
 431     }
 432     fn visit_poly_trait_ref(&mut self, tref: &'tcx PolyTraitRef, m: &'tcx TraitBoundModifier) {
 433         self.smart_resolve_path(
 434             tref.trait_ref.ref_id,
 435             None,
 436             &tref.trait_ref.path,
 437             PathSource::Trait(AliasPossibility::Maybe),
 438         );
 439         visit::walk_poly_trait_ref(self, tref, m);
 440     }
 441     fn visit_foreign_item(&mut self, foreign_item: &'tcx ForeignItem) {
 442         match foreign_item.kind {
 443             ForeignItemKind::Fn(_, ref generics) => {
 444                 self.with_generic_param_rib(generics, ItemRibKind(HasGenericParams::Yes), |this| {
 445                     visit::walk_foreign_item(this, foreign_item);
 446                 });
 447             }
 448             ForeignItemKind::Static(..) => {
 449                 self.with_item_rib(HasGenericParams::No, |this| {
 450                     visit::walk_foreign_item(this, foreign_item);
 451                 });
 452             }
 453             ForeignItemKind::Ty | ForeignItemKind::Macro(..) => {
 454                 visit::walk_foreign_item(self, foreign_item);
 455             }
 456         }
 457     }
 458     fn visit_fn(&mut self, fn_kind: FnKind<'tcx>, declaration: &'tcx FnDecl, sp: Span, _: NodeId) {
 459         let previous_value = replace(&mut self.diagnostic_metadata.current_function, Some(sp));
 460         debug!("(resolving function) entering function");
 461         let rib_kind = match fn_kind {
 462             FnKind::ItemFn(..) => FnItemRibKind,
 463             FnKind::Method(..) | FnKind::Closure(_) => NormalRibKind,
 464         };
 465
 466         // Create a value rib for the function.
 467         self.with_rib(ValueNS, rib_kind, |this| {
 468             // Create a label rib for the function.
 469             this.with_label_rib(rib_kind, |this| {
 470                 // Add each argument to the rib.
 471                 this.resolve_params(&declaration.inputs);
 472
 473                 visit::walk_fn_ret_ty(this, &declaration.output);
 474
 475                 // Resolve the function body, potentially inside the body of an async closure
 476                 match fn_kind {
 477                     FnKind::ItemFn(.., body) | FnKind::Method(.., body) => this.visit_block(body),
 478                     FnKind::Closure(body) => this.visit_expr(body),
 479                 };
 480
 481                 debug!("(resolving function) leaving function");
 482             })
 483         });
 484         self.diagnostic_metadata.current_function = previous_value;
 485     }
 486
 487     fn visit_generics(&mut self, generics: &'tcx Generics) {
 488         // For type parameter defaults, we have to ban access
 489         // to following type parameters, as the InternalSubsts can only
 490         // provide previous type parameters as they're built. We
 491         // put all the parameters on the ban list and then remove
 492         // them one by one as they are processed and become available.
 493         let mut default_ban_rib = Rib::new(ForwardTyParamBanRibKind);
 494         let mut found_default = false;
 495         default_ban_rib.bindings.extend(generics.params.iter().filter_map(
 496             |param| match param.kind {
 497                 GenericParamKind::Const { .. } | GenericParamKind::Lifetime { .. } => None,
 498                 GenericParamKind::Type { ref default, .. } => {
 499                     found_default |= default.is_some();
 500                     found_default.then_some((Ident::with_dummy_span(param.ident.name), Res::Err))
 501                 }
 502             },
 503         ));
 504
 505         // rust-lang/rust#61631: The type `Self` is essentially
 506         // another type parameter. For ADTs, we consider it
 507         // well-defined only after all of the ADT type parameters have
 508         // been provided. Therefore, we do not allow use of `Self`
 509         // anywhere in ADT type parameter defaults.
 510         //
 511         // (We however cannot ban `Self` for defaults on *all* generic
 512         // lists; e.g. trait generics can usefully refer to `Self`,
 513         // such as in the case of `trait Add<Rhs = Self>`.)
 514         if self.diagnostic_metadata.current_self_item.is_some() {
 515             // (`Some` if + only if we are in ADT's generics.)
 516             default_ban_rib.bindings.insert(Ident::with_dummy_span(kw::SelfUpper), Res::Err);
 517         }
 518
 519         for param in &generics.params {
 520             match param.kind {
 521                 GenericParamKind::Lifetime { .. } => self.visit_generic_param(param),
 522                 GenericParamKind::Type { ref default, .. } => {
 523                     for bound in &param.bounds {
 524                         self.visit_param_bound(bound);
 525                     }
 526
 527                     if let Some(ref ty) = default {
 528                         self.ribs[TypeNS].push(default_ban_rib);
 529                         self.visit_ty(ty);
 530                         default_ban_rib = self.ribs[TypeNS].pop().unwrap();
 531                     }
 532
 533                     // Allow all following defaults to refer to this type parameter.
 534                     default_ban_rib.bindings.remove(&Ident::with_dummy_span(param.ident.name));
 535                 }
 536                 GenericParamKind::Const { ref ty } => {
 537                     for bound in &param.bounds {
 538                         self.visit_param_bound(bound);
 539                     }
 540                     self.visit_ty(ty);
 541                 }
 542             }
 543         }
 544         for p in &generics.where_clause.predicates {
 545             self.visit_where_predicate(p);
 546         }
 547     }
 548
 549     fn visit_generic_arg(&mut self, arg: &'tcx GenericArg) {
 550         debug!("visit_generic_arg({:?})", arg);
 551         match arg {
 552             GenericArg::Type(ref ty) => {
 553                 // We parse const arguments as path types as we cannot distiguish them durring
 554                 // parsing. We try to resolve that ambiguity by attempting resolution the type
 555                 // namespace first, and if that fails we try again in the value namespace. If
 556                 // resolution in the value namespace succeeds, we have an generic const argument on
 557                 // our hands.
 558                 if let TyKind::Path(ref qself, ref path) = ty.kind {
 559                     // We cannot disambiguate multi-segment paths right now as that requires type
 560                     // checking.
 561                     if path.segments.len() == 1 && path.segments[0].args.is_none() {
 562                         let mut check_ns = |ns| {
 563                             self.resolve_ident_in_lexical_scope(
 564                                 path.segments[0].ident,
 565                                 ns,
 566                                 None,
 567                                 path.span,
 568                             )
 569                             .is_some()
 570                         };
 571
 572                         if !check_ns(TypeNS) && check_ns(ValueNS) {
 573                             // This must be equivalent to `visit_anon_const`, but we cannot call it
 574                             // directly due to visitor lifetimes so we have to copy-paste some code.
 575                             self.with_constant_rib(|this| {
 576                                 this.smart_resolve_path(
 577                                     ty.id,
 578                                     qself.as_ref(),
 579                                     path,
 580                                     PathSource::Expr(None),
 581                                 );
 582
 583                                 if let Some(ref qself) = *qself {
 584                                     this.visit_ty(&qself.ty);
 585                                 }
 586                                 this.visit_path(path, ty.id);
 587                             });
 588
 589                             return;
 590                         }
 591                     }
 592                 }
 593
 594                 self.visit_ty(ty);
 595             }
 596             GenericArg::Lifetime(lt) => self.visit_lifetime(lt),
 597             GenericArg::Const(ct) => self.visit_anon_const(ct),
 598         }
 599     }
 600 }
 601
 602 impl<'a, 'b> LateResolutionVisitor<'a, '_> {
 603     fn new(resolver: &'b mut Resolver<'a>) -> LateResolutionVisitor<'a, 'b> {
 604         // During late resolution we only track the module component of the parent scope,
 605         // although it may be useful to track other components as well for diagnostics.
 606         let graph_root = resolver.graph_root;
 607         let parent_scope = ParentScope::module(graph_root);
 608         let start_rib_kind = ModuleRibKind(graph_root);
 609         LateResolutionVisitor {
 610             r: resolver,
 611             parent_scope,
 612             ribs: PerNS {
 613                 value_ns: vec![Rib::new(start_rib_kind)],
 614                 type_ns: vec![Rib::new(start_rib_kind)],
 615                 macro_ns: vec![Rib::new(start_rib_kind)],
 616             },
 617             label_ribs: Vec::new(),
 618             current_trait_ref: None,
 619             diagnostic_metadata: DiagnosticMetadata::default(),
 620         }
 621     }
 622
 623     fn resolve_ident_in_lexical_scope(
 624         &mut self,
 625         ident: Ident,
 626         ns: Namespace,
 627         record_used_id: Option<NodeId>,
 628         path_span: Span,
 629     ) -> Option<LexicalScopeBinding<'a>> {
 630         self.r.resolve_ident_in_lexical_scope(
 631             ident,
 632             ns,
 633             &self.parent_scope,
 634             record_used_id,
 635             path_span,
 636             &self.ribs[ns],
 637         )
 638     }
 639
 640     fn resolve_path(
 641         &mut self,
 642         path: &[Segment],
 643         opt_ns: Option<Namespace>, // `None` indicates a module path in import
 644         record_used: bool,
 645         path_span: Span,
 646         crate_lint: CrateLint,
 647     ) -> PathResult<'a> {
 648         self.r.resolve_path_with_ribs(
 649             path,
 650             opt_ns,
 651             &self.parent_scope,
 652             record_used,
 653             path_span,
 654             crate_lint,
 655             Some(&self.ribs),
 656         )
 657     }
 658
 659     // AST resolution
 660     //
 661     // We maintain a list of value ribs and type ribs.
 662     //
 663     // Simultaneously, we keep track of the current position in the module
 664     // graph in the `parent_scope.module` pointer. When we go to resolve a name in
 665     // the value or type namespaces, we first look through all the ribs and
 666     // then query the module graph. When we resolve a name in the module
 667     // namespace, we can skip all the ribs (since nested modules are not
 668     // allowed within blocks in Rust) and jump straight to the current module
 669     // graph node.
 670     //
 671     // Named implementations are handled separately. When we find a method
 672     // call, we consult the module node to find all of the implementations in
 673     // scope. This information is lazily cached in the module node. We then
 674     // generate a fake "implementation scope" containing all the
 675     // implementations thus found, for compatibility with old resolve pass.
 676
 677     /// Do some `work` within a new innermost rib of the given `kind` in the given namespace (`ns`).
 678     fn with_rib<T>(
 679         &mut self,
 680         ns: Namespace,
 681         kind: RibKind<'a>,
 682         work: impl FnOnce(&mut Self) -> T,
 683     ) -> T {
 684         self.ribs[ns].push(Rib::new(kind));
 685         let ret = work(self);
 686         self.ribs[ns].pop();
 687         ret
 688     }
 689
 690     fn with_scope<T>(&mut self, id: NodeId, f: impl FnOnce(&mut Self) -> T) -> T {
 691         let id = self.r.definitions.local_def_id(id);
 692         let module = self.r.module_map.get(&id).cloned(); // clones a reference
 693         if let Some(module) = module {
 694             // Move down in the graph.
 695             let orig_module = replace(&mut self.parent_scope.module, module);
 696             self.with_rib(ValueNS, ModuleRibKind(module), |this| {
 697                 this.with_rib(TypeNS, ModuleRibKind(module), |this| {
 698                     let ret = f(this);
 699                     this.parent_scope.module = orig_module;
 700                     ret
 701                 })
 702             })
 703         } else {
 704             f(self)
 705         }
 706     }
 707
 708     /// Searches the current set of local scopes for labels. Returns the first non-`None` label that
 709     /// is returned by the given predicate function
 710     ///
 711     /// Stops after meeting a closure.
 712     fn search_label<P, R>(&self, mut ident: Ident, pred: P) -> Option<R>
 713     where
 714         P: Fn(&Rib<'_, NodeId>, Ident) -> Option<R>,
 715     {
 716         for rib in self.label_ribs.iter().rev() {
 717             match rib.kind {
 718                 NormalRibKind => {}
 719                 // If an invocation of this macro created `ident`, give up on `ident`
 720                 // and switch to `ident`'s source from the macro definition.
 721                 MacroDefinition(def) => {
 722                     if def == self.r.macro_def(ident.span.ctxt()) {
 723                         ident.span.remove_mark();
 724                     }
 725                 }
 726                 _ => {
 727                     // Do not resolve labels across function boundary
 728                     return None;
 729                 }
 730             }
 731             let r = pred(rib, ident);
 732             if r.is_some() {
 733                 return r;
 734             }
 735         }
 736         None
 737     }
 738
 739     fn resolve_adt(&mut self, item: &Item, generics: &Generics) {
 740         debug!("resolve_adt");
 741         self.with_current_self_item(item, |this| {
 742             this.with_generic_param_rib(generics, ItemRibKind(HasGenericParams::Yes), |this| {
 743                 let item_def_id = this.r.definitions.local_def_id(item.id);
 744                 this.with_self_rib(Res::SelfTy(None, Some(item_def_id)), |this| {
 745                     visit::walk_item(this, item);
 746                 });
 747             });
 748         });
 749     }
 750
 751     fn future_proof_import(&mut self, use_tree: &UseTree) {
 752         let segments = &use_tree.prefix.segments;
 753         if !segments.is_empty() {
 754             let ident = segments[0].ident;
 755             if ident.is_path_segment_keyword() || ident.span.rust_2015() {
 756                 return;
 757             }
 758
 759             let nss = match use_tree.kind {
 760                 UseTreeKind::Simple(..) if segments.len() == 1 => &[TypeNS, ValueNS][..],
 761                 _ => &[TypeNS],
 762             };
 763             let report_error = |this: &Self, ns| {
 764                 let what = if ns == TypeNS { "type parameters" } else { "local variables" };
 765                 this.r.session.span_err(ident.span, &format!("imports cannot refer to {}", what));
 766             };
 767
 768             for &ns in nss {
 769                 match self.resolve_ident_in_lexical_scope(ident, ns, None, use_tree.prefix.span) {
 770                     Some(LexicalScopeBinding::Res(..)) => {
 771                         report_error(self, ns);
 772                     }
 773                     Some(LexicalScopeBinding::Item(binding)) => {
 774                         let orig_blacklisted_binding =
 775                             replace(&mut self.r.blacklisted_binding, Some(binding));
 776                         if let Some(LexicalScopeBinding::Res(..)) = self
 777                             .resolve_ident_in_lexical_scope(ident, ns, None, use_tree.prefix.span)
 778                         {
 779                             report_error(self, ns);
 780                         }
 781                         self.r.blacklisted_binding = orig_blacklisted_binding;
 782                     }
 783                     None => {}
 784                 }
 785             }
 786         } else if let UseTreeKind::Nested(use_trees) = &use_tree.kind {
 787             for (use_tree, _) in use_trees {
 788                 self.future_proof_import(use_tree);
 789             }
 790         }
 791     }
 792
 793     fn resolve_item(&mut self, item: &Item) {
 794         let name = item.ident.name;
 795         debug!("(resolving item) resolving {} ({:?})", name, item.kind);
 796
 797         match item.kind {
 798             ItemKind::TyAlias(_, ref generics) | ItemKind::Fn(_, ref generics, _) => {
 799                 self.with_generic_param_rib(generics, ItemRibKind(HasGenericParams::Yes), |this| {
 800                     visit::walk_item(this, item)
 801                 });
 802             }
 803
 804             ItemKind::Enum(_, ref generics)
 805             | ItemKind::Struct(_, ref generics)
 806             | ItemKind::Union(_, ref generics) => {
 807                 self.resolve_adt(item, generics);
 808             }
 809
 810             ItemKind::Impl(.., ref generics, ref opt_trait_ref, ref self_type, ref impl_items) => {
 811                 self.resolve_implementation(
 812                     generics,
 813                     opt_trait_ref,
 814                     &self_type,
 815                     item.id,
 816                     impl_items,
 817                 )
 818             }
 819
 820             ItemKind::Trait(.., ref generics, ref bounds, ref trait_items) => {
 821                 // Create a new rib for the trait-wide type parameters.
 822                 self.with_generic_param_rib(generics, ItemRibKind(HasGenericParams::Yes), |this| {
 823                     let local_def_id = this.r.definitions.local_def_id(item.id);
 824                     this.with_self_rib(Res::SelfTy(Some(local_def_id), None), |this| {
 825                         this.visit_generics(generics);
 826                         walk_list!(this, visit_param_bound, bounds);
 827
 828                         for trait_item in trait_items {
 829                             this.with_trait_items(trait_items, |this| {
 830                                 this.with_generic_param_rib(
 831                                     &trait_item.generics,
 832                                     AssocItemRibKind,
 833                                     |this| {
 834                                         match trait_item.kind {
 835                                             AssocItemKind::Const(ref ty, ref default) => {
 836                                                 this.visit_ty(ty);
 837
 838                                                 // Only impose the restrictions of
 839                                                 // ConstRibKind for an actual constant
 840                                                 // expression in a provided default.
 841                                                 if let Some(ref expr) = *default {
 842                                                     this.with_constant_rib(|this| {
 843                                                         this.visit_expr(expr);
 844                                                     });
 845                                                 }
 846                                             }
 847                                             AssocItemKind::Fn(_, _) => {
 848                                                 visit::walk_trait_item(this, trait_item)
 849                                             }
 850                                             AssocItemKind::TyAlias(..) => {
 851                                                 visit::walk_trait_item(this, trait_item)
 852                                             }
 853                                             AssocItemKind::Macro(_) => {
 854                                                 panic!("unexpanded macro in resolve!")
 855                                             }
 856                                         };
 857                                     },
 858                                 );
 859                             });
 860                         }
 861                     });
 862                 });
 863             }
 864
 865             ItemKind::TraitAlias(ref generics, ref bounds) => {
 866                 // Create a new rib for the trait-wide type parameters.
 867                 self.with_generic_param_rib(generics, ItemRibKind(HasGenericParams::Yes), |this| {
 868                     let local_def_id = this.r.definitions.local_def_id(item.id);
 869                     this.with_self_rib(Res::SelfTy(Some(local_def_id), None), |this| {
 870                         this.visit_generics(generics);
 871                         walk_list!(this, visit_param_bound, bounds);
 872                     });
 873                 });
 874             }
 875
 876             ItemKind::Mod(_) | ItemKind::ForeignMod(_) => {
 877                 self.with_scope(item.id, |this| {
 878                     visit::walk_item(this, item);
 879                 });
 880             }
 881
 882             ItemKind::Static(ref ty, _, ref expr) | ItemKind::Const(ref ty, ref expr) => {
 883                 debug!("resolve_item ItemKind::Const");
 884                 self.with_item_rib(HasGenericParams::No, |this| {
 885                     this.visit_ty(ty);
 886                     this.with_constant_rib(|this| {
 887                         this.visit_expr(expr);
 888                     });
 889                 });
 890             }
 891
 892             ItemKind::Use(ref use_tree) => {
 893                 self.future_proof_import(use_tree);
 894             }
 895
 896             ItemKind::ExternCrate(..) | ItemKind::MacroDef(..) | ItemKind::GlobalAsm(..) => {
 897                 // do nothing, these are just around to be encoded
 898             }
 899
 900             ItemKind::Mac(_) => panic!("unexpanded macro in resolve!"),
 901         }
 902     }
 903
 904     fn with_generic_param_rib<'c, F>(&'c mut self, generics: &'c Generics, kind: RibKind<'a>, f: F)
 905     where
 906         F: FnOnce(&mut Self),
 907     {
 908         debug!("with_generic_param_rib");
 909         let mut function_type_rib = Rib::new(kind);
 910         let mut function_value_rib = Rib::new(kind);
 911         let mut seen_bindings = FxHashMap::default();
 912
 913         // We also can't shadow bindings from the parent item
 914         if let AssocItemRibKind = kind {
 915             let mut add_bindings_for_ns = |ns| {
 916                 let parent_rib = self.ribs[ns]
 917                     .iter()
 918                     .rfind(|r| if let ItemRibKind(_) = r.kind { true } else { false })
 919                     .expect("associated item outside of an item");
 920                 seen_bindings
 921                     .extend(parent_rib.bindings.iter().map(|(ident, _)| (*ident, ident.span)));
 922             };
 923             add_bindings_for_ns(ValueNS);
 924             add_bindings_for_ns(TypeNS);
 925         }
 926
 927         for param in &generics.params {
 928             if let GenericParamKind::Lifetime { .. } = param.kind {
 929                 continue;
 930             }
 931
 932             let def_kind = match param.kind {
 933                 GenericParamKind::Type { .. } => DefKind::TyParam,
 934                 GenericParamKind::Const { .. } => DefKind::ConstParam,
 935                 _ => unreachable!(),
 936             };
 937
 938             let ident = param.ident.modern();
 939             debug!("with_generic_param_rib: {}", param.id);
 940
 941             if seen_bindings.contains_key(&ident) {
 942                 let span = seen_bindings.get(&ident).unwrap();
 943                 let err = ResolutionError::NameAlreadyUsedInParameterList(ident.name, *span);
 944                 self.r.report_error(param.ident.span, err);
 945             }
 946             seen_bindings.entry(ident).or_insert(param.ident.span);
 947
 948             // Plain insert (no renaming).
 949             let res = Res::Def(def_kind, self.r.definitions.local_def_id(param.id));
 950
 951             match param.kind {
 952                 GenericParamKind::Type { .. } => {
 953                     function_type_rib.bindings.insert(ident, res);
 954                     self.r.record_partial_res(param.id, PartialRes::new(res));
 955                 }
 956                 GenericParamKind::Const { .. } => {
 957                     function_value_rib.bindings.insert(ident, res);
 958                     self.r.record_partial_res(param.id, PartialRes::new(res));
 959                 }
 960                 _ => unreachable!(),
 961             }
 962         }
 963
 964         self.ribs[ValueNS].push(function_value_rib);
 965         self.ribs[TypeNS].push(function_type_rib);
 966
 967         f(self);
 968
 969         self.ribs[TypeNS].pop();
 970         self.ribs[ValueNS].pop();
 971     }
 972
 973     fn with_label_rib(&mut self, kind: RibKind<'a>, f: impl FnOnce(&mut Self)) {
 974         self.label_ribs.push(Rib::new(kind));
 975         f(self);
 976         self.label_ribs.pop();
 977     }
 978
 979     fn with_item_rib(&mut self, has_generic_params: HasGenericParams, f: impl FnOnce(&mut Self)) {
 980         let kind = ItemRibKind(has_generic_params);
 981         self.with_rib(ValueNS, kind, |this| this.with_rib(TypeNS, kind, f))
 982     }
 983
 984     fn with_constant_rib(&mut self, f: impl FnOnce(&mut Self)) {
 985         debug!("with_constant_rib");
 986         self.with_rib(ValueNS, ConstantItemRibKind, |this| {
 987             this.with_label_rib(ConstantItemRibKind, f);
 988         });
 989     }
 990
 991     fn with_current_self_type<T>(&mut self, self_type: &Ty, f: impl FnOnce(&mut Self) -> T) -> T {
 992         // Handle nested impls (inside fn bodies)
 993         let previous_value =
 994             replace(&mut self.diagnostic_metadata.current_self_type, Some(self_type.clone()));
 995         let result = f(self);
 996         self.diagnostic_metadata.current_self_type = previous_value;
 997         result
 998     }
 999
1000     fn with_current_self_item<T>(&mut self, self_item: &Item, f: impl FnOnce(&mut Self) -> T) -> T {
1001         let previous_value =
1002             replace(&mut self.diagnostic_metadata.current_self_item, Some(self_item.id));
1003         let result = f(self);
1004         self.diagnostic_metadata.current_self_item = previous_value;
1005         result
1006     }
1007
1008     /// When evaluating a `trait` use its associated types' idents for suggestionsa in E0412.
1009     fn with_trait_items<T>(
1010         &mut self,
1011         trait_items: &Vec<AssocItem>,
1012         f: impl FnOnce(&mut Self) -> T,
1013     ) -> T {
1014         let trait_assoc_types = replace(
1015             &mut self.diagnostic_metadata.current_trait_assoc_types,
1016             trait_items
1017                 .iter()
1018                 .filter_map(|item| match &item.kind {
1019                     AssocItemKind::TyAlias(bounds, _) if bounds.len() == 0 => Some(item.ident),
1020                     _ => None,
1021                 })
1022                 .collect(),
1023         );
1024         let result = f(self);
1025         self.diagnostic_metadata.current_trait_assoc_types = trait_assoc_types;
1026         result
1027     }
1028
1029     /// This is called to resolve a trait reference from an `impl` (i.e., `impl Trait for Foo`).
1030     fn with_optional_trait_ref<T>(
1031         &mut self,
1032         opt_trait_ref: Option<&TraitRef>,
1033         f: impl FnOnce(&mut Self, Option<DefId>) -> T,
1034     ) -> T {
1035         let mut new_val = None;
1036         let mut new_id = None;
1037         if let Some(trait_ref) = opt_trait_ref {
1038             let path: Vec<_> = Segment::from_path(&trait_ref.path);
1039             let res = self
1040                 .smart_resolve_path_fragment(
1041                     trait_ref.ref_id,
1042                     None,
1043                     &path,
1044                     trait_ref.path.span,
1045                     PathSource::Trait(AliasPossibility::No),
1046                     CrateLint::SimplePath(trait_ref.ref_id),
1047                 )
1048                 .base_res();
1049             if res != Res::Err {
1050                 new_id = Some(res.def_id());
1051                 let span = trait_ref.path.span;
1052                 if let PathResult::Module(ModuleOrUniformRoot::Module(module)) = self.resolve_path(
1053                     &path,
1054                     Some(TypeNS),
1055                     false,
1056                     span,
1057                     CrateLint::SimplePath(trait_ref.ref_id),
1058                 ) {
1059                     new_val = Some((module, trait_ref.clone()));
1060                 }
1061             }
1062         }
1063         let original_trait_ref = replace(&mut self.current_trait_ref, new_val);
1064         let result = f(self, new_id);
1065         self.current_trait_ref = original_trait_ref;
1066         result
1067     }
1068
1069     fn with_self_rib_ns(&mut self, ns: Namespace, self_res: Res, f: impl FnOnce(&mut Self)) {
1070         let mut self_type_rib = Rib::new(NormalRibKind);
1071
1072         // Plain insert (no renaming, since types are not currently hygienic)
1073         self_type_rib.bindings.insert(Ident::with_dummy_span(kw::SelfUpper), self_res);
1074         self.ribs[ns].push(self_type_rib);
1075         f(self);
1076         self.ribs[ns].pop();
1077     }
1078
1079     fn with_self_rib(&mut self, self_res: Res, f: impl FnOnce(&mut Self)) {
1080         self.with_self_rib_ns(TypeNS, self_res, f)
1081     }
1082
1083     fn resolve_implementation(
1084         &mut self,
1085         generics: &Generics,
1086         opt_trait_reference: &Option<TraitRef>,
1087         self_type: &Ty,
1088         item_id: NodeId,
1089         impl_items: &[AssocItem],
1090     ) {
1091         debug!("resolve_implementation");
1092         // If applicable, create a rib for the type parameters.
1093         self.with_generic_param_rib(generics, ItemRibKind(HasGenericParams::Yes), |this| {
1094             // Dummy self type for better errors if `Self` is used in the trait path.
1095             this.with_self_rib(Res::SelfTy(None, None), |this| {
1096                 // Resolve the trait reference, if necessary.
1097                 this.with_optional_trait_ref(opt_trait_reference.as_ref(), |this, trait_id| {
1098                     let item_def_id = this.r.definitions.local_def_id(item_id);
1099                     this.with_self_rib(Res::SelfTy(trait_id, Some(item_def_id)), |this| {
1100                         if let Some(trait_ref) = opt_trait_reference.as_ref() {
1101                             // Resolve type arguments in the trait path.
1102                             visit::walk_trait_ref(this, trait_ref);
1103                         }
1104                         // Resolve the self type.
1105                         this.visit_ty(self_type);
1106                         // Resolve the generic parameters.
1107                         this.visit_generics(generics);
1108                         // Resolve the items within the impl.
1109                         this.with_current_self_type(self_type, |this| {
1110                             this.with_self_rib_ns(ValueNS, Res::SelfCtor(item_def_id), |this| {
1111                                 debug!("resolve_implementation with_self_rib_ns(ValueNS, ...)");
1112                                 for impl_item in impl_items {
1113                                     // We also need a new scope for the impl item type parameters.
1114                                     this.with_generic_param_rib(&impl_item.generics,
1115                                                                 AssocItemRibKind,
1116                                                                 |this| {
1117                                         use crate::ResolutionError::*;
1118                                         match impl_item.kind {
1119                                             AssocItemKind::Const(..) => {
1120                                                 debug!(
1121                                                     "resolve_implementation AssocItemKind::Const",
1122                                                 );
1123                                                 // If this is a trait impl, ensure the const
1124                                                 // exists in trait
1125                                                 this.check_trait_item(
1126                                                     impl_item.ident,
1127                                                     ValueNS,
1128                                                     impl_item.span,
1129                                                     |n, s| ConstNotMemberOfTrait(n, s),
1130                                                 );
1131
1132                                                 this.with_constant_rib(|this| {
1133                                                     visit::walk_impl_item(this, impl_item)
1134                                                 });
1135                                             }
1136                                             AssocItemKind::Fn(..) => {
1137                                                 // If this is a trait impl, ensure the method
1138                                                 // exists in trait
1139                                                 this.check_trait_item(impl_item.ident,
1140                                                                       ValueNS,
1141                                                                       impl_item.span,
1142                                                     |n, s| MethodNotMemberOfTrait(n, s));
1143
1144                                                 visit::walk_impl_item(this, impl_item);
1145                                             }
1146                                             AssocItemKind::TyAlias(_, _) => {
1147                                                 // If this is a trait impl, ensure the type
1148                                                 // exists in trait
1149                                                 this.check_trait_item(impl_item.ident,
1150                                                                       TypeNS,
1151                                                                       impl_item.span,
1152                                                     |n, s| TypeNotMemberOfTrait(n, s));
1153
1154                                                 visit::walk_impl_item(this, impl_item);
1155                                             }
1156                                             AssocItemKind::Macro(_) =>
1157                                                 panic!("unexpanded macro in resolve!"),
1158                                         }
1159                                     });
1160                                 }
1161                             });
1162                         });
1163                     });
1164                 });
1165             });
1166         });
1167     }
1168
1169     fn check_trait_item<F>(&mut self, ident: Ident, ns: Namespace, span: Span, err: F)
1170     where
1171         F: FnOnce(Name, &str) -> ResolutionError<'_>,
1172     {
1173         // If there is a TraitRef in scope for an impl, then the method must be in the
1174         // trait.
1175         if let Some((module, _)) = self.current_trait_ref {
1176             if self
1177                 .r
1178                 .resolve_ident_in_module(
1179                     ModuleOrUniformRoot::Module(module),
1180                     ident,
1181                     ns,
1182                     &self.parent_scope,
1183                     false,
1184                     span,
1185                 )
1186                 .is_err()
1187             {
1188                 let path = &self.current_trait_ref.as_ref().unwrap().1.path;
1189                 self.r.report_error(span, err(ident.name, &path_names_to_string(path)));
1190             }
1191         }
1192     }
1193
1194     fn resolve_params(&mut self, params: &[Param]) {
1195         let mut bindings = smallvec![(PatBoundCtx::Product, Default::default())];
1196         for Param { pat, ty, .. } in params {
1197             self.resolve_pattern(pat, PatternSource::FnParam, &mut bindings);
1198             self.visit_ty(ty);
1199             debug!("(resolving function / closure) recorded parameter");
1200         }
1201     }
1202
1203     fn resolve_local(&mut self, local: &Local) {
1204         // Resolve the type.
1205         walk_list!(self, visit_ty, &local.ty);
1206
1207         // Resolve the initializer.
1208         walk_list!(self, visit_expr, &local.init);
1209
1210         // Resolve the pattern.
1211         self.resolve_pattern_top(&local.pat, PatternSource::Let);
1212     }
1213
1214     /// build a map from pattern identifiers to binding-info's.
1215     /// this is done hygienically. This could arise for a macro
1216     /// that expands into an or-pattern where one 'x' was from the
1217     /// user and one 'x' came from the macro.
1218     fn binding_mode_map(&mut self, pat: &Pat) -> BindingMap {
1219         let mut binding_map = FxHashMap::default();
1220
1221         pat.walk(&mut |pat| {
1222             match pat.kind {
1223                 PatKind::Ident(binding_mode, ident, ref sub_pat)
1224                     if sub_pat.is_some() || self.is_base_res_local(pat.id) =>
1225                 {
1226                     binding_map.insert(ident, BindingInfo { span: ident.span, binding_mode });
1227                 }
1228                 PatKind::Or(ref ps) => {
1229                     // Check the consistency of this or-pattern and
1230                     // then add all bindings to the larger map.
1231                     for bm in self.check_consistent_bindings(ps) {
1232                         binding_map.extend(bm);
1233                     }
1234                     return false;
1235                 }
1236                 _ => {}
1237             }
1238
1239             true
1240         });
1241
1242         binding_map
1243     }
1244
1245     fn is_base_res_local(&self, nid: NodeId) -> bool {
1246         match self.r.partial_res_map.get(&nid).map(|res| res.base_res()) {
1247             Some(Res::Local(..)) => true,
1248             _ => false,
1249         }
1250     }
1251
1252     /// Checks that all of the arms in an or-pattern have exactly the
1253     /// same set of bindings, with the same binding modes for each.
1254     fn check_consistent_bindings(&mut self, pats: &[P<Pat>]) -> Vec<BindingMap> {
1255         let mut missing_vars = FxHashMap::default();
1256         let mut inconsistent_vars = FxHashMap::default();
1257
1258         // 1) Compute the binding maps of all arms.
1259         let maps = pats.iter().map(|pat| self.binding_mode_map(pat)).collect::<Vec<_>>();
1260
1261         // 2) Record any missing bindings or binding mode inconsistencies.
1262         for (map_outer, pat_outer) in pats.iter().enumerate().map(|(idx, pat)| (&maps[idx], pat)) {
1263             // Check against all arms except for the same pattern which is always self-consistent.
1264             let inners = pats
1265                 .iter()
1266                 .enumerate()
1267                 .filter(|(_, pat)| pat.id != pat_outer.id)
1268                 .flat_map(|(idx, _)| maps[idx].iter())
1269                 .map(|(key, binding)| (key.name, map_outer.get(&key), binding));
1270
1271             for (name, info, &binding_inner) in inners {
1272                 match info {
1273                     None => {
1274                         // The inner binding is missing in the outer.
1275                         let binding_error =
1276                             missing_vars.entry(name).or_insert_with(|| BindingError {
1277                                 name,
1278                                 origin: BTreeSet::new(),
1279                                 target: BTreeSet::new(),
1280                                 could_be_path: name.as_str().starts_with(char::is_uppercase),
1281                             });
1282                         binding_error.origin.insert(binding_inner.span);
1283                         binding_error.target.insert(pat_outer.span);
1284                     }
1285                     Some(binding_outer) => {
1286                         if binding_outer.binding_mode != binding_inner.binding_mode {
1287                             // The binding modes in the outer and inner bindings differ.
1288                             inconsistent_vars
1289                                 .entry(name)
1290                                 .or_insert((binding_inner.span, binding_outer.span));
1291                         }
1292                     }
1293                 }
1294             }
1295         }
1296
1297         // 3) Report all missing variables we found.
1298         let mut missing_vars = missing_vars.iter_mut().collect::<Vec<_>>();
1299         missing_vars.sort();
1300         for (name, mut v) in missing_vars {
1301             if inconsistent_vars.contains_key(name) {
1302                 v.could_be_path = false;
1303             }
1304             self.r.report_error(
1305                 *v.origin.iter().next().unwrap(),
1306                 ResolutionError::VariableNotBoundInPattern(v),
1307             );
1308         }
1309
1310         // 4) Report all inconsistencies in binding modes we found.
1311         let mut inconsistent_vars = inconsistent_vars.iter().collect::<Vec<_>>();
1312         inconsistent_vars.sort();
1313         for (name, v) in inconsistent_vars {
1314             self.r.report_error(v.0, ResolutionError::VariableBoundWithDifferentMode(*name, v.1));
1315         }
1316
1317         // 5) Finally bubble up all the binding maps.
1318         maps
1319     }
1320
1321     /// Check the consistency of the outermost or-patterns.
1322     fn check_consistent_bindings_top(&mut self, pat: &Pat) {
1323         pat.walk(&mut |pat| match pat.kind {
1324             PatKind::Or(ref ps) => {
1325                 self.check_consistent_bindings(ps);
1326                 false
1327             }
1328             _ => true,
1329         })
1330     }
1331
1332     fn resolve_arm(&mut self, arm: &Arm) {
1333         self.with_rib(ValueNS, NormalRibKind, |this| {
1334             this.resolve_pattern_top(&arm.pat, PatternSource::Match);
1335             walk_list!(this, visit_expr, &arm.guard);
1336             this.visit_expr(&arm.body);
1337         });
1338     }
1339
1340     /// Arising from `source`, resolve a top level pattern.
1341     fn resolve_pattern_top(&mut self, pat: &Pat, pat_src: PatternSource) {
1342         let mut bindings = smallvec![(PatBoundCtx::Product, Default::default())];
1343         self.resolve_pattern(pat, pat_src, &mut bindings);
1344     }
1345
1346     fn resolve_pattern(
1347         &mut self,
1348         pat: &Pat,
1349         pat_src: PatternSource,
1350         bindings: &mut SmallVec<[(PatBoundCtx, FxHashSet<Ident>); 1]>,
1351     ) {
1352         self.resolve_pattern_inner(pat, pat_src, bindings);
1353         // This has to happen *after* we determine which pat_idents are variants:
1354         self.check_consistent_bindings_top(pat);
1355         visit::walk_pat(self, pat);
1356     }
1357
1358     /// Resolve bindings in a pattern. This is a helper to `resolve_pattern`.
1359     ///
1360     /// ### `bindings`
1361     ///
1362     /// A stack of sets of bindings accumulated.
1363     ///
1364     /// In each set, `PatBoundCtx::Product` denotes that a found binding in it should
1365     /// be interpreted as re-binding an already bound binding. This results in an error.
1366     /// Meanwhile, `PatBound::Or` denotes that a found binding in the set should result
1367     /// in reusing this binding rather than creating a fresh one.
1368     ///
1369     /// When called at the top level, the stack must have a single element
1370     /// with `PatBound::Product`. Otherwise, pushing to the stack happens as
1371     /// or-patterns (`p_0 | ... | p_n`) are encountered and the context needs
1372     /// to be switched to `PatBoundCtx::Or` and then `PatBoundCtx::Product` for each `p_i`.
1373     /// When each `p_i` has been dealt with, the top set is merged with its parent.
1374     /// When a whole or-pattern has been dealt with, the thing happens.
1375     ///
1376     /// See the implementation and `fresh_binding` for more details.
1377     fn resolve_pattern_inner(
1378         &mut self,
1379         pat: &Pat,
1380         pat_src: PatternSource,
1381         bindings: &mut SmallVec<[(PatBoundCtx, FxHashSet<Ident>); 1]>,
1382     ) {
1383         // Visit all direct subpatterns of this pattern.
1384         pat.walk(&mut |pat| {
1385             debug!("resolve_pattern pat={:?} node={:?}", pat, pat.kind);
1386             match pat.kind {
1387                 PatKind::Ident(bmode, ident, ref sub) => {
1388                     // First try to resolve the identifier as some existing entity,
1389                     // then fall back to a fresh binding.
1390                     let has_sub = sub.is_some();
1391                     let res = self
1392                         .try_resolve_as_non_binding(pat_src, pat, bmode, ident, has_sub)
1393                         .unwrap_or_else(|| self.fresh_binding(ident, pat.id, pat_src, bindings));
1394                     self.r.record_partial_res(pat.id, PartialRes::new(res));
1395                 }
1396                 PatKind::TupleStruct(ref path, ..) => {
1397                     self.smart_resolve_path(pat.id, None, path, PathSource::TupleStruct);
1398                 }
1399                 PatKind::Path(ref qself, ref path) => {
1400                     self.smart_resolve_path(pat.id, qself.as_ref(), path, PathSource::Pat);
1401                 }
1402                 PatKind::Struct(ref path, ..) => {
1403                     self.smart_resolve_path(pat.id, None, path, PathSource::Struct);
1404                 }
1405                 PatKind::Or(ref ps) => {
1406                     // Add a new set of bindings to the stack. `Or` here records that when a
1407                     // binding already exists in this set, it should not result in an error because
1408                     // `V1(a) | V2(a)` must be allowed and are checked for consistency later.
1409                     bindings.push((PatBoundCtx::Or, Default::default()));
1410                     for p in ps {
1411                         // Now we need to switch back to a product context so that each
1412                         // part of the or-pattern internally rejects already bound names.
1413                         // For example, `V1(a) | V2(a, a)` and `V1(a, a) | V2(a)` are bad.
1414                         bindings.push((PatBoundCtx::Product, Default::default()));
1415                         self.resolve_pattern_inner(p, pat_src, bindings);
1416                         // Move up the non-overlapping bindings to the or-pattern.
1417                         // Existing bindings just get "merged".
1418                         let collected = bindings.pop().unwrap().1;
1419                         bindings.last_mut().unwrap().1.extend(collected);
1420                     }
1421                     // This or-pattern itself can itself be part of a product,
1422                     // e.g. `(V1(a) | V2(a), a)` or `(a, V1(a) | V2(a))`.
1423                     // Both cases bind `a` again in a product pattern and must be rejected.
1424                     let collected = bindings.pop().unwrap().1;
1425                     bindings.last_mut().unwrap().1.extend(collected);
1426
1427                     // Prevent visiting `ps` as we've already done so above.
1428                     return false;
1429                 }
1430                 _ => {}
1431             }
1432             true
1433         });
1434     }
1435
1436     fn fresh_binding(
1437         &mut self,
1438         ident: Ident,
1439         pat_id: NodeId,
1440         pat_src: PatternSource,
1441         bindings: &mut SmallVec<[(PatBoundCtx, FxHashSet<Ident>); 1]>,
1442     ) -> Res {
1443         // Add the binding to the local ribs, if it doesn't already exist in the bindings map.
1444         // (We must not add it if it's in the bindings map because that breaks the assumptions
1445         // later passes make about or-patterns.)
1446         let ident = ident.modern_and_legacy();
1447
1448         let mut bound_iter = bindings.iter().filter(|(_, set)| set.contains(&ident));
1449         // Already bound in a product pattern? e.g. `(a, a)` which is not allowed.
1450         let already_bound_and = bound_iter.clone().any(|(ctx, _)| *ctx == PatBoundCtx::Product);
1451         // Already bound in an or-pattern? e.g. `V1(a) | V2(a)`.
1452         // This is *required* for consistency which is checked later.
1453         let already_bound_or = bound_iter.any(|(ctx, _)| *ctx == PatBoundCtx::Or);
1454
1455         if already_bound_and {
1456             // Overlap in a product pattern somewhere; report an error.
1457             use ResolutionError::*;
1458             let error = match pat_src {
1459                 // `fn f(a: u8, a: u8)`:
1460                 PatternSource::FnParam => IdentifierBoundMoreThanOnceInParameterList,
1461                 // `Variant(a, a)`:
1462                 _ => IdentifierBoundMoreThanOnceInSamePattern,
1463             };
1464             self.r.report_error(ident.span, error(&ident.as_str()));
1465         }
1466
1467         // Record as bound if it's valid:
1468         let ident_valid = ident.name != kw::Invalid;
1469         if ident_valid {
1470             bindings.last_mut().unwrap().1.insert(ident);
1471         }
1472
1473         if already_bound_or {
1474             // `Variant1(a) | Variant2(a)`, ok
1475             // Reuse definition from the first `a`.
1476             self.innermost_rib_bindings(ValueNS)[&ident]
1477         } else {
1478             let res = Res::Local(pat_id);
1479             if ident_valid {
1480                 // A completely fresh binding add to the set if it's valid.
1481                 self.innermost_rib_bindings(ValueNS).insert(ident, res);
1482             }
1483             res
1484         }
1485     }
1486
1487     fn innermost_rib_bindings(&mut self, ns: Namespace) -> &mut IdentMap<Res> {
1488         &mut self.ribs[ns].last_mut().unwrap().bindings
1489     }
1490
1491     fn try_resolve_as_non_binding(
1492         &mut self,
1493         pat_src: PatternSource,
1494         pat: &Pat,
1495         bm: BindingMode,
1496         ident: Ident,
1497         has_sub: bool,
1498     ) -> Option<Res> {
1499         let binding =
1500             self.resolve_ident_in_lexical_scope(ident, ValueNS, None, pat.span)?.item()?;
1501         let res = binding.res();
1502
1503         // An immutable (no `mut`) by-value (no `ref`) binding pattern without
1504         // a sub pattern (no `@ $pat`) is syntactically ambiguous as it could
1505         // also be interpreted as a path to e.g. a constant, variant, etc.
1506         let is_syntactic_ambiguity = !has_sub && bm == BindingMode::ByValue(Mutability::Not);
1507
1508         match res {
1509             Res::Def(DefKind::Ctor(_, CtorKind::Const), _) | Res::Def(DefKind::Const, _)
1510                 if is_syntactic_ambiguity =>
1511             {
1512                 // Disambiguate in favor of a unit struct/variant or constant pattern.
1513                 self.r.record_use(ident, ValueNS, binding, false);
1514                 Some(res)
1515             }
1516             Res::Def(DefKind::Ctor(..), _)
1517             | Res::Def(DefKind::Const, _)
1518             | Res::Def(DefKind::Static, _) => {
1519                 // This is unambiguously a fresh binding, either syntactically
1520                 // (e.g., `IDENT @ PAT` or `ref IDENT`) or because `IDENT` resolves
1521                 // to something unusable as a pattern (e.g., constructor function),
1522                 // but we still conservatively report an error, see
1523                 // issues/33118#issuecomment-233962221 for one reason why.
1524                 self.r.report_error(
1525                     ident.span,
1526                     ResolutionError::BindingShadowsSomethingUnacceptable(
1527                         pat_src.descr(),
1528                         ident.name,
1529                         binding,
1530                     ),
1531                 );
1532                 None
1533             }
1534             Res::Def(DefKind::Fn, _) | Res::Err => {
1535                 // These entities are explicitly allowed to be shadowed by fresh bindings.
1536                 None
1537             }
1538             res => {
1539                 span_bug!(
1540                     ident.span,
1541                     "unexpected resolution for an \
1542                                         identifier in pattern: {:?}",
1543                     res
1544                 );
1545             }
1546         }
1547     }
1548
1549     // High-level and context dependent path resolution routine.
1550     // Resolves the path and records the resolution into definition map.
1551     // If resolution fails tries several techniques to find likely
1552     // resolution candidates, suggest imports or other help, and report
1553     // errors in user friendly way.
1554     fn smart_resolve_path(
1555         &mut self,
1556         id: NodeId,
1557         qself: Option<&QSelf>,
1558         path: &Path,
1559         source: PathSource<'_>,
1560     ) {
1561         self.smart_resolve_path_fragment(
1562             id,
1563             qself,
1564             &Segment::from_path(path),
1565             path.span,
1566             source,
1567             CrateLint::SimplePath(id),
1568         );
1569     }
1570
1571     fn smart_resolve_path_fragment(
1572         &mut self,
1573         id: NodeId,
1574         qself: Option<&QSelf>,
1575         path: &[Segment],
1576         span: Span,
1577         source: PathSource<'_>,
1578         crate_lint: CrateLint,
1579     ) -> PartialRes {
1580         let ns = source.namespace();
1581         let is_expected = &|res| source.is_expected(res);
1582
1583         let report_errors = |this: &mut Self, res: Option<Res>| {
1584             let (err, candidates) = this.smart_resolve_report_errors(path, span, source, res);
1585             let def_id = this.parent_scope.module.normal_ancestor_id;
1586             let node_id = this.r.definitions.as_local_node_id(def_id).unwrap();
1587             let better = res.is_some();
1588             this.r.use_injections.push(UseError { err, candidates, node_id, better });
1589             PartialRes::new(Res::Err)
1590         };
1591
1592         let partial_res = match self.resolve_qpath_anywhere(
1593             id,
1594             qself,
1595             path,
1596             ns,
1597             span,
1598             source.defer_to_typeck(),
1599             crate_lint,
1600         ) {
1601             Some(partial_res) if partial_res.unresolved_segments() == 0 => {
1602                 if is_expected(partial_res.base_res()) || partial_res.base_res() == Res::Err {
1603                     partial_res
1604                 } else {
1605                     report_errors(self, Some(partial_res.base_res()))
1606                 }
1607             }
1608             Some(partial_res) if source.defer_to_typeck() => {
1609                 // Not fully resolved associated item `T::A::B` or `<T as Tr>::A::B`
1610                 // or `<T>::A::B`. If `B` should be resolved in value namespace then
1611                 // it needs to be added to the trait map.
1612                 if ns == ValueNS {
1613                     let item_name = path.last().unwrap().ident;
1614                     let traits = self.get_traits_containing_item(item_name, ns);
1615                     self.r.trait_map.insert(id, traits);
1616                 }
1617
1618                 let mut std_path = vec![Segment::from_ident(Ident::with_dummy_span(sym::std))];
1619                 std_path.extend(path);
1620                 if self.r.primitive_type_table.primitive_types.contains_key(&path[0].ident.name) {
1621                     let cl = CrateLint::No;
1622                     let ns = Some(ns);
1623                     if let PathResult::Module(_) | PathResult::NonModule(_) =
1624                         self.resolve_path(&std_path, ns, false, span, cl)
1625                     {
1626                         // check if we wrote `str::from_utf8` instead of `std::str::from_utf8`
1627                         let item_span =
1628                             path.iter().last().map(|segment| segment.ident.span).unwrap_or(span);
1629                         debug!("accessed item from `std` submodule as a bare type {:?}", std_path);
1630                         let mut hm = self.r.session.confused_type_with_std_module.borrow_mut();
1631                         hm.insert(item_span, span);
1632                         // In some places (E0223) we only have access to the full path
1633                         hm.insert(span, span);
1634                     }
1635                 }
1636                 partial_res
1637             }
1638             _ => report_errors(self, None),
1639         };
1640
1641         if let PathSource::TraitItem(..) = source {
1642         } else {
1643             // Avoid recording definition of `A::B` in `<T as A>::B::C`.
1644             self.r.record_partial_res(id, partial_res);
1645         }
1646         partial_res
1647     }
1648
1649     fn self_type_is_available(&mut self, span: Span) -> bool {
1650         let binding = self.resolve_ident_in_lexical_scope(
1651             Ident::with_dummy_span(kw::SelfUpper),
1652             TypeNS,
1653             None,
1654             span,
1655         );
1656         if let Some(LexicalScopeBinding::Res(res)) = binding { res != Res::Err } else { false }
1657     }
1658
1659     fn self_value_is_available(&mut self, self_span: Span, path_span: Span) -> bool {
1660         let ident = Ident::new(kw::SelfLower, self_span);
1661         let binding = self.resolve_ident_in_lexical_scope(ident, ValueNS, None, path_span);
1662         if let Some(LexicalScopeBinding::Res(res)) = binding { res != Res::Err } else { false }
1663     }
1664
1665     // Resolve in alternative namespaces if resolution in the primary namespace fails.
1666     fn resolve_qpath_anywhere(
1667         &mut self,
1668         id: NodeId,
1669         qself: Option<&QSelf>,
1670         path: &[Segment],
1671         primary_ns: Namespace,
1672         span: Span,
1673         defer_to_typeck: bool,
1674         crate_lint: CrateLint,
1675     ) -> Option<PartialRes> {
1676         let mut fin_res = None;
1677         for (i, ns) in [primary_ns, TypeNS, ValueNS].iter().cloned().enumerate() {
1678             if i == 0 || ns != primary_ns {
1679                 match self.resolve_qpath(id, qself, path, ns, span, crate_lint) {
1680                     // If defer_to_typeck, then resolution > no resolution,
1681                     // otherwise full resolution > partial resolution > no resolution.
1682                     Some(partial_res)
1683                         if partial_res.unresolved_segments() == 0 || defer_to_typeck =>
1684                     {
1685                         return Some(partial_res);
1686                     }
1687                     partial_res => {
1688                         if fin_res.is_none() {
1689                             fin_res = partial_res
1690                         }
1691                     }
1692                 }
1693             }
1694         }
1695
1696         // `MacroNS`
1697         assert!(primary_ns != MacroNS);
1698         if qself.is_none() {
1699             let path_seg = |seg: &Segment| PathSegment::from_ident(seg.ident);
1700             let path = Path { segments: path.iter().map(path_seg).collect(), span };
1701             if let Ok((_, res)) =
1702                 self.r.resolve_macro_path(&path, None, &self.parent_scope, false, false)
1703             {
1704                 return Some(PartialRes::new(res));
1705             }
1706         }
1707
1708         fin_res
1709     }
1710
1711     /// Handles paths that may refer to associated items.
1712     fn resolve_qpath(
1713         &mut self,
1714         id: NodeId,
1715         qself: Option<&QSelf>,
1716         path: &[Segment],
1717         ns: Namespace,
1718         span: Span,
1719         crate_lint: CrateLint,
1720     ) -> Option<PartialRes> {
1721         debug!(
1722             "resolve_qpath(id={:?}, qself={:?}, path={:?}, ns={:?}, span={:?})",
1723             id, qself, path, ns, span,
1724         );
1725
1726         if let Some(qself) = qself {
1727             if qself.position == 0 {
1728                 // This is a case like `<T>::B`, where there is no
1729                 // trait to resolve.  In that case, we leave the `B`
1730                 // segment to be resolved by type-check.
1731                 return Some(PartialRes::with_unresolved_segments(
1732                     Res::Def(DefKind::Mod, DefId::local(CRATE_DEF_INDEX)),
1733                     path.len(),
1734                 ));
1735             }
1736
1737             // Make sure `A::B` in `<T as A::B>::C` is a trait item.
1738             //
1739             // Currently, `path` names the full item (`A::B::C`, in
1740             // our example).  so we extract the prefix of that that is
1741             // the trait (the slice upto and including
1742             // `qself.position`). And then we recursively resolve that,
1743             // but with `qself` set to `None`.
1744             //
1745             // However, setting `qself` to none (but not changing the
1746             // span) loses the information about where this path
1747             // *actually* appears, so for the purposes of the crate
1748             // lint we pass along information that this is the trait
1749             // name from a fully qualified path, and this also
1750             // contains the full span (the `CrateLint::QPathTrait`).
1751             let ns = if qself.position + 1 == path.len() { ns } else { TypeNS };
1752             let partial_res = self.smart_resolve_path_fragment(
1753                 id,
1754                 None,
1755                 &path[..=qself.position],
1756                 span,
1757                 PathSource::TraitItem(ns),
1758                 CrateLint::QPathTrait { qpath_id: id, qpath_span: qself.path_span },
1759             );
1760
1761             // The remaining segments (the `C` in our example) will
1762             // have to be resolved by type-check, since that requires doing
1763             // trait resolution.
1764             return Some(PartialRes::with_unresolved_segments(
1765                 partial_res.base_res(),
1766                 partial_res.unresolved_segments() + path.len() - qself.position - 1,
1767             ));
1768         }
1769
1770         let result = match self.resolve_path(&path, Some(ns), true, span, crate_lint) {
1771             PathResult::NonModule(path_res) => path_res,
1772             PathResult::Module(ModuleOrUniformRoot::Module(module)) if !module.is_normal() => {
1773                 PartialRes::new(module.res().unwrap())
1774             }
1775             // In `a(::assoc_item)*` `a` cannot be a module. If `a` does resolve to a module we
1776             // don't report an error right away, but try to fallback to a primitive type.
1777             // So, we are still able to successfully resolve something like
1778             //
1779             // use std::u8; // bring module u8 in scope
1780             // fn f() -> u8 { // OK, resolves to primitive u8, not to std::u8
1781             //     u8::max_value() // OK, resolves to associated function <u8>::max_value,
1782             //                     // not to non-existent std::u8::max_value
1783             // }
1784             //
1785             // Such behavior is required for backward compatibility.
1786             // The same fallback is used when `a` resolves to nothing.
1787             PathResult::Module(ModuleOrUniformRoot::Module(_)) | PathResult::Failed { .. }
1788                 if (ns == TypeNS || path.len() > 1)
1789                     && self
1790                         .r
1791                         .primitive_type_table
1792                         .primitive_types
1793                         .contains_key(&path[0].ident.name) =>
1794             {
1795                 let prim = self.r.primitive_type_table.primitive_types[&path[0].ident.name];
1796                 PartialRes::with_unresolved_segments(Res::PrimTy(prim), path.len() - 1)
1797             }
1798             PathResult::Module(ModuleOrUniformRoot::Module(module)) => {
1799                 PartialRes::new(module.res().unwrap())
1800             }
1801             PathResult::Failed { is_error_from_last_segment: false, span, label, suggestion } => {
1802                 self.r.report_error(span, ResolutionError::FailedToResolve { label, suggestion });
1803                 PartialRes::new(Res::Err)
1804             }
1805             PathResult::Module(..) | PathResult::Failed { .. } => return None,
1806             PathResult::Indeterminate => bug!("indetermined path result in resolve_qpath"),
1807         };
1808
1809         if path.len() > 1
1810             && result.base_res() != Res::Err
1811             && path[0].ident.name != kw::PathRoot
1812             && path[0].ident.name != kw::DollarCrate
1813         {
1814             let unqualified_result = {
1815                 match self.resolve_path(
1816                     &[*path.last().unwrap()],
1817                     Some(ns),
1818                     false,
1819                     span,
1820                     CrateLint::No,
1821                 ) {
1822                     PathResult::NonModule(path_res) => path_res.base_res(),
1823                     PathResult::Module(ModuleOrUniformRoot::Module(module)) => {
1824                         module.res().unwrap()
1825                     }
1826                     _ => return Some(result),
1827                 }
1828             };
1829             if result.base_res() == unqualified_result {
1830                 let lint = lint::builtin::UNUSED_QUALIFICATIONS;
1831                 self.r.lint_buffer.buffer_lint(lint, id, span, "unnecessary qualification")
1832             }
1833         }
1834
1835         Some(result)
1836     }
1837
1838     fn with_resolved_label(&mut self, label: Option<Label>, id: NodeId, f: impl FnOnce(&mut Self)) {
1839         if let Some(label) = label {
1840             if label.ident.as_str().as_bytes()[1] != b'_' {
1841                 self.diagnostic_metadata.unused_labels.insert(id, label.ident.span);
1842             }
1843             self.with_label_rib(NormalRibKind, |this| {
1844                 let ident = label.ident.modern_and_legacy();
1845                 this.label_ribs.last_mut().unwrap().bindings.insert(ident, id);
1846                 f(this);
1847             });
1848         } else {
1849             f(self);
1850         }
1851     }
1852
1853     fn resolve_labeled_block(&mut self, label: Option<Label>, id: NodeId, block: &Block) {
1854         self.with_resolved_label(label, id, |this| this.visit_block(block));
1855     }
1856
1857     fn resolve_block(&mut self, block: &Block) {
1858         debug!("(resolving block) entering block");
1859         // Move down in the graph, if there's an anonymous module rooted here.
1860         let orig_module = self.parent_scope.module;
1861         let anonymous_module = self.r.block_map.get(&block.id).cloned(); // clones a reference
1862
1863         let mut num_macro_definition_ribs = 0;
1864         if let Some(anonymous_module) = anonymous_module {
1865             debug!("(resolving block) found anonymous module, moving down");
1866             self.ribs[ValueNS].push(Rib::new(ModuleRibKind(anonymous_module)));
1867             self.ribs[TypeNS].push(Rib::new(ModuleRibKind(anonymous_module)));
1868             self.parent_scope.module = anonymous_module;
1869         } else {
1870             self.ribs[ValueNS].push(Rib::new(NormalRibKind));
1871         }
1872
1873         // Descend into the block.
1874         for stmt in &block.stmts {
1875             if let StmtKind::Item(ref item) = stmt.kind {
1876                 if let ItemKind::MacroDef(..) = item.kind {
1877                     num_macro_definition_ribs += 1;
1878                     let res = self.r.definitions.local_def_id(item.id);
1879                     self.ribs[ValueNS].push(Rib::new(MacroDefinition(res)));
1880                     self.label_ribs.push(Rib::new(MacroDefinition(res)));
1881                 }
1882             }
1883
1884             self.visit_stmt(stmt);
1885         }
1886
1887         // Move back up.
1888         self.parent_scope.module = orig_module;
1889         for _ in 0..num_macro_definition_ribs {
1890             self.ribs[ValueNS].pop();
1891             self.label_ribs.pop();
1892         }
1893         self.ribs[ValueNS].pop();
1894         if anonymous_module.is_some() {
1895             self.ribs[TypeNS].pop();
1896         }
1897         debug!("(resolving block) leaving block");
1898     }
1899
1900     fn resolve_expr(&mut self, expr: &Expr, parent: Option<&Expr>) {
1901         // First, record candidate traits for this expression if it could
1902         // result in the invocation of a method call.
1903
1904         self.record_candidate_traits_for_expr_if_necessary(expr);
1905
1906         // Next, resolve the node.
1907         match expr.kind {
1908             ExprKind::Path(ref qself, ref path) => {
1909                 self.smart_resolve_path(expr.id, qself.as_ref(), path, PathSource::Expr(parent));
1910                 visit::walk_expr(self, expr);
1911             }
1912
1913             ExprKind::Struct(ref path, ..) => {
1914                 self.smart_resolve_path(expr.id, None, path, PathSource::Struct);
1915                 visit::walk_expr(self, expr);
1916             }
1917
1918             ExprKind::Break(Some(label), _) | ExprKind::Continue(Some(label)) => {
1919                 let node_id = self.search_label(label.ident, |rib, ident| {
1920                     rib.bindings.get(&ident.modern_and_legacy()).cloned()
1921                 });
1922                 match node_id {
1923                     None => {
1924                         // Search again for close matches...
1925                         // Picks the first label that is "close enough", which is not necessarily
1926                         // the closest match
1927                         let close_match = self.search_label(label.ident, |rib, ident| {
1928                             let names = rib.bindings.iter().filter_map(|(id, _)| {
1929                                 if id.span.ctxt() == label.ident.span.ctxt() {
1930                                     Some(&id.name)
1931                                 } else {
1932                                     None
1933                                 }
1934                             });
1935                             find_best_match_for_name(names, &ident.as_str(), None)
1936                         });
1937                         self.r.record_partial_res(expr.id, PartialRes::new(Res::Err));
1938                         self.r.report_error(
1939                             label.ident.span,
1940                             ResolutionError::UndeclaredLabel(&label.ident.as_str(), close_match),
1941                         );
1942                     }
1943                     Some(node_id) => {
1944                         // Since this res is a label, it is never read.
1945                         self.r.label_res_map.insert(expr.id, node_id);
1946                         self.diagnostic_metadata.unused_labels.remove(&node_id);
1947                     }
1948                 }
1949
1950                 // visit `break` argument if any
1951                 visit::walk_expr(self, expr);
1952             }
1953
1954             ExprKind::Let(ref pat, ref scrutinee) => {
1955                 self.visit_expr(scrutinee);
1956                 self.resolve_pattern_top(pat, PatternSource::Let);
1957             }
1958
1959             ExprKind::If(ref cond, ref then, ref opt_else) => {
1960                 self.with_rib(ValueNS, NormalRibKind, |this| {
1961                     this.visit_expr(cond);
1962                     this.visit_block(then);
1963                 });
1964                 opt_else.as_ref().map(|expr| self.visit_expr(expr));
1965             }
1966
1967             ExprKind::Loop(ref block, label) => self.resolve_labeled_block(label, expr.id, &block),
1968
1969             ExprKind::While(ref cond, ref block, label) => {
1970                 self.with_resolved_label(label, expr.id, |this| {
1971                     this.with_rib(ValueNS, NormalRibKind, |this| {
1972                         this.visit_expr(cond);
1973                         this.visit_block(block);
1974                     })
1975                 });
1976             }
1977
1978             ExprKind::ForLoop(ref pat, ref iter_expr, ref block, label) => {
1979                 self.visit_expr(iter_expr);
1980                 self.with_rib(ValueNS, NormalRibKind, |this| {
1981                     this.resolve_pattern_top(pat, PatternSource::For);
1982                     this.resolve_labeled_block(label, expr.id, block);
1983                 });
1984             }
1985
1986             ExprKind::Block(ref block, label) => self.resolve_labeled_block(label, block.id, block),
1987
1988             // Equivalent to `visit::walk_expr` + passing some context to children.
1989             ExprKind::Field(ref subexpression, _) => {
1990                 self.resolve_expr(subexpression, Some(expr));
1991             }
1992             ExprKind::MethodCall(ref segment, ref arguments) => {
1993                 let mut arguments = arguments.iter();
1994                 self.resolve_expr(arguments.next().unwrap(), Some(expr));
1995                 for argument in arguments {
1996                     self.resolve_expr(argument, None);
1997                 }
1998                 self.visit_path_segment(expr.span, segment);
1999             }
2000
2001             ExprKind::Call(ref callee, ref arguments) => {
2002                 self.resolve_expr(callee, Some(expr));
2003                 for argument in arguments {
2004                     self.resolve_expr(argument, None);
2005                 }
2006             }
2007             ExprKind::Type(ref type_expr, _) => {
2008                 self.diagnostic_metadata.current_type_ascription.push(type_expr.span);
2009                 visit::walk_expr(self, expr);
2010                 self.diagnostic_metadata.current_type_ascription.pop();
2011             }
2012             // `async |x| ...` gets desugared to `|x| future_from_generator(|| ...)`, so we need to
2013             // resolve the arguments within the proper scopes so that usages of them inside the
2014             // closure are detected as upvars rather than normal closure arg usages.
2015             ExprKind::Closure(_, IsAsync::Async { .. }, _, ref fn_decl, ref body, _span) => {
2016                 self.with_rib(ValueNS, NormalRibKind, |this| {
2017                     // Resolve arguments:
2018                     this.resolve_params(&fn_decl.inputs);
2019                     // No need to resolve return type --
2020                     // the outer closure return type is `FunctionRetTy::Default`.
2021
2022                     // Now resolve the inner closure
2023                     {
2024                         // No need to resolve arguments: the inner closure has none.
2025                         // Resolve the return type:
2026                         visit::walk_fn_ret_ty(this, &fn_decl.output);
2027                         // Resolve the body
2028                         this.visit_expr(body);
2029                     }
2030                 });
2031             }
2032             _ => {
2033                 visit::walk_expr(self, expr);
2034             }
2035         }
2036     }
2037
2038     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
2039         match expr.kind {
2040             ExprKind::Field(_, ident) => {
2041                 // FIXME(#6890): Even though you can't treat a method like a
2042                 // field, we need to add any trait methods we find that match
2043                 // the field name so that we can do some nice error reporting
2044                 // later on in typeck.
2045                 let traits = self.get_traits_containing_item(ident, ValueNS);
2046                 self.r.trait_map.insert(expr.id, traits);
2047             }
2048             ExprKind::MethodCall(ref segment, ..) => {
2049                 debug!("(recording candidate traits for expr) recording traits for {}", expr.id);
2050                 let traits = self.get_traits_containing_item(segment.ident, ValueNS);
2051                 self.r.trait_map.insert(expr.id, traits);
2052             }
2053             _ => {
2054                 // Nothing to do.
2055             }
2056         }
2057     }
2058
2059     fn get_traits_containing_item(
2060         &mut self,
2061         mut ident: Ident,
2062         ns: Namespace,
2063     ) -> Vec<TraitCandidate> {
2064         debug!("(getting traits containing item) looking for '{}'", ident.name);
2065
2066         let mut found_traits = Vec::new();
2067         // Look for the current trait.
2068         if let Some((module, _)) = self.current_trait_ref {
2069             if self
2070                 .r
2071                 .resolve_ident_in_module(
2072                     ModuleOrUniformRoot::Module(module),
2073                     ident,
2074                     ns,
2075                     &self.parent_scope,
2076                     false,
2077                     module.span,
2078                 )
2079                 .is_ok()
2080             {
2081                 let def_id = module.def_id().unwrap();
2082                 found_traits.push(TraitCandidate { def_id: def_id, import_ids: smallvec![] });
2083             }
2084         }
2085
2086         ident.span = ident.span.modern();
2087         let mut search_module = self.parent_scope.module;
2088         loop {
2089             self.get_traits_in_module_containing_item(ident, ns, search_module, &mut found_traits);
2090             search_module =
2091                 unwrap_or!(self.r.hygienic_lexical_parent(search_module, &mut ident.span), break);
2092         }
2093
2094         if let Some(prelude) = self.r.prelude {
2095             if !search_module.no_implicit_prelude {
2096                 self.get_traits_in_module_containing_item(ident, ns, prelude, &mut found_traits);
2097             }
2098         }
2099
2100         found_traits
2101     }
2102
2103     fn get_traits_in_module_containing_item(
2104         &mut self,
2105         ident: Ident,
2106         ns: Namespace,
2107         module: Module<'a>,
2108         found_traits: &mut Vec<TraitCandidate>,
2109     ) {
2110         assert!(ns == TypeNS || ns == ValueNS);
2111         let mut traits = module.traits.borrow_mut();
2112         if traits.is_none() {
2113             let mut collected_traits = Vec::new();
2114             module.for_each_child(self.r, |_, name, ns, binding| {
2115                 if ns != TypeNS {
2116                     return;
2117                 }
2118                 match binding.res() {
2119                     Res::Def(DefKind::Trait, _) | Res::Def(DefKind::TraitAlias, _) => {
2120                         collected_traits.push((name, binding))
2121                     }
2122                     _ => (),
2123                 }
2124             });
2125             *traits = Some(collected_traits.into_boxed_slice());
2126         }
2127
2128         for &(trait_name, binding) in traits.as_ref().unwrap().iter() {
2129             // Traits have pseudo-modules that can be used to search for the given ident.
2130             if let Some(module) = binding.module() {
2131                 let mut ident = ident;
2132                 if ident.span.glob_adjust(module.expansion, binding.span).is_none() {
2133                     continue;
2134                 }
2135                 if self
2136                     .r
2137                     .resolve_ident_in_module_unadjusted(
2138                         ModuleOrUniformRoot::Module(module),
2139                         ident,
2140                         ns,
2141                         &self.parent_scope,
2142                         false,
2143                         module.span,
2144                     )
2145                     .is_ok()
2146                 {
2147                     let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
2148                     let trait_def_id = module.def_id().unwrap();
2149                     found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
2150                 }
2151             } else if let Res::Def(DefKind::TraitAlias, _) = binding.res() {
2152                 // For now, just treat all trait aliases as possible candidates, since we don't
2153                 // know if the ident is somewhere in the transitive bounds.
2154                 let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
2155                 let trait_def_id = binding.res().def_id();
2156                 found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
2157             } else {
2158                 bug!("candidate is not trait or trait alias?")
2159             }
2160         }
2161     }
2162
2163     fn find_transitive_imports(
2164         &mut self,
2165         mut kind: &NameBindingKind<'_>,
2166         trait_name: Ident,
2167     ) -> SmallVec<[NodeId; 1]> {
2168         let mut import_ids = smallvec![];
2169         while let NameBindingKind::Import { directive, binding, .. } = kind {
2170             self.r.maybe_unused_trait_imports.insert(directive.id);
2171             self.r.add_to_glob_map(&directive, trait_name);
2172             import_ids.push(directive.id);
2173             kind = &binding.kind;
2174         }
2175         import_ids
2176     }
2177 }
2178
2179 impl<'a> Resolver<'a> {
2180     pub(crate) fn late_resolve_crate(&mut self, krate: &Crate) {
2181         let mut late_resolution_visitor = LateResolutionVisitor::new(self);
2182         visit::walk_crate(&mut late_resolution_visitor, krate);
2183         for (id, span) in late_resolution_visitor.diagnostic_metadata.unused_labels.iter() {
2184             self.lint_buffer.buffer_lint(lint::builtin::UNUSED_LABELS, *id, *span, "unused label");
2185         }
2186     }
2187 }