Implement `gn analyze`.

tools/gn/analyzer.h

Index: tools/gn/analyzer.h
diff --git a/tools/gn/analyzer.h b/tools/gn/analyzer.h
new file mode 100644
index 0000000000000000000000000000000000000000..9e9439c2fc8bfcfc56d742ef0a0be21ca0dd35f2
--- /dev/null
+++ b/tools/gn/analyzer.h
@@ -0,0 +1,97 @@
+// Copyright (c) 2016 The Chromium Authors. All rights reserved.

[brettw, 2016/08/25 21:22:30]

No (c)

[Dirk Pranke, 2016/08/26 00:34:14]

Done.

+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef TOOLS_GN_ANALYZER_H_
+#define TOOLS_GN_ANALYZER_H_
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include "tools/gn/builder.h"
+#include "tools/gn/label.h"
+#include "tools/gn/source_file.h"
+#include "tools/gn/target.h"
+
+// An Analyzer can answer questions about a 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 Analyzer {
+ public:
+  using LabelSet = std::set<Label>;
+  using SourceFileSet = std::set<const SourceFile*>;
+  using TargetSet = std::set<const Target*>;
+
+  Analyzer(const Builder& builder);

[brettw, 2016/08/25 21:22:30]

Prepend "explicit" since this is a one-arg constructor.

[Dirk Pranke, 2016/08/26 00:34:13]

Done.

+  ~Analyzer();
+
+  // Figures out from a Buider and a JSON-formatted string containing lists
+  // of files and targets, which targets would be affected by modifications
+  // to the files . See the help text for the analyze command (kAnalyze_Help)
+  // for the specification of the input and output string formats and the
+  // expected behavior of the method.
+  std::string Analyze(const std::string& input, Err* err);

[brettw, 2016/08/25 21:22:30]

I don't see any caching in this object any more, so I think all the functions on
this object can be marked "const".

[Dirk Pranke, 2016/08/26 00:34:13]

Yup, I got rid it (or, rather, pushed it into the constructor).

Will do.

+
+ private:
+  using DepMap = std::multimap<const Target*, const Target*>;
+
+  // 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 filtered 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 filter each dependency and add
+  //   its filtered 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 filtered 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).
+  //
+  // This filtering behavior is also known as "pruning" the list of targets.
+  TargetSet Filter(const TargetSet& targets);

[brettw, 2016/08/25 21:22:30]

Would "CollapseGroups" or "FlattenGroups" be a better name for this function?

[Dirk Pranke, 2016/08/26 00:34:13]

No, I don't think those are better. If the concern is that "Filter" is too
generic, I'd probably switch it back to "Prune". However, I'll leave it as
"Filter" for now and we can change in a follow-up CL if need be.

+
+  // Filter an individual target and adds the results to filtered
+  // (see Filter(), above).
+  void FilterTarget(const Target*, TargetSet* seen, TargetSet* filtered);
+
+  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_;
+};
+
+#endif  // TOOLS_GN_ANALYZER_H_