/* National Institute of Standards and Technology (NIST)
/* National Computer System Laboratory (NCSL)
/* Office Systems Engineering (OSE) Group
/* ********************************************************************
/*                            D I S C L A I M E R
/*                              (March 8, 1989)
/*  
/* There is no warranty for the NIST NCSL OSE SGML parser and/or the NIST
/* NCSL OSE SGML parser validation suite.  If the SGML parser and/or
/* validation suite is modified by someone else and passed on, NIST wants
/* the parser's recipients to know that what they have is not what NIST
/* distributed, so that any problems introduced by others will not
/* reflect on our reputation.
/* 
/* Policies
/* 
/* 1. Anyone may copy and distribute verbatim copies of the SGML source
/* code as received in any medium.
/* 
/* 2. Anyone may modify your copy or copies of SGML parser source code or
/* any portion of it, and copy and distribute such modifications provided
/* that all modifications are clearly associated with the entity that
/* performs the modifications.
/* 
/* NO WARRANTY
/* ===========
/* 
/* NIST PROVIDES ABSOLUTELY NO WARRANTY.  THE SGML PARSER AND VALIDATION
/* SUITE ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
/* EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
/* THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS
/* WITH YOU.  SHOULD THE SGML PARSER OR VALIDATION SUITE PROVE DEFECTIVE,
/* YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
/* 
/* IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL NIST BE LIABLE FOR
/* DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL,
/* INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
/* INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA
/* BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR A
/* FAILURE OF THE PROGRAM TO OPERATE WITH PROGRAMS NOT DISTRIBUTED BY
/* NIST) THE PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF
/* SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
*/

/************************************************************************/
/*   TITLE:          SGML PARSER                                        */
/*   SYSTEM:         DTD PROCESSOR                                      */
/*   SUBSYSTEM:                                                         */
/*   SOURCE FILE:    DETTRAV.C                                          */
/*   AUTHOR:         Michael Garris                                     */
/*                                                                      */
/*   DATE CREATED:                                                      */
/*   LAST MODIFIED:                                                     */
/*                                                                      */
/*                  REVISIONS                                           */
/*   WHEN      WHO            WHY                                       */
/************************************************************************/
#include <stdio.h>
#include "detdefs.h"
#include "detglbl.h"

