Added runtime check for array index and division

11 files changed, 153 insertions, 19 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 8330e33..41c379b 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -14,9 +14,11 @@ include_directories(include)
 
 add_library(CPSLexer lib/Lexer/Lexer.cc)
 add_library(CPSParser lib/Parser/Parser.cc)
+
 add_library(CPSCodeGen
     lib/CodeGen/CodeGen.cc
     lib/CodeGen/ArrayHandler.cc
+    lib/CodeGen/RuntimeCheck.cc
 )
 
 llvm_map_components_to_libnames(llvm_libs core support native irreader)
diff --git a/include/cps/AST.h b/include/cps/AST.h
index aaf81cb..a0c0ace 100644
--- a/include/cps/AST.h
+++ b/include/cps/AST.h
@@ -27,22 +27,26 @@ public:
 class ArrayAccessExprAST : public ExprAST {
     std::string Name;
     std::vector<std::unique_ptr<ExprAST>> Indices;
+    int Line;
 public:
-    ArrayAccessExprAST(const std::string &Name, std::vector<std::unique_ptr<ExprAST>> Indices)
-        : Name(Name), Indices(std::move(Indices)) {}
+    ArrayAccessExprAST(const std::string &Name, std::vector<std::unique_ptr<ExprAST>> Indices, int Line)
+        : Name(Name), Indices(std::move(Indices)), Line(Line) {}
     const std::string &getName() const { return Name; }
     const std::vector<std::unique_ptr<ExprAST>> &getIndices() const { return Indices; }
+    int getLine() const { return Line; }
 };
 
 class BinaryExprAST : public ExprAST {
     int Op;
     std::unique_ptr<ExprAST> LHS, RHS;
+    int Line;
 public:
-    BinaryExprAST(int Op, std::unique_ptr<ExprAST> LHS, std::unique_ptr<ExprAST> RHS)
-        : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
+    BinaryExprAST(int Op, std::unique_ptr<ExprAST> LHS, std::unique_ptr<ExprAST> RHS, int Line)
+        : Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)), Line(Line) {}
     int getOp() const { return Op; }
     ExprAST *getLHS() const { return LHS.get(); }
     ExprAST *getRHS() const { return RHS.get(); }
