Merge branch 'master' into default_triplet

# Conflicts:
#	toolsrc/include/vcpkg_cmd_arguments.h
#	toolsrc/src/commands_installation.cpp
#	toolsrc/src/vcpkg_cmd_arguments.cpp

11 files changed, 161 insertions, 49 deletions

diff --git a/toolsrc/include/vcpkg_Dependencies.h b/toolsrc/include/vcpkg_Dependencies.h
new file mode 100644
index 000000000..94aa51f99
--- /dev/null
+++ b/toolsrc/include/vcpkg_Dependencies.h
@@ -0,0 +1,13 @@
+#pragma once
+#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);
+
+    std::unordered_set<package_spec> find_unmet_dependencies(const vcpkg_paths& paths, const std::vector<package_spec>& specs, const StatusParagraphs& status_db);
+}}
diff --git a/toolsrc/include/vcpkg_Maps.h b/toolsrc/include/vcpkg_Maps.h
new file mode 100644
index 000000000..5b7b8ed46
--- /dev/null
+++ b/toolsrc/include/vcpkg_Maps.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#include <unordered_map>
+#include <unordered_set>
+
+namespace vcpkg { namespace Maps
+{
+    template <typename K, typename V>
+    std::unordered_set<K> extract_key_set(const std::unordered_map<K, V>& input_map)
+    {
+        std::unordered_set<K> key_set;
+        for (auto const& element : input_map)
+        {
+            key_set.insert(element.first);
+        }
+        return key_set;
+    }
+}}
diff --git a/toolsrc/include/vcpkg_Sets.h b/toolsrc/include/vcpkg_Sets.h
new file mode 100644
index 000000000..7b330f31c
--- /dev/null
+++ b/toolsrc/include/vcpkg_Sets.h
@@ -0,0 +1,17 @@
+#pragma once
+
+#include "vcpkg_Checks.h"
+#include <unordered_set>
+
+namespace vcpkg { namespace Sets
+{
+    template <typename T, typename Container>
+    void remove_all(std::unordered_set<T>* input_set, Container remove_these)
+    {
+        Checks::check_throw(input_set != nullptr, "Input set cannot be null");
+        for (const T& r : remove_these)
+        {
+            input_set->erase(r);
+        }
+    }
+}}
diff --git a/toolsrc/include/vcpkg_cmd_arguments.h b/toolsrc/include/vcpkg_cmd_arguments.h
index 5a5075d23..704290589 100644
--- a/toolsrc/include/vcpkg_cmd_arguments.h
+++ b/toolsrc/include/vcpkg_cmd_arguments.h
@@ -28,7 +28,6 @@ namespace vcpkg
 
         void check_max_args(size_t arg_count, const char* example_text = nullptr) const;
         std::vector<package_spec> parse_all_arguments_as_package_specs(const vcpkg_paths& paths, const triplet& default_target_triplet, const char* example_text = nullptr) const;
-        std::vector<package_spec> extract_package_specs_with_unmet_dependencies(const vcpkg_paths& paths, const triplet& default_target_triplet, const StatusParagraphs& status_db) const;
 
     private:
         std::unordered_set<std::string> optional_command_arguments;
diff --git a/toolsrc/src/commands_installation.cpp b/toolsrc/src/commands_installation.cpp
index 0ca754dfc..0977dcf37 100644
--- a/toolsrc/src/commands_installation.cpp
+++ b/toolsrc/src/commands_installation.cpp
@@ -6,6 +6,7 @@
 #include "vcpkg_Files.h"
 #include "post_build_lint.h"
 #include "vcpkg_System.h"
+#include "vcpkg_Dependencies.h"
 
 namespace vcpkg
 {
@@ -59,18 +60,19 @@ namespace vcpkg
     {
         StatusParagraphs status_db = database_load_check(paths);
 
-        std::vector<package_spec> specs = args.extract_package_specs_with_unmet_dependencies(paths, default_target_triplet, status_db);
-        Checks::check_exit(!specs.empty(), "Specs cannot be empty");
-        std::string specs_string = to_string(specs[0]);
-        for (size_t i = 1; i < specs.size(); ++i)
+        std::vector<package_spec> specs = args.parse_all_arguments_as_package_specs(default_target_triplet);
+        std::vector<package_spec> install_plan = Dependencies::create_dependency_ordered_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]);
+        for (size_t i = 1; i < install_plan.size(); ++i)
         {
             specs_string.push_back(',');
-            specs_string.append(to_string(specs[i]));
+            specs_string.append(to_string(install_plan[i]));
         }
         TrackProperty("installplan", specs_string);
         Environment::ensure_utilities_on_path(paths);
 
