check-pkgs

#!/usr/bin/env python2.7
import sys, re, os, string, subprocess, pwd, fcntl, time, atexit, random

# Save package lists in ~/.pkgs/ where "~" refers to the home dir of the owner
# of this file
LIST_DIR = '%s/.pkgs/' % pwd.getpwuid(os.stat(__file__).st_uid).pw_dir

# Flag for printing out extra stuff
VERBOSE = False

# Regard recommended/suggested packages as dependencies
RECOMMENDS = False
SUGGESTS = False

def die (s = '', exit_code = 1):
    print >>sys.stderr, s
    sys.exit(exit_code)

def emph(s):
    return '\x1b[32m%s\x1b[m' % s

def yesno (s, default):
    optlist = emph('Y') + '/n' if default else 'y/' + emph('N')
    prompt = '%s [%s]: ' % (s, optlist)
    while True:
        opt = raw_input(prompt).lower()
        if opt == '':
            return default
        if opt in ('yes', 'y'):
            return True
        if opt in ('no', 'n'):
            return False
        print 'Please answer yes or no'

def optlist (opts, default, numbers = False):
    if isinstance(default, (int, long)):
        default = opts[default][0]

    abbrevs = [abbr for abbr, _ in opts]

    optlst = []
    abbrlen = max(map(len, abbrevs))
    numlen = len(str(len(opts) - 1))
    for i, (abbr, desc) in enumerate(opts):
        if numbers:
            lbl = '[%s:%s]' % (str(i).ljust(numlen), abbr)
            lbl = lbl.ljust(numlen + abbrlen + 3)
        else:
            lbl = '[%s]' % abbr
            lbl = lbl.ljust(abbrlen + 2)
        print '  %s %s' % (lbl, desc)
        optlst.append(emph(abbr) if abbr == default else abbr)

    prompt = '[%s] ' % '/'.join(optlst)

    while True:
        opt = raw_input(prompt)
        if len(opt) == 0:
            return default
        elif opt in abbrevs:
            return opt
        elif opt.isdigit():
            try:
                opt = abbrevs[int(opt)]
                if opt in abbrevs:
                    return opt
            except:
                pass
        print 'Please select one of ' + ', '.join(abbrevs)

def selectfromlist(opts):
    numlen = len(str(len(opts)))
    for i, opt in enumerate(opts, 1):
        lbl = '[%s]' % str(i).rjust(numlen)
        print '  %s %s' % (lbl, opt)

    prompt = 'Enter numbers or unique prefixes, separated by commas: '

    while True:
        sels = []
        for sel in (s.strip() for s in raw_input(prompt).split(',')):
            if sel.isdigit():
                sel = int(sel) - 1
                if sel < 0 or sel >= len(opts):
                    print 'Invalid number: %d' % sel
                    break
                sels.append(sel)
                continue
            ms = []
            for i, opt in enumerate(opts):
                if opt.startswith(sel):
                    ms.append(i)
            if len(ms) == 0:
                print 'Invalid prefix: %s' % sel
                break
            elif len(ms) > 1:
                print 'Prefix is not unique: %s' % sel
                break
            sels.append(ms[0])
        else:
            return sels

def plural (noun, amount):
    if hasattr(amount, '__len__'):
        amount = len(amount)
    return noun if amount == 1 else noun + 's'

def parse_version(ver):
    if ':' in ver:
        epoch, ver = ver.split(':', 1)
    else:
        epoch = 0

    if '-' in ver:
        upstream_version, debian_revision = ver.rsplit('-', 1)
    else:
        upstream_version, debian_revision = ver, ''

    return int(epoch), upstream_version, debian_revision

def order(c):
    if not c:
        return 0
    c = c[0]

    if c in string.digits:
        return 0
    elif c in string.letters:
        return ord(c)
    elif c == '~':
        return -1
    else:
        return 256 + ord(c)

