gn: Make generation of main build.ninja file deterministic.

tools/gn/ninja_build_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_build_writer.h"
 
 #include <stddef.h>
 
 #include <fstream>
 #include <map>
@@ skipping 116 matching lines @@
       "\nCollisions:\n" + matches_string);
   for (size_t i = 1; i < matches.size(); i++)
     result.AppendSubErr(Err(matches[i]->defined_from(), "Collision."));
   return result;
 }
 
 }  // namespace
 
 NinjaBuildWriter::NinjaBuildWriter(
     const BuildSettings* build_settings,
-    const std::map<const Settings*, const Toolchain*>& used_toolchains,
+    const std::unordered_map<const Settings*, const Toolchain*>&
+        used_toolchains,
     const Toolchain* default_toolchain,
     const std::vector<const Target*>& default_toolchain_targets,
     std::ostream& out,
     std::ostream& dep_out)
     : build_settings_(build_settings),
       used_toolchains_(used_toolchains),
       default_toolchain_(default_toolchain),
       default_toolchain_targets_(default_toolchain_targets),
       out_(out),
       dep_out_(dep_out),
@@ skipping 12 matching lines @@
 }
 
 // static
 bool NinjaBuildWriter::RunAndWriteFile(
     const BuildSettings* build_settings,
     const Builder& builder,
     Err* err) {
   ScopedTrace trace(TraceItem::TRACE_FILE_WRITE, "build.ninja");
 
   std::vector<const Target*> all_targets = builder.GetAllResolvedTargets();
-  std::map<const Settings*, const Toolchain*> used_toolchains;
+  std::unordered_map<const Settings*, const Toolchain*> used_toolchains;
 
   // Find the default toolchain info.
   Label default_toolchain_label = builder.loader()->GetDefaultToolchain();
   const Settings* default_toolchain_settings =
       builder.loader()->GetToolchainSettings(default_toolchain_label);
   const Toolchain* default_toolchain =
       builder.GetToolchain(default_toolchain_label);
 
   // Most targets will be in the default toolchain. Add it at the beginning and
   // skip adding it to the list every time in the loop.
@@ skipping 72 matching lines @@
   fileset.insert(other_files.begin(), other_files.end());
 
   for (const auto& other_file : fileset)
     dep_out_ << " " << FilePathToUTF8(other_file);
 
   out_ << std::endl;
 }
 
 void NinjaBuildWriter::WriteAllPools() {
   // Compute the pools referenced by all tools of all used toolchains.
-  std::set<const Pool*> used_pools;
+  std::unordered_set<const Pool*> used_pools;
   for (const auto& pair : used_toolchains_) {
     for (int j = Toolchain::TYPE_NONE + 1; j < Toolchain::TYPE_NUMTYPES; j++) {
       Toolchain::ToolType tool_type = static_cast<Toolchain::ToolType>(j);
       const Tool* tool = pair.second->GetTool(tool_type);
       if (tool && tool->pool().ptr)
         used_pools.insert(tool->pool().ptr);
     }
   }
 
-  for (const Pool* pool : used_pools) {
-    std::string pool_name = pool->GetNinjaName(default_toolchain_->label());
-    out_ << "pool " << pool_name << std::endl
+  // Write pools sorted by their name, to make output deterministic.
+  std::vector<const Pool*> sorted_pools(used_pools.begin(), used_pools.end());
+  auto pool_name = [this](const Pool* pool) {
+    return pool->GetNinjaName(default_toolchain_->label());
+  };
+  std::sort(sorted_pools.begin(), sorted_pools.end(),
+            [&pool_name](const Pool* a, const Pool* b) {
+              return pool_name(a) < pool_name(b);
+            });
+  for (const Pool* pool : sorted_pools) {
+    out_ << "pool " << pool_name(pool) << std::endl
          << "  depth = " << pool->depth() << std::endl
          << std::endl;
   }
 }
 
 void NinjaBuildWriter::WriteSubninjas() {
-  for (const auto& pair : used_toolchains_) {
+  // Write toolchains sorted by their name, to make output deterministic.
+  std::vector<std::pair<const Settings*, const Toolchain*>> sorted_settings(
+      used_toolchains_.begin(), used_toolchains_.end());
+  std::sort(sorted_settings.begin(), sorted_settings.end(),
+            [this](const std::pair<const Settings*, const Toolchain*>& a,
+                   const std::pair<const Settings*, const Toolchain*>& b) {
+              // Always put the default toolchain first.
+              if (b.second == default_toolchain_)
+                return false;
+              if (a.second == default_toolchain_)
+                return true;
+              return GetNinjaFileForToolchain(a.first) <
+                     GetNinjaFileForToolchain(b.first);
+            });
+  for (const auto& pair : sorted_settings) {
     out_ << "subninja ";
     path_output_.WriteFile(out_, GetNinjaFileForToolchain(pair.first));
     out_ << std::endl;
   }
   out_ << std::endl;
 }
 
 bool NinjaBuildWriter::WritePhonyAndAllRules(Err* err) {
   // Track rules as we generate them so we don't accidentally write a phony
   // rule that collides with something else.
@@ skipping 158 matching lines @@
   EscapeOptions ninja_escape;
   ninja_escape.mode = ESCAPE_NINJA;
 
   // Escape for special chars Ninja will handle.
   std::string escaped = EscapeString(phony_name, ninja_escape, nullptr);
 
   out_ << "build " << escaped << ": phony ";
   path_output_.WriteFile(out_, target->dependency_output_file());
   out_ << std::endl;
 }