Merge lp:~dotdepends-team/dotdepends/prune into lp:dotdepends

[Kyle Nitzsche]

add dotdepends-prune and manpage.

dotdepends-prune tool provides a quick path for generating reverse dependency dot files and png files by pruning a (possibly very large), pre-existing dotdepends dot file (one for ubuntu-desktop, for example) to:
* only include the parts of the tree that lead to a "bottom" pkg (this creates the reverse dependency tree)
* and then optionally "top pruning" the tree to exclude bits that don't involve the 'top' package.

Bottom line: fast png graphs of highly targeted rdepends trees.

[lp:~dotdepends-team/dotdepends/prune]

89. By Kyle Nitzsche on 2012-09-07

usr/bin/dotdepends-prune:
* add copyright header
* fix typo ('reversly')

[Mike Carifio (carifio)]

gtg

review: Approve

=== modified file 'Dotdepends/Dot.py'
--- Dotdepends/Dot.py	2012-07-11 20:17:42 +0000
+++ Dotdepends/Dot.py	2012-09-07 18:40:25 +0000
@@ -71,6 +71,26 @@
         self.rnodes = self.get_rnodes()
         self.footer = "}\n}"
         self.shape = shape
+        self.nodePkg, self.pkgNode = self.getNodeNames(self.nodes)
+
+    def getNodeNames(self, nodes):
+        """Return two dicts used to convert between pkg names and dot node
+        names."""
+
+        nodePkg = dict()
+        pkgNode = dict()
+        for node in nodes:
+            style = nodes[node]
+            label = style[style.find('label="'):]
+            pkgName = label[label.find('"')+1:].rstrip('"')
+            if len(pkgName) > 0:
+                pkg = pkgName
+            else:
+                pkg = node
+            nodePkg[node] = pkg
+            pkgNode[pkg] = node
+
+        return nodePkg, pkgNode
 
     def get_root(self):
         line = self.dot[0]
 
=== added file 'data/dotdepends-prune.1'
--- data/dotdepends-prune.1	1970-01-01 00:00:00 +0000
+++ data/dotdepends-prune.1	2012-09-07 18:40:25 +0000
@@ -0,0 +1,74 @@
+.TH dotdepends-prune 1 "5 Sep 2012"  "version 0.1"
+.SH NAME
+\fBdotdepends-prune\fP
+.SH SYNOPSIS
+.B dotdepends-prune [-t TOPPACKAGE] -b BOTTOMPACKAGE FILE
+.br
+.SH DESCRIPTION
+Prunes a dependency tree in a dot file produced by dotdepends to include only
+the dependency chains that lead to a specified package (the 'bottom' package).
+This tree represents the reverse dependencies of the 'bottom' package within
+the scope of the initial dot file. For example, you can create a dot file for
+ubuntu-desktop, then, with dotdepends-prune, create a new dot file that only
+includes the 'rdepends' tree for a particular package.
+.SS TOP PRUNING
+You can further prune the tree by specifying a 'top' package. When a top
+package is also specified, the rdepends tree is processed again to prune out
+all dependency chains that do not include the top package. The result is a
+tree that shows all dependency chains that include the top package and that
+lead to the bottom package. For example, you can prune the ubuntu-desktop tree
+with a top package of update-manager and a bottom package of aptdaemon. This
+produces a tightly focused graph.
+.SS TARGETED, FAST REVERSE DEPENDS GRAPHS
+This approach allows you to create a final dot file that is small enough that
+it can be converted into a png very quickly. (Typically reverse dependencies
+trees are very large. It takes a very long time to generate a png for them and
+the png is so crowded and the text is so small that they are very hard to 
+read.)
+.SS DONT DRAW INTERMEDIATE GRAPHS
+Since png creation (with the dot tool) is often the bottleneck that prevents
+creating rdepends dot files and pngs, we can skip creating the png until the
+final, pruned dot file is produced. This is done with dotdepends 'don't run dot'
+mode, set with the -d argument. So, one could create the first
+dot file for ubuntu-desktop without creating a png for it. Then use
+dotdepends-prune to create the final dot file and convert that to a png.
+.SH EXAMPLE
+.PP
+Create the initial dot file for ubuntu-desktop in depends mode, with recommends 
+included, and in 'don't draw mode':
+.PP
+dotdepends -m depends -r -d ubuntu-desktop
+.PP
+That command produces this initial dot file that defines the scope from which
+further pruning can be done:
+ubuntu-desktop/ubuntu-desktop-depends-Recommends-NoSuggests-NoEnhances.dot
+.PP
+Top prune that dot file to update-manager, bottom prune it to
+aptdaemon, and pipe it to dot to create a png whose default node shape is 'box':
+.PP 
+dotdepends-prune -t update-manager -b aptdaemon 
+ubuntu-desktop/ubuntu-desktop-depends-Recommends-NoSuggests-NoEnhances.dot |
+dot -Tpng -Nshape=box > my.png
+.br
+.SH OPTIONS
+\fB\-t\fR TOPPACKAGE, \fB\-\-top\-package\fR=\fITOPPACKAGE\fR
+.PP
+Dot tree is pruned to only include dependency chains
+between an optional 'top' package node and a required 'bottom' package node.
+This argument specifies the 'top' package node. When it is omitted, the
+generated tree includes all dependency chains leading to the bottom package.
+.HP
+\fB\-b\fR BOTTOMPACKAGE, \fB\-\-bottom\-package\fR=\fIBOTTOMPACKAGE\fR
+.PP
+This argument specifies the required 'bottom' package node to prune the tree
+to. This generates a tree of all reverse dependencies to the bottom package
+found in the dot file being processed.
+.PP
+.SH COLOR CODING
+.PP
+\fBBlack arrows\fR show depends relationships.
+.HP
+\fBRed arrows\fR show recommends relationships.
+.br
+.SH AUTHOR
+This manpage was written by Kyle Nitzsche <[e-mail]>
 
