gmt-makemap/src/deptree.cpp

#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;
}