michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- michael@0: * vim: set ts=8 sts=4 et sw=4 tw=99: michael@0: * This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: /* michael@0: * JS atom table. michael@0: */ michael@0: michael@0: #include "jsatominlines.h" michael@0: michael@0: #include "mozilla/ArrayUtils.h" michael@0: #include "mozilla/RangedPtr.h" michael@0: michael@0: #include michael@0: michael@0: #include "jscntxt.h" michael@0: #include "jsstr.h" michael@0: #include "jstypes.h" michael@0: michael@0: #include "gc/Marking.h" michael@0: #include "vm/Xdr.h" michael@0: michael@0: #include "jscntxtinlines.h" michael@0: #include "jscompartmentinlines.h" michael@0: #include "jsobjinlines.h" michael@0: michael@0: #include "vm/String-inl.h" michael@0: michael@0: using namespace js; michael@0: using namespace js::gc; michael@0: michael@0: using mozilla::ArrayEnd; michael@0: using mozilla::ArrayLength; michael@0: using mozilla::RangedPtr; michael@0: michael@0: const char * michael@0: js::AtomToPrintableString(ExclusiveContext *cx, JSAtom *atom, JSAutoByteString *bytes) michael@0: { michael@0: JSString *str = js_QuoteString(cx, atom, 0); michael@0: if (!str) michael@0: return nullptr; michael@0: return bytes->encodeLatin1(cx, str); michael@0: } michael@0: michael@0: const char * const js::TypeStrings[] = { michael@0: js_undefined_str, michael@0: js_object_str, michael@0: js_function_str, michael@0: js_string_str, michael@0: js_number_str, michael@0: js_boolean_str, michael@0: js_null_str, michael@0: }; michael@0: michael@0: #define DEFINE_PROTO_STRING(name,code,init,clasp) const char js_##name##_str[] = #name; michael@0: JS_FOR_EACH_PROTOTYPE(DEFINE_PROTO_STRING) michael@0: #undef DEFINE_PROTO_STRING michael@0: michael@0: #define CONST_CHAR_STR(idpart, id, text) const char js_##idpart##_str[] = text; michael@0: FOR_EACH_COMMON_PROPERTYNAME(CONST_CHAR_STR) michael@0: #undef CONST_CHAR_STR michael@0: michael@0: /* Constant strings that are not atomized. */ michael@0: const char js_break_str[] = "break"; michael@0: const char js_case_str[] = "case"; michael@0: const char js_catch_str[] = "catch"; michael@0: const char js_class_str[] = "class"; michael@0: const char js_close_str[] = "close"; michael@0: const char js_const_str[] = "const"; michael@0: const char js_continue_str[] = "continue"; michael@0: const char js_debugger_str[] = "debugger"; michael@0: const char js_default_str[] = "default"; michael@0: const char js_do_str[] = "do"; michael@0: const char js_else_str[] = "else"; michael@0: const char js_enum_str[] = "enum"; michael@0: const char js_export_str[] = "export"; michael@0: const char js_extends_str[] = "extends"; michael@0: const char js_finally_str[] = "finally"; michael@0: const char js_for_str[] = "for"; michael@0: const char js_getter_str[] = "getter"; michael@0: const char js_if_str[] = "if"; michael@0: const char js_implements_str[] = "implements"; michael@0: const char js_import_str[] = "import"; michael@0: const char js_in_str[] = "in"; michael@0: const char js_instanceof_str[] = "instanceof"; michael@0: const char js_interface_str[] = "interface"; michael@0: const char js_new_str[] = "new"; michael@0: const char js_package_str[] = "package"; michael@0: const char js_private_str[] = "private"; michael@0: const char js_protected_str[] = "protected"; michael@0: const char js_public_str[] = "public"; michael@0: const char js_send_str[] = "send"; michael@0: const char js_setter_str[] = "setter"; michael@0: const char js_static_str[] = "static"; michael@0: const char js_super_str[] = "super"; michael@0: const char js_switch_str[] = "switch"; michael@0: const char js_this_str[] = "this"; michael@0: const char js_try_str[] = "try"; michael@0: const char js_typeof_str[] = "typeof"; michael@0: const char js_void_str[] = "void"; michael@0: const char js_while_str[] = "while"; michael@0: const char js_with_str[] = "with"; michael@0: michael@0: // Use a low initial capacity for atom hash tables to avoid penalizing runtimes michael@0: // which create a small number of atoms. michael@0: static const uint32_t JS_STRING_HASH_COUNT = 64; michael@0: michael@0: struct CommonNameInfo michael@0: { michael@0: const char *str; michael@0: size_t length; michael@0: }; michael@0: michael@0: bool michael@0: JSRuntime::initializeAtoms(JSContext *cx) michael@0: { michael@0: atoms_ = cx->new_(); michael@0: if (!atoms_ || !atoms_->init(JS_STRING_HASH_COUNT)) michael@0: return false; michael@0: michael@0: if (parentRuntime) { michael@0: staticStrings = parentRuntime->staticStrings; michael@0: commonNames = parentRuntime->commonNames; michael@0: emptyString = parentRuntime->emptyString; michael@0: permanentAtoms = parentRuntime->permanentAtoms; michael@0: return true; michael@0: } michael@0: michael@0: permanentAtoms = cx->new_(); michael@0: if (!permanentAtoms || !permanentAtoms->init(JS_STRING_HASH_COUNT)) michael@0: return false; michael@0: michael@0: staticStrings = cx->new_(); michael@0: if (!staticStrings || !staticStrings->init(cx)) michael@0: return false; michael@0: michael@0: static const CommonNameInfo cachedNames[] = { michael@0: #define COMMON_NAME_INFO(idpart, id, text) { js_##idpart##_str, sizeof(text) - 1 }, michael@0: FOR_EACH_COMMON_PROPERTYNAME(COMMON_NAME_INFO) michael@0: #undef COMMON_NAME_INFO michael@0: #define COMMON_NAME_INFO(name, code, init, clasp) { js_##name##_str, sizeof(#name) - 1 }, michael@0: JS_FOR_EACH_PROTOTYPE(COMMON_NAME_INFO) michael@0: #undef COMMON_NAME_INFO michael@0: }; michael@0: michael@0: commonNames = cx->new_(); michael@0: if (!commonNames) michael@0: return false; michael@0: michael@0: FixedHeapPtr *names = reinterpret_cast *>(commonNames); michael@0: for (size_t i = 0; i < ArrayLength(cachedNames); i++, names++) { michael@0: JSAtom *atom = Atomize(cx, cachedNames[i].str, cachedNames[i].length, InternAtom); michael@0: if (!atom) michael@0: return false; michael@0: names->init(atom->asPropertyName()); michael@0: } michael@0: JS_ASSERT(uintptr_t(names) == uintptr_t(commonNames + 1)); michael@0: michael@0: emptyString = commonNames->empty; michael@0: return true; michael@0: } michael@0: michael@0: void michael@0: JSRuntime::finishAtoms() michael@0: { michael@0: if (atoms_) michael@0: js_delete(atoms_); michael@0: michael@0: if (!parentRuntime) { michael@0: if (staticStrings) michael@0: js_delete(staticStrings); michael@0: michael@0: if (commonNames) michael@0: js_delete(commonNames); michael@0: michael@0: if (permanentAtoms) michael@0: js_delete(permanentAtoms); michael@0: } michael@0: michael@0: atoms_ = nullptr; michael@0: staticStrings = nullptr; michael@0: commonNames = nullptr; michael@0: permanentAtoms = nullptr; michael@0: emptyString = nullptr; michael@0: } michael@0: michael@0: void michael@0: js::MarkAtoms(JSTracer *trc) michael@0: { michael@0: JSRuntime *rt = trc->runtime(); michael@0: for (AtomSet::Enum e(rt->atoms()); !e.empty(); e.popFront()) { michael@0: const AtomStateEntry &entry = e.front(); michael@0: if (!entry.isTagged()) michael@0: continue; michael@0: michael@0: JSAtom *atom = entry.asPtr(); michael@0: bool tagged = entry.isTagged(); michael@0: MarkStringRoot(trc, &atom, "interned_atom"); michael@0: if (entry.asPtr() != atom) michael@0: e.rekeyFront(AtomHasher::Lookup(atom), AtomStateEntry(atom, tagged)); michael@0: } michael@0: } michael@0: michael@0: void michael@0: js::MarkPermanentAtoms(JSTracer *trc) michael@0: { michael@0: JSRuntime *rt = trc->runtime(); michael@0: michael@0: // Permanent atoms only need to be marked in the runtime which owns them. michael@0: if (rt->parentRuntime) michael@0: return; michael@0: michael@0: // Static strings are not included in the permanent atoms table. michael@0: if (rt->staticStrings) michael@0: rt->staticStrings->trace(trc); michael@0: michael@0: if (rt->permanentAtoms) { michael@0: for (AtomSet::Enum e(*rt->permanentAtoms); !e.empty(); e.popFront()) { michael@0: const AtomStateEntry &entry = e.front(); michael@0: michael@0: JSAtom *atom = entry.asPtr(); michael@0: MarkPermanentAtom(trc, atom, "permanent_table"); michael@0: } michael@0: } michael@0: } michael@0: michael@0: void michael@0: JSRuntime::sweepAtoms() michael@0: { michael@0: if (!atoms_) michael@0: return; michael@0: michael@0: for (AtomSet::Enum e(*atoms_); !e.empty(); e.popFront()) { michael@0: AtomStateEntry entry = e.front(); michael@0: JSAtom *atom = entry.asPtr(); michael@0: bool isDying = IsStringAboutToBeFinalized(&atom); michael@0: michael@0: /* Pinned or interned key cannot be finalized. */ michael@0: JS_ASSERT_IF(hasContexts() && entry.isTagged(), !isDying); michael@0: michael@0: if (isDying) michael@0: e.removeFront(); michael@0: } michael@0: } michael@0: michael@0: bool michael@0: JSRuntime::transformToPermanentAtoms() michael@0: { michael@0: JS_ASSERT(!parentRuntime); michael@0: michael@0: // All static strings were created as permanent atoms, now move the contents michael@0: // of the atoms table into permanentAtoms and mark each as permanent. michael@0: michael@0: JS_ASSERT(permanentAtoms && permanentAtoms->empty()); michael@0: michael@0: AtomSet *temp = atoms_; michael@0: atoms_ = permanentAtoms; michael@0: permanentAtoms = temp; michael@0: michael@0: for (AtomSet::Enum e(*permanentAtoms); !e.empty(); e.popFront()) { michael@0: AtomStateEntry entry = e.front(); michael@0: JSAtom *atom = entry.asPtr(); michael@0: atom->morphIntoPermanentAtom(); michael@0: } michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: AtomIsInterned(JSContext *cx, JSAtom *atom) michael@0: { michael@0: /* We treat static strings as interned because they're never collected. */ michael@0: if (StaticStrings::isStatic(atom)) michael@0: return true; michael@0: michael@0: AtomHasher::Lookup lookup(atom); michael@0: michael@0: /* Likewise, permanent strings are considered to be interned. */ michael@0: AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup); michael@0: if (p) michael@0: return true; michael@0: michael@0: AutoLockForExclusiveAccess lock(cx); michael@0: michael@0: p = cx->runtime()->atoms().lookup(lookup); michael@0: if (!p) michael@0: return false; michael@0: michael@0: return p->isTagged(); michael@0: } michael@0: michael@0: /* michael@0: * When the jschars reside in a freshly allocated buffer the memory can be used michael@0: * as a new JSAtom's storage without copying. The contract is that the caller no michael@0: * longer owns the memory and this method is responsible for freeing the memory. michael@0: */ michael@0: MOZ_ALWAYS_INLINE michael@0: static JSAtom * michael@0: AtomizeAndtake(ExclusiveContext *cx, jschar *tbchars, size_t length, InternBehavior ib) michael@0: { michael@0: JS_ASSERT(tbchars[length] == 0); michael@0: michael@0: if (JSAtom *s = cx->staticStrings().lookup(tbchars, length)) { michael@0: js_free(tbchars); michael@0: return s; michael@0: } michael@0: michael@0: AtomHasher::Lookup lookup(tbchars, length); michael@0: michael@0: AtomSet::Ptr pp = cx->permanentAtoms().readonlyThreadsafeLookup(lookup); michael@0: if (pp) { michael@0: js_free(tbchars); michael@0: return pp->asPtr(); michael@0: } michael@0: michael@0: AutoLockForExclusiveAccess lock(cx); michael@0: michael@0: /* michael@0: * If a GC occurs at js_NewStringCopy then |p| will still have the correct michael@0: * hash, allowing us to avoid rehashing it. Even though the hash is michael@0: * unchanged, we need to re-lookup the table position because a last-ditch michael@0: * GC will potentially free some table entries. michael@0: */ michael@0: AtomSet& atoms = cx->atoms(); michael@0: AtomSet::AddPtr p = atoms.lookupForAdd(lookup); michael@0: if (p) { michael@0: JSAtom *atom = p->asPtr(); michael@0: p->setTagged(bool(ib)); michael@0: js_free(tbchars); michael@0: return atom; michael@0: } michael@0: michael@0: AutoCompartment ac(cx, cx->atomsCompartment()); michael@0: michael@0: JSFlatString *flat = js_NewString(cx, tbchars, length); michael@0: if (!flat) { michael@0: js_free(tbchars); michael@0: js_ReportOutOfMemory(cx); michael@0: return nullptr; michael@0: } michael@0: michael@0: JSAtom *atom = flat->morphAtomizedStringIntoAtom(); michael@0: michael@0: if (!atoms.relookupOrAdd(p, lookup, AtomStateEntry(atom, bool(ib)))) { michael@0: js_ReportOutOfMemory(cx); /* SystemAllocPolicy does not report OOM. */ michael@0: return nullptr; michael@0: } michael@0: michael@0: return atom; michael@0: } michael@0: michael@0: /* |tbchars| must not point into an inline or short string. */ michael@0: MOZ_ALWAYS_INLINE michael@0: static JSAtom * michael@0: AtomizeAndCopyChars(ExclusiveContext *cx, const jschar *tbchars, size_t length, InternBehavior ib) michael@0: { michael@0: if (JSAtom *s = cx->staticStrings().lookup(tbchars, length)) michael@0: return s; michael@0: michael@0: AtomHasher::Lookup lookup(tbchars, length); michael@0: michael@0: AtomSet::Ptr pp = cx->permanentAtoms().readonlyThreadsafeLookup(lookup); michael@0: if (pp) michael@0: return pp->asPtr(); michael@0: michael@0: /* michael@0: * If a GC occurs at js_NewStringCopy then |p| will still have the correct michael@0: * hash, allowing us to avoid rehashing it. Even though the hash is michael@0: * unchanged, we need to re-lookup the table position because a last-ditch michael@0: * GC will potentially free some table entries. michael@0: */ michael@0: michael@0: AutoLockForExclusiveAccess lock(cx); michael@0: michael@0: AtomSet& atoms = cx->atoms(); michael@0: AtomSet::AddPtr p = atoms.lookupForAdd(lookup); michael@0: if (p) { michael@0: JSAtom *atom = p->asPtr(); michael@0: p->setTagged(bool(ib)); michael@0: return atom; michael@0: } michael@0: michael@0: AutoCompartment ac(cx, cx->atomsCompartment()); michael@0: michael@0: JSFlatString *flat = js_NewStringCopyN(cx, tbchars, length); michael@0: if (!flat) { michael@0: js_ReportOutOfMemory(cx); michael@0: return nullptr; michael@0: } michael@0: michael@0: JSAtom *atom = flat->morphAtomizedStringIntoAtom(); michael@0: michael@0: if (!atoms.relookupOrAdd(p, lookup, AtomStateEntry(atom, bool(ib)))) { michael@0: js_ReportOutOfMemory(cx); /* SystemAllocPolicy does not report OOM. */ michael@0: return nullptr; michael@0: } michael@0: michael@0: return atom; michael@0: } michael@0: michael@0: JSAtom * michael@0: js::AtomizeString(ExclusiveContext *cx, JSString *str, michael@0: js::InternBehavior ib /* = js::DoNotInternAtom */) michael@0: { michael@0: if (str->isAtom()) { michael@0: JSAtom &atom = str->asAtom(); michael@0: /* N.B. static atoms are effectively always interned. */ michael@0: if (ib != InternAtom || js::StaticStrings::isStatic(&atom)) michael@0: return &atom; michael@0: michael@0: AtomHasher::Lookup lookup(&atom); michael@0: michael@0: /* Likewise, permanent atoms are always interned. */ michael@0: AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup); michael@0: if (p) michael@0: return &atom; michael@0: michael@0: AutoLockForExclusiveAccess lock(cx); michael@0: michael@0: p = cx->atoms().lookup(lookup); michael@0: JS_ASSERT(p); /* Non-static atom must exist in atom state set. */ michael@0: JS_ASSERT(p->asPtr() == &atom); michael@0: JS_ASSERT(ib == InternAtom); michael@0: p->setTagged(bool(ib)); michael@0: return &atom; michael@0: } michael@0: michael@0: const jschar *chars = str->getChars(cx); michael@0: if (!chars) michael@0: return nullptr; michael@0: michael@0: return AtomizeAndCopyChars(cx, chars, str->length(), ib); michael@0: } michael@0: michael@0: JSAtom * michael@0: js::Atomize(ExclusiveContext *cx, const char *bytes, size_t length, InternBehavior ib) michael@0: { michael@0: CHECK_REQUEST(cx); michael@0: michael@0: if (!JSString::validateLength(cx, length)) michael@0: return nullptr; michael@0: michael@0: static const unsigned ATOMIZE_BUF_MAX = 32; michael@0: if (length < ATOMIZE_BUF_MAX) { michael@0: /* michael@0: * Avoiding the malloc in InflateString on shorter strings saves us michael@0: * over 20,000 malloc calls on mozilla browser startup. This compares to michael@0: * only 131 calls where the string is longer than a 31 char (net) buffer. michael@0: * The vast majority of atomized strings are already in the hashtable. So michael@0: * js::AtomizeString rarely has to copy the temp string we make. michael@0: */ michael@0: jschar inflated[ATOMIZE_BUF_MAX]; michael@0: InflateStringToBuffer(bytes, length, inflated); michael@0: return AtomizeAndCopyChars(cx, inflated, length, ib); michael@0: } michael@0: michael@0: jschar *tbcharsZ = InflateString(cx, bytes, &length); michael@0: if (!tbcharsZ) michael@0: return nullptr; michael@0: return AtomizeAndtake(cx, tbcharsZ, length, ib); michael@0: } michael@0: michael@0: JSAtom * michael@0: js::AtomizeChars(ExclusiveContext *cx, const jschar *chars, size_t length, InternBehavior ib) michael@0: { michael@0: CHECK_REQUEST(cx); michael@0: michael@0: if (!JSString::validateLength(cx, length)) michael@0: return nullptr; michael@0: michael@0: return AtomizeAndCopyChars(cx, chars, length, ib); michael@0: } michael@0: michael@0: bool michael@0: js::IndexToIdSlow(ExclusiveContext *cx, uint32_t index, MutableHandleId idp) michael@0: { michael@0: JS_ASSERT(index > JSID_INT_MAX); michael@0: michael@0: jschar buf[UINT32_CHAR_BUFFER_LENGTH]; michael@0: RangedPtr end(ArrayEnd(buf), buf, ArrayEnd(buf)); michael@0: RangedPtr start = BackfillIndexInCharBuffer(index, end); michael@0: michael@0: JSAtom *atom = AtomizeChars(cx, start.get(), end - start); michael@0: if (!atom) michael@0: return false; michael@0: michael@0: idp.set(JSID_FROM_BITS((size_t)atom)); michael@0: return true; michael@0: } michael@0: michael@0: template michael@0: static JSAtom * michael@0: ToAtomSlow(ExclusiveContext *cx, typename MaybeRooted::HandleType arg) michael@0: { michael@0: JS_ASSERT(!arg.isString()); michael@0: michael@0: Value v = arg; michael@0: if (!v.isPrimitive()) { michael@0: if (!cx->shouldBeJSContext() || !allowGC) michael@0: return nullptr; michael@0: RootedValue v2(cx, v); michael@0: if (!ToPrimitive(cx->asJSContext(), JSTYPE_STRING, &v2)) michael@0: return nullptr; michael@0: v = v2; michael@0: } michael@0: michael@0: if (v.isString()) michael@0: return AtomizeString(cx, v.toString()); michael@0: if (v.isInt32()) michael@0: return Int32ToAtom(cx, v.toInt32()); michael@0: if (v.isDouble()) michael@0: return NumberToAtom(cx, v.toDouble()); michael@0: if (v.isBoolean()) michael@0: return v.toBoolean() ? cx->names().true_ : cx->names().false_; michael@0: if (v.isNull()) michael@0: return cx->names().null; michael@0: return cx->names().undefined; michael@0: } michael@0: michael@0: template michael@0: JSAtom * michael@0: js::ToAtom(ExclusiveContext *cx, typename MaybeRooted::HandleType v) michael@0: { michael@0: if (!v.isString()) michael@0: return ToAtomSlow(cx, v); michael@0: michael@0: JSString *str = v.toString(); michael@0: if (str->isAtom()) michael@0: return &str->asAtom(); michael@0: michael@0: return AtomizeString(cx, str); michael@0: } michael@0: michael@0: template JSAtom * michael@0: js::ToAtom(ExclusiveContext *cx, HandleValue v); michael@0: michael@0: template JSAtom * michael@0: js::ToAtom(ExclusiveContext *cx, Value v); michael@0: michael@0: template michael@0: bool michael@0: js::XDRAtom(XDRState *xdr, MutableHandleAtom atomp) michael@0: { michael@0: if (mode == XDR_ENCODE) { michael@0: uint32_t nchars = atomp->length(); michael@0: if (!xdr->codeUint32(&nchars)) michael@0: return false; michael@0: michael@0: jschar *chars = const_cast(atomp->getChars(xdr->cx())); michael@0: if (!chars) michael@0: return false; michael@0: michael@0: return xdr->codeChars(chars, nchars); michael@0: } michael@0: michael@0: /* Avoid JSString allocation for already existing atoms. See bug 321985. */ michael@0: uint32_t nchars; michael@0: if (!xdr->codeUint32(&nchars)) michael@0: return false; michael@0: michael@0: JSContext *cx = xdr->cx(); michael@0: JSAtom *atom; michael@0: #if IS_LITTLE_ENDIAN michael@0: /* Directly access the little endian chars in the XDR buffer. */ michael@0: const jschar *chars = reinterpret_cast(xdr->buf.read(nchars * sizeof(jschar))); michael@0: atom = AtomizeChars(cx, chars, nchars); michael@0: #else michael@0: /* michael@0: * We must copy chars to a temporary buffer to convert between little and michael@0: * big endian data. michael@0: */ michael@0: jschar *chars; michael@0: jschar stackChars[256]; michael@0: if (nchars <= ArrayLength(stackChars)) { michael@0: chars = stackChars; michael@0: } else { michael@0: /* michael@0: * This is very uncommon. Don't use the tempLifoAlloc arena for this as michael@0: * most allocations here will be bigger than tempLifoAlloc's default michael@0: * chunk size. michael@0: */ michael@0: chars = cx->runtime()->pod_malloc(nchars); michael@0: if (!chars) michael@0: return false; michael@0: } michael@0: michael@0: JS_ALWAYS_TRUE(xdr->codeChars(chars, nchars)); michael@0: atom = AtomizeChars(cx, chars, nchars); michael@0: if (chars != stackChars) michael@0: js_free(chars); michael@0: #endif /* !IS_LITTLE_ENDIAN */ michael@0: michael@0: if (!atom) michael@0: return false; michael@0: atomp.set(atom); michael@0: return true; michael@0: } michael@0: michael@0: template bool michael@0: js::XDRAtom(XDRState *xdr, MutableHandleAtom atomp); michael@0: michael@0: template bool michael@0: js::XDRAtom(XDRState *xdr, MutableHandleAtom atomp); michael@0: