Rollup merge of #30863 - jseyfried:no_rc, r=eddyb

Use arena allocation instead of reference counting for `Module`s to fix memory leaks from `Rc` cycles.

A module references its module children and its import resolutions, and an import resolution references the module defining the imported name, so there is a cycle whenever a module imports something from an ancestor module.

For example,
```rust
mod foo { // `foo` references `bar`.
    fn baz() {}
    mod bar { // `bar` references the import.
        use foo::baz; // The import references `foo`.
    }
}
```

5 files changed, 260 insertions, 245 deletions

diff --git a/mk/crates.mk b/mk/crates.mk
index 7542d91ce6d..be53234cb02 100644
--- a/mk/crates.mk
+++ b/mk/crates.mk
@@ -103,7 +103,7 @@ DEPS_rustc_lint := rustc log syntax
 DEPS_rustc_llvm := native:rustllvm libc std rustc_bitflags
 DEPS_rustc_metadata := rustc rustc_front syntax rbml
 DEPS_rustc_mir := rustc rustc_front syntax
-DEPS_rustc_resolve := rustc rustc_front log syntax
+DEPS_rustc_resolve := arena rustc rustc_front log syntax
 DEPS_rustc_platform_intrinsics := rustc rustc_llvm
 DEPS_rustc_plugin := rustc rustc_metadata syntax
 DEPS_rustc_privacy := rustc rustc_front log syntax
diff --git a/src/librustc_resolve/build_reduced_graph.rs b/src/librustc_resolve/build_reduced_graph.rs
index 8ed47300a17..2e713a2f50e 100644
--- a/src/librustc_resolve/build_reduced_graph.rs
+++ b/src/librustc_resolve/build_reduced_graph.rs
@@ -21,7 +21,7 @@ use Module;
 use Namespace::{TypeNS, ValueNS};
 use NameBindings;
 use {names_to_string, module_to_string};
-use ParentLink::{self, ModuleParentLink, BlockParentLink};
+use ParentLink::{ModuleParentLink, BlockParentLink};
 use Resolver;
 use resolve_imports::Shadowable;
 use {resolve_error, resolve_struct_error, ResolutionError};
@@ -52,7 +52,6 @@ use rustc_front::intravisit::{self, Visitor};
 
 use std::mem::replace;
 use std::ops::{Deref, DerefMut};
-use std::rc::Rc;
 
 // Specifies how duplicates should be handled when adding a child item if
 // another item exists with the same name in some namespace.
@@ -86,7 +85,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
     /// Constructs the reduced graph for the entire crate.
     fn build_reduced_graph(self, krate: &hir::Crate) {
         let mut visitor = BuildReducedGraphVisitor {
-            parent: self.graph_root.clone(),
+            parent: self.graph_root,
             builder: self,
         };
         intravisit::walk_crate(&mut visitor, krate);
@@ -97,12 +96,12 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
     /// Returns the child's corresponding name bindings.
     fn add_child(&self,
                  name: Name,
-                 parent: &Rc<Module>,
+                 parent: Module<'b>,
                  duplicate_checking_mode: DuplicateCheckingMode,
                  // For printing errors
                  sp: Span)
-                 -> NameBindings {
-        self.check_for_conflicts_between_external_crates_and_items(&**parent, name, sp);
+                 -> NameBindings<'b> {
+        self.check_for_conflicts_between_external_crates_and_items(parent, name, sp);
 
         // Add or reuse the child.
         let child = parent.children.borrow().get(&name).cloned();
@@ -178,12 +177,8 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
         return false;
     }
 
-    fn get_parent_link(&mut self, parent: &Rc<Module>, name: Name) -> ParentLink {
-        ModuleParentLink(Rc::downgrade(parent), name)
-    }
-
     /// Constructs the reduced graph for one item.
-    fn build_reduced_graph_for_item(&mut self, item: &Item, parent: &Rc<Module>) -> Rc<Module> {
+    fn build_reduced_graph_for_item(&mut self, item: &Item, parent: Module<'b>) -> Module<'b> {
         let name = item.name;
         let sp = item.span;
         let is_public = item.vis == hir::Public;
@@ -238,7 +233,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                         }
 
                         let subclass = SingleImport(binding, source_name);
-                        self.build_import_directive(&**parent,
+                        self.build_import_directive(parent,
                                                     module_path,
                                                     subclass,
                                                     view_path.span,
@@ -288,7 +283,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                     (module_path.to_vec(), name, rename)
                                 }
                             };
-                            self.build_import_directive(&**parent,
+                            self.build_import_directive(parent,
                                                         module_path,
                                                         SingleImport(rename, name),
                                                         source_item.span,
@@ -298,7 +293,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                         }
                     }
                     ViewPathGlob(_) => {
-                        self.build_import_directive(&**parent,
+                        self.build_import_directive(parent,
                                                     module_path,
                                                     GlobImport,
                                                     view_path.span,
@@ -307,7 +302,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                                     shadowable);
                     }
                 }
-                parent.clone()
+                parent
             }
 
             ItemExternCrate(_) => {
@@ -319,32 +314,32 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                         index: CRATE_DEF_INDEX,
                     };
                     self.external_exports.insert(def_id);
-                    let parent_link = ModuleParentLink(Rc::downgrade(parent), name);
+                    let parent_link = ModuleParentLink(parent, name);
                     let def = DefMod(def_id);
-                    let external_module = Module::new(parent_link, Some(def), false, true);
+                    let external_module = self.new_module(parent_link, Some(def), false, true);
 
                     debug!("(build reduced graph for item) found extern `{}`",
                            module_to_string(&*external_module));
-                    self.check_for_conflicts_for_external_crate(&parent, name, sp);
+                    self.check_for_conflicts_for_external_crate(parent, name, sp);
                     parent.external_module_children
                           .borrow_mut()
-                          .insert(name, external_module.clone());
+                          .insert(name, external_module);
                     self.build_reduced_graph_for_external_crate(&external_module);
                 }
-                parent.clone()
+                parent
             }
 
             ItemMod(..) => {
                 let name_bindings = self.add_child(name, parent, ForbidDuplicateTypes, sp);
 
-                let parent_link = self.get_parent_link(parent, name);
+                let parent_link = ModuleParentLink(parent, name);
                 let def = DefMod(self.ast_map.local_def_id(item.id));
-                let module = Module::new(parent_link, Some(def), false, is_public);
+                let module = self.new_module(parent_link, Some(def), false, is_public);
                 name_bindings.define_module(module.clone(), sp);
                 module
             }
 
-            ItemForeignMod(..) => parent.clone(),
+            ItemForeignMod(..) => parent,
 
             // These items live in the value namespace.
             ItemStatic(_, m, _) => {
@@ -354,19 +349,19 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 name_bindings.define_value(DefStatic(self.ast_map.local_def_id(item.id), mutbl),
                                            sp,
                                            modifiers);
-                parent.clone()
+                parent
             }
             ItemConst(_, _) => {
                 self.add_child(name, parent, ForbidDuplicateValues, sp)
                     .define_value(DefConst(self.ast_map.local_def_id(item.id)), sp, modifiers);
-                parent.clone()
+                parent
             }
             ItemFn(_, _, _, _, _, _) => {
                 let name_bindings = self.add_child(name, parent, ForbidDuplicateValues, sp);
 
                 let def = DefFn(self.ast_map.local_def_id(item.id), false);
                 name_bindings.define_value(def, sp, modifiers);
-                parent.clone()
+                parent
             }
 
             // These items live in the type namespace.
@@ -376,11 +371,11 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                                    ForbidDuplicateTypes,
                                                    sp);
 
-                let parent_link = self.get_parent_link(parent, name);
+                let parent_link = ModuleParentLink(parent, name);
                 let def = DefTy(self.ast_map.local_def_id(item.id), false);
-                let module = Module::new(parent_link, Some(def), false, is_public);
+                let module = self.new_module(parent_link, Some(def), false, is_public);
                 name_bindings.define_module(module, sp);
