class Evaluator(ast.NodeVisitor):
    def push(self, value):
        if value is None:
            raise Exception('Try to push None value')

        self.stack.append(value)

    def pop(self):
        return self.stack.pop()

    def visit_Name(self, node):
        self.push(self.scope.find_name(node.id, node.lineno))

    def visit_IfExp(self, node):
        self.visit(node.body)

    def visit_Attribute(self, node):
        self.visit(node.value)
        obj = self.pop()

        try:
            value = obj[node.attr]
        except KeyError:
            value = UnknownObject()

        self.push(value)

    def visit_Str(self, node):
        self.push(create_object(self.scope, node.s))

    def visit_Num(self, node):
        self.push(create_object(self.scope, node.n))

    def visit_List(self, node):
        self.push(Indexable(self.scope, create_object(self.scope, []), node.elts))

    def visit_Tuple(self, node):
        self.push(Indexable(self.scope, create_object(self.scope, ()), node.elts))

    def visit_Dict(self, node):
        self.push(Dict(self.scope, node))

    def visit_Call(self, node):
        self.visit(node.func)
        func = self.pop()

        args = []
        for arg in node.args:
            self.visit(arg)
            args.append(self.pop())

        self.push(func.op_call(args))

    def visit_Subscript(self, node):
        self.visit(node.slice)
        idx = self.pop()

        self.visit(node.value)
        obj = self.pop()

        self.push(obj.op_getitem(idx))

    def visit_Slice(self, node):
        if node.upper:
            self.visit(node.upper)
            upper = self.pop()
        else:
            upper = None

        if node.lower:
            self.visit(node.lower)
            lower = self.pop()
        else:
            lower = None

        if node.step:
            self.visit(node.step)
            step = self.pop()
        else:
            step = None

        self.push(Slice(upper, lower, step))

    def visit_BoolOp(self, node):
        self.visit(node.values[-1])

    def visit_BinOp(self, node):
        self.visit(node.left)

    def visit_Compare(self, node):
        self.push(FakeInstanceObject(create_object(self.scope, bool)))

    def visit_ListComp(self, node):
        from .scope import InnerScope
        from .names import PostponedName, AssignedName

        scope = InnerScope(node, self.scope)

        for gen in node.generators:
            value = PostponedName(self.scope, create_object_from_seq_item, self.scope, gen.iter)

            for n, idx in get_indexes_for_target(gen.target, [], []):
                scope.add_name(n.id, AssignedName(idx, value, n.lineno))

        self.push(Indexable(scope, create_object(scope, []), [node.elt]))

    def visit_GeneratorExp(self, node):
        self.visit_ListComp(node)

    def process(self, tree, scope, skip_toplevel=True):
        #from .tree import dump_tree; print '!!!', scope.filename; print dump_tree(tree); print

        if getattr(tree, '_evaluating', False):
            return UnknownObject()

        self.scope = scope
        self.ops = []
        self.stack = []

        tree._evaluating = True

        try:
            if skip_toplevel:
                self.generic_visit(tree)
            else:
                self.visit(tree)

            if len(self.stack) != 1:
                raise Exception('invalid eval stack:', repr(self.stack))
        except RecursiveCallException:
            raise
        except Exception, e:
            if not getattr(e, '_processed', None):
                from .tree import dump_tree
                logger = logging.getLogger(__name__)
                logger.exception('\n<<<<<<<<<<<<<<<<<')
                logger.error('\n|||||||||||| %s - %s - %s\n%s>>>>>>>>>>\n', scope.__class__.__name__,
                    scope.fullname, scope.filename, dump_tree(tree))
                e._processed = True

            raise
        finally:
            tree._evaluating = False

        return self.stack[0] class NameExtractor(ast.NodeVisitor):
    def visit_FunctionDef(self, node):
        function_scope = self.scope.get_child_by_lineno(node.lineno)
        self.add_name(node.name, (FunctionName, function_scope, node), node.lineno)

    def visit_ImportFrom(self, node):
        for n in node.names:
            module_name = '.' * node.level + (node.module if node.module else '')
            if n.name == '*':
                self.starred_imports.append((module_name, node.lineno))
            else:
                name = n.asname if n.asname else n.name
                self.add_name(name, (ImportedName, module_name, n.name), node.lineno)

    def visit_Import(self, node):
        for n in node.names:
            if n.asname:
                self.names[n.asname] = ModuleName, n.name
            else:
                name, _, tail = n.name.partition('.')
                self.add_name(name, (ModuleName, name, set()), node.lineno)
                if tail:
                    self.additional_imports.setdefault(name, []).append(tail)

    def visit_For(self, node):
        value = PostponedName(self.scope, create_object_from_seq_item, self.scope, node.iter)

        for n, idx in get_indexes_for_target(node.target, [], []):
            self.add_name(n.id, (AssignedName, idx, value, n.lineno), node.lineno)

        self.generic_visit(node)

    def visit_ClassDef(self, node):
        class_scope = self.scope.get_child_by_lineno(node.lineno)
        self.add_name(node.name, (ClassName, class_scope, node), node.lineno)

    def visit_Assign(self, node):
        value = Value(self.scope, node.value)

        for n, idx in get_indexes_for_target(node.targets[0], [], []):
            if isinstance(n,  ast.Name):
                self.add_name(n.id, (AssignedName, idx, value, n.lineno), n.lineno)
            if isinstance(n,  ast.Subscript):
                self.subscript_assignments.append((n.value, n.slice, idx, value, n.lineno))

    def visit_arguments(self, node):
        for i, n in enumerate(node.args):
            self.add_name(n.id, (ArgumentName, self.scope, i, n.id), n.lineno)
            self.scope.args[i] = n.id

        for d in node.defaults:
            self.scope.defaults.append(Value(self.scope.parent, d))

        if node.vararg:
            self.scope.vararg = node.vararg
            self.add_name(node.vararg, (VarargName, self.scope), self.scope.node.lineno)

        if node.kwarg:
            self.scope.kwarg = node.kwarg
            self.add_name(node.kwarg, (KwargName, self.scope), self.scope.node.lineno)

    def add_name(self, name, value, lineno):
        if name in self.names:
            self.names[name].insert(0, (lineno, value))
        else:
            self.names[name] = [(lineno, value)]

    def process(self, node, scope):
        #from .tree import dump_tree; print dump_tree(node); print

        self.scope = scope
        self.starred_imports = []
        self.additional_imports = {}
        self.names = {}
        self.subscript_assignments = []

        self.generic_visit(node)

        for k, v in self.additional_imports.iteritems():
            for line, name in self.names[k]:
                if name[0] is not ModuleName:
                    continue

                name[2].update(v)

        return self.names, self.starred_imports, self.subscript_assignments def create_name(node, owner):
    obj = node[0](*node[1:])
    obj.project = owner.project
    obj.filename = owner.filename

    try:
        ds = obj.get_docstring()
    except:
        pass
        #logging.getLogger(__name__).exception("Can't get docstring")
    else:
        if ds:
            obj = owner.project.process_docstring(ds, obj)

    return obj class ArgumentName(GetObjectDelegate):
    def __init__(self, scope, index, name):
        self.scope = scope
        self.index = index
        self.name = name

    def get_object(self):
        try:
            return self._object
        except AttributeError:
            pass

        if self.index == 0 and self.scope.parent.type == 'class':
            from .objects import FakeInstanceObject
            self._object = FakeInstanceObject(self.scope.parent.cls)
        else:
            args = self.scope.project.calldb.get_args_for_scope(self.scope)
            if args:
                index = self.index
                if self.scope.parent.type == 'class':
                    index -= 1

                try:
                    obj = args[index]
                except IndexError:
                    obj = UnknownObject()
            else:
                obj = UnknownObject()

            self._object = obj

        return self._object

    def find_attr_assignments(self):
        return AttributesAssignsExtractor().process(self.name, self.scope, self.scope.node) class VarargName(GetObjectDelegate):
    def __init__(self, scope):
        self.scope = scope

    def get_object(self):
        try:
            return self._object
        except AttributeError:
            pass

        from .objects import InstanceObject
        self._object = InstanceObject(('undefined', None), ())
        return self._object class ClassName(NodeLocation, Object):
    def __init__(self, scope, node):
        self.scope = scope
        self.node = node

    def get_docstring(self):
        return ast.get_docstring(self.node)

    def get_bases(self):
        try:
            return self._bases
        except AttributeError:
            pass

        self._bases = [self.scope.parent.eval(r, False) for r in self.node.bases]
        return self._bases

    def get_names(self):
        try:
            self._names
        except AttributeError:
            self._names = self.scope.get_names()

        names = set()
        names.update(self._names)
        for b in self.get_bases():
            names.update(b.get_names())

        return names

    def __getitem__(self, name):
        if name in self.get_names():
            if name in self._names:
                return self.scope.get_name(name, self._names[name][-1][0])

            for cls in self.get_bases():
                try:
                    return cls[name]
                except KeyError:
                    pass

        raise KeyError(name)

    def op_call(self, args):
        from .objects import FakeInstanceObject
        return FakeInstanceObject(self)

    def get_assigned_attributes(self):
        try:
            self._assigned_attributes
        except AttributeError:
            self._assigned_attributes = {}
            for name, loc in self.scope.get_names().iteritems():
                for line, args in loc:
                    if args[0] == FunctionName:
                        func = self.scope.get_name(name, line)
                        func.scope.get_names()
                        if not func.scope.args:
                            continue

                        slf = func.scope.get_name(func.scope.args[0])
                        self._assigned_attributes.update(slf.find_attr_assignments())


        result = self._assigned_attributes.copy()
        for cls in self.get_bases():
            for attr, value in cls.get_assigned_attributes().iteritems():
                if attr not in result:
                    result[attr] = value

        return result

    def get_signature(self):
        sig = self['__init__'].get_signature()
        if sig:
            name, args, vararg, kwarg, defaults = sig
            return name, args[1:], vararg, kwarg, defaults
        else:
            return None class FunctionName(NodeLocation, Object):
    def __init__(self, scope, node):
        self.scope = scope
        self.node = node
        self._calling = False

    def get_scope(self):
        return self.scope

    def op_call(self, args=[]):

        if self._calling:
            raise RecursiveCallException(self)

        self._calling = True
        try:
            for rvalue in ReturnExtractor().process(self.node):
                try:
                    result = self.scope.get_call_scope(args).eval(rvalue, False)
                    if result and type(result) is not Object:
                        return result
                except RecursiveCallException, e:
                    if not e.is_called_by(self):
                        raise
        finally:
            self._calling = False

        return UnknownObject()

    def as_method_for(self, obj):
        return MethodObject(obj, self)

    def get_signature(self):
        self.scope.get_names()
        args = [self.scope.args[k] for k in sorted(self.scope.args.keys())]
        return (self.scope.name, args, self.scope.vararg, self.scope.kwarg, self.scope.defaults)

    def get_docstring(self):
        return ast.get_docstring(self.node) class ImportedName(GetObjectDelegate):
    def __init__(self, module_name, name):
        self.module_name = module_name
        self.name = name

    def get_object(self):
        module = self.project.get_module(self.module_name, self.filename)
        try:
            return module[self.name]
        except KeyError:
            pass

        mname = self.module_name
        if mname[-1] == '.':
            mname = mname[:-1]

        return self.project.get_module(mname + '.' + self.name, self.filename) class PostponedName(GetObjectDelegate):
    def __init__(self, owner, *node):
        self.owner = owner
        self.node = node

    def get_object(self):
        try:
            return self._object
        except AttributeError:
            pass

        obj = self._object = create_name(self.node, self.owner)
        return obj class ListHolder(GetObjectDelegate):
    def __init__(self, obj, values):
        self.values = values
        self.object = obj

    def get_object(self):
        return self.object

    def op_getitem(self, idx):
        return self.values[idx.get_value()] def create_object_from_class_name(scope, name):
    from .objects import FakeInstanceObject
    return FakeInstanceObject(scope.eval(name, False)) def create_object_from_expr(scope, expr):
    return scope.eval(expr, False)
