JavaScriptCore/pcre/pcre_compile.cpp

   1 /* This is JavaScriptCore's variant of the PCRE library. While this library
   2 started out as a copy of PCRE, many of the features of PCRE have been
   3 removed. This library now supports only the regular expression features
   4 required by the JavaScript language specification, and has only the functions
   5 needed by JavaScriptCore and the rest of WebKit.
   6
   7                  Originally written by Philip Hazel
   8            Copyright (c) 1997-2006 University of Cambridge
   9     Copyright (C) 2002, 2004, 2006, 2007 Apple Inc. All rights reserved.
  10     Copyright (C) 2007 Eric Seidel <eric@webkit.org>
  11
  12 -----------------------------------------------------------------------------
  13 Redistribution and use in source and binary forms, with or without
  14 modification, are permitted provided that the following conditions are met:
  15
  16     * Redistributions of source code must retain the above copyright notice,
  17       this list of conditions and the following disclaimer.
  18
  19     * Redistributions in binary form must reproduce the above copyright
  20       notice, this list of conditions and the following disclaimer in the
  21       documentation and/or other materials provided with the distribution.
  22
  23     * Neither the name of the University of Cambridge nor the names of its
  24       contributors may be used to endorse or promote products derived from
  25       this software without specific prior written permission.
  26
  27 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  28 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  31 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  32 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  33 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  34 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  35 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  36 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  37 POSSIBILITY OF SUCH DAMAGE.
  38 -----------------------------------------------------------------------------
  39 */
  40
  41 /* This module contains the external function jsRegExpExecute(), along with
  42 supporting internal functions that are not used by other modules. */
  43
  44 #include "config.h"
  45
  46 #include "pcre_internal.h"
  47
  48 #include <wtf/ASCIICType.h>
  49 #include <wtf/FastMalloc.h>
  50
  51 using namespace WTF;
  52
  53 /*************************************************
  54 *      Code parameters and static tables         *
  55 *************************************************/
  56
  57 /* Maximum number of items on the nested bracket stacks at compile time. This
  58 applies to the nesting of all kinds of parentheses. It does not limit
  59 un-nested, non-capturing parentheses. This number can be made bigger if
  60 necessary - it is used to dimension one int and one unsigned char vector at
  61 compile time. */
  62
  63 #define BRASTACK_SIZE 200
  64
  65 /* Table for handling escaped characters in the range '0'-'z'. Positive returns
  66 are simple data values; negative values are for special things like \d and so
  67 on. Zero means further processing is needed (for things like \x), or the escape
  68 is invalid. */
  69
  70 static const short escapes[] = {
  71      0,      0,      0,      0,      0,      0,      0,      0,   /* 0 - 7 */
  72      0,      0,    ':',    ';',    '<',    '=',    '>',    '?',   /* 8 - ? */
  73    '@',      0, -ESC_B,      0, -ESC_D,      0,      0,      0,   /* @ - G */
  74      0,      0,      0,      0,      0,      0,      0,      0,   /* H - O */
  75      0,      0,      0, -ESC_S,      0,      0,      0, -ESC_W,   /* P - W */
  76      0,      0,      0,    '[',   '\\',    ']',    '^',    '_',   /* X - _ */
  77    '`',      7, -ESC_b,      0, -ESC_d,      0,   '\f',      0,   /* ` - g */
  78      0,      0,      0,      0,      0,      0,   '\n',      0,   /* h - o */
  79      0,      0,    '\r', -ESC_s,   '\t',      0,  '\v', -ESC_w,   /* p - w */
  80      0,      0,      0                                            /* x - z */
  81 };
  82
  83 /* Error code numbers. They are given names so that they can more easily be
  84 tracked. */
  85
  86 enum ErrorCode {
  87     ERR0, ERR1, ERR2, ERR3, ERR4, ERR5, ERR6, ERR7, ERR8, ERR9,
  88     ERR10, ERR11, ERR12, ERR13, ERR14, ERR15, ERR16, ERR17
  89 };
  90
  91 /* Table of sizes for the fixed-length opcodes. It's defined in a macro so that
  92 the definition is next to the definition of the opcodes in pcre_internal.h. */
  93
  94 static const uschar OP_lengths[] = { OP_LENGTHS };
  95
  96 /* The texts of compile-time error messages. These are "char *" because they
  97 are passed to the outside world. */
  98
  99 static const char* error_text(ErrorCode code)
 100 {
 101     static const char error_texts[] =
 102       /* 1 */
 103       "\\ at end of pattern\0"
 104       "\\c at end of pattern\0"
 105       "character value in \\x{...} sequence is too large\0"
 106       "numbers out of order in {} quantifier\0"
 107       /* 5 */
 108       "number too big in {} quantifier\0"
 109       "missing terminating ] for character class\0"
 110       "internal error: code overflow\0"
 111       "range out of order in character class\0"
 112       "nothing to repeat\0"
 113       /* 10 */
 114       "unmatched parentheses\0"
 115       "internal error: unexpected repeat\0"
 116       "unrecognized character after (?\0"
 117       "failed to get memory\0"
 118       "missing )\0"
 119       /* 15 */
 120       "reference to non-existent subpattern\0"
 121       "regular expression too large\0"
 122       "parentheses nested too deeply"
 123     ;
 124
 125     int i = code;
 126     const char* text = error_texts;
 127     while (i > 1)
 128         i -= !*text++;
 129     return text;
 130 }
 131
 132 /* Definition to allow mutual recursion */
 133
 134 static bool compile_regex(int, int*, uschar**, const UChar**, const UChar*, ErrorCode*, int, int*, int*, CompileData&);
 135
 136 /*************************************************
 137 *            Handle escapes                      *
 138 *************************************************/
 139
 140 /* This function is called when a \ has been encountered. It either returns a
 141 positive value for a simple escape such as \n, or a negative value which
 142 encodes one of the more complicated things such as \d. When UTF-8 is enabled,
 143 a positive value greater than 255 may be returned. On entry, ptr is pointing at
 144 the \. On exit, it is on the final character of the escape sequence.
 145
 146 Arguments:
 147   ptrptr         points to the pattern position pointer
 148   errorcodeptr   points to the errorcode variable
 149   bracount       number of previous extracting brackets
 150   options        the options bits
 151   isclass        true if inside a character class
 152
 153 Returns:         zero or positive => a data character
 154                  negative => a special escape sequence
 155                  on error, errorptr is set
 156 */
 157
 158 static int check_escape(const UChar** ptrptr, const UChar* patternEnd, ErrorCode* errorcodeptr, int bracount, bool isclass)
 159 {
 160     const UChar* ptr = *ptrptr + 1;
 161
 162     /* If backslash is at the end of the pattern, it's an error. */
 163     if (ptr == patternEnd) {
 164         *errorcodeptr = ERR1;
 165         *ptrptr = ptr;
 166         return 0;
 167     }
 168
 169     int c = *ptr;
 170
 171     /* Non-alphamerics are literals. For digits or letters, do an initial lookup in
 172      a table. A non-zero result is something that can be returned immediately.
 173      Otherwise further processing may be required. */
 174
 175     if (c < '0' || c > 'z') { /* Not alphameric */
 176     } else if (int escapeValue = escapes[c - '0'])
 177         c = escapeValue;
 178
 179     /* Escapes that need further processing, or are illegal. */
 180
 181     else {
 182         switch (c) {
 183         case '1':
 184         case '2':
 185         case '3':
 186         case '4':
 187         case '5':
 188         case '6':
 189         case '7':
 190         case '8':
 191         case '9':
 192             /* Escape sequences starting with a non-zero digit are backreferences,
 193              unless there are insufficient brackets, in which case they are octal
 194              escape sequences. Those sequences end on the first non-octal character
 195              or when we overflow 0-255, whichever comes first. */
 196
 197             if (!isclass) {
 198                 const UChar* oldptr = ptr;
 199                 c -= '0';
 200                 while (ptr + 1 < patternEnd && isASCIIDigit(ptr[1]) && c <= bracount)
 201                     c = c * 10 + *(++ptr) - '0';
 202                 if (c <= bracount) {
 203                     c = -(ESC_REF + c);
 204                     break;
 205                 }
 206                 ptr = oldptr;      /* Put the pointer back and fall through */
 207             }
 208
 209             /* Handle an octal number following \. If the first digit is 8 or 9,
 210              this is not octal. */
 211
 212             if ((c = *ptr) >= '8')
 213                 break;
 214
 215             /* \0 always starts an octal number, but we may drop through to here with a
 216              larger first octal digit. */
 217
 218         case '0': {
 219             c -= '0';
 220             int i;
 221             for (i = 1; i <= 2; ++i) {
 222                 if (ptr + i >= patternEnd || ptr[i] < '0' || ptr[i] > '7')
 223                     break;
 224                 int cc = c * 8 + ptr[i] - '0';
 225                 if (cc > 255)
 226                     break;
 227                 c = cc;
 228             }
 229             ptr += i - 1;
 230             break;
 231         }
 232         case 'x': {
 233             c = 0;
 234             int i;
 235             for (i = 1; i <= 2; ++i) {
 236                 if (ptr + i >= patternEnd || !isASCIIHexDigit(ptr[i])) {
 237                     c = 'x';
 238                     i = 1;
 239                     break;
 240                 }
 241                 int cc = ptr[i];
 242                 if (cc >= 'a')
 243                     cc -= 32;             /* Convert to upper case */
 244                 c = c * 16 + cc - ((cc < 'A') ? '0' : ('A' - 10));
 245             }
 246             ptr += i - 1;
 247             break;
 248         }
 249         case 'u': {
 250             c = 0;
 251             int i;
 252             for (i = 1; i <= 4; ++i) {
 253                 if (ptr + i >= patternEnd || !isASCIIHexDigit(ptr[i])) {
 254                     c = 'u';
 255                     i = 1;
 256                     break;
 257                 }
 258                 int cc = ptr[i];
 259                 if (cc >= 'a')
 260                     cc -= 32;             /* Convert to upper case */
 261                 c = c * 16 + cc - ((cc < 'A')? '0' : ('A' - 10));
 262             }
 263             ptr += i - 1;
 264             break;
 265
 266             /* Other special escapes not starting with a digit are straightforward */
 267         }
 268         case 'c':
 269             if (++ptr == patternEnd) {
 270                 *errorcodeptr = ERR2;
 271                 return 0;
 272             }
 273             c = *ptr;
 274
 275             /* A letter is upper-cased; then the 0x40 bit is flipped. This coding
 276              is ASCII-specific, but then the whole concept of \cx is ASCII-specific. */
 277
 278             if (c >= 'a' && c <= 'z')
 279                 c -= 32;
 280             c ^= 0x40;
 281             break;
 282         }
 283     }
 284
 285     *ptrptr = ptr;
 286     return c;
 287 }
 288
 289
 290
 291 /*************************************************
 292 *            Check for counted repeat            *
 293 *************************************************/
 294
 295 /* This function is called when a '{' is encountered in a place where it might
 296 start a quantifier. It looks ahead to see if it really is a quantifier or not.
 297 It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd}
 298 where the ddds are digits.
 299
 300 Arguments:
 301   p         pointer to the first char after '{'
 302
 303 Returns:    true or false
 304 */
 305
 306 static bool is_counted_repeat(const UChar* p, const UChar* patternEnd)
 307 {
 308     if (p >= patternEnd || !isASCIIDigit(*p))
 309         return false;
 310     p++;
 311     while (p < patternEnd && isASCIIDigit(*p))
 312         p++;
 313     if (p < patternEnd && *p == '}')
 314         return true;
 315
 316     if (p >= patternEnd || *p++ != ',')
 317         return false;
 318     if (p < patternEnd && *p == '}')
 319         return true;
 320
 321     if (p >= patternEnd || !isASCIIDigit(*p))
 322         return false;
 323     p++;
 324     while (p < patternEnd && isASCIIDigit(*p))
 325         p++;
 326
 327     return (p < patternEnd && *p == '}');
 328 }
 329
 330
 331 /*************************************************
 332 *         Read repeat counts                     *
 333 *************************************************/
 334
 335 /* Read an item of the form {n,m} and return the values. This is called only
 336 after is_counted_repeat() has confirmed that a repeat-count quantifier exists,
 337 so the syntax is guaranteed to be correct, but we need to check the values.
 338
 339 Arguments:
 340   p              pointer to first char after '{'
 341   minp           pointer to int for min
 342   maxp           pointer to int for max
 343                  returned as -1 if no max
 344   errorcodeptr   points to error code variable
 345
 346 Returns:         pointer to '}' on success;
 347                  current ptr on error, with errorcodeptr set non-zero
 348 */
 349
 350 static const UChar* read_repeat_counts(const UChar* p, int* minp, int* maxp, ErrorCode* errorcodeptr)
 351 {
 352     int min = 0;
 353     int max = -1;
 354
 355     /* Read the minimum value and do a paranoid check: a negative value indicates
 356      an integer overflow. */
 357
 358     while (isASCIIDigit(*p))
 359         min = min * 10 + *p++ - '0';
 360     if (min < 0 || min > 65535) {
 361         *errorcodeptr = ERR5;
 362         return p;
 363     }
 364
 365     /* Read the maximum value if there is one, and again do a paranoid on its size.
 366      Also, max must not be less than min. */
 367
 368     if (*p == '}')
 369         max = min;
 370     else {
 371         if (*(++p) != '}') {
 372             max = 0;
 373             while (isASCIIDigit(*p))
 374                 max = max * 10 + *p++ - '0';
 375             if (max < 0 || max > 65535) {
 376                 *errorcodeptr = ERR5;
 377                 return p;
 378             }
 379             if (max < min) {
 380                 *errorcodeptr = ERR4;
 381                 return p;
 382             }
 383         }
 384     }
 385
 386     /* Fill in the required variables, and pass back the pointer to the terminating
 387      '}'. */
 388
 389     *minp = min;
 390     *maxp = max;
 391     return p;
 392 }
 393
 394
 395 /*************************************************
 396 *      Find first significant op code            *
 397 *************************************************/
 398
 399 /* This is called by several functions that scan a compiled expression looking
 400 for a fixed first character, or an anchoring op code etc. It skips over things
 401 that do not influence this. For some calls, a change of option is important.
 402 For some calls, it makes sense to skip negative forward and all backward
 403 assertions, and also the \b assertion; for others it does not.
 404
 405 Arguments:
 406   code         pointer to the start of the group
 407   skipassert   true if certain assertions are to be skipped
 408
 409 Returns:       pointer to the first significant opcode
 410 */
 411
 412 static const uschar* firstSignificantOpCode(const uschar* code)
 413 {
 414     while (*code == OP_BRANUMBER)
 415         code += OP_lengths[*code];
 416     return code;
 417 }
 418
 419 static const uschar* firstSignificantOpCodeSkippingAssertions(const uschar* code)
 420 {
 421     while (true) {
 422         switch (*code) {
 423         case OP_ASSERT_NOT:
 424             do {
 425                 code += getOpcodeValueAtOffset(code, 1);
 426             } while (*code == OP_ALT);
 427             code += OP_lengths[*code];
 428             break;
 429         case OP_WORD_BOUNDARY:
 430         case OP_NOT_WORD_BOUNDARY:
 431         case OP_BRANUMBER:
 432             code += OP_lengths[*code];
 433             break;
 434         default:
 435             return code;
 436         }
 437     }
 438     ASSERT_NOT_REACHED();
 439 }
 440
 441
 442 /*************************************************
 443 *        Find the fixed length of a pattern      *
 444 *************************************************/
 445
 446 /* Scan a pattern and compute the fixed length of subject that will match it,
 447 if the length is fixed. This is needed for dealing with backward assertions.
 448 In UTF8 mode, the result is in characters rather than bytes.
 449
 450 Arguments:
 451   code     points to the start of the pattern (the bracket)
 452   options  the compiling options
 453
 454 Returns:   the fixed length, or -1 if there is no fixed length,
 455              or -2 if \C was encountered
 456 */
 457
 458 static int find_fixedlength(uschar* code, int options)
 459 {
 460     int length = -1;
 461
 462     int branchlength = 0;
 463     uschar* cc = code + 1 + LINK_SIZE;
 464
 465     /* Scan along the opcodes for this branch. If we get to the end of the
 466      branch, check the length against that of the other branches. */
 467
 468     while (true) {
 469         int d;
 470         int op = *cc;
 471         if (op >= OP_BRA)
 472             op = OP_BRA;
 473
 474         switch (op) {
 475             case OP_BRA:
 476             case OP_ONCE:
 477                 d = find_fixedlength(cc, options);
 478                 if (d < 0)
 479                     return d;
 480                 branchlength += d;
 481                 do {
 482                     cc += getOpcodeValueAtOffset(cc, 1);
 483                 } while (*cc == OP_ALT);
 484                 cc += 1 + LINK_SIZE;
 485                 break;
 486
 487                 /* Reached end of a branch; if it's a ket it is the end of a nested
 488                  call. If it's ALT it is an alternation in a nested call. If it is
 489                  END it's the end of the outer call. All can be handled by the same code. */
 490
 491             case OP_ALT:
 492             case OP_KET:
 493             case OP_KETRMAX:
 494             case OP_KETRMIN:
 495             case OP_END:
 496                 if (length < 0)
 497                     length = branchlength;
 498                 else if (length != branchlength)
 499                     return -1;
 500                 if (*cc != OP_ALT)
 501                     return length;
 502                 cc += 1 + LINK_SIZE;
 503                 branchlength = 0;
 504                 break;
 505
 506                 /* Skip over assertive subpatterns */
 507
 508             case OP_ASSERT:
 509             case OP_ASSERT_NOT:
 510                 do {
 511                     cc += getOpcodeValueAtOffset(cc, 1);
 512                 } while (*cc == OP_ALT);
 513                 /* Fall through */
 514
 515                 /* Skip over things that don't match chars */
 516
 517             case OP_BRANUMBER:
 518             case OP_CIRC:
 519             case OP_DOLL:
 520             case OP_NOT_WORD_BOUNDARY:
 521             case OP_WORD_BOUNDARY:
 522                 cc += OP_lengths[*cc];
 523                 break;
 524
 525                 /* Handle literal characters */
 526
 527             case OP_CHAR:
 528             case OP_CHAR_IGNORING_CASE:
 529             case OP_NOT:
 530                 branchlength++;
 531                 cc += 2;
 532                 while ((*cc & 0xc0) == 0x80)
 533                     cc++;
 534                 break;
 535
 536             case OP_ASCII_CHAR:
 537             case OP_ASCII_LETTER_IGNORING_CASE:
 538                 branchlength++;
 539                 cc += 2;
 540                 break;
 541
 542                 /* Handle exact repetitions. The count is already in characters, but we
 543                  need to skip over a multibyte character in UTF8 mode.  */
 544
 545             case OP_EXACT:
 546                 branchlength += get2ByteOpcodeValueAtOffset(cc,1);
 547                 cc += 4;
 548                 while((*cc & 0x80) == 0x80)
 549                     cc++;
 550                 break;
 551
 552             case OP_TYPEEXACT:
 553                 branchlength += get2ByteOpcodeValueAtOffset(cc,1);
 554                 cc += 4;
 555                 break;
 556
 557                 /* Handle single-char matchers */
 558
 559             case OP_NOT_DIGIT:
 560             case OP_DIGIT:
 561             case OP_NOT_WHITESPACE:
 562             case OP_WHITESPACE:
 563             case OP_NOT_WORDCHAR:
 564             case OP_WORDCHAR:
 565             case OP_NOT_NEWLINE:
 566                 branchlength++;
 567                 cc++;
 568                 break;
 569
 570                 /* Check a class for variable quantification */
 571
 572             case OP_XCLASS:
 573                 cc += getOpcodeValueAtOffset(cc, 1) - 33;
 574                 /* Fall through */
 575
 576             case OP_CLASS:
 577             case OP_NCLASS:
 578                 cc += 33;
 579
 580                 switch (*cc) {
 581                 case OP_CRSTAR:
 582                 case OP_CRMINSTAR:
 583                 case OP_CRQUERY:
 584                 case OP_CRMINQUERY:
 585                     return -1;
 586
 587                 case OP_CRRANGE:
 588                 case OP_CRMINRANGE:
 589                     if (get2ByteOpcodeValueAtOffset(cc, 1) != get2ByteOpcodeValueAtOffset(cc, 3))
 590                         return -1;
 591                     branchlength += get2ByteOpcodeValueAtOffset(cc, 1);
 592                     cc += 5;
 593                     break;
 594
 595                 default:
 596                     branchlength++;
 597                 }
 598                 break;
 599
 600                 /* Anything else is variable length */
 601
 602             default:
 603                 return -1;
 604         }
 605     }
 606     ASSERT_NOT_REACHED();
 607 }
 608
 609
 610 /*************************************************
 611 *         Complete a callout item                *
 612 *************************************************/
 613
 614 /* A callout item contains the length of the next item in the pattern, which
 615 we can't fill in till after we have reached the relevant point. This is used
 616 for both automatic and manual callouts.
 617
 618 Arguments:
 619   previous_callout   points to previous callout item
 620   ptr                current pattern pointer
 621   cd                 pointers to tables etc
 622 */
 623
 624 static void complete_callout(uschar* previous_callout, const UChar* ptr, const CompileData& cd)
 625 {
 626     int length = ptr - cd.start_pattern - getOpcodeValueAtOffset(previous_callout, 2);
 627     putOpcodeValueAtOffset(previous_callout, 2 + LINK_SIZE, length);
 628 }
 629
 630
 631
 632 /*************************************************
 633 *           Get othercase range                  *
 634 *************************************************/
 635
 636 /* This function is passed the start and end of a class range, in UTF-8 mode
 637 with UCP support. It searches up the characters, looking for internal ranges of
 638 characters in the "other" case. Each call returns the next one, updating the
 639 start address.
 640
 641 Arguments:
 642   cptr        points to starting character value; updated
 643   d           end value
 644   ocptr       where to put start of othercase range
 645   odptr       where to put end of othercase range
 646
 647 Yield:        true when range returned; false when no more
 648 */
 649
 650 static bool get_othercase_range(int* cptr, int d, int* ocptr, int* odptr)
 651 {
 652     int c, othercase = 0;
 653
 654     for (c = *cptr; c <= d; c++) {
 655         if ((othercase = _pcre_ucp_othercase(c)) >= 0)
 656             break;
 657     }
 658
 659     if (c > d)
 660         return false;
 661
 662     *ocptr = othercase;
 663     int next = othercase + 1;
 664
 665     for (++c; c <= d; c++) {
 666         if (_pcre_ucp_othercase(c) != next)
 667             break;
 668         next++;
 669     }
 670
 671     *odptr = next - 1;
 672     *cptr = c;
 673
 674     return true;
 675 }
 676
 677 /*************************************************
 678  *       Convert character value to UTF-8         *
 679  *************************************************/
 680
 681 /* This function takes an integer value in the range 0 - 0x7fffffff
 682  and encodes it as a UTF-8 character in 0 to 6 bytes.
 683
 684  Arguments:
 685  cvalue     the character value
 686  buffer     pointer to buffer for result - at least 6 bytes long
 687
 688  Returns:     number of characters placed in the buffer
 689  */
 690
 691 // FIXME: This should be removed as soon as all UTF8 uses are removed from PCRE
 692 int _pcre_ord2utf8(int cvalue, uschar *buffer)
 693 {
 694     int i;
 695     for (i = 0; i < _pcre_utf8_table1_size; i++)
 696         if (cvalue <= _pcre_utf8_table1[i])
 697             break;
 698     buffer += i;
 699     for (int j = i; j > 0; j--) {
 700         *buffer-- = 0x80 | (cvalue & 0x3f);
 701         cvalue >>= 6;
 702     }
 703     *buffer = _pcre_utf8_table2[i] | cvalue;
 704     return i + 1;
 705 }
 706
 707 /*************************************************
 708 *           Compile one branch                   *
 709 *************************************************/
 710
 711 /* Scan the pattern, compiling it into the code vector. If the options are
 712 changed during the branch, the pointer is used to change the external options
 713 bits.
 714
 715 Arguments:
 716   options        the option bits
 717   brackets       points to number of extracting brackets used
 718   codeptr        points to the pointer to the current code point
 719   ptrptr         points to the current pattern pointer
 720   errorcodeptr   points to error code variable
 721   firstbyteptr   set to initial literal character, or < 0 (REQ_UNSET, REQ_NONE)
 722   reqbyteptr     set to the last literal character required, else < 0
 723   cd             contains pointers to tables etc.
 724
 725 Returns:         true on success
 726                  false, with *errorcodeptr set non-zero on error
 727 */
 728
 729 static bool
 730 compile_branch(int options, int* brackets, uschar** codeptr,
 731                const UChar** ptrptr, const UChar* patternEnd, ErrorCode* errorcodeptr, int *firstbyteptr,
 732                int* reqbyteptr, CompileData& cd)
 733 {
 734     int repeat_type, op_type;
 735     int repeat_min = 0, repeat_max = 0;      /* To please picky compilers */
 736     int bravalue = 0;
 737     int reqvary, tempreqvary;
 738     int after_manual_callout = 0;
 739     int c;
 740     uschar* code = *codeptr;
 741     uschar* tempcode;
 742     bool groupsetfirstbyte = false;
 743     const UChar* ptr = *ptrptr;
 744     const UChar* tempptr;
 745     uschar* previous = NULL;
 746     uschar* previous_callout = NULL;
 747     uschar classbits[32];
 748
 749     bool class_utf8;
 750     uschar* class_utf8data;
 751     uschar utf8_char[6];
 752
 753     /* Initialize no first byte, no required byte. REQ_UNSET means "no char
 754      matching encountered yet". It gets changed to REQ_NONE if we hit something that
 755      matches a non-fixed char first char; reqbyte just remains unset if we never
 756      find one.
 757
 758      When we hit a repeat whose minimum is zero, we may have to adjust these values
 759      to take the zero repeat into account. This is implemented by setting them to
 760      zerofirstbyte and zeroreqbyte when such a repeat is encountered. The individual
 761      item types that can be repeated set these backoff variables appropriately. */
 762
 763     int firstbyte = REQ_UNSET;
 764     int reqbyte = REQ_UNSET;
 765     int zeroreqbyte = REQ_UNSET;
 766     int zerofirstbyte = REQ_UNSET;
 767
 768     /* The variable req_caseopt contains either the REQ_IGNORE_CASE value or zero,
 769      according to the current setting of the ignores-case flag. REQ_IGNORE_CASE is a bit
 770      value > 255. It is added into the firstbyte or reqbyte variables to record the
 771      case status of the value. This is used only for ASCII characters. */
 772
 773     int req_caseopt = (options & IgnoreCaseOption) ? REQ_IGNORE_CASE : 0;
 774
 775     /* Switch on next character until the end of the branch */
 776
 777     for (;; ptr++)
 778     {
 779         bool negate_class;
 780         bool should_flip_negation; /* If a negative special such as \S is used, we should negate the whole class to properly support Unicode. */
 781         int class_charcount;
 782         int class_lastchar;
 783         int skipbytes;
 784         int subreqbyte;
 785         int subfirstbyte;
 786         int mclength;
 787         uschar mcbuffer[8];
 788
 789         /* Next byte in the pattern */
 790
 791         c = ptr < patternEnd ? *ptr : 0;
 792
 793         /* Fill in length of a previous callout, except when the next thing is
 794          a quantifier. */
 795
 796         bool is_quantifier = c == '*' || c == '+' || c == '?' || (c == '{' && is_counted_repeat(ptr + 1, patternEnd));
 797
 798         if (!is_quantifier && previous_callout && after_manual_callout-- <= 0) {
 799             complete_callout(previous_callout, ptr, cd);
 800             previous_callout = NULL;
 801         }
 802
 803         switch (c) {
 804             /* The branch terminates at end of string, |, or ). */
 805
 806             case 0:
 807                 if (ptr < patternEnd)
 808                     goto NORMAL_CHAR;
 809                 // End of string; fall through
 810             case '|':
 811             case ')':
 812                 *firstbyteptr = firstbyte;
 813                 *reqbyteptr = reqbyte;
 814                 *codeptr = code;
 815                 *ptrptr = ptr;
 816                 return true;
 817
 818             /* Handle single-character metacharacters. In multiline mode, ^ disables
 819              the setting of any following char as a first character. */
 820
 821             case '^':
 822                 if (options & MatchAcrossMultipleLinesOption) {
 823                     if (firstbyte == REQ_UNSET)
 824                         firstbyte = REQ_NONE;
 825                 }
 826                 previous = NULL;
 827                 *code++ = OP_CIRC;
 828                 break;
 829
 830             case '$':
 831                 previous = NULL;
 832                 *code++ = OP_DOLL;
 833                 break;
 834
 835             /* There can never be a first char if '.' is first, whatever happens about
 836              repeats. The value of reqbyte doesn't change either. */
 837
 838             case '.':
 839                 if (firstbyte == REQ_UNSET)
 840                     firstbyte = REQ_NONE;
 841                 zerofirstbyte = firstbyte;
 842                 zeroreqbyte = reqbyte;
 843                 previous = code;
 844                 *code++ = OP_NOT_NEWLINE;
 845                 break;
 846
 847             /* Character classes. If the included characters are all < 256, we build a
 848              32-byte bitmap of the permitted characters, except in the special case
 849              where there is only one such character. For negated classes, we build the
 850              map as usual, then invert it at the end. However, we use a different opcode
 851              so that data characters > 255 can be handled correctly.
 852
 853              If the class contains characters outside the 0-255 range, a different
 854              opcode is compiled. It may optionally have a bit map for characters < 256,
 855              but those above are are explicitly listed afterwards. A flag byte tells
 856              whether the bitmap is present, and whether this is a negated class or not.
 857              */
 858
 859             case '[': {
 860                 previous = code;
 861                 should_flip_negation = false;
 862
 863                 /* PCRE supports POSIX class stuff inside a class. Perl gives an error if
 864                  they are encountered at the top level, so we'll do that too. */
 865
 866                 /* If the first character is '^', set the negation flag and skip it. */
 867
 868                 if (ptr[1] == '^') {
 869                     negate_class = true;
 870                     ++ptr;
 871                 } else
 872                     negate_class = false;
 873
 874                 /* Keep a count of chars with values < 256 so that we can optimize the case
 875                  of just a single character (as long as it's < 256). For higher valued UTF-8
 876                  characters, we don't yet do any optimization. */
 877
 878                 class_charcount = 0;
 879                 class_lastchar = -1;
 880
 881                 class_utf8 = false;                       /* No chars >= 256 */
 882                 class_utf8data = code + LINK_SIZE + 34;   /* For UTF-8 items */
 883
 884                 /* Initialize the 32-char bit map to all zeros. We have to build the
 885                  map in a temporary bit of store, in case the class contains only 1
 886                  character (< 256), because in that case the compiled code doesn't use the
 887                  bit map. */
 888
 889                 memset(classbits, 0, 32 * sizeof(uschar));
 890
 891                 /* Process characters until ] is reached. The first pass
 892                  through the regex checked the overall syntax, so we don't need to be very
 893                  strict here. At the start of the loop, c contains the first byte of the
 894                  character. */
 895                 while ((c = *(++ptr)) != ']') {
 896                     /* Backslash may introduce a single character, or it may introduce one
 897                      of the specials, which just set a flag. Escaped items are checked for
 898                      validity in the pre-compiling pass. The sequence \b is a special case.
 899                      Inside a class (and only there) it is treated as backspace. Elsewhere
 900                      it marks a word boundary. Other escapes have preset maps ready to
 901                      or into the one we are building. We assume they have more than one
 902                      character in them, so set class_charcount bigger than one. */
 903
 904                     if (c == '\\') {
 905                         c = check_escape(&ptr, patternEnd, errorcodeptr, *brackets, true);
 906
 907                         if (-c == ESC_b)
 908                             c = '\b';       /* \b is backslash in a class */
 909
 910                         if (c < 0) {
 911                             class_charcount += 2;     /* Greater than 1 is what matters */
 912                             switch (-c) {
 913                                 case ESC_d:
 914                                     for (c = 0; c < 32; c++)
 915                                         classbits[c] |= classBitmapForChar(c + cbit_digit);
 916                                     continue;
 917
 918                                 case ESC_D:
 919                                     should_flip_negation = true;
 920                                     for (c = 0; c < 32; c++)
 921                                         classbits[c] |= ~classBitmapForChar(c + cbit_digit);
 922                                     continue;
 923
 924                                 case ESC_w:
 925                                     for (c = 0; c < 32; c++)
 926                                         classbits[c] |= classBitmapForChar(c + cbit_word);
 927                                     continue;
 928
 929                                 case ESC_W:
 930                                     should_flip_negation = true;
 931                                     for (c = 0; c < 32; c++)
 932                                         classbits[c] |= ~classBitmapForChar(c + cbit_word);
 933                                     continue;
 934
 935                                 case ESC_s:
 936                                     for (c = 0; c < 32; c++)
 937                                          classbits[c] |= classBitmapForChar(c + cbit_space);
 938                                     continue;
 939
 940                                 case ESC_S:
 941                                     should_flip_negation = true;
 942                                     for (c = 0; c < 32; c++)
 943                                          classbits[c] |= ~classBitmapForChar(c + cbit_space);
 944                                     continue;
 945
 946                                     /* Unrecognized escapes are faulted if PCRE is running in its
 947                                      strict mode. By default, for compatibility with Perl, they are
 948                                      treated as literals. */
 949
 950                                 default:
 951                                     c = *ptr;              /* The final character */
 952                                     class_charcount -= 2;  /* Undo the default count from above */
 953                             }
 954                         }
 955
 956                         /* Fall through if we have a single character (c >= 0). This may be
 957                          > 256 in UTF-8 mode. */
 958
 959                     }   /* End of backslash handling */
 960
 961                     /* A single character may be followed by '-' to form a range. However,
 962                      Perl does not permit ']' to be the end of the range. A '-' character
 963                      here is treated as a literal. */
 964
 965                     if (ptr[1] == '-' && ptr[2] != ']') {
 966                         ptr += 2;
 967
 968                         int d = *ptr;
 969
 970                         /* The second part of a range can be a single-character escape, but
 971                          not any of the other escapes. Perl 5.6 treats a hyphen as a literal
 972                          in such circumstances. */
 973
 974                         if (d == '\\') {
 975                             const UChar* oldptr = ptr;
 976                             d = check_escape(&ptr, patternEnd, errorcodeptr, *brackets, true);
 977
 978                             /* \b is backslash; \X is literal X; any other special means the '-'
 979                              was literal */
 980
 981                             if (d < 0) {
 982                                 if (d == -ESC_b)
 983                                     d = '\b';
 984                                 else {
 985                                     ptr = oldptr - 2;
 986                                     goto LONE_SINGLE_CHARACTER;  /* A few lines below */
 987                                 }
 988                             }
 989                         }
 990
 991                         /* The check that the two values are in the correct order happens in
 992                          the pre-pass. Optimize one-character ranges */
 993
 994                         if (d == c)
 995                             goto LONE_SINGLE_CHARACTER;  /* A few lines below */
 996
 997                         /* In UTF-8 mode, if the upper limit is > 255, or > 127 for caseless
 998                          matching, we have to use an XCLASS with extra data items. Caseless
 999                          matching for characters > 127 is available only if UCP support is
1000                          available. */
1001
1002                         if ((d > 255 || ((options & IgnoreCaseOption) && d > 127))) {
1003                             class_utf8 = true;
1004
1005                             /* With UCP support, we can find the other case equivalents of
1006                              the relevant characters. There may be several ranges. Optimize how
1007                              they fit with the basic range. */
1008
1009                             if (options & IgnoreCaseOption) {
1010                                 int occ, ocd;
1011                                 int cc = c;
1012                                 int origd = d;
1013                                 while (get_othercase_range(&cc, origd, &occ, &ocd)) {
1014                                     if (occ >= c && ocd <= d)
1015                                         continue;  /* Skip embedded ranges */
1016
1017                                     if (occ < c  && ocd >= c - 1)        /* Extend the basic range */
1018                                     {                                  /* if there is overlap,   */
1019                                         c = occ;                           /* noting that if occ < c */
1020                                         continue;                          /* we can't have ocd > d  */
1021                                     }                                  /* because a subrange is  */
1022                                     if (ocd > d && occ <= d + 1)         /* always shorter than    */
1023                                     {                                  /* the basic range.       */
1024                                         d = ocd;
1025                                         continue;
1026                                     }
1027
1028                                     if (occ == ocd)
1029                                         *class_utf8data++ = XCL_SINGLE;
1030                                     else {
1031                                         *class_utf8data++ = XCL_RANGE;
1032                                         class_utf8data += _pcre_ord2utf8(occ, class_utf8data);
1033                                     }
1034                                     class_utf8data += _pcre_ord2utf8(ocd, class_utf8data);
1035                                 }
1036                             }
1037
1038                             /* Now record the original range, possibly modified for UCP caseless
1039                              overlapping ranges. */
1040
1041                             *class_utf8data++ = XCL_RANGE;
1042                             class_utf8data += _pcre_ord2utf8(c, class_utf8data);
1043                             class_utf8data += _pcre_ord2utf8(d, class_utf8data);
1044
1045                             /* With UCP support, we are done. Without UCP support, there is no
1046                              caseless matching for UTF-8 characters > 127; we can use the bit map
1047                              for the smaller ones. */
1048
1049                             continue;    /* With next character in the class */
1050                         }
1051
1052                         /* We use the bit map for all cases when not in UTF-8 mode; else
1053                          ranges that lie entirely within 0-127 when there is UCP support; else
1054                          for partial ranges without UCP support. */
1055
1056                         for (; c <= d; c++) {
1057                             classbits[c/8] |= (1 << (c&7));
1058                             if (options & IgnoreCaseOption) {
1059                                 int uc = flipCase(c);
1060                                 classbits[uc/8] |= (1 << (uc&7));
1061                             }
1062                             class_charcount++;                /* in case a one-char range */
1063                             class_lastchar = c;
1064                         }
1065
1066                         continue;   /* Go get the next char in the class */
1067                     }
1068
1069                     /* Handle a lone single character - we can get here for a normal
1070                      non-escape char, or after \ that introduces a single character or for an
1071                      apparent range that isn't. */
1072
1073                 LONE_SINGLE_CHARACTER:
1074
1075                     /* Handle a character that cannot go in the bit map */
1076
1077                     if ((c > 255 || ((options & IgnoreCaseOption) && c > 127))) {
1078                         class_utf8 = true;
1079                         *class_utf8data++ = XCL_SINGLE;
1080                         class_utf8data += _pcre_ord2utf8(c, class_utf8data);
1081
1082                         if (options & IgnoreCaseOption) {
1083                             int othercase;
1084                             if ((othercase = _pcre_ucp_othercase(c)) >= 0) {
1085                                 *class_utf8data++ = XCL_SINGLE;
1086                                 class_utf8data += _pcre_ord2utf8(othercase, class_utf8data);
1087                             }
1088                         }
1089                     }
1090                     else
1091
1092                     /* Handle a single-byte character */
1093                     {
1094                         classbits[c/8] |= (1 << (c&7));
1095                         if (options & IgnoreCaseOption) {
1096                             c = flipCase(c);
1097                             classbits[c/8] |= (1 << (c&7));
1098                         }
1099                         class_charcount++;
1100                         class_lastchar = c;
1101                     }
1102                 }
1103
1104                 /* If class_charcount is 1, we saw precisely one character whose value is
1105                  less than 256. In non-UTF-8 mode we can always optimize. In UTF-8 mode, we
1106                  can optimize the negative case only if there were no characters >= 128
1107                  because OP_NOT and the related opcodes like OP_NOTSTAR operate on
1108                  single-bytes only. This is an historical hangover. Maybe one day we can
1109                  tidy these opcodes to handle multi-byte characters.
1110
1111                  The optimization throws away the bit map. We turn the item into a
1112                  1-character OP_CHAR[NC] if it's positive, or OP_NOT if it's negative. Note
1113                  that OP_NOT does not support multibyte characters. In the positive case, it
1114                  can cause firstbyte to be set. Otherwise, there can be no first char if
1115                  this item is first, whatever repeat count may follow. In the case of
1116                  reqbyte, save the previous value for reinstating. */
1117
1118                 if (class_charcount == 1 && (!class_utf8 && (!negate_class || class_lastchar < 128))) {
1119                     zeroreqbyte = reqbyte;
1120
1121                     /* The OP_NOT opcode works on one-byte characters only. */
1122
1123                     if (negate_class) {
1124                         if (firstbyte == REQ_UNSET)
1125                             firstbyte = REQ_NONE;
1126                         zerofirstbyte = firstbyte;
1127                         *code++ = OP_NOT;
1128                         *code++ = class_lastchar;
1129                         break;
1130                     }
1131
1132                     /* For a single, positive character, get the value into c, and
1133                      then we can handle this with the normal one-character code. */
1134
1135                     c = class_lastchar;
1136                     goto NORMAL_CHAR;
1137                 }       /* End of 1-char optimization */
1138
1139                 /* The general case - not the one-char optimization. If this is the first
1140                  thing in the branch, there can be no first char setting, whatever the
1141                  repeat count. Any reqbyte setting must remain unchanged after any kind of
1142                  repeat. */
1143
1144                 if (firstbyte == REQ_UNSET) firstbyte = REQ_NONE;
1145                 zerofirstbyte = firstbyte;
1146                 zeroreqbyte = reqbyte;
1147
1148                 /* If there are characters with values > 255, we have to compile an
1149                  extended class, with its own opcode. If there are no characters < 256,
1150                  we can omit the bitmap. */
1151
1152                 if (class_utf8 && !should_flip_negation) {
1153                     *class_utf8data++ = XCL_END;    /* Marks the end of extra data */
1154                     *code++ = OP_XCLASS;
1155                     code += LINK_SIZE;
1156                     *code = negate_class? XCL_NOT : 0;
1157
1158                     /* If the map is required, install it, and move on to the end of
1159                      the extra data */
1160
1161                     if (class_charcount > 0) {
1162                         *code++ |= XCL_MAP;
1163                         memcpy(code, classbits, 32);
1164                         code = class_utf8data;
1165                     }
1166
1167                     /* If the map is not required, slide down the extra data. */
1168
1169                     else {
1170                         int len = class_utf8data - (code + 33);
1171                         memmove(code + 1, code + 33, len);
1172                         code += len + 1;
1173                     }
1174
1175                     /* Now fill in the complete length of the item */
1176
1177                     putOpcodeValueAtOffset(previous, 1, code - previous);
1178                     break;   /* End of class handling */
1179                 }
1180
1181                 /* If there are no characters > 255, negate the 32-byte map if necessary,
1182                  and copy it into the code vector. If this is the first thing in the branch,
1183                  there can be no first char setting, whatever the repeat count. Any reqbyte
1184                  setting must remain unchanged after any kind of repeat. */
1185
1186                 *code++ = (negate_class == should_flip_negation) ? OP_CLASS : OP_NCLASS;
1187                 if (negate_class)
1188                     for (c = 0; c < 32; c++)
1189                         code[c] = ~classbits[c];
1190                 else
1191                     memcpy(code, classbits, 32);
1192                 code += 32;
1193                 break;
1194             }
1195
1196             /* Various kinds of repeat; '{' is not necessarily a quantifier, but this
1197              has been tested above. */
1198
1199             case '{':
1200                 if (!is_quantifier)
1201                     goto NORMAL_CHAR;
1202                 ptr = read_repeat_counts(ptr+1, &repeat_min, &repeat_max, errorcodeptr);
1203                 if (*errorcodeptr)
1204                     goto FAILED;
1205                 goto REPEAT;
1206
1207             case '*':
1208                 repeat_min = 0;
1209                 repeat_max = -1;
1210                 goto REPEAT;
1211
1212             case '+':
1213                 repeat_min = 1;
1214                 repeat_max = -1;
1215                 goto REPEAT;
1216
1217             case '?':
1218                 repeat_min = 0;
1219                 repeat_max = 1;
1220
1221             REPEAT:
1222                 if (!previous) {
1223                     *errorcodeptr = ERR9;
1224                     goto FAILED;
1225                 }
1226
1227                 if (repeat_min == 0) {
1228                     firstbyte = zerofirstbyte;    /* Adjust for zero repeat */
1229                     reqbyte = zeroreqbyte;        /* Ditto */
1230                 }
1231
1232                 /* Remember whether this is a variable length repeat */
1233
1234                 reqvary = (repeat_min == repeat_max)? 0 : REQ_VARY;
1235
1236                 op_type = 0;                    /* Default single-char op codes */
1237
1238                 /* Save start of previous item, in case we have to move it up to make space
1239                  for an inserted OP_ONCE for the additional '+' extension. */
1240
1241                 tempcode = previous;
1242
1243                 /* If the next character is '+', we have a possessive quantifier. This
1244                  implies greediness, whatever the setting of the PCRE_UNGREEDY option.
1245                  If the next character is '?' this is a minimizing repeat, by default,
1246                  but if PCRE_UNGREEDY is set, it works the other way round. We change the
1247                  repeat type to the non-default. */
1248
1249                 if (ptr + 1 < patternEnd && ptr[1] == '?') {
1250                     repeat_type = 1;
1251                     ptr++;
1252                 } else
1253                     repeat_type = 0;
1254
1255                 /* If previous was a character match, abolish the item and generate a
1256                  repeat item instead. If a char item has a minumum of more than one, ensure
1257                  that it is set in reqbyte - it might not be if a sequence such as x{3} is
1258                  the first thing in a branch because the x will have gone into firstbyte
1259                  instead.  */
1260
1261                 if (*previous == OP_CHAR || *previous == OP_CHAR_IGNORING_CASE) {
1262                     /* Deal with UTF-8 characters that take up more than one byte. It's
1263                      easier to write this out separately than try to macrify it. Use c to
1264                      hold the length of the character in bytes, plus 0x80 to flag that it's a
1265                      length rather than a small character. */
1266
1267                     if (code[-1] & 0x80) {
1268                         uschar *lastchar = code - 1;
1269                         while((*lastchar & 0xc0) == 0x80)
1270                             lastchar--;
1271                         c = code - lastchar;            /* Length of UTF-8 character */
1272                         memcpy(utf8_char, lastchar, c); /* Save the char */
1273                         c |= 0x80;                      /* Flag c as a length */
1274                     }
1275                     else {
1276                         c = code[-1];
1277                         if (repeat_min > 1)
1278                             reqbyte = c | req_caseopt | cd.req_varyopt;
1279                     }
1280
1281                     goto OUTPUT_SINGLE_REPEAT;   /* Code shared with single character types */
1282                 }
1283
1284                 else if (*previous == OP_ASCII_CHAR || *previous == OP_ASCII_LETTER_IGNORING_CASE) {
1285                     c = previous[1];
1286                     if (repeat_min > 1)
1287                         reqbyte = c | req_caseopt | cd.req_varyopt;
1288                     goto OUTPUT_SINGLE_REPEAT;
1289                 }
1290
1291                 /* If previous was a single negated character ([^a] or similar), we use
1292                  one of the special opcodes, replacing it. The code is shared with single-
1293                  character repeats by setting opt_type to add a suitable offset into
1294                  repeat_type. OP_NOT is currently used only for single-byte chars. */
1295
1296                 else if (*previous == OP_NOT) {
1297                     op_type = OP_NOTSTAR - OP_STAR;  /* Use "not" opcodes */
1298                     c = previous[1];
1299                     goto OUTPUT_SINGLE_REPEAT;
1300                 }
1301
1302                 /* If previous was a character type match (\d or similar), abolish it and
1303                  create a suitable repeat item. The code is shared with single-character
1304                  repeats by setting op_type to add a suitable offset into repeat_type. */
1305
1306                 else if (*previous <= OP_NOT_NEWLINE) {
1307                     op_type = OP_TYPESTAR - OP_STAR;  /* Use type opcodes */
1308                     c = *previous;
1309
1310                 OUTPUT_SINGLE_REPEAT:
1311                     int prop_type = -1;
1312                     int prop_value = -1;
1313
1314                     uschar* oldcode = code;
1315                     code = previous;                  /* Usually overwrite previous item */
1316
1317                     /* If the maximum is zero then the minimum must also be zero; Perl allows
1318                      this case, so we do too - by simply omitting the item altogether. */
1319
1320                     if (repeat_max == 0)
1321                         goto END_REPEAT;
1322
1323                     /* Combine the op_type with the repeat_type */
1324
1325                     repeat_type += op_type;
1326
1327                     /* A minimum of zero is handled either as the special case * or ?, or as
1328                      an UPTO, with the maximum given. */
1329
1330                     if (repeat_min == 0) {
1331                         if (repeat_max == -1)
1332                             *code++ = OP_STAR + repeat_type;
1333                         else if (repeat_max == 1)
1334                             *code++ = OP_QUERY + repeat_type;
1335                         else {
1336                             *code++ = OP_UPTO + repeat_type;
1337                             put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max);
1338                         }
1339                     }
1340
1341                     /* A repeat minimum of 1 is optimized into some special cases. If the
1342                      maximum is unlimited, we use OP_PLUS. Otherwise, the original item it
1343                      left in place and, if the maximum is greater than 1, we use OP_UPTO with
1344                      one less than the maximum. */
1345
1346                     else if (repeat_min == 1) {
1347                         if (repeat_max == -1)
1348                             *code++ = OP_PLUS + repeat_type;
1349                         else {
1350                             code = oldcode;                 /* leave previous item in place */
1351                             if (repeat_max == 1)
1352                                 goto END_REPEAT;
1353                             *code++ = OP_UPTO + repeat_type;
1354                             put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max - 1);
1355                         }
1356                     }
1357
1358                     /* The case {n,n} is just an EXACT, while the general case {n,m} is
1359                      handled as an EXACT followed by an UPTO. */
1360
1361                     else {
1362                         *code++ = OP_EXACT + op_type;  /* NB EXACT doesn't have repeat_type */
1363                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_min);
1364
1365                         /* If the maximum is unlimited, insert an OP_STAR. Before doing so,
1366                          we have to insert the character for the previous code. For a repeated
1367                          Unicode property match, there are two extra bytes that define the
1368                          required property. In UTF-8 mode, long characters have their length in
1369                          c, with the 0x80 bit as a flag. */
1370
1371                         if (repeat_max < 0) {
1372                             if (c >= 128) {
1373                                 memcpy(code, utf8_char, c & 7);
1374                                 code += c & 7;
1375                             } else {
1376                                 *code++ = c;
1377                                 if (prop_type >= 0) {
1378                                     *code++ = prop_type;
1379                                     *code++ = prop_value;
1380                                 }
1381                             }
1382                             *code++ = OP_STAR + repeat_type;
1383                         }
1384
1385                         /* Else insert an UPTO if the max is greater than the min, again
1386                          preceded by the character, for the previously inserted code. */
1387
1388                         else if (repeat_max != repeat_min) {
1389                             if (c >= 128) {
1390                                 memcpy(code, utf8_char, c & 7);
1391                                 code += c & 7;
1392                             } else
1393                                 *code++ = c;
1394                             if (prop_type >= 0) {
1395                                 *code++ = prop_type;
1396                                 *code++ = prop_value;
1397                             }
1398                             repeat_max -= repeat_min;
1399                             *code++ = OP_UPTO + repeat_type;
1400                             put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max);
1401                         }
1402                     }
1403
1404                     /* The character or character type itself comes last in all cases. */
1405
1406                     if (c >= 128) {
1407                         memcpy(code, utf8_char, c & 7);
1408                         code += c & 7;
1409                     } else
1410                         *code++ = c;
1411
1412                     /* For a repeated Unicode property match, there are two extra bytes that
1413                      define the required property. */
1414
1415                     if (prop_type >= 0) {
1416                         *code++ = prop_type;
1417                         *code++ = prop_value;
1418                     }
1419                 }
1420
1421                 /* If previous was a character class or a back reference, we put the repeat
1422                  stuff after it, but just skip the item if the repeat was {0,0}. */
1423
1424                 else if (*previous == OP_CLASS ||
1425                          *previous == OP_NCLASS ||
1426                          *previous == OP_XCLASS ||
1427                          *previous == OP_REF)
1428                 {
1429                     if (repeat_max == 0) {
1430                         code = previous;
1431                         goto END_REPEAT;
1432                     }
1433
1434                     if (repeat_min == 0 && repeat_max == -1)
1435                         *code++ = OP_CRSTAR + repeat_type;
1436                     else if (repeat_min == 1 && repeat_max == -1)
1437                         *code++ = OP_CRPLUS + repeat_type;
1438                     else if (repeat_min == 0 && repeat_max == 1)
1439                         *code++ = OP_CRQUERY + repeat_type;
1440                     else {
1441                         *code++ = OP_CRRANGE + repeat_type;
1442                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_min);
1443                         if (repeat_max == -1)
1444                             repeat_max = 0;  /* 2-byte encoding for max */
1445                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max);
1446                     }
1447                 }
1448
1449                 /* If previous was a bracket group, we may have to replicate it in certain
1450                  cases. */
1451
1452                 else if (*previous >= OP_BRA || *previous == OP_ONCE) {
1453                     int ketoffset = 0;
1454                     int len = code - previous;
1455                     uschar* bralink = NULL;
1456
1457                     /* If the maximum repeat count is unlimited, find the end of the bracket
1458                      by scanning through from the start, and compute the offset back to it
1459                      from the current code pointer. There may be an OP_OPT setting following
1460                      the final KET, so we can't find the end just by going back from the code
1461                      pointer. */
1462
1463                     if (repeat_max == -1) {
1464                         uschar* ket = previous;
1465                         do {
1466                             ket += getOpcodeValueAtOffset(ket, 1);
1467                         } while (*ket != OP_KET);
1468                         ketoffset = code - ket;
1469                     }
1470
1471                     /* The case of a zero minimum is special because of the need to stick
1472                      OP_BRAZERO in front of it, and because the group appears once in the
1473                      data, whereas in other cases it appears the minimum number of times. For
1474                      this reason, it is simplest to treat this case separately, as otherwise
1475                      the code gets far too messy. There are several special subcases when the
1476                      minimum is zero. */
1477
1478                     if (repeat_min == 0) {
1479                         /* If the maximum is also zero, we just omit the group from the output
1480                          altogether. */
1481
1482                         if (repeat_max == 0) {
1483                             code = previous;
1484                             goto END_REPEAT;
1485                         }
1486
1487                         /* If the maximum is 1 or unlimited, we just have to stick in the
1488                          BRAZERO and do no more at this point. However, we do need to adjust
1489                          any OP_RECURSE calls inside the group that refer to the group itself or
1490                          any internal group, because the offset is from the start of the whole
1491                          regex. Temporarily terminate the pattern while doing this. */
1492
1493                         if (repeat_max <= 1) {
1494                             *code = OP_END;
1495                             memmove(previous+1, previous, len);
1496                             code++;
1497                             *previous++ = OP_BRAZERO + repeat_type;
1498                         }
1499
1500                         /* If the maximum is greater than 1 and limited, we have to replicate
1501                          in a nested fashion, sticking OP_BRAZERO before each set of brackets.
1502                          The first one has to be handled carefully because it's the original
1503                          copy, which has to be moved up. The remainder can be handled by code
1504                          that is common with the non-zero minimum case below. We have to
1505                          adjust the value or repeat_max, since one less copy is required. Once
1506                          again, we may have to adjust any OP_RECURSE calls inside the group. */
1507
1508                         else {
1509                             *code = OP_END;
1510                             memmove(previous + 2 + LINK_SIZE, previous, len);
1511                             code += 2 + LINK_SIZE;
1512                             *previous++ = OP_BRAZERO + repeat_type;
1513                             *previous++ = OP_BRA;
1514
1515                             /* We chain together the bracket offset fields that have to be
1516                              filled in later when the ends of the brackets are reached. */
1517
1518                             int offset = (!bralink) ? 0 : previous - bralink;
1519                             bralink = previous;
1520                             putOpcodeValueAtOffsetAndAdvance(previous, 0, offset);
1521                         }
1522
1523                         repeat_max--;
1524                     }
1525
1526                     /* If the minimum is greater than zero, replicate the group as many
1527                      times as necessary, and adjust the maximum to the number of subsequent
1528                      copies that we need. If we set a first char from the group, and didn't
1529                      set a required char, copy the latter from the former. */
1530
1531                     else {
1532                         if (repeat_min > 1) {
1533                             if (groupsetfirstbyte && reqbyte < 0)
1534                                 reqbyte = firstbyte;
1535                             for (int i = 1; i < repeat_min; i++) {
1536                                 memcpy(code, previous, len);
1537                                 code += len;
1538                             }
1539                         }
1540                         if (repeat_max > 0)
1541                             repeat_max -= repeat_min;
1542                     }
1543
1544                     /* This code is common to both the zero and non-zero minimum cases. If
1545                      the maximum is limited, it replicates the group in a nested fashion,
1546                      remembering the bracket starts on a stack. In the case of a zero minimum,
1547                      the first one was set up above. In all cases the repeat_max now specifies
1548                      the number of additional copies needed. */
1549
1550                     if (repeat_max >= 0) {
1551                         for (int i = repeat_max - 1; i >= 0; i--) {
1552                             *code++ = OP_BRAZERO + repeat_type;
1553
1554                             /* All but the final copy start a new nesting, maintaining the
1555                              chain of brackets outstanding. */
1556
1557                             if (i != 0) {
1558                                 *code++ = OP_BRA;
1559                                 int offset = (!bralink) ? 0 : code - bralink;
1560                                 bralink = code;
1561                                 putOpcodeValueAtOffsetAndAdvance(code, 0, offset);
1562                             }
1563
1564                             memcpy(code, previous, len);
1565                             code += len;
1566                         }
1567
1568                         /* Now chain through the pending brackets, and fill in their length
1569                          fields (which are holding the chain links pro tem). */
1570
1571                         while (bralink) {
1572                             int offset = code - bralink + 1;
1573                             uschar* bra = code - offset;
1574                             int oldlinkoffset = getOpcodeValueAtOffset(bra, 1);
1575                             bralink = oldlinkoffset ? 0 : bralink - oldlinkoffset;
1576                             *code++ = OP_KET;
1577                             putOpcodeValueAtOffsetAndAdvance(code, 0, offset);
1578                             putOpcodeValueAtOffset(bra, 1, offset);
1579                         }
1580                     }
1581
1582                     /* If the maximum is unlimited, set a repeater in the final copy. We
1583                      can't just offset backwards from the current code point, because we
1584                      don't know if there's been an options resetting after the ket. The
1585                      correct offset was computed above. */
1586
1587                     else
1588                         code[-ketoffset] = OP_KETRMAX + repeat_type;
1589                 }
1590
1591                 /* Else there's some kind of shambles */
1592
1593                 else {
1594                     *errorcodeptr = ERR11;
1595                     goto FAILED;
1596                 }
1597
1598                 /* In all case we no longer have a previous item. We also set the
1599                  "follows varying string" flag for subsequently encountered reqbytes if
1600                  it isn't already set and we have just passed a varying length item. */
1601
1602             END_REPEAT:
1603                 previous = NULL;
1604                 cd.req_varyopt |= reqvary;
1605                 break;
1606
1607             /* Start of nested bracket sub-expression, or comment or lookahead or
1608              lookbehind or option setting or condition. First deal with special things
1609              that can come after a bracket; all are introduced by ?, and the appearance
1610              of any of them means that this is not a referencing group. They were
1611              checked for validity in the first pass over the string, so we don't have to
1612              check for syntax errors here.  */
1613
1614             case '(':
1615                 skipbytes = 0;
1616
1617                 if (*(++ptr) == '?') {
1618                     switch (*(++ptr)) {
1619                     case ':':                 /* Non-extracting bracket */
1620                         bravalue = OP_BRA;
1621                         ptr++;
1622                         break;
1623
1624                     case '=':                 /* Positive lookahead */
1625                         bravalue = OP_ASSERT;
1626                         ptr++;
1627                         break;
1628
1629                     case '!':                 /* Negative lookahead */
1630                         bravalue = OP_ASSERT_NOT;
1631                         ptr++;
1632                         break;
1633
1634                         /* Character after (? not specially recognized */
1635
1636                     default:                  /* Option setting */
1637                         *errorcodeptr = ERR12;
1638                         goto FAILED;
1639                     }
1640                 }
1641
1642                 /* Else we have a referencing group; adjust the opcode. If the bracket
1643                  number is greater than EXTRACT_BASIC_MAX, we set the opcode one higher, and
1644                  arrange for the true number to follow later, in an OP_BRANUMBER item. */
1645
1646                 else {
1647                     if (++(*brackets) > EXTRACT_BASIC_MAX) {
1648                         bravalue = OP_BRA + EXTRACT_BASIC_MAX + 1;
1649                         code[1 + LINK_SIZE] = OP_BRANUMBER;
1650                         put2ByteOpcodeValueAtOffset(code, 2+LINK_SIZE, *brackets);
1651                         skipbytes = 3;
1652                     }
1653                     else
1654                         bravalue = OP_BRA + *brackets;
1655                 }
1656
1657                 /* Process nested bracketed re. Assertions may not be repeated, but other
1658                  kinds can be. We copy code into a non-variable in order to be able
1659                  to pass its address because some compilers complain otherwise. Pass in a
1660                  new setting for the ims options if they have changed. */
1661
1662                 previous = (bravalue >= OP_ONCE) ? code : 0;
1663                 *code = bravalue;
1664                 tempcode = code;
1665                 tempreqvary = cd.req_varyopt;     /* Save value before bracket */
1666
1667                 if (!compile_regex(
1668                                    options,
1669                                    brackets,                     /* Extracting bracket count */
1670                                    &tempcode,                    /* Where to put code (updated) */
1671                                    &ptr,                         /* Input pointer (updated) */
1672                                    patternEnd,
1673                                    errorcodeptr,                 /* Where to put an error message */
1674                                    skipbytes,                    /* Skip over OP_BRANUMBER */
1675                                    &subfirstbyte,                /* For possible first char */
1676                                    &subreqbyte,                  /* For possible last char */
1677                                    cd))                          /* Tables block */
1678                     goto FAILED;
1679
1680                 /* At the end of compiling, code is still pointing to the start of the
1681                  group, while tempcode has been updated to point past the end of the group
1682                  and any option resetting that may follow it. The pattern pointer (ptr)
1683                  is on the bracket. */
1684
1685                 /* Handle updating of the required and first characters. Update for normal
1686                  brackets of all kinds, and conditions with two branches (see code above).
1687                  If the bracket is followed by a quantifier with zero repeat, we have to
1688                  back off. Hence the definition of zeroreqbyte and zerofirstbyte outside the
1689                  main loop so that they can be accessed for the back off. */
1690
1691                 zeroreqbyte = reqbyte;
1692                 zerofirstbyte = firstbyte;
1693                 groupsetfirstbyte = false;
1694
1695                 if (bravalue >= OP_BRA || bravalue == OP_ONCE) {
1696                     /* If we have not yet set a firstbyte in this branch, take it from the
1697                      subpattern, remembering that it was set here so that a repeat of more
1698                      than one can replicate it as reqbyte if necessary. If the subpattern has
1699                      no firstbyte, set "none" for the whole branch. In both cases, a zero
1700                      repeat forces firstbyte to "none". */
1701
1702                     if (firstbyte == REQ_UNSET) {
1703                         if (subfirstbyte >= 0) {
1704                             firstbyte = subfirstbyte;
1705                             groupsetfirstbyte = true;
1706                         }
1707                         else
1708                             firstbyte = REQ_NONE;
1709                         zerofirstbyte = REQ_NONE;
1710                     }
1711
1712                     /* If firstbyte was previously set, convert the subpattern's firstbyte
1713                      into reqbyte if there wasn't one, using the vary flag that was in
1714                      existence beforehand. */
1715
1716                     else if (subfirstbyte >= 0 && subreqbyte < 0)
1717                         subreqbyte = subfirstbyte | tempreqvary;
1718
1719                     /* If the subpattern set a required byte (or set a first byte that isn't
1720                      really the first byte - see above), set it. */
1721
1722                     if (subreqbyte >= 0)
1723                         reqbyte = subreqbyte;
1724                 }
1725
1726                 /* For a forward assertion, we take the reqbyte, if set. This can be
1727                  helpful if the pattern that follows the assertion doesn't set a different
1728                  char. For example, it's useful for /(?=abcde).+/. We can't set firstbyte
1729                  for an assertion, however because it leads to incorrect effect for patterns
1730                  such as /(?=a)a.+/ when the "real" "a" would then become a reqbyte instead
1731                  of a firstbyte. This is overcome by a scan at the end if there's no
1732                  firstbyte, looking for an asserted first char. */
1733
1734                 else if (bravalue == OP_ASSERT && subreqbyte >= 0)
1735                     reqbyte = subreqbyte;
1736
1737                 /* Now update the main code pointer to the end of the group. */
1738
1739                 code = tempcode;
1740
1741                 /* Error if hit end of pattern */
1742
1743                 if (ptr >= patternEnd || *ptr != ')') {
1744                     *errorcodeptr = ERR14;
1745                     goto FAILED;
1746                 }
1747                 break;
1748
1749             /* Check \ for being a real metacharacter; if not, fall through and handle
1750              it as a data character at the start of a string. Escape items are checked
1751              for validity in the pre-compiling pass. */
1752
1753             case '\\':
1754                 tempptr = ptr;
1755                 c = check_escape(&ptr, patternEnd, errorcodeptr, *brackets, false);
1756
1757                 /* Handle metacharacters introduced by \. For ones like \d, the ESC_ values
1758                  are arranged to be the negation of the corresponding OP_values. For the
1759                  back references, the values are ESC_REF plus the reference number. Only
1760                  back references and those types that consume a character may be repeated.
1761                  We can test for values between ESC_b and ESC_w for the latter; this may
1762                  have to change if any new ones are ever created. */
1763
1764                 if (c < 0) {
1765                     /* For metasequences that actually match a character, we disable the
1766                      setting of a first character if it hasn't already been set. */
1767
1768                     if (firstbyte == REQ_UNSET && -c > ESC_b && -c <= ESC_w)
1769                         firstbyte = REQ_NONE;
1770
1771                     /* Set values to reset to if this is followed by a zero repeat. */
1772
1773                     zerofirstbyte = firstbyte;
1774                     zeroreqbyte = reqbyte;
1775
1776                     /* Back references are handled specially */
1777
1778                     if (-c >= ESC_REF) {
1779                         int number = -c - ESC_REF;
1780                         previous = code;
1781                         *code++ = OP_REF;
1782                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, number);
1783                     }
1784
1785                     /* For the rest, we can obtain the OP value by negating the escape
1786                      value */
1787
1788                     else {
1789                         previous = (-c > ESC_b && -c <= ESC_w)? code : NULL;
1790                         *code++ = -c;
1791                     }
1792                     continue;
1793                 }
1794
1795                 /* Fall through. */
1796
1797                 /* Handle a literal character. It is guaranteed not to be whitespace or #
1798                  when the extended flag is set. If we are in UTF-8 mode, it may be a
1799                  multi-byte literal character. */
1800
1801                 default:
1802             NORMAL_CHAR:
1803
1804                 previous = code;
1805
1806                 if (c < 128) {
1807                     mclength = 1;
1808                     mcbuffer[0] = c;
1809
1810                     if ((options & IgnoreCaseOption) && (c | 0x20) >= 'a' && (c | 0x20) <= 'z') {
1811                         *code++ = OP_ASCII_LETTER_IGNORING_CASE;
1812                         *code++ = c | 0x20;
1813                     } else {
1814                         *code++ = OP_ASCII_CHAR;
1815                         *code++ = c;
1816                     }
1817                 } else {
1818                     mclength = _pcre_ord2utf8(c, mcbuffer);
1819
1820                     *code++ = (options & IgnoreCaseOption) ? OP_CHAR_IGNORING_CASE : OP_CHAR;
1821                     for (c = 0; c < mclength; c++)
1822                         *code++ = mcbuffer[c];
1823                 }
1824
1825                 /* Set the first and required bytes appropriately. If no previous first
1826                  byte, set it from this character, but revert to none on a zero repeat.
1827                  Otherwise, leave the firstbyte value alone, and don't change it on a zero
1828                  repeat. */
1829
1830                 if (firstbyte == REQ_UNSET) {
1831                     zerofirstbyte = REQ_NONE;
1832                     zeroreqbyte = reqbyte;
1833
1834                     /* If the character is more than one byte long, we can set firstbyte
1835                      only if it is not to be matched caselessly. */
1836
1837                     if (mclength == 1 || req_caseopt == 0) {
1838                         firstbyte = mcbuffer[0] | req_caseopt;
1839                         if (mclength != 1)
1840                             reqbyte = code[-1] | cd.req_varyopt;
1841                     }
1842                     else
1843                         firstbyte = reqbyte = REQ_NONE;
1844                 }
1845
1846                 /* firstbyte was previously set; we can set reqbyte only the length is
1847                  1 or the matching is caseful. */
1848
1849                 else {
1850                     zerofirstbyte = firstbyte;
1851                     zeroreqbyte = reqbyte;
1852                     if (mclength == 1 || req_caseopt == 0)
1853                         reqbyte = code[-1] | req_caseopt | cd.req_varyopt;
1854                 }
1855
1856                 break;            /* End of literal character handling */
1857         }
1858     }                   /* end of big loop */
1859
1860     /* Control never reaches here by falling through, only by a goto for all the
1861      error states. Pass back the position in the pattern so that it can be displayed
1862      to the user for diagnosing the error. */
1863
1864 FAILED:
1865     *ptrptr = ptr;
1866     return false;
1867 }
1868
1869
1870
1871
1872 /*************************************************
1873 *     Compile sequence of alternatives           *
1874 *************************************************/
1875
1876 /* On entry, ptr is pointing past the bracket character, but on return
1877 it points to the closing bracket, or vertical bar, or end of string.
1878 The code variable is pointing at the byte into which the BRA operator has been
1879 stored. If the ims options are changed at the start (for a (?ims: group) or
1880 during any branch, we need to insert an OP_OPT item at the start of every
1881 following branch to ensure they get set correctly at run time, and also pass
1882 the new options into every subsequent branch compile.
1883
1884 Argument:
1885   options        option bits, including any changes for this subpattern
1886   brackets       -> int containing the number of extracting brackets used
1887   codeptr        -> the address of the current code pointer
1888   ptrptr         -> the address of the current pattern pointer
1889   errorcodeptr   -> pointer to error code variable
1890   skipbytes      skip this many bytes at start (for OP_BRANUMBER)
1891   firstbyteptr   place to put the first required character, or a negative number
1892   reqbyteptr     place to put the last required character, or a negative number
1893   cd             points to the data block with tables pointers etc.
1894
1895 Returns:      true on success
1896 */
1897
1898 static bool
1899 compile_regex(int options, int* brackets, uschar** codeptr,
1900               const UChar** ptrptr, const UChar* patternEnd, ErrorCode* errorcodeptr, int skipbytes,
1901               int* firstbyteptr, int* reqbyteptr, CompileData& cd)
1902 {
1903     const UChar* ptr = *ptrptr;
1904     uschar* code = *codeptr;
1905     uschar* last_branch = code;
1906     uschar* start_bracket = code;
1907     int firstbyte, reqbyte;
1908     int branchfirstbyte, branchreqbyte;
1909
1910     firstbyte = reqbyte = REQ_UNSET;
1911
1912     /* Offset is set zero to mark that this bracket is still open */
1913
1914     putOpcodeValueAtOffset(code, 1, 0);
1915     code += 1 + LINK_SIZE + skipbytes;
1916
1917     /* Loop for each alternative branch */
1918
1919     while (true) {
1920         /* Now compile the branch */
1921
1922         if (!compile_branch(options, brackets, &code, &ptr, patternEnd, errorcodeptr,
1923                             &branchfirstbyte, &branchreqbyte, cd)) {
1924             *ptrptr = ptr;
1925             return false;
1926         }
1927
1928         /* If this is the first branch, the firstbyte and reqbyte values for the
1929          branch become the values for the regex. */
1930
1931         if (*last_branch != OP_ALT) {
1932             firstbyte = branchfirstbyte;
1933             reqbyte = branchreqbyte;
1934         }
1935
1936         /* If this is not the first branch, the first char and reqbyte have to
1937          match the values from all the previous branches, except that if the previous
1938          value for reqbyte didn't have REQ_VARY set, it can still match, and we set
1939          REQ_VARY for the regex. */
1940
1941         else {
1942             /* If we previously had a firstbyte, but it doesn't match the new branch,
1943              we have to abandon the firstbyte for the regex, but if there was previously
1944              no reqbyte, it takes on the value of the old firstbyte. */
1945
1946             if (firstbyte >= 0 && firstbyte != branchfirstbyte) {
1947                 if (reqbyte < 0)
1948                     reqbyte = firstbyte;
1949                 firstbyte = REQ_NONE;
1950             }
1951
1952             /* If we (now or from before) have no firstbyte, a firstbyte from the
1953              branch becomes a reqbyte if there isn't a branch reqbyte. */
1954
1955             if (firstbyte < 0 && branchfirstbyte >= 0 && branchreqbyte < 0)
1956                 branchreqbyte = branchfirstbyte;
1957
1958             /* Now ensure that the reqbytes match */
1959
1960             if ((reqbyte & ~REQ_VARY) != (branchreqbyte & ~REQ_VARY))
1961                 reqbyte = REQ_NONE;
1962             else
1963                 reqbyte |= branchreqbyte;   /* To "or" REQ_VARY */
1964         }
1965
1966         /* Reached end of expression, either ')' or end of pattern. Go back through
1967          the alternative branches and reverse the chain of offsets, with the field in
1968          the BRA item now becoming an offset to the first alternative. If there are
1969          no alternatives, it points to the end of the group. The length in the
1970          terminating ket is always the length of the whole bracketed item. If any of
1971          the ims options were changed inside the group, compile a resetting op-code
1972          following, except at the very end of the pattern. Return leaving the pointer
1973          at the terminating char. */
1974
1975         if (ptr >= patternEnd || *ptr != '|') {
1976             int length = code - last_branch;
1977             do {
1978                 int prev_length = getOpcodeValueAtOffset(last_branch, 1);
1979                 putOpcodeValueAtOffset(last_branch, 1, length);
1980                 length = prev_length;
1981                 last_branch -= length;
1982             } while (length > 0);
1983
1984             /* Fill in the ket */
1985
1986             *code = OP_KET;
1987             putOpcodeValueAtOffset(code, 1, code - start_bracket);
1988             code += 1 + LINK_SIZE;
1989
1990             /* Set values to pass back */
1991
1992             *codeptr = code;
1993             *ptrptr = ptr;
1994             *firstbyteptr = firstbyte;
1995             *reqbyteptr = reqbyte;
1996             return true;
1997         }
1998
1999         /* Another branch follows; insert an "or" node. Its length field points back
2000          to the previous branch while the bracket remains open. At the end the chain
2001          is reversed. It's done like this so that the start of the bracket has a
2002          zero offset until it is closed, making it possible to detect recursion. */
2003
2004         *code = OP_ALT;
2005         putOpcodeValueAtOffset(code, 1, code - last_branch);
2006         last_branch = code;
2007         code += 1 + LINK_SIZE;
2008         ptr++;
2009     }
2010     ASSERT_NOT_REACHED();
2011 }
2012
2013
2014 /*************************************************
2015 *          Check for anchored expression         *
2016 *************************************************/
2017
2018 /* Try to find out if this is an anchored regular expression. Consider each
2019 alternative branch. If they all start with OP_SOD or OP_CIRC, or with a bracket
2020 all of whose alternatives start with OP_SOD or OP_CIRC (recurse ad lib), then
2021 it's anchored. However, if this is a multiline pattern, then only OP_SOD
2022 counts, since OP_CIRC can match in the middle.
2023
2024 We can also consider a regex to be anchored if OP_SOM starts all its branches.
2025 This is the code for \G, which means "match at start of match position, taking
2026 into account the match offset".
2027
2028 A branch is also implicitly anchored if it starts with .* and DOTALL is set,
2029 because that will try the rest of the pattern at all possible matching points,
2030 so there is no point trying again.... er ....
2031
2032 .... except when the .* appears inside capturing parentheses, and there is a
2033 subsequent back reference to those parentheses. We haven't enough information
2034 to catch that case precisely.
2035
2036 At first, the best we could do was to detect when .* was in capturing brackets
2037 and the highest back reference was greater than or equal to that level.
2038 However, by keeping a bitmap of the first 31 back references, we can catch some
2039 of the more common cases more precisely.
2040
2041 Arguments:
2042   code           points to start of expression (the bracket)
2043   options        points to the options setting
2044   bracket_map    a bitmap of which brackets we are inside while testing; this
2045                   handles up to substring 31; after that we just have to take
2046                   the less precise approach
2047   backref_map    the back reference bitmap
2048
2049 Returns:     true or false
2050 */
2051
2052 static bool is_anchored(const uschar* code, int options, unsigned bracket_map, unsigned backref_map)
2053 {
2054     do {
2055         const uschar* scode = firstSignificantOpCode(code + 1 + LINK_SIZE);
2056         int op = *scode;
2057
2058         /* Capturing brackets */
2059         if (op > OP_BRA) {
2060             op -= OP_BRA;
2061             if (op > EXTRACT_BASIC_MAX)
2062                 op = get2ByteOpcodeValueAtOffset(scode, 2 + LINK_SIZE);
2063             int new_map = bracket_map | ((op < 32)? (1 << op) : 1);
2064             if (!is_anchored(scode, options, new_map, backref_map))
2065                 return false;
2066         }
2067
2068         /* Other brackets */
2069         else if (op == OP_BRA || op == OP_ASSERT || op == OP_ONCE) {
2070             if (!is_anchored(scode, options, bracket_map, backref_map))
2071                 return false;
2072
2073         /* Check for explicit anchoring */
2074
2075         } else if ((options & MatchAcrossMultipleLinesOption) || op != OP_CIRC)
2076             return false;
2077         code += getOpcodeValueAtOffset(code, 1);
2078     } while (*code == OP_ALT);   /* Loop for each alternative */
2079     return true;
2080 }
2081
2082
2083
2084 /*************************************************
2085 *         Check for starting with ^ or .*        *
2086 *************************************************/
2087
2088 /* This is called to find out if every branch starts with ^ or .* so that
2089 "first char" processing can be done to speed things up in multiline
2090 matching and for non-DOTALL patterns that start with .* (which must start at
2091 the beginning or after \n). As in the case of is_anchored() (see above), we
2092 have to take account of back references to capturing brackets that contain .*
2093 because in that case we can't make the assumption.
2094
2095 Arguments:
2096   code           points to start of expression (the bracket)
2097   bracket_map    a bitmap of which brackets we are inside while testing; this
2098                   handles up to substring 31; after that we just have to take
2099                   the less precise approach
2100   backref_map    the back reference bitmap
2101 */
2102
2103 static bool canApplyFirstCharOptimization(const uschar* code, unsigned bracket_map, unsigned backref_map)
2104 {
2105     do {
2106         const uschar* scode = firstSignificantOpCode(code + 1 + LINK_SIZE);
2107         int op = *scode;
2108
2109         /* Capturing brackets */
2110         if (op > OP_BRA) {
2111             op -= OP_BRA;
2112             if (op > EXTRACT_BASIC_MAX)
2113                 op = get2ByteOpcodeValueAtOffset(scode, 2+LINK_SIZE);
2114             int new_map = bracket_map | ((op < 32)? (1 << op) : 1);
2115             if (!canApplyFirstCharOptimization(scode, new_map, backref_map))
2116                 return false;
2117         }
2118
2119         /* Other brackets */
2120         else if (op == OP_BRA || op == OP_ASSERT || op == OP_ONCE) {
2121             if (!canApplyFirstCharOptimization(scode, bracket_map, backref_map))
2122                 return false;
2123
2124         /* .* means "start at start or after \n" if it isn't in brackets that
2125          may be referenced. */
2126
2127         } else if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR) {
2128             if (scode[1] != OP_NOT_NEWLINE || (bracket_map & backref_map))
2129                 return false;
2130         } else if (op != OP_CIRC) /* Check for explicit circumflex */
2131             return false;
2132
2133         /* Move on to the next alternative */
2134
2135         code += getOpcodeValueAtOffset(code, 1);
2136     } while (*code == OP_ALT);  /* Loop for each alternative */
2137     return true;
2138 }
2139
2140
2141 /*************************************************
2142 *       Check for asserted fixed first char      *
2143 *************************************************/
2144
2145 /* During compilation, the "first char" settings from forward assertions are
2146 discarded, because they can cause conflicts with actual literals that follow.
2147 However, if we end up without a first char setting for an unanchored pattern,
2148 it is worth scanning the regex to see if there is an initial asserted first
2149 char. If all branches start with the same asserted char, or with a bracket all
2150 of whose alternatives start with the same asserted char (recurse ad lib), then
2151 we return that char, otherwise -1.
2152
2153 Arguments:
2154   code       points to start of expression (the bracket)
2155   options    pointer to the options (used to check casing changes)
2156   inassert   true if in an assertion
2157
2158 Returns:     -1 or the fixed first char
2159 */
2160
2161 static int find_firstassertedchar(const uschar* code, int options, bool inassert)
2162 {
2163     int c = -1;
2164     do {
2165         const uschar* scode = firstSignificantOpCodeSkippingAssertions(code + 1 + LINK_SIZE);
2166         int op = *scode;
2167
2168         if (op >= OP_BRA)
2169             op = OP_BRA;
2170
2171         switch (op) {
2172             default:
2173                 return -1;
2174
2175             case OP_BRA:
2176             case OP_ASSERT:
2177             case OP_ONCE: {
2178                 int d;
2179                 if ((d = find_firstassertedchar(scode, options, op == OP_ASSERT)) < 0)
2180                     return -1;
2181                 if (c < 0)
2182                     c = d;
2183                 else if (c != d)
2184                     return -1;
2185                 break;
2186             }
2187
2188             case OP_EXACT:
2189                 scode += 2;
2190                 /* Fall through */
2191
2192             case OP_CHAR:
2193             case OP_CHAR_IGNORING_CASE:
2194             case OP_ASCII_CHAR:
2195             case OP_ASCII_LETTER_IGNORING_CASE:
2196             case OP_PLUS:
2197             case OP_MINPLUS:
2198                 if (!inassert)
2199                     return -1;
2200                 if (c < 0) {
2201                     c = scode[1];
2202                     if (options & IgnoreCaseOption)
2203                         c |= REQ_IGNORE_CASE;
2204                 }
2205                 else if (c != scode[1])
2206                     return -1;
2207                 break;
2208         }
2209
2210         code += getOpcodeValueAtOffset(code, 1);
2211     } while (*code == OP_ALT);
2212     return c;
2213 }
2214
2215 static int calculateCompiledPatternLengthAndFlags(const UChar* pattern, int patternLength, JSRegExpIgnoreCaseOption ignoreCase, CompileData& compile_block, ErrorCode& errorcode)
2216 {
2217     /* Make a pass over the pattern to compute the
2218      amount of store required to hold the compiled code. This does not have to be
2219      perfect as long as errors are overestimates. At the same time we can detect any
2220      flag settings right at the start, and extract them. Make an attempt to correct
2221      for any counted white space if an "extended" flag setting appears late in the
2222      pattern. We can't be so clever for #-comments. */
2223
2224     int length = 1 + LINK_SIZE;      /* For initial BRA plus length */
2225     int branch_extra = 0;
2226     int lastitemlength = 0;
2227     unsigned brastackptr = 0;
2228     int brastack[BRASTACK_SIZE];
2229     uschar bralenstack[BRASTACK_SIZE];
2230     int item_count = -1;
2231     int bracount = 0;
2232
2233     const UChar* ptr = (const UChar*)(pattern - 1);
2234     const UChar* patternEnd = (const UChar*)(pattern + patternLength);
2235
2236     while (++ptr < patternEnd) {
2237         int minRepeats = 0, maxRepeats = 0;
2238         int c = *ptr;
2239
2240         item_count++;    /* Is zero for the first non-comment item */
2241
2242         switch (c) {
2243             /* A backslashed item may be an escaped data character or it may be a
2244              character type. */
2245
2246             case '\\':
2247                 c = check_escape(&ptr, patternEnd, &errorcode, bracount, false);
2248                 if (errorcode != 0)
2249                     return -1;
2250
2251                 lastitemlength = 1;     /* Default length of last item for repeats */
2252
2253                 if (c >= 0) {            /* Data character */
2254                     length += 2;          /* For a one-byte character */
2255
2256                     if (c > 127) {
2257                         int i;
2258                         for (i = 0; i < _pcre_utf8_table1_size; i++)
2259                             if (c <= _pcre_utf8_table1[i]) break;
2260                         length += i;
2261                         lastitemlength += i;
2262                     }
2263
2264                     continue;
2265                 }
2266
2267                 /* Other escapes need one byte */
2268
2269                 length++;
2270
2271                 /* A back reference needs an additional 2 bytes, plus either one or 5
2272                  bytes for a repeat. We also need to keep the value of the highest
2273                  back reference. */
2274
2275                 if (c <= -ESC_REF) {
2276                     int refnum = -c - ESC_REF;
2277                     compile_block.backref_map |= (refnum < 32)? (1 << refnum) : 1;
2278                     if (refnum > compile_block.top_backref)
2279                         compile_block.top_backref = refnum;
2280                     length += 2;   /* For single back reference */
2281                     if (ptr[1] == '{' && is_counted_repeat(ptr+2, patternEnd)) {
2282                         ptr = read_repeat_counts(ptr+2, &minRepeats, &maxRepeats, &errorcode);
2283                         if (errorcode)
2284                             return -1;
2285                         if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) ||
2286                             (minRepeats == 1 && maxRepeats == -1))
2287                             length++;
2288                         else
2289                             length += 5;
2290                         if (ptr[1] == '?')
2291                             ptr++;
2292                     }
2293                 }
2294                 continue;
2295
2296             case '^':     /* Single-byte metacharacters */
2297             case '.':
2298             case '$':
2299                 length++;
2300                 lastitemlength = 1;
2301                 continue;
2302
2303             case '*':            /* These repeats won't be after brackets; */
2304             case '+':            /* those are handled separately */
2305             case '?':
2306                 length++;
2307                 goto POSSESSIVE;
2308
2309             /* This covers the cases of braced repeats after a single char, metachar,
2310              class, or back reference. */
2311
2312             case '{':
2313                 if (!is_counted_repeat(ptr+1, patternEnd))
2314                     goto NORMAL_CHAR;
2315                 ptr = read_repeat_counts(ptr+1, &minRepeats, &maxRepeats, &errorcode);
2316                 if (errorcode != 0)
2317                     return -1;
2318
2319                 /* These special cases just insert one extra opcode */
2320
2321                 if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) ||
2322                     (minRepeats == 1 && maxRepeats == -1))
2323                     length++;
2324
2325                 /* These cases might insert additional copies of a preceding character. */
2326
2327                 else {
2328                     if (minRepeats != 1) {
2329                         length -= lastitemlength;   /* Uncount the original char or metachar */
2330                         if (minRepeats > 0)
2331                             length += 3 + lastitemlength;
2332                     }
2333                     length += lastitemlength + ((maxRepeats > 0)? 3 : 1);
2334                 }
2335
2336                 if (ptr[1] == '?')
2337                     ptr++;      /* Needs no extra length */
2338
2339             POSSESSIVE:                     /* Test for possessive quantifier */
2340                 if (ptr[1] == '+') {
2341                     ptr++;
2342                     length += 2 + 2 * LINK_SIZE;   /* Allow for atomic brackets */
2343                 }
2344                 continue;
2345
2346             /* An alternation contains an offset to the next branch or ket. If any ims
2347              options changed in the previous branch(es), and/or if we are in a
2348              lookbehind assertion, extra space will be needed at the start of the
2349              branch. This is handled by branch_extra. */
2350
2351             case '|':
2352                 length += 1 + LINK_SIZE + branch_extra;
2353                 continue;
2354
2355             /* A character class uses 33 characters provided that all the character
2356              values are less than 256. Otherwise, it uses a bit map for low valued
2357              characters, and individual items for others. Don't worry about character
2358              types that aren't allowed in classes - they'll get picked up during the
2359              compile. A character class that contains only one single-byte character
2360              uses 2 or 3 bytes, depending on whether it is negated or not. Notice this
2361              where we can. (In UTF-8 mode we can do this only for chars < 128.) */
2362
2363             case '[': {
2364                 int class_optcount;
2365                 if (*(++ptr) == '^') {
2366                     class_optcount = 10;  /* Greater than one */
2367                     ptr++;
2368                 }
2369                 else
2370                     class_optcount = 0;
2371
2372                 bool class_utf8 = false;
2373
2374                 for (; ptr < patternEnd && *ptr != ']'; ++ptr) {
2375                     /* Check for escapes */
2376
2377                     if (*ptr == '\\') {
2378                         c = check_escape(&ptr, patternEnd, &errorcode, bracount, true);
2379                         if (errorcode != 0)
2380                             return -1;
2381
2382                         /* \b is backspace inside a class; \X is literal */
2383
2384                         if (-c == ESC_b)
2385                             c = '\b';
2386
2387                         /* Handle escapes that turn into characters */
2388
2389                         if (c >= 0)
2390                             goto NON_SPECIAL_CHARACTER;
2391
2392                         /* Escapes that are meta-things. The normal ones just affect the
2393                          bit map, but Unicode properties require an XCLASS extended item. */
2394
2395                         else
2396                             class_optcount = 10;         /* \d, \s etc; make sure > 1 */
2397                     }
2398
2399                     /* Anything else increments the possible optimization count. We have to
2400                      detect ranges here so that we can compute the number of extra ranges for
2401                      caseless wide characters when UCP support is available. If there are wide
2402                      characters, we are going to have to use an XCLASS, even for single
2403                      characters. */
2404
2405                     else {
2406                         c = *ptr;
2407
2408                         /* Come here from handling \ above when it escapes to a char value */
2409
2410                     NON_SPECIAL_CHARACTER:
2411                         class_optcount++;
2412
2413                         int d = -1;
2414                         if (ptr + 1 < patternEnd && ptr[1] == '-') {
2415                             UChar const *hyptr = ptr++;
2416                             if (ptr + 1 < patternEnd && ptr[1] == '\\') {
2417                                 ptr++;
2418                                 d = check_escape(&ptr, patternEnd, &errorcode, bracount, true);
2419                                 if (errorcode != 0)
2420                                     return -1;
2421                                 if (-d == ESC_b)
2422                                     d = '\b';        /* backspace */
2423                             }
2424                             else if (ptr + 1 < patternEnd && ptr[1] != ']')
2425                                 d = *++ptr;
2426                             if (d < 0)
2427                                 ptr = hyptr;      /* go back to hyphen as data */
2428                         }
2429
2430                         /* If d >= 0 we have a range. In UTF-8 mode, if the end is > 255, or >
2431                          127 for caseless matching, we will need to use an XCLASS. */
2432
2433                         if (d >= 0) {
2434                             class_optcount = 10;     /* Ensure > 1 */
2435                             if (d < c) {
2436                                 errorcode = ERR8;
2437                                 return -1;
2438                             }
2439
2440                             if ((d > 255 || (ignoreCase && d > 127))) {
2441                                 uschar buffer[6];
2442                                 if (!class_utf8)         /* Allow for XCLASS overhead */
2443                                 {
2444                                     class_utf8 = true;
2445                                     length += LINK_SIZE + 2;
2446                                 }
2447
2448                                 /* If we have UCP support, find out how many extra ranges are
2449                                  needed to map the other case of characters within this range. We
2450                                  have to mimic the range optimization here, because extending the
2451                                  range upwards might push d over a boundary that makes it use
2452                                  another byte in the UTF-8 representation. */
2453
2454                                 if (ignoreCase) {
2455                                     int occ, ocd;
2456                                     int cc = c;
2457                                     int origd = d;
2458                                     while (get_othercase_range(&cc, origd, &occ, &ocd)) {
2459                                         if (occ >= c && ocd <= d)
2460                                             continue;   /* Skip embedded */
2461
2462                                         if (occ < c  && ocd >= c - 1)  /* Extend the basic range */
2463                                         {                            /* if there is overlap,   */
2464                                             c = occ;                     /* noting that if occ < c */
2465                                             continue;                    /* we can't have ocd > d  */
2466                                         }                            /* because a subrange is  */
2467                                         if (ocd > d && occ <= d + 1)   /* always shorter than    */
2468                                         {                            /* the basic range.       */
2469                                             d = ocd;
2470                                             continue;
2471                                         }
2472
2473                                         /* An extra item is needed */
2474
2475                                         length += 1 + _pcre_ord2utf8(occ, buffer) +
2476                                         ((occ == ocd)? 0 : _pcre_ord2utf8(ocd, buffer));
2477                                     }
2478                                 }
2479
2480                                 /* The length of the (possibly extended) range */
2481
2482                                 length += 1 + _pcre_ord2utf8(c, buffer) + _pcre_ord2utf8(d, buffer);
2483                             }
2484
2485                         }
2486
2487                         /* We have a single character. There is nothing to be done unless we
2488                          are in UTF-8 mode. If the char is > 255, or 127 when caseless, we must
2489                          allow for an XCL_SINGLE item, doubled for caselessness if there is UCP
2490                          support. */
2491
2492                         else {
2493                             if ((c > 255 || (ignoreCase && c > 127))) {
2494                                 uschar buffer[6];
2495                                 class_optcount = 10;     /* Ensure > 1 */
2496                                 if (!class_utf8)         /* Allow for XCLASS overhead */
2497                                 {
2498                                     class_utf8 = true;
2499                                     length += LINK_SIZE + 2;
2500                                 }
2501                                 length += (ignoreCase ? 2 : 1) * (1 + _pcre_ord2utf8(c, buffer));
2502                             }
2503                         }
2504                     }
2505                 }
2506
2507                 if (ptr >= patternEnd) {   /* Missing terminating ']' */
2508                     errorcode = ERR6;
2509                     return -1;
2510                 }
2511
2512                 /* We can optimize when there was only one optimizable character. Repeats
2513                  for positive and negated single one-byte chars are handled by the general
2514                  code. Here, we handle repeats for the class opcodes. */
2515
2516                 if (class_optcount == 1)
2517                     length += 3;
2518                 else {
2519                     length += 33;
2520
2521                     /* A repeat needs either 1 or 5 bytes. If it is a possessive quantifier,
2522                      we also need extra for wrapping the whole thing in a sub-pattern. */
2523
2524                     if (ptr + 1 < patternEnd && ptr[1] == '{' && is_counted_repeat(ptr+2, patternEnd)) {
2525                         ptr = read_repeat_counts(ptr+2, &minRepeats, &maxRepeats, &errorcode);
2526                         if (errorcode != 0)
2527                             return -1;
2528                         if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) ||
2529                             (minRepeats == 1 && maxRepeats == -1))
2530                             length++;
2531                         else
2532                             length += 5;
2533                         if (ptr + 1 < patternEnd && ptr[1] == '+') {
2534                             ptr++;
2535                             length += 2 + 2 * LINK_SIZE;
2536                         } else if (ptr + 1 < patternEnd && ptr[1] == '?')
2537                             ptr++;
2538                     }
2539                 }
2540                 continue;
2541             }
2542
2543             /* Brackets may be genuine groups or special things */
2544
2545             case '(': {
2546                 int branch_newextra = 0;
2547                 int bracket_length = 1 + LINK_SIZE;
2548                 bool capturing = false;
2549
2550                 /* Handle special forms of bracket, which all start (? */
2551
2552                 if (ptr + 1 < patternEnd && ptr[1] == '?') {
2553                     switch (c = (ptr + 2 < patternEnd ? ptr[2] : 0)) {
2554                             /* Non-referencing groups and lookaheads just move the pointer on, and
2555                              then behave like a non-special bracket, except that they don't increment
2556                              the count of extracting brackets. Ditto for the "once only" bracket,
2557                              which is in Perl from version 5.005. */
2558
2559                         case ':':
2560                         case '=':
2561                         case '!':
2562                             ptr += 2;
2563                             break;
2564
2565                             /* Else loop checking valid options until ) is met. Anything else is an
2566                              error. If we are without any brackets, i.e. at top level, the settings
2567                              act as if specified in the options, so massage the options immediately.
2568                              This is for backward compatibility with Perl 5.004. */
2569
2570                         default:
2571                             errorcode = ERR12;
2572                             return -1;
2573                     }
2574                 } else
2575                     capturing = 1;
2576
2577                 /* Capturing brackets must be counted so we can process escapes in a
2578                  Perlish way. If the number exceeds EXTRACT_BASIC_MAX we are going to need
2579                  an additional 3 bytes of memory per capturing bracket. */
2580
2581                 if (capturing) {
2582                     bracount++;
2583                     if (bracount > EXTRACT_BASIC_MAX)
2584                         bracket_length += 3;
2585                 }
2586
2587                 /* Save length for computing whole length at end if there's a repeat that
2588                  requires duplication of the group. Also save the current value of
2589                  branch_extra, and start the new group with the new value. If non-zero, this
2590                  will either be 2 for a (?imsx: group, or 3 for a lookbehind assertion. */
2591
2592                 if (brastackptr >= sizeof(brastack)/sizeof(int)) {
2593                     errorcode = ERR17;
2594                     return -1;
2595                 }
2596
2597                 bralenstack[brastackptr] = branch_extra;
2598                 branch_extra = branch_newextra;
2599
2600                 brastack[brastackptr++] = length;
2601                 length += bracket_length;
2602                 continue;
2603             }
2604
2605             /* Handle ket. Look for subsequent maxRepeats/minRepeats; for certain sets of values we
2606              have to replicate this bracket up to that many times. If brastackptr is
2607              0 this is an unmatched bracket which will generate an error, but take care
2608              not to try to access brastack[-1] when computing the length and restoring
2609              the branch_extra value. */
2610
2611             case ')': {
2612                 int duplength;
2613                 length += 1 + LINK_SIZE;
2614                 if (brastackptr > 0) {
2615                     duplength = length - brastack[--brastackptr];
2616                     branch_extra = bralenstack[brastackptr];
2617                 }
2618                 else
2619                     duplength = 0;
2620
2621                 /* Leave ptr at the final char; for read_repeat_counts this happens
2622                  automatically; for the others we need an increment. */
2623
2624                 if (ptr + 1 < patternEnd && (c = ptr[1]) == '{' && is_counted_repeat(ptr+2, patternEnd)) {
2625                     ptr = read_repeat_counts(ptr+2, &minRepeats, &maxRepeats, &errorcode);
2626                     if (errorcode)
2627                         return -1;
2628                 } else if (c == '*') {
2629                     minRepeats = 0;
2630                     maxRepeats = -1;
2631                     ptr++;
2632                 } else if (c == '+') {
2633                     minRepeats = 1;
2634                     maxRepeats = -1;
2635                     ptr++;
2636                 } else if (c == '?') {
2637                     minRepeats = 0;
2638                     maxRepeats = 1;
2639                     ptr++;
2640                 } else {
2641                     minRepeats = 1;
2642                     maxRepeats = 1;
2643                 }
2644
2645                 /* If the minimum is zero, we have to allow for an OP_BRAZERO before the
2646                  group, and if the maximum is greater than zero, we have to replicate
2647                  maxval-1 times; each replication acquires an OP_BRAZERO plus a nesting
2648                  bracket set. */
2649
2650                 if (minRepeats == 0) {
2651                     length++;
2652                     if (maxRepeats > 0) length += (maxRepeats - 1) * (duplength + 3 + 2 * LINK_SIZE);
2653                 }
2654
2655                 /* When the minimum is greater than zero, we have to replicate up to
2656                  minval-1 times, with no additions required in the copies. Then, if there
2657                  is a limited maximum we have to replicate up to maxval-1 times allowing
2658                  for a BRAZERO item before each optional copy and nesting brackets for all
2659                  but one of the optional copies. */
2660
2661                 else {
2662                     length += (minRepeats - 1) * duplength;
2663                     if (maxRepeats > minRepeats)   /* Need this test as maxRepeats=-1 means no limit */
2664                         length += (maxRepeats - minRepeats) * (duplength + 3 + 2 * LINK_SIZE)
2665                         - (2 + 2 * LINK_SIZE);
2666                 }
2667
2668                 /* Allow space for once brackets for "possessive quantifier" */
2669
2670                 if (ptr + 1 < patternEnd && ptr[1] == '+') {
2671                     ptr++;
2672                     length += 2 + 2 * LINK_SIZE;
2673                 }
2674                 continue;
2675             }
2676
2677             /* Non-special character. It won't be space or # in extended mode, so it is
2678              always a genuine character. If we are in a \Q...\E sequence, check for the
2679              end; if not, we have a literal. */
2680
2681             default:
2682             NORMAL_CHAR:
2683                 length += 2;          /* For a one-byte character */
2684                 lastitemlength = 1;   /* Default length of last item for repeats */
2685
2686                 if (c > 127) {
2687                     int i;
2688                     for (i = 0; i < _pcre_utf8_table1_size; i++)
2689                         if (c <= _pcre_utf8_table1[i])
2690                             break;
2691                     length += i;
2692                     lastitemlength += i;
2693                 }
2694
2695                 continue;
2696         }
2697     }
2698
2699     length += 2 + LINK_SIZE;    /* For final KET and END */
2700     return length;
2701 }
2702
2703 #ifdef DEBUG
2704 static void printCompiledRegExp(JSRegExp* re, int length)
2705 {
2706     printf("Length = %d top_bracket = %d top_backref = %d\n",
2707            length, re->top_bracket, re->top_backref);
2708
2709     if (re->options) {
2710         printf("%s%s%s\n",
2711                ((re->options & IsAnchoredOption) != 0)? "anchored " : "",
2712                ((re->options & IgnoreCaseOption) != 0)? "ignores case " : "",
2713                ((re->options & MatchAcrossMultipleLinesOption) != 0)? "multiline " : "");
2714     }
2715
2716     if (re->options & UseFirstByteOptimizationOption) {
2717         char ch = re->first_byte & 255;
2718         const char* caseless = (re->first_byte & REQ_IGNORE_CASE) ? " (ignores case)" : "";
2719         if (isASCIIAlphanumeric(ch))
2720             printf("First char = %c%s\n", ch, caseless);
2721         else
2722             printf("First char = \\x%02x%s\n", ch, caseless);
2723     }
2724
2725     if (re->options & UseRequiredByteOptimizationOption) {
2726         char ch = re->req_byte & 255;
2727         const char* caseless = (re->req_byte & REQ_IGNORE_CASE) ? " (ignores case)" : "";
2728         if (isASCIIAlphanumeric(ch))
2729             printf("Req char = %c%s\n", ch, caseless);
2730         else
2731             printf("Req char = \\x%02x%s\n", ch, caseless);
2732     }
2733
2734     // This debugging function has been removed from JavaScriptCore's PCRE
2735     //pcre_printint(re, stdout);
2736 }
2737 #endif
2738
2739 /*************************************************
2740 *        Compile a Regular Expression            *
2741 *************************************************/
2742
2743 /* This function takes a string and returns a pointer to a block of store
2744 holding a compiled version of the expression. The original API for this
2745 function had no error code return variable; it is retained for backwards
2746 compatibility. The new function is given a new name.
2747
2748 Arguments:
2749   pattern       the regular expression
2750   options       various option bits
2751   errorcodeptr  pointer to error code variable (pcre_compile2() only)
2752                   can be NULL if you don't want a code value
2753   errorptr      pointer to pointer to error text
2754   erroroffset   ptr offset in pattern where error was detected
2755   tables        pointer to character tables or NULL
2756
2757 Returns:        pointer to compiled data block, or NULL on error,
2758                 with errorptr and erroroffset set
2759 */
2760
2761 static JSRegExp* returnError(ErrorCode errorcode, const char** errorptr)
2762 {
2763     *errorptr = error_text(errorcode);
2764     return 0;
2765 }
2766
2767 JSRegExp* jsRegExpCompile(const UChar* pattern, int patternLength,
2768                 JSRegExpIgnoreCaseOption ignoreCase, JSRegExpMultilineOption multiline,
2769                 unsigned* numSubpatterns, const char** errorptr)
2770 {
2771     /* We can't pass back an error message if errorptr is NULL; I guess the best we
2772      can do is just return NULL, but we can set a code value if there is a code pointer. */
2773     if (!errorptr)
2774         return 0;
2775     *errorptr = NULL;
2776
2777     CompileData compile_block;
2778
2779     ErrorCode errorcode = ERR0;
2780     int length = calculateCompiledPatternLengthAndFlags(pattern, patternLength, ignoreCase, compile_block, errorcode);
2781     if (errorcode)
2782         return returnError(errorcode, errorptr);
2783
2784     if (length > MAX_PATTERN_SIZE)
2785         return returnError(ERR16, errorptr);
2786
2787     size_t size = length + sizeof(JSRegExp);
2788     JSRegExp* re = reinterpret_cast<JSRegExp*>(new char[size]);
2789
2790     if (!re)
2791         return returnError(ERR13, errorptr);
2792
2793     /* Put in the magic number, and save the sizes, options, and character table
2794      pointer. NULL is used for the default character tables. The nullpad field is at
2795      the end; it's there to help in the case when a regex compiled on a system with
2796      4-byte pointers is run on another with 8-byte pointers. */
2797
2798     re->size = (pcre_uint32)size;
2799     re->options = (ignoreCase ? IgnoreCaseOption : 0) | (multiline ? MatchAcrossMultipleLinesOption : 0);
2800
2801     /* The starting points of the name/number translation table and of the code are
2802      passed around in the compile data block. */
2803
2804     const uschar* codestart = (const uschar*)(re + 1);
2805     compile_block.start_code = codestart;
2806     compile_block.start_pattern = (const UChar*)pattern;
2807
2808     /* Set up a starting, non-extracting bracket, then compile the expression. On
2809      error, errorcode will be set non-zero, so we don't need to look at the result
2810      of the function here. */
2811
2812     const UChar* ptr = (const UChar*)pattern;
2813     const UChar* patternEnd = pattern + patternLength;
2814     uschar* code = (uschar*)codestart;
2815     *code = OP_BRA;
2816     int firstbyte, reqbyte;
2817     int bracketCount = 0;
2818     (void)compile_regex(re->options, &bracketCount, &code, &ptr,
2819                         patternEnd,
2820                         &errorcode, 0, &firstbyte, &reqbyte, compile_block);
2821     re->top_bracket = bracketCount;
2822     re->top_backref = compile_block.top_backref;
2823
2824     /* If not reached end of pattern on success, there's an excess bracket. */
2825
2826     if (errorcode == 0 && ptr < patternEnd)
2827         errorcode = ERR10;
2828
2829     /* Fill in the terminating state and check for disastrous overflow, but
2830      if debugging, leave the test till after things are printed out. */
2831
2832     *code++ = OP_END;
2833
2834 #ifndef DEBUG
2835     if (code - codestart > length)
2836         errorcode = ERR7;
2837 #endif
2838
2839     /* Give an error if there's back reference to a non-existent capturing
2840      subpattern. */
2841
2842     if (re->top_backref > re->top_bracket)
2843         errorcode = ERR15;