From 39b7876db496d2cae6ec8c2736a45db6319ad46f Mon Sep 17 00:00:00 2001 From: Robert Schumacher Date: Fri, 18 Jan 2019 19:03:37 -0800 Subject: [vcpkg] Randomize topological sort in CI plans to allow concurrent builds to more efficiently interact --- toolsrc/include/vcpkg/base/graphs.h | 43 ++++++++++++++++++++++++++++++------ toolsrc/include/vcpkg/dependencies.h | 20 +++++++++++++++-- 2 files changed, 54 insertions(+), 9 deletions(-) (limited to 'toolsrc/include') 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 + void shuffle(Container& c, Randomizer* r) + { + if (!r) return; + for (int i = static_cast(c.size()); i > 1; --i) + { + auto j = r->random(i); + if (j != i - 1) + { + std::swap(c[i - 1], c[j]); + } + } + } + template void topological_sort_internal(const V& vertex, const AdjacencyProvider& f, std::unordered_map& exploration_status, - std::vector& sorted) + std::vector& 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 - std::vector topological_sort(const VertexRange& starting_vertices, const AdjacencyProvider& f) + template + std::vector topological_sort(VertexContainer starting_vertices, + const AdjacencyProvider& f, + Randomizer* randomizer) { std::vector sorted; std::unordered_map 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 #include +#include #include +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& prevent_default_features = {}) const; void upgrade(const PackageSpec& spec) const; - std::vector serialize() const; + std::vector serialize(const CreateInstallPlanOptions& options = {}) const; private: std::unique_ptr m_graph_plan; @@ -174,9 +185,14 @@ namespace vcpkg::Dependencies const std::vector& specs, const StatusParagraphs& status_db); + /// Figure out which actions are required to install features specifications in `specs`. + /// Contains the ports of the current environment. + /// Feature specifications to resolve dependencies for. + /// Status of installed packages in the current environment. std::vector create_feature_install_plan(const PortFileProvider& provider, const std::vector& specs, - const StatusParagraphs& status_db); + const StatusParagraphs& status_db, + const CreateInstallPlanOptions& options = {}); void print_plan(const std::vector& action_plan, const bool is_recursive = true); } -- cgit v1.2.3 From 8fd34506c3f2d06af8abd8cfbb543ad16e79c6a3 Mon Sep 17 00:00:00 2001 From: Phil Christensen Date: Thu, 21 Feb 2019 22:24:20 -0800 Subject: [vcpkg] improve xunit xml output used in CI tests --- toolsrc/include/vcpkg/install.h | 1 - 1 file changed, 1 deletion(-) (limited to 'toolsrc/include') diff --git a/toolsrc/include/vcpkg/install.h b/toolsrc/include/vcpkg/install.h index b7acbf15f..2e92764dc 100644 --- a/toolsrc/include/vcpkg/install.h +++ b/toolsrc/include/vcpkg/install.h @@ -37,7 +37,6 @@ namespace vcpkg::Install std::string total_elapsed_time; void print() const; - static std::string xunit_result(const PackageSpec& spec, Chrono::ElapsedTime time, Build::BuildResult code); std::string xunit_results() const; }; -- cgit v1.2.3