import ast
import logging
from bisect import bisect
from .evaluator import Evaluator
from .names import NameExtractor, create_name, ArgumentName, VarargName
from .names import ClassName, FunctionName, ImportedName, PostponedName
from .common import ListHolder, create_object_from_class_name, create_object_from_expr
            from supplement.names import AssignedName

        raise KeyError(name)

    def __getitem__(self, name):
        return self.get_name(name)

    def eval(self, node, skip_toplevel=True):
        return Evaluator().process(node, self, skip_toplevel)

    def get_call_scope(self, args):
        return CallScope(self, args)

    def find_name(self, name, lineno=None):
        try:
            return self.get_name(name, lineno)
        except KeyError:
            pass

        scope = self.parent
        while scope:
            try:
                return scope[name]
            except KeyError:
                scope = scope.parent

        return self.project.get_module('__builtin__')[name]

    def get_scope_at(self, source, lineno, continous=True):
        try:
            ranges = self._scope_ranges
        except AttributeError:
            ranges = self._scope_ranges = ([], [])
            collect_scope_ranges(self.node, ranges, [])

        lines, scopes = ranges
        idx = bisect(lines, lineno) - 1
        node, end, parent = scopes[idx]
        cadd = 0

        if end and not continous:
            lines = source.splitlines()
            i = end - 2
            while i >= 0:
                if lines[i].strip():
                    break
                i -= 1
            cadd = end - i - 2

        while parent and end and lineno >= end - cadd:
            node, end, parent = parent

        try:
            return self.node2scope[node]
        except KeyError:
            pass

        for s in traverse_tree(self):
            if s.node is node:
                self.node2scope[node] = s
                return s

        raise Exception('Scope for line %d not found' % lineno)


