/* nfa - NFA 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. */

/*  This file is part of flex. */

/*  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"


/* declare functions that have forward references */

int dupmachine PROTO ((int));
void mkxtion PROTO ((int, int));


/* add_accept - add an accepting state to a machine
 *
 * accepting_number becomes mach's accepting number.
 */

void    add_accept (mach, accepting_number)
     int     mach, accepting_number;
{
 /* Hang the accepting number off an epsilon state.  if it is associated
  * with a state that has a non-epsilon out-transition, then the state
  * will accept BEFORE it makes that transition, i.e., one character
  * too soon.
 */

 if (transchar[finalst[mach]] == SYM_EPSILON)
  accptnum[finalst[mach]] = accepting_number;

 else {
  int     astate = mkstate (SYM_EPSILON);

  accptnum[astate] = accepting_number;
  (void) link_machines (mach, astate);
 }
}


/* copysingl - make a given number of copies of a singleton machine
 *
 * synopsis
 *
 *   newsng = copysingl( singl, num );
 *
 *     newsng - a new singleton composed of num copies of singl
 *     singl  - a singleton machine
 *     num    - the number of copies of singl to be present in newsng
 */

int     copysingl (singl, num)
     int     singl, num;
{
 int     copy, i;

 copy = mkstate (SYM_EPSILON);

 for (i = 1; i <= num; ++i)
  copy = link_machines (copy, dupmachine (singl));

 return copy;
}


/* dumpnfa - debugging routine to write out an nfa */

void    dumpnfa (state1)
     int     state1;

{
 int     sym, tsp1, tsp2, anum, ns;

 fprintf (stderr,
   _
   ("\n\n********** beginning dump of nfa with start state %d\n"),
   state1);

 /* We probably should loop starting at firstst[state1] and going to
  * lastst[state1], but they're not maintained properly when we "or"
  * all of the rules together.  So we use our knowledge that the machine
  * starts at state 1 and ends at lastnfa.
 */

 /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
 for (ns = 1; ns <= lastnfa; ++ns) {
  fprintf (stderr, _("state # %4d\t"), ns);

  sym = transchar[ns];
  tsp1 = trans1[ns];
  tsp2 = trans2[ns];
  anum = accptnum[ns];

  fprintf (stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2);

  if (anum != NIL)
   fprintf (stderr, "  [%d]", anum);

  fprintf (stderr, "\n");
 }

 fprintf (stderr, _("********** end of dump\n"));
}


/* dupmachine - make a duplicate of a given machine
 *
 * synopsis
 *
 *   copy = dupmachine( mach );
 *
 *     copy - holds duplicate of mach
 *     mach - machine to be duplicated
 *
 * note that the copy of mach is NOT an exact duplicate; rather, all the
 * transition states values are adjusted so that the copy is self-contained,
 * as the original should have been.
 *
 * also note that the original MUST be contiguous, with its low and high
 * states accessible by the arrays firstst and lastst
 */

int     dupmachine (mach)
     int     mach;
{
 int     i, init, state_offset;
 int     state = 0;
 int     last = lastst[mach];

 for (i = firstst[mach]; i <= last; ++i) {
  state = mkstate (transchar[i]);

  if (trans1[i] != NO_TRANSITION) {
   mkxtion (finalst[state], trans1[i] + state - i);

   if (transchar[i] == SYM_EPSILON &&
       trans2[i] != NO_TRANSITION)
     mkxtion (finalst[state],
       trans2[i] + state - i);
  }

  accptnum[state] = accptnum[i];
 }

 if (state == 0)
  flexfatal (_("empty machine in dupmachine()"));

 state_offset = state - i + 1;

 init = mach + state_offset;
 firstst[init] = firstst[mach] + state_offset;
 finalst[init] = finalst[mach] + state_offset;
 lastst[init] = lastst[mach] + state_offset;

 return init;
}


/* finish_rule - finish up the processing for a rule
 *
 * An accepting number is added to the given machine.  If variable_trail_rule
 * is true then the rule has trailing context and both the head and trail
 * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
 * the machine recognizes a pattern with trailing context and headcnt is
 * the number of characters in the matched part of the pattern, or zero
 * if the matched part has variable length.  trailcnt is the number of
 * trailing context characters in the pattern, or zero if the trailing
 * context has variable length.
 */

