auto merge of #16326 : pnkfelix/rust/fsk-add-path-suffix-lookup, r=huonw

Extended `ast_map::Map` with an iterator over all node id's that match a path suffix.

Extended pretty printer to let users choose particular items to pretty print, either by indicating an integer node-id, or by providing a path suffix.

 * Example 1: the suffix `typeck::check::check_struct` matches the item with the path `rustc::middle::typeck::check::check_struct` when compiling the `rustc` crate.

 * Example 2: the suffix `and` matches `core::option::Option::and` and `core::result::Result::and` when compiling the `core` crate.

Refactored `pprust` slightly to support the pretty printer changes.

(See individual commits for more description.)

2 files changed, 212 insertions, 25 deletions

diff --git a/src/libsyntax/ast_map/mod.rs b/src/libsyntax/ast_map/mod.rs
index 67de8e7aba1..881ee4fd8d1 100644
--- a/src/libsyntax/ast_map/mod.rs
+++ b/src/libsyntax/ast_map/mod.rs
@@ -11,7 +11,7 @@
 use abi;
 use ast::*;
 use ast_util;
-use codemap::Span;
+use codemap::{Span, Spanned};
 use fold::Folder;
 use fold;
 use parse::token;
@@ -21,6 +21,7 @@ use util::small_vector::SmallVector;
 use std::cell::RefCell;
 use std::fmt;
 use std::gc::{Gc, GC};
+use std::io::IoResult;
 use std::iter;
 use std::slice;
 
