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