Merge pull request #1461 from Microsoft/create_install_tests

feature packages graph algorithm

8 files changed, 231 insertions, 5 deletions

diff --git a/toolsrc/include/BinaryParagraph.h b/toolsrc/include/BinaryParagraph.h
index 1c2edf790..f411b3c39 100644
--- a/toolsrc/include/BinaryParagraph.h
+++ b/toolsrc/include/BinaryParagraph.h
@@ -14,6 +14,9 @@ namespace vcpkg
         BinaryParagraph();
         explicit BinaryParagraph(std::unordered_map<std::string, std::string> fields);
         BinaryParagraph(const SourceParagraph& spgh, const Triplet& triplet);
+        BinaryParagraph::BinaryParagraph(const SourceParagraph& spgh,
+                                         const FeatureParagraph& fpgh,
+                                         const Triplet& triplet);
 
         std::string displayname() const;
 
@@ -25,8 +28,10 @@ namespace vcpkg
         std::string version;
         std::string description;
         std::string maintainer;
+        std::string feature;
+        std::vector<std::string> default_features;
         std::vector<std::string> depends;
     };
 
     void serialize(const BinaryParagraph& pgh, std::string& out_str);
-}
+}
\ No newline at end of file
diff --git a/toolsrc/include/PackageSpec.h b/toolsrc/include/PackageSpec.h
index 62b6fc9de..15b5e5b9b 100644
--- a/toolsrc/include/PackageSpec.h
+++ b/toolsrc/include/PackageSpec.h
@@ -1,5 +1,6 @@
 #pragma once
 #include "PackageSpecParseResult.h"
+#include "SourceParagraph.h"
 #include "Triplet.h"
 #include "vcpkg_expected.h"
 
@@ -7,8 +8,6 @@ namespace vcpkg
 {
     struct PackageSpec
     {
-        static ExpectedT<PackageSpec, PackageSpecParseResult> from_string(const std::string& spec_as_string,
-                                                                          const Triplet& default_triplet);
         static std::string to_string(const std::string& name, const Triplet& triplet);
         static ExpectedT<PackageSpec, PackageSpecParseResult> from_name_and_triplet(const std::string& name,
                                                                                     const Triplet& triplet);
@@ -30,6 +29,9 @@ namespace vcpkg
     {
         PackageSpec package_spec;
         std::vector<std::string> features;
+
+        static ExpectedT<FullPackageSpec, PackageSpecParseResult> from_string(const std::string& spec_as_string,
+                                                                              const Triplet& default_triplet);
     };
 
     bool operator==(const PackageSpec& left, const PackageSpec& right);
diff --git a/toolsrc/include/SourceParagraph.h b/toolsrc/include/SourceParagraph.h
index e85884b51..7ddf999cc 100644
--- a/toolsrc/include/SourceParagraph.h
+++ b/toolsrc/include/SourceParagraph.h
@@ -60,6 +60,7 @@ namespace vcpkg
 
     std::vector<std::string> filter_dependencies(const std::vector<Dependency>& deps, const Triplet& t);
 
+    // zlib[uwp] becomes Dependency{"zlib", "uwp"}
     std::vector<Dependency> expand_qualified_dependencies(const std::vector<std::string>& depends);
     std::vector<std::string> parse_comma_list(const std::string& str);
 
diff --git a/toolsrc/include/vcpkg_Build.h b/toolsrc/include/vcpkg_Build.h
index 9a4e2baeb..c4f3e6746 100644
--- a/toolsrc/include/vcpkg_Build.h
+++ b/toolsrc/include/vcpkg_Build.h
@@ -95,14 +95,35 @@ namespace vcpkg::Build
                            const Triplet& triplet,
                            fs::path&& port_dir,
                            const BuildPackageOptions& build_package_options)
-            : src(src), triplet(triplet), port_dir(std::move(port_dir)), build_package_options(build_package_options)
+            : src(src)
+            , scf(nullptr)
+            , triplet(triplet)
+            , port_dir(std::move(port_dir))
+            , build_package_options(build_package_options)
+            , feature_list(nullptr)
+        {
+        }
+
+        BuildPackageConfig(const SourceControlFile& src,
+                           const Triplet& triplet,
+                           fs::path&& port_dir,
+                           const BuildPackageOptions& build_package_options,
+                           const std::unordered_set<std::string>& feature_list)
+            : src(*src.core_paragraph)
+            , scf(&src)
+            , triplet(triplet)
+            , port_dir(std::move(port_dir))
+            , build_package_options(build_package_options)
+            , feature_list(&feature_list)
         {
         }
 
         const SourceParagraph& src;
+        const SourceControlFile* scf;
         const Triplet& triplet;
         fs::path port_dir;
         const BuildPackageOptions& build_package_options;
+        const std::unordered_set<std::string>* feature_list;
     };
 
     ExtendedBuildResult build_package(const VcpkgPaths& paths,
diff --git a/toolsrc/include/vcpkg_Commands.h b/toolsrc/include/vcpkg_Commands.h
index 67319f240..8348a64e4 100644
--- a/toolsrc/include/vcpkg_Commands.h
+++ b/toolsrc/include/vcpkg_Commands.h
@@ -77,6 +77,7 @@ namespace vcpkg::Commands
     namespace Remove
     {
         void perform_and_exit(const VcpkgCmdArguments& args, const VcpkgPaths& paths, const Triplet& default_triplet);
+        void remove_package(const VcpkgPaths& paths, const PackageSpec& spec, StatusParagraphs* status_db);
     }
 
     namespace Update
diff --git a/toolsrc/include/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
index 018c4f5cf..e3af0fd28 100644
--- a/toolsrc/include/vcpkg_Dependencies.h
+++ b/toolsrc/include/vcpkg_Dependencies.h
@@ -2,6 +2,7 @@
 #include "PackageSpec.h"
 #include "StatusParagraphs.h"
 #include "VcpkgPaths.h"
+#include "vcpkg_Graphs.h"
 #include "vcpkg_optional.h"
 #include <vector>
 
@@ -23,7 +24,49 @@ namespace vcpkg::Dependencies
         Optional<StatusParagraph> status_paragraph;
         Optional<BinaryParagraph> binary_paragraph;
         Optional<SourceParagraph> source_paragraph;
+        Optional<const SourceControlFile*> source_control_file;
     };
