context: /*
   * TokenNFA.cs
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public License
   * as published by the Free Software Foundation; either version 3
   * of the License, or (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   * Lesser General Public License for more details.
   *
   * You should have received a copy of the GNU Lesser General Public
   * License along with this library; if not, write to the Free
   * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
   * MA 02111-1307, USA.
   *
   * Copyright (c) 2009 Per Cederberg. All rights reserved.
   */
  
  using System;
  
  namespace PerCederberg.Grammatica.Runtime {
  
      /**
       * A non-deterministic finite state automaton (NFA) for matching
       * tokens. It supports both fixed strings and simple regular
       * expressions, but should perform similar to a DFA due to highly
       * optimized data structures and tuning. The memory footprint during
       * matching should be near zero, since no heap memory is allocated
       * unless the pre-allocated queues need to be enlarged. The NFA also
       * does not use recursion, but iterates in a loop instead.
       *
       * @author   Per Cederberg
       * @version  1.5
       * @since    1.5
       */
      internal class TokenNFA {
  
          /**
           * The initial state lookup table, indexed by the first ASCII
           * character. This array is used to for speed optimizing the
           * first step in the match, since the initial state would
           * otherwise have a long list of transitions to consider.
           */
          private NFAState[] initialChar = new NFAState[128];
  
          /**
           * The initial state. This state contains any transitions not
           * already stored in the initial text state array, i.e. non-ASCII
           * or complex transitions (such as regular expressions).
           */
          private NFAState initial = new NFAState();
  
          /**
           * The NFA state queue to use.
           */
          private NFAStateQueue queue = new NFAStateQueue();
  
          /**
           * Adds a string match to this automaton. New states and
           * transitions will be added to extend this automaton to support
           * the specified string.
           *
           * @param str            the string to match
           * @param ignoreCase     the case-insensitive match flag
           * @param value          the match value
           */
          public void AddTextMatch(string str, bool ignoreCase, TokenPattern value) {
              NFAState  state;
              char      ch = str[0];
  
              if (ch < 128 && !ignoreCase) {
                  state = initialChar[ch];
                  if (state == null) {
                      state = initialChar[ch] = new NFAState();
                  }
              } else {
                  state = initial.AddOut(ch, ignoreCase, null);
              }
              for (int i = 1; i < str.Length; i++) {
                  state = state.AddOut(str[i], ignoreCase, null);
              }
              state.value = value;
          }
  
          /**
           * Adds a regular expression match to this automaton. New states
           * and transitions will be added to extend this automaton to
           * support the specified string. Note that this method only
           * supports a subset of the full regular expression syntax, so
           * a more complete regular expression library must also be
           * provided.
           *
           * @param pattern        the regular expression string
           * @param ignoreCase     the case-insensitive match flag
           * @param value          the match value
           *
           * @throws RegExpException if the regular expression parsing
           *             failed
           */
          public void AddRegExpMatch(string pattern,
                                     bool ignoreCase,
                                     TokenPattern value) {
  
              TokenRegExpParser  parser = new TokenRegExpParser(pattern, ignoreCase);
              string             debug = "DFA regexp; " + parser.GetDebugInfo();
              bool               isAscii;
  
              isAscii = parser.start.IsAsciiOutgoing();
              for (int i = 0; isAscii && i < 128; i++) {
                  bool match = false;
                  for (int j = 0; j < parser.start.outgoing.Length; j++) {
                      if (parser.start.outgoing[j].Match((char) i)) {
                          if (match) {
                              isAscii = false;
                              break;
                          }
                          match = true;
                      }
                  }
                  if (match && initialChar[i] != null) {
                      isAscii = false;
                  }
              }
              if (parser.start.incoming.Length > 0) {
                  initial.AddOut(new NFAEpsilonTransition(parser.start));
                  debug += ", uses initial epsilon";
              } else if (isAscii && !ignoreCase) {
                  for (int i = 0; isAscii && i < 128; i++) {
                      for (int j = 0; j < parser.start.outgoing.Length; j++) {
                          if (parser.start.outgoing[j].Match((char) i)) {
                              initialChar[i] = parser.start.outgoing[j].state;
                          }
                      }
                  }
                  debug += ", uses ASCII lookup";
              } else {
                  parser.start.MergeInto(initial);
                  debug += ", uses initial state";
              }
              parser.end.value = value;
              value.DebugInfo = debug;
          }
  
          /**
           * Checks if this NFA matches the specified input text. The
           * matching will be performed from position zero (0) in the
           * buffer. This method will not read any characters from the
           * stream, just peek ahead.
           *
           * @param buffer         the input buffer to check
           * @param match          the token match to update
           *
           * @return the number of characters matched, or
           *         zero (0) if no match was found
           *
           * @throws IOException if an I/O error occurred
           */
          public int Match(ReaderBuffer buffer, TokenMatch match) {
              int       length = 0;
              int       pos = 1;
              int       peekChar;
              NFAState  state;
  
              // The first step of the match loop has been unrolled and
              // optimized for performance below.
              this.queue.Clear();
              peekChar = buffer.Peek(0);
              if (0 <= peekChar && peekChar < 128) {
                  state = this.initialChar[peekChar];
                  if (state != null) {
                      this.queue.AddLast(state);
                  }
              }
              if (peekChar >= 0) {
                  this.initial.MatchTransitions((char) peekChar, this.queue, true);
              }
              this.queue.MarkEnd();
              peekChar = buffer.Peek(1);
  
              // The remaining match loop processes all subsequent states
              while (!this.queue.Empty) {
                  if (this.queue.Marked) {
                      pos++;
                      peekChar = buffer.Peek(pos);
                      this.queue.MarkEnd();
                  }
                  state = this.queue.RemoveFirst();
                  if (state.value != null) {
                      match.Update(pos, state.value);
                  }
                  if (peekChar >= 0) {
                      state.MatchTransitions((char) peekChar, this.queue, false);
                  }
              }
              return length;
          }
      }
  
  
      /**
       * An NFA state. The NFA consists of a series of states, each
       * having zero or more transitions to other states.
       */
      internal class NFAState {
  
          /**
          * The optional state value (if it is a final state).
           */
          internal TokenPattern value = null;
  
          /**
          * The incoming transitions to this state.
          */
          internal NFATransition[] incoming = new NFATransition[0];
  
          /**
          * The outgoing transitions from this state.
          */
          internal NFATransition[] outgoing = new NFATransition[0];
  
          /**
          * The outgoing epsilon transitions flag.
          */
          internal bool epsilonOut = false;
  
          /**
           * Checks if this state has any incoming or outgoing
           * transitions.
           *
           * @return true if this state has transitions, or
           *         false otherwise
           */
          public bool HasTransitions() {
              return incoming.Length > 0 || outgoing.Length > 0;
          }
  
          /**
           * Checks if all outgoing transitions only match ASCII
           * characters.
           *
           * @return true if all transitions are ASCII-only, or
           *         false otherwise
           */
          public bool IsAsciiOutgoing() {
              for (int i = 0; i < outgoing.Length; i++) {
                  if (!outgoing[i].IsAscii()) {
                      return false;
                  }
              }
              return true;
          }
  
          /**
           * Adds a new incoming transition.
           *
           * @param trans          the transition to add
           */
          public void AddIn(NFATransition trans) {
              Array.Resize(ref incoming, incoming.Length + 1);
              incoming[incoming.Length - 1] = trans;
          }
  
          /**
           * Adds a new outgoing character transition. If the target
           * state specified was null and an identical transition
           * already exists, it will be reused and its target returned.
           *
           * @param ch             he character to match
           * @param ignoreCase     the case-insensitive flag
           * @param state          the target state, or null
           *
           * @return the transition target state
           */
          public NFAState AddOut(char ch, bool ignoreCase, NFAState state) {
              if (ignoreCase) {
                  if (state == null) {
                      state = new NFAState();
                  }
                  AddOut(new NFACharTransition(Char.ToLower(ch), state));
                  AddOut(new NFACharTransition(Char.ToUpper(ch), state));
                  return state;
              } else {
                  if (state == null) {
                      state = FindUniqueCharTransition(ch);
                      if (state != null) {
                          return state;
                      }
                      state = new NFAState();
                  }
                  return AddOut(new NFACharTransition(ch, state));
              }
          }
  
          /**
           * Adds a new outgoing transition.
           *
           * @param trans          the transition to add
           *
           * @return the transition target state
           */
          public NFAState AddOut(NFATransition trans) {
              Array.Resize(ref outgoing, outgoing.Length + 1);
              outgoing[outgoing.Length - 1] = trans;
              if (trans is NFAEpsilonTransition) {
                  epsilonOut = true;
              }
              return trans.state;
          }
  
          /**
           * Merges all the transitions in this state into another
           * state.
           *
           * @param state      the state to merge into
           */
          public void MergeInto(NFAState state) {
              for (int i = 0; i < incoming.Length; i++) {
                  state.AddIn(incoming[i]);
                  incoming[i].state = state;
              }
              incoming = null;
              for (int i = 0; i < outgoing.Length; i++) {
                  state.AddOut(outgoing[i]);
              }
              outgoing = null;
          }
  
          /**
           * Finds a unique character transition if one exists. The
           * transition must be the only matching single character
           * transition and no other transitions may reach the same
           * state.
           *
           * @param ch             the character to search for
           *
           * @return the unique transition state found, or
           *         null if not found
           */
          private NFAState FindUniqueCharTransition(char ch) {
              NFATransition  res = null;
              NFATransition  trans;
  
              for (int i = 0; i < outgoing.Length; i++) {
                  trans = outgoing[i];
                  if (trans.Match(ch) && trans is NFACharTransition) {
  
gt:                     if (res != null) {