Implement `gn analyze`.

tools/gn/analyzer.cc

Index: tools/gn/analyzer.cc
diff --git a/tools/gn/analyzer.cc b/tools/gn/analyzer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..57776b1045208e2b1741bebe3d60ad9d9c3a32b2
--- /dev/null
+++ b/tools/gn/analyzer.cc
@@ -0,0 +1,410 @@
+// 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:13]

Done.

+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "tools/gn/analyzer.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/builder.h"
+#include "tools/gn/deps_iterator.h"
+#include "tools/gn/err.h"
+#include "tools/gn/loader.h"
+#include "tools/gn/location.h"
+#include "tools/gn/source_file.h"
+#include "tools/gn/target.h"
+
+using LabelSet = Analyzer::LabelSet;
+using SourceFileSet = Analyzer::SourceFileSet;
+using TargetSet = Analyzer::TargetSet;
+
+namespace {
+
+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;
+};
+
+struct Outputs {
+  std::string status;
+  std::string error;
+  LabelSet compile_labels;
+  LabelSet test_labels;
+  LabelSet 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;
+}
+
+std::vector<std::string> GetStringVector(const base::DictionaryValue& dict,
+                                         const std::string& key,
+                                         Err* err) {
+  std::vector<std::string> strings;
+  const base::ListValue* lst;
+  bool ret = dict.GetList(key, &lst);
+  if (!ret) {
+    *err = Err(Location(), "Input does not have a key named \"" + key +
+                               "\" with a list value.");
+    return strings;
+  }
+
+  for (size_t i = 0; i < lst->GetSize(); i++) {
+    std::string s;
+    ret = lst->GetString(i, &s);
+    if (!ret) {
+      *err = Err(Location(), "Item " + std::to_string(i) + " of \"" + key +
+                                 "\" is not a string.");
+      strings.clear();
+      return strings;
+    }
+    strings.push_back(std::move(s));
+  }
+  *err = Err();
+  return strings;
+}
+
+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));
+}
+
+bool IsSourceAbsolute(const std::string& path) {

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

I think this should allow filesystem absolute paths as well. I know some people
use targets with these names and we handle these consistently in other contexts.
I think the only thing you want to prevent here is relative paths.

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

I don't know where we use absolute paths, and doing so seems like it would be a
bad thing. I'll defer this discussion to a follow-up thing so we can land
something, but we should discuss this further. At the very least, if we wanted
to allow non-source-absolute paths, I'd want to change the function name :).

As an aside, this is simply duplicating the logic in filesystem_utils.h.

[brettw, 2016/08/26 17:09:19]

Most of our support for stuff outside of the source root was added by Opera.

This function is correct for something called IsSourceAbsolute, but I think we
just should have called IsPathAbsolute in filesystem utils and deleted this one.

[Dirk Pranke, 2016/08/26 20:40:05]

It's true that we support absolute paths in some situations, but it's not clear
to me 
that they would come up in this one. However, I can probably change the code 
to allow them without creating too much risk.

+  return path.size() >= 2 && path[0] == '/' && path[1] == '/';
+}
+
+Label SourceAbsolutePathToLabel(const Label& default_toolchain,

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

You're really taking label strings as inputs rather than paths to things, which
makes me find this name confusing. How about SourceAbsoluteStringToLabel?

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

Fair enough. Will change.

+                                const std::string& path,
+                                Err* err) {
+  if (!IsSourceAbsolute(path)) {
+    *err = Err(Location(), "\"" + path + "\" is not a source-absolute path");
+    return Label();
+  }
+
+  SourceDir source_root("//");
+  Value v(nullptr, Value::STRING);

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

These two lines can be:
  Value v(nullptr, path);

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

Done.

+  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)
+    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.");
+
+  Err err;
+  std::vector<std::string> strings;
+  strings = GetStringVector(*dict, "files", &err);
+  if (err.has_error())
+    return err;
+  for (auto s : strings) {
+    if (!IsSourceAbsolute(s))
+      return Err(Location(), "\"" + s + "\" is not a source-absolute path.");
+    inputs->source_vec.push_back(SourceFile(s));
+  }
+
+  strings = GetStringVector(*dict, "compile_targets", &err);
+  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(
+          SourceAbsolutePathToLabel(default_toolchain, s, &err));
+      if (err.has_error())
+        return err;
+    }
+  }
+
+  strings = GetStringVector(*dict, "test_targets", &err);
+  if (err.has_error())
+    return err;
+  for (auto& s : strings) {
+    inputs->test_vec.push_back(
+        SourceAbsolutePathToLabel(default_toolchain, s, &err));
+    if (err.has_error())
+      return err;
+  }
+
+  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();
+}
+
+std::string OutputsToJSON(const Outputs& outputs,
+                          const Label& default_toolchain) {
+  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);
+  return output;
+}
+
+}  // namespace
+
+Analyzer::Analyzer(const Builder& builder)
+    : all_targets_(builder.GetAllResolvedTargets()),
+      default_toolchain_(builder.loader()->GetDefaultToolchain()) {
+  for (const 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);
+  }
+}
+
+Analyzer::~Analyzer() {}
+
+std::string Analyzer::Analyze(const std::string& input, Err* err) {

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

I can live with what you wrote but I would have personally made this function
take an AnalyzeInputs struct (move the anon-namespace one to the class) and
return an AnalyzeOutputs struct and leave the JSON serialization to the very end
points in command_analyze.cc.

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

Yeah, I struggled with this tradeoff and the code was actually in
command_analyze.cc for most of the lifetime of this patch. 

I ended up choosing this route because it's much easier to write tests with
strings as input and output, testing the conversion is reasonably important, and
we don't necessarily have a good way to test stuff in the command_* files.

The other advantage is that the Input and Output structures are very much an
implementation detail of the actual analyze() routine and it doesn't make a lot
of sense to expose it through the interface.

If we fix the testing problem I'd be happy to move stuff around.

+  Inputs inputs;
+  Outputs outputs;
+
+  Err local_err = JSONToInputs(default_toolchain_, input, &inputs);
+  if (local_err.has_error()) {
+    outputs.error = local_err.message();
+    if (err)
+      *err = Err();
+    return "";
+  }
+
+  LabelSet invalid_labels;
+  for (const auto& label : InvalidLabels(inputs.compile_labels))
+    invalid_labels.insert(label);
+  for (const auto& label : InvalidLabels(inputs.test_labels))
+    invalid_labels.insert(label);
+  if (!invalid_labels.empty()) {
+    outputs.error = "Invalid targets";
+    outputs.invalid_labels = invalid_labels;
+    if (err)
+      *err = Err();
+    return OutputsToJSON(outputs, default_toolchain_);
+  }
+
+  TargetSet affected_targets = AllAffectedTargets(inputs.source_files);
+  if (affected_targets.empty()) {
+    outputs.status = "No dependency";
+    if (err)
+      *err = Err();
+    return OutputsToJSON(outputs, default_toolchain_);
+  }
+
+  // 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;
+    if (err)
+      *err = Err();
+    return OutputsToJSON(outputs, default_toolchain_);
+  }
+
+  TargetSet compile_targets = TargetsFor(inputs.compile_labels);
+  if (inputs.compile_included_all) {
+    for (auto& root : roots_)
+      compile_targets.insert(root);
+  }
+  TargetSet filtered_targets = Filter(compile_targets);
+  outputs.compile_labels =
+      LabelsFor(Intersect(filtered_targets, affected_targets));
+
+  TargetSet test_targets = 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";
+  *err = Err();
+  return OutputsToJSON(outputs, default_toolchain_);
+}
+
+TargetSet Analyzer::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 Analyzer::InvalidLabels(const LabelSet& labels) {
+  LabelSet invalid_labels;
+  for (const Label& label : labels) {
+    if (labels_to_targets_.find(label) == labels_to_targets_.end())
+      invalid_labels.insert(label);
+  }
+  return invalid_labels;
+}
+
+TargetSet Analyzer::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;
+}
+
+TargetSet Analyzer::Filter(const TargetSet& targets) {
+  TargetSet seen;
+  TargetSet filtered;
+  for (const auto* target : targets)
+    FilterTarget(target, &seen, &filtered);
+  return filtered;
+}
+
+void Analyzer::FilterTarget(const Target* target,
+                            TargetSet* seen,
+                            TargetSet* filtered) {
+  if (seen->find(target) == seen->end()) {
+    seen->insert(target);
+    if (target->output_type() != Target::GROUP) {
+      filtered->insert(target);
+    } else {
+      for (const auto& pair : target->GetDeps(Target::DEPS_ALL))
+        FilterTarget(pair.ptr, seen, filtered);
+    }
+  }
+}
+
+bool Analyzer::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 Analyzer::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 Analyzer::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);

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

I would have used "auto dep_begin" and "auto dep_end" for these decls.

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

Done.

+  for (auto cur_dep = dep_begin; cur_dep != dep_end; cur_dep++)
+    AddAllRefsTo(cur_dep->second, results);
+}