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