<commit_before>'''Perform semantic validation of a syntactically valid AST.

The typechecker module validates trees of AST nodes generated by the parser.

The tree_is_valid() function takes the ast root node as an argument, and returns
True if there are no semantic errors in the tree. If any errors are encountered,
they are printed and False is returned.
'''

import syntaxtree
import tokens

class TypeCheckError(Exception):
    def __init__(self, msg, token=None):
        self.msg = msg
        self.token = token
    
    def __str__(self):
        if self.token:
            underline = '^' if self.token.start == self.token.end else '~'
            line = self.token.line.rstrip()
            return ('Error on line %s: %s\n'
                    '    %s\n'
                    '    %s') % (self.token.lineno, self.msg, line,
                                 ''.join((underline if self.token.start <= i <= self.token.end else ' ')
                                            for i in xrange(len(line))))
        else:
            return self.msg
            
    def __repr__(self):
        return 'TypeCheckError(msg=%r, token=%r)' % (self.msg, self.token)

class _Checker(syntaxtree.TreeWalker):
    def __init__(self):
        super(_Checker, self).__init__()
        
        self.global_scope = {}
        self.scopes = [{}]
        
        self.error_encountered = False
        
        self.visit_functions = {
            syntaxtree.Program:self.visit_program,
            syntaxtree.Assign:self.visit_assign,
            syntaxtree.ProcDecl:self.visit_procdecl,
            syntaxtree.Call:self.visit_call,
        }
        
        self.leave_functions = {
            syntaxtree.ProcDecl:self.leave_procdecl,
        }
        
    def report_error(self, err):
        self.error_encountered = True
        print err

    def enter_scope(self):
        self.scopes.append({})

    def leave_scope(self):
        self.scopes.pop()

    def define_variable(self, name, value, is_global=False):
        if is_global:
            scope = self.global_scope
        else:
            scope = self.scopes[-1]

        if name in scope:
            self.report_error(TypeCheckError('Name %r already defined' % name, name.token))
        
        if isinstance(value, syntaxtree.VarDecl) and value.array_length is not None:
            # Record the declaration even if it's incorrect, so that we don't
            # generate spurious error when the name is referenced.
            array_length_type = self.get_type(value.array_length)
            if array_length_type != tokens.INT:
                self.report_error(TypeCheckError('Size of array has non-integer type %r' % array_length_type, value.array_length.token))
        scope[name] = value

    def get_decl(self, name):
        try:
            return self.scopes[-1][name]
        except KeyError:
            try:
                return self.global_scope[name]
            except KeyError:
                raise TypeCheckError('Undefined identifier %r' % name, name.token)
            
    def get_type(self, node):
        if isinstance(node, syntaxtree.BinaryOp):
            type = self.unify_node_types(node.left, node.right)
            if type != tokens.INT and node.op in (tokens.AND, tokens.OR, tokens.NOT):
                raise TypeCheckError('Bitwise operators only valid on integers, not %r' % type, node.token)
            elif type not in (tokens.INT, tokens.FLOAT):
                raise TypeCheckError('Operator %r only valid on numbers' % node.op, node.token)
            return type
            
        if isinstance(node, syntaxtree.UnaryOp):
            return self.get_type(node.operand)
        
        if isinstance(node, syntaxtree.Num):
            return tokens.FLOAT if '.' in node.n else tokens.INT
        
        if isinstance(node, syntaxtree.Name):
            return self.get_decl(node).type
        
        if isinstance(node, syntaxtree.Subscript):
            decl = self.get_decl(node.name)
            if not isinstance(decl, syntaxtree.VarDecl) or decl.array_length is None:
                raise TypeCheckError('Subscripted value is not an array', node.token)
            if self.get_type(node.index) != tokens.INT:
                raise TypeCheckError('Array index is not an integer', node.token)
            return decl.type
        
        if isinstance(node, syntaxtree.Str):
            return tokens.STRING_TYPE
        
        raise TypeCheckError('Unknown type', node.token)
        
    def unify_node_types(self, node_a, node_b):
        # This complicated chunk of error handling allows us to print errors for
        # both nodes in order.
        try:
            type_a = self.get_type(node_a)
        except TypeCheckError as err:
            try:
                type_b = self.get_type(node_b)
            except TypeCheckError as err2:
                self.report_error(err)
                raise err2
            else:
                raise err
        else:
            type_b = self.get_type(node_b)
        
        try:
            return self.unify_types(type_a, type_b)
        except TypeCheckError:
            # Improve the error printout a little by giving the output a better range
            if node_a.token is not None and node_b.token is not None:
                token = node_a.token._replace(end=node_b.token.end)
            else:
                token = node_a.token
            raise TypeCheckError('Incompatible types %r and %r' % (type_a, type_b), token)
        
    def unify_types(self, type_a, type_b):
        # The error in this expression was already reported, don't report
        # extraneous errors.
        if None in (type_a, type_b):
            return None
        
        if type_a == tokens.BOOL:
            type_a = tokens.INT
        if type_b == tokens.BOOL:
            type_b = tokens.INT
        
        if type_a == type_b:
            return type_a
        
        if set((type_a, type_b)) == set((tokens.INT, tokens.FLOAT)):
            return tokens.FLOAT
        
        raise TypeCheckError('Incompatible types %r and %r' % (type_a, type_b))
    
    def visit_program(self, node):
        for decl in node.decls:
            self.define_variable(decl.name, decl, decl.is_global)

    def visit_call(self, node):
        try:
            proc_decl = self.get_decl(node.func)
        except TypeCheckError as err:
            self.report_error(err)
        else:
            if len(node.args) != len(proc_decl.params):
                self.report_error(TypeCheckError('Procedure %r takes exactly %s arguments (%s given)' %
                                 (node.func.id, len(proc_decl.params), len(node.args)), node.token))
            
            for arg, param in zip(node.args, proc_decl.params):
                if param.direction == tokens.OUT and not isinstance(arg, syntaxtree.Name):
                    self.report_error(TypeCheckError('Argument to out parameter must be an identifier.', arg.token))
                
                try:
                    argtype = self.get_type(arg)
                except TypeCheckError as err:
                    self.report_error(err)
                else:
                    try:
                        self.unify_types(argtype, param.var_decl.type)
                    except TypeCheckError:
                        self.report_error(TypeCheckError('Argument type %r does not match parameter type %r' %
                                          (argtype, param.var_decl.type), arg.token))
                
    def visit_assign(self, node):
        try:
            self.unify_node_types(node.target, node.value)
        except TypeCheckError as err:
            self.report_error(err)
    
    def visit_procdecl(self, node):
        self.enter_scope()
        # Add procedure name to scope to allow recursion.
        self.define_variable(node.name, node)
        # Add local variables to scope.
        for decl in node.decls:
            if decl.is_global:
                self.report_error(TypeCheckError('Can only declare global identifiers at top level scope.', decl.name.token))
            self.define_variable(decl.name, decl)
        # Add parameters to scope.
        for param in node.params:
            self.define_variable(param.var_decl.name, param)
            <commit_msg>Added type checking of parameters.<commit_after>'''Perform semantic validation of a syntactically valid AST.

The typechecker module validates trees of AST nodes generated by the parser.

The tree_is_valid() function takes the ast root node as an argument, and returns
True if there are no semantic errors in the tree. If any errors are encountered,
they are printed and False is returned.
'''

