"""
**********************************************************************

  A RapydScript to JavaScript compiler.
  https://github.com/atsepkov/RapydScript

  -------------------------------- (C) ---------------------------------

                       Author: Alexander Tsepkov
                         <atsepkov@pyjeon.com>
                         http://www.pyjeon.com

  Distributed under BSD License
    Copyright 2013 (c) Alexander Tsepkov <atsepkov@pyjeon.com>

 **********************************************************************
"""

from utils import noop, string_template, colored

def memoized(f):
    return def(x):
        if not this.computedType:
            this.computedType = f.call(this, x)
        return this.computedType

class AST:
    properties = {}

    def __init__(self, initializer):
        # Walk the prototype chain and copy all defined properties from the
        # initializer object
        if initializer:
            obj = self
            while obj:
                for i in dir(obj.properties):
                    self[i] = initializer[i]
                obj = Object.getPrototypeOf(obj)

    def clone(self):
        return new self.constructor(self)


class Token(AST):
    """
    Tokens generated by the tokenizer in the first stage of parsing
    """
    properties = {
        'type': 'The type of the token',
        'subtype': 'The subtype of the token',
        'value': 'The value of the token',
        '_value': 'The src value of the token',
        'line': 'The line number at which the token occurs',
        'col': 'The column number at which the token occurs',
        'pos': 'Absolute position of the token start, relative to document start',
        'endpos': 'Absolute position of the token start, relative to document start',
        'newline_before': 'True if there was a newline before this token',
        'comments_before': 'True if there were comments before this token',
        'comma_expected': 'True if comma was expected instead of this token',
        'file': 'Name of the file currently being parsed'
    }

class Node(AST):
    """
    Base class of all AST nodes
    """
    properties = {
        'start': "[Token] The first token of this node",
        'end': "[Token] The last token of this node"
    }
    computedType = None

    @memoized
    def resolveType(heap):
        """
        Function to resolve the final object type of the statement, if possible, override this on
        per-node basis
        """
        return "?"

    def _walk(self, visitor):
        return visitor._visit(self)

    def walk(self, visitor):
        return self._walk(visitor)

    def _dump(self, depth, omit, offset, include_name, compact):
        """
        Dump node structure, used for debugging:

            depth: how many nodes below to dump
            omit: properties to omit
            offset: padding offset to use
            include_name: whether to output the name of the node
            compact: use compact representation of the node
        """

        def out(string):
            pad = Array(offset + 1).join('  ')
            console.log(pad + string)

        if include_name:
            out(colored(type(self), 'yellow'))

        for key in this:
            if key in omit:
                continue

            colored_key = colored(key + ': ', 'blue')
            value = self[key]
            if Array.isArray(value):
                if value.length:
                    out(' ' + colored_key + '[')
                    if depth > 1:
                        for element in value:
                            element._dump(depth-1, omit, offset+1, True, compact)
                    else:
                        for element in value:
                            out('   ' + colored(type(element), 'yellow'))
                    out(' ]')
                else:
                    if not compact: out(' ' + colored_key + '[]')
            elif value not in [undefined, None]:
                if type(value):
                    if type(value) is 'Token':
                        # tokens identify the lexical trigger for this node
                        if compact:
                            out(' ' + colored_key + colored(
                                type(value) + '(' +
                                value.file + ':' + value.line + ':' + value.col + ': ' +
                                value.value + ')'
                                , 'magenta'
                            ))
                        else:
                            out(' ' + colored_key + colored(type(value), 'magenta'))
                            for property in value:
                                out('   ' + colored(property + ': ', 'blue') + value[property])
                    else:
                        # handle child nodes
                        out(' ' + colored_key + colored(type(value), 'yellow'))
                        if depth > 1:
                            value._dump(depth-1, omit, offset+1, False, compact)
                elif JS('typeof value') is "string":
                    out(' ' + colored_key + colored('"' + value + '"', 'green'))
                elif JS('typeof value') is "number":
                    out(' ' + colored_key + colored(value, 'green'))
                elif JS('typeof value') is "boolean":
                    out(' ' + colored_key + colored(value, 'green'))
                else:
                    # unexpected object
                    out(' ' + colored_key + colored(value, 'red'))
            else:
                # none/undefined
                if not compact: out(' ' + colored_key + value)

    def dump(self, depth=2, omit=['start', 'end'], compact=True):
        # a more user-friendly way to dump the AST tree than console.log
        return self._dump(depth, omit, 0, True, compact)

    @staticmethod
    def warn_function(self): pass

    @staticmethod
    def warn(txt, props):
        if Node.warn_function:
            Node.warn_function(string_template(txt, props))




