diff options
Diffstat (limited to 'third_party/nix/src/nix/why-depends.cc')
| -rw-r--r-- | third_party/nix/src/nix/why-depends.cc | 269 |
1 files changed, 269 insertions, 0 deletions
diff --git a/third_party/nix/src/nix/why-depends.cc b/third_party/nix/src/nix/why-depends.cc new file mode 100644 index 000000000000..954d619ef3ce --- /dev/null +++ b/third_party/nix/src/nix/why-depends.cc @@ -0,0 +1,269 @@ +#include <queue> + +#include <glog/logging.h> + +#include "libmain/shared.hh" +#include "libstore/fs-accessor.hh" +#include "libstore/store-api.hh" +#include "nix/command.hh" + +namespace { +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) != 0 ? c : '.'; + } + return res; +} +} // namespace + +namespace nix { +struct CmdWhyDepends final : 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 { return "why-depends"; } + + 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"}, + }; + } + + 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 = storePathToHash(dependencyPath); + + PathSet closure; + store->computeFSClosure({packagePath}, closure, false, false); + + if (closure.count(dependencyPath) == 0u) { + LOG(WARNING) << "'" << package->what() << "' does not depend on '" + << dependency->what() << "'"; + return; + } + + auto accessor = store->getFSAccessor(); + + 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); + } + } + + /* 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); + } + } + } + } + + /* 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 std::string&, const std::string&)> + printNode; + + const std::string treeConn = "╠═══"; + const std::string treeLast = "╚═══"; + const std::string treeLine = "║ "; + const std::string treeNull = " "; + + struct BailOut {}; + + printNode = [&](Node& node, const std::string& firstPad, + const std::string& tailPad) { + assert(node.dist != inf); + std::cout << fmt("%s%s%s%s" ANSI_NORMAL "\n", firstPad, + node.visited ? "\e[38;5;244m" : "", + !firstPad.empty() ? "=> " : "", node.path); + + if (node.path == dependencyPath && !all && + packagePath != dependencyPath) { + throw BailOut(); + } + + if (node.visited) { + return; + } + node.visited = true; + + /* 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 && packagePath != dependencyPath) { + 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 == 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) { + visitPath(p + "/" + name); + } + } + + else if (st.type == FSAccessor::Type::tRegular) { + auto contents = accessor->readFile(p); + + for (auto& hash : hashes) { + auto pos = contents.find(hash); + if (pos != std::string::npos) { + size_t margin = 32; + 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); + + 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)))); + } + } + } + }; + + // FIXME: should use scanForReferences(). + + visitPath(node.path); + + RunPager pager; + 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::cout << 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&) { + } + } +}; +} // namespace nix + +static nix::RegisterCommand r1(nix::make_ref<nix::CmdWhyDepends>()); |