[vcpkg] Introduce `create_versioned_install_plan()` (#14633)

* [vcpkg] Implement constraints in manifests

* [vcpkg] Add SourceControlFile::check_against_feature_flags to prevent accidentally ignoring versioning fields

* [vcpkg] Switch check_against_feature_flags to accept fs::path

* [vcpkg] Implement overrides parsing in manifests

* [vcpkg] Address CR comments

* [vcpkg] Initial implementation of create_versioned_install_plan()

* [vcpkg] Implement port-version minimums

* [vcpkg] Implement relaxation phase

* [vcpkg] Refactor tests to use check_name_and_version

* [vcpkg] Implemented simple relaxed scheme

* [vcpkg] More relaxed scheme tests

* [vcpkg] Mixed scheme testing

* [vcpkg] Support versions and features without defaults

* [vcpkg] Support versions and features without defaults 2

* [vcpkg] Only consider greater of toplevel and baseilne

* [vcpkg] Implement overrides

* [vcpkg] Install defaults

* [vcpkg] Handle defaults of transitive packages

* [vcpkg] Fix warnings for Span of initializer_list

* [vcpkg] Use CMakeVarProvider during versioned install

* [vcpkg] Handle inter-feature dependencies

* [vcpkg] Correctly handle qualified Dependencies at toplevel

* [vcpkg] Address CR comments

Co-authored-by: Robert Schumacher <roschuma@microsoft.com>

7 files changed, 1878 insertions, 123 deletions

diff --git a/toolsrc/src/vcpkg-test/dependencies.cpp b/toolsrc/src/vcpkg-test/dependencies.cpp
index 2f82d21b4..bcc2f14a0 100644
--- a/toolsrc/src/vcpkg-test/dependencies.cpp
+++ b/toolsrc/src/vcpkg-test/dependencies.cpp
@@ -1,152 +1,1096 @@
 #include <catch2/catch.hpp>
 
+#include <vcpkg/base/graphs.h>
+
 #include <vcpkg/dependencies.h>
-#include <vcpkg/paragraphparser.h>
 #include <vcpkg/portfileprovider.h>
 #include <vcpkg/sourceparagraph.h>
+#include <vcpkg/triplet.h>
+
+#include <memory>
+#include <unordered_map>
+#include <vector>
 
 #include <vcpkg-test/mockcmakevarprovider.h>
 #include <vcpkg-test/util.h>
 
 using namespace vcpkg;
-using namespace vcpkg::Parse;
 
-TEST_CASE ("parse depends", "[dependencies]")
+using Test::make_control_file;
+using Test::make_status_feature_pgh;
+using Test::make_status_pgh;
+using Test::MockCMakeVarProvider;
+using Test::PackageSpecMap;
+
+struct MockBaselineProvider : PortFileProvider::IBaselineProvider
+{
+    mutable std::map<std::string, Versions::Version, std::less<>> v;
+
+    Optional<Versions::Version> get_baseline_version(StringView name) const override
+    {
+        auto it = v.find(name);
+        if (it == v.end()) return nullopt;
+        return it->second;
+    }
+};
+
+struct MockVersionedPortfileProvider : PortFileProvider::IVersionedPortfileProvider
+{
+    mutable std::map<std::string, std::map<Versions::Version, SourceControlFileLocation, VersionTMapLess>> v;
+
+    ExpectedS<const SourceControlFileLocation&> get_control_file(
+        const vcpkg::Versions::VersionSpec& versionspec) const override
+    {
+        return get_control_file(versionspec.port_name, versionspec.version);
+    }
+
+    ExpectedS<const SourceControlFileLocation&> get_control_file(const std::string& name,
+                                                                 const vcpkg::Versions::Version& version) const
+    {
+        auto it = v.find(name);
+        if (it == v.end()) return std::string("Unknown port name");
+        auto it2 = it->second.find(version);
+        if (it2 == it->second.end()) return std::string("Unknown port version");
+        return it2->second;
+    }
+
+    virtual const std::vector<vcpkg::Versions::VersionSpec>& get_port_versions(StringView) const override
+    {
+        Checks::unreachable(VCPKG_LINE_INFO);
+    }
+
+    SourceControlFileLocation& emplace(std::string&& name,
+                                       Versions::Version&& version,
+                                       Versions::Scheme scheme = Versions::Scheme::String)
+    {
+        auto it = v.find(name);
+        if (it == v.end())
+            it = v.emplace(name, std::map<Versions::Version, SourceControlFileLocation, VersionTMapLess>{}).first;
+
+        auto it2 = it->second.find(version);
+        if (it2 == it->second.end())
+        {
+            auto scf = std::make_unique<SourceControlFile>();
+            auto core = std::make_unique<SourceParagraph>();
+            core->name = name;
+            core->version = version.text();
+            core->port_version = version.port_version();
+            core->version_scheme = scheme;
+            scf->core_paragraph = std::move(core);
+            it2 = it->second.emplace(version, SourceControlFileLocation{std::move(scf), fs::u8path(name)}).first;
+        }
+        return it2->second;
+    }
+};
+
+using Versions::Constraint;
+using Versions::Scheme;
+
+template<class T>
+T unwrap(ExpectedS<T> e)
+{
+    if (!e.has_value())
+    {
+        INFO(e.error());
+        REQUIRE(false);
+    }
+    return std::move(*e.get());
+}
+
+static void check_name_and_version(const Dependencies::InstallPlanAction& ipa,
+                                   StringLiteral name,
+                                   Versions::Version v,
+                                   std::initializer_list<StringLiteral> features = {})
+{
+    CHECK(ipa.spec.name() == name);
+    CHECK(ipa.source_control_file_location.has_value());
+    CHECK(ipa.feature_list.size() == features.size() + 1);
+    {
+        INFO("ipa.feature_list = [" << Strings::join(", ", ipa.feature_list) << "]");
+        for (auto&& f : features)
+        {
+            INFO("f = \"" << f.c_str() << "\"");
+            CHECK(Util::find(ipa.feature_list, f) != ipa.feature_list.end());
+        }
+        CHECK(Util::find(ipa.feature_list, "core") != ipa.feature_list.end());
+    }
+    if (auto scfl = ipa.source_control_file_location.get())
+    {
+        CHECK(scfl->source_control_file->core_paragraph->version == v.text());
+        CHECK(scfl->source_control_file->core_paragraph->port_version == v.port_version());
+    }
+}
+
+static const PackageSpec& toplevel_spec()
+{
+    static const PackageSpec ret("toplevel-spec", Test::X86_WINDOWS);
+    return ret;
+}
+
+TEST_CASE ("basic version install single", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a"}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    REQUIRE(install_plan.install_actions.at(0).spec.name() == "a");
+}
+
+TEST_CASE ("basic version install detect cycle", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{}},
+    };
+    vp.emplace("b", {"1", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"a", {}, {}, DependencyConstraint{}},
+    };
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a"}}, {}, toplevel_spec());
+
+    REQUIRE(!install_plan.has_value());
+}
+
+TEST_CASE ("basic version install scheme", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{}},
+    };
+    vp.emplace("b", {"1", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a"}}, {}, toplevel_spec()));
+
+    CHECK(install_plan.size() == 2);
+
+    StringLiteral names[] = {"b", "a"};
+    for (size_t i = 0; i < install_plan.install_actions.size() && i < 2; ++i)
+    {
+        CHECK(install_plan.install_actions[i].spec.name() == names[i]);
+    }
+}
+
+TEST_CASE ("basic version install scheme diamond", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+    bp.v["c"] = {"1", 0};
+    bp.v["d"] = {"1", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{}},
+        Dependency{"c", {}, {}, DependencyConstraint{}},
+    };
+    vp.emplace("b", {"1", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"c", {}, {}, DependencyConstraint{}},
+        Dependency{"d", {}, {}, DependencyConstraint{}},
+    };
+    vp.emplace("c", {"1", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"d", {}, {}, DependencyConstraint{}},
+    };
+    vp.emplace("d", {"1", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a"}}, {}, toplevel_spec()));
+
+    CHECK(install_plan.size() == 4);
+
+    StringLiteral names[] = {"d", "c", "b", "a"};
+    for (size_t i = 0; i < install_plan.install_actions.size() && i < 4; ++i)
+    {
+        CHECK(install_plan.install_actions[i].spec.name() == names[i]);
+    }
+}
+
+TEST_CASE ("basic version install scheme baseline missing", "[versionplan]")
+{
+    MockBaselineProvider bp;
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a"}}, {}, toplevel_spec());
+
+    REQUIRE(!install_plan.has_value());
+}
+
+TEST_CASE ("basic version install scheme baseline missing success", "[versionplan]")
 {
-    auto w = parse_dependencies_list("liba (windows)");
-    REQUIRE(w);
-    auto& v = *w.get();
-    REQUIRE(v.size() == 1);
-    REQUIRE(v.at(0).name == "liba");
-    REQUIRE(v.at(0).platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", ""}}));
-    REQUIRE(v.at(0).platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "WindowsStore"}}));
-    REQUIRE(!v.at(0).platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "Darwin"}}));
+    MockBaselineProvider bp;
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0});
+    vp.emplace("a", {"2", 0});
+    vp.emplace("a", {"3", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp,
+                                                           bp,
+                                                           var_provider,
+                                                           {
+                                                               Dependency{"a", {}, {}, {Constraint::Type::Exact, "2"}},
+                                                           },
+                                                           {},
+                                                           toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"2", 0});
 }
 
