summaryrefslogtreecommitdiff
path: root/support/scripts/graph-depends
blob: fbd591705367a20a6dc68543731f7d82cc3ef0d2 (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
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
#!/usr/bin/python

# Usage (the graphviz package must be installed in your distribution)
#  ./support/scripts/graph-depends [-p package-name] > test.dot
#  dot -Tpdf test.dot -o test.pdf
#
# With no arguments, graph-depends will draw a complete graph of
# dependencies for the current configuration.
# If '-p <package-name>' is specified, graph-depends will draw a graph
# of dependencies for the given package name.
# If '-d <depth>' is specified, graph-depends will limit the depth of
# the dependency graph to 'depth' levels.
#
# Limitations
#
#  * Some packages have dependencies that depend on the Buildroot
#    configuration. For example, many packages have a dependency on
#    openssl if openssl has been enabled. This tool will graph the
#    dependencies as they are with the current Buildroot
#    configuration.
#
# Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>

import sys
import subprocess
import argparse
from fnmatch import fnmatch

import pkgutil

# Modes of operation:
MODE_FULL = 1   # draw full dependency graph for all selected packages
MODE_PKG  = 2   # draw dependency graph for a given package
mode = 0

# Limit drawing the dependency graph to this depth. 0 means 'no limit'.
max_depth = 0

# Whether to draw the transitive dependencies
transitive = True

parser = argparse.ArgumentParser(description="Graph packages dependencies")
parser.add_argument("--check-only", "-C", dest="check_only", action="store_true", default=False,
                    help="Only do the dependency checks (circular deps...)")
parser.add_argument("--outfile", "-o", metavar="OUT_FILE", dest="outfile",
                    help="File in which to generate the dot representation")
parser.add_argument("--package", '-p', metavar="PACKAGE",
                    help="Graph the dependencies of PACKAGE")
parser.add_argument("--depth", '-d', metavar="DEPTH", dest="depth", type=int, default=0,
                    help="Limit the dependency graph to DEPTH levels; 0 means no limit.")
parser.add_argument("--stop-on", "-s", metavar="PACKAGE", dest="stop_list", action="append",
                    help="Do not graph past this package (can be given multiple times)." \
                       + " Can be a package name or a glob, " \
                       + " 'virtual' to stop on virtual packages, or " \
                       + "'host' to stop on host packages.")
parser.add_argument("--exclude", "-x", metavar="PACKAGE", dest="exclude_list", action="append",
                    help="Like --stop-on, but do not add PACKAGE to the graph.")
parser.add_argument("--colours", "-c", metavar="COLOR_LIST", dest="colours",
                    default="lightblue,grey,gainsboro",
                    help="Comma-separated list of the three colours to use" \
                       + " to draw the top-level package, the target" \
                       + " packages, and the host packages, in this order." \
                       + " Defaults to: 'lightblue,grey,gainsboro'")
parser.add_argument("--transitive", dest="transitive", action='store_true',
                    default=False)
parser.add_argument("--no-transitive", dest="transitive", action='store_false',
                    help="Draw (do not draw) transitive dependencies")
parser.add_argument("--direct", dest="direct", action='store_true', default=True,
                    help="Draw direct dependencies (the default)")
parser.add_argument("--reverse", dest="direct", action='store_false',
                    help="Draw reverse dependencies")
args = parser.parse_args()

check_only = args.check_only

if args.outfile is None:
    outfile = sys.stdout
else:
    if check_only:
        sys.stderr.write("don't specify outfile and check-only at the same time\n")
        sys.exit(1)
    outfile = open(args.outfile, "w")

if args.package is None:
    mode = MODE_FULL
else:
    mode = MODE_PKG
    rootpkg = args.package

max_depth = args.depth

if args.stop_list is None:
    stop_list = []
else:
    stop_list = args.stop_list

if args.exclude_list is None:
    exclude_list = []
else:
    exclude_list = args.exclude_list

transitive = args.transitive

if args.direct:
    get_depends_func = pkgutil.get_depends
    arrow_dir = "forward"
else:
    if mode == MODE_FULL:
        sys.stderr.write("--reverse needs a package\n")
        sys.exit(1)
    get_depends_func = pkgutil.get_rdepends
    arrow_dir = "back"

# Get the colours: we need exactly three colours,
# so no need not split more than 4
# We'll let 'dot' validate the colours...
colours = args.colours.split(',',4)
if len(colours) != 3:
    sys.stderr.write("Error: incorrect colour list '%s'\n" % args.colours)
    sys.exit(1)
root_colour = colours[0]
target_colour = colours[1]
host_colour = colours[2]

allpkgs = []

# Execute the "make show-targets" command to get the list of the main
# Buildroot PACKAGES and return it formatted as a Python list. This
# list is used as the starting point for full dependency graphs
def get_targets():
    sys.stderr.write("Getting targets\n")
    cmd = ["make", "-s", "--no-print-directory", "show-targets"]
    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
    output = p.communicate()[0].strip()
    if p.returncode != 0:
        return None
    if output == '':
        return []
    return output.split(' ')

# Recursive function that builds the tree of dependencies for a given
# list of packages. The dependencies are built in a list called
# 'dependencies', which contains tuples of the form (pkg1 ->
# pkg2_on_which_pkg1_depends, pkg3 -> pkg4_on_which_pkg3_depends) and
# the function finally returns this list.
def get_all_depends(pkgs):
    dependencies = []

    # Filter the packages for which we already have the dependencies
    filtered_pkgs = []
    for pkg in pkgs:
        if pkg in allpkgs:
            continue
        filtered_pkgs.append(pkg)
        allpkgs.append(pkg)

    if len(filtered_pkgs) == 0:
        return []

    depends = get_depends_func(filtered_pkgs)

    deps = set()
    for pkg in filtered_pkgs:
        pkg_deps = depends[pkg]

        # This package has no dependency.
        if pkg_deps == []:
            continue

        # Add dependencies to the list of dependencies
        for dep in pkg_deps:
            dependencies.append((pkg, dep))
            deps.add(dep)

    if len(deps) != 0:
        newdeps = get_all_depends(deps)
        if newdeps is not None:
            dependencies += newdeps

    return dependencies

# The Graphviz "dot" utility doesn't like dashes in node names. So for
# node names, we strip all dashes.
def pkg_node_name(pkg):
    return pkg.replace("-","")

TARGET_EXCEPTIONS = [
    "target-finalize",
    "target-post-image",
]

# In full mode, start with the result of get_targets() to get the main
# targets and then use get_all_depends() for all targets
if mode == MODE_FULL:
    targets = get_targets()
    dependencies = []
    allpkgs.append('all')
    filtered_targets = []
    for tg in targets:
        # Skip uninteresting targets
        if tg in TARGET_EXCEPTIONS:
            continue
        dependencies.append(('all', tg))
        filtered_targets.append(tg)
    deps = get_all_depends(filtered_targets)
    if deps is not None:
        dependencies += deps
    rootpkg = 'all'

# In pkg mode, start directly with get_all_depends() on the requested
# package
elif mode == MODE_PKG:
    dependencies = get_all_depends([rootpkg])

# Make the dependencies a dictionnary { 'pkg':[dep1, dep2, ...] }
dict_deps = {}
for dep in dependencies:
    if dep[0] not in dict_deps:
        dict_deps[dep[0]] = []
    dict_deps[dep[0]].append(dep[1])

# Basic cache for the results of the is_dep() function, in order to
# optimize the execution time. The cache is a dict of dict of boolean
# values. The key to the primary dict is "pkg", and the key of the
# sub-dicts is "pkg2".
is_dep_cache = {}

def is_dep_cache_insert(pkg, pkg2, val):
    try:
        is_dep_cache[pkg].update({pkg2: val})
    except KeyError:
        is_dep_cache[pkg] = {pkg2: val}

# Retrieves from the cache whether pkg2 is a transitive dependency
# of pkg.
# Note: raises a KeyError exception if the dependency is not known.
def is_dep_cache_lookup(pkg, pkg2):
    return is_dep_cache[pkg][pkg2]

# This function return True if pkg is a dependency (direct or
# transitive) of pkg2, dependencies being listed in the deps
# dictionary. Returns False otherwise.
# This is the un-cached version.
def is_dep_uncached(pkg,pkg2,deps):
    try:
        for p in deps[pkg2]:
            if pkg == p:
                return True
            if is_dep(pkg,p,deps):
                return True
    except KeyError:
        pass
    return False

# See is_dep_uncached() above; this is the cached version.
def is_dep(pkg,pkg2,deps):
    try:
        return is_dep_cache_lookup(pkg, pkg2)
    except KeyError:
        val = is_dep_uncached(pkg, pkg2, deps)
        is_dep_cache_insert(pkg, pkg2, val)
        return val

# This function eliminates transitive dependencies; for example, given
# these dependency chain: A->{B,C} and B->{C}, the A->{C} dependency is
# already covered by B->{C}, so C is a transitive dependency of A, via B.
# The functions does:
#   - for each dependency d[i] of the package pkg
#     - if d[i] is a dependency of any of the other dependencies d[j]
#       - do not keep d[i]
#     - otherwise keep d[i]
def remove_transitive_deps(pkg,deps):
    d = deps[pkg]
    new_d = []
    for i in range(len(d)):
        keep_me = True
        for j in range(len(d)):
            if j==i:
                continue
            if is_dep(d[i],d[j],deps):
                keep_me = False
        if keep_me:
            new_d.append(d[i])
    return new_d

# This function removes the dependency on some 'mandatory' package, like the
# 'toolchain' package, or the 'skeleton' package
def remove_mandatory_deps(pkg,deps):
    return [p for p in deps[pkg] if p not in ['toolchain', 'skeleton']]

# This function will check that there is no loop in the dependency chain
# As a side effect, it builds up the dependency cache.
def check_circular_deps(deps):
    def recurse(pkg):
        if not pkg in list(deps.keys()):
            return
        if pkg in not_loop:
            return
        not_loop.append(pkg)
        chain.append(pkg)
        for p in deps[pkg]:
            if p in chain:
                sys.stderr.write("\nRecursion detected for  : %s\n" % (p))
                while True:
                    _p = chain.pop()
                    sys.stderr.write("which is a dependency of: %s\n" % (_p))
                    if p == _p:
                        sys.exit(1)
            recurse(p)
        chain.pop()

    not_loop = []
    chain = []
    for pkg in list(deps.keys()):
        recurse(pkg)

# This functions trims down the dependency list of all packages.
# It applies in sequence all the dependency-elimination methods.
def remove_extra_deps(deps):
    for pkg in list(deps.keys()):
        if not pkg == 'all':
            deps[pkg] = remove_mandatory_deps(pkg,deps)
    for pkg in list(deps.keys()):
        if not transitive or pkg == 'all':
            deps[pkg] = remove_transitive_deps(pkg,deps)
    return deps

check_circular_deps(dict_deps)
if check_only:
    sys.exit(0)

dict_deps = remove_extra_deps(dict_deps)
dict_version = pkgutil.get_version([pkg for pkg in allpkgs
                                if pkg != "all" and not pkg.startswith("root")])

# Print the attributes of a node: label and fill-color
def print_attrs(pkg):
    name = pkg_node_name(pkg)
    if pkg == 'all':
        label = 'ALL'
    else:
        label = pkg
    if pkg == 'all' or (mode == MODE_PKG and pkg == rootpkg):
        color = root_colour
    else:
        if pkg.startswith('host') \
        or pkg.startswith('toolchain') \
        or pkg.startswith('rootfs'):
            color = host_colour
        else:
            color = target_colour
    version = dict_version.get(pkg)
    if version == "virtual":
        outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label))
    else:
        outfile.write("%s [label = \"%s\"]\n" % (name, label))
    outfile.write("%s [color=%s,style=filled]\n" % (name, color))

# Print the dependency graph of a package
def print_pkg_deps(depth, pkg):
    if pkg in done_deps:
        return
    done_deps.append(pkg)
    print_attrs(pkg)
    if pkg not in dict_deps:
        return
    for p in stop_list:
        if fnmatch(pkg, p):
            return
    if dict_version.get(pkg) == "virtual" and "virtual" in stop_list:
        return
    if pkg.startswith("host-") and "host" in stop_list:
        return
    if max_depth == 0 or depth < max_depth:
        for d in dict_deps[pkg]:
            if dict_version.get(d) == "virtual" \
               and "virtual" in exclude_list:
                continue
            if d.startswith("host-") \
               and "host" in exclude_list:
                continue
            add = True
            for p in exclude_list:
                if fnmatch(d,p):
                    add = False
                    break
            if add:
                outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), arrow_dir))
                print_pkg_deps(depth+1, d)

# Start printing the graph data
outfile.write("digraph G {\n")

done_deps = []
print_pkg_deps(0, rootpkg)

outfile.write("}\n")