+    int getLine() const { return Line; }
 };
 
 class StmtAST {
@@ -86,12 +90,14 @@ class ArrayAssignStmtAST : public StmtAST {
     std::string Name;
     std::vector<std::unique_ptr<ExprAST>> Indices;
     std::unique_ptr<ExprAST> Expr;
+    int Line;
 public:
-    ArrayAssignStmtAST(const std::string &Name, std::vector<std::unique_ptr<ExprAST>> Indices, std::unique_ptr<ExprAST> Expr)
-        : Name(Name), Indices(std::move(Indices)), Expr(std::move(Expr)) {}
+    ArrayAssignStmtAST(const std::string &Name, std::vector<std::unique_ptr<ExprAST>> Indices, std::unique_ptr<ExprAST> Expr, int Line)
+        : Name(Name), Indices(std::move(Indices)), Expr(std::move(Expr)), Line(Line) {}
     const std::string &getName() const { return Name; }
     const std::vector<std::unique_ptr<ExprAST>> &getIndices() const { return Indices; }
     ExprAST *getExpr() const { return Expr.get(); }
+    int getLine() const { return Line; }
 };
 
 class InputStmtAST : public StmtAST {
diff --git a/include/cps/ArrayHandler.h b/include/cps/ArrayHandler.h
index 5052de4..734f464 100644
--- a/include/cps/ArrayHandler.h
+++ b/include/cps/ArrayHandler.h
@@ -3,6 +3,7 @@
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "cps/AST.h"
+#include "cps/RuntimeCheck.h"
 #include <map>
 #include <string>
 #include <vector>
@@ -26,6 +27,7 @@ class ArrayHandler {
     std::map<std::string, llvm::AllocaInst*> *NamedValues;
 
     std::map<std::string, ArrayMetadata> ArrayTable;
+    RuntimeCheck &RuntimeChecker;
 
     llvm::FunctionCallee MallocFunc;
     llvm::FunctionCallee FreeFunc;
@@ -41,6 +43,7 @@ public:
     
     void emitArrayDeclare(ArrayDeclareStmtAST *Stmt, CodeGen &CG);
     void emitArrayAssign(ArrayAssignStmtAST *Stmt, CodeGen &CG);
+    ArrayHandler(llvm::LLVMContext &C, llvm::IRBuilder<> &B, llvm::Module &M, std::map<std::string, llvm::AllocaInst*> &NV, RuntimeCheck &RC);
     
     llvm::Value* emitArrayAccess(ArrayAccessExprAST *Expr, CodeGen &CG);
 
diff --git a/include/cps/CodeGen.h b/include/cps/CodeGen.h
index 8bf5819..57f0899 100644
--- a/include/cps/CodeGen.h
+++ b/include/cps/CodeGen.h
@@ -3,6 +3,7 @@
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "cps/AST.h"
+#include "cps/RuntimeCheck.h"
 #include <map>
 #include <memory>
 
@@ -17,6 +18,7 @@ class CodeGen {
     std::map<std::string, llvm::AllocaInst*> NamedValues;
     
     std::unique_ptr<ArrayHandler> Arrays;
+    std::unique_ptr<RuntimeCheck> RuntimeChecker;
 
     llvm::FunctionCallee PrintfFunc;
     llvm::FunctionCallee ScanfFunc;
diff --git a/include/cps/Lexer.h b/include/cps/Lexer.h
index a7a6218..237f76a 100644
--- a/include/cps/Lexer.h
+++ b/include/cps/Lexer.h
@@ -44,11 +44,13 @@ enum Token {
 };
 
 class Lexer {
+    int CurrentLine = 1;
 public:
     std::string IdentifierStr;
     int NumVal;
 
     int gettok();
+    int getLine() const { return CurrentLine; }
 };
 
 }
diff --git a/include/cps/RuntimeCheck.h b/include/cps/RuntimeCheck.h
new file mode 100644
index 0000000..3c31f41
--- /dev/null
+++ b/include/cps/RuntimeCheck.h
@@ -0,0 +1,28 @@
+#pragma once
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+
+namespace cps {
+
+class RuntimeCheck {
+    llvm::Module &TheModule;
+    llvm::LLVMContext &TheContext;
+    llvm::IRBuilder<> &Builder;
+
+    llvm::FunctionCallee PrintfFunc;
+    llvm::FunctionCallee ExitFunc;
+    llvm::Value *DivZeroMsg;
+    llvm::Value *OutOfBoundsMsg;
+
+    void setupExternalFunctions();
+    void emitErrorAndExit(llvm::Value *Condition, llvm::Value *Msg, int Line);
+
+public:
+    RuntimeCheck(llvm::Module &M, llvm::LLVMContext &C, llvm::IRBuilder<> &B);
+
+    void emitDivZeroCheck(llvm::Value *Divisor, int Line);
+    void emitIndexCheck(llvm::Value *Index, llvm::Value *Lower, llvm::Value *Upper, int Line);
+};
+
+}
diff --git a/lib/CodeGen/ArrayHandler.cc b/lib/CodeGen/ArrayHandler.cc
index 470cffa..499fd2d 100644
--- a/lib/CodeGen/ArrayHandler.cc
+++ b/lib/CodeGen/ArrayHandler.cc
@@ -8,8 +8,8 @@
 using namespace llvm;
 using namespace cps;
 
-ArrayHandler::ArrayHandler(LLVMContext &C, IRBuilder<> &B, Module &M, std::map<std::string, AllocaInst*> &NV)
-    : TheContext(&C), Builder(&B), TheModule(&M), NamedValues(&NV) {
+ArrayHandler::ArrayHandler(LLVMContext &C, IRBuilder<> &B, Module &M, std::map<std::string, AllocaInst*> &NV, RuntimeCheck &RC)
+    : TheContext(&C), Builder(&B), TheModule(&M), NamedValues(&NV), RuntimeChecker(RC) {
     setupExternalFunctions();
 }
 
@@ -115,8 +115,13 @@ Value* ArrayHandler::emitArrayAccess(ArrayAccessExprAST *Expr, CodeGen &CG) {
     }
 
     std::vector<Value*> Indices;
-    for (const auto &IdxExpr : Expr->getIndices()) {
-        Indices.push_back(CG.emitExpr(IdxExpr.get()));
+    for (size_t i = 0; i < Expr->getIndices().size(); ++i) {
+        Value *Idx = CG.emitExpr(Expr->getIndices()[i].get());
+        Indices.push_back(Idx);
+
+        Value *Lower = Meta.LowerBounds[i];
+        Value *Upper = Meta.UpperBounds[i];
+        RuntimeChecker.emitIndexCheck(Idx, Lower, Upper, Expr->getLine());
     }
     
     Value *Offset = computeFlatIndex(Name, Indices);
@@ -137,8 +142,14 @@ void ArrayHandler::emitArrayAssign(ArrayAssignStmtAST *Stmt, CodeGen &CG) {
     }
     
     std::vector<Value*> Indices;
-    for (const auto &IdxExpr : Stmt->getIndices()) {
-        Indices.push_back(CG.emitExpr(IdxExpr.get()));
+    for (size_t i = 0; i < Stmt->getIndices().size(); ++i) {
+        Value *Idx = CG.emitExpr(Stmt->getIndices()[i].get());
+        Indices.push_back(Idx);
+
+        const auto &Meta = ArrayTable[Name];
+        Value *Lower = Meta.LowerBounds[i];
+        Value *Upper = Meta.UpperBounds[i];
+        RuntimeChecker.emitIndexCheck(Idx, Lower, Upper, Stmt->getLine());
     }
     
     Value *Val = CG.emitExpr(Stmt->getExpr());
diff --git a/lib/CodeGen/CodeGen.cc b/lib/CodeGen/CodeGen.cc
index 57d76eb..e2c959e 100644
--- a/lib/CodeGen/CodeGen.cc
+++ b/lib/CodeGen/CodeGen.cc
@@ -13,7 +13,9 @@ CodeGen::CodeGen() {
     TheModule = std::make_unique<Module>("cps_module", *TheContext);
     Builder = std::make_unique<IRBuilder<>>(*TheContext);
     
-    Arrays = std::make_unique<ArrayHandler>(*TheContext, *Builder, *TheModule, NamedValues);
+    RuntimeChecker = std::make_unique<RuntimeCheck>(*TheModule, *TheContext, *Builder);
+    
+    Arrays = std::make_unique<ArrayHandler>(*TheContext, *Builder, *TheModule, NamedValues, *RuntimeChecker);
     
     SetupExternalFunctions();
 }
@@ -89,7 +91,9 @@ Value *CodeGen::emitExpr(ExprAST *Expr) {
         case '+': return Builder->CreateAdd(L, R, "addtmp");
         case '-': return Builder->CreateSub(L, R, "subtmp");
         case '*': return Builder->CreateMul(L, R, "multmp");
-        case '/': return Builder->CreateSDiv(L, R, "divtmp");
+        case '/': 
+            RuntimeChecker->emitDivZeroCheck(R, Bin->getLine());
+            return Builder->CreateSDiv(L, R, "divtmp");
         case tok_eq: return Builder->CreateICmpEQ(L, R, "eqtmp");
         case tok_ne: return Builder->CreateICmpNE(L, R, "netmp");
         case '<':    return Builder->CreateICmpSLT(L, R, "slttmp");
diff --git a/lib/CodeGen/RuntimeCheck.cc b/lib/CodeGen/RuntimeCheck.cc
new file mode 100644
index 0000000..cab50d5
--- /dev/null
+++ b/lib/CodeGen/RuntimeCheck.cc
@@ -0,0 +1,60 @@
+#include "cps/RuntimeCheck.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Constants.h"
+
+using namespace llvm;
+using namespace cps;
+
+RuntimeCheck::RuntimeCheck(Module &M, LLVMContext &C, IRBuilder<> &B)
+    : TheModule(M), TheContext(C), Builder(B) {
+    setupExternalFunctions();
+}
+
+void RuntimeCheck::setupExternalFunctions() {
+    std::vector<Type*> PrintfArgs;
+    PrintfArgs.push_back(PointerType::getUnqual(TheContext));
+    FunctionType *PrintfType = FunctionType::get(Type::getInt32Ty(TheContext), PrintfArgs, true);
+    PrintfFunc = TheModule.getOrInsertFunction("printf", PrintfType);
+
+    std::vector<Type*> ExitArgs;
+    ExitArgs.push_back(Type::getInt32Ty(TheContext));
+    FunctionType *ExitType = FunctionType::get(Type::getVoidTy(TheContext), ExitArgs, false);
+    ExitFunc = TheModule.getOrInsertFunction("exit", ExitType);
+
+    DivZeroMsg = Builder.CreateGlobalStringPtr("[Fatal] line %d: Division by zero\n", "err_div_zero", 0, &TheModule);
+    OutOfBoundsMsg = Builder.CreateGlobalStringPtr("[Fatal] line %d: Array index out of bounds\n", "err_bounds", 0, &TheModule);
+}
+
+void RuntimeCheck::emitErrorAndExit(Value *Condition, Value *Msg, int Line) {
+    Function *TheFunction = Builder.GetInsertBlock()->getParent();
+    
+    BasicBlock *FailBB = BasicBlock::Create(TheContext, "check_fail", TheFunction);
+    BasicBlock *ContBB = BasicBlock::Create(TheContext, "check_cont", TheFunction);
+
+    Builder.CreateCondBr(Condition, FailBB, ContBB);
+
+    Builder.SetInsertPoint(FailBB);
+    std::vector<Value*> PrintArgs;
+    PrintArgs.push_back(Msg);
+    PrintArgs.push_back(ConstantInt::get(TheContext, APInt(32, Line)));
+    Builder.CreateCall(PrintfFunc, PrintArgs);
+
+    Builder.CreateCall(ExitFunc, ConstantInt::get(TheContext, APInt(32, 1)));
+    Builder.CreateUnreachable();
+
+    Builder.SetInsertPoint(ContBB);
+}
+
+void RuntimeCheck::emitDivZeroCheck(Value *Divisor, int Line) {
+    Value *IsZero = Builder.CreateICmpEQ(Divisor, ConstantInt::get(TheContext, APInt(32, 0)), "is_zero");
+    emitErrorAndExit(IsZero, DivZeroMsg, Line);
+}
+
+void RuntimeCheck::emitIndexCheck(Value *Index, Value *Lower, Value *Upper, int Line) {
+    Value *TooLow = Builder.CreateICmpSLT(Index, Lower, "too_low");
+    Value *TooHigh = Builder.CreateICmpSGT(Index, Upper, "too_high");
+    Value *OutOfBounds = Builder.CreateOr(TooLow, TooHigh, "out_of_bounds");
+    
+    emitErrorAndExit(OutOfBounds, OutOfBoundsMsg, Line);
+}
diff --git a/lib/Lexer/Lexer.cc b/lib/Lexer/Lexer.cc
index fdaa3a5..780c79a 100644
--- a/lib/Lexer/Lexer.cc
+++ b/lib/Lexer/Lexer.cc
@@ -9,8 +9,10 @@ using namespace cps;
 int Lexer::gettok() {
     static int LastChar = ' ';
 
-    while (isspace(LastChar))
+    while (isspace(LastChar)) {
+        if (LastChar == '\n') CurrentLine++;
         LastChar = getchar();
+    }
 
     if (isalpha(LastChar)) {
         IdentifierStr = LastChar;
diff --git a/lib/Parser/Parser.cc b/lib/Parser/Parser.cc
index a85b151..b9396ce 100644
--- a/lib/Parser/Parser.cc
+++ b/lib/Parser/Parser.cc
@@ -38,6 +38,7 @@ std::unique_ptr<ExprAST> Parser::ParseNumberExpr() {
 
 std::unique_ptr<ExprAST> Parser::ParseIdentifierExpr() {
     std::string IdName = Lex.IdentifierStr;
+    int Line = Lex.getLine();
     getNextToken();
     
     if (CurTok == '[') {
@@ -60,7 +61,7 @@ std::unique_ptr<ExprAST> Parser::ParseIdentifierExpr() {
             return nullptr;
         }
         getNextToken(); 
-        return std::make_unique<ArrayAccessExprAST>(IdName, std::move(Indices));
+        return std::make_unique<ArrayAccessExprAST>(IdName, std::move(Indices), Line);
     }
     
     return std::make_unique<VariableExprAST>(IdName);
@@ -84,7 +85,8 @@ std::unique_ptr<ExprAST> Parser::ParsePrimary() {
     case tok_number:     return ParseNumberExpr();
     case '(':            return ParseParenExpr();
     default:
-        fprintf(stderr, "Error: unknown token when expecting an expression\n");
+        fprintf(stderr, "Error: unknown token '%c' (%d) at line %d when expecting an expression\n", 
+                (char)CurTok, CurTok, Lex.getLine());
         return nullptr;
     }
 }
@@ -95,6 +97,7 @@ std::unique_ptr<ExprAST> Parser::ParseBinOpRHS(int ExprPrec, std::unique_ptr<Exp
         if (TokPrec < ExprPrec) return LHS;
 
         int BinOp = CurTok;
+        int Line = Lex.getLine();
         getNextToken();
 
         auto RHS = ParsePrimary();
@@ -106,7 +109,7 @@ std::unique_ptr<ExprAST> Parser::ParseBinOpRHS(int ExprPrec, std::unique_ptr<Exp
             if (!RHS) return nullptr;
         }
 
-        LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
+        LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS), Line);
     }
 }
 
@@ -209,6 +212,7 @@ std::unique_ptr<StmtAST> Parser::ParseIfStmt() {
     while (CurTok != tok_else && CurTok != tok_endif && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) ThenStmts.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_else && CurTok != tok_endif) getNextToken();
     }
 
     std::vector<std::unique_ptr<StmtAST>> ElseStmts;
@@ -217,6 +221,7 @@ std::unique_ptr<StmtAST> Parser::ParseIfStmt() {
         while (CurTok != tok_endif && CurTok != tok_eof) {
             auto Stmt = ParseStatement();
             if (Stmt) ElseStmts.push_back(std::move(Stmt));
+            else if (CurTok != tok_eof && CurTok != tok_endif) getNextToken();
         }
     }
 
@@ -244,6 +249,7 @@ std::unique_ptr<StmtAST> Parser::ParseWhileStmt() {
     while (CurTok != tok_endwhile && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) Body.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_endwhile) getNextToken();
     }
 
     if (CurTok != tok_endwhile) {
@@ -262,6 +268,7 @@ std::unique_ptr<StmtAST> Parser::ParseRepeatStmt() {
     while (CurTok != tok_until && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) Body.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_until) getNextToken();
     }
 
     if (CurTok != tok_until) {
@@ -307,12 +314,14 @@ std::unique_ptr<StmtAST> Parser::ParseForStmt() {
     if (CurTok == tok_step) {
         getNextToken();
         Step = ParseExpression();
+        if (!Step) return nullptr;
     }
 
     std::vector<std::unique_ptr<StmtAST>> Body;
     while (CurTok != tok_next && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) Body.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_next) getNextToken();
     }
 
     if (CurTok != tok_next) {
@@ -342,6 +351,7 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
     }
     else if (CurTok == tok_identifier) {
         std::string Name = Lex.IdentifierStr;
+        int Line = Lex.getLine();
         getNextToken();
         
         if (CurTok == '[') {
@@ -349,6 +359,7 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
             std::vector<std::unique_ptr<ExprAST>> Indices;
             while (true) {
                 auto Exp = ParseExpression();
+                if (!Exp) return nullptr;
                 Indices.push_back(std::move(Exp));
                 if (CurTok == ']') break;
                 if (CurTok == ',') getNextToken();
@@ -361,12 +372,14 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
             }
             getNextToken();
             auto Expr = ParseExpression();
-            return std::make_unique<ArrayAssignStmtAST>(Name, std::move(Indices), std::move(Expr));
+            if (!Expr) return nullptr;
+            return std::make_unique<ArrayAssignStmtAST>(Name, std::move(Indices), std::move(Expr), Line);
         }
         
         if (CurTok != tok_assign) return nullptr;
         getNextToken();
         auto Expr = ParseExpression();
+        if (!Expr) return nullptr;
         return std::make_unique<AssignStmtAST>(Name, std::move(Expr));
     }
     else if (CurTok == tok_input) {
@@ -379,6 +392,7 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
     else if (CurTok == tok_output) {
         getNextToken();
         auto Expr = ParseExpression();
+        if (!Expr) return nullptr;
         return std::make_unique<OutputStmtAST>(std::move(Expr));
     }
     else if (CurTok == tok_if) {