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