-        for (const package_spec& spec : specs)
+        for (const package_spec& spec : install_plan)
         {
             if (status_db.find_installed(spec.name, spec.target_triplet) != status_db.end())
             {
@@ -111,7 +113,27 @@ namespace vcpkg
 
     void build_command(const vcpkg_cmd_arguments& args, const vcpkg_paths& paths, const triplet& default_target_triplet)
     {
+        // Currently the code won't work for multiple packages if one of them depends on another.
+        // Allowing only 1 package for now. 
+        args.check_max_args(1);
+
+        StatusParagraphs status_db = database_load_check(paths);
+
         std::vector<package_spec> specs = args.parse_all_arguments_as_package_specs(paths, default_target_triplet);
+        std::unordered_set<package_spec> unmet_dependencies = Dependencies::find_unmet_dependencies(paths, specs, status_db);
+        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)
+            {
+                System::println("    %s", p.name);
+            }
+            System::println("");
+            exit(EXIT_FAILURE);
+        }
+
         Environment::ensure_utilities_on_path(paths);
         for (const package_spec& spec : specs)
         {
diff --git a/toolsrc/src/vcpkg_Dependencies.cpp b/toolsrc/src/vcpkg_Dependencies.cpp
new file mode 100644
index 000000000..751b503c0
--- /dev/null
+++ b/toolsrc/src/vcpkg_Dependencies.cpp
@@ -0,0 +1,68 @@
+#include "vcpkg_Dependencies.h"
+#include <vector>
+#include "vcpkg_Graphs.h"
+#include "vcpkg_paths.h"
+#include "package_spec.h"
+#include "StatusParagraphs.h"
+#include <unordered_set>
+#include "vcpkg.h"
+#include "vcpkg_Maps.h"
+#include "vcpkg_Sets.h"
+
+namespace vcpkg { namespace Dependencies
+{
+    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
+        Graphs::Graph<package_spec> graph;
+        graph.add_vertices(examine_stack);
+
+        while (!examine_stack.empty())
+        {
+            package_spec spec = examine_stack.back();
+            examine_stack.pop_back();
+
+            if (was_examined.find(spec) != was_examined.end())
+            {
+                continue;
+            }
+
+            std::vector<std::string> dependencies_as_string = get_unmet_package_dependencies(paths, spec, status_db);
+
+            for (const std::string& dep_as_string : dependencies_as_string)
+            {
+                package_spec current_dep = {dep_as_string, spec.target_triplet};
+                auto it = status_db.find(current_dep.name, current_dep.target_triplet);
+                if (it != status_db.end() && (*it)->want == want_t::install)
+                {
+                    continue;
+                }
+
+                graph.add_edge(spec, current_dep);
+                if (was_examined.find(current_dep) == was_examined.end())
+                {
+                    examine_stack.push_back(std::move(current_dep));
+                }
+            }
+
+            was_examined.insert(spec);
+        }
+
+        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> find_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);
+        std::unordered_set<package_spec> key_set = Maps::extract_key_set(dependency_graph.adjacency_list());
+        Sets::remove_all(&key_set, specs);
+
+        return key_set;
+    }
+}}
diff --git a/toolsrc/src/vcpkg_cmd_arguments.cpp b/toolsrc/src/vcpkg_cmd_arguments.cpp
index d302ee42e..e0f3f04ee 100644
--- a/toolsrc/src/vcpkg_cmd_arguments.cpp
+++ b/toolsrc/src/vcpkg_cmd_arguments.cpp
@@ -179,48 +179,7 @@ namespace vcpkg
         }
     }
 
