2007-11-30 Eric Seidel <eric@webkit.org>
[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                     return -1;
874
875                 if (ptr[1] == '^') {
876                     negate_class = true;
877                     ++ptr;
878                 } else
879                     negate_class = false;
880                 
881                 /* Keep a count of chars with values < 256 so that we can optimize the case
882                  of just a single character (as long as it's < 256). For higher valued UTF-8
883                  characters, we don't yet do any optimization. */
884                 
885                 class_charcount = 0;
886                 class_lastchar = -1;
887                 
888                 class_utf8 = false;                       /* No chars >= 256 */
889                 class_utf8data = code + LINK_SIZE + 34;   /* For UTF-8 items */
890                 
891                 /* Initialize the 32-char bit map to all zeros. We have to build the
892                  map in a temporary bit of store, in case the class contains only 1
893                  character (< 256), because in that case the compiled code doesn't use the
894                  bit map. */
895                 
896                 memset(classbits, 0, 32 * sizeof(uschar));
897                 
898                 /* Process characters until ] is reached. The first pass
899                  through the regex checked the overall syntax, so we don't need to be very
900                  strict here. At the start of the loop, c contains the first byte of the
901                  character. */
902
903                 while ((++ptr < patternEnd) && (c = *ptr) != ']') {
904                     /* Backslash may introduce a single character, or it may introduce one
905                      of the specials, which just set a flag. Escaped items are checked for
906                      validity in the pre-compiling pass. The sequence \b is a special case.
907                      Inside a class (and only there) it is treated as backspace. Elsewhere
908                      it marks a word boundary. Other escapes have preset maps ready to
909                      or into the one we are building. We assume they have more than one
910                      character in them, so set class_charcount bigger than one. */
911                     
912                     if (c == '\\') {
913                         c = check_escape(&ptr, patternEnd, errorcodeptr, *brackets, true);
914                         
915                         if (-c == ESC_b)
916                             c = '\b';       /* \b is backslash in a class */
917                         
918                         if (c < 0) {
919                             class_charcount += 2;     /* Greater than 1 is what matters */
920                             switch (-c) {
921                                 case ESC_d:
922                                     for (c = 0; c < 32; c++)
923                                         classbits[c] |= classBitmapForChar(c + cbit_digit);
924                                     continue;
925                                     
926                                 case ESC_D:
927                                     should_flip_negation = true;
928                                     for (c = 0; c < 32; c++)
929                                         classbits[c] |= ~classBitmapForChar(c + cbit_digit);
930                                     continue;
931                                     
932                                 case ESC_w:
933                                     for (c = 0; c < 32; c++)
934                                         classbits[c] |= classBitmapForChar(c + cbit_word);
935                                     continue;
936                                     
937                                 case ESC_W:
938                                     should_flip_negation = true;
939                                     for (c = 0; c < 32; c++)
940                                         classbits[c] |= ~classBitmapForChar(c + cbit_word);
941                                     continue;
942                                     
943                                 case ESC_s:
944                                     for (c = 0; c < 32; c++)
945                                          classbits[c] |= classBitmapForChar(c + cbit_space);
946                                     continue;
947                                     
948                                 case ESC_S:
949                                     should_flip_negation = true;
950                                     for (c = 0; c < 32; c++)
951                                          classbits[c] |= ~classBitmapForChar(c + cbit_space);
952                                     continue;
953                                     
954                                     /* Unrecognized escapes are faulted if PCRE is running in its
955                                      strict mode. By default, for compatibility with Perl, they are
956                                      treated as literals. */
957                                     
958                                 default:
959                                     c = *ptr;              /* The final character */
960                                     class_charcount -= 2;  /* Undo the default count from above */
961                             }
962                         }
963                         
964                         /* Fall through if we have a single character (c >= 0). This may be
965                          > 256 in UTF-8 mode. */
966                         
967                     }   /* End of backslash handling */
968                     
969                     /* A single character may be followed by '-' to form a range. However,
970                      Perl does not permit ']' to be the end of the range. A '-' character
971                      here is treated as a literal. */
972                     
973                     if ((ptr + 2 < patternEnd) && ptr[1] == '-' && ptr[2] != ']') {
974                         ptr += 2;
975                         
976                         int d = *ptr;
977                         
978                         /* The second part of a range can be a single-character escape, but
979                          not any of the other escapes. Perl 5.6 treats a hyphen as a literal
980                          in such circumstances. */
981                         
982                         if (d == '\\') {
983                             const UChar* oldptr = ptr;
984                             d = check_escape(&ptr, patternEnd, errorcodeptr, *brackets, true);
985                             
986                             /* \b is backslash; \X is literal X; any other special means the '-'
987                              was literal */
988                             
989                             if (d < 0) {
990                                 if (d == -ESC_b)
991                                     d = '\b';
992                                 else {
993                                     ptr = oldptr - 2;
994                                     goto LONE_SINGLE_CHARACTER;  /* A few lines below */
995                                 }
996                             }
997                         }
998                         
999                         /* The check that the two values are in the correct order happens in
1000                          the pre-pass. Optimize one-character ranges */
1001                         
1002                         if (d == c)
1003                             goto LONE_SINGLE_CHARACTER;  /* A few lines below */
1004                         
1005                         /* In UTF-8 mode, if the upper limit is > 255, or > 127 for caseless
1006                          matching, we have to use an XCLASS with extra data items. Caseless
1007                          matching for characters > 127 is available only if UCP support is
1008                          available. */
1009                         
1010                         if ((d > 255 || ((options & IgnoreCaseOption) && d > 127))) {
1011                             class_utf8 = true;
1012                             
1013                             /* With UCP support, we can find the other case equivalents of
1014                              the relevant characters. There may be several ranges. Optimize how
1015                              they fit with the basic range. */
1016                             
1017                             if (options & IgnoreCaseOption) {
1018                                 int occ, ocd;
1019                                 int cc = c;
1020                                 int origd = d;
1021                                 while (get_othercase_range(&cc, origd, &occ, &ocd)) {
1022                                     if (occ >= c && ocd <= d)
1023                                         continue;  /* Skip embedded ranges */
1024                                     
1025                                     if (occ < c  && ocd >= c - 1)        /* Extend the basic range */
1026                                     {                                  /* if there is overlap,   */
1027                                         c = occ;                           /* noting that if occ < c */
1028                                         continue;                          /* we can't have ocd > d  */
1029                                     }                                  /* because a subrange is  */
1030                                     if (ocd > d && occ <= d + 1)         /* always shorter than    */
1031                                     {                                  /* the basic range.       */
1032                                         d = ocd;
1033                                         continue;
1034                                     }
1035                                     
1036                                     if (occ == ocd)
1037                                         *class_utf8data++ = XCL_SINGLE;
1038                                     else {
1039                                         *class_utf8data++ = XCL_RANGE;
1040                                         class_utf8data += _pcre_ord2utf8(occ, class_utf8data);
1041                                     }
1042                                     class_utf8data += _pcre_ord2utf8(ocd, class_utf8data);
1043                                 }
1044                             }
1045                             
1046                             /* Now record the original range, possibly modified for UCP caseless
1047                              overlapping ranges. */
1048                             
1049                             *class_utf8data++ = XCL_RANGE;
1050                             class_utf8data += _pcre_ord2utf8(c, class_utf8data);
1051                             class_utf8data += _pcre_ord2utf8(d, class_utf8data);
1052                             
1053                             /* With UCP support, we are done. Without UCP support, there is no
1054                              caseless matching for UTF-8 characters > 127; we can use the bit map
1055                              for the smaller ones. */
1056                             
1057                             continue;    /* With next character in the class */
1058                         }
1059                         
1060                         /* We use the bit map for all cases when not in UTF-8 mode; else
1061                          ranges that lie entirely within 0-127 when there is UCP support; else
1062                          for partial ranges without UCP support. */
1063                         
1064                         for (; c <= d; c++) {
1065                             classbits[c/8] |= (1 << (c&7));
1066                             if (options & IgnoreCaseOption) {
1067                                 int uc = flipCase(c);
1068                                 classbits[uc/8] |= (1 << (uc&7));
1069                             }
1070                             class_charcount++;                /* in case a one-char range */
1071                             class_lastchar = c;
1072                         }
1073                         
1074                         continue;   /* Go get the next char in the class */
1075                     }
1076                     
1077                     /* Handle a lone single character - we can get here for a normal
1078                      non-escape char, or after \ that introduces a single character or for an
1079                      apparent range that isn't. */
1080                     
1081                 LONE_SINGLE_CHARACTER:
1082                     
1083                     /* Handle a character that cannot go in the bit map */
1084                     
1085                     if ((c > 255 || ((options & IgnoreCaseOption) && c > 127))) {
1086                         class_utf8 = true;
1087                         *class_utf8data++ = XCL_SINGLE;
1088                         class_utf8data += _pcre_ord2utf8(c, class_utf8data);
1089                         
1090                         if (options & IgnoreCaseOption) {
1091                             int othercase;
1092                             if ((othercase = _pcre_ucp_othercase(c)) >= 0) {
1093                                 *class_utf8data++ = XCL_SINGLE;
1094                                 class_utf8data += _pcre_ord2utf8(othercase, class_utf8data);
1095                             }
1096                         }
1097                     } else {
1098                         /* Handle a single-byte character */
1099                         classbits[c/8] |= (1 << (c&7));
1100                         if (options & IgnoreCaseOption) {
1101                             c = flipCase(c);
1102                             classbits[c/8] |= (1 << (c&7));
1103                         }
1104                         class_charcount++;
1105                         class_lastchar = c;
1106                     }
1107                 }
1108                 
1109                 /* If class_charcount is 1, we saw precisely one character whose value is
1110                  less than 256. In non-UTF-8 mode we can always optimize. In UTF-8 mode, we
1111                  can optimize the negative case only if there were no characters >= 128
1112                  because OP_NOT and the related opcodes like OP_NOTSTAR operate on
1113                  single-bytes only. This is an historical hangover. Maybe one day we can
1114                  tidy these opcodes to handle multi-byte characters.
1115                  
1116                  The optimization throws away the bit map. We turn the item into a
1117                  1-character OP_CHAR[NC] if it's positive, or OP_NOT if it's negative. Note
1118                  that OP_NOT does not support multibyte characters. In the positive case, it
1119                  can cause firstbyte to be set. Otherwise, there can be no first char if
1120                  this item is first, whatever repeat count may follow. In the case of
1121                  reqbyte, save the previous value for reinstating. */
1122                 
1123                 if (class_charcount == 1 && (!class_utf8 && (!negate_class || class_lastchar < 128))) {
1124                     zeroreqbyte = reqbyte;
1125                     
1126                     /* The OP_NOT opcode works on one-byte characters only. */
1127                     
1128                     if (negate_class) {
1129                         if (firstbyte == REQ_UNSET)
1130                             firstbyte = REQ_NONE;
1131                         zerofirstbyte = firstbyte;
1132                         *code++ = OP_NOT;
1133                         *code++ = class_lastchar;
1134                         break;
1135                     }
1136                     
1137                     /* For a single, positive character, get the value into c, and
1138                      then we can handle this with the normal one-character code. */
1139                     
1140                     c = class_lastchar;
1141                     goto NORMAL_CHAR;
1142                 }       /* End of 1-char optimization */
1143                 
1144                 /* The general case - not the one-char optimization. If this is the first
1145                  thing in the branch, there can be no first char setting, whatever the
1146                  repeat count. Any reqbyte setting must remain unchanged after any kind of
1147                  repeat. */
1148                 
1149                 if (firstbyte == REQ_UNSET) firstbyte = REQ_NONE;
1150                 zerofirstbyte = firstbyte;
1151                 zeroreqbyte = reqbyte;
1152                 
1153                 /* If there are characters with values > 255, we have to compile an
1154                  extended class, with its own opcode. If there are no characters < 256,
1155                  we can omit the bitmap. */
1156                 
1157                 if (class_utf8 && !should_flip_negation) {
1158                     *class_utf8data++ = XCL_END;    /* Marks the end of extra data */
1159                     *code++ = OP_XCLASS;
1160                     code += LINK_SIZE;
1161                     *code = negate_class? XCL_NOT : 0;
1162                     
1163                     /* If the map is required, install it, and move on to the end of
1164                      the extra data */
1165                     
1166                     if (class_charcount > 0) {
1167                         *code++ |= XCL_MAP;
1168                         memcpy(code, classbits, 32);
1169                         code = class_utf8data;
1170                     }
1171                     
1172                     /* If the map is not required, slide down the extra data. */
1173                     
1174                     else {
1175                         int len = class_utf8data - (code + 33);
1176                         memmove(code + 1, code + 33, len);
1177                         code += len + 1;
1178                     }
1179                     
1180                     /* Now fill in the complete length of the item */
1181                     
1182                     putOpcodeValueAtOffset(previous, 1, code - previous);
1183                     break;   /* End of class handling */
1184                 }
1185                 
1186                 /* If there are no characters > 255, negate the 32-byte map if necessary,
1187                  and copy it into the code vector. If this is the first thing in the branch,
1188                  there can be no first char setting, whatever the repeat count. Any reqbyte
1189                  setting must remain unchanged after any kind of repeat. */
1190                 
1191                 *code++ = (negate_class == should_flip_negation) ? OP_CLASS : OP_NCLASS;
1192                 if (negate_class)
1193                     for (c = 0; c < 32; c++)
1194                         code[c] = ~classbits[c];
1195                 else
1196                     memcpy(code, classbits, 32);
1197                 code += 32;
1198                 break;
1199             }
1200                 
1201             /* Various kinds of repeat; '{' is not necessarily a quantifier, but this
1202              has been tested above. */
1203
1204             case '{':
1205                 if (!is_quantifier)
1206                     goto NORMAL_CHAR;
1207                 ptr = read_repeat_counts(ptr+1, &repeat_min, &repeat_max, errorcodeptr);
1208                 if (*errorcodeptr)
1209                     goto FAILED;
1210                 goto REPEAT;
1211                 
1212             case '*':
1213                 repeat_min = 0;
1214                 repeat_max = -1;
1215                 goto REPEAT;
1216                 
1217             case '+':
1218                 repeat_min = 1;
1219                 repeat_max = -1;
1220                 goto REPEAT;
1221                 
1222             case '?':
1223                 repeat_min = 0;
1224                 repeat_max = 1;
1225                 
1226             REPEAT:
1227                 if (!previous) {
1228                     *errorcodeptr = ERR9;
1229                     goto FAILED;
1230                 }
1231                 
1232                 if (repeat_min == 0) {
1233                     firstbyte = zerofirstbyte;    /* Adjust for zero repeat */
1234                     reqbyte = zeroreqbyte;        /* Ditto */
1235                 }
1236                 
1237                 /* Remember whether this is a variable length repeat */
1238                 
1239                 reqvary = (repeat_min == repeat_max)? 0 : REQ_VARY;
1240                 
1241                 op_type = 0;                    /* Default single-char op codes */
1242                 
1243                 /* Save start of previous item, in case we have to move it up to make space
1244                  for an inserted OP_ONCE for the additional '+' extension. */
1245                 
1246                 tempcode = previous;
1247                 
1248                 /* If the next character is '+', we have a possessive quantifier. This
1249                  implies greediness, whatever the setting of the PCRE_UNGREEDY option.
1250                  If the next character is '?' this is a minimizing repeat, by default,
1251                  but if PCRE_UNGREEDY is set, it works the other way round. We change the
1252                  repeat type to the non-default. */
1253                 
1254                 if (safelyCheckNextChar(ptr, patternEnd, '?')) {
1255                     repeat_type = 1;
1256                     ptr++;
1257                 } else
1258                     repeat_type = 0;
1259                 
1260                 /* If previous was a character match, abolish the item and generate a
1261                  repeat item instead. If a char item has a minumum of more than one, ensure
1262                  that it is set in reqbyte - it might not be if a sequence such as x{3} is
1263                  the first thing in a branch because the x will have gone into firstbyte
1264                  instead.  */
1265                 
1266                 if (*previous == OP_CHAR || *previous == OP_CHAR_IGNORING_CASE) {
1267                     /* Deal with UTF-8 characters that take up more than one byte. It's
1268                      easier to write this out separately than try to macrify it. Use c to
1269                      hold the length of the character in bytes, plus 0x80 to flag that it's a
1270                      length rather than a small character. */
1271                     
1272                     if (code[-1] & 0x80) {
1273                         uschar *lastchar = code - 1;
1274                         while((*lastchar & 0xc0) == 0x80)
1275                             lastchar--;
1276                         c = code - lastchar;            /* Length of UTF-8 character */
1277                         memcpy(utf8_char, lastchar, c); /* Save the char */
1278                         c |= 0x80;                      /* Flag c as a length */
1279                     }
1280                     else {
1281                         c = code[-1];
1282                         if (repeat_min > 1)
1283                             reqbyte = c | req_caseopt | cd.req_varyopt;
1284                     }
1285                     
1286                     goto OUTPUT_SINGLE_REPEAT;   /* Code shared with single character types */
1287                 }
1288                 
1289                 else if (*previous == OP_ASCII_CHAR || *previous == OP_ASCII_LETTER_IGNORING_CASE) {
1290                     c = previous[1];
1291                     if (repeat_min > 1)
1292                         reqbyte = c | req_caseopt | cd.req_varyopt;
1293                     goto OUTPUT_SINGLE_REPEAT;
1294                 }
1295                 
1296                 /* If previous was a single negated character ([^a] or similar), we use
1297                  one of the special opcodes, replacing it. The code is shared with single-
1298                  character repeats by setting opt_type to add a suitable offset into
1299                  repeat_type. OP_NOT is currently used only for single-byte chars. */
1300                 
1301                 else if (*previous == OP_NOT) {
1302                     op_type = OP_NOTSTAR - OP_STAR;  /* Use "not" opcodes */
1303                     c = previous[1];
1304                     goto OUTPUT_SINGLE_REPEAT;
1305                 }
1306                 
1307                 /* If previous was a character type match (\d or similar), abolish it and
1308                  create a suitable repeat item. The code is shared with single-character
1309                  repeats by setting op_type to add a suitable offset into repeat_type. */
1310                 
1311                 else if (*previous <= OP_NOT_NEWLINE) {
1312                     op_type = OP_TYPESTAR - OP_STAR;  /* Use type opcodes */
1313                     c = *previous;
1314                     
1315                 OUTPUT_SINGLE_REPEAT:
1316                     int prop_type = -1;
1317                     int prop_value = -1;
1318                     
1319                     uschar* oldcode = code;
1320                     code = previous;                  /* Usually overwrite previous item */
1321                     
1322                     /* If the maximum is zero then the minimum must also be zero; Perl allows
1323                      this case, so we do too - by simply omitting the item altogether. */
1324                     
1325                     if (repeat_max == 0)
1326                         goto END_REPEAT;
1327                     
1328                     /* Combine the op_type with the repeat_type */
1329                     
1330                     repeat_type += op_type;
1331                     
1332                     /* A minimum of zero is handled either as the special case * or ?, or as
1333                      an UPTO, with the maximum given. */
1334                     
1335                     if (repeat_min == 0) {
1336                         if (repeat_max == -1)
1337                             *code++ = OP_STAR + repeat_type;
1338                         else if (repeat_max == 1)
1339                             *code++ = OP_QUERY + repeat_type;
1340                         else {
1341                             *code++ = OP_UPTO + repeat_type;
1342                             put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max);
1343                         }
1344                     }
1345                     
1346                     /* A repeat minimum of 1 is optimized into some special cases. If the
1347                      maximum is unlimited, we use OP_PLUS. Otherwise, the original item it
1348                      left in place and, if the maximum is greater than 1, we use OP_UPTO with
1349                      one less than the maximum. */
1350                     
1351                     else if (repeat_min == 1) {
1352                         if (repeat_max == -1)
1353                             *code++ = OP_PLUS + repeat_type;
1354                         else {
1355                             code = oldcode;                 /* leave previous item in place */
1356                             if (repeat_max == 1)
1357                                 goto END_REPEAT;
1358                             *code++ = OP_UPTO + repeat_type;
1359                             put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max - 1);
1360                         }
1361                     }
1362                     
1363                     /* The case {n,n} is just an EXACT, while the general case {n,m} is
1364                      handled as an EXACT followed by an UPTO. */
1365                     
1366                     else {
1367                         *code++ = OP_EXACT + op_type;  /* NB EXACT doesn't have repeat_type */
1368                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_min);
1369                         
1370                         /* If the maximum is unlimited, insert an OP_STAR. Before doing so,
1371                          we have to insert the character for the previous code. For a repeated
1372                          Unicode property match, there are two extra bytes that define the
1373                          required property. In UTF-8 mode, long characters have their length in
1374                          c, with the 0x80 bit as a flag. */
1375                         
1376                         if (repeat_max < 0) {
1377                             if (c >= 128) {
1378                                 memcpy(code, utf8_char, c & 7);
1379                                 code += c & 7;
1380                             } else {
1381                                 *code++ = c;
1382                                 if (prop_type >= 0) {
1383                                     *code++ = prop_type;
1384                                     *code++ = prop_value;
1385                                 }
1386                             }
1387                             *code++ = OP_STAR + repeat_type;
1388                         }
1389                         
1390                         /* Else insert an UPTO if the max is greater than the min, again
1391                          preceded by the character, for the previously inserted code. */
1392                         
1393                         else if (repeat_max != repeat_min) {
1394                             if (c >= 128) {
1395                                 memcpy(code, utf8_char, c & 7);
1396                                 code += c & 7;
1397                             } else
1398                                 *code++ = c;
1399                             if (prop_type >= 0) {
1400                                 *code++ = prop_type;
1401                                 *code++ = prop_value;
1402                             }
1403                             repeat_max -= repeat_min;
1404                             *code++ = OP_UPTO + repeat_type;
1405                             put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max);
1406                         }
1407                     }
1408                     
1409                     /* The character or character type itself comes last in all cases. */
1410                     
1411                     if (c >= 128) {
1412                         memcpy(code, utf8_char, c & 7);
1413                         code += c & 7;
1414                     } else
1415                         *code++ = c;
1416                     
1417                     /* For a repeated Unicode property match, there are two extra bytes that
1418                      define the required property. */
1419                     
1420                     if (prop_type >= 0) {
1421                         *code++ = prop_type;
1422                         *code++ = prop_value;
1423                     }
1424                 }
1425                 
1426                 /* If previous was a character class or a back reference, we put the repeat
1427                  stuff after it, but just skip the item if the repeat was {0,0}. */
1428                 
1429                 else if (*previous == OP_CLASS ||
1430                          *previous == OP_NCLASS ||
1431                          *previous == OP_XCLASS ||
1432                          *previous == OP_REF)
1433                 {
1434                     if (repeat_max == 0) {
1435                         code = previous;
1436                         goto END_REPEAT;
1437                     }
1438                     
1439                     if (repeat_min == 0 && repeat_max == -1)
1440                         *code++ = OP_CRSTAR + repeat_type;
1441                     else if (repeat_min == 1 && repeat_max == -1)
1442                         *code++ = OP_CRPLUS + repeat_type;
1443                     else if (repeat_min == 0 && repeat_max == 1)
1444                         *code++ = OP_CRQUERY + repeat_type;
1445                     else {
1446                         *code++ = OP_CRRANGE + repeat_type;
1447                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_min);
1448                         if (repeat_max == -1)
1449                             repeat_max = 0;  /* 2-byte encoding for max */
1450                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, repeat_max);
1451                     }
1452                 }
1453                 
1454                 /* If previous was a bracket group, we may have to replicate it in certain
1455                  cases. */
1456                 
1457                 else if (*previous >= OP_BRA || *previous == OP_ONCE) {
1458                     int ketoffset = 0;
1459                     int len = code - previous;
1460                     uschar* bralink = NULL;
1461                     
1462                     /* If the maximum repeat count is unlimited, find the end of the bracket
1463                      by scanning through from the start, and compute the offset back to it
1464                      from the current code pointer. There may be an OP_OPT setting following
1465                      the final KET, so we can't find the end just by going back from the code
1466                      pointer. */
1467                     
1468                     if (repeat_max == -1) {
1469                         uschar* ket = previous;
1470                         do {
1471                             ket += getOpcodeValueAtOffset(ket, 1);
1472                         } while (*ket != OP_KET);
1473                         ketoffset = code - ket;
1474                     }
1475                     
1476                     /* The case of a zero minimum is special because of the need to stick
1477                      OP_BRAZERO in front of it, and because the group appears once in the
1478                      data, whereas in other cases it appears the minimum number of times. For
1479                      this reason, it is simplest to treat this case separately, as otherwise
1480                      the code gets far too messy. There are several special subcases when the
1481                      minimum is zero. */
1482                     
1483                     if (repeat_min == 0) {
1484                         /* If the maximum is also zero, we just omit the group from the output
1485                          altogether. */
1486                         
1487                         if (repeat_max == 0) {
1488                             code = previous;
1489                             goto END_REPEAT;
1490                         }
1491                         
1492                         /* If the maximum is 1 or unlimited, we just have to stick in the
1493                          BRAZERO and do no more at this point. However, we do need to adjust
1494                          any OP_RECURSE calls inside the group that refer to the group itself or
1495                          any internal group, because the offset is from the start of the whole
1496                          regex. Temporarily terminate the pattern while doing this. */
1497                         
1498                         if (repeat_max <= 1) {
1499                             *code = OP_END;
1500                             memmove(previous+1, previous, len);
1501                             code++;
1502                             *previous++ = OP_BRAZERO + repeat_type;
1503                         }
1504                         
1505                         /* If the maximum is greater than 1 and limited, we have to replicate
1506                          in a nested fashion, sticking OP_BRAZERO before each set of brackets.
1507                          The first one has to be handled carefully because it's the original
1508                          copy, which has to be moved up. The remainder can be handled by code
1509                          that is common with the non-zero minimum case below. We have to
1510                          adjust the value or repeat_max, since one less copy is required. Once
1511                          again, we may have to adjust any OP_RECURSE calls inside the group. */
1512                         
1513                         else {
1514                             *code = OP_END;
1515                             memmove(previous + 2 + LINK_SIZE, previous, len);
1516                             code += 2 + LINK_SIZE;
1517                             *previous++ = OP_BRAZERO + repeat_type;
1518                             *previous++ = OP_BRA;
1519                             
1520                             /* We chain together the bracket offset fields that have to be
1521                              filled in later when the ends of the brackets are reached. */
1522                             
1523                             int offset = (!bralink) ? 0 : previous - bralink;
1524                             bralink = previous;
1525                             putOpcodeValueAtOffsetAndAdvance(previous, 0, offset);
1526                         }
1527                         
1528                         repeat_max--;
1529                     }
1530                     
1531                     /* If the minimum is greater than zero, replicate the group as many
1532                      times as necessary, and adjust the maximum to the number of subsequent
1533                      copies that we need. If we set a first char from the group, and didn't
1534                      set a required char, copy the latter from the former. */
1535                     
1536                     else {
1537                         if (repeat_min > 1) {
1538                             if (groupsetfirstbyte && reqbyte < 0)
1539                                 reqbyte = firstbyte;
1540                             for (int i = 1; i < repeat_min; i++) {
1541                                 memcpy(code, previous, len);
1542                                 code += len;
1543                             }
1544                         }
1545                         if (repeat_max > 0)
1546                             repeat_max -= repeat_min;
1547                     }
1548                     
1549                     /* This code is common to both the zero and non-zero minimum cases. If
1550                      the maximum is limited, it replicates the group in a nested fashion,
1551                      remembering the bracket starts on a stack. In the case of a zero minimum,
1552                      the first one was set up above. In all cases the repeat_max now specifies
1553                      the number of additional copies needed. */
1554                     
1555                     if (repeat_max >= 0) {
1556                         for (int i = repeat_max - 1; i >= 0; i--) {
1557                             *code++ = OP_BRAZERO + repeat_type;
1558                             
1559                             /* All but the final copy start a new nesting, maintaining the
1560                              chain of brackets outstanding. */
1561                             
1562                             if (i != 0) {
1563                                 *code++ = OP_BRA;
1564                                 int offset = (!bralink) ? 0 : code - bralink;
1565                                 bralink = code;
1566                                 putOpcodeValueAtOffsetAndAdvance(code, 0, offset);
1567                             }
1568                             
1569                             memcpy(code, previous, len);
1570                             code += len;
1571                         }
1572                         
1573                         /* Now chain through the pending brackets, and fill in their length
1574                          fields (which are holding the chain links pro tem). */
1575                         
1576                         while (bralink) {
1577                             int offset = code - bralink + 1;
1578                             uschar* bra = code - offset;
1579                             int oldlinkoffset = getOpcodeValueAtOffset(bra, 1);
1580                             bralink = oldlinkoffset ? 0 : bralink - oldlinkoffset;
1581                             *code++ = OP_KET;
1582                             putOpcodeValueAtOffsetAndAdvance(code, 0, offset);
1583                             putOpcodeValueAtOffset(bra, 1, offset);
1584                         }
1585                     }
1586                     
1587                     /* If the maximum is unlimited, set a repeater in the final copy. We
1588                      can't just offset backwards from the current code point, because we
1589                      don't know if there's been an options resetting after the ket. The
1590                      correct offset was computed above. */
1591                     
1592                     else
1593                         code[-ketoffset] = OP_KETRMAX + repeat_type;
1594                 }
1595                 
1596                 /* Else there's some kind of shambles */
1597                 
1598                 else {
1599                     *errorcodeptr = ERR11;
1600                     goto FAILED;
1601                 }
1602                 
1603                 /* In all case we no longer have a previous item. We also set the
1604                  "follows varying string" flag for subsequently encountered reqbytes if
1605                  it isn't already set and we have just passed a varying length item. */
1606                 
1607             END_REPEAT:
1608                 previous = NULL;
1609                 cd.req_varyopt |= reqvary;
1610                 break;
1611                 
1612             /* Start of nested bracket sub-expression, or comment or lookahead or
1613              lookbehind or option setting or condition. First deal with special things
1614              that can come after a bracket; all are introduced by ?, and the appearance
1615              of any of them means that this is not a referencing group. They were
1616              checked for validity in the first pass over the string, so we don't have to
1617              check for syntax errors here.  */
1618                 
1619             case '(':
1620                 skipbytes = 0;
1621                 
1622                 if (*(++ptr) == '?') {
1623                     switch (*(++ptr)) {
1624                     case ':':                 /* Non-extracting bracket */
1625                         bravalue = OP_BRA;
1626                         ptr++;
1627                         break;
1628                         
1629                     case '=':                 /* Positive lookahead */
1630                         bravalue = OP_ASSERT;
1631                         ptr++;
1632                         break;
1633                         
1634                     case '!':                 /* Negative lookahead */
1635                         bravalue = OP_ASSERT_NOT;
1636                         ptr++;
1637                         break;
1638                         
1639                         /* Character after (? not specially recognized */
1640                         
1641                     default:                  /* Option setting */
1642                         *errorcodeptr = ERR12;
1643                         goto FAILED;
1644                     }
1645                 }
1646                 
1647                 /* Else we have a referencing group; adjust the opcode. If the bracket
1648                  number is greater than EXTRACT_BASIC_MAX, we set the opcode one higher, and
1649                  arrange for the true number to follow later, in an OP_BRANUMBER item. */
1650                 
1651                 else {
1652                     if (++(*brackets) > EXTRACT_BASIC_MAX) {
1653                         bravalue = OP_BRA + EXTRACT_BASIC_MAX + 1;
1654                         code[1 + LINK_SIZE] = OP_BRANUMBER;
1655                         put2ByteOpcodeValueAtOffset(code, 2+LINK_SIZE, *brackets);
1656                         skipbytes = 3;
1657                     }
1658                     else
1659                         bravalue = OP_BRA + *brackets;
1660                 }
1661                 
1662                 /* Process nested bracketed re. Assertions may not be repeated, but other
1663                  kinds can be. We copy code into a non-variable in order to be able
1664                  to pass its address because some compilers complain otherwise. Pass in a
1665                  new setting for the ims options if they have changed. */
1666                 
1667                 previous = (bravalue >= OP_ONCE) ? code : 0;
1668                 *code = bravalue;
1669                 tempcode = code;
1670                 tempreqvary = cd.req_varyopt;     /* Save value before bracket */
1671                 
1672                 if (!compile_regex(
1673                                    options,
1674                                    brackets,                     /* Extracting bracket count */
1675                                    &tempcode,                    /* Where to put code (updated) */
1676                                    &ptr,                         /* Input pointer (updated) */
1677                                    patternEnd,
1678                                    errorcodeptr,                 /* Where to put an error message */
1679                                    skipbytes,                    /* Skip over OP_BRANUMBER */
1680                                    &subfirstbyte,                /* For possible first char */
1681                                    &subreqbyte,                  /* For possible last char */
1682                                    cd))                          /* Tables block */
1683                     goto FAILED;
1684                 
1685                 /* At the end of compiling, code is still pointing to the start of the
1686                  group, while tempcode has been updated to point past the end of the group
1687                  and any option resetting that may follow it. The pattern pointer (ptr)
1688                  is on the bracket. */
1689                 
1690                 /* Handle updating of the required and first characters. Update for normal
1691                  brackets of all kinds, and conditions with two branches (see code above).
1692                  If the bracket is followed by a quantifier with zero repeat, we have to
1693                  back off. Hence the definition of zeroreqbyte and zerofirstbyte outside the
1694                  main loop so that they can be accessed for the back off. */
1695                 
1696                 zeroreqbyte = reqbyte;
1697                 zerofirstbyte = firstbyte;
1698                 groupsetfirstbyte = false;
1699                 
1700                 if (bravalue >= OP_BRA || bravalue == OP_ONCE) {
1701                     /* If we have not yet set a firstbyte in this branch, take it from the
1702                      subpattern, remembering that it was set here so that a repeat of more
1703                      than one can replicate it as reqbyte if necessary. If the subpattern has
1704                      no firstbyte, set "none" for the whole branch. In both cases, a zero
1705                      repeat forces firstbyte to "none". */
1706                     
1707                     if (firstbyte == REQ_UNSET) {
1708                         if (subfirstbyte >= 0) {
1709                             firstbyte = subfirstbyte;
1710                             groupsetfirstbyte = true;
1711                         }
1712                         else
1713                             firstbyte = REQ_NONE;
1714                         zerofirstbyte = REQ_NONE;
1715                     }
1716                     
1717                     /* If firstbyte was previously set, convert the subpattern's firstbyte
1718                      into reqbyte if there wasn't one, using the vary flag that was in
1719                      existence beforehand. */
1720                     
1721                     else if (subfirstbyte >= 0 && subreqbyte < 0)
1722                         subreqbyte = subfirstbyte | tempreqvary;
1723                     
1724                     /* If the subpattern set a required byte (or set a first byte that isn't
1725                      really the first byte - see above), set it. */
1726                     
1727                     if (subreqbyte >= 0)
1728                         reqbyte = subreqbyte;
1729                 }
1730                 
1731                 /* For a forward assertion, we take the reqbyte, if set. This can be
1732                  helpful if the pattern that follows the assertion doesn't set a different
1733                  char. For example, it's useful for /(?=abcde).+/. We can't set firstbyte
1734                  for an assertion, however because it leads to incorrect effect for patterns
1735                  such as /(?=a)a.+/ when the "real" "a" would then become a reqbyte instead
1736                  of a firstbyte. This is overcome by a scan at the end if there's no
1737                  firstbyte, looking for an asserted first char. */
1738                 
1739                 else if (bravalue == OP_ASSERT && subreqbyte >= 0)
1740                     reqbyte = subreqbyte;
1741                 
1742                 /* Now update the main code pointer to the end of the group. */
1743                 
1744                 code = tempcode;
1745                 
1746                 /* Error if hit end of pattern */
1747                 
1748                 if (ptr >= patternEnd || *ptr != ')') {
1749                     *errorcodeptr = ERR14;
1750                     goto FAILED;
1751                 }
1752                 break;
1753                 
1754             /* Check \ for being a real metacharacter; if not, fall through and handle
1755              it as a data character at the start of a string. Escape items are checked
1756              for validity in the pre-compiling pass. */
1757                 
1758             case '\\':
1759                 tempptr = ptr;
1760                 c = check_escape(&ptr, patternEnd, errorcodeptr, *brackets, false);
1761                 
1762                 /* Handle metacharacters introduced by \. For ones like \d, the ESC_ values
1763                  are arranged to be the negation of the corresponding OP_values. For the
1764                  back references, the values are ESC_REF plus the reference number. Only
1765                  back references and those types that consume a character may be repeated.
1766                  We can test for values between ESC_b and ESC_w for the latter; this may
1767                  have to change if any new ones are ever created. */
1768                 
1769                 if (c < 0) {
1770                     /* For metasequences that actually match a character, we disable the
1771                      setting of a first character if it hasn't already been set. */
1772                     
1773                     if (firstbyte == REQ_UNSET && -c > ESC_b && -c <= ESC_w)
1774                         firstbyte = REQ_NONE;
1775                     
1776                     /* Set values to reset to if this is followed by a zero repeat. */
1777                     
1778                     zerofirstbyte = firstbyte;
1779                     zeroreqbyte = reqbyte;
1780                     
1781                     /* Back references are handled specially */
1782                     
1783                     if (-c >= ESC_REF) {
1784                         int number = -c - ESC_REF;
1785                         previous = code;
1786                         *code++ = OP_REF;
1787                         put2ByteOpcodeValueAtOffsetAndAdvance(code, 0, number);
1788                     }
1789                     
1790                     /* For the rest, we can obtain the OP value by negating the escape
1791                      value */
1792                     
1793                     else {
1794                         previous = (-c > ESC_b && -c <= ESC_w)? code : NULL;
1795                         *code++ = -c;
1796                     }
1797                     continue;
1798                 }
1799                 
1800                 /* Fall through. */
1801                 
1802                 /* Handle a literal character. It is guaranteed not to be whitespace or #
1803                  when the extended flag is set. If we are in UTF-8 mode, it may be a
1804                  multi-byte literal character. */
1805                 
1806                 default:
1807             NORMAL_CHAR:
1808                 
1809                 previous = code;
1810                 
1811                 if (c < 128) {
1812                     mclength = 1;
1813                     mcbuffer[0] = c;
1814                     
1815                     if ((options & IgnoreCaseOption) && (c | 0x20) >= 'a' && (c | 0x20) <= 'z') {
1816                         *code++ = OP_ASCII_LETTER_IGNORING_CASE;
1817                         *code++ = c | 0x20;
1818                     } else {
1819                         *code++ = OP_ASCII_CHAR;
1820                         *code++ = c;
1821                     }
1822                 } else {
1823                     mclength = _pcre_ord2utf8(c, mcbuffer);
1824                     
1825                     *code++ = (options & IgnoreCaseOption) ? OP_CHAR_IGNORING_CASE : OP_CHAR;
1826                     for (c = 0; c < mclength; c++)
1827                         *code++ = mcbuffer[c];
1828                 }
1829                 
1830                 /* Set the first and required bytes appropriately. If no previous first
1831                  byte, set it from this character, but revert to none on a zero repeat.
1832                  Otherwise, leave the firstbyte value alone, and don't change it on a zero
1833                  repeat. */
1834                 
1835                 if (firstbyte == REQ_UNSET) {
1836                     zerofirstbyte = REQ_NONE;
1837                     zeroreqbyte = reqbyte;
1838                     
1839                     /* If the character is more than one byte long, we can set firstbyte
1840                      only if it is not to be matched caselessly. */
1841                     
1842                     if (mclength == 1 || req_caseopt == 0) {
1843                         firstbyte = mcbuffer[0] | req_caseopt;
1844                         if (mclength != 1)
1845                             reqbyte = code[-1] | cd.req_varyopt;
1846                     }
1847                     else
1848                         firstbyte = reqbyte = REQ_NONE;
1849                 }
1850                 
1851                 /* firstbyte was previously set; we can set reqbyte only the length is
1852                  1 or the matching is caseful. */
1853                 
1854                 else {
1855                     zerofirstbyte = firstbyte;
1856                     zeroreqbyte = reqbyte;
1857                     if (mclength == 1 || req_caseopt == 0)
1858                         reqbyte = code[-1] | req_caseopt | cd.req_varyopt;
1859                 }
1860                 
1861                 break;            /* End of literal character handling */
1862         }
1863     }                   /* end of big loop */
1864     
1865     /* Control never reaches here by falling through, only by a goto for all the
1866      error states. Pass back the position in the pattern so that it can be displayed
1867      to the user for diagnosing the error. */
1868     
1869 FAILED:
1870     *ptrptr = ptr;
1871     return false;
1872 }
1873
1874
1875
1876
1877 /*************************************************
1878 *     Compile sequence of alternatives           *
1879 *************************************************/
1880
1881 /* On entry, ptr is pointing past the bracket character, but on return
1882 it points to the closing bracket, or vertical bar, or end of string.
1883 The code variable is pointing at the byte into which the BRA operator has been
1884 stored. If the ims options are changed at the start (for a (?ims: group) or
1885 during any branch, we need to insert an OP_OPT item at the start of every
1886 following branch to ensure they get set correctly at run time, and also pass
1887 the new options into every subsequent branch compile.
1888
1889 Argument:
1890   options        option bits, including any changes for this subpattern
1891   brackets       -> int containing the number of extracting brackets used
1892   codeptr        -> the address of the current code pointer
1893   ptrptr         -> the address of the current pattern pointer
1894   errorcodeptr   -> pointer to error code variable
1895   skipbytes      skip this many bytes at start (for OP_BRANUMBER)
1896   firstbyteptr   place to put the first required character, or a negative number
1897   reqbyteptr     place to put the last required character, or a negative number
1898   cd             points to the data block with tables pointers etc.
1899
1900 Returns:      true on success
1901 */
1902
1903 static bool
1904 compile_regex(int options, int* brackets, uschar** codeptr,
1905               const UChar** ptrptr, const UChar* patternEnd, ErrorCode* errorcodeptr, int skipbytes,
1906               int* firstbyteptr, int* reqbyteptr, CompileData& cd)
1907 {
1908     const UChar* ptr = *ptrptr;
1909     uschar* code = *codeptr;
1910     uschar* last_branch = code;
1911     uschar* start_bracket = code;
1912     int firstbyte = REQ_UNSET;
1913     int reqbyte = REQ_UNSET;
1914     
1915     /* Offset is set zero to mark that this bracket is still open */
1916     
1917     putOpcodeValueAtOffset(code, 1, 0);
1918     code += 1 + LINK_SIZE + skipbytes;
1919     
1920     /* Loop for each alternative branch */
1921     
1922     while (true) {
1923         /* Now compile the branch */
1924         
1925         int branchfirstbyte = REQ_UNSET;
1926         int branchreqbyte = REQ_UNSET;
1927         if (!compile_branch(options, brackets, &code, &ptr, patternEnd, errorcodeptr,
1928                             &branchfirstbyte, &branchreqbyte, cd)) {
1929             *ptrptr = ptr;
1930             return false;
1931         }
1932         
1933         /* If this is the first branch, the firstbyte and reqbyte values for the
1934          branch become the values for the regex. */
1935         
1936         if (*last_branch != OP_ALT) {
1937             firstbyte = branchfirstbyte;
1938             reqbyte = branchreqbyte;
1939         }
1940         
1941         /* If this is not the first branch, the first char and reqbyte have to
1942          match the values from all the previous branches, except that if the previous
1943          value for reqbyte didn't have REQ_VARY set, it can still match, and we set
1944          REQ_VARY for the regex. */
1945         
1946         else {
1947             /* If we previously had a firstbyte, but it doesn't match the new branch,
1948              we have to abandon the firstbyte for the regex, but if there was previously
1949              no reqbyte, it takes on the value of the old firstbyte. */
1950             
1951             if (firstbyte >= 0 && firstbyte != branchfirstbyte) {
1952                 if (reqbyte < 0)
1953                     reqbyte = firstbyte;
1954                 firstbyte = REQ_NONE;
1955             }
1956             
1957             /* If we (now or from before) have no firstbyte, a firstbyte from the
1958              branch becomes a reqbyte if there isn't a branch reqbyte. */
1959             
1960             if (firstbyte < 0 && branchfirstbyte >= 0 && branchreqbyte < 0)
1961                 branchreqbyte = branchfirstbyte;
1962             
1963             /* Now ensure that the reqbytes match */
1964             
1965             if ((reqbyte & ~REQ_VARY) != (branchreqbyte & ~REQ_VARY))
1966                 reqbyte = REQ_NONE;
1967             else
1968                 reqbyte |= branchreqbyte;   /* To "or" REQ_VARY */
1969         }
1970         
1971         /* Reached end of expression, either ')' or end of pattern. Go back through
1972          the alternative branches and reverse the chain of offsets, with the field in
1973          the BRA item now becoming an offset to the first alternative. If there are
1974          no alternatives, it points to the end of the group. The length in the
1975          terminating ket is always the length of the whole bracketed item. If any of
1976          the ims options were changed inside the group, compile a resetting op-code
1977          following, except at the very end of the pattern. Return leaving the pointer
1978          at the terminating char. */
1979         
1980         if (ptr >= patternEnd || *ptr != '|') {
1981             int length = code - last_branch;
1982             do {
1983                 int prev_length = getOpcodeValueAtOffset(last_branch, 1);
1984                 putOpcodeValueAtOffset(last_branch, 1, length);
1985                 length = prev_length;
1986                 last_branch -= length;
1987             } while (length > 0);
1988             
1989             /* Fill in the ket */
1990             
1991             *code = OP_KET;
1992             putOpcodeValueAtOffset(code, 1, code - start_bracket);
1993             code += 1 + LINK_SIZE;
1994             
1995             /* Set values to pass back */
1996             
1997             *codeptr = code;
1998             *ptrptr = ptr;
1999             *firstbyteptr = firstbyte;
2000             *reqbyteptr = reqbyte;
2001             return true;
2002         }
2003         
2004         /* Another branch follows; insert an "or" node. Its length field points back
2005          to the previous branch while the bracket remains open. At the end the chain
2006          is reversed. It's done like this so that the start of the bracket has a
2007          zero offset until it is closed, making it possible to detect recursion. */
2008         
2009         *code = OP_ALT;
2010         putOpcodeValueAtOffset(code, 1, code - last_branch);
2011         last_branch = code;
2012         code += 1 + LINK_SIZE;
2013         ptr++;
2014     }
2015     ASSERT_NOT_REACHED();
2016 }
2017
2018
2019 /*************************************************
2020 *          Check for anchored expression         *
2021 *************************************************/
2022
2023 /* Try to find out if this is an anchored regular expression. Consider each
2024 alternative branch. If they all start with OP_SOD or OP_CIRC, or with a bracket
2025 all of whose alternatives start with OP_SOD or OP_CIRC (recurse ad lib), then
2026 it's anchored. However, if this is a multiline pattern, then only OP_SOD
2027 counts, since OP_CIRC can match in the middle.
2028
2029 We can also consider a regex to be anchored if OP_SOM starts all its branches.
2030 This is the code for \G, which means "match at start of match position, taking
2031 into account the match offset".
2032
2033 A branch is also implicitly anchored if it starts with .* and DOTALL is set,
2034 because that will try the rest of the pattern at all possible matching points,
2035 so there is no point trying again.... er ....
2036
2037 .... except when the .* appears inside capturing parentheses, and there is a
2038 subsequent back reference to those parentheses. We haven't enough information
2039 to catch that case precisely.
2040
2041 At first, the best we could do was to detect when .* was in capturing brackets
2042 and the highest back reference was greater than or equal to that level.
2043 However, by keeping a bitmap of the first 31 back references, we can catch some
2044 of the more common cases more precisely.
2045
2046 Arguments:
2047   code           points to start of expression (the bracket)
2048   options        points to the options setting
2049   bracket_map    a bitmap of which brackets we are inside while testing; this
2050                   handles up to substring 31; after that we just have to take
2051                   the less precise approach
2052   backref_map    the back reference bitmap
2053
2054 Returns:     true or false
2055 */
2056
2057 static bool is_anchored(const uschar* code, int options, unsigned bracket_map, unsigned backref_map)
2058 {
2059     do {
2060         const uschar* scode = firstSignificantOpCode(code + 1 + LINK_SIZE);
2061         int op = *scode;
2062         
2063         /* Capturing brackets */
2064         if (op > OP_BRA) {
2065             op -= OP_BRA;
2066             if (op > EXTRACT_BASIC_MAX)
2067                 op = get2ByteOpcodeValueAtOffset(scode, 2 + LINK_SIZE);
2068             int new_map = bracket_map | ((op < 32)? (1 << op) : 1);
2069             if (!is_anchored(scode, options, new_map, backref_map))
2070                 return false;
2071         }
2072         
2073         /* Other brackets */
2074         else if (op == OP_BRA || op == OP_ASSERT || op == OP_ONCE) {
2075             if (!is_anchored(scode, options, bracket_map, backref_map))
2076                 return false;
2077         
2078         /* Check for explicit anchoring */
2079         
2080         } else if ((options & MatchAcrossMultipleLinesOption) || op != OP_CIRC)
2081             return false;
2082         code += getOpcodeValueAtOffset(code, 1);
2083     } while (*code == OP_ALT);   /* Loop for each alternative */
2084     return true;
2085 }
2086
2087
2088
2089 /*************************************************
2090 *         Check for starting with ^ or .*        *
2091 *************************************************/
2092
2093 /* This is called to find out if every branch starts with ^ or .* so that
2094 "first char" processing can be done to speed things up in multiline
2095 matching and for non-DOTALL patterns that start with .* (which must start at
2096 the beginning or after \n). As in the case of is_anchored() (see above), we
2097 have to take account of back references to capturing brackets that contain .*
2098 because in that case we can't make the assumption.
2099
2100 Arguments:
2101   code           points to start of expression (the bracket)
2102   bracket_map    a bitmap of which brackets we are inside while testing; this
2103                   handles up to substring 31; after that we just have to take
2104                   the less precise approach
2105   backref_map    the back reference bitmap
2106 */
2107
2108 static bool canApplyFirstCharOptimization(const uschar* code, unsigned bracket_map, unsigned backref_map)
2109 {
2110     do {
2111         const uschar* scode = firstSignificantOpCode(code + 1 + LINK_SIZE);
2112         int op = *scode;
2113         
2114         /* Capturing brackets */
2115         if (op > OP_BRA) {
2116             op -= OP_BRA;
2117             if (op > EXTRACT_BASIC_MAX)
2118                 op = get2ByteOpcodeValueAtOffset(scode, 2+LINK_SIZE);
2119             int new_map = bracket_map | ((op < 32)? (1 << op) : 1);
2120             if (!canApplyFirstCharOptimization(scode, new_map, backref_map))
2121                 return false;
2122         }
2123         
2124         /* Other brackets */
2125         else if (op == OP_BRA || op == OP_ASSERT || op == OP_ONCE) {
2126             if (!canApplyFirstCharOptimization(scode, bracket_map, backref_map))
2127                 return false;
2128         
2129         /* .* means "start at start or after \n" if it isn't in brackets that
2130          may be referenced. */
2131         
2132         } else if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR) {
2133             if (scode[1] != OP_NOT_NEWLINE || (bracket_map & backref_map))
2134                 return false;
2135         } else if (op != OP_CIRC) /* Check for explicit circumflex */
2136             return false;
2137         
2138         /* Move on to the next alternative */
2139         
2140         code += getOpcodeValueAtOffset(code, 1);
2141     } while (*code == OP_ALT);  /* Loop for each alternative */
2142     return true;
2143 }
2144
2145
2146 /*************************************************
2147 *       Check for asserted fixed first char      *
2148 *************************************************/
2149
2150 /* During compilation, the "first char" settings from forward assertions are
2151 discarded, because they can cause conflicts with actual literals that follow.
2152 However, if we end up without a first char setting for an unanchored pattern,
2153 it is worth scanning the regex to see if there is an initial asserted first
2154 char. If all branches start with the same asserted char, or with a bracket all
2155 of whose alternatives start with the same asserted char (recurse ad lib), then
2156 we return that char, otherwise -1.
2157
2158 Arguments:
2159   code       points to start of expression (the bracket)
2160   options    pointer to the options (used to check casing changes)
2161   inassert   true if in an assertion
2162
2163 Returns:     -1 or the fixed first char
2164 */
2165
2166 static int find_firstassertedchar(const uschar* code, int options, bool inassert)
2167 {
2168     int c = -1;
2169     do {
2170         const uschar* scode = firstSignificantOpCodeSkippingAssertions(code + 1 + LINK_SIZE);
2171         int op = *scode;
2172         
2173         if (op >= OP_BRA)
2174             op = OP_BRA;
2175         
2176         switch (op) {
2177             default:
2178                 return -1;
2179                 
2180             case OP_BRA:
2181             case OP_ASSERT:
2182             case OP_ONCE: {
2183                 int d;
2184                 if ((d = find_firstassertedchar(scode, options, op == OP_ASSERT)) < 0)
2185                     return -1;
2186                 if (c < 0)
2187                     c = d;
2188                 else if (c != d)
2189                     return -1;
2190                 break;
2191             }
2192
2193             case OP_EXACT:
2194                 scode += 2;
2195                 /* Fall through */
2196
2197             case OP_CHAR:
2198             case OP_CHAR_IGNORING_CASE:
2199             case OP_ASCII_CHAR:
2200             case OP_ASCII_LETTER_IGNORING_CASE:
2201             case OP_PLUS:
2202             case OP_MINPLUS:
2203                 if (!inassert)
2204                     return -1;
2205                 if (c < 0) {
2206                     c = scode[1];
2207                     if (options & IgnoreCaseOption)
2208                         c |= REQ_IGNORE_CASE;
2209                 }
2210                 else if (c != scode[1])
2211                     return -1;
2212                 break;
2213         }
2214
2215         code += getOpcodeValueAtOffset(code, 1);
2216     } while (*code == OP_ALT);
2217     return c;
2218 }
2219
2220 static int calculateCompiledPatternLengthAndFlags(const UChar* pattern, int patternLength, JSRegExpIgnoreCaseOption ignoreCase, CompileData& compile_block, ErrorCode& errorcode)
2221 {
2222     /* Make a pass over the pattern to compute the
2223      amount of store required to hold the compiled code. This does not have to be
2224      perfect as long as errors are overestimates. At the same time we can detect any
2225      flag settings right at the start, and extract them. Make an attempt to correct
2226      for any counted white space if an "extended" flag setting appears late in the
2227      pattern. We can't be so clever for #-comments. */
2228     
2229     int length = 1 + LINK_SIZE;      /* For initial BRA plus length */
2230     int branch_extra = 0;
2231     int lastitemlength = 0;
2232     unsigned brastackptr = 0;
2233     int brastack[BRASTACK_SIZE];
2234     uschar bralenstack[BRASTACK_SIZE];
2235     int item_count = -1;
2236     int bracount = 0;
2237     
2238     const UChar* ptr = (const UChar*)(pattern - 1);
2239     const UChar* patternEnd = (const UChar*)(pattern + patternLength);
2240     
2241     while (++ptr < patternEnd) {
2242         int minRepeats = 0, maxRepeats = 0;
2243         int c = *ptr;
2244
2245         item_count++;    /* Is zero for the first non-comment item */
2246
2247         switch (c) {
2248             /* A backslashed item may be an escaped data character or it may be a
2249              character type. */
2250
2251             case '\\':
2252                 c = check_escape(&ptr, patternEnd, &errorcode, bracount, false);
2253                 if (errorcode != 0)
2254                     return -1;
2255                 
2256                 lastitemlength = 1;     /* Default length of last item for repeats */
2257                 
2258                 if (c >= 0) {            /* Data character */
2259                     length += 2;          /* For a one-byte character */
2260                     
2261                     if (c > 127) {
2262                         int i;
2263                         for (i = 0; i < _pcre_utf8_table1_size; i++)
2264                             if (c <= _pcre_utf8_table1[i]) break;
2265                         length += i;
2266                         lastitemlength += i;
2267                     }
2268                     
2269                     continue;
2270                 }
2271                 
2272                 /* Other escapes need one byte */
2273                 
2274                 length++;
2275                 
2276                 /* A back reference needs an additional 2 bytes, plus either one or 5
2277                  bytes for a repeat. We also need to keep the value of the highest
2278                  back reference. */
2279                 
2280                 if (c <= -ESC_REF) {
2281                     int refnum = -c - ESC_REF;
2282                     compile_block.backref_map |= (refnum < 32)? (1 << refnum) : 1;
2283                     if (refnum > compile_block.top_backref)
2284                         compile_block.top_backref = refnum;
2285                     length += 2;   /* For single back reference */
2286                     if (safelyCheckNextChar(ptr, patternEnd, '{') && is_counted_repeat(ptr + 2, patternEnd)) {
2287                         ptr = read_repeat_counts(ptr + 2, &minRepeats, &maxRepeats, &errorcode);
2288                         if (errorcode)
2289                             return -1;
2290                         if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) ||
2291                             (minRepeats == 1 && maxRepeats == -1))
2292                             length++;
2293                         else
2294                             length += 5;
2295                         if (safelyCheckNextChar(ptr, patternEnd, '?'))
2296                             ptr++;
2297                     }
2298                 }
2299                 continue;
2300                 
2301             case '^':     /* Single-byte metacharacters */
2302             case '.':
2303             case '$':
2304                 length++;
2305                 lastitemlength = 1;
2306                 continue;
2307                 
2308             case '*':            /* These repeats won't be after brackets; */
2309             case '+':            /* those are handled separately */
2310             case '?':
2311                 length++;
2312                 goto POSSESSIVE;
2313                 
2314             /* This covers the cases of braced repeats after a single char, metachar,
2315              class, or back reference. */
2316
2317             case '{':
2318                 if (!is_counted_repeat(ptr+1, patternEnd))
2319                     goto NORMAL_CHAR;
2320                 ptr = read_repeat_counts(ptr+1, &minRepeats, &maxRepeats, &errorcode);
2321                 if (errorcode != 0)
2322                     return -1;
2323                 
2324                 /* These special cases just insert one extra opcode */
2325                 
2326                 if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) ||
2327                     (minRepeats == 1 && maxRepeats == -1))
2328                     length++;
2329                 
2330                 /* These cases might insert additional copies of a preceding character. */
2331                 
2332                 else {
2333                     if (minRepeats != 1) {
2334                         length -= lastitemlength;   /* Uncount the original char or metachar */
2335                         if (minRepeats > 0)
2336                             length += 3 + lastitemlength;
2337                     }
2338                     length += lastitemlength + ((maxRepeats > 0)? 3 : 1);
2339                 }
2340                 
2341                 if (safelyCheckNextChar(ptr, patternEnd, '?'))
2342                     ptr++;      /* Needs no extra length */
2343
2344             POSSESSIVE:                     /* Test for possessive quantifier */
2345                 if (safelyCheckNextChar(ptr, patternEnd, '+')) {
2346                     ptr++;
2347                     length += 2 + 2 * LINK_SIZE;   /* Allow for atomic brackets */
2348                 }
2349                 continue;
2350                 
2351             /* An alternation contains an offset to the next branch or ket. If any ims
2352              options changed in the previous branch(es), and/or if we are in a
2353              lookbehind assertion, extra space will be needed at the start of the
2354              branch. This is handled by branch_extra. */
2355                 
2356             case '|':
2357                 length += 1 + LINK_SIZE + branch_extra;
2358                 continue;
2359                 
2360             /* A character class uses 33 characters provided that all the character
2361              values are less than 256. Otherwise, it uses a bit map for low valued
2362              characters, and individual items for others. Don't worry about character
2363              types that aren't allowed in classes - they'll get picked up during the
2364              compile. A character class that contains only one single-byte character
2365              uses 2 or 3 bytes, depending on whether it is negated or not. Notice this
2366              where we can. (In UTF-8 mode we can do this only for chars < 128.) */
2367                 
2368             case '[': {
2369                 int class_optcount;
2370                 if (*(++ptr) == '^') {
2371                     class_optcount = 10;  /* Greater than one */
2372                     ptr++;
2373                 }
2374                 else
2375                     class_optcount = 0;
2376                 
2377                 bool class_utf8 = false;
2378                 
2379                 for (; ptr < patternEnd && *ptr != ']'; ++ptr) {
2380                     /* Check for escapes */
2381                     
2382                     if (*ptr == '\\') {
2383                         c = check_escape(&ptr, patternEnd, &errorcode, bracount, true);
2384                         if (errorcode != 0)
2385                             return -1;
2386                         
2387                         /* \b is backspace inside a class; \X is literal */
2388                         
2389                         if (-c == ESC_b)
2390                             c = '\b';
2391                         
2392                         /* Handle escapes that turn into characters */
2393                         
2394                         if (c >= 0)
2395                             goto NON_SPECIAL_CHARACTER;
2396                         
2397                         /* Escapes that are meta-things. The normal ones just affect the
2398                          bit map, but Unicode properties require an XCLASS extended item. */
2399                         
2400                         else
2401                             class_optcount = 10;         /* \d, \s etc; make sure > 1 */
2402                     }
2403                     
2404                     /* Anything else increments the possible optimization count. We have to
2405                      detect ranges here so that we can compute the number of extra ranges for
2406                      caseless wide characters when UCP support is available. If there are wide
2407                      characters, we are going to have to use an XCLASS, even for single
2408                      characters. */
2409                     
2410                     else {
2411                         c = *ptr;
2412                         
2413                         /* Come here from handling \ above when it escapes to a char value */
2414                         
2415                     NON_SPECIAL_CHARACTER:
2416                         class_optcount++;
2417                         
2418                         int d = -1;
2419                         if (safelyCheckNextChar(ptr, patternEnd, '-')) {
2420                             UChar const *hyptr = ptr++;
2421                             if (safelyCheckNextChar(ptr, patternEnd, '\\')) {
2422                                 ptr++;
2423                                 d = check_escape(&ptr, patternEnd, &errorcode, bracount, true);
2424                                 if (errorcode != 0)
2425                                     return -1;
2426                                 if (-d == ESC_b)
2427                                     d = '\b';        /* backspace */
2428                             }
2429                             else if ((ptr + 1 < patternEnd) && ptr[1] != ']')
2430                                 d = *++ptr;
2431                             if (d < 0)
2432                                 ptr = hyptr;      /* go back to hyphen as data */
2433                         }
2434                         
2435                         /* If d >= 0 we have a range. In UTF-8 mode, if the end is > 255, or >
2436                          127 for caseless matching, we will need to use an XCLASS. */
2437                         
2438                         if (d >= 0) {
2439                             class_optcount = 10;     /* Ensure > 1 */
2440                             if (d < c) {
2441                                 errorcode = ERR8;
2442                                 return -1;
2443                             }
2444                             
2445                             if ((d > 255 || (ignoreCase && d > 127))) {
2446                                 uschar buffer[6];
2447                                 if (!class_utf8)         /* Allow for XCLASS overhead */
2448                                 {
2449                                     class_utf8 = true;
2450                                     length += LINK_SIZE + 2;
2451                                 }
2452                                 
2453                                 /* If we have UCP support, find out how many extra ranges are
2454                                  needed to map the other case of characters within this range. We
2455                                  have to mimic the range optimization here, because extending the
2456                                  range upwards might push d over a boundary that makes it use
2457                                  another byte in the UTF-8 representation. */
2458                                 
2459                                 if (ignoreCase) {
2460                                     int occ, ocd;
2461                                     int cc = c;
2462                                     int origd = d;
2463                                     while (get_othercase_range(&cc, origd, &occ, &ocd)) {
2464                                         if (occ >= c && ocd <= d)
2465                                             continue;   /* Skip embedded */
2466                                         
2467                                         if (occ < c  && ocd >= c - 1)  /* Extend the basic range */
2468                                         {                            /* if there is overlap,   */
2469                                             c = occ;                     /* noting that if occ < c */
2470                                             continue;                    /* we can't have ocd > d  */
2471                                         }                            /* because a subrange is  */
2472                                         if (ocd > d && occ <= d + 1)   /* always shorter than    */
2473                                         {                            /* the basic range.       */
2474                                             d = ocd;
2475                                             continue;
2476                                         }
2477                                         
2478                                         /* An extra item is needed */
2479                                         
2480                                         length += 1 + _pcre_ord2utf8(occ, buffer) +
2481                                         ((occ == ocd)? 0 : _pcre_ord2utf8(ocd, buffer));
2482                                     }
2483                                 }
2484                                 
2485                                 /* The length of the (possibly extended) range */
2486                                 
2487                                 length += 1 + _pcre_ord2utf8(c, buffer) + _pcre_ord2utf8(d, buffer);
2488                             }
2489                             
2490                         }
2491                         
2492                         /* We have a single character. There is nothing to be done unless we
2493                          are in UTF-8 mode. If the char is > 255, or 127 when caseless, we must
2494                          allow for an XCL_SINGLE item, doubled for caselessness if there is UCP
2495                          support. */
2496                         
2497                         else {
2498                             if ((c > 255 || (ignoreCase && c > 127))) {
2499                                 uschar buffer[6];
2500                                 class_optcount = 10;     /* Ensure > 1 */
2501                                 if (!class_utf8)         /* Allow for XCLASS overhead */
2502                                 {
2503                                     class_utf8 = true;
2504                                     length += LINK_SIZE + 2;
2505                                 }
2506                                 length += (ignoreCase ? 2 : 1) * (1 + _pcre_ord2utf8(c, buffer));
2507                             }
2508                         }
2509                     }
2510                 }
2511                 
2512                 if (ptr >= patternEnd) {   /* Missing terminating ']' */
2513                     errorcode = ERR6;
2514                     return -1;
2515                 }
2516                 
2517                 /* We can optimize when there was only one optimizable character. Repeats
2518                  for positive and negated single one-byte chars are handled by the general
2519                  code. Here, we handle repeats for the class opcodes. */
2520                 
2521                 if (class_optcount == 1)
2522                     length += 3;
2523                 else {
2524                     length += 33;
2525                     
2526                     /* A repeat needs either 1 or 5 bytes. If it is a possessive quantifier,
2527                      we also need extra for wrapping the whole thing in a sub-pattern. */
2528                     
2529                     if (safelyCheckNextChar(ptr, patternEnd, '{') && is_counted_repeat(ptr+2, patternEnd)) {
2530                         ptr = read_repeat_counts(ptr+2, &minRepeats, &maxRepeats, &errorcode);
2531                         if (errorcode != 0)
2532                             return -1;
2533                         if ((minRepeats == 0 && (maxRepeats == 1 || maxRepeats == -1)) ||
2534                             (minRepeats == 1 && maxRepeats == -1))
2535                             length++;
2536                         else
2537                             length += 5;
2538                         if (safelyCheckNextChar(ptr, patternEnd, '+')) {
2539                             ptr++;
2540                             length += 2 + 2 * LINK_SIZE;
2541                         } else if (safelyCheckNextChar(ptr, patternEnd, '?'))
2542                             ptr++;
2543                     }
2544                 }
2545                 continue;
2546             }
2547
2548             /* Brackets may be genuine groups or special things */
2549                 
2550             case '(': {
2551                 int branch_newextra = 0;
2552                 int bracket_length = 1 + LINK_SIZE;
2553                 bool capturing = false;
2554                 
2555                 /* Handle special forms of bracket, which all start (? */
2556                 
2557                 if (safelyCheckNextChar(ptr, patternEnd, '?')) {
2558                     switch (c = (ptr + 2 < patternEnd ? ptr[2] : 0)) {
2559                             /* Non-referencing groups and lookaheads just move the pointer on, and
2560                              then behave like a non-special bracket, except that they don't increment
2561                              the count of extracting brackets. Ditto for the "once only" bracket,
2562                              which is in Perl from version 5.005. */
2563                             
2564                         case ':':
2565                         case '=':
2566                         case '!':
2567                             ptr += 2;
2568                             break;
2569                             
2570                             /* Else loop checking valid options until ) is met. Anything else is an
2571                              error. If we are without any brackets, i.e. at top level, the settings
2572                              act as if specified in the options, so massage the options immediately.
2573                              This is for backward compatibility with Perl 5.004. */
2574                             
2575                         default:
2576                             errorcode = ERR12;
2577                             return -1;
2578                     }
2579                 } else
2580                     capturing = 1;
2581                 
2582                 /* Capturing brackets must be counted so we can process escapes in a
2583                  Perlish way. If the number exceeds EXTRACT_BASIC_MAX we are going to need
2584                  an additional 3 bytes of memory per capturing bracket. */
2585                 
2586                 if (capturing) {
2587                     bracount++;
2588                     if (bracount > EXTRACT_BASIC_MAX)
2589                         bracket_length += 3;
2590                 }
2591                 
2592                 /* Save length for computing whole length at end if there's a repeat that
2593                  requires duplication of the group. Also save the current value of
2594                  branch_extra, and start the new group with the new value. If non-zero, this
2595                  will either be 2 for a (?imsx: group, or 3 for a lookbehind assertion. */
2596                 
2597                 if (brastackptr >= sizeof(brastack)/sizeof(int)) {
2598                     errorcode = ERR17;
2599                     return -1;
2600                 }
2601                 
2602                 bralenstack[brastackptr] = branch_extra;
2603                 branch_extra = branch_newextra;
2604                 
2605                 brastack[brastackptr++] = length;
2606                 length += bracket_length;
2607                 continue;
2608             }
2609
2610             /* Handle ket. Look for subsequent maxRepeats/minRepeats; for certain sets of values we
2611              have to replicate this bracket up to that many times. If brastackptr is
2612              0 this is an unmatched bracket which will generate an error, but take care
2613              not to try to access brastack[-1] when computing the length and restoring
2614              the branch_extra value. */
2615
2616             case ')': {
2617                 int duplength;
2618                 length += 1 + LINK_SIZE;
2619                 if (brastackptr > 0) {
2620                     duplength = length - brastack[--brastackptr];
2621                     branch_extra = bralenstack[brastackptr];
2622                 }
2623                 else
2624                     duplength = 0;
2625                 
2626                 /* Leave ptr at the final char; for read_repeat_counts this happens
2627                  automatically; for the others we need an increment. */
2628                 
2629                 if ((ptr + 1 < patternEnd) && (c = ptr[1]) == '{' && is_counted_repeat(ptr+2, patternEnd)) {
2630                     ptr = read_repeat_counts(ptr+2, &minRepeats, &maxRepeats, &errorcode);
2631                     if (errorcode)
2632                         return -1;
2633                 } else if (c == '*') {
2634                     minRepeats = 0;
2635                     maxRepeats = -1;
2636                     ptr++;
2637                 } else if (c == '+') {
2638                     minRepeats = 1;
2639                     maxRepeats = -1;
2640                     ptr++;
2641                 } else if (c == '?') {
2642                     minRepeats = 0;
2643                     maxRepeats = 1;
2644                     ptr++;
2645                 } else {
2646                     minRepeats = 1;
2647                     maxRepeats = 1;
2648                 }
2649                 
2650                 /* If the minimum is zero, we have to allow for an OP_BRAZERO before the
2651                  group, and if the maximum is greater than zero, we have to replicate
2652                  maxval-1 times; each replication acquires an OP_BRAZERO plus a nesting
2653                  bracket set. */
2654                 
2655                 if (minRepeats == 0) {
2656                     length++;
2657                     if (maxRepeats > 0) length += (maxRepeats - 1) * (duplength + 3 + 2 * LINK_SIZE);
2658                 }
2659                 
2660                 /* When the minimum is greater than zero, we have to replicate up to
2661                  minval-1 times, with no additions required in the copies. Then, if there
2662                  is a limited maximum we have to replicate up to maxval-1 times allowing
2663                  for a BRAZERO item before each optional copy and nesting brackets for all
2664                  but one of the optional copies. */
2665                 
2666                 else {
2667                     length += (minRepeats - 1) * duplength;
2668                     if (maxRepeats > minRepeats)   /* Need this test as maxRepeats=-1 means no limit */
2669                         length += (maxRepeats - minRepeats) * (duplength + 3 + 2 * LINK_SIZE)
2670                         - (2 + 2 * LINK_SIZE);
2671                 }
2672                 
2673                 /* Allow space for once brackets for "possessive quantifier" */
2674                 
2675                 if (safelyCheckNextChar(ptr, patternEnd, '+')) {
2676                     ptr++;
2677                     length += 2 + 2 * LINK_SIZE;
2678                 }
2679                 continue;
2680             }
2681
2682             /* Non-special character. It won't be space or # in extended mode, so it is
2683              always a genuine character. If we are in a \Q...\E sequence, check for the
2684              end; if not, we have a literal. */
2685                 
2686             default:
2687             NORMAL_CHAR:
2688                 length += 2;          /* For a one-byte character */
2689                 lastitemlength = 1;   /* Default length of last item for repeats */
2690
2691                 if (c > 127) {
2692                     int i;
2693                     for (i = 0; i < _pcre_utf8_table1_size; i++)
2694                         if (c <= _pcre_utf8_table1[i])
2695                             break;
2696                     length += i;
2697                     lastitemlength += i;
2698                 }
2699                 
2700                 continue;
2701         }
2702     }
2703     
2704     length += 2 + LINK_SIZE;    /* For final KET and END */
2705     return length;
2706 }
2707
2708 #ifdef DEBUG
2709 static void printCompiledRegExp(JSRegExp* re, int length)
2710 {
2711     printf("Length = %d top_bracket = %d top_backref = %d\n",
2712            length, re->top_bracket, re->top_backref);
2713     
2714     if (re->options) {
2715         printf("%s%s%s\n",
2716                ((re->options & IsAnchoredOption) != 0)? "anchored " : "",
2717                ((re->options & IgnoreCaseOption) != 0)? "ignores case " : "",
2718                ((re->options & MatchAcrossMultipleLinesOption) != 0)? "multiline " : "");
2719     }
2720     
2721     if (re->options & UseFirstByteOptimizationOption) {
2722         char ch = re->first_byte & 255;
2723         const char* caseless = (re->first_byte & REQ_IGNORE_CASE) ? " (ignores case)" : "";
2724         if (isASCIIAlphanumeric(ch))
2725             printf("First char = %c%s\n", ch, caseless);
2726         else
2727             printf("First char = \\x%02x%s\n", ch, caseless);
2728     }
2729     
2730     if (re->options & UseRequiredByteOptimizationOption) {
2731         char ch = re->req_byte & 255;
2732         const char* caseless = (re->req_byte & REQ_IGNORE_CASE) ? " (ignores case)" : "";
2733         if (isASCIIAlphanumeric(ch))
2734             printf("Req char = %c%s\n", ch, caseless);
2735         else
2736             printf("Req char = \\x%02x%s\n", ch, caseless);
2737     }
2738     
2739     // This debugging function has been removed from JavaScriptCore's PCRE
2740     //pcre_printint(re, stdout);
2741 }
2742 #endif
2743
2744 /*************************************************
2745 *        Compile a Regular Expression            *
2746 *************************************************/
2747
2748 /* This function takes a string and returns a pointer to a block of store
2749 holding a compiled version of the expression. The original API for this
2750 function had no error code return variable; it is retained for backwards
2751 compatibility. The new function is given a new name.
2752
2753 Arguments:
2754   pattern       the regular expression
2755   options       various option bits
2756   errorcodeptr  pointer to error code variable (pcre_compile2() only)
2757                   can be NULL if you don't want a code value
2758   errorptr      pointer to pointer to error text
2759   erroroffset   ptr offset in pattern where error was detected
2760   tables        pointer to character tables or NULL
2761
2762 Returns:        pointer to compiled data block, or NULL on error,
2763                 with errorptr and erroroffset set
2764 */
2765
2766 static JSRegExp* returnError(ErrorCode errorcode, const char** errorptr)
2767 {
2768     *errorptr = error_text(errorcode);
2769     return 0;
2770 }
2771
2772 JSRegExp* jsRegExpCompile(const UChar* pattern, int patternLength,
2773                 JSRegExpIgnoreCaseOption ignoreCase, JSRegExpMultilineOption multiline,
2774                 unsigned* numSubpatterns, const char** errorptr)
2775 {
2776     /* We can't pass back an error message if errorptr is NULL; I guess the best we
2777      can do is just return NULL, but we can set a code value if there is a code pointer. */
2778     if (!errorptr)
2779         return 0;
2780     *errorptr = NULL;
2781     
2782     CompileData compile_block;
2783     
2784     ErrorCode errorcode = ERR0;
2785     int length = calculateCompiledPatternLengthAndFlags(pattern, patternLength, ignoreCase, compile_block, errorcode);
2786     if (errorcode)
2787         return returnError(errorcode, errorptr);
2788     
2789     if (length > MAX_PATTERN_SIZE)
2790         return returnError(ERR16, errorptr);
2791     
2792     size_t size = length + sizeof(JSRegExp);
2793     JSRegExp* re = reinterpret_cast<JSRegExp*>(new char[size]);
2794     
2795     if (!re)
2796         return returnError(ERR13, errorptr);
2797     
2798     /* Put in the magic number, and save the sizes, options, and character table
2799      pointer. NULL is used for the default character tables. The nullpad field is at
2800      the end; it's there to help in the case when a regex compiled on a system with
2801      4-byte pointers is run on another with 8-byte pointers. */
2802     
2803     re->size = (pcre_uint32)size;
2804     re->options = (ignoreCase ? IgnoreCaseOption : 0) | (multiline ? MatchAcrossMultipleLinesOption : 0);
2805     
2806     /* The starting points of the name/number translation table and of the code are
2807      passed around in the compile data block. */
2808     
2809     const uschar* codestart = (const uschar*)(re + 1);
2810     compile_block.start_code = codestart;
2811     compile_block.start_pattern = (const UChar*)pattern;
2812     
2813     /* Set up a starting, non-extracting bracket, then compile the expression. On
2814      error, errorcode will be set non-zero, so we don't need to look at the result
2815      of the function here. */
2816     
2817     const UChar* ptr = (const UChar*)pattern;
2818     const UChar* patternEnd = pattern + patternLength;
2819     uschar* code = (uschar*)codestart;
2820     *code = OP_BRA;
2821     int firstbyte, reqbyte;
2822     int bracketCount = 0;
2823     (void)compile_regex(re->options, &bracketCount, &code, &ptr,
2824                         patternEnd,
2825                         &errorcode, 0, &firstbyte, &reqbyte, compile_block);
2826     re->top_bracket = bracketCount;
2827     re->top_backref = compile_block.top_backref;
2828     
2829     /* If not reached end of pattern on success, there's an excess bracket. */
2830     
2831     if (errorcode == 0 && ptr < patternEnd)
2832         errorcode = ERR10;
2833     
2834     /* Fill in the terminating state and check for disastrous overflow, but
2835      if debugging, leave the test till after things are printed out. */
2836     
2837     *code++ = OP_END;
2838     
2839 #ifndef DEBUG
2840     if (code - codestart > length)
2841         errorcode = ERR7;
2842 #endif
2843     
2844     /* Give an error if there's back reference to a non-existent capturing
2845      subpatte