src/librustc_resolve/late.rs

   1 use GenericParameters::*;
   2
   3 use crate::{path_names_to_string, resolve_error};
   4 use crate::{AliasPossibility, BindingError, CrateLint, LexicalScopeBinding, Module};
   5 use crate::{ModuleOrUniformRoot, NameBinding, NameBindingKind, ParentScope, PathResult};
   6 use crate::{PathSource, ResolutionError, Resolver, Rib, RibKind, Segment, UseError};
   7 use crate::RibKind::*;
   8
   9 use log::debug;
  10 use rustc::{bug, lint, span_bug};
  11 use rustc::hir::def::{self, PartialRes, DefKind, CtorKind, PerNS};
  12 use rustc::hir::def::Namespace::{self, *};
  13 use rustc::hir::def_id::{DefId, CRATE_DEF_INDEX};
  14 use rustc::hir::TraitCandidate;
  15 use rustc::util::nodemap::FxHashMap;
  16 use smallvec::{smallvec, SmallVec};
  17 use syntax::{unwrap_or, walk_list};
  18 use syntax::ast::*;
  19 use syntax::ptr::P;
  20 use syntax::symbol::{kw, sym};
  21 use syntax::util::lev_distance::find_best_match_for_name;
  22 use syntax::visit::{self, Visitor, FnKind};
  23 use syntax_pos::Span;
  24
  25 use std::collections::BTreeSet;
  26 use std::mem::replace;
  27
  28 mod diagnostics;
  29
  30 type Res = def::Res<NodeId>;
  31
  32 /// Map from the name in a pattern to its binding mode.
  33 type BindingMap = FxHashMap<Ident, BindingInfo>;
  34
  35 #[derive(Copy, Clone, Debug)]
  36 struct BindingInfo {
  37     span: Span,
  38     binding_mode: BindingMode,
  39 }
  40
  41 #[derive(Copy, Clone)]
  42 enum GenericParameters<'a, 'b> {
  43     NoGenericParams,
  44     HasGenericParams(// Type parameters.
  45                       &'b Generics,
  46
  47                       // The kind of the rib used for type parameters.
  48                       RibKind<'a>),
  49 }
  50
  51 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  52 enum PatternSource {
  53     Match,
  54     Let,
  55     For,
  56     FnParam,
  57 }
  58
  59 impl PatternSource {
  60     fn descr(self) -> &'static str {
  61         match self {
  62             PatternSource::Match => "match binding",
  63             PatternSource::Let => "let binding",
  64             PatternSource::For => "for binding",
  65             PatternSource::FnParam => "function parameter",
  66         }
  67     }
  68 }
  69
  70 struct LateResolutionVisitor<'a, 'b> {
  71     r: &'b mut Resolver<'a>,
  72
  73     /// The module that represents the current item scope.
  74     parent_scope: ParentScope<'a>,
  75
  76     /// The current set of local scopes for types and values.
  77     /// FIXME #4948: Reuse ribs to avoid allocation.
  78     ribs: PerNS<Vec<Rib<'a>>>,
  79
  80     /// The current set of local scopes, for labels.
  81     label_ribs: Vec<Rib<'a, NodeId>>,
  82
  83     /// The trait that the current context can refer to.
  84     current_trait_ref: Option<(Module<'a>, TraitRef)>,
  85
  86     /// The current trait's associated types' ident, used for diagnostic suggestions.
  87     current_trait_assoc_types: Vec<Ident>,
  88
  89     /// The current self type if inside an impl (used for better errors).
  90     current_self_type: Option<Ty>,
  91
  92     /// The current self item if inside an ADT (used for better errors).
  93     current_self_item: Option<NodeId>,
  94
  95     /// A list of labels as of yet unused. Labels will be removed from this map when
  96     /// they are used (in a `break` or `continue` statement)
  97     unused_labels: FxHashMap<NodeId, Span>,
  98
  99     /// Only used for better errors on `fn(): fn()`.
 100     current_type_ascription: Vec<Span>,
 101 }
 102
 103 /// Walks the whole crate in DFS order, visiting each item, resolving names as it goes.
 104 impl<'a, 'tcx> Visitor<'tcx> for LateResolutionVisitor<'a, '_> {
 105     fn visit_item(&mut self, item: &'tcx Item) {
 106         self.resolve_item(item);
 107     }
 108     fn visit_arm(&mut self, arm: &'tcx Arm) {
 109         self.resolve_arm(arm);
 110     }
 111     fn visit_block(&mut self, block: &'tcx Block) {
 112         self.resolve_block(block);
 113     }
 114     fn visit_anon_const(&mut self, constant: &'tcx AnonConst) {
 115         debug!("visit_anon_const {:?}", constant);
 116         self.with_constant_rib(|this| {
 117             visit::walk_anon_const(this, constant);
 118         });
 119     }
 120     fn visit_expr(&mut self, expr: &'tcx Expr) {
 121         self.resolve_expr(expr, None);
 122     }
 123     fn visit_local(&mut self, local: &'tcx Local) {
 124         self.resolve_local(local);
 125     }
 126     fn visit_ty(&mut self, ty: &'tcx Ty) {
 127         match ty.node {
 128             TyKind::Path(ref qself, ref path) => {
 129                 self.smart_resolve_path(ty.id, qself.as_ref(), path, PathSource::Type);
 130             }
 131             TyKind::ImplicitSelf => {
 132                 let self_ty = Ident::with_empty_ctxt(kw::SelfUpper);
 133                 let res = self.resolve_ident_in_lexical_scope(self_ty, TypeNS, Some(ty.id), ty.span)
 134                               .map_or(Res::Err, |d| d.res());
 135                 self.r.record_partial_res(ty.id, PartialRes::new(res));
 136             }
 137             _ => (),
 138         }
 139         visit::walk_ty(self, ty);
 140     }
 141     fn visit_poly_trait_ref(&mut self,
 142                             tref: &'tcx PolyTraitRef,
 143                             m: &'tcx TraitBoundModifier) {
 144         self.smart_resolve_path(tref.trait_ref.ref_id, None,
 145                                 &tref.trait_ref.path, PathSource::Trait(AliasPossibility::Maybe));
 146         visit::walk_poly_trait_ref(self, tref, m);
 147     }
 148     fn visit_foreign_item(&mut self, foreign_item: &'tcx ForeignItem) {
 149         let generic_params = match foreign_item.node {
 150             ForeignItemKind::Fn(_, ref generics) => {
 151                 HasGenericParams(generics, ItemRibKind)
 152             }
 153             ForeignItemKind::Static(..) => NoGenericParams,
 154             ForeignItemKind::Ty => NoGenericParams,
 155             ForeignItemKind::Macro(..) => NoGenericParams,
 156         };
 157         self.with_generic_param_rib(generic_params, |this| {
 158             visit::walk_foreign_item(this, foreign_item);
 159         });
 160     }
 161     fn visit_fn(&mut self,
 162                 function_kind: FnKind<'tcx>,
 163                 declaration: &'tcx FnDecl,
 164                 _: Span,
 165                 _: NodeId)
 166     {
 167         debug!("(resolving function) entering function");
 168         let rib_kind = match function_kind {
 169             FnKind::ItemFn(..) => FnItemRibKind,
 170             FnKind::Method(..) | FnKind::Closure(_) => NormalRibKind,
 171         };
 172
 173         // Create a value rib for the function.
 174         self.ribs[ValueNS].push(Rib::new(rib_kind));
 175
 176         // Create a label rib for the function.
 177         self.label_ribs.push(Rib::new(rib_kind));
 178
 179         // Add each argument to the rib.
 180         let mut bindings_list = FxHashMap::default();
 181         for argument in &declaration.inputs {
 182             self.resolve_pattern(&argument.pat, PatternSource::FnParam, &mut bindings_list);
 183
 184             self.visit_ty(&argument.ty);
 185
 186             debug!("(resolving function) recorded argument");
 187         }
 188         visit::walk_fn_ret_ty(self, &declaration.output);
 189
 190         // Resolve the function body, potentially inside the body of an async closure
 191         match function_kind {
 192             FnKind::ItemFn(.., body) |
 193             FnKind::Method(.., body) => {
 194                 self.visit_block(body);
 195             }
 196             FnKind::Closure(body) => {
 197                 self.visit_expr(body);
 198             }
 199         };
 200
 201         debug!("(resolving function) leaving function");
 202
 203         self.label_ribs.pop();
 204         self.ribs[ValueNS].pop();
 205     }
 206
 207     fn visit_generics(&mut self, generics: &'tcx Generics) {
 208         // For type parameter defaults, we have to ban access
 209         // to following type parameters, as the InternalSubsts can only
 210         // provide previous type parameters as they're built. We
 211         // put all the parameters on the ban list and then remove
 212         // them one by one as they are processed and become available.
 213         let mut default_ban_rib = Rib::new(ForwardTyParamBanRibKind);
 214         let mut found_default = false;
 215         default_ban_rib.bindings.extend(generics.params.iter()
 216             .filter_map(|param| match param.kind {
 217                 GenericParamKind::Const { .. } |
 218                 GenericParamKind::Lifetime { .. } => None,
 219                 GenericParamKind::Type { ref default, .. } => {
 220                     found_default |= default.is_some();
 221                     if found_default {
 222                         Some((Ident::with_empty_ctxt(param.ident.name), Res::Err))
 223                     } else {
 224                         None
 225                     }
 226                 }
 227             }));
 228
 229         // We also ban access to type parameters for use as the types of const parameters.
 230         let mut const_ty_param_ban_rib = Rib::new(TyParamAsConstParamTy);
 231         const_ty_param_ban_rib.bindings.extend(generics.params.iter()
 232             .filter(|param| {
 233                 if let GenericParamKind::Type { .. } = param.kind {
 234                     true
 235                 } else {
 236                     false
 237                 }
 238             })
 239             .map(|param| (Ident::with_empty_ctxt(param.ident.name), Res::Err)));
 240
 241         for param in &generics.params {
 242             match param.kind {
 243                 GenericParamKind::Lifetime { .. } => self.visit_generic_param(param),
 244                 GenericParamKind::Type { ref default, .. } => {
 245                     for bound in &param.bounds {
 246                         self.visit_param_bound(bound);
 247                     }
 248
 249                     if let Some(ref ty) = default {
 250                         self.ribs[TypeNS].push(default_ban_rib);
 251                         self.visit_ty(ty);
 252                         default_ban_rib = self.ribs[TypeNS].pop().unwrap();
 253                     }
 254
 255                     // Allow all following defaults to refer to this type parameter.
 256                     default_ban_rib.bindings.remove(&Ident::with_empty_ctxt(param.ident.name));
 257                 }
 258                 GenericParamKind::Const { ref ty } => {
 259                     self.ribs[TypeNS].push(const_ty_param_ban_rib);
 260
 261                     for bound in &param.bounds {
 262                         self.visit_param_bound(bound);
 263                     }
 264
 265                     self.visit_ty(ty);
 266
 267                     const_ty_param_ban_rib = self.ribs[TypeNS].pop().unwrap();
 268                 }
 269             }
 270         }
 271         for p in &generics.where_clause.predicates {
 272             self.visit_where_predicate(p);
 273         }
 274     }
 275 }
 276
 277 impl<'a, 'b> LateResolutionVisitor<'a, '_> {
 278     fn new(resolver: &'b mut Resolver<'a>) -> LateResolutionVisitor<'a, 'b> {
 279         // During late resolution we only track the module component of the parent scope,
 280         // although it may be useful to track other components as well for diagnostics.
 281         let parent_scope = resolver.dummy_parent_scope();
 282         let graph_root = resolver.graph_root;
 283         LateResolutionVisitor {
 284             r: resolver,
 285             parent_scope,
 286             ribs: PerNS {
 287                 value_ns: vec![Rib::new(ModuleRibKind(graph_root))],
 288                 type_ns: vec![Rib::new(ModuleRibKind(graph_root))],
 289                 macro_ns: vec![Rib::new(ModuleRibKind(graph_root))],
 290             },
 291             label_ribs: Vec::new(),
 292             current_trait_ref: None,
 293             current_trait_assoc_types: Vec::new(),
 294             current_self_type: None,
 295             current_self_item: None,
 296             unused_labels: Default::default(),
 297             current_type_ascription: Vec::new(),
 298         }
 299     }
 300
 301     fn resolve_ident_in_lexical_scope(&mut self,
 302                                       ident: Ident,
 303                                       ns: Namespace,
 304                                       record_used_id: Option<NodeId>,
 305                                       path_span: Span)
 306                                       -> Option<LexicalScopeBinding<'a>> {
 307         self.r.resolve_ident_in_lexical_scope(
 308             ident, ns, &self.parent_scope, record_used_id, path_span, &self.ribs[ns]
 309         )
 310     }
 311
 312     fn resolve_path(
 313         &mut self,
 314         path: &[Segment],
 315         opt_ns: Option<Namespace>, // `None` indicates a module path in import
 316         record_used: bool,
 317         path_span: Span,
 318         crate_lint: CrateLint,
 319     ) -> PathResult<'a> {
 320         self.r.resolve_path_with_ribs(
 321             path, opt_ns, &self.parent_scope, record_used, path_span, crate_lint, &self.ribs
 322         )
 323     }
 324
 325     // AST resolution
 326     //
 327     // We maintain a list of value ribs and type ribs.
 328     //
 329     // Simultaneously, we keep track of the current position in the module
 330     // graph in the `parent_scope.module` pointer. When we go to resolve a name in
 331     // the value or type namespaces, we first look through all the ribs and
 332     // then query the module graph. When we resolve a name in the module
 333     // namespace, we can skip all the ribs (since nested modules are not
 334     // allowed within blocks in Rust) and jump straight to the current module
 335     // graph node.
 336     //
 337     // Named implementations are handled separately. When we find a method
 338     // call, we consult the module node to find all of the implementations in
 339     // scope. This information is lazily cached in the module node. We then
 340     // generate a fake "implementation scope" containing all the
 341     // implementations thus found, for compatibility with old resolve pass.
 342
 343     fn with_scope<F, T>(&mut self, id: NodeId, f: F) -> T
 344         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>) -> T
 345     {
 346         let id = self.r.definitions.local_def_id(id);
 347         let module = self.r.module_map.get(&id).cloned(); // clones a reference
 348         if let Some(module) = module {
 349             // Move down in the graph.
 350             let orig_module = replace(&mut self.parent_scope.module, module);
 351             self.ribs[ValueNS].push(Rib::new(ModuleRibKind(module)));
 352             self.ribs[TypeNS].push(Rib::new(ModuleRibKind(module)));
 353
 354             self.r.finalize_current_module_macro_resolutions(module);
 355             let ret = f(self);
 356
 357             self.parent_scope.module = orig_module;
 358             self.ribs[ValueNS].pop();
 359             self.ribs[TypeNS].pop();
 360             ret
 361         } else {
 362             f(self)
 363         }
 364     }
 365
 366     /// Searches the current set of local scopes for labels. Returns the first non-`None` label that
 367     /// is returned by the given predicate function
 368     ///
 369     /// Stops after meeting a closure.
 370     fn search_label<P, R>(&self, mut ident: Ident, pred: P) -> Option<R>
 371         where P: Fn(&Rib<'_, NodeId>, Ident) -> Option<R>
 372     {
 373         for rib in self.label_ribs.iter().rev() {
 374             match rib.kind {
 375                 NormalRibKind => {}
 376                 // If an invocation of this macro created `ident`, give up on `ident`
 377                 // and switch to `ident`'s source from the macro definition.
 378                 MacroDefinition(def) => {
 379                     if def == self.r.macro_def(ident.span.ctxt()) {
 380                         ident.span.remove_mark();
 381                     }
 382                 }
 383                 _ => {
 384                     // Do not resolve labels across function boundary
 385                     return None;
 386                 }
 387             }
 388             let r = pred(rib, ident);
 389             if r.is_some() {
 390                 return r;
 391             }
 392         }
 393         None
 394     }
 395
 396     fn resolve_adt(&mut self, item: &Item, generics: &Generics) {
 397         debug!("resolve_adt");
 398         self.with_current_self_item(item, |this| {
 399             this.with_generic_param_rib(HasGenericParams(generics, ItemRibKind), |this| {
 400                 let item_def_id = this.r.definitions.local_def_id(item.id);
 401                 this.with_self_rib(Res::SelfTy(None, Some(item_def_id)), |this| {
 402                     visit::walk_item(this, item);
 403                 });
 404             });
 405         });
 406     }
 407
 408     fn future_proof_import(&mut self, use_tree: &UseTree) {
 409         let segments = &use_tree.prefix.segments;
 410         if !segments.is_empty() {
 411             let ident = segments[0].ident;
 412             if ident.is_path_segment_keyword() || ident.span.rust_2015() {
 413                 return;
 414             }
 415
 416             let nss = match use_tree.kind {
 417                 UseTreeKind::Simple(..) if segments.len() == 1 => &[TypeNS, ValueNS][..],
 418                 _ => &[TypeNS],
 419             };
 420             let report_error = |this: &Self, ns| {
 421                 let what = if ns == TypeNS { "type parameters" } else { "local variables" };
 422                 this.r.session.span_err(ident.span, &format!("imports cannot refer to {}", what));
 423             };
 424
 425             for &ns in nss {
 426                 match self.resolve_ident_in_lexical_scope(ident, ns, None, use_tree.prefix.span) {
 427                     Some(LexicalScopeBinding::Res(..)) => {
 428                         report_error(self, ns);
 429                     }
 430                     Some(LexicalScopeBinding::Item(binding)) => {
 431                         let orig_blacklisted_binding =
 432                             replace(&mut self.r.blacklisted_binding, Some(binding));
 433                         if let Some(LexicalScopeBinding::Res(..)) =
 434                                 self.resolve_ident_in_lexical_scope(ident, ns, None,
 435                                                                     use_tree.prefix.span) {
 436                             report_error(self, ns);
 437                         }
 438                         self.r.blacklisted_binding = orig_blacklisted_binding;
 439                     }
 440                     None => {}
 441                 }
 442             }
 443         } else if let UseTreeKind::Nested(use_trees) = &use_tree.kind {
 444             for (use_tree, _) in use_trees {
 445                 self.future_proof_import(use_tree);
 446             }
 447         }
 448     }
 449
 450     fn resolve_item(&mut self, item: &Item) {
 451         let name = item.ident.name;
 452         debug!("(resolving item) resolving {} ({:?})", name, item.node);
 453
 454         match item.node {
 455             ItemKind::TyAlias(_, ref generics) |
 456             ItemKind::OpaqueTy(_, ref generics) |
 457             ItemKind::Fn(_, _, ref generics, _) => {
 458                 self.with_generic_param_rib(
 459                     HasGenericParams(generics, ItemRibKind),
 460                     |this| visit::walk_item(this, item)
 461                 );
 462             }
 463
 464             ItemKind::Enum(_, ref generics) |
 465             ItemKind::Struct(_, ref generics) |
 466             ItemKind::Union(_, ref generics) => {
 467                 self.resolve_adt(item, generics);
 468             }
 469
 470             ItemKind::Impl(.., ref generics, ref opt_trait_ref, ref self_type, ref impl_items) =>
 471                 self.resolve_implementation(generics,
 472                                             opt_trait_ref,
 473                                             &self_type,
 474                                             item.id,
 475                                             impl_items),
 476
 477             ItemKind::Trait(.., ref generics, ref bounds, ref trait_items) => {
 478                 // Create a new rib for the trait-wide type parameters.
 479                 self.with_generic_param_rib(HasGenericParams(generics, ItemRibKind), |this| {
 480                     let local_def_id = this.r.definitions.local_def_id(item.id);
 481                     this.with_self_rib(Res::SelfTy(Some(local_def_id), None), |this| {
 482                         this.visit_generics(generics);
 483                         walk_list!(this, visit_param_bound, bounds);
 484
 485                         for trait_item in trait_items {
 486                             this.with_trait_items(trait_items, |this| {
 487                                 let generic_params = HasGenericParams(
 488                                     &trait_item.generics,
 489                                     AssocItemRibKind,
 490                                 );
 491                                 this.with_generic_param_rib(generic_params, |this| {
 492                                     match trait_item.node {
 493                                         TraitItemKind::Const(ref ty, ref default) => {
 494                                             this.visit_ty(ty);
 495
 496                                             // Only impose the restrictions of
 497                                             // ConstRibKind for an actual constant
 498                                             // expression in a provided default.
 499                                             if let Some(ref expr) = *default{
 500                                                 this.with_constant_rib(|this| {
 501                                                     this.visit_expr(expr);
 502                                                 });
 503                                             }
 504                                         }
 505                                         TraitItemKind::Method(_, _) => {
 506                                             visit::walk_trait_item(this, trait_item)
 507                                         }
 508                                         TraitItemKind::Type(..) => {
 509                                             visit::walk_trait_item(this, trait_item)
 510                                         }
 511                                         TraitItemKind::Macro(_) => {
 512                                             panic!("unexpanded macro in resolve!")
 513                                         }
 514                                     };
 515                                 });
 516                             });
 517                         }
 518                     });
 519                 });
 520             }
 521
 522             ItemKind::TraitAlias(ref generics, ref bounds) => {
 523                 // Create a new rib for the trait-wide type parameters.
 524                 self.with_generic_param_rib(HasGenericParams(generics, ItemRibKind), |this| {
 525                     let local_def_id = this.r.definitions.local_def_id(item.id);
 526                     this.with_self_rib(Res::SelfTy(Some(local_def_id), None), |this| {
 527                         this.visit_generics(generics);
 528                         walk_list!(this, visit_param_bound, bounds);
 529                     });
 530                 });
 531             }
 532
 533             ItemKind::Mod(_) | ItemKind::ForeignMod(_) => {
 534                 self.with_scope(item.id, |this| {
 535                     visit::walk_item(this, item);
 536                 });
 537             }
 538
 539             ItemKind::Static(ref ty, _, ref expr) |
 540             ItemKind::Const(ref ty, ref expr) => {
 541                 debug!("resolve_item ItemKind::Const");
 542                 self.with_item_rib(|this| {
 543                     this.visit_ty(ty);
 544                     this.with_constant_rib(|this| {
 545                         this.visit_expr(expr);
 546                     });
 547                 });
 548             }
 549
 550             ItemKind::Use(ref use_tree) => {
 551                 self.future_proof_import(use_tree);
 552             }
 553
 554             ItemKind::ExternCrate(..) |
 555             ItemKind::MacroDef(..) | ItemKind::GlobalAsm(..) => {
 556                 // do nothing, these are just around to be encoded
 557             }
 558
 559             ItemKind::Mac(_) => panic!("unexpanded macro in resolve!"),
 560         }
 561     }
 562
 563     fn with_generic_param_rib<'c, F>(&'c mut self, generic_params: GenericParameters<'a, 'c>, f: F)
 564         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
 565     {
 566         debug!("with_generic_param_rib");
 567         match generic_params {
 568             HasGenericParams(generics, rib_kind) => {
 569                 let mut function_type_rib = Rib::new(rib_kind);
 570                 let mut function_value_rib = Rib::new(rib_kind);
 571                 let mut seen_bindings = FxHashMap::default();
 572                 for param in &generics.params {
 573                     match param.kind {
 574                         GenericParamKind::Lifetime { .. } => {}
 575                         GenericParamKind::Type { .. } => {
 576                             let ident = param.ident.modern();
 577                             debug!("with_generic_param_rib: {}", param.id);
 578
 579                             if seen_bindings.contains_key(&ident) {
 580                                 let span = seen_bindings.get(&ident).unwrap();
 581                                 let err = ResolutionError::NameAlreadyUsedInParameterList(
 582                                     ident.name,
 583                                     *span,
 584                                 );
 585                                 resolve_error(&self.r, param.ident.span, err);
 586                             }
 587                             seen_bindings.entry(ident).or_insert(param.ident.span);
 588
 589                             // Plain insert (no renaming).
 590                             let res = Res::Def(
 591                                 DefKind::TyParam,
 592                                 self.r.definitions.local_def_id(param.id),
 593                             );
 594                             function_type_rib.bindings.insert(ident, res);
 595                             self.r.record_partial_res(param.id, PartialRes::new(res));
 596                         }
 597                         GenericParamKind::Const { .. } => {
 598                             let ident = param.ident.modern();
 599                             debug!("with_generic_param_rib: {}", param.id);
 600
 601                             if seen_bindings.contains_key(&ident) {
 602                                 let span = seen_bindings.get(&ident).unwrap();
 603                                 let err = ResolutionError::NameAlreadyUsedInParameterList(
 604                                     ident.name,
 605                                     *span,
 606                                 );
 607                                 resolve_error(&self.r, param.ident.span, err);
 608                             }
 609                             seen_bindings.entry(ident).or_insert(param.ident.span);
 610
 611                             let res = Res::Def(
 612                                 DefKind::ConstParam,
 613                                 self.r.definitions.local_def_id(param.id),
 614                             );
 615                             function_value_rib.bindings.insert(ident, res);
 616                             self.r.record_partial_res(param.id, PartialRes::new(res));
 617                         }
 618                     }
 619                 }
 620                 self.ribs[ValueNS].push(function_value_rib);
 621                 self.ribs[TypeNS].push(function_type_rib);
 622             }
 623
 624             NoGenericParams => {
 625                 // Nothing to do.
 626             }
 627         }
 628
 629         f(self);
 630
 631         if let HasGenericParams(..) = generic_params {
 632             self.ribs[TypeNS].pop();
 633             self.ribs[ValueNS].pop();
 634         }
 635     }
 636
 637     fn with_label_rib<F>(&mut self, f: F)
 638         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
 639     {
 640         self.label_ribs.push(Rib::new(NormalRibKind));
 641         f(self);
 642         self.label_ribs.pop();
 643     }
 644
 645     fn with_item_rib<F>(&mut self, f: F)
 646         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
 647     {
 648         self.ribs[ValueNS].push(Rib::new(ItemRibKind));
 649         self.ribs[TypeNS].push(Rib::new(ItemRibKind));
 650         f(self);
 651         self.ribs[TypeNS].pop();
 652         self.ribs[ValueNS].pop();
 653     }
 654
 655     fn with_constant_rib<F>(&mut self, f: F)
 656         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
 657     {
 658         debug!("with_constant_rib");
 659         self.ribs[ValueNS].push(Rib::new(ConstantItemRibKind));
 660         self.label_ribs.push(Rib::new(ConstantItemRibKind));
 661         f(self);
 662         self.label_ribs.pop();
 663         self.ribs[ValueNS].pop();
 664     }
 665
 666     fn with_current_self_type<T, F>(&mut self, self_type: &Ty, f: F) -> T
 667         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>) -> T
 668     {
 669         // Handle nested impls (inside fn bodies)
 670         let previous_value = replace(&mut self.current_self_type, Some(self_type.clone()));
 671         let result = f(self);
 672         self.current_self_type = previous_value;
 673         result
 674     }
 675
 676     fn with_current_self_item<T, F>(&mut self, self_item: &Item, f: F) -> T
 677         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>) -> T
 678     {
 679         let previous_value = replace(&mut self.current_self_item, Some(self_item.id));
 680         let result = f(self);
 681         self.current_self_item = previous_value;
 682         result
 683     }
 684
 685     /// When evaluating a `trait` use its associated types' idents for suggestionsa in E0412.
 686     fn with_trait_items<T, F>(&mut self, trait_items: &Vec<TraitItem>, f: F) -> T
 687         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>) -> T
 688     {
 689         let trait_assoc_types = replace(
 690             &mut self.current_trait_assoc_types,
 691             trait_items.iter().filter_map(|item| match &item.node {
 692                 TraitItemKind::Type(bounds, _) if bounds.len() == 0 => Some(item.ident),
 693                 _ => None,
 694             }).collect(),
 695         );
 696         let result = f(self);
 697         self.current_trait_assoc_types = trait_assoc_types;
 698         result
 699     }
 700
 701     /// This is called to resolve a trait reference from an `impl` (i.e., `impl Trait for Foo`).
 702     fn with_optional_trait_ref<T, F>(&mut self, opt_trait_ref: Option<&TraitRef>, f: F) -> T
 703         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>, Option<DefId>) -> T
 704     {
 705         let mut new_val = None;
 706         let mut new_id = None;
 707         if let Some(trait_ref) = opt_trait_ref {
 708             let path: Vec<_> = Segment::from_path(&trait_ref.path);
 709             let res = self.smart_resolve_path_fragment(
 710                 trait_ref.ref_id,
 711                 None,
 712                 &path,
 713                 trait_ref.path.span,
 714                 PathSource::Trait(AliasPossibility::No),
 715                 CrateLint::SimplePath(trait_ref.ref_id),
 716             ).base_res();
 717             if res != Res::Err {
 718                 new_id = Some(res.def_id());
 719                 let span = trait_ref.path.span;
 720                 if let PathResult::Module(ModuleOrUniformRoot::Module(module)) =
 721                     self.resolve_path(
 722                         &path,
 723                         Some(TypeNS),
 724                         false,
 725                         span,
 726                         CrateLint::SimplePath(trait_ref.ref_id),
 727                     )
 728                 {
 729                     new_val = Some((module, trait_ref.clone()));
 730                 }
 731             }
 732         }
 733         let original_trait_ref = replace(&mut self.current_trait_ref, new_val);
 734         let result = f(self, new_id);
 735         self.current_trait_ref = original_trait_ref;
 736         result
 737     }
 738
 739     fn with_self_rib<F>(&mut self, self_res: Res, f: F)
 740         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
 741     {
 742         let mut self_type_rib = Rib::new(NormalRibKind);
 743
 744         // Plain insert (no renaming, since types are not currently hygienic)
 745         self_type_rib.bindings.insert(Ident::with_empty_ctxt(kw::SelfUpper), self_res);
 746         self.ribs[TypeNS].push(self_type_rib);
 747         f(self);
 748         self.ribs[TypeNS].pop();
 749     }
 750
 751     fn with_self_struct_ctor_rib<F>(&mut self, impl_id: DefId, f: F)
 752         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
 753     {
 754         let self_res = Res::SelfCtor(impl_id);
 755         let mut self_type_rib = Rib::new(NormalRibKind);
 756         self_type_rib.bindings.insert(Ident::with_empty_ctxt(kw::SelfUpper), self_res);
 757         self.ribs[ValueNS].push(self_type_rib);
 758         f(self);
 759         self.ribs[ValueNS].pop();
 760     }
 761
 762     fn resolve_implementation(&mut self,
 763                               generics: &Generics,
 764                               opt_trait_reference: &Option<TraitRef>,
 765                               self_type: &Ty,
 766                               item_id: NodeId,
 767                               impl_items: &[ImplItem]) {
 768         debug!("resolve_implementation");
 769         // If applicable, create a rib for the type parameters.
 770         self.with_generic_param_rib(HasGenericParams(generics, ItemRibKind), |this| {
 771             // Dummy self type for better errors if `Self` is used in the trait path.
 772             this.with_self_rib(Res::SelfTy(None, None), |this| {
 773                 // Resolve the trait reference, if necessary.
 774                 this.with_optional_trait_ref(opt_trait_reference.as_ref(), |this, trait_id| {
 775                     let item_def_id = this.r.definitions.local_def_id(item_id);
 776                     this.with_self_rib(Res::SelfTy(trait_id, Some(item_def_id)), |this| {
 777                         if let Some(trait_ref) = opt_trait_reference.as_ref() {
 778                             // Resolve type arguments in the trait path.
 779                             visit::walk_trait_ref(this, trait_ref);
 780                         }
 781                         // Resolve the self type.
 782                         this.visit_ty(self_type);
 783                         // Resolve the generic parameters.
 784                         this.visit_generics(generics);
 785                         // Resolve the items within the impl.
 786                         this.with_current_self_type(self_type, |this| {
 787                             this.with_self_struct_ctor_rib(item_def_id, |this| {
 788                                 debug!("resolve_implementation with_self_struct_ctor_rib");
 789                                 for impl_item in impl_items {
 790                                     this.r.resolve_visibility(
 791                                         &impl_item.vis, &this.parent_scope
 792                                     );
 793                                     // We also need a new scope for the impl item type parameters.
 794                                     let generic_params = HasGenericParams(&impl_item.generics,
 795                                                                           AssocItemRibKind);
 796                                     this.with_generic_param_rib(generic_params, |this| {
 797                                         use crate::ResolutionError::*;
 798                                         match impl_item.node {
 799                                             ImplItemKind::Const(..) => {
 800                                                 debug!(
 801                                                     "resolve_implementation ImplItemKind::Const",
 802                                                 );
 803                                                 // If this is a trait impl, ensure the const
 804                                                 // exists in trait
 805                                                 this.check_trait_item(
 806                                                     impl_item.ident,
 807                                                     ValueNS,
 808                                                     impl_item.span,
 809                                                     |n, s| ConstNotMemberOfTrait(n, s),
 810                                                 );
 811
 812                                                 this.with_constant_rib(|this| {
 813                                                     visit::walk_impl_item(this, impl_item)
 814                                                 });
 815                                             }
 816                                             ImplItemKind::Method(..) => {
 817                                                 // If this is a trait impl, ensure the method
 818                                                 // exists in trait
 819                                                 this.check_trait_item(impl_item.ident,
 820                                                                       ValueNS,
 821                                                                       impl_item.span,
 822                                                     |n, s| MethodNotMemberOfTrait(n, s));
 823
 824                                                 visit::walk_impl_item(this, impl_item);
 825                                             }
 826                                             ImplItemKind::TyAlias(ref ty) => {
 827                                                 // If this is a trait impl, ensure the type
 828                                                 // exists in trait
 829                                                 this.check_trait_item(impl_item.ident,
 830                                                                       TypeNS,
 831                                                                       impl_item.span,
 832                                                     |n, s| TypeNotMemberOfTrait(n, s));
 833
 834                                                 this.visit_ty(ty);
 835                                             }
 836                                             ImplItemKind::OpaqueTy(ref bounds) => {
 837                                                 // If this is a trait impl, ensure the type
 838                                                 // exists in trait
 839                                                 this.check_trait_item(impl_item.ident,
 840                                                                       TypeNS,
 841                                                                       impl_item.span,
 842                                                     |n, s| TypeNotMemberOfTrait(n, s));
 843
 844                                                 for bound in bounds {
 845                                                     this.visit_param_bound(bound);
 846                                                 }
 847                                             }
 848                                             ImplItemKind::Macro(_) =>
 849                                                 panic!("unexpanded macro in resolve!"),
 850                                         }
 851                                     });
 852                                 }
 853                             });
 854                         });
 855                     });
 856                 });
 857             });
 858         });
 859     }
 860
 861     fn check_trait_item<F>(&mut self, ident: Ident, ns: Namespace, span: Span, err: F)
 862         where F: FnOnce(Name, &str) -> ResolutionError<'_>
 863     {
 864         // If there is a TraitRef in scope for an impl, then the method must be in the
 865         // trait.
 866         if let Some((module, _)) = self.current_trait_ref {
 867             if self.r.resolve_ident_in_module(
 868                 ModuleOrUniformRoot::Module(module),
 869                 ident,
 870                 ns,
 871                 &self.parent_scope,
 872                 false,
 873                 span,
 874             ).is_err() {
 875                 let path = &self.current_trait_ref.as_ref().unwrap().1.path;
 876                 resolve_error(&self.r, span, err(ident.name, &path_names_to_string(path)));
 877             }
 878         }
 879     }
 880
 881     fn resolve_local(&mut self, local: &Local) {
 882         // Resolve the type.
 883         walk_list!(self, visit_ty, &local.ty);
 884
 885         // Resolve the initializer.
 886         walk_list!(self, visit_expr, &local.init);
 887
 888         // Resolve the pattern.
 889         self.resolve_pattern(&local.pat, PatternSource::Let, &mut FxHashMap::default());
 890     }
 891
 892     // build a map from pattern identifiers to binding-info's.
 893     // this is done hygienically. This could arise for a macro
 894     // that expands into an or-pattern where one 'x' was from the
 895     // user and one 'x' came from the macro.
 896     fn binding_mode_map(&mut self, pat: &Pat) -> BindingMap {
 897         let mut binding_map = FxHashMap::default();
 898
 899         pat.walk(&mut |pat| {
 900             if let PatKind::Ident(binding_mode, ident, ref sub_pat) = pat.node {
 901                 if sub_pat.is_some() || match self.r.partial_res_map.get(&pat.id)
 902                                                                   .map(|res| res.base_res()) {
 903                     Some(Res::Local(..)) => true,
 904                     _ => false,
 905                 } {
 906                     let binding_info = BindingInfo { span: ident.span, binding_mode: binding_mode };
 907                     binding_map.insert(ident, binding_info);
 908                 }
 909             }
 910             true
 911         });
 912
 913         binding_map
 914     }
 915
 916     // Checks that all of the arms in an or-pattern have exactly the
 917     // same set of bindings, with the same binding modes for each.
 918     fn check_consistent_bindings(&mut self, pats: &[P<Pat>]) {
 919         if pats.is_empty() {
 920             return;
 921         }
 922
 923         let mut missing_vars = FxHashMap::default();
 924         let mut inconsistent_vars = FxHashMap::default();
 925         for (i, p) in pats.iter().enumerate() {
 926             let map_i = self.binding_mode_map(&p);
 927
 928             for (j, q) in pats.iter().enumerate() {
 929                 if i == j {
 930                     continue;
 931                 }
 932
 933                 let map_j = self.binding_mode_map(&q);
 934                 for (&key, &binding_i) in &map_i {
 935                     if map_j.is_empty() {                   // Account for missing bindings when
 936                         let binding_error = missing_vars    // `map_j` has none.
 937                             .entry(key.name)
 938                             .or_insert(BindingError {
 939                                 name: key.name,
 940                                 origin: BTreeSet::new(),
 941                                 target: BTreeSet::new(),
 942                             });
 943                         binding_error.origin.insert(binding_i.span);
 944                         binding_error.target.insert(q.span);
 945                     }
 946                     for (&key_j, &binding_j) in &map_j {
 947                         match map_i.get(&key_j) {
 948                             None => {  // missing binding
 949                                 let binding_error = missing_vars
 950                                     .entry(key_j.name)
 951                                     .or_insert(BindingError {
 952                                         name: key_j.name,
 953                                         origin: BTreeSet::new(),
 954                                         target: BTreeSet::new(),
 955                                     });
 956                                 binding_error.origin.insert(binding_j.span);
 957                                 binding_error.target.insert(p.span);
 958                             }
 959                             Some(binding_i) => {  // check consistent binding
 960                                 if binding_i.binding_mode != binding_j.binding_mode {
 961                                     inconsistent_vars
 962                                         .entry(key.name)
 963                                         .or_insert((binding_j.span, binding_i.span));
 964                                 }
 965                             }
 966                         }
 967                     }
 968                 }
 969             }
 970         }
 971         let mut missing_vars = missing_vars.iter().collect::<Vec<_>>();
 972         missing_vars.sort();
 973         for (_, v) in missing_vars {
 974             resolve_error(&self.r,
 975                           *v.origin.iter().next().unwrap(),
 976                           ResolutionError::VariableNotBoundInPattern(v));
 977         }
 978         let mut inconsistent_vars = inconsistent_vars.iter().collect::<Vec<_>>();
 979         inconsistent_vars.sort();
 980         for (name, v) in inconsistent_vars {
 981             let err = ResolutionError::VariableBoundWithDifferentMode(*name, v.1);
 982             resolve_error(&self.r, v.0, err);
 983         }
 984     }
 985
 986     fn resolve_arm(&mut self, arm: &Arm) {
 987         self.ribs[ValueNS].push(Rib::new(NormalRibKind));
 988
 989         self.resolve_pats(&arm.pats, PatternSource::Match);
 990
 991         if let Some(ref expr) = arm.guard {
 992             self.visit_expr(expr)
 993         }
 994         self.visit_expr(&arm.body);
 995
 996         self.ribs[ValueNS].pop();
 997     }
 998
 999     /// Arising from `source`, resolve a sequence of patterns (top level or-patterns).
