Merge pull request #1461 from Microsoft/create_install_tests

feature packages graph algorithm

1 files changed, 281 insertions, 16 deletions

diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
index bbf807c95..820e51b33 100644
--- a/toolsrc/src/vcpkg_Dependencies.cpp
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -12,6 +12,8 @@
 
 namespace vcpkg::Dependencies
 {
+    bool operator==(const ClusterPtr& l, const ClusterPtr& r) { return l.ptr == r.ptr; }
+
     std::vector<PackageSpec> AnyParagraph::dependencies(const Triplet& triplet) const
     {
         auto to_package_specs = [&](const std::vector<std::string>& dependencies_as_string) {
@@ -55,6 +57,20 @@ namespace vcpkg::Dependencies
     }
 
     InstallPlanAction::InstallPlanAction(const PackageSpec& spec,
+                                         const SourceControlFile& any_paragraph,
+                                         const std::unordered_set<std::string>& features,
+                                         const RequestType& request_type)
+        : InstallPlanAction()
+    {
+        this->spec = spec;
+        this->request_type = request_type;
+
+        this->plan_type = InstallPlanType::BUILD_AND_INSTALL;
+        this->any_paragraph.source_control_file = &any_paragraph;
+        this->feature_list = features;
+    }
+
+    InstallPlanAction::InstallPlanAction(const PackageSpec& spec,
                                          const AnyParagraph& any_paragraph,
                                          const RequestType& request_type)
         : InstallPlanAction()
@@ -139,20 +155,53 @@ namespace vcpkg::Dependencies
         return left->spec.name() < right->spec.name();
     }
 
-    std::vector<InstallPlanAction> create_install_plan(const VcpkgPaths& paths,
+    MapPortFile::MapPortFile(const std::unordered_map<PackageSpec, SourceControlFile>& map) : ports(map) {}
+
+    const SourceControlFile& MapPortFile::get_control_file(const PackageSpec& spec) const
+    {
+        auto scf = ports.find(spec);
+        if (scf == ports.end())
+        {
+            Checks::exit_fail(VCPKG_LINE_INFO);
+        }
+        return scf->second;
+    }
+
+    PathsPortFile::PathsPortFile(const VcpkgPaths& paths) : ports(paths) {}
+
+    const SourceControlFile& PathsPortFile::get_control_file(const PackageSpec& spec) const
+    {
+        std::unordered_map<PackageSpec, SourceControlFile>::iterator cache_it = cache.find(spec);
+        if (cache_it != cache.end())
+        {
+            return cache_it->second;
+        }
+        Parse::ParseExpected<SourceControlFile> source_control_file =
+            Paragraphs::try_load_port(ports.get_filesystem(), ports.port_dir(spec));
+
+        if (auto scf = source_control_file.get())
+        {
+            auto it = cache.emplace(spec, std::move(*scf->get()));
+            return it.first->second;
+        }
+        print_error_message(source_control_file.error());
+        Checks::exit_fail(VCPKG_LINE_INFO);
+    }
+
+    std::vector<InstallPlanAction> create_install_plan(const PortFileProvider& port_file_provider,
                                                        const std::vector<PackageSpec>& specs,
                                                        const StatusParagraphs& status_db)
     {
         struct InstallAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, InstallPlanAction>
         {
-            const VcpkgPaths& paths;
+            const PortFileProvider& port_file_provider;
             const StatusParagraphs& status_db;
             const std::unordered_set<PackageSpec>& specs_as_set;
 
-            InstallAdjacencyProvider(const VcpkgPaths& p,
+            InstallAdjacencyProvider(const PortFileProvider& port_file_provider,
                                      const StatusParagraphs& s,
                                      const std::unordered_set<PackageSpec>& specs_as_set)
-                : paths(p), status_db(s), specs_as_set(specs_as_set)
+                : port_file_provider(port_file_provider), status_db(s), specs_as_set(specs_as_set)
             {
             }
 
@@ -169,23 +218,14 @@ namespace vcpkg::Dependencies
                                                      : 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<BinaryParagraph> maybe_bpgh = Paragraphs::try_load_cached_package(paths, spec);
-                if (auto bpgh = maybe_bpgh.get())
-                    return InstallPlanAction{spec, {nullopt, *bpgh, nullopt}, request_type};
-
-                auto maybe_scf = Paragraphs::try_load_port(paths.get_filesystem(), paths.port_dir(spec));
-                if (auto scf = maybe_scf.get())
-                    return InstallPlanAction{spec, {nullopt, nullopt, *scf->get()->core_paragraph}, request_type};
-
-                print_error_message(maybe_scf.error());
-                Checks::exit_fail(VCPKG_LINE_INFO);
+                return InstallPlanAction{
+                    spec, {nullopt, nullopt, *port_file_provider.get_control_file(spec).core_paragraph}, request_type};
             }
         };
 
         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});
+            Graphs::topological_sort(specs, InstallAdjacencyProvider{port_file_provider, status_db, specs_as_set});
         Util::erase_remove_if(toposort, [](const InstallPlanAction& plan) {
             return plan.request_type == RequestType::AUTO_SELECTED &&
                    plan.plan_type == InstallPlanType::ALREADY_INSTALLED;
@@ -298,4 +338,229 @@ namespace vcpkg::Dependencies
             Graphs::topological_sort(specs, ExportAdjacencyProvider{paths, status_db, specs_as_set});
         return toposort;
     }
+
+    std::vector<FeatureSpec> to_feature_specs(const std::vector<std::string>& depends, const Triplet& triplet)
+    {
+        std::vector<FeatureSpec> f_specs;
+        for (auto&& depend : depends)
+        {
+            int end = (int)depend.find(']');
+            if (end != std::string::npos)
+            {
+                int start = (int)depend.find('[');
+
+                auto feature_name = depend.substr(start + 1, end - start - 1);
+                auto package_name = depend.substr(0, start);
+                auto p_spec = PackageSpec::from_name_and_triplet(package_name, triplet).value_or_exit(VCPKG_LINE_INFO);
+                auto feature_spec = FeatureSpec{p_spec, feature_name};
+                f_specs.emplace_back(std::move(feature_spec));
+            }
+            else
+            {
+                auto p_spec = PackageSpec::from_name_and_triplet(depend, triplet).value_or_exit(VCPKG_LINE_INFO);
+
+                auto feature_spec = FeatureSpec{p_spec, ""};
+                f_specs.emplace_back(std::move(feature_spec));
+            }
+        }
+        return f_specs;
+    }
+
+    bool mark_plus(const std::string& feature,
+                   Cluster& cluster,
+                   std::unordered_map<PackageSpec, Cluster>& pkg_to_cluster,
+                   GraphPlan& graph_plan)
+    {
+        auto it = cluster.edges.find(feature);
+        std::string updated_feature = feature;
+        if (updated_feature == "")
+        {
+            updated_feature = "core";
+            it = cluster.edges.find("core");
+        }
+        if (it == cluster.edges.end())
+        {
+            Checks::unreachable(VCPKG_LINE_INFO);
+        }
+
+        if (cluster.edges[updated_feature].plus) return true;
+
+        if (cluster.original_features.find(updated_feature) == cluster.original_features.end())
+        {
+            cluster.transient_uninstalled = true;
+        }
+
+        if (!cluster.transient_uninstalled)
+        {
+            return false;
+        }
+        cluster.edges[updated_feature].plus = true;
+
+        if (!cluster.original_features.empty())
+        {
+            mark_minus(cluster, pkg_to_cluster, graph_plan);
+        }
+
+        graph_plan.install_graph.add_vertex({&cluster});
+        auto& tracked = cluster.to_install_features;
+        tracked.insert(updated_feature);
+        if (tracked.find("core") == tracked.end() && tracked.find("") == tracked.end())
+        {
+            cluster.to_install_features.insert("core");
+            for (auto&& depend : cluster.edges["core"].build_edges)
+            {
+                auto& depend_cluster = pkg_to_cluster[depend.spec];
+                mark_plus(depend.feature_name, depend_cluster, pkg_to_cluster, graph_plan);
+                graph_plan.install_graph.add_edge({&cluster}, {&depend_cluster});
+            }
+        }
+
+        for (auto&& depend : cluster.edges[updated_feature].build_edges)
+        {
+            auto& depend_cluster = pkg_to_cluster[depend.spec];
+            mark_plus(depend.feature_name, depend_cluster, pkg_to_cluster, graph_plan);
+            if (&depend_cluster == &cluster) continue;
+            graph_plan.install_graph.add_edge({&cluster}, {&depend_cluster});
+        }
+        return true;
+    }
+
+    void mark_minus(Cluster& cluster, std::unordered_map<PackageSpec, Cluster>& pkg_to_cluster, GraphPlan& graph_plan)
+    {
+        if (cluster.will_remove) return;
+        cluster.will_remove = true;
+
+        graph_plan.remove_graph.add_vertex({&cluster});
+        for (auto&& pair : cluster.edges)
+        {
+            auto& remove_edges_edges = pair.second.remove_edges;
+            for (auto&& depend : remove_edges_edges)
+            {
+                auto& depend_cluster = pkg_to_cluster[depend.spec];
+                graph_plan.remove_graph.add_edge({&cluster}, {&depend_cluster});
+                depend_cluster.transient_uninstalled = true;
+                mark_minus(depend_cluster, pkg_to_cluster, graph_plan);
+            }
+        }
+        for (auto&& original_feature : cluster.original_features)
+        {
+            cluster.transient_uninstalled = true;
+            mark_plus(original_feature, cluster, pkg_to_cluster, graph_plan);
+        }
+    }
+    std::vector<AnyAction> create_feature_install_plan(const std::unordered_map<PackageSpec, SourceControlFile>& map,
+                                                       const std::vector<FullPackageSpec>& specs,
+                                                       const StatusParagraphs& status_db)
+    {
+        std::unordered_map<PackageSpec, Cluster> pkg_spec_to_package_node;
+
+        for (const auto& it : map)
+        {
+            Cluster& node = pkg_spec_to_package_node[it.first];
+
+            node.spec = it.first;
+            FeatureNodeEdges core_dependencies;
+            auto core_depends = filter_dependencies(it.second.core_paragraph->depends, node.spec.triplet());
+            core_dependencies.build_edges = to_feature_specs(core_depends, node.spec.triplet());
+            node.edges["core"] = std::move(core_dependencies);
+
+            for (const auto& feature : it.second.feature_paragraphs)
+            {
+                FeatureNodeEdges added_edges;
+                auto depends = filter_dependencies(feature->depends, node.spec.triplet());
+                added_edges.build_edges = to_feature_specs(depends, node.spec.triplet());
+                node.edges.emplace(feature->name, std::move(added_edges));
+            }
+            node.source_control_file = &it.second;
+        }
+
+        for (auto&& status_paragraph : get_installed_ports(status_db))
+        {
+            auto& spec = status_paragraph->package.spec;
+            auto& status_paragraph_feature = status_paragraph->package.feature;
+            Cluster& cluster = pkg_spec_to_package_node[spec];
+
+            cluster.transient_uninstalled = false;
+            auto reverse_edges =
+                to_feature_specs(status_paragraph->package.depends, status_paragraph->package.spec.triplet());
+
+            for (auto&& dependency : reverse_edges)
+            {
+                auto pkg_node = pkg_spec_to_package_node.find(dependency.spec);
+                auto depends_name = dependency.feature_name;
+                if (depends_name == "")
+                {
+                    for (auto&& default_feature : status_paragraph->package.default_features)
+                    {
+                        auto& target_node = pkg_node->second.edges[default_feature];
+                        target_node.remove_edges.emplace_back(FeatureSpec{spec, status_paragraph_feature});
+                    }
+                    depends_name = "core";
+                }
+                auto& target_node = pkg_node->second.edges[depends_name];
+                target_node.remove_edges.emplace_back(FeatureSpec{spec, status_paragraph_feature});
+            }
+            cluster.status_paragraphs.emplace_back(*status_paragraph);
+            if (status_paragraph_feature == "")
+            {
+                cluster.original_features.insert("core");
+            }
+            else
+            {
+                cluster.original_features.insert(status_paragraph_feature);
+            }
+        }
+
+        GraphPlan graph_plan;
+        for (auto&& spec : specs)
+        {
+            Cluster& spec_cluster = pkg_spec_to_package_node[spec.package_spec];
+            for (auto&& feature : spec.features)
+            {
+                mark_plus(feature, spec_cluster, pkg_spec_to_package_node, graph_plan);
+            }
+        }
+
+        Graphs::GraphAdjacencyProvider<ClusterPtr> adjacency_remove_graph(graph_plan.remove_graph.adjacency_list());
+        auto remove_vertex_list = graph_plan.remove_graph.vertex_list();
+        auto remove_toposort = Graphs::topological_sort(remove_vertex_list, adjacency_remove_graph);
+
+        Graphs::GraphAdjacencyProvider<ClusterPtr> adjacency_install_graph(graph_plan.install_graph.adjacency_list());
+        auto insert_vertex_list = graph_plan.install_graph.vertex_list();
+        auto insert_toposort = Graphs::topological_sort(insert_vertex_list, adjacency_install_graph);
+
+        std::vector<AnyAction> install_plan;
+
+        for (auto&& like_cluster : remove_toposort)
+        {
+            auto scf = *like_cluster.ptr->source_control_file.get();
+
+            AnyAction any_plan;
+            any_plan.remove_plan = RemovePlanAction{
+                PackageSpec::from_name_and_triplet(scf->core_paragraph->name, like_cluster.ptr->spec.triplet())
+                    .value_or_exit(VCPKG_LINE_INFO),
+                RemovePlanType::REMOVE,
+                RequestType::AUTO_SELECTED};
+
+            install_plan.emplace_back(std::move(any_plan));
+        }
+
+        for (auto&& like_cluster : insert_toposort)
+        {
+            if (!like_cluster.ptr->transient_uninstalled) continue;
+
+            auto scf = *like_cluster.ptr->source_control_file.get();
+            auto pkg_spec =
+                PackageSpec::from_name_and_triplet(scf->core_paragraph->name, like_cluster.ptr->spec.triplet())
+                    .value_or_exit(VCPKG_LINE_INFO);
+            auto action =
+                InstallPlanAction{pkg_spec, *scf, like_cluster.ptr->to_install_features, RequestType::AUTO_SELECTED};
+
+            AnyAction any_plan;
+            any_plan.install_plan = std::move(action);
+            install_plan.emplace_back(std::move(any_plan));
+        }
+
+        return install_plan;
+    }
 }