Skip to contentSkip to conversation

Add contrib script to find dependency chains

PATCH In review Paul Eggleton 2 participants 4 messages Dec 17, 2013

lore
Share & tools
lore
#0 lore raw

cover Add contrib script to find dependency chains

The following changes since commit b226ab4cf7779f4dfaa78210cb6249766ed564c1:

insane: handle recursive configures when checking for unknown configure options (2013-12-16 12:12:40 +0000)

are available in the git repository at:

git://git.openembedded.org/openembedded-core-contrib paule/graph-tool
http://cgit.openembedded.org/cgit.cgi/openembedded-core-contrib/log/?h=paule/graph-tool

Paul Eggleton (1):
scripts/contrib: Add graph-tool

 scripts/contrib/graph-tool | 92 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)
 create mode 100755 scripts/contrib/graph-tool
Signature · 1 line
1.8.1.2
#1 lore raw

PATCH 1/1 scripts/contrib: Add graph-tool

A simple script I put together for getting the paths from one node to another in a dot graph. This is useful for example in working out why a particular recipe is getting built in conjunction with dot graph files produced by bitbake -g.

For example:

$ bitbake -g core-image-minimal
...
$ graph-tool find-paths pn-depends.dot core-image-minimal sqlite3-native
core-image-minimal -> packagegroup-core-boot -> udev -> libxslt-native -> libxml2-native -> python-native -> sqlite3-native

Partially addresses [YOCTO #3362].

---
 scripts/contrib/graph-tool | 92 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)
 create mode 100755 scripts/contrib/graph-tool
scripts/contrib/graph-tool new file +92 -0
new file mode 100755
index 0000000..6dc7d33
@@ -0,0 +1,92 @@
+#!/usr/bin/env python
+
+# Simple graph query utility
+# useful for getting answers from .dot files produced by bitbake -g
+#
+# Written by: Paul Eggleton <[email protected]>
+#
+# Copyright 2013 Intel Corporation
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License version 2 as
+# published by the Free Software Foundation.
+#
+# 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, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+#
+
+import sys
+
+def get_path_networkx(dotfile, fromnode, tonode):
+    try:
+        import networkx
+    except ImportError:
+        print('ERROR: Please install the networkx python module')
+        sys.exit(1)
+
+    graph = networkx.DiGraph(networkx.read_dot(dotfile))
+
+    def node_missing(node):
+        import difflib
+        close_matches = difflib.get_close_matches(node, graph.nodes(), cutoff=0.7)
+        if close_matches:
+            print('ERROR: no node "%s" in graph. Close matches:\n  %s' % (node, '\n  '.join(close_matches)))
+        sys.exit(1)
+
+    if not fromnode in graph:
+        node_missing(fromnode)
+    if not tonode in graph:
+        node_missing(tonode)
+    return networkx.all_simple_paths(graph, source=fromnode, target=tonode)
+
+
+def find_paths(args, usage):
+    if len(args) < 3:
+        usage()
+        sys.exit(1)
+
+    fromnode = args[1]
+    tonode = args[2]
+    paths = list(get_path_networkx(args[0], fromnode, tonode))
+    if paths:
+        for path in paths:
+            print ' -> '.join(path)
+    else:
+        print("ERROR: no path from %s to %s in graph" % (fromnode, tonode))
+        sys.exit(1)
+
+def main():
+    import optparse
+    parser = optparse.OptionParser(
+        usage = '''%prog [options] <command> <arguments>
+
+Available commands:
+    find-paths <dotfile> <from> <to>
+        Find all of the paths between two nodes in a dot graph''')
+
+    #parser.add_option("-d", "--debug",
+    #        help = "Report all SRCREV values, not just ones where AUTOREV has been used",
+    #        action="store_true", dest="debug", default=False)
+
+    options, args = parser.parse_args(sys.argv)
+    args = args[1:]
+
+    if len(args) < 1:
+        parser.print_help()
+        sys.exit(1)
+
+    if args[0] == "find-paths":
+        find_paths(args[1:], parser.print_help)
+    else:
+        parser.print_help()
+        sys.exit(1)
+
+
+if __name__ == "__main__":
+    main()
Signature · 1 line
1.8.1.2
#2 lore raw

Re: [PATCH 1/1] scripts/contrib: Add graph-tool

Quoted 11 lines · Paul Eggleton

A simple script I put together for getting the paths from one node to another in a dot graph. This is useful for example in working out why a particular recipe is getting built in conjunction with dot graph files produced by bitbake -g.

For example:

$ bitbake -g core-image-minimal
...
$ graph-tool find-paths pn-depends.dot core-image-minimal sqlite3-native
core-image-minimal -> packagegroup-core-boot -> udev -> libxslt-native -> libxml2-native -> python-native -> sqlite3-native

Nice addition, thanks.

Can it show multiple paths? Maybe it would be better example to show it on multiple-path case.

As future improvement it would be nice to be able to filter some paths, e.g. sometimes I'm interested in runtime-dependencies, sometimes finding path through runtime isn't enough (e.g. when my recipe has runtime dependency of "foo" but actually needs "foo" at build time).

