src/regex.c

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