gistfile1.c

/*
 * semant.c -- semantic analysis
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "utils.h"
#include "sym.h"
#include "temp/temp.h"
#include "frame/frame.h"
#include "absyn.h"
#include "types.h"
#include "table.h"
#include "semant.h"
#include "utils.h"


static bool showLocalTables;

static Type *voidType;
static Type *intType;
static Type *boolType;


static void shouldNotReach(char *nodeName) {
  error("semantic check should not reach '%s' node", nodeName);
}


/**************************************************************/


static Type *checkNode(Absyn *node, Table *table, int pass,
                       Type *rtype, bool breakAllowed);


static Type *checkTy(Absyn *node, Table *table, int pass,
                     Type *rtype, bool breakAllowed) {
  Type *type;

  switch (node->u.ty.code) {
    case ABSYN_TY_VOID:
      type = voidType;
      break;
    case ABSYN_TY_INT:
      type = intType;
      break;
    case ABSYN_TY_BOOL:
      type = boolType;
      break;
    default:
      error("unknown type code %d in checkTy", node->u.ty.code);
  }
  return type;
}


static ParamTypes *checkParams(Absyn *node, Table *table, int pass,
                               Type *rtype, bool breakAllowed) {
  Absyn *param;
  Absyn *next;
  Type *type;

  if (node->u.decList.isEmpty) {
    return emptyParamTypes();
  }
  param = node->u.decList.head;
  next = node->u.decList.tail;
  type = checkNode(param, table, pass,
                   rtype, breakAllowed);
  return newParamTypes(type,
                       checkParams(next, table, pass,
                                   rtype, breakAllowed));
}


static Type *checkFuncDec(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Table *localTable;
  Type *returnType;
  ParamTypes *paramTypes;
  Entry *funcEntry;
  F_frame *frame;
  U_boolList *formals, *last;
  /* params */
  Absyn *params;
  Absyn *param;
  Type *paramType;
  Entry *paramEntry;
  int numParams;
  int n;
  /* locals */
  Absyn *locals;
  Absyn *local;
  Type *localType;
  Entry *localEntry;
  int numLocals;

  if (pass == 1) {
    /* build and enter func declaration into symbol table */
    returnType = checkNode(node->u.funcDec.rtype, table, 1,
                           rtype, breakAllowed);
    paramTypes = checkParams(node->u.funcDec.params, table, 1,
                             rtype, breakAllowed);
    localTable = newTable(table);
    funcEntry = newFuncEntry(returnType, paramTypes, localTable);
    if (enter(table, node->u.funcDec.name, funcEntry) == NULL) {
      error("redeclaration of '%s' in line %d",
            symToString(node->u.funcDec.name), node->line);
    }
  } else {
    /* get the proc declaration entered in pass 1 again */
    funcEntry = lookup(table, node->u.funcDec.name);
    if (funcEntry == NULL || funcEntry->kind != ENTRY_KIND_FUNC) {
      error("procedure declaration vanished from symbol table");
    }
    localTable = funcEntry->u.funcEntry.localTable;
    /* determine number of parameters */
    params = node->u.funcDec.params;
    numParams = 0;
    while (!params->u.decList.isEmpty) {
      params = params->u.decList.tail;
      numParams++;
    }
    funcEntry->u.funcEntry.numParams = numParams;
    /* enter parameters into local symbol table */
    params = node->u.funcDec.params;
    paramTypes = funcEntry->u.funcEntry.paramTypes;
    n = 0;
    formals = U_boolList(false, NULL);
    last = formals;
    while (!params->u.decList.isEmpty) {
      param = params->u.decList.head;
      params = params->u.decList.tail;
      paramType = paramTypes->type;
      paramTypes = paramTypes->next;
      paramEntry = newVarEntry(paramType, n - 2 - numParams);
      if (enter(localTable, param->u.parDec.name, paramEntry) == NULL) {
        error("redeclaration of '%s' in line %d",
              symToString(param->u.parDec.name), node->line);
      }
      /* Build parameter list for frame */
      last->tail = U_boolList(false, NULL);
      last = last->tail;
      n++;
    }    
    
    /* Generate frame for function */
    funcEntry->u.funcEntry.frame = F_newFrame(node->u.funcDec.name, formals);
    
    /* enter local declarations into local symbol table */
    locals = node->u.funcDec.locals;
    numLocals = 0;
    while (!locals->u.decList.isEmpty) {
      local = locals->u.decList.head;
      locals = locals->u.decList.tail;
      localType = checkNode(local, localTable, 2,
                            funcEntry->u.funcEntry.returnType, breakAllowed);
      localEntry = newVarEntry(localType, numLocals);
      if (enter(localTable, local->u.varDec.name, localEntry) == NULL) {
        error("redeclaration of '%s' in line %d",
              symToString(param->u.varDec.name), node->line);
      }
      
      /* Allocate local variable in register */
      localEntry->u.varEntry.access = F_allocLocal(funcEntry->u.funcEntry.frame, false);
      numLocals++;
    }
    funcEntry->u.funcEntry.numLocals = numLocals;
    /* do semantic check on procedure body */
    checkNode(node->u.funcDec.body, localTable, 2,
              funcEntry->u.funcEntry.returnType, breakAllowed);
    /* show symbol table if requested */
    if (showLocalTables) {
      printf("symbol table at end of procedure '%s':\n",
             symToString(node->u.funcDec.name));
      showTable(localTable);
    }
  }  
  return voidType;
}


