/* dfa - DFA construction routines */

/*  Copyright (c) 1990 The Regents of the University of California. */

/*  All rights reserved. */

/*  This code is derived from software contributed to Berkeley by */

/*  Vern Paxson. */

/*  The United States Government has rights in this work pursuant */

/*  to contract no. DE-AC03-76SF00098 between the United States */

/*  Department of Energy and the University of California. */

/*  Redistribution and use in source and binary forms, with or without */

/*  modification, are permitted provided that the following conditions */

/*  are met: */

/*  1. Redistributions of source code must retain the above copyright */

/*     notice, this list of conditions and the following disclaimer. */

/*  2. Redistributions in binary form must reproduce the above copyright */

/*     notice, this list of conditions and the following disclaimer in the */

/*     documentation and/or other materials provided with the distribution. */

/*  Neither the name of the University nor the names of its contributors */

/*  may be used to endorse or promote products derived from this software */

/*  without specific prior written permission. */

/*  THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */

/*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */

/*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */

/*  PURPOSE. */

#include "flexdef.h"

#include "tables.h"

/* declare functions that have forward references */

static void dump_associated_rules(FILE *, int);

static void dump_transitions(FILE *, int[]);

static int  snstods(int[], int, int[], int, int, int *);

static void sympartition(int[], int, int[], int[]);

static int  symfollowset(int[], int, int, int[]);

/* check_for_backing_up - check a DFA state for backing up

 *

 * synopsis

 *     void check_for_backing_up( int ds, int state[numecs] );

 *

 * ds is the number of the state to check and state[] is its out-transitions,

 * indexed by equivalence class.

 */

static void check_for_backing_up(int ds, int state[])

{

  if ((reject && !dfaacc[ds].dfaacc_set) || (!reject && !dfaacc[ds].dfaacc_state)) { /* state is non-accepting */

    ++num_backing_up;

    if (env.backing_up_report) {

      fprintf (ctrl.backing_up_file,

         _("State #%d is non-accepting -\n"), ds);

      /* identify the state */

      dump_associated_rules (ctrl.backing_up_file, ds);

      /* Now identify it further using the out- and

       * jam-transitions.

       */

      dump_transitions (ctrl.backing_up_file, state);

      putc ('\n', ctrl.backing_up_file);

    }

  }

}

/* check_trailing_context - check to see if NFA state set constitutes

 *                          "dangerous" trailing context

 *

 * synopsis

 *    void check_trailing_context( int nfa_states[num_states+1], int num_states,

 *        int accset[nacc+1], int nacc );

 *

 * NOTES

 *  Trailing context is "dangerous" if both the head and the trailing

 *  part are of variable size \and/ there's a DFA state which contains

 *  both an accepting state for the head part of the rule and NFA states

 *  which occur after the beginning of the trailing context.

 *

 *  When such a rule is matched, it's impossible to tell if having been

 *  in the DFA state indicates the beginning of the trailing context or

 *  further-along scanning of the pattern.  In these cases, a warning

 *  message is issued.

 *

 *    nfa_states[1 .. num_states] is the list of NFA states in the DFA.

 *    accset[1 .. nacc] is the list of accepting numbers for the DFA state.

 */

static void check_trailing_context(int *nfa_states, int num_states, int *accset, int nacc)

{

  int i, j;

  for (i = 1; i <= num_states; ++i) {

    int     ns = nfa_states[i];

    int type = state_type[ns];

    int ar = assoc_rule[ns];

    if (type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE) { /* do nothing */

    }

    else if (type == STATE_TRAILING_CONTEXT) {

      /* Potential trouble.  Scan set of accepting numbers

       * for the one marking the end of the "head".  We

       * assume that this looping will be fairly cheap

       * since it's rare that an accepting number set

       * is large.

       */

      for (j = 1; j <= nacc; ++j)

        if (accset[j] & YY_TRAILING_HEAD_MASK) {

          line_warning (_

                  ("dangerous trailing context"),

                  rule_linenum[ar]);

          return;

        }

    }

  }

}