/************************************************************************/
/************************************************************************/
/* PROCINORDR is a traversal which visits every state in an FSA starting*/
/* at the start state "startstate".                                     */
/************************************************************************/
void procinordr(startstate,finalstate)
STATE *startstate,*finalstate;
{
   STATE *node;/* current state being visited */

   /* set current node to "startstate" */
   node = startstate;
   /* if the finalstate has not be reached ... */
   if(startstate != finalstate){
      /* if the current state's left pointer is not NULL, not point*/
      /* back, and not looping directly back to itself ... */
      if((node->lptr != NULL) && (node->llabel != BACK)
          && (node != node->lptr)){
         /* continue to traverse left */
         procinordr(node->lptr,finalstate);
      }
      /* the current node's left pointer is either NULL, pointing */
      /* back, or pointing directly to itself, so invoke "procnode" */
      procnode(node);
      /* now look right */
      /* if current node's right pointer is not NULL, not pointing */
      /* back, and not looping directly back to itself ... */
      if((node->rptr != NULL) && (node->rlabel != BACK)
          && (node != node->rptr)){
         /* continue to traverse right */
         procinordr(node->rptr,finalstate);
      }
   }
   /* otherwise final state has been found */
   else{
      /* process the final state */
      procnode(startstate);
   }
}
/************************************************************************/
/************************************************************************/
/* PROCNODE takes a state structure and prints out the state's address, */
/* the state's left pointer address and label, and the state's right    */
/* pointer address and label.                                           */
/************************************************************************/
void procnode(node)
STATE *node;
{
#ifdef DEBUG
   printf("for node at address %04x\n", node);
   printf("  lptr = %04x, llabel = %04x, linst = %d\n", 
       node->lptr, node->llabel, node->linst);
   printf("  rptr = %04x, rlabel = %04x, rinst = %d\n", 
       node->rptr, node->rlabel, node->rinst);
   printf("___________________________________\n");
#else
   return;
#endif
}
/************************************************************************/
/************************************************************************/
/* PROCDET is a traversal which visits every state in an FSA starting   */
/* at the start state "startstate", and for each state visited, it calls*/
/* a procedure to check the current state passed for "ambiguity".       */
/************************************************************************/
void procdet(startstate,finalstate)
STATE *startstate,*finalstate;
{
   register STATE *node;/* current state being looked at */
   STATE *currnode[BUFFSIZE];/* list to hold all states visited */
   /* while a state is tested for ambiguity */
   int nodeindex = 0;/* subscript to "currnode" */
   int toklist[BUFFSIZE];/* list to hold all edges labeled with */
   /* tokens and their associated instance code*/
   int *tokindex = toklist;/* pointer to toklist initialized to the */
   /* beginning of toklist */
   int *tokmax = tokindex + BUFFSIZE - 2;
   register int i;
   memset((char *)toklist, 0, BUFFSIZE);
   /* set current state to state that was passed */
   node = startstate;
   /* if the state passed is not the finalstate ...*/
   if(startstate != finalstate){
      /* if the left pointer of the current state is not NULL, not */
      /* pointing back, and not looping directly to itself ... */
      if((node->lptr != NULL) && (node->llabel != BACK)
          && (node != node->lptr)){
         /* continue to traverse left */
         procdet(node->lptr,finalstate);
      }
      /* otherwise send the current state and a state list to a */
      /* procedure to detect any ambiguity from that state */
      findlabels(node,currnode,&nodeindex,toklist,&tokindex,tokmax);
      /* if the right pointer of the current state is not NULL, not */
      /* pointing back, and not looping directly to itself ...*/
      if((node->rptr != NULL) && (node->rlabel != BACK)
          && (node != node->rptr)){
         /* continue to traverse right */
         procdet(node->rptr,finalstate);
      }
   }
   /* otherwise the current state is the final state */
   else{
      /* invoke procedure to determine ambiguity on the final state */
      findlabels(startstate,currnode,&nodeindex,toklist,&tokindex,tokmax);
   }
}
/************************************************************************/
/************************************************************************/
/* FINDLABELS takes a state from an FSA and traverses all unique paths  */
/* from that state recording each first occurance of a non-NULL edge    */
/* on each unique path.  On completing each unique path, this procedure */
/* searches a list of the non-NUll edges seen and determines is the     */
/* state is "ambiguous" according to the definition stated by SGML.     */
/************************************************************************/
void findlabels(node,currnode,nodeindex,toklist,ptrin,tokmax)
register STATE *node;
STATE *currnode[];
int *toklist,**ptrin;
int *nodeindex;
int *tokmax;
{
   int *tokindex = *ptrin;

   /* put the current state's address into the list of states visited */
   if (*nodeindex >= BUFFSIZE) {
      printf("overflow in findlabels\n");
      exit(0);
   }
   currnode[(*nodeindex)] = node;
   /* increment the subscript at the location nodeindex */
   *nodeindex = *nodeindex + 1;
   /* if the current state's left edge is labelled EMPTY or BACK, and */
   /* the current state's left edge is not pointing to a state already*/
   /* visited by this traversal on the state passed by procdet ...    */
   if(node->llabel < 0){
      register int i;
      register STATE **jcurrnode = currnode;
      register STATE *jnode = node->lptr;
      for (i = 0; i < *nodeindex; i++) {
         if (*jcurrnode++ == jnode)
            goto OUT1;
      }
      /* continue to traverse left on a unique path */
      findlabels(node->lptr,currnode,nodeindex,toklist,&tokindex, tokmax);
   }
OUT1:
   /* if the current state is not pointing left to a NULL, EMPTY, and */
   /* BACK ...*/
   if((node->lptr != NULL) && (node->llabel != EMPTY)
       && (node->llabel != BACK)){
      /* then the edge is labelled with a token, so print it out */
      if(searchamb(node->llabel,node->linst,toklist,tokindex))
         ambmodel = TRUE;
      if((tokindex + 2) >= tokmax) {
         printf("tokindex overflow in findlabels()\n");
         exit(0);
      }
      *tokindex++ = node->llabel;
      *tokindex++ = node->linst;
   }

   /* if the current state's right edge is labelled EMPTY or BACK, and */
   /* the current state's right edge is not pointing to a state already*/
   /* visited by this traversal on the state passed by procdet ...     */
   if(node->rlabel < 0){
      register int i;
      register STATE **jcurrnode = currnode;
      register STATE *jnode = node->rptr;
      for (i = 0; i < *nodeindex; i++) {
         if (*jcurrnode++ == jnode)
            goto OUT2;
      }
      findlabels(node->rptr,currnode,nodeindex,toklist,&tokindex,tokmax);
   }
OUT2:
   /* otherwise the edge is labelled by a token */
   if((node->rptr != NULL) && (node->rlabel != EMPTY)
       && (node->rlabel != BACK)){
      /* print the labelled edge out */
      if(searchamb(node->rlabel,node->rinst,toklist,tokindex))
         ambmodel = TRUE;
      if((tokindex + 2) >= tokmax) {
         printf("tokindex overflow in findlabels()\n");
         exit(0);
      }
      *tokindex++ = node->rlabel;
      *tokindex++ = node->rinst;
   }
   *ptrin = tokindex;
}
/************************************************************************/
/************************************************************************/
/* SEARCHAMB*/
/************************************************************************/
int searchamb(label,inst,toklist,tokindex)
int label,inst,*toklist,*tokindex;
{
   int i;
   register int *ptr = toklist;

   while(ptr != tokindex){
      if(label == *ptr++){
         if(inst != *ptr++)
            return(TRUE);
      }
      else
         ++ptr;
   }
   return(FALSE);
}
/************************************************************************/
/************************************************************************/
/* SSEARCH searches a list of states for a match on the current state    */
/* "node".  If a match occurs then the function returns FALSE, otherwise*/
/* the function returns TRUE.                                           */
int ssearch(node,currnode,nodeindex)
STATE *node,*currnode[];
register int nodeindex;
{
   register int i,k = 0;

   for(i = 0; i < nodeindex; ++i){
      if(currnode[k++] == node)
         return(FALSE);
   }
   return(TRUE);
}
/************************************************************************/