1		/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2		*
3		* ***** BEGIN LICENSE BLOCK *****
4		* Version: MPL 1.1/GPL 2.0/LGPL 2.1
5		*
6		* The contents of this file are subject to the Mozilla Public License Version
7		* 1.1 (the "License"); you may not use this file except in compliance with
8		* the License. You may obtain a copy of the License at
9		* http://www.mozilla.org/MPL/
10		*
11		* Software distributed under the License is distributed on an "AS IS" basis,
12		* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13		* for the specific language governing rights and limitations under the
14		* License.
15		*
16		* The Original Code is Mozilla Communicator client code, released
17		* March 31, 1998.
18		*
19		* The Initial Developer of the Original Code is
20		* Netscape Communications Corporation.
21		* Portions created by the Initial Developer are Copyright (C) 1998
22		* the Initial Developer. All Rights Reserved.
23		*
24		* Contributor(s):
25		*
26		* Alternatively, the contents of this file may be used under the terms of
27		* either of the GNU General Public License Version 2 or later (the "GPL"),
28		* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29		* in which case the provisions of the GPL or the LGPL are applicable instead
30		* of those above. If you wish to allow use of your version of this file only
31		* under the terms of either the GPL or the LGPL, and not to allow others to
32		* use your version of this file under the terms of the MPL, indicate your
33		* decision by deleting the provisions above and replace them with the notice
34		* and other provisions required by the GPL or the LGPL. If you do not delete
35		* the provisions above, a recipient may use your version of this file under
36		* the terms of any one of the MPL, the GPL or the LGPL.
37		*
38		* ***** END LICENSE BLOCK ***** */
39
40		/*
41		* JS regular expressions, after Perl.
42		*/
43		#include "jsstddef.h"
44		#include <stdlib.h>
45		#include <string.h>
46		#include "jstypes.h"
47		#include "jsarena.h" /* Added by JSIFY */
48		#include "jsutil.h" /* Added by JSIFY */
49		#include "jsapi.h"
50		#include "jsarray.h"
51		#include "jsatom.h"
52		#include "jscntxt.h"
53		#include "jsconfig.h"
54		#include "jsfun.h"
55		#include "jsgc.h"
56		#include "jsinterp.h"
57		#include "jslock.h"
58		#include "jsnum.h"
59		#include "jsobj.h"
60		#include "jsopcode.h"
61		#include "jsregexp.h"
62		#include "jsscan.h"
63		#include "jsstr.h"
64
65		#ifdef XP_MAC
66		#include <MacMemory.h>
67		#endif
68
69		#if JS_HAS_REGEXPS
70
71		/* Note : contiguity of 'simple opcodes' is important for simpleMatch() */
72		typedef enum REOp {
73		REOP_EMPTY         = 0,  /* match rest of input against rest of r.e. */
74		REOP_ALT           = 1,  /* alternative subexpressions in kid and next */
75		REOP_SIMPLE_START  = 2,  /* start of 'simple opcodes' */
76		REOP_BOL           = 2,  /* beginning of input (or line if multiline) */
77		REOP_EOL           = 3,  /* end of input (or line if multiline) */
78		REOP_WBDRY         = 4,  /* match "" at word boundary */
79		REOP_WNONBDRY      = 5,  /* match "" at word non-boundary */
80		REOP_DOT           = 6,  /* stands for any character */
81		REOP_DIGIT         = 7,  /* match a digit char: [0-9] */
82		REOP_NONDIGIT      = 8,  /* match a non-digit char: [^0-9] */
83		REOP_ALNUM         = 9,  /* match an alphanumeric char: [0-9a-z_A-Z] */
84		REOP_NONALNUM      = 10, /* match a non-alphanumeric char: [^0-9a-z_A-Z] */
85		REOP_SPACE         = 11, /* match a whitespace char */
86		REOP_NONSPACE      = 12, /* match a non-whitespace char */
87		REOP_BACKREF       = 13, /* back-reference (e.g., \1) to a parenthetical */
88		REOP_FLAT          = 14, /* match a flat string */
89		REOP_FLAT1         = 15, /* match a single char */
90		REOP_FLATi         = 16, /* case-independent REOP_FLAT */
91		REOP_FLAT1i        = 17, /* case-independent REOP_FLAT1 */
92		REOP_UCFLAT1       = 18, /* single Unicode char */
93		REOP_UCFLAT1i      = 19, /* case-independent REOP_UCFLAT1 */
94		REOP_UCFLAT        = 20, /* flat Unicode string; len immediate counts chars */
95		REOP_UCFLATi       = 21, /* case-independent REOP_UCFLAT */
96		REOP_CLASS         = 22, /* character class with index */
97		REOP_NCLASS        = 23, /* negated character class with index */
98		REOP_SIMPLE_END    = 23, /* end of 'simple opcodes' */
99		REOP_QUANT         = 25, /* quantified atom: atom{1,2} */
100		REOP_STAR          = 26, /* zero or more occurrences of kid */
101		REOP_PLUS          = 27, /* one or more occurrences of kid */
102		REOP_OPT           = 28, /* optional subexpression in kid */
103		REOP_LPAREN        = 29, /* left paren bytecode: kid is u.num'th sub-regexp */
104		REOP_RPAREN        = 30, /* right paren bytecode */
105		REOP_JUMP          = 31, /* for deoptimized closure loops */
106		REOP_DOTSTAR       = 32, /* optimize .* to use a single opcode */
107		REOP_ANCHOR        = 33, /* like .* but skips left context to unanchored r.e. */
108		REOP_EOLONLY       = 34, /* $ not preceded by any pattern */
109		REOP_BACKREFi      = 37, /* case-independent REOP_BACKREF */
110		REOP_LPARENNON     = 41, /* non-capturing version of REOP_LPAREN */
111		REOP_ASSERT        = 43, /* zero width positive lookahead assertion */
112		REOP_ASSERT_NOT    = 44, /* zero width negative lookahead assertion */
113		REOP_ASSERTTEST    = 45, /* sentinel at end of assertion child */
114		REOP_ASSERTNOTTEST = 46, /* sentinel at end of !assertion child */
115		REOP_MINIMALSTAR   = 47, /* non-greedy version of * */
116		REOP_MINIMALPLUS   = 48, /* non-greedy version of + */
117		REOP_MINIMALOPT    = 49, /* non-greedy version of ? */
118		REOP_MINIMALQUANT  = 50, /* non-greedy version of {} */
119		REOP_ENDCHILD      = 51, /* sentinel at end of quantifier child */
120		REOP_REPEAT        = 52, /* directs execution of greedy quantifier */
121		REOP_MINIMALREPEAT = 53, /* directs execution of non-greedy quantifier */
122		REOP_ALTPREREQ     = 54, /* prerequisite for ALT, either of two chars */
123		REOP_ALTPREREQ2    = 55, /* prerequisite for ALT, a char or a class */
124		REOP_ENDALT        = 56, /* end of final alternate */
125		REOP_CONCAT        = 57, /* concatenation of terms (parse time only) */
126
127		REOP_END
128		} REOp;
129
130		#define REOP_IS_SIMPLE(op)  (((op) >= REOP_SIMPLE_START) && ((op) <= REOP_SIMPLE_END))
131
132		struct RENode {
133		REOp            op;         /* r.e. op bytecode */
134		RENode          *next;      /* next in concatenation order */
135		void            *kid;       /* first operand */
136		union {
137		void        *kid2;      /* second operand */
138		jsint       num;        /* could be a number */
139		jsint       parenIndex; /* or a parenthesis index */
140		struct {                /* or a quantifier range */
141		uint16  min;
142		uint16  max;
143		JSBool  greedy;
144		} range;
145		struct {                /* or a character class */
146		uint16  startIndex;
147		uint16  kidlen;     /* length of string at kid, in jschars */
148		uint16  bmsize;     /* bitmap size, based on max char code */
149		uint16  index;      /* index into class list */
150		JSBool  sense;
151		} ucclass;
152		struct {                /* or a literal sequence */
153		jschar  chr;        /* of one character */
154		uint16  length;     /* or many (via the kid) */
155		} flat;
156		struct {
157		RENode  *kid2;      /* second operand from ALT */
158		jschar  ch1;        /* match char for ALTPREREQ */
159		jschar  ch2;        /* ditto, or class index for ALTPREREQ2 */
160		} altprereq;
161		} u;
162		};
163
164		#define RE_IS_LETTER(c)      ( ((c >= 'A') && (c <= 'Z')) ||               \
165		((c >= 'a') && (c <= 'z')) )
166		#define RE_IS_LINE_TERM(c)  ( (c == '\n') || (c == '\r') ||               \
167		(c == LINE_SEPARATOR) || (c == PARA_SEPARATOR))
168
169		#define CLASS_CACHE_SIZE (4)
170		typedef struct CompilerState {
171		JSContext       *context;
172		JSTokenStream   *tokenStream; /* For reporting errors */
173		const jschar    *cpbegin;
174		const jschar    *cpend;
175		const jschar    *cp;
176		uintN           flags;
177		uint16          parenCount;
178		uint16          classCount;   /* number of [] encountered */
179		size_t          progLength;   /* estimated bytecode length */
180		uintN           treeDepth;    /* maximum depth of parse tree */
181		RENode          *result;
182		struct {
183		const jschar *start;        /* small cache of class strings */
184		uint16 length;              /* since they're often the same */
185		uint16 index;
186		} classCache[CLASS_CACHE_SIZE];
187		} CompilerState;
188
189		typedef struct RECapture {
190		int32 index;               /* start of contents, -1 for empty  */
191		uint16 length;             /* length of capture */
192		} RECapture;
193
194		typedef struct REMatchState {
195		const jschar *cp;
196		RECapture parens[1];      /* first of 're->parenCount' captures,
197		* allocated at end of this struct.
198		*/
199		} REMatchState;
200
201		struct REBackTrackData;
202
203		typedef struct REProgState {
204		jsbytecode *continue_pc;        /* current continuation data */
205		jsbytecode continue_op;
206		uint16 index;                   /* progress in text */
207		uintN parenSoFar;               /* highest indexed paren started */
208		union {
209		struct {
210		uint16 min;             /* current quantifier limits */
211		uint16 max;
212		} quantifier;
213		struct {
214		size_t top;             /* backtrack stack state */
215		size_t sz;
216		} assertion;
217		} u;
218		} REProgState;
219
220		typedef struct REBackTrackData {
221		size_t sz;                      /* size of previous stack entry */
222		jsbytecode *backtrack_pc;       /* where to backtrack to */
223		jsbytecode backtrack_op;
224		const jschar *cp;               /* index in text of match at backtrack */
225		intN parenIndex;                /* start index of saved paren contents */
226		uint16 parenCount;              /* # of saved paren contents */
227		uint16 precedingStateTop;       /* number of parent states */
228		/* saved parent states follow */
229		/* saved paren contents follow */
230		} REBackTrackData;
231
232		#define INITIAL_STATESTACK (100)
233		#define INITIAL_BACKTRACK (8000)
234
235		typedef struct REGlobalData {
236		JSContext *cx;
237		JSRegExp *regexp;               /* the RE in execution */
238		JSBool ok;                      /* runtime error (out_of_memory only?) */
239		size_t start;                   /* offset to start at */
240		ptrdiff_t skipped;              /* chars skipped anchoring this r.e. */
241		const jschar *cpbegin, *cpend;  /* text base address and limit */
242
243		REProgState *stateStack;        /* stack of state of current parents */
244		uint16 stateStackTop;
245		uint16 maxStateStack;
246
247		REBackTrackData *backTrackStack;/* stack of matched-so-far positions */
248		REBackTrackData *backTrackSP;
249		size_t maxBackTrack;
250		size_t cursz;                   /* size of current stack entry */
251
252		JSArenaPool pool;               /* I don't understand but it's faster to
253		* use this than to malloc/free the three
254		* items that are allocated from this pool
255		*/
256
257		} REGlobalData;
258
259
260		/*
261		* 1. If IgnoreCase is false, return ch.
262		* 2. Let u be ch converted to upper case as if by calling
263		*    String.prototype.toUpperCase on the one-character string ch.
264		* 3. If u does not consist of a single character, return ch.
265		* 4. Let cu be u's character.
266		* 5. If ch's code point value is greater than or equal to decimal 128 and cu's
267		*    code point value is less than decimal 128, then return ch.
268		* 6. Return cu.
269		*/
270		static jschar
271		upcase(jschar ch)
272	0	{
273	0	jschar cu = JS_TOUPPER(ch);
274	0	if ((ch >= 128) && (cu < 128)) return ch;
275	0	return cu;
276		}
277
278		static jschar
279		downcase(jschar ch)
280	0	{
281	0	jschar cl = JS_TOLOWER(ch);
282	0	if ((cl >= 128) && (ch < 128)) return ch;
283	0	return cl;
284		}
285
286		/* Construct and initialize an RENode, returning NULL for out-of-memory */
287		static RENode *
288		NewRENode(CompilerState *state, REOp op)
289	0	{
290	0	JSContext *cx;
291	0	RENode *ren;
292
293	0	cx = state->context;
294	0	JS_ARENA_ALLOCATE_CAST(ren, RENode *, &cx->tempPool, sizeof *ren);
295	0	if (!ren) {
296	0	JS_ReportOutOfMemory(cx);
297	0	return NULL;
298		}
299	0	ren->op = op;
300	0	ren->next = NULL;
301	0	ren->kid = NULL;
302	0	return ren;
303		}
304
305		/*
306		* Validates and converts hex ascii value.
307		*/
308		static JSBool
309		isASCIIHexDigit(jschar c, uintN *digit)
310	0	{
311	0	uintN cv = c;
312
313	0	if (cv < '0')
314	0	return JS_FALSE;
315	0	if (cv <= '9') {
316	0	*digit = cv - '0';
317	0	return JS_TRUE;
318		}
319	0	cv |= 0x20;
320	0	if (cv >= 'a' && cv <= 'f') {
321	0	*digit = cv - 'a' + 10;
322	0	return JS_TRUE;
323		}
324	0	return JS_FALSE;
325		}
326
327
328		typedef struct {
329		REOp op;
330		const jschar *errPos;
331		uint16 parenIndex;
332		} REOpData;
333
334
335		/*
336		* Process the op against the two top operands, reducing them to a single
337		* operand in the penultimate slot. Update progLength and treeDepth.
338		*/
339		static JSBool
340		processOp(CompilerState *state, REOpData *opData, RENode **operandStack, intN operandSP)
341	0	{
342	0	RENode *result;
343
344	0	switch (opData->op) {
345		case REOP_ALT:
346	0	result = NewRENode(state, REOP_ALT);
347	0	if (!result)
348	0	return JS_FALSE;
349	0	result->kid = operandStack[operandSP - 2];
350	0	result->u.kid2 = operandStack[operandSP - 1];
351	0	operandStack[operandSP - 2] = result;
352		/*
353		* look at both alternates to see if there's a FLAT or a CLASS at
354		* the start of each. If so, use a prerequisite match
355		*/
356	0	++state->treeDepth;
357	0	if ((((RENode *)(result->kid))->op == REOP_FLAT)
358		&& (((RENode *)(result->u.kid2))->op == REOP_FLAT)
359		&& ((state->flags & JSREG_FOLD) == 0) ) {
360	0	result->op = REOP_ALTPREREQ;
361	0	result->u.altprereq.ch1
362		= ((RENode *)(result->kid))->u.flat.chr;
363	0	result->u.altprereq.ch2
364		= ((RENode *)(result->u.kid2))->u.flat.chr;
365		/* ALTPREREQ, <end>, uch1, uch2, <next>, ...,
366		JUMP, <end> ... ENDALT */
367	0	state->progLength += 13;
368		}
369		else
370	0	if ((((RENode *)(result->kid))->op == REOP_CLASS)
371		&& (((RENode *)(result->kid))->u.ucclass.index < 256)
372		&& (((RENode *)(result->u.kid2))->op == REOP_FLAT)
373		&& ((state->flags & JSREG_FOLD) == 0) ) {
374	0	result->op = REOP_ALTPREREQ2;
375	0	result->u.altprereq.ch1
376		= ((RENode *)(result->u.kid2))->u.flat.chr;
377	0	result->u.altprereq.ch2
378		= ((RENode *)(result->kid))->u.ucclass.index;
379		/* ALTPREREQ2, <end>, uch1, uch2, <next>, ...,
380		JUMP, <end> ... ENDALT */
381	0	state->progLength += 13;
382		}
383		else
384	0	if ((((RENode *)(result->kid))->op == REOP_FLAT)
385		&& (((RENode *)(result->u.kid2))->op == REOP_CLASS)
386		&& (((RENode *)(result->u.kid2))->u.ucclass.index < 256)
387		&& ((state->flags & JSREG_FOLD) == 0) ) {
388	0	result->op = REOP_ALTPREREQ2;
389	0	result->u.altprereq.ch1
390		= ((RENode *)(result->kid))->u.flat.chr;
391	0	result->u.altprereq.ch2
392		= ((RENode *)(result->u.kid2))->u.ucclass.index;
393		/* ALTPREREQ2, <end>, uch1, uch2, <next>, ...,
394		JUMP, <end> ... ENDALT */
395	0	state->progLength += 13;
396		}
397		else
398		/* ALT, <next>, ..., JUMP, <end> ... ENDALT */
399	0	state->progLength += 7;
400	0	break;
401		case REOP_CONCAT:
402	0	result = operandStack[operandSP - 2];
403	0	while (result->next)
404	0	result = result->next;
405	0	result->next = operandStack[operandSP - 1];
406	0	break;
407		case REOP_ASSERT:
408		case REOP_ASSERT_NOT:
409		case REOP_LPARENNON:
410		case REOP_LPAREN:
411		/* These should have been processed by a close paren. */
412	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
413		NULL, JSREPORT_ERROR,
414		JSMSG_MISSING_PAREN, opData->errPos);
415	0	return JS_FALSE;
416		default:;
417		}
418	0	return JS_TRUE;
419		}
420
421		/*
422		* Parser forward declarations.
423		*/
424		static JSBool parseTerm(CompilerState *state);
425		static JSBool parseQuantifier(CompilerState *state);
426
427		/*
428		* Top-down regular expression grammar, based closely on Perl4.
429		*
430		*  regexp:     altern                  A regular expression is one or more
431		*              altern '|' regexp       alternatives separated by vertical bar.
432		*/
433
434		#define INITIAL_STACK_SIZE (128)
435		static JSBool
436		parseRegExp(CompilerState *state)
437	0	{
438	0	uint16 parenIndex;
439	0	RENode *operand;
440	0	REOpData *operatorStack;
441	0	RENode **operandStack;
442	0	REOp op;
443	0	intN i;
444	0	JSBool result = JS_FALSE;
445
446	0	intN operatorSP = 0, operatorStackSize = INITIAL_STACK_SIZE;
447	0	intN operandSP = 0, operandStackSize = INITIAL_STACK_SIZE;
448
449		/* Watch out for empty regexp */
450	0	if (state->cp == state->cpend) {
451	0	state->result = NewRENode(state, REOP_EMPTY);
452	0	return (state->result != NULL);
453		}
454
455	0	operatorStack = (REOpData *)JS_malloc(state->context,
456		sizeof(REOpData) * operatorStackSize);
457	0	if (!operatorStack)
458	0	return JS_FALSE;
459
460	0	operandStack = (RENode **)JS_malloc(state->context,
461		sizeof(RENode *) * operandStackSize);
462	0	if (!operandStack)
463	0	goto out;
464
465
466	0	while (JS_TRUE) {
467	0	if (state->cp == state->cpend) {
468		/*
469		* If we are at the end of the regexp and we're short an operand,
470		* the regexp must have the form /x|/ or some such.
471		*/
472	0	if (operatorSP == operandSP) {
473	0	operand = NewRENode(state, REOP_EMPTY);
474	0	if (!operand)
475	0	goto out;
476	0	goto pushOperand;
477		}
478		} else {
479	0	switch (*state->cp) {
480		/* balance '(' */
481		case '(':           /* balance ')' */
482	0	++state->cp;
483	0	if ((state->cp < state->cpend) && (*state->cp == '?')
484		&& ( (state->cp[1] == '=')
485		|| (state->cp[1] == '!')
486		|| (state->cp[1] == ':') )) {
487	0	++state->cp;
488	0	if (state->cp == state->cpend) {
489	0	js_ReportCompileErrorNumber(state->context,
490		state->tokenStream,
491		NULL, JSREPORT_ERROR,
492		JSMSG_MISSING_PAREN);
493	0	goto out;
494		}
495	0	switch (*state->cp++) {
496		case '=':
497	0	op = REOP_ASSERT;
498		/* ASSERT, <next>, ... ASSERTTEST */
499	0	state->progLength += 4;
500	0	break;
501		case '!':
502	0	op = REOP_ASSERT_NOT;
503		/* ASSERTNOT, <next>, ... ASSERTNOTTEST */
504	0	state->progLength += 4;
505	0	break;
506		case ':':
507	0	op = REOP_LPARENNON;
508		break;
509		}
510	0	parenIndex = state->parenCount;
511		}
512		else {
513	0	op = REOP_LPAREN;
514		/* LPAREN, <index>, ... RPAREN, <index> */
515	0	state->progLength += 6;
516	0	parenIndex = state->parenCount++;
517	0	if (state->parenCount == 65535) {
518	0	js_ReportCompileErrorNumber(state->context,
519		state->tokenStream,
520		NULL, JSREPORT_ERROR,
521		JSMSG_TOO_MANY_PARENS);
522	0	goto out;
523		}
524		}
525	0	goto pushOperator;
526		case ')':
527		/* If there's not a stacked open parenthesis, throw
528		* a syntax error.
529		*/
530	0	for (i = operatorSP - 1; i >= 0; i--)
531	0	if ((operatorStack[i].op == REOP_ASSERT)
532		|| (operatorStack[i].op == REOP_ASSERT_NOT)
533		|| (operatorStack[i].op == REOP_LPARENNON)
534		|| (operatorStack[i].op == REOP_LPAREN))
535	0	break;
536	0	if (i == -1) {
537	0	js_ReportCompileErrorNumber(state->context,
538		state->tokenStream,
539		NULL, JSREPORT_ERROR,
540		JSMSG_UNMATCHED_RIGHT_PAREN);
541	0	goto out;
542		}
543		/* fall thru... */
544		case '|':
545		/* Expected an operand before these, so make an empty one */
546	0	operand = NewRENode(state, REOP_EMPTY);
547	0	if (!operand)
548	0	goto out;
549	0	goto pushOperand;
550		default:
551	0	if (!parseTerm(state))
552	0	goto out;
553	0	operand = state->result;
554		pushOperand:
555	0	if (operandSP == operandStackSize) {
556	0	operandStackSize += operandStackSize;
557	0	operandStack =
558		(RENode **)JS_realloc(state->context, operandStack,
559		sizeof(RENode *) * operandStackSize);
560	0	if (!operandStack)
561	0	goto out;
562		}
563	0	operandStack[operandSP++] = operand;
564	0	break;
565		}
566		}
567		/* At the end; process remaining operators */
568		restartOperator:
569	0	if (state->cp == state->cpend) {
570	0	while (operatorSP) {
571	0	--operatorSP;
572	0	if (!processOp(state, &operatorStack[operatorSP],
573		operandStack, operandSP))
574	0	goto out;
575	0	--operandSP;
576		}
577	0	JS_ASSERT(operandSP == 1);
578	0	state->result = operandStack[0];
579	0	result = JS_TRUE;
580	0	goto out;
581		}
582	0	switch (*state->cp) {
583		case '|':
584		/* Process any stacked 'concat' operators */
585	0	++state->cp;
586	0	while (operatorSP
587		&& (operatorStack[operatorSP - 1].op == REOP_CONCAT)) {
588	0	--operatorSP;
589	0	if (!processOp(state, &operatorStack[operatorSP],
590		operandStack, operandSP))
591	0	goto out;
592	0	--operandSP;
593		}
594	0	op = REOP_ALT;
595	0	goto pushOperator;
596
597		case ')':
598		/* If there's not a stacked open parenthesis,we
599		* accept the close as a flat.
600		*/
601	0	for (i = operatorSP - 1; i >= 0; i--)
602	0	if ((operatorStack[i].op == REOP_ASSERT)
603		|| (operatorStack[i].op == REOP_ASSERT_NOT)
604		|| (operatorStack[i].op == REOP_LPARENNON)
605		|| (operatorStack[i].op == REOP_LPAREN))
606	0	break;
607	0	if (i == -1) {
608	0	js_ReportCompileErrorNumber(state->context,
609		state->tokenStream,
610		NULL, JSREPORT_ERROR,
611		JSMSG_UNMATCHED_RIGHT_PAREN);
612	0	goto out;
613		}
614	0	++state->cp;
615		/* process everything on the stack until the open */
616	0	while (JS_TRUE) {
617	0	JS_ASSERT(operatorSP);
618	0	--operatorSP;
619	0	switch (operatorStack[operatorSP].op) {
620		case REOP_ASSERT:
621		case REOP_ASSERT_NOT:
622		case REOP_LPAREN:
623	0	operand = NewRENode(state, operatorStack[operatorSP].op);
624	0	if (!operand)
625	0	goto out;
626	0	operand->u.parenIndex
627		= operatorStack[operatorSP].parenIndex;
628	0	JS_ASSERT(operandSP);
629	0	operand->kid = operandStack[operandSP - 1];
630	0	operandStack[operandSP - 1] = operand;
631	0	++state->treeDepth;
632		/* fall thru... */
633		case REOP_LPARENNON:
634	0	state->result = operandStack[operandSP - 1];
635	0	if (!parseQuantifier(state))
636	0	goto out;
637	0	operandStack[operandSP - 1] = state->result;
638	0	goto restartOperator;
639		default:
640	0	if (!processOp(state, &operatorStack[operatorSP],
641		operandStack, operandSP))
642	0	goto out;
643	0	--operandSP;
644	0	break;
645		}
646		}
647	0	break;
648		default:
649		/* Anything else is the start of the next term */
650	0	op = REOP_CONCAT;
651		pushOperator:
652	0	if (operatorSP == operatorStackSize) {
653	0	operatorStackSize += operatorStackSize;
654	0	operatorStack =
655		(REOpData *)JS_realloc(state->context, operatorStack,
656		sizeof(REOpData) * operatorStackSize);
657	0	if (!operatorStack)
658	0	goto out;
659		}
660	0	operatorStack[operatorSP].op = op;
661	0	operatorStack[operatorSP].errPos = state->cp;
662	0	operatorStack[operatorSP++].parenIndex = parenIndex;
663	0	break;
664		}
665		}
666		out:
667	0	if (operatorStack)
668	0	JS_free(state->context, operatorStack);
669	0	if (operandStack)
670	0	JS_free(state->context, operandStack);
671	0	return result;
672		}
673
674		/*
675		* Extract and return a decimal value at state->cp, the
676		* initial character 'c' has already been read.
677		*/
678		static intN
679		getDecimalValue(jschar c, CompilerState *state)
680	0	{
681	0	intN value = JS7_UNDEC(c);
682	0	while (state->cp < state->cpend) {
683	0	c = *state->cp;
684	0	if (!JS7_ISDEC(c))
685	0	break;
686	0	value = (10 * value) + JS7_UNDEC(c);
687	0	++state->cp;
688		}
689	0	return value;
690		}
691
692		/*
693		* Calculate the total size of the bitmap required for a class expression.
694		*/
695		static JSBool
696		calculateBitmapSize(CompilerState *state, RENode *target, const jschar *src,
697		const jschar *end)
698	0	{
699	0	jschar rangeStart, c;
700	0	uintN n, digit, nDigits, i;
701	0	uintN max = 0;
702	0	JSBool inRange = JS_FALSE;
703
704	0	target->u.ucclass.bmsize = 0;
705	0	target->u.ucclass.sense = JS_TRUE;
706
707	0	if (src == end)
708	0	return JS_TRUE;
709
710	0	if (*src == '^') {
711	0	++src;
712	0	target->u.ucclass.sense = JS_FALSE;
713		}
714
715	0	while (src != end) {
716	0	uintN localMax = 0;
717	0	switch (*src) {
718		case '\\':
719	0	++src;
720	0	c = *src++;
721	0	switch (c) {
722		case 'b':
723	0	localMax = 0x8;
724	0	break;
725		case 'f':
726	0	localMax = 0xC;
727	0	break;
728		case 'n':
729	0	localMax = 0xA;
730	0	break;
731		case 'r':
732	0	localMax = 0xD;
733	0	break;
734		case 't':
735	0	localMax = 0x9;
736	0	break;
737		case 'v':
738	0	localMax = 0xB;
739	0	break;
740		case 'c':
741	0	if (((src + 1) < end) && RE_IS_LETTER(src[1]))
742	0	localMax = (jschar)(*src++ & 0x1F);
743		else
744	0	localMax = '\\';
745	0	break;
746		case 'x':
747	0	nDigits = 2;
748	0	goto lexHex;
749		case 'u':
750	0	nDigits = 4;
751		lexHex:
752	0	n = 0;
753	0	for (i = 0; (i < nDigits) && (src < end); i++) {
754	0	c = *src++;
755	0	if (!isASCIIHexDigit(c, &digit)) {
756		/*
757		* Back off to accepting the original
758		*'\' as a literal.
759		*/
760	0	src -= (i + 1);
761	0	n = '\\';
762	0	break;
763		}
764	0	n = (n << 4) | digit;
765		}
766	0	localMax = n;
767	0	break;
768		case 'd':
769	0	if (inRange) {
770	0	JS_ReportErrorNumber(state->context,
771		js_GetErrorMessage, NULL,
772		JSMSG_BAD_CLASS_RANGE);
773	0	return JS_FALSE;
774		}
775	0	localMax = '9';
776	0	break;
777		case 'D':
778		case 's':
779		case 'S':
780		case 'w':
781		case 'W':
782	0	if (inRange) {
783	0	JS_ReportErrorNumber(state->context,
784		js_GetErrorMessage, NULL,
785		JSMSG_BAD_CLASS_RANGE);
786	0	return JS_FALSE;
787		}
788	0	target->u.ucclass.bmsize = 65535;
789	0	return JS_TRUE;
790		case '0':
791		case '1':
792		case '2':
793		case '3':
794		case '4':
795		case '5':
796		case '6':
797		case '7':
798		/*
799		*  This is a non-ECMA extension - decimal escapes (in this
800		*  case, octal!) are supposed to be an error inside class
801		*  ranges, but supported here for backwards compatibility.
802		*
803		*/
804	0	n = JS7_UNDEC(c);
805	0	c = *src;
806	0	if ('0' <= c && c <= '7') {
807	0	src++;
808	0	n = 8 * n + JS7_UNDEC(c);
809	0	c = *src;
810	0	if ('0' <= c && c <= '7') {
811	0	src++;
812	0	i = 8 * n + JS7_UNDEC(c);
813	0	if (i <= 0377)
814	0	n = i;
815		else
816	0	src--;
817		}
818		}
819	0	localMax = n;
820	0	break;
821
822		default:
823	0	localMax = c;
824	0	break;
825		}
826	0	break;
827		default:
828	0	localMax = *src++;
829	0	break;
830		}
831	0	if (inRange) {
832	0	if (rangeStart > localMax) {
833	0	JS_ReportErrorNumber(state->context,
834		js_GetErrorMessage, NULL,
835		JSMSG_BAD_CLASS_RANGE);
836	0	return JS_FALSE;
837		}
838	0	inRange = JS_FALSE;
839		}
840		else {
841	0	if (src < (end - 1)) {
842	0	if (*src == '-') {
843	0	++src;
844	0	inRange = JS_TRUE;
845	0	rangeStart = (jschar)localMax;
846	0	continue;
847		}
848		}
849		}
850	0	if (state->flags & JSREG_FOLD) {
851	0	c = JS_MAX(upcase((jschar)localMax), downcase((jschar)localMax));
852	0	if (c > localMax)
853	0	localMax = c;
854		}
855	0	if (localMax > max)
856	0	max = localMax;
857		}
858	0	target->u.ucclass.bmsize = max;
859	0	return JS_TRUE;
860		}
861
862		/*
863		*  item:       assertion               An item is either an assertion or
864		*              quantatom               a quantified atom.
865		*
866		*  assertion:  '^'                     Assertions match beginning of string
867		*                                      (or line if the class static property
868		*                                      RegExp.multiline is true).
869		*              '$'                     End of string (or line if the class
870		*                                      static property RegExp.multiline is
871		*                                      true).
872		*              '\b'                    Word boundary (between \w and \W).
873		*              '\B'                    Word non-boundary.
874		*
875		*  quantatom:  atom                    An unquantified atom.
876		*              quantatom '{' n ',' m '}'
877		*                                      Atom must occur between n and m times.
878		*              quantatom '{' n ',' '}' Atom must occur at least n times.
879		*              quantatom '{' n '}'     Atom must occur exactly n times.
880		*              quantatom '*'           Zero or more times (same as {0,}).
881		*              quantatom '+'           One or more times (same as {1,}).
882		*              quantatom '?'           Zero or one time (same as {0,1}).
883		*
884		*              any of which can be optionally followed by '?' for ungreedy
885		*
886		*  atom:       '(' regexp ')'          A parenthesized regexp (what matched
887		*                                      can be addressed using a backreference,
888		*                                      see '\' n below).
889		*              '.'                     Matches any char except '\n'.
890		*              '[' classlist ']'       A character class.
891		*              '[' '^' classlist ']'   A negated character class.
892		*              '\f'                    Form Feed.
893		*              '\n'                    Newline (Line Feed).
894		*              '\r'                    Carriage Return.
895		*              '\t'                    Horizontal Tab.
896		*              '\v'                    Vertical Tab.
897		*              '\d'                    A digit (same as [0-9]).
898		*              '\D'                    A non-digit.
899		*              '\w'                    A word character, [0-9a-z_A-Z].
900		*              '\W'                    A non-word character.
901		*              '\s'                    A whitespace character, [ \b\f\n\r\t\v].
902		*              '\S'                    A non-whitespace character.
903		*              '\' n                   A backreference to the nth (n decimal
904		*                                      and positive) parenthesized expression.
905		*              '\' octal               An octal escape sequence (octal must be
906		*                                      two or three digits long, unless it is
907		*                                      0 for the null character).
908		*              '\x' hex                A hex escape (hex must be two digits).
909		*              '\u' unicode            A unicode escape (must be four digits).
910		*              '\c' ctrl               A control character, ctrl is a letter.
911		*              '\' literalatomchar     Any character except one of the above
912		*                                      that follow '\' in an atom.
913		*              otheratomchar           Any character not first among the other
914		*                                      atom right-hand sides.
915		*/
916		static JSBool
917		parseTerm(CompilerState *state)
918	0	{
919	0	jschar c = *state->cp++;
920	0	uintN nDigits;
921	0	uintN num, tmp, n, i;
922	0	const jschar *termStart;
923	0	JSBool foundCachedCopy;
924
925	0	switch (c) {
926		/* assertions and atoms */
927		case '^':
928	0	state->result = NewRENode(state, REOP_BOL);
929	0	if (!state->result)
930	0	return JS_FALSE;
931	0	state->progLength++;
932	0	return JS_TRUE;
933		case '$':
934	0	state->result = NewRENode(state, REOP_EOL);
935	0	if (!state->result)
936	0	return JS_FALSE;
937	0	state->progLength++;
938	0	return JS_TRUE;
939		case '\\':
940	0	if (state->cp >= state->cpend) {
941		/* a trailing '\' is an error */
942	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
943		NULL, JSREPORT_ERROR,
944		JSMSG_TRAILING_SLASH);
945	0	return JS_FALSE;
946		}
947	0	c = *state->cp++;
948	0	switch (c) {
949		/* assertion escapes */
950		case 'b' :
951	0	state->result = NewRENode(state, REOP_WBDRY);
952	0	if (!state->result)
953	0	return JS_FALSE;
954	0	state->progLength++;
955	0	return JS_TRUE;
956		case 'B':
957	0	state->result = NewRENode(state, REOP_WNONBDRY);
958	0	if (!state->result)
959	0	return JS_FALSE;
960	0	state->progLength++;
961	0	return JS_TRUE;
962		/* Decimal escape */
963		case '0':
964	0	if (JS_HAS_STRICT_OPTION(state->context))
965	0	c = 0;
966		else {
967		doOctal:
968	0	num = 0;
969	0	while (state->cp < state->cpend) {
970	0	if ('0' <= (c = *state->cp) && c <= '7') {
971	0	state->cp++;
972	0	tmp = 8 * num + (uintN)JS7_UNDEC(c);
973	0	if (tmp > 0377)
974	0	break;
975	0	num = tmp;
976		}
977		else
978	0	break;
979		}
980	0	c = (jschar)(num);
981		}
982		doFlat:
983	0	state->result = NewRENode(state, REOP_FLAT);
984	0	if (!state->result)
985	0	return JS_FALSE;
986	0	state->result->u.flat.chr = c;
987	0	state->result->u.flat.length = 1;
988	0	state->progLength += 3;
989	0	break;
990		case '1':
991		case '2':
992		case '3':
993		case '4':
994		case '5':
995		case '6':
996		case '7':
997		case '8':
998		case '9':
999	0	termStart = state->cp - 1;
1000	0	num = (uintN)getDecimalValue(c, state);
1001	0	if (num > 9 &&
1002		num > state->parenCount &&
1003		!JS_HAS_STRICT_OPTION(state->context)) {
1004	0	state->cp = termStart;
1005	0	goto doOctal;
1006		}
1007	0	state->result = NewRENode(state, REOP_BACKREF);
1008	0	if (!state->result)
1009	0	return JS_FALSE;
1010	0	state->result->u.parenIndex = num - 1;
1011	0	state->progLength += 3;
1012	0	break;
1013		/* Control escape */
1014		case 'f':
1015	0	c = 0xC;
1016	0	goto doFlat;
1017		case 'n':
1018	0	c = 0xA;
1019	0	goto doFlat;
1020		case 'r':
1021	0	c = 0xD;
1022	0	goto doFlat;
1023		case 't':
1024	0	c = 0x9;
1025	0	goto doFlat;
1026		case 'v':
1027	0	c = 0xB;
1028	0	goto doFlat;
1029		/* Control letter */
1030		case 'c':
1031	0	if (((state->cp + 1) < state->cpend) &&
1032		RE_IS_LETTER(state->cp[1]))
1033	0	c = (jschar)(*state->cp++ & 0x1F);
1034		else {
1035		/* back off to accepting the original '\' as a literal */
1036	0	--state->cp;
1037	0	c = '\\';
1038		}
1039	0	goto doFlat;
1040		/* HexEscapeSequence */
1041		case 'x':
1042	0	nDigits = 2;
1043	0	goto lexHex;
1044		/* UnicodeEscapeSequence */
1045		case 'u':
1046	0	nDigits = 4;
1047		lexHex:
1048	0	n = 0;
1049	0	for (i = 0; (i < nDigits)
1050		&& (state->cp < state->cpend); i++) {
1051	0	uintN digit;
1052	0	c = *state->cp++;
1053	0	if (!isASCIIHexDigit(c, &digit)) {
1054		/*
1055		*  back off to accepting the original
1056		*  'u' or 'x' as a literal
1057		*/
1058	0	state->cp -= (i + 2);
1059	0	n = *state->cp++;
1060	0	break;
1061		}
1062	0	n = (n << 4) | digit;
1063		}
1064	0	c = (jschar)(n);
1065	0	goto doFlat;
1066		/* Character class escapes */
1067		case 'd':
1068	0	state->result = NewRENode(state, REOP_DIGIT);
1069		doSimple:
1070	0	if (!state->result)
1071	0	return JS_FALSE;
1072	0	state->progLength++;
1073	0	break;
1074		case 'D':
1075	0	state->result = NewRENode(state, REOP_NONDIGIT);
1076	0	goto doSimple;
1077		case 's':
1078	0	state->result = NewRENode(state, REOP_SPACE);
1079	0	goto doSimple;
1080		case 'S':
1081	0	state->result = NewRENode(state, REOP_NONSPACE);
1082	0	goto doSimple;
1083		case 'w':
1084	0	state->result = NewRENode(state, REOP_ALNUM);
1085	0	goto doSimple;
1086		case 'W':
1087	0	state->result = NewRENode(state, REOP_NONALNUM);
1088	0	goto doSimple;
1089		/* IdentityEscape */
1090		default:
1091	0	state->result = NewRENode(state, REOP_FLAT);
1092	0	if (!state->result)
1093	0	return JS_FALSE;
1094	0	state->result->u.flat.chr = c;
1095	0	state->result->u.flat.length = 1;
1096	0	state->result->kid = (void *)(state->cp - 1);
1097	0	state->progLength += 3;
1098	0	break;
1099		}
1100	0	break;
1101		case '[':
1102	0	state->result = NewRENode(state, REOP_CLASS);
1103	0	if (!state->result)
1104	0	return JS_FALSE;
1105	0	termStart = state->cp;
1106	0	state->result->u.ucclass.startIndex = termStart - state->cpbegin;
1107	0	while (JS_TRUE) {
1108	0	if (state->cp == state->cpend) {
1109	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
1110		NULL, JSREPORT_ERROR,
1111		JSMSG_UNTERM_CLASS, termStart);
1112	0	return JS_FALSE;
1113		}
1114	0	if (*state->cp == '\\')
1115	0	state->cp++;
1116		else {
1117	0	if (*state->cp == ']') {
1118	0	state->result->u.ucclass.kidlen = state->cp - termStart;
1119	0	break;
1120		}
1121		}
1122	0	state->cp++;
1123		}
1124	0	foundCachedCopy = JS_FALSE;
1125	0	for (i = 0; i < CLASS_CACHE_SIZE; i++) {
1126	0	if (state->classCache[i].start) {
1127	0	if (state->classCache[i].length == state->result->u.ucclass.kidlen) {
1128	0	foundCachedCopy = JS_TRUE;
1129	0	for (n = 0; n < state->classCache[i].length; n++) {
1130	0	if (state->classCache[i].start[n] != termStart[n]) {
1131	0	foundCachedCopy = JS_FALSE;
1132	0	break;
1133		}
1134		}
1135	0	if (foundCachedCopy) {
1136	0	state->result->u.ucclass.index = state->classCache[i].index;
1137	0	break;
1138		}
1139		}
1140		}
1141		else {
1142	0	state->classCache[i].start = termStart;
1143	0	state->classCache[i].length = state->result->u.ucclass.kidlen;
1144	0	state->classCache[i].index = state->classCount;
1145	0	break;
1146		}
1147		}
1148	0	if (!foundCachedCopy)
1149	0	state->result->u.ucclass.index = state->classCount++;
1150		/*
1151		* Call calculateBitmapSize now as we want any errors it finds
1152		* to be reported during the parse phase, not at execution.
1153		*/
1154	0	if (!calculateBitmapSize(state, state->result, termStart, state->cp++))
1155	0	return JS_FALSE;
1156	0	state->progLength += 3; /* CLASS, <index> */
1157	0	break;
1158
1159		case '.':
1160	0	state->result = NewRENode(state, REOP_DOT);
1161	0	goto doSimple;
1162		case '*':
1163		case '+':
1164		case '?':
1165	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
1166		NULL, JSREPORT_ERROR,
1167		JSMSG_BAD_QUANTIFIER, state->cp - 1);
1168	0	return JS_FALSE;
1169		#if 0
1170		case '{':   /* balance '}' */
1171		/* Treat left-curly in a non-quantifier context as an error only
1172		* if it's followed immediately by a decimal digit.
1173		* This is an Perl extension.
1174		*/
1175		if ((state->cp != state->cpend) && JS7_ISDEC(*state->cp)) {
1176		js_ReportCompileErrorNumber(state->context, state->tokenStream,
1177		NULL, JSREPORT_ERROR,
1178		JSMSG_BAD_QUANTIFIER, state->cp - 1);
1179		return JS_FALSE;
1180		}
1181		/* fall thru... */
1182		#endif
1183		default:
1184	0	state->result = NewRENode(state, REOP_FLAT);
1185	0	if (!state->result)
1186	0	return JS_FALSE;
1187	0	state->result->u.flat.chr = c;
1188	0	state->result->u.flat.length = 1;
1189	0	state->result->kid = (void *)(state->cp - 1);
1190	0	state->progLength += 3;
1191	0	break;
1192		}
1193	0	return parseQuantifier(state);
1194		}
1195
1196		static JSBool
1197		parseQuantifier(CompilerState *state)
1198	0	{
1199	0	RENode *term;
1200	0	term = state->result;
1201	0	if (state->cp < state->cpend) {
1202	0	switch (*state->cp) {
1203		case '+':
1204	0	state->result = NewRENode(state, REOP_QUANT);
1205	0	if (!state->result)
1206	0	return JS_FALSE;
1207	0	state->result->u.range.min = 1;
1208	0	state->result->u.range.max = -1;
1209		/* <PLUS>, <next> ... <ENDCHILD> */
1210	0	state->progLength += 4;
1211	0	goto quantifier;
1212		case '*':
1213	0	state->result = NewRENode(state, REOP_QUANT);
1214	0	if (!state->result)
1215	0	return JS_FALSE;
1216	0	state->result->u.range.min = 0;
1217	0	state->result->u.range.max = -1;
1218		/* <STAR>, <next> ... <ENDCHILD> */
1219	0	state->progLength += 4;
1220	0	goto quantifier;
1221		case '?':
1222	0	state->result = NewRENode(state, REOP_QUANT);
1223	0	if (!state->result)
1224	0	return JS_FALSE;
1225	0	state->result->u.range.min = 0;
1226	0	state->result->u.range.max = 1;
1227		/* <OPT>, <next> ... <ENDCHILD> */
1228	0	state->progLength += 4;
1229	0	goto quantifier;
1230		case '{':       /* balance '}' */
1231		{
1232	0	intN err;
1233	0	intN min = 0;
1234	0	intN max = -1;
1235	0	jschar c;
1236	0	const jschar *errp = state->cp++;
1237
1238	0	c = *state->cp;
1239	0	if (JS7_ISDEC(c)) {
1240	0	++state->cp;
1241	0	min = getDecimalValue(c, state);
1242	0	c = *state->cp;
1243
1244	0	if ((min + 1) >> 16) {
1245	0	err = JSMSG_MIN_TOO_BIG;
1246	0	goto quantError;
1247		}
1248	0	if (c == ',') {
1249	0	c = *++state->cp;
1250	0	if (JS7_ISDEC(c)) {
1251	0	++state->cp;
1252	0	max = getDecimalValue(c, state);
1253	0	c = *state->cp;
1254	0	if ((max + 1) >> 16) {
1255	0	err = JSMSG_MAX_TOO_BIG;
1256	0	goto quantError;
1257		}
1258	0	if (min > max) {
1259	0	err = JSMSG_OUT_OF_ORDER;
1260	0	goto quantError;
1261		}
1262		}
1263		}
1264		else {
1265	0	max = min;
1266		}
1267	0	if (c == '}') {
1268	0	state->result = NewRENode(state, REOP_QUANT);
1269	0	if (!state->result)
1270	0	return JS_FALSE;
1271	0	state->result->u.range.min = min;
1272	0	state->result->u.range.max = max;
1273		/* QUANT, <min>, <max>, <next> ... <ENDCHILD> */
1274	0	state->progLength += 8;
1275	0	goto quantifier;
1276		}
1277		}
1278	0	state->cp = errp;
1279	0	return JS_TRUE;
1280		quantError:
1281	0	js_ReportCompileErrorNumber(state->context,
1282		state->tokenStream,
1283		NULL, JSREPORT_ERROR,
1284		err, errp);
1285	0	return JS_FALSE;
1286		}
1287		}
1288		}
1289	0	return JS_TRUE;
1290
1291		quantifier:
1292	0	++state->treeDepth;
1293	0	++state->cp;
1294	0	state->result->kid = term;
1295	0	if ((state->cp < state->cpend) && (*state->cp == '?')) {
1296	0	++state->cp;
1297	0	state->result->u.range.greedy = JS_FALSE;
1298		}
1299		else
1300	0	state->result->u.range.greedy = JS_TRUE;
1301	0	return JS_TRUE;
1302		}
1303
1304		#define CHECK_OFFSET(diff) (JS_ASSERT(((diff) >= -32768) && ((diff) <= 32767)))
1305		#define SET_OFFSET(pc,off) ((pc)[0] = JUMP_OFFSET_HI(off),                     \
1306		(pc)[1] = JUMP_OFFSET_LO(off))
1307		#define GET_OFFSET(pc)     ((int16)(((pc)[0] << 8) | (pc)[1]))
1308		#define OFFSET_LEN         (2)
1309		#define GET_ARG(pc)        GET_OFFSET(pc)
1310		#define SET_ARG(pc,arg)    SET_OFFSET(pc,arg)
1311		#define ARG_LEN            OFFSET_LEN
1312
1313		/*
1314		* Recursively generate bytecode for the tree rooted at t. Iteratively.
1315		*/
1316
1317		typedef struct {
1318		RENode *nextAlt;
1319		jsbytecode *nextAltFixup, *nextTermFixup, *endTermFixup;
1320		RENode *continueNode;
1321		REOp continueOp;
1322		} EmitStateStackEntry;
1323
1324		static jsbytecode *
1325		emitREBytecode(CompilerState *state, JSRegExp *re, intN treeDepth,
1326		jsbytecode *pc, RENode *t)
1327	0	{
1328	0	ptrdiff_t diff;
1329	0	RECharSet *charSet;
1330	0	EmitStateStackEntry *emitStateSP, *emitStateStack = NULL;
1331	0	REOp op;
1332
1333	0	if (treeDepth) {
1334	0	emitStateStack =
1335		(EmitStateStackEntry *)JS_malloc(state->context,
1336		sizeof(EmitStateStackEntry)
1337		* treeDepth);
1338	0	if (!emitStateStack)
1339	0	return NULL;
1340		}
1341	0	emitStateSP = emitStateStack;
1342	0	op = t->op;
1343
1344	0	while (JS_TRUE) {
1345	0	*pc++ = op;
1346	0	switch (op) {
1347		case REOP_EMPTY:
1348	0	--pc;
1349	0	break;
1350
1351		case REOP_ALTPREREQ2:
1352		case REOP_ALTPREREQ:
1353	0	JS_ASSERT(emitStateSP);
1354	0	emitStateSP->endTermFixup = pc;
1355	0	pc += OFFSET_LEN;
1356	0	SET_ARG(pc, t->u.altprereq.ch1);
1357	0	pc += ARG_LEN;
1358	0	SET_ARG(pc, t->u.altprereq.ch2);
1359	0	pc += ARG_LEN;
1360
1361	0	emitStateSP->nextAltFixup = pc;    /* address of next alternate */
1362	0	pc += OFFSET_LEN;
1363
1364	0	emitStateSP->continueNode = t;
1365	0	emitStateSP->continueOp = REOP_JUMP;
1366	0	++emitStateSP;
1367	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1368	0	t = (RENode *)(t->kid);
1369	0	op = t->op;
1370	0	continue;
1371
1372		case REOP_JUMP:
1373	0	emitStateSP->nextTermFixup = pc;    /* address of following term */
1374	0	pc += OFFSET_LEN;
1375	0	diff = pc - emitStateSP->nextAltFixup;
1376	0	CHECK_OFFSET(diff);
1377	0	SET_OFFSET(emitStateSP->nextAltFixup, diff);
1378	0	emitStateSP->continueOp = REOP_ENDALT;
1379	0	++emitStateSP;
1380	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1381	0	t = (RENode *)(t->u.kid2);
1382	0	op = t->op;
1383	0	continue;
1384
1385		case REOP_ENDALT:
1386	0	diff = pc - emitStateSP->nextTermFixup;
1387	0	CHECK_OFFSET(diff);
1388	0	SET_OFFSET(emitStateSP->nextTermFixup, diff);
1389	0	if (t->op != REOP_ALT) {
1390	0	diff = pc - emitStateSP->endTermFixup;
1391	0	CHECK_OFFSET(diff);
1392	0	SET_OFFSET(emitStateSP->endTermFixup, diff);
1393		}
1394	0	break;
1395
1396		case REOP_ALT:
1397	0	JS_ASSERT(emitStateSP);
1398	0	emitStateSP->nextAltFixup = pc; /* address of pointer to next alternate */
1399	0	pc += OFFSET_LEN;
1400	0	emitStateSP->continueNode = t;
1401	0	emitStateSP->continueOp = REOP_JUMP;
1402	0	++emitStateSP;
1403	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1404	0	t = (RENode *)(t->kid);
1405	0	op = t->op;
1406	0	continue;
1407
1408		case REOP_FLAT:
1409		/*
1410		* Consecutize FLAT's if possible.
1411		*/
1412	0	if (t->kid) {
1413	0	while (t->next && (t->next->op == REOP_FLAT)
1414		&& (((jschar*)(t->kid) + t->u.flat.length)
1415		== (jschar*)(t->next->kid))) {
1416	0	t->u.flat.length += t->next->u.flat.length;
1417	0	t->next = t->next->next;
1418		}
1419		}
1420	0	if (t->kid && (t->u.flat.length > 1)) {
1421	0	if (state->flags & JSREG_FOLD)
1422	0	pc[-1] = REOP_FLATi;
1423		else
1424	0	pc[-1] = REOP_FLAT;
1425	0	SET_ARG(pc, (jschar *)(t->kid) - state->cpbegin);
1426	0	pc += ARG_LEN;
1427	0	SET_ARG(pc, t->u.flat.length);
1428	0	pc += ARG_LEN;
1429		}
1430		else {
1431	0	if (t->u.flat.chr < 256) {
1432	0	if (state->flags & JSREG_FOLD)
1433	0	pc[-1] = REOP_FLAT1i;
1434		else
1435	0	pc[-1] = REOP_FLAT1;
1436	0	*pc++ = (jsbytecode)(t->u.flat.chr);
1437		}
1438		else {
1439	0	if (state->flags & JSREG_FOLD)
1440	0	pc[-1] = REOP_UCFLAT1i;
1441		else
1442	0	pc[-1] = REOP_UCFLAT1;
1443	0	SET_ARG(pc, t->u.flat.chr);
1444	0	pc += ARG_LEN;
1445		}
1446		}
1447	0	break;
1448
1449		case REOP_LPAREN:
1450	0	JS_ASSERT(emitStateSP);
1451	0	SET_ARG(pc, t->u.parenIndex);
1452	0	pc += ARG_LEN;
1453	0	emitStateSP->continueNode = t;
1454	0	emitStateSP->continueOp = REOP_RPAREN;
1455	0	++emitStateSP;
1456	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1457	0	t = (RENode *)(t->kid);
1458	0	op = t->op;
1459	0	continue;
1460		case REOP_RPAREN:
1461	0	SET_ARG(pc, t->u.parenIndex);
1462	0	pc += ARG_LEN;
1463	0	break;
1464
1465		case REOP_BACKREF:
1466	0	SET_ARG(pc, t->u.parenIndex);
1467	0	pc += ARG_LEN;
1468	0	break;
1469		case REOP_ASSERT:
1470	0	JS_ASSERT(emitStateSP);
1471	0	emitStateSP->nextTermFixup = pc;
1472	0	pc += OFFSET_LEN;
1473	0	emitStateSP->continueNode = t;
1474	0	emitStateSP->continueOp = REOP_ASSERTTEST;
1475	0	++emitStateSP;
1476	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1477	0	t = (RENode *)(t->kid);
1478	0	op = t->op;
1479	0	continue;
1480		case REOP_ASSERTTEST:
1481		case REOP_ASSERTNOTTEST:
1482	0	diff = pc - emitStateSP->nextTermFixup;
1483	0	CHECK_OFFSET(diff);
1484	0	SET_OFFSET(emitStateSP->nextTermFixup, diff);
1485	0	break;
1486		case REOP_ASSERT_NOT:
1487	0	JS_ASSERT(emitStateSP);
1488	0	emitStateSP->nextTermFixup = pc;
1489	0	pc += OFFSET_LEN;
1490	0	emitStateSP->continueNode = t;
1491	0	emitStateSP->continueOp = REOP_ASSERTNOTTEST;
1492	0	++emitStateSP;
1493	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1494	0	t = (RENode *)(t->kid);
1495	0	op = t->op;
1496	0	continue;
1497		case REOP_QUANT:
1498	0	JS_ASSERT(emitStateSP);
1499	0	if ((t->u.range.min == 0) && (t->u.range.max == (uint16)(-1)))
1500	0	pc[-1] = (t->u.range.greedy) ? REOP_STAR : REOP_MINIMALSTAR;
1501		else
1502	0	if ((t->u.range.min == 0) && (t->u.range.max == 1))
1503	0	pc[-1] = (t->u.range.greedy) ? REOP_OPT : REOP_MINIMALOPT;
1504		else
1505	0	if ((t->u.range.min == 1) && (t->u.range.max == (uint16)(-1)))
1506	0	pc[-1] = (t->u.range.greedy) ? REOP_PLUS : REOP_MINIMALPLUS;
1507		else {
1508	0	if (!t->u.range.greedy) pc[-1] = REOP_MINIMALQUANT;
1509	0	SET_ARG(pc, t->u.range.min);
1510	0	pc += ARG_LEN;
1511	0	SET_ARG(pc, t->u.range.max);
1512	0	pc += ARG_LEN;
1513		}
1514	0	emitStateSP->nextTermFixup = pc;
1515	0	pc += OFFSET_LEN;
1516	0	emitStateSP->continueNode = t;
1517	0	emitStateSP->continueOp = REOP_ENDCHILD;
1518	0	++emitStateSP;
1519	0	JS_ASSERT((emitStateSP - emitStateStack) <= treeDepth);
1520	0	t = (RENode *)(t->kid);
1521	0	op = t->op;
1522	0	continue;
1523		case REOP_ENDCHILD:
1524	0	diff = pc - emitStateSP->nextTermFixup;
1525	0	CHECK_OFFSET(diff);
1526	0	SET_OFFSET(emitStateSP->nextTermFixup, diff);
1527	0	break;
1528		case REOP_CLASS:
1529	0	if (!t->u.ucclass.sense)
1530	0	pc[-1] = REOP_NCLASS;
1531	0	SET_ARG(pc, t->u.ucclass.index);
1532	0	pc += ARG_LEN;
1533	0	charSet = &re->classList[t->u.ucclass.index];
1534	0	charSet->converted = JS_FALSE;
1535	0	charSet->length = t->u.ucclass.bmsize;
1536	0	charSet->u.src.startIndex = t->u.ucclass.startIndex;
1537	0	charSet->u.src.length = t->u.ucclass.kidlen;
1538	0	charSet->sense = t->u.ucclass.sense;
1539		break;
1540		default:
1541	0	break;
1542		}
1543	0	t = t->next;
1544	0	if (t == NULL) {
1545	0	if (emitStateSP == emitStateStack)
1546	0	break;
1547	0	--emitStateSP;
1548	0	t = emitStateSP->continueNode;
1549	0	op = emitStateSP->continueOp;
1550		}
1551		else
1552	0	op = t->op;
1553		}
1554	0	if (emitStateStack)
1555	0	JS_free(state->context, emitStateStack);
1556	0	return pc;
1557		}
1558
1559
1560		JSRegExp *
1561		js_NewRegExp(JSContext *cx, JSTokenStream *ts,
1562		JSString *str, uintN flags, JSBool flat)
1563	0	{
1564	0	JSRegExp *re;
1565	0	void *mark;
1566	0	CompilerState state;
1567	0	size_t resize;
1568	0	jsbytecode *endPC;
1569	0	uint32 i;
1570	0	size_t len;
1571
1572	0	re = NULL;
1573	0	mark = JS_ARENA_MARK(&cx->tempPool);
1574
1575	0	state.context = cx;
1576	0	state.tokenStream = ts;
1577	0	state.cpbegin = state.cp = JSSTRING_CHARS(str);
1578	0	state.cpend = state.cp + JSSTRING_LENGTH(str);
1579	0	state.flags = flags;
1580	0	state.parenCount = 0;
1581	0	state.classCount = 0;
1582	0	state.progLength = 0;
1583	0	state.treeDepth = 0;
1584	0	for (i = 0; i < CLASS_CACHE_SIZE; i++)
1585	0	state.classCache[i].start = NULL;
1586
1587	0	len = JSSTRING_LENGTH(str);
1588
1589	0	if (len != 0 && flat) {
1590	0	state.result = NewRENode(&state, REOP_FLAT);
1591	0	state.result->u.flat.chr = *state.cpbegin;
1592	0	state.result->u.flat.length = JSSTRING_LENGTH(str);
1593	0	state.result->kid = (void *)(state.cpbegin);
1594	0	state.progLength += 5;
1595		}
1596		else {
1597	0	if (!parseRegExp(&state))
1598	0	goto out;
1599		}
1600	0	resize = sizeof *re + state.progLength + 1;
1601	0	re = (JSRegExp *) JS_malloc(cx, JS_ROUNDUP(resize, sizeof(jsword)));
1602	0	if (!re)
1603	0	goto out;
1604
1605	0	re->classCount = state.classCount;
1606	0	if (state.classCount) {
1607	0	re->classList = (RECharSet *)JS_malloc(cx, sizeof(RECharSet)
1608		* state.classCount);
1609	0	if (!re->classList)
1610	0	goto out;
1611		}
1612		else
1613	0	re->classList = NULL;
1614	0	endPC = emitREBytecode(&state, re, state.treeDepth, re->program, state.result);
1615	0	if (!endPC) {
1616	0	re = NULL;
1617	0	goto out;
1618		}
1619	0	*endPC++ = REOP_END;
1620	0	JS_ASSERT(endPC <= (re->program + (state.progLength + 1)));
1621
1622	0	re->nrefs = 1;
1623	0	re->parenCount = state.parenCount;
1624	0	re->flags = flags;
1625	0	re->source = str;
1626
1627		out:
1628	0	JS_ARENA_RELEASE(&cx->tempPool, mark);
1629	0	return re;
1630		}
1631
1632		JSRegExp *
1633		js_NewRegExpOpt(JSContext *cx, JSTokenStream *ts,
1634		JSString *str, JSString *opt, JSBool flat)
1635	0	{
1636	0	uintN flags;
1637	0	jschar *s;
1638	0	size_t i, n;
1639	0	char charBuf[2];
1640
1641	0	flags = 0;
1642	0	if (opt) {
1643	0	s = JSSTRING_CHARS(opt);
1644	0	for (i = 0, n = JSSTRING_LENGTH(opt); i < n; i++) {
1645	0	switch (s[i]) {
1646		case 'g':
1647	0	flags |= JSREG_GLOB;
1648	0	break;
1649		case 'i':
1650	0	flags |= JSREG_FOLD;
1651	0	break;
1652		case 'm':
1653	0	flags |= JSREG_MULTILINE;
1654	0	break;
1655		default:
1656	0	charBuf[0] = (char)s[i];
1657	0	charBuf[1] = '\0';
1658	0	js_ReportCompileErrorNumber(cx, ts, NULL, JSREPORT_ERROR,
1659		JSMSG_BAD_FLAG, charBuf);
1660	0	return NULL;
1661		}
1662		}
1663		}
1664	0	return js_NewRegExp(cx, ts, str, flags, flat);
1665		}
1666
1667
1668		#define HOLD_REGEXP(cx, re) JS_ATOMIC_INCREMENT(&(re)->nrefs)
1669		#define DROP_REGEXP(cx, re) js_DestroyRegExp(cx, re)
1670
1671		/*
1672		* Save the current state of the match - the position in the input
1673		* text as well as the position in the bytecode. The state of any
1674		* parent expressions is also saved (preceding state).
1675		* Contents of parenCount parentheses from parenIndex are also saved.
1676		*/
1677		static REBackTrackData *
1678		pushBackTrackState(REGlobalData *gData, REOp op,
1679		jsbytecode *target, REMatchState *x, const jschar *cp,
1680		intN parenIndex, intN parenCount)
1681	0	{
1682	0	intN i;
1683		REBackTrackData *result
1684	0	= (REBackTrackData *)((char *)(gData->backTrackSP) + gData->cursz);
1685
1686	0	size_t sz = sizeof(REBackTrackData)
1687		+ gData->stateStackTop * sizeof(REProgState)
1688	0	+ parenCount * sizeof(RECapture);
1689
1690
1691	0	if (((char *)result + sz)
1692		> (char *)gData->backTrackStack + gData->maxBackTrack) {
1693	0	ptrdiff_t offset = (char *)result - (char *)gData->backTrackStack;
1694	0	gData->backTrackStack
1695		= (REBackTrackData *)JS_ArenaGrow(&gData->pool,
1696		gData->backTrackStack,
1697		gData->maxBackTrack,
1698		gData->maxBackTrack);
1699	0	gData->maxBackTrack <<= 1;
1700	0	if (!gData->backTrackStack)
1701	0	return NULL;
1702	0	result = (REBackTrackData *)((char *)gData->backTrackStack + offset);
1703		}
1704	0	gData->backTrackSP = result;
1705	0	result->sz = gData->cursz;
1706	0	gData->cursz = sz;
1707
1708	0	result->backtrack_op = op;
1709	0	result->backtrack_pc = target;
1710	0	result->cp = cp;
1711	0	result->parenCount = parenCount;
1712
1713	0	result->precedingStateTop = gData->stateStackTop;
1714	0	JS_ASSERT(gData->stateStackTop);
1715	0	memcpy(result + 1, gData->stateStack,
1716		sizeof(REProgState) * result->precedingStateTop);
1717
1718	0	if (parenCount != -1) {
1719	0	result->parenIndex = parenIndex;
1720	0	memcpy((char *)(result + 1)
1721		+ sizeof(REProgState) * result->precedingStateTop,
1722		&x->parens[parenIndex],
1723		sizeof(RECapture) * parenCount);
1724	0	for (i = 0; i < parenCount; i++)
1725	0	x->parens[parenIndex + i].index = -1;
1726		}
1727
1728	0	return result;
1729		}
1730
1731
1732		/*
1733		*   Consecutive literal characters.
1734		*/
1735		#if 0
1736		static REMatchState *
1737		flatNMatcher(REGlobalData *gData, REMatchState *x, jschar *matchChars,
1738		intN length)
1739		{
1740		intN i;
1741		if ((x->cp + length) > gData->cpend)
1742		return NULL;
1743		for (i = 0; i < length; i++) {
1744		if (matchChars[i] != x->cp[i])
1745		return NULL;
1746		}
1747		x->cp += length;
1748		return x;
1749		}
1750		#endif
1751
1752		static REMatchState *
1753		flatNIMatcher(REGlobalData *gData, REMatchState *x, jschar *matchChars,
1754		intN length)
1755	0	{
1756	0	intN i;
1757	0	if ((x->cp + length) > gData->cpend)
1758	0	return NULL;
1759	0	for (i = 0; i < length; i++) {
1760	0	if (upcase(matchChars[i]) != upcase(x->cp[i]))
1761	0	return NULL;
1762		}
1763	0	x->cp += length;
1764	0	return x;
1765		}
1766
1767		/*
1768		* 1. Evaluate DecimalEscape to obtain an EscapeValue E.
1769		* 2. If E is not a character then go to step 6.
1770		* 3. Let ch be E's character.
1771		* 4. Let A be a one-element RECharSet containing the character ch.
1772		* 5. Call CharacterSetMatcher(A, false) and return its Matcher result.
1773		* 6. E must be an integer. Let n be that integer.
1774		* 7. If n=0 or n>NCapturingParens then throw a SyntaxError exception.
1775		* 8. Return an internal Matcher closure that takes two arguments, a State x
1776		*    and a Continuation c, and performs the following:
1777		*     1. Let cap be x's captures internal array.
1778		*     2. Let s be cap[n].
1779		*     3. If s is undefined, then call c(x) and return its result.
1780		*     4. Let e be x's endIndex.
1781		*     5. Let len be s's length.
1782		*     6. Let f be e+len.
1783		*     7. If f>InputLength, return failure.
1784		*     8. If there exists an integer i between 0 (inclusive) and len (exclusive)
1785		*        such that Canonicalize(s[i]) is not the same character as
1786		*        Canonicalize(Input [e+i]), then return failure.
1787		*     9. Let y be the State (f, cap).
1788		*     10. Call c(y) and return its result.
1789		*/
1790		static REMatchState *
1791		backrefMatcher(REGlobalData *gData, REMatchState *x, uintN parenIndex)
1792	0	{
1793	0	uintN len;
1794	0	uintN i;
1795	0	const jschar *parenContent;
1796	0	RECapture *s = &x->parens[parenIndex];
1797	0	if (s->index == -1)
1798	0	return x;
1799
1800	0	len = s->length;
1801	0	if ((x->cp + len) > gData->cpend)
1802	0	return NULL;
1803
1804	0	parenContent = &gData->cpbegin[s->index];
1805	0	if (gData->regexp->flags & JSREG_FOLD) {
1806	0	for (i = 0; i < len; i++) {
1807	0	if (upcase(parenContent[i]) != upcase(x->cp[i]))
1808	0	return NULL;
1809		}
1810		}
1811		else {
1812	0	for (i = 0; i < len; i++) {
1813	0	if (parenContent[i] != x->cp[i])
1814	0	return NULL;
1815		}
1816		}
1817	0	x->cp += len;
1818	0	return x;
1819		}
1820
1821
1822		/* Add a single character to the RECharSet */
1823		static void
1824		addCharacterToCharSet(RECharSet *cs, jschar c)
1825	0	{
1826	0	uintN byteIndex = (uintN)(c / 8);
1827	0	JS_ASSERT(c <= cs->length);
1828	0	cs->u.bits[byteIndex] |= 1 << (c & 0x7);
1829		}
1830
1831
1832		/* Add a character range, c1 to c2 (inclusive) to the RECharSet */
1833		static void
1834		addCharacterRangeToCharSet(RECharSet *cs, jschar c1, jschar c2)
1835	0	{
1836	0	uintN i;
1837
1838	0	uintN byteIndex1 = (uintN)(c1 / 8);
1839	0	uintN byteIndex2 = (uintN)(c2 / 8);
1840
1841	0	JS_ASSERT((c2 <= cs->length) && (c1 <= c2));
1842
1843	0	c1 &= 0x7;
1844	0	c2 &= 0x7;
1845
1846	0	if (byteIndex1 == byteIndex2)
1847	0	cs->u.bits[byteIndex1] |= ((uint8)(0xFF) >> (7 - (c2 - c1))) << c1;
1848		else {
1849	0	cs->u.bits[byteIndex1] |= 0xFF << c1;
1850	0	for (i = byteIndex1 + 1; i < byteIndex2; i++)
1851	0	cs->u.bits[i] = 0xFF;
1852	0	cs->u.bits[byteIndex2] |= (uint8)(0xFF) >> (7 - c2);
1853		}
1854		}
1855
1856		/* Compile the source of the class into a RECharSet */
1857		static JSBool
1858		processCharSet(REGlobalData *gData, RECharSet *charSet)
1859	0	{
1860	0	const jschar *src = JSSTRING_CHARS(gData->regexp->source)
1861	0	+ charSet->u.src.startIndex;
1862	0	const jschar *end = src + charSet->u.src.length;
1863
1864	0	jschar rangeStart, thisCh;
1865	0	uintN byteLength;
1866	0	jschar c;
1867	0	uintN n;
1868	0	intN nDigits;
1869	0	intN i;
1870	0	JSBool inRange = JS_FALSE;
1871
1872	0	JS_ASSERT(!charSet->converted);
1873	0	charSet->converted = JS_TRUE;
1874
1875	0	byteLength = (charSet->length / 8) + 1;
1876	0	charSet->u.bits = (uint8 *)JS_malloc(gData->cx, byteLength);
1877	0	if (!charSet->u.bits)
1878	0	return JS_FALSE;
1879	0	memset(charSet->u.bits, 0, byteLength);
1880
1881	0	if (src == end)
1882	0	return JS_TRUE;
1883
1884	0	if (*src == '^') {
1885	0	JS_ASSERT(charSet->sense == JS_FALSE);
1886	0	++src;
1887		}
1888		else
1889	0	JS_ASSERT(charSet->sense == JS_TRUE);
1890
1891
1892	0	while (src != end) {
1893	0	switch (*src) {
1894		case '\\':
1895	0	++src;
1896	0	c = *src++;
1897	0	switch (c) {
1898		case 'b':
1899	0	thisCh = 0x8;
1900	0	break;
1901		case 'f':
1902	0	thisCh = 0xC;
1903	0	break;
1904		case 'n':
1905	0	thisCh = 0xA;
1906	0	break;
1907		case 'r':
1908	0	thisCh = 0xD;
1909	0	break;
1910		case 't':
1911	0	thisCh = 0x9;
1912	0	break;
1913		case 'v':
1914	0	thisCh = 0xB;
1915	0	break;
1916		case 'c':
1917	0	if (((src + 1) < end) && JS_ISWORD(src[1]))
1918	0	thisCh = (jschar)(*src++ & 0x1F);
1919		else {
1920	0	--src;
1921	0	thisCh = '\\';
1922		}
1923	0	break;
1924		case 'x':
1925	0	nDigits = 2;
1926	0	goto lexHex;
1927		case 'u':
1928	0	nDigits = 4;
1929		lexHex:
1930	0	n = 0;
1931	0	for (i = 0; (i < nDigits) && (src < end); i++) {
1932	0	uintN digit;
1933	0	c = *src++;
1934	0	if (!isASCIIHexDigit(c, &digit)) {
1935		/*
1936		* Back off to accepting the original '\'
1937		* as a literal
1938		*/
1939	0	src -= (i + 1);
1940	0	n = '\\';
1941	0	break;
1942		}
1943	0	n = (n << 4) | digit;
1944		}
1945	0	thisCh = (jschar)(n);
1946	0	break;
1947		case '0':
1948		case '1':
1949		case '2':
1950		case '3':
1951		case '4':
1952		case '5':
1953		case '6':
1954		case '7':
1955		/*
1956		*  This is a non-ECMA extension - decimal escapes (in this
1957		*  case, octal!) are supposed to be an error inside class
1958		*  ranges, but supported here for backwards compatibility.
1959		*
1960		*/
1961	0	n = JS7_UNDEC(c);
1962	0	c = *src;
1963	0	if ('0' <= c && c <= '7') {
1964	0	src++;
1965	0	n = 8 * n + JS7_UNDEC(c);
1966	0	c = *src;
1967	0	if ('0' <= c && c <= '7') {
1968	0	src++;
1969	0	i = 8 * n + JS7_UNDEC(c);
1970	0	if (i <= 0377)
1971	0	n = i;
1972		else
1973	0	src--;
1974		}
1975		}
1976	0	thisCh = (jschar)(n);
1977	0	break;
1978
1979		case 'd':
1980	0	addCharacterRangeToCharSet(charSet, '0', '9');
1981	0	continue;   /* don't need range processing */
1982		case 'D':
1983	0	addCharacterRangeToCharSet(charSet, 0, '0' - 1);
1984	0	addCharacterRangeToCharSet(charSet, (jschar)('9' + 1),
1985		(jschar)(charSet->length));
1986	0	continue;
1987		case 's':
1988	0	for (i = (intN)(charSet->length); i >= 0; i--)
1989	0	if (JS_ISSPACE(i))
1990	0	addCharacterToCharSet(charSet, (jschar)(i));
1991	0	continue;
1992		case 'S':
1993	0	for (i = (intN)(charSet->length); i >= 0; i--)
1994	0	if (!JS_ISSPACE(i))
1995	0	addCharacterToCharSet(charSet, (jschar)(i));
1996	0	continue;
1997		case 'w':
1998	0	for (i = (intN)(charSet->length); i >= 0; i--)
1999	0	if (JS_ISWORD(i))
2000	0	addCharacterToCharSet(charSet, (jschar)(i));
2001	0	continue;
2002		case 'W':
2003	0	for (i = (intN)(charSet->length); i >= 0; i--)
2004	0	if (!JS_ISWORD(i))
2005	0	addCharacterToCharSet(charSet, (jschar)(i));
2006	0	continue;
2007		default:
2008	0	thisCh = c;
2009	0	break;
2010
2011		}
2012	0	break;
2013
2014		default:
2015	0	thisCh = *src++;
2016	0	break;
2017
2018		}
2019	0	if (inRange) {
2020	0	if (gData->regexp->flags & JSREG_FOLD) {
2021	0	addCharacterRangeToCharSet(charSet, upcase(rangeStart),
2022		upcase(thisCh));
2023	0	addCharacterRangeToCharSet(charSet, downcase(rangeStart),
2024		downcase(thisCh));
2025		} else {
2026	0	addCharacterRangeToCharSet(charSet, rangeStart, thisCh);
2027		}
2028	0	inRange = JS_FALSE;
2029		}
2030		else {
2031	0	if (gData->regexp->flags & JSREG_FOLD) {
2032	0	addCharacterToCharSet(charSet, upcase(thisCh));
2033	0	addCharacterToCharSet(charSet, downcase(thisCh));
2034		} else {
2035	0	addCharacterToCharSet(charSet, thisCh);
2036		}
2037	0	if (src < (end - 1)) {
2038	0	if (*src == '-') {
2039	0	++src;
2040	0	inRange = JS_TRUE;
2041	0	rangeStart = thisCh;
2042		}
2043		}
2044		}
2045		}
2046	0	return JS_TRUE;
2047		}
2048
2049		void
2050		js_DestroyRegExp(JSContext *cx, JSRegExp *re)
2051	0	{
2052	0	uintN i;
2053	0	if (JS_ATOMIC_DECREMENT(&re->nrefs) == 0) {
2054	0	if (re->classList) {
2055	0	for (i = 0; i < re->classCount; i++) {
2056	0	if (re->classList[i].converted)
2057	0	JS_free(cx, re->classList[i].u.bits);
2058	0	re->classList[i].u.bits = NULL;
2059		}
2060	0	JS_free(cx, re->classList);
2061		}
2062	0	JS_free(cx, re);
2063		}
2064		}
2065
2066		static JSBool
2067		reallocStateStack(REGlobalData *gData)
2068	0	{
2069	0	size_t sz = sizeof(REProgState) * gData->maxStateStack;
2070	0	gData->maxStateStack <<= 1;
2071	0	gData->stateStack
2072		= (REProgState *)JS_ArenaGrow(&gData->pool, gData->stateStack, sz, sz);
2073	0	if (!gData->stateStack) {
2074	0	gData->ok = JS_FALSE;
2075	0	return JS_FALSE;
2076		}
2077	0	return JS_TRUE;
2078		}
2079
2080		/*
2081		*   Apply the current op against the given input to see if
2082		*   it's going to match or fail. Return false if we don't
2083		*   get a match, true if we do and update the state of the
2084		*   input and pc if the update flag is true.
2085		*/
2086		static REMatchState *simpleMatch(REGlobalData *gData, REMatchState *x,
2087		REOp op, jsbytecode **startpc, JSBool update)
2088	0	{
2089	0	REMatchState *result = NULL;
2090	0	jschar matchCh;
2091	0	intN parenIndex;
2092	0	intN offset, length, index;
2093	0	jsbytecode *pc = *startpc;  /* pc has already been incremented past op */
2094	0	jschar *source;
2095	0	const jschar *startcp = x->cp;
2096	0	jschar ch;
2097	0	RECharSet *charSet;
2098
2099
2100	0	switch (op) {
2101		default:
2102	0	JS_ASSERT(JS_FALSE);
2103		case REOP_BOL:
2104	0	if (x->cp != gData->cpbegin) {
2105	0	if (gData->cx->regExpStatics.multiline ||
2106		(gData->regexp->flags & JSREG_MULTILINE)) {
2107	0	if (!RE_IS_LINE_TERM(x->cp[-1]))
2108	0	break;
2109		}
2110		else
2111	0	break;
2112		}
2113	0	result = x;
2114	0	break;
2115		case REOP_EOL:
2116	0	if (x->cp != gData->cpend) {
2117	0	if (gData->cx->regExpStatics.multiline ||
2118		(gData->regexp->flags & JSREG_MULTILINE)) {
2119	0	if (!RE_IS_LINE_TERM(*x->cp))
2120	0	break;
2121		}
2122		else
2123	0	break;
2124		}
2125	0	result = x;
2126	0	break;
2127		case REOP_WBDRY:
2128	0	if ((x->cp == gData->cpbegin || !JS_ISWORD(x->cp[-1]))
2129		^ !((x->cp != gData->cpend) && JS_ISWORD(*x->cp)))
2130	0	result = x;
2131	0	break;
2132		case REOP_WNONBDRY:
2133	0	if ((x->cp == gData->cpbegin || !JS_ISWORD(x->cp[-1]))
2134		^ ((x->cp != gData->cpend) && JS_ISWORD(*x->cp)))
2135	0	result = x;
2136	0	break;
2137		case REOP_DOT:
2138	0	if (x->cp != gData->cpend && !RE_IS_LINE_TERM(*x->cp)) {
2139	0	result = x;
2140	0	result->cp++;
2141		}
2142	0	break;
2143		case REOP_DIGIT:
2144	0	if (x->cp != gData->cpend && JS_ISDIGIT(*x->cp)) {
2145	0	result = x;
2146	0	result->cp++;
2147		}
2148	0	break;
2149		case REOP_NONDIGIT:
2150	0	if (x->cp != gData->cpend && !JS_ISDIGIT(*x->cp)) {
2151	0	result = x;
2152	0	result->cp++;
2153		}
2154	0	break;
2155		case REOP_ALNUM:
2156	0	if (x->cp != gData->cpend && JS_ISWORD(*x->cp)) {
2157	0	result = x;
2158	0	result->cp++;
2159		}
2160	0	break;
2161		case REOP_NONALNUM:
2162	0	if (x->cp != gData->cpend && !JS_ISWORD(*x->cp)) {
2163	0	result = x;
2164	0	result->cp++;
2165		}
2166	0	break;
2167		case REOP_SPACE:
2168	0	if (x->cp != gData->cpend && JS_ISSPACE(*x->cp)) {
2169	0	result = x;
2170	0	result->cp++;
2171		}
2172	0	break;
2173		case REOP_NONSPACE:
2174	0	if (x->cp != gData->cpend && !JS_ISSPACE(*x->cp)) {
2175	0	result = x;
2176	0	result->cp++;
2177		}
2178	0	break;
2179		case REOP_BACKREF:
2180	0	parenIndex = GET_ARG(pc);
2181	0	pc += ARG_LEN;
2182	0	result = backrefMatcher(gData, x, parenIndex);
2183	0	break;
2184		case REOP_FLAT:
2185	0	offset = GET_ARG(pc);
2186	0	pc += ARG_LEN;
2187	0	length = GET_ARG(pc);
2188	0	pc += ARG_LEN;
2189	0	source = JSSTRING_CHARS(gData->regexp->source) + offset;
2190	0	if ((x->cp + length) <= gData->cpend) {
2191	0	for (index = 0; index < length; index++) {
2192	0	if (source[index] != x->cp[index])
2193	0	return NULL;
2194		}
2195	0	x->cp += length;
2196	0	result = x;
2197		}
2198	0	break;
2199		case REOP_FLAT1:
2200	0	matchCh = *pc++;
2201	0	if ((x->cp != gData->cpend) && (*x->cp == matchCh)) {
2202	0	result = x;
2203	0	result->cp++;
2204		}
2205	0	break;
2206		case REOP_FLATi:
2207	0	offset = GET_ARG(pc);
2208	0	pc += ARG_LEN;
2209	0	length = GET_ARG(pc);
2210	0	pc += ARG_LEN;
2211	0	source = JSSTRING_CHARS(gData->regexp->source);
2212	0	result = flatNIMatcher(gData, x, source + offset, length);
2213	0	break;
2214		case REOP_FLAT1i:
2215	0	matchCh = *pc++;
2216	0	if ((x->cp != gData->cpend) && (upcase(*x->cp) == upcase(matchCh))) {
2217	0	result = x;
2218	0	result->cp++;
2219		}
2220	0	break;
2221		case REOP_UCFLAT1:
2222	0	matchCh = GET_ARG(pc);
2223	0	pc += ARG_LEN;
2224	0	if ((x->cp != gData->cpend) && (*x->cp == matchCh)) {
2225	0	result = x;
2226	0	result->cp++;
2227		}
2228	0	break;
2229		case REOP_UCFLAT1i:
2230	0	matchCh = GET_ARG(pc);
2231	0	pc += ARG_LEN;
2232	0	if ((x->cp != gData->cpend) && (upcase(*x->cp) == upcase(matchCh))) {
2233	0	result = x;
2234	0	result->cp++;
2235		}
2236	0	break;
2237		case REOP_CLASS:
2238	0	index = GET_ARG(pc);
2239	0	pc += ARG_LEN;
2240	0	if (x->cp != gData->cpend) {
2241	0	charSet = &gData->regexp->classList[index];
2242	0	JS_ASSERT(charSet->converted);
2243	0	ch = *x->cp;
2244	0	index = ch / 8;
2245	0	if ((charSet->length != 0) &&
2246		( (ch <= charSet->length)
2247		&& ((charSet->u.bits[index] & (1 << (ch & 0x7))) != 0) )) {
2248	0	result = x;
2249	0	result->cp++;
2250		}
2251		}
2252	0	break;
2253		case REOP_NCLASS:
2254	0	index = GET_ARG(pc);
2255	0	pc += ARG_LEN;
2256	0	if (x->cp != gData->cpend) {
2257	0	charSet = &gData->regexp->classList[index];
2258	0	JS_ASSERT(charSet->converted);
2259	0	ch = *x->cp;
2260	0	index = ch / 8;
2261	0	if ((charSet->length == 0) ||
2262		( (ch > charSet->length)
2263		|| ((charSet->u.bits[index] & (1 << (ch & 0x7))) == 0) )) {
2264	0	result = x;
2265	0	result->cp++;
2266		}
2267		}
2268	0	break;
2269		}
2270	0	if (result != NULL) {
2271	0	if (update)
2272	0	*startpc = pc;
2273		else
2274	0	x->cp = startcp;
2275	0	return result;
2276		}
2277	0	x->cp = startcp;
2278	0	return NULL;
2279		}
2280
2281		static REMatchState *
2282		executeREBytecode(REGlobalData *gData, REMatchState *x)
2283	0	{
2284	0	REMatchState *result;
2285	0	REBackTrackData *backTrackData;
2286	0	intN offset;
2287	0	jsbytecode *nextpc;
2288	0	REOp nextop;
2289	0	RECapture *cap;
2290	0	REProgState *curState;
2291	0	const jschar *startcp;
2292	0	uintN parenIndex, k;
2293	0	uintN parenSoFar = 0;
2294
2295	0	jschar matchCh1, matchCh2;
2296	0	RECharSet *charSet;
2297
2298	0	JSBool anchor;
2299	0	jsbytecode *pc = gData->regexp->program;
2300	0	REOp op = (REOp)(*pc++);
2301
2302		/*
2303		*   If the first node is a simple match, step the index into
2304		*   the string until that match is made, or fail if it can't be
2305		*   found at all.
2306		*/
2307	0	if (REOP_IS_SIMPLE(op)) {
2308	0	anchor = JS_FALSE;
2309	0	while (x->cp <= gData->cpend) {
2310	0	nextpc = pc;    /* reset back to start each time */
2311	0	result = simpleMatch(gData, x, op, &nextpc, JS_TRUE);
2312	0	if (result) {
2313	0	anchor = JS_TRUE;
2314	0	x = result;
2315	0	pc = nextpc;    /* accept skip to next opcode */
2316	0	op = (REOp)(*pc++);
2317	0	break;
2318		}
2319		else {
2320	0	gData->skipped++;
2321	0	x->cp++;
2322		}
2323		}
2324	0	if (!anchor)
2325	0	return NULL;
2326		}
2327
2328	0	while (JS_TRUE) {
2329	0	if (REOP_IS_SIMPLE(op))
2330	0	result = simpleMatch(gData, x, op, &pc, JS_TRUE);
2331		else {
2332	0	curState = &gData->stateStack[gData->stateStackTop];
2333	0	switch (op) {
2334		case REOP_EMPTY:
2335	0	result = x;
2336	0	break;
2337
2338		case REOP_ALTPREREQ2:
2339	0	nextpc = pc + GET_OFFSET(pc);   /* start of next op */
2340	0	pc += ARG_LEN;
2341	0	matchCh2 = GET_ARG(pc);
2342	0	pc += ARG_LEN;
2343	0	k = GET_ARG(pc);
2344	0	pc += ARG_LEN;
2345
2346	0	if (x->cp != gData->cpend) {
2347	0	if (*x->cp == matchCh2)
2348	0	goto doAlt;
2349
2350	0	charSet = &gData->regexp->classList[k];
2351	0	if (!charSet->converted)
2352	0	if (!processCharSet(gData, charSet))
2353	0	return NULL;
2354	0	matchCh1 = *x->cp;
2355	0	k = matchCh1 / 8;
2356	0	if ((charSet->length == 0 ||
2357		matchCh1 > charSet->length ||
2358		(charSet->u.bits[k] & (1 << (matchCh1 & 0x7))) == 0)
2359		^ charSet->sense) {
2360	0	goto doAlt;
2361		}
2362		}
2363	0	result = NULL;
2364	0	break;
2365
2366		case REOP_ALTPREREQ:
2367	0	nextpc = pc + GET_OFFSET(pc);   /* start of next op */
2368	0	pc += ARG_LEN;
2369	0	matchCh1 = GET_ARG(pc);
2370	0	pc += ARG_LEN;
2371	0	matchCh2 = GET_ARG(pc);
2372	0	pc += ARG_LEN;
2373	0	if ((x->cp == gData->cpend)
2374		|| ((*x->cp != matchCh1) && (*x->cp != matchCh2))) {
2375	0	result = NULL;
2376	0	break;
2377		}
2378		/* else false thru... */
2379
2380		case REOP_ALT:
2381		doAlt:
2382	0	nextpc = pc + GET_OFFSET(pc);   /* start of next alternate */
2383	0	pc += ARG_LEN;                  /* start of this alternate */
2384	0	curState->parenSoFar = parenSoFar;
2385	0	++gData->stateStackTop;
2386	0	if (gData->stateStackTop == gData->maxStateStack)
2387	0	if (!reallocStateStack(gData))
2388	0	return NULL;
2389	0	op = (REOp)(*pc++);
2390	0	startcp = x->cp;
2391	0	if (REOP_IS_SIMPLE(op)) {
2392	0	if (!simpleMatch(gData, x, op, &pc, JS_TRUE)) {
2393	0	op = (REOp)(*nextpc++);
2394	0	pc = nextpc;
2395	0	continue;
2396		}
2397		else { /* accept the match and move on */
2398	0	result = x;
2399	0	op = (REOp)(*pc++);
2400		}
2401		}
2402	0	nextop = (REOp)(*nextpc++);
2403	0	if (!pushBackTrackState(gData, nextop, nextpc, x, startcp, 0, 0))
2404	0	return NULL;
2405	0	continue;
2406
2407		/*
2408		* Occurs at (succesful) end of REOP_ALT,
2409		*/
2410		case REOP_JUMP:
2411	0	--gData->stateStackTop;
2412	0	offset = GET_OFFSET(pc);
2413	0	pc += offset;
2414	0	op = (REOp)(*pc++);
2415	0	continue;
2416
2417		/*
2418		* Occurs at last (succesful) end of REOP_ALT,
2419		*/
2420		case REOP_ENDALT:
2421	0	--gData->stateStackTop;
2422	0	op = (REOp)(*pc++);
2423	0	continue;
2424
2425		case REOP_LPAREN:
2426	0	parenIndex = GET_ARG(pc);
2427	0	if ((parenIndex + 1) > parenSoFar)
2428	0	parenSoFar = parenIndex + 1;
2429	0	pc += ARG_LEN;
2430	0	x->parens[parenIndex].index = x->cp - gData->cpbegin;
2431	0	x->parens[parenIndex].length = 0;
2432	0	op = (REOp)(*pc++);
2433	0	continue;
2434		case REOP_RPAREN:
2435	0	parenIndex = GET_ARG(pc);
2436	0	pc += ARG_LEN;
2437	0	cap = &x->parens[parenIndex];
2438	0	cap->length = x->cp - (gData->cpbegin + cap->index);
2439	0	op = (REOp)(*pc++);
2440	0	continue;
2441
2442		case REOP_ASSERT:
2443	0	nextpc = pc + GET_OFFSET(pc);  /* start of term after ASSERT */
2444	0	pc += ARG_LEN;                 /* start of ASSERT child */
2445	0	op = (REOp)(*pc++);
2446	0	if (REOP_IS_SIMPLE(op)
2447		&& !simpleMatch(gData, x, op, &pc, JS_FALSE)) {
2448	0	result = NULL;
2449	0	break;
2450		}
2451		else {
2452	0	curState->u.assertion.top
2453		= (char *)gData->backTrackSP
2454		- (char *)gData->backTrackStack;
2455	0	curState->u.assertion.sz = gData->cursz;
2456	0	curState->index = x->cp - gData->cpbegin;
2457	0	curState->parenSoFar = parenSoFar;
2458	0	++gData->stateStackTop;
2459	0	if (gData->stateStackTop == gData->maxStateStack)
2460	0	if (!reallocStateStack(gData))
2461	0	return NULL;
2462	0	if (!pushBackTrackState(gData, REOP_ASSERTTEST,
2463		nextpc, x, x->cp, 0, 0))
2464	0	return NULL;
2465		}
2466	0	continue;
2467		case REOP_ASSERT_NOT:
2468	0	nextpc = pc + GET_OFFSET(pc);
2469	0	pc += ARG_LEN;
2470	0	op = (REOp)(*pc++);
2471	0	if (REOP_IS_SIMPLE(op)
2472		/* Note - fail to fail! */
2473		&& simpleMatch(gData, x, op, &pc, JS_FALSE)) {
2474	0	result = NULL;
2475	0	break;
2476		}
2477		else {
2478	0	curState->u.assertion.top
2479		= (char *)gData->backTrackSP
2480		- (char *)gData->backTrackStack;
2481	0	curState->u.assertion.sz = gData->cursz;
2482	0	curState->index = x->cp - gData->cpbegin;
2483	0	curState->parenSoFar = parenSoFar;
2484	0	++gData->stateStackTop;
2485	0	if (gData->stateStackTop == gData->maxStateStack)
2486	0	if (!reallocStateStack(gData))
2487	0	return NULL;
2488	0	if (!pushBackTrackState(gData, REOP_ASSERTNOTTEST,
2489		nextpc, x, x->cp, 0, 0))
2490	0	return NULL;
2491		}
2492	0	continue;
2493		case REOP_ASSERTTEST:
2494	0	--gData->stateStackTop;
2495	0	--curState;
2496	0	x->cp = gData->cpbegin + curState->index;
2497	0	gData->backTrackSP
2498		= (REBackTrackData *)((char *)gData->backTrackStack
2499		+ curState->u.assertion.top);
2500	0	gData->cursz = curState->u.assertion.sz;
2501	0	if (result != NULL)
2502	0	result = x;
2503	0	break;
2504		case REOP_ASSERTNOTTEST:
2505	0	--gData->stateStackTop;
2506	0	--curState;
2507	0	x->cp = gData->cpbegin + curState->index;
2508	0	gData->backTrackSP
2509		= (REBackTrackData *)((char *)gData->backTrackStack
2510		+ curState->u.assertion.top);
2511	0	gData->cursz = curState->u.assertion.sz;
2512	0	if (result == NULL)
2513	0	result = x;
2514		else
2515	0	result = NULL;
2516	0	break;
2517
2518		case REOP_END:
2519	0	if (x != NULL)
2520	0	return x;
2521	0	break;
2522
2523		case REOP_STAR:
2524	0	curState->u.quantifier.min = 0;
2525	0	curState->u.quantifier.max = -1;
2526	0	goto quantcommon;
2527		case REOP_PLUS:
2528	0	curState->u.quantifier.min = 1;
2529	0	curState->u.quantifier.max = -1;
2530	0	goto quantcommon;
2531		case REOP_OPT:
2532	0	curState->u.quantifier.min = 0;
2533	0	curState->u.quantifier.max = 1;
2534	0	goto quantcommon;
2535		case REOP_QUANT:
2536	0	curState->u.quantifier.min = GET_ARG(pc);
2537	0	pc += ARG_LEN;
2538	0	curState->u.quantifier.max = GET_ARG(pc);
2539	0	pc += ARG_LEN;
2540		quantcommon:
2541	0	if (curState->u.quantifier.max == 0) {
2542	0	pc = pc + GET_OFFSET(pc);
2543	0	op = (REOp)(*pc++);
2544	0	result = x;
2545	0	continue;
2546		}
2547		/* Step over <next> */
2548	0	nextpc = pc + ARG_LEN;
2549	0	op = (REOp)(*nextpc++);
2550	0	startcp = x->cp;
2551	0	if (REOP_IS_SIMPLE(op)) {
2552	0	if (!simpleMatch(gData, x, op, &nextpc, JS_TRUE)) {
2553	0	if (curState->u.quantifier.min == 0)
2554	0	result = x;
2555		else
2556	0	result = NULL;
2557	0	pc = pc + GET_OFFSET(pc);
2558	0	break;
2559		}
2560		else {
2561	0	op = (REOp)(*nextpc++);
2562	0	result = x;
2563		}
2564		}
2565	0	curState->index = startcp - gData->cpbegin;
2566	0	curState->continue_op = REOP_REPEAT;
2567	0	curState->continue_pc = pc;
2568	0	curState->parenSoFar = parenSoFar;
2569	0	++gData->stateStackTop;
2570	0	if (gData->stateStackTop == gData->maxStateStack)
2571	0	if (!reallocStateStack(gData))
2572	0	return NULL;
2573	0	if (curState->u.quantifier.min == 0)
2574	0	if (!pushBackTrackState(gData, REOP_REPEAT,
2575		pc, x, startcp, 0, 0))
2576	0	return NULL;
2577	0	pc = nextpc;
2578	0	continue;
2579
2580		case REOP_ENDCHILD: /* marks the end of a quantifier child */
2581	0	pc = curState[-1].continue_pc;
2582	0	op = curState[-1].continue_op;
2583	0	continue;
2584
2585		case REOP_REPEAT:
2586	0	--curState;
2587		repeatAgain:
2588	0	--gData->stateStackTop;
2589	0	if (result == NULL) {
2590		/*
2591		*  There's been a failure, see if we have enough children.
2592		*/
2593	0	if (curState->u.quantifier.min == 0) {
2594	0	result = x;
2595	0	goto repeatDone;
2596		}
2597	0	break;
2598		}
2599		else {
2600	0	if ((curState->u.quantifier.min == 0)
2601		&& (x->cp == gData->cpbegin + curState->index)) {
2602		/* matched an empty string, that'll get us nowhere */
2603	0	result = NULL;
2604	0	break;
2605		}
2606	0	if (curState->u.quantifier.min != 0)
2607	0	curState->u.quantifier.min--;
2608	0	if (curState->u.quantifier.max != (uint16)(-1))
2609	0	curState->u.quantifier.max--;
2610	0	if (curState->u.quantifier.max == 0) {
2611	0	result = x;
2612	0	goto repeatDone;
2613		}
2614	0	nextpc = pc + ARG_LEN;
2615	0	nextop = (REOp)(*nextpc);
2616	0	startcp = x->cp;
2617	0	if (REOP_IS_SIMPLE(nextop)) {
2618	0	nextpc++;
2619	0	if (!simpleMatch(gData, x, nextop, &nextpc, JS_TRUE)) {
2620	0	if (curState->u.quantifier.min == 0) {
2621	0	result = x;
2622	0	goto repeatDone;
2623		}
2624		else
2625	0	result = NULL;
2626	0	break;
2627		}
2628	0	result = x;
2629		}
2630	0	curState->index = startcp - gData->cpbegin;
2631	0	++gData->stateStackTop;
2632	0	if (gData->stateStackTop == gData->maxStateStack)
2633	0	if (!reallocStateStack(gData))
2634	0	return NULL;
2635	0	if (curState->u.quantifier.min == 0)
2636	0	if (!pushBackTrackState(gData, REOP_REPEAT,
2637		pc, x, startcp,
2638		curState->parenSoFar,
2639		parenSoFar
2640		- curState->parenSoFar))
2641	0	return NULL;
2642	0	if (*nextpc == REOP_ENDCHILD)
2643	0	goto repeatAgain;
2644	0	pc = nextpc;
2645	0	op = (REOp)(*pc++);
2646	0	parenSoFar = curState->parenSoFar;
2647		}
2648	0	continue;
2649		repeatDone:
2650	0	pc = pc + GET_OFFSET(pc);
2651	0	break;
2652
2653
2654		case REOP_MINIMALSTAR:
2655	0	curState->u.quantifier.min = 0;
2656	0	curState->u.quantifier.max = -1;
2657	0	goto minimalquantcommon;
2658		case REOP_MINIMALPLUS:
2659	0	curState->u.quantifier.min = 1;
2660	0	curState->u.quantifier.max = -1;
2661	0	goto minimalquantcommon;
2662		case REOP_MINIMALOPT:
2663	0	curState->u.quantifier.min = 0;
2664	0	curState->u.quantifier.max = 1;
2665	0	goto minimalquantcommon;
2666		case REOP_MINIMALQUANT:
2667	0	curState->u.quantifier.min = GET_ARG(pc);
2668	0	pc += ARG_LEN;
2669	0	curState->u.quantifier.max = GET_ARG(pc);
2670	0	pc += ARG_LEN;
2671		minimalquantcommon:
2672	0	curState->index = x->cp - gData->cpbegin;
2673	0	curState->parenSoFar = parenSoFar;
2674	0	++gData->stateStackTop;
2675	0	if (gData->stateStackTop == gData->maxStateStack)
2676	0	if (!reallocStateStack(gData))
2677	0	return NULL;
2678	0	if (curState->u.quantifier.min != 0) {
2679	0	curState->continue_op = REOP_MINIMALREPEAT;
2680	0	curState->continue_pc = pc;
2681		/* step over <next> */
2682	0	pc += ARG_LEN;
2683	0	op = (REOp)(*pc++);
2684		}
2685		else {
2686	0	if (!pushBackTrackState(gData, REOP_MINIMALREPEAT,
2687		pc, x, x->cp, 0, 0))
2688	0	return NULL;
2689	0	--gData->stateStackTop;
2690	0	pc = pc + GET_OFFSET(pc);
2691	0	op = (REOp)(*pc++);
2692		}
2693	0	continue;
2694
2695		case REOP_MINIMALREPEAT:
2696	0	--gData->stateStackTop;
2697	0	--curState;
2698
2699	0	if (result == NULL) {
2700		/*
2701		* Non-greedy failure - try to consume another child.
2702		*/
2703	0	if ((curState->u.quantifier.max == (uint16)(-1))
2704		|| (curState->u.quantifier.max > 0)) {
2705	0	curState->index = x->cp - gData->cpbegin;
2706	0	curState->continue_op = REOP_MINIMALREPEAT;
2707	0	curState->continue_pc = pc;
2708	0	pc += ARG_LEN;
2709	0	for (k = curState->parenSoFar; k < parenSoFar; k++)
2710	0	x->parens[k].index = -1;
2711	0	++gData->stateStackTop;
2712	0	if (gData->stateStackTop == gData->maxStateStack)
2713	0	if (!reallocStateStack(gData))
2714	0	return NULL;
2715	0	op = (REOp)(*pc++);
2716	0	continue;
2717		}
2718		else {
2719		/* Don't need to adjust pc since we're going to pop. */
2720	0	break;
2721		}
2722		}
2723		else {
2724	0	if ((curState->u.quantifier.min == 0)
2725		&& (x->cp == gData->cpbegin + curState->index)) {
2726		/* Matched an empty string, that'll get us nowhere. */
2727	0	result = NULL;
2728	0	break;
2729		}
2730	0	if (curState->u.quantifier.min != 0)
2731	0	curState->u.quantifier.min--;
2732	0	if (curState->u.quantifier.max != (uint16)(-1))
2733	0	curState->u.quantifier.max--;
2734	0	if (curState->u.quantifier.min != 0) {
2735	0	curState->continue_op = REOP_MINIMALREPEAT;
2736	0	curState->continue_pc = pc;
2737	0	pc += ARG_LEN;
2738	0	for (k = curState->parenSoFar; k < parenSoFar; k++)
2739	0	x->parens[k].index = -1;
2740	0	curState->index = x->cp - gData->cpbegin;
2741	0	++gData->stateStackTop;
2742	0	if (gData->stateStackTop == gData->maxStateStack)
2743	0	if (!reallocStateStack(gData))
2744	0	return NULL;
2745	0	op = (REOp)(*pc++);
2746	0	continue;
2747		}
2748		else {
2749	0	curState->index = x->cp - gData->cpbegin;
2750	0	curState->parenSoFar = parenSoFar;
2751	0	++gData->stateStackTop;
2752	0	if (gData->stateStackTop == gData->maxStateStack)
2753	0	if (!reallocStateStack(gData))
2754	0	return NULL;
2755	0	if (!pushBackTrackState(gData, REOP_MINIMALREPEAT,
2756		pc, x, x->cp,
2757		curState->parenSoFar,
2758		parenSoFar
2759		- curState->parenSoFar))
2760	0	return NULL;
2761	0	--gData->stateStackTop;
2762	0	pc = pc + GET_OFFSET(pc);
2763	0	op = (REOp)(*pc++);
2764	0	continue;
2765		}
2766		}
2767
2768		default:
2769	0	JS_ASSERT(JS_FALSE);
2770	0	result = NULL;
2771		}
2772		}
2773		/*
2774		*  If the match failed and there's a backtrack option, take it.
2775		*  Otherwise this is a complete and utter failure.
2776		*/
2777	0	if (result == NULL) {
2778	0	if (gData->cursz > 0) {
2779	0	backTrackData = gData->backTrackSP;
2780	0	gData->cursz = backTrackData->sz;
2781	0	gData->backTrackSP
2782		= (REBackTrackData *)((char *)backTrackData
2783		- backTrackData->sz);
2784	0	x->cp = backTrackData->cp;
2785	0	pc = backTrackData->backtrack_pc;
2786	0	op = backTrackData->backtrack_op;
2787	0	gData->stateStackTop = backTrackData->precedingStateTop;
2788	0	JS_ASSERT(gData->stateStackTop);
2789
2790	0	memcpy(gData->stateStack, backTrackData + 1,
2791		sizeof(REProgState) * backTrackData->precedingStateTop);
2792	0	curState = &gData->stateStack[gData->stateStackTop - 1];
2793
2794	0	if (backTrackData->parenCount) {
2795	0	memcpy(&x->parens[backTrackData->parenIndex],
2796		(char *)(backTrackData + 1) + sizeof(REProgState) * backTrackData->precedingStateTop,
2797		sizeof(RECapture) * backTrackData->parenCount);
2798	0	parenSoFar = backTrackData->parenIndex + backTrackData->parenCount;
2799		}
2800		else {
2801	0	for (k = curState->parenSoFar; k < parenSoFar; k++)
2802	0	x->parens[k].index = -1;
2803	0	parenSoFar = curState->parenSoFar;
2804		}
2805	0	continue;
2806		}
2807		else
2808	0	return NULL;
2809		}
2810		else
2811	0	x = result;
2812
2813		/*
2814		*  Continue with the expression.
2815		*/
2816	0	op = (REOp)*pc++;
2817		}
2818	0	return NULL;
2819		}
2820
2821		static REMatchState *
2822		MatchRegExp(REGlobalData *gData, REMatchState *x)
2823	0	{
2824	0	REMatchState *result;
2825	0	const jschar *cp = x->cp;
2826	0	const jschar *cp2;
2827	0	uintN j;
2828
2829		/*
2830		* Have to include the position beyond the last character
2831		* in order to detect end-of-input/line condition.
2832		*/
2833	0	for (cp2 = cp; cp2 <= gData->cpend; cp2++) {
2834	0	gData->skipped = cp2 - cp;
2835	0	x->cp = cp2;
2836	0	for (j = 0; j < gData->regexp->parenCount; j++)
2837	0	x->parens[j].index = -1;
2838	0	result = executeREBytecode(gData, x);
2839	0	if (!gData->ok || result)
2840	0	return result;
2841	0	gData->backTrackSP = gData->backTrackStack;
2842	0	gData->cursz = 0;
2843	0	gData->stateStackTop = 0;
2844	0	cp2 = cp + gData->skipped;
2845		}
2846	0	return NULL;
2847		}
2848
2849
2850		static REMatchState *
2851		initMatch(JSContext *cx, REGlobalData *gData, JSRegExp *re)
2852	0	{
2853	0	REMatchState *result;
2854	0	uintN i;
2855
2856	0	gData->maxBackTrack = INITIAL_BACKTRACK;
2857	0	JS_ARENA_ALLOCATE_CAST(gData->backTrackStack, REBackTrackData *,
2858		&gData->pool,
2859		INITIAL_BACKTRACK);
2860	0	if (!gData->backTrackStack)
2861	0	return NULL;
2862	0	gData->backTrackSP = gData->backTrackStack;
2863	0	gData->cursz = 0;
2864
2865
2866	0	gData->maxStateStack = INITIAL_STATESTACK;
2867	0	JS_ARENA_ALLOCATE_CAST(gData->stateStack, REProgState *,
2868		&gData->pool,
2869		sizeof(REProgState) * INITIAL_STATESTACK);
2870	0	if (!gData->stateStack)
2871	0	return NULL;
2872	0	gData->stateStackTop = 0;
2873
2874	0	gData->cx = cx;
2875	0	gData->regexp = re;
2876	0	gData->ok = JS_TRUE;
2877
2878	0	JS_ARENA_ALLOCATE_CAST(result, REMatchState *,
2879		&gData->pool,
2880		sizeof(REMatchState)
2881		+ (re->parenCount - 1) * sizeof(RECapture));
2882	0	if (!result)
2883	0	return NULL;
2884
2885	0	for (i = 0; i < re->classCount; i++)
2886	0	if (!re->classList[i].converted)
2887	0	if (!processCharSet(gData, &re->classList[i]))
2888	0	return NULL;
2889
2890	0	return result;
2891		}
2892
2893		JSBool
2894		js_ExecuteRegExp(JSContext *cx, JSRegExp *re, JSString *str, size_t *indexp,
2895		JSBool test, jsval *rval)
2896	0	{
2897	0	REGlobalData gData;
2898	0	REMatchState *x, *result;
2899
2900	0	const jschar *cp, *ep;
2901	0	size_t i, length, start;
2902	0	JSSubString *morepar;
2903	0	JSBool ok;
2904	0	JSRegExpStatics *res;
2905	0	ptrdiff_t matchlen;
2906	0	uintN num, morenum;
2907	0	JSString *parstr, *matchstr;
2908	0	JSObject *obj;
2909
2910	0	RECapture *parsub;
2911
2912		/*
2913		* It's safe to load from cp because JSStrings have a zero at the end,
2914		* and we never let cp get beyond cpend.
2915		*/
2916	0	start = *indexp;
2917	0	length = JSSTRING_LENGTH(str);
2918	0	if (start > length)
2919	0	start = length;
2920	0	cp = JSSTRING_CHARS(str);
2921	0	gData.cpbegin = cp;
2922	0	gData.cpend = cp + length;
2923	0	cp += start;
2924	0	gData.start = start;
2925	0	gData.skipped = 0;
2926
2927	0	JS_InitArenaPool(&gData.pool, "RegExpPool", 8096, 4);
2928	0	x = initMatch(cx, &gData, re);
2929	0	if (!x)
2930	0	return JS_FALSE;
2931	0	x->cp = cp;
2932
2933		/*
2934		* Call the recursive matcher to do the real work.  Return null on mismatch
2935		* whether testing or not.  On match, return an extended Array object.
2936		*/
2937	0	result = MatchRegExp(&gData, x);
2938	0	if (!(ok = gData.ok)) goto out;
2939	0	if (!result) {
2940	0	*rval = JSVAL_NULL;
2941	0	goto out;
2942		}
2943	0	cp = result->cp;
2944	0	i = PTRDIFF(cp, gData.cpbegin, jschar);
2945	0	*indexp = i;
2946	0	matchlen = i - (start + gData.skipped);
2947	0	ep = cp;
2948	0	cp -= matchlen;
2949
2950	0	if (test) {
2951		/*
2952		* Testing for a match and updating cx->regExpStatics: don't allocate
2953		* an array object, do return true.
2954		*/
2955	0	*rval = JSVAL_TRUE;
2956
2957		/* Avoid warning.  (gcc doesn't detect that obj is needed iff !test); */
2958	0	obj = NULL;
2959		} else {
2960		/*
2961		* The array returned on match has element 0 bound to the matched
2962		* string, elements 1 through state.parenCount bound to the paren
2963		* matches, an index property telling the length of the left context,
2964		* and an input property referring to the input string.
2965		*/
2966	0	obj = js_NewArrayObject(cx, 0, NULL);
2967	0	if (!obj) {
2968	0	ok = JS_FALSE;
2969	0	goto out;
2970		}
2971	0	*rval = OBJECT_TO_JSVAL(obj);
2972
2973		#define DEFVAL(val, id) {                                                     \
2974		ok = js_DefineProperty(cx, obj, id, val,                                  \
2975		JS_PropertyStub, JS_PropertyStub,                  \
2976		JSPROP_ENUMERATE, NULL);                           \
2977		if (!ok) {                                                                \
2978		cx->newborn[GCX_OBJECT] = NULL;                                       \
2979		cx->newborn[GCX_STRING] = NULL;                                       \
2980		goto out;                                                             \
2981		}                                                                         \
2982		}
2983
2984	0	matchstr = js_NewStringCopyN(cx, cp, matchlen, 0);
2985	0	if (!matchstr) {
2986	0	cx->newborn[GCX_OBJECT] = NULL;
2987	0	ok = JS_FALSE;
2988	0	goto out;
2989		}
2990	0	DEFVAL(STRING_TO_JSVAL(matchstr), INT_TO_JSVAL(0));
2991		}
2992
2993	0	res = &cx->regExpStatics;
2994	0	res->input = str;
2995	0	res->parenCount = re->parenCount;
2996	0	if (re->parenCount == 0)
2997	0	res->lastParen = js_EmptySubString;
2998		else {
2999	0	for (num = 0; num < re->parenCount; num++) {
3000	0	parsub = &result->parens[num];
3001	0	if (num < 9) {
3002	0	if (parsub->index == -1) {
3003	0	res->parens[num].chars = NULL;
3004	0	res->parens[num].length = 0;
3005		}
3006		else {
3007	0	res->parens[num].chars = gData.cpbegin + parsub->index;
3008	0	res->parens[num].length = parsub->length;
3009		}
3010		} else {
3011	0	morenum = num - 9;
3012	0	morepar = res->moreParens;
3013	0	if (!morepar) {
3014	0	res->moreLength = 10;
3015	0	morepar = (JSSubString*) JS_malloc(cx,
3016		10 * sizeof(JSSubString));
3017	0	} else if (morenum >= res->moreLength) {
3018	0	res->moreLength += 10;
3019	0	morepar = (JSSubString*) JS_realloc(cx, morepar,
3020		res->moreLength * sizeof(JSSubString));
3021		}
3022	0	if (!morepar) {
3023	0	cx->newborn[GCX_OBJECT] = NULL;
3024	0	cx->newborn[GCX_STRING] = NULL;
3025	0	ok = JS_FALSE;
3026	0	goto out;
3027		}
3028	0	res->moreParens = morepar;
3029	0	if (parsub->index == -1) {
3030	0	morepar[morenum].chars = NULL;
3031	0	morepar[morenum].length = 0;
3032		}
3033		else {
3034	0	morepar[morenum].chars = gData.cpbegin + parsub->index;
3035	0	morepar[morenum].length = parsub->length;
3036		}
3037		}
3038	0	if (test)
3039	0	continue;
3040	0	if (parsub->index == -1)
3041	0	ok = js_DefineProperty(cx, obj, INT_TO_JSVAL(num + 1),
3042		JSVAL_VOID, NULL, NULL,
3043		JSPROP_ENUMERATE, NULL);
3044		else {
3045	0	parstr = js_NewStringCopyN(cx, gData.cpbegin + parsub->index,
3046		parsub->length, 0);
3047	0	if (!parstr) {
3048	0	cx->newborn[GCX_OBJECT] = NULL;
3049	0	cx->newborn[GCX_STRING] = NULL;
3050	0	ok = JS_FALSE;
3051	0	goto out;
3052		}
3053	0	ok = js_DefineProperty(cx, obj, INT_TO_JSVAL(num + 1),
3054		STRING_TO_JSVAL(parstr), NULL, NULL,
3055		JSPROP_ENUMERATE, NULL);
3056		}
3057	0	if (!ok) {
3058	0	cx->newborn[GCX_OBJECT] = NULL;
3059	0	cx->newborn[GCX_STRING] = NULL;
3060	0	goto out;
3061		}
3062		}
3063	0	if (parsub->index == -1) {
3064	0	res->lastParen.chars = NULL;
3065	0	res->lastParen.length = 0;
3066		}
3067		else {
3068	0	res->lastParen.chars = gData.cpbegin + parsub->index;
3069	0	res->lastParen.length = parsub->length;
3070		}
3071		}
3072
3073	0	if (!test) {
3074		/*
3075		* Define the index and input properties last for better for/in loop
3076		* order (so they come after the elements).
3077		*/
3078	0	DEFVAL(INT_TO_JSVAL(start + gData.skipped),
3079		(jsid)cx->runtime->atomState.indexAtom);
3080	0	DEFVAL(STRING_TO_JSVAL(str),
3081		(jsid)cx->runtime->atomState.inputAtom);
3082		}
3083
3084		#undef DEFVAL
3085
3086	0	res->lastMatch.chars = cp;
3087	0	res->lastMatch.length = matchlen;
3088	0	if (cx->version == JSVERSION_1_2) {
3089		/*
3090		* JS1.2 emulated Perl4.0.1.8 (patch level 36) for global regexps used
3091		* in scalar contexts, and unintentionally for the string.match "list"
3092		* psuedo-context.  On "hi there bye", the following would result:
3093		*
3094		* Language     while(/ /g){print("$`");}   s/ /$`/g
3095		* perl4.036    "hi", "there"               "hihitherehi therebye"
3096		* perl5        "hi", "hi there"            "hihitherehi therebye"
3097		* js1.2        "hi", "there"               "hihitheretherebye"
3098		*/
3099	0	res->leftContext.chars = JSSTRING_CHARS(str) + start;
3100	0	res->leftContext.length = gData.skipped;
3101		} else {
3102		/*
3103		* For JS1.3 and ECMAv2, emulate Perl5 exactly:
3104		*
3105		* js1.3        "hi", "hi there"            "hihitherehi therebye"
3106		*/
3107	0	res->leftContext.chars = JSSTRING_CHARS(str);
3108	0	res->leftContext.length = start + gData.skipped;
3109		}
3110	0	res->rightContext.chars = ep;
3111	0	res->rightContext.length = gData.cpend - ep;
3112
3113		out:
3114	0	JS_FinishArenaPool(&gData.pool);
3115	0	return ok;
3116		}
3117
3118		/************************************************************************/
3119
3120		enum regexp_tinyid {
3121		REGEXP_SOURCE       = -1,
3122		REGEXP_GLOBAL       = -2,
3123		REGEXP_IGNORE_CASE  = -3,
3124		REGEXP_LAST_INDEX   = -4,
3125		REGEXP_MULTILINE    = -5
3126		};
3127
3128		#define REGEXP_PROP_ATTRS (JSPROP_PERMANENT|JSPROP_SHARED)
3129
3130		static JSPropertySpec regexp_props[] = {
3131		{"source",     REGEXP_SOURCE,      REGEXP_PROP_ATTRS | JSPROP_READONLY,0,0},
3132		{"global",     REGEXP_GLOBAL,      REGEXP_PROP_ATTRS | JSPROP_READONLY,0,0},
3133		{"ignoreCase", REGEXP_IGNORE_CASE, REGEXP_PROP_ATTRS | JSPROP_READONLY,0,0},
3134		{"lastIndex",  REGEXP_LAST_INDEX,  REGEXP_PROP_ATTRS,0,0},
3135		{"multiline",  REGEXP_MULTILINE,   REGEXP_PROP_ATTRS | JSPROP_READONLY,0,0},
3136		{0,0,0,0,0}
3137		};
3138
3139		static JSBool
3140		regexp_getProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
3141	0	{
3142	0	jsint slot;
3143	0	JSRegExp *re;
3144
3145	0	if (!JSVAL_IS_INT(id))
3146	0	return JS_TRUE;
3147	0	slot = JSVAL_TO_INT(id);
3148	0	if (slot == REGEXP_LAST_INDEX)
3149	0	return JS_GetReservedSlot(cx, obj, 0, vp);
3150
3151	0	JS_LOCK_OBJ(cx, obj);
3152	0	re = (JSRegExp *) JS_GetInstancePrivate(cx, obj, &js_RegExpClass, NULL);
3153	0	if (re) {
3154	0	switch (slot) {
3155		case REGEXP_SOURCE:
3156	0	*vp = STRING_TO_JSVAL(re->source);
3157	0	break;
3158		case REGEXP_GLOBAL:
3159	0	*vp = BOOLEAN_TO_JSVAL((re->flags & JSREG_GLOB) != 0);
3160	0	break;
3161		case REGEXP_IGNORE_CASE:
3162	0	*vp = BOOLEAN_TO_JSVAL((re->flags & JSREG_FOLD) != 0);
3163	0	break;
3164		case REGEXP_MULTILINE:
3165	0	*vp = BOOLEAN_TO_JSVAL((re->flags & JSREG_MULTILINE) != 0);
3166		break;
3167		}
3168		}
3169	0	JS_UNLOCK_OBJ(cx, obj);
3170	0	return JS_TRUE;
3171		}
3172
3173		static JSBool
3174		regexp_setProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
3175	0	{
3176	0	JSBool ok;
3177	0	jsint slot;
3178	0	jsdouble lastIndex;
3179
3180	0	ok = JS_TRUE;
3181	0	if (!JSVAL_IS_INT(id))
3182	0	return ok;
3183	0	slot = JSVAL_TO_INT(id);
3184	0	if (slot == REGEXP_LAST_INDEX) {
3185	0	if (!js_ValueToNumber(cx, *vp, &lastIndex))
3186	0	return JS_FALSE;
3187	0	lastIndex = js_DoubleToInteger(lastIndex);
3188	0	ok = js_NewNumberValue(cx, lastIndex, vp) &&
3189		JS_SetReservedSlot(cx, obj, 0, *vp);
3190		}
3191	0	return ok;
3192		}
3193
3194		/*
3195		* RegExp class static properties and their Perl counterparts:
3196		*
3197		*  RegExp.input                $_
3198		*  RegExp.multiline            $*
3199		*  RegExp.lastMatch            $&
3200		*  RegExp.lastParen            $+
3201		*  RegExp.leftContext          $`
3202		*  RegExp.rightContext         $'
3203		*/
3204		enum regexp_static_tinyid {
3205		REGEXP_STATIC_INPUT         = -1,
3206		REGEXP_STATIC_MULTILINE     = -2,
3207		REGEXP_STATIC_LAST_MATCH    = -3,
3208		REGEXP_STATIC_LAST_PAREN    = -4,
3209		REGEXP_STATIC_LEFT_CONTEXT  = -5,
3210		REGEXP_STATIC_RIGHT_CONTEXT = -6
3211		};
3212
3213		JSBool
3214		js_InitRegExpStatics(JSContext *cx, JSRegExpStatics *res)
3215	0	{
3216	0	JS_ClearRegExpStatics(cx);
3217	0	return js_AddRoot(cx, &res->input, "res->input");
3218		}
3219
3220		void
3221		js_FreeRegExpStatics(JSContext *cx, JSRegExpStatics *res)
3222	0	{
3223	0	if (res->moreParens) {
3224	0	JS_free(cx, res->moreParens);
3225	0	res->moreParens = NULL;
3226		}
3227	0	js_RemoveRoot(cx->runtime, &res->input);
3228		}
3229
3230		static JSBool
3231		regexp_static_getProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
3232	0	{
3233	0	jsint slot;
3234	0	JSRegExpStatics *res;
3235	0	JSString *str;
3236	0	JSSubString *sub;
3237
3238	0	res = &cx->regExpStatics;
3239	0	if (!JSVAL_IS_INT(id))
3240	0	return JS_TRUE;
3241	0	slot = JSVAL_TO_INT(id);
3242	0	switch (slot) {
3243		case REGEXP_STATIC_INPUT:
3244	0	*vp = res->input ? STRING_TO_JSVAL(res->input)
3245		: JS_GetEmptyStringValue(cx);
3246	0	return JS_TRUE;
3247		case REGEXP_STATIC_MULTILINE:
3248	0	*vp = BOOLEAN_TO_JSVAL(res->multiline);
3249	0	return JS_TRUE;
3250		case REGEXP_STATIC_LAST_MATCH:
3251	0	sub = &res->lastMatch;
3252	0	break;
3253		case REGEXP_STATIC_LAST_PAREN:
3254	0	sub = &res->lastParen;
3255	0	break;
3256		case REGEXP_STATIC_LEFT_CONTEXT:
3257	0	sub = &res->leftContext;
3258	0	break;
3259		case REGEXP_STATIC_RIGHT_CONTEXT:
3260	0	sub = &res->rightContext;
3261	0	break;
3262		default:
3263	0	sub = REGEXP_PAREN_SUBSTRING(res, slot);
3264	0	break;
3265		}
3266	0	str = js_NewStringCopyN(cx, sub->chars, sub->length, 0);
3267	0	if (!str)
3268	0	return JS_FALSE;
3269	0	*vp = STRING_TO_JSVAL(str);
3270	0	return JS_TRUE;
3271		}
3272
3273		static JSBool
3274		regexp_static_setProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
3275	0	{
3276	0	JSRegExpStatics *res;
3277
3278	0	if (!JSVAL_IS_INT(id))
3279	0	return JS_TRUE;
3280	0	res = &cx->regExpStatics;
3281		/* XXX use if-else rather than switch to keep MSVC1.52 from crashing */
3282	0	if (JSVAL_TO_INT(id) == REGEXP_STATIC_INPUT) {
3283	0	if (!JSVAL_IS_STRING(*vp) &&
3284		!JS_ConvertValue(cx, *vp, JSTYPE_STRING, vp)) {
3285	0	return JS_FALSE;
3286		}
3287	0	res->input = JSVAL_TO_STRING(*vp);
3288	0	} else if (JSVAL_TO_INT(id) == REGEXP_STATIC_MULTILINE) {
3289	0	if (!JSVAL_IS_BOOLEAN(*vp) &&
3290		!JS_ConvertValue(cx, *vp, JSTYPE_BOOLEAN, vp)) {
3291	0	return JS_FALSE;
3292		}
3293	0	res->multiline = JSVAL_TO_BOOLEAN(*vp);
3294		}
3295	0	return JS_TRUE;
3296		}
3297
3298		static JSPropertySpec regexp_static_props[] = {
3299		{"input",
3300		REGEXP_STATIC_INPUT,
3301		JSPROP_ENUMERATE|JSPROP_SHARED,
3302		regexp_static_getProperty,    regexp_static_setProperty},
3303		{"multiline",
3304		REGEXP_STATIC_MULTILINE,
3305		JSPROP_ENUMERATE|JSPROP_SHARED,
3306		regexp_static_getProperty,    regexp_static_setProperty},
3307		{"lastMatch",
3308		REGEXP_STATIC_LAST_MATCH,
3309		JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3310		regexp_static_getProperty,    regexp_static_getProperty},
3311		{"lastParen",
3312		REGEXP_STATIC_LAST_PAREN,
3313		JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3314		regexp_static_getProperty,    regexp_static_getProperty},
3315		{"leftContext",
3316		REGEXP_STATIC_LEFT_CONTEXT,
3317		JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3318		regexp_static_getProperty,    regexp_static_getProperty},
3319		{"rightContext",
3320		REGEXP_STATIC_RIGHT_CONTEXT,
3321		JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3322		regexp_static_getProperty,    regexp_static_getProperty},
3323
3324		/* XXX should have block scope and local $1, etc. */
3325		{"$1", 0, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3326		regexp_static_getProperty,    regexp_static_getProperty},
3327		{"$2", 1, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3328		regexp_static_getProperty,    regexp_static_getProperty},
3329		{"$3", 2, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3330		regexp_static_getProperty,    regexp_static_getProperty},
3331		{"$4", 3, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3332		regexp_static_getProperty,    regexp_static_getProperty},
3333		{"$5", 4, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3334		regexp_static_getProperty,    regexp_static_getProperty},
3335		{"$6", 5, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3336		regexp_static_getProperty,    regexp_static_getProperty},
3337		{"$7", 6, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3338		regexp_static_getProperty,    regexp_static_getProperty},
3339		{"$8", 7, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3340		regexp_static_getProperty,    regexp_static_getProperty},
3341		{"$9", 8, JSPROP_ENUMERATE|JSPROP_READONLY|JSPROP_SHARED,
3342		regexp_static_getProperty,    regexp_static_getProperty},
3343
3344		{0,0,0,0,0}
3345		};
3346
3347		static void
3348		regexp_finalize(JSContext *cx, JSObject *obj)
3349	0	{
3350	0	JSRegExp *re;
3351
3352	0	re = (JSRegExp *) JS_GetPrivate(cx, obj);
3353	0	if (!re)
3354	0	return;
3355	0	js_DestroyRegExp(cx, re);
3356		}
3357
3358		/* Forward static prototype. */
3359		static JSBool
3360		regexp_exec(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
3361		jsval *rval);
3362
3363		static JSBool
3364		regexp_call(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
3365	0	{
3366	0	return regexp_exec(cx, JSVAL_TO_OBJECT(argv[-2]), argc, argv, rval);
3367		}
3368
3369		#if JS_HAS_XDR
3370
3371		#include "jsxdrapi.h"
3372
3373		static JSBool
3374		regexp_xdrObject(JSXDRState *xdr, JSObject **objp)
3375	0	{
3376	0	JSRegExp *re;
3377	0	JSString *source;
3378	0	uint8 flags;
3379
3380	0	if (xdr->mode == JSXDR_ENCODE) {
3381	0	re = (JSRegExp *) JS_GetPrivate(xdr->cx, *objp);
3382	0	if (!re)
3383	0	return JS_FALSE;
3384	0	source = re->source;
3385	0	flags = (uint8) re->flags;
3386		}
3387	0	if (!JS_XDRString(xdr, &source) ||
3388		!JS_XDRUint8(xdr, &flags)) {
3389	0	return JS_FALSE;
3390		}
3391	0	if (xdr->mode == JSXDR_DECODE) {
3392	0	*objp = js_NewObject(xdr->cx, &js_RegExpClass, NULL, NULL);
3393	0	if (!*objp)
3394	0	return JS_FALSE;
3395	0	re = js_NewRegExp(xdr->cx, NULL, source, flags, JS_FALSE);
3396	0	if (!re)
3397	0	return JS_FALSE;
3398	0	if (!JS_SetPrivate(xdr->cx, *objp, re) ||
3399		!js_SetLastIndex(xdr->cx, *objp, 0)) {
3400	0	js_DestroyRegExp(xdr->cx, re);
3401	0	return JS_FALSE;
3402		}
3403		}
3404	0	return JS_TRUE;
3405		}
3406
3407		#else  /* !JS_HAS_XDR */
3408
3409		#define regexp_xdrObject NULL
3410
3411		#endif /* !JS_HAS_XDR */
3412
3413		static uint32
3414		regexp_mark(JSContext *cx, JSObject *obj, void *arg)
3415	0	{
3416	0	JSRegExp *re = (JSRegExp *) JS_GetPrivate(cx, obj);
3417	0	if (re)
3418	0	JS_MarkGCThing(cx, re->source, "source", arg);
3419	0	return 0;
3420		}
3421
3422		JSClass js_RegExpClass = {
3423		js_RegExp_str,
3424		JSCLASS_HAS_PRIVATE | JSCLASS_HAS_RESERVED_SLOTS(1),
3425		JS_PropertyStub,  JS_PropertyStub,  regexp_getProperty, regexp_setProperty,
3426		JS_EnumerateStub, JS_ResolveStub,   JS_ConvertStub,     regexp_finalize,
3427		NULL,             NULL,             regexp_call,        NULL,
3428		regexp_xdrObject, NULL,             regexp_mark,        0
3429		};
3430
3431		static const jschar empty_regexp_ucstr[] = {'(', '?', ':', ')', 0};
3432
3433		static JSBool
3434		regexp_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
3435		jsval *rval)
3436	0	{
3437	0	JSRegExp *re;
3438	0	const jschar *source;
3439	0	jschar *chars;
3440	0	size_t length, nflags;
3441	0	uintN flags;
3442	0	JSString *str;
3443
3444	0	if (!JS_InstanceOf(cx, obj, &js_RegExpClass, argv))
3445	0	return JS_FALSE;
3446	0	JS_LOCK_OBJ(cx, obj);
3447	0	re = (JSRegExp *) JS_GetPrivate(cx, obj);
3448	0	if (!re) {
3449	0	JS_UNLOCK_OBJ(cx, obj);
3450	0	*rval = STRING_TO_JSVAL(cx->runtime->emptyString);
3451	0	return JS_TRUE;
3452		}
3453
3454	0	source = JSSTRING_CHARS(re->source);
3455	0	length = JSSTRING_LENGTH(re->source);
3456	0	if (length == 0) {
3457	0	source = empty_regexp_ucstr;
3458	0	length = sizeof(empty_regexp_ucstr) / sizeof(jschar) - 1;
3459		}
3460	0	length += 2;
3461	0	nflags = 0;
3462	0	for (flags = re->flags; flags != 0; flags &= flags - 1)
3463	0	nflags++;
3464	0	chars = (jschar*) JS_malloc(cx, (length + nflags + 1) * sizeof(jschar));
3465	0	if (!chars) {
3466	0	JS_UNLOCK_OBJ(cx, obj);
3467	0	return JS_FALSE;
3468		}
3469
3470	0	chars[0] = '/';
3471	0	js_strncpy(&chars[1], source, length - 2);
3472	0	chars[length-1] = '/';
3473	0	if (nflags) {
3474	0	if (re->flags & JSREG_GLOB)
3475	0	chars[length++] = 'g';
3476	0	if (re->flags & JSREG_FOLD)
3477	0	chars[length++] = 'i';
3478	0	if (re->flags & JSREG_MULTILINE)
3479	0	chars[length++] = 'm';
3480		}
3481	0	JS_UNLOCK_OBJ(cx, obj);
3482	0	chars[length] = 0;
3483
3484	0	str = js_NewString(cx, chars, length, 0);
3485	0	if (!str) {
3486	0	JS_free(cx, chars);
3487	0	return JS_FALSE;
3488		}
3489	0	*rval = STRING_TO_JSVAL(str);
3490	0	return JS_TRUE;
3491		}
3492
3493		static JSBool
3494		regexp_compile(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
3495		jsval *rval)
3496	0	{
3497	0	JSString *opt, *str;
3498	0	JSRegExp *oldre, *re;
3499	0	JSBool ok;
3500	0	JSObject *obj2;
3501
3502	0	if (!JS_InstanceOf(cx, obj, &js_RegExpClass, argv))
3503	0	return JS_FALSE;
3504	0	opt = NULL;
3505	0	if (argc == 0) {
3506	0	str = cx->runtime->emptyString;
3507		} else {
3508	0	if (JSVAL_IS_OBJECT(argv[0])) {
3509		/*
3510		* If we get passed in a RegExp object we construct a new
3511		* RegExp that is a duplicate of it by re-compiling the
3512		* original source code. ECMA requires that it be an error
3513		* here if the flags are specified. (We must use the flags
3514		* from the original RegExp also).
3515		*/
3516	0	obj2 = JSVAL_TO_OBJECT(argv[0]);
3517	0	if (obj2 && OBJ_GET_CLASS(cx, obj2) == &js_RegExpClass) {
3518	0	if (argc >= 2 && !JSVAL_IS_VOID(argv[1])) { /* 'flags' passed */
3519	0	JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3520		JSMSG_NEWREGEXP_FLAGGED);
3521	0	return JS_FALSE;
3522		}
3523	0	JS_LOCK_OBJ(cx, obj2);
3524	0	re = (JSRegExp *) JS_GetPrivate(cx, obj2);
3525	0	if (!re) {
3526	0	JS_UNLOCK_OBJ(cx, obj2);
3527	0	return JS_FALSE;
3528		}
3529	0	re = js_NewRegExp(cx, NULL, re->source, re->flags, JS_FALSE);
3530	0	JS_UNLOCK_OBJ(cx, obj2);
3531	0	goto madeit;
3532		}
3533		}
3534	0	str = js_ValueToString(cx, argv[0]);
3535	0	if (!str)
3536	0	return JS_FALSE;
3537	0	argv[0] = STRING_TO_JSVAL(str);
3538	0	if (argc > 1) {
3539	0	if (JSVAL_IS_VOID(argv[1])) {
3540	0	opt = NULL;
3541		} else {
3542	0	opt = js_ValueToString(cx, argv[1]);
3543	0	if (!opt)
3544	0	return JS_FALSE;
3545	0	argv[1] = STRING_TO_JSVAL(opt);
3546		}
3547		}
3548		}
3549	0	re = js_NewRegExpOpt(cx, NULL, str, opt, JS_FALSE);
3550		madeit:
3551	0	if (!re)
3552	0	return JS_FALSE;
3553	0	JS_LOCK_OBJ(cx, obj);
3554	0	oldre = (JSRegExp *) JS_GetPrivate(cx, obj);
3555	0	ok = JS_SetPrivate(cx, obj, re) && js_SetLastIndex(cx, obj, 0);
3556	0	JS_UNLOCK_OBJ(cx, obj);
3557	0	if (!ok) {
3558	0	js_DestroyRegExp(cx, re);
3559		} else {
3560	0	if (oldre)
3561	0	js_DestroyRegExp(cx, oldre);
3562	0	*rval = OBJECT_TO_JSVAL(obj);
3563		}
3564	0	return ok;
3565		}
3566
3567		static JSBool
3568		regexp_exec_sub(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
3569		JSBool test, jsval *rval)
3570	0	{
3571	0	JSBool ok;
3572	0	JSRegExp *re;
3573	0	jsdouble lastIndex;
3574	0	JSString *str;
3575	0	size_t i;
3576
3577	0	ok = JS_InstanceOf(cx, obj, &js_RegExpClass, argv);
3578	0	if (!ok)
3579	0	return JS_FALSE;
3580	0	JS_LOCK_OBJ(cx, obj);
3581	0	re = (JSRegExp *) JS_GetPrivate(cx, obj);
3582	0	if (!re) {
3583	0	JS_UNLOCK_OBJ(cx, obj);
3584	0	return JS_TRUE;
3585		}
3586
3587		/* NB: we must reach out: after this paragraph, in order to drop re. */
3588	0	HOLD_REGEXP(cx, re);
3589	0	if (re->flags & JSREG_GLOB) {
3590	0	ok = js_GetLastIndex(cx, obj, &lastIndex);
3591		} else {
3592	0	lastIndex = 0;
3593		}
3594	0	JS_UNLOCK_OBJ(cx, obj);
3595	0	if (!ok)
3596	0	goto out;
3597
3598		/* Now that obj is unlocked, it's safe to (potentially) grab the GC lock. */
3599	0	if (argc == 0) {
3600	0	str = cx->regExpStatics.input;
3601	0	if (!str) {
3602	0	JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
3603		JSMSG_NO_INPUT,
3604		JS_GetStringBytes(re->source),
3605		(re->flags & JSREG_GLOB) ? "g" : "",
3606		(re->flags & JSREG_FOLD) ? "i" : "",
3607		(re->flags & JSREG_MULTILINE) ? "m" : "");
3608	0	ok = JS_FALSE;
3609	0	goto out;
3610		}
3611		} else {
3612	0	str = js_ValueToString(cx, argv[0]);
3613	0	if (!str)
3614	0	goto out;
3615	0	argv[0] = STRING_TO_JSVAL(str);
3616		}
3617
3618	0	if (lastIndex < 0 || JSSTRING_LENGTH(str) < lastIndex) {
3619	0	ok = js_SetLastIndex(cx, obj, 0);
3620	0	*rval = JSVAL_NULL;
3621		} else {
3622	0	i = (size_t) lastIndex;
3623	0	ok = js_ExecuteRegExp(cx, re, str, &i, test, rval);
3624	0	if (ok && (re->flags & JSREG_GLOB))
3625	0	ok = js_SetLastIndex(cx, obj, (*rval == JSVAL_NULL) ? 0 : i);
3626		}
3627
3628		out:
3629	0	DROP_REGEXP(cx, re);
3630	0	return ok;
3631		}
3632
3633		static JSBool
3634		regexp_exec(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
3635	0	{
3636	0	return regexp_exec_sub(cx, obj, argc, argv, JS_FALSE, rval);
3637		}
3638
3639		static JSBool
3640		regexp_test(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
3641	0	{
3642	0	if (!regexp_exec_sub(cx, obj, argc, argv, JS_TRUE, rval))
3643	0	return JS_FALSE;
3644	0	if (*rval != JSVAL_TRUE)
3645	0	*rval = JSVAL_FALSE;
3646	0	return JS_TRUE;
3647		}
3648
3649		static JSFunctionSpec regexp_methods[] = {
3650		#if JS_HAS_TOSOURCE
3651		{js_toSource_str,   regexp_toString,        0,0,0},
3652		#endif
3653		{js_toString_str,   regexp_toString,        0,0,0},
3654		{"compile",         regexp_compile,         1,0,0},
3655		{"exec",            regexp_exec,            0,0,0},
3656		{"test",            regexp_test,            0,0,0},
3657		{0,0,0,0,0}
3658		};
3659
3660		static JSBool
3661		RegExp(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
3662	0	{
3663	0	if (!(cx->fp->flags & JSFRAME_CONSTRUCTING)) {
3664		/*
3665		* If first arg is regexp and no flags are given, just return the arg.
3666		* (regexp_compile detects the regexp + flags case and throws a
3667		* TypeError.)  See 10.15.3.1.
3668		*/
3669	0	if ((argc < 2 || JSVAL_IS_VOID(argv[1])) && JSVAL_IS_OBJECT(argv[0]) &&
3670		OBJ_GET_CLASS(cx, JSVAL_TO_OBJECT(argv[0])) == &js_RegExpClass) {
3671	0	*rval = argv[0];
3672	0	return JS_TRUE;
3673		}
3674
3675		/* Otherwise, replace obj with a new RegExp object. */
3676	0	obj = js_NewObject(cx, &js_RegExpClass, NULL, NULL);
3677	0	if (!obj)
3678	0	return JS_FALSE;
3679		}
3680	0	return regexp_compile(cx, obj, argc, argv, rval);
3681		}
3682
3683		JSObject *
3684		js_InitRegExpClass(JSContext *cx, JSObject *obj)
3685	0	{
3686	0	JSObject *proto, *ctor;
3687	0	jsval rval;
3688
3689	0	proto = JS_InitClass(cx, obj, NULL, &js_RegExpClass, RegExp, 1,
3690		regexp_props, regexp_methods,
3691		regexp_static_props, NULL);
3692
3693	0	if (!proto || !(ctor = JS_GetConstructor(cx, proto)))
3694	0	return NULL;
3695	0	if (!JS_AliasProperty(cx, ctor, "input",        "$_") ||
3696		!JS_AliasProperty(cx, ctor, "multiline",    "$*") ||
3697		!JS_AliasProperty(cx, ctor, "lastMatch",    "$&") ||
3698		!JS_AliasProperty(cx, ctor, "lastParen",    "$+") ||
3699		!JS_AliasProperty(cx, ctor, "leftContext",  "$`") ||
3700		!JS_AliasProperty(cx, ctor, "rightContext", "$'")) {
3701	0	goto bad;
3702		}
3703
3704		/* Give RegExp.prototype private data so it matches the empty string. */
3705	0	if (!regexp_compile(cx, proto, 0, NULL, &rval))
3706	0	goto bad;
3707	0	return proto;
3708
3709		bad:
3710	0	JS_DeleteProperty(cx, obj, js_RegExpClass.name);
3711	0	return NULL;
3712		}
3713
3714		JSObject *
3715		js_NewRegExpObject(JSContext *cx, JSTokenStream *ts,
3716		jschar *chars, size_t length, uintN flags)
3717	0	{
3718	0	JSString *str;
3719	0	JSObject *obj;
3720	0	JSRegExp *re;
3721
3722	0	str = js_NewStringCopyN(cx, chars, length, 0);
3723	0	if (!str)
3724	0	return NULL;
3725	0	re = js_NewRegExp(cx, ts,  str, flags, JS_FALSE);
3726	0	if (!re)
3727	0	return NULL;
3728	0	obj = js_NewObject(cx, &js_RegExpClass, NULL, NULL);
3729	0	if (!obj || !JS_SetPrivate(cx, obj, re) || !js_SetLastIndex(cx, obj, 0)) {
3730	0	js_DestroyRegExp(cx, re);
3731	0	return NULL;
3732		}
3733	0	return obj;
3734		}
3735
3736		JSObject *
3737		js_CloneRegExpObject(JSContext *cx, JSObject *obj, JSObject *parent)
3738	0	{
3739	0	JSObject *clone;
3740	0	JSRegExp *re;
3741
3742	0	JS_ASSERT(OBJ_GET_CLASS(cx, obj) == &js_RegExpClass);
3743	0	clone = js_NewObject(cx, &js_RegExpClass, NULL, parent);
3744	0	if (!clone)
3745	0	return NULL;
3746	0	re = JS_GetPrivate(cx, obj);
3747	0	if (!JS_SetPrivate(cx, clone, re) || !js_SetLastIndex(cx, clone, 0)) {
3748	0	cx->newborn[GCX_OBJECT] = NULL;
3749	0	return NULL;
3750		}
3751	0	HOLD_REGEXP(cx, re);
3752	0	return clone;
3753		}
3754
3755		JSBool
3756		js_GetLastIndex(JSContext *cx, JSObject *obj, jsdouble *lastIndex)
3757	0	{
3758	0	jsval v;
3759
3760	0	return JS_GetReservedSlot(cx, obj, 0, &v) &&
3761		js_ValueToNumber(cx, v, lastIndex);
3762		}
3763
3764		JSBool
3765		js_SetLastIndex(JSContext *cx, JSObject *obj, jsdouble lastIndex)
3766	0	{
3767	0	jsval v;
3768
3769	0	return js_NewNumberValue(cx, lastIndex, &v) &&
3770		JS_SetReservedSlot(cx, obj, 0, v);
3771		}
3772