summaryrefslogtreecommitdiffstats
path: root/opkg-graph-deps
blob: 6653fd5cea51b85f4eded4cd079c1fc52bc472de (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#!/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)