/*
   checktree.cc -- illustrate how to confirm validity of an abstract syntax tree

Author:  Larry Morell

Algorithm:

   The program checks the semantic requirements (represented by .N. ) of the  following grammar:

PROGRAM        ::= <scanner-list> SCANNER-LIST </scanner-list>
SCANNER-LIST ::= SCANNER | SCANNER SCANNER-LIST
SCANNER  ::= <scanner> NAME ALPHABET STATES START FINAL-STATES TRANSITION-TABLE </scanner>
NAME         ::= <name>.1.</name>
ALPHABET     ::= <alphabet> .2. </alphabet>
STATES       ::= <states> STATE-LIST </states>
STATE-LIST   ::= STATE | STATE STATE-LIST
FINAL-STATES ::= <final-states> STATE-LIST </final-states>
STATE            ::= <state> .4. </state>
START        ::= <start> .4. </final>
TRANSITION-TABLE ::= <transition-table> TRANSITION-LIST </transition-table>
TRANSITION-LIST  ::= TRANSITION | TRANSITION TRANSITION-LIST
TRANSITION       ::= <transition> INPUT STATE NEXTSTATE </transition>
INPUT            ::= <input> .3. </input>
NEXTSTATE        ::= <nextstate> .4. </nextstate>

Check for:
# An FA name that contains a non-letter.
# A state that is not a number.
# A state number that is not in the list of states.
# An input character that is not in the alphabet. 

Strategy:

Create a procedure for major subtrees in the tree 
Each such procedure does one or more of the following analyses:
o Retrieves values from the subtree to support later processing
o Check values in the subtree for consistency with previously
  stored values.
o Call other checking procedures to check the components of
  the subtree.
For example:

The tree submitted as the parameter might look like:

               n -->states
                      |
         --------------------------
         |    |    |    |    |    |
         1    2    3    4    5    6

1 is linked to 2, which is linked to 3, ...  via right pointers


bool checkStates (BinNode *n) {
   BinNode *stateptr = left(n);
   while  (stateptr != NULL) {
      string info = stateptr->getInfo();
      state[statemax] = info;
      for (int i=0; i < info.length(); i++) {
         char ch = info[i];
         if (ch < '0' || ch > '9') {
            cout << "State " << info 
                 << " is not a number in scanner " 
                 << name
                 << endl;
            i= info.length();
         }
      }
      statemax = statemax + 1;
      stateptr = right(stateptr);
   }
}

This procedure is passed a root of a subtree in which the 
first-tier nodes represent the states of a scanner.  

o getInfo() -- retrieves the value of a node ("1", "2" ...)
o states[]  -- is a global array of state names being saved for
               future use in, say, `checkState()'
o statemax  -- is a global int, and holds the number of elements
  of state[].
o left(n)   -- is a macro call equal to (BinNode *)n->getLeft()
o right(n)  -- is a macro call equal to (BinNode *)n->getRight()
 

stateptr is anchored at the head of the list of states,
each node of which is linked to the next via its right pointer.
Traversing this list enables checking to ensure that each
string in the list encodes a number (i.e. consists of all
digits).  An error message is written is a state contains
a non-digit.  The variable `name' is a global string that
holds the name of the scanner, which should be filled in
when executing `checkName()'.



Revision history:
3/22/2006 -- First version to illustrate checking some characteristics of TransitionLists
 either:
*/
using namespace std;
#include <iostream>
#include "Envs.h"
#include "Tokens.h"
#include "Basics.h"
#include "Nodes.h"

typedef IntSet TokenTypeSet; 

Token  t;   
IntSet  ES; // empty set

// check -- true iff the current token (t) is contained in the TokenTypeSet s
int check(TokenTypeSet s, string v)
{
   entering("check");
   //cout << "s=";s.displayln();
   //cout << "v="<<v << endl;
   //cout << s.contains(t.type()) << endl;
   //cout << t.val() << endl;
   leaving("check");
  return s.contains(t.type()) && t.val() == v;
}

