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