-TEST_CASE ("filter depends", "[dependencies]")
+TEST_CASE ("basic version install scheme baseline", "[versionplan]")
 {
-    const std::unordered_map<std::string, std::string> x64_win_cmake_vars{{"VCPKG_TARGET_ARCHITECTURE", "x64"},
-                                                                          {"VCPKG_CMAKE_SYSTEM_NAME", ""}};
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
 
-    const std::unordered_map<std::string, std::string> arm_uwp_cmake_vars{{"VCPKG_TARGET_ARCHITECTURE", "arm"},
-                                                                          {"VCPKG_CMAKE_SYSTEM_NAME", "WindowsStore"}};
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0});
+    vp.emplace("a", {"2", 0});
+    vp.emplace("a", {"3", 0});
+
+    MockCMakeVarProvider var_provider;
 
-    auto deps_ = parse_dependencies_list("liba (!uwp), libb, libc (uwp)");
-    REQUIRE(deps_);
-    auto& deps = *deps_.get();
-    auto v = filter_dependencies(deps, Test::X64_WINDOWS, x64_win_cmake_vars);
-    REQUIRE(v.size() == 2);
-    REQUIRE(v.at(0).package_spec.name() == "liba");
-    REQUIRE(v.at(1).package_spec.name() == "libb");
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a"}}, {}, toplevel_spec()));
 
-    auto v2 = filter_dependencies(deps, Test::ARM_UWP, arm_uwp_cmake_vars);
-    REQUIRE(v.size() == 2);
-    REQUIRE(v2.at(0).package_spec.name() == "libb");
-    REQUIRE(v2.at(1).package_spec.name() == "libc");
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"2", 0});
 }
 
-TEST_CASE ("parse feature depends", "[dependencies]")
+TEST_CASE ("version string baseline agree", "[versionplan]")
 {
-    auto u_ = parse_dependencies_list("libwebp[anim, gif2webp, img2webp, info, mux, nearlossless, "
-                                      "simd, cwebp, dwebp], libwebp[vwebp-sdl, extras] (!osx)");
-    REQUIRE(u_);
-    auto& v = *u_.get();
-    REQUIRE(v.size() == 2);
-    auto&& a0 = v.at(0);
-    REQUIRE(a0.name == "libwebp");
-    REQUIRE(a0.features.size() == 9);
-    REQUIRE(a0.platform.is_empty());
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0});
+    vp.emplace("a", {"2", 0});
+    vp.emplace("a", {"3", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = Dependencies::create_versioned_install_plan(
+        vp, bp, var_provider, {Dependency{"a", {}, {}, {Constraint::Type::Exact, "2"}}}, {}, toplevel_spec());
+
+    REQUIRE(install_plan.has_value());
+}
+
+TEST_CASE ("version install scheme baseline conflict", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"1", 0});
+    vp.emplace("a", {"2", 0});
+    vp.emplace("a", {"3", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan =
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Exact, "3"}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec());
+
+    REQUIRE(!install_plan.has_value());
+}
+
+TEST_CASE ("version install string port version", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0});
+    vp.emplace("a", {"2", 1});
+    vp.emplace("a", {"2", 2});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Exact, "2", 1}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"2", 1});
+}
+
+TEST_CASE ("version install string port version 2", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 1};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0});
+    vp.emplace("a", {"2", 1});
+    vp.emplace("a", {"2", 2});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Exact, "2", 0}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"2", 1});
+}
+
+TEST_CASE ("version install transitive string", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{Constraint::Type::Exact, "1"}},
+    };
+    vp.emplace("a", {"2", 1}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{Constraint::Type::Exact, "2"}},
+    };
+    vp.emplace("b", {"1", 0});
+    vp.emplace("b", {"2", 0});
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Exact, "2", 1}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "b", {"2", 0});
+    check_name_and_version(install_plan.install_actions[1], "a", {"2", 1});
+}
+
+TEST_CASE ("version install simple relaxed", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0}, Scheme::Relaxed);
+    vp.emplace("a", {"3", 0}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Minimum, "3", 0}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"3", 0});
+}
+
+TEST_CASE ("version install transitive relaxed", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+    bp.v["b"] = {"2", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0}, Scheme::Relaxed);
+    vp.emplace("a", {"3", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{Constraint::Type::Minimum, "3"}},
+    };
+    vp.emplace("b", {"2", 0}, Scheme::Relaxed);
+    vp.emplace("b", {"3", 0}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Minimum, "3", 0}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "b", {"3", 0});
+    check_name_and_version(install_plan.install_actions[1], "a", {"3", 0});
+}
+
+TEST_CASE ("version install diamond relaxed", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"2", 0};
+    bp.v["b"] = {"3", 0};
+
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0}, Scheme::Relaxed);
+    vp.emplace("a", {"3", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{Constraint::Type::Minimum, "2", 1}},
+        Dependency{"c", {}, {}, DependencyConstraint{Constraint::Type::Minimum, "5", 1}},
+    };
+    vp.emplace("b", {"2", 1}, Scheme::Relaxed);
+    vp.emplace("b", {"3", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+        Dependency{"c", {}, {}, DependencyConstraint{Constraint::Type::Minimum, "9", 2}},
+    };
+    vp.emplace("c", {"5", 1}, Scheme::Relaxed);
+    vp.emplace("c", {"9", 2}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp,
+                                                    bp,
+                                                    var_provider,
+                                                    {
+                                                        Dependency{"a", {}, {}, {Constraint::Type::Minimum, "3", 0}},
+                                                        Dependency{"b", {}, {}, {Constraint::Type::Minimum, "2", 1}},
+                                                    },
+                                                    {},
+                                                    toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 3);
+    check_name_and_version(install_plan.install_actions[0], "c", {"9", 2});
+    check_name_and_version(install_plan.install_actions[1], "b", {"3", 0});
+    check_name_and_version(install_plan.install_actions[2], "a", {"3", 0});
+}
+
+TEST_CASE ("version install scheme change in port version", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+    vp.emplace("a", {"2", 0}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{Constraint::Type::Exact, "1"}},
+    };
+    vp.emplace("a", {"2", 1}).source_control_file->core_paragraph->dependencies = {
+        Dependency{"b", {}, {}, DependencyConstraint{Constraint::Type::Minimum, "1", 1}},
+    };
+    vp.emplace("b", {"1", 0}, Scheme::String);
+    vp.emplace("b", {"1", 1}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+
+    SECTION ("lower baseline")
+    {
+        MockBaselineProvider bp;
+        bp.v["a"] = {"2", 0};
+
+        auto install_plan = unwrap(
+            Dependencies::create_versioned_install_plan(vp,
+                                                        bp,
+                                                        var_provider,
+                                                        {
+                                                            Dependency{"a", {}, {}, {Constraint::Type::Exact, "2", 1}},
+                                                        },
+                                                        {},
+                                                        toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 2);
+        check_name_and_version(install_plan.install_actions[0], "b", {"1", 1});
+        check_name_and_version(install_plan.install_actions[1], "a", {"2", 1});
+    }
+    SECTION ("higher baseline")
+    {
+        MockBaselineProvider bp;
+        bp.v["a"] = {"2", 1};
+
+        auto install_plan = unwrap(
+            Dependencies::create_versioned_install_plan(vp,
+                                                        bp,
+                                                        var_provider,
+                                                        {
+                                                            Dependency{"a", {}, {}, {Constraint::Type::Exact, "2", 0}},
+                                                        },
+                                                        {},
+                                                        toplevel_spec()));
 
-    auto&& a1 = v.at(1);
-    REQUIRE(a1.name == "libwebp");
-    REQUIRE(a1.features.size() == 2);
-    REQUIRE(!a1.platform.is_empty());
-    REQUIRE(a1.platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", ""}}));
-    REQUIRE(a1.platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "Linux"}}));
-    REQUIRE_FALSE(a1.platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "Darwin"}}));
+        REQUIRE(install_plan.size() == 2);
+        check_name_and_version(install_plan.install_actions[0], "b", {"1", 1});
+        check_name_and_version(install_plan.install_actions[1], "a", {"2", 1});
+    }
 }
 
