diff options
Diffstat (limited to 'src/nix/why-depends.cc')
| -rw-r--r-- | src/nix/why-depends.cc | 190 |
1 files changed, 156 insertions, 34 deletions
diff --git a/src/nix/why-depends.cc b/src/nix/why-depends.cc index da37e5eb04f9..a6750ac95cac 100644 --- a/src/nix/why-depends.cc +++ b/src/nix/why-depends.cc @@ -5,26 +5,44 @@ #include "progress-bar.hh" #include "fs-accessor.hh" +#include <queue> + using namespace nix; -static std::string hilite(const std::string & s, size_t pos, size_t len) +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) - + ANSI_RED + + 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); + + mkFlag() + .longName("all") + .shortName('a') + .description("show all edges in the dependency graph leading from 'package' to 'dependency', rather than just a shortest path") + .set(&all, true); } std::string name() override @@ -67,66 +85,170 @@ struct CmdWhyDepends : SourceExprCommand auto accessor = store->getFSAccessor(); - // FIXME: show the path through the dependency graph. + auto const inf = std::numeric_limits<size_t>::max(); + + struct Node + { + Path path; + PathSet refs; + PathSet rrefs; + size_t dist = inf; + Node * prev = nullptr; + bool queued = false; + bool visited = false; + }; + + std::map<Path, Node> graph; + + for (auto & path : closure) + graph.emplace(path, Node{path, store->queryPathInfo(path)->references}); + + // Transpose the graph. + for (auto & node : graph) + for (auto & ref : node.second.refs) + graph[ref].rrefs.insert(node.first); - bool first = true; + /* Run Dijkstra's shortest path algorithm to get the distance + of every path in the closure to 'dependency'. */ + graph[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); + } + } + + } + } - for (auto & path : closure) { + /* 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; - if (path == dependencyPath && packagePath != dependencyPath) - continue; + const string treeConn = "├───"; + const string treeLast = "└───"; + const string treeLine = "│ "; + const string treeNull = " "; - if (!store->queryPathInfo(path)->references.count(dependencyPath)) - continue; + struct BailOut { }; - if (!first) std::cerr << "\n"; - first = false; + printNode = [&](Node & node, const string & firstPad, const string & tailPad) { + assert(node.dist != inf); + std::cerr << fmt("%s%s%s%s" ANSI_NORMAL "\n", + firstPad, + node.visited ? "\e[38;5;244m" : "", + firstPad != "" ? "=> " : "", + node.path); - std::cerr << fmt("%s:\n", path); + if (node.path == dependencyPath && !all) throw BailOut(); - std::function<void(const Path &)> recurse; + if (node.visited) return; + node.visited = true; - recurse = [&](const Path & p) { + /* Sort the references by distance to `dependency` to + ensure that the shortest path is printed first. */ + std::multimap<size_t, Node *> refs; + std::set<std::string> hashes; + + for (auto & ref : node.refs) { + if (ref == node.path) continue; + auto & node2 = graph.at(ref); + if (node2.dist == inf) continue; + refs.emplace(node2.dist, &node2); + hashes.insert(storePathToHash(node2.path)); + } + + /* For each reference, find the files and symlinks that + contain the reference. */ + std::map<std::string, Strings> hits; + + std::function<void(const Path &)> visitPath; + + visitPath = [&](const Path & p) { auto st = accessor->stat(p); - auto p2 = p == path ? "/" : std::string(p, path.size() + 1); + auto p2 = p == node.path ? "/" : std::string(p, node.path.size() + 1); + + auto getColour = [&](const std::string & hash) { + return hash == dependencyPathHash ? ANSI_GREEN : ANSI_BLUE; + }; if (st.type == FSAccessor::Type::tDirectory) { auto names = accessor->readDirectory(p); for (auto & name : names) - recurse(p + "/" + name); + visitPath(p + "/" + name); } else if (st.type == FSAccessor::Type::tRegular) { auto contents = accessor->readFile(p); - auto pos = contents.find(dependencyPathHash); - if (pos != std::string::npos) { - size_t margin = 16; - auto pos2 = pos >= margin ? pos - margin : 0; - std::string fragment; - for (char c : std::string(contents, pos2, - pos - pos2 + dependencyPathHash.size() + margin)) - { - fragment += isprint(c) ? c : '.'; - } - std::cerr << fmt(" %s: …%s…\n", - p2, - hilite(fragment, pos - pos2, storePathHashLen)); + for (auto & hash : hashes) { + auto pos = contents.find(hash); + if (pos != std::string::npos) { + size_t margin = 16; + auto pos2 = pos >= margin ? pos - margin : 0; + hits[hash].emplace_back(fmt("%s: …%s…\n", + p2, + hilite(filterPrintable( + std::string(contents, pos2, pos - pos2 + hash.size() + margin)), + pos - pos2, storePathHashLen, + getColour(hash)))); + } } } else if (st.type == FSAccessor::Type::tSymlink) { auto target = accessor->readLink(p); - auto pos = target.find(dependencyPathHash); - if (pos != std::string::npos) { - std::cerr << fmt(" %s -> %s\n", p2, hilite(target, pos, storePathHashLen)); + + for (auto & hash : hashes) { + auto pos = target.find(hash); + if (pos != std::string::npos) + hits[hash].emplace_back(fmt("%s -> %s\n", p2, + hilite(target, pos, storePathHashLen, getColour(hash)))); } } }; - recurse(path); - } + visitPath(node.path); + + for (auto & ref : refs) { + auto hash = storePathToHash(ref.second->path); + + bool last = all ? ref == *refs.rbegin() : true; + + for (auto & hit : hits[hash]) { + bool first = hit == *hits[hash].begin(); + std::cerr << tailPad + << (first ? (last ? treeLast : treeConn) : (last ? treeNull : treeLine)) + << hit; + if (!all) break; + } + + printNode(*ref.second, + tailPad + (last ? treeNull : treeLine), + tailPad + (last ? treeNull : treeLine)); + } + }; + + try { + printNode(graph.at(packagePath), "", ""); + } catch (BailOut & ) { } } }; |