#include "semcheck.h"

/*
Program:  LL1_checker.c
*/

static int LL1_CHECK_RESULT= 1;
extern Vertex_Comma_list * terminals;
extern Term_Comma_list * foreignclasses;

void Demeter_in::CHECK_LL1(int &result, int nointer)
{
   input->CHECK_LL1(result, nointer);
}
Cd_graph *Input::CHECK_LL1(int &result, int nointer)
{
	return NULL;
}


Cd_graph *Cd_graph::CHECK_LL1(int &resultforenforcer, int nointer)
{
  terminals = terminal_sets;
  foreignclasses = foreign_classes;
  //global vars
  Cd_graph * usergrammar = (Cd_graph*) this->g_copy();

  cout << "\nChecking LL1 conditions ... " << endl;
  cout << "\n     Computing first sets ... " << endl;
  usergrammar->FIRSTSET();
  cout << "     Computing follow sets ... " << endl;
  usergrammar->FOLLOWSET();

  if (!nointer)
  {
    cout << "     printing first sets and follow sets into cd-ffsets... " << endl;
    usergrammar->print_fset();
  }

  cout << "\n     Checking LL1 conditions ... " << endl;
  usergrammar->get_adjacencies()->CHECK_LL1();
  if (LL1_CHECK_RESULT==0)
     resultforenforcer = 0;
  else
     resultforenforcer = 1;
  return usergrammar;
}



void Adjacency_Nlist::CHECK_LL1()
{
  Adjacency_list_iterator next_arg(*this);
  Adjacency_ each_arg;

  while (each_arg = next_arg())
  {
     each_arg->CHECK_LL1(this);
  }
}

void Adjacency::CHECK_LL1(Adjacency_Nlist* adj_Nlist)
{
  ns->CHECK_LL1(this,adj_Nlist);
}

void Neighbors::CHECK_LL1(Adjacency* rule,Adjacency_Nlist* adj_Nlist)
{
}

/*
To check alternations, check the alternatives for uniqueness, and
the common parts for optional parts.
*/

void  Alternat_ns::CHECK_LL1(Adjacency* rule,Adjacency_Nlist* adj_Nlist)
{
  alternat_ns->LL1_check(rule,adj_Nlist);
    if (this->get_construct_ns())
        this->get_construct_ns()->CHECK_LL1(rule,adj_Nlist);
}

/*
Check the alternatives
*/

void  Term_Bar_list::LL1_check(Adjacency* rule,Adjacency_Nlist* adj_Nlist)
{
static TEpsilon *iepsi = new TEpsilon();
static Ll1SetElement *epsill1 = new Ll1SetElement(NULL, iepsi, NULL, NULL);
Ll1SetElement_Comma_list *all_firstset = new Ll1SetElement_Comma_list();
Ll1SetElement_Comma_list *i_firstset = new Ll1SetElement_Comma_list();
Ll1SetElement_Comma_list *super_followset = new Ll1SetElement_Comma_list();
Ll1SetElement_Comma_list *inter;

Term_list_iterator next_i(*this);
Term_ i;
while (i = next_i()) {
  i_firstset = adj_Nlist->FIRSTSET(i->get_vertex());
  if (i_firstset->contain(epsill1)) {
    Term_list_iterator next_k(*this);
    Term_ k;
    while (k=next_k())
      if (!k->get_vertex()->g_equal(i->get_vertex()))
         all_firstset=all_firstset->
            join(adj_Nlist->FIRSTSET(k->get_vertex()));
    super_followset = adj_Nlist->FOLLOWSET(rule->get_source());
    if (inter = super_followset->empty_intersection(all_firstset))
    {
      cout << "LL(1) violation in the alternatives of alternation class ";
      rule->get_source()->pp();
      cout << ":" << endl;
      cout << "         firstset( ";
      i->get_vertex()->pp();
      cout << ") has epsilon.\n";
      cout << "         the intersection between followset( ";
      rule->get_source()->pp();
      cout << " )\n" <<
              "         and ";
      cout << "the union of firstset( all the other alternatives ) is \n";
      cout << "                        { ";
      inter->print_fset(25,cout);
      cout << "}" << endl;
      LL1_CHECK_RESULT = 0;
    }
   }
}
Term_list_iterator next_j(*this);
Term_ j;
while (j=next_j())
{
   Term_list_iterator next_l(*this);
   Term_ l;
   while (l=next_l())
      if (j->get_vertex()->g_equal(l->get_vertex()))
	   break;
   Ll1SetElement_Comma_list *j_firstset
		   = adj_Nlist->FIRSTSET(j->get_vertex());
   while (l=next_l()) {
      Ll1SetElement_Comma_list *l_firstset
		   = adj_Nlist->FIRSTSET(l->get_vertex());
      if (inter = l_firstset->empty_intersection(j_firstset))
       {
        Adjacency_List*  la=l->compute_associted(adj_Nlist);
        Adjacency_List*  ja=j->compute_associted(adj_Nlist);
        Adjacency_list_iterator  next_la(*la);
        Adjacency* each_la,*each_ja;
        while (each_la = next_la())
        {
           Adjacency_list_iterator  next_ja(*ja);
           while (each_ja = next_ja())
           {
            if (each_ja->get_source()->g_equal(each_la->get_source()))
              continue;
            if (adj_Nlist->FIRSTSET(each_ja->get_source())->
              empty_intersection(adj_Nlist->FIRSTSET(each_la->get_source())))
                 break;
           }
           if (each_ja) break;
        }
        if (each_ja)
        {
         cout << "LL(1) violation in the alternatives of alternation class ";
         rule->get_source()->pp();
         cout << ":" << "\n";
         cout << "      the intersection between firstset( ";
         j->get_vertex()->pp();
	 cout << " ) and\n";
         cout << "      firstset( ";
         l->get_vertex()->pp();
	 cout << " ) is\n";
         cout << "                        { ";
	 inter->print_fset(25,cout);
         cout << "}" << endl;
	 LL1_CHECK_RESULT = 0;
        }
     }
   }
}
}

