[vcpkg] Improve error message upon graph cycle detected.
MODIFY
include/vcpkg/base/graphs.h
include/vcpkg/base/graphs.h
#include <unordered_set>
#include <vcpkg/base/checks.h>
+#include <vcpkg/base/span.h>
namespace vcpkg::Graphs
{
@@ -23,12 +24,14 @@ namespace vcpkg::Graphs
struct AdjacencyProvider
{
virtual std::vector<V> 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;
};
+ namespace details
+ {
template<class V, class U>
- static void topological_sort_internal(const V& vertex,
+ void topological_sort_internal(const V& vertex,
const AdjacencyProvider<V, U>& f,
std::unordered_map<V, ExplorationStatus>& exploration_status,
std::vector<U>& sorted)
@@ -37,7 +40,18 @@ namespace vcpkg::Graphs
switch (status)
{
case ExplorationStatus::FULLY_EXPLORED: return;
- case ExplorationStatus::PARTIALLY_EXPLORED: Checks::exit_with_message(VCPKG_LINE_INFO, "cycle in graph");
+ 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;
@@ -52,110 +66,55 @@ namespace vcpkg::Graphs
default: Checks::unreachable(VCPKG_LINE_INFO);
}
}
+ }
- template<class V, class U>
- std::vector<U> topological_sort(const std::vector<V>& starting_vertices, const AdjacencyProvider<V, U>& f)
+ template<class VertexRange, class V, class U>
+ std::vector<U> topological_sort(const VertexRange& starting_vertices, const AdjacencyProvider<V, U>& f)
{
std::vector<U> sorted;
std::unordered_map<V, ExplorationStatus> 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<class V>
- struct GraphAdjacencyProvider final : AdjacencyProvider<V, V>
- {
- const std::unordered_map<V, std::unordered_set<V>>& vertices;
-
- GraphAdjacencyProvider(const std::unordered_map<V, std::unordered_set<V>>& vertices) : vertices(vertices) {}
-
- std::vector<V> adjacency_list(const V& vertex) const override
- {
- const std::unordered_set<V>& as_set = this->vertices.at(vertex);
- return std::vector<V>(as_set.cbegin(), as_set.cend()); // TODO: Avoid redundant copy
- }
-
- V load_vertex_data(const V& vertex) const override { return vertex; }
- };
-
- template<class V>
- struct Graph
+ struct Graph final : AdjacencyProvider<V, V>
{
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<V>& 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)
- {
- this->vertices[v];
- this->vertices[u].insert(v);
- }
-
- std::vector<V> topological_sort() const
- {
- GraphAdjacencyProvider<V> adjacency_provider{this->vertices};
- std::unordered_map<V, int> indegrees = count_indegrees();
-
- std::vector<V> sorted;
- sorted.reserve(indegrees.size());
-
- std::unordered_map<V, ExplorationStatus> exploration_status;
- exploration_status.reserve(indegrees.size());
-
- for (auto& pair : indegrees)
- {
- if (pair.second == 0) // Starting from vertices with indegree == 0. Not required.
+ std::vector<V> vertex_list() const
{
- V vertex = pair.first;
- topological_sort_internal(vertex, adjacency_provider, exploration_status, sorted);
- }
- }
-
- return sorted;
+ std::vector<V> vertex_list;
+ for (auto&& vertex : this->m_edges)
+ vertex_list.emplace_back(vertex.first);
+ return vertex_list;
}
- std::unordered_map<V, int> count_indegrees() const
- {
- std::unordered_map<V, int> indegrees;
-
- for (auto& pair : this->vertices)
- {
- indegrees[pair.first];
- for (V neighbour : pair.second)
+ std::vector<V> adjacency_list(const V& vertex) const override
{
- ++indegrees[neighbour];
- }
+ const std::unordered_set<V>& as_set = this->m_edges.at(vertex);
+ return std::vector<V>(as_set.cbegin(), as_set.cend()); // TODO: Avoid redundant copy
}
- return indegrees;
- }
+ V load_vertex_data(const V& vertex) const override { return vertex; }
- const std::unordered_map<V, std::unordered_set<V>>& adjacency_list() const { return this->vertices; }
- std::vector<V> vertex_list() const
- {
- // why no &? it returns 0
- std::vector<V> 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<V, std::unordered_set<V>> vertices;
+ std::unordered_map<V, std::unordered_set<V>> m_edges;
};
}

MODIFY
include/vcpkg/dependencies.h
include/vcpkg/dependencies.h
#pragma once
-#include <vcpkg/base/graphs.h>
#include <vcpkg/base/optional.h>
#include <vcpkg/base/util.h>
#include <vcpkg/build.h>

MODIFY
src/vcpkg/dependencies.cpp
src/vcpkg/dependencies.cpp
@@ -373,6 +373,8 @@ namespace vcpkg::Dependencies
}
return RemovePlanAction{spec, RemovePlanType::REMOVE, request_type};
}
+
+ std::string to_string(const PackageSpec& spec) const override { return spec.to_string(); }
};
const std::vector<StatusParagraph*>& installed_ports = get_installed_ports(status_db);
@@ -420,6 +422,8 @@ namespace vcpkg::Dependencies
Checks::exit_with_message(VCPKG_LINE_INFO, "Could not find package %s", spec);
}
+
+ std::string to_string(const PackageSpec& spec) const override { return spec.to_string(); }
};
const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
@@ -598,14 +602,11 @@ namespace vcpkg::Dependencies
std::vector<AnyAction> PackageGraph::serialize() const
{
- Graphs::GraphAdjacencyProvider<ClusterPtr> adjacency_remove_graph(m_graph_plan->remove_graph.adjacency_list());
auto remove_vertex_list = m_graph_plan->remove_graph.vertex_list();
- auto remove_toposort = Graphs::topological_sort(remove_vertex_list, adjacency_remove_graph);
+ auto remove_toposort = Graphs::topological_sort(remove_vertex_list, m_graph_plan->remove_graph);
- Graphs::GraphAdjacencyProvider<ClusterPtr> adjacency_install_graph(
- m_graph_plan->install_graph.adjacency_list());
auto insert_vertex_list = m_graph_plan->install_graph.vertex_list();
- auto insert_toposort = Graphs::topological_sort(insert_vertex_list, adjacency_install_graph);
+ auto insert_toposort = Graphs::topological_sort(insert_vertex_list, m_graph_plan->install_graph);
std::vector<AnyAction> plan;

[vcpkg] Improve error message upon graph cycle detected.