The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

  * vim: set ts=8 sts=4 et sw=4 tw=99:

  * This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 /*

  * JS string type implementation.

  *

  * In order to avoid unnecessary js_LockGCThing/js_UnlockGCThing calls, these

  * native methods store strings (possibly newborn) converted from their 'this'

  * parameter and arguments on the stack: 'this' conversions at argv[-1], arg

  * conversions at their index (argv[0], argv[1]).  This is a legitimate method

  * of rooting things that might lose their newborn root due to subsequent GC

  * allocations in the same native method.

  */

 #include "jsstr.h"

 #include "mozilla/Attributes.h"

 #include "mozilla/Casting.h"

 #include "mozilla/CheckedInt.h"

 #include "mozilla/FloatingPoint.h"

 #include "mozilla/PodOperations.h"

 #include <ctype.h>

 #include <string.h>

 #include "jsapi.h"

 #include "jsarray.h"

 #include "jsatom.h"

 #include "jsbool.h"

 #include "jscntxt.h"

 #include "jsgc.h"

 #include "jsnum.h"

 #include "jsobj.h"

 #include "jsopcode.h"

 #include "jstypes.h"

 #include "jsutil.h"

 #include "builtin/Intl.h"

 #include "builtin/RegExp.h"

 #if ENABLE_INTL_API

 #include "unicode/unorm.h"

 #endif

 #include "vm/GlobalObject.h"

 #include "vm/Interpreter.h"

 #include "vm/NumericConversions.h"

 #include "vm/Opcodes.h"

 #include "vm/RegExpObject.h"

 #include "vm/RegExpStatics.h"

 #include "vm/ScopeObject.h"

 #include "vm/StringBuffer.h"

 #include "jsinferinlines.h"

 #include "vm/Interpreter-inl.h"

 #include "vm/String-inl.h"

 #include "vm/StringObject-inl.h"

 using namespace js;

 using namespace js::gc;

 using namespace js::types;

 using namespace js::unicode;

 using mozilla::CheckedInt;

 using mozilla::IsNaN;

 using mozilla::IsNegativeZero;

 using mozilla::PodCopy;

 using mozilla::PodEqual;

 using mozilla::SafeCast;

 typedef Handle<JSLinearString*> HandleLinearString;

 static JSLinearString *

 ArgToRootedString(JSContext *cx, CallArgs &args, unsigned argno)

 {

     if (argno >= args.length())

         return cx->names().undefined;

     JSString *str = ToString<CanGC>(cx, args[argno]);

     if (!str)

         return nullptr;

     args[argno].setString(str);

     return str->ensureLinear(cx);

 }

 /*

  * Forward declarations for URI encode/decode and helper routines

  */

 static bool

 str_decodeURI(JSContext *cx, unsigned argc, Value *vp);

 static bool

 str_decodeURI_Component(JSContext *cx, unsigned argc, Value *vp);

 static bool

 str_encodeURI(JSContext *cx, unsigned argc, Value *vp);

 static bool

 str_encodeURI_Component(JSContext *cx, unsigned argc, Value *vp);

 /*

  * Global string methods

  */

 /* ES5 B.2.1 */

 static bool

 str_escape(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     static const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7',

                                   '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };

     JSLinearString *str = ArgToRootedString(cx, args, 0);

     if (!str)

         return false;

     size_t length = str->length();

     const jschar *chars = str->chars();

     static const uint8_t shouldPassThrough[256] = {

          0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

          0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

          0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,1,       /*    !"#$%&'()*+,-./  */

          1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,       /*   0123456789:;<=>?  */

          1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,       /*   @ABCDEFGHIJKLMNO  */

          1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,       /*   PQRSTUVWXYZ[\]^_  */

          0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,       /*   `abcdefghijklmno  */

          1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,     /*   pqrstuvwxyz{\}~  DEL */

     };

     /* In step 7, exactly 69 characters should pass through unencoded. */

 #ifdef DEBUG

     size_t count = 0;

     for (size_t i = 0; i < sizeof(shouldPassThrough); i++) {

         if (shouldPassThrough[i]) {

             count++;

         }

     }

     JS_ASSERT(count == 69);

 #endif

     /* Take a first pass and see how big the result string will need to be. */

     size_t newlength = length;

     for (size_t i = 0; i < length; i++) {

         jschar ch = chars[i];

         if (ch < 128 && shouldPassThrough[ch])

             continue;

         /* The character will be encoded as %XX or %uXXXX. */

         newlength += (ch < 256) ? 2 : 5;

         /*

          * This overflow test works because newlength is incremented by at

          * most 5 on each iteration.

          */

         if (newlength < length) {

             js_ReportAllocationOverflow(cx);

             return false;

         }

     }

     if (newlength >= ~(size_t)0 / sizeof(jschar)) {

         js_ReportAllocationOverflow(cx);

         return false;

     }

     jschar *newchars = cx->pod_malloc<jschar>(newlength + 1);

     if (!newchars)

         return false;

     size_t i, ni;

     for (i = 0, ni = 0; i < length; i++) {

         jschar ch = chars[i];

         if (ch < 128 && shouldPassThrough[ch]) {

             newchars[ni++] = ch;

         } else if (ch < 256) {

             newchars[ni++] = '%';

             newchars[ni++] = digits[ch >> 4];

             newchars[ni++] = digits[ch & 0xF];

         } else {

             newchars[ni++] = '%';

             newchars[ni++] = 'u';

             newchars[ni++] = digits[ch >> 12];

             newchars[ni++] = digits[(ch & 0xF00) >> 8];

             newchars[ni++] = digits[(ch & 0xF0) >> 4];

             newchars[ni++] = digits[ch & 0xF];

         }

     }

     JS_ASSERT(ni == newlength);

     newchars[newlength] = 0;

     JSString *retstr = js_NewString<CanGC>(cx, newchars, newlength);

     if (!retstr) {

         js_free(newchars);

         return false;

     }

     args.rval().setString(retstr);

     return true;

 }

 static inline bool

 Unhex4(const jschar *chars, jschar *result)

 {

     jschar a = chars[0],

            b = chars[1],

            c = chars[2],

            d = chars[3];

     if (!(JS7_ISHEX(a) && JS7_ISHEX(b) && JS7_ISHEX(c) && JS7_ISHEX(d)))

         return false;

     *result = (((((JS7_UNHEX(a) << 4) + JS7_UNHEX(b)) << 4) + JS7_UNHEX(c)) << 4) + JS7_UNHEX(d);

     return true;

 }

 static inline bool

 Unhex2(const jschar *chars, jschar *result)

 {

     jschar a = chars[0],

            b = chars[1];

     if (!(JS7_ISHEX(a) && JS7_ISHEX(b)))

         return false;

     *result = (JS7_UNHEX(a) << 4) + JS7_UNHEX(b);

     return true;

 }

 /* ES5 B.2.2 */

 static bool

 str_unescape(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     /* Step 1. */

     JSLinearString *str = ArgToRootedString(cx, args, 0);

     if (!str)

         return false;

     /*

      * NB: use signed integers for length/index to allow simple length

      * comparisons without unsigned-underflow hazards.

      */

     JS_STATIC_ASSERT(JSString::MAX_LENGTH <= INT_MAX);

     /* Step 2. */

     int length = str->length();

     const jschar *chars = str->chars();

     /* Step 3. */

     StringBuffer sb(cx);

     /*

      * Note that the spec algorithm has been optimized to avoid building

      * a string in the case where no escapes are present.

      */

     /* Step 4. */

     int k = 0;

     bool building = false;

     while (true) {

         /* Step 5. */

         if (k == length) {

             JSLinearString *result;

             if (building) {

                 result = sb.finishString();

                 if (!result)

                     return false;

             } else {

                 result = str;

             }

             args.rval().setString(result);

             return true;

         }

         /* Step 6. */

         jschar c = chars[k];

         /* Step 7. */

         if (c != '%')

             goto step_18;

         /* Step 8. */

         if (k > length - 6)

             goto step_14;

         /* Step 9. */

         if (chars[k + 1] != 'u')

             goto step_14;

 #define ENSURE_BUILDING                             \

     JS_BEGIN_MACRO                                  \

         if (!building) {                            \

             building = true;                        \

             if (!sb.reserve(length))                \

                 return false;                       \

             sb.infallibleAppend(chars, chars + k);  \

         }                                           \

     JS_END_MACRO

         /* Step 10-13. */

         if (Unhex4(&chars[k + 2], &c)) {

             ENSURE_BUILDING;

             k += 5;

             goto step_18;

         }

       step_14:

         /* Step 14. */

         if (k > length - 3)

             goto step_18;

         /* Step 15-17. */

         if (Unhex2(&chars[k + 1], &c)) {

             ENSURE_BUILDING;

             k += 2;

         }

       step_18:

         if (building)

             sb.infallibleAppend(c);

         /* Step 19. */

         k += 1;

     }

 #undef ENSURE_BUILDING

 }

 #if JS_HAS_UNEVAL

 static bool

 str_uneval(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     JSString *str = ValueToSource(cx, args.get(0));

     if (!str)

         return false;

     args.rval().setString(str);

     return true;

 }

 #endif

 static const JSFunctionSpec string_functions[] = {

     JS_FN(js_escape_str,             str_escape,                1,0),

     JS_FN(js_unescape_str,           str_unescape,              1,0),

 #if JS_HAS_UNEVAL

     JS_FN(js_uneval_str,             str_uneval,                1,0),

 #endif

     JS_FN(js_decodeURI_str,          str_decodeURI,             1,0),

     JS_FN(js_encodeURI_str,          str_encodeURI,             1,0),

     JS_FN(js_decodeURIComponent_str, str_decodeURI_Component,   1,0),

     JS_FN(js_encodeURIComponent_str, str_encodeURI_Component,   1,0),

     JS_FS_END

 };

 const jschar      js_empty_ucstr[]  = {0};

 const JSSubString js_EmptySubString = {0, js_empty_ucstr};

 static const unsigned STRING_ELEMENT_ATTRS = JSPROP_ENUMERATE | JSPROP_READONLY | JSPROP_PERMANENT;

 static bool

 str_enumerate(JSContext *cx, HandleObject obj)

 {

     RootedString str(cx, obj->as<StringObject>().unbox());

     RootedValue value(cx);

     for (size_t i = 0, length = str->length(); i < length; i++) {

         JSString *str1 = js_NewDependentString(cx, str, i, 1);

         if (!str1)

             return false;

         value.setString(str1);

         if (!JSObject::defineElement(cx, obj, i, value,

                                      JS_PropertyStub, JS_StrictPropertyStub,

                                      STRING_ELEMENT_ATTRS))

         {

             return false;

         }

     }

     return true;

 }

 bool

 js::str_resolve(JSContext *cx, HandleObject obj, HandleId id, MutableHandleObject objp)

 {

     if (!JSID_IS_INT(id))

         return true;

     RootedString str(cx, obj->as<StringObject>().unbox());

     int32_t slot = JSID_TO_INT(id);

     if ((size_t)slot < str->length()) {

         JSString *str1 = cx->staticStrings().getUnitStringForElement(cx, str, size_t(slot));

         if (!str1)

             return false;

         RootedValue value(cx, StringValue(str1));

         if (!JSObject::defineElement(cx, obj, uint32_t(slot), value, nullptr, nullptr,

                                      STRING_ELEMENT_ATTRS))

         {

             return false;

         }

         objp.set(obj);

     }

     return true;

 }

 const Class StringObject::class_ = {

     js_String_str,

     JSCLASS_HAS_RESERVED_SLOTS(StringObject::RESERVED_SLOTS) |

     JSCLASS_NEW_RESOLVE | JSCLASS_HAS_CACHED_PROTO(JSProto_String),

     JS_PropertyStub,         /* addProperty */

     JS_DeletePropertyStub,   /* delProperty */

     JS_PropertyStub,         /* getProperty */

     JS_StrictPropertyStub,   /* setProperty */

     str_enumerate,

     (JSResolveOp)str_resolve,

     JS_ConvertStub

 };

 /*

  * Returns a JSString * for the |this| value associated with 'call', or throws

  * a TypeError if |this| is null or undefined.  This algorithm is the same as

  * calling CheckObjectCoercible(this), then returning ToString(this), as all

  * String.prototype.* methods do (other than toString and valueOf).

  */

 static MOZ_ALWAYS_INLINE JSString *

 ThisToStringForStringProto(JSContext *cx, CallReceiver call)

 {

     JS_CHECK_RECURSION(cx, return nullptr);

     if (call.thisv().isString())

         return call.thisv().toString();

     if (call.thisv().isObject()) {

         RootedObject obj(cx, &call.thisv().toObject());

         if (obj->is<StringObject>()) {

             Rooted<jsid> id(cx, NameToId(cx->names().toString));

             if (ClassMethodIsNative(cx, obj, &StringObject::class_, id, js_str_toString)) {

                 JSString *str = obj->as<StringObject>().unbox();

                 call.setThis(StringValue(str));

                 return str;

             }

         }

     } else if (call.thisv().isNullOrUndefined()) {

         JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_CANT_CONVERT_TO,

                              call.thisv().isNull() ? "null" : "undefined", "object");

         return nullptr;

     }

     JSString *str = ToStringSlow<CanGC>(cx, call.thisv());

     if (!str)

         return nullptr;

     call.setThis(StringValue(str));

     return str;

 }

 MOZ_ALWAYS_INLINE bool

 IsString(HandleValue v)

 {

     return v.isString() || (v.isObject() && v.toObject().is<StringObject>());

 }

 #if JS_HAS_TOSOURCE

 /*

  * String.prototype.quote is generic (as are most string methods), unlike

  * toSource, toString, and valueOf.

  */

 static bool

 str_quote(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     str = js_QuoteString(cx, str, '"');

     if (!str)

         return false;

     args.rval().setString(str);

     return true;

 }

 MOZ_ALWAYS_INLINE bool

 str_toSource_impl(JSContext *cx, CallArgs args)

 {

     JS_ASSERT(IsString(args.thisv()));

     Rooted<JSString*> str(cx, ToString<CanGC>(cx, args.thisv()));

     if (!str)

         return false;

     str = js_QuoteString(cx, str, '"');

     if (!str)

         return false;

     StringBuffer sb(cx);

     if (!sb.append("(new String(") || !sb.append(str) || !sb.append("))"))

         return false;

     str = sb.finishString();

     if (!str)

         return false;

     args.rval().setString(str);

     return true;

 }

 static bool

 str_toSource(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     return CallNonGenericMethod<IsString, str_toSource_impl>(cx, args);

 }

 #endif /* JS_HAS_TOSOURCE */

 MOZ_ALWAYS_INLINE bool

 str_toString_impl(JSContext *cx, CallArgs args)

 {

     JS_ASSERT(IsString(args.thisv()));

     args.rval().setString(args.thisv().isString()

                               ? args.thisv().toString()

                               : args.thisv().toObject().as<StringObject>().unbox());

     return true;

 }

 bool

 js_str_toString(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     return CallNonGenericMethod<IsString, str_toString_impl>(cx, args);

 }

 /*

  * Java-like string native methods.

  */

 static MOZ_ALWAYS_INLINE bool

 ValueToIntegerRange(JSContext *cx, HandleValue v, int32_t *out)

 {

     if (v.isInt32()) {

         *out = v.toInt32();

     } else {

         double d;

         if (!ToInteger(cx, v, &d))

             return false;

         if (d > INT32_MAX)

             *out = INT32_MAX;

         else if (d < INT32_MIN)

             *out = INT32_MIN;

         else

             *out = int32_t(d);

     }

     return true;

 }

 static JSString *

 DoSubstr(JSContext *cx, JSString *str, size_t begin, size_t len)

 {

     /*

      * Optimization for one level deep ropes.

      * This is common for the following pattern:

      *

      * while() {

      *   text = text.substr(0, x) + "bla" + text.substr(x)

      *   test.charCodeAt(x + 1)

      * }

      */

     if (str->isRope()) {

         JSRope *rope = &str->asRope();

         /* Substring is totally in leftChild of rope. */

         if (begin + len <= rope->leftChild()->length()) {

             str = rope->leftChild();

             return js_NewDependentString(cx, str, begin, len);

         }

         /* Substring is totally in rightChild of rope. */

         if (begin >= rope->leftChild()->length()) {

             str = rope->rightChild();

             begin -= rope->leftChild()->length();

             return js_NewDependentString(cx, str, begin, len);

         }

         /*

          * Requested substring is partly in the left and partly in right child.

          * Create a rope of substrings for both childs.

          */

         JS_ASSERT (begin < rope->leftChild()->length() &&

                    begin + len > rope->leftChild()->length());

         size_t lhsLength = rope->leftChild()->length() - begin;

         size_t rhsLength = begin + len - rope->leftChild()->length();

         Rooted<JSRope *> ropeRoot(cx, rope);

         RootedString lhs(cx, js_NewDependentString(cx, ropeRoot->leftChild(),

                                                    begin, lhsLength));

         if (!lhs)

             return nullptr;

         RootedString rhs(cx, js_NewDependentString(cx, ropeRoot->rightChild(), 0, rhsLength));

         if (!rhs)

             return nullptr;

         return JSRope::new_<CanGC>(cx, lhs, rhs, len);

     }

     return js_NewDependentString(cx, str, begin, len);

 }

 static bool

 str_substring(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     JSString *str = ThisToStringForStringProto(cx, args);

     if (!str)

         return false;

     int32_t length, begin, end;

     if (args.length() > 0) {

         end = length = int32_t(str->length());

         if (args[0].isInt32()) {

             begin = args[0].toInt32();

         } else {

             RootedString strRoot(cx, str);

             if (!ValueToIntegerRange(cx, args[0], &begin))

                 return false;

             str = strRoot;

         }

         if (begin < 0)

             begin = 0;

         else if (begin > length)

             begin = length;

         if (args.hasDefined(1)) {

             if (args[1].isInt32()) {

                 end = args[1].toInt32();

             } else {

                 RootedString strRoot(cx, str);

                 if (!ValueToIntegerRange(cx, args[1], &end))

                     return false;

                 str = strRoot;

             }

             if (end > length) {

                 end = length;

             } else {

                 if (end < 0)

                     end = 0;

                 if (end < begin) {

                     int32_t tmp = begin;

                     begin = end;

                     end = tmp;

                 }

             }

         }

         str = DoSubstr(cx, str, size_t(begin), size_t(end - begin));

         if (!str)

             return false;

     }

     args.rval().setString(str);

     return true;

 }

 JSString* JS_FASTCALL

 js_toLowerCase(JSContext *cx, JSString *str)

 {

     size_t n = str->length();

     const jschar *s = str->getChars(cx);

     if (!s)

         return nullptr;

     jschar *news = cx->pod_malloc<jschar>(n + 1);

     if (!news)

         return nullptr;

     for (size_t i = 0; i < n; i++)

         news[i] = unicode::ToLowerCase(s[i]);

     news[n] = 0;

     str = js_NewString<CanGC>(cx, news, n);

     if (!str) {

         js_free(news);

         return nullptr;

     }

     return str;

 }

 static inline bool

 ToLowerCaseHelper(JSContext *cx, CallReceiver call)

 {

     RootedString str(cx, ThisToStringForStringProto(cx, call));

     if (!str)

         return false;

     str = js_toLowerCase(cx, str);

     if (!str)

         return false;

     call.rval().setString(str);

     return true;

 }

 static bool

 str_toLowerCase(JSContext *cx, unsigned argc, Value *vp)

 {

     return ToLowerCaseHelper(cx, CallArgsFromVp(argc, vp));

 }

 static bool

 str_toLocaleLowerCase(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     /*

      * Forcefully ignore the first (or any) argument and return toLowerCase(),

      * ECMA has reserved that argument, presumably for defining the locale.

      */

     if (cx->runtime()->localeCallbacks && cx->runtime()->localeCallbacks->localeToLowerCase) {

         RootedString str(cx, ThisToStringForStringProto(cx, args));

         if (!str)

             return false;

         RootedValue result(cx);

         if (!cx->runtime()->localeCallbacks->localeToLowerCase(cx, str, &result))

             return false;

         args.rval().set(result);

         return true;

     }

     return ToLowerCaseHelper(cx, args);

 }

 JSString* JS_FASTCALL

 js_toUpperCase(JSContext *cx, JSString *str)

 {

     size_t n = str->length();

     const jschar *s = str->getChars(cx);

     if (!s)

         return nullptr;

     jschar *news = cx->pod_malloc<jschar>(n + 1);

     if (!news)

         return nullptr;

     for (size_t i = 0; i < n; i++)

         news[i] = unicode::ToUpperCase(s[i]);

     news[n] = 0;

     str = js_NewString<CanGC>(cx, news, n);

     if (!str) {

         js_free(news);

         return nullptr;

     }

     return str;

 }

 static bool

 ToUpperCaseHelper(JSContext *cx, CallReceiver call)

 {

     RootedString str(cx, ThisToStringForStringProto(cx, call));

     if (!str)

         return false;

     str = js_toUpperCase(cx, str);

     if (!str)

         return false;

     call.rval().setString(str);

     return true;

 }

 static bool

 str_toUpperCase(JSContext *cx, unsigned argc, Value *vp)

 {

     return ToUpperCaseHelper(cx, CallArgsFromVp(argc, vp));

 }

 static bool

 str_toLocaleUpperCase(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     /*

      * Forcefully ignore the first (or any) argument and return toUpperCase(),

      * ECMA has reserved that argument, presumably for defining the locale.

      */

     if (cx->runtime()->localeCallbacks && cx->runtime()->localeCallbacks->localeToUpperCase) {

         RootedString str(cx, ThisToStringForStringProto(cx, args));

         if (!str)

             return false;

         RootedValue result(cx);

         if (!cx->runtime()->localeCallbacks->localeToUpperCase(cx, str, &result))

             return false;

         args.rval().set(result);

         return true;

     }

     return ToUpperCaseHelper(cx, args);

 }

 #if !EXPOSE_INTL_API

 static bool

 str_localeCompare(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     RootedString thatStr(cx, ToString<CanGC>(cx, args.get(0)));

     if (!thatStr)

         return false;

     if (cx->runtime()->localeCallbacks && cx->runtime()->localeCallbacks->localeCompare) {

         RootedValue result(cx);

         if (!cx->runtime()->localeCallbacks->localeCompare(cx, str, thatStr, &result))

             return false;

         args.rval().set(result);

         return true;

     }

     int32_t result;

     if (!CompareStrings(cx, str, thatStr, &result))

         return false;

     args.rval().setInt32(result);

     return true;

 }

 #endif

 #if EXPOSE_INTL_API

 static const size_t SB_LENGTH = 32;

 /* ES6 20140210 draft 21.1.3.12. */

 static bool

 str_normalize(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     // Steps 1-3.

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     // Step 4.

     UNormalizationMode form;

     if (!args.hasDefined(0)) {

         form = UNORM_NFC;

     } else {

         // Steps 5-6.

         Rooted<JSLinearString*> formStr(cx, ArgToRootedString(cx, args, 0));

         if (!formStr)

             return false;

         // Step 7.

         if (formStr == cx->names().NFC) {

             form = UNORM_NFC;

         } else if (formStr == cx->names().NFD) {

             form = UNORM_NFD;

         } else if (formStr == cx->names().NFKC) {

             form = UNORM_NFKC;

         } else if (formStr == cx->names().NFKD) {

             form = UNORM_NFKD;

         } else {

             JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr,

                                  JSMSG_INVALID_NORMALIZE_FORM);

             return false;

         }

     }

     // Step 8.

     Rooted<JSFlatString*> flatStr(cx, str->ensureFlat(cx));

     if (!flatStr)

         return false;

     const UChar *srcChars = JSCharToUChar(flatStr->chars());

     int32_t srcLen = SafeCast<int32_t>(flatStr->length());

     StringBuffer chars(cx);

     if (!chars.resize(SB_LENGTH))

         return false;

     UErrorCode status = U_ZERO_ERROR;

     int32_t size = unorm_normalize(srcChars, srcLen, form, 0,

                                    JSCharToUChar(chars.begin()), SB_LENGTH,

                                    &status);

     if (status == U_BUFFER_OVERFLOW_ERROR) {

         if (!chars.resize(size))

             return false;

         status = U_ZERO_ERROR;

 #ifdef DEBUG

         int32_t finalSize =

 #endif

         unorm_normalize(srcChars, srcLen, form, 0,

                         JSCharToUChar(chars.begin()), size,

                         &status);

         MOZ_ASSERT(size == finalSize || U_FAILURE(status), "unorm_normalize behaved inconsistently");

     }

     if (U_FAILURE(status))

         return false;

     // Trim any unused characters.

     if (!chars.resize(size))

         return false;

     RootedString ns(cx, chars.finishString());

     if (!ns)

         return false;

     // Step 9.

     args.rval().setString(ns);

     return true;

 }

 #endif

 bool

 js_str_charAt(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     RootedString str(cx);

     size_t i;

     if (args.thisv().isString() && args.length() != 0 && args[0].isInt32()) {

         str = args.thisv().toString();

         i = size_t(args[0].toInt32());

         if (i >= str->length())

             goto out_of_range;

     } else {

         str = ThisToStringForStringProto(cx, args);

         if (!str)

             return false;

         double d = 0.0;

         if (args.length() > 0 && !ToInteger(cx, args[0], &d))

             return false;

         if (d < 0 || str->length() <= d)

             goto out_of_range;

         i = size_t(d);

     }

     str = cx->staticStrings().getUnitStringForElement(cx, str, i);

     if (!str)

         return false;

     args.rval().setString(str);

     return true;

   out_of_range:

     args.rval().setString(cx->runtime()->emptyString);

     return true;

 }

 bool

 js_str_charCodeAt(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     RootedString str(cx);

     size_t i;

     if (args.thisv().isString() && args.length() != 0 && args[0].isInt32()) {

         str = args.thisv().toString();

         i = size_t(args[0].toInt32());

         if (i >= str->length())

             goto out_of_range;

     } else {

         str = ThisToStringForStringProto(cx, args);

         if (!str)

             return false;

         double d = 0.0;

         if (args.length() > 0 && !ToInteger(cx, args[0], &d))

             return false;

         if (d < 0 || str->length() <= d)

             goto out_of_range;

         i = size_t(d);

     }

     jschar c;

     if (!str->getChar(cx, i, &c))

         return false;

     args.rval().setInt32(c);

     return true;

 out_of_range:

     args.rval().setNaN();

     return true;

 }

 /*

  * Boyer-Moore-Horspool superlinear search for pat:patlen in text:textlen.

  * The patlen argument must be positive and no greater than sBMHPatLenMax.

  *

  * Return the index of pat in text, or -1 if not found.

  */

 static const uint32_t sBMHCharSetSize = 256; /* ISO-Latin-1 */

 static const uint32_t sBMHPatLenMax   = 255; /* skip table element is uint8_t */

 static const int      sBMHBadPattern  = -2;  /* return value if pat is not ISO-Latin-1 */

 int

 js_BoyerMooreHorspool(const jschar *text, uint32_t textlen,

                       const jschar *pat, uint32_t patlen)

 {

     uint8_t skip[sBMHCharSetSize];

     JS_ASSERT(0 < patlen && patlen <= sBMHPatLenMax);

     for (uint32_t i = 0; i < sBMHCharSetSize; i++)

         skip[i] = (uint8_t)patlen;

     uint32_t m = patlen - 1;

     for (uint32_t i = 0; i < m; i++) {

         jschar c = pat[i];

         if (c >= sBMHCharSetSize)

             return sBMHBadPattern;

         skip[c] = (uint8_t)(m - i);

     }

     jschar c;

     for (uint32_t k = m;

          k < textlen;

          k += ((c = text[k]) >= sBMHCharSetSize) ? patlen : skip[c]) {

         for (uint32_t i = k, j = m; ; i--, j--) {

             if (text[i] != pat[j])

                 break;

             if (j == 0)

                 return static_cast<int>(i);  /* safe: max string size */

         }

     }

     return -1;

 }

 struct MemCmp {

     typedef uint32_t Extent;

     static MOZ_ALWAYS_INLINE Extent computeExtent(const jschar *, uint32_t patlen) {

         return (patlen - 1) * sizeof(jschar);

     }

     static MOZ_ALWAYS_INLINE bool match(const jschar *p, const jschar *t, Extent extent) {

         return memcmp(p, t, extent) == 0;

     }

 };

 struct ManualCmp {

     typedef const jschar *Extent;

     static MOZ_ALWAYS_INLINE Extent computeExtent(const jschar *pat, uint32_t patlen) {

         return pat + patlen;

     }

     static MOZ_ALWAYS_INLINE bool match(const jschar *p, const jschar *t, Extent extent) {

         for (; p != extent; ++p, ++t) {

             if (*p != *t)

                 return false;

         }

         return true;

     }

 };

 template <class InnerMatch>

 static int

 UnrolledMatch(const jschar *text, uint32_t textlen, const jschar *pat, uint32_t patlen)

 {

     JS_ASSERT(patlen > 0 && textlen > 0);

     const jschar *textend = text + textlen - (patlen - 1);

     const jschar p0 = *pat;

     const jschar *const patNext = pat + 1;

     const typename InnerMatch::Extent extent = InnerMatch::computeExtent(pat, patlen);

     uint8_t fixup;

     const jschar *t = text;

     switch ((textend - t) & 7) {

       case 0: if (*t++ == p0) { fixup = 8; goto match; }

       case 7: if (*t++ == p0) { fixup = 7; goto match; }

       case 6: if (*t++ == p0) { fixup = 6; goto match; }

       case 5: if (*t++ == p0) { fixup = 5; goto match; }

       case 4: if (*t++ == p0) { fixup = 4; goto match; }

       case 3: if (*t++ == p0) { fixup = 3; goto match; }

       case 2: if (*t++ == p0) { fixup = 2; goto match; }

       case 1: if (*t++ == p0) { fixup = 1; goto match; }

     }

     while (t != textend) {

       if (t[0] == p0) { t += 1; fixup = 8; goto match; }

       if (t[1] == p0) { t += 2; fixup = 7; goto match; }

       if (t[2] == p0) { t += 3; fixup = 6; goto match; }

       if (t[3] == p0) { t += 4; fixup = 5; goto match; }

       if (t[4] == p0) { t += 5; fixup = 4; goto match; }

       if (t[5] == p0) { t += 6; fixup = 3; goto match; }

       if (t[6] == p0) { t += 7; fixup = 2; goto match; }

       if (t[7] == p0) { t += 8; fixup = 1; goto match; }

         t += 8;

         continue;

         do {

             if (*t++ == p0) {

               match:

                 if (!InnerMatch::match(patNext, t, extent))

                     goto failed_match;

                 return t - text - 1;

             }

           failed_match:;

         } while (--fixup > 0);

     }

     return -1;

 }

 static MOZ_ALWAYS_INLINE int

 StringMatch(const jschar *text, uint32_t textlen,

             const jschar *pat, uint32_t patlen)

 {

     if (patlen == 0)

         return 0;

     if (textlen < patlen)

         return -1;

 #if defined(__i386__) || defined(_M_IX86) || defined(__i386)

     /*

      * Given enough registers, the unrolled loop below is faster than the

      * following loop. 32-bit x86 does not have enough registers.

      */

     if (patlen == 1) {

         const jschar p0 = *pat;

         for (const jschar *c = text, *end = text + textlen; c != end; ++c) {

             if (*c == p0)

                 return c - text;

         }

         return -1;

     }

 #endif

     /*

      * If the text or pattern string is short, BMH will be more expensive than

      * the basic linear scan due to initialization cost and a more complex loop

      * body. While the correct threshold is input-dependent, we can make a few

      * conservative observations:

      *  - When |textlen| is "big enough", the initialization time will be

      *    proportionally small, so the worst-case slowdown is minimized.

      *  - When |patlen| is "too small", even the best case for BMH will be

      *    slower than a simple scan for large |textlen| due to the more complex

      *    loop body of BMH.

      * From this, the values for "big enough" and "too small" are determined

      * empirically. See bug 526348.

      */

     if (textlen >= 512 && patlen >= 11 && patlen <= sBMHPatLenMax) {

         int index = js_BoyerMooreHorspool(text, textlen, pat, patlen);

         if (index != sBMHBadPattern)

             return index;

     }

     /*

      * For big patterns with large potential overlap we want the SIMD-optimized

      * speed of memcmp. For small patterns, a simple loop is faster.

      *

      * FIXME: Linux memcmp performance is sad and the manual loop is faster.

      */

     return

 #if !defined(__linux__)

            patlen > 128 ? UnrolledMatch<MemCmp>(text, textlen, pat, patlen)

                         :

 #endif

                           UnrolledMatch<ManualCmp>(text, textlen, pat, patlen);

 }

 static const size_t sRopeMatchThresholdRatioLog2 = 5;

 bool

 js::StringHasPattern(const jschar *text, uint32_t textlen,

                      const jschar *pat, uint32_t patlen)

 {

     return StringMatch(text, textlen, pat, patlen) != -1;

 }

 // When an algorithm does not need a string represented as a single linear

 // array of characters, this range utility may be used to traverse the string a

 // sequence of linear arrays of characters. This avoids flattening ropes.

 class StringSegmentRange

 {

     // If malloc() shows up in any profiles from this vector, we can add a new

     // StackAllocPolicy which stashes a reusable freed-at-gc buffer in the cx.

     AutoStringVector stack;

     Rooted<JSLinearString*> cur;

     bool settle(JSString *str) {

         while (str->isRope()) {

             JSRope &rope = str->asRope();

             if (!stack.append(rope.rightChild()))

                 return false;

             str = rope.leftChild();

         }

         cur = &str->asLinear();

         return true;

     }

   public:

     StringSegmentRange(JSContext *cx)

       : stack(cx), cur(cx)

     {}

     MOZ_WARN_UNUSED_RESULT bool init(JSString *str) {

         JS_ASSERT(stack.empty());

         return settle(str);

     }

     bool empty() const {

         return cur == nullptr;

     }

     JSLinearString *front() const {

         JS_ASSERT(!cur->isRope());

         return cur;

     }

     MOZ_WARN_UNUSED_RESULT bool popFront() {

         JS_ASSERT(!empty());

         if (stack.empty()) {

             cur = nullptr;

             return true;

         }

         return settle(stack.popCopy());

     }

 };

 /*

  * RopeMatch takes the text to search and the pattern to search for in the text.

  * RopeMatch returns false on OOM and otherwise returns the match index through

  * the 'match' outparam (-1 for not found).

  */

 static bool

 RopeMatch(JSContext *cx, JSString *textstr, const jschar *pat, uint32_t patlen, int *match)

 {

     JS_ASSERT(textstr->isRope());

     if (patlen == 0) {

         *match = 0;

         return true;

     }

     if (textstr->length() < patlen) {

         *match = -1;

         return true;

     }

     /*

      * List of leaf nodes in the rope. If we run out of memory when trying to

      * append to this list, we can still fall back to StringMatch, so use the

      * system allocator so we don't report OOM in that case.

      */

     Vector<JSLinearString *, 16, SystemAllocPolicy> strs;

     /*

      * We don't want to do rope matching if there is a poor node-to-char ratio,

      * since this means spending a lot of time in the match loop below. We also

      * need to build the list of leaf nodes. Do both here: iterate over the

      * nodes so long as there are not too many.

      */

     {

         size_t textstrlen = textstr->length();

         size_t threshold = textstrlen >> sRopeMatchThresholdRatioLog2;

         StringSegmentRange r(cx);

         if (!r.init(textstr))

             return false;

         while (!r.empty()) {

             if (threshold-- == 0 || !strs.append(r.front())) {

                 const jschar *chars = textstr->getChars(cx);

                 if (!chars)

                     return false;

                 *match = StringMatch(chars, textstrlen, pat, patlen);

                 return true;

             }

             if (!r.popFront())

                 return false;

         }

     }

     /* Absolute offset from the beginning of the logical string textstr. */

     int pos = 0;

     for (JSLinearString **outerp = strs.begin(); outerp != strs.end(); ++outerp) {

         /* Try to find a match within 'outer'. */

         JSLinearString *outer = *outerp;

         const jschar *chars = outer->chars();

         size_t len = outer->length();

         int matchResult = StringMatch(chars, len, pat, patlen);

         if (matchResult != -1) {

             /* Matched! */

             *match = pos + matchResult;

             return true;

         }

         /* Try to find a match starting in 'outer' and running into other nodes. */

         const jschar *const text = chars + (patlen > len ? 0 : len - patlen + 1);

         const jschar *const textend = chars + len;

         const jschar p0 = *pat;

         const jschar *const p1 = pat + 1;

         const jschar *const patend = pat + patlen;

         for (const jschar *t = text; t != textend; ) {

             if (*t++ != p0)

                 continue;

             JSLinearString **innerp = outerp;

             const jschar *ttend = textend;

             for (const jschar *pp = p1, *tt = t; pp != patend; ++pp, ++tt) {

                 while (tt == ttend) {

                     if (++innerp == strs.end()) {

                         *match = -1;

                         return true;

                     }

                     JSLinearString *inner = *innerp;

                     tt = inner->chars();

                     ttend = tt + inner->length();

                 }

                 if (*pp != *tt)

                     goto break_continue;

             }

             /* Matched! */

             *match = pos + (t - chars) - 1;  /* -1 because of *t++ above */

             return true;

           break_continue:;

         }

         pos += len;

     }

     *match = -1;

     return true;

 }

 /* ES6 20121026 draft 15.5.4.24. */

 static bool

 str_contains(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     // Steps 1, 2, and 3

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     // Steps 4 and 5

     Rooted<JSLinearString*> searchStr(cx, ArgToRootedString(cx, args, 0));

     if (!searchStr)

         return false;

     // Steps 6 and 7

     uint32_t pos = 0;

     if (args.hasDefined(1)) {

         if (args[1].isInt32()) {

             int i = args[1].toInt32();

             pos = (i < 0) ? 0U : uint32_t(i);

         } else {

             double d;

             if (!ToInteger(cx, args[1], &d))

                 return false;

             pos = uint32_t(Min(Max(d, 0.0), double(UINT32_MAX)));

         }

     }

     // Step 8

     uint32_t textLen = str->length();

     const jschar *textChars = str->getChars(cx);

     if (!textChars)

         return false;

     // Step 9

     uint32_t start = Min(Max(pos, 0U), textLen);

     // Step 10

     uint32_t searchLen = searchStr->length();

     const jschar *searchChars = searchStr->chars();

     // Step 11

     textChars += start;

     textLen -= start;

     int match = StringMatch(textChars, textLen, searchChars, searchLen);

     args.rval().setBoolean(match != -1);

     return true;

 }

 /* ES6 20120927 draft 15.5.4.7. */

 static bool

 str_indexOf(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     // Steps 1, 2, and 3

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     // Steps 4 and 5

     Rooted<JSLinearString*> searchStr(cx, ArgToRootedString(cx, args, 0));

     if (!searchStr)

         return false;

     // Steps 6 and 7

     uint32_t pos = 0;

     if (args.hasDefined(1)) {

         if (args[1].isInt32()) {

             int i = args[1].toInt32();

             pos = (i < 0) ? 0U : uint32_t(i);

         } else {

             double d;

             if (!ToInteger(cx, args[1], &d))

                 return false;

             pos = uint32_t(Min(Max(d, 0.0), double(UINT32_MAX)));

         }

     }

    // Step 8

     uint32_t textLen = str->length();

     const jschar *textChars = str->getChars(cx);

     if (!textChars)

         return false;

     // Step 9

     uint32_t start = Min(Max(pos, 0U), textLen);

     // Step 10

     uint32_t searchLen = searchStr->length();

     const jschar *searchChars = searchStr->chars();

     // Step 11

     textChars += start;

     textLen -= start;

     int match = StringMatch(textChars, textLen, searchChars, searchLen);

     args.rval().setInt32((match == -1) ? -1 : start + match);

     return true;

 }

 static bool

 str_lastIndexOf(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     RootedString textstr(cx, ThisToStringForStringProto(cx, args));

     if (!textstr)

         return false;

     size_t textlen = textstr->length();

     Rooted<JSLinearString*> patstr(cx, ArgToRootedString(cx, args, 0));

     if (!patstr)

         return false;

     size_t patlen = patstr->length();

     int i = textlen - patlen; // Start searching here

     if (i < 0) {

         args.rval().setInt32(-1);

         return true;

     }

     if (args.length() > 1) {

         if (args[1].isInt32()) {

             int j = args[1].toInt32();

             if (j <= 0)

                 i = 0;

             else if (j < i)

                 i = j;

         } else {

             double d;

             if (!ToNumber(cx, args[1], &d))

                 return false;

             if (!IsNaN(d)) {

                 d = ToInteger(d);

                 if (d <= 0)

                     i = 0;

                 else if (d < i)

                     i = (int)d;

             }

         }

     }

     if (patlen == 0) {

         args.rval().setInt32(i);

         return true;

     }

     const jschar *text = textstr->getChars(cx);

     if (!text)

         return false;

     const jschar *pat = patstr->chars();

     const jschar *t = text + i;

     const jschar *textend = text - 1;

     const jschar p0 = *pat;

     const jschar *patNext = pat + 1;

     const jschar *patEnd = pat + patlen;

     for (; t != textend; --t) {

         if (*t == p0) {

             const jschar *t1 = t + 1;

             for (const jschar *p1 = patNext; p1 != patEnd; ++p1, ++t1) {

                 if (*t1 != *p1)

                     goto break_continue;

             }

             args.rval().setInt32(t - text);

             return true;

         }

       break_continue:;

     }

     args.rval().setInt32(-1);

     return true;

 }

 /* ES6 20131108 draft 21.1.3.18. */

 static bool

 str_startsWith(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     // Steps 1, 2, and 3

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     // Step 4

     if (args.get(0).isObject() && IsObjectWithClass(args[0], ESClass_RegExp, cx)) {

         JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_INVALID_ARG_TYPE,

                              "first", "", "Regular Expression");

         return false;

     }

     // Steps 5 and 6

     Rooted<JSLinearString*> searchStr(cx, ArgToRootedString(cx, args, 0));

     if (!searchStr)

         return false;

     // Steps 7 and 8

     uint32_t pos = 0;

     if (args.hasDefined(1)) {

         if (args[1].isInt32()) {

             int i = args[1].toInt32();

             pos = (i < 0) ? 0U : uint32_t(i);

         } else {

             double d;

             if (!ToInteger(cx, args[1], &d))

                 return false;

             pos = uint32_t(Min(Max(d, 0.0), double(UINT32_MAX)));

         }

     }

     // Step 9

     uint32_t textLen = str->length();

     const jschar *textChars = str->getChars(cx);

     if (!textChars)

         return false;

     // Step 10

     uint32_t start = Min(Max(pos, 0U), textLen);

     // Step 11

     uint32_t searchLen = searchStr->length();

     const jschar *searchChars = searchStr->chars();

     // Step 12

     if (searchLen + start < searchLen || searchLen + start > textLen) {

         args.rval().setBoolean(false);

         return true;

     }

     // Steps 13 and 14

     args.rval().setBoolean(PodEqual(textChars + start, searchChars, searchLen));

     return true;

 }

 /* ES6 20131108 draft 21.1.3.7. */

 static bool

 str_endsWith(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     // Steps 1, 2, and 3

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     // Step 4

     if (args.get(0).isObject() && IsObjectWithClass(args[0], ESClass_RegExp, cx)) {

         JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_INVALID_ARG_TYPE,

                              "first", "", "Regular Expression");

         return false;

     }

     // Steps 5 and 6

     Rooted<JSLinearString *> searchStr(cx, ArgToRootedString(cx, args, 0));

     if (!searchStr)

         return false;

     // Step 7

     uint32_t textLen = str->length();

     const jschar *textChars = str->getChars(cx);

     if (!textChars)

         return false;

     // Steps 8 and 9

     uint32_t pos = textLen;

     if (args.hasDefined(1)) {

         if (args[1].isInt32()) {

             int i = args[1].toInt32();

             pos = (i < 0) ? 0U : uint32_t(i);

         } else {

             double d;

             if (!ToInteger(cx, args[1], &d))

                 return false;

             pos = uint32_t(Min(Max(d, 0.0), double(UINT32_MAX)));

         }

     }

     // Step 10

     uint32_t end = Min(Max(pos, 0U), textLen);

     // Step 11

     uint32_t searchLen = searchStr->length();

     const jschar *searchChars = searchStr->chars();

     // Step 13 (reordered)

     if (searchLen > end) {

         args.rval().setBoolean(false);

         return true;

     }

     // Step 12

     uint32_t start = end - searchLen;

     // Steps 14 and 15

     args.rval().setBoolean(PodEqual(textChars + start, searchChars, searchLen));

     return true;

 }

 static bool

 js_TrimString(JSContext *cx, Value *vp, bool trimLeft, bool trimRight)

 {

     CallReceiver call = CallReceiverFromVp(vp);

     RootedString str(cx, ThisToStringForStringProto(cx, call));

     if (!str)

         return false;

     size_t length = str->length();

     const jschar *chars = str->getChars(cx);

     if (!chars)

         return false;

     size_t begin = 0;

     size_t end = length;

     if (trimLeft) {

         while (begin < length && unicode::IsSpace(chars[begin]))

             ++begin;

     }

     if (trimRight) {

         while (end > begin && unicode::IsSpace(chars[end - 1]))

             --end;

     }

     str = js_NewDependentString(cx, str, begin, end - begin);

     if (!str)

         return false;

     call.rval().setString(str);

     return true;

 }

 static bool

 str_trim(JSContext *cx, unsigned argc, Value *vp)

 {

     return js_TrimString(cx, vp, true, true);

 }

 static bool

 str_trimLeft(JSContext *cx, unsigned argc, Value *vp)

 {

     return js_TrimString(cx, vp, true, false);

 }

 static bool

 str_trimRight(JSContext *cx, unsigned argc, Value *vp)

 {

     return js_TrimString(cx, vp, false, true);

 }

 /*

  * Perl-inspired string functions.

  */

 namespace {

 /* Result of a successfully performed flat match. */

 class FlatMatch

 {

     RootedAtom patstr;

     const jschar *pat;

     size_t       patlen;

     int32_t      match_;

     friend class StringRegExpGuard;

   public:

     FlatMatch(JSContext *cx) : patstr(cx) {}

     JSLinearString *pattern() const { return patstr; }

     size_t patternLength() const { return patlen; }

     /*

      * Note: The match is -1 when the match is performed successfully,

      * but no match is found.

      */

     int32_t match() const { return match_; }

 };

 } /* anonymous namespace */

 static inline bool

 IsRegExpMetaChar(jschar c)

 {

     switch (c) {

       /* Taken from the PatternCharacter production in 15.10.1. */

       case '^': case '$': case '\\': case '.': case '*': case '+':

       case '?': case '(': case ')': case '[': case ']': case '{':

       case '}': case '|':

         return true;

       default:

         return false;

     }

 }

 static inline bool

 HasRegExpMetaChars(const jschar *chars, size_t length)

 {

     for (size_t i = 0; i < length; ++i) {

         if (IsRegExpMetaChar(chars[i]))

             return true;

     }

     return false;

 }

 namespace {

 /*

  * StringRegExpGuard factors logic out of String regexp operations.

  *

  * |optarg| indicates in which argument position RegExp flags will be found, if

  * present. This is a Mozilla extension and not part of any ECMA spec.

  */

 class MOZ_STACK_CLASS StringRegExpGuard

 {

     RegExpGuard re_;

     FlatMatch   fm;

     RootedObject obj_;

     /*

      * Upper bound on the number of characters we are willing to potentially

      * waste on searching for RegExp meta-characters.

      */

     static const size_t MAX_FLAT_PAT_LEN = 256;

     static JSAtom *

     flattenPattern(JSContext *cx, JSAtom *patstr)

     {

         StringBuffer sb(cx);

         if (!sb.reserve(patstr->length()))

             return nullptr;

         static const jschar ESCAPE_CHAR = '\\';

         const jschar *chars = patstr->chars();

         size_t len = patstr->length();

         for (const jschar *it = chars; it != chars + len; ++it) {

             if (IsRegExpMetaChar(*it)) {

                 if (!sb.append(ESCAPE_CHAR) || !sb.append(*it))

                     return nullptr;

             } else {

                 if (!sb.append(*it))

                     return nullptr;

             }

         }

         return sb.finishAtom();

     }

   public:

     StringRegExpGuard(JSContext *cx)

       : re_(cx), fm(cx), obj_(cx)

     { }

     /* init must succeed in order to call tryFlatMatch or normalizeRegExp. */

     bool init(JSContext *cx, CallArgs args, bool convertVoid = false)

     {

         if (args.length() != 0 && IsObjectWithClass(args[0], ESClass_RegExp, cx))

             return init(cx, &args[0].toObject());

         if (convertVoid && !args.hasDefined(0)) {

             fm.patstr = cx->runtime()->emptyString;

             return true;

         }

         JSString *arg = ArgToRootedString(cx, args, 0);

         if (!arg)

             return false;

         fm.patstr = AtomizeString(cx, arg);

         if (!fm.patstr)

             return false;

         return true;

     }

     bool init(JSContext *cx, JSObject *regexp) {

         obj_ = regexp;

         JS_ASSERT(ObjectClassIs(obj_, ESClass_RegExp, cx));

         if (!RegExpToShared(cx, obj_, &re_))

             return false;

         return true;

     }

     bool init(JSContext *cx, HandleString pattern) {

         fm.patstr = AtomizeString(cx, pattern);

         if (!fm.patstr)

             return false;

         return true;

     }

     /*

      * Attempt to match |patstr| to |textstr|. A flags argument, metachars in

      * the pattern string, or a lengthy pattern string can thwart this process.

      *

      * |checkMetaChars| looks for regexp metachars in the pattern string.

      *

      * Return whether flat matching could be used.

      *

      * N.B. tryFlatMatch returns nullptr on OOM, so the caller must check

      * cx->isExceptionPending().

      */

     const FlatMatch *

     tryFlatMatch(JSContext *cx, JSString *textstr, unsigned optarg, unsigned argc,

                  bool checkMetaChars = true)

     {

         if (re_.initialized())

             return nullptr;

         fm.pat = fm.patstr->chars();

         fm.patlen = fm.patstr->length();

         if (optarg < argc)

             return nullptr;

         if (checkMetaChars &&

             (fm.patlen > MAX_FLAT_PAT_LEN || HasRegExpMetaChars(fm.pat, fm.patlen))) {

             return nullptr;

         }

         /*

          * textstr could be a rope, so we want to avoid flattening it for as

          * long as possible.

          */

         if (textstr->isRope()) {

             if (!RopeMatch(cx, textstr, fm.pat, fm.patlen, &fm.match_))

                 return nullptr;

         } else {

             const jschar *text = textstr->asLinear().chars();

             size_t textlen = textstr->length();

             fm.match_ = StringMatch(text, textlen, fm.pat, fm.patlen);

         }

         return &fm;

     }

     /* If the pattern is not already a regular expression, make it so. */

     bool normalizeRegExp(JSContext *cx, bool flat, unsigned optarg, CallArgs args)

     {

         if (re_.initialized())

             return true;

         /* Build RegExp from pattern string. */

         RootedString opt(cx);

         if (optarg < args.length()) {

             opt = ToString<CanGC>(cx, args[optarg]);

             if (!opt)

                 return false;

         } else {

             opt = nullptr;

         }

         Rooted<JSAtom *> patstr(cx);

         if (flat) {

             patstr = flattenPattern(cx, fm.patstr);

             if (!patstr)

                 return false;

         } else {

             patstr = fm.patstr;

         }

         JS_ASSERT(patstr);

         return cx->compartment()->regExps.get(cx, patstr, opt, &re_);

     }

     bool zeroLastIndex(JSContext *cx) {

         if (!regExpIsObject())

             return true;

         // Use a fast path for same-global RegExp objects with writable

         // lastIndex.

         if (obj_->is<RegExpObject>() && obj_->nativeLookup(cx, cx->names().lastIndex)->writable()) {

             obj_->as<RegExpObject>().zeroLastIndex();

             return true;

         }

         // Handle everything else generically (including throwing if .lastIndex is non-writable).

         RootedValue zero(cx, Int32Value(0));

         return JSObject::setProperty(cx, obj_, obj_, cx->names().lastIndex, &zero, true);

     }

     RegExpShared &regExp() { return *re_; }

     bool regExpIsObject() { return obj_ != nullptr; }

     HandleObject regExpObject() {

         JS_ASSERT(regExpIsObject());

         return obj_;

     }

   private:

     StringRegExpGuard(const StringRegExpGuard &) MOZ_DELETE;

     void operator=(const StringRegExpGuard &) MOZ_DELETE;

 };

 } /* anonymous namespace */

 static bool

 DoMatchLocal(JSContext *cx, CallArgs args, RegExpStatics *res, Handle<JSLinearString*> input,

              RegExpShared &re)

 {

     size_t charsLen = input->length();

     const jschar *chars = input->chars();

     size_t i = 0;

     ScopedMatchPairs matches(&cx->tempLifoAlloc());

     RegExpRunStatus status = re.execute(cx, chars, charsLen, &i, matches);

     if (status == RegExpRunStatus_Error)

         return false;

     if (status == RegExpRunStatus_Success_NotFound) {

         args.rval().setNull();

         return true;

     }

     if (!res->updateFromMatchPairs(cx, input, matches))

         return false;

     RootedValue rval(cx);

     if (!CreateRegExpMatchResult(cx, input, matches, &rval))

         return false;

     args.rval().set(rval);

     return true;

 }

 /* ES5 15.5.4.10 step 8. */

 static bool

 DoMatchGlobal(JSContext *cx, CallArgs args, RegExpStatics *res, Handle<JSLinearString*> input,

               StringRegExpGuard &g)

 {

     // Step 8a.

     //

     // This single zeroing of "lastIndex" covers all "lastIndex" changes in the

     // rest of String.prototype.match, particularly in steps 8f(i) and

     // 8f(iii)(2)(a).  Here's why.

     //

     // The inputs to the calls to RegExp.prototype.exec are a RegExp object

     // whose .global is true and a string.  The only side effect of a call in

     // these circumstances is that the RegExp's .lastIndex will be modified to

     // the next starting index after the discovered match (or to 0 if there's

     // no remaining match).  Because .lastIndex is a non-configurable data

     // property and no script-controllable code executes after step 8a, passing

     // step 8a implies *every* .lastIndex set succeeds.  String.prototype.match

     // calls RegExp.prototype.exec repeatedly, and the last call doesn't match,

     // so the final value of .lastIndex is 0: exactly the state after step 8a

     // succeeds.  No spec step lets script observe intermediate .lastIndex

     // values.

     //

     // The arrays returned by RegExp.prototype.exec always have a string at

     // index 0, for which [[Get]]s have no side effects.

     //

     // Filling in a new array using [[DefineOwnProperty]] is unobservable.

     //

     // This is a tricky point, because after this set, our implementation *can*

     // fail.  The key is that script can't distinguish these failure modes from

     // one where, in spec terms, we fail immediately after step 8a.  That *in

     // reality* we might have done extra matching work, or created a partial

     // results array to return, or hit an interrupt, is irrelevant.  The

     // script can't tell we did any of those things but didn't update

     // .lastIndex.  Thus we can optimize steps 8b onward however we want,

     // including eliminating intermediate .lastIndex sets, as long as we don't

     // add ways for script to observe the intermediate states.

     //

     // In short: it's okay to cheat (by setting .lastIndex to 0, once) because

     // we can't get caught.

     if (!g.zeroLastIndex(cx))

         return false;

     // Step 8b.

     AutoValueVector elements(cx);

     size_t lastSuccessfulStart = 0;

     // The loop variables from steps 8c-e aren't needed, as we use different

     // techniques from the spec to implement step 8f's loop.

     // Step 8f.

     MatchPair match;

     size_t charsLen = input->length();

     const jschar *chars = input->chars();

     RegExpShared &re = g.regExp();

     for (size_t searchIndex = 0; searchIndex <= charsLen; ) {

         if (!CheckForInterrupt(cx))

             return false;

         // Steps 8f(i-ii), minus "lastIndex" updates (see above).

         size_t nextSearchIndex = searchIndex;

         RegExpRunStatus status = re.executeMatchOnly(cx, chars, charsLen, &nextSearchIndex, match);

         if (status == RegExpRunStatus_Error)

             return false;

         // Step 8f(ii).

         if (status == RegExpRunStatus_Success_NotFound)

             break;

         lastSuccessfulStart = searchIndex;

         // Steps 8f(iii)(1-3).

         searchIndex = match.isEmpty() ? nextSearchIndex + 1 : nextSearchIndex;

         // Step 8f(iii)(4-5).

         JSLinearString *str = js_NewDependentString(cx, input, match.start, match.length());

         if (!str)

             return false;

         if (!elements.append(StringValue(str)))

             return false;

     }

     // Step 8g.

     if (elements.empty()) {

         args.rval().setNull();

         return true;

     }

     // The last *successful* match updates the RegExpStatics. (Interestingly,

     // this implies that String.prototype.match's semantics aren't those

     // implied by the RegExp.prototype.exec calls in the ES5 algorithm.)

     res->updateLazily(cx, input, &re, lastSuccessfulStart);

     // Steps 8b, 8f(iii)(5-6), 8h.

     JSObject *array = NewDenseCopiedArray(cx, elements.length(), elements.begin());

     if (!array)

         return false;

     args.rval().setObject(*array);

     return true;

 }

 static bool

 BuildFlatMatchArray(JSContext *cx, HandleString textstr, const FlatMatch &fm, CallArgs *args)

 {

     if (fm.match() < 0) {

         args->rval().setNull();

         return true;

     }

     /* For this non-global match, produce a RegExp.exec-style array. */

     RootedObject obj(cx, NewDenseEmptyArray(cx));

     if (!obj)

         return false;

     RootedValue patternVal(cx, StringValue(fm.pattern()));

     RootedValue matchVal(cx, Int32Value(fm.match()));

     RootedValue textVal(cx, StringValue(textstr));

     if (!JSObject::defineElement(cx, obj, 0, patternVal) ||

         !JSObject::defineProperty(cx, obj, cx->names().index, matchVal) ||

         !JSObject::defineProperty(cx, obj, cx->names().input, textVal))

     {

         return false;

     }

     args->rval().setObject(*obj);

     return true;

 }

 /* ES5 15.5.4.10. */

 bool

 js::str_match(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     /* Steps 1-2. */

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     /* Steps 3-4, plus the trailing-argument "flags" extension. */

     StringRegExpGuard g(cx);

     if (!g.init(cx, args, true))

         return false;

     /* Fast path when the search pattern can be searched for as a string. */

     if (const FlatMatch *fm = g.tryFlatMatch(cx, str, 1, args.length()))

         return BuildFlatMatchArray(cx, str, *fm, &args);

     /* Return if there was an error in tryFlatMatch. */

     if (cx->isExceptionPending())

         return false;

     /* Create regular-expression internals as needed to perform the match. */

     if (!g.normalizeRegExp(cx, false, 1, args))

         return false;

     RegExpStatics *res = cx->global()->getRegExpStatics();

     Rooted<JSLinearString*> linearStr(cx, str->ensureLinear(cx));

     if (!linearStr)

         return false;

     /* Steps 5-6, 7. */

     if (!g.regExp().global())

         return DoMatchLocal(cx, args, res, linearStr, g.regExp());

     /* Steps 6, 8. */

     return DoMatchGlobal(cx, args, res, linearStr, g);

 }

 bool

 js::str_search(JSContext *cx, unsigned argc, Value *vp)

 {

     CallArgs args = CallArgsFromVp(argc, vp);

     RootedString str(cx, ThisToStringForStringProto(cx, args));

     if (!str)

         return false;

     StringRegExpGuard g(cx);

     if (!g.init(cx, args, true))

         return false;

     if (const FlatMatch *fm = g.tryFlatMatch(cx, str, 1, args.length())) {

         args.rval().setInt32(fm->match());

         return true;

     }

     if (cx->isExceptionPending())  /* from tryFlatMatch */

         return false;

     if (!g.normalizeRegExp(cx, false, 1, args))

         return false;

     Rooted<JSLinearString*> linearStr(cx, str->ensureLinear(cx));

     if (!linearStr)

         return false;

     const jschar *chars = linearStr->chars();

     size_t length = linearStr->length();

     RegExpStatics *res = cx->global()->getRegExpStatics();

     /* Per ECMAv5 15.5.4.12 (5) The last index property is ignored and left unchanged. */

     size_t i = 0;

     MatchPair match;

     RegExpRunStatus status = g.regExp().executeMatchOnly(cx, chars, length, &i, match);

     if (status == RegExpRunStatus_Error)

         return false;

     if (status == RegExpRunStatus_Success)

         res->updateLazily(cx, linearStr, &g.regExp(), 0);

     JS_ASSERT_IF(status == RegExpRunStatus_Success_NotFound, match.start == -1);

     args.rval().setInt32(match.start);

     return true;

 }

 // Utility for building a rope (lazy concatenation) of strings.

 class RopeBuilder {

     JSContext *cx;

     RootedString res;

     RopeBuilder(const RopeBuilder &other) MOZ_DELETE;

     void operator=(const RopeBuilder &other) MOZ_DELETE;

   public:

     RopeBuilder(JSContext *cx)

       : cx(cx), res(cx, cx->runtime()->emptyString)

     {}

     inline bool append(HandleString str) {

         res = ConcatStrings<CanGC>(cx, res, str);

         return !!res;

     }

     inline JSString *result() {

         return res;

     }

 };

 namespace {

 struct ReplaceData

 {

     ReplaceData(JSContext *cx)

       : str(cx), g(cx), lambda(cx), elembase(cx), repstr(cx),

         fig(cx, NullValue()), sb(cx)

     {}

     inline void setReplacementString(JSLinearString *string) {

         JS_ASSERT(string);

         lambda = nullptr;

         elembase = nullptr;

         repstr = string;

         /* We're about to store pointers into the middle of our string. */

         dollarEnd = repstr->chars() + repstr->length();

         dollar = js_strchr_limit(repstr->chars(), '$', dollarEnd);

     }

     inline void setReplacementFunction(JSObject *func) {

         JS_ASSERT(func);

         lambda = func;

         elembase = nullptr;

         repstr = nullptr;

         dollar = dollarEnd = nullptr;

     }

     RootedString       str;            /* 'this' parameter object as a string */

     StringRegExpGuard  g;              /* regexp parameter object and private data */

     RootedObject       lambda;         /* replacement function object or null */

     RootedObject       elembase;       /* object for function(a){return b[a]} replace */

     Rooted<JSLinearString*> repstr; /* replacement string */

     const jschar       *dollar;        /* null or pointer to first $ in repstr */

     const jschar       *dollarEnd;     /* limit pointer for js_strchr_limit */

     int                leftIndex;      /* left context index in str->chars */

     JSSubString        dollarStr;      /* for "$$" InterpretDollar result */

     bool               calledBack;     /* record whether callback has been called */

     FastInvokeGuard    fig;            /* used for lambda calls, also holds arguments */

     StringBuffer       sb;             /* buffer built during DoMatch */

 };

 } /* anonymous namespace */

 static bool

 ReplaceRegExp(JSContext *cx, RegExpStatics *res, ReplaceData &rdata);

 static bool

 DoMatchForReplaceLocal(JSContext *cx, RegExpStatics *res, Handle<JSLinearString*> linearStr,

                        RegExpShared &re, ReplaceData &rdata)

 {

     size_t charsLen = linearStr->length();

     size_t i = 0;

     ScopedMatchPairs matches(&cx->tempLifoAlloc());

     RegExpRunStatus status = re.execute(cx, linearStr->chars(), charsLen, &i, matches);

     if (status == RegExpRunStatus_Error)

         return false;

     if (status == RegExpRunStatus_Success_NotFound)

         return true;

     if (!res->updateFromMatchPairs(cx, linearStr, matches))

         return false;

     return ReplaceRegExp(cx, res, rdata);

 }

 static bool

 DoMatchForReplaceGlobal(JSContext *cx, RegExpStatics *res, Handle<JSLinearString*> linearStr,

                         RegExpShared &re, ReplaceData &rdata)

 {

     size_t charsLen = linearStr->length();

     ScopedMatchPairs matches(&cx->tempLifoAlloc());

     for (size_t count = 0, i = 0; i <= charsLen; ++count) {

         if (!CheckForInterrupt(cx))

             return false;

         RegExpRunStatus status = re.execute(cx, linearStr->chars(), charsLen, &i, matches);

         if (status == RegExpRunStatus_Error)

             return false;

         if (status == RegExpRunStatus_Success_NotFound)

             break;

         if (!res->updateFromMatchPairs(cx, linearStr, matches))

             return false;

         if (!ReplaceRegExp(cx, res, rdata))

             return false;

         if (!res->matched())

             ++i;

     }

     return true;

 }

 static bool

 InterpretDollar(RegExpStatics *res, const jschar *dp, const jschar *ep,

                 ReplaceData &rdata, JSSubString *out, size_t *skip)

 {

     JS_ASSERT(*dp == '$');

     /* If there is only a dollar, bail now */

     if (dp + 1 >= ep)

         return false;

     /* Interpret all Perl match-induced dollar variables. */

     jschar dc = dp[1];

     if (JS7_ISDEC(dc)) {

         /* ECMA-262 Edition 3: 1-9 or 01-99 */

         unsigned num = JS7_UNDEC(dc);

         if (num > res->getMatches().parenCount())

             return false;

         const jschar *cp = dp + 2;

         if (cp < ep && (dc = *cp, JS7_ISDEC(dc))) {

             unsigned tmp = 10 * num + JS7_UNDEC(dc);

             if (tmp <= res->getMatches().parenCount()) {

                 cp++;

                 num = tmp;

             }

         }

         if (num == 0)

             return false;

         *skip = cp - dp;

         JS_ASSERT(num <= res->getMatches().parenCount());

         /*

          * Note: we index to get the paren with the (1-indexed) pair

          * number, as opposed to a (0-indexed) paren number.

          */

         res->getParen(num, out);

         return true;

     }

     *skip = 2;

     switch (dc) {

       case '$':

         rdata.dollarStr.chars = dp;

         rdata.dollarStr.length = 1;

         *out = rdata.dollarStr;

         return true;

       case '&':

         res->getLastMatch(out);

         return true;

       case '+':

         res->getLastParen(out);

         return true;

       case '`':

         res->getLeftContext(out);

         return true;

       case '\'':

         res->getRightContext(out);

         return true;

     }

     return false;

 }

 static bool

 FindReplaceLength(JSContext *cx, RegExpStatics *res, ReplaceData &rdata, size_t *sizep)

 {

     if (rdata.elembase) {

         /*

          * The base object is used when replace was passed a lambda which looks like

          * 'function(a) { return b[a]; }' for the base object b.  b will not change

          * in the course of the replace unless we end up making a scripted call due

          * to accessing a scripted getter or a value with a scripted toString.

          */

         JS_ASSERT(rdata.lambda);

         JS_ASSERT(!rdata.elembase->getOps()->lookupProperty);

         JS_ASSERT(!rdata.elembase->getOps()->getProperty);

         RootedValue match(cx);

         if (!res->createLastMatch(cx, &match))

             return false;

         JSAtom *atom = ToAtom<CanGC>(cx, match);

         if (!atom)

             return false;

         RootedValue v(cx);

         if (HasDataProperty(cx, rdata.elembase, AtomToId(atom), v.address()) && v.isString()) {

             rdata.repstr = v.toString()->ensureLinear(cx);

             if (!rdata.repstr)

                 return false;

             *sizep = rdata.repstr->length();

             return true;

         }

         /*

          * Couldn't handle this property, fall through and despecialize to the

          * general lambda case.

          */

         rdata.elembase = nullptr;

     }

     if (rdata.lambda) {

         RootedObject lambda(cx, rdata.lambda);

         PreserveRegExpStatics staticsGuard(cx, res);

         if (!staticsGuard.init(cx))

             return false;

         /*

          * In the lambda case, not only do we find the replacement string's

          * length, we compute repstr and return it via rdata for use within

          * DoReplace.  The lambda is called with arguments ($&, $1, $2, ...,

          * index, input), i.e., all the properties of a regexp match array.

          * For $&, etc., we must create string jsvals from cx->regExpStatics.

          * We grab up stack space to keep the newborn strings GC-rooted.

          */

         unsigned p = res->getMatches().parenCount();

         unsigned argc = 1 + p + 2;

         InvokeArgs &args = rdata.fig.args();

         if (!args.init(argc))

             return false;

         args.setCallee(ObjectValue(*lambda));

         args.setThis(UndefinedValue());

         /* Push $&, $1, $2, ... */

         unsigned argi = 0;

         if (!res->createLastMatch(cx, args[argi++]))

             return false;

         for (size_t i = 0; i < res->getMatches().parenCount(); ++i) {

             if (!res->createParen(cx, i + 1, args[argi++]))

                 return false;

         }

         /* Push match index and input string. */

         args[argi++].setInt32(res->getMatches()[0].start);

         args[argi].setString(rdata.str);

         if (!rdata.fig.invoke(cx))

             return false;

         /* root repstr: rdata is on the stack, so scanned by conservative gc. */

         JSString *repstr = ToString<CanGC>(cx, args.rval());

         if (!repstr)

             return false;

         rdata.repstr = repstr->ensureLinear(cx);

         if (!rdata.repstr)

             return false;

         *sizep = rdata.repstr->length();

         return true;

     }

     JSString *repstr = rdata.repstr;

     CheckedInt<uint32_t> replen = repstr->length();

     for (const jschar *dp = rdata.dollar, *ep = rdata.dollarEnd; dp;

          dp = js_strchr_limit(dp, '$', ep)) {

         JSSubString sub;

         size_t skip;

         if (InterpretDollar(res, dp, ep, rdata, &sub, &skip)) {

             if (sub.length > skip)

                 replen += sub.length - skip;

             else

                 replen -= skip - sub.length;

             dp += skip;

         } else {

             dp++;

         }

     }

     if (!replen.isValid()) {

         js_ReportAllocationOverflow(cx);

         return false;

     }

     *sizep = replen.value();

     return true;

 }

 /*

  * Precondition: |rdata.sb| already has necessary growth space reserved (as

  * derived from FindReplaceLength).

  */

 static void

 DoReplace(RegExpStatics *res, ReplaceData &rdata)

 {

     JSLinearString *repstr = rdata.repstr;

     const jschar *cp;

     const jschar *bp = cp = repstr->chars();

     const jschar *dp = rdata.dollar;

     const jschar *ep = rdata.dollarEnd;

     for (; dp; dp = js_strchr_limit(dp, '$', ep)) {

         /* Move one of the constant portions of the replacement value. */

         size_t len = dp - cp;

         rdata.sb.infallibleAppend(cp, len);

         cp = dp;

         JSSubString sub;

         size_t skip;

         if (InterpretDollar(res, dp, ep, rdata, &sub, &skip)) {

             len = sub.length;

             rdata.sb.infallibleAppend(sub.chars, len);

             cp += skip;

             dp += skip;

         } else {

             dp++;

         }

     }

     rdata.sb.infallibleAppend(cp, repstr->length() - (cp - bp));

 }

 static bool

 ReplaceRegExp(JSContext *cx, RegExpStatics *res, ReplaceData &rdata)

 {

     const MatchPair &match = res->getMatches()[0];

     JS_ASSERT(!match.isUndefined());

     JS_ASSERT(match.limit >= match.start && match.limit >= 0);

     rdata.calledBack = true;

     size_t leftoff = rdata.leftIndex;

     size_t leftlen = match.start - leftoff;

     rdata.leftIndex = match.limit;

     size_t replen = 0;  /* silence 'unused' warning */

     if (!FindReplaceLength(cx, res, rdata, &replen))

         return false;

     CheckedInt<uint32_t> newlen(rdata.sb.length());

     newlen += leftlen;

     newlen += replen;

     if (!newlen.isValid()) {

         js_ReportAllocationOverflow(cx);

         return false;

     }

     if (!rdata.sb.reserve(newlen.value()))

         return false;

     JSLinearString &str = rdata.str->asLinear();  /* flattened for regexp */

     const jschar *left = str.chars() + leftoff;

     rdata.sb.infallibleAppend(left, leftlen); /* skipped-over portion of the search value */

     DoReplace(res, rdata);

     return true;

 }

 static bool

 BuildFlatReplacement(JSContext *cx, HandleString textstr, HandleString repstr,

                      const FlatMatch &fm, MutableHandleValue rval)

 {

     RopeBuilder builder(cx);

     size_t match = fm.match();

     size_t matchEnd = match + fm.patternLength();

     if (textstr->isRope()) {

         /*

          * If we are replacing over a rope, avoid flattening it by iterating

          * through it, building a new rope.

          */

         StringSegmentRange r(cx);

         if (!r.init(textstr))

             return false;

         size_t pos = 0;

         while (!r.empty()) {

             RootedString str(cx, r.front());

             size_t len = str->length();

             size_t strEnd = pos + len;

             if (pos < matchEnd && strEnd > match) {

                 /*

                  * We need to special-case any part of the rope that overlaps

                  * with the replacement string.

                  */

                 if (match >= pos) {

                     /*

                      * If this part of the rope overlaps with the left side of

                      * the pattern, then it must be the only one to overlap with

                      * the first character in the pattern, so we include the

                      * replacement string here.

                      */

                     RootedString leftSide(cx, js_NewDependentString(cx, str, 0, match - pos));

                     if (!leftSide ||

                         !builder.append(leftSide) ||

                         !builder.append(repstr)) {

                         return false;

                     }

                 }

                 /*

                  * If str runs off the end of the matched string, append the

                  * last part of str.

                  */

                 if (strEnd > matchEnd) {

                     RootedString rightSide(cx, js_NewDependentString(cx, str, matchEnd - pos,

                                                                      strEnd - matchEnd));

                     if (!rightSide || !builder.append(rightSide))

                         return false;

                 }

             } else {

                 if (!builder.append(str))

                     return false;

             }

             pos += str->length();

             if (!r.popFront())

                 return false;

         }

     } else {

         RootedString leftSide(cx, js_NewDependentString(cx, textstr, 0, match));

         if (!leftSide)

             return false;

         RootedString rightSide(cx);

         rightSide = js_NewDependentString(cx, textstr, match + fm.patternLength(),

                                           textstr->length() - match - fm.patternLength());

         if (!rightSide ||

             !builder.append(leftSide) ||

             !builder.append(repstr) ||

             !builder.append(rightSide)) {

             return false;

         }

     }

     rval.setString(builder.result());

     return true;

 }

 /*

  * Perform a linear-scan dollar substitution on the replacement text,

  * constructing a result string that looks like:

  *

  *      newstring = string[:matchStart] + dollarSub(replaceValue) + string[matchLimit:]

  */

 static inline bool

 BuildDollarReplacement(JSContext *cx, JSString *textstrArg, JSLinearString *repstr,

                        const jschar *firstDollar, const FlatMatch &fm, MutableHandleValue rval)

 {

     Rooted<JSLinearString*> textstr(cx, textstrArg->ensureLinear(cx));

     if (!textstr)

         return false;

     JS_ASSERT(repstr->chars() <= firstDollar && firstDollar < repstr->chars() + repstr->length());

     size_t matchStart = fm.match();

     size_t matchLimit = matchStart + fm.patternLength();

     /*

      * Most probably:

      *

      *      len(newstr) >= len(orig) - len(match) + len(replacement)

      *

      * Note that dollar vars _could_ make the resulting text smaller than this.

      */

     StringBuffer newReplaceChars(cx);

     if (!newReplaceChars.reserve(textstr->length() - fm.patternLength() + repstr->length()))