il_gen.py

""" Objects used for the AST -> IL phase of the compiler """

import il_cmds.control as control_cmds
from collections import namedtuple
from errors import CompilerError
from ctypes import CType
from copy import copy


class ILCode:
    """Stores the IL code generated from the AST.
        commands - Dictionary mapping function name to list of IL commands for that function.
        cur_func (str) - Name of the function current commands are for.
        label_num (int) - Unique identifier returned by get_label.
    """

    def __init__(self):
        """ Initialize IL code """
        self.commands = {}
        self.cur_func = None
        self.label_num = 0

        self.static_inits, self.literals, self.string_literals = {}, {}, {}

    def copy(self):
        """Make copy of this object. Preserves identity of all ILValues stored within, but modifying the commands,
        literals, etc. in the returned object does not modify the original.
        """
        new = ILCode()
        new.commands = {name: self.commands[name].copy() for name in self.commands}
        new.cur_func = self.cur_func
        self.label_num = self.label_num
        self.static_inits = self.static_inits.copy()
        self.literals = self.literals.copy()
        self.string_literals = self.string_literals.copy()
        return new

    def start_func(self, func):
        """ Start a new function in the IL code. Call start_func before generating code for a new function """
        self.cur_func = func
        self.commands[func] = []

    def add(self, command):
        """Add a new command to the IL code.
            command (ILCommand) - command to be added.
        """
        self.commands[self.cur_func].append(command)

    def always_returns(self):
        """ Return true if this function ends in a return command """
        return self.commands[self.cur_func] and isinstance(self.commands[self.cur_func][-1], control_cmds.Return)

    def register_literal_var(self, il_value, value):
        """Register a literal IL value.
            il_value - ILValue object that has a literal value.
            value - Literal value to store in the ILValue.
        """
        il_value.literal = IntegerLiteral(value)
        self.literals[il_value] = value

    def register_string_literal(self, il_value, chars):
        """Register a string literal IL value.
            chars (List(int)) - Null-terminated list of character ASCII codes in the string.
        """
        il_value.literal = StringLiteral(chars)
        self.string_literals[il_value] = chars

    def static_initialize(self, il_value, init_val):
        """Initialize given value statically before program execution begins.
            il_value - ILValue object to initialize.
            init_val - Numeric value to initialize `il_value` to.
        """
        self.static_inits[il_value] = init_val

    @staticmethod
    def get_label():
        """ Return a unique label identifier string """
        # Kind of tricky. Ideally, we would return labels here that were unique to the ILCode, and then when generating
        # the ASM code, assign each ILCode label to an ASM code label.

        # Import is here to prevent circular import.
        from asm_gen import ASMCode
        return ASMCode.get_label()


class ILValue:
    """ Value that appears as an element in generated IL code.
        ctype (CType) - C type of this value.
        literal_val - the value of this IL value if it represents a literal value. 
    """

    def __init__(self, ctype, null_ptr_const=False):
        """ Initialize IL value """
        self.null_ptr_const = null_ptr_const
        self.ctype = ctype
        self.literal = None

    def __str__(self):
        return f'{id(self) % 1000:03}'

    def __repr__(self):
        return str(self)


class Literal:
    """ Base class for integer literals, string literals, etc """
    def __init__(self, val):
        self.val = val


class IntegerLiteral(Literal):
    """ Class for integer literals """
    def __init__(self, val):
        super().__init__(int(val))


class StringLiteral(Literal):
    """ Class for string literals """
    def __init__(self, val):
        super().__init__(str(val))


