/*******************************************************************************
* YORKTOWN ADVANCED SGML PARSER (YASP)                                         *
*         An SGML Parser conforming to International Standard ISO 8879 --      *
*         Standard Generalized Markup Language                                 *
*------------------------------------------------------------------------------*
* Written 1987 - 1993 by                                                       *
*         Pierre G. Richard                                                    *
*         IBM T.J. Watson Research Center                                      *
*         Yorktown Heights, New York                                           *
*         petrus@watson.ibm.com                                                *
*------------------------------------------------------------------------------*
* FUNCTION NAME    = YASP / DTD compiler                                       *
* STATUS           = Version 0, Release 1, Level 33 and up                     *
* COMPONENT NAME   = odtambg.c                                                 *
* DESCRIPTIVE NAME = Check ambiguities for a model content                     *
* DATE_WR          = 06/02/1989                                                *
* AUTHOR           = Pierre G. Richard - PETRUS at YKTVMX                      *
*                                                                              *
* FUNCTIONAL DESCRIPTION =                                                     *
*    Check ambiguities using a Finite State Automata model.                    *
*                                                                              *
*                                                                              *
* IMPLEMENTATION NOTE =                                                        *
*                                                                              *
* DEPENDENCIES =  (see Include list)                                           *
*                                                                              *
* IMPORT=                                                                      *
*                                                                              *
* EXPORT=                                                                      *
*                                                                              *
* CHANGE HISTORY =                                                             *
* Number Date     Inits    Change & Reason (brief)                             *
*      1 11/12/91 PETRUS   Make GRPGTCNT customizable                          *
*      2 07/15/92 PETRUS   Fixed a bug with AND groups                         *
*      3 09/11/92 PETRUS   Start get_graph at an earlier recursivity level     *
*      4 09/12/92 PETRUS   Added a test for repeatable groups                  *
*******************************************************************************/
/* #define DEBUG_IS_NEEDED */
/* #define DEBUG_SEE_ALL   */

/*-------------+
|Include Files |
+-------------*/
#include "machine.h"
#include "portable.h"
#include "yaspapi.h"
#include "global.h"
#include "usrlib.h"
#include "sgml.h"
#include "hash.h"
#include "odt.h"

/*------------------------+
|Local Functions and Types|
+------------------------*/
typedef MNODE * ARC;

typedef struct t_GRAPH {
   ARC *St_A;          /* next room free for arcs from Start-State (St_A) */
   ARC *Fn_A;          /* next room free for arcs from Final-State (Fn_A) */
}GRAPH;

typedef GRAPH STACK_BASED * GRAPH_P; /* on the stack */

static void  LP_FCT get_graph   (COMMON_P, uint, MNODE *, GRAPH_P);
static ARC * LP_FCT enter_arcs  (ARC *, ARC *, ARC *, ARC *, ARC *);
static void  LP_FCT check_ambig (COMMON_P, MNODE *, MNODE *);

/*---------------------+
|For Debug Only (TEMP) |
+---------------------*/
#ifdef DEBUG_IS_NEEDED
#undef printf
static uint recurse_level = -1;
static uint testcase_count = 0;
typedef enum {
   ST_AMBG,
   AND_AMBG,
   SEQUENCE_AMBG,
   REPEAT_AMBG
}AMBG_CODE;
static char const * const ambg_message[]  = {
   /* ST_AMBG       */ { "After any group: group St"                    },
   /* AND_AMBG      */ { "After an AND group: St and Fn"                },
   /* SEQUENCE_AMBG */ { "Inside a SEQ group: previous Fn and new ST"   },
   /* REPEAT_AMBG   */ { "Repeatable: new_ST and new_Fn arcs"           }
};
static char const * ambg_explain;
#define SET_AMBG_TYPE(ambg_code) ambg_explain = ambg_message[ambg_code];

#if defined(__TURBOC__)
#pragma warn -ucp

#elif defined (IBMCSET2)
#pragma checkout( suspend )
int _Optlink printf( );
#pragma checkout( resume )

#else
extern int C_FCT printf(const char *, ...);
#endif

static void LP_FCT show_graph (GRAPH_P, GRAPH_P);
static void LP_FCT show_what  (MNODE *);


/*-------------------+
|For a regular module|
+-------------------*/
#else
#define show_graph(a, b) ;
#define show_what(a)   ;
#define SET_AMBG_TYPE(ambg_code) ;
#endif

/*---------------------------------------------------------------------abg_chk-+
| Check ambiguities                                                            |
+-----------------------------------------------------------------------------*/
void P_FCT abg_chk(COMMON_P M_p, MNODE *mnode_p)
{
   GA_P gbla_p = M_p->gbla_p;
   GRAPH new_graph;
   ARC *arc_array;
   int max_arcs  = 2*GRPGTCNT;

   arc_array = malloc(2 * max_arcs * sizeof(ARC));
   new_graph.St_A = arc_array;
   new_graph.Fn_A = arc_array + max_arcs;
   M_p->erh_action = ERH_W_SEV+ERH_LOCATE;
   if (mnode_p->is.connector) get_graph(M_p, OR_CONN, mnode_p, &new_graph);
   free(arc_array);
}

