nfa.C

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#include <stack>
#include <algorithm>

#include <archon/util/text.H>
#include <archon/util/dfa.H>
#include <archon/util/regex.H>

#include <archon/util/nfa.H>

using namespace std;

namespace Archon
{
  namespace Utilities
  {
    bool NFA::closedAdd(int state, set<int> &stateSet) const
    {
      if(!stateSet.insert(state).second) return false;
      stack<int> uncheckedStates;
      uncheckedStates.push(state);
      while(!uncheckedStates.empty())
      {
        const State &s = states[uncheckedStates.top()];
        uncheckedStates.pop();
        for(unsigned i=0; i<s.epsilonEdges.size(); ++i)
        {
          const int e = s.epsilonEdges[i];
          if(stateSet.insert(e).second) uncheckedStates.push(e);
        }
      }
      return true;
    }

    void NFA::updateDfaEdgeRange(Edge e, map<unsigned, pair<unsigned, set<int> > > &dEdges) const
    {
      bool hasRawStateSet = false;
      set<int> rawStateSet;

      map<unsigned, pair<unsigned, set<int> > >::iterator i = dEdges.lower_bound(e.begin);

      /*
       * Conditions:
       *
       * - 'i' references the interval that starts where the incoming
       * interval starts or if no such interval exists 'i' references
       * the first interval starting after the start of the incoming
       * interval or if no such interval exists 'i' references a virtual
       * interval starting at infinity.
       *
       * - The incoming interval is not empty.
       */

      // Detect an overlap with the existing interval (if it exists)
      // preceeding the interval referenced by 'i'.
      if(i != dEdges.begin())
      {
        // We may now assume that e.begin > 0

        map<unsigned, pair<unsigned, set<int> > >::iterator j = i;
        --j;
        if(e.begin <= j->second.first)
        {
          // The new interval has an overlap with the interval starting
          // before it

          // Split the existing interval into two pieces such that the
          // second piece starts where the incoming interval starts.
          dEdges.insert(i, make_pair(e.begin, j->second));
          j->second.first = e.begin-1;

          // Let 'i' refer to the second of the two pieces resulting
          // from the split
          --i;
        }
      }

      // General loop
      for(;;)
      {
        /*
         * Conditions:
         *
         * - 'i' references an existing interval or the virtual interval
         * succeeding the last real interval. The virtual interval
         * conceptually starts at positive infinity.
         *
         * - The remaining part of the incoming interval does not start
         * after the start of the existing real/virtual interval
         * referenced by 'i'.
         *
         * - The remaining part of the incoming interval does not
         * overlap with the previous existing real interval 'i-1' if
         * such an interval exists.
         *
         * - The remaining part of the incoming interval is not empty.
         */

        /*
         * Does the remaining part of the incloming interval start
         * before the existing interval referenced by 'i'. In this case
         * there is an uncovered range before the interval referenced by
         * 'i'. In the following we refer to the uncovered range as the
         * gap.
         */
        if(i == dEdges.end() || e.begin < i->first)
        {
          /*
           * If the incoming interval is adjacent to the previous
           * interval 'i-1' and the epsilon closure of the incoming
           * state is equal to the state set of the previous interval
           * just expand the previous interval.
           */
          if(!hasRawStateSet) closedAdd(e.targetState, rawStateSet);
          bool expanded = false;
          const int gapEnd = i == dEdges.end() ? e.end : min(i->first-1, e.end);
          if(i != dEdges.begin())
          {
            map<unsigned, pair<unsigned, set<int> > >::iterator j = i;
            --j;
            // We may now assume that e.begin > j->second.fist
            if(e.begin-1 == j->second.first &&
               rawStateSet == j->second.second)
            {
              j->second.first = gapEnd;
              expanded = true;
            }
          }

          if(!expanded)
            dEdges.insert(i, make_pair(e.begin, make_pair(gapEnd, rawStateSet)));

          // We may now assume that 'i-1' references a real interval

          /*
           * Stop if the remaining part of the incoming interval ends in
           * the gap without being adjacent to the next interval (the
           * interval referenced by 'i')?
           */
          if(i == dEdges.end() || e.end < i->first-1) break;

          // We may now assume that 'i' references a real interval

          /*
           * Merge intervals if the remaining part of the incoming
           * interval is adjacent to the next interval (the interval
           * referenced by 'i') and they have equal state sets?
           *
           * Regardless of state set equality if the remaining part of
           * the incoming interval is adjacent to the next interval
           * then stop.
           */
          map<unsigned, pair<unsigned, set<int> > >::iterator j = i;
          --j;
          if(e.end == i->first-1)
          {
            if(j->second.second == i->second.second)
            {
              j->second.first = i->second.first;
              dEdges.erase(i);
            }
            break;
          }

          /*
           * Shorten the incoming interval such that is starts where the
           * next existing interval starts (the interval referenced by
           * 'i').
           */
          e.begin = i->first;
        }

        ++i;

        /*
         * Conditions:
         *
         * - 'i' references an existing interval or the virtual interval
         * succeeding the last real interval. The virtual interval
         * conceptually starts at positive infinity.
         *
         * - The previous real interval exists.
         *
         * - The remaining part of the incoming interval starts where
         * the previous existing interval does.
         *
         * - The remaining part of the incoming interval is not empty.
         */

        // Handle overlap with next interval
        map<unsigned, pair<unsigned, set<int> > >::iterator j = i;
        --j;

        bool done = false;
        set<int> stateSet = j->second.second;
        if(closedAdd(e.targetState, stateSet))
        {
          if(e.end < j->second.first)
          {
            dEdges.insert(i, make_pair(e.end+1, j->second));
            --i;
            j->second.first = e.end;
            done = true;
          }
          else
          {
            if(e.end == j->second.first) done = true;
            else e.begin = j->second.first+1;
          }
          j->second.second = stateSet;
        }
        else
        {
          if(e.end <= j->second.first) done = true;
          else e.begin = j->second.first+1;
        }

        // Should we merge 'i-1' and 'i-2'?
        if(j!=dEdges.begin())
        {
          map<unsigned, pair<unsigned, set<int> > >::iterator k = j;
          --k;

          if(k->second.first == j->first-1 &&
             k->second.second == j->second.second)
          {
            k->second.first = j->second.first;
            dEdges.erase(j);
          }
        }

        if(done) break;
      }
    }

