graph-depends improvements (branch yem/graphs)

index 6d97262..d91231c 100644
@@ -150,7 +150,6 @@ endif
 # Need that early, before we scan packages
 # Avoids doing the $(or...) everytime
 BR_GRAPH_OUT := $(or $(BR2_GRAPH_OUT),pdf)
-BR_GRAPH_DEPTH := $(or $(BR2_GRAPH_DEPTH),0)
 
 BUILD_DIR := $(BASE_DIR)/build
 BINARIES_DIR := $(BASE_DIR)/images

@@ -675,7 +674,7 @@ graph-build: $(O)/build/build-time.log
 graph-depends:
 	@$(INSTALL) -d $(O)/graphs
 	@cd "$(CONFIG_DIR)"; \
-	$(TOPDIR)/support/scripts/graph-depends -d $(BR_GRAPH_DEPTH) \
+	$(TOPDIR)/support/scripts/graph-depends $(BR2_GRAPH_DEPS_OPTS) \
 	|tee $(O)/graphs/$(@).dot \
 	|dot -T$(BR_GRAPH_OUT) -o $(O)/graphs/$(@).$(BR_GRAPH_OUT)
 

index 3d5842d..772982a 100644
@@ -92,8 +92,8 @@ to +make+ or set in the environment:
   build-time graphs
 * +BR2_GRAPH_OUT+ to set the filetype of generated graphs, either +pdf+ (the
   default), or +png+.
-* +BR2_GRAPH_DEPTH+ (an integer) to limit the depth of the dependency graph.
-  The default, +0+, is to not limit the depth.
+* +BR2_GRAPH_DEPS_OPTS+ to pass extra options to the dependency graph; see
+  xref:graph-depends[] for the accepted options
 
 An example that uses config files located in the toplevel directory and
 in your $HOME:

@@ -198,6 +198,16 @@ supported.
 BR2_GRAPH_OUT=svg make graph-depends
 --------------------------------
 
+The +graph-depends+ behaviour can be controlled by setting options in the
++BR2_GRAPH_DEPS_OPTS+ environment variable. The accepted options are:
+
+* +--depth N+, +-d N+, to limit the dependency depth to +N+ levels. The
+  default, +0+, means no limit.
+
+--------------------------------
+BR2_GRAPH_DEPS_OPTS='-d 3' make graph-depends
+--------------------------------
+
 === Graphing the build duration
 
 [[graph-duration]]

new file mode 100644
index 0000000..e69de29

index 6eca6d4..426d269 100644
@@ -512,7 +512,7 @@ $(1)-show-depends:
 $(1)-graph-depends:
 			@$(INSTALL) -d $(O)/graphs
 			@cd "$(CONFIG_DIR)"; \
-			$(TOPDIR)/support/scripts/graph-depends -p $(1) -d $(BR_GRAPH_DEPTH) \
+			$(TOPDIR)/support/scripts/graph-depends -p $(1) $(BR2_GRAPH_DEPS_OPTS) \
 			|tee $(O)/graphs/$$(@).dot \
 			|dot -T$(BR_GRAPH_OUT) -o $(O)/graphs/$$(@).$(BR_GRAPH_OUT)
 

index e2a5e1e..4ad18b4 100755
@@ -40,6 +40,10 @@ parser.add_argument("--package", '-p', metavar="PACKAGE",
                     help="Graph the dependencies of PACKAGE")
 parser.add_argument("--depth", '-d', metavar="DEPTH",
                     help="Limit the dependency graph to DEPTH levels")
+parser.add_argument("--transitive", dest="transitive", action='store_true')
+parser.add_argument("--no-transitive", dest="transitive", action='store_false',
+                    default=True,
+                    help="Draw (do not draw) transitive dependencies")
 args = parser.parse_args()
 
 if args.package is None:

@@ -51,6 +55,8 @@ else:
 if args.depth is not None:
     max_depth = int(args.depth)
 
+transitive = args.transitive
+
 allpkgs = []
 
 # Execute the "make show-targets" command to get the list of the main

@@ -220,6 +226,49 @@ for dep in dependencies:
         dict_deps[dep[0]] = []
     dict_deps[dep[0]].append(dep[1])
 
