#!/bin/sh -
#
#   Display the dependency graph (tree) of FreeBSD packages.
#   It uses the dependency information under /var/db/pkg.
#
#   Copyright (C) 2007-2010 Oliver Fromme <olli@fromme.com> <olli@secnetix.de>
#   All rights reserved.  Standard 2-clause BSD license and disclaimer apply,
#   please refer to the file /usr/share/examples/etc/bsd-style-copyright on
#   FreeBSD or ask the author for a copy.
#

"""":
if which python >/dev/null; then
	exec python "$0" "$@"
else
	echo "${0##*/}: Python not found. Please install Python." >&2
	exit 1
fi
"""

#
#   The shell script ends here.  From now on we are in Python.
#

__doc__ = "Display dependency graph of FreeBSD packages."

import os, sys, getopt, fnmatch
from os.path import basename, isfile, join

me = basename(sys.argv[0])

def stderr (msg):
	print >> sys.stderr, msg

def usage():
	stderr (
"""Usage:  %s [-Aav] [-i <pkg>] [-I <pkg>] [-t <pkg>] [<package> ...]
<package> must be the name of an installed package.  As a special shortcut, "*"
will expand to all "root" packages, i.e. packages not required by any other.
This is the default if no packages are specified.
Options:
    -A         Use ASCII characters instead of line drawing characters.
    -a         Show all dependencies, i.e. indirect and direct ones.
    -v         Verbose: Do not replace repeated dependencies with "...".
    -i <pkg>   Ignore <pkg>.
    -d <pkg>   Ignore the dependencies of <pkg>.
    -D <pkg>   Ignore <pkg> and its dependencies, same as -i <pkg> -d <pkg>.
    -t <pkg>   Trace the dependency <pkg> and ignore all unrelated packages.
You can use wildcards (*, ?, [...], [!...]) in package names (you should quote
them so the shell doesn't try to expand them) or specify package name prefixes.
WARNING:  Using -a and -v at the same time will produce HUGE output.""" % me)
	sys.exit (1)

def warn (msg):
	stderr ("%s: %s" % (me, msg))

def err (msg):
	warn (msg)
	sys.exit (1)

#
#   Read list of installed packages.
#

pkg_dbdir = os.environ.get("PKG_DBDIR", "/var/db/pkg")

try:
	allpkgs = set([f for f in os.listdir(pkg_dbdir) if "-" in f])
except OSError, (errno, errstr):
	err ("Can't read directory %s: %s" % (pkg_dbdir, errstr))

if not allpkgs:
	err ("No packages registered.")

def get_root_pkgs (all):
	root_pkgs = []
	for pkg in all:
		req_file = join(pkg_dbdir, pkg, "+REQUIRED_BY")
		if not isfile(req_file) or os.stat(req_file).st_size == 0:
			root_pkgs.append (pkg)
	return root_pkgs

def expand_pkgname (pattern):
	if pattern == "*":
		expanded = get_root_pkgs(allpkgs)
	else:
		expanded = fnmatch.filter(allpkgs, pattern)
	if not expanded:
		# Try prefix match.
		expanded = fnmatch.filter(allpkgs, pattern + "*")
	if not expanded:
		err ('No packages matching "%s" installed.' % pattern)
	return sorted(expanded)

def read_deps (p):
	"Return the list of dependencies for the given package <p>."

	fname = join(pkg_dbdir, p, "+CONTENTS")
	if not isfile(fname):
		warn ('Broken package database for dependency "%s"!' % p)
		return []
	else:
		return sorted([
			line.split()[1]
			for line in file(fname)
			if line.startswith("@pkgdep")
		])

def read_rqby (p):
	fname = join(pkg_dbdir, p, "+REQUIRED_BY")
	if isfile(fname):
		return [line.strip() for line in file(fname)]
	else:
		return []

#
#   Handle command line options.
#

show_all_deps = False
verbose = False
ACS_ok = sys.stdout.isatty()
ign_pkg = set()
trace_pkg = set()

try:
	opts, args = getopt.getopt(sys.argv[1:], "Aavi:d:D:t:")
except getopt.GetoptError:
	usage()

for opt, par in opts:
	if opt == "-A":
		ACS_ok = False
	elif opt == "-a":
		show_all_deps = True
	elif opt == "-v":
		verbose = True
	else:
		par = expand_pkgname(par)
		if opt == "-i":
			ign_pkg.update (par)
		elif opt == "-d":
			for p in par:
				ign_pkg.update (read_deps(p))
		elif opt == "-D":
			ign_pkg.update (par)
			for p in par:
				ign_pkg.update (read_deps(p))
		elif opt == "-t":
			trace_pkg.update (par)

