Auto merge of #32167 - jseyfried:refactor_prelude, r=nikomatsakis

resolve: Refactor how the prelude is handled

This PR refactors how the prelude is handled in `resolve`.

Instead of importing names from the prelude into each module's `resolutions`, this PR adds a new field `prelude: RefCell<Option<Module>>` to `ModuleS` that is set during import resolution but used only when resolving in a lexical scope (i.e. the scope of an initial segment of a relative path).

r? @nikomatsakis

3 files changed, 70 insertions, 90 deletions

diff --git a/src/librustc_resolve/build_reduced_graph.rs b/src/librustc_resolve/build_reduced_graph.rs
index 08b5e517290..479fc5ebf90 100644
--- a/src/librustc_resolve/build_reduced_graph.rs
+++ b/src/librustc_resolve/build_reduced_graph.rs
@@ -22,7 +22,6 @@ use {NameBinding, NameBindingKind};
 use module_to_string;
 use ParentLink::{ModuleParentLink, BlockParentLink};
 use Resolver;
-use resolve_imports::Shadowable;
 use {resolve_error, resolve_struct_error, ResolutionError};
 
 use rustc::middle::cstore::{CrateStore, ChildItem, DlDef, DlField, DlImpl};
@@ -161,14 +160,9 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 };
 
                 // Build up the import directives.
-                let shadowable = item.attrs.iter().any(|attr| {
+                let is_prelude = item.attrs.iter().any(|attr| {
                     attr.name() == special_idents::prelude_import.name.as_str()
                 });
-                let shadowable = if shadowable {
-                    Shadowable::Always
-                } else {
-                    Shadowable::Never
-                };
 
                 match view_path.node {
                     ViewPathSimple(binding, ref full_path) => {
@@ -186,7 +180,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                                     view_path.span,
                                                     item.id,
                                                     is_public,
-                                                    shadowable);
+                                                    is_prelude);
                     }
                     ViewPathList(_, ref source_items) => {
                         // Make sure there's at most one `mod` import in the list.
@@ -237,7 +231,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                                         source_item.span,
                                                         source_item.node.id(),
                                                         is_public,
-                                                        shadowable);
+                                                        is_prelude);
                         }
                     }
                     ViewPathGlob(_) => {
@@ -247,7 +241,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                                     view_path.span,
                                                     item.id,
                                                     is_public,
-                                                    shadowable);
+                                                    is_prelude);
                     }
                 }
                 parent
@@ -631,7 +625,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                               span: Span,
                               id: NodeId,
                               is_public: bool,
-                              shadowable: Shadowable) {
+                              is_prelude: bool) {
         // Bump the reference count on the name. Or, if this is a glob, set
         // the appropriate flag.
 
@@ -640,15 +634,18 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 module_.increment_outstanding_references_for(target, ValueNS, is_public);
                 module_.increment_outstanding_references_for(target, TypeNS, is_public);
             }
-            GlobImport => {
+            GlobImport if !is_prelude => {
                 // Set the glob flag. This tells us that we don't know the
                 // module's exports ahead of time.
                 module_.inc_glob_count(is_public)
             }
+            // Prelude imports are not included in the glob counts since they do not get added to
+            // `resolved_globs` -- they are handled separately in `resolve_imports`.
+            GlobImport => {}
         }
 
         let directive =
-            ImportDirective::new(module_path, subclass, span, id, is_public, shadowable);
+            ImportDirective::new(module_path, subclass, span, id, is_public, is_prelude);
         module_.add_import_directive(directive);
         self.unresolved_imports += 1;
     }
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index af8c9d81687..77fdc657b88 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -349,7 +349,8 @@ fn resolve_struct_error<'b, 'a: 'b, 'tcx: 'a>(resolver: &'b Resolver<'a, 'tcx>,
             if let Some(sp) = resolver.ast_map.span_if_local(did) {
                 err.span_note(sp, "constant defined here");
             }