1000     fn resolve_pats(&mut self, pats: &[P<Pat>], source: PatternSource) {
1001         let mut bindings_list = FxHashMap::default();
1002         for pat in pats {
1003             self.resolve_pattern(pat, source, &mut bindings_list);
1004         }
1005         // This has to happen *after* we determine which pat_idents are variants
1006         self.check_consistent_bindings(pats);
1007     }
1008
1009     fn resolve_block(&mut self, block: &Block) {
1010         debug!("(resolving block) entering block");
1011         // Move down in the graph, if there's an anonymous module rooted here.
1012         let orig_module = self.parent_scope.module;
1013         let anonymous_module = self.r.block_map.get(&block.id).cloned(); // clones a reference
1014
1015         let mut num_macro_definition_ribs = 0;
1016         if let Some(anonymous_module) = anonymous_module {
1017             debug!("(resolving block) found anonymous module, moving down");
1018             self.ribs[ValueNS].push(Rib::new(ModuleRibKind(anonymous_module)));
1019             self.ribs[TypeNS].push(Rib::new(ModuleRibKind(anonymous_module)));
1020             self.parent_scope.module = anonymous_module;
1021             self.r.finalize_current_module_macro_resolutions(anonymous_module);
1022         } else {
1023             self.ribs[ValueNS].push(Rib::new(NormalRibKind));
1024         }
1025
1026         // Descend into the block.
1027         for stmt in &block.stmts {
1028             if let StmtKind::Item(ref item) = stmt.node {
1029                 if let ItemKind::MacroDef(..) = item.node {
1030                     num_macro_definition_ribs += 1;
1031                     let res = self.r.definitions.local_def_id(item.id);
1032                     self.ribs[ValueNS].push(Rib::new(MacroDefinition(res)));
1033                     self.label_ribs.push(Rib::new(MacroDefinition(res)));
1034                 }
1035             }
1036
1037             self.visit_stmt(stmt);
1038         }
1039
1040         // Move back up.
1041         self.parent_scope.module = orig_module;
1042         for _ in 0 .. num_macro_definition_ribs {
1043             self.ribs[ValueNS].pop();
1044             self.label_ribs.pop();
1045         }
1046         self.ribs[ValueNS].pop();
1047         if anonymous_module.is_some() {
1048             self.ribs[TypeNS].pop();
1049         }
1050         debug!("(resolving block) leaving block");
1051     }
1052
1053     fn fresh_binding(&mut self,
1054                      ident: Ident,
1055                      pat_id: NodeId,
1056                      outer_pat_id: NodeId,
1057                      pat_src: PatternSource,
1058                      bindings: &mut FxHashMap<Ident, NodeId>)
1059                      -> Res {
1060         // Add the binding to the local ribs, if it
1061         // doesn't already exist in the bindings map. (We
1062         // must not add it if it's in the bindings map
1063         // because that breaks the assumptions later
1064         // passes make about or-patterns.)
1065         let ident = ident.modern_and_legacy();
1066         let mut res = Res::Local(pat_id);
1067         match bindings.get(&ident).cloned() {
1068             Some(id) if id == outer_pat_id => {
1069                 // `Variant(a, a)`, error
1070                 resolve_error(
1071                     &self.r,
1072                     ident.span,
1073                     ResolutionError::IdentifierBoundMoreThanOnceInSamePattern(
1074                         &ident.as_str())
1075                 );
1076             }
1077             Some(..) if pat_src == PatternSource::FnParam => {
1078                 // `fn f(a: u8, a: u8)`, error
1079                 resolve_error(
1080                     &self.r,
1081                     ident.span,
1082                     ResolutionError::IdentifierBoundMoreThanOnceInParameterList(
1083                         &ident.as_str())
1084                 );
1085             }
1086             Some(..) if pat_src == PatternSource::Match ||
1087                         pat_src == PatternSource::Let => {
1088                 // `Variant1(a) | Variant2(a)`, ok
1089                 // Reuse definition from the first `a`.
1090                 res = self.ribs[ValueNS].last_mut().unwrap().bindings[&ident];
1091             }
1092             Some(..) => {
1093                 span_bug!(ident.span, "two bindings with the same name from \
1094                                        unexpected pattern source {:?}", pat_src);
1095             }
1096             None => {
1097                 // A completely fresh binding, add to the lists if it's valid.
1098                 if ident.name != kw::Invalid {
1099                     bindings.insert(ident, outer_pat_id);
1100                     self.ribs[ValueNS].last_mut().unwrap().bindings.insert(ident, res);
1101                 }
1102             }
1103         }
1104
1105         res
1106     }
1107
1108     fn resolve_pattern(&mut self,
1109                        pat: &Pat,
1110                        pat_src: PatternSource,
1111                        // Maps idents to the node ID for the
1112                        // outermost pattern that binds them.
1113                        bindings: &mut FxHashMap<Ident, NodeId>) {
1114         // Visit all direct subpatterns of this pattern.
1115         let outer_pat_id = pat.id;
1116         pat.walk(&mut |pat| {
1117             debug!("resolve_pattern pat={:?} node={:?}", pat, pat.node);
1118             match pat.node {
1119                 PatKind::Ident(bmode, ident, ref opt_pat) => {
1120                     // First try to resolve the identifier as some existing
1121                     // entity, then fall back to a fresh binding.
1122                     let binding = self.resolve_ident_in_lexical_scope(ident, ValueNS,
1123                                                                       None, pat.span)
1124                                       .and_then(LexicalScopeBinding::item);
1125                     let res = binding.map(NameBinding::res).and_then(|res| {
1126                         let is_syntactic_ambiguity = opt_pat.is_none() &&
1127                             bmode == BindingMode::ByValue(Mutability::Immutable);
1128                         match res {
1129                             Res::Def(DefKind::Ctor(_, CtorKind::Const), _) |
1130                             Res::Def(DefKind::Const, _) if is_syntactic_ambiguity => {
1131                                 // Disambiguate in favor of a unit struct/variant
1132                                 // or constant pattern.
1133                                 self.r.record_use(ident, ValueNS, binding.unwrap(), false);
1134                                 Some(res)
1135                             }
1136                             Res::Def(DefKind::Ctor(..), _)
1137                             | Res::Def(DefKind::Const, _)
1138                             | Res::Def(DefKind::Static, _) => {
1139                                 // This is unambiguously a fresh binding, either syntactically
1140                                 // (e.g., `IDENT @ PAT` or `ref IDENT`) or because `IDENT` resolves
1141                                 // to something unusable as a pattern (e.g., constructor function),
1142                                 // but we still conservatively report an error, see
1143                                 // issues/33118#issuecomment-233962221 for one reason why.
1144                                 resolve_error(
1145                                     &self.r,
1146                                     ident.span,
1147                                     ResolutionError::BindingShadowsSomethingUnacceptable(
1148                                         pat_src.descr(), ident.name, binding.unwrap())
1149                                 );
1150                                 None
1151                             }
1152                             Res::Def(DefKind::Fn, _) | Res::Err => {
1153                                 // These entities are explicitly allowed
1154                                 // to be shadowed by fresh bindings.
1155                                 None
1156                             }
1157                             res => {
1158                                 span_bug!(ident.span, "unexpected resolution for an \
1159                                                        identifier in pattern: {:?}", res);
1160                             }
1161                         }
1162                     }).unwrap_or_else(|| {
1163                         self.fresh_binding(ident, pat.id, outer_pat_id, pat_src, bindings)
1164                     });
1165
1166                     self.r.record_partial_res(pat.id, PartialRes::new(res));
1167                 }
1168
1169                 PatKind::TupleStruct(ref path, ..) => {
1170                     self.smart_resolve_path(pat.id, None, path, PathSource::TupleStruct);
1171                 }
1172
1173                 PatKind::Path(ref qself, ref path) => {
1174                     self.smart_resolve_path(pat.id, qself.as_ref(), path, PathSource::Pat);
1175                 }
1176
1177                 PatKind::Struct(ref path, ..) => {
1178                     self.smart_resolve_path(pat.id, None, path, PathSource::Struct);
1179                 }
1180
1181                 _ => {}
1182             }
1183             true
1184         });
1185
1186         visit::walk_pat(self, pat);
1187     }
1188
1189     // High-level and context dependent path resolution routine.
1190     // Resolves the path and records the resolution into definition map.
1191     // If resolution fails tries several techniques to find likely
1192     // resolution candidates, suggest imports or other help, and report
1193     // errors in user friendly way.
1194     fn smart_resolve_path(&mut self,
1195                           id: NodeId,
1196                           qself: Option<&QSelf>,
1197                           path: &Path,
1198                           source: PathSource<'_>) {
1199         self.smart_resolve_path_fragment(
1200             id,
1201             qself,
1202             &Segment::from_path(path),
1203             path.span,
1204             source,
1205             CrateLint::SimplePath(id),
1206         );
1207     }
1208
1209     fn smart_resolve_path_fragment(&mut self,
1210                                    id: NodeId,
1211                                    qself: Option<&QSelf>,
1212                                    path: &[Segment],
1213                                    span: Span,
1214                                    source: PathSource<'_>,
1215                                    crate_lint: CrateLint)
1216                                    -> PartialRes {
1217         let ns = source.namespace();
1218         let is_expected = &|res| source.is_expected(res);
1219
1220         let report_errors = |this: &mut Self, res: Option<Res>| {
1221             let (err, candidates) = this.smart_resolve_report_errors(path, span, source, res);
1222             let def_id = this.parent_scope.module.normal_ancestor_id;
1223             let node_id = this.r.definitions.as_local_node_id(def_id).unwrap();
1224             let better = res.is_some();
1225             this.r.use_injections.push(UseError { err, candidates, node_id, better });
1226             PartialRes::new(Res::Err)
1227         };
1228
1229         let partial_res = match self.resolve_qpath_anywhere(
1230             id,
1231             qself,
1232             path,
1233             ns,
1234             span,
1235             source.defer_to_typeck(),
1236             crate_lint,
1237         ) {
1238             Some(partial_res) if partial_res.unresolved_segments() == 0 => {
1239                 if is_expected(partial_res.base_res()) || partial_res.base_res() == Res::Err {
1240                     partial_res
1241                 } else {
1242                     // Add a temporary hack to smooth the transition to new struct ctor
1243                     // visibility rules. See #38932 for more details.
1244                     let mut res = None;
1245                     if let Res::Def(DefKind::Struct, def_id) = partial_res.base_res() {
1246                         if let Some((ctor_res, ctor_vis))
1247                                 = self.r.struct_constructors.get(&def_id).cloned() {
1248                             if is_expected(ctor_res) &&
1249                                self.r.is_accessible_from(ctor_vis, self.parent_scope.module) {
1250                                 let lint = lint::builtin::LEGACY_CONSTRUCTOR_VISIBILITY;
1251                                 self.r.session.buffer_lint(lint, id, span,
1252                                     "private struct constructors are not usable through \
1253                                      re-exports in outer modules",
1254                                 );
1255                                 res = Some(PartialRes::new(ctor_res));
1256                             }
1257                         }
1258                     }
1259
1260                     res.unwrap_or_else(|| report_errors(self, Some(partial_res.base_res())))
1261                 }
1262             }
1263             Some(partial_res) if source.defer_to_typeck() => {
1264                 // Not fully resolved associated item `T::A::B` or `<T as Tr>::A::B`
1265                 // or `<T>::A::B`. If `B` should be resolved in value namespace then
1266                 // it needs to be added to the trait map.
1267                 if ns == ValueNS {
1268                     let item_name = path.last().unwrap().ident;
1269                     let traits = self.get_traits_containing_item(item_name, ns);
1270                     self.r.trait_map.insert(id, traits);
1271                 }
1272
1273                 let mut std_path = vec![Segment::from_ident(Ident::with_empty_ctxt(sym::std))];
1274                 std_path.extend(path);
1275                 if self.r.primitive_type_table.primitive_types.contains_key(&path[0].ident.name) {
1276                     let cl = CrateLint::No;
1277                     let ns = Some(ns);
1278                     if let PathResult::Module(_) | PathResult::NonModule(_) =
1279                             self.resolve_path(&std_path, ns, false, span, cl) {
1280                         // check if we wrote `str::from_utf8` instead of `std::str::from_utf8`
1281                         let item_span = path.iter().last().map(|segment| segment.ident.span)
1282                             .unwrap_or(span);
1283                         debug!("accessed item from `std` submodule as a bare type {:?}", std_path);
1284                         let mut hm = self.r.session.confused_type_with_std_module.borrow_mut();
1285                         hm.insert(item_span, span);
1286                         // In some places (E0223) we only have access to the full path
1287                         hm.insert(span, span);
1288                     }
1289                 }
1290                 partial_res
1291             }
1292             _ => report_errors(self, None)
1293         };
1294
1295         if let PathSource::TraitItem(..) = source {} else {
1296             // Avoid recording definition of `A::B` in `<T as A>::B::C`.
1297             self.r.record_partial_res(id, partial_res);
1298         }
1299         partial_res
1300     }
1301
1302     fn self_type_is_available(&mut self, span: Span) -> bool {
1303         let binding = self.resolve_ident_in_lexical_scope(
1304             Ident::with_empty_ctxt(kw::SelfUpper),
1305             TypeNS,
1306             None,
1307             span,
1308         );
1309         if let Some(LexicalScopeBinding::Res(res)) = binding { res != Res::Err } else { false }
1310     }
1311
1312     fn self_value_is_available(&mut self, self_span: Span, path_span: Span) -> bool {
1313         let ident = Ident::new(kw::SelfLower, self_span);
1314         let binding = self.resolve_ident_in_lexical_scope(ident, ValueNS, None, path_span);
1315         if let Some(LexicalScopeBinding::Res(res)) = binding { res != Res::Err } else { false }
1316     }
1317
1318     // Resolve in alternative namespaces if resolution in the primary namespace fails.
1319     fn resolve_qpath_anywhere(
1320         &mut self,
1321         id: NodeId,
1322         qself: Option<&QSelf>,
1323         path: &[Segment],
1324         primary_ns: Namespace,
1325         span: Span,
1326         defer_to_typeck: bool,
1327         crate_lint: CrateLint,
1328     ) -> Option<PartialRes> {
1329         let mut fin_res = None;
1330         for (i, ns) in [primary_ns, TypeNS, ValueNS].iter().cloned().enumerate() {
1331             if i == 0 || ns != primary_ns {
1332                 match self.resolve_qpath(id, qself, path, ns, span, crate_lint) {
1333                     // If defer_to_typeck, then resolution > no resolution,
1334                     // otherwise full resolution > partial resolution > no resolution.
1335                     Some(partial_res) if partial_res.unresolved_segments() == 0 ||
1336                                          defer_to_typeck =>
1337                         return Some(partial_res),
1338                     partial_res => if fin_res.is_none() { fin_res = partial_res },
1339                 }
1340             }
1341         }
1342
1343         // `MacroNS`
1344         assert!(primary_ns != MacroNS);
1345         if qself.is_none() {
1346             let path_seg = |seg: &Segment| PathSegment::from_ident(seg.ident);
1347             let path = Path { segments: path.iter().map(path_seg).collect(), span };
1348             if let Ok((_, res)) = self.r.resolve_macro_path(
1349                 &path, None, &self.parent_scope, false, false
1350             ) {
1351                 return Some(PartialRes::new(res));
1352             }
1353         }
1354
1355         fin_res
1356     }
1357
1358     /// Handles paths that may refer to associated items.
1359     fn resolve_qpath(
1360         &mut self,
1361         id: NodeId,
1362         qself: Option<&QSelf>,
1363         path: &[Segment],
1364         ns: Namespace,
1365         span: Span,
1366         crate_lint: CrateLint,
1367     ) -> Option<PartialRes> {
1368         debug!(
1369             "resolve_qpath(id={:?}, qself={:?}, path={:?}, ns={:?}, span={:?})",
1370             id,
1371             qself,
1372             path,
1373             ns,
1374             span,
1375         );
1376
1377         if let Some(qself) = qself {
1378             if qself.position == 0 {
1379                 // This is a case like `<T>::B`, where there is no
1380                 // trait to resolve.  In that case, we leave the `B`
1381                 // segment to be resolved by type-check.
1382                 return Some(PartialRes::with_unresolved_segments(
1383                     Res::Def(DefKind::Mod, DefId::local(CRATE_DEF_INDEX)), path.len()
1384                 ));
1385             }
1386
1387             // Make sure `A::B` in `<T as A::B>::C` is a trait item.
1388             //
1389             // Currently, `path` names the full item (`A::B::C`, in
1390             // our example).  so we extract the prefix of that that is
1391             // the trait (the slice upto and including
1392             // `qself.position`). And then we recursively resolve that,
1393             // but with `qself` set to `None`.
1394             //
1395             // However, setting `qself` to none (but not changing the
1396             // span) loses the information about where this path
1397             // *actually* appears, so for the purposes of the crate
1398             // lint we pass along information that this is the trait
1399             // name from a fully qualified path, and this also
1400             // contains the full span (the `CrateLint::QPathTrait`).
1401             let ns = if qself.position + 1 == path.len() { ns } else { TypeNS };
1402             let partial_res = self.smart_resolve_path_fragment(
1403                 id,
1404                 None,
1405                 &path[..=qself.position],
1406                 span,
1407                 PathSource::TraitItem(ns),
1408                 CrateLint::QPathTrait {
1409                     qpath_id: id,
1410                     qpath_span: qself.path_span,
1411                 },
1412             );
1413
1414             // The remaining segments (the `C` in our example) will
1415             // have to be resolved by type-check, since that requires doing
1416             // trait resolution.
1417             return Some(PartialRes::with_unresolved_segments(
1418                 partial_res.base_res(),
1419                 partial_res.unresolved_segments() + path.len() - qself.position - 1,
1420             ));
1421         }
1422
1423         let result = match self.resolve_path(&path, Some(ns), true, span, crate_lint) {
1424             PathResult::NonModule(path_res) => path_res,
1425             PathResult::Module(ModuleOrUniformRoot::Module(module)) if !module.is_normal() => {
1426                 PartialRes::new(module.res().unwrap())
1427             }
1428             // In `a(::assoc_item)*` `a` cannot be a module. If `a` does resolve to a module we
1429             // don't report an error right away, but try to fallback to a primitive type.
1430             // So, we are still able to successfully resolve something like
1431             //
1432             // use std::u8; // bring module u8 in scope
1433             // fn f() -> u8 { // OK, resolves to primitive u8, not to std::u8
1434             //     u8::max_value() // OK, resolves to associated function <u8>::max_value,
1435             //                     // not to non-existent std::u8::max_value
1436             // }
1437             //
1438             // Such behavior is required for backward compatibility.
1439             // The same fallback is used when `a` resolves to nothing.
1440             PathResult::Module(ModuleOrUniformRoot::Module(_)) |
1441             PathResult::Failed { .. }
1442                     if (ns == TypeNS || path.len() > 1) &&
1443                        self.r.primitive_type_table.primitive_types
1444                            .contains_key(&path[0].ident.name) => {
1445                 let prim = self.r.primitive_type_table.primitive_types[&path[0].ident.name];
1446                 PartialRes::with_unresolved_segments(Res::PrimTy(prim), path.len() - 1)
1447             }
1448             PathResult::Module(ModuleOrUniformRoot::Module(module)) =>
1449                 PartialRes::new(module.res().unwrap()),
1450             PathResult::Failed { is_error_from_last_segment: false, span, label, suggestion } => {
1451                 let err = ResolutionError::FailedToResolve { label, suggestion };
1452                 resolve_error(&self.r, span, err);
1453                 PartialRes::new(Res::Err)
1454             }
1455             PathResult::Module(..) | PathResult::Failed { .. } => return None,
1456             PathResult::Indeterminate => bug!("indetermined path result in resolve_qpath"),
1457         };
1458
1459         if path.len() > 1 && result.base_res() != Res::Err &&
1460            path[0].ident.name != kw::PathRoot &&
1461            path[0].ident.name != kw::DollarCrate {
1462             let unqualified_result = {
1463                 match self.resolve_path(
1464                     &[*path.last().unwrap()],
1465                     Some(ns),
1466                     false,
1467                     span,
1468                     CrateLint::No,
1469                 ) {
1470                     PathResult::NonModule(path_res) => path_res.base_res(),
1471                     PathResult::Module(ModuleOrUniformRoot::Module(module)) =>
1472                         module.res().unwrap(),
1473                     _ => return Some(result),
1474                 }
1475             };
1476             if result.base_res() == unqualified_result {
1477                 let lint = lint::builtin::UNUSED_QUALIFICATIONS;
1478                 self.r.session.buffer_lint(lint, id, span, "unnecessary qualification")
1479             }
1480         }
1481
1482         Some(result)
1483     }
1484
1485     fn with_resolved_label<F>(&mut self, label: Option<Label>, id: NodeId, f: F)
1486         where F: FnOnce(&mut LateResolutionVisitor<'_, '_>)
1487     {
1488         if let Some(label) = label {
1489             self.unused_labels.insert(id, label.ident.span);
1490             self.with_label_rib(|this| {
1491                 let ident = label.ident.modern_and_legacy();
1492                 this.label_ribs.last_mut().unwrap().bindings.insert(ident, id);
1493                 f(this);
1494             });
1495         } else {
1496             f(self);
1497         }
1498     }
1499
1500     fn resolve_labeled_block(&mut self, label: Option<Label>, id: NodeId, block: &Block) {
1501         self.with_resolved_label(label, id, |this| this.visit_block(block));
1502     }
1503
1504     fn resolve_expr(&mut self, expr: &Expr, parent: Option<&Expr>) {
1505         // First, record candidate traits for this expression if it could
1506         // result in the invocation of a method call.
1507
1508         self.record_candidate_traits_for_expr_if_necessary(expr);
1509
1510         // Next, resolve the node.
1511         match expr.node {
1512             ExprKind::Path(ref qself, ref path) => {
1513                 self.smart_resolve_path(expr.id, qself.as_ref(), path, PathSource::Expr(parent));
1514                 visit::walk_expr(self, expr);
1515             }
1516
1517             ExprKind::Struct(ref path, ..) => {
1518                 self.smart_resolve_path(expr.id, None, path, PathSource::Struct);
1519                 visit::walk_expr(self, expr);
1520             }
1521
1522             ExprKind::Break(Some(label), _) | ExprKind::Continue(Some(label)) => {
1523                 let node_id = self.search_label(label.ident, |rib, ident| {
1524                     rib.bindings.get(&ident.modern_and_legacy()).cloned()
1525                 });
1526                 match node_id {
1527                     None => {
1528                         // Search again for close matches...
1529                         // Picks the first label that is "close enough", which is not necessarily
1530                         // the closest match
1531                         let close_match = self.search_label(label.ident, |rib, ident| {
1532                             let names = rib.bindings.iter().filter_map(|(id, _)| {
1533                                 if id.span.ctxt() == label.ident.span.ctxt() {
1534                                     Some(&id.name)
1535                                 } else {
1536                                     None
1537                                 }
1538                             });
1539                             find_best_match_for_name(names, &*ident.as_str(), None)
1540                         });
1541                         self.r.record_partial_res(expr.id, PartialRes::new(Res::Err));
1542                         resolve_error(&self.r,
1543                                       label.ident.span,
1544                                       ResolutionError::UndeclaredLabel(&label.ident.as_str(),
1545                                                                        close_match));
1546                     }
1547                     Some(node_id) => {
1548                         // Since this res is a label, it is never read.
1549                         self.r.label_res_map.insert(expr.id, node_id);
1550                         self.unused_labels.remove(&node_id);
1551                     }
1552                 }
1553
1554                 // visit `break` argument if any
1555                 visit::walk_expr(self, expr);
1556             }
1557
1558             ExprKind::Let(ref pats, ref scrutinee) => {
1559                 self.visit_expr(scrutinee);
1560                 self.resolve_pats(pats, PatternSource::Let);
1561             }
1562
1563             ExprKind::If(ref cond, ref then, ref opt_else) => {
1564                 self.ribs[ValueNS].push(Rib::new(NormalRibKind));
1565                 self.visit_expr(cond);
1566                 self.visit_block(then);
1567                 self.ribs[ValueNS].pop();
1568
1569                 opt_else.as_ref().map(|expr| self.visit_expr(expr));
1570             }
1571
1572             ExprKind::Loop(ref block, label) => self.resolve_labeled_block(label, expr.id, &block),
1573
1574             ExprKind::While(ref subexpression, ref block, label) => {
1575                 self.with_resolved_label(label, expr.id, |this| {
1576                     this.ribs[ValueNS].push(Rib::new(NormalRibKind));
1577                     this.visit_expr(subexpression);
1578                     this.visit_block(block);
1579                     this.ribs[ValueNS].pop();
1580                 });
1581             }
1582
1583             ExprKind::ForLoop(ref pattern, ref subexpression, ref block, label) => {
1584                 self.visit_expr(subexpression);
1585                 self.ribs[ValueNS].push(Rib::new(NormalRibKind));
1586                 self.resolve_pattern(pattern, PatternSource::For, &mut FxHashMap::default());
1587
1588                 self.resolve_labeled_block(label, expr.id, block);
1589
1590                 self.ribs[ValueNS].pop();
1591             }
1592
1593             ExprKind::Block(ref block, label) => self.resolve_labeled_block(label, block.id, block),
1594
1595             // Equivalent to `visit::walk_expr` + passing some context to children.
1596             ExprKind::Field(ref subexpression, _) => {
1597                 self.resolve_expr(subexpression, Some(expr));
1598             }
1599             ExprKind::MethodCall(ref segment, ref arguments) => {
1600                 let mut arguments = arguments.iter();
1601                 self.resolve_expr(arguments.next().unwrap(), Some(expr));
1602                 for argument in arguments {
1603                     self.resolve_expr(argument, None);
1604                 }
1605                 self.visit_path_segment(expr.span, segment);
1606             }
1607
1608             ExprKind::Call(ref callee, ref arguments) => {
1609                 self.resolve_expr(callee, Some(expr));
1610                 for argument in arguments {
1611                     self.resolve_expr(argument, None);
1612                 }
1613             }
1614             ExprKind::Type(ref type_expr, _) => {
1615                 self.current_type_ascription.push(type_expr.span);
1616                 visit::walk_expr(self, expr);
1617                 self.current_type_ascription.pop();
1618             }
1619             // `async |x| ...` gets desugared to `|x| future_from_generator(|| ...)`, so we need to
1620             // resolve the arguments within the proper scopes so that usages of them inside the
1621             // closure are detected as upvars rather than normal closure arg usages.
1622             ExprKind::Closure(
1623                 _, IsAsync::Async { .. }, _,
1624                 ref fn_decl, ref body, _span,
1625             ) => {
1626                 let rib_kind = NormalRibKind;
1627                 self.ribs[ValueNS].push(Rib::new(rib_kind));
1628                 // Resolve arguments:
1629                 let mut bindings_list = FxHashMap::default();
1630                 for argument in &fn_decl.inputs {
1631                     self.resolve_pattern(&argument.pat, PatternSource::FnParam, &mut bindings_list);
1632                     self.visit_ty(&argument.ty);
1633                 }
1634                 // No need to resolve return type-- the outer closure return type is
1635                 // FunctionRetTy::Default
1636
1637                 // Now resolve the inner closure
1638                 {
1639                     // No need to resolve arguments: the inner closure has none.
1640                     // Resolve the return type:
1641                     visit::walk_fn_ret_ty(self, &fn_decl.output);
1642                     // Resolve the body
1643                     self.visit_expr(body);
1644                 }
1645                 self.ribs[ValueNS].pop();
1646             }
1647             _ => {
1648                 visit::walk_expr(self, expr);
1649             }
1650         }
1651     }
1652
1653     fn record_candidate_traits_for_expr_if_necessary(&mut self, expr: &Expr) {
1654         match expr.node {
1655             ExprKind::Field(_, ident) => {
1656                 // FIXME(#6890): Even though you can't treat a method like a
1657                 // field, we need to add any trait methods we find that match
1658                 // the field name so that we can do some nice error reporting
1659                 // later on in typeck.
1660                 let traits = self.get_traits_containing_item(ident, ValueNS);
1661                 self.r.trait_map.insert(expr.id, traits);
1662             }
1663             ExprKind::MethodCall(ref segment, ..) => {
1664                 debug!("(recording candidate traits for expr) recording traits for {}",
1665                        expr.id);
1666                 let traits = self.get_traits_containing_item(segment.ident, ValueNS);
1667                 self.r.trait_map.insert(expr.id, traits);
1668             }
1669             _ => {
1670                 // Nothing to do.
1671             }
1672         }
1673     }
1674
1675     fn get_traits_containing_item(&mut self, mut ident: Ident, ns: Namespace)
1676                                   -> Vec<TraitCandidate> {
1677         debug!("(getting traits containing item) looking for '{}'", ident.name);
1678
1679         let mut found_traits = Vec::new();
1680         // Look for the current trait.
1681         if let Some((module, _)) = self.current_trait_ref {
1682             if self.r.resolve_ident_in_module(
1683                 ModuleOrUniformRoot::Module(module),
1684                 ident,
1685                 ns,
1686                 &self.parent_scope,
1687                 false,
1688                 module.span,
1689             ).is_ok() {
1690                 let def_id = module.def_id().unwrap();
1691                 found_traits.push(TraitCandidate { def_id: def_id, import_ids: smallvec![] });
1692             }
1693         }
1694
1695         ident.span = ident.span.modern();
1696         let mut search_module = self.parent_scope.module;
1697         loop {
1698             self.get_traits_in_module_containing_item(ident, ns, search_module, &mut found_traits);
1699             search_module = unwrap_or!(
1700                 self.r.hygienic_lexical_parent(search_module, &mut ident.span), break
1701             );
1702         }
1703
1704         if let Some(prelude) = self.r.prelude {
1705             if !search_module.no_implicit_prelude {
1706                 self.get_traits_in_module_containing_item(ident, ns, prelude, &mut found_traits);
1707             }
1708         }
1709
1710         found_traits
1711     }
1712
1713     fn get_traits_in_module_containing_item(&mut self,
1714                                             ident: Ident,
1715                                             ns: Namespace,
1716                                             module: Module<'a>,
1717                                             found_traits: &mut Vec<TraitCandidate>) {
1718         assert!(ns == TypeNS || ns == ValueNS);
1719         let mut traits = module.traits.borrow_mut();
1720         if traits.is_none() {
1721             let mut collected_traits = Vec::new();
1722             module.for_each_child(|name, ns, binding| {
1723                 if ns != TypeNS { return }
1724                 match binding.res() {
1725                     Res::Def(DefKind::Trait, _) |
1726                     Res::Def(DefKind::TraitAlias, _) => collected_traits.push((name, binding)),
1727                     _ => (),
1728                 }
1729             });
1730             *traits = Some(collected_traits.into_boxed_slice());
1731         }
1732
1733         for &(trait_name, binding) in traits.as_ref().unwrap().iter() {
1734             // Traits have pseudo-modules that can be used to search for the given ident.
1735             if let Some(module) = binding.module() {
1736                 let mut ident = ident;
1737                 if ident.span.glob_adjust(
1738                     module.expansion,
1739                     binding.span,
1740                 ).is_none() {
1741                     continue
1742                 }
1743                 if self.r.resolve_ident_in_module_unadjusted(
1744                     ModuleOrUniformRoot::Module(module),
1745                     ident,
1746                     ns,
1747                     &self.parent_scope,
1748                     false,
1749                     module.span,
1750                 ).is_ok() {
1751                     let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
1752                     let trait_def_id = module.def_id().unwrap();
1753                     found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
1754                 }
1755             } else if let Res::Def(DefKind::TraitAlias, _) = binding.res() {
1756                 // For now, just treat all trait aliases as possible candidates, since we don't
1757                 // know if the ident is somewhere in the transitive bounds.
1758                 let import_ids = self.find_transitive_imports(&binding.kind, trait_name);
1759                 let trait_def_id = binding.res().def_id();
1760                 found_traits.push(TraitCandidate { def_id: trait_def_id, import_ids });
1761             } else {
1762                 bug!("candidate is not trait or trait alias?")
1763             }
1764         }
1765     }
1766
1767     fn find_transitive_imports(&mut self, mut kind: &NameBindingKind<'_>,
1768                                trait_name: Ident) -> SmallVec<[NodeId; 1]> {
1769         let mut import_ids = smallvec![];
1770         while let NameBindingKind::Import { directive, binding, .. } = kind {
1771             self.r.maybe_unused_trait_imports.insert(directive.id);
1772             self.r.add_to_glob_map(&directive, trait_name);
1773             import_ids.push(directive.id);
1774             kind = &binding.kind;
1775         };
1776         import_ids
1777     }
1778 }
1779
1780 impl<'a> Resolver<'a> {
1781     pub(crate) fn late_resolve_crate(&mut self, krate: &Crate) {
1782         self.finalize_current_module_macro_resolutions(self.graph_root);
1783         let mut late_resolution_visitor = LateResolutionVisitor::new(self);
1784         visit::walk_crate(&mut late_resolution_visitor, krate);
1785         for (id, span) in late_resolution_visitor.unused_labels.iter() {
1786             self.session.buffer_lint(lint::builtin::UNUSED_LABELS, *id, *span, "unused label");
1787         }
1788     }
1789 }