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 a ragel definition is opened. */
  36 CodeGenData *dotMakeCodeGen( const char *sourceFileName, const char *fsmName,
  37                 ostream &out, bool wantComplete )
  38 {
  39         CodeGenData *codeGen = new GraphvizDotGen(out);
  40
  41         codeGen->sourceFileName = sourceFileName;
  42         codeGen->fsmName = fsmName;
  43         codeGen->wantComplete = wantComplete;
  44
  45         return codeGen;
  46 }
  47
  48 /* Override this so that write statement processing is ignored */
  49 void GraphvizDotGen::writeStatement( InputLoc &, int, char ** )
  50 {
  51 }
  52
  53 std::ostream &GraphvizDotGen::KEY( Key key )
  54 {
  55         if ( displayPrintables && key.isPrintable() ) {
  56                 // Output values as characters, ensuring we escape the quote (") character
  57                 char cVal = (char) key.getVal();
  58                 switch ( cVal ) {
  59                         case '"': case '\\':
  60                                 out << "'\\" << cVal << "'";
  61                                 break;
  62                         case '\a':
  63                                 out << "'\\\\a'";
  64                                 break;
  65                         case '\b':
  66                                 out << "'\\\\b'";
  67                                 break;
  68                         case '\t':
  69                                 out << "'\\\\t'";
  70                                 break;
  71                         case '\n':
  72                                 out << "'\\\\n'";
  73                                 break;
  74                         case '\v':
  75                                 out << "'\\\\v'";
  76                                 break;
  77                         case '\f':
  78                                 out << "'\\\\f'";
  79                                 break;
  80                         case '\r':
  81                                 out << "'\\\\r'";
  82                                 break;
  83                         case ' ':
  84                                 out << "SP";
  85                                 break;
  86                         default:
  87                                 out << "'" << cVal << "'";
  88                                 break;
  89                 }
  90         }
  91         else {
  92                 if ( keyOps->isSigned )
  93                         out << key.getVal();
  94                 else
  95                         out << (unsigned long) key.getVal();
  96         }
  97
  98         return out;
  99 }
 100
 101 std::ostream &GraphvizDotGen::TRANS_ACTION( RedStateAp *fromState, RedTransAp *trans )
 102 {
 103         int n = 0;
 104         RedAction *actions[3];
 105
 106         if ( fromState->fromStateAction != 0 )
 107                 actions[n++] = fromState->fromStateAction;
 108         if ( trans->action != 0 )
 109                 actions[n++] = trans->action;
 110         if ( trans->targ != 0 && trans->targ->toStateAction != 0 )
 111                 actions[n++] = trans->targ->toStateAction;
 112
 113         if ( n > 0 )
 114                 out << " / ";
 115
 116         /* Loop the existing actions and write out what's there. */
 117         for ( int a = 0; a < n; a++ ) {
 118                 for ( GenActionTable::Iter actIt = actions[a]->key.first(); actIt.lte(); actIt++ ) {
 119                         GenAction *action = actIt->value;
 120                         out << action->nameOrLoc();
 121                         if ( a < n-1 || !actIt.last() )
 122                                 out << ", ";
 123                 }
 124         }
 125         return out;
 126 }
 127
 128 std::ostream &GraphvizDotGen::ACTION( RedAction *action )
 129 {
 130         /* The action. */
 131         out << " / ";
 132         for ( GenActionTable::Iter actIt = action->key.first(); actIt.lte(); actIt++ ) {
 133                 GenAction *action = actIt->value;
 134                 if ( action->name != 0 )
 135                         out << action->name;
 136                 else
 137                         out << action->loc.line << ":" << action->loc.col;
 138                 if ( !actIt.last() )
 139                         out << ", ";
 140         }
 141         return out;
 142 }
 143
 144 std::ostream &GraphvizDotGen::ONCHAR( Key lowKey, Key highKey )
 145 {
 146         if ( lowKey > keyOps->maxKey ) {
 147                 GenCondSpace *condSpace = findCondSpace( lowKey, highKey );
 148                 Key values = ( lowKey - condSpace->baseKey ) / keyOps->alphSize();
 149
 150                 lowKey = keyOps->minKey +
 151                         (lowKey - condSpace->baseKey - keyOps->alphSize() * values.getVal());
 152                 highKey = keyOps->minKey +
 153                         (highKey - condSpace->baseKey - keyOps->alphSize() * values.getVal());
 154                 KEY( lowKey );
 155                 if ( lowKey != highKey ) {
 156                         out << "..";
 157                         KEY( highKey );
 158                 }
 159                 out << "(";
 160
 161                 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 162                         bool set = values & (1 << csi.pos());
 163                         if ( !set )
 164                                 out << "!";
 165                         out << (*csi)->nameOrLoc();
 166                         if ( !csi.last() )
 167                                 out << ", ";
 168                 }
 169                 out << ")";
 170         }
 171         else {
 172                 /* Output the key. Possibly a range. */
 173                 KEY( lowKey );
 174                 if ( highKey != lowKey ) {
 175                         out << "..";
 176                         KEY( highKey );
 177                 }
 178         }
 179         return out;
 180 }
 181
 182 void GraphvizDotGen::writeTransList( RedStateAp *state )
 183 {
 184         /* Build the set of unique transitions out of this state. */
 185         RedTransSet stTransSet;
 186         for ( RedTransList::Iter tel = state->outRange; tel.lte(); tel++ ) {
 187                 /* If we haven't seen the transitions before, the move forward
 188                  * emitting all the transitions on the same character. */
 189                 if ( stTransSet.insert( tel->value ) ) {
 190                         /* Write out the from and to states. */
 191                         out << "\t" << state->id << " -> ";
 192
 193                         if ( tel->value->targ == 0 )
 194                                 out << "err_" << state->id;
 195                         else
 196                                 out << tel->value->targ->id;
 197
 198                         /* Begin the label. */
 199                         out << " [ label = \"";
 200                         ONCHAR( tel->lowKey, tel->highKey );
 201
 202                         /* Walk the transition list, finding the same. */
 203                         for ( RedTransList::Iter mtel = tel.next(); mtel.lte(); mtel++ ) {
 204                                 if ( mtel->value == tel->value ) {
 205                                         out << ", ";
 206                                         ONCHAR( mtel->lowKey, mtel->highKey );
 207                                 }
 208                         }
 209
 210                         /* Write the action and close the transition. */
 211                         TRANS_ACTION( state, tel->value );
 212                         out << "\" ];\n";
 213                 }
 214         }
 215
 216         /* Write the default transition. */
 217         if ( state->defTrans != 0 ) {
 218                 /* Write out the from and to states. */
 219                 out << "\t" << state->id << " -> ";
 220
 221                 if ( state->defTrans->targ == 0 )
 222                         out << "err_" << state->id;
 223                 else
 224                         out << state->defTrans->targ->id;
 225
 226                 /* Begin the label. */
 227                 out << " [ label = \"DEF";
 228
 229                 /* Write the action and close the transition. */
 230                 TRANS_ACTION( state, state->defTrans );
 231                 out << "\" ];\n";
 232         }
 233 }
 234
 235 void GraphvizDotGen::writeDotFile( )
 236 {
 237         out <<
 238                 "digraph " << fsmName << " {\n"
 239                 "       rankdir=LR;\n";
 240
 241         /* Define the psuedo states. Transitions will be done after the states
 242          * have been defined as either final or not final. */
 243         out << "        node [ shape = point ];\n";
 244
 245         if ( redFsm->startState != 0 )
 246                 out << "        ENTRY;\n";
 247
 248         /* Psuedo states for entry points in the entry map. */
 249         for ( EntryIdVect::Iter en = entryPointIds; en.lte(); en++ ) {
 250                 RedStateAp *state = allStates + *en;
 251                 out << "        en_" << state->id << ";\n";
 252         }
 253
 254         /* Psuedo states for final states with eof actions. */
 255         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 256                 if ( st->eofTrans != 0 && st->eofTrans->action != 0 )
 257                         out << "        eof_" << st->id << ";\n";
 258                 if ( st->eofAction != 0 )
 259                         out << "        eof_" << st->id << ";\n";
 260         }
 261
 262         out << "        node [ shape = circle, height = 0.2 ];\n";
 263
 264         /* Psuedo states for states whose default actions go to error. */
 265         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 266                 bool needsErr = false;
 267                 if ( st->defTrans != 0 && st->defTrans->targ == 0 )
 268                         needsErr = true;
 269                 else {
 270                         for ( RedTransList::Iter tel = st->outRange; tel.lte(); tel++ ) {
 271                                 if ( tel->value->targ == 0 ) {
 272                                         needsErr = true;
 273                                         break;
 274                                 }
 275                         }
 276                 }
 277
 278                 if ( needsErr )
 279                         out << "        err_" << st->id << " [ label=\"\"];\n";
 280         }
 281
 282         /* Attributes common to all nodes, plus double circle for final states. */
 283         out << "        node [ fixedsize = true, height = 0.65, shape = doublecircle ];\n";
 284
 285         /* List Final states. */
 286         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 287                 if ( st->isFinal )
 288                         out << "        " << st->id << ";\n";
 289         }
 290
 291         /* List transitions. */
 292         out << "        node [ shape = circle ];\n";
 293
 294         /* Walk the states. */
 295         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 296                 writeTransList( st );
 297
 298         /* Transitions into the start state. */
 299         if ( redFsm->startState != 0 )
 300                 out << "        ENTRY -> " << redFsm->startState->id << " [ label = \"IN\" ];\n";
 301
 302         /* Transitions into the entry points. */
 303         for ( EntryIdVect::Iter en = entryPointIds; en.lte(); en++ ) {
 304                 RedStateAp *state = allStates + *en;
 305                 char *name = entryPointNames[en.pos()];
 306                 out << "        en_" << state->id << " -> " << state->id <<
 307                                 " [ label = \"" << name << "\" ];\n";
 308         }
 309
 310         /* Out action transitions. */
 311         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 312                 if ( st->eofTrans != 0 && st->eofTrans->action != 0 ) {
 313                         out << "        " << st->id << " -> eof_" <<
 314                                         st->id << " [ label = \"EOF";
 315                         ACTION( st->eofTrans->action ) << "\" ];\n";
 316                 }
 317                 if ( st->eofAction != 0 ) {
 318                         out << "        " << st->id << " -> eof_" <<
 319                                         st->id << " [ label = \"EOF";
 320                         ACTION( st->eofAction ) << "\" ];\n";
 321                 }
 322         }
 323
 324         out <<
 325                 "}\n";
 326 }
 327
 328 void GraphvizDotGen::finishRagelDef()
 329 {
 330         if ( !graphvizDone ) {
 331                 graphvizDone = true;
 332
 333                 /* For dot file generation we want to pick default transitions. */
 334                 redFsm->chooseDefaultSpan();
 335
 336                 /* Write out with it. */
 337                 writeDotFile();
 338         }
 339 }