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, 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: &[Ident],
 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.ident));
 137         let prefix_start = prefix_iter().next();
 138         let starts_with_non_keyword = prefix_start.map_or(false, |ident| {
 139             !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(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<Ident>| {
 200                 let subclass = SingleImport {
 201                     target: Ident {
 202                         name: keywords::Underscore.name().gensymed(),
 203                         span: source.span,
 204                     },
 205                     source,
 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.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(Ident {
 228                 name: keywords::SelfValue.name(),
 229                 span: source.span,
 230             }));
 231
 232             // One special unprefixed canary per block scope around
 233             // the import, to detect items unreachable by `self::x`.
 234             let orig_current_module = self.current_module;
 235             let mut span = source.span.modern();
 236             loop {
 237                 match self.current_module.kind {
 238                     ModuleKind::Block(..) => emit(self, None),
 239                     ModuleKind::Def(..) => break,
 240                 }
 241                 match self.hygienic_lexical_parent(self.current_module, &mut span) {
 242                     Some(module) => {
 243                         self.current_module = module;
 244                     }
 245                     None => break,
 246                 }
 247             }
 248             self.current_module = orig_current_module;
 249
 250             uniform_paths_canary_emitted = true;
 251         }
 252
 253         let empty_for_self = |prefix: &[Ident]| {
 254             prefix.is_empty() ||
 255             prefix.len() == 1 && prefix[0].name == keywords::CrateRoot.name()
 256         };
 257         match use_tree.kind {
 258             ast::UseTreeKind::Simple(rename, ..) => {
 259                 let mut ident = use_tree.ident();
 260                 let mut module_path = prefix;
 261                 let mut source = module_path.pop().unwrap();
 262                 let mut type_ns_only = false;
 263
 264                 if nested {
 265                     // Correctly handle `self`
 266                     if source.name == keywords::SelfValue.name() {
 267                         type_ns_only = true;
 268
 269                         if empty_for_self(&module_path) {
 270                             resolve_error(
 271                                 self,
 272                                 use_tree.span,
 273                                 ResolutionError::
 274                                 SelfImportOnlyInImportListWithNonEmptyPrefix
 275                             );
 276                             return;
 277                         }
 278
 279                         // Replace `use foo::self;` with `use foo;`
 280                         source = module_path.pop().unwrap();
 281                         if rename.is_none() {
 282                             ident = source;
 283                         }
 284                     }
 285                 } else {
 286                     // Disallow `self`
 287                     if source.name == keywords::SelfValue.name() {
 288                         resolve_error(self,
 289                                       use_tree.span,
 290                                       ResolutionError::SelfImportsOnlyAllowedWithin);
 291                     }
 292
 293                     // Disallow `use $crate;`
 294                     if source.name == keywords::DollarCrate.name() && module_path.is_empty() {
 295                         let crate_root = self.resolve_crate_root(source);
 296                         let crate_name = match crate_root.kind {
 297                             ModuleKind::Def(_, name) => name,
 298                             ModuleKind::Block(..) => unreachable!(),
 299                         };
 300                         // HACK(eddyb) unclear how good this is, but keeping `$crate`
 301                         // in `source` breaks `src/test/compile-fail/import-crate-var.rs`,
 302                         // while the current crate doesn't have a valid `crate_name`.
 303                         if crate_name != keywords::Invalid.name() {
 304                             // `crate_name` should not be interpreted as relative.
 305                             module_path.push(Ident {
 306                                 name: keywords::CrateRoot.name(),
 307                                 span: source.span,
 308                             });
 309                             source.name = crate_name;
 310                         }
 311                         if rename.is_none() {
 312                             ident.name = crate_name;
 313                         }
 314
 315                         self.session.struct_span_warn(item.span, "`$crate` may not be imported")
 316                             .note("`use $crate;` was erroneously allowed and \
 317                                    will become a hard error in a future release")
 318                             .emit();
 319                     }
 320                 }
 321
 322                 if ident.name == keywords::Crate.name() {
 323                     self.session.span_err(ident.span,
 324                         "crate root imports need to be explicitly named: \
 325                          `use crate as name;`");
 326                 }
 327
 328                 let subclass = SingleImport {
 329                     target: ident,
 330                     source,
 331                     result: PerNS {
 332                         type_ns: Cell::new(Err(Undetermined)),
 333                         value_ns: Cell::new(Err(Undetermined)),
 334                         macro_ns: Cell::new(Err(Undetermined)),
 335                     },
 336                     type_ns_only,
 337                 };
 338                 self.add_import_directive(
 339                     module_path,
 340                     subclass,
 341                     use_tree.span,
 342                     id,
 343                     root_span,
 344                     item.id,
 345                     vis,
 346                     parent_scope,
 347                     false, // is_uniform_paths_canary
 348                 );
 349             }
 350             ast::UseTreeKind::Glob => {
 351                 let subclass = GlobImport {
 352                     is_prelude: attr::contains_name(&item.attrs, "prelude_import"),
 353                     max_vis: Cell::new(ty::Visibility::Invisible),
 354                 };
 355                 self.add_import_directive(
 356                     prefix,
 357                     subclass,
 358                     use_tree.span,
 359                     id,
 360                     root_span,
 361                     item.id,
 362                     vis,
 363                     parent_scope,
 364                     false, // is_uniform_paths_canary
 365                 );
 366             }
 367             ast::UseTreeKind::Nested(ref items) => {
 368                 // Ensure there is at most one `self` in the list
 369                 let self_spans = items.iter().filter_map(|&(ref use_tree, _)| {
 370                     if let ast::UseTreeKind::Simple(..) = use_tree.kind {
 371                         if use_tree.ident().name == keywords::SelfValue.name() {
 372                             return Some(use_tree.span);
 373                         }
 374                     }
 375
 376                     None
 377                 }).collect::<Vec<_>>();
 378                 if self_spans.len() > 1 {
 379                     let mut e = resolve_struct_error(self,
 380                         self_spans[0],
 381                         ResolutionError::SelfImportCanOnlyAppearOnceInTheList);
 382
 383                     for other_span in self_spans.iter().skip(1) {
 384                         e.span_label(*other_span, "another `self` import appears here");
 385                     }
 386
 387                     e.emit();
 388                 }
 389
 390                 for &(ref tree, id) in items {
 391                     self.build_reduced_graph_for_use_tree(
 392                         // This particular use tree
 393                         tree, id, &prefix, true, uniform_paths_canary_emitted,
 394                         // The whole `use` item
 395                         parent_scope.clone(), item, vis, root_span,
 396                     );
 397                 }
 398
 399                 // Empty groups `a::b::{}` are turned into synthetic `self` imports
 400                 // `a::b::c::{self as _}`, so that their prefixes are correctly
 401                 // resolved and checked for privacy/stability/etc.
 402                 if items.is_empty() && !empty_for_self(&prefix) {
 403                     let new_span = prefix[prefix.len() - 1].span;
 404                     let tree = ast::UseTree {
 405                         prefix: ast::Path::from_ident(
 406                             Ident::new(keywords::SelfValue.name(), new_span)
 407                         ),
 408                         kind: ast::UseTreeKind::Simple(
 409                             Some(Ident::new(keywords::Underscore.name().gensymed(), new_span)),
 410                             ast::DUMMY_NODE_ID,
 411                             ast::DUMMY_NODE_ID,
 412                         ),
 413                         span: use_tree.span,
 414                     };
 415                     self.build_reduced_graph_for_use_tree(
 416                         // This particular use tree
 417                         &tree, id, &prefix, true, uniform_paths_canary_emitted,
 418                         // The whole `use` item
 419                         parent_scope.clone(), item, ty::Visibility::Invisible, root_span,
 420                     );
 421                 }
 422             }
 423         }
 424     }
 425
 426     /// Constructs the reduced graph for one item.
 427     fn build_reduced_graph_for_item(&mut self, item: &Item, parent_scope: ParentScope<'a>) {
 428         let parent = parent_scope.module;
 429         let expansion = parent_scope.expansion;
 430         let ident = item.ident;
 431         let sp = item.span;
 432         let vis = self.resolve_visibility(&item.vis);
 433
 434         match item.node {
 435             ItemKind::Use(ref use_tree) => {
 436                 self.build_reduced_graph_for_use_tree(
 437                     // This particular use tree
 438                     use_tree, item.id, &[], false, false,
 439                     // The whole `use` item
 440                     parent_scope, item, vis, use_tree.span,
 441                 );
 442             }
 443
 444             ItemKind::ExternCrate(orig_name) => {
 445                 let crate_id = self.crate_loader.process_extern_crate(item, &self.definitions);
 446                 let module =
 447                     self.get_module(DefId { krate: crate_id, index: CRATE_DEF_INDEX });
 448                 self.populate_module_if_necessary(module);
 449                 if injected_crate_name().map_or(false, |name| ident.name == name) {
 450                     self.injected_crate = Some(module);
 451                 }
 452
 453                 let used = self.process_legacy_macro_imports(item, module, &parent_scope);
 454                 let binding =
 455                     (module, ty::Visibility::Public, sp, expansion).to_name_binding(self.arenas);
 456                 if ptr::eq(self.current_module, self.graph_root) {
 457                     if let Some(entry) = self.extern_prelude.get(&ident.modern()) {
 458                         if expansion != Mark::root() && orig_name.is_some() &&
 459                            entry.extern_crate_item.is_none() {
 460                             self.session.span_err(item.span, "macro-expanded `extern crate` items \
 461                                                               cannot shadow names passed with \
 462                                                               `--extern`");
 463                         }
 464                     }
 465                     let entry = self.extern_prelude.entry(ident.modern())
 466                                                    .or_insert(ExternPreludeEntry {
 467                         extern_crate_item: None,
 468                         introduced_by_item: true,
 469                     });
 470                     entry.extern_crate_item = Some(binding);
 471                     if orig_name.is_some() {
 472                         entry.introduced_by_item = true;
 473                     }
 474                 }
 475                 let directive = self.arenas.alloc_import_directive(ImportDirective {
 476                     root_id: item.id,
 477                     id: item.id,
 478                     parent_scope,
 479                     imported_module: Cell::new(Some(ModuleOrUniformRoot::Module(module))),
 480                     subclass: ImportDirectiveSubclass::ExternCrate {
 481                         source: orig_name,
 482                         target: ident,
 483                     },
 484                     root_span: item.span,
 485                     span: item.span,
 486                     module_path: Vec::new(),
 487                     vis: Cell::new(vis),
 488                     used: Cell::new(used),
 489                     is_uniform_paths_canary: false,
 490                 });
 491                 self.potentially_unused_imports.push(directive);
 492                 let imported_binding = self.import(binding, directive);
 493                 self.define(parent, ident, TypeNS, imported_binding);
 494             }
 495
 496             ItemKind::GlobalAsm(..) => {}
 497
 498             ItemKind::Mod(..) if ident == keywords::Invalid.ident() => {} // Crate root
 499
 500             ItemKind::Mod(..) => {
 501                 let def_id = self.definitions.local_def_id(item.id);
 502                 let module_kind = ModuleKind::Def(Def::Mod(def_id), ident.name);
 503                 let module = self.arenas.alloc_module(ModuleData {
 504                     no_implicit_prelude: parent.no_implicit_prelude || {
 505                         attr::contains_name(&item.attrs, "no_implicit_prelude")
 506                     },
 507                     ..ModuleData::new(Some(parent), module_kind, def_id, expansion, item.span)
 508                 });
 509                 self.define(parent, ident, TypeNS, (module, vis, sp, expansion));
 510                 self.module_map.insert(def_id, module);
 511
 512                 // Descend into the module.
 513                 self.current_module = module;
 514             }
 515
 516             // Handled in `rustc_metadata::{native_libs,link_args}`
 517             ItemKind::ForeignMod(..) => {}
 518
 519             // These items live in the value namespace.
 520             ItemKind::Static(_, m, _) => {
 521                 let mutbl = m == Mutability::Mutable;
 522                 let def = Def::Static(self.definitions.local_def_id(item.id), mutbl);
 523                 self.define(parent, ident, ValueNS, (def, vis, sp, expansion));
 524             }
 525             ItemKind::Const(..) => {
 526                 let def = Def::Const(self.definitions.local_def_id(item.id));
 527                 self.define(parent, ident, ValueNS, (def, vis, sp, expansion));
 528             }
 529             ItemKind::Fn(..) => {
 530                 let def = Def::Fn(self.definitions.local_def_id(item.id));
 531                 self.define(parent, ident, ValueNS, (def, vis, sp, expansion));
 532
 533                 // Functions introducing procedural macros reserve a slot
 534                 // in the macro namespace as well (see #52225).
 535                 if attr::contains_name(&item.attrs, "proc_macro") ||
 536                    attr::contains_name(&item.attrs, "proc_macro_attribute") {
 537                     let def = Def::Macro(def.def_id(), MacroKind::ProcMacroStub);
 538                     self.define(parent, ident, MacroNS, (def, vis, sp, expansion));
 539                 }
 540                 if let Some(attr) = attr::find_by_name(&item.attrs, "proc_macro_derive") {
 541                     if let Some(trait_attr) =
 542                             attr.meta_item_list().and_then(|list| list.get(0).cloned()) {
 543                         if let Some(ident) = trait_attr.name().map(Ident::with_empty_ctxt) {
 544                             let sp = trait_attr.span;
 545                             let def = Def::Macro(def.def_id(), MacroKind::ProcMacroStub);
 546                             self.define(parent, ident, MacroNS, (def, vis, sp, expansion));
 547                         }
 548                     }
 549                 }
 550             }
 551
 552             // These items live in the type namespace.
 553             ItemKind::Ty(..) => {
 554                 let def = Def::TyAlias(self.definitions.local_def_id(item.id));
 555                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 556             }
 557
 558             ItemKind::Existential(_, _) => {
 559                 let def = Def::Existential(self.definitions.local_def_id(item.id));
 560                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 561             }
 562
 563             ItemKind::Enum(ref enum_definition, _) => {
 564                 let def = Def::Enum(self.definitions.local_def_id(item.id));
 565                 let module_kind = ModuleKind::Def(def, ident.name);
 566                 let module = self.new_module(parent,
 567                                              module_kind,
 568                                              parent.normal_ancestor_id,
 569                                              expansion,
 570                                              item.span);
 571                 self.define(parent, ident, TypeNS, (module, vis, sp, expansion));
 572
 573                 for variant in &(*enum_definition).variants {
 574                     self.build_reduced_graph_for_variant(variant, module, vis, expansion);
 575                 }
 576             }
 577
 578             ItemKind::TraitAlias(..) => {
 579                 let def = Def::TraitAlias(self.definitions.local_def_id(item.id));
 580                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 581             }
 582
 583             // These items live in both the type and value namespaces.
 584             ItemKind::Struct(ref struct_def, _) => {
 585                 // Define a name in the type namespace.
 586                 let def_id = self.definitions.local_def_id(item.id);
 587                 let def = Def::Struct(def_id);
 588                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 589
 590                 let mut ctor_vis = vis;
 591
 592                 let has_non_exhaustive = attr::contains_name(&item.attrs, "non_exhaustive");
 593
 594                 // If the structure is marked as non_exhaustive then lower the visibility
 595                 // to within the crate.
 596                 if has_non_exhaustive && vis == ty::Visibility::Public {
 597                     ctor_vis = ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX));
 598                 }
 599
 600                 // Record field names for error reporting.
 601                 let field_names = struct_def.fields().iter().filter_map(|field| {
 602                     let field_vis = self.resolve_visibility(&field.vis);
 603                     if ctor_vis.is_at_least(field_vis, &*self) {
 604                         ctor_vis = field_vis;
 605                     }
 606                     field.ident.map(|ident| ident.name)
 607                 }).collect();
 608                 let item_def_id = self.definitions.local_def_id(item.id);
 609                 self.insert_field_names(item_def_id, field_names);
 610
 611                 // If this is a tuple or unit struct, define a name
 612                 // in the value namespace as well.
 613                 if !struct_def.is_struct() {
 614                     let ctor_def = Def::StructCtor(self.definitions.local_def_id(struct_def.id()),
 615                                                    CtorKind::from_ast(struct_def));
 616                     self.define(parent, ident, ValueNS, (ctor_def, ctor_vis, sp, expansion));
 617                     self.struct_constructors.insert(def.def_id(), (ctor_def, ctor_vis));
 618                 }
 619             }
 620
 621             ItemKind::Union(ref vdata, _) => {
 622                 let def = Def::Union(self.definitions.local_def_id(item.id));
 623                 self.define(parent, ident, TypeNS, (def, vis, sp, expansion));
 624
 625                 // Record field names for error reporting.
 626                 let field_names = vdata.fields().iter().filter_map(|field| {
 627                     self.resolve_visibility(&field.vis);
 628                     field.ident.map(|ident| ident.name)
 629                 }).collect();
 630                 let item_def_id = self.definitions.local_def_id(item.id);
 631                 self.insert_field_names(item_def_id, field_names);
 632             }
 633
 634             ItemKind::Impl(..) => {}
 635
 636             ItemKind::Trait(..) => {
 637                 let def_id = self.definitions.local_def_id(item.id);
 638
 639                 // Add all the items within to a new module.
 640                 let module_kind = ModuleKind::Def(Def::Trait(def_id), ident.name);
 641                 let module = self.new_module(parent,
 642                                              module_kind,
 643                                              parent.normal_ancestor_id,
 644                                              expansion,
 645                                              item.span);
 646                 self.define(parent, ident, TypeNS, (module, vis, sp, expansion));
 647                 self.current_module = module;
 648             }
 649
 650             ItemKind::MacroDef(..) | ItemKind::Mac(_) => unreachable!(),
 651         }
 652     }
 653
 654     // Constructs the reduced graph for one variant. Variants exist in the
 655     // type and value namespaces.
 656     fn build_reduced_graph_for_variant(&mut self,
 657                                        variant: &Variant,
 658                                        parent: Module<'a>,
 659                                        vis: ty::Visibility,
 660                                        expansion: Mark) {
 661         let ident = variant.node.ident;
 662         let def_id = self.definitions.local_def_id(variant.node.data.id());
 663
 664         // Define a name in the type namespace.
 665         let def = Def::Variant(def_id);
 666         self.define(parent, ident, TypeNS, (def, vis, variant.span, expansion));
 667
 668         // Define a constructor name in the value namespace.
 669         // Braced variants, unlike structs, generate unusable names in
 670         // value namespace, they are reserved for possible future use.
 671         let ctor_kind = CtorKind::from_ast(&variant.node.data);
 672         let ctor_def = Def::VariantCtor(def_id, ctor_kind);
 673
 674         self.define(parent, ident, ValueNS, (ctor_def, vis, variant.span, expansion));
 675     }
 676
 677     /// Constructs the reduced graph for one foreign item.
 678     fn build_reduced_graph_for_foreign_item(&mut self, item: &ForeignItem, expansion: Mark) {
 679         let (def, ns) = match item.node {
 680             ForeignItemKind::Fn(..) => {
 681                 (Def::Fn(self.definitions.local_def_id(item.id)), ValueNS)
 682             }
 683             ForeignItemKind::Static(_, m) => {
 684                 (Def::Static(self.definitions.local_def_id(item.id), m), ValueNS)
 685             }
 686             ForeignItemKind::Ty => {
 687                 (Def::ForeignTy(self.definitions.local_def_id(item.id)), TypeNS)
 688             }
 689             ForeignItemKind::Macro(_) => unreachable!(),
 690         };
 691         let parent = self.current_module;
 692         let vis = self.resolve_visibility(&item.vis);
 693         self.define(parent, item.ident, ns, (def, vis, item.span, expansion));
 694     }
 695
 696     fn build_reduced_graph_for_block(&mut self, block: &Block, expansion: Mark) {
 697         let parent = self.current_module;
 698         if self.block_needs_anonymous_module(block) {
 699             let module = self.new_module(parent,
 700                                          ModuleKind::Block(block.id),
 701                                          parent.normal_ancestor_id,
 702                                          expansion,
 703                                          block.span);
 704             self.block_map.insert(block.id, module);
 705             self.current_module = module; // Descend into the block.
 706         }
 707     }
 708
 709     /// Builds the reduced graph for a single item in an external crate.
 710     fn build_reduced_graph_for_external_crate_def(&mut self, parent: Module<'a>, child: Export) {
 711         let Export { ident, def, vis, span, .. } = child;
 712         let def_id = def.def_id();
 713         let expansion = Mark::root(); // FIXME(jseyfried) intercrate hygiene
 714         match def {
 715             Def::Mod(..) | Def::Enum(..) => {
 716                 let module = self.new_module(parent,
 717                                              ModuleKind::Def(def, ident.name),
 718                                              def_id,
 719                                              expansion,
 720                                              span);
 721                 self.define(parent, ident, TypeNS, (module, vis, DUMMY_SP, expansion));
 722             }
 723             Def::Variant(..) | Def::TyAlias(..) | Def::ForeignTy(..) => {
 724                 self.define(parent, ident, TypeNS, (def, vis, DUMMY_SP, expansion));
 725             }
 726             Def::Fn(..) | Def::Static(..) | Def::Const(..) | Def::VariantCtor(..) => {
 727                 self.define(parent, ident, ValueNS, (def, vis, DUMMY_SP, expansion));
 728             }
 729             Def::StructCtor(..) => {
 730                 self.define(parent, ident, ValueNS, (def, vis, DUMMY_SP, expansion));
 731
 732                 if let Some(struct_def_id) =
 733                         self.cstore.def_key(def_id).parent
 734                             .map(|index| DefId { krate: def_id.krate, index: index }) {
 735                     self.struct_constructors.insert(struct_def_id, (def, vis));
 736                 }
 737             }
 738             Def::Trait(..) => {
 739                 let module_kind = ModuleKind::Def(def, ident.name);
 740                 let module = self.new_module(parent,
 741                                              module_kind,
 742                                              parent.normal_ancestor_id,
 743                                              expansion,
 744                                              span);
 745                 self.define(parent, ident, TypeNS, (module, vis, DUMMY_SP, expansion));
 746
 747                 for child in self.cstore.item_children_untracked(def_id, self.session) {
 748                     let ns = if let Def::AssociatedTy(..) = child.def { TypeNS } else { ValueNS };
 749                     self.define(module, child.ident, ns,
 750                                 (child.def, ty::Visibility::Public, DUMMY_SP, expansion));
 751
 752                     if self.cstore.associated_item_cloned_untracked(child.def.def_id())
 753                            .method_has_self_argument {
 754                         self.has_self.insert(child.def.def_id());
 755                     }
 756                 }
 757                 module.populated.set(true);
 758             }
 759             Def::Struct(..) | Def::Union(..) => {
 760                 self.define(parent, ident, TypeNS, (def, vis, DUMMY_SP, expansion));
 761
 762                 // Record field names for error reporting.
 763                 let field_names = self.cstore.struct_field_names_untracked(def_id);
 764                 self.insert_field_names(def_id, field_names);
 765             }
 766             Def::Macro(..) => {
 767                 self.define(parent, ident, MacroNS, (def, vis, DUMMY_SP, expansion));
 768             }
 769             _ => bug!("unexpected definition: {:?}", def)
 770         }
 771     }
 772
 773     pub fn get_module(&mut self, def_id: DefId) -> Module<'a> {
 774         if def_id.krate == LOCAL_CRATE {
 775             return self.module_map[&def_id]
 776         }
 777
 778         let macros_only = self.cstore.dep_kind_untracked(def_id.krate).macros_only();
 779         if let Some(&module) = self.extern_module_map.get(&(def_id, macros_only)) {
 780             return module;
 781         }
 782
 783         let (name, parent) = if def_id.index == CRATE_DEF_INDEX {
 784             (self.cstore.crate_name_untracked(def_id.krate).as_interned_str(), None)
 785         } else {
 786             let def_key = self.cstore.def_key(def_id);
 787             (def_key.disambiguated_data.data.get_opt_name().unwrap(),
 788              Some(self.get_module(DefId { index: def_key.parent.unwrap(), ..def_id })))
 789         };
 790
 791         let kind = ModuleKind::Def(Def::Mod(def_id), name.as_symbol());
 792         let module =
 793             self.arenas.alloc_module(ModuleData::new(parent, kind, def_id, Mark::root(), DUMMY_SP));
 794         self.extern_module_map.insert((def_id, macros_only), module);
 795         module
 796     }
 797
 798     pub fn macro_def_scope(&mut self, expansion: Mark) -> Module<'a> {
 799         let def_id = self.macro_defs[&expansion];
 800         if let Some(id) = self.definitions.as_local_node_id(def_id) {
 801             self.local_macro_def_scopes[&id]
 802         } else if def_id.krate == CrateNum::BuiltinMacros {
 803             self.injected_crate.unwrap_or(self.graph_root)
 804         } else {
 805             let module_def_id = ty::DefIdTree::parent(&*self, def_id).unwrap();
 806             self.get_module(module_def_id)
 807         }
 808     }
 809
 810     pub fn get_macro(&mut self, def: Def) -> Lrc<SyntaxExtension> {
 811         let def_id = match def {
 812             Def::Macro(def_id, ..) => def_id,
 813             Def::NonMacroAttr(attr_kind) => return Lrc::new(SyntaxExtension::NonMacroAttr {
 814                 mark_used: attr_kind == NonMacroAttrKind::Tool,
 815             }),
 816             _ => panic!("expected `Def::Macro` or `Def::NonMacroAttr`"),
 817         };
 818         if let Some(ext) = self.macro_map.get(&def_id) {
 819             return ext.clone();
 820         }
 821
 822         let macro_def = match self.cstore.load_macro_untracked(def_id, &self.session) {
 823             LoadedMacro::MacroDef(macro_def) => macro_def,
 824             LoadedMacro::ProcMacro(ext) => return ext,
 825         };
 826
 827         let ext = Lrc::new(macro_rules::compile(&self.session.parse_sess,
 828                                                &self.session.features_untracked(),
 829                                                &macro_def,
 830                                                self.cstore.crate_edition_untracked(def_id.krate)));
 831         self.macro_map.insert(def_id, ext.clone());
 832         ext
 833     }
 834
 835     /// Ensures that the reduced graph rooted at the given external module
 836     /// is built, building it if it is not.
 837     pub fn populate_module_if_necessary(&mut self, module: Module<'a>) {
 838         if module.populated.get() { return }
 839         let def_id = module.def_id().unwrap();
 840         for child in self.cstore.item_children_untracked(def_id, self.session) {
 841             self.build_reduced_graph_for_external_crate_def(module, child);
 842         }
 843         module.populated.set(true)
 844     }
 845
 846     fn legacy_import_macro(&mut self,
 847                            name: Name,
 848                            binding: &'a NameBinding<'a>,
 849                            span: Span,
 850                            allow_shadowing: bool) {
 851         if self.macro_use_prelude.insert(name, binding).is_some() && !allow_shadowing {
 852             let msg = format!("`{}` is already in scope", name);
 853             let note =
 854                 "macro-expanded `#[macro_use]`s may not shadow existing macros (see RFC 1560)";
 855             self.session.struct_span_err(span, &msg).note(note).emit();
 856         }
 857     }
 858
 859     // This returns true if we should consider the underlying `extern crate` to be used.
 860     fn process_legacy_macro_imports(&mut self, item: &Item, module: Module<'a>,
 861                                     parent_scope: &ParentScope<'a>) -> bool {
 862         let mut import_all = None;
 863         let mut single_imports = Vec::new();
 864         for attr in &item.attrs {
 865             if attr.check_name("macro_use") {
 866                 if self.current_module.parent.is_some() {
 867                     span_err!(self.session, item.span, E0468,
 868                         "an `extern crate` loading macros must be at the crate root");
 869                 }
 870                 let ill_formed = |span| span_err!(self.session, span, E0466, "bad macro import");
 871                 match attr.meta() {
 872                     Some(meta) => match meta.node {
 873                         MetaItemKind::Word => {
 874                             import_all = Some(meta.span);
 875                             break;
 876                         }
 877                         MetaItemKind::List(nested_metas) => for nested_meta in nested_metas {
 878                             match nested_meta.word() {
 879                                 Some(word) => single_imports.push((word.name(), word.span)),
 880                                 None => ill_formed(nested_meta.span),
 881                             }
 882                         }
 883                         MetaItemKind::NameValue(..) => ill_formed(meta.span),
 884                     }
 885                     None => ill_formed(attr.span()),
 886                 }
 887             }
 888         }
 889
 890         let arenas = self.arenas;
 891         let macro_use_directive = |span| arenas.alloc_import_directive(ImportDirective {
 892             root_id: item.id,
 893             id: item.id,
 894             parent_scope: parent_scope.clone(),
 895             imported_module: Cell::new(Some(ModuleOrUniformRoot::Module(module))),
 896             subclass: ImportDirectiveSubclass::MacroUse,
 897             root_span: span,
 898             span,
 899             module_path: Vec::new(),
 900             vis: Cell::new(ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX))),
 901             used: Cell::new(false),
 902             is_uniform_paths_canary: false,
 903         });
 904
 905         let allow_shadowing = parent_scope.expansion == Mark::root();
 906         if let Some(span) = import_all {
 907             let directive = macro_use_directive(span);
 908             self.potentially_unused_imports.push(directive);
 909             module.for_each_child(|ident, ns, binding| if ns == MacroNS {
 910                 let imported_binding = self.import(binding, directive);
 911                 self.legacy_import_macro(ident.name, imported_binding, span, allow_shadowing);
 912             });
 913         } else {
 914             for (name, span) in single_imports.iter().cloned() {
 915                 let ident = Ident::with_empty_ctxt(name);
 916                 let result = self.resolve_ident_in_module(
 917                     ModuleOrUniformRoot::Module(module),
 918                     ident,
 919                     MacroNS,
 920                     false,
 921                     span,
 922                 );
 923                 if let Ok(binding) = result {
 924                     let directive = macro_use_directive(span);
 925                     self.potentially_unused_imports.push(directive);
 926                     let imported_binding = self.import(binding, directive);
 927                     self.legacy_import_macro(name, imported_binding, span, allow_shadowing);
 928                 } else {
 929                     span_err!(self.session, span, E0469, "imported macro not found");
 930                 }
 931             }
 932         }
 933         import_all.is_some() || !single_imports.is_empty()
 934     }
 935
 936     // does this attribute list contain "macro_use"?
 937     fn contains_macro_use(&mut self, attrs: &[ast::Attribute]) -> bool {
 938         for attr in attrs {
 939             if attr.check_name("macro_escape") {
 940                 let msg = "macro_escape is a deprecated synonym for macro_use";
 941                 let mut err = self.session.struct_span_warn(attr.span, msg);
 942                 if let ast::AttrStyle::Inner = attr.style {
 943                     err.help("consider an outer attribute, #[macro_use] mod ...").emit();
 944                 } else {
 945                     err.emit();
 946                 }
 947             } else if !attr.check_name("macro_use") {
 948                 continue;
 949             }
 950
 951             if !attr.is_word() {
 952                 self.session.span_err(attr.span, "arguments to macro_use are not allowed here");
 953             }
 954             return true;
 955         }
 956
 957         false
 958     }
 959 }
 960
 961 pub struct BuildReducedGraphVisitor<'a, 'b: 'a, 'c: 'b> {
 962     pub resolver: &'a mut Resolver<'b, 'c>,
 963     pub current_legacy_scope: LegacyScope<'b>,
 964     pub expansion: Mark,
 965 }
 966
 967 impl<'a, 'b, 'cl> BuildReducedGraphVisitor<'a, 'b, 'cl> {
 968     fn visit_invoc(&mut self, id: ast::NodeId) -> &'b InvocationData<'b> {
 969         let mark = id.placeholder_to_mark();
 970         self.resolver.current_module.unresolved_invocations.borrow_mut().insert(mark);
 971         let invocation = self.resolver.invocations[&mark];
 972         invocation.module.set(self.resolver.current_module);
 973         invocation.parent_legacy_scope.set(self.current_legacy_scope);
 974         invocation.output_legacy_scope.set(self.current_legacy_scope);
 975         invocation
 976     }
 977 }
 978
 979 macro_rules! method {
 980     ($visit:ident: $ty:ty, $invoc:path, $walk:ident) => {
 981         fn $visit(&mut self, node: &'a $ty) {
 982             if let $invoc(..) = node.node {
 983                 self.visit_invoc(node.id);
 984             } else {
 985                 visit::$walk(self, node);
 986             }
 987         }
 988     }
 989 }
 990
 991 impl<'a, 'b, 'cl> Visitor<'a> for BuildReducedGraphVisitor<'a, 'b, 'cl> {
 992     method!(visit_impl_item: ast::ImplItem, ast::ImplItemKind::Macro, walk_impl_item);
 993     method!(visit_expr:      ast::Expr,     ast::ExprKind::Mac,       walk_expr);
 994     method!(visit_pat:       ast::Pat,      ast::PatKind::Mac,        walk_pat);
 995     method!(visit_ty:        ast::Ty,       ast::TyKind::Mac,         walk_ty);
 996
 997     fn visit_item(&mut self, item: &'a Item) {
 998         let macro_use = match item.node {
 999             ItemKind::MacroDef(..) => {
1000                 self.resolver.define_macro(item, self.expansion, &mut self.current_legacy_scope);
1001                 return
1002             }
1003             ItemKind::Mac(..) => {
1004                 self.current_legacy_scope = LegacyScope::Invocation(self.visit_invoc(item.id));
1005                 return
1006             }
1007             ItemKind::Mod(..) => self.resolver.contains_macro_use(&item.attrs),
1008             _ => false,
1009         };
1010
1011         let orig_current_module = self.resolver.current_module;
1012         let orig_current_legacy_scope = self.current_legacy_scope;
1013         let parent_scope = ParentScope {
1014             module: self.resolver.current_module,
1015             expansion: self.expansion,
1016             legacy: self.current_legacy_scope,
1017             derives: Vec::new(),
1018         };
1019         self.resolver.build_reduced_graph_for_item(item, parent_scope);
1020         visit::walk_item(self, item);
1021         self.resolver.current_module = orig_current_module;
1022         if !macro_use {
1023             self.current_legacy_scope = orig_current_legacy_scope;
1024         }
1025     }
1026
1027     fn visit_stmt(&mut self, stmt: &'a ast::Stmt) {
1028         if let ast::StmtKind::Mac(..) = stmt.node {
1029             self.current_legacy_scope = LegacyScope::Invocation(self.visit_invoc(stmt.id));
1030         } else {
1031             visit::walk_stmt(self, stmt);
1032         }
1033     }
1034
1035     fn visit_foreign_item(&mut self, foreign_item: &'a ForeignItem) {
1036         if let ForeignItemKind::Macro(_) = foreign_item.node {
1037             self.visit_invoc(foreign_item.id);
1038             return;
1039         }
1040
1041         self.resolver.build_reduced_graph_for_foreign_item(foreign_item, self.expansion);
1042         visit::walk_foreign_item(self, foreign_item);
1043     }
1044
1045     fn visit_block(&mut self, block: &'a Block) {
1046         let orig_current_module = self.resolver.current_module;
1047         let orig_current_legacy_scope = self.current_legacy_scope;
1048         self.resolver.build_reduced_graph_for_block(block, self.expansion);
1049         visit::walk_block(self, block);
1050         self.resolver.current_module = orig_current_module;
1051         self.current_legacy_scope = orig_current_legacy_scope;
1052     }
1053
1054     fn visit_trait_item(&mut self, item: &'a TraitItem) {
1055         let parent = self.resolver.current_module;
1056
1057         if let TraitItemKind::Macro(_) = item.node {
1058             self.visit_invoc(item.id);
1059             return
1060         }
1061
1062         // Add the item to the trait info.
1063         let item_def_id = self.resolver.definitions.local_def_id(item.id);
1064         let (def, ns) = match item.node {
1065             TraitItemKind::Const(..) => (Def::AssociatedConst(item_def_id), ValueNS),
1066             TraitItemKind::Method(ref sig, _) => {
1067                 if sig.decl.has_self() {
1068                     self.resolver.has_self.insert(item_def_id);
1069                 }
1070                 (Def::Method(item_def_id), ValueNS)
1071             }
1072             TraitItemKind::Type(..) => (Def::AssociatedTy(item_def_id), TypeNS),
1073             TraitItemKind::Macro(_) => bug!(),  // handled above
1074         };
1075
1076         let vis = ty::Visibility::Public;
1077         self.resolver.define(parent, item.ident, ns, (def, vis, item.span, self.expansion));
1078
1079         self.resolver.current_module = parent.parent.unwrap(); // nearest normal ancestor
1080         visit::walk_trait_item(self, item);
1081         self.resolver.current_module = parent;
1082     }
1083
1084     fn visit_token(&mut self, t: Token) {
1085         if let Token::Interpolated(nt) = t {
1086             if let token::NtExpr(ref expr) = nt.0 {
1087                 if let ast::ExprKind::Mac(..) = expr.node {
1088                     self.visit_invoc(expr.id);
1089                 }
1090             }
1091         }
1092     }
1093
1094     fn visit_attribute(&mut self, attr: &'a ast::Attribute) {
1095         if !attr.is_sugared_doc && is_builtin_attr(attr) {
1096             let parent_scope = ParentScope {
1097                 module: self.resolver.current_module.nearest_item_scope(),
1098                 expansion: self.expansion,
1099                 legacy: self.current_legacy_scope,
1100                 // Let's hope discerning built-in attributes from derive helpers is not necessary
1101                 derives: Vec::new(),
1102             };
1103             parent_scope.module.builtin_attrs.borrow_mut().push((
1104                 attr.path.segments[0].ident, parent_scope
1105             ));
1106         }
1107         visit::walk_attribute(self, attr);
1108     }
1109 }