Refactor the HIR so that items are stored in a map in the `Crate`,

rather being stored inline. Refactor (and rename) the visitor so that
(by default) it only visits the interior content of an item not nested
items.

This is a [breaking-change] for anyone who uses the HIR visitor. Besides
changing `visit::` to `intravisit::`, you need to refactor your visitor
in one of two ways, depending on what it requires:

1. If you just want to visit all items (most common), you should call
   `krate.visit_all_items(&mut visitor)`.

2. If you need to visit nested items in the middle of the parent items,
   you should override `visit_nested_item` with something like:
   `self.visit_item(self.tcx.map.expect_item(item.id))`, presuming you
   have access to a tcx (or at least a HIR map).

8 files changed, 229 insertions, 112 deletions

diff --git a/mk/crates.mk b/mk/crates.mk
index 89a836eb7cb..d77d99a4a1a 100644
--- a/mk/crates.mk
+++ b/mk/crates.mk
@@ -96,7 +96,7 @@ DEPS_rustc_driver := arena flate getopts graphviz libc rustc rustc_back rustc_bo
                      rustc_typeck rustc_mir rustc_resolve log syntax serialize rustc_llvm \
 		             rustc_trans rustc_privacy rustc_lint rustc_front
 
-DEPS_rustc_front := std syntax log serialize
+DEPS_rustc_front := std syntax log serialize rustc_data_structures
 DEPS_rustc_lint := rustc log syntax
 DEPS_rustc_llvm := native:rustllvm libc std rustc_bitflags
 DEPS_rustc_mir := rustc rustc_front syntax
diff --git a/src/librustc_front/fold.rs b/src/librustc_front/fold.rs
index b963aba9c07..7ec4e1ba331 100644
--- a/src/librustc_front/fold.rs
+++ b/src/librustc_front/fold.rs
@@ -77,10 +77,14 @@ pub trait Folder : Sized {
         noop_fold_foreign_item(ni, self)
     }
 
-    fn fold_item(&mut self, i: P<Item>) -> P<Item> {
+    fn fold_item(&mut self, i: Item) -> Item {
         noop_fold_item(i, self)
     }
 
+    fn fold_item_id(&mut self, i: ItemId) -> ItemId {
+        noop_fold_item_id(i, self)
+    }
+
     fn fold_struct_field(&mut self, sf: StructField) -> StructField {
         noop_fold_struct_field(sf, self)
     }
@@ -271,10 +275,16 @@ pub trait Folder : Sized {
         noop_fold_where_predicate(where_predicate, self)
     }
 
+    /// called for the `id` on each declaration
     fn new_id(&mut self, i: NodeId) -> NodeId {
         i
     }
 
+    /// called for ids that are references (e.g., ItemDef)
+    fn map_id(&mut self, i: NodeId) -> NodeId {
+        i
+    }
+
     fn new_span(&mut self, sp: Span) -> Span {
         sp
     }
@@ -342,7 +352,7 @@ pub fn noop_fold_decl<T: Folder>(d: P<Decl>, fld: &mut T) -> P<Decl> {
                 span: fld.new_span(span),
             },
             DeclItem(it) => Spanned {
-                node: DeclItem(fld.fold_item(it)),
+                node: DeclItem(fld.fold_item_id(it)),
                 span: fld.new_span(span),
             },
         }
@@ -879,34 +889,40 @@ pub fn noop_fold_impl_item<T: Folder>(i: P<ImplItem>, folder: &mut T) -> P<ImplI
     })
 }
 
