src/regex/regc_nfa.c

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