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