lib/regex.c

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