/* ****************************************************************
   File   : fsm_general.c
   Author : Himanshu A. Sanghavi
   Date   : August 1, 1991

   This file contains a number of "support" functions for the 
   finite state machine library.  Functions for input/output,
   copying, deleting, trimming and renaming state machines are
   included in this file.  It also contains functions for 
   masking and unmasking a state machine.

   *************************************************************** */

   #include "fsm.h"


/* ************************************************************ 
   Function : fsm_read

   This function reads in a state machine from an input file

   Arguments : fp      - pointer to the input file
	       fsm_ptr - pointer to the state machine      

   Return Type : void

   ************************************************************ */

void fsm_read(FILE *fp, FSM *fsm_ptr)
{
   int i, j, no_of_states, no_of_trans, no_read;
   char name[MAX_LENGTH], ip[MAX_LENGTH], nxt_st[MAX_LENGTH], *tmpfname;
   ST_LIST *new_state;
   /*FILE *fp = fopen(fname, "r");*/

   if (!fp) 
      prog_abort("fsm_read : invalid file pointer");

   /* ensure that state machine is empty */
   fsm_ptr->states = NULL;

   /* read in the total number of states in the state machine */
   no_read = fscanf(fp, "%d", &no_of_states);  
   if (no_read != 1)
	prog_abort("fsm_read : inappropriate input file format");

   /* read in the states one by one and insert them in the
      linked list of states */
   for (i = 0; i < no_of_states; i++) {

      /* read in the name of the next state */
      no_read = fscanf(fp, "%s", name);
      if (no_read != 1)
	 prog_abort("fsm_read : inappropriate input file format");

      /* insert the state in the linked list */
      new_state = insert_state(fsm_ptr, name);

      /* read in information about whether the state is marked or
	 unmarked and the number of transitions it has */
      no_read = fscanf(fp, "%d %d", &new_state->marked, &no_of_trans);
      if (no_read != 2)
	 prog_abort("fsm_read : inappropriate input file format");

      /* read in each transition and insert in the current state */
      for (j = 0; j < no_of_trans; j++) {
	 
	/*CHANGE...fsm file does not contain controllability bit*/
	 /* read in transition information from file */
	 no_read = fscanf(fp, "%s %s", ip, nxt_st);
	 if (no_read != 2) 
	    prog_abort("fsm_read : inappropriate input file format");

	 /* insert the transition in the current state */
	 insert_trans(fsm_ptr, new_state, ip, nxt_st);
      }
   }
}


/* ***********************************************************
   Function : fsm_print

   This function prints the finite state machine information
   to an output file

   Arguments : fp - pointer to the output file
               fsm_ptr - pointer to the state machine

   Return Type : void

   ************************************************************ */

void fsm_print(fp, fsm_ptr)
FILE *fp;
FSM *fsm_ptr;
{
   int i, j, no_of_states, no_of_trans;
   ST_LIST *current;
   TR_LIST *this;

   if (!fp)  
      prog_abort("fsm_print : invalid file pointer");

   if (!fsm_ptr)
      prog_abort("fsm_print : NULL pointer passed as argument for (FSM *)");

   /* find out the total number of states in this machine 
      and print that as the first line of the output file */
   no_of_states = get_NStates(fsm_ptr);
   fprintf(fp, "%d\n\n", no_of_states);

   /* start with the first state and print information 
      corresponding to each state of the FSM */
   current = fsm_ptr->states;

   for (i = 0; i < no_of_states; i++) {

      /* find out the total number of transitions */
      no_of_trans = get_NTrans(current);

      /* print information about current state */
      fprintf(fp, "%s \t %d \t %d \n", current->name,
				current->marked, no_of_trans);

	  /*CHANGED, not printing controllability info*/
      /* print information corresponding to each transition */
      this = current->trans;
      for(j = 0; j < no_of_trans; j++) {
         fprintf(fp, "%s \t %s \n", this->input, this->next_state->name);
         this = this->next;
      }

      fprintf(fp, "\n");
      current = current->next;
   }
}


/* ************************************************************
   Function : fsm_copy

   This function makes a copy of a given state machine.

   Arguments : fsm1_ptr - pointer to the original state machine
               fsm2_ptr - pointer to the copy dest

   Return Type : void

   ************************************************************* */

