rlcodegen/gvdotgen.cpp

   1 /*
   2  *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
   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
  23 #include "rlcodegen.h"
  24 #include "gvdotgen.h"
  25 #include "gendata.h"
  26 #include "redfsm.h"
  27
  28 using namespace std;
  29
  30 GraphvizDotGen::GraphvizDotGen( char *fsmName, CodeGenData *cgd,
  31                 RedFsmAp *redFsm, ostream &out )
  32 :
  33         fsmName(fsmName),
  34         cgd(cgd),
  35         redFsm(redFsm),
  36         out(out)
  37 {
  38 }
  39
  40 std::ostream &GraphvizDotGen::KEY( Key key )
  41 {
  42         if ( printPrintables && key.isPrintable() ) {
  43                 // Output values as characters, ensuring we escape the quote (") character
  44                 char cVal = (char) key.getVal();
  45                 out << "'";
  46                 switch ( cVal ) {
  47                         case '"': case '\\':
  48                                 out << "\\" << cVal;
  49                                 break;
  50                         default:
  51                                 out << cVal;
  52                                 break;
  53                 }
  54                 out << "'";
  55         }
  56         else {
  57                 if ( keyOps->isSigned )
  58                         out << key.getVal();
  59                 else
  60                         out << (unsigned long) key.getVal();
  61         }
  62
  63         return out;
  64 }
  65
  66 std::ostream &GraphvizDotGen::TRANS_ACTION( RedStateAp *fromState, RedTransAp *trans )
  67 {
  68         int n = 0;
  69         RedAction *actions[3];
  70
  71         if ( fromState->fromStateAction != 0 )
  72                 actions[n++] = fromState->fromStateAction;
  73         if ( trans->action != 0 )
  74                 actions[n++] = trans->action;
  75         if ( trans->targ != 0 && trans->targ->toStateAction != 0 )
  76                 actions[n++] = trans->targ->toStateAction;
  77
  78         if ( n > 0 )
  79                 out << " / ";
  80
  81         /* Loop the existing actions and write out what's there. */
  82         for ( int a = 0; a < n; a++ ) {
  83                 for ( ActionTable::Iter actIt = actions[a]->key.first(); actIt.lte(); actIt++ ) {
  84                         Action *action = actIt->value;
  85                         out << action->nameOrLoc();
  86                         if ( a < n-1 || !actIt.last() )
  87                                 out << ", ";
  88                 }
  89         }
  90         return out;
  91 }
  92
  93 std::ostream &GraphvizDotGen::ACTION( RedAction *action )
  94 {
  95         /* The action. */
  96         out << " / ";
  97         for ( ActionTable::Iter actIt = action->key.first(); actIt.lte(); actIt++ ) {
  98                 Action *action = actIt->value;
  99                 if ( action->name != 0 )
 100                         out << action->name;
 101                 else
 102                         out << action->loc.line << ":" << action->loc.col;
 103                 if ( !actIt.last() )
 104                         out << ", ";
 105         }
 106         return out;
 107 }
 108
 109 std::ostream &GraphvizDotGen::ONCHAR( Key lowKey, Key highKey )
 110 {
 111         if ( lowKey > keyOps->maxKey ) {
 112                 CondSpace *condSpace = cgd->findCondSpace( lowKey, highKey );
 113                 Key values = ( lowKey - condSpace->baseKey ) / keyOps->alphSize();
 114
 115                 lowKey = keyOps->minKey +
 116                         (lowKey - condSpace->baseKey - keyOps->alphSize() * values.getVal());
 117                 highKey = keyOps->minKey +
 118                         (highKey - condSpace->baseKey - keyOps->alphSize() * values.getVal());
 119                 KEY( lowKey );
 120                 if ( lowKey != highKey ) {
 121                         out << "..";
 122                         KEY( highKey );
 123                 }
 124                 out << "(";
 125
 126                 for ( CondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 127                         bool set = values & (1 << csi.pos());
 128                         if ( !set )
 129                                 out << "!";
 130                         out << (*csi)->nameOrLoc();
 131                         if ( !csi.last() )
 132                                 out << ", ";
 133                 }
 134                 out << ")";
 135         }
 136         else {
 137                 /* Output the key. Possibly a range. */
 138                 KEY( lowKey );
 139                 if ( highKey != lowKey ) {
 140                         out << "..";
 141                         KEY( highKey );
 142                 }
 143         }
 144         return out;
 145 }
 146
 147 void GraphvizDotGen::writeTransList( RedStateAp *state )
 148 {
 149         /* Build the set of unique transitions out of this state. */
 150         RedTransSet stTransSet;
 151         for ( RedTransList::Iter tel = state->outRange; tel.lte(); tel++ ) {
 152                 /* If we haven't seen the transitions before, the move forward
 153                  * emitting all the transitions on the same character. */
 154                 if ( stTransSet.insert( tel->value ) ) {
 155                         /* Write out the from and to states. */
 156                         out << "\t" << state->id << " -> ";
 157
 158                         if ( tel->value->targ == 0 )
 159                                 out << "err_" << state->id;
 160                         else
 161                                 out << tel->value->targ->id;
 162
 163                         /* Begin the label. */
 164                         out << " [ label = \"";
 165                         ONCHAR( tel->lowKey, tel->highKey );
 166
 167                         /* Walk the transition list, finding the same. */
 168                         for ( RedTransList::Iter mtel = tel.next(); mtel.lte(); mtel++ ) {
 169                                 if ( mtel->value == tel->value ) {
 170                                         out << ", ";
 171                                         ONCHAR( mtel->lowKey, mtel->highKey );
 172                                 }
 173                         }
 174
 175                         /* Write the action and close the transition. */
 176                         TRANS_ACTION( state, tel->value );
 177                         out << "\" ];\n";
 178                 }
 179         }
 180
 181         /* Write the default transition. */
 182         if ( state->defTrans != 0 ) {
 183                 /* Write out the from and to states. */
 184                 out << "\t" << state->id << " -> ";
 185
 186                 if ( state->defTrans->targ == 0 )
 187                         out << "err_" << state->id;
 188                 else
 189                         out << state->defTrans->targ->id;
 190
 191                 /* Begin the label. */
 192                 out << " [ label = \"DEF";
 193
 194                 /* Write the action and close the transition. */
 195                 TRANS_ACTION( state, state->defTrans );
 196                 out << "\" ];\n";
 197         }
 198 }
 199
 200 void GraphvizDotGen::writeDotFile( )
 201 {
 202         out <<
 203                 "digraph " << fsmName << " {\n"
 204                 "       rankdir=LR;\n";
 205
 206         /* Define the psuedo states. Transitions will be done after the states
 207          * have been defined as either final or not final. */
 208         out << "        node [ shape = point ];\n";
 209         out << "        ENTRY;\n";
 210
 211         /* Psuedo states for entry points in the entry map. */
 212         for ( EntryIdVect::Iter en = cgd->entryPointIds; en.lte(); en++ ) {
 213                 RedStateAp *state = cgd->allStates + *en;
 214                 out << "        en_" << state->id << ";\n";
 215         }
 216
 217         /* Psuedo states for final states with eof actions. */
 218         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 219                 if ( st->eofAction != 0 )
 220                         out << "        eof_" << st->id << ";\n";
 221         }
 222
 223         out << "        node [ shape = circle, height = 0.2 ];\n";
 224
 225         /* Psuedo states for states whose default actions go to error. */
 226         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 227                 bool needsErr = false;
 228                 if ( st->defTrans != 0 && st->defTrans->targ == 0 )
 229                         needsErr = true;
 230                 else {
 231                         for ( RedTransList::Iter tel = st->outRange; tel.lte(); tel++ ) {
 232                                 if ( tel->value->targ == 0 ) {
 233                                         needsErr = true;
 234                                         break;
 235                                 }
 236                         }
 237                 }
 238
 239                 if ( needsErr )
 240                         out << "        err_" << st->id << " [ label=\"\"];\n";
 241         }
 242
 243         /* Attributes common to all nodes, plus double circle for final states. */
 244         out << "        node [ fixedsize = true, height = 0.65, shape = doublecircle ];\n";
 245
 246         /* List Final states. */
 247         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 248                 if ( st->isFinal )
 249                         out << "        " << st->id << ";\n";
 250         }
 251
 252         /* List transitions. */
 253         out << "        node [ shape = circle ];\n";
 254
 255         /* Walk the states. */
 256         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 257                 writeTransList( st );
 258
 259         /* Transitions into the start state. */
 260         out << "        ENTRY -> " << redFsm->startState->id << " [ label = \"IN";
 261         out << "\" ];\n";
 262
 263         /* Transitions into the entry points. */
 264         for ( EntryIdVect::Iter en = cgd->entryPointIds; en.lte(); en++ ) {
 265                 RedStateAp *state = cgd->allStates + *en;
 266                 char *name = cgd->entryPointNames[en.pos()];
 267                 out << "        en_" << state->id << " -> " << state->id <<
 268                                 " [ label = \"" << name << "\" ];\n";
 269         }
 270
 271         /* Out action transitions. */
 272         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 273                 if ( st->eofAction != 0 ) {
 274                         out << "        " << st->id << " -> eof_" <<
 275                                         st->id << " [ label = \"EOF";
 276                         ACTION( st->eofAction ) << "\" ];\n";
 277                 }
 278         }
 279
 280         out <<
 281                 "}\n";
 282 }