contrib/awk/dfa.c

   1 /* dfa.c - deterministic extended regexp routines for GNU
   2    Copyright (C) 1988 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA */
  17
  18 /* Written June, 1988 by Mike Haertel
  19    Modified July, 1988 by Arthur David Olson to assist BMG speedups  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 #include <config.h>
  23 #endif
  24
  25 #include <assert.h>
  26 #include <ctype.h>
  27 #include <stdio.h>
  28
  29 #ifdef STDC_HEADERS
  30 #include <stdlib.h>
  31 #else
  32 #include <sys/types.h>
  33 extern char *calloc(), *malloc(), *realloc();
  34 extern void free();
  35 #endif
  36
  37 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  38 #include <string.h>
  39 #undef index
  40 #define index strchr
  41 #else
  42 #include <strings.h>
  43 #endif
  44
  45 #ifndef DEBUG   /* use the same approach as regex.c */
  46 #undef assert
  47 #define assert(e)
  48 #endif /* DEBUG */
  49
  50 #ifndef isgraph
  51 #define isgraph(C) (isprint(C) && !isspace(C))
  52 #endif
  53
  54 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))
  55 #define ISALPHA(C) isalpha(C)
  56 #define ISUPPER(C) isupper(C)
  57 #define ISLOWER(C) islower(C)
  58 #define ISDIGIT(C) isdigit(C)
  59 #define ISXDIGIT(C) isxdigit(C)
  60 #define ISSPACE(C) isspace(C)
  61 #define ISPUNCT(C) ispunct(C)
  62 #define ISALNUM(C) isalnum(C)
  63 #define ISPRINT(C) isprint(C)
  64 #define ISGRAPH(C) isgraph(C)
  65 #define ISCNTRL(C) iscntrl(C)
  66 #else
  67 #define ISALPHA(C) (isascii(C) && isalpha(C))
  68 #define ISUPPER(C) (isascii(C) && isupper(C))
  69 #define ISLOWER(C) (isascii(C) && islower(C))
  70 #define ISDIGIT(C) (isascii(C) && isdigit(C))
  71 #define ISXDIGIT(C) (isascii(C) && isxdigit(C))
  72 #define ISSPACE(C) (isascii(C) && isspace(C))
  73 #define ISPUNCT(C) (isascii(C) && ispunct(C))
  74 #define ISALNUM(C) (isascii(C) && isalnum(C))
  75 #define ISPRINT(C) (isascii(C) && isprint(C))
  76 #define ISGRAPH(C) (isascii(C) && isgraph(C))
  77 #define ISCNTRL(C) (isascii(C) && iscntrl(C))
  78 #endif
  79
  80 #ifndef __FreeBSD__
  81 #include "regex.h"
  82 #else
  83 #include <gnuregex.h>
  84 #endif
  85 #include "dfa.h"
  86
  87 #ifdef __STDC__
  88 typedef void *ptr_t;
  89 #else
  90 typedef char *ptr_t;
  91 #ifndef const
  92 #define const
  93 #endif
  94 #endif
  95
  96 static void dfamust _RE_ARGS((struct dfa *dfa));
  97
  98 static ptr_t xcalloc _RE_ARGS((size_t n, size_t s));
  99 static ptr_t xmalloc _RE_ARGS((size_t n));
 100 static ptr_t xrealloc _RE_ARGS((ptr_t p, size_t n));
 101 #ifdef DEBUG
 102 static void prtok _RE_ARGS((token t));
 103 #endif
 104 static int tstbit _RE_ARGS((int b, charclass c));
 105 static void setbit _RE_ARGS((int b, charclass c));
 106 static void clrbit _RE_ARGS((int b, charclass c));
 107 static void copyset _RE_ARGS((charclass src, charclass dst));
 108 static void zeroset _RE_ARGS((charclass s));
 109 static void notset _RE_ARGS((charclass s));
 110 static int equal _RE_ARGS((charclass s1, charclass s2));
 111 static int charclass_index _RE_ARGS((charclass s));
 112 static int looking_at _RE_ARGS((const char *s));
 113 static token lex _RE_ARGS((void));
 114 static void addtok _RE_ARGS((token t));
 115 static void atom _RE_ARGS((void));
 116 static int nsubtoks _RE_ARGS((int tindex));
 117 static void copytoks _RE_ARGS((int tindex, int ntokens));
 118 static void closure _RE_ARGS((void));
 119 static void branch _RE_ARGS((void));
 120 static void regexp _RE_ARGS((int toplevel));
 121 static void copy _RE_ARGS((position_set *src, position_set *dst));
 122 static void insert _RE_ARGS((position p, position_set *s));
 123 static void merge _RE_ARGS((position_set *s1, position_set *s2, position_set *m));
 124 static void delete _RE_ARGS((position p, position_set *s));
 125 static int state_index _RE_ARGS((struct dfa *d, position_set *s,
 126                           int newline, int letter));
 127 static void build_state _RE_ARGS((int s, struct dfa *d));
 128 static void build_state_zero _RE_ARGS((struct dfa *d));
 129 static char *icatalloc _RE_ARGS((char *old, char *new));
 130 static char *icpyalloc _RE_ARGS((char *string));
 131 static char *istrstr _RE_ARGS((char *lookin, char *lookfor));
 132 static void ifree _RE_ARGS((char *cp));
 133 static void freelist _RE_ARGS((char **cpp));
 134 static char **enlist _RE_ARGS((char **cpp, char *new, size_t len));
 135 static char **comsubs _RE_ARGS((char *left, char *right));
 136 static char **addlists _RE_ARGS((char **old, char **new));
 137 static char **inboth _RE_ARGS((char **left, char **right));
 138
 139 #ifdef __FreeBSD__
 140 static int collate_range_cmp (a, b)
 141         int a, b;
 142 {
 143         int r;
 144         static char s[2][2];
 145
 146         if ((unsigned char)a == (unsigned char)b)
 147                 return 0;
 148         s[0][0] = a;
 149         s[1][0] = b;
 150         if ((r = strcoll(s[0], s[1])) == 0)
 151                 r = (unsigned char)a - (unsigned char)b;
 152         return r;
 153 }
 154 #endif
 155
 156 static ptr_t
 157 xcalloc(n, s)
 158      size_t n;
 159      size_t s;
 160 {
 161   ptr_t r = calloc(n, s);
 162
 163   if (!r)
 164     dfaerror("Memory exhausted");
 165   return r;
 166 }
 167
 168 static ptr_t
 169 xmalloc(n)
 170      size_t n;
 171 {
 172   ptr_t r = malloc(n);
 173
 174   assert(n != 0);
 175   if (!r)
 176     dfaerror("Memory exhausted");
 177   return r;
 178 }
 179
 180 static ptr_t
 181 xrealloc(p, n)
 182      ptr_t p;
 183      size_t n;
 184 {
 185   ptr_t r = realloc(p, n);
 186
 187   assert(n != 0);
 188   if (!r)
 189     dfaerror("Memory exhausted");
 190   return r;
 191 }
 192
 193 #define CALLOC(p, t, n) ((p) = (t *) xcalloc((size_t)(n), sizeof (t)))
 194 #define MALLOC(p, t, n) ((p) = (t *) xmalloc((n) * sizeof (t)))
 195 #define REALLOC(p, t, n) ((p) = (t *) xrealloc((ptr_t) (p), (n) * sizeof (t)))
 196
 197 /* Reallocate an array of type t if nalloc is too small for index. */
 198 #define REALLOC_IF_NECESSARY(p, t, nalloc, index) \
 199   if ((index) >= (nalloc))                        \
 200     {                                             \
 201       while ((index) >= (nalloc))                 \
 202         (nalloc) *= 2;                            \
 203       REALLOC(p, t, nalloc);                      \
 204     }
 205
 206 #ifdef DEBUG
 207
 208 static void
 209 prtok(t)
 210      token t;
 211 {
 212   char *s;
 213
 214   if (t < 0)
 215     fprintf(stderr, "END");
 216   else if (t < NOTCHAR)
 217     fprintf(stderr, "%c", t);
 218   else
 219     {
 220       switch (t)
 221         {
 222         case EMPTY: s = "EMPTY"; break;
 223         case BACKREF: s = "BACKREF"; break;
 224         case BEGLINE: s = "BEGLINE"; break;
 225         case ENDLINE: s = "ENDLINE"; break;
 226         case BEGWORD: s = "BEGWORD"; break;
 227         case ENDWORD: s = "ENDWORD"; break;
 228         case LIMWORD: s = "LIMWORD"; break;
 229         case NOTLIMWORD: s = "NOTLIMWORD"; break;
 230         case QMARK: s = "QMARK"; break;
 231         case STAR: s = "STAR"; break;
 232         case PLUS: s = "PLUS"; break;
 233         case CAT: s = "CAT"; break;
 234         case OR: s = "OR"; break;
 235         case ORTOP: s = "ORTOP"; break;
 236         case LPAREN: s = "LPAREN"; break;
 237         case RPAREN: s = "RPAREN"; break;
 238         default: s = "CSET"; break;
 239         }
 240       fprintf(stderr, "%s", s);
 241     }
 242 }
 243 #endif /* DEBUG */
 244
 245 /* Stuff pertaining to charclasses. */
 246
 247 static int
 248 tstbit(b, c)
 249      int b;
 250      charclass c;
 251 {
 252   return c[b / INTBITS] & 1 << b % INTBITS;
 253 }
 254
 255 static void
 256 setbit(b, c)
 257      int b;
 258      charclass c;
 259 {
 260   c[b / INTBITS] |= 1 << b % INTBITS;
 261 }
 262
 263 static void
 264 clrbit(b, c)
 265      int b;
 266      charclass c;
 267 {
 268   c[b / INTBITS] &= ~(1 << b % INTBITS);
 269 }
 270
 271 static void
 272 copyset(src, dst)
 273      charclass src;
 274      charclass dst;
 275 {
 276   int i;
 277
 278   for (i = 0; i < CHARCLASS_INTS; ++i)
 279     dst[i] = src[i];
 280 }
 281
 282 static void
 283 zeroset(s)
 284      charclass s;
 285 {
 286   int i;
 287
 288   for (i = 0; i < CHARCLASS_INTS; ++i)
 289     s[i] = 0;
 290 }
 291
 292 static void
 293 notset(s)
 294      charclass s;
 295 {
 296   int i;
 297
 298   for (i = 0; i < CHARCLASS_INTS; ++i)
 299     s[i] = ~s[i];
 300 }
 301
 302 static int
 303 equal(s1, s2)
 304      charclass s1;
 305      charclass s2;
 306 {
 307   int i;
 308
 309   for (i = 0; i < CHARCLASS_INTS; ++i)
 310     if (s1[i] != s2[i])
 311       return 0;
 312   return 1;
 313 }
 314
 315 /* A pointer to the current dfa is kept here during parsing. */
 316 static struct dfa *dfa;
 317
 318 /* Find the index of charclass s in dfa->charclasses, or allocate a new charclass. */
 319 static int
 320 charclass_index(s)
 321      charclass s;
 322 {
 323   int i;
 324
 325   for (i = 0; i < dfa->cindex; ++i)
 326     if (equal(s, dfa->charclasses[i]))
 327       return i;
 328   REALLOC_IF_NECESSARY(dfa->charclasses, charclass, dfa->calloc, dfa->cindex);
 329   ++dfa->cindex;
 330   copyset(s, dfa->charclasses[i]);
 331   return i;
 332 }
 333
 334 /* Syntax bits controlling the behavior of the lexical analyzer. */
 335 static reg_syntax_t syntax_bits, syntax_bits_set;
 336
 337 /* Flag for case-folding letters into sets. */
 338 static int case_fold;
 339
 340 /* Entry point to set syntax options. */
 341 void
 342 dfasyntax(bits, fold)
 343      reg_syntax_t bits;
 344      int fold;
 345 {
 346   syntax_bits_set = 1;
 347   syntax_bits = bits;
 348   case_fold = fold;
 349 }
 350
 351 /* Lexical analyzer.  All the dross that deals with the obnoxious
 352    GNU Regex syntax bits is located here.  The poor, suffering
 353    reader is referred to the GNU Regex documentation for the
 354    meaning of the @#%!@#%^!@ syntax bits. */
 355
 356 static char *lexstart;          /* Pointer to beginning of input string. */
 357 static char *lexptr;            /* Pointer to next input character. */
 358 static int lexleft;             /* Number of characters remaining. */
 359 static token lasttok;           /* Previous token returned; initially END. */
 360 static int laststart;           /* True if we're separated from beginning or (, |
 361                                    only by zero-width characters. */
 362 static int parens;              /* Count of outstanding left parens. */
 363 static int minrep, maxrep;      /* Repeat counts for {m,n}. */
 364
 365 /* Note that characters become unsigned here. */
 366 #define FETCH(c, eoferr)              \
 367   {                                   \
 368     if (! lexleft)                    \
 369       if (eoferr != 0)                \
 370         dfaerror(eoferr);             \
 371       else                            \
 372         return lasttok = END;         \
 373     (c) = (unsigned char) *lexptr++;  \
 374     --lexleft;                        \
 375   }
 376
 377 #ifdef __STDC__
 378 #define FUNC(F, P) static int F(int c) { return P(c); }
 379 #else
 380 #define FUNC(F, P) static int F(c) int c; { return P(c); }
 381 #endif
 382
 383 FUNC(is_alpha, ISALPHA)
 384 FUNC(is_upper, ISUPPER)
 385 FUNC(is_lower, ISLOWER)
 386 FUNC(is_digit, ISDIGIT)
 387 FUNC(is_xdigit, ISXDIGIT)
 388 FUNC(is_space, ISSPACE)
 389 FUNC(is_punct, ISPUNCT)
 390 FUNC(is_alnum, ISALNUM)
 391 FUNC(is_print, ISPRINT)
 392 FUNC(is_graph, ISGRAPH)
 393 FUNC(is_cntrl, ISCNTRL)
 394
 395 static int is_blank(c)
 396 int c;
 397 {
 398    return (c == ' ' || c == '\t');
 399 }
 400
 401 /* The following list maps the names of the Posix named character classes
 402    to predicate functions that determine whether a given character is in
 403    the class.  The leading [ has already been eaten by the lexical analyzer. */
 404 static struct {
 405   const char *name;
 406   int (*pred) _RE_ARGS((int));
 407 } prednames[] = {
 408   { ":alpha:]", is_alpha },
 409   { ":upper:]", is_upper },
 410   { ":lower:]", is_lower },
 411   { ":digit:]", is_digit },
 412   { ":xdigit:]", is_xdigit },
 413   { ":space:]", is_space },
 414   { ":punct:]", is_punct },
 415   { ":alnum:]", is_alnum },
 416   { ":print:]", is_print },
 417   { ":graph:]", is_graph },
 418   { ":cntrl:]", is_cntrl },
 419   { ":blank:]", is_blank },
 420   { 0 }
 421 };
 422
 423 static int
 424 looking_at(s)
 425      const char *s;
 426 {
 427   size_t len;
 428
 429   len = strlen(s);
 430   if (lexleft < len)
 431     return 0;
 432   return strncmp(s, lexptr, len) == 0;
 433 }
 434
 435 static token
 436 lex()
 437 {
 438   token c, c1, c2;
 439   int backslash = 0, invert;
 440   charclass ccl;
 441   int i;
 442
 443   /* Basic plan: We fetch a character.  If it's a backslash,
 444      we set the backslash flag and go through the loop again.
 445      On the plus side, this avoids having a duplicate of the
 446      main switch inside the backslash case.  On the minus side,
 447      it means that just about every case begins with
 448      "if (backslash) ...".  */
 449   for (i = 0; i < 2; ++i)
 450     {
 451       FETCH(c, 0);
 452       switch (c)
 453         {
 454         case '\\':
 455           if (backslash)
 456             goto normal_char;
 457           if (lexleft == 0)
 458             dfaerror("Unfinished \\ escape");
 459           backslash = 1;
 460           break;
 461
 462         case '^':
 463           if (backslash)
 464             goto normal_char;
 465           if (syntax_bits & RE_CONTEXT_INDEP_ANCHORS
 466               || lasttok == END
 467               || lasttok == LPAREN
 468               || lasttok == OR)
 469             return lasttok = BEGLINE;
 470           goto normal_char;
 471
 472         case '$':
 473           if (backslash)
 474             goto normal_char;
 475           if (syntax_bits & RE_CONTEXT_INDEP_ANCHORS
 476               || lexleft == 0
 477               || (syntax_bits & RE_NO_BK_PARENS
 478                   ? lexleft > 0 && *lexptr == ')'
 479                   : lexleft > 1 && lexptr[0] == '\\' && lexptr[1] == ')')
 480               || (syntax_bits & RE_NO_BK_VBAR
 481                   ? lexleft > 0 && *lexptr == '|'
 482                   : lexleft > 1 && lexptr[0] == '\\' && lexptr[1] == '|')
 483               || ((syntax_bits & RE_NEWLINE_ALT)
 484                   && lexleft > 0 && *lexptr == '\n'))
 485             return lasttok = ENDLINE;
 486           goto normal_char;
 487
 488         case '1':
 489         case '2':
 490         case '3':
 491         case '4':
 492         case '5':
 493         case '6':
 494         case '7':
 495         case '8':
 496         case '9':
 497           if (backslash && !(syntax_bits & RE_NO_BK_REFS))
 498             {
 499               laststart = 0;
 500               return lasttok = BACKREF;
 501             }
 502           goto normal_char;
 503
 504         case '`':
 505           if (backslash && !(syntax_bits & RE_NO_GNU_OPS))
 506             return lasttok = BEGLINE;   /* FIXME: should be beginning of string */
 507           goto normal_char;
 508
 509         case '\'':
 510           if (backslash && !(syntax_bits & RE_NO_GNU_OPS))
 511             return lasttok = ENDLINE;   /* FIXME: should be end of string */
 512           goto normal_char;
 513
 514         case '<':
 515           if (backslash && !(syntax_bits & RE_NO_GNU_OPS))
 516             return lasttok = BEGWORD;
 517           goto normal_char;
 518
 519         case '>':
 520           if (backslash && !(syntax_bits & RE_NO_GNU_OPS))
 521             return lasttok = ENDWORD;
 522           goto normal_char;
 523
 524         case 'b':
 525           if (backslash && !(syntax_bits & RE_NO_GNU_OPS))
 526             return lasttok = LIMWORD;
 527           goto normal_char;
 528
 529         case 'B':
 530           if (backslash && !(syntax_bits & RE_NO_GNU_OPS))
 531             return lasttok = NOTLIMWORD;
 532           goto normal_char;
 533
 534         case '?':
 535           if (syntax_bits & RE_LIMITED_OPS)
 536             goto normal_char;
 537           if (backslash != ((syntax_bits & RE_BK_PLUS_QM) != 0))
 538             goto normal_char;
 539           if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart)
 540             goto normal_char;
 541           return lasttok = QMARK;
 542
 543         case '*':
 544           if (backslash)
 545             goto normal_char;
 546           if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart)
 547             goto normal_char;
 548           return lasttok = STAR;
 549
 550         case '+':
 551           if (syntax_bits & RE_LIMITED_OPS)
 552             goto normal_char;
 553           if (backslash != ((syntax_bits & RE_BK_PLUS_QM) != 0))
 554             goto normal_char;
 555           if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart)
 556             goto normal_char;
 557           return lasttok = PLUS;
 558
 559         case '{':
 560           if (!(syntax_bits & RE_INTERVALS))
 561             goto normal_char;
 562           if (backslash != ((syntax_bits & RE_NO_BK_BRACES) == 0))
 563             goto normal_char;
 564           minrep = maxrep = 0;
 565           /* Cases:
 566              {M} - exact count
 567              {M,} - minimum count, maximum is infinity
 568              {,M} - 0 through M
 569              {M,N} - M through N */
 570           FETCH(c, "unfinished repeat count");
 571           if (ISDIGIT(c))
 572             {
 573               minrep = c - '0';
 574               for (;;)
 575                 {
 576                   FETCH(c, "unfinished repeat count");
 577                   if (!ISDIGIT(c))
 578                     break;
 579                   minrep = 10 * minrep + c - '0';
 580                 }
 581             }
 582           else if (c != ',')
 583             dfaerror("malformed repeat count");
 584           if (c == ',')
 585             for (;;)
 586               {
 587                 FETCH(c, "unfinished repeat count");
 588                 if (!ISDIGIT(c))
 589                   break;
 590                 maxrep = 10 * maxrep + c - '0';
 591               }
 592           else
 593             maxrep = minrep;
 594           if (!(syntax_bits & RE_NO_BK_BRACES))
 595             {
 596               if (c != '\\')
 597                 dfaerror("malformed repeat count");
 598               FETCH(c, "unfinished repeat count");
 599             }
 600           if (c != '}')
 601             dfaerror("malformed repeat count");
 602           laststart = 0;
 603           return lasttok = REPMN;
 604
 605         case '|':
 606           if (syntax_bits & RE_LIMITED_OPS)
 607             goto normal_char;
 608           if (backslash != ((syntax_bits & RE_NO_BK_VBAR) == 0))
 609             goto normal_char;
 610           laststart = 1;
 611           return lasttok = OR;
 612
 613         case '\n':
 614           if (syntax_bits & RE_LIMITED_OPS
 615               || backslash
 616               || !(syntax_bits & RE_NEWLINE_ALT))
 617             goto normal_char;
 618           laststart = 1;
 619           return lasttok = OR;
 620
 621         case '(':
 622           if (backslash != ((syntax_bits & RE_NO_BK_PARENS) == 0))
 623             goto normal_char;
 624           ++parens;
 625           laststart = 1;
 626           return lasttok = LPAREN;
 627
 628         case ')':
 629           if (backslash != ((syntax_bits & RE_NO_BK_PARENS) == 0))
 630             goto normal_char;
 631           if (parens == 0 && syntax_bits & RE_UNMATCHED_RIGHT_PAREN_ORD)
 632             goto normal_char;
 633           --parens;
 634           laststart = 0;
 635           return lasttok = RPAREN;
 636
 637         case '.':
 638           if (backslash)
 639             goto normal_char;
 640           zeroset(ccl);
 641           notset(ccl);
 642           if (!(syntax_bits & RE_DOT_NEWLINE))
 643             clrbit('\n', ccl);
 644           if (syntax_bits & RE_DOT_NOT_NULL)
 645             clrbit('\0', ccl);
 646           laststart = 0;
 647           return lasttok = CSET + charclass_index(ccl);
 648
 649         case 'w':
 650         case 'W':
 651           if (!backslash || (syntax_bits & RE_NO_GNU_OPS))
 652             goto normal_char;
 653           zeroset(ccl);
 654           for (c2 = 0; c2 < NOTCHAR; ++c2)
 655             if (ISALNUM(c2))
 656               setbit(c2, ccl);
 657           setbit('_', ccl);
 658           if (c == 'W')
 659             notset(ccl);
 660           laststart = 0;
 661           return lasttok = CSET + charclass_index(ccl);
 662
 663         case '[':
 664           if (backslash)
 665             goto normal_char;
 666           zeroset(ccl);
 667           FETCH(c, "Unbalanced [");
 668           if (c == '^')
 669             {
 670               FETCH(c, "Unbalanced [");
 671               invert = 1;
 672             }
 673           else
 674             invert = 0;
 675           do
 676             {
 677               /* Nobody ever said this had to be fast. :-)
 678                  Note that if we're looking at some other [:...:]
 679                  construct, we just treat it as a bunch of ordinary
 680                  characters.  We can do this because we assume
 681                  regex has checked for syntax errors before
 682                  dfa is ever called. */
 683               if (c == '[' && (syntax_bits & RE_CHAR_CLASSES))
 684                 for (c1 = 0; prednames[c1].name; ++c1)
 685                   if (looking_at(prednames[c1].name))
 686                     {
 687                         int (*pred)() = prednames[c1].pred;
 688                         if (case_fold
 689                             && (pred == is_upper || pred == is_lower))
 690                                 pred = is_alpha;
 691
 692                       for (c2 = 0; c2 < NOTCHAR; ++c2)
 693                         if ((*pred)(c2))
 694                           setbit(c2, ccl);
 695                       lexptr += strlen(prednames[c1].name);
 696                       lexleft -= strlen(prednames[c1].name);
 697                       FETCH(c1, "Unbalanced [");
 698                       goto skip;
 699                     }
 700               if (c == '\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS))
 701                 FETCH(c, "Unbalanced [");
 702               FETCH(c1, "Unbalanced [");
 703               if (c1 == '-')
 704                 {
 705                   FETCH(c2, "Unbalanced [");
 706                   if (c2 == ']')
 707                     {
 708                       /* In the case [x-], the - is an ordinary hyphen,
 709                          which is left in c1, the lookahead character. */
 710                       --lexptr;
 711                       ++lexleft;
 712                       c2 = c;
 713                     }
 714                   else
 715                     {
 716                       if (c2 == '\\'
 717                           && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS))
 718                         FETCH(c2, "Unbalanced [");
 719                       FETCH(c1, "Unbalanced [");
 720                     }
 721                 }
 722               else
 723                 c2 = c;
 724 #ifdef __FreeBSD__
 725               { token c3;
 726
 727                 if (collate_range_cmp(c, c2) > 0) {
 728                   FETCH(c2, "Invalid range");
 729                   goto skip;
 730                 }
 731
 732                 for (c3 = 0; c3 < NOTCHAR; ++c3)
 733                   if (   collate_range_cmp(c, c3) <= 0
 734                       && collate_range_cmp(c3, c2) <= 0
 735                      ) {
 736                     setbit(c3, ccl);
 737                     if (case_fold)
 738                       if (ISUPPER(c3))
 739                         setbit(tolower(c3), ccl);
 740                       else if (ISLOWER(c3))
 741                         setbit(toupper(c3), ccl);
 742                   }
 743               }
 744 #else
 745               while (c <= c2)
 746                 {
 747                   setbit(c, ccl);
 748                   if (case_fold)
 749                     if (ISUPPER(c))
 750                       setbit(tolower(c), ccl);
 751                     else if (ISLOWER(c))
 752                       setbit(toupper(c), ccl);
 753                   ++c;
 754                 }
 755 #endif
 756             skip:
 757               ;
 758             }
 759           while ((c = c1) != ']');
 760           if (invert)
 761             {
 762               notset(ccl);
 763               if (syntax_bits & RE_HAT_LISTS_NOT_NEWLINE)
 764                 clrbit('\n', ccl);
 765             }
 766           laststart = 0;
 767           return lasttok = CSET + charclass_index(ccl);
 768
 769         default:
 770         normal_char:
 771           laststart = 0;
 772           if (case_fold && ISALPHA(c))
 773             {
 774               zeroset(ccl);
 775               setbit(c, ccl);
 776               if (isupper(c))
 777                 setbit(tolower(c), ccl);
 778               else
 779                 setbit(toupper(c), ccl);
 780               return lasttok = CSET + charclass_index(ccl);
 781             }
 782           return c;
 783         }
 784     }
 785
 786   /* The above loop should consume at most a backslash
 787      and some other character. */
 788   abort();
 789   return END;   /* keeps pedantic compilers happy. */
 790 }
 791
 792 /* Recursive descent parser for regular expressions. */
 793
 794 static token tok;               /* Lookahead token. */
 795 static int depth;               /* Current depth of a hypothetical stack
 796                                    holding deferred productions.  This is
 797                                    used to determine the depth that will be
 798                                    required of the real stack later on in
 799                                    dfaanalyze(). */
 800
 801 /* Add the given token to the parse tree, maintaining the depth count and
 802    updating the maximum depth if necessary. */
 803 static void
 804 addtok(t)
 805      token t;
 806 {
 807   REALLOC_IF_NECESSARY(dfa->tokens, token, dfa->talloc, dfa->tindex);
 808   dfa->tokens[dfa->tindex++] = t;
 809
 810   switch (t)
 811     {
 812     case QMARK:
 813     case STAR:
 814     case PLUS:
 815       break;
 816
 817     case CAT:
 818     case OR:
 819     case ORTOP:
 820       --depth;
 821       break;
 822
 823     default:
 824       ++dfa->nleaves;
 825     case EMPTY:
 826       ++depth;
 827       break;
 828     }
 829   if (depth > dfa->depth)
 830     dfa->depth = depth;
 831 }
 832
 833 /* The grammar understood by the parser is as follows.
 834
 835    regexp:
 836      regexp OR branch
 837      branch
 838
 839    branch:
 840      branch closure
 841      closure
 842
 843    closure:
 844      closure QMARK
 845      closure STAR
 846      closure PLUS
 847      atom
 848
 849    atom:
 850      <normal character>
 851      CSET
 852      BACKREF
 853      BEGLINE
 854      ENDLINE
 855      BEGWORD
 856      ENDWORD
 857      LIMWORD
 858      NOTLIMWORD
 859      <empty>
 860
 861    The parser builds a parse tree in postfix form in an array of tokens. */
 862
 863 static void
 864 atom()
 865 {
 866   if ((tok >= 0 && tok < NOTCHAR) || tok >= CSET || tok == BACKREF
 867       || tok == BEGLINE || tok == ENDLINE || tok == BEGWORD
 868       || tok == ENDWORD || tok == LIMWORD || tok == NOTLIMWORD)
 869     {
 870       addtok(tok);
 871       tok = lex();
 872     }
 873   else if (tok == LPAREN)
 874     {
 875       tok = lex();
 876       regexp(0);
 877       if (tok != RPAREN)
 878         dfaerror("Unbalanced (");
 879       tok = lex();
 880     }
 881   else
 882     addtok(EMPTY);
 883 }
 884
 885 /* Return the number of tokens in the given subexpression. */
 886 static int
 887 nsubtoks(tindex)
 888 int tindex;
 889 {
 890   int ntoks1;
 891
 892   switch (dfa->tokens[tindex - 1])
 893     {
 894     default:
 895       return 1;
 896     case QMARK:
 897     case STAR:
 898     case PLUS:
 899       return 1 + nsubtoks(tindex - 1);
 900     case CAT:
 901     case OR:
 902     case ORTOP:
 903       ntoks1 = nsubtoks(tindex - 1);
 904       return 1 + ntoks1 + nsubtoks(tindex - 1 - ntoks1);
 905     }
 906 }
 907
 908 /* Copy the given subexpression to the top of the tree. */
 909 static void
 910 copytoks(tindex, ntokens)
 911      int tindex, ntokens;
 912 {
 913   int i;
 914
 915   for (i = 0; i < ntokens; ++i)
 916     addtok(dfa->tokens[tindex + i]);
 917 }
 918
 919 static void
 920 closure()
 921 {
 922   int tindex, ntokens, i;
 923
 924   atom();
 925   while (tok == QMARK || tok == STAR || tok == PLUS || tok == REPMN)
 926     if (tok == REPMN)
 927       {
 928         ntokens = nsubtoks(dfa->tindex);
 929         tindex = dfa->tindex - ntokens;
 930         if (maxrep == 0)
 931           addtok(PLUS);
 932         if (minrep == 0)
 933           addtok(QMARK);
 934         for (i = 1; i < minrep; ++i)
 935           {
 936             copytoks(tindex, ntokens);
 937             addtok(CAT);
 938           }
 939         for (; i < maxrep; ++i)
 940           {
 941             copytoks(tindex, ntokens);
 942             addtok(QMARK);
 943             addtok(CAT);
 944           }
 945         tok = lex();
 946       }
 947     else
 948       {
 949         addtok(tok);
 950         tok = lex();
 951       }
 952 }
 953
 954 static void
 955 branch()
 956 {
 957   closure();
 958   while (tok != RPAREN && tok != OR && tok >= 0)
 959     {
 960       closure();
 961       addtok(CAT);
 962     }
 963 }
 964
 965 static void
 966 regexp(toplevel)
 967      int toplevel;
 968 {
 969   branch();
 970   while (tok == OR)
 971     {
 972       tok = lex();
 973       branch();
 974       if (toplevel)
 975         addtok(ORTOP);
 976       else
 977         addtok(OR);
 978     }
 979 }
 980
 981 /* Main entry point for the parser.  S is a string to be parsed, len is the
 982    length of the string, so s can include NUL characters.  D is a pointer to
 983    the struct dfa to parse into. */
 984 void
 985 dfaparse(s, len, d)
 986      char *s;
 987      size_t len;
 988      struct dfa *d;
 989
 990 {
 991   dfa = d;
 992   lexstart = lexptr = s;
 993   lexleft = len;
 994   lasttok = END;
 995   laststart = 1;
 996   parens = 0;
 997
 998   if (! syntax_bits_set)
 999     dfaerror("No syntax specified");
1000
1001   tok = lex();
1002   depth = d->depth;
1003
1004   regexp(1);
1005
1006   if (tok != END)
1007     dfaerror("Unbalanced )");
1008
1009   addtok(END - d->nregexps);
1010   addtok(CAT);
1011
1012   if (d->nregexps)
1013     addtok(ORTOP);
1014
1015   ++d->nregexps;
1016 }
1017
1018 /* Some primitives for operating on sets of positions. */
1019
1020 /* Copy one set to another; the destination must be large enough. */
1021 static void
1022 copy(src, dst)
1023      position_set *src;
1024      position_set *dst;
1025 {
1026   int i;
1027
1028   for (i = 0; i < src->nelem; ++i)
1029     dst->elems[i] = src->elems[i];
1030   dst->nelem = src->nelem;
1031 }
1032
1033 /* Insert a position in a set.  Position sets are maintained in sorted
1034    order according to index.  If position already exists in the set with
1035    the same index then their constraints are logically or'd together.
1036    S->elems must point to an array large enough to hold the resulting set. */
1037 static void
1038 insert(p, s)
1039      position p;
1040      position_set *s;
1041 {
1042   int i;
1043   position t1, t2;
1044
1045   for (i = 0; i < s->nelem && p.index < s->elems[i].index; ++i)
1046     continue;
1047   if (i < s->nelem && p.index == s->elems[i].index)
1048     s->elems[i].constraint |= p.constraint;
1049   else
1050     {
1051       t1 = p;
1052       ++s->nelem;
1053       while (i < s->nelem)
1054         {
1055           t2 = s->elems[i];
1056           s->elems[i++] = t1;
1057           t1 = t2;
1058         }
1059     }
1060 }
1061
1062 /* Merge two sets of positions into a third.  The result is exactly as if
1063    the positions of both sets were inserted into an initially empty set. */
1064 static void
1065 merge(s1, s2, m)
1066      position_set *s1;
1067      position_set *s2;
1068      position_set *m;
1069 {
1070   int i = 0, j = 0;
1071
1072   m->nelem = 0;
1073   while (i < s1->nelem && j < s2->nelem)
1074     if (s1->elems[i].index > s2->elems[j].index)
1075       m->elems[m->nelem++] = s1->elems[i++];
1076     else if (s1->elems[i].index < s2->elems[j].index)
1077       m->elems[m->nelem++] = s2->elems[j++];
1078     else
1079       {
1080         m->elems[m->nelem] = s1->elems[i++];
1081         m->elems[m->nelem++].constraint |= s2->elems[j++].constraint;
1082       }
1083   while (i < s1->nelem)
1084     m->elems[m->nelem++] = s1->elems[i++];
1085   while (j < s2->nelem)
1086     m->elems[m->nelem++] = s2->elems[j++];
1087 }
1088
1089 /* Delete a position from a set. */
1090 static void
1091 delete(p, s)
1092      position p;
1093      position_set *s;
1094 {
1095   int i;
1096
1097   for (i = 0; i < s->nelem; ++i)
1098     if (p.index == s->elems[i].index)
1099       break;
1100   if (i < s->nelem)
1101     for (--s->nelem; i < s->nelem; ++i)
1102       s->elems[i] = s->elems[i + 1];
1103 }
1104
1105 /* Find the index of the state corresponding to the given position set with
1106    the given preceding context, or create a new state if there is no such
1107    state.  Newline and letter tell whether we got here on a newline or
1108    letter, respectively. */
1109 static int
1110 state_index(d, s, newline, letter)
1111      struct dfa *d;
1112      position_set *s;
1113      int newline;
1114      int letter;
1115 {
1116   int hash = 0;
1117   int constraint;
1118   int i, j;
1119
1120   newline = newline ? 1 : 0;
1121   letter = letter ? 1 : 0;
1122
1123   for (i = 0; i < s->nelem; ++i)
1124     hash ^= s->elems[i].index + s->elems[i].constraint;
1125
1126   /* Try to find a state that exactly matches the proposed one. */
1127   for (i = 0; i < d->sindex; ++i)
1128     {
1129       if (hash != d->states[i].hash || s->nelem != d->states[i].elems.nelem
1130           || newline != d->states[i].newline || letter != d->states[i].letter)
1131         continue;
1132       for (j = 0; j < s->nelem; ++j)
1133         if (s->elems[j].constraint
1134             != d->states[i].elems.elems[j].constraint
1135             || s->elems[j].index != d->states[i].elems.elems[j].index)
1136           break;
1137       if (j == s->nelem)
1138         return i;
1139     }
1140
1141   /* We'll have to create a new state. */
1142   REALLOC_IF_NECESSARY(d->states, dfa_state, d->salloc, d->sindex);
1143   d->states[i].hash = hash;
1144   MALLOC(d->states[i].elems.elems, position, s->nelem);
1145   copy(s, &d->states[i].elems);
1146   d->states[i].newline = newline;
1147   d->states[i].letter = letter;
1148   d->states[i].backref = 0;
1149   d->states[i].constraint = 0;
1150   d->states[i].first_end = 0;
1151   for (j = 0; j < s->nelem; ++j)
1152     if (d->tokens[s->elems[j].index] < 0)
1153       {
1154         constraint = s->elems[j].constraint;
1155         if (SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 0)
1156             || SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 1)
1157             || SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 0)
1158             || SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 1))
1159           d->states[i].constraint |= constraint;
1160         if (! d->states[i].first_end)
1161           d->states[i].first_end = d->tokens[s->elems[j].index];
1162       }
1163     else if (d->tokens[s->elems[j].index] == BACKREF)
1164       {
1165         d->states[i].constraint = NO_CONSTRAINT;
1166         d->states[i].backref = 1;
1167       }
1168
1169   ++d->sindex;
1170
1171   return i;
1172 }
1173
1174 /* Find the epsilon closure of a set of positions.  If any position of the set
1175    contains a symbol that matches the empty string in some context, replace
1176    that position with the elements of its follow labeled with an appropriate
1177    constraint.  Repeat exhaustively until no funny positions are left.
1178    S->elems must be large enough to hold the result. */
1179 static void epsclosure _RE_ARGS((position_set *s, struct dfa *d));
1180
1181 static void
1182 epsclosure(s, d)
1183      position_set *s;
1184      struct dfa *d;
1185 {
1186   int i, j;
1187   int *visited;
1188   position p, old;
1189
1190   MALLOC(visited, int, d->tindex);
1191   for (i = 0; i < d->tindex; ++i)
1192     visited[i] = 0;
1193
1194   for (i = 0; i < s->nelem; ++i)
1195     if (d->tokens[s->elems[i].index] >= NOTCHAR
1196         && d->tokens[s->elems[i].index] != BACKREF
1197         && d->tokens[s->elems[i].index] < CSET)
1198       {
1199         old = s->elems[i];
1200         p.constraint = old.constraint;
1201         delete(s->elems[i], s);
1202         if (visited[old.index])
1203           {
1204             --i;
1205             continue;
1206           }
1207         visited[old.index] = 1;
1208         switch (d->tokens[old.index])
1209           {
1210           case BEGLINE:
1211             p.constraint &= BEGLINE_CONSTRAINT;
1212             break;
1213           case ENDLINE:
1214             p.constraint &= ENDLINE_CONSTRAINT;
1215             break;
1216           case BEGWORD:
1217             p.constraint &= BEGWORD_CONSTRAINT;
1218             break;
1219           case ENDWORD:
1220             p.constraint &= ENDWORD_CONSTRAINT;
1221             break;
1222           case LIMWORD:
1223             p.constraint &= LIMWORD_CONSTRAINT;
1224             break;
1225           case NOTLIMWORD:
1226             p.constraint &= NOTLIMWORD_CONSTRAINT;
1227             break;
1228           default:
1229             break;
1230           }
1231         for (j = 0; j < d->follows[old.index].nelem; ++j)
1232           {
1233             p.index = d->follows[old.index].elems[j].index;
1234             insert(p, s);
1235           }
1236         /* Force rescan to start at the beginning. */
1237         i = -1;
1238       }
1239
1240   free(visited);
1241 }
1242
1243 /* Perform bottom-up analysis on the parse tree, computing various functions.
1244    Note that at this point, we're pretending constructs like \< are real
1245    characters rather than constraints on what can follow them.
1246
1247    Nullable:  A node is nullable if it is at the root of a regexp that can
1248    match the empty string.
1249    *  EMPTY leaves are nullable.
1250    * No other leaf is nullable.
1251    * A QMARK or STAR node is nullable.
1252    * A PLUS node is nullable if its argument is nullable.
1253    * A CAT node is nullable if both its arguments are nullable.
1254    * An OR node is nullable if either argument is nullable.
1255
1256    Firstpos:  The firstpos of a node is the set of positions (nonempty leaves)
1257    that could correspond to the first character of a string matching the
1258    regexp rooted at the given node.
1259    * EMPTY leaves have empty firstpos.
1260    * The firstpos of a nonempty leaf is that leaf itself.
1261    * The firstpos of a QMARK, STAR, or PLUS node is the firstpos of its
1262      argument.
1263    * The firstpos of a CAT node is the firstpos of the left argument, union
1264      the firstpos of the right if the left argument is nullable.
1265    * The firstpos of an OR node is the union of firstpos of each argument.
1266
1267    Lastpos:  The lastpos of a node is the set of positions that could
1268    correspond to the last character of a string matching the regexp at
1269    the given node.
1270    * EMPTY leaves have empty lastpos.
1271    * The lastpos of a nonempty leaf is that leaf itself.
1272    * The lastpos of a QMARK, STAR, or PLUS node is the lastpos of its
1273      argument.
1274    * The lastpos of a CAT node is the lastpos of its right argument, union
1275      the lastpos of the left if the right argument is nullable.
1276    * The lastpos of an OR node is the union of the lastpos of each argument.
1277
1278    Follow:  The follow of a position is the set of positions that could
1279    correspond to the character following a character matching the node in
1280    a string matching the regexp.  At this point we consider special symbols
1281    that match the empty string in some context to be just normal characters.
1282    Later, if we find that a special symbol is in a follow set, we will
1283    replace it with the elements of its follow, labeled with an appropriate
1284    constraint.
1285    * Every node in the firstpos of the argument of a STAR or PLUS node is in
1286      the follow of every node in the lastpos.
1287    * Every node in the firstpos of the second argument of a CAT node is in
1288      the follow of every node in the lastpos of the first argument.
1289
1290    Because of the postfix representation of the parse tree, the depth-first
1291    analysis is conveniently done by a linear scan with the aid of a stack.
1292    Sets are stored as arrays of the elements, obeying a stack-like allocation
1293    scheme; the number of elements in each set deeper in the stack can be
1294    used to determine the address of a particular set's array. */
1295 void
1296 dfaanalyze(d, searchflag)
1297      struct dfa *d;
1298      int searchflag;
1299 {
1300   int *nullable;                /* Nullable stack. */
1301   int *nfirstpos;               /* Element count stack for firstpos sets. */
1302   position *firstpos;           /* Array where firstpos elements are stored. */
1303   int *nlastpos;                /* Element count stack for lastpos sets. */
1304   position *lastpos;            /* Array where lastpos elements are stored. */
1305   int *nalloc;                  /* Sizes of arrays allocated to follow sets. */
1306   position_set tmp;             /* Temporary set for merging sets. */
1307   position_set merged;          /* Result of merging sets. */
1308   int wants_newline;            /* True if some position wants newline info. */
1309   int *o_nullable;
1310   int *o_nfirst, *o_nlast;
1311   position *o_firstpos, *o_lastpos;
1312   int i, j;
1313   position *pos;
1314
1315 #ifdef DEBUG
1316   fprintf(stderr, "dfaanalyze:\n");
1317   for (i = 0; i < d->tindex; ++i)
1318     {
1319       fprintf(stderr, " %d:", i);
1320       prtok(d->tokens[i]);
1321     }
1322   putc('\n', stderr);
1323 #endif
1324
1325   d->searchflag = searchflag;
1326
1327   MALLOC(nullable, int, d->depth);
1328   o_nullable = nullable;
1329   MALLOC(nfirstpos, int, d->depth);
1330   o_nfirst = nfirstpos;
1331   MALLOC(firstpos, position, d->nleaves);
1332   o_firstpos = firstpos, firstpos += d->nleaves;
1333   MALLOC(nlastpos, int, d->depth);
1334   o_nlast = nlastpos;
1335   MALLOC(lastpos, position, d->nleaves);
1336   o_lastpos = lastpos, lastpos += d->nleaves;
1337   MALLOC(nalloc, int, d->tindex);
1338   for (i = 0; i < d->tindex; ++i)
1339     nalloc[i] = 0;
1340   MALLOC(merged.elems, position, d->nleaves);
1341
1342   CALLOC(d->follows, position_set, d->tindex);
1343
1344   for (i = 0; i < d->tindex; ++i)
1345 #ifdef DEBUG
1346     {                           /* Nonsyntactic #ifdef goo... */
1347 #endif
1348     switch (d->tokens[i])
1349       {
1350       case EMPTY:
1351         /* The empty set is nullable. */
1352         *nullable++ = 1;
1353
1354         /* The firstpos and lastpos of the empty leaf are both empty. */
1355         *nfirstpos++ = *nlastpos++ = 0;
1356         break;
1357
1358       case STAR:
1359       case PLUS:
1360         /* Every element in the firstpos of the argument is in the follow
1361            of every element in the lastpos. */
1362         tmp.nelem = nfirstpos[-1];
1363         tmp.elems = firstpos;
1364         pos = lastpos;
1365         for (j = 0; j < nlastpos[-1]; ++j)
1366           {
1367             merge(&tmp, &d->follows[pos[j].index], &merged);
1368             REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems, position,
1369                                  nalloc[pos[j].index], merged.nelem - 1);
1370             copy(&merged, &d->follows[pos[j].index]);
1371           }
1372
1373       case QMARK:
1374         /* A QMARK or STAR node is automatically nullable. */
1375         if (d->tokens[i] != PLUS)
1376           nullable[-1] = 1;
1377         break;
1378
1379       case CAT:
1380         /* Every element in the firstpos of the second argument is in the
1381            follow of every element in the lastpos of the first argument. */
1382         tmp.nelem = nfirstpos[-1];
1383         tmp.elems = firstpos;
1384         pos = lastpos + nlastpos[-1];
1385         for (j = 0; j < nlastpos[-2]; ++j)
1386           {
1387             merge(&tmp, &d->follows[pos[j].index], &merged);
1388             REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems, position,
1389                                  nalloc[pos[j].index], merged.nelem - 1);
1390             copy(&merged, &d->follows[pos[j].index]);
1391           }
1392
1393         /* The firstpos of a CAT node is the firstpos of the first argument,
1394            union that of the second argument if the first is nullable. */
1395         if (nullable[-2])
1396           nfirstpos[-2] += nfirstpos[-1];
1397         else
1398           firstpos += nfirstpos[-1];
1399         --nfirstpos;
1400
1401         /* The lastpos of a CAT node is the lastpos of the second argument,
1402            union that of the first argument if the second is nullable. */
1403         if (nullable[-1])
1404           nlastpos[-2] += nlastpos[-1];
1405         else
1406           {
1407             pos = lastpos + nlastpos[-2];
1408             for (j = nlastpos[-1] - 1; j >= 0; --j)
1409               pos[j] = lastpos[j];
1410             lastpos += nlastpos[-2];
1411             nlastpos[-2] = nlastpos[-1];
1412           }
1413         --nlastpos;
1414
1415         /* A CAT node is nullable if both arguments are nullable. */
1416         nullable[-2] = nullable[-1] && nullable[-2];
1417         --nullable;
1418         break;
1419
1420       case OR:
1421       case ORTOP:
1422         /* The firstpos is the union of the firstpos of each argument. */
1423         nfirstpos[-2] += nfirstpos[-1];
1424         --nfirstpos;
1425
1426         /* The lastpos is the union of the lastpos of each argument. */
1427         nlastpos[-2] += nlastpos[-1];
1428         --nlastpos;
1429
1430         /* An OR node is nullable if either argument is nullable. */
1431         nullable[-2] = nullable[-1] || nullable[-2];
1432         --nullable;
1433         break;
1434
1435       default:
1436         /* Anything else is a nonempty position.  (Note that special
1437            constructs like \< are treated as nonempty strings here;
1438            an "epsilon closure" effectively makes them nullable later.
1439            Backreferences have to get a real position so we can detect
1440            transitions on them later.  But they are nullable. */
1441         *nullable++ = d->tokens[i] == BACKREF;
1442
1443         /* This position is in its own firstpos and lastpos. */
1444         *nfirstpos++ = *nlastpos++ = 1;
1445         --firstpos, --lastpos;
1446         firstpos->index = lastpos->index = i;
1447         firstpos->constraint = lastpos->constraint = NO_CONSTRAINT;
1448
1449         /* Allocate the follow set for this position. */
1450         nalloc[i] = 1;
1451         MALLOC(d->follows[i].elems, position, nalloc[i]);
1452         break;
1453       }
1454 #ifdef DEBUG
1455     /* ... balance the above nonsyntactic #ifdef goo... */
1456       fprintf(stderr, "node %d:", i);
1457       prtok(d->tokens[i]);
1458       putc('\n', stderr);
1459       fprintf(stderr, nullable[-1] ? " nullable: yes\n" : " nullable: no\n");
1460       fprintf(stderr, " firstpos:");
1461       for (j = nfirstpos[-1] - 1; j >= 0; --j)
1462         {
1463           fprintf(stderr, " %d:", firstpos[j].index);
1464           prtok(d->tokens[firstpos[j].index]);
1465         }
1466       fprintf(stderr, "\n lastpos:");
1467       for (j = nlastpos[-1] - 1; j >= 0; --j)
1468         {
1469           fprintf(stderr, " %d:", lastpos[j].index);
1470           prtok(d->tokens[lastpos[j].index]);
1471         }
1472       putc('\n', stderr);
1473     }
1474 #endif
1475
1476   /* For each follow set that is the follow set of a real position, replace
1477      it with its epsilon closure. */
1478   for (i = 0; i < d->tindex; ++i)
1479     if (d->tokens[i] < NOTCHAR || d->tokens[i] == BACKREF
1480         || d->tokens[i] >= CSET)
1481       {
1482 #ifdef DEBUG
1483         fprintf(stderr, "follows(%d:", i);
1484         prtok(d->tokens[i]);
1485         fprintf(stderr, "):");
1486         for (j = d->follows[i].nelem - 1; j >= 0; --j)
1487           {
1488             fprintf(stderr, " %d:", d->follows[i].elems[j].index);
1489             prtok(d->tokens[d->follows[i].elems[j].index]);
1490           }
1491         putc('\n', stderr);
1492 #endif
1493         copy(&d->follows[i], &merged);
1494         epsclosure(&merged, d);
1495         if (d->follows[i].nelem < merged.nelem)
1496           REALLOC(d->follows[i].elems, position, merged.nelem);
1497         copy(&merged, &d->follows[i]);
1498       }
1499
1500   /* Get the epsilon closure of the firstpos of the regexp.  The result will
1501      be the set of positions of state 0. */
1502   merged.nelem = 0;
1503   for (i = 0; i < nfirstpos[-1]; ++i)
1504     insert(firstpos[i], &merged);
1505   epsclosure(&merged, d);
1506
1507   /* Check if any of the positions of state 0 will want newline context. */
1508   wants_newline = 0;
1509   for (i = 0; i < merged.nelem; ++i)
1510     if (PREV_NEWLINE_DEPENDENT(merged.elems[i].constraint))
1511       wants_newline = 1;
1512
1513   /* Build the initial state. */
1514   d->salloc = 1;
1515   d->sindex = 0;
1516   MALLOC(d->states, dfa_state, d->salloc);
1517   state_index(d, &merged, wants_newline, 0);
1518
1519   free(o_nullable);
1520   free(o_nfirst);
1521   free(o_firstpos);
1522   free(o_nlast);
1523   free(o_lastpos);
1524   free(nalloc);
1525   free(merged.elems);
1526 }
1527
1528 /* Find, for each character, the transition out of state s of d, and store
1529    it in the appropriate slot of trans.
1530
1531    We divide the positions of s into groups (positions can appear in more
1532    than one group).  Each group is labeled with a set of characters that
1533    every position in the group matches (taking into account, if necessary,
1534    preceding context information of s).  For each group, find the union
1535    of the its elements' follows.  This set is the set of positions of the
1536    new state.  For each character in the group's label, set the transition
1537    on this character to be to a state corresponding to the set's positions,
1538    and its associated backward context information, if necessary.
1539
1540    If we are building a searching matcher, we include the positions of state
1541    0 in every state.
1542
1543    The collection of groups is constructed by building an equivalence-class
1544    partition of the positions of s.
1545
1546    For each position, find the set of characters C that it matches.  Eliminate
1547    any characters from C that fail on grounds of backward context.
1548
1549    Search through the groups, looking for a group whose label L has nonempty
1550    intersection with C.  If L - C is nonempty, create a new group labeled
1551    L - C and having the same positions as the current group, and set L to
1552    the intersection of L and C.  Insert the position in this group, set
1553    C = C - L, and resume scanning.
1554
1555    If after comparing with every group there are characters remaining in C,
1556    create a new group labeled with the characters of C and insert this
1557    position in that group. */
1558 void
1559 dfastate(s, d, trans)
1560      int s;
1561      struct dfa *d;
1562      int trans[];
1563 {
1564   position_set grps[NOTCHAR];   /* As many as will ever be needed. */
1565   charclass labels[NOTCHAR];    /* Labels corresponding to the groups. */
1566   int ngrps = 0;                /* Number of groups actually used. */
1567   position pos;                 /* Current position being considered. */
1568   charclass matches;            /* Set of matching characters. */
1569   int matchesf;                 /* True if matches is nonempty. */
1570   charclass intersect;          /* Intersection with some label set. */
1571   int intersectf;               /* True if intersect is nonempty. */
1572   charclass leftovers;          /* Stuff in the label that didn't match. */
1573   int leftoversf;               /* True if leftovers is nonempty. */
1574   static charclass letters;     /* Set of characters considered letters. */
1575   static charclass newline;     /* Set of characters that aren't newline. */
1576   position_set follows;         /* Union of the follows of some group. */
1577   position_set tmp;             /* Temporary space for merging sets. */
1578   int state;                    /* New state. */
1579   int wants_newline;            /* New state wants to know newline context. */
1580   int state_newline;            /* New state on a newline transition. */
1581   int wants_letter;             /* New state wants to know letter context. */
1582   int state_letter;             /* New state on a letter transition. */
1583   static int initialized;       /* Flag for static initialization. */
1584   int i, j, k;
1585
1586   /* Initialize the set of letters, if necessary. */
1587   if (! initialized)
1588     {
1589       initialized = 1;
1590       for (i = 0; i < NOTCHAR; ++i)
1591         if (ISALNUM(i))
1592           setbit(i, letters);
1593       setbit('\n', newline);
1594     }
1595
1596   zeroset(matches);
1597
1598   for (i = 0; i < d->states[s].elems.nelem; ++i)
1599     {
1600       pos = d->states[s].elems.elems[i];
1601       if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR)
1602         setbit(d->tokens[pos.index], matches);
1603       else if (d->tokens[pos.index] >= CSET)
1604         copyset(d->charclasses[d->tokens[pos.index] - CSET], matches);
1605       else
1606         continue;
1607
1608       /* Some characters may need to be eliminated from matches because
1609          they fail in the current context. */
1610       if (pos.constraint != 0xFF)
1611         {
1612           if (! MATCHES_NEWLINE_CONTEXT(pos.constraint,
1613                                          d->states[s].newline, 1))
1614             clrbit('\n', matches);
1615           if (! MATCHES_NEWLINE_CONTEXT(pos.constraint,
1616                                          d->states[s].newline, 0))
1617             for (j = 0; j < CHARCLASS_INTS; ++j)
1618               matches[j] &= newline[j];
1619           if (! MATCHES_LETTER_CONTEXT(pos.constraint,
1620                                         d->states[s].letter, 1))
1621             for (j = 0; j < CHARCLASS_INTS; ++j)
1622               matches[j] &= ~letters[j];
1623           if (! MATCHES_LETTER_CONTEXT(pos.constraint,
1624                                         d->states[s].letter, 0))
1625             for (j = 0; j < CHARCLASS_INTS; ++j)
1626               matches[j] &= letters[j];
1627
1628           /* If there are no characters left, there's no point in going on. */
1629           for (j = 0; j < CHARCLASS_INTS && !matches[j]; ++j)
1630             continue;
1631           if (j == CHARCLASS_INTS)
1632             continue;
1633         }
1634
1635       for (j = 0; j < ngrps; ++j)
1636         {
1637           /* If matches contains a single character only, and the current
1638              group's label doesn't contain that character, go on to the
1639              next group. */
1640           if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR
1641               && !tstbit(d->tokens[pos.index], labels[j]))
1642             continue;
1643
1644           /* Check if this group's label has a nonempty intersection with
1645              matches. */
1646           intersectf = 0;
1647           for (k = 0; k < CHARCLASS_INTS; ++k)
1648             (intersect[k] = matches[k] & labels[j][k]) ? (intersectf = 1) : 0;
1649           if (! intersectf)
1650             continue;
1651
1652           /* It does; now find the set differences both ways. */
1653           leftoversf = matchesf = 0;
1654           for (k = 0; k < CHARCLASS_INTS; ++k)
1655             {
1656               /* Even an optimizing compiler can't know this for sure. */
1657               int match = matches[k], label = labels[j][k];
1658
1659               (leftovers[k] = ~match & label) ? (leftoversf = 1) : 0;
1660               (matches[k] = match & ~label) ? (matchesf = 1) : 0;
1661             }
1662
1663           /* If there were leftovers, create a new group labeled with them. */
1664           if (leftoversf)
1665             {
1666               copyset(leftovers, labels[ngrps]);
1667               copyset(intersect, labels[j]);
1668               MALLOC(grps[ngrps].elems, position, d->nleaves);
1669               copy(&grps[j], &grps[ngrps]);
1670               ++ngrps;
1671             }
1672
1673           /* Put the position in the current group.  Note that there is no
1674              reason to call insert() here. */
1675           grps[j].elems[grps[j].nelem++] = pos;
1676
1677           /* If every character matching the current position has been
1678              accounted for, we're done. */
1679           if (! matchesf)
1680             break;
1681         }
1682
1683       /* If we've passed the last group, and there are still characters
1684          unaccounted for, then we'll have to create a new group. */
1685       if (j == ngrps)
1686         {
1687           copyset(matches, labels[ngrps]);
1688           zeroset(matches);
1689           MALLOC(grps[ngrps].elems, position, d->nleaves);
1690           grps[ngrps].nelem = 1;
1691           grps[ngrps].elems[0] = pos;
1692           ++ngrps;
1693         }
1694     }
1695
1696   MALLOC(follows.elems, position, d->nleaves);
1697   MALLOC(tmp.elems, position, d->nleaves);
1698
1699   /* If we are a searching matcher, the default transition is to a state
1700      containing the positions of state 0, otherwise the default transition
1701      is to fail miserably. */
1702   if (d->searchflag)
1703     {
1704       wants_newline = 0;
1705       wants_letter = 0;
1706       for (i = 0; i < d->states[0].elems.nelem; ++i)
1707         {
1708           if (PREV_NEWLINE_DEPENDENT(d->states[0].elems.elems[i].constraint))
1709             wants_newline = 1;
1710           if (PREV_LETTER_DEPENDENT(d->states[0].elems.elems[i].constraint))
1711             wants_letter = 1;
1712         }
1713       copy(&d->states[0].elems, &follows);
1714       state = state_index(d, &follows, 0, 0);
1715       if (wants_newline)
1716         state_newline = state_index(d, &follows, 1, 0);
1717       else
1718         state_newline = state;
1719       if (wants_letter)
1720         state_letter = state_index(d, &follows, 0, 1);
1721       else
1722         state_letter = state;
1723       for (i = 0; i < NOTCHAR; ++i)
1724         if (i == '\n')
1725           trans[i] = state_newline;
1726         else if (ISALNUM(i))
1727           trans[i] = state_letter;
1728         else
1729           trans[i] = state;
1730     }
1731   else
1732     for (i = 0; i < NOTCHAR; ++i)
1733       trans[i] = -1;
1734
1735   for (i = 0; i < ngrps; ++i)
1736     {
1737       follows.nelem = 0;
1738
1739       /* Find the union of the follows of the positions of the group.
1740          This is a hideously inefficient loop.  Fix it someday. */
1741       for (j = 0; j < grps[i].nelem; ++j)
1742         for (k = 0; k < d->follows[grps[i].elems[j].index].nelem; ++k)
1743           insert(d->follows[grps[i].elems[j].index].elems[k], &follows);
1744
1745       /* If we are building a searching matcher, throw in the positions
1746          of state 0 as well. */
1747       if (d->searchflag)
1748         for (j = 0; j < d->states[0].elems.nelem; ++j)
1749           insert(d->states[0].elems.elems[j], &follows);
1750
1751       /* Find out if the new state will want any context information. */
1752       wants_newline = 0;
1753       if (tstbit('\n', labels[i]))
1754         for (j = 0; j < follows.nelem; ++j)
1755           if (PREV_NEWLINE_DEPENDENT(follows.elems[j].constraint))
1756             wants_newline = 1;
1757
1758       wants_letter = 0;
1759       for (j = 0; j < CHARCLASS_INTS; ++j)
1760         if (labels[i][j] & letters[j])
1761           break;
1762       if (j < CHARCLASS_INTS)
1763         for (j = 0; j < follows.nelem; ++j)
1764           if (PREV_LETTER_DEPENDENT(follows.elems[j].constraint))
1765             wants_letter = 1;
1766
1767       /* Find the state(s) corresponding to the union of the follows. */
1768       state = state_index(d, &follows, 0, 0);
1769       if (wants_newline)
1770         state_newline = state_index(d, &follows, 1, 0);
1771       else
1772         state_newline = state;
1773       if (wants_letter)
1774         state_letter = state_index(d, &follows, 0, 1);
1775       else
1776         state_letter = state;
1777
1778       /* Set the transitions for each character in the current label. */
1779       for (j = 0; j < CHARCLASS_INTS; ++j)
1780         for (k = 0; k < INTBITS; ++k)
1781           if (labels[i][j] & 1 << k)
1782             {
1783               int c = j * INTBITS + k;
1784
1785               if (c == '\n')
1786                 trans[c] = state_newline;
1787               else if (ISALNUM(c))
1788                 trans[c] = state_letter;
1789               else if (c < NOTCHAR)
1790                 trans[c] = state;
1791             }
1792     }
1793
1794   for (i = 0; i < ngrps; ++i)
1795     free(grps[i].elems);
1796   free(follows.elems);
1797   free(tmp.elems);
1798 }
1799
1800 /* Some routines for manipulating a compiled dfa's transition tables.
1801    Each state may or may not have a transition table; if it does, and it
1802    is a non-accepting state, then d->trans[state] points to its table.
1803    If it is an accepting state then d->fails[state] points to its table.
1804    If it has no table at all, then d->trans[state] is NULL.
1805    TODO: Improve this comment, get rid of the unnecessary redundancy. */
1806
1807 static void
1808 build_state(s, d)
1809      int s;
1810      struct dfa *d;
1811 {
1812   int *trans;                   /* The new transition table. */
1813   int i;
1814
1815   /* Set an upper limit on the number of transition tables that will ever
1816      exist at once.  1024 is arbitrary.  The idea is that the frequently
1817      used transition tables will be quickly rebuilt, whereas the ones that
1818      were only needed once or twice will be cleared away. */
1819   if (d->trcount >= 1024)
1820     {
1821       for (i = 0; i < d->tralloc; ++i)
1822         if (d->trans[i])
1823           {
1824             free((ptr_t) d->trans[i]);
1825             d->trans[i] = NULL;
1826           }
1827         else if (d->fails[i])
1828           {
1829             free((ptr_t) d->fails[i]);
1830             d->fails[i] = NULL;
1831           }
1832       d->trcount = 0;
1833     }
1834
1835   ++d->trcount;
1836
1837   /* Set up the success bits for this state. */
1838   d->success[s] = 0;
1839   if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 1, d->states[s].letter, 0,
1840       s, *d))
1841     d->success[s] |= 4;
1842   if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 0, d->states[s].letter, 1,
1843       s, *d))
1844     d->success[s] |= 2;
1845   if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 0, d->states[s].letter, 0,
1846       s, *d))
1847     d->success[s] |= 1;
1848
1849   MALLOC(trans, int, NOTCHAR);
1850   dfastate(s, d, trans);
1851
1852   /* Now go through the new transition table, and make sure that the trans
1853      and fail arrays are allocated large enough to hold a pointer for the
1854      largest state mentioned in the table. */
1855   for (i = 0; i < NOTCHAR; ++i)
1856     if (trans[i] >= d->tralloc)
1857       {
1858         int oldalloc = d->tralloc;
1859
1860         while (trans[i] >= d->tralloc)
1861           d->tralloc *= 2;
1862         REALLOC(d->realtrans, int *, d->tralloc + 1);
1863         d->trans = d->realtrans + 1;
1864         REALLOC(d->fails, int *, d->tralloc);
1865         REALLOC(d->success, int, d->tralloc);
1866         REALLOC(d->newlines, int, d->tralloc);
1867         while (oldalloc < d->tralloc)
1868           {
1869             d->trans[oldalloc] = NULL;
1870             d->fails[oldalloc++] = NULL;
1871           }
1872       }
1873
1874   /* Keep the newline transition in a special place so we can use it as
1875      a sentinel. */
1876   d->newlines[s] = trans['\n'];
1877   trans['\n'] = -1;
1878
1879   if (ACCEPTING(s, *d))
1880     d->fails[s] = trans;
1881   else
1882     d->trans[s] = trans;
1883 }
1884
1885 static void
1886 build_state_zero(d)
1887      struct dfa *d;
1888 {
1889   d->tralloc = 1;
1890   d->trcount = 0;
1891   CALLOC(d->realtrans, int *, d->tralloc + 1);
1892   d->trans = d->realtrans + 1;
1893   CALLOC(d->fails, int *, d->tralloc);
1894   MALLOC(d->success, int, d->tralloc);
1895   MALLOC(d->newlines, int, d->tralloc);
1896   build_state(0, d);
1897 }
1898
1899 /* Search through a buffer looking for a match to the given struct dfa.
1900    Find the first occurrence of a string matching the regexp in the buffer,
1901    and the shortest possible version thereof.  Return a pointer to the first
1902    character after the match, or NULL if none is found.  Begin points to
1903    the beginning of the buffer, and end points to the first character after
1904    its end.  We store a newline in *end to act as a sentinel, so end had
1905    better point somewhere valid.  Newline is a flag indicating whether to
1906    allow newlines to be in the matching string.  If count is non-
1907    NULL it points to a place we're supposed to increment every time we
1908    see a newline.  Finally, if backref is non-NULL it points to a place
1909    where we're supposed to store a 1 if backreferencing happened and the
1910    match needs to be verified by a backtracking matcher.  Otherwise
1911    we store a 0 in *backref. */
1912 char *
1913 dfaexec(d, begin, end, newline, count, backref)
1914      struct dfa *d;
1915      char *begin;
1916      char *end;
1917      int newline;
1918      int *count;
1919      int *backref;
1920 {
1921   register int s, s1, tmp;      /* Current state. */
1922   register unsigned char *p;    /* Current input character. */
1923   register int **trans, *t;     /* Copy of d->trans so it can be optimized
1924                                    into a register. */
1925   static int sbit[NOTCHAR];     /* Table for anding with d->success. */
1926   static int sbit_init;
1927
1928   if (! sbit_init)
1929     {
1930       int i;
1931
1932       sbit_init = 1;
1933       for (i = 0; i < NOTCHAR; ++i)
1934         if (i == '\n')
1935           sbit[i] = 4;
1936         else if (ISALNUM(i))
1937           sbit[i] = 2;
1938         else
1939           sbit[i] = 1;
1940     }
1941
1942   if (! d->tralloc)
1943     build_state_zero(d);
1944
1945   s = s1 = 0;
1946   p = (unsigned char *) begin;
1947   trans = d->trans;
1948   *end = '\n';
1949
1950   for (;;)
1951     {
1952       /* The dreaded inner loop. */
1953       if ((t = trans[s]) != 0)
1954         do
1955           {
1956             s1 = t[*p++];
1957             if (! (t = trans[s1]))
1958               goto last_was_s;
1959             s = t[*p++];
1960           }
1961         while ((t = trans[s]) != 0);
1962       goto last_was_s1;
1963     last_was_s:
1964       tmp = s, s = s1, s1 = tmp;
1965     last_was_s1:
1966
1967       if (s >= 0 && p <= (unsigned char *) end && d->fails[s])
1968         {
1969           if (d->success[s] & sbit[*p])
1970             {
1971               if (backref)
1972                 if (d->states[s].backref)
1973                   *backref = 1;
1974                 else
1975                   *backref = 0;
1976               return (char *) p;
1977             }
1978
1979           s1 = s;
1980           s = d->fails[s][*p++];
1981           continue;
1982         }
1983
1984       /* If the previous character was a newline, count it. */
1985       if (count && (char *) p <= end && p[-1] == '\n')
1986         ++*count;
1987
1988       /* Check if we've run off the end of the buffer. */
1989       if ((char *) p > end)
1990         return NULL;
1991
1992       if (s >= 0)
1993         {
1994           build_state(s, d);
1995           trans = d->trans;
1996           continue;
1997         }
1998
1999       if (p[-1] == '\n' && newline)
2000         {
2001           s = d->newlines[s1];
2002           continue;
2003         }
2004
2005       s = 0;
2006     }
2007 }
2008
2009 /* Initialize the components of a dfa that the other routines don't
2010    initialize for themselves. */
2011 void
2012 dfainit(d)
2013      struct dfa *d;
2014 {
2015   d->calloc = 1;
2016   MALLOC(d->charclasses, charclass, d->calloc);
2017   d->cindex = 0;
2018
2019   d->talloc = 1;
2020   MALLOC(d->tokens, token, d->talloc);
2021   d->tindex = d->depth = d->nleaves = d->nregexps = 0;
2022
2023   d->searchflag = 0;
2024   d->tralloc = 0;
2025
2026   d->musts = 0;
2027 }
2028
2029 /* Parse and analyze a single string of the given length. */
2030 void
2031 dfacomp(s, len, d, searchflag)
2032      char *s;
2033      size_t len;
2034      struct dfa *d;
2035      int searchflag;
2036 {
2037   if (case_fold)        /* dummy folding in service of dfamust() */
2038     {
2039       char *lcopy;
2040       int i;
2041
2042       lcopy = malloc(len);
2043       if (!lcopy)
2044         dfaerror("out of memory");
2045
2046       /* This is a kludge. */
2047       case_fold = 0;
2048       for (i = 0; i < len; ++i)
2049         if (ISUPPER(s[i]))
2050           lcopy[i] = tolower(s[i]);
2051         else
2052           lcopy[i] = s[i];
2053
2054       dfainit(d);
2055       dfaparse(lcopy, len, d);
2056       free(lcopy);
2057       dfamust(d);
2058       d->cindex = d->tindex = d->depth = d->nleaves = d->nregexps = 0;
2059       case_fold = 1;
2060       dfaparse(s, len, d);
2061       dfaanalyze(d, searchflag);
2062     }
2063   else
2064     {
2065         dfainit(d);
2066         dfaparse(s, len, d);
2067         dfamust(d);
2068         dfaanalyze(d, searchflag);
2069     }
2070 }
2071
2072 /* Free the storage held by the components of a dfa. */
2073 void
2074 dfafree(d)
2075      struct dfa *d;
2076 {
2077   int i;
2078   struct dfamust *dm, *ndm;
2079
2080   free((ptr_t) d->charclasses);
2081   free((ptr_t) d->tokens);
2082   for (i = 0; i < d->sindex; ++i)
2083     free((ptr_t) d->states[i].elems.elems);
2084   free((ptr_t) d->states);
2085   for (i = 0; i < d->tindex; ++i)
2086     if (d->follows[i].elems)
2087       free((ptr_t) d->follows[i].elems);
2088   free((ptr_t) d->follows);
2089   for (i = 0; i < d->tralloc; ++i)
2090     if (d->trans[i])
2091       free((ptr_t) d->trans[i]);
2092     else if (d->fails[i])
2093       free((ptr_t) d->fails[i]);
2094   if (d->realtrans) free((ptr_t) d->realtrans);
2095   if (d->fails) free((ptr_t) d->fails);
2096   if (d->newlines) free((ptr_t) d->newlines);
2097   if (d->success) free((ptr_t) d->success);
2098   for (dm = d->musts; dm; dm = ndm)
2099     {
2100       ndm = dm->next;
2101       free(dm->must);
2102       free((ptr_t) dm);
2103     }
2104 }
2105
2106 /* Having found the postfix representation of the regular expression,
2107    try to find a long sequence of characters that must appear in any line
2108    containing the r.e.
2109    Finding a "longest" sequence is beyond the scope here;
2110    we take an easy way out and hope for the best.
2111    (Take "(ab|a)b"--please.)
2112
2113    We do a bottom-up calculation of sequences of characters that must appear
2114    in matches of r.e.'s represented by trees rooted at the nodes of the postfix
2115    representation:
2116         sequences that must appear at the left of the match ("left")
2117         sequences that must appear at the right of the match ("right")
2118         lists of sequences that must appear somewhere in the match ("in")
2119         sequences that must constitute the match ("is")
2120
2121    When we get to the root of the tree, we use one of the longest of its
2122    calculated "in" sequences as our answer.  The sequence we find is returned in
2123    d->must (where "d" is the single argument passed to "dfamust");
2124    the length of the sequence is returned in d->mustn.
2125
2126    The sequences calculated for the various types of node (in pseudo ANSI c)
2127    are shown below.  "p" is the operand of unary operators (and the left-hand
2128    operand of binary operators); "q" is the right-hand operand of binary
2129    operators.
2130
2131    "ZERO" means "a zero-length sequence" below.
2132
2133         Type    left            right           is              in
2134         ----    ----            -----           --              --
2135         char c  # c             # c             # c             # c
2136
2137         CSET    ZERO            ZERO            ZERO            ZERO
2138
2139         STAR    ZERO            ZERO            ZERO            ZERO
2140
2141         QMARK   ZERO            ZERO            ZERO            ZERO
2142
2143         PLUS    p->left         p->right        ZERO            p->in
2144
2145         CAT     (p->is==ZERO)?  (q->is==ZERO)?  (p->is!=ZERO && p->in plus
2146                 p->left :       q->right :      q->is!=ZERO) ?  q->in plus
2147                 p->is##q->left  p->right##q->is p->is##q->is :  p->right##q->left
2148                                                 ZERO
2149
2150         OR      longest common  longest common  (do p->is and   substrings common to
2151                 leading         trailing        q->is have same p->in and q->in
2152                 (sub)sequence   (sub)sequence   length and
2153                 of p->left      of p->right     content) ?
2154                 and q->left     and q->right    p->is : NULL
2155
2156    If there's anything else we recognize in the tree, all four sequences get set
2157    to zero-length sequences.  If there's something we don't recognize in the tree,
2158    we just return a zero-length sequence.
2159
2160    Break ties in favor of infrequent letters (choosing 'zzz' in preference to
2161    'aaa')?
2162
2163    And. . .is it here or someplace that we might ponder "optimizations" such as
2164         egrep 'psi|epsilon'     ->      egrep 'psi'
2165         egrep 'pepsi|epsilon'   ->      egrep 'epsi'
2166                                         (Yes, we now find "epsi" as a "string
2167                                         that must occur", but we might also
2168                                         simplify the *entire* r.e. being sought)
2169         grep '[c]'              ->      grep 'c'
2170         grep '(ab|a)b'          ->      grep 'ab'
2171         grep 'ab*'              ->      grep 'a'
2172         grep 'a*b'              ->      grep 'b'
2173
2174    There are several issues:
2175
2176    Is optimization easy (enough)?
2177
2178    Does optimization actually accomplish anything,
2179    or is the automaton you get from "psi|epsilon" (for example)
2180    the same as the one you get from "psi" (for example)?
2181
2182    Are optimizable r.e.'s likely to be used in real-life situations
2183    (something like 'ab*' is probably unlikely; something like is
2184    'psi|epsilon' is likelier)? */
2185
2186 static char *
2187 icatalloc(old, new)
2188      char *old;
2189      char *new;
2190 {
2191   char *result;
2192   size_t oldsize, newsize;
2193
2194   newsize = (new == NULL) ? 0 : strlen(new);
2195   if (old == NULL)
2196     oldsize = 0;
2197   else if (newsize == 0)
2198     return old;
2199   else  oldsize = strlen(old);
2200   if (old == NULL)
2201     result = (char *) malloc(newsize + 1);
2202   else
2203     result = (char *) realloc((void *) old, oldsize + newsize + 1);
2204   if (result != NULL && new != NULL)
2205     (void) strcpy(result + oldsize, new);
2206   return result;
2207 }
2208
2209 static char *
2210 icpyalloc(string)
2211      char *string;
2212 {
2213   return icatalloc((char *) NULL, string);
2214 }
2215
2216 static char *
2217 istrstr(lookin, lookfor)
2218      char *lookin;
2219      char *lookfor;
2220 {
2221   char *cp;
2222   size_t len;
2223
2224   len = strlen(lookfor);
2225   for (cp = lookin; *cp != '\0'; ++cp)
2226     if (strncmp(cp, lookfor, len) == 0)
2227       return cp;
2228   return NULL;
2229 }
2230
2231 static void
2232 ifree(cp)
2233      char *cp;
2234 {
2235   if (cp != NULL)
2236     free(cp);
2237 }
2238
2239 static void
2240 freelist(cpp)
2241      char **cpp;
2242 {
2243   int i;
2244
2245   if (cpp == NULL)
2246     return;
2247   for (i = 0; cpp[i] != NULL; ++i)
2248     {
2249       free(cpp[i]);
2250       cpp[i] = NULL;
2251     }
2252 }
2253
2254 static char **
2255 enlist(cpp, new, len)
2256      char **cpp;
2257      char *new;
2258      size_t len;
2259 {
2260   int i, j;
2261
2262   if (cpp == NULL)
2263     return NULL;
2264   if ((new = icpyalloc(new)) == NULL)
2265     {
2266       freelist(cpp);
2267       return NULL;
2268     }
2269   new[len] = '\0';
2270   /* Is there already something in the list that's new (or longer)? */
2271   for (i = 0; cpp[i] != NULL; ++i)
2272     if (istrstr(cpp[i], new) != NULL)
2273       {
2274         free(new);
2275         return cpp;
2276       }
2277   /* Eliminate any obsoleted strings. */
2278   j = 0;
2279   while (cpp[j] != NULL)
2280     if (istrstr(new, cpp[j]) == NULL)
2281       ++j;
2282     else
2283       {
2284         free(cpp[j]);
2285         if (--i == j)
2286           break;
2287         cpp[j] = cpp[i];
2288         cpp[i] = NULL;
2289       }
2290   /* Add the new string. */
2291   cpp = (char **) realloc((char *) cpp, (i + 2) * sizeof *cpp);
2292   if (cpp == NULL)
2293     return NULL;
2294   cpp[i] = new;
2295   cpp[i + 1] = NULL;
2296   return cpp;
2297 }
2298
2299 /* Given pointers to two strings, return a pointer to an allocated
2300    list of their distinct common substrings. Return NULL if something
2301    seems wild. */
2302 static char **
2303 comsubs(left, right)
2304      char *left;
2305      char *right;
2306 {
2307   char **cpp;
2308   char *lcp;
2309   char *rcp;
2310   size_t i, len;
2311
2312   if (left == NULL || right == NULL)
2313     return NULL;
2314   cpp = (char **) malloc(sizeof *cpp);
2315   if (cpp == NULL)
2316     return NULL;
2317   cpp[0] = NULL;
2318   for (lcp = left; *lcp != '\0'; ++lcp)
2319     {
2320       len = 0;
2321       rcp = index(right, *lcp);
2322       while (rcp != NULL)
2323         {
2324           for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i)
2325             continue;
2326           if (i > len)
2327             len = i;
2328           rcp = index(rcp + 1, *lcp);
2329         }
2330       if (len == 0)
2331         continue;
2332       if ((cpp = enlist(cpp, lcp, len)) == NULL)
2333         break;
2334     }
2335   return cpp;
2336 }
2337
2338 static char **
2339 addlists(old, new)
2340 char **old;
2341 char **new;
2342 {
2343   int i;
2344
2345   if (old == NULL || new == NULL)
2346     return NULL;
2347   for (i = 0; new[i] != NULL; ++i)
2348     {
2349       old = enlist(old, new[i], strlen(new[i]));
2350       if (old == NULL)
2351         break;
2352     }
2353   return old;
2354 }
2355
2356 /* Given two lists of substrings, return a new list giving substrings
2357    common to both. */
2358 static char **
2359 inboth(left, right)
2360      char **left;
2361      char **right;
2362 {
2363   char **both;
2364   char **temp;
2365   int lnum, rnum;
2366
2367   if (left == NULL || right == NULL)
2368     return NULL;
2369   both = (char **) malloc(sizeof *both);
2370   if (both == NULL)
2371     return NULL;
2372   both[0] = NULL;
2373   for (lnum = 0; left[lnum] != NULL; ++lnum)
2374     {
2375       for (rnum = 0; right[rnum] != NULL; ++rnum)
2376         {
2377           temp = comsubs(left[lnum], right[rnum]);
2378           if (temp == NULL)
2379             {
2380               freelist(both);
2381               return NULL;
2382             }
2383           both = addlists(both, temp);
2384           freelist(temp);
2385           free(temp);
2386           if (both == NULL)
2387             return NULL;
2388         }
2389     }
2390   return both;
2391 }
2392
2393 typedef struct
2394 {
2395   char **in;
2396   char *left;
2397   char *right;
2398   char *is;
2399 } must;
2400
2401 static void
2402 resetmust(mp)
2403 must *mp;
2404 {
2405   mp->left[0] = mp->right[0] = mp->is[0] = '\0';
2406   freelist(mp->in);
2407 }
2408
2409 static void
2410 dfamust(dfa)
2411 struct dfa *dfa;
2412 {
2413   must *musts;
2414   must *mp;
2415   char *result;
2416   int ri;
2417   int i;
2418   int exact;
2419   token t;
2420   static must must0;
2421   struct dfamust *dm;
2422   static char empty_string[] = "";
2423
2424   result = empty_string;
2425   exact = 0;
2426   musts = (must *) malloc((dfa->tindex + 1) * sizeof *musts);
2427   if (musts == NULL)
2428     return;
2429   mp = musts;
2430   for (i = 0; i <= dfa->tindex; ++i)
2431     mp[i] = must0;
2432   for (i = 0; i <= dfa->tindex; ++i)
2433     {
2434       mp[i].in = (char **) malloc(sizeof *mp[i].in);
2435       mp[i].left = malloc(2);
2436       mp[i].right = malloc(2);
2437       mp[i].is = malloc(2);
2438       if (mp[i].in == NULL || mp[i].left == NULL ||
2439           mp[i].right == NULL || mp[i].is == NULL)
2440         goto done;
2441       mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0';
2442       mp[i].in[0] = NULL;
2443     }
2444 #ifdef DEBUG
2445   fprintf(stderr, "dfamust:\n");
2446   for (i = 0; i < dfa->tindex; ++i)
2447     {
2448       fprintf(stderr, " %d:", i);
2449       prtok(dfa->tokens[i]);
2450     }
2451   putc('\n', stderr);
2452 #endif
2453   for (ri = 0; ri < dfa->tindex; ++ri)
2454     {
2455       switch (t = dfa->tokens[ri])
2456         {
2457         case LPAREN:
2458         case RPAREN:
2459           goto done;            /* "cannot happen" */
2460         case EMPTY:
2461         case BEGLINE:
2462         case ENDLINE:
2463         case BEGWORD:
2464         case ENDWORD:
2465         case LIMWORD:
2466         case NOTLIMWORD:
2467         case BACKREF:
2468           resetmust(mp);
2469           break;
2470         case STAR:
2471         case QMARK:
2472           if (mp <= musts)
2473             goto done;          /* "cannot happen" */
2474           --mp;
2475           resetmust(mp);
2476           break;
2477         case OR:
2478         case ORTOP:
2479           if (mp < &musts[2])
2480             goto done;          /* "cannot happen" */
2481           {
2482             char **new;
2483             must *lmp;
2484             must *rmp;
2485             int j, ln, rn, n;
2486
2487             rmp = --mp;
2488             lmp = --mp;
2489             /* Guaranteed to be.  Unlikely, but. . . */
2490             if (strcmp(lmp->is, rmp->is) != 0)
2491               lmp->is[0] = '\0';
2492             /* Left side--easy */
2493             i = 0;
2494             while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i])
2495               ++i;
2496             lmp->left[i] = '\0';
2497             /* Right side */
2498             ln = strlen(lmp->right);
2499             rn = strlen(rmp->right);
2500             n = ln;
2501             if (n > rn)
2502               n = rn;
2503             for (i = 0; i < n; ++i)
2504               if (lmp->right[ln - i - 1] != rmp->right[rn - i - 1])
2505                 break;
2506             for (j = 0; j < i; ++j)
2507               lmp->right[j] = lmp->right[(ln - i) + j];
2508             lmp->right[j] = '\0';
2509             new = inboth(lmp->in, rmp->in);
2510             if (new == NULL)
2511               goto done;
2512             freelist(lmp->in);
2513             free((char *) lmp->in);
2514             lmp->in = new;
2515           }
2516           break;
2517         case PLUS:
2518           if (mp <= musts)
2519             goto done;          /* "cannot happen" */
2520           --mp;
2521           mp->is[0] = '\0';
2522           break;
2523         case END:
2524           if (mp != &musts[1])
2525             goto done;          /* "cannot happen" */
2526           for (i = 0; musts[0].in[i] != NULL; ++i)
2527             if (strlen(musts[0].in[i]) > strlen(result))
2528               result = musts[0].in[i];
2529           if (strcmp(result, musts[0].is) == 0)
2530             exact = 1;
2531           goto done;
2532         case CAT:
2533           if (mp < &musts[2])
2534             goto done;          /* "cannot happen" */
2535           {
2536             must *lmp;
2537             must *rmp;
2538
2539             rmp = --mp;
2540             lmp = --mp;
2541             /* In.  Everything in left, plus everything in
2542                right, plus catenation of
2543                left's right and right's left. */
2544             lmp->in = addlists(lmp->in, rmp->in);
2545             if (lmp->in == NULL)
2546               goto done;
2547             if (lmp->right[0] != '\0' &&
2548                 rmp->left[0] != '\0')
2549               {
2550                 char *tp;
2551
2552                 tp = icpyalloc(lmp->right);
2553                 if (tp == NULL)
2554                   goto done;
2555                 tp = icatalloc(tp, rmp->left);
2556                 if (tp == NULL)
2557                   goto done;
2558                 lmp->in = enlist(lmp->in, tp,
2559                                  strlen(tp));
2560                 free(tp);
2561                 if (lmp->in == NULL)
2562                   goto done;
2563               }
2564             /* Left-hand */
2565             if (lmp->is[0] != '\0')
2566               {
2567                 lmp->left = icatalloc(lmp->left,
2568                                       rmp->left);
2569                 if (lmp->left == NULL)
2570                   goto done;
2571               }
2572             /* Right-hand */
2573             if (rmp->is[0] == '\0')
2574               lmp->right[0] = '\0';
2575             lmp->right = icatalloc(lmp->right, rmp->right);
2576             if (lmp->right == NULL)
2577               goto done;
2578             /* Guaranteed to be */
2579             if (lmp->is[0] != '\0' && rmp->is[0] != '\0')
2580               {
2581                 lmp->is = icatalloc(lmp->is, rmp->is);
2582                 if (lmp->is == NULL)
2583                   goto done;
2584               }
2585             else
2586               lmp->is[0] = '\0';
2587           }
2588           break;
2589         default:
2590           if (t < END)
2591             {
2592               /* "cannot happen" */
2593               goto done;
2594             }
2595           else if (t == '\0')
2596             {
2597               /* not on *my* shift */
2598               goto done;
2599             }
2600           else if (t >= CSET)
2601             {
2602               /* easy enough */
2603               resetmust(mp);
2604             }
2605           else
2606             {
2607               /* plain character */
2608               resetmust(mp);
2609               mp->is[0] = mp->left[0] = mp->right[0] = t;
2610               mp->is[1] = mp->left[1] = mp->right[1] = '\0';
2611               mp->in = enlist(mp->in, mp->is, (size_t)1);
2612               if (mp->in == NULL)
2613                 goto done;
2614             }
2615           break;
2616         }
2617 #ifdef DEBUG
2618       fprintf(stderr, " node: %d:", ri);
2619       prtok(dfa->tokens[ri]);
2620       fprintf(stderr, "\n  in:");
2621       for (i = 0; mp->in[i]; ++i)
2622         fprintf(stderr, " \"%s\"", mp->in[i]);
2623       fprintf(stderr, "\n  is: \"%s\"\n", mp->is);
2624       fprintf(stderr, "  left: \"%s\"\n", mp->left);
2625       fprintf(stderr, "  right: \"%s\"\n", mp->right);
2626 #endif
2627       ++mp;
2628     }
2629  done:
2630   if (strlen(result))
2631     {
2632       dm = (struct dfamust *) malloc(sizeof (struct dfamust));
2633       dm->exact = exact;
2634       dm->must = malloc(strlen(result) + 1);
2635       strcpy(dm->must, result);
2636       dm->next = dfa->musts;
2637       dfa->musts = dm;
2638     }
2639   mp = musts;
2640   for (i = 0; i <= dfa->tindex; ++i)
2641     {
2642       freelist(mp[i].in);
2643       ifree((char *) mp[i].in);
2644       ifree(mp[i].left);
2645       ifree(mp[i].right);
2646       ifree(mp[i].is);
2647     }
2648   free((char *) mp);
2649 }