<commit_before>#include "command.hh"
#include "store-api.hh"
#include "progress-bar.hh"
#include "fs-accessor.hh"
#include "shared.hh"

#include <queue>

using namespace nix;

static std::string hilite(const std::string & s, size_t pos, size_t len,
    const std::string & colour = ANSI_RED)
{
    return
        std::string(s, 0, pos)
        + colour
        + std::string(s, pos, len)
        + ANSI_NORMAL
        + std::string(s, pos + len);
}

static std::string filterPrintable(const std::string & s)
{
    std::string res;
    for (char c : s)
        res += isprint(c) ? c : '.';
    return res;
}

struct CmdWhyDepends : SourceExprCommand
{
    std::string _package, _dependency;
    bool all = false;

    CmdWhyDepends()
    {
        expectArg("package", &_package);
        expectArg("dependency", &_dependency);

        addFlag({
            .longName = "all",
            .shortName = 'a',
            .description = "show all edges in the dependency graph leading from 'package' to 'dependency', rather than just a shortest path",
            .handler = {&all, true},
        });
    }

    std::string description() override
    {
        return "show why a package has another package in its closure";
    }

    Examples examples() override
    {
        return {
            Example{
                "To show one path through the dependency graph leading from Hello to Glibc:",
                "nix why-depends nixpkgs.hello nixpkgs.glibc"
            },
            Example{
                "To show all files and paths in the dependency graph leading from Thunderbird to libX11:",
                "nix why-depends --all nixpkgs.thunderbird nixpkgs.xorg.libX11"
            },
            Example{
                "To show why Glibc depends on itself:",
                "nix why-depends nixpkgs.glibc nixpkgs.glibc"
            },
        };
    }

    Category category() override { return catSecondary; }