Quoted 113 lines

Partially addresses [YOCTO #3362].

---
 scripts/contrib/graph-tool | 92 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)
 create mode 100755 scripts/contrib/graph-tool
scripts/contrib/graph-tool new file +92 -0
new file mode 100755
index 0000000..6dc7d33
@@ -0,0 +1,92 @@
+#!/usr/bin/env python
+
+# Simple graph query utility
+# useful for getting answers from .dot files produced by bitbake -g
+#
+# Written by: Paul Eggleton <[email protected]>
+#
+# Copyright 2013 Intel Corporation
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License version 2 as
+# published by the Free Software Foundation.
+#
+# 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, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+#
+
+import sys
+
+def get_path_networkx(dotfile, fromnode, tonode):
+    try:
+        import networkx
+    except ImportError:
+        print('ERROR: Please install the networkx python module')
+        sys.exit(1)
+
+    graph = networkx.DiGraph(networkx.read_dot(dotfile))
+
+    def node_missing(node):
+        import difflib
+        close_matches = difflib.get_close_matches(node, graph.nodes(), cutoff=0.7)
+        if close_matches:
+            print('ERROR: no node "%s" in graph. Close matches:\n  %s' % (node, '\n  '.join(close_matches)))
+        sys.exit(1)
+
+    if not fromnode in graph:
+        node_missing(fromnode)
+    if not tonode in graph:
+        node_missing(tonode)
+    return networkx.all_simple_paths(graph, source=fromnode, target=tonode)
+
+
+def find_paths(args, usage):
+    if len(args) < 3:
+        usage()
+        sys.exit(1)
+
+    fromnode = args[1]
+    tonode = args[2]
+    paths = list(get_path_networkx(args[0], fromnode, tonode))
+    if paths:
+        for path in paths:
+            print ' -> '.join(path)
+    else:
+        print("ERROR: no path from %s to %s in graph" % (fromnode, tonode))
+        sys.exit(1)
+
+def main():
+    import optparse
+    parser = optparse.OptionParser(
+        usage = '''%prog [options] <command> <arguments>
+
+Available commands:
+    find-paths <dotfile> <from> <to>
+        Find all of the paths between two nodes in a dot graph''')
+
+    #parser.add_option("-d", "--debug",
+    #        help = "Report all SRCREV values, not just ones where AUTOREV has been used",
+    #        action="store_true", dest="debug", default=False)
+
+    options, args = parser.parse_args(sys.argv)
+    args = args[1:]
+
+    if len(args) < 1:
+        parser.print_help()
+        sys.exit(1)
+
+    if args[0] == "find-paths":
+        find_paths(args[1:], parser.print_help)
+    else:
+        parser.print_help()
+        sys.exit(1)
+
+
+if __name__ == "__main__":
+    main()
Signature · 6 lines
1.8.1.2

_______________________________________________
Openembedded-core mailing list
[email protected]
http://lists.openembedded.org/mailman/listinfo/openembedded-core
Signature · 1 line
Martin 'JaMa' Jansa     jabber: [email protected]
#3 lore raw

Re: [PATCH 1/1] scripts/contrib: Add graph-tool

Quoted 13 lines · On Tuesday 17 December 2013 18:16:35 Martin Jansa wrote:
Quoted 5 lines · Paul Eggleton

A simple script I put together for getting the paths from one node to another in a dot graph. This is useful for example in working out why a particular recipe is getting built in conjunction with dot graph files produced by bitbake -g.

Quoted 7 lines

For example:

$ bitbake -g core-image-minimal
...
$ graph-tool find-paths pn-depends.dot core-image-minimal sqlite3-native
core-image-minimal -> packagegroup-core-boot -> udev -> libxslt-native ->
libxml2-native -> python-native -> sqlite3-native
Quoted 4 lines

Nice addition, thanks.

Can it show multiple paths? Maybe it would be better example to show it on multiple-path case.

It can, yes:

$ graph-tool find-paths pn-depends.dot core-image-minimal util-linux
core-image-minimal -> packagegroup-core-boot -> udev -> glib-2.0 -> python-dbus -> dbus-glib -> dbus -> libsm -> e2fsprogs -> util-linux
core-image-minimal -> packagegroup-core-boot -> udev -> glib-2.0 -> python-dbus -> dbus -> libsm -> e2fsprogs -> util-linux
core-image-minimal -> packagegroup-core-boot -> udev -> util-linux

I've updated the branch to use this example.

Quoted 4 lines

As future improvement it would be nice to be able to filter some paths, e.g. sometimes I'm interested in runtime-dependencies, sometimes finding path through runtime isn't enough (e.g. when my recipe has runtime dependency of "foo" but actually needs "foo" at build time).

Well, this script isn't very intelligent - it only operates on single graphs, and isn't a complete tool, hence why I added it to contrib. There's certainly scope for more work in this area, but I suspect it would be in a different tool which is closer to the build system itself (such as Toaster).

Cheers,
Paul

Signature · 2 lines
Paul Eggleton
Intel Open Source Technology Centre