-pub fn noop_fold_mod<T: Folder>(Mod { inner, items }: Mod, folder: &mut T) -> Mod {
+pub fn noop_fold_mod<T: Folder>(Mod { inner, item_ids }: Mod, folder: &mut T) -> Mod {
     Mod {
         inner: folder.new_span(inner),
-        items: items.into_iter().map(|x| folder.fold_item(x)).collect(),
+        item_ids: item_ids.into_iter().map(|x| folder.fold_item_id(x)).collect(),
     }
 }
 
-pub fn noop_fold_crate<T: Folder>(Crate { module, attrs, config, span, exported_macros }: Crate,
+pub fn noop_fold_crate<T: Folder>(Crate { module, attrs, config, span,
+                                          exported_macros, items }: Crate,
                                   folder: &mut T)
                                   -> Crate {
     let config = folder.fold_meta_items(config);
 
-    let crate_mod = folder.fold_item(P(hir::Item {
+    let crate_mod = folder.fold_item(hir::Item {
         name: token::special_idents::invalid.name,
         attrs: attrs,
         id: DUMMY_NODE_ID,
         vis: hir::Public,
         span: span,
         node: hir::ItemMod(module),
-    }));
+    });
 
-    let (module, attrs, span) =
-        crate_mod.and_then(|hir::Item { attrs, span, node, .. }| {
+    let (module, attrs, span) = match crate_mod {
+        hir::Item { attrs, span, node, .. } => {
             match node {
                 hir::ItemMod(m) => (m, attrs, span),
                 _ => panic!("fold converted a module to not a module"),
             }
-        });
+        }
+    };
+
+    let items = items.into_iter()
+                     .map(|(id, item)| (id, folder.fold_item(item)))
+                     .collect();
 
     Crate {
         module: module,
@@ -914,31 +930,37 @@ pub fn noop_fold_crate<T: Folder>(Crate { module, attrs, config, span, exported_
         config: config,
         span: span,
         exported_macros: exported_macros,
+        items: items,
     }
 }
 
-pub fn noop_fold_item<T: Folder>(item: P<Item>, folder: &mut T) -> P<Item> {
-    item.map(|Item { id, name, attrs, node, vis, span }| {
-        let id = folder.new_id(id);
-        let node = folder.fold_item_underscore(node);
-        // FIXME: we should update the impl_pretty_name, but it uses pretty printing.
-        // let ident = match node {
-        //     // The node may have changed, recompute the "pretty" impl name.
-        //     ItemImpl(_, _, _, ref maybe_trait, ref ty, _) => {
-        //         impl_pretty_name(maybe_trait, Some(&**ty))
-        //     }
-        //     _ => ident
-        // };
-
-        Item {
-            id: id,
-            name: folder.fold_name(name),
-            attrs: fold_attrs(attrs, folder),
-            node: node,
-            vis: vis,
-            span: folder.new_span(span),
-        }
-    })
+pub fn noop_fold_item_id<T: Folder>(i: ItemId, folder: &mut T) -> ItemId {
+    let id = folder.map_id(i.id);
+    ItemId { id: id }
+}
+
+// fold one item into one item
+pub fn noop_fold_item<T: Folder>(item: Item, folder: &mut T) -> Item {
+    let Item { id, name, attrs, node, vis, span } = item;
+    let id = folder.new_id(id);
+    let node = folder.fold_item_underscore(node);
+    // FIXME: we should update the impl_pretty_name, but it uses pretty printing.
+    // let ident = match node {
+    //     // The node may have changed, recompute the "pretty" impl name.
+    //     ItemImpl(_, _, _, ref maybe_trait, ref ty, _) => {
+    //         impl_pretty_name(maybe_trait, Some(&**ty))
+    //     }
+    //     _ => ident
+    // };
+
+    Item {
+        id: id,
+        name: folder.fold_name(name),
+        attrs: fold_attrs(attrs, folder),
+        node: node,
+        vis: vis,
+        span: folder.new_span(span),
+    }
 }
 
 pub fn noop_fold_foreign_item<T: Folder>(ni: P<ForeignItem>, folder: &mut T) -> P<ForeignItem> {
diff --git a/src/librustc_front/hir.rs b/src/librustc_front/hir.rs
index 1fa7c9d301c..4232254327c 100644
--- a/src/librustc_front/hir.rs
+++ b/src/librustc_front/hir.rs
@@ -35,6 +35,8 @@ pub use self::ViewPath_::*;
 pub use self::Visibility::*;
 pub use self::PathParameters::*;
 
+use intravisit::Visitor;
+use rustc_data_structures::fnv::FnvHashMap;
 use syntax::codemap::{self, Span, Spanned, DUMMY_SP, ExpnId};
 use syntax::abi::Abi;
 use syntax::ast::{Name, Ident, NodeId, DUMMY_NODE_ID, TokenTree, AsmDialect};
@@ -320,13 +322,42 @@ pub struct WhereEqPredicate {
     pub ty: P<Ty>,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
 pub struct Crate {
     pub module: Mod,
     pub attrs: Vec<Attribute>,
     pub config: CrateConfig,
     pub span: Span,
     pub exported_macros: Vec<MacroDef>,
+    pub items: FnvHashMap<NodeId, Item>,
+}
+
+impl Crate {
+    pub fn item(&self, id: NodeId) -> &Item {
+        &self.items[&id]
+    }
+
+    /// Visits all items in the crate in some determinstic (but
+    /// unspecified) order. If you just need to process every item,
+    /// but don't care about nesting, this method is the best choice.
+    ///
+    /// If you do care about nesting -- usually because your algorithm
+    /// follows lexical scoping rules -- then you want a different
+    /// approach. You should override `visit_nested_item` in your
+    /// visitor and then call `intravisit::walk_crate` instead.
+    pub fn visit_all_items<'hir, V:Visitor<'hir>>(&'hir self, visitor: &mut V) {
+        // In principle, we could just iterate over the hashmap, but
+        // in practice that makes the order of error reporting vary
+        // with small changes in the input etc etc, which makes the
+        // test base hard to maintain. So instead we sort by node-id
+        // so as to get reproducible results.
+        let mut pairs: Vec<_> = self.items.iter().collect();
+        pairs.sort_by(|&(id1, _), &(id2, _)| id1.cmp(id2));
+
+        for (_, item) in pairs {
+            visitor.visit_item(item);
+        }
+    }
 }
 
 /// A macro definition, in this crate or imported from another.
@@ -537,7 +568,7 @@ pub enum Decl_ {
     /// A local (let) binding:
     DeclLocal(P<Local>),
     /// An item binding:
-    DeclItem(P<Item>),
+    DeclItem(ItemId),
 }
 
 /// represents one arm of a 'match'
@@ -992,7 +1023,7 @@ pub struct Mod {
     /// For `mod foo;`, the inner span ranges from the first token
     /// to the last token in the external file.
     pub inner: Span,
-    pub items: Vec<P<Item>>,
+    pub item_ids: Vec<ItemId>,
 }
 
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
@@ -1205,7 +1236,13 @@ impl VariantData {
     }
 }
 
-
+// The bodies for items are stored "out of line", in a separate
+// hashmap in the `Crate`. Here we just record the node-id of the item
+// so it can fetched later.
+#[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+pub struct ItemId {
+    pub id: NodeId,
+}
 
 //  FIXME (#3300): Should allow items to be anonymous. Right now
 //  we just use dummy names for anon items.
diff --git a/src/librustc_front/visit.rs b/src/librustc_front/intravisit.rs
index ec58f31b6de..9c923ea32ef 100644
--- a/src/librustc_front/visit.rs
+++ b/src/librustc_front/intravisit.rs
@@ -45,11 +45,37 @@ pub enum FnKind<'a> {
 /// the substructure of the input via the corresponding `walk` method;
 /// e.g. the `visit_mod` method by default calls `visit::walk_mod`.
 ///
+/// Note that this visitor does NOT visit nested items by default. If
+/// you simply want to visit all items in the crate in some order, you
+/// should call `Crate::visit_all_items`. Otherwise, see the comment
+/// on `visit_nested_item` for details on how to visit nested items.
+///
 /// If you want to ensure that your code handles every variant
 /// explicitly, you need to override each method.  (And you also need
 /// to monitor future changes to `Visitor` in case a new method with a
 /// new default implementation gets introduced.)
 pub trait Visitor<'v> : Sized {
+    ///////////////////////////////////////////////////////////////////////////
+    // Nested items.
+
+    /// Invoked when a nested item is encountered. By default, does
+    /// nothing. If you want a deep walk, you need to override to
+    /// fetch the item contents. But most of the time, it is easier
+    /// (and better) to invoke `Crate::visit_all_items`, which visits
+    /// all items in the crate in some order (but doesn't respect
+    /// nesting).
+    #[allow(unused_variables)]
+    fn visit_nested_item(&mut self, id: ItemId) {
+    }
+
+    /// Visit the top-level item and (optionally) nested items. See
+    /// `visit_nested_item` for details.
+    fn visit_item(&mut self, i: &'v Item) {
+        walk_item(self, i)
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+
     fn visit_name(&mut self, _span: Span, _name: Name) {
         // Nothing to do.
     }
@@ -62,9 +88,6 @@ pub trait Visitor<'v> : Sized {
     fn visit_foreign_item(&mut self, i: &'v ForeignItem) {
         walk_foreign_item(self, i)
     }
-    fn visit_item(&mut self, i: &'v Item) {
-        walk_item(self, i)
-    }
     fn visit_local(&mut self, l: &'v Local) {
         walk_local(self, l)
     }
@@ -180,6 +203,7 @@ pub fn walk_ident<'v, V: Visitor<'v>>(visitor: &mut V, span: Span, ident: Ident)
     visitor.visit_name(span, ident.name);
 }
 
+/// Walks the contents of a crate. See also `Crate::visit_all_items`.
 pub fn walk_crate<'v, V: Visitor<'v>>(visitor: &mut V, krate: &'v Crate) {
     visitor.visit_mod(&krate.module, krate.span, CRATE_NODE_ID);
     walk_list!(visitor, visit_attribute, &krate.attrs);
@@ -193,7 +217,9 @@ pub fn walk_macro_def<'v, V: Visitor<'v>>(visitor: &mut V, macro_def: &'v MacroD
 }
 
 pub fn walk_mod<'v, V: Visitor<'v>>(visitor: &mut V, module: &'v Mod) {
-    walk_list!(visitor, visit_item, &module.items);
+    for &item_id in &module.item_ids {
+        visitor.visit_nested_item(item_id);
+    }
 }
 
 pub fn walk_local<'v, V: Visitor<'v>>(visitor: &mut V, local: &'v Local) {
@@ -658,7 +684,7 @@ pub fn walk_stmt<'v, V: Visitor<'v>>(visitor: &mut V, statement: &'v Stmt) {
 pub fn walk_decl<'v, V: Visitor<'v>>(visitor: &mut V, declaration: &'v Decl) {
     match declaration.node {
         DeclLocal(ref local) => visitor.visit_local(local),
-        DeclItem(ref item) => visitor.visit_item(item),
+        DeclItem(item) => visitor.visit_nested_item(item),
     }
 }
 
diff --git a/src/librustc_front/lib.rs b/src/librustc_front/lib.rs
index 022744cbc3a..d8c5eac1feb 100644
--- a/src/librustc_front/lib.rs
+++ b/src/librustc_front/lib.rs
@@ -45,13 +45,14 @@ extern crate syntax;
 #[macro_use]
 #[no_link]
 extern crate rustc_bitflags;
+extern crate rustc_data_structures;
 
 extern crate serialize as rustc_serialize; // used by deriving
 
 pub mod hir;
 pub mod lowering;
 pub mod fold;
-pub mod visit;
+pub mod intravisit;
 pub mod util;
 
 pub mod print {
diff --git a/src/librustc_front/lowering.rs b/src/librustc_front/lowering.rs
index 250379d2d7e..ad081598c11 100644
--- a/src/librustc_front/lowering.rs
+++ b/src/librustc_front/lowering.rs
@@ -71,6 +71,8 @@ use syntax::codemap::{respan, Spanned, Span};
 use syntax::owned_slice::OwnedSlice;
 use syntax::parse::token::{self, str_to_ident};
 use syntax::std_inject;
+use syntax::visit::{self, Visitor};
+use rustc_data_structures::fnv::FnvHashMap;
 
 use std::cell::{Cell, RefCell};
 
@@ -191,7 +193,7 @@ pub fn lower_decl(lctx: &LoweringContext, d: &Decl) -> P<hir::Decl> {
             span: d.span,
         }),
         DeclItem(ref it) => P(Spanned {
-            node: hir::DeclItem(lower_item(lctx, it)),
+            node: hir::DeclItem(lower_item_id(lctx, it)),
             span: d.span,
         }),
     }
@@ -693,17 +695,36 @@ pub fn lower_impl_item(lctx: &LoweringContext, i: &ImplItem) -> P<hir::ImplItem>
 pub fn lower_mod(lctx: &LoweringContext, m: &Mod) -> hir::Mod {
     hir::Mod {
         inner: m.inner,
-        items: m.items.iter().map(|x| lower_item(lctx, x)).collect(),
+        item_ids: m.items.iter().map(|x| lower_item_id(lctx, x)).collect(),
+    }
+}
+
+struct ItemLowerer<'lcx, 'interner: 'lcx> {
+    items: FnvHashMap<NodeId, hir::Item>,
+    lctx: &'lcx LoweringContext<'interner>,
+}
+
+impl<'lcx, 'interner> Visitor<'lcx> for ItemLowerer<'lcx, 'interner> {
+    fn visit_item(&mut self, item: &'lcx Item) {
+        self.items.insert(item.id, lower_item(self.lctx, item));
+        visit::walk_item(self, item);
     }
 }
 
 pub fn lower_crate(lctx: &LoweringContext, c: &Crate) -> hir::Crate {
+    let items = {
+        let mut item_lowerer = ItemLowerer { items: FnvHashMap(), lctx: lctx };
+        visit::walk_crate(&mut item_lowerer, c);
+        item_lowerer.items
+    };
+
     hir::Crate {
         module: lower_mod(lctx, &c.module),
         attrs: c.attrs.clone(),
         config: c.config.clone(),
         span: c.span,
         exported_macros: c.exported_macros.iter().map(|m| lower_macro_def(lctx, m)).collect(),
+        items: items,
     }
 }
 
@@ -721,13 +742,11 @@ pub fn lower_macro_def(_lctx: &LoweringContext, m: &MacroDef) -> hir::MacroDef {
     }
 }
 
-// fold one item into possibly many items
-pub fn lower_item(lctx: &LoweringContext, i: &Item) -> P<hir::Item> {
-    P(lower_item_simple(lctx, i))
+pub fn lower_item_id(_lctx: &LoweringContext, i: &Item) -> hir::ItemId {
+    hir::ItemId { id: i.id }
 }
 
-// fold one item into exactly one item
-pub fn lower_item_simple(lctx: &LoweringContext, i: &Item) -> hir::Item {
+pub fn lower_item(lctx: &LoweringContext, i: &Item) -> hir::Item {
     let node = lower_item_underscore(lctx, &i.node);
 
     hir::Item {
diff --git a/src/librustc_front/print/pprust.rs b/src/librustc_front/print/pprust.rs
index 09c814449a9..f29ef0e8217 100644
--- a/src/librustc_front/print/pprust.rs
+++ b/src/librustc_front/print/pprust.rs
@@ -25,7 +25,7 @@ use syntax::print::pprust::{self as ast_pp, PrintState};
 use syntax::ptr::P;
 
 use hir;
-use hir::{RegionTyParamBound, TraitTyParamBound, TraitBoundModifier};
+use hir::{Crate, RegionTyParamBound, TraitTyParamBound, TraitBoundModifier};
 
 use std::io::{self, Write, Read};
 
@@ -54,6 +54,7 @@ impl PpAnn for NoAnn {}
 
 
 pub struct State<'a> {
+    krate: Option<&'a Crate>,
     pub s: pp::Printer<'a>,
     cm: Option<&'a CodeMap>,
     comments: Option<Vec<comments::Comment>>,
@@ -85,13 +86,14 @@ impl<'a> PrintState<'a> for State<'a> {
     }
 }
 
-pub fn rust_printer<'a>(writer: Box<Write + 'a>) -> State<'a> {
+pub fn rust_printer<'a>(writer: Box<Write + 'a>, krate: Option<&'a Crate>) -> State<'a> {
     static NO_ANN: NoAnn = NoAnn;
-    rust_printer_annotated(writer, &NO_ANN)
+    rust_printer_annotated(writer, &NO_ANN, krate)
 }
 
-pub fn rust_printer_annotated<'a>(writer: Box<Write + 'a>, ann: &'a PpAnn) -> State<'a> {
+pub fn rust_printer_annotated<'a>(writer: Box<Write + 'a>, ann: &'a PpAnn, krate: Option<&'a Crate>) -> State<'a> {
     State {
+        krate: krate,
         s: pp::mk_printer(writer, default_columns),
         cm: None,
         comments: None,
@@ -124,7 +126,7 @@ pub fn print_crate<'a>(cm: &'a CodeMap,
                        ann: &'a PpAnn,
                        is_expanded: bool)
                        -> io::Result<()> {
-    let mut s = State::new_from_input(cm, span_diagnostic, filename, input, out, ann, is_expanded);
+    let mut s = State::new_from_input(cm, span_diagnostic, filename, input, out, ann, is_expanded, Some(krate));
 
     // When printing the AST, we sometimes need to inject `#[no_std]` here.
     // Since you can't compile the HIR, it's not necessary.
@@ -141,7 +143,8 @@ impl<'a> State<'a> {
                           input: &mut Read,
                           out: Box<Write + 'a>,
                           ann: &'a PpAnn,
-                          is_expanded: bool)
+                          is_expanded: bool,
+                          krate: Option<&'a Crate>)
                           -> State<'a> {
         let (cmnts, lits) = comments::gather_comments_and_literals(span_diagnostic,
                                                                    filename,
@@ -158,16 +161,19 @@ impl<'a> State<'a> {
                        None
                    } else {
                        Some(lits)
-                   })
+                   },
+                   krate)
     }
 
     pub fn new(cm: &'a CodeMap,
                out: Box<Write + 'a>,
                ann: &'a PpAnn,
                comments: Option<Vec<comments::Comment>>,
-               literals: Option<Vec<comments::Literal>>)
+               literals: Option<Vec<comments::Literal>>,
+               krate: Option<&'a Crate>)
                -> State<'a> {
         State {
+            krate: krate,
             s: pp::mk_printer(out, default_columns),
             cm: Some(cm),
             comments: comments.clone(),
@@ -187,7 +193,7 @@ pub fn to_string<F>(f: F) -> String
 {
     let mut wr = Vec::new();
     {
-        let mut printer = rust_printer(Box::new(&mut wr));
+        let mut printer = rust_printer(Box::new(&mut wr), None);
         f(&mut printer).unwrap();
         eof(&mut printer.s).unwrap();
     }
@@ -451,8 +457,8 @@ impl<'a> State<'a> {
 
     pub fn print_mod(&mut self, _mod: &hir::Mod, attrs: &[ast::Attribute]) -> io::Result<()> {
         try!(self.print_inner_attributes(attrs));
-        for item in &_mod.items {
-            try!(self.print_item(&**item));
+        for item_id in &_mod.item_ids {
+            try!(self.print_item_id(item_id));
         }
         Ok(())
     }
@@ -620,6 +626,16 @@ impl<'a> State<'a> {
         word(&mut self.s, ";")
     }
 
+    pub fn print_item_id(&mut self, item_id: &hir::ItemId) -> io::Result<()> {
+        if let Some(krate) = self.krate {
+            // skip nested items if krate context was not provided
+            let item = &krate.items[&item_id.id];
+            self.print_item(item)
+        } else {
+            Ok(())
+        }
+    }
+
     /// Pretty-print an item
     pub fn print_item(&mut self, item: &hir::Item) -> io::Result<()> {
         try!(self.hardbreak_if_not_bol());
@@ -1566,7 +1582,9 @@ impl<'a> State<'a> {
                 }
                 self.end()
             }
-            hir::DeclItem(ref item) => self.print_item(&**item),
+            hir::DeclItem(ref item) => {
+                self.print_item_id(item)
+            }
         }
     }
 
diff --git a/src/librustc_front/util.rs b/src/librustc_front/util.rs
index a2c52b274d5..97b25dafb6d 100644
--- a/src/librustc_front/util.rs
+++ b/src/librustc_front/util.rs
@@ -10,7 +10,7 @@
 
 use hir;
 use hir::*;
-use visit::{self, Visitor, FnKind};
+use intravisit::{self, Visitor, FnKind};
 use syntax::ast_util;
 use syntax::ast::{Ident, Name, NodeId, DUMMY_NODE_ID};
 use syntax::codemap::Span;
@@ -145,12 +145,26 @@ pub fn unop_to_string(op: UnOp) -> &'static str {
 }
 
 pub struct IdVisitor<'a, O: 'a> {
-    pub operation: &'a mut O,
-    pub pass_through_items: bool,
-    pub visited_outermost: bool,
+    operation: &'a mut O,
+
+    // In general, the id visitor visits the contents of an item, but
+    // not including nested trait/impl items, nor other nested items.
+    // The base visitor itself always skips nested items, but not
+    // trait/impl items. This means in particular that if you start by
+    // visiting a trait or an impl, you should not visit the
+    // trait/impl items respectively.  This is handled by setting
+    // `skip_members` to true when `visit_item` is on the stack. This
+    // way, if the user begins by calling `visit_trait_item`, we will
+    // visit the trait item, but if they begin with `visit_item`, we
+    // won't visit the (nested) trait items.
+    skip_members: bool,
 }
 
 impl<'a, O: ast_util::IdVisitingOperation> IdVisitor<'a, O> {
+    pub fn new(operation: &'a mut O) -> IdVisitor<'a, O> {
+        IdVisitor { operation: operation, skip_members: false }
+    }
+
     fn visit_generics_helper(&mut self, generics: &Generics) {
         for type_parameter in generics.ty_params.iter() {
             self.operation.visit_id(type_parameter.id)
@@ -164,22 +178,17 @@ impl<'a, O: ast_util::IdVisitingOperation> IdVisitor<'a, O> {
 impl<'a, 'v, O: ast_util::IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O> {
     fn visit_mod(&mut self, module: &Mod, _: Span, node_id: NodeId) {
         self.operation.visit_id(node_id);
-        visit::walk_mod(self, module)
+        intravisit::walk_mod(self, module)
     }
 
     fn visit_foreign_item(&mut self, foreign_item: &ForeignItem) {
         self.operation.visit_id(foreign_item.id);
-        visit::walk_foreign_item(self, foreign_item)
+        intravisit::walk_foreign_item(self, foreign_item)
     }
 
     fn visit_item(&mut self, item: &Item) {
-        if !self.pass_through_items {
-            if self.visited_outermost {
-                return;
-            } else {
-                self.visited_outermost = true
-            }
-        }
+        assert!(!self.skip_members);
+        self.skip_members = true;
 
         self.operation.visit_id(item.id);
         match item.node {
@@ -196,45 +205,44 @@ impl<'a, 'v, O: ast_util::IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O>
             }
             _ => {}
         }
+        intravisit::walk_item(self, item);
 
-        visit::walk_item(self, item);
-
-        self.visited_outermost = false
+        self.skip_members = false;
     }
 
     fn visit_local(&mut self, local: &Local) {
         self.operation.visit_id(local.id);
-        visit::walk_local(self, local)
+        intravisit::walk_local(self, local)
     }
 
     fn visit_block(&mut self, block: &Block) {
         self.operation.visit_id(block.id);
-        visit::walk_block(self, block)
+        intravisit::walk_block(self, block)
     }
 
     fn visit_stmt(&mut self, statement: &Stmt) {
         self.operation.visit_id(stmt_id(statement));
-        visit::walk_stmt(self, statement)
+        intravisit::walk_stmt(self, statement)
     }
 
     fn visit_pat(&mut self, pattern: &Pat) {
         self.operation.visit_id(pattern.id);
-        visit::walk_pat(self, pattern)
+        intravisit::walk_pat(self, pattern)
     }
 
     fn visit_expr(&mut self, expression: &Expr) {
         self.operation.visit_id(expression.id);
-        visit::walk_expr(self, expression)
+        intravisit::walk_expr(self, expression)
     }
 
     fn visit_ty(&mut self, typ: &Ty) {
         self.operation.visit_id(typ.id);
-        visit::walk_ty(self, typ)
+        intravisit::walk_ty(self, typ)
     }
 
     fn visit_generics(&mut self, generics: &Generics) {
         self.visit_generics_helper(generics);
-        visit::walk_generics(self, generics)
+        intravisit::walk_generics(self, generics)
     }
 
     fn visit_fn(&mut self,
@@ -243,14 +251,6 @@ impl<'a, 'v, O: ast_util::IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O>
                 block: &'v Block,
                 span: Span,
                 node_id: NodeId) {
-        if !self.pass_through_items {
-            match function_kind {
-                FnKind::Method(..) if self.visited_outermost => return,
-                FnKind::Method(..) => self.visited_outermost = true,
-                _ => {}
-            }
-        }
-
         self.operation.visit_id(node_id);
 
         match function_kind {
@@ -267,18 +267,12 @@ impl<'a, 'v, O: ast_util::IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O>
             self.operation.visit_id(argument.id)
         }
 
-        visit::walk_fn(self, function_kind, function_declaration, block, span);
-
-        if !self.pass_through_items {
-            if let FnKind::Method(..) = function_kind {
-                self.visited_outermost = false;
-            }
-        }
+        intravisit::walk_fn(self, function_kind, function_declaration, block, span);
     }
 
     fn visit_struct_field(&mut self, struct_field: &StructField) {
         self.operation.visit_id(struct_field.node.id);
-        visit::walk_struct_field(self, struct_field)
+        intravisit::walk_struct_field(self, struct_field)
     }
 
     fn visit_variant_data(&mut self,
@@ -288,17 +282,21 @@ impl<'a, 'v, O: ast_util::IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O>
                           _: NodeId,
                           _: Span) {
         self.operation.visit_id(struct_def.id());
-        visit::walk_struct_def(self, struct_def);
+        intravisit::walk_struct_def(self, struct_def);
     }
 
     fn visit_trait_item(&mut self, ti: &hir::TraitItem) {
-        self.operation.visit_id(ti.id);
-        visit::walk_trait_item(self, ti);
+        if !self.skip_members {
+            self.operation.visit_id(ti.id);
+            intravisit::walk_trait_item(self, ti);
+        }
     }
 
     fn visit_impl_item(&mut self, ii: &hir::ImplItem) {
-        self.operation.visit_id(ii.id);
-        visit::walk_impl_item(self, ii);
+        if !self.skip_members {
+            self.operation.visit_id(ii.id);
+            intravisit::walk_impl_item(self, ii);
+        }
     }
 
     fn visit_lifetime(&mut self, lifetime: &Lifetime) {
@@ -311,7 +309,7 @@ impl<'a, 'v, O: ast_util::IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O>
 
     fn visit_trait_ref(&mut self, trait_ref: &TraitRef) {
         self.operation.visit_id(trait_ref.ref_id);
-        visit::walk_trait_ref(self, trait_ref);
+        intravisit::walk_trait_ref(self, trait_ref);
     }
 }
 
@@ -323,11 +321,7 @@ pub fn compute_id_range_for_fn_body(fk: FnKind,
                                     id: NodeId)
                                     -> ast_util::IdRange {
     let mut visitor = ast_util::IdRangeComputingVisitor { result: ast_util::IdRange::max() };
-    let mut id_visitor = IdVisitor {
-        operation: &mut visitor,
-        pass_through_items: false,
-        visited_outermost: false,
-    };
+    let mut id_visitor = IdVisitor::new(&mut visitor);
     id_visitor.visit_fn(fk, decl, body, sp, id);
     id_visitor.operation.result
 }