def all(iterable):
def any(iterable):
def sorted(iterable, compare=cmp, key=None):
    def __init__(self, iterable, key=None):
    def __iter__(self):
    def next(self):
    def _grouper(self, tgtkey):
def samefile(file1, file2):
class groupby(object): def sorted_by_timestamp(objects):
    return sorted(objects, key=lambda o: o.timestamp) def side_effects_before(call):
    return older_than(side_effects_of(calls_before(call)), call.timestamp) def objects_affected_by_side_effects(side_effects):
    return flatten(map(lambda se: se.affected_objects, side_effects)) def side_effects_of(calls):
    return flatten(map(lambda c: c.side_effects, calls)) def older_than(events, reference_timestamp):
    return filter(lambda e: e.timestamp < reference_timestamp, events) def newer_than(events, reference_timestamp):
    return filter(lambda e: e.timestamp > reference_timestamp, events) def resolve_dependencies(events):
    events_so_far = set()
    def get_those_and_contained_objects(objs):
        return all_of_type(objs, SerializedObject) + get_contained_objects(objs)
    def get_contained_objects(obj):
        if isinstance(obj, list):
            return flatten(map(get_contained_objects, obj))
        if obj in events_so_far:
            return []
        else:
            events_so_far.add(obj)
        if isinstance(obj, SequenceObject):
            return get_those_and_contained_objects(obj.contained_objects)
        elif isinstance(obj, MapObject):
            return get_those_and_contained_objects(flatten(obj.mapping))
        elif isinstance(obj, LibraryObject):
            return get_those_and_contained_objects(obj.arguments)
        elif isinstance(obj, BuiltinException):
            return get_those_and_contained_objects(obj.args)
        elif isinstance(obj, UserObject):
            return get_contained_objects(obj.get_init_call() or [])
        elif isinstance(obj, (FunctionCall, MethodCall, GeneratorObjectInvocation)):
            return get_those_and_contained_objects(obj.input.values())
        elif isinstance(obj, GeneratorObject):
            if obj.is_activated():
                return get_those_and_contained_objects(obj.args.values() + obj.calls)
            return []
        elif isinstance(obj, SideEffect):
            return get_those_and_contained_objects(list(obj.affected_objects))
        elif isinstance(obj, MethodCallContext):
            return get_those_and_contained_objects([obj.call, obj.user_object])
        elif isinstance(obj, EqualAssertionLine):
            # Actual may be just a variable name, so just skip that.
            if isinstance(obj.actual, str):
                return get_those_and_contained_objects([obj.expected])
            return get_those_and_contained_objects([obj.expected, obj.actual])
        elif isinstance(obj, GeneratorAssertionLine):
            return get_contained_objects(obj.generator_call)
        elif isinstance(obj, RaisesAssertionLine):
            return get_those_and_contained_objects([obj.call, obj.expected_exception])
        elif isinstance(obj, Assign):
            if isinstance(obj.obj, SerializedObject):
                return get_those_and_contained_objects([obj.obj])
            return []
        elif isinstance(obj, ObjectAttributeReference):
            return get_those_and_contained_objects([obj.obj])
        elif isinstance(obj, BindingChange):
            return get_those_and_contained_objects([obj.obj, obj.name])
        elif isinstance(obj, (ImmutableObject, UnknownObject, CallToC,
                              CommentLine, SkipTestLine, EqualAssertionStubLine,
                              ModuleVariableReference)):
            return []
        else:
            raise TypeError("Wrong argument to get_contained_objects: %s." % repr(obj))
    return get_contained_objects(events) class MethodCallContext(object):
    def __init__(self, call, user_object):
        self.call = call
        self.user_object = user_object

    def __getattr__(self, name):
        if name in ['input', 'definition', 'calls', 'args', 'output', 'timestamp']:
            return getattr(self.call, name)

    def __repr__(self):
        return "MethodCallContext(obj=%r, call=%r)" % (self.user_object, self.call) class BuiltinException(CompositeObject):
    """A built-in exception instance, which may hold any kind of objects in its
    `args` attribute.

    It doesn't matter if an exception was generated by the interpreter or by
    the user code, it will be serialized as BuiltinException nevertheless. This
    means we can't assume anything about the contents of `args`.

    User-defined exceptions, both deriving from BaseException and those not,
    are serialized as UserObjects.
    """
    def __init__(self, obj, serialize):
        CompositeObject.__init__(self, obj)

        self.args = map(serialize, obj.args)
        self.constructor_format = "%s(%%s)" % class_name(obj)
        self.imports = set()

        if class_of(obj) in BUILTIN_ENVIRONMENT_ERROR_TYPES and obj.filename is not None:
            self.args.append(serialize(obj.filename)) class ImmutableObject(SerializedObject):
    """A serialized object which identity doesn't matter.

    Immutable objects (like strings or integers) and objects with well-defined
    location (like non-anonymous functions) are all considered ImmutableObjects.

    ImmutableObjects are certain to have a reconstructor.

    :IVariables:
      reconstructor : str
        A string representing code that will construct the object.
      imports : set
        A set of import descriptions needed for the reconstructor code to work.
    """
    def __init__(self, obj):
        SerializedObject.__init__(self, obj)

        self.reconstructor, self.imports = ImmutableObject.get_reconstructor_with_imports(obj)

    def __eq__(self, other):
        return isinstance(other, ImmutableObject) and \
            self.reconstructor == other.reconstructor and \
            self.imports == other.imports

    def __hash__(self):
        return hash(self.reconstructor)

    def __repr__(self):
        if self.imports:
            return "ImmutableObject(%r, imports=%r)" % (self.reconstructor, self.imports)
        return "ImmutableObject(%r)" % self.reconstructor

    # :: object -> (string, set)
    def get_reconstructor_with_imports(obj):
        """
        >>> reconstructor, imports = ImmutableObject.get_reconstructor_with_imports(re.compile('abcd'))
        >>> reconstructor
        "re.compile('abcd')"
        >>> imports == set(['re'])
        True
        >>> reconstructor, imports = ImmutableObject.get_reconstructor_with_imports(re.compile('abcd', re.I | re.M))
        >>> reconstructor
        "re.compile('abcd', re.IGNORECASE | re.MULTILINE)"
        >>> imports == set(['re'])
        True
        """
        if isinstance(obj, (int, long, float, str, unicode, types.NoneType)):
            # Bultin types has very convienient representation.
            return repr(obj), set()
        elif isinstance(obj, RePatternType):
            flags = regexp_flags_as_string(obj.flags)
            if flags:
                return ('re.compile(%r, %s)' % (obj.pattern, flags), set(['re']))
            else:
                return ('re.compile(%r)' % obj.pattern, set(['re']))
        elif isinstance(obj, types.FunctionType):
            function = obj.func_name
            module = obj.__module__
            return (function, set([(module, function)]))
        else:
            raise TypeError("Unknown type of an ImmutableObject: %r." % obj)
    get_reconstructor_with_imports = staticmethod(get_reconstructor_with_imports) class MapObject(CompositeObject):
    """A mutable object that contains unordered mapping of key/value pairs.
    """
    def __init__(self, obj, serialize):
        # Serialize the parts first and only after that call super, so that
        # the parts get a lower timestamp than the whole object.
        self.mapping = [(serialize(k), serialize(v)) for k,v in obj.items()]

        CompositeObject.__init__(self, obj)

        self.constructor_format = "{%s}"
        self.imports = set() class UnknownObject(SerializedObject):
    """A user object or a builtin value that we cannot recreate.

    :IVariables:
      partial_reconstructor : str
        A string representation of a partial object reconstructor. It doesn't
        have to be parsable, as it will be part of a comment. Partial
        reconstructor should give all possible hints about an object to help
        the user complete the code.
    """
    def __init__(self, obj):
        SerializedObject.__init__(self, obj)
        self.partial_reconstructor = get_partial_reconstructor(obj)

    def __repr__(self):
        return "UnknownObject(%r)" % self.partial_reconstructor class SequenceObject(CompositeObject):
    """A builtin object that contains an ordered sequence of other objects
    inside it.

    Tuples and other immutable builtin types are still serialized into
    a SequenceObject, because they may contain a mutable element inside them.
    """
    type_formats_with_imports = {
        list: ("[%s]", set()),
        frozenset: ("frozenset([%s])", set()),
        set: ("set([%s])", set()),
        sets.ImmutableSet: ("ImmutableSet([%s])", set([("sets", "ImmutableSet")])),
        sets.Set: ("Set([%s])", set([("sets", "Set")])),
        tuple: ("(%s)", set()),
    }

    def __init__(self, obj, serialize):
        # Serialize the parts first and only after that call super, so that
        # the parts get a lower timestamp than the whole object.
        self.contained_objects = map(serialize, obj)

        CompositeObject.__init__(self, obj)

        # Arrays constructor needs to include a typecode.
        if isinstance(obj, array.array):
            self.constructor_format = "array.array('%s', [%%s])" % obj.typecode
            self.imports = set(["array"])
        # Special case for tuples with a single element.
        elif isinstance(obj, tuple) and len(obj) == 1:
            self.constructor_format = "(%s,)"
            self.imports = set()
        else:
            self.constructor_format = self.type_formats_with_imports[type(obj)][0]
            self.imports = self.type_formats_with_imports[type(obj)][1]

    def __repr__(self):
        return "SequenceObject(%s)" % (self.constructor_format % self.contained_objects) class LibraryObject(SerializedObject):
    type_formats_with_imports = {
        ('xml.dom.minidom', 'Element'):
            ("Element(%s)",
             ["tagName", "namespaceURI", "prefix"],
             set([("xml.dom.minidom", "Element")])),
        ('datetime', 'datetime'):
            ("datetime.datetime(%s)",
             ["year", "month", "day", "hour", "minute", "second", "microsecond", "tzinfo"],
             set(["datetime"])),
    }

    def __init__(self, obj, serialize):
        con, argnames, imp = self.type_formats_with_imports[id_of_class_of(obj)]

        self.constructor_format = con
        self.arguments = map(serialize, [getattr(obj, a, None) for a in argnames])
        self.imports = imp

        # Arguments were serialized first, before a call to super, so that they
        # get a lower timestamp than the whole object.
        SerializedObject.__init__(self, obj) class SideEffect(Event):
    __metaclass__ = MetaSideEffect
    def __init__(self, affected_objects, only_referenced_objects):
        super(SideEffect, self).__init__()
        self.affected_objects = affected_objects
        self.referenced_objects = affected_objects + only_referenced_objects class GlobalRead(GlobalVariableSideEffect):
    def __init__(self, module, name, value):
        super(GlobalRead, self).__init__([], [])
        self.module = module
        self.name = name
        self.value = value class GlobalRebind(GlobalVariableSideEffect):
    def __init__(self, module, name, value):
        super(GlobalRebind, self).__init__([], []) # TODO: module's __dict__ is affected
        self.module = module
        self.name = name
        self.value = value class BuiltinMethodWithPositionArgsSideEffect(SideEffect):
    definition = None # set in a subclass

    def __init__(self, obj, *args):
        super(BuiltinMethodWithPositionArgsSideEffect, self).__init__([obj], list(args))
        self.obj = obj
        self.args = args

    def args_mapping(self):
        return dict(zip(self.definition.args, self.args)) class AttributeRebind(SideEffect):
    def __init__(self, obj, name, value):
        super(AttributeRebind, self).__init__([obj], [value])
        self.obj = obj
        self.name = name
        self.value = value
    def __repr__(self):
        return "%s(id=%r, %r, %s, %r)" % (self.__class__.__name__, id(self), self.obj, self.name, self.value) class Function(Definition, Callable):
    def __init__(self, name, args=None, code=None, calls=None, is_generator=False, module=None):
        Definition.__init__(self, name, args=args, code=code, is_generator=is_generator)
        Callable.__init__(self, calls)
        self.module = module
        if is_generator:
            self.calls_type = GeneratorObject
        else:
            self.calls_type = FunctionCall

    def get_unique_calls(self):
        return set(self.calls)

    def __repr__(self):
        return "Function(name=%s, args=%r, calls=%r)" % (self.name, self.args, self.calls) class FunctionCall(Call):
    pass class UserObject(Callable, SerializedObject):
    """Serialized instance of a user-defined type.

    UserObjects are also callables that aggregate MethodCall instances,
    capturing the whole life of an object, from initialization to destruction.
    """
    calls_type = (MethodCall, GeneratorObject)

    def __init__(self, obj, klass):
        Callable.__init__(self)
        SerializedObject.__init__(self, obj)
        self.klass = klass
        self.type_name = self.klass.name

    # Defined lazily to ease testing - classes may be assigned to modules after
    # creation of UserObject, or never at all.
    module_name = property(lambda self: self.klass.module.locator, lambda s,v: None)

    def get_init_call(self):
        """Return a call to __init__ or None if it wasn't called.
        """
        return findfirst(lambda call: call.definition.name == '__init__', self.calls)

    def get_external_calls(self):
        """Return all calls to this object made from the outside.

        Note: __init__ is considered an internal call.
        """
        def is_not_init_call(call):
            return call.definition.name != '__init__'
        return filter(is_not_init_call, filter(self.is_external_call, self.calls))

    def get_init_and_external_calls(self):
        return filter(self.is_external_call, self.calls)

    def __repr__(self):
        return "UserObject(id=%s, klass=%r)" % (id(self), self.klass.name)

    def is_external_call(self, call):
        if isinstance(call, GeneratorObject):
            return True
        return (not call.caller) or (call.caller not in self.calls) class MethodCall(Call):
    pass class GeneratorObject(Callable, SerializedObject):
    """Representation of a generator object - a callable with an input and many
    outputs (here called "yields").
    """
    calls_type = GeneratorObjectInvocation

    def __init__(self, obj, generator=None, args=None, callable=None):
        Callable.__init__(self)
        SerializedObject.__init__(self, obj)
        if generator is not None and args is not None and callable is not None:
            self.activate(generator, args, callable)

    def activate(self, generator, args, callable):
        assert_argument_type(generator, (Function, Method))
        assert_argument_type(callable, (Function, UserObject))
        if self.is_activated():
            raise ValueError("This generator has already been activated.")
        if not generator.is_generator:
            raise TypeError("Tried to activate GeneratorObject with %r as a generator definition." % generator)
        self.definition = generator
        self.args = args
        # Finally register this GeneratorObject with its callable context
        # (which will be a Function or an UserObject). This has to be
        # done only once for each GeneratorObject.
        callable.add_call(self)

    def is_activated(self):
        return hasattr(self, 'args')

    def raised_exception(self):
        return any([c.raised_exception() for c in self.calls])

    def _get_exception(self):
        for invocation in self.calls:
            if invocation.raised_exception():
                return invocation.exception
    exception = property(_get_exception)

    def __repr__(self):
        if self.is_activated():
            return "GeneratorObject(generator=%r, args=%r)" % \
                (self.definition.name, self.args)
        else:
            return "GeneratorObject()" class GeneratorObjectInvocation(Call):
    """Representation of a single generator invocation.

    Each time a generator is resumed a new GeneratorObjectInvocation is created.
    """ class Call(Event):
    """Stores information about a single function or method call.

    Includes reference to the caller, all call arguments, references to
    other calls made inside this one, references to side effects that occured
    during this call and finally an output value.

    __eq__ and __hash__ definitions provided for Function.get_unique_calls()
    and UserObject.get_external_calls().
    """
    def __init__(self, definition, args, output=None, exception=None):
        if [value for value in args.values() if not isinstance(value, SerializedObject)]:
            raise ValueError("Values of all arguments should be instances of SerializedObject class.")
        if output and exception:
            raise ValueError("Call should have a single point of return.")
        if not isinstance(definition, Definition):
            raise ValueError("Call definition object should be an instance of Definition.")

        super(Call, self).__init__()

        self.definition = definition
        self.input = args
        self.output = output
        self.exception = exception

        self.caller = None
        self.subcalls = []
        self.side_effects = []

    def add_subcall(self, call):
        if call.caller is not None:
            raise TypeError("This %s of %s already has a caller." % \
                                (class_name(call), call.definition.name))
        call.caller = self
        self.subcalls.append(call)

    def raised_exception(self):
        return self.exception is not None

    def set_output(self, output):
        self.output = output

    def set_exception(self, exception):
        self.exception = exception

    def clear_exception(self):
        self.exception = None

    def add_side_effect(self, side_effect):
        self.side_effects.append(side_effect)

    def __eq__(self, other):
        if type(self) != type(other):
            return False
        return self.definition == other.definition and \
               self.input == other.input and \
               self.output == other.output and \
               self.exception == other.exception and \
               self.side_effects == other.side_effects

    def __hash__(self):
        return hash((self.definition.name,
                     tuple(self.input.iteritems()),
                     self.output,
                     self.exception,
                     tuple(self.side_effects)))

    def __repr__(self):
        return "%s(definition=%s, input=%r, output=%r, exception=%r, side_effects=[..(%d)..])" % \
            (class_name(self), self.definition.name, self.input, self.output,
             self.exception, len(self.side_effects)) class CallToC(Call):
    def __init__(self, name, side_effect=None):
        super(CallToC, self).__init__(CFunction(name), {})
        self.side_effect = side_effect

    def clear_side_effect(self):
        self.side_effect = None class Method(Definition):
    def __init__(self, name, args=None, code=None, is_generator=False, klass=None):
        Definition.__init__(self, name, args=args, code=code, is_generator=is_generator)
        self.klass = klass

    def get_call_args(self):
        """Return names of arguments explicitly passed during call to this
        method.

        In other words, it removes "self" from the list of arguments, as "self"
        is passed implicitly.
        """
        if self.args and self.args[0].startswith('*'):
            return self.args
        return self.args[1:]

    def is_creational(self):
        return self.name in CREATIONAL_METHODS

    def is_private(self):
        """Private methods (by convention) start with a single or double
        underscore.

        Note: Special methods are *not* considered private.
        """
        return self.name.startswith('_') and not self.is_special()

    def is_special(self):
        """Special methods, as defined in
        <http://docs.python.org/reference/datamodel.html#specialnames>
        have names starting and ending with a double underscore.
        """
        return self.name.startswith('__') and self.name.endswith('__')

    def __repr__(self):
        return "Method(name=%s, args=%r)" % (self.name, self.args) class Callable(object):
    """Dynamic aspect of a callable object. Tracks all calls made to given
    callable.

    Each Callable subclass tracks a different type of Calls.
    """
    calls_type = None

    def __init__(self, calls=None):
        if calls is None:
            calls = []
        self.calls = calls

    def add_call(self, call):
        assert_argument_type(call, self.calls_type)
        self.calls.append(call) def all_of_type(objects, type):
    """Return all objects that are instances of a given type.
    """
    return [o for o in objects if isinstance(o, type)] def compact(lst):
    "Remove all occurences of None from the given list."
    return [x for x in lst if x is not None] def flatten(lst):
    """Flatten given list.

    >>> flatten([[1, 2, 3], [4, 5], [6, 7], [8]])
    [1, 2, 3, 4, 5, 6, 7, 8]
    """
    return list(itertools.chain(*lst)) def underscore(name):
    """Convert name into underscore_name.

    >>> underscore('CamelCase')
    'camel_case'
    >>> underscore('already_underscore_name')
    'already_underscore_name'
    >>> underscore('BigHTMLClass')
    'big_html_class'
    >>> underscore('')
    ''
    """
    if name and name[0].isupper():
        name = name[0].lower() + name[1:]

    def capitalize(match):
        string = match.group(1).capitalize()
        return string[:-1] + string[-1].upper()

    def underscore(match):
        return '_' + match.group(1).lower()

    name = re.sub(r'([A-Z]+)', capitalize, name)
    return re.sub(r'([A-Z])', underscore, name)