-            if let Success(binding) = resolver.current_module.resolve_name(name, ValueNS, true) {
+            if let Some(binding) = resolver.current_module
+                                           .resolve_name_in_lexical_scope(name, ValueNS) {
                 if binding.is_import() {
                     err.span_note(binding.span.unwrap(), "constant imported here");
                 }
@@ -820,7 +821,7 @@ pub struct ModuleS<'a> {
     // entry block for `f`.
     module_children: RefCell<NodeMap<Module<'a>>>,
 
-    shadowed_traits: RefCell<Vec<&'a NameBinding<'a>>>,
+    prelude: RefCell<Option<Module<'a>>>,
 
     glob_importers: RefCell<Vec<(Module<'a>, &'a ImportDirective)>>,
     resolved_globs: RefCell<(Vec<Module<'a>> /* public */, Vec<Module<'a>> /* private */)>,
@@ -855,7 +856,7 @@ impl<'a> ModuleS<'a> {
             resolutions: RefCell::new(HashMap::new()),
             unresolved_imports: RefCell::new(Vec::new()),
             module_children: RefCell::new(NodeMap()),
-            shadowed_traits: RefCell::new(Vec::new()),
+            prelude: RefCell::new(None),
             glob_importers: RefCell::new(Vec::new()),
             resolved_globs: RefCell::new((Vec::new(), Vec::new())),
             public_glob_count: Cell::new(0),
@@ -932,8 +933,7 @@ bitflags! {
         // Variants are considered `PUBLIC`, but some of them live in private enums.
         // We need to track them to prohibit reexports like `pub use PrivEnum::Variant`.
         const PRIVATE_VARIANT = 1 << 2,
-        const PRELUDE = 1 << 3,
-        const GLOB_IMPORTED = 1 << 4,
+        const GLOB_IMPORTED = 1 << 3,
     }
 }
 
@@ -1537,13 +1537,17 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                               module: Module<'a>,
                               name: Name,
                               namespace: Namespace,
-                              allow_private_imports: bool,
+                              use_lexical_scope: bool,
                               record_used: bool)
                               -> ResolveResult<&'a NameBinding<'a>> {
         debug!("(resolving name in module) resolving `{}` in `{}`", name, module_to_string(module));
 
         build_reduced_graph::populate_module_if_necessary(self, module);
-        module.resolve_name(name, namespace, allow_private_imports).and_then(|binding| {
+        match use_lexical_scope {
+            true => module.resolve_name_in_lexical_scope(name, namespace)
+                          .map(Success).unwrap_or(Failed(None)),
+            false => module.resolve_name(name, namespace, false),
+        }.and_then(|binding| {
             if record_used {
                 self.record_use(name, namespace, binding);
             }
@@ -2962,7 +2966,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
             if name_path.len() == 1 {
                 match this.primitive_type_table.primitive_types.get(last_name) {
                     Some(_) => None,
-                    None => this.current_module.resolve_name(*last_name, TypeNS, true).success()
+                    None => this.current_module.resolve_name_in_lexical_scope(*last_name, TypeNS)
                                                .and_then(NameBinding::module)
                 }
             } else {
@@ -3019,7 +3023,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
         // Look for a method in the current self type's impl module.
         if let Some(module) = get_module(self, path.span, &name_path) {
-            if let Success(binding) = module.resolve_name(name, ValueNS, true) {
+            if let Some(binding) = module.resolve_name_in_lexical_scope(name, ValueNS) {
                 if let Some(Def::Method(did)) = binding.def() {
                     if is_static_method(self, did) {
                         return StaticMethod(path_names_to_string(&path, 0));
@@ -3336,33 +3340,25 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
             }
 
             // Look for trait children.
-            build_reduced_graph::populate_module_if_necessary(self, &search_module);
-
-            search_module.for_each_child(|_, ns, name_binding| {
+            let mut search_in_module = |module: Module<'a>| module.for_each_child(|_, ns, binding| {
                 if ns != TypeNS { return }
-                let trait_def_id = match name_binding.def() {
+                let trait_def_id = match binding.def() {
                     Some(Def::Trait(trait_def_id)) => trait_def_id,
                     Some(..) | None => return,
                 };
                 if self.trait_item_map.contains_key(&(name, trait_def_id)) {
                     add_trait_info(&mut found_traits, trait_def_id, name);
                     let trait_name = self.get_trait_name(trait_def_id);
-                    self.record_use(trait_name, TypeNS, name_binding);
-                }
-            });
-
-            // Look for shadowed traits.
-            for binding in search_module.shadowed_traits.borrow().iter() {
-                let did = binding.def().unwrap().def_id();
-                if self.trait_item_map.contains_key(&(name, did)) {
-                    add_trait_info(&mut found_traits, did, name);
-                    let trait_name = self.get_trait_name(did);
                     self.record_use(trait_name, TypeNS, binding);
                 }
-            }
+            });
+            search_in_module(search_module);
 
             match search_module.parent_link {
-                NoParentLink | ModuleParentLink(..) => break,
+                NoParentLink | ModuleParentLink(..) => {
+                    search_module.prelude.borrow().map(search_in_module);
+                    break;
+                }
                 BlockParentLink(parent_module, _) => {
                     search_module = parent_module;
                 }
diff --git a/src/librustc_resolve/resolve_imports.rs b/src/librustc_resolve/resolve_imports.rs
index 61e0add8602..3af5031cc47 100644
--- a/src/librustc_resolve/resolve_imports.rs
+++ b/src/librustc_resolve/resolve_imports.rs
@@ -57,13 +57,6 @@ impl ImportDirectiveSubclass {
     }
 }
 
-/// Whether an import can be shadowed by another import.
-#[derive(Debug,PartialEq,Clone,Copy)]
-pub enum Shadowable {
-    Always,
-    Never,
-}
-
 /// One import directive.
 #[derive(Debug,Clone)]
 pub struct ImportDirective {
@@ -72,7 +65,7 @@ pub struct ImportDirective {
     pub span: Span,
     pub id: NodeId,
     pub is_public: bool, // see note in ImportResolutionPerNamespace about how to use this
-    pub shadowable: Shadowable,
+    pub is_prelude: bool,
 }
 
 impl ImportDirective {
@@ -81,7 +74,7 @@ impl ImportDirective {
                span: Span,
                id: NodeId,
                is_public: bool,
-               shadowable: Shadowable)
+               is_prelude: bool)
                -> ImportDirective {
         ImportDirective {
             module_path: module_path,
@@ -89,7 +82,7 @@ impl ImportDirective {
             span: span,
             id: id,
             is_public: is_public,
-            shadowable: shadowable,
+            is_prelude: is_prelude,
         }
     }
 
@@ -105,9 +98,6 @@ impl ImportDirective {
         if let GlobImport = self.subclass {
             modifiers = modifiers | DefModifiers::GLOB_IMPORTED;
         }
-        if self.shadowable == Shadowable::Always {
-            modifiers = modifiers | DefModifiers::PRELUDE;
-        }
 
         NameBinding {
             kind: NameBindingKind::Import {
@@ -135,44 +125,36 @@ pub struct NameResolution<'a> {
 
 impl<'a> NameResolution<'a> {
     fn try_define(&mut self, binding: &'a NameBinding<'a>) -> Result<(), &'a NameBinding<'a>> {
-        match self.binding {
-            Some(old_binding) if !old_binding.defined_with(DefModifiers::PRELUDE) => {
-                if binding.defined_with(DefModifiers::GLOB_IMPORTED) {
-                    self.duplicate_globs.push(binding);
-                } else if old_binding.defined_with(DefModifiers::GLOB_IMPORTED) {
-                    self.duplicate_globs.push(old_binding);
-                    self.binding = Some(binding);
-                } else {
-                    return Err(old_binding);
-                }
+        if let Some(old_binding) = self.binding {
+            if binding.defined_with(DefModifiers::GLOB_IMPORTED) {
+                self.duplicate_globs.push(binding);
+            } else if old_binding.defined_with(DefModifiers::GLOB_IMPORTED) {
+                self.duplicate_globs.push(old_binding);
+                self.binding = Some(binding);
+            } else {
+                return Err(old_binding);
             }
-            _ => self.binding = Some(binding),
+        } else {
+            self.binding = Some(binding);
         }
 
         Ok(())
     }
 
-    // Returns the resolution of the name assuming no more globs will define it.
-    fn result(&self, allow_private_imports: bool) -> ResolveResult<&'a NameBinding<'a>> {
-        match self.binding {
-            Some(binding) if !binding.defined_with(DefModifiers::GLOB_IMPORTED) => Success(binding),
-            // If we don't allow private imports and no public imports can define the name, fail.
-            _ if !allow_private_imports && self.pub_outstanding_references == 0 &&
-                 !self.binding.map(NameBinding::is_public).unwrap_or(false) => Failed(None),
-            _ if self.outstanding_references > 0 => Indeterminate,
-            Some(binding) => Success(binding),
-            None => Failed(None),
-        }
-    }
-
     // Returns Some(the resolution of the name), or None if the resolution depends
     // on whether more globs can define the name.
     fn try_result(&self, allow_private_imports: bool)
                   -> Option<ResolveResult<&'a NameBinding<'a>>> {
-        match self.result(allow_private_imports) {
-            Success(binding) if binding.defined_with(DefModifiers::PRELUDE) => None,
-            Failed(_) => None,
-            result @ _ => Some(result),
+        match self.binding {
+            Some(binding) if !binding.defined_with(DefModifiers::GLOB_IMPORTED) =>
+                Some(Success(binding)),
+            // If (1) we don't allow private imports, (2) no public single import can define the
+            // name, and (3) no public glob has defined the name, the resolution depends on globs.
+            _ if !allow_private_imports && self.pub_outstanding_references == 0 &&
+                 !self.binding.map(NameBinding::is_public).unwrap_or(false) => None,
+            _ if self.outstanding_references > 0 => Some(Indeterminate),
+            Some(binding) => Some(Success(binding)),
+            None => None,
         }
     }
 
@@ -202,8 +184,6 @@ impl<'a> NameResolution<'a> {
         };
 
         for duplicate_glob in self.duplicate_globs.iter() {
-            if duplicate_glob.defined_with(DefModifiers::PRELUDE) { continue }
-
             // FIXME #31337: We currently allow items to shadow glob-imported re-exports.
             if !binding.is_import() {
                 if let NameBindingKind::Import { binding, .. } = duplicate_glob.kind {
@@ -259,7 +239,16 @@ impl<'a> ::ModuleS<'a> {
             }
         }
 
-        resolution.result(true)
+        Failed(None)
+    }
+
+    // Invariant: this may not be called until import resolution is complete.
+    pub fn resolve_name_in_lexical_scope(&self, name: Name, ns: Namespace)
+                                         -> Option<&'a NameBinding<'a>> {
+        self.resolutions.borrow().get(&(name, ns)).and_then(|resolution| resolution.binding)
+            .or_else(|| self.prelude.borrow().and_then(|prelude| {
+                prelude.resolve_name(name, ns, false).success()
+            }))
     }
 
     // Define the name or return the existing binding if there is a collision.
@@ -369,7 +358,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         // resolution for it so that later resolve stages won't complain.
         if let SingleImport { target, .. } = e.import_directive.subclass {
             let dummy_binding = self.resolver.arenas.alloc_name_binding(NameBinding {
-                modifiers: DefModifiers::PRELUDE,
+                modifiers: DefModifiers::GLOB_IMPORTED,
                 kind: NameBindingKind::Def(Def::Err),
                 span: None,
             });
@@ -623,6 +612,11 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         }
         build_reduced_graph::populate_module_if_necessary(self.resolver, target_module);
 
+        if directive.is_prelude {
+            *module_.prelude.borrow_mut() = Some(target_module);
+            return Success(());
+        }
+
         // Add to target_module's glob_importers and module_'s resolved_globs
         target_module.glob_importers.borrow_mut().push((module_, directive));
         match *module_.resolved_globs.borrow_mut() {
@@ -685,13 +679,6 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                     self.resolver.session.add_lint(lint, id, binding.span.unwrap(), msg);
                 }
             }
-
-            // We can always use methods from the prelude traits
-            for glob_binding in resolution.duplicate_globs.iter() {
-                if glob_binding.defined_with(DefModifiers::PRELUDE) {
-                    module.shadowed_traits.borrow_mut().push(glob_binding);
-                }
-            }
         }
 
         if reexports.len() > 0 {