def frag_compare(a, b):
    while a or b:
        while a and a[0] not in string.digits or b and b[0] not in string.digits:
            ac, a = order(a), a[1:]
            bc, b = order(b), b[1:]
            if ac != bc:
                return -1 if ac < bc else 1

        ac = bc = '0'

        while a and a[0] in string.digits:
            ac, a = ac + a[0], a[1:]
        while b and b[0] in string.digits:
            bc, b = bc + b[0], b[1:]

        ac = int(ac)
        bc = int(bc)

        if ac != bc:
            return -1 if ac < bc else 1
    return 0

def version_compare(ver1, ver2):
    epoch1, up1, deb1 = parse_version(ver1)
    epoch2, up2, deb2 = parse_version(ver2)

    if epoch1 != epoch2:
        return -1 if epoch1 < epoch2 else 1

    c = frag_compare(up1, up2)
    if c != 0:
        return c

    return frag_compare(deb1, deb2)

def version_compatible(ver1, op, ver2):
    cmps = {
        '>=': (False, True,  True ),
        '=' : (False, True,  False),
        '>>': (False, False, True ),
        '<<': (True,  False, False),
        '<=': (True,  True,  False)
    }

    return cmps[op][version_compare(ver1, ver2)+1]

def qualified_name(pkg):
    return pkg.setdefault('__qname',
                          '%s:%s' % (pkg['Package'], pkg['Architecture']))

# Packages are are just dictionaries build from dpkg's status file, but we add
# the `__hash__` function to make much of the code simpler.
class Package(dict):
    def __hash__(self):
        return self.setdefault('__hash', qualified_name(self).__hash__())
    def __str__(self):
        return qualified_name(self)
    def __repr__(self):
        return str(self)

def parse_dpkg ():
    fd = open('/var/lib/dpkg/status')
    pkgs = []
    pkg = Package()
    must_fix = []

    rawdata = ''
    for line in fd:
        rawdata += line
        line = line.rstrip('\n')
        if not line:
            # assert that the package is sane
            # info:
            #   http://www.fifi.org/doc/libapt-pkg-doc/dpkg-tech.html/ch1.html
            #   http://manpages.ubuntu.com/manpages/wily/man1/dpkg.1.html
            want, flag, status = pkg['Status'].split()
            if any([flag != 'ok',
                    want not in ('install', 'deinstall', 'hold'),
                    status not in ('installed', 'config-files'),
                   ]):
                must_fix.append(pkg)

            pkg['__raw'] = rawdata
            # XXX: Hack let a package `Provide:` different versions
            pkg['Version'] = [pkg['Version']]
            pkgs.append(pkg)
            rawdata = ''
            pkg = Package()
            continue

        if line[0] == ' ':
            val += '\n' + line
        else:
            key, val = line.split(':', 1)
            val = val.lstrip(' ')

        pkg[key] = val

    if must_fix:
        longest_name = max(len(qualified_name(pkg)) for pkg in must_fix)
        longest_name = max(len('Package:'), longest_name)
        fmt = '  %%-%ds  %%s' % longest_name
        print 'I do not understand the status of these packages:'
        print fmt % ('Package:', 'Status:')
        for pkg in must_fix:
            print fmt % (qualified_name(pkg), pkg['Status'])
        print 'You must resolve these issues'
        sys.exit(1)

    # A package's qualified name should uniquely identify it; check that
    assert len(set(map(qualified_name, pkgs))) == len(pkgs)

    return pkgs

def find_should_purge (pkgs):
    should_purge = []
    def abort(pkg):
        raise Exception('Unexpected package status (%s: %s)' % \
                        (qualified_name(pkg), pkg['Status']))

    for pkg in pkgs:
        # info: http://www.fifi.org/doc/libapt-pkg-doc/dpkg-tech.html/ch1.html
        want, flag, status = pkg['Status'].split()
        if flag != 'ok':
            abort(pkg)
        else:
            if want == 'install' and status == 'installed':
                continue
            if want == 'deinstall' and status == 'config-files':
                should_purge.append(pkg)
            else:
                abort(pkg)
    return should_purge

def is_installed (pkg):
    return pkg['Status'] == 'install ok installed'

