#!/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
  
  # 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")
  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
  ")
          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
  
  # 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'
  " % args.colours)
      sys.exit(1)
  root_colour = colours[0]
  target_colour = colours[1]
  host_colour = colours[2]
  
  allpkgs = []
  
  # Execute the "make <pkg>-show-version" command to get the version of a given
  # list of packages, and return the version formatted as a Python dictionary.
  def get_version(pkgs):
      sys.stderr.write("Getting version for %s
  " % pkgs)
      cmd = ["make", "-s", "--no-print-directory" ]
      for pkg in pkgs:
          cmd.append("%s-show-version" % pkg)
      p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
      output = p.communicate()[0]
      if p.returncode != 0:
          sys.stderr.write("Error getting version %s
  " % pkgs)
          sys.exit(1)
      output = output.split("
  ")
      if len(output) != len(pkgs) + 1:
          sys.stderr.write("Error getting version
  ")
          sys.exit(1)
      version = {}
      for i in range(0, len(pkgs)):
          pkg = pkgs[i]
          version[pkg] = output[i]
      return version
  
  # 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
  ")
      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(' ')
  
  # Execute the "make <pkg>-show-depends" command to get the list of
  # dependencies of a given list of packages, and return the list of
  # dependencies formatted as a Python dictionary.
  def get_depends(pkgs):
      sys.stderr.write("Getting dependencies for %s
  " % pkgs)
      cmd = ["make", "-s", "--no-print-directory" ]
      for pkg in pkgs:
          cmd.append("%s-show-depends" % pkg)
      p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
      output = p.communicate()[0]
      if p.returncode != 0:
          sys.stderr.write("Error getting dependencies %s
  " % pkgs)
          sys.exit(1)
      output = output.split("
  ")
      if len(output) != len(pkgs) + 1:
          sys.stderr.write("Error getting dependencies
  ")
          sys.exit(1)
      deps = {}
      for i in range(0, len(pkgs)):
          pkg = pkgs[i]
          pkg_deps = output[i].split(" ")
          if pkg_deps == ['']:
              deps[pkg] = []
          else:
              deps[pkg] = pkg_deps
      return deps
  
  # 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(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("
  Recursion detected for  : %s
  " % (p))
                  while True:
                      _p = chain.pop()
                      sys.stderr.write("which is a dependency of: %s
  " % (_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 = 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>>]
  " % (name, label))
      else:
          outfile.write("%s [label = \"%s\"]
  " % (name, label))
      outfile.write("%s [color=%s,style=filled]
  " % (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
  " % (pkg_node_name(pkg), pkg_node_name(d)))
                  print_pkg_deps(depth+1, d)
  
  # Start printing the graph data
  outfile.write("digraph G {
  ")
  
  done_deps = []
  print_pkg_deps(0, rootpkg)
  
  outfile.write("}
  ")