[vcpkg] Rework dependencies.cpp to improve type safety and error detection

7 files changed, 355 insertions, 282 deletions

diff --git a/toolsrc/src/tests.plan.cpp b/toolsrc/src/tests.plan.cpp
index a99f1abb9..b054702a1 100644
--- a/toolsrc/src/tests.plan.cpp
+++ b/toolsrc/src/tests.plan.cpp
@@ -81,7 +81,7 @@ namespace UnitTest1
     {
         std::unordered_map<std::string, SourceControlFile> map;
         Triplet triplet;
-        PackageSpecMap(const Triplet& t) { triplet = t; }
+        PackageSpecMap(const Triplet& t = Triplet::X86_WINDOWS) { triplet = t; }
 
         PackageSpec emplace(const char* name,
                             const char* depends = "",
@@ -105,7 +105,7 @@ namespace UnitTest1
         {
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "b");
             auto spec_b = spec_map.emplace("b", "c");
             auto spec_c = spec_map.emplace("c");
@@ -124,7 +124,7 @@ namespace UnitTest1
         {
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "d");
             auto spec_b = spec_map.emplace("b", "d, e");
             auto spec_c = spec_map.emplace("c", "e, h");
@@ -167,7 +167,7 @@ namespace UnitTest1
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
             status_paragraphs.push_back(make_status_pgh("a"));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = FullPackageSpec{spec_map.emplace("a")};
 
             auto install_plan =
@@ -187,7 +187,7 @@ namespace UnitTest1
         {
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = FullPackageSpec{spec_map.emplace("a", "b")};
             auto spec_b = FullPackageSpec{spec_map.emplace("b")};
 
@@ -216,7 +216,7 @@ namespace UnitTest1
             status_paragraphs.push_back(make_status_pgh("j", "k"));
             status_paragraphs.push_back(make_status_pgh("k"));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
 
             auto spec_a = spec_map.emplace("a", "b, c, d, e, f, g, h, j, k");
             auto spec_b = spec_map.emplace("b", "c, d, e, f, g, h, j, k");
@@ -251,7 +251,7 @@ namespace UnitTest1
             status_paragraphs.push_back(make_status_pgh("b"));
             status_paragraphs.push_back(make_status_feature_pgh("b", "b1"));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = FullPackageSpec{spec_map.emplace("a", "b, b[b1]", {{"a1", "b[b2]"}}), {"a1"}};
             auto spec_b = FullPackageSpec{spec_map.emplace("b", "", {{"b1", ""}, {"b2", ""}, {"b3", ""}})};
 
@@ -271,7 +271,7 @@ namespace UnitTest1
         {
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
 
             auto spec_a = FullPackageSpec{spec_map.emplace("a", "b[b1]", {{"a1", "b[b2]"}}), {"a1"}};
             auto spec_b = FullPackageSpec{spec_map.emplace("b", "", {{"b1", ""}, {"b2", ""}, {"b3", ""}})};
@@ -291,7 +291,7 @@ namespace UnitTest1
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
             status_paragraphs.push_back(make_status_pgh("a"));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
 
             auto spec_a = FullPackageSpec{spec_map.emplace("a", "b", {{"a1", ""}}), {"core"}};
             auto spec_b = FullPackageSpec{spec_map.emplace("b")};
@@ -315,7 +315,7 @@ namespace UnitTest1
             status_paragraphs.push_back(make_status_pgh("a"));
             status_paragraphs.push_back(make_status_feature_pgh("a", "a1", ""));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
 
             auto spec_a = FullPackageSpec{spec_map.emplace("a", "b", {{"a1", ""}})};
             auto spec_b = FullPackageSpec{spec_map.emplace("b")};
@@ -334,7 +334,7 @@ namespace UnitTest1
         {
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
 
             auto spec_a =
                 FullPackageSpec{spec_map.emplace("a", "", {{"a1", "b[b1]"}, {"a2", "b[b2]"}, {"a3", "a[a2]"}}), {"a3"}};
@@ -355,7 +355,7 @@ namespace UnitTest1
             std::vector<std::unique_ptr<StatusParagraph>> status_paragraphs;
             status_paragraphs.push_back(make_status_pgh("b"));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = FullPackageSpec{spec_map.emplace("a", "b[core]"), {"core"}};
             auto spec_b = FullPackageSpec{spec_map.emplace("b", "", {{"b1", ""}}), {"b1"}};
 
@@ -376,7 +376,7 @@ namespace UnitTest1
             status_paragraphs.push_back(make_status_pgh("x", "b"));
             status_paragraphs.push_back(make_status_pgh("b"));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
 
             auto spec_a = FullPackageSpec{spec_map.emplace("a")};
             auto spec_x = FullPackageSpec{spec_map.emplace("x", "a"), {"core"}};
@@ -674,17 +674,35 @@ namespace UnitTest1
             Assert::IsTrue(install_plan[0].install_action.get()->computed_dependencies == std::vector<PackageSpec>{});
         }
 
+        TEST_METHOD(install_with_default_features)
+        {
+            std::vector<std::unique_ptr<StatusParagraph>> pghs;
+            pghs.push_back(make_status_pgh("a", ""));
+            StatusParagraphs status_db(std::move(pghs));
+
+            PackageSpecMap spec_map;
+            auto b_spec = spec_map.emplace("b", "", {{"0", ""}}, {"0"});
+            auto a_spec = spec_map.emplace("a", "b[core]", {{"0", ""}});
+
+            // Install "a" and indicate that "b" should not install default features
+            auto install_plan = Dependencies::create_feature_install_plan(
+                spec_map.map, {FeatureSpec{a_spec, "0"}, FeatureSpec{b_spec, "core"}}, status_db);
+
+            Assert::IsTrue(install_plan.size() == 3);
+            remove_plan_check(&install_plan[0], "a");
+            features_check(&install_plan[1], "b", {"core"});
+            features_check(&install_plan[2], "a", {"0", "core"});
+        }
+
         TEST_METHOD(upgrade_with_default_features_1)
         {
             std::vector<std::unique_ptr<StatusParagraph>> pghs;
             pghs.push_back(make_status_pgh("a", "", "1"));
             pghs.push_back(make_status_feature_pgh("a", "0"));
-            pghs.back()->package.spec =
-                PackageSpec::from_name_and_triplet("a", Triplet::X86_WINDOWS).value_or_exit(VCPKG_LINE_INFO);
             StatusParagraphs status_db(std::move(pghs));
 
             // Add a port "a" of which "core" and "0" are already installed.
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "", {{"0", ""}, {"1", ""}}, {"1"});
 
             Dependencies::MapPortFileProvider provider(spec_map.map);
@@ -697,23 +715,47 @@ namespace UnitTest1
             Assert::AreEqual(size_t(2), plan.size());
 
             Assert::AreEqual("a", plan[0].spec().name().c_str());
-            Assert::IsTrue(plan[0].remove_action.has_value());
-
-            Assert::AreEqual("a", plan[1].spec().name().c_str());
-            features_check(&plan[1], "a", {"core", "0"}, Triplet::X86_WINDOWS);
+            remove_plan_check(&plan[0], "a");
+            features_check(&plan[1], "a", {"core", "0"});
         }
 
         TEST_METHOD(upgrade_with_default_features_2)
         {
             std::vector<std::unique_ptr<StatusParagraph>> pghs;
-            pghs.push_back(make_status_pgh("b"));
-            pghs.push_back(make_status_pgh("a", "b[core]"));
-            pghs.back()->package.spec =
-                PackageSpec::from_name_and_triplet("a", Triplet::X64_WINDOWS).value_or_exit(VCPKG_LINE_INFO);
+            // B is currently installed _without_ default feature b0
+            pghs.push_back(make_status_pgh("b", "", "b0", "x64-windows"));
+            pghs.push_back(make_status_pgh("a", "b[core]", "", "x64-windows"));
+
+            StatusParagraphs status_db(std::move(pghs));
+
+            PackageSpecMap spec_map(Triplet::X64_WINDOWS);
+            auto spec_a = spec_map.emplace("a", "b[core]");
+            auto spec_b = spec_map.emplace("b", "", {{"b0", ""}, {"b1", ""}}, {"b0", "b1"});
+
+            Dependencies::MapPortFileProvider provider(spec_map.map);
+            Dependencies::PackageGraph graph(provider, status_db);
+
+            graph.upgrade(spec_a);
+            graph.upgrade(spec_b);
+            auto plan = graph.serialize();
+
+            // The upgrade should install the new default feature b1 but not b0
+            Assert::AreEqual(size_t(4), plan.size());
+            remove_plan_check(&plan[0], "a", Triplet::X64_WINDOWS);
+            remove_plan_check(&plan[1], "b", Triplet::X64_WINDOWS);
+            features_check(&plan[2], "b", {"core", "b1"}, Triplet::X64_WINDOWS);
+            features_check(&plan[3], "a", {"core"}, Triplet::X64_WINDOWS);
+        }
+
+        TEST_METHOD(upgrade_with_default_features_3)
+        {
+            std::vector<std::unique_ptr<StatusParagraph>> pghs;
+            // note: unrelated package due to x86 triplet
+            pghs.push_back(make_status_pgh("b", "", "", "x86-windows"));
+            pghs.push_back(make_status_pgh("a", "", "", "x64-windows"));
 
             StatusParagraphs status_db(std::move(pghs));
 
-            // Add a port "a" of which "core" and "0" are already installed.
             PackageSpecMap spec_map(Triplet::X64_WINDOWS);
             auto spec_a = spec_map.emplace("a", "b[core]");
             spec_map.emplace("b", "", {{"b0", ""}, {"b1", ""}}, {"b0"});
@@ -724,17 +766,33 @@ namespace UnitTest1
             graph.upgrade(spec_a);
             auto plan = graph.serialize();
 
-            // The upgrade should not install the default feature
+            // The upgrade should install the default feature
             Assert::AreEqual(size_t(3), plan.size());
+            remove_plan_check(&plan[0], "a", Triplet::X64_WINDOWS);
+            features_check(&plan[1], "b", {"b0", "core"}, Triplet::X64_WINDOWS);
+            features_check(&plan[2], "a", {"core"}, Triplet::X64_WINDOWS);
+        }
 
-            Assert::AreEqual("a", plan[0].spec().name().c_str());
-            Assert::IsTrue(plan[0].remove_action.has_value());
+        TEST_METHOD(upgrade_with_new_default_feature)
+        {
+            std::vector<std::unique_ptr<StatusParagraph>> pghs;
+            pghs.push_back(make_status_pgh("a", "", "0", "x86-windows"));
 
-            Assert::AreEqual("b", plan[1].spec().name().c_str());
-            features_check(&plan[1], "b", {"b0", "core"}, Triplet::X64_WINDOWS);
+            StatusParagraphs status_db(std::move(pghs));
 
-            Assert::AreEqual("a", plan[2].spec().name().c_str());
-            features_check(&plan[2], "a", {"core"}, Triplet::X64_WINDOWS);
+            PackageSpecMap spec_map;
+            auto spec_a = spec_map.emplace("a", "", {{"0", ""}, {"1", ""}, {"2", ""}}, {"0", "1"});
+
+            Dependencies::MapPortFileProvider provider(spec_map.map);
+            Dependencies::PackageGraph graph(provider, status_db);
+
+            graph.upgrade(spec_a);
+            auto plan = graph.serialize();
+
+            // The upgrade should install the new default feature but not the old default feature 0
+            Assert::AreEqual(size_t(2), plan.size());
+            remove_plan_check(&plan[0], "a", Triplet::X86_WINDOWS);
+            features_check(&plan[1], "a", {"core", "1"}, Triplet::X86_WINDOWS);
         }
 
         TEST_METHOD(transitive_features_test)
@@ -924,7 +982,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("a"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
 
             Dependencies::MapPortFileProvider provider(spec_map.map);
@@ -948,7 +1006,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("b", "a"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
             spec_map.emplace("b", "a");
 
@@ -980,7 +1038,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("b"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
             spec_map.emplace("b", "a");
 
@@ -1004,7 +1062,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("a"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "b");
             spec_map.emplace("b");
 
@@ -1031,7 +1089,7 @@ namespace UnitTest1
             pghs.push_back(make_status_feature_pgh("a", "a1"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "", {{"a1", ""}});
 
             Dependencies::MapPortFileProvider provider(spec_map.map);
@@ -1057,7 +1115,7 @@ namespace UnitTest1
             StatusParagraphs status_db(std::move(pghs));
 
             // a1 was added as a default feature and should be installed in upgrade
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "", {{"a1", ""}}, {"a1"});
 
             Dependencies::MapPortFileProvider provider(spec_map.map);
@@ -1083,7 +1141,7 @@ namespace UnitTest1
             pghs.push_back(make_status_feature_pgh("a", "a2", "a[a1]"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "", {{"a1", ""}, {"a2", "a[a1]"}});
 
             Dependencies::MapPortFileProvider provider(spec_map.map);
@@ -1112,7 +1170,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("a"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
 
             auto plan = Dependencies::create_export_plan({spec_a}, status_db);
@@ -1129,7 +1187,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("b", "a"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
             auto spec_b = spec_map.emplace("b", "a");
 
@@ -1150,7 +1208,7 @@ namespace UnitTest1
             pghs.push_back(make_status_pgh("b"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
             auto spec_b = spec_map.emplace("b", "a");
 
@@ -1165,7 +1223,7 @@ namespace UnitTest1
         {
             StatusParagraphs status_db;
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a");
 
             auto plan = Dependencies::create_export_plan({spec_a}, status_db);
@@ -1183,7 +1241,7 @@ namespace UnitTest1
             pghs.push_back(make_status_feature_pgh("a", "a1", "b[core]"));
             StatusParagraphs status_db(std::move(pghs));
 
-            PackageSpecMap spec_map(Triplet::X86_WINDOWS);
+            PackageSpecMap spec_map;
             auto spec_a = spec_map.emplace("a", "", {{"a1", ""}});
 
             auto plan = Dependencies::create_export_plan({spec_a}, status_db);
diff --git a/toolsrc/src/vcpkg/commands.list.cpp b/toolsrc/src/vcpkg/commands.list.cpp
index 4c4518d25..1bfbc4247 100644
--- a/toolsrc/src/vcpkg/commands.list.cpp
+++ b/toolsrc/src/vcpkg/commands.list.cpp
@@ -44,14 +44,19 @@ namespace vcpkg::Commands::List
         const ParsedArguments options = args.parse_arguments(COMMAND_STRUCTURE);
 
         const StatusParagraphs status_paragraphs = database_load_check(paths);
-        std::vector<StatusParagraph*> installed_packages = get_installed_ports(status_paragraphs);
+        auto installed_ipv = get_installed_ports(status_paragraphs);
 
-        if (installed_packages.empty())
+        if (installed_ipv.empty())
         {
             System::println("No packages are installed. Did you mean `search`?");
             Checks::exit_success(VCPKG_LINE_INFO);
         }
 
+        auto installed_packages = Util::fmap(installed_ipv, [](const InstalledPackageView& ipv) { return ipv.core; });
+        auto installed_features =
+            Util::fmap_flatten(installed_ipv, [](const InstalledPackageView& ipv) { return ipv.features; });
+        installed_packages.insert(installed_packages.end(), installed_features.begin(), installed_features.end());
+
         std::sort(installed_packages.begin(),
                   installed_packages.end(),
                   [](const StatusParagraph* lhs, const StatusParagraph* rhs) -> bool {
diff --git a/toolsrc/src/vcpkg/dependencies.cpp b/toolsrc/src/vcpkg/dependencies.cpp
index f6d81c973..a8bc901a0 100644
--- a/toolsrc/src/vcpkg/dependencies.cpp
+++ b/toolsrc/src/vcpkg/dependencies.cpp
@@ -13,11 +13,17 @@
 
 namespace vcpkg::Dependencies
 {
-    struct FeatureNodeEdges
+    struct ClusterInstalled
     {
-        std::vector<FeatureSpec> remove_edges;
-        std::vector<FeatureSpec> build_edges;
-        bool plus = false;
+        InstalledPackageView ipv;
+        std::set<PackageSpec> remove_edges;
+        std::set<std::string> original_features;
+    };
+
+    struct ClusterSource
+    {
+        const SourceControlFile* scf;
+        std::unordered_map<std::string, std::vector<FeatureSpec>> build_edges;
     };
 
     /// <summary>
@@ -25,14 +31,15 @@ namespace vcpkg::Dependencies
     /// </summary>
     struct Cluster : Util::MoveOnlyBase
     {
-        InstalledPackageView installed_package;
-
-        Optional<const SourceControlFile*> source_control_file;
         PackageSpec spec;
-        std::unordered_map<std::string, FeatureNodeEdges> edges_by_feature;
+
+        Optional<ClusterInstalled> installed;
+        Optional<ClusterSource> source;
+
+        // Note: this map can contain "special" strings such as "" and "*"
+        std::unordered_map<std::string, bool> plus;
         std::set<std::string> to_install_features;
-        std::set<std::string> original_features;
-        bool will_remove = false;
+        bool minus = false;
         bool transient_uninstalled = true;
         RequestType request_type = RequestType::AUTO_SELECTED;
     };
@@ -88,27 +95,26 @@ namespace vcpkg::Dependencies
                 auto maybe_scf = m_provider.get_control_file(spec.name());
                 auto& clust = m_graph[spec];
                 clust.spec = spec;
-                if (auto p_scf = maybe_scf.get()) cluster_from_scf(*p_scf, clust);
+                if (auto p_scf = maybe_scf.get())
+                {
+                    clust.source = cluster_from_scf(*p_scf, clust.spec.triplet());
+                }
                 return clust;
             }
             return it->second;
         }
 
     private:
-        void cluster_from_scf(const SourceControlFile& scf, Cluster& out_cluster) const
+        static ClusterSource cluster_from_scf(const SourceControlFile& scf, Triplet t)
         {
-            FeatureNodeEdges core_dependencies;
-            core_dependencies.build_edges =
-                filter_dependencies_to_specs(scf.core_paragraph->depends, out_cluster.spec.triplet());
-            out_cluster.edges_by_feature.emplace("core", std::move(core_dependencies));
+            ClusterSource ret;
+            ret.build_edges.emplace("core", filter_dependencies_to_specs(scf.core_paragraph->depends, t));
 
             for (const auto& feature : scf.feature_paragraphs)
-            {
-                FeatureNodeEdges added_edges;
-                added_edges.build_edges = filter_dependencies_to_specs(feature->depends, out_cluster.spec.triplet());
-                out_cluster.edges_by_feature.emplace(feature->name, std::move(added_edges));
-            }
-            out_cluster.source_control_file = &scf;
+                ret.build_edges.emplace(feature->name, filter_dependencies_to_specs(feature->depends, t));
+
+            ret.scf = &scf;
+            return ret;
         }
 
         std::unordered_map<PackageSpec, Cluster> m_graph;
@@ -155,11 +161,10 @@ namespace vcpkg::Dependencies
     {
     }
 
-    InstallPlanAction::InstallPlanAction(const PackageSpec& spec,
-                                         InstalledPackageView&& ipv,
+    InstallPlanAction::InstallPlanAction(InstalledPackageView&& ipv,
                                          const std::set<std::string>& features,
                                          const RequestType& request_type)
-        : spec(spec)
+        : spec(ipv.spec())
         , installed_package(std::move(ipv))
         , plan_type(InstallPlanType::ALREADY_INSTALLED)
         , request_type(request_type)
@@ -289,11 +294,11 @@ namespace vcpkg::Dependencies
         struct RemoveAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, RemovePlanAction>
         {
             const StatusParagraphs& status_db;
-            const std::vector<StatusParagraph*>& installed_ports;
+            const std::vector<InstalledPackageView>& installed_ports;
             const std::unordered_set<PackageSpec>& specs_as_set;
 
             RemoveAdjacencyProvider(const StatusParagraphs& status_db,
-                                    const std::vector<StatusParagraph*>& installed_ports,
+                                    const std::vector<InstalledPackageView>& installed_ports,
                                     const std::unordered_set<PackageSpec>& specs_as_set)
                 : status_db(status_db), installed_ports(installed_ports), specs_as_set(specs_as_set)
             {
@@ -308,24 +313,13 @@ namespace vcpkg::Dependencies
 
                 const PackageSpec& spec = plan.spec;
                 std::vector<PackageSpec> dependents;
-                for (const StatusParagraph* an_installed_package : installed_ports)
+                for (auto&& ipv : installed_ports)
                 {
-                    if (an_installed_package->package.spec.triplet() != spec.triplet()) continue;
+                    auto deps = ipv.dependencies();
 
-                    std::vector<std::string> deps = an_installed_package->package.depends;
-                    // <hack>
-                    // This is a hack to work around existing installations that put featurespecs into binary packages
-                    // (example: curl[core]) Eventually, this can be returned to a simple string search.
-                    for (auto&& dep : deps)
-                    {
-                        dep.erase(std::find(dep.begin(), dep.end(), '['), dep.end());
-                    }
-                    Util::unstable_keep_if(deps,
-                                           [&](auto&& e) { return e != an_installed_package->package.spec.name(); });
-                    // </hack>
-                    if (std::find(deps.begin(), deps.end(), spec.name()) == deps.end()) continue;
+                    if (std::find(deps.begin(), deps.end(), spec) == deps.end()) continue;
 
-                    dependents.push_back(an_installed_package->package.spec);
+                    dependents.push_back(ipv.spec());
                 }
 
                 return dependents;
@@ -347,7 +341,7 @@ namespace vcpkg::Dependencies
             std::string to_string(const PackageSpec& spec) const override { return spec.to_string(); }
         };
 
-        const std::vector<StatusParagraph*>& installed_ports = get_installed_ports(status_db);
+        auto 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});
     }
@@ -405,161 +399,201 @@ namespace vcpkg::Dependencies
                                     Cluster& cluster,
                                     ClusterGraph& graph,
                                     GraphPlan& graph_plan,
-                                    const std::unordered_set<std::string>& prevent_default_features = {});
+                                    const std::unordered_set<std::string>& prevent_default_features);
 
-    static void mark_minus(Cluster& cluster, ClusterGraph& graph, GraphPlan& graph_plan);
+    static void mark_minus(Cluster& cluster,
+                           ClusterGraph& graph,
+                           GraphPlan& graph_plan,
+                           const std::unordered_set<std::string>& prevent_default_features);
 
-    MarkPlusResult mark_plus(const std::string& feature,
-                             Cluster& cluster,
-                             ClusterGraph& graph,
-                             GraphPlan& graph_plan,
-                             const std::unordered_set<std::string>& prevent_default_features)
+    static MarkPlusResult follow_plus_dependencies(const std::string& feature,
+                                                   Cluster& cluster,
+                                                   ClusterGraph& graph,
+                                                   GraphPlan& graph_plan,
+                                                   const std::unordered_set<std::string>& prevent_default_features)
     {
-        if (feature.empty())
+        if (auto p_source = cluster.source.get())
         {
-            if (prevent_default_features.find(cluster.spec.name()) == prevent_default_features.end())
+            auto it_build_edges = p_source->build_edges.find(feature);
+            if (it_build_edges != p_source->build_edges.end())
             {
-                // Indicates that core was not specified in the reference
+                // mark this package for rebuilding if needed
+                mark_minus(cluster, graph, graph_plan, prevent_default_features);
+
+                graph_plan.install_graph.add_vertex({&cluster});
+                cluster.to_install_features.insert(feature);
 
-                // Add default features for this package, if this is the "core" feature and we
-                // are not supposed to prevent default features for this package
-                if (auto scf = cluster.source_control_file.value_or(nullptr))
+                if (feature != "core")
                 {
-                    for (auto&& default_feature : scf->core_paragraph.get()->default_features)
-                    {
-                        auto res = mark_plus(default_feature, cluster, graph, graph_plan, prevent_default_features);
-                        if (res != MarkPlusResult::SUCCESS)
-                        {
-                            return res;
-                        }
-                    }
+                    // All features implicitly depend on core
+                    auto res = mark_plus("core", cluster, graph, graph_plan, prevent_default_features);
+
+                    // Should be impossible for "core" to not exist
+                    Checks::check_exit(VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS);
                 }
 
-                // "core" is always an implicit default feature. In case we did not add it as
-                // a dependency above (e.g. no default features), add it here.
-                auto res = mark_plus("core", cluster, graph, graph_plan, prevent_default_features);
-                if (res != MarkPlusResult::SUCCESS)
+                if (!cluster.installed.get() && !Util::Sets::contains(prevent_default_features, cluster.spec.name()))
                 {
-                    return res;
+                    // Add the default features of this package if it was not previously installed and it isn't being
+                    // suppressed.
+                    auto res = mark_plus("", cluster, graph, graph_plan, prevent_default_features);
+
+                    Checks::check_exit(VCPKG_LINE_INFO,
+                                       res == MarkPlusResult::SUCCESS,
+                                       "Error: Unable to satisfy default dependencies of %s",
+                                       cluster.spec);
+                }
+
+                for (auto&& depend : it_build_edges->second)
+                {
+                    auto& depend_cluster = graph.get(depend.spec());
+                    auto res = mark_plus(depend.feature(), depend_cluster, graph, graph_plan, prevent_default_features);
+
+                    Checks::check_exit(VCPKG_LINE_INFO,
+                                       res == MarkPlusResult::SUCCESS,
+                                       "Error: Unable to satisfy dependency %s of %s",
+                                       depend,
+                                       FeatureSpec(cluster.spec, feature));
+
+                    if (&depend_cluster == &cluster) continue;
+                    graph_plan.install_graph.add_edge({&cluster}, {&depend_cluster});
                 }
 
-                return MarkPlusResult::SUCCESS;
-            }
-            else
-            {
-                // Skip adding the default features, as explicitly told not to.
                 return MarkPlusResult::SUCCESS;
             }
         }
 
-        auto it = cluster.edges_by_feature.find(feature);
-        if (it == cluster.edges_by_feature.end()) return MarkPlusResult::FEATURE_NOT_FOUND;
+        // The feature was not available in the installed package nor the source paragraph.
+        return MarkPlusResult::FEATURE_NOT_FOUND;
+    }
 
-        if (cluster.edges_by_feature[feature].plus) return MarkPlusResult::SUCCESS;
+    MarkPlusResult mark_plus(const std::string& feature,
+                             Cluster& cluster,
+                             ClusterGraph& graph,
+                             GraphPlan& graph_plan,
+                             const std::unordered_set<std::string>& prevent_default_features)
+    {
+        auto& plus = cluster.plus[feature];
+        if (plus) return MarkPlusResult::SUCCESS;
+        plus = true;
 
-        if (cluster.original_features.find(feature) == cluster.original_features.end())
+        if (feature.empty())
         {
-            cluster.transient_uninstalled = true;
-        }
+            // Add default features for this package. This is an exact reference, so ignore prevent_default_features.
+            if (auto p_source = cluster.source.get())
+            {
+                for (auto&& default_feature : p_source->scf->core_paragraph.get()->default_features)
+                {
+                    auto res = mark_plus(default_feature, cluster, graph, graph_plan, prevent_default_features);
+                    if (res != MarkPlusResult::SUCCESS)
+                    {
+                        return res;
+                    }
+                }
+            }
+            else
+            {
+                Checks::exit_with_message(VCPKG_LINE_INFO,
+                                          "Error: Unable to install default features because can't find CONTROL for %s",
+                                          cluster.spec);
+            }
 
-        if (!cluster.transient_uninstalled)
-        {
-            return MarkPlusResult::SUCCESS;
+            // "core" is always required.
+            return mark_plus("core", cluster, graph, graph_plan, prevent_default_features);
         }
-        cluster.edges_by_feature[feature].plus = true;
 
-        if (!cluster.original_features.empty())
+        if (feature == "*")
         {
-            mark_minus(cluster, graph, graph_plan);
-        }
+            if (auto p_source = cluster.source.get())
+            {
+                for (auto&& feature : p_source->scf->feature_paragraphs)
+                {
+                    auto res = mark_plus(feature->name, cluster, graph, graph_plan, prevent_default_features);
 
-        graph_plan.install_graph.add_vertex({&cluster});
-        auto& tracked = cluster.to_install_features;
-        tracked.insert(feature);
+                    Checks::check_exit(VCPKG_LINE_INFO,
+                                       res == MarkPlusResult::SUCCESS,
+                                       "Error: Unable to locate feature %s in %s",
+                                       feature->name,
+                                       cluster.spec);
+                }
 
-        if (feature != "core")
-        {
-            // All features implicitly depend on core
-            auto res = mark_plus("core", cluster, graph, graph_plan, prevent_default_features);
+                auto res = mark_plus("core", cluster, graph, graph_plan, prevent_default_features);
 
-            // Should be impossible for "core" to not exist
-            Checks::check_exit(VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS);
-        }
-        else
-        {
-            // Add the default features of this package.
-            auto res = mark_plus("", cluster, graph, graph_plan, prevent_default_features);
+                Checks::check_exit(VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS);
+            }
+            else
+            {
+                Checks::exit_with_message(
+                    VCPKG_LINE_INFO, "Error: Unable to handle '*' because can't find CONTROL for %s", cluster.spec);
+            }
+            return MarkPlusResult::SUCCESS;
         }
 
-        for (auto&& depend : cluster.edges_by_feature[feature].build_edges)
+        if (auto p_installed = cluster.installed.get())
         {
-            auto& depend_cluster = graph.get(depend.spec());
-            auto res = mark_plus(depend.feature(), depend_cluster, graph, graph_plan, prevent_default_features);
-
-            Checks::check_exit(VCPKG_LINE_INFO,
-                               res == MarkPlusResult::SUCCESS,
-                               "Error: Unable to satisfy dependency %s of %s",
-                               depend,
-                               FeatureSpec(cluster.spec, feature));
-
-            if (&depend_cluster == &cluster) continue;
-            graph_plan.install_graph.add_edge({&cluster}, {&depend_cluster});
+            if (p_installed->original_features.find(feature) != p_installed->original_features.end())
+            {
+                return MarkPlusResult::SUCCESS;
+            }
         }
 
-        return MarkPlusResult::SUCCESS;
+        // This feature was or will be uninstalled, therefore we need to rebuild
+        mark_minus(cluster, graph, graph_plan, prevent_default_features);
+
+        return follow_plus_dependencies(feature, cluster, graph, graph_plan, prevent_default_features);
     }
 
-    void mark_minus(Cluster& cluster, ClusterGraph& graph, GraphPlan& graph_plan)
+    void mark_minus(Cluster& cluster,
+                    ClusterGraph& graph,
+                    GraphPlan& graph_plan,
+                    const std::unordered_set<std::string>& prevent_default_features)
     {
-        if (cluster.will_remove) return;
-        cluster.will_remove = true;
-
-        std::unordered_set<std::string> prevent_default_features;
+        if (cluster.minus) return;
+        cluster.minus = true;
+        cluster.transient_uninstalled = true;
 
-        if (cluster.request_type == RequestType::USER_REQUESTED)
-        {
-            // Do not install default features for packages which the user
-            // installed explicitly. New default features for dependent
-            // clusters should still be upgraded.
-            prevent_default_features.insert(cluster.spec.name());
+        auto p_installed = cluster.installed.get();
+        auto p_source = cluster.source.get();
 
-            // For dependent packages this is handles through the recursion
-        }
+        Checks::check_exit(
+            VCPKG_LINE_INFO,
+            p_source,
+            "Error: cannot locate new portfile for %s. Please explicitly remove this package with `vcpkg remove %s`.",
+            cluster.spec,
+            cluster.spec);
 
-        graph_plan.remove_graph.add_vertex({&cluster});
-        for (auto&& pair : cluster.edges_by_feature)
+        if (p_installed)
         {
-            auto& remove_edges_edges = pair.second.remove_edges;
-            for (auto&& depend : remove_edges_edges)
+            graph_plan.remove_graph.add_vertex({&cluster});
+            for (auto&& edge : p_installed->remove_edges)
             {
-                auto& depend_cluster = graph.get(depend.spec());
-                if (&depend_cluster != &cluster) graph_plan.remove_graph.add_edge({&cluster}, {&depend_cluster});
-                mark_minus(depend_cluster, graph, graph_plan);
+                auto& depend_cluster = graph.get(edge);
+                Checks::check_exit(VCPKG_LINE_INFO, &cluster != &depend_cluster);
+                graph_plan.remove_graph.add_edge({&cluster}, {&depend_cluster});
+                mark_minus(depend_cluster, graph, graph_plan, prevent_default_features);
             }
-        }
 
-        cluster.transient_uninstalled = true;
-        for (auto&& original_feature : cluster.original_features)
-        {
-            auto res = mark_plus(original_feature, cluster, graph, graph_plan, prevent_default_features);
-            if (res != MarkPlusResult::SUCCESS)
+            // Reinstall all original features. Don't use mark_plus because it will ignore them since they are
+            // "already installed".
+            for (auto&& f : p_installed->original_features)
             {
-                System::println(System::Color::warning,
-                                "Warning: could not reinstall feature %s",
-                                FeatureSpec{cluster.spec, original_feature});
+                auto res = follow_plus_dependencies(f, cluster, graph, graph_plan, prevent_default_features);
+                if (res != MarkPlusResult::SUCCESS)
+                {
+                    System::println(System::Color::warning,
+                                    "Warning: could not reinstall feature %s",
+                                    FeatureSpec{cluster.spec, f});
+                }
             }
-        }
 
-        // Check if any default features have been added
-        if (auto scf = cluster.source_control_file.value_or(nullptr))
-        {
-            auto& previous_df = cluster.installed_package.core->package.default_features;
-            for (auto&& default_feature : scf->core_paragraph->default_features)
+            // Check if any default features have been added
+            auto& previous_df = p_installed->ipv.core->package.default_features;
+            for (auto&& default_feature : p_source->scf->core_paragraph->default_features)
             {
                 if (std::find(previous_df.begin(), previous_df.end(), default_feature) == previous_df.end())
                 {
-                    // this is a new default feature, mark it for installation
-                    auto res = mark_plus(default_feature, cluster, graph, graph_plan);
+                    // This is a new default feature, mark it for installation
+                    auto res = mark_plus(default_feature, cluster, graph, graph_plan, prevent_default_features);
                     if (res != MarkPlusResult::SUCCESS)
                     {
                         System::println(System::Color::warning,
@@ -588,7 +622,11 @@ namespace vcpkg::Dependencies
 
         PackageGraph pgraph(provider, status_db);
         for (auto&& spec : specs)
+        {
+            // If preventing default features, ignore the automatically generated "" references
+            if (spec.feature().empty() && Util::Sets::contains(prevent_default_features, spec.name())) continue;
             pgraph.install(spec, prevent_default_features);
+        }
 
         return pgraph.serialize();
     }
@@ -614,37 +652,10 @@ namespace vcpkg::Dependencies
     {
         Cluster& spec_cluster = m_graph->get(spec.spec());
         spec_cluster.request_type = RequestType::USER_REQUESTED;
-        if (spec.feature() == "*")
-        {
-            if (auto p_scf = spec_cluster.source_control_file.value_or(nullptr))
-            {
-                for (auto&& feature : p_scf->feature_paragraphs)
-                {
-                    auto res =
-                        mark_plus(feature->name, spec_cluster, *m_graph, *m_graph_plan, prevent_default_features);
-
-                    Checks::check_exit(
-                        VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS, "Error: Unable to locate feature %s", spec);
-                }
-
-                auto res = mark_plus("core", spec_cluster, *m_graph, *m_graph_plan, prevent_default_features);
 
-                Checks::check_exit(
-                    VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS, "Error: Unable to locate feature %s", spec);
-            }
-            else
-            {
-                Checks::exit_with_message(
-                    VCPKG_LINE_INFO, "Error: Unable to handle '*' because can't find CONTROL for %s", spec.spec());
-            }
-        }
-        else
-        {
-            auto res = mark_plus(spec.feature(), spec_cluster, *m_graph, *m_graph_plan, prevent_default_features);
+        auto res = mark_plus(spec.feature(), spec_cluster, *m_graph, *m_graph_plan, prevent_default_features);
 
-            Checks::check_exit(
-                VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS, "Error: Unable to locate feature %s", spec);
-        }
+        Checks::check_exit(VCPKG_LINE_INFO, res == MarkPlusResult::SUCCESS, "Error: Unable to locate feature %s", spec);
 
         m_graph_plan->install_graph.add_vertex(ClusterPtr{&spec_cluster});
     }
@@ -654,7 +665,7 @@ namespace vcpkg::Dependencies
         Cluster& spec_cluster = m_graph->get(spec);
         spec_cluster.request_type = RequestType::USER_REQUESTED;
 
-        mark_minus(spec_cluster, *m_graph, *m_graph_plan);
+        mark_minus(spec_cluster, *m_graph, *m_graph_plan, {});
     }
 
     std::vector<AnyAction> PackageGraph::serialize() const
@@ -669,11 +680,8 @@ namespace vcpkg::Dependencies
 
         for (auto&& p_cluster : remove_toposort)
         {
-            auto scf = *p_cluster->source_control_file.get();
-            auto spec = PackageSpec::from_name_and_triplet(scf->core_paragraph->name, p_cluster->spec.triplet())
-                            .value_or_exit(VCPKG_LINE_INFO);
             plan.emplace_back(RemovePlanAction{
-                std::move(spec),
+                std::move(p_cluster->spec),
                 RemovePlanType::REMOVE,
                 p_cluster->request_type,
             });
@@ -684,8 +692,7 @@ namespace vcpkg::Dependencies
             if (p_cluster->transient_uninstalled)
             {
                 // If it will be transiently uninstalled, we need to issue a full installation command
-                auto pscf = p_cluster->source_control_file.value_or_exit(VCPKG_LINE_INFO);
-                Checks::check_exit(VCPKG_LINE_INFO, pscf != nullptr);
+                auto pscf = p_cluster->source.value_or_exit(VCPKG_LINE_INFO).scf;
 
                 auto dep_specs = Util::fmap(m_graph_plan->install_graph.adjacency_list(p_cluster),
                                             [](ClusterPtr const& p) { return p->spec; });
@@ -703,10 +710,10 @@ namespace vcpkg::Dependencies
             {
                 // If the package isn't transitively installed, still include it if the user explicitly requested it
                 if (p_cluster->request_type != RequestType::USER_REQUESTED) continue;
+                auto&& installed = p_cluster->installed.value_or_exit(VCPKG_LINE_INFO);
                 plan.emplace_back(InstallPlanAction{
-                    p_cluster->spec,
-                    InstalledPackageView{p_cluster->installed_package},
-                    p_cluster->original_features,
+                    InstalledPackageView{installed.ipv},
+                    installed.original_features,
                     p_cluster->request_type,
                 });
             }
@@ -722,44 +729,36 @@ namespace vcpkg::Dependencies
 
         auto installed_ports = get_installed_ports(status_db);
 
-        for (auto&& status_paragraph : installed_ports)
+        for (auto&& ipv : installed_ports)
         {
-            Cluster& cluster = graph->get(status_paragraph->package.spec);
+            Cluster& cluster = graph->get(ipv.spec());
 
             cluster.transient_uninstalled = false;
 
-            auto& status_paragraph_feature = status_paragraph->package.feature;
-
-            // In this case, empty string indicates the "core" paragraph for a package.
-            if (status_paragraph_feature.empty())
-            {
-                cluster.original_features.insert("core");
-                cluster.installed_package.core = status_paragraph;
-            }
-            else
-            {
-                cluster.original_features.insert(status_paragraph_feature);
-                cluster.installed_package.features.emplace_back(status_paragraph);
-            }
+            cluster.installed = [](const InstalledPackageView& ipv) -> ClusterInstalled {
+                ClusterInstalled ret;
+                ret.ipv = ipv;
+                ret.original_features.emplace("core");
+                for (auto&& feature : ipv.features)
+                    ret.original_features.emplace(feature->package.feature);
+                return ret;
+            }(ipv);
         }
 
         // Populate the graph with "remove edges", which are the reverse of the Build-Depends edges.
-        for (auto&& status_paragraph : installed_ports)
+        for (auto&& ipv : installed_ports)
         {
-            auto& spec = status_paragraph->package.spec;
-            auto& status_paragraph_feature = status_paragraph->package.feature;
-            auto reverse_edges = FeatureSpec::from_strings_and_triplet(status_paragraph->package.depends,
-                                                                       status_paragraph->package.spec.triplet());
+            auto deps = ipv.dependencies();
 
-            for (auto&& dependency : reverse_edges)
+            for (auto&& dep : deps)
             {
-                auto& dep_cluster = graph->get(dependency.spec());
-
-                auto depends_name = dependency.feature();
-                if (depends_name.empty()) depends_name = "core";
-
-                auto& target_node = dep_cluster.edges_by_feature[depends_name];
-                target_node.remove_edges.emplace_back(FeatureSpec{spec, status_paragraph_feature});
+                auto p_installed = graph->get(dep).installed.get();
+                Checks::check_exit(VCPKG_LINE_INFO,
+                                   p_installed,
+                                   "Error: database corrupted. Package %s is installed but dependency %s is not.",
+                                   ipv.spec(),
+                                   dep);
+                p_installed->remove_edges.emplace(ipv.spec());
             }
         }
         return graph;
diff --git a/toolsrc/src/vcpkg/remove.cpp b/toolsrc/src/vcpkg/remove.cpp
index 32433b234..13cc9325e 100644
--- a/toolsrc/src/vcpkg/remove.cpp
+++ b/toolsrc/src/vcpkg/remove.cpp
@@ -201,9 +201,9 @@ namespace vcpkg::Remove
     static std::vector<std::string> valid_arguments(const VcpkgPaths& paths)
     {
         const StatusParagraphs status_db = database_load_check(paths);
-        const std::vector<StatusParagraph*> installed_packages = get_installed_ports(status_db);
+        auto installed_packages = get_installed_ports(status_db);
 
-        return Util::fmap(installed_packages, [](auto&& pgh) -> std::string { return pgh->package.spec.to_string(); });
+        return Util::fmap(installed_packages, [](auto&& pgh) -> std::string { return pgh.spec().to_string(); });
     }
 
     const CommandStructure COMMAND_STRUCTURE = {
diff --git a/toolsrc/src/vcpkg/statusparagraph.cpp b/toolsrc/src/vcpkg/statusparagraph.cpp
index 62d1d4b42..236689494 100644
--- a/toolsrc/src/vcpkg/statusparagraph.cpp
+++ b/toolsrc/src/vcpkg/statusparagraph.cpp
@@ -95,7 +95,7 @@ namespace vcpkg
         // Add the core paragraph dependencies to the list
         deps.insert(deps.end(), core->package.depends.begin(), core->package.depends.end());
 
-        auto&& spec = core->package.spec;
+        auto&& l_spec = spec();
 
         // <hack>
         // This is a hack to work around existing installations that put featurespecs into binary packages
@@ -104,12 +104,12 @@ namespace vcpkg
         {
             dep.erase(std::find(dep.begin(), dep.end(), '['), dep.end());
         }
-        Util::unstable_keep_if(deps, [&](auto&& e) { return e != spec.name(); });
+        Util::unstable_keep_if(deps, [&](auto&& e) { return e != l_spec.name(); });
         // </hack>
         Util::sort_unique_erase(deps);
 
         return Util::fmap(deps, [&](const std::string& dep) -> PackageSpec {
-            auto maybe_dependency_spec = PackageSpec::from_name_and_triplet(dep, spec.triplet());
+            auto maybe_dependency_spec = PackageSpec::from_name_and_triplet(dep, l_spec.triplet());
             if (auto dependency_spec = maybe_dependency_spec.get())
             {
                 return std::move(*dependency_spec);
@@ -120,7 +120,7 @@ namespace vcpkg
                                       "Invalid dependency [%s] in package [%s]\n"
                                       "%s",
                                       dep,
-                                      spec.name(),
+                                      l_spec.name(),
                                       vcpkg::to_string(error_type));
         });
     }
diff --git a/toolsrc/src/vcpkg/update.cpp b/toolsrc/src/vcpkg/update.cpp
index d6c5614ed..57259f952 100644
--- a/toolsrc/src/vcpkg/update.cpp
+++ b/toolsrc/src/vcpkg/update.cpp
@@ -17,17 +17,12 @@ namespace vcpkg::Update
     std::vector<OutdatedPackage> find_outdated_packages(const Dependencies::PortFileProvider& provider,
                                                         const StatusParagraphs& status_db)
     {
-        const std::vector<StatusParagraph*> installed_packages = get_installed_ports(status_db);
+        auto installed_packages = get_installed_ports(status_db);
 
         std::vector<OutdatedPackage> output;
-        for (const StatusParagraph* pgh : installed_packages)
+        for (auto&& ipv : installed_packages)
         {
-            if (!pgh->package.feature.empty())
-            {
-                // Skip feature paragraphs; only consider master paragraphs for needing updates.
-                continue;
-            }
-
+            const auto& pgh = ipv.core;
             auto maybe_scf = provider.get_control_file(pgh->package.spec.name());
             if (auto p_scf = maybe_scf.get())
             {
diff --git a/toolsrc/src/vcpkg/vcpkglib.cpp b/toolsrc/src/vcpkg/vcpkglib.cpp
index 7979fd9a5..c8e95dab1 100644
--- a/toolsrc/src/vcpkg/vcpkglib.cpp
+++ b/toolsrc/src/vcpkg/vcpkglib.cpp
@@ -169,16 +169,32 @@ namespace vcpkg
         fs.rename(updated_listfile_path, listfile_path);
     }
 
-    std::vector<StatusParagraph*> get_installed_ports(const StatusParagraphs& status_db)
+    std::vector<InstalledPackageView> get_installed_ports(const StatusParagraphs& status_db)
     {
-        std::vector<StatusParagraph*> installed_packages;
+        std::map<PackageSpec, InstalledPackageView> ipv_map;
+
+        std::vector<InstalledPackageView> installed_packages;
         for (auto&& pgh : status_db)
         {
             if (!pgh->is_installed()) continue;
-            installed_packages.push_back(pgh.get());
+            auto& ipv = ipv_map[pgh->package.spec];
+            if (pgh->package.feature.empty())
+            {
+                ipv.core = pgh.get();
+            }
+            else
+            {
+                ipv.features.emplace_back(pgh.get());
+            }
         }
 
-        return installed_packages;
+        for (auto&& ipv : ipv_map)
+            Checks::check_exit(VCPKG_LINE_INFO,
+                               ipv.second.core != nullptr,
+                               "Database is corrupted: package %s has features but no core paragraph.",
+                               ipv.first);
+
+        return Util::fmap(ipv_map, [](auto&& p) -> InstalledPackageView { return std::move(p.second); });
     }
 
     std::vector<StatusParagraphAndAssociatedFiles> get_installed_files(const VcpkgPaths& paths,