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.
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.
11 //! Reduced graph building
13 //! Here we build the "reduced graph": the graph of the module tree without
14 //! any imports resolved.
16 use resolve_imports
::ImportDirectiveSubclass
::{self, GlobImport}
;
18 use Namespace
::{self, TypeNS, ValueNS}
;
19 use {NameBinding, NameBindingKind}
;
20 use ParentLink
::{ModuleParentLink, BlockParentLink}
;
22 use {resolve_error, resolve_struct_error, ResolutionError}
;
24 use rustc
::middle
::cstore
::{ChildItem, DlDef}
;
25 use rustc
::hir
::def
::*;
26 use rustc
::hir
::def_id
::{CRATE_DEF_INDEX, DefId}
;
27 use rustc
::ty
::{self, VariantKind}
;
29 use syntax
::ast
::Name
;
31 use syntax
::parse
::token
;
33 use syntax
::ast
::{Block, Crate}
;
34 use syntax
::ast
::{ForeignItem, ForeignItemKind, Item, ItemKind}
;
35 use syntax
::ast
::{Mutability, PathListItemKind}
;
36 use syntax
::ast
::{StmtKind, TraitItemKind}
;
37 use syntax
::ast
::{Variant, ViewPathGlob, ViewPathList, ViewPathSimple}
;
38 use syntax
::visit
::{self, Visitor}
;
40 use syntax_pos
::{Span, DUMMY_SP}
;
42 trait ToNameBinding
<'a
> {
43 fn to_name_binding(self) -> NameBinding
<'a
>;
46 impl<'a
> ToNameBinding
<'a
> for (Module
<'a
>, Span
, ty
::Visibility
) {
47 fn to_name_binding(self) -> NameBinding
<'a
> {
48 NameBinding { kind: NameBindingKind::Module(self.0), span: self.1, vis: self.2 }
52 impl<'a
> ToNameBinding
<'a
> for (Def
, Span
, ty
::Visibility
) {
53 fn to_name_binding(self) -> NameBinding
<'a
> {
54 NameBinding { kind: NameBindingKind::Def(self.0), span: self.1, vis: self.2 }
58 impl<'b
> Resolver
<'b
> {
59 /// Constructs the reduced graph for the entire crate.
60 pub fn build_reduced_graph(&mut self, krate
: &Crate
) {
61 let no_implicit_prelude
= attr
::contains_name(&krate
.attrs
, "no_implicit_prelude");
62 self.graph_root
.no_implicit_prelude
.set(no_implicit_prelude
);
64 let mut visitor
= BuildReducedGraphVisitor
{
65 parent
: self.graph_root
,
68 visit
::walk_crate(&mut visitor
, krate
);
71 /// Defines `name` in namespace `ns` of module `parent` to be `def` if it is not yet defined.
72 fn try_define
<T
>(&self, parent
: Module
<'b
>, name
: Name
, ns
: Namespace
, def
: T
)
73 where T
: ToNameBinding
<'b
>
75 let _
= parent
.try_define_child(name
, ns
, def
.to_name_binding());
78 /// Defines `name` in namespace `ns` of module `parent` to be `def` if it is not yet defined;
79 /// otherwise, reports an error.
80 fn define
<T
: ToNameBinding
<'b
>>(&self, parent
: Module
<'b
>, name
: Name
, ns
: Namespace
, def
: T
) {
81 let binding
= def
.to_name_binding();
82 if let Err(old_binding
) = parent
.try_define_child(name
, ns
, binding
.clone()) {
83 self.report_conflict(parent
, name
, ns
, old_binding
, &binding
);
87 fn block_needs_anonymous_module(&mut self, block
: &Block
) -> bool
{
88 // If any statements are items, we need to create an anonymous module
89 block
.stmts
.iter().any(|statement
| match statement
.node
{
90 StmtKind
::Item(_
) => true,
95 /// Constructs the reduced graph for one item.
96 fn build_reduced_graph_for_item(&mut self, item
: &Item
, parent_ref
: &mut Module
<'b
>) {
97 let parent
= *parent_ref
;
98 let name
= item
.ident
.name
;
100 self.current_module
= parent
;
101 let vis
= self.resolve_visibility(&item
.vis
);
104 ItemKind
::Use(ref view_path
) => {
105 // Extract and intern the module part of the path. For
106 // globs and lists, the path is found directly in the AST;
107 // for simple paths we have to munge the path a little.
108 let module_path
: Vec
<Name
> = match view_path
.node
{
109 ViewPathSimple(_
, ref full_path
) => {
115 .map(|seg
| seg
.identifier
.name
)
119 ViewPathGlob(ref module_ident_path
) |
120 ViewPathList(ref module_ident_path
, _
) => {
121 module_ident_path
.segments
123 .map(|seg
| seg
.identifier
.name
)
128 // Build up the import directives.
129 let is_prelude
= attr
::contains_name(&item
.attrs
, "prelude_import");
131 match view_path
.node
{
132 ViewPathSimple(binding
, ref full_path
) => {
133 let source_name
= full_path
.segments
.last().unwrap().identifier
.name
;
134 if source_name
.as_str() == "mod" || source_name
.as_str() == "self" {
137 ResolutionError
::SelfImportsOnlyAllowedWithin
);
140 let subclass
= ImportDirectiveSubclass
::single(binding
.name
, source_name
);
141 let span
= view_path
.span
;
142 parent
.add_import_directive(module_path
, subclass
, span
, item
.id
, vis
);
143 self.unresolved_imports
+= 1;
145 ViewPathList(_
, ref source_items
) => {
146 // Make sure there's at most one `mod` import in the list.
147 let mod_spans
= source_items
.iter().filter_map(|item
| {
149 PathListItemKind
::Mod { .. }
=> Some(item
.span
),
152 }).collect
::<Vec
<Span
>>();
154 if mod_spans
.len() > 1 {
155 let mut e
= resolve_struct_error(self,
157 ResolutionError
::SelfImportCanOnlyAppearOnceInTheList
);
158 for other_span
in mod_spans
.iter().skip(1) {
159 e
.span_note(*other_span
, "another `self` import appears here");
164 for source_item
in source_items
{
165 let (module_path
, name
, rename
) = match source_item
.node
{
166 PathListItemKind
::Ident { name, rename, .. }
=>
167 (module_path
.clone(), name
.name
, rename
.unwrap_or(name
).name
),
168 PathListItemKind
::Mod { rename, .. }
=> {
169 let name
= match module_path
.last() {
176 SelfImportOnlyInImportListWithNonEmptyPrefix
181 let module_path
= module_path
.split_last().unwrap().1;
182 let rename
= rename
.map(|i
| i
.name
).unwrap_or(name
);
183 (module_path
.to_vec(), name
, rename
)
186 let subclass
= ImportDirectiveSubclass
::single(rename
, name
);
187 let (span
, id
) = (source_item
.span
, source_item
.node
.id());
188 parent
.add_import_directive(module_path
, subclass
, span
, id
, vis
);
189 self.unresolved_imports
+= 1;
193 let subclass
= GlobImport { is_prelude: is_prelude }
;
194 let span
= view_path
.span
;
195 parent
.add_import_directive(module_path
, subclass
, span
, item
.id
, vis
);
196 self.unresolved_imports
+= 1;
201 ItemKind
::ExternCrate(_
) => {
202 // n.b. we don't need to look at the path option here, because cstore already
204 if let Some(crate_id
) = self.session
.cstore
.extern_mod_stmt_cnum(item
.id
) {
207 index
: CRATE_DEF_INDEX
,
209 let parent_link
= ModuleParentLink(parent
, name
);
210 let def
= Def
::Mod(def_id
);
211 let module
= self.new_extern_crate_module(parent_link
, def
, item
.id
);
212 self.define(parent
, name
, TypeNS
, (module
, sp
, vis
));
214 self.build_reduced_graph_for_external_crate(module
);
218 ItemKind
::Mod(..) => {
219 let parent_link
= ModuleParentLink(parent
, name
);
220 let def
= Def
::Mod(self.definitions
.local_def_id(item
.id
));
221 let module
= self.new_module(parent_link
, Some(def
), false);
222 module
.no_implicit_prelude
.set({
223 parent
.no_implicit_prelude
.get() ||
224 attr
::contains_name(&item
.attrs
, "no_implicit_prelude")
226 self.define(parent
, name
, TypeNS
, (module
, sp
, vis
));
227 self.module_map
.insert(item
.id
, module
);
228 *parent_ref
= module
;
231 ItemKind
::ForeignMod(..) => {}
233 // These items live in the value namespace.
234 ItemKind
::Static(_
, m
, _
) => {
235 let mutbl
= m
== Mutability
::Mutable
;
236 let def
= Def
::Static(self.definitions
.local_def_id(item
.id
), mutbl
);
237 self.define(parent
, name
, ValueNS
, (def
, sp
, vis
));
239 ItemKind
::Const(_
, _
) => {
240 let def
= Def
::Const(self.definitions
.local_def_id(item
.id
));
241 self.define(parent
, name
, ValueNS
, (def
, sp
, vis
));
243 ItemKind
::Fn(_
, _
, _
, _
, _
, _
) => {
244 let def
= Def
::Fn(self.definitions
.local_def_id(item
.id
));
245 self.define(parent
, name
, ValueNS
, (def
, sp
, vis
));
248 // These items live in the type namespace.
249 ItemKind
::Ty(..) => {
250 let def
= Def
::TyAlias(self.definitions
.local_def_id(item
.id
));
251 self.define(parent
, name
, TypeNS
, (def
, sp
, vis
));
254 ItemKind
::Enum(ref enum_definition
, _
) => {
255 let parent_link
= ModuleParentLink(parent
, name
);
256 let def
= Def
::Enum(self.definitions
.local_def_id(item
.id
));
257 let module
= self.new_module(parent_link
, Some(def
), false);
258 self.define(parent
, name
, TypeNS
, (module
, sp
, vis
));
260 for variant
in &(*enum_definition
).variants
{
261 let item_def_id
= self.definitions
.local_def_id(item
.id
);
262 self.build_reduced_graph_for_variant(variant
, item_def_id
, module
, vis
);
266 // These items live in both the type and value namespaces.
267 ItemKind
::Struct(ref struct_def
, _
) => {
268 // Define a name in the type namespace.
269 let def
= Def
::Struct(self.definitions
.local_def_id(item
.id
));
270 self.define(parent
, name
, TypeNS
, (def
, sp
, vis
));
272 // If this is a newtype or unit-like struct, define a name
273 // in the value namespace as well
274 if !struct_def
.is_struct() {
275 let def
= Def
::Struct(self.definitions
.local_def_id(struct_def
.id()));
276 self.define(parent
, name
, ValueNS
, (def
, sp
, vis
));
279 // Record the def ID and fields of this struct.
280 let field_names
= struct_def
.fields().iter().enumerate().map(|(index
, field
)| {
281 self.resolve_visibility(&field
.vis
);
282 field
.ident
.map(|ident
| ident
.name
)
283 .unwrap_or_else(|| token
::intern(&index
.to_string()))
285 let item_def_id
= self.definitions
.local_def_id(item
.id
);
286 self.structs
.insert(item_def_id
, field_names
);
289 ItemKind
::DefaultImpl(_
, _
) | ItemKind
::Impl(..) => {}
291 ItemKind
::Trait(_
, _
, _
, ref items
) => {
292 let def_id
= self.definitions
.local_def_id(item
.id
);
294 // Add all the items within to a new module.
295 let parent_link
= ModuleParentLink(parent
, name
);
296 let def
= Def
::Trait(def_id
);
297 let module_parent
= self.new_module(parent_link
, Some(def
), false);
298 self.define(parent
, name
, TypeNS
, (module_parent
, sp
, vis
));
300 // Add the names of all the items to the trait info.
302 let item_def_id
= self.definitions
.local_def_id(item
.id
);
303 let mut is_static_method
= false;
304 let (def
, ns
) = match item
.node
{
305 TraitItemKind
::Const(..) => (Def
::AssociatedConst(item_def_id
), ValueNS
),
306 TraitItemKind
::Method(ref sig
, _
) => {
307 is_static_method
= !sig
.decl
.has_self();
308 (Def
::Method(item_def_id
), ValueNS
)
310 TraitItemKind
::Type(..) => (Def
::AssociatedTy(def_id
, item_def_id
), TypeNS
),
311 TraitItemKind
::Macro(_
) => panic
!("unexpanded macro in resolve!"),
314 self.define(module_parent
, item
.ident
.name
, ns
, (def
, item
.span
, vis
));
316 self.trait_item_map
.insert((item
.ident
.name
, def_id
), is_static_method
);
319 ItemKind
::Mac(_
) => panic
!("unexpanded macro in resolve!"),
323 // Constructs the reduced graph for one variant. Variants exist in the
324 // type and value namespaces.
325 fn build_reduced_graph_for_variant(&mut self,
329 vis
: ty
::Visibility
) {
330 let name
= variant
.node
.name
.name
;
331 if variant
.node
.data
.is_struct() {
332 // Not adding fields for variants as they are not accessed with a self receiver
333 let variant_def_id
= self.definitions
.local_def_id(variant
.node
.data
.id());
334 self.structs
.insert(variant_def_id
, Vec
::new());
337 // Variants are always treated as importable to allow them to be glob used.
338 // All variants are defined in both type and value namespaces as future-proofing.
339 let def
= Def
::Variant(item_id
, self.definitions
.local_def_id(variant
.node
.data
.id()));
340 self.define(parent
, name
, ValueNS
, (def
, variant
.span
, vis
));
341 self.define(parent
, name
, TypeNS
, (def
, variant
.span
, vis
));
344 /// Constructs the reduced graph for one foreign item.
345 fn build_reduced_graph_for_foreign_item(&mut self,
346 foreign_item
: &ForeignItem
,
347 parent
: Module
<'b
>) {
348 let name
= foreign_item
.ident
.name
;
350 let def
= match foreign_item
.node
{
351 ForeignItemKind
::Fn(..) => {
352 Def
::Fn(self.definitions
.local_def_id(foreign_item
.id
))
354 ForeignItemKind
::Static(_
, m
) => {
355 Def
::Static(self.definitions
.local_def_id(foreign_item
.id
), m
)
358 self.current_module
= parent
;
359 let vis
= self.resolve_visibility(&foreign_item
.vis
);
360 self.define(parent
, name
, ValueNS
, (def
, foreign_item
.span
, vis
));
363 fn build_reduced_graph_for_block(&mut self, block
: &Block
, parent
: &mut Module
<'b
>) {
364 if self.block_needs_anonymous_module(block
) {
365 let block_id
= block
.id
;
367 debug
!("(building reduced graph for block) creating a new anonymous module for block \
371 let parent_link
= BlockParentLink(parent
, block_id
);
372 let new_module
= self.new_module(parent_link
, None
, false);
373 self.module_map
.insert(block_id
, new_module
);
374 *parent
= new_module
;
378 /// Builds the reduced graph for a single item in an external crate.
379 fn build_reduced_graph_for_external_crate_def(&mut self, parent
: Module
<'b
>, xcdef
: ChildItem
) {
380 let def
= match xcdef
.def
{
385 if let Def
::ForeignMod(def_id
) = def
{
386 // Foreign modules have no names. Recur and populate eagerly.
387 for child
in self.session
.cstore
.item_children(def_id
) {
388 self.build_reduced_graph_for_external_crate_def(parent
, child
);
393 let name
= xcdef
.name
;
394 let vis
= if parent
.is_trait() { ty::Visibility::Public }
else { xcdef.vis }
;
397 Def
::Mod(_
) | Def
::ForeignMod(_
) | Def
::Enum(..) => {
398 debug
!("(building reduced graph for external crate) building module {} {:?}",
400 let parent_link
= ModuleParentLink(parent
, name
);
401 let module
= self.new_module(parent_link
, Some(def
), true);
402 self.try_define(parent
, name
, TypeNS
, (module
, DUMMY_SP
, vis
));
404 Def
::Variant(_
, variant_id
) => {
405 debug
!("(building reduced graph for external crate) building variant {}", name
);
406 // Variants are always treated as importable to allow them to be glob used.
407 // All variants are defined in both type and value namespaces as future-proofing.
408 self.try_define(parent
, name
, TypeNS
, (def
, DUMMY_SP
, vis
));
409 self.try_define(parent
, name
, ValueNS
, (def
, DUMMY_SP
, vis
));
410 if self.session
.cstore
.variant_kind(variant_id
) == Some(VariantKind
::Struct
) {
411 // Not adding fields for variants as they are not accessed with a self receiver
412 self.structs
.insert(variant_id
, Vec
::new());
418 Def
::AssociatedConst(..) |
420 debug
!("(building reduced graph for external crate) building value (fn/static) {}",
422 self.try_define(parent
, name
, ValueNS
, (def
, DUMMY_SP
, vis
));
424 Def
::Trait(def_id
) => {
425 debug
!("(building reduced graph for external crate) building type {}", name
);
427 // If this is a trait, add all the trait item names to the trait
430 let trait_item_def_ids
= self.session
.cstore
.trait_item_def_ids(def_id
);
431 for trait_item_def
in &trait_item_def_ids
{
432 let trait_item_name
=
433 self.session
.cstore
.item_name(trait_item_def
.def_id());
435 debug
!("(building reduced graph for external crate) ... adding trait item \
439 self.trait_item_map
.insert((trait_item_name
, def_id
), false);
442 let parent_link
= ModuleParentLink(parent
, name
);
443 let module
= self.new_module(parent_link
, Some(def
), true);
444 self.try_define(parent
, name
, TypeNS
, (module
, DUMMY_SP
, vis
));
446 Def
::TyAlias(..) | Def
::AssociatedTy(..) => {
447 debug
!("(building reduced graph for external crate) building type {}", name
);
448 self.try_define(parent
, name
, TypeNS
, (def
, DUMMY_SP
, vis
));
451 if self.session
.cstore
.tuple_struct_definition_if_ctor(def_id
).is_none() => {
452 debug
!("(building reduced graph for external crate) building type and value for {}",
454 self.try_define(parent
, name
, TypeNS
, (def
, DUMMY_SP
, vis
));
455 if let Some(ctor_def_id
) = self.session
.cstore
.struct_ctor_def_id(def_id
) {
456 let def
= Def
::Struct(ctor_def_id
);
457 self.try_define(parent
, name
, ValueNS
, (def
, DUMMY_SP
, vis
));
460 // Record the def ID and fields of this struct.
461 let fields
= self.session
.cstore
.struct_field_names(def_id
);
462 self.structs
.insert(def_id
, fields
);
464 Def
::Struct(..) => {}
472 bug
!("didn't expect `{:?}`", def
);
477 /// Builds the reduced graph rooted at the 'use' directive for an external
479 fn build_reduced_graph_for_external_crate(&mut self, root
: Module
<'b
>) {
480 let root_cnum
= root
.def_id().unwrap().krate
;
481 for child
in self.session
.cstore
.crate_top_level_items(root_cnum
) {
482 self.build_reduced_graph_for_external_crate_def(root
, child
);
486 /// Ensures that the reduced graph rooted at the given external module
487 /// is built, building it if it is not.
488 pub fn populate_module_if_necessary(&mut self, module
: Module
<'b
>) {
489 if module
.populated
.get() { return }
490 for child
in self.session
.cstore
.item_children(module
.def_id().unwrap()) {
491 self.build_reduced_graph_for_external_crate_def(module
, child
);
493 module
.populated
.set(true)
497 struct BuildReducedGraphVisitor
<'a
, 'b
: 'a
> {
498 resolver
: &'a
mut Resolver
<'b
>,
502 impl<'a
, 'b
> Visitor
for BuildReducedGraphVisitor
<'a
, 'b
> {
503 fn visit_item(&mut self, item
: &Item
) {
504 let old_parent
= self.parent
;
505 self.resolver
.build_reduced_graph_for_item(item
, &mut self.parent
);
506 visit
::walk_item(self, item
);
507 self.parent
= old_parent
;
510 fn visit_foreign_item(&mut self, foreign_item
: &ForeignItem
) {
511 self.resolver
.build_reduced_graph_for_foreign_item(foreign_item
, &self.parent
);
514 fn visit_block(&mut self, block
: &Block
) {
515 let old_parent
= self.parent
;
516 self.resolver
.build_reduced_graph_for_block(block
, &mut self.parent
);
517 visit
::walk_block(self, block
);
518 self.parent
= old_parent
;