1 // Copyright 2015 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 use self::Determinacy::*;
12 use self::ImportDirectiveSubclass::*;
15 use Namespace::{self, TypeNS, ValueNS};
16 use {NameBinding, NameBindingKind, PrivacyError, ToNameBinding};
20 use UseLexicalScopeFlag::DontUseLexicalScope;
21 use {names_to_string, module_to_string};
22 use {resolve_error, ResolutionError};
25 use rustc::lint::builtin::PRIVATE_IN_PUBLIC;
26 use rustc::hir::def::*;
28 use syntax::ast::{NodeId, Name};
29 use syntax::util::lev_distance::find_best_match_for_name;
30 use syntax_pos::{Span, DUMMY_SP};
32 use std::cell::{Cell, RefCell};
34 impl<'a> Resolver<'a> {
35 pub fn resolve_imports(&mut self) {
36 ImportResolver { resolver: self }.resolve_imports();
40 #[derive(Copy, Clone, Debug)]
41 pub enum Determinacy {
46 /// Contains data for specific types of import directives.
47 #[derive(Clone, Debug)]
48 pub enum ImportDirectiveSubclass<'a> {
52 value_result: Cell<Result<&'a NameBinding<'a>, Determinacy>>,
53 type_result: Cell<Result<&'a NameBinding<'a>, Determinacy>>,
55 GlobImport { is_prelude: bool },
58 impl<'a> ImportDirectiveSubclass<'a> {
59 pub fn single(target: Name, source: Name) -> Self {
63 type_result: Cell::new(Err(Undetermined)),
64 value_result: Cell::new(Err(Undetermined)),
69 /// One import directive.
70 #[derive(Debug,Clone)]
71 pub struct ImportDirective<'a> {
74 module_path: Vec<Name>,
75 imported_module: Cell<Option<Module<'a>>>, // the resolution of `module_path`
76 subclass: ImportDirectiveSubclass<'a>,
78 vis: Cell<ty::Visibility>,
81 impl<'a> ImportDirective<'a> {
82 pub fn is_glob(&self) -> bool {
83 match self.subclass { ImportDirectiveSubclass::GlobImport { .. } => true, _ => false }
87 #[derive(Clone, Default)]
88 /// Records information about the resolution of a name in a namespace of a module.
89 pub struct NameResolution<'a> {
90 /// The single imports that define the name in the namespace.
91 single_imports: SingleImports<'a>,
92 /// The least shadowable known binding for this name, or None if there are no known bindings.
93 pub binding: Option<&'a NameBinding<'a>>,
94 duplicate_globs: Vec<&'a NameBinding<'a>>,
97 #[derive(Clone, Debug)]
98 enum SingleImports<'a> {
99 /// No single imports can define the name in the namespace.
101 /// Only the given single import can define the name in the namespace.
102 MaybeOne(&'a ImportDirective<'a>),
103 /// At least one single import will define the name in the namespace.
107 impl<'a> Default for SingleImports<'a> {
108 fn default() -> Self {
113 impl<'a> SingleImports<'a> {
114 fn add_directive(&mut self, directive: &'a ImportDirective<'a>) {
116 SingleImports::None => *self = SingleImports::MaybeOne(directive),
117 // If two single imports can define the name in the namespace, we can assume that at
118 // least one of them will define it since otherwise both would have to define only one
119 // namespace, leading to a duplicate error.
120 SingleImports::MaybeOne(_) => *self = SingleImports::AtLeastOne,
121 SingleImports::AtLeastOne => {}
125 fn directive_failed(&mut self) {
127 SingleImports::None => unreachable!(),
128 SingleImports::MaybeOne(_) => *self = SingleImports::None,
129 SingleImports::AtLeastOne => {}
134 impl<'a> NameResolution<'a> {
135 // Returns the binding for the name if it is known or None if it not known.
136 fn binding(&self) -> Option<&'a NameBinding<'a>> {
137 self.binding.and_then(|binding| match self.single_imports {
138 SingleImports::None => Some(binding),
139 _ if !binding.is_glob_import() => Some(binding),
140 _ => None, // The binding could be shadowed by a single import, so it is not known.
145 impl<'a> Resolver<'a> {
146 fn resolution(&self, module: Module<'a>, name: Name, ns: Namespace)
147 -> &'a RefCell<NameResolution<'a>> {
148 *module.resolutions.borrow_mut().entry((name, ns))
149 .or_insert_with(|| self.arenas.alloc_name_resolution())
152 /// Attempts to resolve the supplied name in the given module for the given namespace.
153 /// If successful, returns the binding corresponding to the name.
154 /// Invariant: if `record_used` is `Some`, import resolution must be complete.
155 pub fn resolve_name_in_module(&mut self,
159 allow_private_imports: bool,
160 record_used: Option<Span>)
161 -> ResolveResult<&'a NameBinding<'a>> {
162 self.populate_module_if_necessary(module);
164 let resolution = self.resolution(module, name, ns);
165 let resolution = match resolution.borrow_state() {
166 ::std::cell::BorrowState::Unused => resolution.borrow_mut(),
167 _ => return Failed(None), // This happens when there is a cycle of imports
170 let is_disallowed_private_import = |binding: &NameBinding| {
171 !allow_private_imports && !binding.is_pseudo_public() && binding.is_import()
174 if let Some(span) = record_used {
175 if let Some(binding) = resolution.binding {
176 if is_disallowed_private_import(binding) {
179 self.record_use(name, ns, binding);
180 if !self.is_accessible(binding.vis) {
181 self.privacy_errors.push(PrivacyError(span, name, binding));
185 return resolution.binding.map(Success).unwrap_or(Failed(None));
188 // If the resolution doesn't depend on glob definability, check privacy and return.
189 if let Some(result) = self.try_result(&resolution, ns) {
190 return result.and_then(|binding| {
191 if self.is_accessible(binding.vis) && !is_disallowed_private_import(binding) {
199 // Check if the globs are determined
200 for directive in module.globs.borrow().iter() {
201 if self.is_accessible(directive.vis.get()) {
202 if let Some(module) = directive.imported_module.get() {
203 let result = self.resolve_name_in_module(module, name, ns, true, None);
204 if let Indeterminate = result {
205 return Indeterminate;
208 return Indeterminate;
216 // Returns Some(the resolution of the name), or None if the resolution depends
217 // on whether more globs can define the name.
218 fn try_result(&mut self, resolution: &NameResolution<'a>, ns: Namespace)
219 -> Option<ResolveResult<&'a NameBinding<'a>>> {
220 match resolution.binding {
221 Some(binding) if !binding.is_glob_import() =>
222 return Some(Success(binding)), // Items and single imports are not shadowable.
226 // Check if a single import can still define the name.
227 match resolution.single_imports {
228 SingleImports::AtLeastOne => return Some(Indeterminate),
229 SingleImports::MaybeOne(directive) if self.is_accessible(directive.vis.get()) => {
230 let module = match directive.imported_module.get() {
231 Some(module) => module,
232 None => return Some(Indeterminate),
234 let name = match directive.subclass {
235 SingleImport { source, .. } => source,
236 GlobImport { .. } => unreachable!(),
238 match self.resolve_name_in_module(module, name, ns, true, None) {
240 _ => return Some(Indeterminate),
243 SingleImports::MaybeOne(_) | SingleImports::None => {},
246 resolution.binding.map(Success)
249 // Add an import directive to the current module.
250 pub fn add_import_directive(&mut self,
251 module_path: Vec<Name>,
252 subclass: ImportDirectiveSubclass<'a>,
255 vis: ty::Visibility) {
256 let current_module = self.current_module;
257 let directive = self.arenas.alloc_import_directive(ImportDirective {
258 parent: current_module,
259 module_path: module_path,
260 imported_module: Cell::new(None),
267 self.indeterminate_imports.push(directive);
268 match directive.subclass {
269 SingleImport { target, .. } => {
270 for &ns in &[ValueNS, TypeNS] {
271 let mut resolution = self.resolution(current_module, target, ns).borrow_mut();
272 resolution.single_imports.add_directive(directive);
275 // We don't add prelude imports to the globs since they only affect lexical scopes,
276 // which are not relevant to import resolution.
277 GlobImport { is_prelude: true } => {}
278 GlobImport { .. } => self.current_module.globs.borrow_mut().push(directive),
282 // Given a binding and an import directive that resolves to it,
283 // return the corresponding binding defined by the import directive.
284 fn import(&mut self, binding: &'a NameBinding<'a>, directive: &'a ImportDirective<'a>)
287 kind: NameBindingKind::Import {
289 directive: directive,
291 span: directive.span,
292 vis: directive.vis.get(),
296 // Define the name or return the existing binding if there is a collision.
297 pub fn try_define<T>(&mut self, module: Module<'a>, name: Name, ns: Namespace, binding: T)
298 -> Result<(), &'a NameBinding<'a>>
299 where T: ToNameBinding<'a>
301 let binding = self.arenas.alloc_name_binding(binding.to_name_binding());
302 self.update_resolution(module, name, ns, |_, resolution| {
303 if let Some(old_binding) = resolution.binding {
304 if binding.is_glob_import() {
305 resolution.duplicate_globs.push(binding);
306 } else if old_binding.is_glob_import() {
307 resolution.duplicate_globs.push(old_binding);
308 resolution.binding = Some(binding);
310 return Err(old_binding);
313 resolution.binding = Some(binding);
320 // Use `f` to mutate the resolution of the name in the module.
321 // If the resolution becomes a success, define it in the module's glob importers.
322 fn update_resolution<T, F>(&mut self, module: Module<'a>, name: Name, ns: Namespace, f: F) -> T
323 where F: FnOnce(&mut Resolver<'a>, &mut NameResolution<'a>) -> T
325 // Ensure that `resolution` isn't borrowed when defining in the module's glob importers,
326 // during which the resolution might end up getting re-defined via a glob cycle.
327 let (new_binding, t) = {
328 let mut resolution = &mut *self.resolution(module, name, ns).borrow_mut();
329 let was_known = resolution.binding().is_some();
331 let t = f(self, resolution);
333 if was_known { return t; }
334 match resolution.binding() {
335 Some(binding) => (binding, t),
340 // Define `new_binding` in `module`s glob importers.
341 if new_binding.is_importable() && new_binding.is_pseudo_public() {
342 for directive in module.glob_importers.borrow_mut().iter() {
343 let imported_binding = self.import(new_binding, directive);
344 let _ = self.try_define(directive.parent, name, ns, imported_binding);
352 struct ImportResolver<'a, 'b: 'a> {
353 resolver: &'a mut Resolver<'b>,
356 impl<'a, 'b: 'a> ::std::ops::Deref for ImportResolver<'a, 'b> {
357 type Target = Resolver<'b>;
358 fn deref(&self) -> &Resolver<'b> {
363 impl<'a, 'b: 'a> ::std::ops::DerefMut for ImportResolver<'a, 'b> {
364 fn deref_mut(&mut self) -> &mut Resolver<'b> {
369 impl<'a, 'b: 'a> ty::NodeIdTree for ImportResolver<'a, 'b> {
370 fn is_descendant_of(&self, node: NodeId, ancestor: NodeId) -> bool {
371 self.resolver.is_descendant_of(node, ancestor)
375 impl<'a, 'b:'a> ImportResolver<'a, 'b> {
378 // This is a fixed-point algorithm. We resolve imports until our efforts
379 // are stymied by an unresolved import; then we bail out of the current
380 // module and continue. We terminate successfully once no more imports
381 // remain or unsuccessfully when no forward progress in resolving imports
384 fn set_current_module(&mut self, module: Module<'b>) {
385 self.current_module = module;
386 self.current_vis = ty::Visibility::Restricted({
387 let normal_module = self.get_nearest_normal_module_parent_or_self(module);
388 self.definitions.as_local_node_id(normal_module.def_id().unwrap()).unwrap()
392 /// Resolves all imports for the crate. This method performs the fixed-
394 fn resolve_imports(&mut self) {
396 let mut prev_num_indeterminates = self.indeterminate_imports.len() + 1;
398 while self.indeterminate_imports.len() < prev_num_indeterminates {
399 prev_num_indeterminates = self.indeterminate_imports.len();
400 debug!("(resolving imports) iteration {}, {} imports left", i, prev_num_indeterminates);
402 let mut imports = Vec::new();
403 ::std::mem::swap(&mut imports, &mut self.indeterminate_imports);
405 for import in imports {
406 match self.resolve_import(&import) {
407 Failed(_) => self.determined_imports.push(import),
408 Indeterminate => self.indeterminate_imports.push(import),
409 Success(()) => self.determined_imports.push(import),
416 for module in self.arenas.local_modules().iter() {
417 self.finalize_resolutions_in(module);
420 let mut errors = false;
421 for i in 0 .. self.determined_imports.len() {
422 let import = self.determined_imports[i];
423 if let Failed(err) = self.finalize_import(import) {
425 let (span, help) = match err {
426 Some((span, msg)) => (span, format!(". {}", msg)),
427 None => (import.span, String::new()),
430 // If the error is a single failed import then create a "fake" import
431 // resolution for it so that later resolve stages won't complain.
432 self.import_dummy_binding(import);
433 let path = import_path_to_string(&import.module_path, &import.subclass);
434 let error = ResolutionError::UnresolvedImport(Some((&path, &help)));
435 resolve_error(self.resolver, span, error);
439 // Report unresolved imports only if no hard error was already reported
440 // to avoid generating multiple errors on the same import.
442 if let Some(import) = self.indeterminate_imports.iter().next() {
443 let error = ResolutionError::UnresolvedImport(None);
444 resolve_error(self.resolver, import.span, error);
449 // Define a "dummy" resolution containing a Def::Err as a placeholder for a
451 fn import_dummy_binding(&mut self, directive: &'b ImportDirective<'b>) {
452 if let SingleImport { target, .. } = directive.subclass {
453 let dummy_binding = self.arenas.alloc_name_binding(NameBinding {
454 kind: NameBindingKind::Def(Def::Err),
456 vis: ty::Visibility::Public,
458 let dummy_binding = self.import(dummy_binding, directive);
460 let _ = self.try_define(directive.parent, target, ValueNS, dummy_binding.clone());
461 let _ = self.try_define(directive.parent, target, TypeNS, dummy_binding);
465 /// Attempts to resolve the given import. The return value indicates
466 /// failure if we're certain the name does not exist, indeterminate if we
467 /// don't know whether the name exists at the moment due to other
468 /// currently-unresolved imports, or success if we know the name exists.
469 /// If successful, the resolved bindings are written into the module.
470 fn resolve_import(&mut self, directive: &'b ImportDirective<'b>) -> ResolveResult<()> {
471 debug!("(resolving import for module) resolving import `{}::...` in `{}`",
472 names_to_string(&directive.module_path),
473 module_to_string(self.current_module));
475 self.set_current_module(directive.parent);
477 let module = if let Some(module) = directive.imported_module.get() {
480 let vis = directive.vis.get();
481 // For better failure detection, pretend that the import will not define any names
482 // while resolving its module path.
483 directive.vis.set(ty::Visibility::PrivateExternal);
485 self.resolve_module_path(&directive.module_path, DontUseLexicalScope, None);
486 directive.vis.set(vis);
489 Success(module) => module,
490 Indeterminate => return Indeterminate,
491 Failed(err) => return Failed(err),
495 directive.imported_module.set(Some(module));
496 let (source, target, value_result, type_result) = match directive.subclass {
497 SingleImport { source, target, ref value_result, ref type_result } =>
498 (source, target, value_result, type_result),
499 GlobImport { .. } => {
500 self.resolve_glob_import(directive);
505 let mut indeterminate = false;
506 for &(ns, result) in &[(ValueNS, value_result), (TypeNS, type_result)] {
507 if let Err(Undetermined) = result.get() {
509 match self.resolve_name_in_module(module, source, ns, false, None) {
510 Success(binding) => Ok(binding),
511 Indeterminate => Err(Undetermined),
512 Failed(_) => Err(Determined),
520 Err(Undetermined) => indeterminate = true,
522 self.update_resolution(directive.parent, target, ns, |_, resolution| {
523 resolution.single_imports.directive_failed()
526 Ok(binding) if !binding.is_importable() => {
527 let msg = format!("`{}` is not directly importable", target);
528 struct_span_err!(self.session, directive.span, E0253, "{}", &msg)
529 .span_label(directive.span, &format!("cannot be imported directly"))
531 // Do not import this illegal binding. Import a dummy binding and pretend
532 // everything is fine
533 self.import_dummy_binding(directive);
537 let imported_binding = self.import(binding, directive);
538 let conflict = self.try_define(directive.parent, target, ns, imported_binding);
539 if let Err(old_binding) = conflict {
540 let binding = &self.import(binding, directive);
541 self.report_conflict(directive.parent, target, ns, binding, old_binding);
547 if indeterminate { Indeterminate } else { Success(()) }
550 fn finalize_import(&mut self, directive: &'b ImportDirective<'b>) -> ResolveResult<()> {
551 self.set_current_module(directive.parent);
553 let ImportDirective { ref module_path, span, .. } = *directive;
554 let module_result = self.resolve_module_path(&module_path, DontUseLexicalScope, Some(span));
555 let module = match module_result {
556 Success(module) => module,
557 Indeterminate => return Indeterminate,
558 Failed(err) => return Failed(err),
561 let (name, value_result, type_result) = match directive.subclass {
562 SingleImport { source, ref value_result, ref type_result, .. } =>
563 (source, value_result.get(), type_result.get()),
564 GlobImport { .. } if module.def_id() == directive.parent.def_id() => {
565 // Importing a module into itself is not allowed.
566 let msg = "Cannot glob-import a module into itself.".into();
567 return Failed(Some((directive.span, msg)));
569 GlobImport { .. } => return Success(()),
572 for &(ns, result) in &[(ValueNS, value_result), (TypeNS, type_result)] {
573 if let Ok(binding) = result {
574 self.record_use(name, ns, binding);
578 if value_result.is_err() && type_result.is_err() {
579 let (value_result, type_result);
580 value_result = self.resolve_name_in_module(module, name, ValueNS, false, Some(span));
581 type_result = self.resolve_name_in_module(module, name, TypeNS, false, Some(span));
583 return if let (Failed(_), Failed(_)) = (value_result, type_result) {
584 let resolutions = module.resolutions.borrow();
585 let names = resolutions.iter().filter_map(|(&(ref n, _), resolution)| {
586 if *n == name { return None; } // Never suggest the same name
587 match *resolution.borrow() {
588 NameResolution { binding: Some(_), .. } => Some(n),
589 NameResolution { single_imports: SingleImports::None, .. } => None,
593 let lev_suggestion = match find_best_match_for_name(names, &name.as_str(), None) {
594 Some(name) => format!(". Did you mean to use `{}`?", name),
595 None => "".to_owned(),
597 let module_str = module_to_string(module);
598 let msg = if &module_str == "???" {
599 format!("There is no `{}` in the crate root{}", name, lev_suggestion)
601 format!("There is no `{}` in `{}`{}", name, module_str, lev_suggestion)
603 Failed(Some((directive.span, msg)))
605 // `resolve_name_in_module` reported a privacy error.
606 self.import_dummy_binding(directive);
611 match (value_result, type_result) {
612 (Ok(binding), _) if !binding.pseudo_vis().is_at_least(directive.vis.get(), self) => {
613 let msg = format!("`{}` is private, and cannot be reexported", name);
615 format!("consider marking `{}` as `pub` in the imported module", name);
616 struct_span_err!(self.session, directive.span, E0364, "{}", &msg)
617 .span_note(directive.span, ¬e_msg)
621 (_, Ok(binding)) if !binding.pseudo_vis().is_at_least(directive.vis.get(), self) => {
622 if binding.is_extern_crate() {
623 let msg = format!("extern crate `{}` is private, and cannot be reexported \
624 (error E0364), consider declaring with `pub`",
626 self.session.add_lint(PRIVATE_IN_PUBLIC, directive.id, directive.span, msg);
628 struct_span_err!(self.session, directive.span, E0365,
629 "`{}` is private, and cannot be reexported", name)
630 .span_label(directive.span, &format!("reexport of private `{}`", name))
631 .note(&format!("consider declaring type or module `{}` with `pub`", name))
639 // Record what this import resolves to for later uses in documentation,
640 // this may resolve to either a value or a type, but for documentation
641 // purposes it's good enough to just favor one over the other.
642 let def = match type_result.ok().and_then(NameBinding::def) {
644 None => value_result.ok().and_then(NameBinding::def).unwrap(),
646 let path_resolution = PathResolution::new(def);
647 self.def_map.insert(directive.id, path_resolution);
649 debug!("(resolving single import) successfully resolved import");
653 fn resolve_glob_import(&mut self, directive: &'b ImportDirective<'b>) {
654 let module = directive.imported_module.get().unwrap();
655 self.populate_module_if_necessary(module);
657 if let Some(Def::Trait(_)) = module.def {
658 self.session.span_err(directive.span, "items in traits are not importable.");
661 if module.def_id() == directive.parent.def_id() {
663 } else if let GlobImport { is_prelude: true } = directive.subclass {
664 self.prelude = Some(module);
668 // Add to module's glob_importers
669 module.glob_importers.borrow_mut().push(directive);
671 // Ensure that `resolutions` isn't borrowed during `try_define`,
672 // since it might get updated via a glob cycle.
673 let bindings = module.resolutions.borrow().iter().filter_map(|(name, resolution)| {
674 resolution.borrow().binding().map(|binding| (*name, binding))
675 }).collect::<Vec<_>>();
676 for ((name, ns), binding) in bindings {
677 if binding.is_importable() && binding.is_pseudo_public() {
678 let imported_binding = self.import(binding, directive);
679 let _ = self.try_define(directive.parent, name, ns, imported_binding);
683 // Record the destination of this import
684 if let Some(did) = module.def_id() {
685 let resolution = PathResolution::new(Def::Mod(did));
686 self.def_map.insert(directive.id, resolution);
690 // Miscellaneous post-processing, including recording reexports, reporting conflicts,
691 // reporting the PRIVATE_IN_PUBLIC lint, and reporting unresolved imports.
692 fn finalize_resolutions_in(&mut self, module: Module<'b>) {
693 // Since import resolution is finished, globs will not define any more names.
694 *module.globs.borrow_mut() = Vec::new();
696 let mut reexports = Vec::new();
697 for (&(name, ns), resolution) in module.resolutions.borrow().iter() {
698 let resolution = resolution.borrow();
699 let binding = match resolution.binding {
700 Some(binding) => binding,
705 for duplicate_glob in resolution.duplicate_globs.iter() {
706 // FIXME #31337: We currently allow items to shadow glob-imported re-exports.
707 if !binding.is_import() {
708 if let NameBindingKind::Import { binding, .. } = duplicate_glob.kind {
709 if binding.is_import() { continue }
713 self.report_conflict(module, name, ns, duplicate_glob, binding);
716 if binding.vis == ty::Visibility::Public &&
717 (binding.is_import() || binding.is_extern_crate()) {
718 if let Some(def) = binding.def() {
719 reexports.push(Export { name: name, def_id: def.def_id() });
723 if let NameBindingKind::Import { binding: orig_binding, directive, .. } = binding.kind {
724 if ns == TypeNS && orig_binding.is_variant() &&
725 !orig_binding.vis.is_at_least(binding.vis, self) {
726 let msg = format!("variant `{}` is private, and cannot be reexported \
727 (error E0364), consider declaring its enum as `pub`",
729 self.session.add_lint(PRIVATE_IN_PUBLIC, directive.id, binding.span, msg);
734 if reexports.len() > 0 {
735 if let Some(def_id) = module.def_id() {
736 let node_id = self.definitions.as_local_node_id(def_id).unwrap();
737 self.export_map.insert(node_id, reexports);
743 fn import_path_to_string(names: &[Name], subclass: &ImportDirectiveSubclass) -> String {
744 if names.is_empty() {
745 import_directive_subclass_to_string(subclass)
748 names_to_string(names),
749 import_directive_subclass_to_string(subclass)))
754 fn import_directive_subclass_to_string(subclass: &ImportDirectiveSubclass) -> String {
756 SingleImport { source, .. } => source.to_string(),
757 GlobImport { .. } => "*".to_string(),