Major refactor/rework of dependency resolution

6 files changed, 153 insertions, 123 deletions

diff --git a/toolsrc/include/StatusParagraphs.h b/toolsrc/include/StatusParagraphs.h
index 9446d432c..7a0f2177d 100644
--- a/toolsrc/include/StatusParagraphs.h
+++ b/toolsrc/include/StatusParagraphs.h
@@ -13,6 +13,10 @@ namespace vcpkg
         using iterator = container::reverse_iterator;
         using const_iterator = container::const_reverse_iterator;
 
+        const_iterator find(const package_spec& spec) const
+        {
+            return find(spec.name(), spec.target_triplet());
+        }
         const_iterator find(const std::string& name, const triplet& target_triplet) const;
         iterator find(const std::string& name, const triplet& target_triplet);
         iterator find_installed(const std::string& name, const triplet& target_triplet);
diff --git a/toolsrc/include/vcpkg.h b/toolsrc/include/vcpkg.h
index 1d7f87d32..81b4d45ba 100644
--- a/toolsrc/include/vcpkg.h
+++ b/toolsrc/include/vcpkg.h
@@ -16,4 +16,13 @@ namespace vcpkg
 
     void install_package(const vcpkg_paths& paths, const BinaryParagraph& binary_paragraph, StatusParagraphs& status_db);
     void deinstall_package(const vcpkg_paths& paths, const package_spec& spec, StatusParagraphs& status_db);
+
+    expected<SourceParagraph> try_load_port(const fs::path& control_path);
+    inline expected<SourceParagraph> try_load_port(const vcpkg_paths& paths, const std::string& name)
+    {
+        return try_load_port(paths.ports / name);
+    }
+
+    expected<BinaryParagraph> try_load_cached_package(const vcpkg_paths& paths, const package_spec& spec);
+
 } // namespace vcpkg
diff --git a/toolsrc/include/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
index 8e6808ee3..b556eb7d8 100644
--- a/toolsrc/include/vcpkg_Dependencies.h
+++ b/toolsrc/include/vcpkg_Dependencies.h
@@ -2,14 +2,23 @@
 #include <vector>
 #include "package_spec.h"
 #include "StatusParagraphs.h"
-#include <unordered_set>
 #include "vcpkg_paths.h"
 
 namespace vcpkg {namespace Dependencies
 {
-    std::vector<package_spec> create_dependency_ordered_install_plan(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db);
+    enum class install_plan_kind
+    {
+        BUILD_AND_INSTALL,
+        INSTALL,
+        ALREADY_INSTALLED
+    };
 
-    std::unordered_set<package_spec> get_unmet_dependencies(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db);
+    struct install_plan_action
+    {
+        install_plan_kind plan;
+        std::unique_ptr<BinaryParagraph> bpgh;
+        std::unique_ptr<SourceParagraph> spgh;
+    };
 
-    std::vector<std::string> get_unmet_package_build_dependencies(const vcpkg_paths& paths, const package_spec& spec);
+    std::vector<std::pair<package_spec, install_plan_action>> create_install_plan(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db);
 }}
diff --git a/toolsrc/src/commands_installation.cpp b/toolsrc/src/commands_installation.cpp
index 460fa1818..b900b56c8 100644
--- a/toolsrc/src/commands_installation.cpp
+++ b/toolsrc/src/commands_installation.cpp
@@ -9,7 +9,6 @@
 #include "vcpkg_Dependencies.h"
 #include "vcpkg_Input.h"
 #include "vcpkg_Maps.h"
-#include "Paragraphs.h"
 #include "vcpkg_info.h"
 
 namespace vcpkg
@@ -21,17 +20,15 @@ namespace vcpkg
         std::ofstream(binary_control_file) << bpgh;
     }
 
