opkg-graph-deps

#!/usr/bin/env python
from __future__ import absolute_import
from __future__ import print_function

import sys
import os
import getopt
import pydot
import opkg
import six

def usage(more=False):
    print(( 'Usage: opkg-graph-deps '
        '[-h] [-d] [-o feed.dot] '
        '[-u <Base_feed_URL>] '
        '<Paths_to_Packages_files>' ), file=sys.stderr)
    if more:
        print('\n'.join( [
'',
'Generates a dot formatted dependency graph of an IPK feed.',
'',
'The feed is specified by a list of IPK index (Packages) files, which',
'are sourced in the order specified to build a dependency graph. Last',
'index to declare a package wins, but also generates a warning to stderr.',
'Only the flat index format is supported -- I.e. only Packages files,',
'not Packages.gz files.',
'',
'Possible warnings:',
' Duplicate package: package appears in more than one index.',
' Broken dependency: no package satisfies a declared dependency.',
' Self alias: package declares an alias on it\'s own name.',
' Virtual-real alias: package attempts to provide a real package.',
' Missing field: package is missing a required field.',
'',
'If a base feed URL is specified (-u), each node will include an \'href\'',
'to the associated IPK file. This is purely cosmetic. E.g. It can be used',
'to create clickable links on a rendered graph. Using it has no effect',
'on the set of packages or dependencies. It\'s assumed the specified',
'base feed URL hosts the current working directory, so the resulting',
'href\'s are generated by joining the base and a relative IPK path.',
'',
'The resulting feed graph is written to \'./feed.dot\' or an alternate',
'path specified by the caller. Nodes represent real packages (not aliases)',
'and edges represent dependencies.',
'',
'Node attributes:',
' (node name): Package name from feed index (without version or arch)',
' label: [Package name] [ipkArchitecture] [ipkVersion]',
' ipkArchitecture: Architecture name from feed index',
' ipkVersion: The full version number from feed index',
' ipkMissing: Set to "1" when the ipk is not actually in feed, but has',
'  one or inbound dependencies.',
' href: URL to the IPK file. Only if optional base URL is specified.',
'',
'Edge attributes:',
' (from) The package name declaring a dependency',
' (to) The (de-aliased) package name (from) depends on',
' ipkProvides: The alias of (to) which (from) depends on. Only set when',
'  the alias != (to).',
' ipkBrokenDep: Set to "1" if (to) is missing from the feed.',
'',
        ] ), file=sys.stderr)
    exit(1)

# optional args
enable_debug = False
dot_filename = "feed.dot"
feed_url = None

(opts, index_files) = getopt.getopt(sys.argv[1:], "hdo:u:")
for (optkey, optval) in opts:
    if optkey == '-h':
        usage(more=True)
    elif optkey == '-d':
        enable_debug = True
    elif optkey == '-o':
        dot_filename = optval
    elif optkey == '-u':
        feed_url = optval

if not index_files:
    print('Must specify a path to at least one Packages file', file=sys.stderr)
    usage()

def fatal_error(msg):
    print(('ERROR: ' + str(msg)), file=sys.stderr)
    exit(1)

def warn(msg):
    print(str(msg), file=sys.stderr)

def debug(msg):
    if enable_debug:
        print(('DEBUG: ' + str(msg)), file=sys.stderr)

def split_dep_list(lst):
    '''
    Splits a comma-space delimited list, retuning only the first item.
    E.g. 'foo (>= 1.2), bar, lab (x)' yields ['foo', 'bar', 'lab']
    '''
    if not lst:
        lst = ''

    res = []

    splitLst = lst.split(',')
    for itm in splitLst:
        itm = itm.strip()
        if not itm:
            continue
        itmSplit = itm.split()
        res.append(itmSplit[0])

    return res

# define the graph
graph = pydot.Dot(graph_name='ipkFeed', graph_type='digraph')
graph.set_node_defaults(shape='rectangle', style='solid', color='black')
graph.set_edge_defaults(style='solid', color='black')

def pkg_architectcture(pkg):
    return str(pkg.architecture or '?')

def pkg_label(pkg, includeArch=True, includeVersion=False, includePath=False, multiLine=False):
    label = str(pkg.package or '?')
    if multiLine:
        label += '\\n'
    if includeArch:
        label += '[%s]' % pkg_architectcture(pkg)
    if includeVersion:
        label += '[%s]' % (pkg.version or 'none')
    if includePath:
        label += '[%s]' % (pkg.fn or '?')
    return label

def add_package_to_graph(pkg, missing=False):
    if not pkg.package:
        raise Exception('Invalid package name')

    node = pydot.Node(pkg.package)

    node.set('label', pkg_label(pkg,
        includeVersion=(not missing),
        includeArch=(not missing),
        multiLine=True) )

    if missing:
        node.set('ipkMissing', '1')
        node.set('style', 'dotted')
        node.set('color', 'red')

    node.set('ipkVersion', pkg.version or 'none')
    node.set('ipkArchitecture', pkg_architectcture(pkg))

    if feed_url and pkg.filename:
        node.set('href', '%s/%s' % (feed_url, pkg.fn) )

    graph.add_node(node)

def add_dependency_to_graph(fromPkg, toPkg, alias=None, broken=False):
        edge = pydot.Edge(fromPkg.package, toPkg.package)

        if alias:
            edge.set('ipkProvides', alias)
            edge.set('style', 'dashed')

        if broken:
            edge.set('ipkBrokenDep', '1')
            edge.set('style', 'dotted')
            edge.set('color', 'red')

        graph.add_edge(edge)

