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