feature packages graph traversal

8 files changed, 752 insertions, 3 deletions

diff --git a/toolsrc/include/BinaryParagraph.h b/toolsrc/include/BinaryParagraph.h
index 1c2edf790..4adde5e36 100644
--- a/toolsrc/include/BinaryParagraph.h
+++ b/toolsrc/include/BinaryParagraph.h
@@ -25,8 +25,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/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
index c8e15de27..92523a654 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,6 +24,45 @@ namespace vcpkg::Dependencies
         Optional<StatusParagraph> status_paragraph;
         Optional<BinaryParagraph> binary_paragraph;
         Optional<SourceParagraph> source_paragraph;
+        Optional<const SourceControlFile*> source_control_file;
+    };
+
+    struct ClusterNode
+    {
+        std::vector<StatusParagraph> status_paragraphs;
+        Optional<const SourceControlFile*> source_paragraph;
+    };
+}
+
+namespace vcpkg::Dependencies
+{
+    struct FeatureSpec
+    {
+        PackageSpec spec;
+        std::string feature_name;
+    };
+
+    struct FeatureNodeEdges
+    {
+        std::vector<FeatureSpec> dotted;
+        std::vector<FeatureSpec> dashed;
+        bool plus = false;
+    };
+    std::vector<FeatureSpec> to_feature_specs(const std::vector<std::string> depends,
+                                              const std::unordered_map<std::string, PackageSpec> str_to_spec);
+    struct Cluster
+    {
+        ClusterNode cluster_node;
+        std::unordered_map<std::string, FeatureNodeEdges> edges;
+        std::unordered_set<std::string> tracked_nodes;
+        std::unordered_set<std::string> original_nodes;
+        bool minus = false;
+        bool zero = true;
+        Cluster() = default;
+
+    private:
+        Cluster(const Cluster&) = delete;
+        Cluster& operator=(const Cluster&) = delete;
     };
 
     enum class InstallPlanType
@@ -39,6 +79,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,
+                          std::unordered_set<std::string> features,
+                          const RequestType& request_type);
         InstallPlanAction(const InstallPlanAction&) = delete;
         InstallPlanAction(InstallPlanAction&&) = default;
         InstallPlanAction& operator=(const InstallPlanAction&) = delete;
@@ -48,6 +92,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 +118,12 @@ namespace vcpkg::Dependencies
         RequestType request_type;
     };
 
+    struct AnyAction
+    {
+        Optional<InstallPlanAction> install_plan;
+        Optional<RemovePlanAction> remove_plan;
+    };
+
     enum class ExportPlanType
     {
         UNKNOWN,
@@ -125,3 +176,41 @@ namespace vcpkg::Dependencies
                                                      const std::vector<PackageSpec>& specs,
                                                      const StatusParagraphs& status_db);
 }
