Merge from master

20 files changed, 404 insertions, 298 deletions

diff --git a/docs/EXAMPLES.md b/docs/EXAMPLES.md
index 73b0d3048..7331bd81c 100644
--- a/docs/EXAMPLES.md
+++ b/docs/EXAMPLES.md
@@ -62,7 +62,6 @@ PS D:\src\vcpkg> .\vcpkg install sqlite3
 -- Performing post-build validation done
 Package sqlite3:x86-windows is installed
 ```
-In addition to installing, `vcpkg` caches a pristine copy of the built library inside the `packages\` directory -- in this case, `packages\sqlite3_x86-windows`. This allows you to quickly uninstall and reinstall the library in the future using the `remove` and `install` commands.
 
 We can check that sqlite3 was successfully installed for x86 windows desktop by running the `list` command.
 ```
@@ -93,7 +92,7 @@ Installing new libraries will make them instantly available.
 ```
 *Note: You will need to restart Visual Studio or perform a Build to update intellisense with the changes.* 
 
-You can now simply use File -> New Project in Visual Studio 2015 or Visual Studio "15" Preview and the library will be automatically available. For Sqlite, you can try out their [C/C++ sample](https://sqlite.org/quickstart.html).
+You can now simply use File -> New Project in Visual Studio 2015 or Visual Studio 2017 and the library will be automatically available. For Sqlite, you can try out their [C/C++ sample](https://sqlite.org/quickstart.html).
 
 To remove the integration for your user, you can use `.\vcpkg integrate remove`.
 
diff --git a/ports/sdl2-mixer/CMakeLists.txt b/ports/sdl2-mixer/CMakeLists.txt
new file mode 100644
index 000000000..094912b48
--- /dev/null
+++ b/ports/sdl2-mixer/CMakeLists.txt
@@ -0,0 +1,95 @@
+cmake_minimum_required(VERSION 3.0)
+project(SDL2_MIXER C)
+
+find_path(SDL_INCLUDE_DIR SDL.h PATH_SUFFIXES SDL2)
+find_library(SDL_LIBRARY SDL2)
+set(SDL_MIXER_INCLUDES ${SDL_INCLUDE_DIR})
+set(SDL_MIXER_LIBRARIES ${SDL_LIBRARY})
+
+# builtin formats
+set(SDL_MIXER_DEFINES 
+    WAV_MUSIC
+    MID_MUSIC
+    USE_NATIVE_MIDI)
+
+# MP3 support
+if(SDL_MIXER_ENABLE_MP3)
+    find_path(SMPEG_INCLUDE_DIR smpeg.h)
+    find_library(SMPEG_LIBRARY smpeg2)
+    list(APPEND SDL_MIXER_INCLUDES ${SMPEG_INCLUDE_DIR})
+    list(APPEND SDL_MIXER_LIBRARIES ${SMPEG_LIBRARY})
+    list(APPEND SDL_MIXER_DEFINES MP3_MUSIC)
+endif()
+
+# FLAC support
+if(SDL_MIXER_ENABLE_FLAC)
+    find_path(FLAC_INCLUDE_DIR flac/all.h)
+    find_library(FLAC_LIBRARY flac)
+    list(APPEND SDL_MIXER_INCLUDES ${FLAC_INCLUDE_DIR})
+    list(APPEND SDL_MIXER_LIBRARIES ${FLAC_LIBRARY})
+    list(APPEND SDL_MIXER_DEFINES FLAC_MUSIC)
+endif()
+
+# MOD support
+if(SDL_MIXER_ENABLE_MOD)
+    find_path(MODPLUG_INCLUDE_DIR libmodplug/modplug.h)
+    find_library(MODPLUG_LIBRARY modplug)
+    list(APPEND SDL_MIXER_INCLUDES ${MODPLUG_INCLUDE_DIR})
+    list(APPEND SDL_MIXER_LIBRARIES ${MODPLUG_LIBRARY})
+    list(APPEND SDL_MIXER_DEFINES MODPLUG_MUSIC)
+endif()
+
+# Ogg-Vorbis support
+if(SDL_MIXER_ENABLE_OGGVORBIS)
+    find_path(VORBIS_INCLUDE_DIR vorbis/codec.h)
+    find_library(VORBISFILE_LIBRARY vorbisfile)
+    list(APPEND SDL_MIXER_INCLUDES ${VORBIS_INCLUDE_DIR})
+    list(APPEND SDL_MIXER_LIBRARIES ${VORBISFILE_LIBRARY})
+    list(APPEND SDL_MIXER_DEFINES OGG_MUSIC)
+endif()
+
+add_library(SDL2_mixer 
+    dynamic_flac.c
+    dynamic_fluidsynth.c
+    dynamic_mod.c
+    dynamic_modplug.c
+    dynamic_mp3.c
+    dynamic_ogg.c
+    effect_position.c
+    effect_stereoreverse.c
+    effects_internal.c
+    fluidsynth.c
+    load_aiff.c
+    load_flac.c
+    load_mp3.c
+    load_ogg.c
+    load_voc.c
+    mixer.c
+    music.c
+    music_cmd.c
+    music_flac.c
+    music_mad.c
+    music_mod.c
+    music_modplug.c
+    music_ogg.c
+    wavestream.c
+    native_midi/native_midi_common.c
+    native_midi/native_midi_win32.c)
+
+target_compile_definitions(SDL2_mixer PRIVATE ${SDL_MIXER_DEFINES})
+target_include_directories(SDL2_mixer PRIVATE ${SDL_MIXER_INCLUDES} ./native_midi)
+target_link_libraries(SDL2_mixer ${SDL_MIXER_LIBRARIES} Winmm)
+
+install(TARGETS SDL2_mixer
+    RUNTIME DESTINATION bin
+    ARCHIVE DESTINATION lib
+    LIBRARY DESTINATION lib)
+
+if(NOT SDL_MIXER_SKIP_HEADERS)
+    install(FILES SDL_mixer.h DESTINATION include/SDL2)
+endif()
+
+message(STATUS "Link-time dependencies:")
+foreach(LIBRARY ${SDL_MIXER_LIBRARIES})
+    message(STATUS "  " ${LIBRARY})
+endforeach()
diff --git a/ports/sdl2-mixer/CONTROL b/ports/sdl2-mixer/CONTROL
new file mode 100644
index 000000000..b5d51aecd
--- /dev/null
+++ b/ports/sdl2-mixer/CONTROL
@@ -0,0 +1,4 @@
+Source: sdl2-mixer
+Version: 2.0.1
+Description: Multi-channel audio mixer library for SDL.
+Build-Depends: sdl2, libflac, smpeg2, libmodplug, libvorbis
diff --git a/ports/sdl2-mixer/portfile.cmake b/ports/sdl2-mixer/portfile.cmake
new file mode 100644
index 000000000..574e6a1e0
--- /dev/null
+++ b/ports/sdl2-mixer/portfile.cmake
@@ -0,0 +1,26 @@
+include(vcpkg_common_functions)
+set(SOURCE_PATH ${CURRENT_BUILDTREES_DIR}/src/SDL2_mixer-2.0.1)
+vcpkg_download_distfile(ARCHIVE
+    URLS "https://www.libsdl.org/projects/SDL_mixer/release/SDL2_mixer-2.0.1.zip"
+    FILENAME "SDL2_mixer-2.0.1.zip"
+    SHA512 7399f08c5b091698c90d49fcc2996677eae8a36f05a65b4470807c9cf2c04730669e0ca395893cfa49177a929f8c5b2b10b6c541ba2fe2646300dcdad4ec1d9e)
+
+vcpkg_extract_source_archive(${ARCHIVE})
+file(COPY ${CMAKE_CURRENT_LIST_DIR}/CMakeLists.txt DESTINATION ${SOURCE_PATH})
+
+vcpkg_configure_cmake(
+    SOURCE_PATH ${SOURCE_PATH}
+    PREFER_NINJA
+    OPTIONS
+        -DSDL_MIXER_ENABLE_MP3=ON       # smpeg2
+        -DSDL_MIXER_ENABLE_FLAC=ON      # libflac
+        -DSDL_MIXER_ENABLE_MOD=ON       # libmodplug
+        -DSDL_MIXER_ENABLE_OGGVORBIS=ON # libvorbis 
+    OPTIONS_DEBUG
+        -DSDL_MIXER_SKIP_HEADERS=ON)
+
+vcpkg_install_cmake()
+vcpkg_copy_pdbs()
+
+file(COPY ${SOURCE_PATH}/COPYING.txt DESTINATION ${CURRENT_PACKAGES_DIR}/share/sdl2-mixer)
+file(RENAME ${CURRENT_PACKAGES_DIR}/share/sdl2-mixer/COPYING.txt ${CURRENT_PACKAGES_DIR}/share/sdl2-mixer/copyright)
diff --git a/toolsrc/include/PackageSpec.h b/toolsrc/include/PackageSpec.h
index 4c3b47365..0d69ac89c 100644
--- a/toolsrc/include/PackageSpec.h
+++ b/toolsrc/include/PackageSpec.h
@@ -25,6 +25,7 @@ namespace vcpkg
     };
 
     bool operator==(const PackageSpec& left, const PackageSpec& right);
+    bool operator!=(const PackageSpec& left, const PackageSpec& right);
 } //namespace vcpkg
 
 namespace std
diff --git a/toolsrc/include/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
index 0e629ffef..f35250447 100644
--- a/toolsrc/include/vcpkg_Dependencies.h
+++ b/toolsrc/include/vcpkg_Dependencies.h
@@ -16,6 +16,15 @@ namespace vcpkg::Dependencies
 
     std::string to_output_string(RequestType request_type, const CStringView s);
 
+    struct AnyParagraph
+    {
+        std::vector<PackageSpec> dependencies(const Triplet& triplet) const;
+
+        Optional<StatusParagraph> status_paragraph;
+        Optional<BinaryParagraph> binary_paragraph;
+        Optional<SourceParagraph> source_paragraph;
+    };
+
     enum class InstallPlanType
     {
         UNKNOWN,
@@ -26,27 +35,19 @@ namespace vcpkg::Dependencies
 
     struct InstallPlanAction
     {
+        static bool compare_by_name(const InstallPlanAction* left, const InstallPlanAction* right);
+
         InstallPlanAction();
-        InstallPlanAction(const InstallPlanType& plan_type, const RequestType& request_type, Optional<BinaryParagraph> binary_pgh, Optional<SourceParagraph> source_pgh);
+        explicit InstallPlanAction(const PackageSpec& spec, const AnyParagraph& any_paragraph, const RequestType& request_type);
         InstallPlanAction(const InstallPlanAction&) = delete;
         InstallPlanAction(InstallPlanAction&&) = default;
         InstallPlanAction& operator=(const InstallPlanAction&) = delete;
         InstallPlanAction& operator=(InstallPlanAction&&) = default;
 
+        PackageSpec spec;
+        AnyParagraph any_paragraph;
         InstallPlanType plan_type;
         RequestType request_type;
-        Optional<BinaryParagraph> binary_pgh;
-        Optional<SourceParagraph> source_pgh;
-    };
-
-    struct PackageSpecWithInstallPlan
-    {
-        static bool compare_by_name(const PackageSpecWithInstallPlan* left, const PackageSpecWithInstallPlan* right);
-
-        PackageSpecWithInstallPlan(const PackageSpec& spec, InstallPlanAction&& plan);
-
-        PackageSpec spec;
-        InstallPlanAction plan;
     };
 
     enum class RemovePlanType
@@ -58,28 +59,21 @@ namespace vcpkg::Dependencies
 
     struct RemovePlanAction
     {
+        static bool compare_by_name(const RemovePlanAction* left, const RemovePlanAction* right);
+
         RemovePlanAction();
-        RemovePlanAction(const RemovePlanType& plan_type, const RequestType& request_type);
+        RemovePlanAction(const PackageSpec& spec, const RemovePlanType& plan_type, const RequestType& request_type);
         RemovePlanAction(const RemovePlanAction&) = delete;
         RemovePlanAction(RemovePlanAction&&) = default;
         RemovePlanAction& operator=(const RemovePlanAction&) = delete;
         RemovePlanAction& operator=(RemovePlanAction&&) = default;
 
+        PackageSpec spec;
         RemovePlanType plan_type;
         RequestType request_type;
     };
 
-    struct PackageSpecWithRemovePlan
-    {
-        static bool compare_by_name(const PackageSpecWithRemovePlan* left, const PackageSpecWithRemovePlan* right);
-
-        PackageSpecWithRemovePlan(const PackageSpec& spec, RemovePlanAction&& plan);
-
-        PackageSpec spec;
-        RemovePlanAction plan;
-    };
-
-    std::vector<PackageSpecWithInstallPlan> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
+    std::vector<InstallPlanAction> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
 
-    std::vector<PackageSpecWithRemovePlan> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
+    std::vector<RemovePlanAction> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db);
 }
diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h
index 933d9ac67..97cd29236 100644
--- a/toolsrc/include/vcpkg_Graphs.h
+++ b/toolsrc/include/vcpkg_Graphs.h
@@ -1,7 +1,6 @@
 #pragma once
 
 #include <unordered_map>
-#include <unordered_set>
 
 namespace vcpkg::Graphs
 {
@@ -17,104 +16,54 @@ namespace vcpkg::Graphs
         FULLY_EXPLORED
     };
 
-    template <class V>
-    class Graph
+    template <class V, class U>
+    __interface AdjacencyProvider
     {
-        static void find_topological_sort_internal(V vertex,
-                                                   ExplorationStatus& status,
-                                                   const std::unordered_map<V, std::unordered_set<V>>& adjacency_list,
-                                                   std::unordered_map<V, ExplorationStatus>& exploration_status,
-                                                   std::vector<V>& sorted)
-        {
-            status = ExplorationStatus::PARTIALLY_EXPLORED;
-
-            for (V neighbour : adjacency_list.at(vertex))
-            {
-                ExplorationStatus& neighbour_status = exploration_status[neighbour];
-                if (neighbour_status == ExplorationStatus::NOT_EXPLORED)
-                {
-                    find_topological_sort_internal(neighbour, neighbour_status, adjacency_list, exploration_status, sorted);
-                }
-                else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED)
-                {
-                    throw std::runtime_error("cycle in graph");
-                }
-            }
-
-            status = ExplorationStatus::FULLY_EXPLORED;
-            sorted.push_back(vertex);
-        }
+        std::vector<V> adjacency_list(const U& vertex) const;
 
-    public:
-
-        void add_vertex(V v)
-        {
-            this->vertices[v];
-        }
-
-        // TODO: Change with iterators
-        void add_vertices(const std::vector<V>& vs)
-        {
-            for (const V& v : vs)
-            {
-                this->vertices[v];
-            }
-        }
-
-        void add_edge(V u, V v)
-        {
-            this->vertices[v];
-            this->vertices[u].insert(v);
-        }
+        U load_vertex_data(const V& vertex) const;
+    };
 
-        std::vector<V> find_topological_sort() const
+    template <class V, class U>
+    static void topological_sort_internal(const V& vertex,
+                                          const AdjacencyProvider<V, U>& f,
+                                          std::unordered_map<V, ExplorationStatus>& exploration_status,
+                                          std::vector<U>& sorted)
+    {
+        ExplorationStatus& status = exploration_status[vertex];
+        switch (status)
         {
-            std::unordered_map<V, int> indegrees = count_indegrees();
-
-            std::vector<V> sorted;
-            sorted.reserve(indegrees.size());
-
-            std::unordered_map<V, ExplorationStatus> exploration_status;
-            exploration_status.reserve(indegrees.size());
-
-            for (auto& pair : indegrees)
-            {
-                if (pair.second == 0) // Starting from vertices with indegree == 0. Not required.
+            case ExplorationStatus::FULLY_EXPLORED:
+                return;
+            case ExplorationStatus::PARTIALLY_EXPLORED:
+                Checks::exit_with_message(VCPKG_LINE_INFO, "cycle in graph");
+            case ExplorationStatus::NOT_EXPLORED:
                 {
-                    V vertex = pair.first;
-                    ExplorationStatus& status = exploration_status[vertex];
-                    if (status == ExplorationStatus::NOT_EXPLORED)
-                    {
-                        find_topological_sort_internal(vertex, status, this->vertices, exploration_status, sorted);
-                    }
+                    status = ExplorationStatus::PARTIALLY_EXPLORED;
+                    U vertex_data = f.load_vertex_data(vertex);
+                    for (const V& neighbour : f.adjacency_list(vertex_data))
+                        topological_sort_internal(neighbour, f, exploration_status, sorted);
+
+                    sorted.push_back(std::move(vertex_data));
+                    status = ExplorationStatus::FULLY_EXPLORED;
+                    return;
                 }
-            }
-
-            return sorted;
+            default:
+                Checks::unreachable(VCPKG_LINE_INFO);
         }
+    }
 
-        std::unordered_map<V, int> count_indegrees() const
-        {
-            std::unordered_map<V, int> indegrees;
-
-            for (auto& pair : this->vertices)
-            {
-                indegrees[pair.first];
-                for (V neighbour : pair.second)
-                {
-                    ++indegrees[neighbour];
-                }
-            }
-
-            return indegrees;
-        }
+    template <class V, class U>
+    std::vector<U> topological_sort(const std::vector<V>& starting_vertices, const AdjacencyProvider<V, U>& f)
+    {
+        std::vector<U> sorted;
+        std::unordered_map<V, ExplorationStatus> exploration_status;
 
-        const std::unordered_map<V, std::unordered_set<V>>& adjacency_list() const
+        for (auto& vertex : starting_vertices)
         {
-            return this->vertices;
+            topological_sort_internal(vertex, f, exploration_status, sorted);
         }
 
-    private:
-        std::unordered_map<V, std::unordered_set<V>> vertices;
-    };
+        return sorted;
+    }
 }
diff --git a/toolsrc/include/vcpkg_Util.h b/toolsrc/include/vcpkg_Util.h
index cd8dab437..c717830f0 100644
--- a/toolsrc/include/vcpkg_Util.h
+++ b/toolsrc/include/vcpkg_Util.h
@@ -27,4 +27,10 @@ namespace vcpkg::Util
     {
         cont.erase(std::partition(cont.begin(), cont.end(), pred), cont.end());
     }
+
+    template<class Container, class Pred>
+    void keep_if(Container& cont, Pred pred)
+    {
+        cont.erase(std::remove_if(cont.begin(), cont.end(), pred), cont.end());
+    }
 }
\ No newline at end of file
diff --git a/toolsrc/include/vcpkg_optional.h b/toolsrc/include/vcpkg_optional.h
index 4a2ceec30..28bdc81fa 100644
--- a/toolsrc/include/vcpkg_optional.h
+++ b/toolsrc/include/vcpkg_optional.h
@@ -15,6 +15,8 @@ namespace vcpkg
     class Optional
     {
     public:
+        constexpr Optional() : m_is_present(false), m_t() { }
+
         // Constructors are intentionally implicit
         constexpr Optional(NullOpt) : m_is_present(false), m_t() { }
 
diff --git a/toolsrc/src/PackageSpec.cpp b/toolsrc/src/PackageSpec.cpp
index bf1c7380c..2a7f4506c 100644
--- a/toolsrc/src/PackageSpec.cpp
+++ b/toolsrc/src/PackageSpec.cpp
@@ -64,4 +64,9 @@ namespace vcpkg
     {
         return left.name() == right.name() && left.triplet() == right.triplet();
     }
+
+    bool operator!=(const PackageSpec& left, const PackageSpec& right)
+    {
+        return !(left == right);
+    }
 }
diff --git a/toolsrc/src/StatusParagraphs.cpp b/toolsrc/src/StatusParagraphs.cpp
index 132b7d5d4..f41630132 100644
--- a/toolsrc/src/StatusParagraphs.cpp
+++ b/toolsrc/src/StatusParagraphs.cpp
@@ -2,8 +2,6 @@
 #include "StatusParagraphs.h"
 #include "vcpkg_Checks.h"
 #include <algorithm>
-#include <algorithm>
-#include <algorithm>
 
 namespace vcpkg
 {
diff --git a/toolsrc/src/commands_build.cpp b/toolsrc/src/commands_build.cpp
index 8d91ce813..9110e1fd0 100644
--- a/toolsrc/src/commands_build.cpp
+++ b/toolsrc/src/commands_build.cpp
@@ -10,10 +10,11 @@
 #include "metrics.h"
 #include "vcpkg_Enums.h"
 #include "Paragraphs.h"
+#include "vcpkg_Util.h"
 
 namespace vcpkg::Commands::Build
 {
-    using Dependencies::PackageSpecWithInstallPlan;
+    using Dependencies::InstallPlanAction;
     using Dependencies::InstallPlanType;
 
     static const std::string OPTION_CHECKS_ONLY = "--checks-only";
@@ -148,19 +149,17 @@ namespace vcpkg::Commands::Build
         const BuildResult result = build_package(spgh, spec, paths, paths.port_dir(spec), status_db);
         if (result == BuildResult::CASCADED_DUE_TO_MISSING_DEPENDENCIES)
         {
-            std::vector<PackageSpecWithInstallPlan> unmet_dependencies = Dependencies::create_install_plan(paths, { spec }, status_db);
-            unmet_dependencies.erase(
-                std::remove_if(unmet_dependencies.begin(), unmet_dependencies.end(), [&spec](const PackageSpecWithInstallPlan& p)
-                               {
-                                   return (p.spec == spec) || (p.plan.plan_type == InstallPlanType::ALREADY_INSTALLED);
-                               }),
-                unmet_dependencies.end());
+            std::vector<InstallPlanAction> unmet_dependencies = Dependencies::create_install_plan(paths, { spec }, status_db);
+            Util::keep_if(unmet_dependencies, [&spec](const InstallPlanAction& p)
+            {
+                return (p.spec != spec) && (p.plan_type != InstallPlanType::ALREADY_INSTALLED);
+            });
 
             Checks::check_exit(VCPKG_LINE_INFO, !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 PackageSpecWithInstallPlan& p : unmet_dependencies)
+            for (const InstallPlanAction& p : unmet_dependencies)
             {
                 System::println("    %s", p.spec);
             }
diff --git a/toolsrc/src/commands_ci.cpp b/toolsrc/src/commands_ci.cpp
index d4b2865a6..a40a7ed32 100644
--- a/toolsrc/src/commands_ci.cpp
+++ b/toolsrc/src/commands_ci.cpp
@@ -10,7 +10,7 @@
 
 namespace vcpkg::Commands::CI
 {
-    using Dependencies::PackageSpecWithInstallPlan;
+    using Dependencies::InstallPlanAction;
     using Dependencies::InstallPlanType;
     using Build::BuildResult;
 
@@ -36,7 +36,7 @@ namespace vcpkg::Commands::CI
         const std::vector<PackageSpec> specs = load_all_package_specs(paths.get_filesystem(), paths.ports, triplet);
 
         StatusParagraphs status_db = database_load_check(paths);
-        const std::vector<PackageSpecWithInstallPlan> install_plan = Dependencies::create_install_plan(paths, specs, status_db);
+        const std::vector<InstallPlanAction> install_plan = Dependencies::create_install_plan(paths, specs, status_db);
         Checks::check_exit(VCPKG_LINE_INFO, !install_plan.empty(), "Install plan cannot be empty");
 
         std::vector<BuildResult> results;
@@ -44,7 +44,7 @@ namespace vcpkg::Commands::CI
         const ElapsedTime timer = ElapsedTime::create_started();
         size_t counter = 0;
         const size_t package_count = install_plan.size();
-        for (const PackageSpecWithInstallPlan& action : install_plan)
+        for (const InstallPlanAction& action : install_plan)
         {
             const ElapsedTime build_timer = ElapsedTime::create_started();
             counter++;
@@ -56,7 +56,7 @@ namespace vcpkg::Commands::CI
 
             try
             {
-                switch (action.plan.plan_type)
+                switch (action.plan_type)
                 {
                     case InstallPlanType::ALREADY_INSTALLED:
                         results.back() = BuildResult::SUCCEEDED;
@@ -65,7 +65,7 @@ namespace vcpkg::Commands::CI
                     case InstallPlanType::BUILD_AND_INSTALL:
                         {
                             System::println("Building package %s... ", display_name);
-                            const BuildResult result = Commands::Build::build_package(action.plan.source_pgh.value_or_exit(VCPKG_LINE_INFO),
+                            const BuildResult result = Commands::Build::build_package(action.any_paragraph.source_paragraph.value_or_exit(VCPKG_LINE_INFO),
                                                                                       action.spec,
                                                                                       paths,
                                                                                       paths.port_dir(action.spec),
@@ -88,7 +88,7 @@ namespace vcpkg::Commands::CI
                     case InstallPlanType::INSTALL:
                         results.back() = BuildResult::SUCCEEDED;
                         System::println("Installing package %s... ", display_name);
-                        Install::install_package(paths, action.plan.binary_pgh.value_or_exit(VCPKG_LINE_INFO), &status_db);
+                        Install::install_package(paths, action.any_paragraph.binary_paragraph.value_or_exit(VCPKG_LINE_INFO), &status_db);
                         System::println(System::Color::success, "Installing package %s... done", display_name);
                         break;
                     default:
diff --git a/toolsrc/src/commands_hash.cpp b/toolsrc/src/commands_hash.cpp
index 2ffa3a9aa..a9024d9e7 100644
--- a/toolsrc/src/commands_hash.cpp
+++ b/toolsrc/src/commands_hash.cpp
@@ -1,6 +1,7 @@
 #include "pch.h"
 #include "vcpkg_Commands.h"
 #include "vcpkg_System.h"
+#include "vcpkg_Util.h"
 
 namespace vcpkg::Commands::Hash
 {
@@ -20,7 +21,7 @@ namespace vcpkg::Commands::Hash
         Checks::check_exit(VCPKG_LINE_INFO, end != std::string::npos, "Unexpected output format from command: %s", Strings::utf16_to_utf8(cmd_line));
 
         auto hash = output.substr(start, end - start);
-        hash.erase(std::remove_if(hash.begin(), hash.end(), isspace), hash.end());
+        Util::keep_if(hash, [](char c) {return !isspace(c); });
         System::println(hash);
     }
 
diff --git a/toolsrc/src/commands_install.cpp b/toolsrc/src/commands_install.cpp
index 15aab4845..32460b807 100644
--- a/toolsrc/src/commands_install.cpp
+++ b/toolsrc/src/commands_install.cpp
@@ -11,7 +11,7 @@
 
 namespace vcpkg::Commands::Install
 {
-    using Dependencies::PackageSpecWithInstallPlan;
+    using Dependencies::InstallPlanAction;
     using Dependencies::RequestType;
     using Dependencies::InstallPlanType;
 
@@ -140,15 +140,15 @@ namespace vcpkg::Commands::Install
         return SortedVector<std::string>(std::move(installed_files));
     }
 
-    static void print_plan(const std::vector<PackageSpecWithInstallPlan>& plan)
+    static void print_plan(const std::vector<InstallPlanAction>& plan)
     {
-        std::vector<const PackageSpecWithInstallPlan*> already_installed;
-        std::vector<const PackageSpecWithInstallPlan*> build_and_install;
-        std::vector<const PackageSpecWithInstallPlan*> install;
+        std::vector<const InstallPlanAction*> already_installed;
+        std::vector<const InstallPlanAction*> build_and_install;
+        std::vector<const InstallPlanAction*> install;
 
-        for (const PackageSpecWithInstallPlan& i : plan)
+        for (const InstallPlanAction& i : plan)
         {
-            switch (i.plan.plan_type)
+            switch (i.plan_type)
             {
                 case InstallPlanType::ALREADY_INSTALLED:
                     already_installed.push_back(&i);
@@ -164,23 +164,23 @@ namespace vcpkg::Commands::Install
             }
         }
 
-        auto print_lambda = [](const PackageSpecWithInstallPlan* p) { return to_output_string(p->plan.request_type, p->spec.to_string()); };
+        auto print_lambda = [](const InstallPlanAction* p) { return Dependencies::to_output_string(p->request_type, p->spec.to_string()); };
 
         if (!already_installed.empty())
         {
-            std::sort(already_installed.begin(), already_installed.end(), &PackageSpecWithInstallPlan::compare_by_name);
+            std::sort(already_installed.begin(), already_installed.end(), &InstallPlanAction::compare_by_name);
             System::println("The following packages are already installed:\n%s", Strings::join("\n", already_installed, print_lambda));
         }
 
         if (!build_and_install.empty())
         {
-            std::sort(build_and_install.begin(), build_and_install.end(), &PackageSpecWithInstallPlan::compare_by_name);
+            std::sort(build_and_install.begin(), build_and_install.end(), &InstallPlanAction::compare_by_name);
             System::println("The following packages will be built and installed:\n%s", Strings::join("\n", build_and_install, print_lambda));
         }
 
         if (!install.empty())
         {
-            std::sort(install.begin(), install.end(), &PackageSpecWithInstallPlan::compare_by_name);
+            std::sort(install.begin(), install.end(), &InstallPlanAction::compare_by_name);
             System::println("The following packages will be installed:\n%s", Strings::join("\n", install, print_lambda));
         }
     }
@@ -252,7 +252,7 @@ namespace vcpkg::Commands::Install
 
         // create the plan
         StatusParagraphs status_db = database_load_check(paths);
-        std::vector<PackageSpecWithInstallPlan> install_plan = Dependencies::create_install_plan(paths, specs, status_db);
+        std::vector<InstallPlanAction> install_plan = Dependencies::create_install_plan(paths, specs, status_db);
         Checks::check_exit(VCPKG_LINE_INFO, !install_plan.empty(), "Install plan cannot be empty");
 
         // log the plan
@@ -266,9 +266,9 @@ namespace vcpkg::Commands::Install
 
         print_plan(install_plan);
 
-        const bool has_non_user_requested_packages = std::find_if(install_plan.cbegin(), install_plan.cend(), [](const PackageSpecWithInstallPlan& package)-> bool
+        const bool has_non_user_requested_packages = std::find_if(install_plan.cbegin(), install_plan.cend(), [](const InstallPlanAction& package)-> bool
                                                                   {
-                                                                      return package.plan.request_type != RequestType::USER_REQUESTED;
+                                                                      return package.request_type != RequestType::USER_REQUESTED;
                                                                   }) != install_plan.cend();
 
         if (has_non_user_requested_packages)
@@ -282,13 +282,13 @@ namespace vcpkg::Commands::Install
         }
 
         // execute the plan
-        for (const PackageSpecWithInstallPlan& action : install_plan)
+        for (const InstallPlanAction& action : install_plan)
         {
             const std::string display_name = action.spec.to_string();
 
             try
             {
-                switch (action.plan.plan_type)
+                switch (action.plan_type)
                 {
                     case InstallPlanType::ALREADY_INSTALLED:
                         System::println(System::Color::success, "Package %s is already installed", display_name);
@@ -296,7 +296,7 @@ namespace vcpkg::Commands::Install
                     case InstallPlanType::BUILD_AND_INSTALL:
                         {
                             System::println("Building package %s... ", display_name);
-                            const Build::BuildResult result = Commands::Build::build_package(action.plan.source_pgh.value_or_exit(VCPKG_LINE_INFO),
+                            const Build::BuildResult result = Commands::Build::build_package(action.any_paragraph.source_paragraph.value_or_exit(VCPKG_LINE_INFO),
                                                                                              action.spec,
                                                                                              paths,
                                                                                              paths.port_dir(action.spec),
@@ -317,7 +317,7 @@ namespace vcpkg::Commands::Install
                         }
                     case InstallPlanType::INSTALL:
                         System::println("Installing package %s... ", display_name);
-                        install_package(paths, action.plan.binary_pgh.value_or_exit(VCPKG_LINE_INFO), &status_db);
+                        install_package(paths, action.any_paragraph.binary_paragraph.value_or_exit(VCPKG_LINE_INFO), &status_db);
                         System::println(System::Color::success, "Installing package %s... done", display_name);
                         break;
                     case InstallPlanType::UNKNOWN:
diff --git a/toolsrc/src/commands_integrate.cpp b/toolsrc/src/commands_integrate.cpp
index 8569fdd79..819c29082 100644
--- a/toolsrc/src/commands_integrate.cpp
+++ b/toolsrc/src/commands_integrate.cpp
@@ -3,6 +3,7 @@
 #include "vcpkg_Checks.h"
 #include "vcpkg_System.h"
 #include "vcpkg_Files.h"
+#include "vcpkg_Util.h"
 
 namespace vcpkg::Commands::Integrate
 {
@@ -66,10 +67,10 @@ namespace vcpkg::Commands::Integrate
         dir_id.erase(1, 1); // Erasing the ":"
 
         // NuGet id cannot have invalid characters. We will only use alphanumeric and dot.
-        dir_id.erase(std::remove_if(dir_id.begin(), dir_id.end(), [](char c)
-                                    {
-                                        return !isalnum(c) && (c != '.');
-                                    }), dir_id.end());
+        Util::keep_if(dir_id, [](char c)
+                      {
+                          return isalnum(c) || (c == '.');
+                      });
 
         const std::string nuget_id = "vcpkg." + dir_id;
         return nuget_id;
diff --git a/toolsrc/src/commands_remove.cpp b/toolsrc/src/commands_remove.cpp
index 9ce4adb75..a61435b5d 100644
--- a/toolsrc/src/commands_remove.cpp
+++ b/toolsrc/src/commands_remove.cpp
@@ -8,7 +8,7 @@
 
 namespace vcpkg::Commands::Remove
 {
-    using Dependencies::PackageSpecWithRemovePlan;
+    using Dependencies::RemovePlanAction;
     using Dependencies::RemovePlanType;
     using Dependencies::RequestType;
     using Update::OutdatedPackage;
@@ -101,14 +101,14 @@ namespace vcpkg::Commands::Remove
         write_update(paths, pkg);
     }
 
-    static void print_plan(const std::vector<PackageSpecWithRemovePlan>& plan)
+    static void print_plan(const std::vector<RemovePlanAction>& plan)
     {
-        std::vector<const PackageSpecWithRemovePlan*> not_installed;
-        std::vector<const PackageSpecWithRemovePlan*> remove;
+        std::vector<const RemovePlanAction*> not_installed;
+        std::vector<const RemovePlanAction*> remove;
 
-        for (const PackageSpecWithRemovePlan& i : plan)
+        for (const RemovePlanAction& i : plan)
         {
-            switch (i.plan.plan_type)
+            switch (i.plan_type)
             {
                 case RemovePlanType::NOT_INSTALLED:
                     not_installed.push_back(&i);
@@ -121,17 +121,17 @@ namespace vcpkg::Commands::Remove
             }
         }
 
-       auto print_lambda = [](const PackageSpecWithRemovePlan* p) { return to_output_string(p->plan.request_type, p->spec.to_string()); };
+       auto print_lambda = [](const RemovePlanAction* p) { return Dependencies::to_output_string(p->request_type, p->spec.to_string()); };
 
         if (!not_installed.empty())
         {
-            std::sort(not_installed.begin(), not_installed.end(), &PackageSpecWithRemovePlan::compare_by_name);
+            std::sort(not_installed.begin(), not_installed.end(), &RemovePlanAction::compare_by_name);
             System::println("The following packages are not installed, so not removed:\n%s", Strings::join("\n", not_installed, print_lambda));
         }
 
         if (!remove.empty())
         {
-            std::sort(remove.begin(), remove.end(), &PackageSpecWithRemovePlan::compare_by_name);
+            std::sort(remove.begin(), remove.end(), &RemovePlanAction::compare_by_name);
             System::println("The following packages will be removed:\n%s", Strings::join("\n", remove, print_lambda));
         }
     }
@@ -172,14 +172,14 @@ namespace vcpkg::Commands::Remove
         const bool isRecursive = options.find(OPTION_RECURSE) != options.cend();
         const bool dryRun = options.find(OPTION_DRY_RUN) != options.cend();
 
-        const std::vector<PackageSpecWithRemovePlan> remove_plan = Dependencies::create_remove_plan(specs, status_db);
+        const std::vector<RemovePlanAction> remove_plan = Dependencies::create_remove_plan(specs, status_db);
         Checks::check_exit(VCPKG_LINE_INFO, !remove_plan.empty(), "Remove plan cannot be empty");
 
         print_plan(remove_plan);
 
-        const bool has_non_user_requested_packages = std::find_if(remove_plan.cbegin(), remove_plan.cend(), [](const PackageSpecWithRemovePlan& package)-> bool
+        const bool has_non_user_requested_packages = std::find_if(remove_plan.cbegin(), remove_plan.cend(), [](const RemovePlanAction& package)-> bool
                                                                   {
-                                                                      return package.plan.request_type != RequestType::USER_REQUESTED;
+                                                                      return package.request_type != RequestType::USER_REQUESTED;
                                                                   }) != remove_plan.cend();
 
         if (has_non_user_requested_packages)
@@ -198,11 +198,11 @@ namespace vcpkg::Commands::Remove
             Checks::exit_success(VCPKG_LINE_INFO);
         }
 
-        for (const PackageSpecWithRemovePlan& action : remove_plan)
+        for (const RemovePlanAction& action : remove_plan)
         {
             const std::string display_name = action.spec.to_string();
 
-            switch (action.plan.plan_type)
+            switch (action.plan_type)
             {
                 case RemovePlanType::NOT_INSTALLED:
                     System::println(System::Color::success, "Package %s is not installed", display_name);
diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
index 3e3f502b5..03e3c2aeb 100644
--- a/toolsrc/src/vcpkg_Dependencies.cpp
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -5,10 +5,40 @@
 #include "PackageSpec.h"
 #include "StatusParagraphs.h"
 #include "vcpkg_Files.h"
+#include "vcpkg_Util.h"
+#include "vcpkglib.h"
 #include "Paragraphs.h"
 
 namespace vcpkg::Dependencies
 {
+    std::vector<PackageSpec> AnyParagraph::dependencies(const Triplet& triplet) const
+    {
+        auto to_package_specs = [&](const std::vector<std::string>& dependencies_as_string)
+            {
+                return Util::fmap(dependencies_as_string, [&](const std::string s)
+                                  {
+                                      return PackageSpec::from_name_and_triplet(s, triplet).value_or_exit(VCPKG_LINE_INFO);
+                                  });
+            };
+
+        if (auto p = this->status_paragraph.get())
+        {
+            return to_package_specs(p->package.depends);
+        }
+
+        if (auto p = this->binary_paragraph.get())
+        {
+            return to_package_specs(p->depends);
+        }
+
+        if (auto p = this->source_paragraph.get())
+        {
+            return to_package_specs(filter_dependencies(p->depends, triplet));
+        }
+
+        Checks::exit_with_message(VCPKG_LINE_INFO, "Cannot get dependencies because there was none of: source/binary/status paragraphs");
+    }
+
     std::string to_output_string(RequestType request_type, const CStringView s)
     {
         switch (request_type)
@@ -22,160 +52,156 @@ namespace vcpkg::Dependencies
         }
     }
 
-    InstallPlanAction::InstallPlanAction() : plan_type(InstallPlanType::UNKNOWN), request_type(RequestType::UNKNOWN), binary_pgh(nullopt), source_pgh(nullopt) { }
-
-    InstallPlanAction::InstallPlanAction(const InstallPlanType& plan_type, const RequestType& request_type, Optional<BinaryParagraph> binary_pgh, Optional<SourceParagraph> source_pgh)
-        : plan_type(std::move(plan_type)), request_type(request_type), binary_pgh(std::move(binary_pgh)), source_pgh(std::move(source_pgh)) { }
+    InstallPlanAction::InstallPlanAction() : spec()
+                                           , any_paragraph()
+                                           , plan_type(InstallPlanType::UNKNOWN)
+                                           , request_type(RequestType::UNKNOWN) { }
 
-    bool PackageSpecWithInstallPlan::compare_by_name(const PackageSpecWithInstallPlan* left, const PackageSpecWithInstallPlan* right)
+    InstallPlanAction::InstallPlanAction(const PackageSpec& spec, const AnyParagraph& any_paragraph, const RequestType& request_type) : InstallPlanAction()
     {
-        return left->spec.name() < right->spec.name();
-    }
+        this->spec = spec;
+        this->request_type = request_type;
+        if (auto p = any_paragraph.status_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::ALREADY_INSTALLED;
+            this->any_paragraph.status_paragraph = *p;
+            return;
+        }
 
-    PackageSpecWithInstallPlan::PackageSpecWithInstallPlan(const PackageSpec& spec, InstallPlanAction&& plan) : spec(spec), plan(std::move(plan)) { }
+        if (auto p = any_paragraph.binary_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::INSTALL;
+            this->any_paragraph.binary_paragraph = *p;
+            return;
+        }
 
-    RemovePlanAction::RemovePlanAction() : plan_type(RemovePlanType::UNKNOWN), request_type(RequestType::UNKNOWN) { }
+        if (auto p = any_paragraph.source_paragraph.get())
+        {
+            this->plan_type = InstallPlanType::BUILD_AND_INSTALL;
+            this->any_paragraph.source_paragraph = *p;
+            return;
+        }
 
-    RemovePlanAction::RemovePlanAction(const RemovePlanType& plan_type, const Dependencies::RequestType& request_type) : plan_type(plan_type), request_type(request_type) { }
+        this->plan_type = InstallPlanType::UNKNOWN;
+    }
 
-    bool PackageSpecWithRemovePlan::compare_by_name(const PackageSpecWithRemovePlan* left, const PackageSpecWithRemovePlan* right)
+    bool InstallPlanAction::compare_by_name(const InstallPlanAction* left, const InstallPlanAction* right)
     {
         return left->spec.name() < right->spec.name();
     }
 
-    PackageSpecWithRemovePlan::PackageSpecWithRemovePlan(const PackageSpec& spec, RemovePlanAction&& plan)
-        : spec(spec), plan(std::move(plan)) { }
+    RemovePlanAction::RemovePlanAction() : plan_type(RemovePlanType::UNKNOWN)
+                                         , request_type(RequestType::UNKNOWN) { }
 
-    std::vector<PackageSpecWithInstallPlan> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
-    {
-        std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
+    RemovePlanAction::RemovePlanAction(const PackageSpec& spec, const RemovePlanType& plan_type, const RequestType& request_type)
+        : spec(spec)
+        , plan_type(plan_type)
+        , request_type(request_type) { }
 
-        std::unordered_map<PackageSpec, InstallPlanAction> was_examined; // Examine = we have checked its immediate (non-recursive) dependencies
-        Graphs::Graph<PackageSpec> graph;
-        graph.add_vertices(specs);
+    bool RemovePlanAction::compare_by_name(const RemovePlanAction* left, const RemovePlanAction* right)
+    {
+        return left->spec.name() < right->spec.name();
+    }
 
-        std::vector<PackageSpec> examine_stack(specs);
-        while (!examine_stack.empty())
+    std::vector<InstallPlanAction> create_install_plan(const VcpkgPaths& paths, const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
+    {
+        struct InstallAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, InstallPlanAction>
         {
-            const PackageSpec spec = examine_stack.back();
-            examine_stack.pop_back();
+            const VcpkgPaths& paths;
+            const StatusParagraphs& status_db;
+            const std::unordered_set<PackageSpec>& specs_as_set;
 
-            if (was_examined.find(spec) != was_examined.end())
-            {
-                continue;
-            }
+            InstallAdjacencyProvider(const VcpkgPaths& p, const StatusParagraphs& s, const std::unordered_set<PackageSpec>& specs_as_set) : paths(p)
+                                                                                                                                          , status_db(s)
+                                                                                                                                          , specs_as_set(specs_as_set) {}
 
-            auto process_dependencies = [&](const std::vector<std::string>& dependencies_as_string)
-                {
-                    for (const std::string& dep_as_string : dependencies_as_string)
-                    {
-                        const PackageSpec current_dep = PackageSpec::from_name_and_triplet(dep_as_string, spec.triplet()).value_or_exit(VCPKG_LINE_INFO);
-                        auto it = status_db.find_installed(current_dep);
-                        if (it != status_db.end())
-                        {
-                            continue;
-                        }
-
-                        graph.add_edge(spec, current_dep);
-                        if (was_examined.find(current_dep) == was_examined.end())
-                        {
-                            examine_stack.push_back(std::move(current_dep));
-                        }
-                    }
-                };
-
-            const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
-            auto it = status_db.find_installed(spec);
-            if (it != status_db.end())
+            std::vector<PackageSpec> adjacency_list(const InstallPlanAction& p) const override
             {
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::ALREADY_INSTALLED, request_type, nullopt, nullopt });
-                continue;
+                if (p.any_paragraph.status_paragraph.get())
+                    return std::vector<PackageSpec>{};
+                return p.any_paragraph.dependencies(p.spec.triplet());
             }
 
-            Expected<BinaryParagraph> maybe_bpgh = Paragraphs::try_load_cached_package(paths, spec);
-            if (BinaryParagraph* bpgh = maybe_bpgh.get())
+            InstallPlanAction load_vertex_data(const PackageSpec& spec) const override
             {
-                process_dependencies(bpgh->depends);
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::INSTALL, request_type, std::move(*bpgh), nullopt });
-                continue;
-            }
+                const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
+                auto it = status_db.find_installed(spec);
+                if (it != status_db.end())
+                    return InstallPlanAction{ spec, { *it->get(), nullopt, nullopt }, request_type };
 
-            Expected<SourceParagraph> maybe_spgh = Paragraphs::try_load_port(paths.get_filesystem(), paths.port_dir(spec));
-            if (auto spgh = maybe_spgh.get())
-            {
-                process_dependencies(filter_dependencies(spgh->depends, spec.triplet()));
-                was_examined.emplace(spec, InstallPlanAction{ InstallPlanType::BUILD_AND_INSTALL, request_type, nullopt, std::move(*spgh) });
-            }
-            else
-            {
-                Checks::exit_with_message(VCPKG_LINE_INFO, "Cannot find package %s", spec.name());
+                Expected<BinaryParagraph> maybe_bpgh = Paragraphs::try_load_cached_package(paths, spec);
+                if (auto bpgh = maybe_bpgh.get())
+                    return InstallPlanAction{ spec, { nullopt, *bpgh, nullopt }, request_type };
+
+                Expected<SourceParagraph> maybe_spgh = Paragraphs::try_load_port(paths.get_filesystem(), paths.port_dir(spec));
+                if (auto spgh = maybe_spgh.get())
+                    return InstallPlanAction{ spec, { nullopt, nullopt, *spgh }, request_type };
+
+                return InstallPlanAction{ spec , { nullopt, nullopt, nullopt }, request_type };
             }
-        }
+        };
 
-        std::vector<PackageSpecWithInstallPlan> ret;
+        const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
+        std::vector<InstallPlanAction> toposort = Graphs::topological_sort(specs, InstallAdjacencyProvider{ paths, status_db, specs_as_set });
+        Util::keep_if(toposort, [](const InstallPlanAction& p)
+                      {
+                          return !(p.request_type == RequestType::AUTO_SELECTED && p.plan_type == InstallPlanType::ALREADY_INSTALLED);
+                      });
 
-        const std::vector<PackageSpec> pkgs = graph.find_topological_sort();
-        for (const PackageSpec& pkg : pkgs)
-        {
-            ret.push_back(PackageSpecWithInstallPlan(pkg, std::move(was_examined[pkg])));
-        }
-        return ret;
+        return toposort;
     }
 
-    std::vector<PackageSpecWithRemovePlan> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
+    std::vector<RemovePlanAction> create_remove_plan(const std::vector<PackageSpec>& specs, const StatusParagraphs& status_db)
     {
-        std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
-
-        std::unordered_map<PackageSpec, RemovePlanAction> was_examined; // Examine = we have checked its immediate (non-recursive) dependencies
-        Graphs::Graph<PackageSpec> graph;
-        graph.add_vertices(specs);
-
-        std::vector<PackageSpec> examine_stack(specs);
-        while (!examine_stack.empty())
+        struct RemoveAdjacencyProvider final : Graphs::AdjacencyProvider<PackageSpec, RemovePlanAction>
         {
-            const PackageSpec spec = examine_stack.back();
-            examine_stack.pop_back();
-
-            if (was_examined.find(spec) != was_examined.end())
-            {
-                continue;
-            }
+            const StatusParagraphs& status_db;
+            const std::vector<StatusParagraph*>& installed_ports;
+            const std::unordered_set<PackageSpec>& specs_as_set;
 
-            const StatusParagraphs::const_iterator it = status_db.find(spec);
-            if (it == status_db.end() || (*it)->state == InstallState::NOT_INSTALLED)
-            {
-                was_examined.emplace(spec, RemovePlanAction(RemovePlanType::NOT_INSTALLED, RequestType::USER_REQUESTED));
-                continue;
-            }
+            RemoveAdjacencyProvider(const StatusParagraphs& status_db, const std::vector<StatusParagraph*>& installed_ports, const std::unordered_set<PackageSpec>& specs_as_set)
+                : status_db(status_db)
+                , installed_ports(installed_ports)
+                , specs_as_set(specs_as_set) { }
 
-            for (const std::unique_ptr<StatusParagraph>& an_installed_package : status_db)
+            std::vector<PackageSpec> adjacency_list(const RemovePlanAction& p) const override
             {
-                if (an_installed_package->want != Want::INSTALL)
-                    continue;
-                if (an_installed_package->package.spec.triplet() != spec.triplet())
-                    continue;
+                if (p.plan_type == RemovePlanType::NOT_INSTALLED)
+                {
+                    return {};
+                }
 
-                const std::vector<std::string>& deps = an_installed_package->package.depends;
-                if (std::find(deps.begin(), deps.end(), spec.name()) == deps.end())
+                const PackageSpec& spec = p.spec;
+                std::vector<PackageSpec> dependents;
+                for (const StatusParagraph* an_installed_package : installed_ports)
                 {
-                    continue;
+                    if (an_installed_package->package.spec.triplet() != spec.triplet())
+                        continue;
+
+                    const std::vector<std::string>& deps = an_installed_package->package.depends;
+                    if (std::find(deps.begin(), deps.end(), spec.name()) == deps.end())
+                        continue;
+
+                    dependents.push_back(an_installed_package->package.spec);
                 }
 
-                graph.add_edge(spec, an_installed_package.get()->package.spec);
-                examine_stack.push_back(an_installed_package.get()->package.spec);
+                return dependents;
             }
 
-            const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
-            was_examined.emplace(spec, RemovePlanAction(RemovePlanType::REMOVE, request_type));
-        }
-
-        std::vector<PackageSpecWithRemovePlan> ret;
+            RemovePlanAction load_vertex_data(const PackageSpec& spec) const override
+            {
+                const RequestType request_type = specs_as_set.find(spec) != specs_as_set.end() ? RequestType::USER_REQUESTED : RequestType::AUTO_SELECTED;
+                const StatusParagraphs::const_iterator it = status_db.find_installed(spec);
+                if (it == status_db.end())
+                {
+                    return RemovePlanAction{ spec, RemovePlanType::NOT_INSTALLED, request_type };
+                }
+                return RemovePlanAction{ spec, RemovePlanType::REMOVE, request_type };
+            }
+        };
 
-        const std::vector<PackageSpec> pkgs = graph.find_topological_sort();
-        for (const PackageSpec& pkg : pkgs)
-        {
-            ret.push_back(PackageSpecWithRemovePlan(pkg, std::move(was_examined[pkg])));
-        }
-        return ret;
+        const std::vector<StatusParagraph*>& installed_ports = get_installed_ports(status_db);
+        const std::unordered_set<PackageSpec> specs_as_set(specs.cbegin(), specs.cend());
+        return Graphs::topological_sort(specs, RemoveAdjacencyProvider{ status_db, installed_ports, specs_as_set });
     }
 }
diff --git a/toolsrc/src/vcpkg_Strings.cpp b/toolsrc/src/vcpkg_Strings.cpp
index 26dc6388b..3d9895436 100644
--- a/toolsrc/src/vcpkg_Strings.cpp
+++ b/toolsrc/src/vcpkg_Strings.cpp
@@ -1,5 +1,6 @@
 #include "pch.h"
 #include "vcpkg_Strings.h"
+#include "vcpkg_Util.h"
 
 namespace vcpkg::Strings::details
 {
@@ -98,10 +99,10 @@ namespace vcpkg::Strings
             trim(&s);
         }
 
-        strings->erase(std::remove_if(strings->begin(), strings->end(), [](const std::string& s)-> bool
-                                      {
-                                          return s == "";
-                                      }), strings->end());
+        Util::keep_if(*strings, [](const std::string& s)-> bool
+        {
+            return s != "";
+        });
     }
 
     std::vector<std::string> split(const std::string& s, const std::string& delimiter)
diff --git a/toolsrc/src/vcpkglib.cpp b/toolsrc/src/vcpkglib.cpp
index cc70b86b0..6cfc741e1 100644
--- a/toolsrc/src/vcpkglib.cpp
+++ b/toolsrc/src/vcpkglib.cpp
@@ -5,6 +5,7 @@
 #include "metrics.h"
 #include "vcpkg_Util.h"
 #include "vcpkg_Strings.h"
+#include "vcpkg_Util.h"
 
 namespace vcpkg
 {
@@ -200,12 +201,10 @@ namespace vcpkg
             upgrade_to_slash_terminated_sorted_format(fs, &installed_files_of_current_pgh, listfile_path);
 
             // Remove the directories
-            installed_files_of_current_pgh.erase(
-                std::remove_if(installed_files_of_current_pgh.begin(), installed_files_of_current_pgh.end(), [](const std::string& file) -> bool
-                               {
-                                   return file.back() == '/';
-                               }
-                ), installed_files_of_current_pgh.end());
+            Util::keep_if(installed_files_of_current_pgh, [](const std::string& file) -> bool
+            {
+                return file.back() != '/';
+            });
 
             StatusParagraphAndAssociatedFiles pgh_and_files = { *pgh, SortedVector<std::string>(std::move(installed_files_of_current_pgh)) };
             installed_files.push_back(std::move(pgh_and_files));