from copy import copy
from pythoscope.compat import set
from pythoscope.generator.dependencies import sorted_by_timestamp,\
    side_effects_before, objects_affected_by_side_effects, side_effects_of,\
    older_than, newer_than, resolve_dependencies
from pythoscope.generator.method_call_context import MethodCallContext
from pythoscope.generator.lines import *
from pythoscope.generator.selector import testable_calls
from pythoscope.serializer import BuiltinException, ImmutableObject, MapObject,\
    UnknownObject, SequenceObject, LibraryObject
from pythoscope.side_effect import SideEffect, GlobalRead, GlobalRebind,\
    BuiltinMethodWithPositionArgsSideEffect, AttributeRebind
from pythoscope.store import Function, FunctionCall, UserObject, MethodCall,\
    GeneratorObject, GeneratorObjectInvocation, Call, CallToC, Method, Callable
from pythoscope.util import all_of_type, compact, flatten, underscore
    def get_contained_events(obj):
        """Return a list of Events this object requires during testing.

        This function will descend recursively if objects contained within given
        object are composite themselves.
        """
        if isinstance(obj, list):
            return flatten(map(get_contained_events, obj))
        # Lists are unhashable anyway, so we don't remember them.
        if obj in events_so_far:
            return []
        else:
            events_so_far.add(obj)
        if isinstance(obj, ImmutableObject):
            # ImmutableObjects are self-sufficient.
            return []
        elif isinstance(obj, UnknownObject):
            return []
        elif isinstance(obj, SequenceObject):
            return get_those_and_contained_events(obj.contained_objects)
        elif isinstance(obj, MapObject):
            return get_those_and_contained_events(flatten(obj.mapping))
        elif isinstance(obj, LibraryObject):
            return get_those_and_contained_events(obj.arguments)
        elif isinstance(obj, BuiltinException):
            return get_those_and_contained_events(obj.args)
        elif isinstance(obj, UserObject):
            return get_contained_events(obj.get_init_and_external_calls())
        elif isinstance(obj, (FunctionCall, MethodCall, GeneratorObjectInvocation)):
            ret = get_those_and_contained_events(obj.input.values() + list(obj.side_effects))
            if obj.caller:
                ret += side_effects_before_and_affected_objects(obj)
            return ret
        elif isinstance(obj, GeneratorObject):
            if obj.is_activated():
                return get_those_and_contained_events(obj.args.values()) +\
                    get_contained_events(obj.calls)
            else:
                return []
        elif isinstance(obj, SideEffect):
            return [obj] + get_those_and_contained_events(list(obj.affected_objects))
        elif isinstance(obj, CallToC):
            return side_effects_before_and_affected_objects(obj)
        else:
            raise TypeError("Wrong argument to get_contained_events: %s." % repr(obj))
    return get_those_and_contained_events(objs)