+
+template<>
+struct std::hash<vcpkg::Dependencies::Cluster>
+{
+    size_t operator()(const vcpkg::Dependencies::Cluster& value) const
+    {
+        size_t hash = 17;
+        if (auto source = value.cluster_node.source_paragraph.get())
+        {
+            hash = hash * 31 + std::hash<std::string>()((*source)->core_paragraph->name);
+        }
+        else if (!value.cluster_node.status_paragraphs.empty())
+        {
+            auto start = *value.cluster_node.status_paragraphs.begin();
+            hash = hash * 31 + std::hash<std::string>()(start.package.displayname());
+        }
+
+        return hash;
+    }
+};
+
+namespace vcpkg::Dependencies
+{
+    struct GraphPlan
+    {
+        Graphs::Graph<Cluster*> remove_graph;
+        Graphs::Graph<Cluster*> 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>
 
diff --git a/toolsrc/src/BinaryParagraph.cpp b/toolsrc/src/BinaryParagraph.cpp
index af76c6b29..e126054a8 100644
--- a/toolsrc/src/BinaryParagraph.cpp
+++ b/toolsrc/src/BinaryParagraph.cpp
@@ -16,9 +16,11 @@ namespace vcpkg
 
     namespace Fields
     {
+        static const std::string FEATURE = "Feature";
         static const std::string DESCRIPTION = "Description";
         static const std::string MAINTAINER = "Maintainer";
         static const std::string DEPENDS = "Depends";
+        static const std::string DEFAULTFEATURES = "Default-Features";
     }
 
     BinaryParagraph::BinaryParagraph() = default;
@@ -38,7 +40,10 @@ namespace vcpkg
                              .value_or_exit(VCPKG_LINE_INFO);
         }
 
-        parser.required_field(Fields::VERSION, this->version);
+        // one or the other
+        this->version = parser.optional_field(Fields::VERSION);
+        this->feature = parser.optional_field(Fields::FEATURE);
+
         this->description = parser.optional_field(Fields::DESCRIPTION);
         this->maintainer = parser.optional_field(Fields::MAINTAINER);
 
@@ -46,6 +51,10 @@ namespace vcpkg
         parser.required_field(Fields::MULTI_ARCH, multi_arch);
 
         this->depends = parse_comma_list(parser.optional_field(Fields::DEPENDS));
+        if (this->feature.empty())
+        {
+            this->default_features = parse_comma_list(parser.optional_field(Fields::DEFAULTFEATURES));
+        }
 
         if (auto err = parser.error_info(this->spec.name()))
         {
diff --git a/toolsrc/src/PackageSpec.cpp b/toolsrc/src/PackageSpec.cpp
index ab005f255..12217ac98 100644
--- a/toolsrc/src/PackageSpec.cpp
+++ b/toolsrc/src/PackageSpec.cpp
@@ -5,7 +5,10 @@
 
 namespace vcpkg
 {
-    static bool is_valid_package_spec_char(char c) { return (c == '-') || isdigit(c) || (isalpha(c) && islower(c)); }
+    static bool is_valid_package_spec_char(char c)
+    {
+        return (c == '-') || isdigit(c) || (isalpha(c) && islower(c)) || (c == '[') || (c == ']');
+    }
 
     ExpectedT<PackageSpec, PackageSpecParseResult> PackageSpec::from_string(const std::string& spec_as_string,
                                                                             const Triplet& default_triplet)
diff --git a/toolsrc/src/test_install_plan.cpp b/toolsrc/src/test_install_plan.cpp
index 93a1436d8..d90e1e523 100644
--- a/toolsrc/src/test_install_plan.cpp
+++ b/toolsrc/src/test_install_plan.cpp
@@ -1,5 +1,6 @@
 #include "CppUnitTest.h"
 #include "vcpkg_Dependencies.h"
+#include "vcpkg_Util.h"
 
 using namespace Microsoft::VisualStudio::CppUnitTestFramework;
 
@@ -24,6 +25,35 @@ namespace UnitTest1
                 return PackageSpec{*spec.get()};
             }
         };
+
+        static void features_check(Dependencies::AnyAction* install_action,
+                                   std::string pkg_name,
+                                   std::vector<std::string> vec)
+        {
+            const auto& plan = *install_action->install_plan.get();
+            const auto& feature_list = plan.feature_list;
+
+            Assert::AreEqual(pkg_name.c_str(),
+                             (*plan.any_paragraph.source_control_file.get())->core_paragraph->name.c_str());
+            Assert::AreEqual(size_t(vec.size()), feature_list.size());
+
+            for (auto&& feature_name : vec)
+            {
+                if (feature_name == "core" || feature_name == "")
+                {
+                    Assert::IsTrue(Util::find(feature_list, "core") != feature_list.end() ||
+                                   Util::find(feature_list, "") != feature_list.end());
+                    continue;
+                }
+                Assert::IsTrue(Util::find(feature_list, feature_name) != feature_list.end());
+            }
+        }
+
+        static void remove_plan_check(Dependencies::AnyAction* install_action, std::string pkg_name)
+        {
+            Assert::AreEqual(pkg_name.c_str(), install_action->remove_plan.get()->spec.name().c_str());
+        }
+
         TEST_METHOD(basic_install_scheme)
         {
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
@@ -139,5 +169,283 @@ namespace UnitTest1
             Assert::AreEqual("b", install_plan[6].spec.name().c_str());
             Assert::AreEqual("a", install_plan[7].spec.name().c_str());
         }
+
+        TEST_METHOD(basic_feature_test_1)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "a"},
+                                                                              {"Default-Features", ""},
+                                                                              {"Version", "1.3.8"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", "b, b[beefeatureone]"},
+                                                                              {"Status", "install ok installed"}}));
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "b"},
+                                                                              {"Feature", "beefeatureone"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "b"},
+                                                                              {"Default-Features", "beefeatureone"},
+                                                                              {"Version", "1.3"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+
+            PackageSpecMap spec_map;
+
+            auto spec_a =
+                FullPackageSpec{spec_map.get_package_spec(
+                                    {{{"Source", "a"}, {"Version", "1.3.8"}, {"Build-Depends", "b, b[beefeatureone]"}},
+                                     {{"Feature", "featureone"},
+                                      {"Description", "the first feature for a"},
+                                      {"Build-Depends", "b[beefeaturetwo]"}}
+
+                                    }),
+                                {"featureone"}};
+            auto spec_b = FullPackageSpec{spec_map.get_package_spec(
+                {{{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+                 {{"Feature", "beefeatureone"}, {"Description", "the first feature for b"}, {"Build-Depends", ""}},
+                 {{"Feature", "beefeaturetwo"}, {"Description", "the second feature for b"}, {"Build-Depends", ""}},
+                 {{"Feature", "beefeaturethree"}, {"Description", "the third feature for b"}, {"Build-Depends", ""}}
+
+                })};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_a}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(4), install_plan.size());
+            remove_plan_check(&install_plan[0], "a");
+            remove_plan_check(&install_plan[1], "b");
+            features_check(&install_plan[2], "b", {"beefeatureone", "core", "beefeatureone"});
+            features_check(&install_plan[3], "a", {"featureone", "core"});
+        }
+
+        TEST_METHOD(basic_feature_test_2)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+
+            PackageSpecMap spec_map;
+
+            auto spec_a =
+                FullPackageSpec{spec_map.get_package_spec(
+                                    {{{"Source", "a"}, {"Version", "1.3.8"}, {"Build-Depends", "b[beefeatureone]"}},
+                                     {{"Feature", "featureone"},
+                                      {"Description", "the first feature for a"},
+                                      {"Build-Depends", "b[beefeaturetwo]"}}
+
+                                    }),
+                                {"featureone"}};
+            auto spec_b = FullPackageSpec{spec_map.get_package_spec(
+                {{{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+                 {{"Feature", "beefeatureone"}, {"Description", "the first feature for b"}, {"Build-Depends", ""}},
+                 {{"Feature", "beefeaturetwo"}, {"Description", "the second feature for b"}, {"Build-Depends", ""}},
+                 {{"Feature", "beefeaturethree"}, {"Description", "the third feature for b"}, {"Build-Depends", ""}}
+
+                })};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_a}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(2), install_plan.size());
+            features_check(&install_plan[0], "b", {"beefeatureone", "beefeaturetwo", "core"});
+            features_check(&install_plan[1], "a", {"featureone", "core"});
+        }
+
+        TEST_METHOD(basic_feature_test_3)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "a"},
+                                                                              {"Default-Features", ""},
+                                                                              {"Version", "1.3"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+
+            PackageSpecMap spec_map;
+
+            auto spec_a = FullPackageSpec{
+                spec_map.get_package_spec(
+                    {{{"Source", "a"}, {"Version", "1.3"}, {"Build-Depends", "b"}},
+                     {{"Feature", "one"}, {"Description", "the first feature for a"}, {"Build-Depends", ""}}}),
+                {"core"}};
+            auto spec_b = FullPackageSpec{spec_map.get_package_spec({
+                {{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+            })};
+            auto spec_c = FullPackageSpec{spec_map.get_package_spec({
+                                              {{"Source", "c"}, {"Version", "1.3"}, {"Build-Depends", "a[one]"}},
+                                          }),
+                                          {"core"}};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_c, spec_a}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(4), install_plan.size());
+            remove_plan_check(&install_plan[0], "a");
+            features_check(&install_plan[1], "b", {"core"});
+            features_check(&install_plan[2], "a", {"one", "core"});
+            features_check(&install_plan[3], "c", {"core"});
+        }
+
+        TEST_METHOD(basic_feature_test_4)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "a"},
+                                                                              {"Default-Features", ""},
+                                                                              {"Version", "1.3"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "a"},
+                                                                              {"Feature", "one"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+
+            PackageSpecMap spec_map;
+
+            auto spec_a = FullPackageSpec{
+                spec_map.get_package_spec(
+                    {{{"Source", "a"}, {"Version", "1.3"}, {"Build-Depends", "b"}},
+                     {{"Feature", "one"}, {"Description", "the first feature for a"}, {"Build-Depends", ""}}}),
+            };
+            auto spec_b = FullPackageSpec{spec_map.get_package_spec({
+                {{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+            })};
+            auto spec_c = FullPackageSpec{spec_map.get_package_spec({
+                                              {{"Source", "c"}, {"Version", "1.3"}, {"Build-Depends", "a[one]"}},
+                                          }),
+                                          {"core"}};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_c}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(1), install_plan.size());
+            features_check(&install_plan[0], "c", {"core"});
+        }
+
+        TEST_METHOD(basic_feature_test_5)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+
+            PackageSpecMap spec_map;
+
+            auto spec_a = FullPackageSpec{
+                spec_map.get_package_spec(
+                    {{{"Source", "a"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+                     {{"Feature", "1"}, {"Description", "the first feature for a"}, {"Build-Depends", "b[1]"}},
+                     {{"Feature", "2"}, {"Description", "the first feature for a"}, {"Build-Depends", "b[2]"}},
+                     {{"Feature", "3"}, {"Description", "the first feature for a"}, {"Build-Depends", "a[2]"}}}),
+                {"3"}};
+            auto spec_b = FullPackageSpec{spec_map.get_package_spec({
+                {{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+                {{"Feature", "1"}, {"Description", "the first feature for a"}, {"Build-Depends", ""}},
+                {{"Feature", "2"}, {"Description", "the first feature for a"}, {"Build-Depends", ""}},
+            })};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_a}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(2), install_plan.size());
+            features_check(&install_plan[0], "b", {"core", "2"});
+            features_check(&install_plan[1], "a", {"core", "3", "2"});
+        }
+
+        TEST_METHOD(basic_feature_test_6)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "b"},
+                                                                              {"Default-Features", ""},
+                                                                              {"Version", "1.3"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+            PackageSpecMap spec_map;
+
+            auto spec_a = FullPackageSpec{spec_map.get_package_spec({
+                                              {{"Source", "a"}, {"Version", "1.3"}, {"Build-Depends", "b[core]"}},
+                                          }),
+                                          {"core"}};
+            auto spec_b = FullPackageSpec{
+                spec_map.get_package_spec({
+                    {{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+                    {{"Feature", "1"}, {"Description", "the first feature for a"}, {"Build-Depends", ""}},
+                }),
+                {"1"}};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_a, spec_b}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(3), install_plan.size());
+            remove_plan_check(&install_plan[0], "b");
+            features_check(&install_plan[1], "b", {"core", "1"});
+            features_check(&install_plan[2], "a", {"core"});
+        }
+
+        TEST_METHOD(basic_feature_test_7)
+        {
+            using Pgh = std::unordered_map<std::string, std::string>;
+
+            std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "x"},
+                                                                              {"Default-Features", ""},
+                                                                              {"Version", "1.3"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", "b"},
+                                                                              {"Status", "install ok installed"}}));
+            status_paragraphs.push_back(std::make_unique<StatusParagraph>(Pgh{{"Package", "b"},
+                                                                              {"Default-Features", ""},
+                                                                              {"Version", "1.3"},
+                                                                              {"Architecture", "x86-windows"},
+                                                                              {"Multi-Arch", "same"},
+                                                                              {"Depends", ""},
+                                                                              {"Status", "install ok installed"}}));
+            PackageSpecMap spec_map;
+
+            auto spec_a = FullPackageSpec{spec_map.get_package_spec({
+                {{"Source", "a"}, {"Version", "1.3"}, {"Build-Depends", ""}},
+            })};
+            auto spec_x = FullPackageSpec{spec_map.get_package_spec({
+                                              {{"Source", "x"}, {"Version", "1.3"}, {"Build-Depends", "a"}},
+                                          }),
+                                          {"core"}};
+            auto spec_b = FullPackageSpec{
+                spec_map.get_package_spec({
+                    {{"Source", "b"}, {"Version", "1.3"}, {"Build-Depends", ""}, {"Default-Features", ""}},
+                    {{"Feature", "1"}, {"Description", "the first feature for a"}, {"Build-Depends", ""}},
+                }),
+                {"1"}};
+
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {spec_b, spec_x}, StatusParagraphs(std::move(status_paragraphs)));
+
+            Assert::AreEqual(size_t(5), install_plan.size());
+            remove_plan_check(&install_plan[0], "x");
+            remove_plan_check(&install_plan[1], "b");
+
+            // order here may change but A < X, and B anywhere
+            features_check(&install_plan[2], "a", {"core"});
+            features_check(&install_plan[3], "x", {"core"});
+            features_check(&install_plan[4], "b", {"core", "1"});
+        }
     };
 }
