2007-11-15 Eric Seidel <eric@webkit.org>
[WebKit-https.git] / JavaScriptCore / pcre / pcre_exec.cpp
1 /* This is JavaScriptCore's variant of the PCRE library. While this library
2 started out as a copy of PCRE, many of the features of PCRE have been
3 removed. This library now supports only the regular expression features
4 required by the JavaScript language specification, and has only the functions
5 needed by JavaScriptCore and the rest of WebKit.
6
7                  Originally written by Philip Hazel
8            Copyright (c) 1997-2006 University of Cambridge
9     Copyright (C) 2002, 2004, 2006, 2007 Apple Inc. All rights reserved.
10
11 -----------------------------------------------------------------------------
12 Redistribution and use in source and binary forms, with or without
13 modification, are permitted provided that the following conditions are met:
14
15     * Redistributions of source code must retain the above copyright notice,
16       this list of conditions and the following disclaimer.
17
18     * Redistributions in binary form must reproduce the above copyright
19       notice, this list of conditions and the following disclaimer in the
20       documentation and/or other materials provided with the distribution.
21
22     * Neither the name of the University of Cambridge nor the names of its
23       contributors may be used to endorse or promote products derived from
24       this software without specific prior written permission.
25
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
27 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
30 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36 POSSIBILITY OF SUCH DAMAGE.
37 -----------------------------------------------------------------------------
38 */
39
40 /* This module contains jsRegExpExecute(), the externally visible function
41 that does pattern matching using an NFA algorithm, following the rules from
42 the JavaScript specification. There are also some supporting functions. */
43
44 #include "config.h"
45
46 #include "pcre_internal.h"
47
48 #include <wtf/ASCIICType.h>
49 #include <wtf/Vector.h>
50
51 using namespace WTF;
52
53 #ifdef __GNUC__
54 #define USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
55 //#define USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
56 #endif
57
58 /* Avoid warnings on Windows. */
59 #undef min
60 #undef max
61
62 /* Structure for building a chain of data that actually lives on the
63 stack, for holding the values of the subject pointer at the start of each
64 subpattern, so as to detect when an empty string has been matched by a
65 subpattern - to break infinite loops. When NO_RECURSE is set, these blocks
66 are on the heap, not on the stack. */
67
68 typedef struct eptrblock {
69   struct eptrblock *epb_prev;
70   USPTR epb_saved_eptr;
71 } eptrblock;
72
73 /* Structure for remembering the local variables in a private frame */
74
75 typedef struct matchframe {
76   /* Where to jump back to */
77 #ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
78   int where;
79 #else
80   void *where;
81 #endif
82
83   struct matchframe *prevframe;
84
85   /* Function arguments that may change */
86
87   const pcre_uchar *eptr;
88   const uschar *ecode;
89   int offset_top;
90   eptrblock *eptrb;
91
92   /* Function local variables */
93
94   const uschar *data;
95   const uschar *next;
96   const pcre_uchar *pp;
97   const uschar *prev;
98   const pcre_uchar *saved_eptr;
99
100   int repeat_othercase;
101
102   int ctype;
103   int fc;
104   int fi;
105   int length;
106   int max;
107   int number;
108   int offset;
109   int save_offset1, save_offset2, save_offset3;
110
111   eptrblock newptrb;
112 } matchframe;
113
114 /* Structure for passing "static" information around between the functions
115 doing traditional NFA matching, so that they are thread-safe. */
116
117 typedef struct match_data {
118   unsigned long int match_call_count;      /* As it says */
119   int   *offset_vector;         /* Offset vector */
120   int    offset_end;            /* One past the end */
121   int    offset_max;            /* The maximum usable for return data */
122   const uschar *lcc;            /* Points to lower casing table */
123   const uschar *ctypes;         /* Points to table of type maps */
124   BOOL   offset_overflow;       /* Set if too many extractions */
125   USPTR  start_subject;         /* Start of the subject string */
126   USPTR  end_subject;           /* End of the subject string */
127   USPTR  end_match_ptr;         /* Subject position at end match */
128   int    end_offset_top;        /* Highwater mark at end of match */
129   BOOL   multiline;
130   BOOL   caseless;
131 } match_data;
132
133 #define match_isgroup      true    /* Set if start of bracketed group */
134
135 /* Non-error returns from the match() function. Error returns are externally
136 defined PCRE_ERROR_xxx codes, which are all negative. */
137
138 #define MATCH_MATCH        1
139 #define MATCH_NOMATCH      0
140
141 /* Min and max values for the common repeats; for the maxima, 0 => infinity */
142
143 static const char rep_min[] = { 0, 0, 1, 1, 0, 0 };
144 static const char rep_max[] = { 0, 0, 0, 0, 1, 1 };
145
146
147
148 #ifdef DEBUG
149 /*************************************************
150 *        Debugging function to print chars       *
151 *************************************************/
152
153 /* Print a sequence of chars in printable format, stopping at the end of the
154 subject if the requested.
155
156 Arguments:
157   p           points to characters
158   length      number to print
159   is_subject  true if printing from within md->start_subject
160   md          pointer to matching data block, if is_subject is true
161
162 Returns:     nothing
163 */
164
165 static void
166 pchars(const pcre_uchar *p, int length, BOOL is_subject, match_data *md)
167 {
168 int c;
169 if (is_subject && length > md->end_subject - p) length = md->end_subject - p;
170 while (length-- > 0)
171   if (isprint(c = *(p++))) printf("%c", c);
172   else if (c < 256) printf("\\x%02x", c);
173   else printf("\\x{%x}", c);
174 }
175 #endif
176
177
178
179 /*************************************************
180 *          Match a back-reference                *
181 *************************************************/
182
183 /* If a back reference hasn't been set, the length that is passed is greater
184 than the number of characters left in the string, so the match fails.
185
186 Arguments:
187   offset      index into the offset vector
188   eptr        points into the subject
189   length      length to be matched
190   md          points to match data block
191
192 Returns:      true if matched
193 */
194
195 static BOOL
196 match_ref(int offset, register USPTR eptr, int length, match_data *md)
197 {
198 USPTR p = md->start_subject + md->offset_vector[offset];
199
200 #ifdef DEBUG
201 if (eptr >= md->end_subject)
202   printf("matching subject <null>");
203 else
204   {
205   printf("matching subject ");
206   pchars(eptr, length, true, md);
207   }
208 printf(" against backref ");
209 pchars(p, length, false, md);
210 printf("\n");
211 #endif
212
213 /* Always fail if not enough characters left */
214
215 if (length > md->end_subject - eptr) return false;
216
217 /* Separate the caselesss case for speed */
218
219 if (md->caseless)
220   {
221   while (length-- > 0)
222     {
223     pcre_uchar c = *p++;
224     int othercase = _pcre_ucp_othercase(c);
225     pcre_uchar d = *eptr++;
226     if (c != d && othercase != d) return false;
227     }
228   }
229 else
230   { while (length-- > 0) if (*p++ != *eptr++) return false; }
231
232 return true;
233 }
234
235
236
237 /***************************************************************************
238 ****************************************************************************
239                    RECURSION IN THE match() FUNCTION
240
241 The original match() function was highly recursive. The current version
242 still has the remnants of the original in that recursive processing of the
243 regular expression is triggered by invoking a macro named RMATCH. This is
244 no longer really much like a recursive call to match() itself.
245 ****************************************************************************
246 ***************************************************************************/
247
248 /* These versions of the macros use the stack, as normal. There are debugging
249 versions and production versions. */
250
251 #ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
252
253 /* Use numbered labels and switch statement at the bottom of the match function. */
254
255 #define RMATCH_WHERE(num) num
256 #define RRETURN_LABEL RRETURN_SWITCH
257
258 #else
259
260 /* Use GCC's computed goto extension. */
261
262 /* For one test case this is more than 40% faster than the switch statement.
263 We could avoid the use of the num argument entirely by using local labels,
264 but using it for the GCC case as well as the non-GCC case allows us to share
265 a bit more code and notice if we use conflicting numbers.*/
266
267 #define RMATCH_WHERE(num) &&RRETURN_##num
268 #define RRETURN_LABEL *frame->where
269
270 #endif
271
272 #define RMATCH(num, ra, rb, rc)\
273   {\
274   if (frame >= stackframes && frame + 1 < stackframesend)\
275     newframe = frame + 1;\
276   else\
277     newframe = new matchframe;\
278   newframe->eptr = frame->eptr;\
279   newframe->ecode = (ra);\
280   newframe->offset_top = frame->offset_top;\
281   newframe->eptrb = (rb);\
282   is_group_start = (rc);\
283   ++rdepth;\
284   newframe->prevframe = frame;\
285   frame = newframe;\
286   frame->where = RMATCH_WHERE(num);\
287   DPRINTF(("restarting from line %d\n", __LINE__));\
288   goto RECURSE;\
289 RRETURN_##num:\
290   newframe = frame;\
291   frame = frame->prevframe;\
292   if (!(newframe >= stackframes && newframe < stackframesend))\
293     delete newframe;\
294   --rdepth;\
295   DPRINTF(("did a goto back to line %d\n", __LINE__));\
296   }
297  
298 #define RRETURN goto RRETURN_LABEL
299
300 #define RRETURN_NO_MATCH \
301   {\
302     is_match = false;\
303     RRETURN;\
304   }
305
306 #define RRETURN_ERROR(error) \
307   { \
308     i = (error); \
309     goto RETURN_ERROR; \
310   }
311
312 /*************************************************
313 *         Match from current position            *
314 *************************************************/
315
316 /* On entry ecode points to the first opcode, and eptr to the first character
317 in the subject string, while eptrb holds the value of eptr at the start of the
318 last bracketed group - used for breaking infinite loops matching zero-length
319 strings. This function is called recursively in many circumstances. Whenever it
320 returns a negative (error) response, the outer incarnation must also return the
321 same response.
322
323 Arguments:
324    eptr        pointer in subject
325    ecode       position in code
326    offset_top  current top pointer
327    md          pointer to "static" info for the match
328
329 Returns:       MATCH_MATCH if matched            )  these values are >= 0
330                MATCH_NOMATCH if failed to match  )
331                a negative PCRE_ERROR_xxx value if aborted by an error condition
332                  (e.g. stopped by repeated call or recursion limit)
333 */
334
335 static int match(USPTR eptr, const uschar* ecode, int offset_top, match_data* md)
336 {
337     register int is_match = false;
338     register int i;
339     register int c;
340     
341     unsigned rdepth = 0;
342     
343     BOOL cur_is_word;
344     BOOL prev_is_word;
345     BOOL is_group_start = true;
346     int min;
347     BOOL minimize = false; /* Initialization not really needed, but some compilers think so. */
348     
349     /* The value 16 here is large enough that most regular expressions don't require
350      any calls to pcre_stack_malloc, yet the amount of stack used for the array is
351      modest enough that we don't run out of stack. */
352     matchframe stackframes[16];
353     matchframe *stackframesend = stackframes + sizeof(stackframes) / sizeof(stackframes[0]);
354     
355     matchframe *frame = stackframes;
356     matchframe *newframe;
357     
358     /* The opcode jump table. */
359 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
360 #define EMIT_JUMP_TABLE_ENTRY(opcode) &&LABEL_OP_##opcode,
361     static void* opcode_jump_table[256] = { FOR_EACH_OPCODE(EMIT_JUMP_TABLE_ENTRY) };
362 #undef EMIT_JUMP_TABLE_ENTRY
363 #endif
364     
365     /* One-time setup of the opcode jump table. */
366 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
367     i = 255;
368     while (!opcode_jump_table[i])
369         opcode_jump_table[i--] = &&CAPTURING_BRACKET;
370 #endif
371     
372 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
373     frame->where = &&RETURN;
374 #else
375     frame->where = 0;
376 #endif
377     
378     frame->eptr = eptr;
379     frame->ecode = ecode;
380     frame->offset_top = offset_top;
381     frame->eptrb = NULL;
382     
383     /* This is where control jumps back to to effect "recursion" */
384     
385 RECURSE:
386     
387     /* OK, now we can get on with the real code of the function. Recursive calls
388      are specified by the macro RMATCH and RRETURN is used to return. When
389      NO_RECURSE is *not* defined, these just turn into a recursive call to match()
390      and a "return", respectively (possibly with some debugging if DEBUG is
391      defined). However, RMATCH isn't like a function call because it's quite a
392      complicated macro. It has to be used in one particular way. This shouldn't,
393      however, impact performance when true recursion is being used. */
394     
395     /* First check that we haven't called match() too many times, or that we
396      haven't exceeded the recursive call limit. */
397     
398     if (md->match_call_count++ >= MATCH_LIMIT)
399         RRETURN_ERROR(JSRegExpErrorMatchLimit);
400     if (rdepth >= MATCH_LIMIT_RECURSION)
401         RRETURN_ERROR(JSRegExpErrorRecursionLimit);
402     
403     /* At the start of a bracketed group, add the current subject pointer to the
404      stack of such pointers, to be re-instated at the end of the group when we hit
405      the closing ket. When match() is called in other circumstances, we don't add to
406      this stack. */
407     
408     if (is_group_start) {
409         frame->newptrb.epb_prev = frame->eptrb;
410         frame->newptrb.epb_saved_eptr = frame->eptr;
411         frame->eptrb = &frame->newptrb;
412     }
413     
414     /* Now start processing the operations. */
415     
416 #ifndef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
417     while (true)
418 #endif
419     {
420         
421 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
422 #define BEGIN_OPCODE(opcode) LABEL_OP_##opcode
423 #define NEXT_OPCODE goto *opcode_jump_table[*frame->ecode]
424 #else
425 #define BEGIN_OPCODE(opcode) case OP_##opcode
426 #define NEXT_OPCODE continue
427 #endif
428         
429 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
430         NEXT_OPCODE;
431 #else
432         switch (*frame->ecode)
433 #endif
434         {
435                 /* Non-capturing bracket: optimized */
436                 
437                 BEGIN_OPCODE(BRA):
438             NON_CAPTURING_BRACKET:
439                 DPRINTF(("start bracket 0\n"));
440                 do {
441                     RMATCH(2, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
442                     if (is_match)
443                         RRETURN;
444                     frame->ecode += GET(frame->ecode, 1);
445                 } while (*frame->ecode == OP_ALT);
446                 DPRINTF(("bracket 0 failed\n"));
447                 RRETURN;
448                 
449                 /* Skip over large extraction number data if encountered. */
450                 
451                 BEGIN_OPCODE(BRANUMBER):
452                 frame->ecode += 3;
453                 NEXT_OPCODE;
454                 
455                 /* End of the pattern. */
456                 
457                 BEGIN_OPCODE(END):
458                 md->end_match_ptr = frame->eptr;          /* Record where we ended */
459                 md->end_offset_top = frame->offset_top;   /* and how many extracts were taken */
460                 is_match = true;
461                 RRETURN;
462                 
463                 /* Assertion brackets. Check the alternative branches in turn - the
464                  matching won't pass the KET for an assertion. If any one branch matches,
465                  the assertion is true. Lookbehind assertions have an OP_REVERSE item at the
466                  start of each branch to move the current point backwards, so the code at
467                  this level is identical to the lookahead case. */
468                 
469                 BEGIN_OPCODE(ASSERT):
470                 do {
471                     RMATCH(6, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
472                     if (is_match) break;
473                     frame->ecode += GET(frame->ecode, 1);
474                 } while (*frame->ecode == OP_ALT);
475                 if (*frame->ecode == OP_KET)
476                     RRETURN_NO_MATCH;
477                 
478                 /* Continue from after the assertion, updating the offsets high water
479                  mark, since extracts may have been taken during the assertion. */
480                 
481                 do frame->ecode += GET(frame->ecode,1); while (*frame->ecode == OP_ALT);
482                 frame->ecode += 1 + LINK_SIZE;
483                 frame->offset_top = md->end_offset_top;
484                 NEXT_OPCODE;
485                 
486                 /* Negative assertion: all branches must fail to match */
487                 
488                 BEGIN_OPCODE(ASSERT_NOT):
489                 do {
490                     RMATCH(7, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
491                     if (is_match)
492                         RRETURN_NO_MATCH;
493                     frame->ecode += GET(frame->ecode,1);
494                 } while (*frame->ecode == OP_ALT);
495                 
496                 frame->ecode += 1 + LINK_SIZE;
497                 NEXT_OPCODE;
498                 
499                 /* "Once" brackets are like assertion brackets except that after a match,
500                  the point in the subject string is not moved back. Thus there can never be
501                  a move back into the brackets. Friedl calls these "atomic" subpatterns.
502                  Check the alternative branches in turn - the matching won't pass the KET
503                  for this kind of subpattern. If any one branch matches, we carry on as at
504                  the end of a normal bracket, leaving the subject pointer. */
505                 
506                 BEGIN_OPCODE(ONCE):
507                 frame->prev = frame->ecode;
508                 frame->saved_eptr = frame->eptr;
509                 
510                 do {
511                     RMATCH(9, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
512                     if (is_match)
513                         break;
514                     frame->ecode += GET(frame->ecode,1);
515                 } while (*frame->ecode == OP_ALT);
516                 
517                 /* If hit the end of the group (which could be repeated), fail */
518                 
519                 if (*frame->ecode != OP_ONCE && *frame->ecode != OP_ALT)
520                     RRETURN;
521                 
522                 /* Continue as from after the assertion, updating the offsets high water
523                  mark, since extracts may have been taken. */
524                 
525                 do frame->ecode += GET(frame->ecode,1); while (*frame->ecode == OP_ALT);
526                 
527                 frame->offset_top = md->end_offset_top;
528                 frame->eptr = md->end_match_ptr;
529                 
530                 /* For a non-repeating ket, just continue at this level. This also
531                  happens for a repeating ket if no characters were matched in the group.
532                  This is the forcible breaking of infinite loops as implemented in Perl
533                  5.005. If there is an options reset, it will get obeyed in the normal
534                  course of events. */
535                 
536                 if (*frame->ecode == OP_KET || frame->eptr == frame->saved_eptr) {
537                     frame->ecode += 1+LINK_SIZE;
538                     NEXT_OPCODE;
539                 }
540                 
541                 /* The repeating kets try the rest of the pattern or restart from the
542                  preceding bracket, in the appropriate order. We need to reset any options
543                  that changed within the bracket before re-running it, so check the next
544                  opcode. */
545                 
546                 if (*frame->ecode == OP_KETRMIN) {
547                     RMATCH(10, frame->ecode + 1 + LINK_SIZE, frame->eptrb, 0);
548                     if (is_match)
549                         RRETURN;
550                     RMATCH(11, frame->prev, frame->eptrb, match_isgroup);
551                     if (is_match)
552                         RRETURN;
553                 } else { /* OP_KETRMAX */
554                     RMATCH(12, frame->prev, frame->eptrb, match_isgroup);
555                     if (is_match)
556                         RRETURN;
557                     RMATCH(13, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
558                     if (is_match)
559                         RRETURN;
560                 }
561                 RRETURN;
562                 
563                 /* An alternation is the end of a branch; scan along to find the end of the
564                  bracketed group and go to there. */
565                 
566                 BEGIN_OPCODE(ALT):
567                 do frame->ecode += GET(frame->ecode,1); while (*frame->ecode == OP_ALT);
568                 NEXT_OPCODE;
569                 
570                 /* BRAZERO and BRAMINZERO occur just before a bracket group, indicating
571                  that it may occur zero times. It may repeat infinitely, or not at all -
572                  i.e. it could be ()* or ()? in the pattern. Brackets with fixed upper
573                  repeat limits are compiled as a number of copies, with the optional ones
574                  preceded by BRAZERO or BRAMINZERO. */
575                 
576                 BEGIN_OPCODE(BRAZERO):
577                 {
578                     frame->next = frame->ecode+1;
579                     RMATCH(14, frame->next, frame->eptrb, match_isgroup);
580                     if (is_match)
581                         RRETURN;
582                     do frame->next += GET(frame->next,1); while (*frame->next == OP_ALT);
583                     frame->ecode = frame->next + 1+LINK_SIZE;
584                 }
585                 NEXT_OPCODE;
586                 
587                 BEGIN_OPCODE(BRAMINZERO):
588                 {
589                     frame->next = frame->ecode+1;
590                     do frame->next += GET(frame->next,1); while (*frame->next == OP_ALT);
591                     RMATCH(15, frame->next + 1+LINK_SIZE, frame->eptrb, match_isgroup);
592                     if (is_match)
593                         RRETURN;
594                     frame->ecode++;
595                 }
596                 NEXT_OPCODE;
597                 
598                 /* End of a group, repeated or non-repeating. If we are at the end of
599                  an assertion "group", stop matching and return MATCH_MATCH, but record the
600                  current high water mark for use by positive assertions. Do this also
601                  for the "once" (not-backup up) groups. */
602                 
603                 BEGIN_OPCODE(KET):
604                 BEGIN_OPCODE(KETRMIN):
605                 BEGIN_OPCODE(KETRMAX):
606                 frame->prev = frame->ecode - GET(frame->ecode, 1);
607                 frame->saved_eptr = frame->eptrb->epb_saved_eptr;
608                 
609                 /* Back up the stack of bracket start pointers. */
610                 
611                 frame->eptrb = frame->eptrb->epb_prev;
612                 
613                 if (*frame->prev == OP_ASSERT || *frame->prev == OP_ASSERT_NOT || *frame->prev == OP_ONCE) {
614                     md->end_match_ptr = frame->eptr;      /* For ONCE */
615                     md->end_offset_top = frame->offset_top;
616                     is_match = true;
617                     RRETURN;
618                 }
619                 
620                 /* In all other cases except a conditional group we have to check the
621                  group number back at the start and if necessary complete handling an
622                  extraction by setting the offsets and bumping the high water mark. */
623                 
624                 frame->number = *frame->prev - OP_BRA;
625                 
626                 /* For extended extraction brackets (large number), we have to fish out
627                  the number from a dummy opcode at the start. */
628                 
629                 if (frame->number > EXTRACT_BASIC_MAX)
630                     frame->number = GET2(frame->prev, 2+LINK_SIZE);
631                 frame->offset = frame->number << 1;
632                 
633 #ifdef DEBUG
634                 printf("end bracket %d", frame->number);
635                 printf("\n");
636 #endif
637                 
638                 /* Test for a numbered group. This includes groups called as a result
639                  of recursion. Note that whole-pattern recursion is coded as a recurse
640                  into group 0, so it won't be picked up here. Instead, we catch it when
641                  the OP_END is reached. */
642                 
643                 if (frame->number > 0) {
644                     if (frame->offset >= md->offset_max)
645                         md->offset_overflow = true;
646                     else {
647                         md->offset_vector[frame->offset] =
648                         md->offset_vector[md->offset_end - frame->number];
649                         md->offset_vector[frame->offset+1] = frame->eptr - md->start_subject;
650                         if (frame->offset_top <= frame->offset)
651                             frame->offset_top = frame->offset + 2;
652                     }
653                 }
654                 
655                 /* For a non-repeating ket, just continue at this level. This also
656                  happens for a repeating ket if no characters were matched in the group.
657                  This is the forcible breaking of infinite loops as implemented in Perl
658                  5.005. If there is an options reset, it will get obeyed in the normal
659                  course of events. */
660                 
661                 if (*frame->ecode == OP_KET || frame->eptr == frame->saved_eptr) {
662                     frame->ecode += 1 + LINK_SIZE;
663                     NEXT_OPCODE;
664                 }
665                 
666                 /* The repeating kets try the rest of the pattern or restart from the
667                  preceding bracket, in the appropriate order. */
668                 
669                 if (*frame->ecode == OP_KETRMIN) {
670                     RMATCH(16, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
671                     if (is_match)
672                         RRETURN;
673                     RMATCH(17, frame->prev, frame->eptrb, match_isgroup);
674                     if (is_match)
675                         RRETURN;
676                 } else { /* OP_KETRMAX */
677                     RMATCH(18, frame->prev, frame->eptrb, match_isgroup);
678                     if (is_match)
679                         RRETURN;
680                     RMATCH(19, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
681                     if (is_match)
682                         RRETURN;
683                 }
684                 RRETURN;
685                 
686                 /* Start of subject, or after internal newline if multiline. */
687                 
688                 BEGIN_OPCODE(CIRC):
689                 if (frame->eptr != md->start_subject && (!md->multiline || !isNewline(frame->eptr[-1])))
690                     RRETURN_NO_MATCH;
691                 frame->ecode++;
692                 NEXT_OPCODE;
693                 
694                 /* End of subject, or before internal newline if multiline. */
695                 
696                 BEGIN_OPCODE(DOLL):
697                 if (frame->eptr < md->end_subject && (!md->multiline || !isNewline(*frame->eptr)))
698                     RRETURN_NO_MATCH;
699                 frame->ecode++;
700                 NEXT_OPCODE;
701                 
702                 /* Word boundary assertions */
703                 
704                 BEGIN_OPCODE(NOT_WORD_BOUNDARY):
705                 BEGIN_OPCODE(WORD_BOUNDARY):
706                 /* Find out if the previous and current characters are "word" characters.
707                  It takes a bit more work in UTF-8 mode. Characters > 128 are assumed to
708                  be "non-word" characters. */
709                 
710                 if (frame->eptr == md->start_subject)
711                     prev_is_word = false;
712                 else {
713                     const pcre_uchar *lastptr = frame->eptr - 1;
714                     while(ISMIDCHAR(*lastptr))
715                         lastptr--;
716                     GETCHAR(c, lastptr);
717                     prev_is_word = c < 128 && (md->ctypes[c] & ctype_word) != 0;
718                 }
719                 if (frame->eptr >= md->end_subject)
720                     cur_is_word = false;
721                 else {
722                     GETCHAR(c, frame->eptr);
723                     cur_is_word = c < 128 && (md->ctypes[c] & ctype_word) != 0;
724                 }
725                 
726                 /* Now see if the situation is what we want */
727                 
728                 if ((*frame->ecode++ == OP_WORD_BOUNDARY) ? cur_is_word == prev_is_word : cur_is_word != prev_is_word)
729                     RRETURN_NO_MATCH;
730                 NEXT_OPCODE;
731                 
732                 /* Match a single character type; inline for speed */
733                 
734                 BEGIN_OPCODE(ANY):
735                 if (frame->eptr < md->end_subject && isNewline(*frame->eptr))
736                     RRETURN_NO_MATCH;
737                 if (frame->eptr++ >= md->end_subject)
738                     RRETURN_NO_MATCH;
739                 while (frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr))
740                     frame->eptr++;
741                 frame->ecode++;
742                 NEXT_OPCODE;
743                 
744                 BEGIN_OPCODE(NOT_DIGIT):
745                 if (frame->eptr >= md->end_subject)
746                     RRETURN_NO_MATCH;
747                 GETCHARINCTEST(c, frame->eptr);
748                 if (isASCIIDigit(c))
749                     RRETURN_NO_MATCH;
750                 frame->ecode++;
751                 NEXT_OPCODE;
752                 
753                 BEGIN_OPCODE(DIGIT):
754                 if (frame->eptr >= md->end_subject)
755                     RRETURN_NO_MATCH;
756                 GETCHARINCTEST(c, frame->eptr);
757                 if (!isASCIIDigit(c))
758                     RRETURN_NO_MATCH;
759                 frame->ecode++;
760                 NEXT_OPCODE;
761                 
762                 BEGIN_OPCODE(NOT_WHITESPACE):
763                 if (frame->eptr >= md->end_subject)
764                     RRETURN_NO_MATCH;
765                 GETCHARINCTEST(c, frame->eptr);
766                 if (c < 128 && (md->ctypes[c] & ctype_space))
767                     RRETURN_NO_MATCH;
768                 frame->ecode++;
769                 NEXT_OPCODE;
770                 
771                 BEGIN_OPCODE(WHITESPACE):
772                 if (frame->eptr >= md->end_subject)
773                     RRETURN_NO_MATCH;
774                 GETCHARINCTEST(c, frame->eptr);
775                 if (c >= 128 || !(md->ctypes[c] & ctype_space))
776                     RRETURN_NO_MATCH;
777                 frame->ecode++;
778                 NEXT_OPCODE;
779                 
780                 BEGIN_OPCODE(NOT_WORDCHAR):
781                 if (frame->eptr >= md->end_subject)
782                     RRETURN_NO_MATCH;
783                 GETCHARINCTEST(c, frame->eptr);
784                 if (c < 128 && (md->ctypes[c] & ctype_word))
785                     RRETURN_NO_MATCH;
786                 frame->ecode++;
787                 NEXT_OPCODE;
788                 
789                 BEGIN_OPCODE(WORDCHAR):
790                 if (frame->eptr >= md->end_subject)
791                     RRETURN_NO_MATCH;
792                 GETCHARINCTEST(c, frame->eptr);
793                 if (c >= 128 || !(md->ctypes[c] & ctype_word))
794                     RRETURN_NO_MATCH;
795                 frame->ecode++;
796                 NEXT_OPCODE;
797                 
798                 /* Match a back reference, possibly repeatedly. Look past the end of the
799                  item to see if there is repeat information following. The code is similar
800                  to that for character classes, but repeated for efficiency. Then obey
801                  similar code to character type repeats - written out again for speed.
802                  However, if the referenced string is the empty string, always treat
803                  it as matched, any number of times (otherwise there could be infinite
804                  loops). */
805                 
806                 BEGIN_OPCODE(REF):
807                 frame->offset = GET2(frame->ecode, 1) << 1;               /* Doubled ref number */
808                 frame->ecode += 3;                                 /* Advance past item */
809                 
810                 /* If the reference is unset, set the length to be longer than the amount
811                  of subject left; this ensures that every attempt at a match fails. We
812                  can't just fail here, because of the possibility of quantifiers with zero
813                  minima. */
814                 
815                 if (frame->offset >= frame->offset_top || md->offset_vector[frame->offset] < 0)
816                     frame->length = 0;
817                 else
818                     frame->length = md->offset_vector[frame->offset+1] - md->offset_vector[frame->offset];
819                 
820                 /* Set up for repetition, or handle the non-repeated case */
821                 
822                 switch (*frame->ecode) {
823                 case OP_CRSTAR:
824                 case OP_CRMINSTAR:
825                 case OP_CRPLUS:
826                 case OP_CRMINPLUS:
827                 case OP_CRQUERY:
828                 case OP_CRMINQUERY:
829                     c = *frame->ecode++ - OP_CRSTAR;
830                     minimize = (c & 1) != 0;
831                     min = rep_min[c];                 /* Pick up values from tables; */
832                     frame->max = rep_max[c];                 /* zero for max => infinity */
833                     if (frame->max == 0)
834                         frame->max = INT_MAX;
835                     break;
836                     
837                 case OP_CRRANGE:
838                 case OP_CRMINRANGE:
839                     minimize = (*frame->ecode == OP_CRMINRANGE);
840                     min = GET2(frame->ecode, 1);
841                     frame->max = GET2(frame->ecode, 3);
842                     if (frame->max == 0)
843                         frame->max = INT_MAX;
844                     frame->ecode += 5;
845                     break;
846                 
847                 default:               /* No repeat follows */
848                     if (!match_ref(frame->offset, frame->eptr, frame->length, md))
849                         RRETURN_NO_MATCH;
850                     frame->eptr += frame->length;
851                     NEXT_OPCODE;
852                 }
853                 
854                 /* If the length of the reference is zero, just continue with the
855                  main loop. */
856                 
857                 if (frame->length == 0)
858                     NEXT_OPCODE;
859                 
860                 /* First, ensure the minimum number of matches are present. */
861                 
862                 for (i = 1; i <= min; i++) {
863                     if (!match_ref(frame->offset, frame->eptr, frame->length, md))
864                         RRETURN_NO_MATCH;
865                     frame->eptr += frame->length;
866                 }
867                 
868                 /* If min = max, continue at the same level without recursion.
869                  They are not both allowed to be zero. */
870                 
871                 if (min == frame->max)
872                     NEXT_OPCODE;
873                 
874                 /* If minimizing, keep trying and advancing the pointer */
875                 
876                 if (minimize) {
877                     for (frame->fi = min;; frame->fi++) {
878                         RMATCH(20, frame->ecode, frame->eptrb, 0);
879                         if (is_match)
880                             RRETURN;
881                         if (frame->fi >= frame->max || !match_ref(frame->offset, frame->eptr, frame->length, md))
882                             RRETURN;
883                         frame->eptr += frame->length;
884                     }
885                     ASSERT_NOT_REACHED();
886                 }
887                 
888                 /* If maximizing, find the longest string and work backwards */
889                 
890                 else {
891                     frame->pp = frame->eptr;
892                     for (i = min; i < frame->max; i++) {
893                         if (!match_ref(frame->offset, frame->eptr, frame->length, md))
894                             break;
895                         frame->eptr += frame->length;
896                     }
897                     while (frame->eptr >= frame->pp) {
898                         RMATCH(21, frame->ecode, frame->eptrb, 0);
899                         if (is_match)
900                             RRETURN;
901                         frame->eptr -= frame->length;
902                     }
903                     RRETURN_NO_MATCH;
904                 }
905                 ASSERT_NOT_REACHED();
906                 
907                 /* Match a bit-mapped character class, possibly repeatedly. This op code is
908                  used when all the characters in the class have values in the range 0-255,
909                  and either the matching is caseful, or the characters are in the range
910                  0-127 when UTF-8 processing is enabled. The only difference between
911                  OP_CLASS and OP_NCLASS occurs when a data character outside the range is
912                  encountered.
913                  
914                  First, look past the end of the item to see if there is repeat information
915                  following. Then obey similar code to character type repeats - written out
916                  again for speed. */
917                 
918                 BEGIN_OPCODE(NCLASS):
919                 BEGIN_OPCODE(CLASS):
920                 frame->data = frame->ecode + 1;                /* Save for matching */
921                 frame->ecode += 33;                     /* Advance past the item */
922                 
923                 switch (*frame->ecode) {
924                 case OP_CRSTAR:
925                 case OP_CRMINSTAR:
926                 case OP_CRPLUS:
927                 case OP_CRMINPLUS:
928                 case OP_CRQUERY:
929                 case OP_CRMINQUERY:
930                     c = *frame->ecode++ - OP_CRSTAR;
931                     minimize = (c & 1) != 0;
932                     min = rep_min[c];                 /* Pick up values from tables; */
933                     frame->max = rep_max[c];                 /* zero for max => infinity */
934                     if (frame->max == 0)
935                         frame->max = INT_MAX;
936                     break;
937                     
938                 case OP_CRRANGE:
939                 case OP_CRMINRANGE:
940                     minimize = (*frame->ecode == OP_CRMINRANGE);
941                     min = GET2(frame->ecode, 1);
942                     frame->max = GET2(frame->ecode, 3);
943                     if (frame->max == 0)
944                         frame->max = INT_MAX;
945                     frame->ecode += 5;
946                     break;
947                     
948                 default:               /* No repeat follows */
949                     min = frame->max = 1;
950                     break;
951                 }
952                 
953                 /* First, ensure the minimum number of matches are present. */
954                 
955                 for (i = 1; i <= min; i++) {
956                     if (frame->eptr >= md->end_subject)
957                         RRETURN_NO_MATCH;
958                     GETCHARINC(c, frame->eptr);
959                     if (c > 255) {
960                         if (frame->data[-1] == OP_CLASS)
961                             RRETURN_NO_MATCH;
962                     } else {
963                         if ((frame->data[c/8] & (1 << (c&7))) == 0)
964                             RRETURN_NO_MATCH;
965                     }
966                 }
967                 
968                 /* If max == min we can continue with the main loop without the
969                  need to recurse. */
970                 
971                 if (min == frame->max)
972                     NEXT_OPCODE;      
973                 
974                 /* If minimizing, keep testing the rest of the expression and advancing
975                  the pointer while it matches the class. */
976                 if (minimize) {
977                     {
978                         for (frame->fi = min;; frame->fi++) {
979                             RMATCH(22, frame->ecode, frame->eptrb, 0);
980                             if (is_match)
981                                 RRETURN;
982                             if (frame->fi >= frame->max || frame->eptr >= md->end_subject)
983                                 RRETURN;
984                             GETCHARINC(c, frame->eptr);
985                             if (c > 255) {
986                                 if (frame->data[-1] == OP_CLASS)
987                                     RRETURN;
988                             } else {
989                                 if ((frame->data[c/8] & (1 << (c&7))) == 0)
990                                     RRETURN;
991                             }
992                         }
993                     }
994                     ASSERT_NOT_REACHED();
995                 }
996                 /* If maximizing, find the longest possible run, then work backwards. */
997                 else {
998                     frame->pp = frame->eptr;
999                     
1000                     for (i = min; i < frame->max; i++) {
1001                         int len = 1;
1002                         if (frame->eptr >= md->end_subject)
1003                             break;
1004                         GETCHARLEN(c, frame->eptr, len);
1005                         if (c > 255) {
1006                             if (frame->data[-1] == OP_CLASS)
1007                                 break;
1008                         } else {
1009                             if ((frame->data[c/8] & (1 << (c&7))) == 0)
1010                                 break;
1011                         }
1012                         frame->eptr += len;
1013                     }
1014                     for (;;) {
1015                         RMATCH(24, frame->ecode, frame->eptrb, 0);
1016                         if (is_match)
1017                             RRETURN;
1018                         if (frame->eptr-- == frame->pp)
1019                             break;        /* Stop if tried at original pos */
1020                         BACKCHAR(frame->eptr);
1021                     }
1022                     
1023                     RRETURN;
1024                 }
1025                 ASSERT_NOT_REACHED();
1026                 
1027                 /* Match an extended character class. This opcode is encountered only
1028                  in UTF-8 mode, because that's the only time it is compiled. */
1029                 
1030                 BEGIN_OPCODE(XCLASS):
1031                 frame->data = frame->ecode + 1 + LINK_SIZE;                /* Save for matching */
1032                 frame->ecode += GET(frame->ecode, 1);                      /* Advance past the item */
1033                 
1034                 switch (*frame->ecode) {
1035                 case OP_CRSTAR:
1036                 case OP_CRMINSTAR:
1037                 case OP_CRPLUS:
1038                 case OP_CRMINPLUS:
1039                 case OP_CRQUERY:
1040                 case OP_CRMINQUERY:
1041                     c = *frame->ecode++ - OP_CRSTAR;
1042                     minimize = (c & 1) != 0;
1043                     min = rep_min[c];                 /* Pick up values from tables; */
1044                     frame->max = rep_max[c];                 /* zero for max => infinity */
1045                     if (frame->max == 0)
1046                         frame->max = INT_MAX;
1047                     break;
1048                     
1049                 case OP_CRRANGE:
1050                 case OP_CRMINRANGE:
1051                     minimize = (*frame->ecode == OP_CRMINRANGE);
1052                     min = GET2(frame->ecode, 1);
1053                     frame->max = GET2(frame->ecode, 3);
1054                     if (frame->max == 0)
1055                         frame->max = INT_MAX;
1056                     frame->ecode += 5;
1057                     break;
1058                     
1059                 default:               /* No repeat follows */
1060                     min = frame->max = 1;
1061             }
1062                 
1063                 /* First, ensure the minimum number of matches are present. */
1064                 
1065                 for (i = 1; i <= min; i++) {
1066                     if (frame->eptr >= md->end_subject)
1067                         RRETURN_NO_MATCH;
1068                     GETCHARINC(c, frame->eptr);
1069                     if (!_pcre_xclass(c, frame->data))
1070                         RRETURN_NO_MATCH;
1071                 }
1072                 
1073                 /* If max == min we can continue with the main loop without the
1074                  need to recurse. */
1075                 
1076                 if (min == frame->max)
1077                     NEXT_OPCODE;
1078                 
1079                 /* If minimizing, keep testing the rest of the expression and advancing
1080                  the pointer while it matches the class. */
1081                 
1082                 if (minimize) {
1083                     for (frame->fi = min;; frame->fi++) {
1084                         RMATCH(26, frame->ecode, frame->eptrb, 0);
1085                         if (is_match)
1086                             RRETURN;
1087                         if (frame->fi >= frame->max || frame->eptr >= md->end_subject)
1088                             RRETURN;
1089                         GETCHARINC(c, frame->eptr);
1090                         if (!_pcre_xclass(c, frame->data))
1091                             RRETURN;
1092                     }
1093                     ASSERT_NOT_REACHED();
1094                 }
1095                 
1096                 /* If maximizing, find the longest possible run, then work backwards. */
1097                 
1098                 else {
1099                     frame->pp = frame->eptr;
1100                     for (i = min; i < frame->max; i++) {
1101                         int len = 1;
1102                         if (frame->eptr >= md->end_subject)
1103                             break;
1104                         GETCHARLEN(c, frame->eptr, len);
1105                         if (!_pcre_xclass(c, frame->data))
1106                             break;
1107                         frame->eptr += len;
1108                     }
1109                     for(;;) {
1110                         RMATCH(27, frame->ecode, frame->eptrb, 0);
1111                         if (is_match)
1112                             RRETURN;
1113                         if (frame->eptr-- == frame->pp)
1114                             break;        /* Stop if tried at original pos */
1115                         BACKCHAR(frame->eptr)
1116                     }
1117                     RRETURN;
1118                 }
1119                 
1120                 ASSERT_NOT_REACHED();
1121                 
1122                 /* Match a single character, casefully */
1123                 
1124                 BEGIN_OPCODE(CHAR):
1125                 frame->length = 1;
1126                 frame->ecode++;
1127                 GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
1128             {
1129                 int dc;
1130                 frame->ecode += frame->length;
1131                 switch (md->end_subject - frame->eptr) {
1132                 case 0:
1133                     RRETURN_NO_MATCH;
1134                 case 1:
1135                     dc = *frame->eptr++;
1136                     if (IS_LEADING_SURROGATE(dc))
1137                         RRETURN_NO_MATCH;
1138                     break;
1139                     default:
1140                     GETCHARINC(dc, frame->eptr);
1141                 }
1142                 if (frame->fc != dc)
1143                     RRETURN_NO_MATCH;
1144             }
1145                 NEXT_OPCODE;
1146                 
1147                 /* Match a single character, caselessly */
1148                 
1149                 BEGIN_OPCODE(CHARNC):
1150                 frame->length = 1;
1151                 frame->ecode++;
1152                 GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
1153                 
1154                 if (md->end_subject - frame->eptr == 0)
1155                     RRETURN_NO_MATCH;
1156                 
1157             {
1158                 int dc;
1159                 if (md->end_subject - frame->eptr == 1) {
1160                     dc = *frame->eptr++;
1161                     if (IS_LEADING_SURROGATE(dc))
1162                         RRETURN_NO_MATCH;
1163                 } else
1164                     GETCHARINC(dc, frame->eptr);
1165                 frame->ecode += frame->length;
1166                 
1167                 /* If we have Unicode property support, we can use it to test the other
1168                  case of the character, if there is one. */
1169                 
1170                 if (frame->fc != dc) {
1171                     if (dc != _pcre_ucp_othercase(frame->fc))
1172                         RRETURN_NO_MATCH;
1173                 }
1174             }
1175                 NEXT_OPCODE;
1176                 
1177                 /* Match a single ASCII character. */
1178                 
1179                 BEGIN_OPCODE(ASCII_CHAR):
1180                 if (md->end_subject == frame->eptr)
1181                     RRETURN_NO_MATCH;
1182                 if (*frame->eptr != frame->ecode[1])
1183                     RRETURN_NO_MATCH;
1184                 ++frame->eptr;
1185                 frame->ecode += 2;
1186                 NEXT_OPCODE;
1187                 
1188                 /* Match one of two cases of an ASCII character. */
1189                 
1190                 BEGIN_OPCODE(ASCII_LETTER_NC):
1191                 if (md->end_subject == frame->eptr)
1192                     RRETURN_NO_MATCH;
1193                 if ((*frame->eptr | 0x20) != frame->ecode[1])
1194                     RRETURN_NO_MATCH;
1195                 ++frame->eptr;
1196                 frame->ecode += 2;
1197                 NEXT_OPCODE;
1198                 
1199                 /* Match a single character repeatedly; different opcodes share code. */
1200                 
1201                 BEGIN_OPCODE(EXACT):
1202                 min = frame->max = GET2(frame->ecode, 1);
1203                 minimize = false;
1204                 frame->ecode += 3;
1205                 goto REPEATCHAR;
1206                 
1207                 BEGIN_OPCODE(UPTO):
1208                 BEGIN_OPCODE(MINUPTO):
1209                 min = 0;
1210                 frame->max = GET2(frame->ecode, 1);
1211                 minimize = *frame->ecode == OP_MINUPTO;
1212                 frame->ecode += 3;
1213                 goto REPEATCHAR;
1214                 
1215                 BEGIN_OPCODE(STAR):
1216                 BEGIN_OPCODE(MINSTAR):
1217                 BEGIN_OPCODE(PLUS):
1218                 BEGIN_OPCODE(MINPLUS):
1219                 BEGIN_OPCODE(QUERY):
1220                 BEGIN_OPCODE(MINQUERY):
1221                 c = *frame->ecode++ - OP_STAR;
1222                 minimize = (c & 1) != 0;
1223                 min = rep_min[c];                 /* Pick up values from tables; */
1224                 frame->max = rep_max[c];                 /* zero for max => infinity */
1225                 if (frame->max == 0)
1226                     frame->max = INT_MAX;
1227                 
1228                 /* Common code for all repeated single-character matches. We can give
1229                  up quickly if there are fewer than the minimum number of characters left in
1230                  the subject. */
1231                 
1232             REPEATCHAR:
1233                 
1234                 frame->length = 1;
1235                 GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
1236                 if (min * (frame->fc > 0xFFFF ? 2 : 1) > md->end_subject - frame->eptr)
1237                     RRETURN_NO_MATCH;
1238                 frame->ecode += frame->length;
1239                 
1240                 if (frame->fc <= 0xFFFF) {
1241                     int othercase = md->caseless ? _pcre_ucp_othercase(frame->fc) : -1;
1242                     
1243                     for (i = 1; i <= min; i++) {
1244                         if (*frame->eptr != frame->fc && *frame->eptr != othercase)
1245                             RRETURN_NO_MATCH;
1246                         ++frame->eptr;
1247                     }
1248                     
1249                     if (min == frame->max)
1250                         NEXT_OPCODE;
1251                     
1252                     if (minimize) {
1253                         frame->repeat_othercase = othercase;
1254                         for (frame->fi = min;; frame->fi++) {
1255                             RMATCH(28, frame->ecode, frame->eptrb, 0);
1256                             if (is_match)
1257                                 RRETURN;
1258                             if (frame->fi >= frame->max || frame->eptr >= md->end_subject)
1259                                 RRETURN;
1260                             if (*frame->eptr != frame->fc && *frame->eptr != frame->repeat_othercase)
1261                                 RRETURN;
1262                             ++frame->eptr;
1263                         }
1264                         ASSERT_NOT_REACHED();
1265                     } else {
1266                         frame->pp = frame->eptr;
1267                         for (i = min; i < frame->max; i++) {
1268                             if (frame->eptr >= md->end_subject)
1269                                 break;
1270                             if (*frame->eptr != frame->fc && *frame->eptr != othercase)
1271                                 break;
1272                             ++frame->eptr;
1273                         }
1274                         while (frame->eptr >= frame->pp) {
1275                             RMATCH(29, frame->ecode, frame->eptrb, 0);
1276                             if (is_match)
1277                                 RRETURN;
1278                             --frame->eptr;
1279                         }
1280                         RRETURN_NO_MATCH;
1281                     }
1282                     ASSERT_NOT_REACHED();
1283                 } else {
1284                     /* No case on surrogate pairs, so no need to bother with "othercase". */
1285                     
1286                     for (i = 1; i <= min; i++) {
1287                         int nc;
1288                         GETCHAR(nc, frame->eptr);
1289                         if (nc != frame->fc)
1290                             RRETURN_NO_MATCH;
1291                         frame->eptr += 2;
1292                     }
1293                     
1294                     if (min == frame->max)
1295                         NEXT_OPCODE;
1296                     
1297                     if (minimize) {
1298                         for (frame->fi = min;; frame->fi++) {
1299                             int nc;
1300                             RMATCH(30, frame->ecode, frame->eptrb, 0);
1301                             if (is_match)
1302                                 RRETURN;
1303                             if (frame->fi >= frame->max || frame->eptr >= md->end_subject)
1304                                 RRETURN;
1305                             GETCHAR(nc, frame->eptr);
1306                             if (*frame->eptr != frame->fc)
1307                                 RRETURN;
1308                             frame->eptr += 2;
1309                         }
1310                         ASSERT_NOT_REACHED();
1311                     } else {
1312                         frame->pp = frame->eptr;
1313                         for (i = min; i < frame->max; i++) {
1314                             int nc;
1315                             if (frame->eptr > md->end_subject - 2)
1316                                 break;
1317                             GETCHAR(nc, frame->eptr);
1318                             if (*frame->eptr != frame->fc)
1319                                 break;
1320                             frame->eptr += 2;
1321                         }
1322                         while (frame->eptr >= frame->pp) {
1323                             RMATCH(31, frame->ecode, frame->eptrb, 0);
1324                             if (is_match)
1325                                 RRETURN;
1326                             frame->eptr -= 2;
1327                         }
1328                         RRETURN_NO_MATCH;
1329                     }
1330                     ASSERT_NOT_REACHED();
1331                 }
1332                 ASSERT_NOT_REACHED();
1333                 
1334                 /* Match a negated single one-byte character. The character we are
1335                  checking can be multibyte. */
1336                 
1337                 BEGIN_OPCODE(NOT):
1338                 if (frame->eptr >= md->end_subject)
1339                     RRETURN_NO_MATCH;
1340                 frame->ecode++;
1341                 GETCHARINCTEST(c, frame->eptr);
1342                 if (md->caseless) {
1343                     if (c < 128)
1344                         c = md->lcc[c];
1345                     if (md->lcc[*frame->ecode++] == c)
1346                         RRETURN_NO_MATCH;
1347                 } else {
1348                     if (*frame->ecode++ == c)
1349                         RRETURN_NO_MATCH;
1350                 }
1351                 NEXT_OPCODE;
1352                 
1353                 /* Match a negated single one-byte character repeatedly. This is almost a
1354                  repeat of the code for a repeated single character, but I haven't found a
1355                  nice way of commoning these up that doesn't require a test of the
1356                  positive/negative option for each character match. Maybe that wouldn't add
1357                  very much to the time taken, but character matching *is* what this is all
1358                  about... */
1359                 
1360                 BEGIN_OPCODE(NOTEXACT):
1361                 min = frame->max = GET2(frame->ecode, 1);
1362                 minimize = false;
1363                 frame->ecode += 3;
1364                 goto REPEATNOTCHAR;
1365                 
1366                 BEGIN_OPCODE(NOTUPTO):
1367                 BEGIN_OPCODE(NOTMINUPTO):
1368                 min = 0;
1369                 frame->max = GET2(frame->ecode, 1);
1370                 minimize = *frame->ecode == OP_NOTMINUPTO;
1371                 frame->ecode += 3;
1372                 goto REPEATNOTCHAR;
1373                 
1374                 BEGIN_OPCODE(NOTSTAR):
1375                 BEGIN_OPCODE(NOTMINSTAR):
1376                 BEGIN_OPCODE(NOTPLUS):
1377                 BEGIN_OPCODE(NOTMINPLUS):
1378                 BEGIN_OPCODE(NOTQUERY):
1379                 BEGIN_OPCODE(NOTMINQUERY):
1380                 c = *frame->ecode++ - OP_NOTSTAR;
1381                 minimize = (c & 1) != 0;
1382                 min = rep_min[c];                 /* Pick up values from tables; */
1383                 frame->max = rep_max[c];                 /* zero for max => infinity */
1384                 if (frame->max == 0) frame->max = INT_MAX;
1385                 
1386                 /* Common code for all repeated single-byte matches. We can give up quickly
1387                  if there are fewer than the minimum number of bytes left in the
1388                  subject. */
1389                 
1390             REPEATNOTCHAR:
1391                 if (min > md->end_subject - frame->eptr)
1392                     RRETURN_NO_MATCH;
1393                 frame->fc = *frame->ecode++;
1394                 
1395                 /* The code is duplicated for the caseless and caseful cases, for speed,
1396                  since matching characters is likely to be quite common. First, ensure the
1397                  minimum number of matches are present. If min = max, continue at the same
1398                  level without recursing. Otherwise, if minimizing, keep trying the rest of
1399                  the expression and advancing one matching character if failing, up to the
1400                  maximum. Alternatively, if maximizing, find the maximum number of
1401                  characters and work backwards. */
1402                 
1403                 DPRINTF(("negative matching %c{%d,%d}\n", frame->fc, min, frame->max));
1404                 
1405                 if (md->caseless) {
1406                     if (frame->fc < 128)
1407                         frame->fc = md->lcc[frame->fc];
1408                     
1409                     {
1410                         register int d;
1411                         for (i = 1; i <= min; i++) {
1412                             GETCHARINC(d, frame->eptr);
1413                             if (d < 128)
1414                                 d = md->lcc[d];
1415                             if (frame->fc == d)
1416                                 RRETURN_NO_MATCH;
1417                         }
1418                     }
1419                     
1420                     if (min == frame->max)
1421                         NEXT_OPCODE;      
1422                     
1423                     if (minimize) {
1424                         register int d;
1425                         for (frame->fi = min;; frame->fi++) {
1426                             RMATCH(38, frame->ecode, frame->eptrb, 0);
1427                             if (is_match)
1428                                 RRETURN;
1429                             GETCHARINC(d, frame->eptr);
1430                             if (d < 128)
1431                                 d = md->lcc[d];
1432                             if (frame->fi >= frame->max || frame->eptr >= md->end_subject || frame->fc == d)
1433                                 RRETURN;
1434                         }
1435                         ASSERT_NOT_REACHED();
1436                     }
1437                     
1438                     /* Maximize case */
1439                     
1440                     else {
1441                         frame->pp = frame->eptr;
1442                         
1443                         {
1444                             register int d;
1445                             for (i = min; i < frame->max; i++) {
1446                                 int len = 1;
1447                                 if (frame->eptr >= md->end_subject)
1448                                     break;
1449                                 GETCHARLEN(d, frame->eptr, len);
1450                                 if (d < 128)
1451                                     d = md->lcc[d];
1452                                 if (frame->fc == d)
1453                                     break;
1454                                 frame->eptr += len;
1455                             }
1456                             for (;;) {
1457                                 RMATCH(40, frame->ecode, frame->eptrb, 0);
1458                                 if (is_match)
1459                                     RRETURN;
1460                                 if (frame->eptr-- == frame->pp)
1461                                     break;        /* Stop if tried at original pos */
1462                                 BACKCHAR(frame->eptr);
1463                             }
1464                         }
1465                         
1466                         RRETURN;
1467                     }
1468                     ASSERT_NOT_REACHED();
1469                 }
1470                 
1471                 /* Caseful comparisons */
1472                 
1473                 else {
1474                     {
1475                         register int d;
1476                         for (i = 1; i <= min; i++) {
1477                             GETCHARINC(d, frame->eptr);
1478                             if (frame->fc == d)
1479                                 RRETURN_NO_MATCH;
1480                         }
1481                     }
1482                     
1483                     if (min == frame->max)
1484                         NEXT_OPCODE;
1485                     
1486                     if (minimize) {
1487                         register int d;
1488                         for (frame->fi = min;; frame->fi++) {
1489                             RMATCH(42, frame->ecode, frame->eptrb, 0);
1490                             if (is_match)
1491                                 RRETURN;
1492                             GETCHARINC(d, frame->eptr);
1493                             if (frame->fi >= frame->max || frame->eptr >= md->end_subject || frame->fc == d)
1494                                 RRETURN;
1495                         }
1496                         ASSERT_NOT_REACHED();
1497                     }
1498                     
1499                     /* Maximize case */
1500                     
1501                     else {
1502                         frame->pp = frame->eptr;
1503                         
1504                         {
1505                             register int d;
1506                             for (i = min; i < frame->max; i++) {
1507                                 int len = 1;
1508                                 if (frame->eptr >= md->end_subject)
1509                                     break;
1510                                 GETCHARLEN(d, frame->eptr, len);
1511                                 if (frame->fc == d)
1512                                     break;
1513                                 frame->eptr += len;
1514                             }
1515                             for (;;) {
1516                                 RMATCH(44, frame->ecode, frame->eptrb, 0);
1517                                 if (is_match)
1518                                     RRETURN;
1519                                 if (frame->eptr-- == frame->pp)
1520                                     break;        /* Stop if tried at original pos */
1521                                 BACKCHAR(frame->eptr);
1522                             }
1523                         }
1524                         
1525                         RRETURN;
1526                     }
1527                 }
1528                 ASSERT_NOT_REACHED();
1529                 
1530                 /* Match a single character type repeatedly; several different opcodes
1531                  share code. This is very similar to the code for single characters, but we
1532                  repeat it in the interests of efficiency. */
1533                 
1534                 BEGIN_OPCODE(TYPEEXACT):
1535                 min = frame->max = GET2(frame->ecode, 1);
1536                 minimize = true;
1537                 frame->ecode += 3;
1538                 goto REPEATTYPE;
1539                 
1540                 BEGIN_OPCODE(TYPEUPTO):
1541                 BEGIN_OPCODE(TYPEMINUPTO):
1542                 min = 0;
1543                 frame->max = GET2(frame->ecode, 1);
1544                 minimize = *frame->ecode == OP_TYPEMINUPTO;
1545                 frame->ecode += 3;
1546                 goto REPEATTYPE;
1547                 
1548                 BEGIN_OPCODE(TYPESTAR):
1549                 BEGIN_OPCODE(TYPEMINSTAR):
1550                 BEGIN_OPCODE(TYPEPLUS):
1551                 BEGIN_OPCODE(TYPEMINPLUS):
1552                 BEGIN_OPCODE(TYPEQUERY):
1553                 BEGIN_OPCODE(TYPEMINQUERY):
1554                 c = *frame->ecode++ - OP_TYPESTAR;
1555                 minimize = (c & 1) != 0;
1556                 min = rep_min[c];                 /* Pick up values from tables; */
1557                 frame->max = rep_max[c];                 /* zero for max => infinity */
1558                 if (frame->max == 0)
1559                     frame->max = INT_MAX;
1560                 
1561                 /* Common code for all repeated single character type matches. Note that
1562                  in UTF-8 mode, '.' matches a character of any length, but for the other
1563                  character types, the valid characters are all one-byte long. */
1564                 
1565             REPEATTYPE:
1566                 frame->ctype = *frame->ecode++;      /* Code for the character type */
1567                 
1568                 /* First, ensure the minimum number of matches are present. Use inline
1569                  code for maximizing the speed, and do the type test once at the start
1570                  (i.e. keep it out of the loop). Also we can test that there are at least
1571                  the minimum number of bytes before we start. This isn't as effective in
1572                  UTF-8 mode, but it does no harm. Separate the UTF-8 code completely as that
1573                  is tidier. Also separate the UCP code, which can be the same for both UTF-8
1574                  and single-bytes. */
1575                 
1576                 if (min > md->end_subject - frame->eptr)
1577                     RRETURN_NO_MATCH;
1578                 if (min > 0) {
1579                     switch(frame->ctype) {
1580                         case OP_ANY:
1581                             for (i = 1; i <= min; i++) {
1582                                 if (frame->eptr >= md->end_subject || isNewline(*frame->eptr))
1583                                     RRETURN_NO_MATCH;
1584                                 ++frame->eptr;
1585                                 while (frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr))
1586                                     frame->eptr++;
1587                             }
1588                             break;
1589                             
1590                             case OP_NOT_DIGIT:
1591                             for (i = 1; i <= min; i++) {
1592                                 if (frame->eptr >= md->end_subject)
1593                                     RRETURN_NO_MATCH;
1594                                 GETCHARINC(c, frame->eptr);
1595                                 if (isASCIIDigit(c))
1596                                     RRETURN_NO_MATCH;
1597                             }
1598                             break;
1599                             
1600                             case OP_DIGIT:
1601                             for (i = 1; i <= min; i++) {
1602                                 if (frame->eptr >= md->end_subject || !isASCIIDigit(*frame->eptr++))
1603                                     RRETURN_NO_MATCH;
1604                                 /* No need to skip more bytes - we know it's a 1-byte character */
1605                             }
1606                             break;
1607                             
1608                             case OP_NOT_WHITESPACE:
1609                             for (i = 1; i <= min; i++) {
1610                                 if (frame->eptr >= md->end_subject ||
1611                                     (*frame->eptr < 128 && (md->ctypes[*frame->eptr] & ctype_space) != 0))
1612                                     RRETURN_NO_MATCH;
1613                                 while (++frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr));
1614                             }
1615                             break;
1616                             
1617                             case OP_WHITESPACE:
1618                             for (i = 1; i <= min; i++) {
1619                                 if (frame->eptr >= md->end_subject ||
1620                                     *frame->eptr >= 128 || (md->ctypes[*frame->eptr++] & ctype_space) == 0)
1621                                     RRETURN_NO_MATCH;
1622                                 /* No need to skip more bytes - we know it's a 1-byte character */
1623                             }
1624                             break;
1625                             
1626                             case OP_NOT_WORDCHAR:
1627                             for (i = 1; i <= min; i++) {
1628                                 if (frame->eptr >= md->end_subject ||
1629                                     (*frame->eptr < 128 && (md->ctypes[*frame->eptr] & ctype_word) != 0))
1630                                     RRETURN_NO_MATCH;
1631                                 while (++frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr));
1632                             }
1633                             break;
1634                             
1635                             case OP_WORDCHAR:
1636                             for (i = 1; i <= min; i++) {
1637                                 if (frame->eptr >= md->end_subject ||
1638                                     *frame->eptr >= 128 || (md->ctypes[*frame->eptr++] & ctype_word) == 0)
1639                                     RRETURN_NO_MATCH;
1640                                 /* No need to skip more bytes - we know it's a 1-byte character */
1641                             }
1642                             break;
1643                             
1644                             default:
1645                             ASSERT_NOT_REACHED();
1646                             RRETURN_ERROR(JSRegExpErrorInternal);
1647                     }  /* End switch(frame->ctype) */
1648                 }
1649                 
1650                 /* If min = max, continue at the same level without recursing */
1651                 
1652                 if (min == frame->max)
1653                     NEXT_OPCODE;    
1654                 
1655                 /* If minimizing, we have to test the rest of the pattern before each
1656                  subsequent match. */
1657                 
1658                 if (minimize) {
1659                     for (frame->fi = min;; frame->fi++) {
1660                         RMATCH(48, frame->ecode, frame->eptrb, 0);
1661                         if (is_match)
1662                             RRETURN;
1663                         if (frame->fi >= frame->max || frame->eptr >= md->end_subject)
1664                             RRETURN;
1665                         
1666                         GETCHARINC(c, frame->eptr);
1667                         switch(frame->ctype) {
1668                         case OP_ANY:
1669                             if (isNewline(c))
1670                                 RRETURN;
1671                             break;
1672                             
1673                         case OP_NOT_DIGIT:
1674                             if (isASCIIDigit(c))
1675                                 RRETURN;
1676                             break;
1677                             
1678                         case OP_DIGIT:
1679                             if (!isASCIIDigit(c))
1680                                 RRETURN;
1681                             break;
1682                             
1683                         case OP_NOT_WHITESPACE:
1684                             if (c < 128 && (md->ctypes[c] & ctype_space))
1685                                 RRETURN;
1686                             break;
1687                             
1688                         case OP_WHITESPACE:
1689                             if  (c >= 128 || !(md->ctypes[c] & ctype_space))
1690                                 RRETURN;
1691                             break;
1692                             
1693                         case OP_NOT_WORDCHAR:
1694                             if (c < 128 && (md->ctypes[c] & ctype_word))
1695                                 RRETURN;
1696                             break;
1697                             
1698                         case OP_WORDCHAR:
1699                             if (c >= 128 || !(md->ctypes[c] & ctype_word))
1700                                 RRETURN;
1701                             break;
1702                             
1703                         default:
1704                             ASSERT_NOT_REACHED();
1705                             RRETURN_ERROR(JSRegExpErrorInternal);
1706                         }
1707                     }
1708                     ASSERT_NOT_REACHED();
1709                 }
1710                 
1711                 /* If maximizing it is worth using inline code for speed, doing the type
1712                  test once at the start (i.e. keep it out of the loop). */
1713                 
1714                 else {
1715                     frame->pp = frame->eptr;  /* Remember where we started */
1716                     
1717                     switch(frame->ctype) {
1718                         case OP_ANY:
1719                             
1720                             /* Special code is required for UTF8, but when the maximum is unlimited
1721                              we don't need it, so we repeat the non-UTF8 code. This is probably
1722                              worth it, because .* is quite a common idiom. */
1723                             
1724                             if (frame->max < INT_MAX) {
1725                                 for (i = min; i < frame->max; i++) {
1726                                     if (frame->eptr >= md->end_subject || isNewline(*frame->eptr))
1727                                         break;
1728                                     frame->eptr++;
1729                                     while (frame->eptr < md->end_subject && (*frame->eptr & 0xc0) == 0x80)
1730                                         frame->eptr++;
1731                                 }
1732                             }
1733                             
1734                             /* Handle unlimited UTF-8 repeat */
1735                             
1736                             else {
1737                                 for (i = min; i < frame->max; i++) {
1738                                     if (frame->eptr >= md->end_subject || isNewline(*frame->eptr))
1739                                         break;
1740                                     frame->eptr++;
1741                                 }
1742                                 break;
1743                             }
1744                             break;
1745                             
1746                             case OP_NOT_DIGIT:
1747                             for (i = min; i < frame->max; i++) {
1748                                 int len = 1;
1749                                 if (frame->eptr >= md->end_subject)
1750                                     break;
1751                                 GETCHARLEN(c, frame->eptr, len);
1752                                 if (isASCIIDigit(c))
1753                                     break;
1754                                 frame->eptr+= len;
1755                             }
1756                             break;
1757                             
1758                             case OP_DIGIT:
1759                             for (i = min; i < frame->max; i++) {
1760                                 int len = 1;
1761                                 if (frame->eptr >= md->end_subject)
1762                                     break;
1763                                 GETCHARLEN(c, frame->eptr, len);
1764                                 if (!isASCIIDigit(c))
1765                                     break;
1766                                 frame->eptr+= len;
1767                             }
1768                             break;
1769                             
1770                             case OP_NOT_WHITESPACE:
1771                             for (i = min; i < frame->max; i++) {
1772                                 int len = 1;
1773                                 if (frame->eptr >= md->end_subject)
1774                                     break;
1775                                 GETCHARLEN(c, frame->eptr, len);
1776                                 if (c < 128 && (md->ctypes[c] & ctype_space))
1777                                     break;
1778                                 frame->eptr+= len;
1779                             }
1780                             break;
1781                             
1782                             case OP_WHITESPACE:
1783                             for (i = min; i < frame->max; i++) {
1784                                 int len = 1;
1785                                 if (frame->eptr >= md->end_subject)
1786                                     break;
1787                                 GETCHARLEN(c, frame->eptr, len);
1788                                 if (c >= 128 || !(md->ctypes[c] & ctype_space))
1789                                     break;
1790                                 frame->eptr+= len;
1791                             }
1792                             break;
1793                             
1794                             case OP_NOT_WORDCHAR:
1795                             for (i = min; i < frame->max; i++) {
1796                                 int len = 1;
1797                                 if (frame->eptr >= md->end_subject)
1798                                     break;
1799                                 GETCHARLEN(c, frame->eptr, len);
1800                                 if (c < 128 && (md->ctypes[c] & ctype_word))
1801                                     break;
1802                                 frame->eptr+= len;
1803                             }
1804                             break;
1805                             
1806                             case OP_WORDCHAR:
1807                             for (i = min; i < frame->max; i++) {
1808                                 int len = 1;
1809                                 if (frame->eptr >= md->end_subject)
1810                                     break;
1811                                 GETCHARLEN(c, frame->eptr, len);
1812                                 if (c >= 128 || !(md->ctypes[c] & ctype_word))
1813                                     break;
1814                                 frame->eptr+= len;
1815                             }
1816                             break;
1817                             
1818                             default:
1819                             ASSERT_NOT_REACHED();
1820                             RRETURN_ERROR(JSRegExpErrorInternal);
1821                     }
1822                     
1823                     /* frame->eptr is now past the end of the maximum run */
1824                     
1825                     for (;;) {
1826                         RMATCH(52, frame->ecode, frame->eptrb, 0);
1827                         if (is_match)
1828                             RRETURN;
1829                         if (frame->eptr-- == frame->pp)
1830                             break;        /* Stop if tried at original pos */
1831                         BACKCHAR(frame->eptr);
1832                     }
1833                     
1834                     /* Get here if we can't make it match with any permitted repetitions */
1835                     
1836                     RRETURN;
1837                 }
1838                 ASSERT_NOT_REACHED();
1839                 
1840                 BEGIN_OPCODE(CRMINPLUS):
1841                 BEGIN_OPCODE(CRMINQUERY):
1842                 BEGIN_OPCODE(CRMINRANGE):
1843                 BEGIN_OPCODE(CRMINSTAR):
1844                 BEGIN_OPCODE(CRPLUS):
1845                 BEGIN_OPCODE(CRQUERY):
1846                 BEGIN_OPCODE(CRRANGE):
1847                 BEGIN_OPCODE(CRSTAR):
1848                 ASSERT_NOT_REACHED();
1849                 RRETURN_ERROR(JSRegExpErrorInternal);
1850                 
1851 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
1852             CAPTURING_BRACKET:
1853 #else
1854                 default:
1855 #endif
1856                 /* Opening capturing bracket. If there is space in the offset vector, save
1857                  the current subject position in the working slot at the top of the vector. We
1858                  mustn't change the current values of the data slot, because they may be set
1859                  from a previous iteration of this group, and be referred to by a reference
1860                  inside the group.
1861                  
1862                  If the bracket fails to match, we need to restore this value and also the
1863                  values of the final offsets, in case they were set by a previous iteration of
1864                  the same bracket.
1865                  
1866                  If there isn't enough space in the offset vector, treat this as if it were a
1867                  non-capturing bracket. Don't worry about setting the flag for the error case
1868                  here; that is handled in the code for KET. */
1869                 
1870                 ASSERT(*frame->ecode > OP_BRA);
1871                 
1872                 frame->number = *frame->ecode - OP_BRA;
1873                 
1874                 /* For extended extraction brackets (large number), we have to fish out the
1875                  number from a dummy opcode at the start. */
1876                 
1877                 if (frame->number > EXTRACT_BASIC_MAX)
1878                     frame->number = GET2(frame->ecode, 2+LINK_SIZE);
1879                 frame->offset = frame->number << 1;
1880                 
1881 #ifdef DEBUG
1882                 printf("start bracket %d subject=", frame->number);
1883                 pchars(frame->eptr, 16, true, md);
1884                 printf("\n");
1885 #endif
1886                 
1887                 if (frame->offset < md->offset_max) {
1888                     frame->save_offset1 = md->offset_vector[frame->offset];
1889                     frame->save_offset2 = md->offset_vector[frame->offset + 1];
1890                     frame->save_offset3 = md->offset_vector[md->offset_end - frame->number];
1891                     
1892                     DPRINTF(("saving %d %d %d\n", frame->save_offset1, frame->save_offset2, frame->save_offset3));
1893                     md->offset_vector[md->offset_end - frame->number] = frame->eptr - md->start_subject;
1894                     
1895                     do {
1896                         RMATCH(1, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
1897                         if (is_match) RRETURN;
1898                         frame->ecode += GET(frame->ecode, 1);
1899                     } while (*frame->ecode == OP_ALT);
1900                     
1901                     DPRINTF(("bracket %d failed\n", frame->number));
1902                     
1903                     md->offset_vector[frame->offset] = frame->save_offset1;
1904                     md->offset_vector[frame->offset + 1] = frame->save_offset2;
1905                     md->offset_vector[md->offset_end - frame->number] = frame->save_offset3;
1906                     
1907                     RRETURN;
1908                 }
1909                 
1910                 /* Insufficient room for saving captured contents */
1911                 
1912                 goto NON_CAPTURING_BRACKET;
1913         }
1914         
1915         /* Do not stick any code in here without much thought; it is assumed
1916          that "continue" in the code above comes out to here to repeat the main
1917          loop. */
1918         
1919     } /* End of main loop */
1920     
1921     ASSERT_NOT_REACHED();
1922     
1923 #ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
1924     
1925 RRETURN_SWITCH:
1926     switch (frame->where)
1927     {
1928         case 0: goto RETURN;
1929         case 1: goto RRETURN_1;
1930         case 2: goto RRETURN_2;
1931         case 6: goto RRETURN_6;
1932         case 7: goto RRETURN_7;
1933         case 9: goto RRETURN_9;
1934         case 10: goto RRETURN_10;
1935         case 11: goto RRETURN_11;
1936         case 12: goto RRETURN_12;
1937         case 13: goto RRETURN_13;
1938         case 14: goto RRETURN_14;
1939         case 15: goto RRETURN_15;
1940         case 16: goto RRETURN_16;
1941         case 17: goto RRETURN_17;
1942         case 18: goto RRETURN_18;
1943         case 19: goto RRETURN_19;
1944         case 20: goto RRETURN_20;
1945         case 21: goto RRETURN_21;
1946         case 22: goto RRETURN_22;
1947         case 24: goto RRETURN_24;
1948         case 26: goto RRETURN_26;
1949         case 27: goto RRETURN_27;
1950         case 28: goto RRETURN_28;
1951         case 29: goto RRETURN_29;
1952         case 30: goto RRETURN_30;
1953         case 31: goto RRETURN_31;
1954         case 38: goto RRETURN_38;
1955         case 40: goto RRETURN_40;
1956         case 42: goto RRETURN_42;
1957         case 44: goto RRETURN_44;
1958         case 48: goto RRETURN_48;
1959         case 52: goto RRETURN_52;
1960     }
1961     
1962     abort();
1963     RRETURN_ERROR(JSRegExpErrorInternal);
1964     
1965 #endif
1966     
1967 RETURN:
1968     return is_match ? MATCH_MATCH : MATCH_NOMATCH;
1969     
1970 RETURN_ERROR:
1971     while (!(frame >= stackframes && frame < stackframesend)) {
1972         newframe = frame->prevframe;
1973         delete frame;
1974         frame = newframe;
1975     }
1976     return i;
1977 }
1978
1979
1980 /*************************************************
1981 *         Execute a Regular Expression           *
1982 *************************************************/
1983
1984 /* This function applies a compiled re to a subject string and picks out
1985 portions of the string if it matches. Two elements in the vector are set for
1986 each substring: the offsets to the start and end of the substring.
1987
1988 Arguments:
1989   argument_re     points to the compiled expression
1990   extra_data      points to extra data or is NULL
1991   subject         points to the subject string
1992   length          length of subject string (may contain binary zeros)
1993   start_offset    where to start in the subject string
1994   options         option bits
1995   offsets         points to a vector of ints to be filled in with offsets
1996   offsetcount     the number of elements in the vector
1997
1998 Returns:          > 0 => success; value is the number of elements filled in
1999                   = 0 => success, but offsets is not big enough
2000                    -1 => failed to match
2001                  < -1 => some kind of unexpected problem
2002 */
2003
2004 int
2005 jsRegExpExecute(const pcre *argument_re,
2006   const UChar* subject, int length, int start_offset, int *offsets,
2007   int offsetcount)
2008 {
2009 int rc, resetcount, ocount;
2010 int first_byte = -1;
2011 int req_byte = -1;
2012 int req_byte2 = -1;
2013 BOOL using_temporary_offsets = false;
2014 BOOL first_byte_caseless = false;
2015 BOOL startline;
2016 BOOL req_byte_caseless = false;
2017 match_data match_block;
2018 USPTR start_match = (USPTR)subject + start_offset;
2019 USPTR end_subject;
2020 USPTR req_byte_ptr = start_match - 1;
2021 const uschar *start_code;
2022
2023 const real_pcre *external_re = (const real_pcre *)argument_re;
2024 const real_pcre *re = external_re;
2025
2026 /* Plausibility checks */
2027
2028 ASSERT(re);
2029 ASSERT(subject);
2030 ASSERT(offsetcount >= 0);
2031 ASSERT(offsets || offsetcount == 0);
2032
2033 /* Set up other data */
2034
2035 startline = (re->options & PCRE_STARTLINE) != 0;
2036
2037 /* The code starts after the real_pcre block and the capture name table. */
2038
2039 start_code = (const uschar *)(external_re + 1);
2040
2041 match_block.start_subject = (USPTR)subject;
2042 match_block.end_subject = match_block.start_subject + length;
2043 end_subject = match_block.end_subject;
2044
2045 match_block.lcc = _pcre_default_tables + lcc_offset;
2046 match_block.ctypes = _pcre_default_tables + ctypes_offset;
2047
2048 match_block.multiline = (re->options & PCRE_MULTILINE) != 0;
2049 match_block.caseless = (re->options & PCRE_CASELESS) != 0;
2050
2051 /* If the expression has got more back references than the offsets supplied can
2052 hold, we get a temporary chunk of working store to use during the matching.
2053 Otherwise, we can use the vector supplied, rounding down its size to a multiple
2054 of 3. */
2055
2056 ocount = offsetcount - (offsetcount % 3);
2057
2058 if (re->top_backref > 0 && re->top_backref >= ocount/3)
2059   {
2060   ocount = re->top_backref * 3 + 3;
2061   match_block.offset_vector = new int[ocount];
2062   if (match_block.offset_vector == NULL) return JSRegExpErrorNoMemory;
2063   using_temporary_offsets = true;
2064   DPRINTF(("Got memory to hold back references\n"));
2065   }
2066 else match_block.offset_vector = offsets;
2067
2068 match_block.offset_end = ocount;
2069 match_block.offset_max = (2*ocount)/3;
2070 match_block.offset_overflow = false;
2071
2072 /* Compute the minimum number of offsets that we need to reset each time. Doing
2073 this makes a huge difference to execution time when there aren't many brackets
2074 in the pattern. */
2075
2076 resetcount = 2 + re->top_bracket * 2;
2077 if (resetcount > offsetcount) resetcount = ocount;
2078
2079 /* Reset the working variable associated with each extraction. These should
2080 never be used unless previously set, but they get saved and restored, and so we
2081 initialize them to avoid reading uninitialized locations. */
2082
2083 if (match_block.offset_vector != NULL)
2084   {
2085   register int *iptr = match_block.offset_vector + ocount;
2086   register int *iend = iptr - resetcount/2 + 1;
2087   while (--iptr >= iend) *iptr = -1;
2088   }
2089
2090 /* Set up the first character to match, if available. The first_byte value is
2091 never set for an anchored regular expression, but the anchoring may be forced
2092 at run time, so we have to test for anchoring. The first char may be unset for
2093 an unanchored pattern, of course. If there's no first char and the pattern was
2094 studied, there may be a bitmap of possible first characters. */
2095
2096   if ((re->options & PCRE_FIRSTSET) != 0)
2097     {
2098     first_byte = re->first_byte & 255;
2099     if ((first_byte_caseless = ((re->first_byte & REQ_CASELESS) != 0)) == true)
2100       first_byte = match_block.lcc[first_byte];
2101     }
2102
2103 /* For anchored or unanchored matches, there may be a "last known required
2104 character" set. */
2105
2106 if ((re->options & PCRE_REQCHSET) != 0)
2107   {
2108   req_byte = re->req_byte & 255;
2109   req_byte_caseless = (re->req_byte & REQ_CASELESS) != 0;
2110   req_byte2 = (_pcre_default_tables + fcc_offset)[req_byte];  /* case flipped */
2111   }
2112
2113 /* Loop for handling unanchored repeated matching attempts; for anchored regexs
2114 the loop runs just once. */
2115
2116 do
2117   {
2118   USPTR save_end_subject = end_subject;
2119
2120   /* Reset the maximum number of extractions we might see. */
2121
2122   if (match_block.offset_vector != NULL)
2123     {
2124     register int *iptr = match_block.offset_vector;
2125     register int *iend = iptr + resetcount;
2126     while (iptr < iend) *iptr++ = -1;
2127     }
2128
2129   /* Advance to a unique first char if possible. If firstline is true, the
2130   start of the match is constrained to the first line of a multiline string.
2131   Implement this by temporarily adjusting end_subject so that we stop scanning
2132   at a newline. If the match fails at the newline, later code breaks this loop.
2133   */
2134
2135   /* Now test for a unique first byte */
2136
2137   if (first_byte >= 0)
2138     {
2139     pcre_uchar first_char = first_byte;
2140     if (first_byte_caseless)
2141       while (start_match < end_subject)
2142         {
2143         int sm = *start_match;
2144         if (sm > 127)
2145           break;
2146         if (match_block.lcc[sm] == first_char)
2147           break;
2148         start_match++;
2149         }
2150     else
2151       while (start_match < end_subject && *start_match != first_char)
2152         start_match++;
2153     }
2154
2155   /* Or to just after \n for a multiline match if possible */
2156
2157   else if (startline)
2158     {
2159     if (start_match > match_block.start_subject + start_offset)
2160       {
2161       while (start_match < end_subject && !isNewline(start_match[-1]))
2162         start_match++;
2163       }
2164     }
2165
2166   /* Restore fudged end_subject */
2167
2168   end_subject = save_end_subject;
2169
2170 #ifdef DEBUG  /* Sigh. Some compilers never learn. */
2171   printf(">>>> Match against: ");
2172   pchars(start_match, end_subject - start_match, true, &match_block);
2173   printf("\n");
2174 #endif
2175
2176   /* If req_byte is set, we know that that character must appear in the subject
2177   for the match to succeed. If the first character is set, req_byte must be
2178   later in the subject; otherwise the test starts at the match point. This
2179   optimization can save a huge amount of backtracking in patterns with nested
2180   unlimited repeats that aren't going to match. Writing separate code for
2181   cased/caseless versions makes it go faster, as does using an autoincrement
2182   and backing off on a match.
2183
2184   HOWEVER: when the subject string is very, very long, searching to its end can
2185   take a long time, and give bad performance on quite ordinary patterns. This
2186   showed up when somebody was matching /^C/ on a 32-megabyte string... so we
2187   don't do this when the string is sufficiently long.
2188
2189   ALSO: this processing is disabled when partial matching is requested.
2190   */
2191
2192   if (req_byte >= 0 &&
2193       end_subject - start_match < REQ_BYTE_MAX)
2194     {
2195     register USPTR p = start_match + ((first_byte >= 0)? 1 : 0);
2196
2197     /* We don't need to repeat the search if we haven't yet reached the
2198     place we found it at last time. */
2199
2200     if (p > req_byte_ptr)
2201       {
2202       if (req_byte_caseless)
2203         {
2204         while (p < end_subject)
2205           {
2206           register int pp = *p++;
2207           if (pp == req_byte || pp == req_byte2) { p--; break; }
2208           }
2209         }
2210       else
2211         {
2212         while (p < end_subject)
2213           {
2214           if (*p++ == req_byte) { p--; break; }
2215           }
2216         }
2217
2218       /* If we can't find the required character, break the matching loop */
2219
2220       if (p >= end_subject) break;
2221
2222       /* If we have found the required character, save the point where we
2223       found it, so that we don't search again next time round the loop if
2224       the start hasn't passed this character yet. */
2225
2226       req_byte_ptr = p;
2227       }
2228     }
2229
2230   /* When a match occurs, substrings will be set for all internal extractions;
2231   we just need to set up the whole thing as substring 0 before returning. If
2232   there were too many extractions, set the return code to zero. In the case
2233   where we had to get some local store to hold offsets for backreferences, copy
2234   those back references that we can. In this case there need not be overflow
2235   if certain parts of the pattern were not used. */
2236
2237   match_block.match_call_count = 0;
2238
2239   rc = match(start_match, start_code, 2, &match_block);
2240
2241   /* When the result is no match, if the subject's first character was a
2242   newline and the PCRE_FIRSTLINE option is set, break (which will return
2243   PCRE_ERROR_NOMATCH). The option requests that a match occur before the first
2244   newline in the subject. Otherwise, advance the pointer to the next character
2245   and continue - but the continuation will actually happen only when the
2246   pattern is not anchored. */
2247
2248   if (rc == MATCH_NOMATCH)
2249     {
2250     start_match++;
2251       while(start_match < end_subject && ISMIDCHAR(*start_match))
2252         start_match++;
2253     continue;
2254     }
2255
2256   if (rc != MATCH_MATCH)
2257     {
2258     DPRINTF((">>>> error: returning %d\n", rc));
2259     return rc;
2260     }
2261
2262   /* We have a match! Copy the offset information from temporary store if
2263   necessary */
2264
2265   if (using_temporary_offsets)
2266     {
2267     if (offsetcount >= 4)
2268       {
2269       memcpy(offsets + 2, match_block.offset_vector + 2,
2270         (offsetcount - 2) * sizeof(int));
2271       DPRINTF(("Copied offsets from temporary memory\n"));
2272       }
2273     if (match_block.end_offset_top > offsetcount)
2274       match_block.offset_overflow = true;
2275
2276     DPRINTF(("Freeing temporary memory\n"));
2277     delete [] match_block.offset_vector;
2278     }
2279
2280   rc = match_block.offset_overflow? 0 : match_block.end_offset_top/2;
2281
2282   if (offsetcount < 2) rc = 0; else
2283     {
2284     offsets[0] = start_match - match_block.start_subject;
2285     offsets[1] = match_block.end_match_ptr - match_block.start_subject;
2286     }
2287
2288   DPRINTF((">>>> returning %d\n", rc));
2289   return rc;
2290   }
2291
2292 /* This "while" is the end of the "do" above */
2293
2294 while (start_match <= end_subject);
2295
2296 if (using_temporary_offsets)
2297   {
2298   DPRINTF(("Freeing temporary memory\n"));
2299   delete [] match_block.offset_vector;
2300   }
2301
2302   DPRINTF((">>>> returning PCRE_ERROR_NOMATCH\n"));
2303   return JSRegExpErrorNoMatch;
2304 }