def build_name_map (packages):
    name_map = {}
    ver_regex = re.compile(r'^(\S+) \(= (\S+)\)$')

    def add (name, cur):
        name_map.setdefault(name, []).append(cur)

    for pkg in packages:
        add(pkg['Package'], pkg)
        if 'Provides' in pkg:
            for alt_name in pkg['Provides'].split(', '):
                # XXX: Strip version info -- we should probably use it for
                #      something tho'...
                m = ver_regex.match(alt_name)
                if m:
                    alt_name, alt_ver = m.groups()
                    pkg['Version'].append(alt_ver)
                add(alt_name, pkg)

    return name_map

def build_dependency_map (pkgs, name_map):
    dependency_map = []
    ver_regex = re.compile(r'^(\S+) \((\S+) (\S+)\)$')

    def find_satisfies (arch, name):
        m = ver_regex.match(name)
        if not m:
            assert ' ' not in name
            ver_cmp = lambda v: True
        else:
            name, ver_op, ver_num = m.group(1), m.group(2), m.group(3)
            ver_cmp = lambda v: version_compatible(v, ver_op, ver_num)

        do_any = False
        if name.endswith(':any'):
            do_any = True
            name = name[:-4]
        elif ':' in name:
            name, arch = name.split(':', 1)

        result = []

        for candidate in name_map.get(name, []):
            if candidate['Architecture'] == arch or \
               candidate['Architecture'] == 'all' or \
               arch == 'all' or \
               candidate.get('Multi-Arch', 'no') == 'foreign' or \
               candidate.get('Multi-Arch', 'no') == 'allowed' and do_any:
                for ver in candidate['Version']:
                    if ver_cmp(ver):
                        result.append(candidate)
                        break

        return result

    def add_dependencies(pkg, depends, soft=False):
        depends = depends.strip()
        if not depends:
            return

        for depend in depends.split(', '):
            dependencies = []
            for dep_name in depend.split(' | '):
                dependencies.extend(find_satisfies(pkg['Architecture'], dep_name))
            if not soft:
                assert len(dependencies) >= 1
            dependency_map.append((pkg, set(dependencies)))

    for pkg in pkgs:
        for n in ['Depends', 'Pre-Depends']:
            add_dependencies(pkg, pkg.get(n, ''))
        if RECOMMENDS:
            add_dependencies(pkg, pkg.get('Recommends', ''), soft=True)
        if SUGGESTS:
            add_dependencies(pkg, pkg.get('Suggests', ''), soft=True)

    return dependency_map

allowed_chars = set(string.letters + string.digits + '-*+.:')
def convert_to_regex(line, python = True):
    assert allowed_chars.issuperset(line)
    line = line.replace('+', '\\+')
    line = line.replace('*', '.*')
    if python:
        if ':' not in line:
            line += ':.*'
        return '(?:' + line + ')'
    else:
        return '^' + line + '$'

def do_system (cmd):
    ret = os.system(cmd)
    if ret != 0:
        sys.exit(ret)

def sudo(cmd):
    if os.geteuid() != 0:
        cmd = 'sudo ' + cmd
    do_system(cmd)

def name_list (pkgs):
    return ' '.join(pkg if isinstance(pkg, str) else qualified_name(pkg) \
                    for pkg in pkgs)

def do_purge (*pkgs, **kwargs):
    yes = kwargs.get('yes', False)
    sudo('apt-get purge %s %s' % (name_list(pkgs), '--yes' if yes else ''))

def do_install (*pkgs):
    sudo('apt-get install --no-install-recommends %s' % name_list(pkgs))

def read_list (lst):
    filename = '%s/%s.pkgs' % (LIST_DIR, lst)
    if not os.path.exists(filename):
        return []
    out = []
    with open(filename) as fd:
        linum = 1
        for orig_line in fd:
            if not orig_line.endswith('\n'):
                if not orig_line and linum == 1:
                    return []
                orig_line = orig_line + '\n'
            line = orig_line.strip()
            if '#' in line:
                line = line.split('#')[0].strip()
            if not allowed_chars.issuperset(line):
                die('Malformed package name (%s:%d):\n  "%s"' % \
                    (filename,
                     linum,
                     line))
            if line == '':
                line = None
            out.append((line, orig_line))
            linum += 1
    return out

def show_list (lst):
    out = []
    for line, _ in read_list(lst):
        if line:
            out.append(line)
    return '\n'.join(sorted(out))