-    static void build_internal(const package_spec& spec, const vcpkg_paths& paths, const fs::path& port_dir)
+    static void build_internal(const SourceParagraph& source_paragraph, const package_spec& spec, const vcpkg_paths& paths, const fs::path& port_dir)
     {
-        auto pghs = Paragraphs::get_paragraphs(port_dir / "CONTROL");
-        Checks::check_exit(pghs.size() == 1, "Error: invalid control file");
-        SourceParagraph source_paragraph(pghs[0]);
+        Checks::check_exit(spec.name() == source_paragraph.name, "inconsistent arguments to build_internal()");
+        auto&& target_triplet = spec.target_triplet();
 
         const fs::path ports_cmake_script_path = paths.ports_cmake;
-        auto&& target_triplet = spec.target_triplet();
         const std::wstring command = Strings::wformat(LR"("%%VS140COMNTOOLS%%..\..\VC\vcvarsall.bat" %s && cmake -DCMD=BUILD -DPORT=%s -DTARGET_TRIPLET=%s "-DCURRENT_PORT_DIR=%s/." -P "%s")",
                                                       Strings::utf8_to_utf16(target_triplet.architecture()),
-                                                      Strings::utf8_to_utf16(spec.name()),
+                                                      Strings::utf8_to_utf16(source_paragraph.name),
                                                       Strings::utf8_to_utf16(target_triplet.canonical_name()),
                                                       port_dir.generic_wstring(),
                                                       ports_cmake_script_path.generic_wstring());
@@ -65,11 +62,6 @@ namespace vcpkg
         // delete_directory(port_buildtrees_dir);
     }
 
-    static void build_internal(const package_spec& spec, const vcpkg_paths& paths)
-    {
-        return build_internal(spec, paths, paths.ports / spec.name());
-    }
-
     void install_command(const vcpkg_cmd_arguments& args, const vcpkg_paths& paths, const triplet& default_target_triplet)
     {
         static const std::string example = create_example_string("install zlib zlib:x64-windows curl boost");
@@ -78,49 +70,47 @@ namespace vcpkg
 
         std::vector<package_spec> specs = Input::check_and_get_package_specs(args.command_arguments, default_target_triplet, example.c_str());
         Input::check_triplets(specs, paths);
-        std::vector<package_spec> install_plan = Dependencies::create_dependency_ordered_install_plan(paths, specs, status_db);
+        auto install_plan = Dependencies::create_install_plan(paths, specs, status_db);
         Checks::check_exit(!install_plan.empty(), "Install plan cannot be empty");
-        std::string specs_string = to_string(install_plan[0]);
+
+        std::string specs_string = to_string(install_plan[0].first);
         for (size_t i = 1; i < install_plan.size(); ++i)
         {
             specs_string.push_back(',');
-            specs_string.append(to_string(install_plan[i]));
+            specs_string.append(to_string(install_plan[i].first));
         }
         TrackProperty("installplan", specs_string);
         Environment::ensure_utilities_on_path(paths);
 
-        for (const package_spec& spec : install_plan)
+        for (const auto& action : install_plan)
         {
-            if (status_db.find_installed(spec.name(), spec.target_triplet()) != status_db.end())
-            {
-                System::println(System::color::success, "Package %s is already installed", spec);
-                continue;
-            }
-
-            fs::path package_path = paths.package_dir(spec);
-
-            expected<std::string> file_contents = Files::get_contents(package_path / "CONTROL");
-
             try
             {
-                if (file_contents.error_code())
+                if (action.second.plan == Dependencies::install_plan_kind::ALREADY_INSTALLED)
                 {
-                    build_internal(spec, paths);
-                    file_contents = Files::get_contents(package_path / "CONTROL");
-                    if (file_contents.error_code())
+                    if (std::find(specs.begin(), specs.end(), action.first) != specs.end())
                     {
-                        file_contents.get_or_throw();
+                        System::println(System::color::success, "Package %s is already installed", action.first);
                     }
                 }
-
-                auto pghs = Paragraphs::parse_paragraphs(file_contents.get_or_throw());
-                Checks::check_throw(pghs.size() == 1, "multiple paragraphs in control file");
-                install_package(paths, BinaryParagraph(pghs[0]), status_db);
-                System::println(System::color::success, "Package %s is installed", spec);
+                else if (action.second.plan == Dependencies::install_plan_kind::BUILD_AND_INSTALL)
+                {
+                    build_internal(*action.second.spgh, action.first, paths, paths.port_dir(action.first));
+                    auto bpgh = try_load_cached_package(paths, action.first).get_or_throw();
+                    install_package(paths, bpgh, status_db);
+                    System::println(System::color::success, "Package %s is installed", action.first);
+                }
+                else if (action.second.plan == Dependencies::install_plan_kind::INSTALL)
+                {
+                    install_package(paths, *action.second.bpgh, status_db);
+                    System::println(System::color::success, "Package %s is installed", action.first);
+                }
+                else
+                    Checks::unreachable();
             }
             catch (const std::exception& e)
             {
-                System::println(System::color::error, "Error: Could not install package %s: %s", spec, e.what());
+                System::println(System::color::error, "Error: Could not install package %s: %s", action.first, e.what());
                 exit(EXIT_FAILURE);
             }
         }
@@ -142,29 +132,41 @@ namespace vcpkg
         Input::check_triplet(spec.target_triplet(), paths);
 
         // Explicitly load and use the portfile's build dependencies when resolving the build command (instead of a cached package's dependencies).
-        auto first_level_deps = Dependencies::get_unmet_package_build_dependencies(paths, spec);
+        auto maybe_spgh = try_load_port(paths, spec.name());
+        Checks::check_exit(!maybe_spgh.error_code(), "Could not find package named %s: %s", spec, maybe_spgh.error_code().message());
+        auto& spgh = *maybe_spgh.get();
+
+        auto first_level_deps = filter_dependencies(spgh.depends, spec.target_triplet());
+
         std::vector<package_spec> first_level_deps_specs;
         for (auto&& dep : first_level_deps)
         {
             first_level_deps_specs.push_back(package_spec::from_name_and_triplet(dep, spec.target_triplet()).get_or_throw());
         }
 
-        std::unordered_set<package_spec> unmet_dependencies = Dependencies::get_unmet_dependencies(paths, first_level_deps_specs, status_db);
+        auto unmet_dependencies = Dependencies::create_install_plan(paths, first_level_deps_specs, status_db);
+        unmet_dependencies.erase(
+            std::remove_if(unmet_dependencies.begin(), unmet_dependencies.end(), [](auto& p)
+                           {
+                               return p.second.plan == Dependencies::install_plan_kind::ALREADY_INSTALLED;
+                           }),
+            unmet_dependencies.end());
+
         if (!unmet_dependencies.empty())
         {
             System::println(System::color::error, "The build command requires all dependencies to be already installed.");
             System::println("The following dependencies are missing:");
             System::println("");
-            for (const package_spec& p : unmet_dependencies)
+            for (const auto& p : unmet_dependencies)
             {
-                System::println("    %s", to_string(p));
+                System::println("    %s", to_string(p.first));
             }
             System::println("");
             exit(EXIT_FAILURE);
         }
 
         Environment::ensure_utilities_on_path(paths);
-        build_internal(spec, paths);
+        build_internal(spgh, spec, paths, paths.port_dir(spec));
         exit(EXIT_SUCCESS);
     }
 