-                parent.clone()
+                parent
             }
 
             ItemEnum(ref enum_definition, _) => {
@@ -389,9 +384,9 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                                                    ForbidDuplicateTypes,
                                                    sp);
 
-                let parent_link = self.get_parent_link(parent, name);
+                let parent_link = ModuleParentLink(parent, name);
                 let def = DefTy(self.ast_map.local_def_id(item.id), true);
-                let module = Module::new(parent_link, Some(def), false, is_public);
+                let module = self.new_module(parent_link, Some(def), false, is_public);
                 name_bindings.define_module(module.clone(), sp);
 
                 let variant_modifiers = if is_public {
@@ -404,7 +399,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                     self.build_reduced_graph_for_variant(variant, item_def_id,
                                                          &module, variant_modifiers);
                 }
-                parent.clone()
+                parent
             }
 
             // These items live in both the type and value namespaces.
@@ -444,11 +439,11 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 let item_def_id = self.ast_map.local_def_id(item.id);
                 self.structs.insert(item_def_id, named_fields);
 
-                parent.clone()
+                parent
             }
 
             ItemDefaultImpl(_, _) |
-            ItemImpl(..) => parent.clone(),
+            ItemImpl(..) => parent,
 
             ItemTrait(_, _, _, ref items) => {
                 let name_bindings = self.add_child(name,
@@ -459,9 +454,9 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 let def_id = self.ast_map.local_def_id(item.id);
 
                 // Add all the items within to a new module.
-                let parent_link = self.get_parent_link(parent, name);
+                let parent_link = ModuleParentLink(parent, name);
                 let def = DefTrait(def_id);
-                let module_parent = Module::new(parent_link, Some(def), false, is_public);
+                let module_parent = self.new_module(parent_link, Some(def), false, is_public);
                 name_bindings.define_module(module_parent.clone(), sp);
 
                 // Add the names of all the items to the trait info.
@@ -494,7 +489,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                     self.trait_item_map.insert((trait_item.name, def_id), trait_item_def_id);
                 }
 
-                parent.clone()
+                parent
             }
         }
     }