def write_list (lst, lines):
    filename = '%s/%s.pkgs' % (LIST_DIR, lst)
    with open(filename, 'w') as fd:
        for _, orig_line in lines:
            fd.write(orig_line)

def read_remind_list():
    lst = read_list('remind')
    out = []
    for i in range(0, len(lst), 2):
        _line, comment = lst[i]
        here = 'on line %d in remind.pkgs' % i
        if _line != None:
            print 'Expected a comment', here
            out = []
            break
        try:
            remind_at = re.findall(
                r'# Remind at (\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2})',
                comment)[0]
        except:
            print 'Malformed comment', here
            out = []
            break
        try:
            remind_at = time.mktime(time.strptime(remind_at,
                                                  '%Y-%m-%d %H:%M:%S'))
        except:
            print 'Invalid data', here
            out = []
            break

        pkg, _line = lst[i + 1]
        here = 'on line %d in remind.pkgs' % (i + 1)
        if not pkg:
            print 'Expected a package name', here
            out = []
            break

        if time.time() > remind_at:
            continue

        out += lst[i : i + 2]

    if out != lst:
        write_list('remind', out)
    return out

def add_reminder(pkg, lines):
    remind_at = time.gmtime(time.time() + 60 * 60 * 24 * 5)
    remind_at = time.strftime('%Y-%m-%d %H:%M:%S', remind_at)
    line = '# Remind at %s\n' % remind_at
    lines.append((None, line))
    lines.append((pkg, pkg + '\n'))

def pkgs_on_list (lines):
    return [pkg for pkg, _ in lines if pkg]

def del_from_list (pkg, lines):
    for i in range(len(lines)):
        line, _ = lines[i]
        if line == pkg:
            lines.pop(i)
            return

def add_to_list (pkg, lines):
    lines.append((pkg, pkg + '\n'))

def get_installed():
    # Get the packages
    pkgs = parse_dpkg()

    # We only care about installed files
    i = 0
    while i < len(pkgs):
        pkg = pkgs[i]
        if not is_installed(pkg):
            pkgs.pop(i)
        else:
            i += 1

    # Get list of all installed packages
    installed = set()
    for pkg in pkgs:
        installed.add(pkg['Package'])
        installed.add(qualified_name(pkg))

    return installed

def step_deinstall ():
    # Get the installed packages
    pkgs = parse_dpkg()

    # If we have de-installed packages, fix that first
    should_purge = find_should_purge(pkgs)
    if should_purge and \
       yesno('You have %d un-purged %s;  Purge now?' % \
             (len(should_purge), plural('package', should_purge)),
             True):
        do_purge(*should_purge)

def step_dowant ():
    # Handle wanted but not installed packages
    dowant_list = read_list('dowant')

    def get_to_install():
        installed = get_installed()
        to_install = []
        for pkg in pkgs_on_list(dowant_list):
            if '*' in pkg:
                die('Wildcards not allowed in dowant.pkgs')
            if pkg not in installed:
                to_install.append(pkg)
        return to_install

    to_install = get_to_install()
    if to_install:
        print 'You have %d un-installed but wanted %s;  What do?' % \
            (len(to_install), plural('package', to_install))
        while True:
            opt = optlist([('i', 'Install all wanted packages'),
                           ('a', 'Ask me about each package individually'),
                           ('c', 'Continue without installing anything'),
                           ('r', 'Remove all from wanted packages'),
                           ('l', 'List packages'),
                          ], 'i')
            if   opt == 'i':
                do_install(*to_install)
                break
            elif opt == 'c':
                break
            elif opt == 'a':
                while to_install:
                    pkg = to_install.pop(0)
                    print 'Package: %s' % pkg
                    opt = optlist([('i', 'Install'),
                                   ('n', 'Do nothing'),
                                   ('r', 'Remove from wanted packages'),
                                  ], 'i')
                    if   opt == 'i':
                        do_install(pkg)
                        # Other packages might be pulled in as dependencies
                        to_install = get_to_install()
                    elif opt == 'n':
                        pass
                    elif opt == 'r':
                        del_from_list(pkg, dowant_list)
                        write_list('dowant', dowant_list)
                break
            elif opt == 'r':
                for pkg in to_install:
                    del_from_list(pkg, dowant_list)
                    write_list('dowant', dowant_list)
                break
            elif opt == 'l':
                print 'Wanted but not installed:'
                for pkg in to_install:
                    print '  %s' % pkg
                print 'What do?'