-TEST_CASE ("qualified dependency", "[dependencies]")
+TEST_CASE ("version install simple feature", "[versionplan]")
 {
-    using namespace Test;
-    PackageSpecMap spec_map;
-    auto spec_a = FullPackageSpec{spec_map.emplace("a", "b, b[b1] (linux)"), {}};
-    auto spec_b = FullPackageSpec{spec_map.emplace("b", "", {{"b1", ""}}), {}};
+    MockVersionedPortfileProvider vp;
+    auto a_x = std::make_unique<FeatureParagraph>();
+    a_x->name = "x";
+    vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file->feature_paragraphs.push_back(std::move(a_x));
 
-    PortFileProvider::MapPortFileProvider map_port{spec_map.map};
     MockCMakeVarProvider var_provider;
 
-    auto plan = vcpkg::Dependencies::create_feature_install_plan(map_port, var_provider, {spec_a}, {});
-    REQUIRE(plan.install_actions.size() == 2);
-    REQUIRE(plan.install_actions.at(0).feature_list == std::vector<std::string>{"core"});
+    SECTION ("with baseline")
+    {
+        MockBaselineProvider bp;
+        bp.v["a"] = {"1", 0};
+
+        auto install_plan = unwrap(Dependencies::create_versioned_install_plan(vp,
+                                                                               bp,
+                                                                               var_provider,
+                                                                               {
+                                                                                   Dependency{"a", {"x"}},
+                                                                               },
+                                                                               {},
+                                                                               toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 1);
+        check_name_and_version(install_plan.install_actions[0], "a", {"1", 0}, {"x"});
+    }
+
+    SECTION ("without baseline")
+    {
+        MockBaselineProvider bp;
+
+        auto install_plan = unwrap(Dependencies::create_versioned_install_plan(
+            vp,
+            bp,
+            var_provider,
+            {
+                Dependency{"a", {"x"}, {}, {Constraint::Type::Minimum, "1", 0}},
+            },
+            {},
+            toplevel_spec()));
 
-    FullPackageSpec linspec_a{{"a", Triplet::from_canonical_name("x64-linux")}, {}};
-    var_provider.dep_info_vars[linspec_a.package_spec].emplace("VCPKG_CMAKE_SYSTEM_NAME", "Linux");
-    auto plan2 = vcpkg::Dependencies::create_feature_install_plan(map_port, var_provider, {linspec_a}, {});
-    REQUIRE(plan2.install_actions.size() == 2);
-    REQUIRE(plan2.install_actions.at(0).feature_list == std::vector<std::string>{"b1", "core"});
+        REQUIRE(install_plan.size() == 1);
+        check_name_and_version(install_plan.install_actions[0], "a", {"1", 0}, {"x"});
+    }
 }
 
-TEST_CASE ("resolve_deps_as_top_level", "[dependencies]")
+static std::unique_ptr<FeatureParagraph> make_fpgh(std::string name)
 {
-    using namespace Test;
-    PackageSpecMap spec_map;
-    FullPackageSpec spec_a{spec_map.emplace("a", "b, b[b1] (linux)"), {}};
-    FullPackageSpec spec_b{spec_map.emplace("b", "", {{"b1", ""}}), {}};
-    FullPackageSpec spec_c{spec_map.emplace("c", "b", {{"c1", "b[b1]"}, {"c2", "c[c1], a"}}, {"c1"}), {"core"}};
-    FullPackageSpec spec_d{spec_map.emplace("d", "c[core]"), {}};
+    auto f = std::make_unique<FeatureParagraph>();
+    f->name = std::move(name);
+    return f;
+}
+
+TEST_CASE ("version install transitive features", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto a_x = make_fpgh("x");
+    a_x->dependencies.push_back(Dependency{"b", {"y"}});
+    vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file->feature_paragraphs.push_back(std::move(a_x));
+
+    auto b_y = make_fpgh("y");
+    vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file->feature_paragraphs.push_back(std::move(b_y));
 
-    PortFileProvider::MapPortFileProvider map_port{spec_map.map};
     MockCMakeVarProvider var_provider;
-    Triplet t_linux = Triplet::from_canonical_name("x64-linux");
-    var_provider.dep_info_vars[{"a", t_linux}].emplace("VCPKG_CMAKE_SYSTEM_NAME", "Linux");
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+
+    auto install_plan = unwrap(Dependencies::create_versioned_install_plan(vp,
+                                                                           bp,
+                                                                           var_provider,
+                                                                           {
+                                                                               Dependency{"a", {"x"}},
+                                                                           },
+                                                                           {},
+                                                                           toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "b", {"1", 0}, {"y"});
+    check_name_and_version(install_plan.install_actions[1], "a", {"1", 0}, {"x"});
+}
+
+TEST_CASE ("version install transitive feature versioned", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto a_x = make_fpgh("x");
+    a_x->dependencies.push_back(Dependency{"b", {"y"}, {}, {Constraint::Type::Minimum, "2", 0}});
+    vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file->feature_paragraphs.push_back(std::move(a_x));
+
     {
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("a").source_control_file, Test::X86_WINDOWS, {}, var_provider);
-        REQUIRE(deps.size() == 1);
-        REQUIRE(deps.at(0) == spec_b);
+        auto b_y = make_fpgh("y");
+        vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file->feature_paragraphs.push_back(std::move(b_y));
     }
     {
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("a").source_control_file, t_linux, {}, var_provider);
-        REQUIRE(deps.size() == 1);
-        REQUIRE(deps.at(0) == FullPackageSpec({"b", t_linux}, {"b1"}));
+        auto b_y = make_fpgh("y");
+        b_y->dependencies.push_back(Dependency{"c"});
+        vp.emplace("b", {"2", 0}, Scheme::Relaxed).source_control_file->feature_paragraphs.push_back(std::move(b_y));
     }
+
+    vp.emplace("c", {"1", 0}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["c"] = {"1", 0};
+
+    auto install_plan = unwrap(Dependencies::create_versioned_install_plan(vp,
+                                                                           bp,
+                                                                           var_provider,
+                                                                           {
+                                                                               Dependency{"a", {"x"}},
+                                                                           },
+                                                                           {},
+                                                                           toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 3);
+    check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
+    check_name_and_version(install_plan.install_actions[1], "b", {"2", 0}, {"y"});
+    check_name_and_version(install_plan.install_actions[2], "a", {"1", 0}, {"x"});
+}
+
+TEST_CASE ("version install constraint-reduction", "[versionplan]")
+{
+    MockCMakeVarProvider var_provider;
+
+    SECTION ("higher baseline")
     {
-        // without defaults
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {}, var_provider);
-        REQUIRE(deps.size() == 1);
-        REQUIRE(deps.at(0) == spec_b);
+        MockVersionedPortfileProvider vp;
+
+        vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+            Dependency{"c", {}, {}, {Constraint::Type::Minimum, "2"}},
+        };
+        vp.emplace("b", {"2", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+            Dependency{"c", {}, {}, {Constraint::Type::Minimum, "1"}},
+        };
+
+        vp.emplace("c", {"1", 0}, Scheme::Relaxed);
+        // c@2 is used to detect if certain constraints were evaluated
+        vp.emplace("c", {"2", 0}, Scheme::Relaxed);
+
+        MockBaselineProvider bp;
+        bp.v["b"] = {"2", 0};
+        bp.v["c"] = {"1", 0};
+
+        auto install_plan = unwrap(
+            Dependencies::create_versioned_install_plan(vp,
+                                                        bp,
+                                                        var_provider,
+                                                        {
+                                                            Dependency{"b", {}, {}, {Constraint::Type::Minimum, "1"}},
+                                                        },
+                                                        {},
+                                                        toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 2);
+        check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
+        check_name_and_version(install_plan.install_actions[1], "b", {"2", 0});
     }
-    FullPackageSpec spec_b_with_b1{spec_b.package_spec, {"b1"}};
+
+    SECTION ("higher toplevel")
+    {
+        MockVersionedPortfileProvider vp;
+
+        vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+            Dependency{"c", {}, {}, {Constraint::Type::Minimum, "2"}},
+        };
+        vp.emplace("b", {"2", 0}, Scheme::Relaxed).source_control_file->core_paragraph->dependencies = {
+            Dependency{"c", {}, {}, {Constraint::Type::Minimum, "1"}},
+        };
+
+        vp.emplace("c", {"1", 0}, Scheme::Relaxed);
+        // c@2 is used to detect if certain constraints were evaluated
+        vp.emplace("c", {"2", 0}, Scheme::Relaxed);
+
+        MockBaselineProvider bp;
+        bp.v["b"] = {"1", 0};
+        bp.v["c"] = {"1", 0};
+
+        auto install_plan = unwrap(
+            Dependencies::create_versioned_install_plan(vp,
+                                                        bp,
+                                                        var_provider,
+                                                        {
+                                                            Dependency{"b", {}, {}, {Constraint::Type::Minimum, "2"}},
+                                                        },
+                                                        {},
+                                                        toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 2);
+        check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
+        check_name_and_version(install_plan.install_actions[1], "b", {"2", 0});
+    }
+}
+
+TEST_CASE ("version install overrides", "[versionplan]")
+{
+    MockCMakeVarProvider var_provider;
+
+    MockVersionedPortfileProvider vp;
+
+    vp.emplace("b", {"1", 0}, Scheme::Relaxed);
+    vp.emplace("b", {"2", 0}, Scheme::Relaxed);
+    vp.emplace("c", {"1", 0}, Scheme::String);
+    vp.emplace("c", {"2", 0}, Scheme::String);
+
+    MockBaselineProvider bp;
+    bp.v["b"] = {"2", 0};
+    bp.v["c"] = {"2", 0};
+
+    SECTION ("string")
     {
-        // with defaults of c (c1)
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {"default"}, var_provider);
-        REQUIRE(deps.size() == 1);
-        REQUIRE(deps.at(0) == spec_b_with_b1);
+        auto install_plan = unwrap(
+            Dependencies::create_versioned_install_plan(vp,
+                                                        bp,
+                                                        var_provider,
+                                                        {Dependency{"c"}},
+                                                        {DependencyOverride{"b", "1"}, DependencyOverride{"c", "1"}},
+                                                        toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 1);
+        check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
     }
+
+    SECTION ("relaxed")
     {
-        // with c1
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {"c1"}, var_provider);
-        REQUIRE(deps.size() == 1);
-        REQUIRE(deps.at(0) == spec_b_with_b1);
+        auto install_plan = unwrap(
+            Dependencies::create_versioned_install_plan(vp,
+                                                        bp,
+                                                        var_provider,
+                                                        {Dependency{"b"}},
+                                                        {DependencyOverride{"b", "1"}, DependencyOverride{"c", "1"}},
+                                                        toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 1);
+        check_name_and_version(install_plan.install_actions[0], "b", {"1", 0});
     }
+}
+
+TEST_CASE ("version install transitive overrides", "[versionplan]")
+{
+    MockCMakeVarProvider var_provider;
+
+    MockVersionedPortfileProvider vp;
+
+    vp.emplace("b", {"1", 0}, Scheme::Relaxed)
+        .source_control_file->core_paragraph->dependencies.push_back({"c", {}, {}, {Constraint::Type::Exact, "2", 1}});
+    vp.emplace("b", {"2", 0}, Scheme::Relaxed);
+    vp.emplace("c", {"1", 0}, Scheme::String);
+    vp.emplace("c", {"2", 1}, Scheme::String);
+
+    MockBaselineProvider bp;
+    bp.v["b"] = {"2", 0};
+    bp.v["c"] = {"2", 1};
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp,
+                                                           bp,
+                                                           var_provider,
+                                                           {Dependency{"b"}},
+                                                           {DependencyOverride{"b", "1"}, DependencyOverride{"c", "1"}},
+                                                           toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
+    check_name_and_version(install_plan.install_actions[1], "b", {"1", 0});
+}
+
+TEST_CASE ("version install default features", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto a_x = make_fpgh("x");
+    auto& a_scf = vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file;
+    a_scf->core_paragraph->default_features.push_back("x");
+    a_scf->feature_paragraphs.push_back(std::move(a_x));
+
+    MockCMakeVarProvider var_provider;
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp, bp, var_provider, {Dependency{"a"}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"1", 0}, {"x"});
+}
+
+TEST_CASE ("version dont install default features", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto a_x = make_fpgh("x");
+    auto& a_scf = vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file;
+    a_scf->core_paragraph->default_features.push_back("x");
+    a_scf->feature_paragraphs.push_back(std::move(a_x));
+
+    MockCMakeVarProvider var_provider;
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+
+    auto install_plan = unwrap(Dependencies::create_versioned_install_plan(
+        vp, bp, var_provider, {Dependency{"a", {"core"}}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"1", 0});
+}
+
+TEST_CASE ("version install transitive default features", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto a_x = make_fpgh("x");
+    auto& a_scf = vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file;
+    a_scf->core_paragraph->default_features.push_back("x");
+    a_scf->feature_paragraphs.push_back(std::move(a_x));
+
+    auto& b_scf = vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file;
+    b_scf->core_paragraph->dependencies.push_back({"a", {"core"}});
+
+    MockCMakeVarProvider var_provider;
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+
+    auto install_plan = unwrap(
+        Dependencies::create_versioned_install_plan(vp, bp, var_provider, {Dependency{"b"}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "a", {"1", 0}, {"x"});
+    check_name_and_version(install_plan.install_actions[1], "b", {"1", 0});
+}
+
+static PlatformExpression::Expr parse_platform(StringView l)
+{
+    return unwrap(PlatformExpression::parse_platform_expression(l, PlatformExpression::MultipleBinaryOperators::Deny));
+}
+
+TEST_CASE ("version install qualified dependencies", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    vp.emplace("b", {"1", 0}, Scheme::Relaxed);
+    vp.emplace("c", {"1", 0}, Scheme::Relaxed);
+
+    MockBaselineProvider bp;
+    bp.v["b"] = {"1", 0};
+    bp.v["c"] = {"1", 0};
+
+    SECTION ("windows")
     {
-        // with c2 implying c1
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {"c2"}, var_provider);
-        REQUIRE(deps.size() == 2);
-        REQUIRE(deps.at(0) == spec_a);
-        REQUIRE(deps.at(1) == spec_b_with_b1);
+        MockCMakeVarProvider var_provider;
+        var_provider.dep_info_vars[toplevel_spec()] = {{"VCPKG_CMAKE_SYSTEM_NAME", "Windows"}};
+
+        auto install_plan = unwrap(Dependencies::create_versioned_install_plan(
+            vp,
+            bp,
+            var_provider,
+            {{"b", {}, parse_platform("!linux")}, {"c", {}, parse_platform("linux")}},
+            {},
+            toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 1);
+        check_name_and_version(install_plan.install_actions[0], "b", {"1", 0});
     }
+
+    SECTION ("linux")
     {
-        // d -> c[core]
-        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
-            *spec_map.map.at("d").source_control_file, Test::X86_WINDOWS, {}, var_provider);
-        REQUIRE(deps.size() == 1);
-        REQUIRE(deps.at(0) == spec_c);
+        MockCMakeVarProvider var_provider;
+        var_provider.dep_info_vars[toplevel_spec()] = {{"VCPKG_CMAKE_SYSTEM_NAME", "Linux"}};
+
+        auto install_plan = unwrap(Dependencies::create_versioned_install_plan(
+            vp,
+            bp,
+            var_provider,
+            {{"b", {}, parse_platform("!linux")}, {"c", {}, parse_platform("linux")}},
+            {},
+            toplevel_spec()));
+
+        REQUIRE(install_plan.size() == 1);
+        check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
     }
 }
+
+TEST_CASE ("version install qualified default suppression", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto& a_scf = vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file;
+    a_scf->core_paragraph->default_features.push_back("x");
+    a_scf->feature_paragraphs.push_back(make_fpgh("x"));
+
+    vp.emplace("b", {"1", 0}, Scheme::Relaxed)
+        .source_control_file->core_paragraph->dependencies.push_back({"a", {"core"}});
+
+    MockCMakeVarProvider var_provider;
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+
+    auto install_plan = unwrap(Dependencies::create_versioned_install_plan(
+        vp,
+        bp,
+        var_provider,
+        {{"b", {}, parse_platform("!linux")}, {"a", {"core"}, parse_platform("linux")}},
+        {},
+        toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "a", {"1", 0}, {"x"});
+    check_name_and_version(install_plan.install_actions[1], "b", {"1", 0});
+}
+
+TEST_CASE ("version install qualified transitive", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    vp.emplace("a", {"1", 0}, Scheme::Relaxed);
+    vp.emplace("c", {"1", 0}, Scheme::Relaxed);
+
+    auto& b_scf = vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file;
+    b_scf->core_paragraph->dependencies.push_back({"a", {}, parse_platform("!linux")});
+    b_scf->core_paragraph->dependencies.push_back({"c", {}, parse_platform("linux")});
+
+    MockCMakeVarProvider var_provider;
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+    bp.v["c"] = {"1", 0};
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"b"}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 2);
+    check_name_and_version(install_plan.install_actions[0], "a", {"1", 0});
+    check_name_and_version(install_plan.install_actions[1], "b", {"1", 0});
+}
+
+TEST_CASE ("version install different vars", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto& b_scf = vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file;
+    b_scf->core_paragraph->dependencies.push_back({"a", {}, parse_platform("!linux")});
+
+    auto& a_scf = vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file;
+    a_scf->core_paragraph->dependencies.push_back({"c", {}, parse_platform("linux")});
+
+    vp.emplace("c", {"1", 0}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+    var_provider.dep_info_vars[PackageSpec{"a", Test::X86_WINDOWS}] = {{"VCPKG_CMAKE_SYSTEM_NAME", "Linux"}};
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+    bp.v["c"] = {"1", 0};
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"b"}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 3);
+    check_name_and_version(install_plan.install_actions[0], "c", {"1", 0});
+    check_name_and_version(install_plan.install_actions[1], "a", {"1", 0});
+    check_name_and_version(install_plan.install_actions[2], "b", {"1", 0});
+}
+
+TEST_CASE ("version install qualified features", "[versionplan]")
+{
+    MockVersionedPortfileProvider vp;
+
+    auto& b_scf = vp.emplace("b", {"1", 0}, Scheme::Relaxed).source_control_file;
+    b_scf->core_paragraph->default_features.push_back("x");
+    b_scf->feature_paragraphs.push_back(make_fpgh("x"));
+    b_scf->feature_paragraphs.back()->dependencies.push_back({"a", {}, parse_platform("!linux")});
+
+    auto& a_scf = vp.emplace("a", {"1", 0}, Scheme::Relaxed).source_control_file;
+    a_scf->core_paragraph->default_features.push_back("y");
+    a_scf->feature_paragraphs.push_back(make_fpgh("y"));
+    a_scf->feature_paragraphs.back()->dependencies.push_back({"c", {}, parse_platform("linux")});
+
+    auto& c_scf = vp.emplace("c", {"1", 0}, Scheme::Relaxed).source_control_file;
+    c_scf->core_paragraph->default_features.push_back("z");
+    c_scf->feature_paragraphs.push_back(make_fpgh("z"));
+    c_scf->feature_paragraphs.back()->dependencies.push_back({"d", {}, parse_platform("linux")});
+
+    vp.emplace("d", {"1", 0}, Scheme::Relaxed);
+
+    MockCMakeVarProvider var_provider;
+    var_provider.dep_info_vars[PackageSpec{"a", Test::X86_WINDOWS}] = {{"VCPKG_CMAKE_SYSTEM_NAME", "Linux"}};
+
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+    bp.v["b"] = {"1", 0};
+    bp.v["c"] = {"1", 0};
+    bp.v["d"] = {"1", 0};
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"b"}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 3);
+    check_name_and_version(install_plan.install_actions[0], "c", {"1", 0}, {"z"});
+    check_name_and_version(install_plan.install_actions[1], "a", {"1", 0}, {"y"});
+    check_name_and_version(install_plan.install_actions[2], "b", {"1", 0}, {"x"});
+}
+
+TEST_CASE ("version install self features", "[versionplan]")
+{
+    MockBaselineProvider bp;
+    bp.v["a"] = {"1", 0};
+
+    MockVersionedPortfileProvider vp;
+    auto& a_scf = vp.emplace("a", {"1", 0}).source_control_file;
+    a_scf->feature_paragraphs.push_back(make_fpgh("x"));
+    a_scf->feature_paragraphs.back()->dependencies.push_back({"a", {"core", "y"}});
+    a_scf->feature_paragraphs.push_back(make_fpgh("y"));
+    a_scf->feature_paragraphs.push_back(make_fpgh("z"));
+
+    MockCMakeVarProvider var_provider;
+
+    auto install_plan =
+        unwrap(Dependencies::create_versioned_install_plan(vp, bp, var_provider, {{"a", {"x"}}}, {}, toplevel_spec()));
+
+    REQUIRE(install_plan.size() == 1);
+    check_name_and_version(install_plan.install_actions[0], "a", {"1", 0}, {"x", "y"});
+}
diff --git a/toolsrc/src/vcpkg-test/versionplan.cpp b/toolsrc/src/vcpkg-test/versionplan.cpp
new file mode 100644
index 000000000..2f82d21b4
--- /dev/null
+++ b/toolsrc/src/vcpkg-test/versionplan.cpp
@@ -0,0 +1,152 @@
+#include <catch2/catch.hpp>
+
+#include <vcpkg/dependencies.h>
+#include <vcpkg/paragraphparser.h>
+#include <vcpkg/portfileprovider.h>
+#include <vcpkg/sourceparagraph.h>
+
+#include <vcpkg-test/mockcmakevarprovider.h>
+#include <vcpkg-test/util.h>
+
+using namespace vcpkg;
+using namespace vcpkg::Parse;
+
+TEST_CASE ("parse depends", "[dependencies]")
+{
+    auto w = parse_dependencies_list("liba (windows)");
+    REQUIRE(w);
+    auto& v = *w.get();
+    REQUIRE(v.size() == 1);
+    REQUIRE(v.at(0).name == "liba");
+    REQUIRE(v.at(0).platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", ""}}));
+    REQUIRE(v.at(0).platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "WindowsStore"}}));
+    REQUIRE(!v.at(0).platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "Darwin"}}));
+}
+
+TEST_CASE ("filter depends", "[dependencies]")
+{
+    const std::unordered_map<std::string, std::string> x64_win_cmake_vars{{"VCPKG_TARGET_ARCHITECTURE", "x64"},
+                                                                          {"VCPKG_CMAKE_SYSTEM_NAME", ""}};
+
+    const std::unordered_map<std::string, std::string> arm_uwp_cmake_vars{{"VCPKG_TARGET_ARCHITECTURE", "arm"},
+                                                                          {"VCPKG_CMAKE_SYSTEM_NAME", "WindowsStore"}};
+
+    auto deps_ = parse_dependencies_list("liba (!uwp), libb, libc (uwp)");
+    REQUIRE(deps_);
+    auto& deps = *deps_.get();
+    auto v = filter_dependencies(deps, Test::X64_WINDOWS, x64_win_cmake_vars);
+    REQUIRE(v.size() == 2);
+    REQUIRE(v.at(0).package_spec.name() == "liba");
+    REQUIRE(v.at(1).package_spec.name() == "libb");
+
+    auto v2 = filter_dependencies(deps, Test::ARM_UWP, arm_uwp_cmake_vars);
+    REQUIRE(v.size() == 2);
+    REQUIRE(v2.at(0).package_spec.name() == "libb");
+    REQUIRE(v2.at(1).package_spec.name() == "libc");
+}
+
+TEST_CASE ("parse feature depends", "[dependencies]")
+{
+    auto u_ = parse_dependencies_list("libwebp[anim, gif2webp, img2webp, info, mux, nearlossless, "
+                                      "simd, cwebp, dwebp], libwebp[vwebp-sdl, extras] (!osx)");
+    REQUIRE(u_);
+    auto& v = *u_.get();
+    REQUIRE(v.size() == 2);
+    auto&& a0 = v.at(0);
+    REQUIRE(a0.name == "libwebp");
+    REQUIRE(a0.features.size() == 9);
+    REQUIRE(a0.platform.is_empty());
+
+    auto&& a1 = v.at(1);
+    REQUIRE(a1.name == "libwebp");
+    REQUIRE(a1.features.size() == 2);
+    REQUIRE(!a1.platform.is_empty());
+    REQUIRE(a1.platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", ""}}));
+    REQUIRE(a1.platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "Linux"}}));
+    REQUIRE_FALSE(a1.platform.evaluate({{"VCPKG_CMAKE_SYSTEM_NAME", "Darwin"}}));
+}
+
+TEST_CASE ("qualified dependency", "[dependencies]")
+{
+    using namespace Test;
+    PackageSpecMap spec_map;
+    auto spec_a = FullPackageSpec{spec_map.emplace("a", "b, b[b1] (linux)"), {}};
+    auto spec_b = FullPackageSpec{spec_map.emplace("b", "", {{"b1", ""}}), {}};
+
+    PortFileProvider::MapPortFileProvider map_port{spec_map.map};
+    MockCMakeVarProvider var_provider;
+
+    auto plan = vcpkg::Dependencies::create_feature_install_plan(map_port, var_provider, {spec_a}, {});
+    REQUIRE(plan.install_actions.size() == 2);
+    REQUIRE(plan.install_actions.at(0).feature_list == std::vector<std::string>{"core"});
+
+    FullPackageSpec linspec_a{{"a", Triplet::from_canonical_name("x64-linux")}, {}};
+    var_provider.dep_info_vars[linspec_a.package_spec].emplace("VCPKG_CMAKE_SYSTEM_NAME", "Linux");
+    auto plan2 = vcpkg::Dependencies::create_feature_install_plan(map_port, var_provider, {linspec_a}, {});
+    REQUIRE(plan2.install_actions.size() == 2);
+    REQUIRE(plan2.install_actions.at(0).feature_list == std::vector<std::string>{"b1", "core"});
+}
+
+TEST_CASE ("resolve_deps_as_top_level", "[dependencies]")
+{
+    using namespace Test;
+    PackageSpecMap spec_map;
+    FullPackageSpec spec_a{spec_map.emplace("a", "b, b[b1] (linux)"), {}};
+    FullPackageSpec spec_b{spec_map.emplace("b", "", {{"b1", ""}}), {}};
+    FullPackageSpec spec_c{spec_map.emplace("c", "b", {{"c1", "b[b1]"}, {"c2", "c[c1], a"}}, {"c1"}), {"core"}};
+    FullPackageSpec spec_d{spec_map.emplace("d", "c[core]"), {}};
+
+    PortFileProvider::MapPortFileProvider map_port{spec_map.map};
+    MockCMakeVarProvider var_provider;
+    Triplet t_linux = Triplet::from_canonical_name("x64-linux");
+    var_provider.dep_info_vars[{"a", t_linux}].emplace("VCPKG_CMAKE_SYSTEM_NAME", "Linux");
+    {
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("a").source_control_file, Test::X86_WINDOWS, {}, var_provider);
+        REQUIRE(deps.size() == 1);
+        REQUIRE(deps.at(0) == spec_b);
+    }
+    {
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("a").source_control_file, t_linux, {}, var_provider);
+        REQUIRE(deps.size() == 1);
+        REQUIRE(deps.at(0) == FullPackageSpec({"b", t_linux}, {"b1"}));
+    }
+    {
+        // without defaults
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {}, var_provider);
+        REQUIRE(deps.size() == 1);
+        REQUIRE(deps.at(0) == spec_b);
+    }
+    FullPackageSpec spec_b_with_b1{spec_b.package_spec, {"b1"}};
+    {
+        // with defaults of c (c1)
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {"default"}, var_provider);
+        REQUIRE(deps.size() == 1);
+        REQUIRE(deps.at(0) == spec_b_with_b1);
+    }
+    {
+        // with c1
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {"c1"}, var_provider);
+        REQUIRE(deps.size() == 1);
+        REQUIRE(deps.at(0) == spec_b_with_b1);
+    }
+    {
+        // with c2 implying c1
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("c").source_control_file, Test::X86_WINDOWS, {"c2"}, var_provider);
+        REQUIRE(deps.size() == 2);
+        REQUIRE(deps.at(0) == spec_a);
+        REQUIRE(deps.at(1) == spec_b_with_b1);
+    }
+    {
+        // d -> c[core]
+        auto deps = vcpkg::Dependencies::resolve_deps_as_top_level(
+            *spec_map.map.at("d").source_control_file, Test::X86_WINDOWS, {}, var_provider);
+        REQUIRE(deps.size() == 1);
+        REQUIRE(deps.at(0) == spec_c);
+    }
+}
diff --git a/toolsrc/src/vcpkg/dependencies.cpp b/toolsrc/src/vcpkg/dependencies.cpp
index 75509343a..117a05209 100644
--- a/toolsrc/src/vcpkg/dependencies.cpp
+++ b/toolsrc/src/vcpkg/dependencies.cpp
@@ -628,7 +628,7 @@ namespace vcpkg::Dependencies
         auto ctx = [&]() -> const PlatformExpression::Context& {
             if (!ctx_storage)
             {
-                var_provider.load_dep_info_vars({{spec}});
+                var_provider.load_dep_info_vars({&spec, 1});
                 ctx_storage = var_provider.get_dep_info_vars(spec);
             }
             return ctx_storage.value_or_exit(VCPKG_LINE_INFO);
@@ -1157,4 +1157,662 @@ namespace vcpkg::Dependencies
             Checks::exit_fail(VCPKG_LINE_INFO);
         }
     }
