libiberty/regex.c

   1 /* Extended regular expression matching and search library,
   2    version 0.12.
   3    (Implements POSIX draft P1003.2/D11.2, except for some of the
   4    internationalization features.)
   5    Copyright (C) 1993-1999, 2000, 2001 Free Software Foundation, Inc.
   6    This file is part of the GNU C Library.
   7
   8    The GNU C Library is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU Lesser General Public
  10    License as published by the Free Software Foundation; either
  11    version 2.1 of the License, or (at your option) any later version.
  12
  13    The GNU C Library 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 GNU
  16    Lesser General Public License for more details.
  17
  18    You should have received a copy of the GNU Lesser General Public
  19    License along with the GNU C Library; if not, write to the Free
  20    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  21    02111-1307 USA.  */
  22
  23 /* This file has been modified for usage in libiberty.  It includes "xregex.h"
  24    instead of <regex.h>.  The "xregex.h" header file renames all external
  25    routines with an "x" prefix so they do not collide with the native regex
  26    routines or with other components regex routines. */
  27 /* AIX requires this to be the first thing in the file. */
  28 #if defined _AIX && !defined REGEX_MALLOC
  29   #pragma alloca
  30 #endif
  31
  32 #undef  _GNU_SOURCE
  33 #define _GNU_SOURCE
  34
  35 #ifdef HAVE_CONFIG_H
  36 # include <config.h>
  37 #endif
  38
  39 #ifndef PARAMS
  40 # if defined __GNUC__ || (defined __STDC__ && __STDC__)
  41 #  define PARAMS(args) args
  42 # else
  43 #  define PARAMS(args) ()
  44 # endif  /* GCC.  */
  45 #endif  /* Not PARAMS.  */
  46
  47 #ifndef INSIDE_RECURSION
  48
  49 # if defined STDC_HEADERS && !defined emacs
  50 #  include <stddef.h>
  51 # else
  52 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
  53 #  include <sys/types.h>
  54 # endif
  55
  56 # define WIDE_CHAR_SUPPORT (HAVE_WCTYPE_H && HAVE_WCHAR_H && HAVE_BTOWC)
  57
  58 /* For platform which support the ISO C amendement 1 functionality we
  59    support user defined character classes.  */
  60 # if defined _LIBC || WIDE_CHAR_SUPPORT
  61 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>.  */
  62 #  include <wchar.h>
  63 #  include <wctype.h>
  64 # endif
  65
  66 # ifdef _LIBC
  67 /* We have to keep the namespace clean.  */
  68 #  define regfree(preg) __regfree (preg)
  69 #  define regexec(pr, st, nm, pm, ef) __regexec (pr, st, nm, pm, ef)
  70 #  define regcomp(preg, pattern, cflags) __regcomp (preg, pattern, cflags)
  71 #  define regerror(errcode, preg, errbuf, errbuf_size) \
  72         __regerror(errcode, preg, errbuf, errbuf_size)
  73 #  define re_set_registers(bu, re, nu, st, en) \
  74         __re_set_registers (bu, re, nu, st, en)
  75 #  define re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop) \
  76         __re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
  77 #  define re_match(bufp, string, size, pos, regs) \
  78         __re_match (bufp, string, size, pos, regs)
  79 #  define re_search(bufp, string, size, startpos, range, regs) \
  80         __re_search (bufp, string, size, startpos, range, regs)
  81 #  define re_compile_pattern(pattern, length, bufp) \
  82         __re_compile_pattern (pattern, length, bufp)
  83 #  define re_set_syntax(syntax) __re_set_syntax (syntax)
  84 #  define re_search_2(bufp, st1, s1, st2, s2, startpos, range, regs, stop) \
  85         __re_search_2 (bufp, st1, s1, st2, s2, startpos, range, regs, stop)
  86 #  define re_compile_fastmap(bufp) __re_compile_fastmap (bufp)
  87
  88 #  define btowc __btowc
  89
  90 /* We are also using some library internals.  */
  91 #  include <locale/localeinfo.h>
  92 #  include <locale/elem-hash.h>
  93 #  include <langinfo.h>
  94 #  include <locale/coll-lookup.h>
  95 # endif
  96
  97 /* This is for other GNU distributions with internationalized messages.  */
  98 # if HAVE_LIBINTL_H || defined _LIBC
  99 #  include <libintl.h>
 100 #  ifdef _LIBC
 101 #   undef gettext
 102 #   define gettext(msgid) __dcgettext ("libc", msgid, LC_MESSAGES)
 103 #  endif
 104 # else
 105 #  define gettext(msgid) (msgid)
 106 # endif
 107
 108 # ifndef gettext_noop
 109 /* This define is so xgettext can find the internationalizable
 110    strings.  */
 111 #  define gettext_noop(String) String
 112 # endif
 113
 114 /* The `emacs' switch turns on certain matching commands
 115    that make sense only in Emacs. */
 116 # ifdef emacs
 117
 118 #  include "lisp.h"
 119 #  include "buffer.h"
 120 #  include "syntax.h"
 121
 122 # else  /* not emacs */
 123
 124 /* If we are not linking with Emacs proper,
 125    we can't use the relocating allocator
 126    even if config.h says that we can.  */
 127 #  undef REL_ALLOC
 128
 129 #  if defined STDC_HEADERS || defined _LIBC
 130 #   include <stdlib.h>
 131 #  else
 132 char *malloc ();
 133 char *realloc ();
 134 #  endif
 135
 136 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
 137    If nothing else has been done, use the method below.  */
 138 #  ifdef INHIBIT_STRING_HEADER
 139 #   if !(defined HAVE_BZERO && defined HAVE_BCOPY)
 140 #    if !defined bzero && !defined bcopy
 141 #     undef INHIBIT_STRING_HEADER
 142 #    endif
 143 #   endif
 144 #  endif
 145
 146 /* This is the normal way of making sure we have a bcopy and a bzero.
 147    This is used in most programs--a few other programs avoid this
 148    by defining INHIBIT_STRING_HEADER.  */
 149 #  ifndef INHIBIT_STRING_HEADER
 150 #   if defined HAVE_STRING_H || defined STDC_HEADERS || defined _LIBC
 151 #    include <string.h>
 152 #    ifndef bzero
 153 #     ifndef _LIBC
 154 #      define bzero(s, n)       (memset (s, '\0', n), (s))
 155 #     else
 156 #      define bzero(s, n)       __bzero (s, n)
 157 #     endif
 158 #    endif
 159 #   else
 160 #    include <strings.h>
 161 #    ifndef memcmp
 162 #     define memcmp(s1, s2, n)  bcmp (s1, s2, n)
 163 #    endif
 164 #    ifndef memcpy
 165 #     define memcpy(d, s, n)    (bcopy (s, d, n), (d))
 166 #    endif
 167 #   endif
 168 #  endif
 169
 170 /* Define the syntax stuff for \<, \>, etc.  */
 171
 172 /* This must be nonzero for the wordchar and notwordchar pattern
 173    commands in re_match_2.  */
 174 #  ifndef Sword
 175 #   define Sword 1
 176 #  endif
 177
 178 #  ifdef SWITCH_ENUM_BUG
 179 #   define SWITCH_ENUM_CAST(x) ((int)(x))
 180 #  else
 181 #   define SWITCH_ENUM_CAST(x) (x)
 182 #  endif
 183
 184 # endif /* not emacs */
 185
 186 # if defined _LIBC || HAVE_LIMITS_H
 187 #  include <limits.h>
 188 # endif
 189
 190 # ifndef MB_LEN_MAX
 191 #  define MB_LEN_MAX 1
 192 # endif
 193 \f
 194 /* Get the interface, including the syntax bits.  */
 195 # include "xregex.h"  /* change for libiberty */
 196
 197 /* isalpha etc. are used for the character classes.  */
 198 # include <ctype.h>
 199
 200 /* Jim Meyering writes:
 201
 202    "... Some ctype macros are valid only for character codes that
 203    isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
 204    using /bin/cc or gcc but without giving an ansi option).  So, all
 205    ctype uses should be through macros like ISPRINT...  If
 206    STDC_HEADERS is defined, then autoconf has verified that the ctype
 207    macros don't need to be guarded with references to isascii. ...
 208    Defining isascii to 1 should let any compiler worth its salt
 209    eliminate the && through constant folding."
 210    Solaris defines some of these symbols so we must undefine them first.  */
 211
 212 # undef ISASCII
 213 # if defined STDC_HEADERS || (!defined isascii && !defined HAVE_ISASCII)
 214 #  define ISASCII(c) 1
 215 # else
 216 #  define ISASCII(c) isascii(c)
 217 # endif
 218
 219 # ifdef isblank
 220 #  define ISBLANK(c) (ISASCII (c) && isblank (c))
 221 # else
 222 #  define ISBLANK(c) ((c) == ' ' || (c) == '\t')
 223 # endif
 224 # ifdef isgraph
 225 #  define ISGRAPH(c) (ISASCII (c) && isgraph (c))
 226 # else
 227 #  define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
 228 # endif
 229
 230 # undef ISPRINT
 231 # define ISPRINT(c) (ISASCII (c) && isprint (c))
 232 # define ISDIGIT(c) (ISASCII (c) && isdigit (c))
 233 # define ISALNUM(c) (ISASCII (c) && isalnum (c))
 234 # define ISALPHA(c) (ISASCII (c) && isalpha (c))
 235 # define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
 236 # define ISLOWER(c) (ISASCII (c) && islower (c))
 237 # define ISPUNCT(c) (ISASCII (c) && ispunct (c))
 238 # define ISSPACE(c) (ISASCII (c) && isspace (c))
 239 # define ISUPPER(c) (ISASCII (c) && isupper (c))
 240 # define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
 241
 242 # ifdef _tolower
 243 #  define TOLOWER(c) _tolower(c)
 244 # else
 245 #  define TOLOWER(c) tolower(c)
 246 # endif
 247
 248 # ifndef NULL
 249 #  define NULL (void *)0
 250 # endif
 251
 252 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
 253    since ours (we hope) works properly with all combinations of
 254    machines, compilers, `char' and `unsigned char' argument types.
 255    (Per Bothner suggested the basic approach.)  */
 256 # undef SIGN_EXTEND_CHAR
 257 # if __STDC__
 258 #  define SIGN_EXTEND_CHAR(c) ((signed char) (c))
 259 # else  /* not __STDC__ */
 260 /* As in Harbison and Steele.  */
 261 #  define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
 262 # endif
 263 \f
 264 # ifndef emacs
 265 /* How many characters in the character set.  */
 266 #  define CHAR_SET_SIZE 256
 267
 268 #  ifdef SYNTAX_TABLE
 269
 270 extern char *re_syntax_table;
 271
 272 #  else /* not SYNTAX_TABLE */
 273
 274 static char re_syntax_table[CHAR_SET_SIZE];
 275
 276 static void init_syntax_once PARAMS ((void));
 277
 278 static void
 279 init_syntax_once ()
 280 {
 281    register int c;
 282    static int done = 0;
 283
 284    if (done)
 285      return;
 286    bzero (re_syntax_table, sizeof re_syntax_table);
 287
 288    for (c = 0; c < CHAR_SET_SIZE; ++c)
 289      if (ISALNUM (c))
 290         re_syntax_table[c] = Sword;
 291
 292    re_syntax_table['_'] = Sword;
 293
 294    done = 1;
 295 }
 296
 297 #  endif /* not SYNTAX_TABLE */
 298
 299 #  define SYNTAX(c) re_syntax_table[(unsigned char) (c)]
 300
 301 # endif /* emacs */
 302 \f
 303 /* Integer type for pointers.  */
 304 # if !defined _LIBC
 305 typedef unsigned long int uintptr_t;
 306 # endif
 307
 308 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
 309    use `alloca' instead of `malloc'.  This is because using malloc in
 310    re_search* or re_match* could cause memory leaks when C-g is used in
 311    Emacs; also, malloc is slower and causes storage fragmentation.  On
 312    the other hand, malloc is more portable, and easier to debug.
 313
 314    Because we sometimes use alloca, some routines have to be macros,
 315    not functions -- `alloca'-allocated space disappears at the end of the
 316    function it is called in.  */
 317
 318 # ifdef REGEX_MALLOC
 319
 320 #  define REGEX_ALLOCATE malloc
 321 #  define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
 322 #  define REGEX_FREE free
 323
 324 # else /* not REGEX_MALLOC  */
 325
 326 /* Emacs already defines alloca, sometimes.  */
 327 #  ifndef alloca
 328
 329 /* Make alloca work the best possible way.  */
 330 #   ifdef __GNUC__
 331 #    define alloca __builtin_alloca
 332 #   else /* not __GNUC__ */
 333 #    if HAVE_ALLOCA_H
 334 #     include <alloca.h>
 335 #    endif /* HAVE_ALLOCA_H */
 336 #   endif /* not __GNUC__ */
 337
 338 #  endif /* not alloca */
 339
 340 #  define REGEX_ALLOCATE alloca
 341
 342 /* Assumes a `char *destination' variable.  */
 343 #  define REGEX_REALLOCATE(source, osize, nsize)                        \
 344   (destination = (char *) alloca (nsize),                               \
 345    memcpy (destination, source, osize))
 346
 347 /* No need to do anything to free, after alloca.  */
 348 #  define REGEX_FREE(arg) ((void)0) /* Do nothing!  But inhibit gcc warning.  */
 349
 350 # endif /* not REGEX_MALLOC */
 351
 352 /* Define how to allocate the failure stack.  */
 353
 354 # if defined REL_ALLOC && defined REGEX_MALLOC
 355
 356 #  define REGEX_ALLOCATE_STACK(size)                            \
 357   r_alloc (&failure_stack_ptr, (size))
 358 #  define REGEX_REALLOCATE_STACK(source, osize, nsize)          \
 359   r_re_alloc (&failure_stack_ptr, (nsize))
 360 #  define REGEX_FREE_STACK(ptr)                                 \
 361   r_alloc_free (&failure_stack_ptr)
 362
 363 # else /* not using relocating allocator */
 364
 365 #  ifdef REGEX_MALLOC
 366
 367 #   define REGEX_ALLOCATE_STACK malloc
 368 #   define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
 369 #   define REGEX_FREE_STACK free
 370
 371 #  else /* not REGEX_MALLOC */
 372
 373 #   define REGEX_ALLOCATE_STACK alloca
 374
 375 #   define REGEX_REALLOCATE_STACK(source, osize, nsize)                 \
 376    REGEX_REALLOCATE (source, osize, nsize)
 377 /* No need to explicitly free anything.  */
 378 #   define REGEX_FREE_STACK(arg)
 379
 380 #  endif /* not REGEX_MALLOC */
 381 # endif /* not using relocating allocator */
 382
 383
 384 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
 385    `string1' or just past its end.  This works if PTR is NULL, which is
 386    a good thing.  */
 387 # define FIRST_STRING_P(ptr)                                    \
 388   (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
 389
 390 /* (Re)Allocate N items of type T using malloc, or fail.  */
 391 # define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
 392 # define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
 393 # define RETALLOC_IF(addr, n, t) \
 394   if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
 395 # define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
 396
 397 # define BYTEWIDTH 8 /* In bits.  */
 398
 399 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
 400
 401 # undef MAX
 402 # undef MIN
 403 # define MAX(a, b) ((a) > (b) ? (a) : (b))
 404 # define MIN(a, b) ((a) < (b) ? (a) : (b))
 405
 406 typedef char boolean;
 407 # define false 0
 408 # define true 1
 409
 410 static reg_errcode_t byte_regex_compile _RE_ARGS ((const char *pattern, size_t size,
 411                                                    reg_syntax_t syntax,
 412                                                    struct re_pattern_buffer *bufp));
 413 static reg_errcode_t wcs_regex_compile _RE_ARGS ((const char *pattern, size_t size,
 414                                                    reg_syntax_t syntax,
 415                                                    struct re_pattern_buffer *bufp));
 416
 417 static int byte_re_match_2_internal PARAMS ((struct re_pattern_buffer *bufp,
 418                                              const char *string1, int size1,
 419                                              const char *string2, int size2,
 420                                              int pos,
 421                                              struct re_registers *regs,
 422                                              int stop));
 423 static int wcs_re_match_2_internal PARAMS ((struct re_pattern_buffer *bufp,
 424                                             const char *cstring1, int csize1,
 425                                             const char *cstring2, int csize2,
 426                                             int pos,
 427                                             struct re_registers *regs,
 428                                             int stop,
 429                                             wchar_t *string1, int size1,
 430                                             wchar_t *string2, int size2,
 431                                             int *mbs_offset1, int *mbs_offset2));
 432 static int byte_re_search_2 PARAMS ((struct re_pattern_buffer *bufp,
 433                                      const char *string1, int size1,
 434                                      const char *string2, int size2,
 435                                      int startpos, int range,
 436                                      struct re_registers *regs, int stop));
 437 static int wcs_re_search_2 PARAMS ((struct re_pattern_buffer *bufp,
 438                                     const char *string1, int size1,
 439                                     const char *string2, int size2,
 440                                     int startpos, int range,
 441                                     struct re_registers *regs, int stop));
 442 static int byte_re_compile_fastmap PARAMS ((struct re_pattern_buffer *bufp));
 443 static int wcs_re_compile_fastmap PARAMS ((struct re_pattern_buffer *bufp));
 444
 445 \f
 446 /* These are the command codes that appear in compiled regular
 447    expressions.  Some opcodes are followed by argument bytes.  A
 448    command code can specify any interpretation whatsoever for its
 449    arguments.  Zero bytes may appear in the compiled regular expression.  */
 450
 451 typedef enum
 452 {
 453   no_op = 0,
 454
 455   /* Succeed right away--no more backtracking.  */
 456   succeed,
 457
 458         /* Followed by one byte giving n, then by n literal bytes.  */
 459   exactn,
 460
 461 # ifdef MBS_SUPPORT
 462         /* Same as exactn, but contains binary data.  */
 463   exactn_bin,
 464 # endif
 465
 466         /* Matches any (more or less) character.  */
 467   anychar,
 468
 469         /* Matches any one char belonging to specified set.  First
 470            following byte is number of bitmap bytes.  Then come bytes
 471            for a bitmap saying which chars are in.  Bits in each byte
 472            are ordered low-bit-first.  A character is in the set if its
 473            bit is 1.  A character too large to have a bit in the map is
 474            automatically not in the set.  */
 475         /* ifdef MBS_SUPPORT, following element is length of character
 476            classes, length of collating symbols, length of equivalence
 477            classes, length of character ranges, and length of characters.
 478            Next, character class element, collating symbols elements,
 479            equivalence class elements, range elements, and character
 480            elements follow.
 481            See regex_compile function.  */
 482   charset,
 483
 484         /* Same parameters as charset, but match any character that is
 485            not one of those specified.  */
 486   charset_not,
 487
 488         /* Start remembering the text that is matched, for storing in a
 489            register.  Followed by one byte with the register number, in
 490            the range 0 to one less than the pattern buffer's re_nsub
 491            field.  Then followed by one byte with the number of groups
 492            inner to this one.  (This last has to be part of the
 493            start_memory only because we need it in the on_failure_jump
 494            of re_match_2.)  */
 495   start_memory,
 496
 497         /* Stop remembering the text that is matched and store it in a
 498            memory register.  Followed by one byte with the register
 499            number, in the range 0 to one less than `re_nsub' in the
 500            pattern buffer, and one byte with the number of inner groups,
 501            just like `start_memory'.  (We need the number of inner
 502            groups here because we don't have any easy way of finding the
 503            corresponding start_memory when we're at a stop_memory.)  */
 504   stop_memory,
 505
 506         /* Match a duplicate of something remembered. Followed by one
 507            byte containing the register number.  */
 508   duplicate,
 509
 510         /* Fail unless at beginning of line.  */
 511   begline,
 512
 513         /* Fail unless at end of line.  */
 514   endline,
 515
 516         /* Succeeds if at beginning of buffer (if emacs) or at beginning
 517            of string to be matched (if not).  */
 518   begbuf,
 519
 520         /* Analogously, for end of buffer/string.  */
 521   endbuf,
 522
 523         /* Followed by two byte relative address to which to jump.  */
 524   jump,
 525
 526         /* Same as jump, but marks the end of an alternative.  */
 527   jump_past_alt,
 528
 529         /* Followed by two-byte relative address of place to resume at
 530            in case of failure.  */
 531         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 532   on_failure_jump,
 533
 534         /* Like on_failure_jump, but pushes a placeholder instead of the
 535            current string position when executed.  */
 536   on_failure_keep_string_jump,
 537
 538         /* Throw away latest failure point and then jump to following
 539            two-byte relative address.  */
 540         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 541   pop_failure_jump,
 542
 543         /* Change to pop_failure_jump if know won't have to backtrack to
 544            match; otherwise change to jump.  This is used to jump
 545            back to the beginning of a repeat.  If what follows this jump
 546            clearly won't match what the repeat does, such that we can be
 547            sure that there is no use backtracking out of repetitions
 548            already matched, then we change it to a pop_failure_jump.
 549            Followed by two-byte address.  */
 550         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 551   maybe_pop_jump,
 552
 553         /* Jump to following two-byte address, and push a dummy failure
 554            point. This failure point will be thrown away if an attempt
 555            is made to use it for a failure.  A `+' construct makes this
 556            before the first repeat.  Also used as an intermediary kind
 557            of jump when compiling an alternative.  */
 558         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 559   dummy_failure_jump,
 560
 561         /* Push a dummy failure point and continue.  Used at the end of
 562            alternatives.  */
 563   push_dummy_failure,
 564
 565         /* Followed by two-byte relative address and two-byte number n.
 566            After matching N times, jump to the address upon failure.  */
 567         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 568   succeed_n,
 569
 570         /* Followed by two-byte relative address, and two-byte number n.
 571            Jump to the address N times, then fail.  */
 572         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 573   jump_n,
 574
 575         /* Set the following two-byte relative address to the
 576            subsequent two-byte number.  The address *includes* the two
 577            bytes of number.  */
 578         /* ifdef MBS_SUPPORT, the size of address is 1.  */
 579   set_number_at,
 580
 581   wordchar,     /* Matches any word-constituent character.  */
 582   notwordchar,  /* Matches any char that is not a word-constituent.  */
 583
 584   wordbeg,      /* Succeeds if at word beginning.  */
 585   wordend,      /* Succeeds if at word end.  */
 586
 587   wordbound,    /* Succeeds if at a word boundary.  */
 588   notwordbound  /* Succeeds if not at a word boundary.  */
 589
 590 # ifdef emacs
 591   ,before_dot,  /* Succeeds if before point.  */
 592   at_dot,       /* Succeeds if at point.  */
 593   after_dot,    /* Succeeds if after point.  */
 594
 595         /* Matches any character whose syntax is specified.  Followed by
 596            a byte which contains a syntax code, e.g., Sword.  */
 597   syntaxspec,
 598
 599         /* Matches any character whose syntax is not that specified.  */
 600   notsyntaxspec
 601 # endif /* emacs */
 602 } re_opcode_t;
 603 #endif /* not INSIDE_RECURSION */
 604 \f
 605
 606 #ifdef BYTE
 607 # define CHAR_T char
 608 # define UCHAR_T unsigned char
 609 # define COMPILED_BUFFER_VAR bufp->buffer
 610 # define OFFSET_ADDRESS_SIZE 2
 611 # define PREFIX(name) byte_##name
 612 # define ARG_PREFIX(name) name
 613 # define PUT_CHAR(c) putchar (c)
 614 #elif defined WCHAR
 615 # define CHAR_T wchar_t
 616 # define UCHAR_T wchar_t
 617 # define COMPILED_BUFFER_VAR wc_buffer
 618 # define OFFSET_ADDRESS_SIZE 1 /* the size which STORE_NUMBER macro use */
 619 # define CHAR_CLASS_SIZE ((__alignof__(wctype_t)+sizeof(wctype_t))/sizeof(CHAR_T)+1)
 620 # define PREFIX(name) wcs_##name
 621 # define ARG_PREFIX(name) c##name
 622 /* Should we use wide stream??  */
 623 # define PUT_CHAR(c) printf ("%C", c);
 624 # define TRUE 1
 625 # define FALSE 0
 626 #else
 627 # ifdef MBS_SUPPORT
 628 #  define WCHAR
 629 #  define INSIDE_RECURSION
 630 #  include "regex.c"
 631 #  undef INSIDE_RECURSION
 632 # endif
 633 # define BYTE
 634 # define INSIDE_RECURSION
 635 # include "regex.c"
 636 # undef INSIDE_RECURSION
 637 #endif
 638
 639 #ifdef INSIDE_RECURSION
 640 /* Common operations on the compiled pattern.  */
 641
 642 /* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
 643 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element.  */
 644
 645 # ifdef WCHAR
 646 #  define STORE_NUMBER(destination, number)                             \
 647   do {                                                                  \
 648     *(destination) = (UCHAR_T)(number);                         \
 649   } while (0)
 650 # else /* BYTE */
 651 #  define STORE_NUMBER(destination, number)                             \
 652   do {                                                                  \
 653     (destination)[0] = (number) & 0377;                                 \
 654     (destination)[1] = (number) >> 8;                                   \
 655   } while (0)
 656 # endif /* WCHAR */
 657
 658 /* Same as STORE_NUMBER, except increment DESTINATION to
 659    the byte after where the number is stored.  Therefore, DESTINATION
 660    must be an lvalue.  */
 661 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element.  */
 662
 663 # define STORE_NUMBER_AND_INCR(destination, number)                     \
 664   do {                                                                  \
 665     STORE_NUMBER (destination, number);                                 \
 666     (destination) += OFFSET_ADDRESS_SIZE;                               \
 667   } while (0)
 668
 669 /* Put into DESTINATION a number stored in two contiguous bytes starting
 670    at SOURCE.  */
 671 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element.  */
 672
 673 # ifdef WCHAR
 674 #  define EXTRACT_NUMBER(destination, source)                           \
 675   do {                                                                  \
 676     (destination) = *(source);                                          \
 677   } while (0)
 678 # else /* BYTE */
 679 #  define EXTRACT_NUMBER(destination, source)                           \
 680   do {                                                                  \
 681     (destination) = *(source) & 0377;                                   \
 682     (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;           \
 683   } while (0)
 684 # endif
 685
 686 # ifdef DEBUG
 687 static void PREFIX(extract_number) _RE_ARGS ((int *dest, UCHAR_T *source));
 688 static void
 689 PREFIX(extract_number) (dest, source)
 690     int *dest;
 691     UCHAR_T *source;
 692 {
 693 #  ifdef WCHAR
 694   *dest = *source;
 695 #  else /* BYTE */
 696   int temp = SIGN_EXTEND_CHAR (*(source + 1));
 697   *dest = *source & 0377;
 698   *dest += temp << 8;
 699 #  endif
 700 }
 701
 702 #  ifndef EXTRACT_MACROS /* To debug the macros.  */
 703 #   undef EXTRACT_NUMBER
 704 #   define EXTRACT_NUMBER(dest, src) PREFIX(extract_number) (&dest, src)
 705 #  endif /* not EXTRACT_MACROS */
 706
 707 # endif /* DEBUG */
 708
 709 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
 710    SOURCE must be an lvalue.  */
 711
 712 # define EXTRACT_NUMBER_AND_INCR(destination, source)                   \
 713   do {                                                                  \
 714     EXTRACT_NUMBER (destination, source);                               \
 715     (source) += OFFSET_ADDRESS_SIZE;                                    \
 716   } while (0)
 717
 718 # ifdef DEBUG
 719 static void PREFIX(extract_number_and_incr) _RE_ARGS ((int *destination,
 720                                                        UCHAR_T **source));
 721 static void
 722 PREFIX(extract_number_and_incr) (destination, source)
 723     int *destination;
 724     UCHAR_T **source;
 725 {
 726   PREFIX(extract_number) (destination, *source);
 727   *source += OFFSET_ADDRESS_SIZE;
 728 }
 729
 730 #  ifndef EXTRACT_MACROS
 731 #   undef EXTRACT_NUMBER_AND_INCR
 732 #   define EXTRACT_NUMBER_AND_INCR(dest, src) \
 733   PREFIX(extract_number_and_incr) (&dest, &src)
 734 #  endif /* not EXTRACT_MACROS */
 735
 736 # endif /* DEBUG */
 737
 738 \f
 739
 740 /* If DEBUG is defined, Regex prints many voluminous messages about what
 741    it is doing (if the variable `debug' is nonzero).  If linked with the
 742    main program in `iregex.c', you can enter patterns and strings
 743    interactively.  And if linked with the main program in `main.c' and
 744    the other test files, you can run the already-written tests.  */
 745
 746 # ifdef DEBUG
 747
 748 #  ifndef DEFINED_ONCE
 749
 750 /* We use standard I/O for debugging.  */
 751 #   include <stdio.h>
 752
 753 /* It is useful to test things that ``must'' be true when debugging.  */
 754 #   include <assert.h>
 755
 756 static int debug;
 757
 758 #   define DEBUG_STATEMENT(e) e
 759 #   define DEBUG_PRINT1(x) if (debug) printf (x)
 760 #   define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
 761 #   define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
 762 #   define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
 763 #  endif /* not DEFINED_ONCE */
 764
 765 #  define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)                         \
 766   if (debug) PREFIX(print_partial_compiled_pattern) (s, e)
 767 #  define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)                \
 768   if (debug) PREFIX(print_double_string) (w, s1, sz1, s2, sz2)
 769
 770
 771 /* Print the fastmap in human-readable form.  */
 772
 773 #  ifndef DEFINED_ONCE
 774 void
 775 print_fastmap (fastmap)
 776     char *fastmap;
 777 {
 778   unsigned was_a_range = 0;
 779   unsigned i = 0;
 780
 781   while (i < (1 << BYTEWIDTH))
 782     {
 783       if (fastmap[i++])
 784         {
 785           was_a_range = 0;
 786           putchar (i - 1);
 787           while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
 788             {
 789               was_a_range = 1;
 790               i++;
 791             }
 792           if (was_a_range)
 793             {
 794               printf ("-");
 795               putchar (i - 1);
 796             }
 797         }
 798     }
 799   putchar ('\n');
 800 }
 801 #  endif /* not DEFINED_ONCE */
 802
 803
 804 /* Print a compiled pattern string in human-readable form, starting at
 805    the START pointer into it and ending just before the pointer END.  */
 806
 807 void
 808 PREFIX(print_partial_compiled_pattern) (start, end)
 809     UCHAR_T *start;
 810     UCHAR_T *end;
 811 {
 812   int mcnt, mcnt2;
 813   UCHAR_T *p1;
 814   UCHAR_T *p = start;
 815   UCHAR_T *pend = end;
 816
 817   if (start == NULL)
 818     {
 819       printf ("(null)\n");
 820       return;
 821     }
 822
 823   /* Loop over pattern commands.  */
 824   while (p < pend)
 825     {
 826 #  ifdef _LIBC
 827       printf ("%td:\t", p - start);
 828 #  else
 829       printf ("%ld:\t", (long int) (p - start));
 830 #  endif
 831
 832       switch ((re_opcode_t) *p++)
 833         {
 834         case no_op:
 835           printf ("/no_op");
 836           break;
 837
 838         case exactn:
 839           mcnt = *p++;
 840           printf ("/exactn/%d", mcnt);
 841           do
 842             {
 843               putchar ('/');
 844               PUT_CHAR (*p++);
 845             }
 846           while (--mcnt);
 847           break;
 848
 849 #  ifdef MBS_SUPPORT
 850         case exactn_bin:
 851           mcnt = *p++;
 852           printf ("/exactn_bin/%d", mcnt);
 853           do
 854             {
 855               printf("/%lx", (long int) *p++);
 856             }
 857           while (--mcnt);
 858           break;
 859 #  endif /* MBS_SUPPORT */
 860
 861         case start_memory:
 862           mcnt = *p++;
 863           printf ("/start_memory/%d/%ld", mcnt, (long int) *p++);
 864           break;
 865
 866         case stop_memory:
 867           mcnt = *p++;
 868           printf ("/stop_memory/%d/%ld", mcnt, (long int) *p++);
 869           break;
 870
 871         case duplicate:
 872           printf ("/duplicate/%ld", (long int) *p++);
 873           break;
 874
 875         case anychar:
 876           printf ("/anychar");
 877           break;
 878
 879         case charset:
 880         case charset_not:
 881           {
 882 #  ifdef WCHAR
 883             int i, length;
 884             wchar_t *workp = p;
 885             printf ("/charset [%s",
 886                     (re_opcode_t) *(workp - 1) == charset_not ? "^" : "");
 887             p += 5;
 888             length = *workp++; /* the length of char_classes */
 889             for (i=0 ; i<length ; i++)
 890               printf("[:%lx:]", (long int) *p++);
 891             length = *workp++; /* the length of collating_symbol */
 892             for (i=0 ; i<length ;)
 893               {
 894                 printf("[.");
 895                 while(*p != 0)
 896                   PUT_CHAR((i++,*p++));
 897                 i++,p++;
 898                 printf(".]");
 899               }
 900             length = *workp++; /* the length of equivalence_class */
 901             for (i=0 ; i<length ;)
 902               {
 903                 printf("[=");
 904                 while(*p != 0)
 905                   PUT_CHAR((i++,*p++));
 906                 i++,p++;
 907                 printf("=]");
 908               }
 909             length = *workp++; /* the length of char_range */
 910             for (i=0 ; i<length ; i++)
 911               {
 912                 wchar_t range_start = *p++;
 913                 wchar_t range_end = *p++;
 914                 printf("%C-%C", range_start, range_end);
 915               }
 916             length = *workp++; /* the length of char */
 917             for (i=0 ; i<length ; i++)
 918               printf("%C", *p++);
 919             putchar (']');
 920 #  else
 921             register int c, last = -100;
 922             register int in_range = 0;
 923
 924             printf ("/charset [%s",
 925                     (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
 926
 927             assert (p + *p < pend);
 928
 929             for (c = 0; c < 256; c++)
 930               if (c / 8 < *p
 931                   && (p[1 + (c/8)] & (1 << (c % 8))))
 932                 {
 933                   /* Are we starting a range?  */
 934                   if (last + 1 == c && ! in_range)
 935                     {
 936                       putchar ('-');
 937                       in_range = 1;
 938                     }
 939                   /* Have we broken a range?  */
 940                   else if (last + 1 != c && in_range)
 941               {
 942                       putchar (last);
 943                       in_range = 0;
 944                     }
 945
 946                   if (! in_range)
 947                     putchar (c);
 948
 949                   last = c;
 950               }
 951
 952             if (in_range)
 953               putchar (last);
 954
 955             putchar (']');
 956
 957             p += 1 + *p;
 958 #  endif /* WCHAR */
 959           }
 960           break;
 961
 962         case begline:
 963           printf ("/begline");
 964           break;
 965
 966         case endline:
 967           printf ("/endline");
 968           break;
 969
 970         case on_failure_jump:
 971           PREFIX(extract_number_and_incr) (&mcnt, &p);
 972 #  ifdef _LIBC
 973           printf ("/on_failure_jump to %td", p + mcnt - start);
 974 #  else
 975           printf ("/on_failure_jump to %ld", (long int) (p + mcnt - start));
 976 #  endif
 977           break;
 978
 979         case on_failure_keep_string_jump:
 980           PREFIX(extract_number_and_incr) (&mcnt, &p);
 981 #  ifdef _LIBC
 982           printf ("/on_failure_keep_string_jump to %td", p + mcnt - start);
 983 #  else
 984           printf ("/on_failure_keep_string_jump to %ld",
 985                   (long int) (p + mcnt - start));
 986 #  endif
 987           break;
 988
 989         case dummy_failure_jump:
 990           PREFIX(extract_number_and_incr) (&mcnt, &p);
 991 #  ifdef _LIBC
 992           printf ("/dummy_failure_jump to %td", p + mcnt - start);
 993 #  else
 994           printf ("/dummy_failure_jump to %ld", (long int) (p + mcnt - start));
 995 #  endif
 996           break;
 997
 998         case push_dummy_failure:
 999           printf ("/push_dummy_failure");
1000           break;
1001
1002         case maybe_pop_jump:
1003           PREFIX(extract_number_and_incr) (&mcnt, &p);
1004 #  ifdef _LIBC
1005           printf ("/maybe_pop_jump to %td", p + mcnt - start);
1006 #  else
1007           printf ("/maybe_pop_jump to %ld", (long int) (p + mcnt - start));
1008 #  endif
1009           break;
1010
1011         case pop_failure_jump:
1012           PREFIX(extract_number_and_incr) (&mcnt, &p);
1013 #  ifdef _LIBC
1014           printf ("/pop_failure_jump to %td", p + mcnt - start);
1015 #  else
1016           printf ("/pop_failure_jump to %ld", (long int) (p + mcnt - start));
1017 #  endif
1018           break;
1019
1020         case jump_past_alt:
1021           PREFIX(extract_number_and_incr) (&mcnt, &p);
1022 #  ifdef _LIBC
1023           printf ("/jump_past_alt to %td", p + mcnt - start);
1024 #  else
1025           printf ("/jump_past_alt to %ld", (long int) (p + mcnt - start));
1026 #  endif
1027           break;
1028
1029         case jump:
1030           PREFIX(extract_number_and_incr) (&mcnt, &p);
1031 #  ifdef _LIBC
1032           printf ("/jump to %td", p + mcnt - start);
1033 #  else
1034           printf ("/jump to %ld", (long int) (p + mcnt - start));
1035 #  endif
1036           break;
1037
1038         case succeed_n:
1039           PREFIX(extract_number_and_incr) (&mcnt, &p);
1040           p1 = p + mcnt;
1041           PREFIX(extract_number_and_incr) (&mcnt2, &p);
1042 #  ifdef _LIBC
1043           printf ("/succeed_n to %td, %d times", p1 - start, mcnt2);
1044 #  else
1045           printf ("/succeed_n to %ld, %d times",
1046                   (long int) (p1 - start), mcnt2);
1047 #  endif
1048           break;
1049
1050         case jump_n:
1051           PREFIX(extract_number_and_incr) (&mcnt, &p);
1052           p1 = p + mcnt;
1053           PREFIX(extract_number_and_incr) (&mcnt2, &p);
1054           printf ("/jump_n to %d, %d times", p1 - start, mcnt2);
1055           break;
1056
1057         case set_number_at:
1058           PREFIX(extract_number_and_incr) (&mcnt, &p);
1059           p1 = p + mcnt;
1060           PREFIX(extract_number_and_incr) (&mcnt2, &p);
1061 #  ifdef _LIBC
1062           printf ("/set_number_at location %td to %d", p1 - start, mcnt2);
1063 #  else
1064           printf ("/set_number_at location %ld to %d",
1065                   (long int) (p1 - start), mcnt2);
1066 #  endif
1067           break;
1068
1069         case wordbound:
1070           printf ("/wordbound");
1071           break;
1072
1073         case notwordbound:
1074           printf ("/notwordbound");
1075           break;
1076
1077         case wordbeg:
1078           printf ("/wordbeg");
1079           break;
1080
1081         case wordend:
1082           printf ("/wordend");
1083           break;
1084
1085 #  ifdef emacs
1086         case before_dot:
1087           printf ("/before_dot");
1088           break;
1089
1090         case at_dot:
1091           printf ("/at_dot");
1092           break;
1093
1094         case after_dot:
1095           printf ("/after_dot");
1096           break;
1097
1098         case syntaxspec:
1099           printf ("/syntaxspec");
1100           mcnt = *p++;
1101           printf ("/%d", mcnt);
1102           break;
1103
1104         case notsyntaxspec:
1105           printf ("/notsyntaxspec");
1106           mcnt = *p++;
1107           printf ("/%d", mcnt);
1108           break;
1109 #  endif /* emacs */
1110
1111         case wordchar:
1112           printf ("/wordchar");
1113           break;
1114
1115         case notwordchar:
1116           printf ("/notwordchar");
1117           break;
1118
1119         case begbuf:
1120           printf ("/begbuf");
1121           break;
1122
1123         case endbuf:
1124           printf ("/endbuf");
1125           break;
1126
1127         default:
1128           printf ("?%ld", (long int) *(p-1));
1129         }
1130
1131       putchar ('\n');
1132     }
1133
1134 #  ifdef _LIBC
1135   printf ("%td:\tend of pattern.\n", p - start);
1136 #  else
1137   printf ("%ld:\tend of pattern.\n", (long int) (p - start));
1138 #  endif
1139 }
1140
1141
1142 void
1143 PREFIX(print_compiled_pattern) (bufp)
1144     struct re_pattern_buffer *bufp;
1145 {
1146   UCHAR_T *buffer = (UCHAR_T*) bufp->buffer;
1147
1148   PREFIX(print_partial_compiled_pattern) (buffer, buffer
1149                                   + bufp->used / sizeof(UCHAR_T));
1150   printf ("%ld bytes used/%ld bytes allocated.\n",
1151           bufp->used, bufp->allocated);
1152
1153   if (bufp->fastmap_accurate && bufp->fastmap)
1154     {
1155       printf ("fastmap: ");
1156       print_fastmap (bufp->fastmap);
1157     }
1158
1159 #  ifdef _LIBC
1160   printf ("re_nsub: %Zd\t", bufp->re_nsub);
1161 #  else
1162   printf ("re_nsub: %ld\t", (long int) bufp->re_nsub);
1163 #  endif
1164   printf ("regs_alloc: %d\t", bufp->regs_allocated);
1165   printf ("can_be_null: %d\t", bufp->can_be_null);
1166   printf ("newline_anchor: %d\n", bufp->newline_anchor);
1167   printf ("no_sub: %d\t", bufp->no_sub);
1168   printf ("not_bol: %d\t", bufp->not_bol);
1169   printf ("not_eol: %d\t", bufp->not_eol);
1170   printf ("syntax: %lx\n", bufp->syntax);
1171   /* Perhaps we should print the translate table?  */
1172 }
1173
1174
1175 void
1176 PREFIX(print_double_string) (where, string1, size1, string2, size2)
1177     const CHAR_T *where;
1178     const CHAR_T *string1;
1179     const CHAR_T *string2;
1180     int size1;
1181     int size2;
1182 {
1183   int this_char;
1184
1185   if (where == NULL)
1186     printf ("(null)");
1187   else
1188     {
1189       int cnt;
1190
1191       if (FIRST_STRING_P (where))
1192         {
1193           for (this_char = where - string1; this_char < size1; this_char++)
1194             PUT_CHAR (string1[this_char]);
1195
1196           where = string2;
1197         }
1198
1199       cnt = 0;
1200       for (this_char = where - string2; this_char < size2; this_char++)
1201         {
1202           PUT_CHAR (string2[this_char]);
1203           if (++cnt > 100)
1204             {
1205               fputs ("...", stdout);
1206               break;
1207             }
1208         }
1209     }
1210 }
1211
1212 #  ifndef DEFINED_ONCE
1213 void
1214 printchar (c)
1215      int c;
1216 {
1217   putc (c, stderr);
1218 }
1219 #  endif
1220
1221 # else /* not DEBUG */
1222
1223 #  ifndef DEFINED_ONCE
1224 #   undef assert
1225 #   define assert(e)
1226
1227 #   define DEBUG_STATEMENT(e)
1228 #   define DEBUG_PRINT1(x)
1229 #   define DEBUG_PRINT2(x1, x2)
1230 #   define DEBUG_PRINT3(x1, x2, x3)
1231 #   define DEBUG_PRINT4(x1, x2, x3, x4)
1232 #  endif /* not DEFINED_ONCE */
1233 #  define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1234 #  define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1235
1236 # endif /* not DEBUG */
1237
1238 \f
1239
1240 # ifdef WCHAR
1241 /* This  convert a multibyte string to a wide character string.
1242    And write their correspondances to offset_buffer(see below)
1243    and write whether each wchar_t is binary data to is_binary.
1244    This assume invalid multibyte sequences as binary data.
1245    We assume offset_buffer and is_binary is already allocated
1246    enough space.  */
1247
1248 static size_t convert_mbs_to_wcs (CHAR_T *dest, const unsigned char* src,
1249                                   size_t len, int *offset_buffer,
1250                                   char *is_binary);
1251 static size_t
1252 convert_mbs_to_wcs (dest, src, len, offset_buffer, is_binary)
1253      CHAR_T *dest;
1254      const unsigned char* src;
1255      size_t len; /* the length of multibyte string.  */
1256
1257      /* It hold correspondances between src(char string) and
1258         dest(wchar_t string) for optimization.
1259         e.g. src  = "xxxyzz"
1260              dest = {'X', 'Y', 'Z'}
1261               (each "xxx", "y" and "zz" represent one multibyte character
1262                corresponding to 'X', 'Y' and 'Z'.)
1263           offset_buffer = {0, 0+3("xxx"), 0+3+1("y"), 0+3+1+2("zz")}
1264                         = {0, 3, 4, 6}
1265      */
1266      int *offset_buffer;
1267      char *is_binary;
1268 {
1269   wchar_t *pdest = dest;
1270   const unsigned char *psrc = src;
1271   size_t wc_count = 0;
1272
1273   mbstate_t mbs;
1274   int i, consumed;
1275   size_t mb_remain = len;
1276   size_t mb_count = 0;
1277
1278   /* Initialize the conversion state.  */
1279   memset (&mbs, 0, sizeof (mbstate_t));
1280
1281   offset_buffer[0] = 0;
1282   for( ; mb_remain > 0 ; ++wc_count, ++pdest, mb_remain -= consumed,
1283          psrc += consumed)
1284     {
1285       consumed = mbrtowc (pdest, psrc, mb_remain, &mbs);
1286
1287       if (consumed <= 0)
1288         /* failed to convert. maybe src contains binary data.
1289            So we consume 1 byte manualy.  */
1290         {
1291           *pdest = *psrc;
1292           consumed = 1;
1293           is_binary[wc_count] = TRUE;
1294         }
1295       else
1296         is_binary[wc_count] = FALSE;
1297       /* In sjis encoding, we use yen sign as escape character in
1298          place of reverse solidus. So we convert 0x5c(yen sign in
1299          sjis) to not 0xa5(yen sign in UCS2) but 0x5c(reverse
1300          solidus in UCS2).  */
1301       if (consumed == 1 && (int) *psrc == 0x5c && (int) *pdest == 0xa5)
1302         *pdest = (wchar_t) *psrc;
1303
1304       offset_buffer[wc_count + 1] = mb_count += consumed;
1305     }
1306
1307   /* Fill remain of the buffer with sentinel.  */
1308   for (i = wc_count + 1 ; i <= len ; i++)
1309     offset_buffer[i] = mb_count + 1;
1310
1311   return wc_count;
1312 }
1313
1314 # endif /* WCHAR */
1315
1316 #else /* not INSIDE_RECURSION */
1317
1318 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
1319    also be assigned to arbitrarily: each pattern buffer stores its own
1320    syntax, so it can be changed between regex compilations.  */
1321 /* This has no initializer because initialized variables in Emacs
1322    become read-only after dumping.  */
1323 reg_syntax_t re_syntax_options;
1324
1325
1326 /* Specify the precise syntax of regexps for compilation.  This provides
1327    for compatibility for various utilities which historically have
1328    different, incompatible syntaxes.
1329
1330    The argument SYNTAX is a bit mask comprised of the various bits
1331    defined in regex.h.  We return the old syntax.  */
1332
1333 reg_syntax_t
1334 re_set_syntax (syntax)
1335     reg_syntax_t syntax;
1336 {
1337   reg_syntax_t ret = re_syntax_options;
1338
1339   re_syntax_options = syntax;
1340 # ifdef DEBUG
1341   if (syntax & RE_DEBUG)
1342     debug = 1;
1343   else if (debug) /* was on but now is not */
1344     debug = 0;
1345 # endif /* DEBUG */
1346   return ret;
1347 }
1348 # ifdef _LIBC
1349 weak_alias (__re_set_syntax, re_set_syntax)
1350 # endif
1351 \f
1352 /* This table gives an error message for each of the error codes listed
1353    in regex.h.  Obviously the order here has to be same as there.
1354    POSIX doesn't require that we do anything for REG_NOERROR,
1355    but why not be nice?  */
1356
1357 static const char re_error_msgid[] =
1358   {
1359 # define REG_NOERROR_IDX        0
1360     gettext_noop ("Success")    /* REG_NOERROR */
1361     "\0"
1362 # define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
1363     gettext_noop ("No match")   /* REG_NOMATCH */
1364     "\0"
1365 # define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
1366     gettext_noop ("Invalid regular expression") /* REG_BADPAT */
1367     "\0"
1368 # define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
1369     gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
1370     "\0"
1371 # define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
1372     gettext_noop ("Invalid character class name") /* REG_ECTYPE */
1373     "\0"
1374 # define REG_EESCAPE_IDX        (REG_ECTYPE_IDX + sizeof "Invalid character class name")
1375     gettext_noop ("Trailing backslash") /* REG_EESCAPE */
1376     "\0"
1377 # define REG_ESUBREG_IDX        (REG_EESCAPE_IDX + sizeof "Trailing backslash")
1378     gettext_noop ("Invalid back reference") /* REG_ESUBREG */
1379     "\0"
1380 # define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
1381     gettext_noop ("Unmatched [ or [^")  /* REG_EBRACK */
1382     "\0"
1383 # define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
1384     gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
1385     "\0"
1386 # define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
1387     gettext_noop ("Unmatched \\{") /* REG_EBRACE */
1388     "\0"
1389 # define REG_BADBR_IDX  (REG_EBRACE_IDX + sizeof "Unmatched \\{")
1390     gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
1391     "\0"
1392 # define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
1393     gettext_noop ("Invalid range end")  /* REG_ERANGE */
1394     "\0"
1395 # define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
1396     gettext_noop ("Memory exhausted") /* REG_ESPACE */
1397     "\0"
1398 # define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
1399     gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
1400     "\0"
1401 # define REG_EEND_IDX   (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
1402     gettext_noop ("Premature end of regular expression") /* REG_EEND */
1403     "\0"
1404 # define REG_ESIZE_IDX  (REG_EEND_IDX + sizeof "Premature end of regular expression")
1405     gettext_noop ("Regular expression too big") /* REG_ESIZE */
1406     "\0"
1407 # define REG_ERPAREN_IDX        (REG_ESIZE_IDX + sizeof "Regular expression too big")
1408     gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
1409   };
1410
1411 static const size_t re_error_msgid_idx[] =
1412   {
1413     REG_NOERROR_IDX,
1414     REG_NOMATCH_IDX,
1415     REG_BADPAT_IDX,
1416     REG_ECOLLATE_IDX,
1417     REG_ECTYPE_IDX,
1418     REG_EESCAPE_IDX,
1419     REG_ESUBREG_IDX,
1420     REG_EBRACK_IDX,
1421     REG_EPAREN_IDX,
1422     REG_EBRACE_IDX,
1423     REG_BADBR_IDX,
1424     REG_ERANGE_IDX,
1425     REG_ESPACE_IDX,
1426     REG_BADRPT_IDX,
1427     REG_EEND_IDX,
1428     REG_ESIZE_IDX,
1429     REG_ERPAREN_IDX
1430   };
1431 \f
1432 #endif /* INSIDE_RECURSION */
1433
1434 #ifndef DEFINED_ONCE
1435 /* Avoiding alloca during matching, to placate r_alloc.  */
1436
1437 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1438    searching and matching functions should not call alloca.  On some
1439    systems, alloca is implemented in terms of malloc, and if we're
1440    using the relocating allocator routines, then malloc could cause a
1441    relocation, which might (if the strings being searched are in the
1442    ralloc heap) shift the data out from underneath the regexp
1443    routines.
1444
1445    Here's another reason to avoid allocation: Emacs
1446    processes input from X in a signal handler; processing X input may
1447    call malloc; if input arrives while a matching routine is calling
1448    malloc, then we're scrod.  But Emacs can't just block input while
1449    calling matching routines; then we don't notice interrupts when
1450    they come in.  So, Emacs blocks input around all regexp calls
1451    except the matching calls, which it leaves unprotected, in the
1452    faith that they will not malloc.  */
1453
1454 /* Normally, this is fine.  */
1455 # define MATCH_MAY_ALLOCATE
1456
1457 /* When using GNU C, we are not REALLY using the C alloca, no matter
1458    what config.h may say.  So don't take precautions for it.  */
1459 # ifdef __GNUC__
1460 #  undef C_ALLOCA
1461 # endif
1462
1463 /* The match routines may not allocate if (1) they would do it with malloc
1464    and (2) it's not safe for them to use malloc.
1465    Note that if REL_ALLOC is defined, matching would not use malloc for the
1466    failure stack, but we would still use it for the register vectors;
1467    so REL_ALLOC should not affect this.  */
1468 # if (defined C_ALLOCA || defined REGEX_MALLOC) && defined emacs
1469 #  undef MATCH_MAY_ALLOCATE
1470 # endif
1471 #endif /* not DEFINED_ONCE */
1472 \f
1473 #ifdef INSIDE_RECURSION
1474 /* Failure stack declarations and macros; both re_compile_fastmap and
1475    re_match_2 use a failure stack.  These have to be macros because of
1476    REGEX_ALLOCATE_STACK.  */
1477
1478
1479 /* Number of failure points for which to initially allocate space
1480    when matching.  If this number is exceeded, we allocate more
1481    space, so it is not a hard limit.  */
1482 # ifndef INIT_FAILURE_ALLOC
1483 #  define INIT_FAILURE_ALLOC 5
1484 # endif
1485
1486 /* Roughly the maximum number of failure points on the stack.  Would be
1487    exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1488    This is a variable only so users of regex can assign to it; we never
1489    change it ourselves.  */
1490
1491 # ifdef INT_IS_16BIT
1492
1493 #  ifndef DEFINED_ONCE
1494 #   if defined MATCH_MAY_ALLOCATE
1495 /* 4400 was enough to cause a crash on Alpha OSF/1,
1496    whose default stack limit is 2mb.  */
1497 long int re_max_failures = 4000;
1498 #   else
1499 long int re_max_failures = 2000;
1500 #   endif
1501 #  endif
1502
1503 union PREFIX(fail_stack_elt)
1504 {
1505   UCHAR_T *pointer;
1506   long int integer;
1507 };
1508
1509 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1510
1511 typedef struct
1512 {
1513   PREFIX(fail_stack_elt_t) *stack;
1514   unsigned long int size;
1515   unsigned long int avail;              /* Offset of next open position.  */
1516 } PREFIX(fail_stack_type);
1517
1518 # else /* not INT_IS_16BIT */
1519
1520 #  ifndef DEFINED_ONCE
1521 #   if defined MATCH_MAY_ALLOCATE
1522 /* 4400 was enough to cause a crash on Alpha OSF/1,
1523    whose default stack limit is 2mb.  */
1524 int re_max_failures = 4000;
1525 #   else
1526 int re_max_failures = 2000;
1527 #   endif
1528 #  endif
1529
1530 union PREFIX(fail_stack_elt)
1531 {
1532   UCHAR_T *pointer;
1533   int integer;
1534 };
1535
1536 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1537
1538 typedef struct
1539 {
1540   PREFIX(fail_stack_elt_t) *stack;
1541   unsigned size;
1542   unsigned avail;                       /* Offset of next open position.  */
1543 } PREFIX(fail_stack_type);
1544
1545 # endif /* INT_IS_16BIT */
1546
1547 # ifndef DEFINED_ONCE
1548 #  define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
1549 #  define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1550 #  define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
1551 # endif
1552
1553
1554 /* Define macros to initialize and free the failure stack.
1555    Do `return -2' if the alloc fails.  */
1556
1557 # ifdef MATCH_MAY_ALLOCATE
1558 #  define INIT_FAIL_STACK()                                             \
1559   do {                                                                  \
1560     fail_stack.stack = (PREFIX(fail_stack_elt_t) *)             \
1561       REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (PREFIX(fail_stack_elt_t))); \
1562                                                                         \
1563     if (fail_stack.stack == NULL)                               \
1564       return -2;                                                        \
1565                                                                         \
1566     fail_stack.size = INIT_FAILURE_ALLOC;                       \
1567     fail_stack.avail = 0;                                       \
1568   } while (0)
1569
1570 #  define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
1571 # else
1572 #  define INIT_FAIL_STACK()                                             \
1573   do {                                                                  \
1574     fail_stack.avail = 0;                                       \
1575   } while (0)
1576
1577 #  define RESET_FAIL_STACK()
1578 # endif
1579
1580
1581 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1582
1583    Return 1 if succeeds, and 0 if either ran out of memory
1584    allocating space for it or it was already too large.
1585
1586    REGEX_REALLOCATE_STACK requires `destination' be declared.   */
1587
1588 # define DOUBLE_FAIL_STACK(fail_stack)                                  \
1589   ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1590    ? 0                                                                  \
1591    : ((fail_stack).stack = (PREFIX(fail_stack_elt_t) *)                 \
1592         REGEX_REALLOCATE_STACK ((fail_stack).stack,                     \
1593           (fail_stack).size * sizeof (PREFIX(fail_stack_elt_t)),        \
1594           ((fail_stack).size << 1) * sizeof (PREFIX(fail_stack_elt_t))),\
1595                                                                         \
1596       (fail_stack).stack == NULL                                        \
1597       ? 0                                                               \
1598       : ((fail_stack).size <<= 1,                                       \
1599          1)))
1600
1601
1602 /* Push pointer POINTER on FAIL_STACK.
1603    Return 1 if was able to do so and 0 if ran out of memory allocating
1604    space to do so.  */
1605 # define PUSH_PATTERN_OP(POINTER, FAIL_STACK)                           \
1606   ((FAIL_STACK_FULL ()                                                  \
1607     && !DOUBLE_FAIL_STACK (FAIL_STACK))                                 \
1608    ? 0                                                                  \
1609    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,       \
1610       1))
1611
1612 /* Push a pointer value onto the failure stack.
1613    Assumes the variable `fail_stack'.  Probably should only
1614    be called from within `PUSH_FAILURE_POINT'.  */
1615 # define PUSH_FAILURE_POINTER(item)                                     \
1616   fail_stack.stack[fail_stack.avail++].pointer = (UCHAR_T *) (item)
1617
1618 /* This pushes an integer-valued item onto the failure stack.
1619    Assumes the variable `fail_stack'.  Probably should only
1620    be called from within `PUSH_FAILURE_POINT'.  */
1621 # define PUSH_FAILURE_INT(item)                                 \
1622   fail_stack.stack[fail_stack.avail++].integer = (item)
1623
1624 /* Push a fail_stack_elt_t value onto the failure stack.
1625    Assumes the variable `fail_stack'.  Probably should only
1626    be called from within `PUSH_FAILURE_POINT'.  */
1627 # define PUSH_FAILURE_ELT(item)                                 \
1628   fail_stack.stack[fail_stack.avail++] =  (item)
1629
1630 /* These three POP... operations complement the three PUSH... operations.
1631    All assume that `fail_stack' is nonempty.  */
1632 # define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1633 # define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1634 # define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1635
1636 /* Used to omit pushing failure point id's when we're not debugging.  */
1637 # ifdef DEBUG
1638 #  define DEBUG_PUSH PUSH_FAILURE_INT
1639 #  define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1640 # else
1641 #  define DEBUG_PUSH(item)
1642 #  define DEBUG_POP(item_addr)
1643 # endif
1644
1645
1646 /* Push the information about the state we will need
1647    if we ever fail back to it.
1648
1649    Requires variables fail_stack, regstart, regend, reg_info, and
1650    num_regs_pushed be declared.  DOUBLE_FAIL_STACK requires `destination'
1651    be declared.
1652
1653    Does `return FAILURE_CODE' if runs out of memory.  */
1654
1655 # define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)  \
1656   do {                                                                  \
1657     char *destination;                                                  \
1658     /* Must be int, so when we don't save any registers, the arithmetic \
1659        of 0 + -1 isn't done as unsigned.  */                            \
1660     /* Can't be int, since there is not a shred of a guarantee that int \
1661        is wide enough to hold a value of something to which pointer can \
1662        be assigned */                                                   \
1663     active_reg_t this_reg;                                              \
1664                                                                         \
1665     DEBUG_STATEMENT (failure_id++);                                     \
1666     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
1667     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
1668     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
1669     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
1670                                                                         \
1671     DEBUG_PRINT2 ("  slots needed: %ld\n", NUM_FAILURE_ITEMS);          \
1672     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
1673                                                                         \
1674     /* Ensure we have enough space allocated for what we will push.  */ \
1675     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
1676       {                                                                 \
1677         if (!DOUBLE_FAIL_STACK (fail_stack))                            \
1678           return failure_code;                                          \
1679                                                                         \
1680         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
1681                        (fail_stack).size);                              \
1682         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1683       }                                                                 \
1684                                                                         \
1685     /* Push the info, starting with the registers.  */                  \
1686     DEBUG_PRINT1 ("\n");                                                \
1687                                                                         \
1688     if (1)                                                              \
1689       for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1690            this_reg++)                                                  \
1691         {                                                               \
1692           DEBUG_PRINT2 ("  Pushing reg: %lu\n", this_reg);              \
1693           DEBUG_STATEMENT (num_regs_pushed++);                          \
1694                                                                         \
1695           DEBUG_PRINT2 ("    start: %p\n", regstart[this_reg]);         \
1696           PUSH_FAILURE_POINTER (regstart[this_reg]);                    \
1697                                                                         \
1698           DEBUG_PRINT2 ("    end: %p\n", regend[this_reg]);             \
1699           PUSH_FAILURE_POINTER (regend[this_reg]);                      \
1700                                                                         \
1701           DEBUG_PRINT2 ("    info: %p\n      ",                         \
1702                         reg_info[this_reg].word.pointer);               \
1703           DEBUG_PRINT2 (" match_null=%d",                               \
1704                         REG_MATCH_NULL_STRING_P (reg_info[this_reg]));  \
1705           DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));  \
1706           DEBUG_PRINT2 (" matched_something=%d",                        \
1707                         MATCHED_SOMETHING (reg_info[this_reg]));        \
1708           DEBUG_PRINT2 (" ever_matched=%d",                             \
1709                         EVER_MATCHED_SOMETHING (reg_info[this_reg]));   \
1710           DEBUG_PRINT1 ("\n");                                          \
1711           PUSH_FAILURE_ELT (reg_info[this_reg].word);                   \
1712         }                                                               \
1713                                                                         \
1714     DEBUG_PRINT2 ("  Pushing  low active reg: %ld\n", lowest_active_reg);\
1715     PUSH_FAILURE_INT (lowest_active_reg);                               \
1716                                                                         \
1717     DEBUG_PRINT2 ("  Pushing high active reg: %ld\n", highest_active_reg);\
1718     PUSH_FAILURE_INT (highest_active_reg);                              \
1719                                                                         \
1720     DEBUG_PRINT2 ("  Pushing pattern %p:\n", pattern_place);            \
1721     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
1722     PUSH_FAILURE_POINTER (pattern_place);                               \
1723                                                                         \
1724     DEBUG_PRINT2 ("  Pushing string %p: `", string_place);              \
1725     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
1726                                  size2);                                \
1727     DEBUG_PRINT1 ("'\n");                                               \
1728     PUSH_FAILURE_POINTER (string_place);                                \
1729                                                                         \
1730     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
1731     DEBUG_PUSH (failure_id);                                            \
1732   } while (0)
1733
1734 # ifndef DEFINED_ONCE
1735 /* This is the number of items that are pushed and popped on the stack
1736    for each register.  */
1737 #  define NUM_REG_ITEMS  3
1738
1739 /* Individual items aside from the registers.  */
1740 #  ifdef DEBUG
1741 #   define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
1742 #  else
1743 #   define NUM_NONREG_ITEMS 4
1744 #  endif
1745
1746 /* We push at most this many items on the stack.  */
1747 /* We used to use (num_regs - 1), which is the number of registers
1748    this regexp will save; but that was changed to 5
1749    to avoid stack overflow for a regexp with lots of parens.  */
1750 #  define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1751
1752 /* We actually push this many items.  */
1753 #  define NUM_FAILURE_ITEMS                             \
1754   (((0                                                  \
1755      ? 0 : highest_active_reg - lowest_active_reg + 1)  \
1756     * NUM_REG_ITEMS)                                    \
1757    + NUM_NONREG_ITEMS)
1758
1759 /* How many items can still be added to the stack without overflowing it.  */
1760 #  define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1761 # endif /* not DEFINED_ONCE */
1762
1763
1764 /* Pops what PUSH_FAIL_STACK pushes.
1765
1766    We restore into the parameters, all of which should be lvalues:
1767      STR -- the saved data position.
1768      PAT -- the saved pattern position.
1769      LOW_REG, HIGH_REG -- the highest and lowest active registers.
1770      REGSTART, REGEND -- arrays of string positions.
1771      REG_INFO -- array of information about each subexpression.
1772
1773    Also assumes the variables `fail_stack' and (if debugging), `bufp',
1774    `pend', `string1', `size1', `string2', and `size2'.  */
1775 # define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1776 {                                                                       \
1777   DEBUG_STATEMENT (unsigned failure_id;)                                \
1778   active_reg_t this_reg;                                                \
1779   const UCHAR_T *string_temp;                                           \
1780                                                                         \
1781   assert (!FAIL_STACK_EMPTY ());                                        \
1782                                                                         \
1783   /* Remove failure points and point to how many regs pushed.  */       \
1784   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
1785   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
1786   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
1787                                                                         \
1788   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
1789                                                                         \
1790   DEBUG_POP (&failure_id);                                              \
1791   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
1792                                                                         \
1793   /* If the saved string location is NULL, it came from an              \
1794      on_failure_keep_string_jump opcode, and we want to throw away the  \
1795      saved NULL, thus retaining our current position in the string.  */ \
1796   string_temp = POP_FAILURE_POINTER ();                                 \
1797   if (string_temp != NULL)                                              \
1798     str = (const CHAR_T *) string_temp;                                 \
1799                                                                         \
1800   DEBUG_PRINT2 ("  Popping string %p: `", str);                         \
1801   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
1802   DEBUG_PRINT1 ("'\n");                                                 \
1803                                                                         \
1804   pat = (UCHAR_T *) POP_FAILURE_POINTER ();                             \
1805   DEBUG_PRINT2 ("  Popping pattern %p:\n", pat);                        \
1806   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
1807                                                                         \
1808   /* Restore register info.  */                                         \
1809   high_reg = (active_reg_t) POP_FAILURE_INT ();                         \
1810   DEBUG_PRINT2 ("  Popping high active reg: %ld\n", high_reg);          \
1811                                                                         \
1812   low_reg = (active_reg_t) POP_FAILURE_INT ();                          \
1813   DEBUG_PRINT2 ("  Popping  low active reg: %ld\n", low_reg);           \
1814                                                                         \
1815   if (1)                                                                \
1816     for (this_reg = high_reg; this_reg >= low_reg; this_reg--)          \
1817       {                                                                 \
1818         DEBUG_PRINT2 ("    Popping reg: %ld\n", this_reg);              \
1819                                                                         \
1820         reg_info[this_reg].word = POP_FAILURE_ELT ();                   \
1821         DEBUG_PRINT2 ("      info: %p\n",                               \
1822                       reg_info[this_reg].word.pointer);                 \
1823                                                                         \
1824         regend[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER ();     \
1825         DEBUG_PRINT2 ("      end: %p\n", regend[this_reg]);             \
1826                                                                         \
1827         regstart[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER ();   \
1828         DEBUG_PRINT2 ("      start: %p\n", regstart[this_reg]);         \
1829       }                                                                 \
1830   else                                                                  \
1831     {                                                                   \
1832       for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1833         {                                                               \
1834           reg_info[this_reg].word.integer = 0;                          \
1835           regend[this_reg] = 0;                                         \
1836           regstart[this_reg] = 0;                                       \
1837         }                                                               \
1838       highest_active_reg = high_reg;                                    \
1839     }                                                                   \
1840                                                                         \
1841   set_regs_matched_done = 0;                                            \
1842   DEBUG_STATEMENT (nfailure_points_popped++);                           \
1843 } /* POP_FAILURE_POINT */
1844 \f
1845 /* Structure for per-register (a.k.a. per-group) information.
1846    Other register information, such as the
1847    starting and ending positions (which are addresses), and the list of
1848    inner groups (which is a bits list) are maintained in separate
1849    variables.
1850
1851    We are making a (strictly speaking) nonportable assumption here: that
1852    the compiler will pack our bit fields into something that fits into
1853    the type of `word', i.e., is something that fits into one item on the
1854    failure stack.  */
1855
1856
1857 /* Declarations and macros for re_match_2.  */
1858
1859 typedef union
1860 {
1861   PREFIX(fail_stack_elt_t) word;
1862   struct
1863   {
1864       /* This field is one if this group can match the empty string,
1865          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
1866 # define MATCH_NULL_UNSET_VALUE 3
1867     unsigned match_null_string_p : 2;
1868     unsigned is_active : 1;
1869     unsigned matched_something : 1;
1870     unsigned ever_matched_something : 1;
1871   } bits;
1872 } PREFIX(register_info_type);
1873
1874 # ifndef DEFINED_ONCE
1875 #  define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
1876 #  define IS_ACTIVE(R)  ((R).bits.is_active)
1877 #  define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
1878 #  define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
1879
1880
1881 /* Call this when have matched a real character; it sets `matched' flags
1882    for the subexpressions which we are currently inside.  Also records
1883    that those subexprs have matched.  */
1884 #  define SET_REGS_MATCHED()                                            \
1885   do                                                                    \
1886     {                                                                   \
1887       if (!set_regs_matched_done)                                       \
1888         {                                                               \
1889           active_reg_t r;                                               \
1890           set_regs_matched_done = 1;                                    \
1891           for (r = lowest_active_reg; r <= highest_active_reg; r++)     \
1892             {                                                           \
1893               MATCHED_SOMETHING (reg_info[r])                           \
1894                 = EVER_MATCHED_SOMETHING (reg_info[r])                  \
1895                 = 1;                                                    \
1896             }                                                           \
1897         }                                                               \
1898     }                                                                   \
1899   while (0)
1900 # endif /* not DEFINED_ONCE */
1901
1902 /* Registers are set to a sentinel when they haven't yet matched.  */
1903 static CHAR_T PREFIX(reg_unset_dummy);
1904 # define REG_UNSET_VALUE (&PREFIX(reg_unset_dummy))
1905 # define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1906
1907 /* Subroutine declarations and macros for regex_compile.  */
1908 static void PREFIX(store_op1) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc, int arg));
1909 static void PREFIX(store_op2) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1910                                  int arg1, int arg2));
1911 static void PREFIX(insert_op1) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1912                                   int arg, UCHAR_T *end));
1913 static void PREFIX(insert_op2) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1914                                   int arg1, int arg2, UCHAR_T *end));
1915 static boolean PREFIX(at_begline_loc_p) _RE_ARGS ((const CHAR_T *pattern,
1916                                            const CHAR_T *p,
1917                                            reg_syntax_t syntax));
1918 static boolean PREFIX(at_endline_loc_p) _RE_ARGS ((const CHAR_T *p,
1919                                            const CHAR_T *pend,
1920                                            reg_syntax_t syntax));
1921 # ifdef WCHAR
1922 static reg_errcode_t wcs_compile_range _RE_ARGS ((CHAR_T range_start,
1923                                                   const CHAR_T **p_ptr,
1924                                                   const CHAR_T *pend,
1925                                                   char *translate,
1926                                                   reg_syntax_t syntax,
1927                                                   UCHAR_T *b,
1928                                                   CHAR_T *char_set));
1929 static void insert_space _RE_ARGS ((int num, CHAR_T *loc, CHAR_T *end));
1930 # else /* BYTE */
1931 static reg_errcode_t byte_compile_range _RE_ARGS ((unsigned int range_start,
1932                                                    const char **p_ptr,
1933                                                    const char *pend,
1934                                                    char *translate,
1935                                                    reg_syntax_t syntax,
1936                                                    unsigned char *b));
1937 # endif /* WCHAR */
1938
1939 /* Fetch the next character in the uncompiled pattern---translating it
1940    if necessary.  Also cast from a signed character in the constant
1941    string passed to us by the user to an unsigned char that we can use
1942    as an array index (in, e.g., `translate').  */
1943 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1944    because it is impossible to allocate 4GB array for some encodings
1945    which have 4 byte character_set like UCS4.  */
1946 # ifndef PATFETCH
1947 #  ifdef WCHAR
1948 #   define PATFETCH(c)                                                  \
1949   do {if (p == pend) return REG_EEND;                                   \
1950     c = (UCHAR_T) *p++;                                                 \
1951     if (translate && (c <= 0xff)) c = (UCHAR_T) translate[c];           \
1952   } while (0)
1953 #  else /* BYTE */
1954 #   define PATFETCH(c)                                                  \
1955   do {if (p == pend) return REG_EEND;                                   \
1956     c = (unsigned char) *p++;                                           \
1957     if (translate) c = (unsigned char) translate[c];                    \
1958   } while (0)
1959 #  endif /* WCHAR */
1960 # endif
1961
1962 /* Fetch the next character in the uncompiled pattern, with no
1963    translation.  */
1964 # define PATFETCH_RAW(c)                                                \
1965   do {if (p == pend) return REG_EEND;                                   \
1966     c = (UCHAR_T) *p++;                                                 \
1967   } while (0)
1968
1969 /* Go backwards one character in the pattern.  */
1970 # define PATUNFETCH p--
1971
1972
1973 /* If `translate' is non-null, return translate[D], else just D.  We
1974    cast the subscript to translate because some data is declared as
1975    `char *', to avoid warnings when a string constant is passed.  But
1976    when we use a character as a subscript we must make it unsigned.  */
1977 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1978    because it is impossible to allocate 4GB array for some encodings
1979    which have 4 byte character_set like UCS4.  */
1980
1981 # ifndef TRANSLATE
1982 #  ifdef WCHAR
1983 #   define TRANSLATE(d) \
1984   ((translate && ((UCHAR_T) (d)) <= 0xff) \
1985    ? (char) translate[(unsigned char) (d)] : (d))
1986 # else /* BYTE */
1987 #   define TRANSLATE(d) \
1988   (translate ? (char) translate[(unsigned char) (d)] : (d))
1989 #  endif /* WCHAR */
1990 # endif
1991
1992
1993 /* Macros for outputting the compiled pattern into `buffer'.  */
1994
1995 /* If the buffer isn't allocated when it comes in, use this.  */
1996 # define INIT_BUF_SIZE  (32 * sizeof(UCHAR_T))
1997
1998 /* Make sure we have at least N more bytes of space in buffer.  */
1999 # ifdef WCHAR
2000 #  define GET_BUFFER_SPACE(n)                                           \
2001     while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR       \
2002             + (n)*sizeof(CHAR_T)) > bufp->allocated)                    \
2003       EXTEND_BUFFER ()
2004 # else /* BYTE */
2005 #  define GET_BUFFER_SPACE(n)                                           \
2006     while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated)  \
2007       EXTEND_BUFFER ()
2008 # endif /* WCHAR */
2009
2010 /* Make sure we have one more byte of buffer space and then add C to it.  */
2011 # define BUF_PUSH(c)                                                    \
2012   do {                                                                  \
2013     GET_BUFFER_SPACE (1);                                               \
2014     *b++ = (UCHAR_T) (c);                                               \
2015   } while (0)
2016
2017
2018 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
2019 # define BUF_PUSH_2(c1, c2)                                             \
2020   do {                                                                  \
2021     GET_BUFFER_SPACE (2);                                               \
2022     *b++ = (UCHAR_T) (c1);                                              \
2023     *b++ = (UCHAR_T) (c2);                                              \
2024   } while (0)
2025
2026
2027 /* As with BUF_PUSH_2, except for three bytes.  */
2028 # define BUF_PUSH_3(c1, c2, c3)                                         \
2029   do {                                                                  \
2030     GET_BUFFER_SPACE (3);                                               \
2031     *b++ = (UCHAR_T) (c1);                                              \
2032     *b++ = (UCHAR_T) (c2);                                              \
2033     *b++ = (UCHAR_T) (c3);                                              \
2034   } while (0)
2035
2036 /* Store a jump with opcode OP at LOC to location TO.  We store a
2037    relative address offset by the three bytes the jump itself occupies.  */
2038 # define STORE_JUMP(op, loc, to) \
2039  PREFIX(store_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))
2040
2041 /* Likewise, for a two-argument jump.  */
2042 # define STORE_JUMP2(op, loc, to, arg) \
2043   PREFIX(store_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)
2044
2045 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
2046 # define INSERT_JUMP(op, loc, to) \
2047   PREFIX(insert_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)
2048
2049 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
2050 # define INSERT_JUMP2(op, loc, to, arg) \
2051   PREFIX(insert_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
2052               arg, b)
2053
2054 /* This is not an arbitrary limit: the arguments which represent offsets
2055    into the pattern are two bytes long.  So if 2^16 bytes turns out to
2056    be too small, many things would have to change.  */
2057 /* Any other compiler which, like MSC, has allocation limit below 2^16
2058    bytes will have to use approach similar to what was done below for
2059    MSC and drop MAX_BUF_SIZE a bit.  Otherwise you may end up
2060    reallocating to 0 bytes.  Such thing is not going to work too well.
2061    You have been warned!!  */
2062 # ifndef DEFINED_ONCE
2063 #  if defined _MSC_VER  && !defined WIN32
2064 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
2065    The REALLOC define eliminates a flurry of conversion warnings,
2066    but is not required. */
2067 #   define MAX_BUF_SIZE  65500L
2068 #   define REALLOC(p,s) realloc ((p), (size_t) (s))
2069 #  else
2070 #   define MAX_BUF_SIZE (1L << 16)
2071 #   define REALLOC(p,s) realloc ((p), (s))
2072 #  endif
2073
2074 /* Extend the buffer by twice its current size via realloc and
2075    reset the pointers that pointed into the old block to point to the
2076    correct places in the new one.  If extending the buffer results in it
2077    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
2078 #  if __BOUNDED_POINTERS__
2079 #   define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
2080 #   define MOVE_BUFFER_POINTER(P) \
2081   (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
2082 #   define ELSE_EXTEND_BUFFER_HIGH_BOUND        \
2083   else                                          \
2084     {                                           \
2085       SET_HIGH_BOUND (b);                       \
2086       SET_HIGH_BOUND (begalt);                  \
2087       if (fixup_alt_jump)                       \
2088         SET_HIGH_BOUND (fixup_alt_jump);        \
2089       if (laststart)                            \
2090         SET_HIGH_BOUND (laststart);             \
2091       if (pending_exact)                        \
2092         SET_HIGH_BOUND (pending_exact);         \
2093     }
2094 #  else
2095 #   define MOVE_BUFFER_POINTER(P) (P) += incr
2096 #   define ELSE_EXTEND_BUFFER_HIGH_BOUND
2097 #  endif
2098 # endif /* not DEFINED_ONCE */
2099
2100 # ifdef WCHAR
2101 #  define EXTEND_BUFFER()                                               \
2102   do {                                                                  \
2103     UCHAR_T *old_buffer = COMPILED_BUFFER_VAR;                          \
2104     int wchar_count;                                                    \
2105     if (bufp->allocated + sizeof(UCHAR_T) > MAX_BUF_SIZE)               \
2106       return REG_ESIZE;                                                 \
2107     bufp->allocated <<= 1;                                              \
2108     if (bufp->allocated > MAX_BUF_SIZE)                                 \
2109       bufp->allocated = MAX_BUF_SIZE;                                   \
2110     /* How many characters the new buffer can have?  */                 \
2111     wchar_count = bufp->allocated / sizeof(UCHAR_T);                    \
2112     if (wchar_count == 0) wchar_count = 1;                              \
2113     /* Truncate the buffer to CHAR_T align.  */                 \
2114     bufp->allocated = wchar_count * sizeof(UCHAR_T);                    \
2115     RETALLOC (COMPILED_BUFFER_VAR, wchar_count, UCHAR_T);               \
2116     bufp->buffer = (char*)COMPILED_BUFFER_VAR;                          \
2117     if (COMPILED_BUFFER_VAR == NULL)                                    \
2118       return REG_ESPACE;                                                \
2119     /* If the buffer moved, move all the pointers into it.  */          \
2120     if (old_buffer != COMPILED_BUFFER_VAR)                              \
2121       {                                                                 \
2122         int incr = COMPILED_BUFFER_VAR - old_buffer;                    \
2123         MOVE_BUFFER_POINTER (b);                                        \
2124         MOVE_BUFFER_POINTER (begalt);                                   \
2125         if (fixup_alt_jump)                                             \
2126           MOVE_BUFFER_POINTER (fixup_alt_jump);                         \
2127         if (laststart)                                                  \
2128           MOVE_BUFFER_POINTER (laststart);                              \
2129         if (pending_exact)                                              \
2130           MOVE_BUFFER_POINTER (pending_exact);                          \
2131       }                                                                 \
2132     ELSE_EXTEND_BUFFER_HIGH_BOUND                                       \
2133   } while (0)
2134 # else /* BYTE */
2135 #  define EXTEND_BUFFER()                                               \
2136   do {                                                                  \
2137     UCHAR_T *old_buffer = COMPILED_BUFFER_VAR;                          \
2138     if (bufp->allocated == MAX_BUF_SIZE)                                \
2139       return REG_ESIZE;                                                 \
2140     bufp->allocated <<= 1;                                              \
2141     if (bufp->allocated > MAX_BUF_SIZE)                                 \
2142       bufp->allocated = MAX_BUF_SIZE;                                   \
2143     bufp->buffer = (UCHAR_T *) REALLOC (COMPILED_BUFFER_VAR,            \
2144                                                 bufp->allocated);       \
2145     if (COMPILED_BUFFER_VAR == NULL)                                    \
2146       return REG_ESPACE;                                                \
2147     /* If the buffer moved, move all the pointers into it.  */          \
2148     if (old_buffer != COMPILED_BUFFER_VAR)                              \
2149       {                                                                 \
2150         int incr = COMPILED_BUFFER_VAR - old_buffer;                    \
2151         MOVE_BUFFER_POINTER (b);                                        \
2152         MOVE_BUFFER_POINTER (begalt);                                   \
2153         if (fixup_alt_jump)                                             \
2154           MOVE_BUFFER_POINTER (fixup_alt_jump);                         \
2155         if (laststart)                                                  \
2156           MOVE_BUFFER_POINTER (laststart);                              \
2157         if (pending_exact)                                              \
2158           MOVE_BUFFER_POINTER (pending_exact);                          \
2159       }                                                                 \
2160     ELSE_EXTEND_BUFFER_HIGH_BOUND                                       \
2161   } while (0)
2162 # endif /* WCHAR */
2163
2164 # ifndef DEFINED_ONCE
2165 /* Since we have one byte reserved for the register number argument to
2166    {start,stop}_memory, the maximum number of groups we can report
2167    things about is what fits in that byte.  */
2168 #  define MAX_REGNUM 255
2169
2170 /* But patterns can have more than `MAX_REGNUM' registers.  We just
2171    ignore the excess.  */
2172 typedef unsigned regnum_t;
2173
2174
2175 /* Macros for the compile stack.  */
2176
2177 /* Since offsets can go either forwards or backwards, this type needs to
2178    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
2179 /* int may be not enough when sizeof(int) == 2.  */
2180 typedef long pattern_offset_t;
2181
2182 typedef struct
2183 {
2184   pattern_offset_t begalt_offset;
2185   pattern_offset_t fixup_alt_jump;
2186   pattern_offset_t inner_group_offset;
2187   pattern_offset_t laststart_offset;
2188   regnum_t regnum;
2189 } compile_stack_elt_t;
2190
2191
2192 typedef struct
2193 {
2194   compile_stack_elt_t *stack;
2195   unsigned size;
2196   unsigned avail;                       /* Offset of next open position.  */
2197 } compile_stack_type;
2198
2199
2200 #  define INIT_COMPILE_STACK_SIZE 32
2201
2202 #  define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
2203 #  define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
2204
2205 /* The next available element.  */
2206 #  define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
2207
2208 # endif /* not DEFINED_ONCE */
2209
2210 /* Set the bit for character C in a list.  */
2211 # ifndef DEFINED_ONCE
2212 #  define SET_LIST_BIT(c)                               \
2213   (b[((unsigned char) (c)) / BYTEWIDTH]               \
2214    |= 1 << (((unsigned char) c) % BYTEWIDTH))
2215 # endif /* DEFINED_ONCE */
2216
2217 /* Get the next unsigned number in the uncompiled pattern.  */
2218 # define GET_UNSIGNED_NUMBER(num) \
2219   {                                                                     \
2220     while (p != pend)                                                   \
2221       {                                                                 \
2222         PATFETCH (c);                                                   \
2223         if (c < '0' || c > '9')                                         \
2224           break;                                                        \
2225         if (num <= RE_DUP_MAX)                                          \
2226           {                                                             \
2227             if (num < 0)                                                \
2228               num = 0;                                                  \
2229             num = num * 10 + c - '0';                                   \
2230           }                                                             \
2231       }                                                                 \
2232   }
2233
2234 # ifndef DEFINED_ONCE
2235 #  if defined _LIBC || WIDE_CHAR_SUPPORT
2236 /* The GNU C library provides support for user-defined character classes
2237    and the functions from ISO C amendement 1.  */
2238 #   ifdef CHARCLASS_NAME_MAX
2239 #    define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
2240 #   else
2241 /* This shouldn't happen but some implementation might still have this
2242    problem.  Use a reasonable default value.  */
2243 #    define CHAR_CLASS_MAX_LENGTH 256
2244 #   endif
2245
2246 #   ifdef _LIBC
2247 #    define IS_CHAR_CLASS(string) __wctype (string)
2248 #   else
2249 #    define IS_CHAR_CLASS(string) wctype (string)
2250 #   endif
2251 #  else
2252 #   define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
2253
2254 #   define IS_CHAR_CLASS(string)                                        \
2255    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
2256     || STREQ (string, "lower") || STREQ (string, "digit")               \
2257     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
2258     || STREQ (string, "space") || STREQ (string, "print")               \
2259     || STREQ (string, "punct") || STREQ (string, "graph")               \
2260     || STREQ (string, "cntrl") || STREQ (string, "blank"))
2261 #  endif
2262 # endif /* DEFINED_ONCE */
2263 \f
2264 # ifndef MATCH_MAY_ALLOCATE
2265
2266 /* If we cannot allocate large objects within re_match_2_internal,
2267    we make the fail stack and register vectors global.
2268    The fail stack, we grow to the maximum size when a regexp
2269    is compiled.
2270    The register vectors, we adjust in size each time we
2271    compile a regexp, according to the number of registers it needs.  */
2272
2273 static PREFIX(fail_stack_type) fail_stack;
2274
2275 /* Size with which the following vectors are currently allocated.
2276    That is so we can make them bigger as needed,
2277    but never make them smaller.  */
2278 #  ifdef DEFINED_ONCE
2279 static int regs_allocated_size;
2280
2281 static const char **     regstart, **     regend;
2282 static const char ** old_regstart, ** old_regend;
2283 static const char **best_regstart, **best_regend;
2284 static const char **reg_dummy;
2285 #  endif /* DEFINED_ONCE */
2286
2287 static PREFIX(register_info_type) *PREFIX(reg_info);
2288 static PREFIX(register_info_type) *PREFIX(reg_info_dummy);
2289
2290 /* Make the register vectors big enough for NUM_REGS registers,
2291    but don't make them smaller.  */
2292
2293 static void
2294 PREFIX(regex_grow_registers) (num_regs)
2295      int num_regs;
2296 {
2297   if (num_regs > regs_allocated_size)
2298     {
2299       RETALLOC_IF (regstart,     num_regs, const char *);
2300       RETALLOC_IF (regend,       num_regs, const char *);
2301       RETALLOC_IF (old_regstart, num_regs, const char *);
2302       RETALLOC_IF (old_regend,   num_regs, const char *);
2303       RETALLOC_IF (best_regstart, num_regs, const char *);
2304       RETALLOC_IF (best_regend,  num_regs, const char *);
2305       RETALLOC_IF (PREFIX(reg_info), num_regs, PREFIX(register_info_type));
2306       RETALLOC_IF (reg_dummy,    num_regs, const char *);
2307       RETALLOC_IF (PREFIX(reg_info_dummy), num_regs, PREFIX(register_info_type));
2308
2309       regs_allocated_size = num_regs;
2310     }
2311 }
2312
2313 # endif /* not MATCH_MAY_ALLOCATE */
2314 \f
2315 # ifndef DEFINED_ONCE
2316 static boolean group_in_compile_stack _RE_ARGS ((compile_stack_type
2317                                                  compile_stack,
2318                                                  regnum_t regnum));
2319 # endif /* not DEFINED_ONCE */
2320
2321 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2322    Returns one of error codes defined in `regex.h', or zero for success.
2323
2324    Assumes the `allocated' (and perhaps `buffer') and `translate'
2325    fields are set in BUFP on entry.
2326
2327    If it succeeds, results are put in BUFP (if it returns an error, the
2328    contents of BUFP are undefined):
2329      `buffer' is the compiled pattern;
2330      `syntax' is set to SYNTAX;
2331      `used' is set to the length of the compiled pattern;
2332      `fastmap_accurate' is zero;
2333      `re_nsub' is the number of subexpressions in PATTERN;
2334      `not_bol' and `not_eol' are zero;
2335
2336    The `fastmap' and `newline_anchor' fields are neither
2337    examined nor set.  */
2338
2339 /* Return, freeing storage we allocated.  */
2340 # ifdef WCHAR
2341 #  define FREE_STACK_RETURN(value)              \
2342   return (free(pattern), free(mbs_offset), free(is_binary), free (compile_stack.stack), value)
2343 # else
2344 #  define FREE_STACK_RETURN(value)              \
2345   return (free (compile_stack.stack), value)
2346 # endif /* WCHAR */
2347
2348 static reg_errcode_t
2349 PREFIX(regex_compile) (ARG_PREFIX(pattern), ARG_PREFIX(size), syntax, bufp)
2350      const char *ARG_PREFIX(pattern);
2351      size_t ARG_PREFIX(size);
2352      reg_syntax_t syntax;
2353      struct re_pattern_buffer *bufp;
2354 {
2355   /* We fetch characters from PATTERN here.  Even though PATTERN is
2356      `char *' (i.e., signed), we declare these variables as unsigned, so
2357      they can be reliably used as array indices.  */
2358   register UCHAR_T c, c1;
2359
2360 #ifdef WCHAR
2361   /* A temporary space to keep wchar_t pattern and compiled pattern.  */
2362   CHAR_T *pattern, *COMPILED_BUFFER_VAR;
2363   size_t size;
2364   /* offset buffer for optimization. See convert_mbs_to_wc.  */
2365   int *mbs_offset = NULL;
2366   /* It hold whether each wchar_t is binary data or not.  */
2367   char *is_binary = NULL;
2368   /* A flag whether exactn is handling binary data or not.  */
2369   char is_exactn_bin = FALSE;
2370 #endif /* WCHAR */
2371
2372   /* A random temporary spot in PATTERN.  */
2373   const CHAR_T *p1;
2374
2375   /* Points to the end of the buffer, where we should append.  */
2376   register UCHAR_T *b;
2377
2378   /* Keeps track of unclosed groups.  */
2379   compile_stack_type compile_stack;
2380
2381   /* Points to the current (ending) position in the pattern.  */
2382 #ifdef WCHAR
2383   const CHAR_T *p;
2384   const CHAR_T *pend;
2385 #else /* BYTE */
2386   const CHAR_T *p = pattern;
2387   const CHAR_T *pend = pattern + size;
2388 #endif /* WCHAR */
2389
2390   /* How to translate the characters in the pattern.  */
2391   RE_TRANSLATE_TYPE translate = bufp->translate;
2392
2393   /* Address of the count-byte of the most recently inserted `exactn'
2394      command.  This makes it possible to tell if a new exact-match
2395      character can be added to that command or if the character requires
2396      a new `exactn' command.  */
2397   UCHAR_T *pending_exact = 0;
2398
2399   /* Address of start of the most recently finished expression.
2400      This tells, e.g., postfix * where to find the start of its
2401      operand.  Reset at the beginning of groups and alternatives.  */
2402   UCHAR_T *laststart = 0;
2403
2404   /* Address of beginning of regexp, or inside of last group.  */
2405   UCHAR_T *begalt;
2406
2407   /* Address of the place where a forward jump should go to the end of
2408      the containing expression.  Each alternative of an `or' -- except the
2409      last -- ends with a forward jump of this sort.  */
2410   UCHAR_T *fixup_alt_jump = 0;
2411
2412   /* Counts open-groups as they are encountered.  Remembered for the
2413      matching close-group on the compile stack, so the same register
2414      number is put in the stop_memory as the start_memory.  */
2415   regnum_t regnum = 0;
2416
2417 #ifdef WCHAR
2418   /* Initialize the wchar_t PATTERN and offset_buffer.  */
2419   p = pend = pattern = TALLOC(csize + 1, CHAR_T);
2420   mbs_offset = TALLOC(csize + 1, int);
2421   is_binary = TALLOC(csize + 1, char);
2422   if (pattern == NULL || mbs_offset == NULL || is_binary == NULL)
2423     {
2424       free(pattern);
2425       free(mbs_offset);
2426       free(is_binary);
2427       return REG_ESPACE;
2428     }
2429   pattern[csize] = L'\0';       /* sentinel */
2430   size = convert_mbs_to_wcs(pattern, cpattern, csize, mbs_offset, is_binary);
2431   pend = p + size;
2432   if (size < 0)
2433     {
2434       free(pattern);
2435       free(mbs_offset);
2436       free(is_binary);
2437       return REG_BADPAT;
2438     }
2439 #endif
2440
2441 #ifdef DEBUG
2442   DEBUG_PRINT1 ("\nCompiling pattern: ");
2443   if (debug)
2444     {
2445       unsigned debug_count;
2446
2447       for (debug_count = 0; debug_count < size; debug_count++)
2448         PUT_CHAR (pattern[debug_count]);
2449       putchar ('\n');
2450     }
2451 #endif /* DEBUG */
2452
2453   /* Initialize the compile stack.  */
2454   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
2455   if (compile_stack.stack == NULL)
2456     {
2457 #ifdef WCHAR
2458       free(pattern);
2459       free(mbs_offset);
2460       free(is_binary);
2461 #endif
2462       return REG_ESPACE;
2463     }
2464
2465   compile_stack.size = INIT_COMPILE_STACK_SIZE;
2466   compile_stack.avail = 0;
2467
2468   /* Initialize the pattern buffer.  */
2469   bufp->syntax = syntax;
2470   bufp->fastmap_accurate = 0;
2471   bufp->not_bol = bufp->not_eol = 0;
2472
2473   /* Set `used' to zero, so that if we return an error, the pattern
2474      printer (for debugging) will think there's no pattern.  We reset it
2475      at the end.  */
2476   bufp->used = 0;
2477
2478   /* Always count groups, whether or not bufp->no_sub is set.  */
2479   bufp->re_nsub = 0;
2480
2481 #if !defined emacs && !defined SYNTAX_TABLE
2482   /* Initialize the syntax table.  */
2483    init_syntax_once ();
2484 #endif
2485
2486   if (bufp->allocated == 0)
2487     {
2488       if (bufp->buffer)
2489         { /* If zero allocated, but buffer is non-null, try to realloc
2490              enough space.  This loses if buffer's address is bogus, but
2491              that is the user's responsibility.  */
2492 #ifdef WCHAR
2493           /* Free bufp->buffer and allocate an array for wchar_t pattern
2494              buffer.  */
2495           free(bufp->buffer);
2496           COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE/sizeof(UCHAR_T),
2497                                         UCHAR_T);
2498 #else
2499           RETALLOC (COMPILED_BUFFER_VAR, INIT_BUF_SIZE, UCHAR_T);
2500 #endif /* WCHAR */
2501         }
2502       else
2503         { /* Caller did not allocate a buffer.  Do it for them.  */
2504           COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE / sizeof(UCHAR_T),
2505                                         UCHAR_T);
2506         }
2507
2508       if (!COMPILED_BUFFER_VAR) FREE_STACK_RETURN (REG_ESPACE);
2509 #ifdef WCHAR
2510       bufp->buffer = (char*)COMPILED_BUFFER_VAR;
2511 #endif /* WCHAR */
2512       bufp->allocated = INIT_BUF_SIZE;
2513     }
2514 #ifdef WCHAR
2515   else
2516     COMPILED_BUFFER_VAR = (UCHAR_T*) bufp->buffer;
2517 #endif
2518
2519   begalt = b = COMPILED_BUFFER_VAR;
2520
2521   /* Loop through the uncompiled pattern until we're at the end.  */
2522   while (p != pend)
2523     {
2524       PATFETCH (c);
2525
2526       switch (c)
2527         {
2528         case '^':
2529           {
2530             if (   /* If at start of pattern, it's an operator.  */
2531                    p == pattern + 1
2532                    /* If context independent, it's an operator.  */
2533                 || syntax & RE_CONTEXT_INDEP_ANCHORS
2534                    /* Otherwise, depends on what's come before.  */
2535                 || PREFIX(at_begline_loc_p) (pattern, p, syntax))
2536               BUF_PUSH (begline);
2537             else
2538               goto normal_char;
2539           }
2540           break;
2541
2542
2543         case '$':
2544           {
2545             if (   /* If at end of pattern, it's an operator.  */
2546                    p == pend
2547                    /* If context independent, it's an operator.  */
2548                 || syntax & RE_CONTEXT_INDEP_ANCHORS
2549                    /* Otherwise, depends on what's next.  */
2550                 || PREFIX(at_endline_loc_p) (p, pend, syntax))
2551                BUF_PUSH (endline);
2552              else
2553                goto normal_char;
2554            }
2555            break;
2556
2557
2558         case '+':
2559         case '?':
2560           if ((syntax & RE_BK_PLUS_QM)
2561               || (syntax & RE_LIMITED_OPS))
2562             goto normal_char;
2563         handle_plus:
2564         case '*':
2565           /* If there is no previous pattern... */
2566           if (!laststart)
2567             {
2568               if (syntax & RE_CONTEXT_INVALID_OPS)
2569                 FREE_STACK_RETURN (REG_BADRPT);
2570               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
2571                 goto normal_char;
2572             }
2573
2574           {
2575             /* Are we optimizing this jump?  */
2576             boolean keep_string_p = false;
2577
2578             /* 1 means zero (many) matches is allowed.  */
2579             char zero_times_ok = 0, many_times_ok = 0;
2580
2581             /* If there is a sequence of repetition chars, collapse it
2582                down to just one (the right one).  We can't combine
2583                interval operators with these because of, e.g., `a{2}*',
2584                which should only match an even number of `a's.  */
2585
2586             for (;;)
2587               {
2588                 zero_times_ok |= c != '+';
2589                 many_times_ok |= c != '?';
2590
2591                 if (p == pend)
2592                   break;
2593
2594                 PATFETCH (c);
2595
2596                 if (c == '*'
2597                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
2598                   ;
2599
2600                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
2601                   {
2602                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2603
2604                     PATFETCH (c1);
2605                     if (!(c1 == '+' || c1 == '?'))
2606                       {
2607                         PATUNFETCH;
2608                         PATUNFETCH;
2609                         break;
2610                       }
2611
2612                     c = c1;
2613                   }
2614                 else
2615                   {
2616                     PATUNFETCH;
2617                     break;
2618                   }
2619
2620                 /* If we get here, we found another repeat character.  */
2621                }
2622
2623             /* Star, etc. applied to an empty pattern is equivalent
2624                to an empty pattern.  */
2625             if (!laststart)
2626               break;
2627
2628             /* Now we know whether or not zero matches is allowed
2629                and also whether or not two or more matches is allowed.  */
2630             if (many_times_ok)
2631               { /* More than one repetition is allowed, so put in at the
2632                    end a backward relative jump from `b' to before the next
2633                    jump we're going to put in below (which jumps from
2634                    laststart to after this jump).
2635
2636                    But if we are at the `*' in the exact sequence `.*\n',
2637                    insert an unconditional jump backwards to the .,
2638                    instead of the beginning of the loop.  This way we only
2639                    push a failure point once, instead of every time
2640                    through the loop.  */
2641                 assert (p - 1 > pattern);
2642
2643                 /* Allocate the space for the jump.  */
2644                 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2645
2646                 /* We know we are not at the first character of the pattern,
2647                    because laststart was nonzero.  And we've already
2648                    incremented `p', by the way, to be the character after
2649                    the `*'.  Do we have to do something analogous here
2650                    for null bytes, because of RE_DOT_NOT_NULL?  */
2651                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
2652                     && zero_times_ok
2653                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
2654                     && !(syntax & RE_DOT_NEWLINE))
2655                   { /* We have .*\n.  */
2656                     STORE_JUMP (jump, b, laststart);
2657                     keep_string_p = true;
2658                   }
2659                 else
2660                   /* Anything else.  */
2661                   STORE_JUMP (maybe_pop_jump, b, laststart -
2662                               (1 + OFFSET_ADDRESS_SIZE));
2663
2664                 /* We've added more stuff to the buffer.  */
2665                 b += 1 + OFFSET_ADDRESS_SIZE;
2666               }
2667
2668             /* On failure, jump from laststart to b + 3, which will be the
2669                end of the buffer after this jump is inserted.  */
2670             /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE' instead of
2671                'b + 3'.  */
2672             GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2673             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2674                                        : on_failure_jump,
2675                          laststart, b + 1 + OFFSET_ADDRESS_SIZE);
2676             pending_exact = 0;
2677             b += 1 + OFFSET_ADDRESS_SIZE;
2678
2679             if (!zero_times_ok)
2680               {
2681                 /* At least one repetition is required, so insert a
2682                    `dummy_failure_jump' before the initial
2683                    `on_failure_jump' instruction of the loop. This
2684                    effects a skip over that instruction the first time
2685                    we hit that loop.  */
2686                 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2687                 INSERT_JUMP (dummy_failure_jump, laststart, laststart +
2688                              2 + 2 * OFFSET_ADDRESS_SIZE);
2689                 b += 1 + OFFSET_ADDRESS_SIZE;
2690               }
2691             }
2692           break;
2693
2694
2695         case '.':
2696           laststart = b;
2697           BUF_PUSH (anychar);
2698           break;
2699
2700
2701         case '[':
2702           {
2703             boolean had_char_class = false;
2704 #ifdef WCHAR
2705             CHAR_T range_start = 0xffffffff;
2706 #else
2707             unsigned int range_start = 0xffffffff;
2708 #endif
2709             if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2710
2711 #ifdef WCHAR
2712             /* We assume a charset(_not) structure as a wchar_t array.
2713                charset[0] = (re_opcode_t) charset(_not)
2714                charset[1] = l (= length of char_classes)
2715                charset[2] = m (= length of collating_symbols)
2716                charset[3] = n (= length of equivalence_classes)
2717                charset[4] = o (= length of char_ranges)
2718                charset[5] = p (= length of chars)
2719
2720                charset[6] = char_class (wctype_t)
2721                charset[6+CHAR_CLASS_SIZE] = char_class (wctype_t)
2722                          ...
2723                charset[l+5]  = char_class (wctype_t)
2724
2725                charset[l+6]  = collating_symbol (wchar_t)
2726                             ...
2727                charset[l+m+5]  = collating_symbol (wchar_t)
2728                                         ifdef _LIBC we use the index if
2729                                         _NL_COLLATE_SYMB_EXTRAMB instead of
2730                                         wchar_t string.
2731
2732                charset[l+m+6]  = equivalence_classes (wchar_t)
2733                               ...
2734                charset[l+m+n+5]  = equivalence_classes (wchar_t)
2735                                         ifdef _LIBC we use the index in
2736                                         _NL_COLLATE_WEIGHT instead of
2737                                         wchar_t string.
2738
2739                charset[l+m+n+6] = range_start
2740                charset[l+m+n+7] = range_end
2741                                ...
2742                charset[l+m+n+2o+4] = range_start
2743                charset[l+m+n+2o+5] = range_end
2744                                         ifdef _LIBC we use the value looked up
2745                                         in _NL_COLLATE_COLLSEQ instead of
2746                                         wchar_t character.
2747
2748                charset[l+m+n+2o+6] = char
2749                                   ...
2750                charset[l+m+n+2o+p+5] = char
2751
2752              */
2753
2754             /* We need at least 6 spaces: the opcode, the length of
2755                char_classes, the length of collating_symbols, the length of
2756                equivalence_classes, the length of char_ranges, the length of
2757                chars.  */
2758             GET_BUFFER_SPACE (6);
2759
2760             /* Save b as laststart. And We use laststart as the pointer
2761                to the first element of the charset here.
2762                In other words, laststart[i] indicates charset[i].  */
2763             laststart = b;
2764
2765             /* We test `*p == '^' twice, instead of using an if
2766                statement, so we only need one BUF_PUSH.  */
2767             BUF_PUSH (*p == '^' ? charset_not : charset);
2768             if (*p == '^')
2769               p++;
2770
2771             /* Push the length of char_classes, the length of
2772                collating_symbols, the length of equivalence_classes, the
2773                length of char_ranges and the length of chars.  */
2774             BUF_PUSH_3 (0, 0, 0);
2775             BUF_PUSH_2 (0, 0);
2776
2777             /* Remember the first position in the bracket expression.  */
2778             p1 = p;
2779
2780             /* charset_not matches newline according to a syntax bit.  */
2781             if ((re_opcode_t) b[-6] == charset_not
2782                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2783               {
2784                 BUF_PUSH('\n');
2785                 laststart[5]++; /* Update the length of characters  */
2786               }
2787
2788             /* Read in characters and ranges, setting map bits.  */
2789             for (;;)
2790               {
2791                 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2792
2793                 PATFETCH (c);
2794
2795                 /* \ might escape characters inside [...] and [^...].  */
2796                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2797                   {
2798                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2799
2800                     PATFETCH (c1);
2801                     BUF_PUSH(c1);
2802                     laststart[5]++; /* Update the length of chars  */
2803                     range_start = c1;
2804                     continue;
2805                   }
2806
2807                 /* Could be the end of the bracket expression.  If it's
2808                    not (i.e., when the bracket expression is `[]' so
2809                    far), the ']' character bit gets set way below.  */
2810                 if (c == ']' && p != p1 + 1)
2811                   break;
2812
2813                 /* Look ahead to see if it's a range when the last thing
2814                    was a character class.  */
2815                 if (had_char_class && c == '-' && *p != ']')
2816                   FREE_STACK_RETURN (REG_ERANGE);
2817
2818                 /* Look ahead to see if it's a range when the last thing
2819                    was a character: if this is a hyphen not at the
2820                    beginning or the end of a list, then it's the range
2821                    operator.  */
2822                 if (c == '-'
2823                     && !(p - 2 >= pattern && p[-2] == '[')
2824                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2825                     && *p != ']')
2826                   {
2827                     reg_errcode_t ret;
2828                     /* Allocate the space for range_start and range_end.  */
2829                     GET_BUFFER_SPACE (2);
2830                     /* Update the pointer to indicate end of buffer.  */
2831                     b += 2;
2832                     ret = wcs_compile_range (range_start, &p, pend, translate,
2833                                          syntax, b, laststart);
2834                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2835                     range_start = 0xffffffff;
2836                   }
2837                 else if (p[0] == '-' && p[1] != ']')
2838                   { /* This handles ranges made up of characters only.  */
2839                     reg_errcode_t ret;
2840
2841                     /* Move past the `-'.  */
2842                     PATFETCH (c1);
2843                     /* Allocate the space for range_start and range_end.  */
2844                     GET_BUFFER_SPACE (2);
2845                     /* Update the pointer to indicate end of buffer.  */
2846                     b += 2;
2847                     ret = wcs_compile_range (c, &p, pend, translate, syntax, b,
2848                                          laststart);
2849                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2850                     range_start = 0xffffffff;
2851                   }
2852
2853                 /* See if we're at the beginning of a possible character
2854                    class.  */
2855                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2856                   { /* Leave room for the null.  */
2857                     char str[CHAR_CLASS_MAX_LENGTH + 1];
2858
2859                     PATFETCH (c);
2860                     c1 = 0;
2861
2862                     /* If pattern is `[[:'.  */
2863                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2864
2865                     for (;;)
2866                       {
2867                         PATFETCH (c);
2868                         if ((c == ':' && *p == ']') || p == pend)
2869                           break;
2870                         if (c1 < CHAR_CLASS_MAX_LENGTH)
2871                           str[c1++] = c;
2872                         else
2873                           /* This is in any case an invalid class name.  */
2874                           str[0] = '\0';
2875                       }
2876                     str[c1] = '\0';
2877
2878                     /* If isn't a word bracketed by `[:' and `:]':
2879                        undo the ending character, the letters, and leave
2880                        the leading `:' and `[' (but store them as character).  */
2881                     if (c == ':' && *p == ']')
2882                       {
2883                         wctype_t wt;
2884                         uintptr_t alignedp;
2885
2886                         /* Query the character class as wctype_t.  */
2887                         wt = IS_CHAR_CLASS (str);
2888                         if (wt == 0)
2889                           FREE_STACK_RETURN (REG_ECTYPE);
2890
2891                         /* Throw away the ] at the end of the character
2892                            class.  */
2893                         PATFETCH (c);
2894
2895                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2896
2897                         /* Allocate the space for character class.  */
2898                         GET_BUFFER_SPACE(CHAR_CLASS_SIZE);
2899                         /* Update the pointer to indicate end of buffer.  */
2900                         b += CHAR_CLASS_SIZE;
2901                         /* Move data which follow character classes
2902                             not to violate the data.  */
2903                         insert_space(CHAR_CLASS_SIZE,
2904                                      laststart + 6 + laststart[1],
2905                                      b - 1);
2906                         alignedp = ((uintptr_t)(laststart + 6 + laststart[1])
2907                                     + __alignof__(wctype_t) - 1)
2908                                     & ~(uintptr_t)(__alignof__(wctype_t) - 1);
2909                         /* Store the character class.  */
2910                         *((wctype_t*)alignedp) = wt;
2911                         /* Update length of char_classes */
2912                         laststart[1] += CHAR_CLASS_SIZE;
2913
2914                         had_char_class = true;
2915                       }
2916                     else
2917                       {
2918                         c1++;
2919                         while (c1--)
2920                           PATUNFETCH;
2921                         BUF_PUSH ('[');
2922                         BUF_PUSH (':');
2923                         laststart[5] += 2; /* Update the length of characters  */
2924                         range_start = ':';
2925                         had_char_class = false;
2926                       }
2927                   }
2928                 else if (syntax & RE_CHAR_CLASSES && c == '[' && (*p == '='
2929                                                           || *p == '.'))
2930                   {
2931                     CHAR_T str[128];    /* Should be large enough.  */
2932                     CHAR_T delim = *p; /* '=' or '.'  */
2933 # ifdef _LIBC
2934                     uint32_t nrules =
2935                       _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2936 # endif
2937                     PATFETCH (c);
2938                     c1 = 0;
2939
2940                     /* If pattern is `[[=' or '[[.'.  */
2941                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2942
2943                     for (;;)
2944                       {
2945                         PATFETCH (c);
2946                         if ((c == delim && *p == ']') || p == pend)
2947                           break;
2948                         if (c1 < sizeof (str) - 1)
2949                           str[c1++] = c;
2950                         else
2951                           /* This is in any case an invalid class name.  */
2952                           str[0] = '\0';
2953                       }
2954                     str[c1] = '\0';
2955
2956                     if (c == delim && *p == ']' && str[0] != '\0')
2957                       {
2958                         unsigned int i, offset;
2959                         /* If we have no collation data we use the default
2960                            collation in which each character is in a class
2961                            by itself.  It also means that ASCII is the
2962                            character set and therefore we cannot have character
2963                            with more than one byte in the multibyte
2964                            representation.  */
2965
2966                         /* If not defined _LIBC, we push the name and
2967                            `\0' for the sake of matching performance.  */
2968                         int datasize = c1 + 1;
2969
2970 # ifdef _LIBC
2971                         int32_t idx = 0;
2972                         if (nrules == 0)
2973 # endif
2974                           {
2975                             if (c1 != 1)
2976                               FREE_STACK_RETURN (REG_ECOLLATE);
2977                           }
2978 # ifdef _LIBC
2979                         else
2980                           {
2981                             const int32_t *table;
2982                             const int32_t *weights;
2983                             const int32_t *extra;
2984                             const int32_t *indirect;
2985                             wint_t *cp;
2986
2987                             /* This #include defines a local function!  */
2988 #  include <locale/weightwc.h>
2989
2990                             if(delim == '=')
2991                               {
2992                                 /* We push the index for equivalence class.  */
2993                                 cp = (wint_t*)str;
2994
2995                                 table = (const int32_t *)
2996                                   _NL_CURRENT (LC_COLLATE,
2997                                                _NL_COLLATE_TABLEWC);
2998                                 weights = (const int32_t *)
2999                                   _NL_CURRENT (LC_COLLATE,
3000                                                _NL_COLLATE_WEIGHTWC);
3001                                 extra = (const int32_t *)
3002                                   _NL_CURRENT (LC_COLLATE,
3003                                                _NL_COLLATE_EXTRAWC);
3004                                 indirect = (const int32_t *)
3005                                   _NL_CURRENT (LC_COLLATE,
3006                                                _NL_COLLATE_INDIRECTWC);
3007
3008                                 idx = findidx ((const wint_t**)&cp);
3009                                 if (idx == 0 || cp < (wint_t*) str + c1)
3010                                   /* This is no valid character.  */
3011                                   FREE_STACK_RETURN (REG_ECOLLATE);
3012
3013                                 str[0] = (wchar_t)idx;
3014                               }
3015                             else /* delim == '.' */
3016                               {
3017                                 /* We push collation sequence value
3018                                    for collating symbol.  */
3019                                 int32_t table_size;
3020                                 const int32_t *symb_table;
3021                                 const unsigned char *extra;
3022                                 int32_t idx;
3023                                 int32_t elem;
3024                                 int32_t second;
3025                                 int32_t hash;
3026                                 char char_str[c1];
3027
3028                                 /* We have to convert the name to a single-byte
3029                                    string.  This is possible since the names
3030                                    consist of ASCII characters and the internal
3031                                    representation is UCS4.  */
3032                                 for (i = 0; i < c1; ++i)
3033                                   char_str[i] = str[i];
3034
3035                                 table_size =
3036                                   _NL_CURRENT_WORD (LC_COLLATE,
3037                                                     _NL_COLLATE_SYMB_HASH_SIZEMB);
3038                                 symb_table = (const int32_t *)
3039                                   _NL_CURRENT (LC_COLLATE,
3040                                                _NL_COLLATE_SYMB_TABLEMB);
3041                                 extra = (const unsigned char *)
3042                                   _NL_CURRENT (LC_COLLATE,
3043                                                _NL_COLLATE_SYMB_EXTRAMB);
3044
3045                                 /* Locate the character in the hashing table.  */
3046                                 hash = elem_hash (char_str, c1);
3047
3048                                 idx = 0;
3049                                 elem = hash % table_size;
3050                                 second = hash % (table_size - 2);
3051                                 while (symb_table[2 * elem] != 0)
3052                                   {
3053                                     /* First compare the hashing value.  */
3054                                     if (symb_table[2 * elem] == hash
3055                                         && c1 == extra[symb_table[2 * elem + 1]]
3056                                         && memcmp (str,
3057                                                    &extra[symb_table[2 * elem + 1]
3058                                                          + 1], c1) == 0)
3059                                       {
3060                                         /* Yep, this is the entry.  */
3061                                         idx = symb_table[2 * elem + 1];
3062                                         idx += 1 + extra[idx];
3063                                         break;
3064                                       }
3065
3066                                     /* Next entry.  */
3067                                     elem += second;
3068                                   }
3069
3070                                 if (symb_table[2 * elem] != 0)
3071                                   {
3072                                     /* Compute the index of the byte sequence
3073                                        in the table.  */
3074                                     idx += 1 + extra[idx];
3075                                     /* Adjust for the alignment.  */
3076                                     idx = (idx + 3) & ~4;
3077
3078                                     str[0] = (wchar_t) idx + 4;
3079                                   }
3080                                 else if (symb_table[2 * elem] == 0 && c1 == 1)
3081                                   {
3082                                     /* No valid character.  Match it as a
3083                                        single byte character.  */
3084                                     had_char_class = false;
3085                                     BUF_PUSH(str[0]);
3086                                     /* Update the length of characters  */
3087                                     laststart[5]++;
3088                                     range_start = str[0];
3089
3090                                     /* Throw away the ] at the end of the
3091                                        collating symbol.  */
3092                                     PATFETCH (c);
3093                                     /* exit from the switch block.  */
3094                                     continue;
3095                                   }
3096                                 else
3097                                   FREE_STACK_RETURN (REG_ECOLLATE);
3098                               }
3099                             datasize = 1;
3100                           }
3101 # endif
3102                         /* Throw away the ] at the end of the equivalence
3103                            class (or collating symbol).  */
3104                         PATFETCH (c);
3105
3106                         /* Allocate the space for the equivalence class
3107                            (or collating symbol) (and '\0' if needed).  */
3108                         GET_BUFFER_SPACE(datasize);
3109                         /* Update the pointer to indicate end of buffer.  */
3110                         b += datasize;
3111
3112                         if (delim == '=')
3113                           { /* equivalence class  */
3114                             /* Calculate the offset of char_ranges,
3115                                which is next to equivalence_classes.  */
3116                             offset = laststart[1] + laststart[2]
3117                               + laststart[3] +6;
3118                             /* Insert space.  */
3119                             insert_space(datasize, laststart + offset, b - 1);
3120
3121                             /* Write the equivalence_class and \0.  */
3122                             for (i = 0 ; i < datasize ; i++)
3123                        &nb