+}
+
+namespace vcpkg::Dependencies
+{
+    struct FeatureSpec
+    {
+        PackageSpec spec;
+        std::string feature_name;
+    };
+
+    struct FeatureNodeEdges
+    {
+        std::vector<FeatureSpec> remove_edges;
+        std::vector<FeatureSpec> build_edges;
+        bool plus = false;
+    };
+    std::vector<FeatureSpec> to_feature_specs(const std::vector<std::string>& depends, const Triplet& t);
+
+    struct Cluster
+    {
+        std::vector<StatusParagraph> status_paragraphs;
+        Optional<const SourceControlFile*> source_control_file;
+        PackageSpec spec;
+        std::unordered_map<std::string, FeatureNodeEdges> edges;
+        std::unordered_set<std::string> to_install_features;
+        std::unordered_set<std::string> original_features;
+        bool will_remove = false;
+        bool transient_uninstalled = true;
+        Cluster() = default;
+
+    private:
+        Cluster(const Cluster&) = delete;
+        Cluster& operator=(const Cluster&) = delete;
+    };
+
+    struct ClusterPtr
+    {
+        Cluster* ptr;
+    };
+
+    bool operator==(const ClusterPtr& l, const ClusterPtr& r);
 
     enum class InstallPlanType
     {
@@ -39,6 +82,10 @@ namespace vcpkg::Dependencies
 
         InstallPlanAction();
         InstallPlanAction(const PackageSpec& spec, const AnyParagraph& any_paragraph, const RequestType& request_type);
+        InstallPlanAction(const PackageSpec& spec,
+                          const SourceControlFile& any_paragraph,
+                          const std::unordered_set<std::string>& features,
+                          const RequestType& request_type);
         InstallPlanAction(const InstallPlanAction&) = delete;
         InstallPlanAction(InstallPlanAction&&) = default;
         InstallPlanAction& operator=(const InstallPlanAction&) = delete;
@@ -48,6 +95,7 @@ namespace vcpkg::Dependencies
         AnyParagraph any_paragraph;
         InstallPlanType plan_type;
         RequestType request_type;
+        std::unordered_set<std::string> feature_list;
     };
 
     enum class RemovePlanType
@@ -73,6 +121,12 @@ namespace vcpkg::Dependencies
         RequestType request_type;
     };
 