/* dump_associated_rules - list the rules associated with a DFA state

 *

 * Goes through the set of NFA states associated with the DFA and

 * extracts the first MAX_ASSOC_RULES unique rules, sorts them,

 * and writes a report to the given file.

 */

static void dump_associated_rules(FILE *file, int ds)

{

  int i, j;

  int num_associated_rules = 0;

  int rule_set[MAX_ASSOC_RULES + 1];

  int *dset = dss[ds];

  int size = dfasiz[ds];

  for (i = 1; i <= size; ++i) {

    int rule_num = rule_linenum[assoc_rule[dset[i]]];

    for (j = 1; j <= num_associated_rules; ++j)

      if (rule_num == rule_set[j])

        break;

    if (j > num_associated_rules) { /* new rule */

      if (num_associated_rules < MAX_ASSOC_RULES)

        rule_set[++num_associated_rules] =

          rule_num;

    }

  }

  qsort (&rule_set [1], (size_t) num_associated_rules, sizeof (rule_set [1]), intcmp);

  fprintf (file, _(" associated rule line numbers:"));

  for (i = 1; i <= num_associated_rules; ++i) {

    if (i % 8 == 1)

      putc ('\n', file);

    fprintf (file, "\t%d", rule_set[i]);

  }

  putc ('\n', file);

}

/* dump_transitions - list the transitions associated with a DFA state

 *

 * synopsis

 *     dump_transitions( FILE *file, int state[numecs] );

 *

 * Goes through the set of out-transitions and lists them in human-readable

 * form (i.e., not as equivalence classes); also lists jam transitions

 * (i.e., all those which are not out-transitions, plus EOF).  The dump

 * is done to the given file.

 */

static void dump_transitions(FILE *file, int state[])

{

  int i, ec;

  int out_char_set[CSIZE];

  for (i = 0; i < ctrl.csize; ++i) {

    ec = ABS (ecgroup[i]);

    out_char_set[i] = state[ec];

  }

  fprintf (file, _(" out-transitions: "));

  list_character_set (file, out_char_set);

  /* now invert the members of the set to get the jam transitions */

  for (i = 0; i < ctrl.csize; ++i)

    out_char_set[i] = !out_char_set[i];

  fprintf (file, _("\n jam-transitions: EOF "));

  list_character_set (file, out_char_set);

  putc ('\n', file);

}

/* epsclosure - construct the epsilon closure of a set of ndfa states

 *

 * synopsis

 *    int *epsclosure( int t[num_states], int *numstates_addr,

 *      int accset[num_rules+1], int *nacc_addr,

 *      int *hashval_addr );

 *

 * NOTES

 *  The epsilon closure is the set of all states reachable by an arbitrary

 *  number of epsilon transitions, which themselves do not have epsilon

 *  transitions going out, unioned with the set of states which have non-null

 *  accepting numbers.  t is an array of size numstates of nfa state numbers.

 *  Upon return, t holds the epsilon closure and *numstates_addr is updated.

 *  accset holds a list of the accepting numbers, and the size of accset is

 *  given by *nacc_addr.  t may be subjected to reallocation if it is not

 *  large enough to hold the epsilon closure.

 *

 *  hashval is the hash value for the dfa corresponding to the state set.

 */

static int *epsclosure(int *t, int *ns_addr, int accset[], int *nacc_addr, int *hv_addr)

