git.oblomov.eu Git - wine/blob - dlls/jscript/regexp.c

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