+    struct AnyAction
+    {
+        Optional<InstallPlanAction> install_plan;
+        Optional<RemovePlanAction> remove_plan;
+    };
+
     enum class ExportPlanType
     {
         UNKNOWN,
@@ -97,7 +151,28 @@ namespace vcpkg::Dependencies
         RequestType request_type;
     };
 
-    std::vector<InstallPlanAction> create_install_plan(const VcpkgPaths& paths,
+    __interface PortFileProvider { virtual const SourceControlFile& get_control_file(const PackageSpec& spec) const; };
+
+    struct MapPortFile : PortFileProvider
+    {
+        const std::unordered_map<PackageSpec, SourceControlFile>& ports;
+        explicit MapPortFile(const std::unordered_map<PackageSpec, SourceControlFile>& map);
+        const SourceControlFile& get_control_file(const PackageSpec& spec) const override;
+    };
+
+    struct PathsPortFile : PortFileProvider
+    {
+        const VcpkgPaths& ports;
+        mutable std::unordered_map<PackageSpec, SourceControlFile> cache;
+        explicit PathsPortFile(const VcpkgPaths& paths);
+        const SourceControlFile& get_control_file(const PackageSpec& spec) const override;
+
+    private:
+        PathsPortFile(const PathsPortFile&) = delete;
+        PathsPortFile& operator=(const PathsPortFile&) = delete;
+    };
+
+    std::vector<InstallPlanAction> create_install_plan(const PortFileProvider& port_file_provider,
                                                        const std::vector<PackageSpec>& specs,
                                                        const StatusParagraphs& status_db);
 
@@ -108,3 +183,30 @@ namespace vcpkg::Dependencies
                                                      const std::vector<PackageSpec>& specs,
                                                      const StatusParagraphs& status_db);
 }
+
+template<>
+struct std::hash<vcpkg::Dependencies::ClusterPtr>
+{
+    size_t operator()(const vcpkg::Dependencies::ClusterPtr& value) const
+    {
+        return std::hash<vcpkg::PackageSpec>()(value.ptr->spec);
+    }
+};
+
+namespace vcpkg::Dependencies
+{
+    struct GraphPlan
+    {
+        Graphs::Graph<ClusterPtr> remove_graph;
+        Graphs::Graph<ClusterPtr> install_graph;
+    };
+    bool mark_plus(const std::string& feature,
+                   Cluster& cluster,
+                   std::unordered_map<PackageSpec, Cluster>& pkg_to_cluster,
+                   GraphPlan& graph_plan);
+    void mark_minus(Cluster& cluster, std::unordered_map<PackageSpec, Cluster>& pkg_to_cluster, GraphPlan& 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);
+}
diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h
index 3c8c024c2..13c0a7136 100644
--- a/toolsrc/include/vcpkg_Graphs.h
+++ b/toolsrc/include/vcpkg_Graphs.h
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <unordered_map>
+#include <unordered_set>
 
 namespace vcpkg::Graphs
 {
@@ -63,4 +64,96 @@ namespace vcpkg::Graphs
 
         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
+    {
+    public:
+        void add_vertex(V v) { this->vertices[v]; }
+
+        // TODO: Change with iterators
+        void add_vertices(const std::vector<V>& vs)
+        {
+            for (const V& v : vs)
+            {
+                this->vertices[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.
+                {
+                    V vertex = pair.first;
+                    topological_sort_internal(vertex, adjacency_provider, exploration_status, sorted);
+                }
+            }
+
+            return sorted;
+        }
+
+        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;
+        }
+
+        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;
+        }
+
+    private:
+        std::unordered_map<V, std::unordered_set<V>> vertices;
+    };
 }
diff --git a/toolsrc/include/vcpkg_Util.h b/toolsrc/include/vcpkg_Util.h
index 1bd1bcc4a..671997e7e 100644
--- a/toolsrc/include/vcpkg_Util.h
+++ b/toolsrc/include/vcpkg_Util.h
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <map>
 #include <utility>
 #include <vector>