home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / js / src / jsregexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  85.7 KB  |  3,220 lines
  1. /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  2.  *
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  *
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  *
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. /*
  20.  * JS regular expressions, after Perl.
  21.  */
  22. #include <stdlib.h>
  23. #include <string.h>
  24. #include "prtypes.h"
  25. #ifndef NSPR20
  26. #include "prarena.h"
  27. #else
  28. #include "plarena.h"
  29. #endif
  30. #include "prlog.h"
  31. #include "jsapi.h"
  32. #include "jsarray.h"
  33. #include "jsatom.h"
  34. #include "jscntxt.h"
  35. #include "jsconfig.h"
  36. #include "jsfun.h"
  37. #include "jsgc.h"
  38. #include "jslock.h"
  39. #include "jsnum.h"
  40. #include "jsobj.h"
  41. #include "jsopcode.h"
  42. #include "jsregexp.h"
  43. #include "jsstr.h"
  44.  
  45. #if JS_HAS_REGEXPS
  46.  
  47. typedef struct RENode RENode;
  48.  
  49. typedef enum REOp {
  50.     REOP_EMPTY    = 0,  /* match rest of input against rest of r.e. */
  51.     REOP_ALT      = 1,  /* alternative subexpressions in kid and next */
  52.     REOP_BOL      = 2,  /* beginning of input (or line if multiline) */
  53.     REOP_EOL      = 3,  /* end of input (or line if multiline) */
  54.     REOP_WBDRY    = 4,  /* match "" at word boundary */
  55.     REOP_WNONBDRY = 5,  /* match "" at word non-boundary */
  56.     REOP_QUANT    = 6,  /* quantified atom: atom{1,2} */
  57.     REOP_STAR     = 7,  /* zero or more occurrences of kid */
  58.     REOP_PLUS     = 8,  /* one or more occurrences of kid */
  59.     REOP_OPT      = 9,  /* optional subexpression in kid */
  60.     REOP_LPAREN   = 10, /* left paren bytecode: kid is u.num'th sub-regexp */
  61.     REOP_RPAREN   = 11, /* right paren bytecode */
  62.     REOP_DOT      = 12, /* stands for any character */
  63.     REOP_CCLASS   = 13, /* character class: [a-f] */
  64.     REOP_DIGIT    = 14, /* match a digit char: [0-9] */
  65.     REOP_NONDIGIT = 15, /* match a non-digit char: [^0-9] */
  66.     REOP_ALNUM    = 16, /* match an alphanumeric char: [0-9a-z_A-Z] */
  67.     REOP_NONALNUM = 17, /* match a non-alphanumeric char: [^0-9a-z_A-Z] */
  68.     REOP_SPACE    = 18, /* match a whitespace char */
  69.     REOP_NONSPACE = 19, /* match a non-whitespace char */
  70.     REOP_BACKREF  = 20, /* back-reference (e.g., \1) to a parenthetical */
  71.     REOP_FLAT     = 21, /* match a flat string */
  72.     REOP_FLAT1    = 22, /* match a single char */
  73.     REOP_JUMP     = 23, /* for deoptimized closure loops */
  74.     REOP_DOTSTAR  = 24, /* optimize .* to use a single opcode */
  75.     REOP_ANCHOR   = 25, /* like .* but skips left context to unanchored r.e. */
  76.     REOP_EOLONLY  = 26, /* $ not preceded by any pattern */
  77.     REOP_UCFLAT   = 27, /* flat Unicode string; len immediate counts chars */
  78.     REOP_UCFLAT1  = 28, /* single Unicode char */
  79.     REOP_UCCLASS  = 29, /* Unicode character class, vector of chars to match */
  80.     REOP_NUCCLASS = 30, /* negated Unicode character class */
  81.     REOP_BACKREFi = 31, /* case-independent REOP_BACKREF */
  82.     REOP_FLATi    = 32, /* case-independent REOP_FLAT */
  83.     REOP_FLAT1i   = 33, /* case-independent REOP_FLAT1 */
  84.     REOP_UCFLATi  = 34, /* case-independent REOP_UCFLAT */
  85.     REOP_UCFLAT1i = 35, /* case-independent REOP_UCFLAT1 */
  86.     REOP_ANCHOR1  = 36, /* first-char discriminating REOP_ANCHOR */
  87.     REOP_END
  88. } REOp;
  89.  
  90. #define CCLASS_CHARSET_SIZE 256 /* ISO-Latin-1 */
  91.  
  92. uint8 reopsize[] = {
  93.     /* EMPTY */         1,
  94.     /* ALT */           3,
  95.     /* BOL */           1,
  96.     /* EOL */           1,
  97.     /* WBDRY */         1,
  98.     /* WNONBDRY */      1,
  99.     /* QUANT */         7,
  100.     /* STAR */          1,
  101.     /* PLUS */          1,
  102.     /* OPT */           1,
  103.     /* LPAREN */        3,
  104.     /* RPAREN */        3,
  105.     /* DOT */           1,
  106.     /* CCLASS */        1 + (CCLASS_CHARSET_SIZE / PR_BITS_PER_BYTE),
  107.     /* DIGIT */         1,
  108.     /* NONDIGIT */      1,
  109.     /* ALNUM */         1,
  110.     /* NONALNUM */      1,
  111.     /* SPACE */         1,
  112.     /* NONSPACE */      1,
  113.     /* BACKREF */       2,
  114.     /* FLAT */          2,    /* (2 = op + len) + [len bytes] */
  115.     /* FLAT1 */         2,
  116.     /* JUMP */          3,
  117.     /* DOTSTAR */       1,
  118.     /* ANCHOR */        1,
  119.     /* EOLONLY */       1,
  120.     /* UCFLAT */        2,    /* (2 = op + len) + [len 2-byte chars] */
  121.     /* UCFLAT1 */       3,      /* op + hibyte + lobyte */
  122.     /* UCCLASS */       3,      /* (3 = op + 2-byte len) + [len bytes] */
  123.     /* NUCCLASS */      3,      /* (3 = op + 2-byte len) + [len bytes] */
  124.     /* BACKREFi */      2,
  125.     /* FLATi */         2,    /* (2 = op + len) + [len bytes] */
  126.     /* FLAT1i */        2,
  127.     /* UCFLATi */       2,    /* (2 = op + len) + [len 2-byte chars] */
  128.     /* UCFLAT1i */      3,      /* op + hibyte + lobyte */
  129.     /* ANCHOR1 */       1,
  130.     /* END */           0,
  131. };
  132.  
  133. #define REOP_FLATLEN_MAX 255    /* maximum length of FLAT string */
  134.  
  135. struct RENode {
  136.     uint8           op;         /* packed r.e. op bytecode */
  137.     uint8           flags;      /* flags, see below */
  138.     uint16          offset;     /* bytecode offset */
  139.     RENode          *next;      /* next in concatenation order */
  140.     void            *kid;       /* first operand */
  141.     union {
  142.         void        *kid2;      /* second operand */
  143.         jsint       num;        /* could be a number */
  144.         jschar      chr;        /* or a character */
  145.         struct {                /* or a quantifier range */
  146.             uint16  min;
  147.             uint16  max;
  148.         } range;
  149.         struct {                /* or a Unicode character class */
  150.             uint16  kidlen;     /* length of string at kid, in jschars */
  151.             uint16  bmsize;     /* bitmap size, based on max char code */
  152.         } ucclass;
  153.     } u;
  154. };
  155.  
  156. #define REOP(ren)   ((REOp)(ren)->op)
  157.  
  158. #define RENODE_ANCHORED 0x01    /* anchored at the front */
  159. #define RENODE_SINGLE   0x02    /* matches a single char */
  160. #define RENODE_NONEMPTY 0x04    /* does not match empty string */
  161. #define RENODE_ISNEXT   0x08    /* ren is next after at least one node */
  162. #define RENODE_GOODNEXT 0x10    /* ren->next is a tree-like edge in the graph */
  163. #define RENODE_ISJOIN   0x20    /* ren is a join point in the graph */
  164. #define RENODE_REALLOK  0x40    /* REOP_FLAT owns tempPool space to realloc */
  165.  
  166. typedef struct CompilerState {
  167.     JSContext       *context;
  168.     const jschar    *cpbegin;
  169.     const jschar    *cp;
  170.     uintN           flags;
  171.     uintN           parenCount;
  172.     size_t          progLength;
  173. } CompilerState;
  174.  
  175. static RENode *
  176. NewRENode(CompilerState *state, REOp op, void *kid)
  177. {
  178.     JSContext *cx;
  179.     RENode *ren;
  180.  
  181.     cx = state->context;
  182.     PR_ARENA_ALLOCATE(ren, &cx->tempPool, sizeof *ren);
  183.     if (!ren) {
  184.     JS_ReportOutOfMemory(cx);
  185.     return NULL;
  186.     }
  187.     ren->op = (uint8)op;
  188.     ren->flags = 0;
  189.     ren->offset = 0;
  190.     ren->next = NULL;
  191.     ren->kid = kid;
  192.     return ren;
  193. }
  194.  
  195. #ifdef DEBUG
  196.  
  197. #include <stdio.h>
  198.  
  199. static char *reopname[] = {
  200.     "empty",
  201.     "alt",
  202.     "bol",
  203.     "eol",
  204.     "wbdry",
  205.     "wnonbdry",
  206.     "quant",
  207.     "star",
  208.     "plus",
  209.     "opt",
  210.     "lparen",
  211.     "rparen",
  212.     "dot",
  213.     "cclass",
  214.     "digit",
  215.     "nondigit",
  216.     "alnum",
  217.     "nonalnum",
  218.     "space",
  219.     "nonspace",
  220.     "backref",
  221.     "flat",
  222.     "flat1",
  223.     "jump",
  224.     "dotstar",
  225.     "anchor",
  226.     "eolonly",
  227.     "ucflat",
  228.     "ucflat1",
  229.     "ucclass",
  230.     "nucclass",
  231.     "backrefi",
  232.     "flati",
  233.     "flat1i",
  234.     "ucflati",
  235.     "ucflat1i",
  236.     "anchor1",
  237.     "end"
  238. };
  239.  
  240. static void
  241. PrintChar(jschar c)
  242. {
  243.     if (c >> 8)
  244.     printf("\\u%04X", c);
  245.     else
  246. #if !defined XP_PC || !defined _MSC_VER || _MSC_VER > 800
  247.     putchar((char)c);
  248. #else
  249.     /* XXX is there a better way with MSVC1.52? */
  250.     printf("%c", c);
  251. #endif
  252. }
  253.  
  254. static JSBool
  255. DumpRegExp(JSContext *cx, RENode *ren)
  256. {
  257.     static int level;
  258.     JSBool ok;
  259.     int i, len;
  260.     jschar *cp;
  261.     char *cstr;
  262.  
  263.     if (level == 0)
  264.     printf("level offset  flags  description\n");
  265.     level++;
  266.     ok = JS_TRUE;
  267.     do {
  268.     printf("%5d %6d %c%c%c%c%c%c  %s",
  269.            level,
  270.            (int)ren->offset,
  271.            (ren->flags & RENODE_ANCHORED) ? 'A' : '-',
  272.            (ren->flags & RENODE_SINGLE)   ? 'S' : '-',
  273.            (ren->flags & RENODE_NONEMPTY) ? 'F' : '-',    /* F for full */
  274.            (ren->flags & RENODE_ISNEXT)   ? 'N' : '-',    /* N for next */
  275.            (ren->flags & RENODE_GOODNEXT) ? 'G' : '-',
  276.            (ren->flags & RENODE_ISJOIN)   ? 'J' : '-',
  277.            reopname[ren->op]);
  278.  
  279.     switch (REOP(ren)) {
  280.       case REOP_ALT:
  281.         printf(" %d\n", ren->next->offset);
  282.         ok = DumpRegExp(cx, ren->kid);
  283.         if (!ok)
  284.         goto out;
  285.         break;
  286.  
  287.       case REOP_STAR:
  288.       case REOP_PLUS:
  289.       case REOP_OPT:
  290.       case REOP_ANCHOR1:
  291.         printf("\n");
  292.         ok = DumpRegExp(cx, ren->kid);
  293.         if (!ok)
  294.         goto out;
  295.         break;
  296.  
  297.       case REOP_QUANT:
  298.         printf(" next %d min %d max %d\n",
  299.            ren->next->offset, ren->u.range.min, ren->u.range.max);
  300.         ok = DumpRegExp(cx, ren->kid);
  301.         if (!ok)
  302.         goto out;
  303.         break;
  304.  
  305.       case REOP_LPAREN:
  306.         printf(" num %d\n", (int)ren->u.num);
  307.         ok = DumpRegExp(cx, ren->kid);
  308.         if (!ok)
  309.         goto out;
  310.         break;
  311.  
  312.       case REOP_RPAREN:
  313.         printf(" num %d\n", (int)ren->u.num);
  314.         break;
  315.  
  316.       case REOP_CCLASS:
  317.         len = (jschar *)ren->u.kid2 - (jschar *)ren->kid;
  318.         cstr = js_DeflateString(cx, (jschar *)ren->kid, len);
  319.         if (!cstr) {
  320.         ok = JS_FALSE;
  321.         goto out;
  322.         }
  323.         printf(" [%s]\n", cstr);
  324.         JS_free(cx, cstr);
  325.         break;
  326.  
  327.       case REOP_BACKREF:
  328.         printf(" num %d\n", (int)ren->u.num);
  329.         break;
  330.  
  331.       case REOP_FLAT:
  332.         len = (jschar *)ren->u.kid2 - (jschar *)ren->kid;
  333.         cstr = js_DeflateString(cx, (jschar *)ren->kid, len);
  334.         if (!cstr) {
  335.         ok = JS_FALSE;
  336.         goto out;
  337.         }
  338.         printf(" %s (%d)\n", cstr, len);
  339.         JS_free(cx, cstr);
  340.         break;
  341.  
  342.       case REOP_FLAT1:
  343.         printf(" %c ('\\%o')\n", (char)ren->u.chr, ren->u.chr);
  344.         break;
  345.  
  346.       case REOP_JUMP:
  347.         printf(" %d\n", ren->next->offset);
  348.         break;
  349.  
  350.       case REOP_UCFLAT:
  351.         cp = ren->kid;
  352.         len = (jschar *)ren->u.kid2 - cp;
  353.         for (i = 0; i < len; i++)
  354.         PrintChar(cp[i]);
  355.         break;
  356.  
  357.       case REOP_UCFLAT1:
  358.         PrintChar(ren->u.chr);
  359.         break;
  360.  
  361.       case REOP_UCCLASS:
  362.         cp = ren->kid;
  363.         len = (jschar *)ren->u.kid2 - cp;
  364.         printf(" [");
  365.         for (i = 0; i < len; i++)
  366.         PrintChar(cp[i]);
  367.         printf("]\n");
  368.         break;
  369.  
  370.       default:
  371.         printf("\n");
  372.         break;
  373.     }
  374.  
  375.     if (!(ren->flags & RENODE_GOODNEXT))
  376.         break;
  377.     } while ((ren = ren->next) != NULL);
  378. out:
  379.     level--;
  380.     return ok;
  381. }
  382.  
  383. #endif /* DEBUG */
  384.  
  385. static JSBool
  386. FixNext(CompilerState *state, RENode *ren1, RENode *ren2, RENode *oldnext)
  387. {
  388.     JSBool goodnext;
  389.     RENode *next, *kid, *ren;
  390.  
  391.     goodnext = ren2 && !(ren2->flags & RENODE_ISNEXT);
  392.  
  393.     /*
  394.      * Find the final node in a list of alternatives, or concatenations, or
  395.      * even a concatenation of alternatives followed by non-alternatives (e.g.
  396.      * ((x|y)z)w where ((x|y)z) is ren1 and w is ren2).
  397.      */
  398.     for (; (next = ren1->next) != NULL && next != oldnext; ren1 = next) {
  399.     if (REOP(ren1) == REOP_ALT) {
  400.         /* Find the end of this alternative's operand list. */
  401.         kid = ren1->kid;
  402.         if (REOP(kid) == REOP_JUMP)
  403.         continue;
  404.         for (ren = kid; ren->next; ren = ren->next)
  405.         PR_ASSERT(REOP(ren) != REOP_ALT);
  406.  
  407.         /* Append a jump node to all but the last alternative. */
  408.         ren->next = NewRENode(state, REOP_JUMP, NULL);
  409.         if (!ren->next)
  410.         return JS_FALSE;
  411.         ren->next->flags |= RENODE_ISNEXT;
  412.         ren->flags |= RENODE_GOODNEXT;
  413.  
  414.         /* Recur to fix all descendent nested alternatives. */
  415.         if (!FixNext(state, kid, ren2, oldnext))
  416.         return JS_FALSE;
  417.     }
  418.     }
  419.  
  420.     /*
  421.      * Now ren1 points to the last alternative, or to the final node on a
  422.      * concatenation list.  Set its next link to ren2, flagging a join point
  423.      * if appropriate.
  424.      */
  425.     if (ren2) {
  426.     if (!(ren2->flags & RENODE_ISNEXT))
  427.         ren2->flags |= RENODE_ISNEXT;
  428.     else
  429.         ren2->flags |= RENODE_ISJOIN;
  430.     }
  431.     ren1->next = ren2;
  432.     if (goodnext)
  433.     ren1->flags |= RENODE_GOODNEXT;
  434.  
  435.     /*
  436.      * The following ops have a kid subtree through which to recur.  Here is
  437.      * where we fix the next links under the final ALT node's kid.
  438.      */
  439.     switch (REOP(ren1)) {
  440.       case REOP_ALT:
  441.       case REOP_QUANT:
  442.       case REOP_STAR:
  443.       case REOP_PLUS:
  444.       case REOP_OPT:
  445.       case REOP_LPAREN:
  446.     if (!FixNext(state, ren1->kid, ren2, oldnext))
  447.         return JS_FALSE;
  448.     break;
  449.       default:;
  450.     }
  451.     return JS_TRUE;
  452. }
  453.  
  454. static JSBool
  455. SetNext(CompilerState *state, RENode *ren1, RENode *ren2)
  456. {
  457.     return FixNext(state, ren1, ren2, NULL);
  458. }
  459.  
  460. /*
  461.  * Parser forward declarations.
  462.  */
  463. typedef RENode *REParser(CompilerState *state);
  464.  
  465. static REParser ParseRegExp;
  466. static REParser ParseAltern;
  467. static REParser ParseItem;
  468. static REParser ParseQuantAtom;
  469. static REParser ParseAtom;
  470.  
  471. /*
  472.  * Top-down regular expression grammar, based closely on Perl4.
  473.  *
  474.  *  regexp:     altern                  A regular expression is one or more
  475.  *              altern '|' regexp       alternatives separated by vertical bar.
  476.  */
  477. static RENode *
  478. ParseRegExp(CompilerState *state)
  479. {
  480.     RENode *ren, *kid, *ren1, *ren2;
  481.     const jschar *cp;
  482.  
  483.     ren = ParseAltern(state);
  484.     if (!ren)
  485.     return NULL;
  486.     cp = state->cp;
  487.     if (*cp == '|') {
  488.     kid = ren;
  489.     ren = NewRENode(state, REOP_ALT, kid);
  490.     if (!ren)
  491.         return NULL;
  492.     ren->flags = kid->flags & (RENODE_ANCHORED | RENODE_NONEMPTY);
  493.     ren1 = ren;
  494.     do {
  495.         /* (balance: */
  496.         state->cp = ++cp;
  497.         if (*cp == '|' || *cp == ')') {
  498.         kid = NewRENode(state, REOP_EMPTY, NULL);
  499.         } else {
  500.         kid = ParseAltern(state);
  501.         cp = state->cp;
  502.         }
  503.         if (!kid)
  504.         return NULL;
  505.         ren2 = NewRENode(state, REOP_ALT, kid);
  506.         if (!ren2)
  507.         return NULL;
  508.         ren1->next = ren2;
  509.         ren1->flags |= RENODE_GOODNEXT;
  510.         ren2->flags = (kid->flags & (RENODE_ANCHORED | RENODE_NONEMPTY))
  511.               | RENODE_ISNEXT;
  512.         ren1 = ren2;
  513.     } while (*cp == '|');
  514.     }
  515.     return ren;
  516. }
  517.  
  518. /*
  519.  *  altern:     item                    An alternative is one or more items,
  520.  *              item altern             concatenated together.
  521.  */
  522. static RENode *
  523. ParseAltern(CompilerState *state)
  524. {
  525.     RENode *ren, *ren1, *ren2;
  526.     uintN flags;
  527.     const jschar *cp;
  528.     jschar c;
  529.  
  530.     ren = ren1 = ParseItem(state);
  531.     if (!ren)
  532.     return NULL;
  533.     flags = 0;
  534.     cp = state->cp;
  535.     /* (balance: */
  536.     while ((c = *cp) != 0 && c != '|' && c != ')') {
  537.     ren2 = ParseItem(state);
  538.     if (!ren2)
  539.         return NULL;
  540.     if (!SetNext(state, ren1, ren2))
  541.         return NULL;
  542.     flags |= ren2->flags;
  543.     ren1 = ren2;
  544.     cp = state->cp;
  545.     }
  546.  
  547.     /*
  548.      * Propagate NONEMPTY to the front of a concatenation list, so that the
  549.      * first alternative in (^a|b) is considered non-empty.  The first node
  550.      * in a list may match the empty string (as ^ does), but if the list is
  551.      * non-empty, then the first node's NONEMPTY flag must be set.
  552.      */
  553.     ren->flags |= flags & RENODE_NONEMPTY;
  554.     return ren;
  555. }
  556.  
  557. /*
  558.  *  item:       assertion               An item is either an assertion or
  559.  *              quantatom               a quantified atom.
  560.  *
  561.  *  assertion:  '^'                     Assertions match beginning of string
  562.  *                                      (or line if the class static property
  563.  *                                      RegExp.multiline is true).
  564.  *              '$'                     End of string (or line if the class
  565.  *                                      static property RegExp.multiline is
  566.  *                                      true).
  567.  *              '\b'                    Word boundary (between \w and \W).
  568.  *              '\B'                    Word non-boundary.
  569.  */
  570. static RENode *
  571. ParseItem(CompilerState *state)
  572. {
  573.     const jschar *cp;
  574.     RENode *ren;
  575.  
  576.     cp = state->cp;
  577.     switch (*cp) {
  578.       case '^':
  579.     state->cp = cp + 1;
  580.     ren = NewRENode(state, REOP_BOL, NULL);
  581.     if (ren)
  582.         ren->flags |= RENODE_ANCHORED;
  583.     return ren;
  584.  
  585.       case '$':
  586.     state->cp = cp + 1;
  587.     return NewRENode(state,
  588.              (cp == state->cpbegin ||
  589.               ((cp[-1] == '(' || cp[-1] == '|') && /*balance)*/
  590.                (cp - 1 == state->cpbegin || cp[-2] != '\\')))
  591.              ? REOP_EOLONLY
  592.              : REOP_EOL,
  593.              NULL);
  594.  
  595.       case '\\':
  596.     switch (*++cp) {
  597.       case 'b':
  598.         state->cp = cp + 1;
  599.         return NewRENode(state, REOP_WBDRY, NULL);
  600.  
  601.       case 'B':
  602.         state->cp = cp + 1;
  603.         return NewRENode(state, REOP_WNONBDRY, NULL);
  604.     }
  605.     /* FALL THROUGH */
  606.  
  607.       default:;
  608.     }
  609.     return ParseQuantAtom(state);
  610. }
  611.  
  612. /*
  613.  *  quantatom:  atom                    An unquantified atom.
  614.  *              quantatom '{' n ',' m '}'
  615.  *                                      Atom must occur between n and m times.
  616.  *              quantatom '{' n ',' '}' Atom must occur at least n times.
  617.  *              quantatom '{' n '}'     Atom must occur exactly n times.
  618.  *              quantatom '*'           Zero or more times (same as {0,}).
  619.  *              quantatom '+'           One or more times (same as {1,}).
  620.  *              quantatom '?'           Zero or one time (same as {0,1}).
  621.  */
  622. static RENode *
  623. ParseQuantAtom(CompilerState *state)
  624. {
  625.     RENode *ren, *ren2;
  626.     const jschar *cp, *up;
  627.     jschar c;
  628.     uint32 min, max;
  629.  
  630.     ren = ParseAtom(state);
  631.     if (!ren)
  632.     return NULL;
  633.  
  634.     cp = state->cp;
  635. loop:
  636.     switch (*cp) {
  637.       case '{':
  638.     c = *++cp;
  639.     if (!JS7_ISDEC(c)) {
  640.         JS_ReportError(state->context, "invalid quantifier %s", state->cp);
  641.         return NULL;
  642.     }
  643.     min = (uint32)JS7_UNDEC(c);
  644.     for (c = *++cp; JS7_ISDEC(c); c = *++cp) {
  645.         min = 10 * min + (uint32)JS7_UNDEC(c);
  646.         if (min >> 16) {
  647.         JS_ReportError(state->context, "overlarge minimum %s",
  648.                    state->cp);
  649.         return NULL;
  650.         }
  651.     }
  652.     if (*cp == ',') {
  653.         up = ++cp;
  654.         if (JS7_ISDEC(*cp)) {
  655.         max = (uint32)JS7_UNDEC(*cp);
  656.         for (c = *++cp; JS7_ISDEC(c); c = *++cp) {
  657.             max = 10 * max + (uint32)JS7_UNDEC(c);
  658.             if (max >> 16) {
  659.             JS_ReportError(state->context, "overlarge maximum %s",
  660.                        up);
  661.             return NULL;
  662.             }
  663.         }
  664.         if (max == 0)
  665.             goto zero_quant;
  666.         if (min > max) {
  667.             JS_ReportError(state->context,
  668.                    "maximum %s less than minimum", up);
  669.             return NULL;
  670.         }
  671.         } else {
  672.         /* 0 means no upper bound. */
  673.         max = 0;
  674.         }
  675.     } else {
  676.         /* Exactly n times. */
  677.         if (min == 0) {
  678.       zero_quant:
  679.         JS_ReportError(state->context, "zero quantifier %s", state->cp);
  680.         return NULL;
  681.         }
  682.         max = min;
  683.     }
  684.     if (*cp != '}') {
  685.         JS_ReportError(state->context, "unterminated quantifier %s",
  686.                state->cp);
  687.         return NULL;
  688.     }
  689.     cp++;
  690.  
  691.     ren2 = NewRENode(state, REOP_QUANT, ren);
  692.     if (!ren2)
  693.         return NULL;
  694.     if (min > 0 && (ren->flags & RENODE_NONEMPTY))
  695.         ren2->flags |= RENODE_NONEMPTY;
  696.     ren2->u.range.min = (uint16)min;
  697.     ren2->u.range.max = (uint16)max;
  698.     ren = ren2;
  699.     goto loop;
  700.  
  701.       case '*':
  702.     if (!(ren->flags & RENODE_NONEMPTY)) {
  703.         JS_ReportError(state->context,
  704.                "regular expression before * could be empty");
  705.         return NULL;
  706.     }
  707.     cp++;
  708.     ren = NewRENode(state, REOP_STAR, ren);
  709.     goto loop;
  710.  
  711.       case '+':
  712.     if (!(ren->flags & RENODE_NONEMPTY)) {
  713.         JS_ReportError(state->context,
  714.                "regular expression before + could be empty");
  715.         return NULL;
  716.     }
  717.     cp++;
  718.     ren2 = NewRENode(state, REOP_PLUS, ren);
  719.     if (!ren2)
  720.         return NULL;
  721.     if (ren->flags & RENODE_NONEMPTY)
  722.         ren2->flags |= RENODE_NONEMPTY;
  723.     ren = ren2;
  724.     goto loop;
  725.  
  726.       case '?':
  727.     cp++;
  728.     ren = NewRENode(state, REOP_OPT, ren);
  729.     goto loop;
  730.     }
  731.  
  732.     state->cp = cp;
  733.     return ren;
  734. }
  735.  
  736. /*
  737.  *  atom:       '(' regexp ')'          A parenthesized regexp (what matched
  738.  *                                      can be addressed using a backreference,
  739.  *                                      see '\' n below).
  740.  *              '.'                     Matches any char except '\n'.
  741.  *              '[' classlist ']'       A character class.
  742.  *              '[' '^' classlist ']'   A negated character class.
  743.  *              '\f'                    Form Feed.
  744.  *              '\n'                    Newline (Line Feed).
  745.  *              '\r'                    Carriage Return.
  746.  *              '\t'                    Horizontal Tab.
  747.  *              '\v'                    Vertical Tab.
  748.  *              '\d'                    A digit (same as [0-9]).
  749.  *              '\D'                    A non-digit.
  750.  *              '\w'                    A word character, [0-9a-z_A-Z].
  751.  *              '\W'                    A non-word character.
  752.  *              '\s'                    A whitespace character, [ \b\f\n\r\t\v].
  753.  *              '\S'                    A non-whitespace character.
  754.  *              '\' n                   A backreference to the nth (n decimal
  755.  *                                      and positive) parenthesized expression.
  756.  *              '\' octal               An octal escape sequence (octal must be
  757.  *                                      two or three digits long, unless it is
  758.  *                                      0 for the null character).
  759.  *              '\x' hex                A hex escape (hex must be two digits).
  760.  *              '\c' ctrl               A control character, ctrl is a letter.
  761.  *              '\' literalatomchar     Any character except one of the above
  762.  *                                      that follow '\' in an atom.
  763.  *              otheratomchar           Any character not first among the other
  764.  *                                      atom right-hand sides.
  765.  */
  766. static jschar metachars[] = {
  767.     '|', '^', '$', '{', '*', '+', '?', '(', ')', '.', '[', '\\', '}', 0
  768. };
  769.  
  770. static jschar closurechars[] = {
  771.     '{', '*', '+', '?', 0    /* balance} */
  772. };
  773.  
  774. static RENode *
  775. ParseAtom(CompilerState *state)
  776. {
  777.     const jschar *cp, *ocp;
  778.     uintN num, tmp, len;
  779.     RENode *ren, *ren2;
  780.     jschar c;
  781.  
  782.     cp = ocp = state->cp;
  783.     switch (*cp) {
  784.       case 0:
  785.     ren = NewRENode(state, REOP_EMPTY, NULL);
  786.     break;
  787.  
  788.       case '(':
  789.     num = state->parenCount++;    /* \1 is numbered 0, etc. */
  790.     state->cp = cp + 1;
  791.     ren2 = ParseRegExp(state);
  792.     if (!ren2)
  793.         return NULL;
  794.     cp = state->cp;
  795.     if (*cp != ')') {
  796.         JS_ReportError(state->context, "unterminated parenthetical %s",
  797.                ocp);
  798.         return NULL;
  799.     }
  800.     cp++;
  801.     ren = NewRENode(state, REOP_LPAREN, ren2);
  802.     if (!ren)
  803.         return NULL;
  804.     ren->flags = ren2->flags & (RENODE_ANCHORED | RENODE_NONEMPTY);
  805.     ren->u.num = num;
  806.     ren2 = NewRENode(state, REOP_RPAREN, NULL);
  807.     if (!ren2 || !SetNext(state, ren, ren2))
  808.         return NULL;
  809.     ren2->u.num = num;
  810.     break;
  811.  
  812.       case '.':
  813.     cp++;
  814.     if ((c = *cp) == '*')
  815.         cp++;
  816.     ren = NewRENode(state, (c == '*') ? REOP_DOTSTAR : REOP_DOT, NULL);
  817.     if (ren && REOP(ren) == REOP_DOT)
  818.         ren->flags = RENODE_SINGLE | RENODE_NONEMPTY;
  819.     break;
  820.  
  821.       case '[':
  822.     /* A char class must have at least one char in it. */
  823.     if ((c = *++cp) == 0)
  824.         goto bad_cclass;
  825.  
  826.     ren = NewRENode(state, REOP_CCLASS, (void *)cp);
  827.     if (!ren)
  828.         return NULL;
  829.  
  830.     /* A negated class must have at least one char in it after the ^. */
  831.     if (c == '^' && *++cp == 0)
  832.         goto bad_cclass;
  833.  
  834.     while ((c = *++cp) != ']') {
  835.         if (c == 0) {
  836.       bad_cclass:
  837.         JS_ReportError(state->context,
  838.                    "unterminated character class %s", ocp);
  839.         return NULL;
  840.         }
  841.         if (c == '\\' && cp[1] != 0)
  842.         cp++;
  843.     }
  844.     ren->u.kid2 = (void *)cp++;
  845.  
  846.     /* Since we rule out [] and [^], we can set the non-empty flag. */
  847.     ren->flags = RENODE_SINGLE | RENODE_NONEMPTY;
  848.     break;
  849.  
  850.       case '\\':
  851.     c = *++cp;
  852.     switch (c) {
  853.       case 0:
  854.         JS_ReportError(state->context, "trailing \\ in regular expression");
  855.         return NULL;
  856.  
  857.       case 'f':
  858.       case 'n':
  859.       case 'r':
  860.       case 't':
  861.       case 'v':
  862.         ren = NewRENode(state, REOP_FLAT1, NULL);
  863.         c = js_strchr(js_EscapeMap, c)[-1];
  864.         break;
  865.  
  866.       case 'd':
  867.         ren = NewRENode(state, REOP_DIGIT, NULL);
  868.         break;
  869.       case 'D':
  870.         ren = NewRENode(state, REOP_NONDIGIT, NULL);
  871.         break;
  872.       case 'w':
  873.         ren = NewRENode(state, REOP_ALNUM, NULL);
  874.         break;
  875.       case 'W':
  876.         ren = NewRENode(state, REOP_NONALNUM, NULL);
  877.         break;
  878.       case 's':
  879.         ren = NewRENode(state, REOP_SPACE, NULL);
  880.         break;
  881.       case 'S':
  882.         ren = NewRENode(state, REOP_NONSPACE, NULL);
  883.         break;
  884.  
  885.       case '0':
  886.       do_octal:
  887.         num = 0;
  888.         while ('0' <= (c = *++cp) && c <= '7') {
  889.         tmp = 8 * num + (uintN)JS7_UNDEC(c);
  890.         if (tmp > 0377)
  891.             break;
  892.         num = tmp;
  893.         }
  894.         cp--;
  895.         ren = NewRENode(state, REOP_FLAT1, NULL);
  896.         c = (jschar)num;
  897.         break;
  898.  
  899.       case '1':
  900.       case '2':
  901.       case '3':
  902.       case '4':
  903.       case '5':
  904.       case '6':
  905.       case '7':
  906.       case '8':
  907.       case '9':
  908.         num = (uintN)JS7_UNDEC(c);
  909.         for (c = *++cp; JS7_ISDEC(c); c = *++cp)
  910.         num = 10 * num - (uintN)JS7_UNDEC(c);
  911.         if (num > 9 && num > state->parenCount) {
  912.         cp = ocp;
  913.         goto do_octal;
  914.         }
  915.         cp--;
  916.         ren = NewRENode(state, REOP_BACKREF, NULL);
  917.         if (!ren)
  918.         return NULL;
  919.         ren->u.num = num - 1;    /* \1 is numbered 0, etc. */
  920.  
  921.         /* Avoid common chr- and flags-setting code after switch. */
  922.         ren->flags = RENODE_NONEMPTY;
  923.         goto bump_cp;
  924.  
  925.       case 'x':
  926.         ocp = cp;
  927.         c = *++cp;
  928.         if (JS7_ISHEX(c)) {
  929.         num = JS7_UNHEX(c);
  930.         c = *++cp;
  931.         if (JS7_ISHEX(c)) {
  932.             num <<= 4;
  933.             num += JS7_UNHEX(c);
  934.         } else {
  935.             cp--;    /* back up so cp points to last hex char */
  936.         }
  937.         } else {
  938.         cp = ocp;    /* \xZZ is xZZ (Perl does \0ZZ!) */
  939.         num = 'x';
  940.         }
  941.         ren = NewRENode(state, REOP_FLAT1, NULL);
  942.         c = (jschar)num;
  943.         break;
  944.  
  945.       case 'c':
  946.         c = *++cp;
  947.         if (!JS7_ISLET(c)) {
  948.         cp -= 2;
  949.         ocp = cp;
  950.         goto do_flat;
  951.         }
  952.         c = JS_TOUPPER(c);
  953.         c = JS_TOCTRL(c);
  954.         ren = NewRENode(state, REOP_FLAT1, NULL);
  955.         break;
  956.  
  957.       case 'u':
  958.         if (JS7_ISHEX(cp[1]) && JS7_ISHEX(cp[2]) &&
  959.         JS7_ISHEX(cp[3]) && JS7_ISHEX(cp[4])) {
  960.         c = (((((JS7_UNHEX(cp[1]) << 4) + JS7_UNHEX(cp[2])) << 4)
  961.               + JS7_UNHEX(cp[3])) << 4) + JS7_UNHEX(cp[4]);
  962.         cp += 4;
  963.         ren = NewRENode(state, REOP_FLAT1, NULL);
  964.         break;
  965.         }
  966.  
  967.         /* Unlike Perl \xZZ, we take \uZZZ to be literal-u then ZZZ. */
  968.         ocp = cp;
  969.         goto do_flat;
  970.  
  971.       default:
  972.         ocp = cp;
  973.         goto do_flat;
  974.     }
  975.  
  976.     /* Common chr- and flags-setting code for escape opcodes. */
  977.     if (ren) {
  978.         ren->u.chr = c;
  979.         ren->flags = RENODE_SINGLE | RENODE_NONEMPTY;
  980.     }
  981.  
  982.       bump_cp:
  983.     /* Skip to next unparsed char. */
  984.     cp++;
  985.     break;
  986.  
  987.       default:
  988.       do_flat:
  989.     while ((c = *++cp) != 0 && !js_strchr(metachars, c))
  990.         ;
  991.     len = (uintN)(cp - ocp);
  992.     if (c != 0 && len > 1 && js_strchr(closurechars, c)) {
  993.         cp--;
  994.         len--;
  995.     }
  996.     if (len > REOP_FLATLEN_MAX) {
  997.         len = REOP_FLATLEN_MAX;
  998.         cp = ocp + len;
  999.     }
  1000.     ren = NewRENode(state, (len == 1) ? REOP_FLAT1 : REOP_FLAT,
  1001.             (void *)ocp);
  1002.     if (!ren)
  1003.         return NULL;
  1004.     ren->flags = RENODE_NONEMPTY;
  1005.     if (len > 1) {
  1006.         ren->u.kid2 = (void *)cp;
  1007.     } else {
  1008.         ren->flags |= RENODE_SINGLE;
  1009.         ren->u.chr = *ocp;
  1010.     }
  1011.     break;
  1012.     }
  1013.  
  1014.     state->cp = cp;
  1015.     return ren;
  1016. }
  1017.  
  1018. static ptrdiff_t
  1019. CountFirstChars(RENode *alt)
  1020. {
  1021.     ptrdiff_t len, sublen;
  1022.     RENode *kid;
  1023.     jschar c, *ccp, *ccend;
  1024.  
  1025.     len = 0;
  1026.     do {
  1027.     for (kid = alt->kid; REOP(kid) == REOP_LPAREN; kid = kid->kid)
  1028.         ;
  1029.     switch (REOP(kid)) {
  1030.       case REOP_QUANT:
  1031.         if (kid->u.range.min == 0)
  1032.             return -1;
  1033.         /* FALL THROUGH */
  1034.       case REOP_PLUS:
  1035.       case REOP_ALT:
  1036.         sublen = CountFirstChars(kid);
  1037.         if (sublen < 0)
  1038.             return sublen;
  1039.         len += sublen;
  1040.         break;
  1041.       case REOP_FLAT:
  1042.         c = *(jschar *)kid->kid;
  1043.         goto count_char;
  1044.       case REOP_FLAT1:
  1045.         c = kid->u.chr;
  1046.       count_char:
  1047.         /* Only '\\' and '-' need escaping within a character class. */
  1048.         if (c == '\\' || c == '-')
  1049.             len += 2;
  1050.         else
  1051.         len++;
  1052.         break;
  1053.       case REOP_CCLASS:
  1054.         ccp = kid->kid;
  1055.         if (*ccp == '^')
  1056.         return -1;
  1057.         ccend = kid->u.kid2;
  1058.         len += ccend - ccp;
  1059.         break;
  1060.       case REOP_DIGIT:
  1061.       case REOP_NONDIGIT:
  1062.       case REOP_ALNUM:
  1063.       case REOP_NONALNUM:
  1064.       case REOP_SPACE:
  1065.       case REOP_NONSPACE:
  1066.         len += 2;
  1067.         break;
  1068.       default:
  1069.         return -1;
  1070.     }
  1071.     /* Test for non-alt so quant and plus execute to here only. */
  1072.     if (REOP(alt) != REOP_ALT)
  1073.         break;
  1074.     alt = alt->next;
  1075.     } while (alt && REOP(alt) == REOP_ALT);
  1076.     return len;
  1077. }
  1078.  
  1079. static ptrdiff_t
  1080. StoreChar(jschar *cp, ptrdiff_t i, jschar c, JSBool escape)
  1081. {
  1082.     ptrdiff_t j;
  1083.  
  1084.     /* Suppress dups to avoid making a flat1 into a cclass. */
  1085.     for (j = 0; j < i; j++) {
  1086.     if (cp[j] == '\\')
  1087.         j++;
  1088.     if (cp[j] == c && (!escape || (j > 0 && cp[j-1] == '\\')))
  1089.         return i;
  1090.     }
  1091.  
  1092.     /* Only '\\' and '-' need escaping within a character class. */
  1093.     if (escape || c == '\\' || c == '-')
  1094.     cp[i++] = '\\';
  1095.     cp[i++] = c;
  1096.     return i;
  1097. }
  1098.  
  1099. static ptrdiff_t
  1100. StoreFirstChars(RENode *alt, jschar *cp, ptrdiff_t i)
  1101. {
  1102.     RENode *kid;
  1103.     jschar *ccp, *ccend;
  1104.  
  1105.     do {
  1106.     for (kid = alt->kid; REOP(kid) == REOP_LPAREN; kid = kid->kid)
  1107.         ;
  1108.     switch (REOP(kid)) {
  1109.       case REOP_QUANT:
  1110.         PR_ASSERT(kid->u.range.min != 0);
  1111.         /* FALL THROUGH */
  1112.       case REOP_PLUS:
  1113.       case REOP_ALT:
  1114.         i = StoreFirstChars(kid, cp, i);
  1115.         break;
  1116.       case REOP_FLAT:
  1117.         i = StoreChar(cp, i, *(jschar *)kid->kid, JS_FALSE);
  1118.         break;
  1119.       case REOP_FLAT1:
  1120.         i = StoreChar(cp, i, kid->u.chr, JS_FALSE);
  1121.         break;
  1122.       case REOP_CCLASS:
  1123.         ccend = kid->u.kid2;
  1124.         for (ccp = kid->kid; ccp < ccend; ccp++)
  1125.         cp[i++] = *ccp;
  1126.         break;
  1127.       case REOP_DIGIT:
  1128.         i = StoreChar(cp, i, 'd', JS_TRUE);
  1129.         break;
  1130.       case REOP_NONDIGIT:
  1131.         i = StoreChar(cp, i, 'D', JS_TRUE);
  1132.         break;
  1133.       case REOP_ALNUM:
  1134.         i = StoreChar(cp, i, 'w', JS_TRUE);
  1135.         break;
  1136.       case REOP_NONALNUM:
  1137.         i = StoreChar(cp, i, 'W', JS_TRUE);
  1138.         break;
  1139.       case REOP_SPACE:
  1140.         i = StoreChar(cp, i, 's', JS_TRUE);
  1141.         break;
  1142.       case REOP_NONSPACE:
  1143.         i = StoreChar(cp, i, 'S', JS_TRUE);
  1144.         break;
  1145.       default:
  1146.         PR_ASSERT(0);
  1147.     }
  1148.     /* Test for non-alt so quant and plus execute to here only. */
  1149.     if (REOP(alt) != REOP_ALT)
  1150.         break;
  1151.     alt = alt->next;
  1152.     } while (alt && REOP(alt) == REOP_ALT);
  1153.     return i;
  1154. }
  1155.  
  1156. static JSBool
  1157. AnchorRegExp(CompilerState *state, RENode *ren)
  1158. {
  1159.     RENode *ren2, *kid;
  1160.     ptrdiff_t len;
  1161.     jschar *cp;
  1162.     REOp op;
  1163.  
  1164.     for (ren2 = ren; REOP(ren2) == REOP_LPAREN; ren2 = ren2->kid)
  1165.     ;
  1166.     switch (REOP(ren2)) {
  1167.       case REOP_ALT:
  1168.     len = CountFirstChars(ren2);
  1169.     if (len <= 0)
  1170.         goto do_anchor;
  1171.     PR_ARENA_ALLOCATE(cp, &state->context->tempPool, len * sizeof(jschar));
  1172.     if (!cp) {
  1173.         JS_ReportOutOfMemory(state->context);
  1174.         return JS_FALSE;
  1175.     }
  1176.  
  1177.     len = StoreFirstChars(ren2, cp, 0);
  1178.     if (len == 1) {
  1179.         op = REOP_FLAT1;
  1180.     } else if (len == 2 && *cp == '\\') {
  1181.         switch (cp[1]) {
  1182.           case '\\':
  1183.           case '-':
  1184.         /* No need for a character class if just '\\' or '-'. */
  1185.         cp++;
  1186.         op = REOP_FLAT1;
  1187.         break;
  1188.           case 'd':
  1189.         op = REOP_DIGIT;
  1190.         break;
  1191.           case 'D':
  1192.         op = REOP_NONDIGIT;
  1193.         break;
  1194.           case 'w':
  1195.         op = REOP_ALNUM;
  1196.         break;
  1197.           case 'W':
  1198.         op = REOP_NONALNUM;
  1199.         break;
  1200.           case 's':
  1201.         op = REOP_SPACE;
  1202.         break;
  1203.           case 'S':
  1204.         op = REOP_NONSPACE;
  1205.         break;
  1206.           default:
  1207.         op = REOP_CCLASS;
  1208.         break;
  1209.         }
  1210.     } else {
  1211.         op = REOP_CCLASS;
  1212.     }
  1213.  
  1214.       do_first_char:
  1215.     kid = NewRENode(state, op, cp);
  1216.     if (!kid)
  1217.         return JS_FALSE;
  1218.     kid->flags = RENODE_SINGLE | RENODE_NONEMPTY;
  1219.     if (op == REOP_FLAT1)
  1220.         kid->u.chr = *cp;
  1221.     else if (op == REOP_CCLASS)
  1222.         kid->u.kid2 = cp + len;
  1223.  
  1224.     ren2 = NewRENode(state, REOP(ren), ren->kid);
  1225.     if (!ren2)
  1226.         return JS_FALSE;
  1227.     ren2->flags = ren->flags | RENODE_ISNEXT;
  1228.     ren2->next = ren->next;
  1229.     ren2->u = ren->u;
  1230.  
  1231.     ren->op = REOP_ANCHOR1;
  1232.     ren->flags = RENODE_GOODNEXT;
  1233.     ren->next = ren2;
  1234.     ren->kid = kid;
  1235.     ren->u.kid2 = NULL;
  1236.     break;
  1237.  
  1238.       case REOP_FLAT:
  1239.     cp = ren2->kid;
  1240.     op = REOP_FLAT1;
  1241.     goto do_first_char;
  1242.  
  1243.       case REOP_FLAT1:
  1244.           cp = &ren2->u.chr;
  1245.           op = REOP_FLAT1;
  1246.     goto do_first_char;
  1247.  
  1248.       case REOP_DOTSTAR:
  1249.     /*
  1250.      * ".*" is anchored by definition when at the front of a list.
  1251.      */
  1252.     break;
  1253.  
  1254.       default:
  1255.       do_anchor:
  1256.     /*
  1257.      * Any node other than dotstar that's unanchored and nonempty must be
  1258.      * prefixed by REOP_ANCHOR.
  1259.      */
  1260.     PR_ASSERT(REOP(ren2) != REOP_ANCHOR);
  1261.     PR_ASSERT(!(ren2->flags & RENODE_ISNEXT));
  1262.     if ((ren2->flags & (RENODE_ANCHORED | RENODE_NONEMPTY))
  1263.         == RENODE_NONEMPTY) {
  1264.         ren2 = NewRENode(state, REOP(ren), ren->kid);
  1265.         if (!ren2)
  1266.         return JS_FALSE;
  1267.         ren2->flags = ren->flags | RENODE_ISNEXT;
  1268.         ren2->next = ren->next;
  1269.         ren2->u = ren->u;
  1270.         ren->op = REOP_ANCHOR;
  1271.         ren->flags = RENODE_GOODNEXT;
  1272.         ren->next = ren2;
  1273.         ren->kid = ren->u.kid2 = NULL;
  1274.     }
  1275.     break;
  1276.     }
  1277.     return JS_TRUE;
  1278. }
  1279.  
  1280. static RENode *
  1281. CloseTail(CompilerState *state, RENode *alt1, RENode *next)
  1282. {
  1283.     RENode *alt2, *empty;
  1284.  
  1285.     empty = NewRENode(state, REOP_EMPTY, NULL);
  1286.     alt2 = NewRENode(state, REOP_ALT, empty);
  1287.     if (!alt2 || !empty)
  1288.     return NULL;
  1289.     alt1->next = alt2;
  1290.     alt2->next = empty->next = next;
  1291.     if (alt1->flags & RENODE_GOODNEXT)
  1292.     alt2->flags |= RENODE_GOODNEXT;
  1293.     else
  1294.     alt1->flags |= RENODE_GOODNEXT;
  1295.     alt2->flags |= RENODE_ISNEXT;
  1296.     return alt2;
  1297. }
  1298.  
  1299. static JSBool
  1300. OptimizeRegExp(CompilerState *state, RENode *ren)
  1301. {
  1302.     RENode *kid, *next, *jump, *alt1;
  1303.     uintN flag;
  1304.     jschar c, c2, maxc, *cp, *cp2;
  1305.     ptrdiff_t len, len2;
  1306.     size_t size, incr;
  1307.     JSContext *cx;
  1308.     JSBool reallok;
  1309.  
  1310.     do {
  1311.     switch (REOP(ren)) {
  1312.       case REOP_STAR:
  1313.         kid = ren->kid;
  1314.         if (!(kid->flags & RENODE_SINGLE)) {
  1315.         /*
  1316.          * If kid is not simple, deoptimize <kid>* as follows (the |__|
  1317.          * are byte placeholders for next/jump offsets):
  1318.          *
  1319.          * FROM: |STAR|<kid>|
  1320.          *
  1321.          *       +-----------------------+
  1322.          *       V                       |
  1323.          * TO:   |ALT|__|__|<kid>|JUMP|__|__|ALT|__|__|EMPTY|
  1324.          *              |                   ^      |        ^
  1325.          *              +-------------------+      +--------+
  1326.          */
  1327.         ren->op = REOP_ALT;
  1328.         next = ren->next;
  1329.         jump = NewRENode(state, REOP_JUMP, NULL);
  1330.         if (!jump || !FixNext(state, kid, jump, next))
  1331.             return JS_FALSE;
  1332.         jump->next = ren;
  1333.         if (ren->flags & RENODE_ISNEXT)
  1334.             ren->flags |= RENODE_ISJOIN;
  1335.         if (!CloseTail(state, ren, next))
  1336.             return JS_FALSE;
  1337.         }
  1338.         break;
  1339.  
  1340.       case REOP_PLUS:
  1341.         kid = ren->kid;
  1342.         if (!(kid->flags & RENODE_SINGLE)) {
  1343.         /*
  1344.          * FROM: |PLUS|<kid>|
  1345.          *
  1346.          *       +-----------------------+
  1347.          *       V                       |
  1348.          * TO:   |<kid>|ALT|__|__|JUMP|__|__|ALT|__|__|EMPTY|
  1349.          *                    |             ^      |        ^
  1350.          *                    +-------------+      +--------+
  1351.          */
  1352.         next = ren->next;
  1353.         flag = (ren->flags & RENODE_GOODNEXT);
  1354.         *ren = *kid;
  1355.         jump = NewRENode(state, REOP_JUMP, NULL);
  1356.         alt1 = NewRENode(state, REOP_ALT, jump);
  1357.         if (!alt1 || !jump || !FixNext(state, ren, alt1, next))
  1358.             return JS_FALSE;
  1359.         alt1->flags |= flag;
  1360.         jump->next = ren;
  1361.         if (ren->flags & RENODE_ISNEXT)
  1362.             ren->flags |= RENODE_ISJOIN;
  1363.         if (!CloseTail(state, alt1, next))
  1364.             return JS_FALSE;
  1365.         }
  1366.         break;
  1367.  
  1368.       case REOP_OPT:
  1369.         kid = ren->kid;
  1370.         if (!(kid->flags & RENODE_SINGLE)) {
  1371.         /*
  1372.          * FROM: |OPT|<kid>|
  1373.          *
  1374.          *                               +------------------+
  1375.          *                               |                  v
  1376.          * TO:   |ALT|__|__|<kid>|JUMP|__|__|ALT|__|__|EMPTY|
  1377.          *              |                   ^      |        ^
  1378.          *              +-------------------+      +--------+
  1379.          */
  1380.         ren->op = REOP_ALT;
  1381.         next = ren->next;
  1382.         jump = NewRENode(state, REOP_JUMP, NULL);
  1383.         if (!jump || !FixNext(state, kid, jump, next))
  1384.             return JS_FALSE;
  1385.         jump->next = next;
  1386.         if (!CloseTail(state, ren, next))
  1387.             return JS_FALSE;
  1388.         next->flags |= RENODE_ISJOIN;
  1389.         }
  1390.         break;
  1391.  
  1392.       case REOP_FLAT:
  1393.         /*
  1394.          * Coalesce adjacent FLAT and FLAT1 nodes.  Also coalesce FLAT and
  1395.          * FLAT, which can result from deleting a coalesced FLAT1.
  1396.          */
  1397.         while ((next = ren->next) &&
  1398.            !(next->flags & RENODE_ISJOIN) &&
  1399.            (REOP(next) == REOP_FLAT || REOP(next) == REOP_FLAT1)) {
  1400.         if (REOP(next) == REOP_FLAT) {
  1401.             cp2 = next->kid;
  1402.             len2 = (jschar *)next->u.kid2 - cp2;
  1403.         } else {
  1404.             cp2 = &next->u.chr;
  1405.             len2 = 1;
  1406.         }
  1407.         cp = ren->kid;
  1408.         len = (jschar *)ren->u.kid2 - cp;
  1409.         if (len + len2 > REOP_FLATLEN_MAX)
  1410.             break;
  1411.         cx = state->context;
  1412.         reallok = ren->flags & RENODE_REALLOK;
  1413.         if (reallok) {
  1414.             /* Try to extend the last alloc, to fuse FLAT,FLAT1,... */
  1415.             size = (len + 1) * sizeof(jschar);
  1416.             incr = len2 * sizeof(jschar);
  1417.             PR_ARENA_GROW(cp, &cx->tempPool, size, incr);
  1418.         } else {
  1419.             size = (len + len2 + 1) * sizeof(jschar);
  1420.             PR_ARENA_ALLOCATE(cp, &cx->tempPool, size);
  1421.         }
  1422.         if (!cp) {
  1423.             JS_ReportOutOfMemory(cx);
  1424.             return JS_FALSE;
  1425.         }
  1426.         if (!reallok) {
  1427.             js_strncpy(cp, ren->kid, len);
  1428.             ren->flags |= RENODE_REALLOK;
  1429.         }
  1430.         js_strncpy(&cp[len], cp2, len2);
  1431.         len += len2;
  1432.         cp[len] = 0;
  1433.       end_coalesce:
  1434.         ren->kid = cp;
  1435.         PR_ASSERT(ren->flags & RENODE_GOODNEXT);
  1436.         if (!(next->flags & RENODE_GOODNEXT))
  1437.             ren->flags &= ~RENODE_GOODNEXT;
  1438.         ren->u.kid2 = cp + len;
  1439.         ren->next = next->next;
  1440.         next->op = REOP_EMPTY;    /* next should be unreachable! */
  1441.         }
  1442.         break;
  1443.  
  1444.       case REOP_FLAT1:
  1445.         /*
  1446.          * Coalesce adjacent FLAT1 nodes.  Also coalesce FLAT1 and FLAT.
  1447.          * After a single coalesce, we reuse the REOP_FLAT case's code by
  1448.          * jumping into the bottom of its while loop.
  1449.          */
  1450.         next = ren->next;
  1451.         if (next &&
  1452.         !(next->flags & RENODE_ISJOIN) &&
  1453.         (REOP(next) == REOP_FLAT || REOP(next) == REOP_FLAT1)) {
  1454.         if (REOP(next) == REOP_FLAT) {
  1455.             cp2 = next->kid;
  1456.             len = (jschar *)next->u.kid2 - cp2;
  1457.         } else {
  1458.             cp2 = &next->u.chr;
  1459.             len = 1;
  1460.         }
  1461.         cx = state->context;
  1462.         PR_ARENA_ALLOCATE(cp, &cx->tempPool, len + 2);
  1463.         if (!cp) {
  1464.             JS_ReportOutOfMemory(cx);
  1465.             return JS_FALSE;
  1466.         }
  1467.         cp[0] = ren->u.chr;
  1468.         js_strncpy(&cp[1], cp2, len);
  1469.         cp[++len] = 0;
  1470.         ren->op = REOP_FLAT;
  1471.         ren->flags |= RENODE_REALLOK;
  1472.         goto end_coalesce;
  1473.         }
  1474.         break;
  1475.  
  1476.       default:;
  1477.     }
  1478.  
  1479.     /*
  1480.      * Set ren's offset and advance progLength by ren's base size.
  1481.      */
  1482.     ren->offset = (uint16) state->progLength;
  1483.     state->progLength += reopsize[ren->op];
  1484.  
  1485.     switch (REOP(ren)) {
  1486.       case REOP_ALT:
  1487.       case REOP_QUANT:
  1488.       case REOP_STAR:
  1489.       case REOP_PLUS:
  1490.       case REOP_OPT:
  1491.       case REOP_LPAREN:
  1492.       case REOP_ANCHOR1:
  1493.         /*
  1494.          * Recur for nodes that have kid links to other nodes.
  1495.          */
  1496.         if (!OptimizeRegExp(state, ren->kid))
  1497.         return JS_FALSE;
  1498.         break;
  1499.  
  1500.       case REOP_CCLASS:
  1501.         /*
  1502.          * Check for a nonzero high byte or a \uXXXX escape sequence.
  1503.          */
  1504.         cp  = ren->kid;
  1505.         cp2 = ren->u.kid2;
  1506.         len = cp2 - cp;
  1507.         maxc = 0;
  1508.         while (cp < cp2) {
  1509.         c = *cp++;
  1510.         if (c == '\\') {
  1511.             if (cp + 5 <= cp2 && *cp == 'u' &&
  1512.             JS7_ISHEX(cp[1]) && JS7_ISHEX(cp[2]) &&
  1513.             JS7_ISHEX(cp[3]) && JS7_ISHEX(cp[4])) {
  1514.             c = (((((JS7_UNHEX(cp[1]) << 4)
  1515.                     + JS7_UNHEX(cp[2])) << 4)
  1516.                   + JS7_UNHEX(cp[3])) << 4)
  1517.                 + JS7_UNHEX(cp[4]);
  1518.             cp += 5;
  1519.             } else {
  1520.             /*
  1521.              * Octal and hex escapes can't be > 255.  Skip this
  1522.              * backslash and let the loop pass over the remaining
  1523.              * escape sequence as if it were text to match.
  1524.              */
  1525.             continue;
  1526.             }
  1527.         }
  1528.         if (state->flags & JSREG_FOLD) {
  1529.             /*
  1530.              * Don't assume that lowercase are above uppercase, or
  1531.              * that c is either even when c has upper and lowercase
  1532.              * versions.
  1533.              */
  1534.             if ((c2 = JS_TOUPPER(c)) > maxc)
  1535.             maxc = c2;
  1536.             if ((c2 = JS_TOLOWER(c2)) > maxc)
  1537.             maxc = c2;
  1538.         }
  1539.         if (c > maxc)
  1540.             maxc = c;
  1541.         }
  1542.         if (maxc >= CCLASS_CHARSET_SIZE) {
  1543.         ren->op = (uint8)REOP_UCCLASS;
  1544.         size = (size_t)(maxc + PR_BITS_PER_BYTE) / PR_BITS_PER_BYTE;
  1545.         ren->u.ucclass.kidlen = (uint16)len;
  1546.         ren->u.ucclass.bmsize = (uint16)size;
  1547.         state->progLength -= reopsize[REOP_CCLASS];
  1548.         state->progLength += reopsize[REOP_UCCLASS] + size;
  1549.         }
  1550.         break;
  1551.  
  1552.       case REOP_FLAT:
  1553.         /*
  1554.          * FLAT takes 2 bytes plus the bytes in the string to match.
  1555.          * If any character has a non-zero high byte, switch to UCFLAT
  1556.          * and double the immediate operand length.
  1557.          */
  1558.         cp  = ren->kid;
  1559.         cp2 = ren->u.kid2;
  1560.         len = cp2 - cp;
  1561.         while (cp < cp2) {
  1562.         c = *cp++;
  1563.         if (c >> 8) {
  1564.             ren->op = (uint8)REOP_UCFLAT;
  1565.             len *= 2;
  1566.             break;
  1567.         }
  1568.         }
  1569.         state->progLength += len;
  1570.         break;
  1571.  
  1572.       case REOP_FLAT1:
  1573.         c = ren->u.chr;
  1574.         if (c >> 8) {
  1575.         ren->op = (uint8)REOP_UCFLAT1;
  1576.         state->progLength++;
  1577.         }
  1578.         break;
  1579.  
  1580.       case REOP_JUMP:
  1581.         /*
  1582.          * Eliminate jumps to jumps.
  1583.          */
  1584.         while ((next = ren->next) != NULL && REOP(next) == REOP_JUMP)
  1585.         ren->next = next->next;
  1586.         break;
  1587.  
  1588.       case REOP_END:
  1589.         /*
  1590.          * End of program.
  1591.          */
  1592.         return JS_TRUE;
  1593.  
  1594.       default:;
  1595.     }
  1596.  
  1597.     if (!(ren->flags & RENODE_GOODNEXT))
  1598.         break;
  1599.     } while ((ren = ren->next) != NULL);
  1600.  
  1601.     return JS_TRUE;
  1602. }
  1603.  
  1604. static JSBool
  1605. EmitRegExp(CompilerState *state, RENode *ren, JSRegExp *re)
  1606. {
  1607.     REOp op;
  1608.     jsbytecode *pc, fill;
  1609.     RENode *next;
  1610.     ptrdiff_t diff;
  1611.     jschar *cp, *end, *ocp;
  1612.     uintN b, c, i, j, n, lastc, foldc, nchars;
  1613.     JSBool inrange;
  1614.  
  1615.     do {
  1616.     op = REOP(ren);
  1617.     if (op == REOP_END)
  1618.         return JS_TRUE;
  1619.  
  1620.     pc = &re->program[state->progLength];
  1621.     state->progLength += reopsize[ren->op];
  1622.     pc[0] = ren->op;
  1623.     next = ren->next;
  1624.  
  1625.     switch (op) {
  1626.       case REOP_ALT:
  1627.         diff = next->offset - ren->offset;
  1628.         SET_JUMP_OFFSET(pc, diff);
  1629.         if (!EmitRegExp(state, ren->kid, re))
  1630.         return JS_FALSE;
  1631.         break;
  1632.  
  1633.       case REOP_QUANT:
  1634.         diff = next->offset - ren->offset;
  1635.         SET_JUMP_OFFSET(pc, diff);
  1636.         pc += 2;
  1637.         SET_ARGNO(pc, ren->u.range.min);
  1638.         pc += 2;
  1639.         SET_ARGNO(pc, ren->u.range.max);
  1640.         if (!EmitRegExp(state, ren->kid, re))
  1641.         return JS_FALSE;
  1642.         break;
  1643.  
  1644.       case REOP_STAR:
  1645.       case REOP_PLUS:
  1646.       case REOP_OPT:
  1647.       case REOP_ANCHOR1:
  1648.         if (!EmitRegExp(state, ren->kid, re))
  1649.         return JS_FALSE;
  1650.         break;
  1651.  
  1652.       case REOP_LPAREN:
  1653.         SET_ARGNO(pc, ren->u.num);
  1654.         if (!EmitRegExp(state, ren->kid, re))
  1655.         return JS_FALSE;
  1656.         break;
  1657.  
  1658.       case REOP_RPAREN:
  1659.         SET_ARGNO(pc, ren->u.num);
  1660.         break;
  1661.  
  1662.       case REOP_CCLASS:
  1663.       case REOP_UCCLASS:
  1664.         cp = ren->kid;
  1665.         if (*cp == '^') {
  1666.         if (op == REOP_UCCLASS)
  1667.             pc[0] = (jsbytecode)REOP_NUCCLASS;
  1668.         fill = 0xff;
  1669.         cp++;
  1670.         } else {
  1671.         fill = 0;
  1672.         }
  1673.         pc++;
  1674.         if (op == REOP_CCLASS) {
  1675.         end = ren->u.kid2;
  1676.         for (i = 0; i < CCLASS_CHARSET_SIZE / PR_BITS_PER_BYTE; i++)
  1677.             pc[i] = fill;
  1678.         nchars = CCLASS_CHARSET_SIZE;
  1679.         } else {
  1680.         end = cp + ren->u.ucclass.kidlen;
  1681.         n = (uintN)ren->u.ucclass.bmsize;
  1682.         *pc++ = (jsbytecode)(n >> 8);
  1683.         *pc++ = (jsbytecode)n;
  1684.         state->progLength += n;
  1685.         for (i = 0; i < n; i++)
  1686.             pc[i] = fill;
  1687.         nchars = n * PR_BITS_PER_BYTE;
  1688.         }
  1689.  
  1690. /* Split ops up into statements to keep MSVC1.52 from crashing. */
  1691. #define MATCH_BIT(c)    { i = (c) >> 3; b = (c) & 7; b = 1 << b;              \
  1692.               if (fill) pc[i] &= ~b; else pc[i] |= b; }
  1693.  
  1694.         lastc = nchars;
  1695.         inrange = JS_FALSE;
  1696.  
  1697.         while (cp < end) {
  1698.         c = (uintN) *cp++;
  1699.         if (c == '\\') {
  1700.             c = *cp++;
  1701.             switch (c) {
  1702.               case 'b':
  1703.               case 'f':
  1704.               case 'n':
  1705.               case 'r':
  1706.               case 't':
  1707.               case 'v':
  1708.             c = js_strchr(js_EscapeMap, (jschar)c)[-1];
  1709.             break;
  1710.  
  1711. #define CHECK_RANGE() if (inrange) { MATCH_BIT(lastc); MATCH_BIT('-');        \
  1712.                      inrange = JS_FALSE; }
  1713.  
  1714.               case 'd':
  1715.             CHECK_RANGE();
  1716.             for (c = '0'; c <= '9'; c++)
  1717.                 MATCH_BIT(c);
  1718.             continue;
  1719.  
  1720.               case 'D':
  1721.             CHECK_RANGE();
  1722.             for (c = 0; c < '0'; c++)
  1723.                 MATCH_BIT(c);
  1724.             for (c = '9' + 1; c < nchars; c++)
  1725.                 MATCH_BIT(c);
  1726.             continue;
  1727.  
  1728.               case 'w':
  1729.             CHECK_RANGE();
  1730.             for (c = 0; c < nchars; c++)
  1731.                 if (JS_ISWORD(c))
  1732.                 MATCH_BIT(c);
  1733.             continue;
  1734.  
  1735.               case 'W':
  1736.             CHECK_RANGE();
  1737.             for (c = 0; c < nchars; c++)
  1738.                 if (!JS_ISWORD(c))
  1739.                 MATCH_BIT(c);
  1740.             continue;
  1741.  
  1742.               case 's':
  1743.             CHECK_RANGE();
  1744.             for (c = 0; c < nchars; c++)
  1745.                 if (JS_ISSPACE(c))
  1746.                 MATCH_BIT(c);
  1747.             continue;
  1748.  
  1749.               case 'S':
  1750.             CHECK_RANGE();
  1751.             for (c = 0; c < nchars; c++)
  1752.                 if (!JS_ISSPACE(c))
  1753.                 MATCH_BIT(c);
  1754.             continue;
  1755.  
  1756. #undef CHECK_RANGE
  1757.  
  1758.               case '0':
  1759.               case '1':
  1760.               case '2':
  1761.               case '3':
  1762.               case '4':
  1763.               case '5':
  1764.               case '6':
  1765.               case '7':
  1766.             n = JS7_UNDEC(c);
  1767.             ocp = cp - 2;
  1768.             c = *cp;
  1769.             if ('0' <= c && c <= '7') {
  1770.                 cp++;
  1771.                 n = 8 * n + JS7_UNDEC(c);
  1772.  
  1773.                 c = *cp;
  1774.                 if ('0' <= c && c <= '7') {
  1775.                 cp++;
  1776.                 i = 8 * n + JS7_UNDEC(c);
  1777.                 if (i <= 0377)
  1778.                     n = i;
  1779.                 else
  1780.                     cp--;
  1781.                 }
  1782.             }
  1783.             c = n;
  1784.             break;
  1785.  
  1786.               case 'x':
  1787.             ocp = cp;
  1788.             c = *cp++;
  1789.             if (JS7_ISHEX(c)) {
  1790.                 n = JS7_UNHEX(c);
  1791.                 c = *cp++;
  1792.                 if (JS7_ISHEX(c)) {
  1793.                 n <<= 4;
  1794.                 n += JS7_UNHEX(c);
  1795.                 }
  1796.             } else {
  1797.                 cp = ocp;    /* \xZZ is xZZ (Perl does \0ZZ!) */
  1798.                 n = 'x';
  1799.             }
  1800.             c = n;
  1801.             break;
  1802.  
  1803.               case 'u':
  1804.             if (JS7_ISHEX(cp[0]) && JS7_ISHEX(cp[1]) &&
  1805.                 JS7_ISHEX(cp[2]) && JS7_ISHEX(cp[3])) {
  1806.                 n = (((((JS7_UNHEX(cp[0]) << 4)
  1807.                     + JS7_UNHEX(cp[1])) << 4)
  1808.                   + JS7_UNHEX(cp[2])) << 4)
  1809.                 + JS7_UNHEX(cp[3]);
  1810.                 c = n;
  1811.                 cp += 4;
  1812.             }
  1813.             break;
  1814.  
  1815.               case 'c':
  1816.             c = *cp++;
  1817.             c = JS_TOUPPER(c);
  1818.             c = JS_TOCTRL(c);
  1819.             break;
  1820.             }
  1821.         }
  1822.  
  1823.         if (inrange) {
  1824.             if (lastc > c) {
  1825.             JS_ReportError(state->context,
  1826.                        "invalid range in character class");
  1827.             return JS_FALSE;
  1828.             }
  1829.             inrange = JS_FALSE;
  1830.         } else {
  1831.             /* Set lastc so we match just c's bit in the for loop. */
  1832.             lastc = c;
  1833.  
  1834.             /* [balance: */
  1835.             if (*cp == '-' && cp + 1 < end && cp[1] != ']') {
  1836.             cp++;
  1837.             inrange = JS_TRUE;
  1838.             continue;
  1839.             }
  1840.         }
  1841.  
  1842.         /* Match characters in the range [lastc, c]. */
  1843.         for (; lastc <= c; lastc++) {
  1844.             MATCH_BIT(lastc);
  1845.             if (state->flags & JSREG_FOLD) {
  1846.             /*
  1847.              * Must do both upper and lower for Turkish dotless i,
  1848.              * Georgian, etc.
  1849.              */
  1850.             foldc = JS_TOUPPER(lastc);
  1851.             MATCH_BIT(foldc);
  1852.             foldc = JS_TOLOWER(foldc);
  1853.             MATCH_BIT(foldc);
  1854.             }
  1855.         }
  1856.         lastc = c;
  1857.         }
  1858.  
  1859. #undef MATCH_BIT
  1860.         break;
  1861.  
  1862.       case REOP_BACKREF:
  1863.         if (state->flags & JSREG_FOLD)
  1864.         pc[0] = (jsbytecode)REOP_BACKREFi;
  1865.         pc[1] = (jsbytecode)ren->u.num;
  1866.         break;
  1867.  
  1868.       case REOP_FLAT:
  1869.         if (state->flags & JSREG_FOLD)
  1870.         pc[0] = (jsbytecode)REOP_FLATi;
  1871.         goto emit_flat;
  1872.  
  1873.       case REOP_UCFLAT:
  1874.         if (state->flags & JSREG_FOLD)
  1875.         pc[0] = (jsbytecode)REOP_UCFLATi;
  1876.       emit_flat:
  1877.         cp = ren->kid;
  1878.         diff = (jschar *)ren->u.kid2 - cp;
  1879.         pc[1] = (jsbytecode)diff;
  1880.         pc += 2;
  1881.         state->progLength += diff;
  1882.         if (op == REOP_UCFLAT)
  1883.         state->progLength += diff;
  1884.         for (i = j = 0; i < (uintN)diff; i++, j++) {
  1885.         c = (uintN)cp[i];
  1886.  
  1887.         /*
  1888.          * Lay down immediate chars in native byte order so memcmp
  1889.          * with a JSString's chars works.
  1890.          */
  1891. #if IS_BIG_ENDIAN
  1892.         if (op == REOP_UCFLAT)
  1893.             pc[j++] = (jsbytecode)(c >> 8);
  1894. #endif
  1895.         pc[j] = (jsbytecode)c;
  1896. #if IS_LITTLE_ENDIAN
  1897.         if (op == REOP_UCFLAT)
  1898.             pc[j++] = (jsbytecode)(c >> 8);
  1899. #endif
  1900.         }
  1901.         break;
  1902.  
  1903.       case REOP_FLAT1:
  1904.         if (state->flags & JSREG_FOLD)
  1905.         pc[0] = (jsbytecode)REOP_FLAT1i;
  1906.         pc[1] = (jsbytecode)ren->u.chr;
  1907.         break;
  1908.  
  1909.       case REOP_UCFLAT1:
  1910.         if (state->flags & JSREG_FOLD)
  1911.         pc[0] = (jsbytecode)REOP_UCFLAT1i;
  1912.         c = (uintN)ren->u.chr;
  1913.         pc[1] = (jsbytecode)(c >> 8);
  1914.         pc[2] = (jsbytecode)c;
  1915.         break;
  1916.  
  1917.       case REOP_JUMP:
  1918.         diff = next->offset - ren->offset;
  1919.         SET_JUMP_OFFSET(pc, diff);
  1920.         break;
  1921.  
  1922.       default:;
  1923.     }
  1924.  
  1925.     if (!(ren->flags & RENODE_GOODNEXT))
  1926.         break;
  1927.     } while ((ren = next) != NULL);
  1928.     return JS_TRUE;
  1929. }
  1930.  
  1931. JSRegExp *
  1932. js_NewRegExp(JSContext *cx, JSString *str, uintN flags)
  1933. {
  1934.     JSRegExp *re;
  1935.     void *mark;
  1936.     CompilerState state;
  1937.     RENode *ren, *end;
  1938.     size_t resize;
  1939.  
  1940.     re = NULL;
  1941.     mark = PR_ARENA_MARK(&cx->tempPool);
  1942.  
  1943.     state.context = cx;
  1944.     state.cpbegin = state.cp = str->chars;
  1945.     state.flags = flags;
  1946.     state.parenCount = 0;
  1947.     state.progLength = 0;
  1948.  
  1949.     ren = ParseRegExp(&state);
  1950.     if (!ren)
  1951.     goto out;
  1952.  
  1953.     end = NewRENode(&state, REOP_END, NULL);
  1954.     if (!end || !SetNext(&state, ren, end))
  1955.     goto out;
  1956.  
  1957.     if (!AnchorRegExp(&state, ren))
  1958.     goto out;
  1959.     if (!OptimizeRegExp(&state, ren))
  1960.     goto out;
  1961.  
  1962. #ifdef DEBUG_notme
  1963.     if (!DumpRegExp(cx, ren))
  1964.     goto out;
  1965. #endif
  1966.  
  1967.     resize = sizeof *re + state.progLength - 1;
  1968.     re = JS_malloc(cx, PR_ROUNDUP(resize, sizeof(prword)));
  1969.     if (!re)
  1970.     goto out;
  1971.     re->source = str;
  1972.     re->length = state.progLength;
  1973.     re->lastIndex = 0;
  1974.     re->parenCount = state.parenCount;
  1975.     re->flags = flags;
  1976.  
  1977.     state.progLength = 0;
  1978.     if (!EmitRegExp(&state, ren, re)) {
  1979.     js_DestroyRegExp(cx, re);
  1980.     re = NULL;
  1981.     goto out;
  1982.     }
  1983.  
  1984.     /* Success: lock re->source string. */
  1985.     (void) js_LockGCThing(cx, str);
  1986. out:
  1987.     PR_ARENA_RELEASE(&cx->tempPool, mark);
  1988.     return re;
  1989. }
  1990.  
  1991. JSRegExp *
  1992. js_NewRegExpOpt(JSContext *cx, JSString *str, JSString *opt)
  1993. {
  1994.     uintN flags;
  1995.     jschar *cp;
  1996.  
  1997.     flags = 0;
  1998.     if (opt) {
  1999.     for (cp = opt->chars; *cp; cp++) {
  2000.         switch (*cp) {
  2001.           case 'g':
  2002.         flags |= JSREG_GLOB;
  2003.         break;
  2004.           case 'i':
  2005.         flags |= JSREG_FOLD;
  2006.         break;
  2007.           default:
  2008.         JS_ReportError(cx, "invalid regular expression flag %c",
  2009.                    (char) *cp);
  2010.         return NULL;
  2011.         }
  2012.     }
  2013.     }
  2014.     return js_NewRegExp(cx, str, flags);
  2015. }
  2016.  
  2017. void
  2018. js_DestroyRegExp(JSContext *cx, JSRegExp *re)
  2019. {
  2020.     js_UnlockGCThing(cx, re->source);
  2021.     JS_free(cx, re);
  2022. }
  2023.  
  2024. typedef struct MatchState {
  2025.     JSContext       *context;           /* for access to regExpStatics */
  2026.     JSBool          anchoring;          /* true if multiline anchoring ^/$ */
  2027.     jsbytecode      *pcend;             /* pc limit (fencepost) */
  2028.     const jschar    *cpbegin, *cpend;   /* cp base address and limit */
  2029.     size_t          start;              /* offset from cpbegin to start at */
  2030.     ptrdiff_t       skipped;            /* chars skipped anchoring this r.e. */
  2031.     uintN           parenCount;         /* number of paren substring matches */
  2032.     JSSubString     *maybeParens;       /* possible paren substring pointers */
  2033.     JSSubString     *parens;            /* certain paren substring matches */
  2034. } MatchState;
  2035.  
  2036. /*
  2037.  * Returns updated cp on match, null on mismatch.
  2038.  */
  2039. static const jschar *
  2040. MatchRegExp(MatchState *state, jsbytecode *pc, const jschar *cp)
  2041. {
  2042.     jsbytecode *pc2, *pcend;
  2043.     const jschar *cp2, *cp3, *cpbegin, *cpend;
  2044.     REOp op;
  2045.     JSBool matched;
  2046.     ptrdiff_t i, oplen, altlen, matchlen;
  2047.     uintN min, max, num;
  2048.     JSSubString *parsub;
  2049.     const jschar *parstr;
  2050.     size_t parlen;
  2051.     jschar c, c2;
  2052.     uintN bit, byte, size;
  2053.  
  2054.     pcend = state->pcend;
  2055.     cpbegin = state->cpbegin;
  2056.     cpend = state->cpend;
  2057.  
  2058.     while (pc < pcend) {
  2059.     op = (REOp) *pc;
  2060.     oplen = reopsize[op];
  2061.  
  2062.     switch (op) {
  2063.       case REOP_EMPTY:
  2064.         pc += oplen;
  2065.         continue;
  2066.  
  2067.       case REOP_ALT:
  2068.         altlen = GET_JUMP_OFFSET(pc);
  2069.         pc2 = pc + oplen;
  2070.         if ((REOp)pc[altlen] != REOP_ALT) {
  2071.         pc = pc2;
  2072.         continue;
  2073.         }
  2074.         cp2 = MatchRegExp(state, pc2, cp);
  2075.         if (cp2)
  2076.         return cp2;
  2077.         pc += altlen;
  2078.         continue;
  2079.  
  2080.       case REOP_BOL:
  2081.         matched = (cp == cpbegin);
  2082.         if (state->context->regExpStatics.multiline) {
  2083.         /* Anchor-search only if RegExp.multiline is true. */
  2084.         if (state->anchoring) {
  2085.             if (!matched)
  2086.             matched = (cp[-1] == '\n');
  2087.         } else {
  2088.             state->anchoring = JS_TRUE;
  2089.             for (cp2 = cp; cp2 < cpend; cp2++) {
  2090.             if (cp2 == cpbegin || cp2[-1] == '\n') {
  2091.                 cp3 = MatchRegExp(state, pc, cp2);
  2092.                 if (cp3) {
  2093.                 state->skipped = cp2 - cp;
  2094.                 state->anchoring = JS_FALSE;
  2095.                 return cp3;
  2096.                 }
  2097.             }
  2098.             }
  2099.             state->anchoring = JS_FALSE;
  2100.         }
  2101.         }
  2102.         matchlen = 0;
  2103.         break;
  2104.  
  2105.       case REOP_EOL:
  2106.       case REOP_EOLONLY:
  2107.         matched = (cp == cpend);
  2108.         if (op == REOP_EOL || state->anchoring) {
  2109.         if (!matched && state->context->regExpStatics.multiline)
  2110.             matched = (*cp == '\n');
  2111.         } else {
  2112.         /* Always anchor-search EOLONLY, which has no BOL analogue. */
  2113.         state->anchoring = JS_TRUE;
  2114.         for (cp2 = cp; cp2 <= cpend; cp2++) {
  2115.             if (cp2 == cpend || *cp2 == '\n') {
  2116.             cp3 = MatchRegExp(state, pc, cp2);
  2117.             if (cp3) {
  2118.                 state->anchoring = JS_FALSE;
  2119.                 state->skipped = cp2 - cp;
  2120.                 return cp3;
  2121.             }
  2122.             }
  2123.         }
  2124.         state->anchoring = JS_FALSE;
  2125.         }
  2126.         matchlen = 0;
  2127.         break;
  2128.  
  2129.       case REOP_WBDRY:
  2130.         matched = (cp == cpbegin || !JS_ISWORD(cp[-1])) ^ !JS_ISWORD(*cp);
  2131.         matchlen = 0;
  2132.         break;
  2133.  
  2134.       case REOP_WNONBDRY:
  2135.         matched = (cp == cpbegin || !JS_ISWORD(cp[-1])) ^ JS_ISWORD(*cp);
  2136.         matchlen = 0;
  2137.         break;
  2138.  
  2139.       case REOP_QUANT:
  2140.         pc2 = pc;
  2141.         oplen = GET_JUMP_OFFSET(pc2);
  2142.         pc2 += 2;
  2143.         min = GET_ARGNO(pc2);
  2144.         pc2 += 2;
  2145.         max = GET_ARGNO(pc2);
  2146.         pc2 += 3;
  2147.  
  2148.         /* Reduce state->pcend so we match only the quantified regexp. */
  2149.         state->pcend = pc + oplen;
  2150.  
  2151.         /* If min is non-zero, insist on at least that many matches. */
  2152.         for (num = 0; num < min; num++) {
  2153.         cp = MatchRegExp(state, pc2, cp);
  2154.         if (!cp) {
  2155.             state->pcend = pcend;
  2156.             return NULL;
  2157.         }
  2158.         }
  2159.  
  2160.         /* Try matches from min to max, or forever if max == 0. */
  2161.         for (; !max || num < max; num++) {
  2162.         cp2 = MatchRegExp(state, pc2, cp);
  2163.         if (!cp2)
  2164.             break;
  2165.         cp = cp2;
  2166.         }
  2167.  
  2168.         /* Restore state->pcend and set match and matchlen. */
  2169.         state->pcend = pcend;
  2170.         matched = (min <= num && (!max || num <= max));
  2171.         matchlen = 0;
  2172.         break;
  2173.  
  2174.       case REOP_LPAREN:
  2175.         num = GET_ARGNO(pc);
  2176.         parsub = &state->maybeParens[num];
  2177.         parstr = parsub->chars;
  2178.         parsub->chars = cp;
  2179.         pc += oplen;
  2180.         cp3 = MatchRegExp(state, pc, cp);
  2181.         if (!cp3) {
  2182.         /* Restore so later backrefs work, unlike Perl4. */
  2183.         parsub->chars = parstr;
  2184.         return NULL;
  2185.         }
  2186.         parsub = &state->parens[num];
  2187.         if (!parsub->chars) {
  2188.         cp2 = cpbegin + state->start + state->skipped;
  2189.         if (cp < cp2) {
  2190.             parsub->chars = cp2;
  2191.             parsub->length -= cp2 - cp;
  2192.         } else {
  2193.             parsub->chars = cp;
  2194.         }
  2195.         }
  2196.         return cp3;
  2197.  
  2198.       case REOP_RPAREN:
  2199.         num = GET_ARGNO(pc);
  2200.         parsub = &state->maybeParens[num];
  2201.         parsub->length = parlen = cp - parsub->chars;
  2202.         pc += oplen;
  2203.         cp = MatchRegExp(state, pc, cp);
  2204.         if (cp) {
  2205.         parsub = &state->parens[num];
  2206.         if (!parsub->chars)
  2207.             parsub->length = parlen;
  2208.         if (num >= state->parenCount)
  2209.             state->parenCount = num + 1;
  2210.         }
  2211.         return cp;
  2212.  
  2213.       case REOP_BACKREF:
  2214.         num = (uintN)pc[1];
  2215.         parsub = &state->maybeParens[num];
  2216.         matchlen = (ptrdiff_t)parsub->length;
  2217.         matched = (cp + matchlen <= cpend &&
  2218.                !memcmp(cp, parsub->chars, matchlen * sizeof(jschar)));
  2219.         break;
  2220.  
  2221. /*
  2222.  * See java.lang.String for more on why both toupper and tolower are needed, in
  2223.  * comments for equalsIgnoreCase and regionMatches(boolean ignoreCase, ...).
  2224.  */
  2225. #define MATCH_CHARS_IGNORING_CASE(c, c2)                                      \
  2226.     ((c) == (c2) ||                                                           \
  2227.      (c = JS_TOUPPER(c)) == (c2 = JS_TOUPPER(c2)) ||                          \
  2228.      JS_TOLOWER(c) == JS_TOLOWER(c2))
  2229.  
  2230.       case REOP_BACKREFi:
  2231.         num = (uintN)pc[1];
  2232.         parsub = &state->maybeParens[num];
  2233.         matchlen = (ptrdiff_t)parsub->length;
  2234.         matched = (cp + matchlen <= cpend);
  2235.         if (matched) {
  2236.         for (i = 0; i < matchlen; i++) {
  2237.             c  = cp[i];
  2238.             c2 = parsub->chars[i];
  2239.             matched = MATCH_CHARS_IGNORING_CASE(c, c2);
  2240.             if (!matched)
  2241.             break;
  2242.         }
  2243.         }
  2244.         break;
  2245.  
  2246. #define SINGLE_CASES                                                          \
  2247.       case REOP_DOT:                                                      \
  2248.         matched = (cp != cpend && *cp != '\n');                           \
  2249.         matchlen = 1;                                                     \
  2250.         break;                                                            \
  2251.                                                                               \
  2252.       NONDOT_SINGLE_CASES                                                 \
  2253. /* END SINGLE_CASES */
  2254.  
  2255. #define NONDOT_SINGLE_CASES                                                   \
  2256.       case REOP_CCLASS:                                                   \
  2257.         /* Split ops up into statements to keep MSVC1.52 from crashing. */\
  2258.         c = *cp;                                                          \
  2259.         byte = (uintN)c >> 3;                                             \
  2260.         bit = c & 7;                                                      \
  2261.         bit = 1 << bit;                                                   \
  2262.         matched = pc[1 + byte] & bit;                                     \
  2263.         matchlen = 1;                                                     \
  2264.         break;                                                            \
  2265.                                                                               \
  2266.       case REOP_DIGIT:                                                    \
  2267.         matched = JS_ISDIGIT(*cp);                                        \
  2268.         matchlen = 1;                                                     \
  2269.         break;                                                            \
  2270.                                                                               \
  2271.       case REOP_NONDIGIT:                                                 \
  2272.         matched = !JS_ISDIGIT(*cp);                                       \
  2273.         matchlen = 1;                                                     \
  2274.         break;                                                            \
  2275.                                                                               \
  2276.       case REOP_ALNUM:                                                    \
  2277.         matched = JS_ISWORD(*cp);                                         \
  2278.         matchlen = 1;                                                     \
  2279.         break;                                                            \
  2280.                                                                               \
  2281.       case REOP_NONALNUM:                                                 \
  2282.         matched = !JS_ISWORD(*cp);                                        \
  2283.         matchlen = 1;                                                     \
  2284.         break;                                                            \
  2285.                                                                               \
  2286.       case REOP_SPACE:                                                    \
  2287.         matched = JS_ISSPACE(*cp);                                        \
  2288.         matchlen = 1;                                                     \
  2289.         break;                                                            \
  2290.                                                                               \
  2291.       case REOP_NONSPACE:                                                 \
  2292.         matched = !JS_ISSPACE(*cp);                                       \
  2293.         matchlen = 1;                                                     \
  2294.         break;                                                            \
  2295.                                                                               \
  2296.       case REOP_FLAT1:                                                    \
  2297.         c  = *cp;                                                         \
  2298.         c2 = (jschar)pc[1];                                               \
  2299.         matched = (c == c2);                                              \
  2300.         matchlen = 1;                                                     \
  2301.         break;                                                            \
  2302.                                                                               \
  2303.       case REOP_FLAT1i:                                                   \
  2304.         c  = *cp;                                                         \
  2305.         c2 = (jschar)pc[1];                                               \
  2306.         matched = MATCH_CHARS_IGNORING_CASE(c, c2);                       \
  2307.         matchlen = 1;                                                     \
  2308.         break;                                                            \
  2309.                                                                               \
  2310.       case REOP_UCFLAT1:                                                  \
  2311.         c  = *cp;                                                         \
  2312.         c2 = ((pc[1] << 8) | pc[2]);                                      \
  2313.         matched = (c == c2);                                              \
  2314.         matchlen = 1;                                                     \
  2315.         break;                                                            \
  2316.                                                                               \
  2317.       case REOP_UCFLAT1i:                                                 \
  2318.         c  = *cp;                                                         \
  2319.         c2 = ((pc[1] << 8) | pc[2]);                                      \
  2320.         matched = MATCH_CHARS_IGNORING_CASE(c, c2);                       \
  2321.         matchlen = 1;                                                     \
  2322.         break;                                                            \
  2323.                                                                               \
  2324.       case REOP_UCCLASS:                                                  \
  2325.       case REOP_NUCCLASS:                                                 \
  2326.         size = (pc[1] << 8) | pc[2];                                      \
  2327.         oplen += size;                                                    \
  2328.         c = *cp;                                                          \
  2329.         byte = (uintN)c >> 3;                                             \
  2330.         if (byte >= size) {                                               \
  2331.         matched = (op == REOP_NUCCLASS);                              \
  2332.         } else {                                                          \
  2333.         bit = c & 7;                                                  \
  2334.         bit = 1 << bit;                                               \
  2335.         matched = pc[3 + byte] & bit;                                 \
  2336.         }                                                                 \
  2337.         matchlen = 1;                                                     \
  2338.         break;                                                            \
  2339. /* END NONDOT_SINGLE_CASES */
  2340.  
  2341.       /*
  2342.        * Macro-expand single-char/single-opcode cases here and below.
  2343.        */
  2344.       SINGLE_CASES
  2345.  
  2346.       case REOP_STAR:
  2347.         op = (REOp) *++pc;
  2348.         oplen = reopsize[op];
  2349.         for (cp2 = cp; cp < cpend; cp++) {
  2350.         switch (op) {
  2351.           NONDOT_SINGLE_CASES
  2352.           default:
  2353.             PR_ASSERT(0);
  2354.         }
  2355.         if (!matched)
  2356.             break;
  2357.         }
  2358.  
  2359.       backtracker:
  2360.         pc += oplen;
  2361.         do {
  2362.         cp3 = MatchRegExp(state, pc, cp);
  2363.         if (cp3)
  2364.             return cp3;
  2365.         } while (--cp >= cp2);
  2366.         return NULL;
  2367.  
  2368.       case REOP_PLUS:
  2369.         op = (REOp) *++pc;
  2370.         oplen = reopsize[op];
  2371.         for (cp2 = cp; cp < cpend; cp++) {
  2372.         switch (op) {
  2373.           SINGLE_CASES
  2374.           default:
  2375.             PR_ASSERT(0);
  2376.         }
  2377.         if (!matched)
  2378.             break;
  2379.         }
  2380.         if (cp == cp2) {
  2381.         /* Did not match once, hope for an alternative. */
  2382.         return NULL;
  2383.         }
  2384.         /* Matched one or more times, try rest of regexp. */
  2385.         cp2++;
  2386.         goto backtracker;
  2387.  
  2388.       case REOP_OPT:
  2389.         op = (REOp) *++pc;
  2390.         oplen = reopsize[op];
  2391.         switch (op) {
  2392.           SINGLE_CASES
  2393.           default:
  2394.         PR_ASSERT(0);
  2395.         }
  2396.         pc += oplen;
  2397.         if (matched) {
  2398.         cp2 = MatchRegExp(state, pc, cp + 1);
  2399.         if (cp2)
  2400.             return cp2;
  2401.         }
  2402.         continue;
  2403.  
  2404.       case REOP_FLAT:
  2405.         matchlen = (ptrdiff_t)pc[1];
  2406.         oplen += matchlen;
  2407.         matched = (cp + matchlen <= cpend);
  2408.         if (matched) {
  2409.         pc2 = pc + 2;
  2410.         for (i = 0; i < matchlen; i++) {
  2411.             matched = (cp[i] == (jschar)pc2[i]);
  2412.             if (!matched)
  2413.             break;
  2414.         }
  2415.         }
  2416.         break;
  2417.  
  2418.       case REOP_FLATi:
  2419.         matchlen = (ptrdiff_t)pc[1];
  2420.         oplen += matchlen;
  2421.         matched = (cp + matchlen <= cpend);
  2422.         if (matched) {
  2423.         pc2 = pc + 2;
  2424.         for (i = 0; i < matchlen; i++) {
  2425.             c  = cp[i];
  2426.             c2 = (jschar)pc2[i];
  2427.             matched = MATCH_CHARS_IGNORING_CASE(c, c2);
  2428.             if (!matched)
  2429.             break;
  2430.         }
  2431.         }
  2432.         break;
  2433.  
  2434.       case REOP_UCFLAT:
  2435.         matchlen = (ptrdiff_t)pc[1];
  2436.         oplen += 2 * matchlen;
  2437.         matched = (cp + matchlen <= cpend &&
  2438.                !memcmp(cp, pc + 2, matchlen * sizeof(jschar)));
  2439.         break;
  2440.  
  2441.       case REOP_UCFLATi:
  2442.         matchlen = (ptrdiff_t)pc[1];
  2443.         oplen += matchlen;
  2444.         matched = (cp + matchlen <= cpend);
  2445.         if (matched) {
  2446.         pc2 = pc + 2;
  2447.         for (i = 0; i < matchlen; i++) {
  2448.             c  = cp[i];
  2449. #if IS_BIG_ENDIAN
  2450.             c2 = *pc2++ << 8;
  2451.             c2 |= *pc2++;
  2452. #endif
  2453. #if IS_LITTLE_ENDIAN
  2454.             c2 = *pc2++;
  2455.             c2 |= *pc2++ << 8;
  2456. #endif
  2457.             matched = MATCH_CHARS_IGNORING_CASE(c, c2);
  2458.             if (!matched)
  2459.             break;
  2460.         }
  2461.         }
  2462.         break;
  2463.  
  2464.       case REOP_JUMP:
  2465.         oplen = GET_JUMP_OFFSET(pc);
  2466.         pc += oplen;
  2467.         continue;
  2468.  
  2469.       case REOP_DOTSTAR:
  2470.         for (cp2 = cp; cp2 < cpend; cp2++)
  2471.         if (*cp2 == '\n')
  2472.             break;
  2473.         for (pc2 = pc + oplen; cp2 >= cp; cp2--) {
  2474.         cp3 = MatchRegExp(state, pc2, cp2);
  2475.         if (cp3)
  2476.             return cp3;
  2477.         }
  2478.         return NULL;
  2479.  
  2480.       case REOP_ANCHOR:
  2481.         pc2 = pc + oplen;
  2482.         if (pc2 == pcend)
  2483.         break;
  2484.         for (cp2 = cp; cp2 < cpend; cp2++) {
  2485.         cp3 = MatchRegExp(state, pc2, cp2);
  2486.         if (cp3) {
  2487.             state->skipped = cp2 - cp;
  2488.             return cp3;
  2489.         }
  2490.         }
  2491.         return NULL;
  2492.  
  2493.       case REOP_ANCHOR1:
  2494.         op = (REOp) *++pc;
  2495.         oplen = reopsize[op];
  2496.         pc2 = pc + oplen;
  2497.         PR_ASSERT(pc2 < pcend);
  2498.         for (cp2 = cp; cp < cpend; cp++) {
  2499.         switch (op) {
  2500.           NONDOT_SINGLE_CASES
  2501.           default:
  2502.             PR_ASSERT(0);
  2503.         }
  2504.         if (matched) {
  2505.             cp3 = MatchRegExp(state, pc2, cp);
  2506.             if (cp3) {
  2507.             state->skipped = cp - cp2;
  2508.             return cp3;
  2509.             }
  2510.         }
  2511.         }
  2512.         return NULL;
  2513.  
  2514. #undef MATCH_CHARS_IGNORING_CASE
  2515. #undef SINGLE_CASES
  2516. #undef NONDOT_SINGLE_CASES
  2517.  
  2518.       default:
  2519.         PR_ASSERT(0);
  2520.         return NULL;
  2521.     }
  2522.  
  2523.     if (!matched)
  2524.         return NULL;
  2525.     pc += oplen;
  2526.     if (matchlen) {
  2527.         cp += matchlen;
  2528.         if (cp > cpend)
  2529.         cp = cpend;
  2530.     }
  2531.     }
  2532.  
  2533.     return cp;
  2534. }
  2535.  
  2536. JSBool
  2537. js_ExecuteRegExp(JSContext *cx, JSRegExp *re, JSString *str, size_t *indexp,
  2538.          JSBool test, jsval *rval)
  2539. {
  2540.     size_t i, length, start;
  2541.     MatchState state;
  2542.     jsbytecode *pc;
  2543.     const jschar *cp, *ep;
  2544.     void *mark;
  2545.     JSSubString *parsub, *morepar;
  2546.     JSBool ok;
  2547.     JSRegExpStatics *res;
  2548.     ptrdiff_t matchlen;
  2549.     uintN num, morenum;
  2550.     JSString *parstr, *matchstr;
  2551.     JSObject *obj;
  2552.     JSProperty *prop;
  2553.  
  2554.     /*
  2555.      * Initialize a state struct to minimize recursive argument traffic.
  2556.      */
  2557.     state.context = cx;
  2558.     state.anchoring = JS_FALSE;
  2559.     pc = re->program;
  2560.     state.pcend = pc + re->length;
  2561.  
  2562.     /*
  2563.      * It's safe to load from cp because JSStrings have a zero at the end,
  2564.      * and we never let cp get beyond cpend.
  2565.      */
  2566.     start = *indexp;
  2567.     if (start > str->length)
  2568.     start = str->length;
  2569.     cp = str->chars + start;
  2570.     state.cpbegin = str->chars;
  2571.     state.cpend = str->chars + str->length;
  2572.     state.start = start;
  2573.     state.skipped = 0;
  2574.  
  2575.     /*
  2576.      * Use the temporary arena pool to grab space for parenthetical matches.
  2577.      * After the PR_ARENA_ALLOCATE early return on error, goto out to be sure
  2578.      * to free this memory.
  2579.      */
  2580.     length = 2 * sizeof(JSSubString) * re->parenCount;
  2581.     mark = PR_ARENA_MARK(&cx->tempPool);
  2582.     PR_ARENA_ALLOCATE(parsub, &cx->tempPool, length);
  2583.     if (!parsub) {
  2584.     JS_ReportOutOfMemory(cx);
  2585.     return JS_FALSE;
  2586.     }
  2587.     memset(parsub, 0, length);
  2588.     state.parenCount = 0;
  2589.     state.maybeParens = parsub;
  2590.     state.parens = parsub + re->parenCount;
  2591.     ok = JS_TRUE;
  2592.  
  2593.     /*
  2594.      * Call the recursive matcher to do the real work.  Return null on mismatch
  2595.      * whether testing or not.  On match, return an extended Array object.
  2596.      */
  2597.     cp = MatchRegExp(&state, pc, cp);
  2598.     if (!cp) {
  2599.     *rval = JSVAL_NULL;
  2600.     goto out;
  2601.     }
  2602.     i = cp - state.cpbegin;
  2603.     *indexp = i;
  2604.     matchlen = i - (start + state.skipped);
  2605.     ep = cp;
  2606.     cp -= matchlen;
  2607.  
  2608.     if (test) {
  2609.     /*
  2610.      * Testing for a match and updating cx->regExpStatics: don't allocate
  2611.      * an array object, do return true.
  2612.      */
  2613.     *rval = JSVAL_TRUE;
  2614.     } else {
  2615.     /*
  2616.      * The array returned on match has element 0 bound to the matched
  2617.      * string, elements 1 through state.parenCount bound to the paren
  2618.      * matches, an index property telling the length of the left context,
  2619.      * and an input property referring to the input string.
  2620.      */
  2621.     obj = JS_NewArrayObject(cx, 0, NULL);
  2622.     if (!obj) {
  2623.         ok = JS_FALSE;
  2624.         goto out;
  2625.     }
  2626.     *rval = OBJECT_TO_JSVAL(obj);
  2627.  
  2628. #define DEFVAL(val, id) {                                                     \
  2629.     if (!js_DefineProperty(cx, obj, id, val,                                  \
  2630.                JS_PropertyStub, JS_PropertyStub,                  \
  2631.                JSPROP_ENUMERATE)) {                               \
  2632.     cx->newborn[GCX_OBJECT] = NULL;                                       \
  2633.     cx->newborn[GCX_STRING] = NULL;                                       \
  2634.     ok = JS_FALSE;                                                        \
  2635.     goto out;                                                             \
  2636.     }                                                                         \
  2637. }
  2638.  
  2639.     matchstr = js_NewStringCopyN(cx, cp, matchlen, 0);
  2640.     if (!matchstr) {
  2641.         cx->newborn[GCX_OBJECT] = NULL;
  2642.         ok = JS_FALSE;
  2643.         goto out;
  2644.     }
  2645.     DEFVAL(STRING_TO_JSVAL(matchstr), INT_TO_JSVAL(0));
  2646.     }
  2647.  
  2648.     res = &cx->regExpStatics;
  2649.     PR_ASSERT(state.parenCount <= re->parenCount);
  2650.     if (state.parenCount == 0) {
  2651.     res->parenCount = 0;
  2652.     res->lastParen = js_EmptySubString;
  2653.     } else {
  2654.     for (num = 0; num < state.parenCount; num++) {
  2655.         parsub = &state.parens[num];
  2656.         if (num < 9) {
  2657.         res->parens[num] = *parsub;
  2658.         } else {
  2659.         morenum = num - 9;
  2660.         morepar = res->moreParens;
  2661.         if (!morepar) {
  2662.             res->moreLength = 10;
  2663.             morepar = JS_malloc(cx, 10 * sizeof(JSSubString));
  2664.         } else if (morenum > res->moreLength) {
  2665.             res->moreLength += 10;
  2666.             morepar = JS_realloc(cx, morepar,
  2667.                      res->moreLength * sizeof(JSSubString));
  2668.         }
  2669.         if (!morepar) {
  2670.             cx->newborn[GCX_OBJECT] = NULL;
  2671.             cx->newborn[GCX_STRING] = NULL;
  2672.             ok = JS_FALSE;
  2673.             goto out;
  2674.         }
  2675.         res->moreParens = morepar;
  2676.         morepar[morenum] = *parsub;
  2677.         }
  2678.         if (test)
  2679.         continue;
  2680.         parstr = js_NewStringCopyN(cx, parsub->chars, parsub->length, 0);
  2681.         if (!parstr) {
  2682.         cx->newborn[GCX_OBJECT] = NULL;
  2683.         cx->newborn[GCX_STRING] = NULL;
  2684.         ok = JS_FALSE;
  2685.         goto out;
  2686.         }
  2687.         prop = js_DefineProperty(cx, obj, INT_TO_JSVAL(num + 1),
  2688.                      STRING_TO_JSVAL(parstr), NULL, NULL,
  2689.                      JSPROP_ENUMERATE);
  2690.         if (!prop) {
  2691.         cx->newborn[GCX_OBJECT] = NULL;
  2692.         cx->newborn[GCX_STRING] = NULL;
  2693.         ok = JS_FALSE;
  2694.         goto out;
  2695.         }
  2696.     }
  2697.     res->parenCount = num;
  2698.     res->lastParen = *parsub;
  2699.     }
  2700.  
  2701.     if (!test) {
  2702.     /*
  2703.      * Define the index and input properties last for better for/in loop
  2704.      * order (so they come after the elements).
  2705.      */
  2706.     DEFVAL(INT_TO_JSVAL(start + state.skipped),
  2707.            (jsval)cx->runtime->atomState.indexAtom);
  2708.     DEFVAL(STRING_TO_JSVAL(str),
  2709.            (jsval)cx->runtime->atomState.inputAtom);
  2710.     }
  2711.  
  2712. #undef DEFVAL
  2713.  
  2714.     res->lastMatch.chars = cp;
  2715.     res->lastMatch.length = matchlen;
  2716.     if (cx->version == JSVERSION_1_2) {
  2717.     /*
  2718.      * JS1.2 emulated Perl4.0.1.8 (patch level 36) for global regexps used
  2719.      * in scalar contexts, and unintentionally for the string.match "list"
  2720.      * psuedo-context.  On "hi there bye", the following would result:
  2721.      *
  2722.      * Language     while(/ /g){print("$`");}   s/ /$`/g
  2723.      * perl4.036    "hi", "there"               "hihitherehi therebye"
  2724.      * perl5        "hi", "hi there"            "hihitherehi therebye"
  2725.      * js1.2        "hi", "there"               "hihitheretherebye"
  2726.      *
  2727.      * Insofar as JS1.2 always defined $` as "left context from the last
  2728.      * match" for global regexps, it was more consistent than perl4.
  2729.      */
  2730.     res->leftContext.chars = str->chars + start;
  2731.     res->leftContext.length = state.skipped;
  2732.     } else {
  2733.     /*
  2734.      * For JS1.3 and ECMAv2, emulate Perl5 exactly:
  2735.      *
  2736.      * js1.3        "hi", "hi there"            "hihitherehi therebye"
  2737.      */
  2738.     res->leftContext.chars = str->chars;
  2739.     res->leftContext.length = start + state.skipped;
  2740.     }
  2741.     res->rightContext.chars = ep;
  2742.     res->rightContext.length = state.cpend - ep;
  2743.  
  2744. out:
  2745.     PR_ARENA_RELEASE(&cx->tempPool, mark);
  2746.     return ok;
  2747. }
  2748.  
  2749. /************************************************************************/
  2750.  
  2751. enum regexp_tinyid {
  2752.     REGEXP_SOURCE       = -1,
  2753.     REGEXP_GLOBAL       = -2,
  2754.     REGEXP_IGNORE_CASE  = -3,
  2755.     REGEXP_LAST_INDEX   = -4
  2756. };
  2757.  
  2758. static JSPropertySpec regexp_props[] = {
  2759.     {"source",      REGEXP_SOURCE,      JSPROP_ENUMERATE | JSPROP_READONLY},
  2760.     {"global",      REGEXP_GLOBAL,      JSPROP_ENUMERATE | JSPROP_READONLY},
  2761.     {"ignoreCase",  REGEXP_IGNORE_CASE, JSPROP_ENUMERATE | JSPROP_READONLY},
  2762.     {"lastIndex",   REGEXP_LAST_INDEX,  JSPROP_ENUMERATE},
  2763.     {0}
  2764. };
  2765.  
  2766. static JSBool
  2767. regexp_getProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
  2768. {
  2769.     jsint slot;
  2770.     JSRegExp *re;
  2771.  
  2772.     if (!JSVAL_IS_INT(id))
  2773.     return JS_TRUE;
  2774.     slot = JSVAL_TO_INT(id);
  2775.     JS_LOCK(cx);
  2776.     re = JS_GetInstancePrivate(cx, obj, &js_RegExpClass, NULL);
  2777.     if (re) {
  2778.     switch (slot) {
  2779.       case REGEXP_SOURCE:
  2780.         *vp = STRING_TO_JSVAL(re->source);
  2781.         break;
  2782.       case REGEXP_GLOBAL:
  2783.         *vp = BOOLEAN_TO_JSVAL((re->flags & JSREG_GLOB) != 0);
  2784.         break;
  2785.       case REGEXP_IGNORE_CASE:
  2786.         *vp = BOOLEAN_TO_JSVAL((re->flags & JSREG_FOLD) != 0);
  2787.         break;
  2788.       case REGEXP_LAST_INDEX:
  2789.         *vp = INT_TO_JSVAL((jsint)re->lastIndex);
  2790.         break;
  2791.     }
  2792.     }
  2793.     JS_UNLOCK(cx);
  2794.     return JS_TRUE;
  2795. }
  2796.  
  2797. static JSBool
  2798. regexp_setProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
  2799. {
  2800.     jsint slot;
  2801.     JSRegExp *re;
  2802.     jsdouble d;
  2803.  
  2804.     if (!JSVAL_IS_INT(id))
  2805.     return JS_TRUE;
  2806.     slot = JSVAL_TO_INT(id);
  2807.     JS_LOCK(cx);
  2808.     re = JS_GetInstancePrivate(cx, obj, &js_RegExpClass, NULL);
  2809.     if (re && slot == REGEXP_LAST_INDEX) {
  2810.     if (!js_ValueToNumber(cx, *vp, &d))
  2811.         return JS_FALSE;
  2812.     re->lastIndex = (size_t)d;
  2813.     }
  2814.     JS_UNLOCK(cx);
  2815.     return JS_TRUE;
  2816. }
  2817.  
  2818. /*
  2819.  * RegExp class static properties and their Perl counterparts:
  2820.  *
  2821.  *  RegExp.input                $_
  2822.  *  RegExp.multiline            $*
  2823.  *  RegExp.lastMatch            $&
  2824.  *  RegExp.lastParen            $+
  2825.  *  RegExp.leftContext          $`
  2826.  *  RegExp.rightContext         $'
  2827.  */
  2828. enum regexp_static_tinyid {
  2829.     REGEXP_STATIC_INPUT         = -1,
  2830.     REGEXP_STATIC_MULTILINE     = -2,
  2831.     REGEXP_STATIC_LAST_MATCH    = -3,
  2832.     REGEXP_STATIC_LAST_PAREN    = -4,
  2833.     REGEXP_STATIC_LEFT_CONTEXT  = -5,
  2834.     REGEXP_STATIC_RIGHT_CONTEXT = -6
  2835. };
  2836.  
  2837. JSBool
  2838. js_InitRegExpStatics(JSContext *cx, JSRegExpStatics *res)
  2839. {
  2840.     JS_ClearRegExpStatics(cx);
  2841.     return js_AddRoot(cx, &res->input) &&
  2842.        js_AddRoot(cx, &res->execWrapper);
  2843. }
  2844.  
  2845. void
  2846. js_FreeRegExpStatics(JSContext *cx, JSRegExpStatics *res)
  2847. {
  2848.     if (res->moreParens) {
  2849.     JS_free(cx, res->moreParens);
  2850.     res->moreParens = NULL;
  2851.     }
  2852.     js_RemoveRoot(cx, &res->input);
  2853.     js_RemoveRoot(cx, &res->execWrapper);
  2854. }
  2855.  
  2856. static JSBool
  2857. regexp_static_getProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
  2858. {
  2859.     jsint slot;
  2860.     JSRegExpStatics *res;
  2861.     JSString *str;
  2862.     JSSubString *sub;
  2863.  
  2864.     res = &cx->regExpStatics;
  2865.     if (!JSVAL_IS_INT(id))
  2866.     return JS_TRUE;
  2867.     slot = JSVAL_TO_INT(id);
  2868.     switch (slot) {
  2869.       case REGEXP_STATIC_INPUT:
  2870.     *vp = res->input ? STRING_TO_JSVAL(res->input)
  2871.              : JS_GetEmptyStringValue(cx);
  2872.     return JS_TRUE;
  2873.       case REGEXP_STATIC_MULTILINE:
  2874.     *vp = BOOLEAN_TO_JSVAL(res->multiline);
  2875.     return JS_TRUE;
  2876.       case REGEXP_STATIC_LAST_MATCH:
  2877.     sub = &res->lastMatch;
  2878.     break;
  2879.       case REGEXP_STATIC_LAST_PAREN:
  2880.     sub = &res->lastParen;
  2881.     break;
  2882.       case REGEXP_STATIC_LEFT_CONTEXT:
  2883.     sub = &res->leftContext;
  2884.     break;
  2885.       case REGEXP_STATIC_RIGHT_CONTEXT:
  2886.     sub = &res->rightContext;
  2887.     break;
  2888.       default:
  2889.     sub = REGEXP_PAREN_SUBSTRING(res, slot);
  2890.     break;
  2891.     }
  2892.     str = js_NewStringCopyN(cx, sub->chars, sub->length, 0);
  2893.     if (!str)
  2894.     return JS_FALSE;
  2895.     *vp = STRING_TO_JSVAL(str);
  2896.     return JS_TRUE;
  2897. }
  2898.  
  2899. static JSBool
  2900. regexp_static_setProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
  2901. {
  2902.     JSRegExpStatics *res;
  2903.  
  2904.     if (!JSVAL_IS_INT(id))
  2905.     return JS_TRUE;
  2906.     res = &cx->regExpStatics;
  2907.     /* XXX use if-else rather than switch to keep MSVC1.52 from crashing */
  2908.     if (JSVAL_TO_INT(id) == REGEXP_STATIC_INPUT) {
  2909.     if (!JSVAL_IS_STRING(*vp) &&
  2910.         !JS_ConvertValue(cx, *vp, JSTYPE_STRING, vp)) {
  2911.         return JS_FALSE;
  2912.     }
  2913.     res->input = JSVAL_TO_STRING(*vp);
  2914.     } else if (JSVAL_TO_INT(id) == REGEXP_STATIC_MULTILINE) {
  2915.     if (!JSVAL_IS_BOOLEAN(*vp) &&
  2916.         !JS_ConvertValue(cx, *vp, JSTYPE_BOOLEAN, vp)) {
  2917.         return JS_FALSE;
  2918.     }
  2919.     res->multiline = JSVAL_TO_BOOLEAN(*vp);
  2920.     }
  2921.     return JS_TRUE;
  2922. }
  2923.  
  2924. static JSPropertySpec regexp_static_props[] = {
  2925.     {"input",
  2926.      REGEXP_STATIC_INPUT,          JSPROP_ENUMERATE,
  2927.      regexp_static_getProperty,    regexp_static_setProperty},
  2928.     {"multiline",
  2929.      REGEXP_STATIC_MULTILINE,      JSPROP_ENUMERATE,
  2930.      regexp_static_getProperty,    regexp_static_setProperty},
  2931.     {"lastMatch",
  2932.      REGEXP_STATIC_LAST_MATCH,     JSPROP_ENUMERATE|JSPROP_READONLY,
  2933.      regexp_static_getProperty,    regexp_static_getProperty},
  2934.     {"lastParen",
  2935.      REGEXP_STATIC_LAST_PAREN,     JSPROP_ENUMERATE|JSPROP_READONLY,
  2936.      regexp_static_getProperty,    regexp_static_getProperty},
  2937.     {"leftContext",
  2938.      REGEXP_STATIC_LEFT_CONTEXT,   JSPROP_ENUMERATE|JSPROP_READONLY,
  2939.      regexp_static_getProperty,    regexp_static_getProperty},
  2940.     {"rightContext",
  2941.      REGEXP_STATIC_RIGHT_CONTEXT,  JSPROP_ENUMERATE|JSPROP_READONLY,
  2942.      regexp_static_getProperty,    regexp_static_getProperty},
  2943.  
  2944.     /* XXX should have block scope and local $1, etc. */
  2945.     {"$1", 0, JSPROP_ENUMERATE|JSPROP_READONLY,
  2946.      regexp_static_getProperty,    regexp_static_getProperty},
  2947.     {"$2", 1, JSPROP_ENUMERATE|JSPROP_READONLY,
  2948.      regexp_static_getProperty,    regexp_static_getProperty},
  2949.     {"$3", 2, JSPROP_ENUMERATE|JSPROP_READONLY,
  2950.      regexp_static_getProperty,    regexp_static_getProperty},
  2951.     {"$4", 3, JSPROP_ENUMERATE|JSPROP_READONLY,
  2952.      regexp_static_getProperty,    regexp_static_getProperty},
  2953.     {"$5", 4, JSPROP_ENUMERATE|JSPROP_READONLY,
  2954.      regexp_static_getProperty,    regexp_static_getProperty},
  2955.     {"$6", 5, JSPROP_ENUMERATE|JSPROP_READONLY,
  2956.      regexp_static_getProperty,    regexp_static_getProperty},
  2957.     {"$7", 6, JSPROP_ENUMERATE|JSPROP_READONLY,
  2958.      regexp_static_getProperty,    regexp_static_getProperty},
  2959.     {"$8", 7, JSPROP_ENUMERATE|JSPROP_READONLY,
  2960.      regexp_static_getProperty,    regexp_static_getProperty},
  2961.     {"$9", 8, JSPROP_ENUMERATE|JSPROP_READONLY,
  2962.      regexp_static_getProperty,    regexp_static_getProperty},
  2963.  
  2964.     {0}
  2965. };
  2966.  
  2967. static JSBool
  2968. regexp_convert(JSContext *cx, JSObject *obj, JSType type, jsval *vp)
  2969. {
  2970.     if (type == JSTYPE_FUNCTION) {
  2971.     cx->regExpStatics.execObject = obj;
  2972.     *vp = OBJECT_TO_JSVAL(cx->regExpStatics.execWrapper);
  2973.     }
  2974.     return JS_TRUE;
  2975. }
  2976.  
  2977. static void
  2978. regexp_finalize(JSContext *cx, JSObject *obj)
  2979. {
  2980.     JSRegExp *re;
  2981.  
  2982.     re = JS_GetPrivate(cx, obj);
  2983.     if (!re)
  2984.     return;
  2985.     js_DestroyRegExp(cx, re);
  2986. }
  2987.  
  2988. JSClass js_RegExpClass = {
  2989.     "RegExp",
  2990.     JSCLASS_HAS_PRIVATE,
  2991.     JS_PropertyStub,  JS_PropertyStub,  regexp_getProperty, regexp_setProperty,
  2992.     JS_EnumerateStub, JS_ResolveStub,   regexp_convert,     regexp_finalize
  2993. };
  2994.  
  2995. static JSBool
  2996. regexp_toString(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
  2997.             jsval *rval)
  2998. {
  2999.     JSBool ok;
  3000.     JSRegExp *re;
  3001.     jschar *chars;
  3002.     size_t length, nflags;
  3003.     uintN flags;
  3004.     JSString *str;
  3005.  
  3006.     ok = JS_FALSE;
  3007.     JS_LOCK(cx);
  3008.     re = JS_GetInstancePrivate(cx, obj, &js_RegExpClass, argv);
  3009.     if (!re)
  3010.     goto out;
  3011.  
  3012.     length = re->source->length + 2;
  3013.     nflags = 0;
  3014.     for (flags = re->flags; flags != 0; flags &= flags - 1)
  3015.     nflags++;
  3016.     chars = JS_malloc(cx, (length + nflags + 1) * sizeof(jschar));
  3017.     if (!chars)
  3018.     goto out;
  3019.  
  3020.     chars[0] = '/';
  3021.     js_strncpy(&chars[1], re->source->chars, length - 2);
  3022.     chars[length-1] = '/';
  3023.     if (nflags) {
  3024.     if (re->flags & JSREG_GLOB)
  3025.         chars[length++] = 'g';
  3026.     if (re->flags & JSREG_FOLD)
  3027.         chars[length++] = 'i';
  3028.     }
  3029.     chars[length] = 0;
  3030.  
  3031.     str = js_NewString(cx, chars, length, 0);
  3032.     if (!str) {
  3033.     JS_free(cx, chars);
  3034.     goto out;
  3035.     }
  3036.     *rval = STRING_TO_JSVAL(str);
  3037.     ok = JS_TRUE;
  3038. out:
  3039.     JS_UNLOCK(cx);
  3040.     return ok;
  3041. }
  3042.  
  3043. static JSBool
  3044. regexp_compile(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
  3045.            jsval *rval)
  3046. {
  3047.     JSBool ok;
  3048.     JSRegExp *re, *nre;
  3049.     JSString *opt, *str;
  3050.  
  3051.     ok = JS_FALSE;
  3052.     JS_LOCK(cx);
  3053.     if (!JS_InstanceOf(cx, obj, &js_RegExpClass, argv))
  3054.     goto out;
  3055.     re = JS_GetPrivate(cx, obj);
  3056.     opt = NULL;
  3057.     if (argc == 0) {
  3058.     str = cx->runtime->emptyString;
  3059.     } else {
  3060.     str = js_ValueToString(cx, argv[0]);
  3061.     if (!str)
  3062.         goto out;
  3063.     argv[0] = STRING_TO_JSVAL(str);
  3064.     if (argc > 1) {
  3065.         opt = js_ValueToString(cx, argv[1]);
  3066.         if (!opt)
  3067.         goto out;
  3068.         argv[1] = STRING_TO_JSVAL(opt);
  3069.     }
  3070.     }
  3071.     nre = js_NewRegExpOpt(cx, str, opt);
  3072.     if (!nre)
  3073.     goto out;
  3074.     if (!JS_SetPrivate(cx, obj, nre)) {
  3075.     js_DestroyRegExp(cx, nre);
  3076.     goto out;
  3077.     }
  3078.     if (re)
  3079.     js_DestroyRegExp(cx, re);
  3080.     *rval = OBJECT_TO_JSVAL(obj);
  3081.     ok = JS_TRUE;
  3082. out:
  3083.     JS_UNLOCK(cx);
  3084.     return ok;
  3085. }
  3086.  
  3087. static JSBool
  3088. regexp_exec_sub(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
  3089.         JSBool test, jsval *rval)
  3090. {
  3091.     JSBool ok, locked;
  3092.     JSRegExp *re;
  3093.     JSString *str;
  3094.     size_t i;
  3095.  
  3096.     ok = locked = JS_FALSE;
  3097.     re = JS_GetInstancePrivate(cx, obj, &js_RegExpClass, argv);
  3098.     if (!re)
  3099.         goto out;
  3100.     if (argc == 0) {
  3101.     str = cx->regExpStatics.input;
  3102.     if (!str) {
  3103.         JS_ReportError(cx, "no input for /%s/%s%s",
  3104.                JS_GetStringBytes(re->source),
  3105.                (re->flags & JSREG_GLOB) ? "g" : "",
  3106.                (re->flags & JSREG_FOLD) ? "i" : "");
  3107.         goto out;
  3108.     }
  3109.     } else {
  3110.     str = js_ValueToString(cx, argv[0]);
  3111.     if (!str)
  3112.         goto out;
  3113.     argv[0] = STRING_TO_JSVAL(str);
  3114.     }
  3115.     if (re->flags & JSREG_GLOB) {
  3116.     JS_LOCK(cx);
  3117.     locked = JS_TRUE;
  3118.     i = re->lastIndex;
  3119.     } else {
  3120.     i = 0;
  3121.     }
  3122.     ok = js_ExecuteRegExp(cx, re, str, &i, test, rval);
  3123.     if (re->flags & JSREG_GLOB)
  3124.     re->lastIndex = (*rval == JSVAL_NULL) ? 0 : i;
  3125. out:
  3126.     if (locked)
  3127.     JS_UNLOCK(cx);
  3128.     return ok;
  3129. }
  3130.  
  3131. static JSBool
  3132. regexp_exec(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
  3133. {
  3134.     return regexp_exec_sub(cx, obj, argc, argv, JS_FALSE, rval);
  3135. }
  3136.  
  3137. static JSBool
  3138. regexp_test(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
  3139. {
  3140.     if (!regexp_exec_sub(cx, obj, argc, argv, JS_TRUE, rval))
  3141.     return JS_FALSE;
  3142.     if (*rval != JSVAL_TRUE)
  3143.     *rval = JSVAL_FALSE;
  3144.     return JS_TRUE;
  3145. }
  3146.  
  3147. static JSBool
  3148. regexp_execWrapper(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
  3149.            jsval *rval)
  3150. {
  3151.     JSBool ok;
  3152.  
  3153.     ok = regexp_exec(cx, cx->regExpStatics.execObject, argc, argv, rval);
  3154.     cx->regExpStatics.execObject = NULL;
  3155.     return ok;
  3156. }
  3157.  
  3158. static JSFunctionSpec regexp_methods[] = {
  3159.     {js_toString_str,   regexp_toString,        0},
  3160.     {"compile",         regexp_compile,         1},
  3161.     {"exec",            regexp_exec,            0},
  3162.     {"test",            regexp_test,            0},
  3163.     {0}
  3164. };
  3165.  
  3166. JSObject *
  3167. js_InitRegExpClass(JSContext *cx, JSObject *obj)
  3168. {
  3169.     JSFunction *fun;
  3170.     JSObject *proto, *ctor;
  3171.  
  3172.     fun = JS_NewFunction(cx, regexp_execWrapper, 0, 0, NULL, "execWrapper");
  3173.     if (!fun)
  3174.     return NULL;
  3175.     cx->regExpStatics.execWrapper = fun->object;
  3176.  
  3177.     proto = JS_InitClass(cx, obj, NULL, &js_RegExpClass, regexp_compile, 1,
  3178.              regexp_props, regexp_methods,
  3179.              regexp_static_props, NULL);
  3180.  
  3181.     if (!proto || !(ctor = JS_GetConstructor(cx, proto)))
  3182.     return NULL;
  3183.     if (!JS_AliasProperty(cx, ctor, "input",        "$_") ||
  3184.     !JS_AliasProperty(cx, ctor, "multiline",    "$*") ||
  3185.     !JS_AliasProperty(cx, ctor, "lastMatch",    "$&") ||
  3186.     !JS_AliasProperty(cx, ctor, "lastParen",    "$+") ||
  3187.     !JS_AliasProperty(cx, ctor, "leftContext",  "$`") ||
  3188.     !JS_AliasProperty(cx, ctor, "rightContext", "$'")) {
  3189.     goto bad;
  3190.     }
  3191.     return proto;
  3192.  
  3193. bad:
  3194.     JS_DeleteProperty(cx, obj, js_RegExpClass.name);
  3195.     return NULL;
  3196. }
  3197.  
  3198. JSObject *
  3199. js_NewRegExpObject(JSContext *cx, jschar *chars, size_t length, uintN flags)
  3200. {
  3201.     JSString *str;
  3202.     JSObject *obj;
  3203.     JSRegExp *re;
  3204.  
  3205.     str = js_NewStringCopyN(cx, chars, length, 0);
  3206.     if (!str)
  3207.     return NULL;
  3208.     re = js_NewRegExp(cx, str, flags);
  3209.     if (!re)
  3210.     return NULL;
  3211.     obj = js_NewObject(cx, &js_RegExpClass, NULL, NULL);
  3212.     if (!obj || !JS_SetPrivate(cx, obj, re)) {
  3213.     js_DestroyRegExp(cx, re);
  3214.     return NULL;
  3215.     }
  3216.     return obj;
  3217. }
  3218.  
  3219. #endif /* JS_HAS_REGEXPS */
  3220.