=== modified file 'debian/changelog'
--- debian/changelog	2012-07-16 17:05:10 +0000
+++ debian/changelog	2012-09-07 18:40:25 +0000
@@ -1,3 +1,11 @@
+dotdepends (0.3.19dev1) UNRELEASED; urgency=low
+
+  * add dotdepends-prune: a new script that top and bottom prunes dot file
+  trees to produce smaller, targeted rdepends graphs for efficient conversion
+  to pngs and its man page.
+
+ -- Kyle Nitzsche <[e-mail]>  Fri, 07 Sep 2012 12:57:56 -0400
+
 dotdepends (0.3.19) precise; urgency=low
 
   * test/test_Dot.py: Add a unittest suite for the Dot object and populate with
 
=== modified file 'debian/manpages'
--- debian/manpages	2012-07-09 14:42:21 +0000
+++ debian/manpages	2012-09-07 18:40:25 +0000
@@ -1,2 +1,3 @@
 data/dotdepends.1
 data/dotdepends-merge.1
+data/dotdepends-prune.1
 
=== modified file 'usr/bin/dotdepends'
--- usr/bin/dotdepends	2012-07-16 15:23:44 +0000
+++ usr/bin/dotdepends	2012-09-07 18:40:25 +0000
@@ -427,7 +427,7 @@
             node = ""
             if v == pkg:
                 styles['label'] = v
-                styles['fillecolor'] = "blue"
+                styles['fillcolor'] = "blue"
                 styles['style'] = "filled"
                 styles['fontcolor'] = "white"
             else:
 
