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 SerializedObject(Event):
    """An object captured during execution.

    This is an abstract class, see subclasses for descriptions of different
    types of serialized objects.

    :IVariables:
      timestamp : float
        Number marking creation time of this SerializedObject. This number
        cannot be converted to a meaningful time description. It should only
        be used to arrange objects' creation on a timeline.
      human_readable_id : str
        A human-readable description of an object, suitable to be used as
        an identifier.
      module_name : str
        Location of the module this object's class was defined in. Should be
        usable in import statements.
      type_import : tuple(str, str) or None
        An import needed for the type to be available in the testing
        environment. None if no import is needed.
      type_name : str
        A canonical representation of the type this object is an instance of.
    """
    def __init__(self, obj):
        super(SerializedObject, self).__init__()
        self.human_readable_id = get_human_readable_id(obj)
        self.module_name = module_name(obj)
        self.type_name = get_type_name(obj)

    def _get_type_import(self):
        if self.module_name not in ['__builtin__', 'exceptions']:
            return (self.module_name, self.type_name)
    type_import = property(_get_type_import) 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 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 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 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 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 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))
from pythoscope.generator.lines import *
from pythoscope.generator.method_call_context import MethodCallContext
from pythoscope.serializer import BuiltinException, ImmutableObject, MapObject,\
    UnknownObject, SequenceObject, SerializedObject, LibraryObject
from pythoscope.store import FunctionCall, UserObject, MethodCall,\
    GeneratorObject, GeneratorObjectInvocation, CallToC
from pythoscope.side_effect import SideEffect
from pythoscope.util import all_of_type, flatten


# :: [SerializedObject|Call] -> [SerializedObject|Call]
def sorted_by_timestamp(objects):
    return sorted(objects, key=lambda o: o.timestamp)

# :: ([Event], int) -> [Event]
def older_than(events, reference_timestamp):
    return filter(lambda e: e.timestamp < reference_timestamp, events)

# :: ([Event], int) -> [Event]
def newer_than(events, reference_timestamp):
    return filter(lambda e: e.timestamp > reference_timestamp, events)

# :: Call -> Call
def top_caller(call):
    if call.caller is None:
        return call
    return top_caller(call.caller)

# :: (Call, int) -> [Call]
def subcalls_before_timestamp(call, reference_timestamp):
    for c in older_than(call.subcalls, reference_timestamp):
        yield c
        for sc in subcalls_before_timestamp(c, reference_timestamp):
            yield sc

# :: Call -> [Call]
def calls_before(call):
    """Go up the call graph and return all calls that happened before
    the given one.

    >>> class Call(object):
    ...     def __init__(self, caller, timestamp):
    ...         self.subcalls = []
    ...         self.caller = caller
    ...         self.timestamp = timestamp
    ...         if caller:
    ...             caller.subcalls.append(self)
    >>> top = Call(None, 1)
    >>> branch1 = Call(top, 2)
    >>> leaf1 = Call(branch1, 3)
    >>> branch2 = Call(top, 4)
    >>> leaf2 = Call(branch2, 5)
    >>> leaf3 = Call(branch2, 6)
    >>> leaf4 = Call(branch2, 7)
    >>> branch3 = Call(top, 8)
    >>> calls_before(branch3) == [top, branch1, leaf1, branch2, leaf2, leaf3, leaf4]
    True
    >>> calls_before(leaf3) == [top, branch1, leaf1, branch2, leaf2]
    True
    >>> calls_before(branch2) == [top, branch1, leaf1]
    True
    >>> calls_before(branch1) == [top]
    True
    """
    top = top_caller(call)
    return [top] + list(subcalls_before_timestamp(top, call.timestamp))

# :: [Call] -> [SideEffect]
def side_effects_of(calls):
    return flatten(map(lambda c: c.side_effects, calls))

# :: Call -> [SideEffect]
def side_effects_before(call):
    return older_than(side_effects_of(calls_before(call)), call.timestamp)

# :: [SideEffect] -> [SerializedObject]
def objects_affected_by_side_effects(side_effects):
    return flatten(map(lambda se: se.affected_objects, side_effects))

# :: [Event] -> [SerializedObject]
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,