[vcpkg] Randomize topological sort in CI plans to allow concurrent builds to more efficiently interact

2 files changed, 41 insertions, 16 deletions

diff --git a/toolsrc/src/vcpkg/commands.ci.cpp b/toolsrc/src/vcpkg/commands.ci.cpp
index 551eee27b..5ca962744 100644
--- a/toolsrc/src/vcpkg/commands.ci.cpp
+++ b/toolsrc/src/vcpkg/commands.ci.cpp
@@ -2,6 +2,7 @@
 
 #include <vcpkg/base/cache.h>
 #include <vcpkg/base/files.h>
+#include <vcpkg/base/graphs.h>
 #include <vcpkg/base/stringliteral.h>
 #include <vcpkg/base/system.h>
 #include <vcpkg/base/util.h>
@@ -30,14 +31,16 @@ namespace vcpkg::Commands::CI
     static constexpr StringLiteral OPTION_EXCLUDE = "--exclude";
     static constexpr StringLiteral OPTION_PURGE_TOMBSTONES = "--purge-tombstones";
     static constexpr StringLiteral OPTION_XUNIT = "--x-xunit";
+    static constexpr StringLiteral OPTION_RANDOMIZE = "--x-randomize";
 
     static constexpr std::array<CommandSetting, 2> CI_SETTINGS = {{
         {OPTION_EXCLUDE, "Comma separated list of ports to skip"},
         {OPTION_XUNIT, "File to output results in XUnit format (internal)"},
     }};
 
