reduce_dependencies.py

#!/usr/bin/env python

"""Reduces dependency constraints to a minimal set. 

Example: if a package is required in version '>2.2 >3.0 <=4.1', then >2.2 is
redundant in here -- it's entailed in >3.0 Likewise, in '>=4.2 !=4.2' should
just be '>4.2' etc.

This script reads in version constrains such as '>2.2 >3.0 <=4.1' and prints
a reduced list of constraints or unsatisfa if the constraints can't be
satisfied.

Use 'python solution.py test' to run a number of test cases.

Original challenge by @wickman
"""

__author__  = "Manuel Ebert"
__email__   = "[email protected]"
__twitter__ = "@maebert"
__version__ = "3.141729"

import sys


def reduce(conditions):
    """Reduces a list of conditions. Returns None if conditions are conflicting.
    Strategy: for each pair of conditions, try to find a better condition using
    condition.reduce(other_condition). If such a condition is found, remove the
    two original conditions from the set of conditions and add the other one
    instead. Rinse and repeat until nothing moves anymore.
    """
    def _reduce_iteration(conditions):
        tmp_result = set(conditions)
        for c1 in conditions:
            for c2 in conditions:
                if c1.conflicts(c2):
                    return None
                better = c1.reduce(c2)
                if better and c1 != c2:
                    tmp_result.difference_update([c1, c2])
                    tmp_result.add(better)
        return tmp_result
    this_iteration = set(conditions)
    last_iteration = []

    while this_iteration != last_iteration:
        this_iteration, last_iteration = _reduce_iteration(this_iteration), this_iteration
        if this_iteration is None:
            return None
    return this_iteration


def parse_solve_and_format(conditions_str, conflict_return="unsatisfiable"):
    """Parses a string of conditions, reduces it properly and Returns
    the solution as a string"""
    conds = map(Condition, conditions_str.split(" "))
    solution = reduce(conds)
    if not solution:
        return conflict_return
    sorted_solution = sorted(solution, key=lambda c: c.version)
    return " ".join(map(str, sorted_solution))


class Condition(object):
    op_order = ['>', '<', '==', '>=', '<=', '!=']

    # This is important. Read: pick row by self.op, i.e. '==' is the third op
    # in op_order, so if self.op is '==', pick third row. Similarly, pick
    # column in that row by other.op. Say other.op is '>=', then we arrive at
    # '<'. That means, if
    #    self.op is '==' and other.op is '>=' and self.version < other.version
    # Then we have a conflict. BAM.
    conflict_table = [
        ['',   '>=', '>=', '',   '>=', ''   ],
        ['<=', '',   '<=', '<=', '',   ''   ],
        ['<',  '>',  '!=', '<',  '>',  '==' ],
        ['',   '>',  '>',  '',   '>',  ''   ],
        ['<',  '',   '<',  '<',  '',   ''   ],
        ['',   '',   '==', '',   '',   ''   ]
    ]
    # make a neat dict out of that, such that conflict_table['==']['>='] = '<'
    conflict_table = dict(zip(op_order, [dict(zip(op_order, row)) for row in conflict_table]))
    comp_map = {
        '': lambda x, y: False,
        '>': lambda x, y: x > y,
        '<': lambda x, y: x < y,
        '==': lambda x, y: x == y,
        '>=': lambda x, y: x >= y,
        '<=': lambda x, y: x <= y,
        '!=': lambda x, y: x != y,
    }

    def __init__(self, string):
        version_string = string.lstrip("!=<>")
        self.op = string.replace(version_string, "")
        self.version = Version(version_string)

    def __eq__(self, other):
        return self.op == other.op and self.version == other.version

    def conflicts(self, other):
        """Returns True if the conditions conflict."""
        comp = self.conflict_table[self.op][other.op]
        return self.comp_map[comp](self.version, other.version)

    def reduce(self, other):
        """Returns a new Condition that encompasses both self and other,
        or None if such a Condition does not exist. Note that this
        implementation is fucking sloppy, so self.reduce(other) != other.reduce(self).
        Do both."""
        if self.op == '==':  # Assume we catch conflicts somewhere else!
            return self
        if (self.op == '>' and '>' in other.op and self.version <= other.version) or \
            (self.op == other.op == '==' and self.version == other.version) or \
            (self.op == '>=' and '>' in other.op and self.version < other.version) or \
            (self.op == '<' and '<' in other.op and self.version >= other.version) or \
            (self.op == '<=' and '<' in other.op and self.version > other.version) or \
            (self.op == '!=' and '>' in other.op and self.version < other.version) or \
            (self.op == '!=' and '<' in other.op and self.version > other.version):
            return other
        if self.version == other.version and self.op == '>=' and other.op == '<=':
            return Condition('==' + str(other.version))
        if self.version == other.version and self.op == '!=':
            if other.op == '>=':
                return Condition('>' + str(other.version))
            if other.op == '<=':
                return Condition('<' + str(other.version))
        return None

    def __repr__(self):
        return "{}{}".format(self.op, self.version)


class Version(object):
    """This class implements a version that supports comparisons.
    Note that for comparisons
    There is a better implementation of this for semantic versioning at
    https://github.com/halst/version - but this only accepts x.y.z versions."""

    def __init__(self, string):
        self.parts = map(int, string.split("."))

    def _padded(self, n=6):
        return self.parts + [0] * (n - len(self.parts))

    def _zip_parts(self, other):
        max_l = max(len(self), len(other))
        return zip(self._padded(max_l), other._padded(max_l))

    def __len__(self):
        return len(self.parts)

    def __lt__(self, other):
        for x, y in self._zip_parts(other):
            if x < y:
                return True
            if x > y:
                return False
        return False

    def __eq__(self, other):
        return all([x == y for x, y in self._zip_parts(other)])

    def __ge__(self, other):
        return self > other or self == other

    def __ne__(self, other):
        return not all([x == y for x, y in self._zip_parts(other)])

    def __repr__(self):
        # /[.0]*$/ is redundant
        return ".".join(map(str, self.parts))


if __name__ == "__main__":
    test_cases = {
        '>2 >=2.1 <4 !=4.5.0.1': '>=2.1 <4',
        '>=3 !=3': '>3',
        '!=4.5.0.1 >2 >=2.1 <4': '>=2.1 <4',
        '>1 >2 <=3 <4': '>2 <=3',
        '<3 <3 <3': '<3',
        '==3.0.0': '==3.0.0',
        '>2 <1': 'unsatisfiable',
        '==2.2 >2': '==2.2',
        '==2.2 <2': 'unsatisfiable',
        '>=4 <=4': '==4',
        '>=4 <=4 !=4': 'unsatisfiable',
        '>1 >999.999.999.999': '>999.999.999.999',
    }
    if len(sys.argv) == 1:
        print(parse_solve_and_format(raw_input("Dependencies: ")))
    elif sys.argv[1] == "test":
        for case, expected in test_cases.items():
            solution = parse_solve_and_format(case)
            assert solution == expected, "Tried '{}', expected '{}' but got '{}'".format(case, expected, solution)
            print "{:25} --> {}".format(case, expected)
    else:
        print(parse_solve_and_format(sys.argv[1]))