class SymbolTable:
    """Symbol table for the IL -> AST phase.
    This object stores variable name and types, and is mostly used for type checking.
    """

    Tables = namedtuple('Tables', ['vars', 'structs'])

    # Definition statuses
    UNDEFINED = 1
    TENTATIVE = 2
    DEFINED = 3

    # Linkages
    INTERNAL = 1
    EXTERNAL = 2

    # Storage durations
    STATIC = 1
    AUTOMATIC = 2

    def __init__(self):
        """Initialize symbol table.
            tables - list of namedtuples of dictionaries. Each dictionary in the namedtuple is the symbol table for a
            different namespace.
        """
        self.tables = []

        # Store variable linkages
        # ILValue -> INTERNAL / EXTERNAL
        self.linkage_type = {}

        # INTERNAL/EXTERNAL -> name -> ILValue
        self.linkages = {self.INTERNAL: {}, self.EXTERNAL: {}}

        # Store variable definition states
        # ILValue -> DEFINED/UNDEFINED/TENTATIVE
        self.def_state = {}

        # Store variable storage durations
        # ILValue -> STATIC/AUTOMATIC/None
        self.storage = {}

        # Store the names of all IL values.
        # ILValue -> name
        self.names = {}

        self.new_scope()

    def new_scope(self):
        """ Initialize a new scope for the symbol table """
        self.tables.append(self.Tables(dict(), dict()))

    def end_scope(self):
        """ End the most recently started scope """
        self.tables.pop()

    def lookup_raw(self, name):
        """Look up the variable identifier with the given name. This function returns None if not found.
            name (str) - Identifier name to search for.
        """
        for table, _ in self.tables[::-1]:
            if name in table:
                return table[name]

    def lookup_variable(self, identifier):
        """Look up the given identifier. This function returns the ILValue object for the identifier, or raises an
        exception if not found or if the identifier is a typedef.
            identifier (Token(Identifier)) - Identifier to look up.
        """
        ret = self.lookup_raw(identifier.content)
        if ret and isinstance(ret, ILValue):
            return ret
        else:
            descr = f"use of undeclared identifier '{identifier.content}'"
            raise CompilerError(descr, identifier.r)

    def lookup_linkage(self, identifier):
        """ Return the linkage of identifier. If identifier doesn't exist or has no linkage, returns None """
        return self.linkage_type.get(self.lookup_raw(identifier.content))

    def add_variable(self, identifier, ctype, defined, linkage, storage):
        """Add an identifier with the given name and type to the symbol table.
            identifier (Token) - Identifier to add, for error purposes.
            ctype (CType) - C type of the identifier we're adding.
            defined - one of DEFINED, UNDEFINED, or TENTATIVE.
            linkage - one of INTERNAL, EXTERNAL, or None.
            storage - STATIC, AUTOMATIC, or None.
            return (ILValue) - the ILValue added.
        """
        name = identifier.content

        # if it's already declared in this scope
        if name in self.tables[-1].vars:
            var = self.tables[-1].vars[name]
            if isinstance(var, CType):
                err = f"redeclared type definition '{name}' as variable"
                raise CompilerError(err, identifier.r)
            if defined == self.def_state[var] == self.DEFINED:
                raise CompilerError(f"redefinition of '{name}'", identifier.r)
            if linkage != self.linkage_type.get(var, None):
                err = f"redeclared '{name}' with different linkage"
                raise CompilerError(err, identifier.r)
        elif linkage and name in self.linkages[linkage]:
            var = self.linkages[linkage][name]
        else:
            var = ILValue(ctype)

        # Verify new type is compatible with previous type (if there was one)
        if not var.ctype.compatible(ctype):
            err = f"redeclared '{name}' with incompatible type"
            raise CompilerError(err, identifier.r)
        else:
            # Update type of stored variable (in case this declaration completed an object type)
            var.ctype = ctype

        self.tables[-1].vars[name] = var

        # Set this variable's linkage if it has one
        if linkage:
            self.linkages[linkage][name] = var
            self.linkage_type[var] = linkage

        self.def_state[var] = max(self.def_state.get(var, 0), defined)

        # If this variable has not been assigned a storage duration, or the previous storage duration was None, 
        # assign it this storage duration.
        if not self.storage.get(var, None): self.storage[var] = storage

        self.names[var] = name
        return var

    def lookup_struct(self, tag):
        """ Look up struct by tag name and return its ctype object. If not found, returns None """
        for _, structs in self.tables[::-1]:
            if tag in structs: return structs[tag]

    def add_struct(self, tag, ctype):
        """Add struct to the symbol table and return it. If struct already exists in the topmost scope, this function
        does not modify the symbol table and just returns the existing struct ctype. Otherwise, this function adds this
        struct to the topmost scope and returns it.
        """
        if tag not in self.tables[-1].structs: self.tables[-1].structs[tag] = ctype

        return self.tables[-1].structs[tag]

    def add_typedef(self, identifier, ctype):
        """ Add a type definition to the symbol table """

        name = identifier.content
        if name in self.tables[-1].vars:
            old_ctype = self.tables[-1].vars[name]
            if isinstance(old_ctype, ILValue):
                err = f"'{name}' redeclared as type definition in same scope"
                raise CompilerError(err, identifier.r)
            elif not old_ctype.compatible(ctype):
                err = f"'{name}' redeclared as incompatible type in same scope"
                raise CompilerError(err, identifier.r)
            else:
                return

        self.tables[-1].vars[name] = ctype

    def lookup_typedef(self, identifier):
        """ Look up a typedef from the symbol table. If not found, raises an exception """
        ctype = self.lookup_raw(identifier.content)
        if isinstance(ctype, CType):
            return ctype
        else:
            # This exception is only raised when the parser symbol table makes an error, and this only happens when
            # there is another error in the source anyway. For example, consider this:
            #
            # int A;
            # {
            #   static typedef int A;
            #   A a;
            # }
            #
            # The parser symbol table will naively think that A is a typedef on the line `A a`, when in fact the IL gen
            # step will still classify it as an integer because the `static typedef int A;` is not a valid declaration.
            # In this case, we raise the error below.
            err = f"use of undeclared type definition '{identifier.content}'"
            raise CompilerError(err, identifier.r)


class Context:
    """Object for passing current context to make_il functions.
        break_label - Label to which a `break` statement in the current position would jump.
        continue_label - Label to which a `continue` statement in the current position would jump.
        is_global - Whether the current scope is global or within a function.
    Used by declarations to modify emitted code.
    """

    def __init__(self):
        """ Initialize Context """
        self.break_label = None
        self.continue_label = None
        self.return_type = None
        self.is_global = False

    def set_global(self, val):
        """ Return copy of self with is_global set to given value """
        c = copy(self)
        c.is_global = val
        return c

    def set_break(self, lab):
        """ Return copy of self with break_label set to given value """
        c = copy(self)
        c.break_label = lab
        return c

    def set_continue(self, lab):
        """ Return copy of self with break_label set to given value """
        c = copy(self)
        c.continue_label = lab
        return c

    def set_return(self, ctype):
        """ Return copy of self with return_type set to given value """
        c = copy(self)
        c.return_type = ctype
        return c