TagStates.cc

Go to the documentation of this file.

#include <cstdlib>
#include<iostream>
#include<fstream>
#include<regex>
#include<unordered_map>
#include<boost/program_options.hpp>

#include<diades/automata/experimental/AutFile.hh>
#include<diades/automata/experimental/DdAutFile.hh>
#include"../AutomataInterface.hh"
#include "diades/automata/experimental/DdAutFileDescriptor.hh"
#include <diades/automata/experimental/Io.hh>
using namespace std;
using namespace Diades::Automata::Experimental;
using namespace Diades::Utils;
using namespace Diades::CmdInterface;

namespace Poptions = boost::program_options;



const string program("dd-tagstates");
const string briefcomment(": this program tags some states based on regular expressions  (output file or standard output).");
const string detailedcomment=R"( dd-tagstates tags a set of states to be initial or final based 
on a regular expression. Regular expression are defined as proposed in 
http://www.cplusplus.com/reference/regex/ECMAScript/

Example 1: set to be acceptor any states such that its label contains 
the substring 'o.p=ko'

dd-tagstates file.ddaut -r 'final:.*o\.p=ko.*'

Example 2: set to be non-acceptor any states such that its label contains the substring 'o.p=ok'

dd-tagstates file.ddaut -r 'nofinal:.*o\.p=ok.*'

Example 3: set to be initial any states such that its label contains the substring 'init'

dd-tagstates file.ddaut -r 'initial:.*init.*'

Example 4: set to be not initial any states such that its label is 's1' or 's2' or 's3'

dd-tagstates file.ddaut -r 'noinitial:s[1-3]'

Example 5: Applying Example 5: applying Examples 1-4 in one go. Tagging works 
from left to right, we tag first  'final:.*o\.p=ko.*' then -r 'nofinal:.*o\.p=ok.*' 
so the order matters.

dd-tagstates file.ddaut -r 'final:.*o\.p=ko.*' -r 'nofinal:.*o\.p=ok.*' -r 'initial:.*init.*' -r 'noinitial:s[1-3]'


Example 6: tag a set of states S as acceptors and tag other states so that any prefix of a word accepted by a state of S
is also an accepted word.

dd-tagstates file.ddaut -r 'prefix-closed-final:.*o\.p=ko.*' 

Example 7: swap the tags of the  set of states S: swap-final if the state is final swap to non-final, if the state is 
final then swap to final.  swap-initial if the state is initial swap to non-initial, if the state is non-initial then swap 
to initial. 

dd-tagstates file.ddaut -r 'swap-final:.*o\.p=ko.*' 'swap-initial:.*o\.p=ok.*'
)";

/*
 * File suffixes
 */
FileSuffixes suffixes({"ddaut"});

void
initialiseOptions(int argc, char * argv[],
                  Poptions::options_description & desc,
                  Poptions::variables_map & vm)
{
  desc.add_options()
    ("help,h", "produce help message")
    ("file,f", Poptions::value< string >(), "file (.ddaut format)")
    ("regexp,r", Poptions::value< vector<string> >(),
     R"(A set of expressions inside a set of quotes: 'tag:regexp'
tag can be final, initial, nofinal, noinitial. 
Regular expression regexp are on the name of 
the states, for details see
http://www.cplusplus.com/reference/regex/ECMAScript/)
dd-tagstates applies the tags in the order written in
the command line.)")
    ("output,o", Poptions::value< string >(), "outfile name (.ddaut format)")
    ;
  Poptions::positional_options_description p;
  // 1 that The command line can accept 1 file name as positional option
  p.add("file", 1);
  Poptions::store(Poptions::command_line_parser(argc, argv).options(desc).positional(p).run(), vm);
  Poptions::notify(vm);
}


using Diades::Automata::Experimental::DdAutFsm;
using Diades::Automata::Experimental::DdAutFA;
using Diades::Automata::Experimental::DdAutEventManager;
using Diades::Automata::Experimental::DdAutStateManager;

enum Tag { final, nofinal, initial, noinitial, prefixclosedfinal, swapfinal, swapinitial };


