vm.cc

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2008 Kamil Dudka <xdudka00@stud.fit.vutbr.cz>
00003  *
00004  * This file is part of vyp08 (compiler and interpreter of VYP08 language).
00005  *
00006  * vyp08 is free software: you can redistribute it and/or modify
00007  * it under the terms of the GNU General Public License as published by
00008  * the Free Software Foundation, either version 3 of the License, or
00009  * any later version.
00010  *
00011  * vyp08 is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  * GNU General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License
00017  * along with vyp08.  If not, see <http://www.gnu.org/licenses/>.
00018  */
00019 
00020 #include "config.h"
00021 #include "vm.h"
00022 
00023 #include "cmd.h"
00024 #include "vypIO.h"
00025 
00026 #ifndef BUILDING_DOX
00027 #   include <assert.h>
00028 #   include <map>
00029 #   include <queue>
00030 #   include <stack>
00031 #   include <vector>
00032 #endif
00033 
00034 using namespace StreamDecorator;
00035 using std::string;
00036 
00037 // /////////////////////////////////////////////////////////////////////////////
00038 // Value implementation
00039 Value::Value():
00040     type(V_NULL),
00041     boolVal(false),
00042     intVal(0),
00043     doubleVal(0.0)
00044 {
00045 }
00046 std::ostream& operator<< (std::ostream &str, const Value::VType &type) {
00047     str << Color(C_LIGHT_BLUE);
00048     switch (type) {
00049         case Value::V_NULL:     str << "V_NULL";        break;
00050         case Value::V_BOOL:     str << "V_BOOL";        break;
00051         case Value::V_INT:      str << "V_INT";         break;
00052         case Value::V_DOUBLE:   str << "V_DOUBLE";      break;
00053         case Value::V_STRING:   str << "V_STRING";      break;
00054     }
00055     str << Color(C_NO_COLOR);
00056     return str;
00057 }
00058 std::ostream& operator<< (std::ostream &str, const Value &val) {
00059     Value::VType type = val.type;
00060     str << type;
00061     if (type == Value::V_NULL)
00062         return str;
00063 
00064     str << "(" << Color(C_YELLOW);
00065     switch (type) {
00066         case Value::V_BOOL:     str << (val.boolVal ? "true":"false");  break;
00067         case Value::V_INT:      str << val.intVal;      break;
00068         case Value::V_DOUBLE:   str << val.doubleVal;   break;
00069         case Value::V_STRING:   str << val.stringVal;   break;
00070         default:
00071             break;
00072     }
00073     str << Color(C_NO_COLOR) << ")";
00074     return str;
00075 }
00076 
00077 // /////////////////////////////////////////////////////////////////////////////
00078 // Var implementation
00079 Var::Var():
00080     used(false),
00081     initialized(false)
00082 {
00083 }
00084 
00085 // /////////////////////////////////////////////////////////////////////////////
00086 // ValueFactory implementation
00087 PValue ValueFactory::create() {
00088     PValue val(new Value);
00089     val -> type = Value::V_NULL;
00090     return val;
00091 }
00092 
00093 PValue ValueFactory::create(bool b) {
00094     PValue val(new Value);
00095     val -> type = Value::V_BOOL;
00096     val -> boolVal = b;
00097     return val;
00098 }
00099 
00100 PValue ValueFactory::create(int i) {
00101     PValue val(new Value);
00102     val -> type = Value::V_INT;
00103     val -> intVal = i;
00104     return val;
00105 }
00106 
00107 PValue ValueFactory::create(double d) {
00108     PValue val(new Value);
00109     val -> type = Value::V_DOUBLE;
00110     val -> doubleVal = d;
00111     return val;
00112 }
00113 
00114 PValue ValueFactory::create(const std::string &s) {
00115     PValue val(new Value);
00116     val -> type = Value::V_STRING;
00117     val -> stringVal = s;
00118     return val;
00119 }
00120 
00121 // /////////////////////////////////////////////////////////////////////////////
00122 // ValueStack implementation
00123 struct ValueStack::Private {
00124     typedef STD_STACK(PValue) TStack;
00125     TStack      st;
00126 
00127     Vm          *const vm;
00128     Private(Vm *vm_): vm(vm_) { }
00129 };
00130 ValueStack::ValueStack(Vm *vm):
00131     d(new Private(vm))
00132 {
00133 }
00134 ValueStack::~ValueStack() {
00135     delete d;
00136 }
00137 bool ValueStack::isEmpty() const {
00138     return d->st.empty();
00139 }
00140 
00141 void ValueStack::push(PValue val) {
00142 #if DEBUG_TRACE_VMSTACK
00143     std::cerr << Color(C_LIGHT_PURPLE) << "vmStack"
00144         << Color(C_NO_COLOR) << " <-- " << *val << std::endl;
00145 #endif
00146     d->st.push(val);
00147 }
00148 
00149 PValue ValueStack::pop() {
00150     PValue val;
00151     if (!d->st.empty()) {
00152         val = d->st.top();
00153         d->st.pop();
00154     }
00155 #if DEBUG_TRACE_VMSTACK
00156     std::cerr << Color(C_LIGHT_PURPLE) << "vmStack"
00157         << Color(C_NO_COLOR) << " --> " << *val << std::endl;
00158 #endif
00159     return val;
00160 }
00161 
00162 bool ValueStack::push(PValue val, const Token &t) {
00163     Vm *vm = d->vm;
00164     if (val->type == Value::V_NULL) {
00165         std::cerr << Error(E_ERROR, vm->fileName, "vmStack: attempt to push void value", t, true) << std::endl;
00166         return false;
00167     }
00168     vm->vmStack.push(val);
00169     return true;
00170 }
00171 
00172 bool ValueStack::pushFromVar(const Var &var, const Token &t) {
00173     Vm *vm = d->vm;
00174     PValue val(new Value(var.value));
00175     if (!var.initialized) {
00176         std::cerr << Error(E_ERROR, vm->fileName, "attempt to read uninitialized value", t) << std::endl;
00177         std::cerr << Error(E_NOTE, vm->fileName, "definition was here", var.defined) << std::endl;
00178         return false;
00179     }
00180     return push(val, t);
00181 }
00182 
00183 bool ValueStack::pop(PValue &val, const Token &t) {
00184     Vm *vm = d->vm;
00185     ValueStack &stack = vm->vmStack;
00186     if (stack.isEmpty()) {
00187         std::cerr << Error(E_ERROR, vm->fileName, "vmStack underflow", t, true) << std::endl;
00188         return false;
00189     }
00190     val = stack.pop();
00191     return true;
00192 }
00193 
00194 bool ValueStack::popToVar(Var &var, const Token &t) {
00195     Vm *vm = d->vm;
00196 
00197     // pop value from stack
00198     PValue val;
00199     if (!pop(val, t))
00200         return false;
00201 
00202     // check type
00203     Value::VType srcType = val->type;
00204     Value::VType dstType = var.value.type;
00205     if (srcType != dstType) {
00206         // TODO: mark this as internal error after testing as this is now checked statically
00207         std::cerr << Error(E_ERROR, vm->fileName, "type mismatch", t) << std::endl;
00208         std::cerr << Error(E_NOTE, vm->fileName, "expression type: ") << srcType << std::endl;
00209         std::cerr << Error(E_NOTE, vm->fileName, "   L-Value type: ") << dstType << std::endl;
00210         return false;
00211     }
00212 
00213     // store value
00214     var.value = *val;
00215     var.initialized = true;
00216     return true;
00217 }
00218 
00219 // /////////////////////////////////////////////////////////////////////////////
00220 // VarSet implementation
00221 struct VarSet::Private {
00222     typedef STD_VECTOR(PVar)        TVector;
00223     typedef STD_MAP(string, PVar)   TMap;
00224     TVector vect;
00225     TMap    vMap;
00226 };
00227 VarSet::VarSet():
00228     d(new Private)
00229 {
00230 }
00231 VarSet::~VarSet() {
00232     delete d;
00233 }
00234 
00235 VarSet& VarSet::operator= (const VarSet &other) {
00236     // clear self
00237     d->vect.clear();
00238     d->vMap.clear();
00239 
00240     // deep copy of items in other VarSet
00241     for(unsigned i=0; i<other.size(); i++) {
00242         const Var &var = *(other[i]);
00243         PVar pVar(new Var(var));
00244         this->add(pVar);
00245     }
00246 
00247     return *this;
00248 }
00249 
00250 bool VarSet::add(PVar var) {
00251     const string &name = var->name;
00252     if (!name.empty()) {
00253         // named variable
00254         Private::TMap::iterator i = d->vMap.find(name);
00255         if (i != d->vMap.end())
00256             // variable redefinition
00257             return false;
00258 
00259         d->vMap[name] = var;
00260     }
00261     d->vect.push_back(var);
00262     return true;
00263 }
00264 
00265 unsigned VarSet::size() const {
00266     return d->vect.size();
00267 }
00268 
00269 PVar VarSet::operator[] (unsigned pos) {
00270     assert(pos < size());
00271     return d->vect[pos];
00272 }
00273 
00274 PVar VarSet::operator[] (const std::string &name) {
00275     assert(!name.empty());
00276     PVar var;
00277     Private::TMap::iterator i = d->vMap.find(name);
00278     if (i != d->vMap.end())
00279         var = i->second;
00280     return var;
00281 }
00282 
00283 // /////////////////////////////////////////////////////////////////////////////
00284 // FncDeclaration implementation
00285 FncDeclaration::FncDeclaration()
00286 {
00287 }
00288 
00289 FncDeclaration::~FncDeclaration() {
00290 }
00291 
00292 FncDeclaration::FncDeclaration(const FncDeclaration &other):
00293     self(other.self)
00294 {
00295     args = other.args;
00296 }
00297 
00298 FncDeclaration& FncDeclaration::operator= (const FncDeclaration &other) {
00299     self = other.self;
00300     args = other.args;
00301     return *this;
00302 }
00303 
00304 bool operator== (const FncDeclaration &a, const FncDeclaration &b) {
00305     if (a.self.name != b.self.name)
00306         return false;
00307     if (a.self.value.type != b.self.value.type)
00308         return false;
00309     if (a.args.size() != b.args.size())
00310         return false;
00311     for (unsigned i=0; i< a.args.size(); i++) {
00312         const Value &aVal = a.args[i] -> value;
00313         const Value &bVal = b.args[i] -> value;
00314         if (aVal.type != bVal.type)
00315             return false;
00316     }
00317     return true;
00318 }
00319 
00320 bool operator!= (const FncDeclaration &a, const FncDeclaration &b) {
00321     return !operator== (a, b);
00322 }
00323 
00324 // /////////////////////////////////////////////////////////////////////////////
00325 // FncDefinition implementation
00326 FncDefinition::FncDefinition(Vm *vm_):
00327     vm(vm_),
00328     cmdList(new CmdList)
00329 {
00330 }
00331 
00332 FncDefinition::~FncDefinition() {
00333 }
00334 
00335 FncDefinition::FncDefinition(const FncDefinition &other):
00336     FncDeclaration(other),
00337     vm(other.vm),
00338     cmdList(other.cmdList)
00339 {
00340     vars = other.vars;
00341 }
00342 
00343 bool chkUnused(FncDefinition *fnc) {
00344     Vm *vm = fnc->vm;
00345     bool sane = true;
00346 
00347     // check for unused parameters
00348     const VarSet &argSet = fnc -> args;
00349     for (unsigned i = 0; i < argSet.size(); i++) {
00350         PVar arg = argSet[i];
00351         if (arg->used)
00352             continue;
00353 
00354         sane = false;
00355         std::cerr << Error(E_WARNING, vm->fileName, "unused function argument", arg->defined) << std::endl;
00356         std::cerr << Error(E_NOTE, vm->fileName, "defined in this function", fnc->self.defined) << std::endl;
00357     }
00358 
00359     // check for unused local variables
00360     const VarSet &varSet = fnc -> vars;
00361     for (unsigned i = 0; i < varSet.size(); i++) {
00362         PVar var = varSet[i];
00363         if (var->used)
00364             continue;
00365 
00366         sane = false;
00367         std::cerr << Error(E_WARNING, vm->fileName, "unused local variable", var->defined) << std::endl;
00368         std::cerr << Error(E_NOTE, vm->fileName, "defined in this function", fnc->self.defined) << std::endl;
00369     }
00370 
00371     return sane;
00372 }
00373 
00374 // /////////////////////////////////////////////////////////////////////////////
00375 // FncSet implementation
00376 struct FncSet::Private {
00377     typedef STD_MAP(string, FncDeclaration *)  TDeclMap;
00378     typedef STD_MAP(string, FncDefinition *)   TDefMap;
00379     TDeclMap    declMap;
00380     TDefMap     defMap;
00381 };
00382 
00383 FncSet::FncSet():
00384     d(new Private)
00385 {
00386 }
00387 
00388 FncSet::~FncSet() {
00389     for(
00390             Private::TDeclMap::iterator i = d->declMap.begin();
00391             i != d->declMap.end();
00392             i++)
00393         delete (i->second);
00394 
00395     for(
00396             Private::TDefMap::iterator i = d->defMap.begin();
00397             i != d->defMap.end();
00398             i++)
00399         delete (i->second);
00400 
00401     delete d;
00402 }
00403 
00404 bool FncSet::addDeclaration(FncDeclaration *decl) {
00405     const string &name = decl->self.name;
00406     Private::TDeclMap::iterator i = d->declMap.find(name);
00407     if (i == d->declMap.end()) {
00408         d->declMap[name] = decl;
00409         return true;
00410     }
00411     const FncDeclaration &prev = *(i->second);
00412     const FncDeclaration &curr = *decl;
00413     if (prev == curr) {
00414         delete decl;
00415         return true;
00416     }
00417     return false;
00418 }
00419 
00420 FncDeclaration* FncSet::getDeclaration(const std::string &name) {
00421     Private::TDeclMap::iterator i = d->declMap.find(name);
00422     if (i == d->declMap.end())
00423         return 0;
00424     else
00425         return i->second;
00426 }
00427 
00428 bool FncSet::addDefinition(FncDefinition *def) {
00429     const string &name = def->self.name;
00430     if (d->defMap.find(name) != d->defMap.end())
00431         // redefinition
00432         return false;
00433 
00434     Private::TDeclMap::iterator i = d->declMap.find(name);
00435     if (i == d->declMap.end()) {
00436         // add declaration as well
00437         d->declMap[name] = new FncDeclaration(*def);
00438     } else {
00439         const FncDeclaration &prev = *(i->second);
00440         const FncDeclaration &curr = *def;
00441         if (prev != curr)
00442             // decl/def mismatch
00443             return false;
00444     }
00445 
00446     // add definition
00447     d->defMap[name] = def;
00448 
00449     // check for unused arguments / local variables
00450     chkUnused(def);
00451     return true;
00452 }
00453 
00454 FncDefinition* FncSet::getDefinition(const std::string &name) {
00455     Private::TDefMap::iterator i = d->defMap.find(name);
00456     if (i == d->defMap.end())
00457         return 0;
00458     else
00459         return i->second;
00460 }
00461 
00462 void FncSet::getAllDefinitions(TVector &fncVect) {
00463     for (
00464             Private::TDefMap::iterator i = d->defMap.begin();
00465             i != d->defMap.end();
00466             i++
00467         )
00468     {
00469         fncVect.push_back(i->second);
00470     }
00471 }
00472 
00473 // /////////////////////////////////////////////////////////////////////////////
00474 // CmdList implementation
00475 struct CmdList::Private {
00476     typedef STD_VECTOR(PCmd) TVector;
00477     TVector vect;
00478 };
00479 CmdList::CmdList():
00480     d(new Private)
00481 {
00482 }
00483 CmdList::~CmdList() {
00484     delete d;
00485 }
00486 void CmdList::add(PCmd cmd) {
00487     d->vect.push_back(cmd);
00488 }
00489 bool CmdList::exec(FncDefinition *fnc) {
00490     for (
00491             Private::TVector::iterator i = d->vect.begin();
00492             i != d->vect.end();
00493             i++)
00494     {
00495         PCmd &cmd = *i;
00496 #if DEBUG_TRACE_CMD_LIST_EXEC
00497         std::cerr << Color(C_WHITE) << "exec: " << Color(C_NO_COLOR);
00498         cmd->toStream(std::cerr);
00499         std::cerr << std::endl;
00500 #endif
00501         if (!cmd->exec(fnc))
00502             return false;
00503     }
00504     return true;
00505 }
00506 void CmdList::toStream(std::ostream &str) const {
00507     str << Color(C_LIGHT_GREEN) << "{" << Color(C_NO_COLOR) << " ";
00508     for (
00509             Private::TVector::iterator i = d->vect.begin();
00510             i != d->vect.end();
00511             i++)
00512     {
00513         if (i != d->vect.begin())
00514             str << Color(C_LIGHT_GREEN) << "," << Color(C_NO_COLOR) << " ";
00515         PCmd &cmd = *i;
00516         cmd->toStream(str);
00517     }
00518     str << " " << Color(C_LIGHT_GREEN) << "}" << Color(C_NO_COLOR);
00519 }
00520 
00521 // /////////////////////////////////////////////////////////////////////////////
00522 // CalleeSet implementation
00523 struct CalleeSet::Private {
00524     typedef SHARED_PTR(Token)                   PToken;
00525     struct SortableToken {
00526         PToken t;
00527 
00528         SortableToken(const Token &t_): t(new Token(t_)) { }
00529         SortableToken(const SortableToken &other): t(other.t) { }
00530         SortableToken& operator=(const SortableToken &other) { t = other.t; return *this; }
00531         operator int() const { return -t->lineno; }
00532     };
00533     typedef STD_PRIORITY_QUEUE(SortableToken)   TTokenQueue;
00534     typedef SHARED_PTR(TTokenQueue)             PTokenQueue;
00535     typedef STD_MAP(string, PTokenQueue)        TMap;
00536     TMap map;
00537 };
00538 CalleeSet::CalleeSet():
00539     d(new Private)
00540 {
00541 }
00542 CalleeSet::~CalleeSet() {
00543     delete d;
00544 }
00545 void CalleeSet::add(std::string name, Token tCall) {
00546     Private::PTokenQueue queue;
00547 
00548     // name lookup
00549     Private::TMap::iterator i = d->map.find(name);
00550     if (i == d->map.end())
00551         // create new queue
00552         queue.reset(new Private::TTokenQueue);
00553     else
00554         // use existing queue
00555         queue = i->second;
00556 
00557     if (tCall.type != ETOKEN_NULL)
00558         // add token to queue (if any)
00559         queue->push(tCall);
00560 
00561     // move pointer (back) to map
00562     d->map[name] = queue;
00563 }
00564 
00565 bool CalleeSet::isCalled(std::string name) {
00566     return d->map.find(name) != d->map.end();
00567 }
00568 
00569 void CalleeSet::getNames(TStringList &list) {
00570     for (
00571             Private::TMap::iterator i = d->map.begin();
00572             i != d->map.end();
00573             i++)
00574         list.push_back(i->first);
00575 }
00576 
00577 bool CalleeSet::getCalls(std::string name, TTokenList &list) {
00578     // name lookup
00579     Private::TMap::iterator i = d->map.find(name);
00580     if (i == d->map.end())
00581         return false;
00582 
00583     // clone queue and copy to list (not very optimized)
00584     Private::TTokenQueue queue = *(i->second);
00585     while (!queue.empty()) {
00586         list.push_back(*(queue.top().t));
00587         queue.pop();
00588     }
00589 
00590     return true;
00591 }
00592 
00593 
00594 // /////////////////////////////////////////////////////////////////////////////
00595 // VmRunner implementation
00596 struct VmRunner::Private {
00597     Vm      *const vm;
00598     bool    hasError;
00599 
00600     Private(Vm *vm_):
00601         vm(vm_),
00602         hasError(false)
00603     {
00604     }
00605     void chkUnusedGlVars();
00606     void chkUnusedFncs();
00607     void chkFncRefs();
00608     bool run();
00609 };
00610 VmRunner::VmRunner(Vm *vm):
00611     d(new Private(vm))
00612 {
00613     d->chkUnusedGlVars();
00614     d->chkUnusedFncs();
00615     d->chkFncRefs();
00616 }
00617 VmRunner::~VmRunner() {
00618     delete d;
00619 }
00620 bool VmRunner::hasError() const {
00621     return d->hasError;
00622 }
00623 bool VmRunner::run() {
00624     return (d->hasError)
00625         ? false : d->run();
00626 }
00627 
00628 void VmRunner::Private::chkUnusedGlVars() {
00629     const VarSet &varSet = vm -> glVars;
00630     for (unsigned i = 0; i < varSet.size(); i++) {
00631         PVar var = varSet[i];
00632         if (var->used)
00633             continue;
00634         std::cerr << Error(E_WARNING, vm->fileName, "unused global variable", var->defined) << std::endl;
00635     }
00636 }
00637 
00638 void VmRunner::Private::chkUnusedFncs() {
00639     FncSet::TVector fncVect;
00640     vm -> fncSet.getAllDefinitions(fncVect);
00641     CalleeSet unusedSet;
00642     for (unsigned i = 0; i < fncVect.size(); i++) {
00643         const FncDefinition *fnc = fncVect[i];
00644         if (!vm->calleeSet.isCalled(fnc->self.name))
00645             unusedSet.add("", fnc->self.defined);
00646     }
00647     CalleeSet::TTokenList tList;
00648     unusedSet.getCalls("", tList);
00649     for (unsigned i = 0; i < tList.size(); i++)
00650         std::cerr << Error(E_WARNING, vm->fileName, "unused function", tList[i]) << std::endl;
00651 }
00652 
00653 void VmRunner::Private::chkFncRefs() {
00654     FncSet &fncSet = vm -> fncSet;
00655     CalleeSet &calleeSet = vm -> calleeSet;
00656     CalleeSet::TStringList calleeNames;
00657     calleeSet.getNames(calleeNames);
00658     for (unsigned i = 0; i < calleeNames.size(); i++) {
00659         const string &name = calleeNames[i];
00660         if (fncSet.getDefinition(name))
00661             // definition ok
00662             continue;
00663 
00664         hasError = true;
00665         std::cerr << Error(E_ERROR, vm->fileName, "unresolved reference to function", 0, name) << std::endl;
00666         FncDeclaration *decl = fncSet.getDeclaration(name);
00667         if (decl && decl->self.defined.lineno)
00668             std::cerr << Error(E_NOTE, vm->fileName, "declared here", decl->self.defined) << std::endl;
00669         CalleeSet::TTokenList callers;
00670         calleeSet.getCalls(name, callers);
00671         for (unsigned i = 0; i < callers.size(); i++)
00672             std::cerr << Error(E_NOTE, vm->fileName, "called from here", callers[i]) << std::endl;
00673     }
00674 }
00675 
00676 bool VmRunner::Private::run() {
00677     // main function lookup
00678     FncDefinition *mainFnc = vm -> fncSet.getDefinition("main");
00679 
00680     // create CallCmd for main
00681     Token tMain (ETOKEN_ID, 0, 0, 0.0, "main");
00682     CmdFactory cmdFactory(vm);
00683     PCmd callCmd = cmdFactory.createCall(tMain, 0, false);
00684 
00685     // call main
00686     if (!callCmd->exec(mainFnc))
00687         return false;
00688 
00689     // check vmStack offset
00690     if (vm->vmStack.isEmpty())
00691         // all ok
00692         return true;
00693 
00694     std::cerr << Error(E_ERROR, vm->fileName, "vmStack offset detected", tMain, true) << std::endl;
00695     return false;
00696 }
00697 
00698 

Generated on Sat Jul 4 18:32:59 2009 for vyp08 (compiler and interpreter of VYP08 language) by  doxygen 1.5.4