{

  int     stkpos, ns, tsp;

  int     numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;

  int     stkend, nstate;

  static int did_stk_init = false, *stk;

#define MARK_STATE(state) \

do{ trans1[state] = trans1[state] - MARKER_DIFFERENCE;} while(0)

#define IS_MARKED(state) (trans1[state] < 0)

#define UNMARK_STATE(state) \

do{ trans1[state] = trans1[state] + MARKER_DIFFERENCE;} while(0)

#define CHECK_ACCEPT(state) \

do{ \

nfaccnum = accptnum[state]; \

if ( nfaccnum != NIL ) \

accset[++nacc] = nfaccnum; \

}while(0)

#define DO_REALLOCATION() \

do { \

current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \

++num_reallocs; \

t = reallocate_integer_array( t, current_max_dfa_size ); \

stk = reallocate_integer_array( stk, current_max_dfa_size ); \

}while(0) \

#define PUT_ON_STACK(state) \

do { \

if ( ++stkend >= current_max_dfa_size ) \

DO_REALLOCATION(); \

stk[stkend] = state; \

MARK_STATE(state); \

}while(0)

#define ADD_STATE(state) \

do { \

if ( ++numstates >= current_max_dfa_size ) \

DO_REALLOCATION(); \

t[numstates] = state; \

hashval += state; \

}while(0)

#define STACK_STATE(state) \

do { \

PUT_ON_STACK(state); \

CHECK_ACCEPT(state); \

if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \

ADD_STATE(state); \

}while(0)

  if (!did_stk_init) {

    stk = allocate_integer_array (current_max_dfa_size);

    did_stk_init = true;

  }

  nacc = stkend = hashval = 0;

  for (nstate = 1; nstate <= numstates; ++nstate) {

    ns = t[nstate];

    /* The state could be marked if we've already pushed it onto

     * the stack.

     */

    if (!IS_MARKED (ns)) {

      PUT_ON_STACK (ns);

      CHECK_ACCEPT (ns);

      hashval += ns;

    }

  }

  for (stkpos = 1; stkpos <= stkend; ++stkpos) {

    ns = stk[stkpos];

    transsym = transchar[ns];

    if (transsym == SYM_EPSILON) {

      tsp = trans1[ns] + MARKER_DIFFERENCE;

      if (tsp != NO_TRANSITION) {

        if (!IS_MARKED (tsp))

          STACK_STATE (tsp);

        tsp = trans2[ns];

        if (tsp != NO_TRANSITION

            && !IS_MARKED (tsp))

          STACK_STATE (tsp);

      }

    }

  }

  /* Clear out "visit" markers. */

  for (stkpos = 1; stkpos <= stkend; ++stkpos) {

    if (IS_MARKED (stk[stkpos]))

      UNMARK_STATE (stk[stkpos]);

    else

      flexfatal (_

           ("consistency check failed in epsclosure()"));

  }

  *ns_addr = numstates;

  *hv_addr = hashval;

  *nacc_addr = nacc;

  return t;

}

/* increase_max_dfas - increase the maximum number of DFAs */

void increase_max_dfas (void)

{

  current_max_dfas += MAX_DFAS_INCREMENT;

  ++num_reallocs;

  base = reallocate_integer_array (base, current_max_dfas);

  def = reallocate_integer_array (def, current_max_dfas);

  dfasiz = reallocate_integer_array (dfasiz, current_max_dfas);

  accsiz = reallocate_integer_array (accsiz, current_max_dfas);

  dhash = reallocate_integer_array (dhash, current_max_dfas);

  dss = reallocate_int_ptr_array (dss, current_max_dfas);

  dfaacc = reallocate_array(dfaacc, current_max_dfas,

    sizeof(union dfaacc_union));

  if (nultrans)

    nultrans =

      reallocate_integer_array (nultrans,

              current_max_dfas);

}

/* ntod - convert an ndfa to a dfa

 *

 * Creates the dfa corresponding to the ndfa we've constructed.  The

 * dfa starts out in state #1.

 *

 * Return the amount of space, in bytes, allocated for the next table.

 * In some modes this can be zero.

 */

size_t ntod (void)