// verify -- if current token (t) is in in the set TokenTypeSet s, 
//           then get the next token
//           else error message and halt the program
void verify(TokenTypeSet s, string v)
{
   TokenType c,d;
   entering("verify");
   //cout << "Verifying:"; s.displayln();
   if (check(s,v)){
   }
   else {
      cout << "Error: verify: looking for:";
      c = ctagSym; //  first in TokenType
      while (! s.contains(c))
            c =  succ(c);
      cout << tokenTypeStr(c) << endl;
      if (c != stuffSym) {  // loop for commas 
         c = succ(c);
         for ( d = c ; d != stuffSym; d=succ(d)) {
             if (s.contains(d))
               cout << "," << tokenTypeStr(c) 
                           << endl;
         }
         if (s.contains(stuffSym))
            cout << "," << tokenTypeStr(c) 
                        << endl;
      }
      cout << ", " << v << " ";
      cout << "found " ;
      t.displayln();
      exit(1);
   }
   leaving("verify");
}


/* START        ::= <start> .4. </final> */
BinNode* parseStart() { //add tree building stuff
   entering("parseStart");
   verify (otagSym, "start");
   t.getStuff();
   BinNode *startX = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "start");
   t.get();
   leaving("parseStart");
   return startX;
}

/* NAME        ::= <name>.1.</name> */
BinNode* parseName() { //add tree building stuff
   entering("parseName");
   verify (otagSym, "name");
   t.getStuff();
   BinNode *nameX = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "name");
   t.get();
   leaving("parseName");
   return nameX;
}

/* ALPHABET    ::= <alphabet> .2. </alphabet> */
BinNode* parseAlphabet() {  //add tree building stuff
   entering("parseAlphabet");
   verify (otagSym, "alphabet");
   t.getStuff();
   BinNode *alphabetX = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "alphabet");
   t.get();
   leaving("parseAlphabet");
   return alphabetX;
}

/*  INPUT           ::= <input> .3. </input> */
BinNode* parseInput() {
   entering("parseInput");
   verify (otagSym, "input");
   t.getStuff();
   BinNode *root = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "input");
   t.get();
//   cout << "Input tree:" << endl;
//   printTree(root);
   leaving("parseInput");
   return root;
}
/* NEXTSTATE       ::= <nextstate> .4. </nextstate> */
BinNode* parseNextState() {
   entering("parseNextState");
   verify (otagSym, "nextstate");
   t.getStuff();
   BinNode *root = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "nextstate");
   t.get();

//   cout << "NextState tree:" << endl;
//   printTree(root);

   return root;
   leaving("parseNextState");
}

/* STATE           ::= <state> .4. </state> */
BinNode* parseState() {
   entering("parseState");
   verify (otagSym, "state");
   t.getStuff();
   BinNode *root = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "state");
   t.get();

//   cout << "State tree:" << endl;
//   printTree(root);
   return root;
   leaving("parseState");
}

/* STATE-LIST   ::= STATE | STATE STATE-LIST */
BinNode* parseStateList() {
   entering("parseStateList");
   BinNode *tmp = parseState(); 
   if (check(otagSym,"state") )
   {
     BinNode *tmp2 = parseStateList();
     tmp->setRight(tmp2);
   }
   leaving("parseStateLists");
   return tmp;
}

/* STATES       ::= <states> STATE-LIST </states>  */
BinNode* parseStates() {
   entering("parseStates");
   verify (otagSym, "states");
   t.get();
     BinNode *s_list;
//     s_list->setRight(parseStateList()); 
     s_list = parseStateList();  
   verify (ctagSym, "states");
   t.get();
   leaving("parseStates");
   return s_list;
}


/* TRANSITION      ::= <transition> INPUT STATE NEXTSTATE </transition> */
BinNode* parseTransition () {
   entering("parseTransition");
   verify (otagSym, "transition");  t.get();
   BinNode *root, *c1, *c2, *c3;
   c1=parseInput();
   c2=parseState();
   c3=parseNextState();
   c1->setRight(c2); 
   c2->setRight(c3);

   root = new BinNode("transition",NULL,c1);
   verify (ctagSym, "transition");  t.get();
//   cout << "Transition tree:" << endl;
//   printTree(root);

   leaving("parseTransition");
   return root;
}