# -----[ statements ]-----
class Statement(Node): "Base class of all statements"
class Debugger(Statement): "Represents a debugger statement"

class Directive(Statement):
    'Represents a directive, like "use strict";'
    properties = {
        value: "[string] The value of this directive as a plain string (it's not a String!)",
        scope: "[Scope/S] The scope that this directive affects"
    }

class SimpleStatement(Statement):
    "A statement consisting of an expression, i.e. a = 1 + 2"
    properties = {
        body: "[Node] an expression node (should not be instanceof Statement)"
    }
    def walk_(visitor):
        node = this
        return visitor._visit(node, def():
            node.body._walk(visitor)
        )


def walk_body(node, visitor):
    if isinstance(node.body, Statement):
        node.body._walk(visitor)
    elif node.body:
        for stat in node.body:
            stat._walk(visitor)


class Block(Statement):
    "A body of statements (usually bracketed)"
    properties = {
        body: "[Statement*] an array of statements"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            walk_body(self, visitor)
        )

class BlockStatement(Block): "A block statement"

class EmptyStatement(Statement):
    "The empty statement (empty block or simply a semicolon)"
    def _walk(self, visitor):
        return visitor._visit(self)

class StatementWithBody(Statement):
    "Base class for all statements that contain one nested body: `For`, `ForIn`, `Do`, `While`, `With`"
    properties = {
        body: "[Statement] the body; this should always be present, even if it's an EmptyStatement"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.body._walk(visitor)
        )

class LabeledStatement(StatementWithBody):
    "Statement with a label"
    properties = {
        label: "[Label] a label definition"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.label._walk(visitor)
            self.body._walk(visitor)
        )

class DWLoop(StatementWithBody):
    "Base class for do/while statements"
    properties = {
        condition: "[Node] the loop condition.  Should not be instanceof Statement"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.condition._walk(visitor)
            self.body._walk(visitor)
        )

class Do(DWLoop): "A `do` statement"
class While(DWLoop): "A `while` statement"

class ForIn(StatementWithBody):
    "A `for ... in` statement"
    properties = {
        init: "[Node] the `for/in` initialization code",
        name: "[SymbolRef?] the loop variable, only if `init` is Var",
        object: "[Node] the object that we're looping through"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.init._walk(visitor)
            self.object._walk(visitor)
            self.body._walk(visitor)
        )

class ForJS(StatementWithBody):
    "A `for ... in` statement"
    properties = {
        condition: "[Verbatim] raw JavaScript conditional"
    }

class ListComprehension(ForIn):
    "A list comprehension expression"
    properties = {
        condition: "[Node] the `if` condition",
        statement: "[Node] statement to perform on each element before returning it"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.init._walk(visitor)
            self.statement._walk(visitor)
            if self.condition:
                self.condition._walk(visitor)
        )

class DictComprehension(ListComprehension):
    "A dict comprehension expression"
    properties = {
        value_statement: "[Node] statement to perform on each value before returning it"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.init._walk(visitor)
            self.statement._walk(visitor)
            self.value_statement._walk(visitor)
            if self.condition:
                self.condition._walk(visitor)
        )

class With(StatementWithBody):
    "A `with` statement"
    properties = {
        expression: "[Node] the `with` expression"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
            self.body._walk(visitor)
        )

# -----[ scope and functions ]-----
class Scope(Block):
    "Base class for all statements introducing a lexical scope"
    properties = {
        docstring: "[string?] docstring for this scope, if any",
        directives: "[string*/S] an array of directives declared in this scope",
        variables: "[Object/S] a map of name -> SymbolDef for all variables/functions defined in this scope",
        localvars: "[SymbolDef*] list of variables local to this scope",
        functions: "[Object/S] like `variables`, but only lists function declarations",
        parent_scope: "[Scope?/S] link to the parent scope",
        enclosed: "[SymbolDef*/S] a list of all symbol definitions that are accessed from this scope or any subscopes",
    }

class TopLevel(Scope):
    "The toplevel scope"
    properties = {
        globals: "[Object/S] a map of name -> SymbolDef for all undeclared names",
        baselib: "[Object/s] a collection of used parts of baselib",
        imports: "[Object/S] a map of module_id->TopLevel for all imported modules",
        nonlocalvars: "[String*] a list of all non-local variable names (names that come from the global scope)",
        strict: "[boolean/S] true if strict directive is in scope",
        shebang: "[string] If #! line is present, it will be stored here",
        import_order: "[number] The global order in which this scope was imported",
        module_id: "[string] The id of this module",
        exports: "[SymbolDef*] list of names exported from this module",
        submodules: "[string*] list of names exported from this module",
        classes: "[Object/S] a map of class names to Class for classes defined in this module",
        filename: "[string] The absolute path to the file from which this module was read",
        srchash: "[string] SHA1 hash of source code, used for caching",
    }

