/////////////////////////////////////////////////////////////////////
//  grammar.cpp - provides detectors for grammatical constructs    //
//  ver 1.5                                                        //
//                                                                 //
//  Language:     Visual C++, ver 7.0                              //
//  Platfrom:     Dell Dimension 8100, Windows 2000, SP 2.0        //
//  Application:  Prototype for CSE687 Pr#2, Spring 2003           //
//  Author:       Jim Fawcett, CST 2-187, Syracuse University      //
//                (315) 443-3948, jfawcett@twcny.rr.com            //
/////////////////////////////////////////////////////////////////////

#include "grammar.h"
#include <exception>
#include <cctype>

scopeStack grammar::scope;
std::set<sstr> grammar::types;

//----< extract context information from scopeStack >----------

sstr scopeStack::context()
{
  sstr temp;
  std::vector<scope>::iterator iter;
  for(iter=stack.begin(); iter!=stack.end(); ++iter)
    if(iter->_name != "")
      temp += iter->_name + "::";
  return temp;
}
//----< return an identifier's type >--------------------------

sstr typeTable::type(csstr& name)
{
  iterator iter = table.find(name);
  if(iter != table.end())
    return iter->second;
  return "unknown";
}
//----< display identifiers and their types >------------------

sstr typeTable::show(size_t leadingSpaces)
{
  sstr space(leadingSpaces,' ');
  std::map<sstr,sstr>::iterator iter;
  sstr accum;
  for(iter=table.begin(); iter!=table.end(); ++iter)
    accum += sstr("\n") + space + iter->second + " " + iter->first; 
  return accum;
}
//
//----< is this token an identifier? >-------------------------

bool grammar::identifier(csstr& tok)
{
  if(!isalpha(tok[0]) && (tok[0] != '_'))
    return false;
  for(int i=1; i<(int)tok.size(); ++i)
    if(!isalnum(tok[i]) && (tok[i] != '_'))
      return false;
  return true;
}
//----< find complement token >--------------------------------

sstr grammar::complement(csstr &tok)
{
  if(tok == "<") return ">";
  if(tok == ">") return "<";
  if(tok == "(") return ")";
  if(tok == ")") return "(";
  if(tok == "[") return "]";
  if(tok == "]") return "[";
  return "none";
}
//
//----< collect complete identity >----------------------------
//
//  collect object (obj.fun()) and pointer (ptr->fun()) 
//  prefixes for invocations
//
sstr grammar::getQualifiedIdentifier(size_t pos)
{
  if(pos<0 || _se.length()<=pos)
  {
    throw std::domain_error("in grammar::getQualifiedIdentifer");
    return _se[0];
  }
  if(pos == 0)
    return _se[0];

  sstr id = _se[pos];
  --pos;

  // look for <...> or [] or ()

  if(!identifier(id))
  {
    sstr comp = complement(id);
    while(pos>0)
    {
      id = _se[pos] + id;
      --pos;
      if(_se[pos+1] == comp)
        break;
    }
    id = _se[pos] + id;
    --pos;
    if(pos <= 0)
      return id;
  }
  if(_se[pos] == "." || _se[pos] == "->")
  {
    if(!identifier(_se[pos-1]))
      return id;
    id = _se[pos--] + id;
    if(pos >= 0)
      id = _se[pos] + id;
  }
  return id;
}
//
//----< is this string a special key? >------------------------

bool grammar::specialKeys(csstr &s)
{
  static sstr keys[5] = { "for", "if", "switch", "while", "(" };
  for(int i=0; i<5; ++i)
    if(s==keys[i])
      return true;
  return false;
}
//----< is this a function definition? >-----------------------

bool grammar::functionDef()
{
  if(_se[_se.length()-1] != std::string("{"))
    return false;
  size_t len = _se.find("(");
  if(len == _se.length())
    return false;
  if(specialKeys(_se[len-1]))
    return false;
  return true;
}
//----< is this a function declaration? >----------------------

bool grammar::functionDec()
{
  if(_se[_se.length()-1] != std::string(";"))
    return false;
  if(scope.type() == "function")
    return false;
  size_t len = _se.find("(");
  if(len == _se.length())
    return false;
  if(specialKeys(_se[len-1]))
    return false;
  return true;
}
//
//----< is this a function invocation? >-----------------------
//
//  if function invocation on or after len
//    returns position of function name
//  else 
//    returns length of semiExp
//  Designed this way so you can detect multiple invocations
//  in a single semiExp
//
size_t grammar::invocation(size_t len=0)
{
  if(scope.type() != "function")
    return _se.length();
  while((len = _se.find("(",len)) != _se.length())
  {
    if(len == 0)
      return _se.length();  // grouping paren

    // should be a name or name<arg>

    if(!identifier(_se[len-1]) && !(_se[len-1] == ">"))
      return _se.length();
    
    if(!keyword(_se[len-1]))
    {
      // look for old style cast

      size_t pos = _se.find(")",len);
      if(pos < _se.length()-1 && !identifier(_se[pos+1])) 
        return len;           // not cast
      else
        return _se.length();  // is cast
    }
    ++len;
  }
  return _se.length();
}
//----< is this an access specifier? >-------------------------