# the feed -- maps of package names --> Package objects (or list of
#  Package objects in virt_pkg_map's case)
real_pkg_map = {} # contains packages implemented by an IPK of the same name
virt_pkg_map = {} # contains list of packages implemented by an IPK of _different_ name (E.g. via Provides)
missing_pkg_map = {} # contains packages not implemented by any IPK; stub packages for broken deps
active_pkg_map = {} # union of the above, with name collision resolved

real_pkg_replace_count = 0 # number of real package collisions

# Populate real_pkg_map and active_pkg_map with all real packages defined by
# indexes. Do this first to resolve collisions between real packages
# before adding virtual packages (alias).
# Add all real packages to the graph.
for indexFilePath in index_files:
    feedDir = os.path.dirname(indexFilePath)
    feedDir = os.path.relpath(feedDir, start=os.getcwd())

    debug("Reading index file %s" % indexFilePath)
    packages = opkg.Packages()
    packages.read_packages_file(indexFilePath)

    # add each package
    for pkgKey in list(packages.keys()):
        pkg = packages[pkgKey]

        # sanity check: verify important attributes are defined for
        # every package
        if not pkg.package:
            fatal_error("A package in index %s is missing the Package field; i.e. it's name" % indexFilePath)
        if not pkg.filename:
            fatal_error("Package %s from index %s is missing Filename field" % (pkg.package, indexFilePath))
        if not pkg.version or pkg.version == 'none':
            warn("Missing field: Version in package %s" % pkg.package)
        if not pkg.architecture:
            warn("Missing field: Architecture in package %s" % pkg.package)

        # save package filename relative to sub-feed dir
        pkg.fn = os.path.join(feedDir, pkg.filename)

        if pkg.package in real_pkg_map:
            # pkg is being replaced
            replacedPkg = real_pkg_map[pkg.package]

            real_pkg_replace_count = real_pkg_replace_count + 1
            warn("Duplicate package: Replacing %s with %s" % (
                pkg_label(replacedPkg, includePath=True),
                pkg_label(pkg, includePath=True) ))

        debug("Add real package %s" % pkg_label(pkg) )
        real_pkg_map[pkg.package] = pkg
        active_pkg_map[pkg.package] = pkg

        add_package_to_graph(pkg)

# Populate virt_pkg_map and active_pkg_map with virtual (Provides) packages.
# Virtual packages in virt_pkg_map and active_pkg_map point to a real
# Package object that's in real_pkg_map under a different name and
# provides the alias.
# These packages are not added to the graph because their implementations
# are already there.
for pkgKey, pkg in six.iteritems(real_pkg_map):
    for alias in split_dep_list(pkg.provides):
        if alias not in active_pkg_map:
            # add it
            debug("Add alias %s for package %s" % (alias, pkg_label(pkg)) )
            virt_pkg_map[alias] = [pkg]
            active_pkg_map[alias] = pkg
        else:
            oldPkg = active_pkg_map[alias]

            # are they the same object?
            if pkg is oldPkg:
                # weird, not an error, but worth documenting
                warn("Self alias: %s explicitly provides itself" % pkg_label(pkg))
                continue

            if alias in real_pkg_map:
                warn("Virtual-real alias: %s attempts to provide %s, which is already implemented by real package %s; skipping." % (
                    pkg_label(pkg), alias, pkg_label(oldPkg) ))
                continue

            # When there are more than one implementations of one name,
            # use the one with the smallest alphabetical package name
            if pkg.package < oldPkg.package:
                debug("Replacing alias %s (%s) with package %s" % (alias, pkg_label(oldPkg), pkg_label(pkg)) )
                virt_pkg_map[alias].insert(0, pkg)
                active_pkg_map[alias] = pkg
            else:
                debug("Skipping replacer alias %s from package %s; >= package %s" % (alias, pkg_label(pkg), pkg_label(oldPkg)) )
                virt_pkg_map[alias].append(pkg)

# Print alternatives for virtual packages
for pkgKey, pkgList in six.iteritems(virt_pkg_map):
    if len(pkgList) > 1:
        pkgNameList = ','.join( [x.package for x in pkgList] )
        debug("%s alternate implementations of package %s: %s" % (len(pkgList), pkgKey, pkgNameList))

    # sanity check
    if pkgList[0] is not active_pkg_map[pkgKey]:
        fatal_error('Uh oh, head of alternatives list is not the active package')

# Create stub packages in missing_pkg_map and active_pkg_map for broken
# dependencies, and add them to the graph.
for pkgKey, pkg in six.iteritems(real_pkg_map):
    for depName in split_dep_list(pkg.depends):
        if not depName in active_pkg_map:
            warn("Broken dependency: %s --> %s (missing)" % (
                pkg_label(pkg), depName ))

            stub = opkg.Package()
            stub.package = depName

            # don't update real_pkg_map, stub is not a real package
            missing_pkg_map[stub.package] = stub
            active_pkg_map[stub.package] = stub

            add_package_to_graph(stub, missing=True)

# process dependencies
# add edges to graph
for pkgKey, pkg in six.iteritems(real_pkg_map):
    for depName in split_dep_list(pkg.depends):
        depPkg = active_pkg_map[depName]

        add_dependency_to_graph(pkg, depPkg,
            alias=(depName if (depName != depPkg.package) else None),
            broken=(depPkg.package in missing_pkg_map) )

# Results
print("%s total packages are referenced in the feed" % len(active_pkg_map))
print(" %s real packages (%s collisions)" % ( len(real_pkg_map), real_pkg_replace_count ))
print(" %s virtual packages" % len(virt_pkg_map))
print(" %s missing packages" % len(missing_pkg_map))

# sanity check
if len(active_pkg_map) != (len(real_pkg_map) + len(virt_pkg_map) + len(missing_pkg_map)):
    fatal_error('Uh oh, the package counts don\'t add up.')

# Write the graph
graph.write(path=dot_filename)
print("Graphed at %s" % dot_filename)