Recursive dependencies, recursive uninstall, variants

[Shreevatsa R]

[Sorry if this gets sent twice; I sent it from the wrong address by mistake so
I think the list rejected it.]

Hello,

I started replying to this and got busy, so excuse any discontinuity below:

On Sat, Apr 26, 2008 at 12:15:17AM -0500, Ryan Schmidt wrote:
> Being able to get a recursive list of dependencies would certainly be 
> useful. I wrote a PHP web page [1] to display a graph of this information, 
> because I also wanted to see it. Would be handy to have the main logic in 
> the port command. Should make it faster.
>
> [1] http://www.ryandesign.com/tmp/portviz.tar.bz2

Can't be too sure, this is Tcl after all ;-)

I looked at what your PHP code does. I have separated out the different parts
of it, and the port command can now (= if it is committed) produce DOT figures.
See below.

On Sat, Apr 26, 2008 at 04:20:13PM +0200, =?ISO-8859-1?Q?Rainer_M=FCller_ wrote:
> Shreevatsa R wrote:
>> Hi MacPorts developers,
>
> Hi,
>
> This looks good. Of course the output could be a lot better... And how are 
> you dealing with ports appearing multiple times? E.g. portA depends on 
> portB and portC, and these two depend on portD. If portD depends on a lot 
> of other ports you get a long list - twice. Don't know if that can be 
> improved in the ascii output...

That's what I was using the global variable $shownports for -- to avoid
displaying, and recursing on, portD after the first time.

> But I don't like introducing a new command just for this. This should be 
> port deps --follow-deps as discussed earlier.

Yes, it's too specialised to be a new command. However (more on this later), a
general function for getting a port's tree (DAG, actually) of dependencies or
dependents, is something that many different commands can use. That is, any
command's --follow-deps would be equivalently got by running that command on
this list.

> What I also would like (and I think Ryan would like it, too ;-)) is the 
> possibility to output the dependency tree in the dot language for graphviz. 
> So we could use something like this to get a nice graph:
>   port deps --follow-deps --dot | dot -o depgraph.png
>
> Would also be cool to have such graphs on the website.


>> I was planning to do the same for variants (because I install
>> something and later discover I should have installed one of its
>> dependencies with a different variant), and for uninstall (because it
>> is a real pain to uninstall ports).
>
> Not sure what a mean with "variants". port deps currently does not take 
> dependencies into account, because it is reading the PortIndex only. This 
> makes it probably faster but this feature is missing. So to solve this one 
> would have to [mportopen] all ports and their dependencies to get the 
> dependencies list modified by variants.

Oh, I didn't mean dependencies of variants (I know that's a much-wanted
feature), I meant variants of dependencies. portA depends on portB, and portB
has a useful variant that would not be shown by "port variants portA". 

I still dislike the idea of variants as "hidden features", but at least I can
try unhiding them a bit...

> I don't quite understand why you call uninstalling ports a "real pain". 
> What is the problem with that?

~$ port uninstall portA
---> Unable to portA, the following ports depend on it:
--->   portB
--->   portC
--->   portD
--->   portE
--->   portF
--->   portG
--->   portH
Error: port uninstall failed: Please uninstall the ports that depend on portA first.

[Copy-and-paste the names one-by-one...]
~$ port uninstall portB portC portD portE portF portG portH portA
---> Uninstalling portB
---> Unable to uninstall portC, the following ports depend on it:
--->   portD (etc.)

[WTF? It's right there in the list, why can't you figure it out?]
[Swap portC and portD]
~$ port uninstall portB portD portC portE portF portG portH portA
Error: port uninstall failed: Registry error: portB not registered as installed.
[Aaargh.]
[Repeat many times.]
 
Am I doing it incorrectly?

Now, if `port dag --dept-list portA` were guaranteed to return a list of all installed
dependents of portA in topologically sorted order, then 
`port uninstall $(port dag --dept-list portA)` would Just Work. (Of course, I
don't care about the syntax, it could be `port uninstall --follow-deps portA`,
all I mean is that a reusable function for dependencies or dependents would be
useful.)

>> More specifically, I was planning to
>> (1) make a general (simple) function for getting a specific port's
>> "tree of dependencies" (and/or tree of dependents) and then something
>> to act on it. Uninstall would then be trivial.
>> (2) Also, putting something to return the list of dependencies of a
>> port in the MacPorts API itself.
>> (3) Also, looking at action_deps, it seems to share a lot in common
>> with other functions (searching for ports, etc.), so that part can be
>> cleaned up...
>
> Sounds like a good plan!
>
> Rainer

Here is some code; consider it proof-of-concept. It would be good if someone
can tell me what changes to make and what to do to get it committed.

This is how it works now (I'm using "dep" for dependencies and "dept" for
dependents.)

~$ port dag --dep-list glib2
glib2 pkgconfig gettext expat libiconv ncurses gperf ncursesw

~$ port dag --dept-list glib2 
glib2 atk libidl dbus-glib irssi py25-gobject dbus-python25 pango orbit2 shared-mime-info libbonobo gstreamer graphviz gtk2 tcllib libglade2 gtkspell2 py25-gtk gtimelog
[This would be different on your system, of course.]

