Add the 'targets' tool.

This tool list targets by depth or by rule. It can be useful:
- for shell completion script ;
- to know what are the primary targets: ninja -t targets depth 1 ;
- to know targets that are linked: ninja -t rule link ;
- when debugging.

It works by first listing the root nodes and then following the input nodes
of their in edge.

4 files changed, 136 insertions, 1 deletions

diff --git a/manual.asciidoc b/manual.asciidoc
index 80dfc50..8bfc2e7 100644
--- a/manual.asciidoc
+++ b/manual.asciidoc
@@ -313,6 +313,18 @@ graph layout tool.  Use it like: +ninja -t graph _target_ | dot -Tpng
 -ograph.png /dev/stdin+ .  In the Ninja source tree, `ninja graph`
 generates an image for Ninja itself.
 
+`targets`:: output a list of targets either by rule or by depth.  If used
+like this +ninja -t targets rule _name_+ it prints the list of targets
+using the given rule to be built.  If no rule is given, it prints the source
+files (the leaf of the graph).  If used like this
++ninja -t targets depth _digit_+ it
+prints the list of targets in a depth-first manner starting by the root
+targets (the ones with no outputs). Indentation is used to mark dependencies.
+If the depth is zero it prints all targets. If no arguments are provided
++ninja -t targets depth 1+ is assumed. In this mode targets may be listed
+several times. If used like this +ninja -t targets all+ it
+prints all the targets available without indentation and it is way faster
+than the _depth_ mode.  It returns non-zero if an error occurs.
 
 Ninja file reference
 --------------------
diff --git a/src/ninja.cc b/src/ninja.cc
index dbbf05e..0bd51d5 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -58,7 +58,8 @@ void usage(const BuildConfig& config) {
 "  -t TOOL  run a subtool.  tools are:\n"
 "             browse  browse dependency graph in a web browser\n"
 "             graph   output graphviz dot file for targets\n"
-"             query   show inputs/outputs for a path\n",
+"             query   show inputs/outputs for a path\n"
+"             targets list targets by their rule or depth in the DAG\n",
           config.parallelism);
 }
 
@@ -161,6 +162,105 @@ int CmdBrowse(State* state, int argc, char* argv[]) {
   return 1;
 }
 