/* TRANSITION-LIST  ::= TRANSITION | TRANSITION TRANSITION-LIST */
BinNode* parseTransitionList () {
   entering("parseTransitionList");
   BinNode *root, *c1=NULL;
   root = parseTransition(); 
   if ( check(otagSym,"transition") )
     c1 = parseTransitionList();
   
   root->setLeft(c1);
//   cout << "TransitionList tree:" << endl;
//   printTree(root);
   
   leaving("parseTransitionLists");
   return root;
}

//prototype parseScanner()
BinNode *parseScanner();

/* SCANNER-LIST ::= SCANNER | SCANNER SCANNER-LIST  */
BinNode* parseScannerList()
{
   entering("parseScannerList");
   BinNode *root, *c1=NULL;
   root = parseScanner();
   if ( check(otagSym,"scanner") )
     c1 = parseScannerList();

   root->setRight(c1);
//   cout << "ScannerList tree:" << endl;
//   printTree(root);
   leaving("parseScannerList");
   return root;
}

/*  PROGRAM        ::= <scanner-list> SCANNER-LIST </scanner-list> */
BinNode* parseProgram() 
{
  verify(otagSym, "scanner-list");
  t.get();
  BinNode *root = parseScannerList(); //point root to the total tree
  verify(ctagSym, "scanner-list");
  t.get();
  leaving("parseProgram");
  return root;
}


/* FINAL-STATES ::= <final-states> STATE-LIST </final-states>   */
BinNode* parseFinalStates()
{
   entering("parseFinalStates");
   verify (otagSym, "final-states");
   t.get();
   BinNode *finalX = parseStateList();

   verify (ctagSym, "final-states");
   t.get();
   leaving("parseFinalStates");
   return finalX;
}

/* TRANSITION-TABLE ::= <transition-table> TRANSITION-LIST </transition-table>  */
BinNode* parseTransitionTable()
{ 
  entering("parseTransitionList");
  verify(otagSym, "transition-table");
  t.get();
  
  BinNode *trans_t = parseTransitionList();
  
  verify(ctagSym, "transition-table");
  t.get();
  leaving("parseTransitionTable");
  return trans_t;
}

/* SCANNER  ::= <scanner> NAME ALPHABET STATES START FINAL-STATES TRANSITION-TABLE </scanner>  */
BinNode* parseScanner()
{ 
  entering("parseScanner");
  verify(otagSym, "scanner");
  t.get();
  
  BinNode *name = parseName(); //parseName()
  BinNode *alphabet = parseAlphabet();
  BinNode *states = parseStates();
  BinNode *start = parseStart();
  BinNode *final_states = parseFinalStates();
  BinNode *trans_table = parseTransitionTable();  
  
  BinNode *scanner_root = new BinNode(name->getInfo(),NULL,NULL);

  scanner_root->setLeft(alphabet); //set alphabet to left of root
  alphabet->setLeft(states);
  states->setLeft(start);
  start->setLeft(final_states);
  final_states->setLeft(trans_table);

  verify(ctagSym, "scanner");
  t.get(); 
  
  leaving("parseScanner");
  return scanner_root;
}




#define right(n) ((BinNode *) n->getRight())
#define left(n) ((BinNode *) n->getLeft())
string alphabet = "ab";
string name = "ScannerOne";  // Simulated scanner name
string state[100] = {"1", "2", "3"};   // simulate 3 states
int statemax = 20;  //simulate 3 states