/*STATIC------------------------------------------------------------enter_arcs-+
| Move arcs from "arc_pS0" to "arc_pSL" to target "arc_pT0", excluding the     |
| arcs found in the "arg_pC0" to "arg_pCL" list.                               |
| Returns next target.                                                         |
+-----------------------------------------------------------------------------*/
static ARC * LP_FCT enter_arcs(
   ARC *arc_pS0, ARC *arc_pSL, /* Source (arcs to be entered) from.. to.. */
   ARC *arc_pT0,               /* Target (where to enter them) */
   ARC *arc_pC0, ARC *arc_pCL  /* Compared to (check redundancy) from.. to ..*/
) {
   ARC *arc_pS, *arc_pT, *arc_pC;

   arc_pT = arc_pT0;
   for (arc_pS=arc_pS0; arc_pS < arc_pSL; ++arc_pS) {
      for (arc_pC = arc_pC0; ; ++arc_pC) {
         if (arc_pC == arc_pCL) {        /* not found in the list: */
            *(arc_pT++) = *arc_pS;       /* enter new arc */
            break;
         }
         if (*arc_pS == *arc_pC) break;  /* found in the list: break */
      }
   }
   return(arc_pT);
}

/*STATIC-----------------------------------------------------------check_ambig-+
|                                                                              |
+-----------------------------------------------------------------------------*/
static void LP_FCT check_ambig(COMMON_P M_p, MNODE *mnode_p1, MNODE *mnode_p2)
{
   GI *gi_p1, *gi_p2;

   if (mnode_p1 == mnode_p2) return;
   if (mnode_p1->is.ambig_found) return;   /* Already said */

   if (mnode_p1->is.datatag) {
      gi_p1 = (GI *)0;
   }else {
      gi_p1 = mnode_p1->u.gi_p;
   }
   if (mnode_p2->is.datatag) {
      gi_p2 = (GI *)0;
   }else {
      gi_p2 = mnode_p2->u.gi_p;
   }
   if (gi_p1 == gi_p2) {
#ifdef DEBUG_IS_NEEDED
      printf(
         "%*s** %s is ambiguous: %s\n",
         3*recurse_level, "",
         gi_p1 ?  gi_p1->name_p : M_p->gbla_p->gnwdtab.PCDATA.s.p,
         ambg_explain
      );
#endif
      errorh(
         M_p->gbla_p, AMBMDL, M_p->erh_action,
         gi_p1 ?  gi_p1->name_p : M_p->gbla_p->gnwdtab.PCDATA.s.p
      );
      mnode_p1->is.ambig_found = TRUE;
      M_p->erh_action = ERH_W_SEV;      /* To have only one ERH_LOCATE */
   }
}