    int NFA::chooseFinalValue(const set<int> &stateSet) const
    {
      int rule = -1;
      for(set<int>::iterator i=stateSet.begin(); i!=stateSet.end(); ++i)
      {
        const int r = states[*i].finalValue;
        if(r > rule) rule = r;
      }
      return rule;
    }

    template<typename T>
    void set_include(const set<T> &right, set<T> &left)
    {
      typename set<T>::iterator i=left.begin();
      typename set<T>::const_iterator j=right.begin();
      while(j!=right.end())
      {
        if(i == left.end() || *j < *i) left.insert(i, *j++);
        else if(*j == *i) ++j;
        else ++i;
      }
    }

    void NFA::constructDFA(DFA *dfa, vector<set<int> > *stateSets, DFA::AnchorInfo *anchorInfo) const
    {
      if(!states.size()) return; // Handle the special null NFA

      // Maps NFA state sets to DFA state indices.
      map<set<int>, int> dStates;

      stack<pair<set<int>, int> > uncheckedDStates;

      // Add a DFA start state for each NFA start state.
      for(unsigned i=0; i<startStates.size(); ++i)
      {
        set<int> stateSet;
        closedAdd(startStates[i], stateSet);
        pair<map<set<int>, int>::iterator ,bool> r =
          dStates.insert(make_pair(stateSet, 0));
        if(r.second)
        {
          r.first->second = dfa->addStartState(chooseFinalValue(stateSet));
          uncheckedDStates.push(*r.first);
        }
      }

      while(!uncheckedDStates.empty())
      {
        const pair<set<int>, int> &dState = uncheckedDStates.top();
        map<unsigned, pair<unsigned, set<int> > > dEdges;
        for(set<int>::iterator i=dState.first.begin(); i!=dState.first.end(); ++i)
        {
          const State &s = states[*i];
          for(unsigned i=0; i<s.symbolEdges.size(); ++i)
            updateDfaEdgeRange(s.symbolEdges[i], dEdges);
        }

        // Anchor regret
        if(anchorInfo) do
        {
          // Check if there are any anchor symbols among the edges
          // leavinge the current state set.
          map<unsigned, pair<unsigned, set<int> > >::iterator i =
            dEdges.lower_bound(anchorInfo->start);
          if(i != dEdges.begin() && (i == dEdges.end() || i->first != anchorInfo->start)) --i;
          for(unsigned j=0; j<anchorInfo->numberOf; ++j)
          {
            unsigned anchor = anchorInfo->start + j;
            while(i != dEdges.end() && i->second.first < anchor) ++i;
            if(i == dEdges.end()) break;
            if(i->first <= anchor)
            {
              for(set<int>::iterator k=dState.first.begin(); k!=dState.first.end(); ++k)
                updateDfaEdgeRange(Edge(anchor, anchor, *k), dEdges);
            }
          }
        }
        while(false);

        const int currentDFAState = dState.second;
        uncheckedDStates.pop();
        for(map<unsigned, pair<unsigned, set<int> > >::iterator i=dEdges.begin(); i!=dEdges.end(); ++i)
        {
          pair<map<set<int>, int>::iterator ,bool> r =
            dStates.insert(make_pair(i->second.second, 0));
          if(r.second)
          {
            r.first->second = dfa->addState(chooseFinalValue(r.first->first));
            uncheckedDStates.push(*r.first);
          }
          dfa->addEdgeRange(i->first, i->second.first, currentDFAState, r.first->second);
        }
      }

      if(stateSets)
      {
        stateSets->clear();
        stateSets->resize(dfa->states.size());
        for(map<set<int>, int>::iterator i=dStates.begin(); i!=dStates.end(); ++i)
          (*stateSets)[i->second] = i->first;
      }
    }

