1/* 2 * NFA utilities. 3 * This file is #included by regcomp.c. 4 * 5 * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. 6 * 7 * Development of this software was funded, in part, by Cray Research Inc., 8 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics 9 * Corporation, none of whom are responsible for the results. The author 10 * thanks all of them. 11 * 12 * Redistribution and use in source and binary forms -- with or without 13 * modification -- are permitted for any purpose, provided that 14 * redistributions in source form retain this entire copyright notice and 15 * indicate the origin and nature of any modifications. 16 * 17 * I'd appreciate being given credit for this package in the documentation 18 * of software which uses it, but that is not a requirement. 19 * 20 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 21 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 22 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 23 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 * 31 * 32 * 33 * One or two things that technically ought to be in here 34 * are actually in color.c, thanks to some incestuous relationships in 35 * the color chains. 36 */ 37 38#define NISERR() VISERR(nfa->v) 39#define NERR(e) VERR(nfa->v, (e)) 40 41 42/* 43 - newnfa - set up an NFA 44 ^ static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *); 45 */ 46static struct nfa * /* the NFA, or NULL */ 47newnfa(v, cm, parent) 48struct vars *v; 49struct colormap *cm; 50struct nfa *parent; /* NULL if primary NFA */ 51{ 52 struct nfa *nfa; 53 54 nfa = (struct nfa *)MALLOC(sizeof(struct nfa)); 55 if (nfa == NULL) 56 return NULL; 57 58 nfa->states = NULL; 59 nfa->slast = NULL; 60 nfa->free = NULL; 61 nfa->nstates = 0; 62 nfa->cm = cm; 63 nfa->v = v; 64 nfa->bos[0] = nfa->bos[1] = COLORLESS; 65 nfa->eos[0] = nfa->eos[1] = COLORLESS; 66 nfa->post = newfstate(nfa, '@'); /* number 0 */ 67 nfa->pre = newfstate(nfa, '>'); /* number 1 */ 68 nfa->parent = parent; 69 70 nfa->init = newstate(nfa); /* may become invalid later */ 71 nfa->final = newstate(nfa); 72 if (ISERR()) { 73 freenfa(nfa); 74 return NULL; 75 } 76 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init); 77 newarc(nfa, '^', 1, nfa->pre, nfa->init); 78 newarc(nfa, '^', 0, nfa->pre, nfa->init); 79 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post); 80 newarc(nfa, '$', 1, nfa->final, nfa->post); 81 newarc(nfa, '$', 0, nfa->final, nfa->post); 82 83 if (ISERR()) { 84 freenfa(nfa); 85 return NULL; 86 } 87 return nfa; 88} 89 90/* 91 - freenfa - free an entire NFA 92 ^ static VOID freenfa(struct nfa *); 93 */ 94static VOID 95freenfa(nfa) 96struct nfa *nfa; 97{ 98 struct state *s; 99 100 while ((s = nfa->states) != NULL) { 101 s->nins = s->nouts = 0; /* don't worry about arcs */ 102 freestate(nfa, s); 103 } 104 while ((s = nfa->free) != NULL) { 105 nfa->free = s->next; 106 destroystate(nfa, s); 107 } 108 109 nfa->slast = NULL; 110 nfa->nstates = -1; 111 nfa->pre = NULL; 112 nfa->post = NULL; 113 FREE(nfa); 114} 115 116/* 117 - newstate - allocate an NFA state, with zero flag value 118 ^ static struct state *newstate(struct nfa *); 119 */ 120static struct state * /* NULL on error */ 121newstate(nfa) 122struct nfa *nfa; 123{ 124 struct state *s; 125 126 if (nfa->free != NULL) { 127 s = nfa->free; 128 nfa->free = s->next; 129 } else { 130 s = (struct state *)MALLOC(sizeof(struct state)); 131 if (s == NULL) { 132 NERR(REG_ESPACE); 133 return NULL; 134 } 135 s->oas.next = NULL; 136 s->free = NULL; 137 s->noas = 0; 138 } 139 140 assert(nfa->nstates >= 0); 141 s->no = nfa->nstates++; 142 s->flag = 0; 143 if (nfa->states == NULL) 144 nfa->states = s; 145 s->nins = 0; 146 s->ins = NULL; 147 s->nouts = 0; 148 s->outs = NULL; 149 s->tmp = NULL; 150 s->next = NULL; 151 if (nfa->slast != NULL) { 152 assert(nfa->slast->next == NULL); 153 nfa->slast->next = s; 154 } 155 s->prev = nfa->slast; 156 nfa->slast = s; 157 return s; 158} 159 160/* 161 - newfstate - allocate an NFA state with a specified flag value 162 ^ static struct state *newfstate(struct nfa *, int flag); 163 */ 164static struct state * /* NULL on error */ 165newfstate(nfa, flag) 166struct nfa *nfa; 167int flag; 168{ 169 struct state *s; 170 171 s = newstate(nfa); 172 if (s != NULL) 173 s->flag = (char)flag; 174 return s; 175} 176 177/* 178 - dropstate - delete a state's inarcs and outarcs and free it 179 ^ static VOID dropstate(struct nfa *, struct state *); 180 */ 181static VOID 182dropstate(nfa, s) 183struct nfa *nfa; 184struct state *s; 185{ 186 struct arc *a; 187 188 while ((a = s->ins) != NULL) 189 freearc(nfa, a); 190 while ((a = s->outs) != NULL) 191 freearc(nfa, a); 192 freestate(nfa, s); 193} 194 195/* 196 - freestate - free a state, which has no in-arcs or out-arcs 197 ^ static VOID freestate(struct nfa *, struct state *); 198 */ 199static VOID 200freestate(nfa, s) 201struct nfa *nfa; 202struct state *s; 203{ 204 assert(s != NULL); 205 assert(s->nins == 0 && s->nouts == 0); 206 207 s->no = FREESTATE; 208 s->flag = 0; 209 if (s->next != NULL) 210 s->next->prev = s->prev; 211 else { 212 assert(s == nfa->slast); 213 nfa->slast = s->prev; 214 } 215 if (s->prev != NULL) 216 s->prev->next = s->next; 217 else { 218 assert(s == nfa->states); 219 nfa->states = s->next; 220 } 221 s->prev = NULL; 222 s->next = nfa->free; /* don't delete it, put it on the free list */ 223 nfa->free = s; 224} 225 226/* 227 - destroystate - really get rid of an already-freed state 228 ^ static VOID destroystate(struct nfa *, struct state *); 229 */ 230static VOID 231destroystate(nfa, s) 232struct nfa *nfa; 233struct state *s; 234{ 235 struct arcbatch *ab; 236 struct arcbatch *abnext; 237 238 assert(s->no == FREESTATE); 239 for (ab = s->oas.next; ab != NULL; ab = abnext) { 240 abnext = ab->next; 241 FREE(ab); 242 } 243 s->ins = NULL; 244 s->outs = NULL; 245 s->next = NULL; 246 FREE(s); 247} 248 249/* 250 - newarc - set up a new arc within an NFA 251 ^ static VOID newarc(struct nfa *, int, pcolor, struct state *, 252 ^ struct state *); 253 */ 254static VOID 255newarc(nfa, t, co, from, to) 256struct nfa *nfa; 257int t; 258pcolor co; 259struct state *from; 260struct state *to; 261{ 262 struct arc *a; 263 264 assert(from != NULL && to != NULL); 265 266 /* check for duplicates */ 267 for (a = from->outs; a != NULL; a = a->outchain) 268 if (a->to == to && a->co == co && a->type == t) 269 return; 270 271 a = allocarc(nfa, from); 272 if (NISERR()) 273 return; 274 assert(a != NULL); 275 276 a->type = t; 277 a->co = (color)co; 278 a->to = to; 279 a->from = from; 280 281 /* 282 * Put the new arc on the beginning, not the end, of the chains. 283 * Not only is this easier, it has the very useful side effect that 284 * deleting the most-recently-added arc is the cheapest case rather 285 * than the most expensive one. 286 */ 287 a->inchain = to->ins; 288 to->ins = a; 289 a->outchain = from->outs; 290 from->outs = a; 291 292 from->nouts++; 293 to->nins++; 294 295 if (COLORED(a) && nfa->parent == NULL) 296 colorchain(nfa->cm, a); 297 298 return; 299} 300 301/* 302 - allocarc - allocate a new out-arc within a state 303 ^ static struct arc *allocarc(struct nfa *, struct state *); 304 */ 305static struct arc * /* NULL for failure */ 306allocarc(nfa, s) 307struct nfa *nfa; 308struct state *s; 309{ 310 struct arc *a; 311 struct arcbatch *new; 312 int i; 313 314 /* shortcut */ 315 if (s->free == NULL && s->noas < ABSIZE) { 316 a = &s->oas.a[s->noas]; 317 s->noas++; 318 return a; 319 } 320 321 /* if none at hand, get more */ 322 if (s->free == NULL) { 323 new = (struct arcbatch *)MALLOC(sizeof(struct arcbatch)); 324 if (new == NULL) { 325 NERR(REG_ESPACE); 326 return NULL; 327 } 328 new->next = s->oas.next; 329 s->oas.next = new; 330 331 for (i = 0; i < ABSIZE; i++) { 332 new->a[i].type = 0; 333 new->a[i].freechain = &new->a[i+1]; 334 } 335 new->a[ABSIZE-1].freechain = NULL; 336 s->free = &new->a[0]; 337 } 338 assert(s->free != NULL); 339 340 a = s->free; 341 s->free = a->freechain; 342 return a; 343} 344 345/* 346 - freearc - free an arc 347 ^ static VOID freearc(struct nfa *, struct arc *); 348 */ 349static VOID 350freearc(nfa, victim) 351struct nfa *nfa; 352struct arc *victim; 353{ 354 struct state *from = victim->from; 355 struct state *to = victim->to; 356 struct arc *a; 357 358 assert(victim->type != 0); 359 360 /* take it off color chain if necessary */ 361 if (COLORED(victim) && nfa->parent == NULL) 362 uncolorchain(nfa->cm, victim); 363 364 /* take it off source's out-chain */ 365 assert(from != NULL); 366 assert(from->outs != NULL); 367 a = from->outs; 368 if (a == victim) /* simple case: first in chain */ 369 from->outs = victim->outchain; 370 else { 371 for (; a != NULL && a->outchain != victim; a = a->outchain) 372 continue; 373 assert(a != NULL); 374 a->outchain = victim->outchain; 375 } 376 from->nouts--; 377 378 /* take it off target's in-chain */ 379 assert(to != NULL); 380 assert(to->ins != NULL); 381 a = to->ins; 382 if (a == victim) /* simple case: first in chain */ 383 to->ins = victim->inchain; 384 else { 385 for (; a != NULL && a->inchain != victim; a = a->inchain) 386 continue; 387 assert(a != NULL); 388 a->inchain = victim->inchain; 389 } 390 to->nins--; 391 392 /* clean up and place on free list */ 393 victim->type = 0; 394 victim->from = NULL; /* precautions... */ 395 victim->to = NULL; 396 victim->inchain = NULL; 397 victim->outchain = NULL; 398 victim->freechain = from->free; 399 from->free = victim; 400} 401 402/* 403 - findarc - find arc, if any, from given source with given type and color 404 * If there is more than one such arc, the result is random. 405 ^ static struct arc *findarc(struct state *, int, pcolor); 406 */ 407static struct arc * 408findarc(s, type, co) 409struct state *s; 410int type; 411pcolor co; 412{ 413 struct arc *a; 414 415 for (a = s->outs; a != NULL; a = a->outchain) 416 if (a->type == type && a->co == co) 417 return a; 418 return NULL; 419} 420 421/* 422 - cparc - allocate a new arc within an NFA, copying details from old one 423 ^ static VOID cparc(struct nfa *, struct arc *, struct state *, 424 ^ struct state *); 425 */ 426static VOID 427cparc(nfa, oa, from, to) 428struct nfa *nfa; 429struct arc *oa; 430struct state *from; 431struct state *to; 432{ 433 newarc(nfa, oa->type, oa->co, from, to); 434} 435 436/* 437 - moveins - move all in arcs of a state to another state 438 * You might think this could be done better by just updating the 439 * existing arcs, and you would be right if it weren't for the desire 440 * for duplicate suppression, which makes it easier to just make new 441 * ones to exploit the suppression built into newarc. 442 ^ static VOID moveins(struct nfa *, struct state *, struct state *); 443 */ 444static VOID 445moveins(nfa, old, new) 446struct nfa *nfa; 447struct state *old; 448struct state *new; 449{ 450 struct arc *a; 451 452 assert(old != new); 453 454 while ((a = old->ins) != NULL) { 455 cparc(nfa, a, a->from, new); 456 freearc(nfa, a); 457 } 458 assert(old->nins == 0); 459 assert(old->ins == NULL); 460} 461 462/* 463 - copyins - copy all in arcs of a state to another state 464 ^ static VOID copyins(struct nfa *, struct state *, struct state *); 465 */ 466static VOID 467copyins(nfa, old, new) 468struct nfa *nfa; 469struct state *old; 470struct state *new; 471{ 472 struct arc *a; 473 474 assert(old != new); 475 476 for (a = old->ins; a != NULL; a = a->inchain) 477 cparc(nfa, a, a->from, new); 478} 479 480/* 481 - moveouts - move all out arcs of a state to another state 482 ^ static VOID moveouts(struct nfa *, struct state *, struct state *); 483 */ 484static VOID 485moveouts(nfa, old, new) 486struct nfa *nfa; 487struct state *old; 488struct state *new; 489{ 490 struct arc *a; 491 492 assert(old != new); 493 494 while ((a = old->outs) != NULL) { 495 cparc(nfa, a, new, a->to); 496 freearc(nfa, a); 497 } 498} 499 500/* 501 - copyouts - copy all out arcs of a state to another state 502 ^ static VOID copyouts(struct nfa *, struct state *, struct state *); 503 */ 504static VOID 505copyouts(nfa, old, new) 506struct nfa *nfa; 507struct state *old; 508struct state *new; 509{ 510 struct arc *a; 511 512 assert(old != new); 513 514 for (a = old->outs; a != NULL; a = a->outchain) 515 cparc(nfa, a, new, a->to); 516} 517 518/* 519 - cloneouts - copy out arcs of a state to another state pair, modifying type 520 ^ static VOID cloneouts(struct nfa *, struct state *, struct state *, 521 ^ struct state *, int); 522 */ 523static VOID 524cloneouts(nfa, old, from, to, type) 525struct nfa *nfa; 526struct state *old; 527struct state *from; 528struct state *to; 529int type; 530{ 531 struct arc *a; 532 533 assert(old != from); 534 535 for (a = old->outs; a != NULL; a = a->outchain) 536 newarc(nfa, type, a->co, from, to); 537} 538 539/* 540 - delsub - delete a sub-NFA, updating subre pointers if necessary 541 * This uses a recursive traversal of the sub-NFA, marking already-seen 542 * states using their tmp pointer. 543 ^ static VOID delsub(struct nfa *, struct state *, struct state *); 544 */ 545static VOID 546delsub(nfa, lp, rp) 547struct nfa *nfa; 548struct state *lp; /* the sub-NFA goes from here... */ 549struct state *rp; /* ...to here, *not* inclusive */ 550{ 551 assert(lp != rp); 552 553 rp->tmp = rp; /* mark end */ 554 555 deltraverse(nfa, lp, lp); 556 assert(lp->nouts == 0 && rp->nins == 0); /* did the job */ 557 assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */ 558 559 rp->tmp = NULL; /* unmark end */ 560 lp->tmp = NULL; /* and begin, marked by deltraverse */ 561} 562 563/* 564 - deltraverse - the recursive heart of delsub 565 * This routine's basic job is to destroy all out-arcs of the state. 566 ^ static VOID deltraverse(struct nfa *, struct state *, struct state *); 567 */ 568static VOID 569deltraverse(nfa, leftend, s) 570struct nfa *nfa; 571struct state *leftend; 572struct state *s; 573{ 574 struct arc *a; 575 struct state *to; 576 577 if (s->nouts == 0) 578 return; /* nothing to do */ 579 if (s->tmp != NULL) 580 return; /* already in progress */ 581 582 s->tmp = s; /* mark as in progress */ 583 584 while ((a = s->outs) != NULL) { 585 to = a->to; 586 deltraverse(nfa, leftend, to); 587 assert(to->nouts == 0 || to->tmp != NULL); 588 freearc(nfa, a); 589 if (to->nins == 0 && to->tmp == NULL) { 590 assert(to->nouts == 0); 591 freestate(nfa, to); 592 } 593 } 594 595 assert(s->no != FREESTATE); /* we're still here */ 596 assert(s == leftend || s->nins != 0); /* and still reachable */ 597 assert(s->nouts == 0); /* but have no outarcs */ 598 599 s->tmp = NULL; /* we're done here */ 600} 601 602/* 603 - dupnfa - duplicate sub-NFA 604 * Another recursive traversal, this time using tmp to point to duplicates 605 * as well as mark already-seen states. (You knew there was a reason why 606 * it's a state pointer, didn't you? :-)) 607 ^ static VOID dupnfa(struct nfa *, struct state *, struct state *, 608 ^ struct state *, struct state *); 609 */ 610static VOID 611dupnfa(nfa, start, stop, from, to) 612struct nfa *nfa; 613struct state *start; /* duplicate of subNFA starting here */ 614struct state *stop; /* and stopping here */ 615struct state *from; /* stringing duplicate from here */ 616struct state *to; /* to here */ 617{ 618 if (start == stop) { 619 newarc(nfa, EMPTY, 0, from, to); 620 return; 621 } 622 623 stop->tmp = to; 624 duptraverse(nfa, start, from); 625 /* done, except for clearing out the tmp pointers */ 626 627 stop->tmp = NULL; 628 cleartraverse(nfa, start); 629} 630 631/* 632 - duptraverse - recursive heart of dupnfa 633 ^ static VOID duptraverse(struct nfa *, struct state *, struct state *); 634 */ 635static VOID 636duptraverse(nfa, s, stmp) 637struct nfa *nfa; 638struct state *s; 639struct state *stmp; /* s's duplicate, or NULL */ 640{ 641 struct arc *a; 642 643 if (s->tmp != NULL) 644 return; /* already done */ 645 646 s->tmp = (stmp == NULL) ? newstate(nfa) : stmp; 647 if (s->tmp == NULL) { 648 assert(NISERR()); 649 return; 650 } 651 652 for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) { 653 duptraverse(nfa, a->to, (struct state *)NULL); 654 assert(a->to->tmp != NULL); 655 cparc(nfa, a, s->tmp, a->to->tmp); 656 } 657} 658 659/* 660 - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set 661 ^ static VOID cleartraverse(struct nfa *, struct state *); 662 */ 663static VOID 664cleartraverse(nfa, s) 665struct nfa *nfa; 666struct state *s; 667{ 668 struct arc *a; 669 670 if (s->tmp == NULL) 671 return; 672 s->tmp = NULL; 673 674 for (a = s->outs; a != NULL; a = a->outchain) 675 cleartraverse(nfa, a->to); 676} 677 678/* 679 - specialcolors - fill in special colors for an NFA 680 ^ static VOID specialcolors(struct nfa *); 681 */ 682static VOID 683specialcolors(nfa) 684struct nfa *nfa; 685{ 686 /* false colors for BOS, BOL, EOS, EOL */ 687 if (nfa->parent == NULL) { 688 nfa->bos[0] = pseudocolor(nfa->cm); 689 nfa->bos[1] = pseudocolor(nfa->cm); 690 nfa->eos[0] = pseudocolor(nfa->cm); 691 nfa->eos[1] = pseudocolor(nfa->cm); 692 } else { 693 assert(nfa->parent->bos[0] != COLORLESS); 694 nfa->bos[0] = nfa->parent->bos[0]; 695 assert(nfa->parent->bos[1] != COLORLESS); 696 nfa->bos[1] = nfa->parent->bos[1]; 697 assert(nfa->parent->eos[0] != COLORLESS); 698 nfa->eos[0] = nfa->parent->eos[0]; 699 assert(nfa->parent->eos[1] != COLORLESS); 700 nfa->eos[1] = nfa->parent->eos[1]; 701 } 702} 703 704/* 705 - optimize - optimize an NFA 706 ^ static long optimize(struct nfa *, FILE *); 707 */ 708static long /* re_info bits */ 709optimize(nfa, f) 710struct nfa *nfa; 711FILE *f; /* for debug output; NULL none */ 712{ 713 int verbose = (f != NULL) ? 1 : 0; 714 715 if (verbose) 716 fprintf(f, "\ninitial cleanup:\n"); 717 cleanup(nfa); /* may simplify situation */ 718 if (verbose) 719 dumpnfa(nfa, f); 720 if (verbose) 721 fprintf(f, "\nempties:\n"); 722 fixempties(nfa, f); /* get rid of EMPTY arcs */ 723 if (verbose) 724 fprintf(f, "\nconstraints:\n"); 725 pullback(nfa, f); /* pull back constraints backward */ 726 pushfwd(nfa, f); /* push fwd constraints forward */ 727 if (verbose) 728 fprintf(f, "\nfinal cleanup:\n"); 729 cleanup(nfa); /* final tidying */ 730 return analyze(nfa); /* and analysis */ 731} 732 733/* 734 - pullback - pull back constraints backward to (with luck) eliminate them 735 ^ static VOID pullback(struct nfa *, FILE *); 736 */ 737static VOID 738pullback(nfa, f) 739struct nfa *nfa; 740FILE *f; /* for debug output; NULL none */ 741{ 742 struct state *s; 743 struct state *nexts; 744 struct arc *a; 745 struct arc *nexta; 746 int progress; 747 748 /* find and pull until there are no more */ 749 do { 750 progress = 0; 751 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) { 752 nexts = s->next; 753 for (a = s->outs; a != NULL && !NISERR(); a = nexta) { 754 nexta = a->outchain; 755 if (a->type == '^' || a->type == BEHIND) 756 if (pull(nfa, a)) 757 progress = 1; 758 assert(nexta == NULL || s->no != FREESTATE); 759 } 760 } 761 if (progress && f != NULL) 762 dumpnfa(nfa, f); 763 } while (progress && !NISERR()); 764 if (NISERR()) 765 return; 766 767 for (a = nfa->pre->outs; a != NULL; a = nexta) { 768 nexta = a->outchain; 769 if (a->type == '^') { 770 assert(a->co == 0 || a->co == 1); 771 newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to); 772 freearc(nfa, a); 773 } 774 } 775} 776 777/* 778 - pull - pull a back constraint backward past its source state 779 * A significant property of this function is that it deletes at most 780 * one state -- the constraint's from state -- and only if the constraint 781 * was that state's last outarc. 782 ^ static int pull(struct nfa *, struct arc *); 783 */ 784static int /* 0 couldn't, 1 could */ 785pull(nfa, con) 786struct nfa *nfa; 787struct arc *con; 788{ 789 struct state *from = con->from; 790 struct state *to = con->to; 791 struct arc *a; 792 struct arc *nexta; 793 struct state *s; 794 795 if (from == to) { /* circular constraint is pointless */ 796 freearc(nfa, con); 797 return 1; 798 } 799 if (from->flag) /* can't pull back beyond start */ 800 return 0; 801 if (from->nins == 0) { /* unreachable */ 802 freearc(nfa, con); 803 return 1; 804 } 805 806 /* first, clone from state if necessary to avoid other outarcs */ 807 if (from->nouts > 1) { 808 s = newstate(nfa); 809 if (NISERR()) 810 return 0; 811 assert(to != from); /* con is not an inarc */ 812 copyins(nfa, from, s); /* duplicate inarcs */ 813 cparc(nfa, con, s, to); /* move constraint arc */ 814 freearc(nfa, con); 815 from = s; 816 con = from->outs; 817 } 818 assert(from->nouts == 1); 819 820 /* propagate the constraint into the from state's inarcs */ 821 for (a = from->ins; a != NULL; a = nexta) { 822 nexta = a->inchain; 823 switch (combine(con, a)) { 824 case INCOMPATIBLE: /* destroy the arc */ 825 freearc(nfa, a); 826 break; 827 case SATISFIED: /* no action needed */ 828 break; 829 case COMPATIBLE: /* swap the two arcs, more or less */ 830 s = newstate(nfa); 831 if (NISERR()) 832 return 0; 833 cparc(nfa, a, s, to); /* anticipate move */ 834 cparc(nfa, con, a->from, s); 835 if (NISERR()) 836 return 0; 837 freearc(nfa, a); 838 break; 839 default: 840 assert(NOTREACHED); 841 break; 842 } 843 } 844 845 /* remaining inarcs, if any, incorporate the constraint */ 846 moveins(nfa, from, to); 847 dropstate(nfa, from); /* will free the constraint */ 848 return 1; 849} 850 851/* 852 - pushfwd - push forward constraints forward to (with luck) eliminate them 853 ^ static VOID pushfwd(struct nfa *, FILE *); 854 */ 855static VOID 856pushfwd(nfa, f) 857struct nfa *nfa; 858FILE *f; /* for debug output; NULL none */ 859{ 860 struct state *s; 861 struct state *nexts; 862 struct arc *a; 863 struct arc *nexta; 864 int progress; 865 866 /* find and push until there are no more */ 867 do { 868 progress = 0; 869 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) { 870 nexts = s->next; 871 for (a = s->ins; a != NULL && !NISERR(); a = nexta) { 872 nexta = a->inchain; 873 if (a->type == '$' || a->type == AHEAD) 874 if (push(nfa, a)) 875 progress = 1; 876 assert(nexta == NULL || s->no != FREESTATE); 877 } 878 } 879 if (progress && f != NULL) 880 dumpnfa(nfa, f); 881 } while (progress && !NISERR()); 882 if (NISERR()) 883 return; 884 885 for (a = nfa->post->ins; a != NULL; a = nexta) { 886 nexta = a->inchain; 887 if (a->type == '$') { 888 assert(a->co == 0 || a->co == 1); 889 newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to); 890 freearc(nfa, a); 891 } 892 } 893} 894 895/* 896 - push - push a forward constraint forward past its destination state 897 * A significant property of this function is that it deletes at most 898 * one state -- the constraint's to state -- and only if the constraint 899 * was that state's last inarc. 900 ^ static int push(struct nfa *, struct arc *); 901 */ 902static int /* 0 couldn't, 1 could */ 903push(nfa, con) 904struct nfa *nfa; 905struct arc *con; 906{ 907 struct state *from = con->from; 908 struct state *to = con->to; 909 struct arc *a; 910 struct arc *nexta; 911 struct state *s; 912 913 if (to == from) { /* circular constraint is pointless */ 914 freearc(nfa, con); 915 return 1; 916 } 917 if (to->flag) /* can't push forward beyond end */ 918 return 0; 919 if (to->nouts == 0) { /* dead end */ 920 freearc(nfa, con); 921 return 1; 922 } 923 924 /* first, clone to state if necessary to avoid other inarcs */ 925 if (to->nins > 1) { 926 s = newstate(nfa); 927 if (NISERR()) 928 return 0; 929 copyouts(nfa, to, s); /* duplicate outarcs */ 930 cparc(nfa, con, from, s); /* move constraint */ 931 freearc(nfa, con); 932 to = s; 933 con = to->ins; 934 } 935 assert(to->nins == 1); 936 937 /* propagate the constraint into the to state's outarcs */ 938 for (a = to->outs; a != NULL; a = nexta) { 939 nexta = a->outchain; 940 switch (combine(con, a)) { 941 case INCOMPATIBLE: /* destroy the arc */ 942 freearc(nfa, a); 943 break; 944 case SATISFIED: /* no action needed */ 945 break; 946 case COMPATIBLE: /* swap the two arcs, more or less */ 947 s = newstate(nfa); 948 if (NISERR()) 949 return 0; 950 cparc(nfa, con, s, a->to); /* anticipate move */ 951 cparc(nfa, a, from, s); 952 if (NISERR()) 953 return 0; 954 freearc(nfa, a); 955 break; 956 default: 957 assert(NOTREACHED); 958 break; 959 } 960 } 961 962 /* remaining outarcs, if any, incorporate the constraint */ 963 moveouts(nfa, to, from); 964 dropstate(nfa, to); /* will free the constraint */ 965 return 1; 966} 967 968/* 969 - combine - constraint lands on an arc, what happens? 970 ^ #def INCOMPATIBLE 1 // destroys arc 971 ^ #def SATISFIED 2 // constraint satisfied 972 ^ #def COMPATIBLE 3 // compatible but not satisfied yet 973 ^ static int combine(struct arc *, struct arc *); 974 */ 975 976/* FIXME Required for CW 8 on Mac since it's not in limits.h */ 977#ifndef __CHAR_BIT__ 978#define __CHAR_BIT__ 8 979#endif 980 981 982static int 983combine(con, a) 984struct arc *con; 985struct arc *a; 986{ 987# define CA(ct,at) (((ct)<<CHAR_BIT) | (at)) 988 989 switch (CA(con->type, a->type)) { 990 case CA('^', PLAIN): /* newlines are handled separately */ 991 case CA('$', PLAIN): 992 return INCOMPATIBLE; 993 break; 994 case CA(AHEAD, PLAIN): /* color constraints meet colors */ 995 case CA(BEHIND, PLAIN): 996 if (con->co == a->co) 997 return SATISFIED; 998 return INCOMPATIBLE; 999 break; 1000 case CA('^', '^'): /* collision, similar constraints */ 1001 case CA('$', '$'): 1002 case CA(AHEAD, AHEAD): 1003 case CA(BEHIND, BEHIND): 1004 if (con->co == a->co) /* true duplication */ 1005 return SATISFIED; 1006 return INCOMPATIBLE; 1007 break; 1008 case CA('^', BEHIND): /* collision, dissimilar constraints */ 1009 case CA(BEHIND, '^'): 1010 case CA('$', AHEAD): 1011 case CA(AHEAD, '$'): 1012 return INCOMPATIBLE; 1013 break; 1014 case CA('^', '$'): /* constraints passing each other */ 1015 case CA('^', AHEAD): 1016 case CA(BEHIND, '$'): 1017 case CA(BEHIND, AHEAD): 1018 case CA('$', '^'): 1019 case CA('$', BEHIND): 1020 case CA(AHEAD, '^'): 1021 case CA(AHEAD, BEHIND): 1022 case CA('^', LACON): 1023 case CA(BEHIND, LACON): 1024 case CA('$', LACON): 1025 case CA(AHEAD, LACON): 1026 return COMPATIBLE; 1027 break; 1028 } 1029 assert(NOTREACHED); 1030 return INCOMPATIBLE; /* for benefit of blind compilers */ 1031} 1032 1033/* 1034 - fixempties - get rid of EMPTY arcs 1035 ^ static VOID fixempties(struct nfa *, FILE *); 1036 */ 1037static VOID 1038fixempties(nfa, f) 1039struct nfa *nfa; 1040FILE *f; /* for debug output; NULL none */ 1041{ 1042 struct state *s; 1043 struct state *nexts; 1044 struct arc *a; 1045 struct arc *nexta; 1046 int progress; 1047 1048 /* find and eliminate empties until there are no more */ 1049 do { 1050 progress = 0; 1051 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) { 1052 nexts = s->next; 1053 for (a = s->outs; a != NULL && !NISERR(); a = nexta) { 1054 nexta = a->outchain; 1055 if (a->type == EMPTY && unempty(nfa, a)) 1056 progress = 1; 1057 assert(nexta == NULL || s->no != FREESTATE); 1058 } 1059 } 1060 if (progress && f != NULL) 1061 dumpnfa(nfa, f); 1062 } while (progress && !NISERR()); 1063} 1064 1065/* 1066 - unempty - optimize out an EMPTY arc, if possible 1067 * Actually, as it stands this function always succeeds, but the return 1068 * value is kept with an eye on possible future changes. 1069 ^ static int unempty(struct nfa *, struct arc *); 1070 */ 1071static int /* 0 couldn't, 1 could */ 1072unempty(nfa, a) 1073struct nfa *nfa; 1074struct arc *a; 1075{ 1076 struct state *from = a->from; 1077 struct state *to = a->to; 1078 int usefrom; /* work on from, as opposed to to? */ 1079 1080 assert(a->type == EMPTY); 1081 assert(from != nfa->pre && to != nfa->post); 1082 1083 if (from == to) { /* vacuous loop */ 1084 freearc(nfa, a); 1085 return 1; 1086 } 1087 1088 /* decide which end to work on */ 1089 usefrom = 1; /* default: attack from */ 1090 if (from->nouts > to->nins) 1091 usefrom = 0; 1092 else if (from->nouts == to->nins) { 1093 /* decide on secondary issue: move/copy fewest arcs */ 1094 if (from->nins > to->nouts) 1095 usefrom = 0; 1096 } 1097 1098 freearc(nfa, a); 1099 if (usefrom) { 1100 if (from->nouts == 0) { 1101 /* was the state's only outarc */ 1102 moveins(nfa, from, to); 1103 freestate(nfa, from); 1104 } else 1105 copyins(nfa, from, to); 1106 } else { 1107 if (to->nins == 0) { 1108 /* was the state's only inarc */ 1109 moveouts(nfa, to, from); 1110 freestate(nfa, to); 1111 } else 1112 copyouts(nfa, to, from); 1113 } 1114 1115 return 1; 1116} 1117 1118/* 1119 - cleanup - clean up NFA after optimizations 1120 ^ static VOID cleanup(struct nfa *); 1121 */ 1122static VOID 1123cleanup(nfa) 1124struct nfa *nfa; 1125{ 1126 struct state *s; 1127 struct state *nexts; 1128 int n; 1129 1130 /* clear out unreachable or dead-end states */ 1131 /* use pre to mark reachable, then post to mark can-reach-post */ 1132 markreachable(nfa, nfa->pre, (struct state *)NULL, nfa->pre); 1133 markcanreach(nfa, nfa->post, nfa->pre, nfa->post); 1134 for (s = nfa->states; s != NULL; s = nexts) { 1135 nexts = s->next; 1136 if (s->tmp != nfa->post && !s->flag) 1137 dropstate(nfa, s); 1138 } 1139 assert(nfa->post->nins == 0 || nfa->post->tmp == nfa->post); 1140 cleartraverse(nfa, nfa->pre); 1141 assert(nfa->post->nins == 0 || nfa->post->tmp == NULL); 1142 /* the nins==0 (final unreachable) case will be caught later */ 1143 1144 /* renumber surviving states */ 1145 n = 0; 1146 for (s = nfa->states; s != NULL; s = s->next) 1147 s->no = n++; 1148 nfa->nstates = n; 1149} 1150 1151/* 1152 - markreachable - recursive marking of reachable states 1153 ^ static VOID markreachable(struct nfa *, struct state *, struct state *, 1154 ^ struct state *); 1155 */ 1156static VOID 1157markreachable(nfa, s, okay, mark) 1158struct nfa *nfa; 1159struct state *s; 1160struct state *okay; /* consider only states with this mark */ 1161struct state *mark; /* the value to mark with */ 1162{ 1163 struct arc *a; 1164 1165 if (s->tmp != okay) 1166 return; 1167 s->tmp = mark; 1168 1169 for (a = s->outs; a != NULL; a = a->outchain) 1170 markreachable(nfa, a->to, okay, mark); 1171} 1172 1173/* 1174 - markcanreach - recursive marking of states which can reach here 1175 ^ static VOID markcanreach(struct nfa *, struct state *, struct state *, 1176 ^ struct state *); 1177 */ 1178static VOID 1179markcanreach(nfa, s, okay, mark) 1180struct nfa *nfa; 1181struct state *s; 1182struct state *okay; /* consider only states with this mark */ 1183struct state *mark; /* the value to mark with */ 1184{ 1185 struct arc *a; 1186 1187 if (s->tmp != okay) 1188 return; 1189 s->tmp = mark; 1190 1191 for (a = s->ins; a != NULL; a = a->inchain) 1192 markcanreach(nfa, a->from, okay, mark); 1193} 1194 1195/* 1196 - analyze - ascertain potentially-useful facts about an optimized NFA 1197 ^ static long analyze(struct nfa *); 1198 */ 1199static long /* re_info bits to be ORed in */ 1200analyze(nfa) 1201struct nfa *nfa; 1202{ 1203 struct arc *a; 1204 struct arc *aa; 1205 1206 if (nfa->pre->outs == NULL) 1207 return REG_UIMPOSSIBLE; 1208 for (a = nfa->pre->outs; a != NULL; a = a->outchain) 1209 for (aa = a->to->outs; aa != NULL; aa = aa->outchain) 1210 if (aa->to == nfa->post) 1211 return REG_UEMPTYMATCH; 1212 return 0; 1213} 1214 1215/* 1216 - compact - compact an NFA 1217 ^ static VOID compact(struct nfa *, struct cnfa *); 1218 */ 1219static VOID 1220compact(nfa, cnfa) 1221struct nfa *nfa; 1222struct cnfa *cnfa; 1223{ 1224 struct state *s; 1225 struct arc *a; 1226 size_t nstates; 1227 size_t narcs; 1228 struct carc *ca; 1229 struct carc *first; 1230 1231 assert (!NISERR()); 1232 1233 nstates = 0; 1234 narcs = 0; 1235 for (s = nfa->states; s != NULL; s = s->next) { 1236 nstates++; 1237 narcs += 1 + s->nouts + 1; 1238 /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */ 1239 } 1240 1241 cnfa->states = (struct carc **)MALLOC(nstates * sizeof(struct carc *)); 1242 cnfa->arcs = (struct carc *)MALLOC(narcs * sizeof(struct carc)); 1243 if (cnfa->states == NULL || cnfa->arcs == NULL) { 1244 if (cnfa->states != NULL) 1245 FREE(cnfa->states); 1246 if (cnfa->arcs != NULL) 1247 FREE(cnfa->arcs); 1248 NERR(REG_ESPACE); 1249 return; 1250 } 1251 cnfa->nstates = nstates; 1252 cnfa->pre = nfa->pre->no; 1253 cnfa->post = nfa->post->no; 1254 cnfa->bos[0] = nfa->bos[0]; 1255 cnfa->bos[1] = nfa->bos[1]; 1256 cnfa->eos[0] = nfa->eos[0]; 1257 cnfa->eos[1] = nfa->eos[1]; 1258 cnfa->ncolors = maxcolor(nfa->cm) + 1; 1259 cnfa->flags = 0; 1260 1261 ca = cnfa->arcs; 1262 for (s = nfa->states; s != NULL; s = s->next) { 1263 assert((size_t)s->no < nstates); 1264 cnfa->states[s->no] = ca; 1265 ca->co = 0; /* clear and skip flags "arc" */ 1266 ca++; 1267 first = ca; 1268 for (a = s->outs; a != NULL; a = a->outchain) 1269 switch (a->type) { 1270 case PLAIN: 1271 ca->co = a->co; 1272 ca->to = a->to->no; 1273 ca++; 1274 break; 1275 case LACON: 1276 assert(s->no != cnfa->pre); 1277 ca->co = (color)(cnfa->ncolors + a->co); 1278 ca->to = a->to->no; 1279 ca++; 1280 cnfa->flags |= HASLACONS; 1281 break; 1282 default: 1283 assert(NOTREACHED); 1284 break; 1285 } 1286 carcsort(first, ca-1); 1287 ca->co = COLORLESS; 1288 ca->to = 0; 1289 ca++; 1290 } 1291 assert(ca == &cnfa->arcs[narcs]); 1292 assert(cnfa->nstates != 0); 1293 1294 /* mark no-progress states */ 1295 for (a = nfa->pre->outs; a != NULL; a = a->outchain) 1296 cnfa->states[a->to->no]->co = 1; 1297 cnfa->states[nfa->pre->no]->co = 1; 1298} 1299 1300/* 1301 - carcsort - sort compacted-NFA arcs by color 1302 * Really dumb algorithm, but if the list is long enough for that to matter, 1303 * you're in real trouble anyway. 1304 ^ static VOID carcsort(struct carc *, struct carc *); 1305 */ 1306static VOID 1307carcsort(first, last) 1308struct carc *first; 1309struct carc *last; 1310{ 1311 struct carc *p; 1312 struct carc *q; 1313 struct carc tmp; 1314 1315 if (last - first <= 1) 1316 return; 1317 1318 for (p = first; p <= last; p++) 1319 for (q = p; q <= last; q++) 1320 if (p->co > q->co || 1321 (p->co == q->co && p->to > q->to)) { 1322 assert(p != q); 1323 tmp = *p; 1324 *p = *q; 1325 *q = tmp; 1326 } 1327} 1328 1329/* 1330 - freecnfa - free a compacted NFA 1331 ^ static VOID freecnfa(struct cnfa *); 1332 */ 1333static VOID 1334freecnfa(cnfa) 1335struct cnfa *cnfa; 1336{ 1337 assert(cnfa->nstates != 0); /* not empty already */ 1338 cnfa->nstates = 0; 1339 FREE(cnfa->states); 1340 FREE(cnfa->arcs); 1341} 1342 1343/* 1344 - dumpnfa - dump an NFA in human-readable form 1345 ^ static VOID dumpnfa(struct nfa *, FILE *); 1346 */ 1347static VOID 1348dumpnfa(nfa, f) 1349struct nfa *nfa; 1350FILE *f; 1351{ 1352#ifdef REG_DEBUG 1353 struct state *s; 1354 1355 fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no); 1356 if (nfa->bos[0] != COLORLESS) 1357 fprintf(f, ", bos [%ld]", (long)nfa->bos[0]); 1358 if (nfa->bos[1] != COLORLESS) 1359 fprintf(f, ", bol [%ld]", (long)nfa->bos[1]); 1360 if (nfa->eos[0] != COLORLESS) 1361 fprintf(f, ", eos [%ld]", (long)nfa->eos[0]); 1362 if (nfa->eos[1] != COLORLESS) 1363 fprintf(f, ", eol [%ld]", (long)nfa->eos[1]); 1364 fprintf(f, "\n"); 1365 for (s = nfa->states; s != NULL; s = s->next) 1366 dumpstate(s, f); 1367 if (nfa->parent == NULL) 1368 dumpcolors(nfa->cm, f); 1369 fflush(f); 1370#endif 1371} 1372 1373#ifdef REG_DEBUG /* subordinates of dumpnfa */ 1374/* 1375 ^ #ifdef REG_DEBUG 1376 */ 1377 1378/* 1379 - dumpstate - dump an NFA state in human-readable form 1380 ^ static VOID dumpstate(struct state *, FILE *); 1381 */ 1382static VOID 1383dumpstate(s, f) 1384struct state *s; 1385FILE *f; 1386{ 1387 struct arc *a; 1388 1389 fprintf(f, "%d%s%c", s->no, (s->tmp != NULL) ? "T" : "", 1390 (s->flag) ? s->flag : '.'); 1391 if (s->prev != NULL && s->prev->next != s) 1392 fprintf(f, "\tstate chain bad\n"); 1393 if (s->nouts == 0) 1394 fprintf(f, "\tno out arcs\n"); 1395 else 1396 dumparcs(s, f); 1397 fflush(f); 1398 for (a = s->ins; a != NULL; a = a->inchain) { 1399 if (a->to != s) 1400 fprintf(f, "\tlink from %d to %d on %d's in-chain\n", 1401 a->from->no, a->to->no, s->no); 1402 } 1403} 1404 1405/* 1406 - dumparcs - dump out-arcs in human-readable form 1407 ^ static VOID dumparcs(struct state *, FILE *); 1408 */ 1409static VOID 1410dumparcs(s, f) 1411struct state *s; 1412FILE *f; 1413{ 1414 int pos; 1415 1416 assert(s->nouts > 0); 1417 /* printing arcs in reverse order is usually clearer */ 1418 pos = dumprarcs(s->outs, s, f, 1); 1419 if (pos != 1) 1420 fprintf(f, "\n"); 1421} 1422 1423/* 1424 - dumprarcs - dump remaining outarcs, recursively, in reverse order 1425 ^ static int dumprarcs(struct arc *, struct state *, FILE *, int); 1426 */ 1427static int /* resulting print position */ 1428dumprarcs(a, s, f, pos) 1429struct arc *a; 1430struct state *s; 1431FILE *f; 1432int pos; /* initial print position */ 1433{ 1434 if (a->outchain != NULL) 1435 pos = dumprarcs(a->outchain, s, f, pos); 1436 dumparc(a, s, f); 1437 if (pos == 5) { 1438 fprintf(f, "\n"); 1439 pos = 1; 1440 } else 1441 pos++; 1442 return pos; 1443} 1444 1445/* 1446 - dumparc - dump one outarc in readable form, including prefixing tab 1447 ^ static VOID dumparc(struct arc *, struct state *, FILE *); 1448 */ 1449static VOID 1450dumparc(a, s, f) 1451struct arc *a; 1452struct state *s; 1453FILE *f; 1454{ 1455 struct arc *aa; 1456 struct arcbatch *ab; 1457 1458 fprintf(f, "\t"); 1459 switch (a->type) { 1460 case PLAIN: 1461 fprintf(f, "[%ld]", (long)a->co); 1462 break; 1463 case AHEAD: 1464 fprintf(f, ">%ld>", (long)a->co); 1465 break; 1466 case BEHIND: 1467 fprintf(f, "<%ld<", (long)a->co); 1468 break; 1469 case LACON: 1470 fprintf(f, ":%ld:", (long)a->co); 1471 break; 1472 case '^': 1473 case '$': 1474 fprintf(f, "%c%d", a->type, (int)a->co); 1475 break; 1476 case EMPTY: 1477 break; 1478 default: 1479 fprintf(f, "0x%x/0%lo", a->type, (long)a->co); 1480 break; 1481 } 1482 if (a->from != s) 1483 fprintf(f, "?%d?", a->from->no); 1484 for (ab = &a->from->oas; ab != NULL; ab = ab->next) { 1485 for (aa = &ab->a[0]; aa < &ab->a[ABSIZE]; aa++) 1486 if (aa == a) 1487 break; /* NOTE BREAK OUT */ 1488 if (aa < &ab->a[ABSIZE]) /* propagate break */ 1489 break; /* NOTE BREAK OUT */ 1490 } 1491 if (ab == NULL) 1492 fprintf(f, "?!?"); /* not in allocated space */ 1493 fprintf(f, "->"); 1494 if (a->to == NULL) { 1495 fprintf(f, "NULL"); 1496 return; 1497 } 1498 fprintf(f, "%d", a->to->no); 1499 for (aa = a->to->ins; aa != NULL; aa = aa->inchain) 1500 if (aa == a) 1501 break; /* NOTE BREAK OUT */ 1502 if (aa == NULL) 1503 fprintf(f, "?!?"); /* missing from in-chain */ 1504} 1505 1506/* 1507 ^ #endif 1508 */ 1509#endif /* ifdef REG_DEBUG */ 1510 1511/* 1512 - dumpcnfa - dump a compacted NFA in human-readable form 1513 ^ static VOID dumpcnfa(struct cnfa *, FILE *); 1514 */ 1515static VOID 1516dumpcnfa(cnfa, f) 1517struct cnfa *cnfa; 1518FILE *f; 1519{ 1520#ifdef REG_DEBUG 1521 int st; 1522 1523 fprintf(f, "pre %d, post %d", cnfa->pre, cnfa->post); 1524 if (cnfa->bos[0] != COLORLESS) 1525 fprintf(f, ", bos [%ld]", (long)cnfa->bos[0]); 1526 if (cnfa->bos[1] != COLORLESS) 1527 fprintf(f, ", bol [%ld]", (long)cnfa->bos[1]); 1528 if (cnfa->eos[0] != COLORLESS) 1529 fprintf(f, ", eos [%ld]", (long)cnfa->eos[0]); 1530 if (cnfa->eos[1] != COLORLESS) 1531 fprintf(f, ", eol [%ld]", (long)cnfa->eos[1]); 1532 if (cnfa->flags&HASLACONS) 1533 fprintf(f, ", haslacons"); 1534 fprintf(f, "\n"); 1535 for (st = 0; st < cnfa->nstates; st++) 1536 dumpcstate(st, cnfa->states[st], cnfa, f); 1537 fflush(f); 1538#endif 1539} 1540 1541#ifdef REG_DEBUG /* subordinates of dumpcnfa */ 1542/* 1543 ^ #ifdef REG_DEBUG 1544 */ 1545 1546/* 1547 - dumpcstate - dump a compacted-NFA state in human-readable form 1548 ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *); 1549 */ 1550static VOID 1551dumpcstate(st, ca, cnfa, f) 1552int st; 1553struct carc *ca; 1554struct cnfa *cnfa; 1555FILE *f; 1556{ 1557 int i; 1558 int pos; 1559 1560 fprintf(f, "%d%s", st, (ca[0].co) ? ":" : "."); 1561 pos = 1; 1562 for (i = 1; ca[i].co != COLORLESS; i++) { 1563 if (ca[i].co < cnfa->ncolors) 1564 fprintf(f, "\t[%ld]->%d", (long)ca[i].co, ca[i].to); 1565 else 1566 fprintf(f, "\t:%ld:->%d", (long)ca[i].co-cnfa->ncolors, 1567 ca[i].to); 1568 if (pos == 5) { 1569 fprintf(f, "\n"); 1570 pos = 1; 1571 } else 1572 pos++; 1573 } 1574 if (i == 1 || pos != 1) 1575 fprintf(f, "\n"); 1576 fflush(f); 1577} 1578 1579/* 1580 ^ #endif 1581 */ 1582#endif /* ifdef REG_DEBUG */ 1583