/*STATIC-------------------------------------------------------------get_graph-+
| Recursively reduce each model group to a list of:                            |
|    - arcs emaning from start state, (St_A)                                   |
|    - arcs emaning from final state, (Fn_A)                                   |
|                                                                              |
| A) Given a group, examine sequentially each token.                           |
|    - If the token is an elementary token, add the element to new_St_A;       |
|    - If the token is a new group, recurse and get the new_St_A and new_Fn_A  |
|      of this group.                                                          |
|                                                                              |
| B) If the token is repeatable, check the REPEAT_AMBG ambiguities: confront   |
|    the arcs emaning from final states with arcs emaning from start states    |
|    (new_St vs new_Fn).                                                       |
|                                                                              |
| C) If the token is omittable, the arcs emaning from final states must        |
|    include those emaning from start state: because the token is omittable,   |
|    the start-state can also be a final-state.                                |
|                                                                              |
| D) Then, update the St_A/Fn_A for the group from the new_St_A                |
|    and/or new_Fn_A, depending of the group's connector:                      |
|                                                                              |
| D-1) In an OR group:                                                         |
|    - arcs-from-start-state of the group are                                  |
|      arcs-from-start-state of each token                                     |
|    - arcs-from-final-state of the group are                                  |
|      arcs-from-final-state of each token                                     |
|                                                                              |
| D-2) In an AND group:                                                        |
|    AND group are like OR group, except that, for ALL tokens of the group     |
|    arcs-from-start-state must not duplicate ANY arc-from-final-state.        |
|    Since AND are processed like ORs, this test (check for AND_AMBG           |
|    ambiguities) can be done at the end since the group.St and group.Fn       |
|    are the union of (respectively) each token St and Fn.                     |
|                                                                              |
| D-3) In a SEQ group:                                                         |
|    - check SEQUENCE_AMBG ambiguities: confront arcs-from-start-state         |
|      of each token with current arcs-from-final-state of the group.          |
|    - stop cumulating arcs-from-start-state after the first required token    |
|      is found.  I.e., the first token non OMITTABLE ('+' or '1') is the      |
|      last token the new_St_A of which is added to the St_A of the group.     |
|    - then, forget about arcs-from-final-state, until the token is required.  |
|      I.e., Fn_A of the group begins to be updated with the last required     |
|      token, including this one iff it is repeatable ('+').                   |
|      Note: this last condition is not explicitely coded at this point:       |
|           if the last required token is also repeatable ('+'), it has        |
|           already been added to new_Fn by C).                                |
|                                                                              |
| E) Detect the other ambiguities (ST_AMBG) by examining the St_A.             |
|                                                                              |
|                                                                              |
| Implementation Notes:                                                        |
| -  Arcs of the group (St_A/Fn_A) are stored between group_graph and new_graph|
|    Arcs of the currently examined token (new_St_A/new_Fn_A) are between      |
|    new_graph and end_graph                                                   |
|                                                                              |
| -  To speed up the process, only arcs which are duplicated are stored.       |
+-----------------------------------------------------------------------------*/
static void LP_FCT get_graph(
   COMMON_P M_p,
   uint connector,
   MNODE *mnode_p,
   GRAPH_P group_graph_p)
{
   GRAPH new_graph;
   GRAPH end_graph;                           /* working graph for recursion */
   ARC *arc_p1, *arc_p2;
   boolean required_found = FALSE;

#ifdef DEBUG_IS_NEEDED
   ++recurse_level;
   if (!recurse_level) printf("----------------- test %d\n", testcase_count++);
#endif
   new_graph = *group_graph_p;
   for (;;) {
      show_what(mnode_p);
      end_graph = new_graph;
      if (mnode_p->is.connector) {
         get_graph(M_p, mnode_p->is.connector, mnode_p->u.llink, &end_graph);
#if defined(DEBUG_IS_NEEDED) && defined(DEBUG_SEE_ALL)
      }else {
         *(end_graph.St_A++) = mnode_p;
#else
      }else if (mnode_p->is.datatag || mnode_p->is.pcdata) {
         if (M_p->is_PCDATA_duplicate) *(end_graph.St_A++) = mnode_p;
      }else if (mnode_p->u.gi_p->is_duplicate) {
         *(end_graph.St_A++) = mnode_p;
#endif
      }
      if (mnode_p->is.occurence) {                   /* omittable/repeatable */
         if (mnode_p->is.occurence & REPEATABLE) {   /* '+' or '*' */
            SET_AMBG_TYPE(REPEAT_AMBG)
            for (arc_p1=new_graph.Fn_A; arc_p1 < end_graph.Fn_A; ++arc_p1) {
               for (arc_p2 = new_graph.St_A;arc_p2 < end_graph.St_A;++arc_p2) {
                  check_ambig(M_p, *arc_p1, *arc_p2);
               }
            }
         }
         if (mnode_p->is.occurence & OMITTABLE) {    /* '?' or '*' */
            end_graph.Fn_A = enter_arcs(             /* add ... */
               new_graph.St_A, end_graph.St_A,       /* new_St_A ... */
               end_graph.Fn_A,                       /* to new_Fn_A ... */
               new_graph.Fn_A, end_graph.Fn_A        /* not already new_Fn_A */
            );
         }
      }
      switch(connector) {
      case AND_CONN:
      case OR_CONN:
         new_graph.St_A = enter_arcs(                /* add ... */
            new_graph.St_A, end_graph.St_A,          /* new_St_A ... */
            new_graph.St_A,                          /* to group St_A ... */
            group_graph_p->St_A, new_graph.St_A      /* avoiding duplicate */
         );
         new_graph.Fn_A = enter_arcs(                /* add ... */
            new_graph.Fn_A, end_graph.Fn_A,          /* new_Fn_A ... */
            new_graph.Fn_A,                          /* to group Fn_A ...*/
            group_graph_p->Fn_A, new_graph.Fn_A      /* avoiding duplicate */
         );
         break;
      case SEQ_CONN:
         /*-----------------------------------------------------+
         |Check ambiguities between previous Fn_A vs. new_St_A: |
         +-----------------------------------------------------*/
         SET_AMBG_TYPE(SEQUENCE_AMBG)
         for (arc_p1=group_graph_p->Fn_A; arc_p1 < new_graph.Fn_A; ++arc_p1) {
            for (arc_p2 = new_graph.St_A; arc_p2 < end_graph.St_A; ++arc_p2) {
               check_ambig(M_p, *arc_p1, *arc_p2);
            }
         }
         if (!required_found) {                      /* until required found */
            new_graph.St_A = enter_arcs(             /* continue to add ... */
               new_graph.St_A, end_graph.St_A,       /* new_St_A ... */
               new_graph.St_A,                       /* to St_A ... */
               group_graph_p->St_A, new_graph.St_A   /* not already in group */
            );
         }
         if (!(mnode_p->is.occurence & OMITTABLE)) { /* if required */
            required_found = TRUE;
            new_graph.Fn_A = enter_arcs(             /* reset group Fn_A ... */
               new_graph.Fn_A, end_graph.Fn_A,       /* to just the new_Fn_A */
               group_graph_p->Fn_A,                  /* adding to the group */
               (ARC *)0, (ARC *)0                    /* compare is useless */
            );
         }else {
            new_graph.Fn_A = enter_arcs(             /* continue to add ... */
               new_graph.Fn_A, end_graph.Fn_A,       /* new_Fn_A ... */
               new_graph.Fn_A,                       /* to Fn_A ... */
               group_graph_p->Fn_A, new_graph.Fn_A   /* not already in group */
            );
         }
         break;
      }
      show_graph(group_graph_p, &new_graph);
      if (!mnode_p->is.rtag) break;
      mnode_p = mnode_p->rlink;
   }
   if (connector == AND_CONN) {
      /*-----------------------------------------------+
      |Check ambiguities between group_St vs. group_Fn |
      +-----------------------------------------------*/
      SET_AMBG_TYPE(AND_AMBG)
      for (arc_p1=group_graph_p->Fn_A; arc_p1 < new_graph.Fn_A; ++arc_p1) {
         for (arc_p2 = group_graph_p->St_A; arc_p2 < new_graph.St_A; ++arc_p2) {
            if (*arc_p1 != *arc_p2) check_ambig(M_p, *arc_p1, *arc_p2);
         }
      }
   }
   /*-----------------------------+
   |Confront group_graph_p->St_A  |
   |to get the ambiguities if any.|
   +-----------------------------*/
   SET_AMBG_TYPE(ST_AMBG)
   for (arc_p1=group_graph_p->St_A; arc_p1 < new_graph.St_A-1; ++arc_p1) {
      for (arc_p2 = arc_p1 + 1; arc_p2 < new_graph.St_A; ++arc_p2) {
         check_ambig(M_p, *arc_p1, *arc_p2);
      }
   }
   *group_graph_p = new_graph;
#ifdef DEBUG_IS_NEEDED
   --recurse_level;
#endif
}