class Splat(Statement):
    "Container for a naive import into the same scope, everything contained within the splat will be imported"
    properties = {
        module: "[SymbolVar] name of the module we're splatting",
        key: "[string] The key by which this module is stored in the global modules mapping",
        body: "[TopLevel] parsed contents of the imported file",
    }

class Import(Statement):
    "Container for a single import"
    properties = {
        module: "[SymbolVar] name of the module we're importing",
        key: "[string] The key by which this module is stored in the global modules mapping",
        alias: "[SymbolAlias] The name this module is imported as, can be None. For import x as y statements.",
        argnames: "[ImportedVar*] names of objects to be imported",
        body: "[TopLevel] parsed contents of the imported file",
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            for arg in self.argnames:
                arg._walk(visitor)
        )

class Imports(Statement):
    "Container for a single import"
    properties = {
        'imports': "[Import+] array of imports",
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            for imp in self.imports:
                imp._walk(visitor)
        )

class Decorator(Node):
    "Class for function decorators"
    properties = {
        expression: "[Node] decorator expression"
    }
    def _walk(self, visitor):
        if self.expression:
            self.expression.walk(visitor)

class Annotation(Node):
    "Class for argument/return annotations"
    properties = {
        expression: "[Node] decorator expression"
    }
    def _walk(self, visitor):
        if self.expression:
            self.expression.walk(visitor)

    @memoized
    def resolveType(self, heap):
        # annotations are parsed differently from other elements in that it's not what's contained within the variable
        # that defines the type but rather the variable syntax itself
        def parse(obj):
            if isinstance(obj, Array):
                # [Type]
                if obj.elements.length is 1: return '[' + parse(obj.elements[0]) + ']'
                return '[?]'
            if isinstance(obj, ObjectLiteral):
                # {String:Type}
                if obj.properties.length is 1: return '{String:' + parse(obj.properties[0].value) + '}'
                return '{String:?}'
            if isinstance(obj, SymbolRef):
                # Type
                # rename Array and Object/Dictionary to [?] and {String:?}
                return obj.name is 'Array' ? '[?]' : obj.name in ['Object', 'Dictionary'] ? '{String:?}' : obj.name
            if isinstance(obj, Call):
                if isinstance(obj.expression, SymbolRef) and obj.expression.name is 'Array' and obj.args.length is 1:
                    # Array(Type)
                    return '[' + parse(obj.args[0]) + ']'
                if isinstance(obj.expression, SymbolRef) and obj.expression.name in ['Object', 'Dictionary']:
                    # Object(Type), Dictionary(Type), Object(String, Type), Dictionary(String, Type)
                    # in place of Dictionary you can also use Object keyword
                    # both formats are accepted as a convenience feature for developers
                    if 1 <= obj.args.length <= 2:
                        return '{String:' + parse(obj.args[-1]) + '}'
                    return '{String:?}'
            return '?'
        return parse(self.expression)

class Lambda(Scope):
    "Base class for functions"
    properties = {
        name: "[SymbolDeclaration?] the name of this function/class/method",
        argnames: "[SymbolFunarg*] array of arguments",
        kwargs: "[SymbolFunarg?] kwargs symbol, if any",
        uses_arguments: "[boolean/S] tells whether this function accesses the arguments array",
        decorators: "[Decorator*] function decorators, if any",
        generator: "[boolean] true if this is a generator function (false by default)",
        return_annotation: "[Annotation?] the return type annotation provided (if any)"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():

            if self.decorators:
                for d in self.decorators:
                    d.walk(visitor)

            if self.name:
                self.name._walk(visitor)

            for arg in self.argnames:
                arg._walk(visitor)

            if self.argnames.starargs:
                self.argnames.starargs._walk(visitor)

            if self.kwargs:
                self.kwargs._walk(visitor)
            walk_body(self, visitor)
        )

class Accessor(Lambda): "A setter/getter function"

class Function(Lambda):
    "A function expression"
    @memoized
    def resolveType(self, heap):
        # I don't want to bother handling starargs yet, just say the signature is unknown
        if self.argnames.starargs: return 'Function'
        # self logic relies mostly on the resolveType within each annotation itself
        annotated = True
        args = []
        for arg in self.argnames:
            if arg.annotation:
                computedType = arg.annotation.resolveType(heap)
                if computedType:
                    args.push(computedType)
                else:
                    annotated = False
                    break
            else:
                annotated = False
                break

        if self.return_annotation:
            result = self.return_annotation.resolveType(heap)
            if not result:
                # it's ok not to have a return annotation, but not ok to have one that doesn't parse
                annotated = False

        signature = "Function"

        # we naively assume that argument annotations on function mean that the function is fully annotated, even if return is missing
        if annotated:
            signature += "(" + args.join(',') + ")"
            if result: signature += " -> " + result

        return signature

