2007-11-14 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) RRETURN_ERROR(JSRegExpErrorMatchLimit);
399 if (rdepth >= MATCH_LIMIT_RECURSION) RRETURN_ERROR(JSRegExpErrorRecursionLimit);
400
401 /* At the start of a bracketed group, add the current subject pointer to the
402 stack of such pointers, to be re-instated at the end of the group when we hit
403 the closing ket. When match() is called in other circumstances, we don't add to
404 this stack. */
405
406 if (is_group_start)
407   {
408   frame->newptrb.epb_prev = frame->eptrb;
409   frame->newptrb.epb_saved_eptr = frame->eptr;
410   frame->eptrb = &frame->newptrb;
411   }
412
413 /* Now start processing the operations. */
414
415 #ifndef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
416 for (;;)
417 #endif
418   {
419
420 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
421   #define BEGIN_OPCODE(opcode) LABEL_OP_##opcode
422   #define NEXT_OPCODE goto *opcode_jump_table[*frame->ecode]
423 #else
424   #define BEGIN_OPCODE(opcode) case OP_##opcode
425   #define NEXT_OPCODE continue
426 #endif
427
428 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
429   NEXT_OPCODE;
430 #else
431   switch (*frame->ecode)
432 #endif
433     {
434     /* Non-capturing bracket: optimized */
435
436     BEGIN_OPCODE(BRA):
437     NON_CAPTURING_BRACKET:
438     DPRINTF(("start bracket 0\n"));
439     do
440       {
441       RMATCH(2, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
442       if (is_match) RRETURN;
443       frame->ecode += GET(frame->ecode, 1);
444       }
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       {
472       RMATCH(6, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
473       if (is_match) break;
474       frame->ecode += GET(frame->ecode, 1);
475       }
476     while (*frame->ecode == OP_ALT);
477     if (*frame->ecode == OP_KET) RRETURN_NO_MATCH;
478
479     /* Continue from after the assertion, updating the offsets high water
480     mark, since extracts may have been taken during the assertion. */
481
482     do frame->ecode += GET(frame->ecode,1); while (*frame->ecode == OP_ALT);
483     frame->ecode += 1 + LINK_SIZE;
484     frame->offset_top = md->end_offset_top;
485     NEXT_OPCODE;
486
487     /* Negative assertion: all branches must fail to match */
488
489     BEGIN_OPCODE(ASSERT_NOT):
490     do
491       {
492       RMATCH(7, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
493       if (is_match) RRETURN_NO_MATCH;
494       frame->ecode += GET(frame->ecode,1);
495       }
496     while (*frame->ecode == OP_ALT);
497
498     frame->ecode += 1 + LINK_SIZE;
499     NEXT_OPCODE;
500
501     /* "Once" brackets are like assertion brackets except that after a match,
502     the point in the subject string is not moved back. Thus there can never be
503     a move back into the brackets. Friedl calls these "atomic" subpatterns.
504     Check the alternative branches in turn - the matching won't pass the KET
505     for this kind of subpattern. If any one branch matches, we carry on as at
506     the end of a normal bracket, leaving the subject pointer. */
507
508     BEGIN_OPCODE(ONCE):
509       frame->prev = frame->ecode;
510       frame->saved_eptr = frame->eptr;
511
512       do
513         {
514         RMATCH(9, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
515         if (is_match) break;
516         frame->ecode += GET(frame->ecode,1);
517         }
518       while (*frame->ecode == OP_ALT);
519
520       /* If hit the end of the group (which could be repeated), fail */
521
522       if (*frame->ecode != OP_ONCE && *frame->ecode != OP_ALT) RRETURN;
523
524       /* Continue as from after the assertion, updating the offsets high water
525       mark, since extracts may have been taken. */
526
527       do frame->ecode += GET(frame->ecode,1); while (*frame->ecode == OP_ALT);
528
529       frame->offset_top = md->end_offset_top;
530       frame->eptr = md->end_match_ptr;
531
532       /* For a non-repeating ket, just continue at this level. This also
533       happens for a repeating ket if no characters were matched in the group.
534       This is the forcible breaking of infinite loops as implemented in Perl
535       5.005. If there is an options reset, it will get obeyed in the normal
536       course of events. */
537
538       if (*frame->ecode == OP_KET || frame->eptr == frame->saved_eptr)
539         {
540         frame->ecode += 1+LINK_SIZE;
541         NEXT_OPCODE;
542         }
543
544       /* The repeating kets try the rest of the pattern or restart from the
545       preceding bracket, in the appropriate order. We need to reset any options
546       that changed within the bracket before re-running it, so check the next
547       opcode. */
548
549       if (*frame->ecode == OP_KETRMIN)
550         {
551         RMATCH(10, frame->ecode + 1 + LINK_SIZE, frame->eptrb, 0);
552         if (is_match) RRETURN;
553         RMATCH(11, frame->prev, frame->eptrb, match_isgroup);
554         if (is_match) RRETURN;
555         }
556       else  /* OP_KETRMAX */
557         {
558         RMATCH(12, frame->prev, frame->eptrb, match_isgroup);
559         if (is_match) RRETURN;
560         RMATCH(13, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
561         if (is_match) RRETURN;
562         }
563     RRETURN;
564
565     /* An alternation is the end of a branch; scan along to find the end of the
566     bracketed group and go to there. */
567
568     BEGIN_OPCODE(ALT):
569     do frame->ecode += GET(frame->ecode,1); while (*frame->ecode == OP_ALT);
570     NEXT_OPCODE;
571
572     /* BRAZERO and BRAMINZERO occur just before a bracket group, indicating
573     that it may occur zero times. It may repeat infinitely, or not at all -
574     i.e. it could be ()* or ()? in the pattern. Brackets with fixed upper
575     repeat limits are compiled as a number of copies, with the optional ones
576     preceded by BRAZERO or BRAMINZERO. */
577
578     BEGIN_OPCODE(BRAZERO):
579       {
580       frame->next = frame->ecode+1;
581       RMATCH(14, frame->next, frame->eptrb, match_isgroup);
582       if (is_match) RRETURN;
583       do frame->next += GET(frame->next,1); while (*frame->next == OP_ALT);
584       frame->ecode = frame->next + 1+LINK_SIZE;
585       }
586     NEXT_OPCODE;
587
588     BEGIN_OPCODE(BRAMINZERO):
589       {
590       frame->next = frame->ecode+1;
591       do frame->next += GET(frame->next,1); while (*frame->next == OP_ALT);
592       RMATCH(15, frame->next + 1+LINK_SIZE, frame->eptrb, match_isgroup);
593       if (is_match) 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         {
615         md->end_match_ptr = frame->eptr;      /* For ONCE */
616         md->end_offset_top = frame->offset_top;
617         is_match = true;
618         RRETURN;
619         }
620
621       /* In all other cases except a conditional group we have to check the
622       group number back at the start and if necessary complete handling an
623       extraction by setting the offsets and bumping the high water mark. */
624
625         frame->number = *frame->prev - OP_BRA;
626
627         /* For extended extraction brackets (large number), we have to fish out
628         the number from a dummy opcode at the start. */
629
630         if (frame->number > EXTRACT_BASIC_MAX) 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           {
645           if (frame->offset >= md->offset_max) md->offset_overflow = true; else
646             {
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) frame->offset_top = frame->offset + 2;
651             }
652           }
653
654       /* For a non-repeating ket, just continue at this level. This also
655       happens for a repeating ket if no characters were matched in the group.
656       This is the forcible breaking of infinite loops as implemented in Perl
657       5.005. If there is an options reset, it will get obeyed in the normal
658       course of events. */
659
660       if (*frame->ecode == OP_KET || frame->eptr == frame->saved_eptr)
661         {
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         {
671         RMATCH(16, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
672         if (is_match) RRETURN;
673         RMATCH(17, frame->prev, frame->eptrb, match_isgroup);
674         if (is_match) RRETURN;
675         }
676       else  /* OP_KETRMAX */
677         {
678         RMATCH(18, frame->prev, frame->eptrb, match_isgroup);
679         if (is_match) RRETURN;
680         RMATCH(19, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
681         if (is_match) RRETURN;
682         }
683     RRETURN;
684
685     /* Start of subject, or after internal newline if multiline. */
686
687     BEGIN_OPCODE(CIRC):
688     if (frame->eptr != md->start_subject && (!md->multiline || !isNewline(frame->eptr[-1])))
689       RRETURN_NO_MATCH;
690     frame->ecode++;
691     NEXT_OPCODE;
692
693     /* End of subject, or before internal newline if multiline. */
694
695     BEGIN_OPCODE(DOLL):
696     if (frame->eptr < md->end_subject && (!md->multiline || !isNewline(*frame->eptr)))
697       RRETURN_NO_MATCH;
698     frame->ecode++;
699     NEXT_OPCODE;
700
701     /* Word boundary assertions */
702
703     BEGIN_OPCODE(NOT_WORD_BOUNDARY):
704     BEGIN_OPCODE(WORD_BOUNDARY):
705       /* Find out if the previous and current characters are "word" characters.
706       It takes a bit more work in UTF-8 mode. Characters > 128 are assumed to
707       be "non-word" characters. */
708
709         if (frame->eptr == md->start_subject) prev_is_word = false; else
710           {
711           const pcre_uchar *lastptr = frame->eptr - 1;
712           while(ISMIDCHAR(*lastptr)) lastptr--;
713           GETCHAR(c, lastptr);
714           prev_is_word = c < 128 && (md->ctypes[c] & ctype_word) != 0;
715           }
716         if (frame->eptr >= md->end_subject) cur_is_word = false; else
717           {
718           GETCHAR(c, frame->eptr);
719           cur_is_word = c < 128 && (md->ctypes[c] & ctype_word) != 0;
720           }
721
722       /* Now see if the situation is what we want */
723
724       if ((*frame->ecode++ == OP_WORD_BOUNDARY)?
725            cur_is_word == prev_is_word : cur_is_word != prev_is_word)
726         RRETURN_NO_MATCH;
727     NEXT_OPCODE;
728
729     /* Match a single character type; inline for speed */
730
731     BEGIN_OPCODE(ANY):
732     if (frame->eptr < md->end_subject && isNewline(*frame->eptr))
733       RRETURN_NO_MATCH;
734     if (frame->eptr++ >= md->end_subject) RRETURN_NO_MATCH;
735       while (frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr)) frame->eptr++;
736     frame->ecode++;
737     NEXT_OPCODE;
738
739     BEGIN_OPCODE(NOT_DIGIT):
740     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
741     GETCHARINCTEST(c, frame->eptr);
742     if (isASCIIDigit(c))
743       RRETURN_NO_MATCH;
744     frame->ecode++;
745     NEXT_OPCODE;
746
747     BEGIN_OPCODE(DIGIT):
748     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
749     GETCHARINCTEST(c, frame->eptr);
750     if (!isASCIIDigit(c))
751       RRETURN_NO_MATCH;
752     frame->ecode++;
753     NEXT_OPCODE;
754
755     BEGIN_OPCODE(NOT_WHITESPACE):
756     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
757     GETCHARINCTEST(c, frame->eptr);
758     if (c < 128 && (md->ctypes[c] & ctype_space) != 0)
759       RRETURN_NO_MATCH;
760     frame->ecode++;
761     NEXT_OPCODE;
762
763     BEGIN_OPCODE(WHITESPACE):
764     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
765     GETCHARINCTEST(c, frame->eptr);
766     if (c >= 128 || (md->ctypes[c] & ctype_space) == 0)
767       RRETURN_NO_MATCH;
768     frame->ecode++;
769     NEXT_OPCODE;
770
771     BEGIN_OPCODE(NOT_WORDCHAR):
772     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
773     GETCHARINCTEST(c, frame->eptr);
774     if (c < 128 && (md->ctypes[c] & ctype_word) != 0)
775       RRETURN_NO_MATCH;
776     frame->ecode++;
777     NEXT_OPCODE;
778
779     BEGIN_OPCODE(WORDCHAR):
780     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
781     GETCHARINCTEST(c, frame->eptr);
782     if (c >= 128 || (md->ctypes[c] & ctype_word) == 0)
783       RRETURN_NO_MATCH;
784     frame->ecode++;
785     NEXT_OPCODE;
786
787     /* Match a back reference, possibly repeatedly. Look past the end of the
788     item to see if there is repeat information following. The code is similar
789     to that for character classes, but repeated for efficiency. Then obey
790     similar code to character type repeats - written out again for speed.
791     However, if the referenced string is the empty string, always treat
792     it as matched, any number of times (otherwise there could be infinite
793     loops). */
794
795     BEGIN_OPCODE(REF):
796       frame->offset = GET2(frame->ecode, 1) << 1;               /* Doubled ref number */
797       frame->ecode += 3;                                 /* Advance past item */
798
799       /* If the reference is unset, set the length to be longer than the amount
800       of subject left; this ensures that every attempt at a match fails. We
801       can't just fail here, because of the possibility of quantifiers with zero
802       minima. */
803
804       frame->length = (frame->offset >= frame->offset_top || md->offset_vector[frame->offset] < 0)?
805         0 :
806         md->offset_vector[frame->offset+1] - md->offset_vector[frame->offset];
807
808       /* Set up for repetition, or handle the non-repeated case */
809
810       switch (*frame->ecode)
811         {
812         case OP_CRSTAR:
813         case OP_CRMINSTAR:
814         case OP_CRPLUS:
815         case OP_CRMINPLUS:
816         case OP_CRQUERY:
817         case OP_CRMINQUERY:
818         c = *frame->ecode++ - OP_CRSTAR;
819         minimize = (c & 1) != 0;
820         min = rep_min[c];                 /* Pick up values from tables; */
821         frame->max = rep_max[c];                 /* zero for max => infinity */
822         if (frame->max == 0) frame->max = INT_MAX;
823         break;
824
825         case OP_CRRANGE:
826         case OP_CRMINRANGE:
827         minimize = (*frame->ecode == OP_CRMINRANGE);
828         min = GET2(frame->ecode, 1);
829         frame->max = GET2(frame->ecode, 3);
830         if (frame->max == 0) frame->max = INT_MAX;
831         frame->ecode += 5;
832         break;
833
834         default:               /* No repeat follows */
835         if (!match_ref(frame->offset, frame->eptr, frame->length, md)) RRETURN_NO_MATCH;
836         frame->eptr += frame->length;
837         NEXT_OPCODE;
838         }
839
840       /* If the length of the reference is zero, just continue with the
841       main loop. */
842
843       if (frame->length == 0)
844         NEXT_OPCODE;
845
846       /* First, ensure the minimum number of matches are present. */
847
848       for (i = 1; i <= min; i++)
849         {
850         if (!match_ref(frame->offset, frame->eptr, frame->length, md)) RRETURN_NO_MATCH;
851         frame->eptr += frame->length;
852         }
853
854       /* If min = max, continue at the same level without recursion.
855       They are not both allowed to be zero. */
856
857       if (min == frame->max)
858         NEXT_OPCODE;
859
860       /* If minimizing, keep trying and advancing the pointer */
861
862       if (minimize)
863         {
864         for (frame->fi = min;; frame->fi++)
865           {
866           RMATCH(20, frame->ecode, frame->eptrb, 0);
867           if (is_match) RRETURN;
868           if (frame->fi >= frame->max || !match_ref(frame->offset, frame->eptr, frame->length, md))
869             RRETURN;
870           frame->eptr += frame->length;
871           }
872         /* Control never gets here */
873         }
874
875       /* If maximizing, find the longest string and work backwards */
876
877       else
878         {
879         frame->pp = frame->eptr;
880         for (i = min; i < frame->max; i++)
881           {
882           if (!match_ref(frame->offset, frame->eptr, frame->length, md)) break;
883           frame->eptr += frame->length;
884           }
885         while (frame->eptr >= frame->pp)
886           {
887           RMATCH(21, frame->ecode, frame->eptrb, 0);
888           if (is_match) RRETURN;
889           frame->eptr -= frame->length;
890           }
891         RRETURN_NO_MATCH;
892         }
893     /* Control never gets here */
894
895     /* Match a bit-mapped character class, possibly repeatedly. This op code is
896     used when all the characters in the class have values in the range 0-255,
897     and either the matching is caseful, or the characters are in the range
898     0-127 when UTF-8 processing is enabled. The only difference between
899     OP_CLASS and OP_NCLASS occurs when a data character outside the range is
900     encountered.
901
902     First, look past the end of the item to see if there is repeat information
903     following. Then obey similar code to character type repeats - written out
904     again for speed. */
905
906     BEGIN_OPCODE(NCLASS):
907     BEGIN_OPCODE(CLASS):
908       frame->data = frame->ecode + 1;                /* Save for matching */
909       frame->ecode += 33;                     /* Advance past the item */
910
911       switch (*frame->ecode)
912         {
913         case OP_CRSTAR:
914         case OP_CRMINSTAR:
915         case OP_CRPLUS:
916         case OP_CRMINPLUS:
917         case OP_CRQUERY:
918         case OP_CRMINQUERY:
919         c = *frame->ecode++ - OP_CRSTAR;
920         minimize = (c & 1) != 0;
921         min = rep_min[c];                 /* Pick up values from tables; */
922         frame->max = rep_max[c];                 /* zero for max => infinity */
923         if (frame->max == 0) frame->max = INT_MAX;
924         break;
925
926         case OP_CRRANGE:
927         case OP_CRMINRANGE:
928         minimize = (*frame->ecode == OP_CRMINRANGE);
929         min = GET2(frame->ecode, 1);
930         frame->max = GET2(frame->ecode, 3);
931         if (frame->max == 0) frame->max = INT_MAX;
932         frame->ecode += 5;
933         break;
934
935         default:               /* No repeat follows */
936         min = frame->max = 1;
937         break;
938         }
939
940       /* First, ensure the minimum number of matches are present. */
941
942         {
943         for (i = 1; i <= min; i++)
944           {
945           if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
946           GETCHARINC(c, frame->eptr);
947           if (c > 255)
948             {
949             if (frame->data[-1] == OP_CLASS) RRETURN_NO_MATCH;
950             }
951           else
952             {
953             if ((frame->data[c/8] & (1 << (c&7))) == 0) RRETURN_NO_MATCH;
954             }
955           }
956         }
957
958       /* If max == min we can continue with the main loop without the
959       need to recurse. */
960
961       if (min == frame->max)
962         NEXT_OPCODE;      
963
964       /* If minimizing, keep testing the rest of the expression and advancing
965       the pointer while it matches the class. */
966       if (minimize)
967         {
968           {
969           for (frame->fi = min;; frame->fi++)
970             {
971             RMATCH(22, frame->ecode, frame->eptrb, 0);
972             if (is_match) RRETURN;
973             if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN;
974             GETCHARINC(c, frame->eptr);
975             if (c > 255)
976               {
977               if (frame->data[-1] == OP_CLASS) RRETURN;
978               }
979             else
980               {
981               if ((frame->data[c/8] & (1 << (c&7))) == 0) RRETURN;
982               }
983             }
984           }
985         /* Control never gets here */
986         }
987       /* If maximizing, find the longest possible run, then work backwards. */
988       else
989         {
990         frame->pp = frame->eptr;
991
992           for (i = min; i < frame->max; i++)
993             {
994             int len = 1;
995             if (frame->eptr >= md->end_subject) break;
996             GETCHARLEN(c, frame->eptr, len);
997             if (c > 255)
998               {
999               if (frame->data[-1] == OP_CLASS) break;
1000               }
1001             else
1002               {
1003               if ((frame->data[c/8] & (1 << (c&7))) == 0) break;
1004               }
1005             frame->eptr += len;
1006             }
1007           for (;;)
1008             {
1009             RMATCH(24, frame->ecode, frame->eptrb, 0);
1010             if (is_match) RRETURN;
1011             if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
1012             BACKCHAR(frame->eptr);
1013             }
1014
1015         RRETURN;
1016         }
1017     /* Control never gets here */
1018
1019     /* Match an extended character class. This opcode is encountered only
1020     in UTF-8 mode, because that's the only time it is compiled. */
1021
1022     BEGIN_OPCODE(XCLASS):
1023       frame->data = frame->ecode + 1 + LINK_SIZE;                /* Save for matching */
1024       frame->ecode += GET(frame->ecode, 1);                      /* Advance past the item */
1025
1026       switch (*frame->ecode)
1027         {
1028         case OP_CRSTAR:
1029         case OP_CRMINSTAR:
1030         case OP_CRPLUS:
1031         case OP_CRMINPLUS:
1032         case OP_CRQUERY:
1033         case OP_CRMINQUERY:
1034         c = *frame->ecode++ - OP_CRSTAR;
1035         minimize = (c & 1) != 0;
1036         min = rep_min[c];                 /* Pick up values from tables; */
1037         frame->max = rep_max[c];                 /* zero for max => infinity */
1038         if (frame->max == 0) frame->max = INT_MAX;
1039         break;
1040
1041         case OP_CRRANGE:
1042         case OP_CRMINRANGE:
1043         minimize = (*frame->ecode == OP_CRMINRANGE);
1044         min = GET2(frame->ecode, 1);
1045         frame->max = GET2(frame->ecode, 3);
1046         if (frame->max == 0) frame->max = INT_MAX;
1047         frame->ecode += 5;
1048         break;
1049
1050         default:               /* No repeat follows */
1051         min = frame->max = 1;
1052         }
1053
1054       /* First, ensure the minimum number of matches are present. */
1055
1056       for (i = 1; i <= min; i++)
1057         {
1058         if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
1059         GETCHARINC(c, frame->eptr);
1060         if (!_pcre_xclass(c, frame->data)) RRETURN_NO_MATCH;
1061         }
1062
1063       /* If max == min we can continue with the main loop without the
1064       need to recurse. */
1065
1066       if (min == frame->max)
1067         NEXT_OPCODE;
1068
1069       /* If minimizing, keep testing the rest of the expression and advancing
1070       the pointer while it matches the class. */
1071
1072       if (minimize)
1073         {
1074         for (frame->fi = min;; frame->fi++)
1075           {
1076           RMATCH(26, frame->ecode, frame->eptrb, 0);
1077           if (is_match) RRETURN;
1078           if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN;
1079           GETCHARINC(c, frame->eptr);
1080           if (!_pcre_xclass(c, frame->data)) RRETURN;
1081           }
1082         /* Control never gets here */
1083         }
1084
1085       /* If maximizing, find the longest possible run, then work backwards. */
1086
1087       else
1088         {
1089         frame->pp = frame->eptr;
1090         for (i = min; i < frame->max; i++)
1091           {
1092           int len = 1;
1093           if (frame->eptr >= md->end_subject) break;
1094           GETCHARLEN(c, frame->eptr, len);
1095           if (!_pcre_xclass(c, frame->data)) break;
1096           frame->eptr += len;
1097           }
1098         for(;;)
1099           {
1100           RMATCH(27, frame->ecode, frame->eptrb, 0);
1101           if (is_match) RRETURN;
1102           if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
1103           BACKCHAR(frame->eptr)
1104           }
1105         RRETURN;
1106         }
1107
1108     /* Control never gets here */
1109
1110     /* Match a single character, casefully */
1111
1112     BEGIN_OPCODE(CHAR):
1113       frame->length = 1;
1114       frame->ecode++;
1115       GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
1116       {
1117         int dc;
1118         frame->ecode += frame->length;
1119         switch (md->end_subject - frame->eptr)
1120         {
1121           case 0:
1122             RRETURN_NO_MATCH;
1123           case 1:
1124             dc = *frame->eptr++;
1125             if (IS_LEADING_SURROGATE(dc))
1126               RRETURN_NO_MATCH;
1127             break;
1128           default:
1129             GETCHARINC(dc, frame->eptr);
1130         }
1131         if (frame->fc != dc) RRETURN_NO_MATCH;
1132       }
1133     NEXT_OPCODE;
1134
1135     /* Match a single character, caselessly */
1136
1137     BEGIN_OPCODE(CHARNC):
1138       frame->length = 1;
1139       frame->ecode++;
1140       GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
1141
1142       if (md->end_subject - frame->eptr == 0) RRETURN_NO_MATCH;
1143
1144         {
1145         int dc;
1146         if (md->end_subject - frame->eptr == 1) {
1147           dc = *frame->eptr++;
1148           if (IS_LEADING_SURROGATE(dc))
1149             RRETURN_NO_MATCH;
1150         } else
1151         GETCHARINC(dc, frame->eptr);
1152         frame->ecode += frame->length;
1153
1154         /* If we have Unicode property support, we can use it to test the other
1155         case of the character, if there is one. */
1156
1157         if (frame->fc != dc)
1158           {
1159           if (dc != _pcre_ucp_othercase(frame->fc))
1160             RRETURN_NO_MATCH;
1161           }
1162         }
1163     NEXT_OPCODE;
1164
1165     /* Match a single ASCII character. */
1166
1167     BEGIN_OPCODE(ASCII_CHAR):
1168     if (md->end_subject == frame->eptr)
1169       RRETURN_NO_MATCH;
1170     if (*frame->eptr != frame->ecode[1])
1171       RRETURN_NO_MATCH;
1172     ++frame->eptr;
1173     frame->ecode += 2;
1174     NEXT_OPCODE;
1175
1176     /* Match one of two cases of an ASCII character. */
1177
1178     BEGIN_OPCODE(ASCII_LETTER_NC):
1179     if (md->end_subject == frame->eptr)
1180       RRETURN_NO_MATCH;
1181     if ((*frame->eptr | 0x20) != frame->ecode[1])
1182       RRETURN_NO_MATCH;
1183     ++frame->eptr;
1184     frame->ecode += 2;
1185     NEXT_OPCODE;
1186
1187     /* Match a single character repeatedly; different opcodes share code. */
1188
1189     BEGIN_OPCODE(EXACT):
1190     min = frame->max = GET2(frame->ecode, 1);
1191     minimize = false;
1192     frame->ecode += 3;
1193     goto REPEATCHAR;
1194
1195     BEGIN_OPCODE(UPTO):
1196     BEGIN_OPCODE(MINUPTO):
1197     min = 0;
1198     frame->max = GET2(frame->ecode, 1);
1199     minimize = *frame->ecode == OP_MINUPTO;
1200     frame->ecode += 3;
1201     goto REPEATCHAR;
1202
1203     BEGIN_OPCODE(STAR):
1204     BEGIN_OPCODE(MINSTAR):
1205     BEGIN_OPCODE(PLUS):
1206     BEGIN_OPCODE(MINPLUS):
1207     BEGIN_OPCODE(QUERY):
1208     BEGIN_OPCODE(MINQUERY):
1209     c = *frame->ecode++ - OP_STAR;
1210     minimize = (c & 1) != 0;
1211     min = rep_min[c];                 /* Pick up values from tables; */
1212     frame->max = rep_max[c];                 /* zero for max => infinity */
1213     if (frame->max == 0) frame->max = INT_MAX;
1214
1215     /* Common code for all repeated single-character matches. We can give
1216     up quickly if there are fewer than the minimum number of characters left in
1217     the subject. */
1218
1219     REPEATCHAR:
1220
1221       frame->length = 1;
1222       GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
1223       if (min * (frame->fc > 0xFFFF ? 2 : 1) > md->end_subject - frame->eptr) RRETURN_NO_MATCH;
1224       frame->ecode += frame->length;
1225
1226       if (frame->fc <= 0xFFFF)
1227         {
1228         int othercase = md->caseless ? _pcre_ucp_othercase(frame->fc) : -1;
1229
1230         for (i = 1; i <= min; i++)
1231           {
1232           if (*frame->eptr != frame->fc && *frame->eptr != othercase) RRETURN_NO_MATCH;
1233           ++frame->eptr;
1234           }
1235
1236         if (min == frame->max)
1237           NEXT_OPCODE;
1238
1239         if (minimize)
1240           {
1241           frame->repeat_othercase = othercase;
1242           for (frame->fi = min;; frame->fi++)
1243             {
1244             RMATCH(28, frame->ecode, frame->eptrb, 0);
1245             if (is_match) RRETURN;
1246             if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN;
1247             if (*frame->eptr != frame->fc && *frame->eptr != frame->repeat_othercase) RRETURN;
1248             ++frame->eptr;
1249             }
1250           /* Control never gets here */
1251           }
1252         else
1253           {
1254           frame->pp = frame->eptr;
1255           for (i = min; i < frame->max; i++)
1256             {
1257             if (frame->eptr >= md->end_subject) break;
1258             if (*frame->eptr != frame->fc && *frame->eptr != othercase) break;
1259             ++frame->eptr;
1260             }
1261           while (frame->eptr >= frame->pp)
1262            {
1263            RMATCH(29, frame->ecode, frame->eptrb, 0);
1264            if (is_match) RRETURN;
1265            --frame->eptr;
1266            }
1267           RRETURN_NO_MATCH;
1268           }
1269         /* Control never gets here */
1270         }
1271       else
1272         {
1273         /* No case on surrogate pairs, so no need to bother with "othercase". */
1274
1275         for (i = 1; i <= min; i++)
1276           {
1277           int nc;
1278           GETCHAR(nc, frame->eptr);
1279           if (nc != frame->fc) RRETURN_NO_MATCH;
1280           frame->eptr += 2;
1281           }
1282
1283         if (min == frame->max)
1284           NEXT_OPCODE;
1285
1286         if (minimize)
1287           {
1288           for (frame->fi = min;; frame->fi++)
1289             {
1290             int nc;
1291             RMATCH(30, frame->ecode, frame->eptrb, 0);
1292             if (is_match) RRETURN;
1293             if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN;
1294             GETCHAR(nc, frame->eptr);
1295             if (*frame->eptr != frame->fc) RRETURN;
1296             frame->eptr += 2;
1297             }
1298           /* Control never gets here */
1299           }
1300         else
1301           {
1302           frame->pp = frame->eptr;
1303           for (i = min; i < frame->max; i++)
1304             {
1305             int nc;
1306             if (frame->eptr > md->end_subject - 2) break;
1307             GETCHAR(nc, frame->eptr);
1308             if (*frame->eptr != frame->fc) break;
1309             frame->eptr += 2;
1310             }
1311           while (frame->eptr >= frame->pp)
1312            {
1313            RMATCH(31, frame->ecode, frame->eptrb, 0);
1314            if (is_match) RRETURN;
1315            frame->eptr -= 2;
1316            }
1317           RRETURN_NO_MATCH;
1318           }
1319           /* Control never gets here */
1320         }
1321     /* Control never gets here */
1322
1323     /* Match a negated single one-byte character. The character we are
1324     checking can be multibyte. */
1325
1326     BEGIN_OPCODE(NOT):
1327     if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
1328     frame->ecode++;
1329     GETCHARINCTEST(c, frame->eptr);
1330     if (md->caseless)
1331       {
1332       if (c < 128)
1333         c = md->lcc[c];
1334       if (md->lcc[*frame->ecode++] == c) RRETURN_NO_MATCH;
1335       }
1336     else
1337       {
1338       if (*frame->ecode++ == c) RRETURN_NO_MATCH;
1339       }
1340     NEXT_OPCODE;
1341
1342     /* Match a negated single one-byte character repeatedly. This is almost a
1343     repeat of the code for a repeated single character, but I haven't found a
1344     nice way of commoning these up that doesn't require a test of the
1345     positive/negative option for each character match. Maybe that wouldn't add
1346     very much to the time taken, but character matching *is* what this is all
1347     about... */
1348
1349     BEGIN_OPCODE(NOTEXACT):
1350     min = frame->max = GET2(frame->ecode, 1);
1351     minimize = false;
1352     frame->ecode += 3;
1353     goto REPEATNOTCHAR;
1354
1355     BEGIN_OPCODE(NOTUPTO):
1356     BEGIN_OPCODE(NOTMINUPTO):
1357     min = 0;
1358     frame->max = GET2(frame->ecode, 1);
1359     minimize = *frame->ecode == OP_NOTMINUPTO;
1360     frame->ecode += 3;
1361     goto REPEATNOTCHAR;
1362
1363     BEGIN_OPCODE(NOTSTAR):
1364     BEGIN_OPCODE(NOTMINSTAR):
1365     BEGIN_OPCODE(NOTPLUS):
1366     BEGIN_OPCODE(NOTMINPLUS):
1367     BEGIN_OPCODE(NOTQUERY):
1368     BEGIN_OPCODE(NOTMINQUERY):
1369     c = *frame->ecode++ - OP_NOTSTAR;
1370     minimize = (c & 1) != 0;
1371     min = rep_min[c];                 /* Pick up values from tables; */
1372     frame->max = rep_max[c];                 /* zero for max => infinity */
1373     if (frame->max == 0) frame->max = INT_MAX;
1374
1375     /* Common code for all repeated single-byte matches. We can give up quickly
1376     if there are fewer than the minimum number of bytes left in the
1377     subject. */
1378
1379     REPEATNOTCHAR:
1380     if (min > md->end_subject - frame->eptr) RRETURN_NO_MATCH;
1381     frame->fc = *frame->ecode++;
1382
1383     /* The code is duplicated for the caseless and caseful cases, for speed,
1384     since matching characters is likely to be quite common. First, ensure the
1385     minimum number of matches are present. If min = max, continue at the same
1386     level without recursing. Otherwise, if minimizing, keep trying the rest of
1387     the expression and advancing one matching character if failing, up to the
1388     maximum. Alternatively, if maximizing, find the maximum number of
1389     characters and work backwards. */
1390
1391     DPRINTF(("negative matching %c{%d,%d}\n", frame->fc, min, frame->max));
1392
1393     if (md->caseless)
1394       {
1395       if (frame->fc < 128)
1396         frame->fc = md->lcc[frame->fc];
1397
1398         {
1399         register int d;
1400         for (i = 1; i <= min; i++)
1401           {
1402           GETCHARINC(d, frame->eptr);
1403           if (d < 128) d = md->lcc[d];
1404           if (frame->fc == d) RRETURN_NO_MATCH;
1405           }
1406         }
1407
1408       if (min == frame->max)
1409         NEXT_OPCODE;      
1410
1411       if (minimize)
1412         {
1413           {
1414           register int d;
1415           for (frame->fi = min;; frame->fi++)
1416             {
1417             RMATCH(38, frame->ecode, frame->eptrb, 0);
1418             if (is_match) RRETURN;
1419             GETCHARINC(d, frame->eptr);
1420             if (d < 128) d = md->lcc[d];
1421             if (frame->fi >= frame->max || frame->eptr >= md->end_subject || frame->fc == d)
1422               RRETURN;
1423             }
1424           }
1425         /* Control never gets here */
1426         }
1427
1428       /* Maximize case */
1429
1430       else
1431         {
1432         frame->pp = frame->eptr;
1433
1434           {
1435           register int d;
1436           for (i = min; i < frame->max; i++)
1437             {
1438             int len = 1;
1439             if (frame->eptr >= md->end_subject) break;
1440             GETCHARLEN(d, frame->eptr, len);
1441             if (d < 128) d = md->lcc[d];
1442             if (frame->fc == d) break;
1443             frame->eptr += len;
1444             }
1445           for(;;)
1446             {
1447             RMATCH(40, frame->ecode, frame->eptrb, 0);
1448             if (is_match) RRETURN;
1449             if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
1450             BACKCHAR(frame->eptr);
1451             }
1452           }
1453
1454         RRETURN;
1455         }
1456       /* Control never gets here */
1457       }
1458
1459     /* Caseful comparisons */
1460
1461     else
1462       {
1463         {
1464         register int d;
1465         for (i = 1; i <= min; i++)
1466           {
1467           GETCHARINC(d, frame->eptr);
1468           if (frame->fc == d) RRETURN_NO_MATCH;
1469           }
1470         }
1471
1472       if (min == frame->max)
1473         NEXT_OPCODE;
1474
1475       if (minimize)
1476         {
1477           {
1478           register int d;
1479           for (frame->fi = min;; frame->fi++)
1480             {
1481             RMATCH(42, frame->ecode, frame->eptrb, 0);
1482             if (is_match) RRETURN;
1483             GETCHARINC(d, frame->eptr);
1484             if (frame->fi >= frame->max || frame->eptr >= md->end_subject || frame->fc == d)
1485               RRETURN;
1486             }
1487           }
1488         /* Control never gets here */
1489         }
1490
1491       /* Maximize case */
1492
1493       else
1494         {
1495         frame->pp = frame->eptr;
1496
1497           {
1498           register int d;
1499           for (i = min; i < frame->max; i++)
1500             {
1501             int len = 1;
1502             if (frame->eptr >= md->end_subject) break;
1503             GETCHARLEN(d, frame->eptr, len);
1504             if (frame->fc == d) break;
1505             frame->eptr += len;
1506             }
1507           for(;;)
1508             {
1509             RMATCH(44, frame->ecode, frame->eptrb, 0);
1510             if (is_match) RRETURN;
1511             if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
1512             BACKCHAR(frame->eptr);
1513             }
1514           }
1515
1516         RRETURN;
1517         }
1518       }
1519     /* Control never gets here */
1520
1521     /* Match a single character type repeatedly; several different opcodes
1522     share code. This is very similar to the code for single characters, but we
1523     repeat it in the interests of efficiency. */
1524
1525     BEGIN_OPCODE(TYPEEXACT):
1526     min = frame->max = GET2(frame->ecode, 1);
1527     minimize = true;
1528     frame->ecode += 3;
1529     goto REPEATTYPE;
1530
1531     BEGIN_OPCODE(TYPEUPTO):
1532     BEGIN_OPCODE(TYPEMINUPTO):
1533     min = 0;
1534     frame->max = GET2(frame->ecode, 1);
1535     minimize = *frame->ecode == OP_TYPEMINUPTO;
1536     frame->ecode += 3;
1537     goto REPEATTYPE;
1538
1539     BEGIN_OPCODE(TYPESTAR):
1540     BEGIN_OPCODE(TYPEMINSTAR):
1541     BEGIN_OPCODE(TYPEPLUS):
1542     BEGIN_OPCODE(TYPEMINPLUS):
1543     BEGIN_OPCODE(TYPEQUERY):
1544     BEGIN_OPCODE(TYPEMINQUERY):
1545     c = *frame->ecode++ - OP_TYPESTAR;
1546     minimize = (c & 1) != 0;
1547     min = rep_min[c];                 /* Pick up values from tables; */
1548     frame->max = rep_max[c];                 /* zero for max => infinity */
1549     if (frame->max == 0) frame->max = INT_MAX;
1550
1551     /* Common code for all repeated single character type matches. Note that
1552     in UTF-8 mode, '.' matches a character of any length, but for the other
1553     character types, the valid characters are all one-byte long. */
1554
1555     REPEATTYPE:
1556     frame->ctype = *frame->ecode++;      /* Code for the character type */
1557
1558     /* First, ensure the minimum number of matches are present. Use inline
1559     code for maximizing the speed, and do the type test once at the start
1560     (i.e. keep it out of the loop). Also we can test that there are at least
1561     the minimum number of bytes before we start. This isn't as effective in
1562     UTF-8 mode, but it does no harm. Separate the UTF-8 code completely as that
1563     is tidier. Also separate the UCP code, which can be the same for both UTF-8
1564     and single-bytes. */
1565
1566     if (min > md->end_subject - frame->eptr) RRETURN_NO_MATCH;
1567     if (min > 0)
1568       {
1569       switch(frame->ctype)
1570         {
1571         case OP_ANY:
1572         for (i = 1; i <= min; i++)
1573           {
1574           if (frame->eptr >= md->end_subject || isNewline(*frame->eptr))
1575             RRETURN_NO_MATCH;
1576           ++frame->eptr;
1577           while (frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr)) frame->eptr++;
1578           }
1579         break;
1580
1581         case OP_NOT_DIGIT:
1582         for (i = 1; i <= min; i++)
1583           {
1584           if (frame->eptr >= md->end_subject) RRETURN_NO_MATCH;
1585           GETCHARINC(c, frame->eptr);
1586           if (isASCIIDigit(c))
1587             RRETURN_NO_MATCH;
1588           }
1589         break;
1590
1591         case OP_DIGIT:
1592         for (i = 1; i <= min; i++)
1593           {
1594           if (frame->eptr >= md->end_subject || !isASCIIDigit(*frame->eptr++))
1595             RRETURN_NO_MATCH;
1596           /* No need to skip more bytes - we know it's a 1-byte character */
1597           }
1598         break;
1599
1600         case OP_NOT_WHITESPACE:
1601         for (i = 1; i <= min; i++)
1602           {
1603           if (frame->eptr >= md->end_subject ||
1604              (*frame->eptr < 128 && (md->ctypes[*frame->eptr] & ctype_space) != 0))
1605             RRETURN_NO_MATCH;
1606           while (++frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr));
1607           }
1608         break;
1609
1610         case OP_WHITESPACE:
1611         for (i = 1; i <= min; i++)
1612           {
1613           if (frame->eptr >= md->end_subject ||
1614              *frame->eptr >= 128 || (md->ctypes[*frame->eptr++] & ctype_space) == 0)
1615             RRETURN_NO_MATCH;
1616           /* No need to skip more bytes - we know it's a 1-byte character */
1617           }
1618         break;
1619
1620         case OP_NOT_WORDCHAR:
1621         for (i = 1; i <= min; i++)
1622           {
1623           if (frame->eptr >= md->end_subject ||
1624              (*frame->eptr < 128 && (md->ctypes[*frame->eptr] & ctype_word) != 0))
1625             RRETURN_NO_MATCH;
1626           while (++frame->eptr < md->end_subject && ISMIDCHAR(*frame->eptr));
1627           }
1628         break;
1629
1630         case OP_WORDCHAR:
1631         for (i = 1; i <= min; i++)
1632           {
1633           if (frame->eptr >= md->end_subject ||
1634              *frame->eptr >= 128 || (md->ctypes[*frame->eptr++] & ctype_word) == 0)
1635             RRETURN_NO_MATCH;
1636           /* No need to skip more bytes - we know it's a 1-byte character */
1637           }
1638         break;
1639
1640         default:
1641         ASSERT_NOT_REACHED();
1642         RRETURN_ERROR(JSRegExpErrorInternal);
1643         }  /* End switch(frame->ctype) */
1644       }
1645
1646     /* If min = max, continue at the same level without recursing */
1647
1648     if (min == frame->max)
1649       NEXT_OPCODE;    
1650
1651     /* If minimizing, we have to test the rest of the pattern before each
1652     subsequent match. */
1653
1654     if (minimize)
1655       {
1656         {
1657         for (frame->fi = min;; frame->fi++)
1658           {
1659           RMATCH(48, frame->ecode, frame->eptrb, 0);
1660           if (is_match) RRETURN;
1661           if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN;
1662
1663           GETCHARINC(c, frame->eptr);
1664           switch(frame->ctype)
1665             {
1666             case OP_ANY:
1667             if (isNewline(c)) RRETURN;
1668             break;
1669
1670             case OP_NOT_DIGIT:
1671             if (isASCIIDigit(c))
1672               RRETURN;
1673             break;
1674
1675             case OP_DIGIT:
1676             if (!isASCIIDigit(c))
1677               RRETURN;
1678             break;
1679
1680             case OP_NOT_WHITESPACE:
1681             if (c < 128 && (md->ctypes[c] & ctype_space) != 0)
1682               RRETURN;
1683             break;
1684
1685             case OP_WHITESPACE:
1686             if  (c >= 128 || (md->ctypes[c] & ctype_space) == 0)
1687               RRETURN;
1688             break;
1689
1690             case OP_NOT_WORDCHAR:
1691             if (c < 128 && (md->ctypes[c] & ctype_word) != 0)
1692               RRETURN;
1693             break;
1694
1695             case OP_WORDCHAR:
1696             if (c >= 128 || (md->ctypes[c] & ctype_word) == 0)
1697               RRETURN;
1698             break;
1699
1700             default:
1701             ASSERT_NOT_REACHED();
1702             RRETURN_ERROR(JSRegExpErrorInternal);
1703             }
1704           }
1705         }
1706       /* Control never gets here */
1707       }
1708
1709     /* If maximizing it is worth using inline code for speed, doing the type
1710     test once at the start (i.e. keep it out of the loop). */
1711
1712     else
1713       {
1714       frame->pp = frame->eptr;  /* Remember where we started */
1715
1716         switch(frame->ctype)
1717           {
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             {
1726               {
1727               for (i = min; i < frame->max; i++)
1728                 {
1729                 if (frame->eptr >= md->end_subject || isNewline(*frame->eptr)) break;
1730                 frame->eptr++;
1731                 while (frame->eptr < md->end_subject && (*frame->eptr & 0xc0) == 0x80) frame->eptr++;
1732                 }
1733               }
1734             }
1735
1736           /* Handle unlimited UTF-8 repeat */
1737
1738           else
1739             {
1740               {
1741               for (i = min; i < frame->max; i++)
1742                 {
1743                 if (frame->eptr >= md->end_subject || isNewline(*frame->eptr)) break;
1744                 frame->eptr++;
1745                 }
1746               break;
1747               }
1748             }
1749           break;
1750
1751           case OP_NOT_DIGIT:
1752           for (i = min; i < frame->max; i++)
1753             {
1754             int len = 1;
1755             if (frame->eptr >= md->end_subject) break;
1756             GETCHARLEN(c, frame->eptr, len);
1757             if (isASCIIDigit(c)) break;
1758             frame->eptr+= len;
1759             }
1760           break;
1761
1762           case OP_DIGIT:
1763           for (i = min; i < frame->max; i++)
1764             {
1765             int len = 1;
1766             if (frame->eptr >= md->end_subject) break;
1767             GETCHARLEN(c, frame->eptr, len);
1768             if (!isASCIIDigit(c)) break;
1769             frame->eptr+= len;
1770             }
1771           break;
1772
1773           case OP_NOT_WHITESPACE:
1774           for (i = min; i < frame->max; i++)
1775             {
1776             int len = 1;
1777             if (frame->eptr >= md->end_subject) break;
1778             GETCHARLEN(c, frame->eptr, len);
1779             if (c < 128 && (md->ctypes[c] & ctype_space) != 0) break;
1780             frame->eptr+= len;
1781             }
1782           break;
1783
1784           case OP_WHITESPACE:
1785           for (i = min; i < frame->max; i++)
1786             {
1787             int len = 1;
1788             if (frame->eptr >= md->end_subject) break;
1789             GETCHARLEN(c, frame->eptr, len);
1790             if (c >= 128 ||(md->ctypes[c] & ctype_space) == 0) break;
1791             frame->eptr+= len;
1792             }
1793           break;
1794
1795           case OP_NOT_WORDCHAR:
1796           for (i = min; i < frame->max; i++)
1797             {
1798             int len = 1;
1799             if (frame->eptr >= md->end_subject) break;
1800             GETCHARLEN(c, frame->eptr, len);
1801             if (c < 128 && (md->ctypes[c] & ctype_word) != 0) break;
1802             frame->eptr+= len;
1803             }
1804           break;
1805
1806           case OP_WORDCHAR:
1807           for (i = min; i < frame->max; i++)
1808             {
1809             int len = 1;
1810             if (frame->eptr >= md->end_subject) break;
1811             GETCHARLEN(c, frame->eptr, len);
1812             if (c >= 128 || (md->ctypes[c] & ctype_word) == 0) break;
1813             frame->eptr+= len;
1814             }
1815           break;
1816
1817           default:
1818           ASSERT_NOT_REACHED();
1819           RRETURN_ERROR(JSRegExpErrorInternal);
1820           }
1821
1822         /* frame->eptr is now past the end of the maximum run */
1823
1824         for(;;)
1825           {
1826           RMATCH(52, frame->ecode, frame->eptrb, 0);
1827           if (is_match) RRETURN;
1828           if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
1829           BACKCHAR(frame->eptr);
1830           }
1831
1832       /* Get here if we can't make it match with any permitted repetitions */
1833
1834       RRETURN;
1835       }
1836     /* Control never gets here */
1837
1838     BEGIN_OPCODE(CRMINPLUS):
1839     BEGIN_OPCODE(CRMINQUERY):
1840     BEGIN_OPCODE(CRMINRANGE):
1841     BEGIN_OPCODE(CRMINSTAR):
1842     BEGIN_OPCODE(CRPLUS):
1843     BEGIN_OPCODE(CRQUERY):
1844     BEGIN_OPCODE(CRRANGE):
1845     BEGIN_OPCODE(CRSTAR):
1846       ASSERT_NOT_REACHED();
1847       RRETURN_ERROR(JSRegExpErrorInternal);
1848
1849 #ifdef USE_COMPUTED_GOTO_FOR_MATCH_OPCODE_LOOP
1850     CAPTURING_BRACKET:
1851 #else
1852     default:
1853 #endif
1854       /* Opening capturing bracket. If there is space in the offset vector, save
1855       the current subject position in the working slot at the top of the vector. We
1856       mustn't change the current values of the data slot, because they may be set
1857       from a previous iteration of this group, and be referred to by a reference
1858       inside the group.
1859
1860       If the bracket fails to match, we need to restore this value and also the
1861       values of the final offsets, in case they were set by a previous iteration of
1862       the same bracket.
1863
1864       If there isn't enough space in the offset vector, treat this as if it were a
1865       non-capturing bracket. Don't worry about setting the flag for the error case
1866       here; that is handled in the code for KET. */
1867
1868       ASSERT(*frame->ecode > OP_BRA);
1869
1870         frame->number = *frame->ecode - OP_BRA;
1871
1872         /* For extended extraction brackets (large number), we have to fish out the
1873         number from a dummy opcode at the start. */
1874
1875         if (frame->number > EXTRACT_BASIC_MAX)
1876           frame->number = GET2(frame->ecode, 2+LINK_SIZE);
1877         frame->offset = frame->number << 1;
1878
1879 #ifdef DEBUG
1880         printf("start bracket %d subject=", frame->number);
1881         pchars(frame->eptr, 16, true, md);
1882         printf("\n");
1883 #endif
1884
1885         if (frame->offset < md->offset_max)
1886           {
1887           frame->save_offset1 = md->offset_vector[frame->offset];
1888           frame->save_offset2 = md->offset_vector[frame->offset + 1];
1889           frame->save_offset3 = md->offset_vector[md->offset_end - frame->number];
1890
1891           DPRINTF(("saving %d %d %d\n", frame->save_offset1, frame->save_offset2, frame->save_offset3));
1892           md->offset_vector[md->offset_end - frame->number] = frame->eptr - md->start_subject;
1893
1894           do
1895             {
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             }
1900           while (*frame->ecode == OP_ALT);
1901
1902           DPRINTF(("bracket %d failed\n", frame->number));
1903
1904           md->offset_vector[frame->offset] = frame->save_offset1;
1905           md->offset_vector[frame->offset + 1] = frame->save_offset2;
1906           md->offset_vector[md->offset_end - frame->number] = frame->save_offset3;
1907
1908           RRETURN;
1909           }
1910
1911         /* Insufficient room for saving captured contents */
1912
1913         goto NON_CAPTURING_BRACKET;
1914     }
1915
1916   /* Do not stick any code in here without much thought; it is assumed
1917   that "continue" in the code above comes out to here to repeat the main
1918   loop. */
1919
1920   } /* End of main loop */
1921
1922 /* Control never reaches here */
1923
1924 #ifndef USE_COMPUTED_GOTO_FOR_MATCH_RECURSION
1925
1926 RRETURN_SWITCH:
1927 switch (frame->where)
1928   {
1929   case 0: goto RETURN;
1930   case 1: goto RRETURN_1;
1931   case 2: goto RRETURN_2;
1932   case 6: goto RRETURN_6;
1933   case 7: goto RRETURN_7;
1934   case 9: goto RRETURN_9;
1935   case 10: goto RRETURN_10;
1936   case 11: goto RRETURN_11;
1937   case 12: goto RRETURN_12;
1938   case 13: goto RRETURN_13;
1939   case 14: goto RRETURN_14;
1940   case 15: goto RRETURN_15;
1941   case 16: goto RRETURN_16;
1942   case 17: goto RRETURN_17;
1943   case 18: goto RRETURN_18;
1944   case 19: goto RRETURN_19;
1945   case 20: goto RRETURN_20;
1946   case 21: goto RRETURN_21;
1947   case 22: goto RRETURN_22;
1948   case 24: goto RRETURN_24;
1949   case 26: goto RRETURN_26;
1950   case 27: goto RRETURN_27;
1951   case 28: goto RRETURN_28;
1952   case 29: goto RRETURN_29;
1953   case 30: goto RRETURN_30;
1954   case 31: goto RRETURN_31;
1955   case 38: goto RRETURN_38;
1956   case 40: goto RRETURN_40;
1957   case 42: goto RRETURN_42;
1958   case 44: goto RRETURN_44;
1959   case 48: goto RRETURN_48;
1960   case 52: goto RRETURN_52;
1961   }
1962
1963 abort();
1964 RRETURN_ERROR(JSRegExpErrorInternal);
1965
1966 #endif
1967
1968 RETURN:
1969     return is_match ? MATCH_MATCH : MATCH_NOMATCH;
1970
1971 RETURN_ERROR:
1972     while (!(frame >= stackframes && frame < stackframesend)) {
1973         newframe = frame->prevframe;
1974         delete frame;
1975         frame = newframe;
1976     }
1977     return i;
1978 }
1979
1980
1981 /*************************************************
1982 *         Execute a Regular Expression           *
1983 *************************************************/
1984
1985 /* This function applies a compiled re to a subject string and picks out
1986 portions of the string if it matches. Two elements in the vector are set for
1987 each substring: the offsets to the start and end of the substring.
1988
1989 Arguments:
1990   argument_re     points to the compiled expression
1991   extra_data      points to extra data or is NULL
1992   subject         points to the subject string
1993   length          length of subject string (may contain binary zeros)
1994   start_offset    where to start in the subject string
1995   options         option bits
1996   offsets         points to a vector of ints to be filled in with offsets
1997   offsetcount     the number of elements in the vector
1998
1999 Returns:          > 0 => success; value is the number of elements filled in
2000                   = 0 => success, but offsets is not big enough
2001                    -1 => failed to match
2002                  < -1 => some kind of unexpected problem
2003 */
2004
2005 int
2006 jsRegExpExecute(const pcre *argument_re,
2007   const UChar* subject, int length, int start_offset, int *offsets,
2008   int offsetcount)
2009 {
2010 int rc, resetcount, ocount;
2011 int first_byte = -1;
2012 int req_byte = -1;
2013 int req_byte2 = -1;
2014 BOOL using_temporary_offsets = false;
2015 BOOL first_byte_caseless = false;
2016 BOOL startline;
2017 BOOL req_byte_caseless = false;
2018 match_data match_block;
2019 USPTR start_match = (USPTR)subject + start_offset;
2020 USPTR end_subject;
2021 USPTR req_byte_ptr = start_match - 1;
2022 const uschar *start_code;
2023
2024 const real_pcre *external_re = (const real_pcre *)argument_re;
2025 const real_pcre *re = external_re;
2026
2027 /* Plausibility checks */
2028
2029 ASSERT(re);
2030 ASSERT(subject);
2031 ASSERT(offsetcount >= 0);
2032 ASSERT(offsets || offsetcount == 0);
2033
2034 /* Set up other data */
2035
2036 startline = (re->options & PCRE_STARTLINE) != 0;
2037
2038 /* The code starts after the real_pcre block and the capture name table. */
2039
2040 start_code = (const uschar *)(external_re + 1);
2041
2042 match_block.start_subject = (USPTR)subject;
2043 match_block.end_subject = match_block.start_subject + length;
2044 end_subject = match_block.end_subject;
2045
2046 match_block.lcc = _pcre_default_tables + lcc_offset;
2047 match_block.ctypes = _pcre_default_tables + ctypes_offset;
2048
2049 match_block.multiline = (re->options & PCRE_MULTILINE) != 0;
2050 match_block.caseless = (re->options & PCRE_CASELESS) != 0;
2051
2052 /* If the expression has got more back references than the offsets supplied can
2053 hold, we get a temporary chunk of working store to use during the matching.
2054 Otherwise, we can use the vector supplied, rounding down its size to a multiple
2055 of 3. */
2056
2057 ocount = offsetcount - (offsetcount % 3);
2058
2059 if (re->top_backref > 0 && re->top_backref >= ocount/3)
2060   {
2061   ocount = re->top_backref * 3 + 3;
2062   match_block.offset_vector = new int[ocount];
2063   if (match_block.offset_vector == NULL) return JSRegExpErrorNoMemory;
2064   using_temporary_offsets = true;
2065   DPRINTF(("Got memory to hold back references\n"));
2066   }
2067 else match_block.offset_vector = offsets;
2068
2069 match_block.offset_end = ocount;
2070 match_block.offset_max = (2*ocount)/3;
2071 match_block.offset_overflow = false;
2072
2073 /* Compute the minimum number of offsets that we need to reset each time. Doing
2074 this makes a huge difference to execution time when there aren't many brackets
2075 in the pattern. */
2076
2077 resetcount = 2 + re->top_bracket * 2;
2078 if (resetcount > offsetcount) resetcount = ocount;
2079
2080 /* Reset the working variable associated with each extraction. These should
2081 never be used unless previously set, but they get saved and restored, and so we
2082 initialize them to avoid reading uninitialized locations. */
2083
2084 if (match_block.offset_vector != NULL)
2085   {
2086   register int *iptr = match_block.offset_vector + ocount;
2087   register int *iend = iptr - resetcount/2 + 1;
2088   while (--iptr >= iend) *iptr = -1;
2089   }
2090
2091 /* Set up the first character to match, if available. The first_byte value is
2092 never set for an anchored regular expression, but the anchoring may be forced
2093 at run time, so we have to test for anchoring. The first char may be unset for
2094 an unanchored pattern, of course. If there's no first char and the pattern was
2095 studied, there may be a bitmap of possible first characters. */
2096
2097   if ((re->options & PCRE_FIRSTSET) != 0)
2098     {
2099     first_byte = re->first_byte & 255;
2100     if ((first_byte_caseless = ((re->first_byte & REQ_CASELESS) != 0)) == true)
2101       first_byte = match_block.lcc[first_byte];
2102     }
2103
2104 /* For anchored or unanchored matches, there may be a "last known required
2105 character" set. */
2106
2107 if ((re->options & PCRE_REQCHSET) != 0)
2108   {
2109   req_byte = re->req_byte & 255;
2110   req_byte_caseless = (re->req_byte & REQ_CASELESS) != 0;
2111   req_byte2 = (_pcre_default_tables + fcc_offset)[req_byte];  /* case flipped */
2112   }
2113
2114 /* Loop for handling unanchored repeated matching attempts; for anchored regexs
2115 the loop runs just once. */
2116
2117 do
2118   {
2119   USPTR save_end_subject = end_subject;
2120
2121   /* Reset the maximum number of extractions we might see. */
2122
2123   if (match_block.offset_vector != NULL)
2124     {
2125     register int *iptr = match_block.offset_vector;
2126     register int *iend = iptr + resetcount;
2127     while (iptr < iend) *iptr++ = -1;
2128     }
2129
2130   /* Advance to a unique first char if possible. If firstline is true, the
2131   start of the match is constrained to the first line of a multiline string.
2132   Implement this by temporarily adjusting end_subject so that we stop scanning
2133   at a newline. If the match fails at the newline, later code breaks this loop.
2134   */
2135
2136   /* Now test for a unique first byte */
2137
2138   if (first_byte >= 0)
2139     {
2140     pcre_uchar first_char = first_byte;
2141     if (first_byte_caseless)
2142       while (start_match < end_subject)
2143         {
2144         int sm = *start_match;
2145         if (sm > 127)
2146           break;
2147         if (match_block.lcc[sm] == first_char)
2148           break;
2149         start_match++;
2150         }
2151     else
2152       while (start_match < end_subject && *start_match != first_char)
2153         start_match++;
2154     }
2155
2156   /* Or to just after \n for a multiline match if possible */
2157
2158   else if (startline)
2159     {
2160     if (start_match > match_block.start_subject + start_offset)
2161       {
2162       while (start_match < end_subject && !isNewline(start_match[-1]))
2163         start_match++;
2164       }
2165     }
2166
2167   /* Restore fudged end_subject */
2168
2169   end_subject = save_end_subject;
2170
2171 #ifdef DEBUG  /* Sigh. Some compilers never learn. */
2172   printf(">>>> Match against: ");
2173   pchars(start_match, end_subject - start_match, true, &match_block);
2174   printf("\n");
2175 #endif
2176
2177   /* If req_byte is set, we know that that character must appear in the subject
2178   for the match to succeed. If the first character is set, req_byte must be
2179   later in the subject; otherwise the test starts at the match point. This
2180   optimization can save a huge amount of backtracking in patterns with nested
2181   unlimited repeats that aren't going to match. Writing separate code for
2182   cased/caseless versions makes it go faster, as does using an autoincrement
2183   and backing off on a match.
2184
2185   HOWEVER: when the subject string is very, very long, searching to its end can
2186   take a long time, and give bad performance on quite ordinary patterns. This
2187   showed up when somebody was matching /^C/ on a 32-megabyte string... so we
2188   don't do this when the string is sufficiently long.
2189
2190   ALSO: this processing is disabled when partial matching is requested.
2191   */
2192
2193   if (req_byte >= 0 &&
2194       end_subject - start_match < REQ_BYTE_MAX)
2195     {
2196     register USPTR p = start_match + ((first_byte >= 0)? 1 : 0);
2197
2198     /* We don't need to repeat the search if we haven't yet reached the
2199     place we found it at last time. */
2200
2201     if (p > req_byte_ptr)
2202       {
2203       if (req_byte_caseless)
2204         {
2205         while (p < end_subject)
2206           {
2207           register int pp = *p++;
2208           if (pp == req_byte || pp == req_byte2) { p--; break; }
2209           }
2210         }
2211       else
2212         {
2213         while (p < end_subject)
2214           {
2215           if (*p++ == req_byte) { p--; break; }
2216           }
2217         }
2218
2219       /* If we can't find the required character, break the matching loop */
2220
2221       if (p >= end_subject) break;
2222
2223       /* If we have found the required character, save the point where we
2224       found it, so that we don't search again next time round the loop if
2225       the start hasn't passed this character yet. */
2226
2227       req_byte_ptr = p;
2228       }
2229     }
2230
2231   /* When a match occurs, substrings will be set for all internal extractions;
2232   we just need to set up the whole thing as substring 0 before returning. If
2233   there were too many extractions, set the return code to zero. In the case
2234   where we had to get some local store to hold offsets for backreferences, copy
2235   those back references that we can. In this case there need not be overflow
2236   if certain parts of the pattern were not used. */
2237
2238   match_block.match_call_count = 0;
2239
2240   rc = match(start_match, start_code, 2, &match_block);
2241
2242   /* When the result is no match, if the subject's first character was a
2243   newline and the PCRE_FIRSTLINE option is set, break (which will return
2244   PCRE_ERROR_NOMATCH). The option requests that a match occur before the first
2245   newline in the subject. Otherwise, advance the pointer to the next character
2246   and continue - but the continuation will actually happen only when the
2247   pattern is not anchored. */
2248
2249   if (rc == MATCH_NOMATCH)
2250     {
2251     start_match++;
2252       while(start_match < end_subject && ISMIDCHAR(*start_match))
2253         start_match++;
2254     continue;
2255     }
2256
2257   if (rc != MATCH_MATCH)
2258     {
2259     DPRINTF((">>>> error: returning %d\n", rc));
2260     return rc;
2261     }
2262
2263   /* We have a match! Copy the offset information from temporary store if
2264   necessary */
2265
2266   if (using_temporary_offsets)
2267     {
2268     if (offsetcount >= 4)
2269       {
2270       memcpy(offsets + 2, match_block.offset_vector + 2,
2271         (offsetcount - 2) * sizeof(int));
2272       DPRINTF(("Copied offsets from temporary memory\n"));
2273       }
2274     if (match_block.end_offset_top > offsetcount)
2275       match_block.offset_overflow = true;
2276
2277     DPRINTF(("Freeing temporary memory\n"));
2278     delete [] match_block.offset_vector;
2279     }
2280
2281   rc = match_block.offset_overflow? 0 : match_block.end_offset_top/2;
2282
2283   if (offsetcount < 2) rc = 0; else
2284     {
2285     offsets[0] = start_match - match_block.start_subject;
2286     offsets[1] = match_block.end_match_ptr - match_block.start_subject;
2287     }
2288
2289   DPRINTF((">>>> returning %d\n", rc));
2290   return rc;
2291   }
2292
2293 /* This "while" is the end of the "do" above */
2294
2295 while (start_match <= end_subject);
2296
2297 if (using_temporary_offsets)
2298   {
2299   DPRINTF(("Freeing temporary memory\n"));
2300   delete [] match_block.offset_vector;
2301   }
2302
2303   DPRINTF((">>>> returning PCRE_ERROR_NOMATCH\n"));
2304   return JSRegExpErrorNoMatch;
2305 }