src/string.js

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 (function(global, utils) {
   6
   7 %CheckIsBootstrapping();
   8
   9 // -------------------------------------------------------------------
  10 // Imports
  11
  12 var ArrayIndexOf;
  13 var ArrayJoin;
  14 var GlobalRegExp = global.RegExp;
  15 var GlobalString = global.String;
  16 var InternalArray = utils.InternalArray;
  17 var InternalPackedArray = utils.InternalPackedArray;
  18 var RegExpExec;
  19 var RegExpExecNoTests;
  20 var RegExpLastMatchInfo;
  21 var ToNumber;
  22 var ToString;
  23
  24 utils.Import(function(from) {
  25   ArrayIndexOf = from.ArrayIndexOf;
  26   ArrayJoin = from.ArrayJoin;
  27   RegExpExec = from.RegExpExec;
  28   RegExpExecNoTests = from.RegExpExecNoTests;
  29   RegExpLastMatchInfo = from.RegExpLastMatchInfo;
  30   ToNumber = from.ToNumber;
  31   ToString = from.ToString;
  32 });
  33
  34 //-------------------------------------------------------------------
  35
  36 // ECMA-262 section 15.5.4.2
  37 function StringToString() {
  38   if (!IS_STRING(this) && !IS_STRING_WRAPPER(this)) {
  39     throw MakeTypeError(kNotGeneric, 'String.prototype.toString');
  40   }
  41   return %_ValueOf(this);
  42 }
  43
  44
  45 // ECMA-262 section 15.5.4.3
  46 function StringValueOf() {
  47   if (!IS_STRING(this) && !IS_STRING_WRAPPER(this)) {
  48     throw MakeTypeError(kNotGeneric, 'String.prototype.valueOf');
  49   }
  50   return %_ValueOf(this);
  51 }
  52
  53
  54 // ECMA-262, section 15.5.4.4
  55 function StringCharAtJS(pos) {
  56   CHECK_OBJECT_COERCIBLE(this, "String.prototype.charAt");
  57
  58   var result = %_StringCharAt(this, pos);
  59   if (%_IsSmi(result)) {
  60     result = %_StringCharAt(TO_STRING_INLINE(this), TO_INTEGER(pos));
  61   }
  62   return result;
  63 }
  64
  65
  66 // ECMA-262 section 15.5.4.5
  67 function StringCharCodeAtJS(pos) {
  68   CHECK_OBJECT_COERCIBLE(this, "String.prototype.charCodeAt");
  69
  70   var result = %_StringCharCodeAt(this, pos);
  71   if (!%_IsSmi(result)) {
  72     result = %_StringCharCodeAt(TO_STRING_INLINE(this), TO_INTEGER(pos));
  73   }
  74   return result;
  75 }
  76
  77
  78 // ECMA-262, section 15.5.4.6
  79 function StringConcat(other /* and more */) {  // length == 1
  80   CHECK_OBJECT_COERCIBLE(this, "String.prototype.concat");
  81   var len = %_ArgumentsLength();
  82   var this_as_string = TO_STRING_INLINE(this);
  83   if (len === 1) {
  84     return this_as_string + TO_STRING_INLINE(other);
  85   }
  86   var parts = new InternalArray(len + 1);
  87   parts[0] = this_as_string;
  88   for (var i = 0; i < len; i++) {
  89     var part = %_Arguments(i);
  90     parts[i + 1] = TO_STRING_INLINE(part);
  91   }
  92   return %StringBuilderConcat(parts, len + 1, "");
  93 }
  94
  95
  96 // ECMA-262 section 15.5.4.7
  97 function StringIndexOfJS(pattern /* position */) {  // length == 1
  98   CHECK_OBJECT_COERCIBLE(this, "String.prototype.indexOf");
  99
 100   var subject = TO_STRING_INLINE(this);
 101   pattern = TO_STRING_INLINE(pattern);
 102   var index = 0;
 103   if (%_ArgumentsLength() > 1) {
 104     index = %_Arguments(1);  // position
 105     index = TO_INTEGER(index);
 106     if (index < 0) index = 0;
 107     if (index > subject.length) index = subject.length;
 108   }
 109   return %StringIndexOf(subject, pattern, index);
 110 }
 111
 112
 113 // ECMA-262 section 15.5.4.8
 114 function StringLastIndexOfJS(pat /* position */) {  // length == 1
 115   CHECK_OBJECT_COERCIBLE(this, "String.prototype.lastIndexOf");
 116
 117   var sub = TO_STRING_INLINE(this);
 118   var subLength = sub.length;
 119   var pat = TO_STRING_INLINE(pat);
 120   var patLength = pat.length;
 121   var index = subLength - patLength;
 122   if (%_ArgumentsLength() > 1) {
 123     var position = ToNumber(%_Arguments(1));
 124     if (!NUMBER_IS_NAN(position)) {
 125       position = TO_INTEGER(position);
 126       if (position < 0) {
 127         position = 0;
 128       }
 129       if (position + patLength < subLength) {
 130         index = position;
 131       }
 132     }
 133   }
 134   if (index < 0) {
 135     return -1;
 136   }
 137   return %StringLastIndexOf(sub, pat, index);
 138 }
 139
 140
 141 // ECMA-262 section 15.5.4.9
 142 //
 143 // This function is implementation specific.  For now, we do not
 144 // do anything locale specific.
 145 function StringLocaleCompareJS(other) {
 146   CHECK_OBJECT_COERCIBLE(this, "String.prototype.localeCompare");
 147
 148   return %StringLocaleCompare(TO_STRING_INLINE(this),
 149                               TO_STRING_INLINE(other));
 150 }
 151
 152
 153 // ECMA-262 section 15.5.4.10
 154 function StringMatchJS(regexp) {
 155   CHECK_OBJECT_COERCIBLE(this, "String.prototype.match");
 156
 157   var subject = TO_STRING_INLINE(this);
 158   if (IS_REGEXP(regexp)) {
 159     // Emulate RegExp.prototype.exec's side effect in step 5, even though
 160     // value is discarded.
 161     var lastIndex = regexp.lastIndex;
 162     TO_INTEGER_FOR_SIDE_EFFECT(lastIndex);
 163     if (!regexp.global) return RegExpExecNoTests(regexp, subject, 0);
 164     var result = %StringMatch(subject, regexp, RegExpLastMatchInfo);
 165     if (result !== null) $regexpLastMatchInfoOverride = null;
 166     regexp.lastIndex = 0;
 167     return result;
 168   }
 169   // Non-regexp argument.
 170   regexp = new GlobalRegExp(regexp);
 171   return RegExpExecNoTests(regexp, subject, 0);
 172 }
 173
 174
 175 // ECMA-262 v6, section 21.1.3.12
 176 //
 177 // For now we do nothing, as proper normalization requires big tables.
 178 // If Intl is enabled, then i18n.js will override it and provide the the
 179 // proper functionality.
 180 function StringNormalizeJS() {
 181   CHECK_OBJECT_COERCIBLE(this, "String.prototype.normalize");
 182   var s = TO_STRING_INLINE(this);
 183
 184   var formArg = %_Arguments(0);
 185   var form = IS_UNDEFINED(formArg) ? 'NFC' : TO_STRING_INLINE(formArg);
 186
 187   var NORMALIZATION_FORMS = ['NFC', 'NFD', 'NFKC', 'NFKD'];
 188   var normalizationForm =
 189       %_CallFunction(NORMALIZATION_FORMS, form, ArrayIndexOf);
 190   if (normalizationForm === -1) {
 191     throw MakeRangeError(kNormalizationForm,
 192                          %_CallFunction(NORMALIZATION_FORMS, ', ', ArrayJoin));
 193   }
 194
 195   return s;
 196 }
 197
 198
 199 // This has the same size as the RegExpLastMatchInfo array, and can be used
 200 // for functions that expect that structure to be returned.  It is used when
 201 // the needle is a string rather than a regexp.  In this case we can't update
 202 // lastMatchArray without erroneously affecting the properties on the global
 203 // RegExp object.
 204 var reusableMatchInfo = [2, "", "", -1, -1];
 205
 206
 207 // ECMA-262, section 15.5.4.11
 208 function StringReplace(search, replace) {
 209   CHECK_OBJECT_COERCIBLE(this, "String.prototype.replace");
 210
 211   var subject = TO_STRING_INLINE(this);
 212
 213   // Decision tree for dispatch
 214   // .. regexp search
 215   // .... string replace
 216   // ...... non-global search
 217   // ........ empty string replace
 218   // ........ non-empty string replace (with $-expansion)
 219   // ...... global search
 220   // ........ no need to circumvent last match info override
 221   // ........ need to circument last match info override
 222   // .... function replace
 223   // ...... global search
 224   // ...... non-global search
 225   // .. string search
 226   // .... special case that replaces with one single character
 227   // ...... function replace
 228   // ...... string replace (with $-expansion)
 229
 230   if (IS_REGEXP(search)) {
 231     // Emulate RegExp.prototype.exec's side effect in step 5, even if
 232     // value is discarded.
 233     var lastIndex = search.lastIndex;
 234     TO_INTEGER_FOR_SIDE_EFFECT(lastIndex);
 235
 236     if (!IS_CALLABLE(replace)) {
 237       replace = TO_STRING_INLINE(replace);
 238
 239       if (!search.global) {
 240         // Non-global regexp search, string replace.
 241         var match = RegExpExec(search, subject, 0);
 242         if (match == null) {
 243           search.lastIndex = 0
 244           return subject;
 245         }
 246         if (replace.length == 0) {
 247           return %_SubString(subject, 0, match[CAPTURE0]) +
 248                  %_SubString(subject, match[CAPTURE1], subject.length)
 249         }
 250         return ExpandReplacement(replace, subject, RegExpLastMatchInfo,
 251                                  %_SubString(subject, 0, match[CAPTURE0])) +
 252                %_SubString(subject, match[CAPTURE1], subject.length);
 253       }
 254
 255       // Global regexp search, string replace.
 256       search.lastIndex = 0;
 257       if ($regexpLastMatchInfoOverride == null) {
 258         return %StringReplaceGlobalRegExpWithString(
 259             subject, search, replace, RegExpLastMatchInfo);
 260       } else {
 261         // We use this hack to detect whether StringReplaceRegExpWithString
 262         // found at least one hit. In that case we need to remove any
 263         // override.
 264         var saved_subject = RegExpLastMatchInfo[LAST_SUBJECT_INDEX];
 265         RegExpLastMatchInfo[LAST_SUBJECT_INDEX] = 0;
 266         var answer = %StringReplaceGlobalRegExpWithString(
 267             subject, search, replace, RegExpLastMatchInfo);
 268         if (%_IsSmi(RegExpLastMatchInfo[LAST_SUBJECT_INDEX])) {
 269           RegExpLastMatchInfo[LAST_SUBJECT_INDEX] = saved_subject;
 270         } else {
 271           $regexpLastMatchInfoOverride = null;
 272         }
 273         return answer;
 274       }
 275     }
 276
 277     if (search.global) {
 278       // Global regexp search, function replace.
 279       return StringReplaceGlobalRegExpWithFunction(subject, search, replace);
 280     }
 281     // Non-global regexp search, function replace.
 282     return StringReplaceNonGlobalRegExpWithFunction(subject, search, replace);
 283   }
 284
 285   search = TO_STRING_INLINE(search);
 286
 287   if (search.length == 1 &&
 288       subject.length > 0xFF &&
 289       IS_STRING(replace) &&
 290       %StringIndexOf(replace, '$', 0) < 0) {
 291     // Searching by traversing a cons string tree and replace with cons of
 292     // slices works only when the replaced string is a single character, being
 293     // replaced by a simple string and only pays off for long strings.
 294     return %StringReplaceOneCharWithString(subject, search, replace);
 295   }
 296   var start = %StringIndexOf(subject, search, 0);
 297   if (start < 0) return subject;
 298   var end = start + search.length;
 299
 300   var result = %_SubString(subject, 0, start);
 301
 302   // Compute the string to replace with.
 303   if (IS_CALLABLE(replace)) {
 304     result += replace(search, start, subject);
 305   } else {
 306     reusableMatchInfo[CAPTURE0] = start;
 307     reusableMatchInfo[CAPTURE1] = end;
 308     result = ExpandReplacement(TO_STRING_INLINE(replace),
 309                                subject,
 310                                reusableMatchInfo,
 311                                result);
 312   }
 313
 314   return result + %_SubString(subject, end, subject.length);
 315 }
 316
 317
 318 // Expand the $-expressions in the string and return a new string with
 319 // the result.
 320 function ExpandReplacement(string, subject, matchInfo, result) {
 321   var length = string.length;
 322   var next = %StringIndexOf(string, '$', 0);
 323   if (next < 0) {
 324     if (length > 0) result += string;
 325     return result;
 326   }
 327
 328   if (next > 0) result += %_SubString(string, 0, next);
 329
 330   while (true) {
 331     var expansion = '$';
 332     var position = next + 1;
 333     if (position < length) {
 334       var peek = %_StringCharCodeAt(string, position);
 335       if (peek == 36) {         // $$
 336         ++position;
 337         result += '$';
 338       } else if (peek == 38) {  // $& - match
 339         ++position;
 340         result +=
 341           %_SubString(subject, matchInfo[CAPTURE0], matchInfo[CAPTURE1]);
 342       } else if (peek == 96) {  // $` - prefix
 343         ++position;
 344         result += %_SubString(subject, 0, matchInfo[CAPTURE0]);
 345       } else if (peek == 39) {  // $' - suffix
 346         ++position;
 347         result += %_SubString(subject, matchInfo[CAPTURE1], subject.length);
 348       } else if (peek >= 48 && peek <= 57) {
 349         // Valid indices are $1 .. $9, $01 .. $09 and $10 .. $99
 350         var scaled_index = (peek - 48) << 1;
 351         var advance = 1;
 352         var number_of_captures = NUMBER_OF_CAPTURES(matchInfo);
 353         if (position + 1 < string.length) {
 354           var next = %_StringCharCodeAt(string, position + 1);
 355           if (next >= 48 && next <= 57) {
 356             var new_scaled_index = scaled_index * 10 + ((next - 48) << 1);
 357             if (new_scaled_index < number_of_captures) {
 358               scaled_index = new_scaled_index;
 359               advance = 2;
 360             }
 361           }
 362         }
 363         if (scaled_index != 0 && scaled_index < number_of_captures) {
 364           var start = matchInfo[CAPTURE(scaled_index)];
 365           if (start >= 0) {
 366             result +=
 367               %_SubString(subject, start, matchInfo[CAPTURE(scaled_index + 1)]);
 368           }
 369           position += advance;
 370         } else {
 371           result += '$';
 372         }
 373       } else {
 374         result += '$';
 375       }
 376     } else {
 377       result += '$';
 378     }
 379
 380     // Go the the next $ in the string.
 381     next = %StringIndexOf(string, '$', position);
 382
 383     // Return if there are no more $ characters in the string. If we
 384     // haven't reached the end, we need to append the suffix.
 385     if (next < 0) {
 386       if (position < length) {
 387         result += %_SubString(string, position, length);
 388       }
 389       return result;
 390     }
 391
 392     // Append substring between the previous and the next $ character.
 393     if (next > position) {
 394       result += %_SubString(string, position, next);
 395     }
 396   }
 397   return result;
 398 }
 399
 400
 401 // Compute the string of a given regular expression capture.
 402 function CaptureString(string, lastCaptureInfo, index) {
 403   // Scale the index.
 404   var scaled = index << 1;
 405   // Compute start and end.
 406   var start = lastCaptureInfo[CAPTURE(scaled)];
 407   // If start isn't valid, return undefined.
 408   if (start < 0) return;
 409   var end = lastCaptureInfo[CAPTURE(scaled + 1)];
 410   return %_SubString(string, start, end);
 411 }
 412
 413
 414 // TODO(lrn): This array will survive indefinitely if replace is never
 415 // called again. However, it will be empty, since the contents are cleared
 416 // in the finally block.
 417 var reusableReplaceArray = new InternalArray(4);
 418
 419 // Helper function for replacing regular expressions with the result of a
 420 // function application in String.prototype.replace.
 421 function StringReplaceGlobalRegExpWithFunction(subject, regexp, replace) {
 422   var resultArray = reusableReplaceArray;
 423   if (resultArray) {
 424     reusableReplaceArray = null;
 425   } else {
 426     // Inside a nested replace (replace called from the replacement function
 427     // of another replace) or we have failed to set the reusable array
 428     // back due to an exception in a replacement function. Create a new
 429     // array to use in the future, or until the original is written back.
 430     resultArray = new InternalArray(16);
 431   }
 432   var res = %RegExpExecMultiple(regexp,
 433                                 subject,
 434                                 RegExpLastMatchInfo,
 435                                 resultArray);
 436   regexp.lastIndex = 0;
 437   if (IS_NULL(res)) {
 438     // No matches at all.
 439     reusableReplaceArray = resultArray;
 440     return subject;
 441   }
 442   var len = res.length;
 443   if (NUMBER_OF_CAPTURES(RegExpLastMatchInfo) == 2) {
 444     // If the number of captures is two then there are no explicit captures in
 445     // the regexp, just the implicit capture that captures the whole match.  In
 446     // this case we can simplify quite a bit and end up with something faster.
 447     // The builder will consist of some integers that indicate slices of the
 448     // input string and some replacements that were returned from the replace
 449     // function.
 450     var match_start = 0;
 451     var override = new InternalPackedArray(null, 0, subject);
 452     for (var i = 0; i < len; i++) {
 453       var elem = res[i];
 454       if (%_IsSmi(elem)) {
 455         // Integers represent slices of the original string.  Use these to
 456         // get the offsets we need for the override array (so things like
 457         // RegExp.leftContext work during the callback function.
 458         if (elem > 0) {
 459           match_start = (elem >> 11) + (elem & 0x7ff);
 460         } else {
 461           match_start = res[++i] - elem;
 462         }
 463       } else {
 464         override[0] = elem;
 465         override[1] = match_start;
 466         $regexpLastMatchInfoOverride = override;
 467         var func_result = replace(elem, match_start, subject);
 468         // Overwrite the i'th element in the results with the string we got
 469         // back from the callback function.
 470         res[i] = TO_STRING_INLINE(func_result);
 471         match_start += elem.length;
 472       }
 473     }
 474   } else {
 475     for (var i = 0; i < len; i++) {
 476       var elem = res[i];
 477       if (!%_IsSmi(elem)) {
 478         // elem must be an Array.
 479         // Use the apply argument as backing for global RegExp properties.
 480         $regexpLastMatchInfoOverride = elem;
 481         var func_result = %Apply(replace, UNDEFINED, elem, 0, elem.length);
 482         // Overwrite the i'th element in the results with the string we got
 483         // back from the callback function.
 484         res[i] = TO_STRING_INLINE(func_result);
 485       }
 486     }
 487   }
 488   var result = %StringBuilderConcat(res, res.length, subject);
 489   resultArray.length = 0;
 490   reusableReplaceArray = resultArray;
 491   return result;
 492 }
 493
 494
 495 function StringReplaceNonGlobalRegExpWithFunction(subject, regexp, replace) {
 496   var matchInfo = RegExpExec(regexp, subject, 0);
 497   if (IS_NULL(matchInfo)) {
 498     regexp.lastIndex = 0;
 499     return subject;
 500   }
 501   var index = matchInfo[CAPTURE0];
 502   var result = %_SubString(subject, 0, index);
 503   var endOfMatch = matchInfo[CAPTURE1];
 504   // Compute the parameter list consisting of the match, captures, index,
 505   // and subject for the replace function invocation.
 506   // The number of captures plus one for the match.
 507   var m = NUMBER_OF_CAPTURES(matchInfo) >> 1;
 508   var replacement;
 509   if (m == 1) {
 510     // No captures, only the match, which is always valid.
 511     var s = %_SubString(subject, index, endOfMatch);
 512     // Don't call directly to avoid exposing the built-in global object.
 513     replacement = replace(s, index, subject);
 514   } else {
 515     var parameters = new InternalArray(m + 2);
 516     for (var j = 0; j < m; j++) {
 517       parameters[j] = CaptureString(subject, matchInfo, j);
 518     }
 519     parameters[j] = index;
 520     parameters[j + 1] = subject;
 521
 522     replacement = %Apply(replace, UNDEFINED, parameters, 0, j + 2);
 523   }
 524
 525   result += replacement;  // The add method converts to string if necessary.
 526   // Can't use matchInfo any more from here, since the function could
 527   // overwrite it.
 528   return result + %_SubString(subject, endOfMatch, subject.length);
 529 }
 530
 531
 532 // ECMA-262 section 15.5.4.12
 533 function StringSearch(re) {
 534   CHECK_OBJECT_COERCIBLE(this, "String.prototype.search");
 535
 536   var regexp;
 537   if (IS_REGEXP(re)) {
 538     regexp = re;
 539   } else {
 540     regexp = new GlobalRegExp(re);
 541   }
 542   var match = RegExpExec(regexp, TO_STRING_INLINE(this), 0);
 543   if (match) {
 544     return match[CAPTURE0];
 545   }
 546   return -1;
 547 }
 548
 549
 550 // ECMA-262 section 15.5.4.13
 551 function StringSlice(start, end) {
 552   CHECK_OBJECT_COERCIBLE(this, "String.prototype.slice");
 553
 554   var s = TO_STRING_INLINE(this);
 555   var s_len = s.length;
 556   var start_i = TO_INTEGER(start);
 557   var end_i = s_len;
 558   if (!IS_UNDEFINED(end)) {
 559     end_i = TO_INTEGER(end);
 560   }
 561
 562   if (start_i < 0) {
 563     start_i += s_len;
 564     if (start_i < 0) {
 565       start_i = 0;
 566     }
 567   } else {
 568     if (start_i > s_len) {
 569       return '';
 570     }
 571   }
 572
 573   if (end_i < 0) {
 574     end_i += s_len;
 575     if (end_i < 0) {
 576       return '';
 577     }
 578   } else {
 579     if (end_i > s_len) {
 580       end_i = s_len;
 581     }
 582   }
 583
 584   if (end_i <= start_i) {
 585     return '';
 586   }
 587
 588   return %_SubString(s, start_i, end_i);
 589 }
 590
 591
 592 // ECMA-262 section 15.5.4.14
 593 function StringSplitJS(separator, limit) {
 594   CHECK_OBJECT_COERCIBLE(this, "String.prototype.split");
 595
 596   var subject = TO_STRING_INLINE(this);
 597   limit = (IS_UNDEFINED(limit)) ? 0xffffffff : TO_UINT32(limit);
 598
 599   var length = subject.length;
 600   if (!IS_REGEXP(separator)) {
 601     var separator_string = TO_STRING_INLINE(separator);
 602
 603     if (limit === 0) return [];
 604
 605     // ECMA-262 says that if separator is undefined, the result should
 606     // be an array of size 1 containing the entire string.
 607     if (IS_UNDEFINED(separator)) return [subject];
 608
 609     var separator_length = separator_string.length;
 610
 611     // If the separator string is empty then return the elements in the subject.
 612     if (separator_length === 0) return %StringToArray(subject, limit);
 613
 614     var result = %StringSplit(subject, separator_string, limit);
 615
 616     return result;
 617   }
 618
 619   if (limit === 0) return [];
 620
 621   // Separator is a regular expression.
 622   return StringSplitOnRegExp(subject, separator, limit, length);
 623 }
 624
 625
 626 function StringSplitOnRegExp(subject, separator, limit, length) {
 627   if (length === 0) {
 628     if (RegExpExec(separator, subject, 0, 0) != null) {
 629       return [];
 630     }
 631     return [subject];
 632   }
 633
 634   var currentIndex = 0;
 635   var startIndex = 0;
 636   var startMatch = 0;
 637   var result = new InternalArray();
 638
 639   outer_loop:
 640   while (true) {
 641
 642     if (startIndex === length) {
 643       result[result.length] = %_SubString(subject, currentIndex, length);
 644       break;
 645     }
 646
 647     var matchInfo = RegExpExec(separator, subject, startIndex);
 648     if (matchInfo == null || length === (startMatch = matchInfo[CAPTURE0])) {
 649       result[result.length] = %_SubString(subject, currentIndex, length);
 650       break;
 651     }
 652     var endIndex = matchInfo[CAPTURE1];
 653
 654     // We ignore a zero-length match at the currentIndex.
 655     if (startIndex === endIndex && endIndex === currentIndex) {
 656       startIndex++;
 657       continue;
 658     }
 659
 660     result[result.length] = %_SubString(subject, currentIndex, startMatch);
 661
 662     if (result.length === limit) break;
 663
 664     var matchinfo_len = NUMBER_OF_CAPTURES(matchInfo) + REGEXP_FIRST_CAPTURE;
 665     for (var i = REGEXP_FIRST_CAPTURE + 2; i < matchinfo_len; ) {
 666       var start = matchInfo[i++];
 667       var end = matchInfo[i++];
 668       if (end != -1) {
 669         result[result.length] = %_SubString(subject, start, end);
 670       } else {
 671         result[result.length] = UNDEFINED;
 672       }
 673       if (result.length === limit) break outer_loop;
 674     }
 675
 676     startIndex = currentIndex = endIndex;
 677   }
 678   var array_result = [];
 679   %MoveArrayContents(result, array_result);
 680   return array_result;
 681 }
 682
 683
 684 // ECMA-262 section 15.5.4.15
 685 function StringSubstring(start, end) {
 686   CHECK_OBJECT_COERCIBLE(this, "String.prototype.subString");
 687
 688   var s = TO_STRING_INLINE(this);
 689   var s_len = s.length;
 690
 691   var start_i = TO_INTEGER(start);
 692   if (start_i < 0) {
 693     start_i = 0;
 694   } else if (start_i > s_len) {
 695     start_i = s_len;
 696   }
 697
 698   var end_i = s_len;
 699   if (!IS_UNDEFINED(end)) {
 700     end_i = TO_INTEGER(end);
 701     if (end_i > s_len) {
 702       end_i = s_len;
 703     } else {
 704       if (end_i < 0) end_i = 0;
 705       if (start_i > end_i) {
 706         var tmp = end_i;
 707         end_i = start_i;
 708         start_i = tmp;
 709       }
 710     }
 711   }
 712
 713   return %_SubString(s, start_i, end_i);
 714 }
 715
 716
 717 // ES6 draft, revision 26 (2014-07-18), section B.2.3.1
 718 function StringSubstr(start, n) {
 719   CHECK_OBJECT_COERCIBLE(this, "String.prototype.substr");
 720
 721   var s = TO_STRING_INLINE(this);
 722   var len;
 723
 724   // Correct n: If not given, set to string length; if explicitly
 725   // set to undefined, zero, or negative, returns empty string.
 726   if (IS_UNDEFINED(n)) {
 727     len = s.length;
 728   } else {
 729     len = TO_INTEGER(n);
 730     if (len <= 0) return '';
 731   }
 732
 733   // Correct start: If not given (or undefined), set to zero; otherwise
 734   // convert to integer and handle negative case.
 735   if (IS_UNDEFINED(start)) {
 736     start = 0;
 737   } else {
 738     start = TO_INTEGER(start);
 739     // If positive, and greater than or equal to the string length,
 740     // return empty string.
 741     if (start >= s.length) return '';
 742     // If negative and absolute value is larger than the string length,
 743     // use zero.
 744     if (start < 0) {
 745       start += s.length;
 746       if (start < 0) start = 0;
 747     }
 748   }
 749
 750   var end = start + len;
 751   if (end > s.length) end = s.length;
 752
 753   return %_SubString(s, start, end);
 754 }
 755
 756
 757 // ECMA-262, 15.5.4.16
 758 function StringToLowerCaseJS() {
 759   CHECK_OBJECT_COERCIBLE(this, "String.prototype.toLowerCase");
 760
 761   return %StringToLowerCase(TO_STRING_INLINE(this));
 762 }
 763
 764
 765 // ECMA-262, 15.5.4.17
 766 function StringToLocaleLowerCase() {
 767   CHECK_OBJECT_COERCIBLE(this, "String.prototype.toLocaleLowerCase");
 768
 769   return %StringToLowerCase(TO_STRING_INLINE(this));
 770 }
 771
 772
 773 // ECMA-262, 15.5.4.18
 774 function StringToUpperCaseJS() {
 775   CHECK_OBJECT_COERCIBLE(this, "String.prototype.toUpperCase");
 776
 777   return %StringToUpperCase(TO_STRING_INLINE(this));
 778 }
 779
 780
 781 // ECMA-262, 15.5.4.19
 782 function StringToLocaleUpperCase() {
 783   CHECK_OBJECT_COERCIBLE(this, "String.prototype.toLocaleUpperCase");
 784
 785   return %StringToUpperCase(TO_STRING_INLINE(this));
 786 }
 787
 788 // ES5, 15.5.4.20
 789 function StringTrimJS() {
 790   CHECK_OBJECT_COERCIBLE(this, "String.prototype.trim");
 791
 792   return %StringTrim(TO_STRING_INLINE(this), true, true);
 793 }
 794
 795 function StringTrimLeft() {
 796   CHECK_OBJECT_COERCIBLE(this, "String.prototype.trimLeft");
 797
 798   return %StringTrim(TO_STRING_INLINE(this), true, false);
 799 }
 800
 801 function StringTrimRight() {
 802   CHECK_OBJECT_COERCIBLE(this, "String.prototype.trimRight");
 803
 804   return %StringTrim(TO_STRING_INLINE(this), false, true);
 805 }
 806
 807
 808 // ECMA-262, section 15.5.3.2
 809 function StringFromCharCode(code) {
 810   var n = %_ArgumentsLength();
 811   if (n == 1) {
 812     if (!%_IsSmi(code)) code = ToNumber(code);
 813     return %_StringCharFromCode(code & 0xffff);
 814   }
 815
 816   var one_byte = %NewString(n, NEW_ONE_BYTE_STRING);
 817   var i;
 818   for (i = 0; i < n; i++) {
 819     var code = %_Arguments(i);
 820     if (!%_IsSmi(code)) code = ToNumber(code) & 0xffff;
 821     if (code < 0) code = code & 0xffff;
 822     if (code > 0xff) break;
 823     %_OneByteSeqStringSetChar(i, code, one_byte);
 824   }
 825   if (i == n) return one_byte;
 826   one_byte = %TruncateString(one_byte, i);
 827
 828   var two_byte = %NewString(n - i, NEW_TWO_BYTE_STRING);
 829   for (var j = 0; i < n; i++, j++) {
 830     var code = %_Arguments(i);
 831     if (!%_IsSmi(code)) code = ToNumber(code) & 0xffff;
 832     %_TwoByteSeqStringSetChar(j, code, two_byte);
 833   }
 834   return one_byte + two_byte;
 835 }
 836
 837
 838 // ES6 draft, revision 26 (2014-07-18), section B.2.3.2.1
 839 function HtmlEscape(str) {
 840   return %_CallFunction(TO_STRING_INLINE(str), /"/g, "&quot;", StringReplace);
 841 }
 842
 843
 844 // ES6 draft, revision 26 (2014-07-18), section B.2.3.2
 845 function StringAnchor(name) {
 846   CHECK_OBJECT_COERCIBLE(this, "String.prototype.anchor");
 847   return "<a name=\"" + HtmlEscape(name) + "\">" + TO_STRING_INLINE(this) +
 848          "</a>";
 849 }
 850
 851
 852 // ES6 draft, revision 26 (2014-07-18), section B.2.3.3
 853 function StringBig() {
 854   CHECK_OBJECT_COERCIBLE(this, "String.prototype.big");
 855   return "<big>" + TO_STRING_INLINE(this) + "</big>";
 856 }
 857
 858
 859 // ES6 draft, revision 26 (2014-07-18), section B.2.3.4
 860 function StringBlink() {
 861   CHECK_OBJECT_COERCIBLE(this, "String.prototype.blink");
 862   return "<blink>" + TO_STRING_INLINE(this) + "</blink>";
 863 }
 864
 865
 866 // ES6 draft, revision 26 (2014-07-18), section B.2.3.5
 867 function StringBold() {
 868   CHECK_OBJECT_COERCIBLE(this, "String.prototype.bold");
 869   return "<b>" + TO_STRING_INLINE(this) + "</b>";
 870 }
 871
 872
 873 // ES6 draft, revision 26 (2014-07-18), section B.2.3.6
 874 function StringFixed() {
 875   CHECK_OBJECT_COERCIBLE(this, "String.prototype.fixed");
 876   return "<tt>" + TO_STRING_INLINE(this) + "</tt>";
 877 }
 878
 879
 880 // ES6 draft, revision 26 (2014-07-18), section B.2.3.7
 881 function StringFontcolor(color) {
 882   CHECK_OBJECT_COERCIBLE(this, "String.prototype.fontcolor");
 883   return "<font color=\"" + HtmlEscape(color) + "\">" + TO_STRING_INLINE(this) +
 884          "</font>";
 885 }
 886
 887
 888 // ES6 draft, revision 26 (2014-07-18), section B.2.3.8
 889 function StringFontsize(size) {
 890   CHECK_OBJECT_COERCIBLE(this, "String.prototype.fontsize");
 891   return "<font size=\"" + HtmlEscape(size) + "\">" + TO_STRING_INLINE(this) +
 892          "</font>";
 893 }
 894
 895
 896 // ES6 draft, revision 26 (2014-07-18), section B.2.3.9
 897 function StringItalics() {
 898   CHECK_OBJECT_COERCIBLE(this, "String.prototype.italics");
 899   return "<i>" + TO_STRING_INLINE(this) + "</i>";
 900 }
 901
 902
 903 // ES6 draft, revision 26 (2014-07-18), section B.2.3.10
 904 function StringLink(s) {
 905   CHECK_OBJECT_COERCIBLE(this, "String.prototype.link");
 906   return "<a href=\"" + HtmlEscape(s) + "\">" + TO_STRING_INLINE(this) + "</a>";
 907 }
 908
 909
 910 // ES6 draft, revision 26 (2014-07-18), section B.2.3.11
 911 function StringSmall() {
 912   CHECK_OBJECT_COERCIBLE(this, "String.prototype.small");
 913   return "<small>" + TO_STRING_INLINE(this) + "</small>";
 914 }
 915
 916
 917 // ES6 draft, revision 26 (2014-07-18), section B.2.3.12
 918 function StringStrike() {
 919   CHECK_OBJECT_COERCIBLE(this, "String.prototype.strike");
 920   return "<strike>" + TO_STRING_INLINE(this) + "</strike>";
 921 }
 922
 923
 924 // ES6 draft, revision 26 (2014-07-18), section B.2.3.13
 925 function StringSub() {
 926   CHECK_OBJECT_COERCIBLE(this, "String.prototype.sub");
 927   return "<sub>" + TO_STRING_INLINE(this) + "</sub>";
 928 }
 929
 930
 931 // ES6 draft, revision 26 (2014-07-18), section B.2.3.14
 932 function StringSup() {
 933   CHECK_OBJECT_COERCIBLE(this, "String.prototype.sup");
 934   return "<sup>" + TO_STRING_INLINE(this) + "</sup>";
 935 }
 936
 937 // ES6 draft 01-20-14, section 21.1.3.13
 938 function StringRepeat(count) {
 939   CHECK_OBJECT_COERCIBLE(this, "String.prototype.repeat");
 940
 941   var s = TO_STRING_INLINE(this);
 942   var n = $toInteger(count);
 943   // The maximum string length is stored in a smi, so a longer repeat
 944   // must result in a range error.
 945   if (n < 0 || n > %_MaxSmi()) throw MakeRangeError(kInvalidCountValue);
 946
 947   var r = "";
 948   while (true) {
 949     if (n & 1) r += s;
 950     n >>= 1;
 951     if (n === 0) return r;
 952     s += s;
 953   }
 954 }
 955
 956
 957 // ES6 draft 04-05-14, section 21.1.3.18
 958 function StringStartsWith(searchString /* position */) {  // length == 1
 959   CHECK_OBJECT_COERCIBLE(this, "String.prototype.startsWith");
 960
 961   var s = TO_STRING_INLINE(this);
 962
 963   if (IS_REGEXP(searchString)) {
 964     throw MakeTypeError(kFirstArgumentNotRegExp, "String.prototype.startsWith");
 965   }
 966
 967   var ss = TO_STRING_INLINE(searchString);
 968   var pos = 0;
 969   if (%_ArgumentsLength() > 1) {
 970     var arg = %_Arguments(1);  // position
 971     if (!IS_UNDEFINED(arg)) {
 972       pos = $toInteger(arg);
 973     }
 974   }
 975
 976   var s_len = s.length;
 977   if (pos < 0) pos = 0;
 978   if (pos > s_len) pos = s_len;
 979   var ss_len = ss.length;
 980
 981   if (ss_len + pos > s_len) {
 982     return false;
 983   }
 984
 985   for (var i = 0; i < ss_len; i++) {
 986     if (%_StringCharCodeAt(s, pos + i) !== %_StringCharCodeAt(ss, i)) {
 987       return false;
 988     }
 989   }
 990
 991   return true;
 992 }
 993
 994
 995 // ES6 draft 04-05-14, section 21.1.3.7
 996 function StringEndsWith(searchString /* position */) {  // length == 1
 997   CHECK_OBJECT_COERCIBLE(this, "String.prototype.endsWith");
 998
 999   var s = TO_STRING_INLINE(this);
1000
1001   if (IS_REGEXP(searchString)) {
1002     throw MakeTypeError(kFirstArgumentNotRegExp, "String.prototype.endsWith");
1003   }
1004
1005   var ss = TO_STRING_INLINE(searchString);
1006   var s_len = s.length;
1007   var pos = s_len;
1008   if (%_ArgumentsLength() > 1) {
1009     var arg = %_Arguments(1);  // position
1010     if (!IS_UNDEFINED(arg)) {
1011       pos = $toInteger(arg);
1012     }
1013   }
1014
1015   if (pos < 0) pos = 0;
1016   if (pos > s_len) pos = s_len;
1017   var ss_len = ss.length;
1018   pos = pos - ss_len;
1019
1020   if (pos < 0) {
1021     return false;
1022   }
1023
1024   for (var i = 0; i < ss_len; i++) {
1025     if (%_StringCharCodeAt(s, pos + i) !== %_StringCharCodeAt(ss, i)) {
1026       return false;
1027     }
1028   }
1029
1030   return true;
1031 }
1032
1033
1034 // ES6 draft 04-05-14, section 21.1.3.6
1035 function StringIncludes(searchString /* position */) {  // length == 1
1036   CHECK_OBJECT_COERCIBLE(this, "String.prototype.includes");
1037
1038   var string = TO_STRING_INLINE(this);
1039
1040   if (IS_REGEXP(searchString)) {
1041     throw MakeTypeError(kFirstArgumentNotRegExp, "String.prototype.includes");
1042   }
1043
1044   searchString = TO_STRING_INLINE(searchString);
1045   var pos = 0;
1046   if (%_ArgumentsLength() > 1) {
1047     pos = %_Arguments(1);  // position
1048     pos = TO_INTEGER(pos);
1049   }
1050
1051   var stringLength = string.length;
1052   if (pos < 0) pos = 0;
1053   if (pos > stringLength) pos = stringLength;
1054   var searchStringLength = searchString.length;
1055
1056   if (searchStringLength + pos > stringLength) {
1057     return false;
1058   }
1059
1060   return %StringIndexOf(string, searchString, pos) !== -1;
1061 }
1062
1063
1064 // ES6 Draft 05-22-2014, section 21.1.3.3
1065 function StringCodePointAt(pos) {
1066   CHECK_OBJECT_COERCIBLE(this, "String.prototype.codePointAt");
1067
1068   var string = TO_STRING_INLINE(this);
1069   var size = string.length;
1070   pos = TO_INTEGER(pos);
1071   if (pos < 0 || pos >= size) {
1072     return UNDEFINED;
1073   }
1074   var first = %_StringCharCodeAt(string, pos);
1075   if (first < 0xD800 || first > 0xDBFF || pos + 1 == size) {
1076     return first;
1077   }
1078   var second = %_StringCharCodeAt(string, pos + 1);
1079   if (second < 0xDC00 || second > 0xDFFF) {
1080     return first;
1081   }
1082   return (first - 0xD800) * 0x400 + second + 0x2400;
1083 }
1084
1085
1086 // ES6 Draft 05-22-2014, section 21.1.2.2
1087 function StringFromCodePoint(_) {  // length = 1
1088   var code;
1089   var length = %_ArgumentsLength();
1090   var index;
1091   var result = "";
1092   for (index = 0; index < length; index++) {
1093     code = %_Arguments(index);
1094     if (!%_IsSmi(code)) {
1095       code = ToNumber(code);
1096     }
1097     if (code < 0 || code > 0x10FFFF || code !== TO_INTEGER(code)) {
1098       throw MakeRangeError(kInvalidCodePoint, code);
1099     }
1100     if (code <= 0xFFFF) {
1101       result += %_StringCharFromCode(code);
1102     } else {
1103       code -= 0x10000;
1104       result += %_StringCharFromCode((code >>> 10) & 0x3FF | 0xD800);
1105       result += %_StringCharFromCode(code & 0x3FF | 0xDC00);
1106     }
1107   }
1108   return result;
1109 }
1110
1111
1112 // -------------------------------------------------------------------
1113 // String methods related to templates
1114
1115 // ES6 Draft 03-17-2015, section 21.1.2.4
1116 function StringRaw(callSite) {
1117   // TODO(caitp): Use rest parameters when implemented
1118   var numberOfSubstitutions = %_ArgumentsLength();
1119   var cooked = TO_OBJECT(callSite);
1120   var raw = TO_OBJECT(cooked.raw);
1121   var literalSegments = $toLength(raw.length);
1122   if (literalSegments <= 0) return "";
1123
1124   var result = ToString(raw[0]);
1125
1126   for (var i = 1; i < literalSegments; ++i) {
1127     if (i < numberOfSubstitutions) {
1128       result += ToString(%_Arguments(i));
1129     }
1130     result += ToString(raw[i]);
1131   }
1132
1133   return result;
1134 }
1135
1136 // -------------------------------------------------------------------
1137
1138 // Set the String function and constructor.
1139 %FunctionSetPrototype(GlobalString, new GlobalString());
1140
1141 // Set up the constructor property on the String prototype object.
1142 %AddNamedProperty(
1143     GlobalString.prototype, "constructor", GlobalString, DONT_ENUM);
1144
1145 // Set up the non-enumerable functions on the String object.
1146 utils.InstallFunctions(GlobalString, DONT_ENUM, [
1147   "fromCharCode", StringFromCharCode,
1148   "fromCodePoint", StringFromCodePoint,
1149   "raw", StringRaw
1150 ]);
1151
1152 // Set up the non-enumerable functions on the String prototype object.
1153 utils.InstallFunctions(GlobalString.prototype, DONT_ENUM, [
1154   "valueOf", StringValueOf,
1155   "toString", StringToString,
1156   "charAt", StringCharAtJS,
1157   "charCodeAt", StringCharCodeAtJS,
1158   "codePointAt", StringCodePointAt,
1159   "concat", StringConcat,
1160   "endsWith", StringEndsWith,
1161   "includes", StringIncludes,
1162   "indexOf", StringIndexOfJS,
1163   "lastIndexOf", StringLastIndexOfJS,
1164   "localeCompare", StringLocaleCompareJS,
1165   "match", StringMatchJS,
1166   "normalize", StringNormalizeJS,
1167   "repeat", StringRepeat,
1168   "replace", StringReplace,
1169   "search", StringSearch,
1170   "slice", StringSlice,
1171   "split", StringSplitJS,
1172   "substring", StringSubstring,
1173   "substr", StringSubstr,
1174   "startsWith", StringStartsWith,
1175   "toLowerCase", StringToLowerCaseJS,
1176   "toLocaleLowerCase", StringToLocaleLowerCase,
1177   "toUpperCase", StringToUpperCaseJS,
1178   "toLocaleUpperCase", StringToLocaleUpperCase,
1179   "trim", StringTrimJS,
1180   "trimLeft", StringTrimLeft,
1181   "trimRight", StringTrimRight,
1182
1183   "link", StringLink,
1184   "anchor", StringAnchor,
1185   "fontcolor", StringFontcolor,
1186   "fontsize", StringFontsize,
1187   "big", StringBig,
1188   "blink", StringBlink,
1189   "bold", StringBold,
1190   "fixed", StringFixed,
1191   "italics", StringItalics,
1192   "small", StringSmall,
1193   "strike", StringStrike,
1194   "sub", StringSub,
1195   "sup", StringSup
1196 ]);
1197
1198 // -------------------------------------------------------------------
1199 // Exports
1200
1201 utils.Export(function(to) {
1202   to.StringCharAt = StringCharAtJS;
1203   to.StringIndexOf = StringIndexOfJS;
1204   to.StringLastIndexOf = StringLastIndexOfJS;
1205   to.StringMatch = StringMatchJS;
1206   to.StringReplace = StringReplace;
1207   to.StringSlice = StringSlice;
1208   to.StringSplit = StringSplitJS;
1209   to.StringSubstr = StringSubstr;
1210   to.StringSubstring = StringSubstring;
1211 });
1212
1213 })