@@ -504,7 +499,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
     fn build_reduced_graph_for_variant(&mut self,
                                        variant: &Variant,
                                        item_id: DefId,
-                                       parent: &Rc<Module>,
+                                       parent: Module<'b>,
                                        variant_modifiers: DefModifiers) {
         let name = variant.node.name;
         let is_exported = if variant.node.data.is_struct() {
@@ -534,7 +529,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
     /// Constructs the reduced graph for one foreign item.
     fn build_reduced_graph_for_foreign_item(&mut self,
                                             foreign_item: &ForeignItem,
-                                            parent: &Rc<Module>) {
+                                            parent: Module<'b>) {
         let name = foreign_item.name;
         let is_public = foreign_item.vis == hir::Public;
         let modifiers = if is_public {
@@ -555,7 +550,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
         name_bindings.define_value(def, foreign_item.span, modifiers);
     }
 
-    fn build_reduced_graph_for_block(&mut self, block: &Block, parent: &Rc<Module>) -> Rc<Module> {
+    fn build_reduced_graph_for_block(&mut self, block: &Block, parent: Module<'b>) -> Module<'b> {
         if self.block_needs_anonymous_module(block) {
             let block_id = block.id;
 
@@ -563,22 +558,22 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                     {}",
                    block_id);
 
-            let parent_link = BlockParentLink(Rc::downgrade(parent), block_id);
-            let new_module = Module::new(parent_link, None, false, false);
-            parent.anonymous_children.borrow_mut().insert(block_id, new_module.clone());
+            let parent_link = BlockParentLink(parent, block_id);
+            let new_module = self.new_module(parent_link, None, false, false);
+            parent.anonymous_children.borrow_mut().insert(block_id, new_module);
             new_module
         } else {
-            parent.clone()
+            parent
         }
     }
 
     fn handle_external_def(&mut self,
                            def: Def,
                            vis: Visibility,
-                           child_name_bindings: &NameBindings,
+                           child_name_bindings: &NameBindings<'b>,
                            final_ident: &str,
                            name: Name,
-                           new_parent: &Rc<Module>) {
+                           new_parent: Module<'b>) {
         debug!("(building reduced graph for external crate) building external def {}, priv {:?}",
                final_ident,
                vis);
@@ -609,8 +604,8 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                     debug!("(building reduced graph for external crate) building module {} {}",
                            final_ident,
                            is_public);
-                    let parent_link = self.get_parent_link(new_parent, name);
-                    let module = Module::new(parent_link, Some(def), true, is_public);
+                    let parent_link = ModuleParentLink(new_parent, name);
+                    let module = self.new_module(parent_link, Some(def), true, is_public);
                     child_name_bindings.define_module(module, DUMMY_SP);
                 }
             }
@@ -681,8 +676,8 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
                 }
 
                 // Define a module if necessary.
-                let parent_link = self.get_parent_link(new_parent, name);
-                let module = Module::new(parent_link, Some(def), true, is_public);
+                let parent_link = ModuleParentLink(new_parent, name);
+                let module = self.new_module(parent_link, Some(def), true, is_public);
                 child_name_bindings.define_module(module, DUMMY_SP);
             }
             DefTy(..) | DefAssociatedTy(..) => {
@@ -728,7 +723,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
 
     /// Builds the reduced graph for a single item in an external crate.
     fn build_reduced_graph_for_external_crate_def(&mut self,
-                                                  root: &Rc<Module>,
+                                                  root: Module<'b>,
                                                   xcdef: ChildItem) {
         match xcdef.def {
             DlDef(def) => {
@@ -766,9 +761,9 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
     }
 
     /// Builds the reduced graph rooted at the given external module.
-    fn populate_external_module(&mut self, module: &Rc<Module>) {
+    fn populate_external_module(&mut self, module: Module<'b>) {
         debug!("(populating external module) attempting to populate {}",
-               module_to_string(&**module));
+               module_to_string(module));
 
         let def_id = match module.def_id() {
             None => {
@@ -788,7 +783,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
 
     /// Ensures that the reduced graph rooted at the given external module
     /// is built, building it if it is not.
-    fn populate_module_if_necessary(&mut self, module: &Rc<Module>) {
+    fn populate_module_if_necessary(&mut self, module: Module<'b>) {
         if !module.populated.get() {
             self.populate_external_module(module)
         }
@@ -797,7 +792,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
 
     /// Builds the reduced graph rooted at the 'use' directive for an external
     /// crate.
-    fn build_reduced_graph_for_external_crate(&mut self, root: &Rc<Module>) {
+    fn build_reduced_graph_for_external_crate(&mut self, root: Module<'b>) {
         let root_cnum = root.def_id().unwrap().krate;
         for child in self.session.cstore.crate_top_level_items(root_cnum) {
             self.build_reduced_graph_for_external_crate_def(root, child);
@@ -806,7 +801,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
 
     /// Creates and adds an import directive to the given module.
     fn build_import_directive(&mut self,
-                              module_: &Module,
+                              module_: Module<'b>,
                               module_path: Vec<Name>,
                               subclass: ImportDirectiveSubclass,
                               span: Span,
@@ -866,7 +861,7 @@ impl<'a, 'b:'a, 'tcx:'b> GraphBuilder<'a, 'b, 'tcx> {
 
 struct BuildReducedGraphVisitor<'a, 'b: 'a, 'tcx: 'b> {
     builder: GraphBuilder<'a, 'b, 'tcx>,
-    parent: Rc<Module>,
+    parent: Module<'b>,
 }
 
 impl<'a, 'b, 'v, 'tcx> Visitor<'v> for BuildReducedGraphVisitor<'a, 'b, 'tcx> {
@@ -897,6 +892,7 @@ pub fn build_reduced_graph(resolver: &mut Resolver, krate: &hir::Crate) {
     GraphBuilder { resolver: resolver }.build_reduced_graph(krate);
 }
 
-pub fn populate_module_if_necessary(resolver: &mut Resolver, module: &Rc<Module>) {
+pub fn populate_module_if_necessary<'a, 'tcx>(resolver: &mut Resolver<'a, 'tcx>,
+                                              module: Module<'a>) {
     GraphBuilder { resolver: resolver }.populate_module_if_necessary(module);
 }
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index c7031f72af4..9857e83bd62 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -26,6 +26,7 @@
 extern crate log;
 #[macro_use]
 extern crate syntax;
+extern crate arena;
 #[macro_use]
 #[no_link]
 extern crate rustc_bitflags;
@@ -90,7 +91,7 @@ use std::collections::{HashMap, HashSet};
 use std::cell::{Cell, RefCell};
 use std::fmt;
 use std::mem::replace;
-use std::rc::{Rc, Weak};
+use std::rc::Rc;
 
 use resolve_imports::{Target, ImportDirective, ImportResolutionPerNamespace};
 use resolve_imports::Shadowable;
@@ -576,7 +577,7 @@ pub enum Namespace {
 /// a particular namespace. The result is either definitely-resolved,
 /// definitely- unresolved, or unknown.
 #[derive(Clone)]
-enum NamespaceResult {
+enum NamespaceResult<'a> {
     /// Means that resolve hasn't gathered enough information yet to determine
     /// whether the name is bound in this namespace. (That is, it hasn't
     /// resolved all `use` directives yet.)
@@ -586,10 +587,10 @@ enum NamespaceResult {
     UnboundResult,
     /// Means that resolve has determined that the name is bound in the Module
     /// argument, and specified by the NameBinding argument.
-    BoundResult(Rc<Module>, NameBinding),
+    BoundResult(Module<'a>, NameBinding<'a>),
 }
 
-impl NamespaceResult {
+impl<'a> NamespaceResult<'a> {
     fn is_unknown(&self) -> bool {
         match *self {
             UnknownResult => true,
@@ -766,9 +767,9 @@ enum UseLexicalScopeFlag {
     UseLexicalScope,
 }
 
-enum ModulePrefixResult {
+enum ModulePrefixResult<'a> {
     NoPrefixFound,
-    PrefixFound(Rc<Module>, usize),
+    PrefixFound(Module<'a>, usize),
 }
 
 #[derive(Copy, Clone)]
@@ -830,24 +831,24 @@ impl LocalDef {
 
 /// The link from a module up to its nearest parent node.
 #[derive(Clone,Debug)]
-enum ParentLink {
+enum ParentLink<'a> {
     NoParentLink,
-    ModuleParentLink(Weak<Module>, Name),
-    BlockParentLink(Weak<Module>, NodeId),
+    ModuleParentLink(Module<'a>, Name),
+    BlockParentLink(Module<'a>, NodeId),
 }
 
 /// One node in the tree of modules.
-pub struct Module {
-    parent_link: ParentLink,
+pub struct ModuleS<'a> {
+    parent_link: ParentLink<'a>,
     def: Cell<Option<Def>>,
     is_public: bool,
 
-    children: RefCell<HashMap<Name, NameBindings>>,
+    children: RefCell<HashMap<Name, NameBindings<'a>>>,
     imports: RefCell<Vec<ImportDirective>>,
 
     // The external module children of this node that were declared with
     // `extern crate`.
-    external_module_children: RefCell<HashMap<Name, Rc<Module>>>,
+    external_module_children: RefCell<HashMap<Name, Module<'a>>>,
 
     // The anonymous children of this node. Anonymous children are pseudo-
     // modules that are implicitly created around items contained within
@@ -863,10 +864,10 @@ pub struct Module {
     //
     // There will be an anonymous module created around `g` with the ID of the
     // entry block for `f`.
-    anonymous_children: RefCell<NodeMap<Rc<Module>>>,
+    anonymous_children: RefCell<NodeMap<Module<'a>>>,
 
     // The status of resolving each import in this module.
-    import_resolutions: RefCell<HashMap<Name, ImportResolutionPerNamespace>>,
+    import_resolutions: RefCell<HashMap<Name, ImportResolutionPerNamespace<'a>>>,
 
     // The number of unresolved globs that this module exports.
     glob_count: Cell<usize>,
@@ -886,13 +887,11 @@ pub struct Module {
     populated: Cell<bool>,
 }
 
-impl Module {
-    fn new(parent_link: ParentLink,
-           def: Option<Def>,
-           external: bool,
-           is_public: bool)
-           -> Rc<Module> {
-        Rc::new(Module {
+pub type Module<'a> = &'a ModuleS<'a>;
+
+impl<'a> ModuleS<'a> {
+    fn new(parent_link: ParentLink<'a>, def: Option<Def>, external: bool, is_public: bool) -> Self {
+        ModuleS {
             parent_link: parent_link,
             def: Cell::new(def),
             is_public: is_public,
@@ -906,7 +905,7 @@ impl Module {
             pub_glob_count: Cell::new(0),
             resolved_import_count: Cell::new(0),
             populated: Cell::new(!external),
-        })
+        }
     }
 
     fn def_id(&self) -> Option<DefId> {
@@ -935,9 +934,7 @@ impl Module {
             self.imports.borrow().len() == self.resolved_import_count.get()
         }
     }
-}
 
-impl Module {
     pub fn inc_glob_count(&self) {
         self.glob_count.set(self.glob_count.get() + 1);
     }
@@ -961,7 +958,7 @@ impl Module {
     }
 }
 
-impl fmt::Debug for Module {
+impl<'a> fmt::Debug for ModuleS<'a> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f,
                "{:?}, {}",
@@ -989,20 +986,20 @@ bitflags! {
 
 // Records a possibly-private value, type, or module definition.
 #[derive(Debug)]
-struct NsDef {
+struct NsDef<'a> {
     modifiers: DefModifiers, // see note in ImportResolutionPerNamespace about how to use this
-    def_or_module: DefOrModule,
+    def_or_module: DefOrModule<'a>,
     span: Option<Span>,
 }
 
 #[derive(Debug)]
-enum DefOrModule {
+enum DefOrModule<'a> {
     Def(Def),
-    Module(Rc<Module>),
+    Module(Module<'a>),
 }
 
-impl NsDef {
-    fn create_from_module(module: Rc<Module>, span: Option<Span>) -> Self {
+impl<'a> NsDef<'a> {
+    fn create_from_module(module: Module<'a>, span: Option<Span>) -> Self {
         let modifiers = if module.is_public {
             DefModifiers::PUBLIC
         } else {
@@ -1016,9 +1013,9 @@ impl NsDef {
         NsDef { modifiers: modifiers, def_or_module: DefOrModule::Def(def), span: span }
     }
 
-    fn module(&self) -> Option<Rc<Module>> {
+    fn module(&self) -> Option<Module<'a>> {
         match self.def_or_module {
-            DefOrModule::Module(ref module) => Some(module.clone()),
+            DefOrModule::Module(ref module) => Some(module),
             DefOrModule::Def(_) => None,
         }
     }
@@ -1033,18 +1030,18 @@ impl NsDef {
 
 // Records at most one definition that a name in a namespace is bound to
 #[derive(Clone,Debug)]
-pub struct NameBinding(Rc<RefCell<Option<NsDef>>>);
+pub struct NameBinding<'a>(Rc<RefCell<Option<NsDef<'a>>>>);
 
-impl NameBinding {
+impl<'a> NameBinding<'a> {
     fn new() -> Self {
         NameBinding(Rc::new(RefCell::new(None)))
     }
 
-    fn create_from_module(module: Rc<Module>) -> Self {
+    fn create_from_module(module: Module<'a>) -> Self {
         NameBinding(Rc::new(RefCell::new(Some(NsDef::create_from_module(module, None)))))
     }
 
-    fn set(&self, ns_def: NsDef) {
+    fn set(&self, ns_def: NsDef<'a>) {
         *self.0.borrow_mut() = Some(ns_def);
     }
 
@@ -1054,7 +1051,7 @@ impl NameBinding {
         }
     }
 
-    fn borrow(&self) -> ::std::cell::Ref<Option<NsDef>> {
+    fn borrow(&self) -> ::std::cell::Ref<Option<NsDef<'a>>> {
         self.0.borrow()
     }
 
@@ -1062,7 +1059,7 @@ impl NameBinding {
     fn def(&self) -> Option<Def> {
         self.borrow().as_ref().and_then(NsDef::def)
     }
-    fn module(&self) -> Option<Rc<Module>> {
+    fn module(&self) -> Option<Module<'a>> {
         self.borrow().as_ref().and_then(NsDef::module)
     }
     fn span(&self) -> Option<Span> {
@@ -1093,20 +1090,20 @@ impl NameBinding {
 // Records the definitions (at most one for each namespace) that a name is
 // bound to.
 #[derive(Clone,Debug)]
-pub struct NameBindings {
-    type_ns: NameBinding, // < Meaning in type namespace.
-    value_ns: NameBinding, // < Meaning in value namespace.
+pub struct NameBindings<'a> {
+    type_ns: NameBinding<'a>, // < Meaning in type namespace.
+    value_ns: NameBinding<'a>, // < Meaning in value namespace.
 }
 
-impl ::std::ops::Index<Namespace> for NameBindings {
-    type Output = NameBinding;
-    fn index(&self, namespace: Namespace) -> &NameBinding {
+impl<'a> ::std::ops::Index<Namespace> for NameBindings<'a> {
+    type Output = NameBinding<'a>;
+    fn index(&self, namespace: Namespace) -> &NameBinding<'a> {
         match namespace { TypeNS => &self.type_ns, ValueNS => &self.value_ns }
     }
 }
 
-impl NameBindings {
-    fn new() -> NameBindings {
+impl<'a> NameBindings<'a> {
+    fn new() -> Self {
         NameBindings {
             type_ns: NameBinding::new(),
             value_ns: NameBinding::new(),
@@ -1114,7 +1111,7 @@ impl NameBindings {
     }
 
     /// Creates a new module in this set of name bindings.
-    fn define_module(&self, module: Rc<Module>, sp: Span) {
+    fn define_module(&self, module: Module<'a>, sp: Span) {
         self.type_ns.set(NsDef::create_from_module(module, Some(sp)));
     }
 
@@ -1170,7 +1167,7 @@ pub struct Resolver<'a, 'tcx: 'a> {
 
     ast_map: &'a hir_map::Map<'tcx>,
 
-    graph_root: Rc<Module>,
+    graph_root: Module<'a>,
 
     trait_item_map: FnvHashMap<(Name, DefId), DefId>,
 
@@ -1180,7 +1177,7 @@ pub struct Resolver<'a, 'tcx: 'a> {
     unresolved_imports: usize,
 
     // The module that represents the current item scope.
-    current_module: Rc<Module>,
+    current_module: Module<'a>,
 
     // The current set of local scopes, for values.
     // FIXME #4948: Reuse ribs to avoid allocation.
@@ -1226,6 +1223,12 @@ pub struct Resolver<'a, 'tcx: 'a> {
     // The intention is that the callback modifies this flag.
     // Once set, the resolver falls out of the walk, preserving the ribs.
     resolved: bool,
+
+    arenas: &'a ResolverArenas<'a>,
+}
+
+pub struct ResolverArenas<'a> {
+    modules: arena::TypedArena<ModuleS<'a>>,
 }
 
 #[derive(PartialEq)]
@@ -1237,10 +1240,12 @@ enum FallbackChecks {
 impl<'a, 'tcx> Resolver<'a, 'tcx> {
     fn new(session: &'a Session,
            ast_map: &'a hir_map::Map<'tcx>,
-           make_glob_map: MakeGlobMap)
+           make_glob_map: MakeGlobMap,
+           arenas: &'a ResolverArenas<'a>)
            -> Resolver<'a, 'tcx> {
         let root_def_id = ast_map.local_def_id(CRATE_NODE_ID);
-        let graph_root = Module::new(NoParentLink, Some(DefMod(root_def_id)), false, true);
+        let graph_root = ModuleS::new(NoParentLink, Some(DefMod(root_def_id)), false, true);
+        let graph_root = arenas.modules.alloc(graph_root);
 
         Resolver {
             session: session,
@@ -1249,7 +1254,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
             // The outermost module has def ID 0; this is not reflected in the
             // AST.
-            graph_root: graph_root.clone(),
+            graph_root: graph_root,
 
             trait_item_map: FnvHashMap(),
             structs: FnvHashMap(),
@@ -1281,9 +1286,25 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
             callback: None,
             resolved: false,
+
+            arenas: arenas,
+        }
+    }
+
+    fn arenas() -> ResolverArenas<'a> {
+        ResolverArenas {
+            modules: arena::TypedArena::new(),
         }
     }
 
+    fn new_module(&self,
+                  parent_link: ParentLink<'a>,
+                  def: Option<Def>,
+                  external: bool,
+                  is_public: bool) -> Module<'a> {
+        self.arenas.modules.alloc(ModuleS::new(parent_link, def, external, is_public))
+    }
+
     #[inline]
     fn record_import_use(&mut self, import_id: NodeId, name: Name) {
         if !self.make_glob_map {
@@ -1308,7 +1329,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     }
 
     /// Check that an external crate doesn't collide with items or other external crates.
-    fn check_for_conflicts_for_external_crate(&self, module: &Module, name: Name, span: Span) {
+    fn check_for_conflicts_for_external_crate(&self, module: Module<'a>, name: Name, span: Span) {
         if module.external_module_children.borrow().contains_key(&name) {
             span_err!(self.session,
                       span,
@@ -1328,7 +1349,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
     /// Checks that the names of items don't collide with external crates.
     fn check_for_conflicts_between_external_crates_and_items(&self,
-                                                             module: &Module,
+                                                             module: Module<'a>,
                                                              name: Name,
                                                              span: Span) {
         if module.external_module_children.borrow().contains_key(&name) {
@@ -1338,19 +1359,20 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
     /// Resolves the given module path from the given root `module_`.
     fn resolve_module_path_from_root(&mut self,
-                                     module_: Rc<Module>,
+                                     module_: Module<'a>,
                                      module_path: &[Name],
                                      index: usize,
                                      span: Span,
                                      name_search_type: NameSearchType,
                                      lp: LastPrivate)
-                                     -> ResolveResult<(Rc<Module>, LastPrivate)> {
-        fn search_parent_externals(needle: Name, module: &Rc<Module>) -> Option<Rc<Module>> {
+                                     -> ResolveResult<(Module<'a>, LastPrivate)> {
+        fn search_parent_externals<'a>(needle: Name, module: Module<'a>)
+                                       -> Option<Module<'a>> {
             match module.external_module_children.borrow().get(&needle) {
-                Some(_) => Some(module.clone()),
+                Some(_) => Some(module),
                 None => match module.parent_link {
                     ModuleParentLink(ref parent, _) => {
-                        search_parent_externals(needle, &parent.upgrade().unwrap())
+                        search_parent_externals(needle, parent)
                     }
                     _ => None,
                 },
@@ -1367,14 +1389,14 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         // modules as we go.
         while index < module_path_len {
             let name = module_path[index];
-            match self.resolve_name_in_module(search_module.clone(),
+            match self.resolve_name_in_module(search_module,
                                               name,
                                               TypeNS,
                                               name_search_type,
                                               false) {
                 Failed(None) => {
                     let segment_name = name.as_str();
-                    let module_name = module_to_string(&*search_module);
+                    let module_name = module_to_string(search_module);
                     let mut span = span;
                     let msg = if "???" == &module_name[..] {
                         span.hi = span.lo + Pos::from_usize(segment_name.len());
@@ -1445,12 +1467,12 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     /// On success, returns the resolved module, and the closest *private*
     /// module found to the destination when resolving this path.
     fn resolve_module_path(&mut self,
-                           module_: Rc<Module>,
+                           module_: Module<'a>,
                            module_path: &[Name],
                            use_lexical_scope: UseLexicalScopeFlag,
                            span: Span,
                            name_search_type: NameSearchType)
-                           -> ResolveResult<(Rc<Module>, LastPrivate)> {
+                           -> ResolveResult<(Module<'a>, LastPrivate)> {
         let module_path_len = module_path.len();
         assert!(module_path_len > 0);
 
@@ -1459,7 +1481,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                module_to_string(&*module_));
 
         // Resolve the module prefix, if any.
-        let module_prefix_result = self.resolve_module_prefix(module_.clone(), module_path);
+        let module_prefix_result = self.resolve_module_prefix(module_, module_path);
 
         let search_module;
         let start_index;
@@ -1495,7 +1517,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                     DontUseLexicalScope => {
                         // This is a crate-relative path. We will start the
                         // resolution process at index zero.
-                        search_module = self.graph_root.clone();
+                        search_module = self.graph_root;
                         start_index = 0;
                         last_private = LastMod(AllPublic);
                     }
@@ -1519,7 +1541,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 }
             }
             Success(PrefixFound(ref containing_module, index)) => {
-                search_module = containing_module.clone();
+                search_module = containing_module;
                 start_index = index;
                 last_private = LastMod(DependsOn(containing_module.def_id()
                                                                   .unwrap()));
@@ -1537,11 +1559,11 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     /// Invariant: This must only be called during main resolution, not during
     /// import resolution.
     fn resolve_item_in_lexical_scope(&mut self,
-                                     module_: Rc<Module>,
+                                     module_: Module<'a>,
                                      name: Name,
                                      namespace: Namespace,
                                      record_used: bool)
-                                     -> ResolveResult<(Target, bool)> {
+                                     -> ResolveResult<(Target<'a>, bool)> {
         debug!("(resolving item in lexical scope) resolving `{}` in namespace {:?} in `{}`",
                name,
                namespace,
@@ -1554,7 +1576,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         match module_.children.borrow().get(&name) {
             Some(name_bindings) if name_bindings[namespace].defined() => {
                 debug!("top name bindings succeeded");
-                return Success((Target::new(module_.clone(),
+                return Success((Target::new(module_,
                                             name_bindings[namespace].clone(),
                                             Shadowable::Never),
                                 false));
@@ -1594,9 +1616,8 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
         // Search for external modules.
         if namespace == TypeNS {
-            // FIXME (21114): In principle unclear `child` *has* to be lifted.
-            let child = module_.external_module_children.borrow().get(&name).cloned();
-            if let Some(module) = child {
+            let children = module_.external_module_children.borrow();
+            if let Some(module) = children.get(&name) {
                 let name_binding = NameBinding::create_from_module(module);
                 debug!("lower name bindings succeeded");
                 return Success((Target::new(module_, name_binding, Shadowable::Never),
@@ -1608,7 +1629,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         let mut search_module = module_;
         loop {
             // Go to the next parent.
-            match search_module.parent_link.clone() {
+            match search_module.parent_link {
                 NoParentLink => {
                     // No more parents. This module was unresolved.
                     debug!("(resolving item in lexical scope) unresolved module");
@@ -1621,16 +1642,16 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                 searching through module parents");
                             return Failed(None);
                     } else {
-                        search_module = parent_module_node.upgrade().unwrap();
+                        search_module = parent_module_node;
                     }
                 }
-                BlockParentLink(ref parent_module_node, _) => {
-                    search_module = parent_module_node.upgrade().unwrap();
+                BlockParentLink(parent_module_node, _) => {
+                    search_module = parent_module_node;
                 }
             }
 
             // Resolve the name in the parent module.
-            match self.resolve_name_in_module(search_module.clone(),
+            match self.resolve_name_in_module(search_module,
                                               name,
                                               namespace,
                                               PathSearch,
@@ -1657,9 +1678,9 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
     /// Resolves a module name in the current lexical scope.
     fn resolve_module_in_lexical_scope(&mut self,
-                                       module_: Rc<Module>,
+                                       module_: Module<'a>,
                                        name: Name)
-                                       -> ResolveResult<Rc<Module>> {
+                                       -> ResolveResult<Module<'a>> {
         // If this module is an anonymous module, resolve the item in the
         // lexical scope. Otherwise, resolve the item from the crate root.
         let resolve_result = self.resolve_item_in_lexical_scope(module_, name, TypeNS, true);
@@ -1685,14 +1706,14 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     }
 
     /// Returns the nearest normal module parent of the given module.
-    fn get_nearest_normal_module_parent(&mut self, module_: Rc<Module>) -> Option<Rc<Module>> {
+    fn get_nearest_normal_module_parent(&mut self, module_: Module<'a>) -> Option<Module<'a>> {
         let mut module_ = module_;
         loop {
-            match module_.parent_link.clone() {
+            match module_.parent_link {
                 NoParentLink => return None,
                 ModuleParentLink(new_module, _) |
                 BlockParentLink(new_module, _) => {
-                    let new_module = new_module.upgrade().unwrap();
+                    let new_module = new_module;
                     if new_module.is_normal() {
                         return Some(new_module);
                     }
@@ -1704,11 +1725,11 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
     /// Returns the nearest normal module parent of the given module, or the
     /// module itself if it is a normal module.
-    fn get_nearest_normal_module_parent_or_self(&mut self, module_: Rc<Module>) -> Rc<Module> {
+    fn get_nearest_normal_module_parent_or_self(&mut self, module_: Module<'a>) -> Module<'a> {
         if module_.is_normal() {
             return module_;
         }
-        match self.get_nearest_normal_module_parent(module_.clone()) {
+        match self.get_nearest_normal_module_parent(module_) {
             None => module_,
             Some(new_module) => new_module,
         }
@@ -1718,9 +1739,9 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     /// (b) some chain of `super::`.
     /// grammar: (SELF MOD_SEP ) ? (SUPER MOD_SEP) *
     fn resolve_module_prefix(&mut self,
-                             module_: Rc<Module>,
+                             module_: Module<'a>,
                              module_path: &[Name])
-                             -> ResolveResult<ModulePrefixResult> {
+                             -> ResolveResult<ModulePrefixResult<'a>> {
         // Start at the current module if we see `self` or `super`, or at the
         // top of the crate otherwise.
         let mut i = match &*module_path[0].as_str() {
@@ -1756,12 +1777,12 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     /// The boolean returned on success is an indicator of whether this lookup
     /// passed through a public re-export proxy.
     fn resolve_name_in_module(&mut self,
-                              module_: Rc<Module>,
+                              module_: Module<'a>,
                               name: Name,
                               namespace: Namespace,
                               name_search_type: NameSearchType,
                               allow_private_imports: bool)
-                              -> ResolveResult<(Target, bool)> {
+                              -> ResolveResult<(Target<'a>, bool)> {
         debug!("(resolving name in module) resolving `{}` in `{}`",
                name,
                module_to_string(&*module_));
@@ -1769,10 +1790,11 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         // First, check the direct children of the module.
         build_reduced_graph::populate_module_if_necessary(self, &module_);
 
-        match module_.children.borrow().get(&name) {
+        let children = module_.children.borrow();
+        match children.get(&name) {
             Some(name_bindings) if name_bindings[namespace].defined() => {
                 debug!("(resolving name in module) found node as child");
-                return Success((Target::new(module_.clone(),
+                return Success((Target::new(module_,
                                             name_bindings[namespace].clone(),
                                             Shadowable::Never),
                                 false));
@@ -1791,7 +1813,8 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         }
 
         // Check the list of resolved imports.
-        match module_.import_resolutions.borrow().get(&name) {
+        let children = module_.import_resolutions.borrow();
+        match children.get(&name) {
             Some(import_resolution) if allow_private_imports ||
                                        import_resolution[namespace].is_public => {
 
@@ -1823,9 +1846,8 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
         // Finally, search through external children.
         if namespace == TypeNS {
-            // FIXME (21114): In principle unclear `child` *has* to be lifted.
-            let child = module_.external_module_children.borrow().get(&name).cloned();
-            if let Some(module) = child {
+            let children = module_.external_module_children.borrow();
+            if let Some(module) = children.get(&name) {
                 let name_binding = NameBinding::create_from_module(module);
                 return Success((Target::new(module_, name_binding, Shadowable::Never),
                                 false));
@@ -1837,7 +1859,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         return Failed(None);
     }
 
-    fn report_unresolved_imports(&mut self, module_: Rc<Module>) {
+    fn report_unresolved_imports(&mut self, module_: Module<'a>) {
         let index = module_.resolved_import_count.get();
         let imports = module_.imports.borrow();
         let import_count = imports.len();
@@ -1862,7 +1884,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         }
 
         for (_, module_) in module_.anonymous_children.borrow().iter() {
-            self.report_unresolved_imports(module_.clone());
+            self.report_unresolved_imports(module_);
         }
     }
 
@@ -1887,7 +1909,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     fn with_scope<F>(&mut self, name: Option<Name>, f: F)
         where F: FnOnce(&mut Resolver)
     {
-        let orig_module = self.current_module.clone();
+        let orig_module = self.current_module;
 
         // Move down in the graph.
         match name {
@@ -2475,14 +2497,14 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         self.value_ribs.push(Rib::new(NormalRibKind));
 
         // Move down in the graph, if there's an anonymous module rooted here.
-        let orig_module = self.current_module.clone();
+        let orig_module = self.current_module;
         match orig_module.anonymous_children.borrow().get(&block.id) {
             None => {
                 // Nothing to do.
             }
             Some(anonymous_module) => {
                 debug!("(resolving block) found anonymous module, moving down");
-                self.current_module = anonymous_module.clone();
+                self.current_module = anonymous_module;
             }
         }
 
@@ -2871,7 +2893,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                        name: Name,
                                        span: Span)
                                        -> BareIdentifierPatternResolution {
-        let module = self.current_module.clone();
+        let module = self.current_module;
         match self.resolve_item_in_lexical_scope(module, name, ValueNS, true) {
             Success((target, _)) => {
                 debug!("(resolve bare identifier pattern) succeeded in finding {} at {:?}",
@@ -3135,7 +3157,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
         let containing_module;
         let last_private;
-        let current_module = self.current_module.clone();
+        let current_module = self.current_module;
         match self.resolve_module_path(current_module,
                                        &module_path[..],
                                        UseLexicalScope,
@@ -3162,7 +3184,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         }
 
         let name = segments.last().unwrap().identifier.name;
-        let def = match self.resolve_name_in_module(containing_module.clone(),
+        let def = match self.resolve_name_in_module(containing_module,
                                                     name,
                                                     namespace,
                                                     NameSearchType::PathSearch,
@@ -3193,7 +3215,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                   .map(|ps| ps.identifier.name)
                                   .collect::<Vec<_>>();
 
-        let root_module = self.graph_root.clone();
+        let root_module = self.graph_root;
 
         let containing_module;
         let last_private;
@@ -3283,7 +3305,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                              record_used: bool)
                                              -> Option<Def> {
         // Check the items.
-        let module = self.current_module.clone();
+        let module = self.current_module;
         match self.resolve_item_in_lexical_scope(module, name, namespace, record_used) {
             Success((target, _)) => {
                 match target.binding.def() {
@@ -3345,11 +3367,11 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
             }
         }
 
-        fn get_module(this: &mut Resolver,
-                      span: Span,
-                      name_path: &[ast::Name])
-                      -> Option<Rc<Module>> {
-            let root = this.current_module.clone();
+        fn get_module<'a, 'tcx>(this: &mut Resolver<'a, 'tcx>,
+                                span: Span,
+                                name_path: &[ast::Name])
+                                -> Option<Module<'a>> {
+            let root = this.current_module;
             let last_name = name_path.last().unwrap();
 
             if name_path.len() == 1 {
@@ -3603,7 +3625,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                     let name_path = path.segments.iter()
                                                         .map(|seg| seg.identifier.name)
                                                         .collect::<Vec<_>>();
-                                    let current_module = self.current_module.clone();
+                                    let current_module = self.current_module;
 
                                     match self.resolve_module_path(current_module,
                                                    &name_path[..],
@@ -3725,7 +3747,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         }
 
         let mut found_traits = Vec::new();
-        let mut search_module = self.current_module.clone();
+        let mut search_module = self.current_module;
         loop {
             // Look for the current trait.
             match self.current_trait_ref {
@@ -3778,10 +3800,10 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 }
             }
 
-            match search_module.parent_link.clone() {
+            match search_module.parent_link {
                 NoParentLink | ModuleParentLink(..) => break,
                 BlockParentLink(parent_module, _) => {
-                    search_module = parent_module.upgrade().unwrap();
+                    search_module = parent_module;
                 }
             }
         }
@@ -3828,7 +3850,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     //
 
     #[allow(dead_code)]   // useful for debugging
-    fn dump_module(&mut self, module_: Rc<Module>) {
+    fn dump_module(&mut self, module_: Module<'a>) {
         debug!("Dump of module `{}`:", module_to_string(&*module_));
 
         debug!("Children:");
@@ -3891,20 +3913,20 @@ fn path_names_to_string(path: &Path, depth: usize) -> String {
 }
 
 /// A somewhat inefficient routine to obtain the name of a module.
-fn module_to_string(module: &Module) -> String {
+fn module_to_string<'a>(module: Module<'a>) -> String {
     let mut names = Vec::new();
 
-    fn collect_mod(names: &mut Vec<ast::Name>, module: &Module) {
+    fn collect_mod<'a>(names: &mut Vec<ast::Name>, module: Module<'a>) {
         match module.parent_link {
             NoParentLink => {}
             ModuleParentLink(ref module, name) => {
                 names.push(name);
-                collect_mod(names, &*module.upgrade().unwrap());
+                collect_mod(names, module);
             }
             BlockParentLink(ref module, _) => {
                 // danger, shouldn't be ident?
                 names.push(special_idents::opaque.name);
-                collect_mod(names, &*module.upgrade().unwrap());
+                collect_mod(names, module);
             }
         }
     }
@@ -3946,7 +3968,8 @@ pub fn resolve_crate<'a, 'tcx>(session: &'a Session,
                                make_glob_map: MakeGlobMap)
                                -> CrateMap {
     let krate = ast_map.krate();
-    let mut resolver = create_resolver(session, ast_map, krate, make_glob_map, None);
+    let arenas = Resolver::arenas();
+    let mut resolver = create_resolver(session, ast_map, krate, make_glob_map, &arenas, None);
 
     resolver.resolve_crate(krate);
 
@@ -3978,9 +4001,10 @@ pub fn create_resolver<'a, 'tcx>(session: &'a Session,
                                  ast_map: &'a hir_map::Map<'tcx>,
                                  krate: &'a Crate,
                                  make_glob_map: MakeGlobMap,
+                                 arenas: &'a ResolverArenas<'a>,
                                  callback: Option<Box<Fn(hir_map::Node, &mut bool) -> bool>>)
                                  -> Resolver<'a, 'tcx> {
-    let mut resolver = Resolver::new(session, ast_map, make_glob_map);
+    let mut resolver = Resolver::new(session, ast_map, make_glob_map, arenas);
 
     resolver.callback = callback;
 
diff --git a/src/librustc_resolve/record_exports.rs b/src/librustc_resolve/record_exports.rs
index 59cf83e91d2..13f4348f795 100644
--- a/src/librustc_resolve/record_exports.rs
+++ b/src/librustc_resolve/record_exports.rs
@@ -28,7 +28,6 @@ use rustc::middle::def::Export;
 use syntax::ast;
 
 use std::ops::{Deref, DerefMut};
-use std::rc::Rc;
 
 struct ExportRecorder<'a, 'b: 'a, 'tcx: 'b> {
     resolver: &'a mut Resolver<'b, 'tcx>,
@@ -50,7 +49,7 @@ impl<'a, 'b, 'tcx:'b> DerefMut for ExportRecorder<'a, 'b, 'tcx> {
 }
 
 impl<'a, 'b, 'tcx> ExportRecorder<'a, 'b, 'tcx> {
-    fn record_exports_for_module_subtree(&mut self, module_: Rc<Module>) {
+    fn record_exports_for_module_subtree(&mut self, module_: Module<'b>) {
         // If this isn't a local krate, then bail out. We don't need to record
         // exports for nonlocal crates.
 
@@ -59,23 +58,23 @@ impl<'a, 'b, 'tcx> ExportRecorder<'a, 'b, 'tcx> {
                 // OK. Continue.
                 debug!("(recording exports for module subtree) recording exports for local \
                         module `{}`",
-                       module_to_string(&*module_));
+                       module_to_string(module_));
             }
             None => {
                 // Record exports for the root module.
                 debug!("(recording exports for module subtree) recording exports for root module \
                         `{}`",
-                       module_to_string(&*module_));
+                       module_to_string(module_));
             }
             Some(_) => {
                 // Bail out.
                 debug!("(recording exports for module subtree) not recording exports for `{}`",
-                       module_to_string(&*module_));
+                       module_to_string(module_));
                 return;
             }
         }
 
-        self.record_exports_for_module(&*module_);
+        self.record_exports_for_module(module_);
         build_reduced_graph::populate_module_if_necessary(self.resolver, &module_);
 
         for (_, child_name_bindings) in module_.children.borrow().iter() {
@@ -90,11 +89,11 @@ impl<'a, 'b, 'tcx> ExportRecorder<'a, 'b, 'tcx> {
         }
 
         for (_, child_module) in module_.anonymous_children.borrow().iter() {
-            self.record_exports_for_module_subtree(child_module.clone());
+            self.record_exports_for_module_subtree(child_module);
         }
     }
 
-    fn record_exports_for_module(&mut self, module_: &Module) {
+    fn record_exports_for_module(&mut self, module_: Module<'b>) {
         let mut exports = Vec::new();
 
         self.add_exports_for_module(&mut exports, module_);
@@ -128,7 +127,7 @@ impl<'a, 'b, 'tcx> ExportRecorder<'a, 'b, 'tcx> {
         }
     }
 
-    fn add_exports_for_module(&mut self, exports: &mut Vec<Export>, module_: &Module) {
+    fn add_exports_for_module(&mut self, exports: &mut Vec<Export>, module_: Module<'b>) {
         for (name, import_resolution) in module_.import_resolutions.borrow().iter() {
             let xs = [TypeNS, ValueNS];
             for &ns in &xs {
@@ -150,6 +149,6 @@ impl<'a, 'b, 'tcx> ExportRecorder<'a, 'b, 'tcx> {
 
 pub fn record(resolver: &mut Resolver) {
     let mut recorder = ExportRecorder { resolver: resolver };
-    let root_module = recorder.graph_root.clone();
+    let root_module = recorder.graph_root;
     recorder.record_exports_for_module_subtree(root_module);
 }
diff --git a/src/librustc_resolve/resolve_imports.rs b/src/librustc_resolve/resolve_imports.rs
index 40bf55efde6..53d1b888d8e 100644
--- a/src/librustc_resolve/resolve_imports.rs
+++ b/src/librustc_resolve/resolve_imports.rs
@@ -36,7 +36,6 @@ use syntax::codemap::Span;
 use syntax::util::lev_distance::find_best_match_for_name;
 
 use std::mem::replace;
-use std::rc::Rc;
 
 /// Contains data for specific types of import directives.
 #[derive(Copy, Clone,Debug)]
@@ -84,17 +83,15 @@ impl ImportDirective {
 
 /// The item that an import resolves to.
 #[derive(Clone,Debug)]
-pub struct Target {
-    pub target_module: Rc<Module>,
-    pub binding: NameBinding,
+pub struct Target<'a> {
+    pub target_module: Module<'a>,
+    pub binding: NameBinding<'a>,
     pub shadowable: Shadowable,
 }
 
-impl Target {
-    pub fn new(target_module: Rc<Module>,
-               binding: NameBinding,
-               shadowable: Shadowable)
-               -> Target {
+impl<'a> Target<'a> {
+    pub fn new(target_module: Module<'a>, binding: NameBinding<'a>, shadowable: Shadowable)
+               -> Self {
         Target {
             target_module: target_module,
             binding: binding,
@@ -109,44 +106,44 @@ impl Target {
 /// and for each namespace, it records the `use` directive importing the name in the namespace
 /// and the `Target` to which the name in the namespace resolves (if applicable).
 /// Different `use` directives may import the same name in different namespaces.
-pub struct ImportResolutionPerNamespace {
+pub struct ImportResolutionPerNamespace<'a> {
     // When outstanding_references reaches zero, outside modules can count on the targets being
     // correct. Before then, all bets are off; future `use` directives could override the name.
     // Since shadowing is forbidden, the only way outstanding_references > 1 in a legal program
     // is if the name is imported by exactly two `use` directives, one of which resolves to a
     // value and the other of which resolves to a type.
     pub outstanding_references: usize,
-    pub type_ns: ImportResolution,
-    pub value_ns: ImportResolution,
+    pub type_ns: ImportResolution<'a>,
+    pub value_ns: ImportResolution<'a>,
 }
 
 /// Records what we know about an imported name in a namespace (see `ImportResolutionPerNamespace`).
 #[derive(Clone,Debug)]
-pub struct ImportResolution {
+pub struct ImportResolution<'a> {
     /// Whether the name in the namespace was imported with a `use` or a `pub use`.
     pub is_public: bool,
 
     /// Resolution of the name in the namespace
-    pub target: Option<Target>,
+    pub target: Option<Target<'a>>,
 
     /// The source node of the `use` directive
     pub id: NodeId,
 }
 
-impl ::std::ops::Index<Namespace> for ImportResolutionPerNamespace {
-    type Output = ImportResolution;
-    fn index(&self, ns: Namespace) -> &ImportResolution {
+impl<'a> ::std::ops::Index<Namespace> for ImportResolutionPerNamespace<'a> {
+    type Output = ImportResolution<'a>;
+    fn index(&self, ns: Namespace) -> &ImportResolution<'a> {
         match ns { TypeNS => &self.type_ns, ValueNS => &self.value_ns }
     }
 }
 
-impl ::std::ops::IndexMut<Namespace> for ImportResolutionPerNamespace {
-    fn index_mut(&mut self, ns: Namespace) -> &mut ImportResolution {
+impl<'a> ::std::ops::IndexMut<Namespace> for ImportResolutionPerNamespace<'a> {
+    fn index_mut(&mut self, ns: Namespace) -> &mut ImportResolution<'a> {
         match ns { TypeNS => &mut self.type_ns, ValueNS => &mut self.value_ns }
     }
 }
 
-impl ImportResolutionPerNamespace {
+impl<'a> ImportResolutionPerNamespace<'a> {
     pub fn new(id: NodeId, is_public: bool) -> Self {
         let resolution = ImportResolution { id: id, is_public: is_public, target: None };
         ImportResolutionPerNamespace {
@@ -191,8 +188,8 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                    i,
                    self.resolver.unresolved_imports);
 
-            let module_root = self.resolver.graph_root.clone();
-            let errors = self.resolve_imports_for_module_subtree(module_root.clone());
+            let module_root = self.resolver.graph_root;
+            let errors = self.resolve_imports_for_module_subtree(module_root);
 
             if self.resolver.unresolved_imports == 0 {
                 debug!("(resolving imports) success");
@@ -225,13 +222,13 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
     /// Attempts to resolve imports for the given module and all of its
     /// submodules.
     fn resolve_imports_for_module_subtree(&mut self,
-                                          module_: Rc<Module>)
+                                          module_: Module<'b>)
                                           -> Vec<ImportResolvingError> {
         let mut errors = Vec::new();
         debug!("(resolving imports for module subtree) resolving {}",
                module_to_string(&*module_));
-        let orig_module = replace(&mut self.resolver.current_module, module_.clone());
-        errors.extend(self.resolve_imports_for_module(module_.clone()));
+        let orig_module = replace(&mut self.resolver.current_module, module_);
+        errors.extend(self.resolve_imports_for_module(module_));
         self.resolver.current_module = orig_module;
 
         build_reduced_graph::populate_module_if_necessary(self.resolver, &module_);
@@ -247,14 +244,14 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         }
 
         for (_, child_module) in module_.anonymous_children.borrow().iter() {
-            errors.extend(self.resolve_imports_for_module_subtree(child_module.clone()));
+            errors.extend(self.resolve_imports_for_module_subtree(child_module));
         }
 
         errors
     }
 
     /// Attempts to resolve imports for the given module only.
-    fn resolve_imports_for_module(&mut self, module: Rc<Module>) -> Vec<ImportResolvingError> {
+    fn resolve_imports_for_module(&mut self, module: Module<'b>) -> Vec<ImportResolvingError> {
         let mut errors = Vec::new();
 
         if module.all_imports_resolved() {
@@ -268,7 +265,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         let mut indeterminate_imports = Vec::new();
         while module.resolved_import_count.get() + indeterminate_imports.len() < import_count {
             let import_index = module.resolved_import_count.get();
-            match self.resolve_import_for_module(module.clone(), &imports[import_index]) {
+            match self.resolve_import_for_module(module, &imports[import_index]) {
                 ResolveResult::Failed(err) => {
                     let import_directive = &imports[import_index];
                     let (span, help) = match err {
@@ -306,7 +303,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
     /// currently-unresolved imports, or success if we know the name exists.
     /// If successful, the resolved bindings are written into the module.
     fn resolve_import_for_module(&mut self,
-                                 module_: Rc<Module>,
+                                 module_: Module<'b>,
                                  import_directive: &ImportDirective)
                                  -> ResolveResult<()> {
         let mut resolution_result = ResolveResult::Failed(None);
@@ -319,9 +316,9 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         // First, resolve the module path for the directive, if necessary.
         let container = if module_path.is_empty() {
             // Use the crate root.
-            Some((self.resolver.graph_root.clone(), LastMod(AllPublic)))
+            Some((self.resolver.graph_root, LastMod(AllPublic)))
         } else {
-            match self.resolver.resolve_module_path(module_.clone(),
+            match self.resolver.resolve_module_path(module_,
                                                     &module_path[..],
                                                     UseLexicalScopeFlag::DontUseLexicalScope,
                                                     import_directive.span,
@@ -399,8 +396,8 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
     }
 
     fn resolve_single_import(&mut self,
-                             module_: &Module,
-                             target_module: Rc<Module>,
+                             module_: Module<'b>,
+                             target_module: Module<'b>,
                              target: Name,
                              source: Name,
                              directive: &ImportDirective,
@@ -447,7 +444,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                 let mut pub_err = false;
                 if child_name_bindings.value_ns.defined() {
                     debug!("(resolving single import) found value binding");
-                    value_result = BoundResult(target_module.clone(),
+                    value_result = BoundResult(target_module,
                                                child_name_bindings.value_ns.clone());
                     if directive.is_public && !child_name_bindings.value_ns.is_public() {
                         let msg = format!("`{}` is private, and cannot be reexported", source);
@@ -473,7 +470,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                 }
                 if child_name_bindings.type_ns.defined() {
                     debug!("(resolving single import) found type binding");
-                    type_result = BoundResult(target_module.clone(),
+                    type_result = BoundResult(target_module,
                                               child_name_bindings.type_ns.clone());
                     if !pub_err && directive.is_public &&
                        !child_name_bindings.type_ns.is_public() {
@@ -543,11 +540,11 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                     }
                     Some(import_resolution) if import_resolution.outstanding_references == 0 => {
 
-                        fn get_binding(this: &mut Resolver,
-                                       import_resolution: &ImportResolutionPerNamespace,
-                                       namespace: Namespace,
-                                       source: Name)
-                                       -> NamespaceResult {
+                        fn get_binding<'a>(this: &mut Resolver,
+                                           import_resolution: &ImportResolutionPerNamespace<'a>,
+                                           namespace: Namespace,
+                                           source: Name)
+                                           -> NamespaceResult<'a> {
 
                             // Import resolutions must be declared with "pub"
                             // in order to be exported.
@@ -640,7 +637,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         match type_result {
             BoundResult(..) => {}
             _ => {
-                match target_module.external_module_children.borrow_mut().get(&source).cloned() {
+                match target_module.external_module_children.borrow_mut().get(&source) {
                     None => {} // Continue.
                     Some(module) => {
                         debug!("(resolving single import) found external module");
@@ -652,7 +649,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                             _ => {}
                         }
                         let name_binding = NameBinding::create_from_module(module);
-                        type_result = BoundResult(target_module.clone(), name_binding);
+                        type_result = BoundResult(target_module, name_binding);
                         type_used_public = true;
                     }
                 }
@@ -685,7 +682,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                                                              target);
 
                         import_resolution[namespace] = ImportResolution {
-                            target: Some(Target::new(target_module.clone(),
+                            target: Some(Target::new(target_module,
                                                      name_binding.clone(),
                                                      directive.shadowable)),
                             id: directive.id,
@@ -777,8 +774,8 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
     // that exports nothing is valid). target_module is the module we are
     // actually importing, i.e., `foo` in `use foo::*`.
     fn resolve_glob_import(&mut self,
-                           module_: &Module,
-                           target_module: Rc<Module>,
+                           module_: Module<'b>,
+                           target_module: Module<'b>,
                            import_directive: &ImportDirective,
                            lp: LastPrivate)
                            -> ResolveResult<()> {
@@ -841,7 +838,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
 
         for (&name, name_bindings) in target_module.children.borrow().iter() {
             self.merge_import_resolution(module_,
-                                         target_module.clone(),
+                                         target_module,
                                          import_directive,
                                          name,
                                          name_bindings.clone());
@@ -863,11 +860,11 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
     }
 
     fn merge_import_resolution(&mut self,
-                               module_: &Module,
-                               containing_module: Rc<Module>,
+                               module_: Module<'b>,
+                               containing_module: Module<'b>,
                                import_directive: &ImportDirective,
                                name: Name,
-                               name_bindings: NameBindings) {
+                               name_bindings: NameBindings<'b>) {
         let id = import_directive.id;
         let is_public = import_directive.is_public;
 
@@ -916,7 +913,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
                                   msg);
                     } else {
                         dest_import_resolution[namespace] = ImportResolution {
-                            target: Some(Target::new(containing_module.clone(),
+                            target: Some(Target::new(containing_module,
                                                      name_bindings[namespace].clone(),
                                                      import_directive.shadowable)),
                             id: id,
@@ -993,8 +990,8 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
 
     /// Checks that imported names and items don't have the same name.
     fn check_for_conflicts_between_imports_and_items(&mut self,
-                                                     module: &Module,
-                                                     import: &ImportResolutionPerNamespace,
+                                                     module: Module<'b>,
+                                                     import: &ImportResolutionPerNamespace<'b>,
                                                      import_span: Span,
                                                      name: Name) {
         // First, check for conflicts between imports and `extern crate`s.
@@ -1013,8 +1010,7 @@ impl<'a, 'b:'a, 'tcx:'b> ImportResolver<'a, 'b, 'tcx> {
         }
 
         // Check for item conflicts.
-        let children = module.children.borrow();
-        let name_bindings = match children.get(&name) {
+        let name_bindings = match module.children.borrow().get(&name) {
             None => {
                 // There can't be any conflicts.
                 return;