+# This function return True if pkg is a dependency (direct or
+# transitive) of pkg2, dependencies being listed in the deps
+# dictionary. Returns False otherwise.
+def is_dep(pkg,pkg2,deps):
+    if deps.has_key(pkg2):
+        for p in deps[pkg2]:
+            if pkg == p:
+                return True
+            if is_dep(pkg,p,deps):
+                return True
+    return False
+
+# 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 functions trims down the dependency list of all packages.
+def remove_extra_deps(deps):
+    for pkg in deps.keys():
+        if not transitive:
+            deps[pkg] = remove_transitive_deps(pkg,deps)
+    return deps
+
+dict_deps = remove_extra_deps(dict_deps)
+
 # Print the attributes of a node: label and fill-color
 def print_attrs(pkg):
     if pkg == 'all':

index 4ad18b4..1146ed4 100755
@@ -146,40 +146,6 @@ def get_all_depends(pkgs):
 def pkg_node_name(pkg):
     return pkg.replace("-","")
 
-# Helper function for remove_redundant_deps(). This function tells
-# whether package "pkg" is the dependency of another package that is
-# not the special "all" package.
-def has_redundant_deps(deps, pkg):
-    for dep in deps:
-        if dep[0] != "all" and dep[1] == pkg:
-            return True
-    return False
-
-# This function removes redundant dependencies of the special "all"
-# package. This "all" package is created to reflect the origin of the
-# selection for all packages that are not themselves selected by any
-# other package. So for example if you enable libpng, zlib is enabled
-# as a dependency. But zlib being selected by libpng, it also appears
-# as a dependency of the "all" package. This needlessly complicates
-# the generated dependency graph. So when we have the dependency list
-# (all -> zlib, all -> libpn, libpng -> zlib), we get rid of the 'all
-# -> zlib' dependency, because zlib is already a dependency of a
-# regular package.
-def remove_redundant_deps(deps):
-    newdeps = []
-    for dep in deps:
-        if dep[0] == "all" and dep[1] == "toolchain":
-            newdeps.append(dep)
-            continue
-        if dep[0] != "all" and dep[1] != "toolchain":
-            newdeps.append(dep)
-            continue
-        if not has_redundant_deps(deps, dep[1]):
-            newdeps.append(dep)
-            continue
-        sys.stderr.write("Removing redundant dep %s -> %s\n" % (dep[0],dep[1]))
-    return newdeps
-
 TARGET_EXCEPTIONS = [
     "target-generic-securetty",
     "target-generic-issue",

@@ -217,8 +183,6 @@ if mode == FULL_MODE:
 elif mode == PKG_MODE:
     dependencies = get_all_depends([rootpkg])
 
-dependencies = remove_redundant_deps(dependencies)
-
 # Make the dependencies a dictionnary { 'pkg':[dep1, dep2, ...] }
 dict_deps = {}
 for dep in dependencies:

@@ -260,10 +224,18 @@ def remove_transitive_deps(pkg,deps):
             new_d.append(d[i])
     return new_d
 
+# This function removes the dependency on the 'toolchain' package
+def remove_toolchain_deps(pkg,deps):
+    return [p for p in deps[pkg] if not p == 'toolchain']
+
 # 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 deps.keys():
-        if not transitive:
+        if not pkg == 'all':
+            deps[pkg] = remove_toolchain_deps(pkg,deps)
+    for pkg in deps.keys():
+        if not transitive or pkg == 'all':
             deps[pkg] = remove_transitive_deps(pkg,deps)
     return deps
 

index 1146ed4..c3dcbf1 100755
@@ -33,13 +33,15 @@ FULL_MODE = 1
 PKG_MODE  = 2
 
 mode = 0
+
+# Limit drawing the dependency graph to this depth. 0 means 'no limit'.
 max_depth = 0
 
 parser = argparse.ArgumentParser(description="Graph pacakges dependencies")
 parser.add_argument("--package", '-p', metavar="PACKAGE",
                     help="Graph the dependencies of PACKAGE")
-parser.add_argument("--depth", '-d', metavar="DEPTH",
-                    help="Limit the dependency graph to DEPTH levels")
+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("--transitive", dest="transitive", action='store_true')
 parser.add_argument("--no-transitive", dest="transitive", action='store_false',
                     default=True,

@@ -52,8 +54,7 @@ else:
     mode = PKG_MODE
     rootpkg = args.package
 
-if args.depth is not None:
-    max_depth = int(args.depth)
+max_depth = args.depth
 
 transitive = args.transitive
 

index c3dcbf1..dc6b98f 100755
@@ -37,6 +37,9 @@ 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 pacakges dependencies")
 parser.add_argument("--package", '-p', metavar="PACKAGE",
                     help="Graph the dependencies of PACKAGE")

index dc6b98f..86af779 100755
@@ -25,13 +25,9 @@ import sys
 import subprocess
 import argparse
 
-# In FULL_MODE, we draw the full dependency graph for all selected
-# packages
-FULL_MODE = 1
-
-# In PKG_MODE, we only draw the dependency graph for a given package
-PKG_MODE  = 2
-
+# 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'.

@@ -52,9 +48,9 @@ parser.add_argument("--no-transitive", dest="transitive", action='store_false',
 args = parser.parse_args()
 
 if args.package is None:
-    mode = FULL_MODE
+    mode = MODE_FULL
 else:
-    mode = PKG_MODE
+    mode = MODE_PKG
     rootpkg = args.package
 
 max_depth = args.depth

@@ -166,7 +162,7 @@ TARGET_EXCEPTIONS = [
 
 # 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 == FULL_MODE:
+if mode == MODE_FULL:
     targets = get_targets()
     dependencies = []
     allpkgs.append('all')

@@ -184,7 +180,7 @@ if mode == FULL_MODE:
 
 # In pkg mode, start directly with get_all_depends() on the requested
 # package
-elif mode == PKG_MODE:
+elif mode == MODE_PKG:
     dependencies = get_all_depends([rootpkg])
 
 # Make the dependencies a dictionnary { 'pkg':[dep1, dep2, ...] }

@@ -252,7 +248,7 @@ def print_attrs(pkg):
         print "all [color=lightblue,style=filled]"
         return
     print "%s [label = \"%s\"]" % (pkg_node_name(pkg), pkg)
-    if mode == PKG_MODE and pkg == rootpkg:
+    if mode == MODE_PKG and pkg == rootpkg:
         print "%s [color=lightblue,style=filled]" % pkg_node_name(rootpkg)
     else:
         print "%s [color=grey,style=filled]" % pkg_node_name(pkg)

index d91231c..950f95f 100644
@@ -676,7 +676,7 @@ graph-depends:
 	@cd "$(CONFIG_DIR)"; \
 	$(TOPDIR)/support/scripts/graph-depends $(BR2_GRAPH_DEPS_OPTS) \
 	|tee $(O)/graphs/$(@).dot \
-	|dot -T$(BR_GRAPH_OUT) -o $(O)/graphs/$(@).$(BR_GRAPH_OUT)
+	|dot $(BR2_GRAPH_DOT_OPTS) -T$(BR_GRAPH_OUT) -o $(O)/graphs/$(@).$(BR_GRAPH_OUT)
 
 else # ifeq ($(BR2_HAVE_DOT_CONFIG),y)
 

index 426d269..9251290 100644
@@ -514,7 +514,7 @@ $(1)-graph-depends:
 			@cd "$(CONFIG_DIR)"; \
 			$(TOPDIR)/support/scripts/graph-depends -p $(1) $(BR2_GRAPH_DEPS_OPTS) \
 			|tee $(O)/graphs/$$(@).dot \
-			|dot -T$(BR_GRAPH_OUT) -o $(O)/graphs/$$(@).$(BR_GRAPH_OUT)
+			|dot $(BR2_GRAPH_DOT_OPTS) -T$(BR_GRAPH_OUT) -o $(O)/graphs/$$(@).$(BR_GRAPH_OUT)
 
 $(1)-dirclean:		$$($(2)_TARGET_DIRCLEAN)
 

index 772982a..9817915 100644
@@ -94,6 +94,8 @@ to +make+ or set in the environment:
   default), or +png+.
 * +BR2_GRAPH_DEPS_OPTS+ to pass extra options to the dependency graph; see
   xref:graph-depends[] for the accepted options
+* +BR2_GRAPH_DOT_OPTS+ is passed verbatim as options to the +dot+ utility to
+  draw the dependency graph.
 
 An example that uses config files located in the toplevel directory and
 in your $HOME:

@@ -204,6 +206,9 @@ The +graph-depends+ behaviour can be controlled by setting options in the
 * +--depth N+, +-d N+, to limit the dependency depth to +N+ levels. The
   default, +0+, means no limit.
 
+* +--transitive+, +--no-transitive+, to draw (or not) the transitive
+  dependencies. The default is to draw transitive dependencies.
+
 --------------------------------
 BR2_GRAPH_DEPS_OPTS='-d 3' make graph-depends
 --------------------------------