[vcpkg] Improve error message upon graph cycle detected.

2 files changed, 57 insertions, 99 deletions

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 <unordered_set>
 
 #include <vcpkg/base/checks.h>
+#include <vcpkg/base/span.h>
 
 namespace vcpkg::Graphs
 {
@@ -23,139 +24,97 @@ 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;
     };
 
-    template<class V, class U>
-    static void topological_sort_internal(const V& vertex,
-                                          const AdjacencyProvider<V, U>& f,
-                                          std::unordered_map<V, ExplorationStatus>& exploration_status,
-                                          std::vector<U>& sorted)
+    namespace details
     {
-        ExplorationStatus& status = exploration_status[vertex];
-        switch (status)
+        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)
         {
-            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<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)
+        std::vector<V> vertex_list() const
         {
-            this->vertices[v];
-            this->vertices[u].insert(v);
+            std::vector<V> vertex_list;
+            for (auto&& vertex : this->m_edges)
+                vertex_list.emplace_back(vertex.first);
+            return vertex_list;
         }
 
-        std::vector<V> topological_sort() const
+        std::vector<V> adjacency_list(const V& vertex) const override
         {
-            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.
-                {
-                    V vertex = pair.first;
-                    topological_sort_internal(vertex, adjacency_provider, exploration_status, sorted);
-                }
-            }
-
-            return sorted;
+            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
         }
 
-        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)
-                {
-                    ++indegrees[neighbour];
-                }
-            }
-
-            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;
     };
 }
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 <vcpkg/base/graphs.h>
 #include <vcpkg/base/optional.h>
 #include <vcpkg/base/util.h>
 #include <vcpkg/build.h>