1		/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2		* vim: set sw=4 ts=8 et tw=80:
3		*
4		* ***** BEGIN LICENSE BLOCK *****
5		* Version: MPL 1.1/GPL 2.0/LGPL 2.1
6		*
7		* The contents of this file are subject to the Mozilla Public License Version
8		* 1.1 (the "License"); you may not use this file except in compliance with
9		* the License. You may obtain a copy of the License at
10		* http://www.mozilla.org/MPL/
11		*
12		* Software distributed under the License is distributed on an "AS IS" basis,
13		* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14		* for the specific language governing rights and limitations under the
15		* License.
16		*
17		* The Original Code is Mozilla Communicator client code, released
18		* March 31, 1998.
19		*
20		* The Initial Developer of the Original Code is
21		* Netscape Communications Corporation.
22		* Portions created by the Initial Developer are Copyright (C) 1998
23		* the Initial Developer. All Rights Reserved.
24		*
25		* Contributor(s):
26		*
27		* Alternatively, the contents of this file may be used under the terms of
28		* either of the GNU General Public License Version 2 or later (the "GPL"),
29		* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30		* in which case the provisions of the GPL or the LGPL are applicable instead
31		* of those above. If you wish to allow use of your version of this file only
32		* under the terms of either the GPL or the LGPL, and not to allow others to
33		* use your version of this file under the terms of the MPL, indicate your
34		* decision by deleting the provisions above and replace them with the notice
35		* and other provisions required by the GPL or the LGPL. If you do not delete
36		* the provisions above, a recipient may use your version of this file under
37		* the terms of any one of the MPL, the GPL or the LGPL.
38		*
39		* ***** END LICENSE BLOCK ***** */
40
41		/*
42		* JS regular expressions, after Perl.
43		*/
44		#include "jsstddef.h"
45		#include <stdlib.h>
46		#include <string.h>
47		#include "jstypes.h"
48		#include "jsarena.h" /* Added by JSIFY */
49		#include "jsutil.h" /* Added by JSIFY */
50		#include "jsapi.h"
51		#include "jsarray.h"
52		#include "jsatom.h"
53		#include "jscntxt.h"
54		#include "jsconfig.h"
55		#include "jsfun.h"
56		#include "jsgc.h"
57		#include "jsinterp.h"
58		#include "jslock.h"
59		#include "jsnum.h"
60		#include "jsobj.h"
61		#include "jsopcode.h"
62		#include "jsregexp.h"
63		#include "jsscan.h"
64		#include "jsstr.h"
65
66		#if JS_HAS_REGEXPS
67
68		/* Note : contiguity of 'simple opcodes' is important for SimpleMatch() */
69		typedef enum REOp {
70		REOP_EMPTY         = 0,  /* match rest of input against rest of r.e. */
71		REOP_ALT           = 1,  /* alternative subexpressions in kid and next */
72		REOP_SIMPLE_START  = 2,  /* start of 'simple opcodes' */
73		REOP_BOL           = 2,  /* beginning of input (or line if multiline) */
74		REOP_EOL           = 3,  /* end of input (or line if multiline) */
75		REOP_WBDRY         = 4,  /* match "" at word boundary */
76		REOP_WNONBDRY      = 5,  /* match "" at word non-boundary */
77		REOP_DOT           = 6,  /* stands for any character */
78		REOP_DIGIT         = 7,  /* match a digit char: [0-9] */
79		REOP_NONDIGIT      = 8,  /* match a non-digit char: [^0-9] */
80		REOP_ALNUM         = 9,  /* match an alphanumeric char: [0-9a-z_A-Z] */
81		REOP_NONALNUM      = 10, /* match a non-alphanumeric char: [^0-9a-z_A-Z] */
82		REOP_SPACE         = 11, /* match a whitespace char */
83		REOP_NONSPACE      = 12, /* match a non-whitespace char */
84		REOP_BACKREF       = 13, /* back-reference (e.g., \1) to a parenthetical */
85		REOP_FLAT          = 14, /* match a flat string */
86		REOP_FLAT1         = 15, /* match a single char */
87		REOP_FLATi         = 16, /* case-independent REOP_FLAT */
88		REOP_FLAT1i        = 17, /* case-independent REOP_FLAT1 */
89		REOP_UCFLAT1       = 18, /* single Unicode char */
90		REOP_UCFLAT1i      = 19, /* case-independent REOP_UCFLAT1 */
91		REOP_UCFLAT        = 20, /* flat Unicode string; len immediate counts chars */
92		REOP_UCFLATi       = 21, /* case-independent REOP_UCFLAT */
93		REOP_CLASS         = 22, /* character class with index */
94		REOP_NCLASS        = 23, /* negated character class with index */
95		REOP_SIMPLE_END    = 23, /* end of 'simple opcodes' */
96		REOP_QUANT         = 25, /* quantified atom: atom{1,2} */
97		REOP_STAR          = 26, /* zero or more occurrences of kid */
98		REOP_PLUS          = 27, /* one or more occurrences of kid */
99		REOP_OPT           = 28, /* optional subexpression in kid */
100		REOP_LPAREN        = 29, /* left paren bytecode: kid is u.num'th sub-regexp */
101		REOP_RPAREN        = 30, /* right paren bytecode */
102		REOP_JUMP          = 31, /* for deoptimized closure loops */
103		REOP_DOTSTAR       = 32, /* optimize .* to use a single opcode */
104		REOP_ANCHOR        = 33, /* like .* but skips left context to unanchored r.e. */
105		REOP_EOLONLY       = 34, /* $ not preceded by any pattern */
106		REOP_BACKREFi      = 37, /* case-independent REOP_BACKREF */
107		REOP_LPARENNON     = 41, /* non-capturing version of REOP_LPAREN */
108		REOP_ASSERT        = 43, /* zero width positive lookahead assertion */
109		REOP_ASSERT_NOT    = 44, /* zero width negative lookahead assertion */
110		REOP_ASSERTTEST    = 45, /* sentinel at end of assertion child */
111		REOP_ASSERTNOTTEST = 46, /* sentinel at end of !assertion child */
112		REOP_MINIMALSTAR   = 47, /* non-greedy version of * */
113		REOP_MINIMALPLUS   = 48, /* non-greedy version of + */
114		REOP_MINIMALOPT    = 49, /* non-greedy version of ? */
115		REOP_MINIMALQUANT  = 50, /* non-greedy version of {} */
116		REOP_ENDCHILD      = 51, /* sentinel at end of quantifier child */
117		REOP_REPEAT        = 52, /* directs execution of greedy quantifier */
118		REOP_MINIMALREPEAT = 53, /* directs execution of non-greedy quantifier */
119		REOP_ALTPREREQ     = 54, /* prerequisite for ALT, either of two chars */
120		REOP_ALTPREREQ2    = 55, /* prerequisite for ALT, a char or a class */
121		REOP_ENDALT        = 56, /* end of final alternate */
122		REOP_CONCAT        = 57, /* concatenation of terms (parse time only) */
123
124		REOP_END
125		} REOp;
126
127		#define REOP_IS_SIMPLE(op)  ((unsigned)((op) - REOP_SIMPLE_START) <           \
128		(unsigned)REOP_SIMPLE_END)
129
130		struct RENode {
131		REOp            op;         /* r.e. op bytecode */
132		RENode          *next;      /* next in concatenation order */
133		void            *kid;       /* first operand */
134		union {
135		void        *kid2;      /* second operand */
136		jsint       num;        /* could be a number */
137		size_t      parenIndex; /* or a parenthesis index */
138		struct {                /* or a quantifier range */
139		uintN  min;
140		uintN  max;
141		JSPackedBool greedy;
142		} range;
143		struct {                /* or a character class */
144		size_t  startIndex;
145		size_t  kidlen;     /* length of string at kid, in jschars */
146		size_t  index;      /* index into class list */
147		uint16  bmsize;     /* bitmap size, based on max char code */
148		JSPackedBool sense;
149		} ucclass;
150		struct {                /* or a literal sequence */
151		jschar  chr;        /* of one character */
152		size_t  length;     /* or many (via the kid) */
153		} flat;
154		struct {
155		RENode  *kid2;      /* second operand from ALT */
156		jschar  ch1;        /* match char for ALTPREREQ */
157		jschar  ch2;        /* ditto, or class index for ALTPREREQ2 */
158		} altprereq;
159		} u;
160		};
161
162		#define RE_IS_LETTER(c)     (((c >= 'A') && (c <= 'Z')) ||                    \
163		((c >= 'a') && (c <= 'z')) )
164		#define RE_IS_LINE_TERM(c)  ((c == '\n') || (c == '\r') ||                    \
165		(c == LINE_SEPARATOR) || (c == PARA_SEPARATOR))
166
167		#define CLASS_CACHE_SIZE    4
168
169		typedef struct CompilerState {
170		JSContext       *context;
171		JSTokenStream   *tokenStream; /* For reporting errors */
172		const jschar    *cpbegin;
173		const jschar    *cpend;
174		const jschar    *cp;
175		size_t          parenCount;
176		size_t          classCount;   /* number of [] encountered */
177		size_t          treeDepth;    /* maximum depth of parse tree */
178		size_t          progLength;   /* estimated bytecode length */
179		RENode          *result;
180		size_t          classBitmapsMem; /* memory to hold all class bitmaps */
181		struct {
182		const jschar *start;        /* small cache of class strings */
183		size_t length;              /* since they're often the same */
184		size_t index;
185		} classCache[CLASS_CACHE_SIZE];
186		uint16          flags;
187		} CompilerState;
188
189		typedef struct EmitStateStackEntry {
190		jsbytecode      *altHead;       /* start of REOP_ALT* opcode */
191		jsbytecode      *nextAltFixup;  /* fixup pointer to next-alt offset */
192		jsbytecode      *nextTermFixup; /* fixup ptr. to REOP_JUMP offset */
193		jsbytecode      *endTermFixup;  /* fixup ptr. to REOPT_ALTPREREQ* offset */
194		RENode          *continueNode;  /* original REOP_ALT* node being stacked */
195		jsbytecode      continueOp;     /* REOP_JUMP or REOP_ENDALT continuation */
196		JSPackedBool    jumpToJumpFlag; /* true if we've patched jump-to-jump to
197		avoid 16-bit unsigned offset overflow */
198		} EmitStateStackEntry;
199
200		/*
201		* Immediate operand sizes and getter/setters.  Unlike the ones in jsopcode.h,
202		* the getters and setters take the pc of the offset, not of the opcode before
203		* the offset.
204		*/
205		#define ARG_LEN             2
206		#define GET_ARG(pc)         ((uint16)(((pc)[0] << 8) | (pc)[1]))
207		#define SET_ARG(pc, arg)    ((pc)[0] = (jsbytecode) ((arg) >> 8),       \
208		(pc)[1] = (jsbytecode) (arg))
209
210		#define OFFSET_LEN          ARG_LEN
211		#define OFFSET_MAX          (JS_BIT(ARG_LEN * 8) - 1)
212		#define GET_OFFSET(pc)      GET_ARG(pc)
213
214		/*
215		* Maximum supported tree depth is maximum size of EmitStateStackEntry stack.
216		* For sanity, we limit it to 2^24 bytes.
217		*/
218		#define TREE_DEPTH_MAX  (JS_BIT(24) / sizeof(EmitStateStackEntry))
219
220		/*
221		* The maximum memory that can be allocated for class bitmaps.
222		* For sanity, we limit it to 2^24 bytes.
223		*/
224		#define CLASS_BITMAPS_MEM_LIMIT JS_BIT(24)
225
226		/*
227		* Functions to get size and write/read bytecode that represent small indexes
228		* compactly.
229		* Each byte in the code represent 7-bit chunk of the index. 8th bit when set
230		* indicates that the following byte brings more bits to the index. Otherwise
231		* this is the last byte in the index bytecode representing highest index bits.
232		*/
233		static size_t
234		GetCompactIndexWidth(size_t index)
235	737920	{
236	737920	size_t width;
237
238	737920	for (width = 1; (index >>= 7) != 0; ++width) { }
239	737920	return width;
240		}
241
242		static jsbytecode *
243		WriteCompactIndex(jsbytecode *pc, size_t index)
244	1475712	{
245	1475712	size_t next;
246
247	1874916	while ((next = index >> 7) != 0) {
248	399204	*pc++ = (jsbytecode)(index | 0x80);
249	399204	index = next;
250		}
251	1475712	*pc++ = (jsbytecode)index;
252	1475712	return pc;
253		}
254
255		static jsbytecode *
256		ReadCompactIndex(jsbytecode *pc, size_t *result)
257	2441202	{
258	2441202	size_t nextByte;
259
260	2441202	nextByte = *pc++;
261	2441202	if ((nextByte & 0x80) == 0) {
262		/*
263		* Short-circuit the most common case when compact index <= 127.
264		*/
265	2072634	*result = nextByte;
266		} else {
267	368568	size_t shift = 7;
268	368568	*result = 0x7F & nextByte;
269	368568	do {
270	368568	nextByte = *pc++;
271	368568	*result |= (nextByte & 0x7F) << shift;
272	368568	shift += 7;
273	368568	} while ((nextByte & 0x80) != 0);
274		}
275	2441202	return pc;
276		}
277
278		typedef struct RECapture {
279		ptrdiff_t index;           /* start of contents, -1 for empty  */
280		size_t length;             /* length of capture */
281		} RECapture;
282
283		typedef struct REMatchState {
284		const jschar *cp;
285		RECapture parens[1];      /* first of 're->parenCount' captures,
286		allocated at end of this struct */
287		} REMatchState;
288
289		struct REBackTrackData;
290
291		typedef struct REProgState {
292		jsbytecode *continue_pc;        /* current continuation data */
293		jsbytecode continue_op;
294		ptrdiff_t index;                /* progress in text */
295		size_t parenSoFar;              /* highest indexed paren started */
296		union {
297		struct {
298		uintN min;             /* current quantifier limits */
299		uintN max;
300		} quantifier;
301		struct {
302		size_t top;             /* backtrack stack state */
303		size_t sz;
304		} assertion;
305		} u;
306		} REProgState;
307
308		typedef struct REBackTrackData {
309		size_t sz;                      /* size of previous stack entry */
310		jsbytecode *backtrack_pc;       /* where to backtrack to */
311		jsbytecode backtrack_op;
312		const jschar *cp;               /* index in text of match at backtrack */
313		size_t parenIndex;              /* start index of saved paren contents */
314		size_t parenCount;              /* # of saved paren contents */
315		size_t saveStateStackTop;       /* number of parent states */
316		/* saved parent states follow */
317		/* saved paren contents follow */
318		} REBackTrackData;
319
320		#define INITIAL_STATESTACK  100
321		#define INITIAL_BACKTRACK   8000
322
323		typedef struct REGlobalData {
324		JSContext *cx;
325		JSRegExp *regexp;               /* the RE in execution */
326		JSBool ok;                      /* runtime error (out_of_memory only?) */
327		size_t start;                   /* offset to start at */
328		ptrdiff_t skipped;              /* chars skipped anchoring this r.e. */
329		const jschar    *cpbegin;       /* text base address */
330		const jschar    *cpend;         /* text limit address */
331
332		REProgState *stateStack;        /* stack of state of current parents */
333		size_t stateStackTop;
334		size_t stateStackLimit;
335
336		REBackTrackData *backTrackStack;/* stack of matched-so-far positions */
337		REBackTrackData *backTrackSP;
338		size_t backTrackStackSize;
339		size_t cursz;                   /* size of current stack entry */
340
341		JSArenaPool     pool;           /* It's faster to use one malloc'd pool
342		than to malloc/free the three items
343		that are allocated from this pool */
344		} REGlobalData;
345
346		/*
347		* 1. If IgnoreCase is false, return ch.
348		* 2. Let u be ch converted to upper case as if by calling
349		*    String.prototype.toUpperCase on the one-character string ch.
350		* 3. If u does not consist of a single character, return ch.
351		* 4. Let cu be u's character.
352		* 5. If ch's code point value is greater than or equal to decimal 128 and cu's
353		*    code point value is less than decimal 128, then return ch.
354		* 6. Return cu.
355		*/
356		static jschar
357		upcase(jschar ch)
358	0	{
359	0	jschar cu = JS_TOUPPER(ch);
360	0	if (ch >= 128 && cu < 128)
361	0	return ch;
362	0	return cu;
363		}
364
365		static jschar
366		downcase(jschar ch)
367	0	{
368	0	jschar cl = JS_TOLOWER(ch);
369	0	if (cl >= 128 && ch < 128)
370	0	return ch;
371	0	return cl;
372		}
373
374		/* Construct and initialize an RENode, returning NULL for out-of-memory */
375		static RENode *
376		NewRENode(CompilerState *state, REOp op)
377	4764620	{
378	4764620	JSContext *cx;
379	4764620	RENode *ren;
380
381	4764620	cx = state->context;
382	4764620	JS_ARENA_ALLOCATE_CAST(ren, RENode *, &cx->tempPool, sizeof *ren);
383	4764620	if (!ren) {
384	0	JS_ReportOutOfMemory(cx);
385	0	return NULL;
386		}
387	4764620	ren->op = op;
388	4764620	ren->next = NULL;
389	4764620	ren->kid = NULL;
390	4764620	return ren;
391		}
392
393		/*
394		* Validates and converts hex ascii value.
395		*/
396		static JSBool
397		isASCIIHexDigit(jschar c, uintN *digit)
398	0	{
399	0	uintN cv = c;
400
401	0	if (cv < '0')
402	0	return JS_FALSE;
403	0	if (cv <= '9') {
404	0	*digit = cv - '0';
405	0	return JS_TRUE;
406		}
407	0	cv |= 0x20;
408	0	if (cv >= 'a' && cv <= 'f') {
409	0	*digit = cv - 'a' + 10;
410	0	return JS_TRUE;
411		}
412	0	return JS_FALSE;
413		}
414
415
416		typedef struct {
417		REOp op;
418		const jschar *errPos;
419		size_t parenIndex;
420		} REOpData;
421
422
423		/*
424		* Process the op against the two top operands, reducing them to a single
425		* operand in the penultimate slot. Update progLength and treeDepth.
426		*/
427		static JSBool
428		ProcessOp(CompilerState *state, REOpData *opData, RENode **operandStack,
429		intN operandSP)
430	4027132	{
431	4027132	RENode *result;
432
433	4027132	switch (opData->op) {
434		case REOP_ALT:
435	706348	result = NewRENode(state, REOP_ALT);
436	706348	if (!result)
437	0	return JS_FALSE;
438	706348	result->kid = operandStack[operandSP - 2];
439	706348	result->u.kid2 = operandStack[operandSP - 1];
440	706348	operandStack[operandSP - 2] = result;
441
442	706348	if (state->treeDepth == TREE_DEPTH_MAX) {
443	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
444		JSREPORT_TS | JSREPORT_ERROR,
445		JSMSG_REGEXP_TOO_COMPLEX);
446	0	return JS_FALSE;
447		}
448	706348	++state->treeDepth;
449
450		/*
451		* Look at both alternates to see if there's a FLAT or a CLASS at
452		* the start of each. If so, use a prerequisite match.
453		*/
454	706348	if (((RENode *) result->kid)->op == REOP_FLAT &&
455		((RENode *) result->u.kid2)->op == REOP_FLAT &&
456		(state->flags & JSREG_FOLD) == 0) {
457	15386	result->op = REOP_ALTPREREQ;
458	15386	result->u.altprereq.ch1 = ((RENode *) result->kid)->u.flat.chr;
459	15386	result->u.altprereq.ch2 = ((RENode *) result->u.kid2)->u.flat.chr;
460		/* ALTPREREQ, <end>, uch1, uch2, <next>, ...,
461		JUMP, <end> ... ENDALT */
462	15386	state->progLength += 13;
463		}
464		else
465	690962	if (((RENode *) result->kid)->op == REOP_CLASS &&
466		((RENode *) result->kid)->u.ucclass.index < 256 &&
467		((RENode *) result->u.kid2)->op == REOP_FLAT &&
468		(state->flags & JSREG_FOLD) == 0) {
469	0	result->op = REOP_ALTPREREQ2;
470	0	result->u.altprereq.ch1 = ((RENode *) result->u.kid2)->u.flat.chr;
471	0	result->u.altprereq.ch2 = ((RENode *) result->kid)->u.ucclass.index;
472		/* ALTPREREQ2, <end>, uch1, uch2, <next>, ...,
473		JUMP, <end> ... ENDALT */
474	0	state->progLength += 13;
475		}
476		else
477	690962	if (((RENode *) result->kid)->op == REOP_FLAT &&
478		((RENode *) result->u.kid2)->op == REOP_CLASS &&
479		((RENode *) result->u.kid2)->u.ucclass.index < 256 &&
480		(state->flags & JSREG_FOLD) == 0) {
481	0	result->op = REOP_ALTPREREQ2;
482	0	result->u.altprereq.ch1 = ((RENode *) result->kid)->u.flat.chr;
483	0	result->u.altprereq.ch2 =
484		((RENode *) result->u.kid2)->u.ucclass.index;
485		/* ALTPREREQ2, <end>, uch1, uch2, <next>, ...,
486		JUMP, <end> ... ENDALT */
487	0	state->progLength += 13;
488		}
489		else {
490		/* ALT, <next>, ..., JUMP, <end> ... ENDALT */
491	690962	state->progLength += 7;
492		}
493	690962	break;
494
495		case REOP_CONCAT:
496	3320784	result = operandStack[operandSP - 2];
497	3320784	while (result->next)
498	0	result = result->next;
499	3320784	result->next = operandStack[operandSP - 1];
500	3320784	break;
501
502		case REOP_ASSERT:
503		case REOP_ASSERT_NOT:
504		case REOP_LPARENNON:
505		case REOP_LPAREN:
506		/* These should have been processed by a close paren. */
507	0	js_ReportCompileErrorNumberUC(state->context, state->tokenStream,
508		JSREPORT_TS | JSREPORT_ERROR,
509		JSMSG_MISSING_PAREN, opData->errPos);
510	0	return JS_FALSE;
511
512		default:;
513		}
514	4027132	return JS_TRUE;
515		}
516
517		/*
518		* Parser forward declarations.
519		*/
520		static JSBool ParseTerm(CompilerState *state);
521		static JSBool ParseQuantifier(CompilerState *state);
522		static intN ParseMinMaxQuantifier(CompilerState *state, JSBool ignoreValues);
523
524		/*
525		* Top-down regular expression grammar, based closely on Perl4.
526		*
527		*  regexp:     altern                  A regular expression is one or more
528		*              altern '|' regexp       alternatives separated by vertical bar.
529		*/
530		#define INITIAL_STACK_SIZE  128
531
532		static JSBool
533		ParseRegExp(CompilerState *state)
534	15754	{
535	15754	size_t parenIndex;
536	15754	RENode *operand;
537	15754	REOpData *operatorStack;
538	15754	RENode **operandStack;
539	15754	REOp op;
540	15754	intN i;
541	15754	JSBool result = JS_FALSE;
542
543	15754	intN operatorSP = 0, operatorStackSize = INITIAL_STACK_SIZE;
544	15754	intN operandSP = 0, operandStackSize = INITIAL_STACK_SIZE;
545
546		/* Watch out for empty regexp */
547	15754	if (state->cp == state->cpend) {
548	16	state->result = NewRENode(state, REOP_EMPTY);
549	16	return (state->result != NULL);
550		}
551
552	15738	operatorStack = (REOpData *)
553		JS_malloc(state->context, sizeof(REOpData) * operatorStackSize);
554	15738	if (!operatorStack)
555	0	return JS_FALSE;
556
557	15738	operandStack = (RENode **)
558		JS_malloc(state->context, sizeof(RENode *) * operandStackSize);
559	15738	if (!operandStack)
560	0	goto out;
561
562	8100774	for (;;) {
563	4058256	parenIndex = state->parenCount;
564	4058256	if (state->cp == state->cpend) {
565		/*
566		* If we are at the end of the regexp and we're short one or more
567		* operands, the regexp must have the form /x|/ or some such, with
568		* left parentheses making us short more than one operand.
569		*/
570	0	if (operatorSP >= operandSP) {
571	0	operand = NewRENode(state, REOP_EMPTY);
572	0	if (!operand)
573	0	goto out;
574	4058256	goto pushOperand;
575		}
576		} else {
577	4058256	switch (*state->cp) {
578		case '(':
579	15386	++state->cp;
580	15386	if (state->cp + 1 < state->cpend &&
581		*state->cp == '?' &&
582		(state->cp[1] == '=' ||
583		state->cp[1] == '!' ||
584		state->cp[1] == ':')) {
585	0	switch (state->cp[1]) {
586		case '=':
587	0	op = REOP_ASSERT;
588		/* ASSERT, <next>, ... ASSERTTEST */
589	0	state->progLength += 4;
590	0	break;
591		case '!':
592	0	op = REOP_ASSERT_NOT;
593		/* ASSERTNOT, <next>, ... ASSERTNOTTEST */
594	0	state->progLength += 4;
595	0	break;
596		default:
597	0	op = REOP_LPARENNON;
598	0	break;
599		}
600	0	state->cp += 2;
601		} else {
602	15386	op = REOP_LPAREN;
603		/* LPAREN, <index>, ... RPAREN, <index> */
604	15386	state->progLength
605		+= 2 * (1 + GetCompactIndexWidth(parenIndex));
606	15386	state->parenCount++;
607	15386	if (state->parenCount == 65535) {
608	0	js_ReportCompileErrorNumber(state->context,
609		state->tokenStream,
610		JSREPORT_TS |
611		JSREPORT_ERROR,
612		JSMSG_TOO_MANY_PARENS);
613	0	goto out;
614		}
615		}
616	0	goto pushOperator;
617
618		case ')':
619		/*
620		* If there's no stacked open parenthesis, throw syntax error.
621		*/
622	0	for (i = operatorSP - 1; ; i--) {
623	0	if (i < 0) {
624	0	js_ReportCompileErrorNumber(state->context,
625		state->tokenStream,
626		JSREPORT_TS |
627		JSREPORT_ERROR,
628		JSMSG_UNMATCHED_RIGHT_PAREN);
629	0	goto out;
630		}
631	0	if (operatorStack[i].op == REOP_ASSERT ||
632		operatorStack[i].op == REOP_ASSERT_NOT ||
633		operatorStack[i].op == REOP_LPARENNON ||
634		operatorStack[i].op == REOP_LPAREN) {
635	0	break;
636		}
637		}
638		/* FALL THROUGH */
639
640		case '|':
641		/* Expected an operand before these, so make an empty one */
642	0	operand = NewRENode(state, REOP_EMPTY);
643	0	if (!operand)
644	0	goto out;
645	4042870	goto pushOperand;
646
647		default:
648	4042870	if (!ParseTerm(state))
649	0	goto out;
650	4042870	operand = state->result;
651		pushOperand:
652	4042870	if (operandSP == operandStackSize) {
653	0	operandStackSize += operandStackSize;
654	0	operandStack = (RENode **)
655		JS_realloc(state->context, operandStack,
656		sizeof(RENode *) * operandStackSize);
657	0	if (!operandStack)
658	0	goto out;
659		}
660	4042870	operandStack[operandSP++] = operand;
661	4058256	break;
662		}
663		}
664
665		/* At the end; process remaining operators. */
666		restartOperator:
667	4058256	if (state->cp == state->cpend) {
668	50446	while (operatorSP) {
669	34708	--operatorSP;
670	34708	if (!ProcessOp(state, &operatorStack[operatorSP],
671		operandStack, operandSP))
672	0	goto out;
673	34708	--operandSP;
674		}
675	15738	JS_ASSERT(operandSP == 1);
676	15738	state->result = operandStack[0];
677	15738	result = JS_TRUE;
678	15738	goto out;
679		}
680
681	4042518	switch (*state->cp) {
682		case '|':
683		/* Process any stacked 'concat' operators */
684	706348	++state->cp;
685	3915526	while (operatorSP &&
686		operatorStack[operatorSP - 1].op == REOP_CONCAT) {
687	3209178	--operatorSP;
688	3209178	if (!ProcessOp(state, &operatorStack[operatorSP],
689		operandStack, operandSP)) {
690	0	goto out;
691		}
692	3209178	--operandSP;
693		}
694	706348	op = REOP_ALT;
695	706348	goto pushOperator;
696
697		case ')':
698		/*
699		* If there's no stacked open parenthesis, throw syntax error.
700		*/
701	798632	for (i = operatorSP - 1; ; i--) {
702	798632	if (i < 0) {
703	0	js_ReportCompileErrorNumber(state->context,
704		state->tokenStream,
705		JSREPORT_TS | JSREPORT_ERROR,
706		JSMSG_UNMATCHED_RIGHT_PAREN);
707	0	goto out;
708		}
709	798632	if (operatorStack[i].op == REOP_ASSERT ||
710		operatorStack[i].op == REOP_ASSERT_NOT ||
711		operatorStack[i].op == REOP_LPARENNON ||
712		operatorStack[i].op == REOP_LPAREN) {
713	783246	break;
714		}
715		}
716	15386	++state->cp;
717
718		/* Process everything on the stack until the open parenthesis. */
719	1581878	for (;;) {
720	798632	JS_ASSERT(operatorSP);
721	798632	--operatorSP;
722	798632	switch (operatorStack[operatorSP].op) {
723		case REOP_ASSERT:
724		case REOP_ASSERT_NOT:
725		case REOP_LPAREN:
726	15386	operand = NewRENode(state, operatorStack[operatorSP].op);
727	15386	if (!operand)
728	0	goto out;
729	15386	operand->u.parenIndex =
730		operatorStack[operatorSP].parenIndex;
731	15386	JS_ASSERT(operandSP);
732	15386	operand->kid = operandStack[operandSP - 1];
733	15386	operandStack[operandSP - 1] = operand;
734	15386	if (state->treeDepth == TREE_DEPTH_MAX) {
735	0	js_ReportCompileErrorNumber(state->context,
736		state->tokenStream,
737		JSREPORT_TS |
738		JSREPORT_ERROR,
739		JSMSG_REGEXP_TOO_COMPLEX);
740	0	goto out;
741		}
742	15386	++state->treeDepth;
743		/* FALL THROUGH */
744
745		case REOP_LPARENNON:
746	15386	state->result = operandStack[operandSP - 1];
747	15386	if (!ParseQuantifier(state))
748	0	goto out;
749	15386	operandStack[operandSP - 1] = state->result;
750	15386	goto restartOperator;
751		default:
752	783246	if (!ProcessOp(state, &operatorStack[operatorSP],
753		operandStack, operandSP))
754	0	goto out;
755	783246	--operandSP;
756	783246	break;
757		}
758		}
759	0	break;
760
761		case '{':
762		{
763	0	const jschar *errp = state->cp;
764
765	0	if (ParseMinMaxQuantifier(state, JS_TRUE) < 0) {
766		/*
767		* This didn't even scan correctly as a quantifier, so we should
768		* treat it as flat.
769		*/
770	0	op = REOP_CONCAT;
771	0	goto pushOperator;
772		}
773
774	0	state->cp = errp;
775		/* FALL THROUGH */
776		}
777
778		case '+':
779		case '*':
780		case '?':
781	0	js_ReportCompileErrorNumberUC(state->context, state->tokenStream,
782		JSREPORT_TS | JSREPORT_ERROR,
783		JSMSG_BAD_QUANTIFIER, state->cp);
784	0	result = JS_FALSE;
785	0	goto out;
786
787		default:
788		/* Anything else is the start of the next term. */
789	3320784	op = REOP_CONCAT;
790		pushOperator:
791	4042518	if (operatorSP == operatorStackSize) {
792	0	operatorStackSize += operatorStackSize;
793	0	operatorStack = (REOpData *)
794		JS_realloc(state->context, operatorStack,
795		sizeof(REOpData) * operatorStackSize);
796	0	if (!operatorStack)
797	0	goto out;
798		}
799	4042518	operatorStack[operatorSP].op = op;
800	4042518	operatorStack[operatorSP].errPos = state->cp;
801	4042518	operatorStack[operatorSP++].parenIndex = parenIndex;
802	4042518	break;
803		}
804		}
805		out:
806	15738	if (operatorStack)
807	15738	JS_free(state->context, operatorStack);
808	15738	if (operandStack)
809	15738	JS_free(state->context, operandStack);
810	15738	return result;
811		}
812
813		/*
814		* Hack two bits in CompilerState.flags, for use within FindParenCount to flag
815		* its being on the stack, and to propagate errors to its callers.
816		*/
817		#define JSREG_FIND_PAREN_COUNT  0x8000
818		#define JSREG_FIND_PAREN_ERROR  0x4000
819
820		/*
821		* Magic return value from FindParenCount and GetDecimalValue, to indicate
822		* overflow beyond GetDecimalValue's max parameter, or a computed maximum if
823		* its findMax parameter is non-null.
824		*/
825		#define OVERFLOW_VALUE          ((uintN)-1)
826
827		static uintN
828		FindParenCount(CompilerState *state)
829	0	{
830	0	CompilerState temp;
831	0	int i;
832
833	0	if (state->flags & JSREG_FIND_PAREN_COUNT)
834	0	return OVERFLOW_VALUE;
835
836		/*
837		* Copy state into temp, flag it so we never report an invalid backref,
838		* and reset its members to parse the entire regexp.  This is obviously
839		* suboptimal, but GetDecimalValue calls us only if a backref appears to
840		* refer to a forward parenthetical, which is rare.
841		*/
842	0	temp = *state;
843	0	temp.flags |= JSREG_FIND_PAREN_COUNT;
844	0	temp.cp = temp.cpbegin;
845	0	temp.parenCount = 0;
846	0	temp.classCount = 0;
847	0	temp.progLength = 0;
848	0	temp.treeDepth = 0;
849	0	temp.classBitmapsMem = 0;
850	0	for (i = 0; i < CLASS_CACHE_SIZE; i++)
851	0	temp.classCache[i].start = NULL;
852
853	0	if (!ParseRegExp(&temp)) {
854	0	state->flags |= JSREG_FIND_PAREN_ERROR;
855	0	return OVERFLOW_VALUE;
856		}
857	0	return temp.parenCount;
858		}
859
860		/*
861		* Extract and return a decimal value at state->cp.  The initial character c
862		* has already been read.  Return OVERFLOW_VALUE if the result exceeds max.
863		* Callers who pass a non-null findMax should test JSREG_FIND_PAREN_ERROR in
864		* state->flags to discover whether an error occurred under findMax.
865		*/
866		static uintN
867		GetDecimalValue(jschar c, uintN max, uintN (*findMax)(CompilerState *state),
868		CompilerState *state)
869	0	{
870	0	uintN value = JS7_UNDEC(c);
871	0	JSBool overflow = (value > max && (!findMax || value > findMax(state)));
872
873		/* The following restriction allows simpler overflow checks. */
874	0	JS_ASSERT(max <= ((uintN)-1 - 9) / 10);
875	0	while (state->cp < state->cpend) {
876	0	c = *state->cp;
877	0	if (!JS7_ISDEC(c))
878	0	break;
879	0	value = 10 * value + JS7_UNDEC(c);
880	0	if (!overflow && value > max && (!findMax || value > findMax(state)))
881	0	overflow = JS_TRUE;
882	0	++state->cp;
883		}
884	0	return overflow ? OVERFLOW_VALUE : value;
885		}
886
887		/*
888		* Calculate the total size of the bitmap required for a class expression.
889		*/
890		static JSBool
891		CalculateBitmapSize(CompilerState *state, RENode *target, const jschar *src,
892		const jschar *end)
893	0	{
894	0	uintN max = 0;
895	0	JSBool inRange = JS_FALSE;
896	0	jschar c, rangeStart = 0;
897	0	uintN n, digit, nDigits, i;
898
899	0	target->u.ucclass.bmsize = 0;
900	0	target->u.ucclass.sense = JS_TRUE;
901
902	0	if (src == end)
903	0	return JS_TRUE;
904
905	0	if (*src == '^') {
906	0	++src;
907	0	target->u.ucclass.sense = JS_FALSE;
908		}
909
910	0	while (src != end) {
911	0	uintN localMax = 0;
912	0	switch (*src) {
913		case '\\':
914	0	++src;
915	0	c = *src++;
916	0	switch (c) {
917		case 'b':
918	0	localMax = 0x8;
919	0	break;
920		case 'f':
921	0	localMax = 0xC;
922	0	break;
923		case 'n':
924	0	localMax = 0xA;
925	0	break;
926		case 'r':
927	0	localMax = 0xD;
928	0	break;
929		case 't':
930	0	localMax = 0x9;
931	0	break;
932		case 'v':
933	0	localMax = 0xB;
934	0	break;
935		case 'c':
936	0	if (src + 1 < end && RE_IS_LETTER(src[1]))
937	0	localMax = (jschar) (*src++ & 0x1F);
938		else
939	0	localMax = '\\';
940	0	break;
941		case 'x':
942	0	nDigits = 2;
943	0	goto lexHex;
944		case 'u':
945	0	nDigits = 4;
946		lexHex:
947	0	n = 0;
948	0	for (i = 0; (i < nDigits) && (src < end); i++) {
949	0	c = *src++;
950	0	if (!isASCIIHexDigit(c, &digit)) {
951		/*
952		* Back off to accepting the original
953		*'\' as a literal.
954		*/
955	0	src -= i + 1;
956	0	n = '\\';
957	0	break;
958		}
959	0	n = (n << 4) | digit;
960		}
961	0	localMax = n;
962	0	break;
963		case 'd':
964	0	if (inRange) {
965	0	JS_ReportErrorNumber(state->context,
966		js_GetErrorMessage, NULL,
967		JSMSG_BAD_CLASS_RANGE);
968	0	return JS_FALSE;
969		}
970	0	localMax = '9';
971	0	break;
972		case 'D':
973		case 's':
974		case 'S':
975		case 'w':
976		case 'W':
977	0	if (inRange) {
978	0	JS_ReportErrorNumber(state->context,
979		js_GetErrorMessage, NULL,
980		JSMSG_BAD_CLASS_RANGE);
981	0	return JS_FALSE;
982		}
983	0	target->u.ucclass.bmsize = 65535;
984	0	return JS_TRUE;
985		case '0':
986		case '1':
987		case '2':
988		case '3':
989		case '4':
990		case '5':
991		case '6':
992		case '7':
993		/*
994		*  This is a non-ECMA extension - decimal escapes (in this
995		*  case, octal!) are supposed to be an error inside class
996		*  ranges, but supported here for backwards compatibility.
997		*
998		*/
999	0	n = JS7_UNDEC(c);
1000	0	c = *src;
1001	0	if ('0' <= c && c <= '7') {
1002	0	src++;
1003	0	n = 8 * n + JS7_UNDEC(c);
1004	0	c = *src;
1005	0	if ('0' <= c && c <= '7') {
1006	0	src++;
1007	0	i = 8 * n + JS7_UNDEC(c);
1008	0	if (i <= 0377)
1009	0	n = i;
1010		else
1011	0	src--;
1012		}
1013		}
1014	0	localMax = n;
1015	0	break;
1016
1017		default:
1018	0	localMax = c;
1019	0	break;
1020		}
1021	0	break;
1022		default:
1023	0	localMax = *src++;
1024	0	break;
1025		}
1026	0	if (inRange) {
1027	0	if (rangeStart > localMax) {
1028	0	JS_ReportErrorNumber(state->context,
1029		js_GetErrorMessage, NULL,
1030		JSMSG_BAD_CLASS_RANGE);
1031	0	return JS_FALSE;
1032		}
1033	0	inRange = JS_FALSE;
1034		} else {
1035	0	if (src < end - 1) {
1036	0	if (*src == '-') {
1037	0	++src;
1038	0	inRange = JS_TRUE;
1039	0	rangeStart = (jschar)localMax;
1040	0	continue;
1041		}
1042		}
1043		}
1044	0	if (state->flags & JSREG_FOLD) {
1045	0	c = JS_MAX(upcase((jschar)localMax), downcase((jschar)localMax));
1046	0	if (c > localMax)
1047	0	localMax = c;
1048		}
1049	0	if (localMax > max)
1050	0	max = localMax;
1051		}
1052	0	target->u.ucclass.bmsize = max;
1053	0	return JS_TRUE;
1054		}
1055
1056		/*
1057		*  item:       assertion               An item is either an assertion or
1058		*              quantatom               a quantified atom.
1059		*
1060		*  assertion:  '^'                     Assertions match beginning of string
1061		*                                      (or line if the class static property
1062		*                                      RegExp.multiline is true).
1063		*              '$'                     End of string (or line if the class
1064		*                                      static property RegExp.multiline is
1065		*                                      true).
1066		*              '\b'                    Word boundary (between \w and \W).
1067		*              '\B'                    Word non-boundary.
1068		*
1069		*  quantatom:  atom                    An unquantified atom.
1070		*              quantatom '{' n ',' m '}'
1071		*                                      Atom must occur between n and m times.
1072		*              quantatom '{' n ',' '}' Atom must occur at least n times.
1073		*              quantatom '{' n '}'     Atom must occur exactly n times.
1074		*              quantatom '*'           Zero or more times (same as {0,}).
1075		*              quantatom '+'           One or more times (same as {1,}).
1076		*              quantatom '?'           Zero or one time (same as {0,1}).
1077		*
1078		*              any of which can be optionally followed by '?' for ungreedy
1079		*
1080		*  atom:       '(' regexp ')'          A parenthesized regexp (what matched
1081		*                                      can be addressed using a backreference,
1082		*                                      see '\' n below).
1083		*              '.'                     Matches any char except '\n'.
1084		*              '[' classlist ']'       A character class.
1085		*              '[' '^' classlist ']'   A negated character class.
1086		*              '\f'                    Form Feed.
1087		*              '\n'                    Newline (Line Feed).
1088		*              '\r'                    Carriage Return.
1089		*              '\t'                    Horizontal Tab.
1090		*              '\v'                    Vertical Tab.
1091		*              '\d'                    A digit (same as [0-9]).
1092		*              '\D'                    A non-digit.
1093		*              '\w'                    A word character, [0-9a-z_A-Z].
1094		*              '\W'                    A non-word character.
1095		*              '\s'                    A whitespace character, [ \b\f\n\r\t\v].
1096		*              '\S'                    A non-whitespace character.
1097		*              '\' n                   A backreference to the nth (n decimal
1098		*                                      and positive) parenthesized expression.
1099		*              '\' octal               An octal escape sequence (octal must be
1100		*                                      two or three digits long, unless it is
1101		*                                      0 for the null character).
1102		*              '\x' hex                A hex escape (hex must be two digits).
1103		*              '\u' unicode            A unicode escape (must be four digits).
1104		*              '\c' ctrl               A control character, ctrl is a letter.
1105		*              '\' literalatomchar     Any character except one of the above
1106		*                                      that follow '\' in an atom.
1107		*              otheratomchar           Any character not first among the other
1108		*                                      atom right-hand sides.
1109		*/
1110		static JSBool
1111		ParseTerm(CompilerState *state)
1112	4042870	{
1113	4042870	jschar c = *state->cp++;
1114	4042870	uintN nDigits;
1115	4042870	uintN num, tmp, n, i;
1116	4042870	const jschar *termStart;
1117
1118	4042870	switch (c) {
1119		/* assertions and atoms */
1120		case '^':
1121	15418	state->result = NewRENode(state, REOP_BOL);
1122	15418	if (!state->result)
1123	0	return JS_FALSE;
1124	15418	state->progLength++;
1125	15418	return JS_TRUE;
1126		case '$':
1127	15354	state->result = NewRENode(state, REOP_EOL);
1128	15354	if (!state->result)
1129	0	return JS_FALSE;
1130	15354	state->progLength++;
1131	15354	return JS_TRUE;
1132		case '\\':
1133	352	if (state->cp >= state->cpend) {
1134		/* a trailing '\' is an error */
1135	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
1136		JSREPORT_TS | JSREPORT_ERROR,
1137		JSMSG_TRAILING_SLASH);
1138	0	return JS_FALSE;
1139		}
1140	352	c = *state->cp++;
1141	352	switch (c) {
1142		/* assertion escapes */
1143		case 'b' :
1144	0	state->result = NewRENode(state, REOP_WBDRY);
1145	0	if (!state->result)
1146	0	return JS_FALSE;
1147	0	state->progLength++;
1148	0	return JS_TRUE;
1149		case 'B':
1150	0	state->result = NewRENode(state, REOP_WNONBDRY);
1151	0	if (!state->result)
1152	0	return JS_FALSE;
1153	0	state->progLength++;
1154	0	return JS_TRUE;
1155		/* Decimal escape */
1156		case '0':
1157		/* Give a strict warning. See also the note below. */
1158	0	if (!js_ReportCompileErrorNumber(state->context,
1159		state->tokenStream,
1160		JSREPORT_TS |
1161		JSREPORT_WARNING |
1162		JSREPORT_STRICT,
1163		JSMSG_INVALID_BACKREF)) {
1164	0	return JS_FALSE;
1165		}
1166		doOctal:
1167	0	num = 0;
1168	0	while (state->cp < state->cpend) {
1169	0	c = *state->cp;
1170	0	if (c < '0' || '7' < c)
1171	0	break;
1172	0	state->cp++;
1173	0	tmp = 8 * num + (uintN)JS7_UNDEC(c);
1174	0	if (tmp > 0377)
1175	0	break;
1176	0	num = tmp;
1177		}
1178	0	c = (jschar)num;
1179		doFlat:
1180	0	state->result = NewRENode(state, REOP_FLAT);
1181	0	if (!state->result)
1182	0	return JS_FALSE;
1183	0	state->result->u.flat.chr = c;
1184	0	state->result->u.flat.length = 1;
1185	0	state->progLength += 3;
1186	0	break;
1187		case '1':
1188		case '2':
1189		case '3':
1190		case '4':
1191		case '5':
1192		case '6':
1193		case '7':
1194		case '8':
1195		case '9':
1196	0	termStart = state->cp - 1;
1197	0	num = GetDecimalValue(c, state->parenCount, FindParenCount, state);
1198	0	if (state->flags & JSREG_FIND_PAREN_ERROR)
1199	0	return JS_FALSE;
1200	0	if (num == OVERFLOW_VALUE) {
1201		/* Give a strict mode warning. */
1202	0	if (!js_ReportCompileErrorNumber(state->context,
1203		state->tokenStream,
1204		JSREPORT_TS |
1205		JSREPORT_WARNING |
1206		JSREPORT_STRICT,
1207		(c >= '8')
1208		? JSMSG_INVALID_BACKREF
1209		: JSMSG_BAD_BACKREF)) {
1210	0	return JS_FALSE;
1211		}
1212
1213		/*
1214		* Note: ECMA 262, 15.10.2.9 says that we should throw a syntax
1215		* error here. However, for compatibility with IE, we treat the
1216		* whole backref as flat if the first character in it is not a
1217		* valid octal character, and as an octal escape otherwise.
1218		*/
1219	0	state->cp = termStart;
1220	0	if (c >= '8') {
1221		/* Treat this as flat. termStart - 1 is the \. */
1222	0	c = '\\';
1223	0	goto asFlat;
1224		}
1225
1226		/* Treat this as an octal escape. */
1227	0	goto doOctal;
1228		}
1229	0	JS_ASSERT(1 <= num && num <= 0x10000);
1230	0	state->result = NewRENode(state, REOP_BACKREF);
1231	0	if (!state->result)
1232	0	return JS_FALSE;
1233	0	state->result->u.parenIndex = num - 1;
1234	0	state->progLength
1235		+= 1 + GetCompactIndexWidth(state->result->u.parenIndex);
1236	0	break;
1237		/* Control escape */
1238		case 'f':
1239	0	c = 0xC;
1240	0	goto doFlat;
1241		case 'n':
1242	0	c = 0xA;
1243	0	goto doFlat;
1244		case 'r':
1245	0	c = 0xD;
1246	0	goto doFlat;
1247		case 't':
1248	0	c = 0x9;
1249	0	goto doFlat;
1250		case 'v':
1251	0	c = 0xB;
1252	0	goto doFlat;
1253		/* Control letter */
1254		case 'c':
1255	0	if (state->cp + 1 < state->cpend && RE_IS_LETTER(state->cp[1])) {
1256	0	c = (jschar) (*state->cp++ & 0x1F);
1257		} else {
1258		/* back off to accepting the original '\' as a literal */
1259	0	--state->cp;
1260	0	c = '\\';
1261		}
1262	0	goto doFlat;
1263		/* HexEscapeSequence */
1264		case 'x':
1265	0	nDigits = 2;
1266	0	goto lexHex;
1267		/* UnicodeEscapeSequence */
1268		case 'u':
1269	0	nDigits = 4;
1270		lexHex:
1271	0	n = 0;
1272	0	for (i = 0; i < nDigits && state->cp < state->cpend; i++) {
1273	0	uintN digit;
1274	0	c = *state->cp++;
1275	0	if (!isASCIIHexDigit(c, &digit)) {
1276		/*
1277		* Back off to accepting the original 'u' or 'x' as a
1278		* literal.
1279		*/
1280	0	state->cp -= i + 2;
1281	0	n = *state->cp++;
1282	0	break;
1283		}
1284	0	n = (n << 4) | digit;
1285		}
1286	0	c = (jschar) n;
1287	0	goto doFlat;
1288		/* Character class escapes */
1289		case 'd':
1290	0	state->result = NewRENode(state, REOP_DIGIT);
1291		doSimple:
1292	64	if (!state->result)
1293	0	return JS_FALSE;
1294	64	state->progLength++;
1295	64	break;
1296		case 'D':
1297	0	state->result = NewRENode(state, REOP_NONDIGIT);
1298	0	goto doSimple;
1299		case 's':
1300	0	state->result = NewRENode(state, REOP_SPACE);
1301	0	goto doSimple;
1302		case 'S':
1303	0	state->result = NewRENode(state, REOP_NONSPACE);
1304	0	goto doSimple;
1305		case 'w':
1306	0	state->result = NewRENode(state, REOP_ALNUM);
1307	0	goto doSimple;
1308		case 'W':
1309	0	state->result = NewRENode(state, REOP_NONALNUM);
1310	0	goto doSimple;
1311		/* IdentityEscape */
1312		default:
1313	352	state->result = NewRENode(state, REOP_FLAT);
1314	352	if (!state->result)
1315	0	return JS_FALSE;
1316	352	state->result->u.flat.chr = c;
1317	352	state->result->u.flat.length = 1;
1318	352	state->result->kid = (void *) (state->cp - 1);
1319	352	state->progLength += 3;
1320	352	break;
1321		}
1322	352	break;
1323		case '[':
1324	0	state->result = NewRENode(state, REOP_CLASS);
1325	0	if (!state->result)
1326	0	return JS_FALSE;
1327	0	termStart = state->cp;
1328	0	state->result->u.ucclass.startIndex = termStart - state->cpbegin;
1329	0	for (;;) {
1330	0	if (state->cp == state->cpend) {
1331	0	js_ReportCompileErrorNumberUC(state->context, state->tokenStream,
1332		JSREPORT_TS | JSREPORT_ERROR,
1333		JSMSG_UNTERM_CLASS, termStart);
1334
1335	0	return JS_FALSE;
1336		}
1337	0	if (*state->cp == '\\') {
1338	0	state->cp++;
1339	0	if (state->cp != state->cpend)
1340	0	state->cp++;
1341	0	continue;
1342		}
1343	0	if (*state->cp == ']') {
1344	0	state->result->u.ucclass.kidlen = state->cp - termStart;
1345	0	break;
1346		}
1347	0	state->cp++;
1348		}
1349	0	for (i = 0; i < CLASS_CACHE_SIZE; i++) {
1350	0	if (!state->classCache[i].start) {
1351	0	state->classCache[i].start = termStart;
1352	0	state->classCache[i].length = state->result->u.ucclass.kidlen;
1353	0	state->classCache[i].index = state->classCount;
1354	0	break;
1355		}
1356	0	if (state->classCache[i].length ==
1357		state->result->u.ucclass.kidlen) {
1358	0	for (n = 0; ; n++) {
1359	0	if (n == state->classCache[i].length) {
1360	0	state->result->u.ucclass.index
1361		= state->classCache[i].index;
1362	0	goto claim;
1363		}
1364	0	if (state->classCache[i].start[n] != termStart[n])
1365	0	break;
1366		}
1367		}
1368		}
1369	0	state->result->u.ucclass.index = state->classCount++;
1370
1371		claim:
1372		/*
1373		* Call CalculateBitmapSize now as we want any errors it finds
1374		* to be reported during the parse phase, not at execution.
1375		*/
1376	0	if (!CalculateBitmapSize(state, state->result, termStart, state->cp++))
1377	0	return JS_FALSE;
1378		/*
1379		* Update classBitmapsMem with number of bytes to hold bmsize bits,
1380		* which is (bitsCount + 7) / 8 or (highest_bit + 1 + 7) / 8
1381		* or highest_bit / 8 + 1 where highest_bit is u.ucclass.bmsize.
1382		*/
1383	0	n = (state->result->u.ucclass.bmsize >> 3) + 1;
1384	0	if (n > CLASS_BITMAPS_MEM_LIMIT - state->classBitmapsMem) {
1385	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
1386		JSREPORT_TS | JSREPORT_ERROR,
1387		JSMSG_REGEXP_TOO_COMPLEX);
1388	0	return JS_FALSE;
1389		}
1390	0	state->classBitmapsMem += n;
1391		/* CLASS, <index> */
1392	0	state->progLength
1393		+= 1 + GetCompactIndexWidth(state->result->u.ucclass.index);
1394	0	break;
1395
1396		case '.':
1397	64	state->result = NewRENode(state, REOP_DOT);
1398	64	goto doSimple;
1399
1400		case '{':
1401		{
1402	0	const jschar *errp = state->cp--;
1403	0	intN err;
1404
1405	0	err = ParseMinMaxQuantifier(state, JS_TRUE);
1406	0	state->cp = errp;
1407
1408	0	if (err < 0)
1409	0	goto asFlat;
1410
1411		/* FALL THROUGH */
1412		}
1413		case '*':
1414		case '+':
1415		case '?':
1416	0	js_ReportCompileErrorNumberUC(state->context, state->tokenStream,
1417		JSREPORT_TS | JSREPORT_ERROR,
1418		JSMSG_BAD_QUANTIFIER, state->cp - 1);
1419	0	return JS_FALSE;
1420		default:
1421		asFlat:
1422	4011682	state->result = NewRENode(state, REOP_FLAT);
1423	4011682	if (!state->result)
1424	0	return JS_FALSE;
1425	4011682	state->result->u.flat.chr = c;
1426	4011682	state->result->u.flat.length = 1;
1427	4011682	state->result->kid = (void *) (state->cp - 1);
1428	4011682	state->progLength += 3;
1429	4012098	break;
1430		}
1431	4012098	return ParseQuantifier(state);
1432		}
1433
1434		static JSBool
1435		ParseQuantifier(CompilerState *state)
1436	4027484	{
1437	4027484	RENode *term;
1438	4027484	term = state->result;
1439	4027484	if (state->cp < state->cpend) {
1440	4027100	switch (*state->cp) {
1441		case '+':
1442	0	state->result = NewRENode(state, REOP_QUANT);
1443	0	if (!state->result)
1444	0	return JS_FALSE;
1445	0	state->result->u.range.min = 1;
1446	0	state->result->u.range.max = (uintN)-1;
1447		/* <PLUS>, <next> ... <ENDCHILD> */
1448	0	state->progLength += 4;
1449	0	goto quantifier;
1450		case '*':
1451	0	state->result = NewRENode(state, REOP_QUANT);
1452	0	if (!state->result)
1453	0	return JS_FALSE;
1454	0	state->result->u.range.min = 0;
1455	0	state->result->u.range.max = (uintN)-1;
1456		/* <STAR>, <next> ... <ENDCHILD> */
1457	0	state->progLength += 4;
1458	0	goto quantifier;
1459		case '?':
1460	0	state->result = NewRENode(state, REOP_QUANT);
1461	0	if (!state->result)
1462	0	return JS_FALSE;
1463	0	state->result->u.range.min = 0;
1464	0	state->result->u.range.max = 1;
1465		/* <OPT>, <next> ... <ENDCHILD> */
1466	0	state->progLength += 4;
1467	0	goto quantifier;
1468		case '{':       /* balance '}' */
1469		{
1470	0	intN err;
1471	0	const jschar *errp = state->cp;
1472
1473	0	err = ParseMinMaxQuantifier(state, JS_FALSE);
1474	0	if (err == 0)
1475	0	goto quantifier;
1476	0	if (err == -1)
1477	0	return JS_TRUE;
1478
1479	0	js_ReportCompileErrorNumberUC(state->context,
1480		state->tokenStream,
1481		JSREPORT_TS | JSREPORT_ERROR,
1482		err, errp);
1483	0	return JS_FALSE;
1484		}
1485		default:;
1486		}
1487		}
1488	4027484	return JS_TRUE;
1489
1490		quantifier:
1491	0	if (state->treeDepth == TREE_DEPTH_MAX) {
1492	0	js_ReportCompileErrorNumber(state->context, state->tokenStream,
1493		JSREPORT_TS | JSREPORT_ERROR,
1494		JSMSG_REGEXP_TOO_COMPLEX);
1495	0	return JS_FALSE;
1496		}
1497
1498	0	++state->treeDepth;
1499	0	++state->cp;
1500	0	state->result->kid = term;
1501	0	if (state->cp < state->cpend && *state->cp == '?') {
1502	0	++state->cp;
1503	0	state->result->u.range.greedy = JS_FALSE;
1504		} else {
1505	0	state->result->u.range.greedy = JS_TRUE;
1506		}
1507	0	return JS_TRUE;
1508		}
1509
1510		static intN
1511		ParseMinMaxQuantifier(CompilerState *state, JSBool ignoreValues)
1512	0	{
1513	0	uintN min, max;
1514	0	jschar c;
1515	0	const jschar *errp = state->cp++;
1516
1517	0	c = *state->cp;
1518	0	if (JS7_ISDEC(c)) {
1519	0	++state->cp;
1520	0	min = GetDecimalValue(c, 0xFFFF, NULL, state);
1521	0	c = *state->cp;
1522
1523	0	if (!ignoreValues && min == OVERFLOW_VALUE)
1524	0	return JSMSG_MIN_TOO_BIG;
1525
1526	0	if (c == ',') {
1527	0	c = *++state->cp;
1528	0	if (JS7_ISDEC(c)) {
1529	0	++state->cp;
1530	0	max = GetDecimalValue(c, 0xFFFF, NULL, state);
1531	0	c = *state->cp;
1532	0	if (!ignoreValues && max == OVERFLOW_VALUE)
1533	0	return JSMSG_MAX_TOO_BIG;
1534	0	if (!ignoreValues && min > max)
1535	0	return JSMSG_OUT_OF_ORDER;
1536		} else {
1537	0	max = (uintN)-1;
1538		}
1539		} else {
1540	0	max = min;
1541		}
1542	0	if (c == '}') {
1543	0	state->result = NewRENode(state, REOP_QUANT);
1544	0	if (!state->result)
1545	0	return JS_FALSE;
1546	0	state->result->u.range.min = min;
1547	0	state->result->u.range.max = max;
1548		/*
1549		* QUANT, <min>, <max>, <next> ... <ENDCHILD>
1550		* where <max> is written as compact(max+1) to make
1551		* (uintN)-1 sentinel to occupy 1 byte, not width_of(max)+1.
1552		*/
1553	0	state->progLength += (1 + GetCompactIndexWidth(min)
1554		+ GetCompactIndexWidth(max + 1)
1555		+3);
1556	0	return 0;
1557		}
1558		}
1559
1560	0	state->cp = errp;
1561	0	return -1;
1562		}
1563
1564		static JSBool
1565		SetForwardJumpOffset(jsbytecode *jump, jsbytecode *target)
1566	1428082	{
1567	1428082	ptrdiff_t offset = target - jump;
1568
1569		/* Check that target really points forward. */
1570	1428082	JS_ASSERT(offset >= 2);
1571	1428082	if ((size_t)offset > OFFSET_MAX)
1572	0	return JS_FALSE;
1573
1574	1428082	jump[0] = JUMP_OFFSET_HI(offset);
1575	1428082	jump[1] = JUMP_OFFSET_LO(offset);
1576	1428082	return JS_TRUE;
1577		}
1578
1579		/*
1580		* Generate bytecode for the tree rooted at t using an explicit stack instead
1581		* of recursion.
1582		*/
1583		static jsbytecode *
1584		EmitREBytecode(CompilerState *state, JSRegExp *re, size_t treeDepth,
1585		jsbytecode *pc, RENode *t)
1586	15754	{
1587	15754	EmitStateStackEntry *emitStateSP, *emitStateStack;
1588	15754	RECharSet *charSet;
1589	15754	REOp op;
1590
1591	15754	if (treeDepth == 0) {
1592	368	emitStateStack = NULL;
1593		} else {
1594	15386	emitStateStack =
1595		(EmitStateStackEntry *)JS_malloc(state->context,
1596		sizeof(EmitStateStackEntry) *
1597		treeDepth);
1598	15386	if (!emitStateStack)
1599	0	return NULL;
1600		}
1601	15754	emitStateSP = emitStateStack;
1602	15754	op = t->op;
1603
1604	4331284	for (;;) {
1605	2903202	*pc++ = op;
1606	2903202	switch (op) {
1607		case REOP_EMPTY:
1608	16	--pc;
1609	16	break;
1610
1611		case REOP_ALTPREREQ2:
1612		case REOP_ALTPREREQ:
1613	15386	JS_ASSERT(emitStateSP);
1614	15386	emitStateSP->altHead = pc - 1;
1615	15386	emitStateSP->endTermFixup = pc;
1616	15386	pc += OFFSET_LEN;
1617	15386	SET_ARG(pc, t->u.altprereq.ch1);
1618	15386	pc += ARG_LEN;
1619	15386	SET_ARG(pc, t->u.altprereq.ch2);
1620	15386	pc += ARG_LEN;
1621
1622	15386	emitStateSP->nextAltFixup = pc;    /* offset to next alternate */
1623	15386	pc += OFFSET_LEN;
1624
1625	15386	emitStateSP->continueNode = t;
1626	15386	emitStateSP->continueOp = REOP_JUMP;
1627	15386	emitStateSP->jumpToJumpFlag = JS_FALSE;
1628	15386	++emitStateSP;
1629	15386	JS_ASSERT((size_t)(emitStateSP - emitStateStack) <= treeDepth);
1630	15386	t = (RENode *) t->kid;
1631	15386	op = t->op;
1632	15386	continue;
1633
1634		case REOP_JUMP:
1635	706348	emitStateSP->nextTermFixup = pc;    /* offset to following term */
1636	706348	pc += OFFSET_LEN;
1637	706348	if (!SetForwardJumpOffset(emitStateSP->nextAltFixup, pc))
1638	0	goto jump_too_big;
1639	706348	emitStateSP->continueOp = REOP_ENDALT;
1640	706348	++emitStateSP;
1641	706348	JS_ASSERT((size_t)(emitStateSP - emitStateStack) <= treeDepth);
1642	706348	t = t->u.kid2;
1643	706348	op = t->op;
1644	706348	continue;
1645
1646		case REOP_ENDALT:
1647		/*
1648		* If we already patched emitStateSP->nextTermFixup to jump to
1649		* a nearer jump, to avoid 16-bit immediate offset overflow, we
1650		* are done here.
1651		*/
1652	706348	if (emitStateSP->jumpToJumpFlag)
1653	0	break;
1654
1655		/*
1656		* Fix up the REOP_JUMP offset to go to the op after REOP_ENDALT.
1657		* REOP_ENDALT is executed only on successful match of the last
1658		* alternate in a group.
1659		*/
1660	706348	if (!SetForwardJumpOffset(emitStateSP->nextTermFixup, pc))
1661	0	goto jump_too_big;
1662	706348	if (t->op != REOP_ALT) {
1663	15386	if (!SetForwardJumpOffset(emitStateSP->endTermFixup, pc))
1664	0	goto jump_too_big;
1665		}
1666
1667		/*
1668		* If the program is bigger than the REOP_JUMP offset range, then
1669		* we must check for alternates before this one that are part of
1670		* the same group, and fix up their jump offsets to target jumps
1671		* close enough to fit in a 16-bit unsigned offset immediate.
1672		*/
1673	706348	if ((size_t)(pc - re->program) > OFFSET_MAX &&
1674		emitStateSP > emitStateStack) {
1675	0	EmitStateStackEntry *esp, *esp2;
1676	0	jsbytecode *alt, *jump;
1677	0	ptrdiff_t span, header;
1678
1679	0	esp2 = emitStateSP;
1680	0	alt = esp2->altHead;
1681	0	for (esp = esp2 - 1; esp >= emitStateStack; --esp) {
1682	0	if (esp->continueOp == REOP_ENDALT &&
1683		!esp->jumpToJumpFlag &&
1684		esp->nextTermFixup + OFFSET_LEN == alt &&
1685		(size_t)(pc - ((esp->continueNode->op != REOP_ALT)
1686		? esp->endTermFixup
1687		: esp->nextTermFixup)) > OFFSET_MAX) {
1688	0	alt = esp->altHead;
1689	0	jump = esp->nextTermFixup;
1690
1691		/*
1692		* The span must be 1 less than the distance from
1693		* jump offset to jump offset, so we actually jump
1694		* to a REOP_JUMP bytecode, not to its offset!
1695		*/
1696	0	for (;;) {
1697	0	JS_ASSERT(jump < esp2->nextTermFixup);
1698	0	span = esp2->nextTermFixup - jump - 1;
1699	0	if ((size_t)span <= OFFSET_MAX)
1700	0	break;
1701	0	do {
1702	0	if (--esp2 == esp)
1703	0	goto jump_too_big;
1704	0	} while (esp2->continueOp != REOP_ENDALT);
1705		}
1706
1707	0	jump[0] = JUMP_OFFSET_HI(span);
1708	0	jump[1] = JUMP_OFFSET_LO(span);
1709
1710	0	if (esp->continueNode->op != REOP_ALT) {
1711		/*
1712		* We must patch the offset at esp->endTermFixup
1713		* as well, for the REOP_ALTPREREQ{,2} opcodes.
1714		* If we're unlucky and endTermFixup is more than
1715		* OFFSET_MAX bytes from its target, we cheat by
1716		* jumping 6 bytes to the jump whose offset is at
1717		* esp->nextTermFixup, which has the same target.
1718		*/
1719	0	jump = esp->endTermFixup;
1720	0	header = esp->nextTermFixup - jump;
1721	0	span += header;
1722	0	if ((size_t)span > OFFSET_MAX)
1723	0	span = header;
1724
1725	0	jump[0] = JUMP_OFFSET_HI(span);
1726	0	jump[1] = JUMP_OFFSET_LO(span);
1727		}
1728
1729	0	esp->jumpToJumpFlag = JS_TRUE;
1730		}
1731		}
1732		}
1733	690962	break;
1734
1735		case REOP_ALT:
1736	690962	JS_ASSERT(emitStateSP);
1737	690962	emitStateSP->altHead = pc - 1;
1738	690962	emitStateSP->nextAltFixup = pc;     /* offset to next alternate */
1739	690962	pc += OFFSET_LEN;
1740	690962	emitStateSP->continueNode = t;
1741	690962	emitStateSP->continueOp = REOP_JUMP;
1742	690962	emitStateSP->jumpToJumpFlag = JS_FALSE;
1743	690962	++emitStateSP;
1744	690962	JS_ASSERT((size_t)(emitStateSP - emitStateStack) <= treeDepth);
1745	690962	t = t->kid;
1746	690962	op = t->op;
1747	690962	continue;
1748
1749		case REOP_FLAT:
1750		/*
1751		* Coalesce FLATs if possible and if it would not increase bytecode
1752		* beyond preallocated limit. The latter happens only when bytecode
1753		* size for coalesced string with offset p and length 2 exceeds 6
1754		* bytes preallocated for 2 single char nodes, i.e. when
1755		* 1 + GetCompactIndexWidth(p) + GetCompactIndexWidth(2) > 6 or
1756		* GetCompactIndexWidth(p) > 4.
1757		* Since when GetCompactIndexWidth(p) <= 4 coalescing of 3 or more
1758		* nodes strictly decreases bytecode size, the check has to be
1759		* done only for the first coalescing.
1760		*/
1761	722534	if (t->kid &&
1762		&nb