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

2 files changed, 54 insertions, 9 deletions

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);
 }