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