gistfile1.py

__author__ = 'Nicolas Trangez' # :-P

class Package(object):
    '''Basic package representation'''
    __slots__ = 'name', 'dependencies',

    def __init__(self, name, dependencies=None):
        '''Initialize a new package

        :param name: package name
        :type name: str
        :param dependencies: package dependency definitions
        :type dependencies: iterable<Package>
        '''
        dependencies = tuple(dependencies) if dependencies else tuple()
        self.name = name
        self.dependencies = dependencies

    def __str__(self):
        return '<Package \'%s\'>' % self.name

    __repr__ = __str__


class CircularDependencyDetected(Exception):
    '''Exception raised when circular dependencies are detected'''
    def __init__(self, pkg, dep):
        Exception.__init__(self, 'Found circular dependency on %s in %s' % \
                           (dep.name, pkg.name))


def resolve_deps_helper(pkg, seen):
    '''Helper method for resolve_deps

    :param pkg: top package to resolve
    :type pkg: Package
    :param seen: stack of packages seen before
    :type seen: list
    '''
    for dep in pkg.dependencies:
        if dep in seen:
            raise CircularDependencyDetected(pkg, dep)

        yield dep
        # Prepend to list (so it's a forward-growing stack, which is more efficient)
        for child_dep in resolve_deps_helper(dep, [dep] + seen):
            yield child_dep

def resolve_deps(top):
    '''Resolve all dependencies and their installation order of a given package'''
    deps = set()
    # Call the helper with an empty stack of seen deps
    for pkg in reversed(list(resolve_deps_helper(top, list()))):
        if pkg in deps:
            continue

        yield pkg
        # We need uniqueness while traversing right-to-left
        deps.add(pkg)


# Poor-man unittest :-P
def test(name, top):
    print 'Testing', name
    try:
        # Note: we got to apply list() here, since otherwise the
        # CircularDependencyDetected exception would be thrown while iterating
        # over the result in the print call later on
        order = list(resolve_deps(top))
    except CircularDependencyDetected, err:
        print 'Circular dependency detected:', err
        print
        return

    print 'Installation order: %s' % (' '.join(dep.name for dep in order))
    print

# Basic test
C = Package('C')
B = Package('B', (C, ))
D = Package('D', (C, ))
A = Package('A', (B, D, ))

TOP1 = Package('*', (A, B, C, D, ))
test('basic tree', TOP1)

# Introduce a loop
I = Package('I')
J = Package('J', (I, ))
K = Package('K', (J, ))
I.dependencies = (K, )

TOP2 = Package('*', (A, B, C, D, I, J, K))
test('circular dependency', TOP2)


# Same thing using Carl's structure of packages
QBASE = Package('QBase')

PHP = Package('php', (QBASE, ))
MODPHP = Package('mod_php', (PHP, QBASE, ))

JAVA = Package('java', (QBASE, ))
MODJK = Package('mod_jk', (QBASE, JAVA, ))

APACHE = Package('Apache', (QBASE, MODPHP, MODJK, ))

TOP3 = Package('*', (QBASE, PHP, MODPHP, JAVA, MODJK, APACHE, ))
test('Carl setup', TOP3)