[depend-info] Fix bugs, add `--sort`, `--show-depth` and `--max-recurse` options (#7643)

* [depend-info] Follow same rules as vcpkg install

* [depend-info] Add --max-depth and --sort options

* [depend-info] Improve output readability (a tiny bit)

* [depend-info] Add --show-depth option

* [depend-info] Fix build on VS 2015

* [depend-info] Fix output of --dot and --dgml

4 files changed, 210 insertions, 138 deletions

diff --git a/toolsrc/include/vcpkg/base/strings.h b/toolsrc/include/vcpkg/base/strings.h
index a147a8373..0f25607df 100644
--- a/toolsrc/include/vcpkg/base/strings.h
+++ b/toolsrc/include/vcpkg/base/strings.h
@@ -1,6 +1,5 @@
 #pragma once
 
-
 #include <vcpkg/base/cstringview.h>
 #include <vcpkg/base/optional.h>
 #include <vcpkg/base/stringliteral.h>
diff --git a/toolsrc/include/vcpkg/commands.h b/toolsrc/include/vcpkg/commands.h
index 6a94b389a..8a502122e 100644
--- a/toolsrc/include/vcpkg/commands.h
+++ b/toolsrc/include/vcpkg/commands.h
@@ -56,7 +56,7 @@ namespace vcpkg::Commands
     namespace DependInfo
     {
         extern const CommandStructure COMMAND_STRUCTURE;
-        void perform_and_exit(const VcpkgCmdArguments& args, const VcpkgPaths& paths);
+        void perform_and_exit(const VcpkgCmdArguments& args, const VcpkgPaths& paths, const Triplet& default_triplet);
     }
 
     namespace Search
diff --git a/toolsrc/src/vcpkg/commands.cpp b/toolsrc/src/vcpkg/commands.cpp
index 54e9346ba..3ac568979 100644
--- a/toolsrc/src/vcpkg/commands.cpp
+++ b/toolsrc/src/vcpkg/commands.cpp
@@ -24,6 +24,7 @@ namespace vcpkg::Commands
             {"env", &Env::perform_and_exit},
             {"build-external", &BuildExternal::perform_and_exit},
             {"export", &Export::perform_and_exit},
+            {"depend-info", &DependInfo::perform_and_exit},
         };
         return t;
     }
@@ -38,7 +39,6 @@ namespace vcpkg::Commands
             {"integrate", &Integrate::perform_and_exit},
             {"owns", &Owns::perform_and_exit},
             {"update", &Update::perform_and_exit},
-            {"depend-info", &DependInfo::perform_and_exit},
             {"edit", &Edit::perform_and_exit},
             {"create", &Create::perform_and_exit},
             {"import", &Import::perform_and_exit},
diff --git a/toolsrc/src/vcpkg/commands.dependinfo.cpp b/toolsrc/src/vcpkg/commands.dependinfo.cpp
index 7c04a5a2f..8ca88dd56 100644
--- a/toolsrc/src/vcpkg/commands.dependinfo.cpp
+++ b/toolsrc/src/vcpkg/commands.dependinfo.cpp
@@ -4,65 +4,129 @@
 #include <vcpkg/base/system.print.h>

 #include <vcpkg/base/util.h>

 #include <vcpkg/commands.h>

+#include <vcpkg/dependencies.h>

 #include <vcpkg/help.h>

+#include <vcpkg/input.h>

+#include <vcpkg/install.h>

 #include <vcpkg/packagespec.h>

-#include <vcpkg/paragraphs.h>

-

-#include <memory>

-#include <vcpkg/dependencies.h>

 #include <vector>

 

+using vcpkg::Dependencies::AnyAction;

+using vcpkg::Dependencies::create_feature_install_plan;

