Rework toposort and create_install_plan

3 files changed, 172 insertions, 98 deletions

diff --git a/toolsrc/include/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
index 0e629ffef..36dd3cb2d 100644
--- a/toolsrc/include/vcpkg_Dependencies.h
+++ b/toolsrc/include/vcpkg_Dependencies.h
@@ -4,9 +4,20 @@
 #include "StatusParagraphs.h"
 #include "VcpkgPaths.h"
 #include "vcpkg_optional.h"
+#include "Paragraphs.h"
 
 namespace vcpkg::Dependencies
 {
+    struct AnyParagraph
+    {
+        std::vector<PackageSpec> edges() const;
+
+        PackageSpec spec;
+        Optional<StatusParagraph> status_paragraph;
+        Optional<BinaryParagraph> binary_paragraph;
+        Optional<SourceParagraph> source_paragraph;
+    };
+
     enum class RequestType
     {
         UNKNOWN,
@@ -27,6 +38,7 @@ namespace vcpkg::Dependencies
     struct InstallPlanAction
     {
         InstallPlanAction();
+        explicit InstallPlanAction(const AnyParagraph& any_paragraph, const RequestType& request_type);
         InstallPlanAction(const InstallPlanType& plan_type, const RequestType& request_type, Optional<BinaryParagraph> binary_pgh, Optional<SourceParagraph> source_pgh);
         InstallPlanAction(const InstallPlanAction&) = delete;
         InstallPlanAction(InstallPlanAction&&) = default;
diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h
index 3ba26c017..8af2ad053 100644
--- a/toolsrc/include/vcpkg_Graphs.h
+++ b/toolsrc/include/vcpkg_Graphs.h
@@ -17,52 +17,77 @@ namespace vcpkg::Graphs
         FULLY_EXPLORED
     };
 
-    template <class V, class Func>
-    static void topological_sort_internal(const V& vertex,
-                                          ExplorationStatus& status,
-                                          const Func adjacency_list_provider,
-                                          std::unordered_map<V, ExplorationStatus>& exploration_status,
-                                          std::vector<V>& sorted)
+    template <class V, class U>
+    __interface AdjacencyProvider
     {
-        status = ExplorationStatus::PARTIALLY_EXPLORED;
+        std::vector<V> adjacency_list(const U& vertex) const;
 
-        auto neighbours = adjacency_list_provider(vertex);
+        U load_vertex_data(const V& vertex) const;
+    };
 
-        for (V neighbour : neighbours)
+    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)
+    {
+        ExplorationStatus& status = exploration_status[vertex];
+        switch (status)
         {
-            ExplorationStatus& neighbour_status = exploration_status[neighbour];
-            if (neighbour_status == ExplorationStatus::NOT_EXPLORED)
-            {
-                topological_sort_internal(neighbour, neighbour_status, adjacency_list_provider, exploration_status, sorted);
-            }
-            else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED)
-            {
-                throw std::runtime_error("cycle in graph");
-            }
+            case ExplorationStatus::FULLY_EXPLORED:
+                return;
+            case ExplorationStatus::PARTIALLY_EXPLORED:
+                Checks::exit_with_message(VCPKG_LINE_INFO, "cycle in graph");
+            case ExplorationStatus::NOT_EXPLORED:
+                {
+                    status = ExplorationStatus::PARTIALLY_EXPLORED;
+                    const 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);
         }
-        status = ExplorationStatus::FULLY_EXPLORED;
-        sorted.push_back(vertex);
     }
 