SCOPE_CLASSES = (ast.ClassDef, ast.FunctionDef, ast.ExceptHandler, ast.With, ast.Module)
BLOCK_CLASSES = SCOPE_CLASSES + (ast.TryExcept, ast.TryFinally, ast.If, ast.While, ast.For)

def collect_scope_ranges(root, ranges, toclose, parent=None):
    if not isinstance(root, BLOCK_CLASSES):
        return

    isscope = isinstance(root, SCOPE_CLASSES)
    if isscope:
        lrange = [root, None, parent]
        ranges[0].append(root.lineno)
        ranges[1].append(lrange)
        parent = lrange

    for n in root.body if isscope else ast.iter_child_nodes(root):
        if toclose:
            for r in toclose:
                r[1] = n.lineno

            toclose[:] = []

        collect_scope_ranges(n, ranges, toclose, parent)

    if isscope:
        toclose.append(lrange)


class CallScope(object):
    def __init__(self, parent, args):
        self.name = ''
        self.type = 'func'
        self.fullname = parent.fullname
        self.parent = parent
        self.args = args
        self.project = parent.project
        self.filename = parent.filename

    def __repr__(self):
        return '<CallScope %s %s>' % (self.fullname, self.filename)

    def get_names(self):
        return self.parent.get_names()

    def __contains__(self, name):
        return name in self.get_names()

    def find_name(self, name, lineno=None):
        try:
            return self.get_name(name, lineno)
        except KeyError:
            pass

        return self.parent.parent.find_name(name)

    def get_name(self, name, lineno=None):
        obj = self.parent.get_name(name, lineno)

        if isinstance(obj, ArgumentName):