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