GN: Makes GN output deterministic

tools/gn/ninja_target_writer.cc

 // Copyright (c) 2013 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.
 
 #include "tools/gn/ninja_target_writer.h"
 
 #include <sstream>
 
 #include "base/files/file_util.h"
 #include "base/strings/string_util.h"
@@ skipping 189 matching lines @@
     path_output_.WriteFile(out_, input);
   }
   if (list_sources_as_input_deps) {
     for (const auto& source : target_->sources()) {
       out_ << " ";
       path_output_.WriteFile(out_, source);
     }
   }
 
   // The different souces of input deps may duplicate some targets, so uniquify
-  // them (ordering doesn't matter for this case).
-  std::set<const Target*> unique_deps;
+  // them. Note that the order matters, or the output is non-deterministic.

[brettw, 2015/12/10 21:29:46]

Can you rephrase this comment, I feel like it's worded too strongly and implies
that non-ordered might be wrong whereas this is more of a nice-to-have. Maybe
just "These are sorted so the generated files are deterministic."

+  std::vector<const Target*> sorted_deps;
 
   // Hard dependencies that are direct or indirect dependencies.
-  const std::set<const Target*>& hard_deps = target_->recursive_hard_deps();
-  for (const auto& dep : hard_deps)
-    unique_deps.insert(dep);
+  const std::set<const Target*>& hard_deps(target_->recursive_hard_deps());
 
   // Extra hard dependencies passed in.
-  unique_deps.insert(extra_hard_deps.begin(), extra_hard_deps.end());
+  for (const Target* target : extra_hard_deps) {

[M-A Ruel, 2015/12/08 13:49:29]

I think this comment should be added here, it's not obvious (at least to me) and
it's important to understand the performance characteristics.

+    if (!hard_deps.count(target)) {

[brettw, 2015/12/10 21:29:46]

No {} for single line conditionals (for consistency with the rest of the code in
this file). Same thing in a few cases below.

+      sorted_deps.push_back(target);
+    }
+  }
 
   // Toolchain dependencies. These must be resolved before doing anything.
-  // This just writs all toolchain deps for simplicity. If we find that
+  // This just writes all toolchain deps for simplicity. If we find that
   // toolchains often have more than one dependency, we could consider writing
   // a toolchain-specific stamp file and only include the stamp here.
   const LabelTargetVector& toolchain_deps = target_->toolchain()->deps();
-  for (const auto& toolchain_dep : toolchain_deps)
-    unique_deps.insert(toolchain_dep.ptr);
+  for (const auto& toolchain_dep : toolchain_deps) {
+    if (!hard_deps.count(toolchain_dep.ptr)) {

[M-A Ruel, 2015/12/08 13:49:29]

I guess this assumes toolchains are never passed as extra_hard_deps ?

[brettw, 2015/12/10 21:29:46]

You mean "toolchain deps" (these are target dependencies required by everything
in a toolchain, designed for nacl toolchain setup steps).

In our build this should never be the case, but in general this is not
guaranteed. I think this isn't worth worrying about since it's quite hard to
come up with a legitimate reason why this might happen, and the failure mode is
a harmless redundant dependency. And if we start getting interesting toolchain
dependencies we should do the TODO already mentioned about the stamp file.

However, we should add a comment to this effect here: "These could theoretically
duplicate dependencies already in the list, but shouldn't happen in practice, is
inconvenient to check for, and only results in harmless redundant dependencies
listed."

+      sorted_deps.push_back(toolchain_dep.ptr);
+    }
+  }
 
-  for (const auto& dep : unique_deps) {
+  for (const Target* target : hard_deps) {
+    sorted_deps.push_back(target);
+  }
+
+  std::sort(
+      sorted_deps.begin(), sorted_deps.end(),
+      [](const Target* a, const Target* b) { return a->label() < b->label(); });
+
+  for (const auto& dep : sorted_deps) {
     DCHECK(!dep->dependency_output_file().value().empty());
     out_ << " ";
     path_output_.WriteFile(out_, dep->dependency_output_file());
   }
 
   out_ << "\n";
   return input_stamp_file;
 }
 
 void NinjaTargetWriter::WriteStampForTarget(
@@ skipping 15 matching lines @@
        << GetNinjaRulePrefixForToolchain(settings_)
        << Toolchain::ToolTypeToName(Toolchain::TYPE_STAMP);
   path_output_.WriteFiles(out_, files);
 
   if (!order_only_deps.empty()) {
     out_ << " ||";
     path_output_.WriteFiles(out_, order_only_deps);
   }
   out_ << std::endl;
 }