=== added file 'usr/bin/dotdepends-prune'
--- usr/bin/dotdepends-prune	1970-01-01 00:00:00 +0000
+++ usr/bin/dotdepends-prune	2012-09-07 18:40:25 +0000
@@ -0,0 +1,182 @@
+#!/usr/bin/python
+#
+# Copyright 2012 Canonical Ltd
+# Authors:
+#   Kyle Nitzsche <[e-mail]>
+#
+# This program 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, version 3 of the License.
+#
+# This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
+from __future__ import print_function
+from optparse import OptionParser
+import Dotdepends.Dot
+import sys
+import os
+
+def pruneChainsToBottomPkg(btmPkg, chain):
+    """Searches through the dot file and finds every chain of dependencies that
+    leads to the bottomPkg node (reversely depends on it). Each such chain
+    is appended to global 'chains' var."""
+
+    lnodes = dot.get_lnodes_for_rnode(btmPkg)
+    for lnode in lnodes:
+        if lnode in processedLnodes: continue
+        else: processedLnodes.append(lnode)
+        newChain = list(chain)
+        newChain.append(lnode)
+        if chain in chains: chains.remove(chain)
+        chains.append(newChain)
+        pruneChainsToBottomPkg(lnode,newChain)
+
+if __name__ == "__main__":
+
+    # dotdepends with no arguments or with -h should run help
+    if (
+        len(sys.argv) == 1
+        or sys.argv[1] == '-h'
+        or sys.argv[1].find('help')
+        ) > -1:
+        print("See 'man dotdepends-prune' for help", file=sys.stderr)
+        sys.exit(0)
+
+    # command help is in the dotdepends man page
+
+    parser = OptionParser()
+
+    parser.add_option(
+                "-t", "--top-package",
+                dest="topPkg",
+                type="string",
+                default="",
+                    )
+    parser.add_option(
+                "-b", "--bottom-package",
+                dest="bottomPkg",
+                type="string",
+                default="",
+                     )
+    (opt, args) = parser.parse_args()
+
+    dotfile = args[0]
+
+    if len(opt.bottomPkg) < 2:
+        print(
+            "Error: You must specify the 'bottom' package to prune the tree to.",
+            "Stopping."
+            )
+        sys.exit(1)
+    if len(dotfile) < 1:
+        print(
+            "Error: You must specify the dot file to process.",
+            "Stopping."
+            )
+        sys.exit(1)
+
+    if not os.path.exists(dotfile):
+        print(
+            "Error: ",
+            dotfile,
+            "does not exist."
+            "Stopping."
+            )
+        sys.exit(1)
+
+    dot = Dotdepends.Dot.Dot(dotfile)
+    bottomPkg = dot.pkgNode[opt.bottomPkg]
+    hasTop = False
+    if len(opt.topPkg) > 0:
+        hasTop = True
+        top = dot.pkgNode[opt.topPkg]
+    joins = dict()
+    chains = [[bottomPkg]]
+    processedLnodes = []
+
+    pruneChainsToBottomPkg(bottomPkg, chains[0])
+
+    # now ,'chains' has every linear dependency chain that leads to
+    # our bottomPkg. That is, we have 'pruned' the full tree to include
+    # only chains rooted in our bottomPkg.
+
+    prunedChains = []
+
+    # Next, if a topPkg is specified, we need to prune the tree to exclude
+    # all pkgs that do not include our top pkg.
+
+    if hasTop:
+        for chain in chains:
+            if top not in chain: continue
+            prunedChains.append(chain)
+        topPkg = opt.topPkg
+    else:
+        prunedChains = chains
+        topPkg = "None"
+    # time to print a dot file that consists of a header, content, and footer
+
+    for line in dot.header:
+        if not line.startswith("label"): # print extant header but not label
+            print(line.rstrip('\n'), sep="")
+    # make label for current prune and print
+    print(
+        'label="',
+        "Dotdepends graph pruned to:\\nTop package: ",
+        topPkg,
+        ". Bottom package: ",
+        dot.nodePkg[bottomPkg],
+        '"',
+        sep=""
+        )
+
+    # print the pruned tree chains. each chain consists of a series of joins,
+    # with one join per line. each join is two nodes followed by a style.
+    # the style (drawn from the dot file for the join), sets the color of the
+    # arrow in the graph: red for recommends, unset (black) for depends.
+    for chain in prunedChains:
+        idx = -1
+        for item in chain:
+            idx += 1
+            if idx == 0: continue
+            found = False
+            for line in dot.joins:
+                if line[0] == chain[idx] and line[1] == chain[idx-1]:
+                    found = True
+                    print(chain[idx], " -> ", chain[idx-1], line[2], ';', sep="")
+            if not found:
+                print(
+                    "Error: join not found in dot: ", 
+                    chain[idx],
+                    " -> ",
+                    chain[idx-1],
+                    " Stopping."
+                    )
+                sys.exit(1)
+
+    # print nodes. each node is a dot-style node name followed
+    # by a style that contains a label that shows the pkg nam
+    printedNodes = []
+    for chain in prunedChains:
+        for node in chain:
+            if node in printedNodes: continue
+            printedNodes.append(node)
+            if node in dot.nodes.keys():
+                print(
+                    node,
+                    ' [',
+                    dot.nodes[node],
+                    '];',
+                    sep=""
+                    )
+
+    # print footer
+    print(dot.footer, sep="")
+
+    sys.exit()
+
+