def side_effects_before_and_affected_objects(call):
    se = side_effects_before(call)
    return se + objects_affected_by_side_effects(se)

# :: [Event] -> [Event]
def remove_duplicates_and_bare_method_contexts(events):
    new_events = list()
    for event in events:
        if not isinstance(event, MethodCallContext) and event not in new_events:
            new_events.append(event)
    return new_events

# :: ([Event], [Event]) -> [Event]
def include_requirements(test_events, execution_events):
    ignored_side_effects = side_effects_of(explicit_calls(test_events))
    ignored_objects = []
    new_events = []
    for event in test_events:
        for new_event in objects_required_for(event, event.timestamp, execution_events):
            # If a call appears explicitly in the test body we should
            # ignore all side effects caused by it.
            if new_event not in ignored_side_effects:
                new_events.append(new_event)
            elif isinstance(new_event, AttributeRebind) and not isinstance(new_event.value, ImmutableObject):
                change = BindingChange(ObjectAttributeReference(new_event.obj, new_event.name, new_event.timestamp),
                                       new_event.value,
                                       new_event.timestamp)
                new_events.append(change)
                # We can ignore the object that already has an assigned name,
                # unless it was needed earlier.
                if new_event.value not in new_events:
                    ignored_objects.append(new_event.value)
    return filter(lambda e: e not in ignored_objects, new_events + test_events)

# :: (Event, [Event], int) -> bool
def used_later_than(event, timeline, timestamp):
    return not isinstance(event, ImmutableObject) and \
        event in resolve_dependencies(newer_than(timeline, timestamp))

# :: [Event] -> [Event]
def fix_tests_using_call_outputs(timeline):
    """If a tested call output is used later in the test and it was created by
    the call we have to assign it a name.

    E.g. we can't just do that:
        assert_equal(expected, call())
        assert_equal(?call_output?, something.somewhere)
    so sometimes we need this:
        output = call()
        assert_equal(expected, output)
        assert_equal(output, something.somewhere)
    """
    def new_name_generator():
        yield 'result'
        i = 2
        while True:
            yield "result%d" % i
            i += 1
    name = new_name_generator()
    for event in timeline:
        if isinstance(event, EqualAssertionLine) and \
                isinstance(event.actual, (MethodCallContext, Call)) and \
                event.actual.output.timestamp > event.actual.timestamp and \
                used_later_than(event.actual.output, timeline, event.timestamp):
            varname = name.next()
            yield Assign(varname, event.actual, event.actual.timestamp-0.0001)
            event.actual = varname
            yield event
        else:
            yield event

# [Event] -> [Call]
def explicit_calls(event):

    events_so_far = set()