Implement `gn analyze`.

tools/gn/graph.h

Index: tools/gn/graph.h
diff --git a/tools/gn/graph.h b/tools/gn/graph.h
new file mode 100644
index 0000000000000000000000000000000000000000..c96186d7d60ea8e2336ce4e8b8abd1fde0c800a5
--- /dev/null
+++ b/tools/gn/graph.h
@@ -0,0 +1,94 @@
+// Copyright (c) 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef TOOLS_GN_GRAPH_H_
+#define TOOLS_GN_GRAPH_H_
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include "tools/gn/label.h"
+#include "tools/gn/source_file.h"
+#include "tools/gn/target.h"
+
+using DepMap = std::multimap<const Target*, const Target*>;

[brettw, 2016/08/22 21:08:27]

These shouldn't be added to the global namespace. I'd put them inside the class
right after "public".

[Dirk Pranke, 2016/08/23 19:27:31]

Good catch, agreed. 

Some of the names are used in the free functions in the .cc file, so I'll
probably need to play with this a bit.

+using LabelSet = std::set<const Label*>;

[brettw, 2016/08/22 21:08:27]

This should be std::set<Label> since labels have no particular identity and can
be efficiently copied. I don't really know who manages the storage for these
pointers either. The rest of the pointers are OK since those are big things
whose lifetimes are managed by somebody else.

[Dirk Pranke, 2016/08/23 19:27:31]

Ack. My thinking was simply that "someone else" needed to owns the elements, but
a vector of values is better.

+using SourceFileSet = std::set<const SourceFile*>;
+using TargetSet = std::set<const Target*>;
+using TargetVector = std::vector<const Target*>;
+
+// A Graph represents a fully populated build graph. It is used
+// to answer queries for the `refs` and `analyze` commands, where we
+// need to look at the graph in ways that can't easily be determined
+// from just a single Target.
+class Graph {

[brettw, 2016/08/22 21:08:27]

Class name should match file name suggestion from above.

[Dirk Pranke, 2016/08/23 19:27:31]

Acknowledged.

+ public:
+  Graph(const TargetVector& all_targets, const Label& default_toolchain);
+  ~Graph();
+
+  const Label& default_toolchain() { return default_toolchain_; };
+
+  // Returns the roots of the build graph: the set of targets that
+  // no other target depends on.
+  TargetSet& roots() { return roots_; };
+
+  // Returns the set of all targets that might be affected, directly or
+  // indirectly, by modifications to the given source files.
+  TargetSet AllAffectedTargets(const SourceFileSet& source_files);
+
+  // Returns the set of labels that do not refer to objects in the graph.
+  LabelSet InvalidLabels(const LabelSet& labels);
+
+  // Returns the set of all targets that have a label in the given set.
+  // Invalid (or missing) labels will be ignored.
+  TargetSet TargetsFor(const LabelSet& labels);
+
+  // Returns a pruned set of the given targets, meaning that for each of the
+  // given targets,
+  // - if the target is not a group, add it to the set
+  // - if the target is a group, recursively prune each dependency and add
+  //   its pruned results to the set.
+  //
+  // For example, if we had:
+  //
+  //   group("foobar") { deps = [ ":foo", ":bar" ] }
+  //   group("bar") { deps = [ ":baz", ":quux" ] }
+  //   executable("foo") { ... }
+  //   executable("baz") { ... }
+  //   executable("quux") { ... }
+  //
+  // Then the pruned version of {"foobar"} would be {":foo", ":baz", ":quux"}.
+  // This is used by the analyze command in order to only build the affected
+  // dependencies of a group (and not also build the unaffected ones).
+  TargetSet Prune(const TargetSet& targets);
+
+ private:
+  // Prunes an individual target and adds the results to pruned (see Prune(),
+  // above).
+  void PruneTarget(const Target*, TargetSet& seen, TargetSet& pruned);

[brettw, 2016/08/22 21:08:27]

Don't pass non-const refs. The style guide says these should be pointers since
they're really out params.

[Dirk Pranke, 2016/08/23 19:27:31]

Good catch. (They're in-out parameters, but, yeah, mutated).

+
+  bool TargetRefersToFile(const Target* target, const SourceFile* file);
+
+  void AddTargetsDirectlyReferringToFileTo(const SourceFile* file,
+                                           TargetSet* matches);
+
+  void AddAllRefsTo(const Target* target, TargetSet* matches);
+
+  std::vector<const Target*> all_targets_;
+  std::map<const Label, const Target*> labels_to_targets_;
+  Label default_toolchain_;
+  std::set<const Target*> roots_;
+
+  // Maps targets to the list of targets that depend on them.
+  DepMap dep_map_;
+};
+
+// Given a graph and a JSON-formatted string containing lists of files
+// and targets, figures out which targets would be affected by modifications
+// to the files. See command_analyze.cc for expected formats of the files
+// and a full description of the behavior.
+Err Analyze(Graph& graph, const std::string& input, std::string* output);

[brettw, 2016/08/22 21:08:27]

Having "graph" be a non-const ref is against the style guide. I'd say it should
be const but I assume this is what you're complaining about with the caching. Is
there any reason this can't be a member of Grap?

[Dirk Pranke, 2016/08/23 19:27:31]

No particular reason apart from keeping the class minimal (the implementation of
analyze can and should be done using only the public members), but perhaps
that's not a very strong reason.

Yes, it's not const because of the caches.

+
+#endif  // TOOLS_GN_GRAPH_H_