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