    NFA::NFA(basic_string<unsigned> s, int finalValue)
    {
      states.resize(s.size()+1);
      for(unsigned i=0; i<s.size(); ++i)
        states[i].symbolEdges.push_back(Edge(s[i], s[i], i+1));
      states.back().finalValue = finalValue;
      startStates.push_back(0);
    }

    NFA::NFA(unsigned begin, unsigned end, int finalValue)
    {
      if(begin > end) ARCHON_THROW1(ArgumentException, "Illegal range");
      states.resize(2);
      states.front().symbolEdges.push_back(Edge(begin, end, 1));
      states.back().finalValue = finalValue;
      startStates.push_back(0);
    }

    NFA::NFA(const vector<pair<unsigned, unsigned> > &ranges, int finalValue)
    {
      states.resize(2);
      for(unsigned i=0; i<ranges.size(); ++i)
      {
        const pair<unsigned, unsigned> &r = ranges[i];
        if(r.first > r.second) ARCHON_THROW1(ArgumentException, "Illegal range");
        states.front().symbolEdges.push_back(Edge(r.first, r.second, 1));
      }
      states.back().finalValue = finalValue;
      startStates.push_back(0);
    }

    void NFA::altern(const NFA &a)
    {
      if(!states.size()) // Handle special null NFA
      {
        *this = a;
        return;
      }
      if(!a.states.size()) return; // Handle special null NFA
      if(startStates.size()!=1 || a.startStates.size()!=1)
        ARCHON_THROW1(ArgumentException, "Wrong number of start states");

      const unsigned n = states.size();
      const unsigned m = n + a.states.size();
      states.resize(m + 1);
      for(unsigned i=0; i<a.states.size(); ++i)
      {
        State &s = states[n+i] = a.states[i];
        for(unsigned j=0; j<s.symbolEdges.size(); ++j)
          s.symbolEdges[j].targetState += n;
        for(unsigned j=0; j<s.epsilonEdges.size(); ++j)
          s.epsilonEdges[j] += n;
      }
      {
        State &s = states[m];
        s.epsilonEdges.push_back(startStates.front());
        s.epsilonEdges.push_back(n+a.startStates.front());
      }
      startStates.front() = m;
    }

    void NFA::concat(const NFA &a)
    {
      if(!states.size()) // Handle special null NFA
      {
        *this = a;
        return;
      }
      if(!a.states.size()) return; // Handle special null NFA
      if(a.startStates.size()!=1)
        ARCHON_THROW1(ArgumentException, "Wrong number of start states");

      const unsigned n = states.size();
      states.resize(n + a.states.size());
      const unsigned m = a.startStates.front()+n;
      for(unsigned i=0; i<n; ++i)
      {
        State &s = states[i];
        if(s.finalValue < 0) continue;
        s.finalValue = -1;
        s.epsilonEdges.push_back(m);
      }
      for(unsigned i=0; i<a.states.size(); ++i)
      {
        State &s = states[n+i] = a.states[i];
        for(unsigned j=0; j<s.symbolEdges.size(); ++j)
          s.symbolEdges[j].targetState += n;
        for(unsigned j=0; j<s.epsilonEdges.size(); ++j)
          s.epsilonEdges[j] += n;
      }
    }

