chiark / gitweb /
more quilt faff
[pcre3.git] / pcre_exec.c
1 /*************************************************
2 *      Perl-Compatible Regular Expressions       *
3 *************************************************/
4
5 /* PCRE is a library of functions to support regular expressions whose syntax
6 and semantics are as close as possible to those of the Perl 5 language.
7
8                        Written by Philip Hazel
9            Copyright (c) 1997-2014 University of Cambridge
10
11 -----------------------------------------------------------------------------
12 Redistribution and use in source and binary forms, with or without
13 modification, are permitted provided that the following conditions are met:
14
15     * Redistributions of source code must retain the above copyright notice,
16       this list of conditions and the following disclaimer.
17
18     * Redistributions in binary form must reproduce the above copyright
19       notice, this list of conditions and the following disclaimer in the
20       documentation and/or other materials provided with the distribution.
21
22     * Neither the name of the University of Cambridge nor the names of its
23       contributors may be used to endorse or promote products derived from
24       this software without specific prior written permission.
25
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
27 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
30 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 POSSIBILITY OF SUCH DAMAGE.
37 -----------------------------------------------------------------------------
38 */
39
40 /* This module contains pcre_exec(), the externally visible function that does
41 pattern matching using an NFA algorithm, trying to mimic Perl as closely as
42 possible. There are also some static supporting functions. */
43
44 #ifdef HAVE_CONFIG_H
45 #include "config.h"
46 #endif
47
48 #define NLBLOCK md             /* Block containing newline information */
49 #define PSSTART start_subject  /* Field containing processed string start */
50 #define PSEND   end_subject    /* Field containing processed string end */
51
52 #include "pcre_internal.h"
53
54 /* Undefine some potentially clashing cpp symbols */
55
56 #undef min
57 #undef max
58
59 /* The md->capture_last field uses the lower 16 bits for the last captured
60 substring (which can never be greater than 65535) and a bit in the top half
61 to mean "capture vector overflowed". This odd way of doing things was
62 implemented when it was realized that preserving and restoring the overflow bit
63 whenever the last capture number was saved/restored made for a neater
64 interface, and doing it this way saved on (a) another variable, which would
65 have increased the stack frame size (a big NO-NO in PCRE) and (b) another
66 separate set of save/restore instructions. The following defines are used in
67 implementing this. */
68
69 #define CAPLMASK    0x0000ffff    /* The bits used for last_capture */
70 #define OVFLMASK    0xffff0000    /* The bits used for the overflow flag */
71 #define OVFLBIT     0x00010000    /* The bit that is set for overflow */
72
73 /* Values for setting in md->match_function_type to indicate two special types
74 of call to match(). We do it this way to save on using another stack variable,
75 as stack usage is to be discouraged. */
76
77 #define MATCH_CONDASSERT     1  /* Called to check a condition assertion */
78 #define MATCH_CBEGROUP       2  /* Could-be-empty unlimited repeat group */
79
80 /* Non-error returns from the match() function. Error returns are externally
81 defined PCRE_ERROR_xxx codes, which are all negative. */
82
83 #define MATCH_MATCH        1
84 #define MATCH_NOMATCH      0
85
86 /* Special internal returns from the match() function. Make them sufficiently
87 negative to avoid the external error codes. */
88
89 #define MATCH_ACCEPT       (-999)
90 #define MATCH_KETRPOS      (-998)
91 #define MATCH_ONCE         (-997)
92 /* The next 5 must be kept together and in sequence so that a test that checks
93 for any one of them can use a range. */
94 #define MATCH_COMMIT       (-996)
95 #define MATCH_PRUNE        (-995)
96 #define MATCH_SKIP         (-994)
97 #define MATCH_SKIP_ARG     (-993)
98 #define MATCH_THEN         (-992)
99 #define MATCH_BACKTRACK_MAX MATCH_THEN
100 #define MATCH_BACKTRACK_MIN MATCH_COMMIT
101
102 /* Maximum number of ints of offset to save on the stack for recursive calls.
103 If the offset vector is bigger, malloc is used. This should be a multiple of 3,
104 because the offset vector is always a multiple of 3 long. */
105
106 #define REC_STACK_SAVE_MAX 30
107
108 /* Min and max values for the common repeats; for the maxima, 0 => infinity */
109
110 static const char rep_min[] = { 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, };
111 static const char rep_max[] = { 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, };
112
113 #ifdef PCRE_DEBUG
114 /*************************************************
115 *        Debugging function to print chars       *
116 *************************************************/
117
118 /* Print a sequence of chars in printable format, stopping at the end of the
119 subject if the requested.
120
121 Arguments:
122   p           points to characters
123   length      number to print
124   is_subject  TRUE if printing from within md->start_subject
125   md          pointer to matching data block, if is_subject is TRUE
126
127 Returns:     nothing
128 */
129
130 static void
131 pchars(const pcre_uchar *p, int length, BOOL is_subject, match_data *md)
132 {
133 pcre_uint32 c;
134 BOOL utf = md->utf;
135 if (is_subject && length > md->end_subject - p) length = md->end_subject - p;
136 while (length-- > 0)
137   if (isprint(c = UCHAR21INCTEST(p))) printf("%c", (char)c); else printf("\\x{%02x}", c);
138 }
139 #endif
140
141
142
143 /*************************************************
144 *          Match a back-reference                *
145 *************************************************/
146
147 /* Normally, if a back reference hasn't been set, the length that is passed is
148 negative, so the match always fails. However, in JavaScript compatibility mode,
149 the length passed is zero. Note that in caseless UTF-8 mode, the number of
150 subject bytes matched may be different to the number of reference bytes.
151
152 Arguments:
153   offset      index into the offset vector
154   eptr        pointer into the subject
155   length      length of reference to be matched (number of bytes)
156   md          points to match data block
157   caseless    TRUE if caseless
158
159 Returns:      >= 0 the number of subject bytes matched
160               -1 no match
161               -2 partial match; always given if at end subject
162 */
163
164 static int
165 match_ref(int offset, register PCRE_PUCHAR eptr, int length, match_data *md,
166   BOOL caseless)
167 {
168 PCRE_PUCHAR eptr_start = eptr;
169 register PCRE_PUCHAR p = md->start_subject + md->offset_vector[offset];
170 #if defined SUPPORT_UTF && defined SUPPORT_UCP
171 BOOL utf = md->utf;
172 #endif
173
174 #ifdef PCRE_DEBUG
175 if (eptr >= md->end_subject)
176   printf("matching subject <null>");
177 else
178   {
179   printf("matching subject ");
180   pchars(eptr, length, TRUE, md);
181   }
182 printf(" against backref ");
183 pchars(p, length, FALSE, md);
184 printf("\n");
185 #endif
186
187 /* Always fail if reference not set (and not JavaScript compatible - in that
188 case the length is passed as zero). */
189
190 if (length < 0) return -1;
191
192 /* Separate the caseless case for speed. In UTF-8 mode we can only do this
193 properly if Unicode properties are supported. Otherwise, we can check only
194 ASCII characters. */
195
196 if (caseless)
197   {
198 #if defined SUPPORT_UTF && defined SUPPORT_UCP
199   if (utf)
200     {
201     /* Match characters up to the end of the reference. NOTE: the number of
202     data units matched may differ, because in UTF-8 there are some characters
203     whose upper and lower case versions code have different numbers of bytes.
204     For example, U+023A (2 bytes in UTF-8) is the upper case version of U+2C65
205     (3 bytes in UTF-8); a sequence of 3 of the former uses 6 bytes, as does a
206     sequence of two of the latter. It is important, therefore, to check the
207     length along the reference, not along the subject (earlier code did this
208     wrong). */
209
210     PCRE_PUCHAR endptr = p + length;
211     while (p < endptr)
212       {
213       pcre_uint32 c, d;
214       const ucd_record *ur;
215       if (eptr >= md->end_subject) return -2;   /* Partial match */
216       GETCHARINC(c, eptr);
217       GETCHARINC(d, p);
218       ur = GET_UCD(d);
219       if (c != d && c != d + ur->other_case)
220         {
221         const pcre_uint32 *pp = PRIV(ucd_caseless_sets) + ur->caseset;
222         for (;;)
223           {
224           if (c < *pp) return -1;
225           if (c == *pp++) break;
226           }
227         }
228       }
229     }
230   else
231 #endif
232
233   /* The same code works when not in UTF-8 mode and in UTF-8 mode when there
234   is no UCP support. */
235     {
236     while (length-- > 0)
237       {
238       pcre_uint32 cc, cp;
239       if (eptr >= md->end_subject) return -2;   /* Partial match */
240       cc = UCHAR21TEST(eptr);
241       cp = UCHAR21TEST(p);
242       if (TABLE_GET(cp, md->lcc, cp) != TABLE_GET(cc, md->lcc, cc)) return -1;
243       p++;
244       eptr++;
245       }
246     }
247   }
248
249 /* In the caseful case, we can just compare the bytes, whether or not we
250 are in UTF-8 mode. */
251
252 else
253   {
254   while (length-- > 0)
255     {
256     if (eptr >= md->end_subject) return -2;   /* Partial match */
257     if (UCHAR21INCTEST(p) != UCHAR21INCTEST(eptr)) return -1;
258     }
259   }
260
261 return (int)(eptr - eptr_start);
262 }
263
264
265
266 /***************************************************************************
267 ****************************************************************************
268                    RECURSION IN THE match() FUNCTION
269
270 The match() function is highly recursive, though not every recursive call
271 increases the recursive depth. Nevertheless, some regular expressions can cause
272 it to recurse to a great depth. I was writing for Unix, so I just let it call
273 itself recursively. This uses the stack for saving everything that has to be
274 saved for a recursive call. On Unix, the stack can be large, and this works
275 fine.
276
277 It turns out that on some non-Unix-like systems there are problems with
278 programs that use a lot of stack. (This despite the fact that every last chip
279 has oodles of memory these days, and techniques for extending the stack have
280 been known for decades.) So....
281
282 There is a fudge, triggered by defining NO_RECURSE, which avoids recursive
283 calls by keeping local variables that need to be preserved in blocks of memory
284 obtained from malloc() instead instead of on the stack. Macros are used to
285 achieve this so that the actual code doesn't look very different to what it
286 always used to.
287
288 The original heap-recursive code used longjmp(). However, it seems that this
289 can be very slow on some operating systems. Following a suggestion from Stan
290 Switzer, the use of longjmp() has been abolished, at the cost of having to
291 provide a unique number for each call to RMATCH. There is no way of generating
292 a sequence of numbers at compile time in C. I have given them names, to make
293 them stand out more clearly.
294
295 Crude tests on x86 Linux show a small speedup of around 5-8%. However, on
296 FreeBSD, avoiding longjmp() more than halves the time taken to run the standard
297 tests. Furthermore, not using longjmp() means that local dynamic variables
298 don't have indeterminate values; this has meant that the frame size can be
299 reduced because the result can be "passed back" by straight setting of the
300 variable instead of being passed in the frame.
301 ****************************************************************************
302 ***************************************************************************/
303
304 /* Numbers for RMATCH calls. When this list is changed, the code at HEAP_RETURN
305 below must be updated in sync.  */
306
307 enum { RM1=1, RM2,  RM3,  RM4,  RM5,  RM6,  RM7,  RM8,  RM9,  RM10,
308        RM11,  RM12, RM13, RM14, RM15, RM16, RM17, RM18, RM19, RM20,
309        RM21,  RM22, RM23, RM24, RM25, RM26, RM27, RM28, RM29, RM30,
310        RM31,  RM32, RM33, RM34, RM35, RM36, RM37, RM38, RM39, RM40,
311        RM41,  RM42, RM43, RM44, RM45, RM46, RM47, RM48, RM49, RM50,
312        RM51,  RM52, RM53, RM54, RM55, RM56, RM57, RM58, RM59, RM60,
313        RM61,  RM62, RM63, RM64, RM65, RM66, RM67 };
314
315 /* These versions of the macros use the stack, as normal. There are debugging
316 versions and production versions. Note that the "rw" argument of RMATCH isn't
317 actually used in this definition. */
318
319 #ifndef NO_RECURSE
320 #define REGISTER register
321
322 #ifdef PCRE_DEBUG
323 #define RMATCH(ra,rb,rc,rd,re,rw) \
324   { \
325   printf("match() called in line %d\n", __LINE__); \
326   rrc = match(ra,rb,mstart,rc,rd,re,rdepth+1); \
327   printf("to line %d\n", __LINE__); \
328   }
329 #define RRETURN(ra) \
330   { \
331   printf("match() returned %d from line %d\n", ra, __LINE__); \
332   return ra; \
333   }
334 #else
335 #define RMATCH(ra,rb,rc,rd,re,rw) \
336   rrc = match(ra,rb,mstart,rc,rd,re,rdepth+1)
337 #define RRETURN(ra) return ra
338 #endif
339
340 #else
341
342
343 /* These versions of the macros manage a private stack on the heap. Note that
344 the "rd" argument of RMATCH isn't actually used in this definition. It's the md
345 argument of match(), which never changes. */
346
347 #define REGISTER
348
349 #define RMATCH(ra,rb,rc,rd,re,rw)\
350   {\
351   heapframe *newframe = frame->Xnextframe;\
352   if (newframe == NULL)\
353     {\
354     newframe = (heapframe *)(PUBL(stack_malloc))(sizeof(heapframe));\
355     if (newframe == NULL) RRETURN(PCRE_ERROR_NOMEMORY);\
356     newframe->Xnextframe = NULL;\
357     frame->Xnextframe = newframe;\
358     }\
359   frame->Xwhere = rw;\
360   newframe->Xeptr = ra;\
361   newframe->Xecode = rb;\
362   newframe->Xmstart = mstart;\
363   newframe->Xoffset_top = rc;\
364   newframe->Xeptrb = re;\
365   newframe->Xrdepth = frame->Xrdepth + 1;\
366   newframe->Xprevframe = frame;\
367   frame = newframe;\
368   DPRINTF(("restarting from line %d\n", __LINE__));\
369   goto HEAP_RECURSE;\
370   L_##rw:\
371   DPRINTF(("jumped back to line %d\n", __LINE__));\
372   }
373
374 #define RRETURN(ra)\
375   {\
376   heapframe *oldframe = frame;\
377   frame = oldframe->Xprevframe;\
378   if (frame != NULL)\
379     {\
380     rrc = ra;\
381     goto HEAP_RETURN;\
382     }\
383   return ra;\
384   }
385
386
387 /* Structure for remembering the local variables in a private frame */
388
389 typedef struct heapframe {
390   struct heapframe *Xprevframe;
391   struct heapframe *Xnextframe;
392
393   /* Function arguments that may change */
394
395   PCRE_PUCHAR Xeptr;
396   const pcre_uchar *Xecode;
397   PCRE_PUCHAR Xmstart;
398   int Xoffset_top;
399   eptrblock *Xeptrb;
400   unsigned int Xrdepth;
401
402   /* Function local variables */
403
404   PCRE_PUCHAR Xcallpat;
405 #ifdef SUPPORT_UTF
406   PCRE_PUCHAR Xcharptr;
407 #endif
408   PCRE_PUCHAR Xdata;
409   PCRE_PUCHAR Xnext;
410   PCRE_PUCHAR Xpp;
411   PCRE_PUCHAR Xprev;
412   PCRE_PUCHAR Xsaved_eptr;
413
414   recursion_info Xnew_recursive;
415
416   BOOL Xcur_is_word;
417   BOOL Xcondition;
418   BOOL Xprev_is_word;
419
420 #ifdef SUPPORT_UCP
421   int Xprop_type;
422   unsigned int Xprop_value;
423   int Xprop_fail_result;
424   int Xoclength;
425   pcre_uchar Xocchars[6];
426 #endif
427
428   int Xcodelink;
429   int Xctype;
430   unsigned int Xfc;
431   int Xfi;
432   int Xlength;
433   int Xmax;
434   int Xmin;
435   unsigned int Xnumber;
436   int Xoffset;
437   unsigned int Xop;
438   pcre_int32 Xsave_capture_last;
439   int Xsave_offset1, Xsave_offset2, Xsave_offset3;
440   int Xstacksave[REC_STACK_SAVE_MAX];
441
442   eptrblock Xnewptrb;
443
444   /* Where to jump back to */
445
446   int Xwhere;
447
448 } heapframe;
449
450 #endif
451
452
453 /***************************************************************************
454 ***************************************************************************/
455
456
457
458 /*************************************************
459 *         Match from current position            *
460 *************************************************/
461
462 /* This function is called recursively in many circumstances. Whenever it
463 returns a negative (error) response, the outer incarnation must also return the
464 same response. */
465
466 /* These macros pack up tests that are used for partial matching, and which
467 appear several times in the code. We set the "hit end" flag if the pointer is
468 at the end of the subject and also past the start of the subject (i.e.
469 something has been matched). For hard partial matching, we then return
470 immediately. The second one is used when we already know we are past the end of
471 the subject. */
472
473 #define CHECK_PARTIAL()\
474   if (md->partial != 0 && eptr >= md->end_subject && \
475       eptr > md->start_used_ptr) \
476     { \
477     md->hitend = TRUE; \
478     if (md->partial > 1) RRETURN(PCRE_ERROR_PARTIAL); \
479     }
480
481 #define SCHECK_PARTIAL()\
482   if (md->partial != 0 && eptr > md->start_used_ptr) \
483     { \
484     md->hitend = TRUE; \
485     if (md->partial > 1) RRETURN(PCRE_ERROR_PARTIAL); \
486     }
487
488
489 /* Performance note: It might be tempting to extract commonly used fields from
490 the md structure (e.g. utf, end_subject) into individual variables to improve
491 performance. Tests using gcc on a SPARC disproved this; in the first case, it
492 made performance worse.
493
494 Arguments:
495    eptr        pointer to current character in subject
496    ecode       pointer to current position in compiled code
497    mstart      pointer to the current match start position (can be modified
498                  by encountering \K)
499    offset_top  current top pointer
500    md          pointer to "static" info for the match
501    eptrb       pointer to chain of blocks containing eptr at start of
502                  brackets - for testing for empty matches
503    rdepth      the recursion depth
504
505 Returns:       MATCH_MATCH if matched            )  these values are >= 0
506                MATCH_NOMATCH if failed to match  )
507                a negative MATCH_xxx value for PRUNE, SKIP, etc
508                a negative PCRE_ERROR_xxx value if aborted by an error condition
509                  (e.g. stopped by repeated call or recursion limit)
510 */
511
512 static int
513 match(REGISTER PCRE_PUCHAR eptr, REGISTER const pcre_uchar *ecode,
514   PCRE_PUCHAR mstart, int offset_top, match_data *md, eptrblock *eptrb,
515   unsigned int rdepth)
516 {
517 /* These variables do not need to be preserved over recursion in this function,
518 so they can be ordinary variables in all cases. Mark some of them with
519 "register" because they are used a lot in loops. */
520
521 register int  rrc;         /* Returns from recursive calls */
522 register int  i;           /* Used for loops not involving calls to RMATCH() */
523 register pcre_uint32 c;    /* Character values not kept over RMATCH() calls */
524 register BOOL utf;         /* Local copy of UTF flag for speed */
525
526 BOOL minimize, possessive; /* Quantifier options */
527 BOOL caseless;
528 int condcode;
529
530 /* When recursion is not being used, all "local" variables that have to be
531 preserved over calls to RMATCH() are part of a "frame". We set up the top-level
532 frame on the stack here; subsequent instantiations are obtained from the heap
533 whenever RMATCH() does a "recursion". See the macro definitions above. Putting
534 the top-level on the stack rather than malloc-ing them all gives a performance
535 boost in many cases where there is not much "recursion". */
536
537 #ifdef NO_RECURSE
538 heapframe *frame = (heapframe *)md->match_frames_base;
539
540 /* Copy in the original argument variables */
541
542 frame->Xeptr = eptr;
543 frame->Xecode = ecode;
544 frame->Xmstart = mstart;
545 frame->Xoffset_top = offset_top;
546 frame->Xeptrb = eptrb;
547 frame->Xrdepth = rdepth;
548
549 /* This is where control jumps back to to effect "recursion" */
550
551 HEAP_RECURSE:
552
553 /* Macros make the argument variables come from the current frame */
554
555 #define eptr               frame->Xeptr
556 #define ecode              frame->Xecode
557 #define mstart             frame->Xmstart
558 #define offset_top         frame->Xoffset_top
559 #define eptrb              frame->Xeptrb
560 #define rdepth             frame->Xrdepth
561
562 /* Ditto for the local variables */
563
564 #ifdef SUPPORT_UTF
565 #define charptr            frame->Xcharptr
566 #endif
567 #define callpat            frame->Xcallpat
568 #define codelink           frame->Xcodelink
569 #define data               frame->Xdata
570 #define next               frame->Xnext
571 #define pp                 frame->Xpp
572 #define prev               frame->Xprev
573 #define saved_eptr         frame->Xsaved_eptr
574
575 #define new_recursive      frame->Xnew_recursive
576
577 #define cur_is_word        frame->Xcur_is_word
578 #define condition          frame->Xcondition
579 #define prev_is_word       frame->Xprev_is_word
580
581 #ifdef SUPPORT_UCP
582 #define prop_type          frame->Xprop_type
583 #define prop_value         frame->Xprop_value
584 #define prop_fail_result   frame->Xprop_fail_result
585 #define oclength           frame->Xoclength
586 #define occhars            frame->Xocchars
587 #endif
588
589 #define ctype              frame->Xctype
590 #define fc                 frame->Xfc
591 #define fi                 frame->Xfi
592 #define length             frame->Xlength
593 #define max                frame->Xmax
594 #define min                frame->Xmin
595 #define number             frame->Xnumber
596 #define offset             frame->Xoffset
597 #define op                 frame->Xop
598 #define save_capture_last  frame->Xsave_capture_last
599 #define save_offset1       frame->Xsave_offset1
600 #define save_offset2       frame->Xsave_offset2
601 #define save_offset3       frame->Xsave_offset3
602 #define stacksave          frame->Xstacksave
603
604 #define newptrb            frame->Xnewptrb
605
606 /* When recursion is being used, local variables are allocated on the stack and
607 get preserved during recursion in the normal way. In this environment, fi and
608 i, and fc and c, can be the same variables. */
609
610 #else         /* NO_RECURSE not defined */
611 #define fi i
612 #define fc c
613
614 /* Many of the following variables are used only in small blocks of the code.
615 My normal style of coding would have declared them within each of those blocks.
616 However, in order to accommodate the version of this code that uses an external
617 "stack" implemented on the heap, it is easier to declare them all here, so the
618 declarations can be cut out in a block. The only declarations within blocks
619 below are for variables that do not have to be preserved over a recursive call
620 to RMATCH(). */
621
622 #ifdef SUPPORT_UTF
623 const pcre_uchar *charptr;
624 #endif
625 const pcre_uchar *callpat;
626 const pcre_uchar *data;
627 const pcre_uchar *next;
628 PCRE_PUCHAR       pp;
629 const pcre_uchar *prev;
630 PCRE_PUCHAR       saved_eptr;
631
632 recursion_info new_recursive;
633
634 BOOL cur_is_word;
635 BOOL condition;
636 BOOL prev_is_word;
637
638 #ifdef SUPPORT_UCP
639 int prop_type;
640 unsigned int prop_value;
641 int prop_fail_result;
642 int oclength;
643 pcre_uchar occhars[6];
644 #endif
645
646 int codelink;
647 int ctype;
648 int length;
649 int max;
650 int min;
651 unsigned int number;
652 int offset;
653 unsigned int op;
654 pcre_int32 save_capture_last;
655 int save_offset1, save_offset2, save_offset3;
656 int stacksave[REC_STACK_SAVE_MAX];
657
658 eptrblock newptrb;
659
660 /* There is a special fudge for calling match() in a way that causes it to
661 measure the size of its basic stack frame when the stack is being used for
662 recursion. The second argument (ecode) being NULL triggers this behaviour. It
663 cannot normally ever be NULL. The return is the negated value of the frame
664 size. */
665
666 if (ecode == NULL)
667   {
668   if (rdepth == 0)
669     return match((PCRE_PUCHAR)&rdepth, NULL, NULL, 0, NULL, NULL, 1);
670   else
671     {
672     int len = (char *)&rdepth - (char *)eptr;
673     return (len > 0)? -len : len;
674     }
675   }
676 #endif     /* NO_RECURSE */
677
678 /* To save space on the stack and in the heap frame, I have doubled up on some
679 of the local variables that are used only in localised parts of the code, but
680 still need to be preserved over recursive calls of match(). These macros define
681 the alternative names that are used. */
682
683 #define allow_zero    cur_is_word
684 #define cbegroup      condition
685 #define code_offset   codelink
686 #define condassert    condition
687 #define matched_once  prev_is_word
688 #define foc           number
689 #define save_mark     data
690
691 /* These statements are here to stop the compiler complaining about unitialized
692 variables. */
693
694 #ifdef SUPPORT_UCP
695 prop_value = 0;
696 prop_fail_result = 0;
697 #endif
698
699
700 /* This label is used for tail recursion, which is used in a few cases even
701 when NO_RECURSE is not defined, in order to reduce the amount of stack that is
702 used. Thanks to Ian Taylor for noticing this possibility and sending the
703 original patch. */
704
705 TAIL_RECURSE:
706
707 /* OK, now we can get on with the real code of the function. Recursive calls
708 are specified by the macro RMATCH and RRETURN is used to return. When
709 NO_RECURSE is *not* defined, these just turn into a recursive call to match()
710 and a "return", respectively (possibly with some debugging if PCRE_DEBUG is
711 defined). However, RMATCH isn't like a function call because it's quite a
712 complicated macro. It has to be used in one particular way. This shouldn't,
713 however, impact performance when true recursion is being used. */
714
715 #ifdef SUPPORT_UTF
716 utf = md->utf;       /* Local copy of the flag */
717 #else
718 utf = FALSE;
719 #endif
720
721 /* First check that we haven't called match() too many times, or that we
722 haven't exceeded the recursive call limit. */
723
724 if (md->match_call_count++ >= md->match_limit) RRETURN(PCRE_ERROR_MATCHLIMIT);
725 if (rdepth >= md->match_limit_recursion) RRETURN(PCRE_ERROR_RECURSIONLIMIT);
726
727 /* At the start of a group with an unlimited repeat that may match an empty
728 string, the variable md->match_function_type is set to MATCH_CBEGROUP. It is
729 done this way to save having to use another function argument, which would take
730 up space on the stack. See also MATCH_CONDASSERT below.
731
732 When MATCH_CBEGROUP is set, add the current subject pointer to the chain of
733 such remembered pointers, to be checked when we hit the closing ket, in order
734 to break infinite loops that match no characters. When match() is called in
735 other circumstances, don't add to the chain. The MATCH_CBEGROUP feature must
736 NOT be used with tail recursion, because the memory block that is used is on
737 the stack, so a new one may be required for each match(). */
738
739 if (md->match_function_type == MATCH_CBEGROUP)
740   {
741   newptrb.epb_saved_eptr = eptr;
742   newptrb.epb_prev = eptrb;
743   eptrb = &newptrb;
744   md->match_function_type = 0;
745   }
746
747 /* Now start processing the opcodes. */
748
749 for (;;)
750   {
751   minimize = possessive = FALSE;
752   op = *ecode;
753
754   switch(op)
755     {
756     case OP_MARK:
757     md->nomatch_mark = ecode + 2;
758     md->mark = NULL;    /* In case previously set by assertion */
759     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode] + ecode[1], offset_top, md,
760       eptrb, RM55);
761     if ((rrc == MATCH_MATCH || rrc == MATCH_ACCEPT) &&
762          md->mark == NULL) md->mark = ecode + 2;
763
764     /* A return of MATCH_SKIP_ARG means that matching failed at SKIP with an
765     argument, and we must check whether that argument matches this MARK's
766     argument. It is passed back in md->start_match_ptr (an overloading of that
767     variable). If it does match, we reset that variable to the current subject
768     position and return MATCH_SKIP. Otherwise, pass back the return code
769     unaltered. */
770
771     else if (rrc == MATCH_SKIP_ARG &&
772         STRCMP_UC_UC_TEST(ecode + 2, md->start_match_ptr) == 0)
773       {
774       md->start_match_ptr = eptr;
775       RRETURN(MATCH_SKIP);
776       }
777     RRETURN(rrc);
778
779     case OP_FAIL:
780     RRETURN(MATCH_NOMATCH);
781
782     case OP_COMMIT:
783     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
784       eptrb, RM52);
785     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
786     RRETURN(MATCH_COMMIT);
787
788     case OP_PRUNE:
789     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
790       eptrb, RM51);
791     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
792     RRETURN(MATCH_PRUNE);
793
794     case OP_PRUNE_ARG:
795     md->nomatch_mark = ecode + 2;
796     md->mark = NULL;    /* In case previously set by assertion */
797     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode] + ecode[1], offset_top, md,
798       eptrb, RM56);
799     if ((rrc == MATCH_MATCH || rrc == MATCH_ACCEPT) &&
800          md->mark == NULL) md->mark = ecode + 2;
801     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
802     RRETURN(MATCH_PRUNE);
803
804     case OP_SKIP:
805     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
806       eptrb, RM53);
807     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
808     md->start_match_ptr = eptr;   /* Pass back current position */
809     RRETURN(MATCH_SKIP);
810
811     /* Note that, for Perl compatibility, SKIP with an argument does NOT set
812     nomatch_mark. When a pattern match ends with a SKIP_ARG for which there was
813     not a matching mark, we have to re-run the match, ignoring the SKIP_ARG
814     that failed and any that precede it (either they also failed, or were not
815     triggered). To do this, we maintain a count of executed SKIP_ARGs. If a
816     SKIP_ARG gets to top level, the match is re-run with md->ignore_skip_arg
817     set to the count of the one that failed. */
818
819     case OP_SKIP_ARG:
820     md->skip_arg_count++;
821     if (md->skip_arg_count <= md->ignore_skip_arg)
822       {
823       ecode += PRIV(OP_lengths)[*ecode] + ecode[1];
824       break;
825       }
826     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode] + ecode[1], offset_top, md,
827       eptrb, RM57);
828     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
829
830     /* Pass back the current skip name by overloading md->start_match_ptr and
831     returning the special MATCH_SKIP_ARG return code. This will either be
832     caught by a matching MARK, or get to the top, where it causes a rematch
833     with md->ignore_skip_arg set to the value of md->skip_arg_count. */
834
835     md->start_match_ptr = ecode + 2;
836     RRETURN(MATCH_SKIP_ARG);
837
838     /* For THEN (and THEN_ARG) we pass back the address of the opcode, so that
839     the branch in which it occurs can be determined. Overload the start of
840     match pointer to do this. */
841
842     case OP_THEN:
843     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
844       eptrb, RM54);
845     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
846     md->start_match_ptr = ecode;
847     RRETURN(MATCH_THEN);
848
849     case OP_THEN_ARG:
850     md->nomatch_mark = ecode + 2;
851     md->mark = NULL;    /* In case previously set by assertion */
852     RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode] + ecode[1], offset_top,
853       md, eptrb, RM58);
854     if ((rrc == MATCH_MATCH || rrc == MATCH_ACCEPT) &&
855          md->mark == NULL) md->mark = ecode + 2;
856     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
857     md->start_match_ptr = ecode;
858     RRETURN(MATCH_THEN);
859
860     /* Handle an atomic group that does not contain any capturing parentheses.
861     This can be handled like an assertion. Prior to 8.13, all atomic groups
862     were handled this way. In 8.13, the code was changed as below for ONCE, so
863     that backups pass through the group and thereby reset captured values.
864     However, this uses a lot more stack, so in 8.20, atomic groups that do not
865     contain any captures generate OP_ONCE_NC, which can be handled in the old,
866     less stack intensive way.
867
868     Check the alternative branches in turn - the matching won't pass the KET
869     for this kind of subpattern. If any one branch matches, we carry on as at
870     the end of a normal bracket, leaving the subject pointer, but resetting
871     the start-of-match value in case it was changed by \K. */
872
873     case OP_ONCE_NC:
874     prev = ecode;
875     saved_eptr = eptr;
876     save_mark = md->mark;
877     do
878       {
879       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM64);
880       if (rrc == MATCH_MATCH)  /* Note: _not_ MATCH_ACCEPT */
881         {
882         mstart = md->start_match_ptr;
883         break;
884         }
885       if (rrc == MATCH_THEN)
886         {
887         next = ecode + GET(ecode,1);
888         if (md->start_match_ptr < next &&
889             (*ecode == OP_ALT || *next == OP_ALT))
890           rrc = MATCH_NOMATCH;
891         }
892
893       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
894       ecode += GET(ecode,1);
895       md->mark = save_mark;
896       }
897     while (*ecode == OP_ALT);
898
899     /* If hit the end of the group (which could be repeated), fail */
900
901     if (*ecode != OP_ONCE_NC && *ecode != OP_ALT) RRETURN(MATCH_NOMATCH);
902
903     /* Continue as from after the group, updating the offsets high water
904     mark, since extracts may have been taken. */
905
906     do ecode += GET(ecode, 1); while (*ecode == OP_ALT);
907
908     offset_top = md->end_offset_top;
909     eptr = md->end_match_ptr;
910
911     /* For a non-repeating ket, just continue at this level. This also
912     happens for a repeating ket if no characters were matched in the group.
913     This is the forcible breaking of infinite loops as implemented in Perl
914     5.005. */
915
916     if (*ecode == OP_KET || eptr == saved_eptr)
917       {
918       ecode += 1+LINK_SIZE;
919       break;
920       }
921
922     /* The repeating kets try the rest of the pattern or restart from the
923     preceding bracket, in the appropriate order. The second "call" of match()
924     uses tail recursion, to avoid using another stack frame. */
925
926     if (*ecode == OP_KETRMIN)
927       {
928       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM65);
929       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
930       ecode = prev;
931       goto TAIL_RECURSE;
932       }
933     else  /* OP_KETRMAX */
934       {
935       RMATCH(eptr, prev, offset_top, md, eptrb, RM66);
936       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
937       ecode += 1 + LINK_SIZE;
938       goto TAIL_RECURSE;
939       }
940     /* Control never gets here */
941
942     /* Handle a capturing bracket, other than those that are possessive with an
943     unlimited repeat. If there is space in the offset vector, save the current
944     subject position in the working slot at the top of the vector. We mustn't
945     change the current values of the data slot, because they may be set from a
946     previous iteration of this group, and be referred to by a reference inside
947     the group. A failure to match might occur after the group has succeeded,
948     if something later on doesn't match. For this reason, we need to restore
949     the working value and also the values of the final offsets, in case they
950     were set by a previous iteration of the same bracket.
951
952     If there isn't enough space in the offset vector, treat this as if it were
953     a non-capturing bracket. Don't worry about setting the flag for the error
954     case here; that is handled in the code for KET. */
955
956     case OP_CBRA:
957     case OP_SCBRA:
958     number = GET2(ecode, 1+LINK_SIZE);
959     offset = number << 1;
960
961 #ifdef PCRE_DEBUG
962     printf("start bracket %d\n", number);
963     printf("subject=");
964     pchars(eptr, 16, TRUE, md);
965     printf("\n");
966 #endif
967
968     if (offset < md->offset_max)
969       {
970       save_offset1 = md->offset_vector[offset];
971       save_offset2 = md->offset_vector[offset+1];
972       save_offset3 = md->offset_vector[md->offset_end - number];
973       save_capture_last = md->capture_last;
974       save_mark = md->mark;
975
976       DPRINTF(("saving %d %d %d\n", save_offset1, save_offset2, save_offset3));
977       md->offset_vector[md->offset_end - number] =
978         (int)(eptr - md->start_subject);
979
980       for (;;)
981         {
982         if (op >= OP_SBRA) md->match_function_type = MATCH_CBEGROUP;
983         RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
984           eptrb, RM1);
985         if (rrc == MATCH_ONCE) break;  /* Backing up through an atomic group */
986
987         /* If we backed up to a THEN, check whether it is within the current
988         branch by comparing the address of the THEN that is passed back with
989         the end of the branch. If it is within the current branch, and the
990         branch is one of two or more alternatives (it either starts or ends
991         with OP_ALT), we have reached the limit of THEN's action, so convert
992         the return code to NOMATCH, which will cause normal backtracking to
993         happen from now on. Otherwise, THEN is passed back to an outer
994         alternative. This implements Perl's treatment of parenthesized groups,
995         where a group not containing | does not affect the current alternative,
996         that is, (X) is NOT the same as (X|(*F)). */
997
998         if (rrc == MATCH_THEN)
999           {
1000           next = ecode + GET(ecode,1);
1001           if (md->start_match_ptr < next &&
1002               (*ecode == OP_ALT || *next == OP_ALT))
1003             rrc = MATCH_NOMATCH;
1004           }
1005
1006         /* Anything other than NOMATCH is passed back. */
1007
1008         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1009         md->capture_last = save_capture_last;
1010         ecode += GET(ecode, 1);
1011         md->mark = save_mark;
1012         if (*ecode != OP_ALT) break;
1013         }
1014
1015       DPRINTF(("bracket %d failed\n", number));
1016       md->offset_vector[offset] = save_offset1;
1017       md->offset_vector[offset+1] = save_offset2;
1018       md->offset_vector[md->offset_end - number] = save_offset3;
1019
1020       /* At this point, rrc will be one of MATCH_ONCE or MATCH_NOMATCH. */
1021
1022       RRETURN(rrc);
1023       }
1024
1025     /* FALL THROUGH ... Insufficient room for saving captured contents. Treat
1026     as a non-capturing bracket. */
1027
1028     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1029     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1030
1031     DPRINTF(("insufficient capture room: treat as non-capturing\n"));
1032
1033     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1034     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1035
1036     /* Non-capturing or atomic group, except for possessive with unlimited
1037     repeat and ONCE group with no captures. Loop for all the alternatives.
1038
1039     When we get to the final alternative within the brackets, we used to return
1040     the result of a recursive call to match() whatever happened so it was
1041     possible to reduce stack usage by turning this into a tail recursion,
1042     except in the case of a possibly empty group. However, now that there is
1043     the possiblity of (*THEN) occurring in the final alternative, this
1044     optimization is no longer always possible.
1045
1046     We can optimize if we know there are no (*THEN)s in the pattern; at present
1047     this is the best that can be done.
1048
1049     MATCH_ONCE is returned when the end of an atomic group is successfully
1050     reached, but subsequent matching fails. It passes back up the tree (causing
1051     captured values to be reset) until the original atomic group level is
1052     reached. This is tested by comparing md->once_target with the start of the
1053     group. At this point, the return is converted into MATCH_NOMATCH so that
1054     previous backup points can be taken. */
1055
1056     case OP_ONCE:
1057     case OP_BRA:
1058     case OP_SBRA:
1059     DPRINTF(("start non-capturing bracket\n"));
1060
1061     for (;;)
1062       {
1063       if (op >= OP_SBRA || op == OP_ONCE)
1064         md->match_function_type = MATCH_CBEGROUP;
1065
1066       /* If this is not a possibly empty group, and there are no (*THEN)s in
1067       the pattern, and this is the final alternative, optimize as described
1068       above. */
1069
1070       else if (!md->hasthen && ecode[GET(ecode, 1)] != OP_ALT)
1071         {
1072         ecode += PRIV(OP_lengths)[*ecode];
1073         goto TAIL_RECURSE;
1074         }
1075
1076       /* In all other cases, we have to make another call to match(). */
1077
1078       save_mark = md->mark;
1079       save_capture_last = md->capture_last;
1080       RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md, eptrb,
1081         RM2);
1082
1083       /* See comment in the code for capturing groups above about handling
1084       THEN. */
1085
1086       if (rrc == MATCH_THEN)
1087         {
1088         next = ecode + GET(ecode,1);
1089         if (md->start_match_ptr < next &&
1090             (*ecode == OP_ALT || *next == OP_ALT))
1091           rrc = MATCH_NOMATCH;
1092         }
1093
1094       if (rrc != MATCH_NOMATCH)
1095         {
1096         if (rrc == MATCH_ONCE)
1097           {
1098           const pcre_uchar *scode = ecode;
1099           if (*scode != OP_ONCE)           /* If not at start, find it */
1100             {
1101             while (*scode == OP_ALT) scode += GET(scode, 1);
1102             scode -= GET(scode, 1);
1103             }
1104           if (md->once_target == scode) rrc = MATCH_NOMATCH;
1105           }
1106         RRETURN(rrc);
1107         }
1108       ecode += GET(ecode, 1);
1109       md->mark = save_mark;
1110       if (*ecode != OP_ALT) break;
1111       md->capture_last = save_capture_last;
1112       }
1113
1114     RRETURN(MATCH_NOMATCH);
1115
1116     /* Handle possessive capturing brackets with an unlimited repeat. We come
1117     here from BRAZERO with allow_zero set TRUE. The offset_vector values are
1118     handled similarly to the normal case above. However, the matching is
1119     different. The end of these brackets will always be OP_KETRPOS, which
1120     returns MATCH_KETRPOS without going further in the pattern. By this means
1121     we can handle the group by iteration rather than recursion, thereby
1122     reducing the amount of stack needed. */
1123
1124     case OP_CBRAPOS:
1125     case OP_SCBRAPOS:
1126     allow_zero = FALSE;
1127
1128     POSSESSIVE_CAPTURE:
1129     number = GET2(ecode, 1+LINK_SIZE);
1130     offset = number << 1;
1131
1132 #ifdef PCRE_DEBUG
1133     printf("start possessive bracket %d\n", number);
1134     printf("subject=");
1135     pchars(eptr, 16, TRUE, md);
1136     printf("\n");
1137 #endif
1138
1139     if (offset < md->offset_max)
1140       {
1141       matched_once = FALSE;
1142       code_offset = (int)(ecode - md->start_code);
1143
1144       save_offset1 = md->offset_vector[offset];
1145       save_offset2 = md->offset_vector[offset+1];
1146       save_offset3 = md->offset_vector[md->offset_end - number];
1147       save_capture_last = md->capture_last;
1148
1149       DPRINTF(("saving %d %d %d\n", save_offset1, save_offset2, save_offset3));
1150
1151       /* Each time round the loop, save the current subject position for use
1152       when the group matches. For MATCH_MATCH, the group has matched, so we
1153       restart it with a new subject starting position, remembering that we had
1154       at least one match. For MATCH_NOMATCH, carry on with the alternatives, as
1155       usual. If we haven't matched any alternatives in any iteration, check to
1156       see if a previous iteration matched. If so, the group has matched;
1157       continue from afterwards. Otherwise it has failed; restore the previous
1158       capture values before returning NOMATCH. */
1159
1160       for (;;)
1161         {
1162         md->offset_vector[md->offset_end - number] =
1163           (int)(eptr - md->start_subject);
1164         if (op >= OP_SBRA) md->match_function_type = MATCH_CBEGROUP;
1165         RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
1166           eptrb, RM63);
1167         if (rrc == MATCH_KETRPOS)
1168           {
1169           offset_top = md->end_offset_top;
1170           eptr = md->end_match_ptr;
1171           ecode = md->start_code + code_offset;
1172           save_capture_last = md->capture_last;
1173           matched_once = TRUE;
1174           mstart = md->start_match_ptr;    /* In case \K changed it */
1175           continue;
1176           }
1177
1178         /* See comment in the code for capturing groups above about handling
1179         THEN. */
1180
1181         if (rrc == MATCH_THEN)
1182           {
1183           next = ecode + GET(ecode,1);
1184           if (md->start_match_ptr < next &&
1185               (*ecode == OP_ALT || *next == OP_ALT))
1186             rrc = MATCH_NOMATCH;
1187           }
1188
1189         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1190         md->capture_last = save_capture_last;
1191         ecode += GET(ecode, 1);
1192         if (*ecode != OP_ALT) break;
1193         }
1194
1195       if (!matched_once)
1196         {
1197         md->offset_vector[offset] = save_offset1;
1198         md->offset_vector[offset+1] = save_offset2;
1199         md->offset_vector[md->offset_end - number] = save_offset3;
1200         }
1201
1202       if (allow_zero || matched_once)
1203         {
1204         ecode += 1 + LINK_SIZE;
1205         break;
1206         }
1207
1208       RRETURN(MATCH_NOMATCH);
1209       }
1210
1211     /* FALL THROUGH ... Insufficient room for saving captured contents. Treat
1212     as a non-capturing bracket. */
1213
1214     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1215     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1216
1217     DPRINTF(("insufficient capture room: treat as non-capturing\n"));
1218
1219     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1220     /* VVVVVVVVVVVVVVVVVVVVVVVVV */
1221
1222     /* Non-capturing possessive bracket with unlimited repeat. We come here
1223     from BRAZERO with allow_zero = TRUE. The code is similar to the above,
1224     without the capturing complication. It is written out separately for speed
1225     and cleanliness. */
1226
1227     case OP_BRAPOS:
1228     case OP_SBRAPOS:
1229     allow_zero = FALSE;
1230
1231     POSSESSIVE_NON_CAPTURE:
1232     matched_once = FALSE;
1233     code_offset = (int)(ecode - md->start_code);
1234     save_capture_last = md->capture_last;
1235
1236     for (;;)
1237       {
1238       if (op >= OP_SBRA) md->match_function_type = MATCH_CBEGROUP;
1239       RMATCH(eptr, ecode + PRIV(OP_lengths)[*ecode], offset_top, md,
1240         eptrb, RM48);
1241       if (rrc == MATCH_KETRPOS)
1242         {
1243         offset_top = md->end_offset_top;
1244         eptr = md->end_match_ptr;
1245         ecode = md->start_code + code_offset;
1246         matched_once = TRUE;
1247         mstart = md->start_match_ptr;   /* In case \K reset it */
1248         continue;
1249         }
1250
1251       /* See comment in the code for capturing groups above about handling
1252       THEN. */
1253
1254       if (rrc == MATCH_THEN)
1255         {
1256         next = ecode + GET(ecode,1);
1257         if (md->start_match_ptr < next &&
1258             (*ecode == OP_ALT || *next == OP_ALT))
1259           rrc = MATCH_NOMATCH;
1260         }
1261
1262       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1263       ecode += GET(ecode, 1);
1264       if (*ecode != OP_ALT) break;
1265       md->capture_last = save_capture_last;
1266       }
1267
1268     if (matched_once || allow_zero)
1269       {
1270       ecode += 1 + LINK_SIZE;
1271       break;
1272       }
1273     RRETURN(MATCH_NOMATCH);
1274
1275     /* Control never reaches here. */
1276
1277     /* Conditional group: compilation checked that there are no more than two
1278     branches. If the condition is false, skipping the first branch takes us
1279     past the end of the item if there is only one branch, but that's exactly
1280     what we want. */
1281
1282     case OP_COND:
1283     case OP_SCOND:
1284
1285     /* The variable codelink will be added to ecode when the condition is
1286     false, to get to the second branch. Setting it to the offset to the ALT
1287     or KET, then incrementing ecode achieves this effect. We now have ecode
1288     pointing to the condition or callout. */
1289
1290     codelink = GET(ecode, 1);   /* Offset to the second branch */
1291     ecode += 1 + LINK_SIZE;     /* From this opcode */
1292
1293     /* Because of the way auto-callout works during compile, a callout item is
1294     inserted between OP_COND and an assertion condition. */
1295
1296     if (*ecode == OP_CALLOUT)
1297       {
1298       if (PUBL(callout) != NULL)
1299         {
1300         PUBL(callout_block) cb;
1301         cb.version          = 2;   /* Version 1 of the callout block */
1302         cb.callout_number   = ecode[1];
1303         cb.offset_vector    = md->offset_vector;
1304 #if defined COMPILE_PCRE8
1305         cb.subject          = (PCRE_SPTR)md->start_subject;
1306 #elif defined COMPILE_PCRE16
1307         cb.subject          = (PCRE_SPTR16)md->start_subject;
1308 #elif defined COMPILE_PCRE32
1309         cb.subject          = (PCRE_SPTR32)md->start_subject;
1310 #endif
1311         cb.subject_length   = (int)(md->end_subject - md->start_subject);
1312         cb.start_match      = (int)(mstart - md->start_subject);
1313         cb.current_position = (int)(eptr - md->start_subject);
1314         cb.pattern_position = GET(ecode, 2);
1315         cb.next_item_length = GET(ecode, 2 + LINK_SIZE);
1316         cb.capture_top      = offset_top/2;
1317         cb.capture_last     = md->capture_last & CAPLMASK;
1318         /* Internal change requires this for API compatibility. */
1319         if (cb.capture_last == 0) cb.capture_last = -1;
1320         cb.callout_data     = md->callout_data;
1321         cb.mark             = md->nomatch_mark;
1322         if ((rrc = (*PUBL(callout))(&cb)) > 0) RRETURN(MATCH_NOMATCH);
1323         if (rrc < 0) RRETURN(rrc);
1324         }
1325
1326       /* Advance ecode past the callout, so it now points to the condition. We
1327       must adjust codelink so that the value of ecode+codelink is unchanged. */
1328
1329       ecode += PRIV(OP_lengths)[OP_CALLOUT];
1330       codelink -= PRIV(OP_lengths)[OP_CALLOUT];
1331       }
1332
1333     /* Test the various possible conditions */
1334
1335     condition = FALSE;
1336     switch(condcode = *ecode)
1337       {
1338       case OP_RREF:         /* Numbered group recursion test */
1339       if (md->recursive != NULL)     /* Not recursing => FALSE */
1340         {
1341         unsigned int recno = GET2(ecode, 1);   /* Recursion group number*/
1342         condition = (recno == RREF_ANY || recno == md->recursive->group_num);
1343         }
1344       break;
1345
1346       case OP_DNRREF:       /* Duplicate named group recursion test */
1347       if (md->recursive != NULL)
1348         {
1349         int count = GET2(ecode, 1 + IMM2_SIZE);
1350         pcre_uchar *slot = md->name_table + GET2(ecode, 1) * md->name_entry_size;
1351         while (count-- > 0)
1352           {
1353           unsigned int recno = GET2(slot, 0);
1354           condition = recno == md->recursive->group_num;
1355           if (condition) break;
1356           slot += md->name_entry_size;
1357           }
1358         }
1359       break;
1360
1361       case OP_CREF:         /* Numbered group used test */
1362       offset = GET2(ecode, 1) << 1;  /* Doubled ref number */
1363       condition = offset < offset_top && md->offset_vector[offset] >= 0;
1364       break;
1365
1366       case OP_DNCREF:      /* Duplicate named group used test */
1367         {
1368         int count = GET2(ecode, 1 + IMM2_SIZE);
1369         pcre_uchar *slot = md->name_table + GET2(ecode, 1) * md->name_entry_size;
1370         while (count-- > 0)
1371           {
1372           offset = GET2(slot, 0) << 1;
1373           condition = offset < offset_top && md->offset_vector[offset] >= 0;
1374           if (condition) break;
1375           slot += md->name_entry_size;
1376           }
1377         }
1378       break;
1379
1380       case OP_DEF:     /* DEFINE - always false */
1381       break;
1382
1383       /* The condition is an assertion. Call match() to evaluate it - setting
1384       md->match_function_type to MATCH_CONDASSERT causes it to stop at the end
1385       of an assertion. */
1386
1387       default:
1388       md->match_function_type = MATCH_CONDASSERT;
1389       RMATCH(eptr, ecode, offset_top, md, NULL, RM3);
1390       if (rrc == MATCH_MATCH)
1391         {
1392         if (md->end_offset_top > offset_top)
1393           offset_top = md->end_offset_top;  /* Captures may have happened */
1394         condition = TRUE;
1395
1396         /* Advance ecode past the assertion to the start of the first branch,
1397         but adjust it so that the general choosing code below works. If the
1398         assertion has a quantifier that allows zero repeats we must skip over
1399         the BRAZERO. This is a lunatic thing to do, but somebody did! */
1400
1401         if (*ecode == OP_BRAZERO) ecode++;
1402         ecode += GET(ecode, 1);
1403         while (*ecode == OP_ALT) ecode += GET(ecode, 1);
1404         ecode += 1 + LINK_SIZE - PRIV(OP_lengths)[condcode];
1405         }
1406
1407       /* PCRE doesn't allow the effect of (*THEN) to escape beyond an
1408       assertion; it is therefore treated as NOMATCH. Any other return is an
1409       error. */
1410
1411       else if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN)
1412         {
1413         RRETURN(rrc);         /* Need braces because of following else */
1414         }
1415       break;
1416       }
1417
1418     /* Choose branch according to the condition */
1419
1420     ecode += condition? PRIV(OP_lengths)[condcode] : codelink;
1421
1422     /* We are now at the branch that is to be obeyed. As there is only one, we
1423     can use tail recursion to avoid using another stack frame, except when
1424     there is unlimited repeat of a possibly empty group. In the latter case, a
1425     recursive call to match() is always required, unless the second alternative
1426     doesn't exist, in which case we can just plough on. Note that, for
1427     compatibility with Perl, the | in a conditional group is NOT treated as
1428     creating two alternatives. If a THEN is encountered in the branch, it
1429     propagates out to the enclosing alternative (unless nested in a deeper set
1430     of alternatives, of course). */
1431
1432     if (condition || ecode[-(1+LINK_SIZE)] == OP_ALT)
1433       {
1434       if (op != OP_SCOND)
1435         {
1436         goto TAIL_RECURSE;
1437         }
1438
1439       md->match_function_type = MATCH_CBEGROUP;
1440       RMATCH(eptr, ecode, offset_top, md, eptrb, RM49);
1441       RRETURN(rrc);
1442       }
1443
1444      /* Condition false & no alternative; continue after the group. */
1445
1446     else
1447       {
1448       }
1449     break;
1450
1451
1452     /* Before OP_ACCEPT there may be any number of OP_CLOSE opcodes,
1453     to close any currently open capturing brackets. */
1454
1455     case OP_CLOSE:
1456     number = GET2(ecode, 1);   /* Must be less than 65536 */
1457     offset = number << 1;
1458
1459 #ifdef PCRE_DEBUG
1460       printf("end bracket %d at *ACCEPT", number);
1461       printf("\n");
1462 #endif
1463
1464     md->capture_last = (md->capture_last & OVFLMASK) | number;
1465     if (offset >= md->offset_max) md->capture_last |= OVFLBIT; else
1466       {
1467       md->offset_vector[offset] =
1468         md->offset_vector[md->offset_end - number];
1469       md->offset_vector[offset+1] = (int)(eptr - md->start_subject);
1470       if (offset_top <= offset) offset_top = offset + 2;
1471       }
1472     ecode += 1 + IMM2_SIZE;
1473     break;
1474
1475
1476     /* End of the pattern, either real or forced. */
1477
1478     case OP_END:
1479     case OP_ACCEPT:
1480     case OP_ASSERT_ACCEPT:
1481
1482     /* If we have matched an empty string, fail if not in an assertion and not
1483     in a recursion if either PCRE_NOTEMPTY is set, or if PCRE_NOTEMPTY_ATSTART
1484     is set and we have matched at the start of the subject. In both cases,
1485     backtracking will then try other alternatives, if any. */
1486
1487     if (eptr == mstart && op != OP_ASSERT_ACCEPT &&
1488          md->recursive == NULL &&
1489          (md->notempty ||
1490            (md->notempty_atstart &&
1491              mstart == md->start_subject + md->start_offset)))
1492       RRETURN(MATCH_NOMATCH);
1493
1494     /* Otherwise, we have a match. */
1495
1496     md->end_match_ptr = eptr;           /* Record where we ended */
1497     md->end_offset_top = offset_top;    /* and how many extracts were taken */
1498     md->start_match_ptr = mstart;       /* and the start (\K can modify) */
1499
1500     /* For some reason, the macros don't work properly if an expression is
1501     given as the argument to RRETURN when the heap is in use. */
1502
1503     rrc = (op == OP_END)? MATCH_MATCH : MATCH_ACCEPT;
1504     RRETURN(rrc);
1505
1506     /* Assertion brackets. Check the alternative branches in turn - the
1507     matching won't pass the KET for an assertion. If any one branch matches,
1508     the assertion is true. Lookbehind assertions have an OP_REVERSE item at the
1509     start of each branch to move the current point backwards, so the code at
1510     this level is identical to the lookahead case. When the assertion is part
1511     of a condition, we want to return immediately afterwards. The caller of
1512     this incarnation of the match() function will have set MATCH_CONDASSERT in
1513     md->match_function type, and one of these opcodes will be the first opcode
1514     that is processed. We use a local variable that is preserved over calls to
1515     match() to remember this case. */
1516
1517     case OP_ASSERT:
1518     case OP_ASSERTBACK:
1519     save_mark = md->mark;
1520     if (md->match_function_type == MATCH_CONDASSERT)
1521       {
1522       condassert = TRUE;
1523       md->match_function_type = 0;
1524       }
1525     else condassert = FALSE;
1526
1527     /* Loop for each branch */
1528
1529     do
1530       {
1531       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, NULL, RM4);
1532
1533       /* A match means that the assertion is true; break out of the loop
1534       that matches its alternatives. */
1535
1536       if (rrc == MATCH_MATCH || rrc == MATCH_ACCEPT)
1537         {
1538         mstart = md->start_match_ptr;   /* In case \K reset it */
1539         break;
1540         }
1541
1542       /* If not matched, restore the previous mark setting. */
1543
1544       md->mark = save_mark;
1545
1546       /* See comment in the code for capturing groups above about handling
1547       THEN. */
1548
1549       if (rrc == MATCH_THEN)
1550         {
1551         next = ecode + GET(ecode,1);
1552         if (md->start_match_ptr < next &&
1553             (*ecode == OP_ALT || *next == OP_ALT))
1554           rrc = MATCH_NOMATCH;
1555         }
1556
1557       /* Anything other than NOMATCH causes the entire assertion to fail,
1558       passing back the return code. This includes COMMIT, SKIP, PRUNE and an
1559       uncaptured THEN, which means they take their normal effect. This
1560       consistent approach does not always have exactly the same effect as in
1561       Perl. */
1562
1563       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1564       ecode += GET(ecode, 1);
1565       }
1566     while (*ecode == OP_ALT);   /* Continue for next alternative */
1567
1568     /* If we have tried all the alternative branches, the assertion has
1569     failed. If not, we broke out after a match. */
1570
1571     if (*ecode == OP_KET) RRETURN(MATCH_NOMATCH);
1572
1573     /* If checking an assertion for a condition, return MATCH_MATCH. */
1574
1575     if (condassert) RRETURN(MATCH_MATCH);
1576
1577     /* Continue from after a successful assertion, updating the offsets high
1578     water mark, since extracts may have been taken during the assertion. */
1579
1580     do ecode += GET(ecode,1); while (*ecode == OP_ALT);
1581     ecode += 1 + LINK_SIZE;
1582     offset_top = md->end_offset_top;
1583     continue;
1584
1585     /* Negative assertion: all branches must fail to match for the assertion to
1586     succeed. */
1587
1588     case OP_ASSERT_NOT:
1589     case OP_ASSERTBACK_NOT:
1590     save_mark = md->mark;
1591     if (md->match_function_type == MATCH_CONDASSERT)
1592       {
1593       condassert = TRUE;
1594       md->match_function_type = 0;
1595       }
1596     else condassert = FALSE;
1597
1598     /* Loop for each alternative branch. */
1599
1600     do
1601       {
1602       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, NULL, RM5);
1603       md->mark = save_mark;   /* Always restore the mark setting */
1604
1605       switch(rrc)
1606         {
1607         case MATCH_MATCH:            /* A successful match means */
1608         case MATCH_ACCEPT:           /* the assertion has failed. */
1609         RRETURN(MATCH_NOMATCH);
1610
1611         case MATCH_NOMATCH:          /* Carry on with next branch */
1612         break;
1613
1614         /* See comment in the code for capturing groups above about handling
1615         THEN. */
1616
1617         case MATCH_THEN:
1618         next = ecode + GET(ecode,1);
1619         if (md->start_match_ptr < next &&
1620             (*ecode == OP_ALT || *next == OP_ALT))
1621           {
1622           rrc = MATCH_NOMATCH;
1623           break;
1624           }
1625         /* Otherwise fall through. */
1626
1627         /* COMMIT, SKIP, PRUNE, and an uncaptured THEN cause the whole
1628         assertion to fail to match, without considering any more alternatives.
1629         Failing to match means the assertion is true. This is a consistent
1630         approach, but does not always have the same effect as in Perl. */
1631
1632         case MATCH_COMMIT:
1633         case MATCH_SKIP:
1634         case MATCH_SKIP_ARG:
1635         case MATCH_PRUNE:
1636         do ecode += GET(ecode,1); while (*ecode == OP_ALT);
1637         goto NEG_ASSERT_TRUE;   /* Break out of alternation loop */
1638
1639         /* Anything else is an error */
1640
1641         default:
1642         RRETURN(rrc);
1643         }
1644
1645       /* Continue with next branch */
1646
1647       ecode += GET(ecode,1);
1648       }
1649     while (*ecode == OP_ALT);
1650
1651     /* All branches in the assertion failed to match. */
1652
1653     NEG_ASSERT_TRUE:
1654     if (condassert) RRETURN(MATCH_MATCH);  /* Condition assertion */
1655     ecode += 1 + LINK_SIZE;                /* Continue with current branch */
1656     continue;
1657
1658     /* Move the subject pointer back. This occurs only at the start of
1659     each branch of a lookbehind assertion. If we are too close to the start to
1660     move back, this match function fails. When working with UTF-8 we move
1661     back a number of characters, not bytes. */
1662
1663     case OP_REVERSE:
1664 #ifdef SUPPORT_UTF
1665     if (utf)
1666       {
1667       i = GET(ecode, 1);
1668       while (i-- > 0)
1669         {
1670         eptr--;
1671         if (eptr < md->start_subject) RRETURN(MATCH_NOMATCH);
1672         BACKCHAR(eptr);
1673         }
1674       }
1675     else
1676 #endif
1677
1678     /* No UTF-8 support, or not in UTF-8 mode: count is byte count */
1679
1680       {
1681       eptr -= GET(ecode, 1);
1682       if (eptr < md->start_subject) RRETURN(MATCH_NOMATCH);
1683       }
1684
1685     /* Save the earliest consulted character, then skip to next op code */
1686
1687     if (eptr < md->start_used_ptr) md->start_used_ptr = eptr;
1688     ecode += 1 + LINK_SIZE;
1689     break;
1690
1691     /* The callout item calls an external function, if one is provided, passing
1692     details of the match so far. This is mainly for debugging, though the
1693     function is able to force a failure. */
1694
1695     case OP_CALLOUT:
1696     if (PUBL(callout) != NULL)
1697       {
1698       PUBL(callout_block) cb;
1699       cb.version          = 2;   /* Version 1 of the callout block */
1700       cb.callout_number   = ecode[1];
1701       cb.offset_vector    = md->offset_vector;
1702 #if defined COMPILE_PCRE8
1703       cb.subject          = (PCRE_SPTR)md->start_subject;
1704 #elif defined COMPILE_PCRE16
1705       cb.subject          = (PCRE_SPTR16)md->start_subject;
1706 #elif defined COMPILE_PCRE32
1707       cb.subject          = (PCRE_SPTR32)md->start_subject;
1708 #endif
1709       cb.subject_length   = (int)(md->end_subject - md->start_subject);
1710       cb.start_match      = (int)(mstart - md->start_subject);
1711       cb.current_position = (int)(eptr - md->start_subject);
1712       cb.pattern_position = GET(ecode, 2);
1713       cb.next_item_length = GET(ecode, 2 + LINK_SIZE);
1714       cb.capture_top      = offset_top/2;
1715       cb.capture_last     = md->capture_last & CAPLMASK;
1716       /* Internal change requires this for API compatibility. */
1717       if (cb.capture_last == 0) cb.capture_last = -1;
1718       cb.callout_data     = md->callout_data;
1719       cb.mark             = md->nomatch_mark;
1720       if ((rrc = (*PUBL(callout))(&cb)) > 0) RRETURN(MATCH_NOMATCH);
1721       if (rrc < 0) RRETURN(rrc);
1722       }
1723     ecode += 2 + 2*LINK_SIZE;
1724     break;
1725
1726     /* Recursion either matches the current regex, or some subexpression. The
1727     offset data is the offset to the starting bracket from the start of the
1728     whole pattern. (This is so that it works from duplicated subpatterns.)
1729
1730     The state of the capturing groups is preserved over recursion, and
1731     re-instated afterwards. We don't know how many are started and not yet
1732     finished (offset_top records the completed total) so we just have to save
1733     all the potential data. There may be up to 65535 such values, which is too
1734     large to put on the stack, but using malloc for small numbers seems
1735     expensive. As a compromise, the stack is used when there are no more than
1736     REC_STACK_SAVE_MAX values to store; otherwise malloc is used.
1737
1738     There are also other values that have to be saved. We use a chained
1739     sequence of blocks that actually live on the stack. Thanks to Robin Houston
1740     for the original version of this logic. It has, however, been hacked around
1741     a lot, so he is not to blame for the current way it works. */
1742
1743     case OP_RECURSE:
1744       {
1745       recursion_info *ri;
1746       unsigned int recno;
1747
1748       callpat = md->start_code + GET(ecode, 1);
1749       recno = (callpat == md->start_code)? 0 :
1750         GET2(callpat, 1 + LINK_SIZE);
1751
1752       /* Check for repeating a recursion without advancing the subject pointer.
1753       This should catch convoluted mutual recursions. (Some simple cases are
1754       caught at compile time.) */
1755
1756       for (ri = md->recursive; ri != NULL; ri = ri->prevrec)
1757         if (recno == ri->group_num && eptr == ri->subject_position)
1758           RRETURN(PCRE_ERROR_RECURSELOOP);
1759
1760       /* Add to "recursing stack" */
1761
1762       new_recursive.group_num = recno;
1763       new_recursive.saved_capture_last = md->capture_last;
1764       new_recursive.subject_position = eptr;
1765       new_recursive.prevrec = md->recursive;
1766       md->recursive = &new_recursive;
1767
1768       /* Where to continue from afterwards */
1769
1770       ecode += 1 + LINK_SIZE;
1771
1772       /* Now save the offset data */
1773
1774       new_recursive.saved_max = md->offset_end;
1775       if (new_recursive.saved_max <= REC_STACK_SAVE_MAX)
1776         new_recursive.offset_save = stacksave;
1777       else
1778         {
1779         new_recursive.offset_save =
1780           (int *)(PUBL(malloc))(new_recursive.saved_max * sizeof(int));
1781         if (new_recursive.offset_save == NULL) RRETURN(PCRE_ERROR_NOMEMORY);
1782         }
1783       memcpy(new_recursive.offset_save, md->offset_vector,
1784             new_recursive.saved_max * sizeof(int));
1785
1786       /* OK, now we can do the recursion. After processing each alternative,
1787       restore the offset data and the last captured value. If there were nested
1788       recursions, md->recursive might be changed, so reset it before looping.
1789       */
1790
1791       DPRINTF(("Recursing into group %d\n", new_recursive.group_num));
1792       cbegroup = (*callpat >= OP_SBRA);
1793       do
1794         {
1795         if (cbegroup) md->match_function_type = MATCH_CBEGROUP;
1796         RMATCH(eptr, callpat + PRIV(OP_lengths)[*callpat], offset_top,
1797           md, eptrb, RM6);
1798         memcpy(md->offset_vector, new_recursive.offset_save,
1799             new_recursive.saved_max * sizeof(int));
1800         md->capture_last = new_recursive.saved_capture_last;
1801         md->recursive = new_recursive.prevrec;
1802         if (rrc == MATCH_MATCH || rrc == MATCH_ACCEPT)
1803           {
1804           DPRINTF(("Recursion matched\n"));
1805           if (new_recursive.offset_save != stacksave)
1806             (PUBL(free))(new_recursive.offset_save);
1807
1808           /* Set where we got to in the subject, and reset the start in case
1809           it was changed by \K. This *is* propagated back out of a recursion,
1810           for Perl compatibility. */
1811
1812           eptr = md->end_match_ptr;
1813           mstart = md->start_match_ptr;
1814           goto RECURSION_MATCHED;        /* Exit loop; end processing */
1815           }
1816
1817         /* PCRE does not allow THEN, SKIP, PRUNE or COMMIT to escape beyond a
1818         recursion; they cause a NOMATCH for the entire recursion. These codes
1819         are defined in a range that can be tested for. */
1820
1821         if (rrc >= MATCH_BACKTRACK_MIN && rrc <= MATCH_BACKTRACK_MAX)
1822           RRETURN(MATCH_NOMATCH);
1823
1824         /* Any return code other than NOMATCH is an error. */
1825
1826         if (rrc != MATCH_NOMATCH)
1827           {
1828           DPRINTF(("Recursion gave error %d\n", rrc));
1829           if (new_recursive.offset_save != stacksave)
1830             (PUBL(free))(new_recursive.offset_save);
1831           RRETURN(rrc);
1832           }
1833
1834         md->recursive = &new_recursive;
1835         callpat += GET(callpat, 1);
1836         }
1837       while (*callpat == OP_ALT);
1838
1839       DPRINTF(("Recursion didn't match\n"));
1840       md->recursive = new_recursive.prevrec;
1841       if (new_recursive.offset_save != stacksave)
1842         (PUBL(free))(new_recursive.offset_save);
1843       RRETURN(MATCH_NOMATCH);
1844       }
1845
1846     RECURSION_MATCHED:
1847     break;
1848
1849     /* An alternation is the end of a branch; scan along to find the end of the
1850     bracketed group and go to there. */
1851
1852     case OP_ALT:
1853     do ecode += GET(ecode,1); while (*ecode == OP_ALT);
1854     break;
1855
1856     /* BRAZERO, BRAMINZERO and SKIPZERO occur just before a bracket group,
1857     indicating that it may occur zero times. It may repeat infinitely, or not
1858     at all - i.e. it could be ()* or ()? or even (){0} in the pattern. Brackets
1859     with fixed upper repeat limits are compiled as a number of copies, with the
1860     optional ones preceded by BRAZERO or BRAMINZERO. */
1861
1862     case OP_BRAZERO:
1863     next = ecode + 1;
1864     RMATCH(eptr, next, offset_top, md, eptrb, RM10);
1865     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1866     do next += GET(next, 1); while (*next == OP_ALT);
1867     ecode = next + 1 + LINK_SIZE;
1868     break;
1869
1870     case OP_BRAMINZERO:
1871     next = ecode + 1;
1872     do next += GET(next, 1); while (*next == OP_ALT);
1873     RMATCH(eptr, next + 1+LINK_SIZE, offset_top, md, eptrb, RM11);
1874     if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1875     ecode++;
1876     break;
1877
1878     case OP_SKIPZERO:
1879     next = ecode+1;
1880     do next += GET(next,1); while (*next == OP_ALT);
1881     ecode = next + 1 + LINK_SIZE;
1882     break;
1883
1884     /* BRAPOSZERO occurs before a possessive bracket group. Don't do anything
1885     here; just jump to the group, with allow_zero set TRUE. */
1886
1887     case OP_BRAPOSZERO:
1888     op = *(++ecode);
1889     allow_zero = TRUE;
1890     if (op == OP_CBRAPOS || op == OP_SCBRAPOS) goto POSSESSIVE_CAPTURE;
1891       goto POSSESSIVE_NON_CAPTURE;
1892
1893     /* End of a group, repeated or non-repeating. */
1894
1895     case OP_KET:
1896     case OP_KETRMIN:
1897     case OP_KETRMAX:
1898     case OP_KETRPOS:
1899     prev = ecode - GET(ecode, 1);
1900
1901     /* If this was a group that remembered the subject start, in order to break
1902     infinite repeats of empty string matches, retrieve the subject start from
1903     the chain. Otherwise, set it NULL. */
1904
1905     if (*prev >= OP_SBRA || *prev == OP_ONCE)
1906       {
1907       saved_eptr = eptrb->epb_saved_eptr;   /* Value at start of group */
1908       eptrb = eptrb->epb_prev;              /* Backup to previous group */
1909       }
1910     else saved_eptr = NULL;
1911
1912     /* If we are at the end of an assertion group or a non-capturing atomic
1913     group, stop matching and return MATCH_MATCH, but record the current high
1914     water mark for use by positive assertions. We also need to record the match
1915     start in case it was changed by \K. */
1916
1917     if ((*prev >= OP_ASSERT && *prev <= OP_ASSERTBACK_NOT) ||
1918          *prev == OP_ONCE_NC)
1919       {
1920       md->end_match_ptr = eptr;      /* For ONCE_NC */
1921       md->end_offset_top = offset_top;
1922       md->start_match_ptr = mstart;
1923       RRETURN(MATCH_MATCH);         /* Sets md->mark */
1924       }
1925
1926     /* For capturing groups we have to check the group number back at the start
1927     and if necessary complete handling an extraction by setting the offsets and
1928     bumping the high water mark. Whole-pattern recursion is coded as a recurse
1929     into group 0, so it won't be picked up here. Instead, we catch it when the
1930     OP_END is reached. Other recursion is handled here. We just have to record
1931     the current subject position and start match pointer and give a MATCH
1932     return. */
1933
1934     if (*prev == OP_CBRA || *prev == OP_SCBRA ||
1935         *prev == OP_CBRAPOS || *prev == OP_SCBRAPOS)
1936       {
1937       number = GET2(prev, 1+LINK_SIZE);
1938       offset = number << 1;
1939
1940 #ifdef PCRE_DEBUG
1941       printf("end bracket %d", number);
1942       printf("\n");
1943 #endif
1944
1945       /* Handle a recursively called group. */
1946
1947       if (md->recursive != NULL && md->recursive->group_num == number)
1948         {
1949         md->end_match_ptr = eptr;
1950         md->start_match_ptr = mstart;
1951         RRETURN(MATCH_MATCH);
1952         }
1953
1954       /* Deal with capturing */
1955
1956       md->capture_last = (md->capture_last & OVFLMASK) | number;
1957       if (offset >= md->offset_max) md->capture_last |= OVFLBIT; else
1958         {
1959         /* If offset is greater than offset_top, it means that we are
1960         "skipping" a capturing group, and that group's offsets must be marked
1961         unset. In earlier versions of PCRE, all the offsets were unset at the
1962         start of matching, but this doesn't work because atomic groups and
1963         assertions can cause a value to be set that should later be unset.
1964         Example: matching /(?>(a))b|(a)c/ against "ac". This sets group 1 as
1965         part of the atomic group, but this is not on the final matching path,
1966         so must be unset when 2 is set. (If there is no group 2, there is no
1967         problem, because offset_top will then be 2, indicating no capture.) */
1968
1969         if (offset > offset_top)
1970           {
1971           register int *iptr = md->offset_vector + offset_top;
1972           register int *iend = md->offset_vector + offset;
1973           while (iptr < iend) *iptr++ = -1;
1974           }
1975
1976         /* Now make the extraction */
1977
1978         md->offset_vector[offset] =
1979           md->offset_vector[md->offset_end - number];
1980         md->offset_vector[offset+1] = (int)(eptr - md->start_subject);
1981         if (offset_top <= offset) offset_top = offset + 2;
1982         }
1983       }
1984
1985     /* For an ordinary non-repeating ket, just continue at this level. This
1986     also happens for a repeating ket if no characters were matched in the
1987     group. This is the forcible breaking of infinite loops as implemented in
1988     Perl 5.005. For a non-repeating atomic group that includes captures,
1989     establish a backup point by processing the rest of the pattern at a lower
1990     level. If this results in a NOMATCH return, pass MATCH_ONCE back to the
1991     original OP_ONCE level, thereby bypassing intermediate backup points, but
1992     resetting any captures that happened along the way. */
1993
1994     if (*ecode == OP_KET || eptr == saved_eptr)
1995       {
1996       if (*prev == OP_ONCE)
1997         {
1998         RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM12);
1999         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2000         md->once_target = prev;  /* Level at which to change to MATCH_NOMATCH */
2001         RRETURN(MATCH_ONCE);
2002         }
2003       ecode += 1 + LINK_SIZE;    /* Carry on at this level */
2004       break;
2005       }
2006
2007     /* OP_KETRPOS is a possessive repeating ket. Remember the current position,
2008     and return the MATCH_KETRPOS. This makes it possible to do the repeats one
2009     at a time from the outer level, thus saving stack. */
2010
2011     if (*ecode == OP_KETRPOS)
2012       {
2013       md->start_match_ptr = mstart;    /* In case \K reset it */
2014       md->end_match_ptr = eptr;
2015       md->end_offset_top = offset_top;
2016       RRETURN(MATCH_KETRPOS);
2017       }
2018
2019     /* The normal repeating kets try the rest of the pattern or restart from
2020     the preceding bracket, in the appropriate order. In the second case, we can
2021     use tail recursion to avoid using another stack frame, unless we have an
2022     an atomic group or an unlimited repeat of a group that can match an empty
2023     string. */
2024
2025     if (*ecode == OP_KETRMIN)
2026       {
2027       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM7);
2028       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2029       if (*prev == OP_ONCE)
2030         {
2031         RMATCH(eptr, prev, offset_top, md, eptrb, RM8);
2032         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2033         md->once_target = prev;  /* Level at which to change to MATCH_NOMATCH */
2034         RRETURN(MATCH_ONCE);
2035         }
2036       if (*prev >= OP_SBRA)    /* Could match an empty string */
2037         {
2038         RMATCH(eptr, prev, offset_top, md, eptrb, RM50);
2039         RRETURN(rrc);
2040         }
2041       ecode = prev;
2042       goto TAIL_RECURSE;
2043       }
2044     else  /* OP_KETRMAX */
2045       {
2046       RMATCH(eptr, prev, offset_top, md, eptrb, RM13);
2047       if (rrc == MATCH_ONCE && md->once_target == prev) rrc = MATCH_NOMATCH;
2048       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2049       if (*prev == OP_ONCE)
2050         {
2051         RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM9);
2052         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2053         md->once_target = prev;
2054         RRETURN(MATCH_ONCE);
2055         }
2056       ecode += 1 + LINK_SIZE;
2057       goto TAIL_RECURSE;
2058       }
2059     /* Control never gets here */
2060
2061     /* Not multiline mode: start of subject assertion, unless notbol. */
2062
2063     case OP_CIRC:
2064     if (md->notbol && eptr == md->start_subject) RRETURN(MATCH_NOMATCH);
2065
2066     /* Start of subject assertion */
2067
2068     case OP_SOD:
2069     if (eptr != md->start_subject) RRETURN(MATCH_NOMATCH);
2070     ecode++;
2071     break;
2072
2073     /* Multiline mode: start of subject unless notbol, or after any newline. */
2074
2075     case OP_CIRCM:
2076     if (md->notbol && eptr == md->start_subject) RRETURN(MATCH_NOMATCH);
2077     if (eptr != md->start_subject &&
2078         (eptr == md->end_subject || !WAS_NEWLINE(eptr)))
2079       RRETURN(MATCH_NOMATCH);
2080     ecode++;
2081     break;
2082
2083     /* Start of match assertion */
2084
2085     case OP_SOM:
2086     if (eptr != md->start_subject + md->start_offset) RRETURN(MATCH_NOMATCH);
2087     ecode++;
2088     break;
2089
2090     /* Reset the start of match point */
2091
2092     case OP_SET_SOM:
2093     mstart = eptr;
2094     ecode++;
2095     break;
2096
2097     /* Multiline mode: assert before any newline, or before end of subject
2098     unless noteol is set. */
2099
2100     case OP_DOLLM:
2101     if (eptr < md->end_subject)
2102       {
2103       if (!IS_NEWLINE(eptr))
2104         {
2105         if (md->partial != 0 &&
2106             eptr + 1 >= md->end_subject &&
2107             NLBLOCK->nltype == NLTYPE_FIXED &&
2108             NLBLOCK->nllen == 2 &&
2109             UCHAR21TEST(eptr) == NLBLOCK->nl[0])
2110           {
2111           md->hitend = TRUE;
2112           if (md->partial > 1) RRETURN(PCRE_ERROR_PARTIAL);
2113           }
2114         RRETURN(MATCH_NOMATCH);
2115         }
2116       }
2117     else
2118       {
2119       if (md->noteol) RRETURN(MATCH_NOMATCH);
2120       SCHECK_PARTIAL();
2121       }
2122     ecode++;
2123     break;
2124
2125     /* Not multiline mode: assert before a terminating newline or before end of
2126     subject unless noteol is set. */
2127
2128     case OP_DOLL:
2129     if (md->noteol) RRETURN(MATCH_NOMATCH);
2130     if (!md->endonly) goto ASSERT_NL_OR_EOS;
2131
2132     /* ... else fall through for endonly */
2133
2134     /* End of subject assertion (\z) */
2135
2136     case OP_EOD:
2137     if (eptr < md->end_subject) RRETURN(MATCH_NOMATCH);
2138     SCHECK_PARTIAL();
2139     ecode++;
2140     break;
2141
2142     /* End of subject or ending \n assertion (\Z) */
2143
2144     case OP_EODN:
2145     ASSERT_NL_OR_EOS:
2146     if (eptr < md->end_subject &&
2147         (!IS_NEWLINE(eptr) || eptr != md->end_subject - md->nllen))
2148       {
2149       if (md->partial != 0 &&
2150           eptr + 1 >= md->end_subject &&
2151           NLBLOCK->nltype == NLTYPE_FIXED &&
2152           NLBLOCK->nllen == 2 &&
2153           UCHAR21TEST(eptr) == NLBLOCK->nl[0])
2154         {
2155         md->hitend = TRUE;
2156         if (md->partial > 1) RRETURN(PCRE_ERROR_PARTIAL);
2157         }
2158       RRETURN(MATCH_NOMATCH);
2159       }
2160
2161     /* Either at end of string or \n before end. */
2162
2163     SCHECK_PARTIAL();
2164     ecode++;
2165     break;
2166
2167     /* Word boundary assertions */
2168
2169     case OP_NOT_WORD_BOUNDARY:
2170     case OP_WORD_BOUNDARY:
2171       {
2172
2173       /* Find out if the previous and current characters are "word" characters.
2174       It takes a bit more work in UTF-8 mode. Characters > 255 are assumed to
2175       be "non-word" characters. Remember the earliest consulted character for
2176       partial matching. */
2177
2178 #ifdef SUPPORT_UTF
2179       if (utf)
2180         {
2181         /* Get status of previous character */
2182
2183         if (eptr == md->start_subject) prev_is_word = FALSE; else
2184           {
2185           PCRE_PUCHAR lastptr = eptr - 1;
2186           BACKCHAR(lastptr);
2187           if (lastptr < md->start_used_ptr) md->start_used_ptr = lastptr;
2188           GETCHAR(c, lastptr);
2189 #ifdef SUPPORT_UCP
2190           if (md->use_ucp)
2191             {
2192             if (c == '_') prev_is_word = TRUE; else
2193               {
2194               int cat = UCD_CATEGORY(c);
2195               prev_is_word = (cat == ucp_L || cat == ucp_N);
2196               }
2197             }
2198           else
2199 #endif
2200           prev_is_word = c < 256 && (md->ctypes[c] & ctype_word) != 0;
2201           }
2202
2203         /* Get status of next character */
2204
2205         if (eptr >= md->end_subject)
2206           {
2207           SCHECK_PARTIAL();
2208           cur_is_word = FALSE;
2209           }
2210         else
2211           {
2212           GETCHAR(c, eptr);
2213 #ifdef SUPPORT_UCP
2214           if (md->use_ucp)
2215             {
2216             if (c == '_') cur_is_word = TRUE; else
2217               {
2218               int cat = UCD_CATEGORY(c);
2219               cur_is_word = (cat == ucp_L || cat == ucp_N);
2220               }
2221             }
2222           else
2223 #endif
2224           cur_is_word = c < 256 && (md->ctypes[c] & ctype_word) != 0;
2225           }
2226         }
2227       else
2228 #endif
2229
2230       /* Not in UTF-8 mode, but we may still have PCRE_UCP set, and for
2231       consistency with the behaviour of \w we do use it in this case. */
2232
2233         {
2234         /* Get status of previous character */
2235
2236         if (eptr == md->start_subject) prev_is_word = FALSE; else
2237           {
2238           if (eptr <= md->start_used_ptr) md->start_used_ptr = eptr - 1;
2239 #ifdef SUPPORT_UCP
2240           if (md->use_ucp)
2241             {
2242             c = eptr[-1];
2243             if (c == '_') prev_is_word = TRUE; else
2244               {
2245               int cat = UCD_CATEGORY(c);
2246               prev_is_word = (cat == ucp_L || cat == ucp_N);
2247               }
2248             }
2249           else
2250 #endif
2251           prev_is_word = MAX_255(eptr[-1])
2252             && ((md->ctypes[eptr[-1]] & ctype_word) != 0);
2253           }
2254
2255         /* Get status of next character */
2256
2257         if (eptr >= md->end_subject)
2258           {
2259           SCHECK_PARTIAL();
2260           cur_is_word = FALSE;
2261           }
2262         else
2263 #ifdef SUPPORT_UCP
2264         if (md->use_ucp)
2265           {
2266           c = *eptr;
2267           if (c == '_') cur_is_word = TRUE; else
2268             {
2269             int cat = UCD_CATEGORY(c);
2270             cur_is_word = (cat == ucp_L || cat == ucp_N);
2271             }
2272           }
2273         else
2274 #endif
2275         cur_is_word = MAX_255(*eptr)
2276           && ((md->ctypes[*eptr] & ctype_word) != 0);
2277         }
2278
2279       /* Now see if the situation is what we want */
2280
2281       if ((*ecode++ == OP_WORD_BOUNDARY)?
2282            cur_is_word == prev_is_word : cur_is_word != prev_is_word)
2283         RRETURN(MATCH_NOMATCH);
2284       }
2285     break;
2286
2287     /* Match any single character type except newline; have to take care with
2288     CRLF newlines and partial matching. */
2289
2290     case OP_ANY:
2291     if (IS_NEWLINE(eptr)) RRETURN(MATCH_NOMATCH);
2292     if (md->partial != 0 &&
2293         eptr + 1 >= md->end_subject &&
2294         NLBLOCK->nltype == NLTYPE_FIXED &&
2295         NLBLOCK->nllen == 2 &&
2296         UCHAR21TEST(eptr) == NLBLOCK->nl[0])
2297       {
2298       md->hitend = TRUE;
2299       if (md->partial > 1) RRETURN(PCRE_ERROR_PARTIAL);
2300       }
2301
2302     /* Fall through */
2303
2304     /* Match any single character whatsoever. */
2305
2306     case OP_ALLANY:
2307     if (eptr >= md->end_subject)   /* DO NOT merge the eptr++ here; it must */
2308       {                            /* not be updated before SCHECK_PARTIAL. */
2309       SCHECK_PARTIAL();
2310       RRETURN(MATCH_NOMATCH);
2311       }
2312     eptr++;
2313 #ifdef SUPPORT_UTF
2314     if (utf) ACROSSCHAR(eptr < md->end_subject, *eptr, eptr++);
2315 #endif
2316     ecode++;
2317     break;
2318
2319     /* Match a single byte, even in UTF-8 mode. This opcode really does match
2320     any byte, even newline, independent of the setting of PCRE_DOTALL. */
2321
2322     case OP_ANYBYTE:
2323     if (eptr >= md->end_subject)   /* DO NOT merge the eptr++ here; it must */
2324       {                            /* not be updated before SCHECK_PARTIAL. */
2325       SCHECK_PARTIAL();
2326       RRETURN(MATCH_NOMATCH);
2327       }
2328     eptr++;
2329     ecode++;
2330     break;
2331
2332     case OP_NOT_DIGIT:
2333     if (eptr >= md->end_subject)
2334       {
2335       SCHECK_PARTIAL();
2336       RRETURN(MATCH_NOMATCH);
2337       }
2338     GETCHARINCTEST(c, eptr);
2339     if (
2340 #if defined SUPPORT_UTF || !(defined COMPILE_PCRE8)
2341        c < 256 &&
2342 #endif
2343        (md->ctypes[c] & ctype_digit) != 0
2344        )
2345       RRETURN(MATCH_NOMATCH);
2346     ecode++;
2347     break;
2348
2349     case OP_DIGIT:
2350     if (eptr >= md->end_subject)
2351       {
2352       SCHECK_PARTIAL();
2353       RRETURN(MATCH_NOMATCH);
2354       }
2355     GETCHARINCTEST(c, eptr);
2356     if (
2357 #if defined SUPPORT_UTF || !(defined COMPILE_PCRE8)
2358        c > 255 ||
2359 #endif
2360        (md->ctypes[c] & ctype_digit) == 0
2361        )
2362       RRETURN(MATCH_NOMATCH);
2363     ecode++;
2364     break;
2365
2366     case OP_NOT_WHITESPACE:
2367     if (eptr >= md->end_subject)
2368       {
2369       SCHECK_PARTIAL();
2370       RRETURN(MATCH_NOMATCH);
2371       }
2372     GETCHARINCTEST(c, eptr);
2373     if (
2374 #if defined SUPPORT_UTF || !(defined COMPILE_PCRE8)
2375        c < 256 &&
2376 #endif
2377        (md->ctypes[c] & ctype_space) != 0
2378        )
2379       RRETURN(MATCH_NOMATCH);
2380     ecode++;
2381     break;
2382
2383     case OP_WHITESPACE:
2384     if (eptr >= md->end_subject)
2385       {
2386       SCHECK_PARTIAL();
2387       RRETURN(MATCH_NOMATCH);
2388       }
2389     GETCHARINCTEST(c, eptr);
2390     if (
2391 #if defined SUPPORT_UTF || !(defined COMPILE_PCRE8)
2392        c > 255 ||
2393 #endif
2394        (md->ctypes[c] & ctype_space) == 0
2395        )
2396       RRETURN(MATCH_NOMATCH);
2397     ecode++;
2398     break;
2399
2400     case OP_NOT_WORDCHAR:
2401     if (eptr >= md->end_subject)
2402       {
2403       SCHECK_PARTIAL();
2404       RRETURN(MATCH_NOMATCH);
2405       }
2406     GETCHARINCTEST(c, eptr);
2407     if (
2408 #if defined SUPPORT_UTF || !(defined COMPILE_PCRE8)
2409        c < 256 &&
2410 #endif
2411        (md->ctypes[c] & ctype_word) != 0
2412        )
2413       RRETURN(MATCH_NOMATCH);
2414     ecode++;
2415     break;
2416
2417     case OP_WORDCHAR:
2418     if (eptr >= md->end_subject)
2419       {
2420       SCHECK_PARTIAL();
2421       RRETURN(MATCH_NOMATCH);
2422       }
2423     GETCHARINCTEST(c, eptr);
2424     if (
2425 #if defined SUPPORT_UTF || !(defined COMPILE_PCRE8)
2426        c > 255 ||
2427 #endif
2428        (md->ctypes[c] & ctype_word) == 0
2429        )
2430       RRETURN(MATCH_NOMATCH);
2431     ecode++;
2432     break;
2433
2434     case OP_ANYNL:
2435     if (eptr >= md->end_subject)
2436       {
2437       SCHECK_PARTIAL();
2438       RRETURN(MATCH_NOMATCH);
2439       }
2440     GETCHARINCTEST(c, eptr);
2441     switch(c)
2442       {
2443       default: RRETURN(MATCH_NOMATCH);
2444
2445       case CHAR_CR:
2446       if (eptr >= md->end_subject)
2447         {
2448         SCHECK_PARTIAL();
2449         }
2450       else if (UCHAR21TEST(eptr) == CHAR_LF) eptr++;
2451       break;
2452
2453       case CHAR_LF:
2454       break;
2455
2456       case CHAR_VT:
2457       case CHAR_FF:
2458       case CHAR_NEL:
2459 #ifndef EBCDIC
2460       case 0x2028:
2461       case 0x2029:
2462 #endif  /* Not EBCDIC */
2463       if (md->bsr_anycrlf) RRETURN(MATCH_NOMATCH);
2464       break;
2465       }
2466     ecode++;
2467     break;
2468
2469     case OP_NOT_HSPACE:
2470     if (eptr >= md->end_subject)
2471       {
2472       SCHECK_PARTIAL();
2473       RRETURN(MATCH_NOMATCH);
2474       }
2475     GETCHARINCTEST(c, eptr);
2476     switch(c)
2477       {
2478       HSPACE_CASES: RRETURN(MATCH_NOMATCH);  /* Byte and multibyte cases */
2479       default: break;
2480       }
2481     ecode++;
2482     break;
2483
2484     case OP_HSPACE:
2485     if (eptr >= md->end_subject)
2486       {
2487       SCHECK_PARTIAL();
2488       RRETURN(MATCH_NOMATCH);
2489       }
2490     GETCHARINCTEST(c, eptr);
2491     switch(c)
2492       {
2493       HSPACE_CASES: break;  /* Byte and multibyte cases */
2494       default: RRETURN(MATCH_NOMATCH);
2495       }
2496     ecode++;
2497     break;
2498
2499     case OP_NOT_VSPACE:
2500     if (eptr >= md->end_subject)
2501       {
2502       SCHECK_PARTIAL();
2503       RRETURN(MATCH_NOMATCH);
2504       }
2505     GETCHARINCTEST(c, eptr);
2506     switch(c)
2507       {
2508       VSPACE_CASES: RRETURN(MATCH_NOMATCH);
2509       default: break;
2510       }
2511     ecode++;
2512     break;
2513
2514     case OP_VSPACE:
2515     if (eptr >= md->end_subject)
2516       {
2517       SCHECK_PARTIAL();
2518       RRETURN(MATCH_NOMATCH);
2519       }
2520     GETCHARINCTEST(c, eptr);
2521     switch(c)
2522       {
2523       VSPACE_CASES: break;
2524       default: RRETURN(MATCH_NOMATCH);
2525       }
2526     ecode++;
2527     break;
2528
2529 #ifdef SUPPORT_UCP
2530     /* Check the next character by Unicode property. We will get here only
2531     if the support is in the binary; otherwise a compile-time error occurs. */
2532
2533     case OP_PROP:
2534     case OP_NOTPROP:
2535     if (eptr >= md->end_subject)
2536       {
2537       SCHECK_PARTIAL();
2538       RRETURN(MATCH_NOMATCH);
2539       }
2540     GETCHARINCTEST(c, eptr);
2541       {
2542       const pcre_uint32 *cp;
2543       const ucd_record *prop = GET_UCD(c);
2544
2545       switch(ecode[1])
2546         {
2547         case PT_ANY:
2548         if (op == OP_NOTPROP) RRETURN(MATCH_NOMATCH);
2549         break;
2550
2551         case PT_LAMP:
2552         if ((prop->chartype == ucp_Lu ||
2553              prop->chartype == ucp_Ll ||
2554              prop->chartype == ucp_Lt) == (op == OP_NOTPROP))
2555           RRETURN(MATCH_NOMATCH);
2556         break;
2557
2558         case PT_GC:
2559         if ((ecode[2] != PRIV(ucp_gentype)[prop->chartype]) == (op == OP_PROP))
2560           RRETURN(MATCH_NOMATCH);
2561         break;
2562
2563         case PT_PC:
2564         if ((ecode[2] != prop->chartype) == (op == OP_PROP))
2565           RRETURN(MATCH_NOMATCH);
2566         break;
2567
2568         case PT_SC:
2569         if ((ecode[2] != prop->script) == (op == OP_PROP))
2570           RRETURN(MATCH_NOMATCH);
2571         break;
2572
2573         /* These are specials */
2574
2575         case PT_ALNUM:
2576         if ((PRIV(ucp_gentype)[prop->chartype] == ucp_L ||
2577              PRIV(ucp_gentype)[prop->chartype] == ucp_N) == (op == OP_NOTPROP))
2578           RRETURN(MATCH_NOMATCH);
2579         break;
2580
2581         /* Perl space used to exclude VT, but from Perl 5.18 it is included,
2582         which means that Perl space and POSIX space are now identical. PCRE
2583         was changed at release 8.34. */
2584
2585         case PT_SPACE:    /* Perl space */
2586         case PT_PXSPACE:  /* POSIX space */
2587         switch(c)
2588           {
2589           HSPACE_CASES:
2590           VSPACE_CASES:
2591           if (op == OP_NOTPROP) RRETURN(MATCH_NOMATCH);
2592           break;
2593
2594           default:
2595           if ((PRIV(ucp_gentype)[prop->chartype] == ucp_Z) ==
2596             (op == OP_NOTPROP)) RRETURN(MATCH_NOMATCH);
2597           break;
2598           }
2599         break;
2600
2601         case PT_WORD:
2602         if ((PRIV(ucp_gentype)[prop->chartype] == ucp_L ||
2603              PRIV(ucp_gentype)[prop->chartype] == ucp_N ||
2604              c == CHAR_UNDERSCORE) == (op == OP_NOTPROP))
2605           RRETURN(MATCH_NOMATCH);
2606         break;
2607
2608         case PT_CLIST:
2609         cp = PRIV(ucd_caseless_sets) + ecode[2];
2610         for (;;)
2611           {
2612           if (c < *cp)
2613             { if (op == OP_PROP) { RRETURN(MATCH_NOMATCH); } else break; }
2614           if (c == *cp++)
2615             { if (op == OP_PROP) break; else { RRETURN(MATCH_NOMATCH); } }
2616           }
2617         break;
2618
2619         case PT_UCNC:
2620         if ((c == CHAR_DOLLAR_SIGN || c == CHAR_COMMERCIAL_AT ||
2621              c == CHAR_GRAVE_ACCENT || (c >= 0xa0 && c <= 0xd7ff) ||
2622              c >= 0xe000) == (op == OP_NOTPROP))
2623           RRETURN(MATCH_NOMATCH);
2624         break;
2625
2626         /* This should never occur */
2627
2628         default:
2629         RRETURN(PCRE_ERROR_INTERNAL);
2630         }
2631
2632       ecode += 3;
2633       }
2634     break;
2635
2636     /* Match an extended Unicode sequence. We will get here only if the support
2637     is in the binary; otherwise a compile-time error occurs. */
2638
2639     case OP_EXTUNI:
2640     if (eptr >= md->end_subject)
2641       {
2642       SCHECK_PARTIAL();
2643       RRETURN(MATCH_NOMATCH);
2644       }
2645     else
2646       {
2647       int lgb, rgb;
2648       GETCHARINCTEST(c, eptr);
2649       lgb = UCD_GRAPHBREAK(c);
2650       while (eptr < md->end_subject)
2651         {
2652         int len = 1;
2653         if (!utf) c = *eptr; else { GETCHARLEN(c, eptr, len); }
2654         rgb = UCD_GRAPHBREAK(c);
2655         if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
2656         lgb = rgb;
2657         eptr += len;
2658         }
2659       }
2660     CHECK_PARTIAL();
2661     ecode++;
2662     break;
2663 #endif  /* SUPPORT_UCP */
2664
2665
2666     /* Match a back reference, possibly repeatedly. Look past the end of the
2667     item to see if there is repeat information following. The code is similar
2668     to that for character classes, but repeated for efficiency. Then obey
2669     similar code to character type repeats - written out again for speed.
2670     However, if the referenced string is the empty string, always treat
2671     it as matched, any number of times (otherwise there could be infinite
2672     loops). If the reference is unset, there are two possibilities:
2673
2674     (a) In the default, Perl-compatible state, set the length negative;
2675     this ensures that every attempt at a match fails. We can't just fail
2676     here, because of the possibility of quantifiers with zero minima.
2677
2678     (b) If the JavaScript compatibility flag is set, set the length to zero
2679     so that the back reference matches an empty string.
2680
2681     Otherwise, set the length to the length of what was matched by the
2682     referenced subpattern.
2683
2684     The OP_REF and OP_REFI opcodes are used for a reference to a numbered group
2685     or to a non-duplicated named group. For a duplicated named group, OP_DNREF
2686     and OP_DNREFI are used. In this case we must scan the list of groups to
2687     which the name refers, and use the first one that is set. */
2688
2689     case OP_DNREF:
2690     case OP_DNREFI:
2691     caseless = op == OP_DNREFI;
2692       {
2693       int count = GET2(ecode, 1+IMM2_SIZE);
2694       pcre_uchar *slot = md->name_table + GET2(ecode, 1) * md->name_entry_size;
2695       ecode += 1 + 2*IMM2_SIZE;
2696
2697       /* Setting the default length first and initializing 'offset' avoids
2698       compiler warnings in the REF_REPEAT code. */
2699
2700       length = (md->jscript_compat)? 0 : -1;
2701       offset = 0;
2702
2703       while (count-- > 0)
2704         {
2705         offset = GET2(slot, 0) << 1;
2706         if (offset < offset_top && md->offset_vector[offset] >= 0)
2707           {
2708           length = md->offset_vector[offset+1] - md->offset_vector[offset];
2709           break;
2710           }
2711         slot += md->name_entry_size;
2712         }
2713       }
2714     goto REF_REPEAT;
2715
2716     case OP_REF:
2717     case OP_REFI:
2718     caseless = op == OP_REFI;
2719     offset = GET2(ecode, 1) << 1;               /* Doubled ref number */
2720     ecode += 1 + IMM2_SIZE;
2721     if (offset >= offset_top || md->offset_vector[offset] < 0)
2722       length = (md->jscript_compat)? 0 : -1;
2723     else
2724       length = md->offset_vector[offset+1] - md->offset_vector[offset];
2725
2726     /* Set up for repetition, or handle the non-repeated case */
2727
2728     REF_REPEAT:
2729     switch (*ecode)
2730       {
2731       case OP_CRSTAR:
2732       case OP_CRMINSTAR:
2733       case OP_CRPLUS:
2734       case OP_CRMINPLUS:
2735       case OP_CRQUERY:
2736       case OP_CRMINQUERY:
2737       c = *ecode++ - OP_CRSTAR;
2738       minimize = (c & 1) != 0;
2739       min = rep_min[c];                 /* Pick up values from tables; */
2740       max = rep_max[c];                 /* zero for max => infinity */
2741       if (max == 0) max = INT_MAX;
2742       break;
2743
2744       case OP_CRRANGE:
2745       case OP_CRMINRANGE:
2746       minimize = (*ecode == OP_CRMINRANGE);
2747       min = GET2(ecode, 1);
2748       max = GET2(ecode, 1 + IMM2_SIZE);
2749       if (max == 0) max = INT_MAX;
2750       ecode += 1 + 2 * IMM2_SIZE;
2751       break;
2752
2753       default:               /* No repeat follows */
2754       if ((length = match_ref(offset, eptr, length, md, caseless)) < 0)
2755         {
2756         if (length == -2) eptr = md->end_subject;   /* Partial match */
2757         CHECK_PARTIAL();
2758         RRETURN(MATCH_NOMATCH);
2759         }
2760       eptr += length;
2761       continue;              /* With the main loop */
2762       }
2763
2764     /* Handle repeated back references. If the length of the reference is
2765     zero, just continue with the main loop. If the length is negative, it
2766     means the reference is unset in non-Java-compatible mode. If the minimum is
2767     zero, we can continue at the same level without recursion. For any other
2768     minimum, carrying on will result in NOMATCH. */
2769
2770     if (length == 0) continue;
2771     if (length < 0 && min == 0) continue;
2772
2773     /* First, ensure the minimum number of matches are present. We get back
2774     the length of the reference string explicitly rather than passing the
2775     address of eptr, so that eptr can be a register variable. */
2776
2777     for (i = 1; i <= min; i++)
2778       {
2779       int slength;
2780       if ((slength = match_ref(offset, eptr, length, md, caseless)) < 0)
2781         {
2782         if (slength == -2) eptr = md->end_subject;   /* Partial match */
2783         CHECK_PARTIAL();
2784         RRETURN(MATCH_NOMATCH);
2785         }
2786       eptr += slength;
2787       }
2788
2789     /* If min = max, continue at the same level without recursion.
2790     They are not both allowed to be zero. */
2791
2792     if (min == max) continue;
2793
2794     /* If minimizing, keep trying and advancing the pointer */
2795
2796     if (minimize)
2797       {
2798       for (fi = min;; fi++)
2799         {
2800         int slength;
2801         RMATCH(eptr, ecode, offset_top, md, eptrb, RM14);
2802         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2803         if (fi >= max) RRETURN(MATCH_NOMATCH);
2804         if ((slength = match_ref(offset, eptr, length, md, caseless)) < 0)
2805           {
2806           if (slength == -2) eptr = md->end_subject;   /* Partial match */
2807           CHECK_PARTIAL();
2808           RRETURN(MATCH_NOMATCH);
2809           }
2810         eptr += slength;
2811         }
2812       /* Control never gets here */
2813       }
2814
2815     /* If maximizing, find the longest string and work backwards */
2816
2817     else
2818       {
2819       pp = eptr;
2820       for (i = min; i < max; i++)
2821         {
2822         int slength;
2823         if ((slength = match_ref(offset, eptr, length, md, caseless)) < 0)
2824           {
2825           /* Can't use CHECK_PARTIAL because we don't want to update eptr in
2826           the soft partial matching case. */
2827
2828           if (slength == -2 && md->partial != 0 &&
2829               md->end_subject > md->start_used_ptr)
2830             {
2831             md->hitend = TRUE;
2832             if (md->partial > 1) RRETURN(PCRE_ERROR_PARTIAL);
2833             }
2834           break;
2835           }
2836         eptr += slength;
2837         }
2838
2839       while (eptr >= pp)
2840         {
2841         RMATCH(eptr, ecode, offset_top, md, eptrb, RM15);
2842         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2843         eptr -= length;
2844         }
2845       RRETURN(MATCH_NOMATCH);
2846       }
2847     /* Control never gets here */
2848
2849     /* Match a bit-mapped character class, possibly repeatedly. This op code is
2850     used when all the characters in the class have values in the range 0-255,
2851     and either the matching is caseful, or the characters are in the range
2852     0-127 when UTF-8 processing is enabled. The only difference between
2853     OP_CLASS and OP_NCLASS occurs when a data character outside the range is
2854     encountered.
2855
2856     First, look past the end of the item to see if there is repeat information
2857     following. Then obey similar code to character type repeats - written out
2858     again for speed. */
2859
2860     case OP_NCLASS:
2861     case OP_CLASS:
2862       {
2863       /* The data variable is saved across frames, so the byte map needs to
2864       be stored there. */
2865 #define BYTE_MAP ((pcre_uint8 *)data)
2866       data = ecode + 1;                /* Save for matching */
2867       ecode += 1 + (32 / sizeof(pcre_uchar)); /* Advance past the item */
2868
2869       switch (*ecode)
2870         {
2871         case OP_CRSTAR:
2872         case OP_CRMINSTAR:
2873         case OP_CRPLUS:
2874         case OP_CRMINPLUS:
2875         case OP_CRQUERY:
2876         case OP_CRMINQUERY:
2877         case OP_CRPOSSTAR:
2878         case OP_CRPOSPLUS:
2879         case OP_CRPOSQUERY:
2880         c = *ecode++ - OP_CRSTAR;
2881         if (c < OP_CRPOSSTAR - OP_CRSTAR) minimize = (c & 1) != 0;
2882         else possessive = TRUE;
2883         min = rep_min[c];                 /* Pick up values from tables; */
2884         max = rep_max[c];                 /* zero for max => infinity */
2885         if (max == 0) max = INT_MAX;
2886         break;
2887
2888         case OP_CRRANGE:
2889         case OP_CRMINRANGE:
2890         case OP_CRPOSRANGE:
2891         minimize = (*ecode == OP_CRMINRANGE);
2892         possessive = (*ecode == OP_CRPOSRANGE);
2893         min = GET2(ecode, 1);
2894         max = GET2(ecode, 1 + IMM2_SIZE);
2895         if (max == 0) max = INT_MAX;
2896         ecode += 1 + 2 * IMM2_SIZE;
2897         break;
2898
2899         default:               /* No repeat follows */
2900         min = max = 1;
2901         break;
2902         }
2903
2904       /* First, ensure the minimum number of matches are present. */
2905
2906 #ifdef SUPPORT_UTF
2907       if (utf)
2908         {
2909         for (i = 1; i <= min; i++)
2910           {
2911           if (eptr >= md->end_subject)
2912             {
2913             SCHECK_PARTIAL();
2914             RRETURN(MATCH_NOMATCH);
2915             }
2916           GETCHARINC(c, eptr);
2917           if (c > 255)
2918             {
2919             if (op == OP_CLASS) RRETURN(MATCH_NOMATCH);
2920             }
2921           else
2922             if ((BYTE_MAP[c/8] & (1 << (c&7))) == 0) RRETURN(MATCH_NOMATCH);
2923           }
2924         }
2925       else
2926 #endif
2927       /* Not UTF mode */
2928         {
2929         for (i = 1; i <= min; i++)
2930           {
2931           if (eptr >= md->end_subject)
2932             {
2933             SCHECK_PARTIAL();
2934             RRETURN(MATCH_NOMATCH);
2935             }
2936           c = *eptr++;
2937 #ifndef COMPILE_PCRE8
2938           if (c > 255)
2939             {
2940             if (op == OP_CLASS) RRETURN(MATCH_NOMATCH);
2941             }
2942           else
2943 #endif
2944             if ((BYTE_MAP[c/8] & (1 << (c&7))) == 0) RRETURN(MATCH_NOMATCH);
2945           }
2946         }
2947
2948       /* If max == min we can continue with the main loop without the
2949       need to recurse. */
2950
2951       if (min == max) continue;
2952
2953       /* If minimizing, keep testing the rest of the expression and advancing
2954       the pointer while it matches the class. */
2955
2956       if (minimize)
2957         {
2958 #ifdef SUPPORT_UTF
2959         if (utf)
2960           {
2961           for (fi = min;; fi++)
2962             {
2963             RMATCH(eptr, ecode, offset_top, md, eptrb, RM16);
2964             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2965             if (fi >= max) RRETURN(MATCH_NOMATCH);
2966             if (eptr >= md->end_subject)
2967               {
2968               SCHECK_PARTIAL();
2969               RRETURN(MATCH_NOMATCH);
2970               }
2971             GETCHARINC(c, eptr);
2972             if (c > 255)
2973               {
2974               if (op == OP_CLASS) RRETURN(MATCH_NOMATCH);
2975               }
2976             else
2977               if ((BYTE_MAP[c/8] & (1 << (c&7))) == 0) RRETURN(MATCH_NOMATCH);
2978             }
2979           }
2980         else
2981 #endif
2982         /* Not UTF mode */
2983           {
2984           for (fi = min;; fi++)
2985             {
2986             RMATCH(eptr, ecode, offset_top, md, eptrb, RM17);
2987             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
2988             if (fi >= max) RRETURN(MATCH_NOMATCH);
2989             if (eptr >= md->end_subject)
2990               {
2991               SCHECK_PARTIAL();
2992               RRETURN(MATCH_NOMATCH);
2993               }
2994             c = *eptr++;
2995 #ifndef COMPILE_PCRE8
2996             if (c > 255)
2997               {
2998               if (op == OP_CLASS) RRETURN(MATCH_NOMATCH);
2999               }
3000             else
3001 #endif
3002               if ((BYTE_MAP[c/8] & (1 << (c&7))) == 0) RRETURN(MATCH_NOMATCH);
3003             }
3004           }
3005         /* Control never gets here */
3006         }
3007
3008       /* If maximizing, find the longest possible run, then work backwards. */
3009
3010       else
3011         {
3012         pp = eptr;
3013
3014 #ifdef SUPPORT_UTF
3015         if (utf)
3016           {
3017           for (i = min; i < max; i++)
3018             {
3019             int len = 1;
3020             if (eptr >= md->end_subject)
3021               {
3022               SCHECK_PARTIAL();
3023               break;
3024               }
3025             GETCHARLEN(c, eptr, len);
3026             if (c > 255)
3027               {
3028               if (op == OP_CLASS) break;
3029               }
3030             else
3031               if ((BYTE_MAP[c/8] & (1 << (c&7))) == 0) break;
3032             eptr += len;
3033             }
3034
3035           if (possessive) continue;    /* No backtracking */
3036
3037           for (;;)
3038             {
3039             RMATCH(eptr, ecode, offset_top, md, eptrb, RM18);
3040             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3041             if (eptr-- == pp) break;        /* Stop if tried at original pos */
3042             BACKCHAR(eptr);
3043             }
3044           }
3045         else
3046 #endif
3047           /* Not UTF mode */
3048           {
3049           for (i = min; i < max; i++)
3050             {
3051             if (eptr >= md->end_subject)
3052               {
3053               SCHECK_PARTIAL();
3054               break;
3055               }
3056             c = *eptr;
3057 #ifndef COMPILE_PCRE8
3058             if (c > 255)
3059               {
3060               if (op == OP_CLASS) break;
3061               }
3062             else
3063 #endif
3064               if ((BYTE_MAP[c/8] & (1 << (c&7))) == 0) break;
3065             eptr++;
3066             }
3067
3068           if (possessive) continue;    /* No backtracking */
3069
3070           while (eptr >= pp)
3071             {
3072             RMATCH(eptr, ecode, offset_top, md, eptrb, RM19);
3073             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3074             eptr--;
3075             }
3076           }
3077
3078         RRETURN(MATCH_NOMATCH);
3079         }
3080 #undef BYTE_MAP
3081       }
3082     /* Control never gets here */
3083
3084
3085     /* Match an extended character class. In the 8-bit library, this opcode is
3086     encountered only when UTF-8 mode mode is supported. In the 16-bit and
3087     32-bit libraries, codepoints greater than 255 may be encountered even when
3088     UTF is not supported. */
3089
3090 #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
3091     case OP_XCLASS:
3092       {
3093       data = ecode + 1 + LINK_SIZE;                /* Save for matching */
3094       ecode += GET(ecode, 1);                      /* Advance past the item */
3095
3096       switch (*ecode)
3097         {
3098         case OP_CRSTAR:
3099         case OP_CRMINSTAR:
3100         case OP_CRPLUS:
3101         case OP_CRMINPLUS:
3102         case OP_CRQUERY:
3103         case OP_CRMINQUERY:
3104         case OP_CRPOSSTAR:
3105         case OP_CRPOSPLUS:
3106         case OP_CRPOSQUERY:
3107         c = *ecode++ - OP_CRSTAR;
3108         if (c < OP_CRPOSSTAR - OP_CRSTAR) minimize = (c & 1) != 0;
3109         else possessive = TRUE;
3110         min = rep_min[c];                 /* Pick up values from tables; */
3111         max = rep_max[c];                 /* zero for max => infinity */
3112         if (max == 0) max = INT_MAX;
3113         break;
3114
3115         case OP_CRRANGE:
3116         case OP_CRMINRANGE:
3117         case OP_CRPOSRANGE:
3118         minimize = (*ecode == OP_CRMINRANGE);
3119         possessive = (*ecode == OP_CRPOSRANGE);
3120         min = GET2(ecode, 1);
3121         max = GET2(ecode, 1 + IMM2_SIZE);
3122         if (max == 0) max = INT_MAX;
3123         ecode += 1 + 2 * IMM2_SIZE;
3124         break;
3125
3126         default:               /* No repeat follows */
3127         min = max = 1;
3128         break;
3129         }
3130
3131       /* First, ensure the minimum number of matches are present. */
3132
3133       for (i = 1; i <= min; i++)
3134         {
3135         if (eptr >= md->end_subject)
3136           {
3137           SCHECK_PARTIAL();
3138           RRETURN(MATCH_NOMATCH);
3139           }
3140         GETCHARINCTEST(c, eptr);
3141         if (!PRIV(xclass)(c, data, utf)) RRETURN(MATCH_NOMATCH);
3142         }
3143
3144       /* If max == min we can continue with the main loop without the
3145       need to recurse. */
3146
3147       if (min == max) continue;
3148
3149       /* If minimizing, keep testing the rest of the expression and advancing
3150       the pointer while it matches the class. */
3151
3152       if (minimize)
3153         {
3154         for (fi = min;; fi++)
3155           {
3156           RMATCH(eptr, ecode, offset_top, md, eptrb, RM20);
3157           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3158           if (fi >= max) RRETURN(MATCH_NOMATCH);
3159           if (eptr >= md->end_subject)
3160             {
3161             SCHECK_PARTIAL();
3162             RRETURN(MATCH_NOMATCH);
3163             }
3164           GETCHARINCTEST(c, eptr);
3165           if (!PRIV(xclass)(c, data, utf)) RRETURN(MATCH_NOMATCH);
3166           }
3167         /* Control never gets here */
3168         }
3169
3170       /* If maximizing, find the longest possible run, then work backwards. */
3171
3172       else
3173         {
3174         pp = eptr;
3175         for (i = min; i < max; i++)
3176           {
3177           int len = 1;
3178           if (eptr >= md->end_subject)
3179             {
3180             SCHECK_PARTIAL();
3181             break;
3182             }
3183 #ifdef SUPPORT_UTF
3184           GETCHARLENTEST(c, eptr, len);
3185 #else
3186           c = *eptr;
3187 #endif
3188           if (!PRIV(xclass)(c, data, utf)) break;
3189           eptr += len;
3190           }
3191
3192         if (possessive) continue;    /* No backtracking */
3193
3194         for(;;)
3195           {
3196           RMATCH(eptr, ecode, offset_top, md, eptrb, RM21);
3197           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3198           if (eptr-- == pp) break;        /* Stop if tried at original pos */
3199 #ifdef SUPPORT_UTF
3200           if (utf) BACKCHAR(eptr);
3201 #endif
3202           }
3203         RRETURN(MATCH_NOMATCH);
3204         }
3205
3206       /* Control never gets here */
3207       }
3208 #endif    /* End of XCLASS */
3209
3210     /* Match a single character, casefully */
3211
3212     case OP_CHAR:
3213 #ifdef SUPPORT_UTF
3214     if (utf)
3215       {
3216       length = 1;
3217       ecode++;
3218       GETCHARLEN(fc, ecode, length);
3219       if (length > md->end_subject - eptr)
3220         {
3221         CHECK_PARTIAL();             /* Not SCHECK_PARTIAL() */
3222         RRETURN(MATCH_NOMATCH);
3223         }
3224       while (length-- > 0) if (*ecode++ != UCHAR21INC(eptr)) RRETURN(MATCH_NOMATCH);
3225       }
3226     else
3227 #endif
3228     /* Not UTF mode */
3229       {
3230       if (md->end_subject - eptr < 1)
3231         {
3232         SCHECK_PARTIAL();            /* This one can use SCHECK_PARTIAL() */
3233         RRETURN(MATCH_NOMATCH);
3234         }
3235       if (ecode[1] != *eptr++) RRETURN(MATCH_NOMATCH);
3236       ecode += 2;
3237       }
3238     break;
3239
3240     /* Match a single character, caselessly. If we are at the end of the
3241     subject, give up immediately. */
3242
3243     case OP_CHARI:
3244     if (eptr >= md->end_subject)
3245       {
3246       SCHECK_PARTIAL();
3247       RRETURN(MATCH_NOMATCH);
3248       }
3249
3250 #ifdef SUPPORT_UTF
3251     if (utf)
3252       {
3253       length = 1;
3254       ecode++;
3255       GETCHARLEN(fc, ecode, length);
3256
3257       /* If the pattern character's value is < 128, we have only one byte, and
3258       we know that its other case must also be one byte long, so we can use the
3259       fast lookup table. We know that there is at least one byte left in the
3260       subject. */
3261
3262       if (fc < 128)
3263         {
3264         pcre_uint32 cc = UCHAR21(eptr);
3265         if (md->lcc[fc] != TABLE_GET(cc, md->lcc, cc)) RRETURN(MATCH_NOMATCH);
3266         ecode++;
3267         eptr++;
3268         }
3269
3270       /* Otherwise we must pick up the subject character. Note that we cannot
3271       use the value of "length" to check for sufficient bytes left, because the
3272       other case of the character may have more or fewer bytes.  */
3273
3274       else
3275         {
3276         pcre_uint32 dc;
3277         GETCHARINC(dc, eptr);
3278         ecode += length;
3279
3280         /* If we have Unicode property support, we can use it to test the other
3281         case of the character, if there is one. */
3282
3283         if (fc != dc)
3284           {
3285 #ifdef SUPPORT_UCP
3286           if (dc != UCD_OTHERCASE(fc))
3287 #endif
3288             RRETURN(MATCH_NOMATCH);
3289           }
3290         }
3291       }
3292     else
3293 #endif   /* SUPPORT_UTF */
3294
3295     /* Not UTF mode */
3296       {
3297       if (TABLE_GET(ecode[1], md->lcc, ecode[1])
3298           != TABLE_GET(*eptr, md->lcc, *eptr)) RRETURN(MATCH_NOMATCH);
3299       eptr++;
3300       ecode += 2;
3301       }
3302     break;
3303
3304     /* Match a single character repeatedly. */
3305
3306     case OP_EXACT:
3307     case OP_EXACTI:
3308     min = max = GET2(ecode, 1);
3309     ecode += 1 + IMM2_SIZE;
3310     goto REPEATCHAR;
3311
3312     case OP_POSUPTO:
3313     case OP_POSUPTOI:
3314     possessive = TRUE;
3315     /* Fall through */
3316
3317     case OP_UPTO:
3318     case OP_UPTOI:
3319     case OP_MINUPTO:
3320     case OP_MINUPTOI:
3321     min = 0;
3322     max = GET2(ecode, 1);
3323     minimize = *ecode == OP_MINUPTO || *ecode == OP_MINUPTOI;
3324     ecode += 1 + IMM2_SIZE;
3325     goto REPEATCHAR;
3326
3327     case OP_POSSTAR:
3328     case OP_POSSTARI:
3329     possessive = TRUE;
3330     min = 0;
3331     max = INT_MAX;
3332     ecode++;
3333     goto REPEATCHAR;
3334
3335     case OP_POSPLUS:
3336     case OP_POSPLUSI:
3337     possessive = TRUE;
3338     min = 1;
3339     max = INT_MAX;
3340     ecode++;
3341     goto REPEATCHAR;
3342
3343     case OP_POSQUERY:
3344     case OP_POSQUERYI:
3345     possessive = TRUE;
3346     min = 0;
3347     max = 1;
3348     ecode++;
3349     goto REPEATCHAR;
3350
3351     case OP_STAR:
3352     case OP_STARI:
3353     case OP_MINSTAR:
3354     case OP_MINSTARI:
3355     case OP_PLUS:
3356     case OP_PLUSI:
3357     case OP_MINPLUS:
3358     case OP_MINPLUSI:
3359     case OP_QUERY:
3360     case OP_QUERYI:
3361     case OP_MINQUERY:
3362     case OP_MINQUERYI:
3363     c = *ecode++ - ((op < OP_STARI)? OP_STAR : OP_STARI);
3364     minimize = (c & 1) != 0;
3365     min = rep_min[c];                 /* Pick up values from tables; */
3366     max = rep_max[c];                 /* zero for max => infinity */
3367     if (max == 0) max = INT_MAX;
3368
3369     /* Common code for all repeated single-character matches. We first check
3370     for the minimum number of characters. If the minimum equals the maximum, we
3371     are done. Otherwise, if minimizing, check the rest of the pattern for a
3372     match; if there isn't one, advance up to the maximum, one character at a
3373     time.
3374
3375     If maximizing, advance up to the maximum number of matching characters,
3376     until eptr is past the end of the maximum run. If possessive, we are
3377     then done (no backing up). Otherwise, match at this position; anything
3378     other than no match is immediately returned. For nomatch, back up one
3379     character, unless we are matching \R and the last thing matched was
3380     \r\n, in which case, back up two bytes. When we reach the first optional
3381     character position, we can save stack by doing a tail recurse.
3382
3383     The various UTF/non-UTF and caseful/caseless cases are handled separately,
3384     for speed. */
3385
3386     REPEATCHAR:
3387 #ifdef SUPPORT_UTF
3388     if (utf)
3389       {
3390       length = 1;
3391       charptr = ecode;
3392       GETCHARLEN(fc, ecode, length);
3393       ecode += length;
3394
3395       /* Handle multibyte character matching specially here. There is
3396       support for caseless matching if UCP support is present. */
3397
3398       if (length > 1)
3399         {
3400 #ifdef SUPPORT_UCP
3401         pcre_uint32 othercase;
3402         if (op >= OP_STARI &&     /* Caseless */
3403             (othercase = UCD_OTHERCASE(fc)) != fc)
3404           oclength = PRIV(ord2utf)(othercase, occhars);
3405         else oclength = 0;
3406 #endif  /* SUPPORT_UCP */
3407
3408         for (i = 1; i <= min; i++)
3409           {
3410           if (eptr <= md->end_subject - length &&
3411             memcmp(eptr, charptr, IN_UCHARS(length)) == 0) eptr += length;
3412 #ifdef SUPPORT_UCP
3413           else if (oclength > 0 &&
3414                    eptr <= md->end_subject - oclength &&
3415                    memcmp(eptr, occhars, IN_UCHARS(oclength)) == 0) eptr += oclength;
3416 #endif  /* SUPPORT_UCP */
3417           else
3418             {
3419             CHECK_PARTIAL();
3420             RRETURN(MATCH_NOMATCH);
3421             }
3422           }
3423
3424         if (min == max) continue;
3425
3426         if (minimize)
3427           {
3428           for (fi = min;; fi++)
3429             {
3430             RMATCH(eptr, ecode, offset_top, md, eptrb, RM22);
3431             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3432             if (fi >= max) RRETURN(MATCH_NOMATCH);
3433             if (eptr <= md->end_subject - length &&
3434               memcmp(eptr, charptr, IN_UCHARS(length)) == 0) eptr += length;
3435 #ifdef SUPPORT_UCP
3436             else if (oclength > 0 &&
3437                      eptr <= md->end_subject - oclength &&
3438                      memcmp(eptr, occhars, IN_UCHARS(oclength)) == 0) eptr += oclength;
3439 #endif  /* SUPPORT_UCP */
3440             else
3441               {
3442               CHECK_PARTIAL();
3443               RRETURN(MATCH_NOMATCH);
3444               }
3445             }
3446           /* Control never gets here */
3447           }
3448
3449         else  /* Maximize */
3450           {
3451           pp = eptr;
3452           for (i = min; i < max; i++)
3453             {
3454             if (eptr <= md->end_subject - length &&
3455                 memcmp(eptr, charptr, IN_UCHARS(length)) == 0) eptr += length;
3456 #ifdef SUPPORT_UCP
3457             else if (oclength > 0 &&
3458                      eptr <= md->end_subject - oclength &&
3459                      memcmp(eptr, occhars, IN_UCHARS(oclength)) == 0) eptr += oclength;
3460 #endif  /* SUPPORT_UCP */
3461             else
3462               {
3463               CHECK_PARTIAL();
3464               break;
3465               }
3466             }
3467
3468           if (possessive) continue;    /* No backtracking */
3469           for(;;)
3470             {
3471             if (eptr == pp) goto TAIL_RECURSE;
3472             RMATCH(eptr, ecode, offset_top, md, eptrb, RM23);
3473             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3474 #ifdef SUPPORT_UCP
3475             eptr--;
3476             BACKCHAR(eptr);
3477 #else   /* without SUPPORT_UCP */
3478             eptr -= length;
3479 #endif  /* SUPPORT_UCP */
3480             }
3481           }
3482         /* Control never gets here */
3483         }
3484
3485       /* If the length of a UTF-8 character is 1, we fall through here, and
3486       obey the code as for non-UTF-8 characters below, though in this case the
3487       value of fc will always be < 128. */
3488       }
3489     else
3490 #endif  /* SUPPORT_UTF */
3491       /* When not in UTF-8 mode, load a single-byte character. */
3492       fc = *ecode++;
3493
3494     /* The value of fc at this point is always one character, though we may
3495     or may not be in UTF mode. The code is duplicated for the caseless and
3496     caseful cases, for speed, since matching characters is likely to be quite
3497     common. First, ensure the minimum number of matches are present. If min =
3498     max, continue at the same level without recursing. Otherwise, if
3499     minimizing, keep trying the rest of the expression and advancing one
3500     matching character if failing, up to the maximum. Alternatively, if
3501     maximizing, find the maximum number of characters and work backwards. */
3502
3503     DPRINTF(("matching %c{%d,%d} against subject %.*s\n", fc, min, max,
3504       max, (char *)eptr));
3505
3506     if (op >= OP_STARI)  /* Caseless */
3507       {
3508 #ifdef COMPILE_PCRE8
3509       /* fc must be < 128 if UTF is enabled. */
3510       foc = md->fcc[fc];
3511 #else
3512 #ifdef SUPPORT_UTF
3513 #ifdef SUPPORT_UCP
3514       if (utf && fc > 127)
3515         foc = UCD_OTHERCASE(fc);
3516 #else
3517       if (utf && fc > 127)
3518         foc = fc;
3519 #endif /* SUPPORT_UCP */
3520       else
3521 #endif /* SUPPORT_UTF */
3522         foc = TABLE_GET(fc, md->fcc, fc);
3523 #endif /* COMPILE_PCRE8 */
3524
3525       for (i = 1; i <= min; i++)
3526         {
3527         pcre_uint32 cc;                 /* Faster than pcre_uchar */
3528         if (eptr >= md->end_subject)
3529           {
3530           SCHECK_PARTIAL();
3531           RRETURN(MATCH_NOMATCH);
3532           }
3533         cc = UCHAR21TEST(eptr);
3534         if (fc != cc && foc != cc) RRETURN(MATCH_NOMATCH);
3535         eptr++;
3536         }
3537       if (min == max) continue;
3538       if (minimize)
3539         {
3540         for (fi = min;; fi++)
3541           {
3542           pcre_uint32 cc;               /* Faster than pcre_uchar */
3543           RMATCH(eptr, ecode, offset_top, md, eptrb, RM24);
3544           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3545           if (fi >= max) RRETURN(MATCH_NOMATCH);
3546           if (eptr >= md->end_subject)
3547             {
3548             SCHECK_PARTIAL();
3549             RRETURN(MATCH_NOMATCH);
3550             }
3551           cc = UCHAR21TEST(eptr);
3552           if (fc != cc && foc != cc) RRETURN(MATCH_NOMATCH);
3553           eptr++;
3554           }
3555         /* Control never gets here */
3556         }
3557       else  /* Maximize */
3558         {
3559         pp = eptr;
3560         for (i = min; i < max; i++)
3561           {
3562           pcre_uint32 cc;               /* Faster than pcre_uchar */
3563           if (eptr >= md->end_subject)
3564             {
3565             SCHECK_PARTIAL();
3566             break;
3567             }
3568           cc = UCHAR21TEST(eptr);
3569           if (fc != cc && foc != cc) break;
3570           eptr++;
3571           }
3572         if (possessive) continue;       /* No backtracking */
3573         for (;;)
3574           {
3575           if (eptr == pp) goto TAIL_RECURSE;
3576           RMATCH(eptr, ecode, offset_top, md, eptrb, RM25);
3577           eptr--;
3578           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3579           }
3580         /* Control never gets here */
3581         }
3582       }
3583
3584     /* Caseful comparisons (includes all multi-byte characters) */
3585
3586     else
3587       {
3588       for (i = 1; i <= min; i++)
3589         {
3590         if (eptr >= md->end_subject)
3591           {
3592           SCHECK_PARTIAL();
3593           RRETURN(MATCH_NOMATCH);
3594           }
3595         if (fc != UCHAR21INCTEST(eptr)) RRETURN(MATCH_NOMATCH);
3596         }
3597
3598       if (min == max) continue;
3599
3600       if (minimize)
3601         {
3602         for (fi = min;; fi++)
3603           {
3604           RMATCH(eptr, ecode, offset_top, md, eptrb, RM26);
3605           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3606           if (fi >= max) RRETURN(MATCH_NOMATCH);
3607           if (eptr >= md->end_subject)
3608             {
3609             SCHECK_PARTIAL();
3610             RRETURN(MATCH_NOMATCH);
3611             }
3612           if (fc != UCHAR21INCTEST(eptr)) RRETURN(MATCH_NOMATCH);
3613           }
3614         /* Control never gets here */
3615         }
3616       else  /* Maximize */
3617         {
3618         pp = eptr;
3619         for (i = min; i < max; i++)
3620           {
3621           if (eptr >= md->end_subject)
3622             {
3623             SCHECK_PARTIAL();
3624             break;
3625             }
3626           if (fc != UCHAR21TEST(eptr)) break;
3627           eptr++;
3628           }
3629         if (possessive) continue;    /* No backtracking */
3630         for (;;)
3631           {
3632           if (eptr == pp) goto TAIL_RECURSE;
3633           RMATCH(eptr, ecode, offset_top, md, eptrb, RM27);
3634           eptr--;
3635           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
3636           }
3637         /* Control never gets here */
3638         }
3639       }
3640     /* Control never gets here */
3641
3642     /* Match a negated single one-byte character. The character we are
3643     checking can be multibyte. */
3644
3645     case OP_NOT:
3646     case OP_NOTI:
3647     if (eptr >= md->end_subject)
3648       {
3649       SCHECK_PARTIAL();
3650       RRETURN(MATCH_NOMATCH);
3651       }
3652 #ifdef SUPPORT_UTF
3653     if (utf)
3654       {
3655       register pcre_uint32 ch, och;
3656
3657       ecode++;
3658       GETCHARINC(ch, ecode);
3659       GETCHARINC(c, eptr);
3660
3661       if (op == OP_NOT)
3662         {
3663         if (ch == c) RRETURN(MATCH_NOMATCH);
3664         }
3665       else
3666         {
3667 #ifdef SUPPORT_UCP
3668         if (ch > 127)
3669           och = UCD_OTHERCASE(ch);
3670 #else
3671         if (ch > 127)
3672           och = ch;
3673 #endif /* SUPPORT_UCP */
3674         else
3675           och = TABLE_GET(ch, md->fcc, ch);
3676         if (ch == c || och == c) RRETURN(MATCH_NOMATCH);
3677         }
3678       }
3679     else
3680 #endif
3681       {
3682       register pcre_uint32 ch = ecode[1];
3683       c = *eptr++;
3684       if (ch == c || (op == OP_NOTI && TABLE_GET(ch, md->fcc, ch) == c))
3685         RRETURN(MATCH_NOMATCH);