bool grammar::accessSpecifier(const sstr& tok)
{
  return (tok=="public" || tok=="protected" || tok=="private");
}
//----< is this a prefix declaration operator? >---------------

bool grammar::prefixOper(const sstr& tok)
{
  return (tok == "&" || tok == "*");
}
//
//----< is this a postfix declaration operator? >--------------

bool grammar::postfixOper(const sstr& tok)
{
  return (tok == "[" || tok == "]" || tok == "(" || tok == ")");
}
//----< is this a declaration specifier? >---------------------

bool grammar::specifier(const sstr& tok)
{
  const int tabSize = 15;
  static sstr specs[tabSize] = 
  {
    // property specifier
    "explicit", "extern", "friend", "inline", "static", 
    "typename", "virtual",
    // type specifier
    "auto", "const", "mutable", "signed", "register", 
    "template", "unsigned", "volatile"
  };

  for(int i=0; i<tabSize; ++i)
    if(tok == specs[i])
      return true;
  return false;
}
//----< extract type and identifier from declaration >---------
//
//  remove specifiers and operators to get type and name
//
void grammar::saveIdAndType(typeTable& typeTab)
{
  std::list<sstr> temp = compress();
  std::list<sstr>::iterator it;

  if(temp.size() >= 2)
  {
    std::list<sstr>::iterator iter = temp.begin();
    sstr type = *iter;
    ++iter;
    sstr name = context() + *iter;
    typeTab.push(name,type);
  }
}
//
//----< extract types and identifiers from parameter list >----

void grammar::saveParamsAndTypes(typeTable& typeTab)
{
/*
  Extract type information by taking these steps:
  - is list empty?  if so return
  - for each comma extract preceding declaration
    and save in typeTable
  - extract last declaration and save in typeTable
*/
}
//----< is tok a keyword? >------------------------------------

bool grammar::keyword(const sstr &tok)
{
  const int ArrSize = 74;
  static char* keyArray[ArrSize] =
  {
    "and", "and_eq", "asm", "auto", "bitand", "bitor",
    "bool", "break", "case", "catch", "char", "class",
    "compl", "const", "const_cast", "continue", "default", "delete",
    "do", "double", "dynamic_cast", "else", "enum", "explicit",
    "export", "extern", "false", "float", "for", "friend",
    "goto", "if", "inline", "int", "long", "mutable",
    "namespace", "new", "not", "not_eq", "operator", "or",
    "or_eq", "private", "protected", "public", "register", "reinterpret_cast",
    "return", "short", "signed", "sizeof", "static", "static_cast", 
    "struct", "switch", "template", "this", "throw", "true",
    "try", "typedef", "typeid", "typename", "union", "unsigned",
    "using", "virtual", "void", "volatile", "wchar_t", "while",
    "xor", "xor_eq"
  };
  static std::set<sstr> keys(&keyArray[0],&keyArray[ArrSize]);

  if(keys.find(tok) != keys.end())
    return true;
  return false;
}
//
//----< return a compressed list >-----------------------------
//
//  remove template args, scope qualifiers, and declaration specifiers
//
std::list<sstr> grammar::compress()
{
  std::list<sstr> temp;

  // skip template arguments

  bool inTempParam = false;
  for(size_t i=0; i<_se.length(); ++i)
  {
    if(_se[i] == "<")
    {
      inTempParam = true;
      continue;
    }
    if(_se[i] == ">")
    {
      inTempParam = false;
      continue;
    }
    if(!inTempParam /*&& identifier(_se[i]) && !keyword(_se[i])*/)
      temp.push_back(_se[i]);
  }

  // skip scope qualifiers

  std::list<sstr> moreTemp;
  std::list<sstr>::iterator iter, nextIter;
  for(iter=temp.begin(); iter!=temp.end(); ++iter)
  {
    nextIter = iter;
    if(++nextIter != temp.end())
      if(*iter != "::" && *nextIter != "::")
        moreTemp.push_back(*iter);
  }

  // skip specifiers and type operators

  std::list<sstr> stillMoreTemp;
  for(iter = moreTemp.begin(); iter!=moreTemp.end(); ++iter)
  {
    if(*iter == "=")
      break;
    if(postfixOper(*iter))
      break;
    if(!specifier(*iter) && !prefixOper(*iter) && !accessSpecifier(*iter))
      if(":" != *iter)
        stillMoreTemp.push_back(*iter);
  }
  return stillMoreTemp;
}
//
//----< is this a declaration> >-------------------------------

