You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
515 lines
14 KiB
515 lines
14 KiB
#include <stack> |
|
#include "deptree.h" |
|
|
|
// Create variable node |
|
// v - variable name |
|
// vars - definitions of variables |
|
// dvars - variables which are already in tree |
|
// callstack - path in tree used for detections of loops. |
|
int DepTree::CreateNodeFromVar(const std::string& v, VarType& vars, DepTree::DepTreeVars& dvars, DepTree::CallStack& callstack) |
|
{ |
|
COUT(DEBUG)<<"DepTree::CreateNodeFromVar "<<v<<std::endl; |
|
if(vars.count(v)==0) |
|
{ |
|
COUT(ERROR)<<"Definition of variable "<<v<<" not found"<<std::endl; |
|
return 1; |
|
} |
|
|
|
UsedType ids=UsedVars(vars[v]); |
|
|
|
dvars[v]=this; |
|
type=DepTree::VAR; |
|
name=v; |
|
DepTreeVars::const_iterator d; |
|
int ret; |
|
|
|
exe.splice(exe.begin(),vars[v]); // Move expression into node |
|
callstack.insert(this); |
|
for(auto& i:ids) |
|
{ |
|
d=dvars.find(i); |
|
if(d==dvars.end()) |
|
{ |
|
auto n=*childrens.insert(new DepTree).first; |
|
n->parents.insert(this); |
|
ret=n->CreateNodeFromVar(i,vars,dvars,callstack); |
|
if(ret!=0) |
|
{ |
|
const struct grammatic_location& loc=exe.back().Location(); |
|
COUT(ERROR)<<" in definition of variable "<<name<<" at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
return ret; |
|
} |
|
} |
|
else |
|
{ |
|
if(callstack.find(d->second)!=callstack.end()) |
|
{ |
|
COUT(ERROR)<<"Circular dependency of variable "<<name<<" from variable "<<i<<std::endl; |
|
return 1; |
|
} |
|
childrens.insert(d->second); |
|
d->second->parents.insert(this); |
|
} |
|
} |
|
callstack.erase(this); |
|
|
|
return 0; |
|
} |
|
|
|
// Creating PRINT or SAVE node |
|
// list - type of node |
|
// vars - definitions of variables |
|
// exp - expression to print or save |
|
// dvars - variables which are already in tree |
|
int DepTree::CreateNodeFromSP(DepTree::NodeType list, VarType& vars, ExecExpr& exp, DepTreeVars& dvars) |
|
{ |
|
if(list!=DepTree::SAVE && list!=DepTree::PRINT) |
|
{ |
|
COUT(ERROR)<<"Internal error, incorrect NodeType in DepTree::CreateNodeFromSP()."<<std::endl; |
|
return 2; |
|
} |
|
|
|
UsedType ids=UsedVars(exp); |
|
CallStack callstack; |
|
DepTreeVars::const_iterator d; |
|
int ret; |
|
|
|
type=list; |
|
exe.splice(exe.end(),exp); // Move expression into node |
|
COUT(DEBUG)<<"DepTree::CreateNodeFromSP "<<DumpExpr(exe)<<std::endl; |
|
|
|
for(const auto& i:ids) |
|
{ |
|
d=dvars.find(i); // Is variable already in tree? |
|
if(dvars.end()==d) // No |
|
{ |
|
auto n=*childrens.insert(new DepTree).first; |
|
n->parents.insert(this); |
|
ret=n->CreateNodeFromVar(i,vars,dvars,callstack); |
|
if(ret!=0) |
|
{ |
|
const struct grammatic_location& loc=exe.front().Location(); |
|
COUT(ERROR)<<" in "<<((type==DepTree::SAVE)?"save":"print")<<" directive at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
return ret; |
|
} |
|
} |
|
else // Variable already in tree. Just establish links. |
|
{ |
|
childrens.insert(d->second); |
|
d->second->parents.insert(this); |
|
} |
|
} |
|
|
|
return 0; |
|
} |
|
|
|
// Create dependency tree from expressions to save and print and definitions ov variables |
|
int DepTree::CreateTree(ExecType& save, ExecType& print, VarType& vars) |
|
{ |
|
if(parents.size()!=0) |
|
{ |
|
COUT(ERROR)<<"Internal error, DepTree::CreateGlobalTree() call for non-root node."<<std::endl; |
|
return 2; |
|
} |
|
|
|
DepTreeVars dvars; |
|
|
|
type=DepTree::ROOT; |
|
for(auto& i:save) |
|
{ |
|
auto n=*childrens.insert(new DepTree).first; |
|
n->parents.insert(this); |
|
auto ret=n->CreateNodeFromSP(DepTree::SAVE,vars,i,dvars); |
|
if(ret!=0) return ret; |
|
} |
|
for(auto& i:print) |
|
{ |
|
auto n=*childrens.insert(new DepTree).first; |
|
n->parents.insert(this); |
|
auto ret=n->CreateNodeFromSP(DepTree::PRINT,vars,i,dvars); |
|
if(ret!=0) return ret; |
|
} |
|
|
|
return 0; |
|
} |
|
|
|
// Get list of nodes without dependencies |
|
DepTree::LeafVector DepTree::FindLeafNodes() const |
|
{ |
|
LeafVector leafs; |
|
// Visited nodes |
|
CallStack visited; |
|
std::stack<NodeVector::const_iterator> path,ends; |
|
NodeVector::const_iterator it,end; |
|
|
|
// ascending to root |
|
const DepTree* root=this; |
|
while(root->parents.size()!=0) root=*(root->parents.begin()); |
|
|
|
const DepTree* curnode=root; |
|
visited.insert(curnode); |
|
it=curnode->childrens.begin(); |
|
end=curnode->childrens.end(); |
|
|
|
while(true) |
|
{ |
|
if(it!=end) |
|
{ |
|
if(visited.find(*it)!=visited.end()) {++it; continue;} |
|
path.push(it); ends.push(end); |
|
curnode=(*it); |
|
visited.insert(curnode); |
|
it=curnode->childrens.begin(); |
|
end=curnode->childrens.end(); |
|
if(it==end) leafs.push_back(const_cast<DepTree*>(curnode)); |
|
} |
|
else |
|
{ |
|
if(path.size()==0) break; |
|
it=path.top(); path.pop(); |
|
end=ends.top(); ends.pop(); |
|
++it; |
|
} |
|
} |
|
|
|
return leafs; |
|
} |
|
|
|
|
|
// Dump tree contents |
|
void DepTree::DumpTree() const |
|
{ |
|
// Visited nodes |
|
CallStack visited; |
|
std::stack<NodeVector::const_iterator> path,ends; |
|
NodeVector::const_iterator it,end; |
|
|
|
// ascending to root |
|
const DepTree* root=this; |
|
while(root->parents.size()!=0) root=*(root->parents.begin()); |
|
|
|
const DepTree* curnode=root; |
|
visited.insert(curnode); |
|
it=curnode->childrens.begin(); |
|
end=curnode->childrens.end(); |
|
|
|
while(true) |
|
{ |
|
if(it!=end) |
|
{ |
|
if(visited.find(*it)!=visited.end()) {++it; continue;} |
|
path.push(it); ends.push(end); |
|
curnode=(*it); |
|
visited.insert(curnode); |
|
if(SAVE==curnode->type) COUT(NORMAL)<<"save" <<DumpExpr(curnode->exe)<<";"<<std::endl; |
|
if(PRINT==curnode->type) COUT(NORMAL)<<"print"<<DumpExpr(curnode->exe)<<";"<<std::endl; |
|
if(VAR==curnode->type) COUT(NORMAL)<<curnode->name<<"="<<DumpExpr(curnode->exe)<<";"<<std::endl; |
|
it=curnode->childrens.begin(); |
|
end=curnode->childrens.end(); |
|
} |
|
else |
|
{ |
|
if(path.size()==0) break; |
|
it=path.top(); path.pop(); |
|
end=ends.top(); ends.pop(); |
|
++it; |
|
} |
|
} |
|
} |
|
|
|
|
|
// Check if all functions are defined |
|
int DepTree::CheckFunctions() const |
|
{ |
|
// Visited nodes |
|
CallStack visited; |
|
std::stack<NodeVector::const_iterator> path,ends; |
|
NodeVector::const_iterator it,end; |
|
|
|
// ascending to root |
|
const DepTree* root=this; |
|
while(root->parents.size()!=0) root=*(root->parents.begin()); |
|
|
|
const DepTree* curnode=root; |
|
visited.insert(curnode); |
|
it=curnode->childrens.begin(); |
|
end=curnode->childrens.end(); |
|
|
|
while(true) |
|
{ |
|
if(it!=end) |
|
{ |
|
if(visited.find(*it)!=visited.end()) {++it; continue;} |
|
path.push(it); ends.push(end); |
|
curnode=(*it); |
|
visited.insert(curnode); |
|
for(const auto& se: curnode->exe) if(StackElem::TYPE_FUNCTION==se.T() && G_funcs.find(se.Name())==G_funcs.end()) |
|
{ |
|
const struct grammatic_location& loc=se.Location(); |
|
COUT(ERROR)<<"Unknown function "<<se.Name()<<" at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
return 1; |
|
} |
|
|
|
it=curnode->childrens.begin(); |
|
end=curnode->childrens.end(); |
|
} |
|
else |
|
{ |
|
if(path.size()==0) break; |
|
it=path.top(); path.pop(); |
|
end=ends.top(); ends.pop(); |
|
++it; |
|
} |
|
} |
|
return 0; |
|
} |
|
|
|
|
|
// Multi-threaded version |
|
void* TreeEvaluateM(void* arg) |
|
{ |
|
struct timespec skip={0,10000000}; |
|
DepTree::thread_params* p=reinterpret_cast<DepTree::thread_params*>(arg); |
|
DepTree* leaf; |
|
bool err; |
|
|
|
while(true) |
|
{ |
|
// Begin critical section (access to root) |
|
pthread_mutex_lock(&p->root_mtx); |
|
// Check, if all done, or error happens? |
|
if(0==p->root->childrens.size() || 0!=p->exitcode) {pthread_mutex_unlock(&p->root_mtx); return nullptr;} |
|
// End critical section |
|
pthread_mutex_unlock(&p->root_mtx); |
|
|
|
// Begin critical section (access to leafs) |
|
pthread_mutex_lock(&p->leaf_mtx); |
|
// Check, if some work available? |
|
if(0==p->leafs.size()) {pthread_mutex_unlock(&p->leaf_mtx); nanosleep(&skip,nullptr); continue;} |
|
// Select working node |
|
leaf=*(p->leafs.begin()); |
|
// and remove its from list |
|
p->leafs.erase(p->leafs.begin()); |
|
// End critical section |
|
pthread_mutex_unlock(&p->leaf_mtx); |
|
|
|
if(DepTree::SAVE==leaf->type) |
|
{ |
|
err=false; |
|
|
|
std::unique_ptr<const ObjectList> ol(dynamic_cast<const ObjectList*>(Evaluate(leaf->exe,&err))); // No check for return value, trust in grammatical parser |
|
if(err) |
|
{ |
|
const struct grammatic_location& loc=leaf->exe.front().Location(); |
|
COUT(ERROR)<<" in instruction save at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
if(!Save(ol.get())) |
|
{ |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
// This leaf can have only one parent - root |
|
// Begin critical section (access to root) |
|
pthread_mutex_lock(&p->root_mtx); |
|
(*leaf->parents.begin())->childrens.erase(leaf); |
|
// End critical section |
|
pthread_mutex_unlock(&p->root_mtx); |
|
} |
|
|
|
if(DepTree::PRINT==leaf->type) |
|
{ |
|
err=false; |
|
|
|
std::unique_ptr<const ObjectList> ol(dynamic_cast<const ObjectList*>(Evaluate(leaf->exe,&err))); // No check for return value, trust in grammatical parser |
|
if(err) |
|
{ |
|
const struct grammatic_location& loc=leaf->exe.front().Location(); |
|
COUT(ERROR)<<" in instruction print at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
if(!Print(ol.get())) |
|
{ |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
|
|
// Begin critical section (access to root) |
|
pthread_mutex_lock(&p->root_mtx); |
|
// This leaf can have only one parent - root |
|
(*leaf->parents.begin())->childrens.erase(leaf); |
|
// End critical section |
|
pthread_mutex_unlock(&p->root_mtx); |
|
} |
|
|
|
if(DepTree::VAR==leaf->type) |
|
{ |
|
const ObjectBase *eob; |
|
|
|
// Main working call |
|
err=false; |
|
eob=Evaluate(leaf->exe,&err); |
|
if(err) |
|
{ |
|
const struct grammatic_location& loc=leaf->exe.front().Location(); |
|
COUT(ERROR)<<" in definition of variable "<<leaf->name<<" at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
|
|
// Begin critical section (access to tree structure) |
|
pthread_mutex_lock(&p->tree_mtx); |
|
for(auto& i:leaf->parents) |
|
{ |
|
// leaf not children of anyone |
|
i->childrens.erase(leaf); |
|
// Replace variable on eob |
|
ReplaceVar(i->exe,leaf->name,eob); |
|
|
|
// Begin critical section (access to leafs) |
|
pthread_mutex_lock(&p->leaf_mtx); |
|
// If node have no children, it's a new leaf node |
|
if(0==i->childrens.size() && DepTree::ROOT!=i->type) p->leafs.push_back(i); |
|
pthread_mutex_unlock(&p->leaf_mtx); |
|
// End critical section |
|
} |
|
// End critical section |
|
pthread_mutex_unlock(&p->tree_mtx); |
|
delete eob; |
|
} |
|
|
|
leaf->parents.clear(); |
|
delete leaf; |
|
} |
|
return nullptr; |
|
} |
|
|
|
|
|
// Single-threaded version |
|
void* TreeEvaluate(void* arg) |
|
{ |
|
DepTree::thread_params* p=reinterpret_cast<DepTree::thread_params*>(arg); |
|
DepTree* leaf; |
|
bool err; |
|
|
|
while(0!=p->leafs.size()) |
|
{ |
|
// Select working node |
|
leaf=*(p->leafs.begin()); |
|
// and remove its from list |
|
p->leafs.erase(p->leafs.begin()); |
|
|
|
if(DepTree::SAVE==leaf->type) |
|
{ |
|
err=false; |
|
|
|
std::unique_ptr<const ObjectList> ol(dynamic_cast<const ObjectList*>(Evaluate(leaf->exe,&err))); // No check for return value, trust in grammatical parser |
|
if(err) |
|
{ |
|
const struct grammatic_location& loc=leaf->exe.front().Location(); |
|
COUT(ERROR)<<" in instruction save at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
// eob is evaluated object |
|
if(!Save(ol.get())) |
|
{ |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
// This leaf can have only one parent - root |
|
(*leaf->parents.begin())->childrens.erase(leaf); |
|
} |
|
|
|
if(DepTree::PRINT==leaf->type) |
|
{ |
|
err=false; |
|
|
|
std::unique_ptr<const ObjectList> ol(dynamic_cast<const ObjectList*>(Evaluate(leaf->exe,&err))); // No check for return value, trust in grammatical parser |
|
if(err) |
|
{ |
|
const struct grammatic_location& loc=leaf->exe.front().Location(); |
|
COUT(ERROR)<<" in instruction print at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
if(!Print(ol.get())) |
|
{ |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
// This leaf can have only one parent - root |
|
(*leaf->parents.begin())->childrens.erase(leaf); |
|
} |
|
|
|
if(DepTree::VAR==leaf->type) |
|
{ |
|
const ObjectBase *eob; |
|
|
|
// Main working call |
|
err=false; |
|
eob=Evaluate(leaf->exe,&err); |
|
if(err) |
|
{ |
|
const struct grammatic_location& loc=leaf->exe.front().Location(); |
|
COUT(ERROR)<<" in definition of variable "<<leaf->name<<" at line "<<loc.first_line<<", position "<<loc.first_column<<std::endl; |
|
for(const auto& inc: loc.incstack) COUT(ERROR)<<" included from "<<inc.filename<<" at line "<<inc.line<<", position "<<inc.column<<std::endl; |
|
p->exitcode=1; |
|
return nullptr; |
|
} |
|
|
|
for(auto& i:leaf->parents) |
|
{ |
|
// leaf not children of anyone |
|
i->childrens.erase(leaf); |
|
// Replace variable on eob |
|
ReplaceVar(i->exe,leaf->name,eob); |
|
// If node have no children, it's a new leaf node |
|
if(0==i->childrens.size() && DepTree::ROOT!=i->type) p->leafs.push_back(i); |
|
} |
|
delete eob; |
|
} |
|
leaf->parents.clear(); |
|
delete leaf; |
|
} |
|
return nullptr; |
|
} |
|
|
|
|
|
int DepTree::EvaluateTree(unsigned int nthreads) |
|
{ |
|
DepTree::thread_params p; |
|
|
|
p.exitcode=0; |
|
p.leafs=FindLeafNodes(); |
|
|
|
if(1==nthreads) TreeEvaluate(&p); |
|
else |
|
{ |
|
pthread_t* threads=new pthread_t[nthreads-1]; |
|
p.root=this; |
|
pthread_mutex_init(&p.leaf_mtx,nullptr); |
|
pthread_mutex_init(&p.root_mtx,nullptr); |
|
pthread_mutex_init(&p.tree_mtx,nullptr); |
|
while(0!=p.root->parents.size()) p.root=*(p.root->parents.begin()); |
|
|
|
for(unsigned int i=0;i<nthreads-1;++i) pthread_create(threads+i,nullptr,&TreeEvaluateM,&p); |
|
TreeEvaluateM(&p); |
|
for(unsigned int i=0;i<nthreads-1;++i) pthread_join(threads[i],nullptr); |
|
delete[] threads; |
|
pthread_mutex_destroy(&p.leaf_mtx); |
|
pthread_mutex_destroy(&p.root_mtx); |
|
pthread_mutex_destroy(&p.tree_mtx); |
|
} |
|
return p.exitcode; |
|
}
|
|
|