class Class(Scope):
    "A class declaration"
    properties = {
        name: "[SymbolDeclaration?] the name of this class",
        init: "[Function] constructor for the class",
        parent: "[Class?] parent class this class inherits from",
        static: "[string*] list of static methods",
        external: "[boolean] true if class is declared elsewhere, but will be within current scope at runtime",
        bound: "[string*] hash of methods that need to be bound to behave correctly (function pointers)",
        decorators: "[Decorator*] function decorators, if any",
        module_id: "[string] The id of the module this class is defined in",
        statements: "[Node*] list of statements in the class scope (excluding method definitions)",
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.name._walk(visitor)
            walk_body(this, visitor)
            if self.parent:
                self.parent._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        return self.name.name

class Module(Scope):
    "A module definition, meant to abstract a group of related classes and/or functions"
    properties = {
        name: "[SymbolDeclaration?] the name of this class",
        external: "[boolean] true if module is declared elsewhere, but will be within current scope at runtime",
        decorators: "[Decorator*] module decorators, if any"
    }

class Method(Lambda):
    "A class method definition"
    properties = {
        static: "[boolean] true if method is static"
    }

class Constructor(Method):
    "Constructor definition"
    properties = {
        callsSuper: "[boolean] true if user manually called super or Parent.__init__",
        parent: "[string?] parent class this class inherits from"
    }

# -----[ JUMPS ]-----
class Jump(Statement):
    "Base class for “jumps” (for now that's `return`, `throw` `break` and `continue`)"

class Exit(Jump):
    "Base class for “exits” (`return` and `throw`)"
    properties = {
        value: "[Node?] the value returned or thrown by this statement; could be null for Return"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            if self.value:
                self.value._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        return self.value.resolveType(heap)

class Return(Exit): "A `return` statement"
class Yield(Exit):
    "A `yield` statement"
    properties = {
        yield_from: "[boolean] true if it is `yield from` i.e. JS `yield*` ",
        yield_request: "[boolean] true if some value is requested from `yield`: `a = yield` or `f(yield, ...) ` and so on"
    }
class Throw(Exit): "A `throw` statement"

class LoopControl(Jump):
    "Base class for loop control statements (`break` and `continue`)"
    properties = {
        label: "[LabelRef?] the label, or null if none"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            if self.label:
                self.label._walk(visitor)
        )

class Break(LoopControl): "A `break` statement"
class Continue(LoopControl): "A `continue` statement"

# -----[ IF ]-----
class If(StatementWithBody):
    "A `if` statement"
    properties = {
        condition: "[Node] the `if` condition",
        alternative: "[Statement?] the `else` part, or null if not present"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.condition._walk(visitor)
            self.body._walk(visitor)
            if self.alternative:
                self.alternative._walk(visitor)
        )

# -----[ SWITCH ]-----
class Switch(Block):
    "A `switch` statement"
    properties = {
        expression: "[Node] the `switch` “discriminant”"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
            walk_body(self, visitor)
        )

class SwitchBranch(Block): "Base class for `switch` branches"
class Default(SwitchBranch): "A `default` switch branch"

class Case(SwitchBranch):
    "A `case` switch branch"
    properties = {
        expression: "[Node] the `case` expression"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
            walk_body(self, visitor)
        )

# -----[ EXCEPTIONS ]-----
class Try(Block):
    "A `try` statement"
    properties = {
        bcatch: "[Catch?] the catch block, or null if not present",
        bfinally: "[Finally?] the finally block, or null if not present"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            walk_body(self, visitor)
            if self.bcatch:
                self.bcatch._walk(visitor)

            if self.bfinally:
                self.bfinally._walk(visitor)
        )

class Catch(Block): "A `catch` node; only makes sense as part of a `try` statement"

class Except(Block):
    "An `except` node for RapydScript, which resides inside the catch block"
    properties = {
        argname: "[SymbolCatch] symbol for the exception",
        errors: "[SymbolVar*] error classes to catch in this block"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            if (self.argname):
                self.argname.walk(visitor)
            if (self.errors):
                for e in self.errors: e.walk(visitor)
            walk_body(self, visitor)
        )

class Finally(Block):
    "A `finally` node; only makes sense as part of a `try` statement"

# -----[ VAR/CONST ]-----
class Definitions(Statement):
    "Base class for `var` or `const` nodes (variable declarations/initializations)"
    properties = {
        definitions: "[VarDef*] array of variable definitions"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            for def_ in self.definitions:
                def_._walk(visitor)
        )

class Var(Definitions): "A `var` statement"
class Const(Definitions): "A `const` statement"

class VarDef(Node):
    "A variable declaration; only appears in a Definitions node"
    properties = {
        name: "[SymbolVar|SymbolConst] name of the variable",
        value: "[Node?] initializer, or null if there's no initializer"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.name._walk(visitor)
            if self.value:
                self.value._walk(visitor)
        )

# -----[ OTHER ]-----
class BaseCall(Node):
    "A base class for function calls"
    properties = {
        args: "[Node*] array of arguments"
    }

class Call(BaseCall):
    "A function call expression"
    properties = {
        expression: "[Node] expression to invoke as function"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
            for arg in self.args:
                arg._walk(visitor)
            if self.args.kwargs:
                for arg in self.args.kwargs:
                    arg[0]._walk(visitor)
                    arg[1]._walk(visitor)
            if self.args.kwarg_items:
                for arg in self.args.kwarg_items:
                    arg._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        if isinstance(self.expression, SymbolRef):
            # self is where we get a bit devious, we use scope to infer the return type, if possible
            for scope in reversed(heap):
                exp_name = self.expression.name
                # scope.vars[exp_name][-1] - can be None
                if exp_name in scope.vars and scope.vars[exp_name][-1] and "->" in scope.vars[exp_name][-1]:
                    # local var declarations, return result
                    return scope.vars[exp_name][-1].split('->')[1].trim()
                elif exp_name in scope.functions and scope.functions[exp_name] and "->" in scope.functions[exp_name]:
                    # local function declarations, return result
                    return scope.functions[exp_name].split('->')[1].trim()
                elif scope.type is "function" and exp_name is scope.name and scope.return:
                    # recursion, need to check return_annotation
                    # TODO: refactor self to minimize duplication
                    # helper method for detecting if self is a type annotation, and returning appropriate type
                    parse = def(variable):
                        wrap = {
                            "array": def(value): return "[" + value + "]";,
                            "dict": def(value): return "{String:" + value + "}";,
                            "base": def(value): return value
                        }
                        wrapper = "base"
                        if isinstance(variable, Array):
                            # format: [Item]
                            if variable.elements.length is not 1:
                                # multiple items mentioned in array, not a case we can handle yet
                                return
                            wrapper = "array"
                            element = variable.elements[0]
                        elif isinstance(variable, Call) and isinstance(variable.expression, SymbolRef) and variable.expression.name is 'Array':
                            # format: Array(Item)
                            # alias for [Item]
                            if variable.args.length is not 1:
                                # multiple items mentioned in array, not a case we can handle yet
                                return
                            wrapper = "array"
                            element = variable.args[0]
                        elif isinstance(variable, ObjectLiteral):
                            # format: {Item1:Item2}
                            if variable.properties.length is not 1:
                                # multiple items mentioned in hash, not a case we can handle yet
                                return
                            wrapper = "dict"
                            # key is always a string, ignore it
                            element = variable.properties[0].value
                        elif isinstance(variable, Call) and isinstance(variable.expression, SymbolRef) and variable.expression.name in ['Object', 'Dictionary']:
                            # format: Dictionary(Item2) or Dictionary(String,Item2), in place of Dictionary you can also use Object keyword
                            # both formats are accepted as a convenience feature for developers
                            # alias for {Item1:Item2}
                            if 1 <= variable.args.length <= 2:
                                element = variable.args[-1]
                                wrapper = "dict"
                            else:
                                return
                        else:
                            # format: Item
                            element = variable
                        if isinstance(element, SymbolRef) and element.name in NATIVE_CLASSES:
                            # wrap element in dict/array if needed
                            return wrap[wrapper](element.name)
                        elif isinstance(element, Array) or isinstance(element, ObjectLiteral) or isinstance(element, Call):
                            # potentially nested array/dict (i.e. array of dicts, array of arrays, dict of arrays, etc.)
                            result = parse(element)
                            if result: return wrap[wrapper](result)
                    result = parse(scope.return_annotation)
                    if result: return result
                # TODO: there is still a large set of functions we'll miss, address this later
        return "?"

class ClassCall(BaseCall):
    "A function call expression"
    properties = {
        class: "[string] name of the class method belongs to",
        super: "[boolean] this call can be replaced with a super() call",
        method: "[string] class method being called",
        static: "[boolean] defines whether the method is static"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            if self.expression: self.expression._walk(visitor)
            for arg in self.args:
                arg._walk(visitor)
            for arg in self.args.kwargs:
                arg[0]._walk(visitor)
                arg[1]._walk(visitor)
            for arg in self.args.kwarg_items:
                arg._walk(visitor)
        )

class New(Call): "An object instantiation. Derives from a function call since it has exactly the same properties"

class Seq(Node):
    "A sequence expression (two comma-separated expressions)"
    properties = {
        car: "[Node] first element in sequence",
        cdr: "[Node] second element in sequence"
    }
    def cons(self, x, y):
        seq = new Seq(x)
        seq.car = x
        seq.cdr = y
        return seq

    def from_array(self, array):
        if array.length is 0:
            return None

        if array.length is 1:
            return array[0].clone()

        list = None
        for i in range(array.length-1, -1, -1):
            list = Seq.cons(array[i], list)

        p = list
        while p:
            if p.cdr and not p.cdr.cdr:
                p.cdr = p.cdr.car
                break
            p = p.cdr
        return list

    def to_array(self):
        p = this
        a = []
        while p:
            a.push(p.car)
            if p.cdr and not (isinstance(p.cdr, Seq)):
                a.push(p.cdr)
                break
            p = p.cdr
        return a

    def add(self, node):
        p = this
        while p:
            if not (isinstance(p.cdr, Seq)):
                cell = Seq.cons(p.cdr, node)
                return p.cdr = cell
            p = p.cdr

    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.car._walk(visitor)
            if self.cdr:
                self.cdr._walk(visitor)
        )

class PropAccess(Node):
    'Base class for property access expressions, i.e. `a.foo`, `a["foo"]` or a[1:5]'
    properties = {
        expression: "[Node] the “container” expression",
        property: "[Node|string] the property to access. For Dot this is always a plain string, while for Sub it's an arbitrary Node"
    }

class Dot(PropAccess):
    "A dotted property access expression"
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        # dot access can only unpack hashes
        containerType = self.expression.resolveType(heap)
        if containerType and containerType[0] is '{': return /\{\w+:(.*)\}/.exec(containerType)[1]
        return '?'

class Sub(PropAccess):
    'Index-style property access, i.e. `a["foo"]`'
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
            self.property._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        # index-style access can unpack both hashes and arrays
        containerType = self.expression.resolveType(heap)
        if containerType:
            # unpack the array/hash
            if containerType[0] is '[' and isinstance(self.property, Number): return /\[(.*)\]/.exec(containerType)[1]
            if containerType[0] is '{': return /\{\w+:(.*)\}/.exec(containerType)[1]
        return '?'

class Slice(PropAccess):
    'Index-style property access, i.e. `a[3:5]`'
    properties = {
        property2: "[Node] the 2nd property to access - typically ending index for the array.",
        assignment: "[Node] The data being spliced in."
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
            self.property._walk(visitor)
            self.property2._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        # a slice of an iterable will be of same type as the iterable
        return self.expression.resolveType(heap)

class Unary(Node):
    "Base class for unary expressions"
    properties = {
        operator: "[string] the operator",
        expression: "[Node] expression that this unary operator applies to"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.expression._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        if self.operator is "!": return "Boolean"
        if self.operator in ["-", "+"] and self.expression.resolveType(heap) is "Number": return "Number"
        return "?"

class UnaryPrefix(Unary): "Unary prefix expression i.e. `typeof i` or `++i`"
class UnaryPostfix(Unary): "Unary postfix expression i.e. `i++`"

class Binary(Node):
    "Binary expression, i.e. `a + b`"
    properties = {
        left: "[Node] left-hand side expression",
        operator: "[string] the operator",
        right: "[Node] right-hand side expression"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.left._walk(visitor)
            self.right._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        if not (self.left and self.right):
            return "?"
        left = self.left.resolveType(heap)
        right = self.left.resolveType(heap)
        if left is "Number" and right == "Number": return "Number"
        if left is "Boolean" and right == "Boolean" or self.operator in ['===', '!==', '>', '>=', '<', '<=']:
            return "Boolean" # technically bitwise ops produce numbers here
        if left is "String" and self.operator is "+":
            # FIXME: for now allow this operation, in the future we will complain if types don't match
            return "String"
        return "?"

class Range(Binary):
    "Range node (to/til)"
    @memoized
    def resolveType(self, heap): return "[Number]"

class DeepEquality(Binary):
    "Pythonic deep equality operator"
    @memoized
    def resolveType(self, heap): return "Boolean"

class Conditional(Node):
    "Conditional expression using the ternary operator, i.e. `a ? b : c`"
    properties = {
        condition: "[Node] test to run before deciding the return value",
        consequent: "[Node] return expression in the event on truthy test evaluation",
        alternative: "[Node] return expression in the event of falsy test evaluation"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.condition._walk(visitor)
            self.consequent._walk(visitor)
            self.alternative._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        computedType = self.consequent.resolveType(heap)
        return computedType is self.alternative.resolveType(heap) ? computedType : "?"

class Assign(Binary):
    "An assignment expression — `a = b + 5`"
    @memoized
    def resolveType(self, heap):
        # for chained assignments
        if self.operator is "=":
            return self.right.resolveType(heap)
        return "?"

# -----[ LITERALS ]-----
class Array(Node):
    "An array literal"
    properties = {
        elements: "[Node*] array of elements"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            for el in self.elements:
                el._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        # attempt to extract a consistent type within array
        if not self.elements.length: return "[?]"
        expected = self.elements[0].resolveType(heap)
        if not expected: return "[?]"
        for element in self.elements[1:]:
            current = element.resolveType(heap)
            if current is not expected:
                if expected.indexOf("Function") is 0 and current.indexOf("Function") is 0: return "[Function]" # only the signatures don't match
                return "[?]"
        return "[" + expected + "]"

class TupleUnpack(Node):
    "An object used to represent tuple unpacking"
    properties = {
        elements: "[Node*] array of elements being assigned to",
        right: "[Node] right-hand side expression"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            for el in self.elements:
                el._walk(visitor)
            self.right._walk(visitor)
        )

class ObjectLiteral(Node):
    "An object literal"
    properties = {
        properties: "[ObjectProperty*] array of properties"
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            for prop in self.properties:
                prop._walk(visitor)
        )

    @memoized
    def resolveType(self, heap):
        # attempt to extract a consistent type within hashmap
        # for now we'll assume the key is always a string, because it can't yet be anything else
        if not self.properties.length: return "{String:?}"
        start = 0
        spread = None
        while isinstance(self.properties[start], UnaryPrefix):
            # if proeprties start with spread operators, check them all for consistency, if possible
            spread = self.properties[start].expression.resolveType(heap)
            if "?" in spread: return "{String:?}"
            start += 1

        expected = self.properties[start].value.resolveType(heap)
        if not expected: return "{String:?}"
        for element in self.properties[start+1:]:
            # now loop through remaining properties
            if isinstance(element, UnaryPrefix):
                # another spread operator
                if spread:
                    if spread is not element.expression.resolveType(heap): return "{String:?}"
                else:
                    spread = element.expression.resolveType(heap)
            elif isinstance(element, Accessor):
                # hashmap has getters/setters, ignore for now
                # if it's a setter, it has no return type anyway
                # if it's a getter, chances are it returns same type as objects stored inside (although that may be false)
                pass
            else:
                # regular element
                current = element.value.resolveType(heap)
                if not current:
                    return "{String:?}"
                elif current is not expected:
                    if expected.indexOf("Function") is 0 and current.indexOf("Function") is 0:
                        continue # only the signatures don't match
                    else:
                        return "{String:?}"
        result = "{String:" + expected + "}"
        if spread:
            if spread is result: return result
            else: return "{String:?}"
        return result

class ObjectProperty(Node):
    "Base class for literal object properties"
    properties = {
        key: "[Node] the property name or expression for computed key ",
        value: "[Node] property value. For setters and getters this is an Function.",
    }
    def _walk(self, visitor):
        return visitor._visit(self, def():
            self.key._walk(visitor)
            self.value._walk(visitor)
        )

class ObjectKeyVal(ObjectProperty): "A key: value object property"
class ObjectSetter(Accessor): "An object setter property"
class ObjectGetter(Accessor): "An object getter property"

class Symbol(Node):
    "Base class for all symbols"
    properties = {
        name: "[string] name of this symbol",
        scope: "[Scope/S] the current scope (not necessarily the definition scope)",
        thedef: "[SymbolDef/S] the definition of this symbol"
    }

class SymbolAlias(Symbol): "An alias used in an import statement"

class SymbolDeclaration(Symbol):
    "A declaration symbol (symbol in var/const, function name or argument, symbol in catch)"
    properties = {
        init: "[Node*/S] array of initializers for this declaration."
    }

class SymbolVar(SymbolDeclaration): "Symbol defining a variable"
class SymbolNonlocal(SymbolDeclaration): "A nonlocal declaration"

class ImportedVar(SymbolVar):
    "Symbol defining an imported symbol"
    properties = {
        alias: "SymbolAlias the alias for this imported symbol"
    }

class SymbolConst(SymbolDeclaration): "A constant declaration"

class SymbolFunarg(SymbolVar):
    "Symbol naming a function argument"
    properties = {
        annotation: "[Annotation?] annotation provided for this argument, if any"
    }

class SymbolClass(SymbolDeclaration): "Symbol naming a class expression"
class SymbolDefun(SymbolDeclaration):
    "Symbol defining a function"
    properties = {
        js_reserved: "[boolean/S] If True, the method name must be omitted and defined as anonymous function (does matter in es5 only)"
    }
class SymbolAccessor(SymbolDefun): "The name of a property accessor (setter/getter function)"
class SymbolLambda(SymbolDeclaration): "Symbol naming a function expression"
class SymbolCatch(SymbolDeclaration): "Symbol naming the exception in catch"

class Label(Symbol):
    "Symbol naming a label (declaration)"
    properties = {
        references: "[LabelRef*] a list of nodes referring to this label"
    }

class SymbolRef(Symbol):
    "Reference to some symbol (not definition/declaration)"
    properties = {
        parens: "[boolean/S] if true, this variable is wrapped in parentheses"
    }
    @memoized
    def resolveType(self, heap):
        # self is where we get a bit devious, we use scope to infer the symbol, if possible
        for scope in reversed(heap):
            if self.name in scope.vars:
                return scope.vars[self.name][-1]    # last-assigned type
            if scope.args and self.name in scope.args:
                return scope.args[self.name]
        return "?"

class SymbolClassRef(Symbol):
    "Reference to class symbol"
    properties = {
        class: "[SymbolDeclaration?] the name of this class",
    }

class LabelRef(Symbol): "Reference to a label symbol"
class This(Symbol): "The `this` symbol"

class Constant(Node):
    "Base class for all constants"
    def getValue(self): return this.value

class String(Constant):
    "A string literal"
    properties = {
        value: "[string] the contents of this string",
        modifier: "[string] string type modifier"
    }
    @memoized
    def resolveType(self): return "String"

class Verbatim(Constant):
    "Raw JavaScript code"
    properties = {
        value: "[string] A string of raw JS code"
    }
    @memoized
    def resolveType(self): return '?'

class Number(Constant):
    "A number literal"
    properties = {
        value: "[number] the numeric value"
    }
    @memoized
    def resolveType(self): return "Number"

class Identifier(Constant):
    "An identifier literal, used for unquoted property key"
    properties = {
        value: "[string] the name of this key"
    }
    @memoized
    def resolveType(self): return "String"

class RegExp(Constant):
    "A regexp literal"
    properties = {
        value: "[RegExp] the actual regexp"
    }
    @memoized
    def resolveType(self): return "RegExp"

class Atom(Constant): "Base class for atoms"

class Null(Atom):
    "The `null` atom"
    value = None
    @memoized
    def resolveType(self): return None

class NotANumber(Atom):
    "The impossible value"
    value = 0 / 0
    @memoized
    def resolveType(self): return None

class Undefined(Atom):
    "The `undefined` value"
    value = void 0
    @memoized
    def resolveType(self): return None

class Hole(Atom):
    "A hole in an array"
    value = void 0
    @memoized
    def resolveType(self): return None

class Infinity(Atom):
    "The `Infinity` value"
    value = 1 / 0
    @memoized
    def resolveType(self): return "Number"

class Boolean(Atom):
    "Base class for booleans"
    properties = {
        value: "[boolean] value"
    }
    @memoized
    def resolveType(self): return "Boolean"


# -----[ TreeWalker ]-----
class TreeWalker:

    def __init__(self, callback):
        self.visit = callback
        self.stack = []

    def _visit(self, node, descend):
        self.stack.push(node)
        ret = self.visit(node, (descend ? def(): descend.call(node); : noop))
        if not ret and descend:
            descend.call(node)

        self.stack.pop()
        return ret

    def parent(self, n):
        return self.stack[self.stack.length - 2 - (n or 0)]

    def push(self, node):
        self.stack.push(node)

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

    def self(self):
        return self.stack[self.stack.length - 1]

    def find_parent(self, type):
        stack = self.stack
        for i in range(stack.length-1, -1, -1):
            x = stack[i]
            if isinstance(x, type):
                return x

    def in_boolean_context(self):
        stack = self.stack
        i = stack.length
        self = stack[i -= 1]
        while i > 0:
            p = stack[i -= 1]
            if isinstance(p, If) and p.condition is self
            or isinstance(p, Conditional) and p.condition is self
            or isinstance(p, DWLoop) and p.condition is self
            or isinstance(p, UnaryPrefix) and p.operator is "!" and p.expression is self:
                return True
            if not (isinstance(p, Binary) and (p.operator is "&&" or p.operator is "||")):
                return False
            self = p

    def loopcontrol_target(self, label):
        stack = self.stack
        if label:
            for i in range(stack.length-1, -1, -1):
                x = stack[i]
                if isinstance(x, LabeledStatement) and x.label.name is label.name:
                    return x.body
        else:
            for i in range(stack.length-1, -1, -1):
                x = stack[i]
                if isinstance(x, Switch) or isinstance(x, ForIn) or isinstance(x, DWLoop):
                    return x