const std::unordered_map<std::string,Tag> tagOf = {
                                                   {"final",final},
                                                   {"nofinal",nofinal},
                                                   {"initial",initial},
                                                   {"noinitial",noinitial},
                                                   {"prefix-closed-final",prefixclosedfinal},
                                                   {"swap-initial",swapinitial},
                                                   {"swap-final",swapfinal}
};

void applyTag(DdAutFA & fa, DdAutFA::State state, Tag  tag)
{
  switch(tag)
    {
    case final: fa.setAcceptingState(state); break;
    case nofinal: fa.unsetAcceptingState(state); break;
    case initial: fa.setInitial(state); break;
    case noinitial: fa.unsetInitial(state); break;
    case prefixclosedfinal: fa.setAcceptingState(state); break;
    case swapfinal: fa.swapAcceptingState(state); break;
    case swapinitial: fa.swapInitialState(state); break;
    }
}


void getReachable(DdAutFA & fa,CstStMap<char> & mapping,
                  std::regex & reg,
                  DdAutStateManager & sManager,
                  std::list<DdAutFA::State> & acceptors)
{
  std::list<DdAutFA::State> visitingStates;
  std::for_each(fa.initialStateBegin(),fa.initialStateEnd(),
                [&](DdAutFA::State state)
                {
                  visitingStates.push_back(state);
                  if(std::regex_match(sManager.getStateProperty(fa.getStatePropertyId(state)),reg))
                    {
                      acceptors.push_back(state);
                      mapping[state]=2;
                      std::cout << sManager.getStateProperty(fa.getStatePropertyId(state)) << " is reachable and must be set acceptor\n";
                    }
                  else
                    {
                      mapping[state]=1;
                      std::cout << sManager.getStateProperty(fa.getStatePropertyId(state)) << " is reachable but may not be set acceptor\n";
                    }
                });
  while(!visitingStates.empty())
    {
      auto current = visitingStates.front();
      visitingStates.pop_front();
      std::for_each(fa.outputTransitionBegin(current), fa.outputTransitionEnd(current),
                    [&](DdAutFA::Transition transition)
                    {
                      if(mapping[transition.target()] == 0)
                        {
                          visitingStates.push_back(transition.target());
                          if(std::regex_match(sManager.getStateProperty(fa.getStatePropertyId(transition.target())),reg))
                            {
                              acceptors.push_back(transition.target());
                              mapping[transition.target()]=2;
                              std::cout << sManager.getStateProperty(fa.getStatePropertyId(transition.target())) << " is reachable and must be set acceptor\n";
                            }
                          else
                            {
                              mapping[transition.target()]=1;
                              std::cout << sManager.getStateProperty(fa.getStatePropertyId(transition.target())) << " is reachable and may not be set acceptor\n";
                            }
                        }
                    });
    }
}


void tagPredecessors(DdAutFA & fa,std::list<DdAutFA::State> & acceptors, CstStMap<char> & mapping)
{
  std::list<DdAutFA::State> visitingStates = acceptors;
  while(!visitingStates.empty())
    {
      auto current = visitingStates.front();
      for(const auto & state : acceptors)
        {
          applyTag(fa,state,Tag::prefixclosedfinal);
        }
      
      visitingStates.pop_front();
      std::for_each(fa.inputTransitionBegin(current), fa.inputTransitionEnd(current),
                    [&](DdAutFA::Transition transition)
                    {
                      if(mapping[transition.source()] == 1)
                        {
                          mapping[transition.source()] = 2;
                          visitingStates.push_back(transition.source());
                          applyTag(fa,transition.source(),Tag::prefixclosedfinal);
                        }
                    });
    }
}

void setPrefixClosedAcceptorTag(DdAutFA & fa,DdAutStateManager & sManager,std::regex & reg)
{
  CstStMap<char> mapping(fa.behaviour(),fa.numberOfStates(),0);
  std::list<DdAutFA::State> acceptors;
  getReachable(fa,mapping,reg,sManager,acceptors);
  tagPredecessors(fa,acceptors,mapping);
}

