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