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