    void NFA::repeat(bool includeZero, int finalValue)
    {
      if(!states.size()) return; // Handle special null NFA
      if(startStates.size()!=1)
        ARCHON_THROW1(ArgumentException, "Wrong number of start states");

      if(includeZero)
      {
        const unsigned n = states.size();
        states.resize(n+1);
        for(unsigned i=0; i<n; ++i)
        {
          State &s = states[i];
          if(s.finalValue < 0) continue;
          s.finalValue = -1;
          s.epsilonEdges.push_back(n);
        }
        {
          State &s = states[n];
          s.epsilonEdges.push_back(startStates.front());
          s.finalValue = finalValue;
        }
        startStates.front() = n;
        return;
      }

      // One or more times:
      for(unsigned i=0; i<states.size(); ++i)
      {
        State &s = states[i];
        if(s.finalValue < 0) continue;
        s.epsilonEdges.push_back(startStates.front());
      }
    }

    void NFA::setFinalValue(int finalValue)
    {
      for(unsigned i=0; i<states.size(); ++i)
      {
        State &s = states[i];
        if(s.finalValue < 0) continue;
        s.finalValue = finalValue;
      }
    }

    NFA::NFA(const DFA &a)
    {
      a.makeNFA(this);
    }

    NFA::NFA(const Regex &r, int finalValue)
    {
      r.makeNfa(*this);
      setFinalValue(finalValue);
    }

    int NFA::addStartState(int finalValue)
    {
      startStates.push_back(states.size());
      return addState(finalValue);
    }

    int NFA::addState(int finalValue)
    {
      states.push_back(State(finalValue));
      return states.size()-1;
    }

    void NFA::addEdge(int originalState, int targetState)
    {
      states[originalState].epsilonEdges.push_back(targetState);
    }

    void NFA::addEdge(int originalState, int targetState,
                      unsigned begin, unsigned end)
    {
      if(begin > end) ARCHON_THROW1(ArgumentException, "Illegal range");
      states[originalState].symbolEdges.push_back(Edge(begin, end, targetState));
    }

    struct DefaultPrinter: NFA::Printer
    {
      string printSymbol(unsigned s) const
      {
        return Text::toString(s);
      }
    };

    const NFA::Printer &NFA::getDefaultPrinter()
    {
      static DefaultPrinter defaultPrinter;
      return defaultPrinter;
    }

    string NFA::print(const Printer &printer, int width) const
    {
      vector<double> columnWidthFractions;
      columnWidthFractions.push_back(0.1);
      columnWidthFractions.push_back(0.1);
      columnWidthFractions.push_back(0.8);
      Text::Table<string> table(states.size()+1, columnWidthFractions);
      table(0, 0) = "State";
      table(0, 1) = "Final";
      table(0, 2) = "NFA-transitions";
      for(unsigned i=0; i<states.size(); ++i)
      {
        const State &s = states[i];
        table(i+1, 0) = Text::toString(i);
        if(find(startStates.begin(), startStates.end(), static_cast<int>(i))!=startStates.end())
          table(i+1, 0) += "*";
        if(s.finalValue >= 0) table(i+1, 1) = Text::toString(s.finalValue);
        for(unsigned j=0; j<s.symbolEdges.size(); ++j)
        {
          if(table(i+1, 2).size()) table(i+1, 2) += ", ";
          const Edge &e = s.symbolEdges[j];
          table(i+1, 2) += "'" + printer.printSymbol(e.begin) + "'";
          if(e.begin < e.end)
            table(i+1, 2) += "-'" + printer.printSymbol(e.end) + "'";
          table(i+1, 2) += " -> " + Text::toString(e.targetState);
        }

        for(unsigned j=0; j<s.epsilonEdges.size(); ++j)
        {
          if(table(i+1, 2).size()) table(i+1, 2) += ", ";
          table(i+1, 2) += "-> " + Text::toString(s.epsilonEdges[j]);
        }
      }

      return Text::format(table, width, 2, true);      
    }
  }
}

---