/*
Alternatives meet the LL(1) conditions if their first sets are pairwise
disjoint. That is, the intersections of all pairs of first sets for
different alternatives must be empty. This function tests for an empty
intersection of two sets of Tll1setelements.
*/

Ll1SetElement_Comma_list * Ll1SetElement_Comma_list::empty_intersection(Ll1SetElement_Comma_list* set2)
{
  Ll1SetElement_list_iterator next_1(*this);
  Ll1SetElement_ set1_element;
  Ll1SetElement_Comma_list *result
	      = new Ll1SetElement_Comma_list();
  if (!set2) return NULL;
  if (((this->number_of_parts()==0)&&(set2->number_of_parts()==0))  ||
      ((this->number_of_parts()>0)&&(set2->number_of_parts()==0))  ||
      ((this->number_of_parts()==0)&&(set2->number_of_parts()>0)))
     return NULL;

  while (set1_element = next_1()) {
     Ll1SetElement_list_iterator next_2(*set2);
     Ll1SetElement_ set2_element;
     while (set2_element = next_2())
        if (set1_element->g_equal(set2_element))
           result->append(set1_element);
  }
  if (result->list_length()==0)
     return NULL;
  else
     return result;
}

/*
Checking optional parts of constructions or for optional common parts
for alternations involves checking a list of Tanysymbols. If a part is
optional, then its first set must be disjoint from its follow set.
Another way to express this condition is that its first set must be
disjoint from the first set of the symbol which follows it. If no symbol
follows, then the follow set = the follow set of the nonterminal in
which the optional part occurs.
*/

void  Construct_ns::CHECK_LL1(Adjacency* rule,Adjacency_Nlist *adj_Nlist)
{
  this->get_construct_ns()->CHECK_LL1(rule,adj_Nlist);
}

void  Any_vertex_List::CHECK_LL1(Adjacency* rule,Adjacency_Nlist *adj_Nlist)
{
static TEpsilon *iepsi = new TEpsilon();
static Ll1SetElement *epsill1 = new Ll1SetElement(NULL, iepsi, NULL, NULL);
Any_vertex_list_iterator next_arg(*this);
Any_vertex_ each_arg;

while(each_arg = next_arg())
{
  if (each_arg->is_optional())
  {
     Any_vertex_List * this_tail = each_arg->tail(this);
     Ll1SetElement_Comma_list *opt_firstset
                   = each_arg->OPT_FIRSTSET(adj_Nlist,rule);
     Ll1SetElement_Comma_list *inter;
     Ll1SetElement_Comma_list *opt_followset
	    = each_arg->OPT_FOLLOWSET(this_tail,rule,adj_Nlist);
     if ((inter = opt_firstset->empty_intersection(opt_followset)))
     {
     cout << "LL(1) violation in the optional part of ";
     rule->get_source()->pp();
     cout << ":\n";
     cout << "     the intersection between ";
     cout << "   firstset( ";
     each_arg->pp();
     cout << ") and \n";
     cout << "    followset(this optional part) is \n ";
     cout << "         { ";
     inter->print_fset(18,cout);
     cout << "}" << endl;
     LL1_CHECK_RESULT = 0;
     }
    }
  }
}

/*
The following functions are used to determine if a part is an
optional part. The function for Tanysymbol is virtual. Only
a Toptsymbol can be optional.
*/

