From 5ac69dd02bef426d71ed1e58923345c9042c37dc Mon Sep 17 00:00:00 2001 From: Robert Schumacher Date: Mon, 18 Dec 2017 23:00:11 -0800 Subject: [vcpkg] Improve error message upon graph cycle detected. --- toolsrc/include/vcpkg/base/graphs.h | 155 +++++++++++++---------------------- toolsrc/include/vcpkg/dependencies.h | 1 - 2 files changed, 57 insertions(+), 99 deletions(-) (limited to 'toolsrc/include') diff --git a/toolsrc/include/vcpkg/base/graphs.h b/toolsrc/include/vcpkg/base/graphs.h index b585d2bb9..bd22bbcb0 100644 --- a/toolsrc/include/vcpkg/base/graphs.h +++ b/toolsrc/include/vcpkg/base/graphs.h @@ -4,6 +4,7 @@ #include #include +#include namespace vcpkg::Graphs { @@ -23,139 +24,97 @@ namespace vcpkg::Graphs struct AdjacencyProvider { virtual std::vector adjacency_list(const U& vertex) const = 0; - + virtual std::string to_string(const V& vertex) const = 0; virtual U load_vertex_data(const V& vertex) const = 0; }; - template - static void topological_sort_internal(const V& vertex, - const AdjacencyProvider& f, - std::unordered_map& exploration_status, - std::vector& sorted) + namespace details { - ExplorationStatus& status = exploration_status[vertex]; - switch (status) + template + void topological_sort_internal(const V& vertex, + const AdjacencyProvider& f, + std::unordered_map& exploration_status, + std::vector& sorted) { - case ExplorationStatus::FULLY_EXPLORED: return; - case ExplorationStatus::PARTIALLY_EXPLORED: Checks::exit_with_message(VCPKG_LINE_INFO, "cycle in graph"); - case ExplorationStatus::NOT_EXPLORED: + ExplorationStatus& status = exploration_status[vertex]; + switch (status) { - 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); - - sorted.push_back(std::move(vertex_data)); - status = ExplorationStatus::FULLY_EXPLORED; - return; + case ExplorationStatus::FULLY_EXPLORED: return; + case ExplorationStatus::PARTIALLY_EXPLORED: + { + System::println("Cycle detected within graph:"); + for (auto&& node : exploration_status) + { + if (node.second == ExplorationStatus::PARTIALLY_EXPLORED) + { + System::println(" %s", f.to_string(node.first)); + } + } + Checks::exit_fail(VCPKG_LINE_INFO); + } + case ExplorationStatus::NOT_EXPLORED: + { + 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); + + sorted.push_back(std::move(vertex_data)); + status = ExplorationStatus::FULLY_EXPLORED; + return; + } + default: Checks::unreachable(VCPKG_LINE_INFO); } - default: Checks::unreachable(VCPKG_LINE_INFO); } } - template - std::vector topological_sort(const std::vector& starting_vertices, const AdjacencyProvider& f) + template + std::vector topological_sort(const VertexRange& starting_vertices, const AdjacencyProvider& f) { std::vector sorted; std::unordered_map exploration_status; - for (auto& vertex : starting_vertices) + for (auto&& vertex : starting_vertices) { - topological_sort_internal(vertex, f, exploration_status, sorted); + details::topological_sort_internal(vertex, f, exploration_status, sorted); } return sorted; } template - struct GraphAdjacencyProvider final : AdjacencyProvider - { - const std::unordered_map>& vertices; - - GraphAdjacencyProvider(const std::unordered_map>& vertices) : vertices(vertices) {} - - std::vector adjacency_list(const V& vertex) const override - { - const std::unordered_set& as_set = this->vertices.at(vertex); - return std::vector(as_set.cbegin(), as_set.cend()); // TODO: Avoid redundant copy - } - - V load_vertex_data(const V& vertex) const override { return vertex; } - }; - - template - struct Graph + struct Graph final : AdjacencyProvider { public: - void add_vertex(V v) { this->vertices[v]; } + void add_vertex(const V& v) { this->m_edges[v]; } - // TODO: Change with iterators - void add_vertices(const std::vector& vs) + void add_edge(const V& u, const V& v) { - for (const V& v : vs) - { - this->vertices[v]; - } + this->m_edges[v]; + this->m_edges[u].insert(v); } - void add_edge(V u, V v) + std::vector vertex_list() const { - this->vertices[v]; - this->vertices[u].insert(v); + std::vector vertex_list; + for (auto&& vertex : this->m_edges) + vertex_list.emplace_back(vertex.first); + return vertex_list; } - std::vector topological_sort() const + std::vector adjacency_list(const V& vertex) const override { - GraphAdjacencyProvider adjacency_provider{this->vertices}; - std::unordered_map indegrees = count_indegrees(); - - std::vector sorted; - sorted.reserve(indegrees.size()); - - std::unordered_map exploration_status; - exploration_status.reserve(indegrees.size()); - - for (auto& pair : indegrees) - { - if (pair.second == 0) // Starting from vertices with indegree == 0. Not required. - { - V vertex = pair.first; - topological_sort_internal(vertex, adjacency_provider, exploration_status, sorted); - } - } - - return sorted; + const std::unordered_set& as_set = this->m_edges.at(vertex); + return std::vector(as_set.cbegin(), as_set.cend()); // TODO: Avoid redundant copy } - std::unordered_map count_indegrees() const - { - std::unordered_map indegrees; - - for (auto& pair : this->vertices) - { - indegrees[pair.first]; - for (V neighbour : pair.second) - { - ++indegrees[neighbour]; - } - } - - return indegrees; - } + V load_vertex_data(const V& vertex) const override { return vertex; } - const std::unordered_map>& adjacency_list() const { return this->vertices; } - std::vector vertex_list() const - { - // why no &? it returns 0 - std::vector vertex_list; - for (const auto& vertex : this->vertices) - { - vertex_list.emplace_back(vertex.first); - } - return vertex_list; - } + // Note: this function indicates how tied this template is to the exact type it will be templated upon. + // Possible fix: This type shouldn't implement to_string() and should instead be derived from? + std::string to_string(const V& spec) const override { return spec->spec.to_string(); } private: - std::unordered_map> vertices; + std::unordered_map> m_edges; }; } diff --git a/toolsrc/include/vcpkg/dependencies.h b/toolsrc/include/vcpkg/dependencies.h index 8a082efca..8902a7b08 100644 --- a/toolsrc/include/vcpkg/dependencies.h +++ b/toolsrc/include/vcpkg/dependencies.h @@ -1,6 +1,5 @@ #pragma once -#include #include #include #include -- cgit v1.2.3