if len(args) < 1:
	graph = expand_pkgname("*")
else:
	graph = []
	for p in args:
		graph.extend (expand_pkgname(p))

#
#   The following code enables using ACS line drawing characters.
#   The variable ACS_ok should be initialized before like this:
#       ACS_ok = sys.stdout.isatty()
#   If the terminal doesn't support ACS, the variable is changed
#   to False.  In this case you can still use the print_ACS()
#   function, but it will use simple ASCII approximations instead.
#

def ACS_assign (pairs):
	mapping = {}
	for key, val in zip(pairs[::2], pairs[1::2]):
		mapping[key] = val
	return mapping

if ACS_ok:
	import curses
	curses.setupterm()
	en_acs = curses.tigetstr("enacs")
	sm_acs = curses.tigetstr("smacs")
	rm_acs = curses.tigetstr("rmacs")
	acs_c  = curses.tigetstr("acsc") 

	if not (acs_c and sm_acs and rm_acs):
		ACS_ok = False
	else:
		if en_acs:
			curses.putp(en_acs)
		if acs_c and sm_acs and rm_acs:
			ACS = ACS_assign(acs_c)
			for i in "jklmnqtuvwx":
				if i not in ACS:
					ACS_ok = False
					break

if not ACS_ok:
	ACS = ACS_assign("j'k.l,m`n+q-t+u+v+w+x|")

def print_ACS (s):
	ACS_on = False
	for i in s:
		if "j" <= i <= "x":
			if ACS_ok and not ACS_on:
				curses.putp(sm_acs)
				ACS_on = True
			sys.stdout.write(ACS.get(i, ""))
		else:
			if ACS_ok and ACS_on:
				curses.putp(rm_acs)
				ACS_on = False
			sys.stdout.write(i)
	if ACS_ok and ACS_on:
		curses.putp(rm_acs)

#
#   End of support code for ACS line drawing characters.
#

deps_cache = {}

def get_deplist (p):
	deps = deps_cache.get(p, None)
	if deps is None:
		if p in allpkgs:
			deps = sorted([
				d for d in read_deps(p)
				if d not in ign_pkg or d in trace_pkg
			])
		else:
			warn ("Dependency %s is not installed!" % p)
			warn ("Inconsistent package database, please fix it!")
			deps = []
		deps_cache[p] = deps
	return deps

def trace_reduce (g):
	all_rq = set()
	for p in trace_pkg:
		all_rq.update (read_rqby(p))
	return [pkg for pkg in g if pkg in all_rq]

def work_depth_all (g):
	for i in range(len(g)):
		pkg = g[i]
		if type(pkg) != list:
			g[i] = [pkg, get_deplist(pkg)]
			work_depth_all (g[i][1])

def work_depth (g, top = False):
	child_deps = set()
	g_new = []
	for pkg in g:
		deps = get_deplist(pkg)
		child_deps.update (deps)
		g_new.append ([pkg, work_depth(deps)])
	if top:
		return g_new
	else:
		i = 0
		while i < len(g):
			if g[i] in child_deps:
				g.pop(i)
			else:
				i += 1
		return [pkg for pkg in g_new if pkg[0] not in child_deps]

def trace_packages (g):
	i = 0
	while i < len(g):
		if trace_packages(g[i][1]) or g[i][0] in trace_pkg:
			i += 1
		else:
			g.pop(i)
	return bool(g)

def display_indent (indent, mask, is_last):
	for i in range(indent - 1):
		if mask & 1 << i == 0:
			sys.stdout.write ("     ")
		else:
			print_ACS (" x   ")
	if is_last:
		print_ACS (" mqq ")
	else:
		print_ACS (" tqq ")

def display_dots (indent, mask):
	display_indent (indent, mask, True)
	sys.stdout.write ("...\n")

seen = set()

def display_graph (graph, indent = 0, mask = 0):
	if indent:
		mask |= 1 << (indent - 1)
	last = len(graph) - 1
	for i in range(len(graph)):
		pkg, deps = graph[i]
		if indent:
			display_indent (indent, mask, i == last)
		sys.stdout.write (pkg + "\n")
		num_deps = len(deps)
		if num_deps == 0:
			continue

		if i == last and indent:
			mask = mask ^ 1 << (indent - 1)

		if (num_deps > 1 or deps[0][1]) and not verbose:
			if pkg in seen :
				display_dots (indent + 1, mask)
				continue
			else:
				seen.add (pkg)
		display_graph (deps, indent + 1, mask)

if trace_pkg:
	graph = trace_reduce(graph)

if show_all_deps:
	work_depth_all (graph)
else:
	graph = work_depth(graph, top = True)

if trace_pkg:
	trace_packages (graph)

display_graph (graph)

#--