ragel/dotcodegen.cpp

   1 /*
   2  *  Copyright 2001-2007 Adrian Thurston <thurston@complang.org>
   3  */
   4
   5 /*  This file is part of Ragel.
   6  *
   7  *  Ragel is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  Ragel is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with Ragel; if not, write to the Free Software
  19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  */
  21
  22 #include "ragel.h"
  23 #include "dotcodegen.h"
  24 #include "gendata.h"
  25
  26 using std::istream;
  27 using std::ifstream;
  28 using std::ostream;
  29 using std::ios;
  30 using std::cin;
  31 using std::cout;
  32 using std::cerr;
  33 using std::endl;
  34
  35 /* Invoked by the parser when the root element is opened. */
  36 ostream *dotOpenOutput( const char *inputFile )
  37 {
  38         /* Make sure we are not writing to the same file as the input file. */
  39         if ( outputFileName != 0 && strcmp( inputFile, outputFileName  ) == 0 ) {
  40                 error() << "output file \"" << outputFileName  <<
  41                                 "\" is the same as the input file" << endl;
  42         }
  43
  44         if ( outputFileName != 0 ) {
  45                 /* Create the filter on the output and open it. */
  46                 outFilter = new output_filter( outputFileName );
  47                 outFilter->open( outputFileName, ios::out|ios::trunc );
  48                 if ( !outFilter->is_open() ) {
  49                         error() << "error opening " << outputFileName << " for writing" << endl;
  50                         exit(1);
  51                 }
  52
  53                 /* Open the output stream, attaching it to the filter. */
  54                 outStream = new ostream( outFilter );
  55         }
  56         else {
  57                 /* Writing out ot std out. */
  58                 outStream = &cout;
  59         }
  60         return outStream;
  61 }
  62
  63 /* Invoked by the parser when a ragel definition is opened. */
  64 CodeGenData *dotMakeCodeGen( const char *sourceFileName, const char *fsmName,
  65                 ostream &out, bool wantComplete )
  66 {
  67         CodeGenData *codeGen = new GraphvizDotGen(out);
  68
  69         codeGen->sourceFileName = sourceFileName;
  70         codeGen->fsmName = fsmName;
  71         codeGen->wantComplete = wantComplete;
  72
  73         return codeGen;
  74 }
  75
  76 /* Override this so that write statement processing is ignored */
  77 void GraphvizDotGen::writeStatement( InputLoc &, int, char ** )
  78 {
  79 }
  80
  81 std::ostream &GraphvizDotGen::KEY( Key key )
  82 {
  83         if ( displayPrintables && key.isPrintable() ) {
  84                 // Output values as characters, ensuring we escape the quote (") character
  85                 char cVal = (char) key.getVal();
  86                 switch ( cVal ) {
  87                         case '"': case '\\':
  88                                 out << "'\\" << cVal << "'";
  89                                 break;
  90                         case '\a':
  91                                 out << "'\\\\a'";
  92                                 break;
  93                         case '\b':
  94                                 out << "'\\\\b'";
  95                                 break;
  96                         case '\t':
  97                                 out << "'\\\\t'";
  98                                 break;
  99                         case '\n':
 100                                 out << "'\\\\n'";
 101                                 break;
 102                         case '\v':
 103                                 out << "'\\\\v'";
 104                                 break;
 105                         case '\f':
 106                                 out << "'\\\\f'";
 107                                 break;
 108                         case '\r':
 109                                 out << "'\\\\r'";
 110                                 break;
 111                         case ' ':
 112                                 out << "SP";
 113                                 break;
 114                         default:
 115                                 out << "'" << cVal << "'";
 116                                 break;
 117                 }
 118         }
 119         else {
 120                 if ( keyOps->isSigned )
 121                         out << key.getVal();
 122                 else
 123                         out << (unsigned long) key.getVal();
 124         }
 125
 126         return out;
 127 }
 128
 129 std::ostream &GraphvizDotGen::TRANS_ACTION( RedStateAp *fromState, RedTransAp *trans )
 130 {
 131         int n = 0;
 132         RedAction *actions[3];
 133
 134         if ( fromState->fromStateAction != 0 )
 135                 actions[n++] = fromState->fromStateAction;
 136         if ( trans->action != 0 )
 137                 actions[n++] = trans->action;
 138         if ( trans->targ != 0 && trans->targ->toStateAction != 0 )
 139                 actions[n++] = trans->targ->toStateAction;
 140
 141         if ( n > 0 )
 142                 out << " / ";
 143
 144         /* Loop the existing actions and write out what's there. */
 145         for ( int a = 0; a < n; a++ ) {
 146                 for ( GenActionTable::Iter actIt = actions[a]->key.first(); actIt.lte(); actIt++ ) {
 147                         GenAction *action = actIt->value;
 148                         out << action->nameOrLoc();
 149                         if ( a < n-1 || !actIt.last() )
 150                                 out << ", ";
 151                 }
 152         }
 153         return out;
 154 }
 155
 156 std::ostream &GraphvizDotGen::ACTION( RedAction *action )
 157 {
 158         /* The action. */
 159         out << " / ";
 160         for ( GenActionTable::Iter actIt = action->key.first(); actIt.lte(); actIt++ ) {
 161                 GenAction *action = actIt->value;
 162                 if ( action->name != 0 )
 163                         out << action->name;
 164                 else
 165                         out << action->loc.line << ":" << action->loc.col;
 166                 if ( !actIt.last() )
 167                         out << ", ";
 168         }
 169         return out;
 170 }
 171
 172 std::ostream &GraphvizDotGen::ONCHAR( Key lowKey, Key highKey )
 173 {
 174         if ( lowKey > keyOps->maxKey ) {
 175                 GenCondSpace *condSpace = findCondSpace( lowKey, highKey );
 176                 Key values = ( lowKey - condSpace->baseKey ) / keyOps->alphSize();
 177
 178                 lowKey = keyOps->minKey +
 179                         (lowKey - condSpace->baseKey - keyOps->alphSize() * values.getVal());
 180                 highKey = keyOps->minKey +
 181                         (highKey - condSpace->baseKey - keyOps->alphSize() * values.getVal());
 182                 KEY( lowKey );
 183                 if ( lowKey != highKey ) {
 184                         out << "..";
 185                         KEY( highKey );
 186                 }
 187                 out << "(";
 188
 189                 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 190                         bool set = values & (1 << csi.pos());
 191                         if ( !set )
 192                                 out << "!";
 193                         out << (*csi)->nameOrLoc();
 194                         if ( !csi.last() )
 195                                 out << ", ";
 196                 }
 197                 out << ")";
 198         }
 199         else {
 200                 /* Output the key. Possibly a range. */
 201                 KEY( lowKey );
 202                 if ( highKey != lowKey ) {
 203                         out << "..";
 204                         KEY( highKey );
 205                 }
 206         }
 207         return out;
 208 }
 209
 210 void GraphvizDotGen::writeTransList( RedStateAp *state )
 211 {
 212         /* Build the set of unique transitions out of this state. */
 213         RedTransSet stTransSet;
 214         for ( RedTransList::Iter tel = state->outRange; tel.lte(); tel++ ) {
 215                 /* If we haven't seen the transitions before, the move forward
 216                  * emitting all the transitions on the same character. */
 217                 if ( stTransSet.insert( tel->value ) ) {
 218                         /* Write out the from and to states. */
 219                         out << "\t" << state->id << " -> ";
 220
 221                         if ( tel->value->targ == 0 )
 222                                 out << "err_" << state->id;
 223                         else
 224                                 out << tel->value->targ->id;
 225
 226                         /* Begin the label. */
 227                         out << " [ label = \"";
 228                         ONCHAR( tel->lowKey, tel->highKey );
 229
 230                         /* Walk the transition list, finding the same. */
 231                         for ( RedTransList::Iter mtel = tel.next(); mtel.lte(); mtel++ ) {
 232                                 if ( mtel->value == tel->value ) {
 233                                         out << ", ";
 234                                         ONCHAR( mtel->lowKey, mtel->highKey );
 235                                 }
 236                         }
 237
 238                         /* Write the action and close the transition. */
 239                         TRANS_ACTION( state, tel->value );
 240                         out << "\" ];\n";
 241                 }
 242         }
 243
 244         /* Write the default transition. */
 245         if ( state->defTrans != 0 ) {
 246                 /* Write out the from and to states. */
 247                 out << "\t" << state->id << " -> ";
 248
 249                 if ( state->defTrans->targ == 0 )
 250                         out << "err_" << state->id;
 251                 else
 252                         out << state->defTrans->targ->id;
 253
 254                 /* Begin the label. */
 255                 out << " [ label = \"DEF";
 256
 257                 /* Write the action and close the transition. */
 258                 TRANS_ACTION( state, state->defTrans );
 259                 out << "\" ];\n";
 260         }
 261 }
 262
 263 void GraphvizDotGen::writeDotFile( )
 264 {
 265         out <<
 266                 "digraph " << fsmName << " {\n"
 267                 "       rankdir=LR;\n";
 268
 269         /* Define the psuedo states. Transitions will be done after the states
 270          * have been defined as either final or not final. */
 271         out << "        node [ shape = point ];\n";
 272
 273         if ( redFsm->startState != 0 )
 274                 out << "        ENTRY;\n";
 275
 276         /* Psuedo states for entry points in the entry map. */
 277         for ( EntryIdVect::Iter en = entryPointIds; en.lte(); en++ ) {
 278                 RedStateAp *state = allStates + *en;
 279                 out << "        en_" << state->id << ";\n";
 280         }
 281
 282         /* Psuedo states for final states with eof actions. */
 283         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 284                 if ( st->eofTrans != 0 && st->eofTrans->action != 0 )
 285                         out << "        eof_" << st->id << ";\n";
 286                 if ( st->eofAction != 0 )
 287                         out << "        eof_" << st->id << ";\n";
 288         }
 289
 290         out << "        node [ shape = circle, height = 0.2 ];\n";
 291
 292         /* Psuedo states for states whose default actions go to error. */
 293         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 294                 bool needsErr = false;
 295                 if ( st->defTrans != 0 && st->defTrans->targ == 0 )
 296                         needsErr = true;
 297                 else {
 298                         for ( RedTransList::Iter tel = st->outRange; tel.lte(); tel++ ) {
 299                                 if ( tel->value->targ == 0 ) {
 300                                         needsErr = true;
 301                                         break;
 302                                 }
 303                         }
 304                 }
 305
 306                 if ( needsErr )
 307                         out << "        err_" << st->id << " [ label=\"\"];\n";
 308         }
 309
 310         /* Attributes common to all nodes, plus double circle for final states. */
 311         out << "        node [ fixedsize = true, height = 0.65, shape = doublecircle ];\n";
 312
 313         /* List Final states. */
 314         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 315                 if ( st->isFinal )
 316                         out << "        " << st->id << ";\n";
 317         }
 318
 319         /* List transitions. */
 320         out << "        node [ shape = circle ];\n";
 321
 322         /* Walk the states. */
 323         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 324                 writeTransList( st );
 325
 326         /* Transitions into the start state. */
 327         if ( redFsm->startState != 0 )
 328                 out << "        ENTRY -> " << redFsm->startState->id << " [ label = \"IN\" ];\n";
 329
 330         /* Transitions into the entry points. */
 331         for ( EntryIdVect::Iter en = entryPointIds; en.lte(); en++ ) {
 332                 RedStateAp *state = allStates + *en;
 333                 char *name = entryPointNames[en.pos()];
 334                 out << "        en_" << state->id << " -> " << state->id <<
 335                                 " [ label = \"" << name << "\" ];\n";
 336         }
 337
 338         /* Out action transitions. */
 339         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 340                 if ( st->eofTrans != 0 && st->eofTrans->action != 0 ) {
 341                         out << "        " << st->id << " -> eof_" <<
 342                                         st->id << " [ label = \"EOF";
 343                         ACTION( st->eofTrans->action ) << "\" ];\n";
 344                 }
 345                 if ( st->eofAction != 0 ) {
 346                         out << "        " << st->id << " -> eof_" <<
 347                                         st->id << " [ label = \"EOF";
 348                         ACTION( st->eofAction ) << "\" ];\n";
 349                 }
 350         }
 351
 352         out <<
 353                 "}\n";
 354 }
 355
 356 void GraphvizDotGen::finishRagelDef()
 357 {
 358         if ( !graphvizDone ) {
 359                 graphvizDone = true;
 360
 361                 /* For dot file generation we want to pick default transitions. */
 362                 redFsm->chooseDefaultSpan();
 363
 364                 /* Write out with it. */
 365                 writeDotFile();
 366         }
 367 }