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