+using vcpkg::Dependencies::InstallPlanAction;

 using vcpkg::Dependencies::PathsPortFileProvider;

 

 namespace vcpkg::Commands::DependInfo

 {

     constexpr StringLiteral OPTION_DOT = "--dot";

     constexpr StringLiteral OPTION_DGML = "--dgml";

-    constexpr StringLiteral OPTION_NO_RECURSE = "--no-recurse";

+    constexpr StringLiteral OPTION_SHOW_DEPTH = "--show-depth";

+    constexpr StringLiteral OPTION_MAX_RECURSE = "--max-recurse";

+    constexpr StringLiteral OPTION_SORT = "--sort";

+

+    constexpr int NO_RECURSE_LIMIT_VALUE = -1;

+

+    constexpr std::array<CommandSwitch, 3> DEPEND_SWITCHES = {{{OPTION_DOT, "Creates graph on basis of dot"},

+                                                               {OPTION_DGML, "Creates graph on basis of dgml"},

+                                                               {OPTION_SHOW_DEPTH, "Show recursion depth in output"}}};

 

-    constexpr std::array<CommandSwitch, 3> DEPEND_SWITCHES = {{

-        {OPTION_DOT, "Creates graph on basis of dot"},

-        {OPTION_DGML, "Creates graph on basis of dgml"},

-        {OPTION_NO_RECURSE,

-         "Computes only immediate dependencies of packages explicitly specified on the command-line"},

-    }};

+    constexpr std::array<CommandSetting, 2> DEPEND_SETTINGS = {

+        {{OPTION_MAX_RECURSE, "Set max recursion depth, a value of -1 indicates no limit"},

+         {OPTION_SORT,

+          "Set sort order for the list of dependencies, accepted values are: lexicographical, topological (default), "

+          "reverse"}}};

 

     const CommandStructure COMMAND_STRUCTURE = {

-        Help::create_example_string(R"###(depend-info [pat])###"),

+        Help::create_example_string("depend-info sqlite3"),

         0,

         SIZE_MAX,

-        {DEPEND_SWITCHES, {}},

+        {DEPEND_SWITCHES, DEPEND_SETTINGS},

         nullptr,

     };

 

-    std::string replace_dashes_with_underscore(const std::string& input)

+    struct PackageDependInfo

     {

-        std::string output = input;

-        std::replace(output.begin(), output.end(), '-', '_');

-        return output;

+        std::string package;

+        int depth;

+        std::set<std::string> features;

+        std::vector<std::string> dependencies;

+    };

+

+    enum SortMode

+    {

+        Lexicographical = 0,

+        Topological,

+        ReverseTopological,

+        Default = Topological

+    };

+

+    int get_max_depth(const ParsedArguments& options)

+    {

+        auto iter = options.settings.find(OPTION_MAX_RECURSE);

+        if (iter != options.settings.end())

+        {

+            std::string value = iter->second;

+            try

+            {

+                return std::stoi(value);

+            }

+            catch (std::exception&)

+            {

+                Checks::exit_with_message(VCPKG_LINE_INFO, "Value of --max-depth must be an integer");

+            }

+        }

+        // No --max-depth set, default to no limit.

+        return NO_RECURSE_LIMIT_VALUE;

     }

 

-    std::string create_dot_as_string(const std::vector<const SourceControlFile*>& source_control_files)

+    SortMode get_sort_mode(const ParsedArguments& options)

+    {

+        constexpr StringLiteral OPTION_SORT_LEXICOGRAPHICAL = "lexicographical";

+        constexpr StringLiteral OPTION_SORT_TOPOLOGICAL = "topological";

+        constexpr StringLiteral OPTION_SORT_REVERSE = "reverse";

+

+        static const std::map<std::string, SortMode> sortModesMap{{OPTION_SORT_LEXICOGRAPHICAL, Lexicographical},

+                                                                  {OPTION_SORT_TOPOLOGICAL, Topological},

+                                                                  {OPTION_SORT_REVERSE, ReverseTopological}};

+

+        auto iter = options.settings.find(OPTION_SORT);

+        if (iter != options.settings.end())

+        {

+            const std::string value = Strings::ascii_to_lowercase(std::string{iter->second});

+            auto it = sortModesMap.find(value);

+            if (it != sortModesMap.end())

+            {

+                return it->second;

+            }

+            Checks::exit_with_message(VCPKG_LINE_INFO,

+                                      "Value of --sort must be one of `%s`, `%s`, or `%s`",

+                                      OPTION_SORT_LEXICOGRAPHICAL,

+                                      OPTION_SORT_TOPOLOGICAL,

+                                      OPTION_SORT_REVERSE);

+        }

+        return Default;

+    }

+

+    std::string create_dot_as_string(const std::vector<PackageDependInfo>& depend_info)

     {

         int empty_node_count = 0;

 

         std::string s;

         s.append("digraph G{ rankdir=LR; edge [minlen=3]; overlap=false;");

 

-        for (const auto& source_control_file : source_control_files)

+        for (const auto& package : depend_info)

         {

-            const SourceParagraph& source_paragraph = *source_control_file->core_paragraph;

-            if (source_paragraph.depends.empty())

+            if (package.dependencies.empty())

             {

                 empty_node_count++;

                 continue;

             }

 

-            const std::string name = replace_dashes_with_underscore(source_paragraph.name);

+            const std::string name = Strings::replace_all(std::string{ package.package }, "-", "_");

             s.append(Strings::format("%s;", name));

-            for (const Dependency& d : source_paragraph.depends)

+            for (const auto &d : package.dependencies)

             {

-                const std::string dependency_name = replace_dashes_with_underscore(d.depend.name);

+                const std::string dependency_name = Strings::replace_all(std::string{ d }, "-", "_");

                 s.append(Strings::format("%s -> %s;", name, dependency_name));

             }

         }

@@ -71,39 +135,22 @@ namespace vcpkg::Commands::DependInfo
         return s;

     }

 

-    std::string create_dgml_as_string(const std::vector<const SourceControlFile*>& source_control_files)

+    std::string create_dgml_as_string(const std::vector<PackageDependInfo>& depend_info)

     {

         std::string s;

         s.append("<?xml version=\"1.0\" encoding=\"utf-8\"?>");

         s.append("<DirectedGraph xmlns=\"http://schemas.microsoft.com/vs/2009/dgml\">");

 

         std::string nodes, links;

-        for (const auto& source_control_file : source_control_files)

+        for (const auto& package : depend_info)

         {

-            const SourceParagraph& source_paragraph = *source_control_file->core_paragraph;

-            const std::string name = source_paragraph.name;

+            const std::string name = package.package;

             nodes.append(Strings::format("<Node Id=\"%s\" />", name));

 

             // Iterate over dependencies.

-            for (const Dependency& d : source_paragraph.depends)

-            {

-                if (d.qualifier.empty())

-                    links.append(Strings::format("<Link Source=\"%s\" Target=\"%s\" />", name, d.depend.name));

-                else

-                    links.append(Strings::format(

-                        "<Link Source=\"%s\" Target=\"%s\" StrokeDashArray=\"4\" />", name, d.depend.name));

-            }

-

-            // Iterate over feature dependencies.

-            const std::vector<std::unique_ptr<FeatureParagraph>>& feature_paragraphs =

-                source_control_file->feature_paragraphs;

-            for (const auto& feature_paragraph : feature_paragraphs)

+            for (const auto& d : package.dependencies)

             {

-                for (const Dependency& d : feature_paragraph->depends)

-                {

-                    links.append(Strings::format(

-                        "<Link Source=\"%s\" Target=\"%s\" StrokeDashArray=\"4\" />", name, d.depend.name));

-                }

+                links.append(Strings::format("<Link Source=\"%s\" Target=\"%s\" />", name, d));

             }

         }

 

@@ -116,136 +163,162 @@ namespace vcpkg::Commands::DependInfo
     }

 

     std::string create_graph_as_string(const std::unordered_set<std::string>& switches,

-                                       const std::vector<const SourceControlFile*>& source_control_files)

+                                       const std::vector<PackageDependInfo>& depend_info)

     {

         if (Util::Sets::contains(switches, OPTION_DOT))

         {

-            return create_dot_as_string(source_control_files);

+            return create_dot_as_string(depend_info);

         }

         else if (Util::Sets::contains(switches, OPTION_DGML))

         {

-            return create_dgml_as_string(source_control_files);

+            return create_dgml_as_string(depend_info);

         }

         return "";

     }

 