@@ -173,17 +175,21 @@ namespace vcpkg
         static const std::string example = create_example_string(R"(build_external zlib2 C:\path\to\dir\with\controlfile\)");
         args.check_exact_arg_count(2, example.c_str());
 
-        expected<package_spec> current_spec = package_spec::from_string(args.command_arguments[0], default_target_triplet);
-        if (auto spec = current_spec.get())
+        expected<package_spec> maybe_current_spec = package_spec::from_string(args.command_arguments[0], default_target_triplet);
+        if (auto spec = maybe_current_spec.get())
         {
             Input::check_triplet(spec->target_triplet(), paths);
             Environment::ensure_utilities_on_path(paths);
             const fs::path port_dir = args.command_arguments.at(1);
-            build_internal(*spec, paths, port_dir);
-            exit(EXIT_SUCCESS);
+            auto maybe_spgh = try_load_port(port_dir);
+            if (auto spgh = maybe_spgh.get())
+            {
+                build_internal(*spgh, *spec, paths, port_dir);
+                exit(EXIT_SUCCESS);
+            }
         }
 
-        System::println(System::color::error, "Error: %s: %s", current_spec.error_code().message(), args.command_arguments[0]);
+        System::println(System::color::error, "Error: %s: %s", maybe_current_spec.error_code().message(), args.command_arguments[0]);
         print_example(Strings::format("%s zlib:x64-windows", args.command).c_str());
         exit(EXIT_FAILURE);
     }
