ragel-6.10.tar.gz: ragel-6.10/ragel/redfsm.cpp

"Fossies" - the Fresh Open Source Software Archive

Member "ragel-6.10/ragel/redfsm.cpp" (24 Mar 2017, 16725 Bytes) of package /linux/misc/ragel-6.10.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "redfsm.cpp" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report:

6.9_vs_6.10.

1 /* 2 * Copyright 2001-2006 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 "redfsm.h" 23 #include "avlmap.h" 24 #include "mergesort.h" 25 #include <iostream> 26 #include <sstream> 27 28 using std::ostringstream; 29 30 string GenAction::nameOrLoc() 31 { 32 if ( name != 0 ) 33 return string(name); 34 else { 35 ostringstream ret; 36 ret << loc.line << ":" << loc.col; 37 return ret.str(); 38 } 39 } 40 41 RedFsmAp::RedFsmAp() 42 : 43 forcedErrorState(false), 44 nextActionId(0), 45 nextTransId(0), 46 startState(0), 47 errState(0), 48 errTrans(0), 49 firstFinState(0), 50 numFinStates(0), 51 bAnyToStateActions(false), 52 bAnyFromStateActions(false), 53 bAnyRegActions(false), 54 bAnyEofActions(false), 55 bAnyEofTrans(false), 56 bAnyActionGotos(false), 57 bAnyActionCalls(false), 58 bAnyActionRets(false), 59 bAnyActionByValControl(false), 60 bAnyRegActionRets(false), 61 bAnyRegActionByValControl(false), 62 bAnyRegNextStmt(false), 63 bAnyRegCurStateRef(false), 64 bAnyRegBreak(false), 65 bAnyConditions(false) 66 { 67 } 68 69 /* Does the machine have any actions. */ 70 bool RedFsmAp::anyActions() 71 { 72 return actionMap.length() > 0; 73 } 74 75 void RedFsmAp::depthFirstOrdering( RedStateAp *state ) 76 { 77 /* Nothing to do if the state is already on the list. */ 78 if ( state->onStateList ) 79 return; 80 81 /* Doing depth first, put state on the list. */ 82 state->onStateList = true; 83 stateList.append( state ); 84 85 /* At this point transitions should only be in ranges. */ 86 assert( state->outSingle.length() == 0 ); 87 assert( state->defTrans == 0 ); 88 89 /* Recurse on everything ranges. */ 90 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) { 91 if ( rtel->value->targ != 0 ) 92 depthFirstOrdering( rtel->value->targ ); 93 } 94 } 95 96 /* Ordering states by transition connections. */ 97 void RedFsmAp::depthFirstOrdering() 98 { 99 /* Init on state list flags. */ 100 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) 101 st->onStateList = false; 102 103 /* Clear out the state list, we will rebuild it. */ 104 int stateListLen = stateList.length(); 105 stateList.abandon(); 106 107 /* Add back to the state list from the start state and all other entry 108 * points. */ 109 if ( startState != 0 ) 110 depthFirstOrdering( startState ); 111 for ( RedStateSet::Iter en = entryPoints; en.lte(); en++ ) 112 depthFirstOrdering( *en ); 113 if ( forcedErrorState ) 114 depthFirstOrdering( errState ); 115 116 /* Make sure we put everything back on. */ 117 assert( stateListLen == stateList.length() ); 118 } 119 120 /* Assign state ids by appearance in the state list. */ 121 void RedFsmAp::sequentialStateIds() 122 { 123 /* Table based machines depend on the state numbers starting at zero. */ 124 nextStateId = 0; 125 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) 126 st->id = nextStateId++; 127 } 128 129 /* Stable sort the states by final state status. */ 130 void RedFsmAp::sortStatesByFinal() 131 { 132 /* Move forward through the list and throw final states onto the end. */ 133 RedStateAp *state = 0; 134 RedStateAp *next = stateList.head; 135 RedStateAp *last = stateList.tail; 136 while ( state != last ) { 137 /* Move forward and load up the next. */ 138 state = next; 139 next = state->next; 140 141 /* Throw to the end? */ 142 if ( state->isFinal ) { 143 stateList.detach( state ); 144 stateList.append( state ); 145 } 146 } 147 } 148 149 /* Assign state ids by final state state status. */ 150 void RedFsmAp::sortStateIdsByFinal() 151 { 152 /* Table based machines depend on this starting at zero. */ 153 nextStateId = 0; 154 155 /* First pass to assign non final ids. */ 156 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 157 if ( ! st->isFinal ) 158 st->id = nextStateId++; 159 } 160 161 /* Second pass to assign final ids. */ 162 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 163 if ( st->isFinal ) 164 st->id = nextStateId++; 165 } 166 } 167 168 struct CmpStateById 169 { 170 static int compare( RedStateAp *st1, RedStateAp *st2 ) 171 { 172 if ( st1->id < st2->id ) 173 return -1; 174 else if ( st1->id > st2->id ) 175 return 1; 176 else 177 return 0; 178 } 179 }; 180 181 void RedFsmAp::sortByStateId() 182 { 183 /* Make the array. */ 184 int pos = 0; 185 RedStateAp **ptrList = new RedStateAp*[stateList.length()]; 186 for ( RedStateList::Iter st = stateList; st.lte(); st++, pos++ ) 187 ptrList[pos] = st; 188 189 MergeSort<RedStateAp*, CmpStateById> mergeSort; 190 mergeSort.sort( ptrList, stateList.length() ); 191 192 stateList.abandon(); 193 for ( int st = 0; st < pos; st++ ) 194 stateList.append( ptrList[st] ); 195 196 delete[] ptrList; 197 } 198 199 /* Find the final state with the lowest id. */ 200 void RedFsmAp::findFirstFinState() 201 { 202 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 203 if ( st->isFinal && (firstFinState == 0 || st->id < firstFinState->id) ) 204 firstFinState = st; 205 } 206 } 207 208 void RedFsmAp::assignActionLocs() 209 { 210 int nextLocation = 0; 211 for ( GenActionTableMap::Iter act = actionMap; act.lte(); act++ ) { 212 /* Store the loc, skip over the array and a null terminator. */ 213 act->location = nextLocation; 214 nextLocation += act->key.length() + 1; 215 } 216 } 217 218 /* Check if we can extend the current range by displacing any ranges 219 * ahead to the singles. */ 220 bool RedFsmAp::canExtend( const RedTransList &list, int pos ) 221 { 222 /* Get the transition that we want to extend. */ 223 RedTransAp *extendTrans = list[pos].value; 224 225 /* Look ahead in the transition list. */ 226 for ( int next = pos + 1; next < list.length(); pos++, next++ ) { 227 /* If they are not continuous then cannot extend. */ 228 Key nextKey = list[next].lowKey; 229 nextKey.decrement(); 230 if ( list[pos].highKey != nextKey ) 231 break; 232 233 /* Check for the extenstion property. */ 234 if ( extendTrans == list[next].value ) 235 return true; 236 237 /* If the span of the next element is more than one, then don't keep 238 * checking, it won't be moved to single. */ 239 unsigned long long nextSpan = keyOps->span( list[next].lowKey, list[next].highKey ); 240 if ( nextSpan > 1 ) 241 break; 242 } 243 return false; 244 } 245 246 /* Move ranges to the singles list. */ 247 void RedFsmAp::moveTransToSingle( RedStateAp *state ) 248 { 249 RedTransList &range = state->outRange; 250 RedTransList &single = state->outSingle; 251 for ( int rpos = 0; rpos < range.length(); ) { 252 /* Check if this is a range we can extend. */ 253 if ( canExtend( range, rpos ) ) { 254 /* Transfer singles over. */ 255 while ( range[rpos].value != range[rpos+1].value ) { 256 /* Transfer the range to single. */ 257 single.append( range[rpos+1] ); 258 range.remove( rpos+1 ); 259 } 260 261 /* Extend. */ 262 range[rpos].highKey = range[rpos+1].highKey; 263 range.remove( rpos+1 ); 264 } 265 /* Maybe move it to the singles. */ 266 else if ( keyOps->span( range[rpos].lowKey, range[rpos].highKey ) == 1 ) { 267 single.append( range[rpos] ); 268 range.remove( rpos ); 269 } 270 else { 271 /* Keeping it in the ranges. */ 272 rpos += 1; 273 } 274 } 275 } 276 277 /* Look through ranges and choose suitable single character transitions. */ 278 void RedFsmAp::chooseSingle() 279 { 280 /* Loop the states. */ 281 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 282 /* Rewrite the transition list taking out the suitable single 283 * transtions. */ 284 moveTransToSingle( st ); 285 } 286 } 287 288 void RedFsmAp::makeFlat() 289 { 290 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 291 if ( st->stateCondList.length() == 0 ) { 292 st->condLowKey = 0; 293 st->condHighKey = 0; 294 } 295 else { 296 st->condLowKey = st->stateCondList.head->lowKey; 297 st->condHighKey = st->stateCondList.tail->highKey; 298 299 unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey ); 300 st->condList = new GenCondSpace*[ span ]; 301 memset( st->condList, 0, sizeof(GenCondSpace*)*span ); 302 303 for ( GenStateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ ) { 304 unsigned long long base, trSpan; 305 base = keyOps->span( st->condLowKey, sci->lowKey )-1; 306 trSpan = keyOps->span( sci->lowKey, sci->highKey ); 307 for ( unsigned long long pos = 0; pos < trSpan; pos++ ) 308 st->condList[base+pos] = sci->condSpace; 309 } 310 } 311 312 if ( st->outRange.length() == 0 ) { 313 st->lowKey = st->highKey = 0; 314 st->transList = 0; 315 } 316 else { 317 st->lowKey = st->outRange[0].lowKey; 318 st->highKey = st->outRange[st->outRange.length()-1].highKey; 319 unsigned long long span = keyOps->span( st->lowKey, st->highKey ); 320 st->transList = new RedTransAp*[ span ]; 321 memset( st->transList, 0, sizeof(RedTransAp*)*span ); 322 323 for ( RedTransList::Iter trans = st->outRange; trans.lte(); trans++ ) { 324 unsigned long long base, trSpan; 325 base = keyOps->span( st->lowKey, trans->lowKey )-1; 326 trSpan = keyOps->span( trans->lowKey, trans->highKey ); 327 for ( unsigned long long pos = 0; pos < trSpan; pos++ ) 328 st->transList[base+pos] = trans->value; 329 } 330 331 /* Fill in the gaps with the default transition. */ 332 for ( unsigned long long pos = 0; pos < span; pos++ ) { 333 if ( st->transList[pos] == 0 ) 334 st->transList[pos] = st->defTrans; 335 } 336 } 337 } 338 } 339 340 341 /* A default transition has been picked, move it from the outRange to the 342 * default pointer. */ 343 void RedFsmAp::moveToDefault( RedTransAp *defTrans, RedStateAp *state ) 344 { 345 /* Rewrite the outRange, omitting any ranges that use 346 * the picked default. */ 347 RedTransList outRange; 348 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) { 349 /* If it does not take the default, copy it over. */ 350 if ( rtel->value != defTrans ) 351 outRange.append( *rtel ); 352 } 353 354 /* Save off the range we just created into the state's range. */ 355 state->outRange.transfer( outRange ); 356 357 /* Store the default. */ 358 state->defTrans = defTrans; 359 } 360 361 bool RedFsmAp::alphabetCovered( RedTransList &outRange ) 362 { 363 /* Cannot cover without any out ranges. */ 364 if ( outRange.length() == 0 ) 365 return false; 366 367 /* If the first range doesn't start at the the lower bound then the 368 * alphabet is not covered. */ 369 RedTransList::Iter rtel = outRange; 370 if ( keyOps->minKey < rtel->lowKey ) 371 return false; 372 373 /* Check that every range is next to the previous one. */ 374 rtel.increment(); 375 for ( ; rtel.lte(); rtel++ ) { 376 Key highKey = rtel[-1].highKey; 377 highKey.increment(); 378 if ( highKey != rtel->lowKey ) 379 return false; 380 } 381 382 /* The last must extend to the upper bound. */ 383 RedTransEl *last = &outRange[outRange.length()-1]; 384 if ( last->highKey < keyOps->maxKey ) 385 return false; 386 387 return true; 388 } 389 390 RedTransAp *RedFsmAp::chooseDefaultSpan( RedStateAp *state ) 391 { 392 /* Make a set of transitions from the outRange. */ 393 RedTransSet stateTransSet; 394 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) 395 stateTransSet.insert( rtel->value ); 396 397 /* For each transition in the find how many alphabet characters the 398 * transition spans. */ 399 unsigned long long *span = new unsigned long long[stateTransSet.length()]; 400 memset( span, 0, sizeof(unsigned long long) * stateTransSet.length() ); 401 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) { 402 /* Lookup the transition in the set. */ 403 RedTransAp **inSet = stateTransSet.find( rtel->value ); 404 int pos = inSet - stateTransSet.data; 405 span[pos] += keyOps->span( rtel->lowKey, rtel->highKey ); 406 } 407 408 /* Find the max span, choose it for making the default. */ 409 RedTransAp *maxTrans = 0; 410 unsigned long long maxSpan = 0; 411 for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) { 412 if ( span[rtel.pos()] > maxSpan ) { 413 maxSpan = span[rtel.pos()]; 414 maxTrans = *rtel; 415 } 416 } 417 418 delete[] span; 419 return maxTrans; 420 } 421 422 /* Pick default transitions from ranges for the states. */ 423 void RedFsmAp::chooseDefaultSpan() 424 { 425 /* Loop the states. */ 426 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 427 /* Only pick a default transition if the alphabet is covered. This 428 * avoids any transitions in the out range that go to error and avoids 429 * the need for an ERR state. */ 430 if ( alphabetCovered( st->outRange ) ) { 431 /* Pick a default transition by largest span. */ 432 RedTransAp *defTrans = chooseDefaultSpan( st ); 433 434 /* Rewrite the transition list taking out the transition we picked 435 * as the default and store the default. */ 436 moveToDefault( defTrans, st ); 437 } 438 } 439 } 440 441 RedTransAp *RedFsmAp::chooseDefaultGoto( RedStateAp *state ) 442 { 443 /* Make a set of transitions from the outRange. */ 444 RedTransSet stateTransSet; 445 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) { 446 if ( rtel->value->targ == state->next ) 447 return rtel->value; 448 } 449 return 0; 450 } 451 452 void RedFsmAp::chooseDefaultGoto() 453 { 454 /* Loop the states. */ 455 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 456 /* Pick a default transition. */ 457 RedTransAp *defTrans = chooseDefaultGoto( st ); 458 if ( defTrans == 0 ) 459 defTrans = chooseDefaultSpan( st ); 460 461 /* Rewrite the transition list taking out the transition we picked 462 * as the default and store the default. */ 463 moveToDefault( defTrans, st ); 464 } 465 } 466 467 RedTransAp *RedFsmAp::chooseDefaultNumRanges( RedStateAp *state ) 468 { 469 /* Make a set of transitions from the outRange. */ 470 RedTransSet stateTransSet; 471 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) 472 stateTransSet.insert( rtel->value ); 473 474 /* For each transition in the find how many ranges use the transition. */ 475 int *numRanges = new int[stateTransSet.length()]; 476 memset( numRanges, 0, sizeof(int) * stateTransSet.length() ); 477 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) { 478 /* Lookup the transition in the set. */ 479 RedTransAp **inSet = stateTransSet.find( rtel->value ); 480 numRanges[inSet - stateTransSet.data] += 1; 481 } 482 483 /* Find the max number of ranges. */ 484 RedTransAp *maxTrans = 0; 485 int maxNumRanges = 0; 486 for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) { 487 if ( numRanges[rtel.pos()] > maxNumRanges ) { 488 maxNumRanges = numRanges[rtel.pos()]; 489 maxTrans = *rtel; 490 } 491 } 492 493 delete[] numRanges; 494 return maxTrans; 495 } 496 497 void RedFsmAp::chooseDefaultNumRanges() 498 { 499 /* Loop the states. */ 500 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 501 /* Pick a default transition. */ 502 RedTransAp *defTrans = chooseDefaultNumRanges( st ); 503 504 /* Rewrite the transition list taking out the transition we picked 505 * as the default and store the default. */ 506 moveToDefault( defTrans, st ); 507 } 508 } 509 510 RedTransAp *RedFsmAp::getErrorTrans( ) 511 { 512 /* If the error trans has not been made aready, make it. */ 513 if ( errTrans == 0 ) { 514 /* This insert should always succeed since no transition created by 515 * the user can point to the error state. */ 516 errTrans = new RedTransAp( getErrorState(), 0, nextTransId++ ); 517 RedTransAp *inRes = transSet.insert( errTrans ); 518 assert( inRes != 0 ); 519 } 520 return errTrans; 521 } 522 523 RedStateAp *RedFsmAp::getErrorState() 524 { 525 /* Something went wrong. An error state is needed but one was not supplied 526 * by the frontend. */ 527 assert( errState != 0 ); 528 return errState; 529 } 530 531 532 RedTransAp *RedFsmAp::allocateTrans( RedStateAp *targ, RedAction *action ) 533 { 534 /* Create a reduced trans and look for it in the transiton set. */ 535 RedTransAp redTrans( targ, action, 0 ); 536 RedTransAp *inDict = transSet.find( &redTrans ); 537 if ( inDict == 0 ) { 538 inDict = new RedTransAp( targ, action, nextTransId++ ); 539 transSet.insert( inDict ); 540 } 541 return inDict; 542 } 543 544 void RedFsmAp::partitionFsm( int nparts ) 545 { 546 /* At this point the states are ordered by a depth-first traversal. We 547 * will allocate to partitions based on this ordering. */ 548 this->nParts = nparts; 549 int partSize = stateList.length() / nparts; 550 int remainder = stateList.length() % nparts; 551 int numInPart = partSize; 552 int partition = 0; 553 if ( remainder-- > 0 ) 554 numInPart += 1; 555 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 556 st->partition = partition; 557 558 numInPart -= 1; 559 if ( numInPart == 0 ) { 560 partition += 1; 561 numInPart = partSize; 562 if ( remainder-- > 0 ) 563 numInPart += 1; 564 } 565 } 566 } 567 568 void RedFsmAp::setInTrans() 569 { 570 /* First pass counts the number of transitions. */ 571 for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ ) 572 trans->targ->numInTrans += 1; 573 574 /* Pass over states to allocate the needed memory. Reset the counts so we 575 * can use them as the current size. */ 576 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) { 577 st->inTrans = new RedTransAp*[st->numInTrans]; 578 st->numInTrans = 0; 579 } 580 581 /* Second pass over transitions copies pointers into the in trans list. */ 582 for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ ) 583 trans->targ->inTrans[trans->targ->numInTrans++] = trans; 584 }