+
+    namespace
+    {
+        struct VersionedPackageGraph
+        {
+        private:
+            using IVersionedPortfileProvider = PortFileProvider::IVersionedPortfileProvider;
+            using IBaselineProvider = PortFileProvider::IBaselineProvider;
+
+        public:
+            VersionedPackageGraph(const IVersionedPortfileProvider& ver_provider,
+                                  const IBaselineProvider& base_provider,
+                                  const CMakeVars::CMakeVarProvider& var_provider)
+                : m_ver_provider(ver_provider), m_base_provider(base_provider), m_var_provider(var_provider)
+            {
+            }
+
+            void add_override(const std::string& name, const Versions::Version& v);
+
+            void add_roots(View<Dependency> dep, const PackageSpec& toplevel);
+
+            ExpectedS<ActionPlan> finalize_extract_plan();
+
+        private:
+            const IVersionedPortfileProvider& m_ver_provider;
+            const IBaselineProvider& m_base_provider;
+            const CMakeVars::CMakeVarProvider& m_var_provider;
+
+            struct DepSpec
+            {
+                PackageSpec spec;
+                Versions::Version ver;
+                std::vector<std::string> features;
+            };
+
+            // This object contains the current version within a given column.
+            // Each "string" scheme text is treated as a separate column
+            // "relaxed" versions all share the same column
+            struct VersionSchemeInfo
+            {
+                const SourceControlFileLocation* scfl = nullptr;
+                Versions::Version version;
+                // This tracks a list of constraint sources for debugging purposes
+                std::vector<std::string> origins;
+                std::map<std::string, std::vector<FeatureSpec>> deps;
+
+                bool is_less_than(const Versions::Version& new_ver) const;
+            };
+
+            struct PackageNode : Util::MoveOnlyBase
+            {
+                std::map<Versions::Version, VersionSchemeInfo*, VersionTMapLess> vermap;
+                std::map<std::string, VersionSchemeInfo> exacts;
+                Optional<std::unique_ptr<VersionSchemeInfo>> relaxed;
+                std::set<std::string> features;
+                bool default_features = true;
+
+                VersionSchemeInfo* get_node(const Versions::Version& ver);
+                VersionSchemeInfo& emplace_node(Versions::Scheme scheme, const Versions::Version& ver);
+            };
+
+            std::vector<DepSpec> m_roots;
+            std::map<std::string, Versions::Version> m_overrides;
+            std::map<PackageSpec, PackageNode> m_graph;
+
+            std::pair<const PackageSpec, PackageNode>& emplace_package(const PackageSpec& spec);
+
+            void add_constraint(std::pair<const PackageSpec, PackageNode>& ref,
+                                const Dependency& dep,
+                                const std::string& origin);
+            void add_constraint(std::pair<const PackageSpec, PackageNode>& ref,
+                                const Versions::Version& ver,
+                                const std::string& origin);
+            void add_constraint(std::pair<const PackageSpec, PackageNode>& ref,
+                                const std::string& feature,
+                                const std::string& origin);
+
+            void add_constraint_default_features(std::pair<const PackageSpec, PackageNode>& ref,
+                                                 const std::string& origin);
+
+            void add_feature_to(std::pair<const PackageSpec, PackageNode>& ref,
+                                VersionSchemeInfo& vsi,
+                                const std::string& feature);
+
+            std::vector<std::string> m_errors;
+        };
+
+        VersionedPackageGraph::VersionSchemeInfo& VersionedPackageGraph::PackageNode::emplace_node(
+            Versions::Scheme scheme, const Versions::Version& ver)
+        {
+            auto it = vermap.find(ver);
+            if (it != vermap.end()) return *it->second;
+
+            VersionSchemeInfo* vsi = nullptr;
+            if (scheme == Versions::Scheme::String)
+            {
+                vsi = &exacts[ver.text()];
+            }
+            else if (scheme == Versions::Scheme::Relaxed)
+            {
+                if (auto p = relaxed.get())
+                {
+                    vsi = p->get();
+                }
+                else
+                {
+                    relaxed = std::make_unique<VersionSchemeInfo>();
+                    vsi = relaxed.get()->get();
+                }
+            }
+            else
+            {
+                // not implemented
+                Checks::unreachable(VCPKG_LINE_INFO);
+            }
+            vermap.emplace(ver, vsi);
+            return *vsi;
+        }
+
+        VersionedPackageGraph::VersionSchemeInfo* VersionedPackageGraph::PackageNode::get_node(
+            const Versions::Version& ver)
+        {
+            auto it = vermap.find(ver);
+            return it == vermap.end() ? nullptr : it->second;
+        }
+
+        enum class VerComp
+        {
+            unk,
+            lt,
+            eq,
+            gt,
+        };
+        static VerComp compare_versions(Versions::Scheme sa,
+                                        const Versions::Version& a,
+                                        Versions::Scheme sb,
+                                        const Versions::Version& b)
+        {
+            if (sa != sb) return VerComp::unk;
+            switch (sa)
+            {
+                case Versions::Scheme::String:
+                {
+                    if (a.text() != b.text()) return VerComp::unk;
+                    if (a.port_version() < b.port_version()) return VerComp::lt;
+                    if (a.port_version() > b.port_version()) return VerComp::gt;
+                    return VerComp::eq;
+                }
+                case Versions::Scheme::Relaxed:
+                {
+                    auto i1 = atoi(a.text().c_str());
+                    auto i2 = atoi(b.text().c_str());
+                    if (i1 < i2) return VerComp::lt;
+                    if (i1 > i2) return VerComp::gt;
+                    if (a.port_version() < b.port_version()) return VerComp::lt;
+                    if (a.port_version() > b.port_version()) return VerComp::gt;
+                    return VerComp::eq;
+                }
+                default: Checks::unreachable(VCPKG_LINE_INFO);
+            }
+        }
+
+        bool VersionedPackageGraph::VersionSchemeInfo::is_less_than(const Versions::Version& new_ver) const
+        {
+            Checks::check_exit(VCPKG_LINE_INFO, scfl);
+            ASSUME(scfl != nullptr);
+            auto scheme = scfl->source_control_file->core_paragraph->version_scheme;
+            auto r = compare_versions(scheme, version, scheme, new_ver);
+            Checks::check_exit(VCPKG_LINE_INFO, r != VerComp::unk);
+            return r == VerComp::lt;
+        }
+
+        Versions::Version to_version(const SourceControlFile& scf)
+        {
+            return {
+                scf.core_paragraph->version,
+                scf.core_paragraph->port_version,
+            };
+        }
+        Optional<Versions::Version> to_version(const DependencyConstraint& dc)
+        {
+            if (dc.type == Versions::Constraint::Type::None)
+            {
+                return nullopt;
+            }
+            else
+            {
+                return Versions::Version{
+                    dc.value,
+                    dc.port_version,
+                };
+            }
+        }
+
+        void VersionedPackageGraph::add_feature_to(std::pair<const PackageSpec, PackageNode>& ref,
+                                                   VersionSchemeInfo& vsi,
+                                                   const std::string& feature)
+        {
+            auto deps = vsi.scfl->source_control_file->find_dependencies_for_feature(feature);
+            if (!deps)
+            {
+                // This version doesn't have this feature. This may result in an error during finalize if the
+                // constraint is not removed via upgrades.
+                return;
+            }
+            auto p = vsi.deps.emplace(feature, std::vector<FeatureSpec>{});
+            if (!p.second)
+            {
+                // This feature has already been handled
+                return;
+            }
+
+            for (auto&& dep : *deps.get())
+            {
+                PackageSpec dep_spec(dep.name, ref.first.triplet());
+
+                if (!dep.platform.is_empty())
+                {
+                    auto maybe_vars = m_var_provider.get_dep_info_vars(ref.first);
+                    if (!maybe_vars)
+                    {
+                        m_var_provider.load_dep_info_vars({&ref.first, 1});
+                        maybe_vars = m_var_provider.get_dep_info_vars(ref.first);
+                    }
+
+                    if (!dep.platform.evaluate(maybe_vars.value_or_exit(VCPKG_LINE_INFO)))
+                    {
+                        continue;
+                    }
+                }
+
+                auto& dep_node = emplace_package(dep_spec);
+                // Todo: cycle detection
+                add_constraint(dep_node, dep, ref.first.name());
+
+                p.first->second.emplace_back(dep_spec, "core");
+                for (auto&& f : dep.features)
+                {
+                    p.first->second.emplace_back(dep_spec, f);
+                }
+            }
+        }
+
+        void VersionedPackageGraph::add_constraint_default_features(std::pair<const PackageSpec, PackageNode>& ref,
+                                                                    const std::string& origin)
+        {
+            (void)origin;
+            if (!ref.second.default_features)
+            {
+                ref.second.default_features = true;
+
+                if (auto relaxed = ref.second.relaxed.get())
+                {
+                    for (auto&& f : relaxed->get()->scfl->source_control_file->core_paragraph->default_features)
+                    {
+                        add_feature_to(ref, **relaxed, f);
+                    }
+                }
+                for (auto&& vsi : ref.second.exacts)
+                {
+                    for (auto&& f : vsi.second.scfl->source_control_file->core_paragraph->default_features)
+                    {
+                        add_feature_to(ref, vsi.second, f);
+                    }
+                }
+            }
+        }
+
+        void VersionedPackageGraph::add_constraint(std::pair<const PackageSpec, PackageNode>& ref,
+                                                   const Dependency& dep,
+                                                   const std::string& origin)
+        {
+            auto base_ver = m_base_provider.get_baseline_version(dep.name);
+            auto dep_ver = to_version(dep.constraint);
+
+            if (auto dv = dep_ver.get())
+            {
+                add_constraint(ref, *dv, origin);
+            }
+
+            if (auto bv = base_ver.get())
+            {
+                add_constraint(ref, *bv, origin);
+            }
+
+            for (auto&& f : dep.features)
+            {
+                add_constraint(ref, f, origin);
+            }
+        }
+        void VersionedPackageGraph::add_constraint(std::pair<const PackageSpec, PackageNode>& ref,
+                                                   const Versions::Version& version,
+                                                   const std::string& origin)
+        {
+            auto over_it = m_overrides.find(ref.first.name());
+            if (over_it != m_overrides.end() && over_it->second != version)
+            {
+                return add_constraint(ref, over_it->second, origin);
+            }
+            auto maybe_scfl = m_ver_provider.get_control_file({ref.first.name(), version});
+
+            if (auto p_scfl = maybe_scfl.get())
+            {
+                auto& exact_ref =
+                    ref.second.emplace_node(p_scfl->source_control_file->core_paragraph->version_scheme, version);
+                exact_ref.origins.push_back(origin);
+
+                bool replace;
+                if (exact_ref.scfl == nullptr)
+                {
+                    replace = true;
+                }
+                else if (exact_ref.scfl == p_scfl)
+                {
+                    replace = false;
+                }
+                else
+                {
+                    replace = exact_ref.is_less_than(version);
+                }
+
+                if (replace)
+                {
+                    exact_ref.scfl = p_scfl;
+                    exact_ref.version = to_version(*p_scfl->source_control_file);
+                    exact_ref.deps.clear();
+
+                    add_feature_to(ref, exact_ref, "core");
+
+                    for (auto&& f : ref.second.features)
+                    {
+                        add_feature_to(ref, exact_ref, f);
+                    }
+
+                    if (ref.second.default_features)
+                    {
+                        for (auto&& f : p_scfl->source_control_file->core_paragraph->default_features)
+                        {
+                            add_feature_to(ref, exact_ref, f);
+                        }
+                    }
+                }
+            }
+            else
+            {
+                m_errors.push_back(maybe_scfl.error());
+            }
+        }
+
+        void VersionedPackageGraph::add_constraint(std::pair<const PackageSpec, PackageNode>& ref,
+                                                   const std::string& feature,
+                                                   const std::string& origin)
+        {
+            auto inserted = ref.second.features.emplace(feature).second;
+            if (inserted)
+            {
+                if (auto relaxed = ref.second.relaxed.get())
+                {
+                    add_feature_to(ref, **relaxed, feature);
+                }
+                for (auto&& vsi : ref.second.exacts)
+                {
+                    add_feature_to(ref, vsi.second, feature);
+                }
+            }
+            (void)origin;
+        }
+
+        std::pair<const PackageSpec, VersionedPackageGraph::PackageNode>& VersionedPackageGraph::emplace_package(
+            const PackageSpec& spec)
+        {
+            return *m_graph.emplace(spec, PackageNode{}).first;
+        }
+
+        static Optional<Versions::Version> dep_to_version(const std::string& name,
+                                                          const DependencyConstraint& dc,
+                                                          const PortFileProvider::IBaselineProvider& base_provider)
+        {
+            auto maybe_cons = to_version(dc);
+            if (maybe_cons)
+            {
+                return maybe_cons;
+            }
+            else
+            {
+                return base_provider.get_baseline_version(name);
+            }
+        }
+
+        void VersionedPackageGraph::add_override(const std::string& name, const Versions::Version& v)
+        {
+            m_overrides.emplace(name, v);
+        }
+
+        void VersionedPackageGraph::add_roots(View<Dependency> deps, const PackageSpec& toplevel)
+        {
+            auto specs = Util::fmap(deps, [&toplevel](const Dependency& d) {
+                return PackageSpec{d.name, toplevel.triplet()};
+            });
+            specs.push_back(toplevel);
+            Util::sort_unique_erase(specs);
+            m_var_provider.load_dep_info_vars(specs);
+            const auto& vars = m_var_provider.get_dep_info_vars(toplevel).value_or_exit(VCPKG_LINE_INFO);
+            std::vector<const Dependency*> active_deps;
+
+            for (auto&& dep : deps)
+            {
+                PackageSpec spec(dep.name, toplevel.triplet());
+                if (!dep.platform.evaluate(vars)) continue;
+
+                active_deps.push_back(&dep);
+
+                // Disable default features for deps with [core] as a dependency
+                // Note: x[core], x[y] will still eventually depend on defaults due to the second x[y]
+                if (Util::find(dep.features, "core") != dep.features.end())
+                {
+                    auto& node = emplace_package(spec);
+                    node.second.default_features = false;
+                }
+            }
+
+            for (auto pdep : active_deps)
+            {
+                const auto& dep = *pdep;
+                PackageSpec spec(dep.name, toplevel.triplet());
+
+                auto& node = emplace_package(spec);
+
+                auto over_it = m_overrides.find(dep.name);
+                if (over_it != m_overrides.end())
+                {
+                    m_roots.push_back(DepSpec{spec, over_it->second, dep.features});
+                    add_constraint(node, over_it->second, toplevel.name());
+                    continue;
+                }
+
+                auto dep_ver = to_version(dep.constraint);
+                auto base_ver = m_base_provider.get_baseline_version(dep.name);
+                if (auto p_dep_ver = dep_ver.get())
+                {
+                    m_roots.push_back(DepSpec{spec, *p_dep_ver, dep.features});
+                    if (auto p_base_ver = base_ver.get())
+                    {
+                        // Compare version constraint with baseline to only evaluate the "tighter" constraint
+                        auto dep_scfl = m_ver_provider.get_control_file({dep.name, *p_dep_ver});
+                        auto base_scfl = m_ver_provider.get_control_file({dep.name, *p_base_ver});
+                        if (dep_scfl && base_scfl)
+                        {
+                            auto r =
+                                compare_versions(dep_scfl.get()->source_control_file->core_paragraph->version_scheme,
+                                                 *p_dep_ver,
+                                                 base_scfl.get()->source_control_file->core_paragraph->version_scheme,
+                                                 *p_base_ver);
+                            if (r == VerComp::lt)
+                            {
+                                add_constraint(node, *p_base_ver, "baseline");
+                                add_constraint(node, *p_dep_ver, toplevel.name());
+                            }
+                            else
+                            {
+                                add_constraint(node, *p_dep_ver, toplevel.name());
+                                add_constraint(node, *p_base_ver, "baseline");
+                            }
+                        }
+                        else
+                        {
+                            if (!dep_scfl) m_errors.push_back(dep_scfl.error());
+                            if (!base_scfl) m_errors.push_back(base_scfl.error());
+                        }
+                    }
+                    else
+                    {
+                        add_constraint(node, *p_dep_ver, toplevel.name());
+                    }
+                }
+                else if (auto p_base_ver = base_ver.get())
+                {
+                    m_roots.push_back(DepSpec{spec, *p_base_ver, dep.features});
+                    add_constraint(node, *p_base_ver, toplevel.name());
+                }
+                else
+                {
+                    m_errors.push_back(Strings::concat("Cannot resolve unversioned dependency from top-level to ",
+                                                       dep.name,
+                                                       " without a baseline entry or override."));
+                }
+
+                for (auto&& f : dep.features)
+                {
+                    add_constraint(node, f, toplevel.name());
+                }
+                if (Util::find(dep.features, "core") == dep.features.end())
+                {
+                    add_constraint_default_features(node, toplevel.name());
+                }
+            }
+        }
+
+        ExpectedS<ActionPlan> VersionedPackageGraph::finalize_extract_plan()
+        {
+            if (m_errors.size() > 0)
+            {
+                return Strings::join("\n", m_errors);
+            }
+
+            ActionPlan ret;
+
+            // second == nullptr means "in progress"
+            std::map<PackageSpec, VersionSchemeInfo*> emitted;
+            struct Frame
+            {
+                InstallPlanAction ipa;
+                std::vector<DepSpec> deps;
+            };
+            std::vector<Frame> stack;
+
+            auto push = [&emitted, this, &stack](const PackageSpec& spec,
+                                                 const Versions::Version& new_ver) -> Optional<std::string> {
+                auto&& node = m_graph[spec];
+                auto over_it = m_overrides.find(spec.name());
+
+                VersionedPackageGraph::VersionSchemeInfo* p_vnode;
+                if (over_it != m_overrides.end())
+                    p_vnode = node.get_node(over_it->second);
+                else
+                    p_vnode = node.get_node(new_ver);
+
+                if (!p_vnode) return Strings::concat("Version was not found during discovery: ", spec, "@", new_ver);
+
+                auto p = emitted.emplace(spec, nullptr);
+                if (p.second)
+                {
+                    // Newly inserted
+                    if (over_it == m_overrides.end())
+                    {
+                        // Not overridden -- Compare against baseline
+                        if (auto baseline = m_base_provider.get_baseline_version(spec.name()))
+                        {
+                            if (auto base_node = node.get_node(*baseline.get()))
+                            {
+                                if (base_node != p_vnode)
+                                {
+                                    return Strings::concat("Version conflict on ",
+                                                           spec.name(),
+                                                           "@",
+                                                           new_ver,
+                                                           ": baseline required ",
+                                                           *baseline.get());
+                                }
+                            }
+                        }
+                    }
+
+                    // -> Add stack frame
+                    auto maybe_vars = m_var_provider.get_dep_info_vars(spec);
+
+                    InstallPlanAction ipa(spec, *p_vnode->scfl, RequestType::USER_REQUESTED, std::move(p_vnode->deps));
+                    std::vector<DepSpec> deps;
+                    for (auto&& f : ipa.feature_list)
+                    {
+                        if (auto maybe_deps =
+                                p_vnode->scfl->source_control_file->find_dependencies_for_feature(f).get())
+                        {
+                            for (auto&& dep : *maybe_deps)
+                            {
+                                if (dep.name == spec.name()) continue;
+
+                                if (!dep.platform.is_empty() &&
+                                    !dep.platform.evaluate(maybe_vars.value_or_exit(VCPKG_LINE_INFO)))
+                                {
+                                    continue;
+                                }
+                                auto maybe_cons = dep_to_version(dep.name, dep.constraint, m_base_provider);
+
+                                if (auto cons = maybe_cons.get())
+                                {
+                                    deps.emplace_back(DepSpec{{dep.name, spec.triplet()}, std::move(*cons)});
+                                }
+                                else
+                                {
+                                    return Strings::concat("Cannot resolve unconstrained dependency from ",
+                                                           spec.name(),
+                                                           " to ",
+                                                           dep.name,
+                                                           " without a baseline entry or override.");
+                                }
+                            }
+                        }
+                    }
+                    stack.push_back(Frame{std::move(ipa), std::move(deps)});
+                    return nullopt;
+                }
+                else
+                {
+                    // spec already present in map
+                    if (p.first->second == nullptr)
+                    {
+                        return Strings::concat(
+                            "Cycle detected during ",
+                            spec,
+                            ":\n",
+                            Strings::join("\n", stack, [](const auto& p) -> const PackageSpec& { return p.ipa.spec; }));
+                    }
+                    else if (p.first->second != p_vnode)
+                    {
+                        // comparable versions should retrieve the same info node
+                        return Strings::concat(
+                            "Version conflict on ", spec.name(), "@", p.first->second->version, ": required ", new_ver);
+                    }
+                    return nullopt;
+                }
+            };
+
+            for (auto&& root : m_roots)
+            {
+                if (auto err = push(root.spec, root.ver))
+                {
+                    return std::move(*err.get());
+                }
+
+                while (stack.size() > 0)
+                {
+                    auto& back = stack.back();
+                    if (back.deps.empty())
+                    {
+                        emitted[back.ipa.spec] = m_graph[back.ipa.spec].get_node(
+                            to_version(*back.ipa.source_control_file_location.get()->source_control_file));
+                        ret.install_actions.push_back(std::move(back.ipa));
+                        stack.pop_back();
+                    }
+                    else
+                    {
+                        auto dep = std::move(back.deps.back());
+                        back.deps.pop_back();
+                        if (auto err = push(dep.spec, dep.ver))
+                        {
+                            return std::move(*err.get());
+                        }
+                    }
+                }
+            }
+            return ret;
+        }
+    }
+
+    ExpectedS<ActionPlan> create_versioned_install_plan(const PortFileProvider::IVersionedPortfileProvider& provider,
+                                                        const PortFileProvider::IBaselineProvider& bprovider,
+                                                        const CMakeVars::CMakeVarProvider& var_provider,
+                                                        const std::vector<Dependency>& deps,
+                                                        const std::vector<DependencyOverride>& overrides,
+                                                        const PackageSpec& toplevel)
+    {
+        VersionedPackageGraph vpg(provider, bprovider, var_provider);
+        for (auto&& o : overrides)
+            vpg.add_override(o.name, {o.version, o.port_version});
+        vpg.add_roots(deps, toplevel);
+        return vpg.finalize_extract_plan();
+    }
 }