int Any_vertex::is_optional()
{
   return (0);
}

int Optional_term::is_optional()
{
  return 1;
}

/*
Retrieve first ([B]) where [B] indicates that B is optional. Use
the fact that first ([B]) = first (B).
*/

Ll1SetElement_Comma_list* Any_vertex::OPT_FIRSTSET(Adjacency_Nlist *adj_Nlist,Adjacency *rule)
{
  cout << "Tanysymbol::opt_first() - shouldn't get here!" << endl;
  return NULL;
}

Ll1SetElement_Comma_list* Optional_term::OPT_FIRSTSET(Adjacency_Nlist *adj_Nlist,Adjacency *rule)
{
  return opt->OPT_FIRSTSET(adj_Nlist,rule);
}

Ll1SetElement_Comma_list* Opt_labeled_term_Sandwich::OPT_FIRSTSET(Adjacency_Nlist *adj_Nlist,Adjacency *rule)
{
  TEpsilon *iepsi = new TEpsilon();
  Ll1SetElement *epsill1 = new Ll1SetElement(NULL, iepsi, NULL, NULL);
  Ll1SetElement_Comma_list* frstst = new Ll1SetElement_Comma_list();


  if (first->FIRSTSET()->contain(epsill1))
  {
     Vertex *avertex = inner->get_vertex()->get_vertex();
     {
         frstst = adj_Nlist->FIRSTSET(avertex);
         if (frstst->contain(epsill1))
         {
           if (second->FIRSTSET()->contain(epsill1))
           {
               cout << "LL(1) violation in the optional part of ";
               rule->get_source()->pp();
               cout << ":\n";
               cout << "   epsilon is in the firstset of ";
               inner->get_vertex()->get_vertex()->pp();
               cout << "\n";
               LL1_CHECK_RESULT = 0;
               return frstst;
           }
           else
           {
               frstst = frstst->join(second->FIRSTSET());
               frstst = frstst->remove(epsill1);
               return frstst;
            }
         }
         else
             return frstst;
      }
  }
  else
     return first->FIRSTSET();
}

/*
The following functions follow the grammar to retrieve the symbol
name associated with the optional symbol. This is complicated by
the fact that an optional part is a Toptlabeledsymbol which can be
either a Tlabeledsymbol or a Tregularsymbol. If it is a Tregularsymbol,
then it is a Tsymbol. Both the Toptlabeledsymbol and Tregularsymbol
are alternations which means they have virtual functions.
*/

/*
 Retrieve follow ([B]) where [B] indicates that B is optional. This
 is not trivial. It is done as follows:

    Given: A = ... [B] C1 ... Cn .

                           j
    then : follow([B]) = ( U (first (Ck)) ) for j <= n.
                          k=1

                           j
    then : follow([B]) = ( U (first (Ck)) ) u follow(A)
                          k=1
                                 if all first(Ck) contain empty.


           where: Cj is the first symbol where first(Cj) does not
                  contain empty (epsilon)
                  U and u signify union.
*/

Any_vertex_List* Any_vertex::tail(Any_vertex_List* args)
{
  Any_vertex_list_iterator next_arg(*args);
  Any_vertex_ each_arg;
  Any_vertex_List* rest = new Any_vertex_List();

  while (each_arg = next_arg())
     if (each_arg==this) {
        while (each_arg = next_arg())
           rest->append(each_arg);
        break;
       }
  return rest;
}

Ll1SetElement_Comma_list* Any_vertex::OPT_FOLLOWSET(Any_vertex_List* args,Adjacency* rule,Adjacency_Nlist *adj_Nlist)
{
  cout << "Tanysymbol::opt_follow() - shouldn't get here!" << endl;
  return NULL;
}

Ll1SetElement_Comma_list* Optional_term::OPT_FOLLOWSET(Any_vertex_List* args,Adjacency* rule,Adjacency_Nlist *adj_Nlist)
{
  TEpsilon *iepsi = new TEpsilon();
  Ll1SetElement *epsill1 = new Ll1SetElement(NULL, iepsi, NULL, NULL);
  Ll1SetElement_Comma_list* fllwset = new Ll1SetElement_Comma_list();

  fllwset = args->FIRSTSET(adj_Nlist);
  if (fllwset->contain(epsill1)) {
     fllwset = fllwset->remove(epsill1);
     fllwset = fllwset->join(adj_Nlist->FOLLOWSET(rule->get_source()));
     return fllwset;
  }
  else
     return fllwset;
}

int Any_vertex_List::there_is_term()
{
Any_vertex_list_iterator nextpart(*this);
Any_vertex_ part;
while (part = nextpart())
{
  if (part->there_is_term())
     return 1;
}
return 0;
}

