lib/regex.c

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