bool checkStart(BinNode *n) {}
bool checkName(BinNode *n) {
   string nm = n->getInfo();
   //cout << "Check Name  ->" << nm << "<-" << endl;
   for (int i = 0; i < name.length(); i++) 
   {
     char ch = nm[i];
     if(ch == 0 || ch == 1) //Dirtyhack to skip control codes
       continue;
     if ( !((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z' ))) 
     { // illegal character
          cout << "Name " << nm << " contains a non-letter:'" << ch << "'"<< endl;
     }
   }
   name = nm;
}

bool checkAlphabet(BinNode *n) {
   entering("checkAlphabet");
   alphabet = n->getInfo();
}

//WRITE ME
bool checkInput(BinNode *n) 
{ //edited 2006.04.02
  //Check that the input adheres to the grammar
   string tmp = n->getInfo();
   for (int i = 0; i < name.length(); i++) 
   {
     char ch = tmp[i];
     if(ch == 0 || ch == 1) //Dirty hack to skip control codes, NULL and SOH
       continue;
     if ( !((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z' )) ) 
     { // illegal character
        cout << "Input " << tmp <<  " contains a non-letter:'" << ch << "'"<< endl;
      }
   }
}

bool checkNextState(BinNode *n) 
{  //edited 2006.04.02
   string tmp = n->getInfo();
   for (int i = 0; i < name.length(); i++)
   {
       char ch = tmp[i];
       if ( !((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z' )))
      { // illegal character
          cout << "Input " << tmp
               << " contains a non-letter:'" << ch << "'"<< endl;
       }
   }
}

bool checkState(BinNode *n) {
   string st = n->getInfo();
   int i = 0;
   // cout << "Checking: \n" << endl;
   // printTree(n);
   while (i < statemax && state[i] != st ) {
      // cout << "Comparing " << st << " with " << state[i] << endl;
      i++;
   }
   if ( i >= statemax) { // not found
       cout << "State \"" << st << '"' << " not in state list: " ;
       for (int i=0; i < statemax; i++) {
           cout << state[i]  << " " ;
       }
       cout << " in scanner " << name<< endl;
   }

}

bool checkStateList(BinNode *n) 
{ //edited 2006.04.02
    entering("checkStateList");
    checkState(n);
    if (check(otagSym,"state") )
       checkStateList(n);
    leaving("checkStateLists");

}

bool checkStates (BinNode *n) {
   BinNode *stateptr = left(n);
   while  (stateptr != NULL) {
      string info = stateptr->getInfo();
      state[statemax] = info;
      for (int i=0; i < info.length(); i++) {
         char ch = info[i];
         if (ch < '0' || ch > '9') {
            cout << "State " << info 
                 << " is not a number in scanner " 
                 << name
                 << endl;
            i= info.length();
         }
      }
      statemax = statemax + 1;
      stateptr = right(stateptr);
   }
}

bool checkTransition (BinNode *n) {
   entering("checkTransition");
//   BinNode *tmp  = right(n); //check tree format
//   cout << "Printing Tree starting @ transition: " << endl;
//   printTree(n);
//   cout << "node = " << n->getInfo() << endl;
   BinNode *input,
           *state,
           *nextstate;
   input = right(n);
   checkInput(input);
   state  = right(input);
   checkState(state);
   nextstate = right(state);
   checkState(nextstate);
   leaving("checkTransition");
}

bool checkTransitionList (BinNode *n) {
  entering("checkTransitionList");
  BinNode *t = n;
   while (t != NULL) {
      checkTransition (t); 
      t = left(t);
   }
}


bool checkTransitionTable (BinNode *n) 
{ //edited 2006.04.02
  entering("checkTransitionTable");
  checkTransitionList(n);
  leaving("checkTransitionTable");
}

bool checkFinalStates (BinNode *n) 
{ //edited 2006.04.02
  entering("checkFinalStates");
  checkStateList(n);
  leaving("checkFinalStates");
}

bool checkScanner (BinNode *n) {
   entering("checkScanner");
//   n = left(n); 
   BinNode *name, 
           *alphabet, 
           *states, 
           *start, 
           *finals,
           *transitions; 
   name = n;
   alphabet = left(name);
   states = left(alphabet);
   start = left(states);
   finals = left(start);
   transitions = left(finals);
   checkName(name);
   checkAlphabet(alphabet);
   checkStates(states);
   checkStart(start);
   checkFinalStates(finals);
   checkTransitionList(transitions);
}

bool checkScannerList (BinNode *n) {
   entering("checkScannerList");
   BinNode *t = n;
   while (t != NULL) {
      checkScanner (t);
      t = right(t);
   }
}

bool checkProgram (BinNode *n){
  entering("checkProgram");
  return checkScannerList(n); //checkScannerList(left(n))  originally
}

int main(int argc, char *argv[])
{
   BinNode *tree; 
   DEBUG=0;
   if (argc == 2) 
     setTokenSource(argv[1]); // set input to kbd
   else
     setTokenSource(""); // set input to kbd
   
   cout << "Parsing Tree..." << endl;
   t.init(initSym);
   t.get();
   tree = parseProgram();

   cout << "Checking Tree..." << endl; 
   checkProgram(tree);
   return 0;
}