gnu/usr.bin/grep/dfa.c

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