Česky
Kamil Dudka

Flex/Bison based compiler and interpreter written in C++ (using Boost)

File detail

Name:Downloadvm.cc [Download]
Location: vyp08 > vyp08-1.0pre1 > src
Size:18.2 KB
Last modification:2009-07-04 19:51

Source code

/*
 * Copyright (C) 2008 Kamil Dudka <xdudka00@stud.fit.vutbr.cz>
 *
 * This file is part of vyp08 (compiler and interpreter of VYP08 language).
 *
 * vyp08 is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * vyp08 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with vyp08.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#include "config.h"
#include "vm.h"
 
#include "cmd.h"
#include "vypIO.h"
 
#ifndef BUILDING_DOX
#   include <assert.h>
#   include <map>
#   include <queue>
#   include <stack>
#   include <vector>
#endif
 
using namespace StreamDecorator;
using std::string;
 
// /////////////////////////////////////////////////////////////////////////////
// Value implementation
Value::Value():
    type(V_NULL),
    boolVal(false),
    intVal(0),
    doubleVal(0.0)
{
}
std::ostream& operator<< (std::ostream &str, const Value::VType &type) {
    str << Color(C_LIGHT_BLUE);
    switch (type) {
        case Value::V_NULL:     str << "V_NULL";        break;
        case Value::V_BOOL:     str << "V_BOOL";        break;
        case Value::V_INT:      str << "V_INT";         break;
        case Value::V_DOUBLE:   str << "V_DOUBLE";      break;
        case Value::V_STRING:   str << "V_STRING";      break;
    }
    str << Color(C_NO_COLOR);
    return str;
}
std::ostream& operator<< (std::ostream &str, const Value &val) {
    Value::VType type = val.type;
    str << type;
    if (type == Value::V_NULL)
        return str;
 
    str << "(" << Color(C_YELLOW);
    switch (type) {
        case Value::V_BOOL:     str << (val.boolVal ? "true":"false");  break;
        case Value::V_INT:      str << val.intVal;      break;
        case Value::V_DOUBLE:   str << val.doubleVal;   break;
        case Value::V_STRING:   str << val.stringVal;   break;
        default:
            break;
    }
    str << Color(C_NO_COLOR) << ")";
    return str;
}
 
// /////////////////////////////////////////////////////////////////////////////
// Var implementation
Var::Var():
    used(false),
    initialized(false)
{
}
 
// /////////////////////////////////////////////////////////////////////////////
// ValueFactory implementation
PValue ValueFactory::create() {
    PValue val(new Value);
    val -> type = Value::V_NULL;
    return val;
}
 
PValue ValueFactory::create(bool b) {
    PValue val(new Value);
    val -> type = Value::V_BOOL;
    val -> boolVal = b;
    return val;
}
 
PValue ValueFactory::create(int i) {
    PValue val(new Value);
    val -> type = Value::V_INT;
    val -> intVal = i;
    return val;
}
 
PValue ValueFactory::create(double d) {
    PValue val(new Value);
    val -> type = Value::V_DOUBLE;
    val -> doubleVal = d;
    return val;
}
 
PValue ValueFactory::create(const std::string &s) {
    PValue val(new Value);
    val -> type = Value::V_STRING;
    val -> stringVal = s;
    return val;
}
 
// /////////////////////////////////////////////////////////////////////////////
// ValueStack implementation
struct ValueStack::Private {
    typedef STD_STACK(PValue) TStack;
    TStack      st;
 
    Vm          *const vm;
    Private(Vm *vm_): vm(vm_) { }
};
ValueStack::ValueStack(Vm *vm):
    d(new Private(vm))
{
}
ValueStack::~ValueStack() {
    delete d;
}
bool ValueStack::isEmpty() const {
    return d->st.empty();
}
 
void ValueStack::push(PValue val) {
#if DEBUG_TRACE_VMSTACK
    std::cerr << Color(C_LIGHT_PURPLE) << "vmStack"
        << Color(C_NO_COLOR) << " <-- " << *val << std::endl;
#endif
    d->st.push(val);
}
 
PValue ValueStack::pop() {
    PValue val;
    if (!d->st.empty()) {
        val = d->st.top();
        d->st.pop();
    }
#if DEBUG_TRACE_VMSTACK
    std::cerr << Color(C_LIGHT_PURPLE) << "vmStack"
        << Color(C_NO_COLOR) << " --> " << *val << std::endl;
#endif
    return val;
}
 
bool ValueStack::push(PValue val, const Token &t) {
    Vm *vm = d->vm;
    if (val->type == Value::V_NULL) {
        std::cerr << Error(E_ERROR, vm->fileName, "vmStack: attempt to push void value", t, true) << std::endl;
        return false;
    }
    vm->vmStack.push(val);
    return true;
}
 
bool ValueStack::pushFromVar(const Var &var, const Token &t) {
    Vm *vm = d->vm;
    PValue val(new Value(var.value));
    if (!var.initialized) {
        std::cerr << Error(E_ERROR, vm->fileName, "attempt to read uninitialized value", t) << std::endl;
        std::cerr << Error(E_NOTE, vm->fileName, "definition was here", var.defined) << std::endl;
        return false;
    }
    return push(val, t);
}
 
bool ValueStack::pop(PValue &val, const Token &t) {
    Vm *vm = d->vm;
    ValueStack &stack = vm->vmStack;
    if (stack.isEmpty()) {
        std::cerr << Error(E_ERROR, vm->fileName, "vmStack underflow", t, true) << std::endl;
        return false;
    }
    val = stack.pop();
    return true;
}
 
bool ValueStack::popToVar(Var &var, const Token &t) {
    Vm *vm = d->vm;
 
    // pop value from stack
    PValue val;
    if (!pop(val, t))
        return false;
 
    // check type
    Value::VType srcType = val->type;
    Value::VType dstType = var.value.type;
    if (srcType != dstType) {
        // TODO: mark this as internal error after testing as this is now checked statically
        std::cerr << Error(E_ERROR, vm->fileName, "type mismatch", t) << std::endl;
        std::cerr << Error(E_NOTE, vm->fileName, "expression type: ") << srcType << std::endl;
        std::cerr << Error(E_NOTE, vm->fileName, "   L-Value type: ") << dstType << std::endl;
        return false;
    }
 
    // store value
    var.value = *val;
    var.initialized = true;
    return true;
}
 
// /////////////////////////////////////////////////////////////////////////////
// VarSet implementation
struct VarSet::Private {
    typedef STD_VECTOR(PVar)        TVector;
    typedef STD_MAP(string, PVar)   TMap;
    TVector vect;
    TMap    vMap;
};
VarSet::VarSet():
    d(new Private)
{
}
VarSet::~VarSet() {
    delete d;
}
 
VarSet& VarSet::operator= (const VarSet &other) {
    // clear self
    d->vect.clear();
    d->vMap.clear();
 
    // deep copy of items in other VarSet
    for(unsigned i=0; i<other.size(); i++) {
        const Var &var = *(other[i]);
        PVar pVar(new Var(var));
        this->add(pVar);
    }
 
    return *this;
}
 
bool VarSet::add(PVar var) {
    const string &name = var->name;
    if (!name.empty()) {
        // named variable
        Private::TMap::iterator i = d->vMap.find(name);
        if (i != d->vMap.end())
            // variable redefinition
            return false;
 
        d->vMap[name] = var;
    }
    d->vect.push_back(var);
    return true;
}
 
unsigned VarSet::size() const {
    return d->vect.size();
}
 
PVar VarSet::operator[] (unsigned pos) {
    assert(pos < size());
    return d->vect[pos];
}
 
PVar VarSet::operator[] (const std::string &name) {
    assert(!name.empty());
    PVar var;
    Private::TMap::iterator i = d->vMap.find(name);
    if (i != d->vMap.end())
        var = i->second;
    return var;
}
 
// /////////////////////////////////////////////////////////////////////////////
// FncDeclaration implementation
FncDeclaration::FncDeclaration()
{
}
 
FncDeclaration::~FncDeclaration() {
}
 
FncDeclaration::FncDeclaration(const FncDeclaration &other):
    self(other.self)
{
    args = other.args;
}
 
FncDeclaration& FncDeclaration::operator= (const FncDeclaration &other) {
    self = other.self;
    args = other.args;
    return *this;
}
 
bool operator== (const FncDeclaration &a, const FncDeclaration &b) {
    if (a.self.name != b.self.name)
        return false;
    if (a.self.value.type != b.self.value.type)
        return false;
    if (a.args.size() != b.args.size())
        return false;
    for (unsigned i=0; i< a.args.size(); i++) {
        const Value &aVal = a.args[i] -> value;
        const Value &bVal = b.args[i] -> value;
        if (aVal.type != bVal.type)
            return false;
    }
    return true;
}
 
bool operator!= (const FncDeclaration &a, const FncDeclaration &b) {
    return !operator== (a, b);
}
 
// /////////////////////////////////////////////////////////////////////////////
// FncDefinition implementation
FncDefinition::FncDefinition(Vm *vm_):
    vm(vm_),
    cmdList(new CmdList)
{
}
 
FncDefinition::~FncDefinition() {
}
 
FncDefinition::FncDefinition(const FncDefinition &other):
    FncDeclaration(other),
    vm(other.vm),
    cmdList(other.cmdList)
{
    vars = other.vars;
}
 
bool chkUnused(FncDefinition *fnc) {
    Vm *vm = fnc->vm;
    bool sane = true;
 
    // check for unused parameters
    const VarSet &argSet = fnc -> args;
    for (unsigned i = 0; i < argSet.size(); i++) {
        PVar arg = argSet[i];
        if (arg->used)
            continue;
 
        sane = false;
        std::cerr << Error(E_WARNING, vm->fileName, "unused function argument", arg->defined) << std::endl;
        std::cerr << Error(E_NOTE, vm->fileName, "defined in this function", fnc->self.defined) << std::endl;
    }
 
    // check for unused local variables
    const VarSet &varSet = fnc -> vars;
    for (unsigned i = 0; i < varSet.size(); i++) {
        PVar var = varSet[i];
        if (var->used)
            continue;
 
        sane = false;
        std::cerr << Error(E_WARNING, vm->fileName, "unused local variable", var->defined) << std::endl;
        std::cerr << Error(E_NOTE, vm->fileName, "defined in this function", fnc->self.defined) << std::endl;
    }
 
    return sane;
}
 
// /////////////////////////////////////////////////////////////////////////////
// FncSet implementation
struct FncSet::Private {
    typedef STD_MAP(string, FncDeclaration *)  TDeclMap;
    typedef STD_MAP(string, FncDefinition *)   TDefMap;
    TDeclMap    declMap;
    TDefMap     defMap;
};
 
FncSet::FncSet():
    d(new Private)
{
}
 
FncSet::~FncSet() {
    for(
            Private::TDeclMap::iterator i = d->declMap.begin();
            i != d->declMap.end();
            i++)
        delete (i->second);
 
    for(
            Private::TDefMap::iterator i = d->defMap.begin();
            i != d->defMap.end();
            i++)
        delete (i->second);
 
    delete d;
}
 
bool FncSet::addDeclaration(FncDeclaration *decl) {
    const string &name = decl->self.name;
    Private::TDeclMap::iterator i = d->declMap.find(name);
    if (i == d->declMap.end()) {
        d->declMap[name] = decl;
        return true;
    }
    const FncDeclaration &prev = *(i->second);
    const FncDeclaration &curr = *decl;
    if (prev == curr) {
        delete decl;
        return true;
    }
    return false;
}
 
FncDeclaration* FncSet::getDeclaration(const std::string &name) {
    Private::TDeclMap::iterator i = d->declMap.find(name);
    if (i == d->declMap.end())
        return 0;
    else
        return i->second;
}
 
bool FncSet::addDefinition(FncDefinition *def) {
    const string &name = def->self.name;
    if (d->defMap.find(name) != d->defMap.end())
        // redefinition
        return false;
 
    Private::TDeclMap::iterator i = d->declMap.find(name);
    if (i == d->declMap.end()) {
        // add declaration as well
        d->declMap[name] = new FncDeclaration(*def);
    } else {
        const FncDeclaration &prev = *(i->second);
        const FncDeclaration &curr = *def;
        if (prev != curr)
            // decl/def mismatch
            return false;
    }
 
    // add definition
    d->defMap[name] = def;
 
    // check for unused arguments / local variables
    chkUnused(def);
    return true;
}
 
FncDefinition* FncSet::getDefinition(const std::string &name) {
    Private::TDefMap::iterator i = d->defMap.find(name);
    if (i == d->defMap.end())
        return 0;
    else
        return i->second;
}
 
void FncSet::getAllDefinitions(TVector &fncVect) {
    for (
            Private::TDefMap::iterator i = d->defMap.begin();
            i != d->defMap.end();
            i++
        )
    {
        fncVect.push_back(i->second);
    }
}
 
// /////////////////////////////////////////////////////////////////////////////
// CmdList implementation
struct CmdList::Private {
    typedef STD_VECTOR(PCmd) TVector;
    TVector vect;
};
CmdList::CmdList():
    d(new Private)
{
}
CmdList::~CmdList() {
    delete d;
}
void CmdList::add(PCmd cmd) {
    d->vect.push_back(cmd);
}
bool CmdList::exec(FncDefinition *fnc) {
    for (
            Private::TVector::iterator i = d->vect.begin();
            i != d->vect.end();
            i++)
    {
        PCmd &cmd = *i;
#if DEBUG_TRACE_CMD_LIST_EXEC
        std::cerr << Color(C_WHITE) << "exec: " << Color(C_NO_COLOR);
        cmd->toStream(std::cerr);
        std::cerr << std::endl;
#endif
        if (!cmd->exec(fnc))
            return false;
    }
    return true;
}
void CmdList::toStream(std::ostream &str) const {
    str << Color(C_LIGHT_GREEN) << "{" << Color(C_NO_COLOR) << " ";
    for (
            Private::TVector::iterator i = d->vect.begin();
            i != d->vect.end();
            i++)
    {
        if (i != d->vect.begin())
            str << Color(C_LIGHT_GREEN) << "," << Color(C_NO_COLOR) << " ";
        PCmd &cmd = *i;
        cmd->toStream(str);
    }
    str << " " << Color(C_LIGHT_GREEN) << "}" << Color(C_NO_COLOR);
}
 
// /////////////////////////////////////////////////////////////////////////////
// CalleeSet implementation
struct CalleeSet::Private {
    typedef SHARED_PTR(Token)                   PToken;
    struct SortableToken {
        PToken t;
 
        SortableToken(const Token &t_): t(new Token(t_)) { }
        SortableToken(const SortableToken &other): t(other.t) { }
        SortableToken& operator=(const SortableToken &other) { t = other.t; return *this; }
        operator int() const { return -t->lineno; }
    };
    typedef STD_PRIORITY_QUEUE(SortableToken)   TTokenQueue;
    typedef SHARED_PTR(TTokenQueue)             PTokenQueue;
    typedef STD_MAP(string, PTokenQueue)        TMap;
    TMap map;
};
CalleeSet::CalleeSet():
    d(new Private)
{
}
CalleeSet::~CalleeSet() {
    delete d;
}
void CalleeSet::add(std::string name, Token tCall) {
    Private::PTokenQueue queue;
 
    // name lookup
    Private::TMap::iterator i = d->map.find(name);
    if (i == d->map.end())
        // create new queue
        queue.reset(new Private::TTokenQueue);
    else
        // use existing queue
        queue = i->second;
 
    if (tCall.type != ETOKEN_NULL)
        // add token to queue (if any)
        queue->push(tCall);
 
    // move pointer (back) to map
    d->map[name] = queue;
}
 
bool CalleeSet::isCalled(std::string name) {
    return d->map.find(name) != d->map.end();
}
 
void CalleeSet::getNames(TStringList &list) {
    for (
            Private::TMap::iterator i = d->map.begin();
            i != d->map.end();
            i++)
        list.push_back(i->first);
}
 
bool CalleeSet::getCalls(std::string name, TTokenList &list) {
    // name lookup
    Private::TMap::iterator i = d->map.find(name);
    if (i == d->map.end())
        return false;
 
    // clone queue and copy to list (not very optimized)
    Private::TTokenQueue queue = *(i->second);
    while (!queue.empty()) {
        list.push_back(*(queue.top().t));
        queue.pop();
    }
 
    return true;
}
 
 
// /////////////////////////////////////////////////////////////////////////////
// VmRunner implementation
struct VmRunner::Private {
    Vm      *const vm;
    bool    hasError;
 
    Private(Vm *vm_):
        vm(vm_),
        hasError(false)
    {
    }
    void chkUnusedGlVars();
    void chkUnusedFncs();
    void chkFncRefs();
    bool run();
};
VmRunner::VmRunner(Vm *vm):
    d(new Private(vm))
{
    d->chkUnusedGlVars();
    d->chkUnusedFncs();
    d->chkFncRefs();
}
VmRunner::~VmRunner() {
    delete d;
}
bool VmRunner::hasError() const {
    return d->hasError;
}
bool VmRunner::run() {
    return (d->hasError)
        ? false : d->run();
}
 
void VmRunner::Private::chkUnusedGlVars() {
    const VarSet &varSet = vm -> glVars;
    for (unsigned i = 0; i < varSet.size(); i++) {
        PVar var = varSet[i];
        if (var->used)
            continue;
        std::cerr << Error(E_WARNING, vm->fileName, "unused global variable", var->defined) << std::endl;
    }
}
 
void VmRunner::Private::chkUnusedFncs() {
    FncSet::TVector fncVect;
    vm -> fncSet.getAllDefinitions(fncVect);
    CalleeSet unusedSet;
    for (unsigned i = 0; i < fncVect.size(); i++) {
        const FncDefinition *fnc = fncVect[i];
        if (!vm->calleeSet.isCalled(fnc->self.name))
            unusedSet.add("", fnc->self.defined);
    }
    CalleeSet::TTokenList tList;
    unusedSet.getCalls("", tList);
    for (unsigned i = 0; i < tList.size(); i++)
        std::cerr << Error(E_WARNING, vm->fileName, "unused function", tList[i]) << std::endl;
}
 
void VmRunner::Private::chkFncRefs() {
    FncSet &fncSet = vm -> fncSet;
    CalleeSet &calleeSet = vm -> calleeSet;
    CalleeSet::TStringList calleeNames;
    calleeSet.getNames(calleeNames);
    for (unsigned i = 0; i < calleeNames.size(); i++) {
        const string &name = calleeNames[i];
        if (fncSet.getDefinition(name))
            // definition ok
            continue;
 
        hasError = true;
        std::cerr << Error(E_ERROR, vm->fileName, "unresolved reference to function", 0, name) << std::endl;
        FncDeclaration *decl = fncSet.getDeclaration(name);
        if (decl && decl->self.defined.lineno)
            std::cerr << Error(E_NOTE, vm->fileName, "declared here", decl->self.defined) << std::endl;
        CalleeSet::TTokenList callers;
        calleeSet.getCalls(name, callers);
        for (unsigned i = 0; i < callers.size(); i++)
            std::cerr << Error(E_NOTE, vm->fileName, "called from here", callers[i]) << std::endl;
    }
}
 
bool VmRunner::Private::run() {
    // main function lookup
    FncDefinition *mainFnc = vm -> fncSet.getDefinition("main");
 
    // create CallCmd for main
    Token tMain (ETOKEN_ID, 0, 0, 0.0, "main");
    CmdFactory cmdFactory(vm);
    PCmd callCmd = cmdFactory.createCall(tMain, 0, false);
 
    // call main
    if (!callCmd->exec(mainFnc))
        return false;
 
    // check vmStack offset
    if (vm->vmStack.isEmpty())
        // all ok
        return true;
 
    std::cerr << Error(E_ERROR, vm->fileName, "vmStack offset detected", tMain, true) << std::endl;
    return false;
}