~$ port dag --dep-dot glib2  
digraph MacPorts { 
"pkgconfig" -> "glib2" [style=dotted]; 
"gettext" -> "glib2" [style=solid]; 
"libiconv" -> "glib2" [style=solid]; 
"libiconv" -> "gettext" [style=solid]; 
"ncurses" -> "gettext" [style=solid]; 
"expat" -> "gettext" [style=solid]; 
"gperf" -> "libiconv" [style=dotted]; 
"ncursesw" -> "ncurses" [style=dashed]; 
} 

~$ port dag --dept-dot glib2
digraph MacPorts { 
"glib2" -> "py25-gobject" [style=solid]; 
"glib2" -> "atk" [style=solid]; 
"glib2" -> "pango" [style=solid]; 
[... snip ... ]
"gtk2" -> "py25-gtk" [style=solid]; 
"orbit2" -> "libbonobo" [style=solid]; 
"py25-gtk" -> "gtimelog" [style=solid]; 
}

The last two produce pretty pictures when passed through graphviz.

Code follows; I haven't bothered making it into patch format or anything, but
it goes into port.tcl:

#####################################################################################
proc alldeps {portname} { #Return list of the form {type1 {ports} type2 {ports} ... }
    array set portinfo [lindex [mportsearch $portname no exact] 1]

    set alldeps []
    foreach type {depends_build depends_lib depends_run} {
        if {[info exists portinfo($type)]} {
            #set curdeps [map {x {lindex [split $x :] end}} $portinfo($type)]
            set curdeps []
            foreach i $portinfo($type) {
                #$i looks like port:gtk2 or bin:tex:texlive
                lappend curdeps [lindex [split $i :] end]
            }
            lappend alldeps $type
            lappend alldeps $curdeps
        }
    }
    return $alldeps
}

proc alldepts {portname} { #Return list of dependents, of the form {type1 {ports} type2 {ports} ... }
    array set depts []
    registry::open_dep_map
    set rawdepts [join [registry::list_dependents $portname]]
    foreach {this type that} $rawdepts {
        if {$this == $portname} {
            lappend depts($type) $that
        } else {
            ui_error "Unrecognised entry {{$this} {$type} {$that}} in dependents of $portname"
        }
    }
    return [array get depts]
}

proc DAGedges {neighfunc portname} {
    #Given function that returns neighbours of form {type1 {ports} type2 {ports} ... },
    #repeatedly call it, and return DAG as {name1 {type {ports} ... } name2 {type {ports} ... }}
    array set neighbours []
    set queue [list $portname]

    while {[llength $queue] > 0} {
        set portname [lindex $queue 0]
        set queue [lrange $queue 1 end]
        set neighbours($portname) [$neighfunc $portname]
        foreach {type ports} $neighbours($portname) {
            foreach port $ports {
                if {![info exists neighbours($port)]} {lappend queue $port}
            }
        }
    }
    return [array get neighbours]
}

proc dotDAG {dag {rev 0}} {
    #Given a DAG (as above), output DOT format description
    set dot "digraph MacPorts \{ \n"
    array set style {depends_build dotted depends_lib solid depends_run dashed port solid lib dashed}
    #append dot [subst -nocomm {edge [len=2.75]; \n}]
    #append dot [subst -nocomm {node [fontsize=10]; \n}]
    foreach {port neighs} $dag {
        foreach {type ports} $neighs {
            foreach neighbour $ports {
                if {$rev} {
                    append dot [subst {"$neighbour" -> "$port"}]
                } else {
                    append dot [subst {"$port" -> "$neighbour"}]
                }
                if [info exists style($type)] {
                    append dot [subst -nocomm { [style=$style($type)]}]
                }
                append dot "; \n"
            }
        }
    }
    append dot "\} \n"
    return $dot
}

proc toposortDAG {dag} {
    #Given a DAG (as above), return a list of nodes in topologically sorted order
    #Algorithm: Compute indegrees, remove nodes of indegree 0, repeat.
    #This probably sucks on the Tcl structures we're using; it's probably faster to do DFSes and order by finish time
    array set neigh $dag
    array set indegree []
    set ret []
    foreach {port neighs} $dag {
        if {![info exists indegree($port)]} {set indegree($port) 0}
        foreach {type ports} $neighs {
            foreach neighbour $ports {
                if {![info exists indegree($neighbour)]} {
                    set indegree($neighbour) 1
                } else {
                    incr indegree($neighbour)
                }
            }
        }
    }
    while {[array size indegree] > 0} {
        foreach node [array names indegree] {
            if {$indegree($node) == 0} {
                array unset indegree $node
                lappend ret $node
                foreach {type ports} $neigh($node) {
                    foreach neighbour $ports {
                        incr indegree($neighbour) -1
                    }
                }
            }
        }
    }
    return $ret
}

proc action_dag {action portlist opts} {
    set opt [lindex $opts 0]
    foreachport $portlist {
        if {"$opt" == "ports_dag_dep-dot"} {
            puts [dotDAG [DAGedges alldeps $portname] 1]
        } elseif {"ports_dag_dept-dot" eq "$opt"} {
            puts [dotDAG [DAGedges alldepts $portname]]
        } elseif {"ports_dag_dep-list" == $opt} {
            puts [toposortDAG [DAGedges alldeps $portname]]
        } elseif {$opt == "ports_dag_dept-list"} {
            puts [toposortDAG [DAGedges alldepts $portname]]
        } else {
            ui_error "I have no idea what $opt means"
        }
    }
}

#####################################################################################

Thanks,
Shreevatsa