src/librustc_resolve/build_reduced_graph.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Reduced graph building
  12 //!
  13 //! Here we build the "reduced graph": the graph of the module tree without
  14 //! any imports resolved.
  15
  16 use macros::{InvocationData, ParentScope, LegacyScope};
  17 use resolve_imports::ImportDirective;
  18 use resolve_imports::ImportDirectiveSubclass::{self, GlobImport, SingleImport};
  19 use {Module, ModuleData, ModuleKind, NameBinding, NameBindingKind, Segment, ToNameBinding};
  20 use {ModuleOrUniformRoot, PerNS, Resolver, ResolverArenas, ExternPreludeEntry};
  21 use Namespace::{self, TypeNS, ValueNS, MacroNS};
  22 use {resolve_error, resolve_struct_error, ResolutionError};
  23
  24 use rustc::hir::def::*;
  25 use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX, LOCAL_CRATE, DefId};
  26 use rustc::ty;
  27 use rustc::middle::cstore::CrateStore;
  28 use rustc_metadata::cstore::LoadedMacro;
  29
  30 use std::cell::Cell;
  31 use std::ptr;
  32 use rustc_data_structures::sync::Lrc;
  33
  34 use syntax::ast::{Name, Ident};
  35 use syntax::attr;
  36
  37 use syntax::ast::{self, Block, ForeignItem, ForeignItemKind, Item, ItemKind, NodeId};
  38 use syntax::ast::{MetaItemKind, Mutability, StmtKind, TraitItem, TraitItemKind, Variant};
  39 use syntax::ext::base::{MacroKind, SyntaxExtension};
  40 use syntax::ext::base::Determinacy::Undetermined;
  41 use syntax::ext::hygiene::Mark;
  42 use syntax::ext::tt::macro_rules;
  43 use syntax::feature_gate::is_builtin_attr;
  44 use syntax::parse::token::{self, Token};
  45 use syntax::std_inject::injected_crate_name;
  46 use syntax::symbol::keywords;
  47 use syntax::visit::{self, Visitor};
  48
  49 use syntax_pos::{Span, DUMMY_SP};
  50
  51 impl<'a> ToNameBinding<'a> for (Module<'a>, ty::Visibility, Span, Mark) {
  52     fn to_name_binding(self, arenas: &'a ResolverArenas<'a>) -> &'a NameBinding<'a> {
  53         arenas.alloc_name_binding(NameBinding {
  54             kind: NameBindingKind::Module(self.0),
  55             vis: self.1,
  56             span: self.2,
  57             expansion: self.3,
  58         })
  59     }
  60 }
  61
  62 impl<'a> ToNameBinding<'a> for (Def, ty::Visibility, Span, Mark) {
  63     fn to_name_binding(self, arenas: &'a ResolverArenas<'a>) -> &'a NameBinding<'a> {
  64         arenas.alloc_name_binding(NameBinding {
  65             kind: NameBindingKind::Def(self.0, false),
  66             vis: self.1,
  67             span: self.2,
  68             expansion: self.3,
  69         })
  70     }
  71 }
  72
  73 pub(crate) struct IsMacroExport;
  74
  75 impl<'a> ToNameBinding<'a> for (Def, ty::Visibility, Span, Mark, IsMacroExport) {
  76     fn to_name_binding(self, arenas: &'a ResolverArenas<'a>) -> &'a NameBinding<'a> {
  77         arenas.alloc_name_binding(NameBinding {
  78             kind: NameBindingKind::Def(self.0, true),
  79             vis: self.1,
  80             span: self.2,
  81             expansion: self.3,
  82         })
  83     }
  84 }
  85
  86 impl<'a, 'cl> Resolver<'a, 'cl> {
  87     /// Defines `name` in namespace `ns` of module `parent` to be `def` if it is not yet defined;
  88     /// otherwise, reports an error.
  89     pub fn define<T>(&mut self, parent: Module<'a>, ident: Ident, ns: Namespace, def: T)
  90         where T: ToNameBinding<'a>,
  91     {
  92         let binding = def.to_name_binding(self.arenas);
  93         if let Err(old_binding) = self.try_define(parent, ident, ns, binding) {
  94             self.report_conflict(parent, ident, ns, old_binding, &binding);
  95         }
  96     }
  97
  98     fn block_needs_anonymous_module(&mut self, block: &Block) -> bool {
  99         // If any statements are items, we need to create an anonymous module
 100         block.stmts.iter().any(|statement| match statement.node {
 101             StmtKind::Item(_) | StmtKind::Mac(_) => true,
 102             _ => false,
 103         })
 104     }
 105
 106     fn insert_field_names(&mut self, def_id: DefId, field_names: Vec<Name>) {
 107         if !field_names.is_empty() {
 108             self.field_names.insert(def_id, field_names);
 109         }
 110     }
 111
 112     fn build_reduced_graph_for_use_tree(
 113         &mut self,
 114         // This particular use tree
 115         use_tree: &ast::UseTree,
 116         id: NodeId,
 117         parent_prefix: &[Segment],
 118         nested: bool,
 119         mut uniform_paths_canary_emitted: bool,
 120         // The whole `use` item
 121         parent_scope: ParentScope<'a>,
 122         item: &Item,
 123         vis: ty::Visibility,
 124         root_span: Span,
 125     ) {
 126         debug!("build_reduced_graph_for_use_tree(parent_prefix={:?}, \
 127                 uniform_paths_canary_emitted={}, \
 128                 use_tree={:?}, nested={})",
 129                parent_prefix, uniform_paths_canary_emitted, use_tree, nested);
 130
 131         let uniform_paths =
 132             self.session.rust_2018() &&
 133             self.session.features_untracked().uniform_paths;
 134
 135         let prefix_iter = || parent_prefix.iter().cloned()
 136             .chain(use_tree.prefix.segments.iter().map(|seg| seg.into()));
 137         let prefix_start = prefix_iter().next();
 138         let starts_with_non_keyword = prefix_start.map_or(false, |seg| {
 139             !seg.ident.is_path_segment_keyword()
 140         });
 141
 142         // Imports are resolved as global by default, prepend `CrateRoot`,
 143         // unless `#![feature(uniform_paths)]` is enabled.
 144         let inject_crate_root =
 145             !uniform_paths &&
 146             match use_tree.kind {
 147                 // HACK(eddyb) special-case `use *` to mean `use ::*`.
 148                 ast::UseTreeKind::Glob if prefix_start.is_none() => true,
 149                 _ => starts_with_non_keyword,
 150             };
 151         let root = if inject_crate_root {
 152             let span = use_tree.prefix.span.shrink_to_lo();
 153             Some(Segment::from_ident(Ident::new(keywords::CrateRoot.name(), span)))
 154         } else {
 155             None
 156         };
 157
 158         let prefix: Vec<_> = root.into_iter().chain(prefix_iter()).collect();
 159
 160         debug!("build_reduced_graph_for_use_tree: prefix={:?}", prefix);
 161
 162         // `#[feature(uniform_paths)]` allows an unqualified import path,
 163         // e.g. `use x::...;` to resolve not just globally (`use ::x::...;`)
 164         // but also relatively (`use self::x::...;`). To catch ambiguities
 165         // that might arise from both of these being available and resolution
 166         // silently picking one of them, an artificial `use self::x as _;`
 167         // import is injected as a "canary", and an error is emitted if it
 168         // successfully resolves while an `x` external crate exists.
 169         //
 170         // For each block scope around the `use` item, one special canary
 171         // import of the form `use x as _;` is also injected, having its
 172         // parent set to that scope; `resolve_imports` will only resolve
 173         // it within its appropriate scope; if any of them successfully
 174         // resolve, an ambiguity error is emitted, since the original
 175         // import can't see the item in the block scope (`self::x` only
 176         // looks in the enclosing module), but a non-`use` path could.
 177         //
 178         // Additionally, the canary might be able to catch limitations of the
 179         // current implementation, where `::x` may be chosen due to `self::x`
 180         // not existing, but `self::x` could appear later, from macro expansion.
 181         //
 182         // NB. The canary currently only errors if the `x::...` path *could*
 183         // resolve as a relative path through the extern crate, i.e. `x` is
 184         // in `extern_prelude`, *even though* `::x` might still forcefully
 185         // load a non-`extern_prelude` crate.
 186         // While always producing an ambiguity errors if `self::x` exists and
 187         // a crate *could* be loaded, would be more conservative, imports for
 188         // local modules named `test` (or less commonly, `syntax` or `log`),
 189         // would need to be qualified (e.g. `self::test`), which is considered
 190         // ergonomically unacceptable.
 191         let emit_uniform_paths_canary =
 192             !uniform_paths_canary_emitted &&
 193             self.session.rust_2018() &&
 194             starts_with_non_keyword;
 195         if emit_uniform_paths_canary {
 196             let source = prefix_start.unwrap();
 197
 198             // Helper closure to emit a canary with the given base path.
 199             let emit = |this: &mut Self, base: Option<Segment>| {
 200                 let subclass = SingleImport {
 201                     target: Ident {
 202                         name: keywords::Underscore.name().gensymed(),
 203                         span: source.ident.span,
 204                     },
 205                     source: source.ident,
 206                     result: PerNS {
 207                         type_ns: Cell::new(Err(Undetermined)),
 208                         value_ns: Cell::new(Err(Undetermined)),
 209                         macro_ns: Cell::new(Err(Undetermined)),
 210                     },
 211                     type_ns_only: false,
 212                 };
 213                 this.add_import_directive(
 214                     base.into_iter().collect(),
 215                     subclass,
 216                     source.ident.span,
 217                     id,
 218                     root_span,
 219                     item.id,
 220                     ty::Visibility::Invisible,
 221                     parent_scope.clone(),
 222                     true, // is_uniform_paths_canary
 223                 );
 224             };
 225
 226             // A single simple `self::x` canary.
 227             emit(self, Some(Segment {
 228                 ident: Ident {
 229                     name: keywords::SelfValue.name(),
 230                     span: source.ident.span,
 231                 },
 232                 id: source.id
 233             }));
 234
 235             // One special unprefixed canary per block scope around
 236             // the import, to detect items unreachable by `self::x`.
 237             let orig_current_module = self.current_module;
 238             let mut span = source.ident.span.modern();
 239             loop {
 240                 match self.current_module.kind {
 241                     ModuleKind::Block(..) => emit(self, None),
 242                     ModuleKind::Def(..) => break,
 243                 }
 244                 match self.hygienic_lexical_parent(self.current_module, &mut span) {
 245                     Some(module) => {
 246                         self.current_module = module;
 247                     }
 248                     None => break,
 249                 }
 250             }
 251             self.current_module = orig_current_module;
 252
 253             uniform_paths_canary_emitted = true;
 254         }
 255
 256         let empty_for_self = |prefix: &[Segment]| {
 257             prefix.is_empty() ||
 258             prefix.len() == 1 && prefix[0].ident.name == keywords::CrateRoot.name()
 259         };
 260         match use_tree.kind {
 261             ast::UseTreeKind::Simple(rename, ..) => {
 262                 let mut ident = use_tree.ident();
 263                 let mut module_path = prefix;
 264                 let mut source = module_path.pop().unwrap();
 265                 let mut type_ns_only = false;
 266
 267                 if nested {
 268                     // Correctly handle `self`
 269                     if source.ident.name == keywords::SelfValue.name() {
 270                         type_ns_only = true;
 271
 272                         if empty_for_self(&module_path) {
 273                             resolve_error(
 274                                 self,
 275                                 use_tree.span,
 276                                 ResolutionError::
 277                                 SelfImportOnlyInImportListWithNonEmptyPrefix
 278                             );
 279                             return;
 280                         }
 281
 282                         // Replace `use foo::self;` with `use foo;`
 283                         source = module_path.pop().unwrap();
 284                         if rename.is_none() {
 285                             ident = source.ident;
 286                         }
 287                     }
 288                 } else {
 289                     // Disallow `self`
 290                     if source.ident.name == keywords::SelfValue.name() {
 291                         resolve_error(self,
 292                                       use_tree.span,
 293                                       ResolutionError::SelfImportsOnlyAllowedWithin);
 294                     }
 295
 296                     // Disallow `use $crate;`
 297                     if source.ident.name == keywords::DollarCrate.name() && module_path.is_empty() {
 298                         let crate_root = self.resolve_crate_root(source.ident);
 299                         let crate_name = match crate_root.kind {
 300                             ModuleKind::Def(_, name) => name,
 301                             ModuleKind::Block(..) => unreachable!(),
 302                         };
 303                         // HACK(eddyb) unclear how good this is, but keeping `$crate`
 304                         // in `source` breaks `src/test/compile-fail/import-crate-var.rs`,
 305                         // while the current crate doesn't have a valid `crate_name`.
 306                         if crate_name != keywords::Invalid.name() {
 307                             // `crate_name` should not be interpreted as relative.
 308                             module_path.push(Segment {
 309                                 ident: Ident {
 310                                     name: keywords::CrateRoot.name(),
 311                                     span: source.ident.span,
 312                                 },
 313                                 id: Some(self.session.next_node_id()),
 314                             });
 315                             source.ident.name = crate_name;
 316                         }
 317                         if rename.is_none() {
 318                             ident.name = crate_name;
 319                         }
 320
 321                         self.session.struct_span_warn(item.span, "`$crate` may not be imported")
 322                             .note("`use $crate;` was erroneously allowed and \
 323                                    will become a hard error in a future release")
 324                             .emit();
 325                     }
 326                 }
 327
 328                 if ident.name == keywords::Crate.name() {
 329                     self.session.span_err(ident.span,
 330                         "crate root imports need to be explicitly named: \
 331                          `use crate as name;`");
 332                 }
 333
 334                 let subclass = SingleImport {
 335                     target: ident,
 336                     source: source.ident,
 337                     result: PerNS {
 338                         type_ns: Cell::new(Err(Undetermined)),
 339                         value_ns: Cell::new(Err(Undetermined)),
 340                         macro_ns: Cell::new(Err(Undetermined)),
 341                     },
 342                     type_ns_only,
 343                 };
 344                 self.add_import_directive(
 345                     module_path,
 346                     subclass,
 347                     use_tree.span,
 348                     id,
 349                     root_span,
 350                     item.id,
 351                     vis,
 352                     parent_scope,
 353                     false, // is_uniform_paths_canary
 354                 );
 355             }
 356             ast::UseTreeKind::Glob => {
 357                 let subclass = GlobImport {
 358                     is_prelude: attr::contains_name(&item.attrs, "prelude_import"),
 359                     max_vis: Cell::new(ty::Visibility::Invisible),
 360                 };
 361                 self.add_import_directive(
 362                     prefix,
 363                     subclass,
 364                     use_tree.span,
 365                     id,
 366                     root_span,
 367                     item.id,
 368                     vis,
 369                     parent_scope,
 370                     false, // is_uniform_paths_canary
 371                 );
 372             }
 373             ast::UseTreeKind::Nested(ref items) => {
 374                 // Ensure there is at most one `self` in the list
 375                 let self_spans = items.iter().filter_map(|&(ref use_tree, _)| {
 376                     if let ast::UseTreeKind::Simple(..) = use_tree.kind {
 377                         if use_tree.ident().name == keywords::SelfValue.name() {
 378                             return Some(use_tree.span);
 379                         }
 380                     }
 381
 382                     None
 383                 }).collect::<Vec<_>>();
 384                 if self_spans.len() > 1 {
 385                     let mut e = resolve_struct_error(self,
 386                         self_spans[0],
 387                         ResolutionError::SelfImportCanOnlyAppearOnceInTheList);
 388
 389                     for other_span in self_spans.iter().skip(1) {
 390                         e.span_label(*other_span, "another `self` import appears here");
 391                     }
 392
 393                     e.emit();
 394                 }
 395
 396                 for &(ref tree, id) in items {
 397                     self.build_reduced_graph_for_use_tree(
 398                         // This particular use tree
 399                         tree, id, &prefix, true, uniform_paths_canary_emitted,
 400                         // The whole `use` item
 401                         parent_scope.clone(), item, vis, root_span,
 402                     );
 403                 }
 404
 405                 // Empty groups `a::b::{}` are turned into synthetic `self` imports
 406                 // `a::b::c::{self as _}`, so that their prefixes are correctly
 407                 // resolved and checked for privacy/stability/etc.
 408                 if items.is_empty() && !empty_for_self(&prefix) {
 409                     let new_span = prefix[prefix.len() - 1].ident.span;
 410                     let tree = ast::UseTree {
 411                         prefix: ast::Path::from_ident(
 412                             Ident::new(keywords::SelfValue.name(), new_span)
 413                         ),
 414                         kind: ast::UseTreeKind::Simple(
 415                             Some(Ident::new(keywords::Underscore.name().gensymed(), new_span)),
 416                             ast::DUMMY_NODE_ID,
 417                             ast::DUMMY_NODE_ID,
 418                         ),
 419                         span: use_tree.span,
 420                     };
 421                     self.build_reduced_graph_for_use_tree(
 422                         // This particular use tree
 423                         &tree, id, &prefix, true, uniform_paths_canary_emitted,
 424                         // The whole `use` item
 425                         parent_scope.clone(), item, ty::Visibility::Invisible, root_span,
 426                     );
 427                 }
 428             }
 429         }
 430     }
 431
 432     /// Constructs the reduced graph for one item.
 433     fn build_reduced_graph_for_item(&mut self, item: &Item, parent_scope: ParentScope<'a>) {
 434         let parent = parent_scope.module;
 435         let expansion = parent_scope.expansion;
 436         let ident = item.ident;
 437         let sp = item.span;
 438         let vis = self.resolve_visibility(&item.vis);
 439
 440         match item.node {
 441             ItemKind::Use(ref use_tree) => {
 442                 self.build_reduced_graph_for_use_tree(
 443                     // This particular use tree
 444                     use_tree, item.id, &[], false, false,
 445                     // The whole `use` item
 446                     parent_scope, item, vis, use_tree.span,
 447                 );
 448             }
 449
 450             ItemKind::ExternCrate(orig_name) => {
 451                 let crate_id = self.crate_loader.process_extern_crate(item, &self.definitions);
 452                 let module =
 453                     self.get_module(DefId { krate: crate_id, index: CRATE_DEF_INDEX });
 454                 self.populate_module_if_necessary(module);
 455                 if injected_crate_name().map_or(false, |name| ident.name == name) {
 456                     self.injected_crate = Some(module);
 457                 }
 458
 459                 let used = self.process_legacy_macro_imports(item, module, &parent_scope);
 460                 let binding =
 461                     (module, ty::Visibility::Public, sp, expansion).to_name_binding(self.arenas);
 462                 if ptr::eq(self.current_module, self.graph_root) {
 463                     if let Some(entry) = self.extern_prelude.get(&ident.modern()) {
 464                         if expansion != Mark::root() && orig_name.is_some() &&
 465                            entry.extern_crate_item.is_none() {
 466                             self.session.span_err(item.span, "macro-expanded `extern crate` items \
 467                                                               cannot shadow names passed with \
 468                                                               `--extern`");
 469                         }
 470                     }
 471                     let entry = self.extern_prelude.entry(ident.modern())
 472                                                    .or_insert(ExternPreludeEntry {
 473                         extern_crate_item: None,
 474                         introduced_by_item: true,
 475                     });
 476                     entry.extern_crate_item = Some(binding);
 477                     if orig_name.is_some() {
 478                         entry.introduced_by_item = true;
 479                     }
 480                 }
 481                 let directive = self.arenas.alloc_import_directive(ImportDirective {
 482                     root_id: item.id,
 483                     id: item.id,
 484                     parent_scope,
 485                     imported_module: Cell::new(Some(ModuleOrUniformRoot::Module(module))),
 486                     subclass: ImportDirectiveSubclass::ExternCrate {
 487                         source: orig_name,
 488                         target: ident,
 489                     },
 490                     root_span: item.span,
 491                     span: item.span,
 492                     module_path: Vec::new(),
 493                     vis: Cell::new(vis),
 494                     used: Cell::new(used),
 495                     is_uniform_paths_canary: false,
 496                 });
 497                 self.potentially_unused_imports.push(directive);
 498                 let imported_binding = self.import(binding, directive);
 499                 self.define(parent, ident, TypeNS, imported_binding);
 500             }
 501
 502             ItemKind::GlobalAsm(..) => {}
 503
 504             ItemKind::Mod(..) if ident == keywords::Invalid.ident() => {} // Crate root
 505
 506             ItemKind::Mod(..) => {
 507                 let def_id = self.definitions.local_def_id(item.id);
 508                 let module_kind = ModuleKind::Def(Def::Mod(def_id), ident.name);
 509                 let module = self.arenas.alloc_module(ModuleData {
 510                     no_implicit_prelude: parent.no_implicit_prelude || {
 511                         attr::contains_name(&item.attrs, "no_implicit_prelude")
 512                     },
 513                     ..ModuleData::new(Some(parent), module_kind, def_id, expansion, item.span)
 514                 });
 515                 self.define(parent, ident, TypeNS, (module, vis, sp, expansion));
 516                 self.module_map.insert(def_id, module);
 517
 518                 // Descend into the module.
 519                 self.current_module = module;
 520             }
 521
 522             // Handled in `rustc_metadata::{native_libs,link_args}`
 523             ItemKind::ForeignMod(..) => {}
 524
 525             // These items live in the value namespace.
 526             ItemKind::Static(_, m, _) => {
 527                 let mutbl = m == Mutability::Mutable;
 528                 let def = Def::Static(self.definitions.local_def_id(item.id), mutbl);
 529                 self.define(parent, ident, ValueNS, (def, vis, sp, expansion));
 530             }
 531             ItemKind::Const(..) => {
 532                 let def = Def::Const(self.definitions.local_def_id(item.id));
 533                 self.define(parent, ident, ValueNS, (def, vis, sp, expansion));
 534             }
 535             ItemKind::Fn(..) => {
 536                 let def = Def::Fn(self.definitions.local_def_id(item.id));
 537                 self.define(parent, ident, ValueNS, (def, vis, sp, expansion));
 538
 539                 // Functions introducing procedural macros reserve a slot
 540                 // in the macro namespace as well (see #52225).
 541                 if attr::contains_name(&item.attrs, "proc_macro") ||
 542                    attr::contains_name(&item.attrs, "proc_macro_attribute") {
 543                     let def = Def::Macro(def.def_id(), MacroKind::ProcMacroStub);
 544                     self.define(parent, ident, MacroNS, (def, vis, sp, expansion));
 545                 }
 546                 if let Some(attr) = attr::find_by_name(&item.attrs, "proc_macro_derive") {
 547                     if let Some(trait_attr) =
 548                             attr.meta_item_list().and_then(|list| list.get(0).cloned()) {
 549                         if let Some(ident) = trait_attr.name().map(Ident::with_empty_ctxt) {
 550                             let sp = trait_attr.span;
 551                             let def = Def::Macro(def.def_id(), MacroKind::ProcMacroStub);
 552                             self.define(parent, ident, MacroNS, (def, vis, sp, expansion));
 553                         }
 554                     }
 555                 }
 556             }
 557
 558             // These items live in the type namespace.
 559             ItemKind::Ty(..) => {
 560                 let def = Def::TyAlias(self.definitions.local_def_id(item.id));
 561                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 562             }
 563
 564             ItemKind::Existential(_, _) => {
 565                 let def = Def::Existential(self.definitions.local_def_id(item.id));
 566                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 567             }
 568
 569             ItemKind::Enum(ref enum_definition, _) => {
 570                 let def = Def::Enum(self.definitions.local_def_id(item.id));
 571                 let module_kind = ModuleKind::Def(def, ident.name);
 572                 let module = self.new_module(parent,
 573                                              module_kind,
 574                                              parent.normal_ancestor_id,
 575                                              expansion,
 576                                              item.span);
 577                 self.define(parent, ident, TypeNS, (module, vis, sp, expansion));
 578
 579                 for variant in &(*enum_definition).variants {
 580                     self.build_reduced_graph_for_variant(variant, module, vis, expansion);
 581                 }
 582             }
 583
 584             ItemKind::TraitAlias(..) => {
 585                 let def = Def::TraitAlias(self.definitions.local_def_id(item.id));
 586                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 587             }
 588
 589             // These items live in both the type and value namespaces.
 590             ItemKind::Struct(ref struct_def, _) => {
 591                 // Define a name in the type namespace.
 592                 let def_id = self.definitions.local_def_id(item.id);
 593                 let def = Def::Struct(def_id);
 594                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 595
 596                 let mut ctor_vis = vis;
 597
 598                 let has_non_exhaustive = attr::contains_name(&item.attrs, "non_exhaustive");
 599
 600                 // If the structure is marked as non_exhaustive then lower the visibility
 601                 // to within the crate.
 602                 if has_non_exhaustive && vis == ty::Visibility::Public {
 603                     ctor_vis = ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX));
 604                 }
 605
 606                 // Record field names for error reporting.
 607                 let field_names = struct_def.fields().iter().filter_map(|field| {
 608                     let field_vis = self.resolve_visibility(&field.vis);
 609                     if ctor_vis.is_at_least(field_vis, &*self) {
 610                         ctor_vis = field_vis;
 611                     }
 612                     field.ident.map(|ident| ident.name)
 613                 }).collect();
 614                 let item_def_id = self.definitions.local_def_id(item.id);
 615                 self.insert_field_names(item_def_id, field_names);
 616
 617                 // If this is a tuple or unit struct, define a name
 618                 // in the value namespace as well.
 619                 if !struct_def.is_struct() {
 620                     let ctor_def = Def::StructCtor(self.definitions.local_def_id(struct_def.id()),
 621                                                    CtorKind::from_ast(struct_def));
 622                     self.define(parent, ident, ValueNS, (ctor_def, ctor_vis, sp, expansion));
 623                     self.struct_constructors.insert(def.def_id(), (ctor_def, ctor_vis));
 624                 }
 625             }
 626
 627             ItemKind::Union(ref vdata, _) => {
 628                 let def = Def::Union(self.definitions.local_def_id(item.id));
 629                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 630
 631                 // Record field names for error reporting.
 632                 let field_names = vdata.fields().iter().filter_map(|field| {
 633                     self.resolve_visibility(&field.vis);
 634                     field.ident.map(|ident| ident.name)
 635                 }).collect();
 636                 let item_def_id = self.definitions.local_def_id(item.id);
 637                 self.insert_field_names(item_def_id, field_names);
 638             }
 639
 640             ItemKind::Impl(..) => {}
 641
 642             ItemKind::Trait(..) => {
 643                 let def_id = self.definitions.local_def_id(item.id);
 644
 645                 // Add all the items within to a new module.
 646                 let module_kind = ModuleKind::Def(Def::Trait(def_id), ident.name);
 647                 let module = self.new_module(parent,
 648                                              module_kind,
 649                                              parent.normal_ancestor_id,
 650                                              expansion,
 651                                              item.span);
 652                 self.define(parent, ident, TypeNS, (module, vis, sp, expansion));
 653                 self.current_module = module;
 654             }
 655
 656             ItemKind::MacroDef(..) | ItemKind::Mac(_) => unreachable!(),
 657         }
 658     }
 659
 660     // Constructs the reduced graph for one variant. Variants exist in the
 661     // type and value namespaces.
 662     fn build_reduced_graph_for_variant(&mut self,
 663                                        variant: &Variant,
 664                                        parent: Module<'a>,
 665                                        vis: ty::Visibility,
 666                                        expansion: Mark) {
 667         let ident = variant.node.ident;
 668         let def_id = self.definitions.local_def_id(variant.node.data.id());
 669
 670         // Define a name in the type namespace.
 671         let def = Def::Variant(def_id);
 672         self.define(parent, ident, TypeNS, (def, vis, variant.span, expansion));
 673
 674         // Define a constructor name in the value namespace.
 675         // Braced variants, unlike structs, generate unusable names in
 676         // value namespace, they are reserved for possible future use.
 677         let ctor_kind = CtorKind::from_ast(&variant.node.data);
 678         let ctor_def = Def::VariantCtor(def_id, ctor_kind);
 679
 680         self.define(parent, ident, ValueNS, (ctor_def, vis, variant.span, expansion));
 681     }
 682
 683     /// Constructs the reduced graph for one foreign item.
 684     fn build_reduced_graph_for_foreign_item(&mut self, item: &ForeignItem, expansion: Mark) {
 685         let (def, ns) = match item.node {
 686             ForeignItemKind::Fn(..) => {
 687                 (Def::Fn(self.definitions.local_def_id(item.id)), ValueNS)
 688             }
 689             ForeignItemKind::Static(_, m) => {
 690                 (Def::Static(self.definitions.local_def_id(item.id), m), ValueNS)
 691             }
 692             ForeignItemKind::Ty => {
 693                 (Def::ForeignTy(self.definitions.local_def_id(item.id)), TypeNS)
 694             }
 695             ForeignItemKind::Macro(_) => unreachable!(),
 696         };
 697         let parent = self.current_module;
 698         let vis = self.resolve_visibility(&item.vis);
 699         self.define(parent, item.ident, ns, (def, vis, item.span, expansion));
 700     }
 701
 702     fn build_reduced_graph_for_block(&mut self, block: &Block, expansion: Mark) {
 703         let parent = self.current_module;
 704         if self.block_needs_anonymous_module(block) {
 705             let module = self.new_module(parent,
 706                                          ModuleKind::Block(block.id),
 707                                          parent.normal_ancestor_id,
 708                                          expansion,
 709                                          block.span);
 710             self.block_map.insert(block.id, module);
 711             self.current_module = module; // Descend into the block.
 712         }
 713     }
 714
 715     /// Builds the reduced graph for a single item in an external crate.
 716     fn build_reduced_graph_for_external_crate_def(&mut self, parent: Module<'a>, child: Export) {
 717         let Export { ident, def, vis, span, .. } = child;
 718         let def_id = def.def_id();
 719         let expansion = Mark::root(); // FIXME(jseyfried) intercrate hygiene
 720         match def {
 721             Def::Mod(..) | Def::Enum(..) => {
 722                 let module = self.new_module(parent,
 723                                              ModuleKind::Def(def, ident.name),
 724                                              def_id,
 725                                              expansion,
 726                                              span);
 727                 self.define(parent, ident, TypeNS, (module, vis, DUMMY_SP, expansion));
 728             }
 729             Def::Variant(..) | Def::TyAlias(..) | Def::ForeignTy(..) => {
 730                 self.define(parent, ident, TypeNS, (def, vis, DUMMY_SP, expansion));
 731             }
 732             Def::Fn(..) | Def::Static(..) | Def::Const(..) | Def::VariantCtor(..) => {
 733                 self.define(parent, ident, ValueNS, (def, vis, DUMMY_SP, expansion));
 734             }
 735             Def::StructCtor(..) => {
 736                 self.define(parent, ident, ValueNS, (def, vis, DUMMY_SP, expansion));
 737
 738                 if let Some(struct_def_id) =
 739                         self.cstore.def_key(def_id).parent
 740                             .map(|index| DefId { krate: def_id.krate, index: index }) {
 741                     self.struct_constructors.insert(struct_def_id, (def, vis));
 742                 }
 743             }
 744             Def::Trait(..) => {
 745                 let module_kind = ModuleKind::Def(def, ident.name);
 746                 let module = self.new_module(parent,
 747                                              module_kind,
 748                                              parent.normal_ancestor_id,
 749                                              expansion,
 750                                              span);
 751                 self.define(parent, ident, TypeNS, (module, vis, DUMMY_SP, expansion));
 752
 753                 for child in self.cstore.item_children_untracked(def_id, self.session) {
 754                     let ns = if let Def::AssociatedTy(..) = child.def { TypeNS } else { ValueNS };
 755                     self.define(module, child.ident, ns,
 756                                 (child.def, ty::Visibility::Public, DUMMY_SP, expansion));
 757
 758                     if self.cstore.associated_item_cloned_untracked(child.def.def_id())
 759                            .method_has_self_argument {
 760                         self.has_self.insert(child.def.def_id());
 761                     }
 762                 }
 763                 module.populated.set(true);
 764             }
 765             Def::Struct(..) | Def::Union(..) => {
 766                 self.define(parent, ident, TypeNS, (def, vis, DUMMY_SP, expansion));
 767
 768                 // Record field names for error reporting.
 769                 let field_names = self.cstore.struct_field_names_untracked(def_id);
 770                 self.insert_field_names(def_id, field_names);
 771             }
 772             Def::Macro(..) => {
 773                 self.define(parent, ident, MacroNS, (def, vis, DUMMY_SP, expansion));
 774             }
 775             _ => bug!("unexpected definition: {:?}", def)
 776         }
 777     }
 778
 779     pub fn get_module(&mut self, def_id: DefId) -> Module<'a> {
 780         if def_id.krate == LOCAL_CRATE {
 781             return self.module_map[&def_id]
 782         }
 783
 784         let macros_only = self.cstore.dep_kind_untracked(def_id.krate).macros_only();
 785         if let Some(&module) = self.extern_module_map.get(&(def_id, macros_only)) {
 786             return module;
 787         }
 788
 789         let (name, parent) = if def_id.index == CRATE_DEF_INDEX {
 790             (self.cstore.crate_name_untracked(def_id.krate).as_interned_str(), None)
 791         } else {
 792             let def_key = self.cstore.def_key(def_id);
 793             (def_key.disambiguated_data.data.get_opt_name().unwrap(),
 794              Some(self.get_module(DefId { index: def_key.parent.unwrap(), ..def_id })))
 795         };
 796
 797         let kind = ModuleKind::Def(Def::Mod(def_id), name.as_symbol());
 798         let module =
 799             self.arenas.alloc_module(ModuleData::new(parent, kind, def_id, Mark::root(), DUMMY_SP));
 800         self.extern_module_map.insert((def_id, macros_only), module);
 801         module
 802     }
 803
 804     pub fn macro_def_scope(&mut self, expansion: Mark) -> Module<'a> {
 805         let def_id = self.macro_defs[&expansion];
 806         if let Some(id) = self.definitions.as_local_node_id(def_id) {
 807             self.local_macro_def_scopes[&id]
 808         } else if def_id.krate == CrateNum::BuiltinMacros {
 809             self.injected_crate.unwrap_or(self.graph_root)
 810         } else {
 811             let module_def_id = ty::DefIdTree::parent(&*self, def_id).unwrap();
 812             self.get_module(module_def_id)
 813         }
 814     }
 815
 816     pub fn get_macro(&mut self, def: Def) -> Lrc<SyntaxExtension> {
 817         let def_id = match def {
 818             Def::Macro(def_id, ..) => def_id,
 819             Def::NonMacroAttr(attr_kind) => return Lrc::new(SyntaxExtension::NonMacroAttr {
 820                 mark_used: attr_kind == NonMacroAttrKind::Tool,
 821             }),
 822             _ => panic!("expected `Def::Macro` or `Def::NonMacroAttr`"),
 823         };
 824         if let Some(ext) = self.macro_map.get(&def_id) {
 825             return ext.clone();
 826         }
 827
 828         let macro_def = match self.cstore.load_macro_untracked(def_id, &self.session) {
 829             LoadedMacro::MacroDef(macro_def) => macro_def,
 830             LoadedMacro::ProcMacro(ext) => return ext,
 831         };
 832
 833         let ext = Lrc::new(macro_rules::compile(&self.session.parse_sess,
 834                                                &self.session.features_untracked(),
 835                                                &macro_def,
 836                                                self.cstore.crate_edition_untracked(def_id.krate)));
 837         self.macro_map.insert(def_id, ext.clone());
 838         ext
 839     }
 840
 841     /// Ensures that the reduced graph rooted at the given external module
 842     /// is built, building it if it is not.
 843     pub fn populate_module_if_necessary(&mut self, module: Module<'a>) {
 844         if module.populated.get() { return }
 845         let def_id = module.def_id().unwrap();
 846         for child in self.cstore.item_children_untracked(def_id, self.session) {
 847             self.build_reduced_graph_for_external_crate_def(module, child);
 848         }
 849         module.populated.set(true)
 850     }
 851
 852     fn legacy_import_macro(&mut self,
 853                            name: Name,
 854                            binding: &'a NameBinding<'a>,
 855                            span: Span,
 856                            allow_shadowing: bool) {
 857         if self.macro_use_prelude.insert(name, binding).is_some() && !allow_shadowing {
 858             let msg = format!("`{}` is already in scope", name);
 859             let note =
 860                 "macro-expanded `#[macro_use]`s may not shadow existing macros (see RFC 1560)";
 861             self.session.struct_span_err(span, &msg).note(note).emit();
 862         }
 863     }
 864
 865     // This returns true if we should consider the underlying `extern crate` to be used.
 866     fn process_legacy_macro_imports(&mut self, item: &Item, module: Module<'a>,
 867                                     parent_scope: &ParentScope<'a>) -> bool {
 868         let mut import_all = None;
 869         let mut single_imports = Vec::new();
 870         for attr in &item.attrs {
 871             if attr.check_name("macro_use") {
 872                 if self.current_module.parent.is_some() {
 873                     span_err!(self.session, item.span, E0468,
 874                         "an `extern crate` loading macros must be at the crate root");
 875                 }
 876                 let ill_formed = |span| span_err!(self.session, span, E0466, "bad macro import");
 877                 match attr.meta() {
 878                     Some(meta) => match meta.node {
 879                         MetaItemKind::Word => {
 880                             import_all = Some(meta.span);
 881                             break;
 882                         }
 883                         MetaItemKind::List(nested_metas) => for nested_meta in nested_metas {
 884                             match nested_meta.word() {
 885                                 Some(word) => single_imports.push((word.name(), word.span)),
 886                                 None => ill_formed(nested_meta.span),
 887                             }
 888                         }
 889                         MetaItemKind::NameValue(..) => ill_formed(meta.span),
 890                     }
 891                     None => ill_formed(attr.span()),
 892                 }
 893             }
 894         }
 895
 896         let arenas = self.arenas;
 897         let macro_use_directive = |span| arenas.alloc_import_directive(ImportDirective {
 898             root_id: item.id,
 899             id: item.id,
 900             parent_scope: parent_scope.clone(),
 901             imported_module: Cell::new(Some(ModuleOrUniformRoot::Module(module))),
 902             subclass: ImportDirectiveSubclass::MacroUse,
 903             root_span: span,
 904             span,
 905             module_path: Vec::new(),
 906             vis: Cell::new(ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX))),
 907             used: Cell::new(false),
 908             is_uniform_paths_canary: false,
 909         });
 910
 911         let allow_shadowing = parent_scope.expansion == Mark::root();
 912         if let Some(span) = import_all {
 913             let directive = macro_use_directive(span);
 914             self.potentially_unused_imports.push(directive);
 915             module.for_each_child(|ident, ns, binding| if ns == MacroNS {
 916                 let imported_binding = self.import(binding, directive);
 917                 self.legacy_import_macro(ident.name, imported_binding, span, allow_shadowing);
 918             });
 919         } else {
 920             for (name, span) in single_imports.iter().cloned() {
 921                 let ident = Ident::with_empty_ctxt(name);
 922                 let result = self.resolve_ident_in_module(
 923                     ModuleOrUniformRoot::Module(module),
 924                     ident,
 925                     MacroNS,
 926                     false,
 927                     span,
 928                 );
 929                 if let Ok(binding) = result {
 930                     let directive = macro_use_directive(span);
 931                     self.potentially_unused_imports.push(directive);
 932                     let imported_binding = self.import(binding, directive);
 933                     self.legacy_import_macro(name, imported_binding, span, allow_shadowing);
 934                 } else {
 935                     span_err!(self.session, span, E0469, "imported macro not found");
 936                 }
 937             }
 938         }
 939         import_all.is_some() || !single_imports.is_empty()
 940     }
 941
 942     // does this attribute list contain "macro_use"?
 943     fn contains_macro_use(&mut self, attrs: &[ast::Attribute]) -> bool {
 944         for attr in attrs {
 945             if attr.check_name("macro_escape") {
 946                 let msg = "macro_escape is a deprecated synonym for macro_use";
 947                 let mut err = self.session.struct_span_warn(attr.span, msg);
 948                 if let ast::AttrStyle::Inner = attr.style {
 949                     err.help("consider an outer attribute, #[macro_use] mod ...").emit();
 950                 } else {
 951                     err.emit();
 952                 }
 953             } else if !attr.check_name("macro_use") {
 954                 continue;
 955             }
 956
 957             if !attr.is_word() {
 958                 self.session.span_err(attr.span, "arguments to macro_use are not allowed here");
 959             }
 960             return true;
 961         }
 962
 963         false
 964     }
 965 }
 966
 967 pub struct BuildReducedGraphVisitor<'a, 'b: 'a, 'c: 'b> {
 968     pub resolver: &'a mut Resolver<'b, 'c>,
 969     pub current_legacy_scope: LegacyScope<'b>,
 970     pub expansion: Mark,
 971 }
 972
 973 impl<'a, 'b, 'cl> BuildReducedGraphVisitor<'a, 'b, 'cl> {
 974     fn visit_invoc(&mut self, id: ast::NodeId) -> &'b InvocationData<'b> {
 975         let mark = id.placeholder_to_mark();
 976         self.resolver.current_module.unresolved_invocations.borrow_mut().insert(mark);
 977         let invocation = self.resolver.invocations[&mark];
 978         invocation.module.set(self.resolver.current_module);
 979         invocation.parent_legacy_scope.set(self.current_legacy_scope);
 980         invocation.output_legacy_scope.set(self.current_legacy_scope);
 981         invocation
 982     }
 983 }
 984
 985 macro_rules! method {
 986     ($visit:ident: $ty:ty, $invoc:path, $walk:ident) => {
 987         fn $visit(&mut self, node: &'a $ty) {
 988             if let $invoc(..) = node.node {
 989                 self.visit_invoc(node.id);
 990             } else {
 991                 visit::$walk(self, node);
 992             }
 993         }
 994     }
 995 }
 996
 997 impl<'a, 'b, 'cl> Visitor<'a> for BuildReducedGraphVisitor<'a, 'b, 'cl> {
 998     method!(visit_impl_item: ast::ImplItem, ast::ImplItemKind::Macro, walk_impl_item);
 999     method!(visit_expr:      ast::Expr,     ast::ExprKind::Mac,       walk_expr);