diff --git a/toolsrc/src/vcpkg/packagespec.cpp b/toolsrc/src/vcpkg/packagespec.cpp
index a40d30340..3f35e118e 100644
--- a/toolsrc/src/vcpkg/packagespec.cpp
+++ b/toolsrc/src/vcpkg/packagespec.cpp
@@ -273,6 +273,7 @@ namespace vcpkg
         if (lhs.features != rhs.features) return false;
         if (!structurally_equal(lhs.platform, rhs.platform)) return false;
         if (lhs.extra_info != rhs.extra_info) return false;
+        if (lhs.constraint != rhs.constraint) return false;
 
         return true;
     }
diff --git a/toolsrc/src/vcpkg/portfileprovider.cpp b/toolsrc/src/vcpkg/portfileprovider.cpp
index e3053bfa6..3f4640c97 100644
--- a/toolsrc/src/vcpkg/portfileprovider.cpp
+++ b/toolsrc/src/vcpkg/portfileprovider.cpp
@@ -370,7 +370,7 @@ namespace vcpkg::PortFileProvider
         auto port = port_name.to_string();
         for (auto&& version_entry : version_entries)
         {
-            VersionSpec spec(port, version_entry.version, version_entry.scheme);
+            VersionSpec spec(port, version_entry.version);
             m_impl->versions_cache[port].push_back(spec);
             m_impl->git_tree_cache.emplace(std::move(spec), std::move(version_entry.git_tree));
         }
