src/org/mozilla/javascript/regexp/NativeRegExp.java

   1 /* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-\r
   2  *\r
   3  * The contents of this file are subject to the Netscape Public\r
   4  * License Version 1.1 (the "License"); you may not use this file\r
   5  * except in compliance with the License. You may obtain a copy of\r
   6  * the License at http://www.mozilla.org/NPL/\r
   7  *\r
   8  * Software distributed under the License is distributed on an "AS\r
   9  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr\r
  10  * implied. See the License for the specific language governing\r
  11  * rights and limitations under the License.\r
  12  *\r
  13  * The Original Code is Rhino code, released\r
  14  * May 6, 1998.\r
  15  *\r
  16  * The Initial Developer of the Original Code is Netscape\r
  17  * Communications Corporation.  Portions created by Netscape are\r
  18  * Copyright (C) 1997-1999 Netscape Communications Corporation. All\r
  19  * Rights Reserved.\r
  20  *\r
  21  * Contributor(s): \r
  22  * Norris Boyd\r
  23  * Brendan Eich\r
  24  * Matthias Radestock\r
  25  *\r
  26  * Alternatively, the contents of this file may be used under the\r
  27  * terms of the GNU Public License (the "GPL"), in which case the\r
  28  * provisions of the GPL are applicable instead of those above.\r
  29  * If you wish to allow use of your version of this file only\r
  30  * under the terms of the GPL and not to allow others to use your\r
  31  * version of this file under the NPL, indicate your decision by\r
  32  * deleting the provisions above and replace them with the notice\r
  33  * and other provisions required by the GPL.  If you do not delete\r
  34  * the provisions above, a recipient may use your version of this\r
  35  * file under either the NPL or the GPL.\r
  36  */\r
  37 \r
  38 package org.mozilla.javascript.regexp;\r
  39 \r
  40 import org.mozilla.javascript.*;\r
  41 import java.lang.reflect.Method;\r
  42 \r
  43 /**\r
  44  * This class implements the RegExp native object.\r
  45  *\r
  46  * Revision History:\r
  47  * Implementation in C by Brendan Eich\r
  48  * Initial port to Java by Norris Boyd from jsregexp.c version 1.36\r
  49  * Merged up to version 1.38, which included Unicode support.\r
  50  * Merged bug fixes in version 1.39.\r
  51  * Merged JSFUN13_BRANCH changes up to 1.32.2.13\r
  52  *\r
  53  * @author Brendan Eich\r
  54  * @author Norris Boyd\r
  55  */\r
  56 public class NativeRegExp extends IdScriptable implements Function {\r
  57 \r
  58     public static final int GLOB = 0x1;       // 'g' flag: global\r
  59     public static final int FOLD = 0x2;       // 'i' flag: fold\r
  60     public static final int MULTILINE = 0x4;  // 'm' flag: multiline\r
  61 \r
  62     //type of match to perform\r
  63     public static final int TEST = 0;\r
  64     public static final int MATCH = 1;\r
  65     public static final int PREFIX = 2;\r
  66 \r
  67     private static final boolean debug = false;\r
  68 \r
  69     public static void init(Context cx, Scriptable scope, boolean sealed) {\r
  70         \r
  71         NativeRegExp proto = new NativeRegExp();\r
  72         proto.prototypeFlag = true;\r
  73         proto.activateIdMap(MAX_PROTOTYPE_ID);\r
  74         proto.setSealFunctionsFlag(sealed);\r
  75         proto.setFunctionParametrs(cx);\r
  76         proto.setParentScope(scope);\r
  77         proto.setPrototype(getObjectPrototype(scope));\r
  78 \r
  79 \r
  80         NativeRegExpCtor ctor = new NativeRegExpCtor();\r
  81 \r
  82         ctor.setPrototype(getClassPrototype(scope, "Function"));\r
  83         ctor.setParentScope(scope);\r
  84 \r
  85         ctor.setImmunePrototypeProperty(proto);\r
  86         \r
  87         if (sealed) {\r
  88             proto.sealObject();\r
  89             ctor.sealObject();\r
  90         }\r
  91 \r
  92         defineProperty(scope, "RegExp", ctor, ScriptableObject.DONTENUM);\r
  93     }\r
  94 \r
  95     public NativeRegExp(Context cx, Scriptable scope, String source, \r
  96                         String global, boolean flat) {\r
  97         init(cx, scope, source, global, flat);\r
  98     }\r
  99 \r
 100     public void init(Context cx, Scriptable scope, String source, \r
 101                      String global, boolean flat) {\r
 102         this.source = source;\r
 103         flags = 0;\r
 104         if (global != null) {\r
 105             for (int i=0; i < global.length(); i++) {\r
 106                 char c = global.charAt(i);\r
 107                 if (c == 'g') {\r
 108                     flags |= GLOB;\r
 109                 } else if (c == 'i') {\r
 110                     flags |= FOLD;\r
 111                 } else if (c == 'm') {\r
 112                     flags |= MULTILINE;\r
 113                 } else {\r
 114                     Object[] errArgs = { new Character(c) };\r
 115                     throw NativeGlobal.constructError(cx, "SyntaxError",\r
 116                                                       ScriptRuntime.getMessage(\r
 117                                                                                "msg.invalid.re.flag", errArgs),\r
 118                                                       scope);\r
 119                 }\r
 120             }\r
 121         }\r
 122 \r
 123         CompilerState state = new CompilerState(source, flags, cx, scope);\r
 124         if (flat) {\r
 125             ren = null;\r
 126             int sourceLen = source.length();\r
 127             int index = 0;\r
 128             while (sourceLen > 0) {\r
 129                 int len = sourceLen;\r
 130                 if (len > REOP_FLATLEN_MAX) {\r
 131                     len = REOP_FLATLEN_MAX;\r
 132                 }\r
 133                 RENode ren2 = new RENode(state, len == 1 ? REOP_FLAT1 : REOP_FLAT,\r
 134                                          new Integer(index));                                 \r
 135                 ren2.flags = RENode.NONEMPTY;\r
 136                 if (len > 1) {\r
 137                     ren2.kid2 = index + len;\r
 138                 } else {\r
 139                     ren2.flags |= RENode.SINGLE;\r
 140                     ren2.chr = state.source[index];                    \r
 141                 }\r
 142                 index += len;\r
 143                 sourceLen -= len;\r
 144                 if (ren == null)\r
 145                     ren = ren2;\r
 146                 else\r
 147                     setNext(state, ren, ren2);\r
 148             }\r
 149         }\r
 150         else\r
 151             this.ren = parseRegExp(state);\r
 152         if (ren == null) return;\r
 153         RENode end = new RENode(state, REOP_END, null);\r
 154         setNext(state, ren, end);\r
 155         if (debug)\r
 156             dumpRegExp(state, ren);\r
 157         this.lastIndex = 0;\r
 158         this.parenCount = state.parenCount;\r
 159         this.flags = flags;\r
 160 \r
 161         scope = org.xwt.util.JSObject.defaultObjects;\r
 162         setPrototype(getClassPrototype(scope, "RegExp"));\r
 163         setParentScope(scope);\r
 164     }\r
 165 \r
 166     public String getClassName() {\r
 167         return "RegExp";\r
 168     }\r
 169 \r
 170     public Object call(Context cx, Scriptable scope, Scriptable thisObj,\r
 171                        Object[] args) {\r
 172         return execSub(cx, scope, args, MATCH);\r
 173     }\r
 174 \r
 175     public Scriptable construct(Context cx, Scriptable scope, Object[] args) {\r
 176         return (Scriptable) call(cx, scope, null, args);\r
 177     }\r
 178 \r
 179     Scriptable compile(Context cx, Scriptable scope, Object[] args) {\r
 180         if (args.length > 0 && args[0] instanceof NativeRegExp) {\r
 181             if (args.length > 1 && args[1] != Undefined.instance) {\r
 182                 // report error\r
 183                 throw NativeGlobal.constructError(\r
 184                                                   cx, "TypeError",\r
 185                                                   "only one argument may be specified " +\r
 186                                                   "if the first argument is a RegExp object",\r
 187                                                   scope);\r
 188             }\r
 189             NativeRegExp thatObj = (NativeRegExp) args[0];\r
 190             source = thatObj.source; \r
 191             lastIndex = thatObj.lastIndex;\r
 192             parenCount = thatObj.parenCount;\r
 193             flags = thatObj.flags;\r
 194             program = thatObj.program;\r
 195             ren = thatObj.ren;\r
 196             return this;\r
 197         }\r
 198         String s = args.length == 0 ? "" : ScriptRuntime.toString(args[0]);\r
 199         String global = args.length > 1 && args[1] != Undefined.instance\r
 200             ? ScriptRuntime.toString(args[1])\r
 201             : null;\r
 202         init(cx, scope, s, global, false);\r
 203         return this;\r
 204     }\r
 205 \r
 206     public String toString() {\r
 207         StringBuffer buf = new StringBuffer();\r
 208         buf.append('/');\r
 209         buf.append(source);\r
 210         buf.append('/');\r
 211         if ((flags & GLOB) != 0)\r
 212             buf.append('g');\r
 213         if ((flags & FOLD) != 0)\r
 214             buf.append('i');\r
 215         if ((flags & MULTILINE) != 0)\r
 216             buf.append('m');\r
 217         return buf.toString();\r
 218     }\r
 219 \r
 220     public NativeRegExp() {\r
 221     }\r
 222     \r
 223     private static RegExpImpl getImpl(Context cx) {\r
 224         return (RegExpImpl) ScriptRuntime.getRegExpProxy(cx);\r
 225     }\r
 226 \r
 227     private Object execSub(Context cx, Scriptable scopeObj,\r
 228                            Object[] args, int matchType)\r
 229     {\r
 230         RegExpImpl reImpl = getImpl(cx);\r
 231         String str;\r
 232         if (args.length == 0) {\r
 233             str = reImpl.input;\r
 234             if (str == null) {\r
 235                 Object[] errArgs = { toString() };\r
 236                 throw NativeGlobal.constructError(\r
 237                                                   cx, "SyntaxError",\r
 238                                                   ScriptRuntime.getMessage\r
 239                                                   ("msg.no.re.input.for", errArgs),\r
 240                                                   scopeObj);\r
 241             }\r
 242         } else {\r
 243             str = ScriptRuntime.toString(args[0]);\r
 244         }\r
 245         int i = ((flags & GLOB) != 0) ? lastIndex : 0;\r
 246         int indexp[] = { i };\r
 247         Object rval = executeRegExp(cx, scopeObj, \r
 248                                     reImpl, str, indexp, matchType);\r
 249         if ((flags & GLOB) != 0) {\r
 250             lastIndex = (rval == null || rval == Undefined.instance) \r
 251                         ? 0 : indexp[0];\r
 252         }\r
 253         return rval;\r
 254     }\r
 255 \r
 256     private Object exec(Context cx, Scriptable scopeObj, Object[] args) {\r
 257         return execSub(cx, scopeObj, args, MATCH);\r
 258     }\r
 259 \r
 260     private Object test(Context cx, Scriptable scopeObj, Object[] args) {\r
 261         Object rval = execSub(cx, scopeObj, args, TEST);\r
 262         if (rval == null || !rval.equals(Boolean.TRUE))\r
 263             rval = Boolean.FALSE;\r
 264         return rval;\r
 265     }\r
 266 \r
 267     private Object prefix(Context cx, Scriptable scopeObj, Object[] args) {\r
 268         return execSub(cx, scopeObj, args, PREFIX);\r
 269     }\r
 270 \r
 271     static final int JS_BITS_PER_BYTE = 8;\r
 272 \r
 273     private static final byte REOP_EMPTY      = 0;  /* match rest of input against rest of r.e. */\r
 274     private static final byte REOP_ALT        = 1;  /* alternative subexpressions in kid and next */\r
 275     private static final byte REOP_BOL        = 2;  /* beginning of input (or line if multiline) */\r
 276     private static final byte REOP_EOL        = 3;  /* end of input (or line if multiline) */\r
 277     private static final byte REOP_WBDRY      = 4;  /* match "" at word boundary */\r
 278     private static final byte REOP_WNONBDRY   = 5;  /* match "" at word non-boundary */\r
 279     private static final byte REOP_QUANT      = 6;  /* quantified atom: atom{1,2} */\r
 280     private static final byte REOP_STAR       = 7;  /* zero or more occurrences of kid */\r
 281     private static final byte REOP_PLUS       = 8;  /* one or more occurrences of kid */\r
 282     private static final byte REOP_OPT        = 9;  /* optional subexpression in kid */\r
 283     private static final byte REOP_LPAREN     = 10; /* left paren bytecode: kid is u.num'th sub-regexp */\r
 284     private static final byte REOP_RPAREN     = 11; /* right paren bytecode */\r
 285     private static final byte REOP_DOT        = 12; /* stands for any character */\r
 286     private static final byte REOP_CCLASS     = 13; /* character class: [a-f] */\r
 287     private static final byte REOP_DIGIT      = 14; /* match a digit char: [0-9] */\r
 288     private static final byte REOP_NONDIGIT   = 15; /* match a non-digit char: [^0-9] */\r
 289     private static final byte REOP_ALNUM      = 16; /* match an alphanumeric char: [0-9a-z_A-Z] */\r
 290     private static final byte REOP_NONALNUM   = 17; /* match a non-alphanumeric char: [^0-9a-z_A-Z] */\r
 291     private static final byte REOP_SPACE      = 18; /* match a whitespace char */\r
 292     private static final byte REOP_NONSPACE   = 19; /* match a non-whitespace char */\r
 293     private static final byte REOP_BACKREF    = 20; /* back-reference (e.g., \1) to a parenthetical */\r
 294     private static final byte REOP_FLAT       = 21; /* match a flat string */\r
 295     private static final byte REOP_FLAT1      = 22; /* match a single char */\r
 296     private static final byte REOP_JUMP       = 23; /* for deoptimized closure loops */\r
 297     private static final byte REOP_DOTSTAR    = 24; /* optimize .* to use a single opcode */\r
 298     private static final byte REOP_ANCHOR     = 25; /* like .* but skips left context to unanchored r.e. */\r
 299     private static final byte REOP_EOLONLY    = 26; /* $ not preceded by any pattern */\r
 300     private static final byte REOP_UCFLAT     = 27; /* flat Unicode string; len immediate counts chars */\r
 301     private static final byte REOP_UCFLAT1    = 28; /* single Unicode char */\r
 302     private static final byte REOP_UCCLASS    = 29; /* Unicode character class, vector of chars to match */\r
 303     private static final byte REOP_NUCCLASS   = 30; /* negated Unicode character class */\r
 304     private static final byte REOP_BACKREFi   = 31; /* case-independent REOP_BACKREF */\r
 305     private static final byte REOP_FLATi      = 32; /* case-independent REOP_FLAT */\r
 306     private static final byte REOP_FLAT1i     = 33; /* case-independent REOP_FLAT1 */\r
 307     private static final byte REOP_UCFLATi    = 34; /* case-independent REOP_UCFLAT */\r
 308     private static final byte REOP_UCFLAT1i   = 35; /* case-independent REOP_UCFLAT1 */\r
 309     private static final byte REOP_ANCHOR1    = 36; /* first-char discriminating REOP_ANCHOR */\r
 310     private static final byte REOP_NCCLASS    = 37; /* negated 8-bit character class */\r
 311     private static final byte REOP_DOTSTARMIN = 38; /* ungreedy version of REOP_DOTSTAR */\r
 312     private static final byte REOP_LPARENNON  = 39; /* non-capturing version of REOP_LPAREN */\r
 313     private static final byte REOP_RPARENNON  = 40; /* non-capturing version of REOP_RPAREN */\r
 314     private static final byte REOP_ASSERT     = 41; /* zero width positive lookahead assertion */\r
 315     private static final byte REOP_ASSERT_NOT = 42; /* zero width negative lookahead assertion */\r
 316     private static final byte REOP_END        = 43;\r
 317 \r
 318     /* maximum length of FLAT string */\r
 319     private static final int REOP_FLATLEN_MAX = 255;\r
 320 \r
 321     /* not thread safe, used only for debugging */\r
 322     private static int level;\r
 323 \r
 324     private static String[] reopname = null;\r
 325     static {\r
 326         if (debug) {\r
 327             String a[] = {\r
 328                 "empty",\r
 329                 "alt",\r
 330                 "bol",\r
 331                 "eol",\r
 332                 "wbdry",\r
 333                 "wnonbdry",\r
 334                 "quant",\r
 335                 "star",\r
 336                 "plus",\r
 337                 "opt",\r
 338                 "lparen",\r
 339                 "rparen",\r
 340                 "dot",\r
 341                 "cclass",\r
 342                 "digit",\r
 343                 "nondigit",\r
 344                 "alnum",\r
 345                 "nonalnum",\r
 346                 "space",\r
 347                 "nonspace",\r
 348                 "backref",\r
 349                 "flat",\r
 350                 "flat1",\r
 351                 "jump",\r
 352                 "dotstar",\r
 353                 "anchor",\r
 354                 "eolonly",\r
 355                 "ucflat",\r
 356                 "ucflat1",\r
 357                 "ucclass",\r
 358                 "nucclass",\r
 359                 "backrefi",\r
 360                 "flati",\r
 361                 "flat1i",\r
 362                 "ucflati",\r
 363                 "ucflat1i",\r
 364                 "anchor1",\r
 365                 "ncclass",\r
 366                 "dotstar_min",\r
 367                 "lparen_non",\r
 368                 "rparen_non",\r
 369                 "end"\r
 370             };\r
 371             reopname = a;\r
 372         }\r
 373     }\r
 374 \r
 375     private String getPrintableString(String str) {\r
 376         if (debug) {\r
 377             StringBuffer buf = new StringBuffer(str.length());\r
 378             for (int i = 0; i < str.length(); i++) {\r
 379                 int c = str.charAt(i);\r
 380                 if ((c < 0x20) || (c > 0x7F)) {\r
 381                     if (c == '\n')\r
 382                         buf.append("\\n");\r
 383                     else\r
 384                         buf.append("\\u" + Integer.toHexString(c));\r
 385                 }\r
 386                 else\r
 387                     buf.append((char)c);\r
 388             }\r
 389             return buf.toString();\r
 390         } else {\r
 391             return "";\r
 392         }\r
 393     }\r
 394 \r
 395     private void dumpRegExp(CompilerState state, RENode ren) {\r
 396         if (debug) {\r
 397             if (level == 0)\r
 398                 System.out.print("level offset  flags  description\n");\r
 399             level++;\r
 400             do {\r
 401                 char[] source = ren.s != null ? ren.s : state.source;\r
 402                 System.out.print(level);\r
 403                 System.out.print(" ");\r
 404                 System.out.print(ren.offset);\r
 405                 System.out.print(" " +\r
 406                                  ((ren.flags & RENode.ANCHORED) != 0 ? "A" : "-") +\r
 407                                  ((ren.flags & RENode.SINGLE)   != 0 ? "S" : "-") +\r
 408                                  ((ren.flags & RENode.NONEMPTY) != 0 ? "F" : "-") + // F for full\r
 409                                  ((ren.flags & RENode.ISNEXT)   != 0 ? "N" : "-") + // N for next\r
 410                                  ((ren.flags & RENode.GOODNEXT) != 0 ? "G" : "-") +\r
 411                                  ((ren.flags & RENode.ISJOIN)   != 0 ? "J" : "-") +\r
 412                                  ((ren.flags & RENode.MINIMAL)  != 0 ? "M" : "-") +\r
 413                                  "  " +\r
 414                                  reopname[ren.op]);\r
 415 \r
 416                 switch (ren.op) {\r
 417                 case REOP_ALT:\r
 418                     System.out.print(" ");\r
 419                     System.out.println(ren.next.offset);\r
 420                     dumpRegExp(state, (RENode) ren.kid);\r
 421                     break;\r
 422 \r
 423                 case REOP_STAR:\r
 424                 case REOP_PLUS:\r
 425                 case REOP_OPT:\r
 426                 case REOP_ANCHOR1:\r
 427                 case REOP_ASSERT:\r
 428                 case REOP_ASSERT_NOT:\r
 429                     System.out.println();\r
 430                     dumpRegExp(state, (RENode) ren.kid);\r
 431                     break;\r
 432 \r
 433                 case REOP_QUANT:\r
 434                     System.out.print(" next ");\r
 435                     System.out.print(ren.next.offset);\r
 436                     System.out.print(" min ");\r
 437                     System.out.print(ren.min);\r
 438                     System.out.print(" max ");\r
 439                     System.out.println(ren.max);\r
 440                     dumpRegExp(state, (RENode) ren.kid);\r
 441                     break;\r
 442 \r
 443                 case REOP_LPAREN:\r
 444                     System.out.print(" num ");\r
 445                     System.out.println(ren.num);\r
 446                     dumpRegExp(state, (RENode) ren.kid);\r
 447                     break;\r
 448 \r
 449                 case REOP_LPARENNON:\r
 450                     System.out.println();\r
 451                     dumpRegExp(state, (RENode) ren.kid);\r
 452                     break;\r
 453 \r
 454                 case REOP_BACKREF:\r
 455                 case REOP_RPAREN:\r
 456                     System.out.print(" num ");\r
 457                     System.out.println(ren.num);\r
 458                     break;\r
 459 \r
 460                 case REOP_CCLASS: {\r
 461                     int index = ((Integer) ren.kid).intValue();\r
 462                     int index2 = ren.kid2;\r
 463                     int len = index2 - index;\r
 464                     System.out.print(" [");\r
 465                     System.out.print(getPrintableString(new String(source, index, len)));\r
 466                     System.out.println("]");\r
 467                     break;\r
 468                     }\r
 469 \r
 470                 case REOP_FLAT: {\r
 471                     int index = ((Integer) ren.kid).intValue();\r
 472                     int index2 = ren.kid2;\r
 473                     int len = index2 - index;\r
 474                     System.out.print(" ");\r
 475                     System.out.print(getPrintableString(new String(source, index, len)));\r
 476                     System.out.print(" (");\r
 477                     System.out.print(len);\r
 478                     System.out.println(")");\r
 479                     break;\r
 480                     }\r
 481 \r
 482                 case REOP_FLAT1:\r
 483                     System.out.print(" ");\r
 484                     System.out.print(ren.chr);\r
 485                     System.out.print(" ('\\");\r
 486                     System.out.print(Integer.toString(ren.chr, 8));\r
 487                     System.out.println("')");\r
 488                     break;\r
 489 \r
 490                 case REOP_JUMP:\r
 491                     System.out.print(" ");\r
 492                     System.out.println(ren.next.offset);\r
 493                     break;\r
 494 \r
 495                 case REOP_UCFLAT: {\r
 496                     int index = ((Integer) ren.kid).intValue();\r
 497                     int len = ren.kid2 - index;\r
 498                     for (int i = 0; i < len; i++)\r
 499                         System.out.print("\\u" + \r
 500                                          Integer.toHexString(source[index+i]));\r
 501                     System.out.println();\r
 502                     break;\r
 503                     }\r
 504 \r
 505                 case REOP_UCFLAT1:\r
 506                     System.out.print("\\u" + \r
 507                                      Integer.toHexString(ren.chr));\r
 508                     System.out.println();\r
 509                     break;\r
 510 \r
 511                 case REOP_UCCLASS: {\r
 512                     int index = ((Integer) ren.kid).intValue();\r
 513                     int len = ren.kid2 - index;\r
 514                     System.out.print(" [");\r
 515                     for (int i = 0; i < len; i++)\r
 516                         System.out.print("\\u" + \r
 517                                          Integer.toHexString(source[index+i]));\r
 518                     System.out.println("]");\r
 519                     break;\r
 520                     }\r
 521 \r
 522                 default:\r
 523                     System.out.println();\r
 524                     break;\r
 525                 }\r
 526 \r
 527                 if ((ren.flags & RENode.GOODNEXT) == 0)\r
 528                     break;\r
 529             } while ((ren = ren.next) != null);\r
 530             level--;\r
 531         }\r
 532     }\r
 533 \r
 534     private void fixNext(CompilerState state, RENode ren1, RENode ren2,\r
 535                          RENode oldnext) {\r
 536         boolean goodnext;\r
 537         RENode next, kid, ren;\r
 538 \r
 539         goodnext = ren2 != null && (ren2.flags & RENode.ISNEXT) == 0;\r
 540 \r
 541         /*\r
 542          * Find the final node in a list of alternatives, or concatenations, or\r
 543          * even a concatenation of alternatives followed by non-alternatives (e.g.\r
 544          * ((x|y)z)w where ((x|y)z) is ren1 and w is ren2).\r
 545          */\r
 546         for (; (next = ren1.next) != null && next != oldnext; ren1 = next) {\r
 547             if (ren1.op == REOP_ALT) {\r
 548                 /* Find the end of this alternative's operand list. */\r
 549                 kid = (RENode) ren1.kid;\r
 550                 if (kid.op == REOP_JUMP)\r
 551                     continue;\r
 552                 for (ren = kid; ren.next != null; ren = ren.next) {\r
 553                     if (ren.op == REOP_ALT)\r
 554                         throw new RuntimeException("REOP_ALT not expected");\r
 555                 }\r
 556 \r
 557                 /* Append a jump node to all but the last alternative. */\r
 558                 ren.next = new RENode(state, REOP_JUMP, null);\r
 559                 ren.next.flags |= RENode.ISNEXT;\r
 560                 ren.flags |= RENode.GOODNEXT;\r
 561 \r
 562                 /* Recur to fix all descendent nested alternatives. */\r
 563                 fixNext(state, kid, ren2, oldnext);\r
 564             }\r
 565         }\r
 566 \r
 567         /*\r
 568          * Now ren1 points to the last alternative, or to the final node on a\r
 569          * concatenation list.  Set its next link to ren2, flagging a join point\r
 570          * if appropriate.\r
 571          */\r
 572         if (ren2 != null) {\r
 573             if ((ren2.flags & RENode.ISNEXT) == 0)\r
 574                 ren2.flags |= RENode.ISNEXT;\r
 575             else\r
 576                 ren2.flags |= RENode.ISJOIN;\r
 577         }\r
 578         ren1.next = ren2;\r
 579         if (goodnext)\r
 580             ren1.flags |= RENode.GOODNEXT;\r
 581 \r
 582         /*\r
 583          * The following ops have a kid subtree through which to recur.  Here is\r
 584          * where we fix the next links under the final ALT node's kid.\r
 585          */\r
 586         switch (ren1.op) {\r
 587         case REOP_ALT:\r
 588         case REOP_QUANT:\r
 589         case REOP_STAR:\r
 590         case REOP_PLUS:\r
 591         case REOP_OPT:\r
 592         case REOP_LPAREN:\r
 593         case REOP_LPARENNON:\r
 594         case REOP_ASSERT:\r
 595         case REOP_ASSERT_NOT:\r
 596             fixNext(state, (RENode) ren1.kid, ren2, oldnext);\r
 597             break;\r
 598         default:;\r
 599         }\r
 600     }\r
 601 \r
 602     private void setNext(CompilerState state, RENode ren1, RENode ren2) {\r
 603         fixNext(state, ren1, ren2, null);\r
 604     }\r
 605 \r
 606     /*\r
 607      * Top-down regular expression grammar, based closely on Perl 4.\r
 608      *\r
 609      *  regexp:     altern                  A regular expression is one or more\r
 610      *              altern '|' regexp       alternatives separated by vertical bar.\r
 611      */\r
 612     private RENode parseRegExp(CompilerState state) {\r
 613         RENode ren = parseAltern(state);\r
 614         if (ren == null)\r
 615             return null;\r
 616         char[] source = state.source;\r
 617         int index = state.index;\r
 618         if (index < source.length && source[index] == '|') {\r
 619             RENode kid = ren;\r
 620             ren = new RENode(state, REOP_ALT, kid);\r
 621             if (ren == null)\r
 622                 return null;\r
 623             ren.flags = (byte) (kid.flags & (RENode.ANCHORED | RENode.NONEMPTY));\r
 624             RENode ren1 = ren;\r
 625             do {\r
 626                 /* (balance: */\r
 627                 state.index = ++index;\r
 628                 if (index < source.length && (source[index] == '|' ||\r
 629                                               source[index] == ')'))\r
 630                     {\r
 631                         kid = new RENode(state, REOP_EMPTY, null);\r
 632                     } else {\r
 633                         kid = parseAltern(state);\r
 634                         index = state.index;\r
 635                     }\r
 636                 if (kid == null)\r
 637                     return null;\r
 638                 RENode ren2 = new RENode(state, REOP_ALT, kid);\r
 639                 if (ren2 == null)\r
 640                     return null;\r
 641                 ren1.next = ren2;\r
 642                 ren1.flags |= RENode.GOODNEXT;\r
 643                 ren2.flags = (byte) ((kid.flags & (RENode.ANCHORED |\r
 644                                                    RENode.NONEMPTY))\r
 645                                      | RENode.ISNEXT);\r
 646                 ren1 = ren2;\r
 647             } while (index < source.length && source[index] == '|');\r
 648         }\r
 649         return ren;\r
 650     }\r
 651 \r
 652     /*\r
 653      *  altern:     item                    An alternative is one or more items,\r
 654      *              item altern             concatenated together.\r
 655      */\r
 656     private RENode parseAltern(CompilerState state) {\r
 657         RENode ren = parseItem(state);\r
 658         if (ren == null)\r
 659             return null;\r
 660         RENode ren1 = ren;\r
 661         int flags = 0;\r
 662         char[] source = state.source;\r
 663         int index = state.index;\r
 664         char c;\r
 665         /* (balance: */\r
 666         while (index != source.length && (c = source[index]) != '|' &&\r
 667                c != ')')\r
 668             {\r
 669                 RENode ren2 = parseItem(state);\r
 670                 if (ren2 == null)\r
 671                     return null;\r
 672                 setNext(state, ren1, ren2);\r
 673                 flags |= ren2.flags;\r
 674                 ren1 = ren2;\r
 675                 index = state.index;\r
 676             }\r
 677 \r
 678         /*\r
 679          * Propagate NONEMPTY to the front of a concatenation list, so that the\r
 680          * first alternative in (^a|b) is considered non-empty.  The first node\r
 681          * in a list may match the empty string (as ^ does), but if the list is\r
 682          * non-empty, then the first node's NONEMPTY flag must be set.\r
 683          */\r
 684         ren.flags |= flags & RENode.NONEMPTY;\r
 685         return ren;\r
 686     }\r
 687 \r
 688     /*\r
 689      *  item:       assertion               An item is either an assertion or\r
 690      *              quantatom               a quantified atom.\r
 691      *\r
 692      *  assertion:  '^'                     Assertions match beginning of string\r
 693      *                                      (or line if the class static property\r
 694      *                                      RegExp.multiline is true).\r
 695      *              '$'                     End of string (or line if the class\r
 696      *                                      static property RegExp.multiline is\r
 697      *                                      true).\r
 698      *              '\b'                    Word boundary (between \w and \W).\r
 699      *              '\B'                    Word non-boundary.\r
 700      */\r
 701     RENode parseItem(CompilerState state) {\r
 702         RENode ren;\r
 703         byte op;\r
 704 \r
 705         char[] source = state.source;\r
 706         int index = state.index;\r
 707         switch (index < source.length ? source[index] : '\0') {\r
 708         case '^':\r
 709             state.index = index + 1;\r
 710             ren = new RENode(state, REOP_BOL, null);\r
 711             ren.flags |= RENode.ANCHORED;\r
 712             return ren;\r
 713 \r
 714         case '$':\r
 715             state.index = index + 1;\r
 716             return new RENode(state,\r
 717                               (index == state.indexBegin ||\r
 718                                ((source[index-1] == '(' ||\r
 719                                  source[index-1] == '|') && /*balance)*/\r
 720                                 (index - 1 == state.indexBegin ||\r
 721                                  source[index-2] != '\\')))\r
 722                               ? REOP_EOLONLY\r
 723                               : REOP_EOL,\r
 724                               null);\r
 725 \r
 726         case '\\':\r
 727             switch (++index < source.length ? source[index] : '\0') {\r
 728             case 'b':\r
 729                 op = REOP_WBDRY;\r
 730                 break;\r
 731             case 'B':\r
 732                 op = REOP_WNONBDRY;\r
 733                 break;\r
 734             default:\r
 735                 return parseQuantAtom(state);\r
 736             }\r
 737 \r
 738             /*\r
 739              * Word boundaries and non-boundaries are flagged as non-empty\r
 740              * so they will be prefixed by an anchoring node.\r
 741              */\r
 742             state.index = index + 1;\r
 743             ren = new RENode(state, op, null);\r
 744             ren.flags |= RENode.NONEMPTY;\r
 745             return ren;\r
 746 \r
 747         default:;\r
 748         }\r
 749         return parseQuantAtom(state);\r
 750     }\r
 751 \r
 752     /*\r
 753      *  quantatom:  atom                    An unquantified atom.\r
 754      *              quantatom '{' n ',' m '}'\r
 755      *                                      Atom must occur between n and m times.\r
 756      *              quantatom '{' n ',' '}' Atom must occur at least n times.\r
 757      *              quantatom '{' n '}'     Atom must occur exactly n times.\r
 758      *              quantatom '*'           Zero or more times (same as {0,}).\r
 759      *              quantatom '+'           One or more times (same as {1,}).\r
 760      *              quantatom '?'           Zero or one time (same as {0,1}).\r
 761      *\r
 762      *              any of which can be optionally followed by '?' for ungreedy\r
 763      */\r
 764     RENode parseQuantAtom(CompilerState state) {\r
 765         RENode ren = parseAtom(state);\r
 766         if (ren == null)\r
 767             return null;\r
 768 \r
 769         int up;\r
 770         char c;\r
 771         RENode ren2;\r
 772         int min, max;\r
 773         char[] source = state.source;\r
 774         int index = state.index;\r
 775         loop:\r
 776         while (index < source.length) {\r
 777             switch (source[index]) {\r
 778             case '{':\r
 779                 if (++index == source.length || !isDigit(c = source[index])) {\r
 780                     reportError("msg.bad.quant",\r
 781                                 String.valueOf(source[state.index]), state);\r
 782                     return null;\r
 783                 }\r
 784                 min = unDigit(c);\r
 785                 while (++index < source.length && isDigit(c = source[index])) {\r
 786                     min = 10 * min + unDigit(c);\r
 787                     if ((min >> 16) != 0) {\r
 788                         reportError("msg.overlarge.max", tail(source, index),\r
 789                                     state);\r
 790                         return null;\r
 791                     }\r
 792                 }\r
 793                 if (source[index] == ',') {\r
 794                     up = ++index;\r
 795                     if (isDigit(source[index])) {\r
 796                         max = unDigit(source[index]);\r
 797                         while (isDigit(c = source[++index])) {\r
 798                             max = 10 * max + unDigit(c);\r
 799                             if ((max >> 16) != 0) {\r
 800                                 reportError("msg.overlarge.max",\r
 801                                             String.valueOf(source[up]), state);\r
 802                                 return null;\r
 803                             }\r
 804                         }\r
 805                         if (max == 0) {\r
 806                             reportError("msg.zero.quant",\r
 807                                         tail(source, state.index), state);\r
 808                             return null;\r
 809                         }\r
 810                         if (min > max) {\r
 811                             reportError("msg.max.lt.min", tail(source, up), state);\r
 812                             return null;\r
 813                         }\r
 814                     } else {\r
 815                         /* 0 means no upper bound. */\r
 816                         max = 0;\r
 817                     }\r
 818                 } else {\r
 819                     /* Exactly n times. */\r
 820                     if (min == 0) {\r
 821                         reportError("msg.zero.quant",\r
 822                                     tail(source, state.index), state);\r
 823                         return null;\r
 824                     }\r
 825                     max = min;\r
 826                 }\r
 827                 if (source[index] != '}') {\r
 828                     reportError("msg.unterm.quant",\r
 829                                 String.valueOf(source[state.index]), state);\r
 830                     return null;\r
 831                 }\r
 832                 index++;\r
 833 \r
 834                 ren2 = new RENode(state, REOP_QUANT, ren);\r
 835                 if (min > 0 && (ren.flags & RENode.NONEMPTY) != 0)\r
 836                     ren2.flags |= RENode.NONEMPTY;\r
 837                 ren2.min = (short) min;\r
 838                 ren2.max = (short) max;\r
 839                 ren = ren2;\r
 840                 break;\r
 841 \r
 842             case '*':\r
 843                 index++;\r
 844                 ren = new RENode(state, REOP_STAR, ren);\r
 845                 break;\r
 846 \r
 847             case '+':\r
 848                 index++;\r
 849                 ren2 = new RENode(state, REOP_PLUS, ren);\r
 850                 if ((ren.flags & RENode.NONEMPTY) != 0)\r
 851                     ren2.flags |= RENode.NONEMPTY;\r
 852                 ren = ren2;\r
 853                 break;\r
 854 \r
 855             case '?':\r
 856                 index++;\r
 857                 ren = new RENode(state, REOP_OPT, ren);\r
 858                 break;\r
 859 \r
 860             default:\r
 861                 break loop;\r
 862             }\r
 863             if ((index < source.length) && (source[index] == '?')) {\r
 864                 ren.flags |= RENode.MINIMAL;\r
 865                 index++;\r
 866             }\r
 867         }\r
 868 \r
 869         state.index = index;\r
 870         return ren;\r
 871     }\r
 872 \r
 873     /*\r
 874      *  atom:       '(' regexp ')'          A parenthesized regexp (what matched\r
 875      *                                      can be addressed using a backreference,\r
 876      *                                      see '\' n below).\r
 877      *              '.'                     Matches any char except '\n'.\r
 878      *              '[' classlist ']'       A character class.\r
 879      *              '[' '^' classlist ']'   A negated character class.\r
 880      *              '\f'                    Form Feed.\r
 881      *              '\n'                    Newline (Line Feed).\r
 882      *              '\r'                    Carriage Return.\r
 883      *              '\t'                    Horizontal Tab.\r
 884      *              '\v'                    Vertical Tab.\r
 885      *              '\d'                    A digit (same as [0-9]).\r
 886      *              '\D'                    A non-digit.\r
 887      *              '\w'                    A word character, [0-9a-z_A-Z].\r
 888      *              '\W'                    A non-word character.\r
 889      *              '\s'                    A whitespace character, [ \b\f\n\r\t\v].\r
 890      *              '\S'                    A non-whitespace character.\r
 891      *              '\' n                   A backreference to the nth (n decimal\r
 892      *                                      and positive) parenthesized expression.\r
 893      *              '\' octal               An octal escape sequence (octal must be\r
 894      *                                      two or three digits long, unless it is\r
 895      *                                      0 for the null character).\r
 896      *              '\x' hex                A hex escape (hex must be two digits).\r
 897      *              '\c' ctrl               A control character, ctrl is a letter.\r
 898      *              '\' literalatomchar     Any character except one of the above\r
 899      *                                      that follow '\' in an atom.\r
 900      *              otheratomchar           Any character not first among the other\r
 901      *                                      atom right-hand sides.\r
 902      */\r
 903     static final String metachars    = "|^${*+?().[\\";\r
 904     static final String closurechars = "{*+?";\r
 905 \r
 906     RENode parseAtom(CompilerState state) {\r
 907         int num = 0, len;\r
 908         RENode ren = null;\r
 909         RENode ren2;\r
 910         char c;\r
 911         byte op;\r
 912 \r
 913         boolean skipCommon = false;\r
 914         boolean doFlat = false;\r
 915 \r
 916         char[] source = state.source;\r
 917         int index = state.index;\r
 918         int ocp = index;\r
 919         if (index == source.length) {\r
 920             state.index = index;\r
 921             return new RENode(state, REOP_EMPTY, null);\r
 922         }\r
 923         switch (source[index]) {\r
 924             /* handle /|a/ by returning an empty node for the leftside */\r
 925         case '|':\r
 926             return new RENode(state, REOP_EMPTY, null);\r
 927 \r
 928         case '(':\r
 929             op = REOP_END;\r
 930             if (source[index + 1] == '?') {\r
 931                 switch (source[index + 2]) {\r
 932                 case ':' :\r
 933                     op = REOP_LPARENNON;\r
 934                     break;\r
 935                 case '=' :\r
 936                     op = REOP_ASSERT;\r
 937                     break;\r
 938                 case '!' :\r
 939                     op = REOP_ASSERT_NOT;\r
 940                     break;\r
 941                 }\r
 942             }\r
 943             if (op == REOP_END) {\r
 944                 op = REOP_LPAREN;\r
 945                 num = state.parenCount++;      /* \1 is numbered 0, etc. */\r
 946                 index++;\r
 947             }\r
 948             else\r
 949                 index += 3;\r
 950             state.index = index;\r
 951             /* Handle empty paren */\r
 952             if (source[index] == ')') {\r
 953                 ren2 = new RENode(state, REOP_EMPTY, null);\r
 954             }\r
 955             else {\r
 956                 ren2 = parseRegExp(state);\r
 957                 if (ren2 == null)\r
 958                     return null;\r
 959                 index = state.index;\r
 960                 if (index >= source.length || source[index] != ')') {\r
 961                     reportError("msg.unterm.paren", tail(source, ocp), state);\r
 962                     return null;\r
 963                 }\r
 964             }\r
 965             index++;\r
 966             ren = new RENode(state, op, ren2);\r
 967             ren.flags = (byte) (ren2.flags & (RENode.ANCHORED |\r
 968                                               RENode.NONEMPTY));\r
 969             ren.num = num;\r
 970             if ((op == REOP_LPAREN) || (op == REOP_LPARENNON)) {\r
 971                 /* Assume RPAREN ops immediately succeed LPAREN ops */\r
 972                 ren2 = new RENode(state, (byte)(op + 1), null);\r
 973                 setNext(state, ren, ren2);\r
 974                 ren2.num = num;\r
 975             }\r
 976             break;\r
 977 \r
 978         case '.':\r
 979             ++index;\r
 980             op = REOP_DOT;\r
 981             if ((index < source.length) && (source[index] == '*')) {\r
 982                 index++;\r
 983                 op = REOP_DOTSTAR;\r
 984                 if ((index < source.length) && (source[index] == '?')) {\r
 985                     index++;\r
 986                     op = REOP_DOTSTARMIN;\r
 987                 }\r
 988             }\r
 989             ren = new RENode(state, op, null);\r
 990             if (ren.op == REOP_DOT)\r
 991                 ren.flags = RENode.SINGLE | RENode.NONEMPTY;\r
 992             break;\r
 993 \r
 994         case '[':\r
 995             /* A char class must have at least one char in it. */\r
 996             if (++index == source.length) {\r
 997                 reportError("msg.unterm.class", tail(source, ocp), state);\r
 998                 return null;\r
 999             }\r
1000             c = source[index];\r
1001             ren = new RENode(state, REOP_CCLASS, new Integer(index));\r
1002 \r
1003             /* A negated class must have at least one char in it after the ^. */\r
1004             if (c == '^' && ++index == source.length) {\r
1005                 reportError("msg.unterm.class", tail(source, ocp), state);\r
1006                 return null;\r
1007             }\r
1008 \r
1009             for (;;) {\r
1010                 if (++index == source.length) {\r
1011                     reportError("msg.unterm.paren", tail(source, ocp), state);\r
1012                     return null;\r
1013                 }\r
1014                 c = source[index];\r
1015                 if (c == ']')\r
1016                     break;\r
1017                 if (c == '\\' && index+1 != source.length)\r
1018                     index++;\r
1019             }\r
1020             ren.kid2 = index++;\r
1021 \r
1022             /* Since we rule out [] and [^], we can set the non-empty flag. */\r
1023             ren.flags = RENode.SINGLE | RENode.NONEMPTY;\r
1024             break;\r
1025 \r
1026         case '\\':\r
1027             if (++index == source.length) {\r
1028                 Context.reportError(ScriptRuntime.getMessage("msg.trail.backslash",\r
1029                                                              null));\r
1030                 return null;\r
1031             }\r
1032             c = source[index];\r
1033             switch (c) {\r
1034             case 'f':\r
1035             case 'n':\r
1036             case 'r':\r
1037             case 't':\r
1038             case 'v':\r
1039                 c = getEscape(c);\r
1040                 ren = new RENode(state, REOP_FLAT1, null);\r
1041                 break;\r
1042             case 'd':\r
1043                 ren = new RENode(state, REOP_DIGIT, null);\r
1044                 break;\r
1045             case 'D':\r
1046                 ren = new RENode(state, REOP_NONDIGIT, null);\r
1047                 break;\r
1048             case 'w':\r
1049                 ren = new RENode(state, REOP_ALNUM, null);\r
1050                 break;\r
1051             case 'W':\r
1052                 ren = new RENode(state, REOP_NONALNUM, null);\r
1053                 break;\r
1054             case 's':\r
1055                 ren = new RENode(state, REOP_SPACE, null);\r
1056                 break;\r
1057             case 'S':\r
1058                 ren = new RENode(state, REOP_NONSPACE, null);\r
1059                 break;\r
1060 \r
1061             case '0':\r
1062             case '1':\r
1063             case '2':\r
1064             case '3':\r
1065             case '4':\r
1066             case '5':\r
1067             case '6':\r
1068             case '7':\r
1069             case '8':\r
1070             case '9':\r
1071                 /*\r
1072                   Yuk. Keeping the old style \n interpretation for 1.2\r
1073                   compatibility.\r
1074                 */\r
1075                 if ((state.cx.getLanguageVersion() != Context.VERSION_DEFAULT)\r
1076                     && (state.cx.getLanguageVersion() <= Context.VERSION_1_4)) {\r
1077                     switch (c) {                    \r
1078                     case '0':\r
1079                         state.index = index;\r
1080                         num = doOctal(state);\r
1081                         index = state.index;\r
1082                         ren = new RENode(state, REOP_FLAT1, null);\r
1083                         c = (char) num;\r
1084                         break;\r
1085 \r
1086                     case '1':\r
1087                     case '2':\r
1088                     case '3':\r
1089                     case '4':\r
1090                     case '5':\r
1091                     case '6':\r
1092                     case '7':\r
1093                     case '8':\r
1094                     case '9':\r
1095                         num = unDigit(c);\r
1096                         len = 1;\r
1097                         while (++index < source.length\r
1098                                && isDigit(c = source[index])) {\r
1099                             num = 10 * num + unDigit(c);\r
1100                             len++;\r
1101                         }\r
1102                         /* n in [8-9] and > count of parenetheses, then revert to\r
1103                            '8' or '9', ignoring the '\' */\r
1104                         if (((num == 8) || (num == 9)) && (num > state.parenCount)) {\r
1105                             ocp = --index;  /* skip beyond the '\' */\r
1106                             doFlat = true;\r
1107                             skipCommon = true;\r
1108                             break;                        \r
1109                         }\r
1110                         /* more than 1 digit, or a number greater than\r
1111                            the count of parentheses => it's an octal */\r
1112                         if ((len > 1) || (num > state.parenCount)) {\r
1113                             state.index = ocp;\r
1114                             num = doOctal(state);\r
1115                             index = state.index;\r
1116                             ren = new RENode(state, REOP_FLAT1, null);\r
1117                             c = (char) num;\r
1118                             break;\r
1119                         }\r
1120                         index--;\r
1121                         ren = new RENode(state, REOP_BACKREF, null);\r
1122                         ren.num = num - 1;       /* \1 is numbered 0, etc. */\r
1123 \r
1124                         /* Avoid common chr- and flags-setting \r
1125                            code after switch. */\r
1126                         ren.flags = RENode.NONEMPTY;\r
1127                         skipCommon = true;\r
1128                         break;\r
1129                     }\r
1130                 }\r
1131                 else {\r
1132                     if (c == '0') {\r
1133                         ren = new RENode(state, REOP_FLAT1, null);\r
1134                         c = 0;\r
1135                     }\r
1136                     else {\r
1137                         num = unDigit(c);\r
1138                         len = 1;\r
1139                         while (++index < source.length\r
1140                                && isDigit(c = source[index])) {\r
1141                             num = 10 * num + unDigit(c);\r
1142                             len++;\r
1143                         }\r
1144                         index--;\r
1145                         ren = new RENode(state, REOP_BACKREF, null);\r
1146                         ren.num = num - 1;       /* \1 is numbered 0, etc. */\r
1147                         /* Avoid common chr- and flags-setting \r
1148                            code after switch. */\r
1149                         ren.flags = RENode.NONEMPTY;\r
1150                         skipCommon = true;\r
1151                     }\r
1152                 }\r
1153                 break;\r
1154                 \r
1155             case 'x':\r
1156                 ocp = index;\r
1157                 if (++index < source.length && isHex(c = source[index])) {\r
1158                     num = unHex(c);\r
1159                     if (++index < source.length && isHex(c = source[index])) {\r
1160                         num <<= 4;\r
1161                         num += unHex(c);\r
1162                     } else {\r
1163                         if ((state.cx.getLanguageVersion()\r
1164                              != Context.VERSION_DEFAULT)\r
1165                             && (state.cx.getLanguageVersion() \r
1166                                 <= Context.VERSION_1_4)) \r
1167                             index--; /* back up so index points to last hex char */\r
1168                         else { /* ecma 2 requires pairs of hex digits. */\r
1169                             index = ocp;\r
1170                             num = 'x';\r
1171                         }\r
1172                     }\r
1173                 } else {\r
1174                     index = ocp;        /* \xZZ is xZZ (Perl does \0ZZ!) */\r
1175                     num = 'x';\r
1176                 }\r
1177                 ren = new RENode(state, REOP_FLAT1, null);\r
1178                 c = (char)num;\r
1179                 break;\r
1180 \r
1181             case 'c':\r
1182                 c = source[++index];\r
1183                 if (!('A' <= c && c <= 'Z') && !('a' <= c && c <= 'z')) {\r
1184                     index -= 2;\r
1185                     ocp = index;\r
1186                     doFlat = true;\r
1187                     skipCommon = true;\r
1188                     break;\r
1189                 }\r
1190                 c = Character.toUpperCase(c);\r
1191                 c = (char) (c ^ 64); // JS_TOCTRL\r
1192                 ren = new RENode(state, REOP_FLAT1, null);\r
1193                 break;\r
1194 \r
1195             case 'u':\r
1196                 if (index+4 < source.length &&\r
1197                     isHex(source[index+1]) && isHex(source[index+2]) &&\r
1198                     isHex(source[index+3]) && isHex(source[index+4]))\r
1199                     {\r
1200                         num = (((((unHex(source[index+1]) << 4) +\r
1201                                   unHex(source[index+2])) << 4) +\r
1202                                 unHex(source[index+3])) << 4) +\r
1203                             unHex(source[index+4]);\r
1204                         c = (char) num;\r
1205                         index += 4;\r
1206                         ren = new RENode(state, REOP_FLAT1, null);\r
1207                         break;\r
1208                     }\r
1209 \r
1210                 /* Unlike Perl \\xZZ, we take \\uZZZ to be literal-u then ZZZ. */\r
1211                 ocp = index;\r
1212                 doFlat = true;\r
1213                 skipCommon = true;\r
1214                 break;\r
1215 \r
1216             default:\r
1217                 ocp = index;\r
1218                 doFlat = true;\r
1219                 skipCommon = true;\r
1220                 break;\r
1221             }\r
1222 \r
1223             /* Common chr- and flags-setting code for escape opcodes. */\r
1224             if (ren != null && !skipCommon) {\r
1225                 ren.chr = c;\r
1226                 ren.flags = RENode.SINGLE | RENode.NONEMPTY;\r
1227             }\r
1228             skipCommon = false;\r
1229 \r
1230             if (!doFlat) {\r
1231                 /* Skip to next unparsed char. */\r
1232                 index++;\r
1233                 break;\r
1234             }\r
1235 \r
1236             /* fall through since doFlat was true */\r
1237             doFlat = false;\r
1238 \r
1239         default:\r
1240             while (++index != source.length &&\r
1241                    metachars.indexOf(source[index]) == -1)\r
1242                 ;\r
1243             len = (int)(index - ocp);\r
1244             if (index != source.length && len > 1 &&\r
1245                 closurechars.indexOf(source[index]) != -1)\r
1246                 {\r
1247                     index--;\r
1248                     len--;\r
1249                 }\r
1250             if (len > REOP_FLATLEN_MAX) {\r
1251                 len = REOP_FLATLEN_MAX;\r
1252                 index = ocp + len;\r
1253             }\r
1254             ren = new RENode(state, len == 1 ? REOP_FLAT1 : REOP_FLAT,\r
1255                              new Integer(ocp));\r
1256             ren.flags = RENode.NONEMPTY;\r
1257             if (len > 1) {\r
1258                 ren.kid2 = index;\r
1259             } else {\r
1260                 ren.flags |= RENode.SINGLE;\r
1261                 ren.chr = source[ocp];\r
1262             }\r
1263             break;\r
1264         }\r
1265 \r
1266         state.index = index;\r
1267         return ren;\r
1268     }\r
1269 \r
1270     private int doOctal(CompilerState state) {\r
1271         char[] source = state.source;\r
1272         int index = state.index;\r
1273         int tmp, num = 0;\r
1274         char c;\r
1275         while (++index < source.length && '0' <= (c = source[index]) &&\r
1276                c <= '7')\r
1277             {\r
1278                 tmp = 8 * num + (int)(c - '0');\r
1279                 if (tmp > 0377) {\r
1280                     break;\r
1281                 }\r
1282                 num = tmp;\r
1283             }\r
1284         index--;\r
1285         state.index = index;\r
1286         return num;\r
1287     }\r
1288 \r
1289     static char getEscape(char c) {\r
1290         switch (c) {\r
1291         case 'b':\r
1292             return '\b';\r
1293         case 'f':\r
1294             return '\f';\r
1295         case 'n':\r
1296             return '\n';\r
1297         case 'r':\r
1298             return '\r';\r
1299         case 't':\r
1300             return '\t';\r
1301         case 'v':\r
1302             return (char) 11; // '\v' is not vtab in Java\r
1303         }\r
1304         throw new RuntimeException();\r
1305     }\r
1306 \r
1307     static public boolean isDigit(char c) {\r
1308         return '0' <= c && c <= '9';\r
1309     }\r
1310 \r
1311     static int unDigit(char c) {\r
1312         return c - '0';\r
1313     }\r
1314 \r
1315     static boolean isHex(char c) {\r
1316         return ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') ||\r
1317             ('A' <= c && c <= 'F');\r
1318     }\r
1319 \r
1320     static int unHex(char c) {\r
1321         if ('0' <= c && c <= '9')\r
1322             return c - '0';\r
1323         return 10 + Character.toLowerCase(c) - 'a';\r
1324     }\r
1325 \r
1326     static boolean isWord(char c) {\r
1327         return Character.isLetter(c) || isDigit(c) || c == '_';\r
1328     }\r
1329 \r
1330     private String tail(char[] a, int i) {\r
1331         return new String(a, i, a.length - i);\r
1332     }\r
1333 \r
1334     private static boolean matchChar(int flags, char c, char c2) {\r
1335         if (c == c2)\r
1336             return true;\r
1337         else\r
1338             if ((flags & FOLD) != 0) {\r
1339                 c = Character.toUpperCase(c);\r
1340                 c2 = Character.toUpperCase(c2);\r
1341                 return c == c2 ||\r
1342                     Character.toLowerCase(c) == Character.toLowerCase(c2);\r
1343             }\r
1344             else\r
1345                 return false;\r
1346     }\r
1347     \r
1348     \r
1349     int greedyRecurse(GreedyState grState, int index, int previousKid) {\r
1350         int kidMatch;\r
1351         int match;\r
1352         int num;\r
1353 \r
1354         /*\r
1355          *    when the kid match fails, we reset the parencount and run any \r
1356          *    previously succesful kid in order to restablish it's paren\r
1357          *    contents.\r
1358          */\r
1359 \r
1360         num = grState.state.parenCount;\r
1361         kidMatch = matchRENodes(grState.state, grState.kid, grState.next, index);\r
1362         if (kidMatch == -1) {\r
1363             match = matchRENodes(grState.state, grState.next, grState.stop, index);\r
1364             if (match != -1) {\r
1365                 grState.state.parenCount = num;\r
1366                 if (previousKid != -1)\r
1367                     matchRENodes(grState.state, grState.kid, grState.next, previousKid);\r
1368                 return index;\r
1369             }\r
1370             else\r
1371                 return -1;\r
1372         }\r
1373         else {\r
1374             if (kidMatch == index) {\r
1375                 if (previousKid != -1)\r
1376                     matchRENodes(grState.state, grState.kid, grState.next, previousKid);\r
1377                 return kidMatch;    /* no point pursuing an empty match forever */\r
1378             }\r
1379             if ((grState.maxKid == 0) || (++grState.kidCount < grState.maxKid)) {\r
1380                 match = greedyRecurse(grState, kidMatch, index);\r
1381                 if (match != -1) return match;\r
1382                 if (grState.maxKid != 0) --grState.kidCount;\r
1383             }\r
1384             grState.state.parenCount = num;\r
1385             match = matchRENodes(grState.state, grState.next, grState.stop, kidMatch);\r
1386             if (match != -1) {\r
1387                 matchRENodes(grState.state, grState.kid, grState.next, index);\r
1388                 return kidMatch;\r
1389             }\r
1390             else\r
1391                 return -1;\r
1392         }\r
1393     }\r
1394 \r
1395     int matchGreedyKid(MatchState state, RENode ren, RENode stop,\r
1396                        int kidCount, int index, int previousKid) {\r
1397         GreedyState grState = new GreedyState();\r
1398         grState.state = state;\r
1399         grState.kid = (RENode)ren.kid;\r
1400         grState.next = ren.next;\r
1401         grState.maxKid = (ren.op == REOP_QUANT) ? ren.max : 0;\r
1402         /*\r
1403          * We try to match the sub-tree to completion first, and if that\r
1404          * doesn't work, match only up to the given end of the sub-tree.\r
1405          */\r
1406         grState.stop = null;\r
1407         grState.kidCount = kidCount;\r
1408         int match = greedyRecurse(grState, index, previousKid);\r
1409         if (match != -1 || stop == null) return match;\r
1410         grState.kidCount = kidCount;\r
1411         grState.stop = stop;\r
1412         return greedyRecurse(grState, index, previousKid);\r
1413     }\r
1414 \r
1415     int matchNonGreedyKid(MatchState state, RENode ren,\r
1416                           int kidCount, int maxKid,\r
1417                           int index) {\r
1418         int kidMatch;\r
1419         int match;\r
1420 \r
1421         match = matchRENodes(state, ren.next, null, index);\r
1422         if (match != -1) return index;\r
1423         kidMatch = matchRENodes(state, (RENode)ren.kid, ren.next, index);\r
1424         if (kidMatch == -1) return -1;\r
1425         if (kidMatch == index) return kidMatch;    /* no point pursuing an empty match forever */\r
1426         return matchNonGreedyKid(state, ren, kidCount, maxKid, kidMatch);\r
1427     }\r
1428 \r
1429     int matchRENodes(MatchState state, RENode ren, RENode stop, int index) {\r
1430         int num;\r
1431         char[] input = state.input;\r
1432         while ((ren != stop) && (ren != null)) {\r
1433                 switch (ren.op) {\r
1434                 case REOP_EMPTY:\r
1435                     break;\r
1436                 case REOP_ALT: {\r
1437                     if (ren.next.op != REOP_ALT) {\r
1438                         ren = (RENode)ren.kid;\r
1439                         continue;\r
1440                     }\r
1441                     else {\r
1442                         num = state.parenCount;\r
1443                         int kidMatch = matchRENodes(state, (RENode)ren.kid,\r
1444                                                     stop, index);\r
1445                         if (kidMatch != -1) return kidMatch;\r
1446                         for (int i = num; i < state.parenCount; i++)\r
1447                             state.parens[i] = null;\r
1448                         state.parenCount = num;\r
1449                     }\r
1450                 }\r
1451                     break;\r
1452                 case REOP_QUANT: {\r
1453                     int lastKid = -1;\r
1454                     for (num = 0; num < ren.min; num++) {\r
1455                         int kidMatch = matchRENodes(state, (RENode)ren.kid,\r
1456                                                     ren.next, index);\r
1457                         if (kidMatch == -1)\r
1458                             return -1;\r
1459                         else {\r
1460                             lastKid = index;\r
1461                             index = kidMatch;\r
1462                         }\r
1463                     }\r
1464                     if (num == ren.max)\r
1465                         // Have matched the exact count required, \r
1466                         // need to match the rest of the regexp.\r
1467                         break;\r
1468                     if ((ren.flags & RENode.MINIMAL) == 0) {\r
1469                         int kidMatch = matchGreedyKid(state, ren, stop, num,\r
1470                                                       index, lastKid);\r
1471                         if (kidMatch == -1)\r
1472                             index = matchRENodes(state, (RENode)ren.kid,\r
1473                                                  ren.next, index);\r
1474                         else \r
1475                             index = kidMatch;\r
1476                     }        \r
1477                     else {\r
1478                         index = matchNonGreedyKid(state, ren, num,\r
1479                                                   ren.max, index);\r
1480                     }                           \r
1481                     if (index == -1) return -1;\r
1482                 }\r
1483                     break;\r
1484                 case REOP_PLUS: {\r
1485                     int kidMatch = matchRENodes(state, (RENode)ren.kid, \r
1486                                                 ren.next, index);\r
1487                     if (kidMatch == -1)\r
1488                         return -1;\r
1489                     if ((ren.flags & RENode.MINIMAL) == 0) {\r
1490                         kidMatch = matchGreedyKid(state, ren, stop, 1, \r
1491                                                   kidMatch, index);\r
1492                         if (kidMatch == -1)\r
1493                             index = matchRENodes(state,(RENode)ren.kid,\r
1494                                                  ren.next, index);\r
1495                         else\r
1496                             index = kidMatch;\r
1497                     }\r
1498                     else\r
1499                         index = matchNonGreedyKid(state, ren, 1, 0, kidMatch);\r
1500                     if (index == -1) return -1;\r
1501                 }\r
1502                     break;\r
1503                 case REOP_STAR:                                 \r
1504                     if ((ren.flags & RENode.MINIMAL) == 0) {\r
1505                         int kidMatch = matchGreedyKid(state, ren, stop, 0, index, -1);\r
1506                         if (kidMatch != -1)\r
1507                             index = kidMatch;\r
1508                     }\r
1509                     else {\r
1510                         index = matchNonGreedyKid(state, ren, 0, 0, index);\r
1511                         if (index == -1) return -1;\r
1512                     }\r
1513                     break;\r
1514                 case REOP_OPT: {\r
1515                     int saveNum = state.parenCount;\r
1516                     if (((ren.flags & RENode.MINIMAL) != 0)) {\r
1517                         int restMatch = matchRENodes(state, ren.next,\r
1518                                                      stop, index);\r
1519                         if (restMatch != -1) return restMatch;\r
1520                     }\r
1521                     int kidMatch = matchRENodes(state, (RENode)ren.kid,\r
1522                                                 ren.next, index);\r
1523                     if (kidMatch == -1) {\r
1524                         state.parenCount = saveNum;\r
1525                         break;\r
1526                     }\r
1527                     else {\r
1528                         int restMatch = matchRENodes(state, ren.next,\r
1529                                                      stop, kidMatch);\r
1530                         if (restMatch == -1) {\r
1531                             // need to undo the result of running the kid\r
1532                             state.parenCount = saveNum;\r
1533                             break;\r
1534                         }\r
1535                         else\r
1536                             return restMatch;\r
1537                     }\r
1538                 }\r
1539                 case REOP_LPARENNON:\r
1540                     ren = (RENode)ren.kid;\r
1541                     continue;\r
1542                 case REOP_RPARENNON:\r
1543                     break;\r
1544                 case REOP_LPAREN: {\r
1545                     num = ren.num;\r
1546                     ren = (RENode)ren.kid;\r
1547                     SubString parsub = state.parens[num];\r
1548                     if (parsub == null) {\r
1549                         parsub = state.parens[num] = new SubString();\r
1550                         parsub.charArray = input;\r
1551                     }\r
1552                     parsub.index = index;\r
1553                     parsub.length = 0;\r
1554                     if (num >= state.parenCount)\r
1555                         state.parenCount = num + 1;\r
1556                     continue;\r
1557                 }\r
1558                 case REOP_RPAREN: {\r
1559                     num = ren.num;\r
1560                     SubString parsub = state.parens[num];\r
1561                     if (parsub == null)\r
1562                         throw new RuntimeException("Paren problem");\r
1563                     parsub.length = index - parsub.index;\r
1564                     break;\r
1565                 }\r
1566                 case REOP_ASSERT: {\r
1567                     int kidMatch = matchRENodes(state, (RENode)ren.kid,\r
1568                                                 ren.next, index);\r
1569                     if (kidMatch == -1) return -1;\r
1570                     break;\r
1571                 }\r
1572                 case REOP_ASSERT_NOT: {\r
1573                     int kidMatch = matchRENodes(state, (RENode)ren.kid,\r
1574                                                 ren.next, index);\r
1575                     if (kidMatch != -1) return -1;\r
1576                     break;\r
1577                 }\r
1578                 case REOP_BACKREF: {\r
1579                     num = ren.num;\r
1580                     if (num >= state.parens.length) {\r
1581                         Context.reportError(\r
1582                                             ScriptRuntime.getMessage(\r
1583                                                                      "msg.bad.backref", null));\r
1584                         return -1;\r
1585                     }\r
1586                     SubString parsub = state.parens[num];\r
1587                     if (parsub == null)\r
1588                         parsub = state.parens[num] = new SubString();\r
1589                     int length = parsub.length;\r
1590                     for (int i = 0; i < length; i++, index++) {\r
1591                         if (index >= input.length) {\r
1592                             return state.noMoreInput();\r
1593                         }\r
1594                         if (!matchChar(state.flags, input[index],\r
1595                                        parsub.charArray[parsub.index + i]))\r
1596                             return -1;\r
1597                     }\r
1598                 }\r
1599                     break;\r
1600                 case REOP_CCLASS:\r
1601                     if (index >= input.length) {\r
1602                         return state.noMoreInput();\r
1603                     }\r
1604                     if (ren.bitmap == null) {\r
1605                         char[] source = (ren.s != null) \r
1606                             ? ren.s \r
1607                             : this.source.toCharArray();\r
1608                         ren.buildBitmap(state, source, ((state.flags & FOLD) != 0));\r
1609                     }\r
1610                     char c = input[index];\r
1611                     int b = (c >>> 3);\r
1612                     if (b >= ren.bmsize) {\r
1613                         if (ren.kid2 == -1) // a ^ class\r
1614                             index++;\r
1615                         else\r
1616                             return -1;\r
1617                     } else {\r
1618                         int bit = c & 7;\r
1619                         bit = 1 << bit;\r
1620                         if ((ren.bitmap[b] & bit) != 0)\r
1621                             index++;\r
1622                         else\r
1623                             return -1;\r
1624                     }\r
1625                     break;\r
1626                 case REOP_DOT:\r
1627                     if (index >= input.length) {\r
1628                         return state.noMoreInput();\r
1629                     }\r
1630                     if (input[index] != '\n')\r
1631                         index++;\r
1632                     else\r
1633                         return -1;\r
1634                     break;\r
1635                 case REOP_DOTSTARMIN: {\r
1636                     int cp2;\r
1637                     for (cp2 = index; cp2 < input.length; cp2++) {\r
1638                         int cp3 = matchRENodes(state, ren.next, stop, cp2);\r
1639                         if (cp3 != -1) return cp3;\r
1640                         if (input[cp2] == '\n')\r
1641                             return -1;\r
1642                     }\r
1643                     return state.noMoreInput();\r
1644                 }\r
1645                 case REOP_DOTSTAR: {\r
1646                     int cp2;\r
1647                     for (cp2 = index; cp2 < input.length; cp2++)\r
1648                         if (input[cp2] == '\n')\r
1649                             break;\r
1650                     while (cp2 >= index) {\r
1651                         int cp3 = matchRENodes(state, ren.next, stop, cp2);\r
1652                         if (cp3 != -1) {\r
1653                             index = cp2;\r
1654                             break;\r
1655                         }\r
1656                         cp2--;\r
1657                     }\r
1658                     break;\r
1659                 }\r
1660                 case REOP_WBDRY:\r
1661                     if (index == 0 || !isWord(input[index-1])) {\r
1662                         if (index >= input.length)\r
1663                             return state.noMoreInput();\r
1664                         if (!isWord(input[index]))\r
1665                             return -1;\r
1666                     }\r
1667                     else {\r
1668                         if (index < input.length && isWord(input[index]))\r
1669                             return -1;\r
1670                     }\r
1671                     break;\r
1672                 case REOP_WNONBDRY:\r
1673                     if (index == 0 || !isWord(input[index-1])) {\r
1674                         if (index < input.length && isWord(input[index]))\r
1675                             return -1;\r
1676                     }\r
1677                     else {\r
1678                         if (index >= input.length)\r
1679                             return state.noMoreInput();\r
1680                         if (!isWord(input[index]))\r
1681                             return -1;\r
1682                     }\r
1683                     break;\r
1684                 case REOP_EOLONLY:\r
1685                 case REOP_EOL: {\r
1686                     if (index == input.length)\r
1687                         ; // leave index;\r
1688                     else {\r
1689                         Context cx = Context.getCurrentContext();\r
1690                         RegExpImpl reImpl = getImpl(cx);\r
1691                         if ((reImpl.multiline)\r
1692                             || ((state.flags & MULTILINE) != 0))\r
1693                             if (input[index] == '\n')\r
1694                                 ;// leave index\r
1695                             else\r
1696                                 return -1;\r
1697                         else\r
1698                             return -1;\r
1699                     }\r
1700                 }\r
1701                     break;\r
1702                 case REOP_BOL: {\r
1703                     Context cx = Context.getCurrentContext();\r
1704                     RegExpImpl reImpl = getImpl(cx);\r
1705                     if (index != 0) {\r
1706                         if (reImpl.multiline ||\r
1707                             ((state.flags & MULTILINE) != 0)) {\r
1708                             if (index >= input.length) {\r
1709                                 return state.noMoreInput();\r
1710                             }\r
1711                             if (input[index - 1] == '\n') {\r
1712                                 break;\r
1713                             }\r
1714                         }\r
1715                         return -1;\r
1716                     }\r
1717                     // leave index\r
1718                 }\r
1719                     break;\r
1720                 case REOP_DIGIT:\r
1721                     if (index >= input.length) {\r
1722                         return state.noMoreInput();\r
1723                     }\r
1724                     if (!isDigit(input[index])) return -1;\r
1725                     index++;\r
1726                     break;\r
1727                 case REOP_NONDIGIT:\r
1728                     if (index >= input.length) {\r
1729                         return state.noMoreInput();\r
1730                     }\r
1731                     if (isDigit(input[index])) return -1;\r
1732                     index++;\r
1733                     break;\r
1734                 case REOP_ALNUM:\r
1735                     if (index >= input.length) {\r
1736                         return state.noMoreInput();\r
1737                     }\r
1738                     if (!isWord(input[index])) return -1;\r
1739                     index++;\r
1740                     break;\r
1741                 case REOP_NONALNUM:\r
1742                     if (index >= input.length) {\r
1743                         return state.noMoreInput();\r
1744                     }\r
1745                     if (isWord(input[index])) return -1;\r
1746                     index++;\r
1747                     break;\r
1748                 case REOP_SPACE:\r
1749                     if (index >= input.length) {\r
1750                         return state.noMoreInput();\r
1751                     }\r
1752                     if (!(TokenStream.isJSSpace(input[index]) ||\r
1753                           TokenStream.isJSLineTerminator(input[index])))\r
1754                         return -1;\r
1755                     index++;\r
1756                     break;\r
1757                 case REOP_NONSPACE:\r
1758                     if (index >= input.length) {\r
1759                         return state.noMoreInput();\r
1760                     }\r
1761                     if (TokenStream.isJSSpace(input[index]) ||\r
1762                         TokenStream.isJSLineTerminator(input[index]))\r
1763                         return -1;\r
1764                     index++;\r
1765                     break;\r
1766                 case REOP_FLAT1:\r
1767                     if (index >= input.length) {\r
1768                         return state.noMoreInput();\r
1769                     }\r
1770                     if (!matchChar(state.flags, ren.chr, input[index]))\r
1771                         return -1;\r
1772                     index++;\r
1773                     break;\r
1774                 case REOP_FLAT: {\r
1775                     char[] source = (ren.s != null)\r
1776                         ? ren.s\r
1777                         : this.source.toCharArray();\r
1778                     int start = ((Integer)ren.kid).intValue();\r
1779                     int length = ren.kid2 - start;\r
1780                     for (int i = 0; i < length; i++, index++) {\r
1781                         if (index >= input.length) {\r
1782                             return state.noMoreInput();\r
1783                         }\r
1784                         if (!matchChar(state.flags, input[index],\r
1785                                        source[start + i]))\r
1786                             return -1;\r
1787                     }\r
1788                 }\r
1789                     break;\r
1790                 case REOP_JUMP:\r
1791                     break;\r
1792                 case REOP_END:\r
1793                     break;\r
1794                 default :\r
1795                     throw new RuntimeException("Unsupported by node matcher");\r
1796                 }\r
1797                 ren = ren.next;\r
1798             }\r
1799         return index;\r
1800     }\r
1801 \r
1802     int matchRegExp(MatchState state, RENode ren, int index) {\r
1803         // have to include the position beyond the last character\r
1804         // in order to detect end-of-input/line condition\r
1805         for (int i = index; i <= state.input.length; i++) {            \r
1806             state.skipped = i - index;\r
1807             state.parenCount = 0;\r
1808             int result = matchRENodes(state, ren, null, i);\r
1809             if (result != -1)\r
1810                 return result;\r
1811         }\r
1812         return -1;\r
1813     }\r
1814 \r
1815     /*\r
1816      * indexp is assumed to be an array of length 1\r
1817      */\r
1818     Object executeRegExp(Context cx, Scriptable scopeObj, RegExpImpl res,\r
1819                          String str, int indexp[], int matchType) \r
1820     {\r
1821         NativeRegExp re = this;\r
1822         /*\r
1823          * Initialize a CompilerState to minimize recursive argument traffic.\r
1824          */\r
1825         MatchState state = new MatchState();\r
1826         state.inputExhausted = false;\r
1827         state.anchoring = false;\r
1828         state.flags = re.flags;\r
1829         state.scope = scopeObj;\r
1830 \r
1831         char[] charArray = str.toCharArray();\r
1832         int start = indexp[0];\r
1833         if (start > charArray.length)\r
1834             start = charArray.length;\r
1835         int index = start;\r
1836         state.cpbegin = 0;\r
1837         state.cpend = charArray.length;\r
1838         state.start = start;\r
1839         state.skipped = 0;\r
1840         state.input = charArray;\r
1841 \r
1842         state.parenCount = 0;\r
1843         state.maybeParens = new SubString[re.parenCount];\r
1844         state.parens = new SubString[re.parenCount];\r
1845         // We allocate the elements of "parens" and "maybeParens" lazily in\r
1846         // the Java port since we don't have arenas.\r
1847 \r
1848         /*\r
1849          * Call the recursive matcher to do the real work.  Return null on mismatch\r
1850          * whether testing or not.  On match, return an extended Array object.\r
1851          */\r
1852         index = matchRegExp(state, ren, index);\r
1853         if (index == -1) {\r
1854             if (matchType != PREFIX || !state.inputExhausted) return null;\r
1855             return Undefined.instance;\r
1856         }\r
1857         int i = index - state.cpbegin;\r
1858         indexp[0] = i;\r
1859         int matchlen = i - (start + state.skipped);\r
1860         int ep = index; \r
1861         index -= matchlen;\r
1862         Object result;\r
1863         Scriptable obj;\r
1864 \r
1865         if (matchType == TEST) {\r
1866             /*\r
1867              * Testing for a match and updating cx.regExpImpl: don't allocate\r
1868              * an array object, do return true.\r
1869              */\r
1870             result = Boolean.TRUE;\r
1871             obj = null;\r
1872         }\r
1873         else {\r
1874             /*\r
1875              * The array returned on match has element 0 bound to the matched\r
1876              * string, elements 1 through state.parenCount bound to the paren\r
1877              * matches, an index property telling the length of the left context,\r
1878              * and an input property referring to the input string.\r
1879              */\r
1880             Scriptable scope = getTopLevelScope(scopeObj);\r
1881             result = ScriptRuntime.newObject(cx, scope, "Array", null);\r
1882             obj = (Scriptable) result;\r
1883 \r
1884             String matchstr = new String(charArray, index, matchlen);\r
1885             obj.put(0, obj, matchstr);\r
1886         }\r
1887 \r
1888         if (state.parenCount > re.parenCount)\r
1889             throw new RuntimeException();\r
1890         if (state.parenCount == 0) {\r
1891             res.parens.setSize(0);\r
1892             res.lastParen = SubString.emptySubString;\r
1893         } else {\r
1894             SubString parsub = null;\r
1895             int num;\r
1896             res.parens.setSize(state.parenCount);\r
1897             for (num = 0; num < state.parenCount; num++) {\r
1898                 parsub = state.parens[num];\r
1899                 res.parens.setElementAt(parsub, num);\r
1900                 if (matchType == TEST) continue;\r
1901                 String parstr = parsub == null ? "": parsub.toString();\r
1902                 obj.put(num+1, obj, parstr);\r
1903             }\r
1904             res.lastParen = parsub;\r
1905         }\r
1906 \r
1907         if (! (matchType == TEST)) {\r
1908             /*\r
1909              * Define the index and input properties last for better for/in loop\r
1910              * order (so they come after the elements).\r
1911              */\r
1912             obj.put("index", obj, new Integer(start + state.skipped));\r
1913             obj.put("input", obj, str);\r
1914         }\r
1915 \r
1916         if (res.lastMatch == null) {\r
1917             res.lastMatch = new SubString();\r
1918             res.leftContext = new SubString();\r
1919             res.rightContext = new SubString();\r
1920         }\r
1921         res.lastMatch.charArray = charArray;\r
1922         res.lastMatch.index = index;\r
1923         res.lastMatch.length = matchlen;\r
1924 \r
1925         res.leftContext.charArray = charArray;\r
1926         if (cx.getLanguageVersion() == Context.VERSION_1_2) {\r
1927             /*\r
1928              * JS1.2 emulated Perl4.0.1.8 (patch level 36) for global regexps used\r
1929              * in scalar contexts, and unintentionally for the string.match "list"\r
1930              * psuedo-context.  On "hi there bye", the following would result:\r
1931              *\r
1932              * Language     while(/ /g){print("$`");}   s/ /$`/g\r
1933              * perl4.036    "hi", "there"               "hihitherehi therebye"\r
1934              * perl5        "hi", "hi there"            "hihitherehi therebye"\r
1935              * js1.2        "hi", "there"               "hihitheretherebye"\r
1936              *\r
1937              * Insofar as JS1.2 always defined $` as "left context from the last\r
1938              * match" for global regexps, it was more consistent than perl4.\r
1939              */\r
1940             res.leftContext.index = start;\r
1941             res.leftContext.length = state.skipped;\r
1942         } else {\r
1943             /*\r
1944              * For JS1.3 and ECMAv2, emulate Perl5 exactly:\r
1945              *\r
1946              * js1.3        "hi", "hi there"            "hihitherehi therebye"\r
1947              */\r
1948             res.leftContext.index = 0;\r
1949             res.leftContext.length = start + state.skipped;\r
1950         }\r
1951 \r
1952         res.rightContext.charArray = charArray;\r
1953         res.rightContext.index = ep;\r
1954         res.rightContext.length = state.cpend - ep;\r
1955 \r
1956         return result;\r
1957     }\r
1958 \r
1959     public byte getFlags() {\r
1960         return flags;\r
1961     }\r
1962 \r
1963     private void reportError(String msg, String arg, CompilerState state) {\r
1964         Object[] args = { arg };\r
1965         throw NativeGlobal.constructError(\r
1966                                           state.cx, "SyntaxError",\r
1967                                           ScriptRuntime.getMessage(msg, args),\r
1968                                           state.scope);\r
1969     }\r
1970 \r
1971     protected int getIdDefaultAttributes(int id) {\r
1972         switch (id) {\r
1973             case Id_lastIndex:\r
1974                 return ScriptableObject.PERMANENT;\r
1975             case Id_source:     \r
1976             case Id_global:     \r
1977             case Id_ignoreCase: \r
1978             case Id_multiline:  \r
1979                 return ScriptableObject.PERMANENT | ScriptableObject.READONLY;\r
1980         }\r
1981         return super.getIdDefaultAttributes(id);\r
1982     }\r
1983     \r
1984     protected Object getIdValue(int id) {\r
1985         switch (id) {\r
1986             case Id_lastIndex:  return wrap_long(0xffffffffL & lastIndex);\r
1987             case Id_source:     return source;\r
1988             case Id_global:     return wrap_boolean((flags & GLOB) != 0);\r
1989             case Id_ignoreCase: return wrap_boolean((flags & FOLD) != 0);\r
1990             case Id_multiline:  return wrap_boolean((flags & MULTILINE) != 0);\r
1991         }\r
1992         return super.getIdValue(id);\r
1993     }\r
1994     \r
1995     protected void setIdValue(int id, Object value) {\r
1996         if (id == Id_lastIndex) {\r
1997             setLastIndex(ScriptRuntime.toInt32(value));\r
1998             return;\r
1999         }\r
2000         super.setIdValue(id, value);\r
2001     }\r
2002 \r
2003     void setLastIndex(int value) {\r
2004         lastIndex = value;\r
2005     }\r
2006     \r
2007     public int methodArity(int methodId) {\r
2008         if (prototypeFlag) {\r
2009             switch (methodId) {\r
2010                 case Id_compile:  return 1;\r
2011                 case Id_toString: return 0;\r
2012                 case Id_exec:     return 1;\r
2013                 case Id_test:     return 1;\r
2014                 case Id_prefix:   return 1;\r
2015             }\r
2016         }\r
2017         return super.methodArity(methodId);\r
2018     }\r
2019 \r
2020     public Object execMethod(int methodId, IdFunction f, Context cx,\r
2021                              Scriptable scope, Scriptable thisObj, \r
2022                              Object[] args)\r
2023         throws JavaScriptException\r
2024     {\r
2025         if (prototypeFlag) {\r
2026             switch (methodId) {\r
2027                 case Id_compile:\r
2028                     return realThis(thisObj, f, false).compile(cx, scope, args);\r
2029                 \r
2030                 case Id_toString:\r
2031                     return realThis(thisObj, f, true).toString();\r
2032                 \r
2033                 case Id_exec:\r
2034                     return realThis(thisObj, f, false).exec(cx, scope, args);\r
2035                 \r
2036                 case Id_test:\r
2037                     return realThis(thisObj, f, false).test(cx, scope, args);\r
2038                 \r
2039                 case Id_prefix:\r
2040                     return realThis(thisObj, f, false).prefix(cx, scope, args);\r
2041             }\r
2042         }\r
2043         return super.execMethod(methodId, f, cx, scope, thisObj, args);\r
2044     }\r
2045 \r
2046     private NativeRegExp realThis(Scriptable thisObj, IdFunction f, \r
2047                                   boolean readOnly)\r
2048     {\r
2049         while (!(thisObj instanceof NativeRegExp)) {\r
2050             thisObj = nextInstanceCheck(thisObj, f, readOnly);\r
2051         }\r
2052         return (NativeRegExp)thisObj;\r
2053     }\r
2054 \r
2055     protected String getIdName(int id) {\r
2056         switch (id) {\r
2057             case Id_lastIndex:  return "lastIndex";\r
2058             case Id_source:     return "source";\r
2059             case Id_global:     return "global";\r
2060             case Id_ignoreCase: return "ignoreCase";\r
2061             case Id_multiline:  return "multiline";\r
2062         }\r
2063         \r
2064         if (prototypeFlag) {\r
2065             switch (id) {\r
2066                 case Id_compile:  return "compile";\r
2067                 case Id_toString: return "toString";\r
2068                 case Id_exec:     return "exec";\r
2069                 case Id_test:     return "test";\r
2070                 case Id_prefix:   return "prefix";\r
2071             }\r
2072         }\r
2073         return null;\r
2074     }\r
2075 \r
2076     protected int maxInstanceId() { return MAX_INSTANCE_ID; }\r
2077 \r
2078 // #string_id_map#\r
2079 \r
2080     private static final int\r
2081         Id_lastIndex    = 1,\r
2082         Id_source       = 2,\r
2083         Id_global       = 3,\r
2084         Id_ignoreCase   = 4,\r
2085         Id_multiline    = 5,\r
2086         \r
2087         MAX_INSTANCE_ID = 5;\r
2088 \r
2089     protected int mapNameToId(String s) {\r
2090         int id;\r
2091 // #generated# Last update: 2001-05-24 12:01:22 GMT+02:00\r
2092         L0: { id = 0; String X = null; int c;\r
2093             int s_length = s.length();\r
2094             if (s_length==6) {\r
2095                 c=s.charAt(0);\r
2096                 if (c=='g') { X="global";id=Id_global; }\r
2097                 else if (c=='s') { X="source";id=Id_source; }\r
2098             }\r
2099             else if (s_length==9) {\r
2100                 c=s.charAt(0);\r
2101                 if (c=='l') { X="lastIndex";id=Id_lastIndex; }\r
2102                 else if (c=='m') { X="multiline";id=Id_multiline; }\r
2103             }\r
2104             else if (s_length==10) { X="ignoreCase";id=Id_ignoreCase; }\r
2105             if (X!=null && X!=s && !X.equals(s)) id = 0;\r
2106         }\r
2107 // #/generated#\r
2108 // #/string_id_map#\r
2109 \r
2110         if (id != 0 || !prototypeFlag) { return id; }\r
2111 \r
2112 // #string_id_map#\r
2113 // #generated# Last update: 2001-05-24 12:01:22 GMT+02:00\r
2114         L0: { id = 0; String X = null; int c;\r
2115             L: switch (s.length()) {\r
2116             case 4: c=s.charAt(0);\r
2117                 if (c=='e') { X="exec";id=Id_exec; }\r
2118                 else if (c=='t') { X="test";id=Id_test; }\r
2119                 break L;\r
2120             case 6: X="prefix";id=Id_prefix; break L;\r
2121             case 7: X="compile";id=Id_compile; break L;\r
2122             case 8: X="toString";id=Id_toString; break L;\r
2123             }\r
2124             if (X!=null && X!=s && !X.equals(s)) id = 0;\r
2125         }\r
2126 // #/generated#\r
2127         return id;\r
2128     }\r
2129 \r
2130     private static final int\r
2131         Id_compile       = MAX_INSTANCE_ID + 1,\r
2132         Id_toString      = MAX_INSTANCE_ID + 2,\r
2133         Id_exec          = MAX_INSTANCE_ID + 3,\r
2134         Id_test          = MAX_INSTANCE_ID + 4,\r
2135         Id_prefix        = MAX_INSTANCE_ID + 5,\r
2136         \r
2137         MAX_PROTOTYPE_ID = MAX_INSTANCE_ID + 5;\r
2138 \r
2139 // #/string_id_map#\r
2140     private boolean prototypeFlag;\r
2141 \r
2142     private String source;      /* locked source string, sans // */\r
2143     private int lastIndex;      /* index after last match, for //g iterator */\r
2144     private int parenCount;     /* number of parenthesized submatches */\r
2145     private byte flags;         /* flags  */\r
2146     private byte[] program;     /* regular expression bytecode */\r
2147 \r
2148     RENode ren;\r
2149 }\r
2150 \r
2151 class CompilerState {\r
2152     CompilerState(String source, int flags, Context cx, Scriptable scope) {\r
2153         this.source = source.toCharArray();\r
2154         this.scope = scope;\r
2155         this.flags = flags;\r
2156         this.cx = cx;\r
2157     }\r
2158     Context     cx;\r
2159     Scriptable  scope;\r
2160     char[]      source;\r
2161     int         indexBegin;\r
2162     int         index;\r
2163     int         flags;\r
2164     int         parenCount;\r
2165     int         progLength;\r
2166     byte[]      prog;\r
2167 }\r
2168 \r
2169 \r
2170 class RENode {\r
2171     public static final int ANCHORED = 0x01;    /* anchored at the front */\r
2172     public static final int SINGLE   = 0x02;    /* matches a single char */\r
2173     public static final int NONEMPTY = 0x04;    /* does not match empty string */\r
2174     public static final int ISNEXT   = 0x08;    /* ren is next after at least one node */\r
2175     public static final int GOODNEXT = 0x10;    /* ren.next is a tree-like edge in the graph */\r
2176     public static final int ISJOIN   = 0x20;    /* ren is a join point in the graph */\r
2177     public static final int REALLOK  = 0x40;    /* REOP_FLAT owns tempPool space to realloc */\r
2178     public static final int MINIMAL  = 0x80;    /* un-greedy matching for ? * + {} */\r
2179 \r
2180     RENode(CompilerState state, byte op, Object kid) {\r
2181         this.op = op;\r
2182         this.kid = kid;\r
2183     }\r
2184     \r
2185     private void calcBMSize(char[] s, int index, int cp2, boolean fold) {\r
2186         char maxc = 0;\r
2187         while (index < cp2) {\r
2188             char c = s[index++];\r
2189             if (c == '\\') {\r
2190                 if (index + 5 <= cp2 && s[index] == 'u'\r
2191                     && NativeRegExp.isHex(s[index+1]) \r
2192                     && NativeRegExp.isHex(s[index+2])\r
2193                     && NativeRegExp.isHex(s[index+3]) \r
2194                     && NativeRegExp.isHex(s[index+4]))\r
2195                     {\r
2196                         int x = (((((NativeRegExp.unHex(s[index+0]) << 4) +\r
2197                                     NativeRegExp.unHex(s[index+1])) << 4) +\r
2198                                   NativeRegExp.unHex(s[index+2])) << 4) +\r
2199                             NativeRegExp.unHex(s[index+3]);\r
2200                         c = (char) x;\r
2201                         index += 5;\r
2202                     } else {\r
2203                         /*\r
2204                          * Octal and hex escapes can't be > 255.  Skip this\r
2205                          * backslash and let the loop pass over the remaining\r
2206                          * escape sequence as if it were text to match.\r
2207                          */\r
2208                         if (maxc < 255) maxc = 255;\r
2209                         continue;\r
2210                     }\r
2211             }\r
2212             if (fold) {\r
2213                 /*\r
2214                  * Don't assume that lowercase are above uppercase, or\r
2215                  * that c is either even when c has upper and lowercase\r
2216                  * versions.\r
2217                  */\r
2218                 char c2;\r
2219                 if ((c2 = Character.toUpperCase(c)) > maxc)\r
2220                     maxc = c2;\r
2221                 if ((c2 = Character.toLowerCase(c2)) > maxc)\r
2222                     maxc = c2;\r
2223             }\r
2224             if (c > maxc)\r
2225                 maxc = c;\r
2226         }\r
2227         bmsize = (short)((maxc + NativeRegExp.JS_BITS_PER_BYTE) \r
2228                          / NativeRegExp.JS_BITS_PER_BYTE);\r
2229     }\r
2230     \r
2231     private void matchBit(char c, int fill) {\r
2232         int i = (c) >> 3;\r
2233         byte b = (byte) (c & 7);\r
2234         b = (byte) (1 << b);\r
2235         if (fill != 0)\r
2236             bitmap[i] &= ~b;\r
2237         else\r
2238             bitmap[i] |= b;\r
2239     }\r
2240 \r
2241     private void checkRange(char lastc, int fill) {\r
2242         matchBit(lastc, fill);\r
2243         matchBit('-', fill);\r
2244     }\r
2245 \r
2246     void buildBitmap(MatchState state, char[] s, boolean fold) {\r
2247         int index = ((Integer) kid).intValue();\r
2248         int end = kid2;\r
2249         byte fill = 0;\r
2250         int i,n,ocp;\r
2251         \r
2252         boolean not = false;\r
2253         kid2 = 0;\r
2254         if (s[index] == '^') {\r
2255             not = true;\r
2256             kid2 = -1;\r
2257             index++;\r
2258         }\r
2259         \r
2260         calcBMSize(s, index, end, fold);\r
2261         bitmap = new byte[bmsize];\r
2262         if (not) {\r
2263             fill = (byte)0xff;\r
2264             for (i = 0; i < bmsize; i++)\r
2265                 bitmap[i] = (byte)0xff;\r
2266             bitmap[0] = (byte)0xfe;\r
2267         }\r
2268         int nchars = bmsize * NativeRegExp.JS_BITS_PER_BYTE;\r
2269         char lastc = (char)nchars;\r
2270         boolean inrange = false;\r
2271         \r
2272         while (index < end) {\r
2273             char c = s[index++];\r
2274             if (c == '\\') {\r
2275                 c = s[index++];\r
2276                 switch (c) {\r
2277                 case 'b':\r
2278                 case 'f':\r
2279                 case 'n':\r
2280                 case 'r':\r
2281                 case 't':\r
2282                 case 'v':\r
2283                     c = NativeRegExp.getEscape(c);\r
2284                     break;\r
2285 \r
2286                 case 'd':\r
2287                     if (inrange)\r
2288                         checkRange(lastc, fill);\r
2289                     lastc = (char) nchars;\r
2290                     for (c = '0'; c <= '9'; c++)\r
2291                         matchBit(c, fill);\r
2292                     continue;\r
2293 \r
2294                 case 'D':\r
2295                     if (inrange)\r
2296                         checkRange(lastc, fill);\r
2297                     lastc = (char) nchars;\r
2298                     for (c = 0; c < '0'; c++)\r
2299                         matchBit(c, fill);\r
2300                     for (c = '9' + 1; c < nchars; c++)\r
2301                         matchBit(c, fill);\r
2302                     continue;\r
2303 \r
2304                 case 'w':\r
2305                     if (inrange)\r
2306                         checkRange(lastc, fill);\r
2307                     lastc = (char) nchars;\r
2308                     for (c = 0; c < nchars; c++)\r
2309                         if (NativeRegExp.isWord(c))\r
2310                             matchBit(c, fill);\r
2311                     continue;\r
2312 \r
2313                 case 'W':\r
2314                     if (inrange)\r
2315                         checkRange(lastc, fill);\r
2316                     lastc = (char) nchars;\r
2317                     for (c = 0; c < nchars; c++)\r
2318                         if (!NativeRegExp.isWord(c))\r
2319                             matchBit(c, fill);\r
2320                     continue;\r
2321 \r
2322                 case 's':\r
2323                     if (inrange)\r
2324                         checkRange(lastc, fill);\r
2325                     lastc = (char) nchars;\r
2326                     for (c = 0; c < nchars; c++)\r
2327                         if (Character.isWhitespace(c))\r
2328                             matchBit(c, fill);\r
2329                     continue;\r
2330 \r
2331                 case 'S':\r
2332                     if (inrange)\r
2333                         checkRange(lastc, fill);\r
2334                     lastc = (char) nchars;\r
2335                     for (c = 0; c < nchars; c++)\r
2336                         if (!Character.isWhitespace(c))\r
2337                             matchBit(c, fill);\r
2338                     continue;\r
2339 \r
2340                 case '0':\r
2341                 case '1':\r
2342                 case '2':\r
2343                 case '3':\r
2344                 case '4':\r
2345                 case '5':\r
2346                 case '6':\r
2347                 case '7':\r
2348                     n = NativeRegExp.unDigit(c);\r
2349                     ocp = index - 2;\r
2350                     c = s[index];\r
2351                     if ('0' <= c && c <= '7') {\r
2352                         index++;\r
2353                         n = 8 * n + NativeRegExp.unDigit(c);\r
2354 \r
2355                         c = s[index];\r
2356                         if ('0' <= c && c <= '7') {\r
2357                             index++;\r
2358                             i = 8 * n + NativeRegExp.unDigit(c);\r
2359                             if (i <= 0377)\r
2360                                 n = i;\r
2361                             else\r
2362                                 index--;\r
2363                         }\r
2364                     }\r
2365                     c = (char) n;\r
2366                     break;\r
2367 \r
2368                 case 'x':\r
2369                     ocp = index;\r
2370                     if (index < s.length &&\r
2371                         NativeRegExp.isHex(c = s[index++]))\r
2372                         {\r
2373                             n = NativeRegExp.unHex(c);\r
2374                             if (index < s.length &&\r
2375                                 NativeRegExp.isHex(c = s[index++]))\r
2376                                 {\r
2377                                     n <<= 4;\r
2378                                     n += NativeRegExp.unHex(c);\r
2379                                 }\r
2380                         } else {\r
2381                             index = ocp;        /* \xZZ is xZZ (Perl does \0ZZ!) */\r
2382                             n = 'x';\r
2383                         }\r
2384                     c = (char) n;\r
2385                     break;\r
2386 \r
2387                 case 'u':\r
2388                     if (s.length > index+3\r
2389                         && NativeRegExp.isHex(s[index+0])\r
2390                         && NativeRegExp.isHex(s[index+1]) \r
2391                         && NativeRegExp.isHex(s[index+2])\r
2392                         && NativeRegExp.isHex(s[index+3])) {\r
2393                         n = (((((NativeRegExp.unHex(s[index+0]) << 4) +\r
2394                                 NativeRegExp.unHex(s[index+1])) << 4) +\r
2395                               NativeRegExp.unHex(s[index+2])) << 4) +\r
2396                             NativeRegExp.unHex(s[index+3]);\r
2397                         c = (char) n;\r
2398                         index += 4;\r
2399                     }\r
2400                     break;\r
2401 \r
2402                 case 'c':\r
2403                     c = s[index++];\r
2404                     c = Character.toUpperCase(c);\r
2405                     c = (char) (c ^ 64); // JS_TOCTRL\r
2406                     break;\r
2407                 }\r
2408             }\r
2409 \r
2410             if (inrange) {\r
2411                 if (lastc > c) {\r
2412                     throw NativeGlobal.constructError(\r
2413                                                       Context.getCurrentContext(), "RangeError",\r
2414                                                       ScriptRuntime.getMessage(\r
2415                                                                                "msg.bad.range", null),\r
2416                                                       state.scope);\r
2417                 }\r
2418                 inrange = false;\r
2419             } else {\r
2420                 // Set lastc so we match just c's bit in the for loop.\r
2421                 lastc = c;\r
2422 \r
2423                 // [balance:\r
2424                 if (index + 1 < end && s[index] == '-' &&\r
2425                     s[index+1] != ']')\r
2426                     {\r
2427                         index++;\r
2428                         inrange = true;\r
2429                         continue;\r
2430                     }\r
2431             }\r
2432 \r
2433             // Match characters in the range [lastc, c].\r
2434             for (; lastc <= c; lastc++) {\r
2435                 matchBit(lastc, fill);\r
2436                 if (fold) {\r
2437                     /*\r
2438                      * Must do both upper and lower for Turkish dotless i,\r
2439                      * Georgian, etc.\r
2440                      */\r
2441                     char foldc = Character.toUpperCase(lastc);\r
2442                     matchBit(foldc, fill);\r
2443                     foldc = Character.toLowerCase(foldc);\r
2444                     matchBit(foldc, fill);\r
2445                 }\r
2446             }\r
2447             lastc = c;\r
2448         }\r
2449     }\r
2450     byte            op;         /* packed r.e. op bytecode */\r
2451     byte            flags;      /* flags, see below */\r
2452     short           offset;     /* bytecode offset */\r
2453     RENode          next;       /* next in concatenation order */\r
2454     Object          kid;        /* first operand */\r
2455     int             kid2;       /* second operand */\r
2456     int             num;        /* could be a number */\r
2457     char            chr;        /* or a char */\r
2458     short           min,max;    /* or a range */\r
2459     short           kidlen;     /* length of string at kid, in chars */\r
2460     short           bmsize;     /* bitmap size, based on max char code */\r
2461     char[]          s;          /* if null, use state.source */\r
2462     byte[]          bitmap;     /* cclass bitmap */\r
2463 }\r
2464 \r
2465 \r
2466 class MatchState {\r
2467     boolean     inputExhausted;         /* did we run out of input chars ? */\r
2468     boolean     anchoring;              /* true if multiline anchoring ^/$ */\r
2469     int         pcend;                  /* pc limit (fencepost) */\r
2470     int         cpbegin, cpend;         /* cp base address and limit */\r
2471     int         start;                  /* offset from cpbegin to start at */\r
2472     int         skipped;                /* chars skipped anchoring this r.e. */\r
2473     byte        flags;                  /* pennants  */\r
2474     int         parenCount;             /* number of paren substring matches */\r
2475     SubString[] maybeParens;            /* possible paren substring pointers */\r
2476     SubString[] parens;                 /* certain paren substring matches */\r
2477     Scriptable  scope;\r
2478     char[]              input;\r
2479 \r
2480     public int noMoreInput() {\r
2481         inputExhausted = true;\r
2482         /*\r
2483         try {\r
2484             throw new Exception();\r
2485         }\r
2486         catch (Exception e) {\r
2487             e.printStackTrace();\r
2488         }\r
2489         */\r
2490         return -1;\r
2491     }\r
2492 }\r
2493 \r
2494 class GreedyState {\r
2495     MatchState state;\r
2496     RENode kid;\r
2497     RENode next;\r
2498     RENode stop;\r
2499     int kidCount;\r
2500     int maxKid;\r
2501 }\r
2502 \r