-    void build_dependencies_list(std::set<std::string>& packages_to_keep,

-                                 const std::string& requested_package,

-                                 const std::vector<const SourceControlFile*>& source_control_files,

-                                 const std::unordered_set<std::string>& switches)

+    void assign_depth_to_dependencies(const std::string& package,

+                                      const int depth,

+                                      const int max_depth,

+                                      std::map<std::string, PackageDependInfo>& dependencies_map)

     {

-        auto maybe_requested_spec = ParsedSpecifier::from_string(requested_package);

-        // TODO: move this check to the top-level invocation of this function since

-        // argument `requested_package` shall always be valid in inner-level invocation.

-        if (!maybe_requested_spec.has_value())

-        {

-            System::print2(System::Color::warning,

-                           "'",

-                           requested_package,

-                           "' is not a valid package specifier: ",

-                           vcpkg::to_string(maybe_requested_spec.error()),

-                           "\n");

-            return;

-        }

-        auto requested_spec = maybe_requested_spec.get();

+        auto iter = dependencies_map.find(package);

+        Checks::check_exit(VCPKG_LINE_INFO, iter != dependencies_map.end(), "Package not found in dependency graph");

 

-        const auto source_control_file =

-            Util::find_if(source_control_files, [&requested_spec](const auto& source_control_file) {

-                return source_control_file->core_paragraph->name == requested_spec->name;

-            });

+        PackageDependInfo& info = iter->second;

 

-        if (source_control_file != source_control_files.end())

+        if (depth > info.depth)

         {

-            const auto new_package = packages_to_keep.insert(requested_spec->name).second;

-

-            if (new_package && !Util::Sets::contains(switches, OPTION_NO_RECURSE))

+            info.depth = depth;

+            if (depth < max_depth || max_depth == NO_RECURSE_LIMIT_VALUE)

             {

-                for (const auto& dependency : (*source_control_file)->core_paragraph->depends)

-                {

-                    build_dependencies_list(packages_to_keep, dependency.depend.name, source_control_files, switches);

-                }

-

-                // Collect features with `*` considered

-                std::set<const FeatureParagraph*> collected_features;

-                for (const auto& requested_feature_name : requested_spec->features)

+                for (auto&& dependency : info.dependencies)

                 {

-                    if (requested_feature_name == "*")

-                    {

-                        for (auto&& feature_paragraph : (*source_control_file)->feature_paragraphs)

-                        {

-                            collected_features.insert(std::addressof(Util::as_const(*feature_paragraph)));

-                        }

-                        continue;

-                    }

-                    auto maybe_feature = (*source_control_file)->find_feature(requested_feature_name);

-                    if (auto&& feature_paragraph = maybe_feature.get())

-                    {

-                        collected_features.insert(std::addressof(Util::as_const(*feature_paragraph)));

-                    }

-                    else

-                    {

-                        System::print2(System::Color::warning,

-                                       "dependency '",

-                                       requested_feature_name,

-                                       "' of package '",

-                                       requested_spec->name,

-                                       "' does not exist\n");

-                        continue;

-                    }

-                }

-                for (auto feature_paragraph : collected_features)

-                {

-                    for (const auto& dependency : feature_paragraph->depends)

-                    {

-                        build_dependencies_list(

-                            packages_to_keep, dependency.depend.name, source_control_files, switches);

-                    }

+                    assign_depth_to_dependencies(dependency, depth + 1, max_depth, dependencies_map);

                 }

             }

         }

-        else

+    };

