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