    void run(ref<Store> store) override
    {
        auto package = parseInstallable(*this, store, _package, false);
        auto packagePath = toStorePath(store, Build, package);
        auto dependency = parseInstallable(*this, store, _dependency, false);
        auto dependencyPath = toStorePath(store, NoBuild, dependency);
        auto dependencyPathHash = dependencyPath.hashPart();

        StorePathSet closure;
        store->computeFSClosure({packagePath}, closure, false, false);

        if (!closure.count(dependencyPath)) {
            printError("'%s' does not depend on '%s'", package->what(), dependency->what());
            return;
        }

        stopProgressBar(); // FIXME

        auto accessor = store->getFSAccessor();

        auto const inf = std::numeric_limits<size_t>::max();

        struct Node
        {
            StorePath path;
            StorePathSet refs;
            StorePathSet rrefs;
            size_t dist = inf;
            Node * prev = nullptr;
            bool queued = false;
            bool visited = false;
        };

        std::map<StorePath, Node> graph;

        for (auto & path : closure)
            graph.emplace(path, Node { .path = path, .refs = store->queryPathInfo(path)->references });

        // Transpose the graph.
        for (auto & node : graph)
            for (auto & ref : node.second.refs)
                graph.find(ref)->second.rrefs.insert(node.first);

        /* Run Dijkstra's shortest path algorithm to get the distance
           of every path in the closure to 'dependency'. */
        graph.emplace(dependencyPath, Node { .path = dependencyPath, .dist = 0 });

        std::priority_queue<Node *> queue;

        queue.push(&graph.at(dependencyPath));

        while (!queue.empty()) {
            auto & node = *queue.top();
            queue.pop();

            for (auto & rref : node.rrefs) {
                auto & node2 = graph.at(rref);
                auto dist = node.dist + 1;
                if (dist < node2.dist) {
                    node2.dist = dist;
                    node2.prev = &node;
                    if (!node2.queued) {
                        node2.queued = true;
                        queue.push(&node2);
                    }
                }

            }
        }

        /* Print the subgraph of nodes that have 'dependency' in their
           closure (i.e., that have a non-infinite distance to
           'dependency'). Print every edge on a path between `package`
           and `dependency`. */
        std::function<void(Node &, const string &, const string &)> printNode;<commit_msg>nix why-depends: Fix shortest path calculation<commit_after>#include "command.hh"
#include "store-api.hh"
#include "progress-bar.hh"
#include "fs-accessor.hh"
#include "shared.hh"

#include <queue>

using namespace nix;

static std::string hilite(const std::string & s, size_t pos, size_t len,
    const std::string & colour = ANSI_RED)
{
    return
        std::string(s, 0, pos)
        + colour
        + std::string(s, pos, len)
        + ANSI_NORMAL
        + std::string(s, pos + len);
}

static std::string filterPrintable(const std::string & s)
{
    std::string res;
    for (char c : s)
        res += isprint(c) ? c : '.';
    return res;
}

struct CmdWhyDepends : SourceExprCommand
{
    std::string _package, _dependency;
    bool all = false;

    CmdWhyDepends()
    {
        expectArg("package", &_package);
        expectArg("dependency", &_dependency);

        addFlag({
            .longName = "all",
            .shortName = 'a',
            .description = "show all edges in the dependency graph leading from 'package' to 'dependency', rather than just a shortest path",
            .handler = {&all, true},
        });
    }

    std::string description() override
    {
        return "show why a package has another package in its closure";
    }

    Examples examples() override
    {
        return {
            Example{
                "To show one path through the dependency graph leading from Hello to Glibc:",
                "nix why-depends nixpkgs.hello nixpkgs.glibc"
            },
            Example{
                "To show all files and paths in the dependency graph leading from Thunderbird to libX11:",
                "nix why-depends --all nixpkgs.thunderbird nixpkgs.xorg.libX11"
            },
            Example{
                "To show why Glibc depends on itself:",
                "nix why-depends nixpkgs.glibc nixpkgs.glibc"
            },
        };
    }

    Category category() override { return catSecondary; }

    void run(ref<Store> store) override
    {
        auto package = parseInstallable(*this, store, _package, false);
        auto packagePath = toStorePath(store, Build, package);
        auto dependency = parseInstallable(*this, store, _dependency, false);
        auto dependencyPath = toStorePath(store, NoBuild, dependency);
        auto dependencyPathHash = dependencyPath.hashPart();

        StorePathSet closure;
        store->computeFSClosure({packagePath}, closure, false, false);

        if (!closure.count(dependencyPath)) {
            printError("'%s' does not depend on '%s'", package->what(), dependency->what());
            return;
        }

        stopProgressBar(); // FIXME

        auto accessor = store->getFSAccessor();

        auto const inf = std::numeric_limits<size_t>::max();

        struct Node
        {
            StorePath path;
            StorePathSet refs;
            StorePathSet rrefs;
            size_t dist = inf;
            Node * prev = nullptr;
            bool queued = false;
            bool visited = false;
        };

        std::map<StorePath, Node> graph;

        for (auto & path : closure)
            graph.emplace(path, Node {
                .path = path,
                .refs = store->queryPathInfo(path)->references,
                .dist = path == dependencyPath ? 0 : inf
            });

        // Transpose the graph.
        for (auto & node : graph)
            for (auto & ref : node.second.refs)
                graph.find(ref)->second.rrefs.insert(node.first);

        /* Run Dijkstra's shortest path algorithm to get the distance
           of every path in the closure to 'dependency'. */
        std::priority_queue<Node *> queue;

        queue.push(&graph.at(dependencyPath));

        while (!queue.empty()) {
            auto & node = *queue.top();
            queue.pop();

            for (auto & rref : node.rrefs) {
                auto & node2 = graph.at(rref);
                auto dist = node.dist + 1;
                if (dist < node2.dist) {
                    node2.dist = dist;
                    node2.prev = &node;
                    if (!node2.queued) {
                        node2.queued = true;
                        queue.push(&node2);
                    }
                }

            }
        }

        /* Print the subgraph of nodes that have 'dependency' in their
           closure (i.e., that have a non-infinite distance to
           'dependency'). Print every edge on a path between `package`
           and `dependency`. */
        std::function<void(Node &, const string &, const string &)> printNode;
{'fraction_non_alphanumeric': 0.11077158135981666, 'fraction_numerical': 0.0030557677616501145, 'mean_word_length': 1.805019895928987, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5288154', 'n_tokens_mistral': 2618, 'n_tokens_neox': 2481, 'n_words': 725}