void    finish_rule (mach, variable_trail_rule, headcnt, trailcnt,
       pcont_act)
     int     mach, variable_trail_rule, headcnt, trailcnt, pcont_act;
{
 char    action_text[MAXLINE];

 add_accept (mach, num_rules);

 /* We did this in new_rule(), but it often gets the wrong
  * number because we do it before we start parsing the current rule.
 */
 rule_linenum[num_rules] = linenum;

 /* If this is a continued action, then the line-number has already
  * been updated, giving us the wrong number.
 */
 if (continued_action)
  --rule_linenum[num_rules];


 /* If the previous rule was continued action, then we inherit the
  * previous newline flag, possibly overriding the current one.
 */
 if (pcont_act && rule_has_nl[num_rules - 1])
  rule_has_nl[num_rules] = true;

 snprintf (action_text, sizeof(action_text), "case %d:\n", num_rules);
 add_action (action_text);
 if (rule_has_nl[num_rules]) {
  snprintf (action_text, sizeof(action_text), "/* rule %d can match eol */\n",
    num_rules);
  add_action (action_text);
 }


 if (variable_trail_rule) {
  rule_type[num_rules] = RULE_VARIABLE;

  if (performance_report > 0)
   fprintf (stderr,
     _
     ("Variable trailing context rule at line %d\n"),
     rule_linenum[num_rules]);

  variable_trailing_context_rules = true;
 }

 else {
  rule_type[num_rules] = RULE_NORMAL;

  if (headcnt > 0 || trailcnt > 0) {
   /* Do trailing context magic to not match the trailing
    * characters.
 */
   char   *scanner_cp = "YY_G(yy_c_buf_p) = yy_cp";
   char   *scanner_bp = "yy_bp";

   add_action
    ("*yy_cp = YY_G(yy_hold_char); /* undo effects of setting up yytext */\n");

   if (headcnt > 0) {
    if (rule_has_nl[num_rules]) {
     snprintf (action_text, sizeof(action_text),
      "YY_LINENO_REWIND_TO(%s + %d);\n", scanner_bp, headcnt);
     add_action (action_text);
    }
    snprintf (action_text, sizeof(action_text), "%s = %s + %d;\n",
      scanner_cp, scanner_bp, headcnt);
    add_action (action_text);
   }

   else {
    if (rule_has_nl[num_rules]) {
     snprintf (action_text, sizeof(action_text),
       "YY_LINENO_REWIND_TO(yy_cp - %d);\n", trailcnt);
     add_action (action_text);
    }

    snprintf (action_text, sizeof(action_text), "%s -= %d;\n",
      scanner_cp, trailcnt);
    add_action (action_text);
   }

   add_action
    ("YY_DO_BEFORE_ACTION; /* set up yytext again */\n");
  }
 }

 /* Okay, in the action code at this point yytext and yyleng have
  * their proper final values for this rule, so here's the point
  * to do any user action.  But don't do it for continued actions,
  * as that'll result in multiple YY_RULE_SETUP's.
 */
 if (!continued_action)
  add_action ("YY_RULE_SETUP\n");

 line_directive_out ((FILE *) 0, 1);
}


/* link_machines - connect two machines together
 *
 * synopsis
 *
 *   new = link_machines( first, last );
 *
 *     new    - a machine constructed by connecting first to last
 *     first  - the machine whose successor is to be last
 *     last   - the machine whose predecessor is to be first
 *
 * note: this routine concatenates the machine first with the machine
 *  last to produce a machine new which will pattern-match first first
 *  and then last, and will fail if either of the sub-patterns fails.
 *  FIRST is set to new by the operation.  last is unmolested.
 */

int     link_machines (first, last)
     int     first, last;
{
 if (first == NIL)
  return last;

 else if (last == NIL)
  return first;

 else {
  mkxtion (finalst[first], last);
  finalst[first] = finalst[last];
  lastst[first] = MAX (lastst[first], lastst[last]);
  firstst[first] = MIN (firstst[first], firstst[last]);

  return first;
 }
}


/* mark_beginning_as_normal - mark each "beginning" state in a machine
 *                            as being a "normal" (i.e., not trailing context-
 *                            associated) states
 *
 * The "beginning" states are the epsilon closure of the first state
 */

void    mark_beginning_as_normal (mach)
     int mach;
{
 switch (state_type[mach]) {
 case STATE_NORMAL:
  /* Oh, we've already visited here. */
  return;

 case STATE_TRAILING_CONTEXT:
  state_type[mach] = STATE_NORMAL;

  if (transchar[mach] == SYM_EPSILON) {
   if (trans1[mach] != NO_TRANSITION)
    mark_beginning_as_normal (trans1[mach]);

   if (trans2[mach] != NO_TRANSITION)
    mark_beginning_as_normal (trans2[mach]);
  }
  break;

 default:
  flexerror (_
      ("bad state type in mark_beginning_as_normal()"));
  break;
 }
}