void fsm_copy(fsm1_ptr, fsm2_ptr)
FSM *fsm1_ptr, *fsm2_ptr;
{
   ST_LIST *current, *st_ptr;
   TR_LIST *this, *tr_ptr;

   if (!fsm1_ptr || !fsm2_ptr) 
      prog_abort("fsm_copy : NULL pointer passed as argument for (FSM *)");

   /* ensure that fsm2 is empty */
   fsm2_ptr->states = NULL;

   /* start from the initial state of fsm1 */
   current = fsm1_ptr->states;

   /* step through the linked list of the states of fsm1 and
      insert each one of them in fsm2  */
   while (current) {
      st_ptr = insert_state(fsm2_ptr, current->name);
      st_ptr->marked = current->marked;

      /* insert all the transitions of the current state in the copy */
      tr_ptr = current->trans;
      while (tr_ptr) {
         insert_trans(fsm2_ptr, st_ptr, tr_ptr->input, tr_ptr->next_state->name);
         tr_ptr = tr_ptr->next;
      }

      current = current->next;
   }
}


/* ************************************************************
   Function : fsm_delete

   This function deletes a state machine.  The memory used to
   store the machine is returned to the operating system.

   Arguments : fsm_ptr - pointer to the state machine to be
                         deleted

   Return Type : void

   ************************************************************* */

void fsm_delete(fsm_ptr)
FSM *fsm_ptr;
{
   ST_LIST *current, *st_ptr;
   TR_LIST *this, *tr_ptr;

   if (!fsm_ptr)
	prog_abort("fsm_delete : NULL pointer passed as argument for (FSM *)");

   /* start from the initial state of the state machine */
   current = fsm_ptr->states;

   /* step through the linked list of states and delete each 
      state one by one */
   while (current) {
      /* remember the pointer to the next state before deleting
         the current state */ 
      st_ptr = current->next;

      /* first delete all the transitions comming out of the 
         current state */
      this = current->trans;
      while (this) {
         /* remember the pointer to the next transition before 
            deleting this transition */
         tr_ptr = this->next;
         /*free(this->input);/*static now*/
         free(this);              /* delete transition */
         this = tr_ptr;
      }

      /*free(current->name);/*static now*/
      free(current);              /* delete state */
      current = st_ptr;
   }

   fsm_ptr->states = NULL;
}


/* ****************************************************************
   Function : fsm_trim

   This function trims the input state machine

   Arguments : fsm_ptr - pointer to the input state machine

   Return Type : void

   **************************************************************** */

void fsm_trim(fsm_ptr)
FSM *fsm_ptr;
{
   ST_LIST *current, *next_st, *st_ptr;
   TR_LIST *this;
   NAME_LIST *name_list = NULL, *name_ptr;
   BOOLEAN flag, exists;
   FSM fsm_inverse;

   if (!fsm_ptr)
	prog_abort("fsm_trim : NULL pointer passed as argument for (FSM *)");

   /* first find out all the state reachable from the initial state */
   fsm_reachability(fsm_ptr, fsm_ptr->states->name, "ALL", &name_list);
   
   /* now step through all the states of the state machine and if
      any of them is not in the list of reachable states then 
      delete that state */
   current = fsm_ptr->states->next;
   while (current) {

      /* remember pointer to the next state in case the current
         state has to be deleted */
      next_st = current->next;

      /* check if the current state is in the list */
      exists = find_name(name_list, current->name);

      /* if it is not, delete the current state */
      if (!exists)
	 delete_state(fsm_ptr, current);

      current = next_st;
   }

   /* free the storage used to store the name_list */
   delete_name(&name_list);

   /* ensure that temporary fsm used is empty */
   fsm_inverse.states = NULL;

   /* Generate the inverse of fsm_ptr.  If there is a transition
      labeled `a' in fsm_ptr from state `q' to state `p', then
      there is a transition labeled `a' from state `p' to state
      `q' in its inverse */
   current = fsm_ptr->states;
   while (current) {

      /* insert the current state in fsm_inverse */
      st_ptr = insert_state(&fsm_inverse, current->name);
      st_ptr->marked = current->marked;

      /* step through the transitions of the current state of fsm_ptr */
      this = current->trans;
      while (this) {

	 /* insert the inverse transition in fsm_inverse */
	 st_ptr = insert_state(&fsm_inverse, this->next_state->name);
	 insert_trans(&fsm_inverse, st_ptr, this->input, current->name);
	 this = this->next;
      }

      current = current->next;
   }

   /* insert a new state called "dead" in the inverse machine */
   st_ptr = insert_state(&fsm_inverse, "dead");

   /* insert a epsilon transition from the "dead" state to every 
      marked state of fsm_inverse */
   current = fsm_inverse.states;
   while (current) {
      if (current->marked)
	 insert_trans(&fsm_inverse, st_ptr, "*", current->name);
	 current = current->next;
   }

   /* now compute the set of states reachable from the "dead" state */
   fsm_reachability(&fsm_inverse, "dead", "ALL", &name_list);

   /* Step through the states of fsm_ptr.  If any of them is not
      on the list of states reachable from the dead state, delete
      that state */
   current = fsm_ptr->states;
   while (current) {

      /* remember the pointer to the next state */
      next_st = current->next;

      /* check if this state exists in the list of reachable states */
      exists = find_name(name_list, current->name);

      /* if not, then remove the state from the state machine */
      if (!exists) 
         delete_state(fsm_ptr, current);

      current = next_st;
   }

   /* free the storage used by the temporary fsm */
   fsm_delete(&fsm_inverse);
}


