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