Extracting a reachability path out of a (package) DAG

Extracting a reachability path out of a (package) DAG

[Björn Höfling]

[-- Attachment #1.1: Type: text/plain, Size: 1556 bytes --]

Hi Guix,

we have this nice `guix graph` tool which outputs DAGs of the packages
(or even derivations,bags, ...). This is cool if you look at simple
packages like the "hello" package with little to no dependencies. If
you look at "real" packages like qt or maven the information is just
overwhelming and you are scrolling around the image for just getting a
headache. 

Often the only think I want to know is something like: Why is "goodbye"
a dependency of "hello"?

To answer this, I want to extract from hello's package graph the path
(more precisely: the sub-DAG) leading from the root "hello" to the
target node (or even nodes) "goodbye".

After several attempts and failures, I wrote a script for gvpr from
the GraphViz suite that does the job.

Example 1: In bug #30710 Hartmut Goebel asked why qt depends on two
different autoconf-wrapper packages. To answer that, you can find out
the two node names from the .dot file and then call:

gvpr -f markpath.g -a "ex 64168128 64167936" < qt-thing/qt.package.dot
>qt-acw.dot

This extracts (ex) the path (sub-DAG) to the two seed nodes and outputs
it in a new graph. This result is quite compact with only 12 nodes (attached).

Example 2: How/Why is glib a dependency of maven? The extracted graph
has about 50 nodes, so I don't attach it here. You will see that
java-logback-classic depends on a groovy-cluster that finally mounts
into antlr. That depends on a gtk/pango/cairo-cluster that finally
sinks into glib.

Hope that is useful to someone else,

Björn



[-- Attachment #1.2: markpath.g --]
[-- Type: application/octet-stream, Size: 4193 bytes --]

/*

dotscripts --- Scripts for GraphViz

Copyright © 2018 Björn Höfling <bjoern.hoefling@bjoernhoefling.de>

This file is part of dotscripts.

dotscripts is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or (at
your option) any later version.

dotscripts is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with dotscripts.  If not, see <http://www.gnu.org/licenses/>.
*/


/******************************************************************************* 
Extract/Highlight path in a DAG from root to specific node.
*******************************************************************************/

BEGIN {

    // gvpr has no scope. So we define one global loop variable here:
    int i;

    // True(>0) if you want to extract the graph. False(=0) for highlighting.
    int extract;
    
    int numSeeds = ARGC-1;

    // Array of nodes that should be reached from the root node.
    // They act as seeds for the search algorithm.
    node_t seedNodes[];

    //Map of nodes/edges->0/1: indicating weather or not a node/edge is marked.
    int nodesMarked[obj_t];

    graph_t outGraph;

    void showUsage() {
        printf("Usage: gvpr -f markpath.g -a \"<cmd> node1 node2 ... \"\n");
        printf("where <cmd> is one of:\n");
        printf("ex - extract path.\n");
        printf("hl - highlight path.\n");
        printf("\n");
        printf("node1 node2 ... are the seed nodes\n");
        exit(1);    
    }





    if(ARGC<2) {
        showUsage();
    }
    
    if(ARGV[0]=="ex") {
        extract = 1;
    } else if(ARGV[0]=="hl") {
        extract=0;
    } else {
        showUsage();
    }

    /** Marks the object (edge or node) as highlighted/visited.
     */
    void mark(obj_t obj) {
        nodesMarked[obj]=1;

        if(extract) {
            clone(outGraph, obj);
        } else {
        obj.color="red";
        obj.style="filled";
        }
    }

    /**
      Returns true, if s is a seedNode, false otherwise.
    */
    int isSeedNode(node_t s) {
        
        int ii;
        for(ii=0; ii<numSeeds; ii++) {
            if(s==seedNodes[ii]) {
                return 1;
            }
        }
        return 0;
    }
    
    /**
      Traverses over all outEdges of node n.
      If any of those outEdges was already marked,
      return true.
      If no marked Edge is found, return false.
    */
    int anyEdgeMarked(node_t n) {
        edge_t e = fstout(n);
        while(e!=NULL) {
            if(nodesMarked[(obj_t)e]) {
                return 1;
            }
            e = nxtout(e);
        }
        return 0;
    }

    /** Returns true if head node of edge e is marked */
    int headIsMarked(edge_t e) {
        return nodesMarked[(obj_t)e.head];
    }
}

BEG_G {
    // If we want to extract, we create a new graph.
    // Else we use the input graph.
    if(extract) {
        outGraph = graph(sprintf("Extract of %s",$.name), "DS");
    } else {
        outGraph=$;
    }
    
    // Initialize seedNodes. We have to do it here in BEG_G, because only here
    // the graph is availabe.
    for(i=0; i< numSeeds; i++) {
        seedNodes[i]=isNode($, ARGV[i+1]);
        if(seedNodes[i]==NULL) {
            printf("Error: Argument %d is not a node!\n", i+1);
            exit(1);
         }
    }

    // Set traversal order to reverse, going into direction of the root node.
    $tvtype = TV_rev;

    // Setting the start node as one of the seed Nodes.
    // Variable is called "$tvnext", because it usually is ment to go to the next
    // connected component (CC), though we have only one CC here.
    $tvnext = seedNodes[0];
}

// The logic is extracted into functions, so this part looks rather trivial:

N [isSeedNode($)] {
    mark($);
}

N[anyEdgeMarked($)]{
    mark($);
}

E[headIsMarked($)] {
    mark($);
}

END_G {
    $O=outGraph;
}

[-- Attachment #1.3: qt-subdag-autoconf-wrapper.png --]
[-- Type: image/png, Size: 50516 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Pierre Neidhardt]

[-- Attachment #1: Type: text/plain, Size: 397 bytes --]

> gvpr -f markpath.g -a "ex 64168128 64167936" < qt-thing/qt.package.dot
> : qt-acw.dot

Can you explain the two magic numbers?  I'm not sure what you mean with "seed
nodes".

That said, I think it's a great idea.  Could we go even more interactive with an
interface that filter the graph "live", e.g. some HTML+js web page?

Someone must have done that before...
-- 
Pierre Neidhardt

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Nils Gillmann]

Björn Höfling transcribed 74K bytes:
> Hi Guix,
> 
> we have this nice `guix graph` tool which outputs DAGs of the packages
> (or even derivations,bags, ...). This is cool if you look at simple
> packages like the "hello" package with little to no dependencies. If
> you look at "real" packages like qt or maven the information is just
> overwhelming and you are scrolling around the image for just getting a
> headache. 
> 
> Often the only think I want to know is something like: Why is "goodbye"
> a dependency of "hello"?
> 
> To answer this, I want to extract from hello's package graph the path
> (more precisely: the sub-DAG) leading from the root "hello" to the
> target node (or even nodes) "goodbye".
> 
> After several attempts and failures, I wrote a script for gvpr from
> the GraphViz suite that does the job.
> 
> Example 1: In bug #30710 Hartmut Goebel asked why qt depends on two
> different autoconf-wrapper packages. To answer that, you can find out
> the two node names from the .dot file and then call:
> 
> gvpr -f markpath.g -a "ex 64168128 64167936" < qt-thing/qt.package.dot
> >qt-acw.dot
> 
> This extracts (ex) the path (sub-DAG) to the two seed nodes and outputs
> it in a new graph. This result is quite compact with only 12 nodes (attached).
> 
> Example 2: How/Why is glib a dependency of maven? The extracted graph
> has about 50 nodes, so I don't attach it here. You will see that
> java-logback-classic depends on a groovy-cluster that finally mounts
> into antlr. That depends on a gtk/pango/cairo-cluster that finally
> sinks into glib.
> 
> Hope that is useful to someone else,
> 
> Björn
> 
> 

To add to this idea:
abyayala$ nix why-depends --help
Usage: nix why-depends <FLAGS>... <PACKAGE> <DEPENDENCY>

Summary: show why a package has another package in its closure.

Flags:
  -a, --all                     show all edges in the dependency graph leading from 'package' to 'dependency', rather than just a shortest path
  --arg <NAME> <EXPR>       argument to be passed to Nix functions
  --argstr <NAME> <STRING>  string-valued argument to be passed to Nix functions
  -f, --file <FILE>             evaluate FILE rather than the default
  -I, --include <PATH>          add a path to the list of locations used to look up <...> file names

Examples:

  To show one path through the dependency graph leading from Hello to Glibc:
    $ nix why-depends nixpkgs.hello nixpkgs.glibc

  To show all files and paths in the dependency graph leading from Thunderbird to libX11:
    $ nix why-depends --all nixpkgs.thunderbird nixpkgs.xorg.libX11

  To show why Glibc depends on itself:
    $ nix why-depends nixpkgs.glibc nixpkgs.glibc

Note: this program is EXPERIMENTAL and subject to change.



Would it be useful to have a guix package subcommand which replicates this?

Re: Extracting a reachability path out of a (package) DAG

[Björn Höfling]

[-- Attachment #1: Type: text/plain, Size: 1974 bytes --]

On Tue, 17 Jul 2018 10:22:02 +0200
Pierre Neidhardt <ambrevar@gmail.com> wrote:

> > gvpr -f markpath.g -a "ex 64168128 64167936" <
> > qt-thing/qt.package.dot : qt-acw.dot  
> 
> Can you explain the two magic numbers?  I'm not sure what you mean
> with "seed nodes".

The numbers are the node names from the graph created by "guix graph".
It looks like:

digraph "Guix package" {
  "64775296" [label = "ccache@3.4.2", shape = box, fontname = Helvetica];
  "64775296" -> "55094656" [color = dimgrey];
  "64775296" -> "54665792" [color = dimgrey];
  "64775296" -> "61828864" [color = dimgrey];
  "55094656" [label = "perl@5.26.1", shape = box, fontname = Helvetica];
  "54665792" [label = "which@2.21", shape = box, fontname = Helvetica];
  "61828864" [label = "zlib@1.2.11", shape = box, fontname = Helvetica];

}

I don't know how the numbers are generated, but they are the names of
the nodes. I could have used the labels also, but then you have to
parse out the version. So, you have to look into that graph file and
have to figure out your nodes of interest.

"seed nodes" is more like a internal name in my script: That's where I
start searching. Better call them "targets", where your path should go
to/stop at. You can have more than one.


> That said, I think it's a great idea.  Could we go even more
> interactive with an interface that filter the graph "live", e.g. some
> HTML+js web page?
> 
> Someone must have done that before...

guix graph --list-backends
The available backend types are:

  - graphviz: Generate graph in DOT format for use with Graphviz.
  - d3js: Generate chord diagrams with d3js.
  - cypher: Generate Cypher queries.

There is the d3js backend, which produces HTML+js. But I find this also
very confusing. Maybe one could use it as a basis to filter the graph
like I did with gvpr. 

Maybe one could use cypher to work with graphs, but I didn't succeed
with that way.

Björn



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Björn Höfling]

[-- Attachment #1: Type: text/plain, Size: 450 bytes --]

On Tue, 17 Jul 2018 08:24:24 +0000
Nils Gillmann <ng0@n0.is> wrote:


> To add to this idea:
> abyayala$ nix why-depends --help
> Usage: nix why-depends <FLAGS>... <PACKAGE> <DEPENDENCY>
> 
> Summary: show why a package has another package in its closure.

[..]

> Would it be useful to have a guix package subcommand which replicates
> this?


Yeah, would be nice. Because that was missing, I created that script
for me.

Björn

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Gábor Boskovits]

[-- Attachment #1: Type: text/plain, Size: 814 bytes --]

Björn Höfling <bjoern.hoefling@bjoernhoefling.de> ezt írta (időpont: 2018.
júl. 17., K, 12:32):

> On Tue, 17 Jul 2018 08:24:24 +0000
> Nils Gillmann <ng0@n0.is> wrote:
>
>
> > To add to this idea:
> > abyayala$ nix why-depends --help
> > Usage: nix why-depends <FLAGS>... <PACKAGE> <DEPENDENCY>
> >
> > Summary: show why a package has another package in its closure.
>
> [..]
>
> > Would it be useful to have a guix package subcommand which replicates
> > this?
>
>
> Yeah, would be nice. Because that was missing, I created that script
> for me.
>
> Björn
>

Thanks, Björn. I've recently had the same problem, and I was about to write
this script once we moved to jdk8. Now I don't have to do it any more :)
This is very useful, it helps so much in bootstrapping related work.

[-- Attachment #2: Type: text/html, Size: 1227 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Pierre Neidhardt]

[-- Attachment #1: Type: text/plain, Size: 270 bytes --]

Is the d3.js backend functional?

> guix graph --backend=d3js coreutils > coreutils-graph.html

result in a HTML page with a script, but the rendering remains blank.  I don't
know anything about d3js, I could be missing something trivial.

-- 
Pierre Neidhardt

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Alex Kost]

Pierre Neidhardt (2018-07-21 23:55 +0200) wrote:

> Is the d3.js backend functional?
>
>> guix graph --backend=d3js coreutils > coreutils-graph.html
>
> result in a HTML page with a script, but the rendering remains blank.  I don't
> know anything about d3js, I could be missing something trivial.

It works for me, although I know nothing about d3js as well, so I can't
really help :-)

-- 
Alex

Re: Extracting a reachability path out of a (package) DAG

[Pierre Neidhardt]

[-- Attachment #1: Type: text/plain, Size: 2584 bytes --]

Here is the output I get:

--8<---------------cut here---------------start------------->8---
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <style>
text {
  font: 10px sans-serif;
  pointer-events: none;
}
    </style>
    <script type="text/javascript" src="#f"></script>
  </head>
  <body>
    <script type="text/javascript">
var nodes = {},
    nodeArray = [],
    links = [];
nodes["58283904"] = {"id": "58283904", "label": "coreutils@8.29", "index": nodeArray.length};
nodeArray.push(nodes["58283904"]);
links.push({"source": "58283904", "target": "58328960"});
links.push({"source": "58283904", "target": "58285440"});
links.push({"source": "58283904", "target": "45319680"});
links.push({"source": "58283904", "target": "59224640"});
nodes["58328960"] = {"id": "58328960", "label": "perl@5.26.1", "index": nodeArray.length};
nodeArray.push(nodes["58328960"]);
nodes["58285440"] = {"id": "58285440", "label": "acl@2.2.52", "index": nodeArray.length};
nodeArray.push(nodes["58285440"]);
links.push({"source": "58285440", "target": "58208448"});
links.push({"source": "58285440", "target": "58328960"});
links.push({"source": "58285440", "target": "58285632"});
nodes["58208448"] = {"id": "58208448", "label": "gettext-minimal@0.19.8.1", "index": nodeArray.length};
nodeArray.push(nodes["58208448"]);
links.push({"source": "58208448", "target": "55633408"});
nodes["55633408"] = {"id": "55633408", "label": "expat@2.2.5", "index": nodeArray.length};
nodeArray.push(nodes["55633408"]);
nodes["58285632"] = {"id": "58285632", "label": "attr@2.4.47", "index": nodeArray.length};
nodeArray.push(nodes["58285632"]);
links.push({"source": "58285632", "target": "58208448"});
links.push({"source": "58285632", "target": "58328960"});
nodes["45319680"] = {"id": "45319680", "label": "gmp@6.1.2", "index": nodeArray.length};
nodeArray.push(nodes["45319680"]);
links.push({"source": "45319680", "target": "45319872"});
nodes["45319872"] = {"id": "45319872", "label": "m4@1.4.18", "index": nodeArray.length};
nodeArray.push(nodes["45319872"]);
nodes["59224640"] = {"id": "59224640", "label": "libcap@2.25", "index": nodeArray.length};
nodeArray.push(nodes["59224640"]);
links.push({"source": "59224640", "target": "58328960"});
links.push({"source": "59224640", "target": "58285632"});
</script><script type="text/javascript" src="#f"></script></body></html>
--8<---------------cut here---------------end--------------->8---

My terrible web-programming skills tell me it looks very suspicious...
-- 
Pierre Neidhardt

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Björn Höfling]

[-- Attachment #1: Type: text/plain, Size: 1726 bytes --]

On Sun, 22 Jul 2018 20:59:21 +0200
Pierre Neidhardt <ambrevar@gmail.com> wrote:

> Here is the output I get:
> 
> --8<---------------cut here---------------start------------->8---
> <!DOCTYPE html>
> <html>
>   <head>
>     <meta charset="utf-8">
>     <style>
> text {
>   font: 10px sans-serif;
>   pointer-events: none;
> }
>     </style>
>     <script type="text/javascript" src="#f"></script>
>   </head>
>   <body>
[..]
> src="#f"></script></body></html> --8<---------------cut
> here---------------end--------------->8---
> 
> My terrible web-programming skills tell me it looks very suspicious...


I was going to say "works for me too" and was in the process of
creating an example with a guix container and icecat/guix in it. But
exactly there it fails.

Yes, src="#f" is wrong, I sometimes (always in the container) can
reproduce this. In the good case, that first one in the
head should be "d3.v3.js". That can be found in the checked out guix
source.

The last one is "graph.js", also in the guix source. Here's the commit:

commit 4d93f312f084c34a70cf7da3abe5f92a74d76861
Author: Ricardo Wurmus <rekado@elephly.net>
Date:   Sat Oct 22 00:02:19 2016 +0200

    graph: Add d3js backend.
    
    * d3.v3.js, graph.js: New files.
    * Makefile.am (EXTRA_DIST): List them.
    * guix/graph.scm (%d3js-backend): New variable.
    (emit-d3js-prologue, emit-d3js-epilogue, emit-d3js-node,
    emit-d3js-edge): New procedures.
    (%graph-backends): Add %d3js-backend.

I think if you copy both to your directory and adapt your html, then it
should work.

But maybe we should adapt the output html such that the js is fully
included and is portable?

Björn



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Extracting a reachability path out of a (package) DAG

[Ludovic Courtès]

Hi Björn,

Björn Höfling <bjoern.hoefling@bjoernhoefling.de> skribis:

> To answer this, I want to extract from hello's package graph the path
> (more precisely: the sub-DAG) leading from the root "hello" to the
> target node (or even nodes) "goodbye".
>
> After several attempts and failures, I wrote a script for gvpr from
> the GraphViz suite that does the job.
>
> Example 1: In bug #30710 Hartmut Goebel asked why qt depends on two
> different autoconf-wrapper packages. To answer that, you can find out
> the two node names from the .dot file and then call:
>
> gvpr -f markpath.g -a "ex 64168128 64167936" < qt-thing/qt.package.dot
>>qt-acw.dot
>
> This extracts (ex) the path (sub-DAG) to the two seed nodes and outputs
> it in a new graph. This result is quite compact with only 12 nodes (attached).

That’s excellent!  I didn’t know about gvpr and its scripting
capabilities, really nice (GraphViz also has Guile bindings, not sure if
they would help here?).

It may be nice to have some of this functionality available directly in
(guix graph) because these are very common questions one may ask.
Future work!

Thanks,
Ludo’.

Re: Extracting a reachability path out of a (package) DAG

[Chris Marusich]

[-- Attachment #1: Type: text/plain, Size: 662 bytes --]

Hi Björn!

Björn Höfling <bjoern.hoefling@bjoernhoefling.de> writes:

> gvpr -f markpath.g -a "ex 64168128 64167936" < qt-thing/qt.package.dot
>>qt-acw.dot
>
> This extracts (ex) the path (sub-DAG) to the two seed nodes and outputs
> it in a new graph. This result is quite compact with only 12 nodes (attached).
>
> [...]
>
> Hope that is useful to someone else,

This is so cool!  I used this today to reduce a spaghetti monster graph
of dependencies into a small, understandable graph.  I didn't even know
about gvpr, but now it's one of my favorite little tools!  :-)

Thank you for sharing the knowledge, and the script!

-- 
Chris

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]