{

  int    *accset, ds, nacc, newds;

  int     sym, hashval, numstates, dsize;

  int     num_full_table_rows=0;  /* used only for -f */

  int    *nset, *dset;

  int     targptr, totaltrans, i, comstate, comfreq, targ;

  int     symlist[CSIZE + 1];

  int     num_start_states;

  int     todo_head, todo_next;

  struct yytbl_data *yynxt_tbl = 0;

  flex_int32_t *yynxt_data = 0, yynxt_curr = 0;

  /* Note that the following are indexed by *equivalence classes*

   * and not by characters.  Since equivalence classes are indexed

   * beginning with 1, even if the scanner accepts NUL's, this

   * means that (since every character is potentially in its own

   * equivalence class) these arrays must have room for indices

   * from 1 to CSIZE, so their size must be CSIZE + 1.

   */

  int     duplist[CSIZE + 1], state[CSIZE + 1];

  int     targfreq[CSIZE + 1] = {0}, targstate[CSIZE + 1];

  /* accset needs to be large enough to hold all of the rules present

   * in the input, *plus* their YY_TRAILING_HEAD_MASK variants.

   */

  accset = allocate_integer_array ((num_rules + 1) * 2);

  nset = allocate_integer_array (current_max_dfa_size);

  /* The "todo" queue is represented by the head, which is the DFA

   * state currently being processed, and the "next", which is the

   * next DFA state number available (not in use).  We depend on the

   * fact that snstods() returns DFA's \in increasing order/, and thus

   * need only know the bounds of the dfas to be processed.

   */

  todo_head = todo_next = 0;

  for (i = 0; i <= ctrl.csize; ++i) {

    duplist[i] = NIL;

    symlist[i] = false;

  }

  for (i = 0; i <= num_rules; ++i)

    accset[i] = NIL;

  if (env.trace) {

    dumpnfa (scset[1]);

    fputs (_("\n\nDFA Dump:\n\n"), stderr);

  }

  inittbl ();

  /* Check to see whether we should build a separate table for

   * transitions on NUL characters.  We don't do this for full-speed

   * (-F) scanners, since for them we don't have a simple state

   * number lying around with which to index the table.  We also

   * don't bother doing it for scanners unless (1) NUL is in its own

   * equivalence class (indicated by a positive value of

   * ecgroup[NUL]), (2) NUL's equivalence class is the last

   * equivalence class, and (3) the number of equivalence classes is

   * the same as the number of characters.  This latter case comes

   * about when useecs is false or when it's true but every character

   * still manages to land in its own class (unlikely, but it's

   * cheap to check for).  If all these things are true then the

   * character code needed to represent NUL's equivalence class for

   * indexing the tables is going to take one more bit than the

   * number of characters, and therefore we won't be assured of

   * being able to fit it into a YY_CHAR variable.  This rules out

   * storing the transitions in a compressed table, since the code

   * for interpreting them uses a YY_CHAR variable (perhaps it

   * should just use an integer, though; this is worth pondering ...

   * ###).

   *

   * Finally, for full tables, we want the number of entries in the

   * table to be a power of two so the array references go fast (it

   * will just take a shift to compute the major index).  If

   * encoding NUL's transitions in the table will spoil this, we

   * give it its own table (note that this will be the case if we're

   * not using equivalence classes).

   */

  /* Note that the test for ecgroup[0] == numecs below accomplishes

   * both (1) and (2) above

   *

   * New way: we will only use NUL table for fulltbl, because the

   * scanner will use an integer instead of YY_CHAR as noted above

   */

  if (ctrl.fulltbl && ecgroup[0] == numecs && is_power_of_2(numecs))

    nultrans = allocate_integer_array (current_max_dfas);

  if (ctrl.fullspd) {

    for (i = 0; i <= numecs; ++i)

      state[i] = 0;

    place_state (state, 0, 0);

    dfaacc[0].dfaacc_state = 0;

  }

  else if (ctrl.fulltbl) {

    if (nultrans)

      /* We won't be including NUL's transitions in the

       * table, so build it for entries from 0 .. numecs - 1.

       */

      num_full_table_rows = numecs;

    else

      /* Take into account the fact that we'll be including

       * the NUL entries in the transition table.  Build it

       * from 0 .. numecs.

       */

      num_full_table_rows = numecs + 1;

    /* Begin generating yy_nxt[][]

     * This spans the entire LONG function.

     * This table is tricky because we don't know how big it will be.

     * So we'll have to realloc() on the way...

     * we'll wait until we can calculate yynxt_tbl->td_hilen.

     */

    yynxt_tbl = calloc(1, sizeof (struct yytbl_data));

    yytbl_data_init (yynxt_tbl, YYTD_ID_NXT);

    yynxt_tbl->td_hilen = 1;

    yynxt_tbl->td_lolen = (flex_uint32_t) num_full_table_rows;

    yynxt_tbl->td_data = yynxt_data =

        calloc(yynxt_tbl->td_lolen *

         yynxt_tbl->td_hilen,

         sizeof (flex_int32_t));

    yynxt_curr = 0;

    struct packtype_t *ptype = optimize_pack(0);

    /* Note: Used when ctrl.fulltbl is on. Alternately defined elsewhere */

    out_str ("m4_define([[M4_HOOK_NXT_TYPE]], [[%s]])", ptype->name);

    out_dec ("m4_define([[M4_HOOK_NXT_ROWS]], [[%d]])", num_full_table_rows);

    outn ("m4_define([[M4_HOOK_NXT_BODY]], [[m4_dnl");

    outn ("M4_HOOK_TABLE_OPENER");

    if (gentables)

      outn ("M4_HOOK_TABLE_OPENER");

    /* Generate 0 entries for state #0. */

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

      mk2data (0);

      yynxt_data[yynxt_curr++] = 0;

    }

    if (gentables) {

      dataflush ();

      outn ("M4_HOOK_TABLE_CONTINUE");

    }

  }

  /* Create the first states. */

  num_start_states = lastsc * 2;

  for (i = 1; i <= num_start_states; ++i) {

    numstates = 1;

    /* For each start condition, make one state for the case when

     * we're at the beginning of the line (the '^' operator) and

     * one for the case when we're not.

     */

    if (i % 2 == 1)

      nset[numstates] = scset[(i / 2) + 1];

    else

      nset[numstates] =

        mkbranch (scbol[i / 2], scset[i / 2]);

    nset = epsclosure (nset, &numstates, accset, &nacc,

           &hashval);

    if (snstods (nset, numstates, accset, nacc, hashval, &ds)) {

      numas += nacc;

      totnst += numstates;

      ++todo_next;

      if (variable_trailing_context_rules && nacc > 0)

        check_trailing_context (nset, numstates,

              accset, nacc);

    }

  }

  if (!ctrl.fullspd) {

    if (!snstods (nset, 0, accset, 0, 0, &end_of_buffer_state))

      flexfatal (_

           ("could not create unique end-of-buffer state"));

    ++numas;

    ++num_start_states;

    ++todo_next;

  }

  while (todo_head < todo_next) {

    targptr = 0;

    totaltrans = 0;

    for (i = 1; i <= numecs; ++i)

      state[i] = 0;

    ds = ++todo_head;

    dset = dss[ds];

    dsize = dfasiz[ds];

    if (env.trace)

      fprintf (stderr, _("state # %d:\n"), ds);

    sympartition (dset, dsize, symlist, duplist);

    for (sym = 1; sym <= numecs; ++sym) {

      if (symlist[sym]) {

        symlist[sym] = 0;

        if (duplist[sym] == NIL) {

          /* Symbol has unique out-transitions. */

          numstates =

            symfollowset (dset, dsize,

                    sym, nset);

          nset = epsclosure (nset,

                 &numstates,

                 accset, &nacc,

                 &hashval);

          if (snstods

              (nset, numstates, accset, nacc,

               hashval, &newds)) {

            totnst = totnst +

              numstates;

            ++todo_next;

            numas += nacc;

            if (variable_trailing_context_rules && nacc > 0)

              check_trailing_context

                (nset,

                 numstates,

                 accset,

                 nacc);

          }

          state[sym] = newds;

          if (env.trace)

            fprintf (stderr,

               "\t%d\t%d\n", sym,

               newds);

          targfreq[++targptr] = 1;

          targstate[targptr] = newds;

          ++numuniq;

        }

        else {

          /* sym's equivalence class has the same

           * transitions as duplist(sym)'s

           * equivalence class.

           */

          targ = state[duplist[sym]];

          state[sym] = targ;

          if (env.trace)

            fprintf (stderr,

               "\t%d\t%d\n", sym,

               targ);

          /* Update frequency count for

           * destination state.

           */

          i = 0;

          while (targstate[++i] != targ) ;

          ++targfreq[i];

          ++numdup;

        }

        ++totaltrans;

        duplist[sym] = NIL;

      }

    }

    numsnpairs += totaltrans;

    if (ds > num_start_states)

      check_for_backing_up (ds, state);

    if (nultrans) {

      nultrans[ds] = state[NUL_ec];

      state[NUL_ec] = 0;  /* remove transition */

    }

    if (ctrl.fulltbl) {

      /* Each time we hit here, it's another td_hilen, so we realloc. */

      yynxt_tbl->td_hilen++;

      yynxt_tbl->td_data = yynxt_data =

        realloc (yynxt_data,

                 yynxt_tbl->td_hilen *

                 yynxt_tbl->td_lolen *

                 sizeof (flex_int32_t));

      if (gentables)

        outn ("M4_HOOK_TABLE_OPENER");

      /* Supply array's 0-element. */

      if (ds == end_of_buffer_state) {

        mk2data (-end_of_buffer_state);

        yynxt_data[yynxt_curr++] =

          -end_of_buffer_state;

      }

      else {

        mk2data (end_of_buffer_state);

        yynxt_data[yynxt_curr++] =

          end_of_buffer_state;

      }

      for (i = 1; i < num_full_table_rows; ++i) {

        /* Jams are marked by negative of state

         * number.

         */

        mk2data (state[i] ? state[i] : -ds);

        yynxt_data[yynxt_curr++] =

          state[i] ? state[i] : -ds;

      }

      if (gentables) {

        dataflush ();

        outn ("M4_HOOK_TABLE_CONTINUE");

      }

    }

    else if (ctrl.fullspd)

      place_state (state, ds, totaltrans);

    else if (ds == end_of_buffer_state)

      /* Special case this state to make sure it does what

       * it's supposed to, i.e., jam on end-of-buffer.

       */

      stack1 (ds, 0, 0, JAMSTATE);

    else {   /* normal, compressed state */

      /* Determine which destination state is the most

       * common, and how many transitions to it there are.

       */

      comfreq = 0;

      comstate = 0;

      for (i = 1; i <= targptr; ++i)

        if (targfreq[i] > comfreq) {

          comfreq = targfreq[i];

          comstate = targstate[i];

        }

      bldtbl (state, ds, totaltrans, comstate, comfreq);

    }

  }

  if (ctrl.fulltbl) {

    dataend ("M4_HOOK_TABLE_CLOSER");

    outn("/* body */]])");

    if (tablesext) {

      yytbl_data_compress (yynxt_tbl);

      if (yytbl_data_fwrite (&tableswr, yynxt_tbl) < 0)

        flexerror (_

             ("Could not write yynxt_tbl[][]"));

    }

    if (yynxt_tbl) {

      yytbl_data_destroy (yynxt_tbl);

      yynxt_tbl = 0;

    }

  }

  else if (!ctrl.fullspd) {

    cmptmps (); /* create compressed template entries */

    /* Create tables for all the states with only one

     * out-transition.

     */

    while (onesp > 0) {

      mk1tbl (onestate[onesp], onesym[onesp],

        onenext[onesp], onedef[onesp]);

      --onesp;

    }

    mkdeftbl ();

  }

  free(accset);

  free(nset);

  return (yynxt_tbl != NULL) ? (yynxt_tbl->td_hilen * sizeof(int32_t)) : 0;

}