diff --git a/toolsrc/src/vcpkg/versions.cpp b/toolsrc/src/vcpkg/versions.cpp
index ac1829712..7f19813ec 100644
--- a/toolsrc/src/vcpkg/versions.cpp
+++ b/toolsrc/src/vcpkg/versions.cpp
@@ -2,22 +2,19 @@
 
 namespace vcpkg::Versions
 {
-    VersionSpec::VersionSpec(const std::string& port_name, const VersionT& version, Scheme scheme)
-        : port_name(port_name), version(version), scheme(scheme)
+    VersionSpec::VersionSpec(const std::string& port_name, const VersionT& version)
+        : port_name(port_name), version(version)
     {
     }
 
-    VersionSpec::VersionSpec(const std::string& port_name,
-                             const std::string& version_string,
-                             int port_version,
-                             Scheme scheme)
-        : port_name(port_name), version(version_string, port_version), scheme(scheme)
+    VersionSpec::VersionSpec(const std::string& port_name, const std::string& version_string, int port_version)
+        : port_name(port_name), version(version_string, port_version)
     {
     }
 
     bool operator==(const VersionSpec& lhs, const VersionSpec& rhs)
     {
-        return std::tie(lhs.port_name, lhs.version, lhs.scheme) == std::tie(rhs.port_name, rhs.version, rhs.scheme);
+        return std::tie(lhs.port_name, lhs.version) == std::tie(rhs.port_name, rhs.version);
     }
 
     bool operator!=(const VersionSpec& lhs, const VersionSpec& rhs) { return !(lhs == rhs); }
@@ -28,7 +25,6 @@ namespace vcpkg::Versions
         using std::size_t;
         using std::string;
 
-        return ((hash<string>()(key.port_name) ^ (hash<string>()(key.version.to_string()) << 1)) >> 1) ^
-               (hash<int>()(static_cast<int>(key.scheme)) << 1);
+        return hash<string>()(key.port_name) ^ (hash<string>()(key.version.to_string()) >> 1);
     }
 }