+

+    std::vector<PackageDependInfo> extract_depend_info(const std::vector<const InstallPlanAction*>& install_actions,

+                                                       const int max_depth)

+    {

+        std::map<std::string, PackageDependInfo> package_dependencies;

+        for (const InstallPlanAction* pia : install_actions)

         {

-            System::print2(System::Color::warning, "package '", requested_package, "' does not exist\n");

+            const InstallPlanAction& install_action = *pia;

+

+            const std::vector<std::string> dependencies =

+                Util::fmap(install_action.computed_dependencies, [](const PackageSpec& spec) { return spec.name(); });

+

+            std::set<std::string> features{install_action.feature_list};

+            features.erase("core");

+

+            std::string port_name = install_action.spec.name();

+

+            PackageDependInfo info {port_name, -1, features, dependencies};

+            package_dependencies.emplace(port_name, std::move(info));

         }

+

+        const InstallPlanAction& init = *install_actions.back();

+        assign_depth_to_dependencies(init.spec.name(), 0, max_depth, package_dependencies);

+

+        std::vector<PackageDependInfo> out =

+            Util::fmap(package_dependencies, [](auto&& kvpair) -> PackageDependInfo { return kvpair.second; });

+        Util::erase_remove_if(out, [](auto&& info) { return info.depth < 0; });

+        return out;

     }

 

-    void perform_and_exit(const VcpkgCmdArguments& args, const VcpkgPaths& paths)