static Type *checkParDec(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  Type *type;

  type = checkNode(node->u.parDec.ty, table, pass,
                   rtype, breakAllowed);
  return type;
}


static Type *checkVarDec(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  Type *type;

  type = checkNode(node->u.varDec.ty, table, pass,
                   rtype, breakAllowed);
  return type;
}


static Type *checkEmptyStm(Absyn *node, Table *table, int pass,
                           Type *rtype, bool breakAllowed) {
  return voidType;
}


static Type *checkCompStm(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  checkNode(node->u.compStm.stms, table, pass,
            rtype, breakAllowed);
  return voidType;
}


static Entry *getVar(Table *table, Sym *name, int line) {
  Entry *entry;

  entry = lookup(table, name);
  if (entry == NULL) {
    error("undefined variable '%s' in line %d",
          symToString(name), line);
  }
  if (entry->kind != ENTRY_KIND_VAR) {
    error("'%s' is not a variable in line %d",
          symToString(name), line);
  }
  return entry;
}


static Type *checkAssignStm(Absyn *node, Table *table, int pass,
                            Type *rtype, bool breakAllowed) {
  Entry *entry;
  Type *varType;
  Type *expType;

  entry = getVar(table, node->u.assignStm.name, node->line);
  varType = entry->u.varEntry.type;
  expType = checkNode(node->u.assignStm.exp, table, pass,
                      rtype, breakAllowed);
  if (varType != expType) {
    error("assignment has different LHS and RHS types in line %d",
          node->line);
  }
  return voidType;
}


static Type *checkIfStm1(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  Type *testType;

  testType = checkNode(node->u.ifStm1.test, table, pass,
                       rtype, breakAllowed);
  if (testType != boolType) {
    error("'if' test expression must be of type boolean in line",
          node->line);
  }
  checkNode(node->u.ifStm1.thenPart, table, pass,
            rtype, breakAllowed);
  return voidType;
}


static Type *checkIfStm2(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  Type *testType;

  testType = checkNode(node->u.ifStm2.test, table, pass,
                       rtype, breakAllowed);
  if (testType != boolType) {
    error("'if' test expression must be of type boolean in line",
          node->line);
  }
  checkNode(node->u.ifStm2.thenPart, table, pass,
            rtype, breakAllowed);
  checkNode(node->u.ifStm2.elsePart, table, pass,
            rtype, breakAllowed);
  return voidType;
}


static Type *checkWhileStm(Absyn *node, Table *table, int pass,
                           Type *rtype, bool breakAllowed) {
  Type *testType;

  testType = checkNode(node->u.whileStm.test, table, pass,
                       rtype, true);
  if (testType != boolType) {
    error("'while' test expression must be of type boolean in line",
          node->line);
  }
  checkNode(node->u.whileStm.body, table, pass,
            rtype, true);
  return voidType;
}