-    template <class V, class Func>
-    std::vector<V> topological_sort(const std::vector<V>& starting_vertices, const Func adjacency_list_provider)
+    template <class V, class U>
+    std::vector<U> topological_sort(const std::vector<V>& starting_vertices, const AdjacencyProvider<V, U>& f)
     {
-        std::vector<V> sorted;
+        std::vector<U> sorted;
         std::unordered_map<V, ExplorationStatus> exploration_status;
 
         for (auto& vertex : starting_vertices)
         {
-            ExplorationStatus& status = exploration_status[vertex];
-            if (status == ExplorationStatus::NOT_EXPLORED)
-            {
-                topological_sort_internal(vertex, status, adjacency_list_provider, exploration_status, sorted);
-            }
+            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>
     class Graph
     {
     public:
@@ -88,6 +113,7 @@ namespace vcpkg::Graphs
 
         std::vector<V> topological_sort() const
         {
+            GraphAdjacencyProvider<V> adjacency_provider{ this->vertices };
             std::unordered_map<V, int> indegrees = count_indegrees();
 
             std::vector<V> sorted;
@@ -101,13 +127,7 @@ namespace vcpkg::Graphs
                 if (pair.second == 0) // Starting from vertices with indegree == 0. Not required.
                 {
                     V vertex = pair.first;
-                    ExplorationStatus& status = exploration_status[vertex];
-                    if (status == ExplorationStatus::NOT_EXPLORED)
-                    {
-                        topological_sort_internal(vertex, status,
-                                                  [this](const V& v) { return this->vertices.at(v); },
-                                                  exploration_status, sorted);
-                    }
+                    topological_sort_internal(vertex, adjacency_provider, exploration_status, sorted);
                 }
             }
 
diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
index e47162953..3a53c42d1 100644
--- a/toolsrc/src/vcpkg_Dependencies.cpp
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -5,10 +5,38 @@
 #include "PackageSpec.h"
 #include "StatusParagraphs.h"
 #include "vcpkg_Files.h"
-#include "Paragraphs.h"
+#include "vcpkg_Util.h"
 
 namespace vcpkg::Dependencies
 {
+    std::vector<PackageSpec> AnyParagraph::edges() const
+    {
+        auto to_package_specs = [&](const std::vector<std::string>& dependencies_as_string)
+            {
+                return Util::fmap(dependencies_as_string, [&](const std::string s)
+                                  {
+                                      return PackageSpec::from_name_and_triplet(s, this->spec.triplet()).value_or_exit(VCPKG_LINE_INFO);
+                                  });
+            };
+
+        if (auto p = this->status_paragraph.get())
+        {
+            return to_package_specs(p->package.depends);
+        }
+
+        if (auto p = this->binary_paragraph.get())
+        {
+            return to_package_specs(p->depends);
+        }
+
+        if (auto p = this->source_paragraph.get())
+        {
+            return to_package_specs(filter_dependencies(p->depends, this->spec.triplet()));
+        }
+
+        Checks::exit_with_message(VCPKG_LINE_INFO, "Cannot get dependencies for package %s because there was none of: source/binary/status paragraphs", spec.to_string());
+    }
+
     std::string to_output_string(RequestType request_type, const CStringView s)
     {
         switch (request_type)
@@ -22,21 +50,58 @@ namespace vcpkg::Dependencies
         }
     }
 
-    InstallPlanAction::InstallPlanAction() : plan_type(InstallPlanType::UNKNOWN), request_type(RequestType::UNKNOWN), binary_pgh(nullopt), source_pgh(nullopt) { }
+    InstallPlanAction::InstallPlanAction() : plan_type(InstallPlanType::UNKNOWN)
+                                           , request_type(RequestType::UNKNOWN)
+                                           , binary_pgh(nullopt)
+                                           , source_pgh(nullopt) { }
+
+    InstallPlanAction::InstallPlanAction(const AnyParagraph& any_paragraph, const RequestType& request_type) : InstallPlanAction()
+    {
+        this->request_type = request_type;
+        if (any_paragraph.status_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::ALREADY_INSTALLED;
+            return;
+        }
+
+        if (auto p = any_paragraph.binary_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::INSTALL;
+            this->binary_pgh = *p;
+            return;
+        }
+
+        if (auto p = any_paragraph.source_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::BUILD_AND_INSTALL;
+            this->source_pgh = *p;
+            return;
+        }
+
+        this->plan_type = InstallPlanType::UNKNOWN;
+    }
 
     InstallPlanAction::InstallPlanAction(const InstallPlanType& plan_type, const RequestType& request_type, Optional<BinaryParagraph> binary_pgh, Optional<SourceParagraph> source_pgh)
-        : plan_type(std::move(plan_type)), request_type(request_type), binary_pgh(std::move(binary_pgh)), source_pgh(std::move(source_pgh)) { }
+        : plan_type(std::move(plan_type))
+        , request_type(request_type)
+        , binary_pgh(std::move(binary_pgh))
+        , source_pgh(std::move(source_pgh)) { }
 
     bool PackageSpecWithInstallPlan::compare_by_name(const PackageSpecWithInstallPlan* left, const PackageSpecWithInstallPlan* right)
     {
         return left->spec.name() < right->spec.name();
     }
 
-    PackageSpecWithInstallPlan::PackageSpecWithInstallPlan(const PackageSpec& spec, InstallPlanAction&& plan) : spec(spec), plan(std::move(plan)) { }
+    PackageSpecWithInstallPlan::PackageSpecWithInstallPlan(const PackageSpec& spec, InstallPlanAction&& plan)
+        : spec(spec)
+        , plan(std::move(plan)) { }
 
-    RemovePlanAction::RemovePlanAction() : plan_type(RemovePlanType::UNKNOWN), request_type(RequestType::UNKNOWN) { }
+    RemovePlanAction::RemovePlanAction() : plan_type(RemovePlanType::UNKNOWN)
+                                         , request_type(RequestType::UNKNOWN) { }
 
-    RemovePlanAction::RemovePlanAction(const RemovePlanType& plan_type, const Dependencies::RequestType& request_type) : plan_type(plan_type), request_type(request_type) { }
+    RemovePlanAction::RemovePlanAction(const RemovePlanType& plan_type, const RequestType& request_type)
+        : plan_type(plan_type)
+        , request_type(request_type) { }
 
     bool PackageSpecWithRemovePlan::compare_by_name(const PackageSpecWithRemovePlan* left, const PackageSpecWithRemovePlan* right)
     {
@@ -44,80 +109,57 @@ namespace vcpkg::Dependencies
     }
 
     PackageSpecWithRemovePlan::PackageSpecWithRemovePlan(const PackageSpec& spec, RemovePlanAction&& plan)
-        : spec(spec), plan(std::move(plan)) { }
+        : spec(spec)
+        , plan(std::move(plan)) { }
 
     std::vector<PackageSpecWithInstallPlan> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
     {
         std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
 
-        std::unordered_map<PackageSpec, InstallPlanAction> was_examined; // Examine = we have checked its immediate (non-recursive) dependencies
-        Graphs::Graph<PackageSpec> graph;
-        graph.add_vertices(specs);
-
-        std::vector<PackageSpec> examine_stack(specs);
-        while (!examine_stack.empty())
+        struct InstallAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, AnyParagraph>
         {
-            const PackageSpec spec = examine_stack.back();
-            examine_stack.pop_back();
-
-            if (was_examined.find(spec) != was_examined.end())
-            {
-                continue;
-            }
+            const VcpkgPaths& paths;
+            const StatusParagraphs& status_db;
 
-            auto process_dependencies = [&](const std::vector<std::string>& dependencies_as_string)
-                {
-                    for (const std::string& dep_as_string : dependencies_as_string)
-                    {
-                        const PackageSpec current_dep = PackageSpec::from_name_and_triplet(dep_as_string, spec.triplet()).value_or_exit(VCPKG_LINE_INFO);
-                        auto it = status_db.find_installed(current_dep);
-                        if (it != status_db.end())
-                        {
-                            continue;
-                        }
-
-                        graph.add_edge(spec, current_dep);
-                        if (was_examined.find(current_dep) == was_examined.end())
-                        {
-                            examine_stack.push_back(std::move(current_dep));
-                        }
-                    }
-                };
+            InstallAdjacencyProvider(const VcpkgPaths& p, const StatusParagraphs & s) : paths(p)
+                                                                                     , status_db(s) {}
 
-            const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
-            auto it = status_db.find_installed(spec);
-            if (it != status_db.end())
+            std::vector<PackageSpec> adjacency_list(const AnyParagraph& p) const override
             {
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::ALREADY_INSTALLED, request_type, nullopt, nullopt });
-                continue;
+                if (p.status_paragraph.get())
+                    return std::vector<PackageSpec>{};
+                return p.edges();
             }
 
-            Expected<BinaryParagraph> maybe_bpgh = Paragraphs::try_load_cached_package(paths, spec);
-            if (BinaryParagraph* bpgh = maybe_bpgh.get())
+            AnyParagraph load_vertex_data(const PackageSpec& spec) const override
             {
-                process_dependencies(bpgh->depends);
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::INSTALL, request_type, std::move(*bpgh), nullopt });
-                continue;
-            }
+                auto it = status_db.find_installed(spec);
+                if (it != status_db.end())
+                    return { spec, *it->get(), nullopt, nullopt };
 
-            Expected<SourceParagraph> maybe_spgh = Paragraphs::try_load_port(paths.port_dir(spec));
-            if (auto spgh = maybe_spgh.get())
-            {
-                process_dependencies(filter_dependencies(spgh->depends, spec.triplet()));
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::BUILD_AND_INSTALL, request_type, nullopt, std::move(*spgh) });
-            }
-            else
-            {
-                Checks::exit_with_message(VCPKG_LINE_INFO, "Cannot find package %s", spec.name());
+                Expected<BinaryParagraph> maybe_bpgh = Paragraphs::try_load_cached_package(paths, spec);
+                if (auto bpgh = maybe_bpgh.get())
+                    return { spec, nullopt, *bpgh, nullopt };
+
+                Expected<SourceParagraph> maybe_spgh = Paragraphs::try_load_port(paths.port_dir(spec));
+                if (auto spgh = maybe_spgh.get())
+                    return { spec, nullopt, nullopt, *spgh };
+
+                return { spec , nullopt, nullopt, nullopt };
             }
-        }
+        };
 
-        std::vector<PackageSpecWithInstallPlan> ret;
+        auto toposort = Graphs::topological_sort(specs, InstallAdjacencyProvider{ paths, status_db });
 
-        const std::vector<PackageSpec> pkgs = graph.topological_sort();
-        for (const PackageSpec& pkg : pkgs)
+        std::vector<PackageSpecWithInstallPlan> ret;
+        for (const AnyParagraph& pkg : toposort)
         {
-            ret.push_back(PackageSpecWithInstallPlan(pkg, std::move(was_examined[pkg])));
+            auto spec = pkg.spec;
+            const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
+            if (pkg.status_paragraph && request_type != RequestType::USER_REQUESTED)
+                continue;
+            InstallPlanAction a(pkg, request_type);
+            ret.push_back(PackageSpecWithInstallPlan(spec, std::move(a)));
         }
         return ret;
     }