usr/src/cmd/awk/b.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22
  23 /*
  24  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
  25  * Use is subject to license terms.
  26  */
  27
  28 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  29 /*        All Rights Reserved   */
  30
  31 #pragma ident   "%Z%%M% %I%     %E% SMI"
  32
  33 #define DEBUG
  34
  35 #include "awk.h"
  36 #include "y.tab.h"
  37
  38 #define HAT     (NCHARS-1)      /* matches ^ in regular expr */
  39                                 /* NCHARS is 2**n */
  40 #define MAXLIN (3 * LINE_MAX)
  41
  42 #define type(v)         (v)->nobj
  43 #define left(v)         (v)->narg[0]
  44 #define right(v)        (v)->narg[1]
  45 #define parent(v)       (v)->nnext
  46
  47 #define LEAF    case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
  48 #define UNARY   case STAR: case PLUS: case QUEST:
  49
  50 /*
  51  * encoding in tree Nodes:
  52  *      leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL):
  53  *              left is index, right contains value or pointer to value
  54  *      unary (STAR, PLUS, QUEST): left is child, right is null
  55  *      binary (CAT, OR): left and right are children
  56  *      parent contains pointer to parent
  57  */
  58
  59 int     setvec[MAXLIN];
  60 int     tmpset[MAXLIN];
  61 Node    *point[MAXLIN];
  62
  63 int     rtok;           /* next token in current re */
  64 int     rlxval;
  65 uchar   *rlxstr;
  66 uchar   *prestr;        /* current position in current re */
  67 uchar   *lastre;        /* origin of last re */
  68
  69 static  int setcnt;
  70 static  int poscnt;
  71
  72 uchar   *patbeg;
  73 int     patlen;
  74
  75 #define NFA     20      /* cache this many dynamic fa's */
  76 fa      *fatab[NFA];
  77 int     nfatab  = 0;    /* entries in fatab */
  78
  79 static fa       *mkdfa(uchar *, int);
  80 static int      makeinit(fa *, int);
  81 static void     penter(Node *);
  82 static void     freetr(Node *);
  83 static void     overflo(char *);
  84 static void     cfoll(fa *, Node *);
  85 static void     follow(Node *);
  86 static Node     *reparse(uchar *);
  87 static int      relex(void);
  88 static void     freefa(fa *);
  89 static int      cgoto(fa *, int, int);
  90
  91 fa *
  92 makedfa(uchar *s, int anchor)   /* returns dfa for reg expr s */
  93 {
  94         int i, use, nuse;
  95         fa *pfa;
  96
  97         if (compile_time)       /* a constant for sure */
  98                 return (mkdfa(s, anchor));
  99         for (i = 0; i < nfatab; i++) {  /* is it there already? */
 100                 if (fatab[i]->anchor == anchor &&
 101                     strcmp((char *)fatab[i]->restr, (char *)s) == 0) {
 102                         fatab[i]->use++;
 103                         return (fatab[i]);
 104                 }
 105         }
 106         pfa = mkdfa(s, anchor);
 107         if (nfatab < NFA) {     /* room for another */
 108                 fatab[nfatab] = pfa;
 109                 fatab[nfatab]->use = 1;
 110                 nfatab++;
 111                 return (pfa);
 112         }
 113         use = fatab[0]->use;    /* replace least-recently used */
 114         nuse = 0;
 115         for (i = 1; i < nfatab; i++)
 116                 if (fatab[i]->use < use) {
 117                         use = fatab[i]->use;
 118                         nuse = i;
 119                 }
 120         freefa(fatab[nuse]);
 121         fatab[nuse] = pfa;
 122         pfa->use = 1;
 123         return (pfa);
 124 }
 125
 126 fa *
 127 mkdfa(uchar *s, int anchor)     /* does the real work of making a dfa */
 128         /* anchor = 1 for anchored matches, else 0 */
 129 {
 130         Node *p, *p1;
 131         fa *f;
 132
 133         p = reparse(s);
 134         p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
 135                 /* put ALL STAR in front of reg.  exp. */
 136         p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
 137                 /* put FINAL after reg.  exp. */
 138
 139         poscnt = 0;
 140         penter(p1);     /* enter parent pointers and leaf indices */
 141         if ((f = (fa *)calloc(1, sizeof (fa) + poscnt * sizeof (rrow))) == NULL)
 142                 overflo("no room for fa");
 143         /* penter has computed number of positions in re */
 144         f->accept = poscnt-1;
 145         cfoll(f, p1);   /* set up follow sets */
 146         freetr(p1);
 147         if ((f->posns[0] =
 148             (int *)calloc(1, *(f->re[0].lfollow) * sizeof (int))) == NULL) {
 149                         overflo("out of space in makedfa");
 150         }
 151         if ((f->posns[1] = (int *)calloc(1, sizeof (int))) == NULL)
 152                 overflo("out of space in makedfa");
 153         *f->posns[1] = 0;
 154         f->initstat = makeinit(f, anchor);
 155         f->anchor = anchor;
 156         f->restr = tostring(s);
 157         return (f);
 158 }
 159
 160 static int
 161 makeinit(fa *f, int anchor)
 162 {
 163         register int i, k;
 164
 165         f->curstat = 2;
 166         f->out[2] = 0;
 167         f->reset = 0;
 168         k = *(f->re[0].lfollow);
 169         xfree(f->posns[2]);
 170         if ((f->posns[2] = (int *)calloc(1, (k+1) * sizeof (int))) == NULL)
 171                 overflo("out of space in makeinit");
 172         for (i = 0; i <= k; i++) {
 173                 (f->posns[2])[i] = (f->re[0].lfollow)[i];
 174         }
 175         if ((f->posns[2])[1] == f->accept)
 176                 f->out[2] = 1;
 177         for (i = 0; i < NCHARS; i++)
 178                 f->gototab[2][i] = 0;
 179         f->curstat = cgoto(f, 2, HAT);
 180         if (anchor) {
 181                 *f->posns[2] = k-1;     /* leave out position 0 */
 182                 for (i = 0; i < k; i++) {
 183                         (f->posns[0])[i] = (f->posns[2])[i];
 184                 }
 185
 186                 f->out[0] = f->out[2];
 187                 if (f->curstat != 2)
 188                         --(*f->posns[f->curstat]);
 189         }
 190         return (f->curstat);
 191 }
 192
 193 void
 194 penter(Node *p) /* set up parent pointers and leaf indices */
 195 {
 196         switch (type(p)) {
 197         LEAF
 198                 left(p) = (Node *) poscnt;
 199                 point[poscnt++] = p;
 200                 break;
 201         UNARY
 202                 penter(left(p));
 203                 parent(left(p)) = p;
 204                 break;
 205         case CAT:
 206         case OR:
 207                 penter(left(p));
 208                 penter(right(p));
 209                 parent(left(p)) = p;
 210                 parent(right(p)) = p;
 211                 break;
 212         default:
 213                 ERROR "unknown type %d in penter", type(p) FATAL;
 214                 break;
 215         }
 216 }
 217
 218 static void
 219 freetr(Node *p) /* free parse tree */
 220 {
 221         switch (type(p)) {
 222         LEAF
 223                 xfree(p);
 224                 break;
 225         UNARY
 226                 freetr(left(p));
 227                 xfree(p);
 228                 break;
 229         case CAT:
 230         case OR:
 231                 freetr(left(p));
 232                 freetr(right(p));
 233                 xfree(p);
 234                 break;
 235         default:
 236                 ERROR "unknown type %d in freetr", type(p) FATAL;
 237                 break;
 238         }
 239 }
 240
 241 uchar *
 242 cclenter(uchar *p)
 243 {
 244         register int i, c;
 245         uchar *op, *chars, *ret;
 246         size_t  bsize;
 247
 248         init_buf(&chars, &bsize, LINE_INCR);
 249         op = p;
 250         i = 0;
 251         while ((c = *p++) != 0) {
 252                 if (c == '\\') {
 253                         if ((c = *p++) == 't')
 254                                 c = '\t';
 255                         else if (c == 'n')
 256                                 c = '\n';
 257                         else if (c == 'f')
 258                                 c = '\f';
 259                         else if (c == 'r')
 260                                 c = '\r';
 261                         else if (c == 'b')
 262                                 c = '\b';
 263                         else if (c == '\\')
 264                                 c = '\\';
 265                         else if (isdigit(c)) {
 266                                 int n = c - '0';
 267                                 if (isdigit(*p)) {
 268                                         n = 8 * n + *p++ - '0';
 269                                         if (isdigit(*p))
 270                                                 n = 8 * n + *p++ - '0';
 271                                 }
 272                                 c = n;
 273                         } /* else */
 274                                 /* c = c; */
 275                 } else if (c == '-' && i > 0 && chars[i-1] != 0) {
 276                         if (*p != 0) {
 277                                 c = chars[i-1];
 278                                 while ((uchar)c < *p) { /* fails if *p is \\ */
 279                                         expand_buf(&chars, &bsize, i);
 280                                         chars[i++] = ++c;
 281                                 }
 282                                 p++;
 283                                 continue;
 284                         }
 285                 }
 286                 expand_buf(&chars, &bsize, i);
 287                 chars[i++] = c;
 288         }
 289         chars[i++] = '\0';
 290         dprintf(("cclenter: in = |%s|, out = |%s|\n", op, chars));
 291         xfree(op);
 292         ret = tostring(chars);
 293         free(chars);
 294         return (ret);
 295 }
 296
 297 static void
 298 overflo(char *s)
 299 {
 300         ERROR "regular expression too big: %s", gettext((char *)s) FATAL;
 301 }
 302
 303 /* enter follow set of each leaf of vertex v into lfollow[leaf] */
 304 static void
 305 cfoll(fa *f, Node *v)
 306 {
 307         register int i;
 308         register int *p;
 309
 310         switch (type(v)) {
 311         LEAF
 312                 f->re[(int)left(v)].ltype = type(v);
 313                 f->re[(int)left(v)].lval = (int)right(v);
 314                 for (i = 0; i <= f->accept; i++)
 315                         setvec[i] = 0;
 316                 setcnt = 0;
 317                 follow(v);      /* computes setvec and setcnt */
 318                 if ((p = (int *)calloc(1, (setcnt+1) * sizeof (int))) == NULL)
 319                         overflo("follow set overflow");
 320                 f->re[(int)left(v)].lfollow = p;
 321                 *p = setcnt;
 322                 for (i = f->accept; i >= 0; i--) {
 323                         if (setvec[i] == 1)
 324                                 *++p = i;
 325                 }
 326                 break;
 327         UNARY
 328                 cfoll(f, left(v));
 329                 break;
 330         case CAT:
 331         case OR:
 332                 cfoll(f, left(v));
 333                 cfoll(f, right(v));
 334                 break;
 335         default:
 336                 ERROR "unknown type %d in cfoll", type(v) FATAL;
 337         }
 338 }
 339
 340 /*
 341  * collects initially active leaves of p into setvec
 342  * returns 0 or 1 depending on whether p matches empty string
 343  */
 344 static int
 345 first(Node *p)
 346 {
 347         register int b;
 348
 349         switch (type(p)) {
 350         LEAF
 351                 if (setvec[(int)left(p)] != 1) {
 352                         setvec[(int)left(p)] = 1;
 353                         setcnt++;
 354                 }
 355                 if (type(p) == CCL && (*(uchar *)right(p)) == '\0')
 356                         return (0);             /* empty CCL */
 357                 else
 358                         return (1);
 359         case PLUS:
 360                 if (first(left(p)) == 0)
 361                         return (0);
 362                 return (1);
 363         case STAR:
 364         case QUEST:
 365                 (void) first(left(p));
 366                 return (0);
 367         case CAT:
 368                 if (first(left(p)) == 0 && first(right(p)) == 0)
 369                         return (0);
 370                 return (1);
 371         case OR:
 372                 b = first(right(p));
 373                 if (first(left(p)) == 0 || b == 0)
 374                         return (0);
 375                 return (1);
 376         }
 377         ERROR "unknown type %d in first", type(p) FATAL;
 378         return (-1);
 379 }
 380
 381 /* collects leaves that can follow v into setvec */
 382 static void
 383 follow(Node *v)
 384 {
 385         Node *p;
 386
 387         if (type(v) == FINAL)
 388                 return;
 389         p = parent(v);
 390         switch (type(p)) {
 391         case STAR:
 392         case PLUS:
 393                 (void) first(v);
 394                 follow(p);
 395                 return;
 396
 397         case OR:
 398         case QUEST:
 399                 follow(p);
 400                 return;
 401
 402         case CAT:
 403                 if (v == left(p)) {     /* v is left child of p */
 404                         if (first(right(p)) == 0) {
 405                                 follow(p);
 406                                 return;
 407                         }
 408                 } else          /* v is right child */
 409                         follow(p);
 410                 return;
 411         default:
 412                 ERROR "unknown type %d in follow", type(p) FATAL;
 413                 break;
 414         }
 415 }
 416
 417 static int
 418 member(uchar c, uchar *s)       /* is c in s? */
 419 {
 420         while (*s)
 421                 if (c == *s++)
 422                         return (1);
 423         return (0);
 424 }
 425
 426
 427 int
 428 match(fa *f, uchar *p)
 429 {
 430         register int s, ns;
 431
 432         s = f->reset ? makeinit(f, 0) : f->initstat;
 433         if (f->out[s])
 434                 return (1);
 435         do {
 436                 if ((ns = f->gototab[s][*p]) != 0)
 437                         s = ns;
 438                 else
 439                         s = cgoto(f, s, *p);
 440                 if (f->out[s])
 441                         return (1);
 442         } while (*p++ != 0);
 443         return (0);
 444 }
 445
 446 int
 447 pmatch(fa *f, uchar *p)
 448 {
 449         register int s, ns;
 450         register uchar *q;
 451         int i, k;
 452
 453         if (f->reset) {
 454                 f->initstat = s = makeinit(f, 1);
 455         } else {
 456                 s = f->initstat;
 457         }
 458         patbeg = p;
 459         patlen = -1;
 460         do {
 461                 q = p;
 462                 do {
 463                         if (f->out[s])          /* final state */
 464                                 patlen = q-p;
 465                         if ((ns = f->gototab[s][*q]) != 0)
 466                                 s = ns;
 467                         else
 468                                 s = cgoto(f, s, *q);
 469                         if (s == 1) {   /* no transition */
 470                                 if (patlen >= 0) {
 471                                         patbeg = p;
 472                                         return (1);
 473                                 } else
 474                                         goto nextin;    /* no match */
 475                         }
 476                 } while (*q++ != 0);
 477                 if (f->out[s])
 478                         patlen = q - p - 1;     /* don't count $ */
 479                 if (patlen >= 0) {
 480                         patbeg = p;
 481                         return (1);
 482                 }
 483         nextin:
 484                 s = 2;
 485                 if (f->reset) {
 486                         for (i = 2; i <= f->curstat; i++)
 487                                 xfree(f->posns[i]);
 488                         k = *f->posns[0];
 489                         if ((f->posns[2] =
 490                             (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) {
 491                                 overflo("out of space in pmatch");
 492                         }
 493                         for (i = 0; i <= k; i++)
 494                                 (f->posns[2])[i] = (f->posns[0])[i];
 495                         f->initstat = f->curstat = 2;
 496                         f->out[2] = f->out[0];
 497                         for (i = 0; i < NCHARS; i++)
 498                                 f->gototab[2][i] = 0;
 499                 }
 500         } while (*p++ != 0);
 501         return (0);
 502 }
 503
 504 int
 505 nematch(fa *f, uchar *p)
 506 {
 507         register int s, ns;
 508         register uchar *q;
 509         int i, k;
 510
 511         if (f->reset) {
 512                 f->initstat = s = makeinit(f, 1);
 513         } else {
 514                 s = f->initstat;
 515         }
 516         patlen = -1;
 517         while (*p) {
 518                 q = p;
 519                 do {
 520                         if (f->out[s])          /* final state */
 521                                 patlen = q-p;
 522                         if ((ns = f->gototab[s][*q]) != 0)
 523                                 s = ns;
 524                         else
 525                                 s = cgoto(f, s, *q);
 526                         if (s == 1) {   /* no transition */
 527                                 if (patlen > 0) {
 528                                         patbeg = p;
 529                                         return (1);
 530                                 } else
 531                                         goto nnextin;   /* no nonempty match */
 532                         }
 533                 } while (*q++ != 0);
 534                 if (f->out[s])
 535                         patlen = q - p - 1;     /* don't count $ */
 536                 if (patlen > 0) {
 537                         patbeg = p;
 538                         return (1);
 539                 }
 540         nnextin:
 541                 s = 2;
 542                 if (f->reset) {
 543                         for (i = 2; i <= f->curstat; i++)
 544                                 xfree(f->posns[i]);
 545                         k = *f->posns[0];
 546                         if ((f->posns[2] =
 547                             (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) {
 548                                 overflo("out of state space");
 549                         }
 550                         for (i = 0; i <= k; i++)
 551                                 (f->posns[2])[i] = (f->posns[0])[i];
 552                         f->initstat = f->curstat = 2;
 553                         f->out[2] = f->out[0];
 554                         for (i = 0; i < NCHARS; i++)
 555                                 f->gototab[2][i] = 0;
 556                 }
 557                 p++;
 558         }
 559         return (0);
 560 }
 561
 562 static Node *regexp(void), *primary(void), *concat(Node *);
 563 static Node *alt(Node *), *unary(Node *);
 564
 565 static Node *
 566 reparse(uchar *p)
 567 {
 568         /* parses regular expression pointed to by p */
 569         /* uses relex() to scan regular expression */
 570         Node *np;
 571
 572         dprintf(("reparse <%s>\n", p));
 573         lastre = prestr = p;    /* prestr points to string to be parsed */
 574         rtok = relex();
 575         if (rtok == '\0')
 576                 ERROR "empty regular expression" FATAL;
 577         np = regexp();
 578         if (rtok == '\0') {
 579                 return (np);
 580         } else {
 581                 ERROR "syntax error in regular expression %s at %s",
 582                     lastre, prestr FATAL;
 583         }
 584         /*NOTREACHED*/
 585         return (NULL);
 586 }
 587
 588 static Node *
 589 regexp(void)
 590 {
 591         return (alt(concat(primary())));
 592 }
 593
 594 static Node *
 595 primary(void)
 596 {
 597         Node *np;
 598
 599         switch (rtok) {
 600         case CHAR:
 601                 np = op2(CHAR, NIL, (Node *)rlxval);
 602                 rtok = relex();
 603                 return (unary(np));
 604         case ALL:
 605                 rtok = relex();
 606                 return (unary(op2(ALL, NIL, NIL)));
 607         case DOT:
 608                 rtok = relex();
 609                 return (unary(op2(DOT, NIL, NIL)));
 610         case CCL:
 611                 /*LINTED align*/
 612                 np = op2(CCL, NIL, (Node *)cclenter(rlxstr));
 613                 rtok = relex();
 614                 return (unary(np));
 615         case NCCL:
 616                 /*LINTED align*/
 617                 np = op2(NCCL, NIL, (Node *)cclenter(rlxstr));
 618                 rtok = relex();
 619                 return (unary(np));
 620         case '^':
 621                 rtok = relex();
 622                 return (unary(op2(CHAR, NIL, (Node *)HAT)));
 623         case '$':
 624                 rtok = relex();
 625                 return (unary(op2(CHAR, NIL, NIL)));
 626         case '(':
 627                 rtok = relex();
 628                 if (rtok == ')') {      /* special pleading for () */
 629                         rtok = relex();
 630                         return (unary(op2(CCL, NIL,
 631                             /*LINTED align*/
 632                             (Node *)tostring((uchar *)""))));
 633                 }
 634                 np = regexp();
 635                 if (rtok == ')') {
 636                         rtok = relex();
 637                         return (unary(np));
 638                 } else {
 639                         ERROR "syntax error in regular expression %s at %s",
 640                             lastre, prestr FATAL;
 641                 }
 642         default:
 643                 ERROR "illegal primary in regular expression %s at %s",
 644                     lastre, prestr FATAL;
 645         }
 646         /*NOTREACHED*/
 647         return (NULL);
 648 }
 649
 650 static Node *
 651 concat(Node *np)
 652 {
 653         switch (rtok) {
 654         case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
 655                 return (concat(op2(CAT, np, primary())));
 656         default:
 657                 return (np);
 658         }
 659 }
 660
 661 static Node *
 662 alt(Node *np)
 663 {
 664         if (rtok == OR) {
 665                 rtok = relex();
 666                 return (alt(op2(OR, np, concat(primary()))));
 667         }
 668         return (np);
 669 }
 670
 671 static Node *
 672 unary(Node *np)
 673 {
 674         switch (rtok) {
 675         case STAR:
 676                 rtok = relex();
 677                 return (unary(op2(STAR, np, NIL)));
 678         case PLUS:
 679                 rtok = relex();
 680                 return (unary(op2(PLUS, np, NIL)));
 681         case QUEST:
 682                 rtok = relex();
 683                 return (unary(op2(QUEST, np, NIL)));
 684         default:
 685                 return (np);
 686         }
 687 }
 688
 689 static int
 690 relex(void)             /* lexical analyzer for reparse */
 691 {
 692         register int c;
 693         uchar *cbuf;
 694         int clen, cflag;
 695
 696         switch (c = *prestr++) {
 697         case '|': return OR;
 698         case '*': return STAR;
 699         case '+': return PLUS;
 700         case '?': return QUEST;
 701         case '.': return DOT;
 702         case '\0': prestr--; return '\0';
 703         case '^':
 704         case '$':
 705         case '(':
 706         case ')':
 707                 return (c);
 708         case '\\':
 709                 if ((c = *prestr++) == 't')
 710                         c = '\t';
 711                 else if (c == 'n')
 712                         c = '\n';
 713                 else if (c == 'f')
 714                         c = '\f';
 715                 else if (c == 'r')
 716                         c = '\r';
 717                 else if (c == 'b')
 718                         c = '\b';
 719                 else if (c == '\\')
 720                         c = '\\';
 721                 else if (isdigit(c)) {
 722                         int n = c - '0';
 723                         if (isdigit(*prestr)) {
 724                                 n = 8 * n + *prestr++ - '0';
 725                                 if (isdigit(*prestr))
 726                                         n = 8 * n + *prestr++ - '0';
 727                         }
 728                         c = n;
 729                 } /* else it's now in c */
 730                 rlxval = c;
 731                 return (CHAR);
 732         default:
 733                 rlxval = c;
 734                 return (CHAR);
 735         case '[':
 736                 clen = 0;
 737                 if (*prestr == '^') {
 738                         cflag = 1;
 739                         prestr++;
 740                 } else
 741                         cflag = 0;
 742                 init_buf(&cbuf, NULL, strlen((char *)prestr) * 2 + 1);
 743                 for (;;) {
 744                         if ((c = *prestr++) == '\\') {
 745                                 cbuf[clen++] = '\\';
 746                                 if ((c = *prestr++) == '\0') {
 747                                         ERROR
 748                         "nonterminated character class %s", lastre FATAL;
 749                                 }
 750                                 cbuf[clen++] = c;
 751                         } else if (c == ']') {
 752                                 cbuf[clen] = 0;
 753                                 rlxstr = tostring(cbuf);
 754                                 free(cbuf);
 755                                 if (cflag == 0)
 756                                         return (CCL);
 757                                 else
 758                                         return (NCCL);
 759                         } else if (c == '\n') {
 760                                 ERROR "newline in character class %s...",
 761                                     lastre FATAL;
 762                         } else if (c == '\0') {
 763                                 ERROR "nonterminated character class %s",
 764                                     lastre FATAL;
 765                         } else
 766                                 cbuf[clen++] = c;
 767                 }
 768                 /*NOTREACHED*/
 769         }
 770         return (0);
 771 }
 772
 773 static int
 774 cgoto(fa *f, int s, int c)
 775 {
 776         register int i, j, k;
 777         register int *p, *q;
 778
 779         for (i = 0; i <= f->accept; i++)
 780                 setvec[i] = 0;
 781         setcnt = 0;
 782         /* compute positions of gototab[s,c] into setvec */
 783         p = f->posns[s];
 784         for (i = 1; i <= *p; i++) {
 785                 if ((k = f->re[p[i]].ltype) != FINAL) {
 786                         if (k == CHAR && c == f->re[p[i]].lval ||
 787                             k == DOT && c != 0 && c != HAT ||
 788                             k == ALL && c != 0 ||
 789                             k == CCL &&
 790                             member(c, (uchar *)f->re[p[i]].lval) ||
 791                             k == NCCL &&
 792                             !member(c, (uchar *)f->re[p[i]].lval) &&
 793                             c != 0 && c != HAT) {
 794                                 q = f->re[p[i]].lfollow;
 795                                 for (j = 1; j <= *q; j++) {
 796                                         if (setvec[q[j]] == 0) {
 797                                                 setcnt++;
 798                                                 setvec[q[j]] = 1;
 799                                         }
 800                                 }
 801                         }
 802                 }
 803         }
 804         /* determine if setvec is a previous state */
 805         tmpset[0] = setcnt;
 806         j = 1;
 807         for (i = f->accept; i >= 0; i--)
 808                 if (setvec[i]) {
 809                         tmpset[j++] = i;
 810                 }
 811         /* tmpset == previous state? */
 812         for (i = 1; i <= f->curstat; i++) {
 813                 p = f->posns[i];
 814                 if ((k = tmpset[0]) != p[0])
 815                         goto different;
 816                 for (j = 1; j <= k; j++)
 817                         if (tmpset[j] != p[j])
 818                                 goto different;
 819                 /* setvec is state i */
 820                 f->gototab[s][c] = i;
 821                 return (i);
 822         different:;
 823         }
 824
 825         /* add tmpset to current set of states */
 826         if (f->curstat >= NSTATES-1) {
 827                 f->curstat = 2;
 828                 f->reset = 1;
 829                 for (i = 2; i < NSTATES; i++)
 830                         xfree(f->posns[i]);
 831         } else
 832                 ++(f->curstat);
 833         for (i = 0; i < NCHARS; i++)
 834                 f->gototab[f->curstat][i] = 0;
 835         xfree(f->posns[f->curstat]);
 836         if ((p = (int *)calloc(1, (setcnt + 1) * sizeof (int))) == NULL)
 837                 overflo("out of space in cgoto");
 838
 839         f->posns[f->curstat] = p;
 840         f->gototab[s][c] = f->curstat;
 841         for (i = 0; i <= setcnt; i++)
 842                 p[i] = tmpset[i];
 843         if (setvec[f->accept])
 844                 f->out[f->curstat] = 1;
 845         else
 846                 f->out[f->curstat] = 0;
 847         return (f->curstat);
 848 }
 849
 850 static void
 851 freefa(fa *f)
 852 {
 853
 854         register int i;
 855
 856         if (f == NULL)
 857                 return;
 858         for (i = 0; i <= f->curstat; i++)
 859                 xfree(f->posns[i]);
 860         for (i = 0; i <= f->accept; i++)
 861                 xfree(f->re[i].lfollow);
 862         xfree(f->restr);
 863         xfree(f);
 864 }