\ No newline at end of file
diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
index 984d0ab4c..824de15e1 100644
--- a/toolsrc/src/vcpkg_Dependencies.cpp
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -55,6 +55,20 @@ namespace vcpkg::Dependencies
     }
 
     InstallPlanAction::InstallPlanAction(const PackageSpec& spec,
+                                         const SourceControlFile& any_paragraph,
+                                         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()
@@ -320,4 +334,234 @@ 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 std::unordered_map<std::string, PackageSpec> str_to_spec)
+    {
+        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 = str_to_spec.find(package_name);
+                if (p_spec != str_to_spec.end())
+                {
+                    auto feature_spec = FeatureSpec{p_spec->second, feature_name};
+                    f_specs.emplace_back(std::move(feature_spec));
+                }
+            }
+            else
+            {
+                auto p_spec = str_to_spec.find(depend);
+                if (p_spec != str_to_spec.end())
+                {
+                    auto feature_spec = FeatureSpec{p_spec->second, ""};
+                    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::exit_fail(VCPKG_LINE_INFO);
+        }
+
+        if (cluster.edges[updated_feature].plus) return true;
+
+        if (cluster.original_nodes.find(updated_feature) == cluster.original_nodes.end())
+        {
+            cluster.zero = true;
+        }
+
+        if (!cluster.zero)
+        {
+            return false;
+        }
+        cluster.edges[updated_feature].plus = true;
+
+        if (!cluster.original_nodes.empty())
+        {
+            mark_minus(cluster, pkg_to_cluster, graph_plan);
+        }
+
+        graph_plan.install_graph.add_vertex(&cluster);
+        auto& tracked = cluster.tracked_nodes;
+        tracked.insert(updated_feature);
+        if (tracked.find("core") == tracked.end() && tracked.find("") == tracked.end())
+        {
+            cluster.tracked_nodes.insert("core");
+            for (auto&& depend : cluster.edges["core"].dashed)
+            {
+                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].dashed)
+        {
+            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.minus) return;
+        cluster.minus = true;
+
+        graph_plan.remove_graph.add_vertex(&cluster);
+        for (auto&& pair : cluster.edges)
+        {
+            auto& dotted_edges = pair.second.dotted;
+            for (auto&& depend : dotted_edges)
+            {
+                auto& depend_cluster = pkg_to_cluster[depend.spec];
+                graph_plan.remove_graph.add_edge(&cluster, &depend_cluster);
+                depend_cluster.zero = true;
+                mark_minus(depend_cluster, pkg_to_cluster, graph_plan);
+            }
+        }
+        for (auto&& original_feature : cluster.original_nodes)
+        {
+            cluster.zero = 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)
+    {
+        const auto triplet = Triplet::X86_WINDOWS;
+        std::unordered_map<PackageSpec, Cluster> pkg_spec_to_package_node;
+        std::unordered_map<std::string, PackageSpec> str_to_spec;
+
+        for (const auto& it : map)
+        {
+            str_to_spec.emplace(it.first.name(), it.first);
+        }
+
+        for (const auto& it : map)
+        {
+            Cluster& node = pkg_spec_to_package_node[it.first];
+            FeatureNodeEdges core_dependencies;
+            core_dependencies.dashed =
+                to_feature_specs(filter_dependencies(it.second.core_paragraph->depends, triplet), str_to_spec);
+            node.edges["core"] = std::move(core_dependencies);
+
+            for (const auto& feature : it.second.feature_paragraphs)
+            {
+                FeatureNodeEdges added_edges;
+                added_edges.dashed = to_feature_specs(filter_dependencies(feature->depends, triplet), str_to_spec);
+                node.edges.emplace(feature->name, std::move(added_edges));
+            }
+            node.cluster_node.source_paragraph = &it.second;
+        }
+
+        for (auto&& status_paragraph : 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.zero = false;
+            auto reverse_edges = to_feature_specs(status_paragraph->package.depends, str_to_spec);
+
+            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.dotted.emplace_back(FeatureSpec{spec, status_paragraph_feature});
+                    }
+                    depends_name = "core";
+                }
+                auto& target_node = pkg_node->second.edges[depends_name];
+                target_node.dotted.emplace_back(FeatureSpec{spec, status_paragraph_feature});
+            }
+            cluster.cluster_node.status_paragraphs.emplace_back(*status_paragraph);
+            if (status_paragraph_feature == "")
+            {
+                cluster.original_nodes.insert("core");
+            }
+            else
+            {
+                cluster.original_nodes.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<Cluster*> 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<Cluster*> 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&& cluster : remove_toposort)
+        {
+            auto scf = *cluster->cluster_node.source_paragraph.get();
+
+            AnyAction any_plan;
+            any_plan.remove_plan = RemovePlanAction{
+                str_to_spec[scf->core_paragraph->name], RemovePlanType::REMOVE, RequestType::AUTO_SELECTED};
+
+            install_plan.emplace_back(std::move(any_plan));
+        }
+
+        for (auto&& cluster : insert_toposort)
+        {
+            if (!cluster->zero) continue;
+
+            auto scf = *cluster->cluster_node.source_paragraph.get();
+            auto& pkg_spec = str_to_spec[scf->core_paragraph->name];
+            auto action = InstallPlanAction{
+                pkg_spec, map.find(pkg_spec)->second, cluster->tracked_nodes, RequestType::AUTO_SELECTED};
+
+            AnyAction any_plan;
+            any_plan.install_plan = std::move(action);
+            install_plan.emplace_back(std::move(any_plan));
+        }
+
+        return install_plan;
+    }
 }