+    void perform_and_exit(const VcpkgCmdArguments& args, const VcpkgPaths& paths, const Triplet& default_triplet)

     {

         const ParsedArguments options = args.parse_arguments(COMMAND_STRUCTURE);

+        const int max_depth = get_max_depth(options);

+        const SortMode sort_mode = get_sort_mode(options);

+        const bool show_depth = Util::Sets::contains(options.switches, OPTION_SHOW_DEPTH);

 

-        // TODO: Optimize implementation, current implementation needs to load all ports from disk which is too slow.

-        PathsPortFileProvider provider(paths, args.overlay_ports.get());

-        auto source_control_files =

-            Util::fmap(provider.load_all_control_files(),

-                       [](auto&& scfl) -> const SourceControlFile* { return scfl->source_control_file.get(); });

+        const std::vector<FullPackageSpec> specs = Util::fmap(args.command_arguments, [&](auto&& arg) {

+            return Input::check_and_get_full_package_spec(

+                std::string{arg}, default_triplet, COMMAND_STRUCTURE.example_text);

+        });

 

-        if (args.command_arguments.size() >= 1)

+        for (auto&& spec : specs)

         {

-            std::set<std::string> packages_to_keep;

-            for (const auto& requested_package : args.command_arguments)

+            Input::check_triplet(spec.package_spec.triplet(), paths);

+        }

+

+        PathsPortFileProvider provider(paths, args.overlay_ports.get());

+

+        // By passing an empty status_db, we should get a plan containing all dependencies.

+        // All actions in the plan should be install actions, as there's no installed packages to remove.

+        StatusParagraphs status_db;

+        std::vector<AnyAction> action_plan =

+            create_feature_install_plan(provider, FullPackageSpec::to_feature_specs(specs), status_db);

+        std::vector<const InstallPlanAction*> install_actions = Util::fmap(action_plan, [&](const AnyAction& action) {

+            if (auto install_action = action.install_action.get())

             {

-                build_dependencies_list(packages_to_keep, requested_package, source_control_files, options.switches);

+                return install_action;

             }

+            Checks::exit_with_message(VCPKG_LINE_INFO, "Only install actions should exist in the plan");

+        });

 

-            Util::erase_remove_if(source_control_files, [&packages_to_keep](const auto& source_control_file) {

-                return !Util::Sets::contains(packages_to_keep, source_control_file->core_paragraph->name);

-            });

-        }

+        std::vector<PackageDependInfo> depend_info = extract_depend_info(install_actions, max_depth);

 

         if (Util::Sets::contains(options.switches, OPTION_DOT) || Util::Sets::contains(options.switches, OPTION_DGML))

         {

-            const std::string graph_as_string = create_graph_as_string(options.switches, source_control_files);

+            const std::vector<const SourceControlFile*> source_control_files =

+                Util::fmap(install_actions, [](const InstallPlanAction* install_action) {

+                    const SourceControlFileLocation& scfl =

+                        install_action->source_control_file_location.value_or_exit(VCPKG_LINE_INFO);

+                    return const_cast<const SourceControlFile*>(scfl.source_control_file.get());

+                });

+

+            const std::string graph_as_string = create_graph_as_string(options.switches, depend_info);

             System::print2(graph_as_string, '\n');

             Checks::exit_success(VCPKG_LINE_INFO);

         }

 

-        for (auto&& source_control_file : source_control_files)

+

+        // TODO: Improve this code

+        auto lex = [](const PackageDependInfo& lhs, const PackageDependInfo& rhs) -> bool {

+            return lhs.package < rhs.package;

+        };

+        auto topo = [](const PackageDependInfo& lhs, const PackageDependInfo& rhs) -> bool {

+            return lhs.depth > rhs.depth;

+        };

+        auto reverse = [topo](const PackageDependInfo& lhs, const PackageDependInfo& rhs) -> bool {

+            return lhs.depth < rhs.depth;

+        };

+

+        switch (sort_mode)

         {

-            const SourceParagraph& source_paragraph = *source_control_file->core_paragraph.get();

-            const auto s = Strings::join(", ", source_paragraph.depends, [](const Dependency& d) { return d.name(); });

-            System::print2(source_paragraph.name, ": ", s, "\n");

+            case SortMode::Lexicographical: std::sort(std::begin(depend_info), std::end(depend_info), lex); break;

+            case SortMode::ReverseTopological:

+                std::sort(std::begin(depend_info), std::end(depend_info), reverse);

+                break;

+            case SortMode::Topological: std::sort(std::begin(depend_info), std::end(depend_info), topo); break;

+            default: Checks::unreachable(VCPKG_LINE_INFO);

         }

 

+        for (auto&& info : depend_info)

+        {

+            if (info.depth >= 0)

+            {

+                std::string features = Strings::join(", ", info.features);

+                const std::string dependencies = Strings::join(", ", info.dependencies);

+

+                if (show_depth)

+                {

+                    System::print2(System::Color::error, "(", info.depth, ") ");

+                }

+                System::print2(System::Color::success, info.package);

+                if (!features.empty())

+                {

+                    System::print2("[");

+                    System::print2(System::Color::warning, features);

+                    System::print2("]");

+                }

+                System::print2(": ", dependencies, "\n");

+            }

+        }

         Checks::exit_success(VCPKG_LINE_INFO);

     }

 }