#! /usr/bin/env python

from itertools import *
import os, subprocess
from collections import defaultdict, deque

pj = os.path.join

def call_stdout(cmd):
    "returns stdout line by line"
    subp = subprocess.Popen(cmd, shell=True, stdin=None, stdout=subprocess.PIPE)
    return subp.communicate()[0].split('\n')

def l_part(n, c):
    return n.partition(c)[0]

def self_built():
    so = call_stdout('pacman -Qm')
    return [l_part(line, ' ') for line in so if line]

def reduce_by(fn, data, arg_list):
    data = fn(data, arg_list.pop(0))
    if not arg_list:
        return data
    return reduce_by(fn, data, arg_list)

def clean(n):
    return reduce_by(l_part, n.strip(), list('><:='))

def load_info(arch_file):
    info = defaultdict(list)
    mode = None
    for line in (clean(l) for l in arch_file):
        if not line:
            continue
        if line.startswith('%'):
            mode = line
            continue
        info[mode].append(line)
    arch_file.close()
    return info

def strip_info(info):
    keep = ['DEPENDS', 'BUILDDATE', 'INSTALLDATE', 'PROVIDES']
    info = dict((k.strip('%'),v) for k,v in info.items())
    name = info['NAME'][0]
    info = dict((k.lower(),v) for k,v in info.items() if k in keep)
    info['installdate'] = int(info['installdate'][0], 10)
    info['builddate'] = int(info['builddate'][0], 10)
    if 'depends' in info:
        info['depends'] = set(info['depends'])
    else:
        info['depends'] = set([])
    return name, info

def load_tree():
    path = '/var/lib/pacman/local/'
    packages = [p for p,d,f in os.walk(path) if f]
    tree = {}
    for p in set(packages) - set([path]):
        try:
            info = {}
            arch_file = open(pj(p,'depends'), 'r')
            info.update(load_info(arch_file))
            arch_file = open(pj(p,'desc'), 'r')
            info.update(load_info(arch_file))
            name, info = strip_info(info)
            tree[name] = info
        except:
            print 'Error reading package', p
    return tree

def provides(tree):
    todo = [k for k,v in tree.iteritems() if 'provides' in v]
    for pack in todo:
        for pro in tree[pack]['provides']:
            tree[pro] = tree[pack]
    return tree

def full_deps(package, tree):
    deps = set()
    to_crawl = set(tree[package]['depends'])
    while to_crawl:
        current = to_crawl.pop()
        if current in deps:
            continue
        deps.add(current)
        yield current
        current_deps = tree[current]['depends']
        to_crawl.update(current_deps - deps)
    #return list(deps)

def needs_rebuild(package, tree):
    deps = full_deps(package, tree)
    bdate = tree[package]['builddate']
    for d in full_deps(package, tree):
        idate = tree[d]['installdate']
        if idate >= bdate:
            return True
    return False

def main():
    tree = provides(load_tree())
    for package in self_built():
        if needs_rebuild(package, tree):
            print package


if __name__ == '__main__':
    main()