-    std::vector<package_spec> vcpkg_cmd_arguments::extract_package_specs_with_unmet_dependencies(const vcpkg_paths& paths, const triplet& default_target_triplet, const StatusParagraphs& status_db) const
-    {
-        std::vector<package_spec> specs = parse_all_arguments_as_package_specs(paths, default_target_triplet);
-        std::unordered_set<package_spec> had_its_immediate_dependencies_added;
-        Graphs::Graph<package_spec> graph;
-        graph.add_vertices(specs);
-
-        while (!specs.empty())
-        {
-            package_spec spec = specs.back();
-            specs.pop_back();
-
-            if (had_its_immediate_dependencies_added.find(spec) != had_its_immediate_dependencies_added.end())
-            {
-                continue;
-            }
-
-            std::vector<std::string> dependencies_as_string = get_unmet_package_dependencies(paths, spec, status_db);
-
-            for (const std::string& dep_as_string : dependencies_as_string)
-            {
-                package_spec current_dep = {dep_as_string, spec.target_triplet};
-                auto it = status_db.find(current_dep.name, current_dep.target_triplet);
-                if (it != status_db.end() && (*it)->want == want_t::install)
-                {
-                    continue;
-                }
-
-                graph.add_edge(spec, current_dep);
-                if (had_its_immediate_dependencies_added.find(current_dep) == had_its_immediate_dependencies_added.end())
-                {
-                    specs.push_back(std::move(current_dep));
-                }
-            }
-
-            had_its_immediate_dependencies_added.insert(spec);
-        }
-
-        return graph.find_topological_sort();
-    }
-
-    std::vector<package_spec> vcpkg_cmd_arguments::parse_all_arguments_as_package_specs(const vcpkg_paths& paths, const triplet& default_target_triplet, const char* example_text) const
+    std::vector<package_spec> vcpkg_cmd_arguments::parse_all_arguments_as_package_specs(const vcpkg_paths& const triplet& default_target_triplet, const char* example_text) const
     {
         size_t arg_count = command_arguments.size();
         if (arg_count < 1)
diff --git a/toolsrc/vcpkg/vcpkg.vcxproj b/toolsrc/vcpkg/vcpkg.vcxproj
index 065d1b9c5..a59683470 100644
--- a/toolsrc/vcpkg/vcpkg.vcxproj
+++ b/toolsrc/vcpkg/vcpkg.vcxproj
@@ -139,6 +139,7 @@
     <ClCompile Include="..\src\commands_update.cpp" />
     <ClCompile Include="..\src\vcpkg_cmd_arguments.cpp" />
     <ClCompile Include="..\src\commands_other.cpp" />
+    <ClCompile Include="..\src\vcpkg_Dependencies.cpp" />
     <ClCompile Include="..\src\vcpkg_Environment.cpp" />
     <ClCompile Include="..\src\commands_installation.cpp" />
     <ClCompile Include="..\src\commands_integration.cpp" />
@@ -149,6 +150,7 @@
   <ItemGroup>
     <ClInclude Include="..\include\vcpkg_cmd_arguments.h" />
     <ClInclude Include="..\include\vcpkg_Commands.h" />
+    <ClInclude Include="..\include\vcpkg_Dependencies.h" />
     <ClInclude Include="..\include\vcpkg_Environment.h" />
     <ClInclude Include="..\include\post_build_lint.h" />
   </ItemGroup>
diff --git a/toolsrc/vcpkg/vcpkg.vcxproj.filters b/toolsrc/vcpkg/vcpkg.vcxproj.filters
index 95aa0ceb7..2e8a343fc 100644
--- a/toolsrc/vcpkg/vcpkg.vcxproj.filters
+++ b/toolsrc/vcpkg/vcpkg.vcxproj.filters
@@ -66,6 +66,9 @@
     <ClCompile Include="..\src\commands_import.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
+    <ClCompile Include="..\src\vcpkg_Dependencies.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
   </ItemGroup>
   <ItemGroup>
     <ClInclude Include="..\include\post_build_lint.h">
@@ -80,5 +83,8 @@
     <ClInclude Include="..\include\vcpkg_Environment.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\include\vcpkg_Dependencies.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
   </ItemGroup>
 </Project>
\ No newline at end of file
diff --git a/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj b/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj
index 95cfd5764..d5e68fde3 100644
--- a/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj
+++ b/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj
@@ -131,6 +131,8 @@
     <ClInclude Include="..\include\vcpkg_Checks.h" />
     <ClInclude Include="..\include\vcpkg_Files.h" />
     <ClInclude Include="..\include\vcpkg_Graphs.h" />
+    <ClInclude Include="..\include\vcpkg_Maps.h" />
+    <ClInclude Include="..\include\vcpkg_Sets.h" />
     <ClInclude Include="..\include\vcpkg_Strings.h" />
     <ClInclude Include="..\include\vcpkg_System.h" />
   </ItemGroup>
diff --git a/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj.filters b/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj.filters
index a7e98c853..ae747d687 100644
--- a/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj.filters
+++ b/toolsrc/vcpkgcommon/vcpkgcommon.vcxproj.filters
@@ -50,5 +50,11 @@
     <ClInclude Include="..\include\opt_bool.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\include\vcpkg_Maps.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
+    <ClInclude Include="..\include\vcpkg_Sets.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
   </ItemGroup>
 </Project>
\ No newline at end of file