def step_delete ():
    # Handle unwanted but installed packages
    delete_list = read_list('delete')

    def get_to_delete():
        installed = get_installed()
        to_delete = []
        for pkg in pkgs_on_list(delete_list):
            if '*' in pkg:
                die('Wildcards not allowed in delete.pkgs')
            if pkg in installed:
                to_delete.append(pkg)
        return to_delete

    to_delete = get_to_delete()
    if to_delete:
        print 'You have %d installed but unwanted %s;  What do?' % \
            (len(to_delete), plural('package', to_delete))
        while True:
            opt = optlist([('d', 'Delete all unwanted packages'),
                           ('a', 'Ask me about each package individually'),
                           ('c', 'Continue without deleting anything'),
                           ('l', 'List packages'),
                          ], 'd')
            if   opt == 'd':
                do_purge(*to_delete)
                break
            elif opt == 'c':
                break
            elif opt == 'a':
                while to_delete:
                    pkg = to_delete.pop(0)
                    print 'Package: %s' % pkg
                    opt = optlist([('d', 'Delete'),
                                   ('n', 'Do nothing'),
                                   ('r', 'Remove from unwanted packages'),
                                  ], 'd')
                    if   opt == 'd':
                        do_purge(pkg)
                        # Other packages might be purged as well
                        to_delete = get_to_delete()
                    elif opt == 'n':
                        pass
                    elif opt == 'r':
                        del_from_list(pkg, delete_list)
                        write_list('delete', delete_list)
                break
            elif opt == 'l':
                print 'Unwanted but installed:'
                for pkg in to_delete:
                    print '  %s' % pkg
                print 'What do?'

def get_ok_matcher():
    '''Return a function which will return the list on which a qualified name
    appears or `None` if it is not on any list.
    '''

    def build_regex(lst):
        pkgs = map(convert_to_regex, pkgs_on_list(lst))
        return re.compile('^%s$' % '|'.join(pkgs))

    dowant = build_regex(read_list('dowant'))
    ignore = build_regex(read_list('ignore'))
    remind = build_regex(read_remind_list())
    lists = (('dowant', dowant),
             ('ignore', ignore),
             ('remind', remind),
             )

    def matcher(pkg):
        for name, regex in lists:
            if regex.match(qualified_name(pkg)):
                return name

    return matcher

def get_pkg_graph():
    # See `get_orphaned` below for details

    # Get the packages
    pkgs = parse_dpkg()

    # We only care about installed files
    pkgs = filter(is_installed, pkgs)

    # The installed packages all have a qualified name
    # e.g. "python-scipy:amd64". However other packages will only refer to
    # the package as either "python-scipy" or "python-scipy:any". They might
    # also refer to the packages by their virtual names such as
    # "python-numpy-abi9" instead of "python-numpy". So we build a
    # many-to-many relation mapping names to packages.
    name_map = build_name_map(pkgs)

    # From this many-to-many relation we build the dependency graph.  For
    # instance we might have that pkg0 would have a dependency of the format
    # (pkg1 | pkg2 | pkg3), (pkg4 | pkg5).  In this example, we might return
    #
    #   [(pkg0:i386, [pkg1-gtk:i386, pkg1-curses:i386, pkg3:all]),
    #    (pkg0, [pkg4:i386])]
    #
    # Where the first element of the tuple is a string and the elements of
    # the lists are dictionaries
    deps_map = build_dependency_map(pkgs, name_map)

    # Turn the dependcy map into a graph.
    for pkg in pkgs:
        pkg['__children'] = set()
        pkg['__parents'] = set()
    for a, bs in deps_map:
        # Ignore alternatives
        if len(bs) != 1:
            continue
        b = list(bs)[0]
        a['__children'].add(b)
        b['__parents'].add(a)

    return pkgs

