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