/* ****************************************************************
   Function : fsm_rename

   This function renames the states of a state machine.  This is 
   to be used when the names of a particular state machine get too
   complicated (with a lot of concatenation).  This routine can 
   handle a FSM with a maximum of 2600 states.

   Arguments : fsm_ptr - pointer to the state machine

   Return Type : void

   **************************************************************** */

void fsm_rename(fsm_ptr)
FSM *fsm_ptr;
{

   ST_LIST *current;
   char new_name[4];

   /* Start with the name "a00" */
   strcpy(new_name, "a00");

   /* start with the first state of the FSM and step through 
      each state */
   current = fsm_ptr->states;
   while (current) {

      /* rename the current state */
/*      free(current->name);
      current->name = (char *) malloc(8);/*static now*/
      strcpy(current->name, new_name);
      
      /* Now generate the name for the next state */

      /* first increment the units digit, if it is not 9 */
      if (new_name[2] != '9') 
	 ++new_name[2];
      
      /* if the units digit is 9, but the tens digit is not, set
         the units digit to 0 and increment the tens digit */
      else if (new_name[1] != '9') {
	 new_name[2] = '0';
	 ++new_name[1];
      }

      /* if both the units and tens digit are 9s, but the hundreds
	 digit (alphabet) is not z, set the units and tens digits
	 to zeros and set the hundreds digit to the next alphabet */
      else if (new_name[0] != 'z') {
	 new_name[2] = new_name[1] = '0'; 
	 ++new_name[0];
      }

      /* if reached "z99", you cannot go any further, hence abort */
      else
	 prog_abort("fsm_rename : cannot generate unique name for state");
      current = current->next;
   }
}


/* ***************************************************************
   Function : fsm_mask

   This function masks the events of a given state machine.  The
   resulting state machine is the observers view of the original
   state machine.

   Arguments : fp - pointer to the file containing masking information
	       fsm1_ptr - pointer to the machine to be masked
	       fsm2_ptr - pointer to the resultant machine

   Return Type : void

   *************************************************************** */

void fsm_mask(fp, fsm1_ptr, fsm2_ptr)
FILE *fp;
FSM *fsm1_ptr, *fsm2_ptr;
{
   ST_LIST *current1, *current2;
   TR_LIST *this;
   MASK_LIST *mask_list, *mask_ptr, *tmp, **anchor;
   char st1[MAX_LENGTH], st2[MAX_LENGTH];

   if (!fp)
	prog_abort("fsm_mask : Invalid file pointer");

   if (!fsm1_ptr || !fsm2_ptr)
	prog_abort("fsm_mask : NULL pointer passed as argument for (FSM *)");

   /* go to the beginning of the input file */
   rewind(fp);

   /* ensure that fsm2 is empty */
   fsm2_ptr->states = NULL;

   /* Read in the masking information from the input file into 
      mask_list.  anchor is used to insert elements in the list */
   anchor = &mask_list;

   /* read in information corresponding to pair of "original"
      and "masked" names from the input file */
   while(fscanf(fp, "%s %s", st1, st2) == 2) {

      /* allocate space for a new element of mask list */
      tmp = (MASK_LIST *) malloc(sizeof(MASK_LIST));

      /* copy information corresponding to the original and 
         masked names of the current event */
      strcpy(tmp->original, st1);
      strcpy(tmp->masked, st2);

      /* insert the new entry in the list */
      tmp->next = NULL;
      *anchor = tmp;
      anchor = &tmp->next;
   }

   /* start with the first state of the state machine and step
      through each state */
   current1 = fsm1_ptr->states;
   while (current1) {

      /* insert this state in fsm2 */
      current2 = insert_state(fsm2_ptr, current1->name);
      current2->marked = current1->marked;

      /* step through each transition of the current state of fsm1 */
      this = current1->trans;
      while (this) {
	 mask_ptr = mask_list;
	 while (mask_ptr) {

	    /* search for the element in mask_list which contains
	       information about this transition */	
	    if (strcmp(this->input, mask_ptr->original) == 0) {

		/* insert transition in the state of fsm2 but 
		   with its name changed to the masked name */
		insert_trans(fsm2_ptr, current2, mask_ptr->masked,
			 this->next_state->name);

		/* break from loop because this transition has been
		   renamed and hence we need not search further */
		break;
	    }

	    mask_ptr = mask_ptr->next;
	 }

	 this = this->next;
      }

      current1 = current1->next;
   }

   /* free the storage used for storing the masking information */
   while (mask_list) {
      mask_ptr = mask_list->next;
      free(mask_list);
      mask_list = mask_ptr;
   }
}