def get_orphaned ():
    """Consider the directed graph where the nodes are all the installed
    packages on the system and the vertices are all package dependencies.

    We say that a package A dominates another package B, whenever there is a
    path in this graph from A to B, but no path from B to A (i.e. if A somehow
    depends on B, but B does not depend on A).

    NOTE: We will ignore dependencies of the form A=>B|C, where both B and C are
    installed. This can in principle lead to both false-positives and
    false-negatives, but only in cases where the package maintainers have done
    some very sketchy stuff.

    This function calculates the least set of nodes, such that every installed
    package is either in the set or is dominated by a node in the set.

    It calculates it by the following algorithm:

    1) Pick an arbitrary node N. If the graph is empty, you are done.
    2) Split the graph into 4 parts:
       - The set of ancestors,   i.e. any node A with a path A=>N.
       - The set of siblings,    i.e. any node A with a path A=>N and N=>A.
       - The set of descendants, i.e. any node A with a path N=>A.
       - The set of unrelated nodes, i.e. those without a path to N.
    3) If the set of ancestors is empty, then the set of siblings must
       be part of the solution, since no other nodes dominates them.
       If it is non-empty, then the set of siblings cannot be part of the
       solution.
    4) In either case we remove the set of siblings and descendants
       from the graph, and continue from step 1.

    After calculating this set, we remove the all sibling-sets where at least
    one of the nodes in the set have been marked as wanted by the user.

    The orphaned set, is exactly the set of dominant nodes with the
    wanted-by-user nodes and their dependencies removed.

    """

    pkgs = get_pkg_graph()

    # Function for remove a node along with all its descendants.
    def remove_descendants(node):
        if '__removed' not in node:
            node['__removed'] = True
            for child in node['__children']:
                remove_descendants(child)

    # Function for finding a node along with all its ancestors.
    def find_ancestors(node):
        todo = {node}
        seen = set()
        while todo:
            pkg = todo.pop()
            if pkg in seen:
                continue
            seen.add(pkg)
            todo.update(pkg['__parents'])
        return seen

    # Now calculate set the of dominant nodes.
    dominant_sets = []
    todo = list(pkgs)
    random.shuffle(todo)
    next_node = None
    while todo:
        cur = todo.pop()
        if '__removed' in cur:
            continue
        ancestors = find_ancestors(cur)
        remove_descendants(cur)
        if all('__removed' in node for node in ancestors):
            dominant_sets.append(ancestors)

    # Build regex for kosher packages
    match = get_ok_matcher()

    # Remove every node on a wanted list
    orphaned = []
    for curcycle in dominant_sets:
        wanted = []
        for pkg in curcycle:
            pkg['__dominant'] = True
            if match(pkg):
                wanted.append(pkg)
        if len(wanted) == 0:
            orphaned += curcycle
        elif VERBOSE and len(wanted) > 1:
            print "Cyclic chain of wanted packages:",
            for pkg in wanted:
                print qualified_name(pkg),
            print

    if VERBOSE:
        for pkg in pkgs:
            lst = match(pkg)
            if '__dominant' not in pkg and lst:
                print "Non-dominant package '%s' in %s.pkgs" % \
                    (qualified_name(pkg), lst)

    return orphaned

def why(pkg):
    pkgs = get_pkg_graph()

    if ':' in pkg:
        name, arch = pkg.split(':', 1)
    else:
        name, arch = pkg, None

    for pkg in pkgs:
        if pkg['Package'] == name and arch in (None, pkg['Architecture']):
            break
    else:
        die('Package is not installed')

    match = get_ok_matcher()

    # We now do a DFS and mark each package with it's predecessor so we can
    # print the dependency path
    pkg['__prev'] = None

    frontier = {pkg}
    edge = set()
    while frontier:
        pkg = frontier.pop()

        if match(pkg):
            edge.add(pkg)

        for parent in pkg['__parents']:
            # Add this package to the frontier if we haven't seen it already
            if '__prev' not in parent:
                parent['__prev'] = pkg
                frontier.add(parent)

    if not edge:
        die('Package is orphaned')

    paths = []
    for pkg in edge:
        path = []
        while pkg:
            path.append(pkg)
            pkg = pkg['__prev']
        paths.append(path)

    if len(paths) > 1 and not VERBOSE:
        print 'There are %d dependencies for this package.  '\
            'Use --verbose to show them all.' % len(paths)
        paths = [paths[0]]

    for path in paths:
        lst = emph('%s%s.pkgs' % (LIST_DIR, match(path[0])))
        path = [qualified_name(pkg) for pkg in path]
        print '%s: %s' % (lst, emph(' -> ').join(path))

    # print len(paths)
    # print len(set(p[0] for p in paths))

