Remove superfluous check again
[privoxy.git] / pcre / pcre.c
1 /*************************************************
2 *      Perl-Compatible Regular Expressions       *
3 *************************************************/
4
5 /*
6 This is a library of functions to support regular expressions whose syntax
7 and semantics are as close as possible to those of the Perl 5 language. See
8 the file Tech.Notes for some information on the internals.
9
10 Written by: Philip Hazel <ph10@cam.ac.uk>
11
12            Copyright (c) 1997-2000 University of Cambridge
13
14 -----------------------------------------------------------------------------
15 Permission is granted to anyone to use this software for any purpose on any
16 computer system, and to redistribute it freely, subject to the following
17 restrictions:
18
19 1. This software is distributed in the hope that it will be useful,
20    but WITHOUT ANY WARRANTY; without even the implied warranty of
21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
22
23 2. The origin of this software must not be misrepresented, either by
24    explicit claim or by omission.
25
26 3. Altered versions must be plainly marked as such, and must not be
27    misrepresented as being the original software.
28
29 4. If PCRE is embedded in any software that is released under the GNU
30    General Purpose Licence (GPL), then the terms of that licence shall
31    supersede any condition above with which it is incompatible.
32 -----------------------------------------------------------------------------
33 */
34
35
36 /* Define DEBUG to get debugging output on stdout. */
37
38 /* #define DEBUG */
39
40 /* Use a macro for debugging printing, 'cause that eliminates the use of #ifdef
41 inline, and there are *still* stupid compilers about that don't like indented
42 pre-processor statements. I suppose it's only been 10 years... */
43
44 #ifdef DEBUG
45 #define DPRINTF(p) printf p
46 #else
47 #define DPRINTF(p) /*nothing*/
48 #endif
49
50 /* Include the internals header, which itself includes Standard C headers plus
51 the external pcre header. */
52
53 #include "internal.h"
54
55
56 /* Allow compilation as C++ source code, should anybody want to do that. */
57
58 #ifdef __cplusplus
59 #define class pcre_class
60 #endif
61
62
63 /* Number of items on the nested bracket stacks at compile time. This should
64 not be set greater than 200. */
65
66 #define BRASTACK_SIZE 200
67
68
69 /* The number of bytes in a literal character string above which we can't add
70 any more is different when UTF-8 characters may be encountered. */
71
72 #ifdef SUPPORT_UTF8
73 #define MAXLIT 250
74 #else
75 #define MAXLIT 255
76 #endif
77
78
79 /* Min and max values for the common repeats; for the maxima, 0 => infinity */
80
81 static const char rep_min[] = { 0, 0, 1, 1, 0, 0 };
82 static const char rep_max[] = { 0, 0, 0, 0, 1, 1 };
83
84 /* Text forms of OP_ values and things, for debugging (not all used) */
85
86 #ifdef DEBUG
87 static const char *OP_names[] = {
88   "End", "\\A", "\\B", "\\b", "\\D", "\\d",
89   "\\S", "\\s", "\\W", "\\w", "\\Z", "\\z",
90   "Opt", "^", "$", "Any", "chars", "not",
91   "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
92   "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
93   "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
94   "*", "*?", "+", "+?", "?", "??", "{", "{",
95   "class", "Ref", "Recurse",
96   "Alt", "Ket", "KetRmax", "KetRmin", "Assert", "Assert not",
97   "AssertB", "AssertB not", "Reverse", "Once", "Cond", "Cref",
98   "Brazero", "Braminzero", "Bra"
99 };
100 #endif
101
102 /* Table for handling escaped characters in the range '0'-'z'. Positive returns
103 are simple data values; negative values are for special things like \d and so
104 on. Zero means further processing is needed (for things like \x), or the escape
105 is invalid. */
106
107 static const short int escapes[] = {
108     0,      0,      0,      0,      0,      0,      0,      0,   /* 0 - 7 */
109     0,      0,    ':',    ';',    '<',    '=',    '>',    '?',   /* 8 - ? */
110   '@', -ESC_A, -ESC_B,      0, -ESC_D,      0,      0,      0,   /* @ - G */
111     0,      0,      0,      0,      0,      0,      0,      0,   /* H - O */
112     0,      0,      0, -ESC_S,      0,      0,      0, -ESC_W,   /* P - W */
113     0,      0, -ESC_Z,    '[',   '\\',    ']',    '^',    '_',   /* X - _ */
114   '`',      7, -ESC_b,      0, -ESC_d,     27,   '\f',      0,   /* ` - g */
115     0,      0,      0,      0,      0,      0,   '\n',      0,   /* h - o */
116     0,      0,   '\r', -ESC_s,   '\t',      0,      0, -ESC_w,   /* p - w */
117     0,      0, -ESC_z                                            /* x - z */
118 };
119
120 /* Tables of names of POSIX character classes and their lengths. The list is
121 terminated by a zero length entry. The first three must be alpha, upper, lower,
122 as this is assumed for handling case independence. */
123
124 static const char *posix_names[] = {
125   "alpha", "lower", "upper",
126   "alnum", "ascii", "cntrl", "digit", "graph",
127   "print", "punct", "space", "word",  "xdigit" };
128
129 static const uschar posix_name_lengths[] = {
130   5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 6, 0 };
131
132 /* Table of class bit maps for each POSIX class; up to three may be combined
133 to form the class. */
134
135 static const int posix_class_maps[] = {
136   cbit_lower, cbit_upper, -1,             /* alpha */
137   cbit_lower, -1,         -1,             /* lower */
138   cbit_upper, -1,         -1,             /* upper */
139   cbit_digit, cbit_lower, cbit_upper,     /* alnum */
140   cbit_print, cbit_cntrl, -1,             /* ascii */
141   cbit_cntrl, -1,         -1,             /* cntrl */
142   cbit_digit, -1,         -1,             /* digit */
143   cbit_graph, -1,         -1,             /* graph */
144   cbit_print, -1,         -1,             /* print */
145   cbit_punct, -1,         -1,             /* punct */
146   cbit_space, -1,         -1,             /* space */
147   cbit_word,  -1,         -1,             /* word */
148   cbit_xdigit,-1,         -1              /* xdigit */
149 };
150
151
152 /* Definition to allow mutual recursion */
153
154 static BOOL
155   compile_regex(int, int, int *, uschar **, const uschar **, const char **,
156     BOOL, int, int *, int *, compile_data *);
157
158 /* Structure for building a chain of data that actually lives on the
159 stack, for holding the values of the subject pointer at the start of each
160 subpattern, so as to detect when an empty string has been matched by a
161 subpattern - to break infinite loops. */
162
163 typedef struct eptrblock {
164   struct eptrblock *prev;
165   const uschar *saved_eptr;
166 } eptrblock;
167
168 /* Flag bits for the match() function */
169
170 #define match_condassert   0x01    /* Called to check a condition assertion */
171 #define match_isgroup      0x02    /* Set if start of bracketed group */
172
173
174
175 /*************************************************
176 *               Global variables                 *
177 *************************************************/
178
179 /* PCRE is thread-clean and doesn't use any global variables in the normal
180 sense. However, it calls memory allocation and free functions via the two
181 indirections below, which are can be changed by the caller, but are shared
182 between all threads. */
183
184 void *(*pcre_malloc)(size_t) = malloc;
185 void  (*pcre_free)(void *) = free;
186
187
188
189 /*************************************************
190 *    Macros and tables for character handling    *
191 *************************************************/
192
193 /* When UTF-8 encoding is being used, a character is no longer just a single
194 byte. The macros for character handling generate simple sequences when used in
195 byte-mode, and more complicated ones for UTF-8 characters. */
196
197 #ifndef SUPPORT_UTF8
198 #define GETCHARINC(c, eptr) c = *eptr++;
199 #define GETCHARLEN(c, eptr, len) c = *eptr;
200 #define BACKCHAR(eptr)
201
202 #else   /* SUPPORT_UTF8 */
203
204 /* Get the next UTF-8 character, advancing the pointer */
205
206 #define GETCHARINC(c, eptr) \
207   c = *eptr++; \
208   if (md->utf8 && (c & 0xc0) == 0xc0) \
209     { \
210     int a = utf8_table4[c & 0x3f];  /* Number of additional bytes */ \
211     int s = 6 - a;                  /* Amount to shift next byte */  \
212     c &= utf8_table3[a];            /* Low order bits from first byte */ \
213     while (a-- > 0) \
214       { \
215       c |= (*eptr++ & 0x3f) << s; \
216       s += 6; \
217       } \
218     }
219
220 /* Get the next UTF-8 character, not advancing the pointer, setting length */
221
222 #define GETCHARLEN(c, eptr, len) \
223   c = *eptr; \
224   len = 1; \
225   if (md->utf8 && (c & 0xc0) == 0xc0) \
226     { \
227     int i; \
228     int a = utf8_table4[c & 0x3f];  /* Number of additional bytes */ \
229     int s = 6 - a;                  /* Amount to shift next byte */  \
230     c &= utf8_table3[a];            /* Low order bits from first byte */ \
231     for (i = 1; i <= a; i++) \
232       { \
233       c |= (eptr[i] & 0x3f) << s; \
234       s += 6; \
235       } \
236     len += a; \
237     }
238
239 /* If the pointer is not at the start of a character, move it back until
240 it is. */
241
242 #define BACKCHAR(eptr) while((*eptr & 0xc0) == 0x80) eptr--;
243
244 #endif
245
246
247
248 /*************************************************
249 *             Default character tables           *
250 *************************************************/
251
252 /* A default set of character tables is included in the PCRE binary. Its source
253 is built by the maketables auxiliary program, which uses the default C ctypes
254 functions, and put in the file chartables.c. These tables are used by PCRE
255 whenever the caller of pcre_compile() does not provide an alternate set of
256 tables. */
257
258 #include "chartables.c"
259
260
261
262 #ifdef SUPPORT_UTF8
263 /*************************************************
264 *           Tables for UTF-8 support             *
265 *************************************************/
266
267 /* These are the breakpoints for different numbers of bytes in a UTF-8
268 character. */
269
270 static int utf8_table1[] = { 0x7f, 0x7ff, 0xffff, 0x1fffff, 0x3ffffff, 0x7fffffff};
271
272 /* These are the indicator bits and the mask for the data bits to set in the
273 first byte of a character, indexed by the number of additional bytes. */
274
275 static int utf8_table2[] = { 0,    0xc0, 0xe0, 0xf0, 0xf8, 0xfc};
276 static int utf8_table3[] = { 0xff, 0x1f, 0x0f, 0x07, 0x03, 0x01};
277
278 /* Table of the number of extra characters, indexed by the first character
279 masked with 0x3f. The highest number for a valid UTF-8 character is in fact
280 0x3d. */
281
282 static uschar utf8_table4[] = {
283   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
284   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
285   2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
286   3,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5 };
287
288
289 /*************************************************
290 *       Convert character value to UTF-8         *
291 *************************************************/
292
293 /* This function takes an integer value in the range 0 - 0x7fffffff
294 and encodes it as a UTF-8 character in 0 to 6 bytes.
295
296 Arguments:
297   cvalue     the character value
298   buffer     pointer to buffer for result - at least 6 bytes long
299
300 Returns:     number of characters placed in the buffer
301 */
302
303 static int
304 ord2utf8(int cvalue, uschar *buffer)
305 {
306 register int i, j;
307 for (i = 0; i < sizeof(utf8_table1)/sizeof(int); i++)
308   if (cvalue <= utf8_table1[i]) break;
309 *buffer++ = utf8_table2[i] | (cvalue & utf8_table3[i]);
310 cvalue >>= 6 - i;
311 for (j = 0; j < i; j++)
312   {
313   *buffer++ = 0x80 | (cvalue & 0x3f);
314   cvalue >>= 6;
315   }
316 return i + 1;
317 }
318 #endif
319
320
321
322 /*************************************************
323 *          Return version string                 *
324 *************************************************/
325
326 #define STRING(a)  # a
327 #define XSTRING(s) STRING(s)
328
329 const char *
330 pcre_version(void)
331 {
332 return XSTRING(PCRE_MAJOR) "." XSTRING(PCRE_MINOR) " " XSTRING(PCRE_DATE);
333 }
334
335
336
337
338 /*************************************************
339 * (Obsolete) Return info about compiled pattern  *
340 *************************************************/
341
342 /* This is the original "info" function. It picks potentially useful data out
343 of the private structure, but its interface was too rigid. It remains for
344 backwards compatibility. The public options are passed back in an int - though
345 the re->options field has been expanded to a long int, all the public options
346 at the low end of it, and so even on 16-bit systems this will still be OK.
347 Therefore, I haven't changed the API for pcre_info().
348
349 Arguments:
350   external_re   points to compiled code
351   optptr        where to pass back the options
352   first_char    where to pass back the first character,
353                 or -1 if multiline and all branches start ^,
354                 or -2 otherwise
355
356 Returns:        number of capturing subpatterns
357                 or negative values on error
358 */
359
360 int
361 pcre_info(const pcre *external_re, int *optptr, int *first_char)
362 {
363 const real_pcre *re = (const real_pcre *)external_re;
364 if (re == NULL) return PCRE_ERROR_NULL;
365 if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
366 if (optptr != NULL) *optptr = (int)(re->options & PUBLIC_OPTIONS);
367 if (first_char != NULL)
368   *first_char = ((re->options & PCRE_FIRSTSET) != 0)? re->first_char :
369      ((re->options & PCRE_STARTLINE) != 0)? -1 : -2;
370 return re->top_bracket;
371 }
372
373
374
375 /*************************************************
376 *        Return info about compiled pattern      *
377 *************************************************/
378
379 /* This is a newer "info" function which has an extensible interface so
380 that additional items can be added compatibly.
381
382 Arguments:
383   external_re      points to compiled code
384   external_study   points to study data, or NULL
385   what             what information is required
386   where            where to put the information
387
388 Returns:           0 if data returned, negative on error
389 */
390
391 int
392 pcre_fullinfo(const pcre *external_re, const pcre_extra *study_data, int what,
393   void *where)
394 {
395 const real_pcre *re = (const real_pcre *)external_re;
396 const real_pcre_extra *study = (const real_pcre_extra *)study_data;
397
398 if (re == NULL || where == NULL) return PCRE_ERROR_NULL;
399 if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
400
401 switch (what)
402   {
403   case PCRE_INFO_OPTIONS:
404   *((unsigned long int *)where) = re->options & PUBLIC_OPTIONS;
405   break;
406
407   case PCRE_INFO_SIZE:
408   *((size_t *)where) = re->size;
409   break;
410
411   case PCRE_INFO_CAPTURECOUNT:
412   *((int *)where) = re->top_bracket;
413   break;
414
415   case PCRE_INFO_BACKREFMAX:
416   *((int *)where) = re->top_backref;
417   break;
418
419   case PCRE_INFO_FIRSTCHAR:
420   *((int *)where) =
421     ((re->options & PCRE_FIRSTSET) != 0)? re->first_char :
422     ((re->options & PCRE_STARTLINE) != 0)? -1 : -2;
423   break;
424
425   case PCRE_INFO_FIRSTTABLE:
426   *((const uschar **)where) =
427     (study != NULL && (study->options & PCRE_STUDY_MAPPED) != 0)?
428       study->start_bits : NULL;
429   break;
430
431   case PCRE_INFO_LASTLITERAL:
432   *((int *)where) =
433     ((re->options & PCRE_REQCHSET) != 0)? re->req_char : -1;
434   break;
435
436   default: return PCRE_ERROR_BADOPTION;
437   }
438
439 return 0;
440 }
441
442
443
444 #ifdef DEBUG
445 /*************************************************
446 *        Debugging function to print chars       *
447 *************************************************/
448
449 /* Print a sequence of chars in printable format, stopping at the end of the
450 subject if the requested.
451
452 Arguments:
453   p           points to characters
454   length      number to print
455   is_subject  TRUE if printing from within md->start_subject
456   md          pointer to matching data block, if is_subject is TRUE
457
458 Returns:     nothing
459 */
460
461 static void
462 pchars(const uschar *p, int length, BOOL is_subject, match_data *md)
463 {
464 int c;
465 if (is_subject && length > md->end_subject - p) length = md->end_subject - p;
466 while (length-- > 0)
467   if (isprint(c = *(p++))) printf("%c", c); else printf("\\x%02x", c);
468 }
469 #endif
470
471
472
473
474 /*************************************************
475 *            Handle escapes                      *
476 *************************************************/
477
478 /* This function is called when a \ has been encountered. It either returns a
479 positive value for a simple escape such as \n, or a negative value which
480 encodes one of the more complicated things such as \d. When UTF-8 is enabled,
481 a positive value greater than 255 may be returned. On entry, ptr is pointing at
482 the \. On exit, it is on the final character of the escape sequence.
483
484 Arguments:
485   ptrptr     points to the pattern position pointer
486   errorptr   points to the pointer to the error message
487   bracount   number of previous extracting brackets
488   options    the options bits
489   isclass    TRUE if inside a character class
490   cd         pointer to char tables block
491
492 Returns:     zero or positive => a data character
493              negative => a special escape sequence
494              on error, errorptr is set
495 */
496
497 static int
498 check_escape(const uschar **ptrptr, const char **errorptr, int bracount,
499   int options, BOOL isclass, compile_data *cd)
500 {
501 const uschar *ptr = *ptrptr;
502 int c, i;
503
504 /* If backslash is at the end of the pattern, it's an error. */
505
506 c = *(++ptr);
507 if (c == 0) *errorptr = ERR1;
508
509 /* Digits or letters may have special meaning; all others are literals. */
510
511 else if (c < '0' || c > 'z') {}
512
513 /* Do an initial lookup in a table. A non-zero result is something that can be
514 returned immediately. Otherwise further processing may be required. */
515
516 else if ((i = escapes[c - '0']) != 0) c = i;
517
518 /* Escapes that need further processing, or are illegal. */
519
520 else
521   {
522   const uschar *oldptr;
523   switch (c)
524     {
525     /* The handling of escape sequences consisting of a string of digits
526     starting with one that is not zero is not straightforward. By experiment,
527     the way Perl works seems to be as follows:
528
529     Outside a character class, the digits are read as a decimal number. If the
530     number is less than 10, or if there are that many previous extracting
531     left brackets, then it is a back reference. Otherwise, up to three octal
532     digits are read to form an escaped byte. Thus \123 is likely to be octal
533     123 (cf \0123, which is octal 012 followed by the literal 3). If the octal
534     value is greater than 377, the least significant 8 bits are taken. Inside a
535     character class, \ followed by a digit is always an octal number. */
536
537     case '1': case '2': case '3': case '4': case '5':
538     case '6': case '7': case '8': case '9':
539
540     if (!isclass)
541       {
542       oldptr = ptr;
543       c -= '0';
544       while ((cd->ctypes[ptr[1]] & ctype_digit) != 0)
545         c = c * 10 + *(++ptr) - '0';
546       if (c < 10 || c <= bracount)
547         {
548         c = -(ESC_REF + c);
549         break;
550         }
551       ptr = oldptr;      /* Put the pointer back and fall through */
552       }
553
554     /* Handle an octal number following \. If the first digit is 8 or 9, Perl
555     generates a binary zero byte and treats the digit as a following literal.
556     Thus we have to pull back the pointer by one. */
557
558     if ((c = *ptr) >= '8')
559       {
560       ptr--;
561       c = 0;
562       break;
563       }
564
565     /* \0 always starts an octal number, but we may drop through to here with a
566     larger first octal digit. */
567
568     case '0':
569     c -= '0';
570     while(i++ < 2 && (cd->ctypes[ptr[1]] & ctype_digit) != 0 &&
571       ptr[1] != '8' && ptr[1] != '9')
572         c = c * 8 + *(++ptr) - '0';
573     c &= 255;     /* Take least significant 8 bits */
574     break;
575
576     /* \x is complicated when UTF-8 is enabled. \x{ddd} is a character number
577     which can be greater than 0xff, but only if the ddd are hex digits. */
578
579     case 'x':
580 #ifdef SUPPORT_UTF8
581     if (ptr[1] == '{' && (options & PCRE_UTF8) != 0)
582       {
583       const uschar *pt = ptr + 2;
584       register int count = 0;
585       c = 0;
586       while ((cd->ctypes[*pt] & ctype_xdigit) != 0)
587         {
588         count++;
589         c = c * 16 + cd->lcc[*pt] -
590           (((cd->ctypes[*pt] & ctype_digit) != 0)? '0' : 'W');
591         pt++;
592         }
593       if (*pt == '}')
594         {
595         if (c < 0 || count > 8) *errorptr = ERR34;
596         ptr = pt;
597         break;
598         }
599       /* If the sequence of hex digits does not end with '}', then we don't
600       recognize this construct; fall through to the normal \x handling. */
601       }
602 #endif
603
604     /* Read just a single hex char */
605
606     c = 0;
607     while (i++ < 2 && (cd->ctypes[ptr[1]] & ctype_xdigit) != 0)
608       {
609       ptr++;
610       c = c * 16 + cd->lcc[*ptr] -
611         (((cd->ctypes[*ptr] & ctype_digit) != 0)? '0' : 'W');
612       }
613     break;
614
615     /* Other special escapes not starting with a digit are straightforward */
616
617     case 'c':
618     c = *(++ptr);
619     if (c == 0)
620       {
621       *errorptr = ERR2;
622       return 0;
623       }
624
625     /* A letter is upper-cased; then the 0x40 bit is flipped */
626
627     if (c >= 'a' && c <= 'z') c = cd->fcc[c];
628     c ^= 0x40;
629     break;
630
631     /* PCRE_EXTRA enables extensions to Perl in the matter of escapes. Any
632     other alphameric following \ is an error if PCRE_EXTRA was set; otherwise,
633     for Perl compatibility, it is a literal. This code looks a bit odd, but
634     there used to be some cases other than the default, and there may be again
635     in future, so I haven't "optimized" it. */
636
637     default:
638     if ((options & PCRE_EXTRA) != 0) switch(c)
639       {
640       default:
641       *errorptr = ERR3;
642       break;
643       }
644     break;
645     }
646   }
647
648 *ptrptr = ptr;
649 return c;
650 }
651
652
653
654 /*************************************************
655 *            Check for counted repeat            *
656 *************************************************/
657
658 /* This function is called when a '{' is encountered in a place where it might
659 start a quantifier. It looks ahead to see if it really is a quantifier or not.
660 It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd}
661 where the ddds are digits.
662
663 Arguments:
664   p         pointer to the first char after '{'
665   cd        pointer to char tables block
666
667 Returns:    TRUE or FALSE
668 */
669
670 static BOOL
671 is_counted_repeat(const uschar *p, compile_data *cd)
672 {
673 if ((cd->ctypes[*p++] & ctype_digit) == 0) return FALSE;
674 while ((cd->ctypes[*p] & ctype_digit) != 0) p++;
675 if (*p == '}') return TRUE;
676
677 if (*p++ != ',') return FALSE;
678 if (*p == '}') return TRUE;
679
680 if ((cd->ctypes[*p++] & ctype_digit) == 0) return FALSE;
681 while ((cd->ctypes[*p] & ctype_digit) != 0) p++;
682 return (*p == '}');
683 }
684
685
686
687 /*************************************************
688 *         Read repeat counts                     *
689 *************************************************/
690
691 /* Read an item of the form {n,m} and return the values. This is called only
692 after is_counted_repeat() has confirmed that a repeat-count quantifier exists,
693 so the syntax is guaranteed to be correct, but we need to check the values.
694
695 Arguments:
696   p          pointer to first char after '{'
697   minp       pointer to int for min
698   maxp       pointer to int for max
699              returned as -1 if no max
700   errorptr   points to pointer to error message
701   cd         pointer to character tables clock
702
703 Returns:     pointer to '}' on success;
704              current ptr on error, with errorptr set
705 */
706
707 static const uschar *
708 read_repeat_counts(const uschar *p, int *minp, int *maxp,
709   const char **errorptr, compile_data *cd)
710 {
711 int min = 0;
712 int max = -1;
713
714 while ((cd->ctypes[*p] & ctype_digit) != 0) min = min * 10 + *p++ - '0';
715
716 if (*p == '}') max = min; else
717   {
718   if (*(++p) != '}')
719     {
720     max = 0;
721     while((cd->ctypes[*p] & ctype_digit) != 0) max = max * 10 + *p++ - '0';
722     if (max < min)
723       {
724       *errorptr = ERR4;
725       return p;
726       }
727     }
728   }
729
730 /* Do paranoid checks, then fill in the required variables, and pass back the
731 pointer to the terminating '}'. */
732
733 if (min > 65535 || max > 65535)
734   *errorptr = ERR5;
735 else
736   {
737   *minp = min;
738   *maxp = max;
739   }
740 return p;
741 }
742
743
744
745 /*************************************************
746 *        Find the fixed length of a pattern      *
747 *************************************************/
748
749 /* Scan a pattern and compute the fixed length of subject that will match it,
750 if the length is fixed. This is needed for dealing with backward assertions.
751
752 Arguments:
753   code     points to the start of the pattern (the bracket)
754   options  the compiling options
755
756 Returns:   the fixed length, or -1 if there is no fixed length
757 */
758
759 static int
760 find_fixedlength(uschar *code, int options)
761 {
762 int length = -1;
763
764 register int branchlength = 0;
765 register uschar *cc = code + 3;
766
767 /* Scan along the opcodes for this branch. If we get to the end of the
768 branch, check the length against that of the other branches. */
769
770 for (;;)
771   {
772   int d;
773   register int op = *cc;
774   if (op >= OP_BRA) op = OP_BRA;
775
776   switch (op)
777     {
778     case OP_BRA:
779     case OP_ONCE:
780     case OP_COND:
781     d = find_fixedlength(cc, options);
782     if (d < 0) return -1;
783     branchlength += d;
784     do cc += (cc[1] << 8) + cc[2]; while (*cc == OP_ALT);
785     cc += 3;
786     break;
787
788     /* Reached end of a branch; if it's a ket it is the end of a nested
789     call. If it's ALT it is an alternation in a nested call. If it is
790     END it's the end of the outer call. All can be handled by the same code. */
791
792     case OP_ALT:
793     case OP_KET:
794     case OP_KETRMAX:
795     case OP_KETRMIN:
796     case OP_END:
797     if (length < 0) length = branchlength;
798       else if (length != branchlength) return -1;
799     if (*cc != OP_ALT) return length;
800     cc += 3;
801     branchlength = 0;
802     break;
803
804     /* Skip over assertive subpatterns */
805
806     case OP_ASSERT:
807     case OP_ASSERT_NOT:
808     case OP_ASSERTBACK:
809     case OP_ASSERTBACK_NOT:
810     do cc += (cc[1] << 8) + cc[2]; while (*cc == OP_ALT);
811     cc += 3;
812     break;
813
814     /* Skip over things that don't match chars */
815
816     case OP_REVERSE:
817     cc++;
818     /* Fall through */
819
820     case OP_CREF:
821     case OP_OPT:
822     cc++;
823     /* Fall through */
824
825     case OP_SOD:
826     case OP_EOD:
827     case OP_EODN:
828     case OP_CIRC:
829     case OP_DOLL:
830     case OP_NOT_WORD_BOUNDARY:
831     case OP_WORD_BOUNDARY:
832     cc++;
833     break;
834
835     /* Handle char strings. In UTF-8 mode we must count characters, not bytes.
836     This requires a scan of the string, unfortunately. We assume valid UTF-8
837     strings, so all we do is reduce the length by one for byte whose bits are
838     10xxxxxx. */
839
840     case OP_CHARS:
841     branchlength += *(++cc);
842 #ifdef SUPPORT_UTF8
843     for (d = 1; d <= *cc; d++)
844       if ((cc[d] & 0xc0) == 0x80) branchlength--;
845 #endif
846     cc += *cc + 1;
847     break;
848
849     /* Handle exact repetitions */
850
851     case OP_EXACT:
852     case OP_TYPEEXACT:
853     branchlength += (cc[1] << 8) + cc[2];
854     cc += 4;
855     break;
856
857     /* Handle single-char matchers */
858
859     case OP_NOT_DIGIT:
860     case OP_DIGIT:
861     case OP_NOT_WHITESPACE:
862     case OP_WHITESPACE:
863     case OP_NOT_WORDCHAR:
864     case OP_WORDCHAR:
865     case OP_ANY:
866     branchlength++;
867     cc++;
868     break;
869
870
871     /* Check a class for variable quantification */
872
873     case OP_CLASS:
874     cc += (*cc == OP_REF)? 2 : 33;
875
876     switch (*cc)
877       {
878       case OP_CRSTAR:
879       case OP_CRMINSTAR:
880       case OP_CRQUERY:
881       case OP_CRMINQUERY:
882       return -1;
883
884       case OP_CRRANGE:
885       case OP_CRMINRANGE:
886       if ((cc[1] << 8) + cc[2] != (cc[3] << 8) + cc[4]) return -1;
887       branchlength += (cc[1] << 8) + cc[2];
888       cc += 5;
889       break;
890
891       default:
892       branchlength++;
893       }
894     break;
895
896     /* Anything else is variable length */
897
898     default:
899     return -1;
900     }
901   }
902 /* Control never gets here */
903 }
904
905
906
907
908 /*************************************************
909 *           Check for POSIX class syntax         *
910 *************************************************/
911
912 /* This function is called when the sequence "[:" or "[." or "[=" is
913 encountered in a character class. It checks whether this is followed by an
914 optional ^ and then a sequence of letters, terminated by a matching ":]" or
915 ".]" or "=]".
916
917 Argument:
918   ptr      pointer to the initial [
919   endptr   where to return the end pointer
920   cd       pointer to compile data
921
922 Returns:   TRUE or FALSE
923 */
924
925 static BOOL
926 check_posix_syntax(const uschar *ptr, const uschar **endptr, compile_data *cd)
927 {
928 int terminator;          /* Don't combine these lines; the Solaris cc */
929 terminator = *(++ptr);   /* compiler warns about "non-constant" initializer. */
930 if (*(++ptr) == '^') ptr++;
931 while ((cd->ctypes[*ptr] & ctype_letter) != 0) ptr++;
932 if (*ptr == terminator && ptr[1] == ']')
933   {
934   *endptr = ptr;
935   return TRUE;
936   }
937 return FALSE;
938 }
939
940
941
942
943 /*************************************************
944 *          Check POSIX class name                *
945 *************************************************/
946
947 /* This function is called to check the name given in a POSIX-style class entry
948 such as [:alnum:].
949
950 Arguments:
951   ptr        points to the first letter
952   len        the length of the name
953
954 Returns:     a value representing the name, or -1 if unknown
955 */
956
957 static int
958 check_posix_name(const uschar *ptr, int len)
959 {
960 register int yield = 0;
961 while (posix_name_lengths[yield] != 0)
962   {
963   if (len == posix_name_lengths[yield] &&
964     strncmp((const char *)ptr, posix_names[yield], len) == 0) return yield;
965   yield++;
966   }
967 return -1;
968 }
969
970
971
972
973 /*************************************************
974 *           Compile one branch                   *
975 *************************************************/
976
977 /* Scan the pattern, compiling it into the code vector.
978
979 Arguments:
980   options      the option bits
981   brackets     points to number of brackets used
982   code         points to the pointer to the current code point
983   ptrptr       points to the current pattern pointer
984   errorptr     points to pointer to error message
985   optchanged   set to the value of the last OP_OPT item compiled
986   reqchar      set to the last literal character required, else -1
987   countlits    set to count of mandatory literal characters
988   cd           contains pointers to tables
989
990 Returns:       TRUE on success
991                FALSE, with *errorptr set on error
992 */
993
994 static BOOL
995 compile_branch(int options, int *brackets, uschar **codeptr,
996   const uschar **ptrptr, const char **errorptr, int *optchanged,
997   int *reqchar, int *countlits, compile_data *cd)
998 {
999 int repeat_type, op_type;
1000 int repeat_min, repeat_max;
1001 int bravalue, length;
1002 int greedy_default, greedy_non_default;
1003 int prevreqchar;
1004 int condcount = 0;
1005 int subcountlits = 0;
1006 register int c;
1007 register uschar *code = *codeptr;
1008 uschar *tempcode;
1009 const uschar *ptr = *ptrptr;
1010 const uschar *tempptr;
1011 uschar *previous = NULL;
1012 uschar class[32];
1013
1014 /* Set up the default and non-default settings for greediness */
1015
1016 greedy_default = ((options & PCRE_UNGREEDY) != 0);
1017 greedy_non_default = greedy_default ^ 1;
1018
1019 /* Initialize no required char, and count of literals */
1020
1021 *reqchar = prevreqchar = -1;
1022 *countlits = 0;
1023
1024 /* Switch on next character until the end of the branch */
1025
1026 for (;; ptr++)
1027   {
1028   BOOL negate_class;
1029   int class_charcount;
1030   int class_lastchar;
1031   int newoptions;
1032   int condref;
1033   int subreqchar;
1034
1035   c = *ptr;
1036   if ((options & PCRE_EXTENDED) != 0)
1037     {
1038     if ((cd->ctypes[c] & ctype_space) != 0) continue;
1039     if (c == '#')
1040       {
1041       /* The space before the ; is to avoid a warning on a silly compiler
1042       on the Macintosh. */
1043       while ((c = *(++ptr)) != 0 && c != '\n') ;
1044       continue;
1045       }
1046     }
1047
1048   switch(c)
1049     {
1050     /* The branch terminates at end of string, |, or ). */
1051
1052     case 0:
1053     case '|':
1054     case ')':
1055     *codeptr = code;
1056     *ptrptr = ptr;
1057     return TRUE;
1058
1059     /* Handle single-character metacharacters */
1060
1061     case '^':
1062     previous = NULL;
1063     *code++ = OP_CIRC;
1064     break;
1065
1066     case '$':
1067     previous = NULL;
1068     *code++ = OP_DOLL;
1069     break;
1070
1071     case '.':
1072     previous = code;
1073     *code++ = OP_ANY;
1074     break;
1075
1076     /* Character classes. These always build a 32-byte bitmap of the permitted
1077     characters, except in the special case where there is only one character.
1078     For negated classes, we build the map as usual, then invert it at the end.
1079     */
1080
1081     case '[':
1082     previous = code;
1083     *code++ = OP_CLASS;
1084
1085     /* If the first character is '^', set the negation flag and skip it. */
1086
1087     if ((c = *(++ptr)) == '^')
1088       {
1089       negate_class = TRUE;
1090       c = *(++ptr);
1091       }
1092     else negate_class = FALSE;
1093
1094     /* Keep a count of chars so that we can optimize the case of just a single
1095     character. */
1096
1097     class_charcount = 0;
1098     class_lastchar = -1;
1099
1100     /* Initialize the 32-char bit map to all zeros. We have to build the
1101     map in a temporary bit of store, in case the class contains only 1
1102     character, because in that case the compiled code doesn't use the
1103     bit map. */
1104
1105     memset(class, 0, 32 * sizeof(uschar));
1106
1107     /* Process characters until ] is reached. By writing this as a "do" it
1108     means that an initial ] is taken as a data character. */
1109
1110     do
1111       {
1112       if (c == 0)
1113         {
1114         *errorptr = ERR6;
1115         goto FAILED;
1116         }
1117
1118       /* Handle POSIX class names. Perl allows a negation extension of the
1119       form [:^name]. A square bracket that doesn't match the syntax is
1120       treated as a literal. We also recognize the POSIX constructions
1121       [.ch.] and [=ch=] ("collating elements") and fault them, as Perl
1122       5.6 does. */
1123
1124       if (c == '[' &&
1125           (ptr[1] == ':' || ptr[1] == '.' || ptr[1] == '=') &&
1126           check_posix_syntax(ptr, &tempptr, cd))
1127         {
1128         BOOL local_negate = FALSE;
1129         int posix_class, i;
1130         register const uschar *cbits = cd->cbits;
1131
1132         if (ptr[1] != ':')
1133           {
1134           *errorptr = ERR31;
1135           goto FAILED;
1136           }
1137
1138         ptr += 2;
1139         if (*ptr == '^')
1140           {
1141           local_negate = TRUE;
1142           ptr++;
1143           }
1144
1145         posix_class = check_posix_name(ptr, tempptr - ptr);
1146         if (posix_class < 0)
1147           {
1148           *errorptr = ERR30;
1149           goto FAILED;
1150           }
1151
1152         /* If matching is caseless, upper and lower are converted to
1153         alpha. This relies on the fact that the class table starts with
1154         alpha, lower, upper as the first 3 entries. */
1155
1156         if ((options & PCRE_CASELESS) != 0 && posix_class <= 2)
1157           posix_class = 0;
1158
1159         /* Or into the map we are building up to 3 of the static class
1160         tables, or their negations. */
1161
1162         posix_class *= 3;
1163         for (i = 0; i < 3; i++)
1164           {
1165           int taboffset = posix_class_maps[posix_class + i];
1166           if (taboffset < 0) break;
1167           if (local_negate)
1168             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+taboffset];
1169           else
1170             for (c = 0; c < 32; c++) class[c] |= cbits[c+taboffset];
1171           }
1172
1173         ptr = tempptr + 1;
1174         class_charcount = 10;  /* Set > 1; assumes more than 1 per class */
1175         continue;
1176         }
1177
1178       /* Backslash may introduce a single character, or it may introduce one
1179       of the specials, which just set a flag. Escaped items are checked for
1180       validity in the pre-compiling pass. The sequence \b is a special case.
1181       Inside a class (and only there) it is treated as backspace. Elsewhere
1182       it marks a word boundary. Other escapes have preset maps ready to
1183       or into the one we are building. We assume they have more than one
1184       character in them, so set class_count bigger than one. */
1185
1186       if (c == '\\')
1187         {
1188         c = check_escape(&ptr, errorptr, *brackets, options, TRUE, cd);
1189         if (-c == ESC_b) c = '\b';
1190         else if (c < 0)
1191           {
1192           register const uschar *cbits = cd->cbits;
1193           class_charcount = 10;
1194           switch (-c)
1195             {
1196             case ESC_d:
1197             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_digit];
1198             continue;
1199
1200             case ESC_D:
1201             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_digit];
1202             continue;
1203
1204             case ESC_w:
1205             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_word];
1206             continue;
1207
1208             case ESC_W:
1209             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_word];
1210             continue;
1211
1212             case ESC_s:
1213             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_space];
1214             continue;
1215
1216             case ESC_S:
1217             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_space];
1218             continue;
1219
1220             default:
1221             *errorptr = ERR7;
1222             goto FAILED;
1223             }
1224           }
1225
1226         /* Fall through if single character, but don't at present allow
1227         chars > 255 in UTF-8 mode. */
1228
1229 #ifdef SUPPORT_UTF8
1230         if (c > 255)
1231           {
1232           *errorptr = ERR33;
1233           goto FAILED;
1234           }
1235 #endif
1236         }
1237
1238       /* A single character may be followed by '-' to form a range. However,
1239       Perl does not permit ']' to be the end of the range. A '-' character
1240       here is treated as a literal. */
1241
1242       if (ptr[1] == '-' && ptr[2] != ']')
1243         {
1244         int d;
1245         ptr += 2;
1246         d = *ptr;
1247
1248         if (d == 0)
1249           {
1250           *errorptr = ERR6;
1251           goto FAILED;
1252           }
1253
1254         /* The second part of a range can be a single-character escape, but
1255         not any of the other escapes. Perl 5.6 treats a hyphen as a literal
1256         in such circumstances. */
1257
1258         if (d == '\\')
1259           {
1260           const uschar *oldptr = ptr;
1261           d = check_escape(&ptr, errorptr, *brackets, options, TRUE, cd);
1262
1263 #ifdef SUPPORT_UTF8
1264           if (d > 255)
1265             {
1266             *errorptr = ERR33;
1267             goto FAILED;
1268             }
1269 #endif
1270           /* \b is backslash; any other special means the '-' was literal */
1271
1272           if (d < 0)
1273             {
1274             if (d == -ESC_b) d = '\b'; else
1275               {
1276               ptr = oldptr - 2;
1277               goto SINGLE_CHARACTER;  /* A few lines below */
1278               }
1279             }
1280           }
1281
1282         if (d < c)
1283           {
1284           *errorptr = ERR8;
1285           goto FAILED;
1286           }
1287
1288         for (; c <= d; c++)
1289           {
1290           class[c/8] |= (1 << (c&7));
1291           if ((options & PCRE_CASELESS) != 0)
1292             {
1293             int uc = cd->fcc[c];           /* flip case */
1294             class[uc/8] |= (1 << (uc&7));
1295             }
1296           class_charcount++;                /* in case a one-char range */
1297           class_lastchar = c;
1298           }
1299         continue;   /* Go get the next char in the class */
1300         }
1301
1302       /* Handle a lone single character - we can get here for a normal
1303       non-escape char, or after \ that introduces a single character. */
1304
1305       SINGLE_CHARACTER:
1306
1307       class [c/8] |= (1 << (c&7));
1308       if ((options & PCRE_CASELESS) != 0)
1309         {
1310         c = cd->fcc[c];   /* flip case */
1311         class[c/8] |= (1 << (c&7));
1312         }
1313       class_charcount++;
1314       class_lastchar = c;
1315       }
1316
1317     /* Loop until ']' reached; the check for end of string happens inside the
1318     loop. This "while" is the end of the "do" above. */
1319
1320     while ((c = *(++ptr)) != ']');
1321
1322     /* If class_charcount is 1 and class_lastchar is not negative, we saw
1323     precisely one character. This doesn't need the whole 32-byte bit map.
1324     We turn it into a 1-character OP_CHAR if it's positive, or OP_NOT if
1325     it's negative. */
1326
1327     if (class_charcount == 1 && class_lastchar >= 0)
1328       {
1329       if (negate_class)
1330         {
1331         code[-1] = OP_NOT;
1332         }
1333       else
1334         {
1335         code[-1] = OP_CHARS;
1336         *code++ = 1;
1337         }
1338       *code++ = class_lastchar;
1339       }
1340
1341     /* Otherwise, negate the 32-byte map if necessary, and copy it into
1342     the code vector. */
1343
1344     else
1345       {
1346       if (negate_class)
1347         for (c = 0; c < 32; c++) code[c] = ~class[c];
1348       else
1349         memcpy(code, class, 32);
1350       code += 32;
1351       }
1352     break;
1353
1354     /* Various kinds of repeat */
1355
1356     case '{':
1357     if (!is_counted_repeat(ptr+1, cd)) goto NORMAL_CHAR;
1358     ptr = read_repeat_counts(ptr+1, &repeat_min, &repeat_max, errorptr, cd);
1359     if (*errorptr != NULL) goto FAILED;
1360     goto REPEAT;
1361
1362     case '*':
1363     repeat_min = 0;
1364     repeat_max = -1;
1365     goto REPEAT;
1366
1367     case '+':
1368     repeat_min = 1;
1369     repeat_max = -1;
1370     goto REPEAT;
1371
1372     case '?':
1373     repeat_min = 0;
1374     repeat_max = 1;
1375
1376     REPEAT:
1377     if (previous == NULL)
1378       {
1379       *errorptr = ERR9;
1380       goto FAILED;
1381       }
1382
1383     /* If the next character is '?' this is a minimizing repeat, by default,
1384     but if PCRE_UNGREEDY is set, it works the other way round. Advance to the
1385     next character. */
1386
1387     if (ptr[1] == '?')
1388       { repeat_type = greedy_non_default; ptr++; }
1389     else repeat_type = greedy_default;
1390
1391     /* If previous was a string of characters, chop off the last one and use it
1392     as the subject of the repeat. If there was only one character, we can
1393     abolish the previous item altogether. A repeat with a zero minimum wipes
1394     out any reqchar setting, backing up to the previous value. We must also
1395     adjust the countlits value. */
1396
1397     if (*previous == OP_CHARS)
1398       {
1399       int len = previous[1];
1400
1401       if (repeat_min == 0) *reqchar = prevreqchar;
1402       *countlits += repeat_min - 1;
1403
1404       if (len == 1)
1405         {
1406         c = previous[2];
1407         code = previous;
1408         }
1409       else
1410         {
1411         c = previous[len+1];
1412         previous[1]--;
1413         code--;
1414         }
1415       op_type = 0;                 /* Use single-char op codes */
1416       goto OUTPUT_SINGLE_REPEAT;   /* Code shared with single character types */
1417       }
1418
1419     /* If previous was a single negated character ([^a] or similar), we use
1420     one of the special opcodes, replacing it. The code is shared with single-
1421     character repeats by adding a suitable offset into repeat_type. */
1422
1423     else if ((int)*previous == OP_NOT)
1424       {
1425       op_type = OP_NOTSTAR - OP_STAR;  /* Use "not" opcodes */
1426       c = previous[1];
1427       code = previous;
1428       goto OUTPUT_SINGLE_REPEAT;
1429       }
1430
1431     /* If previous was a character type match (\d or similar), abolish it and
1432     create a suitable repeat item. The code is shared with single-character
1433     repeats by adding a suitable offset into repeat_type. */
1434
1435     else if ((int)*previous < OP_EODN || *previous == OP_ANY)
1436       {
1437       op_type = OP_TYPESTAR - OP_STAR;  /* Use type opcodes */
1438       c = *previous;
1439       code = previous;
1440
1441       OUTPUT_SINGLE_REPEAT:
1442
1443       /* If the maximum is zero then the minimum must also be zero; Perl allows
1444       this case, so we do too - by simply omitting the item altogether. */
1445
1446       if (repeat_max == 0) goto END_REPEAT;
1447
1448       /* Combine the op_type with the repeat_type */
1449
1450       repeat_type += op_type;
1451
1452       /* A minimum of zero is handled either as the special case * or ?, or as
1453       an UPTO, with the maximum given. */
1454
1455       if (repeat_min == 0)
1456         {
1457         if (repeat_max == -1) *code++ = OP_STAR + repeat_type;
1458           else if (repeat_max == 1) *code++ = OP_QUERY + repeat_type;
1459         else
1460           {
1461           *code++ = OP_UPTO + repeat_type;
1462           *code++ = repeat_max >> 8;
1463           *code++ = (repeat_max & 255);
1464           }
1465         }
1466
1467       /* The case {1,} is handled as the special case + */
1468
1469       else if (repeat_min == 1 && repeat_max == -1)
1470         *code++ = OP_PLUS + repeat_type;
1471
1472       /* The case {n,n} is just an EXACT, while the general case {n,m} is
1473       handled as an EXACT followed by an UPTO. An EXACT of 1 is optimized. */
1474
1475       else
1476         {
1477         if (repeat_min != 1)
1478           {
1479           *code++ = OP_EXACT + op_type;  /* NB EXACT doesn't have repeat_type */
1480           *code++ = repeat_min >> 8;
1481           *code++ = (repeat_min & 255);
1482           }
1483
1484         /* If the mininum is 1 and the previous item was a character string,
1485         we either have to put back the item that got cancelled if the string
1486         length was 1, or add the character back onto the end of a longer
1487         string. For a character type nothing need be done; it will just get
1488         put back naturally. Note that the final character is always going to
1489         get added below. */
1490
1491         else if (*previous == OP_CHARS)
1492           {
1493           if (code == previous) code += 2; else previous[1]++;
1494           }
1495
1496         /*  For a single negated character we also have to put back the
1497         item that got cancelled. */
1498
1499         else if (*previous == OP_NOT) code++;
1500
1501         /* If the maximum is unlimited, insert an OP_STAR. */
1502
1503         if (repeat_max < 0)
1504           {
1505           *code++ = c;
1506           *code++ = OP_STAR + repeat_type;
1507           }
1508
1509         /* Else insert an UPTO if the max is greater than the min. */
1510
1511         else if (repeat_max != repeat_min)
1512           {
1513           *code++ = c;
1514           repeat_max -= repeat_min;
1515           *code++ = OP_UPTO + repeat_type;
1516           *code++ = repeat_max >> 8;
1517           *code++ = (repeat_max & 255);
1518           }
1519         }
1520
1521       /* The character or character type itself comes last in all cases. */
1522
1523       *code++ = c;
1524       }
1525
1526     /* If previous was a character class or a back reference, we put the repeat
1527     stuff after it, but just skip the item if the repeat was {0,0}. */
1528
1529     else if (*previous == OP_CLASS || *previous == OP_REF)
1530       {
1531       if (repeat_max == 0)
1532         {
1533         code = previous;
1534         goto END_REPEAT;
1535         }
1536       if (repeat_min == 0 && repeat_max == -1)
1537         *code++ = OP_CRSTAR + repeat_type;
1538       else if (repeat_min == 1 && repeat_max == -1)
1539         *code++ = OP_CRPLUS + repeat_type;
1540       else if (repeat_min == 0 && repeat_max == 1)
1541         *code++ = OP_CRQUERY + repeat_type;
1542       else
1543         {
1544         *code++ = OP_CRRANGE + repeat_type;
1545         *code++ = repeat_min >> 8;
1546         *code++ = repeat_min & 255;
1547         if (repeat_max == -1) repeat_max = 0;  /* 2-byte encoding for max */
1548         *code++ = repeat_max >> 8;
1549         *code++ = repeat_max & 255;
1550         }
1551       }
1552
1553     /* If previous was a bracket group, we may have to replicate it in certain
1554     cases. */
1555
1556     else if ((int)*previous >= OP_BRA || (int)*previous == OP_ONCE ||
1557              (int)*previous == OP_COND)
1558       {
1559       register int i;
1560       int ketoffset = 0;
1561       int len = code - previous;
1562       uschar *bralink = NULL;
1563
1564       /* If the maximum repeat count is unlimited, find the end of the bracket
1565       by scanning through from the start, and compute the offset back to it
1566       from the current code pointer. There may be an OP_OPT setting following
1567       the final KET, so we can't find the end just by going back from the code
1568       pointer. */
1569
1570       if (repeat_max == -1)
1571         {
1572         register uschar *ket = previous;
1573         do ket += (ket[1] << 8) + ket[2]; while (*ket != OP_KET);
1574         ketoffset = code - ket;
1575         }
1576
1577       /* The case of a zero minimum is special because of the need to stick
1578       OP_BRAZERO in front of it, and because the group appears once in the
1579       data, whereas in other cases it appears the minimum number of times. For
1580       this reason, it is simplest to treat this case separately, as otherwise
1581       the code gets far too mess. There are several special subcases when the
1582       minimum is zero. */
1583
1584       if (repeat_min == 0)
1585         {
1586         /* If we set up a required char from the bracket, we must back off
1587         to the previous value and reset the countlits value too. */
1588
1589         if (subcountlits > 0)
1590           {
1591           *reqchar = prevreqchar;
1592           *countlits -= subcountlits;
1593           }
1594
1595         /* If the maximum is also zero, we just omit the group from the output
1596         altogether. */
1597
1598         if (repeat_max == 0)
1599           {
1600           code = previous;
1601           goto END_REPEAT;
1602           }
1603
1604         /* If the maximum is 1 or unlimited, we just have to stick in the
1605         BRAZERO and do no more at this point. */
1606
1607         if (repeat_max <= 1)
1608           {
1609           memmove(previous+1, previous, len);
1610           code++;
1611           *previous++ = OP_BRAZERO + repeat_type;
1612           }
1613
1614         /* If the maximum is greater than 1 and limited, we have to replicate
1615         in a nested fashion, sticking OP_BRAZERO before each set of brackets.
1616         The first one has to be handled carefully because it's the original
1617         copy, which has to be moved up. The remainder can be handled by code
1618         that is common with the non-zero minimum case below. We just have to
1619         adjust the value or repeat_max, since one less copy is required. */
1620
1621         else
1622           {
1623           int offset;
1624           memmove(previous+4, previous, len);
1625           code += 4;
1626           *previous++ = OP_BRAZERO + repeat_type;
1627           *previous++ = OP_BRA;
1628
1629           /* We chain together the bracket offset fields that have to be
1630           filled in later when the ends of the brackets are reached. */
1631
1632           offset = (bralink == NULL)? 0 : previous - bralink;
1633           bralink = previous;
1634           *previous++ = offset >> 8;
1635           *previous++ = offset & 255;
1636           }
1637
1638         repeat_max--;
1639         }
1640
1641       /* If the minimum is greater than zero, replicate the group as many
1642       times as necessary, and adjust the maximum to the number of subsequent
1643       copies that we need. */
1644
1645       else
1646         {
1647         for (i = 1; i < repeat_min; i++)
1648           {
1649           memcpy(code, previous, len);
1650           code += len;
1651           }
1652         if (repeat_max > 0) repeat_max -= repeat_min;
1653         }
1654
1655       /* This code is common to both the zero and non-zero minimum cases. If
1656       the maximum is limited, it replicates the group in a nested fashion,
1657       remembering the bracket starts on a stack. In the case of a zero minimum,
1658       the first one was set up above. In all cases the repeat_max now specifies
1659       the number of additional copies needed. */
1660
1661       if (repeat_max >= 0)
1662         {
1663         for (i = repeat_max - 1; i >= 0; i--)
1664           {
1665           *code++ = OP_BRAZERO + repeat_type;
1666
1667           /* All but the final copy start a new nesting, maintaining the
1668           chain of brackets outstanding. */
1669
1670           if (i != 0)
1671             {
1672             int offset;
1673             *code++ = OP_BRA;
1674             offset = (bralink == NULL)? 0 : code - bralink;
1675             bralink = code;
1676             *code++ = offset >> 8;
1677             *code++ = offset & 255;
1678             }
1679
1680           memcpy(code, previous, len);
1681           code += len;
1682           }
1683
1684         /* Now chain through the pending brackets, and fill in their length
1685         fields (which are holding the chain links pro tem). */
1686
1687         while (bralink != NULL)
1688           {
1689           int oldlinkoffset;
1690           int offset = code - bralink + 1;
1691           uschar *bra = code - offset;
1692           oldlinkoffset = (bra[1] << 8) + bra[2];
1693           bralink = (oldlinkoffset == 0)? NULL : bralink - oldlinkoffset;
1694           *code++ = OP_KET;
1695           *code++ = bra[1] = offset >> 8;
1696           *code++ = bra[2] = (offset & 255);
1697           }
1698         }
1699
1700       /* If the maximum is unlimited, set a repeater in the final copy. We
1701       can't just offset backwards from the current code point, because we
1702       don't know if there's been an options resetting after the ket. The
1703       correct offset was computed above. */
1704
1705       else code[-ketoffset] = OP_KETRMAX + repeat_type;
1706       }
1707
1708     /* Else there's some kind of shambles */
1709
1710     else
1711       {
1712       *errorptr = ERR11;
1713       goto FAILED;
1714       }
1715
1716     /* In all case we no longer have a previous item. */
1717
1718     END_REPEAT:
1719     previous = NULL;
1720     break;
1721
1722
1723     /* Start of nested bracket sub-expression, or comment or lookahead or
1724     lookbehind or option setting or condition. First deal with special things
1725     that can come after a bracket; all are introduced by ?, and the appearance
1726     of any of them means that this is not a referencing group. They were
1727     checked for validity in the first pass over the string, so we don't have to
1728     check for syntax errors here.  */
1729
1730     case '(':
1731     newoptions = options;
1732     condref = -1;
1733
1734     if (*(++ptr) == '?')
1735       {
1736       int set, unset;
1737       int *optset;
1738
1739       switch (*(++ptr))
1740         {
1741         case '#':                 /* Comment; skip to ket */
1742         ptr++;
1743         while (*ptr != ')') ptr++;
1744         continue;
1745
1746         case ':':                 /* Non-extracting bracket */
1747         bravalue = OP_BRA;
1748         ptr++;
1749         break;
1750
1751         case '(':
1752         bravalue = OP_COND;       /* Conditional group */
1753         if ((cd->ctypes[*(++ptr)] & ctype_digit) != 0)
1754           {
1755           condref = *ptr - '0';
1756           while (*(++ptr) != ')') condref = condref*10 + *ptr - '0';
1757           if (condref == 0)
1758             {
1759             *errorptr = ERR35;
1760             goto FAILED;
1761             }
1762           ptr++;
1763           }
1764         else ptr--;
1765         break;
1766
1767         case '=':                 /* Positive lookahead */
1768         bravalue = OP_ASSERT;
1769         ptr++;
1770         break;
1771
1772         case '!':                 /* Negative lookahead */
1773         bravalue = OP_ASSERT_NOT;
1774         ptr++;
1775         break;
1776
1777         case '<':                 /* Lookbehinds */
1778         switch (*(++ptr))
1779           {
1780           case '=':               /* Positive lookbehind */
1781           bravalue = OP_ASSERTBACK;
1782           ptr++;
1783           break;
1784
1785           case '!':               /* Negative lookbehind */
1786           bravalue = OP_ASSERTBACK_NOT;
1787           ptr++;
1788           break;
1789
1790           default:                /* Syntax error */
1791           *errorptr = ERR24;
1792           goto FAILED;
1793           }
1794         break;
1795
1796         case '>':                 /* One-time brackets */
1797         bravalue = OP_ONCE;
1798         ptr++;
1799         break;
1800
1801         case 'R':                 /* Pattern recursion */
1802         *code++ = OP_RECURSE;
1803         ptr++;
1804         continue;
1805
1806         default:                  /* Option setting */
1807         set = unset = 0;
1808         optset = &set;
1809
1810         while (*ptr != ')' && *ptr != ':')
1811           {
1812           switch (*ptr++)
1813             {
1814             case '-': optset = &unset; break;
1815
1816             case 'i': *optset |= PCRE_CASELESS; break;
1817             case 'm': *optset |= PCRE_MULTILINE; break;
1818             case 's': *optset |= PCRE_DOTALL; break;
1819             case 'x': *optset |= PCRE_EXTENDED; break;
1820             case 'U': *optset |= PCRE_UNGREEDY; break;
1821             case 'X': *optset |= PCRE_EXTRA; break;
1822
1823             default:
1824             *errorptr = ERR12;
1825             goto FAILED;
1826             }
1827           }
1828
1829         /* Set up the changed option bits, but don't change anything yet. */
1830
1831         newoptions = (options | set) & (~unset);
1832
1833         /* If the options ended with ')' this is not the start of a nested
1834         group with option changes, so the options change at this level. At top
1835         level there is nothing else to be done (the options will in fact have
1836         been set from the start of compiling as a result of the first pass) but
1837         at an inner level we must compile code to change the ims options if
1838         necessary, and pass the new setting back so that it can be put at the
1839         start of any following branches, and when this group ends, a resetting
1840         item can be compiled. */
1841
1842         if (*ptr == ')')
1843           {
1844           if ((options & PCRE_INGROUP) != 0 &&
1845               (options & PCRE_IMS) != (newoptions & PCRE_IMS))
1846             {
1847             *code++ = OP_OPT;
1848             *code++ = *optchanged = newoptions & PCRE_IMS;
1849             }
1850           options = newoptions;  /* Change options at this level */
1851           previous = NULL;       /* This item can't be repeated */
1852           continue;              /* It is complete */
1853           }
1854
1855         /* If the options ended with ':' we are heading into a nested group
1856         with possible change of options. Such groups are non-capturing and are
1857         not assertions of any kind. All we need to do is skip over the ':';
1858         the newoptions value is handled below. */
1859
1860         bravalue = OP_BRA;
1861         ptr++;
1862         }
1863       }
1864
1865     /* Else we have a referencing group; adjust the opcode. */
1866
1867     else
1868       {
1869       if (++(*brackets) > EXTRACT_MAX)
1870         {
1871         *errorptr = ERR13;
1872         goto FAILED;
1873         }
1874       bravalue = OP_BRA + *brackets;
1875       }
1876
1877     /* Process nested bracketed re. Assertions may not be repeated, but other
1878     kinds can be. We copy code into a non-register variable in order to be able
1879     to pass its address because some compilers complain otherwise. Pass in a
1880     new setting for the ims options if they have changed. */
1881
1882     previous = (bravalue >= OP_ONCE)? code : NULL;
1883     *code = bravalue;
1884     tempcode = code;
1885
1886     if (!compile_regex(
1887          options | PCRE_INGROUP,       /* Set for all nested groups */
1888          ((options & PCRE_IMS) != (newoptions & PCRE_IMS))?
1889            newoptions & PCRE_IMS : -1, /* Pass ims options if changed */
1890          brackets,                     /* Bracket level */
1891          &tempcode,                    /* Where to put code (updated) */
1892          &ptr,                         /* Input pointer (updated) */
1893          errorptr,                     /* Where to put an error message */
1894          (bravalue == OP_ASSERTBACK ||
1895           bravalue == OP_ASSERTBACK_NOT), /* TRUE if back assert */
1896          condref,                      /* Condition reference number */
1897          &subreqchar,                  /* For possible last char */
1898          &subcountlits,                /* For literal count */
1899          cd))                          /* Tables block */
1900       goto FAILED;
1901
1902     /* At the end of compiling, code is still pointing to the start of the
1903     group, while tempcode has been updated to point past the end of the group
1904     and any option resetting that may follow it. The pattern pointer (ptr)
1905     is on the bracket. */
1906
1907     /* If this is a conditional bracket, check that there are no more than
1908     two branches in the group. */
1909
1910     if (bravalue == OP_COND)
1911       {
1912       uschar *tc = code;
1913       condcount = 0;
1914
1915       do {
1916          condcount++;
1917          tc += (tc[1] << 8) | tc[2];
1918          }
1919       while (*tc != OP_KET);
1920
1921       if (condcount > 2)
1922         {
1923         *errorptr = ERR27;
1924         goto FAILED;
1925         }
1926       }
1927
1928     /* Handle updating of the required character. If the subpattern didn't
1929     set one, leave it as it was. Otherwise, update it for normal brackets of
1930     all kinds, forward assertions, and conditions with two branches. Don't
1931     update the literal count for forward assertions, however. If the bracket
1932     is followed by a quantifier with zero repeat, we have to back off. Hence
1933     the definition of prevreqchar and subcountlits outside the main loop so
1934     that they can be accessed for the back off. */
1935
1936     if (subreqchar > 0 &&
1937          (bravalue >= OP_BRA || bravalue == OP_ONCE || bravalue == OP_ASSERT ||
1938          (bravalue == OP_COND && condcount == 2)))
1939       {
1940       prevreqchar = *reqchar;
1941       *reqchar = subreqchar;
1942       if (bravalue != OP_ASSERT) *countlits += subcountlits;
1943       }
1944
1945     /* Now update the main code pointer to the end of the group. */
1946
1947     code = tempcode;
1948
1949     /* Error if hit end of pattern */
1950
1951     if (*ptr != ')')
1952       {
1953       *errorptr = ERR14;
1954       goto FAILED;
1955       }
1956     break;
1957
1958     /* Check \ for being a real metacharacter; if not, fall through and handle
1959     it as a data character at the start of a string. Escape items are checked
1960     for validity in the pre-compiling pass. */
1961
1962     case '\\':
1963     tempptr = ptr;
1964     c = check_escape(&ptr, errorptr, *brackets, options, FALSE, cd);
1965
1966     /* Handle metacharacters introduced by \. For ones like \d, the ESC_ values
1967     are arranged to be the negation of the corresponding OP_values. For the
1968     back references, the values are ESC_REF plus the reference number. Only
1969     back references and those types that consume a character may be repeated.
1970     We can test for values between ESC_b and ESC_Z for the latter; this may
1971     have to change if any new ones are ever created. */
1972
1973     if (c < 0)
1974       {
1975       if (-c >= ESC_REF)
1976         {
1977         previous = code;
1978         *code++ = OP_REF;
1979         *code++ = -c - ESC_REF;
1980         }
1981       else
1982         {
1983         previous = (-c > ESC_b && -c < ESC_Z)? code : NULL;
1984         *code++ = -c;
1985         }
1986       continue;
1987       }
1988
1989     /* Data character: reset and fall through */
1990
1991     ptr = tempptr;
1992     c = '\\';
1993
1994     /* Handle a run of data characters until a metacharacter is encountered.
1995     The first character is guaranteed not to be whitespace or # when the
1996     extended flag is set. */
1997
1998     NORMAL_CHAR:
1999     default:
2000     previous = code;
2001     *code = OP_CHARS;
2002     code += 2;
2003     length = 0;
2004
2005     do
2006       {
2007       if ((options & PCRE_EXTENDED) != 0)
2008         {
2009         if ((cd->ctypes[c] & ctype_space) != 0) continue;
2010         if (c == '#')
2011           {
2012           /* The space before the ; is to avoid a warning on a silly compiler
2013           on the Macintosh. */
2014           while ((c = *(++ptr)) != 0 && c != '\n') ;
2015           if (c == 0) break;
2016           continue;
2017           }
2018         }
2019
2020       /* Backslash may introduce a data char or a metacharacter. Escaped items
2021       are checked for validity in the pre-compiling pass. Stop the string
2022       before a metaitem. */
2023
2024       if (c == '\\')
2025         {
2026         tempptr = ptr;
2027         c = check_escape(&ptr, errorptr, *brackets, options, FALSE, cd);
2028         if (c < 0) { ptr = tempptr; break; }
2029
2030         /* If a character is > 127 in UTF-8 mode, we have to turn it into
2031         two or more characters in the UTF-8 encoding. */
2032
2033 #ifdef SUPPORT_UTF8
2034         if (c > 127 && (options & PCRE_UTF8) != 0)
2035           {
2036           uschar buffer[8];
2037           int len = ord2utf8(c, buffer);
2038           for (c = 0; c < len; c++) *code++ = buffer[c];
2039           length += len;
2040           continue;
2041           }
2042 #endif
2043         }
2044
2045       /* Ordinary character or single-char escape */
2046
2047       *code++ = c;
2048       length++;
2049       }
2050
2051     /* This "while" is the end of the "do" above. */
2052
2053     while (length < MAXLIT && (cd->ctypes[c = *(++ptr)] & ctype_meta) == 0);
2054
2055     /* Update the last character and the count of literals */
2056
2057     prevreqchar = (length > 1)? code[-2] : *reqchar;
2058     *reqchar = code[-1];
2059     *countlits += length;
2060
2061     /* Compute the length and set it in the data vector, and advance to
2062     the next state. */
2063
2064     previous[1] = length;
2065     if (length < MAXLIT) ptr--;
2066     break;
2067     }
2068   }                   /* end of big loop */
2069
2070 /* Control never reaches here by falling through, only by a goto for all the
2071 error states. Pass back the position in the pattern so that it can be displayed
2072 to the user for diagnosing the error. */
2073
2074 FAILED:
2075 *ptrptr = ptr;
2076 return FALSE;
2077 }
2078
2079
2080
2081
2082 /*************************************************
2083 *     Compile sequence of alternatives           *
2084 *************************************************/
2085
2086 /* On entry, ptr is pointing past the bracket character, but on return
2087 it points to the closing bracket, or vertical bar, or end of string.
2088 The code variable is pointing at the byte into which the BRA operator has been
2089 stored. If the ims options are changed at the start (for a (?ims: group) or
2090 during any branch, we need to insert an OP_OPT item at the start of every
2091 following branch to ensure they get set correctly at run time, and also pass
2092 the new options into every subsequent branch compile.
2093
2094 Argument:
2095   options     the option bits
2096   optchanged  new ims options to set as if (?ims) were at the start, or -1
2097                for no change
2098   brackets    -> int containing the number of extracting brackets used
2099   codeptr     -> the address of the current code pointer
2100   ptrptr      -> the address of the current pattern pointer
2101   errorptr    -> pointer to error message
2102   lookbehind  TRUE if this is a lookbehind assertion
2103   condref     >= 0 for OPT_CREF setting at start of conditional group
2104   reqchar     -> place to put the last required character, or a negative number
2105   countlits   -> place to put the shortest literal count of any branch
2106   cd          points to the data block with tables pointers
2107
2108 Returns:      TRUE on success
2109 */
2110
2111 static BOOL
2112 compile_regex(int options, int optchanged, int *brackets, uschar **codeptr,
2113   const uschar **ptrptr, const char **errorptr, BOOL lookbehind, int condref,
2114   int *reqchar, int *countlits, compile_data *cd)
2115 {
2116 const uschar *ptr = *ptrptr;
2117 uschar *code = *codeptr;
2118 uschar *last_branch = code;
2119 uschar *start_bracket = code;
2120 uschar *reverse_count = NULL;
2121 int oldoptions = options & PCRE_IMS;
2122 int branchreqchar, branchcountlits;
2123
2124 *reqchar = -1;
2125 *countlits = INT_MAX;
2126 code += 3;
2127
2128 /* At the start of a reference-based conditional group, insert the reference
2129 number as an OP_CREF item. */
2130
2131 if (condref >= 0)
2132   {
2133   *code++ = OP_CREF;
2134   *code++ = condref;
2135   }
2136
2137 /* Loop for each alternative branch */
2138
2139 for (;;)
2140   {
2141   int length;
2142
2143   /* Handle change of options */
2144
2145   if (optchanged >= 0)
2146     {
2147     *code++ = OP_OPT;
2148     *code++ = optchanged;
2149     options = (options & ~PCRE_IMS) | optchanged;
2150     }
2151
2152   /* Set up dummy OP_REVERSE if lookbehind assertion */
2153
2154   if (lookbehind)
2155     {
2156     *code++ = OP_REVERSE;
2157     reverse_count = code;
2158     *code++ = 0;
2159     *code++ = 0;
2160     }
2161
2162   /* Now compile the branch */
2163
2164   if (!compile_branch(options, brackets, &code, &ptr, errorptr, &optchanged,
2165       &branchreqchar, &branchcountlits, cd))
2166     {
2167     *ptrptr = ptr;
2168     return FALSE;
2169     }
2170
2171   /* Fill in the length of the last branch */
2172
2173   length = code - last_branch;
2174   last_branch[1] = length >> 8;
2175   last_branch[2] = length & 255;
2176
2177   /* Save the last required character if all branches have the same; a current
2178   value of -1 means unset, while -2 means "previous branch had no last required
2179   char".  */
2180
2181   if (*reqchar != -2)
2182     {
2183     if (branchreqchar >= 0)
2184       {
2185       if (*reqchar == -1) *reqchar = branchreqchar;
2186       else if (*reqchar != branchreqchar) *reqchar = -2;
2187       }
2188     else *reqchar = -2;
2189     }
2190
2191   /* Keep the shortest literal count */
2192
2193   if (branchcountlits < *countlits) *countlits = branchcountlits;
2194   DPRINTF(("literal count = %d min=%d\n", branchcountlits, *countlits));
2195
2196   /* If lookbehind, check that this branch matches a fixed-length string,
2197   and put the length into the OP_REVERSE item. Temporarily mark the end of
2198   the branch with OP_END. */
2199
2200   if (lookbehind)
2201     {
2202     *code = OP_END;
2203     length = find_fixedlength(last_branch, options);
2204     DPRINTF(("fixed length = %d\n", length));
2205     if (length < 0)
2206       {
2207       *errorptr = ERR25;
2208       *ptrptr = ptr;
2209       return FALSE;
2210       }
2211     reverse_count[0] = (length >> 8);
2212     reverse_count[1] = length & 255;
2213     }
2214
2215   /* Reached end of expression, either ')' or end of pattern. Insert a
2216   terminating ket and the length of the whole bracketed item, and return,
2217   leaving the pointer at the terminating char. If any of the ims options
2218   were changed inside the group, compile a resetting op-code following. */
2219
2220   if (*ptr != '|')
2221     {
2222     length = code - start_bracket;
2223     *code++ = OP_KET;
2224     *code++ = length >> 8;
2225     *code++ = length & 255;
2226     if (optchanged >= 0)
2227       {
2228       *code++ = OP_OPT;
2229       *code++ = oldoptions;
2230       }
2231     *codeptr = code;
2232     *ptrptr = ptr;
2233     return TRUE;
2234     }
2235
2236   /* Another branch follows; insert an "or" node and advance the pointer. */
2237
2238   *code = OP_ALT;
2239   last_branch = code;
2240   code += 3;
2241   ptr++;
2242   }
2243 /* Control never reaches here */
2244 }
2245
2246
2247
2248
2249 /*************************************************
2250 *      Find first significant op code            *
2251 *************************************************/
2252
2253 /* This is called by several functions that scan a compiled expression looking
2254 for a fixed first character, or an anchoring op code etc. It skips over things
2255 that do not influence this. For one application, a change of caseless option is
2256 important.
2257
2258 Arguments:
2259   code       pointer to the start of the group
2260   options    pointer to external options
2261   optbit     the option bit whose changing is significant, or
2262              zero if none are
2263   optstop    TRUE to return on option change, otherwise change the options
2264                value and continue
2265
2266 Returns:     pointer to the first significant opcode
2267 */
2268
2269 static const uschar*
2270 first_significant_code(const uschar *code, int *options, int optbit,
2271   BOOL optstop)
2272 {
2273 for (;;)
2274   {
2275   switch ((int)*code)
2276     {
2277     case OP_OPT:
2278     if (optbit > 0 && ((int)code[1] & optbit) != (*options & optbit))
2279       {
2280       if (optstop) return code;
2281       *options = (int)code[1];
2282       }
2283     code += 2;
2284     break;
2285
2286     case OP_CREF:
2287     code += 2;
2288     break;
2289
2290     case OP_WORD_BOUNDARY:
2291     case OP_NOT_WORD_BOUNDARY:
2292     code++;
2293     break;
2294
2295     case OP_ASSERT_NOT:
2296     case OP_ASSERTBACK:
2297     case OP_ASSERTBACK_NOT:
2298     do code += (code[1] << 8) + code[2]; while (*code == OP_ALT);
2299     code += 3;
2300     break;
2301
2302     default:
2303     return code;
2304     }
2305   }
2306 /* Control never reaches here */
2307 }
2308
2309
2310
2311
2312 /*************************************************
2313 *          Check for anchored expression         *
2314 *************************************************/
2315
2316 /* Try to find out if this is an anchored regular expression. Consider each
2317 alternative branch. If they all start with OP_SOD or OP_CIRC, or with a bracket
2318 all of whose alternatives start with OP_SOD or OP_CIRC (recurse ad lib), then
2319 it's anchored. However, if this is a multiline pattern, then only OP_SOD
2320 counts, since OP_CIRC can match in the middle.
2321
2322 A branch is also implicitly anchored if it starts with .* and DOTALL is set,
2323 because that will try the rest of the pattern at all possible matching points,
2324 so there is no point trying them again.
2325
2326 Arguments:
2327   code       points to start of expression (the bracket)
2328   options    points to the options setting
2329
2330 Returns:     TRUE or FALSE
2331 */
2332
2333 static BOOL
2334 is_anchored(register const uschar *code, int *options)
2335 {
2336 do {
2337    const uschar *scode = first_significant_code(code + 3, options,
2338      PCRE_MULTILINE, FALSE);
2339    register int op = *scode;
2340    if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
2341      { if (!is_anchored(scode, options)) return FALSE; }
2342    else if ((op == OP_TYPESTAR || op == OP_TYPEMINSTAR) &&
2343             (*options & PCRE_DOTALL) != 0)
2344      { if (scode[1] != OP_ANY) return FALSE; }
2345    else if (op != OP_SOD &&
2346            ((*options & PCRE_MULTILINE) != 0 || op != OP_CIRC))
2347      return FALSE;
2348    code += (code[1] << 8) + code[2];
2349    }
2350 while (*code == OP_ALT);
2351 return TRUE;
2352 }
2353
2354
2355
2356 /*************************************************
2357 *         Check for starting with ^ or .*        *
2358 *************************************************/
2359
2360 /* This is called to find out if every branch starts with ^ or .* so that
2361 "first char" processing can be done to speed things up in multiline
2362 matching and for non-DOTALL patterns that start with .* (which must start at
2363 the beginning or after \n).
2364
2365 Argument:  points to start of expression (the bracket)
2366 Returns:   TRUE or FALSE
2367 */
2368
2369 static BOOL
2370 is_startline(const uschar *code)
2371 {
2372 do {
2373    const uschar *scode = first_significant_code(code + 3, NULL, 0, FALSE);
2374    register int op = *scode;
2375    if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
2376      { if (!is_startline(scode)) return FALSE; }
2377    else if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR)
2378      { if (scode[1] != OP_ANY) return FALSE; }
2379    else if (op != OP_CIRC) return FALSE;
2380    code += (code[1] << 8) + code[2];
2381    }
2382 while (*code == OP_ALT);
2383 return TRUE;
2384 }
2385
2386
2387
2388 /*************************************************
2389 *          Check for fixed first char            *
2390 *************************************************/
2391
2392 /* Try to find out if there is a fixed first character. This is called for
2393 unanchored expressions, as it speeds up their processing quite considerably.
2394 Consider each alternative branch. If they all start with the same char, or with
2395 a bracket all of whose alternatives start with the same char (recurse ad lib),
2396 then we return that char, otherwise -1.
2397
2398 Arguments:
2399   code       points to start of expression (the bracket)
2400   options    pointer to the options (used to check casing changes)
2401
2402 Returns:     -1 or the fixed first char
2403 */
2404
2405 static int
2406 find_firstchar(const uschar *code, int *options)
2407 {
2408 register int c = -1;
2409 do {
2410    int d;
2411    const uschar *scode = first_significant_code(code + 3, options,
2412      PCRE_CASELESS, TRUE);
2413    register int op = *scode;
2414
2415    if (op >= OP_BRA) op = OP_BRA;
2416
2417    switch(op)
2418      {
2419      default:
2420      return -1;
2421
2422      case OP_BRA:
2423      case OP_ASSERT:
2424      case OP_ONCE:
2425      case OP_COND:
2426      if ((d = find_firstchar(scode, options)) < 0) return -1;
2427      if (c < 0) c = d; else if (c != d) return -1;
2428      break;
2429
2430      case OP_EXACT:       /* Fall through */
2431      scode++;
2432
2433      case OP_CHARS:       /* Fall through */
2434      scode++;
2435
2436      case OP_PLUS:
2437      case OP_MINPLUS:
2438      if (c < 0) c = scode[1]; else if (c != scode[1]) return -1;
2439      break;
2440      }
2441
2442    code += (code[1] << 8) + code[2];
2443    }
2444 while (*code == OP_ALT);
2445 return c;
2446 }
2447
2448
2449
2450
2451
2452 /*************************************************
2453 *        Compile a Regular Expression            *
2454 *************************************************/
2455
2456 /* This function takes a string and returns a pointer to a block of store
2457 holding a compiled version of the expression.
2458
2459 Arguments:
2460   pattern      the regular expression
2461   options      various option bits
2462   errorptr     pointer to pointer to error text
2463   erroroffset  ptr offset in pattern where error was detected
2464   tables       pointer to character tables or NULL
2465
2466 Returns:       pointer to compiled data block, or NULL on error,
2467                with errorptr and erroroffset set
2468 */
2469
2470 pcre *
2471 pcre_compile(const char *pattern, int options, const char **errorptr,
2472   int *erroroffset, const unsigned char *tables)
2473 {
2474 real_pcre *re;
2475 int length = 3;      /* For initial BRA plus length */
2476 int runlength;
2477 int c, reqchar, countlits;
2478 int bracount = 0;
2479 int top_backref = 0;
2480 int branch_extra = 0;
2481 int branch_newextra;
2482 unsigned int brastackptr = 0;
2483 size_t size;
2484 uschar *code;
2485 const uschar *ptr;
2486 compile_data compile_block;
2487 int brastack[BRASTACK_SIZE];
2488 uschar bralenstack[BRASTACK_SIZE];
2489 const size_t pattern_length = strlen(pattern);
2490
2491 #ifdef DEBUG
2492 uschar *code_base, *code_end;
2493 #endif
2494
2495 /* Can't support UTF8 unless PCRE has been compiled to include the code. */
2496
2497 #ifndef SUPPORT_UTF8
2498 if ((options & PCRE_UTF8) != 0)
2499   {
2500   *errorptr = ERR32;
2501   return NULL;
2502   }
2503 #endif
2504
2505 /* We can't pass back an error message if errorptr is NULL; I guess the best we
2506 can do is just return NULL. */
2507
2508 if (errorptr == NULL) return NULL;
2509 *errorptr = NULL;
2510
2511 /* However, we can give a message for this error */
2512
2513 if (erroroffset == NULL)
2514   {
2515   *errorptr = ERR16;
2516   return NULL;
2517   }
2518 *erroroffset = 0;
2519
2520 if ((options & ~PUBLIC_OPTIONS) != 0)
2521   {
2522   *errorptr = ERR17;
2523   return NULL;
2524   }
2525
2526 /* Set up pointers to the individual character tables */
2527
2528 if (tables == NULL) tables = pcre_default_tables;
2529 compile_block.lcc = tables + lcc_offset;
2530 compile_block.fcc = tables + fcc_offset;
2531 compile_block.cbits = tables + cbits_offset;
2532 compile_block.ctypes = tables + ctypes_offset;
2533
2534 /* Reflect pattern for debugging output */
2535
2536 DPRINTF(("------------------------------------------------------------------\n"));
2537 DPRINTF(("%s\n", pattern));
2538
2539 /* The first thing to do is to make a pass over the pattern to compute the
2540 amount of store required to hold the compiled code. This does not have to be
2541 perfect as long as errors are overestimates. At the same time we can detect any
2542 internal flag settings. Make an attempt to correct for any counted white space
2543 if an "extended" flag setting appears late in the pattern. We can't be so
2544 clever for #-comments. */
2545
2546 ptr = (const uschar *)(pattern - 1);
2547 while ((c = *(++ptr)) != 0)
2548   {
2549   int min, max;
2550   int class_charcount;
2551
2552   if ((options & PCRE_EXTENDED) != 0)
2553     {
2554     if ((compile_block.ctypes[c] & ctype_space) != 0) continue;
2555     if (c == '#')
2556       {
2557       /* The space before the ; is to avoid a warning on a silly compiler
2558       on the Macintosh. */
2559       while ((c = *(++ptr)) != 0 && c != '\n') ;
2560       continue;
2561       }
2562     }
2563
2564   switch(c)
2565     {
2566     /* A backslashed item may be an escaped "normal" character or a
2567     character type. For a "normal" character, put the pointers and
2568     character back so that tests for whitespace etc. in the input
2569     are done correctly. */
2570
2571     case '\\':
2572       {
2573       const uschar *save_ptr = ptr;
2574       c = check_escape(&ptr, errorptr, bracount, options, FALSE, &compile_block);
2575       if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2576       if (c >= 0)
2577         {
2578         ptr = save_ptr;
2579         c = '\\';
2580         goto NORMAL_CHAR;
2581         }
2582       }
2583     length++;
2584
2585     /* A back reference needs an additional char, plus either one or 5
2586     bytes for a repeat. We also need to keep the value of the highest
2587     back reference. */
2588
2589     if (c <= -ESC_REF)
2590       {
2591       int refnum = -c - ESC_REF;
2592       if (refnum > top_backref) top_backref = refnum;
2593       length++;   /* For single back reference */
2594       if (ptr[1] == '{' && is_counted_repeat(ptr+2, &compile_block))
2595         {
2596         ptr = read_repeat_counts(ptr+2, &min, &max, errorptr, &compile_block);
2597         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2598         if ((min == 0 && (max == 1 || max == -1)) ||
2599           (min == 1 && max == -1))
2600             length++;
2601         else length += 5;
2602         if (ptr[1] == '?') ptr++;
2603         }
2604       }
2605     continue;
2606
2607     case '^':
2608     case '.':
2609     case '$':
2610     case '*':     /* These repeats won't be after brackets; */
2611     case '+':     /* those are handled separately */
2612     case '?':
2613     length++;
2614     continue;
2615
2616     /* This covers the cases of repeats after a single char, metachar, class,
2617     or back reference. */
2618
2619     case '{':
2620     if (!is_counted_repeat(ptr+1, &compile_block)) goto NORMAL_CHAR;
2621     ptr = read_repeat_counts(ptr+1, &min, &max, errorptr, &compile_block);
2622     if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2623     if ((min == 0 && (max == 1 || max == -1)) ||
2624       (min == 1 && max == -1))
2625         length++;
2626     else
2627       {
2628       length--;   /* Uncount the original char or metachar */
2629       if (min == 1) length++; else if (min > 0) length += 4;
2630       if (max > 0) length += 4; else length += 2;
2631       }
2632     if (ptr[1] == '?') ptr++;
2633     continue;
2634
2635     /* An alternation contains an offset to the next branch or ket. If any ims
2636     options changed in the previous branch(es), and/or if we are in a
2637     lookbehind assertion, extra space will be needed at the start of the
2638     branch. This is handled by branch_extra. */
2639
2640     case '|':
2641     length += 3 + branch_extra;
2642     continue;
2643
2644     /* A character class uses 33 characters. Don't worry about character types
2645     that aren't allowed in classes - they'll get picked up during the compile.
2646     A character class that contains only one character uses 2 or 3 bytes,
2647     depending on whether it is negated or not. Notice this where we can. */
2648
2649     case '[':
2650     class_charcount = 0;
2651     if (*(++ptr) == '^') ptr++;
2652     do
2653       {
2654       if (*ptr == '\\')
2655         {
2656         int ch = check_escape(&ptr, errorptr, bracount, options, TRUE,
2657           &compile_block);
2658         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2659         if (-ch == ESC_b) class_charcount++; else class_charcount = 10;
2660         }
2661       else class_charcount++;
2662       ptr++;
2663       }
2664     while (*ptr != 0 && *ptr != ']');
2665
2666     /* Repeats for negated single chars are handled by the general code */
2667
2668     if (class_charcount == 1) length += 3; else
2669       {
2670       length += 33;
2671
2672       /* A repeat needs either 1 or 5 bytes. */
2673
2674       if (*ptr != 0 && ptr[1] == '{' && is_counted_repeat(ptr+2, &compile_block))
2675         {
2676         ptr = read_repeat_counts(ptr+2, &min, &max, errorptr, &compile_block);
2677         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2678         if ((min == 0 && (max == 1 || max == -1)) ||
2679           (min == 1 && max == -1))
2680             length++;
2681         else length += 5;
2682         if (ptr[1] == '?') ptr++;
2683         }
2684       }
2685     continue;
2686
2687     /* Brackets may be genuine groups or special things */
2688
2689     case '(':
2690     branch_newextra = 0;
2691
2692     /* Handle special forms of bracket, which all start (? */
2693
2694     if (ptr[1] == '?')
2695       {
2696       int set, unset;
2697       int *optset;
2698
2699       switch (c = ptr[2])
2700         {
2701         /* Skip over comments entirely */
2702         case '#':
2703         ptr += 3;
2704         while (*ptr != 0 && *ptr != ')') ptr++;
2705         if (*ptr == 0)
2706           {
2707           *errorptr = ERR18;
2708           goto PCRE_ERROR_RETURN;
2709           }
2710         continue;
2711
2712         /* Non-referencing groups and lookaheads just move the pointer on, and
2713         then behave like a non-special bracket, except that they don't increment
2714         the count of extracting brackets. Ditto for the "once only" bracket,
2715         which is in Perl from version 5.005. */
2716
2717         case ':':
2718         case '=':
2719         case '!':
2720         case '>':
2721         ptr += 2;
2722         break;
2723
2724         /* A recursive call to the regex is an extension, to provide the
2725         facility which can be obtained by $(?p{perl-code}) in Perl 5.6. */
2726
2727         case 'R':
2728         if (ptr[3] != ')')
2729           {
2730           *errorptr = ERR29;
2731           goto PCRE_ERROR_RETURN;
2732           }
2733         ptr += 3;
2734         length += 1;
2735         break;
2736
2737         /* Lookbehinds are in Perl from version 5.005 */
2738
2739         case '<':
2740         if (ptr[3] == '=' || ptr[3] == '!')
2741           {
2742           ptr += 3;
2743           branch_newextra = 3;
2744           length += 3;         /* For the first branch */
2745           break;
2746           }
2747         *errorptr = ERR24;
2748         goto PCRE_ERROR_RETURN;
2749
2750         /* Conditionals are in Perl from version 5.005. The bracket must either
2751         be followed by a number (for bracket reference) or by an assertion
2752         group. */
2753
2754         case '(':
2755         if ((compile_block.ctypes[ptr[3]] & ctype_digit) != 0)
2756           {
2757           ptr += 4;
2758           length += 2;
2759           while ((compile_block.ctypes[*ptr] & ctype_digit) != 0) ptr++;
2760           if (*ptr != ')')
2761             {
2762             *errorptr = ERR26;
2763             goto PCRE_ERROR_RETURN;
2764             }
2765           }
2766         else   /* An assertion must follow */
2767           {
2768           ptr++;   /* Can treat like ':' as far as spacing is concerned */
2769           if (ptr[2] != '?' ||
2770              (ptr[3] != '=' && ptr[3] != '!' && ptr[3] != '<') )
2771             {
2772             ptr += 2;    /* To get right offset in message */
2773             *errorptr = ERR28;
2774             goto PCRE_ERROR_RETURN;
2775             }
2776           }
2777         break;
2778
2779         /* Else loop checking valid options until ) is met. Anything else is an
2780         error. If we are without any brackets, i.e. at top level, the settings
2781         act as if specified in the options, so massage the options immediately.
2782         This is for backward compatibility with Perl 5.004. */
2783
2784         default:
2785         set = unset = 0;
2786         optset = &set;
2787         ptr += 2;
2788
2789         for (;; ptr++)
2790           {
2791           c = *ptr;
2792           switch (c)
2793             {
2794             case 'i':
2795             *optset |= PCRE_CASELESS;
2796             continue;
2797
2798             case 'm':
2799             *optset |= PCRE_MULTILINE;
2800             continue;
2801
2802             case 's':
2803             *optset |= PCRE_DOTALL;
2804             continue;
2805
2806             case 'x':
2807             *optset |= PCRE_EXTENDED;
2808             continue;
2809
2810             case 'X':
2811             *optset |= PCRE_EXTRA;
2812             continue;
2813
2814             case 'U':
2815             *optset |= PCRE_UNGREEDY;
2816             continue;
2817
2818             case '-':
2819             optset = &unset;
2820             continue;
2821
2822             /* A termination by ')' indicates an options-setting-only item;
2823             this is global at top level; otherwise nothing is done here and
2824             it is handled during the compiling process on a per-bracket-group
2825             basis. */
2826
2827             case ')':
2828             if (brastackptr == 0)
2829               {
2830               options = (options | set) & (~unset);
2831               set = unset = 0;     /* To save length */
2832               }
2833             /* Fall through */
2834
2835             /* A termination by ':' indicates the start of a nested group with
2836             the given options set. This is again handled at compile time, but
2837             we must allow for compiled space if any of the ims options are
2838             set. We also have to allow for resetting space at the end of
2839             the group, which is why 4 is added to the length and not just 2.
2840             If there are several changes of options within the same group, this
2841             will lead to an over-estimate on the length, but this shouldn't
2842             matter very much. We also have to allow for resetting options at
2843             the start of any alternations, which we do by setting
2844             branch_newextra to 2. Finally, we record whether the case-dependent
2845             flag ever changes within the regex. This is used by the "required
2846             character" code. */
2847
2848             case ':':
2849             if (((set|unset) & PCRE_IMS) != 0)
2850               {
2851               length += 4;
2852               branch_newextra = 2;
2853               if (((set|unset) & PCRE_CASELESS) != 0) options |= PCRE_ICHANGED;
2854               }
2855             goto END_OPTIONS;
2856
2857             /* Unrecognized option character */
2858
2859             default:
2860             *errorptr = ERR12;
2861             goto PCRE_ERROR_RETURN;
2862             }
2863           }
2864
2865         /* If we hit a closing bracket, that's it - this is a freestanding
2866         option-setting. We need to ensure that branch_extra is updated if
2867         necessary. The only values branch_newextra can have here are 0 or 2.
2868         If the value is 2, then branch_extra must either be 2 or 5, depending
2869         on whether this is a lookbehind group or not. */
2870
2871         END_OPTIONS:
2872         if (c == ')')
2873           {
2874           if (branch_newextra == 2 && (branch_extra == 0 || branch_extra == 3))
2875             branch_extra += branch_newextra;
2876           continue;
2877           }
2878
2879         /* If options were terminated by ':' control comes here. Fall through
2880         to handle the group below. */
2881         }
2882       }
2883
2884     /* Extracting brackets must be counted so we can process escapes in a
2885     Perlish way. */
2886
2887     else bracount++;
2888
2889     /* Non-special forms of bracket. Save length for computing whole length
2890     at end if there's a repeat that requires duplication of the group. Also
2891     save the current value of branch_extra, and start the new group with
2892     the new value. If non-zero, this will either be 2 for a (?imsx: group, or 3
2893     for a lookbehind assertion. */
2894
2895     if (brastackptr >= sizeof(brastack)/sizeof(int))
2896       {
2897       *errorptr = ERR19;
2898       goto PCRE_ERROR_RETURN;
2899       }
2900
2901     bralenstack[brastackptr] = branch_extra;
2902     branch_extra = branch_newextra;
2903
2904     brastack[brastackptr++] = length;
2905     length += 3;
2906     continue;
2907
2908     /* Handle ket. Look for subsequent max/min; for certain sets of values we
2909     have to replicate this bracket up to that many times. If brastackptr is
2910     0 this is an unmatched bracket which will generate an error, but take care
2911     not to try to access brastack[-1] when computing the length and restoring
2912     the branch_extra value. */
2913
2914     case ')':
2915     length += 3;
2916       {
2917       int minval = 1;
2918       int maxval = 1;
2919       int duplength;
2920
2921       if (brastackptr > 0)
2922         {
2923         duplength = length - brastack[--brastackptr];
2924         branch_extra = bralenstack[brastackptr];
2925         }
2926       else duplength = 0;
2927
2928       /* Leave ptr at the final char; for read_repeat_counts this happens
2929       automatically; for the others we need an increment. */
2930
2931       if ((c = ptr[1]) == '{' && is_counted_repeat(ptr+2, &compile_block))
2932         {
2933         ptr = read_repeat_counts(ptr+2, &minval, &maxval, errorptr,
2934           &compile_block);
2935         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2936         }
2937       else if (c == '*') { minval = 0; maxval = -1; ptr++; }
2938       else if (c == '+') { maxval = -1; ptr++; }
2939       else if (c == '?') { minval = 0; ptr++; }
2940
2941       /* If the minimum is zero, we have to allow for an OP_BRAZERO before the
2942       group, and if the maximum is greater than zero, we have to replicate
2943       maxval-1 times; each replication acquires an OP_BRAZERO plus a nesting
2944       bracket set - hence the 7. */
2945
2946       if (minval == 0)
2947         {
2948         length++;
2949         if (maxval > 0) length += (maxval - 1) * (duplength + 7);
2950         }
2951
2952       /* When the minimum is greater than zero, 1 we have to replicate up to
2953       minval-1 times, with no additions required in the copies. Then, if
2954       there is a limited maximum we have to replicate up to maxval-1 times
2955       allowing for a BRAZERO item before each optional copy and nesting
2956       brackets for all but one of the optional copies. */
2957
2958       else
2959         {
2960         length += (minval - 1) * duplength;
2961         if (maxval > minval)   /* Need this test as maxval=-1 means no limit */
2962           length += (maxval - minval) * (duplength + 7) - 6;
2963         }
2964       }
2965     continue;
2966
2967     /* Non-special character. For a run of such characters the length required
2968     is the number of characters + 2, except that the maximum run length is 255.
2969     We won't get a skipped space or a non-data escape or the start of a #
2970     comment as the first character, so the length can't be zero. */
2971
2972     NORMAL_CHAR:
2973     default:
2974     length += 2;
2975     runlength = 0;
2976     do
2977       {
2978       if ((options & PCRE_EXTENDED) != 0)
2979         {
2980         if ((compile_block.ctypes[c] & ctype_space) != 0) continue;
2981         if (c == '#')
2982           {
2983           /* The space before the ; is to avoid a warning on a silly compiler
2984           on the Macintosh. */
2985           while ((c = *(++ptr)) != 0 && c != '\n') ;
2986           continue;
2987           }
2988         }
2989
2990       /* Backslash may introduce a data char or a metacharacter; stop the
2991       string before the latter. */
2992
2993       if (c == '\\')
2994         {
2995         const uschar *saveptr = ptr;
2996         c = check_escape(&ptr, errorptr, bracount, options, FALSE,
2997           &compile_block);
2998         if (*errorptr != NULL) goto PCRE_ERROR_RETURN;
2999         if (c < 0) { ptr = saveptr; break; }
3000
3001 #ifdef SUPPORT_UTF8
3002         if (c > 127 && (options & PCRE_UTF8) != 0)
3003           {
3004           int i;
3005           for (i = 0; i < sizeof(utf8_table1)/sizeof(int); i++)
3006             if (c <= utf8_table1[i]) break;
3007           runlength += i;
3008           }
3009 #endif
3010         }
3011
3012       /* Ordinary character or single-char escape */
3013
3014       runlength++;
3015
3016       if ((const char *)ptr > pattern + pattern_length)
3017         {
3018         *errorptr = "internal error";
3019         goto PCRE_ERROR_RETURN;
3020         }
3021       }
3022
3023     /* This "while" is the end of the "do" above. */
3024
3025     while (runlength < MAXLIT &&
3026       (compile_block.ctypes[c = *(++ptr)] & ctype_meta) == 0);
3027
3028     ptr--;
3029     length += runlength;
3030     continue;
3031     }
3032   }
3033
3034 length += 4;    /* For final KET and END */
3035
3036 if (length > 65539)
3037   {
3038   *errorptr = ERR20;
3039   return NULL;
3040   }
3041
3042 /* Compute the size of data block needed and get it, either from malloc or
3043 externally provided function. We specify "code[0]" in the offsetof() expression
3044 rather than just "code", because it has been reported that one broken compiler
3045 fails on "code" because it is also an independent variable. It should make no
3046 difference to the value of the offsetof(). */
3047
3048 size = length + offsetof(real_pcre, code[0]);
3049 re = (real_pcre *)(pcre_malloc)(size);
3050
3051 if (re == NULL)
3052   {
3053   *errorptr = ERR21;
3054   return NULL;
3055   }
3056
3057 /* Put in the magic number, and save the size, options, and table pointer */
3058
3059 re->magic_number = MAGIC_NUMBER;
3060 re->size = size;
3061 re->options = options;
3062 re->tables = tables;
3063
3064 /* Set up a starting, non-extracting bracket, then compile the expression. On
3065 error, *errorptr will be set non-NULL, so we don't need to look at the result
3066 of the function here. */
3067
3068 ptr = (const uschar *)pattern;
3069 code = re->code;
3070 *code = OP_BRA;
3071 bracount = 0;
3072 (void)compile_regex(options, -1, &bracount, &code, &ptr, errorptr, FALSE, -1,
3073   &reqchar, &countlits, &compile_block);
3074 re->top_bracket = bracount;
3075 re->top_backref = top_backref;
3076
3077 /* If not reached end of pattern on success, there's an excess bracket. */
3078
3079 if (*errorptr == NULL && *ptr != 0) *errorptr = ERR22;
3080
3081 /* Fill in the terminating state and check for disastrous overflow, but
3082 if debugging, leave the test till after things are printed out. */
3083
3084 *code++ = OP_END;
3085
3086 #ifndef DEBUG
3087 if (code - re->code > length) *errorptr = ERR23;
3088 #endif
3089
3090 /* Give an error if there's back reference to a non-existent capturing
3091 subpattern. */
3092
3093 if (top_backref > re->top_bracket) *errorptr = ERR15;
3094
3095 /* Failed to compile */
3096
3097 if (*errorptr != NULL)
3098   {
3099   (pcre_free)(re);
3100   PCRE_ERROR_RETURN:
3101   *erroroffset = ptr - (const uschar *)pattern;
3102   return NULL;
3103   }
3104
3105 /* If the anchored option was not passed, set flag if we can determine that the
3106 pattern is anchored by virtue of ^ characters or \A or anything else (such as
3107 starting with .* when DOTALL is set).
3108
3109 Otherwise, see if we can determine what the first character has to be, because
3110 that speeds up unanchored matches no end. If not, see if we can set the
3111 PCRE_STARTLINE flag. This is helpful for multiline matches when all branches
3112 start with ^. and also when all branches start with .* for non-DOTALL matches.
3113 */
3114
3115 if ((options & PCRE_ANCHORED) == 0)
3116   {
3117   int temp_options = options;
3118   if (is_anchored(re->code, &temp_options))
3119     re->options |= PCRE_ANCHORED;
3120   else
3121     {
3122     int ch = find_firstchar(re->code, &temp_options);
3123     if (ch >= 0)
3124       {
3125       re->first_char = ch;
3126       re->options |= PCRE_FIRSTSET;
3127       }
3128     else if (is_startline(re->code))
3129       re->options |= PCRE_STARTLINE;
3130     }
3131   }
3132
3133 /* Save the last required character if there are at least two literal
3134 characters on all paths, or if there is no first character setting. */
3135
3136 if (reqchar >= 0 && (countlits > 1 || (re->options & PCRE_FIRSTSET) == 0))
3137   {
3138   re->req_char = reqchar;
3139   re->options |= PCRE_REQCHSET;
3140   }
3141
3142 /* Print out the compiled data for debugging */
3143
3144 #ifdef DEBUG
3145
3146 printf("Length = %d top_bracket = %d top_backref = %d\n",
3147   length, re->top_bracket, re->top_backref);
3148
3149 if (re->options != 0)
3150   {
3151   printf("%s%s%s%s%s%s%s%s%s\n",
3152     ((re->options & PCRE_ANCHORED) != 0)? "anchored " : "",
3153     ((re->options & PCRE_CASELESS) != 0)? "caseless " : "",
3154     ((re->options & PCRE_ICHANGED) != 0)? "case state changed " : "",
3155     ((re->options & PCRE_EXTENDED) != 0)? "extended " : "",
3156     ((re->options & PCRE_MULTILINE) != 0)? "multiline " : "",
3157     ((re->options & PCRE_DOTALL) != 0)? "dotall " : "",
3158     ((re->options & PCRE_DOLLAR_ENDONLY) != 0)? "endonly " : "",
3159     ((re->options & PCRE_EXTRA) != 0)? "extra " : "",
3160     ((re->options & PCRE_UNGREEDY) != 0)? "ungreedy " : "");
3161   }
3162
3163 if ((re->options & PCRE_FIRSTSET) != 0)
3164   {
3165   if (isprint(re->first_char)) printf("First char = %c\n", re->first_char);
3166     else printf("First char = \\x%02x\n", re->first_char);
3167   }
3168
3169 if ((re->options & PCRE_REQCHSET) != 0)
3170   {
3171   if (isprint(re->req_char)) printf("Req char = %c\n", re->req_char);
3172     else printf("Req char = \\x%02x\n", re->req_char);
3173   }
3174
3175 code_end = code;
3176 code_base = code = re->code;
3177
3178 while (code < code_end)
3179   {
3180   int charlength;
3181
3182   printf("%3d ", code - code_base);
3183
3184   if (*code >= OP_BRA)
3185     {
3186     printf("%3d Bra %d", (code[1] << 8) + code[2], *code - OP_BRA);
3187     code += 2;
3188     }
3189
3190   else switch(*code)
3191     {
3192     case OP_OPT:
3193     printf(" %.2x %s", code[1], OP_names[*code]);
3194     code++;
3195     break;
3196
3197     case OP_COND:
3198     printf("%3d Cond", (code[1] << 8) + code[2]);
3199     code += 2;
3200     break;
3201
3202     case OP_CREF:
3203     printf(" %.2d %s", code[1], OP_names[*code]);
3204     code++;
3205     break;
3206
3207     case OP_CHARS:
3208     charlength = *(++code);
3209     printf("%3d ", charlength);
3210     while (charlength-- > 0)
3211       if (isprint(c = *(++code))) printf("%c", c); else printf("\\x%02x", c);
3212     break;
3213
3214     case OP_KETRMAX:
3215     case OP_KETRMIN:
3216     case OP_ALT:
3217     case OP_KET:
3218     case OP_ASSERT:
3219     case OP_ASSERT_NOT:
3220     case OP_ASSERTBACK:
3221     case OP_ASSERTBACK_NOT:
3222     case OP_ONCE:
3223     printf("%3d %s", (code[1] << 8) + code[2], OP_names[*code]);
3224     code += 2;
3225     break;
3226
3227     case OP_REVERSE:
3228     printf("%3d %s", (code[1] << 8) + code[2], OP_names[*code]);
3229     code += 2;
3230     break;
3231
3232     case OP_STAR:
3233     case OP_MINSTAR:
3234     case OP_PLUS:
3235     case OP_MINPLUS:
3236     case OP_QUERY:
3237     case OP_MINQUERY:
3238     case OP_TYPESTAR:
3239     case OP_TYPEMINSTAR:
3240     case OP_TYPEPLUS:
3241     case OP_TYPEMINPLUS:
3242     case OP_TYPEQUERY:
3243     case OP_TYPEMINQUERY:
3244     if (*code >= OP_TYPESTAR)
3245       printf("    %s", OP_names[code[1]]);
3246     else if (isprint(c = code[1])) printf("    %c", c);
3247       else printf("    \\x%02x", c);
3248     printf("%s", OP_names[*code++]);
3249     break;
3250
3251     case OP_EXACT:
3252     case OP_UPTO:
3253     case OP_MINUPTO:
3254     if (isprint(c = code[3])) printf("    %c{", c);
3255       else printf("    \\x%02x{", c);
3256     if (*code != OP_EXACT) printf("0,");
3257     printf("%d}", (code[1] << 8) + code[2]);
3258     if (*code == OP_MINUPTO) printf("?");
3259     code += 3;
3260     break;
3261
3262     case OP_TYPEEXACT:
3263     case OP_TYPEUPTO:
3264     case OP_TYPEMINUPTO:
3265     printf("    %s{", OP_names[code[3]]);
3266     if (*code != OP_TYPEEXACT) printf(",");
3267     printf("%d}", (code[1] << 8) + code[2]);
3268     if (*code == OP_TYPEMINUPTO) printf("?");
3269     code += 3;
3270     break;
3271
3272     case OP_NOT:
3273     if (isprint(c = *(++code))) printf("    [^%c]", c);
3274       else printf("    [^\\x%02x]", c);
3275     break;
3276
3277     case OP_NOTSTAR:
3278     case OP_NOTMINSTAR:
3279     case OP_NOTPLUS:
3280     case OP_NOTMINPLUS:
3281     case OP_NOTQUERY:
3282     case OP_NOTMINQUERY:
3283     if (isprint(c = code[1])) printf("    [^%c]", c);
3284       else printf("    [^\\x%02x]", c);
3285     printf("%s", OP_names[*code++]);
3286     break;
3287
3288     case OP_NOTEXACT:
3289     case OP_NOTUPTO:
3290     case OP_NOTMINUPTO:
3291     if (isprint(c = code[3])) printf("    [^%c]{", c);
3292       else printf("    [^\\x%02x]{", c);
3293     if (*code != OP_NOTEXACT) printf(",");
3294     printf("%d}", (code[1] << 8) + code[2]);
3295     if (*code == OP_NOTMINUPTO) printf("?");
3296     code += 3;
3297     break;
3298
3299     case OP_REF:
3300     printf("    \\%d", *(++code));
3301     code ++;
3302     goto CLASS_REF_REPEAT;
3303
3304     case OP_CLASS:
3305       {
3306       int i, min, max;
3307       code++;
3308       printf("    [");
3309
3310       for (i = 0; i < 256; i++)
3311         {
3312         if ((code[i/8] & (1 << (i&7))) != 0)
3313           {
3314           int j;
3315           for (j = i+1; j < 256; j++)
3316             if ((code[j/8] & (1 << (j&7))) == 0) break;
3317           if (i == '-' || i == ']') printf("\\");
3318           if (isprint(i)) printf("%c", i); else printf("\\x%02x", i);
3319           if (--j > i)
3320             {
3321             printf("-");
3322             if (j == '-' || j == ']') printf("\\");
3323             if (isprint(j)) printf("%c", j); else printf("\\x%02x", j);
3324             }
3325           i = j;
3326           }
3327         }
3328       printf("]");
3329       code += 32;
3330
3331       CLASS_REF_REPEAT:
3332
3333       switch(*code)
3334         {
3335         case OP_CRSTAR:
3336         case OP_CRMINSTAR:
3337         case OP_CRPLUS:
3338         case OP_CRMINPLUS:
3339         case OP_CRQUERY:
3340         case OP_CRMINQUERY:
3341         printf("%s", OP_names[*code]);
3342         break;
3343
3344         case OP_CRRANGE:
3345         case OP_CRMINRANGE:
3346         min = (code[1] << 8) + code[2];
3347         max = (code[3] << 8) + code[4];
3348         if (max == 0) printf("{%d,}", min);
3349         else printf("{%d,%d}", min, max);
3350         if (*code == OP_CRMINRANGE) printf("?");
3351         code += 4;
3352         break;
3353
3354         default:
3355         code--;
3356         }
3357       }
3358     break;
3359
3360     /* Anything else is just a one-node item */
3361
3362     default:
3363     printf("    %s", OP_names[*code]);
3364     break;
3365     }
3366
3367   code++;
3368   printf("\n");
3369   }
3370 printf("------------------------------------------------------------------\n");
3371
3372 /* This check is done here in the debugging case so that the code that
3373 was compiled can be seen. */
3374
3375 if (code - re->code > length)
3376   {
3377   *errorptr = ERR23;
3378   (pcre_free)(re);
3379   *erroroffset = ptr - (uschar *)pattern;
3380   return NULL;
3381   }
3382 #endif
3383
3384 return (pcre *)re;
3385 }
3386
3387
3388
3389 /*************************************************
3390 *          Match a back-reference                *
3391 *************************************************/
3392
3393 /* If a back reference hasn't been set, the length that is passed is greater
3394 than the number of characters left in the string, so the match fails.
3395
3396 Arguments:
3397   offset      index into the offset vector
3398   eptr        points into the subject
3399   length      length to be matched
3400   md          points to match data block
3401   ims         the ims flags
3402
3403 Returns:      TRUE if matched
3404 */
3405
3406 static BOOL
3407 match_ref(int offset, register const uschar *eptr, int length, match_data *md,
3408   unsigned long int ims)
3409 {
3410 const uschar *p = md->start_subject + md->offset_vector[offset];
3411
3412 #ifdef DEBUG
3413 if (eptr >= md->end_subject)
3414   printf("matching subject <null>");
3415 else
3416   {
3417   printf("matching subject ");
3418   pchars(eptr, length, TRUE, md);
3419   }
3420 printf(" against backref ");
3421 pchars(p, length, FALSE, md);
3422 printf("\n");
3423 #endif
3424
3425 /* Always fail if not enough characters left */
3426
3427 if (length > md->end_subject - eptr) return FALSE;
3428
3429 /* Separate the caselesss case for speed */
3430
3431 if ((ims & PCRE_CASELESS) != 0)
3432   {
3433   while (length-- > 0)
3434     if (md->lcc[*p++] != md->lcc[*eptr++]) return FALSE;
3435   }
3436 else
3437   { while (length-- > 0) if (*p++ != *eptr++) return FALSE; }
3438
3439 return TRUE;
3440 }
3441
3442
3443
3444 /*************************************************
3445 *         Match from current position            *
3446 *************************************************/
3447
3448 /* On entry ecode points to the first opcode, and eptr to the first character
3449 in the subject string, while eptrb holds the value of eptr at the start of the
3450 last bracketed group - used for breaking infinite loops matching zero-length
3451 strings.
3452
3453 Arguments:
3454    eptr        pointer in subject
3455    ecode       position in code
3456    offset_top  current top pointer
3457    md          pointer to "static" info for the match
3458    ims         current /i, /m, and /s options
3459    eptrb       pointer to chain of blocks containing eptr at start of
3460                  brackets - for testing for empty matches
3461    flags       can contain
3462                  match_condassert - this is an assertion condition
3463                  match_isgroup - this is the start of a bracketed group
3464
3465 Returns:       TRUE if matched
3466 */
3467
3468 static BOOL
3469 match(register const uschar *eptr, register const uschar *ecode,
3470   int offset_top, match_data *md, unsigned long int ims, eptrblock *eptrb,
3471   int flags)
3472 {
3473 unsigned long int original_ims = ims;   /* Save for resetting on ')' */
3474 eptrblock newptrb;
3475
3476 /* At the start of a bracketed group, add the current subject pointer to the
3477 stack of such pointers, to be re-instated at the end of the group when we hit
3478 the closing ket. When match() is called in other circumstances, we don't add to
3479 the stack. */
3480
3481 if ((flags & match_isgroup) != 0)
3482   {
3483   newptrb.prev = eptrb;
3484   newptrb.saved_eptr = eptr;
3485   eptrb = &newptrb;
3486   }
3487
3488 /* Now start processing the operations. */
3489
3490 for (;;)
3491   {
3492   int op = (int)*ecode;
3493   int min, max, ctype;
3494   register int i;
3495   register int c;
3496   BOOL minimize = FALSE;
3497
3498   /* Opening capturing bracket. If there is space in the offset vector, save
3499   the current subject position in the working slot at the top of the vector. We
3500   mustn't change the current values of the data slot, because they may be set
3501   from a previous iteration of this group, and be referred to by a reference
3502   inside the group.
3503
3504   If the bracket fails to match, we need to restore this value and also the
3505   values of the final offsets, in case they were set by a previous iteration of
3506   the same bracket.
3507
3508   If there isn't enough space in the offset vector, treat this as if it were a
3509   non-capturing bracket. Don't worry about setting the flag for the error case
3510   here; that is handled in the code for KET. */
3511
3512   if (op > OP_BRA)
3513     {
3514     int number = op - OP_BRA;
3515     int offset = number << 1;
3516
3517 #ifdef DEBUG
3518     printf("start bracket %d subject=", number);
3519     pchars(eptr, 16, TRUE, md);
3520     printf("\n");
3521 #endif
3522
3523     if (offset < md->offset_max)
3524       {
3525       int save_offset1 = md->offset_vector[offset];
3526       int save_offset2 = md->offset_vector[offset+1];
3527       int save_offset3 = md->offset_vector[md->offset_end - number];
3528
3529       DPRINTF(("saving %d %d %d\n", save_offset1, save_offset2, save_offset3));
3530       md->offset_vector[md->offset_end - number] = eptr - md->start_subject;
3531
3532       do
3533         {
3534         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup))
3535           return TRUE;
3536         ecode += (ecode[1] << 8) + ecode[2];
3537         }
3538       while (*ecode == OP_ALT);
3539
3540       DPRINTF(("bracket %d failed\n", number));
3541
3542       md->offset_vector[offset] = save_offset1;
3543       md->offset_vector[offset+1] = save_offset2;
3544       md->offset_vector[md->offset_end - number] = save_offset3;
3545       return FALSE;
3546       }
3547
3548     /* Insufficient room for saving captured contents */
3549
3550     else op = OP_BRA;
3551     }
3552
3553   /* Other types of node can be handled by a switch */
3554
3555   switch(op)
3556     {
3557     case OP_BRA:     /* Non-capturing bracket: optimized */
3558     DPRINTF(("start bracket 0\n"));
3559     do
3560       {
3561       if (match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup))
3562         return TRUE;
3563       ecode += (ecode[1] << 8) + ecode[2];
3564       }
3565     while (*ecode == OP_ALT);
3566     DPRINTF(("bracket 0 failed\n"));
3567     return FALSE;
3568
3569     /* Conditional group: compilation checked that there are no more than
3570     two branches. If the condition is false, skipping the first branch takes us
3571     past the end if there is only one branch, but that's OK because that is
3572     exactly what going to the ket would do. */
3573
3574     case OP_COND:
3575     if (ecode[3] == OP_CREF)         /* Condition is extraction test */
3576       {
3577       int offset = ecode[4] << 1;    /* Doubled reference number */
3578       return match(eptr,
3579         ecode + ((offset < offset_top && md->offset_vector[offset] >= 0)?
3580           5 : 3 + (ecode[1] << 8) + ecode[2]),
3581         offset_top, md, ims, eptrb, match_isgroup);
3582       }
3583
3584     /* The condition is an assertion. Call match() to evaluate it - setting
3585     the final argument TRUE causes it to stop at the end of an assertion. */
3586
3587     else
3588       {
3589       if (match(eptr, ecode+3, offset_top, md, ims, NULL,
3590           match_condassert | match_isgroup))
3591         {
3592         ecode += 3 + (ecode[4] << 8) + ecode[5];
3593         while (*ecode == OP_ALT) ecode += (ecode[1] << 8) + ecode[2];
3594         }
3595       else ecode += (ecode[1] << 8) + ecode[2];
3596       return match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup);
3597       }
3598     /* Control never reaches here */
3599
3600     /* Skip over conditional reference data if encountered (should not be) */
3601
3602     case OP_CREF:
3603     ecode += 2;
3604     break;
3605
3606     /* End of the pattern. If PCRE_NOTEMPTY is set, fail if we have matched
3607     an empty string - recursion will then try other alternatives, if any. */
3608
3609     case OP_END:
3610     if (md->notempty && eptr == md->start_match) return FALSE;
3611     md->end_match_ptr = eptr;          /* Record where we ended */
3612     md->end_offset_top = offset_top;   /* and how many extracts were taken */
3613     return TRUE;
3614
3615     /* Change option settings */
3616
3617     case OP_OPT:
3618     ims = ecode[1];
3619     ecode += 2;
3620     DPRINTF(("ims set to %02lx\n", ims));
3621     break;
3622
3623     /* Assertion brackets. Check the alternative branches in turn - the
3624     matching won't pass the KET for an assertion. If any one branch matches,
3625     the assertion is true. Lookbehind assertions have an OP_REVERSE item at the
3626     start of each branch to move the current point backwards, so the code at
3627     this level is identical to the lookahead case. */
3628
3629     case OP_ASSERT:
3630     case OP_ASSERTBACK:
3631     do
3632       {
3633       if (match(eptr, ecode+3, offset_top, md, ims, NULL, match_isgroup)) break;
3634       ecode += (ecode[1] << 8) + ecode[2];
3635       }
3636     while (*ecode == OP_ALT);
3637     if (*ecode == OP_KET) return FALSE;
3638
3639     /* If checking an assertion for a condition, return TRUE. */
3640
3641     if ((flags & match_condassert) != 0) return TRUE;
3642
3643     /* Continue from after the assertion, updating the offsets high water
3644     mark, since extracts may have been taken during the assertion. */
3645
3646     do ecode += (ecode[1] << 8) + ecode[2]; while (*ecode == OP_ALT);
3647     ecode += 3;
3648     offset_top = md->end_offset_top;
3649     continue;
3650
3651     /* Negative assertion: all branches must fail to match */
3652
3653     case OP_ASSERT_NOT:
3654     case OP_ASSERTBACK_NOT:
3655     do
3656       {
3657       if (match(eptr, ecode+3, offset_top, md, ims, NULL, match_isgroup))
3658         return FALSE;
3659       ecode += (ecode[1] << 8) + ecode[2];
3660       }
3661     while (*ecode == OP_ALT);
3662
3663     if ((flags & match_condassert) != 0) return TRUE;
3664
3665     ecode += 3;
3666     continue;
3667
3668     /* Move the subject pointer back. This occurs only at the start of
3669     each branch of a lookbehind assertion. If we are too close to the start to
3670     move back, this match function fails. When working with UTF-8 we move
3671     back a number of characters, not bytes. */
3672
3673     case OP_REVERSE:
3674 #ifdef SUPPORT_UTF8
3675     c = (ecode[1] << 8) + ecode[2];
3676     for (i = 0; i < c; i++)
3677       {
3678       eptr--;
3679       BACKCHAR(eptr)
3680       }
3681 #else
3682     eptr -= (ecode[1] << 8) + ecode[2];
3683 #endif
3684
3685     if (eptr < md->start_subject) return FALSE;
3686     ecode += 3;
3687     break;
3688
3689     /* Recursion matches the current regex, nested. If there are any capturing
3690     brackets started but not finished, we have to save their starting points
3691     and reinstate them after the recursion. However, we don't know how many
3692     such there are (offset_top records the completed total) so we just have
3693     to save all the potential data. There may be up to 99 such values, which
3694     is a bit large to put on the stack, but using malloc for small numbers
3695     seems expensive. As a compromise, the stack is used when there are fewer
3696     than 16 values to store; otherwise malloc is used. A problem is what to do
3697     if the malloc fails ... there is no way of returning to the top level with
3698     an error. Save the top 15 values on the stack, and accept that the rest
3699     may be wrong. */
3700
3701     case OP_RECURSE:
3702       {
3703       BOOL rc;
3704       int *save;
3705       int stacksave[15];
3706
3707       c = md->offset_max;
3708
3709       if (c < 16) save = stacksave; else
3710         {
3711         save = (int *)(pcre_malloc)((c+1) * sizeof(int));
3712         if (save == NULL)
3713           {
3714           save = stacksave;
3715           c = 15;
3716           }
3717         }
3718
3719       for (i = 1; i <= c; i++)
3720         save[i] = md->offset_vector[md->offset_end - i];
3721       rc = match(eptr, md->start_pattern, offset_top, md, ims, eptrb,
3722         match_isgroup);
3723       for (i = 1; i <= c; i++)
3724         md->offset_vector[md->offset_end - i] = save[i];
3725       if (save != stacksave) (pcre_free)(save);
3726       if (!rc) return FALSE;
3727
3728       /* In case the recursion has set more capturing values, save the final
3729       number, then move along the subject till after the recursive match,
3730       and advance one byte in the pattern code. */
3731
3732       offset_top = md->end_offset_top;
3733       eptr = md->end_match_ptr;
3734       ecode++;
3735       }
3736     break;
3737
3738     /* "Once" brackets are like assertion brackets except that after a match,
3739     the point in the subject string is not moved back. Thus there can never be
3740     a move back into the brackets. Check the alternative branches in turn - the
3741     matching won't pass the KET for this kind of subpattern. If any one branch
3742     matches, we carry on as at the end of a normal bracket, leaving the subject
3743     pointer. */
3744
3745     case OP_ONCE:
3746       {
3747       const uschar *prev = ecode;
3748       const uschar *saved_eptr = eptr;
3749
3750       do
3751         {
3752         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, match_isgroup))
3753           break;
3754         ecode += (ecode[1] << 8) + ecode[2];
3755         }
3756       while (*ecode == OP_ALT);
3757
3758       /* If hit the end of the group (which could be repeated), fail */
3759
3760       if (*ecode != OP_ONCE && *ecode != OP_ALT) return FALSE;
3761
3762       /* Continue as from after the assertion, updating the offsets high water
3763       mark, since extracts may have been taken. */
3764
3765       do ecode += (ecode[1] << 8) + ecode[2]; while (*ecode == OP_ALT);
3766
3767       offset_top = md->end_offset_top;
3768       eptr = md->end_match_ptr;
3769
3770       /* For a non-repeating ket, just continue at this level. This also
3771       happens for a repeating ket if no characters were matched in the group.
3772       This is the forcible breaking of infinite loops as implemented in Perl
3773       5.005. If there is an options reset, it will get obeyed in the normal
3774       course of events. */
3775
3776       if (*ecode == OP_KET || eptr == saved_eptr)
3777         {
3778         ecode += 3;
3779         break;
3780         }
3781
3782       /* The repeating kets try the rest of the pattern or restart from the
3783       preceding bracket, in the appropriate order. We need to reset any options
3784       that changed within the bracket before re-running it, so check the next
3785       opcode. */
3786
3787       if (ecode[3] == OP_OPT)
3788         {
3789         ims = (ims & ~PCRE_IMS) | ecode[4];
3790         DPRINTF(("ims set to %02lx at group repeat\n", ims));
3791         }
3792
3793       if (*ecode == OP_KETRMIN)
3794         {
3795         if (match(eptr, ecode+3, offset_top, md, ims, eptrb, 0) ||
3796             match(eptr, prev, offset_top, md, ims, eptrb, match_isgroup))
3797               return TRUE;
3798         }
3799       else  /* OP_KETRMAX */
3800         {
3801         if (match(eptr, prev, offset_top, md, ims, eptrb, match_isgroup) ||
3802             match(eptr, ecode+3, offset_top, md, ims, eptrb, 0)) return TRUE;
3803         }
3804       }
3805     return FALSE;
3806
3807     /* An alternation is the end of a branch; scan along to find the end of the
3808     bracketed group and go to there. */
3809
3810     case OP_ALT:
3811     do ecode += (ecode[1] << 8) + ecode[2]; while (*ecode == OP_ALT);
3812