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