bool grammar::declar()
{
  if(_se.length() < 2 || (_se[_se.length()-1] != ";"))
    return false;

  std::list<sstr> temp = compress();
  
  // is declaration if first two are non-keyword identifiers

  if(temp.size() < 2)
    return false;
  std::list<sstr>::iterator iter = temp.begin();
  if(identifier(*iter) && !keyword(*iter))
  {
    ++iter;
    if(identifier(*iter) && !keyword(*iter))
    {
      return true;
    }
  }
  return false;
}
//----< entering a new scope? >--------------------------------

bool grammar::intoScope()
{
  if(_se[_se.length()-1] != std::string("{"))
    return false;
  return true;
}
//----< leaving a scope? >-------------------------------------

bool grammar::outofScope()
{
  if(_se[_se.length()-1] != std::string("}"))
    return false;
  return true;
}
//----< process changes in scope >-----------------------------

void grammar::processScope()
{
  if(intoScope())
    getScopeInfo();
  else if (outofScope())
    scope.pop();
}
//
//----< is this a qualified type? >----------------------------

bool grammar::qualifiedType(csstr& tok)
{
  const int numTypes = 6;
  static sstr qType[numTypes] = { 
     "class", "namespace", "struct", "enum", "union", "typedef" 
  };
  for(int i=0; i<numTypes; ++i)
    if(qType[i] == tok)
      return true;
  return false;
}
//----< look for a qualified type >----------------------------

size_t grammar::getQualifiedType()
{
  for(size_t i=0; i<_se.length()-1; ++i)
    if(qualifiedType(_se[i]))
    {
      if(i>0 && _se[i-1]=="<")  // skip template < class T >
        return _se.length();
      return i;
    }
  return _se.length();
}
//----< collect type information >-----------------------------

void grammar::saveType()
{
  if(_se[_se.length()-1] != std::string("{"))
    return;
  size_t i = getQualifiedType();
  if(i < _se.length()-1)
  {
    if(i>0 && _se[i-1] == "<")  // skip template < class T >
      return;
    types.insert(_se[i+1]);
  }
}
//
//----< collect scope information >----------------------------
//
//  pushes context information onto context stack
//  you must pop stack when you leave the context
//
bool grammar::getScopeInfo()
{
  if(_se[_se.length()-1] != std::string("{"))
    return false;
  size_t i = getQualifiedType();
  if(i < _se.length()-1)
  {
    scope.push(_se[i],_se[i+1]);
    return true;
  }
  if(functionDef())
  {
    size_t len = _se.find("::");
    if(len == _se.length() || len == 0)
      scope.push("function","");
    else
      scope.push("function",_se[len-1]);
    return true;
  }
  scope.push(scope.type(),"");
  return false;
}
//----< show scope stack contents >----------------------------

sstr grammar::showScope()
{
  sstr temp;
  size_t size = scope.size();
  for(size_t i=0; i<size; ++i)
  {
    temp += "\n  ";
    temp += scope.type() + ", ";
    temp += scope.name();
  }
  return temp;
}
//----< display known types >----------------------------------

sstr grammar::showTypes()
{
  sstr temp;
  std::set<sstr>::iterator iter;
  for(iter=types.begin(); iter!=types.end(); ++iter)
    temp += sstr("\n  ") + *iter;
  temp += "\n";
  return temp;
}
//
#ifdef TEST_GRAMMAR

#include <iostream>
#include <fstream>
using namespace std;

int main(int argc, char *argv[])
{
  cout << "\n  Currently this test stub just illustrates scope analysis."
       << "\n  To see more grammatical processing, look at the output of"
       << "\n  the executive module."
       << "\n ===========================================================\n";

  try
  {
    if(argc==1)
    {
      cout << "\n  please enter name of file to process on command line\n\n";
      return 1;
    }
    ifstream in(argv[1]);
    if(!in.good())
    {
      cout << "\n  can't read file " << argv[1] << "\n\n";
      return 1;
    }
    semiExp se(in);
    while(se.get())
    {
      cout << '\n';
      se.display();
      grammar gr(se);
      if(gr.include())
      {
        cout << "\n    is an include statement";
        continue;
      }
      if(gr.functionDef())
        cout << "\n    is a function definition";
      if(gr.functionDec())
        cout << "\n    is a function declaration";
      if(gr.invocation(0) != se.length())
        cout << "\n    is a function invocation";
      if(gr.intoScope())
      {
        cout << "\n    entering a new scope: "; 
      }
      if(gr.outofScope())
      {
        cout << "\n    leaving a scope";
      }
      cout << "\n    context: " << gr.context();
      cout << "\n    context type: " << gr.scopeType();
    }
  }
  catch(std::exception &e)
  {
    cout << "\n  " << e.what() << "\n\n";
  }
}
#endif