\ No newline at end of file
diff --git a/toolsrc/src/vcpkg/versiont.cpp b/toolsrc/src/vcpkg/versiont.cpp
index 885312307..09dabb450 100644
--- a/toolsrc/src/vcpkg/versiont.cpp
+++ b/toolsrc/src/vcpkg/versiont.cpp
@@ -4,24 +4,28 @@
 
 namespace vcpkg
 {
-    VersionT::VersionT() noexcept : value("0.0.0"), port_version(0) { }
-    VersionT::VersionT(std::string&& value, int port_version) : value(std::move(value)), port_version(port_version) { }
-    VersionT::VersionT(const std::string& value, int port_version) : value(value), port_version(port_version) { }
+    VersionT::VersionT() noexcept : m_text("0.0.0"), m_port_version(0) { }
+    VersionT::VersionT(std::string&& value, int port_version) : m_text(std::move(value)), m_port_version(port_version)
+    {
+    }
+    VersionT::VersionT(const std::string& value, int port_version) : m_text(value), m_port_version(port_version) { }
 
-    std::string VersionT::to_string() const
+    std::string VersionT::to_string() const { return Strings::concat(*this); }
+    void VersionT::to_string(std::string& out) const
     {
-        return port_version == 0 ? value : Strings::format("%s#%d", value, port_version);
+        out.append(m_text);
+        if (m_port_version) Strings::append(out, '#', m_port_version);
     }
 
     bool operator==(const VersionT& left, const VersionT& right)
     {
-        return left.port_version == right.port_version && left.value == right.value;
+        return left.m_port_version == right.m_port_version && left.m_text == right.m_text;
     }
     bool operator!=(const VersionT& left, const VersionT& right) { return !(left == right); }
 
     bool VersionTMapLess::operator()(const VersionT& left, const VersionT& right) const
     {
-        auto cmp = left.value.compare(right.value);
+        auto cmp = left.m_text.compare(right.m_text);
         if (cmp < 0)
         {
             return true;
@@ -31,7 +35,7 @@ namespace vcpkg
             return false;
         }
 
-        return left.port_version < right.port_version;
+        return left.m_port_version < right.m_port_version;
     }
 
     VersionDiff::VersionDiff() noexcept : left(), right() { }