/* mkbranch - make a machine that branches to two machines
 *
 * synopsis
 *
 *   branch = mkbranch( first, second );
 *
 *     branch - a machine which matches either first's pattern or second's
 *     first, second - machines whose patterns are to be or'ed (the | operator)
 *
 * Note that first and second are NEITHER destroyed by the operation.  Also,
 * the resulting machine CANNOT be used with any other "mk" operation except
 * more mkbranch's.  Compare with mkor()
 */

int     mkbranch (first, second)
     int     first, second;
{
 int     eps;

 if (first == NO_TRANSITION)
  return second;

 else if (second == NO_TRANSITION)
  return first;

 eps = mkstate (SYM_EPSILON);

 mkxtion (eps, first);
 mkxtion (eps, second);

 return eps;
}


/* mkclos - convert a machine into a closure
 *
 * synopsis
 *   new = mkclos( state );
 *
 * new - a new state which matches the closure of "state"
 */

int     mkclos (state)
     int     state;
{
 return mkopt (mkposcl (state));
}


/* mkopt - make a machine optional
 *
 * synopsis
 *
 *   new = mkopt( mach );
 *
 *     new  - a machine which optionally matches whatever mach matched
 *     mach - the machine to make optional
 *
 * notes:
 *     1. mach must be the last machine created
 *     2. mach is destroyed by the call
 */

int     mkopt (mach)
     int     mach;
{
 int     eps;

 if (!SUPER_FREE_EPSILON (finalst[mach])) {
  eps = mkstate (SYM_EPSILON);
  mach = link_machines (mach, eps);
 }

 /* Can't skimp on the following if FREE_EPSILON(mach) is true because
  * some state interior to "mach" might point back to the beginning
  * for a closure.
 */
 eps = mkstate (SYM_EPSILON);
 mach = link_machines (eps, mach);

 mkxtion (mach, finalst[mach]);

 return mach;
}


/* mkor - make a machine that matches either one of two machines
 *
 * synopsis
 *
 *   new = mkor( first, second );
 *
 *     new - a machine which matches either first's pattern or second's
 *     first, second - machines whose patterns are to be or'ed (the | operator)
 *
 * note that first and second are both destroyed by the operation
 * the code is rather convoluted because an attempt is made to minimize
 * the number of epsilon states needed
 */

int     mkor (first, second)
     int     first, second;
{
 int     eps, orend;

 if (first == NIL)
  return second;

 else if (second == NIL)
  return first;

 else {
  /* See comment in mkopt() about why we can't use the first
   * state of "first" or "second" if they satisfy "FREE_EPSILON".
 */
  eps = mkstate (SYM_EPSILON);

  first = link_machines (eps, first);

  mkxtion (first, second);

  if (SUPER_FREE_EPSILON (finalst[first]) &&
      accptnum[finalst[first]] == NIL) {
   orend = finalst[first];
   mkxtion (finalst[second], orend);
  }

  else if (SUPER_FREE_EPSILON (finalst[second]) &&
    accptnum[finalst[second]] == NIL) {
   orend = finalst[second];
   mkxtion (finalst[first], orend);
  }

  else {
   eps = mkstate (SYM_EPSILON);

   first = link_machines (first, eps);
   orend = finalst[first];

   mkxtion (finalst[second], orend);
  }
 }

 finalst[first] = orend;
 return first;
}


/* mkposcl - convert a machine into a positive closure
 *
 * synopsis
 *   new = mkposcl( state );
 *
 *    new - a machine matching the positive closure of "state"
 */

int     mkposcl (state)
     int     state;
{
 int     eps;

 if (SUPER_FREE_EPSILON (finalst[state])) {
  mkxtion (finalst[state], state);
  return state;
 }

 else {
  eps = mkstate (SYM_EPSILON);
  mkxtion (eps, state);
  return link_machines (state, eps);
 }
}


/* mkrep - make a replicated machine
 *
 * synopsis
 *   new = mkrep( mach, lb, ub );
 *
 *    new - a machine that matches whatever "mach" matched from "lb"
 *          number of times to "ub" number of times
 *
 * note
 *   if "ub" is INFINITE_REPEAT then "new" matches "lb" or more occurrences of "mach"
 */