int Any_vertex::there_is_term()
{
  return 0;
}

int Opt_labeled_term::there_is_term()
{
   return 1;
}

int Optional_term::there_is_term()
{
  return 1;
}


Term *Any_vertex::LL1_get_term()
{
   cout << "\ncan not be here (Term *Any_vertex::LL1_get_term())!" << endl;
   exit(-1);
  return NULL;
}
Term *Opt_labeled_term::LL1_get_term()
{
   return this->get_vertex();
}

Term *Optional_term::LL1_get_term()
{
    return opt->LL1_get_term();
}

Term *Opt_labeled_term_Sandwich::LL1_get_term()
{
   return inner->LL1_get_term();
}
int Any_vertex::is_Inherit_term()
{
return 0;
}
int Inherit_term::is_Inherit_term()
{
return 1; 
}
int Any_vertex::is_Syntax_vertex()
{
return 0;
}
int Syntax_vertex::is_Syntax_vertex()
{
return 1;
}
int Any_vertex::is_Regular_syntax()
{
return 0;
}
int Regular_syntax::is_Regular_syntax()
{
return 1;
}
/*
 Checking repetitions involves determining that we can always know
 whether to choose another iteration or not. Thus, the first set
 for the repetition must be disjoint from the follow set. That is,
 given:
            A ~ {B} .

 then : first({B}) intersect follow({B}) must be empty.
*/

void  Repetit_n::CHECK_LL1(Adjacency* rule,Adjacency_Nlist* adj_Nlist)
{
    sandwiched->CHECK_LL1(rule,adj_Nlist);
}

void Kernel_Sandwich::CHECK_LL1(Adjacency* rule,Adjacency_Nlist* adj_Nlist)
{
 Ll1SetElement_Comma_list* inter;
 Ll1SetElement_Comma_list* firstset =
	inner->get_repeated()->calc_first(adj_Nlist,this,rule);
 Ll1SetElement_Comma_list* followset = this->calc_follow(rule,adj_Nlist);

 if (inter = firstset->empty_intersection(followset)) {
      cout << "LL(1) violation in  the repetition class ";
      rule->get_source()->pp();
      cout << ":\n      the intersection between firstset(";
      inner->get_repeated()->pp();
      cout << ") and \n";
      cout << "      followset(";
      inner->get_repeated()->pp();
      cout << ") is \n";
      cout << "                  { ";
      inter->print_fset(20,cout);
      cout << "}" << endl;
      LL1_CHECK_RESULT = 0;
 }
}

/*
 The follow set for a repetition is either the first item in the 
 part "<second>" which follows "<repeated>" or it is the follow
 set of the repetition rule.
*/

Ll1SetElement_Comma_list* Kernel_Sandwich::calc_follow(Adjacency* rule,Adjacency_Nlist* adj_Nlist)
{
  static TEpsilon *iepsi = new TEpsilon();
  static Ll1SetElement *epsill1 = new Ll1SetElement(NULL, iepsi, NULL, NULL);
  Ll1SetElement_Comma_list* follow_set;
  if ((follow_set = second->FIRSTSET())->contain(epsill1))
     follow_set = adj_Nlist->FOLLOWSET(rule->get_source());
  return follow_set;
}

/*
 The first set for a repeated symbol is either the first item in the
 Tstringorpp_tlist which precedes the actual symbol (Tregularsymbol)
 or it is the first set of the actual symbol itself.
*/

Ll1SetElement_Comma_list* Term_Sandwich::calc_first(Adjacency_Nlist* adj_Nlist,Kernel_Sandwich *sandwich,Adjacency *rule)
{
  static TEpsilon *iepsi = new TEpsilon();
  static Ll1SetElement *epsill1 = new Ll1SetElement(NULL, iepsi, NULL, NULL);
  Ll1SetElement_Comma_list* first_set = new Ll1SetElement_Comma_list();
  Ll1SetElement *forterminal;
  if ((first_set = first->FIRSTSET())->contain(epsill1))
  {
    first_set = adj_Nlist->FIRSTSET(inner->get_vertex());
    if (first_set->contain(epsill1))
     if (second->FIRSTSET()->contain(epsill1))
     {
	 int length = strlen(rule->get_source()->get_vertex_name()->get_val());
         cout << "LL(1) violation in  the repetition vertex ";
         rule->get_source()->pp();
         cout << ":\n      epsilon is in firstset(";
         this->pp();
	 cout << ")\n";
         LL1_CHECK_RESULT = 0;
     }
     else
     {
        first_set = first_set->join(second->FIRSTSET());
        first_set = first_set->remove(epsill1);
     }
  }
  return first_set;
}