-    static constexpr std::array<CommandSwitch, 2> CI_SWITCHES = {{
+    static constexpr std::array<CommandSwitch, 3> CI_SWITCHES = {{
         {OPTION_DRY_RUN, "Print out plan without execution"},
+        {OPTION_RANDOMIZE, "Randomize the install order"},
         {OPTION_PURGE_TOMBSTONES, "Purge failure tombstones and retry building the ports"},
     }};
 
@@ -69,7 +72,7 @@ namespace vcpkg::Commands::CI
         std::map<PackageSpec, std::string> abi_tag_map;
         std::set<PackageSpec> will_fail;
 
-        const Build::BuildPackageOptions install_plan_options = {
+        const Build::BuildPackageOptions build_options = {
             Build::UseHeadVersion::NO,
             Build::AllowDownloads::YES,
             Build::CleanBuildtrees::YES,
@@ -81,7 +84,9 @@ namespace vcpkg::Commands::CI
 
         vcpkg::Cache<Triplet, Build::PreBuildInfo> pre_build_info_cache;
 
-        auto action_plan = Dependencies::create_feature_install_plan(provider, fspecs, StatusParagraphs {});
+        auto action_plan = Dependencies::create_feature_install_plan(provider, fspecs, {}, {});
+
+        auto timer = Chrono::ElapsedTimer::create_started();
 
         for (auto&& action : action_plan)
         {
@@ -94,7 +99,7 @@ namespace vcpkg::Commands::CI
                     auto triplet = p->spec.triplet();
 
                     const Build::BuildPackageConfig build_config {
-                        *scf, triplet, paths.port_dir(p->spec), install_plan_options, p->feature_list};
+                        *scf, triplet, paths.port_dir(p->spec), build_options, p->feature_list};
 
                     auto dependency_abis =
                         Util::fmap(p->computed_dependencies, [&](const PackageSpec& spec) -> Build::AbiEntry {
@@ -174,6 +179,8 @@ namespace vcpkg::Commands::CI
             }
         }
 
+        System::print("Time to determine pass/fail: %s\n", timer.elapsed().to_string());
+
         return ret;
     }
 
@@ -241,12 +248,31 @@ namespace vcpkg::Commands::CI
             for (auto&& fspec : fspecs)
                 pgraph.install(fspec);
 
+            Dependencies::CreateInstallPlanOptions serialize_options;
+
+            struct RandomizerInstance : Graphs::Randomizer
+            {
+                virtual int random(int i) override
+                {
+                    if (i <= 1) return 0;
+                    std::uniform_int_distribution<int> d(0, i - 1);
+                    return d(e);
+                }
+
+                std::random_device e;
+            } randomizer_instance;
+
+            if (Util::Sets::contains(options.switches, OPTION_RANDOMIZE))
+            {
+                serialize_options.randomizer = &randomizer_instance;
+            }
+
             auto action_plan = [&]() {
                 int iterations = 0;
                 do
                 {
                     bool inconsistent = false;
-                    auto action_plan = pgraph.serialize();
+                    auto action_plan = pgraph.serialize(serialize_options);
 
                     for (auto&& action : action_plan)
                     {
diff --git a/toolsrc/src/vcpkg/dependencies.cpp b/toolsrc/src/vcpkg/dependencies.cpp
index 60c43e4a8..19d8e7ae8 100644
--- a/toolsrc/src/vcpkg/dependencies.cpp
+++ b/toolsrc/src/vcpkg/dependencies.cpp
@@ -354,7 +354,7 @@ namespace vcpkg::Dependencies
 
         auto installed_ports = get_installed_ports(status_db);
         const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
-        return Graphs::topological_sort(specs, RemoveAdjacencyProvider{status_db, installed_ports, specs_as_set});
+        return Graphs::topological_sort(specs, RemoveAdjacencyProvider{status_db, installed_ports, specs_as_set}, {});
     }
 
     std::vector<ExportPlanAction> create_export_plan(const std::vector<PackageSpec>& specs,
@@ -396,7 +396,7 @@ namespace vcpkg::Dependencies
 
         const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
         std::vector<ExportPlanAction> toposort =
-            Graphs::topological_sort(specs, ExportAdjacencyProvider{status_db, specs_as_set});
+            Graphs::topological_sort(specs, ExportAdjacencyProvider{status_db, specs_as_set}, {});
         return toposort;
     }
 
@@ -605,13 +605,10 @@ namespace vcpkg::Dependencies
         }
     }
 
-    /// <summary>Figure out which actions are required to install features specifications in `specs`.</summary>
-    /// <param name="provider">Contains the ports of the current environment.</param>
-    /// <param name="specs">Feature specifications to resolve dependencies for.</param>
-    /// <param name="status_db">Status of installed packages in the current environment.</param>
     std::vector<AnyAction> create_feature_install_plan(const PortFileProvider& provider,
                                                        const std::vector<FeatureSpec>& specs,
-                                                       const StatusParagraphs& status_db)
+                                                       const StatusParagraphs& status_db,
+                                                       const CreateInstallPlanOptions& options)
     {
         std::unordered_set<std::string> prevent_default_features;
         for (auto&& spec : specs)
@@ -628,7 +625,7 @@ namespace vcpkg::Dependencies
             pgraph.install(spec, prevent_default_features);
         }
 
-        return pgraph.serialize();
+        return pgraph.serialize(options);
     }
 
     /// <summary>Figure out which actions are required to install features specifications in `specs`.</summary>
@@ -672,13 +669,15 @@ namespace vcpkg::Dependencies
         mark_minus(spec_cluster, *m_graph, *m_graph_plan, {});
     }
 
-    std::vector<AnyAction> PackageGraph::serialize() const
+    std::vector<AnyAction> PackageGraph::serialize(const CreateInstallPlanOptions& options) const
     {
         auto remove_vertex_list = m_graph_plan->remove_graph.vertex_list();
-        auto remove_toposort = Graphs::topological_sort(remove_vertex_list, m_graph_plan->remove_graph);
+        auto remove_toposort =
+            Graphs::topological_sort(remove_vertex_list, m_graph_plan->remove_graph, options.randomizer);
 
         auto insert_vertex_list = m_graph_plan->install_graph.vertex_list();
-        auto insert_toposort = Graphs::topological_sort(insert_vertex_list, m_graph_plan->install_graph);
+        auto insert_toposort =
+            Graphs::topological_sort(insert_vertex_list, m_graph_plan->install_graph, options.randomizer);
 
         std::vector<AnyAction> plan;