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