import syntaxtree
import tokens

class TypeCheckError(Exception):
    def __init__(self, msg, token=None):
        self.msg = msg
        self.token = token
    
    def __str__(self):
        if self.token:
            underline = '^' if self.token.start == self.token.end else '~'
            line = self.token.line.rstrip()
            return ('Error on line %s: %s\n'
                    '    %s\n'
                    '    %s') % (self.token.lineno, self.msg, line,
                                 ''.join((underline if self.token.start <= i <= self.token.end else ' ')
                                            for i in xrange(len(line))))
        else:
            return self.msg
            
    def __repr__(self):
        return 'TypeCheckError(msg=%r, token=%r)' % (self.msg, self.token)

class _Checker(syntaxtree.TreeWalker):
    def __init__(self):
        super(_Checker, self).__init__()
        
        self.global_scope = {}
        self.scopes = [{}]
        
        self.error_encountered = False
        
        self.visit_functions = {
            syntaxtree.Program:self.visit_program,
            syntaxtree.Assign:self.visit_assign,
            syntaxtree.ProcDecl:self.visit_procdecl,
            syntaxtree.Call:self.visit_call,
        }
        
        self.leave_functions = {
            syntaxtree.ProcDecl:self.leave_procdecl,
        }
        
    def report_error(self, err):
        self.error_encountered = True
        print err

    def enter_scope(self):
        self.scopes.append({})

    def leave_scope(self):
        self.scopes.pop()

    def define_variable(self, name, value, is_global=False):
        if is_global:
            scope = self.global_scope
        else:
            scope = self.scopes[-1]

        if name in scope:
            self.report_error(TypeCheckError('Name %r already defined' % name, name.token))
        
        if isinstance(value, syntaxtree.VarDecl) and value.array_length is not None:
            # Record the declaration even if it's incorrect, so that we don't
            # generate spurious error when the name is referenced.
            array_length_type = self.get_type(value.array_length)
            if array_length_type != tokens.INT:
                self.report_error(TypeCheckError('Size of array has non-integer type %r' % array_length_type, value.array_length.token))
        scope[name] = value

    def get_decl(self, name):
        if isinstance(name, syntaxtree.Name):
            key = name
        elif isinstance(name, syntaxtree.Subscript):
            key = name.name
        else:
            raise TypeCheckError('%r must be an identifier' % name, name.token)
        
        try:
            return self.scopes[-1][key]
        except KeyError:
            try:
                return self.global_scope[key]
            except KeyError:
                raise TypeCheckError('Undefined identifier %r' % key, key.token)
            
    def get_type(self, node):
        if isinstance(node, syntaxtree.BinaryOp):
            type = self.unify_node_types(node.left, node.right)
            if type != tokens.INT and node.op in (tokens.AND, tokens.OR, tokens.NOT):
                raise TypeCheckError('Bitwise operators only valid on integers, not %r' % type, node.token)
            elif type not in (tokens.INT, tokens.FLOAT):
                raise TypeCheckError('Operator %r only valid on numbers' % node.op, node.token)
            return type
            
        if isinstance(node, syntaxtree.UnaryOp):
            return self.get_type(node.operand)
        
        if isinstance(node, syntaxtree.Num):
            return tokens.FLOAT if '.' in node.n else tokens.INT
        
        if isinstance(node, syntaxtree.Name):
            decl = self.get_decl(node)
            if isinstance(decl, syntaxtree.Param):
                if decl.direction != tokens.IN:
                    raise TypeCheckError('Cannot read from out parameter', node.token)
                return decl.var_decl.type
            return decl.type
        
        if isinstance(node, syntaxtree.Subscript):
            decl = self.get_decl(node.name)
            if not isinstance(decl, syntaxtree.VarDecl) or decl.array_length is None:
                raise TypeCheckError('Subscripted value is not an array', node.token)
            if self.get_type(node.index) != tokens.INT:
                raise TypeCheckError('Array index is not an integer', node.token)
            return decl.type
        
        if isinstance(node, syntaxtree.Str):
            return tokens.STRING_TYPE
        
        raise TypeCheckError('Unknown type', node.token)
        
    def unify_node_types(self, node_a, node_b):
        # This complicated chunk of error handling allows us to print errors for
        # both nodes in order.
        try:
            type_a = self.get_type(node_a)
        except TypeCheckError as err:
            try:
                type_b = self.get_type(node_b)
            except TypeCheckError as err2:
                self.report_error(err)
                raise err2
            else:
                raise err
        else:
            type_b = self.get_type(node_b)
        
        try:
            return self.unify_types(type_a, type_b)
        except TypeCheckError:
            # Improve the error printout a little by giving the output a better range
            if node_a.token is not None and node_b.token is not None:
                token = node_a.token._replace(end=node_b.token.end)
            else:
                token = node_a.token
            raise TypeCheckError('Incompatible types %r and %r' % (type_a, type_b), token)
        
    def unify_types(self, type_a, type_b):
        if type_a == tokens.BOOL:
            type_a = tokens.INT
        if type_b == tokens.BOOL:
            type_b = tokens.INT
        
        if type_a == type_b:
            return type_a
        
        if set((type_a, type_b)) == set((tokens.INT, tokens.FLOAT)):
            return tokens.FLOAT
        
        raise TypeCheckError('Incompatible types %r and %r' % (type_a, type_b))
    
    def visit_program(self, node):
        for decl in node.decls:
            self.define_variable(decl.name, decl, decl.is_global)

    def visit_call(self, node):
        try:
            proc_decl = self.get_decl(node.func)
        except TypeCheckError as err:
            self.report_error(err)
        else:
            if len(node.args) != len(proc_decl.params):
                self.report_error(TypeCheckError('Procedure %r takes exactly %s arguments (%s given)' %
                                 (node.func.id, len(proc_decl.params), len(node.args)), node.token))
            
            for arg, param in zip(node.args, proc_decl.params):
                if param.direction == tokens.OUT and not isinstance(arg, syntaxtree.Name):
                    self.report_error(TypeCheckError('Argument to out parameter must be an identifier.', arg.token))
                
                try:
                    argtype = self.get_type(arg)
                except TypeCheckError as err:
                    self.report_error(err)
                else:
                    try:
                        self.unify_types(argtype, param.var_decl.type)
                    except TypeCheckError:
                        self.report_error(TypeCheckError('Argument type %r does not match parameter type %r' %
                                          (argtype, param.var_decl.type), arg.token))
                
    def visit_assign(self, node):
        try:
            # node.target is guaranteed by the parser to be a Name node.
            target_decl = self.get_decl(node.target)
            if isinstance(target_decl, syntaxtree.Param):
                if target_decl.direction == tokens.IN:
                    self.report_error(TypeCheckError('Cannot assign to input parameter', node.target.token))
                self.unify_types(target_decl.var_decl.type, self.get_type(node.value))
            else:
                self.unify_node_types(node.target, node.value)
        except TypeCheckError as err:
            self.report_error(err)
    
    def visit_procdecl(self, node):
        self.enter_scope()
        # Add procedure name to scope to allow recursion.
        self.define_variable(node.name, node)
        # Add local variables to scope.
        for decl in node.decls:
            if decl.is_global:
                self.report_error(TypeCheckError('Can only declare global identifiers at top level scope.', decl.name.token))
            self.define_variable(decl.name, decl)
        # Add parameters to scope.
        for param in node.params:
            self.define_variable(param.var_decl.name, param)
            
{'fraction_non_alphanumeric': 0.08606088349736782, 'fraction_numerical': 0.00045777065690089265, 'mean_word_length': 1.7684143830191668, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1311808', 'n_tokens_mistral': 4848, 'n_tokens_neox': 4743, 'n_words': 1281}