pcre/pcre.c

   1 /*************************************************
   2 *      Perl-Compatible Regular Expressions       *
   3 *************************************************/
   4
   5 /*
   6 This is a library of functions to support regular expressions whose syntax
   7 and semantics are as close as possible to those of the Perl 5 language. See
   8 the file Tech.Notes for some information on the internals.
   9
  10 Written by: Philip Hazel <ph10@cam.ac.uk>
  11
  12            Copyright (c) 1997-2000 University of Cambridge
  13
  14 -----------------------------------------------------------------------------
  15 Permission is granted to anyone to use this software for any purpose on any
  16 computer system, and to redistribute it freely, subject to the following
  17 restrictions:
  18
  19 1. This software is distributed in the hope that it will be useful,
  20    but WITHOUT ANY WARRANTY; without even the implied warranty of
  21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  22
  23 2. The origin of this software must not be misrepresented, either by
  24    explicit claim or by omission.
  25
  26 3. Altered versions must be plainly marked as such, and must not be
  27    misrepresented as being the original software.
  28
  29 4. If PCRE is embedded in any software that is released under the GNU
  30    General Purpose Licence (GPL), then the terms of that licence shall
  31    supersede any condition above with which it is incompatible.
  32 -----------------------------------------------------------------------------
  33 */
  34
  35
  36 /* Define DEBUG to get debugging output on stdout. */
  37
  38 /* #define DEBUG */
  39
  40 /* Use a macro for debugging printing, 'cause that eliminates the use of #ifdef
  41 inline, and there are *still* stupid compilers about that don't like indented
  42 pre-processor statements. I suppose it's only been 10 years... */
  43
  44 #ifdef DEBUG
  45 #define DPRINTF(p) printf p
  46 #else
  47 #define DPRINTF(p) /*nothing*/
  48 #endif
  49
  50 /* Include the internals header, which itself includes Standard C headers plus
  51 the external pcre header. */
  52
  53 #include "internal.h"
  54
  55
  56 /* Allow compilation as C++ source code, should anybody want to do that. */
  57
  58 #ifdef __cplusplus
  59 #define class pcre_class
  60 #endif
  61
  62
  63 /* Number of items on the nested bracket stacks at compile time. This should
  64 not be set greater than 200. */
  65
  66 #define BRASTACK_SIZE 200
  67
  68
  69 /* The number of bytes in a literal character string above which we can't add
  70 any more is different when UTF-8 characters may be encountered. */
  71
  72 #ifdef SUPPORT_UTF8
  73 #define MAXLIT 250
  74 #else
  75 #define MAXLIT 255
  76 #endif
  77
  78
  79 /* Min and max values for the common repeats; for the maxima, 0 => infinity */
  80
  81 static const char rep_min[] = { 0, 0, 1, 1, 0, 0 };
  82 static const char rep_max[] = { 0, 0, 0, 0, 1, 1 };
  83
  84 /* Text forms of OP_ values and things, for debugging (not all used) */
  85
  86 #ifdef DEBUG
  87 static const char *OP_names[] = {
  88   "End", "\\A", "\\B", "\\b", "\\D", "\\d",
  89   "\\S", "\\s", "\\W", "\\w", "\\Z", "\\z",
  90   "Opt", "^", "$", "Any", "chars", "not",
  91   "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
  92   "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
  93   "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
  94   "*", "*?", "+", "+?", "?", "??", "{", "{",
  95   "class", "Ref", "Recurse",
  96   "Alt", "Ket", "KetRmax", "KetRmin", "Assert", "Assert not",
  97   "AssertB", "AssertB not", "Reverse", "Once", "Cond", "Cref",
  98   "Brazero", "Braminzero", "Bra"
  99 };
 100 #endif
 101
 102 /* Table for handling escaped characters in the range '0'-'z'. Positive returns
 103 are simple data values; negative values are for special things like \d and so
 104 on. Zero means further processing is needed (for things like \x), or the escape
 105 is invalid. */
 106
 107 static const short int escapes[] = {
 108     0,      0,      0,      0,      0,      0,      0,      0,   /* 0 - 7 */
 109     0,      0,    ':',    ';',    '<',    '=',    '>',    '?',   /* 8 - ? */
 110   '@', -ESC_A, -ESC_B,      0, -ESC_D,      0,      0,      0,   /* @ - G */
 111     0,      0,      0,      0,      0,      0,      0,      0,   /* H - O */
 112     0,      0,      0, -ESC_S,      0,      0,      0, -ESC_W,   /* P - W */
 113     0,      0, -ESC_Z,    '[',   '\\',    ']',    '^',    '_',   /* X - _ */
 114   '`',      7, -ESC_b,      0, -ESC_d,     27,   '\f',      0,   /* ` - g */
 115     0,      0,      0,      0,      0,      0,   '\n',      0,   /* h - o */
 116     0,      0,   '\r', -ESC_s,   '\t',      0,      0, -ESC_w,   /* p - w */
 117     0,      0, -ESC_z                                            /* x - z */
 118 };
 119
 120 /* Tables of names of POSIX character classes and their lengths. The list is
 121 terminated by a zero length entry. The first three must be alpha, upper, lower,
 122 as this is assumed for handling case independence. */
 123
 124 static const char *posix_names[] = {
 125   "alpha", "lower", "upper",
 126   "alnum", "ascii", "cntrl", "digit", "graph",
 127   "print", "punct", "space", "word",  "xdigit" };
 128
 129 static const uschar posix_name_lengths[] = {
 130   5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 6, 0 };
 131
 132 /* Table of class bit maps for each POSIX class; up to three may be combined
 133 to form the class. */
 134
 135 static const int posix_class_maps[] = {
 136   cbit_lower, cbit_upper, -1,             /* alpha */
 137   cbit_lower, -1,         -1,             /* lower */
 138   cbit_upper, -1,         -1,             /* upper */
 139   cbit_digit, cbit_lower, cbit_upper,     /* alnum */
 140   cbit_print, cbit_cntrl, -1,             /* ascii */
 141   cbit_cntrl, -1,         -1,             /* cntrl */
 142   cbit_digit, -1,         -1,             /* digit */
 143   cbit_graph, -1,         -1,             /* graph */
 144   cbit_print, -1,         -1,             /* print */
 145   cbit_punct, -1,         -1,             /* punct */
 146   cbit_space, -1,         -1,             /* space */
 147   cbit_word,  -1,         -1,             /* word */
 148   cbit_xdigit,-1,         -1              /* xdigit */
 149 };
 150
 151
 152 /* Definition to allow mutual recursion */
 153
 154 static BOOL
 155   compile_regex(int, int, int *, uschar **, const uschar **, const char **,
 156     BOOL, int, int *, int *, compile_data *);
 157
 158 /* Structure for building a chain of data that actually lives on the
 159 stack, for holding the values of the subject pointer at the start of each
 160 subpattern, so as to detect when an empty string has been matched by a
 161 subpattern - to break infinite loops. */
 162
 163 typedef struct eptrblock {
 164   struct eptrblock *prev;
 165   const uschar *saved_eptr;
 166 } eptrblock;
 167
 168 /* Flag bits for the match() function */
 169
 170 #define match_condassert   0x01    /* Called to check a condition assertion */
 171 #define match_isgroup      0x02    /* Set if start of bracketed group */
 172
 173
 174
 175 /*************************************************
 176 *               Global variables                 *
 177 *************************************************/
 178
 179 /* PCRE is thread-clean and doesn't use any global variables in the normal
 180 sense. However, it calls memory allocation and free functions via the two
 181 indirections below, which are can be changed by the caller, but are shared
 182 between all threads. */
 183
 184 void *(*pcre_malloc)(size_t) = malloc;
 185 void  (*pcre_free)(void *) = free;
 186
 187
 188
 189 /*************************************************
 190 *    Macros and tables for character handling    *
 191 *************************************************/
 192
 193 /* When UTF-8 encoding is being used, a character is no longer just a single
 194 byte. The macros for character handling generate simple sequences when used in
 195 byte-mode, and more complicated ones for UTF-8 characters. */
 196
 197 #ifndef SUPPORT_UTF8
 198 #define GETCHARINC(c, eptr) c = *eptr++;
 199 #define GETCHARLEN(c, eptr, len) c = *eptr;
 200 #define BACKCHAR(eptr)
 201
 202 #else   /* SUPPORT_UTF8 */
 203
 204 /* Get the next UTF-8 character, advancing the pointer */
 205
 206 #define GETCHARINC(c, eptr) \
 207   c = *eptr++; \
 208   if (md->utf8 && (c & 0xc0) == 0xc0) \
 209     { \
 210     int a = utf8_table4[c & 0x3f];  /* Number of additional bytes */ \
 211     int s = 6 - a;                  /* Amount to shift next byte */  \
 212     c &= utf8_table3[a];            /* Low order bits from first byte */ \
 213     while (a-- > 0) \
 214       { \
 215       c |= (*eptr++ & 0x3f) << s; \
 216       s += 6; \
 217       } \
 218     }
 219
 220 /* Get the next UTF-8 character, not advancing the pointer, setting length */
 221
 222 #define GETCHARLEN(c, eptr, len) \
 223   c = *eptr; \
 224   len = 1; \
 225   if (md->utf8 && (c & 0xc0) == 0xc0) \
 226     { \
 227     int i; \
 228     int a = utf8_table4[c & 0x3f];  /* Number of additional bytes */ \
 229     int s = 6 - a;                  /* Amount to shift next byte */  \
 230     c &= utf8_table3[a];            /* Low order bits from first byte */ \
 231     for (i = 1; i <= a; i++) \
 232       { \
 233       c |= (eptr[i] & 0x3f) << s; \
 234       s += 6; \
 235       } \
 236     len += a; \
 237     }
 238
 239 /* If the pointer is not at the start of a character, move it back until
 240 it is. */
 241
 242 #define BACKCHAR(eptr) while((*eptr & 0xc0) == 0x80) eptr--;
 243
 244 #endif
 245
 246
 247
 248 /*************************************************
 249 *             Default character tables           *
 250 *************************************************/
 251
 252 /* A default set of character tables is included in the PCRE binary. Its source
 253 is built by the maketables auxiliary program, which uses the default C ctypes
 254 functions, and put in the file chartables.c. These tables are used by PCRE
 255 whenever the caller of pcre_compile() does not provide an alternate set of
 256 tables. */
 257
 258 #include "chartables.c"
 259
 260
 261
 262 #ifdef SUPPORT_UTF8
 263 /*************************************************
 264 *           Tables for UTF-8 support             *
 265 *************************************************/
 266
 267 /* These are the breakpoints for different numbers of bytes in a UTF-8
 268 character. */
 269
 270 static int utf8_table1[] = { 0x7f, 0x7ff, 0xffff, 0x1fffff, 0x3ffffff, 0x7fffffff};
 271
 272 /* These are the indicator bits and the mask for the data bits to set in the
 273 first byte of a character, indexed by the number of additional bytes. */
 274
 275 static int utf8_table2[] = { 0,    0xc0, 0xe0, 0xf0, 0xf8, 0xfc};
 276 static int utf8_table3[] = { 0xff, 0x1f, 0x0f, 0x07, 0x03, 0x01};
 277
 278 /* Table of the number of extra characters, indexed by the first character
 279 masked with 0x3f. The highest number for a valid UTF-8 character is in fact
 280 0x3d. */
 281
 282 static uschar utf8_table4[] = {
 283   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 284   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 285   2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
 286   3,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5 };
 287
 288
 289 /*************************************************
 290 *       Convert character value to UTF-8         *
 291 *************************************************/
 292
 293 /* This function takes an integer value in the range 0 - 0x7fffffff
 294 and encodes it as a UTF-8 character in 0 to 6 bytes.
 295
 296 Arguments:
 297   cvalue     the character value
 298   buffer     pointer to buffer for result - at least 6 bytes long
 299
 300 Returns:     number of characters placed in the buffer
 301 */
 302
 303 static int
 304 ord2utf8(int cvalue, uschar *buffer)
 305 {
 306 register int i, j;
 307 for (i = 0; i < sizeof(utf8_table1)/sizeof(int); i++)
 308   if (cvalue <= utf8_table1[i]) break;
 309 *buffer++ = utf8_table2[i] | (cvalue & utf8_table3[i]);
 310 cvalue >>= 6 - i;
 311 for (j = 0; j < i; j++)
 312   {
 313   *buffer++ = 0x80 | (cvalue & 0x3f);
 314   cvalue >>= 6;
 315   }
 316 return i + 1;
 317 }
 318 #endif
 319
 320
 321
 322 /*************************************************
 323 *          Return version string                 *
 324 *************************************************/
 325
 326 #define STRING(a)  # a
 327 #define XSTRING(s) STRING(s)
 328
 329 const char *
 330 pcre_version(void)
 331 {
 332 return XSTRING(PCRE_MAJOR) "." XSTRING(PCRE_MINOR) " " XSTRING(PCRE_DATE);
 333 }
 334
 335
 336
 337
 338 /*************************************************
 339 * (Obsolete) Return info about compiled pattern  *
 340 *************************************************/
 341
 342 /* This is the original "info" function. It picks potentially useful data out
 343 of the private structure, but its interface was too rigid. It remains for
 344 backwards compatibility. The public options are passed back in an int - though
 345 the re->options field has been expanded to a long int, all the public options
 346 at the low end of it, and so even on 16-bit systems this will still be OK.
 347 Therefore, I haven't changed the API for pcre_info().
 348
 349 Arguments:
 350   external_re   points to compiled code
 351   optptr        where to pass back the options
 352   first_char    where to pass back the first character,
 353                 or -1 if multiline and all branches start ^,
 354                 or -2 otherwise
 355
 356 Returns:        number of capturing subpatterns
 357                 or negative values on error
 358 */
 359
 360 int
 361 pcre_info(const pcre *external_re, int *optptr, int *first_char)
 362 {
 363 const real_pcre *re = (const real_pcre *)external_re;
 364 if (re == NULL) return PCRE_ERROR_NULL;
 365 if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
 366 if (optptr != NULL) *optptr = (int)(re->options & PUBLIC_OPTIONS);
 367 if (first_char != NULL)
 368   *first_char = ((re->options & PCRE_FIRSTSET) != 0)? re->first_char :
 369      ((re->options & PCRE_STARTLINE) != 0)? -1 : -2;
 370 return re->top_bracket;
 371 }
 372
 373
 374
 375 /*************************************************
 376 *        Return info about compiled pattern      *
 377 *************************************************/
 378
 379 /* This is a newer "info" function which has an extensible interface so
 380 that additional items can be added compatibly.
 381
 382 Arguments:
 383   external_re      points to compiled code
 384   external_study   points to study data, or NULL
 385   what             what information is required
 386   where            where to put the information
 387
 388 Returns:           0 if data returned, negative on error
 389 */
 390
 391 int
 392 pcre_fullinfo(const pcre *external_re, const pcre_extra *study_data, int what,
 393   void *where)
 394 {
 395 const real_pcre *re = (const real_pcre *)external_re;
 396 const real_pcre_extra *study = (const real_pcre_extra *)study_data;
 397
 398 if (re == NULL || where == NULL) return PCRE_ERROR_NULL;
 399 if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
 400
 401 switch (what)
 402   {
 403   case PCRE_INFO_OPTIONS:
 404   *((unsigned long int *)where) = re->options & PUBLIC_OPTIONS;
 405   break;
 406
 407   case PCRE_INFO_SIZE:
 408   *((size_t *)where) = re->size;
 409   break;
 410
 411   case PCRE_INFO_CAPTURECOUNT:
 412   *((int *)where) = re->top_bracket;
 413   break;
 414
 415   case PCRE_INFO_BACKREFMAX:
 416   *((int *)where) = re->top_backref;
 417   break;
 418
 419   case PCRE_INFO_FIRSTCHAR:
 420   *((int *)where) =
 421     ((re->options & PCRE_FIRSTSET) != 0)? re->first_char :
 422     ((re->options & PCRE_STARTLINE) != 0)? -1 : -2;
 423   break;
 424
 425   case PCRE_INFO_FIRSTTABLE:
 426   *((const uschar **)where) =
 427     (study != NULL && (study->options & PCRE_STUDY_MAPPED) != 0)?
 428       study->start_bits : NULL;
 429   break;
 430
 431   case PCRE_INFO_LASTLITERAL:
 432   *((int *)where) =
 433     ((re->options & PCRE_REQCHSET) != 0)? re->req_char : -1;
 434   break;
 435
 436   default: return PCRE_ERROR_BADOPTION;
 437   }
 438
 439 return 0;
 440 }
 441
 442
 443
 444 #ifdef DEBUG
 445 /*************************************************
 446 *        Debugging function to print chars       *
 447 *************************************************/
 448
 449 /* Print a sequence of chars in printable format, stopping at the end of the
 450 subject if the requested.
 451
 452 Arguments:
 453   p           points to characters
 454   length      number to print
 455   is_subject  TRUE if printing from within md->start_subject
 456   md          pointer to matching data block, if is_subject is TRUE
 457
 458 Returns:     nothing
 459 */
 460
 461 static void
 462 pchars(const uschar *p, int length, BOOL is_subject, match_data *md)
 463 {
 464 int c;
 465 if (is_subject && length > md->end_subject - p) length = md->end_subject - p;
 466 while (length-- > 0)
 467   if (isprint(c = *(p++))) printf("%c", c); else printf("\\x%02x", c);
 468 }
 469 #endif
 470
 471
 472
 473
 474 /*************************************************
 475 *            Handle escapes                      *
 476 *************************************************/
 477
 478 /* This function is called when a \ has been encountered. It either returns a
 479 positive value for a simple escape such as \n, or a negative value which
 480 encodes one of the more complicated things such as \d. When UTF-8 is enabled,
 481 a positive value greater than 255 may be returned. On entry, ptr is pointing at
 482 the \. On exit, it is on the final character of the escape sequence.
 483
 484 Arguments:
 485   ptrptr     points to the pattern position pointer
 486   errorptr   points to the pointer to the error message
 487   bracount   number of previous extracting brackets
 488   options    the options bits
 489   isclass    TRUE if inside a character class
 490   cd         pointer to char tables block
 491
 492 Returns:     zero or positive => a data character
 493              negative => a special escape sequence
 494              on error, errorptr is set
 495 */
 496
 497 static int
 498 check_escape(const uschar **ptrptr, const char **errorptr, int bracount,
 499   int options, BOOL isclass, compile_data *cd)
 500 {
 501 const uschar *ptr = *ptrptr;
 502 int c, i;
 503
 504 /* If backslash is at the end of the pattern, it's an error. */
 505
 506 c = *(++ptr);
 507 if (c == 0) *errorptr = ERR1;
 508
 509 /* Digits or letters may have special meaning; all others are literals. */
 510
 511 else if (c < '0' || c > 'z') {}
 512
 513 /* Do an initial lookup in a table. A non-zero result is something that can be
 514 returned immediately. Otherwise further processing may be required. */
 515
 516 else if ((i = escapes[c - '0']) != 0) c = i;
 517
 518 /* Escapes that need further processing, or are illegal. */
 519
 520 else
 521   {
 522   const uschar *oldptr;
 523   switch (c)
 524     {
 525     /* The handling of escape sequences consisting of a string of digits
 526     starting with one that is not zero is not straightforward. By experiment,
 527     the way Perl works seems to be as follows:
 528
 529     Outside a character class, the digits are read as a decimal number. If the
 530     number is less than 10, or if there are that many previous extracting
 531     left brackets, then it is a back reference. Otherwise, up to three octal
 532     digits are read to form an escaped byte. Thus \123 is likely to be octal
 533     123 (cf \0123, which is octal 012 followed by the literal 3). If the octal
 534     value is greater than 377, the least significant 8 bits are taken. Inside a
 535     character class, \ followed by a digit is always an octal number. */
 536
 537     case '1': case '2': case '3': case '4': case '5':
 538     case '6': case '7': case '8': case '9':
 539
 540     if (!isclass)
 541       {
 542       oldptr = ptr;
 543       c -= '0';
 544       while ((cd->ctypes[ptr[1]] & ctype_digit) != 0)
 545         c = c * 10 + *(++ptr) - '0';
 546       if (c < 10 || c <= bracount)
 547         {
 548         c = -(ESC_REF + c);
 549         break;
 550         }
 551       ptr = oldptr;      /* Put the pointer back and fall through */
 552       }
 553
 554     /* Handle an octal number following \. If the first digit is 8 or 9, Perl
 555     generates a binary zero byte and treats the digit as a following literal.
 556     Thus we have to pull back the pointer by one. */
 557
 558     if ((c = *ptr) >= '8')
 559       {
 560       ptr--;
 561       c = 0;
 562       break;
 563       }
 564
 565     /* \0 always starts an octal number, but we may drop through to here with a
 566     larger first octal digit. */
 567
 568     case '0':
 569     c -= '0';
 570     while(i++ < 2 && (cd->ctypes[ptr[1]] & ctype_digit) != 0 &&
 571       ptr[1] != '8' && ptr[1] != '9')
 572         c = c * 8 + *(++ptr) - '0';
 573     c &= 255;     /* Take least significant 8 bits */
 574     break;
 575
 576     /* \x is complicated when UTF-8 is enabled. \x{ddd} is a character number
 577     which can be greater than 0xff, but only if the ddd are hex digits. */
 578
 579     case 'x':
 580 #ifdef SUPPORT_UTF8
 581     if (ptr[1] == '{' && (options & PCRE_UTF8) != 0)
 582       {
 583       const uschar *pt = ptr + 2;
 584       register int count = 0;
 585       c = 0;
 586       while ((cd->ctypes[*pt] & ctype_xdigit) != 0)
 587         {
 588         count++;
 589         c = c * 16 + cd->lcc[*pt] -
 590           (((cd->ctypes[*pt] & ctype_digit) != 0)? '0' : 'W');
 591         pt++;
 592         }
 593       if (*pt == '}')
 594         {
 595         if (c < 0 || count > 8) *errorptr = ERR34;
 596         ptr = pt;
 597         break;
 598         }
 599       /* If the sequence of hex digits does not end with '}', then we don't
 600       recognize this construct; fall through to the normal \x handling. */
 601       }
 602 #endif
 603
 604     /* Read just a single hex char */
 605
 606     c = 0;
 607     while (i++ < 2 && (cd->ctypes[ptr[1]] & ctype_xdigit) != 0)
 608       {
 609       ptr++;
 610       c = c * 16 + cd->lcc[*ptr] -
 611         (((cd->ctypes[*ptr] & ctype_digit) != 0)? '0' : 'W');
 612       }
 613     break;
 614
 615     /* Other special escapes not starting with a digit are straightforward */
 616
 617     case 'c':
 618     c = *(++ptr);
 619     if (c == 0)
 620       {
 621       *errorptr = ERR2;
 622       return 0;
 623       }
 624
 625     /* A letter is upper-cased; then the 0x40 bit is flipped */
 626
 627     if (c >= 'a' && c <= 'z') c = cd->fcc[c];
 628     c ^= 0x40;
 629     break;
 630
 631     /* PCRE_EXTRA enables extensions to Perl in the matter of escapes. Any
 632     other alphameric following \ is an error if PCRE_EXTRA was set; otherwise,
 633     for Perl compatibility, it is a literal. This code looks a bit odd, but
 634     there used to be some cases other than the default, and there may be again
 635     in future, so I haven't "optimized" it. */
 636
 637     default:
 638     if ((options & PCRE_EXTRA) != 0) switch(c)
 639       {
 640       default:
 641       *errorptr = ERR3;
 642       break;
 643       }
 644     break;
 645     }
 646   }
 647
 648 *ptrptr = ptr;
 649 return c;
 650 }
 651
 652
 653
 654 /*************************************************
 655 *            Check for counted repeat            *
 656 *************************************************/
 657
 658 /* This function is called when a '{' is encountered in a place where it might
 659 start a quantifier. It looks ahead to see if it really is a quantifier or not.
 660 It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd}
 661 where the ddds are digits.
 662
 663 Arguments:
 664   p         pointer to the first char after '{'
 665   cd        pointer to char tables block
 666
 667 Returns:    TRUE or FALSE
 668 */
 669
 670 static BOOL
 671 is_counted_repeat(const uschar *p, compile_data *cd)
 672 {
 673 if ((cd->ctypes[*p++] & ctype_digit) == 0) return FALSE;
 674 while ((cd->ctypes[*p] & ctype_digit) != 0) p++;
 675 if (*p == '}') return TRUE;
 676
 677 if (*p++ != ',') return FALSE;
 678 if (*p == '}') return TRUE;
 679
 680 if ((cd->ctypes[*p++] & ctype_digit) == 0) return FALSE;
 681 while ((cd->ctypes[*p] & ctype_digit) != 0) p++;
 682 return (*p == '}');
 683 }
 684
 685
 686
 687 /*************************************************
 688 *         Read repeat counts                     *
 689 *************************************************/
 690
 691 /* Read an item of the form {n,m} and return the values. This is called only
 692 after is_counted_repeat() has confirmed that a repeat-count quantifier exists,
 693 so the syntax is guaranteed to be correct, but we need to check the values.
 694
 695 Arguments:
 696   p          pointer to first char after '{'
 697   minp       pointer to int for min
 698   maxp       pointer to int for max
 699              returned as -1 if no max
 700   errorptr   points to pointer to error message
 701   cd         pointer to character tables clock
 702
 703 Returns:     pointer to '}' on success;
 704              current ptr on error, with errorptr set
 705 */
 706
 707 static const uschar *
 708 read_repeat_counts(const uschar *p, int *minp, int *maxp,
 709   const char **errorptr, compile_data *cd)
 710 {
 711 int min = 0;
 712 int max = -1;
 713
 714 while ((cd->ctypes[*p] & ctype_digit) != 0) min = min * 10 + *p++ - '0';
 715
 716 if (*p == '}') max = min; else
 717   {
 718   if (*(++p) != '}')
 719     {
 720     max = 0;
 721     while((cd->ctypes[*p] & ctype_digit) != 0) max = max * 10 + *p++ - '0';
 722     if (max < min)
 723       {
 724       *errorptr = ERR4;
 725       return p;
 726       }
 727     }
 728   }
 729
 730 /* Do paranoid checks, then fill in the required variables, and pass back the
 731 pointer to the terminating '}'. */
 732
 733 if (min > 65535 || max > 65535)
 734   *errorptr = ERR5;
 735 else
 736   {
 737   *minp = min;
 738   *maxp = max;
 739   }
 740 return p;
 741 }
 742
 743
 744
 745 /*************************************************
 746 *        Find the fixed length of a pattern      *
 747 *************************************************/
 748
 749 /* Scan a pattern and compute the fixed length of subject that will match it,
 750 if the length is fixed. This is needed for dealing with backward assertions.
 751
 752 Arguments:
 753   code     points to the start of the pattern (the bracket)
 754   options  the compiling options
 755
 756 Returns:   the fixed length, or -1 if there is no fixed length
 757 */
 758
 759 static int
 760 find_fixedlength(uschar *code, int options)
 761 {
 762 int length = -1;
 763
 764 register int branchlength = 0;
 765 register uschar *cc = code + 3;
 766
 767 /* Scan along the opcodes for this branch. If we get to the end of the
 768 branch, check the length against that of the other branches. */
 769
 770 for (;;)
 771   {
 772   int d;
 773   register int op = *cc;
 774   if (op >= OP_BRA) op = OP_BRA;
 775
 776   switch (op)
 777     {
 778     case OP_BRA:
 779     case OP_ONCE:
 780     case OP_COND:
 781     d = find_fixedlength(cc, options);
 782     if (d < 0) return -1;
 783     branchlength += d;
 784     do cc += (cc[1] << 8) + cc[2]; while (*cc == OP_ALT);
 785     cc += 3;
 786     break;
 787
 788     /* Reached end of a branch; if it's a ket it is the end of a nested
 789     call. If it's ALT it is an alternation in a nested call. If it is
 790     END it's the end of the outer call. All can be handled by the same code. */
 791
 792     case OP_ALT:
 793     case OP_KET:
 794     case OP_KETRMAX:
 795     case OP_KETRMIN:
 796     case OP_END:
 797     if (length < 0) length = branchlength;
 798       else if (length != branchlength) return -1;
 799     if (*cc != OP_ALT) return length;
 800     cc += 3;
 801     branchlength = 0;
 802     break;
 803
 804     /* Skip over assertive subpatterns */
 805
 806     case OP_ASSERT:
 807     case OP_ASSERT_NOT:
 808     case OP_ASSERTBACK:
 809     case OP_ASSERTBACK_NOT:
 810     do cc += (cc[1] << 8) + cc[2]; while (*cc == OP_ALT);
 811     cc += 3;
 812     break;
 813
 814     /* Skip over things that don't match chars */
 815
 816     case OP_REVERSE:
 817     cc++;
 818     /* Fall through */
 819
 820     case OP_CREF:
 821     case OP_OPT:
 822     cc++;
 823     /* Fall through */
 824
 825     case OP_SOD:
 826     case OP_EOD:
 827     case OP_EODN:
 828     case OP_CIRC:
 829     case OP_DOLL:
 830     case OP_NOT_WORD_BOUNDARY:
 831     case OP_WORD_BOUNDARY:
 832     cc++;
 833     break;
 834
 835     /* Handle char strings. In UTF-8 mode we must count characters, not bytes.
 836     This requires a scan of the string, unfortunately. We assume valid UTF-8
 837     strings, so all we do is reduce the length by one for byte whose bits are
 838     10xxxxxx. */
 839
 840     case OP_CHARS:
 841     branchlength += *(++cc);
 842 #ifdef SUPPORT_UTF8
 843     for (d = 1; d <= *cc; d++)
 844       if ((cc[d] & 0xc0) == 0x80) branchlength--;
 845 #endif
 846     cc += *cc + 1;
 847     break;
 848
 849     /* Handle exact repetitions */
 850
 851     case OP_EXACT:
 852     case OP_TYPEEXACT:
 853     branchlength += (cc[1] << 8) + cc[2];
 854     cc += 4;
 855     break;
 856
 857     /* Handle single-char matchers */
 858
 859     case OP_NOT_DIGIT:
 860     case OP_DIGIT:
 861     case OP_NOT_WHITESPACE:
 862     case OP_WHITESPACE:
 863     case OP_NOT_WORDCHAR:
 864     case OP_WORDCHAR:
 865     case OP_ANY:
 866     branchlength++;
 867     cc++;
 868     break;
 869
 870
 871     /* Check a class for variable quantification */
 872
 873     case OP_CLASS:
 874     cc += (*cc == OP_REF)? 2 : 33;
 875
 876     switch (*cc)
 877       {
 878       case OP_CRSTAR:
 879       case OP_CRMINSTAR:
 880       case OP_CRQUERY:
 881       case OP_CRMINQUERY:
 882       return -1;
 883
 884       case OP_CRRANGE:
 885       case OP_CRMINRANGE:
 886       if ((cc[1] << 8) + cc[2] != (cc[3] << 8) + cc[4]) return -1;
 887       branchlength += (cc[1] << 8) + cc[2];
 888       cc += 5;
 889       break;
 890
 891       default:
 892       branchlength++;
 893       }
 894     break;
 895
 896     /* Anything else is variable length */
 897
 898     default:
 899     return -1;
 900     }
 901   }
 902 /* Control never gets here */
 903 }
 904
 905
 906
 907
 908 /*************************************************
 909 *           Check for POSIX class syntax         *
 910 *************************************************/
 911
 912 /* This function is called when the sequence "[:" or "[." or "[=" is
 913 encountered in a character class. It checks whether this is followed by an
 914 optional ^ and then a sequence of letters, terminated by a matching ":]" or
 915 ".]" or "=]".
 916
 917 Argument:
 918   ptr      pointer to the initial [
 919   endptr   where to return the end pointer
 920   cd       pointer to compile data
 921
 922 Returns:   TRUE or FALSE
 923 */
 924
 925 static BOOL
 926 check_posix_syntax(const uschar *ptr, const uschar **endptr, compile_data *cd)
 927 {
 928 int terminator;          /* Don't combine these lines; the Solaris cc */
 929 terminator = *(++ptr);   /* compiler warns about "non-constant" initializer. */
 930 if (*(++ptr) == '^') ptr++;
 931 while ((cd->ctypes[*ptr] & ctype_letter) != 0) ptr++;
 932 if (*ptr == terminator && ptr[1] == ']')
 933   {
 934   *endptr = ptr;
 935   return TRUE;
 936   }
 937 return FALSE;
 938 }
 939
 940
 941
 942
 943 /*************************************************
 944 *          Check POSIX class name                *
 945 *************************************************/
 946
 947 /* This function is called to check the name given in a POSIX-style class entry
 948 such as [:alnum:].
 949
 950 Arguments:
 951   ptr        points to the first letter
 952   len        the length of the name
 953
 954 Returns:     a value representing the name, or -1 if unknown
 955 */
 956
 957 static int
 958 check_posix_name(const uschar *ptr, int len)
 959 {
 960 register int yield = 0;
 961 while (posix_name_lengths[yield] != 0)
 962   {
 963   if (len == posix_name_lengths[yield] &&
 964     strncmp((const char *)ptr, posix_names[yield], len) == 0) return yield;
 965   yield++;
 966   }
 967 return -1;
 968 }
 969
 970
 971
 972
 973 /*************************************************
 974 *           Compile one branch                   *
 975 *************************************************/
 976
 977 /* Scan the pattern, compiling it into the code vector.
 978
 979 Arguments:
 980   options      the option bits
 981   brackets     points to number of brackets used
 982   code         points to the pointer to the current code point
 983   ptrptr       points to the current pattern pointer
 984   errorptr     points to pointer to error message
 985   optchanged   set to the value of the last OP_OPT item compiled
 986   reqchar      set to the last literal character required, else -1
 987   countlits    set to count of mandatory literal characters
 988   cd           contains pointers to tables
 989
 990 Returns:       TRUE on success
 991                FALSE, with *errorptr set on error
 992 */
 993
 994 static BOOL
 995 compile_branch(int options, int *brackets, uschar **codeptr,
 996   const uschar **ptrptr, const char **errorptr, int *optchanged,
 997   int *reqchar, int *countlits, compile_data *cd)
 998 {
 999 int repeat_type, op_type;
1000 int repeat_min, repeat_max;
1001 int bravalue, length;
1002 int greedy_default, greedy_non_default;
1003 int prevreqchar;
1004 int condcount = 0;
1005 int subcountlits = 0;
1006 register int c;
1007 register uschar *code = *codeptr;
1008 uschar *tempcode;
1009 const uschar *ptr = *ptrptr;
1010 const uschar *tempptr;
1011 uschar *previous = NULL;
1012 uschar class[32];
1013
1014 /* Set up the default and non-default settings for greediness */
1015
1016 greedy_default = ((options & PCRE_UNGREEDY) != 0);
1017 greedy_non_default = greedy_default ^ 1;
1018
1019 /* Initialize no required char, and count of literals */
1020
1021 *reqchar = prevreqchar = -1;
1022 *countlits = 0;
1023
1024 /* Switch on next character until the end of the branch */
1025
1026 for (;; ptr++)
1027   {
1028   BOOL negate_class;
1029   int class_charcount;
1030   int class_lastchar;
1031   int newoptions;
1032   int condref;
1033   int subreqchar;
1034
1035   c = *ptr;
1036   if ((options & PCRE_EXTENDED) != 0)
1037     {
1038     if ((cd->ctypes[c] & ctype_space) != 0) continue;
1039     if (c == '#')
1040       {
1041       /* The space before the ; is to avoid a warning on a silly compiler
1042       on the Macintosh. */
1043       while ((c = *(++ptr)) != 0 && c != '\n') ;
1044       continue;
1045       }
1046     }
1047
1048   switch(c)
1049     {
1050     /* The branch terminates at end of string, |, or ). */
1051
1052     case 0:
1053     case '|':
1054     case ')':
1055     *codeptr = code;
1056     *ptrptr = ptr;
1057     return TRUE;
1058
1059     /* Handle single-character metacharacters */
1060
1061     case '^':
1062     previous = NULL;
1063     *code++ = OP_CIRC;
1064     break;
1065
1066     case '$':
1067     previous = NULL;
1068     *code++ = OP_DOLL;
1069     break;
1070
1071     case '.':
1072     previous = code;
1073     *code++ = OP_ANY;
1074     break;
1075
1076     /* Character classes. These always build a 32-byte bitmap of the permitted
1077     characters, except in the special case where there is only one character.
1078     For negated classes, we build the map as usual, then invert it at the end.
1079     */
1080
1081     case '[':
1082     previous = code;
1083     *code++ = OP_CLASS;
1084
1085     /* If the first character is '^', set the negation flag and skip it. */
1086
1087     if ((c = *(++ptr)) == '^')
1088       {
1089       negate_class = TRUE;
1090       c = *(++ptr);
1091       }
1092     else negate_class = FALSE;
1093
1094     /* Keep a count of chars so that we can optimize the case of just a single
1095     character. */
1096
1097     class_charcount = 0;
1098     class_lastchar = -1;
1099
1100     /* Initialize the 32-char bit map to all zeros. We have to build the
1101     map in a temporary bit of store, in case the class contains only 1
1102     character, because in that case the compiled code doesn't use the
1103     bit map. */
1104
1105     memset(class, 0, 32 * sizeof(uschar));
1106
1107     /* Process characters until ] is reached. By writing this as a "do" it
1108     means that an initial ] is taken as a data character. */
1109
1110     do
1111       {
1112       if (c == 0)
1113         {
1114         *errorptr = ERR6;
1115         goto FAILED;
1116         }
1117
1118       /* Handle POSIX class names. Perl allows a negation extension of the
1119       form [:^name]. A square bracket that doesn't match the syntax is
1120       treated as a literal. We also recognize the POSIX constructions
1121       [.ch.] and [=ch=] ("collating elements") and fault them, as Perl
1122       5.6 does. */
1123
1124       if (c == '[' &&
1125           (ptr[1] == ':' || ptr[1] == '.' || ptr[1] == '=') &&
1126           check_posix_syntax(ptr, &tempptr, cd))
1127         {
1128         BOOL local_negate = FALSE;
1129         int posix_class, i;
1130         register const uschar *cbits = cd->cbits;
1131
1132         if (ptr[1] != ':')
1133           {
1134           *errorptr = ERR31;
1135           goto FAILED;
1136           }
1137
1138         ptr += 2;
1139         if (*ptr == '^')
1140           {
1141           local_negate = TRUE;
1142           ptr++;
1143           }
1144
1145         posix_class = check_posix_name(ptr, tempptr - ptr);
1146         if (posix_class < 0)
1147           {
1148           *errorptr = ERR30;
1149           goto FAILED;
1150           }
1151
1152         /* If matching is caseless, upper and lower are converted to
1153         alpha. This relies on the fact that the class table starts with
1154         alpha, lower, upper as the first 3 entries. */
1155
1156         if ((options & PCRE_CASELESS) != 0 && posix_class <= 2)
1157           posix_class = 0;
1158
1159         /* Or into the map we are building up to 3 of the static class
1160         tables, or their negations. */
1161
1162         posix_class *= 3;
1163         for (i = 0; i < 3; i++)
1164           {
1165           int taboffset = posix_class_maps[posix_class + i];
1166           if (taboffset < 0) break;
1167           if (local_negate)
1168             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+taboffset];
1169           else
1170             for (c = 0; c < 32; c++) class[c] |= cbits[c+taboffset];
1171           }
1172
1173         ptr = tempptr + 1;
1174         class_charcount = 10;  /* Set > 1; assumes more than 1 per class */
1175         continue;
1176         }
1177
1178       /* Backslash may introduce a single character, or it may introduce one
1179       of the specials, which just set a flag. Escaped items are checked for
1180       validity in the pre-compiling pass. The sequence \b is a special case.
1181       Inside a class (and only there) it is treated as backspace. Elsewhere
1182       it marks a word boundary. Other escapes have preset maps ready to
1183       or into the one we are building. We assume they have more than one
1184       character in them, so set class_count bigger than one. */
1185
1186       if (c == '\\')
1187         {
1188         c = check_escape(&ptr, errorptr, *brackets, options, TRUE, cd);
1189         if (-c == ESC_b) c = '\b';
1190         else if (c < 0)
1191           {
1192           register const uschar *cbits = cd->cbits;
1193           class_charcount = 10;
1194           switch (-c)
1195             {
1196             case ESC_d:
1197             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_digit];
1198             continue;
1199
1200             case ESC_D:
1201             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_digit];
1202             continue;
1203
1204             case ESC_w:
1205             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_word];
1206             continue;
1207
1208             case ESC_W:
1209             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_word];
1210             continue;
1211
1212             case ESC_s:
1213             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_space];
1214             continue;
1215
1216             case ESC_S:
1217             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_space];
1218             continue;
1219
1220             default:
1221             *errorptr = ERR7;
1222             goto FAILED;
1223             }
1224           }
1225
1226         /* Fall through if single character, but don't at present allow
1227         chars > 255 in UTF-8 mode. */
1228
1229 #ifdef SUPPORT_UTF8
1230         if (c > 255)
1231           {
1232           *errorptr = ERR33;
1233           goto FAILED;
1234           }
1235 #endif
1236         }
1237
1238       /* A single character may be followed by '-' to form a range. However,
1239       Perl does not permit ']' to be the end of the range. A '-' character
1240       here is treated as a literal. */
1241
1242       if (ptr[1] == '-' && ptr[2] != ']')
1243         {
1244         int d;
1245         ptr += 2;
1246         d = *ptr;
1247
1248         if (d == 0)
1249           {
1250           *errorptr = ERR6;
1251           goto FAILED;
1252           }
1253
1254         /* The second part of a range can be a single-character escape, but
1255         not any of the other escapes. Perl 5.6 treats a hyphen as a literal
1256         in such circumstances. */
1257
1258         if (d == '\\')
1259           {
1260           const uschar *oldptr = ptr;
1261           d = check_escape(&ptr, errorptr, *brackets, options, TRUE, cd);
1262
1263 #ifdef SUPPORT_UTF8
1264           if (d > 255)
1265             {
1266             *errorptr = ERR33;
1267             goto FAILED;
1268             }
1269 #endif
1270           /* \b is backslash; any other special means the '-' was literal */
1271
1272           if (d < 0)
1273             {
1274             if (d == -ESC_b) d = '\b'; else
1275               {
1276               ptr = oldptr - 2;
1277               goto SINGLE_CHARACTER;  /* A few lines below */
1278               }
1279             }
1280           }
1281
1282         if (d < c)
1283           {
1284           *errorptr = ERR8;
1285           goto FAILED;
1286           }
1287
1288         for (; c <= d; c++)
1289           {
1290           class[c/8] |= (1 << (c&7));
1291           if ((options & PCRE_CASELESS) != 0)
1292             {
1293             int uc = cd->fcc[c];           /* flip case */
1294             class[uc/8] |= (1 << (uc&7));
1295             }
1296           class_charcount++;                /* in case a one-char range */
1297           class_lastchar = c;
1298           }
1299         continue;   /* Go get the next char in the class */
1300         }
1301
1302       /* Handle a lone single character - we can get here for a normal
1303       non-escape char, or after \ that introduces a single character. */
1304
1305       SINGLE_CHARACTER:
1306
1307       class [c/8] |= (1 << (c&7));
1308       if ((options & PCRE_CASELESS) != 0)
1309         {
1310         c = cd->fcc[c];   /* flip case */
1311         class[c/8] |= (1 << (c&7));
1312         }
1313       class_charcount++;
1314       class_lastchar = c;
1315       }
1316
1317     /* Loop until ']' reached; the check for end of string happens inside the
1318     loop. This "while" is the end of the "do" above. */
1319
1320     while ((c = *(++ptr)) != ']');
1321
1322     /* If class_charcount is 1 and class_lastchar is not negative, we saw
1323     precisely one character. This doesn't need the whole 32-byte bit map.
1324     We turn it into a 1-character OP_CHAR if it's positive, or OP_NOT if
1325     it's negative. */
1326
1327     if (class_charcount == 1 && class_lastchar >= 0)
1328       {
1329       if (negate_class)
1330         {
1331         code[-1] = OP_NOT;
1332         }
1333       else
1334         {
1335         code[-1] = OP_CHARS;
1336         *code++ = 1;
1337         }
1338       *code++ = class_lastchar;
1339       }
1340
1341     /* Otherwise, negate the 32-byte map if necessary, and copy it into
1342     the code vector. */
1343
1344     else
1345       {
1346       if (negate_class)
1347         for (c = 0; c < 32; c++) code[c] = ~class[c];
1348       else
1349         memcpy(code, class, 32);
1350       code += 32;
1351       }
1352     break;
1353
1354     /* Various kinds of repeat */
1355
1356     case '{':
1357     if (!is_counted_repeat(ptr+1, cd)) goto NORMAL_CHAR;
1358     ptr = read_repeat_counts(ptr+1, &repeat_min, &repeat_max, errorptr, cd);
1359     if (*errorptr != NULL) goto FAILED;
1360     goto REPEAT;
1361
1362     case '*':
1363     repeat_min = 0;
1364     repeat_max = -1;
1365     goto REPEAT;
1366
1367     case '+':
1368     repeat_min = 1;
1369     repeat_max = -1;
1370     goto REPEAT;
1371
1372     case '?':
1373     repeat_min = 0;
1374     repeat_max = 1;
1375
1376     REPEAT:
1377     if (previous == NULL)
1378       {
1379       *errorptr = ERR9;
1380       goto FAILED;
1381       }
1382
1383     /* If the next character is '?' this is a minimizing repeat, by default,
1384     but if PCRE_UNGREEDY is set, it works the other way round. Advance to the
1385     next character. */
1386
1387     if (ptr[1] == '?')
1388       { repeat_type = greedy_non_default; ptr++; }
1389     else repeat_type = greedy_default;
1390
1391     /* If previous was a string of characters, chop off the last one and use it
1392     as the subject of the repeat. If there was only one character, we can
1393     abolish the previous item altogether. A repeat with a zero minimum wipes
1394     out any reqchar setting, backing up to the previous value. We must also
1395     adjust the countlits value. */
1396
1397     if (*previous == OP_CHARS)
1398       {
1399       int len = previous[1];
1400
1401       if (repeat_min == 0) *reqchar = prevreqchar;
1402       *countlits += repeat_min - 1;
1403
1404       if (len == 1)
1405         {
1406         c = previous[2];
1407         code = previous;
1408         }
1409       else
1410         {
1411         c = previous[len+1];
1412         previous[1]--;
1413         code--;
1414         }
1415       op_type = 0;                 /* Use single-char op codes */
1416       goto OUTPUT_SINGLE_REPEAT;   /* Code shared with single character types */
1417       }
1418
1419     /* If previous was a single negated character ([^a] or similar), we use
1420     one of the special opcodes, replacing it. The code is shared with single-
1421     character repeats by adding a suitable offset into repeat_type. */
1422
1423     else if ((int)*previous == OP_NOT)
1424       {
1425       op_type = OP_NOTSTAR - OP_STAR;  /* Use "not" opcodes */
1426       c = previous[1];
1427       code = previous;
1428       goto OUTPUT_SINGLE_REPEAT;
1429       }
1430
1431     /* If previous was a character type match (\d or similar), abolish it and
1432     create a suitable repeat item. The code is shared with single-character
1433     repeats by adding a suitable offset into repeat_type. */
1434
1435     else if ((int)*previous < OP_EODN || *previous == OP_ANY)
1436       {
1437       op_type = OP_TYPESTAR - OP_STAR;  /* Use type opcodes */
1438       c = *previous;
1439       code = previous;
1440
1441       OUTPUT_SINGLE_REPEAT:
1442
1443       /* If the maximum is zero then the minimum must also be zero; Perl allows
1444       this case, so we do too - by simply omitting the item altogether. */
1445
1446       if (repeat_max == 0) goto END_REPEAT;
1447
1448       /* Combine the op_type with the repeat_type */
1449
1450       repeat_type += op_type;
1451
1452       /* A minimum of zero is handled either as the special case * or ?, or as
1453       an UPTO, with the maximum given. */
1454
1455       if (repeat_min == 0)
1456         {
1457         if (repeat_max == -1) *code++ = OP_STAR + repeat_type;
1458           else if (repeat_max == 1) *code++ = OP_QUERY + repeat_type;
1459         else
1460           {
1461           *code++ = OP_UPTO + repeat_type;
1462           *code++ = repeat_max >> 8;
1463           *code++ = (repeat_max & 255);
1464           }
1465         }
1466
1467       /* The case {1,} is handled as the special case + */
1468
1469       else if (repeat_min == 1 && repeat_max == -1)
1470         *code++ = OP_PLUS + repeat_type;
1471
1472       /* The case {n,n} is just an EXACT, while the general case {n,m} is
1473       handled as an EXACT followed by an UPTO. An EXACT of 1 is optimized. */
1474
1475       else
1476         {
1477         if (repeat_min != 1)
1478           {
1479           *code++ = OP_EXACT + op_type;  /* NB EXACT doesn't have repeat_type */
1480           *code++ = repeat_min >> 8;
1481           *code++ = (repeat_min & 255);
1482           }
1483
1484         /* If the mininum is 1 and the previous item was a character string,
1485         we either have to put back the item that got cancelled if the string
1486         length was 1, or add the character back onto the end of a longer
1487         string. For a character type nothing need be done; it will just get
1488         put back naturally. Note that the final character is always going to
1489         get added below. */
1490
1491         else if (*previous == OP_CHARS)
1492           {
1493           if (code == previous) code += 2; else previous[1]++;
1494           }
1495
1496         /*  For a single negated character we also have to put back the
1497         item that got cancelled. */
1498
1499         else if (*previous == OP_NOT) code++;
1500
1501         /* If the maximum is unlimited, insert an OP_STAR. */
1502
1503         if (repeat_max < 0)
1504           {
1505           *code++ = c;
1506           *code++ = OP_STAR + repeat_type;
1507           }
1508
1509         /* Else insert an UPTO if the max is greater than the min. */
1510
1511         else if (repeat_max != repeat_min)
1512           {
1513           *code++ = c;
1514           repeat_max -= repeat_min;
1515           *code++ = OP_UPTO + repeat_type;
1516           *code++ = repeat_max >> 8;
1517           *code++ = (repeat_max & 255);
1518           }
1519         }
1520
1521       /* The character or character type itself comes last in all cases. */
1522
1523       *code++ = c;
1524       }
1525
1526     /* If previous was a character class or a back reference, we put the repeat
1527     stuff after it, but just skip the item if the repeat was {0,0}. */
1528
1529     else if (*previous == OP_CLASS || *previous == OP_REF)
1530       {
1531       if (repeat_max == 0)
1532         {
1533         code = previous;
1534         goto END_REPEAT;
1535         }
1536       if (repeat_min == 0 && repeat_max == -1)
1537         *code++ = OP_CRSTAR + repeat_type;
1538       else if (repeat_min == 1 && repeat_max == -1)
1539         *code++ = OP_CRPLUS + repeat_type;
1540       else if (repeat_min == 0 && repeat_max == 1)
1541         *code++ = OP_CRQUERY + repeat_type;
1542       else
1543         {
1544         *code++ = OP_CRRANGE + repeat_type;
1545         *code++ = repeat_min >> 8;
1546         *code++ = repeat_min & 255;
1547         if (repeat_max == -1) repeat_max = 0;  /* 2-byte encoding for max */
1548         *code++ = repeat_max >> 8;
1549         *code++ = repeat_max & 255;
1550         }
1551       }
1552
1553     /* If previous was a bracket group, we may have to replicate it in certain
1554     cases. */
1555
1556     else if ((int)*previous >= OP_BRA || (int)*previous == OP_ONCE ||
1557              (int)*previous == OP_COND)
1558       {
1559       register int i;
1560       int ketoffset = 0;
1561       int len = code - previous;
1562       uschar *bralink = NULL;
1563
1564       /* If the maximum repeat count is unlimited, find the end of the bracket
1565       by scanning through from the start, and compute the offset back to it
1566       from the current code pointer. There may be an OP_OPT setting following
1567       the final KET, so we can't find the end just by going back from the code
1568       pointer. */
1569
1570       if (repeat_max == -1)
1571         {
1572         register uschar *ket = previous;
1573         do ket += (ket[1] << 8) + ket[2]; while (*ket != OP_KET);
1574         ketoffset = code - ket;
1575         }
1576
1577       /* The case of a zero minimum is special because of the need to stick
1578       OP_BRAZERO in front of it, and because the group appears once in the
1579       data, whereas in other cases it appears the minimum number of times. For
1580       this reason, it is simplest to treat this case separately, as otherwise
1581       the code gets far too mess. There are several special subcases when the
1582       minimum is zero. */
1583
1584       if (repeat_min == 0)
1585         {
1586         /* If we set up a required char from the bracket, we must back off
1587         to the previous value and reset the countlits value too. */
1588
1589         if (subcountlits > 0)
1590           {
1591           *reqchar = prevreqchar;
1592           *countlits -= subcountlits;
1593           }
1594
1595         /* If the maximum is also zero, we just omit the group from the output
1596         altogether. */
1597
1598         if (repeat_max == 0)
1599           {
1600           code = previous;
1601           goto END_REPEAT;
1602           }
1603
1604         /* If the maximum is 1 or unlimited, we just have to stick in the
1605         BRAZERO and do no more at this point. */
1606
1607         if (repeat_max <= 1)
1608           {
1609           memmove(previous+1, previous, len);
1610           code++;
1611           *previous++ = OP_BRAZERO + repeat_type;
1612           }
1613
1614         /* If the maximum is greater than 1 and limited, we have to replicate
1615         in a nested fashion, sticking OP_BRAZERO before each set of brackets.
1616         The first one has to be handled carefully because it's the original
1617         copy, which has to be moved up. The remainder can be handled by code
1618         that is common with the non-zero minimum case below. We just have to
1619         adjust the value or repeat_max, since one less copy is required. */
1620
1621         else
1622           {
1623           int offset;
1624           memmove(previous+4, previous, len);
1625           code += 4;
1626           *previous++ = OP_BRAZERO + repeat_type;
1627           *previous++ = OP_BRA;
1628
1629           /* We chain together the bracket offset fields that have to be
1630           filled in later when the ends of the brackets are reached. */
1631
1632           offset = (bralink == NULL)? 0 : previous - bralink;
1633           bralink = previous;
1634           *previous++ = offset >> 8;
1635           *previous++ = offset & 255;
1636           }
1637
1638         repeat_max--;
1639         }
1640
1641       /* If the minimum is greater than zero, replicate the group as many
1642       times as necessary, and adjust the maximum to the number of subsequent
1643       copies that we need. */
1644
1645       else
1646         {
1647         for (i = 1; i < repeat_min; i++)
1648           {
1649           memcpy(code, previous, len);
1650           code += len;
1651           }
1652         if (repeat_max > 0) repeat_max -= repeat_min;
1653         }
1654
1655       /* This code is common to both the zero and non-zero minimum cases. If
1656       the maximum is limited, it replicates the group in a nested fashion,
1657       remembering the bracket starts on a stack. In the case of a zero minimum,
1658       the first one was set up above. In all cases the repeat_max now specifies
1659       the number of additional copies needed. */
1660
1661       if (repeat_max >= 0)
1662         {
1663         for (i = repeat_max - 1; i >= 0; i--)
1664           {
1665           *code++ = OP_BRAZERO + repeat_type;
1666
1667           /* All but the final copy start a new nesting, maintaining the
1668           chain of brackets outstanding. */
1669
1670           if (i != 0)
1671             {
1672             int offset;
1673             *code++ = OP_BRA;
1674             offset = (bralink == NULL)? 0 : code - bralink;
1675             bralink = code;
1676             *code++ = offset >> 8;
1677             *code++ = offset & 255;
1678             }
1679
1680           memcpy(code, previous, len);
1681           code += len;
1682           }
1683
1684         /* Now chain through the pending brackets, and fill in their length
1685         fields (which are holding the chain links pro tem). */
1686
1687         while (bralink != NULL)
1688           {
1689           int oldlinkoffset;
1690           int offset = code - bralink + 1;
1691           uschar *bra = code - offset;
1692           oldlinkoffset = (bra[1] << 8) + bra[2];
1693           bralink = (oldlinkoffset == 0)? NULL : bralink - oldlinkoffset;
1694           *code++ = OP_KET;
1695           *code++ = bra[1] = offset >> 8;
1696           *code++ = bra[2] = (offset & 255);
1697           }
1698         }
1699
1700       /* If the maximum is unlimited, set a repeater in the final copy. We
1701       can't just offset backwards from the current code point, because we
1702       don't know if there's been an options resetting after the ket. The
1703       correct offset was computed above. */
1704
1705       else code[-ketoffset] = OP_KETRMAX + repeat_type;
1706       }
1707
1708     /* Else there's some kind of shambles */
1709
1710     else
1711       {
1712       *errorptr = ERR11;
1713       goto FAILED;
1714       }
1715
1716     /* In all case we no longer have a previous item. */
1717
1718     END_REPEAT:
1719     previous = NULL;
1720     break;
1721
1722
1723     /* Start of nested bracket sub-expression, or comment or lookahead or
1724     lookbehind or option setting or condition. First deal with special things
1725     that can come after a bracket; all are introduced by ?, and the appearance
1726     of any of them means that this is not a referencing group. They were
1727     checked for validity in the first pass over the string, so we don't have to
1728     check for syntax errors here.  */
1729
1730     case '(':
1731     newoptions = options;
1732     condref = -1;
1733
1734     if (*(++ptr) == '?')
1735       {
1736       int set, unset;
1737       int *optset;
1738
1739       switch (*(++ptr))
1740         {
1741         case '#':                 /* Comment; skip to ket */
1742         ptr++;
1743         while (*ptr != ')') ptr++;
1744         continue;
1745
1746         case ':':                 /* Non-extracting bracket */
1747         bravalue = OP_BRA;
1748         ptr++;
1749         break;
1750
1751         case '(':
1752         bravalue = OP_COND;       /* Conditional group */
1753         if ((cd->ctypes[*(++ptr)] & ctype_digit) != 0)
1754           {
1755           condref = *ptr - '0';
1756           while (*(++ptr) != ')') condref = condref*10 + *ptr - '0';
1757           if (condref == 0)
1758             {
1759             *errorptr = ERR35;
1760             goto FAILED;
1761             }
1762           ptr++;
1763           }
1764         else ptr--;
1765         break;
1766
1767         case '=':                 /* Positive lookahead */
1768         bravalue = OP_ASSERT;
1769         ptr++;
1770         break;
1771
1772         case '!':                 /* Negative lookahead */
1773         bravalue = OP_ASSERT_NOT;
1774         ptr++;
1775         break;
1776
1777         case '<':                 /* Lookbehinds */
1778         switch (*(++ptr))
1779           {
1780           case '=':               /* Positive lookbehind */
1781           bravalue = OP_ASSERTBACK;
1782           ptr++;
1783           break;
1784
1785           case '!':               /* Negative lookbehind */
1786           bravalue = OP_ASSERTBACK_NOT;
1787           ptr++;
1788           break;
1789
1790           default:                /* Syntax error */
1791           *errorptr = ERR24;
1792           goto FAILED;
1793           }
1794         break;
1795
1796         case '>':                 /* One-time brackets */
1797         bravalue = OP_ONCE;
1798         ptr++;
1799         break;
1800
1801         case 'R':                 /* Pattern recursion */
1802         *code++ = OP_RECURSE;
1803         ptr++;
1804         continue;
1805
1806         default:                  /* Option setting */
1807         set = unset = 0;
1808         optset = &set;
1809
1810         while (*ptr != ')' && *ptr != ':')
1811           {
1812           switch (*ptr++)
1813             {
1814             case '-': optset = &unset; break;
1815
1816             case 'i': *optset |= PCRE_CASELESS; break;
1817             case 'm': *optset |= PCRE_MULTILINE; break;
1818             case 's': *optset |= PCRE_DOTALL; break;
1819             case 'x': *optset |= PCRE_EXTENDED; break;
1820             case 'U': *optset |= PCRE_UNGREEDY; break;
1821             case 'X': *optset |= PCRE_EXTRA; break;
1822
1823             default:
1824             *errorptr = ERR12;
1825             goto FAILED;
1826             }
1827           }
1828
1829         /* Set up the changed option bits, but don't change anything yet. */
1830
1831         newoptions = (options | set) & (~unset);
1832
1833         /* If the options ended with ')' this is not the start of a nested
1834         group with option changes, so the options change at this level. At top
1835         level there is nothing else to be done (the options will in fact have
1836         been set from the start of compiling as a result of the first pass) but
1837         at an inner level we must compile code to change the ims options if
1838         necessary, and pass the new setting back so that it can be put at the
1839         start of any following branches, and when this group ends, a resetting
1840         item can be compiled. */
1841
1842         if (*ptr == ')')
1843           {
1844           if ((options & PCRE_INGROUP) != 0 &&
1845               (options & PCRE_IMS) != (newoptions & PCRE_IMS))
1846             {
1847             *code++ = OP_OPT;
1848             *code++ = *optchanged = newoptions & PCRE_IMS;
1849             }
1850           options = newoptions;  /* Change options at this level */
1851           previous = NULL;       /* This item can't be repeated */
1852           continue;              /* It is complete */
1853           }
1854
1855         /* If the options ended with ':' we are heading into a nested group
1856         with possible change of options. Such groups are non-capturing and are
1857         not assertions of any kind. All we need to do is skip over the ':';
1858         the newoptions value is handled below. */
1859
1860         bravalue = OP_BRA;
1861         ptr++;
1862         }
1863       }
1864
1865     /* Else we have a referencing group; adjust the opcode. */
1866
1867     else
1868       {
1869       if (++(*brackets) > EXTRACT_MAX)
1870         {
1871         *errorptr = ERR13;
1872         goto FAILED;
1873         }
1874       bravalue = OP_BRA + *brackets;
1875       }
1876
1877     /* Process nested bracketed re. Assertions may not be repeated, but other
1878     kinds can be. We copy code into a non-register variable in order to be able
1879     to pass its address because some compilers complain otherwise. Pass in a
1880     new setting for the ims options if they have changed. */
1881
1882     previous = (bravalue >= OP_ONCE)? code : NULL;
1883     *code = bravalue;
1884     tempcode = code;
1885
1886     if (!compile_regex(
1887          options | PCRE_INGROUP,       /* Set for all nested groups */
1888          ((options & PCRE_IMS) != (newoptions & PCRE_IMS))?
1889            newoptions & PCRE_IMS : -1, /* Pass ims options if changed */
1890          brackets,                     /* Bracket level */
1891          &tempcode,                    /* Where to put code (updated) */
1892          &ptr,                         /* Input pointer (updated) */
1893          errorptr,                     /* Where to put an error message */
1894          (bravalue == OP_ASSERTBACK ||
1895           bravalue == OP_ASSERTBACK_NOT), /* TRUE if back assert */
1896          condref,                      /* Condition reference number */
1897          &subreqchar,                  /* For possible last char */
1898          &subcountlits,                /* For literal count */
1899          cd))                          /* Tables block */
1900       goto FAILED;
1901
1902     /* At the end of compiling, code is still pointing to the start of the
1903     group, while tempcode has been updated to point past the end of the group
1904     and any option resetting that may follow it. The pattern pointer (ptr)
1905     is on the bracket. */
1906
1907     /* If this is a conditional bracket, check that there are no more than
1908     two branches in the group. */
1909
1910     if (bravalue == OP_COND)
1911       {
1912       uschar *tc = code;
1913       condcount = 0;
1914
1915       do {
1916          condcount++;
1917          tc += (tc[1] << 8) | tc[2];
1918          }
1919       while (*tc != OP_KET);
1920
1921       if (condcount > 2)
1922         {
1923         *errorptr = ERR27;
1924         goto FAILED;
1925         }
1926       }
1927
1928     /* Handle updating of the required character. If the subpattern didn't
1929     set one, leave it as it was. Otherwise, update it for normal brackets of
1930     all kinds, forward assertions, and conditions with two branches. Don't
1931     update the literal count for forward assertions, however. If the bracket
1932     is followed by a quantifier with zero repeat, we have to back off. Hence
1933     the definition of prevreqchar and subcountlits outside the main loop so
1934     that they can be accessed for the back off. */
1935
1936     if (subreqchar > 0 &&
1937          (bravalue >= OP_BRA || bravalue == OP_ONCE || bravalue == OP_ASSERT ||
1938          (bravalue == OP_COND && condcount == 2)))
1939       {
1940       prevreqchar = *reqchar;
1941       *reqchar = subreqchar;
1942       if (bravalue != OP_ASSERT) *countlits += subcountlits;
1943       }
1944
1945     /* Now update the main code pointer to the end of the group. */
1946
1947     code = tempcode;
1948
1949     /* Error if hit end of pattern */
1950
1951     if (*ptr != ')')
1952       {
1953       *errorptr = ERR14;
1954       goto FAILED;
1955       }
1956     break;
1957
1958     /* Check \ for being a real metacharacter; if not, fall through and handle
1959     it as a data character at the start of a string. Escape items are checked
1960     for validity in the pre-compiling pass. */
1961
1962     case '\\':
1963     tempptr = ptr;
1964     c = check_escape(&ptr, errorptr, *brackets, options, FALSE, cd);
1965
1966     /* Handle metacharacters introduced by \. For ones like \d, the ESC_ values
1967     are arranged to be the negation of the corresponding OP_values. For the
1968     back references, the values are ESC_REF plus the reference number. Only
1969     back references and those types that consume a character may be repeated.
1970     We can test for values between ESC_b and ESC_Z for the latter; this may
1971     have to change if any new ones are ever created. */
1972
1973     if (c < 0)
1974       {
1975       if (-c >= ESC_REF)
1976         {
1977         previous = code;
1978         *code++ = OP_REF;
1979         *code++ = -c - ESC_REF;
1980         }
1981       else
1982         {
1983         previous = (-c > ESC_b && -c < ESC_Z)? code : NULL;
1984         *code++ = -c;
1985         }
1986       continue;
1987       }
1988
1989     /* Data character: reset and fall through */
1990
1991     ptr = tempptr;
1992     c = '\\';
1993
1994     /* Handle a run of data characters until a metacharacter is encountered.
1995     The first character is guaranteed not to be whitespace or # when the
1996     extended flag is set. */
1997
1998     NORMAL_CHAR:
1999     default:
2000     previous = code;
2001     *code = OP_CHARS;
2002     code += 2;
2003     length = 0;
2004
2005     do
2006       {
2007       if ((options & PCRE_EXTENDED) != 0)
2008         {
2009         if ((cd->ctypes[c] & ctype_space) != 0) continue;
2010         if (c == '#')
2011           {
2012           /* The space before the ; is to avoid a warning on a silly compiler
2013           on the Macintosh. */
2014           while ((c = *(++ptr)) != 0 && c != '\n') ;
2015           if (c == 0) break;
2016           continue;
2017           }
2018         }
2019
2020       /* Backslash may introduce a data char or a metacharacter. Escaped items
2021       are checked for validity in the pre-compiling pass. Stop the string
2022       before a metaitem. */
2023
2024       if (c == '\\')
2025         {
2026         tempptr = ptr;
2027         c = check_escape(&ptr, errorptr, *brackets, options, FALSE, cd);
2028         if (c < 0) { ptr = tempptr; break; }
2029
2030         /* If a character is > 127 in UTF-8 mode, we have to turn it into
2031         two or more characters in the UTF-8 encoding. */
2032
2033 #ifdef SUPPORT_UTF8
2034         if (c > 127 && (options & PCRE_UTF8) != 0)
2035           {
2036           uschar buffer[8];
2037           int len = ord2utf8(c, buffer);
2038           for (c = 0; c < len; c++) *code++ = buffer[c];
2039           length += len;
2040           continue;
2041           }
2042 #endif
2043         }
2044
2045       /* Ordinary character or single-char escape */
2046
2047       *code++ = c;
2048       length++;
2049       }
2050
2051     /* This "while" is the end of the "do" above. */
2052
2053     while (length < MAXLIT && (cd->ctypes[c = *(++ptr)] & ctype_meta) == 0);
2054
2055     /* Update the last character and the count of literals */
2056
2057     prevreqchar = (length > 1)? code[-2] : *reqchar;
2058     *reqchar = code[-1];
2059     *countlits += length;
2060
2061     /* Compute the length and set it in the data vector, and advance to
2062     the next state. */
2063
2064     previous[1] = length;
2065     if (length < MAXLIT) ptr--;
2066     break;
2067     }
2068   }                   /* end of big loop */
2069
2070 /* Control never reaches here by falling through, only by a goto for all the
2071 error states. Pass back the position in the pattern so that it can be displayed
2072 to the user for diagnosing the error. */
2073
2074 FAILED:
2075 *ptrptr = ptr;
2076 return FALSE;
2077 }
2078
2079
2080
2081
2082 /*************************************************
2083 *     Compile sequence of alternatives           *
2084 *************************************************/
2085
2086 /* On entry, ptr is pointing past the bracket character, but on return
2087 it points to the closing bracket, or vertical bar, or end of string.
2088 The code variable is pointing at the byte into which the BRA operator has been
2089 stored. If the ims options are changed at the start (for a (?ims: group) or
2090 during any branch, we need to insert an OP_OPT item at the start of every
2091 following branch to ensure they get set correctly at run time, and also pass
2092 the new options into every subsequent branch compile.
2093
2094 Argument:
2095   options     the option bits
2096   optchanged  new ims options to set as if (?ims) were at the start, or -1
2097                for no change
2098   brackets    -> int containing the number of extracting brackets used
2099   codeptr     -> the address of the current code pointer
2100   ptrptr      -> the address of the current pattern pointer
2101   errorptr    -> pointer to error message
2102   lookbehind  TRUE if this is a lookbehind assertion
2103   condref     >= 0 for OPT_CREF setting at start of conditional group
2104   reqchar     -> place to put the last required character, or a negative number
2105   countlits   -> place to put the shortest literal count of any branch
2106   cd          points to the data block with tables pointers
2107
2108 Returns:      TRUE on success
2109 */
2110
2111 static BOOL
2112 compile_regex(int options, int optchanged, int *brackets, uschar **codeptr,
2113   const uschar **ptrptr, const char **errorptr, BOOL lookbehind, int condref,
2114   int *reqchar, int *countlits, compile_data *cd)
2115 {
2116 const uschar *ptr = *ptrptr;
2117 uschar *code = *codeptr;
2118 uschar *last_branch = code;
2119 uschar *start_bracket = code;
2120 uschar *reverse_count = NULL;
2121 int oldoptions = options & PCRE_IMS;
2122 int branchreqchar, branchcountlits;
2123
2124 *reqchar = -1;
2125 *countlits = INT_MAX;
2126 code += 3;
2127
2128 /* At the start of a reference-based conditional group, insert the reference
2129 number as an OP_CREF item. */
2130
2131 if (condref >= 0)
2132   {
2133   *code++ = OP_CREF;
2134   *code++ = condref;
2135   }
2136
2137 /* Loop for each alternative branch */
2138
2139 for (;;)
2140   {
2141   int length;
2142
2143   /* Handle change of options */
2144
2145   if (optchanged >= 0)
2146     {
2147     *code++ = OP_OPT;
2148     *code++ = optchanged;
2149     options = (options & ~PCRE_IMS) | optchanged;
2150     }
2151
2152   /* Set up dummy OP_REVERSE if lookbehind assertion */
2153
2154   if (lookbehind)
2155     {
2156     *code++ = OP_REVERSE;
2157     reverse_count = code;
2158     *code++ = 0;
2159     *code++ = 0;
2160     }
2161
2162   /* Now compile the branch */
2163
2164   if (!compile_branch(options, brackets, &code, &ptr, errorptr, &optchanged,
2165       &branchreqchar, &branchcountlits, cd))
2166     {
2167     *ptrptr = ptr;
2168     return FALSE;
2169     }
2170
2171   /* Fill in the length of the last branch */
2172
2173   length = code - last_branch;
2174   last_branch[1] = length >> 8;
2175   last_branch[2] = length & 255;
2176
2177   /* Save the last required character if all branches have the same; a current
2178   value of -1 means unset, while -2 means "previous branch had no last required
2179   char".  */
2180
2181   if (*reqchar != -2)
2182     {
2183     if (branchreqchar >= 0)
2184       {
2185       if (*reqchar == -1) *reqchar = branchreqchar;
2186       else if (*reqchar != branchreqchar) *reqchar = -2;
2187       }
2188     else *reqchar = -2;
2189     }
2190
2191   /* Keep the shortest literal count */
2192
2193   if (branchcountlits < *countlits) *countlits = branchcountlits;
2194   DPRINTF(("literal count = %d min=%d\n", branchcountlits, *countlits));
2195
2196   /* If lookbehind, check that this branch matches a fixed-length string,
2197   and put the length into the OP_REVERSE item. Temporarily mark the end of
2198   the branch with OP_END. */
2199
2200   if (lookbehind)
2201     {
2202     *code = OP_END;
2203     length = find_fixedlength(last_branch, options);
2204     DPRINTF(("fixed length = %d\n", length));
2205     if (length < 0)
2206       {
2207       *errorptr = ERR25;
2208       *ptrptr = ptr;
2209       return FALSE;
2210       }
2211     reverse_count[0] = (length >> 8);
2212     reverse_count[1] = length & 255;
2213     }
2214
2215   /* Reached end of expression, either ')' or end of pattern. Insert a
2216   terminating ket and the length of the whole bracketed item, and return,
2217   leaving the pointer at the terminating char. If any of the ims options
2218   were changed inside the group, compile a resetting op-code following. */
2219
2220   if (*ptr != '|')
2221     {
2222     length = code - start_bracket;
2223     *code++ = OP_KET;
2224     *code++ = length >> 8;
2225     *code++ = length & 255;
2226     if (optchanged >= 0)
2227       {
2228       *code++ = OP_OPT;
2229       *code++ = oldoptions;
2230       }
2231     *codeptr = code;
2232     *ptrptr = ptr;
2233     return TRUE;
2234     }
2235
2236   /* Another branch follows; insert an "or" node and advance the pointer. */
2237
2238   *code = OP_ALT;
2239   last_branch = code;
2240   code += 3;
2241   ptr++;
2242   }
2243 /* Control never reaches here */
2244 }
2245
2246
2247
2248
2249 /*************************************************
2250 *      Find first significant op code            *
2251 *************************************************/
2252
2253 /* This is called by several functions that scan a compiled expression looking
2254 for a fixed first character, or an anchoring op code etc. It skips over things
2255 that do not influence this. For one application, a change of caseless option is
2256 important.
2257
2258 Arguments:
2259   code       pointer to the start of the group
2260   options    pointer to external options
2261   optbit     the option bit whose changing is significant, or
2262              zero if none are
2263   optstop    TRUE to return on option change, otherwise change the options
2264                value and continue
2265
2266 Returns:     pointer to the first significant opcode
2267 */
2268
2269 static const uschar*
2270 first_significant_code(const uschar *code, int *options, int optbit,
2271   BOOL optstop)
2272 {
2273 for (;;)
2274   {
2275   switch ((int)*code)
2276     {
2277     case OP_OPT:
2278     if (optbit > 0 && ((int)code[1] & optbit) != (*options & optbit))
2279       {
2280       if (optstop) return code;
2281       *options = (int)code[1];
2282       }
2283     code += 2;
2284     break;
2285
2286     case OP_CREF:
2287     code += 2;
2288     break;
2289
2290     case OP_WORD_BOUNDARY:
2291     case OP_NOT_WORD_BOUNDARY:
2292     code++;
2293     break;
2294
2295     case OP_ASSERT_NOT:
2296     case OP_ASSERTBACK:
2297     case OP_ASSERTBACK_NOT:
2298     do code += (code[1] << 8) + code[2]; while (*code == OP_ALT);
2299     code += 3;
2300     break;
2301
2302     default:
2303     return code;
2304     }
2305   }
2306 /* Control never reaches here */
2307 }
2308
2309
2310
2311
2312 /*************************************************
2313 *          Check for anchored expression         *
2314 *************************************************/
2315
2316 /* Try to find out if this is an anchored regular expression. Consider each
2317 alternative branch. If they all start with OP_SOD or OP_CIRC, or with a bracket
2318 all of whose alternatives start with OP_SOD or OP_CIRC (recurse ad lib), then
2319 it's anchored. However, if this is a multiline pattern, then only OP_SOD
2320 counts, since OP_CIRC can match in the middle.
2321
2322 A branch is also implicitly anchored if it starts with .* and DOTALL is set,
2323 because that will try the rest of the pattern at all possible matching points,
2324 so there is no point trying them again.
2325
2326 Arguments:
2327   code       points to start of expression (the bracket)
2328   options    points to the options setting
2329
2330 Returns:     TRUE or FALSE
2331 */
2332
2333 static BOOL
2334 is_anchored(register const uschar *code, int *options)
2335 {
2336 do {
2337    const uschar *scode = first_significant_code(code + 3, options,
2338      PCRE_MULTILINE, FALSE);
2339    register int op = *scode;
2340    if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
2341      { if (!is_anchored(scode, options)) return FALSE; }
2342    else if ((op == OP_TYPESTAR || op == OP_TYPEMINSTAR) &&
2343             (*options & PCRE_DOTALL) != 0)
2344      { if (scode[1] != OP_ANY) return FALSE; }
2345    else if (op != OP_SOD &&
2346            ((*options & PCRE_MULTILINE) != 0 || op != OP_CIRC))
2347      return FALSE;
2348    code += (code[1] << 8) + code[2];
2349    }
2350 while (*code == OP_ALT);
2351 return TRUE;
2352 }
2353
2354
2355
2356 /*************************************************
2357 *         Check for starting with ^ or .*        *
2358 *************************************************/
2359
2360 /* This is called to find out if every branch starts with ^ or .* so that
2361 "first char" processing can be done to speed things up in multiline
2362 matching and for non-DOTALL patterns that start with .* (which must start at
2363 the beginning or after \n).
2364
2365 Argument:  points to start of expression (the bracket)
2366 Returns:   TRUE or FALSE
2367 */
2368
2369 static BOOL
2370 is_startline(const uschar *code)
2371 {
2372 do {
2373    const uschar *scode = first_significant_code(code + 3, NULL, 0, FALSE);
2374    register int op = *scode;
2375    if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
2376      { if (!is_startline(scode)) return FALSE; }
2377    else if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR)
2378      { if (scode[1] != OP_ANY) return FALSE; }
2379    else if (op != OP_CIRC) return FALSE;
2380    code += (code[1] << 8) + code[2];
2381    }
2382 while (*code == OP_ALT);
2383 return TRUE;
2384 }
2385
2386
2387
2388 /*************************************************
2389 *          Check for fixed first char            *
2390 *************************************************/
2391
2392 /* Try to find out if there is a fixed first character. This is called for
2393 unanchored expressions, as it speeds up their processing quite considerably.
2394 Consider each alternative branch. If they all start with the same char, or with
2395 a bracket all of whose alternatives start with the same char (recurse ad lib),
2396 then we return that char, otherwise -1.
2397
2398 Arguments:
2399   code       points to start of expression (the bracket)
2400   options    pointer to the options (used to check casing changes)
2401
2402 Returns:     -1 or the fixed first char
2403 */
2404
2405 static int
2406 find_firstchar(const uschar *code, int *options)
2407 {
2408 register int c = -1;
2409 do {
2410    int d;
2411    const uschar *scode = first_significant_code(code + 3, options,
2412      PCRE_CASELESS, TRUE);
2413    register int op = *scode;
2414
2415    if (op >= OP_BRA) op = OP_BRA;
2416
2417    switch(op)
2418      {
2419      default:
2420      return -1;
2421
2422      case OP_BRA:
2423      case OP_ASSERT:
2424      case OP_ONCE:
2425      case OP_COND:
2426      if ((d = find_firstchar(scode, options)) < 0) return -1;
2427      if (c < 0) c = d; else if (c != d) return -1;
2428      break;
2429
2430      case OP_EXACT:       /* Fall through */
2431      scode++;
2432
2433      case OP_CHARS:       /* Fall through */
2434      scode++;
2435
2436      case OP_PLUS:
2437      case OP_MINPLUS:
2438      if (c < 0) c = scode[1]; else if (c != scode[1]) return -1;
2439      break;
2440      }
2441
2442    code += (code[1] << 8) + code[2];
2443    }
2444 while (*code == OP_ALT);
2445 return c;
2446 }
2447
2448
2449
2450
2451
2452 /*************************************************
2453 *        Compile a Regular Expression            *
2454 *************************************************/
2455
2456 /* This function takes a string and returns a pointer to a block of store
2457 holding a compiled version of the expression.
2458
2459 Arguments:
2460   pattern      the regular expression
2461   options      various option bits
2462   errorptr     pointer to pointer to error text
2463   erroroffset  ptr offset in pattern where error was detected
2464   tables       pointer to character tables or NULL
2465
2466 Returns:       pointer to compiled data block, or NULL on error,
2467                with errorptr and erroroffset set
2468 */
2469
2470 pcre *
2471 pcre_compile(const char *pattern, int options, const char **errorptr,
2472   int *erroroffset, const unsigned char *tables)
2473 {
2474 real_pcre *re;
2475 int length = 3;      /* For initial BRA plus length */
2476 int runlength;
2477 int c, reqchar, countlits;
2478 int bracount = 0;
2479 int top_backref = 0;
2480 int branch_extra = 0;
2481 int branch_newextra;
2482 unsigned int brastackptr = 0;
2483 size_t size;
2484 uschar *code;
2485 const uschar *ptr;
2486 compile_data compile_block;
2487 int brastack[BRASTACK_SIZE];
2488 uschar bralenstack[BRASTACK_SIZE];
2489 const size_t pattern_length = strlen(pattern);
2490
2491 #ifdef DEBUG
2492 uschar *code_base, *code_end;
2493 #endif
2494
2495 /* Can't support UTF8 unless PCRE has been compiled to include the code. */
2496
2497 #ifndef SUPPORT_UTF8
2498 if ((options & PCRE_UTF8) != 0)
2499   {
2500   *errorptr = ERR32;
2501   return NULL;
2502   }
2503 #endif
2504
2505 /* We can't pass back an error message if errorptr is NULL; I guess the best we
2506 can do is just return NULL. */
2507
2508 if (errorptr == NULL) return NULL;
2509 *errorptr = NULL;
2510
2511 /* However, we can give a message for this error */
2512
2513 if (erroroffset == NULL)
2514   {
2515   *errorptr = ERR16;
2516   return NULL;
2517   }
2518 *erroroffset = 0;
2519
2520 if ((options & ~PUBLIC_OPTIONS) != 0)
2521   {
2522   *errorptr = ERR17;
2523   return NULL;
2524   }
2525
2526 /* Set up pointers to the individual character tables */
2527
2528 if (tables == NULL) tables = pcre_default_tables;
2529 compile_block.lcc = tables + lcc_offset;
2530 compile_block.fcc = tables + fcc_offset;
2531 compile_block.cbits = tables + cbits_offset;
2532 compile_block.ctypes = tables + ctypes_offset;
2533
2534 /* Reflect pattern for debugging output */
2535
2536 DPRINTF(("------------------------------------------------------------------\n"));
2537 DPRINTF(("%s\n", pattern));
2538
2539 /* The first thing to do is to make a pass over the pattern to compute the
2540 amount of store required to hold the compiled code. This does not have to be
2541 perfect as long as errors are overestimates. At the same time we can detect any
2542 internal flag settings. Make an attempt to correct for any counted white space
2543 if an "extended" flag setting appears late in the pattern. We can't be so
2544 clever for #-comments. */
2545
2546 ptr = (const uschar *)(pattern - 1);
2547 while ((c = *(++ptr)) != 0)
2548   {
2549   int min, max;
2550   int class_charcount;
2551
2552   if ((options & PCRE_EXTENDED) != 0)
2553     {
2554     if ((compile_block.ctypes[c] & ctype_space) != 0) continue;
2555     if (c == '#')
2556       {
2557       /* The space before the ; is to avoid a warning on a silly compiler
2558       on the Macintosh. */
2559       while ((c = *(++ptr)) != 0 && c != '\n') ;
2560       continue;
2561       }
2562     }
2563
2564   switch(c)
2565     {
2566     /* A backslashed item may be an escaped "normal" character or a
2567     character type. For a "normal" character, put the pointers and
2568     character back so that tests for whitespace etc. in the input
2569     are done correctly. */
2570
2571     case '\\':
2572       {
2573       const uschar *save_ptr = ptr;
2574       c = check_escape(&ptr, errorptr, bracount, options, FALSE, &compile_block);
2575       if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2576       if (c >= 0)
2577         {
2578         ptr = save_ptr;
2579         c = '\\';
2580         goto NORMAL_CHAR;
2581         }
2582       }
2583     length++;
2584
2585     /* A back reference needs an additional char, plus either one or 5
2586     bytes for a repeat. We also need to keep the value of the highest
2587     back reference. */
2588
2589     if (c <= -ESC_REF)
2590       {
2591       int refnum = -c - ESC_REF;
2592       if (refnum > top_backref) top_backref = refnum;
2593       length++;   /* For single back reference */
2594       if (ptr[1] == '{' && is_counted_repeat(ptr+2, &compile_block))
2595         {
2596         ptr = read_repeat_counts(ptr+2, &min, &max, errorptr, &compile_block);
2597         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2598         if ((min == 0 && (max == 1 || max == -1)) ||
2599           (min == 1 && max == -1))
2600             length++;
2601         else length += 5;
2602         if (ptr[1] == '?') ptr++;
2603         }
2604       }
2605     continue;
2606
2607     case '^':
2608     case '.':
2609     case '$':
2610     case '*':     /* These repeats won't be after brackets; */
2611     case '+':     /* those are handled separately */
2612     case '?':
2613     length++;
2614     continue;
2615
2616     /* This covers the cases of repeats after a single char, metachar, class,
2617     or back reference. */
2618
2619     case '{':
2620     if (!is_counted_repeat(ptr+1, &compile_block)) goto NORMAL_CHAR;
2621     ptr = read_repeat_counts(ptr+1, &min, &max, errorptr, &compile_block);
2622     if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2623     if ((min == 0 && (max == 1 || max == -1)) ||
2624       (min == 1 && max == -1))
2625         length++;
2626     else
2627       {
2628       length--;   /* Uncount the original char or metachar */
2629       if (min == 1) length++; else if (min > 0) length += 4;
2630       if (max > 0) length += 4; else length += 2;
2631       }
2632     if (ptr[1] == '?') ptr++;
2633     continue;
2634
2635     /* An alternation contains an offset to the next branch or ket. If any ims
2636     options changed in the previous branch(es), and/or if we are in a
2637     lookbehind assertion, extra space will be needed at the start of the
2638     branch. This is handled by branch_extra. */
2639
2640     case '|':
2641     length += 3 + branch_extra;
2642     continue;
2643
2644     /* A character class uses 33 characters. Don't worry about character types
2645     that aren't allowed in classes - they'll get picked up during the compile.
2646     A character class that contains only one character uses 2 or 3 bytes,
2647     depending on whether it is negated or not. Notice this where we can. */
2648
2649     case '[':
2650     class_charcount = 0;
2651     if (*(++ptr) == '^') ptr++;
2652     do
2653       {
2654       if (*ptr == '\\')
2655         {
2656         int ch = check_escape(&ptr, errorptr, bracount, options, TRUE,
2657           &compile_block);
2658         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2659         if (-ch == ESC_b) class_charcount++; else class_charcount = 10;
2660         }
2661       else class_charcount++;
2662       ptr++;
2663       }
2664     while (*ptr != 0 && *ptr != ']');
2665
2666     /* Repeats for negated single chars are handled by the general code */
2667
2668     if (class_charcount == 1) length += 3; else
2669       {
2670       length += 33;
2671
2672       /* A repeat needs either 1 or 5 bytes. */
2673
2674       if (*ptr != 0 && ptr[1] == '{' && is_counted_repeat(ptr+2, &compile_block))
2675         {
2676         ptr = read_repeat_counts(ptr+2, &min, &max, errorptr, &compile_block);
2677         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2678         if ((min == 0 && (max == 1 || max == -1)) ||
2679           (min == 1 && max == -1))
2680             length++;
2681         else length += 5;
2682         if (ptr[1] == '?') ptr++;
2683         }
2684       }
2685     continue;
2686
2687     /* Brackets may be genuine groups or special things */
2688
2689     case '(':
2690     branch_newextra = 0;
2691
2692     /* Handle special forms of bracket, which all start (? */
2693
2694     if (ptr[1] == '?')
2695       {
2696       int set, unset;
2697       int *optset;
2698
2699       switch (c = ptr[2])
2700         {
2701         /* Skip over comments entirely */
2702         case '#':
2703         ptr += 3;
2704         while (*ptr != 0 && *ptr != ')') ptr++;
2705         if (*ptr == 0)
2706           {
2707           *errorptr = ERR18;
2708           goto PCRE_ERROR_RETURN;
2709           }
2710         continue;
2711
2712         /* Non-referencing groups and lookaheads just move the pointer on, and
2713         then behave like a non-special bracket, except that they don't increment
2714         the count of extracting brackets. Ditto for the "once only" bracket,
2715         which is in Perl from version 5.005. */
2716
2717         case ':':
2718         case '=':
2719         case '!':
2720         case '>':
2721         ptr += 2;
2722         break;
2723
2724         /* A recursive call to the regex is an extension, to provide the
2725         facility which can be obtained by $(?p{perl-code}) in Perl 5.6. */
2726
2727         case 'R':
2728         if (ptr[3] != ')')
2729           {
2730           *errorptr = ERR29;
2731           goto PCRE_ERROR_RETURN;
2732           }
2733         ptr += 3;
2734         length += 1;
2735         break;
2736
2737         /* Lookbehinds are in Perl from version 5.005 */
2738
2739         case '<':
2740         if (ptr[3] == '=' || ptr[3] == '!')
2741           {
2742           ptr += 3;
2743           branch_newextra = 3;
2744           length += 3;         /* For the first branch */
2745           break;
2746           }
2747         *errorptr = ERR24;
2748         goto PCRE_ERROR_RETURN;
2749
2750         /* Conditionals are in Perl from version 5.005. The bracket must either
2751         be followed by a number (for bracket reference) or by an assertion
2752         group. */
2753
2754         case '(':
2755         if ((compile_block.ctypes[ptr[3]] & ctype_digit) != 0)
2756           {
2757           ptr += 4;
2758           length += 2;
2759           while ((compile_block.ctypes[*ptr] & ctype_digit) != 0) ptr++;
2760           if (*ptr != ')')
2761             {
2762             *errorptr = ERR26;
2763             goto PCRE_ERROR_RETURN;
2764             }
2765           }
2766         else   /* An assertion must follow */
2767           {
2768           ptr++;   /* Can treat like ':' as far as spacing is concerned */
2769           if (ptr[2] != '?' ||
2770              (ptr[3] != '=' && ptr[3] != '!' && ptr[3] != '<') )
2771             {
2772             ptr += 2;    /* To get right offset in message */
2773             *errorptr = ERR28;
2774             goto PCRE_ERROR_RETURN;
2775             }
2776           }
2777         break;
2778
2779         /* Else loop checking valid options until ) is met. Anything else is an
2780         error. If we are without any brackets, i.e. at top level, the settings
2781         act as if specified in the options, so massage the options immediately.
2782         This is for backward compatibility with Perl 5.004. */
2783
2784         default:
2785         set = unset = 0;
2786         optset = &set;
2787         ptr += 2;
2788
2789         for (;; ptr++)
2790           {
2791           c = *ptr;
2792           switch (c)
2793             {
2794             case 'i':
2795             *optset |= PCRE_CASELESS;
2796             continue;
2797
2798             case 'm':
2799             *optset |= PCRE_MULTILINE;
2800             continue;
2801
2802             case 's':
2803             *optset |= PCRE_DOTALL;
2804             continue;
2805
2806             case 'x':
2807             *optset |= PCRE_EXTENDED;
2808             continue;
2809
2810             case 'X':
2811             *optset |= PCRE_EXTRA;
2812             continue;
2813
2814             case 'U':
2815             *optset |= PCRE_UNGREEDY;
2816             continue;
2817
2818             case '-':
2819             optset = &unset;
2820             continue;
2821
2822             /* A termination by ')' indicates an options-setting-only item;
2823             this is global at top level; otherwise nothing is done here and
2824             it is handled during the compiling process on a per-bracket-group
2825             basis. */
2826
2827             case ')':
2828             if (brastackptr == 0)
2829               {
2830               options = (options | set) & (~unset);
2831               set = unset = 0;     /* To save length */
2832               }
2833             /* Fall through */
2834
2835             /* A termination by ':' indicates the start of a nested group with
2836             the given options set. This is again handled at compile time, but
2837             we must allow for compiled space if any of the ims options are
2838             set. We also have to allow for resetting space at the end of
2839             the group, which is why 4 is added to the length and not just 2.
2840             If there are several changes of options within the same group, this
2841             will lead to an over-estimate on the length, but this shouldn't
2842             matter very much. We also have to allow for resetting options at
2843             the start of any alternations, which we do by setting
2844             branch_newextra to 2. Finally, we record whether the case-dependent
2845             flag ever changes within the regex. This is used by the "required
2846             character" code. */
2847
2848             case ':':
2849             if (((set|unset) & PCRE_IMS) != 0)
2850               {
2851               length += 4;
2852               branch_newextra = 2;
2853               if (((set|unset) & PCRE_CASELESS) != 0) options |= PCRE_ICHANGED;
2854               }
2855             goto END_OPTIONS;
2856
2857             /* Unrecognized option character */
2858
2859             default:
2860             *errorptr = ERR12;
2861             goto PCRE_ERROR_RETURN;
2862             }
2863           }
2864
2865         /* If we hit a closing bracket, that's it - this is a freestanding
2866         option-setting. We need to ensure that branch_extra is updated if
2867         necessary. The only values branch_newextra can have here are 0 or 2.
2868         If the value is 2, then branch_extra must either be 2 or 5, depending
2869         on whether this is a lookbehind group or not. */
2870
2871         END_OPTIONS:
2872         if (c == ')')
2873           {
2874           if (branch_newextra == 2 && (branch_extra == 0 || branch_extra == 3))
2875             branch_extra += branch_newextra;
2876           continue;
2877           }
2878
2879         /* If options were terminated by ':' control comes here. Fall through
2880         to handle the group below. */
2881         }
2882       }
2883
2884     /* Extracting brackets must be counted so we can process escapes in a
2885     Perlish way. */
2886
2887     else bracount++;
2888
2889     /* Non-special forms of bracket. Save length for computing whole length
2890     at end if there's a repeat that requires duplication of the group. Also
2891     save the current value of branch_extra, and start the new group with
2892     the new value. If non-zero, this will either be 2 for a (?imsx: group, or 3
2893     for a lookbehind assertion. */
2894
2895     if (brastackptr >= sizeof(brastack)/sizeof(int))
2896       {
2897       *errorptr = ERR19;
2898       goto PCRE_ERROR_RETURN;
2899       }
2900
2901     bralenstack[brastackptr] = branch_extra;
2902     branch_extra = branch_newextra;
2903
2904     brastack[brastackptr++] = length;
2905     length += 3;
2906     continue;
2907
2908     /* Handle ket. Look for subsequent max/min; for certain sets of values we
2909     have to replicate this bracket up to that many times. If brastackptr is
2910     0 this is an unmatched bracket which will generate an error, but take care
2911     not to try to access brastack[-1] when computing the length and restoring
2912     the branch_extra value. */
2913
2914     case ')':
2915     length += 3;
2916       {
2917       int minval = 1;
2918       int maxval = 1;
2919       int duplength;
2920
2921       if (brastackptr > 0)
2922         {
2923         duplength = length - brastack[--brastackptr];
2924         branch_extra = bralenstack[brastackptr];
2925         }
2926       else duplength = 0;
2927
2928       /* Leave ptr at the final char; for read_repeat_counts this happens
2929       automatically; for the others we need an increment. */
2930
2931       if ((c = ptr[1]) == '{' && is_counted_repeat(ptr+2, &compile_block))
2932         {
2933         ptr = read_repeat_counts(ptr+2, &minval, &maxval, errorptr,
2934           &compile_block);
2935         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2936         }
2937       else if (c == '*') { minval = 0; maxval = -1; ptr++; }
2938       else if (c == '+') { maxval = -1; ptr++; }
2939       else if (c == '?') { minval = 0; ptr++; }
2940
2941       /* If the minimum is zero, we have to allow for an OP_BRAZERO before the
2942       group, and if the maximum is greater than zero, we have to replicate
2943       maxval-1 times; each replication acquires an OP_BRAZERO plus a nesting
2944       bracket set - hence the 7. */
2945
2946       if (minval == 0)
2947         {
2948         length++;
2949         if (maxval > 0) length += (maxval - 1) * (duplength + 7);
2950         }
2951
2952       /* When the minimum is greater than zero, 1 we have to replicate up to
2953       minval-1 times, with no additions required in the copies. Then, if
2954       there is a limited maximum we have to replicate up to maxval-1 times
2955       allowing for a BRAZERO item before each optional copy and nesting
2956       brackets for all but one of the optional copies. */
2957
2958       else
2959         {
2960         length += (minval - 1) * duplength;
2961         if (maxval > minval)   /* Need this test as maxval=-1 means no limit */
2962           length += (maxval - minval) * (duplength + 7) - 6;
2963         }
2964       }
2965     continue;
2966
2967     /* Non-special character. For a run of such characters the length required
2968     is the number of characters + 2, except that the maximum run length is 255.
2969     We won't get a skipped space or a non-data escape or the start of a #
2970     comment as the first character, so the length can't be zero. */
2971
2972     NORMAL_CHAR:
2973     default:
2974     length += 2;
2975     runlength = 0;
2976     do
2977       {
2978       if ((options & PCRE_EXTENDED) != 0)
2979         {
2980         if ((compile_block.ctypes[c] & ctype_space) != 0) continue;
2981         if (c == '#')
2982           {
2983           /* The space before the ; is to avoid a warning on a silly compiler
2984           on the Macintosh. */
2985           while ((c = *(++ptr)) != 0 && c != '\n') ;
2986           continue;
2987           }
2988         }
2989
2990       /* Backslash may introduce a data char or a metacharacter; stop the
2991       string before the latter. */
2992
2993       if (c == '\\')
2994         {
2995         const uschar *saveptr = ptr;
2996         c = check_escape(&ptr, errorptr, bracount, options, FALSE,
2997           &compile_block);
2998         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2999         if (c < 0) { ptr = saveptr; break; }
3000
3001 #ifdef SUPPORT_UTF8
3002         if (c > 127 && (options & PCRE_UTF8) != 0)
3003           {
3004           int i;
3005           for (i = 0; i < sizeof(utf8_table1)/sizeof(int); i++)
3006             if (c <= utf8_table1[i]) break;
3007           runlength += i;
3008           }
3009 #endif
3010         }
3011
3012       /* Ordinary character or single-char escape */
3013
3014       runlength++;
3015
3016       if ((const char *)ptr > pattern + pattern_length)
3017         {
3018         *errorptr = "internal error";
3019         goto PCRE_ERROR_RETURN;
3020         }
3021       }
3022
3023     /* This "while" is the end of the "do" above. */
3024
3025     while (runlength < MAXLIT &&
3026       (compile_block.ctypes[c = *(++ptr)] & ctype_meta) == 0);
3027
3028     ptr--;
3029     length += runlength;
3030     continue;
3031     }
3032   }
3033
3034 length += 4;    /* For final KET and END */
3035
3036 if (length > 65539)
3037   {
3038   *errorptr = ERR20;
3039   return NULL;
3040   }
3041
3042 /* Compute the size of data block needed and get it, either from malloc or
3043 externally provided function. We specify "code[0]" in the offsetof() expression
3044 rather than just "code", because it has been reported that one broken compiler
3045 fails on "code" because it is also an independent variable. It should make no
3046 difference to the value of the offsetof(). */
3047
3048 size = length + offsetof(real_pcre, code[0]);
3049 re = (real_pcre *)(pcre_malloc)(size);
3050
3051 if (re == NULL)
3052   {
3053   *errorptr = ERR21;
3054   return NULL;
3055   }
3056
3057 /* Put in the magic number, and save the size, options, and table pointer */
3058
3059 re->magic_number = MAGIC_NUMBER;
3060 re->size = size;
3061 re->options = options;
3062 re->tables = tables;
3063
3064 /* Set up a starting, non-extracting bracket, then compile the expression. On
3065 error, *errorptr will be set non-NULL, so we don't need to look at the result
3066 of the function here. */
3067
3068 ptr = (const uschar *)pattern;
3069 code = re->code;
3070 *code = OP_BRA;
3071 bracount = 0;
3072 (void)compile_regex(options, -1, &bracount, &code, &ptr, errorptr, FALSE, -1,
3073   &reqchar, &countlits, &compile_block);
3074 re->top_bracket = bracount;
3075 re->top_backref = top_backref;
3076
3077 /* If not reached end of pattern on success, there's an excess bracket. */
3078
3079 if (*errorptr == NULL && *ptr != 0) *errorptr = ERR22;
3080
3081 /* Fill in the terminating state and check for disastrous overflow, but
3082 if debugging, leave the test till after things are printed out. */
3083
3084 *code++ = OP_END;
3085
3086 #ifndef DEBUG
3087 if (code - re->code > length) *errorptr = ERR23;
3088 #endif
3089
3090 /* Give an error if there's back reference to a non-existent capturing
3091 subpattern. */
3092
3093 if (top_backref > re->top_bracket) *errorptr = ERR15;
3094
3095 /* Failed to compile */
3096
3097 if (*errorptr != NULL)
3098   {
3099   (pcre_free)(re);
3100   PCRE_ERROR_RETURN:
3101   *erroroffset = ptr - (const uschar *)pattern;
3102   return NULL;
3103   }
3104
3105 /* If the anchored option was not passed, set flag if we can determine that the
3106 pattern is anchored by virtue of ^ characters or \A or anything else (such as
3107 starting with .* when DOTALL is set).
3108
3109 Otherwise, see if we can determine what the first character has to be, because
3110 that speeds up unanchored matches no end. If not, see if we can set the
3111 PCRE_STARTLINE flag. This is helpful for multiline matches when all branches
3112 start with ^. and also when all branches start with .* for non-DOTALL matches.
3113 */
3114
3115 if ((options & PCRE_ANCHORED) == 0)
3116   {
3117   int temp_options = options;
3118   if (is_anchored(re->code, &temp_options))
3119     re->options |= PCRE_ANCHORED;
3120   else
3121     {
3122     int ch = find_firstchar(re->code, &temp_options);
3123     if (ch >= 0)
3124       {
3125       re->first_char = ch;
3126       re->options |= PCRE_FIRSTSET;
3127       }
3128     else if (is_startline(re->code))
3129       re->options |= PCRE_STARTLINE;
3130     }
3131   }
3132
3133 /* Save the last required character if there are at least two literal
3134 characters on all paths, or if there is no first character setting. */
3135
3136 if (reqchar >= 0 && (countlits > 1 || (re->options & PCRE_FIRSTSET) == 0))
3137   {
3138   re->req_char = reqchar;
3139   re->options |= PCRE_REQCHSET;
3140   }
3141
3142 /* Print out the compiled data for debugging */
3143
3144 #ifdef DEBUG
3145
3146 printf("Length = %d top_bracket = %d top_backref = %d\n",
3147   length, re->top_bracket, re->top_backref);
3148
3149 if (re->options != 0)
3150   {
3151   printf("%s%s%s%s%s%s%s%s%s\n",
3152     ((re->options & PCRE_ANCHORED) != 0)? "anchored " : "",
3153     ((re->options & PCRE_CASELESS) != 0)? "caseless " : "",
3154     ((re->options & PCRE_ICHANGED) != 0)? "case state changed " : "",
3155     ((re->options & PCRE_EXTENDED) != 0)? "extended " : "",
3156     ((re->options & PCRE_MULTILINE) != 0)? "multiline " : "",
3157     ((re->options & PCRE_DOTALL) != 0)? "dotall " : "",
3158     ((re->options & PCRE_DOLLAR_ENDONLY) != 0)? "endonly " : "",
3159     ((re->options & PCRE_EXTRA) != 0)? "extra " : "",
3160     ((re->options & PCRE_UNGREEDY) != 0)? "ungreedy " : "");
3161   }
3162
3163 if ((re->options & PCRE_FIRSTSET) != 0)
3164   {
3165   if (isprint(re->first_char)) printf("First char = %c\n", re->first_char);
3166     else printf("First char = \\x%02x\n", re->first_char);
3167   }
3168
3169 if ((re->options & PCRE_REQCHSET) != 0)
3170   {
3171   if (isprint(re->req_char)) printf("Req char = %c\n", re->req_char);
3172     else printf("Req char = \\x%02x\n", re->req_char);
3173   }
3174
3175 code_end = code;
3176 code_base = code = re->code;
3177
3178 while (code < code_end)
3179   {
3180   int charlength;
3181
3182   printf("%3d ", code - code_base);
3183
3184   if (*code >= OP_BRA)
3185     {
3186     printf("%3d Bra %d", (code[1] << 8) + code[2], *code - OP_BRA);
3187     code += 2;
3188     }
3189
3190   else switch(*code)
3191     {
3192     case OP_OPT:
3193     printf(" %.2x %s", code[1], OP_names[*code]);
3194     code++;
3195     break;
3196
3197     case OP_COND:
3198     printf("%3d Cond", (code[1] << 8) + code[2]);
3199     code += 2;
3200     break;
3201
3202     case OP_CREF:
3203     printf(" %.2d %s", code[1], OP_names[*code]);
3204     code++;
3205     break;
3206
3207     case OP_CHARS:
3208     charlength = *(++code);
3209     printf("%3d ", charlength);
3210     while (charlength-- > 0)
3211       if (isprint(c = *(++code))) printf("%c", c); else printf("\\x%02x", c);
3212     break;
3213
3214     case OP_KETRMAX:
3215     case OP_KETRMIN:
3216     case OP_ALT:
3217     case OP_KET:
3218     case OP_ASSERT:
3219     case OP_ASSERT_NOT:
3220     case OP_ASSERTBACK:
3221     case OP_ASSERTBACK_NOT:
3222     case OP_ONCE:
3223     printf("%3d %s", (code[1] << 8) + code[2], OP_names[*code]);
3224     code += 2;
3225     break;
3226
3227     case OP_REVERSE:
3228     printf("%3d %s", (code[1] << 8) + code[2], OP_names[*code]);
3229     code += 2;
3230     break;
3231
3232     case OP_STAR:
3233     case OP_MINSTAR:
3234     case OP_PLUS:
3235     case OP_MINPLUS:
3236     case OP_QUERY:
3237     case OP_MINQUERY:
3238     case OP_TYPESTAR:
3239     case OP_TYPEMINSTAR:
3240     case OP_TYPEPLUS:
3241     case OP_TYPEMINPLUS:
3242     case OP_TYPEQUERY:
3243     case OP_TYPEMINQUERY:
3244     if (*code >= OP_TYPESTAR)
3245       printf("    %s", OP_names[code[1]]);
3246     else if (isprint(c = code[1])) printf("    %c", c);
3247       else printf("    \\x%02x", c);
3248     printf("%s", OP_names[*code++]);
3249     break;
3250
3251     case OP_EXACT:
3252     case OP_UPTO:
3253     case OP_MINUPTO:
3254     if (isprint(c = code[3])) printf("    %c{", c);
3255       else printf("    \\x%02x{", c);
3256     if (*code != OP_EXACT) printf("0,");
3257     printf("%d}", (code[1] << 8) + code[2]);
3258     if (*code == OP_MINUPTO) printf("?");
3259     code += 3;
3260     break;
3261
3262     case OP_TYPEEXACT:
3263     case OP_TYPEUPTO:
3264     case OP_TYPEMINUPTO:
3265     printf("    %s{", OP_names[code[3]]);
3266     if (*code != OP_TYPEEXACT) printf(",");
3267     printf("%d}", (code[1] << 8) + code[2]);
3268     if (*code == OP_TYPEMINUPTO) printf("?");
3269     code += 3;
3270     break;
3271
3272     case OP_NOT:
3273     if (isprint(c = *(++code))) printf("    [^%c]", c);
3274       else printf("    [^\\x%02x]", c);
3275     break;
3276
3277     case OP_NOTSTAR:
3278     case OP_NOTMINSTAR:
3279     case OP_NOTPLUS:
3280     case OP_NOTMINPLUS:
3281     case OP_NOTQUERY:
3282     case OP_NOTMINQUERY:
3283     if (isprint(c = code[1])) printf("    [^%c]", c);
3284       else printf("    [^\\x%02x]", c);
3285     printf("%s", OP_names[*code++]);
3286     break;
3287
3288     case OP_NOTEXACT:
3289     case OP_NOTUPTO:
3290     case OP_NOTMINUPTO:
3291     if (isprint(c = code[3])) printf("    [^%c]{", c);
3292       else printf("    [^\\x%02x]{", c);
3293     if (*code != OP_NOTEXACT) printf(",");
3294     printf("%d}", (code[1] << 8) + code[2]);
3295     if (*code == OP_NOTMINUPTO) printf("?");
3296     code += 3;
3297     break;
3298
3299     case OP_REF:
3300     printf("    \\%d", *(++code));
3301     code ++;
3302     goto CLASS_REF_REPEAT;
3303
3304     case OP_CLASS:
3305       {
3306       int i, min, max;
3307       code++;
3308       printf("    [");
3309
3310       for (i = 0; i < 256; i++)
3311         {
3312         if ((code[i/8] & (1 << (i&7))) != 0)
3313           {
3314           int j;
3315           for (j = i+1; j < 256; j++)
3316             if ((code[j/8] & (1 << (j&7))) == 0) break;
3317           if (i == '-' || i == ']') printf("\\");
3318           if (isprint(i)) printf("%c", i); else printf("\\x%02x", i);
3319           if (--j > i)
3320             {
3321             printf("-");
3322             if (j == '-' || j == ']') printf("\\");
3323             if (isprint(j)) printf("%c", j); else printf("\\x%02x", j);
3324             }
3325           i = j;
3326           }
3327         }
3328       printf("]");
3329       code += 32;
3330
3331       CLASS_REF_REPEAT:
3332
3333       switch(*code)
3334         {
3335         case OP_CRSTAR:
3336         case OP_CRMINSTAR:
3337         case OP_CRPLUS:
3338         case OP_CRMINPLUS:
3339         case OP_CRQUERY:
3340         case OP_CRMINQUERY:
3341         printf("%s", OP_names[*code]);
3342         break;
3343
3344         case OP_CRRANGE:
3345         case OP_CRMINRANGE:
3346         min = (code[1] << 8) + code[2];
3347         max = (code[3] << 8) + code[4];
3348         if (max == 0) printf("{%d,}", min);
3349         else printf("{%d,%d}", min, max);
3350         if (*code == OP_CRMINRANGE) printf("?");
3351         code += 4;
3352         break;
3353
3354         default:
3355         code--;
3356         }
3357       }
3358     break;
3359
3360     /* Anything else is just a one-node item */
3361
3362     default:
3363     printf("    %s", OP_names[*code]);
3364     break;
3365     }
3366
3367   code++;
3368   printf("\n");
3369   }
3370 printf("------------------------------------------------------------------\n");
3371
3372 /* This check is done here in the debugging case so that the code that
3373 was compiled can be seen. */
3374
3375 if (code - re->code > length)
3376   {
3377   *errorptr = ERR23;
3378   (pcre_free)(re);
3379   *erroroffset = ptr - (uschar *)pattern;
3380   return NULL;
3381   }
3382 #endif
3383
3384 return (pcre *)re;
3385 }
3386
3387
3388
3389 /*************************************************
3390 *          Match a back-reference                *
3391 *************************************************/
3392
3393 /* If a back reference hasn't been set, the length that is passed is greater
3394 than the number of characters left in the string, so the match fails.
3395
3396 Arguments:
3397   offset      index into the offset vector
3398   eptr        points into the subject
3399   length      length to be matched
3400   md          points to match data block
3401   ims         the ims flags
3402
3403 Returns:      TRUE if matched
3404 */
3405
3406 static BOOL
3407 match_ref(int offset, register const uschar *eptr, int length, match_data *md,
3408   unsigned long int ims)
3409 {
3410 const uschar *p = md->start_subject + md->offset_vector[offset];
3411
3412 #ifdef DEBUG
3413 if (eptr >= md->end_subject)
3414   printf("matching subject <null>");
3415 else
3416   {
3417   printf("matching subject ");
3418   pchars(eptr, length, TRUE, md);
3419   }
3420 printf(" against backref ");
3421 pchars(p, length, FALSE, md);
3422 printf("\n");
3423 #endif
3424
3425 /* Always fail if not enough characters left */
3426
3427 if (length > md->end_subject - eptr) return FALSE;
3428
3429 /* Separate the caselesss case for speed */
3430
3431 if ((ims & PCRE_CASELESS) != 0)
3432   {
3433   while (length-- > 0)
3434     if (md->lcc[*p++] != md->lcc[*eptr++]) return FALSE;
3435   }
3436 else
3437   { while (length-- > 0) if (*p++ != *eptr++) return FALSE; }
3438
3439 return TRUE;
3440 }
3441
3442
3443
3444 /*************************************************
3445 *         Match from current position            *
3446 *************************************************/
3447
3448 /* On entry ecode points to the first opcode, and eptr to the first character
3449 in the subject string, while eptrb holds the value of eptr at the start of the
3450 last bracketed group - used for breaking infinite loops matching zero-length
3451 strings.
3452
3453 Arguments:
3454    eptr        pointer in subject
3455    ecode       position in code
3456    offset_top  current top pointer
3457    md          pointer to "static" info for the match
3458    ims         current /i, /m, and /s options
3459    eptrb       pointer to chain of blocks containing eptr at start of
3460                  brackets - for testing for empty matches
3461    flags       can contain
3462                  match_condassert - this is an assertion condition
3463                  match_isgroup - this is the start of a bracketed group
3464
3465 Returns:       TRUE if matched
3466 */
3467
3468 static BOOL
3469 match(register const uschar *eptr, register const uschar *ecode,
3470   int offset_top, match_data *md, unsigned long int ims, eptrblock *eptrb,
3471   int flags)
3472 {
3473 unsigned long int original_ims = ims;   /* Save for resetting on ')' */
3474 eptrblock newptrb;
3475
3476 /* At the start of a bracketed group, add the current subject pointer to the
3477 stack of such pointers, to be re-instated at the end of the group when we hit
3478 the closing ket. When match() is called in other circumstances, we don't add to
3479 the stack. */
3480
3481 if ((flags & match_isgroup) != 0)
3482   {
3483   newptrb.prev = eptrb;
3484   newptrb.saved_eptr = eptr;
3485   eptrb = &newptrb;
3486   }
3487
3488 /* Now start processing the operations. */
3489
3490 for (;;)
3491   {
3492   int op = (int)*ecode;
3493   int min, max, ctype;
3494   register int i;
3495   register int c;
3496   BOOL minimize = FALSE;
3497
3498   /* Opening capturing bracket. If there is space in the offset vector, save
3499   the current subject position in the working slot at the top of the vector. We
3500   mustn't change the current values of the data slot, because they may be set
3501   from a previous iteration of this group, and be referred to by a reference
3502   inside the group.
3503
3504   If the bracket fails to match, we need to restore this value and also the
3505   values of the final offsets, in case they were set by a previous iteration of
3506   the same bracket.
3507
3508   If there isn't enough space in the offset vector, treat this as if it were a
3509   non-capturing bracket. Don't worry about setting the flag for the error case
3510   here; that is handled in the code for KET. */
3511
3512   if (op > OP_BRA)
3513     {
3514     int number = op - OP_BRA;
3515     int offset = number << 1;
3516
3517 #ifdef DEBUG
3518     printf("start bracket %d subject=", number);
3519     pchars(eptr, 16, TRUE, md);
3520     printf("\n");
3521 #endif
3522
3523     if (offset < md->offset_max)
3524       {
3525       int save_offset1 = md->offset_vector[offset];
3526       int save_offset2 = md->offset_vector[offset+1];
3527       int save_offset3 = md->offset_vector[md->offset_end - number];
3528
3529       DPRINTF(("saving %d %d %d\n", save_offset1, save_offset2, save_offset3));
3530       md->offset_vector[md->offset_end - number] = eptr - md->start_subject;
3531
3532       do
3533         {
3534         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup))
3535           return TRUE;
3536         ecode += (ecode[1] << 8) + ecode[2];
3537         }
3538       while (*ecode == OP_ALT);
3539
3540       DPRINTF(("bracket %d failed\n", number));
3541
3542       md->offset_vector[offset] = save_offset1;
3543       md->offset_vector[offset+1] = save_offset2;
3544       md->offset_vector[md->offset_end - number] = save_offset3;
3545       return FALSE;
3546       }
3547
3548     /* Insufficient room for saving captured contents */
3549
3550     else op = OP_BRA;
3551     }
3552
3553   /* Other types of node can be handled by a switch */
3554
3555   switch(op)
3556     {
3557     case OP_BRA:     /* Non-capturing bracket: optimized */
3558     DPRINTF(("start bracket 0\n"));
3559     do
3560       {
3561       if (match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup))
3562         return TRUE;
3563       ecode += (ecode[1] << 8) + ecode[2];
3564       }
3565     while (*ecode == OP_ALT);
3566     DPRINTF(("bracket 0 failed\n"));
3567     return FALSE;
3568
3569     /* Conditional group: compilation checked that there are no more than
3570     two branches. If the condition is false, skipping the first branch takes us
3571     past the end if there is only one branch, but that's OK because that is
3572     exactly what going to the ket would do. */
3573
3574     case OP_COND:
3575     if (ecode[3] == OP_CREF)         /* Condition is extraction test */
3576       {
3577       int offset = ecode[4] << 1;    /* Doubled reference number */
3578       return match(eptr,
3579         ecode + ((offset < offset_top && md->offset_vector[offset] >= 0)?
3580           5 : 3 + (ecode[1] << 8) + ecode[2]),
3581         offset_top, md, ims, eptrb, match_isgroup);
3582       }
3583
3584     /* The condition is an assertion. Call match() to evaluate it - setting
3585     the final argument TRUE causes it to stop at the end of an assertion. */
3586
3587     else
3588       {
3589       if (match(eptr, ecode+3, offset_top, md, ims, NULL,
3590           match_condassert | match_isgroup))
3591         {
3592         ecode += 3 + (ecode[4] << 8) + ecode[5];
3593         while (*ecode == OP_ALT) ecode += (ecode[1] << 8) + ecode[2];
3594         }
3595       else ecode += (ecode[1] << 8) + ecode[2];
3596       return match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup);
3597       }
3598     /* Control never reaches here */
3599
3600     /* Skip over conditional reference data if encountered (should not be) */
3601
3602     case OP_CREF:
3603     ecode += 2;
3604     break;
3605
3606     /* End of the pattern. If PCRE_NOTEMPTY is set, fail if we have matched
3607     an empty string - recursion will then try other alternatives, if any. */
3608
3609     case OP_END:
3610     if (md->notempty && eptr == md->start_match) return FALSE;
3611     md->end_match_ptr = eptr;          /* Record where we ended */
3612     md->end_offset_top = offset_top;   /* and how many extracts were taken */
3613     return TRUE;
3614
3615     /* Change option settings */
3616
3617     case OP_OPT:
3618     ims = ecode[1];
3619     ecode += 2;
3620     DPRINTF(("ims set to %02lx\n", ims));
3621     break;
3622
3623     /* Assertion brackets. Check the alternative branches in turn - the
3624     matching won't pass the KET for an assertion. If any one branch matches,
3625     the assertion is true. Lookbehind assertions have an OP_REVERSE item at the
3626     start of each branch to move the current point backwards, so the code at
3627     this level is identical to the lookahead case. */
3628
3629     case OP_ASSERT:
3630     case OP_ASSERTBACK:
3631     do
3632       {
3633       if (match(eptr, ecode+3, offset_top, md, ims, NULL, match_isgroup)) break;
3634       ecode += (ecode[1] << 8) + ecode[2];
3635       }
3636     while (*ecode == OP_ALT);
3637     if (*ecode == OP_KET) return FALSE;
3638
3639     /* If checking an assertion for a condition, return TRUE. */
3640
3641     if ((flags & match_condassert) != 0) return TRUE;
3642
3643     /* Continue from after the assertion, updating the offsets high water
3644     mark, since extracts may have been taken during the assertion. */
3645
3646     do ecode += (ecode[1] << 8) + ecode[2]; while (*ecode == OP_ALT);
3647     ecode += 3;
3648     offset_top = md->end_offset_top;
3649     continue;
3650
3651     /* Negative assertion: all branches must fail to match */
3652
3653     case OP_ASSERT_NOT:
3654     case OP_ASSERTBACK_NOT:
3655     do
3656       {
3657       if (match(eptr, ecode+3, offset_top, md, ims, NULL, match_isgroup))
3658         return FALSE;
3659       ecode += (ecode[1] << 8) + ecode[2];
3660       }
3661     while (*ecode == OP_ALT);
3662
3663     if ((flags & match_condassert) != 0) return TRUE;
3664
3665     ecode += 3;
3666     continue;
3667
3668     /* Move the subject pointer back. This occurs only at the start of
3669     each branch of a lookbehind assertion. If we are too close to the start to
3670     move back, this match function fails. When working with UTF-8 we move
3671     back a number of characters, not bytes. */
3672
3673     case OP_REVERSE:
3674 #ifdef SUPPORT_UTF8
3675     c = (ecode[1] << 8) + ecode[2];
3676     for (i = 0; i < c; i++)
3677       {
3678       eptr--;
3679       BACKCHAR(eptr)
3680       }
3681 #else
3682     eptr -= (ecode[1] << 8) + ecode[2];
3683 #endif
3684
3685     if (eptr < md->start_subject) return FALSE;
3686     ecode += 3;
3687     break;
3688
3689     /* Recursion matches the current regex, nested. If there are any capturing
3690     brackets started but not finished, we have to save their starting points
3691     and reinstate them after the recursion. However, we don't know how many
3692     such there are (offset_top records the completed total) so we just have
3693     to save all the potential data. There may be up to 99 such values, which
3694     is a bit large to put on the stack, but using malloc for small numbers
3695     seems expensive. As a compromise, the stack is used when there are fewer
3696     than 16 values to store; otherwise malloc is used. A problem is what to do
3697     if the malloc fails ... there is no way of returning to the top level with
3698     an error. Save the top 15 values on the stack, and accept that the rest
3699     may be wrong. */
3700
3701     case OP_RECURSE:
3702       {
3703       BOOL rc;
3704       int *save;
3705       int stacksave[15];
3706
3707       c = md->offset_max;
3708
3709       if (c < 16) save = stacksave; else
3710         {
3711         save = (int *)(pcre_malloc)((c+1) * sizeof(int));
3712         if (save == NULL)
3713           {
3714           save = stacksave;
3715           c = 15;
3716           }
3717         }
3718
3719       for (i = 1; i <= c; i++)
3720         save[i] = md->offset_vector[md->offset_end - i];
3721       rc = match(eptr, md->start_pattern, offset_top, md, ims, eptrb,
3722         match_isgroup);
3723       for (i = 1; i <= c; i++)
3724         md->offset_vector[md->offset_end - i] = save[i];
3725       if (save != stacksave) (pcre_free)(save);
3726       if (!rc) return FALSE;
3727
3728       /* In case the recursion has set more capturing values, save the final
3729       number, then move along the subject till after the recursive match,
3730       and advance one byte in the pattern code. */
3731
3732       offset_top = md->end_offset_top;
3733       eptr = md->end_match_ptr;
3734       ecode++;
3735       }
3736     break;
3737
3738     /* "Once" brackets are like assertion brackets except that after a match,
3739     the point in the subject string is not moved back. Thus there can never be
3740     a move back into the brackets. Check the alternative branches in turn - the
3741     matching won't pass the KET for this kind of subpattern. If any one branch
3742     matches, we carry on as at the end of a normal bracket, leaving the subject
3743     pointer. */
3744
3745     case OP_ONCE:
3746       {
3747       const uschar *prev = ecode;
3748       const uschar *saved_eptr = eptr;
3749
3750       do
3751         {
3752         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup))
3753           break;
3754         ecode += (ecode[1] << 8) + ecode[2];
3755         }
3756       while (*ecode == OP_ALT);
3757
3758       /* If hit the end of the group (which could be repeated), fail */
3759
3760       if (*ecode != OP_ONCE && *ecode != OP_ALT) return FALSE;
3761
3762       /* Continue as from after the assertion, updating the offsets high water
3763       mark, since extracts may have been taken. */
3764
3765       do ecode += (ecode[1] << 8) + ecode[2]; while (*ecode == OP_ALT);
3766
3767       offset_top = md->end_offset_top;
3768       eptr = md->end_match_ptr;
3769
3770       /* For a non-repeating ket, just continue at this level. This also
3771       happens for a repeating ket if no characters were matched in the group.
3772       This is the forcible breaking of infinite loops as implemented in Perl
3773       5.005. If there is an options reset, it will get obeyed in the normal
3774       course of events. */
3775
3776       if (*ecode == OP_KET || eptr == saved_eptr)
3777         {
3778         ecode += 3;
3779         break;
3780         }
3781
3782       /* The repeating kets try the rest of the pattern or restart from the
3783       preceding bracket, in the appropriate order. We need to reset any options
3784       that changed within the bracket before re-running it, so check the next
3785       opcode. */
3786
3787       if (ecode[3] == OP_OPT)
3788         {
3789         ims = (ims & ~PCRE_IMS) | ecode[4];
3790         DPRINTF(("ims set to %02lx at group repeat\n", ims));
3791         }
3792
3793       if (*ecode == OP_KETRMIN)
3794         {
3795         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, 0) ||
3796             match(eptr, prev, offset_top, md, ims, eptrb, match_isgroup))
3797               return TRUE;
3798         }
3799       else  /* OP_KETRMAX */
3800         {
3801         if (match(eptr, prev, offset_top, md, ims, eptrb, match_isgroup) ||
3802             match(eptr, ecode+3, offset_top, md, ims, eptrb, 0)) return TRUE;
3803         }
3804       }
3805     return FALSE;
3806
3807     /* An alternation is the end of a branch; scan along to find the end of the
3808     bracketed group and go to there. */
3809
3810     case OP_ALT:
3811     do ecode += (ecode[1] << 8) + ecode[2]; while (*ecode == OP_ALT);
3812     break;
3813
3814     /* BRAZERO and BRAMINZERO occur just before a bracket group, indicating
3815     that it may occur zero times. It may repeat infinitely, or not at all -
3816     i.e. it could be ()* or ()? in the pattern. Brackets with fixed upper
3817     repeat limits are compiled as a number of copies, with the optional ones
3818     preceded by BRAZERO or BRAMINZERO. */
3819
3820     case OP_BRAZERO:
3821       {
3822       const uschar *next = ecode+1;
3823       if (match(eptr, next, offset_top, md, ims, eptrb, match_isgroup))
3824         return TRUE;
3825       do next += (next[1] << 8) + next[2]; while (*next == OP_ALT);
3826       ecode = next + 3;
3827       }
3828     break;
3829
3830     case OP_BRAMINZERO:
3831       {
3832       const uschar *next = ecode+1;
3833       do next += (next[1] << 8) + next[2]; while (*next == OP_ALT);
3834       if (match(eptr, next+3, offset_top, md, ims, eptrb, match_isgroup))
3835         return TRUE;
3836       ecode++;
3837       }
3838     break;
3839
3840     /* End of a group, repeated or non-repeating. If we are at the end of
3841     an assertion "group", stop matching and return TRUE, but record the
3842     current high water mark for use by positive assertions. Do this also
3843     for the "once" (not-backup up) groups. */
3844
3845     case OP_KET:
3846     case OP_KETRMIN:
3847     case OP_KETRMAX:
3848       {
3849       const uschar *prev = ecode - (ecode[1] << 8) - ecode[2];
3850       const uschar *saved_eptr = eptrb->saved_eptr;
3851
3852       eptrb = eptrb->prev;    /* Back up the stack of bracket start pointers */
3853
3854       if (*prev == OP_ASSERT || *prev == OP_ASSERT_NOT ||
3855           *prev == OP_ASSERTBACK || *prev == OP_ASSERTBACK_NOT ||
3856           *prev == OP_ONCE)
3857         {
3858         md->end_match_ptr = eptr;      /* For ONCE */
3859         md->end_offset_top = offset_top;
3860         return TRUE;
3861         }
3862
3863       /* In all other cases except a conditional group we have to check the
3864       group number back at the start and if necessary complete handling an
3865       extraction by setting the offsets and bumping the high water mark. */
3866
3867       if (*prev != OP_COND)
3868         {
3869         int number = *prev - OP_BRA;
3870         int offset = number << 1;
3871
3872 #ifdef DEBUG
3873         printf("end bracket %d", number);
3874         printf("\n");
3875 #endif
3876
3877         if (number > 0)
3878           {
3879           if (offset >= md->offset_max) md->offset_overflow = TRUE; else
3880             {
3881             md->offset_vector[offset] =
3882               md->offset_vector[md->offset_end - number];
3883             md->offset_vector[offset+1] = eptr - md->start_subject;
3884             if (offset_top <= offset) offset_top = offset + 2;
3885             }
3886           }
3887         }
3888
3889       /* Reset the value of the ims flags, in case they got changed during
3890       the group. */
3891
3892       ims = original_ims;
3893       DPRINTF(("ims reset to %02lx\n", ims));
3894
3895       /* For a non-repeating ket, just continue at this level. This also
3896       happens for a repeating ket if no characters were matched in the group.
3897       This is the forcible breaking of infinite loops as implemented in Perl
3898       5.005. If there is an options reset, it will get obeyed in the normal
3899       course of events. */
3900
3901       if (*ecode == OP_KET || eptr == saved_eptr)
3902         {
3903         ecode += 3;
3904         break;
3905         }
3906
3907       /* The repeating kets try the rest of the pattern or restart from the
3908       preceding bracket, in the appropriate order. */
3909
3910       if (*ecode == OP_KETRMIN)
3911         {
3912         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, 0) ||
3913             match(eptr, prev, offset_top, md, ims, eptrb, match_isgroup))
3914               return TRUE;
3915         }
3916       else  /* OP_KETRMAX */
3917         {
3918         if (match(eptr, prev, offset_top, md, ims, eptrb, match_isgroup) ||
3919             match(eptr, ecode+3, offset_top, md, ims, eptrb, 0)) return TRUE;
3920         }
3921       }
3922     return FALSE;
3923
3924     /* Start of subject unless notbol, or after internal newline if multiline */
3925
3926     case OP_CIRC:
3927     if (md->notbol && eptr == md->start_subject) return FALSE;
3928     if ((ims & PCRE_MULTILINE) != 0)
3929       {
3930       if (eptr != md->start_subject && eptr[-1] != '\n') return FALSE;
3931       ecode++;
3932       break;
3933       }
3934     /* ... else fall through */
3935
3936     /* Start of subject assertion */
3937
3938     case OP_SOD:
3939     if (eptr != md->start_subject) return FALSE;
3940     ecode++;
3941     break;
3942
3943     /* Assert before internal newline if multiline, or before a terminating
3944     newline unless endonly is set, else end of subject unless noteol is set. */
3945
3946     case OP_DOLL:
3947     if ((ims & PCRE_MULTILINE) != 0)
3948       {
3949       if (eptr < md->end_subject) { if (*eptr != '\n') return FALSE; }
3950         else { if (md->noteol) return FALSE; }
3951       ecode++;
3952       break;
3953       }
3954     else
3955       {
3956       if (md->noteol) return FALSE;
3957       if (!md->endonly)
3958         {
3959         if (eptr < md->end_subject - 1 ||
3960            (eptr == md->end_subject - 1 && *eptr != '\n')) return FALSE;
3961
3962         ecode++;
3963         break;
3964         }
3965       }
3966     /* ... else fall through */
3967
3968     /* End of subject assertion (\z) */
3969
3970     case OP_EOD:
3971     if (eptr < md->end_subject) return FALSE;
3972     ecode++;
3973     break;
3974
3975     /* End of subject or ending \n assertion (\Z) */
3976
3977     case OP_EODN:
3978     if (eptr < md->end_subject - 1 ||
3979        (eptr == md->end_subject - 1 && *eptr != '\n')) return FALSE;
3980     ecode++;
3981     break;
3982
3983     /* Word boundary assertions */
3984
3985     case OP_NOT_WORD_BOUNDARY:
3986     case OP_WORD_BOUNDARY:
3987       {
3988       BOOL prev_is_word = (eptr != md->start_subject) &&
3989         ((md->ctypes[eptr[-1]] & ctype_word) != 0);
3990       BOOL cur_is_word = (eptr < md->end_subject) &&
3991         ((md->ctypes[*eptr] & ctype_word) != 0);
3992       if ((*ecode++ == OP_WORD_BOUNDARY)?
3993            cur_is_word == prev_is_word : cur_is_word != prev_is_word)
3994         return FALSE;
3995       }
3996     break;
3997
3998     /* Match a single character type; inline for speed */
3999
4000     case OP_ANY:
4001     if ((ims & PCRE_DOTALL) == 0 && eptr < md->end_subject && *eptr == '\n')
4002       return FALSE;
4003     if (eptr++ >= md->end_subject) return FALSE;
4004 #ifdef SUPPORT_UTF8
4005     if (md->utf8)
4006       while (eptr < md->end_subject && (*eptr & 0xc0) == 0x80) eptr++;
4007 #endif
4008     ecode++;
4009     break;
4010
4011     case OP_NOT_DIGIT:
4012     if (eptr >= md->end_subject ||
4013        (md->ctypes[*eptr++] & ctype_digit) != 0)
4014       return FALSE;
4015     ecode++;
4016     break;
4017
4018     case OP_DIGIT:
4019     if (eptr >= md->end_subject ||
4020        (md->ctypes[*eptr++] & ctype_digit) == 0)
4021       return FALSE;
4022     ecode++;
4023     break;
4024
4025     case OP_NOT_WHITESPACE:
4026     if (eptr >= md->end_subject ||
4027        (md->ctypes[*eptr++] & ctype_space) != 0)
4028       return FALSE;
4029     ecode++;
4030     break;
4031
4032     case OP_WHITESPACE:
4033     if (eptr >= md->end_subject ||
4034        (md->ctypes[*eptr++] & ctype_space) == 0)
4035       return FALSE;
4036     ecode++;
4037     break;
4038
4039     case OP_NOT_WORDCHAR:
4040     if (eptr >= md->end_subject ||
4041        (md->ctypes[*eptr++] & ctype_word) != 0)
4042       return FALSE;
4043     ecode++;
4044     break;
4045
4046     case OP_WORDCHAR:
4047     if (eptr >= md->end_subject ||
4048        (md->ctypes[*eptr++] & ctype_word) == 0)
4049       return FALSE;
4050     ecode++;
4051     break;
4052
4053     /* Match a back reference, possibly repeatedly. Look past the end of the
4054     item to see if there is repeat information following. The code is similar
4055     to that for character classes, but repeated for efficiency. Then obey
4056     similar code to character type repeats - written out again for speed.
4057     However, if the referenced string is the empty string, always treat
4058     it as matched, any number of times (otherwise there could be infinite
4059     loops). */
4060
4061     case OP_REF:
4062       {
4063       int length;
4064       int offset = ecode[1] << 1;                /* Doubled reference number */
4065       ecode += 2;                                /* Advance past the item */
4066
4067       /* If the reference is unset, set the length to be longer than the amount
4068       of subject left; this ensures that every attempt at a match fails. We
4069       can't just fail here, because of the possibility of quantifiers with zero
4070       minima. */
4071
4072       length = (offset >= offset_top || md->offset_vector[offset] < 0)?
4073         md->end_subject - eptr + 1 :
4074         md->offset_vector[offset+1] - md->offset_vector[offset];
4075
4076       /* Set up for repetition, or handle the non-repeated case */
4077
4078       switch (*ecode)
4079         {
4080         case OP_CRSTAR:
4081         case OP_CRMINSTAR:
4082         case OP_CRPLUS:
4083         case OP_CRMINPLUS:
4084         case OP_CRQUERY:
4085         case OP_CRMINQUERY:
4086         c = *ecode++ - OP_CRSTAR;
4087         minimize = (c & 1) != 0;
4088         min = rep_min[c];                 /* Pick up values from tables; */
4089         max = rep_max[c];                 /* zero for max => infinity */
4090         if (max == 0) max = INT_MAX;
4091         break;
4092
4093         case OP_CRRANGE:
4094         case OP_CRMINRANGE:
4095         minimize = (*ecode == OP_CRMINRANGE);
4096         min = (ecode[1] << 8) + ecode[2];
4097         max = (ecode[3] << 8) + ecode[4];
4098         if (max == 0) max = INT_MAX;
4099         ecode += 5;
4100         break;
4101
4102         default:               /* No repeat follows */
4103         if (!match_ref(offset, eptr, length, md, ims)) return FALSE;
4104         eptr += length;
4105         continue;              /* With the main loop */
4106         }
4107
4108       /* If the length of the reference is zero, just continue with the
4109       main loop. */
4110
4111       if (length == 0) continue;
4112
4113       /* First, ensure the minimum number of matches are present. We get back
4114       the length of the reference string explicitly rather than passing the
4115       address of eptr, so that eptr can be a register variable. */
4116
4117       for (i = 1; i <= min; i++)
4118         {
4119         if (!match_ref(offset, eptr, length, md, ims)) return FALSE;
4120         eptr += length;
4121         }
4122
4123       /* If min = max, continue at the same level without recursion.
4124       They are not both allowed to be zero. */
4125
4126       if (min == max) continue;
4127
4128       /* If minimizing, keep trying and advancing the pointer */
4129
4130       if (minimize)
4131         {
4132         for (i = min;; i++)
4133           {
4134           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4135             return TRUE;
4136           if (i >= max || !match_ref(offset, eptr, length, md, ims))
4137             return FALSE;
4138           eptr += length;
4139           }
4140         /* Control never gets here */
4141         }
4142
4143       /* If maximizing, find the longest string and work backwards */
4144
4145       else
4146         {
4147         const uschar *pp = eptr;
4148         for (i = min; i < max; i++)
4149           {
4150           if (!match_ref(offset, eptr, length, md, ims)) break;
4151           eptr += length;
4152           }
4153         while (eptr >= pp)
4154           {
4155           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4156             return TRUE;
4157           eptr -= length;
4158           }
4159         return FALSE;
4160         }
4161       }
4162     /* Control never gets here */
4163
4164
4165
4166     /* Match a character class, possibly repeatedly. Look past the end of the
4167     item to see if there is repeat information following. Then obey similar
4168     code to character type repeats - written out again for speed. */
4169
4170     case OP_CLASS:
4171       {
4172       const uschar *data = ecode + 1;  /* Save for matching */
4173       ecode += 33;                     /* Advance past the item */
4174
4175       switch (*ecode)
4176         {
4177         case OP_CRSTAR:
4178         case OP_CRMINSTAR:
4179         case OP_CRPLUS:
4180         case OP_CRMINPLUS:
4181         case OP_CRQUERY:
4182         case OP_CRMINQUERY:
4183         c = *ecode++ - OP_CRSTAR;
4184         minimize = (c & 1) != 0;
4185         min = rep_min[c];                 /* Pick up values from tables; */
4186         max = rep_max[c];                 /* zero for max => infinity */
4187         if (max == 0) max = INT_MAX;
4188         break;
4189
4190         case OP_CRRANGE:
4191         case OP_CRMINRANGE:
4192         minimize = (*ecode == OP_CRMINRANGE);
4193         min = (ecode[1] << 8) + ecode[2];
4194         max = (ecode[3] << 8) + ecode[4];
4195         if (max == 0) max = INT_MAX;
4196         ecode += 5;
4197         break;
4198
4199         default:               /* No repeat follows */
4200         min = max = 1;
4201         break;
4202         }
4203
4204       /* First, ensure the minimum number of matches are present. */
4205
4206       for (i = 1; i <= min; i++)
4207         {
4208         if (eptr >= md->end_subject) return FALSE;
4209         GETCHARINC(c, eptr)         /* Get character; increment eptr */
4210
4211 #ifdef SUPPORT_UTF8
4212         /* We do not yet support class members > 255 */
4213         if (c > 255) return FALSE;
4214 #endif
4215
4216         if ((data[c/8] & (1 << (c&7))) != 0) continue;
4217         return FALSE;
4218         }
4219
4220       /* If max == min we can continue with the main loop without the
4221       need to recurse. */
4222
4223       if (min == max) continue;
4224
4225       /* If minimizing, keep testing the rest of the expression and advancing
4226       the pointer while it matches the class. */
4227
4228       if (minimize)
4229         {
4230         for (i = min;; i++)
4231           {
4232           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4233             return TRUE;
4234           if (i >= max || eptr >= md->end_subject) return FALSE;
4235           GETCHARINC(c, eptr)       /* Get character; increment eptr */
4236
4237 #ifdef SUPPORT_UTF8
4238           /* We do not yet support class members > 255 */
4239           if (c > 255) return FALSE;
4240 #endif
4241           if ((data[c/8] & (1 << (c&7))) != 0) continue;
4242           return FALSE;
4243           }
4244         /* Control never gets here */
4245         }
4246
4247       /* If maximizing, find the longest possible run, then work backwards. */
4248
4249       else
4250         {
4251         const uschar *pp = eptr;
4252         int len = 1;
4253         for (i = min; i < max; i++)
4254           {
4255           if (eptr >= md->end_subject) break;
4256           GETCHARLEN(c, eptr, len)  /* Get character, set length if UTF-8 */
4257
4258 #ifdef SUPPORT_UTF8
4259           /* We do not yet support class members > 255 */
4260           if (c > 255) break;
4261 #endif
4262           if ((data[c/8] & (1 << (c&7))) == 0) break;
4263           eptr += len;
4264           }
4265
4266         while (eptr >= pp)
4267           {
4268           if (match(eptr--, ecode, offset_top, md, ims, eptrb, 0))
4269             return TRUE;
4270
4271 #ifdef SUPPORT_UTF8
4272           BACKCHAR(eptr)
4273 #endif
4274           }
4275         return FALSE;
4276         }
4277       }
4278     /* Control never gets here */
4279
4280     /* Match a run of characters */
4281
4282     case OP_CHARS:
4283       {
4284       register int length = ecode[1];
4285       ecode += 2;
4286
4287 #ifdef DEBUG    /* Sigh. Some compilers never learn. */
4288       if (eptr >= md->end_subject)
4289         printf("matching subject <null> against pattern ");
4290       else
4291         {
4292         printf("matching subject ");
4293         pchars(eptr, length, TRUE, md);
4294         printf(" against pattern ");
4295         }
4296       pchars(ecode, length, FALSE, md);
4297       printf("\n");
4298 #endif
4299
4300       if (length > md->end_subject - eptr) return FALSE;
4301       if ((ims & PCRE_CASELESS) != 0)
4302         {
4303         while (length-- > 0)
4304           if (md->lcc[*ecode++] != md->lcc[*eptr++])
4305             return FALSE;
4306         }
4307       else
4308         {
4309         while (length-- > 0) if (*ecode++ != *eptr++) return FALSE;
4310         }
4311       }
4312     break;
4313
4314     /* Match a single character repeatedly; different opcodes share code. */
4315
4316     case OP_EXACT:
4317     min = max = (ecode[1] << 8) + ecode[2];
4318     ecode += 3;
4319     goto REPEATCHAR;
4320
4321     case OP_UPTO:
4322     case OP_MINUPTO:
4323     min = 0;
4324     max = (ecode[1] << 8) + ecode[2];
4325     minimize = *ecode == OP_MINUPTO;
4326     ecode += 3;
4327     goto REPEATCHAR;
4328
4329     case OP_STAR:
4330     case OP_MINSTAR:
4331     case OP_PLUS:
4332     case OP_MINPLUS:
4333     case OP_QUERY:
4334     case OP_MINQUERY:
4335     c = *ecode++ - OP_STAR;
4336     minimize = (c & 1) != 0;
4337     min = rep_min[c];                 /* Pick up values from tables; */
4338     max = rep_max[c];                 /* zero for max => infinity */
4339     if (max == 0) max = INT_MAX;
4340
4341     /* Common code for all repeated single-character matches. We can give
4342     up quickly if there are fewer than the minimum number of characters left in
4343     the subject. */
4344
4345     REPEATCHAR:
4346     if (min > md->end_subject - eptr) return FALSE;
4347     c = *ecode++;
4348
4349     /* The code is duplicated for the caseless and caseful cases, for speed,
4350     since matching characters is likely to be quite common. First, ensure the
4351     minimum number of matches are present. If min = max, continue at the same
4352     level without recursing. Otherwise, if minimizing, keep trying the rest of
4353     the expression and advancing one matching character if failing, up to the
4354     maximum. Alternatively, if maximizing, find the maximum number of
4355     characters and work backwards. */
4356
4357     DPRINTF(("matching %c{%d,%d} against subject %.*s\n", c, min, max,
4358       max, eptr));
4359
4360     if ((ims & PCRE_CASELESS) != 0)
4361       {
4362       c = md->lcc[c];
4363       for (i = 1; i <= min; i++)
4364         if (c != md->lcc[*eptr++]) return FALSE;
4365       if (min == max) continue;
4366       if (minimize)
4367         {
4368         for (i = min;; i++)
4369           {
4370           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4371             return TRUE;
4372           if (i >= max || eptr >= md->end_subject ||
4373               c != md->lcc[*eptr++])
4374             return FALSE;
4375           }
4376         /* Control never gets here */
4377         }
4378       else
4379         {
4380         const uschar *pp = eptr;
4381         for (i = min; i < max; i++)
4382           {
4383           if (eptr >= md->end_subject || c != md->lcc[*eptr]) break;
4384           eptr++;
4385           }
4386         while (eptr >= pp)
4387           if (match(eptr--, ecode, offset_top, md, ims, eptrb, 0))
4388             return TRUE;
4389         return FALSE;
4390         }
4391       /* Control never gets here */
4392       }
4393
4394     /* Caseful comparisons */
4395
4396     else
4397       {
4398       for (i = 1; i <= min; i++) if (c != *eptr++) return FALSE;
4399       if (min == max) continue;
4400       if (minimize)
4401         {
4402         for (i = min;; i++)
4403           {
4404           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4405             return TRUE;
4406           if (i >= max || eptr >= md->end_subject || c != *eptr++) return FALSE;
4407           }
4408         /* Control never gets here */
4409         }
4410       else
4411         {
4412         const uschar *pp = eptr;
4413         for (i = min; i < max; i++)
4414           {
4415           if (eptr >= md->end_subject || c != *eptr) break;
4416           eptr++;
4417           }
4418         while (eptr >= pp)
4419          if (match(eptr--, ecode, offset_top, md, ims, eptrb, 0))
4420            return TRUE;
4421         return FALSE;
4422         }
4423       }
4424     /* Control never gets here */
4425
4426     /* Match a negated single character */
4427
4428     case OP_NOT:
4429     if (eptr >= md->end_subject) return FALSE;
4430     ecode++;
4431     if ((ims & PCRE_CASELESS) != 0)
4432       {
4433       if (md->lcc[*ecode++] == md->lcc[*eptr++]) return FALSE;
4434       }
4435     else
4436       {
4437       if (*ecode++ == *eptr++) return FALSE;
4438       }
4439     break;
4440
4441     /* Match a negated single character repeatedly. This is almost a repeat of
4442     the code for a repeated single character, but I haven't found a nice way of
4443     commoning these up that doesn't require a test of the positive/negative
4444     option for each character match. Maybe that wouldn't add very much to the
4445     time taken, but character matching *is* what this is all about... */
4446
4447     case OP_NOTEXACT:
4448     min = max = (ecode[1] << 8) + ecode[2];
4449     ecode += 3;
4450     goto REPEATNOTCHAR;
4451
4452     case OP_NOTUPTO:
4453     case OP_NOTMINUPTO:
4454     min = 0;
4455     max = (ecode[1] << 8) + ecode[2];
4456     minimize = *ecode == OP_NOTMINUPTO;
4457     ecode += 3;
4458     goto REPEATNOTCHAR;
4459
4460     case OP_NOTSTAR:
4461     case OP_NOTMINSTAR:
4462     case OP_NOTPLUS:
4463     case OP_NOTMINPLUS:
4464     case OP_NOTQUERY:
4465     case OP_NOTMINQUERY:
4466     c = *ecode++ - OP_NOTSTAR;
4467     minimize = (c & 1) != 0;
4468     min = rep_min[c];                 /* Pick up values from tables; */
4469     max = rep_max[c];                 /* zero for max => infinity */
4470     if (max == 0) max = INT_MAX;
4471
4472     /* Common code for all repeated single-character matches. We can give
4473     up quickly if there are fewer than the minimum number of characters left in
4474     the subject. */
4475
4476     REPEATNOTCHAR:
4477     if (min > md->end_subject - eptr) return FALSE;
4478     c = *ecode++;
4479
4480     /* The code is duplicated for the caseless and caseful cases, for speed,
4481     since matching characters is likely to be quite common. First, ensure the
4482     minimum number of matches are present. If min = max, continue at the same
4483     level without recursing. Otherwise, if minimizing, keep trying the rest of
4484     the expression and advancing one matching character if failing, up to the
4485     maximum. Alternatively, if maximizing, find the maximum number of
4486     characters and work backwards. */
4487
4488     DPRINTF(("negative matching %c{%d,%d} against subject %.*s\n", c, min, max,
4489       max, eptr));
4490
4491     if ((ims & PCRE_CASELESS) != 0)
4492       {
4493       c = md->lcc[c];
4494       for (i = 1; i <= min; i++)
4495         if (c == md->lcc[*eptr++]) return FALSE;
4496       if (min == max) continue;
4497       if (minimize)
4498         {
4499         for (i = min;; i++)
4500           {
4501           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4502             return TRUE;
4503           if (i >= max || eptr >= md->end_subject ||
4504               c == md->lcc[*eptr++])
4505             return FALSE;
4506           }
4507         /* Control never gets here */
4508         }
4509       else
4510         {
4511         const uschar *pp = eptr;
4512         for (i = min; i < max; i++)
4513           {
4514           if (eptr >= md->end_subject || c == md->lcc[*eptr]) break;
4515           eptr++;
4516           }
4517         while (eptr >= pp)
4518           if (match(eptr--, ecode, offset_top, md, ims, eptrb, 0))
4519             return TRUE;
4520         return FALSE;
4521         }
4522       /* Control never gets here */
4523       }
4524
4525     /* Caseful comparisons */
4526
4527     else
4528       {
4529       for (i = 1; i <= min; i++) if (c == *eptr++) return FALSE;
4530       if (min == max) continue;
4531       if (minimize)
4532         {
4533         for (i = min;; i++)
4534           {
4535           if (match(eptr, ecode, offset_top, md, ims, eptrb, 0))
4536             return TRUE;
4537           if (i >= max || eptr >= md->end_subject || c == *eptr++) return FALSE;
4538           }
4539         /* Control never gets here */
4540         }
4541       else
4542         {
4543         const uschar *pp = eptr;
4544         for (i = min; i < max; i++)
4545           {
4546           if (eptr >= md->end_subject || c == *eptr) break;
4547           eptr++;
4548           }
4549         while (eptr >= pp)
4550          if (match(eptr--, ecode, offset_top, md, ims, eptrb, 0))
4551            return TRUE;
4552         return FALSE;
4553         }
4554       }
4555     /* Control never gets here */
4556
4557     /* Match a single character type repeatedly; several different opcodes
4558     share code. This is very similar to the code for single characters, but we
4559     repeat it in the interests of efficiency. */
4560
4561     case OP_TYPEEXACT:
4562     min = max = (ecode[1] << 8) + ecode[2];
4563     minimize = TRUE;
4564     ecode += 3;
4565     goto REPEATTYPE;
4566
4567     case OP_TYPEUPTO:
4568     case OP_TYPEMINUPTO:
4569     min = 0;
4570     max = (ecode[1] << 8) + ecode[2];
4571     minimize = *ecode == OP_TYPEMINUPTO;
4572     ecode += 3;
4573     goto REPEATTYPE;
4574
4575     case OP_TYPESTAR:
4576     case OP_TYPEMINSTAR:
4577     case OP_TYPEPLUS:
4578     case OP_TYPEMINPLUS:
4579     case OP_TYPEQUERY:
4580     case OP_TYPEMINQUERY:
4581     c = *ecode++ - OP_TYPESTAR;
4582     minimize = (c & 1) != 0;
4583     min = rep_min[c];                 /* Pick up values from tables; */
4584     max = rep_max[c];                 /* zero for max => infinity */
4585     if (max == 0) max = INT_MAX;
4586
4587     /* Common code for all repeated single character type matches */
4588
4589     REPEATTYPE:
4590     ctype = *ecode++;      /* Code for the character type */
4591
4592     /* First, ensure the minimum number of matches are present. Use inline
4593     code for maximizing the speed, and do the type test once at the start
4594     (i.e. keep it out of the loop). Also we can test that there are at least
4595     the minimum number of bytes before we start, except when doing '.' in
4596     UTF8 mode. Leave the test in in all cases; in the special case we have
4597     to test after each character. */
4598
4599     if (min > md->end_subject - eptr) return FALSE;
4600     if (min > 0) switch(ctype)
4601       {
4602       case OP_ANY:
4603 #ifdef SUPPORT_UTF8
4604       if (md->utf8)
4605         {
4606         for (i = 1; i <= min; i++)
4607           {
4608           if (eptr >= md->end_subject ||
4609              (*eptr++ == '\n' && (ims & PCRE_DOTALL) == 0))
4610             return FALSE;
4611           while (eptr < md->end_subject && (*eptr & 0xc0) == 0x80) eptr++;
4612           }
4613         break;
4614         }
4615 #endif
4616       /* Non-UTF8 can be faster */
4617       if ((ims & PCRE_DOTALL) == 0)
4618         { for (i = 1; i <= min; i++) if (*eptr++ == '\n') return FALSE; }
4619       else eptr += min;
4620       break;
4621
4622       case OP_NOT_DIGIT:
4623       for (i = 1; i <= min; i++)
4624         if ((md->ctypes[*eptr++] & ctype_digit) != 0) return FALSE;
4625       break;
4626
4627       case OP_DIGIT:
4628       for (i = 1; i <= min; i++)
4629         if ((md->ctypes[*eptr++] & ctype_digit) == 0) return FALSE;
4630       break;
4631
4632       case OP_NOT_WHITESPACE:
4633       for (i = 1; i <= min; i++)
4634         if ((md->ctypes[*eptr++] & ctype_space) != 0) return FALSE;
4635       break;
4636
4637       case OP_WHITESPACE:
4638       for (i = 1; i <= min; i++)
4639         if ((md->ctypes[*eptr++] & ctype_space) == 0) return FALSE;
4640       break;
4641
4642       case OP_NOT_WORDCHAR:
4643       for (i = 1; i <= min; i++)
4644         if ((md->ctypes[*eptr++] & ctype_word) != 0)
4645           return FALSE;
4646       break;
4647
4648       case OP_WORDCHAR:
4649       for (i = 1; i <= min; i++)
4650         if ((md->ctypes[*eptr++] & ctype_word) == 0)
4651           return FALSE;
4652       break;
4653       }
4654
4655     /* If min = max, continue at the same level without recursing */
4656
4657     if (min == max) continue;
4658
4659     /* If minimizing, we have to test the rest of the pattern before each
4660     subsequent match. */
4661
4662     if (minimize)
4663       {
4664       for (i = min;; i++)
4665         {
4666         if (match(eptr, ecode, offset_top, md, ims, eptrb, 0)) return TRUE;
4667         if (i >= max || eptr >= md->end_subject) return FALSE;
4668
4669         c = *eptr++;
4670         switch(ctype)
4671           {
4672           case OP_ANY:
4673           if ((ims & PCRE_DOTALL) == 0 && c == '\n') return FALSE;
4674 #ifdef SUPPORT_UTF8
4675           if (md->utf8)
4676             while (eptr < md->end_subject && (*eptr & 0xc0) == 0x80) eptr++;
4677 #endif
4678           break;
4679
4680           case OP_NOT_DIGIT:
4681           if ((md->ctypes[c] & ctype_digit) != 0) return FALSE;
4682           break;
4683
4684           case OP_DIGIT:
4685           if ((md->ctypes[c] & ctype_digit) == 0) return FALSE;
4686           break;
4687
4688           case OP_NOT_WHITESPACE:
4689           if ((md->ctypes[c] & ctype_space) != 0) return FALSE;
4690           break;
4691
4692           case OP_WHITESPACE:
4693           if  ((md->ctypes[c] & ctype_space) == 0) return FALSE;
4694           break;
4695
4696           case OP_NOT_WORDCHAR:
4697           if ((md->ctypes[c] & ctype_word) != 0) return FALSE;
4698           break;
4699
4700           case OP_WORDCHAR:
4701           if ((md->ctypes[c] & ctype_word) == 0) return FALSE;
4702           break;
4703           }
4704         }
4705       /* Control never gets here */
4706       }
4707
4708     /* If maximizing it is worth using inline code for speed, doing the type
4709     test once at the start (i.e. keep it out of the loop). */
4710
4711     else
4712       {
4713       const uschar *pp = eptr;
4714       switch(ctype)
4715         {
4716         case OP_ANY:
4717
4718         /* Special code is required for UTF8, but when the maximum is unlimited
4719         we don't need it. */
4720
4721 #ifdef SUPPORT_UTF8
4722         if (md->utf8 && max < INT_MAX)
4723           {
4724           if ((ims & PCRE_DOTALL) == 0)
4725             {
4726             for (i = min; i < max; i++)
4727               {
4728               if (eptr >= md->end_subject || *eptr++ == '\n') break;
4729               while (eptr < md->end_subject && (*eptr & 0xc0) == 0x80) eptr++;
4730               }
4731             }
4732           else
4733             {
4734             for (i = min; i < max; i++)
4735               {
4736               eptr++;
4737               while (eptr < md->end_subject && (*eptr & 0xc0) == 0x80) eptr++;
4738               }
4739             }
4740           break;
4741           }
4742 #endif
4743         /* Non-UTF8 can be faster */
4744         if ((ims & PCRE_DOTALL) == 0)
4745           {
4746           for (i = min; i < max; i++)
4747             {
4748             if (eptr >= md->end_subject || *eptr == '\n') break;
4749             eptr++;
4750             }
4751           }
4752         else
4753           {
4754           c = max - min;
4755           if (c > md->end_subject - eptr) c = md->end_subject - eptr;
4756           eptr += c;
4757           }
4758         break;
4759
4760         case OP_NOT_DIGIT:
4761         for (i = min; i < max; i++)
4762           {
4763           if (eptr >= md->end_subject || (md->ctypes[*eptr] & ctype_digit) != 0)
4764             break;
4765           eptr++;
4766           }
4767         break;
4768
4769         case OP_DIGIT:
4770         for (i = min; i < max; i++)
4771           {
4772           if (eptr >= md->end_subject || (md->ctypes[*eptr] & ctype_digit) == 0)
4773             break;
4774           eptr++;
4775           }
4776         break;
4777
4778         case OP_NOT_WHITESPACE:
4779         for (i = min; i < max; i++)
4780           {
4781           if (eptr >= md->end_subject || (md->ctypes[*eptr] & ctype_space) != 0)
4782             break;
4783           eptr++;
4784           }
4785         break;
4786
4787         case OP_WHITESPACE:
4788         for (i = min; i < max; i++)
4789           {
4790           if (eptr >= md->end_subject || (md->ctypes[*eptr] & ctype_space) == 0)
4791             break;
4792           eptr++;
4793           }
4794         break;
4795
4796         case OP_NOT_WORDCHAR:
4797         for (i = min; i < max; i++)
4798           {
4799           if (eptr >= md->end_subject || (md->ctypes[*eptr] & ctype_word) != 0)
4800             break;
4801           eptr++;
4802           }
4803         break;
4804
4805         case OP_WORDCHAR:
4806         for (i = min; i < max; i++)
4807           {
4808           if (eptr >= md->end_subject || (md->ctypes[*eptr] & ctype_word) == 0)
4809             break;
4810           eptr++;
4811           }
4812         break;
4813         }
4814
4815       while (eptr >= pp)
4816         {
4817         if (match(eptr--, ecode, offset_top, md, ims, eptrb, 0))
4818           return TRUE;
4819 #ifdef SUPPORT_UTF8
4820         if (md->utf8)
4821           while (eptr > pp && (*eptr & 0xc0) == 0x80) eptr--;
4822 #endif
4823         }
4824       return FALSE;
4825       }
4826     /* Control never gets here */
4827
4828     /* There's been some horrible disaster. */
4829
4830     default:
4831     DPRINTF(("Unknown opcode %d\n", *ecode));
4832     md->errorcode = PCRE_ERROR_UNKNOWN_NODE;
4833     return FALSE;
4834     }
4835
4836   /* Do not stick any code in here without much thought; it is assumed
4837   that "continue" in the code above comes out to here to repeat the main
4838   loop. */
4839
4840   }             /* End of main loop */
4841 /* Control never reaches here */
4842 }
4843
4844
4845
4846
4847 /*************************************************
4848 *         Execute a Regular Expression           *
4849 *************************************************/
4850
4851 /* This function applies a compiled re to a subject string and picks out
4852 portions of the string if it matches. Two elements in the vector are set for
4853 each substring: the offsets to the start and end of the substring.
4854
4855 Arguments:
4856   external_re     points to the compiled expression
4857   external_extra  points to "hints" from pcre_study() or is NULL
4858   subject         points to the subject string
4859   length          length of subject string (may contain binary zeros)
4860   start_offset    where to start in the subject string
4861   options         option bits
4862   offsets         points to a vector of ints to be filled in with offsets
4863   offsetcount     the number of elements in the vector
4864
4865 Returns:          > 0 => success; value is the number of elements filled in
4866                   = 0 => success, but offsets is not big enough
4867                    -1 => failed to match
4868                  < -1 => some kind of unexpected problem
4869 */
4870
4871 int
4872 pcre_exec(const pcre *external_re, const pcre_extra *external_extra,
4873   const char *subject, int length, int start_offset, int options, int *offsets,
4874   int offsetcount)
4875 {
4876 int resetcount, ocount;
4877 int first_char = -1;
4878 int req_char = -1;
4879 int req_char2 = -1;
4880 unsigned long int ims = 0;
4881 match_data match_block;
4882 const uschar *start_bits = NULL;
4883 const uschar *start_match = (const uschar *)subject + start_offset;
4884 const uschar *end_subject;
4885 const uschar *req_char_ptr = start_match - 1;
4886 const real_pcre *re = (const real_pcre *)external_re;
4887 const real_pcre_extra *extra = (const real_pcre_extra *)external_extra;
4888 BOOL using_temporary_offsets = FALSE;
4889 BOOL anchored = ((re->options | options) & PCRE_ANCHORED) != 0;
4890 BOOL startline = (re->options & PCRE_STARTLINE) != 0;
4891
4892 if ((options & ~PUBLIC_EXEC_OPTIONS) != 0) return PCRE_ERROR_BADOPTION;
4893
4894 if (re == NULL || subject == NULL ||
4895    (offsets == NULL && offsetcount > 0)) return PCRE_ERROR_NULL;
4896 if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
4897
4898 match_block.start_pattern = re->code;
4899 match_block.start_subject = (const uschar *)subject;
4900 match_block.end_subject = match_block.start_subject + length;
4901 end_subject = match_block.end_subject;
4902
4903 match_block.endonly = (re->options & PCRE_DOLLAR_ENDONLY) != 0;
4904 match_block.utf8 = (re->options & PCRE_UTF8) != 0;
4905
4906 match_block.notbol = (options & PCRE_NOTBOL) != 0;
4907 match_block.noteol = (options & PCRE_NOTEOL) != 0;
4908 match_block.notempty = (options & PCRE_NOTEMPTY) != 0;
4909
4910 match_block.errorcode = PCRE_ERROR_NOMATCH;     /* Default error */
4911
4912 match_block.lcc = re->tables + lcc_offset;
4913 match_block.ctypes = re->tables + ctypes_offset;
4914
4915 /* The ims options can vary during the matching as a result of the presence
4916 of (?ims) items in the pattern. They are kept in a local variable so that
4917 restoring at the exit of a group is easy. */
4918
4919 ims = re->options & (PCRE_CASELESS|PCRE_MULTILINE|PCRE_DOTALL);
4920
4921 /* If the expression has got more back references than the offsets supplied can
4922 hold, we get a temporary bit of working store to use during the matching.
4923 Otherwise, we can use the vector supplied, rounding down its size to a multiple
4924 of 3. */
4925
4926 ocount = offsetcount - (offsetcount % 3);
4927
4928 if (re->top_backref > 0 && re->top_backref >= ocount/3)
4929   {
4930   ocount = re->top_backref * 3 + 3;
4931   match_block.offset_vector = (int *)(pcre_malloc)(ocount * sizeof(int));
4932   if (match_block.offset_vector == NULL) return PCRE_ERROR_NOMEMORY;
4933   using_temporary_offsets = TRUE;
4934   DPRINTF(("Got memory to hold back references\n"));
4935   }
4936 else match_block.offset_vector = offsets;
4937
4938 match_block.offset_end = ocount;
4939 match_block.offset_max = (2*ocount)/3;
4940 match_block.offset_overflow = FALSE;
4941
4942 /* Compute the minimum number of offsets that we need to reset each time. Doing
4943 this makes a huge difference to execution time when there aren't many brackets
4944 in the pattern. */
4945
4946 resetcount = 2 + re->top_bracket * 2;
4947 if (resetcount > offsetcount) resetcount = ocount;
4948
4949 /* Reset the working variable associated with each extraction. These should
4950 never be used unless previously set, but they get saved and restored, and so we
4951 initialize them to avoid reading uninitialized locations. */
4952
4953 if (match_block.offset_vector != NULL)
4954   {
4955   register int *iptr = match_block.offset_vector + ocount;
4956   register int *iend = iptr - resetcount/2 + 1;
4957   while (--iptr >= iend) *iptr = -1;
4958   }
4959
4960 /* Set up the first character to match, if available. The first_char value is
4961 never set for an anchored regular expression, but the anchoring may be forced
4962 at run time, so we have to test for anchoring. The first char may be unset for
4963 an unanchored pattern, of course. If there's no first char and the pattern was
4964 studied, there may be a bitmap of possible first characters. */
4965
4966 if (!anchored)
4967   {
4968   if ((re->options & PCRE_FIRSTSET) != 0)
4969     {
4970     first_char = re->first_char;
4971     if ((ims & PCRE_CASELESS) != 0) first_char = match_block.lcc[first_char];
4972     }
4973   else
4974     if (!startline && extra != NULL &&
4975       (extra->options & PCRE_STUDY_MAPPED) != 0)
4976         start_bits = extra->start_bits;
4977   }
4978
4979 /* For anchored or unanchored matches, there may be a "last known required
4980 character" set. If the PCRE_CASELESS is set, implying that the match starts
4981 caselessly, or if there are any changes of this flag within the regex, set up
4982 both cases of the character. Otherwise set the two values the same, which will
4983 avoid duplicate testing (which takes significant time). This covers the vast
4984 majority of cases. It will be suboptimal when the case flag changes in a regex
4985 and the required character in fact is caseful. */
4986
4987 if ((re->options & PCRE_REQCHSET) != 0)
4988   {
4989   req_char = re->req_char;
4990   req_char2 = ((re->options & (PCRE_CASELESS | PCRE_ICHANGED)) != 0)?
4991     (re->tables + fcc_offset)[req_char] : req_char;
4992   }
4993
4994 /* Loop for handling unanchored repeated matching attempts; for anchored regexs
4995 the loop runs just once. */
4996
4997 do
4998   {
4999   int rc;
5000   register int *iptr = match_block.offset_vector;
5001   register int *iend = iptr + resetcount;
5002
5003   /* Reset the maximum number of extractions we might see. */
5004
5005   while (iptr < iend) *iptr++ = -1;
5006
5007   /* Advance to a unique first char if possible */
5008
5009   if (first_char >= 0)
5010     {
5011     if ((ims & PCRE_CASELESS) != 0)
5012       while (start_match < end_subject &&
5013              match_block.lcc[*start_match] != first_char)
5014         start_match++;
5015     else
5016       while (start_match < end_subject && *start_match != first_char)
5017         start_match++;
5018     }
5019
5020   /* Or to just after \n for a multiline match if possible */
5021
5022   else if (startline)
5023     {
5024     if (start_match > match_block.start_subject + start_offset)
5025       {
5026       while (start_match < end_subject && start_match[-1] != '\n')
5027         start_match++;
5028       }
5029     }
5030
5031   /* Or to a non-unique first char after study */
5032
5033   else if (start_bits != NULL)
5034     {
5035     while (start_match < end_subject)
5036       {
5037       register int c = *start_match;
5038       if ((start_bits[c/8] & (1 << (c&7))) == 0) start_match++; else break;
5039       }
5040     }
5041
5042 #ifdef DEBUG  /* Sigh. Some compilers never learn. */
5043   printf(">>>> Match against: ");
5044   pchars(start_match, end_subject - start_match, TRUE, &match_block);
5045   printf("\n");
5046 #endif
5047
5048   /* If req_char is set, we know that that character must appear in the subject
5049   for the match to succeed. If the first character is set, req_char must be
5050   later in the subject; otherwise the test starts at the match point. This
5051   optimization can save a huge amount of backtracking in patterns with nested
5052   unlimited repeats that aren't going to match. We don't know what the state of
5053   case matching may be when this character is hit, so test for it in both its
5054   cases if necessary. However, the different cased versions will not be set up
5055   unless PCRE_CASELESS was given or the casing state changes within the regex.
5056   Writing separate code makes it go faster, as does using an autoincrement and
5057   backing off on a match. */
5058
5059   if (req_char >= 0)
5060     {
5061     register const uschar *p = start_match + ((first_char >= 0)? 1 : 0);
5062
5063     /* We don't need to repeat the search if we haven't yet reached the
5064     place we found it at last time. */
5065
5066     if (p > req_char_ptr)
5067       {
5068       /* Do a single test if no case difference is set up */
5069
5070       if (req_char == req_char2)
5071         {
5072         while (p < end_subject)
5073           {
5074           if (*p++ == req_char) { p--; break; }
5075           }
5076         }
5077
5078       /* Otherwise test for either case */
5079
5080       else
5081         {
5082         while (p < end_subject)
5083           {
5084           register int pp = *p++;
5085           if (pp == req_char || pp == req_char2) { p--; break; }
5086           }
5087         }
5088
5089       /* If we can't find the required character, break the matching loop */
5090
5091       if (p >= end_subject) break;
5092
5093       /* If we have found the required character, save the point where we
5094       found it, so that we don't search again next time round the loop if
5095       the start hasn't passed this character yet. */
5096
5097       req_char_ptr = p;
5098       }
5099     }
5100
5101   /* When a match occurs, substrings will be set for all internal extractions;
5102   we just need to set up the whole thing as substring 0 before returning. If
5103   there were too many extractions, set the return code to zero. In the case
5104   where we had to get some local store to hold offsets for backreferences, copy
5105   those back references that we can. In this case there need not be overflow
5106   if certain parts of the pattern were not used. */
5107
5108   match_block.start_match = start_match;
5109   if (!match(start_match, re->code, 2, &match_block, ims, NULL, match_isgroup))
5110     continue;
5111
5112   /* Copy the offset information from temporary store if necessary */
5113
5114   if (using_temporary_offsets)
5115     {
5116     if (offsetcount >= 4)
5117       {
5118       memcpy(offsets + 2, match_block.offset_vector + 2,
5119         (offsetcount - 2) * sizeof(int));
5120       DPRINTF(("Copied offsets from temporary memory\n"));
5121       }
5122     if (match_block.end_offset_top > offsetcount)
5123       match_block.offset_overflow = TRUE;
5124
5125     DPRINTF(("Freeing temporary memory\n"));
5126     (pcre_free)(match_block.offset_vector);
5127     }
5128
5129   rc = match_block.offset_overflow? 0 : match_block.end_offset_top/2;
5130
5131   if (match_block.offset_end < 2) rc = 0; else
5132     {
5133     offsets[0] = start_match - match_block.start_subject;
5134     offsets[1] = match_block.end_match_ptr - match_block.start_subject;
5135     }
5136
5137   DPRINTF((">>>> returning %d\n", rc));
5138   return rc;
5139   }
5140
5141 /* This "while" is the end of the "do" above */
5142
5143 while (!anchored &&
5144        match_block.errorcode == PCRE_ERROR_NOMATCH &&
5145        start_match++ < end_subject);
5146
5147 if (using_temporary_offsets)
5148   {
5149   DPRINTF(("Freeing temporary memory\n"));
5150   (pcre_free)(match_block.offset_vector);
5151   }
5152
5153 DPRINTF((">>>> returning %d\n", match_block.errorcode));
5154
5155 return match_block.errorcode;
5156 }
5157
5158 /* End of pcre.c */