diff --git a/toolsrc/src/vcpkg.cpp b/toolsrc/src/vcpkg.cpp
index 6e47df2c8..db85eee8f 100644
--- a/toolsrc/src/vcpkg.cpp
+++ b/toolsrc/src/vcpkg.cpp
@@ -369,3 +369,39 @@ void vcpkg::deinstall_package(const vcpkg_paths& paths, const package_spec& spec
     write_update(paths, pkg);
     System::println(System::color::success, "Package %s was successfully removed", pkg.package.displayname());
 }
+
+expected<SourceParagraph> vcpkg::try_load_port(const fs::path& path)
+{
+    try
+    {
+        auto pghs = Paragraphs::get_paragraphs(path / "CONTROL");
+        Checks::check_exit(pghs.size() == 1, "Invalid control file at %s\\CONTROL", path.string());
+        return SourceParagraph(pghs[0]);
+    }
+    catch (std::runtime_error const&)
+    {
+    }
+
+    return std::errc::no_such_file_or_directory;
+}
+
+expected<BinaryParagraph> vcpkg::try_load_cached_package(const vcpkg_paths& paths, const package_spec& spec)
+{
+    const fs::path path = paths.package_dir(spec) / "CONTROL";
+
+    auto control_contents_maybe = Files::get_contents(path);
+    if (auto control_contents = control_contents_maybe.get())
+    {
+        std::vector<std::unordered_map<std::string, std::string>> pghs;
+        try
+        {
+            pghs = Paragraphs::parse_paragraphs(*control_contents);
+        }
+        catch (std::runtime_error)
+        {
+        }
+        Checks::check_exit(pghs.size() == 1, "Invalid control file at %s", path.string());
+        return BinaryParagraph(pghs[0]);
+    }
+    return control_contents_maybe.error_code();
+}
diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
index c054ec913..3142b44ba 100644
--- a/toolsrc/src/vcpkg_Dependencies.cpp
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -7,40 +7,17 @@
 #include <unordered_set>
 #include "vcpkg_Maps.h"
 #include "vcpkg_Files.h"