+int CmdTargetsList(const vector<Node*>& nodes, int depth, int indent) {
+  for (vector<Node*>::const_iterator n = nodes.begin();
+       n != nodes.end();
+       ++n) {
+    for (int i = 0; i < indent; ++i)
+      printf("  ");
+    const char* target = (*n)->file_->path_.c_str();
+    if ((*n)->in_edge_) {
+      printf("%s: %s\n", target, (*n)->in_edge_->rule_->name_.c_str());
+      if (depth > 1 || depth <= 0)
+        CmdTargetsList((*n)->in_edge_->inputs_, depth - 1, indent + 1);
+    } else {
+      printf("%s\n", target);
+    }
+  }
+  return 0;
+}
+
+int CmdTargetsList(const vector<Node*>& nodes, int depth) {
+  return CmdTargetsList(nodes, depth, 0);
+}
+
+int CmdTargetsSourceList(State* state) {
+  for (vector<Edge*>::iterator e = state->edges_.begin();
+       e != state->edges_.end();
+       ++e)
+    for (vector<Node*>::iterator inps = (*e)->inputs_.begin();
+         inps != (*e)->inputs_.end();
+         ++inps)
+      if (!(*inps)->in_edge_)
+        printf("%s\n", (*inps)->file_->path_.c_str());
+  return 0;
+}
+
+int CmdTargetsList(State* state, const string& rule_name) {
+  set<string> rules;
+  // Gather the outputs.
+  for (vector<Edge*>::iterator e = state->edges_.begin();
+       e != state->edges_.end();
+       ++e)
+    if ((*e)->rule_->name_ == rule_name)
+      for (vector<Node*>::iterator out_node = (*e)->outputs_.begin();
+           out_node != (*e)->outputs_.end();
+           ++out_node)
+        rules.insert((*out_node)->file_->path_);
+  // Print them.
+  for (set<string>::const_iterator i = rules.begin();
+       i != rules.end();
+       ++i)
+    printf("%s\n", (*i).c_str());
+  return 0;
+}
+
+int CmdTargetsList(State* state) {
+  for (vector<Edge*>::iterator e = state->edges_.begin();
+       e != state->edges_.end();
+       ++e)
+    for (vector<Node*>::iterator out_node = (*e)->outputs_.begin();
+         out_node != (*e)->outputs_.end();
+         ++out_node)
+      printf("%s: %s\n",
+             (*out_node)->file_->path_.c_str(),
+             (*e)->rule_->name_.c_str());
+  return 0;
+}
+
+int CmdTargets(State* state, int argc, char* argv[]) {
+  int depth = 1;
+  if (argc >= 1) {
+    string mode = argv[0];
+    if (mode == "rule") {
+      string rule;
+      if (argc > 1)
+        rule = argv[1];
+      if (rule.empty())
+        return CmdTargetsSourceList(state);
+      else
+        return CmdTargetsList(state, rule);
+    } else if (mode == "depth") {
+      if (argc > 1)
+        depth = atoi(argv[1]);
+    } else if (mode == "all") {
+      return CmdTargetsList(state);
+    } else {
+      Error("unknown target tool mode '%s'", mode.c_str());
+      return 1;
+    }
+  }
+
+  string err;
+  vector<Node*> root_nodes = state->RootNodes(&err);
+  if (err.empty()) {
+    return CmdTargetsList(root_nodes, depth);
+  } else {
+    Error("%s", err.c_str());
+    return 1;
+  }
+}
+
 int main(int argc, char** argv) {
   BuildConfig config;
   const char* input_file = "build.ninja";
@@ -226,6 +326,8 @@ int main(int argc, char** argv) {
       return CmdQuery(&state, argc, argv);
     if (tool == "browse")
       return CmdBrowse(&state, argc, argv);
+    if (tool == "targets")
+      return CmdTargets(&state, argc, argv);
     Error("unknown tool '%s'", tool.c_str());
   }
 
diff --git a/src/ninja.h b/src/ninja.h
index 2590e63..f387ffc 100644
--- a/src/ninja.h
+++ b/src/ninja.h
@@ -73,6 +73,9 @@ struct State {
   Node* LookupNode(const string& path);
   void AddIn(Edge* edge, const string& path);
   void AddOut(Edge* edge, const string& path);
+  /// @return the root node(s) of the graph. (Root nodes have no input edges).
+  /// @param error where to write the error message if somethings went wrong.
+  vector<Node*> RootNodes(string* error);
 
   StatCache stat_cache_;
   /// All the rules used in the graph.
diff --git a/src/ninja_jumble.cc b/src/ninja_jumble.cc
index fd2ee18..e6a0de6 100644
--- a/src/ninja_jumble.cc
+++ b/src/ninja_jumble.cc
@@ -182,3 +182,21 @@ void State::AddOut(Edge* edge, const string& path) {
   }
   node->in_edge_ = edge;
 }
+
+vector<Node*> State::RootNodes(string* error)
+{
+  assert(error);
+  vector<Node*> root_nodes;
+  // Search for nodes with no output.
+  for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
+    for (vector<Node*>::iterator outs = (*e)->outputs_.begin();
+         outs != (*e)->outputs_.end();
+         ++outs)
+      if ((*outs)->out_edges_.size() == 0)
+        root_nodes.push_back(*outs);
+  if (!edges_.empty() && root_nodes.empty()) {
+    *error = "could not determine root nodes of build graph";
+  }
+  assert(edges_.empty() || !root_nodes.empty());
+  return root_nodes;
+}