1000     method!(visit_pat:       ast::Pat,      ast::PatKind::Mac,        walk_pat);
1001     method!(visit_ty:        ast::Ty,       ast::TyKind::Mac,         walk_ty);
1002
1003     fn visit_item(&mut self, item: &'a Item) {
1004         let macro_use = match item.node {
1005             ItemKind::MacroDef(..) => {
1006                 self.resolver.define_macro(item, self.expansion, &mut self.current_legacy_scope);
1007                 return
1008             }
1009             ItemKind::Mac(..) => {
1010                 self.current_legacy_scope = LegacyScope::Invocation(self.visit_invoc(item.id));
1011                 return
1012             }
1013             ItemKind::Mod(..) => self.resolver.contains_macro_use(&item.attrs),
1014             _ => false,
1015         };
1016
1017         let orig_current_module = self.resolver.current_module;
1018         let orig_current_legacy_scope = self.current_legacy_scope;
1019         let parent_scope = ParentScope {
1020             module: self.resolver.current_module,
1021             expansion: self.expansion,
1022             legacy: self.current_legacy_scope,
1023             derives: Vec::new(),
1024         };
1025         self.resolver.build_reduced_graph_for_item(item, parent_scope);
1026         visit::walk_item(self, item);
1027         self.resolver.current_module = orig_current_module;
1028         if !macro_use {
1029             self.current_legacy_scope = orig_current_legacy_scope;
1030         }
1031     }
1032
1033     fn visit_stmt(&mut self, stmt: &'a ast::Stmt) {
1034         if let ast::StmtKind::Mac(..) = stmt.node {
1035             self.current_legacy_scope = LegacyScope::Invocation(self.visit_invoc(stmt.id));
1036         } else {
1037             visit::walk_stmt(self, stmt);
1038         }
1039     }
1040
1041     fn visit_foreign_item(&mut self, foreign_item: &'a ForeignItem) {
1042         if let ForeignItemKind::Macro(_) = foreign_item.node {
1043             self.visit_invoc(foreign_item.id);
1044             return;
1045         }
1046
1047         self.resolver.build_reduced_graph_for_foreign_item(foreign_item, self.expansion);
1048         visit::walk_foreign_item(self, foreign_item);
1049     }
1050
1051     fn visit_block(&mut self, block: &'a Block) {
1052         let orig_current_module = self.resolver.current_module;
1053         let orig_current_legacy_scope = self.current_legacy_scope;
1054         self.resolver.build_reduced_graph_for_block(block, self.expansion);
1055         visit::walk_block(self, block);
1056         self.resolver.current_module = orig_current_module;
1057         self.current_legacy_scope = orig_current_legacy_scope;
1058     }
1059
1060     fn visit_trait_item(&mut self, item: &'a TraitItem) {
1061         let parent = self.resolver.current_module;
1062
1063         if let TraitItemKind::Macro(_) = item.node {
1064             self.visit_invoc(item.id);
1065             return
1066         }
1067
1068         // Add the item to the trait info.
1069         let item_def_id = self.resolver.definitions.local_def_id(item.id);
1070         let (def, ns) = match item.node {
1071             TraitItemKind::Const(..) => (Def::AssociatedConst(item_def_id), ValueNS),
1072             TraitItemKind::Method(ref sig, _) => {
1073                 if sig.decl.has_self() {
1074                     self.resolver.has_self.insert(item_def_id);
1075                 }
1076                 (Def::Method(item_def_id), ValueNS)
1077             }
1078             TraitItemKind::Type(..) => (Def::AssociatedTy(item_def_id), TypeNS),
1079             TraitItemKind::Macro(_) => bug!(),  // handled above
1080         };
1081
1082         let vis = ty::Visibility::Public;
1083         self.resolver.define(parent, item.ident, ns, (def, vis, item.span, self.expansion));
1084
1085         self.resolver.current_module = parent.parent.unwrap(); // nearest normal ancestor
1086         visit::walk_trait_item(self, item);
1087         self.resolver.current_module = parent;
1088     }
1089
1090     fn visit_token(&mut self, t: Token) {
1091         if let Token::Interpolated(nt) = t {
1092             if let token::NtExpr(ref expr) = nt.0 {
1093                 if let ast::ExprKind::Mac(..) = expr.node {
1094                     self.visit_invoc(expr.id);
1095                 }
1096             }
1097         }
1098     }
1099
1100     fn visit_attribute(&mut self, attr: &'a ast::Attribute) {
1101         if !attr.is_sugared_doc && is_builtin_attr(attr) {
1102             let parent_scope = ParentScope {
1103                 module: self.resolver.current_module.nearest_item_scope(),
1104                 expansion: self.expansion,
1105                 legacy: self.current_legacy_scope,
1106                 // Let's hope discerning built-in attributes from derive helpers is not necessary
1107                 derives: Vec::new(),
1108             };
1109             parent_scope.module.builtin_attrs.borrow_mut().push((
1110                 attr.path.segments[0].ident, parent_scope
1111             ));
1112         }
1113         visit::walk_attribute(self, attr);
1114     }
1115 }