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