[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>

6 files changed, 30 insertions, 9 deletions

diff --git a/toolsrc/include/vcpkg-test/mockcmakevarprovider.h b/toolsrc/include/vcpkg-test/mockcmakevarprovider.h
index 15b24b8d0..6017457b6 100644
--- a/toolsrc/include/vcpkg-test/mockcmakevarprovider.h
+++ b/toolsrc/include/vcpkg-test/mockcmakevarprovider.h
@@ -6,19 +6,23 @@ namespace vcpkg::Test
 {
     struct MockCMakeVarProvider : CMakeVars::CMakeVarProvider
     {
-        void load_generic_triplet_vars(Triplet triplet) const override { generic_triplet_vars[triplet] = {}; }
+        using SMap = std::unordered_map<std::string, std::string>;
+        void load_generic_triplet_vars(Triplet triplet) const override
+        {
+            generic_triplet_vars.emplace(triplet, SMap{});
+        }
 
         void load_dep_info_vars(Span<const PackageSpec> specs) const override
         {
             for (auto&& spec : specs)
-                dep_info_vars[spec] = {};
+                dep_info_vars.emplace(spec, SMap{});
         }
 
         void load_tag_vars(Span<const FullPackageSpec> specs,
                            const PortFileProvider::PortFileProvider& port_provider) const override
         {
             for (auto&& spec : specs)
-                tag_vars[spec.package_spec] = {};
+                tag_vars.emplace(spec.package_spec, SMap{});
             (void)(port_provider);
         }
 
diff --git a/toolsrc/include/vcpkg/dependencies.h b/toolsrc/include/vcpkg/dependencies.h
index 1ea81c185..f4e061b03 100644
--- a/toolsrc/include/vcpkg/dependencies.h
+++ b/toolsrc/include/vcpkg/dependencies.h
@@ -173,5 +173,15 @@ namespace vcpkg::Dependencies
                                                            std::vector<std::string> features,
                                                            CMakeVars::CMakeVarProvider& var_provider);
 
+    /// <param name="provider">Contains the ports of the current environment.</param>
+    /// <param name="specs">Feature specifications to resolve dependencies for.</param>
+    /// <param name="status_db">Status of installed packages in the current environment.</param>
+    ExpectedS<ActionPlan> create_versioned_install_plan(const PortFileProvider::IVersionedPortfileProvider& vprovider,
+                                                        const PortFileProvider::IBaselineProvider& bprovider,
+                                                        const CMakeVars::CMakeVarProvider& var_provider,
+                                                        const std::vector<Dependency>& deps,
+                                                        const std::vector<DependencyOverride>& overrides,
+                                                        const PackageSpec& toplevel);
+
     void print_plan(const ActionPlan& action_plan, const bool is_recursive = true, const fs::path& vcpkg_root_dir = {});
 }
diff --git a/toolsrc/include/vcpkg/fwd/portfileprovider.h b/toolsrc/include/vcpkg/fwd/portfileprovider.h
index 08cce1324..dc381eb92 100644
--- a/toolsrc/include/vcpkg/fwd/portfileprovider.h
+++ b/toolsrc/include/vcpkg/fwd/portfileprovider.h
@@ -4,4 +4,6 @@ namespace vcpkg::PortFileProvider
 {
     struct PortFileProvider;
     struct PathsPortFileProvider;
+    struct IVersionedPortfileProvider;
+    struct IBaselineProvider;
 }
diff --git a/toolsrc/include/vcpkg/packagespec.h b/toolsrc/include/vcpkg/packagespec.h
index d45fb0182..43be57e68 100644
--- a/toolsrc/include/vcpkg/packagespec.h
+++ b/toolsrc/include/vcpkg/packagespec.h
@@ -163,9 +163,9 @@ namespace vcpkg
     struct DependencyOverride
     {
         std::string name;
-        Versions::Scheme version_scheme = Versions::Scheme::String;
         std::string version;
         int port_version = 0;
+        Versions::Scheme version_scheme = Versions::Scheme::String;
 
         Json::Object extra_info;
 
diff --git a/toolsrc/include/vcpkg/versions.h b/toolsrc/include/vcpkg/versions.h
index 7d5b573c2..09df15366 100644
--- a/toolsrc/include/vcpkg/versions.h
+++ b/toolsrc/include/vcpkg/versions.h
@@ -4,6 +4,8 @@
 
 namespace vcpkg::Versions
 {
+    using Version = VersionT;
+
     enum class Scheme
     {
         Relaxed,
@@ -16,11 +18,10 @@ namespace vcpkg::Versions
     {
         std::string port_name;
         VersionT version;
-        Scheme scheme;
 
-        VersionSpec(const std::string& port_name, const VersionT& version, Scheme scheme);
+        VersionSpec(const std::string& port_name, const VersionT& version);
 
-        VersionSpec(const std::string& port_name, const std::string& version_string, int port_version, Scheme scheme);
+        VersionSpec(const std::string& port_name, const std::string& version_string, int port_version);
 
         friend bool operator==(const VersionSpec& lhs, const VersionSpec& rhs);
         friend bool operator!=(const VersionSpec& lhs, const VersionSpec& rhs);
diff --git a/toolsrc/include/vcpkg/versiont.h b/toolsrc/include/vcpkg/versiont.h
index 506d7090a..7819f9875 100644
--- a/toolsrc/include/vcpkg/versiont.h
+++ b/toolsrc/include/vcpkg/versiont.h
@@ -11,15 +11,19 @@ namespace vcpkg
         VersionT(const std::string& value, int port_version);
 
         std::string to_string() const;
+        void to_string(std::string& out) const;
 
         friend bool operator==(const VersionT& left, const VersionT& right);
         friend bool operator!=(const VersionT& left, const VersionT& right);
 
         friend struct VersionTMapLess;
 
+        const std::string text() const { return m_text; }
+        int port_version() const { return m_port_version; }
+
     private:
-        std::string value;
-        int port_version;
+        std::string m_text;
+        int m_port_version;
     };
 
     struct VersionDiff