Merge from master

1 files changed, 143 insertions, 117 deletions

diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
index 3e3f502b5..03e3c2aeb 100644
--- a/toolsrc/src/vcpkg_Dependencies.cpp
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -5,10 +5,40 @@
 #include "PackageSpec.h"
 #include "StatusParagraphs.h"
 #include "vcpkg_Files.h"
+#include "vcpkg_Util.h"
+#include "vcpkglib.h"
 #include "Paragraphs.h"
 
 namespace vcpkg::Dependencies
 {
+    std::vector<PackageSpec> AnyParagraph::dependencies(const Triplet& triplet) 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, 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, triplet));
+        }
+
+        Checks::exit_with_message(VCPKG_LINE_INFO, "Cannot get dependencies because there was none of: source/binary/status paragraphs");
+    }
+
     std::string to_output_string(RequestType request_type, const CStringView s)
     {
         switch (request_type)
@@ -22,160 +52,156 @@ namespace vcpkg::Dependencies
         }
     }
 
-    InstallPlanAction::InstallPlanAction() : plan_type(InstallPlanType::UNKNOWN), request_type(RequestType::UNKNOWN), binary_pgh(nullopt), source_pgh(nullopt) { }
-
-    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)) { }
+    InstallPlanAction::InstallPlanAction() : spec()
+                                           , any_paragraph()
+                                           , plan_type(InstallPlanType::UNKNOWN)
+                                           , request_type(RequestType::UNKNOWN) { }
 
-    bool PackageSpecWithInstallPlan::compare_by_name(const PackageSpecWithInstallPlan* left, const PackageSpecWithInstallPlan* right)
+    InstallPlanAction::InstallPlanAction(const PackageSpec& spec, const AnyParagraph& any_paragraph, const RequestType& request_type) : InstallPlanAction()
     {
-        return left->spec.name() < right->spec.name();
-    }
+        this->spec = spec;
+        this->request_type = request_type;
+        if (auto p = any_paragraph.status_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::ALREADY_INSTALLED;
+            this->any_paragraph.status_paragraph = *p;
+            return;
+        }
 
-    PackageSpecWithInstallPlan::PackageSpecWithInstallPlan(const PackageSpec& spec, InstallPlanAction&& plan) : spec(spec), plan(std::move(plan)) { }
+        if (auto p = any_paragraph.binary_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::INSTALL;
+            this->any_paragraph.binary_paragraph = *p;
+            return;
+        }
 
-    RemovePlanAction::RemovePlanAction() : plan_type(RemovePlanType::UNKNOWN), request_type(RequestType::UNKNOWN) { }
+        if (auto p = any_paragraph.source_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::BUILD_AND_INSTALL;
+            this->any_paragraph.source_paragraph = *p;
+            return;
+        }
 
-    RemovePlanAction::RemovePlanAction(const RemovePlanType& plan_type, const Dependencies::RequestType& request_type) : plan_type(plan_type), request_type(request_type) { }
+        this->plan_type = InstallPlanType::UNKNOWN;
+    }
 
-    bool PackageSpecWithRemovePlan::compare_by_name(const PackageSpecWithRemovePlan* left, const PackageSpecWithRemovePlan* right)
+    bool InstallPlanAction::compare_by_name(const InstallPlanAction* left, const InstallPlanAction* right)
     {
         return left->spec.name() < right->spec.name();
     }
 
-    PackageSpecWithRemovePlan::PackageSpecWithRemovePlan(const PackageSpec& spec, RemovePlanAction&& plan)
-        : spec(spec), plan(std::move(plan)) { }
+    RemovePlanAction::RemovePlanAction() : plan_type(RemovePlanType::UNKNOWN)
+                                         , request_type(RequestType::UNKNOWN) { }
 
-    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());
+    RemovePlanAction::RemovePlanAction(const PackageSpec& spec, const RemovePlanType& plan_type, const RequestType& request_type)
+        : spec(spec)
+        , plan_type(plan_type)
+        , request_type(request_type) { }
 
-        std::unordered_map<PackageSpec, InstallPlanAction> was_examined; // Examine = we have checked its immediate (non-recursive) dependencies
-        Graphs::Graph<PackageSpec> graph;
-        graph.add_vertices(specs);
+    bool RemovePlanAction::compare_by_name(const RemovePlanAction* left, const RemovePlanAction* right)
+    {
+        return left->spec.name() < right->spec.name();
+    }
 
-        std::vector<PackageSpec> examine_stack(specs);
-        while (!examine_stack.empty())
+    std::vector<InstallPlanAction> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
+    {
+        struct InstallAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, InstallPlanAction>
         {
-            const PackageSpec spec = examine_stack.back();
-            examine_stack.pop_back();
+            const VcpkgPaths& paths;
+            const StatusParagraphs& status_db;
+            const std::unordered_set<PackageSpec>& specs_as_set;
 
-            if (was_examined.find(spec) != was_examined.end())
-            {
-                continue;
-            }
+            InstallAdjacencyProvider(const VcpkgPaths& p, const StatusParagraphs& s, const std::unordered_set<PackageSpec>& specs_as_set) : paths(p)
+                                                                                                                                          , status_db(s)
+                                                                                                                                          , specs_as_set(specs_as_set) {}
 
-            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));
-                        }
-                    }
-                };
-
-            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 InstallPlanAction& p) const override
             {
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::ALREADY_INSTALLED, request_type, nullopt, nullopt });
-                continue;
+                if (p.any_paragraph.status_paragraph.get())
+                    return std::vector<PackageSpec>{};
+                return p.any_paragraph.dependencies(p.spec.triplet());
             }
 