def step_decide ():
    dowant_list = read_list('dowant')
    ignore_list = read_list('ignore')
    remind_list = read_remind_list()
    delete_list = read_list('delete')

    pkgs = get_orphaned()

    if len(pkgs) > 1:
        print 'You have %d orphaned %s' % \
            (len(pkgs), plural('package', pkgs))

    while pkgs:
        pkg = pkgs[0]
        print 'Package %s is installed;  Why?' % qualified_name(pkg)
        opt = optlist([('w', 'I want this package'),
                       ('i', 'Ignore this package'),
                       ('c', 'Continue without adding this package to any list'),
                       ('?', 'Show APT\'s information about this package'),
                       ('f', 'List files installed by this package'),
                       ('l', 'List orphaned packages'),
                       ('r', 'Remind me of this package later'),
                       ('R', 'I said later!  Remind me of everything later'),
                       ('s', 'Select which packages to remind me of later'),
                       ('d', 'Good question; delete this package'),
                       ('D', 'Delete every orphaned package!'),
                       ('u', 'Delete this package and mark is as un-wanted'),
                       ('U', 'Delete and mark every orphaned package as un-wanted'),
                       ('q', 'I can\'t deal with this right now; quit!'),
                      ], 'r')
        if   opt == 'w':
            add_to_list(qualified_name(pkg), dowant_list)
            write_list('dowant', dowant_list)
        elif opt == 'i':
            add_to_list(qualified_name(pkg), ignore_list)
            write_list('ignore', ignore_list)
        elif opt == 'c':
            pass
        elif opt == '?':
            print pkg['__raw']
            continue
        elif opt == 'f':
            output = subprocess.check_output(['dpkg',
                                              '-L',
                                              qualified_name(pkg)])
            sys.stdout.write(output)
            continue
        elif opt == 'l':
            print '\n'.join(sorted(map(qualified_name, pkgs)))
            continue
        elif opt == 'r':
            add_reminder(qualified_name(pkg), remind_list)
            write_list('remind', remind_list)
        elif opt == 'R':
            for pkg in pkgs:
                add_reminder(qualified_name(pkg), remind_list)
            write_list('remind', remind_list)
            break
        elif opt == 's':
            sels = selectfromlist(map(qualified_name, pkgs))
            for i in sels:
                add_reminder(qualified_name(pkgs[i]), remind_list)
            write_list('remind', remind_list)
            pkgs = [pkg for i, pkg in enumerate(pkgs) if i not in sels]
            continue
        elif opt in ('d', 'u'):
            do_purge(pkg)
            if opt == 'u':
                add_to_list(qualified_name(pkg), delete_list)
                write_list('delete', delete_list)
            # re-parse
            pkgs = get_orphaned()
            continue
        elif opt in ('D', 'U'):
            if not yesno('Are you sure about this?  I will delete recursively' \
                         ', you know.', True):
                continue
            yes = yesno('Pass --yes flag to APT?', False)
            while pkgs:
                do_purge(*pkgs, yes = yes)
                for pkg in pkgs:
                    if opt == 'U':
                        add_to_list(qualified_name(pkg), delete_list)
                # re-parse
                pkgs = get_orphaned()
            if opt == 'U':
                write_list('delete', delete_list)
            break
        elif opt == 'q':
            break
        pkgs.pop(0)

def usage ():
    print 'usage: %s [--verbose] [--list orphaned|dowant|ignore|remind|delete]' % \
        os.path.basename(sys.argv[0])
    print
    print 'Pro tip:'
    print '  $ echo \'DPkg::Post-Invoke {"PATH/TO/THIS/SCRIPT";};\' > ' \
          '/etc/apt/apt.conf.d/99check-pkgs'
    sys.exit(1)