-#include "Paragraphs.h"
+#include "vcpkg.h"
 
 namespace vcpkg { namespace Dependencies
 {
-    // TODO: Refactoring between this function and install_package
-    static std::vector<std::string> get_single_level_unmet_dependencies(const vcpkg_paths& paths, const package_spec& spec)
+    std::vector<std::pair<package_spec, install_plan_action>> create_install_plan(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db)
     {
-        const fs::path packages_dir_control_file_path = paths.package_dir(spec) / "CONTROL";
-
-        auto control_contents_maybe = Files::get_contents(packages_dir_control_file_path);
-        if (auto control_contents = control_contents_maybe.get())
-        {
-            std::vector<std::unordered_map<std::string, std::string>> pghs;
-            try
-            {
-                pghs = Paragraphs::parse_paragraphs(*control_contents);
-            }
-            catch (std::runtime_error)
-            {
-            }
-            Checks::check_exit(pghs.size() == 1, "Invalid control file at %s", packages_dir_control_file_path.string());
-            return BinaryParagraph(pghs[0]).depends;
-        }
-
-        return get_unmet_package_build_dependencies(paths, spec);
-    }
-
-    static Graphs::Graph<package_spec> build_dependency_graph(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db)
-    {
-        std::vector<package_spec> examine_stack(specs);
-        std::unordered_set<package_spec> was_examined; // Examine = we have checked its immediate (non-recursive) dependencies
+        std::unordered_map<package_spec, install_plan_action> was_examined; // Examine = we have checked its immediate (non-recursive) dependencies
         Graphs::Graph<package_spec> graph;
-        graph.add_vertices(examine_stack);
+        graph.add_vertices(specs);
 
+        std::vector<package_spec> examine_stack(specs);
         while (!examine_stack.empty())
         {
             const package_spec spec = examine_stack.back();
@@ -51,59 +28,48 @@ namespace vcpkg { namespace Dependencies
                 continue;
             }
 
-            std::vector<std::string> dependencies_as_string = get_single_level_unmet_dependencies(paths, spec);
+            auto process_dependencies = [&](const std::vector<std::string>& dependencies_as_string)
+                {
+                    for (const std::string& dep_as_string : dependencies_as_string)
+                    {
+                        const package_spec current_dep = package_spec::from_name_and_triplet(dep_as_string, spec.target_triplet()).get_or_throw();
+                        graph.add_edge(spec, current_dep);
+                        if (was_examined.find(current_dep) == was_examined.end())
+                        {
+                            examine_stack.push_back(std::move(current_dep));
+                        }
+                    }
+                };
 
-            for (const std::string& dep_as_string : dependencies_as_string)
+            auto it = status_db.find(spec);
+            if (it != status_db.end() && (*it)->want == want_t::install)
             {
-                const package_spec current_dep = package_spec::from_name_and_triplet(dep_as_string, spec.target_triplet()).get_or_throw();
-                auto it = status_db.find(current_dep.name(), current_dep.target_triplet());
-                if (it != status_db.end() && (*it)->want == want_t::install)
-                {
-                    continue;
-                }
+                was_examined.emplace(spec, install_plan_action{install_plan_kind::ALREADY_INSTALLED, nullptr, nullptr});
+                continue;
+            }
 
-                graph.add_edge(spec, current_dep);
-                if (was_examined.find(current_dep) == was_examined.end())
-                {
-                    examine_stack.push_back(std::move(current_dep));
-                }
+            expected<BinaryParagraph> maybe_bpgh = try_load_cached_package(paths, spec);
+            if (BinaryParagraph* bpgh = maybe_bpgh.get())
+            {
+                process_dependencies(bpgh->depends);
+                was_examined.emplace(spec, install_plan_action{install_plan_kind::INSTALL, std::make_unique<BinaryParagraph>(std::move(*bpgh)), nullptr});
+                continue;
             }
 
-            was_examined.insert(spec);
+            expected<SourceParagraph> maybe_spgh = try_load_port(paths, spec.name());
+            SourceParagraph* spgh = maybe_spgh.get();
+            Checks::check_exit(spgh != nullptr, "Cannot find package");
+            process_dependencies(filter_dependencies(spgh->depends, spec.target_triplet()));
+            was_examined.emplace(spec, install_plan_action{install_plan_kind::BUILD_AND_INSTALL, nullptr, std::make_unique<SourceParagraph>(std::move(*spgh))});
         }
 
-        return graph;
-    }
-
-    std::vector<package_spec> create_dependency_ordered_install_plan(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db)
-    {
-        return build_dependency_graph(paths, specs, status_db).find_topological_sort();
-    }
-
-    std::unordered_set<package_spec> get_unmet_dependencies(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db)
-    {
-        const Graphs::Graph<package_spec> dependency_graph = build_dependency_graph(paths, specs, status_db);
-        return Maps::extract_key_set(dependency_graph.adjacency_list());
-    }
+        std::vector<std::pair<package_spec, install_plan_action>> ret;
 
-    std::vector<std::string> get_unmet_package_build_dependencies(const vcpkg_paths& paths, const package_spec& spec)
-    {
-        const fs::path ports_dir_control_file_path = paths.port_dir(spec) / "CONTROL";
-        auto control_contents_maybe = Files::get_contents(ports_dir_control_file_path);
-        if (auto control_contents = control_contents_maybe.get())
+        std::vector<package_spec> pkgs = graph.find_topological_sort();
+        for (package_spec& pkg : pkgs)
         {
-            std::vector<std::unordered_map<std::string, std::string>> pghs;
-            try
-            {
-                pghs = Paragraphs::parse_paragraphs(*control_contents);
-            }
-            catch (std::runtime_error)
-            {
-            }
-            Checks::check_exit(pghs.size() == 1, "Invalid control file at %s", ports_dir_control_file_path.string());
-            return filter_dependencies(SourceParagraph(pghs[0]).depends, spec.target_triplet());
+            ret.emplace_back(pkg, std::move(was_examined[pkg]));
         }
-
-        Checks::exit_with_message("Could not find package named %s", spec);
+        return ret;
     }
 }}