#ifdef DEBUG_IS_NEEDED       /* DEBUG ONLY */
/*STATIC-------------------------------------------------------------show_what-+
|                                                                              |
+-----------------------------------------------------------------------------*/
static void LP_FCT show_what(MNODE *mnode_p)
{
   printf("%*s", 3*recurse_level,"");  /* indent 3 blanks per recurse_level */
   switch(mnode_p->is.connector) {
   case SEQ_CONN:
      printf("SEQ group ");
      break;
   case AND_CONN:
      printf("AND group ");
      break;
   case OR_CONN:
      printf("OR group ");
      break;
   case NULL_CONN:
      if (mnode_p->is.pcdata) {
         printf("#PCDATA: %04x ", mnode_p);
      }else if (mnode_p->is.datatag) {
         printf("#PCDATG: %04x ", mnode_p);
      }else {
         printf("GI %s:%04x ", mnode_p->u.gi_p->name_p, mnode_p);
      }
      break;
   }
   switch (mnode_p->is.occurence) {
   case PLUS_OCCUR: printf("(+)"); break;
   case REP_OCCUR:  printf("(*)"); break;
   case OPT_OCCUR:  printf("(?)"); break;
   default:         printf("(1)"); break;
   }
   printf("\n");
}

/*STATIC------------------------------------------------------------show_graph-+
|                                                                              |
+-----------------------------------------------------------------------------*/
static void LP_FCT show_graph(GRAPH_P start_graph_p, GRAPH_P end_graph_p)
{
   ARC *arc_p;

   printf("%*.s- St_A=", 3*recurse_level, "");
   for (arc_p = start_graph_p->St_A; arc_p < end_graph_p->St_A; ++arc_p) {
      printf(
         "%s:%04x ",
         (*arc_p)->u.gi_p ? (*arc_p)->u.gi_p->name_p : "#PCDATA",
         (*arc_p)
      );
   }
   printf("\n");
   printf("%*.s- Fn_A=", 3*recurse_level, "");
   for (arc_p = start_graph_p->Fn_A; arc_p < end_graph_p->Fn_A; ++arc_p) {
      printf(
         "%s:%04x ",
         (*arc_p)->u.gi_p ? (*arc_p)->u.gi_p->name_p : "#PCDATA",
         (*arc_p)
      );
   }
   printf("\n");
}
#endif
/******************************************************************************/