-            Expected<BinaryParagraph> maybe_bpgh = Paragraphs::try_load_cached_package(paths, spec);
-            if (BinaryParagraph* bpgh = maybe_bpgh.get())
+            InstallPlanAction 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;
-            }
+                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())
+                    return InstallPlanAction{ spec, { *it->get(), nullopt, nullopt }, request_type };
 
-            Expected<SourceParagraph> maybe_spgh = Paragraphs::try_load_port(paths.get_filesystem(), 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 InstallPlanAction{ spec, { nullopt, *bpgh, nullopt }, request_type };
+
+                Expected<SourceParagraph> maybe_spgh = Paragraphs::try_load_port(paths.get_filesystem(), paths.port_dir(spec));
+                if (auto spgh = maybe_spgh.get())
+                    return InstallPlanAction{ spec, { nullopt, nullopt, *spgh }, request_type };
+
+                return InstallPlanAction{ spec , { nullopt, nullopt, nullopt }, request_type };
             }
-        }
+        };
 
-        std::vector<PackageSpecWithInstallPlan> ret;
+        const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
+        std::vector<InstallPlanAction> toposort = Graphs::topological_sort(specs, InstallAdjacencyProvider{ paths, status_db, specs_as_set });
+        Util::keep_if(toposort, [](const InstallPlanAction& p)
+                      {
+                          return !(p.request_type == RequestType::AUTO_SELECTED && p.plan_type == InstallPlanType::ALREADY_INSTALLED);
+                      });
 
-        const std::vector<PackageSpec> pkgs = graph.find_topological_sort();
-        for (const PackageSpec& pkg : pkgs)
-        {
-            ret.push_back(PackageSpecWithInstallPlan(pkg, std::move(was_examined[pkg])));
-        }
-        return ret;
+        return toposort;
     }
 
-    std::vector<PackageSpecWithRemovePlan> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
+    std::vector<RemovePlanAction> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
     {
-        std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
-
-        std::unordered_map<PackageSpec, RemovePlanAction> 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 RemoveAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, RemovePlanAction>
         {
-            const PackageSpec spec = examine_stack.back();
-            examine_stack.pop_back();
-
-            if (was_examined.find(spec) != was_examined.end())
-            {
-                continue;
-            }
+            const StatusParagraphs& status_db;
+            const std::vector<StatusParagraph*>& installed_ports;
+            const std::unordered_set<PackageSpec>& specs_as_set;
 
-            const StatusParagraphs::const_iterator it = status_db.find(spec);
-            if (it == status_db.end() || (*it)->state == InstallState::NOT_INSTALLED)
-            {
-                was_examined.emplace(spec, RemovePlanAction(RemovePlanType::NOT_INSTALLED, RequestType::USER_REQUESTED));
-                continue;
-            }
+            RemoveAdjacencyProvider(const StatusParagraphs& status_db, const std::vector<StatusParagraph*>& installed_ports, const std::unordered_set<PackageSpec>& specs_as_set)
+                : status_db(status_db)
+                , installed_ports(installed_ports)
+                , specs_as_set(specs_as_set) { }
 
-            for (const std::unique_ptr<StatusParagraph>& an_installed_package : status_db)
+            std::vector<PackageSpec> adjacency_list(const RemovePlanAction& p) const override
             {
-                if (an_installed_package->want != Want::INSTALL)
-                    continue;
-                if (an_installed_package->package.spec.triplet() != spec.triplet())
-                    continue;
+                if (p.plan_type == RemovePlanType::NOT_INSTALLED)
+                {
+                    return {};
+                }
 
-                const std::vector<std::string>& deps = an_installed_package->package.depends;
-                if (std::find(deps.begin(), deps.end(), spec.name()) == deps.end())
+                const PackageSpec& spec = p.spec;
+                std::vector<PackageSpec> dependents;
+                for (const StatusParagraph* an_installed_package : installed_ports)
                 {
-                    continue;
+                    if (an_installed_package->package.spec.triplet() != spec.triplet())
+                        continue;
+
+                    const std::vector<std::string>& deps = an_installed_package->package.depends;
+                    if (std::find(deps.begin(), deps.end(), spec.name()) == deps.end())
+                        continue;
+
+                    dependents.push_back(an_installed_package->package.spec);
                 }
 
-                graph.add_edge(spec, an_installed_package.get()->package.spec);
-                examine_stack.push_back(an_installed_package.get()->package.spec);
+                return dependents;
             }
 
-            const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
-            was_examined.emplace(spec, RemovePlanAction(RemovePlanType::REMOVE, request_type));
-        }
-
-        std::vector<PackageSpecWithRemovePlan> ret;
+            RemovePlanAction load_vertex_data(const PackageSpec& spec) const override
+            {
+                const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
+                const StatusParagraphs::const_iterator it = status_db.find_installed(spec);
+                if (it == status_db.end())
+                {
+                    return RemovePlanAction{ spec, RemovePlanType::NOT_INSTALLED, request_type };
+                }
+                return RemovePlanAction{ spec, RemovePlanType::REMOVE, request_type };
+            }
+        };
 
-        const std::vector<PackageSpec> pkgs = graph.find_topological_sort();
-        for (const PackageSpec& pkg : pkgs)
-        {
-            ret.push_back(PackageSpecWithRemovePlan(pkg, std::move(was_examined[pkg])));
-        }
-        return ret;
+        const std::vector<StatusParagraph*>& installed_ports = get_installed_ports(status_db);
+        const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
+        return Graphs::topological_sort(specs, RemoveAdjacencyProvider{ status_db, installed_ports, specs_as_set });
     }
 }