void tagStates(DdAutFA & fa, DdAutStateManager & sManager, const std::string & expr)
{
  auto pos = expr.find_first_of(":");
  if(pos== std::string::npos)
    {
        return;
      }
  
    auto tagIt = tagOf.find(expr.substr(0,pos));
    if(tagIt != tagOf.end())
      { auto regexp = expr.substr(pos+1);
        std::regex reg(regexp);
        if(tagIt->second!=Tag::prefixclosedfinal)
          {
         
            for(auto & stateProperty: sManager.storage())
              {
                if(std::regex_match(stateProperty,reg))
                  {
                    applyTag(fa,fa.getState(sManager.statePropertyId(stateProperty)),tagIt->second);
                  }
              }
          }
        else
          {
            setPrefixClosedAcceptorTag(fa,sManager,reg);
          }
      }
  }

  size_t
    tagDdAutStates2(const string & fileName, const string & output, const std::vector<std::string> & regexp)
  {
    DdAutFileDescriptor descriptor;
    DdAutEventManager eManager;
    DdAutStateManager sManager;
    ifstream file(fileName.c_str());
    if(file.is_open())
      {
        auto loaded = descriptor.readStream(file);
        file.close();
        if(!loaded)
          {
            return printCommandLineError(Msg("Error when loading the 'ddaut' automaton file %1%") % fileName);
          }
      }
    else
      {
        return printCommandLineError(Msg("Error when opening the 'ddaut' automaton file %1%") % fileName);
      }
    DdAutFA fa;
    bool result = faFromDescriptor(descriptor, fa, sManager, eManager);
    if(!result)
      {
        return printCommandLineError(Msg("Error when converting the DdAutFileDescriptor from %1% to a Finite Automaton") % fileName);
      }
    for(const auto & expr : regexp)
      {
        tagStates(fa,sManager,expr);
      }
 
    if(output.empty())
      {
        faToDdAutFile(std::cout,{fa, sManager, eManager});
      }
    else
      {
        ofstream outfile(output.c_str());
        if(outfile.is_open())
          {
            faToDdAutFile(outfile,{fa, sManager, eManager});
            outfile.close();
          }
        else
          {
            return printCommandLineError(Msg("Error when creating the dot file %1%") % output);
          }
      }
    return ERROR_UNHANDLED_EXCEPTION;
  }


  size_t tagDdAutStates(const string & fileName, const string & output, const std::vector<std::string> & regexp)
  {

    if(!output.empty())
      {
        if(!suffixes.match(output, "ddaut"))
          {
            return printCommandLineError(Msg("Expecting an output file with a name ending with .ddaut, but I read %1%") % output);
          }
      }
  
    if(suffixes.match(fileName, "ddaut"))
      {
        return tagDdAutStates2(fileName, output,regexp);
      }
    else
      {
        return printCommandLineError(Msg("Expecting a file with a name ending with .ddaut, but I read %1%") % fileName);
      }
    return ERROR_UNHANDLED_EXCEPTION;
  }

  int
    main(int argc, char** argv)
  {
    std::string fileName, output;
    std::vector<std::string> regexp;
    try
      {
     
        Poptions::options_description desc("Options");
        Poptions::variables_map vm;
        initialiseOptions(argc, argv, desc, vm);
        if(vm.count("help"))
          {
            return printUsage(program + briefcomment + detailedcomment, desc);
          }
        if(vm.count("file"))
          {
            fileName = vm["file"].as<std::string> ();
          }
        if(vm.count("output"))
          {
            output = vm["output"].as<std::string>();
          }
        if(vm.count("regexp"))
          {
            regexp = vm["regexp"].as<std::vector<std::string>>();
          }
      }
    catch(Poptions::required_option & e)
      {
        return printCommandLineError(e.what());
      }
    catch(Poptions::error & e)
      {
        return printCommandLineError(e.what());
      }
    if(regexp.empty())
      {
        return  printCommandLineError(Msg("Expecting at least one regular expression but I got nothing, so I do nothing."));
      }
    return tagDdAutStates(fileName, output,regexp);
  }