lib/regex.c

   1 /* Extended regular expression matching and search library,
   2    version 0.12.
   3    (Implements POSIX draft P10003.2/D11.2, except for
   4    internationalization features.)
   5
   6    Copyright (C) 1993 Free Software Foundation, Inc.
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21
  22 /* AIX requires this to be the first thing in the file. */
  23 #if defined (_AIX) && !defined (REGEX_MALLOC)
  24   #pragma alloca
  25 #endif
  26
  27 #define _GNU_SOURCE
  28
  29 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
  30 #include <sys/types.h>
  31
  32 #ifdef HAVE_CONFIG_H
  33 #include "config.h"
  34 #endif
  35
  36 /* The `emacs' switch turns on certain matching commands
  37    that make sense only in Emacs. */
  38 #ifdef emacs
  39
  40 #include "lisp.h"
  41 #include "buffer.h"
  42 #include "syntax.h"
  43
  44 /* Emacs uses `NULL' as a predicate.  */
  45 #undef NULL
  46
  47 #else  /* not emacs */
  48
  49 /* We used to test for `BSTRING' here, but only GCC and Emacs define
  50    `BSTRING', as far as I know, and neither of them use this code.  */
  51 #if HAVE_STRING_H || STDC_HEADERS
  52 #include <string.h>
  53 #ifndef bcmp
  54 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n))
  55 #endif
  56 #ifndef bcopy
  57 #define bcopy(s, d, n)  memcpy ((d), (s), (n))
  58 #endif
  59 #ifndef bzero
  60 #define bzero(s, n)     memset ((s), 0, (n))
  61 #endif
  62 #else
  63 #include <strings.h>
  64 #endif
  65
  66 #ifdef STDC_HEADERS
  67 #include <stdlib.h>
  68 #else
  69 char *malloc ();
  70 char *realloc ();
  71 #endif
  72
  73
  74 /* Define the syntax stuff for \<, \>, etc.  */
  75
  76 /* This must be nonzero for the wordchar and notwordchar pattern
  77    commands in re_match_2.  */
  78 #ifndef Sword
  79 #define Sword 1
  80 #endif
  81
  82 #ifdef SYNTAX_TABLE
  83
  84 extern char *re_syntax_table;
  85
  86 #else /* not SYNTAX_TABLE */
  87
  88 /* How many characters in the character set.  */
  89 #define CHAR_SET_SIZE 256
  90
  91 static char re_syntax_table[CHAR_SET_SIZE];
  92
  93 static void
  94 init_syntax_once ()
  95 {
  96    register int c;
  97    static int done = 0;
  98
  99    if (done)
 100      return;
 101
 102    bzero (re_syntax_table, sizeof re_syntax_table);
 103
 104    for (c = 'a'; c <= 'z'; c++)
 105      re_syntax_table[c] = Sword;
 106
 107    for (c = 'A'; c <= 'Z'; c++)
 108      re_syntax_table[c] = Sword;
 109
 110    for (c = '0'; c <= '9'; c++)
 111      re_syntax_table[c] = Sword;
 112
 113    re_syntax_table['_'] = Sword;
 114
 115    done = 1;
 116 }
 117
 118 #endif /* not SYNTAX_TABLE */
 119
 120 #define SYNTAX(c) re_syntax_table[c]
 121
 122 #endif /* not emacs */
 123 \f
 124 /* Get the interface, including the syntax bits.  */
 125 #include "regex.h"
 126
 127 /* isalpha etc. are used for the character classes.  */
 128 #include <ctype.h>
 129
 130 /* Jim Meyering writes:
 131
 132    "... Some ctype macros are valid only for character codes that
 133    isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
 134    using /bin/cc or gcc but without giving an ansi option).  So, all
 135    ctype uses should be through macros like ISPRINT...  If
 136    STDC_HEADERS is defined, then autoconf has verified that the ctype
 137    macros don't need to be guarded with references to isascii. ...
 138    Defining isascii to 1 should let any compiler worth its salt
 139    eliminate the && through constant folding."  */
 140 #if ! defined (isascii) || defined (STDC_HEADERS)
 141 #undef isascii
 142 #define isascii(c) 1
 143 #endif
 144
 145 #ifdef isblank
 146 #define ISBLANK(c) (isascii (c) && isblank (c))
 147 #else
 148 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
 149 #endif
 150 #ifdef isgraph
 151 #define ISGRAPH(c) (isascii (c) && isgraph (c))
 152 #else
 153 #define ISGRAPH(c) (isascii (c) && isprint (c) && !isspace (c))
 154 #endif
 155
 156 #define ISPRINT(c) (isascii (c) && isprint (c))
 157 #define ISDIGIT(c) (isascii (c) && isdigit (c))
 158 #define ISALNUM(c) (isascii (c) && isalnum (c))
 159 #define ISALPHA(c) (isascii (c) && isalpha (c))
 160 #define ISCNTRL(c) (isascii (c) && iscntrl (c))
 161 #define ISLOWER(c) (isascii (c) && islower (c))
 162 #define ISPUNCT(c) (isascii (c) && ispunct (c))
 163 #define ISSPACE(c) (isascii (c) && isspace (c))
 164 #define ISUPPER(c) (isascii (c) && isupper (c))
 165 #define ISXDIGIT(c) (isascii (c) && isxdigit (c))
 166
 167 #ifndef NULL
 168 #define NULL 0
 169 #endif
 170
 171 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
 172    since ours (we hope) works properly with all combinations of
 173    machines, compilers, `char' and `unsigned char' argument types.
 174    (Per Bothner suggested the basic approach.)  */
 175 #undef SIGN_EXTEND_CHAR
 176 #if __STDC__
 177 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
 178 #else  /* not __STDC__ */
 179 /* As in Harbison and Steele.  */
 180 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
 181 #endif
 182 \f
 183 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
 184    use `alloca' instead of `malloc'.  This is because using malloc in
 185    re_search* or re_match* could cause memory leaks when C-g is used in
 186    Emacs; also, malloc is slower and causes storage fragmentation.  On
 187    the other hand, malloc is more portable, and easier to debug.
 188
 189    Because we sometimes use alloca, some routines have to be macros,
 190    not functions -- `alloca'-allocated space disappears at the end of the
 191    function it is called in.  */
 192
 193 #ifdef REGEX_MALLOC
 194
 195 #define REGEX_ALLOCATE malloc
 196 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
 197
 198 #else /* not REGEX_MALLOC  */
 199
 200 /* Emacs already defines alloca, sometimes.  */
 201 #ifndef alloca
 202
 203 /* Make alloca work the best possible way.  */
 204 #ifdef __GNUC__
 205 #define alloca __builtin_alloca
 206 #else /* not __GNUC__ */
 207 #if HAVE_ALLOCA_H
 208 #include <alloca.h>
 209 #else /* not __GNUC__ or HAVE_ALLOCA_H */
 210 #ifndef _AIX /* Already did AIX, up at the top.  */
 211 char *alloca ();
 212 #endif /* not _AIX */
 213 #endif /* not HAVE_ALLOCA_H */
 214 #endif /* not __GNUC__ */
 215
 216 #endif /* not alloca */
 217
 218 #define REGEX_ALLOCATE alloca
 219
 220 /* Assumes a `char *destination' variable.  */
 221 #define REGEX_REALLOCATE(source, osize, nsize)                          \
 222   (destination = (char *) alloca (nsize),                               \
 223    bcopy (source, destination, osize),                                  \
 224    destination)
 225
 226 #endif /* not REGEX_MALLOC */
 227
 228
 229 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
 230    `string1' or just past its end.  This works if PTR is NULL, which is
 231    a good thing.  */
 232 #define FIRST_STRING_P(ptr)                                     \
 233   (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
 234
 235 /* (Re)Allocate N items of type T using malloc, or fail.  */
 236 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
 237 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
 238 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
 239
 240 #define BYTEWIDTH 8 /* In bits.  */
 241
 242 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
 243
 244 #define MAX(a, b) ((a) > (b) ? (a) : (b))
 245 #define MIN(a, b) ((a) < (b) ? (a) : (b))
 246
 247 typedef char boolean;
 248 #define false 0
 249 #define true 1
 250 \f
 251 /* These are the command codes that appear in compiled regular
 252    expressions.  Some opcodes are followed by argument bytes.  A
 253    command code can specify any interpretation whatsoever for its
 254    arguments.  Zero bytes may appear in the compiled regular expression.
 255
 256    The value of `exactn' is needed in search.c (search_buffer) in Emacs.
 257    So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
 258    `exactn' we use here must also be 1.  */
 259
 260 typedef enum
 261 {
 262   no_op = 0,
 263
 264         /* Followed by one byte giving n, then by n literal bytes.  */
 265   exactn = 1,
 266
 267         /* Matches any (more or less) character.  */
 268   anychar,
 269
 270         /* Matches any one char belonging to specified set.  First
 271            following byte is number of bitmap bytes.  Then come bytes
 272            for a bitmap saying which chars are in.  Bits in each byte
 273            are ordered low-bit-first.  A character is in the set if its
 274            bit is 1.  A character too large to have a bit in the map is
 275            automatically not in the set.  */
 276   charset,
 277
 278         /* Same parameters as charset, but match any character that is
 279            not one of those specified.  */
 280   charset_not,
 281
 282         /* Start remembering the text that is matched, for storing in a
 283            register.  Followed by one byte with the register number, in
 284            the range 0 to one less than the pattern buffer's re_nsub
 285            field.  Then followed by one byte with the number of groups
 286            inner to this one.  (This last has to be part of the
 287            start_memory only because we need it in the on_failure_jump
 288            of re_match_2.)  */
 289   start_memory,
 290
 291         /* Stop remembering the text that is matched and store it in a
 292            memory register.  Followed by one byte with the register
 293            number, in the range 0 to one less than `re_nsub' in the
 294            pattern buffer, and one byte with the number of inner groups,
 295            just like `start_memory'.  (We need the number of inner
 296            groups here because we don't have any easy way of finding the
 297            corresponding start_memory when we're at a stop_memory.)  */
 298   stop_memory,
 299
 300         /* Match a duplicate of something remembered. Followed by one
 301            byte containing the register number.  */
 302   duplicate,
 303
 304         /* Fail unless at beginning of line.  */
 305   begline,
 306
 307         /* Fail unless at end of line.  */
 308   endline,
 309
 310         /* Succeeds if at beginning of buffer (if emacs) or at beginning
 311            of string to be matched (if not).  */
 312   begbuf,
 313
 314         /* Analogously, for end of buffer/string.  */
 315   endbuf,
 316
 317         /* Followed by two byte relative address to which to jump.  */
 318   jump,
 319
 320         /* Same as jump, but marks the end of an alternative.  */
 321   jump_past_alt,
 322
 323         /* Followed by two-byte relative address of place to resume at
 324            in case of failure.  */
 325   on_failure_jump,
 326
 327         /* Like on_failure_jump, but pushes a placeholder instead of the
 328            current string position when executed.  */
 329   on_failure_keep_string_jump,
 330
 331         /* Throw away latest failure point and then jump to following
 332            two-byte relative address.  */
 333   pop_failure_jump,
 334
 335         /* Change to pop_failure_jump if know won't have to backtrack to
 336            match; otherwise change to jump.  This is used to jump
 337            back to the beginning of a repeat.  If what follows this jump
 338            clearly won't match what the repeat does, such that we can be
 339            sure that there is no use backtracking out of repetitions
 340            already matched, then we change it to a pop_failure_jump.
 341            Followed by two-byte address.  */
 342   maybe_pop_jump,
 343
 344         /* Jump to following two-byte address, and push a dummy failure
 345            point. This failure point will be thrown away if an attempt
 346            is made to use it for a failure.  A `+' construct makes this
 347            before the first repeat.  Also used as an intermediary kind
 348            of jump when compiling an alternative.  */
 349   dummy_failure_jump,
 350
 351         /* Push a dummy failure point and continue.  Used at the end of
 352            alternatives.  */
 353   push_dummy_failure,
 354
 355         /* Followed by two-byte relative address and two-byte number n.
 356            After matching N times, jump to the address upon failure.  */
 357   succeed_n,
 358
 359         /* Followed by two-byte relative address, and two-byte number n.
 360            Jump to the address N times, then fail.  */
 361   jump_n,
 362
 363         /* Set the following two-byte relative address to the
 364            subsequent two-byte number.  The address *includes* the two
 365            bytes of number.  */
 366   set_number_at,
 367
 368   wordchar,     /* Matches any word-constituent character.  */
 369   notwordchar,  /* Matches any char that is not a word-constituent.  */
 370
 371   wordbeg,      /* Succeeds if at word beginning.  */
 372   wordend,      /* Succeeds if at word end.  */
 373
 374   wordbound,    /* Succeeds if at a word boundary.  */
 375   notwordbound  /* Succeeds if not at a word boundary.  */
 376
 377 #ifdef emacs
 378   ,before_dot,  /* Succeeds if before point.  */
 379   at_dot,       /* Succeeds if at point.  */
 380   after_dot,    /* Succeeds if after point.  */
 381
 382         /* Matches any character whose syntax is specified.  Followed by
 383            a byte which contains a syntax code, e.g., Sword.  */
 384   syntaxspec,
 385
 386         /* Matches any character whose syntax is not that specified.  */
 387   notsyntaxspec
 388 #endif /* emacs */
 389 } re_opcode_t;
 390 \f
 391 /* Common operations on the compiled pattern.  */
 392
 393 /* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
 394
 395 #define STORE_NUMBER(destination, number)                               \
 396   do {                                                                  \
 397     (destination)[0] = (number) & 0377;                                 \
 398     (destination)[1] = (number) >> 8;                                   \
 399   } while (0)
 400
 401 /* Same as STORE_NUMBER, except increment DESTINATION to
 402    the byte after where the number is stored.  Therefore, DESTINATION
 403    must be an lvalue.  */
 404
 405 #define STORE_NUMBER_AND_INCR(destination, number)                      \
 406   do {                                                                  \
 407     STORE_NUMBER (destination, number);                                 \
 408     (destination) += 2;                                                 \
 409   } while (0)
 410
 411 /* Put into DESTINATION a number stored in two contiguous bytes starting
 412    at SOURCE.  */
 413
 414 #define EXTRACT_NUMBER(destination, source)                             \
 415   do {                                                                  \
 416     (destination) = *(source) & 0377;                                   \
 417     (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;           \
 418   } while (0)
 419
 420 #ifdef DEBUG
 421 static void
 422 extract_number (dest, source)
 423     int *dest;
 424     unsigned char *source;
 425 {
 426   int temp = SIGN_EXTEND_CHAR (*(source + 1));
 427   *dest = *source & 0377;
 428   *dest += temp << 8;
 429 }
 430
 431 #ifndef EXTRACT_MACROS /* To debug the macros.  */
 432 #undef EXTRACT_NUMBER
 433 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
 434 #endif /* not EXTRACT_MACROS */
 435
 436 #endif /* DEBUG */
 437
 438 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
 439    SOURCE must be an lvalue.  */
 440
 441 #define EXTRACT_NUMBER_AND_INCR(destination, source)                    \
 442   do {                                                                  \
 443     EXTRACT_NUMBER (destination, source);                               \
 444     (source) += 2;                                                      \
 445   } while (0)
 446
 447 #ifdef DEBUG
 448 static void
 449 extract_number_and_incr (destination, source)
 450     int *destination;
 451     unsigned char **source;
 452 {
 453   extract_number (destination, *source);
 454   *source += 2;
 455 }
 456
 457 #ifndef EXTRACT_MACROS
 458 #undef EXTRACT_NUMBER_AND_INCR
 459 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
 460   extract_number_and_incr (&dest, &src)
 461 #endif /* not EXTRACT_MACROS */
 462
 463 #endif /* DEBUG */
 464 \f
 465 /* If DEBUG is defined, Regex prints many voluminous messages about what
 466    it is doing (if the variable `debug' is nonzero).  If linked with the
 467    main program in `iregex.c', you can enter patterns and strings
 468    interactively.  And if linked with the main program in `main.c' and
 469    the other test files, you can run the already-written tests.  */
 470
 471 #ifdef DEBUG
 472
 473 /* We use standard I/O for debugging.  */
 474 #include <stdio.h>
 475
 476 /* It is useful to test things that ``must'' be true when debugging.  */
 477 #include <assert.h>
 478
 479 static int debug = 0;
 480
 481 #define DEBUG_STATEMENT(e) e
 482 #define DEBUG_PRINT1(x) if (debug) printf (x)
 483 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
 484 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
 485 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
 486 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)                           \
 487   if (debug) print_partial_compiled_pattern (s, e)
 488 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)                  \
 489   if (debug) print_double_string (w, s1, sz1, s2, sz2)
 490
 491
 492 extern void printchar ();
 493
 494 /* Print the fastmap in human-readable form.  */
 495
 496 void
 497 print_fastmap (fastmap)
 498     char *fastmap;
 499 {
 500   unsigned was_a_range = 0;
 501   unsigned i = 0;
 502
 503   while (i < (1 << BYTEWIDTH))
 504     {
 505       if (fastmap[i++])
 506         {
 507           was_a_range = 0;
 508           printchar (i - 1);
 509           while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
 510             {
 511               was_a_range = 1;
 512               i++;
 513             }
 514           if (was_a_range)
 515             {
 516               printf ("-");
 517               printchar (i - 1);
 518             }
 519         }
 520     }
 521   putchar ('\n');
 522 }
 523
 524
 525 /* Print a compiled pattern string in human-readable form, starting at
 526    the START pointer into it and ending just before the pointer END.  */
 527
 528 void
 529 print_partial_compiled_pattern (start, end)
 530     unsigned char *start;
 531     unsigned char *end;
 532 {
 533   int mcnt, mcnt2;
 534   unsigned char *p = start;
 535   unsigned char *pend = end;
 536
 537   if (start == NULL)
 538     {
 539       printf ("(null)\n");
 540       return;
 541     }
 542
 543   /* Loop over pattern commands.  */
 544   while (p < pend)
 545     {
 546       printf ("%d:\t", p - start);
 547
 548       switch ((re_opcode_t) *p++)
 549         {
 550         case no_op:
 551           printf ("/no_op");
 552           break;
 553
 554         case exactn:
 555           mcnt = *p++;
 556           printf ("/exactn/%d", mcnt);
 557           do
 558             {
 559               putchar ('/');
 560               printchar (*p++);
 561             }
 562           while (--mcnt);
 563           break;
 564
 565         case start_memory:
 566           mcnt = *p++;
 567           printf ("/start_memory/%d/%d", mcnt, *p++);
 568           break;
 569
 570         case stop_memory:
 571           mcnt = *p++;
 572           printf ("/stop_memory/%d/%d", mcnt, *p++);
 573           break;
 574
 575         case duplicate:
 576           printf ("/duplicate/%d", *p++);
 577           break;
 578
 579         case anychar:
 580           printf ("/anychar");
 581           break;
 582
 583         case charset:
 584         case charset_not:
 585           {
 586             register int c, last = -100;
 587             register int in_range = 0;
 588
 589             printf ("/charset [%s",
 590                     (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
 591
 592             assert (p + *p < pend);
 593
 594             for (c = 0; c < 256; c++)
 595               if (c / 8 < *p
 596                   && (p[1 + (c/8)] & (1 << (c % 8))))
 597                 {
 598                   /* Are we starting a range?  */
 599                   if (last + 1 == c && ! in_range)
 600                     {
 601                       putchar ('-');
 602                       in_range = 1;
 603                     }
 604                   /* Have we broken a range?  */
 605                   else if (last + 1 != c && in_range)
 606               {
 607                       printchar (last);
 608                       in_range = 0;
 609                     }
 610
 611                   if (! in_range)
 612                     printchar (c);
 613
 614                   last = c;
 615               }
 616
 617             if (in_range)
 618               printchar (last);
 619
 620             putchar (']');
 621
 622             p += 1 + *p;
 623           }
 624           break;
 625
 626         case begline:
 627           printf ("/begline");
 628           break;
 629
 630         case endline:
 631           printf ("/endline");
 632           break;
 633
 634         case on_failure_jump:
 635           extract_number_and_incr (&mcnt, &p);
 636           printf ("/on_failure_jump to %d", p + mcnt - start);
 637           break;
 638
 639         case on_failure_keep_string_jump:
 640           extract_number_and_incr (&mcnt, &p);
 641           printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
 642           break;
 643
 644         case dummy_failure_jump:
 645           extract_number_and_incr (&mcnt, &p);
 646           printf ("/dummy_failure_jump to %d", p + mcnt - start);
 647           break;
 648
 649         case push_dummy_failure:
 650           printf ("/push_dummy_failure");
 651           break;
 652
 653         case maybe_pop_jump:
 654           extract_number_and_incr (&mcnt, &p);
 655           printf ("/maybe_pop_jump to %d", p + mcnt - start);
 656           break;
 657
 658         case pop_failure_jump:
 659           extract_number_and_incr (&mcnt, &p);
 660           printf ("/pop_failure_jump to %d", p + mcnt - start);
 661           break;
 662
 663         case jump_past_alt:
 664           extract_number_and_incr (&mcnt, &p);
 665           printf ("/jump_past_alt to %d", p + mcnt - start);
 666           break;
 667
 668         case jump:
 669           extract_number_and_incr (&mcnt, &p);
 670           printf ("/jump to %d", p + mcnt - start);
 671           break;
 672
 673         case succeed_n:
 674           extract_number_and_incr (&mcnt, &p);
 675           extract_number_and_incr (&mcnt2, &p);
 676           printf ("/succeed_n to %d, %d times", p + mcnt - start, mcnt2);
 677           break;
 678
 679         case jump_n:
 680           extract_number_and_incr (&mcnt, &p);
 681           extract_number_and_incr (&mcnt2, &p);
 682           printf ("/jump_n to %d, %d times", p + mcnt - start, mcnt2);
 683           break;
 684
 685         case set_number_at:
 686           extract_number_and_incr (&mcnt, &p);
 687           extract_number_and_incr (&mcnt2, &p);
 688           printf ("/set_number_at location %d to %d", p + mcnt - start, mcnt2);
 689           break;
 690
 691         case wordbound:
 692           printf ("/wordbound");
 693           break;
 694
 695         case notwordbound:
 696           printf ("/notwordbound");
 697           break;
 698
 699         case wordbeg:
 700           printf ("/wordbeg");
 701           break;
 702
 703         case wordend:
 704           printf ("/wordend");
 705
 706 #ifdef emacs
 707         case before_dot:
 708           printf ("/before_dot");
 709           break;
 710
 711         case at_dot:
 712           printf ("/at_dot");
 713           break;
 714
 715         case after_dot:
 716           printf ("/after_dot");
 717           break;
 718
 719         case syntaxspec:
 720           printf ("/syntaxspec");
 721           mcnt = *p++;
 722           printf ("/%d", mcnt);
 723           break;
 724
 725         case notsyntaxspec:
 726           printf ("/notsyntaxspec");
 727           mcnt = *p++;
 728           printf ("/%d", mcnt);
 729           break;
 730 #endif /* emacs */
 731
 732         case wordchar:
 733           printf ("/wordchar");
 734           break;
 735
 736         case notwordchar:
 737           printf ("/notwordchar");
 738           break;
 739
 740         case begbuf:
 741           printf ("/begbuf");
 742           break;
 743
 744         case endbuf:
 745           printf ("/endbuf");
 746           break;
 747
 748         default:
 749           printf ("?%d", *(p-1));
 750         }
 751
 752       putchar ('\n');
 753     }
 754
 755   printf ("%d:\tend of pattern.\n", p - start);
 756 }
 757
 758
 759 void
 760 print_compiled_pattern (bufp)
 761     struct re_pattern_buffer *bufp;
 762 {
 763   unsigned char *buffer = bufp->buffer;
 764
 765   print_partial_compiled_pattern (buffer, buffer + bufp->used);
 766   printf ("%d bytes used/%d bytes allocated.\n", bufp->used, bufp->allocated);
 767
 768   if (bufp->fastmap_accurate && bufp->fastmap)
 769     {
 770       printf ("fastmap: ");
 771       print_fastmap (bufp->fastmap);
 772     }
 773
 774   printf ("re_nsub: %d\t", bufp->re_nsub);
 775   printf ("regs_alloc: %d\t", bufp->regs_allocated);
 776   printf ("can_be_null: %d\t", bufp->can_be_null);
 777   printf ("newline_anchor: %d\n", bufp->newline_anchor);
 778   printf ("no_sub: %d\t", bufp->no_sub);
 779   printf ("not_bol: %d\t", bufp->not_bol);
 780   printf ("not_eol: %d\t", bufp->not_eol);
 781   printf ("syntax: %d\n", bufp->syntax);
 782   /* Perhaps we should print the translate table?  */
 783 }
 784
 785
 786 void
 787 print_double_string (where, string1, size1, string2, size2)
 788     const char *where;
 789     const char *string1;
 790     const char *string2;
 791     int size1;
 792     int size2;
 793 {
 794   unsigned this_char;
 795
 796   if (where == NULL)
 797     printf ("(null)");
 798   else
 799     {
 800       if (FIRST_STRING_P (where))
 801         {
 802           for (this_char = where - string1; this_char < size1; this_char++)
 803             printchar (string1[this_char]);
 804
 805           where = string2;
 806         }
 807
 808       for (this_char = where - string2; this_char < size2; this_char++)
 809         printchar (string2[this_char]);
 810     }
 811 }
 812
 813 #else /* not DEBUG */
 814
 815 #undef assert
 816 #define assert(e)
 817
 818 #define DEBUG_STATEMENT(e)
 819 #define DEBUG_PRINT1(x)
 820 #define DEBUG_PRINT2(x1, x2)
 821 #define DEBUG_PRINT3(x1, x2, x3)
 822 #define DEBUG_PRINT4(x1, x2, x3, x4)
 823 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
 824 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
 825
 826 #endif /* not DEBUG */
 827 \f
 828 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
 829    also be assigned to arbitrarily: each pattern buffer stores its own
 830    syntax, so it can be changed between regex compilations.  */
 831 reg_syntax_t re_syntax_options = RE_SYNTAX_EMACS;
 832
 833
 834 /* Specify the precise syntax of regexps for compilation.  This provides
 835    for compatibility for various utilities which historically have
 836    different, incompatible syntaxes.
 837
 838    The argument SYNTAX is a bit mask comprised of the various bits
 839    defined in regex.h.  We return the old syntax.  */
 840
 841 reg_syntax_t
 842 re_set_syntax (syntax)
 843     reg_syntax_t syntax;
 844 {
 845   reg_syntax_t ret = re_syntax_options;
 846
 847   re_syntax_options = syntax;
 848   return ret;
 849 }
 850 \f
 851 /* This table gives an error message for each of the error codes listed
 852    in regex.h.  Obviously the order here has to be same as there.  */
 853
 854 static const char *re_error_msg[] =
 855   { NULL,                                       /* REG_NOERROR */
 856     "No match",                                 /* REG_NOMATCH */
 857     "Invalid regular expression",               /* REG_BADPAT */
 858     "Invalid collation character",              /* REG_ECOLLATE */
 859     "Invalid character class name",             /* REG_ECTYPE */
 860     "Trailing backslash",                       /* REG_EESCAPE */
 861     "Invalid back reference",                   /* REG_ESUBREG */
 862     "Unmatched [ or [^",                        /* REG_EBRACK */
 863     "Unmatched ( or \\(",                       /* REG_EPAREN */
 864     "Unmatched \\{",                            /* REG_EBRACE */
 865     "Invalid content of \\{\\}",                /* REG_BADBR */
 866     "Invalid range end",                        /* REG_ERANGE */
 867     "Memory exhausted",                         /* REG_ESPACE */
 868     "Invalid preceding regular expression",     /* REG_BADRPT */
 869     "Premature end of regular expression",      /* REG_EEND */
 870     "Regular expression too big",               /* REG_ESIZE */
 871     "Unmatched ) or \\)",                       /* REG_ERPAREN */
 872   };
 873 \f
 874 /* Subroutine declarations and macros for regex_compile.  */
 875
 876 static void store_op1 (), store_op2 ();
 877 static void insert_op1 (), insert_op2 ();
 878 static boolean at_begline_loc_p (), at_endline_loc_p ();
 879 static boolean group_in_compile_stack ();
 880 static reg_errcode_t compile_range ();
 881
 882 /* Fetch the next character in the uncompiled pattern---translating it
 883    if necessary.  Also cast from a signed character in the constant
 884    string passed to us by the user to an unsigned char that we can use
 885    as an array index (in, e.g., `translate').  */
 886 #define PATFETCH(c)                                                     \
 887   do {if (p == pend) return REG_EEND;                                   \
 888     c = (unsigned char) *p++;                                           \
 889     if (translate) c = translate[c];                                    \
 890   } while (0)
 891
 892 /* Fetch the next character in the uncompiled pattern, with no
 893    translation.  */
 894 #define PATFETCH_RAW(c)                                                 \
 895   do {if (p == pend) return REG_EEND;                                   \
 896     c = (unsigned char) *p++;                                           \
 897   } while (0)
 898
 899 /* Go backwards one character in the pattern.  */
 900 #define PATUNFETCH p--
 901
 902
 903 /* If `translate' is non-null, return translate[D], else just D.  We
 904    cast the subscript to translate because some data is declared as
 905    `char *', to avoid warnings when a string constant is passed.  But
 906    when we use a character as a subscript we must make it unsigned.  */
 907 #define TRANSLATE(d) (translate ? translate[(unsigned char) (d)] : (d))
 908
 909
 910 /* Macros for outputting the compiled pattern into `buffer'.  */
 911
 912 /* If the buffer isn't allocated when it comes in, use this.  */
 913 #define INIT_BUF_SIZE  32
 914
 915 /* Make sure we have at least N more bytes of space in buffer.  */
 916 #define GET_BUFFER_SPACE(n)                                             \
 917     while (b - bufp->buffer + (n) > bufp->allocated)                    \
 918       EXTEND_BUFFER ()
 919
 920 /* Make sure we have one more byte of buffer space and then add C to it.  */
 921 #define BUF_PUSH(c)                                                     \
 922   do {                                                                  \
 923     GET_BUFFER_SPACE (1);                                               \
 924     *b++ = (unsigned char) (c);                                         \
 925   } while (0)
 926
 927
 928 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
 929 #define BUF_PUSH_2(c1, c2)                                              \
 930   do {                                                                  \
 931     GET_BUFFER_SPACE (2);                                               \
 932     *b++ = (unsigned char) (c1);                                        \
 933     *b++ = (unsigned char) (c2);                                        \
 934   } while (0)
 935
 936
 937 /* As with BUF_PUSH_2, except for three bytes.  */
 938 #define BUF_PUSH_3(c1, c2, c3)                                          \
 939   do {                                                                  \
 940     GET_BUFFER_SPACE (3);                                               \
 941     *b++ = (unsigned char) (c1);                                        \
 942     *b++ = (unsigned char) (c2);                                        \
 943     *b++ = (unsigned char) (c3);                                        \
 944   } while (0)
 945
 946
 947 /* Store a jump with opcode OP at LOC to location TO.  We store a
 948    relative address offset by the three bytes the jump itself occupies.  */
 949 #define STORE_JUMP(op, loc, to) \
 950   store_op1 (op, loc, (to) - (loc) - 3)
 951
 952 /* Likewise, for a two-argument jump.  */
 953 #define STORE_JUMP2(op, loc, to, arg) \
 954   store_op2 (op, loc, (to) - (loc) - 3, arg)
 955
 956 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
 957 #define INSERT_JUMP(op, loc, to) \
 958   insert_op1 (op, loc, (to) - (loc) - 3, b)
 959
 960 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
 961 #define INSERT_JUMP2(op, loc, to, arg) \
 962   insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
 963
 964
 965 /* This is not an arbitrary limit: the arguments which represent offsets
 966    into the pattern are two bytes long.  So if 2^16 bytes turns out to
 967    be too small, many things would have to change.  */
 968 #define MAX_BUF_SIZE (1L << 16)
 969
 970
 971 /* Extend the buffer by twice its current size via realloc and
 972    reset the pointers that pointed into the old block to point to the
 973    correct places in the new one.  If extending the buffer results in it
 974    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
 975 #define EXTEND_BUFFER()                                                 \
 976   do {                                                                  \
 977     unsigned char *old_buffer = bufp->buffer;                           \
 978     if (bufp->allocated == MAX_BUF_SIZE)                                \
 979       return REG_ESIZE;                                                 \
 980     bufp->allocated <<= 1;                                              \
 981     if (bufp->allocated > MAX_BUF_SIZE)                                 \
 982       bufp->allocated = MAX_BUF_SIZE;                                   \
 983     bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
 984     if (bufp->buffer == NULL)                                           \
 985       return REG_ESPACE;                                                \
 986     /* If the buffer moved, move all the pointers into it.  */          \
 987     if (old_buffer != bufp->buffer)                                     \
 988       {                                                                 \
 989         b = (b - old_buffer) + bufp->buffer;                            \
 990         begalt = (begalt - old_buffer) + bufp->buffer;                  \
 991         if (fixup_alt_jump)                                             \
 992           fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
 993         if (laststart)                                                  \
 994           laststart = (laststart - old_buffer) + bufp->buffer;          \
 995         if (pending_exact)                                              \
 996           pending_exact = (pending_exact - old_buffer) + bufp->buffer;  \
 997       }                                                                 \
 998   } while (0)
 999
1000
1001 /* Since we have one byte reserved for the register number argument to
1002    {start,stop}_memory, the maximum number of groups we can report
1003    things about is what fits in that byte.  */
1004 #define MAX_REGNUM 255
1005
1006 /* But patterns can have more than `MAX_REGNUM' registers.  We just
1007    ignore the excess.  */
1008 typedef unsigned regnum_t;
1009
1010
1011 /* Macros for the compile stack.  */
1012
1013 /* Since offsets can go either forwards or backwards, this type needs to
1014    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
1015 typedef int pattern_offset_t;
1016
1017 typedef struct
1018 {
1019   pattern_offset_t begalt_offset;
1020   pattern_offset_t fixup_alt_jump;
1021   pattern_offset_t inner_group_offset;
1022   pattern_offset_t laststart_offset;
1023   regnum_t regnum;
1024 } compile_stack_elt_t;
1025
1026
1027 typedef struct
1028 {
1029   compile_stack_elt_t *stack;
1030   unsigned size;
1031   unsigned avail;                       /* Offset of next open position.  */
1032 } compile_stack_type;
1033
1034
1035 #define INIT_COMPILE_STACK_SIZE 32
1036
1037 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
1038 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
1039
1040 /* The next available element.  */
1041 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1042
1043
1044 /* Set the bit for character C in a list.  */
1045 #define SET_LIST_BIT(c)                               \
1046   (b[((unsigned char) (c)) / BYTEWIDTH]               \
1047    |= 1 << (((unsigned char) c) % BYTEWIDTH))
1048
1049
1050 /* Get the next unsigned number in the uncompiled pattern.  */
1051 #define GET_UNSIGNED_NUMBER(num)                                        \
1052   { if (p != pend)                                                      \
1053      {                                                                  \
1054        PATFETCH (c);                                                    \
1055        while (ISDIGIT (c))                                              \
1056          {                                                              \
1057            if (num < 0)                                                 \
1058               num = 0;                                                  \
1059            num = num * 10 + c - '0';                                    \
1060            if (p == pend)                                               \
1061               break;                                                    \
1062            PATFETCH (c);                                                \
1063          }                                                              \
1064        }                                                                \
1065     }
1066
1067 #define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
1068
1069 #define IS_CHAR_CLASS(string)                                           \
1070    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
1071     || STREQ (string, "lower") || STREQ (string, "digit")               \
1072     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
1073     || STREQ (string, "space") || STREQ (string, "print")               \
1074     || STREQ (string, "punct") || STREQ (string, "graph")               \
1075     || STREQ (string, "cntrl") || STREQ (string, "blank"))
1076 \f
1077 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
1078    Returns one of error codes defined in `regex.h', or zero for success.
1079
1080    Assumes the `allocated' (and perhaps `buffer') and `translate'
1081    fields are set in BUFP on entry.
1082
1083    If it succeeds, results are put in BUFP (if it returns an error, the
1084    contents of BUFP are undefined):
1085      `buffer' is the compiled pattern;
1086      `syntax' is set to SYNTAX;
1087      `used' is set to the length of the compiled pattern;
1088      `fastmap_accurate' is zero;
1089      `re_nsub' is the number of subexpressions in PATTERN;
1090      `not_bol' and `not_eol' are zero;
1091
1092    The `fastmap' and `newline_anchor' fields are neither
1093    examined nor set.  */
1094
1095 static reg_errcode_t
1096 regex_compile (pattern, size, syntax, bufp)
1097      const char *pattern;
1098      int size;
1099      reg_syntax_t syntax;
1100      struct re_pattern_buffer *bufp;
1101 {
1102   /* We fetch characters from PATTERN here.  Even though PATTERN is
1103      `char *' (i.e., signed), we declare these variables as unsigned, so
1104      they can be reliably used as array indices.  */
1105   register unsigned char c, c1;
1106
1107   /* A random tempory spot in PATTERN.  */
1108   const char *p1;
1109
1110   /* Points to the end of the buffer, where we should append.  */
1111   register unsigned char *b;
1112
1113   /* Keeps track of unclosed groups.  */
1114   compile_stack_type compile_stack;
1115
1116   /* Points to the current (ending) position in the pattern.  */
1117   const char *p = pattern;
1118   const char *pend = pattern + size;
1119
1120   /* How to translate the characters in the pattern.  */
1121   char *translate = bufp->translate;
1122
1123   /* Address of the count-byte of the most recently inserted `exactn'
1124      command.  This makes it possible to tell if a new exact-match
1125      character can be added to that command or if the character requires
1126      a new `exactn' command.  */
1127   unsigned char *pending_exact = 0;
1128
1129   /* Address of start of the most recently finished expression.
1130      This tells, e.g., postfix * where to find the start of its
1131      operand.  Reset at the beginning of groups and alternatives.  */
1132   unsigned char *laststart = 0;
1133
1134   /* Address of beginning of regexp, or inside of last group.  */
1135   unsigned char *begalt;
1136
1137   /* Place in the uncompiled pattern (i.e., the {) to
1138      which to go back if the interval is invalid.  */
1139   const char *beg_interval;
1140
1141   /* Address of the place where a forward jump should go to the end of
1142      the containing expression.  Each alternative of an `or' -- except the
1143      last -- ends with a forward jump of this sort.  */
1144   unsigned char *fixup_alt_jump = 0;
1145
1146   /* Counts open-groups as they are encountered.  Remembered for the
1147      matching close-group on the compile stack, so the same register
1148      number is put in the stop_memory as the start_memory.  */
1149   regnum_t regnum = 0;
1150
1151 #ifdef DEBUG
1152   DEBUG_PRINT1 ("\nCompiling pattern: ");
1153   if (debug)
1154     {
1155       unsigned debug_count;
1156
1157       for (debug_count = 0; debug_count < size; debug_count++)
1158         printchar (pattern[debug_count]);
1159       putchar ('\n');
1160     }
1161 #endif /* DEBUG */
1162
1163   /* Initialize the compile stack.  */
1164   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
1165   if (compile_stack.stack == NULL)
1166     return REG_ESPACE;
1167
1168   compile_stack.size = INIT_COMPILE_STACK_SIZE;
1169   compile_stack.avail = 0;
1170
1171   /* Initialize the pattern buffer.  */
1172   bufp->syntax = syntax;
1173   bufp->fastmap_accurate = 0;
1174   bufp->not_bol = bufp->not_eol = 0;
1175
1176   /* Set `used' to zero, so that if we return an error, the pattern
1177      printer (for debugging) will think there's no pattern.  We reset it
1178      at the end.  */
1179   bufp->used = 0;
1180
1181   /* Always count groups, whether or not bufp->no_sub is set.  */
1182   bufp->re_nsub = 0;
1183
1184 #if !defined (emacs) && !defined (SYNTAX_TABLE)
1185   /* Initialize the syntax table.  */
1186    init_syntax_once ();
1187 #endif
1188
1189   if (bufp->allocated == 0)
1190     {
1191       if (bufp->buffer)
1192         { /* If zero allocated, but buffer is non-null, try to realloc
1193              enough space.  This loses if buffer's address is bogus, but
1194              that is the user's responsibility.  */
1195           RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
1196         }
1197       else
1198         { /* Caller did not allocate a buffer.  Do it for them.  */
1199           bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
1200         }
1201       if (!bufp->buffer) return REG_ESPACE;
1202
1203       bufp->allocated = INIT_BUF_SIZE;
1204     }
1205
1206   begalt = b = bufp->buffer;
1207
1208   /* Loop through the uncompiled pattern until we're at the end.  */
1209   while (p != pend)
1210     {
1211       PATFETCH (c);
1212
1213       switch (c)
1214         {
1215         case '^':
1216           {
1217             if (   /* If at start of pattern, it's an operator.  */
1218                    p == pattern + 1
1219                    /* If context independent, it's an operator.  */
1220                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1221                    /* Otherwise, depends on what's come before.  */
1222                 || at_begline_loc_p (pattern, p, syntax))
1223               BUF_PUSH (begline);
1224             else
1225               goto normal_char;
1226           }
1227           break;
1228
1229
1230         case '$':
1231           {
1232             if (   /* If at end of pattern, it's an operator.  */
1233                    p == pend
1234                    /* If context independent, it's an operator.  */
1235                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1236                    /* Otherwise, depends on what's next.  */
1237                 || at_endline_loc_p (p, pend, syntax))
1238                BUF_PUSH (endline);
1239              else
1240                goto normal_char;
1241            }
1242            break;
1243
1244
1245         case '+':
1246         case '?':
1247           if ((syntax & RE_BK_PLUS_QM)
1248               || (syntax & RE_LIMITED_OPS))
1249             goto normal_char;
1250         handle_plus:
1251         case '*':
1252           /* If there is no previous pattern... */
1253           if (!laststart)
1254             {
1255               if (syntax & RE_CONTEXT_INVALID_OPS)
1256                 return REG_BADRPT;
1257               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1258                 goto normal_char;
1259             }
1260
1261           {
1262             /* Are we optimizing this jump?  */
1263             boolean keep_string_p = false;
1264
1265             /* 1 means zero (many) matches is allowed.  */
1266             char zero_times_ok = 0, many_times_ok = 0;
1267
1268             /* If there is a sequence of repetition chars, collapse it
1269                down to just one (the right one).  We can't combine
1270                interval operators with these because of, e.g., `a{2}*',
1271                which should only match an even number of `a's.  */
1272
1273             for (;;)
1274               {
1275                 zero_times_ok |= c != '+';
1276                 many_times_ok |= c != '?';
1277
1278                 if (p == pend)
1279                   break;
1280
1281                 PATFETCH (c);
1282
1283                 if (c == '*'
1284                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
1285                   ;
1286
1287                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
1288                   {
1289                     if (p == pend) return REG_EESCAPE;
1290
1291                     PATFETCH (c1);
1292                     if (!(c1 == '+' || c1 == '?'))
1293                       {
1294                         PATUNFETCH;
1295                         PATUNFETCH;
1296                         break;
1297                       }
1298
1299                     c = c1;
1300                   }
1301                 else
1302                   {
1303                     PATUNFETCH;
1304                     break;
1305                   }
1306
1307                 /* If we get here, we found another repeat character.  */
1308                }
1309
1310             /* Star, etc. applied to an empty pattern is equivalent
1311                to an empty pattern.  */
1312             if (!laststart)
1313               break;
1314
1315             /* Now we know whether or not zero matches is allowed
1316                and also whether or not two or more matches is allowed.  */
1317             if (many_times_ok)
1318               { /* More than one repetition is allowed, so put in at the
1319                    end a backward relative jump from `b' to before the next
1320                    jump we're going to put in below (which jumps from
1321                    laststart to after this jump).
1322
1323                    But if we are at the `*' in the exact sequence `.*\n',
1324                    insert an unconditional jump backwards to the .,
1325                    instead of the beginning of the loop.  This way we only
1326                    push a failure point once, instead of every time
1327                    through the loop.  */
1328                 assert (p - 1 > pattern);
1329
1330                 /* Allocate the space for the jump.  */
1331                 GET_BUFFER_SPACE (3);
1332
1333                 /* We know we are not at the first character of the pattern,
1334                    because laststart was nonzero.  And we've already
1335                    incremented `p', by the way, to be the character after
1336                    the `*'.  Do we have to do something analogous here
1337                    for null bytes, because of RE_DOT_NOT_NULL?  */
1338                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
1339                     && zero_times_ok
1340                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
1341                     && !(syntax & RE_DOT_NEWLINE))
1342                   { /* We have .*\n.  */
1343                     STORE_JUMP (jump, b, laststart);
1344                     keep_string_p = true;
1345                   }
1346                 else
1347                   /* Anything else.  */
1348                   STORE_JUMP (maybe_pop_jump, b, laststart - 3);
1349
1350                 /* We've added more stuff to the buffer.  */
1351                 b += 3;
1352               }
1353
1354             /* On failure, jump from laststart to b + 3, which will be the
1355                end of the buffer after this jump is inserted.  */
1356             GET_BUFFER_SPACE (3);
1357             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
1358                                        : on_failure_jump,
1359                          laststart, b + 3);
1360             pending_exact = 0;
1361             b += 3;
1362
1363             if (!zero_times_ok)
1364               {
1365                 /* At least one repetition is required, so insert a
1366                    `dummy_failure_jump' before the initial
1367                    `on_failure_jump' instruction of the loop. This
1368                    effects a skip over that instruction the first time
1369                    we hit that loop.  */
1370                 GET_BUFFER_SPACE (3);
1371                 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
1372                 b += 3;
1373               }
1374             }
1375           break;
1376
1377
1378         case '.':
1379           laststart = b;
1380           BUF_PUSH (anychar);
1381           break;
1382
1383
1384         case '[':
1385           {
1386             boolean had_char_class = false;
1387
1388             if (p == pend) return REG_EBRACK;
1389
1390             /* Ensure that we have enough space to push a charset: the
1391                opcode, the length count, and the bitset; 34 bytes in all.  */
1392             GET_BUFFER_SPACE (34);
1393
1394             laststart = b;
1395
1396             /* We test `*p == '^' twice, instead of using an if
1397                statement, so we only need one BUF_PUSH.  */
1398             BUF_PUSH (*p == '^' ? charset_not : charset);
1399             if (*p == '^')
1400               p++;
1401
1402             /* Remember the first position in the bracket expression.  */
1403             p1 = p;
1404
1405             /* Push the number of bytes in the bitmap.  */
1406             BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
1407
1408             /* Clear the whole map.  */
1409             bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
1410
1411             /* charset_not matches newline according to a syntax bit.  */
1412             if ((re_opcode_t) b[-2] == charset_not
1413                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
1414               SET_LIST_BIT ('\n');
1415
1416             /* Read in characters and ranges, setting map bits.  */
1417             for (;;)
1418               {
1419                 if (p == pend) return REG_EBRACK;
1420
1421                 PATFETCH (c);
1422
1423                 /* \ might escape characters inside [...] and [^...].  */
1424                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
1425                   {
1426                     if (p == pend) return REG_EESCAPE;
1427
1428                     PATFETCH (c1);
1429                     SET_LIST_BIT (c1);
1430                     continue;
1431                   }
1432
1433                 /* Could be the end of the bracket expression.  If it's
1434                    not (i.e., when the bracket expression is `[]' so
1435                    far), the ']' character bit gets set way below.  */
1436                 if (c == ']' && p != p1 + 1)
1437                   break;
1438
1439                 /* Look ahead to see if it's a range when the last thing
1440                    was a character class.  */
1441                 if (had_char_class && c == '-' && *p != ']')
1442                   return REG_ERANGE;
1443
1444                 /* Look ahead to see if it's a range when the last thing
1445                    was a character: if this is a hyphen not at the
1446                    beginning or the end of a list, then it's the range
1447                    operator.  */
1448                 if (c == '-'
1449                     && !(p - 2 >= pattern && p[-2] == '[')
1450                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
1451                     && *p != ']')
1452                   {
1453                     reg_errcode_t ret
1454                       = compile_range (&p, pend, translate, syntax, b);
1455                     if (ret != REG_NOERROR) return ret;
1456                   }
1457
1458                 else if (p[0] == '-' && p[1] != ']')
1459                   { /* This handles ranges made up of characters only.  */
1460                     reg_errcode_t ret;
1461
1462                     /* Move past the `-'.  */
1463                     PATFETCH (c1);
1464
1465                     ret = compile_range (&p, pend, translate, syntax, b);
1466                     if (ret != REG_NOERROR) return ret;
1467                   }
1468
1469                 /* See if we're at the beginning of a possible character
1470                    class.  */
1471
1472                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
1473                   { /* Leave room for the null.  */
1474                     char str[CHAR_CLASS_MAX_LENGTH + 1];
1475
1476                     PATFETCH (c);
1477                     c1 = 0;
1478
1479                     /* If pattern is `[[:'.  */
1480                     if (p == pend) return REG_EBRACK;
1481
1482                     for (;;)
1483                       {
1484                         PATFETCH (c);
1485                         if (c == ':' || c == ']' || p == pend
1486                             || c1 == CHAR_CLASS_MAX_LENGTH)
1487                           break;
1488                         str[c1++] = c;
1489                       }
1490                     str[c1] = '\0';
1491
1492                     /* If isn't a word bracketed by `[:' and:`]':
1493                        undo the ending character, the letters, and leave
1494                        the leading `:' and `[' (but set bits for them).  */
1495                     if (c == ':' && *p == ']')
1496                       {
1497                         int ch;
1498                         boolean is_alnum = STREQ (str, "alnum");
1499                         boolean is_alpha = STREQ (str, "alpha");
1500                         boolean is_blank = STREQ (str, "blank");
1501                         boolean is_cntrl = STREQ (str, "cntrl");
1502                         boolean is_digit = STREQ (str, "digit");
1503                         boolean is_graph = STREQ (str, "graph");
1504                         boolean is_lower = STREQ (str, "lower");
1505                         boolean is_print = STREQ (str, "print");
1506                         boolean is_punct = STREQ (str, "punct");
1507                         boolean is_space = STREQ (str, "space");
1508                         boolean is_upper = STREQ (str, "upper");
1509                         boolean is_xdigit = STREQ (str, "xdigit");
1510
1511                         if (!IS_CHAR_CLASS (str)) return REG_ECTYPE;
1512
1513                         /* Throw away the ] at the end of the character
1514                            class.  */
1515                         PATFETCH (c);
1516
1517                         if (p == pend) return REG_EBRACK;
1518
1519                         for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
1520                           {
1521                             if (   (is_alnum  && ISALNUM (ch))
1522                                 || (is_alpha  && ISALPHA (ch))
1523                                 || (is_blank  && ISBLANK (ch))
1524                                 || (is_cntrl  && ISCNTRL (ch))
1525                                 || (is_digit  && ISDIGIT (ch))
1526                                 || (is_graph  && ISGRAPH (ch))
1527                                 || (is_lower  && ISLOWER (ch))
1528                                 || (is_print  && ISPRINT (ch))
1529                                 || (is_punct  && ISPUNCT (ch))
1530                                 || (is_space  && ISSPACE (ch))
1531                                 || (is_upper  && ISUPPER (ch))
1532                                 || (is_xdigit && ISXDIGIT (ch)))
1533                             SET_LIST_BIT (ch);
1534                           }
1535                         had_char_class = true;
1536                       }
1537                     else
1538                       {
1539                         c1++;
1540                         while (c1--)
1541                           PATUNFETCH;
1542                         SET_LIST_BIT ('[');
1543                         SET_LIST_BIT (':');
1544                         had_char_class = false;
1545                       }
1546                   }
1547                 else
1548                   {
1549                     had_char_class = false;
1550                     SET_LIST_BIT (c);
1551                   }
1552               }
1553
1554             /* Discard any (non)matching list bytes that are all 0 at the
1555                end of the map.  Decrease the map-length byte too.  */
1556             while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
1557               b[-1]--;
1558             b += b[-1];
1559           }
1560           break;
1561
1562
1563         case '(':
1564           if (syntax & RE_NO_BK_PARENS)
1565             goto handle_open;
1566           else
1567             goto normal_char;
1568
1569
1570         case ')':
1571           if (syntax & RE_NO_BK_PARENS)
1572             goto handle_close;
1573           else
1574             goto normal_char;
1575
1576
1577         case '\n':
1578           if (syntax & RE_NEWLINE_ALT)
1579             goto handle_alt;
1580           else
1581             goto normal_char;
1582
1583
1584         case '|':
1585           if (syntax & RE_NO_BK_VBAR)
1586             goto handle_alt;
1587           else
1588             goto normal_char;
1589
1590
1591         case '{':
1592            if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
1593              goto handle_interval;
1594            else
1595              goto normal_char;
1596
1597
1598         case '\\':
1599           if (p == pend) return REG_EESCAPE;
1600
1601           /* Do not translate the character after the \, so that we can
1602              distinguish, e.g., \B from \b, even if we normally would
1603              translate, e.g., B to b.  */
1604           PATFETCH_RAW (c);
1605
1606           switch (c)
1607             {
1608             case '(':
1609               if (syntax & RE_NO_BK_PARENS)
1610                 goto normal_backslash;
1611
1612             handle_open:
1613               bufp->re_nsub++;
1614               regnum++;
1615
1616               if (COMPILE_STACK_FULL)
1617                 {
1618                   RETALLOC (compile_stack.stack, compile_stack.size << 1,
1619                             compile_stack_elt_t);
1620                   if (compile_stack.stack == NULL) return REG_ESPACE;
1621
1622                   compile_stack.size <<= 1;
1623                 }
1624
1625               /* These are the values to restore when we hit end of this
1626                  group.  They are all relative offsets, so that if the
1627                  whole pattern moves because of realloc, they will still
1628                  be valid.  */
1629               COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
1630               COMPILE_STACK_TOP.fixup_alt_jump
1631                 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
1632               COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
1633               COMPILE_STACK_TOP.regnum = regnum;
1634
1635               /* We will eventually replace the 0 with the number of
1636                  groups inner to this one.  But do not push a
1637                  start_memory for groups beyond the last one we can
1638                  represent in the compiled pattern.  */
1639               if (regnum <= MAX_REGNUM)
1640                 {
1641                   COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
1642                   BUF_PUSH_3 (start_memory, regnum, 0);
1643                 }
1644
1645               compile_stack.avail++;
1646
1647               fixup_alt_jump = 0;
1648               laststart = 0;
1649               begalt = b;
1650               /* If we've reached MAX_REGNUM groups, then this open
1651                  won't actually generate any code, so we'll have to
1652                  clear pending_exact explicitly.  */
1653               pending_exact = 0;
1654               break;
1655
1656
1657             case ')':
1658               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
1659
1660               if (COMPILE_STACK_EMPTY)
1661                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
1662                   goto normal_backslash;
1663                 else
1664                   return REG_ERPAREN;
1665
1666             handle_close:
1667               if (fixup_alt_jump)
1668                 { /* Push a dummy failure point at the end of the
1669                      alternative for a possible future
1670                      `pop_failure_jump' to pop.  See comments at
1671                      `push_dummy_failure' in `re_match_2'.  */
1672                   BUF_PUSH (push_dummy_failure);
1673
1674                   /* We allocated space for this jump when we assigned
1675                      to `fixup_alt_jump', in the `handle_alt' case below.  */
1676                   STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
1677                 }
1678
1679               /* See similar code for backslashed left paren above.  */
1680               if (COMPILE_STACK_EMPTY)
1681                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
1682                   goto normal_char;
1683                 else
1684                   return REG_ERPAREN;
1685
1686               /* Since we just checked for an empty stack above, this
1687                  ``can't happen''.  */
1688               assert (compile_stack.avail != 0);
1689               {
1690                 /* We don't just want to restore into `regnum', because
1691                    later groups should continue to be numbered higher,
1692                    as in `(ab)c(de)' -- the second group is #2.  */
1693                 regnum_t this_group_regnum;
1694
1695                 compile_stack.avail--;
1696                 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
1697                 fixup_alt_jump
1698                   = COMPILE_STACK_TOP.fixup_alt_jump
1699                     ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
1700                     : 0;
1701                 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
1702                 this_group_regnum = COMPILE_STACK_TOP.regnum;
1703                 /* If we've reached MAX_REGNUM groups, then this open
1704                    won't actually generate any code, so we'll have to
1705                    clear pending_exact explicitly.  */
1706                 pending_exact = 0;
1707
1708                 /* We're at the end of the group, so now we know how many
1709                    groups were inside this one.  */
1710                 if (this_group_regnum <= MAX_REGNUM)
1711                   {
1712                     unsigned char *inner_group_loc
1713                       = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
1714
1715                     *inner_group_loc = regnum - this_group_regnum;
1716                     BUF_PUSH_3 (stop_memory, this_group_regnum,
1717                                 regnum - this_group_regnum);
1718                   }
1719               }
1720               break;
1721
1722
1723             case '|':                                   /* `\|'.  */
1724               if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
1725                 goto normal_backslash;
1726             handle_alt:
1727               if (syntax & RE_LIMITED_OPS)
1728                 goto normal_char;
1729
1730               /* Insert before the previous alternative a jump which
1731                  jumps to this alternative if the former fails.  */
1732               GET_BUFFER_SPACE (3);
1733               INSERT_JUMP (on_failure_jump, begalt, b + 6);
1734               pending_exact = 0;
1735               b += 3;
1736
1737               /* The alternative before this one has a jump after it
1738                  which gets executed if it gets matched.  Adjust that
1739                  jump so it will jump to this alternative's analogous
1740                  jump (put in below, which in turn will jump to the next
1741                  (if any) alternative's such jump, etc.).  The last such
1742                  jump jumps to the correct final destination.  A picture:
1743                           _____ _____
1744                           |   | |   |
1745                           |   v |   v
1746                          a | b   | c
1747
1748                  If we are at `b', then fixup_alt_jump right now points to a
1749                  three-byte space after `a'.  We'll put in the jump, set
1750                  fixup_alt_jump to right after `b', and leave behind three
1751                  bytes which we'll fill in when we get to after `c'.  */
1752
1753               if (fixup_alt_jump)
1754                 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
1755
1756               /* Mark and leave space for a jump after this alternative,
1757                  to be filled in later either by next alternative or
1758                  when know we're at the end of a series of alternatives.  */
1759               fixup_alt_jump = b;
1760               GET_BUFFER_SPACE (3);
1761               b += 3;
1762
1763               laststart = 0;
1764               begalt = b;
1765               break;
1766
1767
1768             case '{':
1769               /* If \{ is a literal.  */
1770               if (!(syntax & RE_INTERVALS)
1771                      /* If we're at `\{' and it's not the open-interval
1772                         operator.  */
1773                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1774                   || (p - 2 == pattern  &&  p == pend))
1775                 goto normal_backslash;
1776
1777             handle_interval:
1778               {
1779                 /* If got here, then the syntax allows intervals.  */
1780
1781                 /* At least (most) this many matches must be made.  */
1782                 int lower_bound = -1, upper_bound = -1;
1783
1784                 beg_interval = p - 1;
1785
1786                 if (p == pend)
1787                   {
1788                     if (syntax & RE_NO_BK_BRACES)
1789                       goto unfetch_interval;
1790                     else
1791                       return REG_EBRACE;
1792                   }
1793
1794                 GET_UNSIGNED_NUMBER (lower_bound);
1795
1796                 if (c == ',')
1797                   {
1798                     GET_UNSIGNED_NUMBER (upper_bound);
1799                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
1800                   }
1801                 else
1802                   /* Interval such as `{1}' => match exactly once. */
1803                   upper_bound = lower_bound;
1804
1805                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
1806                     || lower_bound > upper_bound)
1807                   {
1808                     if (syntax & RE_NO_BK_BRACES)
1809                       goto unfetch_interval;
1810                     else
1811                       return REG_BADBR;
1812                   }
1813
1814                 if (!(syntax & RE_NO_BK_BRACES))
1815                   {
1816                     if (c != '\\') return REG_EBRACE;
1817
1818                     PATFETCH (c);
1819                   }
1820
1821                 if (c != '}')
1822                   {
1823                     if (syntax & RE_NO_BK_BRACES)
1824                       goto unfetch_interval;
1825                     else
1826                       return REG_BADBR;
1827                   }
1828
1829                 /* We just parsed a valid interval.  */
1830
1831                 /* If it's invalid to have no preceding re.  */
1832                 if (!laststart)
1833                   {
1834                     if (syntax & RE_CONTEXT_INVALID_OPS)
1835                       return REG_BADRPT;
1836                     else if (syntax & RE_CONTEXT_INDEP_OPS)
1837                       laststart = b;
1838                     else
1839                       goto unfetch_interval;
1840                   }
1841
1842                 /* If the upper bound is zero, don't want to succeed at
1843                    all; jump from `laststart' to `b + 3', which will be
1844                    the end of the buffer after we insert the jump.  */
1845                  if (upper_bound == 0)
1846                    {
1847                      GET_BUFFER_SPACE (3);
1848                      INSERT_JUMP (jump, laststart, b + 3);
1849                      b += 3;
1850                    }
1851
1852                  /* Otherwise, we have a nontrivial interval.  When
1853                     we're all done, the pattern will look like:
1854                       set_number_at <jump count> <upper bound>
1855                       set_number_at <succeed_n count> <lower bound>
1856                       succeed_n <after jump addr> <succed_n count>
1857                       <body of loop>
1858                       jump_n <succeed_n addr> <jump count>
1859                     (The upper bound and `jump_n' are omitted if
1860                     `upper_bound' is 1, though.)  */
1861                  else
1862                    { /* If the upper bound is > 1, we need to insert
1863                         more at the end of the loop.  */
1864                      unsigned nbytes = 10 + (upper_bound > 1) * 10;
1865
1866                      GET_BUFFER_SPACE (nbytes);
1867
1868                      /* Initialize lower bound of the `succeed_n', even
1869                         though it will be set during matching by its
1870                         attendant `set_number_at' (inserted next),
1871                         because `re_compile_fastmap' needs to know.
1872                         Jump to the `jump_n' we might insert below.  */
1873                      INSERT_JUMP2 (succeed_n, laststart,
1874                                    b + 5 + (upper_bound > 1) * 5,
1875                                    lower_bound);
1876                      b += 5;
1877
1878                      /* Code to initialize the lower bound.  Insert
1879                         before the `succeed_n'.  The `5' is the last two
1880                         bytes of this `set_number_at', plus 3 bytes of
1881                         the following `succeed_n'.  */
1882                      insert_op2 (set_number_at, laststart, 5, lower_bound, b);
1883                      b += 5;
1884
1885                      if (upper_bound > 1)
1886                        { /* More than one repetition is allowed, so
1887                             append a backward jump to the `succeed_n'
1888                             that starts this interval.
1889
1890                             When we've reached this during matching,
1891                             we'll have matched the interval once, so
1892                             jump back only `upper_bound - 1' times.  */
1893                          STORE_JUMP2 (jump_n, b, laststart + 5,
1894                                       upper_bound - 1);
1895                          b += 5;
1896
1897                          /* The location we want to set is the second
1898                             parameter of the `jump_n'; that is `b-2' as
1899                             an absolute address.  `laststart' will be
1900                             the `set_number_at' we're about to insert;
1901                             `laststart+3' the number to set, the source
1902                             for the relative address.  But we are
1903                             inserting into the middle of the pattern --
1904                             so everything is getting moved up by 5.
1905                             Conclusion: (b - 2) - (laststart + 3) + 5,
1906                             i.e., b - laststart.
1907
1908                             We insert this at the beginning of the loop
1909                             so that if we fail during matching, we'll
1910                             reinitialize the bounds.  */
1911                          insert_op2 (set_number_at, laststart, b - laststart,
1912                                      upper_bound - 1, b);
1913                          b += 5;
1914                        }
1915                    }
1916                 pending_exact = 0;
1917                 beg_interval = NULL;
1918               }
1919               break;
1920
1921             unfetch_interval:
1922               /* If an invalid interval, match the characters as literals.  */
1923                assert (beg_interval);
1924                p = beg_interval;
1925                beg_interval = NULL;
1926
1927                /* normal_char and normal_backslash need `c'.  */
1928                PATFETCH (c);
1929
1930                if (!(syntax & RE_NO_BK_BRACES))
1931                  {
1932                    if (p > pattern  &&  p[-1] == '\\')
1933                      goto normal_backslash;
1934                  }
1935                goto normal_char;
1936
1937 #ifdef emacs
1938             /* There is no way to specify the before_dot and after_dot
1939                operators.  rms says this is ok.  --karl  */
1940             case '=':
1941               BUF_PUSH (at_dot);
1942               break;
1943
1944             case 's':
1945               laststart = b;
1946               PATFETCH (c);
1947               BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
1948               break;
1949
1950             case 'S':
1951               laststart = b;
1952               PATFETCH (c);
1953               BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
1954               break;
1955 #endif /* emacs */
1956
1957
1958             case 'w':
1959               laststart = b;
1960               BUF_PUSH (wordchar);
1961               break;
1962
1963
1964             case 'W':
1965               laststart = b;
1966               BUF_PUSH (notwordchar);
1967               break;
1968
1969
1970             case '<':
1971               BUF_PUSH (wordbeg);
1972               break;
1973
1974             case '>':
1975               BUF_PUSH (wordend);
1976               break;
1977
1978             case 'b':
1979               BUF_PUSH (wordbound);
1980               break;
1981
1982             case 'B':
1983               BUF_PUSH (notwordbound);
1984               break;
1985
1986             case '`':
1987               BUF_PUSH (begbuf);
1988               break;
1989
1990             case '\'':
1991               BUF_PUSH (endbuf);
1992               break;
1993
1994             case '1': case '2': case '3': case '4': case '5':
1995             case '6': case '7': case '8': case '9':
1996               if (syntax & RE_NO_BK_REFS)
1997                 goto normal_char;
1998
1999               c1 = c - '0';
2000
2001               if (c1 > regnum)
2002                 return REG_ESUBREG;
2003
2004               /* Can't back reference to a subexpression if inside of it.  */
2005               if (group_in_compile_stack (compile_stack, c1))
2006                 goto normal_char;
2007
2008               laststart = b;
2009               BUF_PUSH_2 (duplicate, c1);
2010               break;
2011
2012
2013             case '+':
2014             case '?':
2015               if (syntax & RE_BK_PLUS_QM)
2016                 goto handle_plus;
2017               else
2018                 goto normal_backslash;
2019
2020             default:
2021             normal_backslash:
2022               /* You might think it would be useful for \ to mean
2023                  not to translate; but if we don't translate it
2024                  it will never match anything.  */
2025               c = TRANSLATE (c);
2026               goto normal_char;
2027             }
2028           break;
2029
2030
2031         default:
2032         /* Expects the character in `c'.  */
2033         normal_char:
2034               /* If no exactn currently being built.  */
2035           if (!pending_exact
2036
2037               /* If last exactn not at current position.  */
2038               || pending_exact + *pending_exact + 1 != b
2039
2040               /* We have only one byte following the exactn for the count.  */
2041               || *pending_exact == (1 << BYTEWIDTH) - 1
2042
2043               /* If followed by a repetition operator.  */
2044               || *p == '*' || *p == '^'
2045               || ((syntax & RE_BK_PLUS_QM)
2046                   ? *p == '\\' && (p[1] == '+' || p[1] == '?')
2047                   : (*p == '+' || *p == '?'))
2048               || ((syntax & RE_INTERVALS)
2049                   && ((syntax & RE_NO_BK_BRACES)
2050                       ? *p == '{'
2051                       : (p[0] == '\\' && p[1] == '{'))))
2052             {
2053               /* Start building a new exactn.  */
2054
2055               laststart = b;
2056
2057               BUF_PUSH_2 (exactn, 0);
2058               pending_exact = b - 1;
2059             }
2060
2061           BUF_PUSH (c);
2062           (*pending_exact)++;
2063           break;
2064         } /* switch (c) */
2065     } /* while p != pend */
2066
2067
2068   /* Through the pattern now.  */
2069
2070   if (fixup_alt_jump)
2071     STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2072
2073   if (!COMPILE_STACK_EMPTY)
2074     return REG_EPAREN;
2075
2076   free (compile_stack.stack);
2077
2078   /* We have succeeded; set the length of the buffer.  */
2079   bufp->used = b - bufp->buffer;
2080
2081 #ifdef DEBUG
2082   if (debug)
2083     {
2084       DEBUG_PRINT1 ("\nCompiled pattern: \n");
2085       print_compiled_pattern (bufp);
2086     }
2087 #endif /* DEBUG */
2088
2089   return REG_NOERROR;
2090 } /* regex_compile */
2091 \f
2092 /* Subroutines for `regex_compile'.  */
2093
2094 /* Store OP at LOC followed by two-byte integer parameter ARG.  */
2095
2096 static void
2097 store_op1 (op, loc, arg)
2098     re_opcode_t op;
2099     unsigned char *loc;
2100     int arg;
2101 {
2102   *loc = (unsigned char) op;
2103   STORE_NUMBER (loc + 1, arg);
2104 }
2105
2106
2107 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2.  */
2108
2109 static void
2110 store_op2 (op, loc, arg1, arg2)
2111     re_opcode_t op;
2112     unsigned char *loc;
2113     int arg1, arg2;
2114 {
2115   *loc = (unsigned char) op;
2116   STORE_NUMBER (loc + 1, arg1);
2117   STORE_NUMBER (loc + 3, arg2);
2118 }
2119
2120
2121 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
2122    for OP followed by two-byte integer parameter ARG.  */
2123
2124 static void
2125 insert_op1 (op, loc, arg, end)
2126     re_opcode_t op;
2127     unsigned char *loc;
2128     int arg;
2129     unsigned char *end;
2130 {
2131   register unsigned char *pfrom = end;
2132   register unsigned char *pto = end + 3;
2133
2134   while (pfrom != loc)
2135     *--pto = *--pfrom;
2136
2137   store_op1 (op, loc, arg);
2138 }
2139
2140
2141 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2.  */
2142
2143 static void
2144 insert_op2 (op, loc, arg1, arg2, end)
2145     re_opcode_t op;
2146     unsigned char *loc;
2147     int arg1, arg2;
2148     unsigned char *end;
2149 {
2150   register unsigned char *pfrom = end;
2151   register unsigned char *pto = end + 5;
2152
2153   while (pfrom != loc)
2154     *--pto = *--pfrom;
2155
2156   store_op2 (op, loc, arg1, arg2);
2157 }
2158
2159
2160 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
2161    after an alternative or a begin-subexpression.  We assume there is at
2162    least one character before the ^.  */
2163
2164 static boolean
2165 at_begline_loc_p (pattern, p, syntax)
2166     const char *pattern, *p;
2167     reg_syntax_t syntax;
2168 {
2169   const char *prev = p - 2;
2170   boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
2171
2172   return
2173        /* After a subexpression?  */
2174        (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
2175        /* After an alternative?  */
2176     || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
2177 }
2178
2179
2180 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
2181    at least one character after the $, i.e., `P < PEND'.  */
2182
2183 static boolean
2184 at_endline_loc_p (p, pend, syntax)
2185     const char *p, *pend;
2186     int syntax;
2187 {
2188   const char *next = p;
2189   boolean next_backslash = *next == '\\';
2190   const char *next_next = p + 1 < pend ? p + 1 : NULL;
2191
2192   return
2193        /* Before a subexpression?  */
2194        (syntax & RE_NO_BK_PARENS ? *next == ')'
2195         : next_backslash && next_next && *next_next == ')')
2196        /* Before an alternative?  */
2197     || (syntax & RE_NO_BK_VBAR ? *next == '|'
2198         : next_backslash && next_next && *next_next == '|');
2199 }
2200
2201
2202 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
2203    false if it's not.  */
2204
2205 static boolean
2206 group_in_compile_stack (compile_stack, regnum)
2207     compile_stack_type compile_stack;
2208     regnum_t regnum;
2209 {
2210   int this_element;
2211
2212   for (this_element = compile_stack.avail - 1;
2213        this_element >= 0;
2214        this_element--)
2215     if (compile_stack.stack[this_element].regnum == regnum)
2216       return true;
2217
2218   return false;
2219 }
2220
2221
2222 /* Read the ending character of a range (in a bracket expression) from the
2223    uncompiled pattern *P_PTR (which ends at PEND).  We assume the
2224    starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
2225    Then we set the translation of all bits between the starting and
2226    ending characters (inclusive) in the compiled pattern B.
2227
2228    Return an error code.
2229
2230    We use these short variable names so we can use the same macros as
2231    `regex_compile' itself.  */
2232
2233 static reg_errcode_t
2234 compile_range (p_ptr, pend, translate, syntax, b)
2235     const char **p_ptr, *pend;
2236     char *translate;
2237     reg_syntax_t syntax;
2238     unsigned char *b;
2239 {
2240   unsigned this_char;
2241
2242   const char *p = *p_ptr;
2243   int range_start, range_end;
2244
2245   if (p == pend)
2246     return REG_ERANGE;
2247
2248   /* Even though the pattern is a signed `char *', we need to fetch
2249      with unsigned char *'s; if the high bit of the pattern character
2250      is set, the range endpoints will be negative if we fetch using a
2251      signed char *.
2252
2253      We also want to fetch the endpoints without translating them; the
2254      appropriate translation is done in the bit-setting loop below.  */
2255   range_start = ((unsigned char *) p)[-2];
2256   range_end   = ((unsigned char *) p)[0];
2257
2258   /* Have to increment the pointer into the pattern string, so the
2259      caller isn't still at the ending character.  */
2260   (*p_ptr)++;
2261
2262   /* If the start is after the end, the range is empty.  */
2263   if (range_start > range_end)
2264     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
2265
2266   /* Here we see why `this_char' has to be larger than an `unsigned
2267      char' -- the range is inclusive, so if `range_end' == 0xff
2268      (assuming 8-bit characters), we would otherwise go into an infinite
2269      loop, since all characters <= 0xff.  */
2270   for (this_char = range_start; this_char <= range_end; this_char++)
2271     {
2272       SET_LIST_BIT (TRANSLATE (this_char));
2273     }
2274
2275   return REG_NOERROR;
2276 }
2277 \f
2278 /* Failure stack declarations and macros; both re_compile_fastmap and
2279    re_match_2 use a failure stack.  These have to be macros because of
2280    REGEX_ALLOCATE.  */
2281
2282
2283 /* Number of failure points for which to initially allocate space
2284    when matching.  If this number is exceeded, we allocate more
2285    space, so it is not a hard limit.  */
2286 #ifndef INIT_FAILURE_ALLOC
2287 #define INIT_FAILURE_ALLOC 5
2288 #endif
2289
2290 /* Roughly the maximum number of failure points on the stack.  Would be
2291    exactly that if always used MAX_FAILURE_SPACE each time we failed.
2292    This is a variable only so users of regex can assign to it; we never
2293    change it ourselves.  */
2294 int re_max_failures = 2000;
2295
2296 typedef const unsigned char *fail_stack_elt_t;
2297
2298 typedef struct
2299 {
2300   fail_stack_elt_t *stack;
2301   unsigned size;
2302   unsigned avail;                       /* Offset of next open position.  */
2303 } fail_stack_type;
2304
2305 #define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
2306 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
2307 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
2308 #define FAIL_STACK_TOP()       (fail_stack.stack[fail_stack.avail])
2309
2310
2311 /* Initialize `fail_stack'.  Do `return -2' if the alloc fails.  */
2312
2313 #define INIT_FAIL_STACK()                                               \
2314   do {                                                                  \
2315     fail_stack.stack = (fail_stack_elt_t *)                             \
2316       REGEX_ALLOCATE (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t));  \
2317                                                                         \
2318     if (fail_stack.stack == NULL)                                       \
2319       return -2;                                                        \
2320                                                                         \
2321     fail_stack.size = INIT_FAILURE_ALLOC;                               \
2322     fail_stack.avail = 0;                                               \
2323   } while (0)
2324
2325
2326 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
2327
2328    Return 1 if succeeds, and 0 if either ran out of memory
2329    allocating space for it or it was already too large.
2330
2331    REGEX_REALLOCATE requires `destination' be declared.   */
2332
2333 #define DOUBLE_FAIL_STACK(fail_stack)                                   \
2334   ((fail_stack).size > re_max_failures * MAX_FAILURE_ITEMS              \
2335    ? 0                                                                  \
2336    : ((fail_stack).stack = (fail_stack_elt_t *)                         \
2337         REGEX_REALLOCATE ((fail_stack).stack,                           \
2338           (fail_stack).size * sizeof (fail_stack_elt_t),                \
2339           ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)),        \
2340                                                                         \
2341       (fail_stack).stack == NULL                                        \
2342       ? 0                                                               \
2343       : ((fail_stack).size <<= 1,                                       \
2344          1)))
2345
2346
2347 /* Push PATTERN_OP on FAIL_STACK.
2348
2349    Return 1 if was able to do so and 0 if ran out of memory allocating
2350    space to do so.  */
2351 #define PUSH_PATTERN_OP(pattern_op, fail_stack)                         \
2352   ((FAIL_STACK_FULL ()                                                  \
2353     && !DOUBLE_FAIL_STACK (fail_stack))                                 \
2354     ? 0                                                                 \
2355     : ((fail_stack).stack[(fail_stack).avail++] = pattern_op,           \
2356        1))
2357
2358 /* This pushes an item onto the failure stack.  Must be a four-byte
2359    value.  Assumes the variable `fail_stack'.  Probably should only
2360    be called from within `PUSH_FAILURE_POINT'.  */
2361 #define PUSH_FAILURE_ITEM(item)                                         \
2362   fail_stack.stack[fail_stack.avail++] = (fail_stack_elt_t) item
2363
2364 /* The complement operation.  Assumes `fail_stack' is nonempty.  */
2365 #define POP_FAILURE_ITEM() fail_stack.stack[--fail_stack.avail]
2366
2367 /* Used to omit pushing failure point id's when we're not debugging.  */
2368 #ifdef DEBUG
2369 #define DEBUG_PUSH PUSH_FAILURE_ITEM
2370 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_ITEM ()
2371 #else
2372 #define DEBUG_PUSH(item)
2373 #define DEBUG_POP(item_addr)
2374 #endif
2375
2376
2377 /* Push the information about the state we will need
2378    if we ever fail back to it.
2379
2380    Requires variables fail_stack, regstart, regend, reg_info, and
2381    num_regs be declared.  DOUBLE_FAIL_STACK requires `destination' be
2382    declared.
2383
2384    Does `return FAILURE_CODE' if runs out of memory.  */
2385
2386 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)   \
2387   do {                                                                  \
2388     char *destination;                                                  \
2389     /* Must be int, so when we don't save any registers, the arithmetic \
2390        of 0 + -1 isn't done as unsigned.  */                            \
2391     int this_reg;                                                       \
2392                                                                         \
2393     DEBUG_STATEMENT (failure_id++);                                     \
2394     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
2395     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
2396     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
2397     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
2398                                                                         \
2399     DEBUG_PRINT2 ("  slots needed: %d\n", NUM_FAILURE_ITEMS);           \
2400     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
2401                                                                         \
2402     /* Ensure we have enough space allocated for what we will push.  */ \
2403     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
2404       {                                                                 \
2405         if (!DOUBLE_FAIL_STACK (fail_stack))                    \
2406           return failure_code;                                          \
2407                                                                         \
2408         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
2409                        (fail_stack).size);                              \
2410         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
2411       }                                                                 \
2412                                                                         \
2413     /* Push the info, starting with the registers.  */                  \
2414     DEBUG_PRINT1 ("\n");                                                \
2415                                                                         \
2416     for (this_reg = lowest_active_reg; this_reg <= highest_active_reg;  \
2417          this_reg++)                                                    \
2418       {                                                                 \
2419         DEBUG_PRINT2 ("  Pushing reg: %d\n", this_reg);                 \
2420         DEBUG_STATEMENT (num_regs_pushed++);                            \
2421                                                                         \
2422         DEBUG_PRINT2 ("    start: 0x%x\n", regstart[this_reg]);         \
2423         PUSH_FAILURE_ITEM (regstart[this_reg]);                         \
2424                                                                         \
2425         DEBUG_PRINT2 ("    end: 0x%x\n", regend[this_reg]);             \
2426         PUSH_FAILURE_ITEM (regend[this_reg]);                           \
2427                                                                         \
2428         DEBUG_PRINT2 ("    info: 0x%x\n      ", reg_info[this_reg]);    \
2429         DEBUG_PRINT2 (" match_null=%d",                                 \
2430                       REG_MATCH_NULL_STRING_P (reg_info[this_reg]));    \
2431         DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));    \
2432         DEBUG_PRINT2 (" matched_something=%d",                          \
2433                       MATCHED_SOMETHING (reg_info[this_reg]));          \
2434         DEBUG_PRINT2 (" ever_matched=%d",                               \
2435                       EVER_MATCHED_SOMETHING (reg_info[this_reg]));     \
2436         DEBUG_PRINT1 ("\n");                                            \
2437         PUSH_FAILURE_ITEM (reg_info[this_reg].word);                    \
2438       }                                                                 \
2439                                                                         \
2440     DEBUG_PRINT2 ("  Pushing  low active reg: %d\n", lowest_active_reg);\
2441     PUSH_FAILURE_ITEM (lowest_active_reg);                              \
2442                                                                         \
2443     DEBUG_PRINT2 ("  Pushing high active reg: %d\n", highest_active_reg);\
2444     PUSH_FAILURE_ITEM (highest_active_reg);                             \
2445                                                                         \
2446     DEBUG_PRINT2 ("  Pushing pattern 0x%x: ", pattern_place);           \
2447     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
2448     PUSH_FAILURE_ITEM (pattern_place);                                  \
2449                                                                         \
2450     DEBUG_PRINT2 ("  Pushing string 0x%x: `", string_place);            \
2451     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
2452                                  size2);                                \
2453     DEBUG_PRINT1 ("'\n");                                               \
2454     PUSH_FAILURE_ITEM (string_place);                                   \
2455                                                                         \
2456     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
2457     DEBUG_PUSH (failure_id);                                            \
2458   } while (0)
2459
2460 /* This is the number of items that are pushed and popped on the stack
2461    for each register.  */
2462 #define NUM_REG_ITEMS  3
2463
2464 /* Individual items aside from the registers.  */
2465 #ifdef DEBUG
2466 #define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
2467 #else
2468 #define NUM_NONREG_ITEMS 4
2469 #endif
2470
2471 /* We push at most this many items on the stack.  */
2472 #define MAX_FAILURE_ITEMS ((num_regs - 1) * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
2473
2474 /* We actually push this many items.  */
2475 #define NUM_FAILURE_ITEMS                                               \
2476   ((highest_active_reg - lowest_active_reg + 1) * NUM_REG_ITEMS         \
2477     + NUM_NONREG_ITEMS)
2478
2479 /* How many items can still be added to the stack without overflowing it.  */
2480 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
2481
2482
2483 /* Pops what PUSH_FAIL_STACK pushes.
2484
2485    We restore into the parameters, all of which should be lvalues:
2486      STR -- the saved data position.
2487      PAT -- the saved pattern position.
2488      LOW_REG, HIGH_REG -- the highest and lowest active registers.
2489      REGSTART, REGEND -- arrays of string positions.
2490      REG_INFO -- array of information about each subexpression.
2491
2492    Also assumes the variables `fail_stack' and (if debugging), `bufp',
2493    `pend', `string1', `size1', `string2', and `size2'.  */
2494
2495 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
2496 {                                                                       \
2497   DEBUG_STATEMENT (fail_stack_elt_t failure_id;)                        \
2498   int this_reg;                                                         \
2499   const unsigned char *string_temp;                                     \
2500                                                                         \
2501   assert (!FAIL_STACK_EMPTY ());                                        \
2502                                                                         \
2503   /* Remove failure points and point to how many regs pushed.  */       \
2504   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
2505   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
2506   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
2507                                                                         \
2508   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
2509                                                                         \
2510   DEBUG_POP (&failure_id);                                              \
2511   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
2512                                                                         \
2513   /* If the saved string location is NULL, it came from an              \
2514      on_failure_keep_string_jump opcode, and we want to throw away the  \
2515      saved NULL, thus retaining our current position in the string.  */ \
2516   string_temp = POP_FAILURE_ITEM ();                                    \
2517   if (string_temp != NULL)                                              \
2518     str = (const char *) string_temp;                                   \
2519                                                                         \
2520   DEBUG_PRINT2 ("  Popping string 0x%x: `", str);                       \
2521   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
2522   DEBUG_PRINT1 ("'\n");                                                 \
2523                                                                         \
2524   pat = (unsigned char *) POP_FAILURE_ITEM ();                          \
2525   DEBUG_PRINT2 ("  Popping pattern 0x%x: ", pat);                       \
2526   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
2527                                                                         \
2528   /* Restore register info.  */                                         \
2529   high_reg = (unsigned) POP_FAILURE_ITEM ();                            \
2530   DEBUG_PRINT2 ("  Popping high active reg: %d\n", high_reg);           \
2531                                                                         \
2532   low_reg = (unsigned) POP_FAILURE_ITEM ();                             \
2533   DEBUG_PRINT2 ("  Popping  low active reg: %d\n", low_reg);            \
2534                                                                         \
2535   for (this_reg = high_reg; this_reg >= low_reg; this_reg--)            \
2536     {                                                                   \
2537       DEBUG_PRINT2 ("    Popping reg: %d\n", this_reg);                 \
2538                                                                         \
2539       reg_info[this_reg].word = POP_FAILURE_ITEM ();                    \
2540       DEBUG_PRINT2 ("      info: 0x%x\n", reg_info[this_reg]);          \
2541                                                                         \
2542       regend[this_reg] = (const char *) POP_FAILURE_ITEM ();            \
2543       DEBUG_PRINT2 ("      end: 0x%x\n", regend[this_reg]);             \
2544                                                                         \
2545       regstart[this_reg] = (const char *) POP_FAILURE_ITEM ();          \
2546       DEBUG_PRINT2 ("      start: 0x%x\n", regstart[this_reg]);         \
2547     }                                                                   \
2548                                                                         \
2549   DEBUG_STATEMENT (nfailure_points_popped++);                           \
2550 } /* POP_FAILURE_POINT */
2551 \f
2552 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
2553    BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
2554    characters can start a string that matches the pattern.  This fastmap
2555    is used by re_search to skip quickly over impossible starting points.
2556
2557    The caller must supply the address of a (1 << BYTEWIDTH)-byte data
2558    area as BUFP->fastmap.
2559
2560    We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
2561    the pattern buffer.
2562
2563    Returns 0 if we succeed, -2 if an internal error.   */
2564
2565 int
2566 re_compile_fastmap (bufp)
2567      struct re_pattern_buffer *bufp;
2568 {
2569   int j, k;
2570   fail_stack_type fail_stack;
2571 #ifndef REGEX_MALLOC
2572   char *destination;
2573 #endif
2574   /* We don't push any register information onto the failure stack.  */
2575   unsigned num_regs = 0;
2576
2577   register char *fastmap = bufp->fastmap;
2578   unsigned char *pattern = bufp->buffer;
2579   unsigned long size = bufp->used;
2580   const unsigned char *p = pattern;
2581   register unsigned char *pend = pattern + size;
2582
2583   /* Assume that each path through the pattern can be null until
2584      proven otherwise.  We set this false at the bottom of switch
2585      statement, to which we get only if a particular path doesn't
2586      match the empty string.  */
2587   boolean path_can_be_null = true;
2588
2589   /* We aren't doing a `succeed_n' to begin with.  */
2590   boolean succeed_n_p = false;
2591
2592   assert (fastmap != NULL && p != NULL);
2593
2594   INIT_FAIL_STACK ();
2595   bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.  */
2596   bufp->fastmap_accurate = 1;       /* It will be when we're done.  */
2597   bufp->can_be_null = 0;
2598
2599   while (p != pend || !FAIL_STACK_EMPTY ())
2600     {
2601       if (p == pend)
2602         {
2603           bufp->can_be_null |= path_can_be_null;
2604
2605           /* Reset for next path.  */
2606           path_can_be_null = true;
2607
2608           p = fail_stack.stack[--fail_stack.avail];
2609         }
2610
2611       /* We should never be about to go beyond the end of the pattern.  */
2612       assert (p < pend);
2613
2614 #ifdef SWITCH_ENUM_BUG
2615       switch ((int) ((re_opcode_t) *p++))
2616 #else
2617       switch ((re_opcode_t) *p++)
2618 #endif
2619         {
2620
2621         /* I guess the idea here is to simply not bother with a fastmap
2622            if a backreference is used, since it's too hard to figure out
2623            the fastmap for the corresponding group.  Setting
2624            `can_be_null' stops `re_search_2' from using the fastmap, so
2625            that is all we do.  */
2626         case duplicate:
2627           bufp->can_be_null = 1;
2628           return 0;
2629
2630
2631       /* Following are the cases which match a character.  These end
2632          with `break'.  */
2633
2634         case exactn:
2635           fastmap[p[1]] = 1;
2636           break;
2637
2638
2639         case charset:
2640           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2641             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
2642               fastmap[j] = 1;
2643           break;
2644
2645
2646         case charset_not:
2647           /* Chars beyond end of map must be allowed.  */
2648           for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
2649             fastmap[j] = 1;
2650
2651           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2652             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
2653               fastmap[j] = 1;
2654           break;
2655
2656
2657         case wordchar:
2658           for (j = 0; j < (1 << BYTEWIDTH); j++)
2659             if (SYNTAX (j) == Sword)
2660               fastmap[j] = 1;
2661           break;
2662
2663
2664         case notwordchar:
2665           for (j = 0; j < (1 << BYTEWIDTH); j++)
2666             if (SYNTAX (j) != Sword)
2667               fastmap[j] = 1;
2668           break;
2669
2670
2671         case anychar:
2672           /* `.' matches anything ...  */
2673           for (j = 0; j < (1 << BYTEWIDTH); j++)
2674             fastmap[j] = 1;
2675
2676           /* ... except perhaps newline.  */
2677           if (!(bufp->syntax & RE_DOT_NEWLINE))
2678             fastmap['\n'] = 0;
2679
2680           /* Return if we have already set `can_be_null'; if we have,
2681              then the fastmap is irrelevant.  Something's wrong here.  */
2682           else if (bufp->can_be_null)
2683             return 0;
2684
2685           /* Otherwise, have to check alternative paths.  */
2686           break;
2687
2688
2689 #ifdef emacs
2690         case syntaxspec:
2691           k = *p++;
2692           for (j = 0; j < (1 << BYTEWIDTH); j++)
2693             if (SYNTAX (j) == (enum syntaxcode) k)
2694               fastmap[j] = 1;
2695           break;
2696
2697
2698         case notsyntaxspec:
2699           k = *p++;
2700           for (j = 0; j < (1 << BYTEWIDTH); j++)
2701             if (SYNTAX (j) != (enum syntaxcode) k)
2702               fastmap[j] = 1;
2703           break;
2704
2705
2706       /* All cases after this match the empty string.  These end with
2707          `continue'.  */
2708
2709
2710         case before_dot:
2711         case at_dot:
2712         case after_dot:
2713           continue;
2714 #endif /* not emacs */
2715
2716
2717         case no_op:
2718         case begline:
2719         case endline:
2720         case begbuf:
2721         case endbuf:
2722         case wordbound:
2723         case notwordbound:
2724         case wordbeg:
2725         case wordend:
2726         case push_dummy_failure:
2727           continue;
2728
2729
2730         case jump_n:
2731         case pop_failure_jump:
2732         case maybe_pop_jump:
2733         case jump:
2734         case jump_past_alt:
2735         case dummy_failure_jump:
2736           EXTRACT_NUMBER_AND_INCR (j, p);
2737           p += j;
2738           if (j > 0)
2739             continue;
2740
2741           /* Jump backward implies we just went through the body of a
2742              loop and matched nothing.  Opcode jumped to should be
2743              `on_failure_jump' or `succeed_n'.  Just treat it like an
2744              ordinary jump.  For a * loop, it has pushed its failure
2745              point already; if so, discard that as redundant.  */
2746           if ((re_opcode_t) *p != on_failure_jump
2747               && (re_opcode_t) *p != succeed_n)
2748             continue;
2749
2750           p++;
2751           EXTRACT_NUMBER_AND_INCR (j, p);
2752           p += j;
2753
2754           /* If what's on the stack is where we are now, pop it.  */
2755           if (!FAIL_STACK_EMPTY ()
2756               && fail_stack.stack[fail_stack.avail - 1] == p)
2757             fail_stack.avail--;
2758
2759           continue;
2760
2761
2762         case on_failure_jump:
2763         case on_failure_keep_string_jump:
2764         handle_on_failure_jump:
2765           EXTRACT_NUMBER_AND_INCR (j, p);
2766
2767           /* For some patterns, e.g., `(a?)?', `p+j' here points to the
2768              end of the pattern.  We don't want to push such a point,
2769              since when we restore it above, entering the switch will
2770              increment `p' past the end of the pattern.  We don't need
2771              to push such a point since we obviously won't find any more
2772              fastmap entries beyond `pend'.  Such a pattern can match
2773              the null string, though.  */
2774           if (p + j < pend)
2775             {
2776               if (!PUSH_PATTERN_OP (p + j, fail_stack))
2777                 return -2;
2778             }
2779           else
2780             bufp->can_be_null = 1;
2781
2782           if (succeed_n_p)
2783             {
2784               EXTRACT_NUMBER_AND_INCR (k, p);   /* Skip the n.  */
2785               succeed_n_p = false;
2786             }
2787
2788           continue;
2789
2790
2791         case succeed_n:
2792           /* Get to the number of times to succeed.  */
2793           p += 2;
2794
2795           /* Increment p past the n for when k != 0.  */
2796           EXTRACT_NUMBER_AND_INCR (k, p);
2797           if (k == 0)
2798             {
2799               p -= 4;
2800               succeed_n_p = true;  /* Spaghetti code alert.  */
2801               goto handle_on_failure_jump;
2802             }
2803           continue;
2804
2805
2806         case set_number_at:
2807           p += 4;
2808           continue;
2809
2810
2811         case start_memory:
2812         case stop_memory:
2813           p += 2;
2814           continue;
2815
2816
2817         default:
2818           abort (); /* We have listed all the cases.  */
2819         } /* switch *p++ */
2820
2821       /* Getting here means we have found the possible starting
2822          characters for one path of the pattern -- and that the empty
2823          string does not match.  We need not follow this path further.
2824          Instead, look at the next alternative (remembered on the
2825          stack), or quit if no more.  The test at the top of the loop
2826          does these things.  */
2827       path_can_be_null = false;
2828       p = pend;
2829     } /* while p */
2830
2831   /* Set `can_be_null' for the last path (also the first path, if the
2832      pattern is empty).  */
2833   bufp->can_be_null |= path_can_be_null;
2834   return 0;
2835 } /* re_compile_fastmap */
2836 \f
2837 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
2838    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
2839    this memory for recording register information.  STARTS and ENDS
2840    must be allocated using the malloc library routine, and must each
2841    be at least NUM_REGS * sizeof (regoff_t) bytes long.
2842
2843    If NUM_REGS == 0, then subsequent matches should allocate their own
2844    register data.
2845
2846    Unless this function is called, the first search or match using
2847    PATTERN_BUFFER will allocate its own register data, without
2848    freeing the old data.  */
2849
2850 void
2851 re_set_registers (bufp, regs, num_regs, starts, ends)
2852     struct re_pattern_buffer *bufp;
2853     struct re_registers *regs;
2854     unsigned num_regs;
2855     regoff_t *starts, *ends;
2856 {
2857   if (num_regs)
2858     {
2859       bufp->regs_allocated = REGS_REALLOCATE;
2860       regs->num_regs = num_regs;
2861       regs->start = starts;
2862       regs->end = ends;
2863     }
2864   else
2865     {
2866       bufp->regs_allocated = REGS_UNALLOCATED;
2867       regs->num_regs = 0;
2868       regs->start = regs->end = (regoff_t) 0;
2869     }
2870 }
2871 \f
2872 /* Searching routines.  */
2873
2874 /* Like re_search_2, below, but only one string is specified, and
2875    doesn't let you say where to stop matching. */
2876
2877 int
2878 re_search (bufp, string, size, startpos, range, regs)
2879      struct re_pattern_buffer *bufp;
2880      const char *string;
2881      int size, startpos, range;
2882      struct re_registers *regs;
2883 {
2884   return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
2885                       regs, size);
2886 }
2887
2888
2889 /* Using the compiled pattern in BUFP->buffer, first tries to match the
2890    virtual concatenation of STRING1 and STRING2, starting first at index
2891    STARTPOS, then at STARTPOS + 1, and so on.
2892
2893    STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
2894
2895    RANGE is how far to scan while trying to match.  RANGE = 0 means try
2896    only at STARTPOS; in general, the last start tried is STARTPOS +
2897    RANGE.
2898
2899    In REGS, return the indices of the virtual concatenation of STRING1
2900    and STRING2 that matched the entire BUFP->buffer and its contained
2901    subexpressions.
2902
2903    Do not consider matching one past the index STOP in the virtual
2904    concatenation of STRING1 and STRING2.
2905
2906    We return either the position in the strings at which the match was
2907    found, -1 if no match, or -2 if error (such as failure
2908    stack overflow).  */
2909
2910 int
2911 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
2912      struct re_pattern_buffer *bufp;
2913      const char *string1, *string2;
2914      int size1, size2;
2915      int startpos;
2916      int range;
2917      struct re_registers *regs;
2918      int stop;
2919 {
2920   int val;
2921   register char *fastmap = bufp->fastmap;
2922   register char *translate = bufp->translate;
2923   int total_size = size1 + size2;
2924   int endpos = startpos + range;
2925
2926   /* Check for out-of-range STARTPOS.  */
2927   if (startpos < 0 || startpos > total_size)
2928     return -1;
2929
2930   /* Fix up RANGE if it might eventually take us outside
2931      the virtual concatenation of STRING1 and STRING2.  */
2932   if (endpos < -1)
2933     range = -1 - startpos;
2934   else if (endpos > total_size)
2935     range = total_size - startpos;
2936
2937   /* If the search isn't to be a backwards one, don't waste time in a
2938      search for a pattern that must be anchored.  */
2939   if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0)
2940     {
2941       if (startpos > 0)
2942         return -1;
2943       else
2944         range = 1;
2945     }
2946
2947   /* Update the fastmap now if not correct already.  */
2948   if (fastmap && !bufp->fastmap_accurate)
2949     if (re_compile_fastmap (bufp) == -2)
2950       return -2;
2951
2952   /* Loop through the string, looking for a place to start matching.  */
2953   for (;;)
2954     {
2955       /* If a fastmap is supplied, skip quickly over characters that
2956          cannot be the start of a match.  If the pattern can match the
2957          null string, however, we don't need to skip characters; we want
2958          the first null string.  */
2959       if (fastmap && startpos < total_size && !bufp->can_be_null)
2960         {
2961           if (range > 0)        /* Searching forwards.  */
2962             {
2963               register const char *d;
2964               register int lim = 0;
2965               int irange = range;
2966
2967               if (startpos < size1 && startpos + range >= size1)
2968                 lim = range - (size1 - startpos);
2969
2970               d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
2971
2972               /* Written out as an if-else to avoid testing `translate'
2973                  inside the loop.  */
2974               if (translate)
2975                 while (range > lim
2976                        && !fastmap[(unsigned char)
2977                                    translate[(unsigned char) *d++]])
2978                   range--;
2979               else
2980                 while (range > lim && !fastmap[(unsigned char) *d++])
2981                   range--;
2982
2983               startpos += irange - range;
2984             }
2985           else                          /* Searching backwards.  */
2986             {
2987               register char c = (size1 == 0 || startpos >= size1
2988                                  ? string2[startpos - size1]
2989                                  : string1[startpos]);
2990
2991               if (!fastmap[(unsigned char) TRANSLATE (c)])
2992                 goto advance;
2993             }
2994         }
2995
2996       /* If can't match the null string, and that's all we have left, fail.  */
2997       if (range >= 0 && startpos == total_size && fastmap
2998           && !bufp->can_be_null)
2999         return -1;
3000
3001       val = re_match_2 (bufp, string1, size1, string2, size2,
3002                         startpos, regs, stop);
3003       if (val >= 0)
3004         return startpos;
3005
3006       if (val == -2)
3007         return -2;
3008
3009     advance:
3010       if (!range)
3011         break;
3012       else if (range > 0)
3013         {
3014           range--;
3015           startpos++;
3016         }
3017       else
3018         {
3019           range++;
3020           startpos--;
3021         }
3022     }
3023   return -1;
3024 } /* re_search_2 */
3025 \f
3026 /* Declarations and macros for re_match_2.  */
3027
3028 static int bcmp_translate ();
3029 static boolean alt_match_null_string_p (),
3030                common_op_match_null_string_p (),
3031                group_match_null_string_p ();
3032
3033 /* Structure for per-register (a.k.a. per-group) information.
3034    This must not be longer than one word, because we push this value
3035    onto the failure stack.  Other register information, such as the
3036    starting and ending positions (which are addresses), and the list of
3037    inner groups (which is a bits list) are maintained in separate
3038    variables.
3039
3040    We are making a (strictly speaking) nonportable assumption here: that
3041    the compiler will pack our bit fields into something that fits into
3042    the type of `word', i.e., is something that fits into one item on the
3043    failure stack.  */
3044 typedef union
3045 {
3046   fail_stack_elt_t word;
3047   struct
3048   {
3049       /* This field is one if this group can match the empty string,
3050          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
3051 #define MATCH_NULL_UNSET_VALUE 3
3052     unsigned match_null_string_p : 2;
3053     unsigned is_active : 1;
3054     unsigned matched_something : 1;
3055     unsigned ever_matched_something : 1;
3056   } bits;
3057 } register_info_type;
3058
3059 #define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
3060 #define IS_ACTIVE(R)  ((R).bits.is_active)
3061 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
3062 #define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
3063
3064
3065 /* Call this when have matched a real character; it sets `matched' flags
3066    for the subexpressions which we are currently inside.  Also records
3067    that those subexprs have matched.  */
3068 #define SET_REGS_MATCHED()                                              \
3069   do                                                                    \
3070     {                                                                   \
3071       unsigned r;                                                       \
3072       for (r = lowest_active_reg; r <= highest_active_reg; r++)         \
3073         {                                                               \
3074           MATCHED_SOMETHING (reg_info[r])                               \
3075             = EVER_MATCHED_SOMETHING (reg_info[r])                      \
3076             = 1;                                                        \
3077         }                                                               \
3078     }                                                                   \
3079   while (0)
3080
3081
3082 /* This converts PTR, a pointer into one of the search strings `string1'
3083    and `string2' into an offset from the beginning of that string.  */
3084 #define POINTER_TO_OFFSET(ptr)                                          \
3085   (FIRST_STRING_P (ptr) ? (ptr) - string1 : (ptr) - string2 + size1)
3086
3087 /* Registers are set to a sentinel when they haven't yet matched.  */
3088 #define REG_UNSET_VALUE ((char *) -1)
3089 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
3090
3091
3092 /* Macros for dealing with the split strings in re_match_2.  */
3093
3094 #define MATCHING_IN_FIRST_STRING  (dend == end_match_1)
3095
3096 /* Call before fetching a character with *d.  This switches over to
3097    string2 if necessary.  */
3098 #define PREFETCH()                                                      \
3099   while (d == dend)                                                     \
3100     {                                                                   \
3101       /* End of string2 => fail.  */                                    \
3102       if (dend == end_match_2)                                          \
3103         goto fail;                                                      \
3104       /* End of string1 => advance to string2.  */                      \
3105       d = string2;                                                      \
3106       dend = end_match_2;                                               \
3107     }
3108
3109
3110 /* Test if at very beginning or at very end of the virtual concatenation
3111    of `string1' and `string2'.  If only one string, it's `string2'.  */
3112 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
3113 #define AT_STRINGS_END(d) ((d) == end2)
3114
3115
3116 /* Test if D points to a character which is word-constituent.  We have
3117    two special cases to check for: if past the end of string1, look at
3118    the first character in string2; and if before the beginning of
3119    string2, look at the last character in string1.  */
3120 #define WORDCHAR_P(d)                                                   \
3121   (SYNTAX ((d) == end1 ? *string2                                       \
3122            : (d) == string2 - 1 ? *(end1 - 1) : *(d))                   \
3123    == Sword)
3124
3125 /* Test if the character before D and the one at D differ with respect
3126    to being word-constituent.  */
3127 #define AT_WORD_BOUNDARY(d)                                             \
3128   (AT_STRINGS_BEG (d) || AT_STRINGS_END (d)                             \
3129    || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
3130
3131
3132 /* Free everything we malloc.  */
3133 #ifdef REGEX_MALLOC
3134 #define FREE_VAR(var) if (var) free (var); var = NULL
3135 #define FREE_VARIABLES()                                                \
3136   do {                                                                  \
3137     FREE_VAR (fail_stack.stack);                                        \
3138     FREE_VAR (regstart);                                                \
3139     FREE_VAR (regend);                                                  \
3140     FREE_VAR (old_regstart);                                            \
3141     FREE_VAR (old_regend);                                              \
3142     FREE_VAR (best_regstart);                                           \
3143     FREE_VAR (best_regend);                                             \
3144     FREE_VAR (reg_info);                                                \
3145     FREE_VAR (reg_dummy);                                               \
3146     FREE_VAR (reg_info_dummy);                                          \
3147   } while (0)
3148 #else /* not REGEX_MALLOC */
3149 /* Some MIPS systems (at least) want this to free alloca'd storage.  */
3150 #define FREE_VARIABLES() alloca (0)
3151 #endif /* not REGEX_MALLOC */
3152
3153
3154 /* These values must meet several constraints.  They must not be valid
3155    register values; since we have a limit of 255 registers (because
3156    we use only one byte in the pattern for the register number), we can
3157    use numbers larger than 255.  They must differ by 1, because of
3158    NUM_FAILURE_ITEMS above.  And the value for the lowest register must
3159    be larger than the value for the highest register, so we do not try
3160    to actually save any registers when none are active.  */
3161 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
3162 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
3163 \f
3164 /* Matching routines.  */
3165
3166 #ifndef emacs   /* Emacs never uses this.  */
3167 /* re_match is like re_match_2 except it takes only a single string.  */
3168
3169 int
3170 re_match (bufp, string, size, pos, regs)
3171      struct re_pattern_buffer *bufp;
3172      const char *string;
3173      int size, pos;
3174      struct re_registers *regs;
3175  {
3176   return re_match_2 (bufp, NULL, 0, string, size, pos, regs, size);
3177 }
3178 #endif /* not emacs */
3179
3180
3181 /* re_match_2 matches the compiled pattern in BUFP against the
3182    the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
3183    and SIZE2, respectively).  We start matching at POS, and stop
3184    matching at STOP.
3185
3186    If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
3187    store offsets for the substring each group matched in REGS.  See the
3188    documentation for exactly how many groups we fill.
3189
3190    We return -1 if no match, -2 if an internal error (such as the
3191    failure stack overflowing).  Otherwise, we return the length of the
3192    matched substring.  */
3193
3194 int
3195 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
3196      struct re_pattern_buffer *bufp;
3197      const char *string1, *string2;
3198      int size1, size2;
3199      int pos;
3200      struct re_registers *regs;
3201      int stop;
3202 {
3203   /* General temporaries.  */
3204   int mcnt;
3205   unsigned char *p1;
3206
3207   /* Just past the end of the corresponding string.  */
3208   const char *end1, *end2;
3209
3210   /* Pointers into string1 and string2, just past the last characters in
3211      each to consider matching.  */
3212   const char *end_match_1, *end_match_2;
3213
3214   /* Where we are in the data, and the end of the current string.  */
3215   const char *d, *dend;
3216
3217   /* Where we are in the pattern, and the end of the pattern.  */
3218   unsigned char *p = bufp->buffer;
3219   register unsigned char *pend = p + bufp->used;
3220
3221   /* We use this to map every character in the string.  */
3222   char *translate = bufp->translate;
3223
3224   /* Failure point stack.  Each place that can handle a failure further
3225      down the line pushes a failure point on this stack.  It consists of
3226      restart, regend, and reg_info for all registers corresponding to
3227      the subexpressions we're currently inside, plus the number of such
3228      registers, and, finally, two char *'s.  The first char * is where
3229      to resume scanning the pattern; the second one is where to resume
3230      scanning the strings.  If the latter is zero, the failure point is
3231      a ``dummy''; if a failure happens and the failure point is a dummy,
3232      it gets discarded and the next next one is tried.  */
3233   fail_stack_type fail_stack;
3234 #ifdef DEBUG
3235   static unsigned failure_id = 0;
3236   unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
3237 #endif
3238
3239   /* We fill all the registers internally, independent of what we
3240      return, for use in backreferences.  The number here includes
3241      an element for register zero.  */
3242   unsigned num_regs = bufp->re_nsub + 1;
3243
3244   /* The currently active registers.  */
3245   unsigned lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3246   unsigned highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3247
3248   /* Information on the contents of registers. These are pointers into
3249      the input strings; they record just what was matched (on this
3250      attempt) by a subexpression part of the pattern, that is, the
3251      regnum-th regstart pointer points to where in the pattern we began
3252      matching and the regnum-th regend points to right after where we
3253      stopped matching the regnum-th subexpression.  (The zeroth register
3254      keeps track of what the whole pattern matches.)  */
3255   const char **regstart, **regend;
3256
3257   /* If a group that's operated upon by a repetition operator fails to
3258      match anything, then the register for its start will need to be
3259      restored because it will have been set to wherever in the string we
3260      are when we last see its open-group operator.  Similarly for a
3261      register's end.  */
3262   const char **old_regstart, **old_regend;
3263
3264   /* The is_active field of reg_info helps us keep track of which (possibly
3265      nested) subexpressions we are currently in. The matched_something
3266      field of reg_info[reg_num] helps us tell whether or not we have
3267      matched any of the pattern so far this time through the reg_num-th
3268      subexpression.  These two fields get reset each time through any
3269      loop their register is in.  */
3270   register_info_type *reg_info;
3271
3272   /* The following record the register info as found in the above
3273      variables when we find a match better than any we've seen before.
3274      This happens as we backtrack through the failure points, which in
3275      turn happens only if we have not yet matched the entire string. */
3276   unsigned best_regs_set = false;
3277   const char **best_regstart, **best_regend;
3278
3279   /* Logically, this is `best_regend[0]'.  But we don't want to have to
3280      allocate space for that if we're not allocating space for anything
3281      else (see below).  Also, we never need info about register 0 for
3282      any of the other register vectors, and it seems rather a kludge to
3283      treat `best_regend' differently than the rest.  So we keep track of
3284      the end of the best match so far in a separate variable.  We
3285      initialize this to NULL so that when we backtrack the first time
3286      and need to test it, it's not garbage.  */
3287   const char *match_end = NULL;
3288
3289   /* Used when we pop values we don't care about.  */
3290   const char **reg_dummy;
3291   register_info_type *reg_info_dummy;
3292
3293 #ifdef DEBUG
3294   /* Counts the total number of registers pushed.  */
3295   unsigned num_regs_pushed = 0;
3296 #endif
3297
3298   DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
3299
3300   INIT_FAIL_STACK ();
3301
3302   /* Do not bother to initialize all the register variables if there are
3303      no groups in the pattern, as it takes a fair amount of time.  If
3304      there are groups, we include space for register 0 (the whole
3305      pattern), even though we never use it, since it simplifies the
3306      array indexing.  We should fix this.  */
3307   if (bufp->re_nsub)
3308     {
3309       regstart = REGEX_TALLOC (num_regs, const char *);
3310       regend = REGEX_TALLOC (num_regs, const char *);
3311       old_regstart = REGEX_TALLOC (num_regs, const char *);
3312       old_regend = REGEX_TALLOC (num_regs, const char *);
3313       best_regstart = REGEX_TALLOC (num_regs, const char *);
3314       best_regend = REGEX_TALLOC (num_regs, const char *);
3315       reg_info = REGEX_TALLOC (num_regs, register_info_type);
3316       reg_dummy = REGEX_TALLOC (num_regs, const char *);
3317       reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type);
3318
3319       if (!(regstart && regend && old_regstart && old_regend && reg_info
3320             && best_regstart && best_regend && reg_dummy && reg_info_dummy))
3321         {
3322           FREE_VARIABLES ();
3323           return -2;
3324         }
3325     }
3326 #ifdef REGEX_MALLOC
3327   else
3328     {
3329       /* We must initialize all our variables to NULL, so that
3330          `FREE_VARIABLES' doesn't try to free them.  */
3331       regstart = regend = old_regstart = old_regend = best_regstart
3332         = best_regend = reg_dummy = NULL;
3333       reg_info = reg_info_dummy = (register_info_type *) NULL;
3334     }
3335 #endif /* REGEX_MALLOC */
3336
3337   /* The starting position is bogus.  */
3338   if (pos < 0 || pos > size1 + size2)
3339     {
3340       FREE_VARIABLES ();
3341       return -1;
3342     }
3343
3344   /* Initialize subexpression text positions to -1 to mark ones that no
3345      start_memory/stop_memory has been seen for. Also initialize the
3346      register information struct.  */
3347   for (mcnt = 1; mcnt < num_regs; mcnt++)
3348     {
3349       regstart[mcnt] = regend[mcnt]
3350         = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
3351
3352       REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
3353       IS_ACTIVE (reg_info[mcnt]) = 0;
3354       MATCHED_SOMETHING (reg_info[mcnt]) = 0;
3355       EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
3356     }
3357
3358   /* We move `string1' into `string2' if the latter's empty -- but not if
3359      `string1' is null.  */
3360   if (size2 == 0 && string1 != NULL)
3361     {
3362       string2 = string1;
3363       size2 = size1;
3364       string1 = 0;
3365       size1 = 0;
3366     }
3367   end1 = string1 + size1;
3368   end2 = string2 + size2;
3369
3370   /* Compute where to stop matching, within the two strings.  */
3371   if (stop <= size1)
3372     {
3373       end_match_1 = string1 + stop;
3374       end_match_2 = string2;
3375     }
3376   else
3377     {
3378       end_match_1 = end1;
3379       end_match_2 = string2 + stop - size1;
3380     }
3381
3382   /* `p' scans through the pattern as `d' scans through the data.
3383      `dend' is the end of the input string that `d' points within.  `d'
3384      is advanced into the following input string whenever necessary, but
3385      this happens before fetching; therefore, at the beginning of the
3386      loop, `d' can be pointing at the end of a string, but it cannot
3387      equal `string2'.  */
3388   if (size1 > 0 && pos <= size1)
3389     {
3390       d = string1 + pos;
3391       dend = end_match_1;
3392     }
3393   else
3394     {
3395       d = string2 + pos - size1;
3396       dend = end_match_2;
3397     }
3398
3399   DEBUG_PRINT1 ("The compiled pattern is: ");
3400   DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
3401   DEBUG_PRINT1 ("The string to match is: `");
3402   DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
3403   DEBUG_PRINT1 ("'\n");
3404
3405   /* This loops over pattern commands.  It exits by returning from the
3406      function if the match is complete, or it drops through if the match
3407      fails at this starting point in the input data.  */
3408   for (;;)
3409     {
3410       DEBUG_PRINT2 ("\n0x%x: ", p);
3411
3412       if (p == pend)
3413         { /* End of pattern means we might have succeeded.  */
3414           DEBUG_PRINT1 ("end of pattern ... ");
3415
3416           /* If we haven't matched the entire string, and we want the
3417              longest match, try backtracking.  */
3418           if (d != end_match_2)
3419             {
3420               DEBUG_PRINT1 ("backtracking.\n");
3421
3422               if (!FAIL_STACK_EMPTY ())
3423                 { /* More failure points to try.  */
3424                   boolean same_str_p = (FIRST_STRING_P (match_end)
3425                                         == MATCHING_IN_FIRST_STRING);
3426
3427                   /* If exceeds best match so far, save it.  */
3428                   if (!best_regs_set
3429                       || (same_str_p && d > match_end)
3430                       || (!same_str_p && !MATCHING_IN_FIRST_STRING))
3431                     {
3432                       best_regs_set = true;
3433                       match_end = d;
3434
3435                       DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
3436
3437                       for (mcnt = 1; mcnt < num_regs; mcnt++)
3438                         {
3439                           best_regstart[mcnt] = regstart[mcnt];
3440                           best_regend[mcnt] = regend[mcnt];
3441                         }
3442                     }
3443                   goto fail;
3444                 }
3445
3446               /* If no failure points, don't restore garbage.  */
3447               else if (best_regs_set)
3448                 {
3449                 restore_best_regs:
3450                   /* Restore best match.  It may happen that `dend ==
3451                      end_match_1' while the restored d is in string2.
3452                      For example, the pattern `x.*y.*z' against the
3453                      strings `x-' and `y-z-', if the two strings are
3454                      not consecutive in memory.  */
3455                   DEBUG_PRINT1 ("Restoring best registers.\n");
3456
3457                   d = match_end;
3458                   dend = ((d >= string1 && d <= end1)
3459                            ? end_match_1 : end_match_2);
3460
3461                   for (mcnt = 1; mcnt < num_regs; mcnt++)
3462                     {
3463                       regstart[mcnt] = best_regstart[mcnt];
3464                       regend[mcnt] = best_regend[mcnt];
3465                     }
3466                 }
3467             } /* d != end_match_2 */
3468
3469           DEBUG_PRINT1 ("Accepting match.\n");
3470
3471           /* If caller wants register contents data back, do it.  */
3472           if (regs && !bufp->no_sub)
3473             {
3474               /* Have the register data arrays been allocated?  */
3475               if (bufp->regs_allocated == REGS_UNALLOCATED)
3476                 { /* No.  So allocate them with malloc.  We need one
3477                      extra element beyond `num_regs' for the `-1' marker
3478                      GNU code uses.  */
3479                   regs->num_regs = MAX (RE_NREGS, num_regs + 1);
3480                   regs->start = TALLOC (regs->num_regs, regoff_t);
3481                   regs->end = TALLOC (regs->num_regs, regoff_t);
3482                   if (regs->start == NULL || regs->end == NULL)
3483                     return -2;
3484                   bufp->regs_allocated = REGS_REALLOCATE;
3485                 }
3486               else if (bufp->regs_allocated == REGS_REALLOCATE)
3487                 { /* Yes.  If we need more elements than were already
3488                      allocated, reallocate them.  If we need fewer, just
3489                      leave it alone.  */
3490                   if (regs->num_regs < num_regs + 1)
3491                     {
3492                       regs->num_regs = num_regs + 1;
3493                       RETALLOC (regs->start, regs->num_regs, regoff_t);
3494                       RETALLOC (regs->end, regs->num_regs, regoff_t);
3495                       if (regs->start == NULL || regs->end == NULL)
3496                         return -2;
3497                     }
3498                 }
3499               else
3500                 {
3501                   /* These braces fend off a "empty body in an else-statement"
3502                      warning under GCC when assert expands to nothing.  */
3503                   assert (bufp->regs_allocated == REGS_FIXED);
3504                 }
3505
3506               /* Convert the pointer data in `regstart' and `regend' to
3507                  indices.  Register zero has to be set differently,
3508                  since we haven't kept track of any info for it.  */
3509               if (regs->num_regs > 0)
3510                 {
3511                   regs->start[0] = pos;
3512                   regs->end[0] = (MATCHING_IN_FIRST_STRING ? d - string1
3513                                   : d - string2 + size1);
3514                 }
3515
3516               /* Go through the first `min (num_regs, regs->num_regs)'
3517                  registers, since that is all we initialized.  */
3518               for (mcnt = 1; mcnt < MIN (num_regs, regs->num_regs); mcnt++)
3519                 {
3520                   if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
3521                     regs->start[mcnt] = regs->end[mcnt] = -1;
3522                   else
3523                     {
3524                       regs->start[mcnt] = POINTER_TO_OFFSET (regstart[mcnt]);
3525                       regs->end[mcnt] = POINTER_TO_OFFSET (regend[mcnt]);
3526                     }
3527                 }
3528
3529               /* If the regs structure we return has more elements than
3530                  were in the pattern, set the extra elements to -1.  If
3531                  we (re)allocated the registers, this is the case,
3532                  because we always allocate enough to have at least one
3533                  -1 at the end.  */
3534               for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++)
3535                 regs->start[mcnt] = regs->end[mcnt] = -1;
3536             } /* regs && !bufp->no_sub */
3537
3538           FREE_VARIABLES ();
3539           DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
3540                         nfailure_points_pushed, nfailure_points_popped,
3541                         nfailure_points_pushed - nfailure_points_popped);
3542           DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
3543
3544           mcnt = d - pos - (MATCHING_IN_FIRST_STRING
3545                             ? string1
3546                             : string2 - size1);
3547
3548           DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
3549
3550           return mcnt;
3551         }
3552
3553       /* Otherwise match next pattern command.  */
3554 #ifdef SWITCH_ENUM_BUG
3555       switch ((int) ((re_opcode_t) *p++))
3556 #else
3557       switch ((re_opcode_t) *p++)
3558 #endif
3559         {
3560         /* Ignore these.  Used to ignore the n of succeed_n's which
3561            currently have n == 0.  */
3562         case no_op:
3563           DEBUG_PRINT1 ("EXECUTING no_op.\n");
3564           break;
3565
3566
3567         /* Match the next n pattern characters exactly.  The following
3568            byte in the pattern defines n, and the n bytes after that
3569            are the characters to match.  */
3570         case exactn:
3571           mcnt = *p++;
3572           DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
3573
3574           /* This is written out as an if-else so we don't waste time
3575              testing `translate' inside the loop.  */
3576           if (translate)
3577             {
3578               do
3579                 {
3580                   PREFETCH ();
3581                   if (translate[(unsigned char) *d++] != (char) *p++)
3582                     goto fail;
3583                 }
3584               while (--mcnt);
3585             }
3586           else
3587             {
3588               do
3589                 {
3590                   PREFETCH ();
3591                   if (*d++ != (char) *p++) goto fail;
3592                 }
3593               while (--mcnt);
3594             }
3595           SET_REGS_MATCHED ();
3596           break;
3597
3598
3599         /* Match any character except possibly a newline or a null.  */
3600         case anychar:
3601           DEBUG_PRINT1 ("EXECUTING anychar.\n");
3602
3603           PREFETCH ();
3604
3605           if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
3606               || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
3607             goto fail;
3608
3609           SET_REGS_MATCHED ();
3610           DEBUG_PRINT2 ("  Matched `%d'.\n", *d);
3611           d++;
3612           break;
3613
3614
3615         case charset:
3616         case charset_not:
3617           {
3618             register unsigned char c;
3619             boolean not = (re_opcode_t) *(p - 1) == charset_not;
3620
3621             DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
3622
3623             PREFETCH ();
3624             c = TRANSLATE (*d); /* The character to match.  */
3625
3626             /* Cast to `unsigned' instead of `unsigned char' in case the
3627                bit list is a full 32 bytes long.  */
3628             if (c < (unsigned) (*p * BYTEWIDTH)
3629                 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
3630               not = !not;
3631
3632             p += 1 + *p;
3633
3634             if (!not) goto fail;
3635
3636             SET_REGS_MATCHED ();
3637             d++;
3638             break;
3639           }
3640
3641
3642         /* The beginning of a group is represented by start_memory.
3643            The arguments are the register number in the next byte, and the
3644            number of groups inner to this one in the next.  The text
3645            matched within the group is recorded (in the internal
3646            registers data structure) under the register number.  */
3647         case start_memory:
3648           DEBUG_PRINT3 ("EXECUTING start_memory %d (%d):\n", *p, p[1]);
3649
3650           /* Find out if this group can match the empty string.  */
3651           p1 = p;               /* To send to group_match_null_string_p.  */
3652
3653           if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
3654             REG_MATCH_NULL_STRING_P (reg_info[*p])
3655               = group_match_null_string_p (&p1, pend, reg_info);
3656
3657           /* Save the position in the string where we were the last time
3658              we were at this open-group operator in case the group is
3659              operated upon by a repetition operator, e.g., with `(a*)*b'
3660              against `ab'; then we want to ignore where we are now in
3661              the string in case this attempt to match fails.  */
3662           old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
3663                              ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
3664                              : regstart[*p];
3665           DEBUG_PRINT2 ("  old_regstart: %d\n",
3666                          POINTER_TO_OFFSET (old_regstart[*p]));
3667
3668           regstart[*p] = d;
3669           DEBUG_PRINT2 ("  regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
3670
3671           IS_ACTIVE (reg_info[*p]) = 1;
3672           MATCHED_SOMETHING (reg_info[*p]) = 0;
3673
3674           /* This is the new highest active register.  */
3675           highest_active_reg = *p;
3676
3677           /* If nothing was active before, this is the new lowest active
3678              register.  */
3679           if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
3680             lowest_active_reg = *p;
3681
3682           /* Move past the register number and inner group count.  */
3683           p += 2;
3684           break;
3685
3686
3687         /* The stop_memory opcode represents the end of a group.  Its
3688            arguments are the same as start_memory's: the register
3689            number, and the number of inner groups.  */
3690         case stop_memory:
3691           DEBUG_PRINT3 ("EXECUTING stop_memory %d (%d):\n", *p, p[1]);
3692
3693           /* We need to save the string position the last time we were at
3694              this close-group operator in case the group is operated
3695              upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
3696              against `aba'; then we want to ignore where we are now in
3697              the string in case this attempt to match fails.  */
3698           old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
3699                            ? REG_UNSET (regend[*p]) ? d : regend[*p]
3700                            : regend[*p];
3701           DEBUG_PRINT2 ("      old_regend: %d\n",
3702                          POINTER_TO_OFFSET (old_regend[*p]));
3703
3704           regend[*p] = d;
3705           DEBUG_PRINT2 ("      regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
3706
3707           /* This register isn't active anymore.  */
3708           IS_ACTIVE (reg_info[*p]) = 0;
3709
3710           /* If this was the only register active, nothing is active
3711              anymore.  */
3712           if (lowest_active_reg == highest_active_reg)
3713             {
3714               lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3715               highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3716             }
3717           else
3718             { /* We must scan for the new highest active register, since
3719                  it isn't necessarily one less than now: consider
3720                  (a(b)c(d(e)f)g).  When group 3 ends, after the f), the
3721                  new highest active register is 1.  */
3722               unsigned char r = *p - 1;
3723               while (r > 0 && !IS_ACTIVE (reg_info[r]))
3724                 r--;
3725
3726               /* If we end up at register zero, that means that we saved
3727                  the registers as the result of an `on_failure_jump', not
3728                  a `start_memory', and we jumped to past the innermost
3729                  `stop_memory'.  For example, in ((.)*) we save
3730                  registers 1 and 2 as a result of the *, but when we pop
3731                  back to the second ), we are at the stop_memory 1.
3732                  Thus, nothing is active.  */
3733               if (r == 0)
3734                 {
3735                   lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3736                   highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3737                 }
3738               else
3739                 highest_active_reg = r;
3740             }
3741
3742           /* If just failed to match something this time around with a
3743              group that's operated on by a repetition operator, try to
3744              force exit from the ``loop'', and restore the register
3745              information for this group that we had before trying this
3746              last match.  */
3747           if ((!MATCHED_SOMETHING (reg_info[*p])
3748                || (re_opcode_t) p[-3] == start_memory)
3749               && (p + 2) < pend)
3750             {
3751               boolean is_a_jump_n = false;
3752
3753               p1 = p + 2;
3754               mcnt = 0;
3755               switch ((re_opcode_t) *p1++)
3756                 {
3757                   case jump_n:
3758                     is_a_jump_n = true;
3759                   case pop_failure_jump:
3760                   case maybe_pop_jump:
3761                   case jump:
3762                   case dummy_failure_jump:
3763                     EXTRACT_NUMBER_AND_INCR (mcnt, p1);
3764                     if (is_a_jump_n)
3765                       p1 += 2;
3766                     break;
3767
3768                   default:
3769                     /* do nothing */ ;
3770                 }
3771               p1 += mcnt;
3772
3773               /* If the next operation is a jump backwards in the pattern
3774                  to an on_failure_jump right before the start_memory
3775                  corresponding to this stop_memory, exit from the loop
3776                  by forcing a failure after pushing on the stack the
3777                  on_failure_jump's jump in the pattern, and d.  */
3778               if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
3779                   && (re_opcode_t) p1[3] == start_memory && p1[4] == *p)
3780                 {
3781                   /* If this group ever matched anything, then restore
3782                      what its registers were before trying this last
3783                      failed match, e.g., with `(a*)*b' against `ab' for
3784                      regstart[1], and, e.g., with `((a*)*(b*)*)*'
3785                      against `aba' for regend[3].
3786
3787                      Also restore the registers for inner groups for,
3788                      e.g., `((a*)(b*))*' against `aba' (register 3 would
3789                      otherwise get trashed).  */
3790
3791                   if (EVER_MATCHED_SOMETHING (reg_info[*p]))
3792                     {
3793                       unsigned r;
3794
3795                       EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
3796
3797                       /* Restore this and inner groups' (if any) registers.  */
3798                       for (r = *p; r < *p + *(p + 1); r++)
3799                         {
3800                           regstart[r] = old_regstart[r];
3801
3802                           /* xx why this test?  */
3803                           if ((int) old_regend[r] >= (int) regstart[r])
3804                             regend[r] = old_regend[r];
3805                         }
3806                     }
3807                   p1++;
3808                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
3809                   PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
3810
3811                   goto fail;
3812                 }
3813             }
3814
3815           /* Move past the register number and the inner group count.  */
3816           p += 2;
3817           break;
3818
3819
3820         /* \<digit> has been turned into a `duplicate' command which is
3821            followed by the numeric value of <digit> as the register number.  */
3822         case duplicate:
3823           {
3824             register const char *d2, *dend2;
3825             int regno = *p++;   /* Get which register to match against.  */
3826             DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
3827
3828             /* Can't back reference a group which we've never matched.  */
3829             if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
3830               goto fail;
3831
3832             /* Where in input to try to start matching.  */
3833             d2 = regstart[regno];
3834
3835             /* Where to stop matching; if both the place to start and
3836                the place to stop matching are in the same string, then
3837                set to the place to stop, otherwise, for now have to use
3838                the end of the first string.  */
3839
3840             dend2 = ((FIRST_STRING_P (regstart[regno])
3841                       == FIRST_STRING_P (regend[regno]))
3842                      ? regend[regno] : end_match_1);
3843             for (;;)
3844               {
3845                 /* If necessary, advance to next segment in register
3846                    contents.  */
3847                 while (d2 == dend2)
3848                   {
3849                     if (dend2 == end_match_2) break;
3850                     if (dend2 == regend[regno]) break;
3851
3852                     /* End of string1 => advance to string2. */
3853                     d2 = string2;
3854                     dend2 = regend[regno];
3855                   }
3856                 /* At end of register contents => success */
3857                 if (d2 == dend2) break;
3858
3859                 /* If necessary, advance to next segment in data.  */
3860                 PREFETCH ();
3861
3862                 /* How many characters left in this segment to match.  */
3863                 mcnt = dend - d;
3864
3865                 /* Want how many consecutive characters we can match in
3866                    one shot, so, if necessary, adjust the count.  */
3867                 if (mcnt > dend2 - d2)
3868                   mcnt = dend2 - d2;
3869
3870                 /* Compare that many; failure if mismatch, else move
3871                    past them.  */
3872                 if (translate
3873                     ? bcmp_translate (d, d2, mcnt, translate)
3874                     : bcmp (d, d2, mcnt))
3875                   goto fail;
3876                 d += mcnt, d2 += mcnt;
3877               }
3878           }
3879           break;
3880
3881
3882         /* begline matches the empty string at the beginning of the string
3883            (unless `not_bol' is set in `bufp'), and, if
3884            `newline_anchor' is set, after newlines.  */
3885         case begline:
3886           DEBUG_PRINT1 ("EXECUTING begline.\n");
3887
3888           if (AT_STRINGS_BEG (d))
3889             {
3890               if (!bufp->not_bol) break;
3891             }
3892           else if (d[-1] == '\n' && bufp->newline_anchor)
3893             {
3894               break;
3895             }
3896           /* In all other cases, we fail.  */
3897           goto fail;
3898
3899
3900         /* endline is the dual of begline.  */
3901         case endline:
3902           DEBUG_PRINT1 ("EXECUTING endline.\n");
3903
3904           if (AT_STRINGS_END (d))
3905             {
3906               if (!bufp->not_eol) break;
3907             }
3908
3909           /* We have to ``prefetch'' the next character.  */
3910           else if ((d == end1 ? *string2 : *d) == '\n'
3911                    && bufp->newline_anchor)
3912             {
3913               break;
3914             }
3915           goto fail;
3916
3917
3918         /* Match at the very beginning of the data.  */
3919         case begbuf:
3920           DEBUG_PRINT1 ("EXECUTING begbuf.\n");
3921           if (AT_STRINGS_BEG (d))
3922             break;
3923           goto fail;
3924
3925
3926         /* Match at the very end of the data.  */
3927         case endbuf:
3928           DEBUG_PRINT1 ("EXECUTING endbuf.\n");
3929           if (AT_STRINGS_END (d))
3930             break;
3931           goto fail;
3932
3933
3934         /* on_failure_keep_string_jump is used to optimize `.*\n'.  It
3935            pushes NULL as the value for the string on the stack.  Then
3936            `pop_failure_point' will keep the current value for the
3937            string, instead of restoring it.  To see why, consider
3938            matching `foo\nbar' against `.*\n'.  The .* matches the foo;
3939            then the . fails against the \n.  But the next thing we want
3940            to do is match the \n against the \n; if we restored the
3941            string value, we would be back at the foo.
3942
3943            Because this is used only in specific cases, we don't need to
3944            check all the things that `on_failure_jump' does, to make
3945            sure the right things get saved on the stack.  Hence we don't
3946            share its code.  The only reason to push anything on the
3947            stack at all is that otherwise we would have to change
3948            `anychar's code to do something besides goto fail in this
3949            case; that seems worse than this.  */
3950         case on_failure_keep_string_jump:
3951           DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
3952
3953           EXTRACT_NUMBER_AND_INCR (mcnt, p);
3954           DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
3955
3956           PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
3957           break;
3958
3959
3960         /* Uses of on_failure_jump:
3961
3962            Each alternative starts with an on_failure_jump that points
3963            to the beginning of the next alternative.  Each alternative
3964            except the last ends with a jump that in effect jumps past
3965            the rest of the alternatives.  (They really jump to the
3966            ending jump of the following alternative, because tensioning
3967            these jumps is a hassle.)
3968
3969            Repeats start with an on_failure_jump that points past both
3970            the repetition text and either the following jump or
3971            pop_failure_jump back to this on_failure_jump.  */
3972         case on_failure_jump:
3973         on_failure:
3974           DEBUG_PRINT1 ("EXECUTING on_failure_jump");
3975
3976           EXTRACT_NUMBER_AND_INCR (mcnt, p);
3977           DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
3978
3979           /* If this on_failure_jump comes right before a group (i.e.,
3980              the original * applied to a group), save the information
3981              for that group and all inner ones, so that if we fail back
3982              to this point, the group's information will be correct.
3983              For example, in \(a*\)*\1, we need the preceding group,
3984              and in \(\(a*\)b*\)\2, we need the inner group.  */
3985
3986           /* We can't use `p' to check ahead because we push
3987              a failure point to `p + mcnt' after we do this.  */
3988           p1 = p;
3989
3990           /* We need to skip no_op's before we look for the
3991              start_memory in case this on_failure_jump is happening as
3992              the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
3993              against aba.  */
3994           while (p1 < pend && (re_opcode_t) *p1 == no_op)
3995             p1++;
3996
3997           if (p1 < pend && (re_opcode_t) *p1 == start_memory)
3998             {
3999               /* We have a new highest active register now.  This will
4000                  get reset at the start_memory we are about to get to,
4001                  but we will have saved all the registers relevant to
4002                  this repetition op, as described above.  */
4003               highest_active_reg = *(p1 + 1) + *(p1 + 2);
4004               if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
4005                 lowest_active_reg = *(p1 + 1);
4006             }
4007
4008           DEBUG_PRINT1 (":\n");
4009           PUSH_FAILURE_POINT (p + mcnt, d, -2);
4010           break;
4011
4012
4013         /* A smart repeat ends with `maybe_pop_jump'.
4014            We change it to either `pop_failure_jump' or `jump'.  */
4015         case maybe_pop_jump:
4016           EXTRACT_NUMBER_AND_INCR (mcnt, p);
4017           DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
4018           {
4019             register unsigned char *p2 = p;
4020
4021             /* Compare the beginning of the repeat with what in the
4022                pattern follows its end. If we can establish that there
4023                is nothing that they would both match, i.e., that we
4024                would have to backtrack because of (as in, e.g., `a*a')
4025                then we can change to pop_failure_jump, because we'll
4026                never have to backtrack.
4027
4028                This is not true in the case of alternatives: in
4029                `(a|ab)*' we do need to backtrack to the `ab' alternative
4030                (e.g., if the string was `ab').  But instead of trying to
4031                detect that here, the alternative has put on a dummy
4032                failure point which is what we will end up popping.  */
4033
4034             /* Skip over open/close-group commands.  */
4035             while (p2 + 2 < pend
4036                    && ((re_opcode_t) *p2 == stop_memory
4037                        || (re_opcode_t) *p2 == start_memory))
4038               p2 += 3;                  /* Skip over args, too.  */
4039
4040             /* If we're at the end of the pattern, we can change.  */
4041             if (p2 == pend)
4042               {
4043                 /* Consider what happens when matching ":\(.*\)"
4044                    against ":/".  I don't really understand this code
4045                    yet.  */
4046                 p[-3] = (unsigned char) pop_failure_jump;
4047                 DEBUG_PRINT1
4048                   ("  End of pattern: change to `pop_failure_jump'.\n");
4049               }
4050
4051             else if ((re_opcode_t) *p2 == exactn
4052                      || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
4053               {
4054                 register unsigned char c
4055                   = *p2 == (unsigned char) endline ? '\n' : p2[2];
4056                 p1 = p + mcnt;
4057
4058                 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
4059                    to the `maybe_finalize_jump' of this case.  Examine what
4060                    follows.  */
4061                 if ((re_opcode_t) p1[3] == exactn && p1[5] != c)
4062                   {
4063                     p[-3] = (unsigned char) pop_failure_jump;
4064                     DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
4065                                   c, p1[5]);
4066                   }
4067
4068                 else if ((re_opcode_t) p1[3] == charset
4069                          || (re_opcode_t) p1[3] == charset_not)
4070                   {
4071                     int not = (re_opcode_t) p1[3] == charset_not;
4072
4073                     if (c < (unsigned char) (p1[4] * BYTEWIDTH)
4074                         && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
4075                       not = !not;
4076
4077                     /* `not' is equal to 1 if c would match, which means
4078                         that we can't change to pop_failure_jump.  */
4079                     if (!not)
4080                       {
4081                         p[-3] = (unsigned char) pop_failure_jump;
4082                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
4083                       }
4084                   }
4085               }
4086           }
4087           p -= 2;               /* Point at relative address again.  */
4088           if ((re_opcode_t) p[-1] != pop_failure_jump)
4089             {
4090               p[-1] = (unsigned char) jump;
4091               DEBUG_PRINT1 ("  Match => jump.\n");
4092               goto unconditional_jump;
4093             }
4094         /* Note fall through.  */
4095
4096
4097         /* The end of a simple repeat has a pop_failure_jump back to
4098            its matching on_failure_jump, where the latter will push a
4099            failure point.  The pop_failure_jump takes off failure
4100            points put on by this pop_failure_jump's matching
4101            on_failure_jump; we got through the pattern to here from the
4102            matching on_failure_jump, so didn't fail.  */
4103         case pop_failure_jump:
4104           {
4105             /* We need to pass separate storage for the lowest and
4106                highest registers, even though we don't care about the
4107                actual values.  Otherwise, we will restore only one
4108                register from the stack, since lowest will == highest in
4109                `pop_failure_point'.  */
4110             unsigned dummy_low_reg, dummy_high_reg;
4111             unsigned char *pdummy;
4112             const char *sdummy;
4113
4114             DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
4115             POP_FAILURE_POINT (sdummy, pdummy,
4116                                dummy_low_reg, dummy_high_reg,
4117                                reg_dummy, reg_dummy, reg_info_dummy);
4118           }
4119           /* Note fall through.  */
4120
4121
4122         /* Unconditionally jump (without popping any failure points).  */
4123         case jump:
4124         unconditional_jump:
4125           EXTRACT_NUMBER_AND_INCR (mcnt, p);    /* Get the amount to jump.  */
4126           DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
4127           p += mcnt;                            /* Do the jump.  */
4128           DEBUG_PRINT2 ("(to 0x%x).\n", p);
4129           break;
4130
4131
4132         /* We need this opcode so we can detect where alternatives end
4133            in `group_match_null_string_p' et al.  */
4134         case jump_past_alt:
4135           DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
4136           goto unconditional_jump;
4137
4138
4139         /* Normally, the on_failure_jump pushes a failure point, which
4140            then gets popped at pop_failure_jump.  We will end up at
4141            pop_failure_jump, also, and with a pattern of, say, `a+', we
4142            are skipping over the on_failure_jump, so we have to push
4143            something meaningless for pop_failure_jump to pop.  */
4144         case dummy_failure_jump:
4145           DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
4146           /* It doesn't matter what we push for the string here.  What
4147              the code at `fail' tests is the value for the pattern.  */
4148           PUSH_FAILURE_POINT (0, 0, -2);
4149           goto unconditional_jump;
4150
4151
4152         /* At the end of an alternative, we need to push a dummy failure
4153            point in case we are followed by a `pop_failure_jump', because
4154            we don't want the failure point for the alternative to be
4155            popped.  For example, matching `(a|ab)*' against `aab'
4156            requires that we match the `ab' alternative.  */
4157         case push_dummy_failure:
4158           DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
4159           /* See comments just above at `dummy_failure_jump' about the
4160              two zeroes.  */
4161           PUSH_FAILURE_POINT (0, 0, -2);
4162           break;
4163
4164         /* Have to succeed matching what follows at least n times.
4165            After that, handle like `on_failure_jump'.  */
4166         case succeed_n:
4167           EXTRACT_NUMBER (mcnt, p + 2);
4168           DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
4169
4170           assert (mcnt >= 0);
4171           /* Originally, this is how many times we HAVE to succeed.  */
4172           if (mcnt > 0)
4173             {
4174                mcnt--;
4175                p += 2;
4176                STORE_NUMBER_AND_INCR (p, mcnt);
4177                DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p, mcnt);
4178             }
4179           else if (mcnt == 0)
4180             {
4181               DEBUG_PRINT2 ("  Setting two bytes from 0x%x to no_op.\n", p+2);
4182               p[2] = (unsigned char) no_op;
4183               p[3] = (unsigned char) no_op;
4184               goto on_failure;
4185             }
4186           break;
4187
4188         case jump_n:
4189           EXTRACT_NUMBER (mcnt, p + 2);
4190           DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
4191
4192           /* Originally, this is how many times we CAN jump.  */
4193           if (mcnt)
4194             {
4195                mcnt--;
4196                STORE_NUMBER (p + 2, mcnt);
4197                goto unconditional_jump;
4198             }
4199           /* If don't have to jump any more, skip over the rest of command.  */
4200           else
4201             p += 4;
4202           break;
4203
4204         case set_number_at:
4205           {
4206             DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
4207
4208             EXTRACT_NUMBER_AND_INCR (mcnt, p);
4209             p1 = p + mcnt;
4210             EXTRACT_NUMBER_AND_INCR (mcnt, p);
4211             DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p1, mcnt);
4212             STORE_NUMBER (p1, mcnt);
4213             break;
4214           }
4215
4216         case wordbound:
4217           DEBUG_PRINT1 ("EXECUTING wordbound.\n");
4218           if (AT_WORD_BOUNDARY (d))
4219             break;
4220           goto fail;
4221
4222         case notwordbound:
4223           DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
4224           if (AT_WORD_BOUNDARY (d))
4225             goto fail;
4226           break;
4227
4228         case wordbeg:
4229           DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
4230           if (WORDCHAR_P (d) && (AT_STRINGS_BEG (d) || !WORDCHAR_P (d - 1)))
4231             break;
4232           goto fail;
4233
4234         case wordend:
4235           DEBUG_PRINT1 ("EXECUTING wordend.\n");
4236           if (!AT_STRINGS_BEG (d) && WORDCHAR_P (d - 1)
4237               && (!WORDCHAR_P (d) || AT_STRINGS_END (d)))
4238             break;
4239           goto fail;
4240
4241 #ifdef emacs
4242 #ifdef emacs19
4243         case before_dot:
4244           DEBUG_PRINT1 ("EXECUTING before_dot.\n");
4245           if (PTR_CHAR_POS ((unsigned char *) d) >= point)
4246             goto fail;
4247           break;
4248
4249         case at_dot:
4250           DEBUG_PRINT1 ("EXECUTING at_dot.\n");
4251           if (PTR_CHAR_POS ((unsigned char *) d) != point)
4252             goto fail;
4253           break;
4254
4255         case after_dot:
4256           DEBUG_PRINT1 ("EXECUTING after_dot.\n");
4257           if (PTR_CHAR_POS ((unsigned char *) d) <= point)
4258             goto fail;
4259           break;
4260 #else /* not emacs19 */
4261         case at_dot:
4262           DEBUG_PRINT1 ("EXECUTING at_dot.\n");
4263           if (PTR_CHAR_POS ((unsigned char *) d) + 1 != point)
4264             goto fail;
4265           break;
4266 #endif /* not emacs19 */
4267
4268         case syntaxspec:
4269           DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
4270           mcnt = *p++;
4271           goto matchsyntax;
4272
4273         case wordchar:
4274           DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
4275           mcnt = (int) Sword;
4276         matchsyntax:
4277           PREFETCH ();
4278           if (SYNTAX (*d++) != (enum syntaxcode) mcnt)
4279             goto fail;
4280           SET_REGS_MATCHED ();
4281           break;
4282
4283         case notsyntaxspec:
4284           DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
4285           mcnt = *p++;
4286           goto matchnotsyntax;
4287
4288         case notwordchar:
4289           DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
4290           mcnt = (int) Sword;
4291         matchnotsyntax:
4292           PREFETCH ();
4293           if (SYNTAX (*d++) == (enum syntaxcode) mcnt)
4294             goto fail;
4295           SET_REGS_MATCHED ();
4296           break;
4297
4298 #else /* not emacs */
4299         case wordchar:
4300           DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
4301           PREFETCH ();
4302           if (!WORDCHAR_P (d))
4303             goto fail;
4304           SET_REGS_MATCHED ();
4305           d++;
4306           break;
4307
4308         case notwordchar:
4309           DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
4310           PREFETCH ();
4311           if (WORDCHAR_P (d))
4312             goto fail;
4313           SET_REGS_MATCHED ();
4314           d++;
4315           break;
4316 #endif /* not emacs */
4317
4318         default:
4319           abort ();
4320         }
4321       continue;  /* Successfully executed one pattern command; keep going.  */
4322
4323
4324     /* We goto here if a matching operation fails. */
4325     fail:
4326       if (!FAIL_STACK_EMPTY ())
4327         { /* A restart point is known.  Restore to that state.  */
4328           DEBUG_PRINT1 ("\nFAIL:\n");
4329           POP_FAILURE_POINT (d, p,
4330                              lowest_active_reg, highest_active_reg,
4331                              regstart, regend, reg_info);
4332
4333           /* If this failure point is a dummy, try the next one.  */
4334           if (!p)
4335             goto fail;
4336
4337           /* If we failed to the end of the pattern, don't examine *p.  */
4338           assert (p <= pend);
4339           if (p < pend)
4340             {
4341               boolean is_a_jump_n = false;
4342
4343               /* If failed to a backwards jump that's part of a repetition
4344                  loop, need to pop this failure point and use the next one.  */
4345               switch ((re_opcode_t) *p)
4346                 {
4347                 case jump_n:
4348                   is_a_jump_n = true;
4349                 case maybe_pop_jump:
4350                 case pop_failure_jump:
4351                 case jump:
4352                   p1 = p + 1;
4353                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4354                   p1 += mcnt;
4355
4356                   if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
4357                       || (!is_a_jump_n
4358                           && (re_opcode_t) *p1 == on_failure_jump))
4359                     goto fail;
4360                   break;
4361                 default:
4362                   /* do nothing */ ;
4363                 }
4364             }
4365
4366           if (d >= string1 && d <= end1)
4367             dend = end_match_1;
4368         }
4369       else
4370         break;   /* Matching at this starting point really fails.  */
4371     } /* for (;;) */
4372
4373   if (best_regs_set)
4374     goto restore_best_regs;
4375
4376   FREE_VARIABLES ();
4377
4378   return -1;                            /* Failure to match.  */
4379 } /* re_match_2 */
4380 \f
4381 /* Subroutine definitions for re_match_2.  */
4382
4383
4384 /* We are passed P pointing to a register number after a start_memory.
4385
4386    Return true if the pattern up to the corresponding stop_memory can
4387    match the empty string, and false otherwise.
4388
4389    If we find the matching stop_memory, sets P to point to one past its number.
4390    Otherwise, sets P to an undefined byte less than or equal to END.
4391
4392    We don't handle duplicates properly (yet).  */
4393
4394 static boolean
4395 group_match_null_string_p (p, end, reg_info)
4396     unsigned char **p, *end;
4397     register_info_type *reg_info;
4398 {
4399   int mcnt;
4400   /* Point to after the args to the start_memory.  */
4401   unsigned char *p1 = *p + 2;
4402
4403   while (p1 < end)
4404     {
4405       /* Skip over opcodes that can match nothing, and return true or
4406          false, as appropriate, when we get to one that can't, or to the
4407          matching stop_memory.  */
4408
4409       switch ((re_opcode_t) *p1)
4410         {
4411         /* Could be either a loop or a series of alternatives.  */
4412         case on_failure_jump:
4413           p1++;
4414           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4415
4416           /* If the next operation is not a jump backwards in the
4417              pattern.  */
4418
4419           if (mcnt >= 0)
4420             {
4421               /* Go through the on_failure_jumps of the alternatives,
4422                  seeing if any of the alternatives cannot match nothing.
4423                  The last alternative starts with only a jump,
4424                  whereas the rest start with on_failure_jump and end
4425                  with a jump, e.g., here is the pattern for `a|b|c':
4426
4427                  /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
4428                  /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
4429                  /exactn/1/c
4430
4431                  So, we have to first go through the first (n-1)
4432                  alternatives and then deal with the last one separately.  */
4433
4434
4435               /* Deal with the first (n-1) alternatives, which start
4436                  with an on_failure_jump (see above) that jumps to right
4437                  past a jump_past_alt.  */
4438
4439               while ((re_opcode_t) p1[mcnt-3] == jump_past_alt)
4440                 {
4441                   /* `mcnt' holds how many bytes long the alternative
4442                      is, including the ending `jump_past_alt' and
4443                      its number.  */
4444
4445                   if (!alt_match_null_string_p (p1, p1 + mcnt - 3,
4446                                                       reg_info))
4447                     return false;
4448
4449                   /* Move to right after this alternative, including the
4450                      jump_past_alt.  */
4451                   p1 += mcnt;
4452
4453                   /* Break if it's the beginning of an n-th alternative
4454                      that doesn't begin with an on_failure_jump.  */
4455                   if ((re_opcode_t) *p1 != on_failure_jump)
4456                     break;
4457
4458                   /* Still have to check that it's not an n-th
4459                      alternative that starts with an on_failure_jump.  */
4460                   p1++;
4461                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4462                   if ((re_opcode_t) p1[mcnt-3] != jump_past_alt)
4463                     {
4464                       /* Get to the beginning of the n-th alternative.  */
4465                       p1 -= 3;
4466                       break;
4467                     }
4468                 }
4469
4470               /* Deal with the last alternative: go back and get number
4471                  of the `jump_past_alt' just before it.  `mcnt' contains
4472                  the length of the alternative.  */
4473               EXTRACT_NUMBER (mcnt, p1 - 2);
4474
4475               if (!alt_match_null_string_p (p1, p1 + mcnt, reg_info))
4476                 return false;
4477
4478               p1 += mcnt;       /* Get past the n-th alternative.  */
4479             } /* if mcnt > 0 */
4480           break;
4481
4482
4483         case stop_memory:
4484           assert (p1[1] == **p);
4485           *p = p1 + 2;
4486           return true;
4487
4488
4489         default:
4490           if (!common_op_match_null_string_p (&p1, end, reg_info))
4491             return false;
4492         }
4493     } /* while p1 < end */
4494
4495   return false;
4496 } /* group_match_null_string_p */
4497
4498
4499 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
4500    It expects P to be the first byte of a single alternative and END one
4501    byte past the last. The alternative can contain groups.  */
4502
4503 static boolean
4504 alt_match_null_string_p (p, end, reg_info)
4505     unsigned char *p, *end;
4506     register_info_type *reg_info;
4507 {
4508   int mcnt;
4509   unsigned char *p1 = p;
4510
4511   while (p1 < end)
4512     {
4513       /* Skip over opcodes that can match nothing, and break when we get
4514          to one that can't.  */
4515
4516       switch ((re_opcode_t) *p1)
4517         {
4518         /* It's a loop.  */
4519         case on_failure_jump:
4520           p1++;
4521           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4522           p1 += mcnt;
4523           break;
4524
4525         default:
4526           if (!common_op_match_null_string_p (&p1, end, reg_info))
4527             return false;
4528         }
4529     }  /* while p1 < end */
4530
4531   return true;
4532 } /* alt_match_null_string_p */
4533
4534
4535 /* Deals with the ops common to group_match_null_string_p and
4536    alt_match_null_string_p.
4537
4538    Sets P to one after the op and its arguments, if any.  */
4539
4540 static boolean
4541 common_op_match_null_string_p (p, end, reg_info)
4542     unsigned char **p, *end;
4543     register_info_type *reg_info;
4544 {
4545   int mcnt;
4546   boolean ret;
4547   int reg_no;
4548   unsigned char *p1 = *p;
4549
4550   switch ((re_opcode_t) *p1++)
4551     {
4552     case no_op:
4553     case begline:
4554     case endline:
4555     case begbuf:
4556     case endbuf:
4557     case wordbeg:
4558     case wordend:
4559     case wordbound:
4560     case notwordbound:
4561 #ifdef emacs
4562     case before_dot:
4563     case at_dot:
4564     case after_dot:
4565 #endif
4566       break;
4567
4568     case start_memory:
4569       reg_no = *p1;
4570       assert (reg_no > 0 && reg_no <= MAX_REGNUM);
4571       ret = group_match_null_string_p (&p1, end, reg_info);
4572
4573       /* Have to set this here in case we're checking a group which
4574          contains a group and a back reference to it.  */
4575
4576       if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
4577         REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
4578
4579       if (!ret)
4580         return false;
4581       break;
4582
4583     /* If this is an optimized succeed_n for zero times, make the jump.  */
4584     case jump:
4585       EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4586       if (mcnt >= 0)
4587         p1 += mcnt;
4588       else
4589         return false;
4590       break;
4591
4592     case succeed_n:
4593       /* Get to the number of times to succeed.  */
4594       p1 += 2;
4595       EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4596
4597       if (mcnt == 0)
4598         {
4599           p1 -= 4;
4600           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4601           p1 += mcnt;
4602         }
4603       else
4604         return false;
4605       break;
4606
4607     case duplicate:
4608       if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
4609         return false;
4610       break;
4611
4612     case set_number_at:
4613       p1 += 4;
4614
4615     default:
4616       /* All other opcodes mean we cannot match the empty string.  */
4617       return false;
4618   }
4619
4620   *p = p1;
4621   return true;
4622 } /* common_op_match_null_string_p */
4623
4624
4625 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
4626    bytes; nonzero otherwise.  */
4627
4628 static int
4629 bcmp_translate (s1, s2, len, translate)
4630      unsigned char *s1, *s2;
4631      register int len;
4632      char *translate;
4633 {
4634   register unsigned char *p1 = s1, *p2 = s2;
4635   while (len)
4636     {
4637       if (translate[*p1++] != translate[*p2++]) return 1;
4638       len--;
4639     }
4640   return 0;
4641 }
4642 \f
4643 /* Entry points for GNU code.  */
4644
4645 /* re_compile_pattern is the GNU regular expression compiler: it
4646    compiles PATTERN (of length SIZE) and puts the result in BUFP.
4647    Returns 0 if the pattern was valid, otherwise an error string.
4648
4649    Assumes the `allocated' (and perhaps `buffer') and `translate' fields
4650    are set in BUFP on entry.
4651
4652    We call regex_compile to do the actual compilation.  */
4653
4654 const char *
4655 re_compile_pattern (pattern, length, bufp)
4656      const char *pattern;
4657      int length;
4658      struct re_pattern_buffer *bufp;
4659 {
4660   reg_errcode_t ret;
4661
4662   /* GNU code is written to assume at least RE_NREGS registers will be set
4663      (and at least one extra will be -1).  */
4664   bufp->regs_allocated = REGS_UNALLOCATED;
4665
4666   /* And GNU code determines whether or not to get register information
4667      by passing null for the REGS argument to re_match, etc., not by
4668      setting no_sub.  */
4669   bufp->no_sub = 0;
4670
4671   /* Match anchors at newline.  */
4672   bufp->newline_anchor = 1;
4673
4674   ret = regex_compile (pattern, length, re_syntax_options, bufp);
4675
4676   return re_error_msg[(int) ret];
4677 }
4678 \f
4679 /* Entry points compatible with 4.2 BSD regex library.  We don't define
4680    them if this is an Emacs or POSIX compilation.  */
4681
4682 #if !defined (emacs) && !defined (_POSIX_SOURCE)
4683
4684 /* BSD has one and only one pattern buffer.  */
4685 static struct re_pattern_buffer re_comp_buf;
4686
4687 char *
4688 re_comp (s)
4689     const char *s;
4690 {
4691   reg_errcode_t ret;
4692
4693   if (!s)
4694     {
4695       if (!re_comp_buf.buffer)
4696         return "No previous regular expression";
4697       return 0;
4698     }
4699
4700   if (!re_comp_buf.buffer)
4701     {
4702       re_comp_buf.buffer = (unsigned char *) malloc (200);
4703       if (re_comp_buf.buffer == NULL)
4704         return "Memory exhausted";
4705       re_comp_buf.allocated = 200;
4706
4707       re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
4708       if (re_comp_buf.fastmap == NULL)
4709         return "Memory exhausted";
4710     }
4711
4712   /* Since `re_exec' always passes NULL for the `regs' argument, we
4713      don't need to initialize the pattern buffer fields which affect it.  */
4714
4715   /* Match anchors at newlines.  */
4716   re_comp_buf.newline_anchor = 1;
4717
4718   ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
4719
4720   /* Yes, we're discarding `const' here.  */
4721   return (char *) re_error_msg[(int) ret];
4722 }
4723
4724
4725 int
4726 re_exec (s)
4727     const char *s;
4728 {
4729   const int len = strlen (s);
4730   return
4731     0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0);
4732 }
4733 #endif /* not emacs and not _POSIX_SOURCE */
4734 \f
4735 /* POSIX.2 functions.  Don't define these for Emacs.  */
4736
4737 #ifndef emacs
4738
4739 /* regcomp takes a regular expression as a string and compiles it.
4740
4741    PREG is a regex_t *.  We do not expect any fields to be initialized,
4742    since POSIX says we shouldn't.  Thus, we set
4743
4744      `buffer' to the compiled pattern;
4745      `used' to the length of the compiled pattern;
4746      `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
4747        REG_EXTENDED bit in CFLAGS is set; otherwise, to
4748        RE_SYNTAX_POSIX_BASIC;
4749      `newline_anchor' to REG_NEWLINE being set in CFLAGS;
4750      `fastmap' and `fastmap_accurate' to zero;
4751      `re_nsub' to the number of subexpressions in PATTERN.
4752
4753    PATTERN is the address of the pattern string.
4754
4755    CFLAGS is a series of bits which affect compilation.
4756
4757      If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
4758      use POSIX basic syntax.
4759
4760      If REG_NEWLINE is set, then . and [^...] don't match newline.
4761      Also, regexec will try a match beginning after every newline.
4762
4763      If REG_ICASE is set, then we considers upper- and lowercase
4764      versions of letters to be equivalent when matching.
4765
4766      If REG_NOSUB is set, then when PREG is passed to regexec, that
4767      routine will report only success or failure, and nothing about the
4768      registers.
4769
4770    It returns 0 if it succeeds, nonzero if it doesn't.  (See regex.h for
4771    the return codes and their meanings.)  */
4772
4773 int
4774 regcomp (preg, pattern, cflags)
4775     regex_t *preg;
4776     const char *pattern;
4777     int cflags;
4778 {
4779   reg_errcode_t ret;
4780   unsigned syntax
4781     = (cflags & REG_EXTENDED) ?
4782       RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
4783
4784   /* regex_compile will allocate the space for the compiled pattern.  */
4785   preg->buffer = 0;
4786   preg->allocated = 0;
4787
4788   /* Don't bother to use a fastmap when searching.  This simplifies the
4789      REG_NEWLINE case: if we used a fastmap, we'd have to put all the
4790      characters after newlines into the fastmap.  This way, we just try
4791      every character.  */
4792   preg->fastmap = 0;
4793
4794   if (cflags & REG_ICASE)
4795     {
4796       unsigned i;
4797
4798       preg->translate = (char *) malloc (CHAR_SET_SIZE);
4799       if (preg->translate == NULL)
4800         return (int) REG_ESPACE;
4801
4802       /* Map uppercase characters to corresponding lowercase ones.  */
4803       for (i = 0; i < CHAR_SET_SIZE; i++)
4804         preg->translate[i] = ISUPPER (i) ? tolower (i) : i;
4805     }
4806   else
4807     preg->translate = NULL;
4808
4809   /* If REG_NEWLINE is set, newlines are treated differently.  */
4810   if (cflags & REG_NEWLINE)
4811     { /* REG_NEWLINE implies neither . nor [^...] match newline.  */
4812       syntax &= ~RE_DOT_NEWLINE;
4813       syntax |= RE_HAT_LISTS_NOT_NEWLINE;
4814       /* It also changes the matching behavior.  */
4815       preg->newline_anchor = 1;
4816     }
4817   else
4818     preg->newline_anchor = 0;
4819
4820   preg->no_sub = !!(cflags & REG_NOSUB);
4821
4822   /* POSIX says a null character in the pattern terminates it, so we
4823      can use strlen here in compiling the pattern.  */
4824   ret = regex_compile (pattern, strlen (pattern), syntax, preg);
4825
4826   /* POSIX doesn't distinguish between an unmatched open-group and an
4827      unmatched close-group: both are REG_EPAREN.  */
4828   if (ret == REG_ERPAREN) ret = REG_EPAREN;
4829
4830   return (int) ret;
4831 }
4832
4833
4834 /* regexec searches for a given pattern, specified by PREG, in the
4835    string STRING.
4836
4837    If NMATCH is zero or REG_NOSUB was set in the cflags argument to
4838    `regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at
4839    least NMATCH elements, and we set them to the offsets of the
4840    corresponding matched substrings.
4841
4842    EFLAGS specifies `execution flags' which affect matching: if
4843    REG_NOTBOL is set, then ^ does not match at the beginning of the
4844    string; if REG_NOTEOL is set, then $ does not match at the end.
4845
4846    We return 0 if we find a match and REG_NOMATCH if not.  */
4847
4848 int
4849 regexec (preg, string, nmatch, pmatch, eflags)
4850     const regex_t *preg;
4851     const char *string;
4852     size_t nmatch;
4853     regmatch_t pmatch[];
4854     int eflags;
4855 {
4856   int ret;
4857   struct re_registers regs;
4858   regex_t private_preg;
4859   int len = strlen (string);
4860   boolean want_reg_info = !preg->no_sub && nmatch > 0;
4861
4862   private_preg = *preg;
4863
4864   private_preg.not_bol = !!(eflags & REG_NOTBOL);
4865   private_preg.not_eol = !!(eflags & REG_NOTEOL);
4866
4867   /* The user has told us exactly how many registers to return
4868      information about, via `nmatch'.  We have to pass that on to the
4869      matching routines.  */
4870   private_preg.regs_allocated = REGS_FIXED;
4871
4872   if (want_reg_info)
4873     {
4874       regs.num_regs = nmatch;
4875       regs.start = TALLOC (nmatch, regoff_t);
4876       regs.end = TALLOC (nmatch, regoff_t);
4877       if (regs.start == NULL || regs.end == NULL)
4878         return (int) REG_NOMATCH;
4879     }
4880
4881   /* Perform the searching operation.  */
4882   ret = re_search (&private_preg, string, len,
4883                    /* start: */ 0, /* range: */ len,
4884                    want_reg_info ? &regs : (struct re_registers *) 0);
4885
4886   /* Copy the register information to the POSIX structure.  */
4887   if (want_reg_info)
4888     {
4889       if (ret >= 0)
4890         {
4891           unsigned r;
4892
4893           for (r = 0; r < nmatch; r++)
4894             {
4895               pmatch[r].rm_so = regs.start[r];
4896               pmatch[r].rm_eo = regs.end[r];
4897             }
4898         }
4899
4900       /* If we needed the temporary register info, free the space now.  */
4901       free (regs.start);
4902       free (regs.end);
4903     }
4904
4905   /* We want zero return to mean success, unlike `re_search'.  */
4906   return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
4907 }
4908
4909
4910 /* Returns a message corresponding to an error code, ERRCODE, returned
4911    from either regcomp or regexec.   We don't use PREG here.  */
4912
4913 size_t
4914 regerror (errcode, preg, errbuf, errbuf_size)
4915     int errcode;
4916     const regex_t *preg;
4917     char *errbuf;
4918     size_t errbuf_size;
4919 {
4920   const char *msg;
4921   size_t msg_size;
4922
4923   if (errcode < 0
4924       || errcode >= (sizeof (re_error_msg) / sizeof (re_error_msg[0])))
4925     /* Only error codes returned by the rest of the code should be passed
4926        to this routine.  If we are given anything else, or if other regex
4927        code generates an invalid error code, then the program has a bug.
4928        Dump core so we can fix it.  */
4929     abort ();
4930
4931   msg = re_error_msg[errcode];
4932
4933   /* POSIX doesn't require that we do anything in this case, but why
4934      not be nice.  */
4935   if (! msg)
4936     msg = "Success";
4937
4938   msg_size = strlen (msg) + 1; /* Includes the null.  */
4939
4940   if (errbuf_size != 0)
4941     {
4942       if (msg_size > errbuf_size)
4943         {
4944           strncpy (errbuf, msg, errbuf_size - 1);
4945           errbuf[errbuf_size - 1] = 0;
4946         }
4947       else
4948         strcpy (errbuf, msg);
4949     }
4950
4951   return msg_size;
4952 }
4953
4954
4955 /* Free dynamically allocated space used by PREG.  */
4956
4957 void
4958 regfree (preg)
4959     regex_t *preg;
4960 {
4961   if (preg->buffer != NULL)
4962     free (preg->buffer);
4963   preg->buffer = NULL;
4964
4965   preg->allocated = 0;
4966   preg->used = 0;
4967
4968   if (preg->fastmap != NULL)
4969     free (preg->fastmap);
4970   preg->fastmap = NULL;
4971   preg->fastmap_accurate = 0;
4972
4973   if (preg->translate != NULL)
4974     free (preg->translate);
4975   preg->translate = NULL;
4976 }
4977
4978 #endif /* not emacs  */
4979 \f
4980 /*
4981 Local variables:
4982 make-backup-files: t
4983 version-control: t
4984 trim-versions-without-asking: nil
4985 End:
4986 */