@@ -203,6 +204,10 @@ pub struct Map {
 }
 
 impl Map {
+    fn entry_count(&self) -> uint {
+        self.map.borrow().len()
+    }
+
     fn find_entry(&self, id: NodeId) -> Option<MapEntry> {
         let map = self.map.borrow();
         if map.len() > id as uint {
@@ -405,6 +410,20 @@ impl Map {
         f(attrs)
     }
 
+    /// Returns an iterator that yields the node id's with paths that
+    /// match `parts`.  (Requires `parts` is non-empty.)
+    ///
+    /// For example, if given `parts` equal to `["bar", "quux"]`, then
+    /// the iterator will produce node id's for items with paths
+    /// such as `foo::bar::quux`, `bar::quux`, `other::bar::quux`, and
+    /// any other such items it can find in the map.
+    pub fn nodes_matching_suffix<'a, S:Str>(&'a self, parts: &'a [S]) -> NodesMatchingSuffix<'a,S> {
+        NodesMatchingSuffix { map: self,
+                              item_name: parts.last().unwrap(),
+                              where: parts.slice_to(parts.len() - 1),
+                              idx: 0 }
+    }
+
     pub fn opt_span(&self, id: NodeId) -> Option<Span> {
         let sp = match self.find(id) {
             Some(NodeItem(item)) => item.span,
@@ -438,6 +457,119 @@ impl Map {
     }
 }
 
+pub struct NodesMatchingSuffix<'a, S> {
+    map: &'a Map,
+    item_name: &'a S,
+    where: &'a [S],
+    idx: NodeId,
+}
+
+impl<'a,S:Str> NodesMatchingSuffix<'a,S> {
+    /// Returns true only if some suffix of the module path for parent
+    /// matches `self.where`.
+    ///
+    /// In other words: let `[x_0,x_1,...,x_k]` be `self.where`;
+    /// returns true if parent's path ends with the suffix
+    /// `x_0::x_1::...::x_k`.
+    fn suffix_matches(&self, parent: NodeId) -> bool {
+        let mut cursor = parent;
+        for part in self.where.iter().rev() {
+            let (mod_id, mod_name) = match find_first_mod_parent(self.map, cursor) {
+                None => return false,
+                Some((node_id, name)) => (node_id, name),
+            };
+            if part.as_slice() != mod_name.as_str() {
+                return false;
+            }
+            cursor = self.map.get_parent(mod_id);
+        }
+        return true;
+
+        // Finds the first mod in parent chain for `id`, along with
+        // that mod's name.
+        //
+        // If `id` itself is a mod named `m` with parent `p`, then
+        // returns `Some(id, m, p)`.  If `id` has no mod in its parent
+        // chain, then returns `None`.
+        fn find_first_mod_parent<'a>(map: &'a Map, mut id: NodeId) -> Option<(NodeId, Name)> {
+            loop {
+                match map.find(id) {
+                    None => return None,
+                    Some(NodeItem(item)) if item_is_mod(&*item) =>
+                        return Some((id, item.ident.name)),
+                    _ => {}
+                }
+                let parent = map.get_parent(id);
+                if parent == id { return None }
+                id = parent;
+            }
+
+            fn item_is_mod(item: &Item) -> bool {
+                match item.node {
+                    ItemMod(_) => true,
+                    _ => false,
+                }
+            }
+        }
+    }
+
+    // We are looking at some node `n` with a given name and parent
+    // id; do their names match what I am seeking?
+    fn matches_names(&self, parent_of_n: NodeId, name: Name) -> bool {
+        name.as_str() == self.item_name.as_slice() &&
+            self.suffix_matches(parent_of_n)
+    }
+}
+
+impl<'a,S:Str> Iterator<NodeId> for NodesMatchingSuffix<'a,S> {
+    fn next(&mut self) -> Option<NodeId> {
+        loop {
+            let idx = self.idx;
+            if idx as uint >= self.map.entry_count() {
+                return None;
+            }
+            self.idx += 1;
+            let (p, name) = match self.map.find_entry(idx) {
+                Some(EntryItem(p, n))        => (p, n.name()),
+                Some(EntryForeignItem(p, n)) => (p, n.name()),
+                Some(EntryTraitMethod(p, n)) => (p, n.name()),
+                Some(EntryMethod(p, n))      => (p, n.name()),
+                Some(EntryVariant(p, n))     => (p, n.name()),
+                _ => continue,
+            };
+            if self.matches_names(p, name) {
+                return Some(idx)
+            }
+        }
+    }
+}
+
+trait Named {
+    fn name(&self) -> Name;
+}
+
+impl<T:Named> Named for Spanned<T> { fn name(&self) -> Name { self.node.name() } }
+
+impl Named for Item { fn name(&self) -> Name { self.ident.name } }
+impl Named for ForeignItem { fn name(&self) -> Name { self.ident.name } }
+impl Named for Variant_ { fn name(&self) -> Name { self.name.name } }
+impl Named for TraitMethod {
+    fn name(&self) -> Name {
+        match *self {
+            Required(ref tm) => tm.ident.name,
+            Provided(m) => m.name(),
+        }
+    }
+}
+impl Named for Method {
+    fn name(&self) -> Name {
+        match self.node {
+            MethDecl(i, _, _, _, _, _, _, _) => i.name,
+            MethMac(_) => fail!("encountered unexpanded method macro."),
+        }
+    }
+}
+
 pub trait FoldOps {
     fn new_id(&self, id: NodeId) -> NodeId {
         id
@@ -688,6 +820,34 @@ pub fn map_decoded_item<F: FoldOps>(map: &Map,
     ii
 }
 
+pub trait NodePrinter {
+    fn print_node(&mut self, node: &Node) -> IoResult<()>;
+}
+
+impl<'a> NodePrinter for pprust::State<'a> {
+    fn print_node(&mut self, node: &Node) -> IoResult<()> {
+        match *node {
+            NodeItem(a)        => self.print_item(&*a),
+            NodeForeignItem(a) => self.print_foreign_item(&*a),
+            NodeTraitMethod(a) => self.print_trait_method(&*a),
+            NodeMethod(a)      => self.print_method(&*a),
+            NodeVariant(a)     => self.print_variant(&*a),
+            NodeExpr(a)        => self.print_expr(&*a),
+            NodeStmt(a)        => self.print_stmt(&*a),
+            NodePat(a)         => self.print_pat(&*a),
+            NodeBlock(a)       => self.print_block(&*a),
+            NodeLifetime(a)    => self.print_lifetime(&*a),
+
+            // these cases do not carry enough information in the
+            // ast_map to reconstruct their full structure for pretty
+            // printing.
+            NodeLocal(_)       => fail!("cannot print isolated Local"),
+            NodeArg(_)         => fail!("cannot print isolated Arg"),
+            NodeStructCtor(_)  => fail!("cannot print isolated StructCtor"),
+        }
+    }
+}
+
 fn node_id_to_string(map: &Map, id: NodeId) -> String {
     match map.find(id) {
         Some(NodeItem(item)) => {
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index d60e4cb3b54..9d4b7343c8a 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -97,35 +97,62 @@ pub fn print_crate<'a>(cm: &'a CodeMap,
                        out: Box<io::Writer>,
                        ann: &'a PpAnn,
                        is_expanded: bool) -> IoResult<()> {
-    let (cmnts, lits) = comments::gather_comments_and_literals(
-        span_diagnostic,
-        filename,
-        input
-    );
-    let mut s = State {
-        s: pp::mk_printer(out, default_columns),
-        cm: Some(cm),
-        comments: Some(cmnts),
-        // If the code is post expansion, don't use the table of
-        // literals, since it doesn't correspond with the literals
-        // in the AST anymore.
-        literals: if is_expanded {
-            None
-        } else {
-            Some(lits)
-        },
-        cur_cmnt_and_lit: CurrentCommentAndLiteral {
-            cur_cmnt: 0,
-            cur_lit: 0
-        },
-        boxes: Vec::new(),
-        ann: ann
-    };
+    let mut s = State::new_from_input(cm,
+                                      span_diagnostic,
+                                      filename,
+                                      input,
+                                      out,
+                                      ann,
+                                      is_expanded);
     try!(s.print_mod(&krate.module, krate.attrs.as_slice()));
     try!(s.print_remaining_comments());
     eof(&mut s.s)
 }
 
+impl<'a> State<'a> {
+    pub fn new_from_input(cm: &'a CodeMap,
+                          span_diagnostic: &diagnostic::SpanHandler,
+                          filename: String,
+                          input: &mut io::Reader,
+                          out: Box<io::Writer>,
+                          ann: &'a PpAnn,
+                          is_expanded: bool) -> State<'a> {
+        let (cmnts, lits) = comments::gather_comments_and_literals(
+            span_diagnostic,
+            filename,
+            input);
+
+        State::new(
+            cm,
+            out,
+            ann,
+            Some(cmnts),
+            // If the code is post expansion, don't use the table of
+            // literals, since it doesn't correspond with the literals
+            // in the AST anymore.
+            if is_expanded { None } else { Some(lits) })
+    }
+
+    pub fn new(cm: &'a CodeMap,
+               out: Box<io::Writer>,
+               ann: &'a PpAnn,
+               comments: Option<Vec<comments::Comment>>,
+               literals: Option<Vec<comments::Literal>>) -> State<'a> {
+        State {
+            s: pp::mk_printer(out, default_columns),
+            cm: Some(cm),
+            comments: comments,
+            literals: literals,
+            cur_cmnt_and_lit: CurrentCommentAndLiteral {
+                cur_cmnt: 0,
+                cur_lit: 0
+            },
+            boxes: Vec::new(),
+            ann: ann
+        }
+    }
+}
+
 pub fn to_string(f: |&mut State| -> IoResult<()>) -> String {
     let mut s = rust_printer(box MemWriter::new());
     f(&mut s).unwrap();