1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.objects;
  27 
  28 import static jdk.nashorn.internal.runtime.ECMAErrors.typeError;
  29 import static jdk.nashorn.internal.runtime.ScriptRuntime.UNDEFINED;
  30 
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.List;
  34 
  35 import jdk.nashorn.internal.objects.annotations.Attribute;
  36 import jdk.nashorn.internal.objects.annotations.Constructor;
  37 import jdk.nashorn.internal.objects.annotations.Function;
  38 import jdk.nashorn.internal.objects.annotations.Getter;
  39 import jdk.nashorn.internal.objects.annotations.Property;
  40 import jdk.nashorn.internal.objects.annotations.ScriptClass;
  41 import jdk.nashorn.internal.objects.annotations.SpecializedConstructor;
  42 import jdk.nashorn.internal.objects.annotations.Where;
  43 import jdk.nashorn.internal.runtime.BitVector;
  44 import jdk.nashorn.internal.runtime.JSType;
  45 import jdk.nashorn.internal.runtime.ParserException;
  46 import jdk.nashorn.internal.runtime.regexp.RegExp;
  47 import jdk.nashorn.internal.runtime.regexp.RegExpFactory;
  48 import jdk.nashorn.internal.runtime.regexp.RegExpResult;
  49 import jdk.nashorn.internal.runtime.regexp.RegExpMatcher;
  50 import jdk.nashorn.internal.runtime.ScriptFunction;
  51 import jdk.nashorn.internal.runtime.ScriptObject;
  52 import jdk.nashorn.internal.runtime.ScriptRuntime;
  53 
  54 /**
  55  * ECMA 15.10 RegExp Objects.
  56  */
  57 @ScriptClass("RegExp")
  58 public final class NativeRegExp extends ScriptObject {
  59     /** ECMA 15.10.7.5 lastIndex property */
  60     @Property(attributes = Attribute.NOT_ENUMERABLE | Attribute.NOT_CONFIGURABLE)
  61     public Object lastIndex;
  62 
  63     /** Compiled regexp */
  64     private RegExp regexp;
  65 
  66     // Reference to global object needed to support static RegExp properties
  67     private Global globalObject;
  68 
  69     NativeRegExp(final String input, final String flagString) {
  70         try {
  71             this.regexp = RegExpFactory.create(input, flagString);
  72         } catch (final ParserException e) {
  73             // translate it as SyntaxError object and throw it
  74             e.throwAsEcmaException();
  75             throw new AssertionError(); //guard against null warnings below
  76         }
  77 
  78         this.setLastIndex(0);
  79         init();
  80     }
  81 
  82     NativeRegExp(final String string) {
  83         this(string, "");
  84     }
  85 
  86     NativeRegExp(final NativeRegExp regExp) {
  87         this.lastIndex  = regExp.getLastIndexObject();
  88         this.regexp      = regExp.getRegExp();
  89         init();
  90     }
  91 
  92     @Override
  93     public String getClassName() {
  94         return "RegExp";
  95     }
  96 
  97     /**
  98      * ECMA 15.10.4
  99      *
 100      * Constructor
 101      *
 102      * @param isNew is the new operator used for instantiating this regexp
 103      * @param self  self reference
 104      * @param args  arguments (optional: pattern and flags)
 105      * @return new NativeRegExp
 106      */
 107     @Constructor(arity = 2)
 108     public static Object constructor(final boolean isNew, final Object self, final Object... args) {
 109         if (args.length > 1) {
 110             return newRegExp(args[0], args[1]);
 111         } else if (args.length > 0) {
 112             return newRegExp(args[0], UNDEFINED);
 113         }
 114 
 115         return newRegExp(UNDEFINED, UNDEFINED);
 116     }
 117 
 118     /**
 119      * ECMA 15.10.4
 120      *
 121      * Constructor - specialized version, no args, empty regexp
 122      *
 123      * @param isNew is the new operator used for instantiating this regexp
 124      * @param self  self reference
 125      * @return new NativeRegExp
 126      */
 127     @SpecializedConstructor
 128     public static Object constructor(final boolean isNew, final Object self) {
 129         return new NativeRegExp("", "");
 130     }
 131 
 132     /**
 133      * ECMA 15.10.4
 134      *
 135      * Constructor - specialized version, pattern, no flags
 136      *
 137      * @param isNew is the new operator used for instantiating this regexp
 138      * @param self  self reference
 139      * @param pattern pattern
 140      * @return new NativeRegExp
 141      */
 142     @SpecializedConstructor
 143     public static Object constructor(final boolean isNew, final Object self, final Object pattern) {
 144         return newRegExp(pattern, UNDEFINED);
 145     }
 146 
 147     /**
 148      * ECMA 15.10.4
 149      *
 150      * Constructor - specialized version, pattern and flags
 151      *
 152      * @param isNew is the new operator used for instantiating this regexp
 153      * @param self  self reference
 154      * @param pattern pattern
 155      * @param flags  flags
 156      * @return new NativeRegExp
 157      */
 158     @SpecializedConstructor
 159     public static Object constructor(final boolean isNew, final Object self, final Object pattern, final Object flags) {
 160         return newRegExp(pattern, flags);
 161     }
 162 
 163     /**
 164      * External constructor used in generated code, which explains the public access
 165      *
 166      * @param regexp regexp
 167      * @param flags  flags
 168      * @return new NativeRegExp
 169      */
 170     public static NativeRegExp newRegExp(final Object regexp, final Object flags) {
 171         String  patternString = "";
 172         String  flagString    = "";
 173         boolean flagsDefined  = false;
 174 
 175         if (flags != UNDEFINED) {
 176             flagsDefined = true;
 177             flagString = JSType.toString(flags);
 178         }
 179 
 180         if (regexp != UNDEFINED) {
 181             if (regexp instanceof NativeRegExp) {
 182                 if (!flagsDefined) {
 183                     return (NativeRegExp)regexp; // 15.10.3.1 - undefined flags and regexp as
 184                 }
 185                 throw typeError("regex.cant.supply.flags");
 186             }
 187             patternString = JSType.toString(regexp);
 188         }
 189 
 190         return new NativeRegExp(patternString, flagString);
 191     }
 192 
 193     /**
 194      * Build a regexp that matches {@code string} as-is. All meta-characters will be escaped.
 195      *
 196      * @param string pattern string
 197      * @return flat regexp
 198      */
 199     static NativeRegExp flatRegExp(String string) {
 200         // escape special characters
 201         StringBuilder sb = null;
 202         final int length = string.length();
 203 
 204         for (int i = 0; i < length; i++) {
 205             final char c = string.charAt(i);
 206             switch (c) {
 207                 case '^':
 208                 case '$':
 209                 case '\\':
 210                 case '.':
 211                 case '*':
 212                 case '+':
 213                 case '?':
 214                 case '(':
 215                 case ')':
 216                 case '[':
 217                 case '{':
 218                 case '|':
 219                     if (sb == null) {
 220                         sb = new StringBuilder(length * 2);
 221                         sb.append(string, 0, i);
 222                     }
 223                     sb.append('\\');
 224                     sb.append(c);
 225                     break;
 226                 default:
 227                     if (sb != null) {
 228                         sb.append(c);
 229                     }
 230                     break;
 231             }
 232         }
 233         return new NativeRegExp(sb == null ? string : sb.toString(), "");
 234     }
 235 
 236     private String getFlagString() {
 237         final StringBuilder sb = new StringBuilder(3);
 238 
 239         if (regexp.isGlobal()) {
 240             sb.append('g');
 241         }
 242         if (regexp.isIgnoreCase()) {
 243             sb.append('i');
 244         }
 245         if (regexp.isMultiline()) {
 246             sb.append('m');
 247         }
 248 
 249         return sb.toString();
 250     }
 251 
 252     @Override
 253     public String safeToString() {
 254         return "[RegExp " + toString() + "]";
 255     }
 256 
 257     @Override
 258     public String toString() {
 259         return "/" + regexp.getSource() + "/" + getFlagString();
 260     }
 261 
 262     /**
 263      * Nashorn extension: RegExp.prototype.compile - everybody implements this!
 264      *
 265      * @param self    self reference
 266      * @param pattern pattern
 267      * @param flags   flags
 268      * @return new NativeRegExp
 269      */
 270     @Function(attributes = Attribute.NOT_ENUMERABLE)
 271     public static Object compile(final Object self, final Object pattern, final Object flags) {
 272         final NativeRegExp regExp   = checkRegExp(self);
 273         final NativeRegExp compiled = newRegExp(pattern, flags);
 274         // copy over regexp to 'self'
 275         regExp.setRegExp(compiled.getRegExp());
 276 
 277         // Some implementations return undefined. Some return 'self'. Since return
 278         // value is most likely be ignored, we can play safe and return 'self'.
 279         return regExp;
 280     }
 281 
 282     /**
 283      * ECMA 15.10.6.2 RegExp.prototype.exec(string)
 284      *
 285      * @param self   self reference
 286      * @param string string to match against regexp
 287      * @return array containing the matches or {@code null} if no match
 288      */
 289     @Function(attributes = Attribute.NOT_ENUMERABLE)
 290     public static Object exec(final Object self, final Object string) {
 291         return checkRegExp(self).exec(JSType.toString(string));
 292     }
 293 
 294     /**
 295      * ECMA 15.10.6.3 RegExp.prototype.test(string)
 296      *
 297      * @param self   self reference
 298      * @param string string to test for matches against regexp
 299      * @return true if matches found, false otherwise
 300      */
 301     @Function(attributes = Attribute.NOT_ENUMERABLE)
 302     public static Object test(final Object self, final Object string) {
 303         return checkRegExp(self).test(JSType.toString(string));
 304     }
 305 
 306     /**
 307      * ECMA 15.10.6.4 RegExp.prototype.toString()
 308      *
 309      * @param self self reference
 310      * @return string version of regexp
 311      */
 312     @Function(attributes = Attribute.NOT_ENUMERABLE)
 313     public static Object toString(final Object self) {
 314         return checkRegExp(self).toString();
 315     }
 316 
 317     /**
 318      * ECMA 15.10.7.1 source
 319      *
 320      * @param self self reference
 321      * @return the input string for the regexp
 322      */
 323     @Getter(attributes = Attribute.NON_ENUMERABLE_CONSTANT)
 324     public static Object source(final Object self) {
 325         return checkRegExp(self).getRegExp().getSource();
 326     }
 327 
 328     /**
 329      * ECMA 15.10.7.2 global
 330      *
 331      * @param self self reference
 332      * @return true if this regexp is flagged global, false otherwise
 333      */
 334     @Getter(attributes = Attribute.NON_ENUMERABLE_CONSTANT)
 335     public static Object global(final Object self) {
 336         return checkRegExp(self).getRegExp().isGlobal();
 337     }
 338 
 339     /**
 340      * ECMA 15.10.7.3 ignoreCase
 341      *
 342      * @param self self reference
 343      * @return true if this regexp if flagged to ignore case, false otherwise
 344      */
 345     @Getter(attributes = Attribute.NON_ENUMERABLE_CONSTANT)
 346     public static Object ignoreCase(final Object self) {
 347         return checkRegExp(self).getRegExp().isIgnoreCase();
 348     }
 349 
 350     /**
 351      * ECMA 15.10.7.4 multiline
 352      *
 353      * @param self self reference
 354      * @return true if this regexp is flagged to be multiline, false otherwise
 355      */
 356     @Getter(attributes = Attribute.NON_ENUMERABLE_CONSTANT)
 357     public static Object multiline(final Object self) {
 358         return checkRegExp(self).getRegExp().isMultiline();
 359     }
 360 
 361     /**
 362      * Getter for non-standard RegExp.input property.
 363      * @param self self object
 364      * @return last regexp input
 365      */
 366     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "input")
 367     public static Object getLastInput(Object self) {
 368         final RegExpResult match = Global.instance().getLastRegExpResult();
 369         return match == null ? "" : match.getInput();
 370     }
 371 
 372     /**
 373      * Getter for non-standard RegExp.multiline property.
 374      * @param self self object
 375      * @return last regexp input
 376      */
 377     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "multiline")
 378     public static Object getLastMultiline(Object self) {
 379         return false; // doesn't ever seem to become true and isn't documented anyhwere
 380     }
 381 
 382     /**
 383      * Getter for non-standard RegExp.lastMatch property.
 384      * @param self self object
 385      * @return last regexp input
 386      */
 387     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "lastMatch")
 388     public static Object getLastMatch(Object self) {
 389         final RegExpResult match = Global.instance().getLastRegExpResult();
 390         return match == null ? "" : match.getGroup(0);
 391     }
 392 
 393     /**
 394      * Getter for non-standard RegExp.lastParen property.
 395      * @param self self object
 396      * @return last regexp input
 397      */
 398     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "lastParen")
 399     public static Object getLastParen(Object self) {
 400         final RegExpResult match = Global.instance().getLastRegExpResult();
 401         return match == null ? "" : match.getLastParen();
 402     }
 403 
 404     /**
 405      * Getter for non-standard RegExp.leftContext property.
 406      * @param self self object
 407      * @return last regexp input
 408      */
 409     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "leftContext")
 410     public static Object getLeftContext(Object self) {
 411         final RegExpResult match = Global.instance().getLastRegExpResult();
 412         return match == null ? "" : match.getInput().substring(0, match.getIndex());
 413     }
 414 
 415     /**
 416      * Getter for non-standard RegExp.rightContext property.
 417      * @param self self object
 418      * @return last regexp input
 419      */
 420     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "rightContext")
 421     public static Object getRightContext(Object self) {
 422         final RegExpResult match = Global.instance().getLastRegExpResult();
 423         return match == null ? "" : match.getInput().substring(match.getIndex() + match.length());
 424     }
 425 
 426     /**
 427      * Getter for non-standard RegExp.$1 property.
 428      * @param self self object
 429      * @return last regexp input
 430      */
 431     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$1")
 432     public static Object getGroup1(Object self) {
 433         final RegExpResult match = Global.instance().getLastRegExpResult();
 434         return match == null ? "" : match.getGroup(1);
 435     }
 436 
 437     /**
 438      * Getter for non-standard RegExp.$2 property.
 439      * @param self self object
 440      * @return last regexp input
 441      */
 442     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$2")
 443     public static Object getGroup2(Object self) {
 444         final RegExpResult match = Global.instance().getLastRegExpResult();
 445         return match == null ? "" : match.getGroup(2);
 446     }
 447 
 448     /**
 449      * Getter for non-standard RegExp.$3 property.
 450      * @param self self object
 451      * @return last regexp input
 452      */
 453     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$3")
 454     public static Object getGroup3(Object self) {
 455         final RegExpResult match = Global.instance().getLastRegExpResult();
 456         return match == null ? "" : match.getGroup(3);
 457     }
 458 
 459     /**
 460      * Getter for non-standard RegExp.$4 property.
 461      * @param self self object
 462      * @return last regexp input
 463      */
 464     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$4")
 465     public static Object getGroup4(Object self) {
 466         final RegExpResult match = Global.instance().getLastRegExpResult();
 467         return match == null ? "" : match.getGroup(4);
 468     }
 469 
 470     /**
 471      * Getter for non-standard RegExp.$5 property.
 472      * @param self self object
 473      * @return last regexp input
 474      */
 475     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$5")
 476     public static Object getGroup5(Object self) {
 477         final RegExpResult match = Global.instance().getLastRegExpResult();
 478         return match == null ? "" : match.getGroup(5);
 479     }
 480 
 481     /**
 482      * Getter for non-standard RegExp.$6 property.
 483      * @param self self object
 484      * @return last regexp input
 485      */
 486     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$6")
 487     public static Object getGroup6(Object self) {
 488         final RegExpResult match = Global.instance().getLastRegExpResult();
 489         return match == null ? "" : match.getGroup(6);
 490     }
 491 
 492     /**
 493      * Getter for non-standard RegExp.$7 property.
 494      * @param self self object
 495      * @return last regexp input
 496      */
 497     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$7")
 498     public static Object getGroup7(Object self) {
 499         final RegExpResult match = Global.instance().getLastRegExpResult();
 500         return match == null ? "" : match.getGroup(7);
 501     }
 502 
 503     /**
 504      * Getter for non-standard RegExp.$8 property.
 505      * @param self self object
 506      * @return last regexp input
 507      */
 508     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$8")
 509     public static Object getGroup8(Object self) {
 510         final RegExpResult match = Global.instance().getLastRegExpResult();
 511         return match == null ? "" : match.getGroup(8);
 512     }
 513 
 514     /**
 515      * Getter for non-standard RegExp.$9 property.
 516      * @param self self object
 517      * @return last regexp input
 518      */
 519     @Getter(where = Where.CONSTRUCTOR, attributes = Attribute.CONSTANT, name = "$9")
 520     public static Object getGroup9(Object self) {
 521         final RegExpResult match = Global.instance().getLastRegExpResult();
 522         return match == null ? "" : match.getGroup(9);
 523     }
 524 
 525     private RegExpResult execInner(final String string) {
 526         final boolean isGlobal = regexp.isGlobal();
 527         int start = getLastIndex();
 528         if (!isGlobal) {
 529             start = 0;
 530         }
 531 
 532         if (start < 0 || start > string.length()) {
 533             if (isGlobal) {
 534                 setLastIndex(0);
 535             }
 536             return null;
 537         }
 538 
 539         final RegExpMatcher matcher = regexp.match(string);
 540         if (matcher == null || !matcher.search(start)) {
 541             if (isGlobal) {
 542                 setLastIndex(0);
 543             }
 544             return null;
 545         }
 546 
 547         if (isGlobal) {
 548             setLastIndex(matcher.end());
 549         }
 550 
 551         final RegExpResult match = new RegExpResult(string, matcher.start(), groups(matcher));
 552         globalObject.setLastRegExpResult(match);
 553         return match;
 554     }
 555 
 556     // String.prototype.split method ignores the global flag and should not update lastIndex property.
 557     private RegExpResult execSplit(final String string, int start) {
 558         if (start < 0 || start > string.length()) {
 559             return null;
 560         }
 561 
 562         final RegExpMatcher matcher = regexp.match(string);
 563         if (matcher == null || !matcher.search(start)) {
 564             return null;
 565         }
 566 
 567         final RegExpResult match = new RegExpResult(string, matcher.start(), groups(matcher));
 568         globalObject.setLastRegExpResult(match);
 569         return match;
 570     }
 571 
 572     /**
 573      * Convert java.util.regex.Matcher groups to JavaScript groups.
 574      * That is, replace null and groups that didn't match with undefined.
 575      */
 576     private Object[] groups(final RegExpMatcher matcher) {
 577         final int groupCount = matcher.groupCount();
 578         final Object[] groups = new Object[groupCount + 1];
 579         final BitVector groupsInNegativeLookahead  = regexp.getGroupsInNegativeLookahead();
 580 
 581         for (int i = 0, lastGroupStart = matcher.start(); i <= groupCount; i++) {
 582             final int groupStart = matcher.start(i);
 583             if (lastGroupStart > groupStart
 584                     || (groupsInNegativeLookahead != null && groupsInNegativeLookahead.isSet(i))) {
 585                 // (1) ECMA 15.10.2.5 NOTE 3: need to clear Atom's captures each time Atom is repeated.
 586                 // (2) ECMA 15.10.2.8 NOTE 3: Backreferences to captures in (?!Disjunction) from elsewhere
 587                 // in the pattern always return undefined because the negative lookahead must fail.
 588                 groups[i] = UNDEFINED;
 589                 continue;
 590             }
 591             final String group = matcher.group(i);
 592             groups[i] = group == null ? UNDEFINED : group;
 593             lastGroupStart = groupStart;
 594         }
 595         return groups;
 596     }
 597 
 598     /**
 599      * Executes a search for a match within a string based on a regular
 600      * expression. It returns an array of information or null if no match is
 601      * found.
 602      *
 603      * @param string String to match.
 604      * @return NativeArray of matches, string or null.
 605      */
 606     public Object exec(final String string) {
 607         final RegExpResult match = execInner(string);
 608 
 609         if (match == null) {
 610             return null;
 611         }
 612 
 613         return new NativeRegExpExecResult(match);
 614     }
 615 
 616     /**
 617      * Executes a search for a match within a string based on a regular
 618      * expression.
 619      *
 620      * @param string String to match.
 621      * @return True if a match is found.
 622      */
 623     public Object test(final String string) {
 624         return execInner(string) != null;
 625     }
 626 
 627     /**
 628      * Searches and replaces the regular expression portion (match) with the
 629      * replaced text instead. For the "replacement text" parameter, you can use
 630      * the keywords $1 to $2 to replace the original text with values from
 631      * sub-patterns defined within the main pattern.
 632      *
 633      * @param string String to match.
 634      * @param replacement Replacement string.
 635      * @return String with substitutions.
 636      */
 637     Object replace(final String string, final String replacement, final ScriptFunction function) {
 638         final RegExpMatcher matcher = regexp.match(string);
 639 
 640         if (matcher == null) {
 641             return string;
 642         }
 643 
 644         /*
 645          * $$ -> $
 646          * $& -> the matched substring
 647          * $` -> the portion of string that preceeds matched substring
 648          * $' -> the portion of string that follows the matched substring
 649          * $n -> the nth capture, where n is [1-9] and $n is NOT followed by a decimal digit
 650          * $nn -> the nnth capture, where nn is a two digit decimal number [01-99].
 651          */
 652         String replace = replacement;
 653 
 654         if (!regexp.isGlobal()) {
 655             if (!matcher.search(0)) {
 656                 return string;
 657             }
 658 
 659             final StringBuilder sb = new StringBuilder();
 660             if (function != null) {
 661                 replace = callReplaceValue(function, matcher, string);
 662             }
 663             appendReplacement(matcher, string, replace, sb, 0);
 664             sb.append(string, matcher.end(), string.length());
 665             return sb.toString();
 666         }
 667 
 668         setLastIndex(0);
 669 
 670         if (!matcher.search(0)) {
 671             return string;
 672         }
 673 
 674         int thisIndex = 0;
 675         int previousLastIndex = 0;
 676         final StringBuilder sb = new StringBuilder();
 677 
 678         do {
 679             if (function != null) {
 680                 replace = callReplaceValue(function, matcher, string);
 681             }
 682 
 683             appendReplacement(matcher, string, replace, sb, thisIndex);
 684 
 685             // ECMA 15.5.4.10 String.prototype.match(regexp)
 686             thisIndex = matcher.end();
 687             if (thisIndex == previousLastIndex) {
 688                 setLastIndex(thisIndex + 1);
 689                 previousLastIndex = thisIndex + 1;
 690             } else {
 691                 previousLastIndex = thisIndex;
 692             }
 693         } while (previousLastIndex <= string.length() && matcher.search(previousLastIndex));
 694 
 695         sb.append(string, thisIndex, string.length());
 696 
 697         return sb.toString();
 698     }
 699 
 700     private void appendReplacement(final RegExpMatcher matcher, final String text, final String replacement, final StringBuilder sb, final int lastAppendPosition) {
 701         // Process substitution string to replace group references with groups
 702         int cursor = 0;
 703         final StringBuilder result = new StringBuilder();
 704         Object[] groups = null;
 705 
 706         while (cursor < replacement.length()) {
 707             char nextChar = replacement.charAt(cursor);
 708             if (nextChar == '$') {
 709                 // Skip past $
 710                 cursor++;
 711                 nextChar = replacement.charAt(cursor);
 712                 final int firstDigit = nextChar - '0';
 713 
 714                 if (firstDigit >= 0 && firstDigit <= 9 && firstDigit <= matcher.groupCount()) {
 715                     // $0 is not supported, but $01 is. implementation-defined: if n>m, ignore second digit.
 716                     int refNum = firstDigit;
 717                     cursor++;
 718                     if (cursor < replacement.length() && firstDigit < matcher.groupCount()) {
 719                         final int secondDigit = replacement.charAt(cursor) - '0';
 720                         if ((secondDigit >= 0) && (secondDigit <= 9)) {
 721                             final int newRefNum = (firstDigit * 10) + secondDigit;
 722                             if (newRefNum <= matcher.groupCount() && newRefNum > 0) {
 723                                 // $nn ($01-$99)
 724                                 refNum = newRefNum;
 725                                 cursor++;
 726                             }
 727                         }
 728                     }
 729                     if (refNum > 0) {
 730                         if (groups == null) {
 731                             groups = groups(matcher);
 732                         }
 733                         // Append group if matched.
 734                         if (groups[refNum] != UNDEFINED) {
 735                             result.append((String) groups[refNum]);
 736                         }
 737                     } else { // $0. ignore.
 738                         assert refNum == 0;
 739                         result.append("$0");
 740                     }
 741                 } else if (nextChar == '$') {
 742                     result.append('$');
 743                     cursor++;
 744                 } else if (nextChar == '&') {
 745                     result.append(matcher.group());
 746                     cursor++;
 747                 } else if (nextChar == '`') {
 748                     result.append(text.substring(0, matcher.start()));
 749                     cursor++;
 750                 } else if (nextChar == '\'') {
 751                     result.append(text.substring(matcher.end()));
 752                     cursor++;
 753                 } else {
 754                     // unknown substitution or $n with n>m. skip.
 755                     result.append('$');
 756                 }
 757             } else {
 758                 result.append(nextChar);
 759                 cursor++;
 760             }
 761         }
 762         // Append the intervening text
 763         sb.append(text, lastAppendPosition, matcher.start());
 764         // Append the match substitution
 765         sb.append(result);
 766     }
 767 
 768     private String callReplaceValue(final ScriptFunction function, final RegExpMatcher matcher, final String string) {
 769         final Object[] groups = groups(matcher);
 770         final Object[] args   = Arrays.copyOf(groups, groups.length + 2);
 771 
 772         args[groups.length]     = matcher.start();
 773         args[groups.length + 1] = string;
 774 
 775         final Object self = function.isStrict() ? UNDEFINED : Global.instance();
 776 
 777         return JSType.toString(ScriptRuntime.apply(function, self, args));
 778     }
 779 
 780     /**
 781      * Breaks up a string into an array of substrings based on a regular
 782      * expression or fixed string.
 783      *
 784      * @param string String to match.
 785      * @param limit  Split limit.
 786      * @return Array of substrings.
 787      */
 788     Object split(final String string, final long limit) {
 789         if (limit == 0L) {
 790             return new NativeArray();
 791         }
 792 
 793         final List<Object> matches = new ArrayList<>();
 794 
 795         RegExpResult match;
 796         final int inputLength = string.length();
 797         int lastLength = -1;
 798         int lastIndex = 0;
 799         int lastLastIndex = 0;
 800 
 801         while ((match = execSplit(string, lastIndex)) != null) {
 802             lastIndex = match.getIndex() + match.length();
 803 
 804             if (lastIndex > lastLastIndex) {
 805                 matches.add(string.substring(lastLastIndex, match.getIndex()));
 806                 final Object[] groups = match.getGroups();
 807                 if (groups.length > 1 && match.getIndex() < inputLength) {
 808                     for (int index = 1; index < groups.length && matches.size() < limit; index++) {
 809                         matches.add(groups[index]);
 810                     }
 811                 }
 812 
 813                 lastLength = match.length();
 814 
 815                 if (matches.size() >= limit) {
 816                     break;
 817                 }
 818             }
 819 
 820             // bump the index to avoid infinite loop
 821             if (lastIndex == lastLastIndex) {
 822                 lastIndex++;
 823             } else {
 824                 lastLastIndex = lastIndex;
 825             }
 826         }
 827 
 828         if (matches.size() < limit) {
 829             // check special case if we need to append an empty string at the
 830             // end of the match
 831             // if the lastIndex was the entire string
 832             if (lastLastIndex == string.length()) {
 833                 if (lastLength > 0 || execSplit("", 0) == null) {
 834                     matches.add("");
 835                 }
 836             } else {
 837                 matches.add(string.substring(lastLastIndex, inputLength));
 838             }
 839         }
 840 
 841         return new NativeArray(matches.toArray());
 842     }
 843 
 844     /**
 845      * Tests for a match in a string. It returns the index of the match, or -1
 846      * if not found.
 847      *
 848      * @param string String to match.
 849      * @return Index of match.
 850      */
 851     Object search(final String string) {
 852         final RegExpResult match = execInner(string);
 853 
 854         if (match == null) {
 855             return -1;
 856         }
 857 
 858         return match.getIndex();
 859     }
 860 
 861     /**
 862      * Fast lastIndex getter
 863      * @return last index property as int
 864      */
 865     public int getLastIndex() {
 866         return JSType.toInt32(lastIndex);
 867     }
 868 
 869     /**
 870      * Fast lastIndex getter
 871      * @return last index property as boxed integer
 872      */
 873     public Object getLastIndexObject() {
 874         return lastIndex;
 875     }
 876 
 877     /**
 878      * Fast lastIndex setter
 879      * @param lastIndex lastIndex
 880      */
 881     public void setLastIndex(final int lastIndex) {
 882         this.lastIndex = JSType.toObject(lastIndex);
 883     }
 884 
 885     private void init() {
 886         // Keep reference to global object to support "static" properties of RegExp
 887         this.globalObject = Global.instance();
 888         this.setProto(globalObject.getRegExpPrototype());
 889     }
 890 
 891     private static NativeRegExp checkRegExp(final Object self) {
 892         Global.checkObjectCoercible(self);
 893         if (self instanceof NativeRegExp) {
 894             return (NativeRegExp)self;
 895         } else if (self != null && self == Global.instance().getRegExpPrototype()) {
 896             return Global.instance().DEFAULT_REGEXP;
 897         } else {
 898             throw typeError("not.a.regexp", ScriptRuntime.safeToString(self));
 899         }
 900     }
 901 
 902     private void setGlobal(final boolean global) {
 903         regexp.setGlobal(global);
 904     }
 905 
 906     boolean getGlobal() {
 907         return regexp.isGlobal();
 908     }
 909 
 910     private RegExp getRegExp() {
 911         return regexp;
 912     }
 913 
 914     private void setRegExp(final RegExp regexp) {
 915         this.regexp = regexp;
 916     }
 917 
 918 }