Make Ninja output deterministic across GN binary builds

SubstitutionBits::FillVector() iterated a base::flat_set<const
Substitution*> in pointer order, causing ninja variable assignments
(defines, include_dirs, etc.) within build edges to appear in a
different order depending on which build of GN was used, even from the
same source. Different binaries place the Substitution objects at
different addresses, producing different iteration order.

Fix by sorting the FillVector output by substitution name.

Change-Id: Ie90abe5b7121e21614e8dffcfc24889bbeaa028a
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/23440
Reviewed-by: Takuto Ikuta <tikuta@google.com>
Reviewed-by: Matt Stark <msta@google.com>
Commit-Queue: Philipp Wollermann <philwo@google.com>

build/gen.py

diff --git a/build/gen.py b/build/gen.py
index 9a9027b..c95b57e 100755
--- a/build/gen.py
+++ b/build/gen.py
@@ -924,6 +924,7 @@
         'src/gn/string_output_buffer_unittest.cc',
         'src/gn/string_utils_unittest.cc',
         'src/gn/substitution_pattern_unittest.cc',
+        'src/gn/substitution_type_unittest.cc',
         'src/gn/substitution_writer_unittest.cc',
         'src/gn/target_public_pair_unittest.cc',
         'src/gn/target_unittest.cc',

src/gn/substitution_type.cc

diff --git a/src/gn/substitution_type.cc b/src/gn/substitution_type.cc
index 723bf8a..9f7877f 100644
--- a/src/gn/substitution_type.cc
+++ b/src/gn/substitution_type.cc
@@ -7,6 +7,9 @@
 #include <stddef.h>
 #include <stdlib.h>
 
+#include <algorithm>
+#include <cstring>
+
 #include "gn/c_substitution_type.h"
 #include "gn/err.h"
 #include "gn/rust_substitution_type.h"
@@ -123,6 +126,13 @@
   for (const Substitution* s : used) {
     vect->push_back(s);
   }
+  // Sort by name for deterministic output across different builds of the
+  // same GN source. The flat_set iterates by pointer address which can
+  // vary between binaries.
+  std::sort(vect->begin(), vect->end(),
+            [](const Substitution* a, const Substitution* b) {
+              return std::strcmp(a->name, b->name) < 0;
+            });
 }
 
 bool SubstitutionIsInOutputDir(const Substitution* type) {

src/gn/substitution_type_unittest.cc

diff --git a/src/gn/substitution_type_unittest.cc b/src/gn/substitution_type_unittest.cc
new file mode 100644
index 0000000..d8e8b33
--- /dev/null
+++ b/src/gn/substitution_type_unittest.cc
@@ -0,0 +1,33 @@
+// Copyright 2026 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 "gn/substitution_type.h"
+
+#include <cstring>
+#include <vector>
+
+#include "util/test/test.h"
+
+TEST(SubstitutionBitsTest, FillVectorDeterministicOrdering) {
+  SubstitutionBits bits;
+  bits.used.insert(&SubstitutionTargetGenDir);
+  bits.used.insert(&SubstitutionSource);
+  bits.used.insert(&SubstitutionOutput);
+  bits.used.insert(&SubstitutionLabel);
+  bits.used.insert(&SubstitutionBundleRootDir);
+
+  std::vector<const Substitution*> vect;
+  bits.FillVector(&vect);
+
+  ASSERT_EQ(5u, vect.size());
+  EXPECT_STREQ("{{bundle_root_dir}}", vect[0]->name);
+  EXPECT_STREQ("{{label}}", vect[1]->name);
+  EXPECT_STREQ("{{output}}", vect[2]->name);
+  EXPECT_STREQ("{{source}}", vect[3]->name);
+  EXPECT_STREQ("{{target_gen_dir}}", vect[4]->name);
+
+  for (size_t i = 1; i < vect.size(); ++i) {
+    EXPECT_LT(std::strcmp(vect[i - 1]->name, vect[i]->name), 0);
+  }
+}