int     mkrep (mach, lb, ub)
     int     mach, lb, ub;
{
 int     base_mach, tail, copy, i;

 base_mach = copysingl (mach, lb - 1);

 if (ub == INFINITE_REPEAT) {
  copy = dupmachine (mach);
  mach = link_machines (mach,
          link_machines (base_mach,
           mkclos (copy)));
 }

 else {
  tail = mkstate (SYM_EPSILON);

  for (i = lb; i < ub; ++i) {
   copy = dupmachine (mach);
   tail = mkopt (link_machines (copy, tail));
  }

  mach =
   link_machines (mach,
           link_machines (base_mach, tail));
 }

 return mach;
}


/* mkstate - create a state with a transition on a given symbol
 *
 * synopsis
 *
 *   state = mkstate( sym );
 *
 *     state - a new state matching sym
 *     sym   - the symbol the new state is to have an out-transition on
 *
 * note that this routine makes new states in ascending order through the
 * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
 * relies on machines being made in ascending order and that they are
 * CONTIGUOUS.  Change it and you will have to rewrite DUPMACHINE (kludge
 * that it admittedly is)
 */

int     mkstate (sym)
     int     sym;
{
 if (++lastnfa >= current_mns) {
  if ((current_mns += MNS_INCREMENT) >= maximum_mns)
   lerr(_
    ("input rules are too complicated (>= %d NFA states)"),
current_mns);

  ++num_reallocs;

  firstst = reallocate_integer_array (firstst, current_mns);
  lastst = reallocate_integer_array (lastst, current_mns);
  finalst = reallocate_integer_array (finalst, current_mns);
  transchar =
   reallocate_integer_array (transchar, current_mns);
  trans1 = reallocate_integer_array (trans1, current_mns);
  trans2 = reallocate_integer_array (trans2, current_mns);
  accptnum =
   reallocate_integer_array (accptnum, current_mns);
  assoc_rule =
   reallocate_integer_array (assoc_rule, current_mns);
  state_type =
   reallocate_integer_array (state_type, current_mns);
 }

 firstst[lastnfa] = lastnfa;
 finalst[lastnfa] = lastnfa;
 lastst[lastnfa] = lastnfa;
 transchar[lastnfa] = sym;
 trans1[lastnfa] = NO_TRANSITION;
 trans2[lastnfa] = NO_TRANSITION;
 accptnum[lastnfa] = NIL;
 assoc_rule[lastnfa] = num_rules;
 state_type[lastnfa] = current_state_type;

 /* Fix up equivalence classes base on this transition.  Note that any
  * character which has its own transition gets its own equivalence
  * class.  Thus only characters which are only in character classes
  * have a chance at being in the same equivalence class.  E.g. "a|b"
  * puts 'a' and 'b' into two different equivalence classes.  "[ab]"
  * puts them in the same equivalence class (barring other differences
  * elsewhere in the input).
 */

 if (sym < 0) {
  /* We don't have to update the equivalence classes since
   * that was already done when the ccl was created for the
   * first time.
 */
 }

 else if (sym == SYM_EPSILON)
  ++numeps;

 else {
  check_char (sym);

  if (useecs)
   /* Map NUL's to csize. */
   mkechar (sym ? sym : csize, nextecm, ecgroup);
 }

 return lastnfa;
}


/* mkxtion - make a transition from one state to another
 *
 * synopsis
 *
 *   mkxtion( statefrom, stateto );
 *
 *     statefrom - the state from which the transition is to be made
 *     stateto   - the state to which the transition is to be made
 */

void    mkxtion (statefrom, stateto)
     int     statefrom, stateto;
{
 if (trans1[statefrom] == NO_TRANSITION)
  trans1[statefrom] = stateto;

 else if ((transchar[statefrom] != SYM_EPSILON) ||
   (trans2[statefrom] != NO_TRANSITION))
  flexfatal (_("found too many transitions in mkxtion()"));

 else {   /* second out-transition for an epsilon state */
  ++eps2;
  trans2[statefrom] = stateto;
 }
}

/* new_rule - initialize for a new rule */

void    new_rule ()
{
 if (++num_rules >= current_max_rules) {
  ++num_reallocs;
  current_max_rules += MAX_RULES_INCREMENT;
  rule_type = reallocate_integer_array (rule_type,
            current_max_rules);
  rule_linenum = reallocate_integer_array (rule_linenum,
        current_max_rules);
  rule_useful = reallocate_integer_array (rule_useful,
       current_max_rules);
  rule_has_nl = reallocate_bool_array (rule_has_nl,
           current_max_rules);
 }

 if (num_rules > MAX_RULE)
  lerr (_("too many rules (> %d)!"), MAX_RULE);

 rule_linenum[num_rules] = linenum;
 rule_useful[num_rules] = false;
 rule_has_nl[num_rules] = false;
}