/* snstods - converts a set of ndfa states into a dfa state

 *

 * synopsis

 *    is_new_state = snstods( int sns[numstates], int numstates,

 *        int accset[num_rules+1], int nacc,

 *        int hashval, int *newds_addr );

 *

 * On return, the dfa state number is in newds.

 */

static int snstods(int sns[], int numstates, int accset[], int nacc, int hashval, int *newds_addr)

{

  int didsort = 0;

  int i, j;

  int newds, *oldsns;

  for (i = 1; i <= lastdfa; ++i)

    if (hashval == dhash[i]) {

      if (numstates == dfasiz[i]) {

        oldsns = dss[i];

        if (!didsort) {

          /* We sort the states in sns so we

           * can compare it to oldsns quickly.

           */

          qsort (&sns [1], (size_t) numstates, sizeof (sns [1]), intcmp);

          didsort = 1;

        }

        for (j = 1; j <= numstates; ++j)

          if (sns[j] != oldsns[j])

            break;

        if (j > numstates) {

          ++dfaeql;

          *newds_addr = i;

          return 0;

        }

        ++hshcol;

      }

      else

        ++hshsave;

    }

  /* Make a new dfa. */

  if (++lastdfa >= current_max_dfas)

    increase_max_dfas ();

  newds = lastdfa;

  dss[newds] = allocate_integer_array (numstates + 1);

  /* If we haven't already sorted the states in sns, we do so now,

   * so that future comparisons with it can be made quickly.

   */

  if (!didsort)

            qsort (&sns [1], (size_t) numstates, sizeof (sns [1]), intcmp);

  for (i = 1; i <= numstates; ++i)

    dss[newds][i] = sns[i];

  dfasiz[newds] = numstates;

  dhash[newds] = hashval;

  if (nacc == 0) {

    if (reject)

      dfaacc[newds].dfaacc_set = NULL;

    else

      dfaacc[newds].dfaacc_state = 0;

    accsiz[newds] = 0;

  }

  else if (reject) {

    /* We sort the accepting set in increasing order so the

     * disambiguating rule that the first rule listed is considered

     * match in the event of ties will work.

     */

    qsort (&accset [1], (size_t) nacc, sizeof (accset [1]), intcmp);

    dfaacc[newds].dfaacc_set =

      allocate_integer_array (nacc + 1);

    /* Save the accepting set for later */

    for (i = 1; i <= nacc; ++i) {

      dfaacc[newds].dfaacc_set[i] = accset[i];

      if (accset[i] <= num_rules)

        /* Who knows, perhaps a REJECT can yield

         * this rule.

         */

        rule_useful[accset[i]] = true;

    }

    accsiz[newds] = nacc;

  }

  else {

    /* Find lowest numbered rule so the disambiguating rule

     * will work.

     */

    j = num_rules + 1;

    for (i = 1; i <= nacc; ++i)

      if (accset[i] < j)

        j = accset[i];

    dfaacc[newds].dfaacc_state = j;

    if (j <= num_rules)

      rule_useful[j] = true;

  }

  *newds_addr = newds;

  return 1;

}

/* symfollowset - follow the symbol transitions one step

 *

 * synopsis

 *    numstates = symfollowset( int ds[current_max_dfa_size], int dsize,

 *        int transsym, int nset[current_max_dfa_size] );

 */

static int symfollowset(int ds[], int dsize, int transsym, int nset[])

{

  int     ns, tsp, sym, i, j, lenccl, ch, numstates, ccllist;