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

5 files changed, 97 insertions, 26 deletions

diff --git a/toolsrc/.clang-format b/toolsrc/.clang-format
index 4700062c7..c14765672 100644
--- a/toolsrc/.clang-format
+++ b/toolsrc/.clang-format
@@ -29,4 +29,5 @@ IndentCaseLabels: true
 KeepEmptyLinesAtTheStartOfBlocks: false
 NamespaceIndentation: All
 PenaltyReturnTypeOnItsOwnLine: 1000
-SpaceAfterTemplateKeyword: false
\ No newline at end of file
+SpaceAfterTemplateKeyword: false
+SpaceBeforeCpp11BracedList: false
diff --git a/toolsrc/include/vcpkg/base/graphs.h b/toolsrc/include/vcpkg/base/graphs.h
index 1b0fa61c7..6cff75ad3 100644
--- a/toolsrc/include/vcpkg/base/graphs.h
+++ b/toolsrc/include/vcpkg/base/graphs.h
@@ -29,13 +29,36 @@ namespace vcpkg::Graphs
         virtual U load_vertex_data(const V& vertex) const = 0;
     };
 
+    struct Randomizer
+    {
+        virtual int random(int max_exclusive) = 0;
+
+    protected:
+        ~Randomizer() {}
+    };
+
     namespace details
     {
+        template<class Container>
+        void shuffle(Container& c, Randomizer* r)
+        {
+            if (!r) return;
+            for (int i = static_cast<int>(c.size()); i > 1; --i)
+            {
+                auto j = r->random(i);
+                if (j != i - 1)
+                {
+                    std::swap(c[i - 1], c[j]);
+                }
+            }
+        }
+
         template<class V, class U>
         void topological_sort_internal(const V& vertex,
                                        const AdjacencyProvider<V, U>& f,
                                        std::unordered_map<V, ExplorationStatus>& exploration_status,
-                                       std::vector<U>& sorted)
+                                       std::vector<U>& sorted,
+                                       Randomizer* randomizer)
         {
             ExplorationStatus& status = exploration_status[vertex];
             switch (status)
@@ -43,7 +66,7 @@ namespace vcpkg::Graphs
                 case ExplorationStatus::FULLY_EXPLORED: return;
                 case ExplorationStatus::PARTIALLY_EXPLORED:
                 {
-                    System::println("Cycle detected within graph:");
+                    System::println("Cycle detected within graph at %s:", f.to_string(vertex));
                     for (auto&& node : exploration_status)
                     {
                         if (node.second == ExplorationStatus::PARTIALLY_EXPLORED)
@@ -57,8 +80,10 @@ namespace vcpkg::Graphs
                 {
                     status = ExplorationStatus::PARTIALLY_EXPLORED;
                     U vertex_data = f.load_vertex_data(vertex);
-                    for (const V& neighbour : f.adjacency_list(vertex_data))
-                        topological_sort_internal(neighbour, f, exploration_status, sorted);
+                    auto neighbours = f.adjacency_list(vertex_data);
+                    details::shuffle(neighbours, randomizer);
+                    for (const V& neighbour : neighbours)
+                        topological_sort_internal(neighbour, f, exploration_status, sorted, randomizer);
 
                     sorted.push_back(std::move(vertex_data));
                     status = ExplorationStatus::FULLY_EXPLORED;
@@ -69,15 +94,19 @@ namespace vcpkg::Graphs
         }
     }
 
-    template<class VertexRange, class V, class U>
-    std::vector<U> topological_sort(const VertexRange& starting_vertices, const AdjacencyProvider<V, U>& f)
+    template<class VertexContainer, class V, class U>
+    std::vector<U> topological_sort(VertexContainer starting_vertices,
+                                    const AdjacencyProvider<V, U>& f,
+                                    Randomizer* randomizer)
     {
         std::vector<U> sorted;
         std::unordered_map<V, ExplorationStatus> exploration_status;
 
+        details::shuffle(starting_vertices, randomizer);
+
         for (auto&& vertex : starting_vertices)
         {
-            details::topological_sort_internal(vertex, f, exploration_status, sorted);
+            details::topological_sort_internal(vertex, f, exploration_status, sorted, randomizer);
         }
 
         return sorted;
diff --git a/toolsrc/include/vcpkg/dependencies.h b/toolsrc/include/vcpkg/dependencies.h
index 3c3b8f267..16fdb3f73 100644
--- a/toolsrc/include/vcpkg/dependencies.h
+++ b/toolsrc/include/vcpkg/dependencies.h
@@ -7,8 +7,14 @@
 #include <vcpkg/statusparagraphs.h>
 #include <vcpkg/vcpkgpaths.h>
 
+#include <functional>
 #include <vector>
 
+namespace vcpkg::Graphs
+{
+    struct Randomizer;
+}
+
 namespace vcpkg::Dependencies
 {
     enum class RequestType
@@ -148,6 +154,11 @@ namespace vcpkg::Dependencies
     struct ClusterGraph;
     struct GraphPlan;
 
+    struct CreateInstallPlanOptions
+    {
+        Graphs::Randomizer* randomizer = nullptr;
+    };
+
     struct PackageGraph
     {
         PackageGraph(const PortFileProvider& provider, const StatusParagraphs& status_db);
@@ -157,7 +168,7 @@ namespace vcpkg::Dependencies
                      const std::unordered_set<std::string>& prevent_default_features = {}) const;
         void upgrade(const PackageSpec& spec) const;
 
-        std::vector<AnyAction> serialize() const;
+        std::vector<AnyAction> serialize(const CreateInstallPlanOptions& options = {}) const;
 
     private:
         std::unique_ptr<GraphPlan> m_graph_plan;
@@ -174,9 +185,14 @@ namespace vcpkg::Dependencies
                                                        const std::vector<FeatureSpec>& specs,
                                                        const StatusParagraphs& status_db);
 
+    /// <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 = {});
 
     void print_plan(const std::vector<AnyAction>& action_plan, const bool is_recursive = true);
 }
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;