static Type *checkDoStm(Absyn *node, Table *table, int pass,
                        Type *rtype, bool breakAllowed) {
  Type *testType;

  testType = checkNode(node->u.doStm.test, table, pass,
                       rtype, true);
  if (testType != boolType) {
    error("'do' test expression must be of type boolean in line",
          node->line);
  }
  checkNode(node->u.doStm.body, table, pass,
            rtype, true);
  return voidType;
}


static Type *checkBreakStm(Absyn *node, Table *table, int pass,
                           Type *rtype, bool breakAllowed) {
  if (!breakAllowed) {
    error("misplaced 'break' in line %d", node->line);
  }
  return voidType;
}


static Type *checkCallStm(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Entry *entry;
  ParamTypes *parameterTypes;
  Absyn *argumentExprs;
  Type *parameterType;
  Absyn *argumentExpr;
  Type *argumentType;
  int argNum;

  entry = lookup(table, node->u.callStm.name);
  if (entry == NULL) {
    error("undefined function '%s' in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  if (entry->kind != ENTRY_KIND_FUNC) {
    error("call of non-function '%s' in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  parameterTypes = entry->u.funcEntry.paramTypes;
  argumentExprs = node->u.callStm.args;
  argNum = 1;
  while (!parameterTypes->isEmpty && !argumentExprs->u.expList.isEmpty) {
    parameterType = parameterTypes->type;
    argumentExpr = argumentExprs->u.expList.head;
    argumentType = checkNode(argumentExpr, table, pass,
                             rtype, breakAllowed);
    if (parameterType != argumentType) {
      error("procedure '%s' argument %d type mismatch in line %d",
            symToString(node->u.callStm.name), argNum, node->line);
    }
    parameterTypes = parameterTypes->next;
    argumentExprs = argumentExprs->u.expList.tail;
    argNum++;
  }
  if (!parameterTypes->isEmpty) {
    error("procedure '%s' called with too few arguments in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  if (!argumentExprs->u.expList.isEmpty) {
    error("procedure '%s' called with too many arguments in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  return voidType;
}


static Type *checkRetStm(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  if (rtype == NULL) {
    error("misplaced 'return' in line %d", node->line);
  }
  if (rtype != voidType) {
    error("return in line %d must not return any value",
          node->line);
  }
  return voidType;
}


static Type *checkRetExpStm(Absyn *node, Table *table, int pass,
                            Type *rtype, bool breakAllowed) {
  Type *type;

  type = checkNode(node->u.retExpStm.exp, table, pass,
                   rtype, breakAllowed);
  if (rtype == NULL) {
    error("misplaced 'return' in line %d", node->line);
  }
  if (rtype != type) {
    error("return type in line %d does not match function declaration",
          node->line);
  }
  return voidType;
}


static Type *checkBinopExp(Absyn *node, Table *table, int pass,
                           Type *rtype, bool breakAllowed) {
  Type *leftType;
  Type *rightType;
  Type *type;

  leftType = checkNode(node->u.binopExp.left, table, pass,
                       rtype, breakAllowed);
  rightType = checkNode(node->u.binopExp.right, table, pass,
                        rtype, breakAllowed);
  switch (node->u.binopExp.op) {
    case ABSYN_BINOP_LOR:
    case ABSYN_BINOP_LAND:
      if (leftType != boolType || rightType != boolType) {
        error("logical operation requires boolean operands in line %d",
              node->line);
      }
      type = boolType;
      break;
    case ABSYN_BINOP_EQ:
    case ABSYN_BINOP_NE:
      if (leftType != rightType) {
        error("comparison operation requires same operand types in line %d",
              node->line);
      }
      type = boolType;
      break;
    case ABSYN_BINOP_LT:
    case ABSYN_BINOP_LE:
    case ABSYN_BINOP_GT:
    case ABSYN_BINOP_GE:
      if (leftType != intType || rightType != intType) {
        error("comparison operation requires integer operands in line %d",
              node->line);
      }
      type = boolType;
      break;
    case ABSYN_BINOP_ADD:
    case ABSYN_BINOP_SUB:
    case ABSYN_BINOP_MUL:
    case ABSYN_BINOP_DIV:
    case ABSYN_BINOP_MOD:
      if (leftType != intType || rightType != intType) {
        error("arithmetic operation requires integer operands in line %d",
              node->line);
      }
      type = intType;
      break;
    default:
      error("unknown binary operator %d in checkBinopExp",
            node->u.binopExp.op);
  }
  return type;
}


static Type *checkUnopExp(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Type *rightType;
  Type *type;

  rightType = checkNode(node->u.unopExp.right, table, pass,
                        rtype, breakAllowed);
  switch (node->u.unopExp.op) {
    case ABSYN_UNOP_PLUS:
    case ABSYN_UNOP_MINUS:
      if (rightType != intType) {
        error("arithmetic operation requires integer operand in line %d",
              node->line);
      }
      type = intType;
      break;
    case ABSYN_UNOP_LNOT:
      if (rightType != boolType) {
        error("logical operation requires boolean operand in line %d",
              node->line);
      }
      type = boolType;
      break;
    default:
      error("unknown unary operator %d in checkUnopExp",
            node->u.unopExp.op);
  }
  return type;
}


static Type *checkIntExp(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  Type *type;

  type = intType;
  return type;
}


static Type *checkBoolExp(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Type *type;

  type = boolType;
  return type;
}


static Type *checkVarExp(Absyn *node, Table *table, int pass,
                         Type *rtype, bool breakAllowed) {
  Entry *entry;
  Type *type;

  entry = getVar(table, node->u.varExp.name, node->line);
  type = entry->u.varEntry.type;
  return type;
}


static Type *checkCallExp(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Entry *entry;
  ParamTypes *parameterTypes;
  Absyn *argumentExprs;
  Type *parameterType;
  Absyn *argumentExpr;
  Type *argumentType;
  int argNum;

  entry = lookup(table, node->u.callStm.name);
  if (entry == NULL) {
    error("undefined function '%s' in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  if (entry->kind != ENTRY_KIND_FUNC) {
    error("call of non-function '%s' in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  parameterTypes = entry->u.funcEntry.paramTypes;
  argumentExprs = node->u.callStm.args;
  argNum = 1;
  while (!parameterTypes->isEmpty && !argumentExprs->u.expList.isEmpty) {
    parameterType = parameterTypes->type;
    argumentExpr = argumentExprs->u.expList.head;
    argumentType = checkNode(argumentExpr, table, pass,
                             rtype, breakAllowed);
    if (parameterType != argumentType) {
      error("procedure '%s' argument %d type mismatch in line %d",
            symToString(node->u.callStm.name), argNum, node->line);
    }
    parameterTypes = parameterTypes->next;
    argumentExprs = argumentExprs->u.expList.tail;
    argNum++;
  }
  if (!parameterTypes->isEmpty) {
    error("procedure '%s' called with too few arguments in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  if (!argumentExprs->u.expList.isEmpty) {
    error("procedure '%s' called with too many arguments in line %d",
          symToString(node->u.callStm.name), node->line);
  }
  return entry->u.funcEntry.returnType;
}


static Type *checkDecList(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Absyn *list;

  list = node;
  while (!list->u.decList.isEmpty) {
    checkNode(list->u.decList.head, table, pass,
              rtype, breakAllowed);
    list = list->u.decList.tail;
  }
  return voidType;
}


static Type *checkStmList(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Absyn *list;

  list = node;
  while (!list->u.stmList.isEmpty) {
    checkNode(list->u.stmList.head, table, pass,
              rtype, breakAllowed);
    list = list->u.stmList.tail;
  }
  return voidType;
}


static Type *checkExpList(Absyn *node, Table *table, int pass,
                          Type *rtype, bool breakAllowed) {
  Absyn *list;

  list = node;
  while (!list->u.expList.isEmpty) {
    checkNode(list->u.expList.head, table, pass,
              rtype, breakAllowed);
    list = list->u.expList.tail;
  }
  return voidType;
}


static Type *checkNode(Absyn *node, Table *table, int pass,
                       Type *rtype, bool breakAllowed) {
  if (node == NULL) {
    error("checkNode got NULL node pointer");
  }
  switch (node->type) {
    case ABSYN_TY:
      return checkTy(node, table, pass, rtype, breakAllowed);
    case ABSYN_FUNCDEC:
      return checkFuncDec(node, table, pass, rtype, breakAllowed);
    case ABSYN_PARDEC:
      return checkParDec(node, table, pass, rtype, breakAllowed);
    case ABSYN_VARDEC:
      return checkVarDec(node, table, pass, rtype, breakAllowed);
    case ABSYN_EMPTYSTM:
      return checkEmptyStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_COMPSTM:
      return checkCompStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_ASSIGNSTM:
      return checkAssignStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_IFSTM1:
      return checkIfStm1(node, table, pass, rtype, breakAllowed);
    case ABSYN_IFSTM2:
      return checkIfStm2(node, table, pass, rtype, breakAllowed);
    case ABSYN_WHILESTM:
      return checkWhileStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_DOSTM:
      return checkDoStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_BREAKSTM:
      return checkBreakStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_CALLSTM:
      return checkCallStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_RETSTM:
      return checkRetStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_RETEXPSTM:
      return checkRetExpStm(node, table, pass, rtype, breakAllowed);
    case ABSYN_BINOPEXP:
      return checkBinopExp(node, table, pass, rtype, breakAllowed);
    case ABSYN_UNOPEXP:
      return checkUnopExp(node, table, pass, rtype, breakAllowed);
    case ABSYN_INTEXP:
      return checkIntExp(node, table, pass, rtype, breakAllowed);
    case ABSYN_BOOLEXP:
      return checkBoolExp(node, table, pass, rtype, breakAllowed);
    case ABSYN_VAREXP:
      return checkVarExp(node, table, pass, rtype, breakAllowed);
    case ABSYN_CALLEXP:
      return checkCallExp(node, table, pass, rtype, breakAllowed);
    case ABSYN_DECLIST:
      return checkDecList(node, table, pass, rtype, breakAllowed);
    case ABSYN_STMLIST:
      return checkStmList(node, table, pass, rtype, breakAllowed);
    case ABSYN_EXPLIST:
      return checkExpList(node, table, pass, rtype, breakAllowed);
    default:
      /* this should never happen */
      error("unknown node type %d in checkNode", node->type);
      /* not reached */
      return voidType;
  }
}


/**************************************************************/


static void enterLibraryFuncs(Table *table) {
  ParamTypes *paramTypes;
  Entry *funcEntry;

  /* int read() */
  paramTypes = emptyParamTypes();
  funcEntry = newFuncEntry(intType, paramTypes, NULL);
  funcEntry->u.funcEntry.numParams = 0;
  funcEntry->u.funcEntry.numLocals = 0;
  enter(table, newSym("read"), funcEntry);

  /* void write(int) */
  paramTypes = newParamTypes(intType, emptyParamTypes());
  funcEntry = newFuncEntry(voidType, paramTypes, NULL);
  funcEntry->u.funcEntry.numParams = 1;
  funcEntry->u.funcEntry.numLocals = 0;
  enter(table, newSym("write"), funcEntry);

  /* void exit() */
  paramTypes = emptyParamTypes();
  funcEntry = newFuncEntry(voidType, paramTypes, NULL);
  funcEntry->u.funcEntry.numParams = 0;
  funcEntry->u.funcEntry.numLocals = 0;
  enter(table, newSym("exit"), funcEntry);
}


static void checkMain(Table *globalTable) {
  Entry *mainEntry;

  mainEntry = lookup(globalTable, newSym("main"));
  if (mainEntry == NULL) {
    error("function 'main' is missing");
  }
  if (mainEntry->kind != ENTRY_KIND_FUNC) {
    error("'main' is not a function");
  }
  if (mainEntry->u.funcEntry.returnType != voidType) {
    error("function 'main' must not return a value");
  }
  if (!mainEntry->u.funcEntry.paramTypes->isEmpty) {
    error("procedure 'main' must not have any parameters");
  }
}


Table *check(Absyn *program, bool showSymbolTables) {
  Table *globalTable;

  /* store global flag to show local symbol tables */
  showLocalTables = showSymbolTables;
  /* generate built-in types */
  voidType = newPrimitiveType("void");
  intType = newPrimitiveType("integer");
  boolType = newPrimitiveType("boolean");
  /* setup global symbol table */
  globalTable = newTable(NULL);
  enterLibraryFuncs(globalTable);
  /* do semantic checks in 2 passes */
  checkNode(program, globalTable, 1, NULL, false);
  checkNode(program, globalTable, 2, NULL, false);
  /* check if "main()" is present */
  checkMain(globalTable);
  /* return global symbol table */
  return globalTable;
}