Implement `gn analyze`.

tools/gn/graph.cc

Index: tools/gn/graph.cc
diff --git a/tools/gn/graph.cc b/tools/gn/graph.cc
new file mode 100644
index 0000000000000000000000000000000000000000..79df8e6bddc0bbb93eb37188d3a6427d6f07475e
--- /dev/null
+++ b/tools/gn/graph.cc
@@ -0,0 +1,375 @@
+// Copyright (c) 2016 The Chromium Authors. All rights reserved.

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

No (c)

+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "tools/gn/graph.h"
+
+#include <algorithm>
+#include <iterator>
+#include <set>
+#include <vector>
+
+#include "base/json/json_reader.h"
+#include "base/json/json_writer.h"
+#include "base/memory/ptr_util.h"
+#include "base/strings/string_util.h"
+#include "base/strings/string_util.h"
+#include "base/values.h"
+#include "tools/gn/deps_iterator.h"
+#include "tools/gn/err.h"
+#include "tools/gn/location.h"
+#include "tools/gn/source_file.h"
+#include "tools/gn/target.h"
+
+Graph::Graph(const TargetVector& all_targets, const Label& default_toolchain)
+    : all_targets_(all_targets), default_toolchain_(default_toolchain) {
+  for (auto* target : all_targets_) {
+    labels_to_targets_[target->label()] = target;
+    for (const auto& dep_pair : target->GetDeps(Target::DEPS_ALL))
+      dep_map_.insert(std::make_pair(dep_pair.ptr, target));
+  }
+  for (const auto& target : all_targets_) {
+    if (dep_map_.find(target) == dep_map_.end())
+      roots_.insert(target);
+  }
+}
+
+Graph::~Graph() {}
+
+TargetSet Graph::Prune(const TargetSet& targets) {
+  TargetSet seen;
+  TargetSet pruned;
+  for (const auto& target : targets)
+    PruneTarget(target, seen, pruned);
+  return pruned;
+}
+
+TargetSet Graph::AllAffectedTargets(const SourceFileSet& source_files) {
+  TargetSet direct_matches;
+  for (const auto& source_file : source_files)
+    AddTargetsDirectlyReferringToFileTo(source_file, &direct_matches);
+  TargetSet all_matches;
+  for (const auto& match : direct_matches)
+    AddAllRefsTo(match, &all_matches);
+  return all_matches;
+}
+
+LabelSet Graph::InvalidLabels(const LabelSet& labels) {
+  LabelSet invalid_labels;
+  for (const auto& label : labels) {
+    if (labels_to_targets_.find(*label) == labels_to_targets_.end())
+      invalid_labels.insert(label);
+  }
+  return invalid_labels;
+}
+
+TargetSet Graph::TargetsFor(const LabelSet& labels) {
+  TargetSet targets;
+  for (const auto& label : labels) {
+    auto it = labels_to_targets_.find(*label);
+    if (it != labels_to_targets_.end())
+      targets.insert(it->second);
+  }
+  return targets;
+}
+
+void Graph::PruneTarget(const Target* target,
+                        TargetSet& seen,
+                        TargetSet& pruned) {
+  if (seen.find(target) == seen.end()) {
+    seen.insert(target);
+    if (target->output_type() != Target::GROUP) {
+      pruned.insert(target);
+    } else {
+      for (const auto& pair : target->GetDeps(Target::DEPS_ALL))
+        PruneTarget(pair.ptr, seen, pruned);
+    }
+  }
+}
+
+bool Graph::TargetRefersToFile(const Target* target, const SourceFile* file) {
+  for (const auto& cur_file : target->sources()) {
+    if (cur_file == *file)
+      return true;
+  }
+  for (const auto& cur_file : target->public_headers()) {
+    if (cur_file == *file)
+      return true;
+  }
+  for (const auto& cur_file : target->inputs()) {
+    if (cur_file == *file)
+      return true;
+  }
+  for (const auto& cur_file : target->data()) {
+    if (cur_file == file->value())
+      return true;
+    if (cur_file.back() == '/' &&
+        base::StartsWith(file->value(), cur_file, base::CompareCase::SENSITIVE))
+      return true;
+  }
+
+  if (target->action_values().script().value() == file->value())
+    return true;
+
+  std::vector<SourceFile> outputs;
+  target->action_values().GetOutputsAsSourceFiles(target, &outputs);
+  for (const auto& cur_file : outputs) {
+    if (cur_file == *file)
+      return true;
+  }
+  return false;
+}
+
+void Graph::AddTargetsDirectlyReferringToFileTo(const SourceFile* file,
+                                                TargetSet* matches) {
+  for (const auto& target : all_targets_) {
+    // Only handles targets in the default toolchain.
+    if ((target->label().GetToolchainLabel() == default_toolchain_) &&
+        TargetRefersToFile(target, file))
+      matches->insert(target);
+  }
+}
+
+void Graph::AddAllRefsTo(const Target* target, TargetSet* results) {
+  if (results->find(target) != results->end())
+    return;  // Already found this target.
+  results->insert(target);
+
+  DepMap::const_iterator dep_begin = dep_map_.lower_bound(target);
+  DepMap::const_iterator dep_end = dep_map_.upper_bound(target);
+  for (DepMap::const_iterator cur_dep = dep_begin; cur_dep != dep_end;
+       cur_dep++)
+    AddAllRefsTo(cur_dep->second, results);
+}
+
+namespace {
+
+using Inputs = struct Inputs {
+  std::vector<SourceFile> source_vec;
+  std::vector<Label> compile_vec;
+  std::vector<Label> test_vec;
+  bool compile_included_all;
+  SourceFileSet source_files;
+  LabelSet compile_labels;
+  LabelSet test_labels;
+};
+
+using Outputs = struct Outputs {
+  std::string status;
+  std::string error;
+  LabelSet compile_labels;
+  LabelSet test_labels;
+  LabelSet invalid_labels;
+};
+
+LabelSet InvalidLabels(Graph& graph, const Inputs& inputs) {
+  LabelSet invalid_labels;
+  for (const auto& label : graph.InvalidLabels(inputs.compile_labels))
+    invalid_labels.insert(label);
+  for (const auto& label : graph.InvalidLabels(inputs.test_labels))
+    invalid_labels.insert(label);
+  return invalid_labels;
+}
+
+LabelSet LabelsFor(const TargetSet& targets) {
+  LabelSet labels;
+  for (const auto& target : targets)
+    labels.insert(&target->label());
+  return labels;
+}
+
+bool AnyBuildFilesWereModified(const SourceFileSet& source_files) {
+  for (const auto& file : source_files) {
+    if (base::EndsWith(file->value(), ".gn", base::CompareCase::SENSITIVE) ||
+        base::EndsWith(file->value(), ".gni", base::CompareCase::SENSITIVE))
+      return true;
+  }
+  return false;
+}
+
+TargetSet Intersect(const TargetSet& l, const TargetSet& r) {
+  TargetSet result;
+  std::set_intersection(l.begin(), l.end(), r.begin(), r.end(),
+                        std::inserter(result, result.begin()));
+  return result;
+}
+
+Err GetStringVector(const base::DictionaryValue& dict,
+                    const std::string& key,
+                    std::vector<std::string>* strings) {
+  const base::ListValue* lst;
+  bool ret = dict.GetList(key, &lst);
+  if (!ret)
+    return Err(Location(), "Input does not have a key named \"" + key +
+                               "\" with a list value.");
+
+  strings->clear();
+  for (size_t i = 0; i < lst->GetSize(); i++) {
+    std::string s;
+    ret = lst->GetString(i, &s);
+    if (!ret)
+      return Err(Location(), "Item " + std::to_string(i) + " of \"" + key +
+                                 "\" is not a string.");
+    strings->push_back(s);
+  }
+  return Err();
+}
+
+void WriteString(base::DictionaryValue& dict,
+                 const std::string& key,
+                 const std::string& value) {
+  dict.SetString(key, value);
+};
+
+void WriteLabels(const Label& default_toolchain,
+                 base::DictionaryValue& dict,
+                 const std::string& key,
+                 const LabelSet& labels) {
+  std::vector<std::string> strings;
+  auto value = base::WrapUnique(new base::ListValue());
+  for (const auto& l : labels)
+    strings.push_back(l->GetUserVisibleName(default_toolchain));
+  std::sort(strings.begin(), strings.end());
+  value->AppendStrings(strings);
+  dict.Set(key, std::move(value));
+}
+
+Label StringToLabel(const Label& default_toolchain, const std::string path) {
+  SourceDir source_root("//");
+  Err err;
+  Value v(nullptr, Value::STRING);
+  v.string_value() = path;
+  return Label::Resolve(source_root, default_toolchain, v, &err);
+}
+
+Err JSONToInputs(const Label& default_toolchain,
+                 const std::string input,
+                 Inputs* inputs) {
+  int error_code_out;
+  std::string error_msg_out;
+  int error_line_out;
+  int error_column_out;
+  std::unique_ptr<base::Value> value = base::JSONReader().ReadAndReturnError(
+      input, base::JSONParserOptions::JSON_PARSE_RFC, &error_code_out,
+      &error_msg_out, &error_line_out, &error_column_out);
+  if (value == nullptr)
+    return Err(Location(), "Input is not valid JSON:" + error_msg_out);
+
+  const base::DictionaryValue* dict;
+  if (!value->GetAsDictionary(&dict))
+    return Err(Location(), "Input is not a dictionary.");
+
+  std::vector<std::string> strings;
+  Err err = GetStringVector(*dict, "files", &strings);
+  if (err.has_error())
+    return err;
+  for (auto s : strings)
+    inputs->source_vec.push_back(SourceFile(s));
+
+  err = GetStringVector(*dict, "compile_targets", &strings);
+  if (err.has_error())
+    return err;
+
+  inputs->compile_included_all = false;
+  for (auto& s : strings) {
+    if (s == "all")
+      inputs->compile_included_all = true;
+    else {
+      inputs->compile_vec.push_back(StringToLabel(default_toolchain, s));
+    }
+  }
+
+  err = GetStringVector(*dict, "test_targets", &strings);
+  if (err.has_error())
+    return err;
+  for (auto& s : strings)
+    inputs->test_vec.push_back(StringToLabel(default_toolchain, s));
+
+  for (auto& s : inputs->source_vec)
+    inputs->source_files.insert(&s);
+  for (auto& l : inputs->compile_vec)
+    inputs->compile_labels.insert(&l);
+  for (auto& l : inputs->test_vec)
+    inputs->test_labels.insert(&l);
+  return Err();
+}
+
+void OutputsToJSON(const Label& default_toolchain,
+                   const Outputs& outputs,
+                   std::string* output) {
+  auto value = base::MakeUnique<base::DictionaryValue>();
+
+  if (outputs.error.size()) {
+    WriteString(*value, "error", outputs.error);
+    WriteLabels(default_toolchain, *value, "invalid_targets",
+                outputs.invalid_labels);
+  } else {
+    WriteString(*value, "status", outputs.status);
+    WriteLabels(default_toolchain, *value, "compile_targets",
+                outputs.compile_labels);
+    WriteLabels(default_toolchain, *value, "test_targets", outputs.test_labels);
+  }
+
+  base::JSONWriter::WriteWithOptions(
+      *value.get(), base::JSONWriter::OPTIONS_PRETTY_PRINT, output);
+}
+
+}  // namespace
+
+Err Analyze(Graph& graph, const std::string& input, std::string* output) {
+  Inputs inputs;
+  Outputs outputs;
+  const Label default_toolchain = graph.default_toolchain();
+
+  Err err = JSONToInputs(default_toolchain, input, &inputs);
+  if (err.has_error())
+    return err;
+
+  LabelSet invalid_labels = InvalidLabels(graph, inputs);
+  if (!invalid_labels.empty()) {
+    outputs.error = "Invalid targets";
+    outputs.invalid_labels = invalid_labels;
+    OutputsToJSON(default_toolchain, outputs, output);
+    return Err();
+  }
+
+  TargetSet affected_targets = graph.AllAffectedTargets(inputs.source_files);
+  if (affected_targets.empty()) {
+    outputs.status = "No dependency";
+    OutputsToJSON(default_toolchain, outputs, output);
+    return Err();
+  }
+
+  // TODO: We can do smarter things when we detect changes to build files.
+  // For example, if all of the ninja files are unchanged, we know that we
+  // can ignore changes to these files. Also, for most .gn files, we can
+  // treat a change as simply affecting every target, config, or toolchain
+  // defined in that file.
+  if (AnyBuildFilesWereModified(inputs.source_files)) {
+    outputs.status = "Found dependency (all)";
+    outputs.compile_labels = inputs.compile_labels;
+    outputs.test_labels = inputs.test_labels;
+    OutputsToJSON(default_toolchain, outputs, output);
+    return Err();
+  }
+
+  TargetSet compile_targets = graph.TargetsFor(inputs.compile_labels);
+  if (inputs.compile_included_all) {
+    for (auto& root : graph.roots()) {
+      compile_targets.insert(root);
+    }
+  }
+  TargetSet pruned_targets = graph.Prune(compile_targets);
+  outputs.compile_labels =
+      LabelsFor(Intersect(pruned_targets, affected_targets));
+
+  TargetSet test_targets = graph.TargetsFor(inputs.test_labels);
+  outputs.test_labels = LabelsFor(Intersect(test_targets, affected_targets));
+
+  if (outputs.compile_labels.empty() && outputs.test_labels.empty())
+    outputs.status = "No dependency";
+  else
+    outputs.status = "Found dependency";
+  OutputsToJSON(default_toolchain, outputs, output);
+  return Err();
+}