lib/regex.c

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