def main ():
    global VERBOSE
    # If this script is called as a post-invoke hook from APT and then itself
    # calls apt-get we run into trouble: apt-get releases the
    # "/var/cache/apt/archives/lock" lock file *after* the post-invoke hooks
    # have run.  This means that the this script's call to apt-get will fail.
    # Fix: we delete the lock file.
    try:
        os.unlink('/var/cache/apt/archives/lock')
    except OSError:
        pass

    if 'CHECK_PKGS_DONT_RUN' in os.environ:
        sys.exit(0)

    # Drop privs to owner of this file
    st = os.stat(__file__)
    uid = st.st_uid
    if os.getuid() != uid:
        os.setegid(st.st_gid)
        os.seteuid(uid)

    # Claim PID file
    pid_path = '/tmp/check-pkgs.pid'
    pidfile = open(pid_path, 'a+')
    try:
        fcntl.flock(pidfile.fileno(), fcntl.LOCK_EX | fcntl.LOCK_NB)
    except IOError:
        sys.exit(0)

    def clean(*_):
        try:
            os.unlink(pid_path)
        except:
            pass
    atexit.register(clean)

    pidfile.seek(0)
    pidfile.truncate()
    pidfile.write(str(os.getpid()))
    pidfile.flush()
    pidfile.seek(0)

    # And go!

    # Handle optional arguments
    optargs = ('verbose', 'recommends', 'suggests')
    for optarg in optargs:
        flag = '--' + optarg
        while flag in sys.argv:
            globals()[optarg.upper()] = True
            sys.argv.remove(flag)

    if not os.path.exists(LIST_DIR):
        print 'Creating directory: %s' % LIST_DIR
        os.mkdir(LIST_DIR)

    # No command, so just do our thing
    if len(sys.argv) == 1:
        step_deinstall()
        step_dowant()
        step_delete()
        step_decide()
        return

    # Usage message
    if len(sys.argv) == 2 and sys.argv[1] in ('-h', '--help', 'help'):
        usage()

    # Accept prefix of a command
    prefix = sys.argv[1]
    # Command names and arg counts
    commands = (('remind', 0),
                ('edit'  , 1),
                ('list'  , 1),
                ('why'   , 1),
                )
    cmd = [c for c in commands if c[0].startswith(prefix)]

    if len(cmd) == 0:
        die('Unknown command: %s' % prefix)

    # This cannot happen at the moment, but just like squirrels I like to
    # prepare for the future
    if len(cmd) > 1:
        die('Ambiguous command: %s (could be %s)' % \
            (prefix, ', '.join(c[0] for c in cmd)))

    cmd, argc = cmd[0]
    argv = sys.argv[2:]

    if argc != len(argv):
        die(''.join(('Expected ',
                     'no' if argc == 0 else str(argc),
                     ' argument',
                     '' if argc == 1 else 's',
                     ' but got %d' % len(argv),
                     )
                    ))

    if   cmd == 'remind':
        path = '%sremind.pkgs' % LIST_DIR
        if os.path.isfile(path):
            os.unlink(path)
        # Remove arg, release PID file and go run again
        sys.argv.pop()
        pidfile.close()
        main()

    elif cmd == 'edit':
        editor = os.getenv('EDITOR', 'editor')
        os.system('%s %s/%s.pkgs' % (editor, LIST_DIR, argv[0]))

    elif cmd == 'list':
        if   argv[0] == 'orphaned':
            print '\n'.join(qualified_name(pkg) for pkg in get_orphaned())
        elif argv[0] in ('dowant', 'ignore', 'remind', 'delete'):
            print show_list(sys.argv[2])
        else:
            lists = ('orphaned', 'dowant', 'ignore', 'remind', 'delete')
            die('Invalid argument.  Valid is: %s.' % ', '.join(lists))

    elif cmd == 'why':
        why(argv[0])

if __name__ == '__main__':
    try:
        main()
    except KeyboardInterrupt:
        print
    except EOFError:
        print '^D'