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).
+  // them. Note that the order matters, or the output is non-deterministic.
   std::set<const Target*> unique_deps;
 
   // Hard dependencies that are direct or indirect dependencies.
   const std::set<const Target*>& hard_deps = target_->recursive_hard_deps();

[M-A Ruel, 2015/12/07 15:09:50]

Use the copy-constructor to save an empty initialization.
std::set<const Target*> unique_deps(target_->recursive_hard_deps());

But then I read http://stackoverflow.com/a/1041939/1939810 and made me wonder a
bit. STL is weird, e.g. "Convert to set (manually)" vs "Convert to set (using a
constructor)".

But I do hope the set(set) copy constructor is better than set(vector).

I don't know what scale (especially with number of duplicates) we want to
optimize for.

[brettw, 2015/12/07 18:48:54]

We don't have to micro-optimize, but in the GN code I try to be pretty careful
since this will be called several thousand times in ~900ms.

In this case, the extra_hard_deps and toolchaion_deps are almost always empty
and if they aren't, they will be small. In contrast, the recursive_hard_deps can
be several hundred items.

I would do something like this:

std::vector<const Target*> sorted_deps;
for (dep : extra_hard_deps) {
  if (hard_deps doesn't contain dep)
    sorted_deps.push_back(dep)
}
<Same thing for toolchain deps>
sorted_deps.insert(hard_deps);
sort(sorted_deps)

This will prevent the extra set construction just to merge with extra_hard_deps.

[Zachary Forman, 2015/12/08 09:40:42]

Nice approach, and probably scales better too. Pretty similar base runtime,
however.

-  for (const auto& dep : hard_deps)
-    unique_deps.insert(dep);
 
+  unique_deps.insert(hard_deps.begin(), hard_deps.end());
   // Extra hard dependencies passed in.
   unique_deps.insert(extra_hard_deps.begin(), extra_hard_deps.end());
 
   // Toolchain dependencies. These must be resolved before doing anything.
   // This just writs all toolchain deps for simplicity. If we find that

[M-A Ruel, 2015/12/07 15:09:50]

writes
(while at it)

[Zachary Forman, 2015/12/08 09:40:42]

Done.

   // 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& dep : unique_deps) {
+  // Sort the dependencies so they're in deterministic order.
+  std::vector<const Target*> sorted_deps(unique_deps.begin(),
+                                         unique_deps.end());
+
+  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;
 }