/* **************************************************************
   Function : fsm_unmask

   This function unmasks a state machine i.e. does the inverse
   operation of mask.

   Arguments : fp - pointer to the file containing masking information
	       fsm1_ptr - pointer to the machine to be unmasked
	       fsm2_ptr - pointer to the resultant machine
	       
   Return Type : void

   *************************************************************** */

void fsm_unmask(fp, fsm1_ptr, fsm2_ptr)
FILE *fp;
FSM *fsm1_ptr, *fsm2_ptr;
{
   ST_LIST *current1, *current2;
   TR_LIST *this;
   MASK_LIST *mask_list, *mask_ptr, *tmp, **anchor;
   char st1[MAX_LENGTH], st2[MAX_LENGTH];

   if (!fp)
	prog_abort("fsm_unmask : invalid file pointer");

   if (!fsm1_ptr || !fsm2_ptr)
	prog_abort("fsm_unmask : NULL pointer passed as argument for (FSM *)");

   /* go to the begining of the input file */
   rewind(fp);

   /* ensure that fsm2 is empty */
   fsm2_ptr->states = NULL;

   /* Read in the masking information from the input file into 
      mask_list.  anchor is used to insert elements in the list */
   anchor = &mask_list;

   /* read in information corresponding to pair of "original"
      and "masked" names from the input file */
   while(fscanf(fp, "%s %s", st1, st2) == 2) {

      /* allocate space for a new element of mask list */
      tmp = (MASK_LIST *) malloc(sizeof(MASK_LIST));

      /* copy information corresponding to the original and masked 
         names of the current event */
      strcpy(tmp->original, st1);
      strcpy(tmp->masked, st2);

      /* insert the new entry in the list */
      tmp->next = NULL;
      *anchor = tmp;
      anchor = &tmp->next;
   }

   /* Step through the states of fsm1 and insert corresponding states
      in fsm2.  In fsm2, the transitions are "unmasked" i.e. the 
      masked names of transitions of fsm1 are replaced by their 
      unmasked equivalents */
   current1 = fsm1_ptr->states;
   while (current1) {

      /* insert the current state in fsm2 */
      current2 = insert_state(fsm2_ptr, current1->name);
      current2->marked = current1->marked;

      /* Step through the transitions of current1 and insert each one
         of them in current2.  Note that there may be more there one
         unmasked transition corresponding to one masked name  */
      this = current1->trans;
      while (this) {
	 mask_ptr = mask_list;   
	 while (mask_ptr) {
	    if (strcmp(this->input, mask_ptr->masked) == 0) 
		insert_trans(fsm2_ptr, current2, mask_ptr->original,
				this->next_state->name);	
	    mask_ptr = mask_ptr->next; 
	 }

      /*Greg added need to retain * transitions that aren't self loops*/
	if (strcmp(this->input, "*") == 0 && strcmp(current1->name, this->next_state->name) != 0)
		insert_trans(fsm2_ptr, current2, "*",
				this->next_state->name);
	 this = this->next;
      }

      current1 = current1->next;
   }

   /* Find out all transitions, which when masked result in an epsilon
      transition.  Insert self loops in every state of fsm2 on such
      transitions.   The self loops are uncontrollable. */    
   mask_ptr = mask_list;
   while (mask_ptr) {
      if (strcmp(mask_ptr->masked, "*") == 0) {
	 current2 = fsm2_ptr->states;
	 while (current2) {
	    insert_trans(fsm2_ptr, current2, mask_ptr->original,
			        current2->name);
	    current2 = current2->next;
	 }
      }

      mask_ptr = mask_ptr->next;
   }

   /* free the storage used for storing the masking information */
   while (mask_list) {
      mask_ptr = mask_list->next;
      free(mask_list);
      mask_list = mask_ptr;
   }
}
